[컴파일러] - IRs

Intermediate Representations

• Abstract Syntax Tree(ASTs)
• Linear Representations
• & more

What’s a Parser to Do?

• Idea: 중요한 포인트를 찾아내는 것(파서가 문백을 파악하고 의미적인 처리를 수행) → semantic action
  • LR에서 production이 reduce 될때 or LL에서 convenient point(파서가 현재 입력 스트림에 대해 적절한 규칙을 선택할 수 있는 지점)
    • 규칙이 S → aSb | ε이고 현재 입력이 'a'로 시작한다면, 파서는 S → aSb 규칙을 적용할 것이다. 여기서 'convenient point'는 a를 인식하는 시점
• 전형적인 semantic actions
  • 중간표현이나 구문트리를 구성하고 반환할 수 있음(Compiler)
  • 파서는 문법을 축소하는 동안 계산을 수행하고 최종결과를 반환할 수 있음(Interpreter)

Intermediate Representations

• 대부분의 compilers에서 파서는 program의 Intermediate Representations(IR)을 만든다
• 중간 표현은 소스 코드의 구조와 의미를 추상화한 형태로, 컴파일러의 나머지 부분에서 처리하기 쉬운 형식

IR Design

• 중간 표현(IR)의 설계는 컴파일러의 나머지 부분, 특히 최적화 및 코드 생성 단계의 속도와 효율성에 중대한 영향을 미친다.
• IR 설계시 고려해야할 속성
  • 생산하기 쉬워야 한다. → parsing 단계에서, (파서가 입력 소스 코드로부터 IR을 직관적으로 생성할 수 있어야함)
  • 조작하기 쉬워야 한다. → 최적화 및 기타 변환 과정에서 IR은 쉽게 조작될 수 있어야함
  • 표현력 → 구조를 보고도 어떤 의미인지 이해할 수 있어야함
  • 추상화 수준 → IR은 소스 코드의 고수준 구조를 적절히 추상화해야 하면서도, 최적화 및 타겟 코드 생성에 필요한 세부 정보를 충분히 제공해야함
• 컴파일러의 목표에 따른 트레이드 오프
  • 컴파일러가 고성능 코드를 생성하는 것을 목표로 할 때는 최적화를 위한 더 복잡한 IR을 선택할 수 있다. 반면, 컴파일 속도를 높이는 것이 중요하다면, 더 단순한 IR이 선호될 수 있응ㅁ
• 컴파일러의 다른 부분에 관한 트레이드 오프
  • 컴파일러 내에서도 다른 단계는 다른 형태의 IR을 요구할 수 있다. 예를 들어, 초기 최적화 단계는 추상화 수준이 높은 IR을 사용할 수 있는 반면, 코드 생성 단계에 가까워질수록 더 구체적인 IR이 필요할 수 있음

IRs의 Types

• 3가지 주된 카테고리
  • Structural
    • ex) tree
  • Liinear
    • 거의 machine code
  • Hybrid
    • 위 두개를 사용

추상화 정도

• key design decision: 얼마나 detail을 표현할건지
  • 다양한 최적화의 가능성과 수익성에 영향을 미친다
  • Structural IRs → high-level에 가깝다(사람과 가까움)
  • Linear IRs → low-level에 가깝다(기계와 비슷)
  • 그러나 위와같은 일반화가 항상 맞는건 아님

Structual IRs

• 일반적으로 source 코드 또는 다른 고수준 언어의 구조를 나타냄

• 큰 경향이 있음

• example) syntax trees

• source-to-source 변형에 특히 유용함

• Concrete Syntax Trees

  • 프로그램의 정확한 구문 구조를 나타내는 중간 표현(IR) 형태

  • 구현하기는 쉬움. But, 필요없는 디테일들이 많이 포함된다.

  • ex)

      expr::= expr+ term| expr – term| term
      term::= term* factor| term | factor| factor
      factor::= int| id | ( expr)

    x = 2*(n+m);

    

• Abstract Syntax Trees

  • concrete 보다 추상적

  • 위의 예시를 AST로

    

Linear IRs

• abstract machine을 위한 Pseudo-code

• abstraction수준의 다양성

• 간단하고 컴팩트한 데이터 구조

• examples) stack machine code, three-address code

• Stack Machine Code

  • 일반적으로 stack-based 컴퓨터에서 사용된다.

  • 장점

    • 매우 컴팩트하다
    • 생성하기 쉽다
    • machine code로 변환하기 간단하다.

  • x = 2*(n+m);

    

• Three-Address code

  • 다른 표현들이 많다

  • 일반 적인 form: x ← y (op) z

    • 한개의 연산자
    • 최대 3개까지 나올수 있다

  • example) x = 2*(n+m);

      t1 ← n+ m
      t2 ← 2*t1
      x ← t2

  • 장점

    • 컴팩트하다.
    • 실제 머신 코드와 유사하다
    • IR의 명시적 명명

IR중에 어떤 것을 사용해야 할까

• AST or 다른 structural 표현
  • 파서에 의해 생성되며, 컴파일러의 초기 단계에서 사용
  • 소스 코드에 가깝기 때문에, 의미 분석(semantic analysis)에 유용
  • 고수준 최적화를 수행하기에 적합한 구조
  • 예를 들어, 타입 체크, 범위 분석, 고수준 언어 구조의 변환과 같은 작업에 사용
• linear IR
  • 컴파일러의 후기 단계에서 사용
  • 기계 코드에 더 가깝기 때문에, 기계 관련 최적화에 유용
  • 선형 IR은 더 낮은 수준의 표현을 제공하며, 메모리 접근, 레지스터 할당, 명령어 선택과 같은 작업을 위해 사용