1218887Sdim//==- IdempotentOperationChecker.cpp - Idempotent Operations ----*- C++ -*-==// 2218887Sdim// 3218887Sdim// The LLVM Compiler Infrastructure 4218887Sdim// 5218887Sdim// This file is distributed under the University of Illinois Open Source 6218887Sdim// License. See LICENSE.TXT for details. 7218887Sdim// 8218887Sdim//===----------------------------------------------------------------------===// 9218887Sdim// 10218887Sdim// This file defines a set of path-sensitive checks for idempotent and/or 11218887Sdim// tautological operations. Each potential operation is checked along all paths 12218887Sdim// to see if every path results in a pointless operation. 13218887Sdim// +-------------------------------------------+ 14218887Sdim// |Table of idempotent/tautological operations| 15218887Sdim// +-------------------------------------------+ 16218887Sdim//+--------------------------------------------------------------------------+ 17218887Sdim//|Operator | x op x | x op 1 | 1 op x | x op 0 | 0 op x | x op ~0 | ~0 op x | 18218887Sdim//+--------------------------------------------------------------------------+ 19218887Sdim// +, += | | | | x | x | | 20218887Sdim// -, -= | | | | x | -x | | 21218887Sdim// *, *= | | x | x | 0 | 0 | | 22218887Sdim// /, /= | 1 | x | | N/A | 0 | | 23218887Sdim// &, &= | x | | | 0 | 0 | x | x 24218887Sdim// |, |= | x | | | x | x | ~0 | ~0 25218887Sdim// ^, ^= | 0 | | | x | x | | 26218887Sdim// <<, <<= | | | | x | 0 | | 27218887Sdim// >>, >>= | | | | x | 0 | | 28263508Sdim// || | x | 1 | 1 | x | x | 1 | 1 29263508Sdim// && | x | x | x | 0 | 0 | x | x 30218887Sdim// = | x | | | | | | 31218887Sdim// == | 1 | | | | | | 32218887Sdim// >= | 1 | | | | | | 33218887Sdim// <= | 1 | | | | | | 34218887Sdim// > | 0 | | | | | | 35218887Sdim// < | 0 | | | | | | 36218887Sdim// != | 0 | | | | | | 37218887Sdim//===----------------------------------------------------------------------===// 38218887Sdim// 39218887Sdim// Things TODO: 40218887Sdim// - Improved error messages 41218887Sdim// - Handle mixed assumptions (which assumptions can belong together?) 42218887Sdim// - Finer grained false positive control (levels) 43218887Sdim// - Handling ~0 values 44218887Sdim 45218887Sdim#include "ClangSACheckers.h" 46249423Sdim#include "clang/AST/Stmt.h" 47249423Sdim#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h" 48249423Sdim#include "clang/Analysis/Analyses/PseudoConstantAnalysis.h" 49218887Sdim#include "clang/Analysis/CFGStmtMap.h" 50249423Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 51249423Sdim#include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" 52221345Sdim#include "clang/StaticAnalyzer/Core/Checker.h" 53218887Sdim#include "clang/StaticAnalyzer/Core/CheckerManager.h" 54219077Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h" 55218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CheckerHelpers.h" 56218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h" 57218887Sdim#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" 58249423Sdim#include "llvm/ADT/BitVector.h" 59218887Sdim#include "llvm/ADT/DenseMap.h" 60218887Sdim#include "llvm/ADT/SmallSet.h" 61234353Sdim#include "llvm/ADT/SmallString.h" 62218887Sdim#include "llvm/Support/ErrorHandling.h" 63249423Sdim#include "llvm/Support/raw_ostream.h" 64218887Sdim 65218887Sdimusing namespace clang; 66218887Sdimusing namespace ento; 67218887Sdim 68218887Sdimnamespace { 69218887Sdimclass IdempotentOperationChecker 70221345Sdim : public Checker<check::PreStmt<BinaryOperator>, 71219077Sdim check::PostStmt<BinaryOperator>, 72219077Sdim check::EndAnalysis> { 73218887Sdimpublic: 74219077Sdim void checkPreStmt(const BinaryOperator *B, CheckerContext &C) const; 75219077Sdim void checkPostStmt(const BinaryOperator *B, CheckerContext &C) const; 76219077Sdim void checkEndAnalysis(ExplodedGraph &G, BugReporter &B,ExprEngine &Eng) const; 77218887Sdim 78218887Sdimprivate: 79218887Sdim // Our assumption about a particular operation. 80218887Sdim enum Assumption { Possible = 0, Impossible, Equal, LHSis1, RHSis1, LHSis0, 81218887Sdim RHSis0 }; 82218887Sdim 83219077Sdim static void UpdateAssumption(Assumption &A, const Assumption &New); 84218887Sdim 85218887Sdim // False positive reduction methods 86218887Sdim static bool isSelfAssign(const Expr *LHS, const Expr *RHS); 87234353Sdim static bool isUnused(const Expr *E, AnalysisDeclContext *AC); 88218887Sdim static bool isTruncationExtensionAssignment(const Expr *LHS, 89218887Sdim const Expr *RHS); 90234353Sdim static bool pathWasCompletelyAnalyzed(AnalysisDeclContext *AC, 91219077Sdim const CFGBlock *CB, 92219077Sdim const CoreEngine &CE); 93218887Sdim static bool CanVary(const Expr *Ex, 94234353Sdim AnalysisDeclContext *AC); 95218887Sdim static bool isConstantOrPseudoConstant(const DeclRefExpr *DR, 96234353Sdim AnalysisDeclContext *AC); 97218887Sdim static bool containsNonLocalVarDecl(const Stmt *S); 98218887Sdim 99218887Sdim // Hash table and related data structures 100218887Sdim struct BinaryOperatorData { 101226633Sdim BinaryOperatorData() : assumption(Possible) {} 102218887Sdim 103218887Sdim Assumption assumption; 104218887Sdim ExplodedNodeSet explodedNodes; // Set of ExplodedNodes that refer to a 105218887Sdim // BinaryOperator 106218887Sdim }; 107218887Sdim typedef llvm::DenseMap<const BinaryOperator *, BinaryOperatorData> 108218887Sdim AssumptionMap; 109219077Sdim mutable AssumptionMap hash; 110239462Sdim mutable OwningPtr<BugType> BT; 111218887Sdim}; 112218887Sdim} 113218887Sdim 114219077Sdimvoid IdempotentOperationChecker::checkPreStmt(const BinaryOperator *B, 115219077Sdim CheckerContext &C) const { 116218887Sdim // Find or create an entry in the hash for this BinaryOperator instance. 117218887Sdim // If we haven't done a lookup before, it will get default initialized to 118218887Sdim // 'Possible'. At this stage we do not store the ExplodedNode, as it has not 119218887Sdim // been created yet. 120218887Sdim BinaryOperatorData &Data = hash[B]; 121218887Sdim Assumption &A = Data.assumption; 122234353Sdim AnalysisDeclContext *AC = C.getCurrentAnalysisDeclContext(); 123218887Sdim 124218887Sdim // If we already have visited this node on a path that does not contain an 125218887Sdim // idempotent operation, return immediately. 126218887Sdim if (A == Impossible) 127218887Sdim return; 128218887Sdim 129218887Sdim // Retrieve both sides of the operator and determine if they can vary (which 130218887Sdim // may mean this is a false positive. 131218887Sdim const Expr *LHS = B->getLHS(); 132218887Sdim const Expr *RHS = B->getRHS(); 133218887Sdim 134218887Sdim // At this stage we can calculate whether each side contains a false positive 135218887Sdim // that applies to all operators. We only need to calculate this the first 136218887Sdim // time. 137218887Sdim bool LHSContainsFalsePositive = false, RHSContainsFalsePositive = false; 138218887Sdim if (A == Possible) { 139218887Sdim // An expression contains a false positive if it can't vary, or if it 140218887Sdim // contains a known false positive VarDecl. 141218887Sdim LHSContainsFalsePositive = !CanVary(LHS, AC) 142218887Sdim || containsNonLocalVarDecl(LHS); 143218887Sdim RHSContainsFalsePositive = !CanVary(RHS, AC) 144218887Sdim || containsNonLocalVarDecl(RHS); 145218887Sdim } 146218887Sdim 147234353Sdim ProgramStateRef state = C.getState(); 148234353Sdim const LocationContext *LCtx = C.getLocationContext(); 149234353Sdim SVal LHSVal = state->getSVal(LHS, LCtx); 150234353Sdim SVal RHSVal = state->getSVal(RHS, LCtx); 151218887Sdim 152218887Sdim // If either value is unknown, we can't be 100% sure of all paths. 153218887Sdim if (LHSVal.isUnknownOrUndef() || RHSVal.isUnknownOrUndef()) { 154218887Sdim A = Impossible; 155218887Sdim return; 156218887Sdim } 157218887Sdim BinaryOperator::Opcode Op = B->getOpcode(); 158218887Sdim 159218887Sdim // Dereference the LHS SVal if this is an assign operation 160218887Sdim switch (Op) { 161218887Sdim default: 162218887Sdim break; 163218887Sdim 164218887Sdim // Fall through intentional 165218887Sdim case BO_AddAssign: 166218887Sdim case BO_SubAssign: 167218887Sdim case BO_MulAssign: 168218887Sdim case BO_DivAssign: 169218887Sdim case BO_AndAssign: 170218887Sdim case BO_OrAssign: 171218887Sdim case BO_XorAssign: 172218887Sdim case BO_ShlAssign: 173218887Sdim case BO_ShrAssign: 174218887Sdim case BO_Assign: 175218887Sdim // Assign statements have one extra level of indirection 176249423Sdim if (!LHSVal.getAs<Loc>()) { 177218887Sdim A = Impossible; 178218887Sdim return; 179218887Sdim } 180249423Sdim LHSVal = state->getSVal(LHSVal.castAs<Loc>(), LHS->getType()); 181218887Sdim } 182218887Sdim 183218887Sdim 184218887Sdim // We now check for various cases which result in an idempotent operation. 185218887Sdim 186218887Sdim // x op x 187218887Sdim switch (Op) { 188218887Sdim default: 189218887Sdim break; // We don't care about any other operators. 190218887Sdim 191218887Sdim // Fall through intentional 192218887Sdim case BO_Assign: 193218887Sdim // x Assign x can be used to silence unused variable warnings intentionally. 194218887Sdim // If this is a self assignment and the variable is referenced elsewhere, 195218887Sdim // and the assignment is not a truncation or extension, then it is a false 196218887Sdim // positive. 197218887Sdim if (isSelfAssign(LHS, RHS)) { 198218887Sdim if (!isUnused(LHS, AC) && !isTruncationExtensionAssignment(LHS, RHS)) { 199218887Sdim UpdateAssumption(A, Equal); 200218887Sdim return; 201218887Sdim } 202218887Sdim else { 203218887Sdim A = Impossible; 204218887Sdim return; 205218887Sdim } 206218887Sdim } 207218887Sdim 208218887Sdim case BO_SubAssign: 209218887Sdim case BO_DivAssign: 210218887Sdim case BO_AndAssign: 211218887Sdim case BO_OrAssign: 212218887Sdim case BO_XorAssign: 213218887Sdim case BO_Sub: 214218887Sdim case BO_Div: 215218887Sdim case BO_And: 216218887Sdim case BO_Or: 217218887Sdim case BO_Xor: 218218887Sdim case BO_LOr: 219218887Sdim case BO_LAnd: 220218887Sdim case BO_EQ: 221218887Sdim case BO_NE: 222218887Sdim if (LHSVal != RHSVal || LHSContainsFalsePositive 223218887Sdim || RHSContainsFalsePositive) 224218887Sdim break; 225218887Sdim UpdateAssumption(A, Equal); 226218887Sdim return; 227218887Sdim } 228218887Sdim 229218887Sdim // x op 1 230218887Sdim switch (Op) { 231218887Sdim default: 232218887Sdim break; // We don't care about any other operators. 233218887Sdim 234218887Sdim // Fall through intentional 235218887Sdim case BO_MulAssign: 236218887Sdim case BO_DivAssign: 237218887Sdim case BO_Mul: 238218887Sdim case BO_Div: 239218887Sdim case BO_LOr: 240218887Sdim case BO_LAnd: 241218887Sdim if (!RHSVal.isConstant(1) || RHSContainsFalsePositive) 242218887Sdim break; 243218887Sdim UpdateAssumption(A, RHSis1); 244218887Sdim return; 245218887Sdim } 246218887Sdim 247218887Sdim // 1 op x 248218887Sdim switch (Op) { 249218887Sdim default: 250218887Sdim break; // We don't care about any other operators. 251218887Sdim 252218887Sdim // Fall through intentional 253218887Sdim case BO_MulAssign: 254218887Sdim case BO_Mul: 255218887Sdim case BO_LOr: 256218887Sdim case BO_LAnd: 257218887Sdim if (!LHSVal.isConstant(1) || LHSContainsFalsePositive) 258218887Sdim break; 259218887Sdim UpdateAssumption(A, LHSis1); 260218887Sdim return; 261218887Sdim } 262218887Sdim 263218887Sdim // x op 0 264218887Sdim switch (Op) { 265218887Sdim default: 266218887Sdim break; // We don't care about any other operators. 267218887Sdim 268218887Sdim // Fall through intentional 269218887Sdim case BO_AddAssign: 270218887Sdim case BO_SubAssign: 271218887Sdim case BO_MulAssign: 272218887Sdim case BO_AndAssign: 273218887Sdim case BO_OrAssign: 274218887Sdim case BO_XorAssign: 275218887Sdim case BO_Add: 276218887Sdim case BO_Sub: 277218887Sdim case BO_Mul: 278218887Sdim case BO_And: 279218887Sdim case BO_Or: 280218887Sdim case BO_Xor: 281218887Sdim case BO_Shl: 282218887Sdim case BO_Shr: 283218887Sdim case BO_LOr: 284218887Sdim case BO_LAnd: 285218887Sdim if (!RHSVal.isConstant(0) || RHSContainsFalsePositive) 286218887Sdim break; 287218887Sdim UpdateAssumption(A, RHSis0); 288218887Sdim return; 289218887Sdim } 290218887Sdim 291218887Sdim // 0 op x 292218887Sdim switch (Op) { 293218887Sdim default: 294218887Sdim break; // We don't care about any other operators. 295218887Sdim 296218887Sdim // Fall through intentional 297218887Sdim //case BO_AddAssign: // Common false positive 298218887Sdim case BO_SubAssign: // Check only if unsigned 299218887Sdim case BO_MulAssign: 300218887Sdim case BO_DivAssign: 301218887Sdim case BO_AndAssign: 302218887Sdim //case BO_OrAssign: // Common false positive 303218887Sdim //case BO_XorAssign: // Common false positive 304218887Sdim case BO_ShlAssign: 305218887Sdim case BO_ShrAssign: 306218887Sdim case BO_Add: 307218887Sdim case BO_Sub: 308218887Sdim case BO_Mul: 309218887Sdim case BO_Div: 310218887Sdim case BO_And: 311218887Sdim case BO_Or: 312218887Sdim case BO_Xor: 313218887Sdim case BO_Shl: 314218887Sdim case BO_Shr: 315218887Sdim case BO_LOr: 316218887Sdim case BO_LAnd: 317218887Sdim if (!LHSVal.isConstant(0) || LHSContainsFalsePositive) 318218887Sdim break; 319218887Sdim UpdateAssumption(A, LHSis0); 320218887Sdim return; 321218887Sdim } 322218887Sdim 323218887Sdim // If we get to this point, there has been a valid use of this operation. 324218887Sdim A = Impossible; 325218887Sdim} 326218887Sdim 327218887Sdim// At the post visit stage, the predecessor ExplodedNode will be the 328218887Sdim// BinaryOperator that was just created. We use this hook to collect the 329218887Sdim// ExplodedNode. 330219077Sdimvoid IdempotentOperationChecker::checkPostStmt(const BinaryOperator *B, 331219077Sdim CheckerContext &C) const { 332218887Sdim // Add the ExplodedNode we just visited 333218887Sdim BinaryOperatorData &Data = hash[B]; 334218887Sdim 335249423Sdim const Stmt *predStmt = 336249423Sdim C.getPredecessor()->getLocation().castAs<StmtPoint>().getStmt(); 337249423Sdim 338218887Sdim // Ignore implicit calls to setters. 339221345Sdim if (!isa<BinaryOperator>(predStmt)) 340218887Sdim return; 341221345Sdim 342218887Sdim Data.explodedNodes.Add(C.getPredecessor()); 343218887Sdim} 344218887Sdim 345219077Sdimvoid IdempotentOperationChecker::checkEndAnalysis(ExplodedGraph &G, 346218887Sdim BugReporter &BR, 347219077Sdim ExprEngine &Eng) const { 348239462Sdim if (!BT) 349239462Sdim BT.reset(new BugType("Idempotent operation", "Dead code")); 350239462Sdim 351218887Sdim // Iterate over the hash to see if we have any paths with definite 352218887Sdim // idempotent operations. 353218887Sdim for (AssumptionMap::const_iterator i = hash.begin(); i != hash.end(); ++i) { 354218887Sdim // Unpack the hash contents 355218887Sdim const BinaryOperatorData &Data = i->second; 356218887Sdim const Assumption &A = Data.assumption; 357218887Sdim const ExplodedNodeSet &ES = Data.explodedNodes; 358218887Sdim 359226633Sdim // If there are no nodes accosted with the expression, nothing to report. 360226633Sdim // FIXME: This is possible because the checker does part of processing in 361226633Sdim // checkPreStmt and part in checkPostStmt. 362226633Sdim if (ES.begin() == ES.end()) 363226633Sdim continue; 364226633Sdim 365218887Sdim const BinaryOperator *B = i->first; 366218887Sdim 367218887Sdim if (A == Impossible) 368218887Sdim continue; 369218887Sdim 370218887Sdim // If the analyzer did not finish, check to see if we can still emit this 371218887Sdim // warning 372218887Sdim if (Eng.hasWorkRemaining()) { 373218887Sdim // If we can trace back 374234353Sdim AnalysisDeclContext *AC = (*ES.begin())->getLocationContext() 375234353Sdim ->getAnalysisDeclContext(); 376219077Sdim if (!pathWasCompletelyAnalyzed(AC, 377219077Sdim AC->getCFGStmtMap()->getBlock(B), 378218887Sdim Eng.getCoreEngine())) 379218887Sdim continue; 380218887Sdim } 381218887Sdim 382218887Sdim // Select the error message and SourceRanges to report. 383234353Sdim SmallString<128> buf; 384218887Sdim llvm::raw_svector_ostream os(buf); 385218887Sdim bool LHSRelevant = false, RHSRelevant = false; 386218887Sdim switch (A) { 387218887Sdim case Equal: 388218887Sdim LHSRelevant = true; 389218887Sdim RHSRelevant = true; 390218887Sdim if (B->getOpcode() == BO_Assign) 391218887Sdim os << "Assigned value is always the same as the existing value"; 392218887Sdim else 393218887Sdim os << "Both operands to '" << B->getOpcodeStr() 394218887Sdim << "' always have the same value"; 395218887Sdim break; 396218887Sdim case LHSis1: 397218887Sdim LHSRelevant = true; 398218887Sdim os << "The left operand to '" << B->getOpcodeStr() << "' is always 1"; 399218887Sdim break; 400218887Sdim case RHSis1: 401218887Sdim RHSRelevant = true; 402218887Sdim os << "The right operand to '" << B->getOpcodeStr() << "' is always 1"; 403218887Sdim break; 404218887Sdim case LHSis0: 405218887Sdim LHSRelevant = true; 406218887Sdim os << "The left operand to '" << B->getOpcodeStr() << "' is always 0"; 407218887Sdim break; 408218887Sdim case RHSis0: 409218887Sdim RHSRelevant = true; 410218887Sdim os << "The right operand to '" << B->getOpcodeStr() << "' is always 0"; 411218887Sdim break; 412218887Sdim case Possible: 413218887Sdim llvm_unreachable("Operation was never marked with an assumption"); 414218887Sdim case Impossible: 415218887Sdim llvm_unreachable(0); 416218887Sdim } 417218887Sdim 418218887Sdim // Add a report for each ExplodedNode 419218887Sdim for (ExplodedNodeSet::iterator I = ES.begin(), E = ES.end(); I != E; ++I) { 420226633Sdim BugReport *report = new BugReport(*BT, os.str(), *I); 421218887Sdim 422218887Sdim // Add source ranges and visitor hooks 423218887Sdim if (LHSRelevant) { 424218887Sdim const Expr *LHS = i->first->getLHS(); 425218887Sdim report->addRange(LHS->getSourceRange()); 426249423Sdim FindLastStoreBRVisitor::registerStatementVarDecls(*report, LHS, false); 427218887Sdim } 428218887Sdim if (RHSRelevant) { 429218887Sdim const Expr *RHS = i->first->getRHS(); 430218887Sdim report->addRange(i->first->getRHS()->getSourceRange()); 431249423Sdim FindLastStoreBRVisitor::registerStatementVarDecls(*report, RHS, false); 432218887Sdim } 433218887Sdim 434243830Sdim BR.emitReport(report); 435218887Sdim } 436218887Sdim } 437219077Sdim 438219077Sdim hash.clear(); 439218887Sdim} 440218887Sdim 441218887Sdim// Updates the current assumption given the new assumption 442218887Sdiminline void IdempotentOperationChecker::UpdateAssumption(Assumption &A, 443218887Sdim const Assumption &New) { 444218887Sdim// If the assumption is the same, there is nothing to do 445218887Sdim if (A == New) 446218887Sdim return; 447218887Sdim 448218887Sdim switch (A) { 449218887Sdim // If we don't currently have an assumption, set it 450218887Sdim case Possible: 451218887Sdim A = New; 452218887Sdim return; 453218887Sdim 454218887Sdim // If we have determined that a valid state happened, ignore the new 455218887Sdim // assumption. 456218887Sdim case Impossible: 457218887Sdim return; 458218887Sdim 459218887Sdim // Any other case means that we had a different assumption last time. We don't 460218887Sdim // currently support mixing assumptions for diagnostic reasons, so we set 461218887Sdim // our assumption to be impossible. 462218887Sdim default: 463218887Sdim A = Impossible; 464218887Sdim return; 465218887Sdim } 466218887Sdim} 467218887Sdim 468218887Sdim// Check for a statement where a variable is self assigned to possibly avoid an 469218887Sdim// unused variable warning. 470218887Sdimbool IdempotentOperationChecker::isSelfAssign(const Expr *LHS, const Expr *RHS) { 471218887Sdim LHS = LHS->IgnoreParenCasts(); 472218887Sdim RHS = RHS->IgnoreParenCasts(); 473218887Sdim 474218887Sdim const DeclRefExpr *LHS_DR = dyn_cast<DeclRefExpr>(LHS); 475218887Sdim if (!LHS_DR) 476218887Sdim return false; 477218887Sdim 478218887Sdim const VarDecl *VD = dyn_cast<VarDecl>(LHS_DR->getDecl()); 479218887Sdim if (!VD) 480218887Sdim return false; 481218887Sdim 482218887Sdim const DeclRefExpr *RHS_DR = dyn_cast<DeclRefExpr>(RHS); 483218887Sdim if (!RHS_DR) 484218887Sdim return false; 485218887Sdim 486218887Sdim if (VD != RHS_DR->getDecl()) 487218887Sdim return false; 488218887Sdim 489218887Sdim return true; 490218887Sdim} 491218887Sdim 492218887Sdim// Returns true if the Expr points to a VarDecl that is not read anywhere 493218887Sdim// outside of self-assignments. 494218887Sdimbool IdempotentOperationChecker::isUnused(const Expr *E, 495234353Sdim AnalysisDeclContext *AC) { 496218887Sdim if (!E) 497218887Sdim return false; 498218887Sdim 499218887Sdim const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E->IgnoreParenCasts()); 500218887Sdim if (!DR) 501218887Sdim return false; 502218887Sdim 503218887Sdim const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()); 504218887Sdim if (!VD) 505218887Sdim return false; 506218887Sdim 507218887Sdim if (AC->getPseudoConstantAnalysis()->wasReferenced(VD)) 508218887Sdim return false; 509218887Sdim 510218887Sdim return true; 511218887Sdim} 512218887Sdim 513218887Sdim// Check for self casts truncating/extending a variable 514218887Sdimbool IdempotentOperationChecker::isTruncationExtensionAssignment( 515218887Sdim const Expr *LHS, 516218887Sdim const Expr *RHS) { 517218887Sdim 518218887Sdim const DeclRefExpr *LHS_DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParenCasts()); 519218887Sdim if (!LHS_DR) 520218887Sdim return false; 521218887Sdim 522218887Sdim const VarDecl *VD = dyn_cast<VarDecl>(LHS_DR->getDecl()); 523218887Sdim if (!VD) 524218887Sdim return false; 525218887Sdim 526218887Sdim const DeclRefExpr *RHS_DR = dyn_cast<DeclRefExpr>(RHS->IgnoreParenCasts()); 527218887Sdim if (!RHS_DR) 528218887Sdim return false; 529218887Sdim 530218887Sdim if (VD != RHS_DR->getDecl()) 531218887Sdim return false; 532218887Sdim 533218887Sdim return dyn_cast<DeclRefExpr>(RHS->IgnoreParenLValueCasts()) == NULL; 534218887Sdim} 535218887Sdim 536218887Sdim// Returns false if a path to this block was not completely analyzed, or true 537218887Sdim// otherwise. 538218887Sdimbool 539234353SdimIdempotentOperationChecker::pathWasCompletelyAnalyzed(AnalysisDeclContext *AC, 540218887Sdim const CFGBlock *CB, 541218887Sdim const CoreEngine &CE) { 542218887Sdim 543221345Sdim CFGReverseBlockReachabilityAnalysis *CRA = AC->getCFGReachablityAnalysis(); 544218887Sdim 545218887Sdim // Test for reachability from any aborted blocks to this block 546221345Sdim typedef CoreEngine::BlocksExhausted::const_iterator ExhaustedIterator; 547221345Sdim for (ExhaustedIterator I = CE.blocks_exhausted_begin(), 548221345Sdim E = CE.blocks_exhausted_end(); I != E; ++I) { 549218887Sdim const BlockEdge &BE = I->first; 550218887Sdim 551218887Sdim // The destination block on the BlockEdge is the first block that was not 552218887Sdim // analyzed. If we can reach this block from the aborted block, then this 553218887Sdim // block was not completely analyzed. 554218887Sdim // 555218887Sdim // Also explicitly check if the current block is the destination block. 556218887Sdim // While technically reachable, it means we aborted the analysis on 557218887Sdim // a path that included that block. 558218887Sdim const CFGBlock *destBlock = BE.getDst(); 559218887Sdim if (destBlock == CB || CRA->isReachable(destBlock, CB)) 560218887Sdim return false; 561218887Sdim } 562221345Sdim 563221345Sdim // Test for reachability from blocks we just gave up on. 564221345Sdim typedef CoreEngine::BlocksAborted::const_iterator AbortedIterator; 565221345Sdim for (AbortedIterator I = CE.blocks_aborted_begin(), 566221345Sdim E = CE.blocks_aborted_end(); I != E; ++I) { 567221345Sdim const CFGBlock *destBlock = I->first; 568221345Sdim if (destBlock == CB || CRA->isReachable(destBlock, CB)) 569221345Sdim return false; 570221345Sdim } 571218887Sdim 572218887Sdim // For the items still on the worklist, see if they are in blocks that 573218887Sdim // can eventually reach 'CB'. 574218887Sdim class VisitWL : public WorkList::Visitor { 575218887Sdim const CFGStmtMap *CBM; 576218887Sdim const CFGBlock *TargetBlock; 577221345Sdim CFGReverseBlockReachabilityAnalysis &CRA; 578218887Sdim public: 579218887Sdim VisitWL(const CFGStmtMap *cbm, const CFGBlock *targetBlock, 580221345Sdim CFGReverseBlockReachabilityAnalysis &cra) 581218887Sdim : CBM(cbm), TargetBlock(targetBlock), CRA(cra) {} 582218887Sdim virtual bool visit(const WorkListUnit &U) { 583218887Sdim ProgramPoint P = U.getNode()->getLocation(); 584218887Sdim const CFGBlock *B = 0; 585249423Sdim if (Optional<StmtPoint> SP = P.getAs<StmtPoint>()) { 586218887Sdim B = CBM->getBlock(SP->getStmt()); 587249423Sdim } else if (Optional<BlockEdge> BE = P.getAs<BlockEdge>()) { 588218887Sdim B = BE->getDst(); 589249423Sdim } else if (Optional<BlockEntrance> BEnt = P.getAs<BlockEntrance>()) { 590218887Sdim B = BEnt->getBlock(); 591249423Sdim } else if (Optional<BlockExit> BExit = P.getAs<BlockExit>()) { 592218887Sdim B = BExit->getBlock(); 593218887Sdim } 594218887Sdim if (!B) 595218887Sdim return true; 596218887Sdim 597221345Sdim return B == TargetBlock || CRA.isReachable(B, TargetBlock); 598218887Sdim } 599218887Sdim }; 600219077Sdim VisitWL visitWL(AC->getCFGStmtMap(), CB, *CRA); 601218887Sdim // Were there any items in the worklist that could potentially reach 602218887Sdim // this block? 603218887Sdim if (CE.getWorkList()->visitItemsInWorkList(visitWL)) 604218887Sdim return false; 605218887Sdim 606218887Sdim // Verify that this block is reachable from the entry block 607219077Sdim if (!CRA->isReachable(&AC->getCFG()->getEntry(), CB)) 608218887Sdim return false; 609218887Sdim 610218887Sdim // If we get to this point, there is no connection to the entry block or an 611218887Sdim // aborted block. This path is unreachable and we can report the error. 612218887Sdim return true; 613218887Sdim} 614218887Sdim 615218887Sdim// Recursive function that determines whether an expression contains any element 616218887Sdim// that varies. This could be due to a compile-time constant like sizeof. An 617218887Sdim// expression may also involve a variable that behaves like a constant. The 618218887Sdim// function returns true if the expression varies, and false otherwise. 619218887Sdimbool IdempotentOperationChecker::CanVary(const Expr *Ex, 620234353Sdim AnalysisDeclContext *AC) { 621218887Sdim // Parentheses and casts are irrelevant here 622218887Sdim Ex = Ex->IgnoreParenCasts(); 623218887Sdim 624218887Sdim if (Ex->getLocStart().isMacroID()) 625218887Sdim return false; 626218887Sdim 627218887Sdim switch (Ex->getStmtClass()) { 628218887Sdim // Trivially true cases 629218887Sdim case Stmt::ArraySubscriptExprClass: 630218887Sdim case Stmt::MemberExprClass: 631218887Sdim case Stmt::StmtExprClass: 632218887Sdim case Stmt::CallExprClass: 633218887Sdim case Stmt::VAArgExprClass: 634218887Sdim case Stmt::ShuffleVectorExprClass: 635218887Sdim return true; 636218887Sdim default: 637218887Sdim return true; 638218887Sdim 639218887Sdim // Trivially false cases 640218887Sdim case Stmt::IntegerLiteralClass: 641218887Sdim case Stmt::CharacterLiteralClass: 642218887Sdim case Stmt::FloatingLiteralClass: 643218887Sdim case Stmt::PredefinedExprClass: 644218887Sdim case Stmt::ImaginaryLiteralClass: 645218887Sdim case Stmt::StringLiteralClass: 646218887Sdim case Stmt::OffsetOfExprClass: 647218887Sdim case Stmt::CompoundLiteralExprClass: 648218887Sdim case Stmt::AddrLabelExprClass: 649218887Sdim case Stmt::BinaryTypeTraitExprClass: 650218887Sdim case Stmt::GNUNullExprClass: 651218887Sdim case Stmt::InitListExprClass: 652218887Sdim case Stmt::DesignatedInitExprClass: 653218887Sdim case Stmt::BlockExprClass: 654218887Sdim return false; 655218887Sdim 656218887Sdim // Cases requiring custom logic 657221345Sdim case Stmt::UnaryExprOrTypeTraitExprClass: { 658221345Sdim const UnaryExprOrTypeTraitExpr *SE = 659221345Sdim cast<const UnaryExprOrTypeTraitExpr>(Ex); 660221345Sdim if (SE->getKind() != UETT_SizeOf) 661218887Sdim return false; 662218887Sdim return SE->getTypeOfArgument()->isVariableArrayType(); 663218887Sdim } 664218887Sdim case Stmt::DeclRefExprClass: 665218887Sdim // Check for constants/pseudoconstants 666218887Sdim return !isConstantOrPseudoConstant(cast<DeclRefExpr>(Ex), AC); 667218887Sdim 668218887Sdim // The next cases require recursion for subexpressions 669218887Sdim case Stmt::BinaryOperatorClass: { 670218887Sdim const BinaryOperator *B = cast<const BinaryOperator>(Ex); 671218887Sdim 672218887Sdim // Exclude cases involving pointer arithmetic. These are usually 673218887Sdim // false positives. 674218887Sdim if (B->getOpcode() == BO_Sub || B->getOpcode() == BO_Add) 675218887Sdim if (B->getLHS()->getType()->getAs<PointerType>()) 676218887Sdim return false; 677218887Sdim 678218887Sdim return CanVary(B->getRHS(), AC) 679218887Sdim || CanVary(B->getLHS(), AC); 680218887Sdim } 681263508Sdim case Stmt::UnaryOperatorClass: 682263508Sdim return CanVary(cast<UnaryOperator>(Ex)->getSubExpr(), AC); 683218887Sdim case Stmt::ConditionalOperatorClass: 684218887Sdim case Stmt::BinaryConditionalOperatorClass: 685218887Sdim return CanVary(cast<AbstractConditionalOperator>(Ex)->getCond(), AC); 686218887Sdim } 687218887Sdim} 688218887Sdim 689218887Sdim// Returns true if a DeclRefExpr is or behaves like a constant. 690218887Sdimbool IdempotentOperationChecker::isConstantOrPseudoConstant( 691218887Sdim const DeclRefExpr *DR, 692234353Sdim AnalysisDeclContext *AC) { 693218887Sdim // Check if the type of the Decl is const-qualified 694218887Sdim if (DR->getType().isConstQualified()) 695218887Sdim return true; 696218887Sdim 697218887Sdim // Check for an enum 698218887Sdim if (isa<EnumConstantDecl>(DR->getDecl())) 699218887Sdim return true; 700218887Sdim 701218887Sdim const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl()); 702218887Sdim if (!VD) 703218887Sdim return true; 704218887Sdim 705218887Sdim // Check if the Decl behaves like a constant. This check also takes care of 706218887Sdim // static variables, which can only change between function calls if they are 707218887Sdim // modified in the AST. 708218887Sdim PseudoConstantAnalysis *PCA = AC->getPseudoConstantAnalysis(); 709218887Sdim if (PCA->isPseudoConstant(VD)) 710218887Sdim return true; 711218887Sdim 712218887Sdim return false; 713218887Sdim} 714218887Sdim 715218887Sdim// Recursively find any substatements containing VarDecl's with storage other 716218887Sdim// than local 717218887Sdimbool IdempotentOperationChecker::containsNonLocalVarDecl(const Stmt *S) { 718218887Sdim const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(S); 719218887Sdim 720218887Sdim if (DR) 721218887Sdim if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) 722218887Sdim if (!VD->hasLocalStorage()) 723218887Sdim return true; 724218887Sdim 725218887Sdim for (Stmt::const_child_iterator I = S->child_begin(); I != S->child_end(); 726218887Sdim ++I) 727218887Sdim if (const Stmt *child = *I) 728218887Sdim if (containsNonLocalVarDecl(child)) 729218887Sdim return true; 730218887Sdim 731218887Sdim return false; 732218887Sdim} 733218887Sdim 734218887Sdim 735219077Sdimvoid ento::registerIdempotentOperationChecker(CheckerManager &mgr) { 736219077Sdim mgr.registerChecker<IdempotentOperationChecker>(); 737218887Sdim} 738