K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 87
Текст из файла (страница 87)
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. If so, it just assigns the register number to result.Otherwise, it uses the standard mechanisms to load the value frommemory.Call-by-reference parameter If the address resides in a register, thecompiler simply loads the value into a register. If the address resides inthe ar, it must load the address before it loads the value.7.3 Arithmetic Operators 347COMMUTATIVITY, ASSOCIATIVITY, AND NUMBER SYSTEMSThe compiler can often take advantage of algebraic properties of the operators.
Addition and multiplication are commutative and associative, as arethe boolean operators. Thus, if the compiler sees a code fragment thatcomputes a + b and then computes b + a, with no intervening assignmentsto either a or b, it should recognize that they compute the same value. Similarly, if it sees the expressions a + b + c and d + a + b, it should recognize thata + b is a common subexpression. If it evaluates both expressions in strictleft-to-right order, it will never recognize the common subexpression, sinceit will compute the second expression as d + a and then (d + a) + b.The compiler should use commutativity and associativity to improve thequality of code that it generates.
Reordering expressions can expose additional opportunities for many transformations.Due to limitations in precision, floating-point numbers on a computer represent only a subset of the real numbers, one that does not preserve associativity.For this reason, compilers should not reorder floating-point expressions unlessthe language definition specifically allows it.Consider the following example: computing a - b - c.
We can assignfloating-point values to a, b, and c such thatb, c < aa-b=aa-c=abut a - (b + c) 6= a. In that case, the numerical result depends on the orderof evaluation. Evaluating (a - b) - c produces a result identical to a, whileevaluating b + c first and subtracting that quantity from a produces a resultthat is distinct from a.This problem arises from the approximate nature of floating-point numbers; the mantissa is small relative to the range of the exponent. To addtwo numbers, the hardware must normalize them; if the difference in exponents is larger than the precision of the mantissa, the smaller number willbe truncated to zero.
The compiler cannot easily work its way around thisissue, so it should, in general, avoid reordering float-point computations.In either case, the code fits nicely into the treewalk framework. Note that thecompiler cannot keep the value of a call-by-reference parameter in a registeracross an assignment, unless the compiler can prove that the reference isunambiguous, across all calls to the procedure.7.3.3 Function Calls in an ExpressionSo far, we have assumed that all the operands in an expression are variables,constants, and temporary values produced by other subexpressions.
FunctionIf the actual parameter is a local variable of thecaller and its address is never taken, thecorresponding formal is unambiguous.348 CHAPTER 7 Code Shapecalls also occur as operands in expressions. To evaluate a function call, thecompiler simply generates the calling sequence needed to invoke the function and emits the code necessary to move the returned value to a register (seeSection 7.9). The linkage convention limits the callee’s impact on the caller.The presence of a function call may restrict the compiler’s ability to changean expression’s evaluation order.
The function may have side effects thatmodify the values of variables used in the expression. The compiler mustrespect the implied evaluation order of the source expression, at least withrespect to the call. Without knowledge about the possible side effects ofa call, the compiler cannot move references across the call. The compilermust assume the worst case—that the function both modifies and uses everyvariable that it can access. The desire to improve on worst-case assumptions,such as this one, has motivated much of the work in interprocedural analysis(see Section 9.4).7.3.4 Other Arithmetic OperatorsTo handle other arithmetic operations, we can extend the treewalk model.The basic scheme remains the same: get the operands into registers, performthe operation, and store the result.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
