ABSTRACT
This chapter explores the lifetime analysis techniques that will enable to share buffers effectively, and thus reduce the buffer memory requirements of SAS significantly compared to previous efforts. Lifetime analysis techniques for sharing memory are well known in a number of contexts. The first is for register allocation in traditional compilers; given a scheduled dataflow graph, register allocation techniques determine whether the variables in the graph can be shared by looking at their lifetimes. Extracting the lifetimes efficiently requires several algorithms for determining the durations, the start and stop times. These lifetimes could also be periodic; it would be desirable to represent the periodicity implicitly, without having to physically create an interval for each occurrence. Hence, the lifetime extraction algorithms also have to model this periodicity efficiently. J. Fabri models array lifetimes as weighted interval graphs and uses coloring heuristics for generating memory allocations.
