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