contrib/llvm/tools/clang/lib/StaticAnalyzer/Checkers/IdempotentOperationChecker.cpp

   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 {
  99     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
 112 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.
 329 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
 344 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
 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.
 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.
 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
 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
 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.
 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.
 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
 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
 740 void ento::registerIdempotentOperationChecker(CheckerManager &mgr) {
 741   mgr.registerChecker<IdempotentOperationChecker>();
 742 }