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

基于函数调用图的静态数据分配 Static Data Allocation Based on Function Call Graph 何炎祥 HE Yanxiang 1 2 first-author 李清安 LI Qing’an 1 陈勇 CHEN Yong 1 吴伟 WU Wei 1 徐超 XU Chao 1 江南 JIANG Nan 1 武汉大学计算机学院 武汉大学计算机学院 School of Computer,Wuhan University School of Computer,Wuhan University 武汉大学软件工程国家重点实验室 武汉大学软件工程国家重点实验室 State Key Laboratory of Software Engineering,Wuhan University State Key Laboratory of Software Engineering,Wuhan University 在许多嵌入式设计中,数据存储器是稀缺资源.如何基于静态分配方案,用最少的内存空间来存储程序数据成为嵌入式设计中一个非常重要的问题.如果两个函数之间不存在直接或者间接的调用关系的话,这两个函数的局部变量的生命期就没有重叠.这样的两个函数的局部变量可以共用存储空间而不会影响程序的正确性.基于这个思路,本文提出一种基于函数调用图的拓扑排序的最优静态分配算法（TBA）并证明了该分配算法的最优性.该分配算法通过静态分析技术,构建函数调用图（FCG）,基于FCG的拓扑排序,计算每个函数的私有数据段的全局地址以及段内每个符号的全局地址,并根据重定位表更新对这些符号的引用.实验结果表明该算法优于前人提出的启发式算法. Data memory is a scarce resource for many embedded designs.As a result,it is a critical issue to explore a static memory allocation scheme which stores the program data upon the minimum amount of memory.It is observed that the local variables of two functions could share the same memory space,if these two functions neither directly nor indirectly invoke each other during aprogram’s execution.Based on this observation,this paper proposes an optimal static memory allocation scheme and proves its optimality.This scheme consists of three steps.First,it constructs the function call graph（FCG）via static analysis.Then,it determines the address of each function’s private data segment based on the topologic ordering of FCG.Finally,it determines the addresses of local symbols in private data segments and updates the reference to these symbols based on the relocation table.The optimality of this scheme is proved and the experimental results show that this scheme works better than the previous work. 函数调用图 拓扑排序 编译器 静态数据分配 function call graph topological ordering compiler static data allocation 10.14188/j.1671-8836.2013.06.010 TP368.1 国家自然科学基金（61170022,91118003,61003071,61373039）资助项目 2013-06-01 2021-04-01 6 59