myblog

Def-use chain Use-def chain Static Single Assignment(SSA) => improve def-use chains => each register has only one definition Phi Function Dominance Frontier => Dominator: 만약 어떤 노드 x가 Entry에서 y까지 가는 모든 path에 의해서 반드시 호출 되어지는 것이라면 그것을 우리는 y의 dominator x라고 부른다. => Strictly dominating: x가 y의 strictly dominator 라고 한다면, x는 y를 domiante 한다 하지만 x는 y가 아니라는 것이다. => Dominance Frontier: X 는 Y의 predecessor들중 한..

Instruction Level Parallelism Hardware Scheduling Data Dependence - RAW - WAR - WAW => WAW와 WAR은 제거 가능, RAW는 불가능(True dependence) Control Dependence List Scheduling Loop Scheduling

Compiler Backend 동작 1) Register allocation => 무한개의 virtual register를 유한개의 실제 register에 map 2) Optimmizer => programmer나 frontend의 비효율 제거 3) Scheduler = 단일 entry point를 가진다. 그리고 이 entry point node(header)가 그아래 형성된 모든 노드를 dominate(지배)함 Loop invari..

Register Cache Main Memory Disk Programmer: disk & memory Hardware: memory & cache Compiler: memory & register Graph Coloring => Colors = Registers => k-colorable => NP-hard problem => 인접한게 가장 적은 node부터 stack에 넣고 전부 다 넣은뒤 하나씩 꺼내면서 coloring Spilling => 색이 모자랄때 => 두가지 방법 1) spill이 발생했을때 한 register를 stack에 뺀다고 생각 2) 애초에 register(color) 2개 빼놓고 stack 이용, 2개는 stack management에 이용 Coalescing => interfe..

두 포인터가 메모리에서 동일한 개체를 가리킬 수 있는지 여부를 결정 Must-Alias May-Alias No-Alias Flow-Insensitive Analysis - Andersen analysis => precise but slow - Steensgaard analysis => fast but less precise

Live Variable Analysis => X가 이전에 defined 되었을때 X가 나중에 사용되는지 확인 OUT은 successor들의 IN의 합집합 IN은 USE와 (OUT - DEF)의 합집합 - register allocation의 live range를 알아보는 것 - scheduling - dead code 삭제 - Def-Use Chains, Use-Def Chains - out edges: successor nodes의 leading edge - in edges: predecessor nodes의 coming edge Reaching Definitions => node가 x를 쓸때 누가 x를 define했는지 찾음 unambigous - explicitly define ambigous -..

문법 체크 Stream of Tokens Abstract Syntax Tree IR Source → Lexer → Parser → FE' → Parsing Understanding sentence structure Parser가 필요한 이유: some program may have recuresive structures Finite Automata는 기억을 못하기 때문에 recursive 구조를 인식할 수 없다. => Push-down Automata => FSM + stack(에 기록) Context-Free Grammar set of productions로 구성됨 symbol -> symbol symbol ... symbol Symbol types: - Terminal: token types - No..

Tocken 단위로 나눔 Regular Expressions ↓ Lexer Generator ↓ Source → Lexer (Finite Automata) → Streams of Tokens Finite automata (FSM: Finite State Machine) state 갯수가 finite start state는 한개 Regular Expressions Base Cases: - Symbol - Epsilon: empty string Induction Cases - Alternation(M|N) - Concatenation(MN) - Repetition(M*) => including zero How lexer generator make Lexer from REs? 1. change REs to f..

Compiler: translate source language to a target language Source Program Front-End Lexical Analysis Syntax Analysis Semantic Analysis IR Code Generation Intermediate Representation Back-End IR Optimization Target Code Generation Target Code Optimization Target Program