head 1.1; branch 1.1.1; access; symbols netbsd-11-0-RC4:1.1.1.8 netbsd-11-0-RC3:1.1.1.8 netbsd-11-0-RC2:1.1.1.8 netbsd-11-0-RC1:1.1.1.8 perseant-exfatfs-base-20250801:1.1.1.8 netbsd-11:1.1.1.8.0.10 netbsd-11-base:1.1.1.8 netbsd-10-1-RELEASE:1.1.1.8 perseant-exfatfs-base-20240630:1.1.1.8 perseant-exfatfs:1.1.1.8.0.8 perseant-exfatfs-base:1.1.1.8 netbsd-8-3-RELEASE:1.1.1.6 netbsd-9-4-RELEASE:1.1.1.7 netbsd-10-0-RELEASE:1.1.1.8 netbsd-10-0-RC6:1.1.1.8 netbsd-10-0-RC5:1.1.1.8 netbsd-10-0-RC4:1.1.1.8 netbsd-10-0-RC3:1.1.1.8 netbsd-10-0-RC2:1.1.1.8 netbsd-10-0-RC1:1.1.1.8 netbsd-10:1.1.1.8.0.6 netbsd-10-base:1.1.1.8 netbsd-9-3-RELEASE:1.1.1.7 cjep_sun2x:1.1.1.8.0.4 cjep_sun2x-base:1.1.1.8 cjep_staticlib_x-base1:1.1.1.8 netbsd-9-2-RELEASE:1.1.1.7 cjep_staticlib_x:1.1.1.8.0.2 cjep_staticlib_x-base:1.1.1.8 netbsd-9-1-RELEASE:1.1.1.7 phil-wifi-20200421:1.1.1.8 phil-wifi-20200411:1.1.1.8 phil-wifi-20200406:1.1.1.8 netbsd-8-2-RELEASE:1.1.1.6 netbsd-9-0-RELEASE:1.1.1.7 netbsd-9-0-RC2:1.1.1.7 netbsd-9-0-RC1:1.1.1.7 netbsd-9:1.1.1.7.0.2 netbsd-9-base:1.1.1.7 phil-wifi-20190609:1.1.1.7 netbsd-8-1-RELEASE:1.1.1.6 netbsd-8-1-RC1:1.1.1.6 pgoyette-compat-merge-20190127:1.1.1.6.12.1 pgoyette-compat-20190127:1.1.1.7 pgoyette-compat-20190118:1.1.1.7 pgoyette-compat-1226:1.1.1.7 pgoyette-compat-1126:1.1.1.7 pgoyette-compat-1020:1.1.1.7 pgoyette-compat-0930:1.1.1.7 pgoyette-compat-0906:1.1.1.7 netbsd-7-2-RELEASE:1.1.1.4 pgoyette-compat-0728:1.1.1.7 clang-337282:1.1.1.7 netbsd-8-0-RELEASE:1.1.1.6 phil-wifi:1.1.1.6.0.14 phil-wifi-base:1.1.1.6 pgoyette-compat-0625:1.1.1.6 netbsd-8-0-RC2:1.1.1.6 pgoyette-compat-0521:1.1.1.6 pgoyette-compat-0502:1.1.1.6 pgoyette-compat-0422:1.1.1.6 netbsd-8-0-RC1:1.1.1.6 pgoyette-compat-0415:1.1.1.6 pgoyette-compat-0407:1.1.1.6 pgoyette-compat-0330:1.1.1.6 pgoyette-compat-0322:1.1.1.6 pgoyette-compat-0315:1.1.1.6 netbsd-7-1-2-RELEASE:1.1.1.4 pgoyette-compat:1.1.1.6.0.12 pgoyette-compat-base:1.1.1.6 netbsd-7-1-1-RELEASE:1.1.1.4 clang-319952:1.1.1.6 matt-nb8-mediatek:1.1.1.6.0.10 matt-nb8-mediatek-base:1.1.1.6 clang-309604:1.1.1.6 perseant-stdc-iso10646:1.1.1.6.0.8 perseant-stdc-iso10646-base:1.1.1.6 netbsd-8:1.1.1.6.0.6 netbsd-8-base:1.1.1.6 prg-localcount2-base3:1.1.1.6 prg-localcount2-base2:1.1.1.6 prg-localcount2-base1:1.1.1.6 prg-localcount2:1.1.1.6.0.4 prg-localcount2-base:1.1.1.6 pgoyette-localcount-20170426:1.1.1.6 bouyer-socketcan-base1:1.1.1.6 pgoyette-localcount-20170320:1.1.1.6 netbsd-7-1:1.1.1.4.0.10 netbsd-7-1-RELEASE:1.1.1.4 netbsd-7-1-RC2:1.1.1.4 clang-294123:1.1.1.6 netbsd-7-nhusb-base-20170116:1.1.1.4 bouyer-socketcan:1.1.1.6.0.2 bouyer-socketcan-base:1.1.1.6 clang-291444:1.1.1.6 pgoyette-localcount-20170107:1.1.1.5 netbsd-7-1-RC1:1.1.1.4 pgoyette-localcount-20161104:1.1.1.5 netbsd-7-0-2-RELEASE:1.1.1.4 localcount-20160914:1.1.1.5 netbsd-7-nhusb:1.1.1.4.0.8 netbsd-7-nhusb-base:1.1.1.4 clang-280599:1.1.1.5 pgoyette-localcount-20160806:1.1.1.5 pgoyette-localcount-20160726:1.1.1.5 pgoyette-localcount:1.1.1.5.0.2 pgoyette-localcount-base:1.1.1.5 netbsd-7-0-1-RELEASE:1.1.1.4 clang-261930:1.1.1.5 netbsd-7-0:1.1.1.4.0.6 netbsd-7-0-RELEASE:1.1.1.4 netbsd-7-0-RC3:1.1.1.4 netbsd-7-0-RC2:1.1.1.4 netbsd-7-0-RC1:1.1.1.4 clang-237755:1.1.1.4 clang-232565:1.1.1.4 clang-227398:1.1.1.4 tls-maxphys-base:1.1.1.4 tls-maxphys:1.1.1.4.0.4 netbsd-7:1.1.1.4.0.2 netbsd-7-base:1.1.1.4 clang-215315:1.1.1.4 clang-209886:1.1.1.4 yamt-pagecache:1.1.1.3.0.4 yamt-pagecache-base9:1.1.1.3 tls-earlyentropy:1.1.1.3.0.2 tls-earlyentropy-base:1.1.1.4 riastradh-xf86-video-intel-2-7-1-pre-2-21-15:1.1.1.3 riastradh-drm2-base3:1.1.1.3 clang-202566:1.1.1.3 clang-201163:1.1.1.2 clang-199312:1.1.1.2 clang-198450:1.1.1.2 clang-196603:1.1.1.1 clang-195771:1.1.1.1 LLVM:1.1.1; locks; strict; comment @// @; 1.1 date 2013.11.28.14.14.52; author joerg; state Exp; branches 1.1.1.1; next ; commitid ow8OybrawrB1f3fx; 1.1.1.1 date 2013.11.28.14.14.52; author joerg; state Exp; branches; next 1.1.1.2; commitid ow8OybrawrB1f3fx; 1.1.1.2 date 2014.01.05.15.39.31; author joerg; state Exp; branches; next 1.1.1.3; commitid wh3aCSIWykURqWjx; 1.1.1.3 date 2014.03.04.19.55.01; author joerg; state Exp; branches 1.1.1.3.2.1 1.1.1.3.4.1; next 1.1.1.4; commitid 29z1hJonZISIXprx; 1.1.1.4 date 2014.05.30.18.14.44; author joerg; state Exp; branches 1.1.1.4.4.1; next 1.1.1.5; commitid 8q0kdlBlCn09GACx; 1.1.1.5 date 2016.02.27.22.12.06; author joerg; state Exp; branches 1.1.1.5.2.1; next 1.1.1.6; commitid tIimz3oDlh1NpBWy; 1.1.1.6 date 2017.01.11.10.35.39; author joerg; state Exp; branches 1.1.1.6.12.1 1.1.1.6.14.1; next 1.1.1.7; commitid CNnUNfII1jgNmxBz; 1.1.1.7 date 2018.07.17.18.31.08; author joerg; state Exp; branches; next 1.1.1.8; commitid wDzL46ALjrCZgwKA; 1.1.1.8 date 2019.11.13.22.19.28; author joerg; state dead; branches; next ; commitid QD8YATxuNG34YJKB; 1.1.1.3.2.1 date 2014.08.10.07.08.10; author tls; state Exp; branches; next ; commitid t01A1TLTYxkpGMLx; 1.1.1.3.4.1 date 2014.03.04.19.55.01; author yamt; state dead; branches; next 1.1.1.3.4.2; commitid WSrDtL5nYAUyiyBx; 1.1.1.3.4.2 date 2014.05.22.16.18.31; author yamt; state Exp; branches; next ; commitid WSrDtL5nYAUyiyBx; 1.1.1.4.4.1 date 2014.05.30.18.14.44; author tls; state dead; branches; next 1.1.1.4.4.2; commitid jTnpym9Qu0o4R1Nx; 1.1.1.4.4.2 date 2014.08.19.23.47.31; author tls; state Exp; branches; next ; commitid jTnpym9Qu0o4R1Nx; 1.1.1.5.2.1 date 2017.03.20.06.52.42; author pgoyette; state Exp; branches; next ; commitid jjw7cAwgyKq7RfKz; 1.1.1.6.12.1 date 2018.07.28.04.33.24; author pgoyette; state Exp; branches; next ; commitid 1UP1xAIUxv1ZgRLA; 1.1.1.6.14.1 date 2019.06.10.21.45.29; author christos; state Exp; branches; next 1.1.1.6.14.2; commitid jtc8rnCzWiEEHGqB; 1.1.1.6.14.2 date 2020.04.13.07.46.39; author martin; state dead; branches; next ; commitid X01YhRUPVUDaec4C; desc @@ 1.1 log @Initial revision @ text @//==- UnreachableCodeChecker.cpp - Generalized dead code checker -*- C++ -*-==// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // This file implements a generalized unreachable code checker using a // path-sensitive analysis. We mark any path visited, and then walk the CFG as a // post-analysis to determine what was never visited. // // A similar flow-sensitive only check exists in Analysis/ReachableCode.cpp //===----------------------------------------------------------------------===// #include "ClangSACheckers.h" #include "clang/AST/ParentMap.h" #include "clang/Basic/Builtins.h" #include "clang/Basic/SourceManager.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" #include "clang/StaticAnalyzer/Core/Checker.h" #include "clang/StaticAnalyzer/Core/CheckerManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" #include "llvm/ADT/SmallSet.h" // The number of CFGBlock pointers we want to reserve memory for. This is used // once for each function we analyze. #define DEFAULT_CFGBLOCKS 256 using namespace clang; using namespace ento; namespace { class UnreachableCodeChecker : public Checker { public: void checkEndAnalysis(ExplodedGraph &G, BugReporter &B, ExprEngine &Eng) const; private: typedef llvm::SmallSet CFGBlocksSet; static inline const Stmt *getUnreachableStmt(const CFGBlock *CB); static void FindUnreachableEntryPoints(const CFGBlock *CB, CFGBlocksSet &reachable, CFGBlocksSet &visited); static bool isInvalidPath(const CFGBlock *CB, const ParentMap &PM); static inline bool isEmptyCFGBlock(const CFGBlock *CB); }; } void UnreachableCodeChecker::checkEndAnalysis(ExplodedGraph &G, BugReporter &B, ExprEngine &Eng) const { CFGBlocksSet reachable, visited; if (Eng.hasWorkRemaining()) return; const Decl *D = 0; CFG *C = 0; ParentMap *PM = 0; const LocationContext *LC = 0; // Iterate over ExplodedGraph for (ExplodedGraph::node_iterator I = G.nodes_begin(), E = G.nodes_end(); I != E; ++I) { const ProgramPoint &P = I->getLocation(); LC = P.getLocationContext(); if (!LC->inTopFrame()) continue; if (!D) D = LC->getAnalysisDeclContext()->getDecl(); // Save the CFG if we don't have it already if (!C) C = LC->getAnalysisDeclContext()->getUnoptimizedCFG(); if (!PM) PM = &LC->getParentMap(); if (Optional BE = P.getAs()) { const CFGBlock *CB = BE->getBlock(); reachable.insert(CB->getBlockID()); } } // Bail out if we didn't get the CFG or the ParentMap. if (!D || !C || !PM) return; // Don't do anything for template instantiations. Proving that code // in a template instantiation is unreachable means proving that it is // unreachable in all instantiations. if (const FunctionDecl *FD = dyn_cast(D)) if (FD->isTemplateInstantiation()) return; // Find CFGBlocks that were not covered by any node for (CFG::const_iterator I = C->begin(), E = C->end(); I != E; ++I) { const CFGBlock *CB = *I; // Check if the block is unreachable if (reachable.count(CB->getBlockID())) continue; // Check if the block is empty (an artificial block) if (isEmptyCFGBlock(CB)) continue; // Find the entry points for this block if (!visited.count(CB->getBlockID())) FindUnreachableEntryPoints(CB, reachable, visited); // This block may have been pruned; check if we still want to report it if (reachable.count(CB->getBlockID())) continue; // Check for false positives if (CB->size() > 0 && isInvalidPath(CB, *PM)) continue; // It is good practice to always have a "default" label in a "switch", even // if we should never get there. It can be used to detect errors, for // instance. Unreachable code directly under a "default" label is therefore // likely to be a false positive. if (const Stmt *label = CB->getLabel()) if (label->getStmtClass() == Stmt::DefaultStmtClass) continue; // Special case for __builtin_unreachable. // FIXME: This should be extended to include other unreachable markers, // such as llvm_unreachable. if (!CB->empty()) { bool foundUnreachable = false; for (CFGBlock::const_iterator ci = CB->begin(), ce = CB->end(); ci != ce; ++ci) { if (Optional S = (*ci).getAs()) if (const CallExpr *CE = dyn_cast(S->getStmt())) { if (CE->isBuiltinCall() == Builtin::BI__builtin_unreachable) { foundUnreachable = true; break; } } } if (foundUnreachable) continue; } // We found a block that wasn't covered - find the statement to report SourceRange SR; PathDiagnosticLocation DL; SourceLocation SL; if (const Stmt *S = getUnreachableStmt(CB)) { SR = S->getSourceRange(); DL = PathDiagnosticLocation::createBegin(S, B.getSourceManager(), LC); SL = DL.asLocation(); if (SR.isInvalid() || !SL.isValid()) continue; } else continue; // Check if the SourceLocation is in a system header const SourceManager &SM = B.getSourceManager(); if (SM.isInSystemHeader(SL) || SM.isInExternCSystemHeader(SL)) continue; B.EmitBasicReport(D, "Unreachable code", "Dead code", "This statement is never executed", DL, SR); } } // Recursively finds the entry point(s) for this dead CFGBlock. void UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB, CFGBlocksSet &reachable, CFGBlocksSet &visited) { visited.insert(CB->getBlockID()); for (CFGBlock::const_pred_iterator I = CB->pred_begin(), E = CB->pred_end(); I != E; ++I) { if (!reachable.count((*I)->getBlockID())) { // If we find an unreachable predecessor, mark this block as reachable so // we don't report this block reachable.insert(CB->getBlockID()); if (!visited.count((*I)->getBlockID())) // If we haven't previously visited the unreachable predecessor, recurse FindUnreachableEntryPoints(*I, reachable, visited); } } } // Find the Stmt* in a CFGBlock for reporting a warning const Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) { for (CFGBlock::const_iterator I = CB->begin(), E = CB->end(); I != E; ++I) { if (Optional S = I->getAs()) return S->getStmt(); } if (const Stmt *S = CB->getTerminator()) return S; else return 0; } // Determines if the path to this CFGBlock contained an element that infers this // block is a false positive. We assume that FindUnreachableEntryPoints has // already marked only the entry points to any dead code, so we need only to // find the condition that led to this block (the predecessor of this block.) // There will never be more than one predecessor. bool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB, const ParentMap &PM) { // We only expect a predecessor size of 0 or 1. If it is >1, then an external // condition has broken our assumption (for example, a sink being placed by // another check). In these cases, we choose not to report. if (CB->pred_size() > 1) return true; // If there are no predecessors, then this block is trivially unreachable if (CB->pred_size() == 0) return false; const CFGBlock *pred = *CB->pred_begin(); // Get the predecessor block's terminator conditon const Stmt *cond = pred->getTerminatorCondition(); //assert(cond && "CFGBlock's predecessor has a terminator condition"); // The previous assertion is invalid in some cases (eg do/while). Leaving // reporting of these situations on at the moment to help triage these cases. if (!cond) return false; // Run each of the checks on the conditions if (containsMacro(cond) || containsEnum(cond) || containsStaticLocal(cond) || containsBuiltinOffsetOf(cond) || containsStmt(cond)) return true; return false; } // Returns true if the given CFGBlock is empty bool UnreachableCodeChecker::isEmptyCFGBlock(const CFGBlock *CB) { return CB->getLabel() == 0 // No labels && CB->size() == 0 // No statements && CB->getTerminator() == 0; // No terminator } void ento::registerUnreachableCodeChecker(CheckerManager &mgr) { mgr.registerChecker(); } @ 1.1.1.1 log @Import Clang 3.4rc1 r195771. @ text @@ 1.1.1.2 log @Import clang 3.5svn r198450. @ text @d139 1 a139 1 if (CE->getBuiltinCallee() == Builtin::BI__builtin_unreachable) { d245 1 a245 1 && !CB->getTerminator(); // No terminator @ 1.1.1.3 log @Import Clang 3.5svn r202566. @ text @d168 1 a168 1 B.EmitBasicReport(D, this, "Unreachable code", "Dead code", a180 3 if (!*I) continue; a221 2 if (!pred) return false; @ 1.1.1.3.2.1 log @Rebase. @ text @d61 4 a64 4 const Decl *D = nullptr; CFG *C = nullptr; ParentMap *PM = nullptr; const LocationContext *LC = nullptr; d204 1 a204 1 return nullptr; d248 1 a248 1 return CB->getLabel() == nullptr // No labels @ 1.1.1.4 log @Import Clang 3.5svn r209886. @ text @d61 4 a64 4 const Decl *D = nullptr; CFG *C = nullptr; ParentMap *PM = nullptr; const LocationContext *LC = nullptr; d204 1 a204 1 return nullptr; d248 1 a248 1 return CB->getLabel() == nullptr // No labels @ 1.1.1.5 log @Import Clang 3.8.0rc3 r261930. @ text @d57 1 a57 1 d91 1 a91 1 d238 6 a243 3 return containsMacro(cond) || containsEnum(cond) || containsStaticLocal(cond) || containsBuiltinOffsetOf(cond) || containsStmt(cond); @ 1.1.1.5.2.1 log @Sync with HEAD @ text @d29 4 d42 1 a42 1 typedef llvm::SmallSet CFGBlocksSet; a153 8 // In macros, 'do {...} while (0)' is often used. Don't warn about the // condition 0 when it is unreachable. if (S->getLocStart().isMacroID()) if (const auto *I = dyn_cast(S)) if (I->getValue() == 0ULL) if (const Stmt *Parent = PM->getParent(S)) if (isa(Parent)) continue; d198 2 a199 4 if (Optional S = I->getAs()) { if (!isa(S->getStmt())) return S->getStmt(); } @ 1.1.1.6 log @Import Clang pre-4.0.0 r291444. @ text @d29 4 d42 1 a42 1 typedef llvm::SmallSet CFGBlocksSet; a153 8 // In macros, 'do {...} while (0)' is often used. Don't warn about the // condition 0 when it is unreachable. if (S->getLocStart().isMacroID()) if (const auto *I = dyn_cast(S)) if (I->getValue() == 0ULL) if (const Stmt *Parent = PM->getParent(S)) if (isa(Parent)) continue; d198 2 a199 4 if (Optional S = I->getAs()) { if (!isa(S->getStmt())) return S->getStmt(); } @ 1.1.1.6.14.1 log @Sync with HEAD @ text @d115 1 a115 1 if (isInvalidPath(CB, *PM)) d135 1 a135 2 if (CE->getBuiltinCallee() == Builtin::BI__builtin_unreachable || CE->isBuiltinAssumeFalse(Eng.getContext())) { @ 1.1.1.6.14.2 log @Mostly merge changes from HEAD upto 20200411 @ text @@ 1.1.1.6.12.1 log @Sync with HEAD @ text @d115 1 a115 1 if (isInvalidPath(CB, *PM)) d135 1 a135 2 if (CE->getBuiltinCallee() == Builtin::BI__builtin_unreachable || CE->isBuiltinAssumeFalse(Eng.getContext())) { @ 1.1.1.7 log @Import clang r337282 from trunk @ text @d115 1 a115 1 if (isInvalidPath(CB, *PM)) d135 1 a135 2 if (CE->getBuiltinCallee() == Builtin::BI__builtin_unreachable || CE->isBuiltinAssumeFalse(Eng.getContext())) { @ 1.1.1.8 log @Mark old LLVM instance as dead. @ text @@ 1.1.1.4.4.1 log @file UnreachableCodeChecker.cpp was added on branch tls-maxphys on 2014-08-19 23:47:31 +0000 @ text @d1 255 @ 1.1.1.4.4.2 log @Rebase to HEAD as of a few days ago. @ text @a0 255 //==- UnreachableCodeChecker.cpp - Generalized dead code checker -*- C++ -*-==// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // This file implements a generalized unreachable code checker using a // path-sensitive analysis. We mark any path visited, and then walk the CFG as a // post-analysis to determine what was never visited. // // A similar flow-sensitive only check exists in Analysis/ReachableCode.cpp //===----------------------------------------------------------------------===// #include "ClangSACheckers.h" #include "clang/AST/ParentMap.h" #include "clang/Basic/Builtins.h" #include "clang/Basic/SourceManager.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" #include "clang/StaticAnalyzer/Core/Checker.h" #include "clang/StaticAnalyzer/Core/CheckerManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" #include "llvm/ADT/SmallSet.h" // The number of CFGBlock pointers we want to reserve memory for. This is used // once for each function we analyze. #define DEFAULT_CFGBLOCKS 256 using namespace clang; using namespace ento; namespace { class UnreachableCodeChecker : public Checker { public: void checkEndAnalysis(ExplodedGraph &G, BugReporter &B, ExprEngine &Eng) const; private: typedef llvm::SmallSet CFGBlocksSet; static inline const Stmt *getUnreachableStmt(const CFGBlock *CB); static void FindUnreachableEntryPoints(const CFGBlock *CB, CFGBlocksSet &reachable, CFGBlocksSet &visited); static bool isInvalidPath(const CFGBlock *CB, const ParentMap &PM); static inline bool isEmptyCFGBlock(const CFGBlock *CB); }; } void UnreachableCodeChecker::checkEndAnalysis(ExplodedGraph &G, BugReporter &B, ExprEngine &Eng) const { CFGBlocksSet reachable, visited; if (Eng.hasWorkRemaining()) return; const Decl *D = nullptr; CFG *C = nullptr; ParentMap *PM = nullptr; const LocationContext *LC = nullptr; // Iterate over ExplodedGraph for (ExplodedGraph::node_iterator I = G.nodes_begin(), E = G.nodes_end(); I != E; ++I) { const ProgramPoint &P = I->getLocation(); LC = P.getLocationContext(); if (!LC->inTopFrame()) continue; if (!D) D = LC->getAnalysisDeclContext()->getDecl(); // Save the CFG if we don't have it already if (!C) C = LC->getAnalysisDeclContext()->getUnoptimizedCFG(); if (!PM) PM = &LC->getParentMap(); if (Optional BE = P.getAs()) { const CFGBlock *CB = BE->getBlock(); reachable.insert(CB->getBlockID()); } } // Bail out if we didn't get the CFG or the ParentMap. if (!D || !C || !PM) return; // Don't do anything for template instantiations. Proving that code // in a template instantiation is unreachable means proving that it is // unreachable in all instantiations. if (const FunctionDecl *FD = dyn_cast(D)) if (FD->isTemplateInstantiation()) return; // Find CFGBlocks that were not covered by any node for (CFG::const_iterator I = C->begin(), E = C->end(); I != E; ++I) { const CFGBlock *CB = *I; // Check if the block is unreachable if (reachable.count(CB->getBlockID())) continue; // Check if the block is empty (an artificial block) if (isEmptyCFGBlock(CB)) continue; // Find the entry points for this block if (!visited.count(CB->getBlockID())) FindUnreachableEntryPoints(CB, reachable, visited); // This block may have been pruned; check if we still want to report it if (reachable.count(CB->getBlockID())) continue; // Check for false positives if (CB->size() > 0 && isInvalidPath(CB, *PM)) continue; // It is good practice to always have a "default" label in a "switch", even // if we should never get there. It can be used to detect errors, for // instance. Unreachable code directly under a "default" label is therefore // likely to be a false positive. if (const Stmt *label = CB->getLabel()) if (label->getStmtClass() == Stmt::DefaultStmtClass) continue; // Special case for __builtin_unreachable. // FIXME: This should be extended to include other unreachable markers, // such as llvm_unreachable. if (!CB->empty()) { bool foundUnreachable = false; for (CFGBlock::const_iterator ci = CB->begin(), ce = CB->end(); ci != ce; ++ci) { if (Optional S = (*ci).getAs()) if (const CallExpr *CE = dyn_cast(S->getStmt())) { if (CE->getBuiltinCallee() == Builtin::BI__builtin_unreachable) { foundUnreachable = true; break; } } } if (foundUnreachable) continue; } // We found a block that wasn't covered - find the statement to report SourceRange SR; PathDiagnosticLocation DL; SourceLocation SL; if (const Stmt *S = getUnreachableStmt(CB)) { SR = S->getSourceRange(); DL = PathDiagnosticLocation::createBegin(S, B.getSourceManager(), LC); SL = DL.asLocation(); if (SR.isInvalid() || !SL.isValid()) continue; } else continue; // Check if the SourceLocation is in a system header const SourceManager &SM = B.getSourceManager(); if (SM.isInSystemHeader(SL) || SM.isInExternCSystemHeader(SL)) continue; B.EmitBasicReport(D, this, "Unreachable code", "Dead code", "This statement is never executed", DL, SR); } } // Recursively finds the entry point(s) for this dead CFGBlock. void UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB, CFGBlocksSet &reachable, CFGBlocksSet &visited) { visited.insert(CB->getBlockID()); for (CFGBlock::const_pred_iterator I = CB->pred_begin(), E = CB->pred_end(); I != E; ++I) { if (!*I) continue; if (!reachable.count((*I)->getBlockID())) { // If we find an unreachable predecessor, mark this block as reachable so // we don't report this block reachable.insert(CB->getBlockID()); if (!visited.count((*I)->getBlockID())) // If we haven't previously visited the unreachable predecessor, recurse FindUnreachableEntryPoints(*I, reachable, visited); } } } // Find the Stmt* in a CFGBlock for reporting a warning const Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) { for (CFGBlock::const_iterator I = CB->begin(), E = CB->end(); I != E; ++I) { if (Optional S = I->getAs()) return S->getStmt(); } if (const Stmt *S = CB->getTerminator()) return S; else return nullptr; } // Determines if the path to this CFGBlock contained an element that infers this // block is a false positive. We assume that FindUnreachableEntryPoints has // already marked only the entry points to any dead code, so we need only to // find the condition that led to this block (the predecessor of this block.) // There will never be more than one predecessor. bool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB, const ParentMap &PM) { // We only expect a predecessor size of 0 or 1. If it is >1, then an external // condition has broken our assumption (for example, a sink being placed by // another check). In these cases, we choose not to report. if (CB->pred_size() > 1) return true; // If there are no predecessors, then this block is trivially unreachable if (CB->pred_size() == 0) return false; const CFGBlock *pred = *CB->pred_begin(); if (!pred) return false; // Get the predecessor block's terminator conditon const Stmt *cond = pred->getTerminatorCondition(); //assert(cond && "CFGBlock's predecessor has a terminator condition"); // The previous assertion is invalid in some cases (eg do/while). Leaving // reporting of these situations on at the moment to help triage these cases. if (!cond) return false; // Run each of the checks on the conditions if (containsMacro(cond) || containsEnum(cond) || containsStaticLocal(cond) || containsBuiltinOffsetOf(cond) || containsStmt(cond)) return true; return false; } // Returns true if the given CFGBlock is empty bool UnreachableCodeChecker::isEmptyCFGBlock(const CFGBlock *CB) { return CB->getLabel() == nullptr // No labels && CB->size() == 0 // No statements && !CB->getTerminator(); // No terminator } void ento::registerUnreachableCodeChecker(CheckerManager &mgr) { mgr.registerChecker(); } @ 1.1.1.3.4.1 log @file UnreachableCodeChecker.cpp was added on branch yamt-pagecache on 2014-05-22 16:18:31 +0000 @ text @d1 255 @ 1.1.1.3.4.2 log @sync with head. for a reference, the tree before this commit was tagged as yamt-pagecache-tag8. this commit was splitted into small chunks to avoid a limitation of cvs. ("Protocol error: too many arguments") @ text @a0 255 //==- UnreachableCodeChecker.cpp - Generalized dead code checker -*- C++ -*-==// // // The LLVM Compiler Infrastructure // // This file is distributed under the University of Illinois Open Source // License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // This file implements a generalized unreachable code checker using a // path-sensitive analysis. We mark any path visited, and then walk the CFG as a // post-analysis to determine what was never visited. // // A similar flow-sensitive only check exists in Analysis/ReachableCode.cpp //===----------------------------------------------------------------------===// #include "ClangSACheckers.h" #include "clang/AST/ParentMap.h" #include "clang/Basic/Builtins.h" #include "clang/Basic/SourceManager.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" #include "clang/StaticAnalyzer/Core/Checker.h" #include "clang/StaticAnalyzer/Core/CheckerManager.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" #include "llvm/ADT/SmallSet.h" // The number of CFGBlock pointers we want to reserve memory for. This is used // once for each function we analyze. #define DEFAULT_CFGBLOCKS 256 using namespace clang; using namespace ento; namespace { class UnreachableCodeChecker : public Checker { public: void checkEndAnalysis(ExplodedGraph &G, BugReporter &B, ExprEngine &Eng) const; private: typedef llvm::SmallSet CFGBlocksSet; static inline const Stmt *getUnreachableStmt(const CFGBlock *CB); static void FindUnreachableEntryPoints(const CFGBlock *CB, CFGBlocksSet &reachable, CFGBlocksSet &visited); static bool isInvalidPath(const CFGBlock *CB, const ParentMap &PM); static inline bool isEmptyCFGBlock(const CFGBlock *CB); }; } void UnreachableCodeChecker::checkEndAnalysis(ExplodedGraph &G, BugReporter &B, ExprEngine &Eng) const { CFGBlocksSet reachable, visited; if (Eng.hasWorkRemaining()) return; const Decl *D = 0; CFG *C = 0; ParentMap *PM = 0; const LocationContext *LC = 0; // Iterate over ExplodedGraph for (ExplodedGraph::node_iterator I = G.nodes_begin(), E = G.nodes_end(); I != E; ++I) { const ProgramPoint &P = I->getLocation(); LC = P.getLocationContext(); if (!LC->inTopFrame()) continue; if (!D) D = LC->getAnalysisDeclContext()->getDecl(); // Save the CFG if we don't have it already if (!C) C = LC->getAnalysisDeclContext()->getUnoptimizedCFG(); if (!PM) PM = &LC->getParentMap(); if (Optional BE = P.getAs()) { const CFGBlock *CB = BE->getBlock(); reachable.insert(CB->getBlockID()); } } // Bail out if we didn't get the CFG or the ParentMap. if (!D || !C || !PM) return; // Don't do anything for template instantiations. Proving that code // in a template instantiation is unreachable means proving that it is // unreachable in all instantiations. if (const FunctionDecl *FD = dyn_cast(D)) if (FD->isTemplateInstantiation()) return; // Find CFGBlocks that were not covered by any node for (CFG::const_iterator I = C->begin(), E = C->end(); I != E; ++I) { const CFGBlock *CB = *I; // Check if the block is unreachable if (reachable.count(CB->getBlockID())) continue; // Check if the block is empty (an artificial block) if (isEmptyCFGBlock(CB)) continue; // Find the entry points for this block if (!visited.count(CB->getBlockID())) FindUnreachableEntryPoints(CB, reachable, visited); // This block may have been pruned; check if we still want to report it if (reachable.count(CB->getBlockID())) continue; // Check for false positives if (CB->size() > 0 && isInvalidPath(CB, *PM)) continue; // It is good practice to always have a "default" label in a "switch", even // if we should never get there. It can be used to detect errors, for // instance. Unreachable code directly under a "default" label is therefore // likely to be a false positive. if (const Stmt *label = CB->getLabel()) if (label->getStmtClass() == Stmt::DefaultStmtClass) continue; // Special case for __builtin_unreachable. // FIXME: This should be extended to include other unreachable markers, // such as llvm_unreachable. if (!CB->empty()) { bool foundUnreachable = false; for (CFGBlock::const_iterator ci = CB->begin(), ce = CB->end(); ci != ce; ++ci) { if (Optional S = (*ci).getAs()) if (const CallExpr *CE = dyn_cast(S->getStmt())) { if (CE->getBuiltinCallee() == Builtin::BI__builtin_unreachable) { foundUnreachable = true; break; } } } if (foundUnreachable) continue; } // We found a block that wasn't covered - find the statement to report SourceRange SR; PathDiagnosticLocation DL; SourceLocation SL; if (const Stmt *S = getUnreachableStmt(CB)) { SR = S->getSourceRange(); DL = PathDiagnosticLocation::createBegin(S, B.getSourceManager(), LC); SL = DL.asLocation(); if (SR.isInvalid() || !SL.isValid()) continue; } else continue; // Check if the SourceLocation is in a system header const SourceManager &SM = B.getSourceManager(); if (SM.isInSystemHeader(SL) || SM.isInExternCSystemHeader(SL)) continue; B.EmitBasicReport(D, this, "Unreachable code", "Dead code", "This statement is never executed", DL, SR); } } // Recursively finds the entry point(s) for this dead CFGBlock. void UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB, CFGBlocksSet &reachable, CFGBlocksSet &visited) { visited.insert(CB->getBlockID()); for (CFGBlock::const_pred_iterator I = CB->pred_begin(), E = CB->pred_end(); I != E; ++I) { if (!*I) continue; if (!reachable.count((*I)->getBlockID())) { // If we find an unreachable predecessor, mark this block as reachable so // we don't report this block reachable.insert(CB->getBlockID()); if (!visited.count((*I)->getBlockID())) // If we haven't previously visited the unreachable predecessor, recurse FindUnreachableEntryPoints(*I, reachable, visited); } } } // Find the Stmt* in a CFGBlock for reporting a warning const Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) { for (CFGBlock::const_iterator I = CB->begin(), E = CB->end(); I != E; ++I) { if (Optional S = I->getAs()) return S->getStmt(); } if (const Stmt *S = CB->getTerminator()) return S; else return 0; } // Determines if the path to this CFGBlock contained an element that infers this // block is a false positive. We assume that FindUnreachableEntryPoints has // already marked only the entry points to any dead code, so we need only to // find the condition that led to this block (the predecessor of this block.) // There will never be more than one predecessor. bool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB, const ParentMap &PM) { // We only expect a predecessor size of 0 or 1. If it is >1, then an external // condition has broken our assumption (for example, a sink being placed by // another check). In these cases, we choose not to report. if (CB->pred_size() > 1) return true; // If there are no predecessors, then this block is trivially unreachable if (CB->pred_size() == 0) return false; const CFGBlock *pred = *CB->pred_begin(); if (!pred) return false; // Get the predecessor block's terminator conditon const Stmt *cond = pred->getTerminatorCondition(); //assert(cond && "CFGBlock's predecessor has a terminator condition"); // The previous assertion is invalid in some cases (eg do/while). Leaving // reporting of these situations on at the moment to help triage these cases. if (!cond) return false; // Run each of the checks on the conditions if (containsMacro(cond) || containsEnum(cond) || containsStaticLocal(cond) || containsBuiltinOffsetOf(cond) || containsStmt(cond)) return true; return false; } // Returns true if the given CFGBlock is empty bool UnreachableCodeChecker::isEmptyCFGBlock(const CFGBlock *CB) { return CB->getLabel() == 0 // No labels && CB->size() == 0 // No statements && !CB->getTerminator(); // No terminator } void ento::registerUnreachableCodeChecker(CheckerManager &mgr) { mgr.registerChecker(); } @