[Sprint 3] Restrict Function Inlining

heatz123 commented 1 year ago

1. 착안점

현재 Function Inlining과 Loop Unrolling이 동시에 쓰일 경우 llvm 코드 길이의 증가로 인해 컴파일 타임이 약 6분 이상으로 늘어나는 이슈를 확인하였다.
즉 function inlining 또는 loop unrolling을 제한할 필요가 있는데, 벤치마크 실험을 통해 function inlining을 제한하는 것을 먼저 선택하였다.

2. 최적화 개요

Function Inlining의 적용 case를 줄인다. 단 성능 감소는 최대한 작아야 한다.

3. 구현 방식

callee 내부에 call이 있는 경우 inlining을 수행하지 않도록 한다.

4. 유닛 테스트 변경

유닛 테스트에서 callee에 call이 있는 경우를 수정하였다.
- function_inlining-6.ll을 수정하였다.

5. 벤치마크 결과

Compile Time

기존: 로컬 4분 -> 변경: 로컬 40초

성능 비교

cost_gain_fi_degradation 패치 이후 성능 감소가 약 0.18%로 미미한 것을 확인함.

heatz123 commented 1 year ago

function inlining같은 경우 call을 제거해 시간을 줄일 수 있다는 장점도 있지만, 찾아보니 inlining진행 이후 caller입장에서 callee가 더이상 blackbox가 되지 않기 때문에 이후 추가적인 최적화가 가능하다는 이유도 있다고 나왔습니다. 만약 simplifyCFG에서 한 것처럼 MPM이후 FPM이 가능하다면, GVN등을 inlining이후에 적용할 경우 추가적인 이득을 볼 수 있을 것이라 생각합니다.

하지만 문제는 GVN의 경우 mul이 add보다 느리다고 생각하기 때문에 arithmetic pass에서 최적화를 진행했던 내용을 되돌릴 수 있으니, LICM을 이후 추가해보는 것도 고려할 수는 있을 것 같습니다.

다시 생각해보니 function inlining자체를 맨 앞에 실행할 수 있다면 가장 좋을 것 같기는 합니다.

Function Inlining을 앞에서 수행함으로서 추가적인 최적화가 가능하게 되는 경우가 혹시 어떤 케이스인가요? 간단한 예시를 들어주실 수 있을까요?

heatz123 commented 1 year ago

일단 MPM인 function inlining을 FPM보다 앞에 배치하기 위해서는 다른 Pass들을 MPM으로 바꿔야 하기 때문에 다음과 같이 코드를 수정해서 벤치마킹해보았습니다.

    MPM.addPass(function_inlining::FunctionInlining());
    MPM.addPass(createModuleToFunctionPassAdaptor(gvn_pass::GVNpass()));
    MPM.addPass(createModuleToFunctionPassAdaptor(lcssa_pass::LCSSApass()));
    MPM.addPass(createModuleToFunctionPassAdaptor(loop_unrolling::LoopUnrolling()));
    MPM.addPass(createModuleToFunctionPassAdaptor(bias_to_false_branch::BiasToFalseBranch()));
    MPM.addPass(createModuleToFunctionPassAdaptor(add_to_sum::AddToSum()));
    MPM.addPass(createModuleToFunctionPassAdaptor(arithmetic_pass::ArithmeticPass()));
    MPM.addPass(createModuleToFunctionPassAdaptor(use_async_load::UseAsyncLoad()));

cost_gain_function_inlining_first

결과는 생각보다 적용 범위가 크네요. 좋은 제안이었던 것 같습니다!

다만 이 부분은 FPM을 MPM으로 바꾸는 별도의 Feature를 요구하기 때문에 Funtion Inlining의 적용 범위를 제한하는 이 PR에서 처리하기는 적절하지 않은 것 같고, Wrap Up때 별도의 PR을 만들어 적용 순서를 변경하면 좋을 것 같습니다.

heatz123 commented 1 year ago

Loop Unrolling(#40)에서 innermost loop만 unroll되도록 한 것과 유사한 제한인 것 같네요. 저도 컴파일타임과 코드가 너무 길어져서 제한을 시켰었습니다.

코드에 달아둔 질문만 답변해주시면 good to go인 것 같습니다.

네 이해하신 바가 맞습니다. innermost loop와 유사하게 innermost call function만 inlining하는 것으로 제한했습니다.

SyphonArch / swpp202301-compiler-team1