LLVM 之 IR 篇（7）：如何编写内联 Pass

Author: stormQ

Created: Monday, 23. August 2021 08:17PM

Last Modified: Thursday, 26. August 2021 11:05PM

摘要

本文基于release/12.x版本的 LLVM 源码，介绍了如何编写用于将函数内联化的 Pass——myinliner。该 Pass 仅尝试对带alwaysinline属性的函数调用进行内联优化。通过实现这样一个简单的 Pass，从而初步了解 LLVM IR 的优化——内联，以便更深入地研究相关内容。

研究过程

准备

实现自定义的内联 Pass

测试

准备

本节介绍了编写用于将函数内联化的自定义 Pass——myinliner的前期准备工作（不涉及具体功能的实现）。

step 1： 实现自定义的 Pass

1）添加实现代码

在llvm/lib/Transforms/IPO目录中新建MyInliner.cpp文件，内容如下：

  1 #include "llvm/InitializePasses.h"
  2 #include "llvm/Transforms/IPO.h"
  3 #include "llvm/Transforms/IPO/Inliner.h"
  4 #include "llvm/Analysis/InlineCost.h"
  5 
  6 using namespace llvm;
  7 
  8 #define DEBUG_TYPE "myinliner"
  9 
 10 namespace {
 11 
 12 class MyInlinerLegacyPass : public LegacyInlinerBase {
 13 public:
 14   static char ID;
 15 
 16   MyInlinerLegacyPass() : LegacyInlinerBase(ID) {
 17     initializeMyInlinerLegacyPassPass(*PassRegistry::getPassRegistry());
 18   }
 19 
 20   InlineCost getInlineCost(CallBase &CB) override;
 21 };
 22 
 23 } // anonymous namespace
 24 
 25 InlineCost MyInlinerLegacyPass::getInlineCost(CallBase &CB) {
 26   return InlineCost::getNever("never inliner");
 27 }
 28 
 29 char MyInlinerLegacyPass::ID = 0;
 30 
 31 INITIALIZE_PASS(MyInlinerLegacyPass, DEBUG_TYPE,
 32                 "Inliner for always_inline functions Legacy Pass", false, false)
 33 
 34 Pass *llvm::createMyInlinerLegacyPass() {
 35   return new MyInlinerLegacyPass();
 36 }

注：将源文件MyInliner.cpp添加到llvm/lib/Transforms/IPO目录中，是因为其依赖的Inliner.h文件位于该目录下，从而集成到共享库libLLVMipo.so中。

step 2： 修改 InitializePasses.h

在llvm/include/llvm/InitializePasses.h文件中添加如下内容：

void initializeMyInlinerLegacyPassPass(PassRegistry&);

修改后的内容为：

namespace llvm {
省略 ...
void initializeMyInlinerLegacyPassPass(PassRegistry&);
} // end namespace llvm

step 3： 修改 LinkAllPasses.h

在llvm/include/llvm/LinkAllPasses.h文件中添加如下内容：

(void) llvm::createMyInlinerLegacyPass();

修改后的内容为：

namespace {
  struct ForcePassLinking {
    ForcePassLinking() {
      省略 ...
      (void) llvm::createMyInlinerLegacyPass();
      省略 ...
    }
  } ForcePassLinking; // Force link by creating a global definition.
}

step 4： 修改 IPO.h

1）在llvm/include/llvm/Transforms/IPO.h文件中添加如下内容

Pass *createMyInlinerLegacyPass();

修改后的内容为：

namespace llvm {
省略 ...
Pass *createMyInlinerLegacyPass();
} // End llvm namespace

2）在llvm/include/llvm-c/Transforms/IPO.h文件中添加如下内容（optional）

/** See llvm::createMyInlinerLegacyPass function. */
void LLVMMyInlinerLegacyPass(LLVMPassManagerRef PM);

上述代码在 llvm-c 库中添加一个外部接口。从而，允许其他编程语言通过调用该 C 接口运行自定义的内联 Pass。

step 5： 修改 IPO.cpp

1）在llvm/lib/Transforms/IPO/IPO.cpp文件中添加如下内容

initializeMyInlinerLegacyPassPass(Registry);

修改后的内容为：

void llvm::initializeIPOOpts(PassRegistry &Registry) {
  省略 ...
  initializeMyInlinerLegacyPassPass(Registry);
}

2）在llvm/lib/Transforms/IPO/IPO.cpp文件中添加如下内容（optional）

void LLVMMyInlinerLegacyPass(LLVMPassManagerRef PM) {
  unwrap(PM)->add(createMyInlinerLegacyPass());
}

step 6： 修改 IPO 目录中的 CMakeLists.txt

在llvm/lib/Transforms/IPO/CMakeLists.txt文件中添加如下内容：

MyInliner.cpp

step 7： 编译安装

$ ninja -j8
$ sudo ninja install

安装完成后，查看默认的opt工具是否包含选项myinliner：

$ opt --help | grep myinliner
      --myinliner                                                          - Inliner for always_inline functions Legacy Pass

返回上一级

实现自定义的内联 Pass

本节介绍了自定义内联 Pass——myinliner的实现过程，其关键之处在于如何判定函数是否应该内联化。

step 1： 实现内联化判定逻辑

当继承自类llvm::LegacyInlinerBase时，我们必须在派生类（这里是MyInlinerLegacyPass）中提供纯虚成员函数getInlineCost()的实现，用于决定是否应该将被调用函数内联化。其实现如下：

 25 InlineCost MyInlinerLegacyPass::getInlineCost(CallBase &CB) {
 26   if (!CB.hasFnAttr(Attribute::AlwaysInline)) {
 27     return InlineCost::getNever("no alwaysinline attribute");
 28   }
 29 
 30   Function *Callee = CB.getCalledFunction();
 31 
 32   if (!Callee) {
 33     return InlineCost::getNever("indirect function invocation");
 34   }
 35 
 36   if (Callee->isDeclaration()) {
 37     return InlineCost::getNever("no function definition");
 38   }
 39 
 40   if (Callee->isPresplitCoroutine()) {
 41     return InlineCost::getNever("unsplited coroutine call");
 42   }
 43 
 44   auto IsVisble = isInlineViable(*Callee);
 45   if (!IsVisble.isSuccess()) {
 46     return InlineCost::getNever(IsVisble.getFailureReason());
 47   }
 48 
 49   return InlineCost::getAlways("always inliner");
 50 }

上述代码的逻辑为：

第 25 行，成员函数getInlineCost()的参数CB（数据类型为CallBase &）表示用于调用函数的指令。比如：%r = call i32 @inner1()。
第 26~28 行，判断该指令是否带alwaysinline属性。如果该指令或被调用函数都未带alwaysinline属性，则返回InlineCost::getNever("no alwaysinline attribute");，表示不对其内联化，原因为no alwaysinline attribute。
第 30~34 行，判断被调用函数Callee是否为直接调用。如果是间接调用，则不对其内联化。
第 36~38 行，判断被调用函数是否在本编译单元中有定义。如果被调用函数的定义由其他编译单元提供，则不对其内联化。

注：通过调试发现，如果被调用函数不是在本编译单元中定义的，则程序不会进入MyInlinerLegacyPass::getInlineCost()函数。
第 40~42 行，判断被调用函数是否带coroutine.presplit属性。如果被调用函数带coroutine.presplit属性，则不对其内联化。
第 44~47 行，调用通用的用于判断内联是否可行的函数llvm::isInlineViable()。如果不可行，则不对其内联化。
第 49 行，如果都通过了上述的条件测试，则返回InlineCost::getAlways("always inliner")，表示对其内联化，原因为always inliner。

step 2： 完整的程序

MyInliner.cpp 的完整内容如下：

  1 #include "llvm/InitializePasses.h"
  2 #include "llvm/Transforms/IPO.h"
  3 #include "llvm/Transforms/IPO/Inliner.h"
  4 #include "llvm/Analysis/InlineCost.h"
  5 
  6 using namespace llvm;
  7 
  8 #define DEBUG_TYPE "myinliner"
  9 
 10 namespace {
 11 
 12 class MyInlinerLegacyPass : public LegacyInlinerBase {
 13 public:
 14   static char ID;
 15 
 16   MyInlinerLegacyPass() : LegacyInlinerBase(ID) {
 17     initializeMyInlinerLegacyPassPass(*PassRegistry::getPassRegistry());
 18   }
 19 
 20   InlineCost getInlineCost(CallBase &CB) override;
 21 };
 22 
 23 } // anonymous namespace
 24 
 25 InlineCost MyInlinerLegacyPass::getInlineCost(CallBase &CB) {
 26   if (!CB.hasFnAttr(Attribute::AlwaysInline)) {
 27     return InlineCost::getNever("no alwaysinline attribute");
 28   }
 29 
 30   Function *Callee = CB.getCalledFunction();
 31 
 32   if (!Callee) {
 33     return InlineCost::getNever("indirect function invocation");
 34   }
 35 
 36   if (Callee->isDeclaration()) {
 37     return InlineCost::getNever("no function definition");
 38   }
 39 
 40   if (Callee->isPresplitCoroutine()) {
 41     return InlineCost::getNever("unsplited coroutine call");
 42   }
 43 
 44   auto IsVisble = isInlineViable(*Callee);
 45   if (!IsVisble.isSuccess()) {
 46     return InlineCost::getNever(IsVisble.getFailureReason());
 47   }
 48 
 49   return InlineCost::getAlways("always inliner");
 50 }
 51 
 52 char MyInlinerLegacyPass::ID = 0;
 53 
 54 INITIALIZE_PASS(MyInlinerLegacyPass, DEBUG_TYPE,
 55                 "Inliner for always_inline functions Legacy Pass", false, false)
 56 
 57 Pass *llvm::createMyInlinerLegacyPass() {
 58   return new MyInlinerLegacyPass();
 59 }

返回上一级

测试

在完成编译安装后，分别运行以下测试程序观察自定义内联 Pass——myinliner的优化效果。

step 1： 运行测试程序 1

1）测试程序 1

test1.ll 的内容如下：

define i32 @inner1() #0 {
  %1 = add nsw i32 1, 4
  ret i32 %1
}

define i32 @outer1() #1 {
  %r = call i32 @inner1()
  ret i32 %r
}

define i32 @outer2() #1 {
  %r = call i32 @inner1()
  ret i32 %r
}

attributes #0 = { alwaysinline }
attributes #1 = { noinline optnone }

上述代码中，被调用函数inner1()仅带alwaysinline属性，且在本编译单元中有定义。因此，该函数的所有被调用点都应该内联化。

运行：

$ opt -S -myinliner test1.ll

输出结果如下：

; ModuleID = 'test1.ll'
source_filename = "test1.ll"

; Function Attrs: alwaysinline
define i32 @inner1() #0 {
  %1 = add nsw i32 1, 4
  ret i32 %1
}

; Function Attrs: noinline optnone
define i32 @outer1() #1 {
  ret i32 5
}

; Function Attrs: noinline optnone
define i32 @outer2() #1 {
  ret i32 5
}

attributes #0 = { alwaysinline }
attributes #1 = { noinline optnone }

从上面的输出结果可以看出，自定义内联 Pass——myinliner对inner1()函数的所有被调用点outer1()和outer2()都进行了内联化，符合预期结果。

step 2： 运行测试程序 2

1）测试程序 2

test2.ll 的内容如下：

declare i32 @inner1() #0

define i32 @outer1() #1 {
  %r = call i32 @inner1()
  ret i32 %r
}

define i32 @outer2() #1 {
  %r = call i32 @inner1()
  ret i32 %r
}

attributes #0 = { alwaysinline }
attributes #1 = { noinline optnone }

上述代码中，被调用函数inner1()未在本编译单元中进行定义。因此，该函数的所有被调用点都不应该被内联化。

运行：

$ opt -S -myinliner test2.ll

输出结果如下：

; ModuleID = 'test2.ll'
source_filename = "test2.ll"

; Function Attrs: alwaysinline
declare i32 @inner1() #0

; Function Attrs: noinline optnone
define i32 @outer1() #1 {
  %r = call i32 @inner1()
  ret i32 %r
}

; Function Attrs: noinline optnone
define i32 @outer2() #1 {
  %r = call i32 @inner1()
  ret i32 %r
}

attributes #0 = { alwaysinline }
attributes #1 = { noinline optnone }

从上面的输出结果可以看出，自定义内联 Pass——myinliner不会对inner1()函数的任何被调用点进行内联化，符合预期结果。

step 3： 运行测试程序 3

1）测试程序 3

test3.ll 的内容如下：

$ opt -S -myinliner test3.ll

运行：

define i32 @inner1() {
  %1 = add nsw i32 1, 4
  ret i32 %1
}

define i32 @outer1() #1 {
  %r = call i32 @inner1()
  ret i32 %r
}

define i32 @outer2() #1 {
  %r = call i32 @inner1() alwaysinline
  ret i32 %r
}

attributes #0 = { alwaysinline }
attributes #1 = { noinline optnone }

上述代码中，被调用函数inner1()不带任何属性，且在本编译单元中有定义。另外，函数outer1()中调用inner1()的指令——%r = call i32 @inner1()也未带alwaysinline属性，而函数outer2()中调用inner1()的指令——%r = call i32 @inner1() alwaysinline带了alwaysinline属性。因此，函数inner1()的被调用点outer1()不应该被内联化，而其被调用点outer2()应该被内联化。

输出结果如下：

; ModuleID = 'test3.ll'
source_filename = "test3.ll"

define i32 @inner1() {
  %1 = add nsw i32 1, 4
  ret i32 %1
}

; Function Attrs: noinline optnone
define i32 @outer1() #0 {
  %r = call i32 @inner1()
  ret i32 %r
}

; Function Attrs: noinline optnone
define i32 @outer2() #0 {
  ret i32 5
}

attributes #0 = { noinline optnone }

从上面的输出结果可以看出，函数inner1()的被调用点outer1()未被内联化，而其被调用点outer2()被内联化了，符合预期结果。

返回上一级

研究结论

本文所实现的 Pass——myinliner仅尝试对带alwaysinline属性的函数调用进行内联优化。要实施内联优化，需要同时满足以下条件：

用于函数调用的指令或者被调用函数，至少其中之一带alwaysinline属性
被调用函数必须是直接调用
被调用函数在本编译单元中必须有定义
被调用函数不允许带coroutine.presplit属性
满足通用的内联可行性条件

通过实现这样一个简单的 Pass，我们可以看出其关键之处在于实现内联化判定逻辑。而后续的如何内联化以及如何更新控制流图等逻辑都是由其基类llvm::LegacyInlinerBase实现的。

References

LLVM Cookbook

下一篇：LLVM 之 IR 篇（8）：如何编写别名分析 Pass

上一篇：LLVM 之 IR 篇（6）：如何编写消除死代码 Pass

首页