高级编译器设计与实现

第七章

基本定义

基本块——一段只能从它的开始处进入并且从结束处离开的线性代码序列，简单来说就是经过单一节点合并后的代码块。

必经节点——dominator，用于标识程序中的循环。

流图中的回边——backdege代表的其头节点是尾节点的必经节点，头节点在这里是指的被指向的节点。

循环的入口节点是所有这些节点的必经节点，所有的这些节点都可以到达入口节点，而且其内只有一条回边。

拓展基本块——指的是除了第一个节点之外不包含其他汇合节点的块，例如图1中的B1,B2,B3就组合成了一个拓展基本块。

反拓展基本块——指的是以分支节点结束的，且除最后一个节点外不包含其他分支节点的最长指令序列。

控制流分析方法

对单一过程进行控制流分析的两种主要途径，都从确定构成过程的基本块开始，然后构造出它的流图。第一种途径使用必经节点来找出循环，并为优化简单的标出它所找到的循环。第二种途径成为区间分析，它包括一系列的方法，这些方法分析例程的整个结构并且将他分解为称作区间的嵌套区域。区间的嵌套结构形成了所谓的控制树。区间分析的一种成熟变体称为结构分析，它实质上是对例程中的每一种控制流结构进行分类。基于区间的数据流分析方法被称为消去法（elimination method），他们和用于线性代数问题的高斯消去法之间有明显的相似性。

计算必经节点

1.通过集合统计每个节点的前继节点，并且通过并操作合并每个前继节点的必经节点，只需要初始化一下起点，当支配集合不再发生变化退出循环。要统计直接必经节点的话，只需要统计当节点必经节点是否为当前集合中其他节点的必经节点如果是就从集合中去除。这在OI上被称作数据流迭代法。

为了提高效率，我们希望每轮迭代时，当前迭代的结点的所有前驱结点尽可能都已经执行完了这次迭代，因此我们要利用深度优先排序得出这个图的逆后序，根据这个顺序进行迭代。

不做预处理的话时间复杂度应该就是ON^2

OI上给的求直接支配集的方法，就用了bitset来做合并操作还是挺有意思的,并一下u和其某个支配结点v的支配集合，这样就可以得到v除去所缺少的那个支配集，再xor一下包含这个点的u的支配集就可以得到一个包含一位1的bitset了。

code

std::bitset<N> dom[N];
std::vector<int> Dom[N];
int idom[N];

void getidom() {
  for (int u = 2; u <= n; ++u) {
    for (int v : Dom[u]) {
      std::bitset<N> tmp = (dom[v] & dom[u]) ^ dom[u];
      if (tmp.count() == 1 and tmp[u]) {
        idom[u] = v;
        break;
      }
    }
  }
  for (int u = 2; u <= n; ++u) {
    e[idom[u]].push_back(u);
  }
}

2.Lent79算法

Lent79算法简介

Lent79算法主要用于循环检测，特别是在控制流图（Control Flow Graph, CFG）中识别自然循环。该算法最初由 Charles H. Lent 在1979年提出，目的是通过分析程序控制流的循环结构，找到那些包含单入口的自然循环。在编译器的优化中，它可以帮助识别循环体，以便进一步进行优化，例如循环展开、循环优化、并行化等。

Lent79算法概述

Lent79算法通过对控制流图的结构进行深度优先遍历（DFS），并结合支配树（Dominator Tree）的信息，识别出循环头和回边。该算法的目标是找到自然循环，也就是从图中的某个节点出发，有路径回到这个节点，并且只能通过这个节点进入循环。

核心概念

控制流图 (CFG, Control Flow Graph)：用于描述程序的执行路径，图中的节点表示程序的基本块，边表示控制流转移。

回边 (Back Edge)：在深度优先遍历中，若从一个节点 vvv 指向其祖先节点 uuu 的边，这条边称为回边。回边标识循环的存在。

支配关系 (Dominator)：若节点 AAA 支配节点 BBB，表示每条进入 BBB 的路径都必须经过 AAA。循环的入口节点（循环头）通常是一个节点 hhh，其支配所有循环内的节点。

自然循环 (Natural Loop)：是由一个循环头（入口节点）和一条回边构成的循环。循环头是整个循环的唯一入口，而循环体包含回边的所有节点。

Lent79算法的步骤

构建控制流图：首先，根据程序的基本块和控制流信息，构建一个控制流图 G=(V,E)G = (V, E)G=(V,E)，其中 VVV 是节点集合，EEE 是边集合，表示程序的控制流。

计算支配树：通过深度优先遍历（DFS），计算图中的支配关系，构建支配树（Dominator Tree）。支配树用于识别循环头，即支配循环体中所有节点的节点。

标识回边：通过DFS找到所有回边。回边定义为从节点 vvv 到其祖先节点 uuu 的一条边 (v,u)(v, u)(v,u)，其中 uuu 是循环头。

构建自然循环：对于每一条回边 (v,u)(v, u)(v,u)，通过倒退路径（即逆向遍历）找到所有可以到达 uuu 的节点，并将这些节点加入自然循环集合 L(u)L(u)L(u)。这些节点构成了循环体，并且从图结构上，循环头 uuu 是这些节点的唯一入口。

处理多出口循环：Lent79算法的一个扩展是处理多出口的自然循环。循环体中的节点可以有多个出口，但整个循环只能通过唯一的入口节点进入。

形式化步骤

深度优先搜索 (DFS)：

从起始节点开始对控制流图 G 进行深度优先搜索。

在搜索过程中记录节点的发现时间和完成时间。

支配关系计算：

通过已知的算法（例如 Lengauer-Tarjan 算法）计算出每个节点的支配者。

找到控制流图中所有节点的支配关系，从而确定循环头。

回边标识：

若在 DFS 中发现一条边 (v,u)，且 u 是 v 的祖先节点（即 u 的发现时间比 v 早），则认为这条边是回边。

(v,u)(v, u)

构造自然循环：

对于每一条回边 (v,u)，从 v 开始逆向遍历控制流图，找到所有通过控制流路径能够到达节点 u 的节点。

(v,u)(v, u)

将这些节点和 u 一起构成自然循环体。

算法的关键性质

唯一入口：每个自然循环都有一个唯一入口（循环头），该入口支配整个循环体中的所有节点。

循环检测效率：Lent79算法可以在线性时间内检测自然循环，因为它结合了DFS与支配树的计算。

回边的唯一性：自然循环中的回边是唯一的，它从循环体的某个节点返回到入口节点。

Lent79算法的应用

编译器优化：在编译器中识别自然循环后，可以进行各种优化，比如：

循环展开（Loop Unrolling）

循环不变代码外提（Loop Invariant Code Motion）

循环归纳变量简化（Induction Variable Simplification）

代码分析：在程序分析和静态分析工具中，识别循环是重要的一步。Lent79算法可以用来分析代码中的循环结构，帮助进行代码优化或检测潜在的性能问题。

OIwiki支配树介绍

CSDN支配树介绍

半必经结点介绍

LT证明

LENT79算法的目的是针对一个只包含自然循环的数据流图，生成一颗对应的支配树。

其中引入了一个新的半必经结点的概念，其定义其实就是从起点对这棵树进行DFS，存在一条从V到U的通路，当未遍历到这条通路之间的点情况下，这个点集中dfn最小的点。

The immediate dominator for v is its semidominator, if there is no vertex a on the path sdom(v)

这段证明还是有点复杂的，但是从感性的角度来思考这两个论点又没有那么复杂。尝试从下面两个图里找反例就行了。

无非是通过这个等式，还有之前通过之前那份并查集的代码添加一些状态更新应该就可以了。

LLVM在2017年从LT算法改成了semi_nca算法，原理就是

这个的证明过程我也没看明白，但是结论确实很好记，它的时间复杂度理论上来说比LT慢，但是由于可以增量型计算idom，实际计算速度反而比LT要快。另外从实现的角度上来说也更简单。

这两个算法都只能支持我们建立一颗idom树，当然有了idom树，要求出dom关系也很简单，然后再通过dom关系求出回边以及自然循环也是可以的。

循环和强连通分量

这里重新定义一下回边——其头是其尾的必经节点的边。

通过这条回边，我们就可以得到一个自然循环内的所有点。

当然如果出现了多个循环入口点的情况（非自然循环）还可以通过找出图中的所有SCC的方式来找循环内节点。

可规约性

如果流图是可规约的，那么在此流图中的所有循环都是由他们的回边刻画的自然循环。反之亦然。由这个定义得出，可规约流图中没有转入循环体内的转移，每一个循环只能通过他的首节点进入。

当某些控制流图不可规约，这种情况一般是流图的多入口强连通分量导致的。

在多数语言中，只要我们避免使用goto，尤其是转移到循环体内的goto，则构造出来的过程也具有可归约性，但是异常等机制也会给流图引入不可规约的风险。

不可规约流图的解决办法：

区间分析和控制树

结构分析

伪代码

procedure Structural_Analysis(N,E,entry)
	N: in set of Node
	E: in set of (Node * Node)
	entry: in Node
begin
	m,n,p:Node
	rtype: ReginonType
	NodeSet,ReachUnder: set of Node
	StructOf:= StructType := Structures := StructNodes := Ø
	CTNodes := N; CTEdges := Ø
	repeat
		Post := Ø; Visit := Ø
		PostMax := 0; PostCtr := 1
		DFS_Postorder(N,E,entry)
		while |N| > 1& PostCtr <= PostMax do
			n := Post(PostCtr)
			|| locate an acyclic region, if present
			rtype := Acyclic_Region_Type(N,E,n,NodeSet)
			if rtype ≠ nil then
				p:= Reduce(N,E,rtype,NodeSet)
				if entry ∈ NodeSet then
					entry := p
				fi
			else
				|| locate a cyclic region, if present
				ReachUnder := {n}
				for each m ∈ N do
					if Path_Back(m,n) then
						ReachUnder ∪＝ {m}
					fi
				od
				rtype := Cyclic_Region_Type(N,E,n,ReachUnder)
				if rtype ≠ nil then
					p := Reduce(N,E,rtype,ReachUnder)
					if entry ∈ ReachUnder then
						entry := p
					fi
				else
					PostCtr += 1
				fi
			fi
		od
	until |N| = 1
end || Structural_Analysis

小节总结

必经结点方法部分

显然区间控制和必经节点这两种手段都能帮助我还原循环结构，之所以控制结构中单提这个，主要是因为我应用的范围里没有switch，也就是说最复杂的部分，其实就是循环结构的还原。

关于循环的部分，目前能想到的就是：

如果我有控制流图中每个结点的后置结点前置结点以及后必经结点和必经结点的信息，那么我是否可以通过查询当前结点A的每个前置结点Bi的必经结点中是否包含当前结点A，如果包含的则表示存在一条自然循环的回边？

这种方式来找到回边比较简单，不过用一下染色法的DFS等方式应该也是能把一个图的所有回边找齐的，DFS的时间复杂度应该就是接近ON了，不过要遍历整棵树，我这个方法的话应该是ON^2，如果只考虑自然循环且不考虑虚假分支的话，是不会有一个循环存在多个入口点这种不可归化情况发生的，而如果存在goto或者异常等机制的代码里，可能还需要添加其他的处理。如果要处理的话，甚至可以在所有回边后面添加一个循环的后置空结点用于方便处理。不过理论上来说应该也是会有接近线性复杂度的处理方案的。

另外我这里的找循环内结点是只能找到自然循环的，如果有多个入口点可能就要用tarjan去找scc了。无向图的缩点与强连通分量

最后这份比较简单的算法代码里，其实用的是我自己/GPT写的比较呆的集合操作，要说的话，应该也是能用位来表示集合的，只是会要多很多额外的处理，另外节点多了的话，应该也需要高级数据结构，不太好自己手写，但应该会快一点点，毕竟理论上来说最大可以是几万个点的有向图。

区间控制/结构控制部分

前置结点