Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 1 | //==- UnreachableCodeChecker.cpp - Generalized dead code checker -*- C++ -*-==// |
| 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // This file implements a generalized unreachable code checker using a |
| 10 | // path-sensitive analysis. We mark any path visited, and then walk the CFG as a |
| 11 | // post-analysis to determine what was never visited. |
| 12 | // |
Jordy Rose | 5e04bdd | 2010-07-27 03:39:53 +0000 | [diff] [blame] | 13 | // A similar flow-sensitive only check exists in Analysis/ReachableCode.cpp |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 14 | //===----------------------------------------------------------------------===// |
| 15 | |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 16 | #include "clang/AST/ParentMap.h" |
| 17 | #include "clang/Basic/Builtins.h" |
Tom Care | f890679 | 2010-08-03 21:24:13 +0000 | [diff] [blame] | 18 | #include "clang/Basic/SourceManager.h" |
Argyrios Kyrtzidis | 98cabba | 2010-12-22 18:51:49 +0000 | [diff] [blame] | 19 | #include "clang/GR/PathSensitive/CheckerVisitor.h" |
| 20 | #include "clang/GR/PathSensitive/ExplodedGraph.h" |
| 21 | #include "clang/GR/PathSensitive/SVals.h" |
| 22 | #include "clang/GR/PathSensitive/CheckerHelpers.h" |
| 23 | #include "clang/GR/BugReporter/BugReporter.h" |
Argyrios Kyrtzidis | d2592a3 | 2010-12-22 18:53:44 +0000 | [diff] [blame^] | 24 | #include "ExprEngineExperimentalChecks.h" |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 25 | #include "llvm/ADT/SmallPtrSet.h" |
| 26 | |
| 27 | // The number of CFGBlock pointers we want to reserve memory for. This is used |
| 28 | // once for each function we analyze. |
| 29 | #define DEFAULT_CFGBLOCKS 256 |
| 30 | |
| 31 | using namespace clang; |
Argyrios Kyrtzidis | 5a4f98f | 2010-12-22 18:53:20 +0000 | [diff] [blame] | 32 | using namespace GR; |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 33 | |
| 34 | namespace { |
Tom Care | bfc4a95 | 2010-10-01 20:52:07 +0000 | [diff] [blame] | 35 | class UnreachableCodeChecker : public Checker { |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 36 | public: |
| 37 | static void *getTag(); |
Tom Care | bc42c53 | 2010-08-03 01:55:07 +0000 | [diff] [blame] | 38 | void VisitEndAnalysis(ExplodedGraph &G, |
| 39 | BugReporter &B, |
Argyrios Kyrtzidis | d2592a3 | 2010-12-22 18:53:44 +0000 | [diff] [blame^] | 40 | ExprEngine &Eng); |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 41 | private: |
Tom Care | f890679 | 2010-08-03 21:24:13 +0000 | [diff] [blame] | 42 | static inline const Stmt *getUnreachableStmt(const CFGBlock *CB); |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 43 | void FindUnreachableEntryPoints(const CFGBlock *CB); |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 44 | static bool isInvalidPath(const CFGBlock *CB, const ParentMap &PM); |
Tom Care | 505a506 | 2010-08-12 23:01:06 +0000 | [diff] [blame] | 45 | static inline bool isEmptyCFGBlock(const CFGBlock *CB); |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 46 | |
Tom Care | f890679 | 2010-08-03 21:24:13 +0000 | [diff] [blame] | 47 | llvm::SmallSet<unsigned, DEFAULT_CFGBLOCKS> reachable; |
| 48 | llvm::SmallSet<unsigned, DEFAULT_CFGBLOCKS> visited; |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 49 | }; |
| 50 | } |
| 51 | |
| 52 | void *UnreachableCodeChecker::getTag() { |
| 53 | static int x = 0; |
| 54 | return &x; |
| 55 | } |
| 56 | |
Argyrios Kyrtzidis | d2592a3 | 2010-12-22 18:53:44 +0000 | [diff] [blame^] | 57 | void GR::RegisterUnreachableCodeChecker(ExprEngine &Eng) { |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 58 | Eng.registerCheck(new UnreachableCodeChecker()); |
| 59 | } |
| 60 | |
| 61 | void UnreachableCodeChecker::VisitEndAnalysis(ExplodedGraph &G, |
| 62 | BugReporter &B, |
Argyrios Kyrtzidis | d2592a3 | 2010-12-22 18:53:44 +0000 | [diff] [blame^] | 63 | ExprEngine &Eng) { |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 64 | // Bail out if we didn't cover all paths |
Tom Care | bc42c53 | 2010-08-03 01:55:07 +0000 | [diff] [blame] | 65 | if (Eng.hasWorkRemaining()) |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 66 | return; |
| 67 | |
| 68 | CFG *C = 0; |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 69 | ParentMap *PM = 0; |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 70 | // Iterate over ExplodedGraph |
Tom Care | 505a506 | 2010-08-12 23:01:06 +0000 | [diff] [blame] | 71 | for (ExplodedGraph::node_iterator I = G.nodes_begin(), E = G.nodes_end(); |
| 72 | I != E; ++I) { |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 73 | const ProgramPoint &P = I->getLocation(); |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 74 | const LocationContext *LC = P.getLocationContext(); |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 75 | |
| 76 | // Save the CFG if we don't have it already |
| 77 | if (!C) |
Tom Care | f890679 | 2010-08-03 21:24:13 +0000 | [diff] [blame] | 78 | C = LC->getAnalysisContext()->getUnoptimizedCFG(); |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 79 | if (!PM) |
| 80 | PM = &LC->getParentMap(); |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 81 | |
| 82 | if (const BlockEntrance *BE = dyn_cast<BlockEntrance>(&P)) { |
| 83 | const CFGBlock *CB = BE->getBlock(); |
Tom Care | f890679 | 2010-08-03 21:24:13 +0000 | [diff] [blame] | 84 | reachable.insert(CB->getBlockID()); |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 85 | } |
| 86 | } |
| 87 | |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 88 | // Bail out if we didn't get the CFG or the ParentMap. |
| 89 | if (!C || !PM) |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 90 | return; |
| 91 | |
Jordy Rose | 5e04bdd | 2010-07-27 03:39:53 +0000 | [diff] [blame] | 92 | ASTContext &Ctx = B.getContext(); |
| 93 | |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 94 | // Find CFGBlocks that were not covered by any node |
Tom Care | 4895b9c | 2010-10-06 23:02:25 +0000 | [diff] [blame] | 95 | for (CFG::const_iterator I = C->begin(), E = C->end(); I != E; ++I) { |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 96 | const CFGBlock *CB = *I; |
| 97 | // Check if the block is unreachable |
Tom Care | f890679 | 2010-08-03 21:24:13 +0000 | [diff] [blame] | 98 | if (reachable.count(CB->getBlockID())) |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 99 | continue; |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 100 | |
Tom Care | 505a506 | 2010-08-12 23:01:06 +0000 | [diff] [blame] | 101 | // Check if the block is empty (an artificial block) |
| 102 | if (isEmptyCFGBlock(CB)) |
| 103 | continue; |
| 104 | |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 105 | // Find the entry points for this block |
Tom Care | 4895b9c | 2010-10-06 23:02:25 +0000 | [diff] [blame] | 106 | if (!visited.count(CB->getBlockID())) |
| 107 | FindUnreachableEntryPoints(CB); |
Jordy Rose | 5e04bdd | 2010-07-27 03:39:53 +0000 | [diff] [blame] | 108 | |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 109 | // This block may have been pruned; check if we still want to report it |
Tom Care | f890679 | 2010-08-03 21:24:13 +0000 | [diff] [blame] | 110 | if (reachable.count(CB->getBlockID())) |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 111 | continue; |
| 112 | |
| 113 | // Check for false positives |
| 114 | if (CB->size() > 0 && isInvalidPath(CB, *PM)) |
| 115 | continue; |
| 116 | |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 117 | // Special case for __builtin_unreachable. |
| 118 | // FIXME: This should be extended to include other unreachable markers, |
| 119 | // such as llvm_unreachable. |
| 120 | if (!CB->empty()) { |
Zhongxing Xu | b36cd3e | 2010-09-16 01:25:47 +0000 | [diff] [blame] | 121 | CFGElement First = CB->front(); |
| 122 | if (CFGStmt S = First.getAs<CFGStmt>()) { |
| 123 | if (const CallExpr *CE = dyn_cast<CallExpr>(S.getStmt())) { |
| 124 | if (CE->isBuiltinCall(Ctx) == Builtin::BI__builtin_unreachable) |
| 125 | continue; |
| 126 | } |
Jordy Rose | 5e04bdd | 2010-07-27 03:39:53 +0000 | [diff] [blame] | 127 | } |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 128 | } |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 129 | |
Tom Care | f890679 | 2010-08-03 21:24:13 +0000 | [diff] [blame] | 130 | // We found a block that wasn't covered - find the statement to report |
| 131 | SourceRange SR; |
| 132 | SourceLocation SL; |
| 133 | if (const Stmt *S = getUnreachableStmt(CB)) { |
| 134 | SR = S->getSourceRange(); |
| 135 | SL = S->getLocStart(); |
| 136 | if (SR.isInvalid() || SL.isInvalid()) |
| 137 | continue; |
| 138 | } |
| 139 | else |
| 140 | continue; |
| 141 | |
| 142 | // Check if the SourceLocation is in a system header |
| 143 | const SourceManager &SM = B.getSourceManager(); |
| 144 | if (SM.isInSystemHeader(SL) || SM.isInExternCSystemHeader(SL)) |
| 145 | continue; |
| 146 | |
| 147 | B.EmitBasicReport("Unreachable code", "Dead code", "This statement is never" |
| 148 | " executed", SL, SR); |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 149 | } |
| 150 | } |
| 151 | |
| 152 | // Recursively finds the entry point(s) for this dead CFGBlock. |
| 153 | void UnreachableCodeChecker::FindUnreachableEntryPoints(const CFGBlock *CB) { |
Tom Care | f890679 | 2010-08-03 21:24:13 +0000 | [diff] [blame] | 154 | visited.insert(CB->getBlockID()); |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 155 | |
Tom Care | 4895b9c | 2010-10-06 23:02:25 +0000 | [diff] [blame] | 156 | for (CFGBlock::const_pred_iterator I = CB->pred_begin(), E = CB->pred_end(); |
| 157 | I != E; ++I) { |
Tom Care | 0600918 | 2010-08-05 17:53:44 +0000 | [diff] [blame] | 158 | if (!reachable.count((*I)->getBlockID())) { |
Tom Care | 4895b9c | 2010-10-06 23:02:25 +0000 | [diff] [blame] | 159 | // If we find an unreachable predecessor, mark this block as reachable so |
| 160 | // we don't report this block |
| 161 | reachable.insert(CB->getBlockID()); |
Tom Care | 0600918 | 2010-08-05 17:53:44 +0000 | [diff] [blame] | 162 | if (!visited.count((*I)->getBlockID())) |
Tom Care | 4895b9c | 2010-10-06 23:02:25 +0000 | [diff] [blame] | 163 | // If we haven't previously visited the unreachable predecessor, recurse |
Tom Care | 0600918 | 2010-08-05 17:53:44 +0000 | [diff] [blame] | 164 | FindUnreachableEntryPoints(*I); |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 165 | } |
| 166 | } |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 167 | } |
| 168 | |
Tom Care | f890679 | 2010-08-03 21:24:13 +0000 | [diff] [blame] | 169 | // Find the Stmt* in a CFGBlock for reporting a warning |
| 170 | const Stmt *UnreachableCodeChecker::getUnreachableStmt(const CFGBlock *CB) { |
Zhongxing Xu | b36cd3e | 2010-09-16 01:25:47 +0000 | [diff] [blame] | 171 | for (CFGBlock::const_iterator I = CB->begin(), E = CB->end(); I != E; ++I) { |
| 172 | if (CFGStmt S = I->getAs<CFGStmt>()) |
| 173 | return S; |
| 174 | } |
| 175 | if (const Stmt *S = CB->getTerminator()) |
Tom Care | f890679 | 2010-08-03 21:24:13 +0000 | [diff] [blame] | 176 | return S; |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 177 | else |
Tom Care | f890679 | 2010-08-03 21:24:13 +0000 | [diff] [blame] | 178 | return 0; |
Tom Care | c4b5bd8 | 2010-07-23 23:04:53 +0000 | [diff] [blame] | 179 | } |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 180 | |
Tom Care | f890679 | 2010-08-03 21:24:13 +0000 | [diff] [blame] | 181 | // Determines if the path to this CFGBlock contained an element that infers this |
| 182 | // block is a false positive. We assume that FindUnreachableEntryPoints has |
| 183 | // already marked only the entry points to any dead code, so we need only to |
| 184 | // find the condition that led to this block (the predecessor of this block.) |
| 185 | // There will never be more than one predecessor. |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 186 | bool UnreachableCodeChecker::isInvalidPath(const CFGBlock *CB, |
| 187 | const ParentMap &PM) { |
Tom Care | aaca011 | 2010-08-27 22:37:31 +0000 | [diff] [blame] | 188 | // We only expect a predecessor size of 0 or 1. If it is >1, then an external |
| 189 | // condition has broken our assumption (for example, a sink being placed by |
| 190 | // another check). In these cases, we choose not to report. |
| 191 | if (CB->pred_size() > 1) |
| 192 | return true; |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 193 | |
Tom Care | f890679 | 2010-08-03 21:24:13 +0000 | [diff] [blame] | 194 | // If there are no predecessors, then this block is trivially unreachable |
| 195 | if (CB->pred_size() == 0) |
| 196 | return false; |
| 197 | |
| 198 | const CFGBlock *pred = *CB->pred_begin(); |
| 199 | |
| 200 | // Get the predecessor block's terminator conditon |
| 201 | const Stmt *cond = pred->getTerminatorCondition(); |
Tom Care | 505a506 | 2010-08-12 23:01:06 +0000 | [diff] [blame] | 202 | |
| 203 | //assert(cond && "CFGBlock's predecessor has a terminator condition"); |
| 204 | // The previous assertion is invalid in some cases (eg do/while). Leaving |
| 205 | // reporting of these situations on at the moment to help triage these cases. |
| 206 | if (!cond) |
| 207 | return false; |
Tom Care | f890679 | 2010-08-03 21:24:13 +0000 | [diff] [blame] | 208 | |
| 209 | // Run each of the checks on the conditions |
| 210 | if (containsMacro(cond) || containsEnum(cond) |
| 211 | || containsStaticLocal(cond) || containsBuiltinOffsetOf(cond) |
| 212 | || containsStmt<SizeOfAlignOfExpr>(cond)) |
| 213 | return true; |
Tom Care | 7bce3a1 | 2010-07-27 23:30:21 +0000 | [diff] [blame] | 214 | |
| 215 | return false; |
| 216 | } |
Tom Care | 505a506 | 2010-08-12 23:01:06 +0000 | [diff] [blame] | 217 | |
| 218 | // Returns true if the given CFGBlock is empty |
| 219 | bool UnreachableCodeChecker::isEmptyCFGBlock(const CFGBlock *CB) { |
| 220 | return CB->getLabel() == 0 // No labels |
| 221 | && CB->size() == 0 // No statements |
| 222 | && CB->getTerminator() == 0; // No terminator |
| 223 | } |