Copyright © 2004
Robert W. Hasker

Ch. 7

• Issue: n source languages, m target architectures
  • straightforward implementation: need parser for every language, backend for each parser to each architecture: n * m compilers
    • can share pieces, but difficult to manage
  • better solution: introduce intermediate representation (IR)
  • each parser: output in IR
  • write backend for each architecture
  • essentially n + m compilers
• design issues
  • easy to construct from abstract parse tree
  • easy to generate machine code
  • support optimization

IR tree nodes for our project

• classes derived from Exp (expressions):
  • CONST(i): integer constant
  • NAME(n): symbolic constant (assembly label)
  • TEMP(t): temporary t
    • will often be allocated to register
    • infinite number of temporaries
  • BINOP(o, e₁, e₂): application of operator o to pair of expressions
  • MEM(e): reference to word at address e
  • CALL(f, l): call function f with argument list l
    • subexpression f evaluated first
    • arguments evaluated left to right
  • ESEQ(s, e): evaluate statement s, evaluate e for result
• classes derived from Stm (statements):
  • MOVE(TEMP t, e): evaluate e, put result in t
  • MOVE(MEM(e₁), e₂): eval e₁, then e₂, then put result of second in address specified by first
  • EXP(e): evaluate expression and discard result
  • JUMP(e, labs): evaluate e and jump to that address; labs specifies all places could jump to (say for switch statements)
    • usual case: JUMP(NAME l, new LabelList(l, null))
  • CJUMP(o, e₁, e₂, t, f): evaluate e₁ then e₂ (in that order); compare using relational operator o; if true, jump to t, else jump to f
  • SEQ(s₁, s₂): execute s₁ then s₂
  • LABEL(n): define n to be current machine address (implements label definitions)
    • can then use NAME(n) as the target of jumps, etc.

Translating from Abstract Parse Trees to Intermediate Trees

• issue: subtleties about translation
  • first cut: expressions translate to Tree.Exp, statements to Tree.Stm
  • "a + b;" should probably translate to a statement, not an expression
  • if ( a > b ) ... would translate to a CJUMP, not an expression
    • Why not change CJUMP to take 3 expressions?
  • thus: need to consider how the expression is used before translating
• textbook: introduces abstract classes with methods like unEx, unNx, unCx for translating
  • not explained well
  • not required (see end of chapter)
• Translating expressions
  • MiniJava does not allow ignoring results of expressions
  • boolean expression in if: use CJUMP:

        if ( a < b && c < d )
        {
           ... true block with label t
        }
        else
        {
           ... false block with label f
        }
    

    translates to

        let z = new Label()
        in
            new SEQ(new CJUMP(CJUMP.LT, translate(a),
                                        translate(b), z, f),
                    new SEQ(new LABEL(z),
                            new CJUMP(CJUMP.LT, translate(c),
                                                translate(d), t, f)))
    

  • boolean expression in assignment: need to generate labels:

        flag = a < b && c < d;
    

    translates to

        let r = new Temp(), t = new Label(), f = new Label()
        in
            new ESEQ(new SEQ(new MOVE(new TEMP(r), new CONST(1)),
                             new SEQ(translate(a < b && c < d, t, f),
                                     new SEQ(new LABEL(f),
                                             new SEQ(new MOVE(new TEMP(r), new CONST(0)),
                                                     new LABEL(t))))),
                     new TEMP(r))
    

Variables

• recall:
  • r-value: result of an expression which can appear on just the right-hand-side of an assignment; eg: 5, a - 2, f(x) (where f returns an int)
  • l-value: result of an expression which can appear on left-hand-side of assignment: variables, array references
    • l-value denotes a location
    • can always convert an l-value into an r-value by accessing the contents of the l-value
• translating simple variables
  • MiniJava: all variables have the same size
  • access (as either l or r values) to variable v:

            new MEM(new BINOP(PLUS, new TEMP(fp), new CONST(k)))
    

    where fp is defined by class Frame and k is the offset for v in the frame (again defined by class Frame)
• array variables
  • array assignment will be handled as pointer assignment (like Java)
• structured l-values
  • integers, pointers (in most languages): scalar values
    • no subcomponents; occupies one word of memory
    • all MiniJava variables are scalar
      • object, array variables are just pointers
    • C++, Pascal: structured types mean some variables are not scalar
      • MOVE operation must provide for number of bytes to copy to support
• subscripting
  • MiniJava: a[i] translates to

            new MEM(new BINOP(PLUS, translate(a), new BINOP(MUL, translate(i), new CONST(w))))
    

    where w is the word size
  • in general: may need to allow for start index (Pascal), different sizes of items in array
  • note: MEM can be used on both sides of MOVE (both as l-values/store and r-values/fetch)
  • need to add check on array bound!

More on expressions

• arithmetic
  • straightforward
  • note no unary operators; can implement unary negation by subtracting from 0
• conditionals
  • use CJUMP as described above
  • much of the discussion in the text has to do with conditional expressions (rather than if statements) of the form

            if e1 then e2 else e3
    

    This is an ML issue and isn't relevant for MiniJava.
  • for project: translate all comparisons to something which gives 0 or 1 and use new CJUMP(EQ, expr, new CONST(1), t, f)
• strings
  • need to allocate space for each string (global lifetime, local scope), generate initialization code

Allocation

• implementing new X or new int[]
• for array:
  1. determine space needed for array: (length + 1) * Wordsize
     • length will be stored at offset 0 for bounds checks
  2. call external function for allocation from heap
  3. generate code to write length to offset 0
  4. generate code to initialize all elements to 0 starting at offset Wordsize
• external call: likely to be calling C or assembly language routine
  • may encounter system-dependent calling conventions for external routines
    • prepend underscores to all C routines?
    • static link?
  • add externalCall method in Frame class to handle such calls
    • generally, this will reduce to a regular CALL but with allowances for differing names, calling conventions
• function call
  • standard calls: f(a₁, ... a₂) translates to

            new CALL(new NAME(lf), [arguments])
    

    where l_f is the label for function f
  • method calls
    • need parameter this
    • call to p.m(a₁, ... a₂) in class C:

              new CALL(new NAME(lC$m), [p, ...args...])
      

  • dynamic methods: later
• for objects (p. 158)
  • steps:
    1. generate code to allocate heap space (number of member variables * wordsize)
    2. initialize all variables to 0
    3. in general (though not in MiniJava): call constructor
  • method calls: all must include implicit parameter for "this"
  • note that access to this will be done by accessing first (hidden) parameter

Statements

• while loop:
  • general layout:

            test:
                    if not(condition) goto done
                    body
                    goto test
            done:
    

  • issue: how to handle break statement?
• for loop:
  • simple translation:

            for(init; expr; update)
               body
    

    to

            init;
            while ( expr )
            {
               body
               update
            }
    

  • issue: for loop in Pascal, Ada, etc: must store values up front, and must be careful about incrementing before comparing:

            for i := low to high do
               body
    

    becomes

            temp = high
            i = low
            if i > temp goto done
    top:
            body
            if i >= temp goto done
            i = i + 1
            goto top
    

    • note this handles the case where high is maxint

Static Links

• Pascal, ML, etc: if access variable in another function's scope, need to use static links to access the data:

      MEM(BINOP(PLUS, CONST(kn),
                      MEM(BINOP(PLUS, CONST(kn-1),
                                      ... MEM(BINOP(PLUS, CONST(k1), TEMP(fp)))
                                      ... ))))
  

  (note no new's)
• implies must know nesting level of every variable (addition to symbol table)
  • nesting level useful for removing entries from symbol table anyways
• in addition: temp variables which can be accessed from another scope must be allocated on stack (not in register)
• calls: add static link as first parameter
  • static link has to be computed in a similar way to the above, but now use nesting level of the two functions involved

Declarations

• variable declarations/definitions: add code to initialize the variable
• function definitions:
  • include prologue, body, epilogue:

    [prologue:]

    1. pseudo-instructions to "announce" the beginning of the function
    2. label for function name
    3. instruction to adjust stack pointer to allocate new frame
    4. instructions to save "escaping" arguments and move other arguments to appropriate registers
    5. store instructions to save any callee-save registers (including return address?)

    6. body

       [epilogue:]

    7. move return value to appropriate register/location
    8. restore callee-save registers
    9. reset stack pointer (deallocate frame)
    10. return instruction
    11. pseudo-instructions to "announce" end of function
  • frame size may not be known until after register allocation
  • item 7: will take the form new MOVE(Ret, body) where body is an ESEQ item
    • Ret determined by Frame method

Review

• IR trees
• Translating various constructs to IR trees