lib/Analysis/CFG.cpp

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