1 //===--- CFG.cpp - Classes for representing and building CFGs----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the CFG and CFGBuilder classes for representing and
11 // building Control-Flow Graphs (CFGs) from ASTs.
13 //===----------------------------------------------------------------------===//
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 "clang/AST/CharUnits.h"
21 #include "llvm/Support/GraphWriter.h"
22 #include "llvm/Support/Allocator.h"
23 #include "llvm/Support/Format.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/SmallPtrSet.h"
26 #include "llvm/ADT/OwningPtr.h"
28 using namespace clang;
32 static SourceLocation GetEndLoc(Decl* D) {
33 if (VarDecl* VD = dyn_cast<VarDecl>(D))
34 if (Expr* Ex = VD->getInit())
35 return Ex->getSourceRange().getEnd();
36 return D->getLocation();
41 /// The CFG builder uses a recursive algorithm to build the CFG. When
42 /// we process an expression, sometimes we know that we must add the
43 /// subexpressions as block-level expressions. For example:
47 /// When processing the '||' expression, we know that exp1 and exp2
48 /// need to be added as block-level expressions, even though they
49 /// might not normally need to be. AddStmtChoice records this
50 /// contextual information. If AddStmtChoice is 'NotAlwaysAdd', then
51 /// the builder has an option not to add a subexpression as a
52 /// block-level expression.
56 enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 };
58 AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {}
60 bool alwaysAdd(CFGBuilder &builder,
61 const Stmt *stmt) const;
63 /// Return a copy of this object, except with the 'always-add' bit
65 AddStmtChoice withAlwaysAdd(bool alwaysAdd) const {
66 return AddStmtChoice(alwaysAdd ? AlwaysAdd : NotAlwaysAdd);
73 /// LocalScope - Node in tree of local scopes created for C++ implicit
74 /// destructor calls generation. It contains list of automatic variables
75 /// declared in the scope and link to position in previous scope this scope
78 /// The process of creating local scopes is as follows:
79 /// - Init CFGBuilder::ScopePos with invalid position (equivalent for null),
80 /// - Before processing statements in scope (e.g. CompoundStmt) create
81 /// LocalScope object using CFGBuilder::ScopePos as link to previous scope
82 /// and set CFGBuilder::ScopePos to the end of new scope,
83 /// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points
85 /// - For every normal (without jump) end of scope add to CFGBlock destructors
86 /// for objects in the current scope,
87 /// - For every jump add to CFGBlock destructors for objects
88 /// between CFGBuilder::ScopePos and local scope position saved for jump
89 /// target. Thanks to C++ restrictions on goto jumps we can be sure that
90 /// jump target position will be on the path to root from CFGBuilder::ScopePos
91 /// (adding any variable that doesn't need constructor to be called to
92 /// LocalScope can break this assumption),
96 typedef BumpVector<VarDecl*> AutomaticVarsTy;
98 /// const_iterator - Iterates local scope backwards and jumps to previous
99 /// scope on reaching the beginning of currently iterated scope.
100 class const_iterator {
101 const LocalScope* Scope;
103 /// VarIter is guaranteed to be greater then 0 for every valid iterator.
104 /// Invalid iterator (with null Scope) has VarIter equal to 0.
108 /// Create invalid iterator. Dereferencing invalid iterator is not allowed.
109 /// Incrementing invalid iterator is allowed and will result in invalid
112 : Scope(NULL), VarIter(0) {}
114 /// Create valid iterator. In case when S.Prev is an invalid iterator and
115 /// I is equal to 0, this will create invalid iterator.
116 const_iterator(const LocalScope& S, unsigned I)
117 : Scope(&S), VarIter(I) {
118 // Iterator to "end" of scope is not allowed. Handle it by going up
119 // in scopes tree possibly up to invalid iterator in the root.
120 if (VarIter == 0 && Scope)
124 VarDecl* const* operator->() const {
125 assert (Scope && "Dereferencing invalid iterator is not allowed");
126 assert (VarIter != 0 && "Iterator has invalid value of VarIter member");
127 return &Scope->Vars[VarIter - 1];
129 VarDecl* operator*() const {
130 return *this->operator->();
133 const_iterator& operator++() {
137 assert (VarIter != 0 && "Iterator has invalid value of VarIter member");
143 const_iterator operator++(int) {
144 const_iterator P = *this;
149 bool operator==(const const_iterator& rhs) const {
150 return Scope == rhs.Scope && VarIter == rhs.VarIter;
152 bool operator!=(const const_iterator& rhs) const {
153 return !(*this == rhs);
156 operator bool() const {
157 return *this != const_iterator();
160 int distance(const_iterator L);
163 friend class const_iterator;
166 BumpVectorContext ctx;
168 /// Automatic variables in order of declaration.
169 AutomaticVarsTy Vars;
170 /// Iterator to variable in previous scope that was declared just before
171 /// begin of this scope.
175 /// Constructs empty scope linked to previous scope in specified place.
176 LocalScope(BumpVectorContext &ctx, const_iterator P)
177 : ctx(ctx), Vars(ctx, 4), Prev(P) {}
179 /// Begin of scope in direction of CFG building (backwards).
180 const_iterator begin() const { return const_iterator(*this, Vars.size()); }
182 void addVar(VarDecl* VD) {
183 Vars.push_back(VD, ctx);
187 /// distance - Calculates distance from this to L. L must be reachable from this
188 /// (with use of ++ operator). Cost of calculating the distance is linear w.r.t.
189 /// number of scopes between this and L.
190 int LocalScope::const_iterator::distance(LocalScope::const_iterator L) {
192 const_iterator F = *this;
193 while (F.Scope != L.Scope) {
194 assert (F != const_iterator()
195 && "L iterator is not reachable from F iterator.");
199 D += F.VarIter - L.VarIter;
203 /// BlockScopePosPair - Structure for specifying position in CFG during its
204 /// build process. It consists of CFGBlock that specifies position in CFG graph
205 /// and LocalScope::const_iterator that specifies position in LocalScope graph.
206 struct BlockScopePosPair {
207 BlockScopePosPair() : block(0) {}
208 BlockScopePosPair(CFGBlock* b, LocalScope::const_iterator scopePos)
209 : block(b), scopePosition(scopePos) {}
212 LocalScope::const_iterator scopePosition;
215 /// TryResult - a class representing a variant over the values
216 /// 'true', 'false', or 'unknown'. This is returned by tryEvaluateBool,
217 /// and is used by the CFGBuilder to decide if a branch condition
218 /// can be decided up front during CFG construction.
222 TryResult(bool b) : X(b ? 1 : 0) {}
223 TryResult() : X(-1) {}
225 bool isTrue() const { return X == 1; }
226 bool isFalse() const { return X == 0; }
227 bool isKnown() const { return X >= 0; }
234 /// CFGBuilder - This class implements CFG construction from an AST.
235 /// The builder is stateful: an instance of the builder should be used to only
236 /// construct a single CFG.
240 /// CFGBuilder builder;
241 /// CFG* cfg = builder.BuildAST(stmt1);
243 /// CFG construction is done via a recursive walk of an AST. We actually parse
244 /// the AST in reverse order so that the successor of a basic block is
245 /// constructed prior to its predecessor. This allows us to nicely capture
246 /// implicit fall-throughs without extra basic blocks.
249 typedef BlockScopePosPair JumpTarget;
250 typedef BlockScopePosPair JumpSource;
253 llvm::OwningPtr<CFG> cfg;
257 JumpTarget ContinueJumpTarget;
258 JumpTarget BreakJumpTarget;
259 CFGBlock* SwitchTerminatedBlock;
260 CFGBlock* DefaultCaseBlock;
261 CFGBlock* TryTerminatedBlock;
263 // Current position in local scope.
264 LocalScope::const_iterator ScopePos;
266 // LabelMap records the mapping from Label expressions to their jump targets.
267 typedef llvm::DenseMap<LabelDecl*, JumpTarget> LabelMapTy;
270 // A list of blocks that end with a "goto" that must be backpatched to their
271 // resolved targets upon completion of CFG construction.
272 typedef std::vector<JumpSource> BackpatchBlocksTy;
273 BackpatchBlocksTy BackpatchBlocks;
275 // A list of labels whose address has been taken (for indirect gotos).
276 typedef llvm::SmallPtrSet<LabelDecl*, 5> LabelSetTy;
277 LabelSetTy AddressTakenLabels;
280 const CFG::BuildOptions &BuildOpts;
282 // State to track for building switch statements.
283 bool switchExclusivelyCovered;
284 Expr::EvalResult *switchCond;
286 CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry;
287 const Stmt *lastLookup;
290 explicit CFGBuilder(ASTContext *astContext,
291 const CFG::BuildOptions &buildOpts)
292 : Context(astContext), cfg(new CFG()), // crew a new CFG
293 Block(NULL), Succ(NULL),
294 SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL),
295 TryTerminatedBlock(NULL), badCFG(false), BuildOpts(buildOpts),
296 switchExclusivelyCovered(false), switchCond(0),
297 cachedEntry(0), lastLookup(0) {}
299 // buildCFG - Used by external clients to construct the CFG.
300 CFG* buildCFG(const Decl *D, Stmt *Statement);
302 bool alwaysAdd(const Stmt *stmt);
305 // Visitors to walk an AST and construct the CFG.
306 CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc);
307 CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc);
308 CFGBlock *VisitBlockExpr(BlockExpr* E, AddStmtChoice asc);
309 CFGBlock *VisitBreakStmt(BreakStmt *B);
310 CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S);
311 CFGBlock *VisitExprWithCleanups(ExprWithCleanups *E,
313 CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T);
314 CFGBlock *VisitCXXTryStmt(CXXTryStmt *S);
315 CFGBlock *VisitCXXForRangeStmt(CXXForRangeStmt *S);
316 CFGBlock *VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
318 CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc);
319 CFGBlock *VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
321 CFGBlock *VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C,
323 CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc);
324 CFGBlock *VisitCaseStmt(CaseStmt *C);
325 CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc);
326 CFGBlock *VisitCompoundStmt(CompoundStmt *C);
327 CFGBlock *VisitConditionalOperator(AbstractConditionalOperator *C,
329 CFGBlock *VisitContinueStmt(ContinueStmt *C);
330 CFGBlock *VisitDeclStmt(DeclStmt *DS);
331 CFGBlock *VisitDeclSubExpr(DeclStmt* DS);
332 CFGBlock *VisitDefaultStmt(DefaultStmt *D);
333 CFGBlock *VisitDoStmt(DoStmt *D);
334 CFGBlock *VisitForStmt(ForStmt *F);
335 CFGBlock *VisitGotoStmt(GotoStmt* G);
336 CFGBlock *VisitIfStmt(IfStmt *I);
337 CFGBlock *VisitImplicitCastExpr(ImplicitCastExpr *E, AddStmtChoice asc);
338 CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I);
339 CFGBlock *VisitLabelStmt(LabelStmt *L);
340 CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc);
341 CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S);
342 CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S);
343 CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S);
344 CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S);
345 CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S);
346 CFGBlock *VisitReturnStmt(ReturnStmt* R);
347 CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
349 CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc);
350 CFGBlock *VisitSwitchStmt(SwitchStmt *S);
351 CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc);
352 CFGBlock *VisitWhileStmt(WhileStmt *W);
354 CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd);
355 CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc);
356 CFGBlock *VisitChildren(Stmt* S);
358 // Visitors to walk an AST and generate destructors of temporaries in
360 CFGBlock *VisitForTemporaryDtors(Stmt *E, bool BindToTemporary = false);
361 CFGBlock *VisitChildrenForTemporaryDtors(Stmt *E);
362 CFGBlock *VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E);
363 CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors(CXXBindTemporaryExpr *E,
364 bool BindToTemporary);
366 VisitConditionalOperatorForTemporaryDtors(AbstractConditionalOperator *E,
367 bool BindToTemporary);
369 // NYS == Not Yet Supported
375 void autoCreateBlock() { if (!Block) Block = createBlock(); }
376 CFGBlock *createBlock(bool add_successor = true);
378 CFGBlock *addStmt(Stmt *S) {
379 return Visit(S, AddStmtChoice::AlwaysAdd);
381 CFGBlock *addInitializer(CXXCtorInitializer *I);
382 void addAutomaticObjDtors(LocalScope::const_iterator B,
383 LocalScope::const_iterator E, Stmt* S);
384 void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD);
386 // Local scopes creation.
387 LocalScope* createOrReuseLocalScope(LocalScope* Scope);
389 void addLocalScopeForStmt(Stmt* S);
390 LocalScope* addLocalScopeForDeclStmt(DeclStmt* DS, LocalScope* Scope = NULL);
391 LocalScope* addLocalScopeForVarDecl(VarDecl* VD, LocalScope* Scope = NULL);
393 void addLocalScopeAndDtors(Stmt* S);
395 // Interface to CFGBlock - adding CFGElements.
396 void appendStmt(CFGBlock *B, const Stmt *S) {
398 cachedEntry->second = B;
400 // All block-level expressions should have already been IgnoreParens()ed.
401 assert(!isa<Expr>(S) || cast<Expr>(S)->IgnoreParens() == S);
402 B->appendStmt(const_cast<Stmt*>(S), cfg->getBumpVectorContext());
404 void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) {
405 B->appendInitializer(I, cfg->getBumpVectorContext());
407 void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) {
408 B->appendBaseDtor(BS, cfg->getBumpVectorContext());
410 void appendMemberDtor(CFGBlock *B, FieldDecl *FD) {
411 B->appendMemberDtor(FD, cfg->getBumpVectorContext());
413 void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) {
414 B->appendTemporaryDtor(E, cfg->getBumpVectorContext());
417 void insertAutomaticObjDtors(CFGBlock* Blk, CFGBlock::iterator I,
418 LocalScope::const_iterator B, LocalScope::const_iterator E, Stmt* S);
419 void appendAutomaticObjDtors(CFGBlock* Blk, LocalScope::const_iterator B,
420 LocalScope::const_iterator E, Stmt* S);
421 void prependAutomaticObjDtorsWithTerminator(CFGBlock* Blk,
422 LocalScope::const_iterator B, LocalScope::const_iterator E);
424 void addSuccessor(CFGBlock *B, CFGBlock *S) {
425 B->addSuccessor(S, cfg->getBumpVectorContext());
428 /// Try and evaluate an expression to an integer constant.
429 bool tryEvaluate(Expr *S, Expr::EvalResult &outResult) {
430 if (!BuildOpts.PruneTriviallyFalseEdges)
432 return !S->isTypeDependent() &&
433 !S->isValueDependent() &&
434 S->Evaluate(outResult, *Context);
437 /// tryEvaluateBool - Try and evaluate the Stmt and return 0 or 1
438 /// if we can evaluate to a known value, otherwise return -1.
439 TryResult tryEvaluateBool(Expr *S) {
440 Expr::EvalResult Result;
441 if (!tryEvaluate(S, Result))
444 if (Result.Val.isInt())
445 return Result.Val.getInt().getBoolValue();
447 if (Result.Val.isLValue()) {
448 const Expr *e = Result.Val.getLValueBase();
449 const CharUnits &c = Result.Val.getLValueOffset();
450 if (!e && c.isZero())
458 inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder,
459 const Stmt *stmt) const {
460 return builder.alwaysAdd(stmt) || kind == AlwaysAdd;
463 bool CFGBuilder::alwaysAdd(const Stmt *stmt) {
464 if (!BuildOpts.forcedBlkExprs)
467 if (lastLookup == stmt) {
469 assert(cachedEntry->first == stmt);
477 // Perform the lookup!
478 CFG::BuildOptions::ForcedBlkExprs *fb = *BuildOpts.forcedBlkExprs;
481 // No need to update 'cachedEntry', since it will always be null.
482 assert(cachedEntry == 0);
486 CFG::BuildOptions::ForcedBlkExprs::iterator itr = fb->find(stmt);
487 if (itr == fb->end()) {
496 // FIXME: Add support for dependent-sized array types in C++?
497 // Does it even make sense to build a CFG for an uninstantiated template?
498 static const VariableArrayType *FindVA(const Type *t) {
499 while (const ArrayType *vt = dyn_cast<ArrayType>(t)) {
500 if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(vt))
501 if (vat->getSizeExpr())
504 t = vt->getElementType().getTypePtr();
510 /// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an
511 /// arbitrary statement. Examples include a single expression or a function
512 /// body (compound statement). The ownership of the returned CFG is
513 /// transferred to the caller. If CFG construction fails, this method returns
515 CFG* CFGBuilder::buildCFG(const Decl *D, Stmt* Statement) {
520 // Create an empty block that will serve as the exit block for the CFG. Since
521 // this is the first block added to the CFG, it will be implicitly registered
522 // as the exit block.
523 Succ = createBlock();
524 assert(Succ == &cfg->getExit());
525 Block = NULL; // the EXIT block is empty. Create all other blocks lazily.
527 if (BuildOpts.AddImplicitDtors)
528 if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D))
529 addImplicitDtorsForDestructor(DD);
531 // Visit the statements and create the CFG.
532 CFGBlock *B = addStmt(Statement);
537 // For C++ constructor add initializers to CFG.
538 if (const CXXConstructorDecl *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) {
539 for (CXXConstructorDecl::init_const_reverse_iterator I = CD->init_rbegin(),
540 E = CD->init_rend(); I != E; ++I) {
541 B = addInitializer(*I);
550 // Backpatch the gotos whose label -> block mappings we didn't know when we
552 for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(),
553 E = BackpatchBlocks.end(); I != E; ++I ) {
555 CFGBlock* B = I->block;
556 GotoStmt* G = cast<GotoStmt>(B->getTerminator());
557 LabelMapTy::iterator LI = LabelMap.find(G->getLabel());
559 // If there is no target for the goto, then we are looking at an
560 // incomplete AST. Handle this by not registering a successor.
561 if (LI == LabelMap.end()) continue;
563 JumpTarget JT = LI->second;
564 prependAutomaticObjDtorsWithTerminator(B, I->scopePosition,
566 addSuccessor(B, JT.block);
569 // Add successors to the Indirect Goto Dispatch block (if we have one).
570 if (CFGBlock* B = cfg->getIndirectGotoBlock())
571 for (LabelSetTy::iterator I = AddressTakenLabels.begin(),
572 E = AddressTakenLabels.end(); I != E; ++I ) {
574 // Lookup the target block.
575 LabelMapTy::iterator LI = LabelMap.find(*I);
577 // If there is no target block that contains label, then we are looking
578 // at an incomplete AST. Handle this by not registering a successor.
579 if (LI == LabelMap.end()) continue;
581 addSuccessor(B, LI->second.block);
584 // Create an empty entry block that has no predecessors.
585 cfg->setEntry(createBlock());
590 /// createBlock - Used to lazily create blocks that are connected
591 /// to the current (global) succcessor.
592 CFGBlock* CFGBuilder::createBlock(bool add_successor) {
593 CFGBlock* B = cfg->createBlock();
594 if (add_successor && Succ)
595 addSuccessor(B, Succ);
599 /// addInitializer - Add C++ base or member initializer element to CFG.
600 CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) {
601 if (!BuildOpts.AddInitializers)
604 bool IsReference = false;
605 bool HasTemporaries = false;
607 // Destructors of temporaries in initialization expression should be called
608 // after initialization finishes.
609 Expr *Init = I->getInit();
611 if (FieldDecl *FD = I->getAnyMember())
612 IsReference = FD->getType()->isReferenceType();
613 HasTemporaries = isa<ExprWithCleanups>(Init);
615 if (BuildOpts.AddImplicitDtors && HasTemporaries) {
616 // Generate destructors for temporaries in initialization expression.
617 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),
623 appendInitializer(Block, I);
626 if (HasTemporaries) {
627 // For expression with temporaries go directly to subexpression to omit
628 // generating destructors for the second time.
629 return Visit(cast<ExprWithCleanups>(Init)->getSubExpr());
637 /// addAutomaticObjDtors - Add to current block automatic objects destructors
638 /// for objects in range of local scope positions. Use S as trigger statement
640 void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B,
641 LocalScope::const_iterator E, Stmt* S) {
642 if (!BuildOpts.AddImplicitDtors)
649 appendAutomaticObjDtors(Block, B, E, S);
652 /// addImplicitDtorsForDestructor - Add implicit destructors generated for
653 /// base and member objects in destructor.
654 void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) {
655 assert (BuildOpts.AddImplicitDtors
656 && "Can be called only when dtors should be added");
657 const CXXRecordDecl *RD = DD->getParent();
659 // At the end destroy virtual base objects.
660 for (CXXRecordDecl::base_class_const_iterator VI = RD->vbases_begin(),
661 VE = RD->vbases_end(); VI != VE; ++VI) {
662 const CXXRecordDecl *CD = VI->getType()->getAsCXXRecordDecl();
663 if (!CD->hasTrivialDestructor()) {
665 appendBaseDtor(Block, VI);
669 // Before virtual bases destroy direct base objects.
670 for (CXXRecordDecl::base_class_const_iterator BI = RD->bases_begin(),
671 BE = RD->bases_end(); BI != BE; ++BI) {
672 if (!BI->isVirtual()) {
673 const CXXRecordDecl *CD = BI->getType()->getAsCXXRecordDecl();
674 if (!CD->hasTrivialDestructor()) {
676 appendBaseDtor(Block, BI);
681 // First destroy member objects.
682 for (CXXRecordDecl::field_iterator FI = RD->field_begin(),
683 FE = RD->field_end(); FI != FE; ++FI) {
684 // Check for constant size array. Set type to array element type.
685 QualType QT = FI->getType();
686 if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {
687 if (AT->getSize() == 0)
689 QT = AT->getElementType();
692 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
693 if (!CD->hasTrivialDestructor()) {
695 appendMemberDtor(Block, *FI);
700 /// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either
701 /// way return valid LocalScope object.
702 LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) {
704 llvm::BumpPtrAllocator &alloc = cfg->getAllocator();
705 Scope = alloc.Allocate<LocalScope>();
706 BumpVectorContext ctx(alloc);
707 new (Scope) LocalScope(ctx, ScopePos);
712 /// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement
713 /// that should create implicit scope (e.g. if/else substatements).
714 void CFGBuilder::addLocalScopeForStmt(Stmt* S) {
715 if (!BuildOpts.AddImplicitDtors)
718 LocalScope *Scope = 0;
720 // For compound statement we will be creating explicit scope.
721 if (CompoundStmt *CS = dyn_cast<CompoundStmt>(S)) {
722 for (CompoundStmt::body_iterator BI = CS->body_begin(), BE = CS->body_end()
725 if (LabelStmt *LS = dyn_cast<LabelStmt>(SI))
726 SI = LS->getSubStmt();
727 if (DeclStmt *DS = dyn_cast<DeclStmt>(SI))
728 Scope = addLocalScopeForDeclStmt(DS, Scope);
733 // For any other statement scope will be implicit and as such will be
734 // interesting only for DeclStmt.
735 if (LabelStmt *LS = dyn_cast<LabelStmt>(S))
736 S = LS->getSubStmt();
737 if (DeclStmt *DS = dyn_cast<DeclStmt>(S))
738 addLocalScopeForDeclStmt(DS);
741 /// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will
742 /// reuse Scope if not NULL.
743 LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt* DS,
745 if (!BuildOpts.AddImplicitDtors)
748 for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end()
750 if (VarDecl* VD = dyn_cast<VarDecl>(*DI))
751 Scope = addLocalScopeForVarDecl(VD, Scope);
756 /// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will
757 /// create add scope for automatic objects and temporary objects bound to
758 /// const reference. Will reuse Scope if not NULL.
759 LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl* VD,
761 if (!BuildOpts.AddImplicitDtors)
764 // Check if variable is local.
765 switch (VD->getStorageClass()) {
770 default: return Scope;
773 // Check for const references bound to temporary. Set type to pointee.
774 QualType QT = VD->getType();
775 if (const ReferenceType* RT = QT.getTypePtr()->getAs<ReferenceType>()) {
776 QT = RT->getPointeeType();
777 if (!QT.isConstQualified())
779 if (!VD->extendsLifetimeOfTemporary())
783 // Check for constant size array. Set type to array element type.
784 if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {
785 if (AT->getSize() == 0)
787 QT = AT->getElementType();
790 // Check if type is a C++ class with non-trivial destructor.
791 if (const CXXRecordDecl* CD = QT->getAsCXXRecordDecl())
792 if (!CD->hasTrivialDestructor()) {
793 // Add the variable to scope
794 Scope = createOrReuseLocalScope(Scope);
796 ScopePos = Scope->begin();
801 /// addLocalScopeAndDtors - For given statement add local scope for it and
802 /// add destructors that will cleanup the scope. Will reuse Scope if not NULL.
803 void CFGBuilder::addLocalScopeAndDtors(Stmt* S) {
804 if (!BuildOpts.AddImplicitDtors)
807 LocalScope::const_iterator scopeBeginPos = ScopePos;
808 addLocalScopeForStmt(S);
809 addAutomaticObjDtors(ScopePos, scopeBeginPos, S);
812 /// insertAutomaticObjDtors - Insert destructor CFGElements for variables with
813 /// automatic storage duration to CFGBlock's elements vector. Insertion will be
814 /// performed in place specified with iterator.
815 void CFGBuilder::insertAutomaticObjDtors(CFGBlock* Blk, CFGBlock::iterator I,
816 LocalScope::const_iterator B, LocalScope::const_iterator E, Stmt* S) {
817 BumpVectorContext& C = cfg->getBumpVectorContext();
818 I = Blk->beginAutomaticObjDtorsInsert(I, B.distance(E), C);
820 I = Blk->insertAutomaticObjDtor(I, *B++, S);
823 /// appendAutomaticObjDtors - Append destructor CFGElements for variables with
824 /// automatic storage duration to CFGBlock's elements vector. Elements will be
825 /// appended to physical end of the vector which happens to be logical
827 void CFGBuilder::appendAutomaticObjDtors(CFGBlock* Blk,
828 LocalScope::const_iterator B, LocalScope::const_iterator E, Stmt* S) {
829 insertAutomaticObjDtors(Blk, Blk->begin(), B, E, S);
832 /// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for
833 /// variables with automatic storage duration to CFGBlock's elements vector.
834 /// Elements will be prepended to physical beginning of the vector which
835 /// happens to be logical end. Use blocks terminator as statement that specifies
836 /// destructors call site.
837 void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock* Blk,
838 LocalScope::const_iterator B, LocalScope::const_iterator E) {
839 insertAutomaticObjDtors(Blk, Blk->end(), B, E, Blk->getTerminator());
842 /// Visit - Walk the subtree of a statement and add extra
843 /// blocks for ternary operators, &&, and ||. We also process "," and
844 /// DeclStmts (which may contain nested control-flow).
845 CFGBlock* CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) {
851 if (Expr *E = dyn_cast<Expr>(S))
852 S = E->IgnoreParens();
854 switch (S->getStmtClass()) {
856 return VisitStmt(S, asc);
858 case Stmt::AddrLabelExprClass:
859 return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc);
861 case Stmt::BinaryConditionalOperatorClass:
862 return VisitConditionalOperator(cast<BinaryConditionalOperator>(S), asc);
864 case Stmt::BinaryOperatorClass:
865 return VisitBinaryOperator(cast<BinaryOperator>(S), asc);
867 case Stmt::BlockExprClass:
868 return VisitBlockExpr(cast<BlockExpr>(S), asc);
870 case Stmt::BreakStmtClass:
871 return VisitBreakStmt(cast<BreakStmt>(S));
873 case Stmt::CallExprClass:
874 case Stmt::CXXOperatorCallExprClass:
875 case Stmt::CXXMemberCallExprClass:
876 return VisitCallExpr(cast<CallExpr>(S), asc);
878 case Stmt::CaseStmtClass:
879 return VisitCaseStmt(cast<CaseStmt>(S));
881 case Stmt::ChooseExprClass:
882 return VisitChooseExpr(cast<ChooseExpr>(S), asc);
884 case Stmt::CompoundStmtClass:
885 return VisitCompoundStmt(cast<CompoundStmt>(S));
887 case Stmt::ConditionalOperatorClass:
888 return VisitConditionalOperator(cast<ConditionalOperator>(S), asc);
890 case Stmt::ContinueStmtClass:
891 return VisitContinueStmt(cast<ContinueStmt>(S));
893 case Stmt::CXXCatchStmtClass:
894 return VisitCXXCatchStmt(cast<CXXCatchStmt>(S));
896 case Stmt::ExprWithCleanupsClass:
897 return VisitExprWithCleanups(cast<ExprWithCleanups>(S), asc);
899 case Stmt::CXXBindTemporaryExprClass:
900 return VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), asc);
902 case Stmt::CXXConstructExprClass:
903 return VisitCXXConstructExpr(cast<CXXConstructExpr>(S), asc);
905 case Stmt::CXXFunctionalCastExprClass:
906 return VisitCXXFunctionalCastExpr(cast<CXXFunctionalCastExpr>(S), asc);
908 case Stmt::CXXTemporaryObjectExprClass:
909 return VisitCXXTemporaryObjectExpr(cast<CXXTemporaryObjectExpr>(S), asc);
911 case Stmt::CXXThrowExprClass:
912 return VisitCXXThrowExpr(cast<CXXThrowExpr>(S));
914 case Stmt::CXXTryStmtClass:
915 return VisitCXXTryStmt(cast<CXXTryStmt>(S));
917 case Stmt::CXXForRangeStmtClass:
918 return VisitCXXForRangeStmt(cast<CXXForRangeStmt>(S));
920 case Stmt::DeclStmtClass:
921 return VisitDeclStmt(cast<DeclStmt>(S));
923 case Stmt::DefaultStmtClass:
924 return VisitDefaultStmt(cast<DefaultStmt>(S));
926 case Stmt::DoStmtClass:
927 return VisitDoStmt(cast<DoStmt>(S));
929 case Stmt::ForStmtClass:
930 return VisitForStmt(cast<ForStmt>(S));
932 case Stmt::GotoStmtClass:
933 return VisitGotoStmt(cast<GotoStmt>(S));
935 case Stmt::IfStmtClass:
936 return VisitIfStmt(cast<IfStmt>(S));
938 case Stmt::ImplicitCastExprClass:
939 return VisitImplicitCastExpr(cast<ImplicitCastExpr>(S), asc);
941 case Stmt::IndirectGotoStmtClass:
942 return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S));
944 case Stmt::LabelStmtClass:
945 return VisitLabelStmt(cast<LabelStmt>(S));
947 case Stmt::MemberExprClass:
948 return VisitMemberExpr(cast<MemberExpr>(S), asc);
950 case Stmt::ObjCAtCatchStmtClass:
951 return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S));
953 case Stmt::ObjCAtSynchronizedStmtClass:
954 return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S));
956 case Stmt::ObjCAtThrowStmtClass:
957 return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S));
959 case Stmt::ObjCAtTryStmtClass:
960 return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S));
962 case Stmt::ObjCForCollectionStmtClass:
963 return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S));
965 case Stmt::NullStmtClass:
968 case Stmt::ReturnStmtClass:
969 return VisitReturnStmt(cast<ReturnStmt>(S));
971 case Stmt::UnaryExprOrTypeTraitExprClass:
972 return VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
975 case Stmt::StmtExprClass:
976 return VisitStmtExpr(cast<StmtExpr>(S), asc);
978 case Stmt::SwitchStmtClass:
979 return VisitSwitchStmt(cast<SwitchStmt>(S));
981 case Stmt::UnaryOperatorClass:
982 return VisitUnaryOperator(cast<UnaryOperator>(S), asc);
984 case Stmt::WhileStmtClass:
985 return VisitWhileStmt(cast<WhileStmt>(S));
989 CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) {
990 if (asc.alwaysAdd(*this, S)) {
992 appendStmt(Block, S);
995 return VisitChildren(S);
998 /// VisitChildren - Visit the children of a Stmt.
999 CFGBlock *CFGBuilder::VisitChildren(Stmt* Terminator) {
1000 CFGBlock *lastBlock = Block;
1001 for (Stmt::child_range I = Terminator->children(); I; ++I)
1002 if (Stmt *child = *I)
1003 if (CFGBlock *b = Visit(child))
1009 CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A,
1010 AddStmtChoice asc) {
1011 AddressTakenLabels.insert(A->getLabel());
1013 if (asc.alwaysAdd(*this, A)) {
1015 appendStmt(Block, A);
1021 CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U,
1022 AddStmtChoice asc) {
1023 if (asc.alwaysAdd(*this, U)) {
1025 appendStmt(Block, U);
1028 return Visit(U->getSubExpr(), AddStmtChoice());
1031 CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B,
1032 AddStmtChoice asc) {
1033 if (B->isLogicalOp()) { // && or ||
1034 CFGBlock* ConfluenceBlock = Block ? Block : createBlock();
1035 appendStmt(ConfluenceBlock, B);
1040 // create the block evaluating the LHS
1041 CFGBlock* LHSBlock = createBlock(false);
1042 LHSBlock->setTerminator(B);
1044 // create the block evaluating the RHS
1045 Succ = ConfluenceBlock;
1047 CFGBlock* RHSBlock = addStmt(B->getRHS());
1053 // Create an empty block for cases where the RHS doesn't require
1054 // any explicit statements in the CFG.
1055 RHSBlock = createBlock();
1058 // See if this is a known constant.
1059 TryResult KnownVal = tryEvaluateBool(B->getLHS());
1060 if (KnownVal.isKnown() && (B->getOpcode() == BO_LOr))
1063 // Now link the LHSBlock with RHSBlock.
1064 if (B->getOpcode() == BO_LOr) {
1065 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock);
1066 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock);
1068 assert(B->getOpcode() == BO_LAnd);
1069 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock);
1070 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock);
1073 // Generate the blocks for evaluating the LHS.
1075 return addStmt(B->getLHS());
1078 if (B->getOpcode() == BO_Comma) { // ,
1080 appendStmt(Block, B);
1081 addStmt(B->getRHS());
1082 return addStmt(B->getLHS());
1085 if (B->isAssignmentOp()) {
1086 if (asc.alwaysAdd(*this, B)) {
1088 appendStmt(Block, B);
1091 return Visit(B->getRHS());
1094 if (asc.alwaysAdd(*this, B)) {
1096 appendStmt(Block, B);
1099 CFGBlock *RBlock = Visit(B->getRHS());
1100 CFGBlock *LBlock = Visit(B->getLHS());
1101 // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr
1102 // containing a DoStmt, and the LHS doesn't create a new block, then we should
1103 // return RBlock. Otherwise we'll incorrectly return NULL.
1104 return (LBlock ? LBlock : RBlock);
1107 CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) {
1108 if (asc.alwaysAdd(*this, E)) {
1110 appendStmt(Block, E);
1115 CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) {
1116 // "break" is a control-flow statement. Thus we stop processing the current
1121 // Now create a new block that ends with the break statement.
1122 Block = createBlock(false);
1123 Block->setTerminator(B);
1125 // If there is no target for the break, then we are looking at an incomplete
1126 // AST. This means that the CFG cannot be constructed.
1127 if (BreakJumpTarget.block) {
1128 addAutomaticObjDtors(ScopePos, BreakJumpTarget.scopePosition, B);
1129 addSuccessor(Block, BreakJumpTarget.block);
1137 static bool CanThrow(Expr *E, ASTContext &Ctx) {
1138 QualType Ty = E->getType();
1139 if (Ty->isFunctionPointerType())
1140 Ty = Ty->getAs<PointerType>()->getPointeeType();
1141 else if (Ty->isBlockPointerType())
1142 Ty = Ty->getAs<BlockPointerType>()->getPointeeType();
1144 const FunctionType *FT = Ty->getAs<FunctionType>();
1146 if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT))
1147 if (Proto->isNothrow(Ctx))
1153 CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) {
1154 // Compute the callee type.
1155 QualType calleeType = C->getCallee()->getType();
1156 if (calleeType == Context->BoundMemberTy) {
1157 QualType boundType = Expr::findBoundMemberType(C->getCallee());
1159 // We should only get a null bound type if processing a dependent
1160 // CFG. Recover by assuming nothing.
1161 if (!boundType.isNull()) calleeType = boundType;
1164 // If this is a call to a no-return function, this stops the block here.
1165 bool NoReturn = getFunctionExtInfo(*calleeType).getNoReturn();
1167 bool AddEHEdge = false;
1169 // Languages without exceptions are assumed to not throw.
1170 if (Context->getLangOptions().Exceptions) {
1171 if (BuildOpts.AddEHEdges)
1175 if (FunctionDecl *FD = C->getDirectCallee()) {
1176 if (FD->hasAttr<NoReturnAttr>())
1178 if (FD->hasAttr<NoThrowAttr>())
1182 if (!CanThrow(C->getCallee(), *Context))
1185 if (!NoReturn && !AddEHEdge)
1186 return VisitStmt(C, asc.withAlwaysAdd(true));
1194 Block = createBlock(!NoReturn);
1195 appendStmt(Block, C);
1198 // Wire this to the exit block directly.
1199 addSuccessor(Block, &cfg->getExit());
1202 // Add exceptional edges.
1203 if (TryTerminatedBlock)
1204 addSuccessor(Block, TryTerminatedBlock);
1206 addSuccessor(Block, &cfg->getExit());
1209 return VisitChildren(C);
1212 CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C,
1213 AddStmtChoice asc) {
1214 CFGBlock* ConfluenceBlock = Block ? Block : createBlock();
1215 appendStmt(ConfluenceBlock, C);
1219 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);
1220 Succ = ConfluenceBlock;
1222 CFGBlock* LHSBlock = Visit(C->getLHS(), alwaysAdd);
1226 Succ = ConfluenceBlock;
1228 CFGBlock* RHSBlock = Visit(C->getRHS(), alwaysAdd);
1232 Block = createBlock(false);
1233 // See if this is a known constant.
1234 const TryResult& KnownVal = tryEvaluateBool(C->getCond());
1235 addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock);
1236 addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock);
1237 Block->setTerminator(C);
1238 return addStmt(C->getCond());
1242 CFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) {
1243 addLocalScopeAndDtors(C);
1244 CFGBlock* LastBlock = Block;
1246 for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend();
1248 // If we hit a segment of code just containing ';' (NullStmts), we can
1249 // get a null block back. In such cases, just use the LastBlock
1250 if (CFGBlock *newBlock = addStmt(*I))
1251 LastBlock = newBlock;
1260 CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C,
1261 AddStmtChoice asc) {
1262 const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(C);
1263 const OpaqueValueExpr *opaqueValue = (BCO ? BCO->getOpaqueValue() : NULL);
1265 // Create the confluence block that will "merge" the results of the ternary
1267 CFGBlock* ConfluenceBlock = Block ? Block : createBlock();
1268 appendStmt(ConfluenceBlock, C);
1272 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);
1274 // Create a block for the LHS expression if there is an LHS expression. A
1275 // GCC extension allows LHS to be NULL, causing the condition to be the
1276 // value that is returned instead.
1277 // e.g: x ?: y is shorthand for: x ? x : y;
1278 Succ = ConfluenceBlock;
1280 CFGBlock* LHSBlock = 0;
1281 const Expr *trueExpr = C->getTrueExpr();
1282 if (trueExpr != opaqueValue) {
1283 LHSBlock = Visit(C->getTrueExpr(), alwaysAdd);
1289 LHSBlock = ConfluenceBlock;
1291 // Create the block for the RHS expression.
1292 Succ = ConfluenceBlock;
1293 CFGBlock* RHSBlock = Visit(C->getFalseExpr(), alwaysAdd);
1297 // Create the block that will contain the condition.
1298 Block = createBlock(false);
1300 // See if this is a known constant.
1301 const TryResult& KnownVal = tryEvaluateBool(C->getCond());
1302 addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock);
1303 addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock);
1304 Block->setTerminator(C);
1305 Expr *condExpr = C->getCond();
1308 // Run the condition expression if it's not trivially expressed in
1309 // terms of the opaque value (or if there is no opaque value).
1310 if (condExpr != opaqueValue)
1313 // Before that, run the common subexpression if there was one.
1314 // At least one of this or the above will be run.
1315 return addStmt(BCO->getCommon());
1318 return addStmt(condExpr);
1321 CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) {
1322 // Check if the Decl is for an __label__. If so, elide it from the
1324 if (isa<LabelDecl>(*DS->decl_begin()))
1327 // This case also handles static_asserts.
1328 if (DS->isSingleDecl())
1329 return VisitDeclSubExpr(DS);
1333 // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy.
1334 typedef llvm::SmallVector<Decl*,10> BufTy;
1335 BufTy Buf(DS->decl_begin(), DS->decl_end());
1337 for (BufTy::reverse_iterator I = Buf.rbegin(), E = Buf.rend(); I != E; ++I) {
1338 // Get the alignment of the new DeclStmt, padding out to >=8 bytes.
1339 unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8
1340 ? 8 : llvm::AlignOf<DeclStmt>::Alignment;
1342 // Allocate the DeclStmt using the BumpPtrAllocator. It will get
1343 // automatically freed with the CFG.
1344 DeclGroupRef DG(*I);
1346 void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A);
1347 DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D));
1349 // Append the fake DeclStmt to block.
1350 B = VisitDeclSubExpr(DSNew);
1356 /// VisitDeclSubExpr - Utility method to add block-level expressions for
1357 /// DeclStmts and initializers in them.
1358 CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt* DS) {
1359 assert(DS->isSingleDecl() && "Can handle single declarations only.");
1360 Decl *D = DS->getSingleDecl();
1362 if (isa<StaticAssertDecl>(D)) {
1363 // static_asserts aren't added to the CFG because they do not impact
1364 // runtime semantics.
1368 VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl());
1372 appendStmt(Block, DS);
1376 bool IsReference = false;
1377 bool HasTemporaries = false;
1379 // Destructors of temporaries in initialization expression should be called
1380 // after initialization finishes.
1381 Expr *Init = VD->getInit();
1383 IsReference = VD->getType()->isReferenceType();
1384 HasTemporaries = isa<ExprWithCleanups>(Init);
1386 if (BuildOpts.AddImplicitDtors && HasTemporaries) {
1387 // Generate destructors for temporaries in initialization expression.
1388 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),
1394 appendStmt(Block, DS);
1398 // For expression with temporaries go directly to subexpression to omit
1399 // generating destructors for the second time.
1400 Visit(cast<ExprWithCleanups>(Init)->getSubExpr());
1405 // If the type of VD is a VLA, then we must process its size expressions.
1406 for (const VariableArrayType* VA = FindVA(VD->getType().getTypePtr());
1407 VA != 0; VA = FindVA(VA->getElementType().getTypePtr()))
1408 Block = addStmt(VA->getSizeExpr());
1410 // Remove variable from local scope.
1411 if (ScopePos && VD == *ScopePos)
1417 CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) {
1418 // We may see an if statement in the middle of a basic block, or it may be the
1419 // first statement we are processing. In either case, we create a new basic
1420 // block. First, we create the blocks for the then...else statements, and
1421 // then we create the block containing the if statement. If we were in the
1422 // middle of a block, we stop processing that block. That block is then the
1423 // implicit successor for the "then" and "else" clauses.
1425 // Save local scope position because in case of condition variable ScopePos
1426 // won't be restored when traversing AST.
1427 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
1429 // Create local scope for possible condition variable.
1430 // Store scope position. Add implicit destructor.
1431 if (VarDecl* VD = I->getConditionVariable()) {
1432 LocalScope::const_iterator BeginScopePos = ScopePos;
1433 addLocalScopeForVarDecl(VD);
1434 addAutomaticObjDtors(ScopePos, BeginScopePos, I);
1437 // The block we were processing is now finished. Make it the successor
1445 // Process the false branch.
1446 CFGBlock* ElseBlock = Succ;
1448 if (Stmt* Else = I->getElse()) {
1449 SaveAndRestore<CFGBlock*> sv(Succ);
1451 // NULL out Block so that the recursive call to Visit will
1452 // create a new basic block.
1455 // If branch is not a compound statement create implicit scope
1456 // and add destructors.
1457 if (!isa<CompoundStmt>(Else))
1458 addLocalScopeAndDtors(Else);
1460 ElseBlock = addStmt(Else);
1462 if (!ElseBlock) // Can occur when the Else body has all NullStmts.
1463 ElseBlock = sv.get();
1470 // Process the true branch.
1471 CFGBlock* ThenBlock;
1473 Stmt* Then = I->getThen();
1475 SaveAndRestore<CFGBlock*> sv(Succ);
1478 // If branch is not a compound statement create implicit scope
1479 // and add destructors.
1480 if (!isa<CompoundStmt>(Then))
1481 addLocalScopeAndDtors(Then);
1483 ThenBlock = addStmt(Then);
1486 // We can reach here if the "then" body has all NullStmts.
1487 // Create an empty block so we can distinguish between true and false
1488 // branches in path-sensitive analyses.
1489 ThenBlock = createBlock(false);
1490 addSuccessor(ThenBlock, sv.get());
1497 // Now create a new block containing the if statement.
1498 Block = createBlock(false);
1500 // Set the terminator of the new block to the If statement.
1501 Block->setTerminator(I);
1503 // See if this is a known constant.
1504 const TryResult &KnownVal = tryEvaluateBool(I->getCond());
1506 // Now add the successors.
1507 addSuccessor(Block, KnownVal.isFalse() ? NULL : ThenBlock);
1508 addSuccessor(Block, KnownVal.isTrue()? NULL : ElseBlock);
1510 // Add the condition as the last statement in the new block. This may create
1511 // new blocks as the condition may contain control-flow. Any newly created
1512 // blocks will be pointed to be "Block".
1513 Block = addStmt(I->getCond());
1515 // Finally, if the IfStmt contains a condition variable, add both the IfStmt
1516 // and the condition variable initialization to the CFG.
1517 if (VarDecl *VD = I->getConditionVariable()) {
1518 if (Expr *Init = VD->getInit()) {
1520 appendStmt(Block, I->getConditionVariableDeclStmt());
1529 CFGBlock* CFGBuilder::VisitReturnStmt(ReturnStmt* R) {
1530 // If we were in the middle of a block we stop processing that block.
1532 // NOTE: If a "return" appears in the middle of a block, this means that the
1533 // code afterwards is DEAD (unreachable). We still keep a basic block
1534 // for that code; a simple "mark-and-sweep" from the entry block will be
1535 // able to report such dead blocks.
1537 // Create the new block.
1538 Block = createBlock(false);
1540 // The Exit block is the only successor.
1541 addAutomaticObjDtors(ScopePos, LocalScope::const_iterator(), R);
1542 addSuccessor(Block, &cfg->getExit());
1544 // Add the return statement to the block. This may create new blocks if R
1545 // contains control-flow (short-circuit operations).
1546 return VisitStmt(R, AddStmtChoice::AlwaysAdd);
1549 CFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt *L) {
1550 // Get the block of the labeled statement. Add it to our map.
1551 addStmt(L->getSubStmt());
1552 CFGBlock *LabelBlock = Block;
1554 if (!LabelBlock) // This can happen when the body is empty, i.e.
1555 LabelBlock = createBlock(); // scopes that only contains NullStmts.
1557 assert(LabelMap.find(L->getDecl()) == LabelMap.end() &&
1558 "label already in map");
1559 LabelMap[L->getDecl()] = JumpTarget(LabelBlock, ScopePos);
1561 // Labels partition blocks, so this is the end of the basic block we were
1562 // processing (L is the block's label). Because this is label (and we have
1563 // already processed the substatement) there is no extra control-flow to worry
1565 LabelBlock->setLabel(L);
1569 // We set Block to NULL to allow lazy creation of a new block (if necessary);
1572 // This block is now the implicit successor of other blocks.
1578 CFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) {
1579 // Goto is a control-flow statement. Thus we stop processing the current
1580 // block and create a new one.
1582 Block = createBlock(false);
1583 Block->setTerminator(G);
1585 // If we already know the mapping to the label block add the successor now.
1586 LabelMapTy::iterator I = LabelMap.find(G->getLabel());
1588 if (I == LabelMap.end())
1589 // We will need to backpatch this block later.
1590 BackpatchBlocks.push_back(JumpSource(Block, ScopePos));
1592 JumpTarget JT = I->second;
1593 addAutomaticObjDtors(ScopePos, JT.scopePosition, G);
1594 addSuccessor(Block, JT.block);
1600 CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) {
1601 CFGBlock* LoopSuccessor = NULL;
1603 // Save local scope position because in case of condition variable ScopePos
1604 // won't be restored when traversing AST.
1605 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
1607 // Create local scope for init statement and possible condition variable.
1608 // Add destructor for init statement and condition variable.
1609 // Store scope position for continue statement.
1610 if (Stmt* Init = F->getInit())
1611 addLocalScopeForStmt(Init);
1612 LocalScope::const_iterator LoopBeginScopePos = ScopePos;
1614 if (VarDecl* VD = F->getConditionVariable())
1615 addLocalScopeForVarDecl(VD);
1616 LocalScope::const_iterator ContinueScopePos = ScopePos;
1618 addAutomaticObjDtors(ScopePos, save_scope_pos.get(), F);
1620 // "for" is a control-flow statement. Thus we stop processing the current
1625 LoopSuccessor = Block;
1627 LoopSuccessor = Succ;
1629 // Save the current value for the break targets.
1630 // All breaks should go to the code following the loop.
1631 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
1632 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
1634 // Because of short-circuit evaluation, the condition of the loop can span
1635 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
1636 // evaluate the condition.
1637 CFGBlock* ExitConditionBlock = createBlock(false);
1638 CFGBlock* EntryConditionBlock = ExitConditionBlock;
1640 // Set the terminator for the "exit" condition block.
1641 ExitConditionBlock->setTerminator(F);
1643 // Now add the actual condition to the condition block. Because the condition
1644 // itself may contain control-flow, new blocks may be created.
1645 if (Stmt* C = F->getCond()) {
1646 Block = ExitConditionBlock;
1647 EntryConditionBlock = addStmt(C);
1650 assert(Block == EntryConditionBlock ||
1651 (Block == 0 && EntryConditionBlock == Succ));
1653 // If this block contains a condition variable, add both the condition
1654 // variable and initializer to the CFG.
1655 if (VarDecl *VD = F->getConditionVariable()) {
1656 if (Expr *Init = VD->getInit()) {
1658 appendStmt(Block, F->getConditionVariableDeclStmt());
1659 EntryConditionBlock = addStmt(Init);
1660 assert(Block == EntryConditionBlock);
1670 // The condition block is the implicit successor for the loop body as well as
1671 // any code above the loop.
1672 Succ = EntryConditionBlock;
1674 // See if this is a known constant.
1675 TryResult KnownVal(true);
1678 KnownVal = tryEvaluateBool(F->getCond());
1680 // Now create the loop body.
1682 assert(F->getBody());
1684 // Save the current values for Block, Succ, and continue targets.
1685 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
1686 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget);
1688 // Create a new block to contain the (bottom) of the loop body.
1691 // Loop body should end with destructor of Condition variable (if any).
1692 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, F);
1694 if (Stmt* I = F->getInc()) {
1695 // Generate increment code in its own basic block. This is the target of
1696 // continue statements.
1699 // No increment code. Create a special, empty, block that is used as the
1700 // target block for "looping back" to the start of the loop.
1701 assert(Succ == EntryConditionBlock);
1702 Succ = Block ? Block : createBlock();
1705 // Finish up the increment (or empty) block if it hasn't been already.
1707 assert(Block == Succ);
1713 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
1715 // The starting block for the loop increment is the block that should
1716 // represent the 'loop target' for looping back to the start of the loop.
1717 ContinueJumpTarget.block->setLoopTarget(F);
1719 // If body is not a compound statement create implicit scope
1720 // and add destructors.
1721 if (!isa<CompoundStmt>(F->getBody()))
1722 addLocalScopeAndDtors(F->getBody());
1724 // Now populate the body block, and in the process create new blocks as we
1725 // walk the body of the loop.
1726 CFGBlock* BodyBlock = addStmt(F->getBody());
1729 BodyBlock = ContinueJumpTarget.block;//can happen for "for (...;...;...);"
1733 // This new body block is a successor to our "exit" condition block.
1734 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock);
1737 // Link up the condition block with the code that follows the loop. (the
1739 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor);
1741 // If the loop contains initialization, create a new block for those
1742 // statements. This block can also contain statements that precede the loop.
1743 if (Stmt* I = F->getInit()) {
1744 Block = createBlock();
1748 // There is no loop initialization. We are thus basically a while loop.
1749 // NULL out Block to force lazy block construction.
1751 Succ = EntryConditionBlock;
1752 return EntryConditionBlock;
1755 CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) {
1756 if (asc.alwaysAdd(*this, M)) {
1758 appendStmt(Block, M);
1760 return Visit(M->getBase());
1763 CFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) {
1764 // Objective-C fast enumeration 'for' statements:
1765 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC
1767 // for ( Type newVariable in collection_expression ) { statements }
1772 // 1. collection_expression
1773 // T. jump to loop_entry
1775 // 1. side-effects of element expression
1776 // 1. ObjCForCollectionStmt [performs binding to newVariable]
1777 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil]
1780 // T. jump to loop_entry
1786 // Type existingItem;
1787 // for ( existingItem in expression ) { statements }
1791 // the same with newVariable replaced with existingItem; the binding works
1792 // the same except that for one ObjCForCollectionStmt::getElement() returns
1793 // a DeclStmt and the other returns a DeclRefExpr.
1796 CFGBlock* LoopSuccessor = 0;
1801 LoopSuccessor = Block;
1804 LoopSuccessor = Succ;
1806 // Build the condition blocks.
1807 CFGBlock* ExitConditionBlock = createBlock(false);
1808 CFGBlock* EntryConditionBlock = ExitConditionBlock;
1810 // Set the terminator for the "exit" condition block.
1811 ExitConditionBlock->setTerminator(S);
1813 // The last statement in the block should be the ObjCForCollectionStmt, which
1814 // performs the actual binding to 'element' and determines if there are any
1815 // more items in the collection.
1816 appendStmt(ExitConditionBlock, S);
1817 Block = ExitConditionBlock;
1819 // Walk the 'element' expression to see if there are any side-effects. We
1820 // generate new blocks as necessary. We DON'T add the statement by default to
1821 // the CFG unless it contains control-flow.
1822 EntryConditionBlock = Visit(S->getElement(), AddStmtChoice::NotAlwaysAdd);
1829 // The condition block is the implicit successor for the loop body as well as
1830 // any code above the loop.
1831 Succ = EntryConditionBlock;
1833 // Now create the true branch.
1835 // Save the current values for Succ, continue and break targets.
1836 SaveAndRestore<CFGBlock*> save_Succ(Succ);
1837 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
1838 save_break(BreakJumpTarget);
1840 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
1841 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos);
1843 CFGBlock* BodyBlock = addStmt(S->getBody());
1846 BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;"
1852 // This new body block is a successor to our "exit" condition block.
1853 addSuccessor(ExitConditionBlock, BodyBlock);
1856 // Link up the condition block with the code that follows the loop.
1857 // (the false branch).
1858 addSuccessor(ExitConditionBlock, LoopSuccessor);
1860 // Now create a prologue block to contain the collection expression.
1861 Block = createBlock();
1862 return addStmt(S->getCollection());
1865 CFGBlock* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S) {
1866 // FIXME: Add locking 'primitives' to CFG for @synchronized.
1869 CFGBlock *SyncBlock = addStmt(S->getSynchBody());
1871 // The sync body starts its own basic block. This makes it a little easier
1872 // for diagnostic clients.
1881 // Add the @synchronized to the CFG.
1883 appendStmt(Block, S);
1885 // Inline the sync expression.
1886 return addStmt(S->getSynchExpr());
1889 CFGBlock* CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt* S) {
1894 CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) {
1895 CFGBlock* LoopSuccessor = NULL;
1897 // Save local scope position because in case of condition variable ScopePos
1898 // won't be restored when traversing AST.
1899 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
1901 // Create local scope for possible condition variable.
1902 // Store scope position for continue statement.
1903 LocalScope::const_iterator LoopBeginScopePos = ScopePos;
1904 if (VarDecl* VD = W->getConditionVariable()) {
1905 addLocalScopeForVarDecl(VD);
1906 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W);
1909 // "while" is a control-flow statement. Thus we stop processing the current
1914 LoopSuccessor = Block;
1917 LoopSuccessor = Succ;
1919 // Because of short-circuit evaluation, the condition of the loop can span
1920 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
1921 // evaluate the condition.
1922 CFGBlock* ExitConditionBlock = createBlock(false);
1923 CFGBlock* EntryConditionBlock = ExitConditionBlock;
1925 // Set the terminator for the "exit" condition block.
1926 ExitConditionBlock->setTerminator(W);
1928 // Now add the actual condition to the condition block. Because the condition
1929 // itself may contain control-flow, new blocks may be created. Thus we update
1930 // "Succ" after adding the condition.
1931 if (Stmt* C = W->getCond()) {
1932 Block = ExitConditionBlock;
1933 EntryConditionBlock = addStmt(C);
1934 // The condition might finish the current 'Block'.
1935 Block = EntryConditionBlock;
1937 // If this block contains a condition variable, add both the condition
1938 // variable and initializer to the CFG.
1939 if (VarDecl *VD = W->getConditionVariable()) {
1940 if (Expr *Init = VD->getInit()) {
1942 appendStmt(Block, W->getConditionVariableDeclStmt());
1943 EntryConditionBlock = addStmt(Init);
1944 assert(Block == EntryConditionBlock);
1954 // The condition block is the implicit successor for the loop body as well as
1955 // any code above the loop.
1956 Succ = EntryConditionBlock;
1958 // See if this is a known constant.
1959 const TryResult& KnownVal = tryEvaluateBool(W->getCond());
1961 // Process the loop body.
1963 assert(W->getBody());
1965 // Save the current values for Block, Succ, and continue and break targets
1966 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
1967 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
1968 save_break(BreakJumpTarget);
1970 // Create an empty block to represent the transition block for looping back
1971 // to the head of the loop.
1973 assert(Succ == EntryConditionBlock);
1974 Succ = createBlock();
1975 Succ->setLoopTarget(W);
1976 ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos);
1978 // All breaks should go to the code following the loop.
1979 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
1981 // NULL out Block to force lazy instantiation of blocks for the body.
1984 // Loop body should end with destructor of Condition variable (if any).
1985 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W);
1987 // If body is not a compound statement create implicit scope
1988 // and add destructors.
1989 if (!isa<CompoundStmt>(W->getBody()))
1990 addLocalScopeAndDtors(W->getBody());
1992 // Create the body. The returned block is the entry to the loop body.
1993 CFGBlock* BodyBlock = addStmt(W->getBody());
1996 BodyBlock = ContinueJumpTarget.block; // can happen for "while(...) ;"
2002 // Add the loop body entry as a successor to the condition.
2003 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock);
2006 // Link up the condition block with the code that follows the loop. (the
2008 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor);
2010 // There can be no more statements in the condition block since we loop back
2011 // to this block. NULL out Block to force lazy creation of another block.
2014 // Return the condition block, which is the dominating block for the loop.
2015 Succ = EntryConditionBlock;
2016 return EntryConditionBlock;
2020 CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt* S) {
2021 // FIXME: For now we pretend that @catch and the code it contains does not
2026 CFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) {
2027 // FIXME: This isn't complete. We basically treat @throw like a return
2030 // If we were in the middle of a block we stop processing that block.
2034 // Create the new block.
2035 Block = createBlock(false);
2037 // The Exit block is the only successor.
2038 addSuccessor(Block, &cfg->getExit());
2040 // Add the statement to the block. This may create new blocks if S contains
2041 // control-flow (short-circuit operations).
2042 return VisitStmt(S, AddStmtChoice::AlwaysAdd);
2045 CFGBlock* CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr* T) {
2046 // If we were in the middle of a block we stop processing that block.
2050 // Create the new block.
2051 Block = createBlock(false);
2053 if (TryTerminatedBlock)
2054 // The current try statement is the only successor.
2055 addSuccessor(Block, TryTerminatedBlock);
2057 // otherwise the Exit block is the only successor.
2058 addSuccessor(Block, &cfg->getExit());
2060 // Add the statement to the block. This may create new blocks if S contains
2061 // control-flow (short-circuit operations).
2062 return VisitStmt(T, AddStmtChoice::AlwaysAdd);
2065 CFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) {
2066 CFGBlock* LoopSuccessor = NULL;
2068 // "do...while" is a control-flow statement. Thus we stop processing the
2073 LoopSuccessor = Block;
2075 LoopSuccessor = Succ;
2077 // Because of short-circuit evaluation, the condition of the loop can span
2078 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
2079 // evaluate the condition.
2080 CFGBlock* ExitConditionBlock = createBlock(false);
2081 CFGBlock* EntryConditionBlock = ExitConditionBlock;
2083 // Set the terminator for the "exit" condition block.
2084 ExitConditionBlock->setTerminator(D);
2086 // Now add the actual condition to the condition block. Because the condition
2087 // itself may contain control-flow, new blocks may be created.
2088 if (Stmt* C = D->getCond()) {
2089 Block = ExitConditionBlock;
2090 EntryConditionBlock = addStmt(C);
2097 // The condition block is the implicit successor for the loop body.
2098 Succ = EntryConditionBlock;
2100 // See if this is a known constant.
2101 const TryResult &KnownVal = tryEvaluateBool(D->getCond());
2103 // Process the loop body.
2104 CFGBlock* BodyBlock = NULL;
2106 assert(D->getBody());
2108 // Save the current values for Block, Succ, and continue and break targets
2109 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
2110 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
2111 save_break(BreakJumpTarget);
2113 // All continues within this loop should go to the condition block
2114 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos);
2116 // All breaks should go to the code following the loop.
2117 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
2119 // NULL out Block to force lazy instantiation of blocks for the body.
2122 // If body is not a compound statement create implicit scope
2123 // and add destructors.
2124 if (!isa<CompoundStmt>(D->getBody()))
2125 addLocalScopeAndDtors(D->getBody());
2127 // Create the body. The returned block is the entry to the loop body.
2128 BodyBlock = addStmt(D->getBody());
2131 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)"
2137 if (!KnownVal.isFalse()) {
2138 // Add an intermediate block between the BodyBlock and the
2139 // ExitConditionBlock to represent the "loop back" transition. Create an
2140 // empty block to represent the transition block for looping back to the
2141 // head of the loop.
2142 // FIXME: Can we do this more efficiently without adding another block?
2145 CFGBlock *LoopBackBlock = createBlock();
2146 LoopBackBlock->setLoopTarget(D);
2148 // Add the loop body entry as a successor to the condition.
2149 addSuccessor(ExitConditionBlock, LoopBackBlock);
2152 addSuccessor(ExitConditionBlock, NULL);
2155 // Link up the condition block with the code that follows the loop.
2156 // (the false branch).
2157 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor);
2159 // There can be no more statements in the body block(s) since we loop back to
2160 // the body. NULL out Block to force lazy creation of another block.
2163 // Return the loop body, which is the dominating block for the loop.
2168 CFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) {
2169 // "continue" is a control-flow statement. Thus we stop processing the
2174 // Now create a new block that ends with the continue statement.
2175 Block = createBlock(false);
2176 Block->setTerminator(C);
2178 // If there is no target for the continue, then we are looking at an
2179 // incomplete AST. This means the CFG cannot be constructed.
2180 if (ContinueJumpTarget.block) {
2181 addAutomaticObjDtors(ScopePos, ContinueJumpTarget.scopePosition, C);
2182 addSuccessor(Block, ContinueJumpTarget.block);
2189 CFGBlock *CFGBuilder::VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
2190 AddStmtChoice asc) {
2192 if (asc.alwaysAdd(*this, E)) {
2194 appendStmt(Block, E);
2197 // VLA types have expressions that must be evaluated.
2198 CFGBlock *lastBlock = Block;
2200 if (E->isArgumentType()) {
2201 for (const VariableArrayType *VA =FindVA(E->getArgumentType().getTypePtr());
2202 VA != 0; VA = FindVA(VA->getElementType().getTypePtr()))
2203 lastBlock = addStmt(VA->getSizeExpr());
2209 /// VisitStmtExpr - Utility method to handle (nested) statement
2210 /// expressions (a GCC extension).
2211 CFGBlock* CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) {
2212 if (asc.alwaysAdd(*this, SE)) {
2214 appendStmt(Block, SE);
2216 return VisitCompoundStmt(SE->getSubStmt());
2219 CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) {
2220 // "switch" is a control-flow statement. Thus we stop processing the current
2222 CFGBlock* SwitchSuccessor = NULL;
2224 // Save local scope position because in case of condition variable ScopePos
2225 // won't be restored when traversing AST.
2226 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2228 // Create local scope for possible condition variable.
2229 // Store scope position. Add implicit destructor.
2230 if (VarDecl* VD = Terminator->getConditionVariable()) {
2231 LocalScope::const_iterator SwitchBeginScopePos = ScopePos;
2232 addLocalScopeForVarDecl(VD);
2233 addAutomaticObjDtors(ScopePos, SwitchBeginScopePos, Terminator);
2239 SwitchSuccessor = Block;
2240 } else SwitchSuccessor = Succ;
2242 // Save the current "switch" context.
2243 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock),
2244 save_default(DefaultCaseBlock);
2245 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
2247 // Set the "default" case to be the block after the switch statement. If the
2248 // switch statement contains a "default:", this value will be overwritten with
2249 // the block for that code.
2250 DefaultCaseBlock = SwitchSuccessor;
2252 // Create a new block that will contain the switch statement.
2253 SwitchTerminatedBlock = createBlock(false);
2255 // Now process the switch body. The code after the switch is the implicit
2257 Succ = SwitchSuccessor;
2258 BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos);
2260 // When visiting the body, the case statements should automatically get linked
2261 // up to the switch. We also don't keep a pointer to the body, since all
2262 // control-flow from the switch goes to case/default statements.
2263 assert(Terminator->getBody() && "switch must contain a non-NULL body");
2266 // For pruning unreachable case statements, save the current state
2267 // for tracking the condition value.
2268 SaveAndRestore<bool> save_switchExclusivelyCovered(switchExclusivelyCovered,
2271 // Determine if the switch condition can be explicitly evaluated.
2272 assert(Terminator->getCond() && "switch condition must be non-NULL");
2273 Expr::EvalResult result;
2274 bool b = tryEvaluate(Terminator->getCond(), result);
2275 SaveAndRestore<Expr::EvalResult*> save_switchCond(switchCond,
2278 // If body is not a compound statement create implicit scope
2279 // and add destructors.
2280 if (!isa<CompoundStmt>(Terminator->getBody()))
2281 addLocalScopeAndDtors(Terminator->getBody());
2283 addStmt(Terminator->getBody());
2289 // If we have no "default:" case, the default transition is to the code
2290 // following the switch body. Moreover, take into account if all the
2291 // cases of a switch are covered (e.g., switching on an enum value).
2292 addSuccessor(SwitchTerminatedBlock,
2293 switchExclusivelyCovered || Terminator->isAllEnumCasesCovered()
2294 ? 0 : DefaultCaseBlock);
2296 // Add the terminator and condition in the switch block.
2297 SwitchTerminatedBlock->setTerminator(Terminator);
2298 Block = SwitchTerminatedBlock;
2299 Block = addStmt(Terminator->getCond());
2301 // Finally, if the SwitchStmt contains a condition variable, add both the
2302 // SwitchStmt and the condition variable initialization to the CFG.
2303 if (VarDecl *VD = Terminator->getConditionVariable()) {
2304 if (Expr *Init = VD->getInit()) {
2306 appendStmt(Block, Terminator->getConditionVariableDeclStmt());
2314 static bool shouldAddCase(bool &switchExclusivelyCovered,
2315 const Expr::EvalResult *switchCond,
2321 bool addCase = false;
2323 if (!switchExclusivelyCovered) {
2324 if (switchCond->Val.isInt()) {
2325 // Evaluate the LHS of the case value.
2326 Expr::EvalResult V1;
2327 CS->getLHS()->Evaluate(V1, Ctx);
2328 assert(V1.Val.isInt());
2329 const llvm::APSInt &condInt = switchCond->Val.getInt();
2330 const llvm::APSInt &lhsInt = V1.Val.getInt();
2332 if (condInt == lhsInt) {
2334 switchExclusivelyCovered = true;
2336 else if (condInt < lhsInt) {
2337 if (const Expr *RHS = CS->getRHS()) {
2338 // Evaluate the RHS of the case value.
2339 Expr::EvalResult V2;
2340 RHS->Evaluate(V2, Ctx);
2341 assert(V2.Val.isInt());
2342 if (V2.Val.getInt() <= condInt) {
2344 switchExclusivelyCovered = true;
2355 CFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) {
2356 // CaseStmts are essentially labels, so they are the first statement in a
2358 CFGBlock *TopBlock = 0, *LastBlock = 0;
2360 if (Stmt *Sub = CS->getSubStmt()) {
2361 // For deeply nested chains of CaseStmts, instead of doing a recursion
2362 // (which can blow out the stack), manually unroll and create blocks
2364 while (isa<CaseStmt>(Sub)) {
2365 CFGBlock *currentBlock = createBlock(false);
2366 currentBlock->setLabel(CS);
2369 addSuccessor(LastBlock, currentBlock);
2371 TopBlock = currentBlock;
2373 addSuccessor(SwitchTerminatedBlock,
2374 shouldAddCase(switchExclusivelyCovered, switchCond,
2376 ? currentBlock : 0);
2378 LastBlock = currentBlock;
2379 CS = cast<CaseStmt>(Sub);
2380 Sub = CS->getSubStmt();
2386 CFGBlock* CaseBlock = Block;
2388 CaseBlock = createBlock();
2390 // Cases statements partition blocks, so this is the top of the basic block we
2391 // were processing (the "case XXX:" is the label).
2392 CaseBlock->setLabel(CS);
2397 // Add this block to the list of successors for the block with the switch
2399 assert(SwitchTerminatedBlock);
2400 addSuccessor(SwitchTerminatedBlock,
2401 shouldAddCase(switchExclusivelyCovered, switchCond,
2405 // We set Block to NULL to allow lazy creation of a new block (if necessary)
2409 addSuccessor(LastBlock, CaseBlock);
2412 // This block is now the implicit successor of other blocks.
2419 CFGBlock* CFGBuilder::VisitDefaultStmt(DefaultStmt* Terminator) {
2420 if (Terminator->getSubStmt())
2421 addStmt(Terminator->getSubStmt());
2423 DefaultCaseBlock = Block;
2425 if (!DefaultCaseBlock)
2426 DefaultCaseBlock = createBlock();
2428 // Default statements partition blocks, so this is the top of the basic block
2429 // we were processing (the "default:" is the label).
2430 DefaultCaseBlock->setLabel(Terminator);
2435 // Unlike case statements, we don't add the default block to the successors
2436 // for the switch statement immediately. This is done when we finish
2437 // processing the switch statement. This allows for the default case
2438 // (including a fall-through to the code after the switch statement) to always
2439 // be the last successor of a switch-terminated block.
2441 // We set Block to NULL to allow lazy creation of a new block (if necessary)
2444 // This block is now the implicit successor of other blocks.
2445 Succ = DefaultCaseBlock;
2447 return DefaultCaseBlock;
2450 CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) {
2451 // "try"/"catch" is a control-flow statement. Thus we stop processing the
2453 CFGBlock* TrySuccessor = NULL;
2458 TrySuccessor = Block;
2459 } else TrySuccessor = Succ;
2461 CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock;
2463 // Create a new block that will contain the try statement.
2464 CFGBlock *NewTryTerminatedBlock = createBlock(false);
2465 // Add the terminator in the try block.
2466 NewTryTerminatedBlock->setTerminator(Terminator);
2468 bool HasCatchAll = false;
2469 for (unsigned h = 0; h <Terminator->getNumHandlers(); ++h) {
2470 // The code after the try is the implicit successor.
2471 Succ = TrySuccessor;
2472 CXXCatchStmt *CS = Terminator->getHandler(h);
2473 if (CS->getExceptionDecl() == 0) {
2477 CFGBlock *CatchBlock = VisitCXXCatchStmt(CS);
2478 if (CatchBlock == 0)
2480 // Add this block to the list of successors for the block with the try
2482 addSuccessor(NewTryTerminatedBlock, CatchBlock);
2485 if (PrevTryTerminatedBlock)
2486 addSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock);
2488 addSuccessor(NewTryTerminatedBlock, &cfg->getExit());
2491 // The code after the try is the implicit successor.
2492 Succ = TrySuccessor;
2494 // Save the current "try" context.
2495 SaveAndRestore<CFGBlock*> save_try(TryTerminatedBlock);
2496 TryTerminatedBlock = NewTryTerminatedBlock;
2498 assert(Terminator->getTryBlock() && "try must contain a non-NULL body");
2500 Block = addStmt(Terminator->getTryBlock());
2504 CFGBlock* CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt* CS) {
2505 // CXXCatchStmt are treated like labels, so they are the first statement in a
2508 // Save local scope position because in case of exception variable ScopePos
2509 // won't be restored when traversing AST.
2510 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2512 // Create local scope for possible exception variable.
2513 // Store scope position. Add implicit destructor.
2514 if (VarDecl* VD = CS->getExceptionDecl()) {
2515 LocalScope::const_iterator BeginScopePos = ScopePos;
2516 addLocalScopeForVarDecl(VD);
2517 addAutomaticObjDtors(ScopePos, BeginScopePos, CS);
2520 if (CS->getHandlerBlock())
2521 addStmt(CS->getHandlerBlock());
2523 CFGBlock* CatchBlock = Block;
2525 CatchBlock = createBlock();
2527 CatchBlock->setLabel(CS);
2532 // We set Block to NULL to allow lazy creation of a new block (if necessary)
2538 CFGBlock* CFGBuilder::VisitCXXForRangeStmt(CXXForRangeStmt* S) {
2539 // C++0x for-range statements are specified as [stmt.ranged]:
2542 // auto && __range = range-init;
2543 // for ( auto __begin = begin-expr,
2544 // __end = end-expr;
2545 // __begin != __end;
2547 // for-range-declaration = *__begin;
2552 // Save local scope position before the addition of the implicit variables.
2553 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2555 // Create local scopes and destructors for range, begin and end variables.
2556 if (Stmt *Range = S->getRangeStmt())
2557 addLocalScopeForStmt(Range);
2558 if (Stmt *BeginEnd = S->getBeginEndStmt())
2559 addLocalScopeForStmt(BeginEnd);
2560 addAutomaticObjDtors(ScopePos, save_scope_pos.get(), S);
2562 LocalScope::const_iterator ContinueScopePos = ScopePos;
2564 // "for" is a control-flow statement. Thus we stop processing the current
2566 CFGBlock* LoopSuccessor = NULL;
2570 LoopSuccessor = Block;
2572 LoopSuccessor = Succ;
2574 // Save the current value for the break targets.
2575 // All breaks should go to the code following the loop.
2576 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
2577 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
2579 // The block for the __begin != __end expression.
2580 CFGBlock* ConditionBlock = createBlock(false);
2581 ConditionBlock->setTerminator(S);
2583 // Now add the actual condition to the condition block.
2584 if (Expr *C = S->getCond()) {
2585 Block = ConditionBlock;
2586 CFGBlock *BeginConditionBlock = addStmt(C);
2589 assert(BeginConditionBlock == ConditionBlock &&
2590 "condition block in for-range was unexpectedly complex");
2591 (void)BeginConditionBlock;
2594 // The condition block is the implicit successor for the loop body as well as
2595 // any code above the loop.
2596 Succ = ConditionBlock;
2598 // See if this is a known constant.
2599 TryResult KnownVal(true);
2602 KnownVal = tryEvaluateBool(S->getCond());
2604 // Now create the loop body.
2606 assert(S->getBody());
2608 // Save the current values for Block, Succ, and continue targets.
2609 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
2610 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget);
2612 // Generate increment code in its own basic block. This is the target of
2613 // continue statements.
2615 Succ = addStmt(S->getInc());
2616 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
2618 // The starting block for the loop increment is the block that should
2619 // represent the 'loop target' for looping back to the start of the loop.
2620 ContinueJumpTarget.block->setLoopTarget(S);
2622 // Finish up the increment block and prepare to start the loop body.
2629 // Add implicit scope and dtors for loop variable.
2630 addLocalScopeAndDtors(S->getLoopVarStmt());
2632 // Populate a new block to contain the loop body and loop variable.
2633 Block = addStmt(S->getBody());
2636 Block = addStmt(S->getLoopVarStmt());
2640 // This new body block is a successor to our condition block.
2641 addSuccessor(ConditionBlock, KnownVal.isFalse() ? 0 : Block);
2644 // Link up the condition block with the code that follows the loop (the
2646 addSuccessor(ConditionBlock, KnownVal.isTrue() ? 0 : LoopSuccessor);
2648 // Add the initialization statements.
2649 Block = createBlock();
2650 addStmt(S->getBeginEndStmt());
2651 return addStmt(S->getRangeStmt());
2654 CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E,
2655 AddStmtChoice asc) {
2656 if (BuildOpts.AddImplicitDtors) {
2657 // If adding implicit destructors visit the full expression for adding
2658 // destructors of temporaries.
2659 VisitForTemporaryDtors(E->getSubExpr());
2661 // Full expression has to be added as CFGStmt so it will be sequenced
2662 // before destructors of it's temporaries.
2663 asc = asc.withAlwaysAdd(true);
2665 return Visit(E->getSubExpr(), asc);
2668 CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
2669 AddStmtChoice asc) {
2670 if (asc.alwaysAdd(*this, E)) {
2672 appendStmt(Block, E);
2674 // We do not want to propagate the AlwaysAdd property.
2675 asc = asc.withAlwaysAdd(false);
2677 return Visit(E->getSubExpr(), asc);
2680 CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C,
2681 AddStmtChoice asc) {
2683 if (!C->isElidable())
2684 appendStmt(Block, C);
2686 return VisitChildren(C);
2689 CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
2690 AddStmtChoice asc) {
2691 if (asc.alwaysAdd(*this, E)) {
2693 appendStmt(Block, E);
2694 // We do not want to propagate the AlwaysAdd property.
2695 asc = asc.withAlwaysAdd(false);
2697 return Visit(E->getSubExpr(), asc);
2700 CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C,
2701 AddStmtChoice asc) {
2703 appendStmt(Block, C);
2704 return VisitChildren(C);
2707 CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E,
2708 AddStmtChoice asc) {
2709 if (asc.alwaysAdd(*this, E)) {
2711 appendStmt(Block, E);
2713 return Visit(E->getSubExpr(), AddStmtChoice());
2716 CFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) {
2717 // Lazily create the indirect-goto dispatch block if there isn't one already.
2718 CFGBlock* IBlock = cfg->getIndirectGotoBlock();
2721 IBlock = createBlock(false);
2722 cfg->setIndirectGotoBlock(IBlock);
2725 // IndirectGoto is a control-flow statement. Thus we stop processing the
2726 // current block and create a new one.
2730 Block = createBlock(false);
2731 Block->setTerminator(I);
2732 addSuccessor(Block, IBlock);
2733 return addStmt(I->getTarget());
2736 CFGBlock *CFGBuilder::VisitForTemporaryDtors(Stmt *E, bool BindToTemporary) {
2742 switch (E->getStmtClass()) {
2744 return VisitChildrenForTemporaryDtors(E);
2746 case Stmt::BinaryOperatorClass:
2747 return VisitBinaryOperatorForTemporaryDtors(cast<BinaryOperator>(E));
2749 case Stmt::CXXBindTemporaryExprClass:
2750 return VisitCXXBindTemporaryExprForTemporaryDtors(
2751 cast<CXXBindTemporaryExpr>(E), BindToTemporary);
2753 case Stmt::BinaryConditionalOperatorClass:
2754 case Stmt::ConditionalOperatorClass:
2755 return VisitConditionalOperatorForTemporaryDtors(
2756 cast<AbstractConditionalOperator>(E), BindToTemporary);
2758 case Stmt::ImplicitCastExprClass:
2759 // For implicit cast we want BindToTemporary to be passed further.
2760 E = cast<CastExpr>(E)->getSubExpr();
2763 case Stmt::ParenExprClass:
2764 E = cast<ParenExpr>(E)->getSubExpr();
2767 case Stmt::MaterializeTemporaryExprClass:
2768 E = cast<MaterializeTemporaryExpr>(E)->GetTemporaryExpr();
2773 CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E) {
2774 // When visiting children for destructors we want to visit them in reverse
2775 // order. Because there's no reverse iterator for children must to reverse
2776 // them in helper vector.
2777 typedef llvm::SmallVector<Stmt *, 4> ChildrenVect;
2778 ChildrenVect ChildrenRev;
2779 for (Stmt::child_range I = E->children(); I; ++I) {
2780 if (*I) ChildrenRev.push_back(*I);
2783 CFGBlock *B = Block;
2784 for (ChildrenVect::reverse_iterator I = ChildrenRev.rbegin(),
2785 L = ChildrenRev.rend(); I != L; ++I) {
2786 if (CFGBlock *R = VisitForTemporaryDtors(*I))
2792 CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E) {
2793 if (E->isLogicalOp()) {
2794 // Destructors for temporaries in LHS expression should be called after
2795 // those for RHS expression. Even if this will unnecessarily create a block,
2796 // this block will be used at least by the full expression.
2798 CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getLHS());
2802 Succ = ConfluenceBlock;
2804 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS());
2810 // If RHS expression did produce destructors we need to connect created
2811 // blocks to CFG in same manner as for binary operator itself.
2812 CFGBlock *LHSBlock = createBlock(false);
2813 LHSBlock->setTerminator(CFGTerminator(E, true));
2815 // For binary operator LHS block is before RHS in list of predecessors
2816 // of ConfluenceBlock.
2817 std::reverse(ConfluenceBlock->pred_begin(),
2818 ConfluenceBlock->pred_end());
2820 // See if this is a known constant.
2821 TryResult KnownVal = tryEvaluateBool(E->getLHS());
2822 if (KnownVal.isKnown() && (E->getOpcode() == BO_LOr))
2825 // Link LHSBlock with RHSBlock exactly the same way as for binary operator
2827 if (E->getOpcode() == BO_LOr) {
2828 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock);
2829 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock);
2831 assert (E->getOpcode() == BO_LAnd);
2832 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock);
2833 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock);
2840 Block = ConfluenceBlock;
2841 return ConfluenceBlock;
2844 if (E->isAssignmentOp()) {
2845 // For assignment operator (=) LHS expression is visited
2846 // before RHS expression. For destructors visit them in reverse order.
2847 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS());
2848 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS());
2849 return LHSBlock ? LHSBlock : RHSBlock;
2852 // For any other binary operator RHS expression is visited before
2853 // LHS expression (order of children). For destructors visit them in reverse
2855 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS());
2856 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS());
2857 return RHSBlock ? RHSBlock : LHSBlock;
2860 CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors(
2861 CXXBindTemporaryExpr *E, bool BindToTemporary) {
2862 // First add destructors for temporaries in subexpression.
2863 CFGBlock *B = VisitForTemporaryDtors(E->getSubExpr());
2864 if (!BindToTemporary) {
2865 // If lifetime of temporary is not prolonged (by assigning to constant
2866 // reference) add destructor for it.
2868 appendTemporaryDtor(Block, E);
2874 CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors(
2875 AbstractConditionalOperator *E, bool BindToTemporary) {
2876 // First add destructors for condition expression. Even if this will
2877 // unnecessarily create a block, this block will be used at least by the full
2880 CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getCond());
2883 if (BinaryConditionalOperator *BCO
2884 = dyn_cast<BinaryConditionalOperator>(E)) {
2885 ConfluenceBlock = VisitForTemporaryDtors(BCO->getCommon());
2890 // Try to add block with destructors for LHS expression.
2891 CFGBlock *LHSBlock = NULL;
2892 Succ = ConfluenceBlock;
2894 LHSBlock = VisitForTemporaryDtors(E->getTrueExpr(), BindToTemporary);
2898 // Try to add block with destructors for RHS expression;
2899 Succ = ConfluenceBlock;
2901 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getFalseExpr(),
2906 if (!RHSBlock && !LHSBlock) {
2907 // If neither LHS nor RHS expression had temporaries to destroy don't create
2909 Block = ConfluenceBlock;
2913 Block = createBlock(false);
2914 Block->setTerminator(CFGTerminator(E, true));
2916 // See if this is a known constant.
2917 const TryResult &KnownVal = tryEvaluateBool(E->getCond());
2920 addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock);
2921 } else if (KnownVal.isFalse()) {
2922 addSuccessor(Block, NULL);
2924 addSuccessor(Block, ConfluenceBlock);
2925 std::reverse(ConfluenceBlock->pred_begin(), ConfluenceBlock->pred_end());
2929 RHSBlock = ConfluenceBlock;
2930 addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock);
2935 } // end anonymous namespace
2937 /// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has
2938 /// no successors or predecessors. If this is the first block created in the
2939 /// CFG, it is automatically set to be the Entry and Exit of the CFG.
2940 CFGBlock* CFG::createBlock() {
2941 bool first_block = begin() == end();
2943 // Create the block.
2944 CFGBlock *Mem = getAllocator().Allocate<CFGBlock>();
2945 new (Mem) CFGBlock(NumBlockIDs++, BlkBVC);
2946 Blocks.push_back(Mem, BlkBVC);
2948 // If this is the first block, set it as the Entry and Exit.
2950 Entry = Exit = &back();
2952 // Return the block.
2956 /// buildCFG - Constructs a CFG from an AST. Ownership of the returned
2957 /// CFG is returned to the caller.
2958 CFG* CFG::buildCFG(const Decl *D, Stmt* Statement, ASTContext *C,
2959 const BuildOptions &BO) {
2960 CFGBuilder Builder(C, BO);
2961 return Builder.buildCFG(D, Statement);
2964 const CXXDestructorDecl *
2965 CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const {
2966 switch (getKind()) {
2967 case CFGElement::Invalid:
2968 case CFGElement::Statement:
2969 case CFGElement::Initializer:
2970 llvm_unreachable("getDestructorDecl should only be used with "
2972 case CFGElement::AutomaticObjectDtor: {
2973 const VarDecl *var = cast<CFGAutomaticObjDtor>(this)->getVarDecl();
2974 QualType ty = var->getType();
2975 ty = ty.getNonReferenceType();
2976 if (const ArrayType *arrayType = astContext.getAsArrayType(ty)) {
2977 ty = arrayType->getElementType();
2979 const RecordType *recordType = ty->getAs<RecordType>();
2980 const CXXRecordDecl *classDecl =
2981 cast<CXXRecordDecl>(recordType->getDecl());
2982 return classDecl->getDestructor();
2984 case CFGElement::TemporaryDtor: {
2985 const CXXBindTemporaryExpr *bindExpr =
2986 cast<CFGTemporaryDtor>(this)->getBindTemporaryExpr();
2987 const CXXTemporary *temp = bindExpr->getTemporary();
2988 return temp->getDestructor();
2990 case CFGElement::BaseDtor:
2991 case CFGElement::MemberDtor:
2993 // Not yet supported.
2996 llvm_unreachable("getKind() returned bogus value");
3000 bool CFGImplicitDtor::isNoReturn(ASTContext &astContext) const {
3001 if (const CXXDestructorDecl *cdecl = getDestructorDecl(astContext)) {
3002 QualType ty = cdecl->getType();
3003 return cast<FunctionType>(ty)->getNoReturnAttr();
3008 //===----------------------------------------------------------------------===//
3009 // CFG: Queries for BlkExprs.
3010 //===----------------------------------------------------------------------===//
3013 typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy;
3016 static void FindSubExprAssignments(Stmt *S,
3017 llvm::SmallPtrSet<Expr*,50>& Set) {
3021 for (Stmt::child_range I = S->children(); I; ++I) {
3026 if (BinaryOperator* B = dyn_cast<BinaryOperator>(child))
3027 if (B->isAssignmentOp()) Set.insert(B);
3029 FindSubExprAssignments(child, Set);
3033 static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) {
3034 BlkExprMapTy* M = new BlkExprMapTy();
3036 // Look for assignments that are used as subexpressions. These are the only
3037 // assignments that we want to *possibly* register as a block-level
3038 // expression. Basically, if an assignment occurs both in a subexpression and
3039 // at the block-level, it is a block-level expression.
3040 llvm::SmallPtrSet<Expr*,50> SubExprAssignments;
3042 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I)
3043 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI)
3044 if (const CFGStmt *S = BI->getAs<CFGStmt>())
3045 FindSubExprAssignments(S->getStmt(), SubExprAssignments);
3047 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) {
3049 // Iterate over the statements again on identify the Expr* and Stmt* at the
3050 // block-level that are block-level expressions.
3052 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) {
3053 const CFGStmt *CS = BI->getAs<CFGStmt>();
3056 if (Expr* Exp = dyn_cast<Expr>(CS->getStmt())) {
3057 assert((Exp->IgnoreParens() == Exp) && "No parens on block-level exps");
3059 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) {
3060 // Assignment expressions that are not nested within another
3061 // expression are really "statements" whose value is never used by
3062 // another expression.
3063 if (B->isAssignmentOp() && !SubExprAssignments.count(Exp))
3065 } else if (const StmtExpr* SE = dyn_cast<StmtExpr>(Exp)) {
3066 // Special handling for statement expressions. The last statement in
3067 // the statement expression is also a block-level expr.
3068 const CompoundStmt* C = SE->getSubStmt();
3069 if (!C->body_empty()) {
3070 const Stmt *Last = C->body_back();
3071 if (const Expr *LastEx = dyn_cast<Expr>(Last))
3072 Last = LastEx->IgnoreParens();
3073 unsigned x = M->size();
3078 unsigned x = M->size();
3083 // Look at terminators. The condition is a block-level expression.
3085 Stmt* S = (*I)->getTerminatorCondition();
3087 if (S && M->find(S) == M->end()) {
3088 unsigned x = M->size();
3096 CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) {
3098 if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); }
3100 BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap);
3101 BlkExprMapTy::iterator I = M->find(S);
3102 return (I == M->end()) ? CFG::BlkExprNumTy() : CFG::BlkExprNumTy(I->second);
3105 unsigned CFG::getNumBlkExprs() {
3106 if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap))
3109 // We assume callers interested in the number of BlkExprs will want
3110 // the map constructed if it doesn't already exist.
3111 BlkExprMap = (void*) PopulateBlkExprMap(*this);
3112 return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size();
3115 //===----------------------------------------------------------------------===//
3116 // Filtered walking of the CFG.
3117 //===----------------------------------------------------------------------===//
3119 bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F,
3120 const CFGBlock *From, const CFGBlock *To) {
3122 if (To && F.IgnoreDefaultsWithCoveredEnums) {
3123 // If the 'To' has no label or is labeled but the label isn't a
3124 // CaseStmt then filter this edge.
3125 if (const SwitchStmt *S =
3126 dyn_cast_or_null<SwitchStmt>(From->getTerminator().getStmt())) {
3127 if (S->isAllEnumCasesCovered()) {
3128 const Stmt *L = To->getLabel();
3129 if (!L || !isa<CaseStmt>(L))
3138 //===----------------------------------------------------------------------===//
3139 // Cleanup: CFG dstor.
3140 //===----------------------------------------------------------------------===//
3143 delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap);
3146 //===----------------------------------------------------------------------===//
3147 // CFG pretty printing
3148 //===----------------------------------------------------------------------===//
3152 class StmtPrinterHelper : public PrinterHelper {
3153 typedef llvm::DenseMap<const Stmt*,std::pair<unsigned,unsigned> > StmtMapTy;
3154 typedef llvm::DenseMap<const Decl*,std::pair<unsigned,unsigned> > DeclMapTy;
3157 signed currentBlock;
3158 unsigned currentStmt;
3159 const LangOptions &LangOpts;
3162 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO)
3163 : currentBlock(0), currentStmt(0), LangOpts(LO)
3165 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) {
3167 for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ;
3168 BI != BEnd; ++BI, ++j ) {
3169 if (const CFGStmt *SE = BI->getAs<CFGStmt>()) {
3170 const Stmt *stmt= SE->getStmt();
3171 std::pair<unsigned, unsigned> P((*I)->getBlockID(), j);
3174 switch (stmt->getStmtClass()) {
3175 case Stmt::DeclStmtClass:
3176 DeclMap[cast<DeclStmt>(stmt)->getSingleDecl()] = P;
3178 case Stmt::IfStmtClass: {
3179 const VarDecl *var = cast<IfStmt>(stmt)->getConditionVariable();
3184 case Stmt::ForStmtClass: {
3185 const VarDecl *var = cast<ForStmt>(stmt)->getConditionVariable();
3190 case Stmt::WhileStmtClass: {
3191 const VarDecl *var =
3192 cast<WhileStmt>(stmt)->getConditionVariable();
3197 case Stmt::SwitchStmtClass: {
3198 const VarDecl *var =
3199 cast<SwitchStmt>(stmt)->getConditionVariable();
3204 case Stmt::CXXCatchStmtClass: {
3205 const VarDecl *var =
3206 cast<CXXCatchStmt>(stmt)->getExceptionDecl();
3220 virtual ~StmtPrinterHelper() {}
3222 const LangOptions &getLangOpts() const { return LangOpts; }
3223 void setBlockID(signed i) { currentBlock = i; }
3224 void setStmtID(unsigned i) { currentStmt = i; }
3226 virtual bool handledStmt(Stmt* S, llvm::raw_ostream& OS) {
3227 StmtMapTy::iterator I = StmtMap.find(S);
3229 if (I == StmtMap.end())
3232 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
3233 && I->second.second == currentStmt) {
3237 OS << "[B" << I->second.first << "." << I->second.second << "]";
3241 bool handleDecl(const Decl* D, llvm::raw_ostream& OS) {
3242 DeclMapTy::iterator I = DeclMap.find(D);
3244 if (I == DeclMap.end())
3247 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
3248 && I->second.second == currentStmt) {
3252 OS << "[B" << I->second.first << "." << I->second.second << "]";
3256 } // end anonymous namespace
3260 class CFGBlockTerminatorPrint
3261 : public StmtVisitor<CFGBlockTerminatorPrint,void> {
3263 llvm::raw_ostream& OS;
3264 StmtPrinterHelper* Helper;
3265 PrintingPolicy Policy;
3267 CFGBlockTerminatorPrint(llvm::raw_ostream& os, StmtPrinterHelper* helper,
3268 const PrintingPolicy &Policy)
3269 : OS(os), Helper(helper), Policy(Policy) {}
3271 void VisitIfStmt(IfStmt* I) {
3273 I->getCond()->printPretty(OS,Helper,Policy);
3277 void VisitStmt(Stmt* Terminator) {
3278 Terminator->printPretty(OS, Helper, Policy);
3281 void VisitForStmt(ForStmt* F) {
3286 if (Stmt* C = F->getCond())
3287 C->printPretty(OS, Helper, Policy);
3294 void VisitWhileStmt(WhileStmt* W) {
3296 if (Stmt* C = W->getCond())
3297 C->printPretty(OS, Helper, Policy);
3300 void VisitDoStmt(DoStmt* D) {
3301 OS << "do ... while ";
3302 if (Stmt* C = D->getCond())
3303 C->printPretty(OS, Helper, Policy);
3306 void VisitSwitchStmt(SwitchStmt* Terminator) {
3308 Terminator->getCond()->printPretty(OS, Helper, Policy);
3311 void VisitCXXTryStmt(CXXTryStmt* CS) {
3315 void VisitAbstractConditionalOperator(AbstractConditionalOperator* C) {
3316 C->getCond()->printPretty(OS, Helper, Policy);
3317 OS << " ? ... : ...";
3320 void VisitChooseExpr(ChooseExpr* C) {
3321 OS << "__builtin_choose_expr( ";
3322 C->getCond()->printPretty(OS, Helper, Policy);
3326 void VisitIndirectGotoStmt(IndirectGotoStmt* I) {
3328 I->getTarget()->printPretty(OS, Helper, Policy);
3331 void VisitBinaryOperator(BinaryOperator* B) {
3332 if (!B->isLogicalOp()) {
3337 B->getLHS()->printPretty(OS, Helper, Policy);
3339 switch (B->getOpcode()) {
3347 assert(false && "Invalid logical operator.");
3351 void VisitExpr(Expr* E) {
3352 E->printPretty(OS, Helper, Policy);
3355 } // end anonymous namespace
3357 static void print_elem(llvm::raw_ostream &OS, StmtPrinterHelper* Helper,
3358 const CFGElement &E) {
3359 if (const CFGStmt *CS = E.getAs<CFGStmt>()) {
3360 Stmt *S = CS->getStmt();
3364 // special printing for statement-expressions.
3365 if (StmtExpr* SE = dyn_cast<StmtExpr>(S)) {
3366 CompoundStmt* Sub = SE->getSubStmt();
3368 if (Sub->children()) {
3370 Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS);
3375 // special printing for comma expressions.
3376 if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
3377 if (B->getOpcode() == BO_Comma) {
3379 Helper->handledStmt(B->getRHS(),OS);
3385 S->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts()));
3387 if (isa<CXXOperatorCallExpr>(S)) {
3388 OS << " (OperatorCall)";
3389 } else if (isa<CXXBindTemporaryExpr>(S)) {
3390 OS << " (BindTemporary)";
3393 // Expressions need a newline.
3397 } else if (const CFGInitializer *IE = E.getAs<CFGInitializer>()) {
3398 const CXXCtorInitializer *I = IE->getInitializer();
3399 if (I->isBaseInitializer())
3400 OS << I->getBaseClass()->getAsCXXRecordDecl()->getName();
3401 else OS << I->getAnyMember()->getName();
3404 if (Expr* IE = I->getInit())
3405 IE->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts()));
3408 if (I->isBaseInitializer())
3409 OS << " (Base initializer)\n";
3410 else OS << " (Member initializer)\n";
3412 } else if (const CFGAutomaticObjDtor *DE = E.getAs<CFGAutomaticObjDtor>()){
3413 const VarDecl* VD = DE->getVarDecl();
3414 Helper->handleDecl(VD, OS);
3416 const Type* T = VD->getType().getTypePtr();
3417 if (const ReferenceType* RT = T->getAs<ReferenceType>())
3418 T = RT->getPointeeType().getTypePtr();
3419 else if (const Type *ET = T->getArrayElementTypeNoTypeQual())
3422 OS << ".~" << T->getAsCXXRecordDecl()->getName().str() << "()";
3423 OS << " (Implicit destructor)\n";
3425 } else if (const CFGBaseDtor *BE = E.getAs<CFGBaseDtor>()) {
3426 const CXXBaseSpecifier *BS = BE->getBaseSpecifier();
3427 OS << "~" << BS->getType()->getAsCXXRecordDecl()->getName() << "()";
3428 OS << " (Base object destructor)\n";
3430 } else if (const CFGMemberDtor *ME = E.getAs<CFGMemberDtor>()) {
3431 const FieldDecl *FD = ME->getFieldDecl();
3433 const Type *T = FD->getType().getTypePtr();
3434 if (const Type *ET = T->getArrayElementTypeNoTypeQual())
3437 OS << "this->" << FD->getName();
3438 OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()";
3439 OS << " (Member object destructor)\n";
3441 } else if (const CFGTemporaryDtor *TE = E.getAs<CFGTemporaryDtor>()) {
3442 const CXXBindTemporaryExpr *BT = TE->getBindTemporaryExpr();
3443 OS << "~" << BT->getType()->getAsCXXRecordDecl()->getName() << "()";
3444 OS << " (Temporary object destructor)\n";
3448 static void print_block(llvm::raw_ostream& OS, const CFG* cfg,
3450 StmtPrinterHelper* Helper, bool print_edges) {
3452 if (Helper) Helper->setBlockID(B.getBlockID());
3454 // Print the header.
3455 OS << "\n [ B" << B.getBlockID();
3457 if (&B == &cfg->getEntry())
3458 OS << " (ENTRY) ]\n";
3459 else if (&B == &cfg->getExit())
3460 OS << " (EXIT) ]\n";
3461 else if (&B == cfg->getIndirectGotoBlock())
3462 OS << " (INDIRECT GOTO DISPATCH) ]\n";
3466 // Print the label of this block.
3467 if (Stmt* Label = const_cast<Stmt*>(B.getLabel())) {
3472 if (LabelStmt* L = dyn_cast<LabelStmt>(Label))
3474 else if (CaseStmt* C = dyn_cast<CaseStmt>(Label)) {
3476 C->getLHS()->printPretty(OS, Helper,
3477 PrintingPolicy(Helper->getLangOpts()));
3480 C->getRHS()->printPretty(OS, Helper,
3481 PrintingPolicy(Helper->getLangOpts()));
3483 } else if (isa<DefaultStmt>(Label))
3485 else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Label)) {
3487 if (CS->getExceptionDecl())
3488 CS->getExceptionDecl()->print(OS, PrintingPolicy(Helper->getLangOpts()),
3495 assert(false && "Invalid label statement in CFGBlock.");
3500 // Iterate through the statements in the block and print them.
3503 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ;
3504 I != E ; ++I, ++j ) {
3506 // Print the statement # in the basic block and the statement itself.
3510 OS << llvm::format("%3d", j) << ": ";
3513 Helper->setStmtID(j);
3515 print_elem(OS,Helper,*I);
3518 // Print the terminator of this block.
3519 if (B.getTerminator()) {
3525 if (Helper) Helper->setBlockID(-1);
3527 CFGBlockTerminatorPrint TPrinter(OS, Helper,
3528 PrintingPolicy(Helper->getLangOpts()));
3529 TPrinter.Visit(const_cast<Stmt*>(B.getTerminator().getStmt()));
3534 // Print the predecessors of this block.
3535 OS << " Predecessors (" << B.pred_size() << "):";
3538 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end();
3541 if (i == 8 || (i-8) == 0)
3544 OS << " B" << (*I)->getBlockID();
3549 // Print the successors of this block.
3550 OS << " Successors (" << B.succ_size() << "):";
3553 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end();
3556 if (i == 8 || (i-8) % 10 == 0)
3560 OS << " B" << (*I)->getBlockID();
3570 /// dump - A simple pretty printer of a CFG that outputs to stderr.
3571 void CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); }
3573 /// print - A simple pretty printer of a CFG that outputs to an ostream.
3574 void CFG::print(llvm::raw_ostream &OS, const LangOptions &LO) const {
3575 StmtPrinterHelper Helper(this, LO);
3577 // Print the entry block.
3578 print_block(OS, this, getEntry(), &Helper, true);
3580 // Iterate through the CFGBlocks and print them one by one.
3581 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) {
3582 // Skip the entry block, because we already printed it.
3583 if (&(**I) == &getEntry() || &(**I) == &getExit())
3586 print_block(OS, this, **I, &Helper, true);
3589 // Print the exit block.
3590 print_block(OS, this, getExit(), &Helper, true);
3594 /// dump - A simply pretty printer of a CFGBlock that outputs to stderr.
3595 void CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const {
3596 print(llvm::errs(), cfg, LO);
3599 /// print - A simple pretty printer of a CFGBlock that outputs to an ostream.
3600 /// Generally this will only be called from CFG::print.
3601 void CFGBlock::print(llvm::raw_ostream& OS, const CFG* cfg,
3602 const LangOptions &LO) const {
3603 StmtPrinterHelper Helper(cfg, LO);
3604 print_block(OS, cfg, *this, &Helper, true);
3607 /// printTerminator - A simple pretty printer of the terminator of a CFGBlock.
3608 void CFGBlock::printTerminator(llvm::raw_ostream &OS,
3609 const LangOptions &LO) const {
3610 CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO));
3611 TPrinter.Visit(const_cast<Stmt*>(getTerminator().getStmt()));
3614 Stmt* CFGBlock::getTerminatorCondition() {
3615 Stmt *Terminator = this->Terminator;
3621 switch (Terminator->getStmtClass()) {
3625 case Stmt::ForStmtClass:
3626 E = cast<ForStmt>(Terminator)->getCond();
3629 case Stmt::WhileStmtClass:
3630 E = cast<WhileStmt>(Terminator)->getCond();
3633 case Stmt::DoStmtClass:
3634 E = cast<DoStmt>(Terminator)->getCond();
3637 case Stmt::IfStmtClass:
3638 E = cast<IfStmt>(Terminator)->getCond();
3641 case Stmt::ChooseExprClass:
3642 E = cast<ChooseExpr>(Terminator)->getCond();
3645 case Stmt::IndirectGotoStmtClass:
3646 E = cast<IndirectGotoStmt>(Terminator)->getTarget();
3649 case Stmt::SwitchStmtClass:
3650 E = cast<SwitchStmt>(Terminator)->getCond();
3653 case Stmt::BinaryConditionalOperatorClass:
3654 E = cast<BinaryConditionalOperator>(Terminator)->getCond();
3657 case Stmt::ConditionalOperatorClass:
3658 E = cast<ConditionalOperator>(Terminator)->getCond();
3661 case Stmt::BinaryOperatorClass: // '&&' and '||'
3662 E = cast<BinaryOperator>(Terminator)->getLHS();
3665 case Stmt::ObjCForCollectionStmtClass:
3669 return E ? E->IgnoreParens() : NULL;
3672 //===----------------------------------------------------------------------===//
3673 // CFG Graphviz Visualization
3674 //===----------------------------------------------------------------------===//
3678 static StmtPrinterHelper* GraphHelper;
3681 void CFG::viewCFG(const LangOptions &LO) const {
3683 StmtPrinterHelper H(this, LO);
3685 llvm::ViewGraph(this,"CFG");
3692 struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits {
3694 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
3696 static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph) {
3699 std::string OutSStr;
3700 llvm::raw_string_ostream Out(OutSStr);
3701 print_block(Out,Graph, *Node, GraphHelper, false);
3702 std::string& OutStr = Out.str();
3704 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin());
3706 // Process string output to make it nicer...
3707 for (unsigned i = 0; i != OutStr.length(); ++i)
3708 if (OutStr[i] == '\n') { // Left justify
3710 OutStr.insert(OutStr.begin()+i+1, 'l');
3719 } // end namespace llvm