Initial support for checking out of bound memory access. Only support

ConcreteInt index for now.


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

10 files changed, 96 insertions, 7 deletions

diff --git a/include/clang/Analysis/PathSensitive/BasicValueFactory.h b/include/clang/Analysis/PathSensitive/BasicValueFactory.h
index 639ff5d92c..70fbe1de83 100644
--- a/include/clang/Analysis/PathSensitive/BasicValueFactory.h
+++ b/include/clang/Analysis/PathSensitive/BasicValueFactory.h
@@ -72,6 +72,7 @@ public:
   ASTContext& getContext() const { return Ctx; }  
 
   const llvm::APSInt& getValue(const llvm::APSInt& X);
+  const llvm::APSInt& getValue(const llvm::APInt& X, bool isUnsigned);
   const llvm::APSInt& getValue(uint64_t X, unsigned BitWidth, bool isUnsigned);
   const llvm::APSInt& getValue(uint64_t X, QualType T);
 
diff --git a/include/clang/Analysis/PathSensitive/ConstraintManager.h b/include/clang/Analysis/PathSensitive/ConstraintManager.h
index 71ae247f57..3f2e60d3ef 100644
--- a/include/clang/Analysis/PathSensitive/ConstraintManager.h
+++ b/include/clang/Analysis/PathSensitive/ConstraintManager.h
@@ -34,6 +34,10 @@ public:
   virtual const GRState* Assume(const GRState* St, SVal Cond, 
                                 bool Assumption, bool& isFeasible) = 0;
 
+  virtual const GRState* AssumeInBound(const GRState* St, SVal Idx, 
+                                       SVal UpperBound, bool Assumption,
+                                       bool& isFeasible) = 0;
+
   virtual const GRState* AddNE(const GRState* St, SymbolID sym, 
                                const llvm::APSInt& V) = 0;
   virtual const llvm::APSInt* getSymVal(const GRState* St, SymbolID sym) = 0;
diff --git a/include/clang/Analysis/PathSensitive/GRExprEngine.h b/include/clang/Analysis/PathSensitive/GRExprEngine.h
index 5ba61d8645..1b7d9bf6a3 100644
--- a/include/clang/Analysis/PathSensitive/GRExprEngine.h
+++ b/include/clang/Analysis/PathSensitive/GRExprEngine.h
@@ -468,11 +468,7 @@ protected:
 
   const GRState* AssumeInBound(const GRState* St, SVal Idx, SVal UpperBound,
                                bool Assumption, bool& isFeasible) {
-    // FIXME: In this function, we will check if Idx can be in/out 
-    // [0, UpperBound) according to the assumption.  We can extend the 
-    // interface to include a LowerBound parameter.
-    isFeasible = true;
-    return St;
+    return StateMgr.AssumeInBound(St, Idx, UpperBound, Assumption, isFeasible);
   }
 
   NodeTy* MakeNode(NodeSet& Dst, Stmt* S, NodeTy* Pred, const GRState* St,
diff --git a/include/clang/Analysis/PathSensitive/GRState.h b/include/clang/Analysis/PathSensitive/GRState.h
index 0a40998e39..68f7921db3 100644
--- a/include/clang/Analysis/PathSensitive/GRState.h
+++ b/include/clang/Analysis/PathSensitive/GRState.h
@@ -523,6 +523,12 @@ public:
     return ConstraintMgr->Assume(St, Cond, Assumption, isFeasible);
   }
 
+  const GRState* AssumeInBound(const GRState* St, SVal Idx, SVal UpperBound,
+                               bool Assumption, bool& isFeasible) {
+    return ConstraintMgr->AssumeInBound(St, Idx, UpperBound, Assumption, 
+                                        isFeasible);
+  }
+
   const GRState* AddNE(const GRState* St, SymbolID sym, const llvm::APSInt& V) {
     return ConstraintMgr->AddNE(St, sym, V);
   }
diff --git a/include/clang/Analysis/PathSensitive/SVals.h b/include/clang/Analysis/PathSensitive/SVals.h
index 417a89adc8..16322f111f 100644
--- a/include/clang/Analysis/PathSensitive/SVals.h
+++ b/include/clang/Analysis/PathSensitive/SVals.h
@@ -173,6 +173,9 @@ public:
   static NonLoc MakeVal(BasicValueFactory& BasicVals, uint64_t X, QualType T);
   
   static NonLoc MakeVal(BasicValueFactory& BasicVals, IntegerLiteral* I);
+
+  static NonLoc MakeVal(BasicValueFactory& BasicVals, const llvm::APInt& I,
+                        bool isUnsigned);
     
   static NonLoc MakeIntTruthVal(BasicValueFactory& BasicVals, bool b);
 
diff --git a/lib/Analysis/BasicConstraintManager.cpp b/lib/Analysis/BasicConstraintManager.cpp
index b09d9de446..a359b23c54 100644
--- a/lib/Analysis/BasicConstraintManager.cpp
+++ b/lib/Analysis/BasicConstraintManager.cpp
@@ -69,6 +69,9 @@ public:
   const GRState* AssumeSymLE(const GRState* St, SymbolID sym,
                              const llvm::APSInt& V, bool& isFeasible);
 
+  const GRState* AssumeInBound(const GRState* St, SVal Idx, SVal UpperBound,
+                               bool Assumption, bool& isFeasible);
+
   const GRState* AddEQ(const GRState* St, SymbolID sym, const llvm::APSInt& V);
 
   const GRState* AddNE(const GRState* St, SymbolID sym, const llvm::APSInt& V);
@@ -83,6 +86,9 @@ public:
 
   void print(const GRState* St, std::ostream& Out, 
              const char* nl, const char *sep);
+
+private:
+  BasicValueFactory& getBasicVals() { return StateMgr.getBasicVals(); }
 };
 
 } // end anonymous namespace
@@ -352,6 +358,27 @@ BasicConstraintManager::AssumeSymLE(const GRState* St, SymbolID sym,
   return St;
 }
 
+const GRState* 
+BasicConstraintManager::AssumeInBound(const GRState* St, SVal Idx, 
+                                      SVal UpperBound, bool Assumption, 
+                                      bool& isFeasible) {
+  // Only support ConcreteInt for now.
+  if (!(isa<nonloc::ConcreteInt>(Idx) && isa<nonloc::ConcreteInt>(UpperBound))){
+    isFeasible = true;
+    return St;
+  }
+
+  const llvm::APSInt& Zero = getBasicVals().getZeroWithPtrWidth(false);
+  const llvm::APSInt& IdxV = cast<nonloc::ConcreteInt>(Idx).getValue();
+  const llvm::APSInt& UBV = cast<nonloc::ConcreteInt>(UpperBound).getValue();
+
+  bool InBound = (Zero <= IdxV) && (IdxV < UBV);
+
+  isFeasible = Assumption ? InBound : !InBound;
+
+  return St;
+}
+
 static int ConstEqTyIndex = 0;
 static int ConstNotEqTyIndex = 0;
 
diff --git a/lib/Analysis/BasicValueFactory.cpp b/lib/Analysis/BasicValueFactory.cpp
index 5b7041bc43..7ce305e4cf 100644
--- a/lib/Analysis/BasicValueFactory.cpp
+++ b/lib/Analysis/BasicValueFactory.cpp
@@ -76,6 +76,12 @@ const llvm::APSInt& BasicValueFactory::getValue(const llvm::APSInt& X) {
   return *P;
 }
 
+const llvm::APSInt& BasicValueFactory::getValue(const llvm::APInt& X,
+                                                bool isUnsigned) {
+  llvm::APSInt V(X, isUnsigned);
+  return getValue(V);
+}
+
 const llvm::APSInt& BasicValueFactory::getValue(uint64_t X, unsigned BitWidth,
                                            bool isUnsigned) {
   llvm::APSInt V(BitWidth, isUnsigned);
diff --git a/lib/Analysis/GRExprEngine.cpp b/lib/Analysis/GRExprEngine.cpp
index db325fb9f9..6de910fc17 100644
--- a/lib/Analysis/GRExprEngine.cpp
+++ b/lib/Analysis/GRExprEngine.cpp
@@ -1084,9 +1084,14 @@ const GRState* GRExprEngine::EvalLocation(Stmt* Ex, NodeTy* Pred,
       bool isFeasibleOutBound = false;
       const GRState* StOutBound = AssumeInBound(StNotNull, Idx, NumElements, 
                                                 false, isFeasibleOutBound);
-      StInBound = StOutBound = 0; // FIXME: squeltch warning.
 
-      // Report warnings ...
+      if (isFeasibleOutBound) {
+        // Report warning.
+
+        StOutBound = 0;
+      }
+
+      return isFeasibleInBound ? StInBound : NULL;
     }
   }
   
diff --git a/lib/Analysis/RegionStore.cpp b/lib/Analysis/RegionStore.cpp
index 6f632f4bc5..cc7715a98a 100644
--- a/lib/Analysis/RegionStore.cpp
+++ b/lib/Analysis/RegionStore.cpp
@@ -80,6 +80,8 @@ public:
 
   SVal getLValueElement(const GRState* St, SVal Base, SVal Offset);
 
+  SVal getSizeInElements(const GRState* St, const MemRegion* R);
+
   SVal ArrayToPointer(SVal Array);
 
   std::pair<const GRState*, SVal>
@@ -257,6 +259,40 @@ SVal RegionStoreManager::getLValueElement(const GRState* St,
   return UnknownVal();
 }
 
+SVal RegionStoreManager::getSizeInElements(const GRState* St,
+                                           const MemRegion* R) {
+  if (const VarRegion* VR = dyn_cast<VarRegion>(R)) {
+    // Get the type of the variable.
+    QualType T = VR->getType(getContext());
+
+    // It must be of array type. 
+    const ConstantArrayType* CAT = cast<ConstantArrayType>(T.getTypePtr());
+
+    // return the size as signed integer.
+    return NonLoc::MakeVal(getBasicVals(), CAT->getSize(), false);
+  }
+
+  if (const StringRegion* SR = dyn_cast<StringRegion>(R)) {
+    // FIXME: Unsupported yet.
+    SR = 0;
+    return UnknownVal();
+  }
+
+  if (const AnonTypedRegion* ATR = dyn_cast<AnonTypedRegion>(R)) {
+    // FIXME: Unsupported yet.
+    ATR = 0;
+    return UnknownVal();
+  }
+
+  if (const FieldRegion* FR = dyn_cast<FieldRegion>(R)) {
+    // FIXME: Unsupported yet.
+    FR = 0;
+    return UnknownVal();
+  }
+  printf("kidn = %d\n", R->getKind());
+  assert(0 && "Other regions are not supported yet.");
+}
+
 // Cast 'pointer to array' to 'pointer to the first element of array'.
 
 SVal RegionStoreManager::ArrayToPointer(SVal Array) {
diff --git a/lib/Analysis/SVals.cpp b/lib/Analysis/SVals.cpp
index 644f60d25a..764a05fe8f 100644
--- a/lib/Analysis/SVals.cpp
+++ b/lib/Analysis/SVals.cpp
@@ -253,6 +253,11 @@ NonLoc NonLoc::MakeVal(BasicValueFactory& BasicVals, IntegerLiteral* I) {
                               I->getType()->isUnsignedIntegerType())));
 }
 
+NonLoc NonLoc::MakeVal(BasicValueFactory& BasicVals, const llvm::APInt& I,
+                       bool isUnsigned) {
+  return nonloc::ConcreteInt(BasicVals.getValue(I, isUnsigned));
+}
+
 NonLoc NonLoc::MakeIntTruthVal(BasicValueFactory& BasicVals, bool b) {
   return nonloc::ConcreteInt(BasicVals.getTruthValue(b));
 }