[Compiler] Code Optimization의 중요성

Compiler의 기본 구성은 다음과 같이 나눌 수 있다.

- Lexical Analysis

- Syntex Analysis

- Semantic Analysis

- Optimization

- Code Generation

보통 Compiler의 가장 기본적인 역할은 high level language를 low level language로 바꿔주는 번역기의 역할일텐데, 초기에 등장한 프로그래밍 언어들은 위의 요소들이 비슷한 비중을 차지했다. 

하지만 현대의 컴파일러는 다른 것보다 code optimization이 중요시되고 있다. 마침 OCW 중 Computer Language Engineering 수업중에 Code Optimization에 관한 내용을 쉬운 예제를 토대로 소개하고 있어서 한번 정리해보고자 한다.

예제는 다음과 같다.

물론 딱봐도 필요없는 부분도 있을 것이고, 소프트웨어 공학을 수강한 사람이라면 어떻게 하면 처리 속도를 향상시킬 수 있는지에 대한 알고리즘도 머리에 떠오를 것이다. 그런데 나는 전자도 후자도 아닌 케이스이기에 그냥 하나하나씩 적용해보고자 한다.

맨처음 적용할 수 있는 방법은 Constant Propagation이다. 일단 상수부분을 고려해본다.

딱 보면 상수를 차지하고 있는 부분은 x,y가 0으로 할당되어있다. 이 부분은 상관이 없다. 그런데 문제는 for loop 내에서의 연산이다. 딱 보면 알겠지만 y에 영향을 끼치는 요소는 전혀 없고, 심지어 y로 인해서 두번째 수식이 전혀 쓸모없게 되어버린다. compling시 constant를 load/store 하는 것은 memory를 사용하는, 소위 말하는 비싼 작업이기 때문에 될 수 있으면 이를 배제한 방법을 먼저 찾아보는게 중요하다. 그래서 다음과 같이 y를 대체할 수 있다.

다음으로 적용할 수 있는 방법은 Algebraic Simplification이다. 이 부분은 너무 뻔하다. 앞에서 잠깐 언급한 것처럼 y=0이라는 값이 들어가면서 두번째 수식이 x=x라는 전혀 무의미한 수식을 가지게 된다. 우선 0이 들어가면서 소거되는 부분을 제거하는 것이 이 방법의 목적이다.

다음이 Copy Propagation인데 이 부분은 x=x라는 무의한 부분을 제거하는 부분이다.

다음은 Common Subexpression Elimination 이다. 이름에서 나오듯 반복되는 부분에 대한 제거를 다루는 부분이다. 위 식에서 반복되는 구문은 바로 i+1이 거듭제곱되는 부분이다. 같은 것을 곱하는 연산일지라도 곱하기 전에 더하는 연산이 두번 수행된다. 이러는 것보다는 사전에 더하기를 한번만 결과를 바탕으로 연산을 할 수 있기 때문에 다음과 같이 variable을 두고 수식을 요약할 수 있다.

다음으로 적용할 수 있는 방법은 Dead Code Elimination인데 우리는 이식을 보면 어떤 값이 필요 없는지를 금방 찾을 수 있다. 바로 y이다. 당연히 0으로 저장하는 부분도 줄일 수 있을 것이다.

다음은 Loop invariant Removal 이다. 아까 앞에서 적용했던 Common SubExpression Elimination의 내용처럼 loop 내의 연산은 최대한 variable로 처리해서 미리 계산할 수 있게끔 하는 것이 loop 연산을 수행하는데 있어서 최적화 할 수 있는 부분이다. 이또한 새로운 variable을 두고 다음과 같이 수정할 수 있다.

이제 적용할 수 있는게 Strength Reduction이다. 이 관점은 두가지 부분에 적용해볼 수 있다. 맨 처음은 for loop 내에서 x값의 변화를 봐야 한다.

 x에 관한 수식에서 for loop 내에서 변화가 있는 변수는 i 뿐이다. 나머지는 loop 밖에서 정의되었기 때문에 loop 내에서는 constant나 마찬가지이다. 그러면 i 값에 따라서 x 값을 변화시키면 다음과 같이 표현할 수 있게 된다.

그럼 이 부분도 따로 변수로 뽑을 수 있지 않을까 해서 다음과 같이 수정할 수 있게 된다.

한가지 더 줄일 수 있는 부분이  u 값이 정의되는 부분이다. 얼핏보면 상수와 변수가 곱해지고 나눠지는 부분이기에 축약될 부분이 없어 보인다. 하지만 한가지 간과된 부분이 복잡도이다. 사실 곱하기나 나누기는 더하기와 빼기의 반복 연산이다. 따라서 연산에 따른 Complexity도 곱하기나 나누기가 더 복잡하다. 실제로 논리회로를 구성해보면 multiplier와 Adder를 비교해보면 multiplier가 훨씬 더 복잡하고 크다. Optimization의 목적은 최대한 complier가 high level language를 low level로 번역하는데 있기 때문에 이런 연산 속도를 개선하는 것이 중요하다. 

 이 때는 변수들이 binary로 저장되는 점에서 착안해, shift 연산을 하게 하면 조금더 빠르게 연산을 수행할 수 있다. 4를 곱하는 것은 변수를 2만큼 shift left함으로써 같은 결과를 얻을 수 있다. 그래서 이렇게 수정할 수 있다.

이밖에도 앞에서 언급한 것처럼 Memory의 load/store를 최대한 피하기 위해서 register에다 relocation하는 방법도 있기도 하다. 

지금까지 수행한 것이 Complier를 구성하는 요소중 Optimizer가 하는 역할이다. 그래서 결과를 비교해보면 다음과 같다.

실질적으로 별 차이가 없어보이지만, Optimization의 다음 단계인 Code Generation으로 넘어가면 두 코드가 확연하게 차이난다.

더불어 speed 측면에서도 약 2.5배 정도의 성능향상이 나타난 것을 확인할 수 있다. 물론 코드의 크기가 줄면서 가독성 측면에서도 우위를 나타낸다. 이런 간단한 코드 내에서도 2.5배의 속도 향상을 나타냈으니 실제로 코드에 적용되면 그 효과는 더 크게 나타날 것이다.

이때문에 modern complier에서는 Optimization이 많은 비율을 차지한다. 지금까지도 계속 언급했기도 했지만 일단은

- Performance / Speed 에서 큰 효과를 나타낼 수 있고,

- Code Size가 작아지기 때문에 최종적으로 나오는 결과물의 size 역시 줄일 수 있으며

- 또한 불필요한 연산을 사용하지 않으므로 그에 따른 Power Consumption에서도 이점을 차지할 수 있다.

- 또한 코드의 줄 자체도 축약되었기 때문에 Security나 Readability관점에서도 사용자에게 적합해지며

- 이 때문에 Debugging 하기가 쉬워진다.

- 물론 코드 complie 시에도 처리되는 구문이 줄었기 때문에 빠르고 효율적인 compilation을 추구할 수 있다.

잘 보면 알겠지만 단순히 소프트웨어 측면에서 고수준 언어만 중요한게 아니라 하드웨어 관점에서도 보면서 저수준 언어도 볼 줄 알아야 코드를 최적화하는데도 도움이 많이 될 것 같다.

Resource :

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-035-computer-language-engineering-sma-5502-fall-2005/lecture-notes/l1-course-administration-information-and-overview/