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