收敛性和一致性¶
简介¶
在某些环境中，线程组并行执行同一个程序，其中使用称为收敛操作的特殊原语建立组内的有效通信。收敛操作的结果对参与其中的线程集敏感。
收敛的直观概念是围绕线程“同步”执行构建的——如果一组线程都在“一起执行相同的指令序列”，则认为它们是收敛的。这些线程可能会在不同分支处发散，之后也可能在某个公共程序点重新收敛。
在这个直观的图景中，当收敛的线程执行一条指令时，如果结果值在这些线程中相同，则称该值为一致的，否则为不同的。相应地，如果分支的条件是一致的，则称该分支为一致分支，否则为不同分支。
但是，同步执行的假设对于描述收敛操作处的通信并非必要。它还通过过度指定这些并行环境中线程的执行方式来约束实现（编译器以及硬件）。为了消除这个假设
我们将收敛定义为不同线程执行每条指令之间的关系，而不是线程本身之间的关系。此定义对于已知的目标是合理的，并且与 LLVM IR 中收敛操作的语义兼容。
我们还根据此收敛定义一致性。只有当指令的相应执行是收敛的时，才能检查指令的输出在多个线程中是否一致。
本文档描述了一种静态分析方法，用于确定函数中每条指令的收敛性。该分析扩展了先前关于发散分析的工作[DivergenceSPMD]，以涵盖不可归约的控制流。所描述的分析在 LLVM 中用于实现 UniformityAnalysis，该分析确定 LLVM IR 或 MIR 函数中每条指令计算的值的一致性。
Julian Rosemann、Simon Moll 和 Sebastian Hack。2021。可归约控制流图上SPMD发散的抽象解释。Proc. ACM Program. Lang. 5, POPL，第 31 条文章（2021 年 1 月），35 页。https://doi.org/10.1145/3434312
动机¶
不同分支限制了程序转换，例如更改 CFG 或将收敛操作移动到 CFG 的不同位置。跨不同分支执行这些转换可能会更改以收敛方式执行收敛操作的线程集。虽然这些约束不在本文档的范围之内，但一致性分析允许这些转换识别不满足这些约束的一致分支。
一致性本身在以组方式（例如波、线或子组）执行线程并共享执行资源的目标上也很有用。
一致输出可能在共享资源上计算或存储。
这些目标必须“线性化”不同分支以确保分支的每一侧都由同一组中的相应线程遵循。但在一致分支上，线性化是不必要的，因为整个线程组都遵循分支的一侧或另一侧。
术语¶
线程和动态实例¶
程序源代码中指令的每次出现都称为静态实例。当线程执行程序时，静态实例的每次执行都会生成该指令的不同的动态实例。
每个线程生成唯一的动态实例序列
该序列是根据分支决策和循环遍历生成的。
以“第一个”指令的动态实例开始。
继续使用后续“下一个”指令的动态实例。
线程是独立的；某些目标可能会选择将它们分组执行，以便在可能的情况下共享资源。
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|||
线程 1 |
Entry1 |
H1 |
B1 |
L1 |
H3 |
L3 |
Exit |
||||
线程 2 |
Entry1 |
H2 |
L2 |
H4 |
B2 |
L4 |
H5 |
B3 |
L5 |
Exit |
在上表中，每一行都是一个不同的线程，从左到右列出了该线程生成的动态实例。每个线程都执行相同的程序，该程序以Entry节点开始，以Exit节点结束，但不同的线程可能会通过程序的控制流的不同路径。这些列仅为了方便编号，空单元格没有特殊含义。同一列中列出的动态实例是收敛的。
收敛¶
收敛前是动态实例上的严格偏序关系，定义为以下关系的传递闭包：
如果动态实例
P在同一线程中严格地在Q之前执行，则P收敛前于Q。如果动态实例
P在同一线程中严格地在Q1之前执行，并且Q1与Q2收敛，则P收敛前于Q2。如果动态实例
P1与P2收敛，并且P2在同一线程中严格地在Q之前执行，则P1收敛前于Q。
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
线程 1 |
Entry |
… |
S2 |
T |
… |
Exit |
|||
线程 2 |
Entry |
… |
Q2 |
R |
S1 |
… |
Exit |
||
线程 3 |
Entry |
… |
P |
Q1 |
… |
上表显示了来自不同线程的部分动态实例序列。同一列中的动态实例假定是收敛的（即，在收敛关系中相互关联）。生成的收敛顺序包括边P -> Q2、Q1 -> R、P -> R、P -> T等。
与…收敛是不同线程为同一静态实例生成的动态实例上的传递对称关系。
提供与…收敛关系的任何一个定义都是不切实际的，因为不同的环境可能希望以不同的方式关联动态实例。收敛前是严格偏序关系这一事实是对与…收敛关系的约束。如果不同的动态实例永远不会收敛，则它很容易满足。下面，我们提供了一种称为最大与…收敛的关系，它满足收敛前并且适用于已知的目标。
注意
收敛前关系是不可直接观察的。程序转换通常可以自由更改指令的顺序，即使这显然会更改收敛前关系。
收敛的动态实例不必在同一时间或甚至在同一资源上执行。收敛操作的收敛动态实例似乎可以这样做，但那是一个实现细节。
事实
P收敛前于Q并不自动意味着P在内存模型意义上先于Q发生。
最大收敛¶
本节定义了一个约束，该约束可用于生成最大与…收敛关系，而不会违反严格的收敛前顺序。这种最大与…收敛关系对于实际目标是合理的，并且与收敛操作兼容。
最大与…收敛关系是根据循环头定义的，假设线程在每次循环“迭代”时都在循环头上收敛。通俗地说，如果两个线程先前在进入该循环后都执行了相同次数的循环头，则它们执行循环的同一迭代。通常，这还需要考虑父循环的迭代次数。
最大与…收敛
如果且仅当以下条件满足时，由不同线程为同一个静态实例
X生成的动态实例X1和X2在最大收敛关系中收敛。
X不包含在任何循环中，或者，对于每个包含
X且头部为H的循环C
在各自的线程中，每个先于
X1的H的动态实例H1都收敛于X2之前，并且，在各自的线程中，每个先于
X2的H的动态实例H2都收敛于X1之前，不假设
X1与X2收敛。
注意
如果 CFG 不可约，则循环头部可能对给定的 CFG 不是唯一的。对于同一个 CFG，每个循环层次结构都会导致不同的最大收敛关系。
为简洁起见，本文档其余部分将“收敛”一词限制为“在给定循环层次结构的最大收敛关系下相关”。
现在可以在前面的示例中演示最大收敛，如下所示
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|||
线程 1 |
Entry1 |
H1 |
B1 |
L1 |
H3 |
L3 |
Exit |
||||
线程 2 |
Entry2 |
H2 |
L2 |
H4 |
B2 |
L4 |
H5 |
B3 |
L5 |
Exit |
Entry1和Entry2收敛。H1和H2收敛。B1和B2未收敛，因为H4不收敛于B1之前。H3和H4收敛。H3未与H5收敛，因为H4不收敛于H3之前。L1和L2收敛。L3和L4收敛。L3未与L5收敛，因为H5不收敛于L3之前。
对循环头部的依赖性¶
“收敛于…之前”中的矛盾只可能发生在位于某个循环内的两个节点之间。这些节点的动态实例可能在同一个线程中交错执行，并且这种交错在不同的线程中可能不同。
当一个线程先执行一次节点 X，然后再次执行它时，它一定是在 CFG 中遵循了一条包含 X 的闭合路径。这样的路径必须经过至少一个循环的头部——包含整个闭合路径的最小循环。在给定的线程中，X 的两个动态实例要么被至少一个循环头部的执行隔开，要么 X 本身就是循环头部。
在可约循环（自然循环）中，每次执行头部都等效于循环新迭代的开始。但是，当存在对收敛关系的显式约束时，这种类比就会失效，例如 未来工作 中描述的那些约束。相反，循环头部应该被视为最大收敛关系中的隐式“收敛点”。
考虑一系列嵌套循环 C1、C2、…、Ck，其中 C1 是最外层循环，Ck 是最内层循环，其头部分别为 H1、H2、…、Hk。当一个线程进入循环 Ck 时，以下任何情况都可能发生
线程直接进入循环
Ck，而没有执行任何从H1到Hk的头部。线程执行了部分或全部嵌套头部一次或多次。
最大收敛关系捕捉了关于循环的以下直觉
当两个线程进入顶级循环
C1时，它们会执行每个作为C1的 子节点 的节点的收敛动态实例。当两个线程进入嵌套循环
Ck时，它们会执行每个作为Ck的子节点的节点的收敛动态实例，直到任一线程退出Ck，当且仅当它们执行了任一线程遇到的最后一个嵌套头部的收敛动态实例。请注意，当一个线程退出嵌套循环
Ck时，它必须遵循Ck外部的闭合路径才能重新进入它。这需要执行某个外部循环的头部，如前所述。
考虑由线程 T1 和 T2 为嵌套循环 Ck 的子节点 X 生成的两个动态实例 X1 和 X2。最大收敛关系如下关联 X1 和 X2
如果这两个线程都没有执行任何从
H1到Hk的头部，则X1和X2收敛。否则，如果没有任何从
H1到Hk的头部Q（其中Q可能与X相同）的收敛动态实例Q1和Q2，使得Q1先于X1且Q2先于X2在各自的线程中，则X1和X2不收敛。否则，考虑从
H1到Hk的头部Q的收敛动态实例对Q1和Q2，它们在各自的线程中最近出现在X1和X2之前。然后，当且仅当不存在任何从H1到Hk的头部的动态实例出现在线程T1中Q1和X1之间，或者出现在线程T2中Q2和X2之间时，X1和X2收敛。换句话说，Q1和Q2代表了最后一个收敛点，在执行X之前没有执行其他头部。
示例
上图显示了两个具有头部 R 和 S 的嵌套不可约循环。节点 Entry 和 Q 具有发散分支。下表显示了通过 CFG 采取不同路径的三个线程之间的收敛情况。同一列中列出的动态实例是收敛的。
1
2
3
4
5
6
7
8
10
线程1
Entry
P1
Q1
S1
P3
Q3
R1
S2
Exit
线程2
Entry
P2
Q2
R2
S3
Exit
线程3
Entry
R3
S4
Exit
P2和P3未收敛，因为S1Q2和Q3未收敛，因为S1S1和S3未收敛，因为R2S1和S4未收敛，因为R3
非正式地说，T1 和 T2 执行内部循环的次数不同，而没有执行外部循环的头部。当所有线程第一次执行外部循环的头部时，它们在外部循环中收敛。
一致性¶
如果且仅当两个收敛动态实例的输出在比较时相等，则这两个收敛动态实例的输出是一致的。
如果且仅当静态实例
X的输出对于这些线程产生的每个收敛的动态实例对都是一致的，则其输出对于给定的一组线程来说是一致的。
非一致的值被称为发散。
对于一组线程 S，每个静态实例输出的均匀性如下确定
指令的语义可能指定输出为一致的。
否则，如果静态实例不是 m-收敛，则输出是发散的。
否则，如果静态实例是 m-收敛的
如果它是一个 PHI 节点，则当且仅当对于所有线程
S中产生的每个收敛的动态实例对两个实例都从收敛的动态实例中选择相同的输出，并且
该输出对于
S中的所有线程都是一致的。
否则，当且仅当输入操作数对于
S中的所有线程都是一致的，输出才是一致的。
发散循环出口¶
当在循环内部发生发散分支时，发散路径可能会继续到循环的出口。这称为发散循环出口。如果循环是不可约的，则发散路径可能会重新进入并最终到达循环内的连接点。应检查此类连接点是否满足 发散入口准则。
位于循环外部的发散路径上的节点经历时间发散，当两个线程在循环内部收敛执行时产生一致的值，但在执行头部不同次数（非正式地，在循环的不同迭代中）后沿相同的发散路径退出循环。对于循环内部的节点 N，对于这两个线程，输出可能是一致的，但循环外部的任何使用 U 都从 N 的非收敛动态实例接收值。 U 的输出可能是发散的，具体取决于指令的语义。
静态均匀性分析¶
不可约控制流会导致不同的循环层次结构，具体取决于深度优先遍历期间头节点的选择。因此，静态分析无法始终确定不可约循环中节点的收敛性，任何均匀性分析都仅限于那些收敛性独立于循环层次结构的静态实例。
m-收敛静态实例
对于给定的 CFG，如果且仅当其动态实例的最大收敛关系在该 CFG 可以构建的每个循环层次结构中都相同，则静态实例
X对于该 CFG 是m-收敛的。注意
换句话说，m-收敛静态实例
X的两个动态实例X1和X2在某个循环层次结构中收敛，当且仅当它们在相同 CFG 的每个其他循环层次结构中也收敛。如前所述，为简洁起见，我们将术语收敛限制为“在给定循环层次结构的最大收敛关系下相关”。
如果且仅当给定 CFG 中的每个节点 X 包含的每个循环都满足以下必要条件，则报告该节点为 m-收敛的
注意
可约循环 自然满足上述条件。特别是，如果整个 CFG 是可约的，则 CFG 中的所有节点都是 m-收敛的。
使用 前面描述的准则确定每个静态实例输出的均匀性。发现发散输出可能会导致其使用（包括分支）也变得发散。分析传播这种发散，直到达到不动点。
使用这些准则推断的收敛性是任何循环层次结构的最大收敛关系的安全子集。特别是，足以确定静态实例是否对于给定循环层次结构 T 是 m-收敛的，即使在检查其他一些循环层次结构 T' 时未检测到该事实。
此属性允许编译器转换使用均匀性分析而不受底层循环分析中进行的 DFS 选择的影响。当两个转换对相同 CFG 使用均匀性分析的不同实例时，一个分析实例中的“发散值”结果不会与另一个分析实例中的“一致值”结果发生冲突。
诸如 SimplifyCFG、CSE 和循环转换之类的通用转换通常以改变最大收敛关系的方式更改程序。这也意味着在这样的转换之后，先前一致的值可能会变得发散。在进行此类转换后，必须重新计算均匀性。
循环内的发散分支¶
上图显示了不可约循环区域内部的发散分支 Q。当两个线程在 Q 处发散时，循环区域内动态实例的收敛性取决于所选的循环层次结构
在检测到具有头节点
P的单个循环C的实现中，循环内部的收敛性由P确定。在检测到具有头节点
R和S的两个嵌套循环的实现中，这些循环内部的收敛性由其各自的头节点确定。
一种保守的方法是简单地报告不可约循环内部的所有节点都具有发散输出。但为了最大化均匀性，希望识别 CFG 中的 m-收敛节点。本节描述了从闭合路径派生的此类节点的一种模式，闭合路径是 CFG 的属性，不依赖于循环层次结构。
发散入口准则
闭合路径
P中所有节点的动态实例仅当对于每个发散分支B及其连接节点J（位于P上）来说，不存在位于从B到J的发散路径上的P的入口时，才是 m-收敛的。
考虑上图中的闭合路径 P -> Q -> R -> S。 P 和 R 是 闭合路径的入口。 Q 是发散分支， S 是该分支的连接点，发散路径为 Q -> R -> S 和 Q -> S。
如果存在发散入口
R，则在某个循环层次结构中，R是包含闭合路径的最小循环C的头节点，并且在集合C - R中存在子循环C'，包含分支Q和连接点S。当线程在Q处发散时，一个子集M继续在循环C'内部执行，而补集N退出C'并到达R。由于R的存在，子集M中的线程执行的S的动态实例与子集N中执行的动态实例不收敛。非正式地说，在Q处发散的线程在外部循环C的相同迭代中重新收敛，但它们可能以不同的方式执行了内部循环C'。1
2
3
4
5
6
7
8
9
10
11
线程1
Entry
P1
Q1
R1
S1
P3
…
Exit
线程2
Entry
P2
Q2
S2
P4
Q4
R2
S4
Exit
在上表中，由于
R1，S2与S1不收敛。
如果
R不存在，或者如果除了R之外的任何节点都是C的头节点，则不会检测到此类子循环C'。在Q处发散的线程执行S的收敛动态实例，因为它们在从Q到S的任何路径上都不会遇到循环头节点。非正式地说，在Q处发散的线程在S处在C的相同迭代中重新收敛。1
2
3
4
5
6
7
8
9
10
线程1
Entry
P1
Q1
R1
S1
P3
Q3
R3
S3
Exit
线程2
Entry
P2
Q2
S2
P4
Q4
R2
S4
Exit
注意
通常，上述语句中的循环
C不希望对于不同的头节点来说是相同的循环。循环及其头节点紧密耦合；对于相同最外层循环中的不同头节点，检测到的子循环可能不同。与上述示例相关的属性是，对于每个闭合路径，都存在一个包含该路径的循环C，并且其头节点位于该路径上。
对于每个穿过发散分支B及其连接点J的闭合路径，都必须检查发散入口准则。由于每个闭合路径都会穿过某个循环的头节点，因此这相当于检查包含B和J的每个循环C。当C的头节点支配连接点J时，从头节点到J的任何路径都不会存在入口，其中包括从B到J的任何发散路径。对于穿过包含C的外层循环的头节点的任何闭合路径，也同样适用。
因此，发散入口准则可以保守地简化为如下形式：
对于一个发散分支
B及其连接节点J，包含B和J的循环C中的节点仅当满足以下条件时，才是m-收敛的：
B严格支配J，或者，
C的头节点H严格支配J，或者，递归地，在
C内部存在满足相同条件的循环C'。
当J与H或B相同时，简单的支配关系不足以对发散路径的入口做出任何声明。
到达循环的发散路径¶
该图展示了两个循环层次结构，其中发散分支位于Entry而不是Q。对于两个分别在P和R进入闭合路径P -> Q -> R -> S的线程，沿路径生成的动态实例的收敛性取决于P或R是否为头节点。
当
P为头节点时的收敛性。1
2
3
4
5
6
7
8
9
10
11
12
13
线程1
Entry
P1
Q1
R1
S1
P3
Q3
S3
Exit
线程2
Entry
R2
S2
P2
Q2
S2
P4
Q4
R3
S4
Exit
当
R为头节点时的收敛性。1
2
3
4
5
6
7
8
9
10
11
12
线程1
Entry
P1
Q1
R1
S1
P3
Q3
S3
Exit
线程2
Entry
R2
S2
P2
Q2
S2
P4
…
Exit
因此，当发散路径从循环外部到达不可约循环的不同入口时，静态分析会保守地将循环中的每个节点报告为非m-收敛的。
可约循环¶
如果C是一个头节点为H的可约循环，那么在任何深度优先搜索中，H必须是包含C的某个循环C'的头节点。与深度优先搜索无关，除了H本身之外，子图C不存在其他入口。因此，我们有以下结论：
对于一个发散分支及其连接点，如果两者都位于子图
C内部，则发散入口准则显然满足。当发散路径从外部到达子图
C时，它们的收敛性始终由相同头节点H决定。
显然，这只能在将C检测为可约循环的循环层次结构T中确定。在另一个循环层次结构T'中无法得出这样的结论，其中C是具有相同头节点的更大循环C'的一部分，但这并不与T中的结论相矛盾。
受控收敛¶
收敛控制令牌提供了一种明确的语义来确定程序中给定点哪些线程是收敛的。这种影响体现在受控最大收敛关系（在动态实例之间）和受控m-收敛（静态实例的属性）上。LLVM 中实现的一致性分析包含了这一点，适用于支持收敛控制令牌的目标。