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