IdempotentOperationChecker.cpp revision 219077
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/CheckerV2.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#include <deque> 63 64using namespace clang; 65using namespace ento; 66 67namespace { 68class IdempotentOperationChecker 69 : public CheckerV2<check::PreStmt<BinaryOperator>, 70 check::PostStmt<BinaryOperator>, 71 check::EndAnalysis> { 72public: 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 77private: 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, AnalysisContext *AC); 87 static bool isTruncationExtensionAssignment(const Expr *LHS, 88 const Expr *RHS); 89 static bool pathWasCompletelyAnalyzed(AnalysisContext *AC, 90 const CFGBlock *CB, 91 const CoreEngine &CE); 92 static bool CanVary(const Expr *Ex, 93 AnalysisContext *AC); 94 static bool isConstantOrPseudoConstant(const DeclRefExpr *DR, 95 AnalysisContext *AC); 96 static bool containsNonLocalVarDecl(const Stmt *S); 97 98 // Hash table and related data structures 99 struct BinaryOperatorData { 100 BinaryOperatorData() : assumption(Possible), analysisContext(0) {} 101 102 Assumption assumption; 103 AnalysisContext *analysisContext; 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}; 111} 112 113void 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 AnalysisContext *AC = C.getCurrentAnalysisContext(); 122 Data.analysisContext = AC; 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 const GRState *state = C.getState(); 148 149 SVal LHSVal = state->getSVal(LHS); 150 SVal RHSVal = state->getSVal(RHS); 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 (!isa<Loc>(LHSVal)) { 177 A = Impossible; 178 return; 179 } 180 LHSVal = state->getSVal(cast<Loc>(LHSVal), 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. 330void 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 = cast<StmtPoint>(C.getPredecessor()->getLocation()).getStmt(); 337 338 // Ignore implicit calls to setters. 339 if (isa<ObjCPropertyRefExpr>(predStmt)) 340 return; 341 342 assert(isa<BinaryOperator>(predStmt)); 343 Data.explodedNodes.Add(C.getPredecessor()); 344} 345 346void IdempotentOperationChecker::checkEndAnalysis(ExplodedGraph &G, 347 BugReporter &BR, 348 ExprEngine &Eng) const { 349 BugType *BT = new BugType("Idempotent operation", "Dead code"); 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 AnalysisContext *AC = Data.analysisContext; 357 const ExplodedNodeSet &ES = Data.explodedNodes; 358 359 const BinaryOperator *B = i->first; 360 361 if (A == Impossible) 362 continue; 363 364 // If the analyzer did not finish, check to see if we can still emit this 365 // warning 366 if (Eng.hasWorkRemaining()) { 367 // If we can trace back 368 if (!pathWasCompletelyAnalyzed(AC, 369 AC->getCFGStmtMap()->getBlock(B), 370 Eng.getCoreEngine())) 371 continue; 372 } 373 374 // Select the error message and SourceRanges to report. 375 llvm::SmallString<128> buf; 376 llvm::raw_svector_ostream os(buf); 377 bool LHSRelevant = false, RHSRelevant = false; 378 switch (A) { 379 case Equal: 380 LHSRelevant = true; 381 RHSRelevant = true; 382 if (B->getOpcode() == BO_Assign) 383 os << "Assigned value is always the same as the existing value"; 384 else 385 os << "Both operands to '" << B->getOpcodeStr() 386 << "' always have the same value"; 387 break; 388 case LHSis1: 389 LHSRelevant = true; 390 os << "The left operand to '" << B->getOpcodeStr() << "' is always 1"; 391 break; 392 case RHSis1: 393 RHSRelevant = true; 394 os << "The right operand to '" << B->getOpcodeStr() << "' is always 1"; 395 break; 396 case LHSis0: 397 LHSRelevant = true; 398 os << "The left operand to '" << B->getOpcodeStr() << "' is always 0"; 399 break; 400 case RHSis0: 401 RHSRelevant = true; 402 os << "The right operand to '" << B->getOpcodeStr() << "' is always 0"; 403 break; 404 case Possible: 405 llvm_unreachable("Operation was never marked with an assumption"); 406 case Impossible: 407 llvm_unreachable(0); 408 } 409 410 // Add a report for each ExplodedNode 411 for (ExplodedNodeSet::iterator I = ES.begin(), E = ES.end(); I != E; ++I) { 412 EnhancedBugReport *report = new EnhancedBugReport(*BT, os.str(), *I); 413 414 // Add source ranges and visitor hooks 415 if (LHSRelevant) { 416 const Expr *LHS = i->first->getLHS(); 417 report->addRange(LHS->getSourceRange()); 418 report->addVisitorCreator(bugreporter::registerVarDeclsLastStore, LHS); 419 } 420 if (RHSRelevant) { 421 const Expr *RHS = i->first->getRHS(); 422 report->addRange(i->first->getRHS()->getSourceRange()); 423 report->addVisitorCreator(bugreporter::registerVarDeclsLastStore, RHS); 424 } 425 426 BR.EmitReport(report); 427 } 428 } 429 430 hash.clear(); 431} 432 433// Updates the current assumption given the new assumption 434inline void IdempotentOperationChecker::UpdateAssumption(Assumption &A, 435 const Assumption &New) { 436// If the assumption is the same, there is nothing to do 437 if (A == New) 438 return; 439 440 switch (A) { 441 // If we don't currently have an assumption, set it 442 case Possible: 443 A = New; 444 return; 445 446 // If we have determined that a valid state happened, ignore the new 447 // assumption. 448 case Impossible: 449 return; 450 451 // Any other case means that we had a different assumption last time. We don't 452 // currently support mixing assumptions for diagnostic reasons, so we set 453 // our assumption to be impossible. 454 default: 455 A = Impossible; 456 return; 457 } 458} 459 460// Check for a statement where a variable is self assigned to possibly avoid an 461// unused variable warning. 462bool IdempotentOperationChecker::isSelfAssign(const Expr *LHS, const Expr *RHS) { 463 LHS = LHS->IgnoreParenCasts(); 464 RHS = RHS->IgnoreParenCasts(); 465 466 const DeclRefExpr *LHS_DR = dyn_cast<DeclRefExpr>(LHS); 467 if (!LHS_DR) 468 return false; 469 470 const VarDecl *VD = dyn_cast<VarDecl>(LHS_DR->getDecl()); 471 if (!VD) 472 return false; 473 474 const DeclRefExpr *RHS_DR = dyn_cast<DeclRefExpr>(RHS); 475 if (!RHS_DR) 476 return false; 477 478 if (VD != RHS_DR->getDecl()) 479 return false; 480 481 return true; 482} 483 484// Returns true if the Expr points to a VarDecl that is not read anywhere 485// outside of self-assignments. 486bool IdempotentOperationChecker::isUnused(const Expr *E, 487 AnalysisContext *AC) { 488 if (!E) 489 return false; 490 491 const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()); 492 if (!DR) 493 return false; 494 495 const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()); 496 if (!VD) 497 return false; 498 499 if (AC->getPseudoConstantAnalysis()->wasReferenced(VD)) 500 return false; 501 502 return true; 503} 504 505// Check for self casts truncating/extending a variable 506bool IdempotentOperationChecker::isTruncationExtensionAssignment( 507 const Expr *LHS, 508 const Expr *RHS) { 509 510 const DeclRefExpr *LHS_DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParenCasts()); 511 if (!LHS_DR) 512 return false; 513 514 const VarDecl *VD = dyn_cast<VarDecl>(LHS_DR->getDecl()); 515 if (!VD) 516 return false; 517 518 const DeclRefExpr *RHS_DR = dyn_cast<DeclRefExpr>(RHS->IgnoreParenCasts()); 519 if (!RHS_DR) 520 return false; 521 522 if (VD != RHS_DR->getDecl()) 523 return false; 524 525 return dyn_cast<DeclRefExpr>(RHS->IgnoreParenLValueCasts()) == NULL; 526} 527 528// Returns false if a path to this block was not completely analyzed, or true 529// otherwise. 530bool 531IdempotentOperationChecker::pathWasCompletelyAnalyzed(AnalysisContext *AC, 532 const CFGBlock *CB, 533 const CoreEngine &CE) { 534 535 CFGReachabilityAnalysis *CRA = AC->getCFGReachablityAnalysis(); 536 537 // Test for reachability from any aborted blocks to this block 538 typedef CoreEngine::BlocksAborted::const_iterator AbortedIterator; 539 for (AbortedIterator I = CE.blocks_aborted_begin(), 540 E = CE.blocks_aborted_end(); I != E; ++I) { 541 const BlockEdge &BE = I->first; 542 543 // The destination block on the BlockEdge is the first block that was not 544 // analyzed. If we can reach this block from the aborted block, then this 545 // block was not completely analyzed. 546 // 547 // Also explicitly check if the current block is the destination block. 548 // While technically reachable, it means we aborted the analysis on 549 // a path that included that block. 550 const CFGBlock *destBlock = BE.getDst(); 551 if (destBlock == CB || CRA->isReachable(destBlock, CB)) 552 return false; 553 } 554 555 // For the items still on the worklist, see if they are in blocks that 556 // can eventually reach 'CB'. 557 class VisitWL : public WorkList::Visitor { 558 const CFGStmtMap *CBM; 559 const CFGBlock *TargetBlock; 560 CFGReachabilityAnalysis &CRA; 561 public: 562 VisitWL(const CFGStmtMap *cbm, const CFGBlock *targetBlock, 563 CFGReachabilityAnalysis &cra) 564 : CBM(cbm), TargetBlock(targetBlock), CRA(cra) {} 565 virtual bool visit(const WorkListUnit &U) { 566 ProgramPoint P = U.getNode()->getLocation(); 567 const CFGBlock *B = 0; 568 if (StmtPoint *SP = dyn_cast<StmtPoint>(&P)) { 569 B = CBM->getBlock(SP->getStmt()); 570 } 571 else if (BlockEdge *BE = dyn_cast<BlockEdge>(&P)) { 572 B = BE->getDst(); 573 } 574 else if (BlockEntrance *BEnt = dyn_cast<BlockEntrance>(&P)) { 575 B = BEnt->getBlock(); 576 } 577 else if (BlockExit *BExit = dyn_cast<BlockExit>(&P)) { 578 B = BExit->getBlock(); 579 } 580 if (!B) 581 return true; 582 583 return CRA.isReachable(B, TargetBlock); 584 } 585 }; 586 VisitWL visitWL(AC->getCFGStmtMap(), CB, *CRA); 587 // Were there any items in the worklist that could potentially reach 588 // this block? 589 if (CE.getWorkList()->visitItemsInWorkList(visitWL)) 590 return false; 591 592 // Verify that this block is reachable from the entry block 593 if (!CRA->isReachable(&AC->getCFG()->getEntry(), CB)) 594 return false; 595 596 // If we get to this point, there is no connection to the entry block or an 597 // aborted block. This path is unreachable and we can report the error. 598 return true; 599} 600 601// Recursive function that determines whether an expression contains any element 602// that varies. This could be due to a compile-time constant like sizeof. An 603// expression may also involve a variable that behaves like a constant. The 604// function returns true if the expression varies, and false otherwise. 605bool IdempotentOperationChecker::CanVary(const Expr *Ex, 606 AnalysisContext *AC) { 607 // Parentheses and casts are irrelevant here 608 Ex = Ex->IgnoreParenCasts(); 609 610 if (Ex->getLocStart().isMacroID()) 611 return false; 612 613 switch (Ex->getStmtClass()) { 614 // Trivially true cases 615 case Stmt::ArraySubscriptExprClass: 616 case Stmt::MemberExprClass: 617 case Stmt::StmtExprClass: 618 case Stmt::CallExprClass: 619 case Stmt::VAArgExprClass: 620 case Stmt::ShuffleVectorExprClass: 621 return true; 622 default: 623 return true; 624 625 // Trivially false cases 626 case Stmt::IntegerLiteralClass: 627 case Stmt::CharacterLiteralClass: 628 case Stmt::FloatingLiteralClass: 629 case Stmt::PredefinedExprClass: 630 case Stmt::ImaginaryLiteralClass: 631 case Stmt::StringLiteralClass: 632 case Stmt::OffsetOfExprClass: 633 case Stmt::CompoundLiteralExprClass: 634 case Stmt::AddrLabelExprClass: 635 case Stmt::BinaryTypeTraitExprClass: 636 case Stmt::GNUNullExprClass: 637 case Stmt::InitListExprClass: 638 case Stmt::DesignatedInitExprClass: 639 case Stmt::BlockExprClass: 640 case Stmt::BlockDeclRefExprClass: 641 return false; 642 643 // Cases requiring custom logic 644 case Stmt::SizeOfAlignOfExprClass: { 645 const SizeOfAlignOfExpr *SE = cast<const SizeOfAlignOfExpr>(Ex); 646 if (!SE->isSizeOf()) 647 return false; 648 return SE->getTypeOfArgument()->isVariableArrayType(); 649 } 650 case Stmt::DeclRefExprClass: 651 // Check for constants/pseudoconstants 652 return !isConstantOrPseudoConstant(cast<DeclRefExpr>(Ex), AC); 653 654 // The next cases require recursion for subexpressions 655 case Stmt::BinaryOperatorClass: { 656 const BinaryOperator *B = cast<const BinaryOperator>(Ex); 657 658 // Exclude cases involving pointer arithmetic. These are usually 659 // false positives. 660 if (B->getOpcode() == BO_Sub || B->getOpcode() == BO_Add) 661 if (B->getLHS()->getType()->getAs<PointerType>()) 662 return false; 663 664 return CanVary(B->getRHS(), AC) 665 || CanVary(B->getLHS(), AC); 666 } 667 case Stmt::UnaryOperatorClass: { 668 const UnaryOperator *U = cast<const UnaryOperator>(Ex); 669 // Handle trivial case first 670 switch (U->getOpcode()) { 671 case UO_Extension: 672 return false; 673 default: 674 return CanVary(U->getSubExpr(), AC); 675 } 676 } 677 case Stmt::ChooseExprClass: 678 return CanVary(cast<const ChooseExpr>(Ex)->getChosenSubExpr( 679 AC->getASTContext()), AC); 680 case Stmt::ConditionalOperatorClass: 681 case Stmt::BinaryConditionalOperatorClass: 682 return CanVary(cast<AbstractConditionalOperator>(Ex)->getCond(), AC); 683 } 684} 685 686// Returns true if a DeclRefExpr is or behaves like a constant. 687bool IdempotentOperationChecker::isConstantOrPseudoConstant( 688 const DeclRefExpr *DR, 689 AnalysisContext *AC) { 690 // Check if the type of the Decl is const-qualified 691 if (DR->getType().isConstQualified()) 692 return true; 693 694 // Check for an enum 695 if (isa<EnumConstantDecl>(DR->getDecl())) 696 return true; 697 698 const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()); 699 if (!VD) 700 return true; 701 702 // Check if the Decl behaves like a constant. This check also takes care of 703 // static variables, which can only change between function calls if they are 704 // modified in the AST. 705 PseudoConstantAnalysis *PCA = AC->getPseudoConstantAnalysis(); 706 if (PCA->isPseudoConstant(VD)) 707 return true; 708 709 return false; 710} 711 712// Recursively find any substatements containing VarDecl's with storage other 713// than local 714bool IdempotentOperationChecker::containsNonLocalVarDecl(const Stmt *S) { 715 const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(S); 716 717 if (DR) 718 if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) 719 if (!VD->hasLocalStorage()) 720 return true; 721 722 for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end(); 723 ++I) 724 if (const Stmt *child = *I) 725 if (containsNonLocalVarDecl(child)) 726 return true; 727 728 return false; 729} 730 731 732void ento::registerIdempotentOperationChecker(CheckerManager &mgr) { 733 mgr.registerChecker<IdempotentOperationChecker>(); 734} 735