BB-GC: BasicBlock Level Garbage Collection

Memory space limitation is a serious problem for many embedded systems from diverse application do-mains. While circuit/packaging techniques are definitely im-portant to squeeze large quantities of data / instruction into small size memories typically employed by embed-ded systems, software can also play a crucial role in re-ducing memory space demands of embedded applications. This paper focuses on a software-managed two-level mem-ory hierarchy and instruction accesses. Our goal is to reduce on-chip memory requirements of a given applica-tion as much as possible, so that the memory space saved can be used by other simultaneously-executing applica-tions. The proposed approach achieves this by tracking the lifetime of instructions. Specifically, when an instruc-tion is dead (i.e., it could not be visited again in the rest of execution), we deallocate the on-chip memory space allo-cated to it. Working on the control flow graph representa-tion of an embedded application, our approach performs basic block-level garbage collection for on-chip memo-ries. 1