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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注