Last updated March 18, 1997.Brian Grant (grant@cs.washington.edu)
This document is dated, but much of it is still applicable to our current design. The annotations, of course, have changed. See Markus's quals writeup for a description of makeStatic and makeDynamic, the new types of policies, and the new function annotations. In summary, keepConst has become makeStatic, with a few more options added.
Consequently, the BTA has changed as well. Some aspects of it are up in the air. We think that the live-variables analysis must precede the BTA. It is possible that the BTA need not be iterative if we have sufficient use-def information, but the reachability analysis might require iteration. It is clear that we must keep track of the derivations of all static variables, and that keeping track of which annotated variable each temp corresponds to is a pain. Clustering of unit boundaries will have to either happen within the BTA, or clustering could incrementally update output from the BTA, or the BTA may need to run before and after clustering.
Our approach to building the specialized dynamic compilers has also changed. Charlie and Matthai have written a Perl script to merge the setup code with the template code in a post-pass to the compiler. So, Multiflow will run only once, at a cost of less well scheduled code in the specialized dynamic compiler.
The cache scheme has changed to a simpler, flat design. There will be one flat cache per unit.
Many of these changes should be outlined in our upcoming PEMP '97 paper.
In the next-generation dynamic-compilation system, we have planned to integrate setup and stitching. We have also designed a more general set of annotations that requires replicating specialization and lazy stitching of nested dynamic regions. Thus, we must implement both eager and lazy stitching.
This document describes how the static compiler will construct a fast specialized dynamic compiler for each dynamic region. The dynamic compiler will perform both setup and stitching, and lazily stitch when required.
In the following description of our approach to setup and stitching, I will generally refer to the combined task of setup and stitching simply as stitching.
For the next generation of our dynamic-compilation system, we designed all-new annotations based around keepConst. The only annotation we have preserved from the original set is the dynamicRegion construct.
The dynamicRegion annotation need not be single-entry or single-exit, but must be completely contained within a function. As before, it is used to demarcate a code region that is to be specialized. dynamicRegions may be nested.
The isConst and keepConst annotations specify the variables on which the region is to be specialized. These variables are called run-time constants because their values are hardcoded into each specialized version of the code, like true constants in statically compiled code. The annotations may be used at the beginning of or anywhere within a dynamic region.
isConst indicates that particular variables are to be made run-time constants in the specialized code that follows until their values can no longer be uniquely determined from true and run-time constants. keepConst implies this as well, but further dictates that code replication should be used to keep the specified variables run-time-constant past merges of paths on which the variables acquire different run-time-constant values, past late entries into a dynamic region (if there are multiple entries), and past assignments of dynamic values (e.g., input) to the specified variables. If keepConst is used on a loop induction variable, and the loop bound is also a run-time constant, the effect is the unrolling of the loop. The unkeepConst annotation can be used to terminate this replicating specialization prior to the end of the enclosing dynamic region.
lazy is a hint to the dynamic-compilation system that it might want to stitch the annotated statement lazily. When the system cannot determine that it is safe to stitch the statement eagerly, it ensures that the statement is stitched lazily. The current effect of the annotation is to cause conditionals (?:, ||, &&, if, switch, while, and for) to be stitched lazily.
Some of the new functionality these annotations provide include:
For a complete description of the new annotations, see the annotations document.
As mentioned above, it is possible to nest dynamic regions, or even overlap specialization policies in unstructured ways using isConst, keepConst, and unkeepConst. The values of the variables to become run-time constants are not known until the isConst or keepConst annotation is reached, unless the variables are already run-time constants (it is permissible to use isConst and keepConst on variables that have already been annotated for specialization or that are derived run-time constants). The values of variables to be kept constant may also be unknown after dynamic assignments. For these reasons, we must lazily stitch portions of dynamic regions. Note also that the outermost region must always be lazily stitched when it is reached from the surrounding code.
Since some laziness is required, we considered stitching all templates lazily. In such an implementation, the template code could be executed along with the setup code and stitcher instructions since the program's original control flow would be followed. In the mixed-eager/lazy approach (eager stitching where possible, and lazy stitching only when necessary), multiple paths through the graph are stitched eagerly, violating the program's original control flow, and requiring all eager stitching be completed before executing the stitched templates.
In the all-lazy approach, fewer context switches between the stitcher and the stitched code should be required during the first run through the code, but more context switches may be required to switch back to the stitcher to stitch unstitched paths through the code compared to the mixed-eager/lazy approach. Also, interleaving the three types of instructions (setup, stitcher, template) in the all-lazy approach may create additional register pressure and spills. Because of the questionable benefit of the all-lazy approach and its possible disadvantages, we decided on the mixed-eager/lazy approach.
However, it should be pointed out that eager stitching is potentially unsafe. If some unsafe code to be specialized is guarded by a dynamic conditional, then the stitcher could raise an exception (e.g., a/b, tan(a), *p) or enter into an infinite loop while stitching eagerly, although the program ran correctly when statically compiled. This case can occur because the BTA cannot always determine the relationship between the conditional predicate and the unsafe expression. Thus, we should provide a mechanism for the programmer to ensure that unsafe code of this type is stitched lazily. This is the rationale behind the lazy annotation.
Since we must implement both eager and lazy stitching anyway, we have also decided to implement the eager and lazy specifications designed for the keepConst annotation to control the eagerness of code replication. The same implementation should work for all types of eagerness and laziness.
Replicating specialization, triggered by the keepConst annotation, keeps a variable run-time-constant beyond dynamic assignments and beyond merges where the variable has different definitions, run-time-constant or dynamic, on different incoming edges, as long as the variable is run-time-constant on at least one incoming edge. This is achieved by duplicating the code beyond such merges, called discordant merges, specializing the code for the different incoming values of the variable. The following code shows a typical example.
dynamicRegion {
...
x = foo(x, y, z);
keepConst(x);
/* one version will be generated for every
value of x */
...
if (d)
x += 1;
else
x += 2;
/* two versions of the code that follows
will be generated for every version of
the preceding code */
...
}
Replication ends at an unkeepConst annotation, at the end of the enclosing dynamic region, or after the last reference of the variable to be kept constant (the last case is an optimization).
The following code presents a simple example of nested and overlapping regions of replicating specialization.
dynamicRegion {
unit_0: /* Kconst={} */ ...
keepConst(x);
unit_1: /* Kconst={x} */ ...
keepConst(y);
unit_2: /* Kconst={x,y} */ ...
keepConst(z);
unit_3: /* Kconst={x,y,z} */ ...
unkeepConst(y);
unit_4: /* Kconst={x,z} */ ...
unkeepConst(x);
unit_5: /* Kconst={z} */ ...
}
Here is an example of multi-way unrolling of a byte-code interpreter for a language that allows indirect jumps on run-time-computed values (e.g., a hardware simulator). The instructionList is an array of instructions that will be run-time-constant. opcode(pc) extracts the operation from the instruction, and is a derived run-time constant. firstOperand(pc) and secondOperand(pc) are used to extract the operands from the instruction at pc, and are also derived run-time constants. The registerFile is an array used to represent the register file, and its contents are dynamic.
dynamicRegion {
...
pc = &instructionList[0];
keepConst( pc :cache);
keepConst(*pc :unchecked);
while (opcode(pc) != RETURN) {
...
switch opcode(pc) {
case BR:
/* we can compute the pc on both paths eagerly
* ==> multi-way unrolling
*/
if (registerFile[firstOperand(pc)]) {
pc += secondOperand(pc);
} else {
pc += 4;
}
break;
case IJMP:
/* no way to compute the new pc eagerly!
*/
pc = registerFile[firstOperand(pc)]; break;
...
default:
pc += 4; break;
}
}
}
The keepConst annotations will cause the loop to be multi-way unrolled. The IJMP instruction does not prevent the unrolling, though it does halt eager stitching. When the IJMP case is reached in the stitched code, a cache check will determine whether the loop has been unrolled for the new pc value. If not, then control will transfer back to the stitcher, with eager multi-way unrolling again proceeding from there.
Replicating specialization essentially requires splitting at merges where variables to be kept constant could have different incoming values. However, the situation is complicated by loops. At merges with different incoming sets of variables to be kept constant, the graph is split in the BTA. At discordant merges where the same variables are to be kept constant on all incoming paths, replicating specialization is implemented using the same mechanism as for implementing nested dynamic regions: specialization units (discussed below). The same decisions about whether or not to perform cache checks and whether to stitch lazily or eagerly apply to the beginnings of dynamic regions and to discordant merges.
Run-time efficiency. We decided to merge the setup code and stitching to reduce our run-time overheads. The more work we can do statically, the less work required by the dynamic compiler.
In order to construct a specialized dynamic compiler, we will run
the static compiler on the annotated source file twice. Both times,
the initial steps will be the same.
Afterwards, during the first run of the static compiler, the
following steps must be taken to generate the templates and directives
to the second pass.
In the second run of the static compiler, the templates are read
from the object file generated during the first pass and incorporated
into the setup code to construct the specialized stitcher.
Every program point is specialized on the set of computed run-time constants, called the RTconst set. However, we only need to generate different specialized versions of the code when variables must be kept constant whose values cannot be computed from values of other run-time constants. This can occur at isConst or keepConst annotations or when a variable to be kept constant is assigned a dynamic value. So, we can use the RTconst set and the set of variables to be kept constant, called the Kconst set, to decide when we may need to generate a new specialized version.
To manage specialization of different portions of the dynamic region on different variables, we partition the graph into specialization units. Each unit is specialized on a particular set of variables. A unit is marked eager if the values on which it specializes can be computed based of the values of run-time constants from preceding units, and lazy if it must specialize on potentially dynamic values.
The unit-partitioning algorithm operates on basic blocks of the CFG for the dynamic region. So, we must partition a basic block if something important happens in the middle. We must partition a block in the following circumstances:
Once we're sure that the only changes to the RTconst, Iconst, and Kconst sets we care about happen between basic blocks, we can partition the graph. We can perform the partitioning by traversing the nodes of the graph in topological order and by marking nodes with the head of their unit.
We must begin a new lazy unit at node N, with N as the unit's head, in the following situations:
We must begin a new eager unit at node N, with N as the unit's head, in the following situations:
Otherwise, the node is assigned to the same unit as its immediate predecessors. At this stage, all immediate predecessors must have the same Kconst sets because merges with different Kconst sets are split in the BTA. That means we don't have to mark any units created by the last rule (multiple preceding units) as lazy.
*: Actually, we want to delay the creation of a new unit until the variable first becomes live, and then only create a new unit if the value of the variable cannot be derived from constants and run-time constants. We may also need to examine where run-time contants die, or at least where they permanently die (and will not be resurrected). Perhaps a liveness analysis should follow the BTA and refine its output.
During this process, we can also insert the cache checks. Cache checks must be inserted in both the stitcher and in the stitched code. In the stitched code, we need a cache check when the code that follows must be specialized on a variable with a dynamic value. These checks are inserted into blocks with branches to lazy units. If the cacheing policy of the lazy unit is cache or cache1, then the emitted branches to the unit are replaced with an emitted cache check and either a branch to the stitched code or a context switch to the stitcher at the lazy unit. If the cacheing policy is replicate, the emitted branches are replaced by just a context switch to the stitcher. If the policy is unchecked, the emitted branches are replaced with an indirect jump that initially goes to code that performs a context switch to the stitcher, but is switched to point to the stitched code after the stitcher executes (as in the prototype). The same can be done for lazy units created voluntarily through the annotations, when the context is known to be the same as the unit's predecessors'.
In the stitcher, lazy units need no cache checks because the checks are performed in the stitched code. However, we may need to perform other actions. If the cache policy is cache1, the old stitched version of the lazy unit must be removed from the cache. If the policy is unchecked, the stitcher must change the indirect jumps to the unit to jump to the stitched code. In the head of the lazy unit, we also need to set a variable with the address of the code that is about to be stitched.
Cache checks are needed in the stitcher at the tops of eager units whose cache policies are cache or cache1 and which are preceded by either multiple units or a single unit with a different Context set (includes variables from both the Iconst and Kconst sets). If we reach an eager unit that is in the cache, we know we can stop because all eager units following the unit must also be in the cache. So, if the eager unit is in the cache, then patch branches from the code just stitched into the units in the cache and switch to the code just stitched. If the cache policy is unchecked, then the check is still required, but only that there is some version in the cache (the whole context is not checked). A check can be eliminated completely between an unchecked unit and one with the same Context set as its predecessors because we know the unchecked unit will be stitched only once for each version of its predecessors.
To optimize cache checks, we must establish a hierarchy of units specialized on the same variables. The cache can be structured as a lattice based on the context of each unit. Units with unchecked cache policies are inserted in the cache as if they belong in their parents' context.
For every unit for which a cache check is required, we must enter that unit into the cache. We will maintain a cache for each context type (the particular Context set). Each such cache will contain a hash table of pointers to per-context caches. Each per-context cache will have pointers to caches for context types that are strict supersets of the current context type and to the units specialized for the context.
When moving from one context to another, the cache pointer must be changed to point to the current cache. Only the additional context need be checked when moving to a new context that is a superset of the old one. When moving to a subset context, merely look for the correct unit (no context needs to be checked).
The following code example creates seven units and five context types.
dynamicRegion {
Unit0: /* Context={} */ ...
keepConst(x);
Unit1: /* Context={x} */ ...
keepConst(y);
Unit2: /* Context={x,y} */ ...
keepConst(z);
Unit3: /* Context={x,y,z} */ ...
Unit4: z = dynamic_foo(z); ...
unkeepConst(y);
Unit5: /* Context={x,z} */ ...
unkeepConst(Z);
Unit6: /* Context={x} */ ...
}
Here is the cache structure created after one execution of the region (x=1, y=7, z=3 initially and z=9 after the call to dynamic_foo):
RootCache = Cache0
Cache0
ParentContext= NIL
ContextType= ()
ContextHashTable= {Context0}
Context0
ParentCaches= {Cache0}
Context= ()
SubCacheHashTable= {Cache1}
UnitHashTable= {Unit0}
Cache1
ParentContext= Context0
ContextType= (x)
ContextHashTable= {Context1}
Context1
ParentCaches= {Cache1}
Context= (1)
SubCacheHashTable= {Cache2, Cache4}
UnitHashTable= {Unit1, Unit6}
Cache2
ParentContext= Context1
ContextType= (x,y)
ContextHashTable= {Context2}
Context2
ParentCaches= {Cache2}
Context= (1,7)
SubCacheHashTable= {Cache3}
UnitHashTable= {Unit2}
Cache3
ParentContext= Context2
ContextType= (x,y,z)
ContextHashTable= {Context3, Context4}
Context3
ParentCaches= {Cache3}
Context= (1,7,3)
SubCacheHashTable= {}
UnitHashTable= {Unit3}
Context4
ParentCaches= {Cache3, Cache5}
Context= (1,7,9)
SubCacheHashTable= {}
UnitHashTable= {Unit4}
Cache4
ParentContext= Context1
ContextType= (x,z)
ContextHashTable= {Context5}
Context5
ParentCaches= {Cache4}
Context= (1,9)
SubCacheHashTable= {Cache5}
UnitHashTable= {Unit5}
Cache5
ParentContext= Context5
ContextType= (x,y,z)
ContextHashTable= {Context4}
Note at the cache check for Unit5, we first check the parent caches of Context4 for the correct parent context. If the correct context is not found, as when the check is done for the first time, then we must check the subcaches of Context1.
Minimize stitch-time overhead by:
The depth-first topological traversal is the traversal algorithm most commonly applied to CFGs. In a topological traversal (TT), no successor is traversed before a predecessor, which simplifies analyses and makes it easier to maintain invariants on the graph.
Here is a list of reason why we should put the blocks in topological order, roughly ordered from most important to least important.
Unfortunately, we don't want to stitch all blocks in a unit.
Essentially, static branches select among different sets of blocks
that should be stitched. That doesn't sound so bad. However, the
situation becomes complicated in the presence of:
We have the most troubles when all three of these situations occur simultaneously. In particular, chains of overlapping back edges directed into the bodies of static ifs are present the biggest challenge. If a loop head is reached from one path, and its tail from another, then we must ensure the head will be stitched if the tail is reached. However, by the time the tail is reached, it is usually too late to then stitch the head, if we want to maintain topological order.
Another issue also arose in the discussion of reordering blocks in a unit. There was a vague feeling that maybe we should try to preserve "structured subgraphs". However, because of the difficulty in identifying such subgraphs and because of the difficulties created by violating the topological order, this idea was abandoned.
Finally, I was originally attempting to be more aggressive in eliminating the use of stacks and worklists to traverse the CFG, reserving their use only for implementing an eager solution to replicating specialization. Relaxing this goal, breaking the graph into smaller specialization units, and traversing the units using a stack simplified the reordering algorithms.
Over the past three months, I have been working towards a solution to this problem. I have proposed several algorithms for linearizing the blocks of the CFG. I will summarize them here and then explain the chosen algorithm in detail.
In this solution, the CFG is traversed with a DFTT and a duplicate graph is constructed with the same nodes but different edges from the original. The paradigm for the algorithm is edge redirection. That is, an edge in the duplicate graph either goes to its original destination or is redirected (or is omitted from the duplicate graph). The result was essentially a topological sort of the graph, but with static branches left intact to skip blocks that did not need to be stitched.
Unfortunately, this solution never fully worked. It's remaining problems were:
This strategy solved many of the problems of the edge-redirection approach. The algorithm identifies blocks that can be strung together and those that are reached by static branches. It does this by computing nested equivalence classes of blocks on the reachability conditions. New equivalence classes are spawned by static branches and disjunctive merges, merges that introduce disjunctions into the reachability conditions. Blocks in the same equivalence class can be linearized. Blocks in a nested equivalence class are linearized before the parent class is linearized.
Blocks that are reachable by different static branches are those in equivalence classes spawned by disjunctive merges. The decision to stitch such blocks is postponed until it has been definitively determined whether or not they need to be stitched. Loops are not a problem because the loop head is either in the same equivalence class as the tail, in an ancestor class, or in a disjunctive-merge class nested in an ancestor class.
A big advantage over the edge-redirection approach is that no jumping back is necessary. The checks on the missed blocks are performed in one place. Another is that the algorithm is easier to understand.
One disadvantage is that some checks may be performed unnecessarily. Another is that because the disjunctive-merge classes are appended to the end of their parent class, live ranges of the run-time constants they reference can be extended.
The splitting-and-merging approach eliminates the need for checks and maintains strict topological order on the blocks within a unit. The concept for this algorithm is based on splitting at merges and stitching a subset of the graph in topological order, the subset being determined by which static branches are taken at stitch-time.
We maintain a list in topological order of blocks that need to be stitched and a list of nodes we need to visit. We first add the unit head to the list of blocks that we need to visit. Then, we repeatedly remove the block with the least topological number from that list, add it to the list of blocks that need to be stitched, and add the children of the block to the list of nodes we need to visit. We duplicate the two lists for every path from every static branch, creating a number of lists that is exponential in the number of static branches.
The merging algorithm uses the lists of nodes that must be stitched along the different paths to create the final graph.
This algorithm creates a list of lists of blocks for each unit. These lists are then passed to the merging algorithm for merging. The blocks in each list are in topological order. Each list corresponds to one combination of true and false paths from static branches. So, the first list contains the blocks reached when all static branches in the unit evaluate to true, and the last list contains the blocks reached when they all evaluate to false.
As presented, this algorithm has a problem with back edges from one side of a static if into another static if body. This situation can create a difference between lists (i.e., blocks in one list but not the other) before the static branch causing the difference appears in the lists. The two possible solutions are to include the blocks in question in both lists, or to move the blocks below the static branch. The first solution has the disadvantage that some blocks will be unnecessarily stitched on some paths. The second solution inhibits merging. I plan to go with the second solution because its run-time efficiency is higher (no blocks unnecessarily stitched) and because it is easier to implement.
Note that this algorithm assumes that units cannot contain disconnected blocks.
The merging algorithm requires a tree rather than a list of lists. That tree can be reconstructed from the lists generated by this algorithm, or this algorithm can be modified to generate the tree directly.
procedure SortAndSplitUnits(UnitRootList) {
UnitPathList = CreateEmptyList(1, 0, Zero)
until EmptyList(UnitRootList) {
/* Get the root of this specialization unit */
(CurrentUnit) = RemoveHeadOfList(UnitRootList)
PathStack = CreateEmptyStack(2)
VisitedNodeList = CreateEmptyList(2, 0, Topo#)
InsertIntoList(UnitPathList, (VisitedNodeList))
NextNodeList = CreateEmptyList(1, 0, Topo#)
InsertIntoList(NextNodeList, (CurrentUnit))
PushOntoStack(PathStack, (VisitedNodeList,
NextNodeList))
until EmptyStack(PathStack) {
/* Start on a new path through the unit */
(VisitedNodeList, NextNodeList) = PopOffStack(PathStack)
/* Add to the path until it is completed */
until EmptyList(NextNodeList) {
(NextNode) = RemoveHeadOfList(NextNodeList)
if EndsInStaticBranch(NextNode) {
/* Static branches spawn new paths through the
unit. The current path follows the first edge.
*/
for each outgoing edge NextNode->Edge[i]
except the first (in reverse topo. order) {
/* Create a new path */
NewVisitedList = CopyList(VisitedNodeList)
InsertIntoList(UnitPathList, (NewVisitedList))
/* Keep track of which path we took */
InsertIntoList(NewVisitedList,
(NextNode, NextNode->Edge[i]->Condition))
/* Work on each new path begins at a different
destination. Stay within the unit and
don't revisit visited nodes (must check
because we follow back edges).
*/
NewNextList = CopyList(NextNodeList)
Destination = NextNode->Edge[i]->Destination
if ((UnitHead(Destination) == CurrentUnit) &&
(! IsInList(NewVisitedList, (Destination,
*)))) {
InsertIntoList(NewNextList, (Destination))
}
PushOntoStack(PathStack,
(NewVisitedList, NewNextList))
}
InsertIntoList(VisitedNodeList,
(NextNode, NextNode->Edge[0]->Condition))
Destination = NextNode->Edge[0]->Destination
if ((UnitHead(Destination) == CurrentUnit) &&
(! IsInList(VisitedNodeList, (Destination, *)))) {
InsertIntoList(NextNodeList, (Destination))
}
}
else {
InsertIntoList(VisitedNodeList,
(NextNode, NoCondition))
/* Visit all children of this node that are in
this unit and that have not already been
visited.
*/
for each outgoing edge NextNode->Edge[i] {
Destination = NextNode->Edge[i]->Destination
if ((UnitHead(Destination) == CurrentUnit) &&
(! IsInList(VisitedNodeList, (Destination,
*)))) {
InsertIntoList(NextNodeList, (Destination))
}
}
}
}
DestroyList(NextNodeList)
}
DestroyStack(PathStack)
}
DestroyList(UnitRootList)
return UnitPathList
}
First, we merge the lists from the front to create a tree with forks at static branches. As mentioned above, we could alternatively create the tree in the splitting algorithm. Given the tree, we then merge its branches, starting with the leaves. The result is a DAG.
For each unit:
This algorithm does not perform some of the reordering optimizations we discussed previously. For example, if all successors of a static branch represented the same block, then we could merge the successors and move the merged node above the branch. Or, if one predecessor of a merge appears in more lists than another, and they both appear in some lists, the more frequently occuring predecessor should be listed last (changing the topological order) so that more merges could be performed.
However, I feel that those cases would occur infrequently and the merging algorithm would be unnecessarily complicated by the addition of code to handle them. If we later feel it is necessary, we can create another pass to reorder blocks to create more opportunities for the merging algorithm.
Where are there emitted branches to eager units, also push the eager units to a unit stack. At the leaves of a unit with no eager successors, pop from the unit stack. If the stack is empty, switch to the code just stitched.
To ensure Multiflow allocates registers appropriately and that it inserts needed spills and loads, on each leaf of a unit with:
I'm not entirely sure this solution will work. I need to find out what is possible in Multiflow before this problem will be solved conclusively.
We also need to ensure that all run-time constants live across edges to lazy units are saved so that they can be restored when returning to the lazy units. Furthermore, we need to pass new run-time-constant values from the stitched code to the stitcher when stitching lazy units.
Most of the lazy-stitching discussion was focused on minimizing context-switching overhead. We can generate specialized fix-up code to save and restore context and to pass new run-time-constant values to the stitcher in registers. Should we use the JSR_COROUTINE instruction? How exactly we will do this remains an open question that likely won't be solved until we try to do it.
Last updated March 18, 1997.