K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 95
Текст из файла (страница 95)
Unlessthe compiler performs an in-depth analysis of the array subscripts, it maynot be able to determine whether two array references overlap. When thecompiler cannot distinguish between two references, such as a[i,j,k] anda[i,j,l], it must treat both references conservatively. The problem of disambiguating array references, while challenging, is easier than the problemof disambiguating pointer references.Analysis to disambiguate pointer references and array references is amajor source of potential improvement in program performance.
Forpointer-intensive programs, the compiler may perform an interprocedural data-flow analysis aimed at discovering, for each pointer, the set ofobjects to which it can point. For array-intensive programs, the compiler may use data-dependence analysis to understand the patterns of arrayreferences.Data-dependence analysis is beyond the scope ofthis book. See [352, 20, 270].380 CHAPTER 7 Code ShapeSECTION REVIEWTo implement structures and arrays of structures, the compiler mustestablish a layout for each structure and must have a formula to calculatethe offset of any structure element.
In a language where the declarationsdictate the relative position of data elements, structure layout simplyrequires the compiler to calculate offsets. If the language allows thecompiler to determine the relative position of the data elements, thenthe layout problem is similar to data-area layout (see Section 7.2.2). Theaddress computation for a structure element is a simple application ofthe schemes used for scalar variables (e.g.
base + offset) and for arrayelements.Two features related to structures introduce complications. If thelanguage permits unions or variant structures, then input code mustspecify the desired element in an unambiguous way. The typical solutionto this problem is the use of fully qualified names for structure elementsin a union. The second issue arises from runtime allocation of structures.The use of pointers to hold addresses of dynamically allocated objectsintroduces ambiguities that complicate the issue of which values can bekept in registers.Review Questions1.
When the compiler lays out a structure, it must ensure that each element of the structure is aligned on the appropriate boundary. Thecompiler may need to insert padding (blank space) between elementsto meet alignment restrictions. Write a set of "rules of thumb" that aprogrammer could use to reduce the likelihood of compiler-insertedpadding.2.
If the compiler has the freedom to rearrange structures and arrays, itcan sometimes improve performance. What programming languagefeatures inhibit the compiler’s ability to perform such rearrangement?7.8 CONTROL-FLOW CONSTRUCTSA basic block is just a maximal-length sequence of straight-line, unpredicated code. Any statement that does not affect control flow can appearinside a block. Any control-flow transfer ends the block, as does a labelledstatement since it can be the target of a branch.
As the compiler generatescode, it can build up basic blocks by simply aggregating consecutive, unlabeled, non-control-flow operations. (We assume that a labelled statement isnot labelled gratuitously, that is, every labelled statement is the target of7.8 Control-Flow Constructs 381some branch.) The representation of a basic block need not be complex. Forexample, if the compiler has an assembly-like representation held in a simplelinear array, then a block can be described by a pair, h first,lasti, that holdsthe indices of the instruction that begins the block and the instruction thatends the block.
(If the block indices are stored in ascending numerical order,an array of firsts will suffice.)To tie a set of blocks together so that they form a procedure, the compilermust insert code that implements the control-flow operations of the sourceprogram. To capture the relationships among blocks, many compilers builda control-flow graph (cfg, see Sections 5.2.2 and 8.6.1) and use it for analysis, optimization, and code generation.
In the cfg, nodes represent basicblocks and edges represent possible transfers of control between blocks.Typically, the cfg is a derivative representation that contains references to amore detailed representation of each block.The code to implement control-flow constructs resides in the basic blocks—at or near the end of each block. (In iloc, there is no fall-through caseon a branch, so every block ends with a branch or a jump.
If the ir models delay slots, then the control-flow operation may not be the last operationin the block.) While many different syntactic conventions have been usedto express control flow, the number of underlying concepts is small. Thissection examines many of the control-flow constructs found in modernprogramming languages.7.8.1 Conditional ExecutionMost programming languages provide some version of an if-then-elseconstruct. Given the source textif exprthen statement1else statement2statement3the compiler must generate code that evaluates expr and branches tostatement1 or statement2 , based on the value of expr.
The iloc code thatimplements the two statements must end with a jump to statement3 . Aswe saw in Section 7.4, the compiler has many options for implementingif-then-else constructs.The discussion in Section 7.4 focused on evaluating the controlling expression. It showed how the underlying instruction set influenced the strategies for handling both the controlling expression and, in some cases, thecontrolled statements.382 CHAPTER 7 Code ShapeProgrammers can place arbitrarily large code fragments inside the then andelse parts.
The size of these code fragments has an impact on the com-piler’s strategy for implementing the if-then-else construct. With trivialthen and else parts, as shown in Figure 7.9, the primary consideration forthe compiler is matching the expression evaluation to the underlying hardware. As the then and else parts grow, the importance of efficient executioninside the then and else parts begins to outweigh the cost of executing thecontrolling expression.For example, on a machine that supports predicated execution, using predicates for large blocks in the then and else parts can waste execution cycles.Since the processor must issue each predicated instruction to one of its functional units, each operation with a false predicate has an opportunity cost—itties up an issue slot.
With large blocks of code under both the then andelse parts, the cost of unexecuted instructions may outweigh the overheadof using a conditional branch.Figure 7.14 illustrates this tradeoff. It assumes that both the then and elseparts contain 10 independent iloc operations and that the target machine canissue two operations per cycle.Figure 7.14a shows code that might be generated using predication; itassumes that the value of the controlling expression is in r1 . The code issuestwo instructions per cycle. One of them executes in each cycle.
All of thethen part’s operations are issued to Unit 1, while the then part’s operations are issued to Unit 2. The code avoids all branching. If each operationUnit 1(r1)(r1)(r1)(r1)(r1)(r1)(r1)(r1)(r1)(r1)Unit 2comparison ⇒ r1op1(¬r1) op11op2(¬r1) op12op3(¬r1) op13op4(¬r1) op14op5(¬r1) op15op6(¬r1) op16op7(¬r1) op17op8(¬r1) op18op9(¬r1) op19op10 (¬r1) op20Unit 1Unit 2compare & branchL1 : op1op3op5op7op9jumpIop2op4op6op8op10→ L3L2 : op11op13op15op17op19jumpIop12op14op16op18op20→ L3L3 : nop(a) Using Predicatesn FIGURE 7.14 Predication versus Branching.(b) Using Branches7.8 Control-Flow Constructs 383BRANCH PREDICTION BY USERSOne urban compiler legend concerns branch prediction. FORTRAN hasan arithmetic if statement that takes one of three branches, based onwhether the controlling expression evaluates to a negative number, tozero, or to a positive number.
One early compiler allowed the user to supply a weight for each label that reflected the relative probability of takingthat branch. The compiler then used the weights to order the branches ina way that minimized total expected delay from branching.After the compiler had been in the field for a year, the story goes, a maintainer discovered that the branch weights were being used in the reverseorder, maximizing the expected delay. No one had complained. The storyis usually told as a fable about the value of programmers’ opinions aboutthe behavior of code they have written. (Of course, no one reported theimprovement, if any, from using the branch weights in the correct order.)takes a single cycle, it takes 10 cycles to execute the controlled statements,independent of which branch is taken.Figure 7.14b shows code that might be generated using branches; it assumesthat control flows to L1 for the then part or to L2 for the else part.
Becausethe instructions are independent, the code issues two instructions per cycle.Following the then path takes five cycles to execute the operations for thetaken path, plus the cost of the terminal jump. The cost for the else part isidentical.The predicated version avoids the initial branch required in the unpredicatedcode (to either L1 or L2 in the figure), as well as the terminal jumps (toL3 ). The branching version incurs the overhead of a branch and a jump, butmay execute faster.
Each path contains a conditional branch, five cycles ofoperations, and the terminal jump. (Some of the operations may be used tofill delay slots on jumps.) The difference lies in the effective issue rate—the branching version issues roughly half the instructions of the predicatedversion. As the code fragments in the then and else parts grow larger, thisdifference becomes larger.Choosing between branching and predication to implement an if-thenelse requires some care. Several issues should be considered, as follows:1. Expected frequency of execution If one side of the conditional executessignificantly more often, techniques that speed execution of that pathmay produce faster code.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
