2012年10月9日 星期二

LLVM : Control Flow Graph

主要紀錄 LLVM Basic Block 走訪方式

建議可搭配 LLVM 寫一個 pass - 教學入門篇 一起玩
另外這是 GCC 的對照組GCC : Control Flow Graph

0. 使用前注意

通常在 LLVM 裡面你會是在某個 Pass 裡面去走訪 CFG,
而這個時候你必須明確告訴 LLVM 你有使用 CFG, 然後他在呼叫你的 pass 之前就一定會幫你準備好
要作到這件事則必須把以下函數加入到你的 Pass 的那個 struct/class 中
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  AU.setPreservesCFG();
}

1. 走訪該函數所有的 Basic Block

Function F;

for (Function::iterator itr = F.begin();
     itr != F.end();
     ++itr) {
  BasicBlock &bb = *itr;
}

2. 走訪 basic block 的所有 successor

BasicBlock bb;
for (succ_iterator itr = succ_begin(&bb);
     itr != succ_end(&bb);
     ++itr) {
     BasicBlock *succ = *itr;

}

3. 走訪 basic block 的所有 Predecessor

BasicBlock bb;
for (pred_iterator itr = pred_begin(&bb);
     itr != pred_end(&bb);
     ++itr) {
     BasicBlock *pred = *itr;

}

4. 取得 Function 的 Entry Basic Block

要注意的是收的變數最好是 Reference !
Function F;

BasicBlock &bb = F.getEntryBlock();

5. Basic Block中所有指令

BasicBlock bb;
for (BasicBlock::iterator itr = bb.begin();
     itr != bb.end();
     ++itr) {
  Instruction &inst = *itr;
}

跳過所有 PHI Node

BasicBlock bb;
for (BasicBlock::iterator itr = bb.getFirstNonPHI();
     itr != bb.end();
     ++itr) {
  Instruction &inst = *itr;
}
另外還有getFirstNonPHIOrDbg () 及 getFirstNonPHIOrDbgOrLifetime () 可以跳過除錯資訊及Lifetime 的資訊

6. 走訪一個函數裡面所有 BB 中的指令之FunctionPass 範例程式碼

#define DEBUG_TYPE "hello"
#include "llvm/Pass.h"
#include "llvm/Function.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/CFG.h"
using namespace llvm;

STATISTIC(HelloCounter, "Counts number of functions greeted");

namespace {
  // Hello - The first implementation, without getAnalysisUsage.
  struct Hello : public FunctionPass {
    static char ID; // Pass identification, replacement for typeid
    Hello() : FunctionPass(ID) {}

    virtual bool runOnFunction(Function &F) {
      ++HelloCounter;
      errs() << "Hello: ";
      errs() << F.getName() << '\n';
      for (Function::iterator itr = F.begin();
           itr != F.end();
           ++itr) {
        BasicBlock &bb = *itr;
        errs() << "Basic block :" << bb.getName () << "\n";
        errs() << "successor : {";
        for (succ_iterator ssitr = succ_begin(&bb);
             ssitr != succ_end(&bb);
             ++ssitr) {
          BasicBlock *ss = *ssitr;
          errs() << ss->getName() <<", ";
        }
        errs() << "}\n";
        errs() << "predecessors : {";
        for (pred_iterator ssitr = pred_begin(&bb);
             ssitr != pred_end(&bb);
             ++ssitr) {
          BasicBlock *ss = *ssitr;
          errs() << ss->getName() <<", ";
        }
        errs() << "}\n";
        for (BasicBlock::iterator iitr = bb.begin();
             iitr != bb.end();
             ++iitr) {
          Instruction &inst = *iitr;
          errs() << inst << '\n';
        }

      }
      return false;
    }
    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.setPreservesCFG();
    }
  };
}

char Hello::ID = 0;
static RegisterPass<Hello> X("hello", "Hello World Pass");