K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 89
Текст из файла (страница 89)
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.
If the sole use of the result is to determine control flow, as inFigure 7.9a, then the conditional branch that the compiler uses to read the condition code can often implement the source-level control-flow construct, aswell. If the result is used in a boolean operation, or it is preserved in a variable,as in Figure 7.9b, the code must convert the result into a concrete representation of a boolean, as do the two loadI operations in Figure 7.9b.
Either way,the code has at least one conditional branch per relational operator.The advantage of condition codes comes from another feature that processors usually implement alongside condition codes. Typically, arithmeticoperations on these processors set the condition code to reflect their computed results. If the compiler can arrange to have the arithmetic operationsthat must be performed also set the condition code needed to control thebranch, then the comparison operation can be omitted. Thus, advocates ofthis architectural style argue that it allows a more efficient encoding of theprogram—the code may execute fewer instructions than it would with acomparator that puts a boolean value in a general-purpose register.Conditional MoveThis scheme adds a conditional move instruction to the straight conditioncode model.
In iloc, a conditional move looks like:i2i LT cci , rj , rk ⇒ rm7.4 Boolean and Relational Operators 357If the condition code cci matches LT, then the value of rj is copied to rm .Otherwise, the value of rk is copied to rm . The conditional move operationtypically executes in a single cycle. It leads to faster code by allowing thecompiler to avoid branches.Conditional move retains the principal advantage of using condition codes—avoiding a comparison when an earlier operation has already set the condition code.
As shown in Figure 7.9a, it lets the compiler encode simpleconditional operations with branches. Here, the compiler speculatively evaluates the two additions. It uses conditional move for the final assignment.This is safe as long as neither addition can raise an exception.If the compiler has values for true and false in registers, say rT for trueand rF for false, then it can use conditional move to convert the conditioncode into a boolean.
Figure 7.9b uses this strategy. It compares a and b andplaces the boolean result in r1 . It computes the boolean for c < d into r2 . Itcomputes the final result as the logical and of r1 and r2 .Boolean-Valued ComparisonsThis scheme avoids condition codes entirely. The comparison operatorreturns a boolean value in a register. The conditional branch takes that resultas an argument that determines its behavior.Boolean-valued comparisons do not help with the code in Figure 7.9a.The code is equivalent to the straight condition-code scheme. It requirescomparisons, branches, and jumps to evaluate the if-then-else construct.Figure 7.9b shows the strength of this scheme. The boolean compare letsthe code evaluate the relational operator without a branch and without converting comparison results to boolean values.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
