llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang-static-analyzer-1 Author: Donát Nagy (NagyDonat) <details> <summary>Changes</summary> This commit refactors `ExprEngine::processSwitch()` and related logic to make it easier to understand and "prepare the ground" for planned functional changes. Unfortunately there were many idiosyncratic decisions in this part of the engine -- e.g. `BranchNodeBuilder` does not derive from `NodeBuilder` and doesn't use a `NodeBuilderContext`. For now I left these skeletons in the closet, but I tried to pick the low-hanging fruit and moved `processSwitch` a bit closer to its "big sibling" `processBranch`. For example I moved the initialization of the node builder into the body of `processSwitch` because if I want to trigger `BranchCondition` callbacks from this method (the way `processBranch` does it) I will need to iterate over the nodes created by checkers and construct a new node builder in each iteration. (By the way this question is a bit academical because AFAIK there are no BranchCondition callbacks that actually split the state -- and until recently `processBranch` would've badly mishandled such callbacks -- but properly handling state splits is much easier than documenting and checking that `BranchCondition` callbacks are not allowed to split the state.) --- Full diff: https://github.com/llvm/llvm-project/pull/178678.diff 4 Files Affected: - (modified) clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h (+9-40) - (modified) clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h (+2-1) - (modified) clang/lib/StaticAnalyzer/Core/CoreEngine.cpp (+5-10) - (modified) clang/lib/StaticAnalyzer/Core/ExprEngine.cpp (+34-43) ``````````diff diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index b2b4e8729af25..8e179e8a58ae6 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -514,57 +514,26 @@ class IndirectGotoNodeBuilder { }; class SwitchNodeBuilder { - CoreEngine& Eng; + const CoreEngine &Eng; const CFGBlock *Src; const Expr *Condition; ExplodedNode *Pred; public: - SwitchNodeBuilder(ExplodedNode *pred, const CFGBlock *src, - const Expr *condition, CoreEngine* eng) - : Eng(*eng), Src(src), Condition(condition), Pred(pred) {} - - class iterator { - friend class SwitchNodeBuilder; + SwitchNodeBuilder(ExplodedNode *P, const CFGBlock *S, const Expr *C, + CoreEngine &E) + : Eng(E), Src(S), Condition(C), Pred(P) {} - CFGBlock::const_succ_reverse_iterator I; + using iterator = CFGBlock::const_succ_reverse_iterator; - iterator(CFGBlock::const_succ_reverse_iterator i) : I(i) {} + iterator begin() { return Src->succ_rbegin() + 1; } + iterator end() { return Src->succ_rend(); } - public: - iterator &operator++() { ++I; return *this; } - bool operator!=(const iterator &X) const { return I != X.I; } - bool operator==(const iterator &X) const { return I == X.I; } - - const CaseStmt *getCase() const { - return cast<CaseStmt>((*I)->getLabel()); - } - - const CFGBlock *getBlock() const { - return *I; - } - }; - - iterator begin() { return iterator(Src->succ_rbegin()+1); } - iterator end() { return iterator(Src->succ_rend()); } - - const SwitchStmt *getSwitch() const { - return cast<SwitchStmt>(Src->getTerminator()); - } - - ExplodedNode *generateCaseStmtNode(const iterator &I, + ExplodedNode *generateCaseStmtNode(const CFGBlock *Block, ProgramStateRef State); ExplodedNode *generateDefaultCaseNode(ProgramStateRef State, - bool isSink = false); - - const Expr *getCondition() const { return Condition; } - - ProgramStateRef getState() const { return Pred->State; } - - const LocationContext *getLocationContext() const { - return Pred->getLocationContext(); - } + bool IsSink = false); }; } // namespace ento diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h index d184986cda15d..e5980fa2e2a4d 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -361,7 +361,8 @@ class ExprEngine { /// ProcessSwitch - Called by CoreEngine. Used to generate successor /// nodes by processing the 'effects' of a switch statement. - void processSwitch(SwitchNodeBuilder& builder); + void processSwitch(const SwitchStmt *Switch, CoreEngine &CoreEng, + const CFGBlock *B, ExplodedNode *Pred); /// Called by CoreEngine. Used to notify checkers that processing a /// function has begun. Called for both inlined and top-level functions. diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index 95a843ee87571..857b2f0689e05 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -449,10 +449,7 @@ void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) { return; case Stmt::SwitchStmtClass: { - SwitchNodeBuilder builder(Pred, B, cast<SwitchStmt>(Term)->getCond(), - this); - - ExprEng.processSwitch(builder); + ExprEng.processSwitch(cast<SwitchStmt>(Term), *this, B, Pred); return; } @@ -748,13 +745,11 @@ IndirectGotoNodeBuilder::generateNode(const iterator &I, return Succ; } -ExplodedNode* -SwitchNodeBuilder::generateCaseStmtNode(const iterator &I, - ProgramStateRef St) { +ExplodedNode *SwitchNodeBuilder::generateCaseStmtNode(const CFGBlock *Block, + ProgramStateRef St) { bool IsNew; - ExplodedNode *Succ = - Eng.G.getNode(BlockEdge(Src, I.getBlock(), Pred->getLocationContext()), - St, false, &IsNew); + ExplodedNode *Succ = Eng.G.getNode( + BlockEdge(Src, Block, Pred->getLocationContext()), St, false, &IsNew); Succ->addPredecessor(Pred, Eng.G); if (!IsNew) return nullptr; diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index a6a96b594fe85..98e4d79841491 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -3107,37 +3107,34 @@ void ExprEngine::processEndOfFunction(NodeBuilderContext& BC, /// ProcessSwitch - Called by CoreEngine. Used to generate successor /// nodes by processing the 'effects' of a switch statement. -void ExprEngine::processSwitch(SwitchNodeBuilder& builder) { - using iterator = SwitchNodeBuilder::iterator; +void ExprEngine::processSwitch(const SwitchStmt *Switch, CoreEngine &CoreEng, + const CFGBlock *B, ExplodedNode *Pred) { + const Expr *Condition = Switch->getCond(); - ProgramStateRef state = builder.getState(); - const Expr *CondE = builder.getCondition(); - SVal CondV_untested = state->getSVal(CondE, builder.getLocationContext()); + SwitchNodeBuilder Builder(Pred, B, Condition, CoreEng); - if (CondV_untested.isUndef()) { - //ExplodedNode* N = builder.generateDefaultCaseNode(state, true); - // FIXME: add checker - //UndefBranches.insert(N); + ProgramStateRef State = Pred->getState(); + SVal CondV = State->getSVal(Condition, Pred->getLocationContext()); + if (CondV.isUndef()) { + // ExplodedNode* N = builder.generateDefaultCaseNode(state, true); + // FIXME: add checker + // UndefBranches.insert(N); return; } - DefinedOrUnknownSVal CondV = CondV_untested.castAs<DefinedOrUnknownSVal>(); - - ProgramStateRef DefaultSt = state; - iterator I = builder.begin(), EI = builder.end(); - bool defaultIsFeasible = I == EI; + std::optional<NonLoc> CondNL = CondV.getAs<NonLoc>(); - for ( ; I != EI; ++I) { + for (const CFGBlock *Block : Builder) { // Successor may be pruned out during CFG construction. - if (!I.getBlock()) + if (!Block) continue; - const CaseStmt *Case = I.getCase(); + const CaseStmt *Case = cast<CaseStmt>(Block->getLabel()); // Evaluate the LHS of the case value. llvm::APSInt V1 = Case->getLHS()->EvaluateKnownConstInt(getContext()); - assert(V1.getBitWidth() == getContext().getIntWidth(CondE->getType())); + assert(V1.getBitWidth() == getContext().getIntWidth(Condition->getType())); // Get the RHS of the case, if it exists. llvm::APSInt V2; @@ -3146,29 +3143,25 @@ void ExprEngine::processSwitch(SwitchNodeBuilder& builder) { else V2 = V1; - ProgramStateRef StateCase; - if (std::optional<NonLoc> NL = CondV.getAs<NonLoc>()) - std::tie(StateCase, DefaultSt) = - DefaultSt->assumeInclusiveRange(*NL, V1, V2); - else // UnknownVal - StateCase = DefaultSt; - - if (StateCase) - builder.generateCaseStmtNode(I, StateCase); - - // Now "assume" that the case doesn't match. Add this state - // to the default state (if it is feasible). - if (DefaultSt) - defaultIsFeasible = true; - else { - defaultIsFeasible = false; - break; + ProgramStateRef StateMatching; + if (CondNL) { + // Split the state: this "case:" matches / does not match. + std::tie(StateMatching, State) = + State->assumeInclusiveRange(*CondNL, V1, V2); + } else { + // The switch condition is UnknownVal, so we enter each "case:" without + // any state update. + StateMatching = State; } - } - if (!defaultIsFeasible) - return; + if (StateMatching) + Builder.generateCaseStmtNode(Block, StateMatching); + // If _not_ entering the current case is infeasible, we are done with + // processing this branch. + if (!State) + return; + } // If we have switch(enum value), the default branch is not // feasible if all of the enum constants not covered by 'case:' statements // are not feasible values for the switch condition. @@ -3176,14 +3169,12 @@ void ExprEngine::processSwitch(SwitchNodeBuilder& builder) { // Note that this isn't as accurate as it could be. Even if there isn't // a case for a particular enum value as long as that enum value isn't // feasible then it shouldn't be considered for making 'default:' reachable. - const SwitchStmt *SS = builder.getSwitch(); - const Expr *CondExpr = SS->getCond()->IgnoreParenImpCasts(); - if (CondExpr->getType()->isEnumeralType()) { - if (SS->isAllEnumCasesCovered()) + if (Condition->IgnoreParenImpCasts()->getType()->isEnumeralType()) { + if (Switch->isAllEnumCasesCovered()) return; } - builder.generateDefaultCaseNode(DefaultSt); + Builder.generateDefaultCaseNode(State); } //===----------------------------------------------------------------------===// `````````` </details> https://github.com/llvm/llvm-project/pull/178678 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
