上海交通大学：《编译原理》教学资源_第六周讲义_Run-Time Environments

Run-Time Environments CS308 Compiler Theory

Run-Time Environments CS308 Compiler Theory 1

Run-Time Environments How do we allocate the space for the generated target code and the data object of our source programs? The places of the data objects that can be determined at compile time will be allocated statically. But the places for the some of data objects will be allocated at run-time. The allocation of de-allocation of the data objects is managed by the run-time support package. run-time support package is loaded together with the generate target code. the structure of the run-time support package depends on the semantics of the programming language (especially the semantics of procedures in that language). Each execution of a procedure is called as activation of that procedure. CS308 Compiler Theory 2

Run-Time Environments • How do we allocate the space for the generated target code and the data obj f ect o f our source programs? • The places of the data objects that can be determined at compile time will be all t d t ti ll lloca t e d s t atically. • But the places for the some of data objects will be allocated at run-time. • Th ll ti f d The allocation o f de-all ti f th d t bj t i d b th llocation o f the d a ta objec ts is manage d by the run-time support package. – run -time support package is loaded together with the generate target code time support package is loaded together with the generate target code. – the structure of the run-time support package depends on the semantics of the programming language (especially the semantics of procedures in that language). • E h i f d i ll d Eac h execut ion o f a proce dure is call e d as activation ofh d t at proce dure. CS308 Compiler Theory 2

Procedure Activations An execution of a procedure starts at the beginning of the procedure body; When the procedure is completed,it returns the control to the point immediately after the place where that procedure is called Each execution of a procedure is called as its activation. Lifetime of an activation of a procedure is the sequence of the steps between the first and the last steps in the execution of that procedure (including the other procedures called by that procedure). If a and b are procedure activations,then their lifetimes are either non- overlapping or are nested. If a procedure is recursive,a new activation can begin before an earlier activation of the same procedure has ended. CS308 Compiler Theory 3

Procedure Activations • An execution of a procedure starts at the beginning of the procedure b do dy; • When the procedure is completed, it returns the control to the point i di t l ft th l h th t d i ll d immedi a t e ly after the p lace w here th a t proce dure is call e d. • Each execution of a procedure is called as its activation. • Lif i et ime of ti ti f d i th f th t f an activation o f a proce dure is the sequence o f the s teps between the first and the last steps in the execution of that procedure (including the other procedures called by that procedure) (including the other procedures called by that procedure). • If a and b are procedure activations, then their lifetimes are either non￾overlapping rlappin g or are nested. • If a procedure is recursive, a new activation can begin before an earlier activation of the same procedure has ended. CS308 Compiler Theory 3

Activation tree We can use a tree (called activation tree)to show the way control enters and leaves activations. In an activation tree: -Each node represents an activation of a procedure. The root represents the activation of the main program. The node a is a parent of the node b iff the control flows from a to b. -The node a is left toto the node b iff the lifetime of a occurs before the lifetime of b. CS308 Compiler Theory 4

Activation Tree • We can use a tree (called activation tree) to show the way control enters andl i i eaves activations. • In an activation tree: – Each node represents an activation of a procedure. – The root represents the activation of the main program. – The node a is a parent of the node b iff the control flows from a to b. – The node a is left to to the node b iff the lifetime of a occurs before the lifetime of b. CS308 Compiler Theory 4

Activation Tree (cont.) program main; enter main procedure s; enter p begin ..end; enter q procedure p; _exit q procedure q; Center s begin ..end; -exit s begin q;s;end; exit p begin p;s;end; enter s -exit s exit main A Nested Structure CS308 Compiler Theory

Activation Tree (cont.) program main; enter main procedure s; enter p begin ... end; enter q proce dure p; exit q procedure q; enter s begin end; begin ... end; exit s begin q; s; end; exit p begin p; s; end; begin p; s; end; enter s enter s exit s exit main A Nested Structure CS308 Compiler Theory 5

Activation Tree (cont.) main p S q S CS308 Compiler Theory 6

Activation Tree (cont.) main p s q s CS308 Compiler Theory 6

Control Stack The flow of the control in a program corresponds to a depth-first traversal of the activation tree that: starts at the root. visits a node before its children,and recursively visits children at each node an a left-to-right order A stack (called control stack)can be used to keep track of live procedure activations. An activation record is pushed onto the control stack as the activation starts. That activation record is popped when that activation ends. When node n is at the top of the control stack,the stack contains the nodes along the path from n to the root. CS308 Compiler Theory 7

Control Stack • The flow of the control in a program corresponds to a depth-first traversal fh i i h l of the activation tree that: – starts at the root, – visits a node before its children, and – recursively visits children at each node an a left-to-right order. • A stack (called control stack) can be used to keep track of live procedure activations. – A i i di h d h l k h An activation record is pushed onto the control stack as the activation starts. – Th t ti ti d i d h th t ti ti d That activation record is popped when that activation ends. • When node n is at the top of the control stack, the stack contains the nodes along the path from n to the root CS308 Compiler Theory 7 nodes along the path from n to the root

Variable scopes The same variable name can be used in the different parts of the program. The scope rules of the language determine which declaration of a name applies when the name appears in the program. An occurrence of a variable (a name)is: local:If that occurrence is in the same procedure in which that name is declared. non-local:Otherwise (ie.it is declared outside of that procedure) procedure p; var b:real; procedure p; var a:integer; a is local begin a :1;b 2;end; b is non-local begin ..end; CS308 Compiler Theory 8

Variable Scopes • The same variable name can be used in the different parts of the program. • The scope rules of the language determine which declaration of a name applies when the name appears in the program. applies when the name appears in the program. • An occurrence of a variable (a name) is: – local: If that occurrence is in the same procedure in which that name is declared. – non-local: Otherwise (ie. it is declared outside of that procedure) procedure p; procedure p; var b:real; procedure p; var a: integer; var a: integer; a is local a is local begin a := 1; b := 2; end; b is non-local begin ... end; CS308 Compiler Theory 8

Run-Time Storage Organization Code Memory locations for code are determined at compile time. Static Data Locations of static data can also be determined at compile time. Stack Data objects allocated at run-time. (Activation Records) Other dynamically allocated data Heap objects at run-time.(For example, malloc area in C). CS308 Compiler Theory 9

Run-Time Storage Organization Code Memory locations for code are determined at compile time. Static Data determined at compile time. Locations of static data can also be Stack determined at compile time. Data objects allocated at r n Data objects allocated at ru n -time. (Activation Records) Other dynamically allocated data Heap objects at run-time. (For example, malloc area in C). CS308 Compiler Theory 9

Activation Records Information needed by a single execution of a procedure is managed using a contiguous block of storage called activation record. An activation record is allocated when a procedure is entered,and it is de-allocated when that procedure exited. 。6 Size of each field can be determined at compile time(Although actual location of the activation record is determined at run-time). -Except that if the procedure has a local variable and its size depends on a parameter,its size is determined at the run time. CS308 Compiler Theory 10

Activation Records • Information needed by a single execution of a procedure is managed usi i bl k f ll d ing a contiguous block of storage called activation record. • An activation record is allocated when a procedure is entered, and it is de-all t d h th t d it d llocated when that procedure exited. • Size of each field can be determined at compile time (Although actual location of the activation record is determined at run location of the activation record is determined at run-time). – Except that if the procedure has a local variable and its size depends on a parameter its size is determined at the run time on a parameter, its size is determined at the run time. CS308 Compiler Theory 10