Cooper_Engineering_a_Compiler(Second Edition) (1157546), страница 68
Текст из файла (страница 68)
Draw its cfg andshow its ssa form as a linear code.5. Show how the expression x - 2 × y might be translated into an abstractsyntax tree, one-address code, two-address code, and three-addresscode.6. Given a linear list of iloc operations, develop an algorithm that findsthe basic blocks in the iloc code.
Extend your algorithm to build acontrol-flow graph to represent the connections between blocks.7. For the code shown in Figure 5.14, find the basic blocks and constructthe cfg.Section 5.4266 CHAPTER 5 Intermediate Representations···x ← ···y ← ···a ← y + 2b ← 0while(x < a)if (y < x)x ← y + 1y ← b × 2elsex ← y + 2y ← a ÷ 2;w ← x + 2z ← y × ay ← y + 1n FIGURE 5.13 Code Fragment for Exercise 4.L01: addra ,rbr1L05: addr9 ,rbaddrc ,rdr2addra ,rbr3addrc ,rdr4i2irar5addr13 ,rbL02,L04multIr12 ,17⇒⇒addr1 ,r2⇒addra ,rb⇒cmp LT r1 ,r2⇒cbrr5→L02: addra ,rb⇒multI r6 ,17⇒jumpI→L03: addra , rb ⇒multI r22 ,17 ⇒jumpI→L04: addrc ,rd⇒i2ira⇒cmp LT r9 ,rd⇒cbrr10→r6r7jumpIL06: addr1 ,r2L03i2ir2r22i2ir1r23addr17 ,r18L07addr18 ,r17r8multIr1 ,17r9r10jumpI⇒⇒⇒⇒⇒⇒→⇒⇒⇒⇒⇒⇒→r11r12r13r13r14r15L03r16r17r18r19r20r21L03L07: nopL05,L06n FIGURE 5.14 Code Fragment for Exercise 7.8.
Consider the three c procedures shown in Figure 5.15.a. Suppose a compiler uses a register-to-register memory model.Which variables in procedures A, B, and C would the compiler beforced to store in memory? Justify your answers.b. Suppose a compiler uses a memory-to-memory model. Considerthe execution of the two statements that are in the if clause of theExercises 267static int max = 0;void A(int b, int e){int B(int k){int x, y;int a, c, d, p;x = pow(2, k);a = B(b);y = x * 5;return y;if (b > 100) {c = a + b;d = c * 5 + e;}elsec = a * b;*p = c;C(&p);}}void C(int *p){if (*p > max)max = *p;}n FIGURE 5.15 Code for Exercise 8.if-else construct.
If the compiler has two registers available atthat point in the computation, how many loads and stores would thecompiler need to issue in order to load values in registers and storethem back to memory during execution of those two statements?What if the compiler has three registers available?9. In fortran, two variables can be forced to begin at the same storagelocation with an equivalence statement. For example, the followingstatement forces a and b to share storage:equivalence (a,b)Can the compiler keep a local variable in a register throughout theprocedure if that variable appears in an equivalence statement? Justifyyour answer.10. Some part of the compiler must be responsible for entering eachidentifier into the symbol table.a. Should the scanner or the parser enter identifiers into the symboltable? Each has an opportunity to do so.b. Is there an interaction between this issue, declare-before-use rules,and disambiguation of subscripts from function calls in a languagewith the FORTRAN 77 ambiguity?11.
The compiler must store information in the ir version of the programthat allows it to get back to the symbol table entry for each name.Among the options open to the compiler writer are pointers to theSection 5.5268 CHAPTER 5 Intermediate Representations1234567891011121314151617procedure maininteger a, b, c;procedure f1(w,x);integer a,x,y;call f2(w,x);end;procedure f2(y,z)integer a,y,z;procedure f3(m,n)integer b, m, n;c = a * b * m * n;end;call f3(c,z);end;...call f1(a,b);end;n FIGURE 5.16 Program for Exercise 12.original character strings and subscripts into the symbol table. Ofcourse, the clever implementor may discover other options.What are the advantages and disadvantages of each of theserepresentations for a name? How would you represent the name?12.
You are writing a compiler for a simple lexically-scoped language.Consider the example program shown in Figure 5.16.a. Draw the symbol table and its contents at line 11.b. What actions are required for symbol table management when theparser enters a new procedure and when it exits a procedure?13. The most common implementation technique for a symbol table usesa hash table, where insertion and deletion are expected to have O(1)cost.a. What is the worst-case cost for insertion and for deletion in a hashtable?b.
Suggest an alternative implementation scheme that guaranteesO(1) insertion and deletion.Chapter6The Procedure AbstractionnCHAPTER OVERVIEWProcedures play a critical role in the development of software systems.They provide abstractions for control flow and naming. They provide basicinformation hiding. They are the building block on which systems provideinterfaces.
They are one of the principal forms of abstraction in Algol-likelanguages; object-oriented languages rely on procedures to implement theirmethods or code members.This chapter provides an in-depth look at the implementation of proceduresand procedure calls, from the perspective of a compiler writer.
Along theway, it highlights the implementation similarities and differences betweenAlgol-like languages and object-oriented languages.Keywords: Procedure Calls, Parameter Binding, Linkage Conventions6.1 INTRODUCTIONThe procedure is one of the central abstractions in most modern programming languages.
Procedures create a controlled execution environment;each procedure has its own private named storage. Procedures help defineinterfaces between system components; cross-component interactions aretypically structured through procedure calls. Finally, procedures are the basicunit of work for most compilers. A typical compiler processes a collection ofprocedures and produces code for them that will link and execute correctlywith other collections of compiled procedures.This latter feature, often called separate compilation, allows us to build largesoftware systems. If the compiler needed the entire text of a program for eachcompilation, large software systems would be untenable. Imagine recompiling a multimillion line application for each editing change made duringEngineering a Compiler.
DOI: 10.1016/B978-0-12-088478-0.00006-2c 2012, Elsevier Inc. All rights reserved.Copyright 269270 CHAPTER 6 The Procedure Abstractiondevelopment! Thus, procedures play as critical a role in system design andengineering as they do in language design and compiler implementation.This chapter focuses on how compilers implement the procedure abstraction.Conceptual RoadmapTo translate a source-language program into executable code, the compilermust map all of the source-language constructs that the program uses intooperations and data structures on the target processor.
The compiler needs astrategy for each of the abstractions supported by the source language. Thesestrategies include both algorithms and data structures that are embedded intothe executable code. These runtime algorithms and data structures combineto implement the behavior dictated by the abstraction. These runtime strategies also require support at compile time in the form of algorithms and datastructures that run inside the compiler.This chapter explains the techniques used to implement procedures andprocedure calls. Specifically, it examines the implementation of control,of naming, and of the call interface.
These abstractions encapsulate manyof the features that make programming languages usable and that enableconstruction of large-scale systems.OverviewCalleeIn a procedure call, we refer to the procedure thatis invoked as the callee.CallerIn a procedure call, we refer to the callingprocedure as the caller.The procedure is one of the central abstractions that underlie most modernprogramming languages. Procedures create a controlled execution environment. Each procedure has its own private named storage.
Statementsexecuted inside the procedure can access the private, or local, variables inthat private storage. A procedure executes when it is invoked, or called, byanother procedure (or the operating system). The callee may return a valueto its caller, in which case the procedure is termed a function. This interfacebetween procedures lets programmers develop and test parts of a programin isolation; the separation between procedures provides some insulationagainst problems in other procedures.Procedures play an important role in the way that programmers develop software and that compilers translate programs.
Three critical abstractions thatprocedures provide allow the construction of nontrivial programs.1. Procedure Call Abstraction Procedural languages support anabstraction for procedure calls. Each language has a standardmechanism to invoke a procedure and map a set of arguments, orparameters, from the caller’s name space to the callee’s name space.This abstraction typically includes a mechanism to return control to the6.1 Introduction 271caller and continue execution at the pointimmediately after the call.Most languages allow a procedure to return one or more values to thecaller. The use of standard linkage conventions, sometimes referred toas calling sequences, lets the programmer invoke code written andcompiled by other people and at other times; it lets the applicationinvoke library routines and system services.2.
Name Space In most languages, each procedure creates a new andprotected name space. The programmer can declare new names, such asvariables and labels, without concern for the surrounding context. Insidethe procedure, those local declarations take precedence over any earlierdeclarations for the same names. The programmer can create parametersfor the procedure that allow the caller to map values and variables in thecaller’s name space into formal parameters in the callee’s name space.Because the procedure has a known and separate name space, it canfunction correctly and consistently when called from different contexts.Executing a call instantiates the callee’s name space.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
