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