Added GRBlockCounter class, which tracks the number of times blocks

have been visited in a path.  Added GRBlockCounter as an item to be
enqueued to the worklist.

Modified "ProcessBranch" in GRConstants to prune branches with symbolic
conditions that have been already taken.


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@47010 91177308-0d34-0410-b5e6-96231b3b80d8

6 files changed, 208 insertions, 28 deletions

diff --git a/Analysis/GRBlockCounter.cpp b/Analysis/GRBlockCounter.cpp
new file mode 100644
index 0000000000..def87c2c47
--- /dev/null
+++ b/Analysis/GRBlockCounter.cpp
@@ -0,0 +1,54 @@
+//==- GRBlockCounter.h - ADT for counting block visits -------------*- 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 GRBlockCounter, an abstract data type used to count
+//  the number of times a given block has been visited along a path
+//  analyzed by GREngine.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/Analysis/PathSensitive/GRBlockCounter.h"
+#include "llvm/ADT/ImmutableMap.h"
+
+using namespace clang;
+
+typedef llvm::ImmutableMap<unsigned,unsigned> CountMap;
+
+static inline CountMap GetMap(void* D) {
+  return CountMap(static_cast<CountMap::TreeTy*>(D));
+}
+
+static inline CountMap::Factory& GetFactory(void* F) {
+  return *static_cast<CountMap::Factory*>(F);
+}
+
+unsigned GRBlockCounter::getNumVisited(unsigned BlockID) const {
+  CountMap M = GetMap(Data);
+  CountMap::TreeTy* T = M.SlimFind(BlockID);
+  return T ? T->getValue().second : 0;
+}
+
+GRBlockCounter::Factory::Factory(llvm::BumpPtrAllocator& Alloc) {
+  F = new CountMap::Factory(Alloc);
+}
+
+GRBlockCounter::Factory::~Factory() {
+  delete static_cast<CountMap*>(F);
+}
+
+GRBlockCounter
+GRBlockCounter::Factory::IncrementCount(GRBlockCounter BC, unsigned BlockID) {
+  return GRBlockCounter(GetFactory(F).Add(GetMap(BC.Data), BlockID,
+                                        BC.getNumVisited(BlockID)+1).getRoot());
+}
+
+GRBlockCounter
+GRBlockCounter::Factory::GetEmptyCounter() {
+  return GRBlockCounter(GetFactory(F).GetEmptyMap().getRoot());
+}
diff --git a/Analysis/GRConstants.cpp b/Analysis/GRConstants.cpp
index 4ae90770c9..8b94aaa70b 100644
--- a/Analysis/GRConstants.cpp
+++ b/Analysis/GRConstants.cpp
@@ -375,23 +375,45 @@ void GRConstants::ProcessBranch(Expr* Condition, Stmt* Term,
     }      
   }
 
-  // Process the true branch.
-  bool isFeasible = true;
+  // Get the current block counter.
+  GRBlockCounter BC = builder.getBlockCounter();
+    
+  unsigned NumVisited = BC.getNumVisited(builder.getTargetBlock(true)->getBlockID());
   
-  StateTy St = Assume(PrevState, V, true, isFeasible);
+  if (isa<nonlval::ConcreteInt>(V) || 
+      BC.getNumVisited(builder.getTargetBlock(true)->getBlockID()) < 1) {
+    
+    // Process the true branch.
 
-  if (isFeasible)
-    builder.generateNode(St, true);
-  else {
-    builder.markInfeasible(true);
-    isFeasible = true;
+    bool isFeasible = true;
+    
+    StateTy St = Assume(PrevState, V, true, isFeasible);
+
+    if (isFeasible)
+      builder.generateNode(St, true);
+    else
+      builder.markInfeasible(true);
   }
+  else
+    builder.markInfeasible(true);
   
-  // Process the false branch.  
-  St = Assume(PrevState, V, false, isFeasible);
+  NumVisited = BC.getNumVisited(builder.getTargetBlock(true)->getBlockID());
+
   
-  if (isFeasible)
-    builder.generateNode(St, false);
+  if (isa<nonlval::ConcreteInt>(V) || 
+      BC.getNumVisited(builder.getTargetBlock(false)->getBlockID()) < 1) {
+    
+    // Process the false branch.  
+    
+    bool isFeasible = false;
+    
+    StateTy St = Assume(PrevState, V, false, isFeasible);
+    
+    if (isFeasible)
+      builder.generateNode(St, false);
+    else
+      builder.markInfeasible(false);
+  }
   else
     builder.markInfeasible(false);
 }
diff --git a/Analysis/GREngine.cpp b/Analysis/GREngine.cpp
index e3b238aebe..9858f24784 100644
--- a/Analysis/GREngine.cpp
+++ b/Analysis/GREngine.cpp
@@ -71,6 +71,9 @@ bool GREngineImpl::ExecuteWorkList(unsigned Steps) {
     // starting location in the function.
     BlockEdge StartLoc(getCFG(), Entry, Succ);
     
+    // Set the current block counter to being empty.
+    WList->setBlockCounter(BCounterFactory.GetEmptyCounter());
+    
     // Generate the root.
     GenerateNode(StartLoc, getInitialState());
   }
@@ -78,6 +81,11 @@ bool GREngineImpl::ExecuteWorkList(unsigned Steps) {
   while (Steps && WList->hasWork()) {
     --Steps;
     const GRWorkListUnit& WU = WList->Dequeue();
+    
+    // Set the current block counter.
+    WList->setBlockCounter(WU.getBlockCounter());
+
+    // Retrieve the node.
     ExplodedNodeImpl* Node = WU.getNode();
     
     // Dispatch on the location type.
@@ -138,6 +146,12 @@ void GREngineImpl::HandleBlockEdge(const BlockEdge& L, ExplodedNodeImpl* Pred) {
 void GREngineImpl::HandleBlockEntrance(const BlockEntrance& L,
                                        ExplodedNodeImpl* Pred) {
   
+  // Increment the block counter.
+  GRBlockCounter Counter = WList->getBlockCounter();
+  Counter = BCounterFactory.IncrementCount(Counter, L.getBlock()->getBlockID());
+  WList->setBlockCounter(Counter);
+  
+  // Process the entrance of the block.  
   if (Stmt* S = L.getFirstStmt()) {
     GRStmtNodeBuilderImpl Builder(L.getBlock(), 0, Pred, this);
     ProcessStmt(S, Builder);
@@ -196,7 +210,7 @@ void GREngineImpl::HandleBranch(Expr* Cond, Stmt* Term, CFGBlock * B,
                                 ExplodedNodeImpl* Pred) {
   assert (B->succ_size() == 2);
 
-  GRBranchNodeBuilderImpl Builder(B, *(B->succ_begin()), *(B->succ_begin()+1), 
+  GRBranchNodeBuilderImpl Builder(B, *(B->succ_begin()), *(B->succ_begin()+1),
                                   Pred, this);
   
   ProcessBranch(Cond, Term, Builder);
@@ -244,7 +258,7 @@ void GREngineImpl::GenerateNode(const ProgramPoint& Loc, void* State,
   }
   
   // Only add 'Node' to the worklist if it was freshly generated.
-  if (IsNew) WList->Enqueue(GRWorkListUnit(Node));
+  if (IsNew) WList->Enqueue(Node);
 }
 
 GRStmtNodeBuilderImpl::GRStmtNodeBuilderImpl(CFGBlock* b, unsigned idx,
@@ -325,5 +339,5 @@ GRBranchNodeBuilderImpl::~GRBranchNodeBuilderImpl() {
   if (!GeneratedFalse) generateNodeImpl(Pred->State, false);
   
   for (DeferredTy::iterator I=Deferred.begin(), E=Deferred.end(); I!=E; ++I)
-    if (!(*I)->isSink()) Eng.WList->Enqueue(GRWorkListUnit(*I));
+    if (!(*I)->isSink()) Eng.WList->Enqueue(*I);
 }
diff --git a/include/clang/Analysis/PathSensitive/GRBlockCounter.h b/include/clang/Analysis/PathSensitive/GRBlockCounter.h
new file mode 100644
index 0000000000..4197a8fd85
--- /dev/null
+++ b/include/clang/Analysis/PathSensitive/GRBlockCounter.h
@@ -0,0 +1,50 @@
+//==- GRBlockCounter.h - ADT for counting block visits -------------*- 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 GRBlockCounter, an abstract data type used to count
+//  the number of times a given block has been visited along a path
+//  analyzed by GREngine.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_GRBLOCKCOUNTER
+#define LLVM_CLANG_ANALYSIS_GRBLOCKCOUNTER
+
+namespace llvm {
+  class BumpPtrAllocator;
+}
+
+namespace clang {
+
+class GRBlockCounter {
+  void* Data;
+  
+  GRBlockCounter(void* D) : Data(D) {}  
+
+public:
+  GRBlockCounter() : Data(0) {}
+  
+  unsigned getNumVisited(unsigned BlockID) const;
+  
+  class Factory {
+    void* F;
+  public:
+    Factory(llvm::BumpPtrAllocator& Alloc);
+    ~Factory();
+    
+    GRBlockCounter GetEmptyCounter();
+    GRBlockCounter IncrementCount(GRBlockCounter BC, unsigned BlockID);
+  };
+  
+  friend class Factory;
+};
+
+} // end clang namespace
+  
+#endif
diff --git a/include/clang/Analysis/PathSensitive/GREngine.h b/include/clang/Analysis/PathSensitive/GREngine.h
index 157d283d5a..14ca1842da 100644
--- a/include/clang/Analysis/PathSensitive/GREngine.h
+++ b/include/clang/Analysis/PathSensitive/GREngine.h
@@ -8,7 +8,7 @@
 //===----------------------------------------------------------------------===//
 //
 //  This file defines a generic engine for intraprocedural, path-sensitive,
-//  dataflow analysis via graph reachability engine.
+//  dataflow analysis via graph reachability.
 //
 //===----------------------------------------------------------------------===//
 
@@ -17,6 +17,7 @@
 
 #include "clang/Analysis/PathSensitive/ExplodedGraph.h"
 #include "clang/Analysis/PathSensitive/GRWorkList.h"
+#include "clang/Analysis/PathSensitive/GRBlockCounter.h"
 #include "llvm/ADT/OwningPtr.h"
 
 namespace clang {
@@ -47,7 +48,12 @@ protected:
   ///  the order that nodes are processed.
   GRWorkList* WList;
   
-  void GenerateNode(const ProgramPoint& Loc, void* State, 
+  /// BCounterFactory - A factory object for created GRBlockCounter objects.
+  ///   These are used to record for key nodes in the ExplodedGraph the
+  ///   number of times different CFGBlocks have been visited along a path.
+  GRBlockCounter::Factory BCounterFactory;
+  
+  void GenerateNode(const ProgramPoint& Loc, void* State,
                     ExplodedNodeImpl* Pred = NULL);
   
   /// getInitialState - Gets the void* representing the initial 'state'
@@ -78,7 +84,8 @@ private:
   GREngineImpl& operator=(const GREngineImpl&);
   
 protected:  
-  GREngineImpl(ExplodedGraphImpl* g, GRWorkList* wl) : G(g), WList(wl) {}
+  GREngineImpl(ExplodedGraphImpl* g, GRWorkList* wl)
+    : G(g), WList(wl), BCounterFactory(g->getAllocator()) {}
   
 public:
   /// ExecuteWorkList - Run the worklist algorithm for a maximum number of
@@ -183,8 +190,13 @@ public:
   
   ExplodedNodeImpl* getPredecessor() const { return Pred; }
   const ExplodedGraphImpl& getGraph() const { return *Eng.G; }
+  GRBlockCounter getBlockCounter() const { return Eng.WList->getBlockCounter();}
     
-  ExplodedNodeImpl* generateNodeImpl(void* State, bool branch);  
+  ExplodedNodeImpl* generateNodeImpl(void* State, bool branch);
+  
+  CFGBlock* getTargetBlock(bool branch) const {
+    return branch ? DstT : DstF;
+  }    
   
   void markInfeasible(bool branch) {
     if (branch) GeneratedTrue = true;
@@ -221,6 +233,14 @@ public:
     return static_cast<NodeTy*>(NB.generateNodeImpl(state, branch));
   }
   
+  GRBlockCounter getBlockCounter() const {
+    return NB.getBlockCounter();
+  }
+  
+  CFGBlock* getTargetBlock(bool branch) const {
+    return NB.getTargetBlock(branch);
+  }
+  
   inline void markInfeasible(bool branch) {
     NB.markInfeasible(branch);
   }
diff --git a/include/clang/Analysis/PathSensitive/GRWorkList.h b/include/clang/Analysis/PathSensitive/GRWorkList.h
index 6f82594f5a..b18da6be29 100644
--- a/include/clang/Analysis/PathSensitive/GRWorkList.h
+++ b/include/clang/Analysis/PathSensitive/GRWorkList.h
@@ -15,39 +15,59 @@
 #ifndef LLVM_CLANG_ANALYSIS_GRWORKLIST
 #define LLVM_CLANG_ANALYSIS_GRWORKLIST
 
+#include "clang/Analysis/PathSensitive/GRBlockCounter.h"
+
 namespace clang {  
 
 class ExplodedNodeImpl;
   
 class GRWorkListUnit {
   ExplodedNodeImpl* Node;
+  GRBlockCounter Counter;
   CFGBlock* Block;
   unsigned BlockIdx;
   
 public:
-  GRWorkListUnit(ExplodedNodeImpl* N, CFGBlock* B, unsigned idx)
-  : Node(N), Block(B), BlockIdx(idx) {}
+  GRWorkListUnit(ExplodedNodeImpl* N, GRBlockCounter C,
+                 CFGBlock* B, unsigned idx)
+  : Node(N),
+    Counter(C),
+    Block(B),
+    BlockIdx(idx) {}
   
-  explicit GRWorkListUnit(ExplodedNodeImpl* N)
-  : Node(N), Block(NULL), BlockIdx(0) {}
+  explicit GRWorkListUnit(ExplodedNodeImpl* N, GRBlockCounter C)
+  : Node(N),
+    Counter(C),
+    Block(NULL),
+    BlockIdx(0) {}
   
-  ExplodedNodeImpl* getNode()  const { return Node; }    
-  CFGBlock*         getBlock() const { return Block; }
-  unsigned          getIndex() const { return BlockIdx; }
+  ExplodedNodeImpl* getNode()         const { return Node; }
+  GRBlockCounter    getBlockCounter() const { return Counter; }
+  CFGBlock*         getBlock()        const { return Block; }
+  unsigned          getIndex()        const { return BlockIdx; }
 };
 
 class GRWorkList {
+  GRBlockCounter CurrentCounter;
 public:
   virtual ~GRWorkList();
   virtual bool hasWork() const = 0;
+    
   virtual void Enqueue(const GRWorkListUnit& U) = 0;
 
-  void Enqueue(ExplodedNodeImpl* N, CFGBlock& B, unsigned idx) {
-    Enqueue(GRWorkListUnit(N,&B,idx));
+  void Enqueue(ExplodedNodeImpl* N, CFGBlock& B, unsigned idx) {    
+    Enqueue(GRWorkListUnit(N, CurrentCounter, &B, idx));
+  }
+  
+  void Enqueue(ExplodedNodeImpl* N) {
+    Enqueue(GRWorkListUnit(N, CurrentCounter));
   }
   
   virtual GRWorkListUnit Dequeue() = 0;
   
+  void setBlockCounter(GRBlockCounter C) { CurrentCounter = C; }
+  GRBlockCounter getBlockCounter() const { return CurrentCounter; }
+  
   static GRWorkList* MakeDFS(); 
 };
 } // end clang namespace