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