mojo's Blog

Code Generation 연산 레지스터가 여러 개인 경우: ● 구문 트리를 만들 때 각 노드의 부분 트리를 계산하는 데 필요한 레지스터의 수 를 먼저 계산한 다음 표시. 레지스터의 수를 label로 가진 구문 트리에서 목적 코드를 생성해낸다. ● 이 방법을 통해 STORE연산이 필요하지 않기 위한 레지스터의 수를 구할 수 있다. ● 레지스터의 수를 때때로 A. Ershov 수(Ershov number)라 부른다. 식 E를 계산하는 데 필요한 레지스터의 수를 CR(E)로 표시하면 [알고리즘]에 의해 구문 트리로부터 CE(E) 값을 구할 수 있다. Label을 붙이는 순서는 터미널 노드에서 루트 노드로 진행하며, 필요한 레지스터의 수가 큰 쪽의 부분 트리부터 목적 코드로 변환해가면 된다. [알고리즘] 레..

Machine-dependent Optimization 기계 종속적 최적화 기법Machine-dependent Optimization ● 기계의 특성에 따라 달라질 수 있음 ● 중복 명령어 제거, 효율적인 명령어 선택, 레지스터 할당과 배정, 명령어 스케줄링 등이 있음 중복 명령어 제거 ● 핍홀 최적화 기법에서 사용하는 것과 동일 ● 중복되는 로드 명령문이나 저장 명령문을 제거함으로써 최적화하는 방법 효율적인 명령어 선택 ● 동일한 기능을 가진 더 효율적인 명령어로 대치함으로써 최적화하는 방법 ● ex) 소스코드 x = x + 1에 대한 명령어는 다음과 같다: LOAD R1, x ADD R1, 1 STORE x, R1 컴퓨터가 레지스터나 메모리에서 1을 증가시키는 INC(increase) 명령어를 가질 ..

Directed Acyclic Graph (DAG) 자료 흐름 분석이 완료된 후 기본 블록에 대한 코드를 생성할 때, 각 블록에 대해 DAG(directed acyclic graph) 생성하여 활용한다. ● DAG는 값이 어떻게 계산되는지를 그림으로 나타내준다. ● DAG는 주로 블록 내부에서 사용되지만, 블록 외부에서 어떤 문장이 그 문장에서 계산한 값을 사용하는지 알아볼 수 있으므로 매우 중요하다. DAG는 모든 산술식에 대한 노드를 가진다. ● 내부 노드(interior node)는 연산자를 나타내고 그 자식 노드는 피연산자를 나타낸다. ● 터미널 노드는 id나 constant이고 중간 노드는 연산자이다. ● 노드 옆에 여러 개의 id를 놓을 수 있으며, 이는 노드의 계산 결과를 이 id들이 공유함..

Parameter Passing Parameter: actual parameter, formal parameter ● 실 매개변수와 형식 매개변수는 서로 값을 주고받는다 (parameter passing) ● 여러 가지 parameter passing 방법이 있음 ○ 참조 호출(Call by reference): 포트란77 ○ 값 호출 (Call by value): C 예시) a[i] = a[j] ● 산술식 a[j]는 값을 나타내는 r-값(right value) ● a[i]는 a[j]의 값이 있는 메모리의 위치인 l-value(left value, location value)을 나타낸다. ○ l-value: 산술식이 나타내는 기억 위치 ○ r-value: 메모리에 저장될 값 Call by Value 값 ..

Structural data type 기본 자료형(elementary data type) ● 하나의 이름이 하나의 자료 객체(data object)를 가진 것 ● 정수, 실수, 문자형 등 구조적 자료형(structured data type) ● 하나의 이름에 여러 개의 자료 객체가 있는 것 ● 레코드, 배열, 문자열, 집합, 트리 등 ○ 레코드, 구조체: 이질(heterogeneous)의 자료 개체들을 하나로 묶고 이름을 부여하여 하나의 자료형을 선언 ○ PL/I, 코볼, 파스칼, C, 알골 등과 같은 언어는 레코드를 사용할 수 있는데 구체적 표현은 언어마다 조금씩 다르다. Record 레코드 ADDRESS ● PERSON, STREET, CITY와 같은 그룹 항목 ● 각 항목들은 다시 하나 이상의 기본..

Intermediate code는 ● semantic analysis 단계에서 만들어진 syntax tree를 이용하여 생성되거나, ● 문법 규칙이 reduce 될 때마다 syntax-directed translation으로 생성된다. ● intermediate code를 생성하는 데는 intermediate language를 사용한다. 컴파일러의 frontend와 backend를 연결해주는 기능을 한다. Intermediate Code 생성 방법 ● intermediate code generator (ICG)를 이용 ○ 파스 트리 또는 구문 트리를 순회하면서 효과적인 intermediate code를 생성 ● syntax-directed translation (SDT) 방법 ○ CFG의 각 생성 규칙에..