关于控制依赖的进一步解释

D题专家

看同学关于控制依赖的问题比较多，在此作进一步解释，避免定义给大家造成误解。

如果节点A出发有多条边，其中只有部分边出发的路径经过下游节点B，则A和B构成控制依赖。

例如图A-2中，B0出发只有1条边B0-B1，从B0-B1出发的路径经过了B5，所以B0到B5不构成控制依赖。事实上，只有一条出向边的节点不会和其它任何节点构成控制依赖。

whale23456789

请教一下，这种情况 B0和B5有控制依赖吗

wangyx

关于控制依赖，建议给出更精确的定义描述。试写如下，不知妥否？

几个图论概念。在以基本块为顶点的有向图中，若从基本块A到基本块B存在一条有向边，则称基本块B是基本块A的后继基本块。基本块A到基本块B之间的一条路径，是图中的有向边的一个序列，其中每一条边的终点是下一条边的起点。若从基本块A到基本块B存在一条路径，则称从基本块A可达基本块B；否则称从基本块A不可达基本块B。

控制依赖是程序控制流导致的一种约束。控制依赖定义为：当基本块A有多个（即大于1个）后继基本块，且这些后继基本块中只有部分可达基本块B时，则称基本块A与基本块B存在控制依赖（更具体地说，是基本块B对基本块A有控制依赖）。

特别说明：（1）当基本块A只有1个后继基本块C时，不论从基本块C是否可达基本块B，基本块B均不会对基本块存在控制依赖。（2）当从基本块A的所有后继基本块都可达（或者都不可达）基本块B时，二者不存在控制依赖。

teriri

whale23456789 发表于 2022-10-6 18:41
请教一下，这种情况 B0和B5有控制依赖吗

我觉得不存在控制依赖，因为B0到B5通过了从B0出发的所有路径。

D题专家

kion 发表于 2022-10-7 17:08
老师您提到：“只有一条出向边的节点不会和其它任何节点构成控制依赖” 。但是图中这种情况2号节点虽然只有 ...

2号不会和其它几点构成控制依赖，但其它几点可能和2号构成控制依赖

D题专家

99673216 发表于 2022-10-6 17:01
您好，
疑问1：
的定义是不是长度只有1，比如b1出发的路径只有B1—B2，B1-B5,而不包括B1-B2-B3等等这种？ ...

是这样理解的。

D题专家

排布到流水线同一级的所有基本块都是并行执行的。

99673216

您好，
疑问1：

出发路径

的定义是不是长度只有1，比如b1出发的路径只有B1—B2，B1-B5,而不包括B1-B2-B3等等这种？
疑问2：
B1，B7存在控制依赖的理解能否这样理解？B1有两个路径，分别b1-b2,b1-b5两条，到达B7的只是用了两条路径的其中一条b1-b5,所以b1，b7存在控制依赖，同样原文中

B5出发的两条路径

指的是b5-b6，b5-b8，而不是b5-b6-b7和b5-b8-b7？

D题专家

whale23456789 发表于 2022-10-6 18:41
请教一下，这种情况 B0和B5有控制依赖吗

不存在

kion

老师您提到：“只有一条出向边的节点不会和其它任何节点构成控制依赖” 。但是图中这种情况2号节点虽然只有一个出度，但是二号节点和零号节点应该是有依赖关系的吧？