[Sprint1] [A-VI] Arithmetic & Logical Instruction Optimization

[pzmaus]

[A-VI] Arithmetic & Logical Instruction Optimization

[ 착안점 ]

특정 산술/논리 연산들은 더 저렴한 연산의 조합으로 변환될 수 있다.

[최적화 개요]

• Add const 1 to 4의 경우 각 경우에 맞는 type의 incr 함수를 call해준다.
• add %x %x instruction을 mul %x 2로 변경한다. Cost: 5 (Add) -> 1 (Mul)
• [shl %x c]를 mul %x (2^c)로 변경한다. Cost: 4 (Shift) -> 1 (Mul)
• [ashr %x c]를 sdiv %x (2^c)로 변경한다. Cost: 4 (Shift) -> 1 (Div)
• [lshr %x c]를 udiv %x (2^c)로 변경한다. Cost: 4 (Shift) -> 1 (Div)

[구현 방식]

아래 4가지의 변환의 경우 : 각 instruction이 들어올 때 operand를 확인한 다음 조건에 맞아 떨어질 경우 일대일로 instruction을 교환해준다.

1 to 4의 상수가 더해지는 경우 :

1. add operation임을 확인
2. 더해지는 상수를 확인(1 to 4 인지)
3. 맞다면 type을 확인하고 그에 맞는 incr함수를 상수번 부르는 instruction으로 대체한다

[유닛 테스트] arithmetic_pass_1.ll: 1 to 4 상수를 더하는 경우를 제외한 나머지 4가지 경우를 테스트한다. arithmetic_pass_2.ll: add 1 to 4 및 추가적인 변환이 동시에 일어났을 때 제대로 작동하는지 테스트한다. arithmetic_pass_3.ll: i8, i16, i32, i64 모든 경우에 대해 add 1 to 4가 알맞게 변환되는지 테스트한다.

---

[Review 이후 변경사항]

1. 이제 sub %a, 1~4또한 add와 마찬가지로 decr로 치환됩니다.
2. sub 0, %a를 mul %a, -1로 치환합니다.
3. add 1~4, %a처럼 const가 앞에있는 경우 preprocess를 통해 앞뒤 순서를 미리 바꿔 최적화가 가능해졌습니다.
4. add %a, (-1 ~ -4)를 preprocessing을 통해 sub %a, (1~4)로 바꿔 최적화가 가능해졌습니다.
5. sub %a, (-1 ~ -4)를 preprocessing을 통해 add %a, (1~4)로 바꿔 최적화가 가능해졌습니다.
6. 요청하신대로 add/sub할때 type check하는 방식을 간단하게 변경했습니다.
7. 사용하지 않는 #include들을 제거했습니다.
8. format을 수정했습니다. 하지만 생각보다 변경점이 없는 것 같습니다.
9. CMakeList에서 LLVM_ROOT를 개인적으로 사용하던 부분을 주석처리했습니다.
10. 새로 추가된 경우들을 체크하기 위한 testcase들을 추가했습니다. + test1을 약간 변경했습니다.

line수가 200줄을 채워서 추가적인 수정사항이 필요한 경우 300line PR로 바꾸거나 arithmetic_pass_ver2를 만들어야 할 듯 합니다.

[review 이후 추가변경사항] clang format 결과 줄수가 많이 늘어나서 아마 200 초과 PR을 이번서 사용하게 될 것 같습니다.

추가로 benchmark test도중 문제가 생겨 수정한 부분이 있습니다. 예를 들어 shl %a, c가 들어온다면 mul로 바꾸는 경우는 처리했지만, 반대로 shl c, %a로 들어오거나 shl %a, %b처럼 변경하면 안되는 경우 버그가 발생했었습니다. match가 아니라 operand1의 값이 const인지만 봐서 생긴 문제라 생각되며 모든 최적화 부분에 있어 const로 변환이 가능한지 체크한 뒤 format이 맞아떨어지지 않으면 넘어가도록 구현했습니다. 또 혹시 몰라 충돌을 막기 위해 모든 부분에 continue를 추가했습니다. (약간 더 빨라지는 효과도 기대해봅니다)

---

[구현상 발생한 이슈] getElementPtr 제거의 경우 이번 PR의 내용과 사뭇 다른점이 있으며 코드 길이가 길어지기에 다음 PR에서 구현하기로 결정했다. #1

[heatz123]

그리고 코드에서 incr 변환 시 const operand가 앞에 나온 경우 (ex) add i32 2, %x 도 같은 방식으로 처리하도록 추가해야 할 것 같습니다.

[heatz123]

이건 새로 생각난건데, sub i32 0, %x와 같은 코드를 mul i32 %x, -1로 변환하는 것도 추가 구현되면 좋을 것 같습니다. 현재 c 코드가 llvm으로 변환될 때 int y = -x와 같은 코드를 어떤 식으로 변환하는지는 모르겠으나, sub를 이용해서 변환한다면 이 구현이 성능에 도움이 될 듯합니다.

[pzmaus]

이건 새로 생각난건데, sub i32 0, %x와 같은 코드를 mul i32 %x, -1로 변환하는 것도 추가 구현되면 좋을 것 같습니다. 현재 c 코드가 llvm으로 변환될 때 int y = -x와 같은 코드를 어떤 식으로 변환하는지는 모르겠으나, sub를 이용해서 변환한다면 이 구현이 성능에 도움이 될 듯합니다.

위에서 말씀하신 add i32 2, %x의 예시나 'mul i32 %x, -1'로의 변환 말고도 add i32 %a, -3 -> decr을 이용하게 변경 sub i32 %a, -2 -> incr을 이용하게 변경 정도도 생각하고 있기는 합니다.

몰론 sub i32 1, %a 이러한 경우도

%b = mul i32 -1, %a
incr(%b)

이런식으로 바꿀수도 있기는 한데, 자주 사용될지는 의문이기는 합니다. 줄수 제한에 문제가 되지 않는다면 추가할 예정입니다.

[heatz123]

이건 새로 생각난건데, sub i32 0, %x와 같은 코드를 mul i32 %x, -1로 변환하는 것도 추가 구현되면 좋을 것 같습니다. 현재 c 코드가 llvm으로 변환될 때 int y = -x와 같은 코드를 어떤 식으로 변환하는지는 모르겠으나, sub를 이용해서 변환한다면 이 구현이 성능에 도움이 될 듯합니다.

위에서 말씀하신 add i32 2, %x의 예시나 'mul i32 %x, -1'로의 변환 말고도 add i32 %a, -3 -> decr을 이용하게 변경 sub i32 %a, -2 -> incr을 이용하게 변경 정도도 생각하고 있기는 합니다.

몰론 sub i32 1, %a 이러한 경우도

%b = mul i32 -1, %a
incr(%b)

이런식으로 바꿀수도 있기는 한데, 자주 사용될지는 의문이기는 합니다. 줄수 제한에 문제가 되지 않는다면 추가할 예정입니다.

넵 좋습니다!

[pzmaus]

review 의견들 모두 반영해서 PR을 업데이트했습니다! 변경사항은 추가된 description을 확인해주세요