ASDenysPetrov created this revision.
ASDenysPetrov added reviewers: NoQ, MaskRay, martong, steakhal.
ASDenysPetrov added a project: clang.
Herald added subscribers: manas, StephenFan, dkrupp, donat.nagy, Szelethus,
mikhail.ramalho, a.sidorin, rnkovacs, szepet, baloghadamsoftware, xazax.hun.
Herald added a project: All.
ASDenysPetrov requested review of this revision.
Herald added a subscriber: cfe-commits.
Change structures of storing bindings between Symbols and Equivalent Classes.
Add a Bitwidth characteristic as a common feature of integral Symbol to make
`(char)(int x)` and `(uchar)(int x)` treated under the same Equivalent Class.
The link **Symbol **- **Class **was direct and now it depends on the
effective(minimal) Bitwidth of the Symbol.
The link **Class **- **Symbol **stays as previously.
Some test cases are affected by regression for the sake of the next patch which
will fix it.
This patch does not introduce integral casts but prepares the field for the
core patch.
Repository:
rG LLVM Github Monorepo
https://reviews.llvm.org/D138319
Files:
clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
clang/test/Analysis/svalbuilder-casts.cpp
Index: clang/test/Analysis/svalbuilder-casts.cpp
===================================================================
--- clang/test/Analysis/svalbuilder-casts.cpp
+++ clang/test/Analysis/svalbuilder-casts.cpp
@@ -39,17 +39,17 @@
// These are not truncated to short as zero.
static_assert((short)1 != 0, "");
- clang_analyzer_eval(x == 1); // expected-warning{{FALSE}}
+ clang_analyzer_eval(x == 1); // expected-warning{{UNKNOWN}}
static_assert((short)-1 != 0, "");
- clang_analyzer_eval(x == -1); // expected-warning{{FALSE}}
+ clang_analyzer_eval(x == -1); // expected-warning{{UNKNOWN}}
static_assert((short)65537 != 0, "");
- clang_analyzer_eval(x == 65537); // expected-warning{{FALSE}}
+ clang_analyzer_eval(x == 65537); // expected-warning{{UNKNOWN}}
static_assert((short)-65537 != 0, "");
- clang_analyzer_eval(x == -65537); // expected-warning{{FALSE}}
+ clang_analyzer_eval(x == -65537); // expected-warning{{UNKNOWN}}
static_assert((short)131073 != 0, "");
- clang_analyzer_eval(x == 131073); // expected-warning{{FALSE}}
+ clang_analyzer_eval(x == 131073); // expected-warning{{UNKNOWN}}
static_assert((short)-131073 != 0, "");
- clang_analyzer_eval(x == -131073); // expected-warning{{FALSE}}
+ clang_analyzer_eval(x == -131073); // expected-warning{{UNKNOWN}}
// Check for implicit cast.
short s = y;
Index: clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
===================================================================
--- clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
+++ clang/lib/StaticAnalyzer/Core/RangeConstraintManager.cpp
@@ -13,6 +13,7 @@
#include "clang/Basic/JsonSupport.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/APSIntType.h"
+#include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramState.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ProgramStateTrait.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/RangedConstraintManager.h"
@@ -872,17 +873,18 @@
}
LLVM_DUMP_METHOD void RangeSet::dump() const { dump(llvm::errs()); }
-REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(SymbolSet, SymbolRef)
-
namespace {
class EquivalenceClass;
+using BitWidthType = uint32_t;
} // end anonymous namespace
-REGISTER_MAP_WITH_PROGRAMSTATE(ClassMap, SymbolRef, EquivalenceClass)
+REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(SymbolSet, SymbolRef)
+REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(ClassSet, EquivalenceClass)
+REGISTER_MAP_FACTORY_WITH_PROGRAMSTATE(ClassMap, BitWidthType, EquivalenceClass)
+
+REGISTER_MAP_WITH_PROGRAMSTATE(SymClassMap, SymbolRef, ClassMap)
REGISTER_MAP_WITH_PROGRAMSTATE(ClassMembers, EquivalenceClass, SymbolSet)
REGISTER_MAP_WITH_PROGRAMSTATE(ConstraintRange, EquivalenceClass, RangeSet)
-
-REGISTER_SET_FACTORY_WITH_PROGRAMSTATE(ClassSet, EquivalenceClass)
REGISTER_MAP_WITH_PROGRAMSTATE(DisequalityMap, EquivalenceClass, ClassSet)
namespace {
@@ -989,11 +991,10 @@
return getRepresentativeSymbol()->getType();
}
- EquivalenceClass() = delete;
+ EquivalenceClass() = default;
EquivalenceClass(const EquivalenceClass &) = default;
- EquivalenceClass &operator=(const EquivalenceClass &) = delete;
- EquivalenceClass(EquivalenceClass &&) = default;
- EquivalenceClass &operator=(EquivalenceClass &&) = delete;
+ EquivalenceClass(SymbolRef Sym) : ID(reinterpret_cast<uintptr_t>(Sym)) {}
+ EquivalenceClass &operator=(const EquivalenceClass &) = default;
bool operator==(const EquivalenceClass &Other) const {
return ID == Other.ID;
@@ -1010,9 +1011,6 @@
void Profile(llvm::FoldingSetNodeID &ID) const { Profile(ID, this->ID); }
private:
- /* implicit */ EquivalenceClass(SymbolRef Sym)
- : ID(reinterpret_cast<uintptr_t>(Sym)) {}
-
/// This function is intended to be used ONLY within the class.
/// The fact that ID is a pointer to a symbol is an implementation detail
/// and should stay that way.
@@ -1033,9 +1031,25 @@
EquivalenceClass First, EquivalenceClass Second);
/// This is a unique identifier of the class.
- uintptr_t ID;
+ uintptr_t ID = 0;
};
+using MinBitWidthAndSymbolRoot = std::pair<BitWidthType, SymbolRef>;
+static MinBitWidthAndSymbolRoot parseSymbolCast(ProgramStateRef State,
+ SymbolRef Sym) {
+ ASTContext &C = State->getStateManager().getContext();
+ const QualType Ty = Sym->getType();
+ BitWidthType MinBitWidth = C.getIntWidth(Ty);
+ while (const SymbolCast *SC = dyn_cast<SymbolCast>(Sym)) {
+ Sym = SC->getOperand();
+ const QualType Ty = Sym->getType();
+ const BitWidthType BitWidth = C.getIntWidth(Ty);
+ if (MinBitWidth > BitWidth)
+ MinBitWidth = BitWidth;
+ }
+ return {MinBitWidth, Sym};
+}
+
//===----------------------------------------------------------------------===//
// Constraint functions
//===----------------------------------------------------------------------===//
@@ -2039,7 +2053,22 @@
[[nodiscard]] ProgramStateRef assign(SymbolRef Sym, RangeSet NewConstraint) {
// All constraints are actually associated with equivalence classes, and
// that's what we are going to do first.
- State = assign(EquivalenceClass::find(State, Sym), NewConstraint);
+ ClassMap::Factory &CMF = State->get_context<ClassMap>();
+ MinBitWidthAndSymbolRoot MBWSR = parseSymbolCast(State, Sym);
+ const ClassMap *CMPtr = State->get<SymClassMap>(MBWSR.second);
+ const EquivalenceClass *ECPtr =
+ CMPtr ? CMPtr->lookup(MBWSR.first) : nullptr;
+ ClassMap CM = CMPtr ? *CMPtr : CMF.getEmptyMap();
+ EquivalenceClass EC;
+ if (!CMPtr || !ECPtr) {
+ EC = EquivalenceClass{Sym};
+ CM = CMF.add(CM, MBWSR.first, EC);
+ State = State->set<SymClassMap>(MBWSR.second, CM);
+ } else {
+ EC = *ECPtr;
+ }
+
+ State = assign(EC, NewConstraint);
if (!State)
return nullptr;
@@ -2229,9 +2258,11 @@
SymbolRef Sym) {
assert(State && "State should not be null");
assert(Sym && "Symbol should not be null");
+ MinBitWidthAndSymbolRoot MBWSR = parseSymbolCast(State, Sym);
// We store far from all Symbol -> Class mappings
- if (const EquivalenceClass *NontrivialClass = State->get<ClassMap>(Sym))
- return *NontrivialClass;
+ if (const ClassMap *CM = State->get<SymClassMap>(MBWSR.second))
+ if (const EquivalenceClass *EC = CM->lookup(MBWSR.first))
+ return *EC;
// This is a trivial class of Sym.
return Sym;
@@ -2328,8 +2359,7 @@
}
// 2. Get ALL equivalence-related maps
- ClassMapTy Classes = State->get<ClassMap>();
- ClassMapTy::Factory &CMF = State->get_context<ClassMap>();
+ ClassMap::Factory &CMF = State->get_context<ClassMap>();
ClassMembersTy Members = State->get<ClassMembers>();
ClassMembersTy::Factory &MF = State->get_context<ClassMembers>();
@@ -2342,10 +2372,22 @@
// 2. Merge members of the Other class into the current class.
SymbolSet NewClassMembers = MyMembers;
+
+ auto AccociateSymWithThisClass = [&](SymbolRef Sym) {
+ MinBitWidthAndSymbolRoot MBWSR = parseSymbolCast(State, Sym);
+ const ClassMap *CM = State->get<SymClassMap>(MBWSR.second);
+ ClassMap NewCM = CM ? *CM : CMF.getEmptyMap();
+ NewCM = CMF.add(NewCM, MBWSR.first, *this);
+ State = State->set<SymClassMap>(MBWSR.second, NewCM);
+ };
+
+ // This is the last time we see this class trivial.
+ if (isTrivial(State))
+ AccociateSymWithThisClass(getRepresentativeSymbol());
+
for (SymbolRef Sym : OtherMembers) {
NewClassMembers = F.add(NewClassMembers, Sym);
- // *this is now the class for all these new symbols.
- Classes = CMF.add(Classes, Sym, *this);
+ AccociateSymWithThisClass(Sym);
}
// 3. Adjust member mapping.
@@ -2388,7 +2430,6 @@
}
// 5. Update the state
- State = State->set<ClassMap>(Classes);
State = State->set<ClassMembers>(Members);
return State;
@@ -2546,10 +2587,12 @@
State = State->set<ClassMembers>(ClassMembersMap);
// Remove `Old`'s Sym->Class relation.
- ClassMapTy Classes = State->get<ClassMap>();
- ClassMapTy::Factory &CMF = State->get_context<ClassMap>();
- Classes = CMF.remove(Classes, Old);
- State = State->set<ClassMap>(Classes);
+ ClassMap::Factory &CMF = State->get_context<ClassMap>();
+ MinBitWidthAndSymbolRoot MBWSR = parseSymbolCast(State, Old);
+ if (const ClassMap *CM = State->get<SymClassMap>(MBWSR.second)) {
+ ClassMap NewCM = CMF.remove(*CM, MBWSR.first);
+ State = State->set<SymClassMap>(MBWSR.second, NewCM);
+ }
return State;
}
@@ -2809,16 +2852,16 @@
ConstraintRangeTy::Factory &ConstraintFactory =
State->get_context<ConstraintRange>();
- ClassMapTy Map = State->get<ClassMap>();
- ClassMapTy NewMap = Map;
- ClassMapTy::Factory &ClassFactory = State->get_context<ClassMap>();
+ SymClassMapTy SCM = State->get<SymClassMap>();
+ SymClassMapTy NewSCM = SCM;
+ SymClassMapTy::Factory &SCMFactory = State->get_context<SymClassMap>();
DisequalityMapTy Disequalities = State->get<DisequalityMap>();
DisequalityMapTy::Factory &DisequalityFactory =
State->get_context<DisequalityMap>();
ClassSet::Factory &ClassSetFactory = State->get_context<ClassSet>();
- bool ClassMapChanged = false;
+ bool SymClassMapChanged = false;
bool MembersMapChanged = false;
bool ConstraintMapChanged = false;
bool DisequalitiesChanged = false;
@@ -2867,14 +2910,16 @@
}
// 2. We don't need to track classes for dead symbols.
- for (std::pair<SymbolRef, EquivalenceClass> SymbolClassPair : Map) {
- SymbolRef Sym = SymbolClassPair.first;
-
- if (SymReaper.isDead(Sym)) {
- ClassMapChanged = true;
- NewMap = ClassFactory.remove(NewMap, Sym);
- }
- }
+ AnalyzerOptions &Opts = State->getAnalysisManager().getAnalyzerOptions();
+ if (!Opts.ShouldSupportSymbolicIntegerCasts)
+ for (std::pair<SymbolRef, ClassMap> SymbolClassPair : SCM) {
+ SymbolRef Sym = SymbolClassPair.first;
+
+ if (SymReaper.isDead(Sym)) {
+ SymClassMapChanged = true;
+ NewSCM = SCMFactory.remove(NewSCM, Sym);
+ }
+ };
// 3. Remove dead members from classes and remove dead non-trivial classes
// and their constraints.
@@ -2913,8 +2958,8 @@
// 4. Update the state with new maps.
//
// Here we try to be humble and update a map only if it really changed.
- if (ClassMapChanged)
- State = State->set<ClassMap>(NewMap);
+ if (SymClassMapChanged)
+ State = State->set<SymClassMap>(NewSCM);
if (MembersMapChanged)
State = State->set<ClassMembers>(NewClassMembersMap);
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
