K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 86
Текст из файла (страница 86)
MostMost assembly languages have directives tospecify the alignment of the start of a data area,such as a doubleword boundary.340 CHAPTER 7 Code Shapevariables have interactions with many other variables; this creates a web ofrelationships that the compiler may not be able to satisfy concurrently.
Ifwe consider a loop that uses several large arrays, the problem of arrangingmutual noninterference becomes even worse. If the compiler can discoverthe relationship between the various array references in the loop, it can addpadding between the arrays to increase the likelihood that the references hitdifferent cache lines and, thus, do not interfere with each other.As we saw previously, the mapping of the program’s logical address spaceto the hardware’s physical address space need not preserve the distancebetween specific variables. Carrying this thought to its logical conclusion,the reader should ask how the compiler can ensure anything about relativeoffsets that are larger than the size of a virtual-memory page.
The processor’s cache may use either virtual addresses or physical addresses in itstag fields. A virtually addressed cache preserves the spacing between values that the compiler creates; with such a cache, the compiler may be ableto plan noninterference between large objects.
With a physically addressedcache, the distance between two locations in different pages is determinedby the page mapping (unless cache size ≤ page size). Thus, the compiler’sdecisions about memory layout have little, if any, effect, except within asingle page. In this situation, the compiler should focus on getting objectsthat are referenced together into the same page and, if possible, the samecache line.7.2.3 Keeping Values in RegistersSpillWhen the register allocator cannot assign somevirtual register to a physical register, it spills thevalue by storing it to RAM after each definitionand loading it into a temporary register beforeeach use.In a register-to-register memory model, the compiler tries to assign as manyvalues as possible to virtual registers.
In this approach, the compiler relies onthe register allocator to map virtual registers in the ir to physical registerson the processor and to spill to memory any virtual register that it cannotkeep in a physical register. If the compiler keeps a static value in a register,it must load the value before its first use in the procedure and store it backto memory before leaving the procedure, either at the procedure’s exit or atany call site within the procedure.In most of the examples in this book, we follow a simple method for assigning virtual registers to values. Each value receives its own virtual registerwith a distinct subscript. This discipline exposes the largest set of values tosubsequent analysis and optimization.
It may, in fact, use too many names.(See the digression, “The Impact of Naming” on page 248.) However, thisscheme has three principal advantages. It is simple. It can improve theresults of analysis and optimization. It prevents the compiler writer from7.2 Assigning Storage Locations 341working processor-specific constraints into the code before optimization,thus enhancing portability. A strong register allocator can manage the namespace and tailor it precisely to the needs of the application and the resourcesavailable on the target processor.A value that the compiler can keep in a register is called an unambiguousvalue; a value that can have more than one name is called an ambiguous value.
Ambiguity arises in several ways. Values stored in pointer-basedvariables are often ambiguous. Interactions between call-by-reference formal parameters and name scoping rules can make the formal parametersambiguous. Many compilers treat array-element values as ambiguous values because the compiler cannot tell if two references, such as A[i,j] andA[m,n], can ever refer to the same location.
In general, the compiler cannotkeep an ambiguous value in a register across either a definition or a use ofanother ambiguous value.With careful analysis, the compiler can disambiguate some of these cases.Consider the sequence of assignments in the margin, assuming that both aand b are ambiguous. If a and b refer to the same location, then c gets thevalue 26; otherwise it receives m + n + 13. The compiler cannot keep a in aregister across an assignment to another ambiguous variable unless it canprove that the set of locations to which the two names can refer are disjoint.This kind of comparative pairwise analysis is expensive, so compilers typically relegate ambiguous values to memory, with a load before each use anda store after each definition.Analysis of ambiguity therefore focuses on proving that a given value is notambiguous.
The analysis might be cursory and local. For example, in c, anylocal variable whose address is never taken is unambiguous in the procedurewhere it is declared. More complex analyses build sets of possible namesfor each pointer variable; any variable whose set has just one element isunambiguous. Unfortunately, analysis cannot resolve all ambiguities.
Thus,the compiler must be prepared to handle ambiguous values cautiously andcorrectly.Language features can affect the compiler’s ability to analyze ambiguity. Forexample, ansi c includes two keywords that directly communicate information about ambiguity.
The restrict keyword informs the compiler that apointer is unambiguous. It is often used when a procedure passes an addressdirectly at a call site. The volatile keyword lets the programmer declarethat the contents of a variable may change arbitrarily and without notice. It isused for hardware device registers and for variables that might be modifiedby interrupt service routines or other threads of control in an application.Unambiguous valueA value that can be accessed with just one nameis unambiguous.Ambiguous valueAny value that can be accessed by multiplenames is ambiguous.a ← m + n;b ← 13;c ← a + b;342 CHAPTER 7 Code ShapeSECTION REVIEWThe compiler must determine, for each value computed in the program,where it must be stored: in memory or a register and, in either case, thespecific location. It must assign to each value a location that is consistentwith both its lifetime (see Section 6.3) and its addressability (see Section6.4.3).
Thus, the compiler will group together values into data areas inwhich each value has the same storage class.Storage assignment provides the compiler with a key opportunity toencode information into the IR for use by later passes. Specifically, thedistinction between an ambiguous value and an unambiguous value canbe hard to derive by analysis of the IR. If, however, the compiler assignseach unambiguous value its own virtual register for its entire lifetime,subsequent phases of the compiler can use a value’s storage locationto determine whether or not a reference is ambiguous.
This knowledgesimplifies subsequent optimization.void fee() {int a, *b;···b = &a;···}Review Questions1. Sketch an algorithm that assigns offsets to a list of static variables ina single file from a C program. How does it order the variables? Whatalignment restrictions might your algorithm encounter?2. Consider the short C fragment in the margin. It mentions three values:a, b, and *b. Which values are ambiguous? Which are unambiguous?7.3 ARITHMETIC OPERATORSModern processors provide broad support for evaluating expressions.
Atypical risc machine has a full complement of three-address operations,including arithmetic operators, shifts, and boolean operators. The threeaddress form lets the compiler name the result of any operation and preserveit for later reuse. It also eliminates the major complication of the two-addressform: destructive operations.To generate code for a trivial expression, such as a + b, the compiler firstemits code to ensure that the values of a and b are in registers, say ra andrb .
If a is stored in memory at offset @a in the current ar, the resulting codemight beloadI @a⇒ r1loadAO rarp , r1 ⇒ ra7.3 Arithmetic Operators 343If, however, the value of a is already in a register, the compiler can simply use that register in place of ra . The compiler follows a similar chainof decisions for b. Finally, it emits an instruction to perform the addition,such asadd ra , rb ⇒ rtIf the expression is represented in a tree-like ir, this process fits into a postorder tree walk. Figure 7.5a shows the code for a tree walk that generatescode for simple expressions. It relies on two routines, base and offset, tohide some of the complexity. The base routine returns the name of a registerholding the base address for an identifier; if needed, it emits code to get thataddress into a register.
The offset routine has a similar function; it returnsthe name of a register holding the identifier’s offset relative to the addressreturned by base.expr(node) {int result, t1, t2;switch(type(node)) {case ×, ÷, +, -:t1 ← expr(LeftChild(node));t2 ← expr(RightChild(node));result ← NextRegister( );- Z=~Za× Z=~Zbcemit(op(node), t1, t2, result);break;(b) Abstract Syntax Tree fora - bx ccase IDENT:t1 ← base(node);t2 ← offset(node);result ← NextRegister( );emit( loadAO, t1, t2, result);break;case NUM:result ← NextRegister( );emit(loadI, val(node), none,result);break;}return result;}(a) Treewalk Code Generatorn FIGURE 7.5 Simple Treewalk Code Generator for Expressions.loadIloadAOloadIloadAOloadIloadAOmultsub@ararp , r1@brarp , r3@crarp , r5r4 , r6r2 , r7⇒⇒⇒⇒⇒⇒⇒⇒(c) Naive Coder1r2r3r4r5r6r7r8344 CHAPTER 7 Code ShapeThe same code handles +, -, ×, and ÷.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
