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

Using too many registers to hold base addresses may adverselyaffect overall runtime performance.Variables with Dynamic Base AddressesAs described in Section 6.3.2, local variables declared within a procedureare typically stored in the procedure’s ar. Thus, they have dynamic baseaddresses. To access these values, the compiler needs a mechanism to findthe addresses of various ars. Fortunately, lexical scoping rules limit the setof ars that can be accessed from any point in the code to the current ar andthe ars of lexically enclosing procedures.Local Variable of the Current ProcedureAccessing a local variable of the current procedure is trivial.

Its base addressis simply the address of the current ar, which is stored in the arp. Thus, thecompiler can emit code that adds its offset to the arp and uses the result asthe value’s address. (This offset is the same value as the offset in the value’sstatic coordinate.) In iloc the compiler might use a loadAI (an “address +immediate offset” operation) or a loadAO (an “address + offset” operation).Most processors provide efficient support for these common operations.In some cases, a value is not stored at a constant offset from the arp.

Thevalue might reside in a register, in which case loads and stores are notneeded. If the variable has an unpredictable or changing size, the compilerwill store it in an area reserved for variable-size objects, either at the endof the ar or in the heap. In this case, the compiler can reserve space in thear for a pointer to the variable’s actual location and generate one additionalload to access the variable.Local Variables of Other ProceduresTo access a local variable of some enclosing lexical scope, the compilermust arrange for the construction of runtime data structures that map a staticcoordinate, produced using a lexically-scoped symbol table in the parser,into a runtime address.For example, assume that procedure fee, at lexical level m, references variable a from fee’s lexical ancestor fie, at level n.

The parser converts thisreference into a static coordinate hn,oi, where o is a’s offset in the ar for fie.The compiler can compute the number of lexical levels between fee and fieas m−n. (The coordinate hm–n,oi is sometimes called the static-distancecoordinate of the reference.)The compiler needs a mechanism to convert hn,oi into a runtime address.In general, that scheme will use runtime data structures to find the arp of304 CHAPTER 6 The Procedure Abstractionthe most recent level n procedure, and use that arp as the base address inits computation. It adds the offset o to that base address to produce a runtime address for the value whose static coordinate is hn,oi.

The complicationlies in building and traversing the runtime data structures to find the baseaddress. The following subsections examine two common methods: use ofaccess links and use of a global display.Access LinksThe intuition behind access links is simple. The compiler ensures that eachar contains a pointer, called an access link or a static link, to the ar ofits immediate lexical ancestor.

The access links form a chain that includesall the lexical ancestors of the current procedure, as shown in Figure 6.8.Thus, any local variable of another procedure that is visible to the currentprocedure is stored in an ar on the chain of access links that begins in thecurrent procedure.To access a value hn,oi from a level m procedure, the compiler emits codeto walk the chain of links and find the level n arp. Next, it emits a loadthat uses the level n arp and o. To make this concrete, consider the programrepresented by Figure 6.8. Assume that m is 2 and that the access link isstored at an offset of −4 from the arp.

The following table shows a set ofLevel 0Local-Data AreaLevel 1Local-Data AreaLevel 2ARPCaller’s ARPLocal-Data AreaAccess LinkCaller’s ARPReturn AddressAccess LinkReturn ValueReturn AddressRegister-Save AreaParametersn FIGURE 6.8 Using Access Links.Access LinkReturn AddressReturn ValueRegister-Save AreaParametersReturn ValueRegister-Save AreaCaller’s ARPParameters6.4 Communicating Values Between Procedures 305three different static coordinates alongside the iloc code that a compilermight generate for them.

Each sequence leaves the result in r2 .CoordinateCodeh2,24iloadAI rarp , 24 ⇒ r2h1,12iloadAI rarp , -4 ⇒ r1loadAI r1 , 12⇒ r2h0,16iloadAI rarp , -4 ⇒ r1loadAI r1 , -4⇒ r1loadAI r1 , 16⇒ r2Since the compiler has the static coordinate for each reference, it cancompute the static distance (m−n). The distance tells it how many chainfollowing loads to generate, so the compiler can emit the correct sequencefor each nonlocal reference. The cost of the address calculation is proportional to the static distance. If programs exhibit shallow lexical nesting, thedifference in cost between accessing two variables at different levels will befairly small.To maintain access links, the compiler must add code to each procedure callthat finds the appropriate arp and stores it as the callee’s access link.

For acaller at level m and a callee at level n, three cases arise. If n = m + 1, thecallee is nested inside the caller, and the callee can use the caller’s arp as itsaccess link. If n = m, the callee’s access link is the same as the caller’s accesslink. Finally, if n < m, the callee’s access link is the level n − 1 access linkfor the caller. (If n is zero, the access link is null.) The compiler can generatea sequence of m − n + 1 loads to find this arp and store that pointer as thecallee’s access link.Global DisplayIn this scheme, the compiler allocates a single global array, called thedisplay, to hold the arp of the most recent activation of a procedure ateach lexical level.

All references to local variables of other proceduresbecome indirect references through the display. To access a variable hn,oi,the compiler uses the arp from element n of the display. It uses o as theoffset and generates the appropriate load operation. Figure 6.9 shows thissituation.Returning to the static coordinates used in the discussion of access links, thefollowing table shows code that the compiler might emit for a display-based306 CHAPTER 6 The Procedure AbstractionDisplayLevel 0Level 0Local-Data AreaLevel 1Level 1Level 2Saved PointerLocal-Data AreaLevel 3Level 2Return AddressCaller’s ARPLocal-Data AreaARPCaller’s ARPCaller’s ARPSaved PointerReturn AddressReturn ValueReturn ValueSaved PointerRegister-Save AreaReturn AddressParametersReturn ValueRegister-Save AreaParametersRegister-Save AreaParametersn FIGURE 6.9 Using a Global Display.implementation. Assume that the current procedure is at lexical level 2, andthat the label disp gives the address of the display.CoordinateCodeh2,24iloadAI rarp , 24 ⇒ r2h1,12iloadI disploadAI r1 , 4h0,16iloadAI r1 , 12⇒ r1⇒ r1⇒ r2loadI disploadAI r1 , 16⇒ r1⇒ r2With a display, the cost of nonlocal access is fixed.

With access links, thecompiler generates a series of m−n loads; with a display, it uses n × l asoffset into the display, where l is the length of a pointer (4 in the example).Local access is still cheaper than nonlocal access, but with a display, thepenalty for nonlocal access is constant, rather than variable.Of course, the compiler must insert code where needed to maintain the display. Thus, when procedure p at level n calls some procedure q at level n+1,p’s arp becomes the display entry for level n.

(While p is executing, that6.4 Communicating Values Between Procedures 307entry is unused.) The simplest way to keep the display current is to have pupdate the level n entry when control enters p and to restore it on exit from p.On entry, p can copy the level n display entry to the reserved addressabilityslot in its ar and store its own arp in the level n slot of the display.Many of these display updates can be avoided. The only procedures that canuse the arp stored by a procedure p are procedures q that p calls (directly orindirectly), where q is nested inside p’s scope. Thus, any p that does not calla procedure nested inside itself need not update the display. This eliminatesall updates in leaf procedures, as well as many other updates.SECTION REVIEWIf the fundamental purpose of a procedure is abstraction, then theability to communicate values between procedures is critical to theirutility.