Cooper_Engineering_a_Compiler(Second Edition) (1157546), страница 69
Текст из файла (страница 69)
The call mustcreate storage for the objects declared by the callee. This allocationmust be both automatic and efficient—a consequence of calling theprocedure.3. External Interface Procedures define the critical interfaces among theparts of large software systems. The linkage convention defines rulesthat map names to values and locations, that preserve the caller’sruntime environment and create the callee’s environment, and thattransfer control from caller to callee and back.
It creates a context inwhich the programmer can safely invoke code written by other people.The existence of uniform calling sequences allows the development anduse of libraries and system calls. Without a linkage convention, both theprogrammer and the compiler would need detailed knowledge about theimplementation of the callee at each procedure call.Thus, the procedure is, in many ways, the fundamental abstraction thatunderlies Algol-like languages.
It is an elaborate facade created collaboratively by the compiler and the underlying hardware, with assistancefrom the operating system. Procedures create named variables and mapthem to virtual addresses; the operating system maps virtual addresses tophysical addresses. Procedures establish rules for visibility of names andaddressability; the hardware typically provides several variants of load andstore operations. Procedures let us decompose large software systems intocomponents; linkers and loaders knit these together into an executable program that the hardware can execute by advancing its program counter andfollowing branches.Linkage conventionan agreement between the compiler andoperating system that defines the actions takento call a procedure or functionActual parameterA value or variable passed as a parameter at a callsite is an actual parameter of the call.Formal parameterA name declared as a parameter of someprocedure p is a formal parameter of p.272 CHAPTER 6 The Procedure AbstractionA WORD ABOUT TIMEThis chapter deals with both compile-time and runtime mechanisms.
Thedistinction between events that occur at compile time and those thatoccur at runtime can be confusing. The compiler generates all the codethat executes at runtime. As part of the compilation process, the compileranalyzes the source code and builds data structures that encode the resultsof the analysis. (Recall the discussion of lexically scoped symbol tables inSection 5.5.3.) The compiler determines much of the storage layout thatthe program will use at runtime. It then generates the code needed tocreate that layout, to maintain it during execution, and to access both dataobjects and code in memory. When the compiled code runs, it accessesdata objects and calls procedures or methods.
All of the code is generatedat compile time; all of the accesses occur at runtime.A large part of the compiler’s task is putting in place the code needed torealize the various pieces of the procedure abstraction. The compiler mustdictate the layout of memory and encode that layout in the generated program. Since it may compile the different components of the program atdifferent times, without knowing their relationships to one another, thismemory layout and all the conventions that it induces must be standardizedand uniformly applied. The compiler must also use the various interfacesprovided by the operating system, to handle input and output, managememory, and communicate with other processes.This chapter focuses on the procedure as an abstraction and the mechanismsthat the compiler uses to establish its control abstraction, name space, andinterface to the outside world.6.2 PROCEDURE CALLSIn Algol-like languages (alls), procedures have a simple and clearcall/return discipline.
A procedure call transfers control from the call sitein the caller to the start of the callee; on exit from the callee, controlreturns to the point in the caller that immediately follows its invocation.If the callee invokes other procedures, they return control in the same way.Figure 6.1a shows a Pascal program with several nested procedures, whileFigures 6.1b and 6.1c show the program’s call graph and its executionhistory, respectively.The call graph shows the set of potential calls among the procedures.Executing Main can result in two calls to Fee: one from Foe and anotherfrom Fum. The execution history shows that both calls occur at runtime.
Each6.2 Procedure Calls 273program Main(input, output);Mainvar x,y,z: integer;procedure Fee;var x: integer;Fiebegin { Fee }x := 1;Foey := x * 2 + 1end;Fumprocedure Fie;var y: real;procedure Foe;Feevar z: real;procedure Fum;(b) Call Graphvar y: real;begin { Fum }x := 1.25 * z;Fee;writeln(‘x = ’,x)end;begin { Foe }z := 1;Fee;Fumend;begin { Fie }Foe;writeln(‘x = ’,x)end;begin { Main }x := 0;Fieend.(a) Example Pascal Program1.2.3.4.5.6.7.8.9.10.Main calls FieFie calls FoeFoe calls FeeFee returns to FoeFoe calls FumFum calls FeeFee returns to FumFum returns to FoeFoe returns to FieFie returns to Main(c) Execution Historyn FIGURE 6.1 Nonrecursive Pascal Program and Its Execution History.of these calls creates a distinct instance, or activation, of Fee.
By the timethat Fum is called, the first instance of Fee is no longer active. It was createdby the call from Foe (event 3 in the execution history), and destroyed afterit returned control back to Foe (event 4). When control returns to Fee, fromthe call in Fum (event 6), it creates a new activation of Fee. The return fromFee to Fum destroys that activation.ActivationA call to a procedure activates it; thus, we call aninstance of its execution an activation.274 CHAPTER 6 The Procedure Abstraction(define (fact k)(cond[(<= k 1) 1][else (* (fact (sub1 k)) k)]))n FIGURE 6.2 Recursive Factorial Program in Scheme.When the program executes the assignment x := 1 in the first invocationof Fee, the active procedures are Fee, Foe, Fie, and Main. These all lieon a path in the call graph from Main to Fee.
Similarly, when it executesthe second invocation of Fee, the active procedures (Fee, Fum, Foe, Fie,and Main) lie on a path from Main to Fee. Pascal’s call and return mechanism ensures that, at any point during execution, the procedure activationsinstantiate some rooted path through the call graph.DivergeA computation that does not terminate normallyis said to diverge.Return addressWhen p calls q, the address in p where executionshould continue after p’s return is called itsreturn address.When the compiler generates code for calls and returns, that code must preserve enough information so that calls and returns operate correctly. Thus,when Foe calls Fum, the code must record the address in Foe to which Fumshould return control.
Fum may diverge, or not return, due to a runtime error,an infinite loop, or a call to another procedure that does not return. Still,the call mechanism must preserve enough information to allow execution toresume in Foe if Fum returns.The call and return behavior of alls can be modelled with a stack. AsFie calls Foe, it pushes the return address in Fie onto the stack. WhenFoe returns, it pops that address off the stack and jumps to the address.If all procedures use the same stack, popping a return address exposes thenext one.The stack mechanism handles recursion as well. The call mechanism, ineffect, unrolls the cyclic path through the call graph and creates a distinctactivation for each call to a procedure.
As long as the recursion terminates,this path will be finite and the stack of return addresses will correctly capturethe program’s behavior.To make this concrete, consider the recursive factorial computation shownin Figure 6.2. When invoked to compute (fact 5), it generates a series ofrecursive calls: (fact 5) calls (fact 4) calls (fact 3) calls (fact 2)calls (fact 1). At that point, the cond statement executes the clause for(<= k 1), terminating the recursion. The recursion unwinds in the reverseorder, with the call to (fact 1) returning the value 1 to (fact 2). It, inturn, returns the value 2 to (fact 3), which returns 6 to (fact 4). Finally,(fact 4) returns 24 to (fact 5), which multiplies 24 times 5 to return theanswer 120. The recursive program exhibits last-in, first-out behavior, so thestack mechanism correctly tracks all of the return addresses.6.2 Procedure Calls 275Control Flow in Object-Oriented LanguagesFrom the perspective of procedure calls and returns, object-oriented languages (ools) are similar to alls.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
