SymbolicExprGraph.h

/*
 * Developed by Qingkai Shi, Fan Gang
 * Copy Right by Prism Research Group, HKUST and State Key Lab for Novel
 * Software Tech., Nanjing University.
 */
 
#ifndef SYMBOLIC_EXPR_GRAPH_H
#define SYMBOLIC_EXPR_GRAPH_H
 
#include <llvm/IR/BasicBlock.h>
#include <llvm/IR/CallSite.h>
#include <llvm/IR/Constants.h>
#include <llvm/IR/Function.h>
#include <llvm/IR/InstIterator.h>
#include <llvm/IR/Instructions.h>
#include <llvm/IR/Value.h>
 
#include <llvm/Support/Casting.h>
#include <llvm/Support/FileSystem.h>
#include <llvm/Support/Format.h>
#include <llvm/Support/raw_ostream.h>
 
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
#include "Analysis/Alias/PathSensitiveAADriver/ProgramVal.h"
#include "IR/SEG/SEGValue.h"
#include "Transform/ValueComparator.h"
#include "Utils/ADT/MapIterators.h"
#include "Utils/ADT/kvec.h"
 
using namespace llvm;
 
class SEGCallSite;
class SEGCallSiteOutputNode;
class SEGCallSitePseudoInputNode;
class SEGCallSitePseudoOutputNode;
class SEGCallSiteArgumentSummaryNode;
class SEGCallSiteReturnSummaryNode;
 
class SEGOpcodeNode;
class SEGOperandNode;
class SEGRegionNode;
class SEGPhiNode;
class SEGLoadMemNode;
class SEGStoreMemNode;
 
class SEGReturnNode;
class SEGCommonReturnNode;
class SEGPseudoReturnNode;
 
class SEGArgumentNode;
class SEGCommonArgumentNode;
class SEGPseudoArgumentNode;
class SEGVarArgumentNode;
 
class SEGCastNode;
class SEGBinaryWithIntConstNode;
class SEGSimpleOpcodeNode;
 
class SEGSiteBase;
 
class SymbolicExprGraph;
class SymbolicExprGraphBuilder;
class OCValueFlowBuilder;
 
class SEGOptions {
public:
  static bool EnableValueToString;
  static bool EnableArithmeticFlow;
};
 
class SEGObject {
  friend class SEGSerializer;
  friend class SEGHash;
 
public:
  enum SEGObjectKind {
    // nodes
    SEGOBJK_NodeBegin,
    // operand nodes
    SEGOBJK_OperandBegin,
 
    SEGOBJK_ArgumentBegin,
    SEGOBJK_CommonArgument,
    SEGOBJK_VarArgument,
    SEGOBJK_PseudoArgument,
    SEGOBJK_ArgumentEnd,
 
    SEGOBJK_CallSiteOutputBegin,
    SEGOBJK_CallSiteCommonOutput,
    SEGOBJK_CallSitePseudoOutput,
    SEGOBJK_CallSiteOutputEnd,
 
    SEGOBJK_ReturnBegin,
    SEGOBJK_CommonReturn,
    SEGOBJK_PseudoReturn,
    SEGOBJK_ReturnEnd,
 
    SEGOBJK_LoadMem,
    SEGOBJK_StoreMem,
    SEGOBJK_Phi,
    SEGOBJK_Region,
    SEGOBJK_SimpleOperand,
    SEGOBJK_Undef,
    SEGOBJK_CallSitePseudoInput,
    SEGOBJK_CallSiteSummaryArgument,
    SEGOBJK_CallSiteSummaryReturn,
 
    SEGOBJK_OperandEnd,
 
    // opcode nodes
    SEGOBJK_OpcodeBegin,
    SEGOBJK_BinaryWithIntConst,
    SEGOBJK_Cast,
    SEGOBJK_SimpleOpcode,
    SEGOBJK_OpcodeEnd,
 
    SEGOBJK_NodeEnd,
 
    // use sites
    SEGOBJK_SiteBegin,
 
    SEGOBJK_CallSite,
    SEGOBJK_ReturnSite,
 
    SEGOBJK_SimpleSiteBegin,
    SEGOBJK_GEPSite,
    SEGOBJK_DereferenceSite,
    SEGOBJK_DivSite,
    SEGOBJK_CmpSite,
    SEGOBJK_AllocSite,
    SEGOBJK_SimpleSiteEnd,
 
    SEGOBJK_SiteEnd,
  };
 
private:
  const SEGObjectKind ObjKind;
 
  SymbolicExprGraph *ParentGraph;
 
  BasicBlock *ParentBasicBlock = nullptr;
 
  // Index of this SEGObject
  int64_t ObjIndex = -1;
 
  // Index of this SEG
  std::string SEGIndex;
 
protected:
public:
  SEGObject(SEGObjectKind OK, SymbolicExprGraph *SEG, BasicBlock *BB,
            bool fromDisk);
 
  virtual ~SEGObject() = 0;
 
  // getLLVMDbgValue and getLLVMDbgInstruction are used for printing human
  // readable info for SEGObjects This design is to eliminate the enumerating of
  // SEG object types to print the required corresponding info for SEGObjects We
  // try best to collect such info, For example, for callsite output nodes, if
  // we want to distinguish the output values, we can use getLLVMDbgValue to get
  // the value if we want to get the line number in the source code, we can use
  // getLLVMDbgInstruction This function returns the callsite instruction
  // containing the output node, which can be used to get the line number to
  // find the callsite
  //
  // getLLVMDbgValue and getLLVMDbgInstruction are virtual functions in
  // SEGObject. Thus, we can use them on each node in SEG, to print human
  // readable debug info and still eliminate enumerating SEG Object types
 
  // Try best to collect the llvm value corresponding to the SEGObject
  // For printing human readable Debug info relative to values
  // SEGOperandNode : the value of the node
  // SEGSite : the instruction
  // Default : null
  virtual Value *getLLVMDbgValue() const { return nullptr; }
 
  // Try best to collect the llvm instruction corresponding to the SEGObject
  // For printing human readable Debug info requiring instructions
  // In detail,
  // For callsite pseudo-output nodes, we return the callsite
  // For store mem node, we return the store site
  // Otherwise, we return the instruction for the value if value exists or
  // otherwise return null
  virtual Instruction *getLLVMDbgInstruction() const {
    Value *val = getLLVMDbgValue();
    if (val != nullptr) {
      return dyn_cast<Instruction>(val);
    }
 
    return nullptr;
  }
 
  SEGObjectKind getKind() const { return ObjKind; }
 
  std::string getSEGIndex() const { return SEGIndex; }
 
  void setObjIndex(int64_t index) { ObjIndex = index; }
 
  int64_t getObjIndex() const {
    assert(ObjIndex != -1 && "Index should not be -1");
    return ObjIndex;
  }
 
  const char *getKindName() const;
 
  void setParentBasicBlock(BasicBlock *BB) { this->ParentBasicBlock = BB; }
 
  BasicBlock *getParentBasicBlock() const { return ParentBasicBlock; }
 
  Function *getParentFunction() const { return ParentBasicBlock->getParent(); }
 
  const SymbolicExprGraph *getParentGraph() const { return ParentGraph; }
  SymbolicExprGraph *getParentGraph() { return ParentGraph; }
 
  friend raw_ostream &operator<<(llvm::raw_ostream &Out, const SEGObject &N);
};
 
struct seg_cmp {
  bool operator()(const SEGObject *A, const SEGObject *B) const {
    std::string indexSEGA = A ? A->getSEGIndex() : "";
    std::string indexSEGB = B ? B->getSEGIndex() : "";
    if (indexSEGA != indexSEGB || (indexSEGA.empty() && indexSEGB.empty())) {
      return indexSEGA < indexSEGB;
    } else {
      int64_t indexA = A ? A->getObjIndex() : -1;
      int64_t indexB = B ? B->getObjIndex() : -1;
      return indexA < indexB;
    }
  }
};
 
class SEGNodeBase : public SEGObject {
  friend class SEGSerializer;
  friend class SEGHash;
 
protected:
  SEGNodeBase(SEGObjectKind K, Type *Ty, SymbolicExprGraph *SEG, BasicBlock *BB,
              bool fromDisk);
 
  void setDescription(std::string &Desc) { Description = Desc; }
 
  friend class SymbolicExprGraph;
 
private:
  // This is useful for debugging
  std::string Description;
 
  std::vector<SEGNodeBase *> Children;
 
  std::map<const SEGNodeBase *, float, seg_cmp> Parents;
 
  std::vector<SEGSiteBase *> UseSites;
  std::set<SEGSiteBase *> UseSiteSet;
 
  Type *LLVMType = nullptr;
 
  SEGRegionNode *Region = nullptr;
 
public:
  virtual ~SEGNodeBase() {}
 
  Type *getLLVMType() const { return LLVMType; }
 
  SEGNodeBase *getChild(unsigned I) const {
    assert(Children.size() > I &&
           "Invalid child index when querying SEG edges");
    return Children[I];
  }
 
  float getConfidence(const SEGNodeBase *ParentNode) const {
    auto It = Parents.find(ParentNode);
    assert(It != Parents.end() &&
           "Invalid parent node when querying SEG edges");
    return It->second;
  }
 
  unsigned getNumChildren() const { return Children.size(); }
 
  unsigned getNumParents() const { return Parents.size(); }
 
  void addChild(SEGNodeBase *N, float Confidence = 1.0f) {
    Children.push_back(N);
    N->Parents.insert(std::make_pair(this, Confidence));
  }
 
  void eraseAllChildren() {
    for (auto *Child : Children) {
      Child->Parents.erase(this);
    }
    Children.clear();
  }
 
  void addUseSite(SEGSiteBase *U) {
    if (!UseSiteSet.count(U)) {
      UseSiteSet.insert(U);
      UseSites.push_back(U);
    }
  }
 
  virtual bool isTerminalNode() const { return Children.empty(); }
 
  SEGRegionNode *getRegion() const;
 
  bool containsParentNode(const SEGNodeBase *N) const {
    return Parents.count(N);
  }
 
  const std::string &getDescription() const { return Description; }
 
  virtual void dot(raw_fd_ostream &O) const = 0;
 
  friend raw_ostream &operator<<(llvm::raw_ostream &Out, const SEGNodeBase &N);
 
  /*==-------Iterators------==*/
  class ValueFlowIterator {
  private:
    const SEGNodeBase *Node;
    key_iterator<std::map<const SEGNodeBase *, float>::const_iterator> It;
 
  public:
    ValueFlowIterator(const SEGNodeBase *N, bool End) : Node(N) {
      if (End) {
        It = N->parent_end();
      } else {
        It = N->parent_begin();
        increment();
      }
    }
 
    ValueFlowIterator(const ValueFlowIterator &VFIt)
        : Node(VFIt.Node), It(VFIt.It) {}
 
    ValueFlowIterator &operator=(const ValueFlowIterator &VFIt) {
      if (this != &VFIt) {
        this->Node = VFIt.Node;
        this->It = VFIt.It;
      }
      return *this;
    }
 
    ValueFlowIterator operator++(int) {
      ValueFlowIterator Old(*this);
      ++(*this);
      return Old;
    }
 
    ValueFlowIterator &operator++() {
      It++;
      increment();
      return *this;
    }
 
    const SEGNodeBase *operator*() { return *It; }
 
    bool operator==(const ValueFlowIterator &VFIt) { return It == VFIt.It; }
 
    bool operator!=(const ValueFlowIterator &VFIt) { return It != VFIt.It; }
 
  private:
    void increment();
  };
 
  ValueFlowIterator vflow_begin() const { return {this, false}; }
 
  ValueFlowIterator vflow_end() const { return {this, true}; }
 
  key_iterator<std::map<const SEGNodeBase *, float>::const_iterator>
  parent_begin() const {
    return {Parents.begin()};
  }
 
  key_iterator<std::map<const SEGNodeBase *, float>::const_iterator>
  parent_end() const {
    return {Parents.end()};
  }
 
  iterator_range<std::map<const SEGNodeBase *, float>::const_iterator>
  parents() const {
    return {Parents.begin(), Parents.end()};
  }
 
  std::vector<SEGNodeBase *>::const_iterator child_begin() const {
    return Children.begin();
  }
 
  std::vector<SEGNodeBase *>::const_iterator child_end() const {
    return Children.end();
  }
 
  iterator_range<std::vector<SEGNodeBase *>::const_iterator> children() const {
    return {Children.begin(), Children.end()};
  }
 
  std::map<const SEGNodeBase *, float>::const_iterator
  parent_confidence_begin() const {
    return key_iterator<std::map<const SEGNodeBase *, float>::const_iterator>(
        Parents.begin());
  }
 
  std::map<const SEGNodeBase *, float>::const_iterator
  parent_confidence_end() const {
    return key_iterator<std::map<const SEGNodeBase *, float>::const_iterator>(
        Parents.end());
  }
 
  size_t child_size() const { return Children.size(); }
 
  size_t parent_size() const { return Parents.size(); }
 
  std::vector<SEGSiteBase *>::const_iterator use_site_begin() const {
    return UseSites.begin();
  }
 
  std::vector<SEGSiteBase *>::const_iterator use_site_end() const {
    return UseSites.end();
  }
 
  iterator_range<std::vector<SEGSiteBase *>::const_iterator> use_sites() {
    return {UseSites.begin(), UseSites.end()};
  };
 
  size_t use_site_size() const { return UseSites.size(); }
 
public:
  static bool classof(const SEGObject *N) {
    return N->getKind() >= SEGOBJK_NodeBegin && N->getKind() <= SEGOBJK_NodeEnd;
  }
};
 
class SEGOperandNode : public SEGNodeBase {
protected:
  Value *LLVMValue = nullptr;
 
  SEGValue *segValue = nullptr;
 
  SEGOperandNode(SEGObjectKind K, Type *Ty, SymbolicExprGraph *SEG,
                 BasicBlock *BB, bool fromDisk);
 
  SEGOperandNode(SEGObjectKind K, Value *Val, Type *Ty, SymbolicExprGraph *SEG,
                 BasicBlock *BB, bool fromDisk);
 
  friend class SymbolicExprGraph;
  friend class SEGHash;
 
public:
  virtual ~SEGOperandNode() = 0;
 
  Value *getLLVMValue() const { return LLVMValue; }
 
  SEGValue *getSEGValue() const { return segValue; }
 
  void dot(raw_fd_ostream &O) const override;
 
  friend raw_ostream &operator<<(llvm::raw_ostream &Out,
                                 const SEGOperandNode &N) {
    if (Value *Val = N.getLLVMValue()) {
      Out << *Val;
    } else {
      Out << N.getDescription();
    }
    return Out;
  }
 
  virtual Value *getLLVMDbgValue() const override { return getLLVMValue(); }
 
public:
  static bool classof(const SEGObject *N) {
    return N->getKind() >= SEGOBJK_OperandBegin &&
           N->getKind() <= SEGOBJK_OperandEnd;
  }
 
private:
  void initialize(Value *Val);
};
 
class SEGOpcodeNode : public SEGNodeBase {
 
public:
  enum CodeKind {
    CK_BinaryBegin,
    CK_URem = CK_BinaryBegin,
    CK_FRem,
    CK_SRem,
    CK_UDiv,
    CK_FDiv,
    CK_SDiv,
    CK_And,
    CK_Or,
    CK_Xor,
    CK_Add,
    CK_FAdd,
    CK_Sub,
    CK_FSub,
    CK_Mul,
    CK_FMul,
    CK_Shl,
    CK_LShr,
    CK_AShr,
    CK_BinaryEnd = CK_AShr,
 
    CK_CastBegin,
    CK_AddressCast = CK_CastBegin,
    CK_Int2Ptr,
    CK_Ptr2Int,
    CK_Bitcast,
    CK_Trunc,
    CK_FPTrunc,
    CK_SExt,
    CK_ZExt,
    CK_FPExt,
    CK_SI2FP,
    CK_FP2SI,
    CK_UI2FP,
    CK_FP2UI,
    CK_CastEnd = CK_FP2UI,
 
    CK_ExtractElmt,
    CK_InsertElmt,
 
    CK_Select,
 
    CK_GetElmtPtr,
 
    CK_Concat,
 
    CK_CmpBegin,
    // Predicates for comparing floating numbers
    //                           U L G E    Intuitive operation
    CK_FFalse = CK_CmpBegin, 
    CK_FOEq,                 
    CK_FOGT,                 
    CK_FOGE,  
    CK_FOLT,  
    CK_FOLE,  
    CK_FONE,  
    CK_FOrd,  
    CK_FUno,  
    CK_FUEq,  
    CK_FUGT,  
    CK_FUGE,  
    CK_FULT,  
    CK_FULE,  
    CK_FUNE,  
    CK_FTrue, 
 
    // Predicates for comparing integers
    CK_IEq,  
    CK_INE,  
    CK_IUGT, 
    CK_IUGE, 
    CK_IULT, 
    CK_IULE, 
    CK_ISGT, 
    CK_ISGE, 
    CK_ISLT, 
    CK_ISLE, 
    CK_CmpEnd = CK_ISLE,
 
    CK_InvalidCode,
  };
 
protected:
  CodeKind Opcode;
 
  SEGOpcodeNode(SEGObjectKind K, CodeKind Opcode, Type *Ty,
                SymbolicExprGraph *SEG, BasicBlock *BB, bool fromDisk);
 
  friend class SymbolicExprGraph;
 
public:
  virtual ~SEGOpcodeNode() = 0;
 
  CodeKind getOpcode() const { return Opcode; }
 
  virtual void dot(raw_fd_ostream &O) const;
 
  bool isCmpNode() const {
    return Opcode <= CK_CmpEnd && Opcode >= CK_CmpBegin;
  }
 
  bool isSignedCmp() const { return Opcode <= CK_ISLE && Opcode >= CK_ISGT; }
 
  bool isUnSignedCmp() const { return Opcode <= CK_IULE && Opcode >= CK_IUGT; }
 
  bool isFloatCmp() const { return Opcode <= CK_FTrue && Opcode >= CK_FFalse; }
 
  bool isAddNode() const { return Opcode == CK_Add; }
 
  bool isSubNode() const { return Opcode == CK_Sub; }
 
  bool isGEPNode() const { return Opcode == CK_GetElmtPtr; }
 
  bool isSelectNode() const { return Opcode == CK_Select; }
 
  bool isCastNode() const {
    return Opcode <= CK_CastEnd && Opcode >= CK_CastBegin;
  }
 
  bool isBinaryNode() const {
    return Opcode <= CK_BinaryEnd && Opcode >= CK_BinaryBegin;
  }
 
  bool isExtractElmtNode() const { return Opcode == CK_ExtractElmt; }
 
  bool isInsertElmtNode() const { return Opcode == CK_InsertElmt; }
 
  bool isConcatNode() const { return Opcode == CK_Concat; }
 
public:
  static bool classof(const SEGObject *N) {
    return N->getKind() >= SEGOBJK_OpcodeBegin &&
           N->getKind() <= SEGOBJK_OpcodeEnd;
  }
 
  static const char *getOpcodeName(CodeKind CK);
};
 
class SEGSiteBase : public SEGObject {
 
private:
  Instruction *User = nullptr;
 
  SEGValue *segValue = nullptr;
 
protected:
  SEGSiteBase(SEGObjectKind K, Instruction *User, SymbolicExprGraph *G,
              bool fromDisk);
  friend class SymbolicExprGraph;
 
public:
  virtual ~SEGSiteBase() = 0;
 
  CallSite getLLVMCallSite() const { return CallSite(User); }
 
  Instruction *getInstruction() const { return User; }
 
  SEGValue *getSEGValue() const { return segValue; }
 
  virtual Value *getLLVMDbgValue() const override { return getInstruction(); }
 
  friend raw_ostream &operator<<(llvm::raw_ostream &Out,
                                 const SEGSiteBase &US) {
    Out << *US.User;
    return Out;
  }
 
public:
  static bool classof(const SEGObject *O) {
    return O->getKind() >= SEGOBJK_SiteBegin && O->getKind() <= SEGOBJK_SiteEnd;
  }
};
 
namespace FalconPlus {
class AbstractCond;
class RegionCond;
class IntraFalcon;
class AbstractCondPtr;
class MemValueSet;
} // namespace FalconPlus
 
namespace SymbolicExecution {
class AnalysisState;
}; // namespace SymbolicExecution
 
class SymbolicExprGraph {
 
  friend class SEGRegionNode;
  friend class SymbolicExprGraphBuilder;
  friend class IntraFalcon;
  friend class PTGraph;
  friend class SEGObject;
  friend class OCValueFlowBuilder;
  friend class SEGSerializer;
 
  friend class FalconPlus::AbstractCond;
  friend class FalconPlus::RegionCond;
  friend class FalconPlus::IntraFalcon;
  friend class FalconPlus::AbstractCondPtr;
  friend class FalconPlus::MemValueSet;
 
  friend class SymbolicExecution::AnalysisState;
 
public:
  struct CDGCond {
    SEGNodeBase *CondNode;
    BasicBlock *BB;
    bool Cond;
 
  public:
    CDGCond(SEGNodeBase *CN, BasicBlock *B, bool C)
        : CondNode(CN), BB(B), Cond(C) {}
 
    bool operator<(const CDGCond &RHS) const {
      return (CondNode < RHS.CondNode) ||
             (CondNode == RHS.CondNode && BB < RHS.BB) ||
             (CondNode == RHS.CondNode && BB == RHS.BB && Cond < RHS.Cond);
    }
 
    bool operator==(const CDGCond &RHS) const {
      return CondNode == RHS.CondNode && BB == RHS.BB && Cond == RHS.Cond;
    }
 
    BasicBlock *getBB() const { return BB; }
  };
 
private:
  // The base function for this SEG
  Function *BaseFunc = nullptr;
 
  // All the nodes in seg
  std::vector<SEGObject *> NodesList;
 
  std::unordered_map<Value *, SEGOperandNode *> ValueNodesMap;
 
  std::vector<std::pair<Value *, SEGOperandNode *>> ValueNodePairs;
 
  std::set<SEGNodeBase *> NonValueNodes;
 
  std::map<std::pair<Instruction *, Value *>, SEGStoreMemNode *>
      StoreMemNodesMap;
 
  std::map<Instruction *, SEGSiteBase *> InstSiteMap;
  std::vector<SEGCallSite *> CallSites;
 
  std::map<BasicBlock *, std::set<CDGCond> *> BlockCondMap;
 
  std::string SEGIndex;
 
public:
  // For Swap
  std::string getSEGIndex() const {
    assert(!SEGIndex.empty() && "SEGIndex should not be empty");
    return SEGIndex;
  }
 
  template <class T> T *getSEGObject(int64_t index) {
    assert(index == -1 || (index >= 0 && index < NodesList.size()));
    if (index == -1)
      return nullptr;
    auto *Obj = NodesList[index];
    assert(isa<T>(Obj));
    return (T *)Obj;
  }
 
private:
  /*==--------------------Structures for Inter-procedural
   * Analysis--------------------==*/
  SEGCommonReturnNode *CommonReturn = nullptr;
  kvec<SEGPseudoReturnNode *> PseudoReturns;
 
  kvec<SEGCommonArgumentNode *> CommonArgumentNodes;
  kvec<SEGPseudoArgumentNode *> PseudoArgumentNodes;
  kvec<SEGVarArgumentNode *> VarArgumentNodes;
 
  // Summary Nodes
  // SEGNodeBase : the node
  // int : the corresponding ap-depth (0 means ap-depth larger than considered)
  //
  // For each ap-depth, there is only one return summary node with a load mem
  // node as child,
  //     which collects all values with conditions and confidence score, that
  //     may escape to caller with the corresponding ap-depth
  // For each ap-depth, there can be multiple arg-summary node,
  //     each has a parent to the argument node that is not inlined
  // Each summary node has type PTGraph::DEFAULT_NON_POINTER_TYPE
  //     which is currently int64 type
  std::unordered_map<SEGNodeBase *, int> SummaryArgNodes;
  std::unordered_map<int, std::unordered_set<SEGNodeBase *>>
      SummaryArgNodesCache;
  std::unordered_map<SEGNodeBase *, int> SummaryReturnNodes;
  std::unordered_map<int, std::unordered_set<SEGNodeBase *>>
      SummaryReturnNodesCache;
 
  std::map<std::string, SEGOperandNode *> NameToPseudoArgNode;
  std::unordered_map<std::string, SEGOperandNode *> NameToNonArgPseudoNode;
  std::unordered_map<std::string, std::unique_ptr<PseudoVal>> PseudoValStorage;
 
  void addCommonArgumentNodes(SEGCommonArgumentNode *Node);
 
  void addPseudoArgumentNodes(SEGPseudoArgumentNode *Node);
 
  void addVarArgumentNodes(SEGVarArgumentNode *Node);
 
  void setCommonReturnNode(SEGCommonReturnNode *Node);
 
  void addPseudoReturnNode(SEGPseudoReturnNode *Node);
 
  void addSummaryArgNode(SEGNodeBase *Node, int APDepth);
 
  void addSummaryReturnNode(SEGNodeBase *Node, int APDepth);
 
public:
  size_t getNumCommonArgument() const { return CommonArgumentNodes.size(); }
 
  size_t getNumPseudoArgument() const { return PseudoArgumentNodes.size(); }
 
  size_t getNumVarArgument() const { return VarArgumentNodes.size(); }
 
  size_t getNumPseudoReturn() const { return PseudoReturns.size(); }
 
  bool hasCommonReturnNode() const {
    if (CommonReturn)
      return true;
    else
      return false;
  }
 
  const SEGCommonReturnNode *getCommonReturn() const { return CommonReturn; }
 
  const SEGPseudoReturnNode *getPseudoReturn(size_t Index) const {
    return PseudoReturns[Index];
  }
 
  const SEGCommonArgumentNode *getCommonArgument(size_t Index) const {
    return CommonArgumentNodes[Index];
  }
 
  const SEGPseudoArgumentNode *getPseudoArgument(size_t Index) const {
    return PseudoArgumentNodes[Index];
  }
 
  const SEGVarArgumentNode *getVarArgument(size_t Index) const {
    return VarArgumentNodes[Index];
  }
 
  bool isSummaryArgument(const SEGNodeBase *Node) const;
 
  // Return the ap-depth of an SEGNodeBase as summary argument.
  // If the node is not a summary argument, return -1.
  int getSummaryArgumentAPDepth(const SEGNodeBase *Node) const;
 
  // Get the set of summary argument nodes given APDepth
  // Return null if not exist
  std::unordered_set<SEGNodeBase *> *getSummaryArgument(int APDepth) const;
 
  bool isSummaryReturn(const SEGNodeBase *Node) const;
 
  // Return the ap-depth of an SEGNodeBase as summary return node.
  // If the node is not a summary return node, return -1.
  int getSummaryReturnAPDepth(const SEGNodeBase *Node) const;
 
  // Get the set of summary return nodes given APDepth
  // Return null if not exist
  std::unordered_set<SEGNodeBase *> *getSummaryReturn(int APDepth) const;
 
  // Return if the value represented by the Node is directly passed to/from
  // caller A node is directly passed to/from caller if either it is a common or
  // pseudo return/argument node or a summary return/argument node. A node is
  // indirectly passed to/from caller if one of it's ancestor/descendant is
  // directly passed to/from caller
  bool isDirectlyPassedToCaller(const SEGNodeBase *Node) const;
  bool isDirectlyPassedFromCaller(const SEGNodeBase *Node) const;
 
private:
  // Cache of region nodes to avoid multiple creation of same regions
  // Positive regions: Value of SEGNodeBase is true
  // Negative regions: Value of SEGNodeBase is false
  // compond_regions_cache_and: SEGRegionNode(3) is SEGRegionNode(1) and
  // SEGRegionNode(2) compond_regions_cache_or: SEGRegionNode(3) is
  // SEGRegionNode(1) or SEGRegionNode(2) Note, for compound regions, we assume
  // (pointer) value SEGRegionNode*(1) < SEGRegionNode*(2)
  std::unordered_map<SEGNodeBase *, SEGRegionNode *> positive_regions_cache;
  std::unordered_map<SEGNodeBase *, SEGRegionNode *> negative_regions_cache;
  std::unordered_map<SEGRegionNode *,
                     std::unordered_map<SEGRegionNode *, SEGRegionNode *>>
      compound_regions_cache_and;
  std::unordered_map<SEGRegionNode *,
                     std::unordered_map<SEGRegionNode *, SEGRegionNode *>>
      compound_regions_cache_or;
 
  // cache the corresponding region nodes for basic blocks
  std::unordered_map<BasicBlock *, SEGRegionNode *> bb_region_cache;
 
public:
  void clearRegionNodeCache();
 
private:
  // All the functions that may change the SEG (i.e. have side-effects on the
  // SEG) are private) Meaning that the SEG cannot be changed once created. Only
  // friend class of SEG can modify the SEG, which is used to protect the SEG
  // from modified by checkers
 
  SEGOperandNode *findOrCreateNode(Value *Val, Type *Ty, BasicBlock *BB);
 
  template <class OperandNodeTy>
  OperandNodeTy *findOrCreateOperandNode(Value *Val, Type *Ty, BasicBlock *BB,
                                         bool fromDisk = false) {
    assert(Ty && BB);
    assert(Val && !Val->getType()->isVoidTy());
    assert((!(dyn_cast<Instruction>(Val)) ||
            BB == ((Instruction *)Val)->getParent()) &&
           "Incorrect BasicBlock detected");
 
    auto It = ValueNodesMap.find(Val);
    if (It != ValueNodesMap.end()) {
      assert(isa<OperandNodeTy>(It->second));
      return (OperandNodeTy *)It->second;
    } else {
      auto *N = new OperandNodeTy(Val, Ty, this, BB, fromDisk);
      ValueNodePairs.push_back({Val, N});
      ValueNodesMap[Val] = N;
      return N;
    }
  }
 
 
  template <class OperandNodeTy>
  OperandNodeTy *
  clonePseudoVal(const PseudoVal *Arg,
                 std::function<OperandNodeTy *(const PseudoVal *)> Proc) {
    const std::string &ArgName = Arg->getName();
    auto ClonedArg = std::unique_ptr<PseudoVal>(Arg->clone());
    auto *ArgNode = Proc(ClonedArg.get());
 
    if (std::is_same<OperandNodeTy, SEGPseudoArgumentNode>::value) {
      NameToPseudoArgNode.insert(std::make_pair(ArgName, ArgNode));
    } else {
      NameToNonArgPseudoNode.insert(std::make_pair(ArgName, ArgNode));
    }
 
    assert(!PseudoValStorage.count(ArgName));
    PseudoValStorage.insert({ArgName, std::move(ClonedArg)});
    return ArgNode;
  }
 
  template <class OperandNodeTy>
  OperandNodeTy *
  findOrClonePseudoVal(const PseudoVal *Arg,
                       std::function<OperandNodeTy *(const PseudoVal *)> Proc) {
    const std::string &ArgName = Arg->getName();
    if (std::is_same<OperandNodeTy, SEGPseudoArgumentNode>::value) {
      if (NameToPseudoArgNode.count(ArgName)) {
        return cast<OperandNodeTy>(NameToPseudoArgNode.at(ArgName));
      }
    } else {
      if (NameToNonArgPseudoNode.count(ArgName)) {
        static_assert(
            std::is_base_of<SEGOperandNode, OperandNodeTy>::value,
            "OperandNodeTy must be a derived class of SEGOperandNode.");
        return cast<OperandNodeTy>(NameToNonArgPseudoNode.at(ArgName));
      }
    }
 
    return clonePseudoVal<OperandNodeTy>(Arg, Proc);
  }
 
  SEGPseudoArgumentNode *findOrCreatePseudoArgumentNode(const PseudoVal *Arg,
                                                        BasicBlock *BB);
  // Call this after all pseudo args have been created.
  void finalizePseudoArgumentNodes();
  SEGOperandNode *findOrCreateSimpleOperandFromPseudoVal(const PseudoVal *Arg,
                                                         BasicBlock *BB);
  SEGPseudoReturnNode *createPseudoReturnNode(const PseudoVal *Arg,
                                              BasicBlock *BB);
  SEGCallSitePseudoInputNode *createPseudoInputNode(const PseudoVal *Arg,
                                                    BasicBlock *BB, CallSite CS,
                                                    Function *Callee);
  SEGCallSitePseudoOutputNode *createPseudoOutputNode(const PseudoVal *Arg,
                                                      BasicBlock *BB,
                                                      CallInst *Call,
                                                      Function *Callee);
 
  template <class OperandNodeTy>
  OperandNodeTy *CreateUniqueOperandNode(Value *Val, Type *Ty, BasicBlock *BB,
                                         bool fromDisk = false) {
    assert(Ty && BB);
    assert(Val && !Val->getType()->isVoidTy());
    assert((!(dyn_cast<Instruction>(Val)) ||
            BB == ((Instruction *)Val)->getParent()) &&
           "Incorrect BasicBlock detected");
 
    auto *N = new OperandNodeTy(Val, Ty, this, BB, fromDisk);
    ValueNodesMap[Val] = N;
    ValueNodePairs.push_back({Val, N});
    return N;
  }
 
  template <class OperandNodeTy>
  OperandNodeTy *createOperandNode(Type *Ty, BasicBlock *BB,
                                   bool fromDisk = false) {
    assert(Ty);
    assert(BB);
    auto *Ret = new OperandNodeTy(Ty, this, BB, fromDisk);
    NonValueNodes.insert(Ret);
    return Ret;
  }
 
  template <class SiteTy>
  SiteTy *findOrCreateSite(Instruction *I, bool fromDisk = false) {
    assert(I);
 
    auto It = InstSiteMap.find(I);
    if (It != InstSiteMap.end()) {
      assert(isa<SiteTy>(It->second));
      return (SiteTy *)It->second;
    } else {
      SiteTy *N = new SiteTy(I, this, fromDisk);
      InstSiteMap[I] = N;
 
      if (SEGCallSite *CS = dyn_cast<SEGCallSite>(N)) {
        CallSites.push_back(CS);
      }
 
      return N;
    }
  }
 
  // Create callSite argument summary node as operandNode(Type* Ty,
  // SymbolicExprGraph* SEG, BasicBlock* BB) for call site Callsite with
  // ap-depth APDepth
  SEGCallSiteArgumentSummaryNode *
  createCallSiteArgumentSummaryNode(Type *Ty, BasicBlock *BB,
                                    Instruction *Callsite, int APDepth,
                                    bool fromDisk = false);
 
  // Create callSite return summary node as operandNode(Type* Ty,
  // SymbolicExprGraph* SEG, BasicBlock* BB) for call site Callsite, with value
  // confidence Confidence
  SEGCallSiteReturnSummaryNode *
  createCallSiteReturnSummaryNode(Type *Ty, BasicBlock *BB,
                                  Instruction *Callsite, float Confidence,
                                  bool fromDisk = false);
 
  // find or create a call site output node
  SEGCallSiteOutputNode *
  findOrCreateCallSiteOutputNode(Value *Val, Type *Ty, BasicBlock *BB,
                                 CallSite CS, Function *Callee, bool IsCommon);
 
  SEGCallSiteOutputNode *createCallSiteOutputNode(Value *Val, Type *Ty,
                                                  BasicBlock *BB, CallSite CS,
                                                  Function *Callee,
                                                  bool IsCommon,
                                                  bool fromDisk = false);
 
  // find or create a call site pseudo input node
  SEGCallSitePseudoInputNode *
  findOrCreateCallSitePseudoInputNode(Value *Val, Type *Ty, BasicBlock *BB,
                                      CallSite CS, Function *Callee,
                                      bool fromDisk = false);
 
  SEGStoreMemNode *findOrCreateStoreMemNode(Type *Ty, Instruction *StoreSite,
                                            Value *StoreVal, BasicBlock *BB,
                                            bool fromDisk = false);
 
  // Create a region node
  SEGRegionNode *createRegionNode(SEGNodeBase *cond_node = nullptr,
                                  bool cond = false, bool fromDisk = false);
 
  // Find or create a Region node from a region unit (with boolean value
  // cond_node == cond)
  SEGRegionNode *findOrCreateUnitRegion(SEGNodeBase *cond_node, bool cond);
 
  // Find or create a Region node "region1 and region2"
  SEGRegionNode *findOrCreateAndRegion(SEGRegionNode *region1,
                                       SEGRegionNode *region2);
 
  // Find or create a Region node "region1 or region2"
  SEGRegionNode *findOrCreateOrRegion(SEGRegionNode *region1,
                                      SEGRegionNode *region2);
 
  // Find or create a Region node "not region1"
  SEGRegionNode *findOrCreateNotRegion(SEGRegionNode *region1);
 
  // Find or create a node representing a constant bool value : Constant True or
  // Constant False
  SEGOperandNode *findOrCreateConstantBoolNode(bool bool_val);
 
  SEGSimpleOpcodeNode *createExpr(SEGOpcodeNode::CodeKind Opcode, Type *Ty,
                                  BasicBlock *BB, SEGNodeBase *FirstOperand,
                                  ...);
 
  SEGSimpleOpcodeNode *createExpr(SEGOpcodeNode::CodeKind Opcode, Type *Ty,
                                  BasicBlock *BB, const kvec<SEGNodeBase *> &,
                                  bool fromDisk = false);
 
  SEGCastNode *createCastExpr(SEGOpcodeNode::CodeKind Opcode, Type *Ty,
                              BasicBlock *BB, SEGNodeBase *Op, uint64_t OSz,
                              uint64_t TSz, bool fromDisk = false);
 
  SEGBinaryWithIntConstNode *
  createBinaryWithIntConstExpr(SEGOpcodeNode::CodeKind Opcode, Type *Ty,
                               BasicBlock *BB, SEGNodeBase *Op, uint64_t TSz,
                               bool fromDisk = false);
 
  void addBlockCond(BasicBlock *CurrBB, SEGNodeBase *BrNode, BasicBlock *DepBB,
                    bool Label);
 
public:
  SymbolicExprGraph(Function *);
  ~SymbolicExprGraph();
 
  Function *getBaseFunc() const { return BaseFunc; }
 
  Module *getBaseModule() const { return BaseFunc->getParent(); }
 
  template <class SiteTy> SiteTy *findSite(Instruction *I) const {
    assert(I);
 
    auto It = InstSiteMap.find(I);
    if (It != InstSiteMap.end()) {
      // assert(isa<SiteTy>(It->second));
      return dyn_cast<SiteTy>(It->second);
    } else {
      return nullptr;
    }
  }
 
  template <class SiteTy> SiteTy *findSite(SEGValue *sValue) const {
    Instruction *I = dyn_cast<Instruction>(sValue->getValue());
    assert(I);
 
    auto It = InstSiteMap.find(I);
    if (It != InstSiteMap.end()) {
      // assert(isa<SiteTy>(It->second));
      return dyn_cast<SiteTy>(It->second);
    } else {
      return nullptr;
    }
  }
 
  SEGOperandNode *findNode(Value *) const;
 
  SEGOperandNode *findNode(SEGValue *) const;
 
  // Find the Region node from a region unit (with boolean value cond_node ==
  // cond)
  SEGRegionNode *findUnitRegion(SEGNodeBase *cond_node, bool cond) const;
 
  // Find the Region node "region1 and region2"
  SEGRegionNode *findAndRegion(SEGRegionNode *region1,
                               SEGRegionNode *region2) const;
 
  // Find the Region node "region1 or region2"
  SEGRegionNode *findOrRegion(SEGRegionNode *region1,
                              SEGRegionNode *region2) const;
 
  // Find the Region node "not region1"
  SEGRegionNode *findNotRegion(SEGRegionNode *region1) const;
 
  const std::set<CDGCond> *getBlockCond(BasicBlock *BB) const {
    auto It = BlockCondMap.find(BB);
    if (It != BlockCondMap.end()) {
      return It->second;
    }
    return nullptr;
  }
 
  void dot(const char *FileName) const;
 
  void dot(std::vector<const SEGNodeBase *> Srcs, const char *FileName) const;
 
  void validate();
 
  // Return the region node for the corresponding basicblock, if not computed,
  // we compute and generate a new region
  SEGRegionNode *findOrCreateRegionForBB(BasicBlock *BB);
 
  // Find the region for BB. If the region is not computed, we return null
  SEGRegionNode *findRegionForBB(BasicBlock *BB) const;
 
  /*==------------------------Iterators--------------------==*/
 
  std::unordered_map<Value *, SEGOperandNode *>::const_iterator
  value_node_begin() const {
    return ValueNodesMap.begin();
  }
 
  std::unordered_map<Value *, SEGOperandNode *>::const_iterator
  value_node_end() const {
    return ValueNodesMap.end();
  }
 
  std::vector<std::pair<Value *, SEGOperandNode *>>::const_iterator
  value_node_pair_begin() const {
    return ValueNodePairs.begin();
  }
 
  std::vector<std::pair<Value *, SEGOperandNode *>>::const_iterator
  value_node_pair_end() const {
    return ValueNodePairs.end();
  }
 
  std::set<SEGNodeBase *>::const_iterator non_value_node_begin() const {
    return NonValueNodes.begin();
  }
 
  std::set<SEGNodeBase *>::const_iterator non_value_node_end() const {
    return NonValueNodes.end();
  }
 
  std::map<Instruction *, SEGSiteBase *>::const_iterator
  inst_site_begin() const {
    return InstSiteMap.begin();
  }
 
  std::map<Instruction *, SEGSiteBase *>::const_iterator inst_site_end() const {
    return InstSiteMap.end();
  }
 
  std::map<std::pair<Instruction *, Value *>, SEGStoreMemNode *>::const_iterator
  store_mem_node_begin() const {
    return StoreMemNodesMap.begin();
  }
 
  std::map<std::pair<Instruction *, Value *>, SEGStoreMemNode *>::const_iterator
  store_mem_node_end() const {
    return StoreMemNodesMap.end();
  }
 
  std::map<Instruction *, SEGSiteBase *>::const_iterator site_begin() const {
    return InstSiteMap.begin();
  }
 
  std::map<Instruction *, SEGSiteBase *>::const_iterator site_end() const {
    return InstSiteMap.end();
  }
 
  std::vector<SEGObject *>::const_iterator node_begin() const {
    return NodesList.begin();
  }
 
  std::vector<SEGObject *>::const_iterator node_end() const {
    return NodesList.end();
  }
 
  class ReturnIterator {
  private:
    size_t I;
    SEGCommonReturnNode *CommonRet;
    const kvec<SEGPseudoReturnNode *> &PseudoRets;
 
  public:
    ReturnIterator(size_t Id, SEGCommonReturnNode *CR,
                   const kvec<SEGPseudoReturnNode *> &PRs)
        : I(Id), CommonRet(CR), PseudoRets(PRs) {}
 
    ReturnIterator(const ReturnIterator &It)
        : I(It.I), CommonRet(It.CommonRet), PseudoRets(It.PseudoRets) {}
 
    ReturnIterator &operator++() {
      I++;
      return *this;
    }
 
    ReturnIterator operator++(int) {
      ReturnIterator Old(*this);
      ++(*this);
      return Old;
    }
 
    const SEGReturnNode *operator*() {
      if (CommonRet) {
        if (I == 0) {
          return (const SEGReturnNode *)CommonRet;
        } else {
          return (const SEGReturnNode *)PseudoRets[I - 1];
        }
      } else {
        return (const SEGReturnNode *)PseudoRets[I];
      }
    }
 
    bool operator==(const ReturnIterator &It) { return I == It.I; }
 
    bool operator!=(const ReturnIterator &It) { return I != It.I; }
  };
 
  ReturnIterator return_begin() const {
    return ReturnIterator(0, CommonReturn, PseudoReturns);
  }
 
  ReturnIterator return_end() const {
    return ReturnIterator(getNumPseudoReturn() + (getCommonReturn() ? 1 : 0),
                          CommonReturn, PseudoReturns);
  }
 
  ReturnIterator pseudo_return_begin() const {
    size_t StartIndex = getCommonReturn() ? 1 : 0;
    return ReturnIterator(StartIndex, CommonReturn, PseudoReturns);
  }
 
  ReturnIterator pseudo_return_end() const { return return_end(); }
 
  class ArgumentIterator {
  private:
    size_t I;
    const kvec<SEGCommonArgumentNode *> &CommonArgs;
    const kvec<SEGPseudoArgumentNode *> &PseudoArgs;
    const kvec<SEGVarArgumentNode *> &VarArgs;
 
  public:
    ArgumentIterator(size_t Id, const kvec<SEGCommonArgumentNode *> &CA,
                     const kvec<SEGPseudoArgumentNode *> &PA,
                     const kvec<SEGVarArgumentNode *> &VA)
        : I(Id), CommonArgs(CA), PseudoArgs(PA), VarArgs(VA) {}
 
    ArgumentIterator(const ArgumentIterator &It)
        : I(It.I), CommonArgs(It.CommonArgs), PseudoArgs(It.PseudoArgs),
          VarArgs(It.VarArgs) {}
 
    ArgumentIterator &operator++() {
      I++;
      return *this;
    }
 
    ArgumentIterator operator++(int) {
      ArgumentIterator Old(*this);
      ++(*this);
      return Old;
    }
 
    const SEGArgumentNode *operator*() {
      if (I < (size_t)CommonArgs.size()) {
        return (const SEGArgumentNode *)CommonArgs[I];
      }
 
      if (I < (size_t)(CommonArgs.size() + PseudoArgs.size())) {
        return (const SEGArgumentNode *)PseudoArgs[I - CommonArgs.size()];
      }
 
      assert(I <
             (size_t)(CommonArgs.size() + PseudoArgs.size() + VarArgs.size()));
      return (const SEGArgumentNode *)
          VarArgs[I - (CommonArgs.size() + PseudoArgs.size())];
    }
 
    bool operator==(const ArgumentIterator &It) { return I == It.I; }
 
    bool operator!=(const ArgumentIterator &It) { return I != It.I; }
  };
 
  ArgumentIterator arg_begin() const {
    return ArgumentIterator(0, CommonArgumentNodes, PseudoArgumentNodes,
                            VarArgumentNodes);
  }
 
  ArgumentIterator arg_end() const {
    size_t NumArgs =
        getNumCommonArgument() + getNumPseudoArgument() + getNumVarArgument();
    return ArgumentIterator(NumArgs, CommonArgumentNodes, PseudoArgumentNodes,
                            VarArgumentNodes);
  }
 
  ArgumentIterator common_arg_begin() const { return arg_begin(); }
 
  ArgumentIterator common_arg_end() const {
    size_t NumArgs = getNumCommonArgument();
    return ArgumentIterator(NumArgs, CommonArgumentNodes, PseudoArgumentNodes,
                            VarArgumentNodes);
  }
 
  ArgumentIterator pseudo_arg_begin() const { return common_arg_end(); }
 
  ArgumentIterator pseudo_arg_end() const {
    size_t EndId = getNumCommonArgument() + getNumPseudoArgument();
    return ArgumentIterator(EndId, CommonArgumentNodes, PseudoArgumentNodes,
                            VarArgumentNodes);
  }
 
  ArgumentIterator var_arg_begin() const { return pseudo_arg_end(); }
 
  ArgumentIterator var_arg_end() const { return arg_end(); }
 
  typedef std::vector<SEGCallSite *>::const_iterator SEGCallSiteIterator;
  SEGCallSiteIterator seg_callsite_begin() const { return CallSites.begin(); }
 
  SEGCallSiteIterator seg_callsite_end() const { return CallSites.end(); }
};
 
#endif