A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition), страница 31

Our goal issimply to pull s out of the BINOP expression; but now (to preserve the order of evaluation)we must pull e1 out of the BINOP with it. To do so, we assign e1 into a new temporary t, andput t inside the BINOP.144It may happen that s causes no side effects that can alter the result produced by e1. This willhappen if the temporaries and memory locations assigned by s are not referenced by e1 (and sand e1 don't both perform external I/O). In this case, identity (4) can be used.We cannot always tell if two expressions commute. For example, whether MOVE(MEM(x),y) commutes with MEM(z) depends on whether x = z, which we cannot always determine atcompile time. So we conservatively approximate whether statements commute, saying either"they definitely do commute" or "perhaps they don't commute." For example, we know thatany statement "definitely commutes" with the expression CONST(n), so we can use identity(4) to justify special cases likeThe commute function estimates (very naively) whether a statement commutes with anexpression:static boolean commute(Tree.Stm a, Tree.Exp b) {return isNop(a)|| b instanceof Tree.NAME|| b instanceof Tree.CONST;}static boolean isNop(Tree.Stm a) {return a instanceof Tree.EXP&& ((Tree.EXP)a).exp instanceof Tree.CONST;}A constant commutes with any statement, and the empty statement commutes with anyexpression.

Anything else is assumed not to commute.GENERAL REWRITING RULESIn general, for each kind of Tree statement or expression we can identify the subexpressions.Then we can make rewriting rules, similar to the ones in Figure 8.1, to pull the ESEQs out ofthe statement or expression.For example, in [e1, e2, ESEQ(s, e3)], the statement s must be pulled leftward past e2 and e1. Ifthey commute, we have (s; [e1, e2, e3]). But suppose e2 does not commute with s; then wemust haveOr if e2 commutes with s but e1 does not, we haveThe reorder function takes a list of expressions and returns a pair of (statement, expressionlist).

The statement contains all the things that must be executed before the expression-list. Asshown in these examples, this includes all the statement-parts of the ESEQs, as well as anyexpressions to their left with which they did not commute. When there are no ESEQs at all wewill use EXP(CONST 0), which does nothing, as the statement.Algorithm Step one is to make a "subexpression-extraction" method for each kind. Step twois to make a "subexpression-insertion" method: Given an ESEQ-clean version of eachsubexpression, this builds a new version of the expression or statement.145These will be methods of the Tree.Exp and Tree.Stm classes:package Tree;abstract public class Exp {abstract public ExpList kids();abstract public Exp build(ExpList kids);}abstract public class Stm {abstract public ExpList kids();abstract public Stm build(ExpList kids);}Each subclass Exp or Stm must implement the methods; for example,package Tree;public class BINOP extends Exp {public int binop;public Exp left, right;public BINOP(int b, Exp l, Exp r) {binop=b; ...}public final static int PLUS=0, MINUS=1, MUL=2, DIV=3,AND=4,OR=5,LSHIFT=6,RSHIFT=7,ARSHIFT=8,XOR=9;public ExpList kids() {return new ExpList(left,new ExpList(right,null));}public Exp build(ExpList kids) {return new BINOP(binop,kids.head,kids.tail.head);}}Other subclasses have similar (or even simpler) kids and build methods.

Using these buildmethods, we can write functionsstatic Tree.Stm do_stm(Tree.Stm s)static Tree.ESEQ do_exp (Tree.Exp e)that pull all the ESEQs out of a statement or expression, respectively. That is, do_stm usess.kids() to get the immediate subexpressions of s, which will be an expression-list l. It thenpulls all the ESEQs out of l recursively, yielding a clump of side-effecting statements s1 and acleaned-up list l′. Then SEQ(s1, s.build(l′)) constructs a new statement, like the original sbut with no ESEQs. These functions rely on auxiliary functions reorder_stm andreorder_exp for help; see also Exercise 8.3.The left-hand operand of the MOVE statement is not considered a subexpression, because it isthe destination of the statement - its value is not used by the statement.

However, if thedestination is a memory location, then the address acts like a source. Thus we have,public class MOVE extends Stm {public Exp dst, src;public MOVE(Exp d, Exp s) {dst=d; src=s;}public ExpList kids() {if (dst instanceof MEM)return new ExpList(((MEM)dst).exp,new ExpList(src,null));else return new ExpList(src,null);}public Stm build(ExpList kids) {if (dst instanceof MEM)return new MOVE(new MEM(kids.head), kids.tail.head);else return new MOVE(dst, kids.head);146}}Now, given a list of "kids", we pull the ESEQs out, from right to left.MOVING CALLS TO TOP LEVELThe Tree language permits CALL nodes to be used as subexpressions.

However, the actualimplementation of CALL will be that each function returns its result in the same dedicatedreturn-value register TEMP(RV). Thus, if we havethe second call will overwrite the RV register before the PLUS can be executed.We can solve this problem with a rewriting rule. The idea is to assign each return valueimmediately into a fresh temporary register, that isNow the ESEQ-eliminator will percolate the MOVE up outside of its containing BINOP (etc.)expressions.This technique will generate a few extra MOVE instructions, which the register allocator(Chapter 11) can clean up.The rewriting rule is implemented as follows: reorder replaces any occurrence of CALL(f,args) byand calls itself again on the ESEQ.

But do_stm recognizes the patternand does not call reorder on the CALL node in that case, but treats the f and args as thechildren of the MOVE node. Thus, reorder never "sees" any CALL that is already theimmediate child of a MOVE. Occurrences of the pattern EXP(CALL(f, args)) are treatedsimilarly.A LINEAR LIST OF STATEMENTSOnce an entire function body s0 is processed with do_stm, the result is a tree s0′ where all theSEQ nodes are near the top (never underneath any other kind of node). The linearizefunction repeatedly applies the ruleThe result is that s′0 is linearized into an expression of the form147Here the SEQ nodes provide no structuring information at all, and we can just consider this tobe a simple list of statements,where none of the si contain SEQ or ESEQ nodes.These rewrite rules are implemented by linearize, with an auxiliary function linear:static Tree.StmList linear(Tree.SEQ s, Tree.StmList l) {return linear(s.left,linear(s.right,l));}static Tree.StmList linear(Tree.Stm s, Tree.StmList l) {if (s instanceof Tree.SEQ) return linear((Tree.SEQ)s,l);else return new Tree.StmList(s,l);}static public Tree.StmList linearize(Tree.Stm s) {return linear(do_stm(s), null);}8.2 TAMING CONDITIONAL BRANCHESAnother aspect of the Tree language that has no direct equivalent in most machine instructionsets is the two-way branch of the CJUMP instruction.

The Tree language CJUMP is designedwith two target labels for convenience in translating into trees and analyzing trees. On a realmachine, the conditional jump either transfers control (on a true condition) or "falls through"to the next instruction.To make the trees easy to translate into machine instructions, we will rearrange them so thatevery CJUMP(cond, lt, lf) is immediately followed by LABEL(lf), its "false branch." Eachsuch CJUMP can be directly implemented on a real machine as a conditional branch to labell t.We will make this transformation in two stages: First, we take the list of canonical trees andform them into basic blocks; then we order the basic blocks into a trace.

The next sectionswill define these terms.BASIC BLOCKSIn determining where the jumps go in a program, we are analyzing the program's control flow.Control flow is the sequencing of instructions in a program, ignoring the data values inregisters and memory, and ignoring the arithmetic calculations. Of course, not knowing thedata values means we cannot know whether the conditional jumps will go to their true or falselabels; so we simply say that such jumps can go either way.In analyzing the control flow of a program, any instruction that is not a jump has an entirelyuninteresting behavior.

We can lump together any sequence of nonbranch instructions into abasic block and analyze the control flow between basic blocks.A basic block is a sequence of statements that is always entered at the beginning and exited atthe end, that is:••The first statement is a LABEL.The last statement is a JUMP or CJUMP.148•There are no other LABELs, JUMPs, or CJUMPs.The algorithm for dividing a long sequence of statements into basic blocks is quite simple.The sequence is scanned from beginning to end; whenever a LABEL is found, a new block isstarted (and the previous block is ended); whenever a JUMP or CJUMP is found, a block isended (and the next block is started).