diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowAnalysisContext.h @@ -103,6 +103,10 @@ /// Returns a stable storage location for `E`. StorageLocation &getStableStorageLocation(const Expr &E); + StorageLocation &getUnknownStorageLocation(QualType Ty); + + bool isUnknownStorageLocation(const StorageLocation &Loc) const; + /// Assigns `Loc` as the storage location of `D`. /// /// Requirements: @@ -241,6 +245,8 @@ llvm::DenseMap NullPointerVals; + llvm::DenseMap UnknownStorageLocations; + Options Opts; // Flow conditions are tracked symbolically: each unique flow condition is diff --git a/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp b/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp --- a/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowAnalysisContext.cpp @@ -90,6 +90,35 @@ return Loc; } +StorageLocation & +DataflowAnalysisContext::getUnknownStorageLocation(QualType Ty) { + // FIXME: Deal with self-referential data structures correctly. + // e.g. `struct S { S& s; };` will currently cause an infinite loop in this + // function, I think. + auto Res = UnknownStorageLocations.try_emplace(Ty, nullptr); + if (Res.second) { + if (!Ty.isNull() && Ty->isRecordType()) { + llvm::DenseMap FieldLocs; + for (const FieldDecl *Field : getModeledFields(Ty)) + FieldLocs.insert({Field, &getUnknownStorageLocation( + Field->getType().getNonReferenceType())}); + Res.first->second = + &arena().create(Ty, std::move(FieldLocs)); + } else { + Res.first->second = &arena().create(Ty); + } + } + return *Res.first->second; +} + +bool DataflowAnalysisContext::isUnknownStorageLocation( + const StorageLocation &Loc) const { + auto Iter = UnknownStorageLocations.find(Loc.getType()); + if (Iter == UnknownStorageLocations.end()) + return false; + return Iter->second == &Loc; +} + PointerValue & DataflowAnalysisContext::getOrCreateNullPointerValue(QualType PointeeType) { auto CanonicalPointeeType = diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -161,6 +161,16 @@ return CurrentEnv.makeTopBoolValue(); } + if (auto *PrevPtr = dyn_cast(&Prev)) { + auto &CurPtr = cast(Current); + + if (&PrevPtr->getPointeeLoc() != &CurPtr.getPointeeLoc()) + // TODO: Widen properties + return CurrentEnv.create( + CurrentEnv.getDataflowAnalysisContext().getUnknownStorageLocation( + CurPtr.getPointeeLoc().getType())); + } + // FIXME: Add other built-in model widening. // Custom-model widening. @@ -658,6 +668,20 @@ void Environment::setValue(const StorageLocation &Loc, Value &Val) { assert(!isa(&Val) || &cast(&Val)->getLoc() == &Loc); + // TODO: Currently, if `Loc` is an unknown storage location, just bail out. + // But is this the right thing to do? + // Alternatives: + // - Assert that `Loc` is not an unknown storage location. But then that + // potentially puts the burden of testing on the caller. And what else would + // they do except not set the value? + // - Because the unknown storage location is conceptually a "top", it + // effectively refers to the set of _all_ possible storage locations. So, + // because we could be potentially setting the value of any storage, + // maybe we should blow away _all_ of the entries in `LocToVal`? Or at least + // those whose type is one that is compatible with `Loc` in the sense that + // it can refer to a value of type `Loc.getType()`? + if (getDataflowAnalysisContext().isUnknownStorageLocation(Loc)) + return; LocToVal[&Loc] = &Val; } @@ -686,6 +710,8 @@ } Value *Environment::getValue(const StorageLocation &Loc) const { + if (getDataflowAnalysisContext().isUnknownStorageLocation(Loc)) + return nullptr; return LocToVal.lookup(&Loc); } diff --git a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp --- a/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp +++ b/clang/unittests/Analysis/FlowSensitive/TransferTest.cpp @@ -3843,10 +3843,7 @@ } } )cc"; - // FIXME: Implement pointer value widening to make analysis converge. - ASSERT_THAT_ERROR( - checkDataflowWithNoopAnalysis(Code), - llvm::FailedWithMessage("maximum number of iterations reached")); + ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded()); } TEST(TransferTest, LoopDereferencingChangingRecordPointerConverges) { @@ -3868,10 +3865,7 @@ } } )cc"; - // FIXME: Implement pointer value widening to make analysis converge. - ASSERT_THAT_ERROR( - checkDataflowWithNoopAnalysis(Code), - llvm::FailedWithMessage("maximum number of iterations reached")); + ASSERT_THAT_ERROR(checkDataflowWithNoopAnalysis(Code), llvm::Succeeded()); } TEST(TransferTest, DoesNotCrashOnUnionThisExpr) {