当前位置：网站首页>LLVM系列第二十一章：写一个简单的Loop Pass

LLVM系列第二十一章：写一个简单的Loop Pass

2022-08-02 14:07:00 【飞翼剑仆】

系列文章目录

本文目录

前言
一、项目结构
二、项目细节
- 1. 程序模块
- 3. Simple Loop Pass
三、编译
四、总结

前言

在此记录下在LLVM上写一个简单的Loop Pass的过程，以备查阅。

开发环境的配置请参考第一章《LLVM系列第一章：编译LLVM源码》。

Loop Pass，是在程序中的每个循环(Loop)上执行的。在运行Loop Pass的时候，，每个循环之间是互不影响的。Loop Pass执行的顺序是由内而外的，即内层的循环先执行，外层的循环后执行。

本章我们就来写一个最简单的Loop Pass。

一、项目结构

我们把这个简单的项目命名为SimpleLoopPass。可以参考LLVM的源码中其它Pass流程的组织结构，来组织我们自己的代码（示例）：

llvm-project/llvm
├── ...
├── lib
│   └── Transforms
│       ├── CMakeLists.txt
│       └── SimpleLoopPass
│           ├── CMakeLists.txt
│           └── SimpleLoopPass.cpp
└── ...

二、项目细节

1. 程序模块

这个简单的项目只包含了一个模块：

SimpleLoopPass，一个简单的Loop Pass模块

SimpleLoopPass将会对每一个循环进行处理，即把循环中所有的子循环和Basic Block等信息打印出来。

注意，我们需要把SimpleLoopPass项目加入到LLVM Transforms父项目中，即指示CMake在编译LLVM源码的同时，也要编译SimpleLoopPass项目。

以下是跟项目组织结构相关的部分CMake脚本。

(1) lib/Transforms/SimpleLoopPass/CMakeLists.txt文件（示例）：

# CMakeLists.txt

add_llvm_library(SimpleLoopPass MODULE BUILDTREE_ONLY
    SimpleLoopPass.cpp

    PLUGIN_TOOL
    opt
)

(2) lib/Transforms/CMakeLists.txt文件（示例）：

...
add_subdirectory(SimpleLoopPass)
...

3. Simple Loop Pass

SimpleLoopPass的实现在文件lib/Transforms/SimpleLoopPass/SimpleLoopPass.cpp中：

// SimpleLoopPass.cpp

#include "llvm/IR/PassManager.h"
#include "llvm/Passes/PassBuilder.h"
#include "llvm/Passes/PassPlugin.h"
#include "llvm/Support/raw_ostream.h"

#include <iostream>

using namespace llvm;
using std::cout;
using std::endl;

namespace
{
    
    class SimpleLoopPass : public PassInfoMixin<SimpleLoopPass>
    {
    
    public:

        PreservedAnalyses run(Loop& loop,
                              LoopAnalysisManager& analysisManager,
                              LoopStandardAnalysisResults& analysisResults,
                              LPMUpdater& updater)
        {
    
            cout << "Loop: " << loop.getName().str() << endl;

            // Print out all the sub-loops in this loop
            cout << endl << " Sub-Loop Count: " << loop.getSubLoops().size() << endl;
            for (const auto& subLoop : loop)
            {
    
                cout << " Sub-Loop: " << subLoop->getName().str() << endl;
            }

            // Print out all the basic blocks in this loop
            cout << endl << " Basic Block Count: " << loop.getNumBlocks() << endl;
            for (const auto& basicBlock : loop.getBlocks())
            {
    
                cout << " Basic Block: " << basicBlock->getName().str() << endl;
            }

            cout << endl << endl;

            // Assuming we did not change anything of the IR code
            return PreservedAnalyses::all();
        }
    };
} // namespace

// This is the new way of registering our pass
extern "C" PassPluginLibraryInfo LLVM_ATTRIBUTE_WEAK llvmGetPassPluginInfo()
{
    
    return {
    LLVM_PLUGIN_API_VERSION, "SimpleLoopPass", "v0.1", [](PassBuilder& passBuilder) {
    
                passBuilder.registerPipelineParsingCallback(
                    [](StringRef name, LoopPassManager& passManager, ArrayRef<PassBuilder::PipelineElement>) {
    
                        if (name == "simple-loop-pass")
                        {
    
                            passManager.addPass(SimpleLoopPass());
                            return true;
                        }

                        return false;
                    });
            }};
}

三、编译

1. 生成项目文件

用CMake工具生成项目文件（示例）：

cd /path/to/llvm-project
mkdir build
cd build

cmake -G Ninja -DLLVM_ENABLE_PROJECTS=clang ../llvm

输出log如下（示例）：

-- clang project is enabled
-- clang-tools-extra project is disabled
-- ...
-- Ninja version: 1.10.2
-- Found ld64 - /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/ld
-- ...
-- LLVM host triple: x86_64-apple-darwin20.6.0
-- LLVM default target triple: x86_64-apple-darwin20.6.0
-- ...
-- Configuring done
-- Generating done
-- Build files have been written to: .../llvm-project/build

2. 编译

用ninja进行编译（示例）：

ninja

如果我们是在第一章的编译LLVM完成之后，再编译此项目，则仅仅需要编译SimpleLoopPass项目即可。当然，这是ninja自动就能识别出来的，即所谓的增量编译技术。输出log如下（示例）：

[4/4] Linking CXX shared module lib/SimpleLoopPass.dylib

3. 运行

为了简单起见，假设我们要对以下SimpleLoopTest.c文件中C代码进行处理（示例）：

// SimpleLoopTest.c

int array[1024];

void SimpleLoopTest()
{
    
    for (int i = 0; i < 100; i++)
    {
    
        array[i] = i;
    }

    for (int i = 101; i < 200; i++)
    {
    
        array[i] = array[i] * i;
    }
}

可以用clang生成IR代码，命令如下（示例）：

mv ../llvm/lib/Transforms/SimpleLoopPass/Tests/SimpleLoopTest.c.txt ../llvm/lib/Transforms/SimpleLoopPass/Tests/SimpleLoopTest.c

clang -S -emit-llvm -O1 ../llvm/lib/Transforms/SimpleLoopPass/Tests/SimpleLoopTest.c -o ../llvm/lib/Transforms/SimpleLoopPass/Tests/SimpleLoopTest.ll

生成IR代码如下（示例）：

; ModuleID = '../llvm/lib/Transforms/SimpleLoopPass/Tests/SimpleLoopTest.c'
source_filename = "../llvm/lib/Transforms/SimpleLoopPass/Tests/SimpleLoopTest.c"
target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx11.0.0"

@array = dso_local local_unnamed_addr global [1024 x i32] zeroinitializer, align 16

; Function Attrs: nofree norecurse nounwind ssp uwtable
define dso_local void @SimpleLoopTest() local_unnamed_addr #0 {
    
entry:
  br label %for.body

for.body:                                         ; preds = %entry, %for.body
  %indvars.iv24 = phi i64 [ 0, %entry ], [ %indvars.iv.next25, %for.body ]
  %arrayidx = getelementptr inbounds [1024 x i32], [1024 x i32]* @array, i64 0, i64 %indvars.iv24
  %0 = trunc i64 %indvars.iv24 to i32
  store i32 %0, i32* %arrayidx, align 4, !tbaa !3
  %indvars.iv.next25 = add nuw nsw i64 %indvars.iv24, 1
  %exitcond26.not = icmp eq i64 %indvars.iv.next25, 100
  br i1 %exitcond26.not, label %for.body5, label %for.body, !llvm.loop !7

for.cond.cleanup4:                                ; preds = %for.body5
  ret void

for.body5:                                        ; preds = %for.body, %for.body5
  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body5 ], [ 101, %for.body ]
  %arrayidx7 = getelementptr inbounds [1024 x i32], [1024 x i32]* @array, i64 0, i64 %indvars.iv
  %1 = load i32, i32* %arrayidx7, align 4, !tbaa !3
  %2 = trunc i64 %indvars.iv to i32
  %mul = mul nsw i32 %1, %2
  store i32 %mul, i32* %arrayidx7, align 4, !tbaa !3
  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
  %exitcond.not = icmp eq i64 %indvars.iv.next, 200
  br i1 %exitcond.not, label %for.cond.cleanup4, label %for.body5, !llvm.loop !10
}

attributes #0 = {
     nofree norecurse nounwind ssp uwtable "disable-tail-calls"="false" "frame-pointer"="all" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="true" "stack-protector-buffer-size"="8" "target-cpu"="penryn" "target-features"="+cx16,+cx8,+fxsr,+mmx,+sahf,+sse,+sse2,+sse3,+sse4.1,+ssse3,+x87" "tune-cpu"="generic" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{
    !0, !1}
!llvm.ident = !{
    !2}

!0 = !{
    i32 1, !"wchar_size", i32 4}
!1 = !{
    i32 7, !"PIC Level", i32 2}
!2 = !{
    !"clang version 12.0.1 (https://github.com/llvm/llvm-project fed41342a82f5a3a9201819a82bf7a48313e296b)"}
!3 = !{
    !4, !4, i64 0}
!4 = !{
    !"int", !5, i64 0}
!5 = !{
    !"omnipotent char", !6, i64 0}
!6 = !{
    !"Simple C/C++ TBAA"}
!7 = distinct !{
    !7, !8, !9}
!8 = !{
    !"llvm.loop.mustprogress"}
!9 = !{
    !"llvm.loop.unroll.disable"}
!10 = distinct !{
    !10, !8, !9}

运行SimpleLoopPass（示例）：

./bin/opt -load-pass-plugin=lib/SimpleLoopPass.dylib -passes="simple-loop-pass" -disable-output ../llvm/lib/Transforms/SimpleLoopPass/Tests/SimpleLoopTest.ll

输出结果如下（示例）：

Loop: for.body

    Sub-Loop Count: 0

    Basic Block Count: 1
        Basic Block: for.body


Loop: for.body5

    Sub-Loop Count: 0

    Basic Block Count: 1
        Basic Block: for.body5