CSE4120 서강대학교 기초컴파일러 Prj3

실제 c가 아니라 제한사항이 있는 mini-c 상에서 optimization생각들 모음

마지막 프젝을 만점 받지는 못했지만, 할 때 생각한 아이디어들 모음
따로 유명한 최적화 방법에 대한 공부는 하지 않았다. 교수님이 코드/tc는 공유하지 말라 하셔서 아이디어 정도만 적는다. 사실 오래 고민한게 아까워서 적어 놓는다. 기본적인 구현은 RD,LA,AE를 통한 CP,DCE,AE를 다 하고 나서의 이야기이다.

 

1. mem2reg 하는 방법

포인터는 항상 mem2reg한다. 그리고 어떤 int,bool 단일원소가 포인터로 대입되는 operand가 아니라면 추가로 mem2reg가능하다. 이 정당성은 쉽게 보일 수 있다.

배열에 대해서 생각해 보았는데 이건 쉽지 않았다.

사실상 이게 젤 중요

 

2. Load ~ 도 AE Set에 넣을 수 있다.

Store를 만나면 AE Set의 모든 Load들을 빼는 것을 통해 Load 또한 넣을 수 있다.

 

3. 계산하지 않고도 아는 식들은 미리 처리 하자.

Register x에 대해서 x/x,x/x,0/x,1*x 등등 이런식으로 계산하지 않고도 어떤 값인지 알 수 있다.

 

4. AE 및 CSE 확장 시키기

 

x+y와 y+x가 같은데, 이걸 나는 추가로 구현하였다.
단순히 expression을 정렬하는 걸로 해결할 수 있는데, 정렬하는 것이 잘 안되길래 나는, 순서를 바꿔도 동일한 연산들(+,*,==,!=)에 대해서 AE set에 양방향을 집어 넣었다. 즉 z=x+y가 나오면 [x+y in z] 와 [y+x in z]를 둘 다 집어 넣었다.

 

이를 확장하여 x=y에 대해서도 [x in y] [y in x]를 둘 다 집어 넣으면 더 최적화가 잘 될 것 같은데, 사실 나는 이쪽은 진행하지 않았는데 다음과 같은 문제가 있을 것 같았다. 

예를 들어 z=x가 있으면 z=y로 바뀌고 다음 loop에서 또 z=x로 바뀌면 무한히 반복될 수 있을 것 같았다.

물론 레지스터들간의 비교연산을 통해 우선순위를 정해주면 strictly increasing 하게 IR들이 바뀌게 되어 괜찮을 것 같은데 구현하기 귀찮아서 하지 않았다.

 

5.  조건문 잘 구현하기

if,else,while 조건문에 대한 AST -> IR 코드만 잘 바꿔도 최적화 많이 오른다. 핵심은 GOTO 안의 IR 코드 개수를 최대한 줄이는 식으로 짜기

 

6. 배열 DCE 하기

이건 나도 구현을 못했는데, 배열은 mem2reg을 안 하는데 (나의 구현상) 따라서 dce가 되는지 안되는지를 판단하기가 어려워서 하지 않았다. 구현했으면 점수 좀 더 오를 것 같긴 하다.

 

7.  GOTO 최적화 하기

 

- GOTO L1과 L1 사이 라벨밖에 없다면 이 GOTO L1과 L1은 지울 수 있다.

즉 GOTO L1 ; L2 ; L3 ; L4 ;  L1 비슷하게 L1이 먼저 나와도 지워도 된다. 근데 후자는 까먹고 구현을 안했는데 했으면 점수 더 잘 나왔었을 듯;;
은 지워도 된다.

 - GOTO L1과 L1 사이 라벨이 없다면 이 GOTO L1과 L1은 지울 수 있다.

이 GOTO문 사이로 들어오는게 없다는 뜻이니까 지울 수 있다. 이는 구현하지 않았고 8번을 하면 저절로 구현된다.

 

8.  indegree가 0인 CFG 전부 지우기

 내 개인적인 생각은 8번을 안하면 최적화가 매우 안되는 테케가 있었으면 좋았을 거라는 생각이다. 8번을 하지 않으면 AE가 매우 축소된다. AE set은 계속해서 intersect되기 때문에 필요 없는 노드를 만나면 사실상 별 효과가 없게 된다.

int f(int x,int y) {

    int a= x + y;

    int b= y + x;

    if(a==b){

        return x+y;

    }

    else {

        return x+y+1;

    }

    return x;

}

위 코드가 잘 짠 IR로 최적화되면
f(x, y) : [
  %r5 = x + y,
  ret %r5
]
로 끝나야 한다.

 

9.  CFG에 분기가 없으면 모든 포인터,변수들이 mem2reg가능하다.

이건 나와 동건이형이 하루동안 삽질 박은 주제이다. (ㅈㅅ ㅋㅋ....)
이건 map 같은 것을 통해 구현할 수 있는데, 하... 자세한 구현은 생략한다. 이건 진짜 최적화 엄청 많이 된다.
단점은 CFG에 분기가 있으면 안되는 것 같다. 추가로 NULL과의 비교도 꽤나 어려운데 잘 하시길... 9는 최종 제출할때는 빼서 제출했다. 

9를 CFG 분기가 달라질 때마다 map을 전이하는 식으로 "잘" 확장하면 사실 모든 CFG에 대해서도 될 것 같은데 너무 어려운 구현이라는 생각이 들어서 하지 않았다.

 

 

 

이정도를 추가로 구현한 것 같고 배운것 기본적인 것들만 하고 포인터 mem2reg만 해도 프젝3 90점 이상은 받을 것 같다.