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