llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang Author: Donát Nagy (NagyDonat) <details> <summary>Changes</summary> Previously `IndirectGotoNodeBuilder` and `SwitchNodeBuilder` were not subclasses of the base class `NodeBuilder` and duplicated some `generateNode()`-like functionality. This commit reimplements these two classes as subclasses of `NodeBuilder`. Updating `SwitchNodeBuilder` is a prerequisite for activating the `BranchCondition` checkers on the condition of the `switch` statement because `CheckerContext` requires the presence of a `NodeBuilder`. Updating `IndirectGotoNodeBuilder` doesn't have any analogous goals -- I'm just doing it for the sake of consistency. I also added some very basic tests because this area wasn't properly covered by the old tests. --- Full diff: https://github.com/llvm/llvm-project/pull/180960.diff 6 Files Affected: - (modified) clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h (+26-25) - (modified) clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h (+4-3) - (modified) clang/lib/StaticAnalyzer/Core/CoreEngine.cpp (+35-46) - (modified) clang/lib/StaticAnalyzer/Core/ExprEngine.cpp (+18-28) - (added) clang/test/Analysis/indirect-goto-basics.c (+83) - (added) clang/test/Analysis/switch-basics.c (+110) ``````````diff diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index 96ddd12b286a6..6d7dca2622a89 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -399,55 +399,56 @@ class BranchNodeBuilder: public NodeBuilder { ExplodedNode *Pred); }; -class IndirectGotoNodeBuilder { - const CoreEngine &Eng; - const CFGBlock *Src; +class IndirectGotoNodeBuilder : public NodeBuilder { const CFGBlock &DispatchBlock; - const Expr *E; - ExplodedNode *Pred; + const Expr *Target; public: - IndirectGotoNodeBuilder(ExplodedNode *Pred, const CFGBlock *Src, - const Expr *E, const CFGBlock *Dispatch, - const CoreEngine *Eng) - : Eng(*Eng), Src(Src), DispatchBlock(*Dispatch), E(E), Pred(Pred) {} + IndirectGotoNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, + NodeBuilderContext &Ctx, const Expr *Tgt, + const CFGBlock *Dispatch) + : NodeBuilder(SrcNode, DstSet, Ctx), DispatchBlock(*Dispatch), + Target(Tgt) { + // The indirect goto node builder does not generate autotransitions. + takeNodes(SrcNode); + } using iterator = CFGBlock::const_succ_iterator; iterator begin() { return DispatchBlock.succ_begin(); } iterator end() { return DispatchBlock.succ_end(); } - ExplodedNode *generateNode(const CFGBlock *Block, ProgramStateRef State, - bool IsSink = false); + using NodeBuilder::generateNode; - const Expr *getTarget() const { return E; } + ExplodedNode *generateNode(const CFGBlock *Block, ProgramStateRef State, + ExplodedNode *Pred); - ProgramStateRef getState() const { return Pred->State; } + const Expr *getTarget() const { return Target; } const LocationContext *getLocationContext() const { - return Pred->getLocationContext(); + return C.getLocationContext(); } }; -class SwitchNodeBuilder { - const CoreEngine &Eng; - const CFGBlock *Src; - ExplodedNode *Pred; - +class SwitchNodeBuilder : public NodeBuilder { public: - SwitchNodeBuilder(ExplodedNode *P, const CFGBlock *S, CoreEngine &E) - : Eng(E), Src(S), Pred(P) {} + SwitchNodeBuilder(ExplodedNode *SrcNode, ExplodedNodeSet &DstSet, + const NodeBuilderContext &Ctx) + : NodeBuilder(SrcNode, DstSet, Ctx) { + // The switch node builder does not generate autotransitions. + takeNodes(SrcNode); + } using iterator = CFGBlock::const_succ_reverse_iterator; - iterator begin() { return Src->succ_rbegin() + 1; } - iterator end() { return Src->succ_rend(); } + iterator begin() { return C.getBlock()->succ_rbegin() + 1; } + iterator end() { return C.getBlock()->succ_rend(); } ExplodedNode *generateCaseStmtNode(const CFGBlock *Block, - ProgramStateRef State); + ProgramStateRef State, ExplodedNode *Pred); ExplodedNode *generateDefaultCaseNode(ProgramStateRef State, - bool IsSink = false); + ExplodedNode *Pred); }; } // namespace ento diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h index 6705716932bbc..20f62f93f9095 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -355,12 +355,13 @@ class ExprEngine { /// processIndirectGoto - Called by CoreEngine. Used to generate successor /// nodes by processing the 'effects' of a computed goto jump. - void processIndirectGoto(IndirectGotoNodeBuilder& builder); + void processIndirectGoto(IndirectGotoNodeBuilder &Builder, + ExplodedNode *Pred); /// ProcessSwitch - Called by CoreEngine. Used to generate successor /// nodes by processing the 'effects' of a switch statement. - void processSwitch(const SwitchStmt *Switch, CoreEngine &CoreEng, - const CFGBlock *B, ExplodedNode *Pred); + void processSwitch(NodeBuilderContext &BC, const SwitchStmt *Switch, + ExplodedNode *Pred, ExplodedNodeSet &Dst); /// 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 bfaa874f1632a..8f087cc53aaa9 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -425,12 +425,23 @@ void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) { case Stmt::IndirectGotoStmtClass: { // Only 1 successor: the indirect goto dispatch block. assert(B->succ_size() == 1); - - IndirectGotoNodeBuilder - builder(Pred, B, cast<IndirectGotoStmt>(Term)->getTarget(), - *(B->succ_begin()), this); - - ExprEng.processIndirectGoto(builder); + NodeBuilderContext Ctx(*this, B, Pred); + ExplodedNodeSet Dst; + IndirectGotoNodeBuilder Builder( + Pred, Dst, Ctx, cast<IndirectGotoStmt>(Term)->getTarget(), + *(B->succ_begin())); + + ExprEng.processIndirectGoto(Builder, Pred); + // Enqueue the new frontier onto the worklist. + llvm::errs() << "Pred location is "; + Pred->getLocation().dump(); + llvm::errs() << "\n"; + for (auto *N : Dst) { + llvm::errs() << "Enqueueing node at "; + N->getLocation().dump(); + llvm::errs() << "\n"; + WList->enqueue(N); + } return; } @@ -449,7 +460,12 @@ void CoreEngine::HandleBlockExit(const CFGBlock * B, ExplodedNode *Pred) { return; case Stmt::SwitchStmtClass: { - ExprEng.processSwitch(cast<SwitchStmt>(Term), *this, B, Pred); + NodeBuilderContext Ctx(*this, B, Pred); + ExplodedNodeSet Dst; + ExprEng.processSwitch(Ctx, cast<SwitchStmt>(Term), Pred, Dst); + // Enqueue the new frontier onto the worklist. + for (auto *N : Dst) + WList->enqueue(N); return; } @@ -726,38 +742,22 @@ ExplodedNode *BranchNodeBuilder::generateNode(ProgramStateRef State, ExplodedNode *IndirectGotoNodeBuilder::generateNode(const CFGBlock *Block, ProgramStateRef St, - bool IsSink) { - bool IsNew; - ExplodedNode *Succ = Eng.G.getNode( - BlockEdge(Src, Block, Pred->getLocationContext()), St, IsSink, &IsNew); - Succ->addPredecessor(Pred, Eng.G); - - if (!IsNew) - return nullptr; - - if (!IsSink) - Eng.WList->enqueue(Succ); - - return Succ; + ExplodedNode *Pred) { + BlockEdge BE(C.getBlock(), Block, Pred->getLocationContext()); + return generateNode(BE, St, Pred); } ExplodedNode *SwitchNodeBuilder::generateCaseStmtNode(const CFGBlock *Block, - ProgramStateRef St) { - bool IsNew; - ExplodedNode *Succ = Eng.G.getNode( - BlockEdge(Src, Block, Pred->getLocationContext()), St, false, &IsNew); - Succ->addPredecessor(Pred, Eng.G); - if (!IsNew) - return nullptr; - - Eng.WList->enqueue(Succ); - return Succ; + ProgramStateRef St, + ExplodedNode *Pred) { + BlockEdge BE(C.getBlock(), Block, Pred->getLocationContext()); + return generateNode(BE, St, Pred); } -ExplodedNode* -SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St, - bool IsSink) { +ExplodedNode *SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St, + ExplodedNode *Pred) { // Get the block for the default case. + const CFGBlock *Src = C.getBlock(); assert(Src->succ_rbegin() != Src->succ_rend()); CFGBlock *DefaultBlock = *Src->succ_rbegin(); @@ -766,17 +766,6 @@ SwitchNodeBuilder::generateDefaultCaseNode(ProgramStateRef St, if (!DefaultBlock) return nullptr; - bool IsNew; - ExplodedNode *Succ = - Eng.G.getNode(BlockEdge(Src, DefaultBlock, Pred->getLocationContext()), - St, IsSink, &IsNew); - Succ->addPredecessor(Pred, Eng.G); - - if (!IsNew) - return nullptr; - - if (!IsSink) - Eng.WList->enqueue(Succ); - - return Succ; + BlockEdge BE(Src, DefaultBlock, Pred->getLocationContext()); + return generateNode(BE, St, Pred); } diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 883c7b5d66c32..47312a53f61ff 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -2992,23 +2992,18 @@ void ExprEngine::processStaticInitializer( /// processIndirectGoto - Called by CoreEngine. Used to generate successor /// nodes by processing the 'effects' of a computed goto jump. -void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { - ProgramStateRef state = builder.getState(); - SVal V = state->getSVal(builder.getTarget(), builder.getLocationContext()); - - // Three possibilities: - // - // (1) We know the computed label. - // (2) The label is NULL (or some other constant), or Undefined. - // (3) We have no clue about the label. Dispatch to all targets. - // +void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &Builder, + ExplodedNode *Pred) { + ProgramStateRef State = Pred->getState(); + SVal V = State->getSVal(Builder.getTarget(), Builder.getLocationContext()); + // Case 1: We know the computed label. if (std::optional<loc::GotoLabel> LV = V.getAs<loc::GotoLabel>()) { const LabelDecl *L = LV->getLabel(); - for (const CFGBlock *Succ : builder) { + for (const CFGBlock *Succ : Builder) { if (cast<LabelStmt>(Succ->getLabel())->getDecl() == L) { - builder.generateNode(Succ, state); + Builder.generateNode(Succ, State, Pred); return; } } @@ -3016,19 +3011,16 @@ void ExprEngine::processIndirectGoto(IndirectGotoNodeBuilder &builder) { llvm_unreachable("No block with label."); } + // Case 2: The label is NULL (or some other constant), or Undefined. if (isa<UndefinedVal, loc::ConcreteInt>(V)) { - // Dispatch to the first target and mark it as a sink. - //ExplodedNode* N = builder.generateNode(builder.begin(), state, true); - // FIXME: add checker visit. - // UndefBranches.insert(N); + // FIXME: Emit warnings when the jump target is undefined or numerical. return; } - // This is really a catch-all. We don't support symbolics yet. + // Case 3: We have no clue about the label. Dispatch to all targets. // FIXME: Implement dispatch for symbolic pointers. - - for (const CFGBlock *Succ : builder) - builder.generateNode(Succ, state); + for (const CFGBlock *Succ : Builder) + Builder.generateNode(Succ, State, Pred); } void ExprEngine::processBeginOfFunction(NodeBuilderContext &BC, @@ -3112,19 +3104,17 @@ 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(const SwitchStmt *Switch, CoreEngine &CoreEng, - const CFGBlock *B, ExplodedNode *Pred) { +void ExprEngine::processSwitch(NodeBuilderContext &BC, const SwitchStmt *Switch, + ExplodedNode *Pred, ExplodedNodeSet &Dst) { const Expr *Condition = Switch->getCond(); - SwitchNodeBuilder Builder(Pred, B, CoreEng); + SwitchNodeBuilder Builder(Pred, Dst, BC); 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); + // FIXME: Emit warnings when the switch condition is undefined. return; } @@ -3160,7 +3150,7 @@ void ExprEngine::processSwitch(const SwitchStmt *Switch, CoreEngine &CoreEng, } if (StateMatching) - Builder.generateCaseStmtNode(Block, StateMatching); + Builder.generateCaseStmtNode(Block, StateMatching, Pred); // If _not_ entering the current case is infeasible, we are done with // processing this branch. @@ -3179,7 +3169,7 @@ void ExprEngine::processSwitch(const SwitchStmt *Switch, CoreEngine &CoreEng, return; } - Builder.generateDefaultCaseNode(State); + Builder.generateDefaultCaseNode(State, Pred); } //===----------------------------------------------------------------------===// diff --git a/clang/test/Analysis/indirect-goto-basics.c b/clang/test/Analysis/indirect-goto-basics.c new file mode 100644 index 0000000000000..93ee5b39ce913 --- /dev/null +++ b/clang/test/Analysis/indirect-goto-basics.c @@ -0,0 +1,83 @@ +// RUN: %clang_analyze_cc1 -verify %s -analyzer-checker=core + +// This file tests ExprEngine::processIndirectGoto and the class +// IndirectGotoNodeBuilder. + +int goto_known_label_1(int x) { + // In this example the ternary operator splits the state, the analyzer can + // exactly follow the computed goto on both execution paths and validate that + // we reach "33 / x" with a state where x is constrained to zero. + void *target = x ? &&nonzero : &&zero; + goto *target; +zero: + return 33 / x; // expected-warning {{Division by zero}} +nonzero: + return 66 / (x + 1); +} + +int goto_known_label_2(int x) { + // In this example the ternary operator splits the state, the analyzer can + // exactly follow the computed goto on both execution paths and validate that + // we do not reach "66 / x" with the state where x is constrained to zero. + void *target = x ? &&nonzero : &&zero; + goto *target; +zero: + return 33 / (x + 1); +nonzero: + return 66 / x; +} + +void *select(int, void *, void *, void *); +int goto_symbolic(int x, int y) { + // In this example the target of the indirect goto is a symbolic value so the + // analyzer dispatches to all possible labels and we get the zero division + // errors at all of them. + void *target = select(x, &&first, &&second, &&third); + if (y) + return 41; + goto *target; +first: + return 33 / y; // expected-warning {{Division by zero}} +second: + return 66 / y; // expected-warning {{Division by zero}} +third: + return 123 / y; // expected-warning {{Division by zero}} +} + +int goto_nullpointer(int x, int y) { + // In this example the target of the indirect goto is a loc::ConcreteInt (a + // null pointer), so the analyzer doesn't dispatch anywhere. + // FIXME: We should emit a warning in this situation. + void *target = (void *)0; + (void)&&first; + (void)&&second; + (void)&&third; + if (y) + return 41; + goto *target; +first: + return 33 / y; +second: + return 66 / y; +third: + return 123 / y; +} + +int goto_undefined(int x, int y) { + // In this example the target of the indirect goto is an uninitialized + // pointer, so the analyzer doesn't dispatch anywhere. + // FIXME: We should emit a warning in this situation. + void *target; + (void)&&first; + (void)&&second; + (void)&&third; + if (y) + return 41; + goto *target; +first: + return 33 / y; +second: + return 66 / y; +third: + return 123 / y; +} diff --git a/clang/test/Analysis/switch-basics.c b/clang/test/Analysis/switch-basics.c new file mode 100644 index 0000000000000..2a0f9c2a3cf1b --- /dev/null +++ b/clang/test/Analysis/switch-basics.c @@ -0,0 +1,110 @@ +// RUN: %clang_analyze_cc1 -verify %s -analyzer-checker=core + +// This file tests ExprEngine::processSwitch and the class SwitchNodeBuilder. + +int switch_simple(int x) { + // Validate that switch behaves as expected in a very simple situation. + switch (x) { + case 1: + return 13 / x; + case 0: + return 14 / x; // expected-warning {{Division by zero}} + case 2: + return 15 / x; + default: + return 67 / (x - x); // expected-warning {{Division by zero}} + } +} + +int switch_default(int x) { + // Validate that the default case is evaluated after excluding the other + // cases -- even if it appears first. + if (x > 2 || x < 0) + return 0; + switch (x) { + default: + return 16 / x; // expected-warning {{Division by zero}} + case 1: + return 13 / x; + case 2: + return 15 / x; + } +} + +int switch_unreachable_default(int x) { + // Validate that the default case is not evaluated if it is infeasible. + int zero = 0; + if (x > 2 || x < 0) + return 0; + switch (x) { + default: + return 16 / zero; // no-warning + case 0: + return 456; + case 1: + return 13 / x; + case 2: + return 15 / x; + } +} + +enum Color {Red, Green, Blue}; + +int switch_all_enum_cases_covered(enum Color x) { + // Validate that the default case is not evaluated if the switch is over an + // enum value and all enumerators appear as 'case's. + int zero = 0; + switch (x) { + default: + return 16 / zero; // no-warning + case Red: + case Green: + return 2; + case Blue: + return 3; + } +} + +int switch_all_feasible_enum_cases_covered(enum Color x) { + // Highlight a shortcoming of enum/switch handling: here the 'case's cover + // all the enumerators that could appear in the symbolic value 'x', but the + // default is still executed. + // FIXME: The default branch shouldn't be executed here. + int zero = 0; + + if (x == Red) + return 1; + switch (x) { + default: + return 16 / zero; // expected-warning {{Division by zero}} + case Green: + return 2; + case Blue: + return 3; + } +} + +int switch_no_compound_stmt(int x) { + // Validate that the engine can follow the switch statement even if there is + // no compound statement around the cases. (Yes, this is valid, although + // not very practical.) + switch (x) case 1: case 0: return 16 / x; // expected-warning {{Division by zero}} + + return 0; +} + +int switch_with_case_range(int x) { + // Validate that the GNU case range extension is properly handled. + switch (x) { + case 5: + return 55 / x; + case 2 ... 4: + return 3; + case 0 ... 1: + return 44 / x; // no-warning: there is no state split between 0 and 1 + default: + if (x) + return 8; + return 45 / x; // no-warning: x cannot be 0 on the default branch + } +} `````````` </details> https://github.com/llvm/llvm-project/pull/180960 _______________________________________________ cfe-commits mailing list [email protected] https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
