K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 97
Текст из файла (страница 97)
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.
Finally, it eitherbranches to the corresponding label or to the default case.Figure 7.18a shows our example case statement, rewritten with a differentset of labels. For the figure, we will assume case labels of 0, 15, 23, 37, 41,50, 68, 72, 83, and 99, as well as a default case. The labels could, of course,cover a much larger range. For such a case statement, the compiler mightbuild a search table such as the one shown in Figure 7.18b, and generate abinary search, as in Figure 7.18c, to locate the desired case. If fall-throughbehavior is allowed, as in c, the compiler must ensure that the blocks appearin memory in their original order.In a binary search or direct address computation, the compiler writer shouldensure that the set of potential targets of the jump are visible in the ir, usinga construct such as the iloc tbl pseudo-operation (see Appendix A.4.2).Such hints both simplify later analysis and make its results more precise.SECTION REVIEWProgramming languages include a variety of features to implementcontrol flow.
The compiler needs a schema for each control-flowconstruct in the source languages that it accepts. In some cases, such as aloop, one approach serves for a variety of different constructs. In others,such as a case statement, the compiler should choose an implementationstrategy based on the specific properties of the code at hand.The exact form of the search loop might vary.For example, the code in the figure does notshort circuit the case when it finds the label early.Empirical testing of several variants written inthe target machine’s assembly code is needed tofind the best choices.392 CHAPTER 7 Code ShapeReview Questionsdo 10 i = 1, 100loop body10i = i + 2continue1. Write the ILOC code for the FORTRAN loop shown in the margin.
Recallthat the loop body must execute 100 iterations, even though the loopmodifies the value of i.2. Consider the tradeoff between implementing a C switch statementwith a direct address computation and with a binary search. At whatpoint should the compiler switch from direct address computation toa binary search? What properties of the actual code should play a rolein that determination?7.9 PROCEDURE CALLSThe implementation of procedure calls is, for the most part, straightforward.As shown in Figure 7.19, a procedure call consists of a precall sequenceand a postreturn sequence in the caller, and a prologue and an epiloguein the callee.
A single procedure can contain multiple call sites, each withits own precall and postreturn sequences. In most languages, a procedurehas one entry point, so it has one prologue sequence and one epiloguesequence. (Some languages allow multiple entry points, each of which hasits own prologue sequence.) Many of the details involved in these sequencesare described in Section 6.5.
This section focuses on issues that affect thecompiler’s ability to generate efficient, compact, and consistent code forprocedure calls.Procedure pPrologueProcedure qPrecallllCaPostreturnReEpiloguen FIGURE 7.19 A Standard Procedure Linkage.turnPrologueEpilogue7.9 Procedure Calls 393As a general rule, moving operations from the precall and postreturnsequences into the prologue and epilogue sequences should reduce theoverall size of the final code. If the call from p to q shown in Figure 7.19 isthe only call to q in the entire program, then moving an operation from theprecall sequence in p to the prologue in q (or from the postreturn sequencein p to the epilogue in q) has no impact on code size.
If, however, other callsites invoke q and the compiler moves an operation from the caller to thecallee (at all the call sites), it should reduce the overall code size by replacing multiple copies of an operation with a single one. As the number of callsites that invoke a given procedure rises, the savings grow.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
