Consumed.cpp revision 4252598a2e58c3f74027511f535ed327f9b32b77
1//===- Consumed.cpp --------------------------------------------*- 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// A intra-procedural analysis for checking consumed properties. This is based, 11// in part, on research on linear types. 12// 13//===----------------------------------------------------------------------===// 14 15#include "clang/AST/ASTContext.h" 16#include "clang/AST/Attr.h" 17#include "clang/AST/DeclCXX.h" 18#include "clang/AST/ExprCXX.h" 19#include "clang/AST/RecursiveASTVisitor.h" 20#include "clang/AST/StmtVisitor.h" 21#include "clang/AST/StmtCXX.h" 22#include "clang/AST/Type.h" 23#include "clang/Analysis/Analyses/PostOrderCFGView.h" 24#include "clang/Analysis/AnalysisContext.h" 25#include "clang/Analysis/CFG.h" 26#include "clang/Analysis/Analyses/Consumed.h" 27#include "clang/Basic/OperatorKinds.h" 28#include "clang/Basic/SourceLocation.h" 29#include "llvm/ADT/DenseMap.h" 30#include "llvm/ADT/SmallVector.h" 31#include "llvm/Support/Compiler.h" 32#include "llvm/Support/raw_ostream.h" 33 34// TODO: Correctly identify unreachable blocks when chaining boolean operators. 35// TODO: Warn about unreachable code. 36// TODO: Switch to using a bitmap to track unreachable blocks. 37// TODO: Mark variables as Unknown going into while- or for-loops only if they 38// are referenced inside that block. (Deferred) 39// TODO: Handle variable definitions, e.g. bool valid = x.isValid(); 40// if (valid) ...; (Deferred) 41// TODO: Add a method(s) to identify which method calls perform what state 42// transitions. (Deferred) 43// TODO: Take notes on state transitions to provide better warning messages. 44// (Deferred) 45// TODO: Test nested conditionals: A) Checking the same value multiple times, 46// and 2) Checking different values. (Deferred) 47 48using namespace clang; 49using namespace consumed; 50 51// Key method definition 52ConsumedWarningsHandlerBase::~ConsumedWarningsHandlerBase() {} 53 54static ConsumedState invertConsumedUnconsumed(ConsumedState State) { 55 switch (State) { 56 case CS_Unconsumed: 57 return CS_Consumed; 58 case CS_Consumed: 59 return CS_Unconsumed; 60 case CS_None: 61 return CS_None; 62 case CS_Unknown: 63 return CS_Unknown; 64 } 65 llvm_unreachable("invalid enum"); 66} 67 68static bool isKnownState(ConsumedState State) { 69 switch (State) { 70 case CS_Unconsumed: 71 case CS_Consumed: 72 return true; 73 case CS_None: 74 case CS_Unknown: 75 return false; 76 } 77 llvm_unreachable("invalid enum"); 78} 79 80static bool isTestingFunction(const FunctionDecl *FunDecl) { 81 return FunDecl->hasAttr<TestsUnconsumedAttr>(); 82} 83 84static StringRef stateToString(ConsumedState State) { 85 switch (State) { 86 case consumed::CS_None: 87 return "none"; 88 89 case consumed::CS_Unknown: 90 return "unknown"; 91 92 case consumed::CS_Unconsumed: 93 return "unconsumed"; 94 95 case consumed::CS_Consumed: 96 return "consumed"; 97 } 98 llvm_unreachable("invalid enum"); 99} 100 101namespace { 102struct VarTestResult { 103 const VarDecl *Var; 104 ConsumedState TestsFor; 105}; 106} // end anonymous::VarTestResult 107 108namespace clang { 109namespace consumed { 110 111enum EffectiveOp { 112 EO_And, 113 EO_Or 114}; 115 116class PropagationInfo { 117 enum { 118 IT_None, 119 IT_State, 120 IT_Test, 121 IT_BinTest, 122 IT_Var 123 } InfoType; 124 125 struct BinTestTy { 126 const BinaryOperator *Source; 127 EffectiveOp EOp; 128 VarTestResult LTest; 129 VarTestResult RTest; 130 }; 131 132 union { 133 ConsumedState State; 134 VarTestResult Test; 135 const VarDecl *Var; 136 BinTestTy BinTest; 137 }; 138 139public: 140 PropagationInfo() : InfoType(IT_None) {} 141 142 PropagationInfo(const VarTestResult &Test) : InfoType(IT_Test), Test(Test) {} 143 PropagationInfo(const VarDecl *Var, ConsumedState TestsFor) 144 : InfoType(IT_Test) { 145 146 Test.Var = Var; 147 Test.TestsFor = TestsFor; 148 } 149 150 PropagationInfo(const BinaryOperator *Source, EffectiveOp EOp, 151 const VarTestResult <est, const VarTestResult &RTest) 152 : InfoType(IT_BinTest) { 153 154 BinTest.Source = Source; 155 BinTest.EOp = EOp; 156 BinTest.LTest = LTest; 157 BinTest.RTest = RTest; 158 } 159 160 PropagationInfo(const BinaryOperator *Source, EffectiveOp EOp, 161 const VarDecl *LVar, ConsumedState LTestsFor, 162 const VarDecl *RVar, ConsumedState RTestsFor) 163 : InfoType(IT_BinTest) { 164 165 BinTest.Source = Source; 166 BinTest.EOp = EOp; 167 BinTest.LTest.Var = LVar; 168 BinTest.LTest.TestsFor = LTestsFor; 169 BinTest.RTest.Var = RVar; 170 BinTest.RTest.TestsFor = RTestsFor; 171 } 172 173 PropagationInfo(ConsumedState State) : InfoType(IT_State), State(State) {} 174 PropagationInfo(const VarDecl *Var) : InfoType(IT_Var), Var(Var) {} 175 176 const ConsumedState & getState() const { 177 assert(InfoType == IT_State); 178 return State; 179 } 180 181 const VarTestResult & getTest() const { 182 assert(InfoType == IT_Test); 183 return Test; 184 } 185 186 const VarTestResult & getLTest() const { 187 assert(InfoType == IT_BinTest); 188 return BinTest.LTest; 189 } 190 191 const VarTestResult & getRTest() const { 192 assert(InfoType == IT_BinTest); 193 return BinTest.RTest; 194 } 195 196 const VarDecl * getVar() const { 197 assert(InfoType == IT_Var); 198 return Var; 199 } 200 201 EffectiveOp testEffectiveOp() const { 202 assert(InfoType == IT_BinTest); 203 return BinTest.EOp; 204 } 205 206 const BinaryOperator * testSourceNode() const { 207 assert(InfoType == IT_BinTest); 208 return BinTest.Source; 209 } 210 211 bool isValid() const { return InfoType != IT_None; } 212 bool isState() const { return InfoType == IT_State; } 213 bool isTest() const { return InfoType == IT_Test; } 214 bool isBinTest() const { return InfoType == IT_BinTest; } 215 bool isVar() const { return InfoType == IT_Var; } 216 217 PropagationInfo invertTest() const { 218 assert(InfoType == IT_Test || InfoType == IT_BinTest); 219 220 if (InfoType == IT_Test) { 221 return PropagationInfo(Test.Var, invertConsumedUnconsumed(Test.TestsFor)); 222 223 } else if (InfoType == IT_BinTest) { 224 return PropagationInfo(BinTest.Source, 225 BinTest.EOp == EO_And ? EO_Or : EO_And, 226 BinTest.LTest.Var, invertConsumedUnconsumed(BinTest.LTest.TestsFor), 227 BinTest.RTest.Var, invertConsumedUnconsumed(BinTest.RTest.TestsFor)); 228 } else { 229 return PropagationInfo(); 230 } 231 } 232}; 233 234class ConsumedStmtVisitor : public ConstStmtVisitor<ConsumedStmtVisitor> { 235 236 typedef llvm::DenseMap<const Stmt *, PropagationInfo> MapType; 237 typedef std::pair<const Stmt *, PropagationInfo> PairType; 238 typedef MapType::iterator InfoEntry; 239 typedef MapType::const_iterator ConstInfoEntry; 240 241 AnalysisDeclContext &AC; 242 ConsumedAnalyzer &Analyzer; 243 ConsumedStateMap *StateMap; 244 MapType PropagationMap; 245 246 void checkCallability(const PropagationInfo &PInfo, 247 const FunctionDecl *FunDecl, 248 const CallExpr *Call); 249 void forwardInfo(const Stmt *From, const Stmt *To); 250 void handleTestingFunctionCall(const CallExpr *Call, const VarDecl *Var); 251 bool isLikeMoveAssignment(const CXXMethodDecl *MethodDecl); 252 253public: 254 255 void Visit(const Stmt *StmtNode); 256 257 void VisitBinaryOperator(const BinaryOperator *BinOp); 258 void VisitCallExpr(const CallExpr *Call); 259 void VisitCastExpr(const CastExpr *Cast); 260 void VisitCXXConstructExpr(const CXXConstructExpr *Call); 261 void VisitCXXMemberCallExpr(const CXXMemberCallExpr *Call); 262 void VisitCXXOperatorCallExpr(const CXXOperatorCallExpr *Call); 263 void VisitDeclRefExpr(const DeclRefExpr *DeclRef); 264 void VisitDeclStmt(const DeclStmt *DelcS); 265 void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *Temp); 266 void VisitMemberExpr(const MemberExpr *MExpr); 267 void VisitParmVarDecl(const ParmVarDecl *Param); 268 void VisitUnaryOperator(const UnaryOperator *UOp); 269 void VisitVarDecl(const VarDecl *Var); 270 271 ConsumedStmtVisitor(AnalysisDeclContext &AC, ConsumedAnalyzer &Analyzer, 272 ConsumedStateMap *StateMap) 273 : AC(AC), Analyzer(Analyzer), StateMap(StateMap) {} 274 275 PropagationInfo getInfo(const Stmt *StmtNode) const { 276 ConstInfoEntry Entry = PropagationMap.find(StmtNode); 277 278 if (Entry != PropagationMap.end()) 279 return Entry->second; 280 else 281 return PropagationInfo(); 282 } 283 284 void reset(ConsumedStateMap *NewStateMap) { 285 StateMap = NewStateMap; 286 } 287}; 288 289// TODO: When we support CallableWhenConsumed this will have to check for 290// the different attributes and change the behavior bellow. (Deferred) 291void ConsumedStmtVisitor::checkCallability(const PropagationInfo &PInfo, 292 const FunctionDecl *FunDecl, 293 const CallExpr *Call) { 294 295 if (!FunDecl->hasAttr<CallableWhenUnconsumedAttr>()) return; 296 297 if (PInfo.isVar()) { 298 const VarDecl *Var = PInfo.getVar(); 299 300 switch (StateMap->getState(Var)) { 301 case CS_Consumed: 302 Analyzer.WarningsHandler.warnUseWhileConsumed( 303 FunDecl->getNameAsString(), Var->getNameAsString(), 304 Call->getExprLoc()); 305 break; 306 307 case CS_Unknown: 308 Analyzer.WarningsHandler.warnUseInUnknownState( 309 FunDecl->getNameAsString(), Var->getNameAsString(), 310 Call->getExprLoc()); 311 break; 312 313 case CS_None: 314 case CS_Unconsumed: 315 break; 316 } 317 318 } else { 319 switch (PInfo.getState()) { 320 case CS_Consumed: 321 Analyzer.WarningsHandler.warnUseOfTempWhileConsumed( 322 FunDecl->getNameAsString(), Call->getExprLoc()); 323 break; 324 325 case CS_Unknown: 326 Analyzer.WarningsHandler.warnUseOfTempInUnknownState( 327 FunDecl->getNameAsString(), Call->getExprLoc()); 328 break; 329 330 case CS_None: 331 case CS_Unconsumed: 332 break; 333 } 334 } 335} 336 337void ConsumedStmtVisitor::forwardInfo(const Stmt *From, const Stmt *To) { 338 InfoEntry Entry = PropagationMap.find(From); 339 340 if (Entry != PropagationMap.end()) 341 PropagationMap.insert(PairType(To, Entry->second)); 342} 343 344void ConsumedStmtVisitor::handleTestingFunctionCall(const CallExpr *Call, 345 const VarDecl *Var) { 346 347 ConsumedState VarState = StateMap->getState(Var); 348 349 if (VarState != CS_Unknown) { 350 SourceLocation CallLoc = Call->getExprLoc(); 351 352 if (!CallLoc.isMacroID()) 353 Analyzer.WarningsHandler.warnUnnecessaryTest(Var->getNameAsString(), 354 stateToString(VarState), CallLoc); 355 } 356 357 PropagationMap.insert(PairType(Call, PropagationInfo(Var, CS_Unconsumed))); 358} 359 360bool ConsumedStmtVisitor::isLikeMoveAssignment( 361 const CXXMethodDecl *MethodDecl) { 362 363 return MethodDecl->isMoveAssignmentOperator() || 364 (MethodDecl->getOverloadedOperator() == OO_Equal && 365 MethodDecl->getNumParams() == 1 && 366 MethodDecl->getParamDecl(0)->getType()->isRValueReferenceType()); 367} 368 369void ConsumedStmtVisitor::Visit(const Stmt *StmtNode) { 370 371 ConstStmtVisitor<ConsumedStmtVisitor>::Visit(StmtNode); 372 373 for (Stmt::const_child_iterator CI = StmtNode->child_begin(), 374 CE = StmtNode->child_end(); CI != CE; ++CI) { 375 376 PropagationMap.erase(*CI); 377 } 378} 379 380void ConsumedStmtVisitor::VisitBinaryOperator(const BinaryOperator *BinOp) { 381 switch (BinOp->getOpcode()) { 382 case BO_LAnd: 383 case BO_LOr : { 384 InfoEntry LEntry = PropagationMap.find(BinOp->getLHS()), 385 REntry = PropagationMap.find(BinOp->getRHS()); 386 387 VarTestResult LTest, RTest; 388 389 if (LEntry != PropagationMap.end() && LEntry->second.isTest()) { 390 LTest = LEntry->second.getTest(); 391 392 } else { 393 LTest.Var = NULL; 394 LTest.TestsFor = CS_None; 395 } 396 397 if (REntry != PropagationMap.end() && REntry->second.isTest()) { 398 RTest = REntry->second.getTest(); 399 400 } else { 401 RTest.Var = NULL; 402 RTest.TestsFor = CS_None; 403 } 404 405 if (!(LTest.Var == NULL && RTest.Var == NULL)) 406 PropagationMap.insert(PairType(BinOp, PropagationInfo(BinOp, 407 static_cast<EffectiveOp>(BinOp->getOpcode() == BO_LOr), LTest, RTest))); 408 409 break; 410 } 411 412 case BO_PtrMemD: 413 case BO_PtrMemI: 414 forwardInfo(BinOp->getLHS(), BinOp); 415 break; 416 417 default: 418 break; 419 } 420} 421 422void ConsumedStmtVisitor::VisitCallExpr(const CallExpr *Call) { 423 if (const FunctionDecl *FunDecl = 424 dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee())) { 425 426 // Special case for the std::move function. 427 // TODO: Make this more specific. (Deferred) 428 if (FunDecl->getNameAsString() == "move") { 429 InfoEntry Entry = PropagationMap.find(Call->getArg(0)); 430 431 if (Entry != PropagationMap.end()) { 432 PropagationMap.insert(PairType(Call, Entry->second)); 433 } 434 435 return; 436 } 437 438 unsigned Offset = Call->getNumArgs() - FunDecl->getNumParams(); 439 440 for (unsigned Index = Offset; Index < Call->getNumArgs(); ++Index) { 441 QualType ParamType = FunDecl->getParamDecl(Index - Offset)->getType(); 442 443 InfoEntry Entry = PropagationMap.find(Call->getArg(Index)); 444 445 if (Entry == PropagationMap.end() || !Entry->second.isVar()) { 446 continue; 447 } 448 449 PropagationInfo PInfo = Entry->second; 450 451 if (ParamType->isRValueReferenceType() || 452 (ParamType->isLValueReferenceType() && 453 !cast<LValueReferenceType>(*ParamType).isSpelledAsLValue())) { 454 455 StateMap->setState(PInfo.getVar(), consumed::CS_Consumed); 456 457 } else if (!(ParamType.isConstQualified() || 458 ((ParamType->isReferenceType() || 459 ParamType->isPointerType()) && 460 ParamType->getPointeeType().isConstQualified()))) { 461 462 StateMap->setState(PInfo.getVar(), consumed::CS_Unknown); 463 } 464 } 465 } 466} 467 468void ConsumedStmtVisitor::VisitCastExpr(const CastExpr *Cast) { 469 forwardInfo(Cast->getSubExpr(), Cast); 470} 471 472void ConsumedStmtVisitor::VisitCXXConstructExpr(const CXXConstructExpr *Call) { 473 CXXConstructorDecl *Constructor = Call->getConstructor(); 474 475 ASTContext &CurrContext = AC.getASTContext(); 476 QualType ThisType = Constructor->getThisType(CurrContext)->getPointeeType(); 477 478 if (Analyzer.isConsumableType(ThisType)) { 479 if (Constructor->hasAttr<ConsumesAttr>() || 480 Constructor->isDefaultConstructor()) { 481 482 PropagationMap.insert(PairType(Call, 483 PropagationInfo(consumed::CS_Consumed))); 484 485 } else if (Constructor->isMoveConstructor()) { 486 487 PropagationInfo PInfo = 488 PropagationMap.find(Call->getArg(0))->second; 489 490 if (PInfo.isVar()) { 491 const VarDecl* Var = PInfo.getVar(); 492 493 PropagationMap.insert(PairType(Call, 494 PropagationInfo(StateMap->getState(Var)))); 495 496 StateMap->setState(Var, consumed::CS_Consumed); 497 498 } else { 499 PropagationMap.insert(PairType(Call, PInfo)); 500 } 501 502 } else if (Constructor->isCopyConstructor()) { 503 MapType::iterator Entry = PropagationMap.find(Call->getArg(0)); 504 505 if (Entry != PropagationMap.end()) 506 PropagationMap.insert(PairType(Call, Entry->second)); 507 508 } else { 509 PropagationMap.insert(PairType(Call, 510 PropagationInfo(consumed::CS_Unconsumed))); 511 } 512 } 513} 514 515void ConsumedStmtVisitor::VisitCXXMemberCallExpr( 516 const CXXMemberCallExpr *Call) { 517 518 VisitCallExpr(Call); 519 520 InfoEntry Entry = PropagationMap.find(Call->getCallee()->IgnoreParens()); 521 522 if (Entry != PropagationMap.end()) { 523 PropagationInfo PInfo = Entry->second; 524 const CXXMethodDecl *MethodDecl = Call->getMethodDecl(); 525 526 checkCallability(PInfo, MethodDecl, Call); 527 528 if (PInfo.isVar()) { 529 if (isTestingFunction(MethodDecl)) 530 handleTestingFunctionCall(Call, PInfo.getVar()); 531 else if (MethodDecl->hasAttr<ConsumesAttr>()) 532 StateMap->setState(PInfo.getVar(), consumed::CS_Consumed); 533 } 534 } 535} 536 537void ConsumedStmtVisitor::VisitCXXOperatorCallExpr( 538 const CXXOperatorCallExpr *Call) { 539 540 const FunctionDecl *FunDecl = 541 dyn_cast_or_null<FunctionDecl>(Call->getDirectCallee()); 542 543 if (!FunDecl) return; 544 545 if (isa<CXXMethodDecl>(FunDecl) && 546 isLikeMoveAssignment(cast<CXXMethodDecl>(FunDecl))) { 547 548 InfoEntry LEntry = PropagationMap.find(Call->getArg(0)); 549 InfoEntry REntry = PropagationMap.find(Call->getArg(1)); 550 551 PropagationInfo LPInfo, RPInfo; 552 553 if (LEntry != PropagationMap.end() && 554 REntry != PropagationMap.end()) { 555 556 LPInfo = LEntry->second; 557 RPInfo = REntry->second; 558 559 if (LPInfo.isVar() && RPInfo.isVar()) { 560 StateMap->setState(LPInfo.getVar(), 561 StateMap->getState(RPInfo.getVar())); 562 563 StateMap->setState(RPInfo.getVar(), consumed::CS_Consumed); 564 565 PropagationMap.insert(PairType(Call, LPInfo)); 566 567 } else if (LPInfo.isVar() && !RPInfo.isVar()) { 568 StateMap->setState(LPInfo.getVar(), RPInfo.getState()); 569 570 PropagationMap.insert(PairType(Call, LPInfo)); 571 572 } else if (!LPInfo.isVar() && RPInfo.isVar()) { 573 PropagationMap.insert(PairType(Call, 574 PropagationInfo(StateMap->getState(RPInfo.getVar())))); 575 576 StateMap->setState(RPInfo.getVar(), consumed::CS_Consumed); 577 578 } else { 579 PropagationMap.insert(PairType(Call, RPInfo)); 580 } 581 582 } else if (LEntry != PropagationMap.end() && 583 REntry == PropagationMap.end()) { 584 585 LPInfo = LEntry->second; 586 587 if (LPInfo.isVar()) { 588 StateMap->setState(LPInfo.getVar(), consumed::CS_Unknown); 589 590 PropagationMap.insert(PairType(Call, LPInfo)); 591 592 } else { 593 PropagationMap.insert(PairType(Call, 594 PropagationInfo(consumed::CS_Unknown))); 595 } 596 597 } else if (LEntry == PropagationMap.end() && 598 REntry != PropagationMap.end()) { 599 600 RPInfo = REntry->second; 601 602 if (RPInfo.isVar()) { 603 const VarDecl *Var = RPInfo.getVar(); 604 605 PropagationMap.insert(PairType(Call, 606 PropagationInfo(StateMap->getState(Var)))); 607 608 StateMap->setState(Var, consumed::CS_Consumed); 609 610 } else { 611 PropagationMap.insert(PairType(Call, RPInfo)); 612 } 613 } 614 615 } else { 616 617 VisitCallExpr(Call); 618 619 InfoEntry Entry = PropagationMap.find(Call->getArg(0)); 620 621 if (Entry != PropagationMap.end()) { 622 PropagationInfo PInfo = Entry->second; 623 624 checkCallability(PInfo, FunDecl, Call); 625 626 if (PInfo.isVar()) { 627 if (isTestingFunction(FunDecl)) 628 handleTestingFunctionCall(Call, PInfo.getVar()); 629 else if (FunDecl->hasAttr<ConsumesAttr>()) 630 StateMap->setState(PInfo.getVar(), consumed::CS_Consumed); 631 } 632 } 633 } 634} 635 636void ConsumedStmtVisitor::VisitDeclRefExpr(const DeclRefExpr *DeclRef) { 637 if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclRef->getDecl())) 638 if (StateMap->getState(Var) != consumed::CS_None) 639 PropagationMap.insert(PairType(DeclRef, PropagationInfo(Var))); 640} 641 642void ConsumedStmtVisitor::VisitDeclStmt(const DeclStmt *DeclS) { 643 for (DeclStmt::const_decl_iterator DI = DeclS->decl_begin(), 644 DE = DeclS->decl_end(); DI != DE; ++DI) { 645 646 if (isa<VarDecl>(*DI)) VisitVarDecl(cast<VarDecl>(*DI)); 647 } 648 649 if (DeclS->isSingleDecl()) 650 if (const VarDecl *Var = dyn_cast_or_null<VarDecl>(DeclS->getSingleDecl())) 651 PropagationMap.insert(PairType(DeclS, PropagationInfo(Var))); 652} 653 654void ConsumedStmtVisitor::VisitMaterializeTemporaryExpr( 655 const MaterializeTemporaryExpr *Temp) { 656 657 InfoEntry Entry = PropagationMap.find(Temp->GetTemporaryExpr()); 658 659 if (Entry != PropagationMap.end()) 660 PropagationMap.insert(PairType(Temp, Entry->second)); 661} 662 663void ConsumedStmtVisitor::VisitMemberExpr(const MemberExpr *MExpr) { 664 forwardInfo(MExpr->getBase(), MExpr); 665} 666 667 668void ConsumedStmtVisitor::VisitParmVarDecl(const ParmVarDecl *Param) { 669 if (Analyzer.isConsumableType(Param->getType())) 670 StateMap->setState(Param, consumed::CS_Unknown); 671} 672 673void ConsumedStmtVisitor::VisitUnaryOperator(const UnaryOperator *UOp) { 674 InfoEntry Entry = PropagationMap.find(UOp->getSubExpr()->IgnoreParens()); 675 if (Entry == PropagationMap.end()) return; 676 677 switch (UOp->getOpcode()) { 678 case UO_AddrOf: 679 PropagationMap.insert(PairType(UOp, Entry->second)); 680 break; 681 682 case UO_LNot: 683 if (Entry->second.isTest() || Entry->second.isBinTest()) 684 PropagationMap.insert(PairType(UOp, Entry->second.invertTest())); 685 break; 686 687 default: 688 break; 689 } 690} 691 692void ConsumedStmtVisitor::VisitVarDecl(const VarDecl *Var) { 693 if (Analyzer.isConsumableType(Var->getType())) { 694 if (Var->hasInit()) { 695 PropagationInfo PInfo = 696 PropagationMap.find(Var->getInit())->second; 697 698 StateMap->setState(Var, PInfo.isVar() ? 699 StateMap->getState(PInfo.getVar()) : PInfo.getState()); 700 701 } else { 702 StateMap->setState(Var, consumed::CS_Unknown); 703 } 704 } 705} 706}} // end clang::consumed::ConsumedStmtVisitor 707 708namespace clang { 709namespace consumed { 710 711void splitVarStateForIf(const IfStmt * IfNode, const VarTestResult &Test, 712 ConsumedStateMap *ThenStates, 713 ConsumedStateMap *ElseStates) { 714 715 ConsumedState VarState = ThenStates->getState(Test.Var); 716 717 if (VarState == CS_Unknown) { 718 ThenStates->setState(Test.Var, Test.TestsFor); 719 if (ElseStates) 720 ElseStates->setState(Test.Var, invertConsumedUnconsumed(Test.TestsFor)); 721 722 } else if (VarState == invertConsumedUnconsumed(Test.TestsFor)) { 723 ThenStates->markUnreachable(); 724 725 } else if (VarState == Test.TestsFor && ElseStates) { 726 ElseStates->markUnreachable(); 727 } 728} 729 730void splitVarStateForIfBinOp(const PropagationInfo &PInfo, 731 ConsumedStateMap *ThenStates, ConsumedStateMap *ElseStates) { 732 733 const VarTestResult <est = PInfo.getLTest(), 734 &RTest = PInfo.getRTest(); 735 736 ConsumedState LState = LTest.Var ? ThenStates->getState(LTest.Var) : CS_None, 737 RState = RTest.Var ? ThenStates->getState(RTest.Var) : CS_None; 738 739 if (LTest.Var) { 740 if (PInfo.testEffectiveOp() == EO_And) { 741 if (LState == CS_Unknown) { 742 ThenStates->setState(LTest.Var, LTest.TestsFor); 743 744 } else if (LState == invertConsumedUnconsumed(LTest.TestsFor)) { 745 ThenStates->markUnreachable(); 746 747 } else if (LState == LTest.TestsFor && isKnownState(RState)) { 748 if (RState == RTest.TestsFor) { 749 if (ElseStates) 750 ElseStates->markUnreachable(); 751 } else { 752 ThenStates->markUnreachable(); 753 } 754 } 755 756 } else { 757 if (LState == CS_Unknown && ElseStates) { 758 ElseStates->setState(LTest.Var, 759 invertConsumedUnconsumed(LTest.TestsFor)); 760 761 } else if (LState == LTest.TestsFor && ElseStates) { 762 ElseStates->markUnreachable(); 763 764 } else if (LState == invertConsumedUnconsumed(LTest.TestsFor) && 765 isKnownState(RState)) { 766 767 if (RState == RTest.TestsFor) { 768 if (ElseStates) 769 ElseStates->markUnreachable(); 770 } else { 771 ThenStates->markUnreachable(); 772 } 773 } 774 } 775 } 776 777 if (RTest.Var) { 778 if (PInfo.testEffectiveOp() == EO_And) { 779 if (RState == CS_Unknown) 780 ThenStates->setState(RTest.Var, RTest.TestsFor); 781 else if (RState == invertConsumedUnconsumed(RTest.TestsFor)) 782 ThenStates->markUnreachable(); 783 784 } else if (ElseStates) { 785 if (RState == CS_Unknown) 786 ElseStates->setState(RTest.Var, 787 invertConsumedUnconsumed(RTest.TestsFor)); 788 else if (RState == RTest.TestsFor) 789 ElseStates->markUnreachable(); 790 } 791 } 792} 793 794void ConsumedBlockInfo::addInfo(const CFGBlock *Block, 795 ConsumedStateMap *StateMap, 796 bool &AlreadyOwned) { 797 798 if (VisitedBlocks.alreadySet(Block)) return; 799 800 ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()]; 801 802 if (Entry) { 803 Entry->intersect(StateMap); 804 805 } else if (AlreadyOwned) { 806 StateMapsArray[Block->getBlockID()] = new ConsumedStateMap(*StateMap); 807 808 } else { 809 StateMapsArray[Block->getBlockID()] = StateMap; 810 AlreadyOwned = true; 811 } 812} 813 814void ConsumedBlockInfo::addInfo(const CFGBlock *Block, 815 ConsumedStateMap *StateMap) { 816 817 if (VisitedBlocks.alreadySet(Block)) { 818 delete StateMap; 819 return; 820 } 821 822 ConsumedStateMap *Entry = StateMapsArray[Block->getBlockID()]; 823 824 if (Entry) { 825 Entry->intersect(StateMap); 826 delete StateMap; 827 828 } else { 829 StateMapsArray[Block->getBlockID()] = StateMap; 830 } 831} 832 833ConsumedStateMap* ConsumedBlockInfo::getInfo(const CFGBlock *Block) { 834 return StateMapsArray[Block->getBlockID()]; 835} 836 837void ConsumedBlockInfo::markVisited(const CFGBlock *Block) { 838 VisitedBlocks.insert(Block); 839} 840 841ConsumedState ConsumedStateMap::getState(const VarDecl *Var) { 842 MapType::const_iterator Entry = Map.find(Var); 843 844 if (Entry != Map.end()) { 845 return Entry->second; 846 847 } else { 848 return CS_None; 849 } 850} 851 852void ConsumedStateMap::intersect(const ConsumedStateMap *Other) { 853 ConsumedState LocalState; 854 855 if (this->From && this->From == Other->From && !Other->Reachable) { 856 this->markUnreachable(); 857 return; 858 } 859 860 for (MapType::const_iterator DMI = Other->Map.begin(), 861 DME = Other->Map.end(); DMI != DME; ++DMI) { 862 863 LocalState = this->getState(DMI->first); 864 865 if (LocalState == CS_None) 866 continue; 867 868 if (LocalState != DMI->second) 869 Map[DMI->first] = CS_Unknown; 870 } 871} 872 873void ConsumedStateMap::markUnreachable() { 874 this->Reachable = false; 875 Map.clear(); 876} 877 878void ConsumedStateMap::makeUnknown() { 879 for (MapType::const_iterator DMI = Map.begin(), DME = Map.end(); DMI != DME; 880 ++DMI) { 881 882 Map[DMI->first] = CS_Unknown; 883 } 884} 885 886void ConsumedStateMap::setState(const VarDecl *Var, ConsumedState State) { 887 Map[Var] = State; 888} 889 890void ConsumedStateMap::remove(const VarDecl *Var) { 891 Map.erase(Var); 892} 893 894bool ConsumedAnalyzer::isConsumableType(QualType Type) { 895 const CXXRecordDecl *RD = 896 dyn_cast_or_null<CXXRecordDecl>(Type->getAsCXXRecordDecl()); 897 898 if (!RD) return false; 899 900 std::pair<CacheMapType::iterator, bool> Entry = 901 ConsumableTypeCache.insert(std::make_pair(RD, false)); 902 903 if (Entry.second) 904 Entry.first->second = hasConsumableAttributes(RD); 905 906 return Entry.first->second; 907} 908 909// TODO: Walk the base classes to see if any of them are unique types. 910// (Deferred) 911bool ConsumedAnalyzer::hasConsumableAttributes(const CXXRecordDecl *RD) { 912 for (CXXRecordDecl::method_iterator MI = RD->method_begin(), 913 ME = RD->method_end(); MI != ME; ++MI) { 914 915 for (Decl::attr_iterator AI = (*MI)->attr_begin(), AE = (*MI)->attr_end(); 916 AI != AE; ++AI) { 917 918 switch ((*AI)->getKind()) { 919 case attr::CallableWhenUnconsumed: 920 case attr::TestsUnconsumed: 921 return true; 922 923 default: 924 break; 925 } 926 } 927 } 928 929 return false; 930} 931 932bool ConsumedAnalyzer::splitState(const CFGBlock *CurrBlock, 933 const ConsumedStmtVisitor &Visitor) { 934 935 ConsumedStateMap *FalseStates = new ConsumedStateMap(*CurrStates); 936 PropagationInfo PInfo; 937 938 if (const IfStmt *IfNode = 939 dyn_cast_or_null<IfStmt>(CurrBlock->getTerminator().getStmt())) { 940 941 bool HasElse = IfNode->getElse() != NULL; 942 const Stmt *Cond = IfNode->getCond(); 943 944 PInfo = Visitor.getInfo(Cond); 945 if (!PInfo.isValid() && isa<BinaryOperator>(Cond)) 946 PInfo = Visitor.getInfo(cast<BinaryOperator>(Cond)->getRHS()); 947 948 if (PInfo.isTest()) { 949 CurrStates->setSource(Cond); 950 FalseStates->setSource(Cond); 951 952 splitVarStateForIf(IfNode, PInfo.getTest(), CurrStates, 953 HasElse ? FalseStates : NULL); 954 955 } else if (PInfo.isBinTest()) { 956 CurrStates->setSource(PInfo.testSourceNode()); 957 FalseStates->setSource(PInfo.testSourceNode()); 958 959 splitVarStateForIfBinOp(PInfo, CurrStates, HasElse ? FalseStates : NULL); 960 961 } else { 962 delete FalseStates; 963 return false; 964 } 965 966 } else if (const BinaryOperator *BinOp = 967 dyn_cast_or_null<BinaryOperator>(CurrBlock->getTerminator().getStmt())) { 968 969 PInfo = Visitor.getInfo(BinOp->getLHS()); 970 if (!PInfo.isTest()) { 971 if ((BinOp = dyn_cast_or_null<BinaryOperator>(BinOp->getLHS()))) { 972 PInfo = Visitor.getInfo(BinOp->getRHS()); 973 974 if (!PInfo.isTest()) { 975 delete FalseStates; 976 return false; 977 } 978 979 } else { 980 delete FalseStates; 981 return false; 982 } 983 } 984 985 CurrStates->setSource(BinOp); 986 FalseStates->setSource(BinOp); 987 988 const VarTestResult &Test = PInfo.getTest(); 989 ConsumedState VarState = CurrStates->getState(Test.Var); 990 991 if (BinOp->getOpcode() == BO_LAnd) { 992 if (VarState == CS_Unknown) 993 CurrStates->setState(Test.Var, Test.TestsFor); 994 else if (VarState == invertConsumedUnconsumed(Test.TestsFor)) 995 CurrStates->markUnreachable(); 996 997 } else if (BinOp->getOpcode() == BO_LOr) { 998 if (VarState == CS_Unknown) 999 FalseStates->setState(Test.Var, 1000 invertConsumedUnconsumed(Test.TestsFor)); 1001 else if (VarState == Test.TestsFor) 1002 FalseStates->markUnreachable(); 1003 } 1004 1005 } else { 1006 delete FalseStates; 1007 return false; 1008 } 1009 1010 CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(); 1011 1012 if (*SI) 1013 BlockInfo.addInfo(*SI, CurrStates); 1014 else 1015 delete CurrStates; 1016 1017 if (*++SI) 1018 BlockInfo.addInfo(*SI, FalseStates); 1019 else 1020 delete FalseStates; 1021 1022 CurrStates = NULL; 1023 return true; 1024} 1025 1026void ConsumedAnalyzer::run(AnalysisDeclContext &AC) { 1027 const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(AC.getDecl()); 1028 1029 if (!D) return; 1030 1031 BlockInfo = ConsumedBlockInfo(AC.getCFG()); 1032 1033 PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>(); 1034 1035 CurrStates = new ConsumedStateMap(); 1036 ConsumedStmtVisitor Visitor(AC, *this, CurrStates); 1037 1038 // Add all trackable parameters to the state map. 1039 for (FunctionDecl::param_const_iterator PI = D->param_begin(), 1040 PE = D->param_end(); PI != PE; ++PI) { 1041 Visitor.VisitParmVarDecl(*PI); 1042 } 1043 1044 // Visit all of the function's basic blocks. 1045 for (PostOrderCFGView::iterator I = SortedGraph->begin(), 1046 E = SortedGraph->end(); I != E; ++I) { 1047 1048 const CFGBlock *CurrBlock = *I; 1049 BlockInfo.markVisited(CurrBlock); 1050 1051 if (CurrStates == NULL) 1052 CurrStates = BlockInfo.getInfo(CurrBlock); 1053 1054 if (!CurrStates) { 1055 continue; 1056 1057 } else if (!CurrStates->isReachable()) { 1058 delete CurrStates; 1059 CurrStates = NULL; 1060 continue; 1061 } 1062 1063 Visitor.reset(CurrStates); 1064 1065 // Visit all of the basic block's statements. 1066 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 1067 BE = CurrBlock->end(); BI != BE; ++BI) { 1068 1069 switch (BI->getKind()) { 1070 case CFGElement::Statement: 1071 Visitor.Visit(BI->castAs<CFGStmt>().getStmt()); 1072 break; 1073 case CFGElement::AutomaticObjectDtor: 1074 CurrStates->remove(BI->castAs<CFGAutomaticObjDtor>().getVarDecl()); 1075 default: 1076 break; 1077 } 1078 } 1079 1080 // TODO: Handle other forms of branching with precision, including while- 1081 // and for-loops. (Deferred) 1082 if (!splitState(CurrBlock, Visitor)) { 1083 CurrStates->setSource(NULL); 1084 1085 if (CurrBlock->succ_size() > 1) { 1086 CurrStates->makeUnknown(); 1087 1088 bool OwnershipTaken = false; 1089 1090 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 1091 SE = CurrBlock->succ_end(); SI != SE; ++SI) { 1092 1093 if (*SI) BlockInfo.addInfo(*SI, CurrStates, OwnershipTaken); 1094 } 1095 1096 if (!OwnershipTaken) 1097 delete CurrStates; 1098 1099 CurrStates = NULL; 1100 1101 } else if (CurrBlock->succ_size() == 1 && 1102 (*CurrBlock->succ_begin())->pred_size() > 1) { 1103 1104 BlockInfo.addInfo(*CurrBlock->succ_begin(), CurrStates); 1105 CurrStates = NULL; 1106 } 1107 } 1108 } // End of block iterator. 1109 1110 // Delete the last existing state map. 1111 delete CurrStates; 1112 1113 WarningsHandler.emitDiagnostics(); 1114} 1115}} // end namespace clang::consumed 1116