使用LLVM进行代码分析

非决定论的诅咒

我第一次尝试编写LLVM段落-我喜欢这些段

最近，我遇到了一个有趣的问题-我需要一种确定性和跨平台的方法来确定C ++代码的执行时间。 “确定性”一词是指相同的代码将在相同数量的时间单位内执行。 通过跨平台，我知道Windows和Ubuntu下的相同代码将在相同的时间单位内运行。

自然地，在CPU上测量时间不满足这些条件。 机器代码取决于体系结构和操作系统，并且相同的代码将花费不同的时间来执行。 即使在同一台机器上，诸如高速缓存未命中之类的因素也将发挥重要作用-足以扭曲测量同一代码执行时间的结果。 我需要更聪明的东西...

动机

当我在我的项目“代码字符”中工作时遇到了这个问题。 Code Character是一个在线AI竞赛，参赛者编写机器人以回合制策略控制军队。 我想限制参与者一口气就能执行的代码量。

我的第一个想法只是测量代码的执行时间，但是，正如我们所看到的，这种策略不是确定性的，两次发送相同代码的参与者将获得完全不同的结果。 实际上，我们尝试实现此解决方案，结果变化很大，以至于参与者可以使用相同的代码赢或输。 结果将是完全随机的，因此我们放弃了测量时间的想法。

LLVM字节码

由于无法衡量时间，因此我们决定衡量执行的指令数。 因此，我们需要检测参与者代码。 如果您不熟悉此术语，则这是向应用程序添加一些代码，以便监视某些参数，例如CPU使用率或运行时。 自然，我们不希望参与者自己做，我们必须使过程自动化。

我们希望避免在服务器上工作时运行时工具的开销，因此，像PIN工具这样的东西不适合我们的目的。 相反，我们决定直接指示参与者代码，以便计算将要执行的指令数量。 代替检测二进制文件（机器代码），我们决定使用Clang编译代码并检测LLVM字节码。

如果您不熟悉LLVM，则它是模块化和可重用的编译器和工具链技术的集合。 LLVM IR和后端是主要项目之一。 简而言之，已经开发了一个中间表示形式，一个编译前端可以在其中编译代码。 然后，此代码LLVM IR被LLVM后端编译为机器代码。 因此，如果要创建新的语言，则可以决定允许LLVM支持机器代码生成和优化，并编写前端以将您的语言转换为LLVM IR。


Clang将C ++代码转换为LLVM IR，然后由LLVM后端转换为机器代码。

Clang是LLVM的前端。 由于我们需要跨平台的方法来测量代码，因此我们无法检测二进制代码。 但是，LLVM IR是平台无关的，因为它只是代码的中间表示。 使用LLVM库检测IR代码是一个简单的跨平台解决方案。

解决方案

简单的LLVM IR指令计数显然不适合，因为我们需要实际执行的指令数量，而不仅仅是代码中的指令数量。 最后，我们根据基本代码块的概念开发了一种简单的算法。

基本单元是一组指令，其中只有第一个指令可以是输入点，只有最后一条指令可以是输出点。 （ 也禁止在基本块内部进行任何转换-大约翻译。 ）要理解这一点，请尝试将代码分成若干部分，其中分支指令（转换，循环和返回）只能是集合中的最后一条，而该块的输入（即第一条指令）函数，循环或if / else块）只能在第一条指令上使用。 结果是一组基本块-一系列顺序代码块，它们仅按顺序执行，而无需决定下一步执行什么指令。

为什么我们现在不尝试呢？ 这是由代码字符提供者提供的代码片段：

// Make the soldiers who aren't patrolling attack the enemy for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) { auto &soldier = state.soldiers[i]; if (soldier.hp == 0) // If this soldier is dead, skip it continue; for (auto enemy_soldier : state.enemy_soldiers) { if (enemy_soldier.hp != 0) { // Ensure your prospective target has // not already been slain soldier.soldier_target = enemy_soldier.id; break; } } } 

Github链接： https : //gist.github.com/JHurricane96/8c9c3a45ec5e969de4d9fecb47ebef69#file-player_code-cpp

利用基本单元只有一个输入点（第一条指令）的事实，我们可以将此片段划分为以下基本单元：

 //-------------------------------- BB 1 ---------------------------------- for (int i = NUM_SOLDIERS / 2; i < NUM_SOLDIERS; ++i) { //-------------------------------- BB 2 ---------------------------------- auto &soldier = state.soldiers[i]; if (soldier.hp == 0) //-------------------------------- BB 3 ---------------------------------- continue; //-------------------------------- BB 4 ---------------------------------- for (auto enemy_soldier : state.enemy_soldiers) { //-------------------------------- BB 5 ---------------------------------- if (enemy_soldier.hp != 0) { //-------------------------------- BB 6 ---------------------------------- soldier.soldier_target = enemy_soldier.id; break; //-------------------------------- BB 7 ---------------------------------- } } } 

Github链接
这有助于我们了解基本块的工作原理，现在让我们在LLVM IR中查看该算法：

 ; <label>:140: ; preds = %181, %139 %141 = load i32, i32* %19, align 4 %142 = sext i32 %141 to i64 %143 = icmp slt i64 %142, 20 br i1 %143, label %144, label %184 ; <label>:144: ; preds = %140 %145 = getelementptr inbounds %"struct.player_state::State", %"struct.player_state::State"* %2, i32 0, i32 1 %146 = load i32, i32* %19, align 4 %147 = sext i32 %146 to i64 %148 = call dereferenceable(72) %"struct.player_state::Soldier"* @_ZNSt5arrayIN12player_state7SoldierELm20EEixEm( %"struct.std::array.10"* %145, i64 %147) #3 store %"struct.player_state::Soldier"* %148, %"struct.player_state::Soldier"** %20, align 8 %149 = load %"struct.player_state::Soldier"*, %"struct.player_state::Soldier"** %20, align 8 %150 = getelementptr inbounds %"struct.player_state::Soldier", %"struct.player_state::Soldier"* %149, i32 0, i32 2 %151 = load i64, i64* %150, align 8 %152 = icmp eq i64 %151, 0 br i1 %152, label %153, label %154 ; <label>:153: ; preds = %144 br label %181 

Github链接

如果仔细看，您会发现上面的代码片段是在LLVM IR中编译的C ++代码片段的前三个块（每行都是基础块的开头）。

LLVM具有允许我们编写“通过”的库-可以转换LLVM IR的代码。 LLVM API允许我们通过遍历模块，函数和基本块轻松地读取和分析LLVM IR，并在将LLVM IR编译为机器代码之前对其进行修改。

现在我们有了基本的块和LLVM API，使用这种简单的算法来计算要执行的指令数量已变得很简单：

1. 我们编写函数IncrementCount，该函数接受一个整数，并在每次调用此值时将其增加一个静态整数。 它需要链接到成员代码。
2. 我们对所有基本块进行迭代。 对于每个基本单元，执行步骤3和4。
3. 我们找到n-该基本单元中的指令数。
4. 我们使用参数n将对IncrementCount函数的调用插入到基本单元的最后一条指令之前。
5. 执行代码后，IncrementCount使用的静态整数将是指令计数器。 可以将其保存在某个位置，然后进行检查。

我们的仪器化IR的工作方式如下：

 ; <label>:140: ; preds = %181, %139 %141 = load i32, i32* %19, align 4 %142 = sext i32 %141 to i64 %143 = icmp slt i64 %142, 20 call void @_Z14IncrementCountm(i32 4) br i1 %143, label %144, label %184 ; <label>:144: ; preds = %140 %145 = getelementptr inbounds %"struct.player_state::State", %"struct.player_state::State"* %2, i32 0, i32 1 %146 = load i32, i32* %19, align 4 %147 = sext i32 %146 to i64 %148 = call dereferenceable(72) %"struct.player_state::Soldier"* @_ZNSt5arrayIN12player_state7SoldierELm20EEixEm( %"struct.std::array.10"* %145, i64 %147) #3 store %"struct.player_state::Soldier"* %148, %"struct.player_state::Soldier"** %20, align 8 %149 = load %"struct.player_state::Soldier"*, %"struct.player_state::Soldier"** %20, align 8 %150 = getelementptr inbounds %"struct.player_state::Soldier", %"struct.player_state::Soldier"* %149, i32 0, i32 2 %151 = load i64, i64* %150, align 8 %152 = icmp eq i64 %151, 0 call void @_Z14IncrementCountm(i32 10) br i1 %152, label %153, label %154 ; <label>:153: ; preds = %144 call void @_Z14IncrementCountm(i32 1) br label %181 

Github链接

如我们所见，在每个基本块的末尾，就在最后一条语句之前，进行了一个IncrementCount调用。 使用IncrementCount使用的静态int，我们可以在每个参与者移动结束时获得指令数。 这种方法是确定性的和跨平台的，因为 如果我们使用相同版本的编译器和相同标志，则可以保证相同的源代码生成相同的LLVM IR。

结论

代码剖析并不是我曾经想过的那么简单。 在完成这样一个相对简单的任务的过程中，我熟悉了编译器的工作方式以及如何编写LLVM传递。 如果您对生成代码感兴趣并想编写自己的文章，则LLVM有一个初学者指南 。 还有一篇很棒的博客文章，我曾经写过自己的文章。 由于LLVM API在主要版本之间不向后兼容，因此请注意所使用的LLVM版本。

您可以在此处获取通行证的源代码。