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/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
  65 using namespace clang;
  66 using namespace ento;
  67
  68 namespace {
  69 class IdempotentOperationChecker
  70   : public Checker<check::PreStmt<BinaryOperator>,
  71                      check::PostStmt<BinaryOperator>,
  72                      check::EndAnalysis> {
  73 public:
  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
  78 private:
  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
 114 void 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.
 330 void 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
 345 void 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
 442 inline 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.
 470 bool 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.
 494 bool 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
 514 bool 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.
 538 bool
 539 IdempotentOperationChecker::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.
 619 bool 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     const UnaryOperator *U = cast<const UnaryOperator>(Ex);
 683     // Handle trivial case first
 684     switch (U->getOpcode()) {
 685     case UO_Extension:
 686       return false;
 687     default:
 688       return CanVary(U->getSubExpr(), AC);
 689     }
 690   }
 691   case Stmt::ChooseExprClass:
 692     return CanVary(cast<const ChooseExpr>(Ex)->getChosenSubExpr(
 693         AC->getASTContext()), AC);
 694   case Stmt::ConditionalOperatorClass:
 695   case Stmt::BinaryConditionalOperatorClass:
 696     return CanVary(cast<AbstractConditionalOperator>(Ex)->getCond(), AC);
 697   }
 698 }
 699
 700 // Returns true if a DeclRefExpr is or behaves like a constant.
 701 bool IdempotentOperationChecker::isConstantOrPseudoConstant(
 702                                                           const DeclRefExpr *DR,
 703                                                           AnalysisDeclContext *AC) {
 704   // Check if the type of the Decl is const-qualified
 705   if (DR->getType().isConstQualified())
 706     return true;
 707
 708   // Check for an enum
 709   if (isa<EnumConstantDecl>(DR->getDecl()))
 710     return true;
 711
 712   const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
 713   if (!VD)
 714     return true;
 715
 716   // Check if the Decl behaves like a constant. This check also takes care of
 717   // static variables, which can only change between function calls if they are
 718   // modified in the AST.
 719   PseudoConstantAnalysis *PCA = AC->getPseudoConstantAnalysis();
 720   if (PCA->isPseudoConstant(VD))
 721     return true;
 722
 723   return false;
 724 }
 725
 726 // Recursively find any substatements containing VarDecl's with storage other
 727 // than local
 728 bool IdempotentOperationChecker::containsNonLocalVarDecl(const Stmt *S) {
 729   const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(S);
 730
 731   if (DR)
 732     if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()))
 733       if (!VD->hasLocalStorage())
 734         return true;
 735
 736   for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end();
 737       ++I)
 738     if (const Stmt *child = *I)
 739       if (containsNonLocalVarDecl(child))
 740         return true;
 741
 742   return false;
 743 }
 744
 745
 746 void ento::registerIdempotentOperationChecker(CheckerManager &mgr) {
 747   mgr.registerChecker<IdempotentOperationChecker>();
 748 }