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

As long as the loop-ending jump is an immediatejump, the hardware can take steps to minimize any disruption that it mightcause.The canonical loop shape from Figure 7.15 also sets the stage for later optimization. For example, if e1 and e2 contain only known constants, as in386 CHAPTER 7 Code Shapethe example, the compiler can fold the value from step 1 into the test instep 2 and either eliminate the compare and branch (if control enters theloop) or eliminate the loop body (if control never enters the loop).

In thesingle-test loop, the compiler cannot do this. Instead, the compiler finds twopaths leading to the test—one from step 1 and one from step 4. The valueused in the test, ri , has a varying value along the edge from step 4, so thetest’s outcome is not predictable.FORTRAN’s doLoopIn fortran, the iterative loop is a do loop.

It resembles the c for loop, buthas a more restricted form.j = 1do 10 i = 1, 100loop bodyj = j + 210continuenext statementloadIloadIloadIcmp GTcbr11100ri , r1r2⇒⇒⇒⇒→rj// j ← 1ri// Step 1r1// Step 2r2L2 , L1L1 : loop bodyaddIrj , 2addIri , 1cmp LE ri , r1cbrr3⇒⇒⇒→// Step 3rj// j ← j + 2ri// Step 4r3L1 , L2L2 : next statement// Step 5The comments map portions of the iloc code back to the schema inFigure 7.15.The definition of fortran, like that of many languages, has some interestingquirks. One such peculiarity relates to do loops and their index variables. Thenumber of iterations of a loop is fixed before execution enters the loop. Ifthe program changes the index variable’s value, that change does not affectthe number of iterations that execute. To ensure the correct behavior, thecompiler may need to generate a hidden induction variable, called a shadowindex variable, to control the iteration.While LoopsA while loop can also be implemented with the loop schema in Figure 7.15.Unlike the c for loop or the fortran do loop, a while loop has noinitialization.

Thus, the code is even more compact.while (x < y) {loop body}next statementcmp LT rx , ry ⇒ r1// Step 2cbrr1→ L1 , L2L1 : loop body// Step 3cmp LT rx , ry ⇒ r2// Step 4cbrr2→ L1 , L2L2 : next statement// Step 57.8 Control-Flow Constructs 387Replicating the test in step 4 creates the possibility of a loop with a singlebasic block. The same benefits that accrue to a for loop from this structurealso occur for a while loop.Until LoopsAn until loop iterates as long as the controlling expression is false. Itchecks the controlling expression after each iteration. Thus, it always entersthe loop and performs at least one iteration.

This produces a particularlysimple loop structure, since it avoids steps 1 and 2 in the schema:{loop body} until (x < y)next statementL1 : loop body// Step 3cmp LT rx , ry ⇒ r2// Step 4cbrr2→ L2 , L1L2 : next statement// Step 5C does not have an until loop. Its do construct is similar to an until loop,except that the sense of the condition is reversed. It iterates as long as thecondition evaluates to true, where the until iterates as long as the conditionis false.Expressing Iteration as Tail RecursionIn Lisp-like languages, iteration is often implemented (by programmers)using a stylized form of recursion.

If the last action executed by a functionis a call, that call is known as a tail call. For example, to find the last element of a list in Scheme, the programmer might write the following simplefunction:(define (last alon)(cond((empty? alon) empty)((empty? (cdr alon)) (car alon))(else (last (cdr alon)))))Compilers often subject tail calls to special treatment, because the compiler can generate particularly efficient call for them (see Section 10.4.1).Tail recursion can be used to achieve the same effects as iteration, as in thefollowing Scheme code:(define (count alon ct)(cond((empty? alon) ct)(else (count (cdr alon) (+ ct 1)))))(define (len alon)(count alon 0))Tail callA procedure call that occurs as the last actionin some procedure is termed a tail call.

Aself-recursive tail call is termed a tail recursion.388 CHAPTER 7 Code ShapeInvoking len on a list returns the list’s length. len relies on count, whichimplements a simple counter using tail calls.Break StatementsSeveral languages implement variations on a break or exit statement.

Thebreak statement is a structured way to exit a control-flow construct. In aloop, break transfers control to the first statement following the loop. Fornested loops, a break typically exits the innermost loop. Some languages,such as Ada and Java, allow an optional label on a break statement. Thiscauses the break statement to exit from the enclosing construct specifiedby that label.

In a nested loop, a labelled break allows the program to exitseveral loops at once. c also uses break in its switch statement, to transfercontrol to the statement that follows the switch statement.These actions have simple implementations. Each loop and each case statement should end with a label for the statement that follows it. A break wouldbe implemented as an immediate jump to that label. Some languages includea skip or continue statement that jumps to the next iteration of a loop. Thisconstruct can be implemented as an immediate jump to the code that reevaluates the controlling expression and tests its value.

Alternatively, the compilercan simply insert a copy of the evaluation, test, and branch at the point wherethe skip occurs.7.8.3 Case StatementsMany programming languages include some variant of a case statement.fortran has its computed goto. Algol-W introduced the case statementin its modern form. bcpl and c have a switch construct, while pl/i has ageneralized construct that maps well onto a nested set of if-then-elsestatements.

As the introduction to this chapter hinted, implementing a casestatement efficiently is complex.Consider the implementation of c’s switch statement. The basic strategyis straightforward: (1) evaluate the controlling expression; (2) branch to theselected case; and (3) execute the code for that case. Steps 1 and 3 are wellunderstood, as they follow from discussions elsewhere in this chapter. In c,the individual cases usually end with a break statement that exits the switchstatement.The complex part of case-statement implementation lies in choosing anefficient method to locate the designated case.

Because the desired case isnot known until runtime, the compiler must emit code that will use the valueof the controlling expression to locate the corresponding case. No single7.8 Control-Flow Constructs 389switch (e1 )case 0:{block0 ;break;case 1:block1 ;t1 ← e1if (t1 = 0)then block0else if (t1 = 1)then block1break;case 3:else if (t1 = 2)then block2block3 ;break;else if (t1 = 3)then block3default: blockd ;break;else blockd}(a) Switch Statement(b) Implemented as a Linear Searchn FIGURE 7.16 Case Statement Implemented with Linear Search.method works well for all case statements.

Many compilers have provisionfor several different search schemes and choose between them based on thespecific details of the set of cases.This section examines three strategies: a linear search, a binary search, anda computed address. Each strategy is appropriate under different circumstances.Linear SearchThe simplest way to locate the appropriate case is to treat the case statement as the specification for a nested set of if-then-else statements.

Forexample, the switch statement shown in Figure 7.16a can be translated intothe nest of statements shown in Figure 7.16b. This translation preserves themeaning of the switch statement, but makes the cost of reaching individual cases dependent on the order in which they are written. With a linearsearch strategy, the compiler should attempt to order the cases by estimatedexecution frequency. Still, when the number of cases is small—say three orfour—this strategy can be efficient.Directly Computing the AddressIf the case labels form a compact set, the compiler can do better than binarysearch. Consider the switch statement shown in Figure 7.17a. It has caselabels from zero to nine, plus a default case.

For this code, the compiler canbuild a compact vector, or jump table, that contains the block labels, andfind the appropriate label by index into the table. The jump table is shownJump tablea vector of labels used to transfer control basedon a computed index into the table390 CHAPTER 7 Code Shapeswitch (e1 ){case 0:block0case 1:case 2:···case 9:Labelbreak;LB0block1LB1t1 ← e1break;LB2block2break;LB3if (0 > t1 or t1 > 9)then jump to LBdelseLB4LB5block9break;default: blockdbreak;LB6LB7LB8t2 ←@Table + t1 x 4t3 ← memory(t2 )jump to t3LB9}(a) Switch Statement(b) Jump Table(c) Code for Address Computationn FIGURE 7.17 Case Statement Implemented with Direct Address Computation.in Figure 7.17b, while the code to compute the correct case’s label is shownin Figure 7.17c.

The search code assumes that the jump table is stored at@Table and that each label occupies four bytes.For a dense label set, this scheme generates compact and efficient code. Thecost is small and constant—a brief calculation, a memory reference, and ajump. If a few holes exist in the label set, the compiler can fill those slotswith the label for the default case. If no default case exists, the appropriateaction depends on the language. In c, for example, the code should branchto the first statement after the switch, so the compiler can place that labelin each hole in the table. If the language treats a missing case as an error,as pl/i did, the compiler can fill holes in the jump table with the label of ablock that throws the appropriate runtime error.Binary SearchAs the number of cases rises, the efficiency of linear search becomes aproblem.

In a similar way, as the label set becomes less dense and lesscompact, the size of the jump table can become a problem for the directaddress computation. The classic solutions that arise in building an efficientsearch apply in this situation. If the compiler can impose an order on the caselabels, it can use binary search to obtain a logarithmic search rather than alinear one.The idea is simple. The compiler builds a compact ordered table of caselabels, along with their corresponding branch labels. It uses binary search to7.8 Control-Flow Constructs 391switch (e1 ){case 0:block0break;case 15: block15break;case 23: block23break;...case 99: block99break;default: blockdbreak;t1 ← e1Value0152337415068728399LabelLB0LB15LB23down ← 0// lower boundup ← 10// upper bound + 1while (down + 1 < up)LB37LB41then down ← middleelse up ← middleLB50LB68LB72}LB83if (Value [down] = t1then jump to Label[down]LB99}(a) Switch Statement{middle ← (up + down) ÷ 2if (Value [middle] ≤ t1 )(b) Search Tableelse jump to LBd(c) Code for Binary Searchn FIGURE 7.18 Case Statement Implemented with Binary Search.discover a matching case label, or the absence of a match.