CustomPass.cpp

//===----------------------------------------------------------------------===//
//
//                   Interprocedural Dependency Checker
//
//===----------------------------------------------------------------------===//
//
//  Copyright (C) 2017-2018. rollrat. All Rights Reserved.
//
//===----------------------------------------------------------------------===//

#include "llvm/IR/Function.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/Pass.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Support/Casting.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/LinkAllPasses.h"
#include <stack>

#define DEBUG_TYPE "dependency-check"

/// Dependency check과정에서 확인된 inst를 콘솔에 
/// 출력할 지의 여부를 결정합니다.
#define IDC_PRINT_INSTRUCTION                       0

/// Dependency check 결과를 출력할 지의 여부를 결정합니다.
#define IDC_PRINT_RESULT                            1

/// 함수가 정의되지 않은 경우, 콘솔에 메시지를 출력합니다.
#define IDC_PRINT_MSG_EMPTY_FUNCTION                1

/// 함수가 정의되지 않은 경우, 해당 함수의 함수인자가
/// 리턴값에 영향을 미치는지 여부를 결정합니다.
#define IDC_EMPTY_FUNCTION_PARAM_AFFECT_RETURN      1

/// branch map을 이용한 검사를 할 지의 여부를 결정합니다.
#define IDC_SCAN_CONTROL_FLOW                       1


using namespace llvm;

/*
  Same name function have same algorithm.
*/

namespace {

  static const char *llvm_annotate_variable = "llvm.var.annotation";
  
  ///---------------------------------------------------------
  ///
  ///          Branch Map
  ///
  ///---------------------------------------------------------

  class BlockNode
  {
    BasicBlock *basic_block;
    BranchInst *branch_inst;
    SmallVector<BlockNode *, 4> from_node;
    SmallVector<BlockNode *, 4> to_node;

  public:

    BlockNode(BasicBlock *BB) : basic_block(BB), branch_inst(nullptr) { }
    
    void addFromNode(BlockNode *BN) { from_node.push_back(BN); }
    SmallVector<BlockNode *, 4>& getFromNodes() { return from_node; }
    void addToNode(BlockNode *BN) { to_node.push_back(BN); }
    SmallVector<BlockNode *, 4>& getToNodes() { return to_node; }

    void setBranchInst(BranchInst *BI) { branch_inst = BI; }
    BranchInst *getBranchInst() { return branch_inst; }

    BasicBlock *getBasicBlock() { return basic_block; }
  };

  class BranchManager
  {
    Function *function;
    BlockNode *start;
    std::vector<BlockNode *> nodes;

  public:

    BranchManager(Function *F) : function(F) 
    {
      if (!F->isIntrinsic()) 
      {
        start = new BlockNode(&F->getEntryBlock());
        nodes.push_back(start);
        if (BranchInst *bi = dyn_cast<BranchInst> (&start->getBasicBlock()->back())) {
          start->setBranchInst(bi);
          for (size_t i = 0; i < bi->getNumSuccessors(); i++)
            start->addToNode(run(bi->getSuccessor(i), start));
        }
      }
    }

    BlockNode *getNodeFromInstruction(Instruction *inst)
    {
      for (BlockNode *bn : nodes)
        for (Instruction& i : *bn->getBasicBlock())
          if (&i == inst)
            return bn;
      return nullptr;
    }

  private:

    BlockNode *run(BasicBlock *BB, BlockNode *P)
    {
      BlockNode *node = new BlockNode(BB);
      node->addFromNode(P);
      nodes.push_back(node);
      Instruction *last = &BB->back();
      if (BranchInst *bi = dyn_cast<BranchInst> (last))
      {
        node->setBranchInst(bi);
        for (size_t i = 0; i < bi->getNumSuccessors(); i++)
        {
          for (size_t j = 0; j < nodes.size(); j++)
            if (nodes[j]->getBasicBlock() == bi->getSuccessor(i))
            {
              node->addToNode(nodes[j]);
              nodes[j]->addFromNode(node);
              goto FINISH;
            }
          node->addToNode(run(bi->getSuccessor(i), node));
        FINISH:
          ;
        }
      }
      return node;
    }

  };

  ///---------------------------------------------------------
  ///
  ///                    Pass Tools
  ///
  ///---------------------------------------------------------

  class InstructionDependency
  {
    using PairType = std::pair<Instruction *, bool>;
    using InstsType = std::vector<PairType>;
    InstsType insts;

  public:

    bool hasInstructoin(Instruction *I, bool P = true)
    { 
      for (auto& pair : insts) 
        if (pair.first == I && (pair.second == P || pair.second))
          return true;
      return false;
    }
    void addInstruction(Instruction *I, bool P = true) 
    {
      for (auto& pair : insts)
        if (pair.first == I)
        {
          if (P) pair.second = true;
          return;
        }
      insts.push_back(PairType(I,P));
    }

    InstsType::iterator begin() { return insts.begin(); }
    InstsType::const_iterator begin() const { return insts.begin(); }
    InstsType::iterator end() { return insts.end(); }
    InstsType::const_iterator end() const { return insts.end(); }
  };
  
  class InstructionDependencyMap
  {
    using ValueMap = std::map<Value *, InstructionDependency *>;
    ValueMap value_map;

  public:

    InstructionDependencyMap() : value_map() { }
    ~InstructionDependencyMap() { for (auto& id : value_map) delete id.second; }
    bool hasDependency(Value *V) { return value_map.find(V) != value_map.end(); }
    InstructionDependency* getDependency(Value *V) { return value_map[V]; }
    void addDependency(Value *V, InstructionDependency *ID) { value_map[V] = ID; }

    ValueMap::iterator begin() { return value_map.begin(); }
    ValueMap::const_iterator begin() const { return value_map.begin(); }
    ValueMap::iterator end() { return value_map.end(); }
    ValueMap::const_iterator end() const { return value_map.end(); }
  };

  class ArgumentInstructionDependencyMap
  {
    using IndexMap = std::map<int, InstructionDependency *>;
    IndexMap index_map;

  public:

    ArgumentInstructionDependencyMap() : index_map() { }
    bool hasDependency(int ArgNo) { return index_map.find(ArgNo) != index_map.end(); }
    InstructionDependency* getDependency(int ArgNo) { return index_map[ArgNo]; }
    void addDependency(int ArgNo, InstructionDependency *ID) { index_map[ArgNo] = ID; }

    IndexMap::iterator begin() { return index_map.begin(); }
    IndexMap::const_iterator begin() const { return index_map.begin(); }
    IndexMap::iterator end() { return index_map.end(); }
    IndexMap::const_iterator end() const { return index_map.end(); }
  };

  class FunctionArgumentDependency
  {
    Argument *argument;
    std::vector<bool> argument_dependency;

  public:

    FunctionArgumentDependency(Argument *A, size_t argc)
      : argument(A), argument_dependency(argc) { }
    Argument* getArgument() { return argument; }
    bool hasArgumentDependency(int ix) { return argument_dependency[ix]; }
    void setArgumentDependency(int ix) { argument_dependency[ix] = true; }
  };
  
  /// 이 클래스는 다음과 같은 세 가지 정보를 가지고 있습니다.
  /// 1. 함수인자가 반환값에 미치는 영향
  /// 2. 함수인자가 어떤 함수인자에 미치는 영향
  /// 3. 위 두가지 중 한 개 이상의 경우에서 영향을 미치는
  ///    호출되는 함수들의 목록
  class FunctionDependency
  {
    Function *function;
    std::vector<bool> return_dependency;
    SmallVector<FunctionArgumentDependency *, 8> arg_dependency;
    SmallVector<FunctionDependency *, 8> call_dependency;
    InstructionDependencyMap *insts_map = nullptr;
    InstructionDependency *return_instruction_dependency = nullptr;
    ArgumentInstructionDependencyMap *arg_map = nullptr;
    BranchManager *branch_manager;

  public:

    FunctionDependency(Function *F) 
      : function (F), return_dependency(F->arg_size()), arg_dependency(F->arg_size()) 
    {
      branch_manager = new BranchManager(F);
      for (size_t i = 0; i < F->arg_size(); i++)
      {
        Argument *arg = F->arg_begin() + i;
        arg_dependency[i] = new FunctionArgumentDependency(arg, F->arg_size());
      }
    }

    ~FunctionDependency()
    {
      if (insts_map) delete insts_map;
      if (return_instruction_dependency) delete return_instruction_dependency;
      if (arg_map) delete arg_map;
      delete branch_manager;
    }

    Function* getFunction() { return function; }

    /// 반환값에 영향을 미치는 함수인자를 알아볼 수 있습니다.
    bool hasReturnDependency(int ix) { return return_dependency[ix]; }
    void setReturnDependency(int ix) { return_dependency[ix] = true; }

    /// 어떤 함수인자가 특정 함수인자에 영향을 미치는지 알아볼 수 있습니다.
    FunctionArgumentDependency *getFunctionArgumentDependency(size_t i) { return arg_dependency[i]; }

    void addFunctionDependency(FunctionDependency *FD) { call_dependency.push_back(FD); }
    size_t getFunctionDependencyNum() { return call_dependency.size(); }
    FunctionDependency* getFunctionDependency(size_t i) { return call_dependency[i]; }

    /// annotated variables instruction dependency
    void setInstructionDependencyMap(InstructionDependencyMap *IDM) { insts_map = IDM; }
    InstructionDependencyMap *getInstrctionDependencyMap() { return insts_map; }

    /// return instruction dependency
    void setReturnInstructionDependency(InstructionDependency *ID) { return_instruction_dependency = ID; }
    InstructionDependency *getReturnInstructionDependency() { return return_instruction_dependency; }

    /// argument instruction dependency
    void setArgumentInstructionDependencyMap(ArgumentInstructionDependencyMap *AIDM) { arg_map = AIDM; }
    ArgumentInstructionDependencyMap *getArgumentInstructionDependencyMap() { return arg_map; }

    BranchManager *getBranchManager() { return branch_manager; }
  };
  
  class DependencyMap
  {
    using FunctionMap = std::map<Function *, FunctionDependency *>;
    FunctionMap function_map;

  public:

    DependencyMap() : function_map() { }
    ~DependencyMap() { for (auto& fd : function_map) delete fd.second; }
    bool hasDependency(Function *F) { return function_map.find(F) != function_map.end(); }
    FunctionDependency* getDependency(Function *F) { return function_map[F]; }
    void addDependency(Function *F, FunctionDependency *FD) { function_map[F] = FD; }
  };
  
  ///---------------------------------------------------------
  ///
  ///          Dependency Check Routine
  ///
  ///---------------------------------------------------------
  
  static DependencyMap *recursion_map;

  class DependencyChecker
  {
  public:

    static void run(FunctionDependency *FD, DependencyMap *DM)
    {
      if (FD->getFunction()->isIntrinsic()) return;
      if (FD->getFunction()->empty()) {
#if IDC_PRINT_MSG_EMPTY_FUNCTION
        errs() << "Function is not defined!\n";
#endif
#if IDC_EMPTY_FUNCTION_PARAM_AFFECT_RETURN
        for (size_t argc = 0; argc < FD->getFunction()->arg_size(); argc++)
          FD->setReturnDependency(argc);
#endif
        return;
      }

      /// 어떤 함수인자가 반환값에 영향을 미치는지 검사합니다.
      FunctionReturnDependencyChecker return_checker(FD, DM);

      /// 어떤 함수인자가 특정 함수인자에 미치는 영향을 검사합니다.
      FunctionArgumentDependencyCheck argument_checker(FD, DM);
    }

    class FunctionReturnDependencyChecker
    {
      Function *function;
      DependencyMap *dependency_map;
      FunctionDependency *function_dependency;
      InstructionDependency *inst_dependency; // used only checking overlapping
      std::vector<BlockNode *> block_nodes;

    public:

      FunctionReturnDependencyChecker(FunctionDependency *FD, DependencyMap *DM)
        : function_dependency(FD), dependency_map(DM)
      {
        function = function_dependency->getFunction();
        recursion_map->addDependency(function, nullptr);

        for (BasicBlock& basic_block : *function)
          for (Instruction& inst : basic_block)
            if (ReturnInst *ri = dyn_cast<ReturnInst>(&inst)) {

              // 반환되는 내용은 반드시 ReturnInst를 거쳐야됩니다. 따라서 ReturnInst의
              // Operand에 영향을 미치는 것들을 차례로 조사합니다. 이 과정은 함수 내부에
              // 모든 ReturnInst를 조사합니다.
              inst_dependency = new InstructionDependency();
              runBottomUp(ri->getReturnValue());
              delete inst_dependency;
            }
      }

    private:
      
      /// [정보]
      /// 어떤 함수인자가 V에 영향을 미치는지 검사합니다. 이 과정은
      /// 재귀적으로 진행됩니다.
      void runBottomUp(Value *V, bool P = true)
      {
        if (Argument *arg = dyn_cast<Argument> (V)) {
          function_dependency->setReturnDependency(arg->getArgNo());
          return;
        }
        
        if (Instruction *inst = dyn_cast <Instruction> (V))
        {
          if (inst_dependency->hasInstructoin(inst, P))
            return;

#if IDC_PRINT_INSTRUCTION
          errs() << "    (" << function->getName() << ")" << *inst << "\n";
#endif

          inst_dependency->addInstruction(inst, P);

          // PHINode와 기타 Instruction은 Operand에 접근하는 방법이 다릅니다.
          // 따라서 두 가지 분리하여 검사하였습니다.
          // 다른 접근 방법을 가진 Instruction은 여기서 특수화 해야합니다.
          if (PHINode *phi = dyn_cast<PHINode> (inst)) {
            for (unsigned i = 0; i < phi->getNumIncomingValues(); i++) {
              Value *target_value = phi->getIncomingValue(i);
              runBottomUp(target_value, P);
              runSearch(target_value, P);
            }
          } else if (CallInst *ci = dyn_cast<CallInst> (inst)) {
            
            // 어떤 함수인자가 반환값에 영향을 미칩니까?
            FunctionDependency *depends;
            if (!(depends = processCallInst(ci))) return;

            // 반환값에 영향을 미치는 모든 함수인자들은 V에 영향을 미치게 됩니다.
            for (size_t i = 0; i < ci->getCalledFunction()->arg_size(); i++)
              if (depends->hasReturnDependency(i) == true) {
                runBottomUp(ci->getOperand(i), P);
                runSearch(ci->getOperand(i), P);
              }

          } else {

            for (unsigned i = 0; i < inst->getNumOperands(); i++) {
              Value *target_value = inst->getOperand(i);
              runBottomUp(target_value, P);
              runSearch(target_value, P);
            }
          }

          processBranches(V);
        }
      }
      
      /// [정보]
      /// CallInst에 의해 호출된 함수의 Dependency를 가져옵니다.
      ///
      /// [보충]
      /// - callinst를 만났을 경우 다음과 같은 두 가지 영향을 분석합니다.
      ///   1. 반환값에 영향을 미치는 함수인자들의 목록
      ///   2. 포인터 함수인자에 영향을 미치는 함수인자들의 목록
      /// - 이 함수와 동일한 이름을 갖는 함수는 모두 같은 기능을 가집니다.
      FunctionDependency *processCallInst(CallInst *CI)
      {
        FunctionDependency *depends = nullptr;
        Function *target_function = CI->getCalledFunction();

        if (dependency_map->hasDependency(target_function)) {
          depends = dependency_map->getDependency(target_function);
        } else {
          if (recursion_map->hasDependency(target_function))
            return nullptr;
          depends = new FunctionDependency(target_function);
          run(depends, dependency_map);
          dependency_map->addDependency(target_function, depends);
        }

        function_dependency->addFunctionDependency(depends);

        return depends;
      }

      /// [정보]
      /// V가 속한 블록에 영향을 미치는 블록을 찾습니다.
      void processBranches(Value *V)
      {
#if IDC_SCAN_CONTROL_FLOW
        if (Instruction *inst = dyn_cast<Instruction> (V))
        {
          BranchManager *bm = function_dependency->getBranchManager();
          BlockNode *this_node = bm->getNodeFromInstruction(inst);
          processBlock(this_node);
        }
#endif
      }
      
      void processBlock(BlockNode *BN)
      {
        bool is_perpect = BN->getFromNodes().size() == 1;
        for (BlockNode *bn : BN->getFromNodes())
        {
          for (BlockNode *x : block_nodes)
            if (x == bn) return;
          block_nodes.push_back(bn);
          if (bn->getBranchInst()->isConditional()) {
            runBottomUp(bn->getBranchInst()->getCondition(), is_perpect);
            runSearch(bn->getBranchInst()->getCondition(), is_perpect);
          }
          processBlock(bn);
        }
      }

      /// [정보]
      /// Node따라가기에서 찾지못하는 특정 변수의 Dependency를 분석하기 위해
      /// 몇 가지 조건을 검사합니다. 이 단계에선 [보충]경우에서의 Dependency를
      /// 예상할 뿐 확신을 할 수는 없습니다.
      /// 
      /// [보충]
      /// - 현재까지 다음과 같은 세 가지 경우에서만 변수를 변경될 수 있음을
      ///   확인했습니다.
      ///   1. StoreInst: StoreInst는 register에 값을 쓰는 역할을 담당합니다.
      ///      따라서 StoreInst의 Pointer가 찾으려는 변수일 경우를 확인합니다.
      ///   2. LoadInst: LoadInst의 Pointer가 찾으려는 변수일 경우, LoadInst
      ///      그 자체가 해당 변수를 담당할 수 있습니다.
      ///   3. CallInst: 찾으려는 변수가 포인터형태의 함수인자로 어떤 함수에 넘겨지는 
      ///      경우 해당 함수의 다른 함수인자들이 이 변수에 영향을 미칠 수 있습니다.
      void runSearch(Value *V, bool P = true)
      {
        for (BasicBlock& basic_block : *function)
          for (Instruction& inst : basic_block) {
            if (StoreInst *si = dyn_cast<StoreInst> (&inst))
            {
              if (si->getPointerOperand() == V)
                runBottomUp(si->getValueOperand());
            }
            else if (CallInst *ci = dyn_cast<CallInst> (&inst))
            {
              FunctionDependency *depends;
              if (!(depends = processCallInst(ci))) continue;
              for (size_t i = 0; i < depends->getFunction()->arg_size(); i++)
                if (depends->getFunctionArgumentDependency(i)->getArgument() == V)
                  for (size_t j = 0; j < depends->getFunction()->arg_size(); j++)
                    if (depends->getFunctionArgumentDependency(i)->hasArgumentDependency(j))
                      runBottomUp(depends->getFunctionArgumentDependency(j)->getArgument(), P);
            }
          }
        processBranches(V);
      }

    };

    class FunctionArgumentDependencyCheck
    {
      Function *function;
      DependencyMap *dependency_map;
      FunctionDependency *function_dependency;
      std::vector<Value *> overlap;
      std::vector<BlockNode *> block_nodes;

    public:

      FunctionArgumentDependencyCheck(FunctionDependency *FD, DependencyMap *DM)
        : function_dependency(FD), dependency_map(DM)
      {
        function = function_dependency->getFunction();
        recursion_map->addDependency(function, nullptr);

        for (Argument *arg = function->arg_begin(); arg != function->arg_end(); arg++)
          if (arg->getType()->isPointerTy())
            for (Argument *arg2 = function->arg_begin(); arg2 != function->arg_end(); arg2++)
              if (arg != arg2) {
                overlap.clear();
                runChecker(arg, arg2);
              }
      }

    private:

      FunctionDependency *processCallInst(CallInst *CI)
      {
        FunctionDependency *depends = nullptr;
        Function *target_function = CI->getCalledFunction();

        if (dependency_map->hasDependency(target_function)) {
          depends = dependency_map->getDependency(target_function);
        } else {
          if (recursion_map->hasDependency(target_function))
            return nullptr;
          depends = new FunctionDependency(target_function);
          run(depends, dependency_map);
          dependency_map->addDependency(target_function, depends);
        }

        function_dependency->addFunctionDependency(depends);

        return depends;
      }
      
      void processBlock(Argument *A, BlockNode *BN)
      {
        bool is_perpect = BN->getFromNodes().size() == 1;
        for (BlockNode *bn : BN->getFromNodes())
        {
          for (BlockNode *x : block_nodes)
            if (x == bn) return;
          block_nodes.push_back(bn);
          if (bn->getBranchInst()->isConditional()) {
            runChecker(A, bn->getBranchInst()->getCondition(), is_perpect);
          }
          processBlock(A, bn);
        }
      }

      /// [정보]
      /// 검사하려는 함수인자 A와 같은 V가 있는지 재귀적으로 검사합니다.
      /// 이 함수는 runBottomUp과 runSearch를 합한 형태를 가집니다.
      ///
      /// [보충]
      /// 
      void runChecker(Argument *A, Value *V, bool P = true)
      {
        if (Argument *arg = dyn_cast<Argument> (V)) {
          function_dependency->getFunctionArgumentDependency(
            A->getArgNo())->setArgumentDependency(arg->getArgNo());
          return;
        }
        
#if IDC_PRINT_INSTRUCTION
          errs() << "    (" << function->getName() << ")" << *V << "\n";
#endif

        // 이 함수는 무한재귀 성질을 가지므로 중복검사를 시행합니다.
        if (std::find(overlap.begin(), overlap.end(), V) != overlap.end())
          return;
        overlap.push_back(V);
        
        // runSearch 알고리즘
        for (BasicBlock& basic_block : *function)
          for (Instruction& inst : basic_block) {
            if (StoreInst *si = dyn_cast<StoreInst> (&inst))
            {
              if (si->getPointerOperand() == V)
                runChecker(A, si->getValueOperand(), P);
              else if (si->getValueOperand() == V)
                runChecker(A, si->getPointerOperand(), P);
            }
            else if (LoadInst *li = dyn_cast<LoadInst> (&inst))
            {
              if (si->getPointerOperand() == V)
                runChecker(A, li, P);
            }
            else if (CallInst *ci = dyn_cast<CallInst> (&inst))
            {
              FunctionDependency *depends;
              if (!(depends = processCallInst(ci))) continue;
              for (size_t i = 0; i < depends->getFunction()->arg_size(); i++)
                if (depends->getFunctionArgumentDependency(i)->getArgument() == V)
                  for (size_t j = 0; j < depends->getFunction()->arg_size(); j++)
                    if (depends->getFunctionArgumentDependency(i)->hasArgumentDependency(j))
                      runChecker(A, depends->getFunctionArgumentDependency(j)->getArgument(), P);
            }
          }
        
        // runBottomUp 알고리즘
        if (Instruction *inst = dyn_cast <Instruction> (V))
        {
#if IDC_SCAN_CONTROL_FLOW
          BranchManager *bm = function_dependency->getBranchManager();
          BlockNode *this_node = bm->getNodeFromInstruction(inst);
          processBlock(A, this_node);
#endif

          if (PHINode *phi = dyn_cast<PHINode> (inst)) {
            for (unsigned i = 0; i < phi->getNumIncomingValues(); i++) {
              Value *target_value = phi->getIncomingValue(i);
              runChecker(A, target_value, P);
            }
          } else if (CallInst *ci = dyn_cast<CallInst> (inst)) {
            FunctionDependency *depends;
            if (!(depends = processCallInst(ci))) return;
            for (size_t i = 0; i < ci->getCalledFunction()->arg_size(); i++)
              if (depends->hasReturnDependency(i) == true) {
                runChecker(A, ci->getOperand(i), P);
              }
          } else {
            for (unsigned i = 0; i < inst->getNumOperands(); i++) {
              Value *target_value = inst->getOperand(i);
              runChecker(A, target_value, P);
            }
          }
        }
      }

    };

  };
  
  /// This class must be called only once by each target-function.
  class BottomUpDependencyChecker
  {
    Function *function;
    DependencyMap *dependency_map;
    FunctionDependency *function_dependency;
    InstructionDependency *inst_dependency;
    std::vector<BlockNode *> block_nodes;

  public:

    BottomUpDependencyChecker(Function *F, SmallVector<Value *, 16> V,
      DependencyMap *DM, FunctionDependency *FD, InstructionDependencyMap *IDM)
      : function(F), dependency_map(DM), function_dependency(FD)
    {
      for (Value *value : V)
      {
        inst_dependency = new InstructionDependency();
        runSearch(value, true, true);
        IDM->addDependency(value, inst_dependency);
        inst_dependency = nullptr;
      }
    }

  private:

    void runBottomUp(Value *V, bool P = true)
    {
      if (Instruction *inst = dyn_cast <Instruction> (V))
      {
        if (inst_dependency->hasInstructoin(inst, P))
          return;
        
#if IDC_PRINT_INSTRUCTION
          errs() << "    (" << function->getName() << ")" << *inst << "\n";
#endif

        inst_dependency->addInstruction(inst, P);

        if (PHINode *phi = dyn_cast<PHINode> (inst)) {
          for (unsigned i = 0; i < phi->getNumIncomingValues(); i++) {
            Value *target_value = phi->getIncomingValue(i);
            runBottomUp(target_value, P);
            runSearch(target_value, P);
          }
        } else if (CallInst *ci = dyn_cast<CallInst> (inst)) {
          FunctionDependency *depends = processCallInst(ci);
          for (size_t i = 0; i < ci->getCalledFunction()->arg_size(); i++)
            if (depends->hasReturnDependency(i) == true) {
              runBottomUp(ci->getOperand(i), P);
              runSearch(ci->getOperand(i), P);
            }
        } else {
          for (unsigned i = 0; i < inst->getNumOperands(); i++) {
            Value *target_value = inst->getOperand(i);
            runBottomUp(target_value, P);
            runSearch(target_value, P);
          }
        }
        processBranches(V);
      }
    }

    FunctionDependency *processCallInst(CallInst *CI)
    {
      FunctionDependency *depends = nullptr;
      Function *target_function = CI->getCalledFunction();
      
      if (dependency_map->hasDependency(target_function)) {
        depends = dependency_map->getDependency(target_function);
      } else {
        depends = new FunctionDependency(target_function);
        DependencyChecker::run(depends, dependency_map);
        dependency_map->addDependency(target_function, depends);
      }

      function_dependency->addFunctionDependency(depends);

      return depends;
    }
    
    void processBranches(Value *V)
    {
#if IDC_SCAN_CONTROL_FLOW
      if (Instruction *inst = dyn_cast<Instruction> (V))
      {
        BranchManager *bm = function_dependency->getBranchManager();
        BlockNode *this_node = bm->getNodeFromInstruction(inst);
        processBlock(this_node);
      }
#endif
    }

    void processBlock(BlockNode *BN)
    {
      bool is_perpect = BN->getFromNodes().size() == 1;
      for (BlockNode *bn : BN->getFromNodes())
      {
        for (BlockNode *x : block_nodes)
          if (x == bn) return;
        block_nodes.push_back(bn);
        if (bn->getBranchInst()->isConditional()) {
          runBottomUp(bn->getBranchInst()->getCondition(), is_perpect);
          runSearch(bn->getBranchInst()->getCondition(), is_perpect);
        }
        processBlock(bn);
      }
    }

    void runSearch(Value *V, bool P = true, bool ROOT = false)
    {
      for (BasicBlock& basic_block : *function)
        for (Instruction& inst : basic_block) {
          if (StoreInst *si = dyn_cast<StoreInst> (&inst))
          {
            if (si->getPointerOperand() == V) {
              runBottomUp(si->getValueOperand(), P && ROOT);
              runSearch(si->getValueOperand(), P && ROOT);
            }
          }
          else if (CallInst *ci = dyn_cast<CallInst> (&inst))
          {
            FunctionDependency *depends = processCallInst(ci);
            for (size_t i = 0; i < depends->getFunction()->arg_size(); i++)
              if (depends->getFunctionArgumentDependency(i)->getArgument() == V)
                for (size_t j = 0; j < depends->getFunction()->arg_size(); j++)
                  if (depends->getFunctionArgumentDependency(i)->hasArgumentDependency(j)) {
                    runBottomUp(depends->getFunctionArgumentDependency(j)->getArgument(), P && ROOT);
                    runSearch(depends->getFunctionArgumentDependency(j)->getArgument(), P && ROOT);
                  }
          }
        }
      processBranches(V);
    }
    
  };

  class DependencyManager
  {
  public:
    using AnnotatedTuple = std::tuple<Value *, CallInst *>;
    using AnnotatedVector = SmallVector<AnnotatedTuple, 8>;

  private:
    DependencyMap *map;
    DependencyMap *annotated_map;
    Function *target_function;
    AnnotatedVector annotated_value;
    SmallVector<Value *, 16> annotated_target;

  public:

    DependencyManager(Function *TargetFunction, DependencyMap *Map, DependencyMap *AnnotatedMap)
      : target_function(TargetFunction), map(Map), annotated_map(AnnotatedMap)
    {
      calAnnotatedValue();
    }

    void run()
    {
      FunctionDependency *fd = new FunctionDependency(target_function);
      InstructionDependencyMap *idm = new InstructionDependencyMap();

      recursion_map = new DependencyMap();
      BottomUpDependencyChecker checker(target_function, annotated_target, map, fd, idm);
      delete recursion_map;
      
      fd->setInstructionDependencyMap(idm);
      annotated_map->addDependency(target_function, fd);
    }

    AnnotatedVector& getAnnotatedVariableList()
    {
      return annotated_value;
    }
    
    StringRef getAnnotatedMessage(CallInst *ci)
    {
      ConstantExpr *ce = cast<ConstantExpr>(ci->getArgOperand(1));
      GlobalVariable *gv = cast<GlobalVariable>(ce->getOperand(0));
      Constant *cs = gv->getInitializer();
      ConstantDataArray *cda = cast<ConstantDataArray>(cs);
      return cda->getAsCString();
    }

  private:

    bool isAnnotated(Value *v)
    {
      for (AnnotatedTuple at : annotated_value) {
        if (std::get<0>(at) == v)
          return true;
      }
      return false;
    }

    /// get all annotated-variable in target-function
    void calAnnotatedValue()
    {
      for (BasicBlock& basic_block : *target_function)
        for (Instruction& inst : basic_block)
          if (CallInst *ci = dyn_cast<CallInst> (&inst))
            if (ci->getCalledFunction()->getName() == llvm_annotate_variable) {
              annotated_value.push_back(AnnotatedTuple((
                cast<BitCastInst>(ci->getArgOperand(0)))->getOperand(0), ci));
              annotated_target.push_back((cast<BitCastInst>(ci->getArgOperand(0)))->getOperand(0));
            }
    }

  };

  ///---------------------------------------------------------
  ///
  ///            LLVM-IR Nodes Traversal
  ///
  ///---------------------------------------------------------
  
  ///---------------------------------------------------------
  ///
  ///            Dependency Printer
  ///
  ///---------------------------------------------------------

  class DependencyPrinter
  {
    Function *target_function;
    DependencyMap *annotated_map;
    std::string tab;

  public:

    DependencyPrinter(DependencyMap *AnnotatedMap)
      : annotated_map(AnnotatedMap)
    {
    }

    void setTargetFunction(Function *F)
    {
      target_function = F;
    }

    void printTargetFunctionName()
    {
      out() << "Function - " << target_function->getName() << "\n";
    }

    void printTargetFunctionAnnotatedVariable(DependencyManager *DM)
    {
      DependencyManager::AnnotatedVector vec = DM->getAnnotatedVariableList();
      increaseTab();
      if (vec.size() == 0)
      {
        out() << "Annotated Variable is not found.\n\n";
        decreaseTab();
        return;
      }
      out() << "Annotated Variable List :\n";
      increaseTab();
      for (DependencyManager::AnnotatedTuple& tu : vec)
      {
        StringRef message = DM->getAnnotatedMessage(std::get<1>(tu));
        out() << "- Annotated : " << std::get<0>(tu)->getName() << "(message: " << message << ")\n";
      }
      out() << "\n";
      decreaseTab();
      decreaseTab();
    }

    void printTargetFunctionDependencyInstruction()
    {
      FunctionDependency *dependency = annotated_map->getDependency(target_function);
      InstructionDependencyMap *inst_map = dependency->getInstrctionDependencyMap();
      
      increaseTab();
      for (auto element : *inst_map)
      {
        out() << "Annotated-Variable : " << element.first->getName() << "\n";
        increaseTab();
        InstructionDependency *inst_dependency = element.second;
        for (auto inst : *inst_dependency)
        {
          out() << (inst.second ? "(Perpect)" : "(Maybe)") << *inst.first << "\n";
        }
        out() << "\n";
        decreaseTab();
      }
      decreaseTab();
    }

  private:

    void increaseTab()
    {
      tab += "    ";
    }
    void decreaseTab()
    {
      tab.erase(0, 4);
    }

    raw_ostream& out()
    {
      return errs() << tab;
    }

  };

  ///---------------------------------------------------------
  ///
  ///       Interprocedural Dependency Checker Pass
  ///
  ///---------------------------------------------------------

  struct InterproceduralDependencyCheckPass : public FunctionPass 
  {
    static char ID;
    
    DependencyMap *dependency_map;
    DependencyMap *annotated_map;
    std::map<Function *, DependencyManager *> function_map;

    InterproceduralDependencyCheckPass()
      : FunctionPass(ID)
    {
      initializeInterproceduralDependencyCheckPass(*PassRegistry::getPassRegistry());
      dependency_map = new DependencyMap();
      annotated_map = new DependencyMap();
    }

    ~InterproceduralDependencyCheckPass()
    {
      delete dependency_map;
    }

    bool runOnFunction(Function &F) override
    {
      DependencyManager *dm = new DependencyManager(&F, dependency_map, annotated_map);
      dm->run();
      function_map[&F] = dm;
#if IDC_PRINT_RESULT
      print(&F);
#endif
      check(&F);
      return false;
    }

    void print(Function *F)
    {
      DependencyPrinter printer(annotated_map);
      printer.setTargetFunction(F);

      printer.printTargetFunctionName();
      printer.printTargetFunctionAnnotatedVariable(function_map[F]);
      printer.printTargetFunctionDependencyInstruction();
    }

    void check(Function *F)
    {
      FunctionDependency *dependency = annotated_map->getDependency(F);
      InstructionDependencyMap *inst_map = dependency->getInstrctionDependencyMap();
      for (auto& element : *inst_map)
      {
        InstructionDependency *inst_dependency = element.second;
        for (auto& inst : *inst_dependency)
        {
          ((Value *)(inst.first))->setDependency();
          if (inst.second)
            ((Value *)(inst.second))->setMaybeDependency();
        }
      }
    }

  };

}

char InterproceduralDependencyCheckPass::ID = 0;
static RegisterPass<InterproceduralDependencyCheckPass> X("dependency", "DependencyPass");

INITIALIZE_PASS_BEGIN(InterproceduralDependencyCheckPass, "dependency",
  "Dependency Check and Marking Pass", false, false)
INITIALIZE_PASS_END(InterproceduralDependencyCheckPass, "dependency",
    "Dependency Check and Marking Pass", false, false)

FunctionPass *llvm::createInterproceduralDependencyCheckPass() {
  return new InterproceduralDependencyCheckPass();
}