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);
377 CFGBlock *createNoReturnBlock();
379 CFGBlock *addStmt(Stmt *S) {
380 return Visit(S, AddStmtChoice::AlwaysAdd);
382 CFGBlock *addInitializer(CXXCtorInitializer *I);
383 void addAutomaticObjDtors(LocalScope::const_iterator B,
384 LocalScope::const_iterator E, Stmt *S);
385 void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD);
387 // Local scopes creation.
388 LocalScope* createOrReuseLocalScope(LocalScope* Scope);
390 void addLocalScopeForStmt(Stmt *S);
391 LocalScope* addLocalScopeForDeclStmt(DeclStmt *DS, LocalScope* Scope = NULL);
392 LocalScope* addLocalScopeForVarDecl(VarDecl *VD, LocalScope* Scope = NULL);
394 void addLocalScopeAndDtors(Stmt *S);
396 // Interface to CFGBlock - adding CFGElements.
397 void appendStmt(CFGBlock *B, const Stmt *S) {
398 if (alwaysAdd(S) && cachedEntry)
399 cachedEntry->second = B;
401 // All block-level expressions should have already been IgnoreParens()ed.
402 assert(!isa<Expr>(S) || cast<Expr>(S)->IgnoreParens() == S);
403 B->appendStmt(const_cast<Stmt*>(S), cfg->getBumpVectorContext());
405 void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) {
406 B->appendInitializer(I, cfg->getBumpVectorContext());
408 void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) {
409 B->appendBaseDtor(BS, cfg->getBumpVectorContext());
411 void appendMemberDtor(CFGBlock *B, FieldDecl *FD) {
412 B->appendMemberDtor(FD, cfg->getBumpVectorContext());
414 void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) {
415 B->appendTemporaryDtor(E, cfg->getBumpVectorContext());
417 void appendAutomaticObjDtor(CFGBlock *B, VarDecl *VD, Stmt *S) {
418 B->appendAutomaticObjDtor(VD, S, cfg->getBumpVectorContext());
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) {
441 if (!BuildOpts.PruneTriviallyFalseEdges ||
442 S->isTypeDependent() || S->isValueDependent() ||
443 !S->EvaluateAsBooleanCondition(Result, *Context))
450 inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder,
451 const Stmt *stmt) const {
452 return builder.alwaysAdd(stmt) || kind == AlwaysAdd;
455 bool CFGBuilder::alwaysAdd(const Stmt *stmt) {
456 bool shouldAdd = BuildOpts.alwaysAdd(stmt);
458 if (!BuildOpts.forcedBlkExprs)
461 if (lastLookup == stmt) {
463 assert(cachedEntry->first == stmt);
471 // Perform the lookup!
472 CFG::BuildOptions::ForcedBlkExprs *fb = *BuildOpts.forcedBlkExprs;
475 // No need to update 'cachedEntry', since it will always be null.
476 assert(cachedEntry == 0);
480 CFG::BuildOptions::ForcedBlkExprs::iterator itr = fb->find(stmt);
481 if (itr == fb->end()) {
490 // FIXME: Add support for dependent-sized array types in C++?
491 // Does it even make sense to build a CFG for an uninstantiated template?
492 static const VariableArrayType *FindVA(const Type *t) {
493 while (const ArrayType *vt = dyn_cast<ArrayType>(t)) {
494 if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(vt))
495 if (vat->getSizeExpr())
498 t = vt->getElementType().getTypePtr();
504 /// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an
505 /// arbitrary statement. Examples include a single expression or a function
506 /// body (compound statement). The ownership of the returned CFG is
507 /// transferred to the caller. If CFG construction fails, this method returns
509 CFG* CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) {
514 // Create an empty block that will serve as the exit block for the CFG. Since
515 // this is the first block added to the CFG, it will be implicitly registered
516 // as the exit block.
517 Succ = createBlock();
518 assert(Succ == &cfg->getExit());
519 Block = NULL; // the EXIT block is empty. Create all other blocks lazily.
521 if (BuildOpts.AddImplicitDtors)
522 if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D))
523 addImplicitDtorsForDestructor(DD);
525 // Visit the statements and create the CFG.
526 CFGBlock *B = addStmt(Statement);
531 // For C++ constructor add initializers to CFG.
532 if (const CXXConstructorDecl *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) {
533 for (CXXConstructorDecl::init_const_reverse_iterator I = CD->init_rbegin(),
534 E = CD->init_rend(); I != E; ++I) {
535 B = addInitializer(*I);
544 // Backpatch the gotos whose label -> block mappings we didn't know when we
546 for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(),
547 E = BackpatchBlocks.end(); I != E; ++I ) {
549 CFGBlock *B = I->block;
550 GotoStmt *G = cast<GotoStmt>(B->getTerminator());
551 LabelMapTy::iterator LI = LabelMap.find(G->getLabel());
553 // If there is no target for the goto, then we are looking at an
554 // incomplete AST. Handle this by not registering a successor.
555 if (LI == LabelMap.end()) continue;
557 JumpTarget JT = LI->second;
558 prependAutomaticObjDtorsWithTerminator(B, I->scopePosition,
560 addSuccessor(B, JT.block);
563 // Add successors to the Indirect Goto Dispatch block (if we have one).
564 if (CFGBlock *B = cfg->getIndirectGotoBlock())
565 for (LabelSetTy::iterator I = AddressTakenLabels.begin(),
566 E = AddressTakenLabels.end(); I != E; ++I ) {
568 // Lookup the target block.
569 LabelMapTy::iterator LI = LabelMap.find(*I);
571 // If there is no target block that contains label, then we are looking
572 // at an incomplete AST. Handle this by not registering a successor.
573 if (LI == LabelMap.end()) continue;
575 addSuccessor(B, LI->second.block);
578 // Create an empty entry block that has no predecessors.
579 cfg->setEntry(createBlock());
584 /// createBlock - Used to lazily create blocks that are connected
585 /// to the current (global) succcessor.
586 CFGBlock *CFGBuilder::createBlock(bool add_successor) {
587 CFGBlock *B = cfg->createBlock();
588 if (add_successor && Succ)
589 addSuccessor(B, Succ);
593 /// createNoReturnBlock - Used to create a block is a 'noreturn' point in the
594 /// CFG. It is *not* connected to the current (global) successor, and instead
595 /// directly tied to the exit block in order to be reachable.
596 CFGBlock *CFGBuilder::createNoReturnBlock() {
597 CFGBlock *B = createBlock(false);
598 B->setHasNoReturnElement();
599 addSuccessor(B, &cfg->getExit());
603 /// addInitializer - Add C++ base or member initializer element to CFG.
604 CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) {
605 if (!BuildOpts.AddInitializers)
608 bool IsReference = false;
609 bool HasTemporaries = false;
611 // Destructors of temporaries in initialization expression should be called
612 // after initialization finishes.
613 Expr *Init = I->getInit();
615 if (FieldDecl *FD = I->getAnyMember())
616 IsReference = FD->getType()->isReferenceType();
617 HasTemporaries = isa<ExprWithCleanups>(Init);
619 if (BuildOpts.AddImplicitDtors && HasTemporaries) {
620 // Generate destructors for temporaries in initialization expression.
621 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),
627 appendInitializer(Block, I);
630 if (HasTemporaries) {
631 // For expression with temporaries go directly to subexpression to omit
632 // generating destructors for the second time.
633 return Visit(cast<ExprWithCleanups>(Init)->getSubExpr());
641 /// addAutomaticObjDtors - Add to current block automatic objects destructors
642 /// for objects in range of local scope positions. Use S as trigger statement
644 void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B,
645 LocalScope::const_iterator E, Stmt *S) {
646 if (!BuildOpts.AddImplicitDtors)
652 CFGBlock::iterator InsertPos;
654 // We need to append the destructors in reverse order, but any one of them
655 // may be a no-return destructor which changes the CFG. As a result, buffer
656 // this sequence up and replay them in reverse order when appending onto the
658 SmallVector<VarDecl*, 10> Decls;
659 Decls.reserve(B.distance(E));
660 for (LocalScope::const_iterator I = B; I != E; ++I)
663 for (SmallVectorImpl<VarDecl*>::reverse_iterator I = Decls.rbegin(),
666 // If this destructor is marked as a no-return destructor, we need to
667 // create a new block for the destructor which does not have as a successor
668 // anything built thus far: control won't flow out of this block.
669 QualType Ty = (*I)->getType().getNonReferenceType();
670 if (const ArrayType *AT = Context->getAsArrayType(Ty))
671 Ty = AT->getElementType();
672 const CXXDestructorDecl *Dtor = Ty->getAsCXXRecordDecl()->getDestructor();
673 if (cast<FunctionType>(Dtor->getType())->getNoReturnAttr())
674 Block = createNoReturnBlock();
678 appendAutomaticObjDtor(Block, *I, S);
682 /// addImplicitDtorsForDestructor - Add implicit destructors generated for
683 /// base and member objects in destructor.
684 void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) {
685 assert (BuildOpts.AddImplicitDtors
686 && "Can be called only when dtors should be added");
687 const CXXRecordDecl *RD = DD->getParent();
689 // At the end destroy virtual base objects.
690 for (CXXRecordDecl::base_class_const_iterator VI = RD->vbases_begin(),
691 VE = RD->vbases_end(); VI != VE; ++VI) {
692 const CXXRecordDecl *CD = VI->getType()->getAsCXXRecordDecl();
693 if (!CD->hasTrivialDestructor()) {
695 appendBaseDtor(Block, VI);
699 // Before virtual bases destroy direct base objects.
700 for (CXXRecordDecl::base_class_const_iterator BI = RD->bases_begin(),
701 BE = RD->bases_end(); BI != BE; ++BI) {
702 if (!BI->isVirtual()) {
703 const CXXRecordDecl *CD = BI->getType()->getAsCXXRecordDecl();
704 if (!CD->hasTrivialDestructor()) {
706 appendBaseDtor(Block, BI);
711 // First destroy member objects.
712 for (CXXRecordDecl::field_iterator FI = RD->field_begin(),
713 FE = RD->field_end(); FI != FE; ++FI) {
714 // Check for constant size array. Set type to array element type.
715 QualType QT = FI->getType();
716 if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {
717 if (AT->getSize() == 0)
719 QT = AT->getElementType();
722 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
723 if (!CD->hasTrivialDestructor()) {
725 appendMemberDtor(Block, *FI);
730 /// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either
731 /// way return valid LocalScope object.
732 LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) {
734 llvm::BumpPtrAllocator &alloc = cfg->getAllocator();
735 Scope = alloc.Allocate<LocalScope>();
736 BumpVectorContext ctx(alloc);
737 new (Scope) LocalScope(ctx, ScopePos);
742 /// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement
743 /// that should create implicit scope (e.g. if/else substatements).
744 void CFGBuilder::addLocalScopeForStmt(Stmt *S) {
745 if (!BuildOpts.AddImplicitDtors)
748 LocalScope *Scope = 0;
750 // For compound statement we will be creating explicit scope.
751 if (CompoundStmt *CS = dyn_cast<CompoundStmt>(S)) {
752 for (CompoundStmt::body_iterator BI = CS->body_begin(), BE = CS->body_end()
754 Stmt *SI = (*BI)->stripLabelLikeStatements();
755 if (DeclStmt *DS = dyn_cast<DeclStmt>(SI))
756 Scope = addLocalScopeForDeclStmt(DS, Scope);
761 // For any other statement scope will be implicit and as such will be
762 // interesting only for DeclStmt.
763 if (DeclStmt *DS = dyn_cast<DeclStmt>(S->stripLabelLikeStatements()))
764 addLocalScopeForDeclStmt(DS);
767 /// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will
768 /// reuse Scope if not NULL.
769 LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt *DS,
771 if (!BuildOpts.AddImplicitDtors)
774 for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end()
776 if (VarDecl *VD = dyn_cast<VarDecl>(*DI))
777 Scope = addLocalScopeForVarDecl(VD, Scope);
782 /// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will
783 /// create add scope for automatic objects and temporary objects bound to
784 /// const reference. Will reuse Scope if not NULL.
785 LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD,
787 if (!BuildOpts.AddImplicitDtors)
790 // Check if variable is local.
791 switch (VD->getStorageClass()) {
796 default: return Scope;
799 // Check for const references bound to temporary. Set type to pointee.
800 QualType QT = VD->getType();
801 if (const ReferenceType* RT = QT.getTypePtr()->getAs<ReferenceType>()) {
802 QT = RT->getPointeeType();
803 if (!QT.isConstQualified())
805 if (!VD->extendsLifetimeOfTemporary())
809 // Check for constant size array. Set type to array element type.
810 if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {
811 if (AT->getSize() == 0)
813 QT = AT->getElementType();
816 // Check if type is a C++ class with non-trivial destructor.
817 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
818 if (!CD->hasTrivialDestructor()) {
819 // Add the variable to scope
820 Scope = createOrReuseLocalScope(Scope);
822 ScopePos = Scope->begin();
827 /// addLocalScopeAndDtors - For given statement add local scope for it and
828 /// add destructors that will cleanup the scope. Will reuse Scope if not NULL.
829 void CFGBuilder::addLocalScopeAndDtors(Stmt *S) {
830 if (!BuildOpts.AddImplicitDtors)
833 LocalScope::const_iterator scopeBeginPos = ScopePos;
834 addLocalScopeForStmt(S);
835 addAutomaticObjDtors(ScopePos, scopeBeginPos, S);
838 /// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for
839 /// variables with automatic storage duration to CFGBlock's elements vector.
840 /// Elements will be prepended to physical beginning of the vector which
841 /// happens to be logical end. Use blocks terminator as statement that specifies
842 /// destructors call site.
843 /// FIXME: This mechanism for adding automatic destructors doesn't handle
844 /// no-return destructors properly.
845 void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
846 LocalScope::const_iterator B, LocalScope::const_iterator E) {
847 BumpVectorContext &C = cfg->getBumpVectorContext();
848 CFGBlock::iterator InsertPos
849 = Blk->beginAutomaticObjDtorsInsert(Blk->end(), B.distance(E), C);
850 for (LocalScope::const_iterator I = B; I != E; ++I)
851 InsertPos = Blk->insertAutomaticObjDtor(InsertPos, *I,
852 Blk->getTerminator());
855 /// Visit - Walk the subtree of a statement and add extra
856 /// blocks for ternary operators, &&, and ||. We also process "," and
857 /// DeclStmts (which may contain nested control-flow).
858 CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) {
864 if (Expr *E = dyn_cast<Expr>(S))
865 S = E->IgnoreParens();
867 switch (S->getStmtClass()) {
869 return VisitStmt(S, asc);
871 case Stmt::AddrLabelExprClass:
872 return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc);
874 case Stmt::BinaryConditionalOperatorClass:
875 return VisitConditionalOperator(cast<BinaryConditionalOperator>(S), asc);
877 case Stmt::BinaryOperatorClass:
878 return VisitBinaryOperator(cast<BinaryOperator>(S), asc);
880 case Stmt::BlockExprClass:
881 return VisitBlockExpr(cast<BlockExpr>(S), asc);
883 case Stmt::BreakStmtClass:
884 return VisitBreakStmt(cast<BreakStmt>(S));
886 case Stmt::CallExprClass:
887 case Stmt::CXXOperatorCallExprClass:
888 case Stmt::CXXMemberCallExprClass:
889 return VisitCallExpr(cast<CallExpr>(S), asc);
891 case Stmt::CaseStmtClass:
892 return VisitCaseStmt(cast<CaseStmt>(S));
894 case Stmt::ChooseExprClass:
895 return VisitChooseExpr(cast<ChooseExpr>(S), asc);
897 case Stmt::CompoundStmtClass:
898 return VisitCompoundStmt(cast<CompoundStmt>(S));
900 case Stmt::ConditionalOperatorClass:
901 return VisitConditionalOperator(cast<ConditionalOperator>(S), asc);
903 case Stmt::ContinueStmtClass:
904 return VisitContinueStmt(cast<ContinueStmt>(S));
906 case Stmt::CXXCatchStmtClass:
907 return VisitCXXCatchStmt(cast<CXXCatchStmt>(S));
909 case Stmt::ExprWithCleanupsClass:
910 return VisitExprWithCleanups(cast<ExprWithCleanups>(S), asc);
912 case Stmt::CXXBindTemporaryExprClass:
913 return VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), asc);
915 case Stmt::CXXConstructExprClass:
916 return VisitCXXConstructExpr(cast<CXXConstructExpr>(S), asc);
918 case Stmt::CXXFunctionalCastExprClass:
919 return VisitCXXFunctionalCastExpr(cast<CXXFunctionalCastExpr>(S), asc);
921 case Stmt::CXXTemporaryObjectExprClass:
922 return VisitCXXTemporaryObjectExpr(cast<CXXTemporaryObjectExpr>(S), asc);
924 case Stmt::CXXThrowExprClass:
925 return VisitCXXThrowExpr(cast<CXXThrowExpr>(S));
927 case Stmt::CXXTryStmtClass:
928 return VisitCXXTryStmt(cast<CXXTryStmt>(S));
930 case Stmt::CXXForRangeStmtClass:
931 return VisitCXXForRangeStmt(cast<CXXForRangeStmt>(S));
933 case Stmt::DeclStmtClass:
934 return VisitDeclStmt(cast<DeclStmt>(S));
936 case Stmt::DefaultStmtClass:
937 return VisitDefaultStmt(cast<DefaultStmt>(S));
939 case Stmt::DoStmtClass:
940 return VisitDoStmt(cast<DoStmt>(S));
942 case Stmt::ForStmtClass:
943 return VisitForStmt(cast<ForStmt>(S));
945 case Stmt::GotoStmtClass:
946 return VisitGotoStmt(cast<GotoStmt>(S));
948 case Stmt::IfStmtClass:
949 return VisitIfStmt(cast<IfStmt>(S));
951 case Stmt::ImplicitCastExprClass:
952 return VisitImplicitCastExpr(cast<ImplicitCastExpr>(S), asc);
954 case Stmt::IndirectGotoStmtClass:
955 return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S));
957 case Stmt::LabelStmtClass:
958 return VisitLabelStmt(cast<LabelStmt>(S));
960 case Stmt::MemberExprClass:
961 return VisitMemberExpr(cast<MemberExpr>(S), asc);
963 case Stmt::ObjCAtCatchStmtClass:
964 return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S));
966 case Stmt::ObjCAtSynchronizedStmtClass:
967 return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S));
969 case Stmt::ObjCAtThrowStmtClass:
970 return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S));
972 case Stmt::ObjCAtTryStmtClass:
973 return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S));
975 case Stmt::ObjCForCollectionStmtClass:
976 return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S));
978 case Stmt::NullStmtClass:
981 case Stmt::ReturnStmtClass:
982 return VisitReturnStmt(cast<ReturnStmt>(S));
984 case Stmt::UnaryExprOrTypeTraitExprClass:
985 return VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
988 case Stmt::StmtExprClass:
989 return VisitStmtExpr(cast<StmtExpr>(S), asc);
991 case Stmt::SwitchStmtClass:
992 return VisitSwitchStmt(cast<SwitchStmt>(S));
994 case Stmt::UnaryOperatorClass:
995 return VisitUnaryOperator(cast<UnaryOperator>(S), asc);
997 case Stmt::WhileStmtClass:
998 return VisitWhileStmt(cast<WhileStmt>(S));
1002 CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) {
1003 if (asc.alwaysAdd(*this, S)) {
1005 appendStmt(Block, S);
1008 return VisitChildren(S);
1011 /// VisitChildren - Visit the children of a Stmt.
1012 CFGBlock *CFGBuilder::VisitChildren(Stmt *Terminator) {
1013 CFGBlock *lastBlock = Block;
1014 for (Stmt::child_range I = Terminator->children(); I; ++I)
1015 if (Stmt *child = *I)
1016 if (CFGBlock *b = Visit(child))
1022 CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A,
1023 AddStmtChoice asc) {
1024 AddressTakenLabels.insert(A->getLabel());
1026 if (asc.alwaysAdd(*this, A)) {
1028 appendStmt(Block, A);
1034 CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U,
1035 AddStmtChoice asc) {
1036 if (asc.alwaysAdd(*this, U)) {
1038 appendStmt(Block, U);
1041 return Visit(U->getSubExpr(), AddStmtChoice());
1044 CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B,
1045 AddStmtChoice asc) {
1046 if (B->isLogicalOp()) { // && or ||
1047 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
1048 appendStmt(ConfluenceBlock, B);
1053 // create the block evaluating the LHS
1054 CFGBlock *LHSBlock = createBlock(false);
1055 LHSBlock->setTerminator(B);
1057 // create the block evaluating the RHS
1058 Succ = ConfluenceBlock;
1060 CFGBlock *RHSBlock = addStmt(B->getRHS());
1066 // Create an empty block for cases where the RHS doesn't require
1067 // any explicit statements in the CFG.
1068 RHSBlock = createBlock();
1071 // See if this is a known constant.
1072 TryResult KnownVal = tryEvaluateBool(B->getLHS());
1073 if (KnownVal.isKnown() && (B->getOpcode() == BO_LOr))
1076 // Now link the LHSBlock with RHSBlock.
1077 if (B->getOpcode() == BO_LOr) {
1078 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock);
1079 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock);
1081 assert(B->getOpcode() == BO_LAnd);
1082 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock);
1083 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock);
1086 // Generate the blocks for evaluating the LHS.
1088 return addStmt(B->getLHS());
1091 if (B->getOpcode() == BO_Comma) { // ,
1093 appendStmt(Block, B);
1094 addStmt(B->getRHS());
1095 return addStmt(B->getLHS());
1098 if (B->isAssignmentOp()) {
1099 if (asc.alwaysAdd(*this, B)) {
1101 appendStmt(Block, B);
1104 return Visit(B->getRHS());
1107 if (asc.alwaysAdd(*this, B)) {
1109 appendStmt(Block, B);
1112 CFGBlock *RBlock = Visit(B->getRHS());
1113 CFGBlock *LBlock = Visit(B->getLHS());
1114 // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr
1115 // containing a DoStmt, and the LHS doesn't create a new block, then we should
1116 // return RBlock. Otherwise we'll incorrectly return NULL.
1117 return (LBlock ? LBlock : RBlock);
1120 CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) {
1121 if (asc.alwaysAdd(*this, E)) {
1123 appendStmt(Block, E);
1128 CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) {
1129 // "break" is a control-flow statement. Thus we stop processing the current
1134 // Now create a new block that ends with the break statement.
1135 Block = createBlock(false);
1136 Block->setTerminator(B);
1138 // If there is no target for the break, then we are looking at an incomplete
1139 // AST. This means that the CFG cannot be constructed.
1140 if (BreakJumpTarget.block) {
1141 addAutomaticObjDtors(ScopePos, BreakJumpTarget.scopePosition, B);
1142 addSuccessor(Block, BreakJumpTarget.block);
1150 static bool CanThrow(Expr *E, ASTContext &Ctx) {
1151 QualType Ty = E->getType();
1152 if (Ty->isFunctionPointerType())
1153 Ty = Ty->getAs<PointerType>()->getPointeeType();
1154 else if (Ty->isBlockPointerType())
1155 Ty = Ty->getAs<BlockPointerType>()->getPointeeType();
1157 const FunctionType *FT = Ty->getAs<FunctionType>();
1159 if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT))
1160 if (Proto->isNothrow(Ctx))
1166 CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) {
1167 // Compute the callee type.
1168 QualType calleeType = C->getCallee()->getType();
1169 if (calleeType == Context->BoundMemberTy) {
1170 QualType boundType = Expr::findBoundMemberType(C->getCallee());
1172 // We should only get a null bound type if processing a dependent
1173 // CFG. Recover by assuming nothing.
1174 if (!boundType.isNull()) calleeType = boundType;
1177 // If this is a call to a no-return function, this stops the block here.
1178 bool NoReturn = getFunctionExtInfo(*calleeType).getNoReturn();
1180 bool AddEHEdge = false;
1182 // Languages without exceptions are assumed to not throw.
1183 if (Context->getLangOptions().Exceptions) {
1184 if (BuildOpts.AddEHEdges)
1188 if (FunctionDecl *FD = C->getDirectCallee()) {
1189 if (FD->hasAttr<NoReturnAttr>())
1191 if (FD->hasAttr<NoThrowAttr>())
1195 if (!CanThrow(C->getCallee(), *Context))
1198 if (!NoReturn && !AddEHEdge)
1199 return VisitStmt(C, asc.withAlwaysAdd(true));
1208 Block = createNoReturnBlock();
1210 Block = createBlock();
1212 appendStmt(Block, C);
1215 // Add exceptional edges.
1216 if (TryTerminatedBlock)
1217 addSuccessor(Block, TryTerminatedBlock);
1219 addSuccessor(Block, &cfg->getExit());
1222 return VisitChildren(C);
1225 CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C,
1226 AddStmtChoice asc) {
1227 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
1228 appendStmt(ConfluenceBlock, C);
1232 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);
1233 Succ = ConfluenceBlock;
1235 CFGBlock *LHSBlock = Visit(C->getLHS(), alwaysAdd);
1239 Succ = ConfluenceBlock;
1241 CFGBlock *RHSBlock = Visit(C->getRHS(), alwaysAdd);
1245 Block = createBlock(false);
1246 // See if this is a known constant.
1247 const TryResult& KnownVal = tryEvaluateBool(C->getCond());
1248 addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock);
1249 addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock);
1250 Block->setTerminator(C);
1251 return addStmt(C->getCond());
1255 CFGBlock *CFGBuilder::VisitCompoundStmt(CompoundStmt *C) {
1256 addLocalScopeAndDtors(C);
1257 CFGBlock *LastBlock = Block;
1259 for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend();
1261 // If we hit a segment of code just containing ';' (NullStmts), we can
1262 // get a null block back. In such cases, just use the LastBlock
1263 if (CFGBlock *newBlock = addStmt(*I))
1264 LastBlock = newBlock;
1273 CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C,
1274 AddStmtChoice asc) {
1275 const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(C);
1276 const OpaqueValueExpr *opaqueValue = (BCO ? BCO->getOpaqueValue() : NULL);
1278 // Create the confluence block that will "merge" the results of the ternary
1280 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
1281 appendStmt(ConfluenceBlock, C);
1285 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);
1287 // Create a block for the LHS expression if there is an LHS expression. A
1288 // GCC extension allows LHS to be NULL, causing the condition to be the
1289 // value that is returned instead.
1290 // e.g: x ?: y is shorthand for: x ? x : y;
1291 Succ = ConfluenceBlock;
1293 CFGBlock *LHSBlock = 0;
1294 const Expr *trueExpr = C->getTrueExpr();
1295 if (trueExpr != opaqueValue) {
1296 LHSBlock = Visit(C->getTrueExpr(), alwaysAdd);
1302 LHSBlock = ConfluenceBlock;
1304 // Create the block for the RHS expression.
1305 Succ = ConfluenceBlock;
1306 CFGBlock *RHSBlock = Visit(C->getFalseExpr(), alwaysAdd);
1310 // Create the block that will contain the condition.
1311 Block = createBlock(false);
1313 // See if this is a known constant.
1314 const TryResult& KnownVal = tryEvaluateBool(C->getCond());
1315 addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock);
1316 addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock);
1317 Block->setTerminator(C);
1318 Expr *condExpr = C->getCond();
1321 // Run the condition expression if it's not trivially expressed in
1322 // terms of the opaque value (or if there is no opaque value).
1323 if (condExpr != opaqueValue)
1326 // Before that, run the common subexpression if there was one.
1327 // At least one of this or the above will be run.
1328 return addStmt(BCO->getCommon());
1331 return addStmt(condExpr);
1334 CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) {
1335 // Check if the Decl is for an __label__. If so, elide it from the
1337 if (isa<LabelDecl>(*DS->decl_begin()))
1340 // This case also handles static_asserts.
1341 if (DS->isSingleDecl())
1342 return VisitDeclSubExpr(DS);
1346 // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy.
1347 typedef SmallVector<Decl*,10> BufTy;
1348 BufTy Buf(DS->decl_begin(), DS->decl_end());
1350 for (BufTy::reverse_iterator I = Buf.rbegin(), E = Buf.rend(); I != E; ++I) {
1351 // Get the alignment of the new DeclStmt, padding out to >=8 bytes.
1352 unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8
1353 ? 8 : llvm::AlignOf<DeclStmt>::Alignment;
1355 // Allocate the DeclStmt using the BumpPtrAllocator. It will get
1356 // automatically freed with the CFG.
1357 DeclGroupRef DG(*I);
1359 void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A);
1360 DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D));
1362 // Append the fake DeclStmt to block.
1363 B = VisitDeclSubExpr(DSNew);
1369 /// VisitDeclSubExpr - Utility method to add block-level expressions for
1370 /// DeclStmts and initializers in them.
1371 CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) {
1372 assert(DS->isSingleDecl() && "Can handle single declarations only.");
1373 Decl *D = DS->getSingleDecl();
1375 if (isa<StaticAssertDecl>(D)) {
1376 // static_asserts aren't added to the CFG because they do not impact
1377 // runtime semantics.
1381 VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl());
1385 appendStmt(Block, DS);
1389 bool IsReference = false;
1390 bool HasTemporaries = false;
1392 // Destructors of temporaries in initialization expression should be called
1393 // after initialization finishes.
1394 Expr *Init = VD->getInit();
1396 IsReference = VD->getType()->isReferenceType();
1397 HasTemporaries = isa<ExprWithCleanups>(Init);
1399 if (BuildOpts.AddImplicitDtors && HasTemporaries) {
1400 // Generate destructors for temporaries in initialization expression.
1401 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),
1407 appendStmt(Block, DS);
1411 // For expression with temporaries go directly to subexpression to omit
1412 // generating destructors for the second time.
1413 Visit(cast<ExprWithCleanups>(Init)->getSubExpr());
1418 // If the type of VD is a VLA, then we must process its size expressions.
1419 for (const VariableArrayType* VA = FindVA(VD->getType().getTypePtr());
1420 VA != 0; VA = FindVA(VA->getElementType().getTypePtr()))
1421 Block = addStmt(VA->getSizeExpr());
1423 // Remove variable from local scope.
1424 if (ScopePos && VD == *ScopePos)
1430 CFGBlock *CFGBuilder::VisitIfStmt(IfStmt *I) {
1431 // We may see an if statement in the middle of a basic block, or it may be the
1432 // first statement we are processing. In either case, we create a new basic
1433 // block. First, we create the blocks for the then...else statements, and
1434 // then we create the block containing the if statement. If we were in the
1435 // middle of a block, we stop processing that block. That block is then the
1436 // implicit successor for the "then" and "else" clauses.
1438 // Save local scope position because in case of condition variable ScopePos
1439 // won't be restored when traversing AST.
1440 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
1442 // Create local scope for possible condition variable.
1443 // Store scope position. Add implicit destructor.
1444 if (VarDecl *VD = I->getConditionVariable()) {
1445 LocalScope::const_iterator BeginScopePos = ScopePos;
1446 addLocalScopeForVarDecl(VD);
1447 addAutomaticObjDtors(ScopePos, BeginScopePos, I);
1450 // The block we were processing is now finished. Make it the successor
1458 // Process the false branch.
1459 CFGBlock *ElseBlock = Succ;
1461 if (Stmt *Else = I->getElse()) {
1462 SaveAndRestore<CFGBlock*> sv(Succ);
1464 // NULL out Block so that the recursive call to Visit will
1465 // create a new basic block.
1468 // If branch is not a compound statement create implicit scope
1469 // and add destructors.
1470 if (!isa<CompoundStmt>(Else))
1471 addLocalScopeAndDtors(Else);
1473 ElseBlock = addStmt(Else);
1475 if (!ElseBlock) // Can occur when the Else body has all NullStmts.
1476 ElseBlock = sv.get();
1483 // Process the true branch.
1484 CFGBlock *ThenBlock;
1486 Stmt *Then = I->getThen();
1488 SaveAndRestore<CFGBlock*> sv(Succ);
1491 // If branch is not a compound statement create implicit scope
1492 // and add destructors.
1493 if (!isa<CompoundStmt>(Then))
1494 addLocalScopeAndDtors(Then);
1496 ThenBlock = addStmt(Then);
1499 // We can reach here if the "then" body has all NullStmts.
1500 // Create an empty block so we can distinguish between true and false
1501 // branches in path-sensitive analyses.
1502 ThenBlock = createBlock(false);
1503 addSuccessor(ThenBlock, sv.get());
1510 // Now create a new block containing the if statement.
1511 Block = createBlock(false);
1513 // Set the terminator of the new block to the If statement.
1514 Block->setTerminator(I);
1516 // See if this is a known constant.
1517 const TryResult &KnownVal = tryEvaluateBool(I->getCond());
1519 // Now add the successors.
1520 addSuccessor(Block, KnownVal.isFalse() ? NULL : ThenBlock);
1521 addSuccessor(Block, KnownVal.isTrue()? NULL : ElseBlock);
1523 // Add the condition as the last statement in the new block. This may create
1524 // new blocks as the condition may contain control-flow. Any newly created
1525 // blocks will be pointed to be "Block".
1526 Block = addStmt(I->getCond());
1528 // Finally, if the IfStmt contains a condition variable, add both the IfStmt
1529 // and the condition variable initialization to the CFG.
1530 if (VarDecl *VD = I->getConditionVariable()) {
1531 if (Expr *Init = VD->getInit()) {
1533 appendStmt(Block, I->getConditionVariableDeclStmt());
1542 CFGBlock *CFGBuilder::VisitReturnStmt(ReturnStmt *R) {
1543 // If we were in the middle of a block we stop processing that block.
1545 // NOTE: If a "return" appears in the middle of a block, this means that the
1546 // code afterwards is DEAD (unreachable). We still keep a basic block
1547 // for that code; a simple "mark-and-sweep" from the entry block will be
1548 // able to report such dead blocks.
1550 // Create the new block.
1551 Block = createBlock(false);
1553 // The Exit block is the only successor.
1554 addAutomaticObjDtors(ScopePos, LocalScope::const_iterator(), R);
1555 addSuccessor(Block, &cfg->getExit());
1557 // Add the return statement to the block. This may create new blocks if R
1558 // contains control-flow (short-circuit operations).
1559 return VisitStmt(R, AddStmtChoice::AlwaysAdd);
1562 CFGBlock *CFGBuilder::VisitLabelStmt(LabelStmt *L) {
1563 // Get the block of the labeled statement. Add it to our map.
1564 addStmt(L->getSubStmt());
1565 CFGBlock *LabelBlock = Block;
1567 if (!LabelBlock) // This can happen when the body is empty, i.e.
1568 LabelBlock = createBlock(); // scopes that only contains NullStmts.
1570 assert(LabelMap.find(L->getDecl()) == LabelMap.end() &&
1571 "label already in map");
1572 LabelMap[L->getDecl()] = JumpTarget(LabelBlock, ScopePos);
1574 // Labels partition blocks, so this is the end of the basic block we were
1575 // processing (L is the block's label). Because this is label (and we have
1576 // already processed the substatement) there is no extra control-flow to worry
1578 LabelBlock->setLabel(L);
1582 // We set Block to NULL to allow lazy creation of a new block (if necessary);
1585 // This block is now the implicit successor of other blocks.
1591 CFGBlock *CFGBuilder::VisitGotoStmt(GotoStmt *G) {
1592 // Goto is a control-flow statement. Thus we stop processing the current
1593 // block and create a new one.
1595 Block = createBlock(false);
1596 Block->setTerminator(G);
1598 // If we already know the mapping to the label block add the successor now.
1599 LabelMapTy::iterator I = LabelMap.find(G->getLabel());
1601 if (I == LabelMap.end())
1602 // We will need to backpatch this block later.
1603 BackpatchBlocks.push_back(JumpSource(Block, ScopePos));
1605 JumpTarget JT = I->second;
1606 addAutomaticObjDtors(ScopePos, JT.scopePosition, G);
1607 addSuccessor(Block, JT.block);
1613 CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) {
1614 CFGBlock *LoopSuccessor = NULL;
1616 // Save local scope position because in case of condition variable ScopePos
1617 // won't be restored when traversing AST.
1618 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
1620 // Create local scope for init statement and possible condition variable.
1621 // Add destructor for init statement and condition variable.
1622 // Store scope position for continue statement.
1623 if (Stmt *Init = F->getInit())
1624 addLocalScopeForStmt(Init);
1625 LocalScope::const_iterator LoopBeginScopePos = ScopePos;
1627 if (VarDecl *VD = F->getConditionVariable())
1628 addLocalScopeForVarDecl(VD);
1629 LocalScope::const_iterator ContinueScopePos = ScopePos;
1631 addAutomaticObjDtors(ScopePos, save_scope_pos.get(), F);
1633 // "for" is a control-flow statement. Thus we stop processing the current
1638 LoopSuccessor = Block;
1640 LoopSuccessor = Succ;
1642 // Save the current value for the break targets.
1643 // All breaks should go to the code following the loop.
1644 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
1645 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
1647 // Because of short-circuit evaluation, the condition of the loop can span
1648 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
1649 // evaluate the condition.
1650 CFGBlock *ExitConditionBlock = createBlock(false);
1651 CFGBlock *EntryConditionBlock = ExitConditionBlock;
1653 // Set the terminator for the "exit" condition block.
1654 ExitConditionBlock->setTerminator(F);
1656 // Now add the actual condition to the condition block. Because the condition
1657 // itself may contain control-flow, new blocks may be created.
1658 if (Stmt *C = F->getCond()) {
1659 Block = ExitConditionBlock;
1660 EntryConditionBlock = addStmt(C);
1663 assert(Block == EntryConditionBlock ||
1664 (Block == 0 && EntryConditionBlock == Succ));
1666 // If this block contains a condition variable, add both the condition
1667 // variable and initializer to the CFG.
1668 if (VarDecl *VD = F->getConditionVariable()) {
1669 if (Expr *Init = VD->getInit()) {
1671 appendStmt(Block, F->getConditionVariableDeclStmt());
1672 EntryConditionBlock = addStmt(Init);
1673 assert(Block == EntryConditionBlock);
1683 // The condition block is the implicit successor for the loop body as well as
1684 // any code above the loop.
1685 Succ = EntryConditionBlock;
1687 // See if this is a known constant.
1688 TryResult KnownVal(true);
1691 KnownVal = tryEvaluateBool(F->getCond());
1693 // Now create the loop body.
1695 assert(F->getBody());
1697 // Save the current values for Block, Succ, and continue targets.
1698 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
1699 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget);
1701 // Create a new block to contain the (bottom) of the loop body.
1704 // Loop body should end with destructor of Condition variable (if any).
1705 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, F);
1707 if (Stmt *I = F->getInc()) {
1708 // Generate increment code in its own basic block. This is the target of
1709 // continue statements.
1712 // No increment code. Create a special, empty, block that is used as the
1713 // target block for "looping back" to the start of the loop.
1714 assert(Succ == EntryConditionBlock);
1715 Succ = Block ? Block : createBlock();
1718 // Finish up the increment (or empty) block if it hasn't been already.
1720 assert(Block == Succ);
1726 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
1728 // The starting block for the loop increment is the block that should
1729 // represent the 'loop target' for looping back to the start of the loop.
1730 ContinueJumpTarget.block->setLoopTarget(F);
1732 // If body is not a compound statement create implicit scope
1733 // and add destructors.
1734 if (!isa<CompoundStmt>(F->getBody()))
1735 addLocalScopeAndDtors(F->getBody());
1737 // Now populate the body block, and in the process create new blocks as we
1738 // walk the body of the loop.
1739 CFGBlock *BodyBlock = addStmt(F->getBody());
1742 BodyBlock = ContinueJumpTarget.block;//can happen for "for (...;...;...);"
1746 // This new body block is a successor to our "exit" condition block.
1747 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock);
1750 // Link up the condition block with the code that follows the loop. (the
1752 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor);
1754 // If the loop contains initialization, create a new block for those
1755 // statements. This block can also contain statements that precede the loop.
1756 if (Stmt *I = F->getInit()) {
1757 Block = createBlock();
1761 // There is no loop initialization. We are thus basically a while loop.
1762 // NULL out Block to force lazy block construction.
1764 Succ = EntryConditionBlock;
1765 return EntryConditionBlock;
1768 CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) {
1769 if (asc.alwaysAdd(*this, M)) {
1771 appendStmt(Block, M);
1773 return Visit(M->getBase());
1776 CFGBlock *CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt *S) {
1777 // Objective-C fast enumeration 'for' statements:
1778 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC
1780 // for ( Type newVariable in collection_expression ) { statements }
1785 // 1. collection_expression
1786 // T. jump to loop_entry
1788 // 1. side-effects of element expression
1789 // 1. ObjCForCollectionStmt [performs binding to newVariable]
1790 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil]
1793 // T. jump to loop_entry
1799 // Type existingItem;
1800 // for ( existingItem in expression ) { statements }
1804 // the same with newVariable replaced with existingItem; the binding works
1805 // the same except that for one ObjCForCollectionStmt::getElement() returns
1806 // a DeclStmt and the other returns a DeclRefExpr.
1809 CFGBlock *LoopSuccessor = 0;
1814 LoopSuccessor = Block;
1817 LoopSuccessor = Succ;
1819 // Build the condition blocks.
1820 CFGBlock *ExitConditionBlock = createBlock(false);
1822 // Set the terminator for the "exit" condition block.
1823 ExitConditionBlock->setTerminator(S);
1825 // The last statement in the block should be the ObjCForCollectionStmt, which
1826 // performs the actual binding to 'element' and determines if there are any
1827 // more items in the collection.
1828 appendStmt(ExitConditionBlock, S);
1829 Block = ExitConditionBlock;
1831 // Walk the 'element' expression to see if there are any side-effects. We
1832 // generate new blocks as necessary. We DON'T add the statement by default to
1833 // the CFG unless it contains control-flow.
1834 CFGBlock *EntryConditionBlock = Visit(S->getElement(),
1835 AddStmtChoice::NotAlwaysAdd);
1842 // The condition block is the implicit successor for the loop body as well as
1843 // any code above the loop.
1844 Succ = EntryConditionBlock;
1846 // Now create the true branch.
1848 // Save the current values for Succ, continue and break targets.
1849 SaveAndRestore<CFGBlock*> save_Succ(Succ);
1850 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
1851 save_break(BreakJumpTarget);
1853 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
1854 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos);
1856 CFGBlock *BodyBlock = addStmt(S->getBody());
1859 BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;"
1865 // This new body block is a successor to our "exit" condition block.
1866 addSuccessor(ExitConditionBlock, BodyBlock);
1869 // Link up the condition block with the code that follows the loop.
1870 // (the false branch).
1871 addSuccessor(ExitConditionBlock, LoopSuccessor);
1873 // Now create a prologue block to contain the collection expression.
1874 Block = createBlock();
1875 return addStmt(S->getCollection());
1878 CFGBlock *CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S) {
1879 // FIXME: Add locking 'primitives' to CFG for @synchronized.
1882 CFGBlock *SyncBlock = addStmt(S->getSynchBody());
1884 // The sync body starts its own basic block. This makes it a little easier
1885 // for diagnostic clients.
1894 // Add the @synchronized to the CFG.
1896 appendStmt(Block, S);
1898 // Inline the sync expression.
1899 return addStmt(S->getSynchExpr());
1902 CFGBlock *CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt *S) {
1907 CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) {
1908 CFGBlock *LoopSuccessor = NULL;
1910 // Save local scope position because in case of condition variable ScopePos
1911 // won't be restored when traversing AST.
1912 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
1914 // Create local scope for possible condition variable.
1915 // Store scope position for continue statement.
1916 LocalScope::const_iterator LoopBeginScopePos = ScopePos;
1917 if (VarDecl *VD = W->getConditionVariable()) {
1918 addLocalScopeForVarDecl(VD);
1919 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W);
1922 // "while" is a control-flow statement. Thus we stop processing the current
1927 LoopSuccessor = Block;
1930 LoopSuccessor = Succ;
1932 // Because of short-circuit evaluation, the condition of the loop can span
1933 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
1934 // evaluate the condition.
1935 CFGBlock *ExitConditionBlock = createBlock(false);
1936 CFGBlock *EntryConditionBlock = ExitConditionBlock;
1938 // Set the terminator for the "exit" condition block.
1939 ExitConditionBlock->setTerminator(W);
1941 // Now add the actual condition to the condition block. Because the condition
1942 // itself may contain control-flow, new blocks may be created. Thus we update
1943 // "Succ" after adding the condition.
1944 if (Stmt *C = W->getCond()) {
1945 Block = ExitConditionBlock;
1946 EntryConditionBlock = addStmt(C);
1947 // The condition might finish the current 'Block'.
1948 Block = EntryConditionBlock;
1950 // If this block contains a condition variable, add both the condition
1951 // variable and initializer to the CFG.
1952 if (VarDecl *VD = W->getConditionVariable()) {
1953 if (Expr *Init = VD->getInit()) {
1955 appendStmt(Block, W->getConditionVariableDeclStmt());
1956 EntryConditionBlock = addStmt(Init);
1957 assert(Block == EntryConditionBlock);
1967 // The condition block is the implicit successor for the loop body as well as
1968 // any code above the loop.
1969 Succ = EntryConditionBlock;
1971 // See if this is a known constant.
1972 const TryResult& KnownVal = tryEvaluateBool(W->getCond());
1974 // Process the loop body.
1976 assert(W->getBody());
1978 // Save the current values for Block, Succ, and continue and break targets
1979 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
1980 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
1981 save_break(BreakJumpTarget);
1983 // Create an empty block to represent the transition block for looping back
1984 // to the head of the loop.
1986 assert(Succ == EntryConditionBlock);
1987 Succ = createBlock();
1988 Succ->setLoopTarget(W);
1989 ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos);
1991 // All breaks should go to the code following the loop.
1992 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
1994 // NULL out Block to force lazy instantiation of blocks for the body.
1997 // Loop body should end with destructor of Condition variable (if any).
1998 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W);
2000 // If body is not a compound statement create implicit scope
2001 // and add destructors.
2002 if (!isa<CompoundStmt>(W->getBody()))
2003 addLocalScopeAndDtors(W->getBody());
2005 // Create the body. The returned block is the entry to the loop body.
2006 CFGBlock *BodyBlock = addStmt(W->getBody());
2009 BodyBlock = ContinueJumpTarget.block; // can happen for "while(...) ;"
2015 // Add the loop body entry as a successor to the condition.
2016 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock);
2019 // Link up the condition block with the code that follows the loop. (the
2021 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor);
2023 // There can be no more statements in the condition block since we loop back
2024 // to this block. NULL out Block to force lazy creation of another block.
2027 // Return the condition block, which is the dominating block for the loop.
2028 Succ = EntryConditionBlock;
2029 return EntryConditionBlock;
2033 CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt *S) {
2034 // FIXME: For now we pretend that @catch and the code it contains does not
2039 CFGBlock *CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt *S) {
2040 // FIXME: This isn't complete. We basically treat @throw like a return
2043 // If we were in the middle of a block we stop processing that block.
2047 // Create the new block.
2048 Block = createBlock(false);
2050 // The Exit block is the only successor.
2051 addSuccessor(Block, &cfg->getExit());
2053 // Add the statement to the block. This may create new blocks if S contains
2054 // control-flow (short-circuit operations).
2055 return VisitStmt(S, AddStmtChoice::AlwaysAdd);
2058 CFGBlock *CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr *T) {
2059 // If we were in the middle of a block we stop processing that block.
2063 // Create the new block.
2064 Block = createBlock(false);
2066 if (TryTerminatedBlock)
2067 // The current try statement is the only successor.
2068 addSuccessor(Block, TryTerminatedBlock);
2070 // otherwise the Exit block is the only successor.
2071 addSuccessor(Block, &cfg->getExit());
2073 // Add the statement to the block. This may create new blocks if S contains
2074 // control-flow (short-circuit operations).
2075 return VisitStmt(T, AddStmtChoice::AlwaysAdd);
2078 CFGBlock *CFGBuilder::VisitDoStmt(DoStmt *D) {
2079 CFGBlock *LoopSuccessor = NULL;
2081 // "do...while" is a control-flow statement. Thus we stop processing the
2086 LoopSuccessor = Block;
2088 LoopSuccessor = Succ;
2090 // Because of short-circuit evaluation, the condition of the loop can span
2091 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
2092 // evaluate the condition.
2093 CFGBlock *ExitConditionBlock = createBlock(false);
2094 CFGBlock *EntryConditionBlock = ExitConditionBlock;
2096 // Set the terminator for the "exit" condition block.
2097 ExitConditionBlock->setTerminator(D);
2099 // Now add the actual condition to the condition block. Because the condition
2100 // itself may contain control-flow, new blocks may be created.
2101 if (Stmt *C = D->getCond()) {
2102 Block = ExitConditionBlock;
2103 EntryConditionBlock = addStmt(C);
2110 // The condition block is the implicit successor for the loop body.
2111 Succ = EntryConditionBlock;
2113 // See if this is a known constant.
2114 const TryResult &KnownVal = tryEvaluateBool(D->getCond());
2116 // Process the loop body.
2117 CFGBlock *BodyBlock = NULL;
2119 assert(D->getBody());
2121 // Save the current values for Block, Succ, and continue and break targets
2122 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
2123 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
2124 save_break(BreakJumpTarget);
2126 // All continues within this loop should go to the condition block
2127 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos);
2129 // All breaks should go to the code following the loop.
2130 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
2132 // NULL out Block to force lazy instantiation of blocks for the body.
2135 // If body is not a compound statement create implicit scope
2136 // and add destructors.
2137 if (!isa<CompoundStmt>(D->getBody()))
2138 addLocalScopeAndDtors(D->getBody());
2140 // Create the body. The returned block is the entry to the loop body.
2141 BodyBlock = addStmt(D->getBody());
2144 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)"
2150 if (!KnownVal.isFalse()) {
2151 // Add an intermediate block between the BodyBlock and the
2152 // ExitConditionBlock to represent the "loop back" transition. Create an
2153 // empty block to represent the transition block for looping back to the
2154 // head of the loop.
2155 // FIXME: Can we do this more efficiently without adding another block?
2158 CFGBlock *LoopBackBlock = createBlock();
2159 LoopBackBlock->setLoopTarget(D);
2161 // Add the loop body entry as a successor to the condition.
2162 addSuccessor(ExitConditionBlock, LoopBackBlock);
2165 addSuccessor(ExitConditionBlock, NULL);
2168 // Link up the condition block with the code that follows the loop.
2169 // (the false branch).
2170 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor);
2172 // There can be no more statements in the body block(s) since we loop back to
2173 // the body. NULL out Block to force lazy creation of another block.
2176 // Return the loop body, which is the dominating block for the loop.
2181 CFGBlock *CFGBuilder::VisitContinueStmt(ContinueStmt *C) {
2182 // "continue" is a control-flow statement. Thus we stop processing the
2187 // Now create a new block that ends with the continue statement.
2188 Block = createBlock(false);
2189 Block->setTerminator(C);
2191 // If there is no target for the continue, then we are looking at an
2192 // incomplete AST. This means the CFG cannot be constructed.
2193 if (ContinueJumpTarget.block) {
2194 addAutomaticObjDtors(ScopePos, ContinueJumpTarget.scopePosition, C);
2195 addSuccessor(Block, ContinueJumpTarget.block);
2202 CFGBlock *CFGBuilder::VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
2203 AddStmtChoice asc) {
2205 if (asc.alwaysAdd(*this, E)) {
2207 appendStmt(Block, E);
2210 // VLA types have expressions that must be evaluated.
2211 CFGBlock *lastBlock = Block;
2213 if (E->isArgumentType()) {
2214 for (const VariableArrayType *VA =FindVA(E->getArgumentType().getTypePtr());
2215 VA != 0; VA = FindVA(VA->getElementType().getTypePtr()))
2216 lastBlock = addStmt(VA->getSizeExpr());
2221 /// VisitStmtExpr - Utility method to handle (nested) statement
2222 /// expressions (a GCC extension).
2223 CFGBlock *CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) {
2224 if (asc.alwaysAdd(*this, SE)) {
2226 appendStmt(Block, SE);
2228 return VisitCompoundStmt(SE->getSubStmt());
2231 CFGBlock *CFGBuilder::VisitSwitchStmt(SwitchStmt *Terminator) {
2232 // "switch" is a control-flow statement. Thus we stop processing the current
2234 CFGBlock *SwitchSuccessor = NULL;
2236 // Save local scope position because in case of condition variable ScopePos
2237 // won't be restored when traversing AST.
2238 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2240 // Create local scope for possible condition variable.
2241 // Store scope position. Add implicit destructor.
2242 if (VarDecl *VD = Terminator->getConditionVariable()) {
2243 LocalScope::const_iterator SwitchBeginScopePos = ScopePos;
2244 addLocalScopeForVarDecl(VD);
2245 addAutomaticObjDtors(ScopePos, SwitchBeginScopePos, Terminator);
2251 SwitchSuccessor = Block;
2252 } else SwitchSuccessor = Succ;
2254 // Save the current "switch" context.
2255 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock),
2256 save_default(DefaultCaseBlock);
2257 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
2259 // Set the "default" case to be the block after the switch statement. If the
2260 // switch statement contains a "default:", this value will be overwritten with
2261 // the block for that code.
2262 DefaultCaseBlock = SwitchSuccessor;
2264 // Create a new block that will contain the switch statement.
2265 SwitchTerminatedBlock = createBlock(false);
2267 // Now process the switch body. The code after the switch is the implicit
2269 Succ = SwitchSuccessor;
2270 BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos);
2272 // When visiting the body, the case statements should automatically get linked
2273 // up to the switch. We also don't keep a pointer to the body, since all
2274 // control-flow from the switch goes to case/default statements.
2275 assert(Terminator->getBody() && "switch must contain a non-NULL body");
2278 // For pruning unreachable case statements, save the current state
2279 // for tracking the condition value.
2280 SaveAndRestore<bool> save_switchExclusivelyCovered(switchExclusivelyCovered,
2283 // Determine if the switch condition can be explicitly evaluated.
2284 assert(Terminator->getCond() && "switch condition must be non-NULL");
2285 Expr::EvalResult result;
2286 bool b = tryEvaluate(Terminator->getCond(), result);
2287 SaveAndRestore<Expr::EvalResult*> save_switchCond(switchCond,
2290 // If body is not a compound statement create implicit scope
2291 // and add destructors.
2292 if (!isa<CompoundStmt>(Terminator->getBody()))
2293 addLocalScopeAndDtors(Terminator->getBody());
2295 addStmt(Terminator->getBody());
2301 // If we have no "default:" case, the default transition is to the code
2302 // following the switch body. Moreover, take into account if all the
2303 // cases of a switch are covered (e.g., switching on an enum value).
2304 addSuccessor(SwitchTerminatedBlock,
2305 switchExclusivelyCovered || Terminator->isAllEnumCasesCovered()
2306 ? 0 : DefaultCaseBlock);
2308 // Add the terminator and condition in the switch block.
2309 SwitchTerminatedBlock->setTerminator(Terminator);
2310 Block = SwitchTerminatedBlock;
2311 Block = addStmt(Terminator->getCond());
2313 // Finally, if the SwitchStmt contains a condition variable, add both the
2314 // SwitchStmt and the condition variable initialization to the CFG.
2315 if (VarDecl *VD = Terminator->getConditionVariable()) {
2316 if (Expr *Init = VD->getInit()) {
2318 appendStmt(Block, Terminator->getConditionVariableDeclStmt());
2326 static bool shouldAddCase(bool &switchExclusivelyCovered,
2327 const Expr::EvalResult *switchCond,
2333 bool addCase = false;
2335 if (!switchExclusivelyCovered) {
2336 if (switchCond->Val.isInt()) {
2337 // Evaluate the LHS of the case value.
2338 const llvm::APSInt &lhsInt = CS->getLHS()->EvaluateKnownConstInt(Ctx);
2339 const llvm::APSInt &condInt = switchCond->Val.getInt();
2341 if (condInt == lhsInt) {
2343 switchExclusivelyCovered = true;
2345 else if (condInt < lhsInt) {
2346 if (const Expr *RHS = CS->getRHS()) {
2347 // Evaluate the RHS of the case value.
2348 const llvm::APSInt &V2 = RHS->EvaluateKnownConstInt(Ctx);
2349 if (V2 <= condInt) {
2351 switchExclusivelyCovered = true;
2362 CFGBlock *CFGBuilder::VisitCaseStmt(CaseStmt *CS) {
2363 // CaseStmts are essentially labels, so they are the first statement in a
2365 CFGBlock *TopBlock = 0, *LastBlock = 0;
2367 if (Stmt *Sub = CS->getSubStmt()) {
2368 // For deeply nested chains of CaseStmts, instead of doing a recursion
2369 // (which can blow out the stack), manually unroll and create blocks
2371 while (isa<CaseStmt>(Sub)) {
2372 CFGBlock *currentBlock = createBlock(false);
2373 currentBlock->setLabel(CS);
2376 addSuccessor(LastBlock, currentBlock);
2378 TopBlock = currentBlock;
2380 addSuccessor(SwitchTerminatedBlock,
2381 shouldAddCase(switchExclusivelyCovered, switchCond,
2383 ? currentBlock : 0);
2385 LastBlock = currentBlock;
2386 CS = cast<CaseStmt>(Sub);
2387 Sub = CS->getSubStmt();
2393 CFGBlock *CaseBlock = Block;
2395 CaseBlock = createBlock();
2397 // Cases statements partition blocks, so this is the top of the basic block we
2398 // were processing (the "case XXX:" is the label).
2399 CaseBlock->setLabel(CS);
2404 // Add this block to the list of successors for the block with the switch
2406 assert(SwitchTerminatedBlock);
2407 addSuccessor(SwitchTerminatedBlock,
2408 shouldAddCase(switchExclusivelyCovered, switchCond,
2412 // We set Block to NULL to allow lazy creation of a new block (if necessary)
2416 addSuccessor(LastBlock, CaseBlock);
2419 // This block is now the implicit successor of other blocks.
2426 CFGBlock *CFGBuilder::VisitDefaultStmt(DefaultStmt *Terminator) {
2427 if (Terminator->getSubStmt())
2428 addStmt(Terminator->getSubStmt());
2430 DefaultCaseBlock = Block;
2432 if (!DefaultCaseBlock)
2433 DefaultCaseBlock = createBlock();
2435 // Default statements partition blocks, so this is the top of the basic block
2436 // we were processing (the "default:" is the label).
2437 DefaultCaseBlock->setLabel(Terminator);
2442 // Unlike case statements, we don't add the default block to the successors
2443 // for the switch statement immediately. This is done when we finish
2444 // processing the switch statement. This allows for the default case
2445 // (including a fall-through to the code after the switch statement) to always
2446 // be the last successor of a switch-terminated block.
2448 // We set Block to NULL to allow lazy creation of a new block (if necessary)
2451 // This block is now the implicit successor of other blocks.
2452 Succ = DefaultCaseBlock;
2454 return DefaultCaseBlock;
2457 CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) {
2458 // "try"/"catch" is a control-flow statement. Thus we stop processing the
2460 CFGBlock *TrySuccessor = NULL;
2465 TrySuccessor = Block;
2466 } else TrySuccessor = Succ;
2468 CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock;
2470 // Create a new block that will contain the try statement.
2471 CFGBlock *NewTryTerminatedBlock = createBlock(false);
2472 // Add the terminator in the try block.
2473 NewTryTerminatedBlock->setTerminator(Terminator);
2475 bool HasCatchAll = false;
2476 for (unsigned h = 0; h <Terminator->getNumHandlers(); ++h) {
2477 // The code after the try is the implicit successor.
2478 Succ = TrySuccessor;
2479 CXXCatchStmt *CS = Terminator->getHandler(h);
2480 if (CS->getExceptionDecl() == 0) {
2484 CFGBlock *CatchBlock = VisitCXXCatchStmt(CS);
2485 if (CatchBlock == 0)
2487 // Add this block to the list of successors for the block with the try
2489 addSuccessor(NewTryTerminatedBlock, CatchBlock);
2492 if (PrevTryTerminatedBlock)
2493 addSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock);
2495 addSuccessor(NewTryTerminatedBlock, &cfg->getExit());
2498 // The code after the try is the implicit successor.
2499 Succ = TrySuccessor;
2501 // Save the current "try" context.
2502 SaveAndRestore<CFGBlock*> save_try(TryTerminatedBlock, NewTryTerminatedBlock);
2503 cfg->addTryDispatchBlock(TryTerminatedBlock);
2505 assert(Terminator->getTryBlock() && "try must contain a non-NULL body");
2507 Block = addStmt(Terminator->getTryBlock());
2511 CFGBlock *CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt *CS) {
2512 // CXXCatchStmt are treated like labels, so they are the first statement in a
2515 // Save local scope position because in case of exception variable ScopePos
2516 // won't be restored when traversing AST.
2517 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2519 // Create local scope for possible exception variable.
2520 // Store scope position. Add implicit destructor.
2521 if (VarDecl *VD = CS->getExceptionDecl()) {
2522 LocalScope::const_iterator BeginScopePos = ScopePos;
2523 addLocalScopeForVarDecl(VD);
2524 addAutomaticObjDtors(ScopePos, BeginScopePos, CS);
2527 if (CS->getHandlerBlock())
2528 addStmt(CS->getHandlerBlock());
2530 CFGBlock *CatchBlock = Block;
2532 CatchBlock = createBlock();
2534 CatchBlock->setLabel(CS);
2539 // We set Block to NULL to allow lazy creation of a new block (if necessary)
2545 CFGBlock *CFGBuilder::VisitCXXForRangeStmt(CXXForRangeStmt *S) {
2546 // C++0x for-range statements are specified as [stmt.ranged]:
2549 // auto && __range = range-init;
2550 // for ( auto __begin = begin-expr,
2551 // __end = end-expr;
2552 // __begin != __end;
2554 // for-range-declaration = *__begin;
2559 // Save local scope position before the addition of the implicit variables.
2560 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2562 // Create local scopes and destructors for range, begin and end variables.
2563 if (Stmt *Range = S->getRangeStmt())
2564 addLocalScopeForStmt(Range);
2565 if (Stmt *BeginEnd = S->getBeginEndStmt())
2566 addLocalScopeForStmt(BeginEnd);
2567 addAutomaticObjDtors(ScopePos, save_scope_pos.get(), S);
2569 LocalScope::const_iterator ContinueScopePos = ScopePos;
2571 // "for" is a control-flow statement. Thus we stop processing the current
2573 CFGBlock *LoopSuccessor = NULL;
2577 LoopSuccessor = Block;
2579 LoopSuccessor = Succ;
2581 // Save the current value for the break targets.
2582 // All breaks should go to the code following the loop.
2583 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
2584 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
2586 // The block for the __begin != __end expression.
2587 CFGBlock *ConditionBlock = createBlock(false);
2588 ConditionBlock->setTerminator(S);
2590 // Now add the actual condition to the condition block.
2591 if (Expr *C = S->getCond()) {
2592 Block = ConditionBlock;
2593 CFGBlock *BeginConditionBlock = addStmt(C);
2596 assert(BeginConditionBlock == ConditionBlock &&
2597 "condition block in for-range was unexpectedly complex");
2598 (void)BeginConditionBlock;
2601 // The condition block is the implicit successor for the loop body as well as
2602 // any code above the loop.
2603 Succ = ConditionBlock;
2605 // See if this is a known constant.
2606 TryResult KnownVal(true);
2609 KnownVal = tryEvaluateBool(S->getCond());
2611 // Now create the loop body.
2613 assert(S->getBody());
2615 // Save the current values for Block, Succ, and continue targets.
2616 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
2617 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget);
2619 // Generate increment code in its own basic block. This is the target of
2620 // continue statements.
2622 Succ = addStmt(S->getInc());
2623 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
2625 // The starting block for the loop increment is the block that should
2626 // represent the 'loop target' for looping back to the start of the loop.
2627 ContinueJumpTarget.block->setLoopTarget(S);
2629 // Finish up the increment block and prepare to start the loop body.
2636 // Add implicit scope and dtors for loop variable.
2637 addLocalScopeAndDtors(S->getLoopVarStmt());
2639 // Populate a new block to contain the loop body and loop variable.
2640 Block = addStmt(S->getBody());
2643 Block = addStmt(S->getLoopVarStmt());
2647 // This new body block is a successor to our condition block.
2648 addSuccessor(ConditionBlock, KnownVal.isFalse() ? 0 : Block);
2651 // Link up the condition block with the code that follows the loop (the
2653 addSuccessor(ConditionBlock, KnownVal.isTrue() ? 0 : LoopSuccessor);
2655 // Add the initialization statements.
2656 Block = createBlock();
2657 addStmt(S->getBeginEndStmt());
2658 return addStmt(S->getRangeStmt());
2661 CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E,
2662 AddStmtChoice asc) {
2663 if (BuildOpts.AddImplicitDtors) {
2664 // If adding implicit destructors visit the full expression for adding
2665 // destructors of temporaries.
2666 VisitForTemporaryDtors(E->getSubExpr());
2668 // Full expression has to be added as CFGStmt so it will be sequenced
2669 // before destructors of it's temporaries.
2670 asc = asc.withAlwaysAdd(true);
2672 return Visit(E->getSubExpr(), asc);
2675 CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
2676 AddStmtChoice asc) {
2677 if (asc.alwaysAdd(*this, E)) {
2679 appendStmt(Block, E);
2681 // We do not want to propagate the AlwaysAdd property.
2682 asc = asc.withAlwaysAdd(false);
2684 return Visit(E->getSubExpr(), asc);
2687 CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C,
2688 AddStmtChoice asc) {
2690 if (!C->isElidable())
2691 appendStmt(Block, C);
2693 return VisitChildren(C);
2696 CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
2697 AddStmtChoice asc) {
2698 if (asc.alwaysAdd(*this, E)) {
2700 appendStmt(Block, E);
2701 // We do not want to propagate the AlwaysAdd property.
2702 asc = asc.withAlwaysAdd(false);
2704 return Visit(E->getSubExpr(), asc);
2707 CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C,
2708 AddStmtChoice asc) {
2710 appendStmt(Block, C);
2711 return VisitChildren(C);
2714 CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E,
2715 AddStmtChoice asc) {
2716 if (asc.alwaysAdd(*this, E)) {
2718 appendStmt(Block, E);
2720 return Visit(E->getSubExpr(), AddStmtChoice());
2723 CFGBlock *CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt *I) {
2724 // Lazily create the indirect-goto dispatch block if there isn't one already.
2725 CFGBlock *IBlock = cfg->getIndirectGotoBlock();
2728 IBlock = createBlock(false);
2729 cfg->setIndirectGotoBlock(IBlock);
2732 // IndirectGoto is a control-flow statement. Thus we stop processing the
2733 // current block and create a new one.
2737 Block = createBlock(false);
2738 Block->setTerminator(I);
2739 addSuccessor(Block, IBlock);
2740 return addStmt(I->getTarget());
2743 CFGBlock *CFGBuilder::VisitForTemporaryDtors(Stmt *E, bool BindToTemporary) {
2749 switch (E->getStmtClass()) {
2751 return VisitChildrenForTemporaryDtors(E);
2753 case Stmt::BinaryOperatorClass:
2754 return VisitBinaryOperatorForTemporaryDtors(cast<BinaryOperator>(E));
2756 case Stmt::CXXBindTemporaryExprClass:
2757 return VisitCXXBindTemporaryExprForTemporaryDtors(
2758 cast<CXXBindTemporaryExpr>(E), BindToTemporary);
2760 case Stmt::BinaryConditionalOperatorClass:
2761 case Stmt::ConditionalOperatorClass:
2762 return VisitConditionalOperatorForTemporaryDtors(
2763 cast<AbstractConditionalOperator>(E), BindToTemporary);
2765 case Stmt::ImplicitCastExprClass:
2766 // For implicit cast we want BindToTemporary to be passed further.
2767 E = cast<CastExpr>(E)->getSubExpr();
2770 case Stmt::ParenExprClass:
2771 E = cast<ParenExpr>(E)->getSubExpr();
2774 case Stmt::MaterializeTemporaryExprClass:
2775 E = cast<MaterializeTemporaryExpr>(E)->GetTemporaryExpr();
2780 CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E) {
2781 // When visiting children for destructors we want to visit them in reverse
2782 // order. Because there's no reverse iterator for children must to reverse
2783 // them in helper vector.
2784 typedef SmallVector<Stmt *, 4> ChildrenVect;
2785 ChildrenVect ChildrenRev;
2786 for (Stmt::child_range I = E->children(); I; ++I) {
2787 if (*I) ChildrenRev.push_back(*I);
2790 CFGBlock *B = Block;
2791 for (ChildrenVect::reverse_iterator I = ChildrenRev.rbegin(),
2792 L = ChildrenRev.rend(); I != L; ++I) {
2793 if (CFGBlock *R = VisitForTemporaryDtors(*I))
2799 CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E) {
2800 if (E->isLogicalOp()) {
2801 // Destructors for temporaries in LHS expression should be called after
2802 // those for RHS expression. Even if this will unnecessarily create a block,
2803 // this block will be used at least by the full expression.
2805 CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getLHS());
2809 Succ = ConfluenceBlock;
2811 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS());
2817 // If RHS expression did produce destructors we need to connect created
2818 // blocks to CFG in same manner as for binary operator itself.
2819 CFGBlock *LHSBlock = createBlock(false);
2820 LHSBlock->setTerminator(CFGTerminator(E, true));
2822 // For binary operator LHS block is before RHS in list of predecessors
2823 // of ConfluenceBlock.
2824 std::reverse(ConfluenceBlock->pred_begin(),
2825 ConfluenceBlock->pred_end());
2827 // See if this is a known constant.
2828 TryResult KnownVal = tryEvaluateBool(E->getLHS());
2829 if (KnownVal.isKnown() && (E->getOpcode() == BO_LOr))
2832 // Link LHSBlock with RHSBlock exactly the same way as for binary operator
2834 if (E->getOpcode() == BO_LOr) {
2835 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock);
2836 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock);
2838 assert (E->getOpcode() == BO_LAnd);
2839 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock);
2840 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock);
2847 Block = ConfluenceBlock;
2848 return ConfluenceBlock;
2851 if (E->isAssignmentOp()) {
2852 // For assignment operator (=) LHS expression is visited
2853 // before RHS expression. For destructors visit them in reverse order.
2854 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS());
2855 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS());
2856 return LHSBlock ? LHSBlock : RHSBlock;
2859 // For any other binary operator RHS expression is visited before
2860 // LHS expression (order of children). For destructors visit them in reverse
2862 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS());
2863 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS());
2864 return RHSBlock ? RHSBlock : LHSBlock;
2867 CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors(
2868 CXXBindTemporaryExpr *E, bool BindToTemporary) {
2869 // First add destructors for temporaries in subexpression.
2870 CFGBlock *B = VisitForTemporaryDtors(E->getSubExpr());
2871 if (!BindToTemporary) {
2872 // If lifetime of temporary is not prolonged (by assigning to constant
2873 // reference) add destructor for it.
2875 // If the destructor is marked as a no-return destructor, we need to create
2876 // a new block for the destructor which does not have as a successor
2877 // anything built thus far. Control won't flow out of this block.
2878 const CXXDestructorDecl *Dtor = E->getTemporary()->getDestructor();
2879 if (cast<FunctionType>(Dtor->getType())->getNoReturnAttr())
2880 Block = createNoReturnBlock();
2884 appendTemporaryDtor(Block, E);
2890 CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors(
2891 AbstractConditionalOperator *E, bool BindToTemporary) {
2892 // First add destructors for condition expression. Even if this will
2893 // unnecessarily create a block, this block will be used at least by the full
2896 CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getCond());
2899 if (BinaryConditionalOperator *BCO
2900 = dyn_cast<BinaryConditionalOperator>(E)) {
2901 ConfluenceBlock = VisitForTemporaryDtors(BCO->getCommon());
2906 // Try to add block with destructors for LHS expression.
2907 CFGBlock *LHSBlock = NULL;
2908 Succ = ConfluenceBlock;
2910 LHSBlock = VisitForTemporaryDtors(E->getTrueExpr(), BindToTemporary);
2914 // Try to add block with destructors for RHS expression;
2915 Succ = ConfluenceBlock;
2917 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getFalseExpr(),
2922 if (!RHSBlock && !LHSBlock) {
2923 // If neither LHS nor RHS expression had temporaries to destroy don't create
2925 Block = ConfluenceBlock;
2929 Block = createBlock(false);
2930 Block->setTerminator(CFGTerminator(E, true));
2932 // See if this is a known constant.
2933 const TryResult &KnownVal = tryEvaluateBool(E->getCond());
2936 addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock);
2937 } else if (KnownVal.isFalse()) {
2938 addSuccessor(Block, NULL);
2940 addSuccessor(Block, ConfluenceBlock);
2941 std::reverse(ConfluenceBlock->pred_begin(), ConfluenceBlock->pred_end());
2945 RHSBlock = ConfluenceBlock;
2946 addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock);
2951 } // end anonymous namespace
2953 /// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has
2954 /// no successors or predecessors. If this is the first block created in the
2955 /// CFG, it is automatically set to be the Entry and Exit of the CFG.
2956 CFGBlock *CFG::createBlock() {
2957 bool first_block = begin() == end();
2959 // Create the block.
2960 CFGBlock *Mem = getAllocator().Allocate<CFGBlock>();
2961 new (Mem) CFGBlock(NumBlockIDs++, BlkBVC);
2962 Blocks.push_back(Mem, BlkBVC);
2964 // If this is the first block, set it as the Entry and Exit.
2966 Entry = Exit = &back();
2968 // Return the block.
2972 /// buildCFG - Constructs a CFG from an AST. Ownership of the returned
2973 /// CFG is returned to the caller.
2974 CFG* CFG::buildCFG(const Decl *D, Stmt *Statement, ASTContext *C,
2975 const BuildOptions &BO) {
2976 CFGBuilder Builder(C, BO);
2977 return Builder.buildCFG(D, Statement);
2980 const CXXDestructorDecl *
2981 CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const {
2982 switch (getKind()) {
2983 case CFGElement::Invalid:
2984 case CFGElement::Statement:
2985 case CFGElement::Initializer:
2986 llvm_unreachable("getDestructorDecl should only be used with "
2988 case CFGElement::AutomaticObjectDtor: {
2989 const VarDecl *var = cast<CFGAutomaticObjDtor>(this)->getVarDecl();
2990 QualType ty = var->getType();
2991 ty = ty.getNonReferenceType();
2992 if (const ArrayType *arrayType = astContext.getAsArrayType(ty)) {
2993 ty = arrayType->getElementType();
2995 const RecordType *recordType = ty->getAs<RecordType>();
2996 const CXXRecordDecl *classDecl =
2997 cast<CXXRecordDecl>(recordType->getDecl());
2998 return classDecl->getDestructor();
3000 case CFGElement::TemporaryDtor: {
3001 const CXXBindTemporaryExpr *bindExpr =
3002 cast<CFGTemporaryDtor>(this)->getBindTemporaryExpr();
3003 const CXXTemporary *temp = bindExpr->getTemporary();
3004 return temp->getDestructor();
3006 case CFGElement::BaseDtor:
3007 case CFGElement::MemberDtor:
3009 // Not yet supported.
3012 llvm_unreachable("getKind() returned bogus value");
3016 bool CFGImplicitDtor::isNoReturn(ASTContext &astContext) const {
3017 if (const CXXDestructorDecl *cdecl = getDestructorDecl(astContext)) {
3018 QualType ty = cdecl->getType();
3019 return cast<FunctionType>(ty)->getNoReturnAttr();
3024 //===----------------------------------------------------------------------===//
3025 // CFG: Queries for BlkExprs.
3026 //===----------------------------------------------------------------------===//
3029 typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy;
3032 static void FindSubExprAssignments(const Stmt *S,
3033 llvm::SmallPtrSet<const Expr*,50>& Set) {
3037 for (Stmt::const_child_range I = S->children(); I; ++I) {
3038 const Stmt *child = *I;
3042 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(child))
3043 if (B->isAssignmentOp()) Set.insert(B);
3045 FindSubExprAssignments(child, Set);
3049 static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) {
3050 BlkExprMapTy* M = new BlkExprMapTy();
3052 // Look for assignments that are used as subexpressions. These are the only
3053 // assignments that we want to *possibly* register as a block-level
3054 // expression. Basically, if an assignment occurs both in a subexpression and
3055 // at the block-level, it is a block-level expression.
3056 llvm::SmallPtrSet<const Expr*,50> SubExprAssignments;
3058 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I)
3059 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI)
3060 if (const CFGStmt *S = BI->getAs<CFGStmt>())
3061 FindSubExprAssignments(S->getStmt(), SubExprAssignments);
3063 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) {
3065 // Iterate over the statements again on identify the Expr* and Stmt* at the
3066 // block-level that are block-level expressions.
3068 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) {
3069 const CFGStmt *CS = BI->getAs<CFGStmt>();
3072 if (const Expr *Exp = dyn_cast<Expr>(CS->getStmt())) {
3073 assert((Exp->IgnoreParens() == Exp) && "No parens on block-level exps");
3075 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) {
3076 // Assignment expressions that are not nested within another
3077 // expression are really "statements" whose value is never used by
3078 // another expression.
3079 if (B->isAssignmentOp() && !SubExprAssignments.count(Exp))
3081 } else if (const StmtExpr *SE = dyn_cast<StmtExpr>(Exp)) {
3082 // Special handling for statement expressions. The last statement in
3083 // the statement expression is also a block-level expr.
3084 const CompoundStmt *C = SE->getSubStmt();
3085 if (!C->body_empty()) {
3086 const Stmt *Last = C->body_back();
3087 if (const Expr *LastEx = dyn_cast<Expr>(Last))
3088 Last = LastEx->IgnoreParens();
3089 unsigned x = M->size();
3094 unsigned x = M->size();
3099 // Look at terminators. The condition is a block-level expression.
3101 Stmt *S = (*I)->getTerminatorCondition();
3103 if (S && M->find(S) == M->end()) {
3104 unsigned x = M->size();
3112 CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt *S) {
3114 if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); }
3116 BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap);
3117 BlkExprMapTy::iterator I = M->find(S);
3118 return (I == M->end()) ? CFG::BlkExprNumTy() : CFG::BlkExprNumTy(I->second);
3121 unsigned CFG::getNumBlkExprs() {
3122 if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap))
3125 // We assume callers interested in the number of BlkExprs will want
3126 // the map constructed if it doesn't already exist.
3127 BlkExprMap = (void*) PopulateBlkExprMap(*this);
3128 return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size();
3131 //===----------------------------------------------------------------------===//
3132 // Filtered walking of the CFG.
3133 //===----------------------------------------------------------------------===//
3135 bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F,
3136 const CFGBlock *From, const CFGBlock *To) {
3138 if (To && F.IgnoreDefaultsWithCoveredEnums) {
3139 // If the 'To' has no label or is labeled but the label isn't a
3140 // CaseStmt then filter this edge.
3141 if (const SwitchStmt *S =
3142 dyn_cast_or_null<SwitchStmt>(From->getTerminator().getStmt())) {
3143 if (S->isAllEnumCasesCovered()) {
3144 const Stmt *L = To->getLabel();
3145 if (!L || !isa<CaseStmt>(L))
3154 //===----------------------------------------------------------------------===//
3155 // Cleanup: CFG dstor.
3156 //===----------------------------------------------------------------------===//
3159 delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap);
3162 //===----------------------------------------------------------------------===//
3163 // CFG pretty printing
3164 //===----------------------------------------------------------------------===//
3168 class StmtPrinterHelper : public PrinterHelper {
3169 typedef llvm::DenseMap<const Stmt*,std::pair<unsigned,unsigned> > StmtMapTy;
3170 typedef llvm::DenseMap<const Decl*,std::pair<unsigned,unsigned> > DeclMapTy;
3173 signed currentBlock;
3174 unsigned currentStmt;
3175 const LangOptions &LangOpts;
3178 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO)
3179 : currentBlock(0), currentStmt(0), LangOpts(LO)
3181 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) {
3183 for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ;
3184 BI != BEnd; ++BI, ++j ) {
3185 if (const CFGStmt *SE = BI->getAs<CFGStmt>()) {
3186 const Stmt *stmt= SE->getStmt();
3187 std::pair<unsigned, unsigned> P((*I)->getBlockID(), j);
3190 switch (stmt->getStmtClass()) {
3191 case Stmt::DeclStmtClass:
3192 DeclMap[cast<DeclStmt>(stmt)->getSingleDecl()] = P;
3194 case Stmt::IfStmtClass: {
3195 const VarDecl *var = cast<IfStmt>(stmt)->getConditionVariable();
3200 case Stmt::ForStmtClass: {
3201 const VarDecl *var = cast<ForStmt>(stmt)->getConditionVariable();
3206 case Stmt::WhileStmtClass: {
3207 const VarDecl *var =
3208 cast<WhileStmt>(stmt)->getConditionVariable();
3213 case Stmt::SwitchStmtClass: {
3214 const VarDecl *var =
3215 cast<SwitchStmt>(stmt)->getConditionVariable();
3220 case Stmt::CXXCatchStmtClass: {
3221 const VarDecl *var =
3222 cast<CXXCatchStmt>(stmt)->getExceptionDecl();
3236 virtual ~StmtPrinterHelper() {}
3238 const LangOptions &getLangOpts() const { return LangOpts; }
3239 void setBlockID(signed i) { currentBlock = i; }
3240 void setStmtID(unsigned i) { currentStmt = i; }
3242 virtual bool handledStmt(Stmt *S, raw_ostream &OS) {
3243 StmtMapTy::iterator I = StmtMap.find(S);
3245 if (I == StmtMap.end())
3248 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
3249 && I->second.second == currentStmt) {
3253 OS << "[B" << I->second.first << "." << I->second.second << "]";
3257 bool handleDecl(const Decl *D, raw_ostream &OS) {
3258 DeclMapTy::iterator I = DeclMap.find(D);
3260 if (I == DeclMap.end())
3263 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
3264 && I->second.second == currentStmt) {
3268 OS << "[B" << I->second.first << "." << I->second.second << "]";
3272 } // end anonymous namespace
3276 class CFGBlockTerminatorPrint
3277 : public StmtVisitor<CFGBlockTerminatorPrint,void> {
3280 StmtPrinterHelper* Helper;
3281 PrintingPolicy Policy;
3283 CFGBlockTerminatorPrint(raw_ostream &os, StmtPrinterHelper* helper,
3284 const PrintingPolicy &Policy)
3285 : OS(os), Helper(helper), Policy(Policy) {}
3287 void VisitIfStmt(IfStmt *I) {
3289 I->getCond()->printPretty(OS,Helper,Policy);
3293 void VisitStmt(Stmt *Terminator) {
3294 Terminator->printPretty(OS, Helper, Policy);
3297 void VisitForStmt(ForStmt *F) {
3302 if (Stmt *C = F->getCond())
3303 C->printPretty(OS, Helper, Policy);
3310 void VisitWhileStmt(WhileStmt *W) {
3312 if (Stmt *C = W->getCond())
3313 C->printPretty(OS, Helper, Policy);
3316 void VisitDoStmt(DoStmt *D) {
3317 OS << "do ... while ";
3318 if (Stmt *C = D->getCond())
3319 C->printPretty(OS, Helper, Policy);
3322 void VisitSwitchStmt(SwitchStmt *Terminator) {
3324 Terminator->getCond()->printPretty(OS, Helper, Policy);
3327 void VisitCXXTryStmt(CXXTryStmt *CS) {
3331 void VisitAbstractConditionalOperator(AbstractConditionalOperator* C) {
3332 C->getCond()->printPretty(OS, Helper, Policy);
3333 OS << " ? ... : ...";
3336 void VisitChooseExpr(ChooseExpr *C) {
3337 OS << "__builtin_choose_expr( ";
3338 C->getCond()->printPretty(OS, Helper, Policy);
3342 void VisitIndirectGotoStmt(IndirectGotoStmt *I) {
3344 I->getTarget()->printPretty(OS, Helper, Policy);
3347 void VisitBinaryOperator(BinaryOperator* B) {
3348 if (!B->isLogicalOp()) {
3353 B->getLHS()->printPretty(OS, Helper, Policy);
3355 switch (B->getOpcode()) {
3363 llvm_unreachable("Invalid logical operator.");
3367 void VisitExpr(Expr *E) {
3368 E->printPretty(OS, Helper, Policy);
3371 } // end anonymous namespace
3373 static void print_elem(raw_ostream &OS, StmtPrinterHelper* Helper,
3374 const CFGElement &E) {
3375 if (const CFGStmt *CS = E.getAs<CFGStmt>()) {
3376 const Stmt *S = CS->getStmt();
3380 // special printing for statement-expressions.
3381 if (const StmtExpr *SE = dyn_cast<StmtExpr>(S)) {
3382 const CompoundStmt *Sub = SE->getSubStmt();
3384 if (Sub->children()) {
3386 Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS);
3391 // special printing for comma expressions.
3392 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
3393 if (B->getOpcode() == BO_Comma) {
3395 Helper->handledStmt(B->getRHS(),OS);
3401 S->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts()));
3403 if (isa<CXXOperatorCallExpr>(S)) {
3404 OS << " (OperatorCall)";
3405 } else if (isa<CXXBindTemporaryExpr>(S)) {
3406 OS << " (BindTemporary)";
3409 // Expressions need a newline.
3413 } else if (const CFGInitializer *IE = E.getAs<CFGInitializer>()) {
3414 const CXXCtorInitializer *I = IE->getInitializer();
3415 if (I->isBaseInitializer())
3416 OS << I->getBaseClass()->getAsCXXRecordDecl()->getName();
3417 else OS << I->getAnyMember()->getName();
3420 if (Expr *IE = I->getInit())
3421 IE->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts()));
3424 if (I->isBaseInitializer())
3425 OS << " (Base initializer)\n";
3426 else OS << " (Member initializer)\n";
3428 } else if (const CFGAutomaticObjDtor *DE = E.getAs<CFGAutomaticObjDtor>()){
3429 const VarDecl *VD = DE->getVarDecl();
3430 Helper->handleDecl(VD, OS);
3432 const Type* T = VD->getType().getTypePtr();
3433 if (const ReferenceType* RT = T->getAs<ReferenceType>())
3434 T = RT->getPointeeType().getTypePtr();
3435 else if (const Type *ET = T->getArrayElementTypeNoTypeQual())
3438 OS << ".~" << T->getAsCXXRecordDecl()->getName().str() << "()";
3439 OS << " (Implicit destructor)\n";
3441 } else if (const CFGBaseDtor *BE = E.getAs<CFGBaseDtor>()) {
3442 const CXXBaseSpecifier *BS = BE->getBaseSpecifier();
3443 OS << "~" << BS->getType()->getAsCXXRecordDecl()->getName() << "()";
3444 OS << " (Base object destructor)\n";
3446 } else if (const CFGMemberDtor *ME = E.getAs<CFGMemberDtor>()) {
3447 const FieldDecl *FD = ME->getFieldDecl();
3449 const Type *T = FD->getType().getTypePtr();
3450 if (const Type *ET = T->getArrayElementTypeNoTypeQual())
3453 OS << "this->" << FD->getName();
3454 OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()";
3455 OS << " (Member object destructor)\n";
3457 } else if (const CFGTemporaryDtor *TE = E.getAs<CFGTemporaryDtor>()) {
3458 const CXXBindTemporaryExpr *BT = TE->getBindTemporaryExpr();
3459 OS << "~" << BT->getType()->getAsCXXRecordDecl()->getName() << "()";
3460 OS << " (Temporary object destructor)\n";
3464 static void print_block(raw_ostream &OS, const CFG* cfg,
3466 StmtPrinterHelper* Helper, bool print_edges) {
3468 if (Helper) Helper->setBlockID(B.getBlockID());
3470 // Print the header.
3471 OS << "\n [ B" << B.getBlockID();
3473 if (&B == &cfg->getEntry())
3474 OS << " (ENTRY) ]\n";
3475 else if (&B == &cfg->getExit())
3476 OS << " (EXIT) ]\n";
3477 else if (&B == cfg->getIndirectGotoBlock())
3478 OS << " (INDIRECT GOTO DISPATCH) ]\n";
3482 // Print the label of this block.
3483 if (Stmt *Label = const_cast<Stmt*>(B.getLabel())) {
3488 if (LabelStmt *L = dyn_cast<LabelStmt>(Label))
3490 else if (CaseStmt *C = dyn_cast<CaseStmt>(Label)) {
3492 C->getLHS()->printPretty(OS, Helper,
3493 PrintingPolicy(Helper->getLangOpts()));
3496 C->getRHS()->printPretty(OS, Helper,
3497 PrintingPolicy(Helper->getLangOpts()));
3499 } else if (isa<DefaultStmt>(Label))
3501 else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Label)) {
3503 if (CS->getExceptionDecl())
3504 CS->getExceptionDecl()->print(OS, PrintingPolicy(Helper->getLangOpts()),
3511 llvm_unreachable("Invalid label statement in CFGBlock.");
3516 // Iterate through the statements in the block and print them.
3519 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ;
3520 I != E ; ++I, ++j ) {
3522 // Print the statement # in the basic block and the statement itself.
3526 OS << llvm::format("%3d", j) << ": ";
3529 Helper->setStmtID(j);
3531 print_elem(OS,Helper,*I);
3534 // Print the terminator of this block.
3535 if (B.getTerminator()) {
3541 if (Helper) Helper->setBlockID(-1);
3543 CFGBlockTerminatorPrint TPrinter(OS, Helper,
3544 PrintingPolicy(Helper->getLangOpts()));
3545 TPrinter.Visit(const_cast<Stmt*>(B.getTerminator().getStmt()));
3550 // Print the predecessors of this block.
3551 OS << " Predecessors (" << B.pred_size() << "):";
3554 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end();
3557 if (i == 8 || (i-8) == 0)
3560 OS << " B" << (*I)->getBlockID();
3565 // Print the successors of this block.
3566 OS << " Successors (" << B.succ_size() << "):";
3569 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end();
3572 if (i == 8 || (i-8) % 10 == 0)
3576 OS << " B" << (*I)->getBlockID();
3586 /// dump - A simple pretty printer of a CFG that outputs to stderr.
3587 void CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); }
3589 /// print - A simple pretty printer of a CFG that outputs to an ostream.
3590 void CFG::print(raw_ostream &OS, const LangOptions &LO) const {
3591 StmtPrinterHelper Helper(this, LO);
3593 // Print the entry block.
3594 print_block(OS, this, getEntry(), &Helper, true);
3596 // Iterate through the CFGBlocks and print them one by one.
3597 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) {
3598 // Skip the entry block, because we already printed it.
3599 if (&(**I) == &getEntry() || &(**I) == &getExit())
3602 print_block(OS, this, **I, &Helper, true);
3605 // Print the exit block.
3606 print_block(OS, this, getExit(), &Helper, true);
3610 /// dump - A simply pretty printer of a CFGBlock that outputs to stderr.
3611 void CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const {
3612 print(llvm::errs(), cfg, LO);
3615 /// print - A simple pretty printer of a CFGBlock that outputs to an ostream.
3616 /// Generally this will only be called from CFG::print.
3617 void CFGBlock::print(raw_ostream &OS, const CFG* cfg,
3618 const LangOptions &LO) const {
3619 StmtPrinterHelper Helper(cfg, LO);
3620 print_block(OS, cfg, *this, &Helper, true);
3623 /// printTerminator - A simple pretty printer of the terminator of a CFGBlock.
3624 void CFGBlock::printTerminator(raw_ostream &OS,
3625 const LangOptions &LO) const {
3626 CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO));
3627 TPrinter.Visit(const_cast<Stmt*>(getTerminator().getStmt()));
3630 Stmt *CFGBlock::getTerminatorCondition() {
3631 Stmt *Terminator = this->Terminator;
3637 switch (Terminator->getStmtClass()) {
3641 case Stmt::ForStmtClass:
3642 E = cast<ForStmt>(Terminator)->getCond();
3645 case Stmt::WhileStmtClass:
3646 E = cast<WhileStmt>(Terminator)->getCond();
3649 case Stmt::DoStmtClass:
3650 E = cast<DoStmt>(Terminator)->getCond();
3653 case Stmt::IfStmtClass:
3654 E = cast<IfStmt>(Terminator)->getCond();
3657 case Stmt::ChooseExprClass:
3658 E = cast<ChooseExpr>(Terminator)->getCond();
3661 case Stmt::IndirectGotoStmtClass:
3662 E = cast<IndirectGotoStmt>(Terminator)->getTarget();
3665 case Stmt::SwitchStmtClass:
3666 E = cast<SwitchStmt>(Terminator)->getCond();
3669 case Stmt::BinaryConditionalOperatorClass:
3670 E = cast<BinaryConditionalOperator>(Terminator)->getCond();
3673 case Stmt::ConditionalOperatorClass:
3674 E = cast<ConditionalOperator>(Terminator)->getCond();
3677 case Stmt::BinaryOperatorClass: // '&&' and '||'
3678 E = cast<BinaryOperator>(Terminator)->getLHS();
3681 case Stmt::ObjCForCollectionStmtClass:
3685 return E ? E->IgnoreParens() : NULL;
3688 //===----------------------------------------------------------------------===//
3689 // CFG Graphviz Visualization
3690 //===----------------------------------------------------------------------===//
3694 static StmtPrinterHelper* GraphHelper;
3697 void CFG::viewCFG(const LangOptions &LO) const {
3699 StmtPrinterHelper H(this, LO);
3701 llvm::ViewGraph(this,"CFG");
3708 struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits {
3710 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
3712 static std::string getNodeLabel(const CFGBlock *Node, const CFG* Graph) {
3715 std::string OutSStr;
3716 llvm::raw_string_ostream Out(OutSStr);
3717 print_block(Out,Graph, *Node, GraphHelper, false);
3718 std::string& OutStr = Out.str();
3720 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin());
3722 // Process string output to make it nicer...
3723 for (unsigned i = 0; i != OutStr.length(); ++i)
3724 if (OutStr[i] == '\n') { // Left justify
3726 OutStr.insert(OutStr.begin()+i+1, 'l');
3735 } // end namespace llvm