[Sprint 3] [A-II] Heap to Stack

What is Heap to Stack?

heap의 사용 cost는 바이트당 1024에 이른다. 따라서 malloc으로 heap을 사용하는 프로그램들은 이 메모리 사용량이 전체 cost를 dominate하는 현상을 확인할 수 있다. Heap to Stack은, 이러한 heap 사용량을 줄이거나 아예 사용하지 않도록 만들어 전체 cost의 dramatic한 감소를 꾀한다.

How does Heap to Stack work?

strace와 같은 툴들은 시스템 콜을 intercept하여 사용 정보를 중간에서 파악한다. Heap to Stack은 malloc과 free를 각각 my_malloc과 my_free로 intercept하여, 가능한 경우 메모리 할당을 heap이 아닌 stack 위에 진행한다.

my_malloc과 my_free의 정의는 다음과 같다:

define i8* @my_malloc(i64 %size) {
  %current_pos_pointer = inttoptr i64 4088 to i64*
  %heap_end_int = add i64 0, [HEAP-END]
  %heap_end = inttoptr i64 %heap_end_int to i8*
  %current_pos_val = load i64, i64* %current_pos_pointer
  %first_alloc = icmp eq i64 %current_pos_val, 0
  br i1 %first_alloc, label %init_heap, label %alloc

init_heap:
  ; Set current_pos to the start of the heap
  store i64 4096, i64* %current_pos_pointer
  br label %alloc

alloc:
  %current_pos_val.1 = load i64, i64* %current_pos_pointer
  %next_pos_val = add i64 %current_pos_val.1, %size
  %overflow = icmp ugt i64 %next_pos_val, %heap_end_int
  br i1 %overflow, label %fallback, label %update_pos

update_pos:
  store i64 %next_pos_val, i64* %current_pos_pointer
  %current_pos = inttoptr i64 %current_pos_val.1 to i8*
  ret i8* %current_pos

fallback:
  %malloc_ptr = call i8* @malloc(i64 %size)
  ret i8* %malloc_ptr
}

define void @my_free(i8* %ptr) {
  %heap_end_int = add i64 0, 102400
  %heap_end = inttoptr i64 %heap_end_int to i8*
  %ptr_int = ptrtoint i8* %ptr to i64
  %is_on_heap = icmp ugt i64 %ptr_int, %heap_end_int
  br i1 %is_on_heap, label %heap, label %stack

stack:
  ret void

heap:
  call void @free(i8* %ptr)
  ret void
}

이 두 함수를 새로운 모듈로 parsing한 후, 기존의 모듈에 링킹하여 삽입을 진행한다.

동작 설명:

my_malloc은, 4096부터 [HEAP-END]까지를 (stack 내의) heap 공간으로 잡는다. 이 공간 내에서, 단순히 current_pos를 increment 하면서 메모리 할당을 진행한다. free는 당장 구현계획이 없기에 메모리 블록의 크기 등의 정보는 저장하지 않았다. 만약 stack 내의 공간이 부족해지면, 진짜 malloc을 호출하여 그 결과값을 전달해준다. (4096부터인 이유는, 0부터 했을 시 일부 벤치마크에서 틀린 결과가 나와서이다. 낮은 address 위치에서 무슨 일이 일어나는건지 잘 모르겠다. 또, 이 시작값이 8의 배수인 것도 중요한 듯 하다.)
my_free는, 입력받은 포인터의 크기를 확인하여, (진짜) heap 범위이면 진짜 free를 호출하고, (stack 내의) 가짜 heap 범위이면 아무 일도 하지 않는다.

이 때 [HEAP-END]는 프로그램의 runtime stack usage의 상한을 전체 stack 크기에서 뺀 값으로, 모든 함수의 Instruction마다 8 바이트씩의 stack usage를 가정하여 설정한다(i64인 경우가 이럴 것이다). 물론 alloca call들의 메모리 사용량도 다 더해준다. 혹시 모르니 SAFETY_BUFFER만큼의 여유 공간도 더해준다. (external function 등을 호출하며 stack을 더 쓸 수도 있다.)

결국 프로그램의 heap 사용량이 충분히 작다면, 모든 malloc이 stack 내에서 일어날 수도 있다.

Stack은 공짜다! (load/store도 더 싸다 ㅎㅎ)

단순히 다 intercept하기 전에, 몇 가지 제한사항이 있다.

malloc을 사용하지 않는 모듈에는, my_malloc 삽입을 진행하지 않는다. 왜인지는 모르겠지만, my_malloc을 사용하지 않고 단순히 정의만 해도 heap 사용량이 8 바이트 늘어나는 현상을 확인하였다. --> 해당 현상은 전역변수 @current_pos를 사용해서 발생하는 overhead이다. --> 전역변수를 사용하지 않도록 수정하였다.
재귀함수가 존재할 경우, 위의 [HEAP-START] 계산법이 유효하지 않다. Pass를 실행하지 않는다. 재귀함수는, 함수가 자신을 부르는 경우 뿐만 아니라 call graph 내에 사이클이 존재하는 모든 경우를 뜻한다. (추후 applicability를 위해 개선 시도 예정)

Unit Tests

malloc_and_free.ll: 단순한 malloc과 free 사용에서 interception이 잘 되는지 확인한다.
no_malloc.ll: malloc이 없는 경우, my_malloc, my_free가 삽입되지 않음을 확인한다.
recursive_malloc.ll: 재귀함수가 존재할 경우, pass가 실행되지 않는 것을 확인한다.
extensive_stack_usage.ll: stack 사용량이 높아 my_malloc이 불가능할 경우, pass를 실행하지 않는다.

Benchmarks

우선, 본 pass가 동작하고 있음을 확인할 수 있는 부분이다: Screenshot from 2023-06-04 19-20-13 입력의 크기가 변화해도, max heap usage가 일정하게 유지된다. Heap을 쓰고 있지 않기 때문이다!

벤치마크에서는 dramatic한 개선이 있었다.

만약 재귀함수에 대한 제약을 해제할 경우 다음과 같이 개선폭과 applicability가 더욱 커진다:

하지만 재귀함수에 대한 적용은 안전하지 않으므로 일단은 적용을 보류한다. ABORT_ON_RECURSION flag를 만들어두었다.

SyphonArch / swpp202301-compiler-team1