K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 96
Текст из файла (страница 96)
This bias may take the form of predicting abranch, of executing some instructions speculatively, orof reordering the logic.384 CHAPTER 7 Code Shape2. Uneven amounts of code If one path through the construct containsmany more instructions than the other, this may weigh againstpredication or for a combination of predication and branching.3. Control flow inside the construct If either path contains nontrivialcontrol flow, such as an if-then-else, loop, case statement,or call, then predication may be a poor choice. In particular, nested ifconstructs create complex predicates and lower the fraction of issuedoperations that are useful.To make the best decision, the compiler must consider all these factors, aswell as the surrounding context.
These factors may be difficult to assess earlyin compilation; for example, optimization may change them in significantways.7.8.2 Loops and IterationMost programming languages include loop constructs to perform iteration.The first fortran compiler introduced the do loop to perform iteration.Today, loops are found in many forms. For the most part, they have a similarstructure.Consider the c for loop as an example.
Figure 7.15 shows how the compiler might lay out the code. The for loop has three controlling expressions:e1 , which provides for initialization; e2 , which evaluates to a boolean andgoverns execution of the loop; and e3 , which executes at the end of each iteration and, potentially, updates the values used in e2 . We will use this figureas the basic schema to explain the implementation of several kinds of loops.For (e1 ; e2 ; e3 ) {loop body}StepPurpose11Evaluate e122If (¬e2 )Then goto 533Loop Body44Evaluate e3If (e2 )Then goto 35Code After Loop5(a) Example Code for Loop(b) Schema for Implementing Loopn FIGURE 7.15 General Schema for Layout of a for Loop.7.8 Control-Flow Constructs 385If the loop body consists of a single basic block—that is, it contains noother control flow—then the loop that results from this schema has an initialbranch plus one branch per iteration.
The compiler might hide the latencyof this branch in one of two ways. If the architecture allows the compiler topredict whether or not the branch is taken, the compiler should predict thebranch in step 4 as being taken (to start the next iteration). If the architectureallows the compiler to move instructions into the delay slot(s) of the branch,the compiler should attempt to fill the delay slot(s) with instruction(s) fromthe loop body.For LoopsTo map a for loop into code, the compiler follows the general schema fromFigure 7.15.
To make this concrete, consider the following example. Steps 1and 2 produce a single basic block, as shown in the following code:for (i=1; i<=100; i++) {loop body}next statementloadI 1loadI 100cmp GT ri , r1cbrr2L1 : loop bodyaddIri , 1cmp LE ri , r1cbrr3L2 : next statement⇒⇒⇒→rir1r2L2 , L1// Step 1// Step 2// Step 3⇒ ri// Step 4⇒ r3→ L1 , L2// Step 5The code produced in steps 1, 2, and 4 is straightforward. If the loop body(step 3) either consists of a single basic block or it ends with a single basicblock, then the compiler can optimize the update and test produced in step 4with the loop body. This may lead to improvements in the code—for example, the instruction scheduler might use operations from the end of step 3 tofill delay slots in the branch from step 4.The compiler can also shape the loop so that it has only one copy of the test—the one in step 2.
In this form, step 4 evaluates e3 and then jumps to step 2.The compiler would replace cmp LE, cbr sequence at the end of the loopwith a jumpI. This form of the loop is one operation smaller than the twotest form. However, it creates a two-block loop for even the simplest loops,and it lengthens the path through the loop by at least one operation. Whencode size is a serious consideration, consistent use of this more compact loopform might be worthwhile. 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
