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 的合成.

DFG @ c++

如果你對 llvm 很熟的話. 那麼這篇你看了應該會吐血....因為....小弟沒把 Reference manual 看熟,就自己硬幹底層的 class 導致跟 frond end 的 llvm interface 接起來有點醜. 感覺是小弟自己重複定義了 llvm 已有的 class. 如 llvm 中的 Instruction 可用 dyn_cast 的方式轉成 binary operator 跟 Value 的型態. 而我們定義了 Node, Edge 來描述 Instruction 的結構.... 類似的情況. 而 llvm 可以藉由自己定義的 library 來改變 IR. 而我們是改變 Graph 的 type... 反正就是一個字來形容 "菜" .XD 主要的問題就是在於 llvm 是用 Transport Triggered Architecture 的方式來 link dependent instruction. 就 (tmp3+tmp1)>>1 的結果而言. llvm 會把 tmp3+tmp1 的結果(%add) 的 pointer 指向 next dependent 的 instruction. 且 (%add) 的 result 沒有 API 可以 Get. 雖然可以用 iterator 從最後一個 Instruction 把每個 Instruction 的關係找出來. 但這樣好像有點暴力...

%add = add nsw i32 %tmp3, %tmp1
%shr = ashr i32 %add, 1

還好有提早發現到這個問題,不然再繼續走下去.會更加吐血吧... project: https://github.com/funningboy/XVerilog/blob/master/main.cpp 目前完成 Node : 定義每個 hardware resource ex: reg, alu, mem .... Edge : 定義每個 hardware resource 彼此的相依關係 ex: prelist, nxtlist... Graph : 定義個Basic Blcok內的 Node, Edge. cycle check : 針對每個 instruction 的 Delay 來判斷是否要插入 reg schedule : ASAP/ALAP refs: TCE project: Co-design of application-specific processors with LLVM-based compilation support How do I get the result of an instruction?