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