CFG.cpp revision 2455636163fdd18581d7fdae816433f886d88213
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 139 /// TryResult - a class representing a variant over the values 140 /// 'true', 'false', or 'unknown'. This is returned by TryEvaluateBool, 141 /// and is used by the CFGBuilder to decide if a branch condition 142 /// can be decided up front during CFG construction. 143 class TryResult { 144 int X; 145 public: 146 TryResult(bool b) : X(b ? 1 : 0) {} 147 TryResult() : X(-1) {} 148 149 bool isTrue() const { return X == 1; } 150 bool isFalse() const { return X == 0; } 151 bool isKnown() const { return X >= 0; } 152 void negate() { 153 assert(isKnown()); 154 X ^= 0x1; 155 } 156 }; 157 158 /// TryEvaluateBool - Try and evaluate the Stmt and return 0 or 1 159 /// if we can evaluate to a known value, otherwise return -1. 160 TryResult TryEvaluateBool(Expr *S) { 161 Expr::EvalResult Result; 162 if (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 - When the last statement has been added to the block, we must 274/// reverse the statements because they have been inserted in reverse order. 275bool CFGBuilder::FinishBlock(CFGBlock* B) { 276 if (badCFG) 277 return false; 278 279 assert(B); 280 B->reverseStmts(); 281 return true; 282} 283 284/// Visit - Walk the subtree of a statement and add extra 285/// blocks for ternary operators, &&, and ||. We also process "," and 286/// DeclStmts (which may contain nested control-flow). 287CFGBlock* CFGBuilder::Visit(Stmt * S, bool alwaysAdd) { 288tryAgain: 289 switch (S->getStmtClass()) { 290 default: 291 return VisitStmt(S, alwaysAdd); 292 293 case Stmt::AddrLabelExprClass: 294 return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), alwaysAdd); 295 296 case Stmt::BinaryOperatorClass: 297 return VisitBinaryOperator(cast<BinaryOperator>(S), alwaysAdd); 298 299 case Stmt::BlockExprClass: 300 return VisitBlockExpr(cast<BlockExpr>(S), alwaysAdd); 301 302 case Stmt::BlockDeclRefExprClass: 303 return VisitBlockDeclRefExpr(cast<BlockDeclRefExpr>(S), alwaysAdd); 304 305 case Stmt::BreakStmtClass: 306 return VisitBreakStmt(cast<BreakStmt>(S)); 307 308 case Stmt::CallExprClass: 309 return VisitCallExpr(cast<CallExpr>(S), alwaysAdd); 310 311 case Stmt::CaseStmtClass: 312 return VisitCaseStmt(cast<CaseStmt>(S)); 313 314 case Stmt::ChooseExprClass: 315 return VisitChooseExpr(cast<ChooseExpr>(S)); 316 317 case Stmt::CompoundStmtClass: 318 return VisitCompoundStmt(cast<CompoundStmt>(S)); 319 320 case Stmt::ConditionalOperatorClass: 321 return VisitConditionalOperator(cast<ConditionalOperator>(S)); 322 323 case Stmt::ContinueStmtClass: 324 return VisitContinueStmt(cast<ContinueStmt>(S)); 325 326 case Stmt::DeclStmtClass: 327 return VisitDeclStmt(cast<DeclStmt>(S)); 328 329 case Stmt::DefaultStmtClass: 330 return VisitDefaultStmt(cast<DefaultStmt>(S)); 331 332 case Stmt::DoStmtClass: 333 return VisitDoStmt(cast<DoStmt>(S)); 334 335 case Stmt::ForStmtClass: 336 return VisitForStmt(cast<ForStmt>(S)); 337 338 case Stmt::GotoStmtClass: 339 return VisitGotoStmt(cast<GotoStmt>(S)); 340 341 case Stmt::IfStmtClass: 342 return VisitIfStmt(cast<IfStmt>(S)); 343 344 case Stmt::IndirectGotoStmtClass: 345 return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S)); 346 347 case Stmt::LabelStmtClass: 348 return VisitLabelStmt(cast<LabelStmt>(S)); 349 350 case Stmt::ObjCAtCatchStmtClass: 351 return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S)); 352 353 case Stmt::CXXThrowExprClass: 354 return VisitCXXThrowExpr(cast<CXXThrowExpr>(S)); 355 356 case Stmt::ObjCAtSynchronizedStmtClass: 357 return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S)); 358 359 case Stmt::ObjCAtThrowStmtClass: 360 return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S)); 361 362 case Stmt::ObjCAtTryStmtClass: 363 return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S)); 364 365 case Stmt::ObjCForCollectionStmtClass: 366 return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S)); 367 368 case Stmt::ParenExprClass: 369 S = cast<ParenExpr>(S)->getSubExpr(); 370 goto tryAgain; 371 372 case Stmt::NullStmtClass: 373 return Block; 374 375 case Stmt::ReturnStmtClass: 376 return VisitReturnStmt(cast<ReturnStmt>(S)); 377 378 case Stmt::SizeOfAlignOfExprClass: 379 return VisitSizeOfAlignOfExpr(cast<SizeOfAlignOfExpr>(S), alwaysAdd); 380 381 case Stmt::StmtExprClass: 382 return VisitStmtExpr(cast<StmtExpr>(S), alwaysAdd); 383 384 case Stmt::SwitchStmtClass: 385 return VisitSwitchStmt(cast<SwitchStmt>(S)); 386 387 case Stmt::WhileStmtClass: 388 return VisitWhileStmt(cast<WhileStmt>(S)); 389 } 390} 391 392CFGBlock *CFGBuilder::VisitStmt(Stmt *S, bool alwaysAdd) { 393 if (alwaysAdd) { 394 autoCreateBlock(); 395 Block->appendStmt(S); 396 } 397 398 return VisitChildren(S); 399} 400 401/// VisitChildren - Visit the children of a Stmt. 402CFGBlock *CFGBuilder::VisitChildren(Stmt* Terminator) { 403 CFGBlock *B = Block; 404 for (Stmt::child_iterator I = Terminator->child_begin(), 405 E = Terminator->child_end(); I != E; ++I) { 406 if (*I) B = Visit(*I); 407 } 408 return B; 409} 410 411CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, bool alwaysAdd) { 412 AddressTakenLabels.insert(A->getLabel()); 413 414 if (alwaysAdd) { 415 autoCreateBlock(); 416 Block->appendStmt(A); 417 } 418 419 return Block; 420} 421 422CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, bool alwaysAdd) { 423 if (B->isLogicalOp()) { // && or || 424 CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 425 ConfluenceBlock->appendStmt(B); 426 427 if (!FinishBlock(ConfluenceBlock)) 428 return 0; 429 430 // create the block evaluating the LHS 431 CFGBlock* LHSBlock = createBlock(false); 432 LHSBlock->setTerminator(B); 433 434 // create the block evaluating the RHS 435 Succ = ConfluenceBlock; 436 Block = NULL; 437 CFGBlock* RHSBlock = addStmt(B->getRHS()); 438 if (!FinishBlock(RHSBlock)) 439 return 0; 440 441 // See if this is a known constant. 442 TryResult KnownVal = TryEvaluateBool(B->getLHS()); 443 if (KnownVal.isKnown() && (B->getOpcode() == BinaryOperator::LOr)) 444 KnownVal.negate(); 445 446 // Now link the LHSBlock with RHSBlock. 447 if (B->getOpcode() == BinaryOperator::LOr) { 448 LHSBlock->addSuccessor(KnownVal.isTrue() ? NULL : ConfluenceBlock); 449 LHSBlock->addSuccessor(KnownVal.isFalse() ? NULL : RHSBlock); 450 } else { 451 assert (B->getOpcode() == BinaryOperator::LAnd); 452 LHSBlock->addSuccessor(KnownVal.isFalse() ? NULL : RHSBlock); 453 LHSBlock->addSuccessor(KnownVal.isTrue() ? NULL : ConfluenceBlock); 454 } 455 456 // Generate the blocks for evaluating the LHS. 457 Block = LHSBlock; 458 return addStmt(B->getLHS()); 459 } 460 else if (B->getOpcode() == BinaryOperator::Comma) { // , 461 autoCreateBlock(); 462 Block->appendStmt(B); 463 addStmt(B->getRHS()); 464 return addStmt(B->getLHS()); 465 } 466 467 return VisitStmt(B, alwaysAdd); 468} 469 470CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr* E, bool alwaysAdd) { 471 // FIXME 472 return NYS(); 473} 474 475CFGBlock *CFGBuilder::VisitBlockDeclRefExpr(BlockDeclRefExpr* E, 476 bool alwaysAdd) { 477 // FIXME 478 return NYS(); 479} 480 481CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { 482 // "break" is a control-flow statement. Thus we stop processing the current 483 // block. 484 if (Block && !FinishBlock(Block)) 485 return 0; 486 487 // Now create a new block that ends with the break statement. 488 Block = createBlock(false); 489 Block->setTerminator(B); 490 491 // If there is no target for the break, then we are looking at an incomplete 492 // AST. This means that the CFG cannot be constructed. 493 if (BreakTargetBlock) 494 Block->addSuccessor(BreakTargetBlock); 495 else 496 badCFG = true; 497 498 499 return Block; 500} 501 502CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, bool alwaysAdd) { 503 // If this is a call to a no-return function, this stops the block here. 504 bool NoReturn = false; 505 if (C->getCallee()->getType().getNoReturnAttr()) { 506 NoReturn = true; 507 } 508 509 if (FunctionDecl *FD = C->getDirectCallee()) 510 if (FD->hasAttr<NoReturnAttr>()) 511 NoReturn = true; 512 513 if (!NoReturn) 514 return VisitStmt(C, alwaysAdd); 515 516 if (Block && !FinishBlock(Block)) 517 return 0; 518 519 // Create new block with no successor for the remaining pieces. 520 Block = createBlock(false); 521 Block->appendStmt(C); 522 523 // Wire this to the exit block directly. 524 Block->addSuccessor(&cfg->getExit()); 525 526 return VisitChildren(C); 527} 528 529CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C) { 530 CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 531 ConfluenceBlock->appendStmt(C); 532 if (!FinishBlock(ConfluenceBlock)) 533 return 0; 534 535 Succ = ConfluenceBlock; 536 Block = NULL; 537 CFGBlock* LHSBlock = addStmt(C->getLHS()); 538 if (!FinishBlock(LHSBlock)) 539 return 0; 540 541 Succ = ConfluenceBlock; 542 Block = NULL; 543 CFGBlock* RHSBlock = addStmt(C->getRHS()); 544 if (!FinishBlock(RHSBlock)) 545 return 0; 546 547 Block = createBlock(false); 548 // See if this is a known constant. 549 const TryResult& KnownVal = TryEvaluateBool(C->getCond()); 550 Block->addSuccessor(KnownVal.isFalse() ? NULL : LHSBlock); 551 Block->addSuccessor(KnownVal.isTrue() ? NULL : RHSBlock); 552 Block->setTerminator(C); 553 return addStmt(C->getCond()); 554} 555 556 557CFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) { 558 CFGBlock* LastBlock = Block; 559 560 for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); 561 I != E; ++I ) { 562 LastBlock = addStmt(*I); 563 } 564 return LastBlock; 565} 566 567CFGBlock *CFGBuilder::VisitConditionalOperator(ConditionalOperator *C) { 568 // Create the confluence block that will "merge" the results of the ternary 569 // expression. 570 CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 571 ConfluenceBlock->appendStmt(C); 572 if (!FinishBlock(ConfluenceBlock)) 573 return 0; 574 575 // Create a block for the LHS expression if there is an LHS expression. A 576 // GCC extension allows LHS to be NULL, causing the condition to be the 577 // value that is returned instead. 578 // e.g: x ?: y is shorthand for: x ? x : y; 579 Succ = ConfluenceBlock; 580 Block = NULL; 581 CFGBlock* LHSBlock = NULL; 582 if (C->getLHS()) { 583 LHSBlock = addStmt(C->getLHS()); 584 if (!FinishBlock(LHSBlock)) 585 return 0; 586 Block = NULL; 587 } 588 589 // Create the block for the RHS expression. 590 Succ = ConfluenceBlock; 591 CFGBlock* RHSBlock = addStmt(C->getRHS()); 592 if (!FinishBlock(RHSBlock)) 593 return 0; 594 595 // Create the block that will contain the condition. 596 Block = createBlock(false); 597 598 // See if this is a known constant. 599 const TryResult& KnownVal = TryEvaluateBool(C->getCond()); 600 if (LHSBlock) { 601 Block->addSuccessor(KnownVal.isFalse() ? NULL : LHSBlock); 602 } else { 603 if (KnownVal.isFalse()) { 604 // If we know the condition is false, add NULL as the successor for 605 // the block containing the condition. In this case, the confluence 606 // block will have just one predecessor. 607 Block->addSuccessor(0); 608 assert(ConfluenceBlock->pred_size() == 1); 609 } else { 610 // If we have no LHS expression, add the ConfluenceBlock as a direct 611 // successor for the block containing the condition. Moreover, we need to 612 // reverse the order of the predecessors in the ConfluenceBlock because 613 // the RHSBlock will have been added to the succcessors already, and we 614 // want the first predecessor to the the block containing the expression 615 // for the case when the ternary expression evaluates to true. 616 Block->addSuccessor(ConfluenceBlock); 617 assert(ConfluenceBlock->pred_size() == 2); 618 std::reverse(ConfluenceBlock->pred_begin(), 619 ConfluenceBlock->pred_end()); 620 } 621 } 622 623 Block->addSuccessor(KnownVal.isTrue() ? NULL : RHSBlock); 624 Block->setTerminator(C); 625 return addStmt(C->getCond()); 626} 627 628CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) { 629 autoCreateBlock(); 630 631 if (DS->isSingleDecl()) { 632 Block->appendStmt(DS); 633 return VisitDeclSubExpr(DS->getSingleDecl()); 634 } 635 636 CFGBlock *B = 0; 637 638 // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy. 639 typedef llvm::SmallVector<Decl*,10> BufTy; 640 BufTy Buf(DS->decl_begin(), DS->decl_end()); 641 642 for (BufTy::reverse_iterator I = Buf.rbegin(), E = Buf.rend(); I != E; ++I) { 643 // Get the alignment of the new DeclStmt, padding out to >=8 bytes. 644 unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8 645 ? 8 : llvm::AlignOf<DeclStmt>::Alignment; 646 647 // Allocate the DeclStmt using the BumpPtrAllocator. It will get 648 // automatically freed with the CFG. 649 DeclGroupRef DG(*I); 650 Decl *D = *I; 651 void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A); 652 DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); 653 654 // Append the fake DeclStmt to block. 655 Block->appendStmt(DSNew); 656 B = VisitDeclSubExpr(D); 657 } 658 659 return B; 660} 661 662/// VisitDeclSubExpr - Utility method to add block-level expressions for 663/// initializers in Decls. 664CFGBlock *CFGBuilder::VisitDeclSubExpr(Decl* D) { 665 assert(Block); 666 667 VarDecl *VD = dyn_cast<VarDecl>(D); 668 669 if (!VD) 670 return Block; 671 672 Expr *Init = VD->getInit(); 673 674 if (Init) { 675 // Optimization: Don't create separate block-level statements for literals. 676 switch (Init->getStmtClass()) { 677 case Stmt::IntegerLiteralClass: 678 case Stmt::CharacterLiteralClass: 679 case Stmt::StringLiteralClass: 680 break; 681 default: 682 Block = addStmt(Init); 683 } 684 } 685 686 // If the type of VD is a VLA, then we must process its size expressions. 687 for (VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); VA != 0; 688 VA = FindVA(VA->getElementType().getTypePtr())) 689 Block = addStmt(VA->getSizeExpr()); 690 691 return Block; 692} 693 694CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { 695 // We may see an if statement in the middle of a basic block, or it may be the 696 // first statement we are processing. In either case, we create a new basic 697 // block. First, we create the blocks for the then...else statements, and 698 // then we create the block containing the if statement. If we were in the 699 // middle of a block, we stop processing that block and reverse its 700 // statements. That block is then the implicit successor for the "then" and 701 // "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 and 773 // reverse its statements. 774 // 775 // NOTE: If a "return" appears in the middle of a block, this means that the 776 // code afterwards is DEAD (unreachable). We still keep a basic block 777 // for that code; a simple "mark-and-sweep" from the entry block will be 778 // able to report such dead blocks. 779 if (Block) 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 = EntryConditionBlock; // 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 = EntryConditionBlock; // 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 and 1184 // reverse its statements. 1185 if (Block && !FinishBlock(Block)) 1186 return 0; 1187 1188 // Create the new block. 1189 Block = createBlock(false); 1190 1191 // The Exit block is the only successor. 1192 Block->addSuccessor(&cfg->getExit()); 1193 1194 // Add the statement to the block. This may create new blocks if S contains 1195 // control-flow (short-circuit operations). 1196 return VisitStmt(S, true); 1197} 1198 1199CFGBlock* CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr* T) { 1200 // If we were in the middle of a block we stop processing that block and 1201 // reverse its statements. 1202 if (Block && !FinishBlock(Block)) 1203 return 0; 1204 1205 // Create the new block. 1206 Block = createBlock(false); 1207 1208 // The Exit block is the only successor. 1209 Block->addSuccessor(&cfg->getExit()); 1210 1211 // Add the statement to the block. This may create new blocks if S contains 1212 // control-flow (short-circuit operations). 1213 return VisitStmt(T, true); 1214} 1215 1216CFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { 1217 CFGBlock* LoopSuccessor = NULL; 1218 1219 // "do...while" is a control-flow statement. Thus we stop processing the 1220 // current block. 1221 if (Block) { 1222 if (!FinishBlock(Block)) 1223 return 0; 1224 LoopSuccessor = Block; 1225 } else 1226 LoopSuccessor = Succ; 1227 1228 // Because of short-circuit evaluation, the condition of the loop can span 1229 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1230 // evaluate the condition. 1231 CFGBlock* ExitConditionBlock = createBlock(false); 1232 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1233 1234 // Set the terminator for the "exit" condition block. 1235 ExitConditionBlock->setTerminator(D); 1236 1237 // Now add the actual condition to the condition block. Because the condition 1238 // itself may contain control-flow, new blocks may be created. 1239 if (Stmt* C = D->getCond()) { 1240 Block = ExitConditionBlock; 1241 EntryConditionBlock = addStmt(C); 1242 if (Block) { 1243 if (!FinishBlock(EntryConditionBlock)) 1244 return 0; 1245 } 1246 } 1247 1248 // The condition block is the implicit successor for the loop body. 1249 Succ = EntryConditionBlock; 1250 1251 // See if this is a known constant. 1252 const TryResult &KnownVal = TryEvaluateBool(D->getCond()); 1253 1254 // Process the loop body. 1255 CFGBlock* BodyBlock = NULL; 1256 { 1257 assert (D->getBody()); 1258 1259 // Save the current values for Block, Succ, and continue and break targets 1260 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1261 save_continue(ContinueTargetBlock), 1262 save_break(BreakTargetBlock); 1263 1264 // All continues within this loop should go to the condition block 1265 ContinueTargetBlock = EntryConditionBlock; 1266 1267 // All breaks should go to the code following the loop. 1268 BreakTargetBlock = LoopSuccessor; 1269 1270 // NULL out Block to force lazy instantiation of blocks for the body. 1271 Block = NULL; 1272 1273 // Create the body. The returned block is the entry to the loop body. 1274 BodyBlock = addStmt(D->getBody()); 1275 1276 if (!BodyBlock) 1277 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" 1278 else if (Block) { 1279 if (!FinishBlock(BodyBlock)) 1280 return 0; 1281 } 1282 1283 // Add an intermediate block between the BodyBlock and the 1284 // ExitConditionBlock to represent the "loop back" transition. Create an 1285 // empty block to represent the transition block for looping back to the 1286 // head of the loop. 1287 // FIXME: Can we do this more efficiently without adding another block? 1288 Block = NULL; 1289 Succ = BodyBlock; 1290 CFGBlock *LoopBackBlock = createBlock(); 1291 LoopBackBlock->setLoopTarget(D); 1292 1293 // Add the loop body entry as a successor to the condition. 1294 ExitConditionBlock->addSuccessor(KnownVal.isFalse() ? NULL : LoopBackBlock); 1295 } 1296 1297 // Link up the condition block with the code that follows the loop. 1298 // (the false branch). 1299 ExitConditionBlock->addSuccessor(KnownVal.isTrue() ? NULL : LoopSuccessor); 1300 1301 // There can be no more statements in the body block(s) since we loop back to 1302 // the body. NULL out Block to force lazy creation of another block. 1303 Block = NULL; 1304 1305 // Return the loop body, which is the dominating block for the loop. 1306 Succ = BodyBlock; 1307 return BodyBlock; 1308} 1309 1310CFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) { 1311 // "continue" is a control-flow statement. Thus we stop processing the 1312 // current block. 1313 if (Block && !FinishBlock(Block)) 1314 return 0; 1315 1316 // Now create a new block that ends with the continue statement. 1317 Block = createBlock(false); 1318 Block->setTerminator(C); 1319 1320 // If there is no target for the continue, then we are looking at an 1321 // incomplete AST. This means the CFG cannot be constructed. 1322 if (ContinueTargetBlock) 1323 Block->addSuccessor(ContinueTargetBlock); 1324 else 1325 badCFG = true; 1326 1327 return Block; 1328} 1329 1330CFGBlock *CFGBuilder::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, 1331 bool alwaysAdd) { 1332 1333 if (alwaysAdd) { 1334 autoCreateBlock(); 1335 Block->appendStmt(E); 1336 } 1337 1338 // VLA types have expressions that must be evaluated. 1339 if (E->isArgumentType()) { 1340 for (VariableArrayType* VA = FindVA(E->getArgumentType().getTypePtr()); 1341 VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) 1342 addStmt(VA->getSizeExpr()); 1343 } 1344 1345 return Block; 1346} 1347 1348/// VisitStmtExpr - Utility method to handle (nested) statement 1349/// expressions (a GCC extension). 1350CFGBlock* CFGBuilder::VisitStmtExpr(StmtExpr *SE, bool alwaysAdd) { 1351 if (alwaysAdd) { 1352 autoCreateBlock(); 1353 Block->appendStmt(SE); 1354 } 1355 return VisitCompoundStmt(SE->getSubStmt()); 1356} 1357 1358CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { 1359 // "switch" is a control-flow statement. Thus we stop processing the current 1360 // block. 1361 CFGBlock* SwitchSuccessor = NULL; 1362 1363 if (Block) { 1364 if (!FinishBlock(Block)) 1365 return 0; 1366 SwitchSuccessor = Block; 1367 } else SwitchSuccessor = Succ; 1368 1369 // Save the current "switch" context. 1370 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), 1371 save_break(BreakTargetBlock), 1372 save_default(DefaultCaseBlock); 1373 1374 // Set the "default" case to be the block after the switch statement. If the 1375 // switch statement contains a "default:", this value will be overwritten with 1376 // the block for that code. 1377 DefaultCaseBlock = SwitchSuccessor; 1378 1379 // Create a new block that will contain the switch statement. 1380 SwitchTerminatedBlock = createBlock(false); 1381 1382 // Now process the switch body. The code after the switch is the implicit 1383 // successor. 1384 Succ = SwitchSuccessor; 1385 BreakTargetBlock = SwitchSuccessor; 1386 1387 // When visiting the body, the case statements should automatically get linked 1388 // up to the switch. We also don't keep a pointer to the body, since all 1389 // control-flow from the switch goes to case/default statements. 1390 assert (Terminator->getBody() && "switch must contain a non-NULL body"); 1391 Block = NULL; 1392 CFGBlock *BodyBlock = addStmt(Terminator->getBody()); 1393 if (Block) { 1394 if (!FinishBlock(BodyBlock)) 1395 return 0; 1396 } 1397 1398 // If we have no "default:" case, the default transition is to the code 1399 // following the switch body. 1400 SwitchTerminatedBlock->addSuccessor(DefaultCaseBlock); 1401 1402 // Add the terminator and condition in the switch block. 1403 SwitchTerminatedBlock->setTerminator(Terminator); 1404 assert (Terminator->getCond() && "switch condition must be non-NULL"); 1405 Block = SwitchTerminatedBlock; 1406 1407 return addStmt(Terminator->getCond()); 1408} 1409 1410CFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) { 1411 // CaseStmts are essentially labels, so they are the first statement in a 1412 // block. 1413 1414 if (CS->getSubStmt()) 1415 addStmt(CS->getSubStmt()); 1416 1417 CFGBlock* CaseBlock = Block; 1418 if (!CaseBlock) 1419 CaseBlock = createBlock(); 1420 1421 // Cases statements partition blocks, so this is the top of the basic block we 1422 // were processing (the "case XXX:" is the label). 1423 CaseBlock->setLabel(CS); 1424 1425 if (!FinishBlock(CaseBlock)) 1426 return 0; 1427 1428 // Add this block to the list of successors for the block with the switch 1429 // statement. 1430 assert(SwitchTerminatedBlock); 1431 SwitchTerminatedBlock->addSuccessor(CaseBlock); 1432 1433 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1434 Block = NULL; 1435 1436 // This block is now the implicit successor of other blocks. 1437 Succ = CaseBlock; 1438 1439 return CaseBlock; 1440} 1441 1442CFGBlock* CFGBuilder::VisitDefaultStmt(DefaultStmt* Terminator) { 1443 if (Terminator->getSubStmt()) 1444 addStmt(Terminator->getSubStmt()); 1445 1446 DefaultCaseBlock = Block; 1447 1448 if (!DefaultCaseBlock) 1449 DefaultCaseBlock = createBlock(); 1450 1451 // Default statements partition blocks, so this is the top of the basic block 1452 // we were processing (the "default:" is the label). 1453 DefaultCaseBlock->setLabel(Terminator); 1454 1455 if (!FinishBlock(DefaultCaseBlock)) 1456 return 0; 1457 1458 // Unlike case statements, we don't add the default block to the successors 1459 // for the switch statement immediately. This is done when we finish 1460 // processing the switch statement. This allows for the default case 1461 // (including a fall-through to the code after the switch statement) to always 1462 // be the last successor of a switch-terminated block. 1463 1464 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1465 Block = NULL; 1466 1467 // This block is now the implicit successor of other blocks. 1468 Succ = DefaultCaseBlock; 1469 1470 return DefaultCaseBlock; 1471} 1472 1473CFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1474 // Lazily create the indirect-goto dispatch block if there isn't one already. 1475 CFGBlock* IBlock = cfg->getIndirectGotoBlock(); 1476 1477 if (!IBlock) { 1478 IBlock = createBlock(false); 1479 cfg->setIndirectGotoBlock(IBlock); 1480 } 1481 1482 // IndirectGoto is a control-flow statement. Thus we stop processing the 1483 // current block and create a new one. 1484 if (Block && !FinishBlock(Block)) 1485 return 0; 1486 1487 Block = createBlock(false); 1488 Block->setTerminator(I); 1489 Block->addSuccessor(IBlock); 1490 return addStmt(I->getTarget()); 1491} 1492 1493} // end anonymous namespace 1494 1495/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has 1496/// no successors or predecessors. If this is the first block created in the 1497/// CFG, it is automatically set to be the Entry and Exit of the CFG. 1498CFGBlock* CFG::createBlock() { 1499 bool first_block = begin() == end(); 1500 1501 // Create the block. 1502 Blocks.push_front(CFGBlock(NumBlockIDs++)); 1503 1504 // If this is the first block, set it as the Entry and Exit. 1505 if (first_block) Entry = Exit = &front(); 1506 1507 // Return the block. 1508 return &front(); 1509} 1510 1511/// buildCFG - Constructs a CFG from an AST. Ownership of the returned 1512/// CFG is returned to the caller. 1513CFG* CFG::buildCFG(Stmt* Statement, ASTContext *C) { 1514 CFGBuilder Builder; 1515 return Builder.buildCFG(Statement, C); 1516} 1517 1518/// reverseStmts - Reverses the orders of statements within a CFGBlock. 1519void CFGBlock::reverseStmts() { std::reverse(Stmts.begin(),Stmts.end()); } 1520 1521//===----------------------------------------------------------------------===// 1522// CFG: Queries for BlkExprs. 1523//===----------------------------------------------------------------------===// 1524 1525namespace { 1526 typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy; 1527} 1528 1529static void FindSubExprAssignments(Stmt* Terminator, llvm::SmallPtrSet<Expr*,50>& Set) { 1530 if (!Terminator) 1531 return; 1532 1533 for (Stmt::child_iterator I=Terminator->child_begin(), E=Terminator->child_end(); I!=E; ++I) { 1534 if (!*I) continue; 1535 1536 if (BinaryOperator* B = dyn_cast<BinaryOperator>(*I)) 1537 if (B->isAssignmentOp()) Set.insert(B); 1538 1539 FindSubExprAssignments(*I, Set); 1540 } 1541} 1542 1543static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { 1544 BlkExprMapTy* M = new BlkExprMapTy(); 1545 1546 // Look for assignments that are used as subexpressions. These are the only 1547 // assignments that we want to *possibly* register as a block-level 1548 // expression. Basically, if an assignment occurs both in a subexpression and 1549 // at the block-level, it is a block-level expression. 1550 llvm::SmallPtrSet<Expr*,50> SubExprAssignments; 1551 1552 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) 1553 for (CFGBlock::iterator BI=I->begin(), EI=I->end(); BI != EI; ++BI) 1554 FindSubExprAssignments(*BI, SubExprAssignments); 1555 1556 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { 1557 1558 // Iterate over the statements again on identify the Expr* and Stmt* at the 1559 // block-level that are block-level expressions. 1560 1561 for (CFGBlock::iterator BI=I->begin(), EI=I->end(); BI != EI; ++BI) 1562 if (Expr* Exp = dyn_cast<Expr>(*BI)) { 1563 1564 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { 1565 // Assignment expressions that are not nested within another 1566 // expression are really "statements" whose value is never used by 1567 // another expression. 1568 if (B->isAssignmentOp() && !SubExprAssignments.count(Exp)) 1569 continue; 1570 } else if (const StmtExpr* Terminator = dyn_cast<StmtExpr>(Exp)) { 1571 // Special handling for statement expressions. The last statement in 1572 // the statement expression is also a block-level expr. 1573 const CompoundStmt* C = Terminator->getSubStmt(); 1574 if (!C->body_empty()) { 1575 unsigned x = M->size(); 1576 (*M)[C->body_back()] = x; 1577 } 1578 } 1579 1580 unsigned x = M->size(); 1581 (*M)[Exp] = x; 1582 } 1583 1584 // Look at terminators. The condition is a block-level expression. 1585 1586 Stmt* S = I->getTerminatorCondition(); 1587 1588 if (S && M->find(S) == M->end()) { 1589 unsigned x = M->size(); 1590 (*M)[S] = x; 1591 } 1592 } 1593 1594 return M; 1595} 1596 1597CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) { 1598 assert(S != NULL); 1599 if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } 1600 1601 BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap); 1602 BlkExprMapTy::iterator I = M->find(S); 1603 1604 if (I == M->end()) return CFG::BlkExprNumTy(); 1605 else return CFG::BlkExprNumTy(I->second); 1606} 1607 1608unsigned CFG::getNumBlkExprs() { 1609 if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) 1610 return M->size(); 1611 else { 1612 // We assume callers interested in the number of BlkExprs will want 1613 // the map constructed if it doesn't already exist. 1614 BlkExprMap = (void*) PopulateBlkExprMap(*this); 1615 return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); 1616 } 1617} 1618 1619//===----------------------------------------------------------------------===// 1620// Cleanup: CFG dstor. 1621//===----------------------------------------------------------------------===// 1622 1623CFG::~CFG() { 1624 delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); 1625} 1626 1627//===----------------------------------------------------------------------===// 1628// CFG pretty printing 1629//===----------------------------------------------------------------------===// 1630 1631namespace { 1632 1633class VISIBILITY_HIDDEN StmtPrinterHelper : public PrinterHelper { 1634 1635 typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; 1636 StmtMapTy StmtMap; 1637 signed CurrentBlock; 1638 unsigned CurrentStmt; 1639 const LangOptions &LangOpts; 1640public: 1641 1642 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) 1643 : CurrentBlock(0), CurrentStmt(0), LangOpts(LO) { 1644 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { 1645 unsigned j = 1; 1646 for (CFGBlock::const_iterator BI = I->begin(), BEnd = I->end() ; 1647 BI != BEnd; ++BI, ++j ) 1648 StmtMap[*BI] = std::make_pair(I->getBlockID(),j); 1649 } 1650 } 1651 1652 virtual ~StmtPrinterHelper() {} 1653 1654 const LangOptions &getLangOpts() const { return LangOpts; } 1655 void setBlockID(signed i) { CurrentBlock = i; } 1656 void setStmtID(unsigned i) { CurrentStmt = i; } 1657 1658 virtual bool handledStmt(Stmt* Terminator, llvm::raw_ostream& OS) { 1659 1660 StmtMapTy::iterator I = StmtMap.find(Terminator); 1661 1662 if (I == StmtMap.end()) 1663 return false; 1664 1665 if (CurrentBlock >= 0 && I->second.first == (unsigned) CurrentBlock 1666 && I->second.second == CurrentStmt) 1667 return false; 1668 1669 OS << "[B" << I->second.first << "." << I->second.second << "]"; 1670 return true; 1671 } 1672}; 1673} // end anonymous namespace 1674 1675 1676namespace { 1677class VISIBILITY_HIDDEN CFGBlockTerminatorPrint 1678 : public StmtVisitor<CFGBlockTerminatorPrint,void> { 1679 1680 llvm::raw_ostream& OS; 1681 StmtPrinterHelper* Helper; 1682 PrintingPolicy Policy; 1683 1684public: 1685 CFGBlockTerminatorPrint(llvm::raw_ostream& os, StmtPrinterHelper* helper, 1686 const PrintingPolicy &Policy) 1687 : OS(os), Helper(helper), Policy(Policy) {} 1688 1689 void VisitIfStmt(IfStmt* I) { 1690 OS << "if "; 1691 I->getCond()->printPretty(OS,Helper,Policy); 1692 } 1693 1694 // Default case. 1695 void VisitStmt(Stmt* Terminator) { 1696 Terminator->printPretty(OS, Helper, Policy); 1697 } 1698 1699 void VisitForStmt(ForStmt* F) { 1700 OS << "for (" ; 1701 if (F->getInit()) OS << "..."; 1702 OS << "; "; 1703 if (Stmt* C = F->getCond()) C->printPretty(OS, Helper, Policy); 1704 OS << "; "; 1705 if (F->getInc()) OS << "..."; 1706 OS << ")"; 1707 } 1708 1709 void VisitWhileStmt(WhileStmt* W) { 1710 OS << "while " ; 1711 if (Stmt* C = W->getCond()) C->printPretty(OS, Helper, Policy); 1712 } 1713 1714 void VisitDoStmt(DoStmt* D) { 1715 OS << "do ... while "; 1716 if (Stmt* C = D->getCond()) C->printPretty(OS, Helper, Policy); 1717 } 1718 1719 void VisitSwitchStmt(SwitchStmt* Terminator) { 1720 OS << "switch "; 1721 Terminator->getCond()->printPretty(OS, Helper, Policy); 1722 } 1723 1724 void VisitConditionalOperator(ConditionalOperator* C) { 1725 C->getCond()->printPretty(OS, Helper, Policy); 1726 OS << " ? ... : ..."; 1727 } 1728 1729 void VisitChooseExpr(ChooseExpr* C) { 1730 OS << "__builtin_choose_expr( "; 1731 C->getCond()->printPretty(OS, Helper, Policy); 1732 OS << " )"; 1733 } 1734 1735 void VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1736 OS << "goto *"; 1737 I->getTarget()->printPretty(OS, Helper, Policy); 1738 } 1739 1740 void VisitBinaryOperator(BinaryOperator* B) { 1741 if (!B->isLogicalOp()) { 1742 VisitExpr(B); 1743 return; 1744 } 1745 1746 B->getLHS()->printPretty(OS, Helper, Policy); 1747 1748 switch (B->getOpcode()) { 1749 case BinaryOperator::LOr: 1750 OS << " || ..."; 1751 return; 1752 case BinaryOperator::LAnd: 1753 OS << " && ..."; 1754 return; 1755 default: 1756 assert(false && "Invalid logical operator."); 1757 } 1758 } 1759 1760 void VisitExpr(Expr* E) { 1761 E->printPretty(OS, Helper, Policy); 1762 } 1763}; 1764} // end anonymous namespace 1765 1766 1767static void print_stmt(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, 1768 Stmt* Terminator) { 1769 if (Helper) { 1770 // special printing for statement-expressions. 1771 if (StmtExpr* SE = dyn_cast<StmtExpr>(Terminator)) { 1772 CompoundStmt* Sub = SE->getSubStmt(); 1773 1774 if (Sub->child_begin() != Sub->child_end()) { 1775 OS << "({ ... ; "; 1776 Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); 1777 OS << " })\n"; 1778 return; 1779 } 1780 } 1781 1782 // special printing for comma expressions. 1783 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Terminator)) { 1784 if (B->getOpcode() == BinaryOperator::Comma) { 1785 OS << "... , "; 1786 Helper->handledStmt(B->getRHS(),OS); 1787 OS << '\n'; 1788 return; 1789 } 1790 } 1791 } 1792 1793 Terminator->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 1794 1795 // Expressions need a newline. 1796 if (isa<Expr>(Terminator)) OS << '\n'; 1797} 1798 1799static void print_block(llvm::raw_ostream& OS, const CFG* cfg, 1800 const CFGBlock& B, 1801 StmtPrinterHelper* Helper, bool print_edges) { 1802 1803 if (Helper) Helper->setBlockID(B.getBlockID()); 1804 1805 // Print the header. 1806 OS << "\n [ B" << B.getBlockID(); 1807 1808 if (&B == &cfg->getEntry()) 1809 OS << " (ENTRY) ]\n"; 1810 else if (&B == &cfg->getExit()) 1811 OS << " (EXIT) ]\n"; 1812 else if (&B == cfg->getIndirectGotoBlock()) 1813 OS << " (INDIRECT GOTO DISPATCH) ]\n"; 1814 else 1815 OS << " ]\n"; 1816 1817 // Print the label of this block. 1818 if (Stmt* Terminator = const_cast<Stmt*>(B.getLabel())) { 1819 1820 if (print_edges) 1821 OS << " "; 1822 1823 if (LabelStmt* L = dyn_cast<LabelStmt>(Terminator)) 1824 OS << L->getName(); 1825 else if (CaseStmt* C = dyn_cast<CaseStmt>(Terminator)) { 1826 OS << "case "; 1827 C->getLHS()->printPretty(OS, Helper, 1828 PrintingPolicy(Helper->getLangOpts())); 1829 if (C->getRHS()) { 1830 OS << " ... "; 1831 C->getRHS()->printPretty(OS, Helper, 1832 PrintingPolicy(Helper->getLangOpts())); 1833 } 1834 } else if (isa<DefaultStmt>(Terminator)) 1835 OS << "default"; 1836 else 1837 assert(false && "Invalid label statement in CFGBlock."); 1838 1839 OS << ":\n"; 1840 } 1841 1842 // Iterate through the statements in the block and print them. 1843 unsigned j = 1; 1844 1845 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; 1846 I != E ; ++I, ++j ) { 1847 1848 // Print the statement # in the basic block and the statement itself. 1849 if (print_edges) 1850 OS << " "; 1851 1852 OS << llvm::format("%3d", j) << ": "; 1853 1854 if (Helper) 1855 Helper->setStmtID(j); 1856 1857 print_stmt(OS,Helper,*I); 1858 } 1859 1860 // Print the terminator of this block. 1861 if (B.getTerminator()) { 1862 if (print_edges) 1863 OS << " "; 1864 1865 OS << " T: "; 1866 1867 if (Helper) Helper->setBlockID(-1); 1868 1869 CFGBlockTerminatorPrint TPrinter(OS, Helper, 1870 PrintingPolicy(Helper->getLangOpts())); 1871 TPrinter.Visit(const_cast<Stmt*>(B.getTerminator())); 1872 OS << '\n'; 1873 } 1874 1875 if (print_edges) { 1876 // Print the predecessors of this block. 1877 OS << " Predecessors (" << B.pred_size() << "):"; 1878 unsigned i = 0; 1879 1880 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); 1881 I != E; ++I, ++i) { 1882 1883 if (i == 8 || (i-8) == 0) 1884 OS << "\n "; 1885 1886 OS << " B" << (*I)->getBlockID(); 1887 } 1888 1889 OS << '\n'; 1890 1891 // Print the successors of this block. 1892 OS << " Successors (" << B.succ_size() << "):"; 1893 i = 0; 1894 1895 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); 1896 I != E; ++I, ++i) { 1897 1898 if (i == 8 || (i-8) % 10 == 0) 1899 OS << "\n "; 1900 1901 if (*I) 1902 OS << " B" << (*I)->getBlockID(); 1903 else 1904 OS << " NULL"; 1905 } 1906 1907 OS << '\n'; 1908 } 1909} 1910 1911 1912/// dump - A simple pretty printer of a CFG that outputs to stderr. 1913void CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); } 1914 1915/// print - A simple pretty printer of a CFG that outputs to an ostream. 1916void CFG::print(llvm::raw_ostream &OS, const LangOptions &LO) const { 1917 StmtPrinterHelper Helper(this, LO); 1918 1919 // Print the entry block. 1920 print_block(OS, this, getEntry(), &Helper, true); 1921 1922 // Iterate through the CFGBlocks and print them one by one. 1923 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { 1924 // Skip the entry block, because we already printed it. 1925 if (&(*I) == &getEntry() || &(*I) == &getExit()) 1926 continue; 1927 1928 print_block(OS, this, *I, &Helper, true); 1929 } 1930 1931 // Print the exit block. 1932 print_block(OS, this, getExit(), &Helper, true); 1933 OS.flush(); 1934} 1935 1936/// dump - A simply pretty printer of a CFGBlock that outputs to stderr. 1937void CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const { 1938 print(llvm::errs(), cfg, LO); 1939} 1940 1941/// print - A simple pretty printer of a CFGBlock that outputs to an ostream. 1942/// Generally this will only be called from CFG::print. 1943void CFGBlock::print(llvm::raw_ostream& OS, const CFG* cfg, 1944 const LangOptions &LO) const { 1945 StmtPrinterHelper Helper(cfg, LO); 1946 print_block(OS, cfg, *this, &Helper, true); 1947} 1948 1949/// printTerminator - A simple pretty printer of the terminator of a CFGBlock. 1950void CFGBlock::printTerminator(llvm::raw_ostream &OS, 1951 const LangOptions &LO) const { 1952 CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); 1953 TPrinter.Visit(const_cast<Stmt*>(getTerminator())); 1954} 1955 1956Stmt* CFGBlock::getTerminatorCondition() { 1957 1958 if (!Terminator) 1959 return NULL; 1960 1961 Expr* E = NULL; 1962 1963 switch (Terminator->getStmtClass()) { 1964 default: 1965 break; 1966 1967 case Stmt::ForStmtClass: 1968 E = cast<ForStmt>(Terminator)->getCond(); 1969 break; 1970 1971 case Stmt::WhileStmtClass: 1972 E = cast<WhileStmt>(Terminator)->getCond(); 1973 break; 1974 1975 case Stmt::DoStmtClass: 1976 E = cast<DoStmt>(Terminator)->getCond(); 1977 break; 1978 1979 case Stmt::IfStmtClass: 1980 E = cast<IfStmt>(Terminator)->getCond(); 1981 break; 1982 1983 case Stmt::ChooseExprClass: 1984 E = cast<ChooseExpr>(Terminator)->getCond(); 1985 break; 1986 1987 case Stmt::IndirectGotoStmtClass: 1988 E = cast<IndirectGotoStmt>(Terminator)->getTarget(); 1989 break; 1990 1991 case Stmt::SwitchStmtClass: 1992 E = cast<SwitchStmt>(Terminator)->getCond(); 1993 break; 1994 1995 case Stmt::ConditionalOperatorClass: 1996 E = cast<ConditionalOperator>(Terminator)->getCond(); 1997 break; 1998 1999 case Stmt::BinaryOperatorClass: // '&&' and '||' 2000 E = cast<BinaryOperator>(Terminator)->getLHS(); 2001 break; 2002 2003 case Stmt::ObjCForCollectionStmtClass: 2004 return Terminator; 2005 } 2006 2007 return E ? E->IgnoreParens() : NULL; 2008} 2009 2010bool CFGBlock::hasBinaryBranchTerminator() const { 2011 2012 if (!Terminator) 2013 return false; 2014 2015 Expr* E = NULL; 2016 2017 switch (Terminator->getStmtClass()) { 2018 default: 2019 return false; 2020 2021 case Stmt::ForStmtClass: 2022 case Stmt::WhileStmtClass: 2023 case Stmt::DoStmtClass: 2024 case Stmt::IfStmtClass: 2025 case Stmt::ChooseExprClass: 2026 case Stmt::ConditionalOperatorClass: 2027 case Stmt::BinaryOperatorClass: 2028 return true; 2029 } 2030 2031 return E ? E->IgnoreParens() : NULL; 2032} 2033 2034 2035//===----------------------------------------------------------------------===// 2036// CFG Graphviz Visualization 2037//===----------------------------------------------------------------------===// 2038 2039 2040#ifndef NDEBUG 2041static StmtPrinterHelper* GraphHelper; 2042#endif 2043 2044void CFG::viewCFG(const LangOptions &LO) const { 2045#ifndef NDEBUG 2046 StmtPrinterHelper H(this, LO); 2047 GraphHelper = &H; 2048 llvm::ViewGraph(this,"CFG"); 2049 GraphHelper = NULL; 2050#endif 2051} 2052 2053namespace llvm { 2054template<> 2055struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { 2056 static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph, 2057 bool ShortNames) { 2058 2059#ifndef NDEBUG 2060 std::string OutSStr; 2061 llvm::raw_string_ostream Out(OutSStr); 2062 print_block(Out,Graph, *Node, GraphHelper, false); 2063 std::string& OutStr = Out.str(); 2064 2065 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 2066 2067 // Process string output to make it nicer... 2068 for (unsigned i = 0; i != OutStr.length(); ++i) 2069 if (OutStr[i] == '\n') { // Left justify 2070 OutStr[i] = '\\'; 2071 OutStr.insert(OutStr.begin()+i+1, 'l'); 2072 } 2073 2074 return OutStr; 2075#else 2076 return ""; 2077#endif 2078 } 2079}; 2080} // end namespace llvm 2081