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/AST/Stmt.h"
47#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h"
48#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"
52#include "clang/StaticAnalyzer/Core/Checker.h"
53#include "clang/StaticAnalyzer/Core/CheckerManager.h"
54#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h"
55#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h"
56#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h"
57#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h"
58#include "llvm/ADT/BitVector.h"
59#include "llvm/ADT/DenseMap.h"
60#include "llvm/ADT/SmallSet.h"
61#include "llvm/ADT/SmallString.h"
62#include "llvm/Support/ErrorHandling.h"
63#include "llvm/Support/raw_ostream.h"
64
65using namespace clang;
66using namespace ento;
67
68namespace {
69class IdempotentOperationChecker
70  : public Checker<check::PreStmt<BinaryOperator>,
71                     check::PostStmt<BinaryOperator>,
72                     check::EndAnalysis> {
73public:
74  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;
77
78private:
79  // Our assumption about a particular operation.
80  enum Assumption { Possible = 0, Impossible, Equal, LHSis1, RHSis1, LHSis0,
81      RHSis0 };
82
83  static void UpdateAssumption(Assumption &A, const Assumption &New);
84
85  // False positive reduction methods
86  static bool isSelfAssign(const Expr *LHS, const Expr *RHS);
87  static bool isUnused(const Expr *E, AnalysisDeclContext *AC);
88  static bool isTruncationExtensionAssignment(const Expr *LHS,
89                                              const Expr *RHS);
90  static bool pathWasCompletelyAnalyzed(AnalysisDeclContext *AC,
91                                        const CFGBlock *CB,
92                                        const CoreEngine &CE);
93  static bool CanVary(const Expr *Ex,
94                      AnalysisDeclContext *AC);
95  static bool isConstantOrPseudoConstant(const DeclRefExpr *DR,
96                                         AnalysisDeclContext *AC);
97  static bool containsNonLocalVarDecl(const Stmt *S);
98
99  // Hash table and related data structures
100  struct BinaryOperatorData {
101    BinaryOperatorData() : assumption(Possible) {}
102
103    Assumption assumption;
104    ExplodedNodeSet explodedNodes; // Set of ExplodedNodes that refer to a
105                                   // BinaryOperator
106  };
107  typedef llvm::DenseMap<const BinaryOperator *, BinaryOperatorData>
108      AssumptionMap;
109  mutable AssumptionMap hash;
110  mutable OwningPtr<BugType> BT;
111};
112}
113
114void IdempotentOperationChecker::checkPreStmt(const BinaryOperator *B,
115                                              CheckerContext &C) const {
116  // 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
118  // '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;
122  AnalysisDeclContext *AC = C.getCurrentAnalysisDeclContext();
123
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
129  // Retrieve both sides of the operator and determine if they can vary (which
130  // may mean this is a false positive.
131  const Expr *LHS = B->getLHS();
132  const Expr *RHS = B->getRHS();
133
134  // 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;
138  if (A == Possible) {
139    // 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);
145  }
146
147  ProgramStateRef state = C.getState();
148  const LocationContext *LCtx = C.getLocationContext();
149  SVal LHSVal = state->getSVal(LHS, LCtx);
150  SVal RHSVal = state->getSVal(RHS, LCtx);
151
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
165  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:
175  // Assign statements have one extra level of indirection
176    if (!LHSVal.getAs<Loc>()) {
177      A = Impossible;
178      return;
179    }
180    LHSVal = state->getSVal(LHSVal.castAs<Loc>(), LHS->getType());
181  }
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
192  case BO_Assign:
193    // 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,
195    // and the assignment is not a truncation or extension, then it is a false
196    // positive.
197    if (isSelfAssign(LHS, RHS)) {
198      if (!isUnused(LHS, AC) && !isTruncationExtensionAssignment(LHS, RHS)) {
199        UpdateAssumption(A, Equal);
200        return;
201      }
202      else {
203        A = Impossible;
204        return;
205      }
206    }
207
208  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:
220  case BO_EQ:
221  case BO_NE:
222    if (LHSVal != RHSVal || LHSContainsFalsePositive
223        || RHSContainsFalsePositive)
224      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
235   case BO_MulAssign:
236   case BO_DivAssign:
237   case BO_Mul:
238   case BO_Div:
239   case BO_LOr:
240   case BO_LAnd:
241     if (!RHSVal.isConstant(1) || RHSContainsFalsePositive)
242       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
253  case BO_MulAssign:
254  case BO_Mul:
255  case BO_LOr:
256  case BO_LAnd:
257    if (!LHSVal.isConstant(1) || LHSContainsFalsePositive)
258      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
269  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:
285    if (!RHSVal.isConstant(0) || RHSContainsFalsePositive)
286      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
297  //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:
317    if (!LHSVal.isConstant(0) || LHSContainsFalsePositive)
318      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
327// 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.
330void IdempotentOperationChecker::checkPostStmt(const BinaryOperator *B,
331                                               CheckerContext &C) const {
332  // Add the ExplodedNode we just visited
333  BinaryOperatorData &Data = hash[B];
334
335  const Stmt *predStmt =
336      C.getPredecessor()->getLocation().castAs<StmtPoint>().getStmt();
337
338  // Ignore implicit calls to setters.
339  if (!isa<BinaryOperator>(predStmt))
340    return;
341
342  Data.explodedNodes.Add(C.getPredecessor());
343}
344
345void IdempotentOperationChecker::checkEndAnalysis(ExplodedGraph &G,
346                                                  BugReporter &BR,
347                                                  ExprEngine &Eng) const {
348  if (!BT)
349    BT.reset(new BugType("Idempotent operation", "Dead code"));
350
351  // Iterate over the hash to see if we have any paths with definite
352  // idempotent operations.
353  for (AssumptionMap::const_iterator i = hash.begin(); i != hash.end(); ++i) {
354    // Unpack the hash contents
355    const BinaryOperatorData &Data = i->second;
356    const Assumption &A = Data.assumption;
357    const ExplodedNodeSet &ES = Data.explodedNodes;
358
359    // 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
365    const BinaryOperator *B = i->first;
366
367    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()) {
373      // If we can trace back
374      AnalysisDeclContext *AC = (*ES.begin())->getLocationContext()
375                                         ->getAnalysisDeclContext();
376      if (!pathWasCompletelyAnalyzed(AC,
377                                     AC->getCFGStmtMap()->getBlock(B),
378                                     Eng.getCoreEngine()))
379        continue;
380    }
381
382    // Select the error message and SourceRanges to report.
383    SmallString<128> buf;
384    llvm::raw_svector_ostream os(buf);
385    bool LHSRelevant = false, RHSRelevant = false;
386    switch (A) {
387    case Equal:
388      LHSRelevant = true;
389      RHSRelevant = true;
390      if (B->getOpcode() == BO_Assign)
391        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:
397      LHSRelevant = true;
398      os << "The left operand to '" << B->getOpcodeStr() << "' is always 1";
399      break;
400    case RHSis1:
401      RHSRelevant = true;
402      os << "The right operand to '" << B->getOpcodeStr() << "' is always 1";
403      break;
404    case LHSis0:
405      LHSRelevant = true;
406      os << "The left operand to '" << B->getOpcodeStr() << "' is always 0";
407      break;
408    case RHSis0:
409      RHSRelevant = true;
410      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
418    // Add a report for each ExplodedNode
419    for (ExplodedNodeSet::iterator I = ES.begin(), E = ES.end(); I != E; ++I) {
420      BugReport *report = new BugReport(*BT, os.str(), *I);
421
422      // Add source ranges and visitor hooks
423      if (LHSRelevant) {
424        const Expr *LHS = i->first->getLHS();
425        report->addRange(LHS->getSourceRange());
426        FindLastStoreBRVisitor::registerStatementVarDecls(*report, LHS, false);
427      }
428      if (RHSRelevant) {
429        const Expr *RHS = i->first->getRHS();
430        report->addRange(i->first->getRHS()->getSourceRange());
431        FindLastStoreBRVisitor::registerStatementVarDecls(*report, RHS, false);
432      }
433
434      BR.emitReport(report);
435    }
436  }
437
438  hash.clear();
439}
440
441// Updates the current assumption given the new assumption
442inline void IdempotentOperationChecker::UpdateAssumption(Assumption &A,
443                                                        const Assumption &New) {
444// If the assumption is the same, there is nothing to do
445  if (A == New)
446    return;
447
448  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
468// 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) {
471  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
478  const VarDecl *VD = dyn_cast<VarDecl>(LHS_DR->getDecl());
479  if (!VD)
480    return false;
481
482  const DeclRefExpr *RHS_DR = dyn_cast<DeclRefExpr>(RHS);
483  if (!RHS_DR)
484    return false;
485
486  if (VD != RHS_DR->getDecl())
487    return false;
488
489  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,
495                                          AnalysisDeclContext *AC) {
496  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
507  if (AC->getPseudoConstantAnalysis()->wasReferenced(VD))
508    return false;
509
510  return true;
511}
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
533  return dyn_cast<DeclRefExpr>(RHS->IgnoreParenLValueCasts()) == NULL;
534}
535
536// Returns false if a path to this block was not completely analyzed, or true
537// otherwise.
538bool
539IdempotentOperationChecker::pathWasCompletelyAnalyzed(AnalysisDeclContext *AC,
540                                                      const CFGBlock *CB,
541                                                      const CoreEngine &CE) {
542
543  CFGReverseBlockReachabilityAnalysis *CRA = AC->getCFGReachablityAnalysis();
544
545  // Test for reachability from any aborted blocks to this block
546  typedef CoreEngine::BlocksExhausted::const_iterator ExhaustedIterator;
547  for (ExhaustedIterator I = CE.blocks_exhausted_begin(),
548      E = CE.blocks_exhausted_end(); I != E; ++I) {
549    const BlockEdge &BE =  I->first;
550
551    // The destination block on the BlockEdge is the first block that was not
552    // analyzed. If we can reach this block from the aborted block, then this
553    // block was not completely analyzed.
554    //
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))
560      return false;
561  }
562
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  }
571
572  // For the items still on the worklist, see if they are in blocks that
573  // can eventually reach 'CB'.
574  class VisitWL : public WorkList::Visitor {
575    const CFGStmtMap *CBM;
576    const CFGBlock *TargetBlock;
577    CFGReverseBlockReachabilityAnalysis &CRA;
578  public:
579    VisitWL(const CFGStmtMap *cbm, const CFGBlock *targetBlock,
580            CFGReverseBlockReachabilityAnalysis &cra)
581      : CBM(cbm), TargetBlock(targetBlock), CRA(cra) {}
582    virtual bool visit(const WorkListUnit &U) {
583      ProgramPoint P = U.getNode()->getLocation();
584      const CFGBlock *B = 0;
585      if (Optional<StmtPoint> SP = P.getAs<StmtPoint>()) {
586        B = CBM->getBlock(SP->getStmt());
587      } else if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) {
588        B = BE->getDst();
589      } else if (Optional<BlockEntrance> BEnt = P.getAs<BlockEntrance>()) {
590        B = BEnt->getBlock();
591      } else if (Optional<BlockExit> BExit = P.getAs<BlockExit>()) {
592        B = BExit->getBlock();
593      }
594      if (!B)
595        return true;
596
597      return B == TargetBlock || CRA.isReachable(B, TargetBlock);
598    }
599  };
600  VisitWL visitWL(AC->getCFGStmtMap(), CB, *CRA);
601  // Were there any items in the worklist that could potentially reach
602  // this block?
603  if (CE.getWorkList()->visitItemsInWorkList(visitWL))
604    return false;
605
606  // Verify that this block is reachable from the entry block
607  if (!CRA->isReachable(&AC->getCFG()->getEntry(), CB))
608    return false;
609
610  // 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.
619bool IdempotentOperationChecker::CanVary(const Expr *Ex,
620                                         AnalysisDeclContext *AC) {
621  // 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:
649  case Stmt::BinaryTypeTraitExprClass:
650  case Stmt::GNUNullExprClass:
651  case Stmt::InitListExprClass:
652  case Stmt::DesignatedInitExprClass:
653  case Stmt::BlockExprClass:
654    return false;
655
656  // Cases requiring custom logic
657  case Stmt::UnaryExprOrTypeTraitExprClass: {
658    const UnaryExprOrTypeTraitExpr *SE =
659                       cast<const UnaryExprOrTypeTraitExpr>(Ex);
660    if (SE->getKind() != UETT_SizeOf)
661      return false;
662    return SE->getTypeOfArgument()->isVariableArrayType();
663  }
664  case Stmt::DeclRefExprClass:
665    // Check for constants/pseudoconstants
666    return !isConstantOrPseudoConstant(cast<DeclRefExpr>(Ex), AC);
667
668  // The next cases require recursion for subexpressions
669  case Stmt::BinaryOperatorClass: {
670    const BinaryOperator *B = cast<const BinaryOperator>(Ex);
671
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
678    return CanVary(B->getRHS(), AC)
679        || CanVary(B->getLHS(), AC);
680   }
681  case Stmt::UnaryOperatorClass:
682    return CanVary(cast<UnaryOperator>(Ex)->getSubExpr(), AC);
683  case Stmt::ConditionalOperatorClass:
684  case Stmt::BinaryConditionalOperatorClass:
685    return CanVary(cast<AbstractConditionalOperator>(Ex)->getCond(), AC);
686  }
687}
688
689// Returns true if a DeclRefExpr is or behaves like a constant.
690bool IdempotentOperationChecker::isConstantOrPseudoConstant(
691                                                          const DeclRefExpr *DR,
692                                                          AnalysisDeclContext *AC) {
693  // Check if the type of the Decl is const-qualified
694  if (DR->getType().isConstQualified())
695    return true;
696
697  // Check for an enum
698  if (isa<EnumConstantDecl>(DR->getDecl()))
699    return true;
700
701  const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
702  if (!VD)
703    return true;
704
705  // Check if the Decl behaves like a constant. This check also takes care of
706  // static variables, which can only change between function calls if they are
707  // modified in the AST.
708  PseudoConstantAnalysis *PCA = AC->getPseudoConstantAnalysis();
709  if (PCA->isPseudoConstant(VD))
710    return true;
711
712  return false;
713}
714
715// Recursively find any substatements containing VarDecl's with storage other
716// than local
717bool IdempotentOperationChecker::containsNonLocalVarDecl(const Stmt *S) {
718  const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(S);
719
720  if (DR)
721    if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
722      if (!VD->hasLocalStorage())
723        return true;
724
725  for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end();
726      ++I)
727    if (const Stmt *child = *I)
728      if (containsNonLocalVarDecl(child))
729        return true;
730
731  return false;
732}
733
734
735void ento::registerIdempotentOperationChecker(CheckerManager &mgr) {
736  mgr.registerChecker<IdempotentOperationChecker>();
737}
738