Split View: [컴파일러] 15. 루프 최적화와 코드 이동

// Flow graph:
//   1 -> 2 -> 3 -> 4
//        |    ^    |
//        v    |    v
//        5 ---+    6
//                  |
//                  v
//                  7

// Dominator tree:
//        1
//        |
//        2
//      / | \
//     3  5  6
//     |     |
//     4     7
//
// Interpretation: 1 dom all nodes
//                 2 dom 3,4,5,6,7
//                 3 dom 4
//                 6 dom 7

Algorithm: Dominator Computation

Initialization:
  DOM[entry] = {entry}
  DOM[n] = set of all nodes (n != entry)

Iterate (until convergence):
  for (all nodes n != entry):
    DOM[n] = {n} U ( n DOM[p] )  // p is all predecessors of n
                                  // Add n to the intersection of predecessors' DOMs

DF(n) = set of nodes y | n dominates a predecessor of y, but does not (strictly) dominate y itself

// In a flow graph:
//   1 -> 2 -> 3 -> 4
//        ^         |
//        +---------+   // 4 -> 2 is a back edge (2 dom 4)

Algorithm: Natural Loop Construction (back edge n -> d)

1. loop = {d}
2. stack = {n}  (if n is different from d)
3. while stack is not empty:
     m = pop from stack
     if m is not in loop:
         add m to loop
         push all predecessors of m onto stack
4. Result: loop

// Flow graph:
//   B1 -> B2 -> B3 -> B4
//          ^          |
//          +----------+  (back edge: B4 -> B2)
//          |
//          +-- B5 (B2 -> B5, B5 -> B2 is also a back edge)

// Natural loop for back edge B4 -> B2:
//   {B2, B3, B4}  (reachable to B4 without going through B2: B3, B4)

// Natural loop for back edge B5 -> B2:
//   {B2, B5}

// Outer loop: {B1, B2, B3, B4, B5}
// Inner loop: {B3, B4}
//
// Optimize the inner loop first, then the outer loop
// (from inside out)

Algorithm: Loop-Invariant Code Detection

1. Mark instructions whose operands are constants or defined only outside
   the loop as "loop invariant"
2. Repeat:
   - Newly mark instructions as "loop invariant" if all operands are constants,
     outside definitions, or have exactly one definition already marked as loop invariant
3. Terminate when no new markings are made

// Loop:
//   B2: i = i + 1
//       t1 = n * 4       // n is defined outside the loop -> loop invariant
//       t2 = a[t1]       // t1 is loop invariant and a is invariant in loop -> loop invariant
//       t3 = t2 + i
//       if i < 100 goto B2

// Pass 1: Mark t1 = n * 4 (n is an outside definition)
// Pass 2: Mark t2 = a[t1] (t1 is loop invariant)
// Pass 3: No more -> terminate

// Safe case:
//   preheader -> [B1: s: x=... ] -> B2(exit)
//   B1 dominates the exit, so motion is possible

// Dangerous case:
//   preheader -> B1 -> B3(exit)
//                |
//                v
//               B2: s: x=...
//   B2 does not dominate exit B3 -> motion not possible
//   (a path exists where s is not executed)

// Before motion:
//   ... -> header -> body -> ...
//           ^               |
//           +---------------+

// After preheader insertion:
//   ... -> preheader -> header -> body -> ...
//                        ^               |
//                        +---------------+

// Place loop-invariant code in the preheader:
//   preheader:
//     t1 = n * 4       // Moved code
//     t2 = a[t1]       // Moved code

// Example:
// i = i + 1        // i is a basic induction variable
// t1 = 4 * i       // t1 is a derived induction variable: (i, 4, 0)
// t2 = t1 + base   // t2 is a derived induction variable: (i, 4, base)

Algorithm: Induction Variable Detection

Step 1: Detect basic induction variables
  - Find variables defined only in the form i = i + c within the loop

Step 2: Detect derived induction variables
  - j = c1 * i (i is basic induction variable, c1 is loop constant)
    -> j's triple: (i, c1, 0)
  - j = k + c2 (k is induction variable (i, a, b), c2 is loop constant)
    -> j's triple: (i, a, b+c2)
  - j = c1 * k (k is induction variable (i, a, b))
    -> j's triple: (i, c1*a, c1*b)

// Original code:
// i = 0
// loop:
//   t1 = 4 * i       // Multiplication
//   a[t1] = 0
//   i = i + 1
//   if i < n goto loop

// After strength reduction:
// i = 0
// t1 = 0             // Initial value: 4 * 0 = 0
// loop:
//   a[t1] = 0
//   i = i + 1
//   t1 = t1 + 4      // Multiplication -> addition
//   if i < n goto loop

// After strength reduction:
// i = 0
// t1 = 0
// loop:
//   a[t1] = 0
//   i = i + 1         // i is used only in comparison
//   t1 = t1 + 4
//   if i < n goto loop

// After induction variable elimination:
// t1 = 0
// limit = 4 * n       // Termination condition conversion (computed once outside loop)
// loop:
//   a[t1] = 0
//   t1 = t1 + 4
//   if t1 < limit goto loop
//
// i is completely eliminated!

// Original (100 iterations)
for (i = 0; i < 100; i++) {
    a[i] = 0;
}

// 4x unrolling (25 iterations)
for (i = 0; i < 100; i += 4) {
    a[i]   = 0;
    a[i+1] = 0;
    a[i+2] = 0;
    a[i+3] = 0;
}

// When the iteration count is not a multiple of the unrolling factor
// Remainder handling is needed

// When n might not be a multiple of 4
i = 0
// Main loop (4x unrolling)
while (i + 3 < n) {
    a[i] = 0; a[i+1] = 0; a[i+2] = 0; a[i+3] = 0;
    i += 4;
}
// Remainder handling
while (i < n) {
    a[i] = 0;
    i++;
}

// Original code (initializing a row of a matrix)
i = 0
loop:
    t1 = i * 8           // Induction variable (multiplication)
    t2 = base + t1       // Induction variable
    *t2 = 0.0
    i = i + 1
    if i < n goto loop

// Step 1: Loop-invariant code motion
//   (none applicable in this example)

// Step 2: Strength reduction
i = 0
t1 = 0                   // Initial value
t2 = base                // Initial value
loop:
    *t2 = 0.0
    i = i + 1
    t1 = t1 + 8          // Multiplication -> addition
    t2 = t2 + 8          // Multiplication -> addition
    if i < n goto loop

// Step 3: Induction variable elimination (remove i and t1)
t2 = base
limit = base + n * 8     // Computed once outside the loop
loop:
    *t2 = 0.0
    t2 = t2 + 8
    if t2 < limit goto loop

// Step 4: Loop unrolling (2x)
t2 = base
limit = base + n * 8
loop:
    *t2 = 0.0
    *(t2 + 8) = 0.0
    t2 = t2 + 16
    if t2 < limit goto loop
// (remainder handling code omitted)