An interesting problem arises when we compile trace trees. When an instruction in the tree (which means its on the loop body) refers to an instruction in the header (so its outside the loop body), we have to make sure to assign a register to the instruction outside the loop body that is globally untouched, even in paths we already compiled (in case we detect this scenario half way through compiling a tree).
Archive for May, 2007
Virgin Registers
May 31, 2007Untyped Context Nodes
May 30, 2007Michael wrote on his blog about untyped context nodes.
Context nodes represent the local variable/stack state along the incoming edge into the trace tree, which again is really a loop. Since loops almost always have an empty stack at entry, its really just the local variables we have to be concerned with. Context nodes point to these local variable slots, and whenever an instruction in the tree refers to them it really means that the instruction wants to operate on the value that was in that JVM local variable at loop entry, or whatever value was written their during a previous loop iteration in case the value is updated by at least one path in the tree.
Containment Analysis & Lock Elimination
May 30, 2007Eliminating locks on objects that our Containment Analysis has identified to be local as long we stay in the trace is simple. Each trace in the tree is just a linear sequence of instructions, and we can use a slightly beefed up Common Subexpression Elimination pass to eliminate redundant lock/unlock pairs. For side exits we have to keep track whether at the side exit point the object is locked or unlocked. If its locked, the lock has to be taken in the side exit path.
As long we stay in the tree, no locks will ever be needed, only side exits might require to lock the object, because it might “go global” behind the side exits, and the interpreted code might rely on the object be already locked (if the code in the loop was supposed to do that before we eliminated the lock path).
Containment Analysis
May 30, 2007The idea behind Containment Analysis is to use a trace tree to find objects that are created locally in side the trace tree, and also die within the same scope. Such objects can be stack allocated, and even more importantly, do not have to be locked. So whats so different about Containment Analysis? Well, first of all Escape Analysis is pretty cumbersome and expensive because its an intraprocedural analysis. You have to not only look at the code of a method to determine whether objects escape, but also analyze all methods that call it, and any method it in turn invokes. The dataflow analysis required for that is quadratic, and not necessarily cheap to perform. Trace trees represent a hot loop and inline all paths through that hot code into one data structure. This eliminates the need to do intraprocedural analysis. All the code we have to consider is right there in the trace tree.
