CFG.cpp revision 3fa1e4b27300a4ea4cf273182d4b6427ef87f3f8
1//===--- CFG.cpp - Classes for representing and building CFGs----*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the CFG and CFGBuilder classes for representing and 11// building Control-Flow Graphs (CFGs) from ASTs. 12// 13//===----------------------------------------------------------------------===// 14 15#include "clang/Analysis/Support/SaveAndRestore.h" 16#include "clang/Analysis/CFG.h" 17#include "clang/AST/StmtVisitor.h" 18#include "clang/AST/PrettyPrinter.h" 19#include "llvm/Support/GraphWriter.h" 20#include "llvm/Support/Allocator.h" 21#include "llvm/Support/Format.h" 22#include "llvm/ADT/DenseMap.h" 23#include "llvm/ADT/SmallPtrSet.h" 24#include "llvm/ADT/OwningPtr.h" 25 26using namespace clang; 27 28namespace { 29 30static SourceLocation GetEndLoc(Decl* D) { 31 if (VarDecl* VD = dyn_cast<VarDecl>(D)) 32 if (Expr* Ex = VD->getInit()) 33 return Ex->getSourceRange().getEnd(); 34 35 return D->getLocation(); 36} 37 38class AddStmtChoice { 39public: 40 enum Kind { NotAlwaysAdd = 0, AlwaysAdd, AlwaysAddAsLValue }; 41public: 42 AddStmtChoice(Kind kind) : k(kind) {} 43 bool alwaysAdd() const { return k != NotAlwaysAdd; } 44 bool asLValue() const { return k == AlwaysAddAsLValue; } 45private: 46 Kind k; 47}; 48 49/// CFGBuilder - This class implements CFG construction from an AST. 50/// The builder is stateful: an instance of the builder should be used to only 51/// construct a single CFG. 52/// 53/// Example usage: 54/// 55/// CFGBuilder builder; 56/// CFG* cfg = builder.BuildAST(stmt1); 57/// 58/// CFG construction is done via a recursive walk of an AST. We actually parse 59/// the AST in reverse order so that the successor of a basic block is 60/// constructed prior to its predecessor. This allows us to nicely capture 61/// implicit fall-throughs without extra basic blocks. 62/// 63class CFGBuilder { 64 ASTContext *Context; 65 llvm::OwningPtr<CFG> cfg; 66 67 CFGBlock* Block; 68 CFGBlock* Succ; 69 CFGBlock* ContinueTargetBlock; 70 CFGBlock* BreakTargetBlock; 71 CFGBlock* SwitchTerminatedBlock; 72 CFGBlock* DefaultCaseBlock; 73 CFGBlock* TryTerminatedBlock; 74 75 // LabelMap records the mapping from Label expressions to their blocks. 76 typedef llvm::DenseMap<LabelStmt*,CFGBlock*> LabelMapTy; 77 LabelMapTy LabelMap; 78 79 // A list of blocks that end with a "goto" that must be backpatched to their 80 // resolved targets upon completion of CFG construction. 81 typedef std::vector<CFGBlock*> BackpatchBlocksTy; 82 BackpatchBlocksTy BackpatchBlocks; 83 84 // A list of labels whose address has been taken (for indirect gotos). 85 typedef llvm::SmallPtrSet<LabelStmt*,5> LabelSetTy; 86 LabelSetTy AddressTakenLabels; 87 88public: 89 explicit CFGBuilder() : cfg(new CFG()), // crew a new CFG 90 Block(NULL), Succ(NULL), 91 ContinueTargetBlock(NULL), BreakTargetBlock(NULL), 92 SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL), 93 TryTerminatedBlock(NULL) {} 94 95 // buildCFG - Used by external clients to construct the CFG. 96 CFG* buildCFG(Stmt *Statement, ASTContext *C); 97 98private: 99 // Visitors to walk an AST and construct the CFG. 100 CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc); 101 CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc); 102 CFGBlock *VisitBlockExpr(BlockExpr* E, AddStmtChoice asc); 103 CFGBlock *VisitBreakStmt(BreakStmt *B); 104 CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc); 105 CFGBlock *VisitCaseStmt(CaseStmt *C); 106 CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc); 107 CFGBlock *VisitCompoundStmt(CompoundStmt *C); 108 CFGBlock *VisitConditionalOperator(ConditionalOperator *C, 109 AddStmtChoice asc); 110 CFGBlock *VisitContinueStmt(ContinueStmt *C); 111 CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S); 112 CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T); 113 CFGBlock *VisitCXXTryStmt(CXXTryStmt *S); 114 CFGBlock *VisitDeclStmt(DeclStmt *DS); 115 CFGBlock *VisitDeclSubExpr(Decl* D); 116 CFGBlock *VisitDefaultStmt(DefaultStmt *D); 117 CFGBlock *VisitDoStmt(DoStmt *D); 118 CFGBlock *VisitForStmt(ForStmt *F); 119 CFGBlock *VisitGotoStmt(GotoStmt* G); 120 CFGBlock *VisitIfStmt(IfStmt *I); 121 CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I); 122 CFGBlock *VisitLabelStmt(LabelStmt *L); 123 CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S); 124 CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S); 125 CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S); 126 CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S); 127 CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S); 128 CFGBlock *VisitReturnStmt(ReturnStmt* R); 129 CFGBlock *VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, AddStmtChoice asc); 130 CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc); 131 CFGBlock *VisitSwitchStmt(SwitchStmt *S); 132 CFGBlock *VisitWhileStmt(WhileStmt *W); 133 134 CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd); 135 CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc); 136 CFGBlock *VisitChildren(Stmt* S); 137 138 // NYS == Not Yet Supported 139 CFGBlock* NYS() { 140 badCFG = true; 141 return Block; 142 } 143 144 void autoCreateBlock() { if (!Block) Block = createBlock(); } 145 CFGBlock *createBlock(bool add_successor = true); 146 bool FinishBlock(CFGBlock* B); 147 CFGBlock *addStmt(Stmt *S, AddStmtChoice asc = AddStmtChoice::AlwaysAdd) { 148 return Visit(S, asc); 149 } 150 151 void AppendStmt(CFGBlock *B, Stmt *S, 152 AddStmtChoice asc = AddStmtChoice::AlwaysAdd) { 153 B->appendStmt(S, cfg->getBumpVectorContext(), asc.asLValue()); 154 } 155 156 void AddSuccessor(CFGBlock *B, CFGBlock *S) { 157 B->addSuccessor(S, cfg->getBumpVectorContext()); 158 } 159 160 /// TryResult - a class representing a variant over the values 161 /// 'true', 'false', or 'unknown'. This is returned by TryEvaluateBool, 162 /// and is used by the CFGBuilder to decide if a branch condition 163 /// can be decided up front during CFG construction. 164 class TryResult { 165 int X; 166 public: 167 TryResult(bool b) : X(b ? 1 : 0) {} 168 TryResult() : X(-1) {} 169 170 bool isTrue() const { return X == 1; } 171 bool isFalse() const { return X == 0; } 172 bool isKnown() const { return X >= 0; } 173 void negate() { 174 assert(isKnown()); 175 X ^= 0x1; 176 } 177 }; 178 179 /// TryEvaluateBool - Try and evaluate the Stmt and return 0 or 1 180 /// if we can evaluate to a known value, otherwise return -1. 181 TryResult TryEvaluateBool(Expr *S) { 182 Expr::EvalResult Result; 183 if (!S->isTypeDependent() && !S->isValueDependent() && 184 S->Evaluate(Result, *Context) && Result.Val.isInt()) 185 return Result.Val.getInt().getBoolValue(); 186 187 return TryResult(); 188 } 189 190 bool badCFG; 191}; 192 193// FIXME: Add support for dependent-sized array types in C++? 194// Does it even make sense to build a CFG for an uninstantiated template? 195static VariableArrayType* FindVA(Type* t) { 196 while (ArrayType* vt = dyn_cast<ArrayType>(t)) { 197 if (VariableArrayType* vat = dyn_cast<VariableArrayType>(vt)) 198 if (vat->getSizeExpr()) 199 return vat; 200 201 t = vt->getElementType().getTypePtr(); 202 } 203 204 return 0; 205} 206 207/// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an 208/// arbitrary statement. Examples include a single expression or a function 209/// body (compound statement). The ownership of the returned CFG is 210/// transferred to the caller. If CFG construction fails, this method returns 211/// NULL. 212CFG* CFGBuilder::buildCFG(Stmt* Statement, ASTContext* C) { 213 Context = C; 214 assert(cfg.get()); 215 if (!Statement) 216 return NULL; 217 218 badCFG = false; 219 220 // Create an empty block that will serve as the exit block for the CFG. Since 221 // this is the first block added to the CFG, it will be implicitly registered 222 // as the exit block. 223 Succ = createBlock(); 224 assert(Succ == &cfg->getExit()); 225 Block = NULL; // the EXIT block is empty. Create all other blocks lazily. 226 227 // Visit the statements and create the CFG. 228 CFGBlock* B = addStmt(Statement); 229 if (!B) 230 B = Succ; 231 232 if (B) { 233 // Finalize the last constructed block. This usually involves reversing the 234 // order of the statements in the block. 235 if (Block) FinishBlock(B); 236 237 // Backpatch the gotos whose label -> block mappings we didn't know when we 238 // encountered them. 239 for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(), 240 E = BackpatchBlocks.end(); I != E; ++I ) { 241 242 CFGBlock* B = *I; 243 GotoStmt* G = cast<GotoStmt>(B->getTerminator()); 244 LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); 245 246 // If there is no target for the goto, then we are looking at an 247 // incomplete AST. Handle this by not registering a successor. 248 if (LI == LabelMap.end()) continue; 249 250 AddSuccessor(B, LI->second); 251 } 252 253 // Add successors to the Indirect Goto Dispatch block (if we have one). 254 if (CFGBlock* B = cfg->getIndirectGotoBlock()) 255 for (LabelSetTy::iterator I = AddressTakenLabels.begin(), 256 E = AddressTakenLabels.end(); I != E; ++I ) { 257 258 // Lookup the target block. 259 LabelMapTy::iterator LI = LabelMap.find(*I); 260 261 // If there is no target block that contains label, then we are looking 262 // at an incomplete AST. Handle this by not registering a successor. 263 if (LI == LabelMap.end()) continue; 264 265 AddSuccessor(B, LI->second); 266 } 267 268 Succ = B; 269 } 270 271 // Create an empty entry block that has no predecessors. 272 cfg->setEntry(createBlock()); 273 274 return badCFG ? NULL : cfg.take(); 275} 276 277/// createBlock - Used to lazily create blocks that are connected 278/// to the current (global) succcessor. 279CFGBlock* CFGBuilder::createBlock(bool add_successor) { 280 CFGBlock* B = cfg->createBlock(); 281 if (add_successor && Succ) 282 AddSuccessor(B, Succ); 283 return B; 284} 285 286/// FinishBlock - "Finalize" the block by checking if we have a bad CFG. 287bool CFGBuilder::FinishBlock(CFGBlock* B) { 288 if (badCFG) 289 return false; 290 291 assert(B); 292 return true; 293} 294 295/// Visit - Walk the subtree of a statement and add extra 296/// blocks for ternary operators, &&, and ||. We also process "," and 297/// DeclStmts (which may contain nested control-flow). 298CFGBlock* CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) { 299tryAgain: 300 switch (S->getStmtClass()) { 301 default: 302 return VisitStmt(S, asc); 303 304 case Stmt::AddrLabelExprClass: 305 return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc); 306 307 case Stmt::BinaryOperatorClass: 308 return VisitBinaryOperator(cast<BinaryOperator>(S), asc); 309 310 case Stmt::BlockExprClass: 311 return VisitBlockExpr(cast<BlockExpr>(S), asc); 312 313 case Stmt::BreakStmtClass: 314 return VisitBreakStmt(cast<BreakStmt>(S)); 315 316 case Stmt::CallExprClass: 317 return VisitCallExpr(cast<CallExpr>(S), asc); 318 319 case Stmt::CaseStmtClass: 320 return VisitCaseStmt(cast<CaseStmt>(S)); 321 322 case Stmt::ChooseExprClass: 323 return VisitChooseExpr(cast<ChooseExpr>(S), asc); 324 325 case Stmt::CompoundStmtClass: 326 return VisitCompoundStmt(cast<CompoundStmt>(S)); 327 328 case Stmt::ConditionalOperatorClass: 329 return VisitConditionalOperator(cast<ConditionalOperator>(S), asc); 330 331 case Stmt::ContinueStmtClass: 332 return VisitContinueStmt(cast<ContinueStmt>(S)); 333 334 case Stmt::CXXCatchStmtClass: 335 return VisitCXXCatchStmt(cast<CXXCatchStmt>(S)); 336 337 case Stmt::CXXThrowExprClass: 338 return VisitCXXThrowExpr(cast<CXXThrowExpr>(S)); 339 340 case Stmt::CXXTryStmtClass: 341 return VisitCXXTryStmt(cast<CXXTryStmt>(S)); 342 343 case Stmt::DeclStmtClass: 344 return VisitDeclStmt(cast<DeclStmt>(S)); 345 346 case Stmt::DefaultStmtClass: 347 return VisitDefaultStmt(cast<DefaultStmt>(S)); 348 349 case Stmt::DoStmtClass: 350 return VisitDoStmt(cast<DoStmt>(S)); 351 352 case Stmt::ForStmtClass: 353 return VisitForStmt(cast<ForStmt>(S)); 354 355 case Stmt::GotoStmtClass: 356 return VisitGotoStmt(cast<GotoStmt>(S)); 357 358 case Stmt::IfStmtClass: 359 return VisitIfStmt(cast<IfStmt>(S)); 360 361 case Stmt::IndirectGotoStmtClass: 362 return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S)); 363 364 case Stmt::LabelStmtClass: 365 return VisitLabelStmt(cast<LabelStmt>(S)); 366 367 case Stmt::ObjCAtCatchStmtClass: 368 return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S)); 369 370 case Stmt::ObjCAtSynchronizedStmtClass: 371 return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S)); 372 373 case Stmt::ObjCAtThrowStmtClass: 374 return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S)); 375 376 case Stmt::ObjCAtTryStmtClass: 377 return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S)); 378 379 case Stmt::ObjCForCollectionStmtClass: 380 return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S)); 381 382 case Stmt::ParenExprClass: 383 S = cast<ParenExpr>(S)->getSubExpr(); 384 goto tryAgain; 385 386 case Stmt::NullStmtClass: 387 return Block; 388 389 case Stmt::ReturnStmtClass: 390 return VisitReturnStmt(cast<ReturnStmt>(S)); 391 392 case Stmt::SizeOfAlignOfExprClass: 393 return VisitSizeOfAlignOfExpr(cast<SizeOfAlignOfExpr>(S), asc); 394 395 case Stmt::StmtExprClass: 396 return VisitStmtExpr(cast<StmtExpr>(S), asc); 397 398 case Stmt::SwitchStmtClass: 399 return VisitSwitchStmt(cast<SwitchStmt>(S)); 400 401 case Stmt::WhileStmtClass: 402 return VisitWhileStmt(cast<WhileStmt>(S)); 403 } 404} 405 406CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) { 407 if (asc.alwaysAdd()) { 408 autoCreateBlock(); 409 AppendStmt(Block, S, asc); 410 } 411 412 return VisitChildren(S); 413} 414 415/// VisitChildren - Visit the children of a Stmt. 416CFGBlock *CFGBuilder::VisitChildren(Stmt* Terminator) { 417 CFGBlock *B = Block; 418 for (Stmt::child_iterator I = Terminator->child_begin(), 419 E = Terminator->child_end(); I != E; ++I) { 420 if (*I) B = Visit(*I); 421 } 422 return B; 423} 424 425CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, 426 AddStmtChoice asc) { 427 AddressTakenLabels.insert(A->getLabel()); 428 429 if (asc.alwaysAdd()) { 430 autoCreateBlock(); 431 AppendStmt(Block, A, asc); 432 } 433 434 return Block; 435} 436 437CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, 438 AddStmtChoice asc) { 439 if (B->isLogicalOp()) { // && or || 440 CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 441 AppendStmt(ConfluenceBlock, B, asc); 442 443 if (!FinishBlock(ConfluenceBlock)) 444 return 0; 445 446 // create the block evaluating the LHS 447 CFGBlock* LHSBlock = createBlock(false); 448 LHSBlock->setTerminator(B); 449 450 // create the block evaluating the RHS 451 Succ = ConfluenceBlock; 452 Block = NULL; 453 CFGBlock* RHSBlock = addStmt(B->getRHS()); 454 if (!FinishBlock(RHSBlock)) 455 return 0; 456 457 // See if this is a known constant. 458 TryResult KnownVal = TryEvaluateBool(B->getLHS()); 459 if (KnownVal.isKnown() && (B->getOpcode() == BinaryOperator::LOr)) 460 KnownVal.negate(); 461 462 // Now link the LHSBlock with RHSBlock. 463 if (B->getOpcode() == BinaryOperator::LOr) { 464 AddSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 465 AddSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 466 } else { 467 assert(B->getOpcode() == BinaryOperator::LAnd); 468 AddSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 469 AddSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 470 } 471 472 // Generate the blocks for evaluating the LHS. 473 Block = LHSBlock; 474 return addStmt(B->getLHS()); 475 } 476 else if (B->getOpcode() == BinaryOperator::Comma) { // , 477 autoCreateBlock(); 478 AppendStmt(Block, B, asc); 479 addStmt(B->getRHS()); 480 return addStmt(B->getLHS()); 481 } 482 483 return VisitStmt(B, asc); 484} 485 486CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) { 487 if (asc.alwaysAdd()) { 488 autoCreateBlock(); 489 AppendStmt(Block, E, asc); 490 } 491 return Block; 492} 493 494CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { 495 // "break" is a control-flow statement. Thus we stop processing the current 496 // block. 497 if (Block && !FinishBlock(Block)) 498 return 0; 499 500 // Now create a new block that ends with the break statement. 501 Block = createBlock(false); 502 Block->setTerminator(B); 503 504 // If there is no target for the break, then we are looking at an incomplete 505 // AST. This means that the CFG cannot be constructed. 506 if (BreakTargetBlock) 507 AddSuccessor(Block, BreakTargetBlock); 508 else 509 badCFG = true; 510 511 512 return Block; 513} 514 515CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { 516 // If this is a call to a no-return function, this stops the block here. 517 bool NoReturn = false; 518 if (C->getCallee()->getType().getNoReturnAttr()) { 519 NoReturn = true; 520 } 521 522 if (FunctionDecl *FD = C->getDirectCallee()) 523 if (FD->hasAttr<NoReturnAttr>()) 524 NoReturn = true; 525 526 if (!NoReturn) 527 return VisitStmt(C, asc); 528 529 if (Block && !FinishBlock(Block)) 530 return 0; 531 532 // Create new block with no successor for the remaining pieces. 533 Block = createBlock(false); 534 AppendStmt(Block, C, asc); 535 536 // Wire this to the exit block directly. 537 AddSuccessor(Block, &cfg->getExit()); 538 539 return VisitChildren(C); 540} 541 542CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C, 543 AddStmtChoice asc) { 544 CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 545 AppendStmt(ConfluenceBlock, C, asc); 546 if (!FinishBlock(ConfluenceBlock)) 547 return 0; 548 549 Succ = ConfluenceBlock; 550 Block = NULL; 551 CFGBlock* LHSBlock = addStmt(C->getLHS()); 552 if (!FinishBlock(LHSBlock)) 553 return 0; 554 555 Succ = ConfluenceBlock; 556 Block = NULL; 557 CFGBlock* RHSBlock = addStmt(C->getRHS()); 558 if (!FinishBlock(RHSBlock)) 559 return 0; 560 561 Block = createBlock(false); 562 // See if this is a known constant. 563 const TryResult& KnownVal = TryEvaluateBool(C->getCond()); 564 AddSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); 565 AddSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); 566 Block->setTerminator(C); 567 return addStmt(C->getCond()); 568} 569 570 571CFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) { 572 CFGBlock* LastBlock = Block; 573 574 for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); 575 I != E; ++I ) { 576 LastBlock = addStmt(*I); 577 578 if (badCFG) 579 return NULL; 580 } 581 return LastBlock; 582} 583 584CFGBlock *CFGBuilder::VisitConditionalOperator(ConditionalOperator *C, 585 AddStmtChoice asc) { 586 // Create the confluence block that will "merge" the results of the ternary 587 // expression. 588 CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 589 AppendStmt(ConfluenceBlock, C, asc); 590 if (!FinishBlock(ConfluenceBlock)) 591 return 0; 592 593 // Create a block for the LHS expression if there is an LHS expression. A 594 // GCC extension allows LHS to be NULL, causing the condition to be the 595 // value that is returned instead. 596 // e.g: x ?: y is shorthand for: x ? x : y; 597 Succ = ConfluenceBlock; 598 Block = NULL; 599 CFGBlock* LHSBlock = NULL; 600 if (C->getLHS()) { 601 LHSBlock = addStmt(C->getLHS()); 602 if (!FinishBlock(LHSBlock)) 603 return 0; 604 Block = NULL; 605 } 606 607 // Create the block for the RHS expression. 608 Succ = ConfluenceBlock; 609 CFGBlock* RHSBlock = addStmt(C->getRHS()); 610 if (!FinishBlock(RHSBlock)) 611 return 0; 612 613 // Create the block that will contain the condition. 614 Block = createBlock(false); 615 616 // See if this is a known constant. 617 const TryResult& KnownVal = TryEvaluateBool(C->getCond()); 618 if (LHSBlock) { 619 AddSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); 620 } else { 621 if (KnownVal.isFalse()) { 622 // If we know the condition is false, add NULL as the successor for 623 // the block containing the condition. In this case, the confluence 624 // block will have just one predecessor. 625 AddSuccessor(Block, 0); 626 assert(ConfluenceBlock->pred_size() == 1); 627 } else { 628 // If we have no LHS expression, add the ConfluenceBlock as a direct 629 // successor for the block containing the condition. Moreover, we need to 630 // reverse the order of the predecessors in the ConfluenceBlock because 631 // the RHSBlock will have been added to the succcessors already, and we 632 // want the first predecessor to the the block containing the expression 633 // for the case when the ternary expression evaluates to true. 634 AddSuccessor(Block, ConfluenceBlock); 635 assert(ConfluenceBlock->pred_size() == 2); 636 std::reverse(ConfluenceBlock->pred_begin(), 637 ConfluenceBlock->pred_end()); 638 } 639 } 640 641 AddSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); 642 Block->setTerminator(C); 643 return addStmt(C->getCond()); 644} 645 646CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) { 647 autoCreateBlock(); 648 649 if (DS->isSingleDecl()) { 650 AppendStmt(Block, DS); 651 return VisitDeclSubExpr(DS->getSingleDecl()); 652 } 653 654 CFGBlock *B = 0; 655 656 // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy. 657 typedef llvm::SmallVector<Decl*,10> BufTy; 658 BufTy Buf(DS->decl_begin(), DS->decl_end()); 659 660 for (BufTy::reverse_iterator I = Buf.rbegin(), E = Buf.rend(); I != E; ++I) { 661 // Get the alignment of the new DeclStmt, padding out to >=8 bytes. 662 unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8 663 ? 8 : llvm::AlignOf<DeclStmt>::Alignment; 664 665 // Allocate the DeclStmt using the BumpPtrAllocator. It will get 666 // automatically freed with the CFG. 667 DeclGroupRef DG(*I); 668 Decl *D = *I; 669 void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A); 670 DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); 671 672 // Append the fake DeclStmt to block. 673 AppendStmt(Block, DSNew); 674 B = VisitDeclSubExpr(D); 675 } 676 677 return B; 678} 679 680/// VisitDeclSubExpr - Utility method to add block-level expressions for 681/// initializers in Decls. 682CFGBlock *CFGBuilder::VisitDeclSubExpr(Decl* D) { 683 assert(Block); 684 685 VarDecl *VD = dyn_cast<VarDecl>(D); 686 687 if (!VD) 688 return Block; 689 690 Expr *Init = VD->getInit(); 691 692 if (Init) { 693 // Optimization: Don't create separate block-level statements for literals. 694 switch (Init->getStmtClass()) { 695 case Stmt::IntegerLiteralClass: 696 case Stmt::CharacterLiteralClass: 697 case Stmt::StringLiteralClass: 698 break; 699 default: 700 Block = addStmt(Init, 701 VD->getType()->isReferenceType() 702 ? AddStmtChoice::AlwaysAddAsLValue 703 : AddStmtChoice::AlwaysAdd); 704 } 705 } 706 707 // If the type of VD is a VLA, then we must process its size expressions. 708 for (VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); VA != 0; 709 VA = FindVA(VA->getElementType().getTypePtr())) 710 Block = addStmt(VA->getSizeExpr()); 711 712 return Block; 713} 714 715CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { 716 // We may see an if statement in the middle of a basic block, or it may be the 717 // first statement we are processing. In either case, we create a new basic 718 // block. First, we create the blocks for the then...else statements, and 719 // then we create the block containing the if statement. If we were in the 720 // middle of a block, we stop processing that block. That block is then the 721 // implicit successor for the "then" and "else" clauses. 722 723 // The block we were proccessing is now finished. Make it the successor 724 // block. 725 if (Block) { 726 Succ = Block; 727 if (!FinishBlock(Block)) 728 return 0; 729 } 730 731 // Process the false branch. 732 CFGBlock* ElseBlock = Succ; 733 734 if (Stmt* Else = I->getElse()) { 735 SaveAndRestore<CFGBlock*> sv(Succ); 736 737 // NULL out Block so that the recursive call to Visit will 738 // create a new basic block. 739 Block = NULL; 740 ElseBlock = addStmt(Else); 741 742 if (!ElseBlock) // Can occur when the Else body has all NullStmts. 743 ElseBlock = sv.get(); 744 else if (Block) { 745 if (!FinishBlock(ElseBlock)) 746 return 0; 747 } 748 } 749 750 // Process the true branch. 751 CFGBlock* ThenBlock; 752 { 753 Stmt* Then = I->getThen(); 754 assert(Then); 755 SaveAndRestore<CFGBlock*> sv(Succ); 756 Block = NULL; 757 ThenBlock = addStmt(Then); 758 759 if (!ThenBlock) { 760 // We can reach here if the "then" body has all NullStmts. 761 // Create an empty block so we can distinguish between true and false 762 // branches in path-sensitive analyses. 763 ThenBlock = createBlock(false); 764 AddSuccessor(ThenBlock, sv.get()); 765 } else if (Block) { 766 if (!FinishBlock(ThenBlock)) 767 return 0; 768 } 769 } 770 771 // Now create a new block containing the if statement. 772 Block = createBlock(false); 773 774 // Set the terminator of the new block to the If statement. 775 Block->setTerminator(I); 776 777 // See if this is a known constant. 778 const TryResult &KnownVal = TryEvaluateBool(I->getCond()); 779 780 // Now add the successors. 781 AddSuccessor(Block, KnownVal.isFalse() ? NULL : ThenBlock); 782 AddSuccessor(Block, KnownVal.isTrue()? NULL : ElseBlock); 783 784 // Add the condition as the last statement in the new block. This may create 785 // new blocks as the condition may contain control-flow. Any newly created 786 // blocks will be pointed to be "Block". 787 Block = addStmt(I->getCond()); 788 789 // Finally, if the IfStmt contains a condition variable, add both the IfStmt 790 // and the condition variable initialization to the CFG. 791 if (VarDecl *VD = I->getConditionVariable()) { 792 if (Expr *Init = VD->getInit()) { 793 autoCreateBlock(); 794 AppendStmt(Block, I, AddStmtChoice::AlwaysAdd); 795 addStmt(Init); 796 } 797 } 798 799 return Block; 800} 801 802 803CFGBlock* CFGBuilder::VisitReturnStmt(ReturnStmt* R) { 804 // If we were in the middle of a block we stop processing that block. 805 // 806 // NOTE: If a "return" appears in the middle of a block, this means that the 807 // code afterwards is DEAD (unreachable). We still keep a basic block 808 // for that code; a simple "mark-and-sweep" from the entry block will be 809 // able to report such dead blocks. 810 if (Block) 811 FinishBlock(Block); 812 813 // Create the new block. 814 Block = createBlock(false); 815 816 // The Exit block is the only successor. 817 AddSuccessor(Block, &cfg->getExit()); 818 819 // Add the return statement to the block. This may create new blocks if R 820 // contains control-flow (short-circuit operations). 821 return VisitStmt(R, AddStmtChoice::AlwaysAdd); 822} 823 824CFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt* L) { 825 // Get the block of the labeled statement. Add it to our map. 826 addStmt(L->getSubStmt()); 827 CFGBlock* LabelBlock = Block; 828 829 if (!LabelBlock) // This can happen when the body is empty, i.e. 830 LabelBlock = createBlock(); // scopes that only contains NullStmts. 831 832 assert(LabelMap.find(L) == LabelMap.end() && "label already in map"); 833 LabelMap[ L ] = LabelBlock; 834 835 // Labels partition blocks, so this is the end of the basic block we were 836 // processing (L is the block's label). Because this is label (and we have 837 // already processed the substatement) there is no extra control-flow to worry 838 // about. 839 LabelBlock->setLabel(L); 840 if (!FinishBlock(LabelBlock)) 841 return 0; 842 843 // We set Block to NULL to allow lazy creation of a new block (if necessary); 844 Block = NULL; 845 846 // This block is now the implicit successor of other blocks. 847 Succ = LabelBlock; 848 849 return LabelBlock; 850} 851 852CFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) { 853 // Goto is a control-flow statement. Thus we stop processing the current 854 // block and create a new one. 855 if (Block) 856 FinishBlock(Block); 857 858 Block = createBlock(false); 859 Block->setTerminator(G); 860 861 // If we already know the mapping to the label block add the successor now. 862 LabelMapTy::iterator I = LabelMap.find(G->getLabel()); 863 864 if (I == LabelMap.end()) 865 // We will need to backpatch this block later. 866 BackpatchBlocks.push_back(Block); 867 else 868 AddSuccessor(Block, I->second); 869 870 return Block; 871} 872 873CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { 874 CFGBlock* LoopSuccessor = NULL; 875 876 // "for" is a control-flow statement. Thus we stop processing the current 877 // block. 878 if (Block) { 879 if (!FinishBlock(Block)) 880 return 0; 881 LoopSuccessor = Block; 882 } else 883 LoopSuccessor = Succ; 884 885 // Because of short-circuit evaluation, the condition of the loop can span 886 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 887 // evaluate the condition. 888 CFGBlock* ExitConditionBlock = createBlock(false); 889 CFGBlock* EntryConditionBlock = ExitConditionBlock; 890 891 // Set the terminator for the "exit" condition block. 892 ExitConditionBlock->setTerminator(F); 893 894 // Now add the actual condition to the condition block. Because the condition 895 // itself may contain control-flow, new blocks may be created. 896 if (Stmt* C = F->getCond()) { 897 Block = ExitConditionBlock; 898 EntryConditionBlock = addStmt(C); 899 assert(Block == EntryConditionBlock); 900 901 // If this block contains a condition variable, add both the condition 902 // variable and initializer to the CFG. 903 if (VarDecl *VD = F->getConditionVariable()) { 904 if (Expr *Init = VD->getInit()) { 905 autoCreateBlock(); 906 AppendStmt(Block, F, AddStmtChoice::AlwaysAdd); 907 EntryConditionBlock = addStmt(Init); 908 assert(Block == EntryConditionBlock); 909 } 910 } 911 912 if (Block) { 913 if (!FinishBlock(EntryConditionBlock)) 914 return 0; 915 } 916 } 917 918 // The condition block is the implicit successor for the loop body as well as 919 // any code above the loop. 920 Succ = EntryConditionBlock; 921 922 // See if this is a known constant. 923 TryResult KnownVal(true); 924 925 if (F->getCond()) 926 KnownVal = TryEvaluateBool(F->getCond()); 927 928 // Now create the loop body. 929 { 930 assert(F->getBody()); 931 932 // Save the current values for Block, Succ, and continue and break targets 933 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 934 save_continue(ContinueTargetBlock), 935 save_break(BreakTargetBlock); 936 937 // Create a new block to contain the (bottom) of the loop body. 938 Block = NULL; 939 940 if (Stmt* I = F->getInc()) { 941 // Generate increment code in its own basic block. This is the target of 942 // continue statements. 943 Succ = addStmt(I); 944 } else { 945 // No increment code. Create a special, empty, block that is used as the 946 // target block for "looping back" to the start of the loop. 947 assert(Succ == EntryConditionBlock); 948 Succ = createBlock(); 949 } 950 951 // Finish up the increment (or empty) block if it hasn't been already. 952 if (Block) { 953 assert(Block == Succ); 954 if (!FinishBlock(Block)) 955 return 0; 956 Block = 0; 957 } 958 959 ContinueTargetBlock = Succ; 960 961 // The starting block for the loop increment is the block that should 962 // represent the 'loop target' for looping back to the start of the loop. 963 ContinueTargetBlock->setLoopTarget(F); 964 965 // All breaks should go to the code following the loop. 966 BreakTargetBlock = LoopSuccessor; 967 968 // Now populate the body block, and in the process create new blocks as we 969 // walk the body of the loop. 970 CFGBlock* BodyBlock = addStmt(F->getBody()); 971 972 if (!BodyBlock) 973 BodyBlock = ContinueTargetBlock; // can happen for "for (...;...;...) ;" 974 else if (Block && !FinishBlock(BodyBlock)) 975 return 0; 976 977 // This new body block is a successor to our "exit" condition block. 978 AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); 979 } 980 981 // Link up the condition block with the code that follows the loop. (the 982 // false branch). 983 AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 984 985 // If the loop contains initialization, create a new block for those 986 // statements. This block can also contain statements that precede the loop. 987 if (Stmt* I = F->getInit()) { 988 Block = createBlock(); 989 return addStmt(I); 990 } else { 991 // There is no loop initialization. We are thus basically a while loop. 992 // NULL out Block to force lazy block construction. 993 Block = NULL; 994 Succ = EntryConditionBlock; 995 return EntryConditionBlock; 996 } 997} 998 999CFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { 1000 // Objective-C fast enumeration 'for' statements: 1001 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC 1002 // 1003 // for ( Type newVariable in collection_expression ) { statements } 1004 // 1005 // becomes: 1006 // 1007 // prologue: 1008 // 1. collection_expression 1009 // T. jump to loop_entry 1010 // loop_entry: 1011 // 1. side-effects of element expression 1012 // 1. ObjCForCollectionStmt [performs binding to newVariable] 1013 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil] 1014 // TB: 1015 // statements 1016 // T. jump to loop_entry 1017 // FB: 1018 // what comes after 1019 // 1020 // and 1021 // 1022 // Type existingItem; 1023 // for ( existingItem in expression ) { statements } 1024 // 1025 // becomes: 1026 // 1027 // the same with newVariable replaced with existingItem; the binding works 1028 // the same except that for one ObjCForCollectionStmt::getElement() returns 1029 // a DeclStmt and the other returns a DeclRefExpr. 1030 // 1031 1032 CFGBlock* LoopSuccessor = 0; 1033 1034 if (Block) { 1035 if (!FinishBlock(Block)) 1036 return 0; 1037 LoopSuccessor = Block; 1038 Block = 0; 1039 } else 1040 LoopSuccessor = Succ; 1041 1042 // Build the condition blocks. 1043 CFGBlock* ExitConditionBlock = createBlock(false); 1044 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1045 1046 // Set the terminator for the "exit" condition block. 1047 ExitConditionBlock->setTerminator(S); 1048 1049 // The last statement in the block should be the ObjCForCollectionStmt, which 1050 // performs the actual binding to 'element' and determines if there are any 1051 // more items in the collection. 1052 AppendStmt(ExitConditionBlock, S); 1053 Block = ExitConditionBlock; 1054 1055 // Walk the 'element' expression to see if there are any side-effects. We 1056 // generate new blocks as necesary. We DON'T add the statement by default to 1057 // the CFG unless it contains control-flow. 1058 EntryConditionBlock = Visit(S->getElement(), AddStmtChoice::NotAlwaysAdd); 1059 if (Block) { 1060 if (!FinishBlock(EntryConditionBlock)) 1061 return 0; 1062 Block = 0; 1063 } 1064 1065 // The condition block is the implicit successor for the loop body as well as 1066 // any code above the loop. 1067 Succ = EntryConditionBlock; 1068 1069 // Now create the true branch. 1070 { 1071 // Save the current values for Succ, continue and break targets. 1072 SaveAndRestore<CFGBlock*> save_Succ(Succ), 1073 save_continue(ContinueTargetBlock), save_break(BreakTargetBlock); 1074 1075 BreakTargetBlock = LoopSuccessor; 1076 ContinueTargetBlock = EntryConditionBlock; 1077 1078 CFGBlock* BodyBlock = addStmt(S->getBody()); 1079 1080 if (!BodyBlock) 1081 BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;" 1082 else if (Block) { 1083 if (!FinishBlock(BodyBlock)) 1084 return 0; 1085 } 1086 1087 // This new body block is a successor to our "exit" condition block. 1088 AddSuccessor(ExitConditionBlock, BodyBlock); 1089 } 1090 1091 // Link up the condition block with the code that follows the loop. 1092 // (the false branch). 1093 AddSuccessor(ExitConditionBlock, LoopSuccessor); 1094 1095 // Now create a prologue block to contain the collection expression. 1096 Block = createBlock(); 1097 return addStmt(S->getCollection()); 1098} 1099 1100CFGBlock* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S) { 1101 // FIXME: Add locking 'primitives' to CFG for @synchronized. 1102 1103 // Inline the body. 1104 CFGBlock *SyncBlock = addStmt(S->getSynchBody()); 1105 1106 // The sync body starts its own basic block. This makes it a little easier 1107 // for diagnostic clients. 1108 if (SyncBlock) { 1109 if (!FinishBlock(SyncBlock)) 1110 return 0; 1111 1112 Block = 0; 1113 } 1114 1115 Succ = SyncBlock; 1116 1117 // Inline the sync expression. 1118 return addStmt(S->getSynchExpr()); 1119} 1120 1121CFGBlock* CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt* S) { 1122 // FIXME 1123 return NYS(); 1124} 1125 1126CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { 1127 CFGBlock* LoopSuccessor = NULL; 1128 1129 // "while" is a control-flow statement. Thus we stop processing the current 1130 // block. 1131 if (Block) { 1132 if (!FinishBlock(Block)) 1133 return 0; 1134 LoopSuccessor = Block; 1135 } else 1136 LoopSuccessor = Succ; 1137 1138 // Because of short-circuit evaluation, the condition of the loop can span 1139 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1140 // evaluate the condition. 1141 CFGBlock* ExitConditionBlock = createBlock(false); 1142 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1143 1144 // Set the terminator for the "exit" condition block. 1145 ExitConditionBlock->setTerminator(W); 1146 1147 // Now add the actual condition to the condition block. Because the condition 1148 // itself may contain control-flow, new blocks may be created. Thus we update 1149 // "Succ" after adding the condition. 1150 if (Stmt* C = W->getCond()) { 1151 Block = ExitConditionBlock; 1152 EntryConditionBlock = addStmt(C); 1153 assert(Block == EntryConditionBlock); 1154 1155 // If this block contains a condition variable, add both the condition 1156 // variable and initializer to the CFG. 1157 if (VarDecl *VD = W->getConditionVariable()) { 1158 if (Expr *Init = VD->getInit()) { 1159 autoCreateBlock(); 1160 AppendStmt(Block, W, AddStmtChoice::AlwaysAdd); 1161 EntryConditionBlock = addStmt(Init); 1162 assert(Block == EntryConditionBlock); 1163 } 1164 } 1165 1166 if (Block) { 1167 if (!FinishBlock(EntryConditionBlock)) 1168 return 0; 1169 } 1170 } 1171 1172 // The condition block is the implicit successor for the loop body as well as 1173 // any code above the loop. 1174 Succ = EntryConditionBlock; 1175 1176 // See if this is a known constant. 1177 const TryResult& KnownVal = TryEvaluateBool(W->getCond()); 1178 1179 // Process the loop body. 1180 { 1181 assert(W->getBody()); 1182 1183 // Save the current values for Block, Succ, and continue and break targets 1184 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1185 save_continue(ContinueTargetBlock), 1186 save_break(BreakTargetBlock); 1187 1188 // Create an empty block to represent the transition block for looping back 1189 // to the head of the loop. 1190 Block = 0; 1191 assert(Succ == EntryConditionBlock); 1192 Succ = createBlock(); 1193 Succ->setLoopTarget(W); 1194 ContinueTargetBlock = Succ; 1195 1196 // All breaks should go to the code following the loop. 1197 BreakTargetBlock = LoopSuccessor; 1198 1199 // NULL out Block to force lazy instantiation of blocks for the body. 1200 Block = NULL; 1201 1202 // Create the body. The returned block is the entry to the loop body. 1203 CFGBlock* BodyBlock = addStmt(W->getBody()); 1204 1205 if (!BodyBlock) 1206 BodyBlock = ContinueTargetBlock; // can happen for "while(...) ;" 1207 else if (Block) { 1208 if (!FinishBlock(BodyBlock)) 1209 return 0; 1210 } 1211 1212 // Add the loop body entry as a successor to the condition. 1213 AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); 1214 } 1215 1216 // Link up the condition block with the code that follows the loop. (the 1217 // false branch). 1218 AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 1219 1220 // There can be no more statements in the condition block since we loop back 1221 // to this block. NULL out Block to force lazy creation of another block. 1222 Block = NULL; 1223 1224 // Return the condition block, which is the dominating block for the loop. 1225 Succ = EntryConditionBlock; 1226 return EntryConditionBlock; 1227} 1228 1229 1230CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt* S) { 1231 // FIXME: For now we pretend that @catch and the code it contains does not 1232 // exit. 1233 return Block; 1234} 1235 1236CFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) { 1237 // FIXME: This isn't complete. We basically treat @throw like a return 1238 // statement. 1239 1240 // If we were in the middle of a block we stop processing that block. 1241 if (Block && !FinishBlock(Block)) 1242 return 0; 1243 1244 // Create the new block. 1245 Block = createBlock(false); 1246 1247 // The Exit block is the only successor. 1248 AddSuccessor(Block, &cfg->getExit()); 1249 1250 // Add the statement to the block. This may create new blocks if S contains 1251 // control-flow (short-circuit operations). 1252 return VisitStmt(S, AddStmtChoice::AlwaysAdd); 1253} 1254 1255CFGBlock* CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr* T) { 1256 // If we were in the middle of a block we stop processing that block. 1257 if (Block && !FinishBlock(Block)) 1258 return 0; 1259 1260 // Create the new block. 1261 Block = createBlock(false); 1262 1263 if (TryTerminatedBlock) 1264 // The current try statement is the only successor. 1265 AddSuccessor(Block, TryTerminatedBlock); 1266 else 1267 // otherwise the Exit block is the only successor. 1268 AddSuccessor(Block, &cfg->getExit()); 1269 1270 // Add the statement to the block. This may create new blocks if S contains 1271 // control-flow (short-circuit operations). 1272 return VisitStmt(T, AddStmtChoice::AlwaysAdd); 1273} 1274 1275CFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { 1276 CFGBlock* LoopSuccessor = NULL; 1277 1278 // "do...while" is a control-flow statement. Thus we stop processing the 1279 // current block. 1280 if (Block) { 1281 if (!FinishBlock(Block)) 1282 return 0; 1283 LoopSuccessor = Block; 1284 } else 1285 LoopSuccessor = Succ; 1286 1287 // Because of short-circuit evaluation, the condition of the loop can span 1288 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1289 // evaluate the condition. 1290 CFGBlock* ExitConditionBlock = createBlock(false); 1291 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1292 1293 // Set the terminator for the "exit" condition block. 1294 ExitConditionBlock->setTerminator(D); 1295 1296 // Now add the actual condition to the condition block. Because the condition 1297 // itself may contain control-flow, new blocks may be created. 1298 if (Stmt* C = D->getCond()) { 1299 Block = ExitConditionBlock; 1300 EntryConditionBlock = addStmt(C); 1301 if (Block) { 1302 if (!FinishBlock(EntryConditionBlock)) 1303 return 0; 1304 } 1305 } 1306 1307 // The condition block is the implicit successor for the loop body. 1308 Succ = EntryConditionBlock; 1309 1310 // See if this is a known constant. 1311 const TryResult &KnownVal = TryEvaluateBool(D->getCond()); 1312 1313 // Process the loop body. 1314 CFGBlock* BodyBlock = NULL; 1315 { 1316 assert(D->getBody()); 1317 1318 // Save the current values for Block, Succ, and continue and break targets 1319 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1320 save_continue(ContinueTargetBlock), 1321 save_break(BreakTargetBlock); 1322 1323 // All continues within this loop should go to the condition block 1324 ContinueTargetBlock = EntryConditionBlock; 1325 1326 // All breaks should go to the code following the loop. 1327 BreakTargetBlock = LoopSuccessor; 1328 1329 // NULL out Block to force lazy instantiation of blocks for the body. 1330 Block = NULL; 1331 1332 // Create the body. The returned block is the entry to the loop body. 1333 BodyBlock = addStmt(D->getBody()); 1334 1335 if (!BodyBlock) 1336 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" 1337 else if (Block) { 1338 if (!FinishBlock(BodyBlock)) 1339 return 0; 1340 } 1341 1342 // Add an intermediate block between the BodyBlock and the 1343 // ExitConditionBlock to represent the "loop back" transition. Create an 1344 // empty block to represent the transition block for looping back to the 1345 // head of the loop. 1346 // FIXME: Can we do this more efficiently without adding another block? 1347 Block = NULL; 1348 Succ = BodyBlock; 1349 CFGBlock *LoopBackBlock = createBlock(); 1350 LoopBackBlock->setLoopTarget(D); 1351 1352 // Add the loop body entry as a successor to the condition. 1353 AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : LoopBackBlock); 1354 } 1355 1356 // Link up the condition block with the code that follows the loop. 1357 // (the false branch). 1358 AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 1359 1360 // There can be no more statements in the body block(s) since we loop back to 1361 // the body. NULL out Block to force lazy creation of another block. 1362 Block = NULL; 1363 1364 // Return the loop body, which is the dominating block for the loop. 1365 Succ = BodyBlock; 1366 return BodyBlock; 1367} 1368 1369CFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) { 1370 // "continue" is a control-flow statement. Thus we stop processing the 1371 // current block. 1372 if (Block && !FinishBlock(Block)) 1373 return 0; 1374 1375 // Now create a new block that ends with the continue statement. 1376 Block = createBlock(false); 1377 Block->setTerminator(C); 1378 1379 // If there is no target for the continue, then we are looking at an 1380 // incomplete AST. This means the CFG cannot be constructed. 1381 if (ContinueTargetBlock) 1382 AddSuccessor(Block, ContinueTargetBlock); 1383 else 1384 badCFG = true; 1385 1386 return Block; 1387} 1388 1389CFGBlock *CFGBuilder::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, 1390 AddStmtChoice asc) { 1391 1392 if (asc.alwaysAdd()) { 1393 autoCreateBlock(); 1394 AppendStmt(Block, E); 1395 } 1396 1397 // VLA types have expressions that must be evaluated. 1398 if (E->isArgumentType()) { 1399 for (VariableArrayType* VA = FindVA(E->getArgumentType().getTypePtr()); 1400 VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) 1401 addStmt(VA->getSizeExpr()); 1402 } 1403 1404 return Block; 1405} 1406 1407/// VisitStmtExpr - Utility method to handle (nested) statement 1408/// expressions (a GCC extension). 1409CFGBlock* CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) { 1410 if (asc.alwaysAdd()) { 1411 autoCreateBlock(); 1412 AppendStmt(Block, SE); 1413 } 1414 return VisitCompoundStmt(SE->getSubStmt()); 1415} 1416 1417CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { 1418 // "switch" is a control-flow statement. Thus we stop processing the current 1419 // block. 1420 CFGBlock* SwitchSuccessor = NULL; 1421 1422 if (Block) { 1423 if (!FinishBlock(Block)) 1424 return 0; 1425 SwitchSuccessor = Block; 1426 } else SwitchSuccessor = Succ; 1427 1428 // Save the current "switch" context. 1429 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), 1430 save_break(BreakTargetBlock), 1431 save_default(DefaultCaseBlock); 1432 1433 // Set the "default" case to be the block after the switch statement. If the 1434 // switch statement contains a "default:", this value will be overwritten with 1435 // the block for that code. 1436 DefaultCaseBlock = SwitchSuccessor; 1437 1438 // Create a new block that will contain the switch statement. 1439 SwitchTerminatedBlock = createBlock(false); 1440 1441 // Now process the switch body. The code after the switch is the implicit 1442 // successor. 1443 Succ = SwitchSuccessor; 1444 BreakTargetBlock = SwitchSuccessor; 1445 1446 // When visiting the body, the case statements should automatically get linked 1447 // up to the switch. We also don't keep a pointer to the body, since all 1448 // control-flow from the switch goes to case/default statements. 1449 assert(Terminator->getBody() && "switch must contain a non-NULL body"); 1450 Block = NULL; 1451 CFGBlock *BodyBlock = addStmt(Terminator->getBody()); 1452 if (Block) { 1453 if (!FinishBlock(BodyBlock)) 1454 return 0; 1455 } 1456 1457 // If we have no "default:" case, the default transition is to the code 1458 // following the switch body. 1459 AddSuccessor(SwitchTerminatedBlock, DefaultCaseBlock); 1460 1461 // Add the terminator and condition in the switch block. 1462 SwitchTerminatedBlock->setTerminator(Terminator); 1463 assert(Terminator->getCond() && "switch condition must be non-NULL"); 1464 Block = SwitchTerminatedBlock; 1465 Block = addStmt(Terminator->getCond()); 1466 1467 // Finally, if the SwitchStmt contains a condition variable, add both the 1468 // SwitchStmt and the condition variable initialization to the CFG. 1469 if (VarDecl *VD = Terminator->getConditionVariable()) { 1470 if (Expr *Init = VD->getInit()) { 1471 autoCreateBlock(); 1472 AppendStmt(Block, Terminator, AddStmtChoice::AlwaysAdd); 1473 addStmt(Init); 1474 } 1475 } 1476 1477 return Block; 1478} 1479 1480CFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) { 1481 // CaseStmts are essentially labels, so they are the first statement in a 1482 // block. 1483 1484 if (CS->getSubStmt()) 1485 addStmt(CS->getSubStmt()); 1486 1487 CFGBlock* CaseBlock = Block; 1488 if (!CaseBlock) 1489 CaseBlock = createBlock(); 1490 1491 // Cases statements partition blocks, so this is the top of the basic block we 1492 // were processing (the "case XXX:" is the label). 1493 CaseBlock->setLabel(CS); 1494 1495 if (!FinishBlock(CaseBlock)) 1496 return 0; 1497 1498 // Add this block to the list of successors for the block with the switch 1499 // statement. 1500 assert(SwitchTerminatedBlock); 1501 AddSuccessor(SwitchTerminatedBlock, CaseBlock); 1502 1503 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1504 Block = NULL; 1505 1506 // This block is now the implicit successor of other blocks. 1507 Succ = CaseBlock; 1508 1509 return CaseBlock; 1510} 1511 1512CFGBlock* CFGBuilder::VisitDefaultStmt(DefaultStmt* Terminator) { 1513 if (Terminator->getSubStmt()) 1514 addStmt(Terminator->getSubStmt()); 1515 1516 DefaultCaseBlock = Block; 1517 1518 if (!DefaultCaseBlock) 1519 DefaultCaseBlock = createBlock(); 1520 1521 // Default statements partition blocks, so this is the top of the basic block 1522 // we were processing (the "default:" is the label). 1523 DefaultCaseBlock->setLabel(Terminator); 1524 1525 if (!FinishBlock(DefaultCaseBlock)) 1526 return 0; 1527 1528 // Unlike case statements, we don't add the default block to the successors 1529 // for the switch statement immediately. This is done when we finish 1530 // processing the switch statement. This allows for the default case 1531 // (including a fall-through to the code after the switch statement) to always 1532 // be the last successor of a switch-terminated block. 1533 1534 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1535 Block = NULL; 1536 1537 // This block is now the implicit successor of other blocks. 1538 Succ = DefaultCaseBlock; 1539 1540 return DefaultCaseBlock; 1541} 1542 1543CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) { 1544 // "try"/"catch" is a control-flow statement. Thus we stop processing the 1545 // current block. 1546 CFGBlock* TrySuccessor = NULL; 1547 1548 if (Block) { 1549 if (!FinishBlock(Block)) 1550 return 0; 1551 TrySuccessor = Block; 1552 } else TrySuccessor = Succ; 1553 1554 // Save the current "try" context. 1555 SaveAndRestore<CFGBlock*> save_try(TryTerminatedBlock); 1556 1557 // Create a new block that will contain the try statement. 1558 TryTerminatedBlock = createBlock(false); 1559 // Add the terminator in the try block. 1560 TryTerminatedBlock->setTerminator(Terminator); 1561 1562 for (unsigned h = 0; h <Terminator->getNumHandlers(); ++h) { 1563 // The code after the try is the implicit successor. 1564 Succ = TrySuccessor; 1565 CXXCatchStmt *CS = Terminator->getHandler(h); 1566 Block = NULL; 1567 CFGBlock *CatchBlock = VisitCXXCatchStmt(CS); 1568 if (CatchBlock == 0) 1569 return 0; 1570 // Add this block to the list of successors for the block with the try 1571 // statement. 1572 AddSuccessor(TryTerminatedBlock, CatchBlock); 1573 } 1574 1575 // The code after the try is the implicit successor. 1576 Succ = TrySuccessor; 1577 1578 // When visiting the body, the case statements should automatically get linked 1579 // up to the try. 1580 assert(Terminator->getTryBlock() && "try must contain a non-NULL body"); 1581 Block = NULL; 1582 Block = addStmt(Terminator->getTryBlock()); 1583 return Block; 1584} 1585 1586CFGBlock* CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt* CS) { 1587 // CXXCatchStmt are treated like labels, so they are the first statement in a 1588 // block. 1589 1590 if (CS->getHandlerBlock()) 1591 addStmt(CS->getHandlerBlock()); 1592 1593 CFGBlock* CatchBlock = Block; 1594 if (!CatchBlock) 1595 CatchBlock = createBlock(); 1596 1597 CatchBlock->setLabel(CS); 1598 1599 if (!FinishBlock(CatchBlock)) 1600 return 0; 1601 1602 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1603 Block = NULL; 1604 1605 return CatchBlock; 1606} 1607 1608CFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1609 // Lazily create the indirect-goto dispatch block if there isn't one already. 1610 CFGBlock* IBlock = cfg->getIndirectGotoBlock(); 1611 1612 if (!IBlock) { 1613 IBlock = createBlock(false); 1614 cfg->setIndirectGotoBlock(IBlock); 1615 } 1616 1617 // IndirectGoto is a control-flow statement. Thus we stop processing the 1618 // current block and create a new one. 1619 if (Block && !FinishBlock(Block)) 1620 return 0; 1621 1622 Block = createBlock(false); 1623 Block->setTerminator(I); 1624 AddSuccessor(Block, IBlock); 1625 return addStmt(I->getTarget()); 1626} 1627 1628} // end anonymous namespace 1629 1630/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has 1631/// no successors or predecessors. If this is the first block created in the 1632/// CFG, it is automatically set to be the Entry and Exit of the CFG. 1633CFGBlock* CFG::createBlock() { 1634 bool first_block = begin() == end(); 1635 1636 // Create the block. 1637 CFGBlock *Mem = getAllocator().Allocate<CFGBlock>(); 1638 new (Mem) CFGBlock(NumBlockIDs++, BlkBVC); 1639 Blocks.push_back(Mem, BlkBVC); 1640 1641 // If this is the first block, set it as the Entry and Exit. 1642 if (first_block) 1643 Entry = Exit = &back(); 1644 1645 // Return the block. 1646 return &back(); 1647} 1648 1649/// buildCFG - Constructs a CFG from an AST. Ownership of the returned 1650/// CFG is returned to the caller. 1651CFG* CFG::buildCFG(Stmt* Statement, ASTContext *C) { 1652 CFGBuilder Builder; 1653 return Builder.buildCFG(Statement, C); 1654} 1655 1656//===----------------------------------------------------------------------===// 1657// CFG: Queries for BlkExprs. 1658//===----------------------------------------------------------------------===// 1659 1660namespace { 1661 typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy; 1662} 1663 1664static void FindSubExprAssignments(Stmt *S, 1665 llvm::SmallPtrSet<Expr*,50>& Set) { 1666 if (!S) 1667 return; 1668 1669 for (Stmt::child_iterator I=S->child_begin(), E=S->child_end(); I!=E; ++I) { 1670 Stmt *child = *I; 1671 if (!child) 1672 continue; 1673 1674 if (BinaryOperator* B = dyn_cast<BinaryOperator>(child)) 1675 if (B->isAssignmentOp()) Set.insert(B); 1676 1677 FindSubExprAssignments(child, Set); 1678 } 1679} 1680 1681static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { 1682 BlkExprMapTy* M = new BlkExprMapTy(); 1683 1684 // Look for assignments that are used as subexpressions. These are the only 1685 // assignments that we want to *possibly* register as a block-level 1686 // expression. Basically, if an assignment occurs both in a subexpression and 1687 // at the block-level, it is a block-level expression. 1688 llvm::SmallPtrSet<Expr*,50> SubExprAssignments; 1689 1690 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) 1691 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) 1692 FindSubExprAssignments(*BI, SubExprAssignments); 1693 1694 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { 1695 1696 // Iterate over the statements again on identify the Expr* and Stmt* at the 1697 // block-level that are block-level expressions. 1698 1699 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) 1700 if (Expr* Exp = dyn_cast<Expr>(*BI)) { 1701 1702 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { 1703 // Assignment expressions that are not nested within another 1704 // expression are really "statements" whose value is never used by 1705 // another expression. 1706 if (B->isAssignmentOp() && !SubExprAssignments.count(Exp)) 1707 continue; 1708 } else if (const StmtExpr* Terminator = dyn_cast<StmtExpr>(Exp)) { 1709 // Special handling for statement expressions. The last statement in 1710 // the statement expression is also a block-level expr. 1711 const CompoundStmt* C = Terminator->getSubStmt(); 1712 if (!C->body_empty()) { 1713 unsigned x = M->size(); 1714 (*M)[C->body_back()] = x; 1715 } 1716 } 1717 1718 unsigned x = M->size(); 1719 (*M)[Exp] = x; 1720 } 1721 1722 // Look at terminators. The condition is a block-level expression. 1723 1724 Stmt* S = (*I)->getTerminatorCondition(); 1725 1726 if (S && M->find(S) == M->end()) { 1727 unsigned x = M->size(); 1728 (*M)[S] = x; 1729 } 1730 } 1731 1732 return M; 1733} 1734 1735CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) { 1736 assert(S != NULL); 1737 if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } 1738 1739 BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap); 1740 BlkExprMapTy::iterator I = M->find(S); 1741 return (I == M->end()) ? CFG::BlkExprNumTy() : CFG::BlkExprNumTy(I->second); 1742} 1743 1744unsigned CFG::getNumBlkExprs() { 1745 if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) 1746 return M->size(); 1747 else { 1748 // We assume callers interested in the number of BlkExprs will want 1749 // the map constructed if it doesn't already exist. 1750 BlkExprMap = (void*) PopulateBlkExprMap(*this); 1751 return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); 1752 } 1753} 1754 1755//===----------------------------------------------------------------------===// 1756// Cleanup: CFG dstor. 1757//===----------------------------------------------------------------------===// 1758 1759CFG::~CFG() { 1760 delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); 1761} 1762 1763//===----------------------------------------------------------------------===// 1764// CFG pretty printing 1765//===----------------------------------------------------------------------===// 1766 1767namespace { 1768 1769class StmtPrinterHelper : public PrinterHelper { 1770 typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; 1771 StmtMapTy StmtMap; 1772 signed CurrentBlock; 1773 unsigned CurrentStmt; 1774 const LangOptions &LangOpts; 1775public: 1776 1777 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) 1778 : CurrentBlock(0), CurrentStmt(0), LangOpts(LO) { 1779 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { 1780 unsigned j = 1; 1781 for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ; 1782 BI != BEnd; ++BI, ++j ) 1783 StmtMap[*BI] = std::make_pair((*I)->getBlockID(),j); 1784 } 1785 } 1786 1787 virtual ~StmtPrinterHelper() {} 1788 1789 const LangOptions &getLangOpts() const { return LangOpts; } 1790 void setBlockID(signed i) { CurrentBlock = i; } 1791 void setStmtID(unsigned i) { CurrentStmt = i; } 1792 1793 virtual bool handledStmt(Stmt* Terminator, llvm::raw_ostream& OS) { 1794 1795 StmtMapTy::iterator I = StmtMap.find(Terminator); 1796 1797 if (I == StmtMap.end()) 1798 return false; 1799 1800 if (CurrentBlock >= 0 && I->second.first == (unsigned) CurrentBlock 1801 && I->second.second == CurrentStmt) { 1802 return false; 1803 } 1804 1805 OS << "[B" << I->second.first << "." << I->second.second << "]"; 1806 return true; 1807 } 1808}; 1809} // end anonymous namespace 1810 1811 1812namespace { 1813class CFGBlockTerminatorPrint 1814 : public StmtVisitor<CFGBlockTerminatorPrint,void> { 1815 1816 llvm::raw_ostream& OS; 1817 StmtPrinterHelper* Helper; 1818 PrintingPolicy Policy; 1819public: 1820 CFGBlockTerminatorPrint(llvm::raw_ostream& os, StmtPrinterHelper* helper, 1821 const PrintingPolicy &Policy) 1822 : OS(os), Helper(helper), Policy(Policy) {} 1823 1824 void VisitIfStmt(IfStmt* I) { 1825 OS << "if "; 1826 I->getCond()->printPretty(OS,Helper,Policy); 1827 } 1828 1829 // Default case. 1830 void VisitStmt(Stmt* Terminator) { 1831 Terminator->printPretty(OS, Helper, Policy); 1832 } 1833 1834 void VisitForStmt(ForStmt* F) { 1835 OS << "for (" ; 1836 if (F->getInit()) 1837 OS << "..."; 1838 OS << "; "; 1839 if (Stmt* C = F->getCond()) 1840 C->printPretty(OS, Helper, Policy); 1841 OS << "; "; 1842 if (F->getInc()) 1843 OS << "..."; 1844 OS << ")"; 1845 } 1846 1847 void VisitWhileStmt(WhileStmt* W) { 1848 OS << "while " ; 1849 if (Stmt* C = W->getCond()) 1850 C->printPretty(OS, Helper, Policy); 1851 } 1852 1853 void VisitDoStmt(DoStmt* D) { 1854 OS << "do ... while "; 1855 if (Stmt* C = D->getCond()) 1856 C->printPretty(OS, Helper, Policy); 1857 } 1858 1859 void VisitSwitchStmt(SwitchStmt* Terminator) { 1860 OS << "switch "; 1861 Terminator->getCond()->printPretty(OS, Helper, Policy); 1862 } 1863 1864 void VisitCXXTryStmt(CXXTryStmt* CS) { 1865 OS << "try ..."; 1866 } 1867 1868 void VisitConditionalOperator(ConditionalOperator* C) { 1869 C->getCond()->printPretty(OS, Helper, Policy); 1870 OS << " ? ... : ..."; 1871 } 1872 1873 void VisitChooseExpr(ChooseExpr* C) { 1874 OS << "__builtin_choose_expr( "; 1875 C->getCond()->printPretty(OS, Helper, Policy); 1876 OS << " )"; 1877 } 1878 1879 void VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1880 OS << "goto *"; 1881 I->getTarget()->printPretty(OS, Helper, Policy); 1882 } 1883 1884 void VisitBinaryOperator(BinaryOperator* B) { 1885 if (!B->isLogicalOp()) { 1886 VisitExpr(B); 1887 return; 1888 } 1889 1890 B->getLHS()->printPretty(OS, Helper, Policy); 1891 1892 switch (B->getOpcode()) { 1893 case BinaryOperator::LOr: 1894 OS << " || ..."; 1895 return; 1896 case BinaryOperator::LAnd: 1897 OS << " && ..."; 1898 return; 1899 default: 1900 assert(false && "Invalid logical operator."); 1901 } 1902 } 1903 1904 void VisitExpr(Expr* E) { 1905 E->printPretty(OS, Helper, Policy); 1906 } 1907}; 1908} // end anonymous namespace 1909 1910 1911static void print_stmt(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, 1912 Stmt* Terminator) { 1913 if (Helper) { 1914 // special printing for statement-expressions. 1915 if (StmtExpr* SE = dyn_cast<StmtExpr>(Terminator)) { 1916 CompoundStmt* Sub = SE->getSubStmt(); 1917 1918 if (Sub->child_begin() != Sub->child_end()) { 1919 OS << "({ ... ; "; 1920 Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); 1921 OS << " })\n"; 1922 return; 1923 } 1924 } 1925 1926 // special printing for comma expressions. 1927 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Terminator)) { 1928 if (B->getOpcode() == BinaryOperator::Comma) { 1929 OS << "... , "; 1930 Helper->handledStmt(B->getRHS(),OS); 1931 OS << '\n'; 1932 return; 1933 } 1934 } 1935 } 1936 1937 Terminator->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 1938 1939 // Expressions need a newline. 1940 if (isa<Expr>(Terminator)) OS << '\n'; 1941} 1942 1943static void print_block(llvm::raw_ostream& OS, const CFG* cfg, 1944 const CFGBlock& B, 1945 StmtPrinterHelper* Helper, bool print_edges) { 1946 1947 if (Helper) Helper->setBlockID(B.getBlockID()); 1948 1949 // Print the header. 1950 OS << "\n [ B" << B.getBlockID(); 1951 1952 if (&B == &cfg->getEntry()) 1953 OS << " (ENTRY) ]\n"; 1954 else if (&B == &cfg->getExit()) 1955 OS << " (EXIT) ]\n"; 1956 else if (&B == cfg->getIndirectGotoBlock()) 1957 OS << " (INDIRECT GOTO DISPATCH) ]\n"; 1958 else 1959 OS << " ]\n"; 1960 1961 // Print the label of this block. 1962 if (Stmt* Terminator = const_cast<Stmt*>(B.getLabel())) { 1963 1964 if (print_edges) 1965 OS << " "; 1966 1967 if (LabelStmt* L = dyn_cast<LabelStmt>(Terminator)) 1968 OS << L->getName(); 1969 else if (CaseStmt* C = dyn_cast<CaseStmt>(Terminator)) { 1970 OS << "case "; 1971 C->getLHS()->printPretty(OS, Helper, 1972 PrintingPolicy(Helper->getLangOpts())); 1973 if (C->getRHS()) { 1974 OS << " ... "; 1975 C->getRHS()->printPretty(OS, Helper, 1976 PrintingPolicy(Helper->getLangOpts())); 1977 } 1978 } else if (isa<DefaultStmt>(Terminator)) 1979 OS << "default"; 1980 else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Terminator)) { 1981 OS << "catch ("; 1982 CS->getExceptionDecl()->print(OS, PrintingPolicy(Helper->getLangOpts()), 1983 0); 1984 OS << ")"; 1985 1986 } else 1987 assert(false && "Invalid label statement in CFGBlock."); 1988 1989 OS << ":\n"; 1990 } 1991 1992 // Iterate through the statements in the block and print them. 1993 unsigned j = 1; 1994 1995 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; 1996 I != E ; ++I, ++j ) { 1997 1998 // Print the statement # in the basic block and the statement itself. 1999 if (print_edges) 2000 OS << " "; 2001 2002 OS << llvm::format("%3d", j) << ": "; 2003 2004 if (Helper) 2005 Helper->setStmtID(j); 2006 2007 print_stmt(OS,Helper,*I); 2008 } 2009 2010 // Print the terminator of this block. 2011 if (B.getTerminator()) { 2012 if (print_edges) 2013 OS << " "; 2014 2015 OS << " T: "; 2016 2017 if (Helper) Helper->setBlockID(-1); 2018 2019 CFGBlockTerminatorPrint TPrinter(OS, Helper, 2020 PrintingPolicy(Helper->getLangOpts())); 2021 TPrinter.Visit(const_cast<Stmt*>(B.getTerminator())); 2022 OS << '\n'; 2023 } 2024 2025 if (print_edges) { 2026 // Print the predecessors of this block. 2027 OS << " Predecessors (" << B.pred_size() << "):"; 2028 unsigned i = 0; 2029 2030 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); 2031 I != E; ++I, ++i) { 2032 2033 if (i == 8 || (i-8) == 0) 2034 OS << "\n "; 2035 2036 OS << " B" << (*I)->getBlockID(); 2037 } 2038 2039 OS << '\n'; 2040 2041 // Print the successors of this block. 2042 OS << " Successors (" << B.succ_size() << "):"; 2043 i = 0; 2044 2045 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); 2046 I != E; ++I, ++i) { 2047 2048 if (i == 8 || (i-8) % 10 == 0) 2049 OS << "\n "; 2050 2051 if (*I) 2052 OS << " B" << (*I)->getBlockID(); 2053 else 2054 OS << " NULL"; 2055 } 2056 2057 OS << '\n'; 2058 } 2059} 2060 2061 2062/// dump - A simple pretty printer of a CFG that outputs to stderr. 2063void CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); } 2064 2065/// print - A simple pretty printer of a CFG that outputs to an ostream. 2066void CFG::print(llvm::raw_ostream &OS, const LangOptions &LO) const { 2067 StmtPrinterHelper Helper(this, LO); 2068 2069 // Print the entry block. 2070 print_block(OS, this, getEntry(), &Helper, true); 2071 2072 // Iterate through the CFGBlocks and print them one by one. 2073 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { 2074 // Skip the entry block, because we already printed it. 2075 if (&(**I) == &getEntry() || &(**I) == &getExit()) 2076 continue; 2077 2078 print_block(OS, this, **I, &Helper, true); 2079 } 2080 2081 // Print the exit block. 2082 print_block(OS, this, getExit(), &Helper, true); 2083 OS.flush(); 2084} 2085 2086/// dump - A simply pretty printer of a CFGBlock that outputs to stderr. 2087void CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const { 2088 print(llvm::errs(), cfg, LO); 2089} 2090 2091/// print - A simple pretty printer of a CFGBlock that outputs to an ostream. 2092/// Generally this will only be called from CFG::print. 2093void CFGBlock::print(llvm::raw_ostream& OS, const CFG* cfg, 2094 const LangOptions &LO) const { 2095 StmtPrinterHelper Helper(cfg, LO); 2096 print_block(OS, cfg, *this, &Helper, true); 2097} 2098 2099/// printTerminator - A simple pretty printer of the terminator of a CFGBlock. 2100void CFGBlock::printTerminator(llvm::raw_ostream &OS, 2101 const LangOptions &LO) const { 2102 CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); 2103 TPrinter.Visit(const_cast<Stmt*>(getTerminator())); 2104} 2105 2106Stmt* CFGBlock::getTerminatorCondition() { 2107 2108 if (!Terminator) 2109 return NULL; 2110 2111 Expr* E = NULL; 2112 2113 switch (Terminator->getStmtClass()) { 2114 default: 2115 break; 2116 2117 case Stmt::ForStmtClass: 2118 E = cast<ForStmt>(Terminator)->getCond(); 2119 break; 2120 2121 case Stmt::WhileStmtClass: 2122 E = cast<WhileStmt>(Terminator)->getCond(); 2123 break; 2124 2125 case Stmt::DoStmtClass: 2126 E = cast<DoStmt>(Terminator)->getCond(); 2127 break; 2128 2129 case Stmt::IfStmtClass: 2130 E = cast<IfStmt>(Terminator)->getCond(); 2131 break; 2132 2133 case Stmt::ChooseExprClass: 2134 E = cast<ChooseExpr>(Terminator)->getCond(); 2135 break; 2136 2137 case Stmt::IndirectGotoStmtClass: 2138 E = cast<IndirectGotoStmt>(Terminator)->getTarget(); 2139 break; 2140 2141 case Stmt::SwitchStmtClass: 2142 E = cast<SwitchStmt>(Terminator)->getCond(); 2143 break; 2144 2145 case Stmt::ConditionalOperatorClass: 2146 E = cast<ConditionalOperator>(Terminator)->getCond(); 2147 break; 2148 2149 case Stmt::BinaryOperatorClass: // '&&' and '||' 2150 E = cast<BinaryOperator>(Terminator)->getLHS(); 2151 break; 2152 2153 case Stmt::ObjCForCollectionStmtClass: 2154 return Terminator; 2155 } 2156 2157 return E ? E->IgnoreParens() : NULL; 2158} 2159 2160bool CFGBlock::hasBinaryBranchTerminator() const { 2161 2162 if (!Terminator) 2163 return false; 2164 2165 Expr* E = NULL; 2166 2167 switch (Terminator->getStmtClass()) { 2168 default: 2169 return false; 2170 2171 case Stmt::ForStmtClass: 2172 case Stmt::WhileStmtClass: 2173 case Stmt::DoStmtClass: 2174 case Stmt::IfStmtClass: 2175 case Stmt::ChooseExprClass: 2176 case Stmt::ConditionalOperatorClass: 2177 case Stmt::BinaryOperatorClass: 2178 return true; 2179 } 2180 2181 return E ? E->IgnoreParens() : NULL; 2182} 2183 2184 2185//===----------------------------------------------------------------------===// 2186// CFG Graphviz Visualization 2187//===----------------------------------------------------------------------===// 2188 2189 2190#ifndef NDEBUG 2191static StmtPrinterHelper* GraphHelper; 2192#endif 2193 2194void CFG::viewCFG(const LangOptions &LO) const { 2195#ifndef NDEBUG 2196 StmtPrinterHelper H(this, LO); 2197 GraphHelper = &H; 2198 llvm::ViewGraph(this,"CFG"); 2199 GraphHelper = NULL; 2200#endif 2201} 2202 2203namespace llvm { 2204template<> 2205struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { 2206 2207 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 2208 2209 static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph) { 2210 2211#ifndef NDEBUG 2212 std::string OutSStr; 2213 llvm::raw_string_ostream Out(OutSStr); 2214 print_block(Out,Graph, *Node, GraphHelper, false); 2215 std::string& OutStr = Out.str(); 2216 2217 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 2218 2219 // Process string output to make it nicer... 2220 for (unsigned i = 0; i != OutStr.length(); ++i) 2221 if (OutStr[i] == '\n') { // Left justify 2222 OutStr[i] = '\\'; 2223 OutStr.insert(OutStr.begin()+i+1, 'l'); 2224 } 2225 2226 return OutStr; 2227#else 2228 return ""; 2229#endif 2230 } 2231}; 2232} // end namespace llvm 2233