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

We call these alignment rules.Some processors provide operations to implement procedure calls beyonda simple jump operation. Such support often adds further alignment constraints. For example, the isa might dictate the format of the ar and thealignment of the start of each ar. The dec vax computers had a particularlyelaborate call instruction; it stored registers and other parts of the processorstate based on a call-specific bit mask that the compiler produced.For each data area, the compiler must compute a layout that assigns eachvariable in the data area its offset. That layout must comply with the isa’salignment rules. The compiler may need to insert padding between somevariables to obtain the proper alignments. To minimize wasted space, thecompiler should order the variables into groups, from those with the mostrestrictive alignment rules to those with the least.

(For example, doubleword alignment is more restrictive than word alignment.) The compiler thenassigns offsets to the variables in the most restricted category, followed bythe next most restricted class, and so on, until all variables have offsets.Since alignment rules almost always specify a power of two, the end of eachcategory will naturally fit the restriction for the next category.Relative Offsets and Cache PerformanceThe widespread use of cache memories in modern computer systems hassubtle implications for the layout of variables in memory. If two values areused in proximity in the code, the compiler would like to ensure that they canreside in the cache at the same time. This can be accomplished in two ways.In the best situation, the two values would share a single cache block, whichguarantees that the values are fetched from memory to the cache together.

Ifthey cannot share a cache block, the compiler would like to ensure that thetwo variables map to different cache lines. The compiler can achieve this bycontrolling the distance between their addresses.If we consider just two variables, controlling the distance between themseems manageable. When all the active variables are considered, however, the problem of optimal arrangement for a cache is np-complete. 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 .