Split View: [컴파일러] 12. 코드 생성 알고리즘과 레지스터 할당

Initial state:
  R1: empty
  R2: empty
  R3: empty

After instruction "LD R1, a":
  R1: a
  R2: empty
  R3: empty

Variable a: memory
Variable b: R1, memory
Variable c: R2

// Three-address code
t = a - b
u = a - c
v = t + u
d = v + u

Instruction: t = a - b
  getReg -> R1 (empty)
  Code: LD  R1, a      // R1 = a
        LD  R2, b      // R2 = b
        SUB R1, R1, R2 // R1 = a - b = t
  Registers: R1=t, R2=b
  Descriptors: t->R1, a->memory, b->R2/memory

Instruction: u = a - c
  getReg -> R2 (b is not needed later)
  Code: LD  R2, a      // R2 = a
        SUB R2, R2, c  // R2 = a - c = u
  Registers: R1=t, R2=u

Instruction: v = t + u
  getReg -> R1 (t is not needed later)
  Code: ADD R1, R1, R2 // R1 = t + u = v
  Registers: R1=v, R2=u

Instruction: d = v + u
  getReg -> R1 (v is not needed later)
  Code: ADD R1, R1, R2 // R1 = v + u = d
  Registers: R1=d, R2=u

// End of basic block: store live variable d to memory
  Code: ST  d, R1

LD  R1, a
LD  R2, b
SUB R1, R1, R2
LD  R2, a
SUB R2, R2, c
ADD R1, R1, R2
ADD R1, R1, R2
ST  d, R1

// DAG:
//        (d: +)
//       /      \
//    (v: +)    (u: -)
//    /    \    /    \
// (t: -)  (u) a0    c0
//  /   \
// a0   b0

// Good order: t, u, v, d (consumed right after use)
// Bad order: t, v, u, d (t must be kept for a long time)

Algorithm: DAG Node Ordering

1. Push root nodes (nodes with no output) onto the stack
2. While the stack is not empty:
   a. Pop node n from the top of the stack and output it
   b. Push children of n whose parents have all been output
   c. If multiple children satisfy the condition, push the leftmost child first

1. Leaf node: label = 1 (left child) or 0 (right child in memory)
2. If the two children's labels differ: label = max(l1, l2)
3. If the two children's labels are equal: label = l1 + 1

//       (*)      label = 2
//      /   \
//    (+)    (-)   label = 1, 1
//   / \    / \
//  a   b  c   d   leaves
//
// (+): left=1, right=0 -> different, max(1,0) = 1
// (-): left=1, right=0 -> different, max(1,0) = 1
// (*): left=1, right=1 -> equal, 1+1 = 2
//
// Conclusion: 2 registers needed

Algorithm: genCode(node)

if node is a leaf:
    LD Ri, node.name
else:
    left = node.leftChild
    right = node.rightChild

    if left.label >= right.label:
        genCode(left)   // result in Ri
        genCode(right)  // result in Rj
        emit("OP Ri, Ri, Rj")
    else:
        genCode(right)  // right side first
        genCode(left)
        emit("OP Ri, Rj, Ri")

// Code:
// 1: a = ...
// 2: b = ...     (a live)
// 3: c = a + b   (a, b live)
// 4: d = c       (c live)
// 5: e = b + d   (b, d live)
// 6: return e

// Interference graph:
//   a --- b
//   |
//   c     d --- b
//         |
//         e

Algorithm: Graph Coloring Register Allocation

1. Simplify:
   - Remove nodes with degree less than k from the graph and push onto stack
   - After removal, other nodes' degrees may decrease, so repeat

2. Spill:
   - If all nodes have degree >= k, mark one as a potential spill and remove it
   - Spill candidate selection criteria: infrequently used variables, variables outside loops

3. Select:
   - Pop nodes from the stack one at a time, adding them back to the graph
   - Assign a color (register) not used by neighbors
   - If no color is available, actual spill occurs

4. Actual Spill Handling:
   - Insert load/store code for spilled variables
   - Rebuild the interference graph and repeat the algorithm

// Interference graph:
//   a --- b --- c
//
// Degrees: a=1, b=2, c=1

// Simplify: remove a (degree 1 < 2) -> remove c (degree 1 < 2) -> remove b (degree 0 < 2)
// Stack: [a, c, b]

// Select:
//   b -> R1 (no neighbors, any color works)
//   c -> R2 (neighbor b=R1, so R2)
//   a -> R2 (neighbor b=R1, so R2)

// Result: a=R2, b=R1, c=R2

// Before optimization
ST a, R1
LD R1, a    // Redundant load

// After optimization
ST a, R1
// LD removed (R1 already contains the value of a)

// Before optimization
BR L2
ADD R1, R2, R3   // Unreachable
SUB R4, R5, R6   // Unreachable
L2:

// After optimization
BR L2
L2:
// Or the BR itself can be removed (if consecutive labels)

// Before optimization
BR L1
...
L1: BR L2

// After optimization
BR L2     // Skip L1 and go directly to L2

// Before optimization
ADD R1, R1, #0   // x + 0 = x
MUL R2, R2, #1   // x * 1 = x
MUL R3, R3, #2   // x * 2

// After optimization
// ADD removed (identity operation)
// MUL removed (identity operation)
SHL R3, R3, #1   // Replace multiplication with shift (strength reduction)

// Before optimization
MUL R1, R2, #4    // Multiplication (slow)
MUL R3, R4, #8
DIV R5, R6, #2

// After optimization
SHL R1, R2, #2    // Left shift (fast): x*4 = x<<2
SHL R3, R4, #3    // x*8 = x<<3
SHR R5, R6, #1    // Right shift: x/2 = x>>1

// Before optimization
LD  R1, a
ADD R1, R1, #1
ST  a, R1

// After optimization (if machine supports INC instruction)
INC a