diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -264,13 +264,31 @@ /// /// Requirements: /// - /// `D` must not be assigned a storage location in the environment. + /// `D` must not already have a storage location in the environment. + /// + /// If `D` has reference type, `Loc` must refer directly to the referenced + /// object (if any), not to a `ReferenceValue`, and it is not permitted to + /// later change `Loc` to refer to a `ReferenceValue.` void setStorageLocation(const ValueDecl &D, StorageLocation &Loc); - /// Returns the storage location assigned to `D` in the environment, applying - /// the `SP` policy for skipping past indirections, or null if `D` isn't - /// assigned a storage location in the environment. - StorageLocation *getStorageLocation(const ValueDecl &D, SkipPast SP) const; + /// Removes the storage location assigned to `D`. + /// + /// Requirements: + /// + /// `D` must have a storage location in the environment. + void unsetStorageLocation(const ValueDecl &D); + + /// Returns the storage location assigned to `D` in the environment, or null + /// if `D` isn't assigned a storage location in the environment. + /// + /// Note that if `D` has reference type, the storage location that is returned + /// refers directly to the referenced object, not a `ReferenceValue`. + /// + /// The `SP` parameter is deprecated and has no effect. In addition, it is + /// not permitted to pass `SkipPast::ReferenceThenPointer` for this parameter. + /// New uses of this function should use the default argument for `SP`. + StorageLocation *getStorageLocation(const ValueDecl &D, + SkipPast SP = SkipPast::None) const; /// Assigns `Loc` as the storage location of `E` in the environment. /// @@ -315,7 +333,11 @@ /// Equivalent to `getValue(getStorageLocation(D, SP), SkipPast::None)` if `D` /// is assigned a storage location in the environment, otherwise returns null. - Value *getValue(const ValueDecl &D, SkipPast SP) const; + /// + /// The `SP` parameter is deprecated and has no effect. In addition, it is + /// not permitted to pass `SkipPast::ReferenceThenPointer` for this parameter. + /// New uses of this function should use the default argument for `SP`. + Value *getValue(const ValueDecl &D, SkipPast SP = SkipPast::None) const; /// Equivalent to `getValue(getStorageLocation(E, SP), SkipPast::None)` if `E` /// is assigned a storage location in the environment, otherwise returns null. diff --git a/clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp b/clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp --- a/clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp +++ b/clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp @@ -75,6 +75,7 @@ Options.AddTemporaryDtors = true; Options.AddInitializers = true; Options.AddCXXDefaultInitExprInCtors = true; + Options.AddScopes = true; // Ensure that all sub-expressions in basic blocks are evaluated. Options.setAllAlwaysAdd(); 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 @@ -49,6 +49,19 @@ return Result; } +/// Returns whether there is a key that is present in both maps and maps to +/// different values. +template +bool conflictingValues(const llvm::DenseMap &Map1, + const llvm::DenseMap &Map2) { + for (auto &Entry : Map1) { + auto It = Map2.find(Entry.first); + if (It != Map2.end() && Entry.second != It->second) + return true; + } + return false; +} + static bool compareDistinctValues(QualType Type, Value &Val1, const Environment &Env1, Value &Val2, const Environment &Env2, @@ -247,9 +260,9 @@ for (const VarDecl *D : Vars) { if (getStorageLocation(*D, SkipPast::None) != nullptr) continue; - auto &Loc = createStorageLocation(*D); + auto &Loc = createStorageLocation(D->getType().getNonReferenceType()); setStorageLocation(*D, Loc); - if (auto *Val = createValue(D->getType())) + if (auto *Val = createValue(D->getType().getNonReferenceType())) setValue(Loc, *Val); } @@ -291,10 +304,12 @@ for (const auto *ParamDecl : FuncDecl->parameters()) { assert(ParamDecl != nullptr); - auto &ParamLoc = createStorageLocation(*ParamDecl); + auto &ParamLoc = + createStorageLocation(ParamDecl->getType().getNonReferenceType()); setStorageLocation(*ParamDecl, ParamLoc); - if (Value *ParamVal = createValue(ParamDecl->getType())) - setValue(ParamLoc, *ParamVal); + if (Value *ParamVal = + createValue(ParamDecl->getType().getNonReferenceType())) + setValue(ParamLoc, *ParamVal); } QualType ReturnType = FuncDecl->getReturnType(); @@ -376,17 +391,19 @@ continue; const VarDecl *Param = *ParamIt; - auto &Loc = createStorageLocation(*Param); - setStorageLocation(*Param, Loc); QualType ParamType = Param->getType(); if (ParamType->isReferenceType()) { - auto &Val = arena().create(*ArgLoc); - setValue(Loc, Val); - } else if (auto *ArgVal = getValue(*ArgLoc)) { - setValue(Loc, *ArgVal); - } else if (Value *Val = createValue(ParamType)) { - setValue(Loc, *Val); + setStorageLocation(*Param, *ArgLoc); + } else { + auto &Loc = createStorageLocation(*Param); + setStorageLocation(*Param, Loc); + + if (auto *ArgVal = getValue(*ArgLoc)) { + setValue(Loc, *ArgVal); + } else if (Value *Val = createValue(ParamType)) { + setValue(Loc, *Val); + } } } } @@ -518,6 +535,7 @@ JoinedEnv.ReturnLoc = ReturnLoc; JoinedEnv.ThisPointeeLoc = ThisPointeeLoc; + assert(!conflictingValues(DeclToLoc, Other.DeclToLoc)); JoinedEnv.DeclToLoc = intersectDenseMaps(DeclToLoc, Other.DeclToLoc); if (DeclToLoc.size() != JoinedEnv.DeclToLoc.size()) Effect = LatticeJoinEffect::Changed; @@ -589,13 +607,30 @@ void Environment::setStorageLocation(const ValueDecl &D, StorageLocation &Loc) { assert(!DeclToLoc.contains(&D)); + assert(dyn_cast_or_null(getValue(Loc)) == nullptr); DeclToLoc[&D] = &Loc; } +void Environment::unsetStorageLocation(const ValueDecl &D) { + bool erased = DeclToLoc.erase(&D); + if (!erased) + D.dump(); + assert(erased); +} + StorageLocation *Environment::getStorageLocation(const ValueDecl &D, SkipPast SP) const { + assert(SP != SkipPast::ReferenceThenPointer); + 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(dyn_cast_or_null(getValue(*Loc)) == nullptr); + + return Loc; } void Environment::setStorageLocation(const Expr &E, StorageLocation &Loc) { @@ -662,6 +697,8 @@ } Value *Environment::getValue(const ValueDecl &D, SkipPast SP) const { + assert(SP != SkipPast::ReferenceThenPointer); + auto *Loc = getStorageLocation(D, SP); if (Loc == nullptr) return nullptr; diff --git a/clang/lib/Analysis/FlowSensitive/Transfer.cpp b/clang/lib/Analysis/FlowSensitive/Transfer.cpp --- a/clang/lib/Analysis/FlowSensitive/Transfer.cpp +++ b/clang/lib/Analysis/FlowSensitive/Transfer.cpp @@ -223,24 +223,7 @@ if (DeclLoc == nullptr) return; - // If the value is already an lvalue, don't double-wrap it. - if (isa_and_nonnull(Env.getValue(*DeclLoc))) { - // We only expect to encounter a `ReferenceValue` for a reference type - // (always) or for `BindingDecl` (sometimes). For the latter, we can't - // rely on type, because their type does not indicate whether they are a - // reference type. The assert is not strictly necessary, since we don't - // depend on its truth to proceed. But, it verifies our assumptions, - // which, if violated, probably indicate a problem elsewhere. - assert((VD->getType()->isReferenceType() || isa(VD)) && - "Only reference-typed declarations or `BindingDecl`s should map " - "to `ReferenceValue`s"); - Env.setStorageLocation(*S, *DeclLoc); - } else { - auto &Loc = Env.createStorageLocation(*S); - auto &Val = Env.create(*DeclLoc); - Env.setStorageLocation(*S, Loc); - Env.setValue(Loc, Val); - } + Env.setStorageLocation(*S, *DeclLoc); } void VisitDeclStmt(const DeclStmt *S) { @@ -248,55 +231,70 @@ // is safe. const auto &D = *cast(S->getSingleDecl()); + ProcessVarDecl(D); + } + + void ProcessVarDecl(const VarDecl &D) { // Static local vars are already initialized in `Environment`. if (D.hasGlobalStorage()) return; - // The storage location for `D` could have been created earlier, before the - // variable's declaration statement (for example, in the case of - // BindingDecls). - auto *MaybeLoc = Env.getStorageLocation(D, SkipPast::None); - if (MaybeLoc == nullptr) { - MaybeLoc = &Env.createStorageLocation(D); - Env.setStorageLocation(D, *MaybeLoc); - } - auto &Loc = *MaybeLoc; + if (D.getType()->isReferenceType()) { + // If this is the holding variable for a `BindingDecl`, we may already + // have a storage location set up -- so check. (See also explanation below + // where we process the `BindingDecl`.) + if (Env.getStorageLocation(D) == nullptr) { + const Expr *InitExpr = D.getInit(); + assert(InitExpr != nullptr); + if (auto *InitExprLoc = + Env.getStorageLocation(*InitExpr, SkipPast::Reference)) { + Env.setStorageLocation(D, *InitExprLoc); + } else { + // 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. + StorageLocation &Loc = + Env.createStorageLocation(D.getType().getNonReferenceType()); + Env.setStorageLocation(D, Loc); + if (Value *Val = Env.createValue(D.getType().getNonReferenceType())) + Env.setValue(Loc, *Val); + } + } + } else { + // Not a reference type. - const Expr *InitExpr = D.getInit(); - if (InitExpr == nullptr) { - // No initializer expression - associate `Loc` with a new value. - if (Value *Val = Env.createValue(D.getType())) - Env.setValue(Loc, *Val); - return; - } + assert(Env.getStorageLocation(D) == nullptr); + StorageLocation &Loc = Env.createStorageLocation(D); + Env.setStorageLocation(D, Loc); - if (D.getType()->isReferenceType()) { - // Initializing a reference variable - do not create a reference to - // reference. - // FIXME: reuse the ReferenceValue instead of creating a new one. - if (auto *InitExprLoc = - Env.getStorageLocation(*InitExpr, SkipPast::Reference)) { - auto &Val = Env.create(*InitExprLoc); - Env.setValue(Loc, Val); + const Expr *InitExpr = D.getInit(); + if (InitExpr == nullptr) { + // No initializer expression - associate `Loc` with a new value. + if (Value *Val = Env.createValue(D.getType())) + Env.setValue(Loc, *Val); + return; } - } else if (auto *InitExprVal = Env.getValue(*InitExpr, SkipPast::None)) { - Env.setValue(Loc, *InitExprVal); - } - if (Env.getValue(Loc) == nullptr) { - // We arrive here in (the few) cases where an expression is intentionally - // "uninterpreted". 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. - // - // 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). - if (Value *Val = Env.createValue(D.getType())) - Env.setValue(Loc, *Val); + if (auto *InitExprVal = Env.getValue(*InitExpr, SkipPast::None)) { + Env.setValue(Loc, *InitExprVal); + } + + if (Env.getValue(Loc) == nullptr) { + // We arrive here in (the few) cases where an expression is + // intentionally "uninterpreted". 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. + // + // 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). + if (Value *Val = Env.createValue(D.getType())) + Env.setValue(Loc, *Val); + } } // `DecompositionDecl` must be handled after we've interpreted the loc @@ -322,15 +320,16 @@ if (auto *Loc = Env.getStorageLocation(*ME, SkipPast::Reference)) Env.setStorageLocation(*B, *Loc); } else if (auto *VD = B->getHoldingVar()) { - // Holding vars are used to back the BindingDecls of tuple-like - // types. The holding var declarations appear *after* this statement, - // so we have to create a location for them here to share with `B`. We - // don't visit the binding, because we know it will be a DeclRefExpr - // to `VD`. Note that, by construction of the AST, `VD` will always be - // a reference -- either lvalue or rvalue. - auto &VDLoc = Env.createStorageLocation(*VD); - Env.setStorageLocation(*VD, VDLoc); - Env.setStorageLocation(*B, VDLoc); + // Holding vars are used to back the `BindingDecl`s of tuple-like + // types. The holding var declarations appear after the + // `DecompositionDecl`, so we have to explicitly process them here + // to know their storage location. They will be processed a second + // time when we visit their `VarDecl`s, so we have code that protects + // against this above. + ProcessVarDecl(*VD); + auto *VDLoc = Env.getStorageLocation(*VD); + assert(VDLoc != nullptr); + Env.setStorageLocation(*B, *VDLoc); } } } @@ -539,15 +538,7 @@ if (VarDeclLoc == nullptr) return; - if (VarDeclLoc->getType()->isReferenceType()) { - assert(isa_and_nonnull(Env.getValue((*VarDeclLoc))) && - "reference-typed declarations map to `ReferenceValue`s"); - Env.setStorageLocation(*S, *VarDeclLoc); - } else { - auto &Loc = Env.createStorageLocation(*S); - Env.setStorageLocation(*S, Loc); - Env.setValue(Loc, Env.create(*VarDeclLoc)); - } + Env.setStorageLocation(*S, *VarDeclLoc); return; } } diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp --- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp +++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp @@ -64,6 +64,8 @@ return false; } +namespace { + // The return type of the visit functions in TerminatorVisitor. The first // element represents the terminator expression (that is the conditional // expression in case of a path split in the CFG). The second element @@ -185,6 +187,8 @@ llvm::ArrayRef> BlockStates; }; +} // namespace + /// Computes the input state for a given basic block by joining the output /// states of its predecessors. /// @@ -276,17 +280,19 @@ } /// Built-in transfer function for `CFGStmt`. -void builtinTransferStatement(const CFGStmt &Elt, - TypeErasedDataflowAnalysisState &InputState, - AnalysisContext &AC) { +static void +builtinTransferStatement(const CFGStmt &Elt, + TypeErasedDataflowAnalysisState &InputState, + AnalysisContext &AC) { const Stmt *S = Elt.getStmt(); assert(S != nullptr); transfer(StmtToEnvMap(AC.CFCtx, AC.BlockStates), *S, InputState.Env); } /// Built-in transfer function for `CFGInitializer`. -void builtinTransferInitializer(const CFGInitializer &Elt, - TypeErasedDataflowAnalysisState &InputState) { +static void +builtinTransferInitializer(const CFGInitializer &Elt, + TypeErasedDataflowAnalysisState &InputState) { const CXXCtorInitializer *Init = Elt.getInitializer(); assert(Init != nullptr); @@ -319,9 +325,17 @@ } } -void builtinTransfer(const CFGElement &Elt, - TypeErasedDataflowAnalysisState &State, - AnalysisContext &AC) { +static void +builtinTransferScopeEnd(const CFGScopeEnd &Elt, + TypeErasedDataflowAnalysisState &InputState) { + if (const VarDecl *VD = Elt.getVarDecl()) { + InputState.Env.unsetStorageLocation(*VD); + } +} + +static void builtinTransfer(const CFGElement &Elt, + TypeErasedDataflowAnalysisState &State, + AnalysisContext &AC) { switch (Elt.getKind()) { case CFGElement::Statement: builtinTransferStatement(Elt.castAs(), State, AC); @@ -329,6 +343,9 @@ case CFGElement::Initializer: builtinTransferInitializer(Elt.castAs(), State); break; + case CFGElement::ScopeEnd: + builtinTransferScopeEnd(Elt.castAs(), State); + break; default: // FIXME: Evaluate other kinds of `CFGElement`. break; @@ -343,7 +360,7 @@ /// user-specified analysis. /// `PostVisitCFG` (if provided) will be applied to the element after evaluation /// by the user-specified analysis. -TypeErasedDataflowAnalysisState +static TypeErasedDataflowAnalysisState transferCFGBlock(const CFGBlock &Block, AnalysisContext &AC, std::function 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 @@ -403,14 +403,9 @@ const StorageLocation *FooLoc = Env.getStorageLocation(*FooDecl, SkipPast::None); - ASSERT_TRUE(isa_and_nonnull(FooLoc)); - - const ReferenceValue *FooVal = - cast(Env.getValue(*FooLoc)); - const StorageLocation &FooReferentLoc = FooVal->getReferentLoc(); - EXPECT_TRUE(isa(&FooReferentLoc)); + ASSERT_TRUE(isa_and_nonnull(FooLoc)); - const Value *FooReferentVal = Env.getValue(FooReferentLoc); + const Value *FooReferentVal = Env.getValue(*FooLoc); EXPECT_TRUE(isa_and_nonnull(FooReferentVal)); }); } @@ -494,11 +489,9 @@ ASSERT_THAT(BazRefDecl, NotNull()); ASSERT_THAT(BazPtrDecl, NotNull()); - const auto *FooLoc = cast( + const auto *FooLoc = cast( Env.getStorageLocation(*FooDecl, SkipPast::None)); - const auto *FooVal = cast(Env.getValue(*FooLoc)); - const auto *FooReferentVal = - cast(Env.getValue(FooVal->getReferentLoc())); + const auto *FooReferentVal = cast(Env.getValue(*FooLoc)); const auto *BarVal = cast(FooReferentVal->getChild(*BarDecl)); @@ -507,13 +500,17 @@ const auto *FooRefVal = cast(BarReferentVal->getChild(*FooRefDecl)); - const StorageLocation &FooReferentLoc = FooRefVal->getReferentLoc(); - EXPECT_THAT(Env.getValue(FooReferentLoc), IsNull()); + const auto &FooReferentLoc = + cast(FooRefVal->getReferentLoc()); + EXPECT_THAT(Env.getValue(FooReferentLoc), NotNull()); + EXPECT_THAT(Env.getValue(FooReferentLoc.getChild(*BarDecl)), IsNull()); const auto *FooPtrVal = cast(BarReferentVal->getChild(*FooPtrDecl)); - const StorageLocation &FooPtrPointeeLoc = FooPtrVal->getPointeeLoc(); - EXPECT_THAT(Env.getValue(FooPtrPointeeLoc), IsNull()); + const auto &FooPtrPointeeLoc = + cast(FooPtrVal->getPointeeLoc()); + EXPECT_THAT(Env.getValue(FooPtrPointeeLoc), NotNull()); + EXPECT_THAT(Env.getValue(FooPtrPointeeLoc.getChild(*BarDecl)), IsNull()); const auto *BazRefVal = cast(BarReferentVal->getChild(*BazRefDecl)); @@ -1058,16 +1055,9 @@ const StorageLocation *FooLoc = Env.getStorageLocation(*FooDecl, SkipPast::None); - ASSERT_TRUE(isa_and_nonnull(FooLoc)); - - const ReferenceValue *FooVal = - dyn_cast(Env.getValue(*FooLoc)); - ASSERT_THAT(FooVal, NotNull()); + ASSERT_TRUE(isa_and_nonnull(FooLoc)); - const StorageLocation &FooReferentLoc = FooVal->getReferentLoc(); - EXPECT_TRUE(isa(&FooReferentLoc)); - - const Value *FooReferentVal = Env.getValue(FooReferentLoc); + const Value *FooReferentVal = Env.getValue(*FooLoc); EXPECT_TRUE(isa_and_nonnull(FooReferentVal)); }); } @@ -1905,15 +1895,13 @@ const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo"); ASSERT_THAT(FooDecl, NotNull()); - const auto *FooVal = - cast(Env.getValue(*FooDecl, SkipPast::None)); + const auto *FooLoc = Env.getStorageLocation(*FooDecl); const ValueDecl *QuxDecl = findValueDecl(ASTCtx, "Qux"); ASSERT_THAT(QuxDecl, NotNull()); - const auto *QuxVal = - cast(Env.getValue(*QuxDecl, SkipPast::None)); - EXPECT_EQ(&QuxVal->getReferentLoc(), &FooVal->getReferentLoc()); + const auto *QuxLoc = Env.getStorageLocation(*QuxDecl); + EXPECT_EQ(QuxLoc, FooLoc); }); } @@ -2593,9 +2581,8 @@ const auto *FooVal = cast(Env.getValue(*FooDecl, SkipPast::None)); - const auto *BarVal = - cast(Env.getValue(*BarDecl, SkipPast::None)); - EXPECT_EQ(&BarVal->getReferentLoc(), &FooVal->getPointeeLoc()); + const auto *BarLoc = Env.getStorageLocation(*BarDecl); + EXPECT_EQ(BarLoc, &FooVal->getPointeeLoc()); }); } @@ -2643,17 +2630,20 @@ void target(int *Foo) { do { int Bar = *Foo; + // [[in_loop]] } while (true); (void)0; - /*[[p]]*/ + // [[after_loop]] } )"; runDataflow( Code, [](const llvm::StringMap> &Results, ASTContext &ASTCtx) { - ASSERT_THAT(Results.keys(), UnorderedElementsAre("p")); - const Environment &Env = getEnvironmentAtAnnotation(Results, "p"); + const Environment &EnvInLoop = + getEnvironmentAtAnnotation(Results, "in_loop"); + const Environment &EnvAfterLoop = + getEnvironmentAtAnnotation(Results, "after_loop"); const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo"); ASSERT_THAT(FooDecl, NotNull()); @@ -2662,15 +2652,14 @@ ASSERT_THAT(BarDecl, NotNull()); const auto *FooVal = - cast(Env.getValue(*FooDecl, SkipPast::None)); + cast(EnvAfterLoop.getValue(*FooDecl)); const auto *FooPointeeVal = - cast(Env.getValue(FooVal->getPointeeLoc())); - - const auto *BarVal = dyn_cast_or_null( - Env.getValue(*BarDecl, SkipPast::None)); - ASSERT_THAT(BarVal, NotNull()); + cast(EnvAfterLoop.getValue(FooVal->getPointeeLoc())); + const auto *BarVal = cast(EnvInLoop.getValue(*BarDecl)); EXPECT_EQ(BarVal, FooPointeeVal); + + ASSERT_THAT(EnvAfterLoop.getValue(*BarDecl), IsNull()); }); }