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