Cooper_Engineering_a_Compiler(Second Edition) (Rice), страница 86

If a is stored in memory at offset @a in the current ar, the resulting codemight beloadI @a⇒ r1loadAO rarp , r1 ⇒ ra7.3 Arithmetic Operators 343If, however, the value of a is already in a register, the compiler can simply use that register in place of ra . The compiler follows a similar chainof decisions for b. Finally, it emits an instruction to perform the addition,such asadd ra , rb ⇒ rtIf the expression is represented in a tree-like ir, this process fits into a postorder tree walk. Figure 7.5a shows the code for a tree walk that generatescode for simple expressions.

It relies on two routines, base and offset, tohide some of the complexity. The base routine returns the name of a registerholding the base address for an identifier; if needed, it emits code to get thataddress into a register. The offset routine has a similar function; it returnsthe name of a register holding the identifier’s offset relative to the addressreturned by base.expr(node) {int result, t1, t2;switch(type(node)) {case ×, ÷, +, -:t1 ← expr(LeftChild(node));t2 ← expr(RightChild(node));result ← NextRegister( );- Z=~Za× Z=~Zbcemit(op(node), t1, t2, result);break;(b) Abstract Syntax Tree fora - bx ccase IDENT:t1 ← base(node);t2 ← offset(node);result ← NextRegister( );emit( loadAO, t1, t2, result);break;case NUM:result ← NextRegister( );emit(loadI, val(node), none,result);break;}return result;}(a) Treewalk Code Generatorn FIGURE 7.5 Simple Treewalk Code Generator for Expressions.loadIloadAOloadIloadAOloadIloadAOmultsub@ararp , r1@brarp , r3@crarp , r5r4 , r6r2 , r7⇒⇒⇒⇒⇒⇒⇒⇒(c) Naive Coder1r2r3r4r5r6r7r8344 CHAPTER 7 Code ShapeThe same code handles +, -, ×, and ÷.

From a code-generation perspective,these operators are interchangeable, ignoring commutativity. Invoking theroutine expr from Figure 7.5a on the ast for a - b x c shown in part b ofthe figure produces the results shown in part c of the figure. The exampleassumes that a, b, and c are not already in registers and that each resides inthe current ar.Notice the similarity between the treewalk code generator and the ad hocsyntax-directed translation scheme shown in Figure 4.15. The treewalkmakes more details explicit, including the handling of terminals and theevaluation order for subtrees. In the syntax-directed translation scheme, theorder of evaluation is controlled by the parser.

Still, the two schemes produceroughly equivalent code.7.3.1 Reducing Demand for RegistersMany issues affect the quality of the generated code. For example, the choiceof storage locations has a direct impact, even for this simple expression.

Ifa were in a global data area, the sequence of instructions needed to get ainto a register might require an additional loadI to obtain the base addressand a register to hold that value for a brief time. Alternatively, if a werein a register, the two instructions used to load it into r2 could be omitted,and the compiler would use the name of the register holding a directly inthe sub instruction. Keeping the value in a register avoids both the memoryaccess and any address calculation. If a, b, and c were already in registers, the seven-instruction sequence could be shortened to a two-instructionsequence.Code-shape decisions encoded into the treewalk code generator have aneffect on demand for registers.

The naive code in the figure uses eight registers, plus rarp . It is tempting to assume that the register allocator, whenit runs late in compilation, can reduce the number of registers to a minimum. For example, the register allocator could rewrite the code as shown inFigure 7.6a, which drops register use from eight registers to three, plus rarp .The maximum demand for registers occurs in the sequence that loads c andperforms the multiply.A different code shape can reduce the demand for registers. The treewalkcode generator loads a before it computes b x c, an artifact of the decision touse a left-to-right tree walk.

Using a right-to-left tree walk would producethe code shown in Figure 7.6b. While the initial code uses the same numberof registers as the code generated left-to-right, register allocation reveals thatthe code actually needs one fewer registers, as shown in Figure 7.6c.7.3 Arithmetic Operators 345loadIloadAOloadIloadAOloadIloadAOmultsub@ararp , r1@brarp , r2@crarp , r3r2 , r3r1 , r2⇒⇒⇒⇒⇒⇒⇒⇒r1r1r2r2r3r3r2r2(a) Example After AllocationloadIloadAOloadIloadAOmultloadIloadAOsub@crarp , r1@brarp , r3r2 , r4@ararp , r6r7 , r5⇒⇒⇒⇒⇒⇒⇒⇒r1r2r3r4r5r6r7r8(b) Evaluating b x c FirstloadIloadAOloadIloadAOmultloadIloadAOsub@crarp , r1@brarp , r2r1 , r2@ararp , r2r2 , r1⇒⇒⇒⇒⇒⇒⇒⇒r1r1r2r2r1r2r2r1(c) After Register Allocationn FIGURE 7.6 Rewriting a - b x c to Reduce Demand for Registers.Of course, right-to-left evaluation is not a general solution.

For the expression a x b + c, left-to-right evaluation produces the lower demand for registers. Some expressions, such as a + (b + c) x d, defy a simple static rule. Theevaluation order that minimizes register demand is a + ( (b + c) x d).To choose an evaluation order that reduces demand for registers, the codegenerator must alternate between right and left children; it needs informationabout the detailed register needs of each subtree.

As a rule, the compiler canminimize register use by evaluating first, at each node, the subtree that needsthe most registers. The generated code must preserve the value of the firstsubtree that it evaluates across the evaluation of the second subtree; thus,handling the less demanding subtree first increases the demand for registersin the more demanding subtree by one register. This approach requires aninitial pass over the code to compute demand for registers, followed by apass that emits the actual code.7.3.2 Accessing Parameter ValuesThe code generator in Figure 7.5 implicitly assumes that a single accessmethod works for all identifiers. Formal parameters may need different treatment.

A call-by-value parameter passed in the ar can be handled as if it werea local variable. A call-by-reference parameter passed in the ar requiresone additional indirection. Thus, for the call-by-reference parameter d, thecompiler might generateloadI @d⇒ r1loadAO rarp , r1 ⇒ r2loadr2⇒ r3to obtain d’s value.

The first two operations move the address of theparameter’s value into r2 . The final operation moves the value itself into r3 .This approach, analysis followed bytransformation, applies in both code generationand optimization [150].346 CHAPTER 7 Code ShapeGENERATING LOAD ADDRESS IMMEDIATEA careful reader might notice that the code in Figure 7.5 never generatesILOC’s load address-immediate instruction, loadAI. Instead, it generates aload immediate (loadI), followed by a load address-offset (loadAO):loadI @a⇒ r1loadAO rarp , r1 ⇒ r2instead ofloadAI rarp , @a ⇒ r2Throughout the book, the examples assume that it is preferable to generate this two-operation sequence, rather than the single operation. Threefactors suggest this course.1.

The longer code sequence gives an explicit name to @a. If @a is reusedin other contexts, that name can be reused.2. The offset @a may not fit in the immediate field of a loadAI. Thatdetermination is best made in the instruction selector.3. The two-operation sequence leads to a clean functionaldecomposition in the code generator, shown Figure 7.5.The compiler can convert the two-operation sequence into a single operation during optimization, if appropriate (e.g. either @a is not reused orit is cheaper to reload it). The best course, however, may be to defer theissue to instruction selection, thus isolating the machine-dependent constant length into a part of the compiler that is already highly machinedependent.If the compiler writer wants to generate the loadAI earlier, two simpleapproaches work.

The compiler writer can refactor the treewalk code generator in Figure 7.5 and pull the logic hidden in base and offset into thecase for IDENT. Alternatively, the compiler writer can have emit maintaina small instruction buffer, recognize this special case, and emit the loadAI.Using a small buffer makes this approach practical (see Section 11.5).Many linkage conventions pass the first few parameters in registers. Aswritten, the code in Figure 7.5 cannot handle a value that is permanently keptin a register. The necessary extensions, however, are easy to implement.nnCall-by-value parameters The IDENT case must check if the value isalready in a register.