컴퓨터/컴파일러 (11) 썸네일형 리스트형 11. Loop Optimization 코드를 실행하게 되면 많은 시간이 loop구문에서 소비되게 된다.따라서 반복되는 부분을 최적화 한다면 빠른 속도를 얻을 수 있다.Dominator모든 CFG는 start node s0가 있고 이는 predecessor가 없다그리고 d dominates n이라는 것은 만약 s0에서 n으로 직선 경로가 주어질 때 무조건 d를 지나야 n에 도달할 수 있을 때를 의미한다.Dom[n]은 노드 n에 dominate되는 모든 노드 집합을 의미한다.Immediate Dominator노드n 바로 직전의 마지막 dominator를 의미한다.IDom[n]으로 표기하고 이는 자기 자신이 될 수 없고, n을 dominate한다.그리고 n의 다른 dominator를 dominate하지 않는다.따라서 모든 노드 n은 정확히 하나의.. 10. Register Allocation Interference Graph 기본적인 아이디어는 각각의 노드가 virtual register를 대표하고 노드간에 edge 가 생기면 live range가 있다고 생각한다.만약 노드n에서 def[n] = {a}이면 interference edge for every b ∈ out[b]을 추가한다이 내용을 바탕으로 그래프를 그리면 아래와 같이 구할 수 있다. Graph Coloring intergerence graph를 통해 구한 결과에서 각각의 그래프의 노드를 색을 할당해 칠하는 것이다.이때 각각의 노드는 virtual register를 의미하고, 색은 real register를 의미한다.따라서 K개의 machine register가 있다는 뜻은 K개의 종류의 색을 칠할 수 있다는 뜻이다.. 9. Liveness Analysis Front-End Compilation 프로그램 코드를 직접 번역하는 것으로 무한개의 virtual register가 있다고 가정하고 진행을 한다.하지만 실제로 physical register에 할당을 할 때는 갯수가 정해져 있기 때문에 이에 맞춰서 다시 진행해준다.그리고 processor architecture에 맞추지 않아 불필요한 것이 들어갈 수 있다. Back-End Compilation virtual register를 실제 physical register로 mapping하는 부분이다.불필요한 부분들을 다 제거하는 dead code elimination을 진행하여 아무 동작 안하고 선언만 되어있는 부분을 다 지운다. Control Flow Graph (CFG) graph의 노드는 instruc.. 8. Instruction Selection IR언어는 각각의 tree마다 하나의 연산만을 표현한다.예를들어 다음과 같은 연산의경우MEM(BINOP(PLUS, TEMP(t), CONST(c)))아래의 그림과 같이 tree로 표현할 수 있다. 메로리 접근을 할 때 load/store instruction을 통해서 한다.이때 각각의 명령어는 어떤 레지스터도 접근 가능하다.그리고 레지스터 중에서 r0은 special register로 항상 0을 가진다.각 명령어의 대기 시간은 한 사이클이고 이 한 사이클에 한 명령만 가능하다. 이제 기본적인 연산에 대해서 보면 다음과 같다.ADD rd= rs1 + rs2 이는 기본적인 덧샘을 하는 연산이다.ADDI rd= rs + c 이는 특별히 레지스터에 상수를 더해주는 연산이다.SUB rd= rs1 – rs2 이는 .. 7. Basic Blocks and Traces IR Tree의 문제점CJUMP의 경우 원래는 true와 faluse에 따라서 다른 label로 이동을 해야하지만 실제는 false인 경우 그냥 다음 instruction을 실행한다. ESEQ, CALL의 경우 동작을 하면서 side effect가 발생할 수 있어 동작의 예측을 하기 힘들다.그리고 이러한 특성 때문에 계산하는 순서에 따라서 결과가 다르게 나오는 문제가 생긴다. Canonicalization canonical tree는 SEQ와 ESEQ를 없애고, 각각의 CALL의 parent는 EXP이거나 MOVE이어야한다. canonicalization은 다음과 같은 방법으로 수행이 된다.1. ESEQ를 제거하도록 tree를 수정한다.2. CALL이 있으면 CALL의 parent가 EXP나 MOVE가.. 6. Translation to Intermediate Code Intermediate Representation(IR)기계어 연산을 표현할 수 있는 추상적 언어로 소스 언어와 무관하고 컴파일러마다 IR이 다를 수 있다.IR은 필수는 아니지만 호환성을 위해서 있으면 좋다.왜냐하면 IR을 사용하면 언어간에 바꾸기 편하고, 이해하기 쉽고, CPU의 차이를 잘 반영할 수 있기 때문이다. CISC: 1개의 복잡한 일을 다루는 것으로 더 복잡한 코드를 1개의 명령어로 표현 가능하다RISC: 명령어가 단순한 작업일 때 사용하는 것으로 더 많은 명령어가 사용 가능하다. Assembly Languageword는 프로세서가 다룰 수 있는 단위로 일반적으로 레지스터의 크기를 의미한다.여기서 %eax, %ecx, %edx, %ebx, %esi, %edi는 32-bit register를 .. 5. Activation Records Memory LayoutText : 프로그램의 코드를 저장하는 부분이다.Data : global 변수를 저장하는 부분이다.Stack : 파라미터, local 변수가 저장된다.Heap : 동적으로 할당되는 부분이 저장된다. 여기서 stack영역에 저장되는 함수의 정보를 stack frame이라고 하고 마지막 위치를 SP(stack pointer)로 표시해준다.SP아래의 부분은 garbege로 간주되고 stack에서 push를 하게 되면 sp에 1을 빼고 pop을 하면 1을 더해주는 방식으로 동작한다. Stack Frame Organization 모든 컴파일러가 사용하는 표준 레이아웃 체계를 지정한다.어떻게 구성하고 배치할지는 규칙을 통해서 정한다. Registers 레지스터는 메모리보다 빠르기 때문에 가.. 4. Semantic Analysis Semantic Analysis는 의미론적 분석으로 문장에서 의미를 파악해 프로그램의 의미를 분석하여 맞는지 확인한다.그리고 결과적으로 abstract syntax tree를 intermediate representation(IR)로 변환한다.Semantic Analysis에서는 구조는 맞지만 identifier가 1번만 정의 되었는지, 상속 관계가 잘 되었는지, type이 잘 정의 되었는지 등을 확인한다. Symbol Table 식별자를 그들의 type과 location에 mapping시킨것이다.위와 같이 화살표를 통해서 표기를 하는데 식별자는 해당 type으로 묶여있다는 것을 나타낸다. ▪ Imperative Style 1개의 global environment를 가지고 table에 entry를 넣고.. 이전 1 2 다음 목록 더보기
