Compiler Designing W06L1106

Stack Machines

  • Code generation model.
  • It only contains a stack. It takes an instruction I=F(a1,a2…an) pushes and pops from the stack according to the instruction. For example, 7+5 would be implemented as:
LET S be a stack
    when 7 is input then S → S.7
    when 5 is input then S → S.7.5
    for add operation 5 and 7 are popped out and 12 is pushed, S → S.12

instructions for the above:
     push 7
     push 5
     add

 In the above method, S is untouched.

  • The other kind of machine is register machine, the above addition in this kind of machine can be done using one line instruction:
 add r1, r2, r3;
  • Stack machine vs. Register machine: In a register based machine the average instructions are larger than the stack machine’s instructions, so the code is simpler in stack machines. Register machines are faster, optimization can also be easily implemented here as the common code can be processed and used number of times. For more, refer this article.
  • Something intermediate or mixture of these machines is called n-register stack machine. In this machine n-top locations of stack is stored in registers.
  • 1-register stack machine is a special type, where the register that has the top value of the stack is called accumulator.
    • In the case of stack machine, when an add operation is performed, it reads out 2 data and writes one, but when the same operation is performed by this machine, it would be implemented as:
acc ← acc + top_of_stack
  •  Taking the machine as 1-register stack machine, the operation op(e1,e2…en) would be done as:
for i ← 1 to n:
     if i is not 1: push ei-1 in stack
     ei is evaluated and stored in accumulator;

what op will do is thet it will pop all n-1 elements in stack and apply it with accumulator which stores en
  •  If the above is done for any expression then the stack is unchanged. Expression evaluation preserves the stack.

Compiler Designing W06L1105

Alignment

  • This is related to the concept of storing data in a machine. For example, a 32-bit machine have a word length of 32-bit or equivalently of 4-bytes and a 64-bit machine, similarly, have word length of 8-bytes.
  • Alignment refers to the structure of storing words such that each word starts from the next word boundary.
  • Alignment makes faster execution as it is easier to find a word in the memory.
  • The memory bytes skipped by the program in order to achieve alignment are junk and never ever referred by the program.

Compiler Designing W06L1104

Globals and Heap

  • Global variables would have only one reference in program so they are allocated statically or at the compile time and for the same reason they cannot be stored in AR. Depending on the language there may be other variables those are allocated statically.
  • Languages having dynamically allocated data use heaps to store dynamically allocated data:
 function foo(){new obj;} //the allocated space would be accessible to external objects too.
                          //as the AR destroys everything they have after completing the work,                            //this cannot be allocated to an AR, hence heaps are used.
  • Now the memory has divided into four parts:
    • Code Area: This is statically created and contains object code, and usually of fixed size and read-only.
    • Static Data Area: This contains statically allocated data eg. global variables.This is readable and writable space.
    • Stack Area: It contains data in AR. It can grow or shrink.
    • Heap Area: It contains dynamically allocated data. Heap can also grow and shrink.
  • Stack and Heap both can grow and shrink and it is the possible that both of the data area are overlapped. To make it more systematic stack and heap grow towards each other as in the figure and when the pointer the stack top and heap top becomes equal the program runs out of the memory.

memory1

Compiler Designing W06L1103

Activation Records

  • All the information that will be needed for executing an activation is called activation record(AR) or frame.
  • If F calls G then G’s AR will have a mix of AR of F and G. F is suspended till G is running then F resumes. Hence G will have the information to complete G and resume F.
  • The activation record can be anything that is advantageous for the language usage. In the video, an AR contained 4 words: result, argument, control link and return address. See the video for its implementation.
  • As an AR structure can affect speed and complexity of code generation, it should be designed with code generator.
  • Frames are stored sequentially data space.

Compiler Designing W06L1102

Procedure Activations

  • An invocation of procedure P is the activation P. All the statements executed between the time when P is called and P is returned is the lifetime of P.
  • In code generation, two main goals are: Correct and fast. To achieve this, a runtime structure is chosen to fulfill both.
  • Languages that would be defined here would follow these two assumptions:
    • Execution would be sequential; (concurrency is the other option in languages)
    • if a procedure is called then the control would return to the pointer immediately after the call. (features like exceptions and call/cc can be other options)[as the exceptions are caught the execution will start from the end of the block where exception as raised.]
  • Scope and lifetime of a variable: Scope is the span of the program to which a variable can be accessed. Lifetime is the time for which memory is reserved for the variable. From the definitions it is clear that lifetime is a dynamic(run-time) term while scope is a static(compile-time) term. Lifetime is also called “allocation method” or “storage duration.” Some basic properties of scope and lifetime is here.
  • If in a procedure another procedure is called then this procedure will return before the second procedure can. So these calls can be shown by a tree.
f() {g();}                                      main
g() {1;}                                        /  \
main(){g();f();}                               g    f
                                                    |
                                                    g

the left side g’s lifetime is main. f’s is main and the lifetime of g below f is f.

  • The activation tree depends on the runtime behavior. Different input can produce different activation trees.
  • As they are perfectly nested so a stack can be used to keep track of currently running activations. With stack memory will look like:

memory

Compiler Designing W06L1101

Runtime Organization

  • Front-end phases are for enforcing language definition and build data structure for back-end.
  • Back-end phase have mainly two parts: Optimization and Code generation.
  • These two phases defines the number of ways to structure executable file.
  • Runtime organization includes:
    • Management of run-time resources
    • Correspondence between static(compile-time) and dynamic(run-time) structures and
    • Storage organization
  • When a program is invoked it first allocated space by OS and then loaded into memory and then execution of ‘main’ happens. In Memory program looks like this:
fig8-1
Code and the Data Part
  • For simplicity, say there is only code space and data space, code space is located towards low address and data part is located towards high address.
  • Both of these parts are related and generated by the compiler. Related so that data can be retrieved easily by the code.