K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 78
Текст из файла (страница 78)
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. The flow of values between procedures occurs with two differentmechanisms: the use of parameters and the use of values that arevisible in multiple procedures.
In each of these cases, the compiler writermust arrange access conventions and runtime structures to support theaccess. For parameter binding, two particular mechanisms have emergedas the common cases: call by value and call by reference. For nonlocalaccesses, the compiler must emit code to compute the appropriate baseaddresses. Two mechanisms have emerged as the common cases: accesslinks and a display.The most confusing aspect of this material is the distinction betweenactions that happen at compile time, such as the parser finding staticcoordinates for a variable, and those that happen at runtime, such asthe executing program tracing up a chain of access links to find the ARPof some surrounding scope.
In the case of compile-time actions, thecompiler performs the action directly. In the case of runtime actions, thecompiler emits code that will perform the action at runtime.Review Questions1. An early FORTRAN implementation had an odd bug. The short programin the margin would print, as its result, the value 16. What did thecompiler do that led to this result? What should it have done instead?(FORTRAN uses call-by-reference parameter binding.)2.
Compare and contrast the costs involved in using access links versus global displays to establish addresses for references to variablesdeclared in surrounding scopes. Which would you choose? Do language features affect your choice?subroutine change(n)integer nn = n * 2endprogram testcall change(2)print *, 2 * 2end308 CHAPTER 6 The Procedure Abstraction6.5 STANDARDIZED LINKAGESThe procedure linkage is a contract between the compiler, the operating system, and the target machine that clearly divides responsibility for naming,allocation of resources, addressability, and protection.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
