조회 수 94 추천 수 0 댓글 10
?

단축키

Prev이전 문서

Next다음 문서

위로 아래로 댓글로 가기 인쇄 첨부
?

단축키

Prev이전 문서

Next다음 문서

위로 아래로 댓글로 가기 인쇄 첨부

코드 최적화 - 더 나은 코드 생성

코드 최적화의 목표는 소스 코드를 실행하는 더 효율적인 기계어 코드를 생산하는 것이다.

유향비순환 그래프, Sethi-Ullman의 트리를 위한 최적 레지스터 할당, Proebsting-Fischer의 트리를 위한 최최적 레지스터 할당 등을 활용할 수 있다.

예를 들어 주어진 식 a + a * (b - c) + (b - c) * d을 최적화해보자. 이때 식에서 부분식 (b -c)가 반복되는 것을 볼 수 있다. 이때 b - c의 값은 항상 같으므로 한번만 연산하여 최적화를 할 수 있다. 그렇다면 어떻게 이를 구현할 것인가?

유향 비순환 그래프(DAG): 수식 트리에서 a * (b - c) 와 (b - c) * d가 자식 노드 (b - c)를 공유하는 식으로 한다. 트리와 달리 자식 노드는 복수의 부모를 가질 수 있다. 그러나 트리와 같이 루트 노드는 하나만 허용되며 순환이 발생해서는 안된다. 이경우 문장에서 공통된 부분식을 찾으려면 식에서 유향 비순환 그래프를 생성하고 이를 가지고 기계어 코드를 생성하면 된다.

 - 어떻게 DAG를 생성할 것인가: 트리 생성 코드에 노드 생성시 연산자, 좌피연산자, 우피연산자를, 리프 생성시 그 값을 해시 테이블에 저장한다. -> 해시 테이블을 검색하여 공통된 부분식이 있는지 찾는다.

 - 대입 연산을 어떻게 해결할 것인가?: 대입 연산 존재시 공통 부분식을 찾기 어렵다. 각 값이 서로 다른 노드가 될 수 있고, 따라서 변수들에 첨자를 달아 해결한다. 예를 들어 변수 x에 대입 연산을 하면 좌변을 새 노드 xi로 만들고, 기존의 xi-1로 생성된 노드들은 xi의 공통식으로 인정하지 않는다. 즉, x1 = x0 + 1과 같은 식으로 둔다.

 - 각 기본 블록(basic block, 반복, 분기문이 없는 코드의 단위)마다 DAG를 생성한다. 기본 블록의 DAG는 라벨된 노드를 갖는다. 각 리프들은 서로 다른 식별자로 라벨되며, (상수, 변수 관계 없음) 초기 값을 나타낸다. 자식 노드를 가진 노드들은 연산자로 라벨된다. 노드는 추가로 식별자 라벨을 가질 수 있는데, 자식 노드를 가진 노드는 계산된 값을 나타내고, 이때 식별자 라벨이 붙을 경우 대입이 발생했음을 나타낸다. 예를 들어 코드 {a  = b + c; b = a - d; c = b + c; d = a - d;}의 경우 DAG에서 {a0 = b0 + c0; b1 = a0 - d0; c1 = b1 + c0; d1 = a0 - d0;}로 라벨링되고, 트리는

cs420171116.PNG

 

   로 나타낼 수 있다.

 - DAG 생성 알고리즘 : (1)각 심볼들에 대해 비정의된 노드를 생성한다. -> (2)x = y op  꼴의 각 문장에 대해 (3-5) 반복한다. -> (3) 노드 y가 정의되지 않았을 경우 y를 나타내는 리프를 생성한 후 이를 노드 y의 정의로 한다. -> (4) <op, 노드 y, 노드 z>가 없을 경우 이를 생성하고 이 노드를 n이 가리킨다. -> (5) x를 노드 x의 라벨 리스ㅡ에서 제거한 후 x를 n의 라벨 리스트로 추가한 후 노드 x를 (4)에서 나온 n으로 정의한다.

 - 실제 활용: DAG 생성 알고리즘은 충분히 빨라서 실제 컴파일에 사용 가능하다. quad를 중간 코드로 쓰는 컴파일러 역시 공통 부분식을 찾기 위해 DAG를 쓴 후, 다시 quad로 변환환한다. 공통 부분식은 addressing, 배열 참조, 레코드에서의 필드 접근, 루프 내부 변수 관련 수식, 인수 접근 등에서 자주 사용되기 때문에 DAG는 유용하다.

 

코드 생성기 생성기: 코드 생성기 작성 역시 자동화할 수 있다. 이 경우 중간 코드와 기계의 내역을 가지고 좋은 코드를 생성하고 속도가 빠른 코드 생성기를 생성하는 것이 목적이다. 코드 생성기 생성기를 만드는 데는 트리 패턴 매칭과 명령어 매칭 방식이 사용된다.

 - 기본 구조: 파서 생성기와 유사하다. 중간 코드 -> 최적화 -> 테이블 기반 코드 생성기 <-> 테이블 <- 코드 생성기 생성기 <- 중간코드 및 기계 내역

 

트리 패턴 매칭: 프로그램이 트리의 집합으로 생성된다고 하자. 이때 트리 재작성 규칙인 BURS를 이용한다. 이때 기계 내역은 부분 트리를 기계어 코드의 조합인 단일 노드로 맵핑한다. 예를 들어 ri = a + b의 경우 {load r1, a; load r2, b; add r1, r2, r3;}로 맵핑하는 식이다. 쉽게 말해 부분 트리와 매칭되는 패턴을 찾아 패턴의 우변을 좌변으로 대체한 후 기계어 코드의 집합을 반환하는 것이다.

 - 기본 기술: 깊이 우선 순회와 단순한 local choice criterion을 가지고 작업한다. 여기에 여러 문자열 패턴을 매칭, 선형 폼으로 번역한 것이 Aho & Corasick 문자열 매칭(TWIG)이다. 한편, Aho & Johnson은 동적 프로그래밍을 이용하여 재생성과 비용 연산을 병행하여 각 지점마다 비용이 적은 방식을 채택하는 식으로 보완했다. 실제 트리 패턴 매칭 알고리즘을 사용할 수 도 있는데, 이경우 모든 부분 트리 매칭을 생성하여 그 중 가장 나은 것을 고르는 식이다.

 - LR 파서 사용: 패턴 매칭을 파싱 문제로 치환하여 해결 가능하다. LR파서는 컴파일러 제작자에게 익숙하기 때문에 LR파서 사용이 개발에 도움이 된다. 목표 기계를 서술하는 문법을 생성하면 치환이 가능하다. 그러나 문제는 이들 문법이 모호하다는 것이다. 이를 해결하기 위해 reduce 사이에 충돌이 발생하면 더 긴 reduction을, shift/reduce 충돌이 발생하면 shift를 우선하는 것으로 규칙을 정한다. 이러한 단점에도 불구하고 이 방식은 선형 실행 시간을 가진다는 장점이 있다.

 

저는 한다면 합니다


List of Articles
번호 제목 글쓴이 최근 수정일 날짜 조회 수 추천 수
10275 호주 되게 아까운듯 Primary 2018.06.16 2018.06.16 60 0
10274 히히ㅣ히히ㅣ히히ㅣ히ㅣ히히히ㅣ히히ㅣ히히ㅣ히ㅣ히히ㅣ히히ㅣ히힣 20 file Resurrection 2018.06.15 2018.06.07 240 0
10273 비밀번호 변경좀 고쳐줘요 2 야에쨩 2018.06.15 2018.06.15 77 0
10272 저 이번에 록색당 안찍었습니다 16 Resurrection 2018.06.15 2018.06.12 189 0
10271 아니 이인간들이 진짜ㅡㅡ 7 Resurrection 2018.06.15 2018.06.14 128 0
10270 저 월말에 대전가는데 12 BC둘기 2018.06.14 2018.06.12 102 0
10269 아아 여긴 녹색당 존이라고 한다 4 거냥거냥 2018.06.14 2018.06.14 88 0
10268 여기가 녹색당을 지지하는 싸이트라고 해서 방문했습니다. 2 deepsea 2018.06.14 2018.06.14 76 0
10267 잘들어 우리는 서울로 간다 2 Resurrection 2018.06.14 2018.06.14 69 0
10266 힘들 때 웃는 것은 1류다 4 file Primary 2018.06.14 2018.06.13 121 0
10265 황사와의 쌈 ㄸㄸㄸㅎㄷ 최부장네아랫집 2018.06.14 2018.06.14 30 0
10264 스브스....개표방송...CG... file Resurrection 2018.06.14 2018.06.14 56 0
10263 야구팬의 잠금화면 2 최부장네아랫집 2018.06.13 2018.06.12 86 0
10262 2018 자카르타 아시안게임 야구 대표팀 최종 엔트리 4 file BC둘기 2018.06.12 2018.06.11 67 0
10261 어떤놈이 그렸는지... 1 최부장네아랫집 2018.06.12 2018.06.11 67 0
10260 성우 미나세 이노리 6 BC둘기 2018.06.12 2018.06.11 72 0
10259 부활 나와서 이 글을 보거라 3 거냥거냥 2018.06.10 2018.06.01 139 0
10258 6월 3일 어제의 9시 이후 상황 8 BC둘기 2018.06.10 2018.06.04 146 0
10257 18.06.10 오늘의 노래 2 BC둘기 2018.06.10 2018.06.10 56 0
10256 사랑니 뺐음 8 거냥거냥 2018.06.09 2018.06.08 102 0
10255 피서객 팩트폭행 1 최부장네아랫집 2018.06.08 2018.06.08 83 0
10254 볼리비아전 선발 라인업 9 file Primary 2018.06.08 2018.06.07 118 0
10253 오늘부터 하복인데? 최부장네아랫집 2018.06.07 2018.06.07 69 0
10252 녹초가 된 몸으로 퇴근을 해도 직장인들은 꼭 뭔가를 한다.jpg 1 최부장네아랫집 2018.06.05 2018.06.04 97 0
10251 이세상에서 가장 편한 직업ㅎㅎㅎ 최부장네아랫집 2018.06.05 2018.06.05 171 0
10250 [밀리시타]미키 떴냐?? 2 BC둘기 2018.06.04 2018.06.02 85 0
10249 솔직히 애니존 많은 사람들이 다 튀어도 file Primary 2018.06.03 2018.06.03 113 0
10248 모기의 계절이 돌아왔네요 6 file Primary 2018.06.03 2018.06.01 118 0
10247 친구에게 선물을 받았는데요... 7 너프된꼬마 2018.06.03 2018.06.02 101 0
10246 방학이라 할머니댁 방문한 손주.. 1 최부장네아랫집 2018.06.02 2018.06.02 73 0
목록
Board Pagination Prev 1 ... 5 6 7 8 9 10 11 12 13 14 ... 352 Next
/ 352
서버에 요청 중입니다. 잠시만 기다려 주십시오...