LLVM札记1: 架构

LLVM作者在文章(LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation)对LLVM做了全面的Review。 指出LLVM是对现在JVM和托管C++的高层虚拟机的补充。是指令级别的,在IR层面和架构设计上有创新设计的。具体表现在将前端,中端,后端区分开来,做到编译时,链接时,安装时,运行时的优化。 传统的GCC构建框架,前端和后端代码是强耦合的。而用LLVM实现的编译器在前端Parser翻译好AST后,直接转换成统一的LLVM IR。在编译优化阶段通过Operation抽象的具体实现对语言进行不同处理,很好的体现了面向对象和模块化思维。

  1. 比如:TensorFlow有很多后端支持,以适配不同硬件需要。如TPU下的XLA,移动设备下的TFLite。
  2. 适配硬件的过程中,很多编译优化手段是通用的。没必要重写一遍。
  3. 针对这个问题,LLVM祭出MLIR来解决这个问题。比如A语言实现了某个常量折叠的优化。那么B语言可以复用A语言的优化时用到的数据结构。具体表现在继承一个表结构,复用操作过程。为什么可以共用,因为共享一个统一的中间层表示。你可以在插入多个IR(也是Multiple Layer Intermediate Representation的来源)来表示复杂的处理过程。这就是万能的软件中间层。
  4. LLVM IR是最底层的IR表示,它的设计创新在与可以对指针以SSA指令的方式来做算数操作。
  5. LLVM的另一个创新在于,自带一个类型系统。这个类型系统是抽象的,与上层具体语言无关的。

MLIR大概过程如下,LLVM IR作为底层表示,MLIR中间由用户扩展表示,并可以使用LLVM IR的数据结构。

mlir architecture
摘自文章

如果要分,其实还有中端。以下引用知乎的一段话”中端是最讲算法的部分,图的连通性,深度和广度优先搜索,强连通分量,最短路,拓扑排序这些基本算法全都用得上。后端思维方式是硬件思维,代码需要嵌入大量硬件相关的信息,并且有很多后端相关的优化。后端的优化相对中端更局部一些。”

MLIR目前只是个DSL工厂,社区里有各行各业的人: 硬件从业者,学者,工程师。具体分为研究算法的,设计新硬件的,做verification的,做ML的。

LLVM IR指令集:

  • 通过SSA的形式表达数据流,可以很清楚的定位代码的数据走向。
  • 显式的表达控制流(包括异常)
  • 显式的表达语言无关的类型信息
对于C代码
for (i = 0;i < N; ++i)
    Sum(&A[i],&P);

用LLVM IR来表达的样子是:

loop:
  // phi 指令位于基本块的开头,第一组是初始值,后面的组可以是label。
  %i.1 = phi int [ 0, %bb0 ], [ %i.2, %loop ]
  // 拿到 A指针 往后 偏移 i 的指针 即&A[i]
  %AiAddr = getelementptr float* %A, int %i.1
  // 调用Sum函数,这里的表示虽然是SSA形式,但表现形式很High Level
  call void %Sum(float %AiAddr, %pair* %P)
  // i变量自增1
  %i.2 = add int %i.1, 1
  //  如果 i 小于 N,那么将结果给 tmp.4 
  %tmp.4 = setlt int %i.1, %N
  // 条件跳转,如果tmp.4 为真,跳转到loop,如果为假,跳出循环。
  br bool %tmp.4, label %loop, label %outloop

LLVM札记2:基本块

BasicBlock:是一个顺序执行的指令容器。BasicBlock是一个Value,被分支和SWITCH语句所引用。 BasicBlock的类型是Type::LabelTy,这个类型代表一个branch分支可以跳转到的标签Label。一个组织良好的基本块只有在结束时才会被中断指令停止。但组织异常的基本块也会出现在构造和修改程序的中间态中出现,验证者需要确保基本块是“组织良好的”。

class BasicBlock final :
         public Value, // Basic blocks are data objects also
         public ilist_node_with_parent<BasicBlock, Function> {
 public:
   using InstListType = SymbolTableList<Instruction>;
 
 private:
   friend class BlockAddress;
   friend class SymbolTableListTraits<BasicBlock>;
 
   InstListType InstList;
   Function *Parent;
}

那么对于下面这段程序,他有多少个基本块呢。

int main(int argc, char **argv) {
  int i, j, k, t = 0;
  for(i = 0; i < 10; i++) {
    for(j = 0; j < 10; j++) {
      for(k = 0; k < 10; k++) {
        t++;
      }
    }
    for(j = 0; j < 10; j++) {
      t++;
    }
  }
  for(i = 0; i < 20; i++) {
    for(j = 0; j < 20; j++) {
      t++;
    }
    for(j = 0; j < 20; j++) {
      t++;
    }
  }
  return t;
}

利用LLVM中的BlockFrequencyInfo类的来统计下基本块信息:

//runOnFunction 
bool BlockFrequencyInfoWrapperPass::runOnFunction(Function &F) {
  BranchProbabilityInfo &BPI =
      getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
  LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  BFI.calculate(F, BPI, LI);
  return false;
}

以上代码会调用LoopInfo Pass来获取循环的信息,如果我们迭代的从这个对象里获取信息,我们可以拿到基本块信息:

unsigned num_Blocks = 0;
  Loop::block_iterator bb;
  for(bb = L->block_begin(); bb != L->block_end();++bb)
    num_Blocks++;
  errs() << "Loop level " << nest << " has " << num_Blocks
<< " blocks\n";

上面代码拿到的只是外层循环的基本块。为了获取内存循环的基本块信息,可以递归的调用 `getSubLoops`函数。

void countBlocksInLoop(Loop *L, unsigned nest) {
  unsigned num_Blocks = 0;
  Loop::block_iterator bb;
  for(bb = L->block_begin(); bb != L->block_end();++bb)
    num_Blocks++;
  errs() << "Loop level " << nest << " has " << num_Blocks
<< " blocks\n";
  std::vector<Loop*> subLoops = L->getSubLoops();
  Loop::iterator j, f;
  for (j = subLoops.begin(), f = subLoops.end(); j != f;
++j)
    countBlocksInLoop(*j, nest + 1);
}
 
virtual bool runOnFunction(Function &F) {
  LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
  errs() << "Function " << F.getName() + "\n";
  for (Loop *L : *LI)
    countBlocksInLoop(L, 0);
  return false;
}

通过用Opt优化ll代码,我们自定义的Pass会被执行

clang –O0 –S –emit-llvm sample.c –o sample.ll
opt  -load (path_to_.so_file)/FuncBlockCount.so  -funcblockcount sample.ll

输出:

Function main
Loop level 0 has 11 blocks
Loop level 1 has 3 blocks
Loop level 1 has 3 blocks
Loop level 0 has 15 blocks
Loop level 1 has 7 blocks
Loop level 2 has 3 blocks
Loop level 1 has 3 blocks

输出很不好理解,而且好像人工也算不出。看不出来基本块是怎么计算出来的。