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