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

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. The compiler, the operatingsystem, and the processor cooperate to ensure that multiple programs canexecute safely on an interleaved (time-sliced) basis. Thus, many of the decisions about how to lay out, manipulate, and manage a program’s addressspace lie outside the purview of the compiler writer. However, the decisions have a strong impact on the code that the compiler generates.

Thus,the compiler writer must have a broad understanding of these issues.Figure 7.2 shows a typical layout for the address space used by a single compiled program. The layout places fixed size regions of code and data at thelow end of the address space. Code sits at the bottom of the address space;the adjacent region, labelled Static, holds both static and global data areas,along with any fixed size data created by the compiler. The region aboveThe compiler may create additional static dataareas to hold constant values, jump tables, anddebugging information.336 CHAPTER 7 Code Shape2nFree MemoryStackHeapStaticCodeLown FIGURE 7.2 Logical Address-Space Layout.these static data areas is devoted to data areas that expand and contract.

Ifthe compiler can stack-allocate ars, it will need a runtime stack. In most languages, it will also need a heap for dynamically allocated data structures. Toallow for efficient space utilization, the heap and the stack should be placedat opposite ends of the open space and grow towards each other. In the drawing, the heap grows toward higher addresses, while the stack grows towardlower addresses. The opposite arrangement works equally well.From the compiler’s perspective, this logical address space is the wholepicture. However, modern computer systems typically execute many programs in an interleaved fashion. The operating system maps multiple logicaladdress spaces into the single physical address space supported by the processor.

Figure 7.3 shows this larger picture. Each program is isolated in itsown logical address space; each can behave as if it has its own machine.Pagethe unit of allocation in a virtual address spaceThe operating system maps virtual pages intophysical page frames.A single logical address space can occupy disjoint pages in the physicaladdress space; thus, the addresses 100,000 and 200,000 in the program’s logical address space need not be 100,000 bytes apart in physical memory. Infact, the physical address associated with the logical address 100,000 may belarger than the physical address associated with the logical address 200,000.The mapping from logical addresses to physical addresses is maintainedcooperatively by the hardware and the operating system.

It is, in almost allrespects, beyond the compiler’s purview.7.2.2 Layout for Data AreasFor convenience, the compiler groups together the storage for values withthe same lifetimes and visibility; it creates distinct data areas for them. Theplacement of these data areas depends on language rules about lifetimesand visibility of values. For example, the compiler can place procedurelocal automatic storage inside the procedure’s activation record, preciselybecause the lifetimes of such variables matches the ar’s lifetime.

In contrast,it must place procedure-local static storage where it will exist acrossinvocations—in the “static” region of memory. Figure 7.4 shows a typical7.2 Assigning Storage Locations 337Compiler’s View2n……large0StackStack2n0CodeStaticHeap0CodeStaticHeap2nStackStackCodeStaticHeap0CodeStaticHeap2n0PhysicalAddressesVirtualAddressesOperatingSystem’sViewHardware’s Viewn FIGURE 7.3 Different Views of the Address Space.if x is declared locally in procedure p, andits value is not preserved across distinct invocations of pthen assign it to procedure-local storageif its value is preserved across invocations of pthen assign it to procedure-local static storageif x is declared as globally visiblethen assign it to global storageif x is allocated under program controlthen assign it to the runtime heapn FIGURE 7.4 Assigning Names to Data Areas.set of rules for assigning a variable to a specific data area.

Object-orientedlanguages follow different rules, but the problems are no more complex.Placing local automatic variables in the ar leads to efficient access. Sincethe code already needs the arp in a register, it can use arp-relative offsetsto access these values, with operations such as loadAI or loadAO. Frequentaccess to the ar will likely keep it in the data cache. The compiler placesvariables with either static lifetimes or global visibility into data areas in the“static” region of memory. Access to these values takes slightly more workat runtime; the compiler must ensure that it has an address for the data areain a register.Values stored in the heap have lifetimes that the compiler cannot easilypredict.

A value can be placed in the heap by two distinct mechanisms.To establish the address of a static or global dataarea, the compiler typically loads a relocatableassembly language label.338 CHAPTER 7 Code ShapeA PRIMER ON CACHE MEMORIESOne way that architects try to bridge the gap between processor speed andmemory speed is through the use of cache memories. A cache is a small,fast memory placed between the processor and main memory. The cacheis divided into a series of equal-sized frames. Each frame has an addressfield, called its tag, that holds a main-memory address.The hardware automatically maps memory locations to cache frames.

Thesimplest mapping, used in a direct-mapped cache, computes the cacheaddress as the main memory address modulo the size of the cache. Thispartitions the memory into a linear set of blocks, each the size of a cacheframe. A line is a memory block that maps to a frame. At any point in time,each cache frame holds a copy of the data from one of its blocks. Its tagfield holds the address in memory where that data normally resides.On each read access to memory, the hardware checks to see if therequested word is already in its cache frame.

If so, the requested bytesare returned to the processor. If not, the block currently in the frame isevicted and the requested block is brought into the cache.Some caches use more complex mappings. A set-associative cache usesmultiple frames for each cache line, typically two or four frames per line.A fully associative cache can place any block in any frame. Both theseschemes use an associative search over the tags to determine if a block isin the cache. Associative schemes use a policy to determine which block toevict; common schemes are random replacement and least-recently-used(LRU) replacement.In practice, the effective memory speed is determined by memory bandwidth, cache block length, the ratio of cache speed to memory speed,and the percentage of accesses that hit in the cache. From the compiler’sperspective, the first three are fixed.

Compiler-based efforts to improvememory performance focus on increasing the ratio of cache hits to cachemisses, called the hit ratio.Some architectures provide instructions that allow a program to give thecache hints as to when specific blocks should be brought into memory(prefetched) and when they are no longer needed (flushed).The programmer can explicitly allocate storage from the heap; the compilershould not override that decision. The compiler can place a value on the heapwhen it detects that the value might outlive the procedure that created it. Ineither case, a value in the heap is represented by a full address, rather thanan offset from some base address.7.2 Assigning Storage Locations 339Assigning OffsetsIn the case of local, static, and global data areas, the compiler must assigneach name an offset inside the data area. Target isas constrain the placement of data items in memory. A typical set of constraints might specifythat 32-bit integers and 32-bit floating-point numbers begin on word (32-bit)boundaries, that 64-bit integer and floating-point data begin on doubleword(64-bit) boundaries, and that string data begin on halfword (16-bit) boundaries.