MergeFunctions pass,其工作原理¶
导言¶
有时代码包含相同的函数,或者即使在 IR 级别上不相等(例如:乘以 2 和 ‘shl 1’),但执行完全相同操作的函数。这可能是由多种原因造成的:主要是模板和自动代码生成器的使用。当然,有时用户自己可能会写两次相同的东西 :-)
此 pass 的主要目的是识别此类函数并将它们合并。
本文档是对 pass 注释的扩展,描述了 pass 的逻辑。它描述了用于比较函数的算法,并解释了我们如何正确组合相同的函数以保持模块有效。
材料以自顶向下的形式呈现,因此读者可以从高层次的思想开始学习 pass,最终了解低层次的算法细节,从而为他或她阅读源代码做好准备。
主要目标是描述这里的算法和逻辑以及概念。如果您不想阅读源代码,但想了解 pass 算法,本文档非常适合您。作者尽量不重复源代码,仅涵盖常见情况,以避免在任何小的代码更改后需要更新本文档的情况。
为了能够理解本文档,我应该了解什么?¶
读者应该熟悉常见的编译工程原理和 LLVM 代码基础知识。在本文中,我们假设读者熟悉单静态赋值概念,并理解IR 结构。
我们将使用诸如“模块”、“函数”、“基本块”、“用户”、“值”、“指令”之类的术语。
作为一个好的起点,可以使用 Kaleidoscope 教程
尤其重要的是理解教程的第 3 章
读者还应该了解 pass 在 LLVM 中是如何工作的。他们可以使用这篇文章作为参考和起点
还有什么?嗯,也许读者还应该有一些 LLVM pass 调试和 bug 修复的经验。
叙述结构¶
本文由三部分组成。第一部分从顶层解释 pass 的功能。第二部分描述了比较过程本身。第三部分描述了合并过程。
在每个部分中,作者都试图以自顶向下的形式组织内容。首先描述顶层方法,然后在其尾部描述终端方法。如果读者看到对尚未描述的方法的引用,他们将在稍下方找到其描述。
基础知识¶
如何做到?¶
我们需要合并函数吗?显而易见的答案是:是的,这很可能发生。我们通常确实有重复项,最好摆脱它们。但是我们如何检测重复项呢?这是想法:我们将函数拆分为更小的块或部分,并比较“块”的数量。如果相等,我们比较“块”本身,然后对函数本身做出结论。
可能有什么区别?例如,在具有 64 位指针的机器上(假设我们只有一个地址空间),一个函数存储一个 64 位整数,而另一个函数存储一个指针。如果目标是上面提到的机器,并且如果函数是相同的,除了参数类型(我们可以将其视为函数类型的一部分),那么我们可以将 uint64_t
和 void*
视为相等。
这只是一个例子;更多可能的细节将在稍后描述。
作为另一个例子,读者可以想象另外两个函数。第一个函数执行乘以 2 的运算,而第二个函数执行逻辑左移 1 的运算。
可能的解决方案¶
让我们简要考虑关于如何以及我们必须实现什么才能创建功能齐全的函数合并的可能选项,以及这对我们意味着什么。
相等函数检测显然假设要实现一个“检测器”方法,并且后者应该回答“函数是否相等”的问题。这个“检测器”方法由微小的“子检测器”组成,每个子检测器都精确地回答相同的问题,但针对函数部分。
作为第二步,我们应该合并相等的函数。因此它应该是一个“合并器”方法。“合并器”接受两个函数F1和F2,并生成F1F2函数,即合并的结果。
有了这些例程,我们可以处理整个模块,并合并所有相等的函数。
在这种情况下,我们必须将每个函数与另一个函数进行比较。读者可能会注意到,这种方式似乎非常昂贵。当然,我们可以引入哈希和其他辅助工具,但这仍然只是一种优化,因此复杂度级别为 O(N*N)。
我们可以达到另一个级别吗?我们可以引入对数搜索或随机访问查找吗?答案是:“是的”。
随机访问¶
这怎么能做到呢?只需将每个函数转换为一个数字,并将它们全部收集在一个特殊的哈希表中。具有相等哈希值的函数是相等的。良好的哈希意味着必须考虑每个函数部分。这意味着我们必须将每个函数部分转换为某个数字,然后将其添加到哈希中。查找时间会很短,但这种方法由于哈希例程而增加了一些延迟。
对数搜索¶
我们可以引入函数集合之间的全序关系,一旦排序,我们就可以实现对数搜索。查找时间仍然取决于 N,但增加了一点延迟 (log(N))。
当前状态¶
这两种方法(随机访问和对数)都已实现和测试,并且都给出了非常好的改进。最令人惊讶的是,对数搜索更快;有时高达 15%。哈希方法需要一些额外的 CPU 时间,这是它工作速度较慢的主要原因;在大多数情况下,总的“哈希”时间大于总的“对数搜索”时间。
因此,首选“对数搜索”。
尽管在需要的情况下,对数搜索(读作“全序关系”)可以用作我们通往随机访问实现的里程碑。
每次比较都基于数字或标志比较。在随机访问方法中,我们可以使用相同的比较算法。在比较期间,一旦我们发现差异就会退出,但在这里我们可能必须每次扫描整个函数体(注意,这可能会更慢)。就像在“全序关系”中一样,我们将跟踪每个数字和标志,但不是比较,我们应该获取数字序列,然后创建哈希数。因此,再次,全序关系可以被认为是更快(理论上)的随机访问方法的里程碑。
MergeFunctions,主要字段和 runOnModule¶
类中有两个主要的重要字段
FnTree
– 所有唯一函数的集合。它保留了无法相互合并的项目。它被定义为
std::set<FunctionNode> FnTree;
这里 FunctionNode
是 llvm::Function
类的包装器,在函数集中实现了“<”运算符(下面我们将解释它是如何精确工作的;这是快速函数比较的关键点)。
Deferred
– 合并过程可能会影响已经在 FnTree
中的函数的主体。显然,应该再次检查这些函数。在这种情况下,我们从 FnTree
中删除它们,并将它们标记为重新扫描,即将它们放入 Deferred
列表。
runOnModule¶
该算法非常简单
将模块的所有函数放入 worklist 中。
2. 扫描 worklist 的函数两次:首先仅枚举强函数,然后仅枚举弱函数
2.1. 循环体:从 worklist 中取出一个函数(称之为 FCur),并尝试将其插入到 FnTree 中:检查 FCur 是否与 FnTree 中的某个函数相等。如果 FnTree 中有一个相等的函数(称之为 FExists):将函数 FCur 与 FExists 合并。否则,将来自 worklist 的函数添加到 FnTree。
3. 一旦 worklist 扫描和合并操作完成,检查 Deferred 列表。如果它不为空:用 Deferred 列表重新填充 worklist 内容,并重做步骤 2,如果 Deferred 列表为空,则从方法退出。
比较和对数搜索¶
让我们回顾一下我们的任务:对于模块 M 中的每个函数 F,我们必须尽快找到相等的函数 F`,并将它们合并为一个函数。
在函数集中定义全序关系允许我们将函数组织成二叉树。在这种情况下,查找过程的复杂度估计为 O(log(N))。但是我们如何定义全序关系呢?
我们必须引入一个适用于每对函数的单一规则,并遵循此规则,然后评估哪个函数更大。它可能是什么样的规则?让我们将其声明为“compare”方法,该方法返回 3 个可能值之一
-1,左边小于右边,
0,左边和右边相等,
1,左边大于右边。
当然,这意味着我们必须维护严格和非严格的顺序关系属性
自反性(
a <= a
,a == a
,a >= a
),反对称性(如果
a <= b
并且b <= a
则a == b
),传递性(
a <= b
并且b <= c
,则a <= c
)不对称性(如果
a < b
,则a > b
或a == b
)。
如前所述,比较例程由“子比较例程”组成,其中每个“子比较例程”也由“子比较例程”组成,依此类推。最后,它以原始比较结束。
下面,我们将使用以下操作
cmpNumbers(number1, number2)
是一种方法,如果左边小于右边则返回 -1;如果左边和右边相等则返回 0;否则返回 1。cmpFlags(flag1, flag2)
是一种假设的方法,用于比较两个标志。逻辑与cmpNumbers
中的相同,其中true
为 1,false
为 0。
本文的其余部分基于 MergeFunctions.cpp 源代码(位于 <llvm_dir>/lib/Transforms/IPO/MergeFunctions.cpp)。我们希望读者保持此文件打开,以便我们可以将其用作进一步解释的参考。
现在,我们准备进入下一章,看看它是如何工作的。
函数比较¶
首先,让我们定义我们如何精确地比较复杂对象。
复杂对象比较(函数、基本块等)主要基于其子对象比较结果。它类似于下一个“树”对象比较
对于两棵树 T1 和 T2,我们执行深度优先遍历,并将两个序列作为产物:“T1Items”和“T2Items”。
然后,我们以最重要的项目优先的顺序比较链“T1Items”和“T2Items”。项目比较的结果将是 T1 和 T2 比较本身的结果。
FunctionComparator::compare(void)¶
简单看一下源代码,我们知道比较从“int FunctionComparator::compare(void)
”方法开始。
1. 要比较的第一部分是函数的属性和一些在“属性”术语之外的属性,但仍然可以在不更改其主体的情况下使函数有所不同。此部分比较通常在简单的 cmpNumbers 或 cmpFlags 操作中完成(例如 cmpFlags(F1->hasGC(), F2->hasGC())
)。以下是在此阶段要比较的函数属性的完整列表
属性(这些属性由
Function::getAttributes()
方法返回)。GC,为了等价,RHS 和 LHS 应该都是没有 GC 或具有相同的 GC。
Section,就像 GC 一样:RHS 和 LHS 应该在同一 section 中定义。
可变参数。LHS 和 RHS 应该都具有或都不具有 var-args。
调用约定应该相同。
2. 函数类型。由 FunctionComparator::cmpType(Type*, Type*)
方法检查。它检查返回类型和参数类型;该方法本身将在稍后描述。
3. 将函数形式参数相互关联。然后比较函数体,如果我们在 LHS 主体中看到使用了 LHS 的第 i 个参数,那么我们希望在 RHS 主体中的相同位置看到使用了 RHS 的第 i 个参数,否则函数是不同的。在此阶段,我们将优先级授予我们在函数体中稍后遇到的那些(我们首先遇到的值将更小)。这是通过“FunctionComparator::cmpValues(const Value*, const Value*)
”方法完成的(将在稍后描述)。
函数体比较。正如方法注释中写道的
“我们执行 CFG 有序遍历,因为链接列表中块的实际顺序无关紧要。我们的遍历从两个函数的入口块开始,然后按顺序从每个终止符获取每个块。作为一种人为现象,这也意味着不可达块将被忽略。”
因此,使用此遍历,我们以相同的顺序从左和右获取 BB,并通过“FunctionComparator::compare(const BasicBlock*, const BasicBlock*)
”方法比较它们。
我们还将 BB 相互关联,就像我们对函数形式参数所做的那样(请参阅下面的 cmpValues
方法)。
FunctionComparator::cmpType¶
考虑类型比较如何工作。
1. 将指针强制转换为整数。如果左类型是指针,请尝试将其强制转换为整数类型。如果其地址空间为 0,或者如果完全忽略地址空间,则可以这样做。对右类型执行相同的操作。
2. 如果左类型和右类型相等,则返回 0。否则,我们需要优先考虑其中一个。因此继续下一步。
3. 如果类型种类不同(不同的类型 ID)。返回类型 ID 比较的结果,将其视为数字(使用 cmpNumbers
操作)。
4. 如果类型是向量或整数,则返回其指针比较的结果,将它们作为数字进行比较。
检查类型 ID 是否属于下一个组(称之为等价组)
Void
Float
Double
X86_FP80
FP128
PPC_FP128
Label
Metadata。
如果 ID 属于上面的组,则返回 0。因为看到类型具有相同的
TypeID
就足够了。不需要其他信息。
6. 左边和右边是指针。返回地址空间比较的结果(数字比较)。
7. 复杂类型(结构体、数组等)。遵循复杂对象比较技术(参见本章的第一段)。左边和右边都要展开,并且它们的元素类型将以相同的方式检查。如果我们在某个阶段获得 -1 或 1,则返回它。否则返回 0。
8. 步骤 1-6 描述了所有可能的情况,如果我们通过了步骤 1-6 并且没有得出任何结论,则调用 llvm_unreachable
,因为这是一个非常意外的情况。
cmpValues(const Value*, const Value*)¶
比较局部值的方法。
此方法为我们提供了一个非常有趣的问题的答案:我们是否可以将局部值视为相等,否则哪个值更大。最好从示例开始
考虑我们在左函数“FL”和右函数“FR”中查看相同位置的情况。左边位置的每个部分都等于右边位置的相应部分,并且(!)两个部分都使用 Value 实例,例如
instr0 i32 %LV ; left side, function FL
instr0 i32 %RV ; right side, function FR
因此,现在我们的结论取决于 Value 实例比较。
此方法的主要目的是确定此类值之间的关系。
我们对相等函数有什么期望?在函数“FL”和“FR”的相同位置,我们期望看到相等的值,或者在“FL”和“FR”的相同位置定义的值。
这里考虑一个小例子
define void %f(i32 %pf0, i32 %pf1) {
instr0 i32 %pf0 instr1 i32 %pf1 instr2 i32 123
}
define void %g(i32 %pg0, i32 %pg1) {
instr0 i32 %pg0 instr1 i32 %pg0 instr2 i32 123
}
在此示例中,pf0 与 pg0 关联,pf1 与 pg1 关联,并且我们还声明 pf0 < pf1,因此 pg0 < pf1。
操作码为“instr0”的指令将是相等的,因为它们的类型和操作码相等,并且值是关联的。
来自 f 的操作码为“instr1”的指令大于来自 g 的操作码为“instr1”的指令;这里我们有相等的类型和操作码,但“pf1 大于 “pg0”。
操作码为“instr2”的指令是相等的,因为它们的操作码和类型相等,并且使用了相同的常量作为值。
我们在 cmpValues 中关联什么?¶
函数参数。来自左函数的第 i 个参数与来自右函数的第 i 个参数关联。
BasicBlock 实例。在基本块枚举循环中,我们将来自左函数的第 i 个 BasicBlock 与来自右函数的第 i 个 BasicBlock 关联。
指令。
指令操作数。注意,我们可以在这里遇到我们从未见过的 Value。在这种情况下,它不是函数参数,也不是 BasicBlock,也不是 Instruction。它是一个全局值。它是一个常量,因为它是这里唯一假设的全局值。该方法还比较:类型相同的常量,如果右常量可以无损地位铸到左常量,那么我们也比较它们。
如何实现 cmpValues?¶
关联对我们来说是一种相等的情况。我们只是将此类值视为相等,但一般来说,我们需要实现反对称关系。如上所述,为了理解什么是更小,我们可以使用我们遇到值的顺序。如果两个值在函数中具有相同的顺序(同时遇到),那么我们将值视为关联。否则 – 这取决于谁先出现。
每次我们运行顶层比较方法时,我们都会初始化两个相同的映射(一个用于左侧,另一个用于右侧)
map<Value, int> sn_mapL, sn_mapR;
映射的键是 Value 本身,value – 是它的顺序(称之为序列号)。
要添加值 V,我们需要执行下一个过程
sn_map.insert(std::make_pair(V, sn_map.size()));
对于第一个 Value,映射将返回 0,对于第二个 Value,映射将返回 1,依此类推。
然后我们可以通过简单的比较来检查左值和右值是否同时遇到
cmpNumbers(sn_mapL[Left], sn_mapR[Right]);
当然,我们可以结合插入和比较
std::pair<iterator, bool>
LeftRes = sn_mapL.insert(std::make_pair(Left, sn_mapL.size())), RightRes
= sn_mapR.insert(std::make_pair(Right, sn_mapR.size()));
return cmpNumbers(LeftRes.first->second, RightRes.first->second);
让我们看看整个方法是如何实现的。
1. 我们必须从坏消息开始。考虑函数自引用和交叉引用的情况
// self-reference unsigned fact0(unsigned n) { return n > 1 ? n
* fact0(n-1) : 1; } unsigned fact1(unsigned n) { return n > 1 ? n *
fact1(n-1) : 1; }
// cross-reference unsigned ping(unsigned n) { return n!= 0 ? pong(n-1) : 0;
} unsigned pong(unsigned n) { return n!= 0 ? ping(n-1) : 0; }
此比较已在初始 MergeFunctions pass 版本中实现。但不幸的是,它不是传递性的。这是我们无法转换为小于等于大于比较的唯一情况。这是一个罕见的情况,10000 个函数中有 4-5 个(在测试套件中检查),并且,我们希望读者会原谅我们为了获得 O(log(N)) pass 时间而做出的牺牲。
2. 如果左/右 Value 是一个常量,我们必须比较它们。如果它是相同的常量,则返回 0,否则使用 cmpConstants
方法。
3. 如果左/右是 InlineAsm 实例。返回 Value 指针比较的结果。
4. L(左值)和 R(右值)的显式关联。我们需要找出值是否同时遇到,因此是关联的。或者我们需要制定规则:何时将 L < R。现在很容易:我们只需返回数字比较的结果
std::pair<iterator, bool>
LeftRes = sn_mapL.insert(std::make_pair(Left, sn_mapL.size())),
RightRes = sn_mapR.insert(std::make_pair(Right, sn_mapR.size()));
if (LeftRes.first->second == RightRes.first->second) return 0;
if (LeftRes.first->second < RightRes.first->second) return -1;
return 1;
现在当 cmpValues 返回 0 时,我们可以继续比较过程。否则,如果我们得到(-1 或 1),我们需要将此结果传递到顶层,并完成比较过程。
cmpConstants¶
按如下方式执行常量比较
1. 使用 cmpType
方法比较常量类型。如果结果为 -1 或 1,则转到步骤 2,否则继续步骤 3。
2. 如果类型不同,我们仍然可以检查常量是否可以无损地位铸到彼此。进一步的解释是 canLosslesslyBitCastTo
方法的修改。
2.1 检查常量是否属于第一类类型(
isFirstClassType
检查)2.1.1. 如果两个常量都不是第一类类型:返回
cmpType
的结果。2.1.2. 否则,如果左类型不是第一类类型,则返回 -1。如果右类型不是第一类类型,则返回 1。
2.1.3. 如果两种类型都是第一类类型,则继续下一步(2.1.3.1)。
2.1.3.1. 如果类型是向量,则使用 cmpNumbers 比较它们的位宽。如果结果不为 0,则返回它。
2.1.3.2. 类型不同,但不是向量
如果它们都是指针,这对我们来说很好,我们可以继续步骤 3。
如果其中一种类型是指针,则返回 isPointer 标志比较的结果(cmpFlags 操作)。
否则,我们没有证明位铸能力的方法,因此返回类型比较的结果(-1 或 1)。
以下步骤适用于类型相等的情况,或者常量可位铸的情况
3. 其中一个常量是“null”值。返回 cmpFlags(L->isNullValue, R->isNullValue)
比较的结果。
比较值 ID,如果结果不为 0,则返回结果
if (int Res = cmpNumbers(L->getValueID(), R->getValueID()))
return Res;
5. 比较常量的内容。比较取决于常量的种类,但在这一阶段,它只是一个字典式比较。只需查看“函数比较”段落的开头是如何描述的。从数学上讲,它等于下一种情况:我们编码左常量和右常量(以类似于 bitcode-writer 的方式)。然后比较左代码序列和右代码序列。
compare(const BasicBlock*, const BasicBlock*)¶
比较两个 BasicBlock 实例。
它枚举来自左 BB 和右 BB 的指令。
1. 它使用 cmpValues
方法为左侧和右侧指令分配序列号。
2. 如果左侧或右侧之一是 GEP (GetElementPtr
),则将 GEP 视为大于其他指令。如果两个指令都是 GEP,则使用 cmpGEP
方法进行比较。如果结果为 -1 或 1,则将其传递给顶层比较(返回它)。
3.1. 比较操作。调用
cmpOperation
方法。如果结果为 -1 或 1,则返回它。3.2. 比较操作数的数量,如果结果为 -1 或 1,则返回它。
3.3. 比较操作数本身,使用
cmpValues
方法。如果结果为 -1 或 1,则返回结果。3.4. 比较操作数的类型,使用
cmpType
方法。如果结果为 -1 或 1,则返回结果。3.5. 继续处理下一条指令。
我们可以在 3 种情况下完成指令枚举
4.1. 我们到达了左侧和右侧基本块的末尾。我们没有在步骤 1-3 中退出,因此内容相等,返回 0。
4.2. 我们已经到达了左侧基本块的末尾。返回 -1。
4.3. 返回 1(我们到达了右侧基本块的末尾)。
cmpGEP¶
比较两个 GEP (getelementptr
指令)。
它与常规操作比较的不同之处仅在于:可以使用 accumulateConstantOffset
方法。
因此,如果我们获得左侧和右侧 GEP 的常量偏移量,则将其作为数字进行比较,并返回比较结果。
否则,将其视为常规操作(参见上一段)。
cmpOperation¶
比较指令操作码和一些重要的操作属性。
比较操作码,如果不同则返回结果。
比较操作数的数量。如果不同,则返回结果。
3. 比较操作类型,使用 cmpType。同样,如果类型不同,则返回结果。
4. 比较 subclassOptionalData,使用 getRawSubclassOptionalData
方法获取它,并像比较数字一样比较它。
比较操作数类型。
6. 对于某些特定的指令,检查一些重要属性的等价性(在我们的例子中是关系)。例如,我们必须比较 load
指令的对齐方式。
O(log(N))¶
上面描述的方法实现了顺序关系。并且稍后,可以用于二叉树中的节点比较。因此,我们可以将函数集组织到二叉树中,并将查找过程的成本从 O(N*N) 降低到 O(log(N))。
合并过程,mergeTwoFunctions¶
一旦 MergeFunctions 检测到当前函数 (G) 等于之前分析过的函数 (函数 F),它会调用 mergeTwoFunctions(Function*, Function*)
。
操作以下列方式影响 FnTree
的内容:F 将保留在 FnTree
中。与 F 相等的 G 将不会被添加到 FnTree
中。对 G 的调用将被其他内容替换。它会更改调用者的主体。因此,调用 G 的函数将被放入 Deferred
集合中,并从 FnTree
中移除,并再次分析。
方法如下
1. 最理想的情况:当我们可以使用别名并且 F 和 G 都是弱链接时。我们将它们都用别名指向第三个强链接函数 H。实际上 H 就是 F。请参阅下面它是如何实现的(但最好直接查看源代码)。嗯,这是一个我们可以直接将 G 替换为 F 的情况,我们在这里使用 replaceAllUsesWith
操作 (RAUW)。
2. F 不能被覆盖,而 G 可以。最好这样做:在合并使用可覆盖函数的地方之后,仍然使用可覆盖的存根。因此,尝试使 G 成为 F 的别名,或者在 F 周围创建可覆盖的尾调用包装器,并将 G 替换为该调用。
3. F 和 G 都不能被覆盖。我们不能使用 RAUW。我们只能更改调用者:调用 F 而不是 G。replaceDirectCallers
就是做这个的。
下面是详细的主体描述。
如果 “F” 可以被覆盖¶
从 mayBeOverridden
注释可以看出:“此全局变量的定义是否可以在链接时被非等效的内容替换”。如果是这样,那就没问题:我们可以使用 F 的别名来代替 G,或者更改调用指令本身。
HasGlobalAliases, removeUsers¶
首先考虑我们有一个函数名称到另一个函数名称的全局别名的情况。我们的目的是使它们都使用别名指向第三个强链接函数。但是,如果我们保持 F 存活并且没有重大更改,我们可以将其保留在 FnTree
中。尝试结合这两个目标。
用 F 的别名替换 F 本身的存根。
1. 创建存根函数 H,其名称和属性与函数 F 相同。它采用 F 和 G 的最大对齐方式。
2. 将所有对函数 F 的使用替换为对函数 H 的使用。这是一个两步过程。首先,我们必须考虑到,所有调用 F 的函数都将被更改:因为我们更改了调用参数(从 F 到 H)。如果是这样,我们必须在此过程之后再次审查这些调用者函数。我们从 FnTree
中移除调用者,名为 removeUsers(F)
的方法就是做这个的(不要与 replaceAllUsesWith
混淆)
2.1.
在 removeUsers(Value* V)
内部,我们遍历所有使用值 V(或上下文中的 F)的值。如果值是指令,我们转到持有此指令的函数,并将其标记为要再次分析(放入Deferred
集合),我们还从FnTree
中移除调用者。2.2. 现在我们可以进行替换了:调用
F->replaceAllUsesWith(H)
。
3. H(现在“正式”扮演 F 的角色)被替换为 F 的别名。对 G 执行相同的操作:将其替换为 F 的别名。因此,最终在所有使用 F 的地方,我们都使用 H,它是 F 的别名,并且在所有使用 G 的地方,我们也有 F 的别名。
将 F 的链接设置为私有。使其成为强链接 :-)
没有全局别名,replaceDirectCallers¶
如果不支持全局别名。我们调用 replaceDirectCallers
。只需遍历所有对 G 的调用,并将其替换为对 F 的调用。如果您查看该方法,您将看到它也扫描了 G 的所有使用,如果使用是被调用者(如果用户是调用指令并且 G 用作要调用的对象),我们将其替换为对 F 的使用。
如果 “F” 不能被覆盖,修复它!¶
我们调用 writeThunkOrAlias(Function *F, Function *G)
。在这里,我们首先尝试用 F 的别名替换 G。以下条件至关重要
目标应支持全局别名,
G 的地址本身应该是无关紧要的,未命名的,并且在任何地方都没有被引用,
函数应具有外部、本地或弱链接。
否则,我们编写 thunk:一些具有 G 接口并调用 F 的包装器,因此 G 可以用此包装器替换。
writeAlias
正如 llvm 参考中所述
“别名充当别名值的第二个名称”。因此,我们只想为 F 创建第二个名称,并用它代替 G
创建全局别名本身 (GA),
调整 F 的对齐方式,使其必须是当前对齐方式和 G 的对齐方式的最大值;
替换对 G 的使用
3.1. 首先使用
removeUsers
方法(参见上文)将 G 的所有调用者标记为要再次分析,3.2. 调用
G->replaceAllUsesWith(GA)
。摆脱 G。
writeThunk
正如方法注释中所写
“用对 bitcast(F) 的简单尾调用替换 G。 还要用 bitcast(F) 替换 G 的直接使用。 删除 G。”
总的来说,它与我们想要替换被调用者时通常的做法相同,除了第一点
1. 我们在 F 周围生成尾调用包装器,但具有允许用它代替 G 的接口。
“像往常一样”:然后是
removeUsers
和replaceAllUsesWith
。摆脱 G。