支配

维基百科,自由的百科全书
跳转至: 导航搜索
1 dom     1 2 3 4 5 6
2 dom 2 3 4 5 6
3 dom 3
4 dom 4
5 dom 5
6 dom 6
控制关系图
灰色节点 表示非严格控制
红色节点 表示最近必经
以1作为开始节点的控制流图实例

计算机科学中,控制流图的一个节点 d 支配节点 n,当且仅当从开始节点(可以理解为源)到节点 n的每一条路径均要经过节点d,写作d dom n (一写作d \gg n)。根据上述定义,容易得到每个节点均控制其自身。

一些相關概念:

  • 我们说一个节点 d 严格控制节点n,当且仅当 d控制 n 而不等于 n
  • 节点 n 的最近必经点(immediate dominator),简称 idom 是一个独特的节点,它严格支配节点 n,却不支配任何严格支配节点n的其他节点。不是所有的节点均有最近必经点,如开始节点就没有。
  • 一个节点 d 的可支配边界是一个点集,其中任意节点n均满足, d 能严格支配所有节点u((u,v)是图中的一条有向边),却不能严格支配 n。就是 d 支配能力的极限。
  • 一个支配树是一棵,它的所有节点儿子是被其最近支配的所有节点。由于最近必经点是唯一的,故其为一棵树,开始节点即为树根。

历史[编辑]

计算机科学中支配的概念第一次被提出是在Reese T. Prosser在1959年一篇关于流网络的论文中提出的[1] 而在此论文中,Prosser并未提出一种有效算法以计算支配关系,解决这一问题的有效算法直到十年后才被 Edward S. Lowry and C. W. Medlock[2] 提出。Ron Cytron等人在1989年将其应用于高效计算应用于静态单赋值形式的φ 函数时对其重新燃起了兴趣。[3]

参考[编辑]

  1. ^ Prosser, Reese T. Applications of Boolean matrices to the analysis of flow diagrams. AFIPS Joint Computer Conferences: Papers presented at the December 1–3, 1959, eastern joint IRE-AIEE-ACM computer conference (Boston, MA: ACM). 1959: 133–138. 
  2. ^ Lowry, Edward S.; and Medlock, Cleburne W. Object code optimization. Communications of the ACM. 1969-01, 12 (1): 13–22. 
  3. ^ Cytron, Ron; Hind, Michael; and Hsieh, Wilson. Automatic Generation of DAG Parallelism. Proceedings of the ACM SIGPLAN 89 Conference on Programming Language Design and Implementation. 1989: 54–68. CiteSeerX: 10.1.1.50.9287.