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
输出很不好理解,而且好像人工也算不出。看不出来基本块是怎么计算出来的。