【输入】
程序控制流图CFG
【输出】
带区域结点的控制依赖图CDG
【流程】
1. 为CFG添加一个虚构谓词结点start，它的Y边指向入口结点entry，出边指向出口结点exit，得到CFG+。添加start是因为entry到第1个基本块没有条件判断
2. 为CFG+构建后必经结点树PDOMTree，将CFG+中所有n不是m的后必经结点的边m->n加入集合S，边的标号来自CFG为Y或N
3. 遍历S，对每条边m->n，先在PDOMTree中找到最低公共祖先p（如果m为根结点则为m，否则为m的父结点），再将PDOMTree中p到n路径上每个结点（p和entry除外）x加入CDG，并添加边m->x，其边标号同m->n
4. 对CDG的每个内部结点，若存在Y边，则新建一个区域结点，连接所有Y边对应的子结点；若存在N结点，则新建一个区域结点，连接所有N边对应的子结点
【应用】
对于控制依赖于同一结点的所有结点，只要它们之间没有数据依赖关系，就可以并行执行
posted on 2023-09-06 23:07
春秋十二月 阅读(73)
评论(0) 编辑 收藏 引用 所属分类:
Compiler