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

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.

We assume thatmost procedures are called from several locations; if not, both the programmer and the compiler should consider including the procedure inline at thepoint of its only invocation.From the code-shape perspective, procedure calls are similar in Algol-likelanguages and object-oriented languages. The major difference betweenthem lies in the technique used to name the callee (see Section 6.3.4). Inaddition, a call in an object-oriented language typically adds an implicitactual parameter, that is, the receiver’s object record.7.9.1 Evaluating Actual ParametersWhen it builds the precall sequence, the compiler must emit code to evaluatethe actual parameters to the call.

The compiler treats each actual parameteras an expression. For a call-by-value parameter, the precall sequence evaluates the expression and stores its value in a location designated for thatparameter—either in a register or in the callee’s ar. For a call-by-referenceparameter, the precall sequence evaluates the parameter to an address andstores the address in a location designated for that parameter. If a call-byreference parameter has no storage location, then the compiler may need toallocate space to hold the parameter’s value so that it has an address to passto the callee.If the source language specifies an order of evaluation for the actual parameters, the compiler must, of course, follow that order. Otherwise, it shoulduse a consistent order—either left to right or right to left. The evaluationorder matters for parameters that might have side effects.

For example, aprogram that used two routines push and pop to manipulate a stack wouldproduce different results for the sequence subtract(pop(), pop()) underleft-to-right and right-to-left evaluation.Procedures typically have several implicit arguments. These include theprocedure’s arp, the caller’s arp, the return address, and any information394 CHAPTER 7 Code Shapeneeded to establish addressability.

Object-oriented languages pass thereceiver as an implicit parameter. Some of these arguments are passed inregisters while others usually reside in memory. Many architectures have anoperation likejsr label1 ⇒ rithat transfers control to label1 and places the address of the operation thatfollows the jsr into ri .Procedures passed as actual parameters may require special treatment.

If pcalls q, passing procedure r as an argument, p must pass to q more information than r’s starting address. In particular, if the compiled code uses accesslinks to find nonlocal variables, the callee needs r’s lexical level so that asubsequent call to r can find the correct access link for r’s level.

The compiler can construct an haddress,leveli pair and pass it (or its address) in placeof the procedure-valued parameter. When the compiler constructs the precallsequence for a procedure-valued parameter, it must insert the extra code tofetch the lexical level and adjust the access link accordingly.7.9.2 Saving and Restoring RegistersUnder any calling convention, one or both of the caller and the callee mustpreserve register values. Often, linkage conventions use a combination ofcaller-saves and callee-saves registers. As both the cost of memory operations and the number of registers have risen, the cost of saving and restoringregisters at call sites has increased, to the point where it merits carefulattention.In choosing a strategy to save and restore registers, the compiler writer mustconsider both efficiency and code size.

Some processor features impact thischoice. Features that spill a portion of the register set can reduce code size.Examples of such features include register windows on the sparc machines,the multiword load and store operations on the Power architectures, and thehigh-level call operation on the vax. Each offers the compiler a compactway to save and restore some portion of the register set.While larger register sets can increase the number of registers that the codesaves and restores, in general, using these additional registers improves thespeed of the resulting code. With fewer registers, the compiler would beforced to generate loads and stores throughout the code; with more registers,7.9 Procedure Calls 395many of these spills occur only at a call site. (The larger register set shouldreduce the total number of spills in the code.) The concentration of savesand restores at call sites presents the compiler with opportunities to handle them in better ways than it might if they were spread across an entireprocedure.nnnUsing multi-register memory operations When saving and restoringadjacent registers, the compiler can use a multiregister memoryoperation.

Many isas support doubleword and quadword load and storeoperations. Using these operations can reduce code size; it may alsoimprove execution speed. Generalized multiregister memory operationscan have the same effect.Using a library routine As the number of registers grows, the precalland postreturn sequences both grow. The compiler writer can replacethe sequence of individual memory operations with a call to acompiler-supplied save or restore routine.

Done across all calls, thisstrategy can produce a significant savings in code size. Since the saveand restore routines are known only to the compiler, they can useminimal call sequence to keep the runtime cost low.The save and restore routines can take an argument that specifies whichregisters must be preserved. It may be worthwhile to generate optimizedversions for common cases, such as preserving all the caller-saves orcallee-saves registers.Combining responsibilities To further reduce overhead, the compilermight combine the work for caller-saves and callee-saves registers.