• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //==- 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 //
39 // Things TODO:
40 // - Improved error messages
41 // - Handle mixed assumptions (which assumptions can belong together?)
42 // - Finer grained false positive control (levels)
43 // - Handling ~0 values
44 
45 #include "ClangSACheckers.h"
46 #include "clang/Analysis/CFGStmtMap.h"
47 #include "clang/Analysis/Analyses/PseudoConstantAnalysis.h"
48 #include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
49 #include "clang/StaticAnalyzer/Core/Checker.h"
50 #include "clang/StaticAnalyzer/Core/CheckerManager.h"
51 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
52 #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h"
53 #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h"
54 #include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
55 #include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
56 #include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
57 #include "clang/AST/Stmt.h"
58 #include "llvm/ADT/DenseMap.h"
59 #include "llvm/ADT/SmallSet.h"
60 #include "llvm/ADT/BitVector.h"
61 #include "llvm/Support/ErrorHandling.h"
62 
63 using namespace clang;
64 using namespace ento;
65 
66 namespace {
67 class IdempotentOperationChecker
68   : public Checker<check::PreStmt<BinaryOperator>,
69                      check::PostStmt<BinaryOperator>,
70                      check::EndAnalysis> {
71 public:
72   void checkPreStmt(const BinaryOperator *B, CheckerContext &C) const;
73   void checkPostStmt(const BinaryOperator *B, CheckerContext &C) const;
74   void checkEndAnalysis(ExplodedGraph &G, BugReporter &B,ExprEngine &Eng) const;
75 
76 private:
77   // Our assumption about a particular operation.
78   enum Assumption { Possible = 0, Impossible, Equal, LHSis1, RHSis1, LHSis0,
79       RHSis0 };
80 
81   static void UpdateAssumption(Assumption &A, const Assumption &New);
82 
83   // False positive reduction methods
84   static bool isSelfAssign(const Expr *LHS, const Expr *RHS);
85   static bool isUnused(const Expr *E, AnalysisContext *AC);
86   static bool isTruncationExtensionAssignment(const Expr *LHS,
87                                               const Expr *RHS);
88   static bool pathWasCompletelyAnalyzed(AnalysisContext *AC,
89                                         const CFGBlock *CB,
90                                         const CoreEngine &CE);
91   static bool CanVary(const Expr *Ex,
92                       AnalysisContext *AC);
93   static bool isConstantOrPseudoConstant(const DeclRefExpr *DR,
94                                          AnalysisContext *AC);
95   static bool containsNonLocalVarDecl(const Stmt *S);
96 
97   // Hash table and related data structures
98   struct BinaryOperatorData {
BinaryOperatorData__anon98cbdff20111::IdempotentOperationChecker::BinaryOperatorData99     BinaryOperatorData() : assumption(Possible), analysisContext(0) {}
100 
101     Assumption assumption;
102     AnalysisContext *analysisContext;
103     ExplodedNodeSet explodedNodes; // Set of ExplodedNodes that refer to a
104                                    // BinaryOperator
105   };
106   typedef llvm::DenseMap<const BinaryOperator *, BinaryOperatorData>
107       AssumptionMap;
108   mutable AssumptionMap hash;
109 };
110 }
111 
checkPreStmt(const BinaryOperator * B,CheckerContext & C) const112 void IdempotentOperationChecker::checkPreStmt(const BinaryOperator *B,
113                                               CheckerContext &C) const {
114   // Find or create an entry in the hash for this BinaryOperator instance.
115   // If we haven't done a lookup before, it will get default initialized to
116   // 'Possible'. At this stage we do not store the ExplodedNode, as it has not
117   // been created yet.
118   BinaryOperatorData &Data = hash[B];
119   Assumption &A = Data.assumption;
120   AnalysisContext *AC = C.getCurrentAnalysisContext();
121   Data.analysisContext = AC;
122 
123   // If we already have visited this node on a path that does not contain an
124   // idempotent operation, return immediately.
125   if (A == Impossible)
126     return;
127 
128   // Retrieve both sides of the operator and determine if they can vary (which
129   // may mean this is a false positive.
130   const Expr *LHS = B->getLHS();
131   const Expr *RHS = B->getRHS();
132 
133   // At this stage we can calculate whether each side contains a false positive
134   // that applies to all operators. We only need to calculate this the first
135   // time.
136   bool LHSContainsFalsePositive = false, RHSContainsFalsePositive = false;
137   if (A == Possible) {
138     // An expression contains a false positive if it can't vary, or if it
139     // contains a known false positive VarDecl.
140     LHSContainsFalsePositive = !CanVary(LHS, AC)
141         || containsNonLocalVarDecl(LHS);
142     RHSContainsFalsePositive = !CanVary(RHS, AC)
143         || containsNonLocalVarDecl(RHS);
144   }
145 
146   const GRState *state = C.getState();
147 
148   SVal LHSVal = state->getSVal(LHS);
149   SVal RHSVal = state->getSVal(RHS);
150 
151   // If either value is unknown, we can't be 100% sure of all paths.
152   if (LHSVal.isUnknownOrUndef() || RHSVal.isUnknownOrUndef()) {
153     A = Impossible;
154     return;
155   }
156   BinaryOperator::Opcode Op = B->getOpcode();
157 
158   // Dereference the LHS SVal if this is an assign operation
159   switch (Op) {
160   default:
161     break;
162 
163   // Fall through intentional
164   case BO_AddAssign:
165   case BO_SubAssign:
166   case BO_MulAssign:
167   case BO_DivAssign:
168   case BO_AndAssign:
169   case BO_OrAssign:
170   case BO_XorAssign:
171   case BO_ShlAssign:
172   case BO_ShrAssign:
173   case BO_Assign:
174   // Assign statements have one extra level of indirection
175     if (!isa<Loc>(LHSVal)) {
176       A = Impossible;
177       return;
178     }
179     LHSVal = state->getSVal(cast<Loc>(LHSVal), LHS->getType());
180   }
181 
182 
183   // We now check for various cases which result in an idempotent operation.
184 
185   // x op x
186   switch (Op) {
187   default:
188     break; // We don't care about any other operators.
189 
190   // Fall through intentional
191   case BO_Assign:
192     // x Assign x can be used to silence unused variable warnings intentionally.
193     // If this is a self assignment and the variable is referenced elsewhere,
194     // and the assignment is not a truncation or extension, then it is a false
195     // positive.
196     if (isSelfAssign(LHS, RHS)) {
197       if (!isUnused(LHS, AC) && !isTruncationExtensionAssignment(LHS, RHS)) {
198         UpdateAssumption(A, Equal);
199         return;
200       }
201       else {
202         A = Impossible;
203         return;
204       }
205     }
206 
207   case BO_SubAssign:
208   case BO_DivAssign:
209   case BO_AndAssign:
210   case BO_OrAssign:
211   case BO_XorAssign:
212   case BO_Sub:
213   case BO_Div:
214   case BO_And:
215   case BO_Or:
216   case BO_Xor:
217   case BO_LOr:
218   case BO_LAnd:
219   case BO_EQ:
220   case BO_NE:
221     if (LHSVal != RHSVal || LHSContainsFalsePositive
222         || RHSContainsFalsePositive)
223       break;
224     UpdateAssumption(A, Equal);
225     return;
226   }
227 
228   // x op 1
229   switch (Op) {
230    default:
231      break; // We don't care about any other operators.
232 
233    // Fall through intentional
234    case BO_MulAssign:
235    case BO_DivAssign:
236    case BO_Mul:
237    case BO_Div:
238    case BO_LOr:
239    case BO_LAnd:
240      if (!RHSVal.isConstant(1) || RHSContainsFalsePositive)
241        break;
242      UpdateAssumption(A, RHSis1);
243      return;
244   }
245 
246   // 1 op x
247   switch (Op) {
248   default:
249     break; // We don't care about any other operators.
250 
251   // Fall through intentional
252   case BO_MulAssign:
253   case BO_Mul:
254   case BO_LOr:
255   case BO_LAnd:
256     if (!LHSVal.isConstant(1) || LHSContainsFalsePositive)
257       break;
258     UpdateAssumption(A, LHSis1);
259     return;
260   }
261 
262   // x op 0
263   switch (Op) {
264   default:
265     break; // We don't care about any other operators.
266 
267   // Fall through intentional
268   case BO_AddAssign:
269   case BO_SubAssign:
270   case BO_MulAssign:
271   case BO_AndAssign:
272   case BO_OrAssign:
273   case BO_XorAssign:
274   case BO_Add:
275   case BO_Sub:
276   case BO_Mul:
277   case BO_And:
278   case BO_Or:
279   case BO_Xor:
280   case BO_Shl:
281   case BO_Shr:
282   case BO_LOr:
283   case BO_LAnd:
284     if (!RHSVal.isConstant(0) || RHSContainsFalsePositive)
285       break;
286     UpdateAssumption(A, RHSis0);
287     return;
288   }
289 
290   // 0 op x
291   switch (Op) {
292   default:
293     break; // We don't care about any other operators.
294 
295   // Fall through intentional
296   //case BO_AddAssign: // Common false positive
297   case BO_SubAssign: // Check only if unsigned
298   case BO_MulAssign:
299   case BO_DivAssign:
300   case BO_AndAssign:
301   //case BO_OrAssign: // Common false positive
302   //case BO_XorAssign: // Common false positive
303   case BO_ShlAssign:
304   case BO_ShrAssign:
305   case BO_Add:
306   case BO_Sub:
307   case BO_Mul:
308   case BO_Div:
309   case BO_And:
310   case BO_Or:
311   case BO_Xor:
312   case BO_Shl:
313   case BO_Shr:
314   case BO_LOr:
315   case BO_LAnd:
316     if (!LHSVal.isConstant(0) || LHSContainsFalsePositive)
317       break;
318     UpdateAssumption(A, LHSis0);
319     return;
320   }
321 
322   // If we get to this point, there has been a valid use of this operation.
323   A = Impossible;
324 }
325 
326 // At the post visit stage, the predecessor ExplodedNode will be the
327 // BinaryOperator that was just created. We use this hook to collect the
328 // ExplodedNode.
checkPostStmt(const BinaryOperator * B,CheckerContext & C) const329 void IdempotentOperationChecker::checkPostStmt(const BinaryOperator *B,
330                                                CheckerContext &C) const {
331   // Add the ExplodedNode we just visited
332   BinaryOperatorData &Data = hash[B];
333 
334   const Stmt *predStmt
335     = cast<StmtPoint>(C.getPredecessor()->getLocation()).getStmt();
336 
337   // Ignore implicit calls to setters.
338   if (!isa<BinaryOperator>(predStmt))
339     return;
340 
341   Data.explodedNodes.Add(C.getPredecessor());
342 }
343 
checkEndAnalysis(ExplodedGraph & G,BugReporter & BR,ExprEngine & Eng) const344 void IdempotentOperationChecker::checkEndAnalysis(ExplodedGraph &G,
345                                                   BugReporter &BR,
346                                                   ExprEngine &Eng) const {
347   BugType *BT = new BugType("Idempotent operation", "Dead code");
348   // Iterate over the hash to see if we have any paths with definite
349   // idempotent operations.
350   for (AssumptionMap::const_iterator i = hash.begin(); i != hash.end(); ++i) {
351     // Unpack the hash contents
352     const BinaryOperatorData &Data = i->second;
353     const Assumption &A = Data.assumption;
354     AnalysisContext *AC = Data.analysisContext;
355     const ExplodedNodeSet &ES = Data.explodedNodes;
356 
357     const BinaryOperator *B = i->first;
358 
359     if (A == Impossible)
360       continue;
361 
362     // If the analyzer did not finish, check to see if we can still emit this
363     // warning
364     if (Eng.hasWorkRemaining()) {
365       // If we can trace back
366       if (!pathWasCompletelyAnalyzed(AC,
367                                      AC->getCFGStmtMap()->getBlock(B),
368                                      Eng.getCoreEngine()))
369         continue;
370     }
371 
372     // Select the error message and SourceRanges to report.
373     llvm::SmallString<128> buf;
374     llvm::raw_svector_ostream os(buf);
375     bool LHSRelevant = false, RHSRelevant = false;
376     switch (A) {
377     case Equal:
378       LHSRelevant = true;
379       RHSRelevant = true;
380       if (B->getOpcode() == BO_Assign)
381         os << "Assigned value is always the same as the existing value";
382       else
383         os << "Both operands to '" << B->getOpcodeStr()
384            << "' always have the same value";
385       break;
386     case LHSis1:
387       LHSRelevant = true;
388       os << "The left operand to '" << B->getOpcodeStr() << "' is always 1";
389       break;
390     case RHSis1:
391       RHSRelevant = true;
392       os << "The right operand to '" << B->getOpcodeStr() << "' is always 1";
393       break;
394     case LHSis0:
395       LHSRelevant = true;
396       os << "The left operand to '" << B->getOpcodeStr() << "' is always 0";
397       break;
398     case RHSis0:
399       RHSRelevant = true;
400       os << "The right operand to '" << B->getOpcodeStr() << "' is always 0";
401       break;
402     case Possible:
403       llvm_unreachable("Operation was never marked with an assumption");
404     case Impossible:
405       llvm_unreachable(0);
406     }
407 
408     // Add a report for each ExplodedNode
409     for (ExplodedNodeSet::iterator I = ES.begin(), E = ES.end(); I != E; ++I) {
410       EnhancedBugReport *report = new EnhancedBugReport(*BT, os.str(), *I);
411 
412       // Add source ranges and visitor hooks
413       if (LHSRelevant) {
414         const Expr *LHS = i->first->getLHS();
415         report->addRange(LHS->getSourceRange());
416         report->addVisitorCreator(bugreporter::registerVarDeclsLastStore, LHS);
417       }
418       if (RHSRelevant) {
419         const Expr *RHS = i->first->getRHS();
420         report->addRange(i->first->getRHS()->getSourceRange());
421         report->addVisitorCreator(bugreporter::registerVarDeclsLastStore, RHS);
422       }
423 
424       BR.EmitReport(report);
425     }
426   }
427 
428   hash.clear();
429 }
430 
431 // Updates the current assumption given the new assumption
UpdateAssumption(Assumption & A,const Assumption & New)432 inline void IdempotentOperationChecker::UpdateAssumption(Assumption &A,
433                                                         const Assumption &New) {
434 // If the assumption is the same, there is nothing to do
435   if (A == New)
436     return;
437 
438   switch (A) {
439   // If we don't currently have an assumption, set it
440   case Possible:
441     A = New;
442     return;
443 
444   // If we have determined that a valid state happened, ignore the new
445   // assumption.
446   case Impossible:
447     return;
448 
449   // Any other case means that we had a different assumption last time. We don't
450   // currently support mixing assumptions for diagnostic reasons, so we set
451   // our assumption to be impossible.
452   default:
453     A = Impossible;
454     return;
455   }
456 }
457 
458 // Check for a statement where a variable is self assigned to possibly avoid an
459 // unused variable warning.
isSelfAssign(const Expr * LHS,const Expr * RHS)460 bool IdempotentOperationChecker::isSelfAssign(const Expr *LHS, const Expr *RHS) {
461   LHS = LHS->IgnoreParenCasts();
462   RHS = RHS->IgnoreParenCasts();
463 
464   const DeclRefExpr *LHS_DR = dyn_cast<DeclRefExpr>(LHS);
465   if (!LHS_DR)
466     return false;
467 
468   const VarDecl *VD = dyn_cast<VarDecl>(LHS_DR->getDecl());
469   if (!VD)
470     return false;
471 
472   const DeclRefExpr *RHS_DR = dyn_cast<DeclRefExpr>(RHS);
473   if (!RHS_DR)
474     return false;
475 
476   if (VD != RHS_DR->getDecl())
477     return false;
478 
479   return true;
480 }
481 
482 // Returns true if the Expr points to a VarDecl that is not read anywhere
483 // outside of self-assignments.
isUnused(const Expr * E,AnalysisContext * AC)484 bool IdempotentOperationChecker::isUnused(const Expr *E,
485                                           AnalysisContext *AC) {
486   if (!E)
487     return false;
488 
489   const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E->IgnoreParenCasts());
490   if (!DR)
491     return false;
492 
493   const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
494   if (!VD)
495     return false;
496 
497   if (AC->getPseudoConstantAnalysis()->wasReferenced(VD))
498     return false;
499 
500   return true;
501 }
502 
503 // Check for self casts truncating/extending a variable
isTruncationExtensionAssignment(const Expr * LHS,const Expr * RHS)504 bool IdempotentOperationChecker::isTruncationExtensionAssignment(
505                                                               const Expr *LHS,
506                                                               const Expr *RHS) {
507 
508   const DeclRefExpr *LHS_DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParenCasts());
509   if (!LHS_DR)
510     return false;
511 
512   const VarDecl *VD = dyn_cast<VarDecl>(LHS_DR->getDecl());
513   if (!VD)
514     return false;
515 
516   const DeclRefExpr *RHS_DR = dyn_cast<DeclRefExpr>(RHS->IgnoreParenCasts());
517   if (!RHS_DR)
518     return false;
519 
520   if (VD != RHS_DR->getDecl())
521      return false;
522 
523   return dyn_cast<DeclRefExpr>(RHS->IgnoreParenLValueCasts()) == NULL;
524 }
525 
526 // Returns false if a path to this block was not completely analyzed, or true
527 // otherwise.
528 bool
pathWasCompletelyAnalyzed(AnalysisContext * AC,const CFGBlock * CB,const CoreEngine & CE)529 IdempotentOperationChecker::pathWasCompletelyAnalyzed(AnalysisContext *AC,
530                                                       const CFGBlock *CB,
531                                                       const CoreEngine &CE) {
532 
533   CFGReverseBlockReachabilityAnalysis *CRA = AC->getCFGReachablityAnalysis();
534 
535   // Test for reachability from any aborted blocks to this block
536   typedef CoreEngine::BlocksExhausted::const_iterator ExhaustedIterator;
537   for (ExhaustedIterator I = CE.blocks_exhausted_begin(),
538       E = CE.blocks_exhausted_end(); I != E; ++I) {
539     const BlockEdge &BE =  I->first;
540 
541     // The destination block on the BlockEdge is the first block that was not
542     // analyzed. If we can reach this block from the aborted block, then this
543     // block was not completely analyzed.
544     //
545     // Also explicitly check if the current block is the destination block.
546     // While technically reachable, it means we aborted the analysis on
547     // a path that included that block.
548     const CFGBlock *destBlock = BE.getDst();
549     if (destBlock == CB || CRA->isReachable(destBlock, CB))
550       return false;
551   }
552 
553   // Test for reachability from blocks we just gave up on.
554   typedef CoreEngine::BlocksAborted::const_iterator AbortedIterator;
555   for (AbortedIterator I = CE.blocks_aborted_begin(),
556        E = CE.blocks_aborted_end(); I != E; ++I) {
557     const CFGBlock *destBlock = I->first;
558     if (destBlock == CB || CRA->isReachable(destBlock, CB))
559       return false;
560   }
561 
562   // For the items still on the worklist, see if they are in blocks that
563   // can eventually reach 'CB'.
564   class VisitWL : public WorkList::Visitor {
565     const CFGStmtMap *CBM;
566     const CFGBlock *TargetBlock;
567     CFGReverseBlockReachabilityAnalysis &CRA;
568   public:
569     VisitWL(const CFGStmtMap *cbm, const CFGBlock *targetBlock,
570             CFGReverseBlockReachabilityAnalysis &cra)
571       : CBM(cbm), TargetBlock(targetBlock), CRA(cra) {}
572     virtual bool visit(const WorkListUnit &U) {
573       ProgramPoint P = U.getNode()->getLocation();
574       const CFGBlock *B = 0;
575       if (StmtPoint *SP = dyn_cast<StmtPoint>(&P)) {
576         B = CBM->getBlock(SP->getStmt());
577       }
578       else if (BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
579         B = BE->getDst();
580       }
581       else if (BlockEntrance *BEnt = dyn_cast<BlockEntrance>(&P)) {
582         B = BEnt->getBlock();
583       }
584       else if (BlockExit *BExit = dyn_cast<BlockExit>(&P)) {
585         B = BExit->getBlock();
586       }
587       if (!B)
588         return true;
589 
590       return B == TargetBlock || CRA.isReachable(B, TargetBlock);
591     }
592   };
593   VisitWL visitWL(AC->getCFGStmtMap(), CB, *CRA);
594   // Were there any items in the worklist that could potentially reach
595   // this block?
596   if (CE.getWorkList()->visitItemsInWorkList(visitWL))
597     return false;
598 
599   // Verify that this block is reachable from the entry block
600   if (!CRA->isReachable(&AC->getCFG()->getEntry(), CB))
601     return false;
602 
603   // If we get to this point, there is no connection to the entry block or an
604   // aborted block. This path is unreachable and we can report the error.
605   return true;
606 }
607 
608 // Recursive function that determines whether an expression contains any element
609 // that varies. This could be due to a compile-time constant like sizeof. An
610 // expression may also involve a variable that behaves like a constant. The
611 // function returns true if the expression varies, and false otherwise.
CanVary(const Expr * Ex,AnalysisContext * AC)612 bool IdempotentOperationChecker::CanVary(const Expr *Ex,
613                                          AnalysisContext *AC) {
614   // Parentheses and casts are irrelevant here
615   Ex = Ex->IgnoreParenCasts();
616 
617   if (Ex->getLocStart().isMacroID())
618     return false;
619 
620   switch (Ex->getStmtClass()) {
621   // Trivially true cases
622   case Stmt::ArraySubscriptExprClass:
623   case Stmt::MemberExprClass:
624   case Stmt::StmtExprClass:
625   case Stmt::CallExprClass:
626   case Stmt::VAArgExprClass:
627   case Stmt::ShuffleVectorExprClass:
628     return true;
629   default:
630     return true;
631 
632   // Trivially false cases
633   case Stmt::IntegerLiteralClass:
634   case Stmt::CharacterLiteralClass:
635   case Stmt::FloatingLiteralClass:
636   case Stmt::PredefinedExprClass:
637   case Stmt::ImaginaryLiteralClass:
638   case Stmt::StringLiteralClass:
639   case Stmt::OffsetOfExprClass:
640   case Stmt::CompoundLiteralExprClass:
641   case Stmt::AddrLabelExprClass:
642   case Stmt::BinaryTypeTraitExprClass:
643   case Stmt::GNUNullExprClass:
644   case Stmt::InitListExprClass:
645   case Stmt::DesignatedInitExprClass:
646   case Stmt::BlockExprClass:
647   case Stmt::BlockDeclRefExprClass:
648     return false;
649 
650   // Cases requiring custom logic
651   case Stmt::UnaryExprOrTypeTraitExprClass: {
652     const UnaryExprOrTypeTraitExpr *SE =
653                        cast<const UnaryExprOrTypeTraitExpr>(Ex);
654     if (SE->getKind() != UETT_SizeOf)
655       return false;
656     return SE->getTypeOfArgument()->isVariableArrayType();
657   }
658   case Stmt::DeclRefExprClass:
659     // Check for constants/pseudoconstants
660     return !isConstantOrPseudoConstant(cast<DeclRefExpr>(Ex), AC);
661 
662   // The next cases require recursion for subexpressions
663   case Stmt::BinaryOperatorClass: {
664     const BinaryOperator *B = cast<const BinaryOperator>(Ex);
665 
666     // Exclude cases involving pointer arithmetic.  These are usually
667     // false positives.
668     if (B->getOpcode() == BO_Sub || B->getOpcode() == BO_Add)
669       if (B->getLHS()->getType()->getAs<PointerType>())
670         return false;
671 
672     return CanVary(B->getRHS(), AC)
673         || CanVary(B->getLHS(), AC);
674    }
675   case Stmt::UnaryOperatorClass: {
676     const UnaryOperator *U = cast<const UnaryOperator>(Ex);
677     // Handle trivial case first
678     switch (U->getOpcode()) {
679     case UO_Extension:
680       return false;
681     default:
682       return CanVary(U->getSubExpr(), AC);
683     }
684   }
685   case Stmt::ChooseExprClass:
686     return CanVary(cast<const ChooseExpr>(Ex)->getChosenSubExpr(
687         AC->getASTContext()), AC);
688   case Stmt::ConditionalOperatorClass:
689   case Stmt::BinaryConditionalOperatorClass:
690     return CanVary(cast<AbstractConditionalOperator>(Ex)->getCond(), AC);
691   }
692 }
693 
694 // Returns true if a DeclRefExpr is or behaves like a constant.
isConstantOrPseudoConstant(const DeclRefExpr * DR,AnalysisContext * AC)695 bool IdempotentOperationChecker::isConstantOrPseudoConstant(
696                                                           const DeclRefExpr *DR,
697                                                           AnalysisContext *AC) {
698   // Check if the type of the Decl is const-qualified
699   if (DR->getType().isConstQualified())
700     return true;
701 
702   // Check for an enum
703   if (isa<EnumConstantDecl>(DR->getDecl()))
704     return true;
705 
706   const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
707   if (!VD)
708     return true;
709 
710   // Check if the Decl behaves like a constant. This check also takes care of
711   // static variables, which can only change between function calls if they are
712   // modified in the AST.
713   PseudoConstantAnalysis *PCA = AC->getPseudoConstantAnalysis();
714   if (PCA->isPseudoConstant(VD))
715     return true;
716 
717   return false;
718 }
719 
720 // Recursively find any substatements containing VarDecl's with storage other
721 // than local
containsNonLocalVarDecl(const Stmt * S)722 bool IdempotentOperationChecker::containsNonLocalVarDecl(const Stmt *S) {
723   const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(S);
724 
725   if (DR)
726     if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
727       if (!VD->hasLocalStorage())
728         return true;
729 
730   for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end();
731       ++I)
732     if (const Stmt *child = *I)
733       if (containsNonLocalVarDecl(child))
734         return true;
735 
736   return false;
737 }
738 
739 
registerIdempotentOperationChecker(CheckerManager & mgr)740 void ento::registerIdempotentOperationChecker(CheckerManager &mgr) {
741   mgr.registerChecker<IdempotentOperationChecker>();
742 }
743