【输入】
根过程,及每个过程(含根过程)的指令序列
【输出】
调用图,由过程点集和调用边(形如<p,i,q>,p在位置i调用q)集构成
【全局结构】
PVVs:过程值变量集合
PVVals:过程值变量到过程常数集合的映射
PVBinds:过程值变量到过程值变量集合的映射
PVCalls:调用边的集合
【流程核心】
1. 分析过程p内指令,要处理调用指令和赋值指令两种类型。对于调用指令,若被调过程q是过程常数,则将q和<p,i,q>加入调用图,先解析q的过程值形参与传入实参的关系,有4种情况
a)过程常数cp传入过程值形参fp,将偶对<fp,cp>加入PVVals,fp加入PVVs
b)过程值变量vp传入过程值形参fp,将<fp,vp>加入PVBinds,fp和vp加入PVVs
c)过程值形参fp传出过程值变量vp,将<vp,fp>加入PVBinds,vp和fp加入PVVs
d)过程值形参fp传出过程常数cp,将<fp,cp>加入PVVals,fp加入PVVs
若q不是常数而是过程值变量,则将q加入PVVs,<p,i,q>加入PVCalls。再解析q的返回与p的关系,有2种情况
e)返回一个过程值变量vp1赋给另一过程值变量vp2,将<vp2,vp1>加入PVBinds,vp2和vp1加入PVVs
f)返回一个过程常数cp赋给一个过程值变量vp,将<vp,cp>加入PVVals,vp加入PVVs
对于赋值指令,其实情况和上述返回赋值一样
----------------------------------------------------------------
2. 遍历PVVs,传播各过程值变量的PVBinds,直至不再改变(迭代求不动解),本质是计算过程值变量的传递闭包
3. 遍历PVCalls,对每个<p,i,q>,先遍历它的每个PVVals u,将u和<p,i,u>加入调用图;再遍历它的每个PVBinds u及u的每个PVVals v,将v和<p,i,v>加入调用图
----------------------------------------------------------------
以上三环节可使用工作表w来驱动,w初始只有根过程,不断从w移出一个过程p、分析p,每当在环节1或环节3发现一个新过程(过程常数)就加入w,直至w为空,这时所有过程都已分析,调用图构建完成
posted on 2023-09-06 23:04
春秋十二月 阅读(39)
评论(0) 编辑 收藏 引用 所属分类:
Compiler