Tuesday, November 20, 2007

Common branch suffixes

Another little enhancement has made its way into the Freya optimizer: common branch suffix detection. This technique detects repeated operation codes in code paths converging in a single point, and moves the branching instruction to take advantage of the common code. It's a trick for reducing code size without affecting its speed, at least, in a direct way. Of course, less code means faster JIT translation and better CPU cache performance.
Let's say we must generate code for this statement:
if condition then
a.m(p1, p2, q)
else
a.m(p3, p4, q)
The translation scheme would be as follows:
    EVAL(condition)
br.false @@else
EVAL(a)
EVAL(p1)
EVAL(p2)
EVAL(q)
callvirt m
br @@continue
@@else:
EVAL(a)
EVAL(p3)
EVAL(p4)
EVAL(q)
callvirt m
@@continue:
It's hard for the compiler to detect the common code in the Abstract Syntax Tree, so this is a task for our peephole optimizer. The optimizer kicks in after each unconditional jump, and scans backwards in parallel, from the branching point and the branch target. The above translation scheme is simplified this way:
    EVAL(condition)
br.false @@else
EVAL(a)
EVAL(p1)
EVAL(p2)
br @@continue
@@else:
EVAL(a)
EVAL(p3)
EVAL(p4)
@@continue:
EVAL(q)
callvirt m
In almost all situations, this change won't affect speed. There is, however, a case where we must be careful: suppose our conditional was the last statement in a method. In that case, the unconditional branch would jump into a return code, and the peephole optimizer would have substituted the jump with a direct return, saving the time consumed by the jump. To prevent this, common branch suffixes are always detected after the jump optimizer has finished its own duty.
About the impact of this optimization in real-world applications, please note that our example can't benefit from Freya's conditional expressions. What's more, the automatically generated code for iterators typically contains many assignments to the state field that can be factored out with our technique.

Labels: ,

0 Comments:

Post a Comment

<< Home