Java Reference
In-Depth Information
NonTerm
→
→
terminal
NonTerm
OP
...
NonTerm
NonTerm
Figure 13.37: Simple Tree Patterns
How can costs and IR tree patterns be used to specify to an instruction
selector that two alternative translations are possible depending on the
size of an immediate operand?
24. Assume we have tree-structured instruction patterns limited to the two
forms shown in Figure 13.37.
That is, a nonterminal may generate a single terminal symbol or it may
generate an operator, all of whose children are nonterminals.
Give an algorithm that can walk any IR tree and determine whether it
can be covered (matched) using a set of productions limited to the two
forms described above.
25. Assume that we now add cost values (integer literals greater than or
equal to 0) to instruction patterns limited to the two forms described in
Exercise 24. Extend the algorithm you proposed in Exercise 24 so that
it now finds a
least-cost cover
. That is, your algorithm should choose
productions that minimize the overall cost of matching a given IR tree.
26. The following instruction sequence often appears in Java programs:
a[i] = ...
... = a[i];
That is, an element of an array is stored, then that same element is im-
mediately reused. Suggest a peephole optimization rule, at the bytecode
level, that would recognize this situation and optimize it using the dup
bytecode.
