컴파일러 - Memory Allocation

Storage Class Selection Problem

• 레지스터 파일에 저장할지, 메모리에 저장할지 결정하는 문제
• 보통 Global, Static들은 memory에, Local 중에 composite type(Struct, array 같은 것들)은 메모리에, 다른 것들은 레지스터에 넣는다고 한다.

Optimize 할 때는 할 때는 unlimited register로 가정했고, code generation 할 때는 all memory approach로 생각했었다.

근데 이제는 unlimited register가 아니라 실제 배정을 해보는 단계

Recall : Liveness Analysis 

이거를 다시 생각해 보는 이유는 서로 같은 시점에 live 하지 않으면 레지스터를 공유할 수 있기 때문이다.

Liveness Analysis는 Backward로 OUT[b]가 IN [b]를 계산하는 데 쓰였다. 

• IN[b] = USE[b] ∪ (OUT[b] - DEF[b]) 
  • [BB에서 사용하는 값]과 [OUT에서 들어온 값들 중에서 재할당 된 값을 제외한 값]의 합집합이었다. 

따라서 어떤 두 값이 동시에 live 하지 않는 시점이 있다면 레지스터를 공유해도 된다.

 

Register Interference Graph( RIG)

말 그대로 레지스터끼리의 간섭을 표현한 그래프이다.

특정 시점에 같이 live 하다면 edge를 잇는 방법으로 그리는 법은 간단하다.

Graph Coloring

RIG에서 "서로 인접한 노드는 같은 색이 아니다"라는 조건으로 색칠해 주면 되는데,

이것은 레지스터를 할당하는 과정과 같다.

BUT. 이것은 NP-hard 문제이다. 만약 성공한다면 그대로 쓰면 되지만, 성공하지 못한다고 해서 안 되는 것도 아니다.

 

• Problem reduction 
  • K개보다 적은 neighbor를 가진 노드를 삭제해 주면서(stack에 쌓아주기), 마지막 그래프가 k-colorable 하다면 원래 그래프도 가능하다. (그래프가 소멸해도 상관없음)

(쉽죠?)

 

Optimistic Coloring

만약 실패한다면 한 개의 노드를 spill 해준다고 가정하고 해 본다. (그냥 빼고 해 보는 거랑 같음)

 

Register Spilling

자, 그래도 안 되는 수가 있다. (like our life)

그렇다면 레지스터 spilling을 해줘야 한다. 

 

기본 수칙

• f를 위한 memory location를 할당해 준다. (fa)
• f를 읽기 전에 load를 해준다. 
  • d := -a
  • f1 := load fa
  • e := d + f1
• f를 쓰고 나서 store를 해준다.
  • f2 := 2 * e
  • store fa := f2
• 사용할 때마다 이름을 바꿔준다. (f1, f2...) - 예를 들어 같은 a 값을 load 하더라도 이름은 달라야 함
  • f3 := load fa
  • b := f3 + c

📌여기서 생기는 문제

어떤 레지스터를 spill 할 것인가... 는 사실 정답은 없지만 어떤 값을 하느냐에 따라

1) 추가적인 레지스터 spilling 이 발생할 수도 있고

2) 레즈스터 spilling에 의한 높은 overhead가 발생할 수도 있는

문제다. 따라서 예시로 휴리스틱을 말하자면

 

1. 가장 충돌이 적은, 즉 같이 살아있는 값들이 적은, 즉 edge가 적은 temporaries를 spill 한다.

2. 적은 definition과 사용인 것을 spill 한다.

3. loop 이 있는 것들은 spill 하지 않는다. 왜냐하면 loop 돌 때마다 load, store 해주는 overhead가 발생할 수 있기 때문에

 

✅ 아마 여기서 시험이 나올 거 같다. 뭐 register spill 하기 좋은 것을 고르고 설명하시오..(근데 아마 정답은 없겠지)

 

Reducing Spilling Cost

• BB(Basic Block) 간에 경계로 만약 a를 spill 했는데 바로 다음 BB에서 다시 load 해서 써야 한다면 낭비겠다. 그때는 load 하지 말고 그냥 쓰는 방식이 있다. 
• 또한 loop에서는 처음 한번 load 하는 식으로 BB를 분리하는 방법이 있다. 분리하지 않으면 loop을 돌 때마다 load 해줘야 하니까.

 

Manual Memory Management

C나 C++에서 segment fault와 같이 dangling pointer를 참조하는 문제나, 다 쓴 메모리를 free 하지 않았을 때의 문제들이 생긴다.

 

이에 비해 JAVA에서는 Automatic Memory Management를 해주는데 주 업무는 절대 사용되지 않을 메모리공간을 free 해주는 것이다.

Object Reachability 

특정 object에 대해 pointer가 있어야 reach 할 수 있다. (당연한 말 하기)

그 object reachability를 root에서부터 data를 traverse 하면서 알아낼 수 있다. 

Garbage Collection

• 새로운 object에게 space를 할당하는 것
• space가 더 이상 없으면 unreachable object를 free 하는 것

이 두 가지 단계를 한다. collection이라고 collect만 하는 게 아니라 할당도 한다는 것 기억하기.

특정 전략은 space가 없기 전에 collect 하기도 한다.

 

1. Mark and Sweep

1. Mark phase : reachable object를 찾고 mark 하는 것
2. Sweep phase : garbage object를 collect 하는 것

🕹️과정

이 작업을 하기 위해서 extra bit이 필요하다.

Mark 단계에서는 root 에서부터 시작해 mark가 0이면 1로 바꿔주고, 거기에서 또 접근할 수 있는 곳들을 todo set에 넣어준다.

Sweep 단계에서는 heap의 아래에서부터 위로 올라가며,

1) 1로 마킹된 것은 0으로 바꿔주고, 2) 0인 것은 freelist로 빼준다.

 

📌실제 구현에서의 이슈

• 공간(space)이 없을 때 실행되는데 이때 시작하려면 todo list를 만들어야 하는데
• 이때 추가적인 memory를 사용하게 된다. (이게 뭐람!!!)
• 또한 fragmentation이 많이 발생할 수 있어 나중에 allocate 할 때 문제가 생길 수도 있다.

해결하는 Trick 👀

Q. mark 할 때 todo list를 따로 만들어 주는 상황에서 추가적인 memory할당 문제

A. object에 추가 data를 저장하는 것이다. previous pointer를 저장하는 레지스터를 추가로 사용해

처음부터 DFS like 작업을 해주는데, 갈 수 있는 끝까지 내려간다.

내려가면서 pointer들을 다음 object를 가리키는 게 아니라 parent를 가리키게 하고 현재 값은 previous pointer에 저장한 채로 현재 pointer가 가리켰던 곳으로 넘어가는 것이다. 그러면서 Mark 작업을 한다.

그러다가 끝에 도달하면 previous pointer 값을 참고해 되돌아가면서 원상태로 되돌려 놓는다.

이러면 todo list를 위해 따로 memory 할당을 하지 않아도 된다.

 

Q. Memory fragmentation문제

A. 새로운 값을 저장할 때, 값이 맞는 가장 큰 block이 할당된다. 이때 memory fragmenation이 발생한다. 해결하려면 가능할 때 block들을 merge 해야 한다.

 

장점: Garbage collect 하는 과정에서 object가 움직이지 않는다. - c/c++에서 유리함

단점: Memory fragmentation 문제가 있다. 모든 object들을 다 scan 해야 한다. 

2. Stop and Copy

• old space : 할당을 위한 공간
• new space : Garbage Collect를 위한 공간

heap pointer는 old space(할당을 위한 공간)의 다음 free word를 가리킨다.

 

🕹️과정

GC를 old space가 가득 차면 시작한다. 

모든 reachable 한 object를 new space로 할당한다. (연속적으로)

Garbage는 oldspace에 그대로 둔다.

old space와 new space를 뒤집는다.

 

Q. Pointer를 조정할 때 다 새로 업데이트하는 것보다 조금 나은 방법이 없을 까?

A. Lazy update

old space에서 new space로 복사할 때, 일단 다 업데이트하는 게 아니라.

new space(이전 old space 이전에 할당을 위했던 공간)에 forward pointer를 만들어 놓고,

만약 new space로 reference 하는 경우가 있으면 이때 업데이트

(일단 표시만 해놓고 안 했다가 누가 물어보면 아 하려고 했어요~~ 이런 식)

 

Simple Sweep in Stop and Copy

start, scan, alloc을 사용하여 mark phase를 minimize 하는 방법

 

start: old와 new space를 나누는 pointer

scan: copied 된 것들 중에서 scan 된 것과 안된 것들을 나누는 것

alloc: copied 된 거 들의 끝

 

🕹️과정

scan과 alloc이 같은 위치에서 시작

old space에서 new space로 옮기기 시작하며 alloc을 한 개씩 높여줌 (forward referencing 하면서)

scan을 한개 옆으로 옮기면서 그 scan 값에서 접근 가능 한 것들을 alloc 시켜줌 - todo list와 비슷

scan과 alloc 이 같아질 때까지 진행

 

장점 :

• 가장 빠른 GC 기술
• 할당하는 게 비용이 낮음 (그냥 heap pointer를 늘리면 됨)
• collection 도 상대적으로 비용이 낮음(전체 scan 안 하고 reachable object만 touch)
• memory fragmentation이 안 생김 - 메모리가 연속적으로 정리되어서

단점: 

• 메모리 사용량이 2배
• GB 시간에 stop 해야 해서 느려질 수 있음
• 복사하는 overhead 발생
• pointer를 업데이트할 때 모든 참조를 새로운 위치로 업데이트해야 해서 비용이 높음

C/C++에서는 location 이 바뀌거나 copy 하는 것을 허용하지 않음 - 포인터가 메모리 주소를 직접 가리켜서.

---

Garbage Collection and Types

어떤 언어에서는 pointer인지 아닌지 알아내기가 어려울 수 있음( 정확한 메모리 참조 정보를 알 수 없는 경우)

3. Conservative Collection

pointer처럼 보이면 pointer로 치자는 마인드 - overestimate(돼야 하는 데 안 되는 것보단 나음)

하지만 이렇게 한다고 해도 C/C++에서 stop and copy를 사용하도록 허용하지 않음

4. Reference Counting

Space가 다 찰 때까지 기다리는 게 아니라, pointer들이 없는 순간 free 하겠다.

new 하면 ref count + 1이 됨

 

장점 : 

• 구현하기 쉬움
• 사용자 경험이 좋음 - 오래 pause 하지 않음 ( 한꺼번에 하는 것보다)

단점: 

• 순환 참조 문제: 서로 참조하는 객체가 있을 경우 참조 카운터가 0이 되지 않아 메모리 누수 발생 가능 
• ref count를 조정해야 해서 각 과정이 느림

Overview of the Automatic Memory Management

장점 : 심각한 storage 버그를 예방함

단점 :

• 프로그래머의 자유도를 줄임 - memory layout 이런 거, 몇 번 쓰고 안쓸 때 이건 reachable 하니까 GB를 안 함
• 실시간 어플리케이션에서 안 좋을 수 있음 - 지연이 있어서
• 순환 참조같이 문제가 생길 수 있음