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 } 748