path: root/include/clang/Analysis/PathSensitive/GRExprEngine.h

//===-- GRExprEngine.h - Path-Sensitive Expression-Level Dataflow ---*- C++ -*-=
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
//  This file defines a meta-engine for path-sensitive dataflow analysis that
//  is built on GREngine, but provides the boilerplate to execute transfer
//  functions and build the ExplodedGraph at the expression level.
//
//===----------------------------------------------------------------------===//

#include "ValueState.h"

#include "clang/Analysis/PathSensitive/GRCoreEngine.h"
#include "clang/Analysis/PathSensitive/GRTransferFuncs.h"

namespace clang {
  
class GRExprEngine {
  
public:
  typedef ValueStateManager::StateTy  StateTy;
  typedef ExplodedGraph<GRExprEngine> GraphTy;
  typedef GraphTy::NodeTy             NodeTy;
  
  // Builders.
  typedef GRStmtNodeBuilder<GRExprEngine>          StmtNodeBuilder;
  typedef GRBranchNodeBuilder<GRExprEngine>        BranchNodeBuilder;
  typedef GRIndirectGotoNodeBuilder<GRExprEngine>  IndirectGotoNodeBuilder;
  typedef GRSwitchNodeBuilder<GRExprEngine>        SwitchNodeBuilder;
  
  class NodeSet {
    typedef llvm::SmallVector<NodeTy*,3> ImplTy;
    ImplTy Impl;
    
  public:

    NodeSet(NodeTy* N) { assert (N && !N->isSink()); Impl.push_back(N); }
    NodeSet() {}
    
    inline void Add(NodeTy* N) { if (N && !N->isSink()) Impl.push_back(N); }
    
    typedef ImplTy::iterator       iterator;
    typedef ImplTy::const_iterator const_iterator;
    
    inline unsigned size() const { return Impl.size();  }
    inline bool empty()    const { return Impl.empty(); }
    
    inline iterator begin() { return Impl.begin(); }
    inline iterator end()   { return Impl.end();   }
    
    inline const_iterator begin() const { return Impl.begin(); }
    inline const_iterator end()   const { return Impl.end();   }
  };
  
protected:
  /// G - the simulation graph.
  GraphTy& G;
  
  /// Liveness - live-variables information the ValueDecl* and block-level
  ///  Expr* in the CFG.  Used to prune out dead state.
  LiveVariables Liveness;
  
  /// Builder - The current GRStmtNodeBuilder which is used when building the
  ///  nodes for a given statement.
  StmtNodeBuilder* Builder;
  
  /// StateMgr - Object that manages the data for all created states.
  ValueStateManager StateMgr;
  
  /// ValueMgr - Object that manages the data for all created RVals.
  ValueManager& ValMgr;
  
  /// TF - Object that represents a bundle of transfer functions
  ///  for manipulating and creating RVals.
  GRTransferFuncs* TF;
  
  /// SymMgr - Object that manages the symbol information.
  SymbolManager& SymMgr;
  
  /// StmtEntryNode - The immediate predecessor node.
  NodeTy* StmtEntryNode;
  
  /// CurrentStmt - The current block-level statement.
  Stmt* CurrentStmt;

  typedef llvm::SmallPtrSet<NodeTy*,2> UninitBranchesTy;  
  typedef llvm::SmallPtrSet<NodeTy*,2> UninitStoresTy;
  typedef llvm::SmallPtrSet<NodeTy*,2> BadDerefTy;
  typedef llvm::SmallPtrSet<NodeTy*,2> BadDividesTy;
  typedef llvm::SmallPtrSet<NodeTy*,2> NoReturnCallsTy;  
  
  /// UninitBranches - Nodes in the ExplodedGraph that result from
  ///  taking a branch based on an uninitialized value.
  UninitBranchesTy UninitBranches;
  
  /// UninitStores - Sinks in the ExplodedGraph that result from
  ///  making a store to an uninitialized lvalue.
  UninitStoresTy UninitStores;
  
  /// NoReturnCalls - Sinks in the ExplodedGraph that result from
  //  calling a function with the attribute "noreturn".
  NoReturnCallsTy NoReturnCalls;
  
  /// ImplicitNullDeref - Nodes in the ExplodedGraph that result from
  ///  taking a dereference on a symbolic pointer that MAY be NULL.
  BadDerefTy ImplicitNullDeref;
    
  /// ExplicitNullDeref - Nodes in the ExplodedGraph that result from
  ///  taking a dereference on a symbolic pointer that MUST be NULL.
  BadDerefTy ExplicitNullDeref;
  
  /// UnitDeref - Nodes in the ExplodedGraph that result from
  ///  taking a dereference on an uninitialized value.
  BadDerefTy UninitDeref;

  /// BadDivides - Nodes in the ExplodedGraph that result from evaluating
  ///  a divide-by-zero or divide-by-uninitialized.
  BadDividesTy BadDivides;
  
  bool StateCleaned;
  
public:
  GRExprEngine(GraphTy& g) : 
  G(g), Liveness(G.getCFG(), G.getFunctionDecl()),
  Builder(NULL),
  StateMgr(G.getContext(), G.getAllocator()),
  ValMgr(StateMgr.getValueManager()),
  TF(NULL), // FIXME.
  SymMgr(StateMgr.getSymbolManager()),
  StmtEntryNode(NULL), CurrentStmt(NULL) {
    
    // Compute liveness information.
    Liveness.runOnCFG(G.getCFG());
    Liveness.runOnAllBlocks(G.getCFG(), NULL, true);
  }
  
  /// getContext - Return the ASTContext associated with this analysis.
  ASTContext& getContext() const { return G.getContext(); }
  
  /// getCFG - Returns the CFG associated with this analysis.
  CFG& getCFG() { return G.getCFG(); }
  
  /// setTransferFunctions
  void setTransferFunctions(GRTransferFuncs* tf) { TF = tf; }
  void setTransferFunctions(GRTransferFuncs& tf) { TF = &tf; }
  
  /// ViewGraph - Visualize the ExplodedGraph created by executing the
  ///  simulation.
  void ViewGraph();
  
  /// getInitialState - Return the initial state used for the root vertex
  ///  in the ExplodedGraph.
  StateTy getInitialState();
  
  bool isUninitControlFlow(const NodeTy* N) const {
    return N->isSink() && UninitBranches.count(const_cast<NodeTy*>(N)) != 0;
  }
  
  bool isUninitStore(const NodeTy* N) const {
    return N->isSink() && UninitStores.count(const_cast<NodeTy*>(N)) != 0;
  }
  
  bool isImplicitNullDeref(const NodeTy* N) const {
    return N->isSink() && ImplicitNullDeref.count(const_cast<NodeTy*>(N)) != 0;
  }
  
  bool isExplicitNullDeref(const NodeTy* N) const {
    return N->isSink() && ExplicitNullDeref.count(const_cast<NodeTy*>(N)) != 0;
  }
  
  bool isUninitDeref(const NodeTy* N) const {
    return N->isSink() && UninitDeref.count(const_cast<NodeTy*>(N)) != 0;
  }
  
  bool isBadDivide(const NodeTy* N) const {
    return N->isSink() && BadDivides.count(const_cast<NodeTy*>(N)) != 0; 
  }
  
  bool isNoReturnCall(const NodeTy* N) const {
    return N->isSink() && NoReturnCalls.count(const_cast<NodeTy*>(N)) != 0;
  }

  typedef BadDerefTy::iterator null_deref_iterator;
  null_deref_iterator null_derefs_begin() { return ExplicitNullDeref.begin(); }
  null_deref_iterator null_derefs_end() { return ExplicitNullDeref.end(); }
  
  typedef BadDerefTy::iterator uninit_deref_iterator;
  uninit_deref_iterator uninit_derefs_begin() { return UninitDeref.begin(); }
  uninit_deref_iterator uninit_derefs_end() { return UninitDeref.end(); }
  
  typedef BadDividesTy::iterator bad_divide_iterator;
  bad_divide_iterator bad_divides_begin() { return BadDivides.begin(); }
  bad_divide_iterator bad_divides_end() { return BadDivides.end(); }
  
  /// ProcessStmt - Called by GRCoreEngine. Used to generate new successor
  ///  nodes by processing the 'effects' of a block-level statement.
  void ProcessStmt(Stmt* S, StmtNodeBuilder& builder);    
  
  /// ProcessBranch - Called by GRCoreEngine.  Used to generate successor
  ///  nodes by processing the 'effects' of a branch condition.
  void ProcessBranch(Expr* Condition, Stmt* Term, BranchNodeBuilder& builder);
  
  /// ProcessIndirectGoto - Called by GRCoreEngine.  Used to generate successor
  ///  nodes by processing the 'effects' of a computed goto jump.
  void ProcessIndirectGoto(IndirectGotoNodeBuilder& builder);
  
  /// ProcessSwitch - Called by GRCoreEngine.  Used to generate successor
  ///  nodes by processing the 'effects' of a switch statement.
  void ProcessSwitch(SwitchNodeBuilder& builder);
  
protected:
  
  /// RemoveDeadBindings - Return a new state that is the same as 'St' except
  ///  that all subexpression mappings are removed and that any
  ///  block-level expressions that are not live at 'S' also have their
  ///  mappings removed.
  inline StateTy RemoveDeadBindings(Stmt* S, StateTy St) {
    return StateMgr.RemoveDeadBindings(St, S, Liveness);
  }
  
  StateTy SetRVal(StateTy St, Expr* Ex, const RVal& V);
  
  StateTy SetRVal(StateTy St, const Expr* Ex, const RVal& V) {
    return SetRVal(St, const_cast<Expr*>(Ex), V);
  }
 
  StateTy SetBlkExprRVal(StateTy St, Expr* Ex, const RVal& V) {
    return StateMgr.SetRVal(St,