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