aboutsummaryrefslogtreecommitdiff
path: root/contrib/llvm-project/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'contrib/llvm-project/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp')
-rw-r--r--contrib/llvm-project/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp744
1 files changed, 477 insertions, 267 deletions
diff --git a/contrib/llvm-project/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/contrib/llvm-project/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
index cc3992805cc7..3a91025df6e1 100644
--- a/contrib/llvm-project/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
+++ b/contrib/llvm-project/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp
@@ -20,6 +20,7 @@
#include "clang/Analysis/FlowSensitive/Value.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/ErrorHandling.h"
@@ -107,22 +108,44 @@ static Value *mergeDistinctValues(QualType Type, Value &Val1,
// if (o.has_value())
// x = o.value();
// ```
- auto *Expr1 = cast<BoolValue>(&Val1);
- auto *Expr2 = cast<BoolValue>(&Val2);
- auto &MergedVal = MergedEnv.makeAtomicBoolValue();
- MergedEnv.addToFlowCondition(MergedEnv.makeOr(
- MergedEnv.makeAnd(Env1.getFlowConditionToken(),
- MergedEnv.makeIff(MergedVal, *Expr1)),
- MergedEnv.makeAnd(Env2.getFlowConditionToken(),
- MergedEnv.makeIff(MergedVal, *Expr2))));
- return &MergedVal;
+ auto &Expr1 = cast<BoolValue>(Val1).formula();
+ auto &Expr2 = cast<BoolValue>(Val2).formula();
+ auto &A = MergedEnv.arena();
+ auto &MergedVal = A.makeAtomRef(A.makeAtom());
+ MergedEnv.addToFlowCondition(
+ A.makeOr(A.makeAnd(A.makeAtomRef(Env1.getFlowConditionToken()),
+ A.makeEquals(MergedVal, Expr1)),
+ A.makeAnd(A.makeAtomRef(Env2.getFlowConditionToken()),
+ A.makeEquals(MergedVal, Expr2))));
+ return &A.makeBoolValue(MergedVal);
+ }
+
+ Value *MergedVal = nullptr;
+ if (auto *StructVal1 = dyn_cast<StructValue>(&Val1)) {
+ [[maybe_unused]] auto *StructVal2 = cast<StructValue>(&Val2);
+
+ // Values to be merged are always associated with the same location in
+ // `LocToVal`. The location stored in `StructVal` should therefore also
+ // be the same.
+ assert(&StructVal1->getAggregateLoc() == &StructVal2->getAggregateLoc());
+
+ // `StructVal1` and `StructVal2` may have different properties associated
+ // with them. Create a new `StructValue` without any properties so that we
+ // soundly approximate both values. If a particular analysis needs to merge
+ // properties, it should do so in `DataflowAnalysis::merge()`.
+ MergedVal = &MergedEnv.create<StructValue>(StructVal1->getAggregateLoc());
+ } else {
+ MergedVal = MergedEnv.createValue(Type);
}
// FIXME: Consider destroying `MergedValue` immediately if `ValueModel::merge`
// returns false to avoid storing unneeded values in `DACtx`.
// FIXME: Creating the value based on the type alone creates misshapen values
// for lvalues, since the type does not reflect the need for `ReferenceValue`.
- if (Value *MergedVal = MergedEnv.createValue(Type))
+ // This issue will be resolved when `ReferenceValue` is eliminated as part
+ // of the ongoing migration to strict handling of value categories (see
+ // https://discourse.llvm.org/t/70086 for details).
+ if (MergedVal)
if (Model.merge(Type, Val1, Env1, Val2, Env2, *MergedVal, MergedEnv))
return MergedVal;
@@ -156,17 +179,24 @@ static Value &widenDistinctValues(QualType Type, Value &Prev,
/// Initializes a global storage value.
static void insertIfGlobal(const Decl &D,
- llvm::DenseSet<const FieldDecl *> &Fields,
llvm::DenseSet<const VarDecl *> &Vars) {
if (auto *V = dyn_cast<VarDecl>(&D))
if (V->hasGlobalStorage())
Vars.insert(V);
}
-static void getFieldsAndGlobalVars(const Decl &D,
- llvm::DenseSet<const FieldDecl *> &Fields,
- llvm::DenseSet<const VarDecl *> &Vars) {
- insertIfGlobal(D, Fields, Vars);
+static void insertIfFunction(const Decl &D,
+ llvm::DenseSet<const FunctionDecl *> &Funcs) {
+ if (auto *FD = dyn_cast<FunctionDecl>(&D))
+ Funcs.insert(FD);
+}
+
+static void
+getFieldsGlobalsAndFuncs(const Decl &D, FieldSet &Fields,
+ llvm::DenseSet<const VarDecl *> &Vars,
+ llvm::DenseSet<const FunctionDecl *> &Funcs) {
+ insertIfGlobal(D, Vars);
+ insertIfFunction(D, Funcs);
if (const auto *Decomp = dyn_cast<DecompositionDecl>(&D))
for (const auto *B : Decomp->bindings())
if (auto *ME = dyn_cast_or_null<MemberExpr>(B->getBinding()))
@@ -175,60 +205,99 @@ static void getFieldsAndGlobalVars(const Decl &D,
Fields.insert(FD);
}
-/// Traverses `S` and inserts into `Vars` any global storage values that are
-/// declared in or referenced from sub-statements.
-static void getFieldsAndGlobalVars(const Stmt &S,
- llvm::DenseSet<const FieldDecl *> &Fields,
- llvm::DenseSet<const VarDecl *> &Vars) {
+/// Traverses `S` and inserts into `Fields`, `Vars` and `Funcs` any fields,
+/// global variables and functions that are declared in or referenced from
+/// sub-statements.
+static void
+getFieldsGlobalsAndFuncs(const Stmt &S, FieldSet &Fields,
+ llvm::DenseSet<const VarDecl *> &Vars,
+ llvm::DenseSet<const FunctionDecl *> &Funcs) {
for (auto *Child : S.children())
if (Child != nullptr)
- getFieldsAndGlobalVars(*Child, Fields, Vars);
+ getFieldsGlobalsAndFuncs(*Child, Fields, Vars, Funcs);
+ if (const auto *DefaultInit = dyn_cast<CXXDefaultInitExpr>(&S))
+ getFieldsGlobalsAndFuncs(*DefaultInit->getExpr(), Fields, Vars, Funcs);
if (auto *DS = dyn_cast<DeclStmt>(&S)) {
if (DS->isSingleDecl())
- getFieldsAndGlobalVars(*DS->getSingleDecl(), Fields, Vars);
+ getFieldsGlobalsAndFuncs(*DS->getSingleDecl(), Fields, Vars, Funcs);
else
for (auto *D : DS->getDeclGroup())
- getFieldsAndGlobalVars(*D, Fields, Vars);
+ getFieldsGlobalsAndFuncs(*D, Fields, Vars, Funcs);
} else if (auto *E = dyn_cast<DeclRefExpr>(&S)) {
- insertIfGlobal(*E->getDecl(), Fields, Vars);
+ insertIfGlobal(*E->getDecl(), Vars);
+ insertIfFunction(*E->getDecl(), Funcs);
} else if (auto *E = dyn_cast<MemberExpr>(&S)) {
// FIXME: should we be using `E->getFoundDecl()`?
const ValueDecl *VD = E->getMemberDecl();
- insertIfGlobal(*VD, Fields, Vars);
+ insertIfGlobal(*VD, Vars);
+ insertIfFunction(*VD, Funcs);
if (const auto *FD = dyn_cast<FieldDecl>(VD))
Fields.insert(FD);
+ } else if (auto *InitList = dyn_cast<InitListExpr>(&S)) {
+ if (RecordDecl *RD = InitList->getType()->getAsRecordDecl())
+ for (const auto *FD : getFieldsForInitListExpr(RD))
+ Fields.insert(FD);
}
}
// FIXME: Add support for resetting globals after function calls to enable
// the implementation of sound analyses.
-void Environment::initVars(llvm::DenseSet<const VarDecl *> Vars) {
+void Environment::initFieldsGlobalsAndFuncs(const FunctionDecl *FuncDecl) {
+ assert(FuncDecl->getBody() != nullptr);
+
+ FieldSet Fields;
+ llvm::DenseSet<const VarDecl *> Vars;
+ llvm::DenseSet<const FunctionDecl *> Funcs;
+
+ // Look for global variable and field references in the
+ // constructor-initializers.
+ if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(FuncDecl)) {
+ for (const auto *Init : CtorDecl->inits()) {
+ if (Init->isMemberInitializer()) {
+ Fields.insert(Init->getMember());
+ } else if (Init->isIndirectMemberInitializer()) {
+ for (const auto *I : Init->getIndirectMember()->chain())
+ Fields.insert(cast<FieldDecl>(I));
+ }
+ const Expr *E = Init->getInit();
+ assert(E != nullptr);
+ getFieldsGlobalsAndFuncs(*E, Fields, Vars, Funcs);
+ }
+ // Add all fields mentioned in default member initializers.
+ for (const FieldDecl *F : CtorDecl->getParent()->fields())
+ if (const auto *I = F->getInClassInitializer())
+ getFieldsGlobalsAndFuncs(*I, Fields, Vars, Funcs);
+ }
+ getFieldsGlobalsAndFuncs(*FuncDecl->getBody(), Fields, Vars, Funcs);
+
+ // These have to be added before the lines that follow to ensure that
+ // `create*` work correctly for structs.
+ DACtx->addModeledFields(Fields);
+
for (const VarDecl *D : Vars) {
- if (getStorageLocation(*D, SkipPast::None) != nullptr)
+ if (getStorageLocation(*D) != nullptr)
continue;
- auto &Loc = createStorageLocation(*D);
- setStorageLocation(*D, Loc);
- if (auto *Val = createValue(D->getType()))
- setValue(Loc, *Val);
+
+ setStorageLocation(*D, createObject(*D));
+ }
+
+ for (const FunctionDecl *FD : Funcs) {
+ if (getStorageLocation(*FD) != nullptr)
+ continue;
+ auto &Loc = createStorageLocation(FD->getType());
+ setStorageLocation(*FD, Loc);
}
}
Environment::Environment(DataflowAnalysisContext &DACtx)
- : DACtx(&DACtx), FlowConditionToken(&DACtx.makeFlowConditionToken()) {}
-
-Environment::Environment(const Environment &Other)
- : DACtx(Other.DACtx), CallStack(Other.CallStack),
- ReturnLoc(Other.ReturnLoc), ThisPointeeLoc(Other.ThisPointeeLoc),
- DeclToLoc(Other.DeclToLoc), ExprToLoc(Other.ExprToLoc),
- LocToVal(Other.LocToVal), MemberLocToStruct(Other.MemberLocToStruct),
- FlowConditionToken(&DACtx->forkFlowCondition(*Other.FlowConditionToken)) {
-}
+ : DACtx(&DACtx),
+ FlowConditionToken(DACtx.arena().makeFlowConditionToken()) {}
-Environment &Environment::operator=(const Environment &Other) {
- Environment Copy(Other);
- *this = std::move(Copy);
- return *this;
+Environment Environment::fork() const {
+ Environment Copy(*this);
+ Copy.FlowConditionToken = DACtx->forkFlowCondition(FlowConditionToken);
+ return Copy;
}
Environment::Environment(DataflowAnalysisContext &DACtx,
@@ -239,37 +308,12 @@ Environment::Environment(DataflowAnalysisContext &DACtx,
if (const auto *FuncDecl = dyn_cast<FunctionDecl>(&DeclCtx)) {
assert(FuncDecl->getBody() != nullptr);
- llvm::DenseSet<const FieldDecl *> Fields;
- llvm::DenseSet<const VarDecl *> Vars;
-
- // Look for global variable references in the constructor-initializers.
- if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(&DeclCtx)) {
- for (const auto *Init : CtorDecl->inits()) {
- if (const auto *M = Init->getAnyMember())
- Fields.insert(M);
- const Expr *E = Init->getInit();
- assert(E != nullptr);
- getFieldsAndGlobalVars(*E, Fields, Vars);
- }
- }
- getFieldsAndGlobalVars(*FuncDecl->getBody(), Fields, Vars);
-
- // These have to be added before the lines that follow to ensure that
- // `create*` work correctly for structs.
- DACtx.addModeledFields(Fields);
-
- initVars(Vars);
+ initFieldsGlobalsAndFuncs(FuncDecl);
for (const auto *ParamDecl : FuncDecl->parameters()) {
assert(ParamDecl != nullptr);
- auto &ParamLoc = createStorageLocation(*ParamDecl);
- setStorageLocation(*ParamDecl, ParamLoc);
- if (Value *ParamVal = createValue(ParamDecl->getType()))
- setValue(ParamLoc, *ParamVal);
+ setStorageLocation(*ParamDecl, createObject(*ParamDecl, nullptr));
}
-
- QualType ReturnType = FuncDecl->getReturnType();
- ReturnLoc = &createStorageLocation(ReturnType);
}
if (const auto *MethodDecl = dyn_cast<CXXMethodDecl>(&DeclCtx)) {
@@ -281,9 +325,8 @@ Environment::Environment(DataflowAnalysisContext &DACtx,
// FIXME: Initialize the ThisPointeeLoc of lambdas too.
if (MethodDecl && !MethodDecl->isStatic()) {
QualType ThisPointeeType = MethodDecl->getThisObjectType();
- ThisPointeeLoc = &createStorageLocation(ThisPointeeType);
- if (Value *ThisPointeeVal = createValue(ThisPointeeType))
- setValue(*ThisPointeeLoc, *ThisPointeeVal);
+ ThisPointeeLoc =
+ &cast<StructValue>(createValue(ThisPointeeType))->getAggregateLoc();
}
}
}
@@ -296,13 +339,11 @@ bool Environment::canDescend(unsigned MaxDepth,
Environment Environment::pushCall(const CallExpr *Call) const {
Environment Env(*this);
- // FIXME: Support references here.
- Env.ReturnLoc = getStorageLocation(*Call, SkipPast::Reference);
-
if (const auto *MethodCall = dyn_cast<CXXMemberCallExpr>(Call)) {
if (const Expr *Arg = MethodCall->getImplicitObjectArgument()) {
if (!isa<CXXThisExpr>(Arg))
- Env.ThisPointeeLoc = getStorageLocation(*Arg, SkipPast::Reference);
+ Env.ThisPointeeLoc = cast<AggregateStorageLocation>(
+ getStorageLocation(*Arg, SkipPast::Reference));
// Otherwise (when the argument is `this`), retain the current
// environment's `ThisPointeeLoc`.
}
@@ -317,10 +358,7 @@ Environment Environment::pushCall(const CallExpr *Call) const {
Environment Environment::pushCall(const CXXConstructExpr *Call) const {
Environment Env(*this);
- // FIXME: Support references here.
- Env.ReturnLoc = getStorageLocation(*Call, SkipPast::Reference);
-
- Env.ThisPointeeLoc = Env.ReturnLoc;
+ Env.ThisPointeeLoc = &Env.getResultObjectLocation(*Call);
Env.pushCallInternal(Call->getConstructor(),
llvm::ArrayRef(Call->getArgs(), Call->getNumArgs()));
@@ -330,28 +368,15 @@ Environment Environment::pushCall(const CXXConstructExpr *Call) const {
void Environment::pushCallInternal(const FunctionDecl *FuncDecl,
ArrayRef<const Expr *> Args) {
- CallStack.push_back(FuncDecl);
+ // Canonicalize to the definition of the function. This ensures that we're
+ // putting arguments into the same `ParamVarDecl`s` that the callee will later
+ // be retrieving them from.
+ assert(FuncDecl->getDefinition() != nullptr);
+ FuncDecl = FuncDecl->getDefinition();
- // FIXME: Share this code with the constructor, rather than duplicating it.
- llvm::DenseSet<const FieldDecl *> Fields;
- llvm::DenseSet<const VarDecl *> Vars;
- // Look for global variable references in the constructor-initializers.
- if (const auto *CtorDecl = dyn_cast<CXXConstructorDecl>(FuncDecl)) {
- for (const auto *Init : CtorDecl->inits()) {
- if (const auto *M = Init->getAnyMember())
- Fields.insert(M);
- const Expr *E = Init->getInit();
- assert(E != nullptr);
- getFieldsAndGlobalVars(*E, Fields, Vars);
- }
- }
- getFieldsAndGlobalVars(*FuncDecl->getBody(), Fields, Vars);
-
- // These have to be added before the lines that follow to ensure that
- // `create*` work correctly for structs.
- DACtx->addModeledFields(Fields);
+ CallStack.push_back(FuncDecl);
- initVars(Vars);
+ initFieldsGlobalsAndFuncs(FuncDecl);
const auto *ParamIt = FuncDecl->param_begin();
@@ -359,45 +384,49 @@ void Environment::pushCallInternal(const FunctionDecl *FuncDecl,
// overloaded operators implemented as member functions, and parameter packs.
for (unsigned ArgIndex = 0; ArgIndex < Args.size(); ++ParamIt, ++ArgIndex) {
assert(ParamIt != FuncDecl->param_end());
-
- const Expr *Arg = Args[ArgIndex];
- auto *ArgLoc = getStorageLocation(*Arg, SkipPast::Reference);
- if (ArgLoc == nullptr)
- continue;
-
const VarDecl *Param = *ParamIt;
- auto &Loc = createStorageLocation(*Param);
- setStorageLocation(*Param, Loc);
-
- QualType ParamType = Param->getType();
- if (ParamType->isReferenceType()) {
- auto &Val = takeOwnership(std::make_unique<ReferenceValue>(*ArgLoc));
- setValue(Loc, Val);
- } else if (auto *ArgVal = getValue(*ArgLoc)) {
- setValue(Loc, *ArgVal);
- } else if (Value *Val = createValue(ParamType)) {
- setValue(Loc, *Val);
- }
+ setStorageLocation(*Param, createObject(*Param, Args[ArgIndex]));
}
}
-void Environment::popCall(const Environment &CalleeEnv) {
+void Environment::popCall(const CallExpr *Call, const Environment &CalleeEnv) {
// We ignore `DACtx` because it's already the same in both. We don't want the
- // callee's `DeclCtx`, `ReturnLoc` or `ThisPointeeLoc`. We don't bring back
- // `DeclToLoc` and `ExprToLoc` because we want to be able to later analyze the
- // same callee in a different context, and `setStorageLocation` requires there
- // to not already be a storage location assigned. Conceptually, these maps
- // capture information from the local scope, so when popping that scope, we do
- // not propagate the maps.
+ // callee's `DeclCtx`, `ReturnVal`, `ReturnLoc` or `ThisPointeeLoc`. We don't
+ // bring back `DeclToLoc` and `ExprToLoc` because we want to be able to later
+ // analyze the same callee in a different context, and `setStorageLocation`
+ // requires there to not already be a storage location assigned. Conceptually,
+ // these maps capture information from the local scope, so when popping that
+ // scope, we do not propagate the maps.
this->LocToVal = std::move(CalleeEnv.LocToVal);
- this->MemberLocToStruct = std::move(CalleeEnv.MemberLocToStruct);
this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
+
+ if (Call->isGLValue()) {
+ if (CalleeEnv.ReturnLoc != nullptr)
+ setStorageLocationStrict(*Call, *CalleeEnv.ReturnLoc);
+ } else if (!Call->getType()->isVoidType()) {
+ if (CalleeEnv.ReturnVal != nullptr)
+ setValueStrict(*Call, *CalleeEnv.ReturnVal);
+ }
+}
+
+void Environment::popCall(const CXXConstructExpr *Call,
+ const Environment &CalleeEnv) {
+ // See also comment in `popCall(const CallExpr *, const Environment &)` above.
+ this->LocToVal = std::move(CalleeEnv.LocToVal);
+ this->FlowConditionToken = std::move(CalleeEnv.FlowConditionToken);
+
+ if (Value *Val = CalleeEnv.getValue(*CalleeEnv.ThisPointeeLoc)) {
+ setValueStrict(*Call, *Val);
+ }
}
bool Environment::equivalentTo(const Environment &Other,
Environment::ValueModel &Model) const {
assert(DACtx == Other.DACtx);
+ if (ReturnVal != Other.ReturnVal)
+ return false;
+
if (ReturnLoc != Other.ReturnLoc)
return false;
@@ -435,6 +464,7 @@ bool Environment::equivalentTo(const Environment &Other,
LatticeJoinEffect Environment::widen(const Environment &PrevEnv,
Environment::ValueModel &Model) {
assert(DACtx == PrevEnv.DACtx);
+ assert(ReturnVal == PrevEnv.ReturnVal);
assert(ReturnLoc == PrevEnv.ReturnLoc);
assert(ThisPointeeLoc == PrevEnv.ThisPointeeLoc);
assert(CallStack == PrevEnv.CallStack);
@@ -447,17 +477,10 @@ LatticeJoinEffect Environment::widen(const Environment &PrevEnv,
// block. For `DeclToLoc` and `ExprToLoc`, join guarantees that these maps are
// subsets of the maps in `PrevEnv`. So, as long as we maintain this property
// here, we don't need change their current values to widen.
- //
- // FIXME: `MemberLocToStruct` does not share the above property, because
- // `join` can cause the map size to increase (when we add fresh data in places
- // of conflict). Once this issue with join is resolved, re-enable the
- // assertion below or replace with something that captures the desired
- // invariant.
assert(DeclToLoc.size() <= PrevEnv.DeclToLoc.size());
assert(ExprToLoc.size() <= PrevEnv.ExprToLoc.size());
- // assert(MemberLocToStruct.size() <= PrevEnv.MemberLocToStruct.size());
- llvm::DenseMap<const StorageLocation *, Value *> WidenedLocToVal;
+ llvm::MapVector<const StorageLocation *, Value *> WidenedLocToVal;
for (auto &Entry : LocToVal) {
const StorageLocation *Loc = Entry.first;
assert(Loc != nullptr);
@@ -482,60 +505,75 @@ LatticeJoinEffect Environment::widen(const Environment &PrevEnv,
Effect = LatticeJoinEffect::Changed;
}
LocToVal = std::move(WidenedLocToVal);
- // FIXME: update the equivalence calculation for `MemberLocToStruct`, once we
- // have a systematic way of soundly comparing this map.
if (DeclToLoc.size() != PrevEnv.DeclToLoc.size() ||
ExprToLoc.size() != PrevEnv.ExprToLoc.size() ||
- LocToVal.size() != PrevEnv.LocToVal.size() ||
- MemberLocToStruct.size() != PrevEnv.MemberLocToStruct.size())
+ LocToVal.size() != PrevEnv.LocToVal.size())
Effect = LatticeJoinEffect::Changed;
return Effect;
}
-LatticeJoinEffect Environment::join(const Environment &Other,
- Environment::ValueModel &Model) {
- assert(DACtx == Other.DACtx);
- assert(ReturnLoc == Other.ReturnLoc);
- assert(ThisPointeeLoc == Other.ThisPointeeLoc);
- assert(CallStack == Other.CallStack);
-
- auto Effect = LatticeJoinEffect::Unchanged;
-
- Environment JoinedEnv(*DACtx);
+Environment Environment::join(const Environment &EnvA, const Environment &EnvB,
+ Environment::ValueModel &Model) {
+ assert(EnvA.DACtx == EnvB.DACtx);
+ assert(EnvA.ThisPointeeLoc == EnvB.ThisPointeeLoc);
+ assert(EnvA.CallStack == EnvB.CallStack);
+
+ Environment JoinedEnv(*EnvA.DACtx);
+
+ JoinedEnv.CallStack = EnvA.CallStack;
+ JoinedEnv.ThisPointeeLoc = EnvA.ThisPointeeLoc;
+
+ if (EnvA.ReturnVal == nullptr || EnvB.ReturnVal == nullptr) {
+ // `ReturnVal` might not always get set -- for example if we have a return
+ // statement of the form `return some_other_func()` and we decide not to
+ // analyze `some_other_func()`.
+ // In this case, we can't say anything about the joined return value -- we
+ // don't simply want to propagate the return value that we do have, because
+ // it might not be the correct one.
+ // This occurs for example in the test `ContextSensitiveMutualRecursion`.
+ JoinedEnv.ReturnVal = nullptr;
+ } else if (areEquivalentValues(*EnvA.ReturnVal, *EnvB.ReturnVal)) {
+ JoinedEnv.ReturnVal = EnvA.ReturnVal;
+ } else {
+ assert(!EnvA.CallStack.empty());
+ // FIXME: Make `CallStack` a vector of `FunctionDecl` so we don't need this
+ // cast.
+ auto *Func = dyn_cast<FunctionDecl>(EnvA.CallStack.back());
+ assert(Func != nullptr);
+ if (Value *MergedVal =
+ mergeDistinctValues(Func->getReturnType(), *EnvA.ReturnVal, EnvA,
+ *EnvB.ReturnVal, EnvB, JoinedEnv, Model))
+ JoinedEnv.ReturnVal = MergedVal;
+ }
- JoinedEnv.CallStack = CallStack;
- JoinedEnv.ReturnLoc = ReturnLoc;
- JoinedEnv.ThisPointeeLoc = ThisPointeeLoc;
+ if (EnvA.ReturnLoc == EnvB.ReturnLoc)
+ JoinedEnv.ReturnLoc = EnvA.ReturnLoc;
+ else
+ JoinedEnv.ReturnLoc = nullptr;
- JoinedEnv.DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc);
- if (DeclToLoc.size() != JoinedEnv.DeclToLoc.size())
- Effect = LatticeJoinEffect::Changed;
+ // FIXME: Once we're able to remove declarations from `DeclToLoc` when their
+ // lifetime ends, add an assertion that there aren't any entries in
+ // `DeclToLoc` and `Other.DeclToLoc` that map the same declaration to
+ // different storage locations.
+ JoinedEnv.DeclToLoc = intersectDenseMaps(EnvA.DeclToLoc, EnvB.DeclToLoc);
- JoinedEnv.ExprToLoc = intersectDenseMaps(ExprToLoc, Other.ExprToLoc);
- if (ExprToLoc.size() != JoinedEnv.ExprToLoc.size())
- Effect = LatticeJoinEffect::Changed;
+ JoinedEnv.ExprToLoc = intersectDenseMaps(EnvA.ExprToLoc, EnvB.ExprToLoc);
- JoinedEnv.MemberLocToStruct =
- intersectDenseMaps(MemberLocToStruct, Other.MemberLocToStruct);
- if (MemberLocToStruct.size() != JoinedEnv.MemberLocToStruct.size())
- Effect = LatticeJoinEffect::Changed;
-
- // FIXME: set `Effect` as needed.
// FIXME: update join to detect backedges and simplify the flow condition
// accordingly.
- JoinedEnv.FlowConditionToken = &DACtx->joinFlowConditions(
- *FlowConditionToken, *Other.FlowConditionToken);
+ JoinedEnv.FlowConditionToken = EnvA.DACtx->joinFlowConditions(
+ EnvA.FlowConditionToken, EnvB.FlowConditionToken);
- for (auto &Entry : LocToVal) {
+ for (auto &Entry : EnvA.LocToVal) {
const StorageLocation *Loc = Entry.first;
assert(Loc != nullptr);
Value *Val = Entry.second;
assert(Val != nullptr);
- auto It = Other.LocToVal.find(Loc);
- if (It == Other.LocToVal.end())
+ auto It = EnvB.LocToVal.find(Loc);
+ if (It == EnvB.LocToVal.end())
continue;
assert(It->second != nullptr);
@@ -544,19 +582,13 @@ LatticeJoinEffect Environment::join(const Environment &Other,
continue;
}
- if (Value *MergedVal =
- mergeDistinctValues(Loc->getType(), *Val, *this, *It->second, Other,
- JoinedEnv, Model)) {
+ if (Value *MergedVal = mergeDistinctValues(
+ Loc->getType(), *Val, EnvA, *It->second, EnvB, JoinedEnv, Model)) {
JoinedEnv.LocToVal.insert({Loc, MergedVal});
- Effect = LatticeJoinEffect::Changed;
}
}
- if (LocToVal.size() != JoinedEnv.LocToVal.size())
- Effect = LatticeJoinEffect::Changed;
- *this = std::move(JoinedEnv);
-
- return Effect;
+ return JoinedEnv;
}
StorageLocation &Environment::createStorageLocation(QualType Type) {
@@ -578,22 +610,39 @@ StorageLocation &Environment::createStorageLocation(const Expr &E) {
}
void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) {
- assert(DeclToLoc.find(&D) == DeclToLoc.end());
+ assert(!DeclToLoc.contains(&D));
+ assert(!isa_and_nonnull<ReferenceValue>(getValue(Loc)));
DeclToLoc[&D] = &Loc;
}
-StorageLocation *Environment::getStorageLocation(const ValueDecl &D,
- SkipPast SP) const {
+StorageLocation *Environment::getStorageLocation(const ValueDecl &D) const {
auto It = DeclToLoc.find(&D);
- return It == DeclToLoc.end() ? nullptr : &skip(*It->second, SP);
+ if (It == DeclToLoc.end())
+ return nullptr;
+
+ StorageLocation *Loc = It->second;
+
+ assert(!isa_and_nonnull<ReferenceValue>(getValue(*Loc)));
+
+ return Loc;
}
void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) {
const Expr &CanonE = ignoreCFGOmittedNodes(E);
- assert(ExprToLoc.find(&CanonE) == ExprToLoc.end());
+ assert(!ExprToLoc.contains(&CanonE));
ExprToLoc[&CanonE] = &Loc;
}
+void Environment::setStorageLocationStrict(const Expr &E,
+ StorageLocation &Loc) {
+ // `DeclRefExpr`s to builtin function types aren't glvalues, for some reason,
+ // but we still want to be able to associate a `StorageLocation` with them,
+ // so allow these as an exception.
+ assert(E.isGLValue() ||
+ E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
+ setStorageLocation(E, Loc);
+}
+
StorageLocation *Environment::getStorageLocation(const Expr &E,
SkipPast SP) const {
// FIXME: Add a test with parens.
@@ -601,12 +650,37 @@ StorageLocation *Environment::getStorageLocation(const Expr &E,
return It == ExprToLoc.end() ? nullptr : &skip(*It->second, SP);
}
-StorageLocation *Environment::getThisPointeeStorageLocation() const {
+StorageLocation *Environment::getStorageLocationStrict(const Expr &E) const {
+ // See comment in `setStorageLocationStrict()`.
+ assert(E.isGLValue() ||
+ E.getType()->isSpecificBuiltinType(BuiltinType::BuiltinFn));
+ StorageLocation *Loc = getStorageLocation(E, SkipPast::None);
+
+ if (Loc == nullptr)
+ return nullptr;
+
+ if (auto *RefVal = dyn_cast_or_null<ReferenceValue>(getValue(*Loc)))
+ return &RefVal->getReferentLoc();
+
+ return Loc;
+}
+
+AggregateStorageLocation *Environment::getThisPointeeStorageLocation() const {
return ThisPointeeLoc;
}
-StorageLocation *Environment::getReturnStorageLocation() const {
- return ReturnLoc;
+AggregateStorageLocation &
+Environment::getResultObjectLocation(const Expr &RecordPRValue) {
+ assert(RecordPRValue.getType()->isRecordType());
+ assert(RecordPRValue.isPRValue());
+
+ if (StorageLocation *ExistingLoc =
+ getStorageLocation(RecordPRValue, SkipPast::None))
+ return *cast<AggregateStorageLocation>(ExistingLoc);
+ auto &Loc = cast<AggregateStorageLocation>(
+ DACtx->getStableStorageLocation(RecordPRValue));
+ setStorageLocation(RecordPRValue, Loc);
+ return Loc;
}
PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) {
@@ -614,45 +688,41 @@ PointerValue &Environment::getOrCreateNullPointerValue(QualType PointeeType) {
}
void Environment::setValue(const StorageLocation &Loc, Value &Val) {
- LocToVal[&Loc] = &Val;
+ assert(!isa<StructValue>(&Val) ||
+ &cast<StructValue>(&Val)->getAggregateLoc() == &Loc);
- if (auto *StructVal = dyn_cast<StructValue>(&Val)) {
- auto &AggregateLoc = *cast<AggregateStorageLocation>(&Loc);
+ LocToVal[&Loc] = &Val;
+}
- const QualType Type = AggregateLoc.getType();
- assert(Type->isStructureOrClassType() || Type->isUnionType());
+void Environment::setValueStrict(const Expr &E, Value &Val) {
+ assert(E.isPRValue());
+ assert(!isa<ReferenceValue>(Val));
- for (const FieldDecl *Field : DACtx->getReferencedFields(Type)) {
- assert(Field != nullptr);
- StorageLocation &FieldLoc = AggregateLoc.getChild(*Field);
- MemberLocToStruct[&FieldLoc] = std::make_pair(StructVal, Field);
- if (auto *FieldVal = StructVal->getChild(*Field))
- setValue(FieldLoc, *FieldVal);
- }
+ if (auto *StructVal = dyn_cast<StructValue>(&Val)) {
+ if (auto *ExistingVal = cast_or_null<StructValue>(getValueStrict(E)))
+ assert(&ExistingVal->getAggregateLoc() == &StructVal->getAggregateLoc());
+ if (StorageLocation *ExistingLoc = getStorageLocation(E, SkipPast::None))
+ assert(ExistingLoc == &StructVal->getAggregateLoc());
+ else
+ setStorageLocation(E, StructVal->getAggregateLoc());
+ setValue(StructVal->getAggregateLoc(), Val);
+ return;
}
- auto It = MemberLocToStruct.find(&Loc);
- if (It != MemberLocToStruct.end()) {
- // `Loc` is the location of a struct member so we need to also update the
- // value of the member in the corresponding `StructValue`.
-
- assert(It->second.first != nullptr);
- StructValue &StructVal = *It->second.first;
-
- assert(It->second.second != nullptr);
- const ValueDecl &Member = *It->second.second;
-
- StructVal.setChild(Member, Val);
+ StorageLocation *Loc = getStorageLocation(E, SkipPast::None);
+ if (Loc == nullptr) {
+ Loc = &createStorageLocation(E);
+ setStorageLocation(E, *Loc);
}
+ setValue(*Loc, Val);
}
Value *Environment::getValue(const StorageLocation &Loc) const {
- auto It = LocToVal.find(&Loc);
- return It == LocToVal.end() ? nullptr : It->second;
+ return LocToVal.lookup(&Loc);
}
-Value *Environment::getValue(const ValueDecl &D, SkipPast SP) const {
- auto *Loc = getStorageLocation(D, SP);
+Value *Environment::getValue(const ValueDecl &D) const {
+ auto *Loc = getStorageLocation(D);
if (Loc == nullptr)
return nullptr;
return getValue(*Loc);
@@ -665,6 +735,15 @@ Value *Environment::getValue(const Expr &E, SkipPast SP) const {
return getValue(*Loc);
}
+Value *Environment::getValueStrict(const Expr &E) const {
+ assert(E.isPRValue());
+ Value *Val = getValue(E, SkipPast::None);
+
+ assert(Val == nullptr || !isa<ReferenceValue>(Val));
+
+ return Val;
+}
+
Value *Environment::createValue(QualType Type) {
llvm::DenseSet<QualType> Visited;
int CreatedValuesCount = 0;
@@ -697,65 +776,120 @@ Value *Environment::createValueUnlessSelfReferential(
// with integers, and so distinguishing them serves no purpose, but could
// prevent convergence.
CreatedValuesCount++;
- return &takeOwnership(std::make_unique<IntegerValue>());
+ return &arena().create<IntegerValue>();
}
- if (Type->isReferenceType()) {
+ if (Type->isReferenceType() || Type->isPointerType()) {
CreatedValuesCount++;
- QualType PointeeType = Type->castAs<ReferenceType>()->getPointeeType();
- auto &PointeeLoc = createStorageLocation(PointeeType);
+ QualType PointeeType = Type->getPointeeType();
+ StorageLocation &PointeeLoc =
+ createLocAndMaybeValue(PointeeType, Visited, Depth, CreatedValuesCount);
- if (Visited.insert(PointeeType.getCanonicalType()).second) {
- Value *PointeeVal = createValueUnlessSelfReferential(
- PointeeType, Visited, Depth, CreatedValuesCount);
- Visited.erase(PointeeType.getCanonicalType());
-
- if (PointeeVal != nullptr)
- setValue(PointeeLoc, *PointeeVal);
- }
-
- return &takeOwnership(std::make_unique<ReferenceValue>(PointeeLoc));
+ if (Type->isReferenceType())
+ return &arena().create<ReferenceValue>(PointeeLoc);
+ else
+ return &arena().create<PointerValue>(PointeeLoc);
}
- if (Type->isPointerType()) {
+ if (Type->isRecordType()) {
CreatedValuesCount++;
- QualType PointeeType = Type->castAs<PointerType>()->getPointeeType();
- auto &PointeeLoc = createStorageLocation(PointeeType);
+ llvm::DenseMap<const ValueDecl *, StorageLocation *> FieldLocs;
+ for (const FieldDecl *Field : DACtx->getModeledFields(Type)) {
+ assert(Field != nullptr);
- if (Visited.insert(PointeeType.getCanonicalType()).second) {
- Value *PointeeVal = createValueUnlessSelfReferential(
- PointeeType, Visited, Depth, CreatedValuesCount);
- Visited.erase(PointeeType.getCanonicalType());
+ QualType FieldType = Field->getType();
- if (PointeeVal != nullptr)
- setValue(PointeeLoc, *PointeeVal);
+ FieldLocs.insert(
+ {Field, &createLocAndMaybeValue(FieldType, Visited, Depth + 1,
+ CreatedValuesCount)});
}
- return &takeOwnership(std::make_unique<PointerValue>(PointeeLoc));
+ AggregateStorageLocation &Loc =
+ arena().create<AggregateStorageLocation>(Type, std::move(FieldLocs));
+ StructValue &StructVal = create<StructValue>(Loc);
+
+ // As we already have a storage location for the `StructValue`, we can and
+ // should associate them in the environment.
+ setValue(Loc, StructVal);
+
+ return &StructVal;
}
- if (Type->isStructureOrClassType() || Type->isUnionType()) {
- CreatedValuesCount++;
- llvm::DenseMap<const ValueDecl *, Value *> FieldValues;
- for (const FieldDecl *Field : DACtx->getReferencedFields(Type)) {
- assert(Field != nullptr);
+ return nullptr;
+}
- QualType FieldType = Field->getType();
- if (Visited.contains(FieldType.getCanonicalType()))
- continue;
-
- Visited.insert(FieldType.getCanonicalType());
- if (auto *FieldValue = createValueUnlessSelfReferential(
- FieldType, Visited, Depth + 1, CreatedValuesCount))
- FieldValues.insert({Field, FieldValue});
- Visited.erase(FieldType.getCanonicalType());
+StorageLocation &
+Environment::createLocAndMaybeValue(QualType Ty,
+ llvm::DenseSet<QualType> &Visited,
+ int Depth, int &CreatedValuesCount) {
+ if (!Visited.insert(Ty.getCanonicalType()).second)
+ return createStorageLocation(Ty.getNonReferenceType());
+ Value *Val = createValueUnlessSelfReferential(
+ Ty.getNonReferenceType(), Visited, Depth, CreatedValuesCount);
+ Visited.erase(Ty.getCanonicalType());
+
+ Ty = Ty.getNonReferenceType();
+
+ if (Val == nullptr)
+ return createStorageLocation(Ty);
+
+ if (Ty->isRecordType())
+ return cast<StructValue>(Val)->getAggregateLoc();
+
+ StorageLocation &Loc = createStorageLocation(Ty);
+ setValue(Loc, *Val);
+ return Loc;
+}
+
+StorageLocation &Environment::createObjectInternal(const VarDecl *D,
+ QualType Ty,
+ const Expr *InitExpr) {
+ if (Ty->isReferenceType()) {
+ // Although variables of reference type always need to be initialized, it
+ // can happen that we can't see the initializer, so `InitExpr` may still
+ // be null.
+ if (InitExpr) {
+ if (auto *InitExprLoc =
+ getStorageLocation(*InitExpr, SkipPast::Reference))
+ return *InitExprLoc;
}
- return &takeOwnership(
- std::make_unique<StructValue>(std::move(FieldValues)));
+ // Even though we have an initializer, we might not get an
+ // InitExprLoc, for example if the InitExpr is a CallExpr for which we
+ // don't have a function body. In this case, we just invent a storage
+ // location and value -- it's the best we can do.
+ return createObjectInternal(D, Ty.getNonReferenceType(), nullptr);
}
- return nullptr;
+ Value *Val = nullptr;
+ if (InitExpr)
+ // In the (few) cases where an expression is intentionally
+ // "uninterpreted", `InitExpr` is not associated with a value. There are
+ // two ways to handle this situation: propagate the status, so that
+ // uninterpreted initializers result in uninterpreted variables, or
+ // provide a default value. We choose the latter so that later refinements
+ // of the variable can be used for reasoning about the surrounding code.
+ // For this reason, we let this case be handled by the `createValue()`
+ // call below.
+ //
+ // FIXME. If and when we interpret all language cases, change this to
+ // assert that `InitExpr` is interpreted, rather than supplying a
+ // default value (assuming we don't update the environment API to return
+ // references).
+ Val = getValueStrict(*InitExpr);
+ if (!Val)
+ Val = createValue(Ty);
+
+ if (Ty->isRecordType())
+ return cast<StructValue>(Val)->getAggregateLoc();
+
+ StorageLocation &Loc =
+ D ? createStorageLocation(*D) : createStorageLocation(Ty);
+
+ if (Val)
+ setValue(Loc, *Val);
+
+ return Loc;
}
StorageLocation &Environment::skip(StorageLocation &Loc, SkipPast SP) const {
@@ -768,11 +902,6 @@ StorageLocation &Environment::skip(StorageLocation &Loc, SkipPast SP) const {
if (auto *Val = dyn_cast_or_null<ReferenceValue>(getValue(Loc)))
return Val->getReferentLoc();
return Loc;
- case SkipPast::ReferenceThenPointer:
- StorageLocation &LocPastRef = skip(Loc, SkipPast::Reference);
- if (auto *Val = dyn_cast_or_null<PointerValue>(getValue(LocPastRef)))
- return Val->getPointeeLoc();
- return LocPastRef;
}
llvm_unreachable("bad SkipPast kind");
}
@@ -782,12 +911,12 @@ const StorageLocation &Environment::skip(const StorageLocation &Loc,
return skip(*const_cast<StorageLocation *>(&Loc), SP);
}
-void Environment::addToFlowCondition(BoolValue &Val) {
- DACtx->addFlowConditionConstraint(*FlowConditionToken, Val);
+void Environment::addToFlowCondition(const Formula &Val) {
+ DACtx->addFlowConditionConstraint(FlowConditionToken, Val);
}
-bool Environment::flowConditionImplies(BoolValue &Val) const {
- return DACtx->flowConditionImplies(*FlowConditionToken, Val);
+bool Environment::flowConditionImplies(const Formula &Val) const {
+ return DACtx->flowConditionImplies(FlowConditionToken, Val);
}
void Environment::dump(raw_ostream &OS) const {
@@ -795,7 +924,7 @@ void Environment::dump(raw_ostream &OS) const {
// fields are printed.
OS << "DeclToLoc:\n";
for (auto [D, L] : DeclToLoc)
- OS << " [" << D->getName() << ", " << L << "]\n";
+ OS << " [" << D->getNameAsString() << ", " << L << "]\n";
OS << "ExprToLoc:\n";
for (auto [E, L] : ExprToLoc)
@@ -807,12 +936,93 @@ void Environment::dump(raw_ostream &OS) const {
}
OS << "FlowConditionToken:\n";
- DACtx->dumpFlowCondition(*FlowConditionToken);
+ DACtx->dumpFlowCondition(FlowConditionToken, OS);
}
void Environment::dump() const {
dump(llvm::dbgs());
}
+AggregateStorageLocation *
+getImplicitObjectLocation(const CXXMemberCallExpr &MCE,
+ const Environment &Env) {
+ Expr *ImplicitObject = MCE.getImplicitObjectArgument();
+ if (ImplicitObject == nullptr)
+ return nullptr;
+ StorageLocation *Loc =
+ Env.getStorageLocation(*ImplicitObject, SkipPast::Reference);
+ if (Loc == nullptr)
+ return nullptr;
+ if (ImplicitObject->getType()->isPointerType()) {
+ if (auto *Val = cast_or_null<PointerValue>(Env.getValue(*Loc)))
+ return &cast<AggregateStorageLocation>(Val->getPointeeLoc());
+ return nullptr;
+ }
+ return cast<AggregateStorageLocation>(Loc);
+}
+
+AggregateStorageLocation *getBaseObjectLocation(const MemberExpr &ME,
+ const Environment &Env) {
+ Expr *Base = ME.getBase();
+ if (Base == nullptr)
+ return nullptr;
+ StorageLocation *Loc = Env.getStorageLocation(*Base, SkipPast::Reference);
+ if (Loc == nullptr)
+ return nullptr;
+ if (ME.isArrow()) {
+ if (auto *Val = cast_or_null<PointerValue>(Env.getValue(*Loc)))
+ return &cast<AggregateStorageLocation>(Val->getPointeeLoc());
+ return nullptr;
+ }
+ return cast<AggregateStorageLocation>(Loc);
+}
+
+std::vector<FieldDecl *> getFieldsForInitListExpr(const RecordDecl *RD) {
+ // Unnamed bitfields are only used for padding and do not appear in
+ // `InitListExpr`'s inits. However, those fields do appear in `RecordDecl`'s
+ // field list, and we thus need to remove them before mapping inits to
+ // fields to avoid mapping inits to the wrongs fields.
+ std::vector<FieldDecl *> Fields;
+ llvm::copy_if(
+ RD->fields(), std::back_inserter(Fields),
+ [](const FieldDecl *Field) { return !Field->isUnnamedBitfield(); });
+ return Fields;
+}
+
+StructValue &refreshStructValue(AggregateStorageLocation &Loc,
+ Environment &Env) {
+ auto &NewVal = Env.create<StructValue>(Loc);
+ Env.setValue(Loc, NewVal);
+ return NewVal;
+}
+
+StructValue &refreshStructValue(const Expr &Expr, Environment &Env) {
+ assert(Expr.getType()->isRecordType());
+
+ if (Expr.isPRValue()) {
+ if (auto *ExistingVal =
+ cast_or_null<StructValue>(Env.getValueStrict(Expr))) {
+ auto &NewVal = Env.create<StructValue>(ExistingVal->getAggregateLoc());
+ Env.setValueStrict(Expr, NewVal);
+ return NewVal;
+ }
+
+ auto &NewVal = *cast<StructValue>(Env.createValue(Expr.getType()));
+ Env.setValueStrict(Expr, NewVal);
+ return NewVal;
+ }
+
+ if (auto *Loc = cast_or_null<AggregateStorageLocation>(
+ Env.getStorageLocationStrict(Expr))) {
+ auto &NewVal = Env.create<StructValue>(*Loc);
+ Env.setValue(*Loc, NewVal);
+ return NewVal;
+ }
+
+ auto &NewVal = *cast<StructValue>(Env.createValue(Expr.getType()));
+ Env.setStorageLocationStrict(Expr, NewVal.getAggregateLoc());
+ return NewVal;
+}
+
} // namespace dataflow
} // namespace clang