K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 84
Текст из файла (страница 84)
The alternative, generating the ir with scalar variables stored in memory and having theallocator promote them into registers, requires much more complex analysis.Engineering a Compiler. DOI: 10.1016/B978-0-12-088478-0.00007-4c 2012, Elsevier Inc. All rights reserved.Copyright 331332 CHAPTER 7 Code ShapeEncoding knowledge into the ir name space in this way both simplifies thelater passes and improves the compiler’s effectiveness and efficiency.Conceptual RoadmapThe translation of source code constructs into target-machine operations isone of the fundamental acts of compilation.
The compiler must produce target code for each source-language construct. Many of the same issues arisewhen generating ir in the compiler’s front end and generating assembly codefor a real processor in its back end. The target processor may, due to finiteresources and idiosyncratic features, present a more difficult problem, butthe principles are the same.This chapter focuses on ways to implement various source-language constructs. In many cases, specific details of the implementation affect thecompiler’s ability to analyze and to improve the code in later passes.
Theconcept of “code shape” encapsulates all of the decisions, large and small,that the compiler writer makes about how to represent the computation inboth ir and assembly code. Careful attention to code shape can both simplify the task of analyzing and improving the code, and improve the qualityof the final code that the compiler produces.OverviewIn general, the compiler writer should focus on shaping the code so that thevarious passes in the compiler can combine to produce outstanding code. Inpractice, a compiler can implement most source-language constructs manyways on a given processor.
These variations use different operations anddifferent approaches. Some of these implementations are faster than others;some use less memory; some use fewer registers; some might consume lessenergy during execution. We consider these differences to be matters of codeshape.Code shape has a strong impact both on the behavior of the compiled codeand on the ability of the optimizer and back end to improve it. Consider,for example, the way that a c compiler might implement a switch statement that switched on a single-byte character value. The compiler mightuse a cascaded series of if–then–else statements to implement the switchstatement. Depending on the layout of the tests, this could produce different results. If the first test is for zero, the second for one, and so on, thenthis approach devolves to linear search over a field of 256 keys.
If characters are uniformly distributed, the character searches will require an averageof 128 tests and branches per character—an expensive way to implement acase statement. If, instead, the tests perform a binary search, the average casewould involve eight tests and branches, a more palatable number. To trade7.1 Introduction 333Source CodeCodex+y+zLow-Level, Three-Address Coder1 ← rx + ry r1 ← rx + rz r1 ← ry + rzr2 ← r1 + rz r2 ← r1 + ry r2 ← r1 + rx+Treexy+z++rzrx ry+rx rz++ryryrxrzn FIGURE 7.1 Alternate Code Shapes for x + y + z.data space for speed, the compiler can construct a table of 256 labels andinterpret the character by loading the corresponding table entry and jumpingto it—with a constant overhead per character.All of these are legal implementations of the switch statement.
Decidingwhich one makes sense for a particular switch statement depends on manyfactors. In particular, the number of cases and their relative execution frequencies are important, as is detailed knowledge of the cost structure forbranching on the processor. Even when the compiler cannot determine theinformation that it needs to make the best choice, it must make a choice. Thedifferences among the possible implementations, and the compiler’s choice,are matters of code shape.As another example, consider the simple expression x + y + z, where x, y,and z are integers.
Figure 7.1 shows several ways of implementing thisexpression. In source-code form, we may think of the operation as a ternaryadd, shown on the left. However, mapping this idealized operation into asequence of binary additions exposes the impact of evaluation order. Thethree versions on the right show three possible evaluation orders, both asthree-address code and as abstract syntax trees. (We assume that each variable is in an appropriately named register and that the source language doesnot specify the evaluation order for such an expression.) Because integeraddition is both commutative and associative, all the orders are equivalent;the compiler must choose one to implement.Left associativity would produce the first binary tree.
This tree seems “natural” in that left associativity corresponds to our left-to-right reading style.Consider what happens if we replace y with the literal constant 2 and z with3. Of course, x + 2 + 3 is equivalent to x + 5. The compiler should detect thecomputation of 2 + 3, evaluate it, and fold the result directly into the code.In the left-associative form, however, 2 + 3 never occurs. The order x + z + yhides it, as well. The right-associative version exposes the opportunity for334 CHAPTER 7 Code Shapeimprovement.
For each prospective tree, however, there is an assignmentof variables and constants to x, y, and z that does not expose the constantexpression for optimization.As with the switch statement, the compiler cannot choose the best shapefor this expression without understanding the context in which it appears.If, for example, the expression x + y has been computed recently and neitherthe values of x nor y have changed, then using the leftmost shape would letthe compiler replace the first operation, r1 ← rx + ry , with a reference tothe previously computed value. Often, the best evaluation order depends oncontext from the surrounding code.This chapter explores the code-shape issues that arise in implementingmany common source-language constructs.
It focuses on the code thatshould be generated for specific constructs, while largely ignoring the algorithms required to pick specific assembly-language instructions. The issuesof instruction selection, register allocation, and instruction scheduling aretreated separately, in later chapters.7.2 ASSIGNING STORAGE LOCATIONSAs part of translation, the compiler must assign a storage location to eachvalue produced by the code. The compiler must understand the value’s type,its size, its visibility, and its lifetime.
The compiler must take into accountthe runtime layout of memory, any source-language constraints on the layoutof data areas and data structures, and any target-processor constraints onplacement or use of data. The compiler addresses these issues by definingand following a set of conventions.A typical procedure computes many values. Some of them, such as variables in an Algol-like language, have explicit names in the source code.Other values have implicit names, such as the value i - 3 in the expressionA[i - 3, j + 2].nnThe lifetime of a named value is defined by source-language rules andactual use in the code.
For example, a static variable’s value must bepreserved across multiple invocations of its defining procedure, while alocal variable of the same procedure is only needed from its firstdefinition to its last use in each invocation.In contrast, the compiler has more freedom in how it treats unnamedvalues, such as i - 3. It must handle them in ways that are consistentwith the meaning of the program, but it has great leeway in determiningwhere these values reside and how long to retain them.7.2 Assigning Storage Locations 335Compilation options may also affect placement; for example, code compiledto work with a debugger should preserve all values that the debugger canname—typically named variables.The compiler must also decide, for each value, whether to keep it in a registeror to keep it in memory.
In general, compilers adopt a “memory model”—aset of rules to guide it in choosing locations for values. Two common policiesare a memory-to-memory model and a register-to-register model. The choicebetween them has a major impact on the code that the compiler produces.With a memory-to-memory model, the compiler assumes that all valuesreside in memory. Values are loaded into registers as needed, but the codestores them back to memory after each definition. In a memory-to-memorymodel, the ir typically uses physical register names. The compiler ensuresthat demand for registers does not exceed supply at each statement.In a register-to-register model, the compiler assumes that it has enough registers to express the computation.
It invents a distinct name, a virtual register,for each value that can legally reside in a register. The compiled code willstore a virtual register’s value to memory only when absolutely necessary,such as when it is passed as a parameter or a return value, or when theregister allocator spills it.Physical registera named register in the target ISAVirtual registera symbolic name used in the IR in place of aphysical register nameChoice of memory model also affects the compiler’s structure. For example,in a memory-to-memory model, the register allocator is an optimization thatimproves the code. In a register-to-register memory model, the register allocator is a mandatory phase that reduces demand for registers and maps thevirtual register names onto physical register names.7.2.1 Placing Runtime Data StructuresTo perform storage assignment, the compiler must understand the systemwide conventions on memory allocation and use.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
