基于函数调用图的静态数据分配

在许多嵌入式设计中,数据存储器是稀缺资源.如何基于静态分配方案,用最少的内存空间来存储程序数据成为嵌入式设计中一个非常重要的问题.如果两个函数之间不存在直接或者间接的调用关系的话,这两个函数的局部变量的生命期就没有重叠.这样的两个函数的局部变量可以共用存储空间而不会影响程序的正确性.基于这个思路,本文提出一种基于函数调用图的拓扑排序的最优静态分配算法(TBA)并证明了该分配算法的最优性.该分配算法通过静态分析技术,构建函数调用图(FCG),基于FCG的拓扑排序,计算每个函数的私有数据段的全局地址以及段内每个符号的全局地址,并根据重定位表更新对这些符号的引用.实验结果表明该算法优于前人提出的启发式算法.