Lec18. Register Allocation - 15주차 2강

마지막이다!!!! 12월 11일 - 15주차 2강

* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다.

 

• 백엔드의 핵심은 레지스터 할당임

• 레지스터 할당
  • IR을 사용 가능한 레지스터 수에 맞춰 재작성함
  • IR 변환 과정에서는 수많은 임시 변수가 생성되는데, 실제 하드웨어는 제한된 레지스터 수량만 사용 가능
• 사용이 끝난 변수에 할당된 레지스터를 재사용할 수 있음. a,e는 dead 후 동일한 레지스터에 할당 가능함

• 기본 아이디어
  • 프로그램에서 한 번에 t1, t2 중 하나만 사용되면 둘은 같은 레지스터 공유 가능
  • 만약 t1,t2가 동시에 live이면 두 변수는 레지스터 공유 불가능
• workflow
  • 1단계: liveness 분석
  • 2단계: 레지스터 간 간섭 그래프 생성. 각 노드는 변수를 나타내고, 두 변수가 동시에 활성되면 간선 추가.
  • 3단계: 그래프 색칠을 통해 레지스터 할당. 연결된 노드는 같은 색을 가질 수 없음

• 각 지점에서 live 변수를 찾는다

https://www.cs.utexas.edu/~pingali/CS380C/2024/lectures/optimizations/dataflow-1.pdf

아니 렉쳐 17에서 설명해준 라이브변수 구하는 예시랑 너무 다르잖소!!!! 위의 텍사스 머시기 대학 자료 찾아서 다시 공부함

이해하는데 진짜 개오래걸림.....대학 교재 ppt는 양심있게 설명하라! 설명하라!

명령어 여러 개가 묶인 블록을 한 명령어 단위로 분리해줘야 liveness analysis를 제대로 적용할 수 있음(여기서 엄청 헤맴)

블록으로 들어오는 화살표를 in, 블록에서 나가는 화살표를 out으로 생각하고 결과값을 그래프에 대입하면 얼추 맞음

여기에서 변수는, 이전에 배운 것과는 다르게 블록에서 나가는 화살표 중에 다음 블록이 명확하지 않은 것들이 있음.

문제 상에서 임의로 이 다음에 b가 쓰일 수 있다~라는 식으로 가정한 것 같고, 그래서 out 화살표에 {b}가 있는 것 같음.

그래서 {b}를 live 변수로 고려하면서 LA를 했을 때 얼추 슬라이드와 비슷한 정답을 얻어낼 수 있었음..

이렇게 구해진 live 변수들의 쌍을 모두 나열하고, 하나로 묶인 쌍 내의 노드를 간선으로 모두 연결하면 그래프가 그려

• 양방향 그래프. 각 임시 변수는 노드로 표현되고, 임시 변수가 동시에 활성되면 두 노드 사이에 간선을 연결함
• 간선으로 연결된 두 임시변수는 같은 레지스터에 할당될 수 없음

• 그래프 색칠하기
  • 레지스터 할당 문제를 그래프 색칠로 줄인다
  • 그래프 색칠: 연결된 노드는 다른 색으로 칠한다.
  • k개의 색으로 노드를 모두 칠할 수 있으면, k-colorable이라고 함

• 이 문제에서 색상 = 레지스터로 해석됨. 필요한 색상의 개수는 필요한 레지스터 개수와 같으.
• 숫자 k를 머신 레지스터의 수라고 한다
• RIG가 k-colorable이면 k개 이하의 레지스터로 변수를 할당할 수 있음

• 예시 문제에서 그래프 컬러링를 바탕으로 레지스터를 할당한 결과

예시문제에서 4-colorable 문제를 해결하는 과정.

4 미만의 간선을 가진 노드를 스택에 넣음. 다 넣으면 마지막 노드부터 꺼내서 이웃한 노드와 다른 색으로 칠함.

색칠을 완료했으면 같은 색의 노드는 같은 레지스터를 할당한다. a변수는 r2,r3 중 하나 할당 가능해서 r2로 할당함

• 그래프 컬러링에 대해
  • 그래프 컬러링 계산은 어떻게 하나?
  •  그래프 색칠 문제는 NP-hard(계산적으로 어려운 문제)지만, practive에서 잘 작동하는 휴리스틱 알고리즘이 있음
• 휴리스틱 알고리즘의 단계
  • RIG에서 k개의 이웃보다 작은 이웃을 가진 노드 t를 선택
  • 해당 노드 t와 그와 연결된 간선을 제거한다
  • 남은 그래프에서 k-colorable이면, 원래 그래프도 k-colorable이다.
• 마지막 전제가 성립하는 이유
  • 만약 노드 t의 이웃들이 k개의 색보다 적은 색으로 색칠된다면, 노드 t와 이웃들을 다른 색으로 칠해도 k개 이내에서 해결 가능하다

• 그래프 컬러링
  • 1. RIG 노드를 stack에 push한다
    • k개의 이웃보다 적은 이웃을 가진 노드 t를 고른다
    • 선택한 노드를 스택에 넣고, RIG에서 해당 노드와 관련된 간선을 제거한다
    • 그래프가 빌 때까지 반복한다
  • 2. stack의 노드에 색상을 할당한다
    • stack의 마지막 노드(최근 추가)부터 시작한다
    • 이미 색칠된 이웃과 다른 색을 선택해 노드에 할당한다

 

• 컬러링 휴리스틱 알고리즘이 실패한 경우
  • 사용가능한 레지스터의 개수가 부족해 모든 변수를 레지스터에 할당할 수 없음.
  • 저장할 수 없는 변수를 메모리로 옮기는 "spilling"이 필요함. 레지스터보다 느려서 성능 저하 발생

• 3-컬러링 시도
• a는 3 미만인 2개의 이웃 가지고 있음. 제거한다.
• 그런데 남은 이웃들이 모두 3개 이웃을 가지고 있음. spilling 필요함.
• 예시에서는 f를 선택해서 메모리에 저장함.
• 나머지 b,c,d,e에 대해서는 모두 3미만의 이웃을 가지고 있어서 성공적 색칠이 가능하다.

• opimisic coloring: 낙관적 색칠
• 가능한 모든 변수에 레지스터를 할당하는 것을 목표로 하며, f를 메모리에 집어넣는게 아니라 레지스터를 할당시도함
• 낙관적 색칠이 실패하면 f를 spilling하고, f를 저장할 메모리 위치 a를 할당한다
• 읽기(사용) 작업 전: 메모리에서 변수 로드. fi:=load a
• 쓰기(정의) 작업 후: 메모리에 변수를 저장. store fi,a

• spilling에서 f는 3개의 임시변수(f1,f2,f3)으로 나눠서 잠재적인 간섭 가능성을 줄이고, 독립적으로 수행되도록 한다.
• f에 접근하려면 메모리에서 로드하고, 연산 후 메모리에 저장해야하기 때문에, 충돌을 방지하기 위함

• fi: 제한된 live 범위를 가짐
  • 로드 이후부터 다음 명령어 실행 전까지 라이브
  • 스토어 이전 명령어 이후부터 스토어 실행전까지 라이브
• spilling 효과: live 범위 축소로 인해 f의 간섭하는 변수 수가 줄어듦. RIG의 복잡성 감소.

• 3-colorable 이후 RIG의 결과. f가 3개로 나뉨.

spill 목표로 f를 선택하고, f가 등장하는 statement를 모두 f의 임시 변수 f1,f2,f3로 바꿔준다

f를 표현식에 사용하는 경우에는 바로 위에 load문을, f에 변수를 대입하는 경우에는 바로 아래에 store문을 삽입.

기존의 live 변수의 경우, 각 live 변수 쌍에서 f를 모두 제거한다.

  load인 경우: 직전 live 변수 set에 f값을 임시변수f로 치환해서 load문에서 out되는 live 변수set을 구한다

  sotre인 경우: 직전 live 변수 set에 f값을 임시변수f로 치환해서 store문에 in되는 live 변수set을 구한다

새롭게 정의된 live 변수 쌍들을 바탕으로 그래프를 다시 그린다. 이제 3-colorable일 것.

직접 해봐도 3-colorable임. 일단 내가 찾아본 결과로는 임시변수로 나눈 후에는 그냥 일반 변수처럼 생각하고 k-colorable 원칙만 따르면서 레지스터를 자유롭게 할당하면 된다고 함....

 

• 추가적인 spill 가능성. coloring 완료 전 추가적인 spill이 필요할 수 있음.
• 어떤 변수를 spill할지 결정하는 것은 어려움. 그러나, 어떤 선택이든 정확성에는 영향이 없고 성능에 영향을 미침.
• 스필링 휴리스틱을 선택하는 기준
  
  • 충돌이 가장 많은 임시 변수를 스필: 많은 변수와 간섭하는 변수를 메모리에 저장해 간섭 줄임
  • 정의와 사용이 적은 임시 변수 스필: 코드에서 적게 사용되는 변수 스필해 성능 영향 최소화
  • 내부 루프에서 스필이 발생하면 성능 저하가 심각할 수 있으므로 이를 회피

• 커버 못한 토픽들 다음학기에는 커버할거니까 원하면 재수강하라는데 진짜 무슨 말씀이세요 교수님.....

 

끼얏호!!! 이제 기말고사만 보면 종강~~~0.<