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