LLVM Optimization study - LoopFlatten

LoopFlatten은 Loop 문을 평탄화 하는 최적화인데, 말로는 느낌이 잘 안오니 다음 주석을 참고하자.

LoopFlatten.cpp

//   for (int i = 0; i < N; ++i)
//     for (int j = 0; j < M; ++j)
//       f(A[i*M+j]);
//
// into one loop:
//
//   for (int i = 0; i < (N*M); ++i)
//     f(A[i]);

 

평탄화라는 것이 주석처럼 2층 구조를 가진 Loop를 단층화 하는 것으로 평탄화가 어떤 의미인지 뉘앙스를 알 수 있다.

이를 도식화하면 다음과 같다. (샘플위치 : llvm/test/Transforms/LoopFlatten/loop-flatten.ll)

 

LoopFlatten 을 거치면 위와 같이 CFG 가 변경된 것을 확인할 수 있다.

IR 을 확인하면, Loop.entry에 Tripcount 가 추가되고 2차원 배열이 1차원 배열로 변경됐음을 확인할 수 있다.

 

LoopFlatten은 몇 가지 조건을 검사한 뒤에 OuterLoop와 InnerLoop의 Loop Counter 를 찾아서 TripCount로 병합하는 것이 주요로직이다.나열하자면 다음과 같다.

1. LoopFlatten 과정을 수행해도 되는 LOOP 문인지 확인

2. Outer-Inner Loop 간의 Loop Counter 확인

3. TripCounter로 병합 후 InnerLoop 제거 및 InnerLoop의 LoopCounter use 변경

 

 

 

두 번째, Loop Counter를 확인하는 로직을 추려서 다음 테스트 코드를 작성했다.

 

 

Loop 관련 구조에 대해서는 다음 글을 참고하면 좋다.

 

https://die4taoam.tistory.com/100

LoopLatch