[Sprint 2] [A-IX] Function Inlining

[heatz123]

착안점

Function Inlining은 함수의 호출 instruction을 함수의 inline code로 포함하는 과정을 의미한다. Inlining 수행 시 함수 호출과 관련된 오버헤드를 줄일 수 있고, 함수 호출의 cost(2 + argument 수)를 없앨 수 있다. 만약 루프 안에서 호출하는 함수가 있는 경우와 같이 함수가 많이 호출되는 코드의 경우, cost에서 유의미한 이득을 볼 수 있다.

최적화

callee의 함수를 caller로 붙여넣은 뒤, return value와 return block을 적절하게 수정한다. 구체적으로는,

• call이 있는 basic block을 call 이전과 이후로 split한다.
• call 이전의 block에 붙여넣은 함수의 entry로 branch하도록 branch instruction을 추가한다.
• call 이후의 block을 return block과 합친다.
• return block의 use를 모두 합쳐진 block으로 바꾼다.

[foxisobese]

아직 구현 방법을 제시하지 않으셨지만 고려하셔야 할 부분이 있을 것 같아서 댓글 남깁니다. 재귀함수가 존재하는 경우, 이 pass 가 종료할 것인지, 적절한 길이의 llvm IR 을 출력할 것인지 에 대한 고려가 필요합니다.

극단적인 예시를 들자면, 재귀함수 f 가 llvm IR 에 포함될 때, 재귀에 대한 고려가 없다면 inlining 은 종결하지 않을 것입니다. 더 현실적인 예시를 들자면, 재귀함수 f 가 llvm IR 에 포함될 때, 재귀함수의 inlining 횟수를 n 번으로 정해 놓는다 하더라도 f 가 자기 자신을 m 번 호출한다면 코드상에 단 1 번 등장하는 f 때문에 그 body 를 m^n 번 추가하게 됩니다.

비록 코드 길이가 측정하는 cost 에 제한을 주지는 않지만 코드가 너무 길어진다면 저희 pass 가 제한시간 내에 llvm IR 을 출력하지 못할 가능성이 있습니다.

따라서 inlining 을 하면서 각 함수들의 이름, 등장 횟수, 함수들의 body 길이, body 에서 호출하는 함수들의 목록 들을 고려해서 inlining pass 종결 시점을 결정하는 것이 적절해 보입니다. 해피코딩 되세요~

[heatz123]

넵, 함수의 길이와 Register Pressure (#32)을 모두 고려해서 inlining을 하면 좋을 것 같습니다. 의견 감사합니다!