[clang] [clang-tools-extra] [clang-tidy] Add support for bsl::optional (PR #101450)
@@ -784,6 +814,12 @@ auto buildTransferMatchSwitch() { isOptionalMemberCallWithNameMatcher(hasName("operator bool")), transferOptionalHasValueCall) + // NullableValue::isNull + // Only NullableValue has isNull + .CaseOfCFGStmt( + isOptionalMemberCallWithNameMatcher(hasAnyName("isNull")), ymand wrote: Please use `hasName` given that it's just one name. https://github.com/llvm/llvm-project/pull/101450 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang-tools-extra] [clang-tidy] Add support for bsl::optional (PR #101450)
@@ -38,10 +38,22 @@ namespace clang { namespace dataflow { -static bool isTopLevelNamespaceWithName(const NamespaceDecl , -llvm::StringRef Name) { - return NS.getDeclName().isIdentifier() && NS.getName() == Name && - NS.getParent() != nullptr && NS.getParent()->isTranslationUnit(); +template +static bool hasNestedNamespace(const NamespaceDecl , llvm::StringRef Name, ymand wrote: I think this function name makes the callsites harder to understand. E.g. for "absl", we're not querying for a nested namespace of "absl". Please either find a more precise name or document behavior in a comment. When I read "hasNestedNamespace", I think of a function that searches a namespace for another one nested inside. At the least, why not "isNestedNamespace", since the query is on the NamespaceDecl itself and is an exact match, so "is" seems more appropriate than "has"? https://github.com/llvm/llvm-project/pull/101450 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang-tools-extra] [clang-tidy] Add support for bsl::optional (PR #101450)
https://github.com/ymand requested changes to this pull request. https://github.com/llvm/llvm-project/pull/101450 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Handle this-capturing lambdas in field initializers. (PR #99519)
https://github.com/ymand closed https://github.com/llvm/llvm-project/pull/99519 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Handle this-capturing lambdas in field initializers. (PR #99519)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/99519 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Handle this-capturing lambdas in field initializers. (PR #99519)
https://github.com/ymand edited https://github.com/llvm/llvm-project/pull/99519 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][transformer] Introduce a `constructExprArgs` range selector. (PR #95901)
https://github.com/ymand approved this pull request. Thanks! https://github.com/llvm/llvm-project/pull/95901 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Teach `AnalysisASTVisitor` that `typeid()` can be evaluated. (PR #96731)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/96731 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [clang][nullability] Don't return null fields from `getReferencedDecls()`. (PR #94983)
https://github.com/ymand approved this pull request. Thanks! I'm once again struck by how much this project would benefit from Nullability annotations/checking. https://github.com/llvm/llvm-project/pull/94983 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Handle `AtomicExpr` in `ResultObjectVisitor`. (PR #94963)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/94963 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Propagate storage location of compound assignment operators. (PR #94332)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/94332 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][nullability] Propagate storage location / value of `++`/`--` operators. (PR #94217)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/94217 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Rewrite `getReferencedDecls()` with a `RecursiveASTVisitor`. (PR #93461)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/93461 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Rewrite `getReferencedDecls()` with a `RecursiveASTVisitor`. (PR #93461)
https://github.com/ymand edited https://github.com/llvm/llvm-project/pull/93461 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Rewrite `getReferencedDecls()` with a `RecursiveASTVisitor`. (PR #93461)
@@ -188,90 +188,97 @@ static MemberExpr *getMemberForAccessor(const CXXMemberCallExpr ) { return nullptr; } -static void getReferencedDecls(const Decl , ReferencedDecls ) { - insertIfGlobal(D, Referenced.Globals); - insertIfFunction(D, Referenced.Functions); - if (const auto *Decomp = dyn_cast()) -for (const auto *B : Decomp->bindings()) - if (auto *ME = dyn_cast_or_null(B->getBinding())) -// FIXME: should we be using `E->getFoundDecl()`? -if (const auto *FD = dyn_cast(ME->getMemberDecl())) - Referenced.Fields.insert(FD); -} +class ReferencedDeclsVisitor +: public AnalysisASTVisitor { +public: + ReferencedDeclsVisitor(ReferencedDecls ) + : Referenced(Referenced) {} + + void TraverseConstructorInits(const CXXConstructorDecl *Ctor) { +for (const CXXCtorInitializer *Init : Ctor->inits()) { + if (Init->isMemberInitializer()) { +Referenced.Fields.insert(Init->getMember()); + } else if (Init->isIndirectMemberInitializer()) { +for (const auto *I : Init->getIndirectMember()->chain()) + Referenced.Fields.insert(cast(I)); + } + + Expr *InitExpr = Init->getInit(); + + // Ensure that any result objects within `InitExpr` (e.g. temporaries) + // are also propagated to the prvalues that initialize them. ymand wrote: Here and below: this comment seems out of place for this visitor -- it's just collecting names, not doing any propagating (I thought)? https://github.com/llvm/llvm-project/pull/93461 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Rewrite `getReferencedDecls()` with a `RecursiveASTVisitor`. (PR #93461)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/93461 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [clang][dataflow] Make `CNFFormula` externally accessible. (PR #92401)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/92401 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Fully support Environment construction for Stmt analysis. (PR #91616)
https://github.com/ymand closed https://github.com/llvm/llvm-project/pull/91616 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Fully support Environment construction for Stmt analysis. (PR #91616)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/91616 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Fully support Environment construction for Stmt analysis. (PR #91616)
@@ -476,7 +476,7 @@ runTypeErasedDataflowAnalysis( PrettyStackTraceAnalysis CrashInfo(ACFG, "runTypeErasedDataflowAnalysis"); std::optional MaybeStartingEnv; - if (InitEnv.callStackSize() == 1) { + if (InitEnv.callStackSize() == 0) { ymand wrote: aside: this line now feels more "right" than the original version. https://github.com/llvm/llvm-project/pull/91616 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Fully support Environment construction for Stmt analysis. (PR #91616)
https://github.com/ymand approved this pull request. Nice! https://github.com/llvm/llvm-project/pull/91616 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Fully support Environment construction for Stmt analysis. (PR #91616)
@@ -718,29 +730,46 @@ class Environment { void pushCallInternal(const FunctionDecl *FuncDecl, ArrayRef Args); + // FIXME: Add support for resetting globals after function calls to enable + // the implementation of sound analyses. + /// Assigns storage locations and values to all global variables, fields - /// and functions referenced in `FuncDecl`. `FuncDecl` must have a body. - void initFieldsGlobalsAndFuncs(const FunctionDecl *FuncDecl); + /// and functions in `Referenced`. + void initFieldsGlobalsAndFuncs(const ReferencedDecls ); static PrValueToResultObject buildResultObjectMap(DataflowAnalysisContext *DACtx, const FunctionDecl *FuncDecl, RecordStorageLocation *ThisPointeeLoc, RecordStorageLocation *LocForRecordReturnVal); + static PrValueToResultObject + buildResultObjectMap(DataflowAnalysisContext *DACtx, Stmt *S, + RecordStorageLocation *ThisPointeeLoc, + RecordStorageLocation *LocForRecordReturnVal); + // `DACtx` is not null and not owned by this object. DataflowAnalysisContext *DACtx; - // FIXME: move the fields `CallStack`, `ResultObjectMap`, `ReturnVal`, + // FIXME: move the fields `TargetStack`, `ResultObjectMap`, `ReturnVal`, ymand wrote: s/TargetStack/CallStack/ https://github.com/llvm/llvm-project/pull/91616 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Fully support Environment construction for Stmt analysis. (PR #91616)
https://github.com/ymand edited https://github.com/llvm/llvm-project/pull/91616 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Fully support Environment construction for Stmt analysis. (PR #91616)
ymand wrote: > I agree with the usefulness of storing the initial target separately, > reducing checks and branching based on whether the current target is a `Stmt` > or `Function`. Since I was touching everywhere `CallStack` was used anyway, I > went ahead with not pushing the starting `FunctionDecl` onto that stack. Thanks! > I wasn't immediately able to reduce the `initialize` duplication for > statements and function bodies since `buildResultObjectMap` and > `initFieldsGlobalsAndFuncs`, via `getReferencedDecls`, both handle > `FunctionDecl`s and `Stmt`s differently, pulling info from a `FunctionDecl` > beyond just its body. If templating `initFieldsGlobalsAndFuncs` is really > undesirable, I could either pass in the `ReferencedDecls` from current > callers or insert an intermediate with two overloads that takes the > `Stmt`/`FunctionDecl` and passes along the `ReferencedDecls`. I'm generally allergic to templates unless necessary, but that doesn't mean I'm right :) I'm inclined towards either of the solutions you suggested involving passing `ReferencedDecls` (with a slight, arbitrary preference for the first since it involves fewer new function declarations), but I leave it up to you since you're actually writing the code and have a better view as to which solution is cleaner. Also happy to hear from other reviewers. https://github.com/llvm/llvm-project/pull/91616 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Fully support Environment construction for Stmt analysis. (PR #91616)
https://github.com/ymand commented: I think we can do this without resorting to a pointer union and templating of the initialization functions, but it will take a little refactoring. First, notice that `stmt` doesn't make sense for the CallStack. The call stack serves two purposes -- to avoid recursion (line 627) and to process the return val (lines 801-811). Neither of these cases apply for stmts, as you've correctly identified in your modifications to the code (e.g. line 776 in your new version of DataflowEnvironment.cpp) So, I think its fair to say that CallStack should remain as is. If you're analyzing a Stmt, then you simply don't push onto the call stack. (I'm actually thinking we should not push the starting FunctionDecl onto the call stack either, since it's not called from anywhere, but that's a separate issue...) That brings us to the second use of the function decl -- initialization. here's where refactoring comes in -- if you look at the init call stack, it's actually doing two things: use the "function decl" stuff (like parameters) and using the body (which is just a stmt). Currently, these are nested. But, I think that, instead, you can refactor to sequence them. Then, for FunctionDecl cases we call both but for Stmts just the second. The way to distinguish I think is just to explicitly store both the FD and the Stmt as separate fields. Then, init will assume there's always a stmt but will check the FD for null. Or, it can rely on the call stack and just look at the top of the call stack, if any. WDYT? https://github.com/llvm/llvm-project/pull/91616 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [llvm] [clang][dataflow] Make `SolverTest` a type-parameterized test. (PR #91455)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/91455 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Allow `DataflowAnalysisContext` to use a non-owned `Solver`. (PR #91316)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/91316 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Allow `DataflowAnalysisContext` to use a non-owned `Solver`. (PR #91316)
@@ -209,6 +221,9 @@ class DataflowAnalysisContext { using DenseMapInfo::isEqual; }; + DataflowAnalysisContext(Solver , std::unique_ptr OwnedSolver, ymand wrote: Please add comments either here or on the fields relating S and OwnedSolver. https://github.com/llvm/llvm-project/pull/91316 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Allow `DataflowAnalysisContext` to use a non-owned `Solver`. (PR #91316)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/91316 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Allow `DataflowAnalysisContext` to use a non-owned `Solver`. (PR #91316)
https://github.com/ymand edited https://github.com/llvm/llvm-project/pull/91316 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Add `reachedLimit()` to the `Solver` interface. (PR #91320)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/91320 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Strengthen pointer comparison. (PR #75170)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/75170 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Don't propagate result objects in unevaluated contexts (reland #90438) (PR #91172)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/91172 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Fix crash when `operator=` result type is not destination type. (PR #90898)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/90898 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Fix crash when `ConstantExpr` is used in conditional operator. (PR #90112)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/90112 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] Reapply "[clang][dataflow] Model conditional operator correctly." with fixes (PR #89596)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/89596 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Expose getReferencedDecls for a Stmt. (PR #89444)
https://github.com/ymand closed https://github.com/llvm/llvm-project/pull/89444 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Expose getReferencedDecls for a Stmt. (PR #89444)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/89444 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Support `CXXParenListInitExpr` in `PropagateResultObject()`. (PR #89235)
@@ -401,6 +401,29 @@ class ResultObjectVisitor : public RecursiveASTVisitor { return true; } + void + PropagateResultObjectToRecordInitList(const RecordInitListHelper , +RecordStorageLocation *Loc) { +for (auto [Base, Init] : InitList.base_inits()) { + assert(Base->getType().getCanonicalType() == + Init->getType().getCanonicalType()); + + // Storage location for the base class is the same as that of the + // derived class because we "flatten" the object hierarchy and put all + // fields in `RecordStorageLocation` of the derived class. + PropagateResultObject(Init, Loc); +} + +for (auto [Field, Init] : InitList.field_inits()) { + // Fields of non-record type are handled in + // `TransferVisitor::VisitInitListExpr()`. + if (!Field->getType()->isRecordType()) +continue; + PropagateResultObject(Init, + cast(Loc->getChild(*Field))); ymand wrote: ```suggestion if (Field->getType()->isRecordType()) PropagateResultObject(Init, cast(Loc->getChild(*Field))); ``` https://github.com/llvm/llvm-project/pull/89235 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Support `CXXParenListInitExpr` in `PropagateResultObject()`. (PR #89235)
https://github.com/ymand edited https://github.com/llvm/llvm-project/pull/89235 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Support `CXXParenListInitExpr` in `PropagateResultObject()`. (PR #89235)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/89235 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Model conditional operator correctly. (PR #89213)
@@ -5243,6 +5243,67 @@ TEST(TransferTest, BinaryOperatorComma) { }); } +TEST(TransferTest, ConditionalOperatorValue) { + std::string Code = R"( +void target(bool Cond, bool B1, bool B2) { + bool JoinSame = Cond ? B1 : B1; + bool JoinDifferent = Cond ? B1 : B2; + // [[p]] +} + )"; + runDataflow( + Code, + [](const llvm::StringMap> , + ASTContext ) { +Environment Env = getEnvironmentAtAnnotation(Results, "p").fork(); + +auto = getValueForDecl(ASTCtx, Env, "B1"); +auto = getValueForDecl(ASTCtx, Env, "B2"); +auto = getValueForDecl(ASTCtx, Env, "JoinSame"); +auto = +getValueForDecl(ASTCtx, Env, "JoinDifferent"); + +EXPECT_EQ(, ); + +const Formula = +Env.arena().makeEquals(JoinDifferent.formula(), B1.formula()); +EXPECT_TRUE(Env.allows(JoinDifferentEqB1)); ymand wrote: Nice use of `allows`! https://github.com/llvm/llvm-project/pull/89213 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Model conditional operator correctly. (PR #89213)
@@ -657,17 +658,22 @@ class TransferVisitor : public ConstStmtVisitor { } void VisitConditionalOperator(const ConditionalOperator *S) { -// FIXME: Revisit this once flow conditions are added to the framework. For -// `a = b ? c : d` we can add `b => a == c && !b => a == d` to the flow -// condition. -// When we do this, we will need to retrieve the values of the operands from -// the environments for the basic blocks they are computed in, in a similar -// way to how this is done for short-circuited logical operators in -// `getLogicOperatorSubExprValue()`. -if (S->isGLValue()) - Env.setStorageLocation(*S, Env.createObject(S->getType())); -else if (!S->getType()->isRecordType()) { - if (Value *Val = Env.createValue(S->getType())) +const Environment *TrueEnv = StmtToEnv.getEnvironment(*S->getTrueExpr()); +const Environment *FalseEnv = StmtToEnv.getEnvironment(*S->getFalseExpr()); + +if (TrueEnv == nullptr || FalseEnv == nullptr) + return; + +if (S->isGLValue()) { + StorageLocation *TrueLoc = TrueEnv->getStorageLocation(*S->getTrueExpr()); + StorageLocation *FalseLoc = + FalseEnv->getStorageLocation(*S->getFalseExpr()); + if (TrueLoc == FalseLoc && TrueLoc != nullptr) +Env.setStorageLocation(*S, *TrueLoc); +} else if (!S->getType()->isRecordType()) { + if (Value *Val = Environment::joinValues( ymand wrote: it might be worth commenting why we need a join here. IIUC, we lack any concept of a "result expression" of a basic block. So, when the environments were joined in the normal basic-block processing algorithm, these two expressions would have been simply dropped (existing at respectively different locations in LocToVal). Hence, we need to explicitly extract them and join at this point. https://github.com/llvm/llvm-project/pull/89213 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Model conditional operator correctly. (PR #89213)
https://github.com/ymand edited https://github.com/llvm/llvm-project/pull/89213 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Model conditional operator correctly. (PR #89213)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/89213 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang] fix -Wnullability-completeness false-positive in dependent code (PR #88727)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/88727 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `PropagateResultObject()` with a switch statement. (PR #88865)
https://github.com/ymand approved this pull request. Thanks! https://github.com/llvm/llvm-project/pull/88865 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Expose getReferencedDecls and relocate free functions. (PR #88754)
https://github.com/ymand closed https://github.com/llvm/llvm-project/pull/88754 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Treat `BuiltinBitCastExpr` correctly in `PropagateResultObject()`. (PR #88875)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/88875 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Support `StmtExpr` in `PropagateResultObject()`. (PR #88872)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/88872 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `PropagateResultObject()` with a switch statement. (PR #88865)
ymand wrote: Clearly, this is a matter of taste, so I would defer to your opinion, since you are the primary maintainer of this code. But, personally, I prefer this style since it makes clear that the body of the function is a single case analysis, which is not obvious from the series of if statements. It's unfortunate that the enum syntax is so bulky (the need for `Stmt::` and the `Class` suffix). The casts don't bother me (well, any more than C++'s general lack of built-in datatype and pattern matching support bother me :)). https://github.com/llvm/llvm-project/pull/88865 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Expose getReferencedDecls and relocate free functions. (PR #88754)
https://github.com/ymand approved this pull request. Thanks! https://github.com/llvm/llvm-project/pull/88754 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Fix result object location for builtin `<=>`. (PR #88726)
@@ -508,6 +508,11 @@ class ResultObjectVisitor : public RecursiveASTVisitor { isa(E)) { return; } +if (auto *Op = dyn_cast(E); ymand wrote: I guess the `isa` calls were what we really jumped out since they amount to N calls and tests on `getStmtClass` rather than one and a jump. But, readability wins over performance here. But, I do wonder about readability win from converting to a switch because it will directly express which cases are covered in this function, rather than leaving it implicit in a series of `if`s. FWIW. https://github.com/llvm/llvm-project/pull/88726 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Fix result object location for builtin `<=>`. (PR #88726)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/88726 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Fix result object location for builtin `<=>`. (PR #88726)
@@ -508,6 +508,11 @@ class ResultObjectVisitor : public RecursiveASTVisitor { isa(E)) { return; } +if (auto *Op = dyn_cast(E); ymand wrote: aside: Might lines 506 through 553 be better expressed as a switch on `E->getStmtClass()`? https://github.com/llvm/llvm-project/pull/88726 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Fix result object location for builtin `<=>`. (PR #88726)
https://github.com/ymand edited https://github.com/llvm/llvm-project/pull/88726 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Expose fields, globals, and functions referenced. (PR #88534)
@@ -62,6 +62,52 @@ FieldSet getObjectFields(QualType Type); bool containsSameFields(const FieldSet , const RecordStorageLocation::FieldToLoc ); +/// Returns the fields of a `RecordDecl` that are initialized by an +/// `InitListExpr`, in the order in which they appear in +/// `InitListExpr::inits()`. +/// `Init->getType()` must be a record type. +std::vector +getFieldsForInitListExpr(const InitListExpr *InitList); + +/// Helper class for initialization of a record with an `InitListExpr`. +/// `InitListExpr::inits()` contains the initializers for both the base classes +/// and the fields of the record; this helper class separates these out into two +/// different lists. In addition, it deals with special cases associated with +/// unions. +class RecordInitListHelper { +public: + // `InitList` must have record type. + RecordInitListHelper(const InitListExpr *InitList); + + // Base classes with their associated initializer expressions. + ArrayRef> base_inits() const { +return BaseInits; + } + + // Fields with their associated initializer expressions. + ArrayRef> field_inits() const { +return FieldInits; + } + +private: + SmallVector> BaseInits; + SmallVector> FieldInits; + + // We potentially synthesize an `ImplicitValueInitExpr` for unions. It's a + // member variable because we store a pointer to it in `FieldInits`. + std::optional ImplicitValueInitForUnion; +}; + +struct FieldsGlobalsAndFuncs { ymand wrote: Maybe prefix "Mentioned" or "Referenced" or "Used"? Also, please add a brief comment. In context, it's role is obvious, but for cross-referencing tools, its often helpful to have comment when you're looking at a mention in another file. https://github.com/llvm/llvm-project/pull/88534 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Expose fields, globals, and functions referenced. (PR #88534)
https://github.com/ymand approved this pull request. Thanks! https://github.com/llvm/llvm-project/pull/88534 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Expose fields, globals, and functions referenced. (PR #88534)
@@ -62,6 +62,52 @@ FieldSet getObjectFields(QualType Type); bool containsSameFields(const FieldSet , const RecordStorageLocation::FieldToLoc ); +/// Returns the fields of a `RecordDecl` that are initialized by an +/// `InitListExpr`, in the order in which they appear in +/// `InitListExpr::inits()`. +/// `Init->getType()` must be a record type. +std::vector +getFieldsForInitListExpr(const InitListExpr *InitList); + +/// Helper class for initialization of a record with an `InitListExpr`. +/// `InitListExpr::inits()` contains the initializers for both the base classes +/// and the fields of the record; this helper class separates these out into two +/// different lists. In addition, it deals with special cases associated with +/// unions. +class RecordInitListHelper { +public: + // `InitList` must have record type. + RecordInitListHelper(const InitListExpr *InitList); + + // Base classes with their associated initializer expressions. + ArrayRef> base_inits() const { +return BaseInits; + } + + // Fields with their associated initializer expressions. + ArrayRef> field_inits() const { +return FieldInits; + } + +private: + SmallVector> BaseInits; + SmallVector> FieldInits; + + // We potentially synthesize an `ImplicitValueInitExpr` for unions. It's a + // member variable because we store a pointer to it in `FieldInits`. + std::optional ImplicitValueInitForUnion; +}; + +struct FieldsGlobalsAndFuncs { + FieldSet Fields; + // Globals includes all variables with global storage, notably including + // static data members and static variables declared within a function. + llvm::DenseSet Globals; + llvm::DenseSet Funcs; ymand wrote: Comment `Funcs`? I'm actually not sure offhand what that's for. :) https://github.com/llvm/llvm-project/pull/88534 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Expose fields, globals, and functions referenced. (PR #88534)
https://github.com/ymand edited https://github.com/llvm/llvm-project/pull/88534 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Remove deprecated alias `ControlFlowContext`. (PR #88358)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/88358 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Reland #87320: Propagate locations from result objects to initializers. (PR #88316)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/88316 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libTooling] Fix `getFileRangeForEdit` for inner nested template types (PR #87673)
@@ -510,6 +519,26 @@ int c = M3(3); Visitor.runOver(Code.code()); } +TEST(SourceCodeTest, InnerNestedTemplate) { ymand wrote: Add a test case that covers the case of the split being in the BeginToken? https://github.com/llvm/llvm-project/pull/87673 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libTooling] Fix `getFileRangeForEdit` for inner nested template types (PR #87673)
https://github.com/ymand approved this pull request. Nice work - really subtle! I'd been wondering how clang handles this issue (of relexing returning the wrong token because it lacked context). https://github.com/llvm/llvm-project/pull/87673 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [libTooling] Fix `getFileRangeForEdit` for inner nested template types (PR #87673)
https://github.com/ymand edited https://github.com/llvm/llvm-project/pull/87673 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
ymand wrote: I also fixed up the other tests to use `getValue/LocForDecl` to be consistent. https://github.com/llvm/llvm-project/pull/87233 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/87233 >From d8d875271bd47b71701143afb06ea654546e2b7c Mon Sep 17 00:00:00 2001 From: Yitzhak Mandelbaum Date: Mon, 1 Apr 2024 12:13:39 + Subject: [PATCH 1/4] [clang][dataflow] Refactor `widen` API to be explicit about change effect. The previous API relied on pointer equality of inputs and outputs to signal whether a change occured. This was too subtle and led to bugs in practice. It was also very limiting: the override could not return an equivalent (but not identical) value. --- .../FlowSensitive/DataflowEnvironment.h | 47 +++--- .../FlowSensitive/DataflowEnvironment.cpp | 43 ++--- .../TypeErasedDataflowAnalysisTest.cpp| 48 +++ 3 files changed, 104 insertions(+), 34 deletions(-) diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h index c30bccd06674a4..0a37d9d68e2898 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -97,6 +97,16 @@ class Environment { const Value , const Environment , Value , Environment ) {} +/// The result of the `widen` operation. +struct WidenResult { + /// Non-null pointer to a potentially widened version of the widening + /// input. + Value *V; + /// Whether `V` represents a "change" (that is, a different value) with + /// respect to the previous value in the sequence. + LatticeJoinEffect Effect; +}; + /// This function may widen the current value -- replace it with an /// approximation that can reach a fixed point more quickly than iterated /// application of the transfer function alone. The previous value is @@ -104,14 +114,17 @@ class Environment { /// serve as a comparison operation, by indicating whether the widened value /// is equivalent to the previous value. /// -/// Returns either: -/// -/// `nullptr`, if this value is not of interest to the model, or -/// -/// ``, if the widened value is equivalent to `Prev`, or -/// -/// A non-null value that approximates `Current`. `Prev` is available to -/// inform the chosen approximation. +/// Returns one of the folowing: +/// * `std::nullopt`, if this value is not of interest to the +/// model. +/// * A `WidenResult` with: +///* A non-null `Value *` that points either to `Current` or a widened +/// version of `Current`. This value must be consistent with +/// the flow condition of `CurrentEnv`. We particularly caution +/// against using `Prev`, which is rarely consistent. +///* A `LatticeJoinEffect` indicating whether the value should be +/// considered a new value (`Changed`) or one *equivalent* (if not +/// necessarily equal) to `Prev` (`Unchanged`). /// /// `PrevEnv` and `CurrentEnv` can be used to query child values and path /// condition implications of `Prev` and `Current`, respectively. @@ -122,17 +135,19 @@ class Environment { /// /// `Prev` and `Current` must be assigned to the same storage location in /// `PrevEnv` and `CurrentEnv`, respectively. -virtual Value *widen(QualType Type, Value , const Environment , - Value , Environment ) { +virtual std::optional widen(QualType Type, Value , + const Environment , + Value , + Environment ) { // The default implementation reduces to just comparison, since comparison // is required by the API, even if no widening is performed. switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) { -case ComparisonResult::Same: - return -case ComparisonResult::Different: - return -case ComparisonResult::Unknown: - return nullptr; + case ComparisonResult::Unknown: +return std::nullopt; + case ComparisonResult::Same: +return WidenResult{, LatticeJoinEffect::Unchanged}; + case ComparisonResult::Different: +return WidenResult{, LatticeJoinEffect::Changed}; } llvm_unreachable("all cases in switch covered"); } diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp index f729d676dd0de8..8ae51b7cdb444d 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -166,17 +166,20 @@ static Value *joinDistinctValues(QualType Type, Value , return JoinedVal; } -// When widening does not change `Current`, return value will equal ``. -static Value
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
ymand wrote: Martin, I've addressed all of your comments. PTAL. https://github.com/llvm/llvm-project/pull/87233 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -975,6 +994,35 @@ TEST_F(WideningTest, DistinctValuesWithSamePropertiesAreEquivalent) { }); } +TEST_F(WideningTest, DistinctValuesWithDifferentPropertiesWidenedToTop) { + std::string Code = R"( +void target(bool Cond) { + int *Foo; + int i = 0; + Foo = nullptr; + while (Cond) { +Foo = + } + (void)0; + /*[[p]]*/ +} + )"; + runDataflow( + Code, + [](const llvm::StringMap> , + ASTContext ) { +ASSERT_THAT(Results.keys(), UnorderedElementsAre("p")); +const Environment = getEnvironmentAtAnnotation(Results, "p"); + +const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo"); +ASSERT_THAT(FooDecl, NotNull()); + +const auto *FooVal = Env.getValue(*FooDecl); ymand wrote: Done https://github.com/llvm/llvm-project/pull/87233 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/87233 >From d8d875271bd47b71701143afb06ea654546e2b7c Mon Sep 17 00:00:00 2001 From: Yitzhak Mandelbaum Date: Mon, 1 Apr 2024 12:13:39 + Subject: [PATCH 1/3] [clang][dataflow] Refactor `widen` API to be explicit about change effect. The previous API relied on pointer equality of inputs and outputs to signal whether a change occured. This was too subtle and led to bugs in practice. It was also very limiting: the override could not return an equivalent (but not identical) value. --- .../FlowSensitive/DataflowEnvironment.h | 47 +++--- .../FlowSensitive/DataflowEnvironment.cpp | 43 ++--- .../TypeErasedDataflowAnalysisTest.cpp| 48 +++ 3 files changed, 104 insertions(+), 34 deletions(-) diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h index c30bccd06674a4..0a37d9d68e2898 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -97,6 +97,16 @@ class Environment { const Value , const Environment , Value , Environment ) {} +/// The result of the `widen` operation. +struct WidenResult { + /// Non-null pointer to a potentially widened version of the widening + /// input. + Value *V; + /// Whether `V` represents a "change" (that is, a different value) with + /// respect to the previous value in the sequence. + LatticeJoinEffect Effect; +}; + /// This function may widen the current value -- replace it with an /// approximation that can reach a fixed point more quickly than iterated /// application of the transfer function alone. The previous value is @@ -104,14 +114,17 @@ class Environment { /// serve as a comparison operation, by indicating whether the widened value /// is equivalent to the previous value. /// -/// Returns either: -/// -/// `nullptr`, if this value is not of interest to the model, or -/// -/// ``, if the widened value is equivalent to `Prev`, or -/// -/// A non-null value that approximates `Current`. `Prev` is available to -/// inform the chosen approximation. +/// Returns one of the folowing: +/// * `std::nullopt`, if this value is not of interest to the +/// model. +/// * A `WidenResult` with: +///* A non-null `Value *` that points either to `Current` or a widened +/// version of `Current`. This value must be consistent with +/// the flow condition of `CurrentEnv`. We particularly caution +/// against using `Prev`, which is rarely consistent. +///* A `LatticeJoinEffect` indicating whether the value should be +/// considered a new value (`Changed`) or one *equivalent* (if not +/// necessarily equal) to `Prev` (`Unchanged`). /// /// `PrevEnv` and `CurrentEnv` can be used to query child values and path /// condition implications of `Prev` and `Current`, respectively. @@ -122,17 +135,19 @@ class Environment { /// /// `Prev` and `Current` must be assigned to the same storage location in /// `PrevEnv` and `CurrentEnv`, respectively. -virtual Value *widen(QualType Type, Value , const Environment , - Value , Environment ) { +virtual std::optional widen(QualType Type, Value , + const Environment , + Value , + Environment ) { // The default implementation reduces to just comparison, since comparison // is required by the API, even if no widening is performed. switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) { -case ComparisonResult::Same: - return -case ComparisonResult::Different: - return -case ComparisonResult::Unknown: - return nullptr; + case ComparisonResult::Unknown: +return std::nullopt; + case ComparisonResult::Same: +return WidenResult{, LatticeJoinEffect::Unchanged}; + case ComparisonResult::Different: +return WidenResult{, LatticeJoinEffect::Changed}; } llvm_unreachable("all cases in switch covered"); } diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp index f729d676dd0de8..8ae51b7cdb444d 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -166,17 +166,20 @@ static Value *joinDistinctValues(QualType Type, Value , return JoinedVal; } -// When widening does not change `Current`, return value will equal ``. -static Value
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/87233 >From d8d875271bd47b71701143afb06ea654546e2b7c Mon Sep 17 00:00:00 2001 From: Yitzhak Mandelbaum Date: Mon, 1 Apr 2024 12:13:39 + Subject: [PATCH 1/2] [clang][dataflow] Refactor `widen` API to be explicit about change effect. The previous API relied on pointer equality of inputs and outputs to signal whether a change occured. This was too subtle and led to bugs in practice. It was also very limiting: the override could not return an equivalent (but not identical) value. --- .../FlowSensitive/DataflowEnvironment.h | 47 +++--- .../FlowSensitive/DataflowEnvironment.cpp | 43 ++--- .../TypeErasedDataflowAnalysisTest.cpp| 48 +++ 3 files changed, 104 insertions(+), 34 deletions(-) diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h index c30bccd06674a4..0a37d9d68e2898 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -97,6 +97,16 @@ class Environment { const Value , const Environment , Value , Environment ) {} +/// The result of the `widen` operation. +struct WidenResult { + /// Non-null pointer to a potentially widened version of the widening + /// input. + Value *V; + /// Whether `V` represents a "change" (that is, a different value) with + /// respect to the previous value in the sequence. + LatticeJoinEffect Effect; +}; + /// This function may widen the current value -- replace it with an /// approximation that can reach a fixed point more quickly than iterated /// application of the transfer function alone. The previous value is @@ -104,14 +114,17 @@ class Environment { /// serve as a comparison operation, by indicating whether the widened value /// is equivalent to the previous value. /// -/// Returns either: -/// -/// `nullptr`, if this value is not of interest to the model, or -/// -/// ``, if the widened value is equivalent to `Prev`, or -/// -/// A non-null value that approximates `Current`. `Prev` is available to -/// inform the chosen approximation. +/// Returns one of the folowing: +/// * `std::nullopt`, if this value is not of interest to the +/// model. +/// * A `WidenResult` with: +///* A non-null `Value *` that points either to `Current` or a widened +/// version of `Current`. This value must be consistent with +/// the flow condition of `CurrentEnv`. We particularly caution +/// against using `Prev`, which is rarely consistent. +///* A `LatticeJoinEffect` indicating whether the value should be +/// considered a new value (`Changed`) or one *equivalent* (if not +/// necessarily equal) to `Prev` (`Unchanged`). /// /// `PrevEnv` and `CurrentEnv` can be used to query child values and path /// condition implications of `Prev` and `Current`, respectively. @@ -122,17 +135,19 @@ class Environment { /// /// `Prev` and `Current` must be assigned to the same storage location in /// `PrevEnv` and `CurrentEnv`, respectively. -virtual Value *widen(QualType Type, Value , const Environment , - Value , Environment ) { +virtual std::optional widen(QualType Type, Value , + const Environment , + Value , + Environment ) { // The default implementation reduces to just comparison, since comparison // is required by the API, even if no widening is performed. switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) { -case ComparisonResult::Same: - return -case ComparisonResult::Different: - return -case ComparisonResult::Unknown: - return nullptr; + case ComparisonResult::Unknown: +return std::nullopt; + case ComparisonResult::Same: +return WidenResult{, LatticeJoinEffect::Unchanged}; + case ComparisonResult::Different: +return WidenResult{, LatticeJoinEffect::Changed}; } llvm_unreachable("all cases in switch covered"); } diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp index f729d676dd0de8..8ae51b7cdb444d 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -166,17 +166,20 @@ static Value *joinDistinctValues(QualType Type, Value , return JoinedVal; } -// When widening does not change `Current`, return value will equal ``. -static Value
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -975,6 +994,35 @@ TEST_F(WideningTest, DistinctValuesWithSamePropertiesAreEquivalent) { }); } +TEST_F(WideningTest, DistinctValuesWithDifferentPropertiesWidenedToTop) { + std::string Code = R"( +void target(bool Cond) { + int *Foo; + int i = 0; + Foo = nullptr; + while (Cond) { +Foo = + } + (void)0; + /*[[p]]*/ +} + )"; + runDataflow( + Code, + [](const llvm::StringMap> , + ASTContext ) { +ASSERT_THAT(Results.keys(), UnorderedElementsAre("p")); +const Environment = getEnvironmentAtAnnotation(Results, "p"); + +const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo"); +ASSERT_THAT(FooDecl, NotNull()); + +const auto *FooVal = Env.getValue(*FooDecl); +EXPECT_TRUE(areEquivalentValues(*FooVal->getProperty("is_null"), ymand wrote: I prefer direct assertion, because it results in a cleaner error message on failure (crashing the test process vs exiting the test with a test-assertion failure). https://github.com/llvm/llvm-project/pull/87233 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -975,6 +994,35 @@ TEST_F(WideningTest, DistinctValuesWithSamePropertiesAreEquivalent) { }); } +TEST_F(WideningTest, DistinctValuesWithDifferentPropertiesWidenedToTop) { + std::string Code = R"( +void target(bool Cond) { + int *Foo; + int i = 0; + Foo = nullptr; + while (Cond) { +Foo = + } + (void)0; + /*[[p]]*/ +} + )"; + runDataflow( + Code, + [](const llvm::StringMap> , + ASTContext ) { +ASSERT_THAT(Results.keys(), UnorderedElementsAre("p")); ymand wrote: Great. I've removed it here and in all other cases of WideningTest. https://github.com/llvm/llvm-project/pull/87233 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -805,6 +805,25 @@ class NullPointerAnalysis final else JoinedVal.setProperty("is_null", JoinedEnv.makeTopBoolValue()); } + + std::optional widen(QualType Type, Value , + const Environment , Value , + Environment ) override { ymand wrote: I added this so that we can test the widening functionality. Turns out we had no tests for framework calls to `widen`. https://github.com/llvm/llvm-project/pull/87233 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
@@ -122,17 +135,19 @@ class Environment { /// /// `Prev` and `Current` must be assigned to the same storage location in /// `PrevEnv` and `CurrentEnv`, respectively. -virtual Value *widen(QualType Type, Value , const Environment , - Value , Environment ) { +virtual std::optional widen(QualType Type, Value , ymand wrote: That's the *only* override I could find. So, I think we'll just prepare a patch to crubit to coincide with pushing this. https://github.com/llvm/llvm-project/pull/87233 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/87233 >From d8d875271bd47b71701143afb06ea654546e2b7c Mon Sep 17 00:00:00 2001 From: Yitzhak Mandelbaum Date: Mon, 1 Apr 2024 12:13:39 + Subject: [PATCH] [clang][dataflow] Refactor `widen` API to be explicit about change effect. The previous API relied on pointer equality of inputs and outputs to signal whether a change occured. This was too subtle and led to bugs in practice. It was also very limiting: the override could not return an equivalent (but not identical) value. --- .../FlowSensitive/DataflowEnvironment.h | 47 +++--- .../FlowSensitive/DataflowEnvironment.cpp | 43 ++--- .../TypeErasedDataflowAnalysisTest.cpp| 48 +++ 3 files changed, 104 insertions(+), 34 deletions(-) diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h index c30bccd06674a4..0a37d9d68e2898 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -97,6 +97,16 @@ class Environment { const Value , const Environment , Value , Environment ) {} +/// The result of the `widen` operation. +struct WidenResult { + /// Non-null pointer to a potentially widened version of the widening + /// input. + Value *V; + /// Whether `V` represents a "change" (that is, a different value) with + /// respect to the previous value in the sequence. + LatticeJoinEffect Effect; +}; + /// This function may widen the current value -- replace it with an /// approximation that can reach a fixed point more quickly than iterated /// application of the transfer function alone. The previous value is @@ -104,14 +114,17 @@ class Environment { /// serve as a comparison operation, by indicating whether the widened value /// is equivalent to the previous value. /// -/// Returns either: -/// -/// `nullptr`, if this value is not of interest to the model, or -/// -/// ``, if the widened value is equivalent to `Prev`, or -/// -/// A non-null value that approximates `Current`. `Prev` is available to -/// inform the chosen approximation. +/// Returns one of the folowing: +/// * `std::nullopt`, if this value is not of interest to the +/// model. +/// * A `WidenResult` with: +///* A non-null `Value *` that points either to `Current` or a widened +/// version of `Current`. This value must be consistent with +/// the flow condition of `CurrentEnv`. We particularly caution +/// against using `Prev`, which is rarely consistent. +///* A `LatticeJoinEffect` indicating whether the value should be +/// considered a new value (`Changed`) or one *equivalent* (if not +/// necessarily equal) to `Prev` (`Unchanged`). /// /// `PrevEnv` and `CurrentEnv` can be used to query child values and path /// condition implications of `Prev` and `Current`, respectively. @@ -122,17 +135,19 @@ class Environment { /// /// `Prev` and `Current` must be assigned to the same storage location in /// `PrevEnv` and `CurrentEnv`, respectively. -virtual Value *widen(QualType Type, Value , const Environment , - Value , Environment ) { +virtual std::optional widen(QualType Type, Value , + const Environment , + Value , + Environment ) { // The default implementation reduces to just comparison, since comparison // is required by the API, even if no widening is performed. switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) { -case ComparisonResult::Same: - return -case ComparisonResult::Different: - return -case ComparisonResult::Unknown: - return nullptr; + case ComparisonResult::Unknown: +return std::nullopt; + case ComparisonResult::Same: +return WidenResult{, LatticeJoinEffect::Unchanged}; + case ComparisonResult::Different: +return WidenResult{, LatticeJoinEffect::Changed}; } llvm_unreachable("all cases in switch covered"); } diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp index f729d676dd0de8..8ae51b7cdb444d 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -166,17 +166,20 @@ static Value *joinDistinctValues(QualType Type, Value , return JoinedVal; } -// When widening does not change `Current`, return value will equal ``. -static Value
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/87233 >From b7f63ed7ca3c503f55eccc215f0a66368e2c5e5e Mon Sep 17 00:00:00 2001 From: Yitzhak Mandelbaum Date: Mon, 1 Apr 2024 12:13:39 + Subject: [PATCH] [clang][dataflow] Refactor `widen` API to be explicit about change effect. The previous API relied on pointer equality of inputs and outputs to signal whether a change occured. This was too subtle and led to bugs in practice. It was also very limiting: the override could not return an equivalent (but not identical) value. --- .../FlowSensitive/DataflowEnvironment.h | 47 --- .../FlowSensitive/DataflowEnvironment.cpp | 43 ++--- 2 files changed, 56 insertions(+), 34 deletions(-) diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h index c30bccd06674a4..0a37d9d68e2898 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -97,6 +97,16 @@ class Environment { const Value , const Environment , Value , Environment ) {} +/// The result of the `widen` operation. +struct WidenResult { + /// Non-null pointer to a potentially widened version of the widening + /// input. + Value *V; + /// Whether `V` represents a "change" (that is, a different value) with + /// respect to the previous value in the sequence. + LatticeJoinEffect Effect; +}; + /// This function may widen the current value -- replace it with an /// approximation that can reach a fixed point more quickly than iterated /// application of the transfer function alone. The previous value is @@ -104,14 +114,17 @@ class Environment { /// serve as a comparison operation, by indicating whether the widened value /// is equivalent to the previous value. /// -/// Returns either: -/// -/// `nullptr`, if this value is not of interest to the model, or -/// -/// ``, if the widened value is equivalent to `Prev`, or -/// -/// A non-null value that approximates `Current`. `Prev` is available to -/// inform the chosen approximation. +/// Returns one of the folowing: +/// * `std::nullopt`, if this value is not of interest to the +/// model. +/// * A `WidenResult` with: +///* A non-null `Value *` that points either to `Current` or a widened +/// version of `Current`. This value must be consistent with +/// the flow condition of `CurrentEnv`. We particularly caution +/// against using `Prev`, which is rarely consistent. +///* A `LatticeJoinEffect` indicating whether the value should be +/// considered a new value (`Changed`) or one *equivalent* (if not +/// necessarily equal) to `Prev` (`Unchanged`). /// /// `PrevEnv` and `CurrentEnv` can be used to query child values and path /// condition implications of `Prev` and `Current`, respectively. @@ -122,17 +135,19 @@ class Environment { /// /// `Prev` and `Current` must be assigned to the same storage location in /// `PrevEnv` and `CurrentEnv`, respectively. -virtual Value *widen(QualType Type, Value , const Environment , - Value , Environment ) { +virtual std::optional widen(QualType Type, Value , + const Environment , + Value , + Environment ) { // The default implementation reduces to just comparison, since comparison // is required by the API, even if no widening is performed. switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) { -case ComparisonResult::Same: - return -case ComparisonResult::Different: - return -case ComparisonResult::Unknown: - return nullptr; + case ComparisonResult::Unknown: +return std::nullopt; + case ComparisonResult::Same: +return WidenResult{, LatticeJoinEffect::Unchanged}; + case ComparisonResult::Different: +return WidenResult{, LatticeJoinEffect::Changed}; } llvm_unreachable("all cases in switch covered"); } diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp index f729d676dd0de8..8ae51b7cdb444d 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -166,17 +166,20 @@ static Value *joinDistinctValues(QualType Type, Value , return JoinedVal; } -// When widening does not change `Current`, return value will equal ``. -static Value (QualType Type, Value , - const
[clang] [clang][dataflow] Refactor `widen` API to be explicit about change effect. (PR #87233)
https://github.com/ymand created https://github.com/llvm/llvm-project/pull/87233 The previous API relied on pointer equality of inputs and outputs to signal whether a change occured. This was too subtle and led to bugs in practice. It was also very limiting: the override could not return an equivalent (but not identical) value. >From 6889df911a11fc5c27149f138176166aef3e1f73 Mon Sep 17 00:00:00 2001 From: Yitzhak Mandelbaum Date: Mon, 1 Apr 2024 12:13:39 + Subject: [PATCH] [clang][dataflow] Refactor `widen` API to be explicit about change effect. The previous API relied on pointer equality of inputs and outputs to signal whether a change occured. This was too subtle and led to bugs in practice. It was also very limiting: the override could not return an equivalent (but not identical) value. --- .../FlowSensitive/DataflowEnvironment.h | 43 +-- .../FlowSensitive/DataflowEnvironment.cpp | 42 ++ 2 files changed, 53 insertions(+), 32 deletions(-) diff --git a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h index c30bccd06674a4..8e4e846e594f5b 100644 --- a/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h +++ b/clang/include/clang/Analysis/FlowSensitive/DataflowEnvironment.h @@ -97,6 +97,16 @@ class Environment { const Value , const Environment , Value , Environment ) {} +/// The result of the `widen` operation. +struct WidenResult { + /// Non-null pointer to a potentially widened version of the widening + /// input. + Value *V; + /// Whether `V` represents a "change" (that is, a different value) with + /// respect to the previous value in the sequence. + LatticeJoinEffect Effect; +}; + /// This function may widen the current value -- replace it with an /// approximation that can reach a fixed point more quickly than iterated /// application of the transfer function alone. The previous value is @@ -104,14 +114,17 @@ class Environment { /// serve as a comparison operation, by indicating whether the widened value /// is equivalent to the previous value. /// -/// Returns either: -/// -/// `nullptr`, if this value is not of interest to the model, or -/// -/// ``, if the widened value is equivalent to `Prev`, or -/// -/// A non-null value that approximates `Current`. `Prev` is available to -/// inform the chosen approximation. +/// Returns one of the folowing: +/// * `std::nullopt`, if this value is not of interest to the +/// model. +/// * A `WidenResult` with: +///* A non-null `Value *` that points either to `Current` or a widened +/// version of `Current`. This value must be consistent with +/// the flow condition of `CurrentEnv`. We particularly caution +/// against using `Prev`, which is rarely consistent. +///* A `LatticeJoinEffect` indicating whether the value should be +/// considered a new value (`Changed`) or one *equivalent* (if not +/// necessarily equal) to `Prev` (`Unchanged`). /// /// `PrevEnv` and `CurrentEnv` can be used to query child values and path /// condition implications of `Prev` and `Current`, respectively. @@ -122,17 +135,19 @@ class Environment { /// /// `Prev` and `Current` must be assigned to the same storage location in /// `PrevEnv` and `CurrentEnv`, respectively. -virtual Value *widen(QualType Type, Value , const Environment , - Value , Environment ) { +virtual std::optional widen(QualType Type, Value , + const Environment , + Value , + Environment ) { // The default implementation reduces to just comparison, since comparison // is required by the API, even if no widening is performed. switch (compare(Type, Prev, PrevEnv, Current, CurrentEnv)) { +case ComparisonResult::Unknown: + return std::nullopt; case ComparisonResult::Same: - return + return WidenResult{, LatticeJoinEffect::Unchanged}; case ComparisonResult::Different: - return -case ComparisonResult::Unknown: - return nullptr; + return WidenResult{, LatticeJoinEffect::Changed}; } llvm_unreachable("all cases in switch covered"); } diff --git a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp index f729d676dd0de8..d41f03262ecf4c 100644 --- a/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp +++ b/clang/lib/Analysis/FlowSensitive/DataflowEnvironment.cpp @@ -166,17 +166,19 @@ static Value *joinDistinctValues(QualType Type, Value ,
[clang] [clang][dataflow] Fix for value constructor in class derived from optional. (PR #86942)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/86942 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Introduce a helper class for handling record initializer lists. (PR #86675)
@@ -744,6 +744,35 @@ RecordStorageLocation *getBaseObjectLocation(const MemberExpr , std::vector getFieldsForInitListExpr(const InitListExpr *InitList); +/// Helper class for initialization of a record with an `InitListExpr`. +/// `InitListExpr::inits()` contains the initializers for both the base classes +/// and the fields of the record; this helper class separates these out into two +/// different lists. In addition, it deals with special cases associated with +/// unions. +class RecordInitListHelper { ymand wrote: Why an object vs something like: ``` struct RecordInits { SmallVector> BaseInits; SmallVector> FieldInits; }; RecordInits RecordInitListHelper(const InitListExpr *InitList); ``` Is it because of the optional storage needed for the union? https://github.com/llvm/llvm-project/pull/86675 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Introduce a helper class for handling record initializer lists. (PR #86675)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/86675 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Introduce a helper class for handling record initializer lists. (PR #86675)
https://github.com/ymand edited https://github.com/llvm/llvm-project/pull/86675 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Bail out if input is Objective-C++. (PR #86479)
https://github.com/ymand approved this pull request. Thanks! https://github.com/llvm/llvm-project/pull/86479 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Factor out built-in boolean model into an explicit module. (PR #82950)
@@ -50,29 +50,206 @@ const Environment *StmtToEnvMap::getEnvironment(const Stmt ) const { return >Env; } -static BoolValue (const Expr , const Expr , - Environment ) { - Value *LHSValue = Env.getValue(LHS); - Value *RHSValue = Env.getValue(RHS); +static BoolValue (BoolValue , Environment ) { + if (auto *Top = llvm::dyn_cast()) { +auto = Env.getDataflowAnalysisContext().arena(); +return A.makeBoolValue(A.makeAtomRef(Top->getAtom())); + } + return V; +} - if (LHSValue == RHSValue) -return Env.getBoolLiteralValue(true); +static void propagateValue(const Expr , const Expr , Environment ) { + if (auto *Val = Env.getValue(From)) +Env.setValue(To, *Val); +} - if (auto *LHSBool = dyn_cast_or_null(LHSValue)) -if (auto *RHSBool = dyn_cast_or_null(RHSValue)) - return Env.makeIff(*LHSBool, *RHSBool); +static void propagateStorageLocation(const Expr , const Expr , + Environment ) { + if (auto *Loc = Env.getStorageLocation(From)) +Env.setStorageLocation(To, *Loc); +} + +// Propagates the value or storage location of `From` to `To` in cases where +// `From` may be either a glvalue or a prvalue. `To` must be a glvalue iff +// `From` is a glvalue. +static void propagateValueOrStorageLocation(const Expr , const Expr , +Environment ) { + assert(From.isGLValue() == To.isGLValue()); + if (From.isGLValue()) +propagateStorageLocation(From, To, Env); + else +propagateValue(From, To, Env); +} +namespace sat_bool_model { + +BoolValue (Environment ) { return Env.makeAtomicBoolValue(); } -static BoolValue (BoolValue , Environment ) { - if (auto *Top = llvm::dyn_cast()) { -auto = Env.getDataflowAnalysisContext().arena(); -return A.makeBoolValue(A.makeAtomRef(Top->getAtom())); +BoolValue (BoolValue , Environment ) { + return unpackValue(V, Env); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeOr(LHS, RHS); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeAnd(LHS, RHS); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeIff(LHS, RHS); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeNot(Env.makeIff(LHS, RHS)); +} + +BoolValue (BoolValue , Environment ) { return Env.makeNot(Sub); } + +void transferBranch(bool BranchVal, BoolValue , Environment ) { + // The condition must be inverted for the successor that encompasses the + // "else" branch, if such exists. + BoolValue = BranchVal ? CondVal : Env.makeNot(CondVal); + Env.assume(AssertedVal.formula()); +} + +} // namespace sat_bool_model + +namespace simple_bool_model { + +std::optional getLiteralValue(const Formula , const Environment ) { + switch (F.kind()) { + case Formula::AtomRef: +return Env.getAtomValue(F.getAtom()); + case Formula::Literal: +return F.literal(); + case Formula::Not: { ymand wrote: Sorry, this got clobbered when I pushed after a rebase. But, this was on the function `getLiteralValue` (now in DataflowEnvironment.cpp) and I don't think the original concerns apply, since we now support And and Or, etc. https://github.com/llvm/llvm-project/pull/82950 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Factor out built-in boolean model into an explicit module. (PR #82950)
https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/82950 >From 33f753d99bbb477ad37614d29658e964aa590a80 Mon Sep 17 00:00:00 2001 From: Yitzhak Mandelbaum Date: Fri, 23 Feb 2024 20:15:36 + Subject: [PATCH 1/3] [clang][dataflow] Factor out built-in boolean model into an explicit module. In the process, drastically simplify the handling of terminators. --- .../clang/Analysis/FlowSensitive/Transfer.h | 24 +++ clang/lib/Analysis/FlowSensitive/Transfer.cpp | 144 -- 2 files changed, 124 insertions(+), 44 deletions(-) diff --git a/clang/include/clang/Analysis/FlowSensitive/Transfer.h b/clang/include/clang/Analysis/FlowSensitive/Transfer.h index ed148250d8eb29..bc8e9cdb03d703 100644 --- a/clang/include/clang/Analysis/FlowSensitive/Transfer.h +++ b/clang/include/clang/Analysis/FlowSensitive/Transfer.h @@ -48,6 +48,30 @@ class StmtToEnvMap { const TypeErasedDataflowAnalysisState }; +namespace bool_model { + +BoolValue (Environment ); + +BoolValue (BoolValue , Environment ); + +BoolValue (BoolValue , BoolValue , Environment ); + +BoolValue (BoolValue , BoolValue , Environment ); + +BoolValue (BoolValue , BoolValue , Environment ); + +BoolValue (BoolValue , BoolValue , Environment ); + +BoolValue (BoolValue , Environment ); + +// Models the transition along a branch edge in the CFG. +// BranchVal -- the concrete, dynamic branch value -- true for `then` and false +// for `else`. +// CondVal -- the abstract value representing the condition. +void transferBranch(bool BranchVal, BoolValue , Environment ); + +} // namespace bool_model + /// Evaluates `S` and updates `Env` accordingly. /// /// Requirements: diff --git a/clang/lib/Analysis/FlowSensitive/Transfer.cpp b/clang/lib/Analysis/FlowSensitive/Transfer.cpp index 960e9688ffb725..6e215daaf3fa19 100644 --- a/clang/lib/Analysis/FlowSensitive/Transfer.cpp +++ b/clang/lib/Analysis/FlowSensitive/Transfer.cpp @@ -50,21 +50,6 @@ const Environment *StmtToEnvMap::getEnvironment(const Stmt ) const { return >Env; } -static BoolValue (const Expr , const Expr , - Environment ) { - Value *LHSValue = Env.getValue(LHS); - Value *RHSValue = Env.getValue(RHS); - - if (LHSValue == RHSValue) -return Env.getBoolLiteralValue(true); - - if (auto *LHSBool = dyn_cast_or_null(LHSValue)) -if (auto *RHSBool = dyn_cast_or_null(RHSValue)) - return Env.makeIff(*LHSBool, *RHSBool); - - return Env.makeAtomicBoolValue(); -} - static BoolValue (BoolValue , Environment ) { if (auto *Top = llvm::dyn_cast()) { auto = Env.getDataflowAnalysisContext().arena(); @@ -73,6 +58,68 @@ static BoolValue (BoolValue , Environment ) { return V; } +static void propagateValue(const Expr , const Expr , Environment ) { + if (auto *Val = Env.getValue(From)) +Env.setValue(To, *Val); +} + +static void propagateStorageLocation(const Expr , const Expr , + Environment ) { + if (auto *Loc = Env.getStorageLocation(From)) +Env.setStorageLocation(To, *Loc); +} + +// Propagates the value or storage location of `From` to `To` in cases where +// `From` may be either a glvalue or a prvalue. `To` must be a glvalue iff +// `From` is a glvalue. +static void propagateValueOrStorageLocation(const Expr , const Expr , +Environment ) { + assert(From.isGLValue() == To.isGLValue()); + if (From.isGLValue()) +propagateStorageLocation(From, To, Env); + else +propagateValue(From, To, Env); +} + +namespace bool_model { + +BoolValue (Environment ) { + return Env.makeAtomicBoolValue(); +} + +BoolValue (BoolValue , Environment ) { + return unpackValue(V, Env); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeOr(LHS, RHS); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeAnd(LHS, RHS); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeIff(LHS, RHS); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeNot(Env.makeIff(LHS, RHS)); +} + +BoolValue (BoolValue , Environment ) { return Env.makeNot(Sub); } + +void transferBranch(bool BranchVal, BoolValue , Environment ) { + if (BranchVal) +Env.assume(CondVal.formula()); + else +// The condition must be inverted for the successor that encompasses the +// "else" branch, if such exists. +Env.assume(Env.makeNot(CondVal).formula()); +} + +} // namespace bool_model + // Unpacks the value (if any) associated with `E` and updates `E` to the new // value, if any unpacking occured. Also, does the lvalue-to-rvalue conversion, // by skipping past the reference. @@ -86,34 +133,45 @@ static Value *maybeUnpackLValueExpr(const Expr , Environment ) { if (B == nullptr) return Val; - auto = unpackValue(*B, Env); + auto = bool_model::rValueFromLValue(*B, Env); if ( == Val) return Val; Env.setValue(*Loc, UnpackedVal); return }
[clang] [clang][dataflow] Factor out built-in boolean model into an explicit module. (PR #82950)
https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/82950 >From 33f753d99bbb477ad37614d29658e964aa590a80 Mon Sep 17 00:00:00 2001 From: Yitzhak Mandelbaum Date: Fri, 23 Feb 2024 20:15:36 + Subject: [PATCH 1/3] [clang][dataflow] Factor out built-in boolean model into an explicit module. In the process, drastically simplify the handling of terminators. --- .../clang/Analysis/FlowSensitive/Transfer.h | 24 +++ clang/lib/Analysis/FlowSensitive/Transfer.cpp | 144 -- 2 files changed, 124 insertions(+), 44 deletions(-) diff --git a/clang/include/clang/Analysis/FlowSensitive/Transfer.h b/clang/include/clang/Analysis/FlowSensitive/Transfer.h index ed148250d8eb29..bc8e9cdb03d703 100644 --- a/clang/include/clang/Analysis/FlowSensitive/Transfer.h +++ b/clang/include/clang/Analysis/FlowSensitive/Transfer.h @@ -48,6 +48,30 @@ class StmtToEnvMap { const TypeErasedDataflowAnalysisState }; +namespace bool_model { + +BoolValue (Environment ); + +BoolValue (BoolValue , Environment ); + +BoolValue (BoolValue , BoolValue , Environment ); + +BoolValue (BoolValue , BoolValue , Environment ); + +BoolValue (BoolValue , BoolValue , Environment ); + +BoolValue (BoolValue , BoolValue , Environment ); + +BoolValue (BoolValue , Environment ); + +// Models the transition along a branch edge in the CFG. +// BranchVal -- the concrete, dynamic branch value -- true for `then` and false +// for `else`. +// CondVal -- the abstract value representing the condition. +void transferBranch(bool BranchVal, BoolValue , Environment ); + +} // namespace bool_model + /// Evaluates `S` and updates `Env` accordingly. /// /// Requirements: diff --git a/clang/lib/Analysis/FlowSensitive/Transfer.cpp b/clang/lib/Analysis/FlowSensitive/Transfer.cpp index 960e9688ffb725..6e215daaf3fa19 100644 --- a/clang/lib/Analysis/FlowSensitive/Transfer.cpp +++ b/clang/lib/Analysis/FlowSensitive/Transfer.cpp @@ -50,21 +50,6 @@ const Environment *StmtToEnvMap::getEnvironment(const Stmt ) const { return >Env; } -static BoolValue (const Expr , const Expr , - Environment ) { - Value *LHSValue = Env.getValue(LHS); - Value *RHSValue = Env.getValue(RHS); - - if (LHSValue == RHSValue) -return Env.getBoolLiteralValue(true); - - if (auto *LHSBool = dyn_cast_or_null(LHSValue)) -if (auto *RHSBool = dyn_cast_or_null(RHSValue)) - return Env.makeIff(*LHSBool, *RHSBool); - - return Env.makeAtomicBoolValue(); -} - static BoolValue (BoolValue , Environment ) { if (auto *Top = llvm::dyn_cast()) { auto = Env.getDataflowAnalysisContext().arena(); @@ -73,6 +58,68 @@ static BoolValue (BoolValue , Environment ) { return V; } +static void propagateValue(const Expr , const Expr , Environment ) { + if (auto *Val = Env.getValue(From)) +Env.setValue(To, *Val); +} + +static void propagateStorageLocation(const Expr , const Expr , + Environment ) { + if (auto *Loc = Env.getStorageLocation(From)) +Env.setStorageLocation(To, *Loc); +} + +// Propagates the value or storage location of `From` to `To` in cases where +// `From` may be either a glvalue or a prvalue. `To` must be a glvalue iff +// `From` is a glvalue. +static void propagateValueOrStorageLocation(const Expr , const Expr , +Environment ) { + assert(From.isGLValue() == To.isGLValue()); + if (From.isGLValue()) +propagateStorageLocation(From, To, Env); + else +propagateValue(From, To, Env); +} + +namespace bool_model { + +BoolValue (Environment ) { + return Env.makeAtomicBoolValue(); +} + +BoolValue (BoolValue , Environment ) { + return unpackValue(V, Env); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeOr(LHS, RHS); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeAnd(LHS, RHS); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeIff(LHS, RHS); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeNot(Env.makeIff(LHS, RHS)); +} + +BoolValue (BoolValue , Environment ) { return Env.makeNot(Sub); } + +void transferBranch(bool BranchVal, BoolValue , Environment ) { + if (BranchVal) +Env.assume(CondVal.formula()); + else +// The condition must be inverted for the successor that encompasses the +// "else" branch, if such exists. +Env.assume(Env.makeNot(CondVal).formula()); +} + +} // namespace bool_model + // Unpacks the value (if any) associated with `E` and updates `E` to the new // value, if any unpacking occured. Also, does the lvalue-to-rvalue conversion, // by skipping past the reference. @@ -86,34 +133,45 @@ static Value *maybeUnpackLValueExpr(const Expr , Environment ) { if (B == nullptr) return Val; - auto = unpackValue(*B, Env); + auto = bool_model::rValueFromLValue(*B, Env); if ( == Val) return Val; Env.setValue(*Loc, UnpackedVal); return }
[clang] [clang][dataflow] Factor out built-in boolean model into an explicit module. (PR #82950)
ymand wrote: Martin, I've thoroughly updated the refactoring, exactly as you suggested -- all of the interesting differences are actually just in how we handle the logical operations, so most of the changes are now in DataflowEnvironment.cpp. I've left the factoring in Transfer because we may want it for the future -- these two models both use formulae, but other implementations could differ. The test failures are down to 35 and all they are all WAI -- places where we have genuine differences between the models, primarily around encoding custom API properties with formulae. https://github.com/llvm/llvm-project/pull/82950 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Factor out built-in boolean model into an explicit module. (PR #82950)
@@ -1059,9 +1066,16 @@ void Environment::assume(const Formula ) { DACtx->addFlowConditionConstraint(FlowConditionToken, F); } +#if 0 bool Environment::proves(const Formula ) const { return DACtx->flowConditionImplies(FlowConditionToken, F); } +#else +bool Environment::proves(const Formula ) const { + auto V = simple_bool_model::getLiteralValue(F, *this); + return V.has_value() && *V; +} +#endif bool Environment::allows(const Formula ) const { return DACtx->flowConditionAllows(FlowConditionToken, F); ymand wrote: Yes, but not to `proves`: it should be `value_or(true)` -- that is, if we lack any definite setting, we "allow" it to be anything. https://github.com/llvm/llvm-project/pull/82950 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Factor out built-in boolean model into an explicit module. (PR #82950)
https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/82950 >From 33f753d99bbb477ad37614d29658e964aa590a80 Mon Sep 17 00:00:00 2001 From: Yitzhak Mandelbaum Date: Fri, 23 Feb 2024 20:15:36 + Subject: [PATCH 1/3] [clang][dataflow] Factor out built-in boolean model into an explicit module. In the process, drastically simplify the handling of terminators. --- .../clang/Analysis/FlowSensitive/Transfer.h | 24 +++ clang/lib/Analysis/FlowSensitive/Transfer.cpp | 144 -- 2 files changed, 124 insertions(+), 44 deletions(-) diff --git a/clang/include/clang/Analysis/FlowSensitive/Transfer.h b/clang/include/clang/Analysis/FlowSensitive/Transfer.h index ed148250d8eb29..bc8e9cdb03d703 100644 --- a/clang/include/clang/Analysis/FlowSensitive/Transfer.h +++ b/clang/include/clang/Analysis/FlowSensitive/Transfer.h @@ -48,6 +48,30 @@ class StmtToEnvMap { const TypeErasedDataflowAnalysisState }; +namespace bool_model { + +BoolValue (Environment ); + +BoolValue (BoolValue , Environment ); + +BoolValue (BoolValue , BoolValue , Environment ); + +BoolValue (BoolValue , BoolValue , Environment ); + +BoolValue (BoolValue , BoolValue , Environment ); + +BoolValue (BoolValue , BoolValue , Environment ); + +BoolValue (BoolValue , Environment ); + +// Models the transition along a branch edge in the CFG. +// BranchVal -- the concrete, dynamic branch value -- true for `then` and false +// for `else`. +// CondVal -- the abstract value representing the condition. +void transferBranch(bool BranchVal, BoolValue , Environment ); + +} // namespace bool_model + /// Evaluates `S` and updates `Env` accordingly. /// /// Requirements: diff --git a/clang/lib/Analysis/FlowSensitive/Transfer.cpp b/clang/lib/Analysis/FlowSensitive/Transfer.cpp index 960e9688ffb725..6e215daaf3fa19 100644 --- a/clang/lib/Analysis/FlowSensitive/Transfer.cpp +++ b/clang/lib/Analysis/FlowSensitive/Transfer.cpp @@ -50,21 +50,6 @@ const Environment *StmtToEnvMap::getEnvironment(const Stmt ) const { return >Env; } -static BoolValue (const Expr , const Expr , - Environment ) { - Value *LHSValue = Env.getValue(LHS); - Value *RHSValue = Env.getValue(RHS); - - if (LHSValue == RHSValue) -return Env.getBoolLiteralValue(true); - - if (auto *LHSBool = dyn_cast_or_null(LHSValue)) -if (auto *RHSBool = dyn_cast_or_null(RHSValue)) - return Env.makeIff(*LHSBool, *RHSBool); - - return Env.makeAtomicBoolValue(); -} - static BoolValue (BoolValue , Environment ) { if (auto *Top = llvm::dyn_cast()) { auto = Env.getDataflowAnalysisContext().arena(); @@ -73,6 +58,68 @@ static BoolValue (BoolValue , Environment ) { return V; } +static void propagateValue(const Expr , const Expr , Environment ) { + if (auto *Val = Env.getValue(From)) +Env.setValue(To, *Val); +} + +static void propagateStorageLocation(const Expr , const Expr , + Environment ) { + if (auto *Loc = Env.getStorageLocation(From)) +Env.setStorageLocation(To, *Loc); +} + +// Propagates the value or storage location of `From` to `To` in cases where +// `From` may be either a glvalue or a prvalue. `To` must be a glvalue iff +// `From` is a glvalue. +static void propagateValueOrStorageLocation(const Expr , const Expr , +Environment ) { + assert(From.isGLValue() == To.isGLValue()); + if (From.isGLValue()) +propagateStorageLocation(From, To, Env); + else +propagateValue(From, To, Env); +} + +namespace bool_model { + +BoolValue (Environment ) { + return Env.makeAtomicBoolValue(); +} + +BoolValue (BoolValue , Environment ) { + return unpackValue(V, Env); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeOr(LHS, RHS); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeAnd(LHS, RHS); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeIff(LHS, RHS); +} + +BoolValue (BoolValue , BoolValue , Environment ) { + return Env.makeNot(Env.makeIff(LHS, RHS)); +} + +BoolValue (BoolValue , Environment ) { return Env.makeNot(Sub); } + +void transferBranch(bool BranchVal, BoolValue , Environment ) { + if (BranchVal) +Env.assume(CondVal.formula()); + else +// The condition must be inverted for the successor that encompasses the +// "else" branch, if such exists. +Env.assume(Env.makeNot(CondVal).formula()); +} + +} // namespace bool_model + // Unpacks the value (if any) associated with `E` and updates `E` to the new // value, if any unpacking occured. Also, does the lvalue-to-rvalue conversion, // by skipping past the reference. @@ -86,34 +133,45 @@ static Value *maybeUnpackLValueExpr(const Expr , Environment ) { if (B == nullptr) return Val; - auto = unpackValue(*B, Env); + auto = bool_model::rValueFromLValue(*B, Env); if ( == Val) return Val; Env.setValue(*Loc, UnpackedVal); return }
[clang] [NFC][CLANG] Fix static analyzer bugs about unnecessary object copies with auto keyword (PR #85962)
ymand wrote: Looks good, but per LLVM style guidelines, should we go ahead and replace the `auto` as well? https://github.com/llvm/llvm-project/pull/85962 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [dataflow] CXXForRangeStmt should extend flow condition (PR #80989)
ymand wrote: Just a note: I've siginfiicantly simplified the code that you're modifying in this PR (https://github.com/llvm/llvm-project/pull/84499), so expect some merge conflicts next time you pull from main. https://github.com/llvm/llvm-project/pull/80989 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor processing of terminator element (PR #84499)
https://github.com/ymand closed https://github.com/llvm/llvm-project/pull/84499 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor processing of terminator element (PR #84499)
https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/84499 >From 02381f2dbdcc569889ae55a2ca5d8698f74626d8 Mon Sep 17 00:00:00 2001 From: Yitzhak Mandelbaum Date: Fri, 8 Mar 2024 15:19:14 + Subject: [PATCH 1/2] [clang][dataflow] Refactor processing of terminator element This patch vastly simplifies the code handling terminators, without changing any behavior. Additionally, the simplification unblocks our ability to address a (simple) FIXME in the code to invoke `transferBranch`, even when builtin options are disabled. --- .../TypeErasedDataflowAnalysis.cpp| 126 +- 1 file changed, 35 insertions(+), 91 deletions(-) diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp index 721a11c2098530..be05ab5435e842 100644 --- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp +++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp @@ -11,7 +11,6 @@ // //===--===// -#include #include #include #include @@ -33,7 +32,6 @@ #include "clang/Analysis/FlowSensitive/Value.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/SmallBitVector.h" #include "llvm/Support/Debug.h" #include "llvm/Support/Error.h" @@ -64,88 +62,27 @@ static bool isBackedgeNode(const CFGBlock ) { 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 -// represents whether the condition was true or false. -using TerminatorVisitorRetTy = std::pair; - -/// Extends the flow condition of an environment based on a terminator -/// statement. +/// Extracts the condition expression. class TerminatorVisitor -: public ConstStmtVisitor { +: public ConstStmtVisitor { public: - TerminatorVisitor(Environment , int BlockSuccIdx) - : Env(Env), BlockSuccIdx(BlockSuccIdx) {} - - TerminatorVisitorRetTy VisitIfStmt(const IfStmt *S) { -auto *Cond = S->getCond(); -assert(Cond != nullptr); -return extendFlowCondition(*Cond); - } - - TerminatorVisitorRetTy VisitWhileStmt(const WhileStmt *S) { -auto *Cond = S->getCond(); -assert(Cond != nullptr); -return extendFlowCondition(*Cond); - } - - TerminatorVisitorRetTy VisitDoStmt(const DoStmt *S) { -auto *Cond = S->getCond(); -assert(Cond != nullptr); -return extendFlowCondition(*Cond); - } - - TerminatorVisitorRetTy VisitForStmt(const ForStmt *S) { -auto *Cond = S->getCond(); -if (Cond != nullptr) - return extendFlowCondition(*Cond); -return {nullptr, false}; - } - - TerminatorVisitorRetTy VisitCXXForRangeStmt(const CXXForRangeStmt *) { + TerminatorVisitor() = default; + const Expr *VisitIfStmt(const IfStmt *S) { return S->getCond(); } + const Expr *VisitWhileStmt(const WhileStmt *S) { return S->getCond(); } + const Expr *VisitDoStmt(const DoStmt *S) { return S->getCond(); } + const Expr *VisitForStmt(const ForStmt *S) { return S->getCond(); } + const Expr *VisitCXXForRangeStmt(const CXXForRangeStmt *) { // Don't do anything special for CXXForRangeStmt, because the condition // (being implicitly generated) isn't visible from the loop body. -return {nullptr, false}; +return nullptr; } - - TerminatorVisitorRetTy VisitBinaryOperator(const BinaryOperator *S) { + const Expr *VisitBinaryOperator(const BinaryOperator *S) { assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr); -auto *LHS = S->getLHS(); -assert(LHS != nullptr); -return extendFlowCondition(*LHS); +return S->getLHS(); } - - TerminatorVisitorRetTy - VisitConditionalOperator(const ConditionalOperator *S) { -auto *Cond = S->getCond(); -assert(Cond != nullptr); -return extendFlowCondition(*Cond); - } - -private: - TerminatorVisitorRetTy extendFlowCondition(const Expr ) { -auto *Val = Env.get(Cond); -// In transferCFGBlock(), we ensure that we always have a `Value` for the -// terminator condition, so assert this. -// We consciously assert ourselves instead of asserting via `cast()` so -// that we get a more meaningful line number if the assertion fails. -assert(Val != nullptr); - -bool ConditionValue = true; -// The condition must be inverted for the successor that encompasses the -// "else" branch, if such exists. -if (BlockSuccIdx == 1) { - Val = (*Val); - ConditionValue = false; -} - -Env.assume(Val->formula()); -return {, ConditionValue}; + const Expr *VisitConditionalOperator(const ConditionalOperator *S) { +return S->getCond(); } - - Environment - int BlockSuccIdx; }; /// Holds data structures required for running dataflow analysis. @@ -336,26 +273,33 @@
[clang] [clang][dataflow] Refactor processing of terminator element (PR #84499)
@@ -337,26 +274,33 @@ computeBlockInputState(const CFGBlock , AnalysisContext ) { AC.BlockStates[Pred->getBlockID()]; if (!MaybePredState) continue; - -if (AC.Analysis.builtinOptions()) { - if (const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) { -// We have a terminator: we need to mutate an environment to describe -// when the terminator is taken. Copy now. +const TypeErasedDataflowAnalysisState = *MaybePredState; + +if (const Stmt *PredTerminatorStmt = Pred->getTerminatorStmt()) { ymand wrote: Done https://github.com/llvm/llvm-project/pull/84499 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Refactor processing of terminator element (PR #84499)
https://github.com/ymand updated https://github.com/llvm/llvm-project/pull/84499 >From 3b20e1823753ab46e3e259d3d8c727dea91ce1d4 Mon Sep 17 00:00:00 2001 From: Yitzhak Mandelbaum Date: Fri, 8 Mar 2024 15:19:14 + Subject: [PATCH 1/2] [clang][dataflow] Refactor processing of terminator element This patch vastly simplifies the code handling terminators, without changing any behavior. Additionally, the simplification unblocks our ability to address a (simple) FIXME in the code to invoke `transferBranch`, even when builtin options are disabled. --- .../TypeErasedDataflowAnalysis.cpp| 126 +- 1 file changed, 35 insertions(+), 91 deletions(-) diff --git a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp index 939247c047c66e..2d745231fd0758 100644 --- a/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp +++ b/clang/lib/Analysis/FlowSensitive/TypeErasedDataflowAnalysis.cpp @@ -11,7 +11,6 @@ // //===--===// -#include #include #include #include @@ -33,7 +32,6 @@ #include "clang/Analysis/FlowSensitive/Value.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/STLExtras.h" -#include "llvm/ADT/SmallBitVector.h" #include "llvm/Support/Debug.h" #include "llvm/Support/Error.h" @@ -64,88 +62,27 @@ static bool isBackedgeNode(const CFGBlock ) { 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 -// represents whether the condition was true or false. -using TerminatorVisitorRetTy = std::pair; - -/// Extends the flow condition of an environment based on a terminator -/// statement. +/// Extracts the condition expression. class TerminatorVisitor -: public ConstStmtVisitor { +: public ConstStmtVisitor { public: - TerminatorVisitor(Environment , int BlockSuccIdx) - : Env(Env), BlockSuccIdx(BlockSuccIdx) {} - - TerminatorVisitorRetTy VisitIfStmt(const IfStmt *S) { -auto *Cond = S->getCond(); -assert(Cond != nullptr); -return extendFlowCondition(*Cond); - } - - TerminatorVisitorRetTy VisitWhileStmt(const WhileStmt *S) { -auto *Cond = S->getCond(); -assert(Cond != nullptr); -return extendFlowCondition(*Cond); - } - - TerminatorVisitorRetTy VisitDoStmt(const DoStmt *S) { -auto *Cond = S->getCond(); -assert(Cond != nullptr); -return extendFlowCondition(*Cond); - } - - TerminatorVisitorRetTy VisitForStmt(const ForStmt *S) { -auto *Cond = S->getCond(); -if (Cond != nullptr) - return extendFlowCondition(*Cond); -return {nullptr, false}; - } - - TerminatorVisitorRetTy VisitCXXForRangeStmt(const CXXForRangeStmt *) { + TerminatorVisitor() = default; + const Expr *VisitIfStmt(const IfStmt *S) { return S->getCond(); } + const Expr *VisitWhileStmt(const WhileStmt *S) { return S->getCond(); } + const Expr *VisitDoStmt(const DoStmt *S) { return S->getCond(); } + const Expr *VisitForStmt(const ForStmt *S) { return S->getCond(); } + const Expr *VisitCXXForRangeStmt(const CXXForRangeStmt *) { // Don't do anything special for CXXForRangeStmt, because the condition // (being implicitly generated) isn't visible from the loop body. -return {nullptr, false}; +return nullptr; } - - TerminatorVisitorRetTy VisitBinaryOperator(const BinaryOperator *S) { + const Expr *VisitBinaryOperator(const BinaryOperator *S) { assert(S->getOpcode() == BO_LAnd || S->getOpcode() == BO_LOr); -auto *LHS = S->getLHS(); -assert(LHS != nullptr); -return extendFlowCondition(*LHS); +return S->getLHS(); } - - TerminatorVisitorRetTy - VisitConditionalOperator(const ConditionalOperator *S) { -auto *Cond = S->getCond(); -assert(Cond != nullptr); -return extendFlowCondition(*Cond); - } - -private: - TerminatorVisitorRetTy extendFlowCondition(const Expr ) { -auto *Val = Env.get(Cond); -// In transferCFGBlock(), we ensure that we always have a `Value` for the -// terminator condition, so assert this. -// We consciously assert ourselves instead of asserting via `cast()` so -// that we get a more meaningful line number if the assertion fails. -assert(Val != nullptr); - -bool ConditionValue = true; -// The condition must be inverted for the successor that encompasses the -// "else" branch, if such exists. -if (BlockSuccIdx == 1) { - Val = (*Val); - ConditionValue = false; -} - -Env.assume(Val->formula()); -return {, ConditionValue}; + const Expr *VisitConditionalOperator(const ConditionalOperator *S) { +return S->getCond(); } - - Environment - int BlockSuccIdx; }; /// Holds data structures required for running dataflow analysis. @@ -337,26 +274,33 @@
[clang] [clang][dataflow] Make optional checker work for types derived from optional. (PR #84138)
@@ -129,19 +215,19 @@ auto inPlaceClass() { auto isOptionalNulloptConstructor() { return cxxConstructExpr( - hasOptionalType(), + hasOptionalOrDerivedType(), ymand wrote: Here and below -- now that this matcher is more expensive, please move until after the less expensive matchers. https://github.com/llvm/llvm-project/pull/84138 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Make optional checker work for types derived from optional. (PR #84138)
@@ -64,39 +64,117 @@ static bool hasOptionalClassName(const CXXRecordDecl ) { return false; } +static const CXXRecordDecl *getOptionalBaseClass(const CXXRecordDecl *RD) { + if (RD == nullptr) +return nullptr; + if (hasOptionalClassName(*RD)) +return RD; + + if (!RD->hasDefinition()) +return nullptr; + + for (const CXXBaseSpecifier : RD->bases()) +if (const CXXRecordDecl *BaseClass = +getOptionalBaseClass(Base.getType()->getAsCXXRecordDecl())) + return BaseClass; + + return nullptr; +} + namespace { using namespace ::clang::ast_matchers; using LatticeTransferState = TransferState; -AST_MATCHER(CXXRecordDecl, hasOptionalClassNameMatcher) { - return hasOptionalClassName(Node); +AST_MATCHER(CXXRecordDecl, optionalClass) { return hasOptionalClassName(Node); } + +AST_MATCHER(CXXRecordDecl, optionalOrDerivedClass) { + return getOptionalBaseClass() != nullptr; } -DeclarationMatcher optionalClass() { - return classTemplateSpecializationDecl( - hasOptionalClassNameMatcher(), - hasTemplateArgument(0, refersToType(type().bind("T"; +auto desugarsToOptionalType() { + return hasUnqualifiedDesugaredType( + recordType(hasDeclaration(cxxRecordDecl(optionalClass(); } -auto optionalOrAliasType() { +auto desugarsToOptionalOrDerivedType() { return hasUnqualifiedDesugaredType( - recordType(hasDeclaration(optionalClass(; + recordType(hasDeclaration(cxxRecordDecl(optionalOrDerivedClass(); } -/// Matches any of the spellings of the optional types and sugar, aliases, etc. -auto hasOptionalType() { return hasType(optionalOrAliasType()); } +auto hasOptionalType() { return hasType(desugarsToOptionalType()); } + +/// Matches any of the spellings of the optional types and sugar, aliases, +/// derived classes, etc. +auto hasOptionalOrDerivedType() { + return hasType(desugarsToOptionalOrDerivedType()); +} + +QualType getPublicType(const Expr *E) { + auto *Cast = dyn_cast(E->IgnoreParens()); + if (Cast == nullptr || Cast->getCastKind() != CK_UncheckedDerivedToBase) { +QualType Ty = E->getType(); +if (Ty->isPointerType()) + return Ty->getPointeeType(); +return Ty; + } + + QualType Ty = getPublicType(Cast->getSubExpr()); + + // Is `Ty` the type of `*this`? In this special case, we can upcast to the + // base class even if the base is non-public. + bool TyIsThisType = isa(Cast->getSubExpr()); + + for (const CXXBaseSpecifier *Base : Cast->path()) { +if (Base->getAccessSpecifier() != AS_public && !TyIsThisType) + break; +Ty = Base->getType(); +TyIsThisType = false; + } ymand wrote: Yes, very clear now. Thanks! https://github.com/llvm/llvm-project/pull/84138 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Make optional checker work for types derived from optional. (PR #84138)
https://github.com/ymand approved this pull request. https://github.com/llvm/llvm-project/pull/84138 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Make optional checker work for types derived from optional. (PR #84138)
@@ -119,20 +119,28 @@ QualType getPublicType(const Expr *E) { return Ty; } - QualType Ty = getPublicType(Cast->getSubExpr()); - - // Is `Ty` the type of `*this`? In this special case, we can upcast to the - // base class even if the base is non-public. - bool TyIsThisType = isa(Cast->getSubExpr()); - + // Is the derived type that we're casting from the type of `*this`? In this + // special case, we can upcast to the base class even if the base is + // non-public. + bool CastingFromThis = isa(Cast->getSubExpr()); + + // Find the least-derived type in the path (i.e. the last entry in the list) + // that we can access. + QualType Ty; for (const CXXBaseSpecifier *Base : Cast->path()) { -if (Base->getAccessSpecifier() != AS_public && !TyIsThisType) +if (Base->getAccessSpecifier() != AS_public && !CastingFromThis) break; Ty = Base->getType(); ymand wrote: optional super nit: save `` instead, avoiding a call to `getType()` until after the loop. https://github.com/llvm/llvm-project/pull/84138 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[clang] [clang][dataflow] Make optional checker work for types derived from optional. (PR #84138)
https://github.com/ymand edited https://github.com/llvm/llvm-project/pull/84138 ___ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits