Jeff Dean presented a sequences of slides that illustrated
the solution that he and Joel came up with for the identifying
the problem of marking variables in an arbitrary flowgraph
as "static" or "dynamic" given a set of variables known
to be static in some part of the flow graph.
static == run time constant
dynamic == variable
Slide 1: problem definition
Slide 2: Merges
Slide 3: The "family of graphs" viewpoint
Slide 4: Identifying Phantom Merges
One of the claims in slide 4 was that control dependence is insufficient'
for our purposes. Slide 4 (a) gives an example of a graph that
illustrates this failure. Nodes C in this graph are not control
dependent on node A, but we would still like to reason about this
graph and eliminate one of the edges coming out of A, for example.
At this point, Craig and Dave pointed out that control dependence should
be transitive; Jeff suggested perhaps transitivity holds only for structured
graphs.
Craig noted that we should relate the "Reachability Tracking" approach
to control dependence by the time PLDI comes around.
Slide 5: Reachability Tracking
Slide 6: Handling Branches
Jeff and Joel noted that upstream knowledge is used to solve static/
dynamic problems simulaneously, in the sense that at branch we have
to do two things:
i)From the merges, deduce the identity and values of all static
constants.
ii)Depending on whether the branch variable at the current branch
is static/dynamic, decide how to annotate the outgoing branches.
Craig remarked that this notion/method of solving two inter-related problems
simultaneously is interesting.
Craig asked how propagated information was represented: Joel and Jeff
answered that many representations seem to be possible, but naive
implementations are exponential space. Conceptually, however, the information
just corresponds to having a true/false corresponding to the branch decision
taken at each branch on the way to the current arc.
7)Handling merges
The merge rule was defined here, and there was some confusion on
what it meant to "intersect the sets of sets" representing two
paths. The answer was that the inner sets are considered atoms
and you then use the conventional set intersection on the
outer set.
After the intersection confusion was resolved:
Jeff/Joel: Stitching can be viewed as a modification of the flowgraph
that throws out some edges.
Craig: We've labelled pieces of the graph with the conditions under
which the code can be generated...
Jeff/Joel: ...under which the code will be reached.
Susan asked if the variable-value bindings were also being propagated.
Jeff said yes; these bindings are resolved at each merge after the merge rule
is selected. Merge rule selection is what the Reachability Tracking
algorithm does.
Jeff asserted that loops are just special cases of the merge rule.
The iteration of the algorithm through the back edge will not
invalidate any of the annotations on the edges because we record
only static variables in these annotations, and these static variables
will not change over loop iterations.
We spent the last 10 minutes talking about unrolling loops. Specifically,
Craig wanted to re-examine the issue of checking whether we _could_
unroll a loop.
Jeff's loop unrolling slide was buggy, because it contained multiple exits.