带调用栈语义的全局资源变量活跃性分析算法求解

核心问题 #

全局资源标识符表的存在导致函数无法独立分析，传统Gen+Kill的单控制流图分析无法处理函数调用-返回的栈式跳转语义，尤其是递归和多调用方场景。

可行算法与技术方案 #

1. 上下文敏感控制流图（CSCFG） #

为每个函数调用点生成独立的函数上下文实例，每个实例的尾块后继指向对应调用点的返回块，精准追踪不同调用路径的资源活跃性。

• 优化策略：用调用字符串或函数摘要减少实例数量，纯函数可复用同一摘要，避免递归导致的无限膨胀。

2. 迭代式函数间活跃性分析 #

将活跃性分析扩展为跨函数的迭代框架：

• 为每个函数计算入口活跃集（调用方传递的活跃资源）和出口活跃集（函数执行后需传回调用方的资源）。
• 调用指令处：将被调用函数的入口活跃集与当前块的活跃集合并。
• 返回指令处：将被调用函数的出口活跃集传递给返回块的活跃集。
• 递归处理：通过迭代收敛判断终止——当所有函数的入口/出口活跃集不再变化时停止，实际场景中活跃集通常会快速收敛。

3. 栈模拟启发式方法 #

若严格分析开销过高，可采用模拟调用栈的实用方案：

• 分析时维护模拟栈，记录当前调用路径的上下文（调用点、活跃资源集）。
• 调用函数时，压入当前活跃集并分析被调用函数；返回时，弹出栈顶活跃集，与函数出口活跃集合并后继续分析返回块。
• 递归处理：设置栈深度阈值，超过阈值时复用已有活跃集结果，避免无限递归分析，适合精度要求适中的场景。

理论参考 #

• 《Compilers: Principles, Techniques, and Tools》（龙书）第9章“Interprocedural Analysis”，详细讲解了函数间数据流分析的基础框架，包含活跃性分析的跨函数扩展方法。
• 论文《Context-Sensitive Interprocedural Dataflow Analysis via Graph Reachability》，提出基于图可达性的上下文敏感分析方法，可适配带调用栈语义的数据流问题。

内容的提问来源于stack exchange，提问作者ChrisB