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/SmallString.h"
  61 #include "llvm/ADT/BitVector.h"
  62 #include "llvm/Support/ErrorHandling.h"
  63
  64 using namespace clang;
  65 using namespace ento;
  66
  67 namespace {
  68 class IdempotentOperationChecker
  69   : public Checker<check::PreStmt<BinaryOperator>,
  70                      check::PostStmt<BinaryOperator>,
  71                      check::EndAnalysis> {
  72 public:
  73   void checkPreStmt(const BinaryOperator *B, CheckerContext &C) const;
  74   void checkPostStmt(const BinaryOperator *B, CheckerContext &C) const;
  75   void checkEndAnalysis(ExplodedGraph &G, BugReporter &B,ExprEngine &Eng) const;
  76
  77 private:
  78   // Our assumption about a particular operation.
  79   enum Assumption { Possible = 0, Impossible, Equal, LHSis1, RHSis1, LHSis0,
  80       RHSis0 };
  81
  82   static void UpdateAssumption(Assumption &A, const Assumption &New);
  83
  84   // False positive reduction methods
  85   static bool isSelfAssign(const Expr *LHS, const Expr *RHS);
  86   static bool isUnused(const Expr *E, AnalysisDeclContext *AC);
  87   static bool isTruncationExtensionAssignment(const Expr *LHS,
  88                                               const Expr *RHS);
  89   static bool pathWasCompletelyAnalyzed(AnalysisDeclContext *AC,
  90                                         const CFGBlock *CB,
  91                                         const CoreEngine &CE);
  92   static bool CanVary(const Expr *Ex,
  93                       AnalysisDeclContext *AC);
  94   static bool isConstantOrPseudoConstant(const DeclRefExpr *DR,
  95                                          AnalysisDeclContext *AC);
  96   static bool containsNonLocalVarDecl(const Stmt *S);
  97
  98   // Hash table and related data structures
  99   struct BinaryOperatorData {
 100     BinaryOperatorData() : assumption(Possible) {}
 101
 102     Assumption assumption;
 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   AnalysisDeclContext *AC = C.getCurrentAnalysisDeclContext();
 121
 122   // If we already have visited this node on a path that does not contain an
 123   // idempotent operation, return immediately.
 124   if (A == Impossible)
 125     return;
 126
 127   // Retrieve both sides of the operator and determine if they can vary (which
 128   // may mean this is a false positive.
 129   const Expr *LHS = B->getLHS();
 130   const Expr *RHS = B->getRHS();
 131
 132   // At this stage we can calculate whether each side contains a false positive
 133   // that applies to all operators. We only need to calculate this the first
 134   // time.
 135   bool LHSContainsFalsePositive = false, RHSContainsFalsePositive = false;
 136   if (A == Possible) {
 137     // An expression contains a false positive if it can't vary, or if it
 138     // contains a known false positive VarDecl.
 139     LHSContainsFalsePositive = !CanVary(LHS, AC)
 140         || containsNonLocalVarDecl(LHS);
 141     RHSContainsFalsePositive = !CanVary(RHS, AC)
 142         || containsNonLocalVarDecl(RHS);
 143   }
 144
 145   ProgramStateRef state = C.getState();
 146   const LocationContext *LCtx = C.getLocationContext();
 147   SVal LHSVal = state->getSVal(LHS, LCtx);
 148   SVal RHSVal = state->getSVal(RHS, LCtx);
 149
 150   // If either value is unknown, we can't be 100% sure of all paths.
 151   if (LHSVal.isUnknownOrUndef() || RHSVal.isUnknownOrUndef()) {
 152     A = Impossible;
 153     return;
 154   }
 155   BinaryOperator::Opcode Op = B->getOpcode();
 156
 157   // Dereference the LHS SVal if this is an assign operation
 158   switch (Op) {
 159   default:
 160     break;
 161
 162   // Fall through intentional
 163   case BO_AddAssign:
 164   case BO_SubAssign:
 165   case BO_MulAssign:
 166   case BO_DivAssign:
 167   case BO_AndAssign:
 168   case BO_OrAssign:
 169   case BO_XorAssign:
 170   case BO_ShlAssign:
 171   case BO_ShrAssign:
 172   case BO_Assign:
 173   // Assign statements have one extra level of indirection
 174     if (!isa<Loc>(LHSVal)) {
 175       A = Impossible;
 176       return;
 177     }
 178     LHSVal = state->getSVal(cast<Loc>(LHSVal), LHS->getType());
 179   }
 180
 181
 182   // We now check for various cases which result in an idempotent operation.
 183
 184   // x op x
 185   switch (Op) {
 186   default:
 187     break; // We don't care about any other operators.
 188
 189   // Fall through intentional
 190   case BO_Assign:
 191     // x Assign x can be used to silence unused variable warnings intentionally.
 192     // If this is a self assignment and the variable is referenced elsewhere,
 193     // and the assignment is not a truncation or extension, then it is a false
 194     // positive.
 195     if (isSelfAssign(LHS, RHS)) {
 196       if (!isUnused(LHS, AC) && !isTruncationExtensionAssignment(LHS, RHS)) {
 197         UpdateAssumption(A, Equal);
 198         return;
 199       }
 200       else {
 201         A = Impossible;
 202         return;
 203       }
 204     }
 205
 206   case BO_SubAssign:
 207   case BO_DivAssign:
 208   case BO_AndAssign:
 209   case BO_OrAssign:
 210   case BO_XorAssign:
 211   case BO_Sub:
 212   case BO_Div:
 213   case BO_And:
 214   case BO_Or:
 215   case BO_Xor:
 216   case BO_LOr:
 217   case BO_LAnd:
 218   case BO_EQ:
 219   case BO_NE:
 220     if (LHSVal != RHSVal || LHSContainsFalsePositive
 221         || RHSContainsFalsePositive)
 222       break;
 223     UpdateAssumption(A, Equal);
 224     return;
 225   }
 226
 227   // x op 1
 228   switch (Op) {
 229    default:
 230      break; // We don't care about any other operators.
 231
 232    // Fall through intentional
 233    case BO_MulAssign:
 234    case BO_DivAssign:
 235    case BO_Mul:
 236    case BO_Div:
 237    case BO_LOr:
 238    case BO_LAnd:
 239      if (!RHSVal.isConstant(1) || RHSContainsFalsePositive)
 240        break;
 241      UpdateAssumption(A, RHSis1);
 242      return;
 243   }
 244
 245   // 1 op x
 246   switch (Op) {
 247   default:
 248     break; // We don't care about any other operators.
 249
 250   // Fall through intentional
 251   case BO_MulAssign:
 252   case BO_Mul:
 253   case BO_LOr:
 254   case BO_LAnd:
 255     if (!LHSVal.isConstant(1) || LHSContainsFalsePositive)
 256       break;
 257     UpdateAssumption(A, LHSis1);
 258     return;
 259   }
 260
 261   // x op 0
 262   switch (Op) {
 263   default:
 264     break; // We don't care about any other operators.
 265
 266   // Fall through intentional
 267   case BO_AddAssign:
 268   case BO_SubAssign:
 269   case BO_MulAssign:
 270   case BO_AndAssign:
 271   case BO_OrAssign:
 272   case BO_XorAssign:
 273   case BO_Add:
 274   case BO_Sub:
 275   case BO_Mul:
 276   case BO_And:
 277   case BO_Or:
 278   case BO_Xor:
 279   case BO_Shl:
 280   case BO_Shr:
 281   case BO_LOr:
 282   case BO_LAnd:
 283     if (!RHSVal.isConstant(0) || RHSContainsFalsePositive)
 284       break;
 285     UpdateAssumption(A, RHSis0);
 286     return;
 287   }
 288
 289   // 0 op x
 290   switch (Op) {
 291   default:
 292     break; // We don't care about any other operators.
 293
 294   // Fall through intentional
 295   //case BO_AddAssign: // Common false positive
 296   case BO_SubAssign: // Check only if unsigned
 297   case BO_MulAssign:
 298   case BO_DivAssign:
 299   case BO_AndAssign:
 300   //case BO_OrAssign: // Common false positive
 301   //case BO_XorAssign: // Common false positive
 302   case BO_ShlAssign:
 303   case BO_ShrAssign:
 304   case BO_Add:
 305   case BO_Sub:
 306   case BO_Mul:
 307   case BO_Div:
 308   case BO_And:
 309   case BO_Or:
 310   case BO_Xor:
 311   case BO_Shl:
 312   case BO_Shr:
 313   case BO_LOr:
 314   case BO_LAnd:
 315     if (!LHSVal.isConstant(0) || LHSContainsFalsePositive)
 316       break;
 317     UpdateAssumption(A, LHSis0);
 318     return;
 319   }
 320
 321   // If we get to this point, there has been a valid use of this operation.
 322   A = Impossible;
 323 }
 324
 325 // At the post visit stage, the predecessor ExplodedNode will be the
 326 // BinaryOperator that was just created. We use this hook to collect the
 327 // ExplodedNode.
 328 void IdempotentOperationChecker::checkPostStmt(const BinaryOperator *B,
 329                                                CheckerContext &C) const {
 330   // Add the ExplodedNode we just visited
 331   BinaryOperatorData &Data = hash[B];
 332
 333   const Stmt *predStmt
 334     = cast<StmtPoint>(C.getPredecessor()->getLocation()).getStmt();
 335
 336   // Ignore implicit calls to setters.
 337   if (!isa<BinaryOperator>(predStmt))
 338     return;
 339
 340   Data.explodedNodes.Add(C.getPredecessor());
 341 }
 342
 343 void IdempotentOperationChecker::checkEndAnalysis(ExplodedGraph &G,
 344                                                   BugReporter &BR,
 345                                                   ExprEngine &Eng) const {
 346   BugType *BT = new BugType("Idempotent operation", "Dead code");
 347   // Iterate over the hash to see if we have any paths with definite
 348   // idempotent operations.
 349   for (AssumptionMap::const_iterator i = hash.begin(); i != hash.end(); ++i) {
 350     // Unpack the hash contents
 351     const BinaryOperatorData &Data = i->second;
 352     const Assumption &A = Data.assumption;
 353     const ExplodedNodeSet &ES = Data.explodedNodes;
 354
 355     // If there are no nodes accosted with the expression, nothing to report.
 356     // FIXME: This is possible because the checker does part of processing in
 357     // checkPreStmt and part in checkPostStmt.
 358     if (ES.begin() == ES.end())
 359       continue;
 360
 361     const BinaryOperator *B = i->first;
 362
 363     if (A == Impossible)
 364       continue;
 365
 366     // If the analyzer did not finish, check to see if we can still emit this
 367     // warning
 368     if (Eng.hasWorkRemaining()) {
 369       // If we can trace back
 370       AnalysisDeclContext *AC = (*ES.begin())->getLocationContext()
 371                                          ->getAnalysisDeclContext();
 372       if (!pathWasCompletelyAnalyzed(AC,
 373                                      AC->getCFGStmtMap()->getBlock(B),
 374                                      Eng.getCoreEngine()))
 375         continue;
 376     }
 377
 378     // Select the error message and SourceRanges to report.
 379     SmallString<128> buf;
 380     llvm::raw_svector_ostream os(buf);
 381     bool LHSRelevant = false, RHSRelevant = false;
 382     switch (A) {
 383     case Equal:
 384       LHSRelevant = true;
 385       RHSRelevant = true;
 386       if (B->getOpcode() == BO_Assign)
 387         os << "Assigned value is always the same as the existing value";
 388       else
 389         os << "Both operands to '" << B->getOpcodeStr()
 390            << "' always have the same value";
 391       break;
 392     case LHSis1:
 393       LHSRelevant = true;
 394       os << "The left operand to '" << B->getOpcodeStr() << "' is always 1";
 395       break;
 396     case RHSis1:
 397       RHSRelevant = true;
 398       os << "The right operand to '" << B->getOpcodeStr() << "' is always 1";
 399       break;
 400     case LHSis0:
 401       LHSRelevant = true;
 402       os << "The left operand to '" << B->getOpcodeStr() << "' is always 0";
 403       break;
 404     case RHSis0:
 405       RHSRelevant = true;
 406       os << "The right operand to '" << B->getOpcodeStr() << "' is always 0";
 407       break;
 408     case Possible:
 409       llvm_unreachable("Operation was never marked with an assumption");
 410     case Impossible:
 411       llvm_unreachable(0);
 412     }
 413
 414     // Add a report for each ExplodedNode
 415     for (ExplodedNodeSet::iterator I = ES.begin(), E = ES.end(); I != E; ++I) {
 416       BugReport *report = new BugReport(*BT, os.str(), *I);
 417
 418       // Add source ranges and visitor hooks
 419       if (LHSRelevant) {
 420         const Expr *LHS = i->first->getLHS();
 421         report->addRange(LHS->getSourceRange());
 422         FindLastStoreBRVisitor::registerStatementVarDecls(*report, LHS);
 423       }
 424       if (RHSRelevant) {
 425         const Expr *RHS = i->first->getRHS();
 426         report->addRange(i->first->getRHS()->getSourceRange());
 427         FindLastStoreBRVisitor::registerStatementVarDecls(*report, RHS);
 428       }
 429
 430       BR.EmitReport(report);
 431     }
 432   }
 433
 434   hash.clear();
 435 }
 436
 437 // Updates the current assumption given the new assumption
 438 inline void IdempotentOperationChecker::UpdateAssumption(Assumption &A,
 439                                                         const Assumption &New) {
 440 // If the assumption is the same, there is nothing to do
 441   if (A == New)
 442     return;
 443
 444   switch (A) {
 445   // If we don't currently have an assumption, set it
 446   case Possible:
 447     A = New;
 448     return;
 449
 450   // If we have determined that a valid state happened, ignore the new
 451   // assumption.
 452   case Impossible:
 453     return;
 454
 455   // Any other case means that we had a different assumption last time. We don't
 456   // currently support mixing assumptions for diagnostic reasons, so we set
 457   // our assumption to be impossible.
 458   default:
 459     A = Impossible;
 460     return;
 461   }
 462 }
 463
 464 // Check for a statement where a variable is self assigned to possibly avoid an
 465 // unused variable warning.
 466 bool IdempotentOperationChecker::isSelfAssign(const Expr *LHS, const Expr *RHS) {
 467   LHS = LHS->IgnoreParenCasts();
 468   RHS = RHS->IgnoreParenCasts();
 469
 470   const DeclRefExpr *LHS_DR = dyn_cast<DeclRefExpr>(LHS);
 471   if (!LHS_DR)
 472     return false;
 473
 474   const VarDecl *VD = dyn_cast<VarDecl>(LHS_DR->getDecl());
 475   if (!VD)
 476     return false;
 477
 478   const DeclRefExpr *RHS_DR = dyn_cast<DeclRefExpr>(RHS);
 479   if (!RHS_DR)
 480     return false;
 481
 482   if (VD != RHS_DR->getDecl())
 483     return false;
 484
 485   return true;
 486 }
 487
 488 // Returns true if the Expr points to a VarDecl that is not read anywhere
 489 // outside of self-assignments.
 490 bool IdempotentOperationChecker::isUnused(const Expr *E,
 491                                           AnalysisDeclContext *AC) {
 492   if (!E)
 493     return false;
 494
 495   const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E->IgnoreParenCasts());
 496   if (!DR)
 497     return false;
 498
 499   const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl());
 500   if (!VD)
 501     return false;
 502
 503   if (AC->getPseudoConstantAnalysis()->wasReferenced(VD))
 504     return false;
 505
 506   return true;
 507 }
 508
 509 // Check for self casts truncating/extending a variable
 510 bool IdempotentOperationChecker::isTruncationExtensionAssignment(
 511                                                               const Expr *LHS,
 512                                                               const Expr *RHS) {
 513
 514   const DeclRefExpr *LHS_DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParenCasts());
 515   if (!LHS_DR)
 516     return false;
 517
 518   const VarDecl *VD = dyn_cast<VarDecl>(LHS_DR->getDecl());
 519   if (!VD)
 520     return false;
 521
 522   const DeclRefExpr *RHS_DR = dyn_cast<DeclRefExpr>(RHS->IgnoreParenCasts());
 523   if (!RHS_DR)
 524     return false;
 525
 526   if (VD != RHS_DR->getDecl())
 527      return false;
 528
 529   return dyn_cast<DeclRefExpr>(RHS->IgnoreParenLValueCasts()) == NULL;
 530 }
 531
 532 // Returns false if a path to this block was not completely analyzed, or true
 533 // otherwise.
 534 bool
 535 IdempotentOperationChecker::pathWasCompletelyAnalyzed(AnalysisDeclContext *AC,
 536                                                       const CFGBlock *CB,
 537                                                       const CoreEngine &CE) {
 538
 539   CFGReverseBlockReachabilityAnalysis *CRA = AC->getCFGReachablityAnalysis();
 540
 541   // Test for reachability from any aborted blocks to this block
 542   typedef CoreEngine::BlocksExhausted::const_iterator ExhaustedIterator;
 543   for (ExhaustedIterator I = CE.blocks_exhausted_begin(),
 544       E = CE.blocks_exhausted_end(); I != E; ++I) {
 545     const BlockEdge &BE =  I->first;
 546
 547     // The destination block on the BlockEdge is the first block that was not
 548     // analyzed. If we can reach this block from the aborted block, then this
 549     // block was not completely analyzed.
 550     //
 551     // Also explicitly check if the current block is the destination block.
 552     // While technically reachable, it means we aborted the analysis on
 553     // a path that included that block.
 554     const CFGBlock *destBlock = BE.getDst();
 555     if (destBlock == CB || CRA->isReachable(destBlock, CB))
 556       return false;
 557   }
 558
 559   // Test for reachability from blocks we just gave up on.
 560   typedef CoreEngine::BlocksAborted::const_iterator AbortedIterator;
 561   for (AbortedIterator I = CE.blocks_aborted_begin(),
 562        E = CE.blocks_aborted_end(); I != E; ++I) {
 563     const CFGBlock *destBlock = I->first;
 564     if (destBlock == CB || CRA->isReachable(destBlock, CB))
 565       return false;
 566   }
 567
 568   // For the items still on the worklist, see if they are in blocks that
 569   // can eventually reach 'CB'.
 570   class VisitWL : public WorkList::Visitor {
 571     const CFGStmtMap *CBM;
 572     const CFGBlock *TargetBlock;
 573     CFGReverseBlockReachabilityAnalysis &CRA;
 574   public:
 575     VisitWL(const CFGStmtMap *cbm, const CFGBlock *targetBlock,
 576             CFGReverseBlockReachabilityAnalysis &cra)
 577       : CBM(cbm), TargetBlock(targetBlock), CRA(cra) {}
 578     virtual bool visit(const WorkListUnit &U) {
 579       ProgramPoint P = U.getNode()->getLocation();
 580       const CFGBlock *B = 0;
 581       if (StmtPoint *SP = dyn_cast<StmtPoint>(&P)) {
 582         B = CBM->getBlock(SP->getStmt());
 583       }
 584       else if (BlockEdge *BE = dyn_cast<BlockEdge>(&P)) {
 585         B = BE->getDst();
 586       }
 587       else if (BlockEntrance *BEnt = dyn_cast<BlockEntrance>(&P)) {
 588         B = BEnt->getBlock();
 589       }
 590       else if (BlockExit *BExit = dyn_cast<BlockExit>(&P)) {
 591         B = BExit->getBlock();
 592       }
 593       if (!B)
 594         return true;
 595
 596       return B == TargetBlock || CRA.isReachable(B, TargetBlock);
 597     }
 598   };
 599   VisitWL visitWL(AC->getCFGStmtMap(), CB, *CRA);
 600   // Were there any items in the worklist that could potentially reach
 601   // this block?
 602   if (CE.getWorkList()->visitItemsInWorkList(visitWL))
 603     return false;
 604
 605   // Verify that this block is reachable from the entry block
 606   if (!CRA->isReachable(&AC->getCFG()->getEntry(), CB))
 607     return false;
 608
 609   // If we get to this point, there is no connection to the entry block or an
 610   // aborted block. This path is unreachable and we can report the error.
 611   return true;
 612 }
 613
 614 // Recursive function that determines whether an expression contains any element
 615 // that varies. This could be due to a compile-time constant like sizeof. An
 616 // expression may also involve a variable that behaves like a constant. The
 617 // function returns true if the expression varies, and false otherwise.
 618 bool IdempotentOperationChecker::CanVary(const Expr *Ex,
 619                                          AnalysisDeclContext *AC) {
 620   // Parentheses and casts are irrelevant here
 621   Ex = Ex->IgnoreParenCasts();
 622
 623   if (Ex->getLocStart().isMacroID())
 624     return false;
 625
 626   switch (Ex->getStmtClass()) {
 627   // Trivially true cases
 628   case Stmt::ArraySubscriptExprClass:
 629   case Stmt::MemberExprClass:
 630   case Stmt::StmtExprClass:
 631   case Stmt::CallExprClass:
 632   case Stmt::VAArgExprClass:
 633   case Stmt::ShuffleVectorExprClass:
 634     return true;
 635   default:
 636     return true;
 637
 638   // Trivially false cases
 639   case Stmt::IntegerLiteralClass:
 640   case Stmt::CharacterLiteralClass:
 641   case Stmt::FloatingLiteralClass:
 642   case Stmt::PredefinedExprClass:
 643   case Stmt::ImaginaryLiteralClass:
 644   case Stmt::StringLiteralClass:
 645   case Stmt::OffsetOfExprClass:
 646   case Stmt::CompoundLiteralExprClass:
 647   case Stmt::AddrLabelExprClass:
 648   case Stmt::BinaryTypeTraitExprClass:
 649   case Stmt::GNUNullExprClass:
 650   case Stmt::InitListExprClass:
 651   case Stmt::DesignatedInitExprClass:
 652   case Stmt::BlockExprClass:
 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                                                           AnalysisDeclContext *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 }