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