blob: 271ba4702c579960f936d97c5c4c4782f393daa9 [file] [log] [blame]
Tom Care3ff08a82010-07-06 21:43:29 +00001//==- IdempotentOperationChecker.cpp - Idempotent Operations ----*- 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//
10// This file defines a set of path-sensitive checks for idempotent and/or
11// tautological operations. Each potential operation is checked along all paths
12// to see if every path results in a pointless operation.
13// +-------------------------------------------+
14// |Table of idempotent/tautological operations|
15// +-------------------------------------------+
16//+--------------------------------------------------------------------------+
17//|Operator | x op x | x op 1 | 1 op x | x op 0 | 0 op x | x op ~0 | ~0 op x |
18//+--------------------------------------------------------------------------+
19// +, += | | | | x | x | |
20// -, -= | | | | x | -x | |
21// *, *= | | x | x | 0 | 0 | |
22// /, /= | 1 | x | | N/A | 0 | |
23// &, &= | x | | | 0 | 0 | x | x
24// |, |= | x | | | x | x | ~0 | ~0
25// ^, ^= | 0 | | | x | x | |
26// <<, <<= | | | | x | 0 | |
27// >>, >>= | | | | x | 0 | |
28// || | 1 | 1 | 1 | x | x | 1 | 1
29// && | 1 | x | x | 0 | 0 | x | x
30// = | x | | | | | |
31// == | 1 | | | | | |
32// >= | 1 | | | | | |
33// <= | 1 | | | | | |
34// > | 0 | | | | | |
35// < | 0 | | | | | |
36// != | 0 | | | | | |
37//===----------------------------------------------------------------------===//
38//
Tom Caref8a98632010-08-12 22:45:47 +000039// Things TODO:
Tom Care3ff08a82010-07-06 21:43:29 +000040// - Improved error messages
41// - Handle mixed assumptions (which assumptions can belong together?)
42// - Finer grained false positive control (levels)
Tom Caref8a98632010-08-12 22:45:47 +000043// - Handling ~0 values
Tom Care3ff08a82010-07-06 21:43:29 +000044
Argyrios Kyrtzidisb2400922011-02-15 22:55:14 +000045#include "ClangSACheckers.h"
Chandler Carruth3a022472012-12-04 09:13:33 +000046#include "clang/AST/Stmt.h"
Ted Kremenek80861ca2011-02-23 01:51:59 +000047#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
Chandler Carruth3a022472012-12-04 09:13:33 +000048#include "clang/Analysis/Analyses/PseudoConstantAnalysis.h"
49#include "clang/Analysis/CFGStmtMap.h"
50#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
51#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
Argyrios Kyrtzidis6a5674f2011-03-01 01:16:21 +000052#include "clang/StaticAnalyzer/Core/Checker.h"
Argyrios Kyrtzidis507ff532011-02-17 21:39:17 +000053#include "clang/StaticAnalyzer/Core/CheckerManager.h"
Argyrios Kyrtzidis66b38c22011-02-23 21:04:44 +000054#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
Ted Kremenekf8cbac42011-02-10 01:03:03 +000055#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
Ted Kremenekf8cbac42011-02-10 01:03:03 +000056#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
57#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
Chandler Carruth3a022472012-12-04 09:13:33 +000058#include "llvm/ADT/BitVector.h"
Tom Care3ff08a82010-07-06 21:43:29 +000059#include "llvm/ADT/DenseMap.h"
Tom Caref8a98632010-08-12 22:45:47 +000060#include "llvm/ADT/SmallSet.h"
Benjamin Kramer49038022012-02-04 13:45:25 +000061#include "llvm/ADT/SmallString.h"
Chandler Carruthdce439d2010-07-07 00:07:37 +000062#include "llvm/Support/ErrorHandling.h"
Benjamin Kramer444a1302012-12-01 17:12:56 +000063#include "llvm/Support/raw_ostream.h"
Tom Care3ff08a82010-07-06 21:43:29 +000064
65using namespace clang;
Ted Kremenek98857c92010-12-23 07:20:52 +000066using namespace ento;
Tom Care3ff08a82010-07-06 21:43:29 +000067
68namespace {
69class IdempotentOperationChecker
Argyrios Kyrtzidis6a5674f2011-03-01 01:16:21 +000070 : public Checker<check::PreStmt<BinaryOperator>,
Argyrios Kyrtzidis66b38c22011-02-23 21:04:44 +000071 check::PostStmt<BinaryOperator>,
72 check::EndAnalysis> {
Tom Care68df12f2010-09-09 02:04:52 +000073public:
Argyrios Kyrtzidis66b38c22011-02-23 21:04:44 +000074 void checkPreStmt(const BinaryOperator *B, CheckerContext &C) const;
75 void checkPostStmt(const BinaryOperator *B, CheckerContext &C) const;
76 void checkEndAnalysis(ExplodedGraph &G, BugReporter &B,ExprEngine &Eng) const;
Tom Care68df12f2010-09-09 02:04:52 +000077
78private:
79 // Our assumption about a particular operation.
80 enum Assumption { Possible = 0, Impossible, Equal, LHSis1, RHSis1, LHSis0,
81 RHSis0 };
82
Argyrios Kyrtzidis66b38c22011-02-23 21:04:44 +000083 static void UpdateAssumption(Assumption &A, const Assumption &New);
Tom Care68df12f2010-09-09 02:04:52 +000084
85 // False positive reduction methods
86 static bool isSelfAssign(const Expr *LHS, const Expr *RHS);
Ted Kremenek81ce1c82011-10-24 01:32:45 +000087 static bool isUnused(const Expr *E, AnalysisDeclContext *AC);
Tom Care68df12f2010-09-09 02:04:52 +000088 static bool isTruncationExtensionAssignment(const Expr *LHS,
89 const Expr *RHS);
Ted Kremenek81ce1c82011-10-24 01:32:45 +000090 static bool pathWasCompletelyAnalyzed(AnalysisDeclContext *AC,
Argyrios Kyrtzidis66b38c22011-02-23 21:04:44 +000091 const CFGBlock *CB,
92 const CoreEngine &CE);
Tom Care68df12f2010-09-09 02:04:52 +000093 static bool CanVary(const Expr *Ex,
Ted Kremenek81ce1c82011-10-24 01:32:45 +000094 AnalysisDeclContext *AC);
Tom Care68df12f2010-09-09 02:04:52 +000095 static bool isConstantOrPseudoConstant(const DeclRefExpr *DR,
Ted Kremenek81ce1c82011-10-24 01:32:45 +000096 AnalysisDeclContext *AC);
Tom Care68df12f2010-09-09 02:04:52 +000097 static bool containsNonLocalVarDecl(const Stmt *S);
Tom Care68df12f2010-09-09 02:04:52 +000098
99 // Hash table and related data structures
100 struct BinaryOperatorData {
Anna Zaks208d54c2011-10-03 23:07:13 +0000101 BinaryOperatorData() : assumption(Possible) {}
Tom Care68df12f2010-09-09 02:04:52 +0000102
103 Assumption assumption;
Tom Care68df12f2010-09-09 02:04:52 +0000104 ExplodedNodeSet explodedNodes; // Set of ExplodedNodes that refer to a
105 // BinaryOperator
106 };
107 typedef llvm::DenseMap<const BinaryOperator *, BinaryOperatorData>
108 AssumptionMap;
Argyrios Kyrtzidis66b38c22011-02-23 21:04:44 +0000109 mutable AssumptionMap hash;
Tom Care698daef2012-05-31 21:24:58 +0000110 mutable OwningPtr<BugType> BT;
Tom Care3ff08a82010-07-06 21:43:29 +0000111};
112}
113
Argyrios Kyrtzidis66b38c22011-02-23 21:04:44 +0000114void IdempotentOperationChecker::checkPreStmt(const BinaryOperator *B,
115 CheckerContext &C) const {
Ted Kremenek8a4a2b12010-08-02 20:33:02 +0000116 // Find or create an entry in the hash for this BinaryOperator instance.
117 // If we haven't done a lookup before, it will get default initialized to
Tom Care796ed502010-09-02 23:30:22 +0000118 // 'Possible'. At this stage we do not store the ExplodedNode, as it has not
119 // been created yet.
120 BinaryOperatorData &Data = hash[B];
121 Assumption &A = Data.assumption;
Ted Kremenek81ce1c82011-10-24 01:32:45 +0000122 AnalysisDeclContext *AC = C.getCurrentAnalysisDeclContext();
Tom Care3ff08a82010-07-06 21:43:29 +0000123
124 // If we already have visited this node on a path that does not contain an
125 // idempotent operation, return immediately.
126 if (A == Impossible)
127 return;
128
Tom Caref8a98632010-08-12 22:45:47 +0000129 // Retrieve both sides of the operator and determine if they can vary (which
130 // may mean this is a false positive.
Tom Care3ff08a82010-07-06 21:43:29 +0000131 const Expr *LHS = B->getLHS();
132 const Expr *RHS = B->getRHS();
Tom Careb9933f32010-08-18 21:17:24 +0000133
Tom Caree332c3b2010-08-23 19:51:57 +0000134 // At this stage we can calculate whether each side contains a false positive
135 // that applies to all operators. We only need to calculate this the first
136 // time.
137 bool LHSContainsFalsePositive = false, RHSContainsFalsePositive = false;
Tom Careb9933f32010-08-18 21:17:24 +0000138 if (A == Possible) {
Tom Caree332c3b2010-08-23 19:51:57 +0000139 // An expression contains a false positive if it can't vary, or if it
140 // contains a known false positive VarDecl.
141 LHSContainsFalsePositive = !CanVary(LHS, AC)
142 || containsNonLocalVarDecl(LHS);
143 RHSContainsFalsePositive = !CanVary(RHS, AC)
144 || containsNonLocalVarDecl(RHS);
Tom Careb9933f32010-08-18 21:17:24 +0000145 }
Tom Care3ff08a82010-07-06 21:43:29 +0000146
Ted Kremenek49b1e382012-01-26 21:29:00 +0000147 ProgramStateRef state = C.getState();
Ted Kremenek632e3b72012-01-06 22:09:28 +0000148 const LocationContext *LCtx = C.getLocationContext();
149 SVal LHSVal = state->getSVal(LHS, LCtx);
150 SVal RHSVal = state->getSVal(RHS, LCtx);
Tom Care3ff08a82010-07-06 21:43:29 +0000151
152 // If either value is unknown, we can't be 100% sure of all paths.
153 if (LHSVal.isUnknownOrUndef() || RHSVal.isUnknownOrUndef()) {
154 A = Impossible;
155 return;
156 }
157 BinaryOperator::Opcode Op = B->getOpcode();
158
159 // Dereference the LHS SVal if this is an assign operation
160 switch (Op) {
161 default:
162 break;
163
164 // Fall through intentional
John McCalle3027922010-08-25 11:45:40 +0000165 case BO_AddAssign:
166 case BO_SubAssign:
167 case BO_MulAssign:
168 case BO_DivAssign:
169 case BO_AndAssign:
170 case BO_OrAssign:
171 case BO_XorAssign:
172 case BO_ShlAssign:
173 case BO_ShrAssign:
174 case BO_Assign:
Tom Care3ff08a82010-07-06 21:43:29 +0000175 // Assign statements have one extra level of indirection
David Blaikie2fdacbc2013-02-20 05:52:05 +0000176 if (!LHSVal.getAs<Loc>()) {
Tom Care3ff08a82010-07-06 21:43:29 +0000177 A = Impossible;
178 return;
179 }
David Blaikie2fdacbc2013-02-20 05:52:05 +0000180 LHSVal = state->getSVal(LHSVal.castAs<Loc>(), LHS->getType());
Tom Care3ff08a82010-07-06 21:43:29 +0000181 }
182
183
184 // We now check for various cases which result in an idempotent operation.
185
186 // x op x
187 switch (Op) {
188 default:
189 break; // We don't care about any other operators.
190
191 // Fall through intentional
John McCalle3027922010-08-25 11:45:40 +0000192 case BO_Assign:
Tom Care9026d4b2010-08-30 19:25:43 +0000193 // x Assign x can be used to silence unused variable warnings intentionally.
194 // If this is a self assignment and the variable is referenced elsewhere,
Tom Carebc9eaef2010-09-07 20:27:56 +0000195 // and the assignment is not a truncation or extension, then it is a false
196 // positive.
Tom Care9026d4b2010-08-30 19:25:43 +0000197 if (isSelfAssign(LHS, RHS)) {
Tom Carebc9eaef2010-09-07 20:27:56 +0000198 if (!isUnused(LHS, AC) && !isTruncationExtensionAssignment(LHS, RHS)) {
Tom Care9026d4b2010-08-30 19:25:43 +0000199 UpdateAssumption(A, Equal);
200 return;
201 }
202 else {
203 A = Impossible;
204 return;
205 }
Tom Care826e6b42010-07-16 20:41:41 +0000206 }
207
John McCalle3027922010-08-25 11:45:40 +0000208 case BO_SubAssign:
209 case BO_DivAssign:
210 case BO_AndAssign:
211 case BO_OrAssign:
212 case BO_XorAssign:
213 case BO_Sub:
214 case BO_Div:
215 case BO_And:
216 case BO_Or:
217 case BO_Xor:
218 case BO_LOr:
219 case BO_LAnd:
Tom Care71cc9d82010-08-27 22:50:47 +0000220 case BO_EQ:
221 case BO_NE:
Tom Caree332c3b2010-08-23 19:51:57 +0000222 if (LHSVal != RHSVal || LHSContainsFalsePositive
223 || RHSContainsFalsePositive)
Tom Care3ff08a82010-07-06 21:43:29 +0000224 break;
225 UpdateAssumption(A, Equal);
226 return;
227 }
228
229 // x op 1
230 switch (Op) {
231 default:
232 break; // We don't care about any other operators.
233
234 // Fall through intentional
John McCalle3027922010-08-25 11:45:40 +0000235 case BO_MulAssign:
236 case BO_DivAssign:
237 case BO_Mul:
238 case BO_Div:
239 case BO_LOr:
240 case BO_LAnd:
Tom Caree332c3b2010-08-23 19:51:57 +0000241 if (!RHSVal.isConstant(1) || RHSContainsFalsePositive)
Tom Care3ff08a82010-07-06 21:43:29 +0000242 break;
243 UpdateAssumption(A, RHSis1);
244 return;
245 }
246
247 // 1 op x
248 switch (Op) {
249 default:
250 break; // We don't care about any other operators.
251
252 // Fall through intentional
John McCalle3027922010-08-25 11:45:40 +0000253 case BO_MulAssign:
254 case BO_Mul:
255 case BO_LOr:
256 case BO_LAnd:
Tom Caree332c3b2010-08-23 19:51:57 +0000257 if (!LHSVal.isConstant(1) || LHSContainsFalsePositive)
Tom Care3ff08a82010-07-06 21:43:29 +0000258 break;
259 UpdateAssumption(A, LHSis1);
260 return;
261 }
262
263 // x op 0
264 switch (Op) {
265 default:
266 break; // We don't care about any other operators.
267
268 // Fall through intentional
John McCalle3027922010-08-25 11:45:40 +0000269 case BO_AddAssign:
270 case BO_SubAssign:
271 case BO_MulAssign:
272 case BO_AndAssign:
273 case BO_OrAssign:
274 case BO_XorAssign:
275 case BO_Add:
276 case BO_Sub:
277 case BO_Mul:
278 case BO_And:
279 case BO_Or:
280 case BO_Xor:
281 case BO_Shl:
282 case BO_Shr:
283 case BO_LOr:
284 case BO_LAnd:
Tom Caree332c3b2010-08-23 19:51:57 +0000285 if (!RHSVal.isConstant(0) || RHSContainsFalsePositive)
Tom Care3ff08a82010-07-06 21:43:29 +0000286 break;
287 UpdateAssumption(A, RHSis0);
288 return;
289 }
290
291 // 0 op x
292 switch (Op) {
293 default:
294 break; // We don't care about any other operators.
295
296 // Fall through intentional
John McCalle3027922010-08-25 11:45:40 +0000297 //case BO_AddAssign: // Common false positive
298 case BO_SubAssign: // Check only if unsigned
299 case BO_MulAssign:
300 case BO_DivAssign:
301 case BO_AndAssign:
302 //case BO_OrAssign: // Common false positive
303 //case BO_XorAssign: // Common false positive
304 case BO_ShlAssign:
305 case BO_ShrAssign:
306 case BO_Add:
307 case BO_Sub:
308 case BO_Mul:
309 case BO_Div:
310 case BO_And:
311 case BO_Or:
312 case BO_Xor:
313 case BO_Shl:
314 case BO_Shr:
315 case BO_LOr:
316 case BO_LAnd:
Tom Caree332c3b2010-08-23 19:51:57 +0000317 if (!LHSVal.isConstant(0) || LHSContainsFalsePositive)
Tom Care3ff08a82010-07-06 21:43:29 +0000318 break;
319 UpdateAssumption(A, LHSis0);
320 return;
321 }
322
323 // If we get to this point, there has been a valid use of this operation.
324 A = Impossible;
325}
326
Tom Care796ed502010-09-02 23:30:22 +0000327// At the post visit stage, the predecessor ExplodedNode will be the
328// BinaryOperator that was just created. We use this hook to collect the
329// ExplodedNode.
Argyrios Kyrtzidis66b38c22011-02-23 21:04:44 +0000330void IdempotentOperationChecker::checkPostStmt(const BinaryOperator *B,
331 CheckerContext &C) const {
Tom Care796ed502010-09-02 23:30:22 +0000332 // Add the ExplodedNode we just visited
333 BinaryOperatorData &Data = hash[B];
Ted Kremenekc0597982011-02-12 18:50:03 +0000334
David Blaikie87396b92013-02-21 22:23:56 +0000335 const Stmt *predStmt =
336 C.getPredecessor()->getLocation().castAs<StmtPoint>().getStmt();
337
Ted Kremenekc0597982011-02-12 18:50:03 +0000338 // Ignore implicit calls to setters.
Ted Kremenekcdb2ae52011-03-15 19:27:57 +0000339 if (!isa<BinaryOperator>(predStmt))
Ted Kremenekc0597982011-02-12 18:50:03 +0000340 return;
Ted Kremenekcdb2ae52011-03-15 19:27:57 +0000341
Tom Care796ed502010-09-02 23:30:22 +0000342 Data.explodedNodes.Add(C.getPredecessor());
343}
344
Argyrios Kyrtzidis66b38c22011-02-23 21:04:44 +0000345void IdempotentOperationChecker::checkEndAnalysis(ExplodedGraph &G,
Ted Kremenek83b598c2010-07-27 18:49:08 +0000346 BugReporter &BR,
Argyrios Kyrtzidis66b38c22011-02-23 21:04:44 +0000347 ExprEngine &Eng) const {
Tom Care698daef2012-05-31 21:24:58 +0000348 if (!BT)
349 BT.reset(new BugType("Idempotent operation", "Dead code"));
350
Tom Care3ff08a82010-07-06 21:43:29 +0000351 // Iterate over the hash to see if we have any paths with definite
352 // idempotent operations.
Tom Caref8a98632010-08-12 22:45:47 +0000353 for (AssumptionMap::const_iterator i = hash.begin(); i != hash.end(); ++i) {
354 // Unpack the hash contents
Tom Care796ed502010-09-02 23:30:22 +0000355 const BinaryOperatorData &Data = i->second;
356 const Assumption &A = Data.assumption;
Tom Care796ed502010-09-02 23:30:22 +0000357 const ExplodedNodeSet &ES = Data.explodedNodes;
Ted Kremenek83b598c2010-07-27 18:49:08 +0000358
Anna Zaks208d54c2011-10-03 23:07:13 +0000359 // If there are no nodes accosted with the expression, nothing to report.
360 // FIXME: This is possible because the checker does part of processing in
361 // checkPreStmt and part in checkPostStmt.
362 if (ES.begin() == ES.end())
363 continue;
364
Tom Caref8a98632010-08-12 22:45:47 +0000365 const BinaryOperator *B = i->first;
Tom Care3ff08a82010-07-06 21:43:29 +0000366
Tom Caref8a98632010-08-12 22:45:47 +0000367 if (A == Impossible)
368 continue;
369
370 // If the analyzer did not finish, check to see if we can still emit this
371 // warning
372 if (Eng.hasWorkRemaining()) {
Tom Caref8a98632010-08-12 22:45:47 +0000373 // If we can trace back
Ted Kremenek81ce1c82011-10-24 01:32:45 +0000374 AnalysisDeclContext *AC = (*ES.begin())->getLocationContext()
375 ->getAnalysisDeclContext();
Ted Kremenek80861ca2011-02-23 01:51:59 +0000376 if (!pathWasCompletelyAnalyzed(AC,
377 AC->getCFGStmtMap()->getBlock(B),
Tom Caref8a98632010-08-12 22:45:47 +0000378 Eng.getCoreEngine()))
379 continue;
Tom Care3ff08a82010-07-06 21:43:29 +0000380 }
Tom Caref8a98632010-08-12 22:45:47 +0000381
Tom Care796ed502010-09-02 23:30:22 +0000382 // Select the error message and SourceRanges to report.
Dylan Noblesmith2c1dd272012-02-05 02:13:05 +0000383 SmallString<128> buf;
Tom Caref8a98632010-08-12 22:45:47 +0000384 llvm::raw_svector_ostream os(buf);
Tom Care796ed502010-09-02 23:30:22 +0000385 bool LHSRelevant = false, RHSRelevant = false;
Tom Caref8a98632010-08-12 22:45:47 +0000386 switch (A) {
387 case Equal:
Tom Care796ed502010-09-02 23:30:22 +0000388 LHSRelevant = true;
389 RHSRelevant = true;
John McCalle3027922010-08-25 11:45:40 +0000390 if (B->getOpcode() == BO_Assign)
Tom Caref8a98632010-08-12 22:45:47 +0000391 os << "Assigned value is always the same as the existing value";
392 else
393 os << "Both operands to '" << B->getOpcodeStr()
394 << "' always have the same value";
395 break;
396 case LHSis1:
Tom Care796ed502010-09-02 23:30:22 +0000397 LHSRelevant = true;
Tom Caref8a98632010-08-12 22:45:47 +0000398 os << "The left operand to '" << B->getOpcodeStr() << "' is always 1";
399 break;
400 case RHSis1:
Tom Care796ed502010-09-02 23:30:22 +0000401 RHSRelevant = true;
Tom Caref8a98632010-08-12 22:45:47 +0000402 os << "The right operand to '" << B->getOpcodeStr() << "' is always 1";
403 break;
404 case LHSis0:
Tom Care796ed502010-09-02 23:30:22 +0000405 LHSRelevant = true;
Tom Caref8a98632010-08-12 22:45:47 +0000406 os << "The left operand to '" << B->getOpcodeStr() << "' is always 0";
407 break;
408 case RHSis0:
Tom Care796ed502010-09-02 23:30:22 +0000409 RHSRelevant = true;
Tom Caref8a98632010-08-12 22:45:47 +0000410 os << "The right operand to '" << B->getOpcodeStr() << "' is always 0";
411 break;
412 case Possible:
413 llvm_unreachable("Operation was never marked with an assumption");
414 case Impossible:
415 llvm_unreachable(0);
416 }
417
Tom Care796ed502010-09-02 23:30:22 +0000418 // Add a report for each ExplodedNode
419 for (ExplodedNodeSet::iterator I = ES.begin(), E = ES.end(); I != E; ++I) {
Anna Zaks3a6bdf82011-08-17 23:00:25 +0000420 BugReport *report = new BugReport(*BT, os.str(), *I);
Tom Care796ed502010-09-02 23:30:22 +0000421
422 // Add source ranges and visitor hooks
423 if (LHSRelevant) {
424 const Expr *LHS = i->first->getLHS();
425 report->addRange(LHS->getSourceRange());
Anna Zaks05fb3712013-03-28 23:15:22 +0000426 FindLastStoreBRVisitor::registerStatementVarDecls(*report, LHS, false);
Tom Care796ed502010-09-02 23:30:22 +0000427 }
428 if (RHSRelevant) {
429 const Expr *RHS = i->first->getRHS();
430 report->addRange(i->first->getRHS()->getSourceRange());
Anna Zaks05fb3712013-03-28 23:15:22 +0000431 FindLastStoreBRVisitor::registerStatementVarDecls(*report, RHS, false);
Tom Care796ed502010-09-02 23:30:22 +0000432 }
433
Jordan Rosee10d5a72012-11-02 01:53:40 +0000434 BR.emitReport(report);
Tom Care796ed502010-09-02 23:30:22 +0000435 }
Tom Care3ff08a82010-07-06 21:43:29 +0000436 }
Argyrios Kyrtzidis66b38c22011-02-23 21:04:44 +0000437
438 hash.clear();
Tom Care3ff08a82010-07-06 21:43:29 +0000439}
440
441// Updates the current assumption given the new assumption
442inline void IdempotentOperationChecker::UpdateAssumption(Assumption &A,
443 const Assumption &New) {
Tom Carec29c91a2010-08-27 22:35:28 +0000444// If the assumption is the same, there is nothing to do
445 if (A == New)
446 return;
447
Tom Care3ff08a82010-07-06 21:43:29 +0000448 switch (A) {
449 // If we don't currently have an assumption, set it
450 case Possible:
451 A = New;
452 return;
453
454 // If we have determined that a valid state happened, ignore the new
455 // assumption.
456 case Impossible:
457 return;
458
459 // Any other case means that we had a different assumption last time. We don't
460 // currently support mixing assumptions for diagnostic reasons, so we set
461 // our assumption to be impossible.
462 default:
463 A = Impossible;
464 return;
465 }
466}
467
Tom Care9026d4b2010-08-30 19:25:43 +0000468// Check for a statement where a variable is self assigned to possibly avoid an
469// unused variable warning.
470bool IdempotentOperationChecker::isSelfAssign(const Expr *LHS, const Expr *RHS) {
Tom Care826e6b42010-07-16 20:41:41 +0000471 LHS = LHS->IgnoreParenCasts();
472 RHS = RHS->IgnoreParenCasts();
473
474 const DeclRefExpr *LHS_DR = dyn_cast<DeclRefExpr>(LHS);
475 if (!LHS_DR)
476 return false;
477
Tom Carea4603112010-08-24 21:09:07 +0000478 const VarDecl *VD = dyn_cast<VarDecl>(LHS_DR->getDecl());
479 if (!VD)
Tom Care826e6b42010-07-16 20:41:41 +0000480 return false;
481
482 const DeclRefExpr *RHS_DR = dyn_cast<DeclRefExpr>(RHS);
483 if (!RHS_DR)
484 return false;
485
Tom Carea4603112010-08-24 21:09:07 +0000486 if (VD != RHS_DR->getDecl())
487 return false;
488
Tom Care9026d4b2010-08-30 19:25:43 +0000489 return true;
490}
491
492// Returns true if the Expr points to a VarDecl that is not read anywhere
493// outside of self-assignments.
494bool IdempotentOperationChecker::isUnused(const Expr *E,
Ted Kremenek81ce1c82011-10-24 01:32:45 +0000495 AnalysisDeclContext *AC) {
Tom Care9026d4b2010-08-30 19:25:43 +0000496 if (!E)
497 return false;
498
499 const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E->IgnoreParenCasts());
500 if (!DR)
501 return false;
502
503 const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
504 if (!VD)
505 return false;
506
Tom Carea4603112010-08-24 21:09:07 +0000507 if (AC->getPseudoConstantAnalysis()->wasReferenced(VD))
508 return false;
509
510 return true;
Tom Care826e6b42010-07-16 20:41:41 +0000511}
512
513// Check for self casts truncating/extending a variable
514bool IdempotentOperationChecker::isTruncationExtensionAssignment(
515 const Expr *LHS,
516 const Expr *RHS) {
517
518 const DeclRefExpr *LHS_DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParenCasts());
519 if (!LHS_DR)
520 return false;
521
522 const VarDecl *VD = dyn_cast<VarDecl>(LHS_DR->getDecl());
523 if (!VD)
524 return false;
525
526 const DeclRefExpr *RHS_DR = dyn_cast<DeclRefExpr>(RHS->IgnoreParenCasts());
527 if (!RHS_DR)
528 return false;
529
530 if (VD != RHS_DR->getDecl())
531 return false;
532
John McCall34376a62010-12-04 03:47:34 +0000533 return dyn_cast<DeclRefExpr>(RHS->IgnoreParenLValueCasts()) == NULL;
Tom Care826e6b42010-07-16 20:41:41 +0000534}
535
Tom Caref8a98632010-08-12 22:45:47 +0000536// Returns false if a path to this block was not completely analyzed, or true
537// otherwise.
Ted Kremeneka71d5d32011-02-14 17:59:20 +0000538bool
Ted Kremenek81ce1c82011-10-24 01:32:45 +0000539IdempotentOperationChecker::pathWasCompletelyAnalyzed(AnalysisDeclContext *AC,
Ted Kremeneka71d5d32011-02-14 17:59:20 +0000540 const CFGBlock *CB,
Ted Kremeneka71d5d32011-02-14 17:59:20 +0000541 const CoreEngine &CE) {
Ted Kremenek4ea90042011-02-15 02:20:03 +0000542
Ted Kremenekddc06d02011-03-19 01:00:33 +0000543 CFGReverseBlockReachabilityAnalysis *CRA = AC->getCFGReachablityAnalysis();
Ted Kremeneka71d5d32011-02-14 17:59:20 +0000544
Tom Care68df12f2010-09-09 02:04:52 +0000545 // Test for reachability from any aborted blocks to this block
Ted Kremenek8f89f7c2011-04-02 02:56:23 +0000546 typedef CoreEngine::BlocksExhausted::const_iterator ExhaustedIterator;
547 for (ExhaustedIterator I = CE.blocks_exhausted_begin(),
548 E = CE.blocks_exhausted_end(); I != E; ++I) {
Tom Caref8a98632010-08-12 22:45:47 +0000549 const BlockEdge &BE = I->first;
Tom Care3ff08a82010-07-06 21:43:29 +0000550
Tom Caref8a98632010-08-12 22:45:47 +0000551 // The destination block on the BlockEdge is the first block that was not
Tom Care68df12f2010-09-09 02:04:52 +0000552 // analyzed. If we can reach this block from the aborted block, then this
553 // block was not completely analyzed.
Ted Kremenek5794ef62011-02-14 17:59:23 +0000554 //
555 // Also explicitly check if the current block is the destination block.
556 // While technically reachable, it means we aborted the analysis on
557 // a path that included that block.
558 const CFGBlock *destBlock = BE.getDst();
559 if (destBlock == CB || CRA->isReachable(destBlock, CB))
Tom Caref8a98632010-08-12 22:45:47 +0000560 return false;
Tom Caref8a98632010-08-12 22:45:47 +0000561 }
Ted Kremenek8f89f7c2011-04-02 02:56:23 +0000562
563 // Test for reachability from blocks we just gave up on.
564 typedef CoreEngine::BlocksAborted::const_iterator AbortedIterator;
565 for (AbortedIterator I = CE.blocks_aborted_begin(),
566 E = CE.blocks_aborted_end(); I != E; ++I) {
567 const CFGBlock *destBlock = I->first;
568 if (destBlock == CB || CRA->isReachable(destBlock, CB))
569 return false;
570 }
Ted Kremenekcf9dbe92010-11-13 05:04:52 +0000571
572 // For the items still on the worklist, see if they are in blocks that
573 // can eventually reach 'CB'.
Argyrios Kyrtzidis1696f502010-12-22 18:53:44 +0000574 class VisitWL : public WorkList::Visitor {
Ted Kremenekcf9dbe92010-11-13 05:04:52 +0000575 const CFGStmtMap *CBM;
576 const CFGBlock *TargetBlock;
Ted Kremenekddc06d02011-03-19 01:00:33 +0000577 CFGReverseBlockReachabilityAnalysis &CRA;
Ted Kremenekcf9dbe92010-11-13 05:04:52 +0000578 public:
579 VisitWL(const CFGStmtMap *cbm, const CFGBlock *targetBlock,
Ted Kremenekddc06d02011-03-19 01:00:33 +0000580 CFGReverseBlockReachabilityAnalysis &cra)
Ted Kremenekcf9dbe92010-11-13 05:04:52 +0000581 : CBM(cbm), TargetBlock(targetBlock), CRA(cra) {}
Ted Kremenekf4ef3d32011-01-11 02:34:50 +0000582 virtual bool visit(const WorkListUnit &U) {
Ted Kremenekcf9dbe92010-11-13 05:04:52 +0000583 ProgramPoint P = U.getNode()->getLocation();
584 const CFGBlock *B = 0;
David Blaikie87396b92013-02-21 22:23:56 +0000585 if (Optional<StmtPoint> SP = P.getAs<StmtPoint>()) {
Ted Kremenekcf9dbe92010-11-13 05:04:52 +0000586 B = CBM->getBlock(SP->getStmt());
David Blaikie87396b92013-02-21 22:23:56 +0000587 } else if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
Ted Kremenekf2819192010-11-13 05:12:26 +0000588 B = BE->getDst();
David Blaikie87396b92013-02-21 22:23:56 +0000589 } else if (Optional<BlockEntrance> BEnt = P.getAs<BlockEntrance>()) {
Ted Kremenekf2819192010-11-13 05:12:26 +0000590 B = BEnt->getBlock();
David Blaikie87396b92013-02-21 22:23:56 +0000591 } else if (Optional<BlockExit> BExit = P.getAs<BlockExit>()) {
Ted Kremenekf2819192010-11-13 05:12:26 +0000592 B = BExit->getBlock();
593 }
Ted Kremenekcf9dbe92010-11-13 05:04:52 +0000594 if (!B)
595 return true;
596
Ted Kremenek905a6022011-04-12 21:47:02 +0000597 return B == TargetBlock || CRA.isReachable(B, TargetBlock);
Ted Kremenekcf9dbe92010-11-13 05:04:52 +0000598 }
599 };
Ted Kremenek80861ca2011-02-23 01:51:59 +0000600 VisitWL visitWL(AC->getCFGStmtMap(), CB, *CRA);
Ted Kremenekcf9dbe92010-11-13 05:04:52 +0000601 // Were there any items in the worklist that could potentially reach
602 // this block?
Ted Kremenekf4ef3d32011-01-11 02:34:50 +0000603 if (CE.getWorkList()->visitItemsInWorkList(visitWL))
Ted Kremenekcf9dbe92010-11-13 05:04:52 +0000604 return false;
Tom Caref8a98632010-08-12 22:45:47 +0000605
Tom Care68df12f2010-09-09 02:04:52 +0000606 // Verify that this block is reachable from the entry block
Ted Kremenek80861ca2011-02-23 01:51:59 +0000607 if (!CRA->isReachable(&AC->getCFG()->getEntry(), CB))
Tom Care68df12f2010-09-09 02:04:52 +0000608 return false;
609
Tom Caref8a98632010-08-12 22:45:47 +0000610 // If we get to this point, there is no connection to the entry block or an
611 // aborted block. This path is unreachable and we can report the error.
612 return true;
613}
614
615// Recursive function that determines whether an expression contains any element
616// that varies. This could be due to a compile-time constant like sizeof. An
617// expression may also involve a variable that behaves like a constant. The
618// function returns true if the expression varies, and false otherwise.
Tom Careb9933f32010-08-18 21:17:24 +0000619bool IdempotentOperationChecker::CanVary(const Expr *Ex,
Ted Kremenek81ce1c82011-10-24 01:32:45 +0000620 AnalysisDeclContext *AC) {
Tom Caref8a98632010-08-12 22:45:47 +0000621 // Parentheses and casts are irrelevant here
622 Ex = Ex->IgnoreParenCasts();
623
624 if (Ex->getLocStart().isMacroID())
625 return false;
626
627 switch (Ex->getStmtClass()) {
628 // Trivially true cases
629 case Stmt::ArraySubscriptExprClass:
630 case Stmt::MemberExprClass:
631 case Stmt::StmtExprClass:
632 case Stmt::CallExprClass:
633 case Stmt::VAArgExprClass:
634 case Stmt::ShuffleVectorExprClass:
635 return true;
636 default:
637 return true;
638
639 // Trivially false cases
640 case Stmt::IntegerLiteralClass:
641 case Stmt::CharacterLiteralClass:
642 case Stmt::FloatingLiteralClass:
643 case Stmt::PredefinedExprClass:
644 case Stmt::ImaginaryLiteralClass:
645 case Stmt::StringLiteralClass:
646 case Stmt::OffsetOfExprClass:
647 case Stmt::CompoundLiteralExprClass:
648 case Stmt::AddrLabelExprClass:
Francois Pichet34b21132010-12-08 22:35:30 +0000649 case Stmt::BinaryTypeTraitExprClass:
Tom Caref8a98632010-08-12 22:45:47 +0000650 case Stmt::GNUNullExprClass:
651 case Stmt::InitListExprClass:
652 case Stmt::DesignatedInitExprClass:
653 case Stmt::BlockExprClass:
Tom Caref8a98632010-08-12 22:45:47 +0000654 return false;
655
656 // Cases requiring custom logic
Peter Collingbournee190dee2011-03-11 19:24:49 +0000657 case Stmt::UnaryExprOrTypeTraitExprClass: {
658 const UnaryExprOrTypeTraitExpr *SE =
659 cast<const UnaryExprOrTypeTraitExpr>(Ex);
660 if (SE->getKind() != UETT_SizeOf)
Tom Caref8a98632010-08-12 22:45:47 +0000661 return false;
662 return SE->getTypeOfArgument()->isVariableArrayType();
663 }
664 case Stmt::DeclRefExprClass:
Tom Care9026d4b2010-08-30 19:25:43 +0000665 // Check for constants/pseudoconstants
Tom Careb9933f32010-08-18 21:17:24 +0000666 return !isConstantOrPseudoConstant(cast<DeclRefExpr>(Ex), AC);
Tom Caref8a98632010-08-12 22:45:47 +0000667
668 // The next cases require recursion for subexpressions
669 case Stmt::BinaryOperatorClass: {
670 const BinaryOperator *B = cast<const BinaryOperator>(Ex);
Ted Kremenek310c5a82010-10-29 01:06:54 +0000671
672 // Exclude cases involving pointer arithmetic. These are usually
673 // false positives.
674 if (B->getOpcode() == BO_Sub || B->getOpcode() == BO_Add)
675 if (B->getLHS()->getType()->getAs<PointerType>())
676 return false;
677
Tom Careb9933f32010-08-18 21:17:24 +0000678 return CanVary(B->getRHS(), AC)
679 || CanVary(B->getLHS(), AC);
Tom Caref8a98632010-08-12 22:45:47 +0000680 }
681 case Stmt::UnaryOperatorClass: {
682 const UnaryOperator *U = cast<const UnaryOperator>(Ex);
Eli Friedmana2622dd2010-08-13 01:36:11 +0000683 // Handle trivial case first
Tom Caref8a98632010-08-12 22:45:47 +0000684 switch (U->getOpcode()) {
John McCalle3027922010-08-25 11:45:40 +0000685 case UO_Extension:
Tom Caref8a98632010-08-12 22:45:47 +0000686 return false;
687 default:
Tom Careb9933f32010-08-18 21:17:24 +0000688 return CanVary(U->getSubExpr(), AC);
Tom Caref8a98632010-08-12 22:45:47 +0000689 }
690 }
691 case Stmt::ChooseExprClass:
Tom Careb9933f32010-08-18 21:17:24 +0000692 return CanVary(cast<const ChooseExpr>(Ex)->getChosenSubExpr(
693 AC->getASTContext()), AC);
Tom Caref8a98632010-08-12 22:45:47 +0000694 case Stmt::ConditionalOperatorClass:
John McCallc07a0c72011-02-17 10:25:35 +0000695 case Stmt::BinaryConditionalOperatorClass:
696 return CanVary(cast<AbstractConditionalOperator>(Ex)->getCond(), AC);
Tom Caref8a98632010-08-12 22:45:47 +0000697 }
Tom Care3ff08a82010-07-06 21:43:29 +0000698}
699
Tom Careb9933f32010-08-18 21:17:24 +0000700// Returns true if a DeclRefExpr is or behaves like a constant.
701bool IdempotentOperationChecker::isConstantOrPseudoConstant(
Tom Care9026d4b2010-08-30 19:25:43 +0000702 const DeclRefExpr *DR,
Ted Kremenek81ce1c82011-10-24 01:32:45 +0000703 AnalysisDeclContext *AC) {
Tom Careb9933f32010-08-18 21:17:24 +0000704 // Check if the type of the Decl is const-qualified
705 if (DR->getType().isConstQualified())
706 return true;
707
Tom Carec129cc12010-08-16 21:43:52 +0000708 // Check for an enum
709 if (isa<EnumConstantDecl>(DR->getDecl()))
710 return true;
711
Tom Caree332c3b2010-08-23 19:51:57 +0000712 const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
713 if (!VD)
Tom Careb9933f32010-08-18 21:17:24 +0000714 return true;
715
Tom Caree332c3b2010-08-23 19:51:57 +0000716 // Check if the Decl behaves like a constant. This check also takes care of
717 // static variables, which can only change between function calls if they are
718 // modified in the AST.
719 PseudoConstantAnalysis *PCA = AC->getPseudoConstantAnalysis();
720 if (PCA->isPseudoConstant(VD))
721 return true;
722
723 return false;
724}
725
726// Recursively find any substatements containing VarDecl's with storage other
727// than local
728bool IdempotentOperationChecker::containsNonLocalVarDecl(const Stmt *S) {
729 const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(S);
730
731 if (DR)
732 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
733 if (!VD->hasLocalStorage())
734 return true;
735
736 for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end();
737 ++I)
738 if (const Stmt *child = *I)
739 if (containsNonLocalVarDecl(child))
740 return true;
741
Tom Carec129cc12010-08-16 21:43:52 +0000742 return false;
743}
Tom Care68df12f2010-09-09 02:04:52 +0000744
Tom Care68df12f2010-09-09 02:04:52 +0000745
Argyrios Kyrtzidis66b38c22011-02-23 21:04:44 +0000746void ento::registerIdempotentOperationChecker(CheckerManager &mgr) {
747 mgr.registerChecker<IdempotentOperationChecker>();
748}