Switch RegionStore over to using <BaseRegion+raw offset> to store
value bindings. Along with a small change to OSAtomicChecker, this
resolves <rdar://problem/7527292> and resolves some long-standing
issues with how values can be bound to the same physical address by
not have the same "key". This change is only a beginning; logically
RegionStore needs to better handle loads from addresses where the
stored value is larger/smaller/different type than the loaded value.
We handle these cases in an approximate fashion now (via
CastRetrievedVal and help in SimpleSValuator), but it could be made
much smarter.
git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@93137 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/clang/Analysis/PathSensitive/SValuator.h b/include/clang/Analysis/PathSensitive/SValuator.h
index e63eb12..4a4b502 100644
--- a/include/clang/Analysis/PathSensitive/SValuator.h
+++ b/include/clang/Analysis/PathSensitive/SValuator.h
@@ -28,8 +28,10 @@
protected:
ValueManager &ValMgr;
+public:
+ // FIXME: Make these protected again one RegionStoreManager correctly
+ // handles loads from differening bound value types.
virtual SVal EvalCastNL(NonLoc val, QualType castTy) = 0;
-
virtual SVal EvalCastL(Loc val, QualType castTy) = 0;
public:
diff --git a/include/clang/Analysis/PathSensitive/Store.h b/include/clang/Analysis/PathSensitive/Store.h
index aaf8223..70c17ac 100644
--- a/include/clang/Analysis/PathSensitive/Store.h
+++ b/include/clang/Analysis/PathSensitive/Store.h
@@ -189,7 +189,8 @@
/// CastRetrievedVal - Used by subclasses of StoreManager to implement
/// implicit casts that arise from loads from regions that are reinterpreted
/// as another region.
- SVal CastRetrievedVal(SVal val, const TypedRegion *R, QualType castTy);
+ SVal CastRetrievedVal(SVal val, const TypedRegion *R, QualType castTy,
+ bool performTestOnly = true);
};
// FIXME: Do we still need this?
diff --git a/lib/Analysis/OSAtomicChecker.cpp b/lib/Analysis/OSAtomicChecker.cpp
index cf16796..9d34e9e 100644
--- a/lib/Analysis/OSAtomicChecker.cpp
+++ b/lib/Analysis/OSAtomicChecker.cpp
@@ -103,19 +103,9 @@
SVal location = state->getSVal(theValueExpr);
// Here we should use the value type of the region as the load type.
QualType LoadTy;
- if (const MemRegion *R = location.getAsRegion()) {
- // We must be careful, as SymbolicRegions aren't typed.
- const MemRegion *strippedR = R->StripCasts();
- // FIXME: This isn't quite the right solution. One test case in 'test/Analysis/NSString.m'
- // is giving the wrong result.
- const TypedRegion *typedR =
- isa<SymbolicRegion>(strippedR) ? cast<TypedRegion>(R) :
- dyn_cast<TypedRegion>(strippedR);
-
- if (typedR) {
- LoadTy = typedR->getValueType(Ctx);
- location = loc::MemRegionVal(typedR);
- }
+ if (const TypedRegion *TR =
+ dyn_cast_or_null<TypedRegion>(location.getAsRegion())) {
+ LoadTy = TR->getValueType(Ctx);
}
Engine.EvalLoad(Tmp, const_cast<Expr *>(theValueExpr), C.getPredecessor(),
state, location, OSAtomicLoadTag, LoadTy);
@@ -184,14 +174,22 @@
E2 = TmpStore.end(); I2 != E2; ++I2) {
ExplodedNode *predNew = *I2;
const GRState *stateNew = predNew->getState();
- SVal Res = Engine.getValueManager().makeTruthVal(true, CE->getType());
+ // Check for 'void' return type if we have a bogus function prototype.
+ SVal Res = UnknownVal();
+ QualType T = CE->getType();
+ if (!T->isVoidType())
+ Res = Engine.getValueManager().makeTruthVal(true, T);
C.GenerateNode(stateNew->BindExpr(CE, Res), predNew);
}
}
// Were they not equal?
if (const GRState *stateNotEqual = stateLoad->Assume(Cmp, false)) {
- SVal Res = Engine.getValueManager().makeTruthVal(false, CE->getType());
+ // Check for 'void' return type if we have a bogus function prototype.
+ SVal Res = UnknownVal();
+ QualType T = CE->getType();
+ if (!T->isVoidType())
+ Res = Engine.getValueManager().makeTruthVal(false, CE->getType());
C.GenerateNode(stateNotEqual->BindExpr(CE, Res), N);
}
}
diff --git a/lib/Analysis/RegionStore.cpp b/lib/Analysis/RegionStore.cpp
index 20549d1..9b5b44b 100644
--- a/lib/Analysis/RegionStore.cpp
+++ b/lib/Analysis/RegionStore.cpp
@@ -87,8 +87,8 @@
namespace {
class BindingKey : public std::pair<const MemRegion*, uint64_t> {
public:
- explicit BindingKey(const MemRegion *r)
- : std::pair<const MemRegion*,uint64_t>(r,0) {}
+ explicit BindingKey(const MemRegion *r, uint64_t offset)
+ : std::pair<const MemRegion*,uint64_t>(r, offset) { assert(r); }
const MemRegion *getRegion() const { return first; }
uint64_t getOffset() const { return second; }
@@ -97,6 +97,8 @@
ID.AddPointer(getRegion());
ID.AddInteger(getOffset());
}
+
+ static BindingKey Make(const MemRegion *R);
};
} // end anonymous namespace
@@ -1101,19 +1103,43 @@
if (const FieldRegion* FR = dyn_cast<FieldRegion>(R))
return SValuator::CastResult(state,
- CastRetrievedVal(RetrieveField(state, FR), FR, T));
+ CastRetrievedVal(RetrieveField(state, FR), FR,
+ T, false));
- if (const ElementRegion* ER = dyn_cast<ElementRegion>(R))
+ if (const ElementRegion* ER = dyn_cast<ElementRegion>(R)) {
+ // FIXME: Here we actually perform an implicit conversion from the loaded
+ // value to the element type. Eventually we want to compose these values
+ // more intelligently. For example, an 'element' can encompass multiple
+ // bound regions (e.g., several bound bytes), or could be a subset of
+ // a larger value.
return SValuator::CastResult(state,
- CastRetrievedVal(RetrieveElement(state, ER), ER, T));
+ CastRetrievedVal(RetrieveElement(state, ER),
+ ER, T, false));
+ }
- if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R))
+ if (const ObjCIvarRegion *IVR = dyn_cast<ObjCIvarRegion>(R)) {
+ // FIXME: Here we actually perform an implicit conversion from the loaded
+ // value to the ivar type. What we should model is stores to ivars
+ // that blow past the extent of the ivar. If the address of the ivar is
+ // reinterpretted, it is possible we stored a different value that could
+ // fit within the ivar. Either we need to cast these when storing them
+ // or reinterpret them lazily (as we do here).
return SValuator::CastResult(state,
- CastRetrievedVal(RetrieveObjCIvar(state, IVR), IVR, T));
+ CastRetrievedVal(RetrieveObjCIvar(state, IVR),
+ IVR, T, false));
+ }
- if (const VarRegion *VR = dyn_cast<VarRegion>(R))
+ if (const VarRegion *VR = dyn_cast<VarRegion>(R)) {
+ // FIXME: Here we actually perform an implicit conversion from the loaded
+ // value to the variable type. What we should model is stores to variables
+ // that blow past the extent of the variable. If the address of the
+ // variable is reinterpretted, it is possible we stored a different value
+ // that could fit within the variable. Either we need to cast these when
+ // storing them or reinterpret them lazily (as we do here).
return SValuator::CastResult(state,
- CastRetrievedVal(RetrieveVar(state, VR), VR, T));
+ CastRetrievedVal(RetrieveVar(state, VR), VR, T,
+ false));
+ }
RegionBindings B = GetRegionBindings(state->getStore());
const BindingVal *V = Lookup(B, R);
@@ -1169,7 +1195,7 @@
const ElementRegion* R) {
// Check if the region has a binding.
RegionBindings B = GetRegionBindings(state->getStore());
- if (Optional<SVal> V = getDirectBinding(B, R))
+ if (Optional<SVal> V = getDirectBinding(B, R))
return *V;
const MemRegion* superR = R->getSuperRegion();
@@ -1219,7 +1245,7 @@
// Other cases: give up.
return UnknownVal();
}
-
+
return RetrieveFieldOrElementCommon(state, R, R->getElementType(), superR);
}
@@ -1413,13 +1439,9 @@
//===----------------------------------------------------------------------===//
Store RegionStoreManager::Remove(Store store, Loc L) {
- const MemRegion* R = 0;
-
if (isa<loc::MemRegionVal>(L))
- R = cast<loc::MemRegionVal>(L).getRegion();
-
- if (R)
- return Remove(store, BindingKey(R));
+ if (const MemRegion* R = cast<loc::MemRegionVal>(L).getRegion())
+ return Remove(store, BindingKey::Make(R));
return store;
}
@@ -1695,6 +1717,20 @@
// "Raw" retrievals and bindings.
//===----------------------------------------------------------------------===//
+BindingKey BindingKey::Make(const MemRegion *R) {
+ if (const ElementRegion *ER = dyn_cast<ElementRegion>(R)) {
+ const RegionRawOffset &O = ER->getAsRawOffset();
+
+ if (O.getRegion())
+ return BindingKey(O.getRegion(), O.getByteOffset());
+
+ // FIXME: There are some ElementRegions for which we cannot compute
+ // raw offsets yet, including regions with symbolic offsets.
+ }
+
+ return BindingKey(R, 0);
+}
+
RegionBindings RegionStoreManager::Add(RegionBindings B, BindingKey K,
BindingVal V) {
return RBFactory.Add(B, K, V);
@@ -1702,7 +1738,7 @@
RegionBindings RegionStoreManager::Add(RegionBindings B, const MemRegion *R,
BindingVal V) {
- return Add(B, BindingKey(R), V);
+ return Add(B, BindingKey::Make(R), V);
}
const BindingVal *RegionStoreManager::Lookup(RegionBindings B, BindingKey K) {
@@ -1711,7 +1747,7 @@
const BindingVal *RegionStoreManager::Lookup(RegionBindings B,
const MemRegion *R) {
- return Lookup(B, BindingKey(R));
+ return Lookup(B, BindingKey::Make(R));
}
RegionBindings RegionStoreManager::Remove(RegionBindings B, BindingKey K) {
@@ -1719,7 +1755,7 @@
}
RegionBindings RegionStoreManager::Remove(RegionBindings B, const MemRegion *R){
- return Remove(B, BindingKey(R));
+ return Remove(B, BindingKey::Make(R));
}
Store RegionStoreManager::Remove(Store store, BindingKey K) {
diff --git a/lib/Analysis/SimpleSValuator.cpp b/lib/Analysis/SimpleSValuator.cpp
index 2afcd3e..8f2f5a1 100644
--- a/lib/Analysis/SimpleSValuator.cpp
+++ b/lib/Analysis/SimpleSValuator.cpp
@@ -53,13 +53,13 @@
if (isLocType)
return LI->getLoc();
+ // FIXME: Correctly support promotions/truncations.
ASTContext &Ctx = ValMgr.getContext();
-
- // FIXME: Support promotions/truncations.
- if (Ctx.getTypeSize(castTy) == Ctx.getTypeSize(Ctx.VoidPtrTy))
+ unsigned castSize = Ctx.getTypeSize(castTy);
+ if (castSize == LI->getNumBits())
return val;
- return UnknownVal();
+ return ValMgr.makeLocAsInteger(LI->getLoc(), castSize);
}
if (const SymExpr *se = val.getAsSymbolicExpression()) {
diff --git a/lib/Analysis/Store.cpp b/lib/Analysis/Store.cpp
index 4d15023..fd44a80 100644
--- a/lib/Analysis/Store.cpp
+++ b/lib/Analysis/Store.cpp
@@ -197,23 +197,29 @@
/// CastRetrievedVal - Used by subclasses of StoreManager to implement
/// implicit casts that arise from loads from regions that are reinterpreted
/// as another region.
-SVal StoreManager::CastRetrievedVal(SVal V, const TypedRegion *R,
- QualType castTy) {
+SVal StoreManager::CastRetrievedVal(SVal V, const TypedRegion *R,
+ QualType castTy, bool performTestOnly) {
-#ifndef NDEBUG
if (castTy.isNull())
return V;
ASTContext &Ctx = ValMgr.getContext();
- QualType T = R->getValueType(Ctx);
- // Automatically translate references to pointers.
- if (const ReferenceType *RT = T->getAs<ReferenceType>())
- T = Ctx.getPointerType(RT->getPointeeType());
-
- assert(ValMgr.getContext().hasSameUnqualifiedType(castTy, T));
-#endif
-
+ if (performTestOnly) {
+ // Automatically translate references to pointers.
+ QualType T = R->getValueType(Ctx);
+ if (const ReferenceType *RT = T->getAs<ReferenceType>())
+ T = Ctx.getPointerType(RT->getPointeeType());
+
+ assert(ValMgr.getContext().hasSameUnqualifiedType(castTy, T));
+ return V;
+ }
+
+ if (const Loc *L = dyn_cast<Loc>(&V))
+ return ValMgr.getSValuator().EvalCastL(*L, castTy);
+ else if (const NonLoc *NL = dyn_cast<NonLoc>(&V))
+ return ValMgr.getSValuator().EvalCastNL(*NL, castTy);
+
return V;
}
diff --git a/test/Analysis/misc-ps-region-store.m b/test/Analysis/misc-ps-region-store.m
index df423ef..a88c26c 100644
--- a/test/Analysis/misc-ps-region-store.m
+++ b/test/Analysis/misc-ps-region-store.m
@@ -710,3 +710,23 @@
return test_return_struct_2_aux_rdar_7526777().x;
}
+//===----------------------------------------------------------------------===//
+// <rdar://problem/7527292> Assertion failed: (Op == BinaryOperator::Add ||
+// Op == BinaryOperator::Sub)
+// This test case previously triggered an assertion failure due to a discrepancy
+// been the loaded/stored value in the array
+//===----------------------------------------------------------------------===//
+
+_Bool OSAtomicCompareAndSwapPtrBarrier( void *__oldValue, void *__newValue, void * volatile *__theValue );
+
+void rdar_7527292() {
+ static id Cache7527292[32];
+ for (signed long idx = 0;
+ idx < 32;
+ idx++) {
+ id v = Cache7527292[idx];
+ if (v && OSAtomicCompareAndSwapPtrBarrier(v, ((void*)0), (void * volatile *)(Cache7527292 + idx))) {
+ }
+ }
+}
+