Compiler 개요

서울대 백흥준 교수님의 강의를 듣고 정리해 보았다. 잘못 이해한 부분이 있겠으며 학습차원에서 정리했다는 것을 먼제 얘기해야할 듯 하다.

 

1. 요즘들어 Compiler가 왜 주목받는가?
Compiler의 역사는 50년대쯤부터 시작이 된다고 한다. 그리고 70, 80년대를 거치면서 구문분석 및 기계어 변환에 관련된 기술은 이미 안정화 되었고 계속적인 발전이 진행되지 않고 있다고한다.

 

90년대 들어서면서 S/W의 복잡도가 크게 증가하였고 코드 최적화에 대한 이슈가 생길 듯 하였지만 H/W의 성능이 비약적으로 발전하면서 컴파일러 단계에서의 최적화 이슈는 크게 제기되지 못하였다.

 

그러나 요즘 들어서는 다소 상황이 다른다. S/W의 복잡도가 H/W의 복잡도 즉 일명 무어의 법칙에서 제시하는 증가폭을 넘어선 것이다. 이미 H/W진영에서는 별다른 방안을 강구하지 못한체 Core를 여러개 넣는 등의 Multi-core 체계를 대안으로 제시하고 있다. 즉, 한계에 다다른 것이다. 그리고 최적화에 대한 이슈는 이제 S/W에서도 무시할 수 없는 형국이 되어 버렸다. 그렇다면 Compiler는 이제 자동으로 최적환 문제를 해결하는 도구가 되는 것인가?

 

아직은 많은 문제가 있을 것이며 사용자의 조작에 의한 즉, 사용자가 몇몇 환경을 특정한 상황에 맞추어 세팅하는 방식에 의한 user interactive방식으로 진행이 되고 있는 듯 하다.

 

또한 H/W Architecture 설계 및 생산에 대한 속도가 빨라지고 일반인들도 손쉽게 시뮬레이션 환경등을 구성하고 실제 보드를 제작할 수 있는 환경이 되었고 이러한 시스템은 자체 Compiler를 내장하게 됨에 따라 Compiler 제작에 대한 이슈가 생겨나게 되었다.

 

그리고 전문 Tool에 의해서 Compiler제작이 용이해져서 일반적인 gcc와 같은 범용 compiler가 아닌 직접 제작한 compiler를 쉽게 사용할 수 있는 환경이 된 것이다.

 

2. Compiler는 어떠한 작업 단계를 가지게 되는가?
크게 Frontend와 Backend 단계로 나뉘게 된다. 전자는 IR(intermediate representation)을 생성하는 단계까지를 가리키고 후자는 IR를 가지고 최적화 작업을 수행하고 machine code를 생성하는 단계를 가진다.

 

Frontend는 lexical analysis, syntax analysis 그리고 semantic analysis의 단계로 구성이 된다.

lexical analysis는 일종의 각 단어(token)가 올바른지를 구성하는 단계이다. 예를 들어서 C언어의 경우 "switch"라는 키워드(token)이 있는데 "switck"로 작성이 되어 있다면 오류로 잡아내는 것이다. 어떻게 잡아낼까? token만을 별도 관리하는 사전과 같은 무언가가 있어서 찾아보고 없다면 Error를 보일 것이다. 각각의 token은 사전에 정의된 tag와 함께 매핑되어 보관된다. 사용자가 기입한 변수값은(ex. int i = 1;) id와 같은 특정 tag로 관리가된다.

 

다음은 syntax analysis로 구문분석을 하게 된다. 구문분석에는 BNF(Backus Naur Form)가 사용이 되는데 일종의 정규식과 같다. 즉, 코드의 구조 즉, 문법이 올바른지를 확인하는 것이다.
(BNF대로 구성되어 있는지 확인을 하기 위해서는 일반적으로 Stack기반의 "Push-down automata"를 사용한다.)

 

다음은 symantic analysis를 수행한다. 이는 의미론적으로 문제가 있는지 확인하는 것으로 대표적인 것이 type이 올바른지 확인하는 것이다.

(lex, yacc라는 대표적인 도구가 있는데 lexical analysis, syntax analysis를 수행하고 IR 코드 혹은 machine code생성을 지원한다. 즉, 이들 도구를 사용하면 간단한 compiler작성을 쉽게 할 수 있다.)

 

그렇다면 다음은 IR 코드를 생성해야할 것이다. 앞의 analysis단계를 거치면서 Parse Tree를 생성하게 되는데 이는 AST(Abstract Syntax Tree)로 변환된다. 즉, 불필요한 노드를 모두 제외하고 필요한 것들만을 남기는 것이다. 그리고 이러한 AST를 기반으로 Tree-address code를 생성하게 된다. 이것은 ASM(어셈블리어)의 바로 앞 단계 결과물로 어셈블리어와 같이 레지스트리를 표현하지는 않지만 +, -, *, / 그리고 GOTO와 같은 기본적인 연산로직만을 사용하여 표현되며 모양은 어셈블리코드와 많이 비슷한 형태를 가지게 된다. 이것이 바로 IR인 것이다.

 

자, 이제 Backend단계로 넘어가는 것이다. IR에서 ASM이 생성되고 이를 기계어로 바꾸는 작업은 손쉽게 진행될 수 있다.(거의 1:1 매핑일 것이다.)

 

3. Optimization은 언제 어떻게 수행되는가?
일반적으로 IR코드를 기반으로 작업에 들어간다. 가장 일반적인 것은 다음과 같다.

 

불필요한 라인 즉, 코드의 수행목적에 영향을 주지 못하는 라인은 제거하는 것이다. 예를 들어 int a = 0; 이후 어떠한 라인에서도 변수 a를 사용하지 않는다면 이는 불필요한 라인일 것이다.

 

또한 동일한 연산이 있을 경우 하나만을 남기는 작업도 있게 된다.

 

그리고 나누기 연산(DIV)의 경우 SHIFT연산으로 대체하여 instruction수행 cycle을 줄일 수 있다.

 

또한 Loop구문의 경우에는 looping 횟수를 줄일 수도 있다.

 

이러한 작업을 위해서 일단 IR코드를 블럭(BLOCK)단위로 나누게 된다. 블럭이란 Entry point와 Exit point가 하나인 가장 긴 단위를 가리킨다. 그리고 각각의 블럭 내부에서의 최적화 그리고 블럭간의 관계를 분석하여 최적화 등 작업을 진행시키게 된다.

 

최적화 기술은 100가지가 넘는다고 한다. GCC의 경우에도 170여가지나 된다고 한다. 그리고 이들 100여가지를 어떻게 조합하여 적용하는가도 중요한데 100!정도의 경우의 수가 나오기에 이 또한 이슈가 될 수 있다고 한다.