[Sprint 2] [A-IX] Function Inlining

[heatz123]

Function Inlining

Issue link: #23

Note: this PR is built on the top of #33.

1. 착안점

• Function Inlining은 함수 call을 실제 함수의 body로 대체함으로써 function call을 처리하는 데 드는 오버헤드를 줄일 수 있는 최적화로, 대부분의 코드에 적용할 수 있다고 생각하여 추가를 진행했다.
• 우리의 machine의 경우 함수 call은 2 + (# arguments) 만큼이 소요되므로, inlining이 잘 작동할 경우 해당 오버헤드를 줄일 수 있다.
• 다만 function inlining을 남용할 경우 다음의 문제가 있을 수 있다.
  • Register Spilling
  • 본 코드베이스의 backend는 이미 주어져 있고, 이는 변경할 수 없다. backend의 구현을 확인하였을 때, 함수의 특정 시점에서 관리하는 변수가 전체 레지스터 개수를 초과할 경우, 레지스터에 있지 않은 변수를 사용하게 되면 레지스터를 store하고 load하는 과정이 발생하게 된다.
  • Inlining은 기존에 Caller에서 관리하던 변수를 Caller로 끌어내리는 과정을 포함하므로, Register Spilling에 의한 코스트 손해를 크게 볼 수 있다.
  • Compile Time
  • Inlining으로 인해 코드가 너무 길어질 경우, 1분이라는 컴파일 타임 제한 시간을 초과할 가능성이 있다. 특히 backend의 register allocation을 구현하는 코드를 확인한 결과 Interference Graph를 만들고 처리하는 데 O(N^2) 이상의 Time Complexity가 존재하는 것을 확인했다. (N = # Instruction in a Function)
  • 따라서 코드 길이와 register spilling을 고려한 안전한 Function Inlining을 구현하였다.

2. 최적화 개요

Function Inlining에서는 함수 Call을 Callee의 body로 바꾼다. 이때, 전체 코드 길이와 현재 Register Pressure를 고려한다. 이때 Register Pressure는 프로그램의 특정 시점에 관리되는 변수의 총 개수로 정의하고, 이를 계산하기 위해 기존에 구현된 Register Pressure Analysis를 활용할 수 있다. (#33 )

3. 구현 방식

핵심적인 함수는 다음과 같다.

bool shouldInline(CallInst *CI)

다음 조건을 확인하여 inline 여부를 결정한다.

• Definition이 파일 상에 존재한다.
• 자기 자신을 부르지 않는다. (재귀가 아니다.)
• Return문이 하나만 존재한다.
• name이 "oracle"이 아니다.
• Callee와 Caller의 코드 길이 합이 3000줄 미만이다.
• Callee와 Caller의 Register Pressure 합이 32 미만이다.

이때 Return문이 여러 개인 파일에 대한 inlining은 아직 구현하지 않았다. (코드 길이 제한 때문) 단, Return문이 여러개인 함수가 존재하는 벤치마크 파일을 전수조사해본 결과, 재귀가 존재하는 프로그램인 gcd와 mergesort 단 두 경우밖에 없었기 때문에, 우선순위는 아니라고 판단된다.

void inlineFunction(CallInst *CI, Function &Callee)

실제 inlining을 수행한다.

• Callee의 body를 Caller에 복사한다. (cloneFunctionInto)
• 만약 Callee에 static alloca가 있다면 Caller의 entry block으로 옮긴다. (moveStaticAllocasUpIfExists)
• 복사한 코드를 잘 변경하여 inline이 valid하도록 만든다. (mergeToCallSite)

구체적인 예시

define i32 @caller(i32 %a, i32 %b) {
  %add = add i32 %a, %b
  %call = call i32 @callee(i32 %add)
  ret i32 %call
}

define i32 @callee(i32 %x) {
  %sub = sub i32 %x, 5
  br label %exit

exit:
  %sub2 = sub i32 %sub, 10
  ret i32 %sub2
}

1. Callee 복사

   define i32 @caller(i32 %a, i32 %b) {
     %add = add i32 %a, %b
     %call = call i32 @callee(i32 %add)
     ret i32 %call
   
   entry2:
     %sub = sub i32 %x, 5
     br label %exit
   
   exit:
     %sub2 = sub i32 %sub, 10
     ret i32 %sub2
   }
   
   define i32 @callee(i32 %x) {
     %sub = sub i32 %x, 5
     br label %exit
   
   exit:
     %sub2 = sub i32 %sub, 10
     ret i32 %sub2
   }

2. static alloca를 위로 옮기는 과정(생략 ,현재 예시에는 static alloca가 없다.) alloca가 static하지 않은 경우 백엔드가 작동하지 않기 때문에, 프로그램의 정상 작동을 위해 alloca를 static하게 만들어야 한다.

3. split BasicBlock

   define i32 @caller(i32 %a, i32 %b) {
     %add = add i32 %a, %b
     br %callee.exit
   
   callee.exit:
     %call = call i32 @callee(i32 %add)
     ret i32 %call
   
   entry2:
     %sub = sub i32 %x, 5
     br label %exit
   
   exit:
     %sub2 = sub i32 %sub, 10
     ret i32 %sub2
   }

4. branch 변경

   define i32 @caller(i32 %a, i32 %b) {
     %add = add i32 %a, %b
     br %entry2 ; <- entry2로 변경됨
   
   callee.exit:
     %call = call i32 @callee(i32 %add)
     ret i32 %call
   
   entry2:
     %sub = sub i32 %x, 5
     br label %exit
   
   exit:
     %sub2 = sub i32 %sub, 10
     ret i32 %sub2
   }

5. merge return block

   define i32 @caller(i32 %a, i32 %b) {
     %add = add i32 %a, %b
     br %entry2
   
   callee.exit:
     %sub2 = sub i32 %sub, 10
     ret i32 %sub2
     %call = call i32 @callee(i32 %add)
     ret i32 %call
   
   entry2:
     %sub = sub i32 %x, 5
     br label %exit
   }

6. set branch to return block

   define i32 @caller(i32 %a, i32 %b) {
     %add = add i32 %a, %b
     br %entry2
   
   callee.exit:
     %sub2 = sub i32 %sub, 10
     ret i32 %sub2
     %call = call i32 @callee(i32 %add)
     ret i32 %call
   
   entry2:
     %sub = sub i32 %x, 5
     br label %callee.exit ; <- callee.exit으로 변경
   }

7. replace use of ret & deletion

   define i32 @caller(i32 %a, i32 %b) {
     %add = add i32 %a, %b
     br %entry2
   
   callee.exit:
     %sub2 = sub i32 %sub, 10
     ; ret i32 %sub2 -> removed
     ; %call = call i32 @callee(i32 %add) -> removed
     ret i32 %sub2 ; -> replaced
   
   entry2:
     %sub = sub i32 %x, 5
     br label %callee.exit ; <- callee.exit으로 변경
   }

4. 유닛 테스트

• function_inlining-1.ll: Check if the function inlining works in the most simple case. (Callee has 1 BasicBlock and 1 int return instruction)
• function_inlining-2.ll: Check if the function inlining works in the most simple case. (Callee has 1 BasicBlock and 1 void return instruction)
• function_inlining-3.ll: Check if function inlining works when the Callee has multiple BasicBlocks.
• function_inlining-4.ll: Check if the function inlining pass works when Callee has calls in function body.
• function_inlining-5.ll: Check if the pass does not corrupt the code in the multiple returns case.
• function_inlining-6.ll: Check if the inlining does not corrupt the code in the case of recursion.
• function_inlining-7.ll: Check if the pass does not inline oracle function.
• function_inlining-8.ll: Check if function inlining moves the static allocas up.
• function_inlining-9.ll: Check if the phi after split is remapped correctly.

5. 성능 비교 (이전/이후)

1. register pressure를 고려하지 않고 inline한 결과 본래부터 register pressure가 큰 matmul2 프로그램의 경우 성능 하락이 존재하였음.

2. register pressure를 설정하여 선택적으로 inline 구현 결과 성능이 일관되게 향상하는 것을 확인하였음.

3. Function Inlining Pass를 2회 적용한 결과 (상: 2회 적용 결과, 하: 1회 적용과의 비교) 2회 적용한 경우 추가적인 성능 향상이 존재하나, 컴파일 타임이 훨씬 길어져 성능 향상에 비해 리스크가 있는 것으로보임.