山东大学编译原理Chapter7-RuntimeEnvironments

1、Chapter 7 Runtime Environments一个程序要运行，至少应有这样两个存储空间：(1) 代码空间这是经翻译后生成的目标代码的存储区域，线性存放着目标指令序列。对三地址代码来说，当前执行的指令位置由指令指针ip指示。因此，只要将ip指向程序的第一个语句，程序便处于开始执行的状态，以后每执行一个语句，ip便加4(我们约定，三地址代码的每个语句占4个字节)，指向下个语句。要改变程序控制顺序，只要将转向点赋给ip即可。(2) 数据空间每个程序都定义一定数量的各种类型的变量和常数，翻译程序必须为之分配相应的存储空间。初等类型的数据，如逻辑、整型、实型变量，通常以存储器的基本存储单元

2、如字节、字、双字来存储。Chapter 7 Runtime Environments 7.1 Source Language IssuesProgram vs program execution A program consists of several procedures (functions) An execution of a program is called as a process An execution of a program would cause the activation of the related procedures A name (e.g, a variab

3、le name)in a procedure would be related to different data objectsNotes: An activation may manipulate data objects allocated for its use.Chapter 7 Runtime Environments 7.1 Source Language Issues Allocation and de-allocation of data objects Managed by the run-time support package Allocation of a data

4、object is just to allocate storage space to the data object relating to the name in the procedure Notes: The representation of a data object at run time is determined by its type.Chapter 7 Runtime Environments 7.1 Source Language Issues A procedure is activated when called The lifetime of an activat

5、ion of a procedure is the sequence of steps between the first and last steps in the execution of the procedure body A procedure is recursive if a new activation can begin before an earlier activation of the same procedure has endedChapter 7 Runtime Environments 7.1 Source Language Issues3.Activation

6、 Trees A tree to depict the control flow enters and leaves activation of a procedure f(4) f(3) f(2) f(2) f(1) f(1) f(0) f(1) f(0) Enter f(4)Enter f(3)Enter f(2)Enter f(1)Leave f(1)Enter f(0)Leave f(0)Leave f(2)Enter f(1)Leave f(1)Leave f(3)Enter f(2)Enter f(1)Leave f(1)Enter f(0)Leave f(0)Leave f(2)

7、Leave f(4)Procedure Activations: Exampleprogram sort(input, output) var a : array 0.10 of integer; procedure readarray; var i : integer; begin for i := 1 to 9 do read(ai) end; function partition(y, z : integer) : integer var i, j, x, v : integer; begin end procedure quicksort(m, n : integer); var i

8、: integer; begin if (n m) then begin i := partition(m, n); quicksort(m, i - 1); quicksort(i + 1, n) end end; begin a0 := -9999; a10 := 9999; readarray; quicksort(1, 9) end.Activations:begin sort enter readarray leave readarray enter quicksort(1,9) enter partition(1,9) leave partition(1,9) enter quic

9、ksort(1,3) leave quicksort(1,3) enter quicksort(5,9) leave quicksort(5,9) leave quicksort(1,9)end sort.Activation Trees: Examplesq(1,9)q(1,3)p(1,3)q(1,0) q(2,3)q(2,1)p(2,3)q(3,3)p(1,9)rq(5,9)p(5,9)q(5,5) q(7,9)q(7,7)p(7,9)q(9,9)Activation tree for the sort programNote: also referred to as the dynami

10、c call graphChapter 7 Runtime Environments 7.1 Source Language Issues4.Control stacks A stack to keep track of live procedure activationsChapter 7 Runtime Environments 7.1 Source Language Issues Control Stacksq(1,9)q(1,3)p(1,3)q(1,0) q(2,3)p(1,9)rActivations:begin sort enter readarray leave readarra

11、y enter quicksort(1,9) enter partition(1,9) leave partition(1,9) enter quicksort(1,3) enter partition(1,3) leave partition(1,3) enter quicksort(1,0) leave quicksort(1,0) enter quicksort(2,3) Controlstack:Activation tree:sq(1,9)q(1,3)q(2,3)Scope Rules Environment determines name-to-object bindings: w

12、hich objects are in scope?program prg; var y : real;function x(a : real) : real; begin end;procedure p; var x : integer; begin x := 1; end;begin y := x(0.0); end.Variable x locally declared in pA function xChapter 7 Runtime Environments 7.1 Source Language IssuesBindings of Names When an environment

13、 associates storage location s with a name x, we say that x is bound to s; the association itself is referred to as a binding of x. Notes: 1)Even each name is declared once in a program, the same name may denote different object at run time 2)The “ data object” corresponds to a storage location that

14、 can hold valuesChapter 7 Runtime EnvironmentsBindings of NamesNotes: 3)In programming language semantics, the term “environment” refers to a function that maps a name to a storage location, and term “state” refers to a function that maps a storage location to the value held there. environment state

15、 name storage value Chapter 7 Runtime Environments5.Bindings of NamesNotes: 4)Environments and states are different; an assignment changes the state, but not the environment 5)If x is not of a basic type, the storage s for x may be a collection of memory words 6)A binding is the dynamic counterpart

16、of a declarationChapter 7 Runtime Environments6.Factors that determines the run time environment of a program Recursive definition Local name storage space allocation strategy global name storage space allocation strategy Parameter passing mechanism A function is whether allowed to be a parameter of

17、 or return value of a functionChapter 7 Runtime Environments 7.2Storage organization1.Subdivision of Runtime MemoryTypical subdivision of runtime memory into code and data areascodeStatic datastackheapThe generated target code;Data objects;A counterpart of the control stack to keep track of procedur

18、e activations Chapter 7 Runtime Environments 7.2Storage organization2.Activation Records/Frames1) Definition A contiguous block of storage that stores information needed by a single execution of a procedureChapter 7 Runtime Environments 7.2Storage organization2.Activation Records2) A general activat

19、ion recordReturned valueActual parametersOptional control linkOptional access linkSaved machine statusLocal datatemporariesControl LinksfpspControl linkStackgrowthCallees activation recordCallers activation recordThe control link is the old value of the fp活动记录活动记录（1）临时数据域临时数据域 如计算表达式出现的中间结果，若如计算表达式出

20、现的中间结果，若寄存器不足以存放所有这些中间结果时，可以把它寄存器不足以存放所有这些中间结果时，可以把它们存放在临时数据域中。们存放在临时数据域中。（2）局部数据域局部数据域 保存局部于过程执行的数据，这保存局部于过程执行的数据，这个域的布局在下面讨论。个域的布局在下面讨论。（3）机器状态域机器状态域 保存刚好在过程调用前的机器状保存刚好在过程调用前的机器状态信息，包括程序计数器的值和控制从这个过程返态信息，包括程序计数器的值和控制从这个过程返回时必须恢复的机器寄存器的值。回时必须恢复的机器寄存器的值。（4）访问链访问链 Pascal语言需要用访问链来访问非局语言需要用访问链来访问非局部数据，

21、我们在部数据，我们在6.3节介绍。像节介绍。像Fortran和和C这样的语这样的语言不需要访问链，因为全局数据保存在固定的地方。言不需要访问链，因为全局数据保存在固定的地方。访问链也称为静态链。访问链也称为静态链。活动记录活动记录（5）控制链控制链 用来指向调用者的活动记录。用来指向调用者的活动记录。控制链也称为动态链。控制链也称为动态链。（6）参数域参数域 用于存放调用过程提供的实在用于存放调用过程提供的实在参数。为提高效率，实际上常常用寄存器传参数。为提高效率，实际上常常用寄存器传递参数。递参数。（7）返回值域返回值域 用于存放被调用过程返回给用于存放被调用过程返回给调用过程的值。为提高效

22、率，这个值也常常调用过程的值。为提高效率，这个值也常常用寄存器返回。用寄存器返回。 编译时局部数据的安排编译时局部数据的安排 字节是可编址内存的最小单位。字节是可编址内存的最小单位。 变量所需的存储空间可以根据其类型而静态变量所需的存储空间可以根据其类型而静态确定。确定。 一个过程所声明的局部变量，按这些变量声一个过程所声明的局部变量，按这些变量声明时出现的次序，在局部数据域中依次分配明时出现的次序，在局部数据域中依次分配空间。空间。 局部数据的地址可以用相对于某个位置的地局部数据的地址可以用相对于某个位置的地址来表示。址来表示。 数据对象的存储安排还有一个对齐问题。数据对象的存储安排还有一个

23、对齐问题。Chapter 7 Runtime Environments 7.3 Storage allocation strategies1.Storage allocation strategies Static allocation Lays out storage for all data objects at compile time. Stack allocation Manages the run-time storage as a stack. Heap allocation Allocates and de-allocates storage as needed at run

24、time from a heap.Chapter 7 Runtime Environments 7.3 Storage allocation strategies2.Static allocation The size of a data object and constraints on its position in memory must be known at compile time. Recursive procedures are restricted. Data structures cannot be created dynamically. Fortran permits

25、static storage allocationStatic allocation(1)(1)program consumeprogram consume(2)(2)charactercharacter 50 buffer50 buffer(3)(3)integer nextinteger next(4)(4)character c, producecharacter c, produce(5)(5)data next /1/, buffer / /data next /1/, buffer / /(6) 6(6) 6c = produce ()c = produce ()(7)(7)buf

26、fer(next : next) = cbuffer(next : next) = c(8)(8)next = next + 1next = next + 1(9)(9)if (c .ne. ) goto 6if (c .ne. ) goto 6(10)(10)write(write( , (A) buffer, (A) buffer(11)(11)endendStatic allocation(12)(12)character function produce()character function produce()(13)(13)charactercharacter 80 buffer8

27、0 buffer(14)(14)integer nextinteger next(15)(15)save buffer, nextsave buffer, next(16)(16)data next /81/data next /81/(17)(17)if (next .gt. 80) thenif (next .gt. 80) then(18)(18)read (read ( , (A) buffer, (A) buffer(19)(19)next = 1next = 1(20)(20)end ifend if(21)(21)produce = buffer(next : next)prod

28、uce = buffer(next : next)(22)(22)next = next + 1next = next + 1(23)(23) endendStatic allocationFortran语言被设计成允许静态存储分配语言被设计成允许静态存储分配consume的代码的代码produce的代码的代码character 50 bufferinteger nextcharacter ccharacter 80 bufferinteger nextproduce的活动记录的活动记录consume的活动记录的活动记录静态数据静态数据代码代码Chapter 7 Runtime Environ

29、ments 7.3 Storage allocation strategies3.Heap allocation A separate area of run-time memory, called a heap. Heap allocation parcels out pieces of contiguous storage, as needed for activation records or other objects. Pieces may be de-allocated in any order.Chapter 7 Runtime Environments 7.3 Storage

30、allocation strategies4. Stack allocation1)Main idea Based on the idea of a control stack; storage is organized as a stack, and activation records are pushed and popped as activations begin and end, respectively. Storage for the locals in each call of a procedure is contained in the activation record

31、 for that call. Locals are bound to fresh storage in each activationChapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation2)Calling sequences A call sequence allocates an activation record and enters information into its fields A return sequence restores the state of the

32、 machine so the calling procedure can continue execution.e.g. the calling sequence is like the following:main () q( ); p( ) q( ) p( ); Activation record for mainActivation record for QActivation record for PTOPTop-SPChapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation2

33、)Calling sequencesSteps: (1)The caller evaluates actual parameters.(2)The caller stores a return address and the old value of top-sp into the callees activation record.(3)The callee saves register values and other status information(4)the callee initializes its local data and begins execution.Chapte

34、r 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation2)calling sequencesA possible return sequence : (1)The callee places a return value next to the activation record of the caller (2)Using the information in the status field, the callee restores top-sp and other registers an

35、d branches to a return address in the callers code. (3)Although top-sp has been decremented, the caller can copy the returned value into its own activation record and use it to evaluate an expression.Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation3)Stack allocatio

36、n for non-nested procedure Stack allocation for C When entering a procedure, the activation record of the procedure is set up on the top of the stack Initially, put the global(static) variables and the activation record of the Main functionChapter 7 Runtime Environments 7.3 Storage allocation strate

37、gies4. Stack allocation3)Stack allocation for non-nested procedureMain AR Q ARP ARTOPSPglobal VarChapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation3)Stack allocation for non-nested procedureCallers SPCalling Return addressAmount of parametersFormal parametersLocal da

38、ta Array dataTemporariesReturned valueChapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation3)Stack allocation for non-nested procedure #include int i,j; void main() int k,l; cinl; k=p(l); coutk; Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack al

39、location3)Stack allocation for non-nested procedure #include int i,j; int p(int m) int t; if (m=0 | m=1) return(1); else t=m*p(m-1); return(t); Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)Stack allocation for nested procedures(1) the nesting of procedure defi

40、nitions in the Pascal programP0P1P2Call P2Call P1P0P1P2Call P2Call P1Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)Stack allocation for nested procedures(2) nesting depthi1P0Pi-1Pii0Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack alloca

41、tion4)Stack allocation for nested procedures(3) access linksP0P1P2Call P2Call P1TOPTop-SPP2P1P0Access linkAccess linkAccess linkChapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)Stack allocation for nested procedures(3) access linksTOPTop-SPP2P1P0Access linkAccess

42、linkAccess linkP0P1P2Call P2Call P1Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)Stack allocation for nested procedures(4) displays Faster access to global than with access links can be obtained using an array d of pointers to activation records, called a displ

43、ay.Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)Stack allocation for nested procedures(4) displays Suppose control is in an activation of a procedure pj at nesting depth j, then the display of activation of pj is:j1Sp for p0Sp for pj-1Sp for pjj0dj+1Chapter 7

44、Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)Stack allocation for nested procedures(4) displays When a new activation record for a procedure at nesting depth i is setup, we A) save the value of di in the new activation record; B) set di to point to the new activation re

45、cord.Chapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)Stack allocation for nested procedures(5) non-displays non-display of current procedure =non-display of caller+start address of current local activation recordChapter 7 Runtime Environments 7.3 Storage allocati

46、on strategies4. Stack allocation4)Stack allocation for nested proceduresCallers SPCalling Return addressAmount of parametersFormal parametersLocal data Array dataTemporariesReturned valueLocal displayglobal displayChapter 7 Runtime Environments 7.3 Storage allocation strategies4. Stack allocation4)S

47、tack allocation for nested proceduresProgram M; var A,B:integer function F(N:integer):integer; if N=2 then teturn(N) else return (N*F(N-1); begin read(A); /*Let A=5*/ B:=F(A); write (B); end.K+11K+6Local D+12Returned value from F+13K+6(SP1)+14Returned address+15K+11Global D+161Number of P+174Formal

48、P N+18K+19K+14Loc D+20Returned value from F+21Global D4K5K+1D+2A+3B+4Returned value from F+5K(SP0)+6Returned address+7K+2+81Number of P+9Formal P N+10Chapter 7 Runtime Environments 7.4 Access to Nonlocal Names语言的作用域规则规定了如何处理非局部名字语言的作用域规则规定了如何处理非局部名字的访问。一种常用的规则叫做的访问。一种常用的规则叫做词法作用域词法作用域或或静态作用域静态作用域规则，

49、它仅根据程序正文静态地规则，它仅根据程序正文静态地确定用于名字的声明。许多语言，如确定用于名字的声明。许多语言，如PascalPascal，C C和和AdaAda，都使用静态作用域规则。我们首先，都使用静态作用域规则。我们首先考虑考虑C C语言那样的非局部名字。由于语言那样的非局部名字。由于C C语言不语言不允许嵌套的过程声明，因此所有的非局部名允许嵌套的过程声明，因此所有的非局部名字都可以静态地绑定到所分配的存储单元。字都可以静态地绑定到所分配的存储单元。 Chapter 7 Runtime Environments 7.4 Access to Nonlocal Names7.4.1 程序块

50、程序块有局部数据的语句有局部数据的语句7.4.2 无过程嵌套的静态作用域无过程嵌套的静态作用域 过程体中的非局部引用可以直接使用静态确过程体中的非局部引用可以直接使用静态确定的地址定的地址 局部变量在栈顶的活动记录中，可以通过局部变量在栈顶的活动记录中，可以通过basebase_ _spsp指针来访问指针来访问 无须深入栈中取数据，无须访问链无须深入栈中取数据，无须访问链 过程可以作为参数来传递，也可以作为结果过程可以作为参数来传递，也可以作为结果来返回来返回7.4 Access to Nonlocal NamesC语言的函数声明不能嵌套，函数不论在什语言的函数声明不能嵌套，函数不论在什么情况

51、下激活，要访问的数据分成两种情况么情况下激活，要访问的数据分成两种情况: : 非静态局部变量（包括形式参数），它们分非静态局部变量（包括形式参数），它们分配在活动记录栈顶的那个活动记录中配在活动记录栈顶的那个活动记录中 外部变量（包括定义在其它源文件中的外部外部变量（包括定义在其它源文件中的外部变量）和静态的局部变量，它们都分配在静变量）和静态的局部变量，它们都分配在静态数据区态数据区 全局数据说明全局数据说明Main( ) Main中的数据说明中的数据说明 void R( ) R中的数据说明中的数据说明void Q( ) Q中的数据说明中的数据说明 主程序主程序过程过程Q 过程过程RQ的活动

52、记录的活动记录主程序活动记录主程序活动记录TOPR的活动记录的活动记录SP参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元全局数据区全局数据区 每个过程的活动记录内容如图每个过程的活动记录内容如图:对任何局部变量对任何局部变量X的的引用可表示为变址访引用可表示为变址访问问: dxSP dx: 变量变量X相对于活相对于活动记录起点的地址，动记录起点的地址，在编译时可确定。在编译时可确定。参数个数参数个数返回地址返回地址形式单元形式单元临时单元临时单元内情向量内情向量局部变量局部变量SP 012老老SPTOP 9.4.2 C的活动记录的活动记

53、录 过程调用的四元式序列过程调用的四元式序列:par T1par T2 par Tncall P，n9.4.2 C的过程调用、过程进入、数组空的过程调用、过程进入、数组空间分配和过程返回间分配和过程返回 1) 每个每个par Ti(i=1,2,n)可直接翻译成如下指令可直接翻译成如下指令:(i+3)TOP:= Ti (传值传值)(i+3)TOP:=addr(Ti) (传地址传地址)2) call P，n 被翻译成被翻译成:1TOP:=SP (保护现行保护现行SP)3TOP:=n (传递参数个数传递参数个数)JSR P (转子指令转子指令)参数个数参数个数返回地址返回地址形式单元形式单元内情向量

54、内情向量局部变量局部变量老老SP临时单元临时单元对于对于par和和call产生的目标代码如下产生的目标代码如下:TOP SP 调用过程的调用过程的活动记录活动记录形式单元形式单元老老SP参数个数参数个数3) 转进过程转进过程P后，首先应执行下述指令后，首先应执行下述指令:SP:=TOP+1 (定义新的定义新的SP)1SP:=返回地址返回地址 (保护返回地址保护返回地址)TOP:=TOP+L (新新TOP) L：过程过程P的活动记录所需单元数，的活动记录所需单元数， 在编译时可确定。在编译时可确定。 参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元

55、临时单元TOP 调用过程的活动记录调用过程的活动记录返回地址返回地址TOPSP4) 过程返回时，应执行下列指令过程返回时，应执行下列指令:TOP:=SP-1 (恢复调用前恢复调用前TOP)SP:=0SP (恢复调用前恢复调用前SP)X:=2TOP (把返回地址取到把返回地址取到X中中)UJ 0X (按按X返回返回)参数个数参数个数返回地址返回地址形式单元形式单元内情向量内情向量局部变量局部变量老老SP临时单元临时单元调用过程的活动记录调用过程的活动记录TOPSPSPTOP7.4.3 有过程嵌套的静态作用域有过程嵌套的静态作用域(1)program sort(input, output);(2)

56、var a: array0.10 of integer;(3)x: integer;(4)procedure readarray;(5)var i: integer;(6)begin a endreadarray;(7)procedure exchange(i, j : integer);(8)begin(9)x := ai; ai := aj; aj := x(10)endexchange;7.4.3 有过程嵌套的静态作用域有过程嵌套的静态作用域(11)procedurequicksort(m,n: integer);(12)var k, v: integer;(13)function pa

57、rtition(y, z: integer): integer;(14)var i, j: integer;(15)begin a (16) v ( 1 7 ) exchange(i, j); (18)endpartition;(19)begin endquicksort;(20)begin endsort.7.4.3 有过程嵌套的静态作用域有过程嵌套的静态作用域7.4.3.1 7.4.3.1 过程过程嵌套深度嵌套深度sort1readarray2exchange2quicksort2partition3变量的嵌套深度：它的声明所在过程的嵌套深变量的嵌套深度：它的声明所在过程的嵌套深度作为该名

58、字的嵌套深度度作为该名字的嵌套深度7.4.3 有过程嵌套的静态作用域有过程嵌套的静态作用域7.4.3.2 7.4.3.2 寻找非局部名字存储单元的访问链寻找非局部名字存储单元的访问链 sa, xq (1, 9)k, v访问链访问链sa, xq (1, 3)k, v访问链访问链q (1, 9)k, v访问链访问链sa, xq (1, 3)k, v访问链访问链q (1, 9)k, v访问链访问链p (1, 3)i, j访问链访问链e (1, 3)访问链访问链sa, xq (1, 3)k, v访问链访问链q (1, 9)k, v访问链访问链p (1, 3)i, j访问链访问链7.4.3.2 7.4.

59、3.2 访问链访问链假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用嵌套深度为，它引用嵌套深度为na的变量的变量a，na np。如何访问。如何访问a的存储单元？的存储单元？ 从栈顶的活动记录开始，追踪访问链从栈顶的活动记录开始，追踪访问链np na次。次。 到达到达a的声明所在过程的活动记录。的声明所在过程的活动记录。 访问链的追踪用间接操作就可完成。访问链的追踪用间接操作就可完成。7.4.3.2 7.4.3.2 访问链访问链访问非局部名字的存储单元访问非局部名字的存储单元 sa, xq (1, 9)k, v访问链访问链sa, xq (1, 3)k, v访问链访问链q (1, 9)k,

60、v访问链访问链sa, xq (1, 3)k, v访问链访问链q (1, 9)k, v访问链访问链p (1, 3)i, j访问链访问链e (1, 3)访问链访问链sa, xq (1, 3)k, v访问链访问链q (1, 9)k, v访问链访问链p (1, 3)i, j访问链访问链sort readarray exchange quicksort partition7.4.3.2 7.4.3.2 访问链访问链过程过程p对变量对变量a访问时，访问时，a的地址由下面的二元的地址由下面的二元组表示：组表示：（np na，a在活动记录中的偏移）在活动记录中的偏移）7.4.3.2 7.4.3.2 访问链访问