Java Reference
In-Depth Information
Stmts
⇒
⇒
⇒
IF
OP
Plus
IntLit3
Plus
True
Stmts
IntLit1
IntLit2
IntLit2
Plus
IntLit3
Var
IntLit1
Var
(a)
(b)
(c)
Figure 13.31: AST-Level Peephole Optimization
+
⇒
IntLit3
IntLit
⇒
OP
+
<<
+
IntLit
*
⇒
⇒
IntLit
IntLit1
IntLit2
+
IntLit1
2
n
IntLit3
0
(a)
(b)
(c)
(d)
*
IntLit
IntLit
+
+
+
⇒
IntLit
⇒
⇒
−
1
IntLit1
IntLit2
IntLit1
IntLit1
−
IntLit1 IntLit2
IntLit2
(e)
(f)
(g)
Figure 13.32: IR-Level Peephole Optimizations
is always true is replaced with the body of the conditional. In (b) and (c),
expressions involving constant operands are
folded
(replaced with the value
of the expression). This folding optimization can expose other optimizations
(such as the conditional replacement optimization of (a)).
Optimizations at the AST level can be conveniently implemented using a
tree rewriting tool like BURS. Source patterns are first recognized and labeled.
Then, during the “processing” traversal, trees can be rewritten into the target
form. If necessary, an AST can be traversed several times, so that rewritten
ASTs can be matched and transformed several times.
IR-Level Optimizations
As illustrated in Figure 13.32, a variety of useful optimizations can be per-
formed at the IR level. In (a) and (b), constant folding is specified. Since
some arithmetic operations are exposed only after translation (e.g., indexing
arithmetic), folding can be done at both the AST and IR levels. In (c), multi-
plication by a power of 2 is replaced with a left shift operation. In (d) and (e),
identity operations are removed. In (f), the commutativity of addition is ex-
posed, and in (g), addition of a negative value is transformed into subtraction.
Transformations on IR trees can be conveniently implemented using a tool like
BURS.
