레이블이 compiler인 게시물을 표시합니다. 모든 게시물 표시
레이블이 compiler인 게시물을 표시합니다. 모든 게시물 표시

2017-11-26

[C++] as-if rule - 소스에 적힌 순서대로 실행되지 않는 이유

 as-if rule이란, 프로그램의 실행 결과가 변하지 않는다면 소스에 적혀있는 것이 아닌 다른 방법으로 실행하는 것을 허용하는 규칙을 말한다. 이러한 규칙을 as-if rule이라는 이름으로 부르는 것은 C++에서만 찾을 수 있지만, C를 비롯한 다른 언어에서도 이러한 부류의 최적화를 허용한다.

 as-if rule을 허용하는 이유는 크게 두 가지로 보인다. 우선 컴파일러의 최적화를 방해하지 않기 위함이다. 만약, 표준 문서에서 적용할 수 있는 최적화 방법을 화이트 리스트로 관리한다면, 새로운 최적화 기법이 나왔을 때, 컴파일러가 이를 적용하기 위해서는 표준을 수정해야 한다. 하지만 표준에서 허용하지 않는 동작만 기술해두면 컴파일러 구현체에서 새로운 최적화를 구현하는데 조금 더 자유로울 수 있다.
 두 번째 이유는 C++이 가정하는 abstract machine이 엄밀하게 정의되지 않았기 때문이다. 일반적으로 C++의 실행 타깃은 native processor다. 이 프로세서는 제조사에 따라서, 혹은 칩 아키텍처에 따라서 다른 특성을 가질 수 있는데, C++ 표준은 이때 실행할 프로세서의 종류나 특성을 한정 짓지 않는다. CPU 별로 메모리 오더, 레지스터 크기, 레지스터 개수 등이 전부 다르기 때문에 가능한 최적화도 전부 다르다. 따라서 표준에서 어떤 최적화를 허용할지 명시할 수 없고 as-if rule이라는 이름으로 코드의 실행결과를 바꾸지 않는 최적화를 전부 허용하도록 명시한 것이다.

2014-11-28

컴파일러의 구조 - front-end와 back-end

 지난번 글에서 보여준 컴파일러의 구조를 잘 보면, Code Generator를 전후로 machine independent한 작업과 machine dependent한 작업들로 나누어지는 것을 알 수 있다.
 여기서 machine independent한 작업들(Lexical Analyzer, Syntax Analyzer, Semantic Analyzer, Intermediate Code Generator, Machine-Independent Optimizer)을 컴파일러의 front-end라고 부르고, machine dependent한 작업들(Code Generator, Machine-Dndependent Optimizer)를 컴파일러의 back-end라고 부른다.

 현대의 컴파일러들은 대부분 front-end와 back-end가 확실하게 나누어진다. Front-end와 Back-end 사이를 연결해 주는 것을 Intermediate Representation(a.k.a. IR)이라고 한다. IR은 컴퓨터가 실행할 프로그램을 표현해주는데 여러 가지 형태로 표현될 수 있다.1) JVM이나 .Net 같은 가상머신에서는 쓰이는 bytecode도 일종의 stack-based IR이다.

1) http://cs.lmu.edu/~ray/notes/ir/

2014-11-27

컴파일러의 구조

 사람이 읽기 쉽게 쓰여 있는 소스코드를 기계가 실행할 수 있는 byte 코드로 변환하여 주는 프로그램을 컴파일러라고 한다. 소스를 그에 대응하는 기계어의 집합으로 바꿔주는 일은 언뜻 보기에는 간단해 보이지만, 최적화나 platform dependent한 문제들이 엮이면 쉽지 않은 작업이다. 그래서 복잡한 작업을 최대한 간단하게 만들기 위해 현대의 컴파일러는 다음과 같은 복잡한 구조를 가진다.

  Source Code
Lexical Analyzer
  Token Stream
Syntax Analyzer
  Syntax Tree
Semantic Analyzer
  Syntax Tree, Symbol table
Intermediate Code Generator
  Intermediate Representation, Symbol Table
Machine-Independent Optimizer
  Optimized Intermediate Representation, Symbol Table
Code Generator
  Machine Code
Machine-Dependent Optimizer
  Optimized Machine Code

 위의 구조는 컴파일러 교재로 유명한 dragon book1)이 설명하고 있는 모델이다. 이런 복잡한 구조를 가지는 이유는 dragon book의 표지 그림이 상징적으로 설명해준다.
 앞에서 말했듯이 컴파일러가 해야 하는 일은 매우 복잡하해서 이 complexity of compiler design을 상대하기 위해서 고안된 모델이다.
 하지만 이는 어디까지나 복잡한 일을 쉽게 하기 위해서다. 어디까지나 일을 쉽게 하기 위한 것인 만큼 이 구조에 얽매일 필요는 없다.

 하지만 이보다 단순한 구조로 컴파일러를 만들기는 쉽지 않을 것이다. 그래서 경우에 따라 컴파일러를 새로 만드는 것이 아니라, 기존의 언어에서 제공하는 기능을 이용하여 언어를 확장하여 DSL을 만들거나(Lisp의 macro나, Scala의 implicit 등이 여기에 해당한다.), 기존의 언어로 convert하여 기존의 언어 컴파일러를 이용하는 경우(JVM 위에서 돌아가는 Rhino engine이 대표적이다.)도 있다.


1) LAM, Monica, et al. Compilers: Principles, Techniques, and Tools. 2006. p.5