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

// 흐름 그래프:
//   1 -> 2 -> 3 -> 4
//        |    ^    |
//        v    |    v
//        5 ---+    6
//                  |
//                  v
//                  7

// 지배자 트리:
//        1
//        |
//        2
//      / | \
//     3  5  6
//     |     |
//     4     7
//
// 해석: 1 dom 모든 노드
//       2 dom 3,4,5,6,7
//       3 dom 4
//       6 dom 7

알고리즘: 지배자 계산

초기화:
  DOM[entry] = {entry}
  DOM[n] = 모든 노드의 집합 (n != entry)

반복 (수렴할 때까지):
  for (모든 노드 n != entry):
    DOM[n] = {n} U ( n DOM[p] )  // p는 n의 모든 선행자
                                  // 선행자들의 DOM 교집합에 n을 추가

DF(n) = 노드 y의 집합 | n이 y의 선행자를 지배하지만, y 자체는 (엄격하게) 지배하지 않음

// 흐름 그래프에서:
//   1 -> 2 -> 3 -> 4
//        ^         |
//        +---------+   // 4 -> 2는 후방 간선 (2 dom 4)

알고리즘: 자연 루프 구성 (후방 간선 n -> d)

1. loop = {d}
2. stack = {n}  (n이 d와 다르면)
3. while stack이 비어있지 않음:
     m = stack에서 pop
     if m이 loop에 없으면:
         loop에 m 추가
         m의 모든 선행자를 stack에 push
4. 결과: loop

// 흐름 그래프:
//   B1 -> B2 -> B3 -> B4
//          ^          |
//          +----------+  (후방 간선: B4 -> B2)
//          |
//          +-- B5 (B2 -> B5, B5 -> B2도 후방 간선)

// 후방 간선 B4 -> B2의 자연 루프:
//   {B2, B3, B4}  (B2를 거치지 않고 B4에 도달 가능: B3, B4)

// 후방 간선 B5 -> B2의 자연 루프:
//   {B2, B5}

// 외부 루프: {B1, B2, B3, B4, B5}
// 내부 루프: {B3, B4}
//
// 내부 루프를 먼저 최적화한 후 외부 루프를 최적화합니다
// (안쪽에서 바깥쪽으로)

알고리즘: 루프 불변 코드 검출

1. 상수이거나 루프 밖에서만 정의된 피연산자를 가진 명령어를
   "루프 불변"으로 표시
2. 반복:
   - 모든 피연산자가 상수이거나, 루프 밖 정의이거나,
     이미 루프 불변으로 표시된 정의 하나만 가지는 명령어를
     새로 "루프 불변"으로 표시
3. 더 이상 새로운 표시가 없으면 종료

// 루프:
//   B2: i = i + 1
//       t1 = n * 4       // n은 루프 밖에서 정의 -> 루프 불변
//       t2 = a[t1]       // t1이 루프 불변이고 a가 루프에서 불변 -> 루프 불변
//       t3 = t2 + i
//       if i < 100 goto B2

// 1차: t1 = n * 4 표시 (n이 루프 밖 정의)
// 2차: t2 = a[t1] 표시 (t1이 루프 불변)
// 3차: 더 이상 없음 -> 종료

// 안전한 경우:
//   preheader -> [B1: s: x=... ] -> B2(출구)
//   B1이 출구를 지배하므로 이동 가능

// 위험한 경우:
//   preheader -> B1 -> B3(출구)
//                |
//                v
//               B2: s: x=...
//   B2가 출구 B3를 지배하지 않음 -> 이동 불가
//   (s가 실행되지 않는 경로가 존재)

// 이동 전:
//   ... -> header -> body -> ...
//           ^               |
//           +---------------+

// preheader 삽입 후:
//   ... -> preheader -> header -> body -> ...
//                        ^               |
//                        +---------------+

// 루프 불변 코드를 preheader에 배치:
//   preheader:
//     t1 = n * 4       // 이동된 코드
//     t2 = a[t1]       // 이동된 코드

// 예시:
// i = i + 1        // i는 기본 유도 변수
// t1 = 4 * i       // t1은 파생 유도 변수: (i, 4, 0)
// t2 = t1 + base   // t2는 파생 유도 변수: (i, 4, base)

알고리즘: 유도 변수 검출

1단계: 기본 유도 변수 검출
  - 루프 내에서 i = i + c 형태로만 정의되는 변수를 찾음

2단계: 파생 유도 변수 검출
  - j = c1 * i (i가 기본 유도 변수, c1이 루프 상수)
    -> j의 삼중쌍: (i, c1, 0)
  - j = k + c2 (k가 유도 변수 (i, a, b), c2가 루프 상수)
    -> j의 삼중쌍: (i, a, b+c2)
  - j = c1 * k (k가 유도 변수 (i, a, b))
    -> j의 삼중쌍: (i, c1*a, c1*b)

// 원본 코드:
// i = 0
// loop:
//   t1 = 4 * i       // 곱셈
//   a[t1] = 0
//   i = i + 1
//   if i < n goto loop

// 강도 감소 후:
// i = 0
// t1 = 0             // 초기값: 4 * 0 = 0
// loop:
//   a[t1] = 0
//   i = i + 1
//   t1 = t1 + 4      // 곱셈 -> 덧셈
//   if i < n goto loop

// 강도 감소 후:
// i = 0
// t1 = 0
// loop:
//   a[t1] = 0
//   i = i + 1         // i는 비교에서만 사용
//   t1 = t1 + 4
//   if i < n goto loop

// 유도 변수 제거 후:
// t1 = 0
// limit = 4 * n       // 종료 조건 변환 (루프 밖에서 한 번만 계산)
// loop:
//   a[t1] = 0
//   t1 = t1 + 4
//   if t1 < limit goto loop
//
// i가 완전히 제거됨!

// 원본 (100번 반복)
for (i = 0; i < 100; i++) {
    a[i] = 0;
}

// 4배 펼침 (25번 반복)
for (i = 0; i < 100; i += 4) {
    a[i]   = 0;
    a[i+1] = 0;
    a[i+2] = 0;
    a[i+3] = 0;
}

// 반복 횟수가 펼침 인수의 배수가 아닌 경우
// 나머지 처리가 필요

// n이 4의 배수가 아닐 수 있는 경우
i = 0
// 메인 루프 (4배 펼침)
while (i + 3 < n) {
    a[i] = 0; a[i+1] = 0; a[i+2] = 0; a[i+3] = 0;
    i += 4;
}
// 나머지 처리
while (i < n) {
    a[i] = 0;
    i++;
}

// 원본 코드 (행렬의 한 행 초기화)
i = 0
loop:
    t1 = i * 8           // 유도 변수 (곱셈)
    t2 = base + t1       // 유도 변수
    *t2 = 0.0
    i = i + 1
    if i < n goto loop

// 1단계: 루프 불변 코드 이동
//   (이 예시에서는 해당 없음)

// 2단계: 강도 감소
i = 0
t1 = 0                   // 초기값
t2 = base                // 초기값
loop:
    *t2 = 0.0
    i = i + 1
    t1 = t1 + 8          // 곱셈 -> 덧셈
    t2 = t2 + 8          // 곱셈 -> 덧셈
    if i < n goto loop

// 3단계: 유도 변수 제거 (i와 t1 제거)
t2 = base
limit = base + n * 8     // 루프 밖에서 한 번 계산
loop:
    *t2 = 0.0
    t2 = t2 + 8
    if t2 < limit goto loop

// 4단계: 루프 펼침 (2배)
t2 = base
limit = base + n * 8
loop:
    *t2 = 0.0
    *(t2 + 8) = 0.0
    t2 = t2 + 16
    if t2 < limit goto loop
// (나머지 처리 코드는 생략)