Scribd Logo
Upload

Welcome to Scribd!

  • 64 views

    Run-Time Environments: COP5621 Compiler Construction

    Uploaded by

    Hassnain Abbas
    Compiler Construction

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Run-Time Environments: COP5621 Compiler Construction

    Uploaded by

    Hassnain Abbas
    64 views21 pages
    Compiler Construction

    Original Title

    Ch7 Modified

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Compiler Construction

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    64 views21 pages

    Run-Time Environments: COP5621 Compiler Construction

    Uploaded by

    Hassnain Abbas
    Compiler Construction

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 21

    1

    Run-Time Environments

    Chapter 7

    COP5621 Compiler Construction


    Copyright Robert van Engelen, Florida State University, 2007-2013
    Storage Organization
    Static vs. Dynamic Allocation
    • Static: Compile time,
    • Dynamic: Runtime allocation
    • Many compilers use some combination of
    following
    – Stack storage: for local variables, parameters and so
    on
    – Heap storage: Data that may outlive the call to the
    procedure that created it
    • Stack allocation is a valid allocation for
    procedures since procedure calls are nested
    4

    Procedure Activation and


    Lifetime
    • A procedure is activated when called
    • The lifetime of an activation 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 ended
    Sketch of a quicksort program
    Activation for Quicksort
    Activations:
    begin sort
    enter readarray
    leave readarray
    enter quicksort(1,9)
    enter partition(1,9)
    leave partition(1,9)
    enter quicksort(1,3)
    …
    leave quicksort(1,3)
    enter quicksort(5,9)
    …
    leave quicksort(5,9)
    leave quicksort(1,9)
    end sort.
    Activation tree representing calls
    during an execution of quicksort

    r q(1,9)

    p(1,9) q(1,3) q(5,9)

    p(1,3) q(1,0) q(2,3) p(5,9) q(5,5) q(7,9)

    p(2,3) q(2,1) q(3,3) p(7,9) q(7,7) q(9,9)


    8

    Control Stack

    Activation tree: Control Activations:


    begin sort
    s stack: enter readarray
    r
    s leave readarray
    q(1,9) enter quicksort(1,9)
    q(1,9) enter partition(1,9)
    p(1,9) q(1,3) q(1,3) leave partition(1,9)
    enter quicksort(1,3)
    q(2,3) enter partition(1,3)
    p(1,3) q(1,0) q(2,3) leave partition(1,3)
    enter quicksort(1,0)
    leave quicksort(1,0)
    enter quicksort(2,3)
    …
    9

    Scope Rules
    • Environment determines name-to-object
    bindings: which objects are in scope?
    program prg;
    var y : real;
    function x(a : real) : real;
    begin … end;
    procedure p;
    var x : integer;
    Variable x locally declared in p begin
    x := 1;
    …
    end;
    begin
    y := x(0.0);
    A function x …
    end.
    10

    Mapping Names to Values

    environment state

    name storage value

    var i;
    …
    i := 0;
    …
    i := i + 1;
    11

    Mapping Names to Values


    At compile time At run time

    environment state

    name storage value

    var i;
    …
    i := 0;
    …
    i := i + 1;
    12

    Stack Allocation
    • Activation records (subroutine frames) on the run-
    time stack hold the state of a subroutine
    • Calling sequences are code statements to create
    activations records on the stack and enter data in
    them
    – Caller’s calling sequence enters actual arguments,
    control link, access link, and saved machine state
    – Callee’s calling sequence initializes local data
    – Callee’s return sequence enters return value
    – Caller’s return sequence removes activation record
    13

    Activation Records
    (Subroutine Frames)
    fp
    (frame pointer) Returned value
    Actual parameters
    Caller’s
    Optional control link responsibility
    Optional access link to initialize

    Saved machine status


    (w/ opt. return address)
    Local data Callee’s
    responsibility
    Temporaries to initialize
    14

    Activation Records
    • Temporary values, such as those arising from the evaluation
    of expressions
    • Local data belonging to the procedure
    • A saved machine status, with information about the state of the
    machine just before the call to the procedure
    • An "access link" may be needed to locate data needed by the called
    procedure
    • A control link, pointing to the activation record of the caller
    • Space for the return value of the called function, if any. Again, not
    all called procedures return a value, and if one does, we may prefer
    to place that value in a register for efficiency.
    • The actual parameters used by the calling procedure. Commonly,
    these values are not placed in the activation record but rather in
    registers, when possible, for greater efficiency.
    15

    Control Links

    The control link is the old


    value of the fp

    Caller’s activation record


    fp
    Callee’s activation record
    Control link
    sp

    Stack
    growth
    16

    Parameter Passing Modes


    • Call-by-value:
    – This is the simplest method of parameter passing
    – The actual parameter are evaluated and their r-values are
    passed to caller procedure
    – The operations on formal parameters do not change the
    values of a parameter
    17

    Parameter Passing Modes


    • Call-by-reference:
    – This method also called as call-by-address or call-by-location
    – The l-value, the address of actual parameter is passed to the
    called routines activation record
    18

    Parameter Passing Example


    19

    Parameter Passing Modes


    • Copy-restore (aka value-result):
    – This method is hybrid between call-by-value and call-by-
    reference. This method is also known as copy-in-copy-out or
    values result.
    – This calling procedure calculates the value of actual
    parameter and it then copied to activation record for the
    called procedure.
    – During execution of the called procedure, the actual
    parameters value is not affected.
    – If the actual parameter has l-value then at return the value of
    formal parameter is copied to actual parameter.
    20

    Parameter Passing Modes


    • Call-by-name:
    – This is less popular method of parameter passing.
    – Procedure is treated like macro. The procedure body is
    substituted for call in caller with actual parameters
    substituted for formals.
    – The actual parameters can be surrounded by parenthesis to
    preserve their integrity.
    – The local names of called procedure and names of calling
    procedure are distinct.
    21

    You might also like