为什么LLVM可以调用永不调用的函数？

我不在乎你的龙说什么，这是一个谎言。 龙说谎。 您不知道对方在等什么。

铁龙之女迈克尔·斯旺威克

本文基于Krister Walfridsson博客中的帖子， “为什么未定义的行为可能调用从未调用的函数？” 。

本文得出一个简单的结论：编译器中的未定义行为可以执行任何操作，甚至是绝对出乎意料的操作。 在本文中，我研究了此优化工作的内部机制。

简要回顾一下Waldfridsson的帖子，在下面的源代码中，不应从main调用EraseAll函数，并且在使用-O0编译时实际上并未调用它，但是在优化-O1及更高版本时突然调用了该函数。

#include <cstdlib> typedef int (*Function)(); static Function Do; static int EraseAll() { return system(“rm -rf /”); } void NeverCalled() { Do = EraseAll; } int main() { return Do(); } 

编译器如何优化它？ 首先，Do指向函数的指针为空，因为根据C标准，程序启动时所有全局变量的值均为零。



该程序将尝试取消引用Do指针并调用分配的函数。 但是，如果我们尝试取消引用空指针，则标准会说它是UB，未定义行为。 通常，如果我们在不进行优化的情况下使用-O0选项进行编译，则会出现Segmentation Fault（在Linux中）。 但是标准说，对于UB，程序可以做任何事情。



编译器使用标准的此功能来删除不必要的操作。 如果编译器发现在程序中的任何位置都分配了Do，则它可以在初始化时间内分配该值，而不在运行时分配它。 实际上，有两种可能性：

1.如果在分配指针后取消了指针的引用，我们将获胜，因为编译器可以删除不必要的分配。

2.如果在分配指针之前取消了指针的引用，则标准会说它是UB，并且行为可以是任何行为，包括调用任意函数。 也就是说，调用函数PrintHello（）与标准并不矛盾。

也就是说，在任何情况下，我们都可以根据标准将一些非空值分配给未初始化的指针并获取行为。



在什么条件下可以进行优化？ 最初，程序应包含没有任何初始值或具有空值（相同）的全局指针。 接下来，程序应在指针解引用之前或之后的任何位置（无论在任何地方）为该指针分配一个值。 在上面的示例中，根本没有发生分配，但是编译器看到该分配存在。

如果满足这些条件，则编译器可以删除分配并将其更改为指针的初始值。

在给定的代码中，变量Do是指向函数的指针，并且其初始值为null。 当我们尝试在空指针上调用函数时，程序的行为是不确定的（未定义行为，UB），并且编译器有权根据需要优化UB。 在这种情况下，编译器立即执行Do = EraseAll分配。

为什么会这样？ 在本文的其余部分，LLVM和Clang版本5.0.0用作编译器。 代码示例可运行，供您练习。

首先，让我们看一下使用-O0和-O1优化时的IR代码。 让我们稍微更改一下源代码以使其不那么生动：

 #include <cstdlib> typedef int (*Function)(); static Function Do; static int PrintHello() { return printf("hello world\n"); } void NeverCalled() { Do = PrintHello; } int main() { return Do(); } 

然后，我们用-O0编译IR代码（为清晰起见，省略了调试信息）：

 ; ModuleID = 'test.c' source_filename = "test.c" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" @Do = internal global i32 (...)* null, align 8 @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1 ; Function Attrs: noinline nounwind optnone uwtable define void @NeverCalled() #0 { entry: store i32 (...)* bitcast (i32 ()* @PrintHello to i32 (...)*), i32 (...)** @Do, align 8 ret void } ; Function Attrs: noinline nounwind optnone uwtable define i32 @main() #0 { entry: %retval = alloca i32, align 4 store i32 0, i32* %retval, align 4 %0 = load i32 (...)*, i32 (...)** @Do, align 8 %call = call i32 (...) %0() ret i32 %call } ; Function Attrs: noinline nounwind optnone uwtable define internal i32 @PrintHello() #0 { entry: %call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @.str, i32 0, i32 0)) ret i32 %call } declare i32 @printf(i8*, ...) #1 And with -O1: ; ModuleID = 'test.ll' source_filename = "test.c" target datalayout = "em:e-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1 ; Function Attrs: noinline nounwind optnone uwtable define void @NeverCalled() local_unnamed_addr #0 { entry: ret void } ; Function Attrs: noinline nounwind optnone uwtable define i32 @main() local_unnamed_addr #0 { entry: %retval = alloca i32, align 4 store i32 0, i32* %retval, align 4 %call = call i32 (...) bitcast (i32 ()* @PrintHello to i32 (...)*)() ret i32 %call } ; Function Attrs: noinline nounwind optnone uwtable define internal i32 @PrintHello() unnamed_addr #0 { entry: %call = call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([13 x i8], [13 x i8]* @.str, i32 0, i32 0)) ret i32 %call } declare i32 @printf(i8*, ...) local_unnamed_addr #1 

如果编译可执行文件，将确认在第一种情况下发生分段错误，在第二种情况下显示“ hello world”。 使用其他优化选项，结果与-O1相同。

现在，找到执行此优化的编译器代码部分。 LLVM前端的架构本身并不处理优化，即cfe（Clang Frontend）始终生成没有优化的代码，我们在-O0的版本中看到，所有优化均由opt实用程序执行：



对于-O1，执行186次优化遍。

一遍又一遍地关闭通行证，我们找到了所需的东西： globalopt通行证。 我们只能保留这一优化过程，并确保它（没有其他过程）生成我们需要的代码。 源在文件/lib/Transforms/IPO/GlobalOpt.cpp中。 您可以在LLVM存储库中查看源代码。 为简洁起见，我仅提供了对于理解其工作原理很重要的功能。



该图片表示IR表示的结构。 LLVM IR表示中的代码具有层次结构级别：模块代表层次结构的最高级别，并且包括所有函数和全局对象，例如全局变量。 功能是IR表示的最重要级别，大多数过程都在此级别上进行。 基本块是编译器理论中最重要的概念。 基本块由指令组成，这些指令不能从基本块的中间或基本块内部进行跳转。 基本块之间的所有转换都只能从基本块的末尾到基本块的开始，并且从基本块到中间块的任何跳转都是不可能的。 指令级别代表LLVM IR代码指令。 这不是处理器的指令，它是某些具有无限数量的寄存器的非常通用的虚拟机的指令。



此图显示了LLVM传递的层次结构。 左侧显示了处理LLVM IR代码的过程，右侧显示了处理目标指令的过程。

最初，它实现runOnModule方法，即，在工作时，它会看到并优化整个模块（在这种情况下，这当然是合理的）。 执行优化的函数是optimizeGlobalsInModule：

 static bool optimizeGlobalsInModule( Module &M, const DataLayout &DL, TargetLibraryInfo *TLI, function_ref<dominatortree> LookupDomTree) { SmallSet<const comdat="Comdat" 8="8"> NotDiscardableComdats; bool Changed = false; bool LocalChange = true; while (LocalChange) { LocalChange = false; NotDiscardableComdats.clear(); for (const GlobalVariable &GV : M.globals()) if (const Comdat *C = GV.getComdat()) if (!GV.isDiscardableIfUnused() || !GV.use_empty()) NotDiscardableComdats.insert(C); for (Function &F : M) if (const Comdat *C = F.getComdat()) if (!F.isDefTriviallyDead()) NotDiscardableComdats.insert(C); for (GlobalAlias &GA : M.aliases()) if (const Comdat *C = GA.getComdat()) if (!GA.isDiscardableIfUnused() || !GA.use_empty()) NotDiscardableComdats.insert(C); // Delete functions that are trivially dead, ccc -> fastcc LocalChange |= OptimizeFunctions(M, TLI, LookupDomTree, NotDiscardableComdats); // Optimize global_ctors list. LocalChange |= optimizeGlobalCtorsList(M, [&](Function *F) { return EvaluateStaticConstructor(F, DL, TLI); }); // Optimize non-address-taken globals. LocalChange |= OptimizeGlobalVars(M, TLI, LookupDomTree, NotDiscardableComdats); // Resolve aliases, when possible. LocalChange |= OptimizeGlobalAliases(M, NotDiscardableComdats); // Try to remove trivial global destructors if they are not removed // already. Function *CXAAtExitFn = FindCXAAtExit(M, TLI); if (CXAAtExitFn) LocalChange |= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn); Changed |= LocalChange; } // TODO: Move all global ctors functions to the end of the module for code // layout. return Changed; } 

让我们尝试用语言来描述此功能的作用。 对于模块中的每个全局变量，它都请求Comdat对象。

什么是Comdat对象？

Comdat部分是对象文件中放置对象的部分，可以在其他对象文件中复制这些对象。 每个对象都有链接器的信息，指示检测到重复项时必须执行的操作。 选项可以是：任何-执行任何操作，ExactMatch-重复项必须完全匹配，否则会发生错误，最大-取值最大的对象，NoDublicates-不应重复，SameSize-重复项必须具有相同的大小，否则会发生错误。

在LLVM中，Comdat数据由枚举表示：

 enum SelectionKind { Any, ///< The linker may choose any COMDAT. ExactMatch, ///< The data referenced by the COMDAT must be the same. Largest, ///< The linker will choose the largest COMDAT. NoDuplicates, ///< No other Module may specify this COMDAT. SameSize, ///< The data referenced by the COMDAT must be the same size. }; 

而Comdat类实际上代表一对（名称，SelectionKind）。 （实际上，一切都更加复杂。）由于某种原因而无法删除的所有变量都放置在一组NotDiscardableComdats中。 使用函数和全局别名，我们可以执行相同操作-无法删除的内容放置在NotDiscardableComdats中。 然后，为全局构造函数，全局函数，全局变量，全局别名和全局析构函数调用单独的优化函数。 优化将继续循环，直到没有执行优化为止。 在循环的每次迭代中，NotDiscardableComdats的集合都设置为零。

让我们看看测试源中列出的对象是什么。

全局变量：

 1. @Do = internal global i32 (...)* null, align 8 2. @.str = private unnamed_addr constant [13 x i8] c"hello world\0A\00", align 1 

（稍微向前看，我可以说优化器将在第一次迭代时删除第一个变量）。
功能：

 define void @NeverCalled() define i32 @main() define internal i32 @PrintHello() declare i32 @printf(i8*, ...) 

请注意，仅声明了printf，但未定义。

没有全局别名。

让我们看一下优化过程的示例，并考虑一下结果如何。 当然，即使一次分析所有优化选项也是一项艰巨的任务，因为它涉及许多不同的优化特殊情况。 我们将集中在我们的示例上，考虑对理解此优化过程的工作很重要的那些功能和数据结构。

最初，在这种情况下，优化器进行各种无用的检查，并调用processInternalGlobal函数，该函数尝试优化全局变量。 这个函数也很复杂，可以做很多不同的事情，但是我们对一件事很感兴趣：

 if (GS.StoredType == GlobalStatus::StoredOnce && GS.StoredOnceValue) { ... // We are trying to optimize global variables, about which it is known that they are assigned a value only once, except the initializing value. if (optimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GS.Ordering, DL, TLI)) return true; ... } 

从GS结构（GlobalStatus）中提取了为全局变量分配的值一次且仅一次的信息。 此结构填充在调用函数中：

 static bool processGlobal(GlobalValue &GV, TargetLibraryInfo *TLI, function_ref<dominatortree> LookupDomTree) { if (GV.getName().startswith("llvm.")) return false; GlobalStatus GS; if (GlobalStatus::analyzeGlobal(&GV, GS)) return false; ... 

在这里，我们看到了另一个有趣的事实：名称以“ llvm”开头的对象。 不受优化（因为它们是llvm运行时的系统调用）。 而且，以防万一，LLVM IR中的变量名称可以包含点（甚至包括一个前缀为@或％的点）。 函数analyticGlobal是对LLVM API的调用，我们将不考虑其内部工作。 应该详细查看GlobalStatus的结构，因为它包含有关优化过程的非常重要的信息。

 /// As we analyze each global, keep track of some information about it. If we /// find out that the address of the global is taken, none of this info will be /// accurate. struct GlobalStatus { /// True if the global's address is used in a comparison. bool IsCompared = false; /// True if the global is ever loaded. If the global isn't ever loaded it /// can be deleted. bool IsLoaded = false; /// Keep track of what stores to the global look like. enum StoredType { /// There is no store to this global. It can thus be marked constant. NotStored, /// This global is stored to, but the only thing stored is the constant it /// was initialized with. This is only tracked for scalar globals. InitializerStored, /// This global is stored to, but only its initializer and one other value /// is ever stored to it. If this global isStoredOnce, we track the value /// stored to it in StoredOnceValue below. This is only tracked for scalar /// globals. StoredOnce, /// This global is stored to by multiple values or something else that we /// cannot track. Stored } StoredType = NotStored; /// If only one value (besides the initializer constant) is ever stored to /// this global, keep track of what value it is. Value *StoredOnceValue = nullptr; ... }; 

值得解释为什么“如果我们发现全局地址已被使用，那么这些信息都将不准确。” 实际上，如果我们采用全局变量的地址，然后在该地址上写一些东西，而不是按名称写东西，那么跟踪它将非常困难，最好不进行优化就直接保留这些变量。 。

因此，我们进入了函数optimizeOnceStoredGlobal，变量（GV）和存储值（StoredOnceVal）传递给该函数。 它们是：

 @Do = internal unnamed_addr global i32 (...)* null, align 8 // the variable i32 (...)* bitcast (i32 ()* @PrintHello to i32 (...)*) // the value 

接下来，对于该值，删除无关紧要的位广播，对于变量，检查以下条件：

 if (GV->getInitializer()->getType()->isPointerTy() && GV->getInitializer()->isNullValue()) { ... 

也就是说，必须使用空指针初始化变量。 如果是这种情况，那么我们将创建一个新的SOVC变量，该变量对应于强制转换为GV类型的StoredOnceVal的值：

 if (Constant *SOVC = dyn_cast<constant>(StoredOnceVal)) { if (GV->getInitializer()->getType() != SOVC->getType()) SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType()); 

在这里，getBitCast是返回bitcast命令的方法，该命令以LLVM IR语言键入类型。

之后，将调用函数OptimizeAwayTrappingUsesOfLoads。 它传输全局变量GV和常数LV。

直接优化由功能OptimizeAwayTrappingUsesOfValue（值* V，常数* NewV）执行。

对于变量的每次使用：

 for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) { Instruction *I = cast<instruction>(*UI++); 

如果这是一个Load命令，则将其操作数替换为新值：

 if (LoadInst *LI = dyn_cast<loadinst>(I)) { LI->setOperand(0, NewV); Changed = true; } 

如果在函数调用或调用中使用了变量（这正是本例中发生的情况），请创建一个新函数，将其参数替换为新值：

 if (isa<callinst>(I) || isa<invokeinst>(I)) { CallSite CS(I); if (CS.getCalledValue() == V) { // Calling through the pointer! Turn into a direct call, but be careful // that the pointer is not also being passed as an argument. CS.setCalledFunction(NewV); Changed = true; bool PassedAsArg = false; for (unsigned i = 0, e = CS.arg_size(); i != e; ++i) if (CS.getArgument(i) == V) { PassedAsArg = true; CS.setArgument(i, NewV); } 

该函数的所有其他参数都将被简单复制。

同样，为Cast和GEP指令提供了类似的替换算法，但在我们这种情况下不会发生。

进一步的操作如下：我们遍历了全局变量的所有使用，试图删除除赋值外的所有内容。 如果成功，则可以删除Do变量。

因此，我们在一个特定示例上简要回顾了优化过程LLVM的工作。 原则上，这里没有什么超级复杂的，但是需要更仔细的编程才能提供命令和变量类型的所有可能组合。 当然，所有这些都必须包含在测试中。 学习LLVM优化器的源代码将帮助您编写优化程序，从而使您可以针对某些特定情况改进代码。