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

The former assigns specificvalues to true and false and manipulates them using the target machine’sarithmetic and logical operations. The latter approach encodes the value ofthe expression as a position in the executable code. It uses comparisons andconditional branches to evaluate the expression; the different control-flowpaths represent the result of evaluation. Each approach works well for someexamples, but not for others.Numerical EncodingWhen the program stores the result of a boolean or relational operation intoa variable, the compiler must ensure that the value has a concrete representation.

The compiler writer must assign numerical values to true and false thatwork with the hardware operations such as and, or, and not. Typical valuesare zero for false and either one or a word of ones, ¬false, for true.For example, if b, c, and d are all in registers, the compiler might producethe following code for the expression b ∨ c ∧ ¬ d:not rd⇒ r1and rc , r1 ⇒ r2or rb , r2 ⇒ r3For a comparison, such as a < b, the compiler must generate code thatcompares a and b and assigns the appropriate value to the result. If thetarget machine supports a comparison operation that returns a boolean, thecode is trivial:cmp LT ra , rb ⇒ r1352 CHAPTER 7 Code ShapeILOC contains syntax to implement both styles ofcompare and branch. A normal IR would chooseone; ILOC includes both so that it can express thecode in this section.If, on the other hand, the comparison defines a condition code that mustbe read with a branch, the resulting code is longer and more involved.

Thisstyle of comparison leads to a messier implementation for a < b.compcbr LTL1 : loadIjumpIL2 : loadIjumpIL3 : nopra , rb ⇒ cc1cc1→ L1 , L2true ⇒ r1→ L3false ⇒ r1→ L3Implementing a < b with condition-code operations requires more operationsthan using a comparison that returns a boolean.Positional EncodingIn the previous example, the code at L1 creates the value true and the codeat L2 creates the value false. At each of those points, the value is known.

Insome cases, the code need not produce a concrete value for the expression’sresult. Instead, the compiler can encode that value in a location in the code,such as L1 or L2 .Figure 7.8a shows the code that a treewalk code generator might emit forthe expression a < b ∨ c < d ∧ e < f. The code evaluates the three subexpressions, a < b, c < d, and e < f, using a series of comparisons and jumps.

Itthen combines the result of the three subexpression evaluations using theboolean operations at L9 . Unfortunately, this produces a sequence of operations in which every path takes 11 operations, including three branches andthree jumps. Some of the complexity of this code can be eliminated by representing the subexpression values implicitly and generating code that shortcircuits the evaluation, as in Figure 7.8b. This version of the code evaluatesa < b ∨ c < d ∧ e < f with fewer operations because it does not create valuesto represent the subexpressions.Positional encoding makes sense if an expression’s result is never stored.When the code uses the result of an expression to determine control flow,positional encoding often avoids extraneous operations.

For example, in thecode fragmentif (a < b)then statement1else statement2the sole use for a < b is to determine whether statement1 or statement2executes. Producing an explicit value for a < b serves no direct purpose.7.4 Boolean and Relational Operators 353compra , rbcbr LT cc1L1 : loadI truejumpI → L3L2 : loadI falsejumpI → L3⇒ cc1// a < b→ L1 , L2⇒ r1L3 : comprc , rdcbr LT cc2L4 : loadI truejumpI → L6L5 : loadI falsejumpI → L6⇒ cc2// c < d→ L4 , L5⇒ r2L6 : compcbr LTL7 : loadIjumpIL8 : loadIjumpIre , rfcc3true⇒→⇒→⇒→L9 : andorr2 , r3r1 , r4false⇒ r1⇒ r2cc3L7 , L8r3L9r3L9// e < fcompra , rbcbr LT cc1⇒ cc1// a < b→ L3 , L1L1 : comprc , rdcbr LT cc2⇒ cc2// c < d→ L2 , L4L2 : compre , rfcbr LT cc3⇒ cc3// e < f→ L3 , L4L3 : loadIjumpItrue⇒ r5→ L5L4 : loadIjumpIfalse⇒ r5→ L5L5 : nop⇒ r4⇒ r5(a) Naive Encoding(b) Positional Encoding withShort-Circuit Evaluationn FIGURE 7.8 Encoding a < b ∨ c < d ∧ e < f.On a machine where the compiler must use a comparison and a branch toproduce a value, the compiler can simply place the code for statement1 andstatement2 in the locations where naive code would assign true and false.This use of positional encoding leads to simpler, faster code than usingnumerical encoding.compcbr LTra , rbcc1⇒ cc1// a < b→ L1 , L2L1 : code for statement1jumpI→ L6L2 : code for statement2jumpI→ L6L6 : nopHere, the code to evaluate a < b has been combined with the code to selectbetween statement1 and statement2 .

The code represents the result of a < bas a position, either L1 or L2 .7.4.2 Hardware Support for Relational OperationsSpecific, low-level details in the target machine’s instruction set stronglyinfluence the choice of a representation for relational values. In particular,354 CHAPTER 7 Code ShapeSHORT-CIRCUIT EVALUATIONIn many cases, the value of a subexpression determines the value of theentire expression.

For example, the code shown in Figure 7.8a, evaluatesc < d ∧ e <f, even if it has already determined that a < b, in which case theentire expression evaluates to true. Similarly, if both a ≥ b and c ≥ d,then the value of e < f does not matter. The code in Figure 7.8b usesthese relationships to produce a result as soon as the expression’s valuecan be known. This approach to expression evaluation, in which the codeevaluates the minimal amount of the expression needed to determine itsfinal value, is called short-circuit evaluation.

Short-circuit evaluation relieson two boolean identities:∀ x, false ∧ x = false∀ x, true ∨ x = trueTo generate the short-circuit code, the compiler must analyze the expression in light of these two identities and find the set of minimal conditionsthat determine its value. If clauses in the expression contain expensiveoperators or if the evaluation uses branches, as do many of the schemesdiscussed in this section, then short-circuit evaluation can significantlyreduce the cost of evaluating boolean expressions.Some programming languages, like C, require the compiler to use shortcircuit evaluation.

For example, the expression(x != 0 && y / x > 0.001)in C relies on short-circuit evaluation for safety. If x is zero, y / x is notdefined. Clearly, the programmer intends to avoid the hardware exceptiontriggered by division by zero. The language definition specifies that thiscode will never perform the division if x has the value zero.the compiler writer must pay attention to the handling of condition codes,compare operations, and conditional move operations, as they have a majorimpact on the relative costs of the various representations.

We will considerfour schemes for supporting relational expressions: straight condition codes,condition codes augmented with a conditional move operation, booleanvalued comparisons, and predicated operations. Each scheme is an idealizedversion of a real implementation.Figure 7.9 shows two source-level constructs and their implementationsunder each of these schemes. Figure 7.9a shows an if-then-else that controls a pair of assignment statements.

Figure 7.9b shows the assignment of aboolean value.7.4 Boolean and Relational Operators 355SourceCodeif (x < y)then a ← c + delse a ← e + fcomprx , ry ⇒ cc1cbr LT cc1→ L1 , L2ILOCCodecmp LT rx , ry ⇒ r1cbrr1→ L1 , L2L1 : addrc , rd ⇒ rajumpI→ LoutL1 : addrc , rd ⇒ rajumpI→ LoutL2 : addre , rf ⇒ rajumpI→ LoutL2 : addre , rf ⇒ rajumpI→ LoutLout : nopLout : nopStraight Condition Codescompaddaddi2i LTrx , ryrc , rdre , rfcc1 , r1 , r2⇒⇒⇒⇒cc1r1r2raConditional MoveBoolean Comparecmp LT rx , rynotr1(r1 )? addrc , rd(r2 )? addre , rf⇒⇒⇒⇒r1r2raraPredicated Execution(a) Using a Relational Expression to Govern Control FlowSourceCodeILOCCodex ← a < b ∧ c < dcompcbr LTL1 : compcbr LTL2 : loadIjumpIra , rbcc1rc , rdcc2falseL3 : loadI truejumpI⇒→⇒→⇒→⇒→cc1L1 ,L2cc2L3 ,L2rxLoutrxLoutLout : nopStraight Condition Codescompi2i LTcompi2i LTandra ,rbcc1 ,rT ,rFrc ,rdcc2 ,rT ,rFr1 ,r2⇒⇒⇒⇒⇒cc1r1cc2r2rxConditional Movecmp LT ra , rbcmp LT rc , rdandr1 , r2⇒ r1⇒ r2⇒ rxBoolean Comparecmp LT ra , rbcmp LT rc , rdandr1 , r2⇒ r1⇒ r2⇒ rxPredicated Execution(b) Using a Relational Expression to Produce a Valuen FIGURE 7.9 Implementing Boolean and Relational Operators.Straight Condition CodesIn this scheme, the comparison operation sets a condition-code register.

Theonly instruction that interprets the condition code is a conditional branch,with variants that branch on each of the six relations (<, ≤, =, ≥, >, and 6=).These instructions may exist for operands of several types.356 CHAPTER 7 Code ShapeSHORT-CIRCUIT EVALUATION AS AN OPTIMIZATIONShort-circuit evaluation arose from a positional encoding of the valuesof boolean and relational expressions. On processors that use conditioncodes to record the result of a comparison and use conditional branchesto interpret the condition code, short circuiting makes sense.As processors include features like conditional move, boolean-valuedcomparisons, and predicated execution, the advantages of short-circuitevaluation will likely fade.

With branch latencies growing, the cost of theconditional branches required for short circuiting grows too. When thebranch costs exceed the savings from avoiding evaluation, short circuitingwill no longer be an improvement. Instead, full evaluation will be faster.When the language requires short-circuit evaluation, as does C, the compiler may need to perform some analysis to determine when it is safe tosubstitute full evaluation for short-circuit evaluation. Thus, future C compilers may include analysis and transformation to replace short circuitingwith full evaluation, just as compilers in the past have performed analysisand transformation to replace full evaluation with short-circuit evaluation.The compiler must use conditional branches to interpret the value of a condition code.