LLVM + BOOST = LMBOOST....

底下就把 LLVM + Boost c++ 做簡單的結合. 有 Lib 就是個 "爽"

#define DEBUG_TYPE "BoostPass"

#include "llvm/Pass.h"
#include "llvm/Module.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/Analysis/Dominators.h"

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>


#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>

using namespace llvm;
using namespace boost;
using namespace std;

 
    template<class T>
    class BoostEdge {
     
       public:
         BoostEdge(T iEdgeFm,
                   T iEdgeTo) : InstructionEdgeFm(iEdgeFm),
                                InstructionEdgeTo(iEdgeTo) {}
        ~BoostEdge(){} 

         T GetInstructionEdgeFm(){ return InstructionEdgeFm; }
         T GetInstructionEdgeTo(){ return InstructionEdgeTo; }

       private:
        T InstructionEdgeFm;
        T InstructionEdgeTo;
    };

    class BoostPass : public FunctionPass {

        public:

            static char ID;

            BoostPass() : FunctionPass(ID) { LLVM2BoostInx=0; }

           ~BoostPass(){ 
                         BoostEdgeList.clear();
                         BoostNodeList.clear();
                         LLVM2BoostMapList.clear();
                         Boost2LLVMMapList.clear(); 
                       } 

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

            bool runOnFunction(Function &F);

            void setInstructionLLVM2Boost(Instruction *inst);

            int  getIndexLLVM2Boost(Instruction *inst);


       private:
          std::vector<BoostEdge<int>*>  BoostEdgeList;          
          std::vector<Instruction*>     BoostNodeList;

          std::map<Instruction*,int>    LLVM2BoostMapList;
          std::map<int,Instruction*>    Boost2LLVMMapList;

          int LLVM2BoostInx;
    };


  void  BoostPass::setInstructionLLVM2Boost(Instruction *inst){

        if(std::find(BoostNodeList.begin(),BoostNodeList.end(), inst) == BoostNodeList.end()){
           BoostNodeList.push_back(inst);
           LLVM2BoostMapList[inst] = LLVM2BoostInx++; 
        } 
  }

  int  BoostPass::getIndexLLVM2Boost(Instruction *inst){

       std::map<Instruction*,int>::iterator it = LLVM2BoostMapList.find(inst);

       if(it!=LLVM2BoostMapList.end())
       return it->second;

       return -1;
  }

  bool BoostPass::runOnFunction(Function &F) {
 
        for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB) {
                   BasicBlock  *BC = dyn_cast<BasicBlock>(BB);

             for (BasicBlock::iterator IB = BB->begin(), IE = BB->end(); IB != IE; ++IB) {  
                          Instruction *IT = dyn_cast<Instruction>(IB);

                  // @ Instruction::Add , Sub ...
                  if(dyn_cast<BinaryOperator>(IT)){

                    for (Instruction::use_iterator uit = IT->use_begin(); uit!= IT->use_end(); ++uit) {

                        if(dyn_cast<BinaryOperator>(*uit)){
                           Instruction *NT = dyn_cast<Instruction>(*uit);

                           //@ same basic block 
                           if( NT->getParent()==BC ){
                               errs() << "LLVM->From Instruction :: " << *IT << "\n";
                               errs() << "LLVM->To   Instruction :: " << *NT << "\n";
                               errs() << "\n";

                               setInstructionLLVM2Boost(IT);
                               setInstructionLLVM2Boost(NT);

                               int it = getIndexLLVM2Boost(IT); 
                               int nt = getIndexLLVM2Boost(NT);
                               
                               assert( it!=-1 && nt!=-1 && "LLVM2Boost Error<1>");                               

                               BoostEdge<int> *BtEdgePtr = new BoostEdge<int>(it,nt);
                               BoostEdgeList.push_back(BtEdgePtr); 
                          }
                        }
                    }
                 }
          
          } //end Instruction iterator

          // @ LLVM 2 Boost Graph
          const unsigned int NodeSize = BoostNodeList.size()+1;  
          const unsigned int EdgeSize = BoostEdgeList.size();

          if( NodeSize>1 && EdgeSize>0 ){

          typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;

          typedef std::pair<int, int> Edge;

          Graph g(NodeSize);

          for(std::vector<BoostEdge<int>*>::iterator IE = BoostEdgeList.begin(); IE != BoostEdgeList.end(); ++IE)
              boost::add_edge((*IE)->GetInstructionEdgeFm(), (*IE)->GetInstructionEdgeTo(), g);

          
          // get the property map for vertex indices
          typedef property_map<Graph, vertex_index_t>::type IndexMap;
          IndexMap index = get(vertex_index, g);

          std::cout << "vertices(g) = ";
          typedef graph_traits<Graph>::vertex_iterator vertex_iter;
          std::pair<vertex_iter, vertex_iter> vp;
          for (vp = vertices(g); vp.first != vp.second; ++vp.first)
            std::cout << index[*vp.first] <<  " ";
            std::cout << std::endl;

          // @ Boost Graph Algorithm
          // ....


          // @ Boost Graph Result 2 LLVM 
          // ...
 
         }

        BoostNodeList.clear();
        BoostEdgeList.clear();

        LLVM2BoostMapList.clear();
        Boost2LLVMMapList.clear();

        LLVM2BoostInx =0;
   
        } // end basic block iterator

       return true;
    }

    char BoostPass::ID = 0;
    RegisterPass<BoostPass> PXX("Boost_pass", "Boost c++ lib test",false,false);
     

compile

opt -load Debug+Asserts/lib/Boost_t.so  -Boost_pass test/scalar.bc

ps: 後來發現可以用 std::pair 來取代 Edge class..XD Table of Contents: the Boost Graph Library

Sample Pass @ LLVM

寫了個簡單的 sample @ LLVM, 就當練習練習...XD. 不過沒有考慮 function 的正確性.

#define DEBUG_TYPE "SamplePass"

#include "llvm/Pass.h"
#include "llvm/Module.h"
#include "llvm/Function.h"
#include "llvm/Instructions.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/Analysis/Dominators.h"

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>

using namespace llvm;

using std::set;
using std::map;
using std::vector;
using std::pair;
using std::string;

    class SamplePass : public FunctionPass {

        public:

            static char ID;

            SamplePass() : FunctionPass(ID) {}

            virtual void getAnalysisUsage(AnalysisUsage &AU) const {

                  AU.setPreservesCFG();
            }

            bool runOnFunction(Function &F);

    };


  bool SamplePass::runOnFunction(Function &F) {
 
        for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB) {
                   BasicBlock  *BC = dyn_cast<BasicBlock>(BB);

             std::vector<Instruction*> RemoveList;
                                       RemoveList.clear();
  
             for (BasicBlock::iterator IB = BB->begin(), IE = BB->end(); IB != IE; ++IB) {  
                          Instruction *IT = dyn_cast<Instruction>(IB);

                // @ get Array Load instruction 
                 if (dyn_cast<GetElementPtrInst>(IB)) {

                    for (Instruction::use_iterator uit = IT->use_begin(); uit!= IT->use_end(); ++uit) {
                        if(dyn_cast<LoadInst>(*uit)){
                           
                           Instruction *NT = dyn_cast<Instruction>(*uit);
                         
                           errs() << "getelementptr ::" << *IT << "\n";
                           errs() << "load          ::" << *NT << "\n";
                           errs() << "\n";
                        }
                    }
                 }

              // @ get ALL PHI values && same basic block check        
                if(dyn_cast<PHINode>(IT)){
                   PHINode *phi = dyn_cast<PHINode>(IT);

                   unsigned incs = phi->getNumIncomingValues(); 
                   for(unsigned i =0; i<incs; i++){ 

                      BasicBlock  *INB = phi->getIncomingBlock(i);
                      Value       *val = phi->getIncomingValue(i);

                      if( INB==BC ){
                         errs() << "Instruct  ::" << *IT << "\n";
                         errs() << "PHI value ::" << *val << "\n";
                         errs() << "\n";
                      }  
                   }
                }

              // @ get Binary Operator Instruction::Add
              if(dyn_cast<BinaryOperator>(IT)){
                 BinaryOperator* bin = dyn_cast<BinaryOperator>(IT);

                if (bin->getOpcode() == Instruction::Add) {
                    Value *val0 = IT->getOperand(0);
                    Value *val1 = IT->getOperand(1);

                    errs() << "Add Value0 ::" << *val0 << "\n";
                    errs() << "Add Value1 ::" << *val1 << "\n"; 
                }
              }


            // @ insert Sub Instruction after Add Instruction
            if(dyn_cast<BinaryOperator>(IT)){ 
               BinaryOperator* bin = dyn_cast<BinaryOperator>(IT);

               if (bin->getOpcode() == Instruction::Add){
                   Value *val0 = IT->getOperand(0);
                   Value *val1 = IT->getOperand(1);

                   BinaryOperator::Create(Instruction::Sub, val0, val1, "SUB", IT);
      
               }
            }

            // @ remove ALL Instruction::Add && link the Value0 at next connect
            if(dyn_cast<BinaryOperator>(IT)){
               BinaryOperator* bin = dyn_cast<BinaryOperator>(IT);

                if (bin->getOpcode() == Instruction::Add) {

                       Value *val0 = IT->getOperand(0);

                       IT->replaceAllUsesWith(val0);
                       RemoveList.push_back(IT);
             }
           }

           
          } //end Instruction iterator
  
         // @ remove ALL Instruction::Add 
         for(std::vector<Instruction*>::iterator rmIt  = RemoveList.begin();
                                                 rmIt != RemoveList.end();   ++rmIt){

                   Instruction *It = dyn_cast<Instruction>(*rmIt);
                                It->eraseFromParent();
          }

          RemoveList.clear();


        } // end basic block iterator

        return true;
    }

    char SamplePass::ID = 0;
    RegisterPass<SamplePass> PXX("Sample_pass", "extract Sample DFG",false,false);

compile

opt -load Debug+Asserts/lib/Parallel_t.so  -Sample_pass test/opt_scalar.bc | llvm-dis | grep sub

parallel synthesis @ llvm

我們在machine code 上看到的指令是cycle by cycle 的形式,但實際在硬體上卻可以透過多個 hardware resource 做到 parallel 的方式.如在 Verilog 的語法上用 '(' ')' 來 assign hardware. 底下就用 C 2 Verilog 內的例子來講解 ps: 不管 RHS, LHS 的相關性.這邊只考慮同 alu type 的 instruction. 且至少連續3個 ALU 以上的 instruction. 假設一個sample 的 hardware IP named test. ex : sample c code

void test(int a,int b, int c, int d, int e, int *o){
     *o = a+b+c+d+e;
}

透過 GCC compile 之後的 machine code 可以看出是 cycle by cycle 的型態.

test:
        movl    8(%esp), %eax
        addl    4(%esp), %eax
        addl    12(%esp), %eax
        addl    16(%esp), %eax
        addl    20(%esp), %eax
        movl    24(%esp), %ecx
        movl    %eax, (%ecx)
        ret

在 llvm IR 中也是如此.

define void @test(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e, i32* nocapture %o) nounwind {
entry:
  %add = add i32 %b, %a
  %add3 = add i32 %add, %c
  %add5 = add i32 %add3, %d
  %add7 = add i32 %add5, %e
  store i32 %add7, i32* %o, align 4, !tbaa !0
  ret void
}

轉成 Graph 來看.大致是如此 但是從 hardware 的角度來看,不管 hardware resource constrains 可以長成這樣子 這邊我們只要用到3個clock cycle 跟兩個 ALU IP ADDs 就可以完成.有了以上的觀念後. 其實最後目標就是改變 llvm 的 IR 型態來符合我們的假設. 改變後的 IR, 可發現出 parallel 的方式.

define void @test(i32 %a, i32 %b, i32 %c, i32 %d, i32 %e, i32* nocapture %o) nounwind {
entry:
  %lowlevel = add i32 %b, %a
  %lowlevel1 = add i32 %c, %d
  %lowlevelOdd = add i32 %e, %lowlevel1
  %headNode = add i32 %lowlevel, %lowlevelOdd
  store i32 %headNode, i32* %o, align 4, !tbaa !0
  ret void
}

ps: 其實在 verilog 中,可以用 (a+b)+(c+d)+e 的方式來做出 parallel 的合成.