2015-03-19
Code Generation (Ch. 5-6)

Chapter 6: Intermediate-Code Generation

TAC code generation SDD (Figs. 6.19 and 6.20)
  - general TAC form: "dest = src1 op src2"
  - depth-first postorder traversal
  - S.code and E.code contain corresponding TAC
    - can be emitted incrementally instead of stored
  - E.addr contains address holding value of E

Ex. 6.11:    a = b + - c

    S                             S
    id = E;                  id   =   E
    a = E;                    a
    a = E1 + E2;                  E   +   E
    a = id + E2;                 id
    a = b + E2;                   b
    a = b + - E1;                       -   E
    a = b + - id;                           id
    a = b + - c;                            c

    t1 = - c
    t2 = b + t1
    a = t2

Ex: r = s * t + u * v

    t1 = s * t
    t2 = u * v
    t3 = t1 + t2
    r = t3

array accesses:  base + idx * width
  - generalization to multidimensions:
      base + (i_1 * w_1) + (i_2 * w_2) + ... + (i_k * w_k)
  - alternate definition:
      1d: base + width * (i_1)
      2d: base + width * (i_1 * n_2 + i_2)
      nd: base + width * (( ... ((i_1 * n_2 + i_2) * n_3 + i_3) ... ) * n_k + i_k) * width
  - row-major vs. column-major
  - translation SDD

control flow
  - introduce program labels
    - named location in the program
  - generated sequentially using static newlabel() call

short-circuiting
  - e1 && e2 is false if e1 is false
  - e1 || e2 is true  if e1 is true
  - Ex. 6.21

if statement: if (E) B1

        << E code >>
        if E goto l1
        goto l2
    l1:
        << B1 code >>
    l2:

if statement: if (E) B1 else B2

        << E code >>
        if E goto l1
        goto l2
    l1:
        << B1 code >>
        goto l3
    l2:
        << B2 code >>
    l3:

while loop: while (E) B

    l1:                         ; CONTINUE target
        << E code >>
        if E goto l2
        goto l3
    l2:
        << B code >>
        goto l1
    l3:                         ; BREAK target

for loop: for V in E1, E2 B

        << E1 code >>
        << E2 code >>
        V = E1
    l1:
        t1 = V >= E2
        if t1 goto l2
        << B code >>
        V = V + 1               ; CONTINUE target
        goto l1
    l2:                         ; BREAK target

avoiding redundant GOTOs

        if V goto l1
        goto l2
    l1:
        << code >>
    l2:

  - using ifFalse and fallthrough:

        ifFalse V goto l1
        << code >>
    l1:

  - using negation and fallthrough:

        t1 = !V
        if t1 goto l1
        << code >>
    l1:

backpatching: hack necessitated by the nature of their SDD

switch statement:

    switch (E) {
        case V1:    B1
        case V2:    B2
        default:    BD
    }

        << E code >>
        if E == V1 goto l1
        if E == V2 goto l2
        << BD code >>
        goto l3
    l1:
        << B1 code >>
        goto l3
    l2:
        << B2 code >>
        goto l3
    l3:

  - for sequential values starting with constant (C):
    ("jump table")

        << E code >>
        goto jt(E-C)
    jt: goto l1
        goto l2
    (...)

    (can also use raw instruction addresses and pointer arithmetic)

current dilemmas:
  - include ifFalse?
    - more expressive
    - fewer generated instructions
    - not strictly necessary
    - additional complication during x86 generation
  - include if <relop> ?
    - fewer generated instructions
    - cleaner x86 for (some) jumps
    - more complicated TAC generation

TAC forms for Decaf (tentative):

  - <dest> = <src1>               (copy)
  - <dest>[<idx>] = <src1>        (indexed copy)
  - <dest> = <src1>[<idx>]        (   "     "  )

  - <dest> = <op> <src1>          (unary op)
  - <dest> = <src1> <op> <src2>   (binary op)

  - <lbl>:                        (label)
  - goto <lbl>                    (unconditional jump)
  - if var goto <lbl>             (conditional jump)

  - param var                     (push parameter)
  - call <lbl>                    (call function)
  - <dest> = call <lbl>           (call function w/ return value)
  - ret                           (function return)
  - ret var                       (function return w/ value)