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