본문 바로가기

전공/프로그래밍 언어 및 컴파일러

 (21)
Lec18. Register Allocation - 15주차 2강 마지막이다!!!! 12월 11일 - 15주차 2강* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다. 백엔드의 핵심은 레지스터 할당임레지스터 할당IR을 사용 가능한 레지스터 수에 맞춰 재작성함IR 변환 과정에서는 수많은 임시 변수가 생성되는데, 실제 하드웨어는 제한된 레지스터 수량만 사용 가능사용이 끝난 변수에 할당된 레지스터를 재사용할 수 있음. a,e는 dead 후 동일한 레지스터에 할당 가능함기본 아이디어프로그램에서 한 번에 t1, t2 중 하나만 사용되면 둘은 같은 레지스터 공유 가능만약 t1,t2가 동시에 live이면 두 변수는 레지스터 공유 불가능workflow1단계: liveness 분석2단계: 레지스터 간 간섭 그래프 생성. 각 노드는 변수를..
Lec17.Optimization (2) - 15주차 1강 12월 9일, 15주차 1강부제: Data Flow Analysis* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다. Reaching Definition Analysishttps://estudies4you.blogspot.com/2017/12/reaching-definitions-in-dataflow.html이 모든 것을 이해하는데 지대한 도움을 준 글.다만! 다른 자료들과 다르게 이 자료만 out의 초기화 값을 gen으로 설명하고 있음. 그런데 다른 자료들 다 찾아봐도 in, out은 모두 공집합으로 초기화하라고 하고 있음. 이부분에 주의할 것.아래 ppt대로 설명하긴 하겠지만, 지금 한 번 쭉 정리하고 내 말로 한 번 설명하겠음특정 변수에 값을 할당한..
Lec16.Optimization (1) - 14주차 2강 12월 4일, 14주차 2강* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다.middle-end optimizer: 중간표현을 입력받아 효율적인 코드로 변환하는 역할.코드 의미를 보존하면서도 불필요한 중간 변수나 연산을 제거해 최적화된 결과 생성코드 최적화 방법공통 부분식 제거표현식 E가 프로그램 내에서 한 번 계산된 이후, 해당 변수 값이 변경되지 않았다면 E는 공통 부분식으로 간주동일한 계산 반복할 필요 없이, 이전 계산 결과 재사용해 프로그램 최적화copy propagationu=v와 같은 복사문 이후, u가 재정의 되지 않는 한 u 대신 v를 사용하는 최적화 기법중간 변수 없이 값 바로 사용하는 방식, 코드 간결성과 실행효율 높임불필요한 변수 제거..
Lec15.lR Translation (2) - 14주차 2강 부제: Control-Flow Graph 14주차 2강. 2024.12.04. three address code - 각 식이 최대 3개의 피연산자를 갖도록 함. 단순한 연산 단위로 분해해 분석과 최적화 용이하게.global optimization을 효과적으로 수행하기 위해 3주소 코드를 CFG로 변환함. CFG는 프로그램 제어 흐름을 그래프로 표현한 구조. 최적화와 정적 분석을 위해 사용.Node는 Basic Block을 나타냄. 분기 없이 연속적으로 실행되는 명령어 집합Edge: Basic Block 간의 Control Flow. 조건문, 반복문의 흐름에 따라 블록이 연결됨.basic block은 분기가 없는 명령어의 최대 연속 집합. 중간에서 흐름이 끊기지 않고 처음부터 끝까지 순차적 실행.basic..
Lec14.IR Translation (1) - 14주차 1강 부제: Automatic Translation12월 2일, 14주차 1강* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다.컴파일러 디자인의 복잡도를 줄이기 위해 IR을 사용한다x=0, t1=0x에 t1 값을 할당t3에 x값을 할당t4에 1을 할당t2에 t3과 t4의 합을 할당t2를 write한 후 정지초기화, sum=0, i=02:SKIP: 반복문 시작조건 검사t4에 i값 복사t5에 10 복사t3에 t4조건이 거짓이면 3으로 점프반복문 본문sum=sum+i를 계산해 sum에 저장i++ 연산을 수행반복문 시작으로 돌아가기 위해 goto23:SKIP: 반복문 종료출력 및 종료sum값을 출력하고 HALT 소스 언어과 타겟언어 사이의 자동변환 절차를 정의S: 변..
Lec13.Semantic Analysis (4) - 13주차 1강/2강 11월 25일, 27일 / 13주차 1강, 2강* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다.고정점 계산반복문처럼 state의 변화가 있는 명령문에서 stable state를 찾기 위해 고정점 계산을 함고정점은 항상 종료되는가? 종료되기 위해서는 추상 도메인의 lattice가 finite height를 가져야 함그러나 실제 도메인은 infinite height를 가져, 고정점 계산이 끝나지 않을 수 있음Widening 연산자 - 고정점 계산이 종료하지 않는 문제를 해결하기 위해 도입상태 병합(join) 과정에서 빠르게 상위 상태로 approximation하여 반복 과정을 종료하도록 함무한 높이를 가진 lattice에서도 고정점 계산의 종료를 보장정확성..
Lec12.Semantic Analysis (3) - 13주차 1강 11월 25일 13주차 1강* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다.대충 Lec 11에서 계속 배우던 연산, 불리안, 코맨드 구현의 코드를 깃허브에 올려놓으셨단 뜻아래 렉쳐 슬라이드에서는 코드 중 일부를 가져와서 설명함 module Sign = struct type t = Top | Bot | Pos | Neg | Zero | NonPos | NonNeg | NonZero let porder : t -> t -> bool = fun s1 s2 -> match s1, s2 with | _, _ when s1 = s2 -> true (* 동일한 값은 포함 관계 성립 *) | Bot, _ -> true (* NONE은..
[Lec.Halting] Undecidability, Halting Problem - 11주차 2강 11월 13일 - 11주차 2강정지 문제를 대학 전공 수업에서 한 번도 다루지 않았다는 사실에 충격을 받은 교수님...급기야 추가 렉쳐를 기획하게 되는데....* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다. 예, 아니오로 대답할 수 있는 문제유한 오토마타가 문자열을 인식하는가? CFG가 ambiguous 한가?결정 가능 문제: 모든 입력에 대한 올바른 답(예/아니오)를 유한 시간 내에 출력 가능한 알고리즘 존재결정 불가능 문제: 모든 입력에 대해 항상 올바른 답을 출력할 수 있는 알고리즘을 만드는 것이 불가능한 문제TSP 외판원 문제 -  다른 문제로부터 결정 문제로 변가능최적화 문제: 모든 도시를 정확히 한 번씩 방문하고 시작 지점으로 돌아오는 최단..
Lec11. Semantic Analysis (2) - 11주차 2강, 12주차 2강 11주차 2강, 12주차 2강 11/13, 11/2011/18은 휴강 lec10에서 언급한 내용임Abstract Interperetation의 주요 단계abstract domain: 변수는 구체적인 값 대신 추상화된 값으로 표현 됨변수의 값이 가질 수 있는 범위 또는 특성을 정의, 구간 / 옥타곤, 짝홀 등구체적인 의미로는 7에 2를 더하면 9가 되지만, 추상적인 의미로는 홀수에 2를 더하면 홀수이다연산, 불리안 판별, command 처리에 대한 simple language 만드는 과정추상 도메인 개요새로운 기호들이 등장하는데, 본문 슬라이드 내용과 같고이상하게 생긴 육각형은 맨위의 any부터 시작해서 아래로 뻗어나오는 tree처럼 생각하면 됨any: 모든 값 포함non-pos: 0 또는 음의 정수, n..
Lec10. Semantic Analysis (1) - 11주차 1강 11월 11일, 11주차 1강* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다.  soundness: 정확성분석기가 p가 안전하다고 생각하면, 실제로 p는 안전해야 한다만약 p가 안전하지 않다면, 분석기는 반드시 unsafe로 판단해야 한다분석기가 error를 놓치지 않아야 한다. no false negativecompleteness: 완전성p가 실제로 안전하다면, 분석기는 반드시 p의 안전성을 증명해야 하낟분석기가 p를 unsafe로 판단했다면, p는 실제로 안전하지 않음분석기가 안전한 프로그램을 위험하다고 판단하지 않아야 한다. no false positive이상적인 분석기: no false negative, no false positivehard l..

티스토리툴바