-
Title:
The Living and the Dead Solution - Programming Languages
-
Description:
-
For this homework, we asked you to remove dead code.
-
That is code that could not have any effect
-
on the final return result of the method we’re
-
interested in. So, let’s go ahead and just dive right
-
into this. We take a fragment; if you remember
-
the fragments are of this shape where the first part
-
of the tuple is the variable to be assigned to and
-
then the next part of the tuple is the expression
-
that is being assigned to it, in this case one is
-
being assigned to A or A operational, one is being
-
assigned to B, 2 is being assigned to C etcetera.
-
Now we’re not really concerned with what
-
specifically the operations are. We don’t care
-
what operations are being done. We just care that
-
something is being done to these variables,
-
because if there is something being done, even if
-
it ends up setting them to the exact same thing, we
-
can’t necessarily know that ahead of time. So, if
-
you have a fragment of this shape, then we store
-
that as the old fragment, as the un-optimized
-
fragment. And that’s the first argument to this
-
method. And the return is the end return value;
-
it’s the list of variables returned at the end of the
-
fragment. And if they’re returned at the end of the
-
fragment, they’re automatically live, as we said
-
up here. Now we want to create a new optimized
-
fragment of just the live variables. So we start off
-
by initializing that to an empty list. And we set a
-
variable called live equal to the returned live
-
variables, because we know those are live.
-
Now for every statement in the fragment starting from
-
the back, so we’re working backwards from the
-
return statement, back up to the top, we check if
-
the first element of the tuple statement, that is the
-
left hand side of the statement, is already in live.
-
That is, it is one of the live variables currently.
-
If it is, then we add that statement to the new
-
optimized fragment. Otherwise we fall through
-
and now we take the list of live variables and we
-
remove the variables that we’re now assigning to.
-
So we take all those out. From there, we update
-
the live list with all the variables that are currently
-
on the right hand side of statement. We run
-
through the entire fragment doing that over and
-
over until we get back to the top. Once we’re
-
done with that, we check if the new fragment is
-
equal to the old fragment. If it is, then we return
-
the new fragment. We didn’t change anything.
-
So we just return and stop and we’re done. If it isn’t,
-
well, then we might have further optimizations as
-
we discussed earlier. Then we return, removing
-
dead of the new fragment in return. So we
-
recursively call this until we don’t get any
-
further changes, because hopefully we can
-
optimize further. Now we’re going to check that
-
removed dead gives us what we would expect if
-
we ran through all the optimizations by hand, and
-
I’m not going to bother going through all of these.
-
You can read them fairly easily and when we do
-
that, we see that we get true values for each of
-
these. This is a fairly involved little bit of code.
-
It takes a little bit to think about and this is a
-
very useful optimization because we can
-
potentially get rid of a lot of code doing this.
