K. Cooper, L. Torczon - Engineering a Compiler (2011 - 2nd edition) (798440), страница 83
Текст из файла (страница 83)
Show the call tree and execution history for the following c program:int Sub(int i, int j) {return i - j;}int Mul(int i, int j) {return i * j;}int Delta(int a, int b, int c) {return Sub(Mul(b,b), Mul(Mul(4,a),c));}void main() {int a, b, c, delta;scanf("%d %d %d", &a, &b, &c);delta = Delta(a, b, c);if (delta == 0)puts("Two equal roots");else if (delta > 0)puts("Two different roots");elseputs("No root");}2. Show the call tree and execution history for the following c program:void Output(int n, int x) {printf("The value of %d! is %s.\n", n, x);}int Fat(int n) {int x;if (n > 1)x = n * Fat(n - 1);elsex = 1;Output(n, x);return x;}void main() {Fat(4);}Exercises 3253. Consider the following Pascal program, in which only procedure callsand variable declarations are shown:1234567891011121314151617181920212223242526272829303132333435program Main(input, output);var a, b, c : integer;procedure P4; forward;procedure P1;procedure P2;beginend;var b, d, f : integer;procedure P3;var a, b : integer;beginP2;end;beginP2;P4;P3;end;var d, e : integer;procedure P4;var a, c, g : integer;procedure P5;var c, d : integer;beginP1;end;var d : integer;beginP1;P5;end;beginP1;P4;end.a.
Construct a static coordinate table, similar to the one in Figure 6.3.b. Construct a graph to show the nesting relationships in the program.c. Construct a graph to show the calling relationships in the program.Section 6.3326 CHAPTER 6 The Procedure Abstraction4. Some programming languages allow the programmer to use functionsin the initialization of local variables but not in the initialization ofglobal variables.a. Is there an implementation rationale to explain this seeming quirkof the language definition?b.
What mechanisms would be needed to allow initialization of aglobal variable with the result of a function call?5. The compiler writer can optimize the allocation of ars in severalways. For example, the compiler might:a. Allocate ars for leaf procedures statically.b. Combine the ars for procedures that are always called together.(When α is called, it always calls β.)c.
Use an arena-style allocator in place of heap allocation of ars.For each scheme, consider the following questions:a. What fraction of the calls might benefit? In the best case? In theworst case?b. What is the impact on runtime space utilization?6. Draw the structures that the compiler would need to create to supportan object of type Dumbo, defined as follows:class Elephant {private int Length;private int Weight;static int type;public int GetLen();public int GetTyp();}class Dumbo extends Elephant {private int EarSize;private boolean Fly;public boolean CanFly();}7.
In a programming language with an open class structure, the numberof method invocations that need runtime name resolution, or dynamicdispatch, can be large. A method cache, as described in Section 6.3.4,can reduce the runtime cost of these lookups by short-circuiting them.As an alternative to a global method cache, the implementation mightmaintain a single entry method cache at each call site—an inlineExercises 3271234567891011121314151617procedure main;var a : array[1...3] of int;i : int;procedure p2(e : int);begine := e + 3;a[i] := 5;i := 2;e := e + 4;end;begina := [1, 10, 77];i := 1;p2(a[i]);for i := 1 to 3 doprint(a[i]);end.n FIGURE 6.13 Program for Problem 8.method cache that records record the address of the method mostrecently dispatched from that site, along with its class.Develop pseudocode to use and maintain such an inline method cache.Explain the initialization of the inline method caches and anymodifications to the general method lookup routine required tosupport inline method caches.8.
Consider the program written in Pascal-like pseudo code shown inFigure 6.13. Simulate its execution under call-by-value,call-by-reference, call-by-name, and call-by-value-result parameterbinding rules. Show the results of the print statements in each case.9. The possibility that two distinct variables refer to the same object(memory area) is considered undesirable in programming languages.Consider the following Pascal procedure, with parameters passed byreference:procedure mystery(var x, y : integer);beginx := x + y;y := x - y;x := x - y;end;Section 6.4328 CHAPTER 6 The Procedure Abstraction1234567891011121314151617181920212223242526program main(input, output);procedure P1( function g(b: integer): integer);var a: integer;begina := 3;writeln(g(2))Local Variablesend;Access Linkprocedure P2;var a: integer;ARPfunction F1(b: integer): integer;Return AddressArgument 1beginF1 := a + b···end;Argument nprocedure P3;var a:integer;(b) Activation Record Structurebegina := 7;ARPP1(F1)end;Access Link (0)Return Address (0)begina := 0;(c) Initial Activation RecordP3end;beginP2end.(a) Example Pascal Programn FIGURE 6.14 Program for Problem 10.If no overflow or underflow occurs during the arithmetic operations:a.
What result does mystery produce when it is called with twodistinct variables, a and b?b. What would be the expected result if mystery is invoked with asingle variable a passed to both parameters? What is the actualresult in this case?Section 6.510. Consider the Pascal program shown in Figure 6.14a.
Suppose that theimplementation uses ars as shown in Figure 6.14b. (Some fields havebeen omitted for simplicity.) The implementation stack allocatesthe ars, with the stack growing toward the top of the page. The arp isExercises 329the only pointer to the ar, so access links are previous values of thearp. Finally, Figure 6.14c shows the initial ar for a computation.For the example program in Figure 6.14a, draw the set of its ars justprior to the return from function F1.
Include all entries in the ars. Useline numbers for return addresses. Draw directed arcs for access links.Label the values of local variables and parameters. Label each ar withits procedure name.11. Assume that the compiler is capable of analyzing the code todetermine facts such as “from this point on, variable v is not usedagain in this procedure” or “variable v has its next use in line 11 ofthis procedure,” and that the compiler keeps all local variables inregisters for the following three procedures:procedure maininteger a, b, cb = a + c;c = f1(a,b);call print(c);end;procedure f1(integer x, y)integer v;v = x * y;call print(v);call f2(v);return -x;end;procedure f2(integer q)integer k, r;···k = q / r;end;a. Variable x in procedure f1 is live across two procedure calls. Forthe fastest execution of the compiled code, should the compilerkeep it in a caller-saves or callee-saves register? Justify youranswer.b.
Consider variables a and c in procedure main. Should the compilerkeep them in caller-saves or callee-saves registers, again assumingthat the compiler is trying to maximize the speed of the compiledcode? Justify your answer.330 CHAPTER 6 The Procedure Abstraction12. Consider the following Pascal program. Assume that the ars followthe same layout as in problem 10,with the same initial condition,except that the implementation uses a global display rather than accesslinks.123456789101112131415161718192021program main(input, output);var x : integer;a : float;procedure p1();var g:character;begin···end;procedure p2();var h:character;procedure p3();var h,i:integer;beginp1();end;beginp3();end;beginp2();endDraw the set of ars that are on the runtime stack when the programreaches line 7 in procedure p1.Chapter7Code ShapenCHAPTER OVERVIEWTo translate an application program, the compiler must map each sourcelanguage statement into a sequence of one or more operations in the targetmachine’s instruction set.
The compiler must chose among many alternativeways to implement each construct. Those choices have a strong and directimpact on the quality of the code that the compiler eventually produces.This chapter explores some of the implementation strategies that thecompiler can employ for a variety of common programming-languageconstructs.Keywords: Code Generation, Control Structures, Expression Evaluation7.1 INTRODUCTIONWhen the compiler translates application code into executable form, it facesmyriad choices about specific details, such as the organization of the computation and the location of data. Such decisions often affect the performanceof the resulting code. The compiler’s decisions are guided by informationthat it derives over the course of translation.
When information is discoveredin one pass and used in another, the compiler must record that informationfor its own later use.Often, compilers encode facts in the ir form of the program—facts that arehard to re-derive unless they are encoded. For example, the compiler mightgenerate the ir so that every scalar variable that can safely reside in a register is stored in a virtual register. In this scheme, the register allocator’s jobis to decide which virtual registers it should demote to memory.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
