[Sprint 2] Add Heap2Stack Pass

willi19 commented 1 year ago

Overview

First, to prevent stack-overflow, this pass doesn't work if there exist recursion function(for cycle between function calls). Also I set the pass to use at most 80% of the stack to prevent stack overflow by small register spill. I found that memory spill and alloca of each function was much smaller than total stack size but this can be problem when these are accumulated by recursive call. Pass increase the cost of the free, as it adds conditional branches. So pass does not work if there are no malloc to be changed. Also stack pointer returns to it's value when returned, so I only converted malloc in main function. Free function also need to be fixedas it can only fre e memory on heap. I checked the value of the address and call free only when it is on heap.

Implementation

I used $decr_sp intrinsic to change stack pointer, Also by using $decr_sp 0, current value of sp can be seen and able to use stack only when there is space.

/*BB
  |      \
AllocaBB  MallocBB
   |     /
divBB(CI==Malloc) 
*/

Whenever malloc that can be converted to stack is found, pass split the basic block with the second block have malloc instruction in first instruction. Then pass make two basic block with $decr_sp and malloc. Then put condition comparing SP 0.8 and size of memory that are requested. If req memory > SP 0.8 than there aren't enough space so pass allocate memory with malloc and otherwise use $decr_sp to put memory on stack.

Whenever free call is encountered, pass split basic block and put condition that compare the value of requested pointer and 102400, at the end of the first block. Then pass create new block with calling free. First block branch to this block if the value is bigger than 102400 and branch to second basic block otherwise(do nothing).

While implementing, I found that free function is a waste of cost if malloc is not called after it. So I think pass that remove these free function will be useful. Also some malloc wrapper like malloc_upto.. function in benchmark are not converted. I'm expecting this can be solved with function inlining.

Unit tests

heap2stack/test01.ll Check malloc is converted into $desc_sp properly

heap2stack/test02.ll Recursive functioncall, two function calling each other. -> Must Not Optimize

heap2stack/test03.ll Calling malloc and free inside the function(wrapper). Malloc should not be converted while free should be changed. Also malloc and free in main function should be changed.