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