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 "llvm/Support/GraphWriter.h"
21 #include "llvm/Support/Allocator.h"
22 #include "llvm/Support/Format.h"
23 #include "llvm/ADT/DenseMap.h"
24 #include "llvm/ADT/SmallPtrSet.h"
25 #include "llvm/ADT/OwningPtr.h"
27 using namespace clang
;
31 static SourceLocation
GetEndLoc(Decl
* D
) {
32 if (VarDecl
* VD
= dyn_cast
<VarDecl
>(D
))
33 if (Expr
* Ex
= VD
->getInit())
34 return Ex
->getSourceRange().getEnd();
35 return D
->getLocation();
38 /// The CFG builder uses a recursive algorithm to build the CFG. When
39 /// we process an expression, sometimes we know that we must add the
40 /// subexpressions as block-level expressions. For example:
44 /// When processing the '||' expression, we know that exp1 and exp2
45 /// need to be added as block-level expressions, even though they
46 /// might not normally need to be. AddStmtChoice records this
47 /// contextual information. If AddStmtChoice is 'NotAlwaysAdd', then
48 /// the builder has an option not to add a subexpression as a
49 /// block-level expression.
53 enum Kind
{ NotAlwaysAdd
= 0, AlwaysAdd
= 1 };
55 AddStmtChoice(Kind a_kind
= NotAlwaysAdd
) : kind(a_kind
) {}
57 bool alwaysAdd() const { return kind
& AlwaysAdd
; }
59 /// Return a copy of this object, except with the 'always-add' bit
61 AddStmtChoice
withAlwaysAdd(bool alwaysAdd
) const {
62 return AddStmtChoice(alwaysAdd
? Kind(kind
| AlwaysAdd
) :
63 Kind(kind
& ~AlwaysAdd
));
70 /// LocalScope - Node in tree of local scopes created for C++ implicit
71 /// destructor calls generation. It contains list of automatic variables
72 /// declared in the scope and link to position in previous scope this scope
75 /// The process of creating local scopes is as follows:
76 /// - Init CFGBuilder::ScopePos with invalid position (equivalent for null),
77 /// - Before processing statements in scope (e.g. CompoundStmt) create
78 /// LocalScope object using CFGBuilder::ScopePos as link to previous scope
79 /// and set CFGBuilder::ScopePos to the end of new scope,
80 /// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points
82 /// - For every normal (without jump) end of scope add to CFGBlock destructors
83 /// for objects in the current scope,
84 /// - For every jump add to CFGBlock destructors for objects
85 /// between CFGBuilder::ScopePos and local scope position saved for jump
86 /// target. Thanks to C++ restrictions on goto jumps we can be sure that
87 /// jump target position will be on the path to root from CFGBuilder::ScopePos
88 /// (adding any variable that doesn't need constructor to be called to
89 /// LocalScope can break this assumption),
93 typedef BumpVector
<VarDecl
*> AutomaticVarsTy
;
95 /// const_iterator - Iterates local scope backwards and jumps to previous
96 /// scope on reaching the beginning of currently iterated scope.
97 class const_iterator
{
98 const LocalScope
* Scope
;
100 /// VarIter is guaranteed to be greater then 0 for every valid iterator.
101 /// Invalid iterator (with null Scope) has VarIter equal to 0.
105 /// Create invalid iterator. Dereferencing invalid iterator is not allowed.
106 /// Incrementing invalid iterator is allowed and will result in invalid
109 : Scope(NULL
), VarIter(0) {}
111 /// Create valid iterator. In case when S.Prev is an invalid iterator and
112 /// I is equal to 0, this will create invalid iterator.
113 const_iterator(const LocalScope
& S
, unsigned I
)
114 : Scope(&S
), VarIter(I
) {
115 // Iterator to "end" of scope is not allowed. Handle it by going up
116 // in scopes tree possibly up to invalid iterator in the root.
117 if (VarIter
== 0 && Scope
)
121 VarDecl
* const* operator->() const {
122 assert (Scope
&& "Dereferencing invalid iterator is not allowed");
123 assert (VarIter
!= 0 && "Iterator has invalid value of VarIter member");
124 return &Scope
->Vars
[VarIter
- 1];
126 VarDecl
* operator*() const {
127 return *this->operator->();
130 const_iterator
& operator++() {
134 assert (VarIter
!= 0 && "Iterator has invalid value of VarIter member");
140 const_iterator
operator++(int) {
141 const_iterator P
= *this;
146 bool operator==(const const_iterator
& rhs
) const {
147 return Scope
== rhs
.Scope
&& VarIter
== rhs
.VarIter
;
149 bool operator!=(const const_iterator
& rhs
) const {
150 return !(*this == rhs
);
153 operator bool() const {
154 return *this != const_iterator();
157 int distance(const_iterator L
);
160 friend class const_iterator
;
163 BumpVectorContext ctx
;
165 /// Automatic variables in order of declaration.
166 AutomaticVarsTy Vars
;
167 /// Iterator to variable in previous scope that was declared just before
168 /// begin of this scope.
172 /// Constructs empty scope linked to previous scope in specified place.
173 LocalScope(BumpVectorContext
&ctx
, const_iterator P
)
174 : ctx(ctx
), Vars(ctx
, 4), Prev(P
) {}
176 /// Begin of scope in direction of CFG building (backwards).
177 const_iterator
begin() const { return const_iterator(*this, Vars
.size()); }
179 void addVar(VarDecl
* VD
) {
180 Vars
.push_back(VD
, ctx
);
184 /// distance - Calculates distance from this to L. L must be reachable from this
185 /// (with use of ++ operator). Cost of calculating the distance is linear w.r.t.
186 /// number of scopes between this and L.
187 int LocalScope::const_iterator::distance(LocalScope::const_iterator L
) {
189 const_iterator F
= *this;
190 while (F
.Scope
!= L
.Scope
) {
191 assert (F
!= const_iterator()
192 && "L iterator is not reachable from F iterator.");
196 D
+= F
.VarIter
- L
.VarIter
;
200 /// BlockScopePosPair - Structure for specifying position in CFG during its
201 /// build process. It consists of CFGBlock that specifies position in CFG graph
202 /// and LocalScope::const_iterator that specifies position in LocalScope graph.
203 struct BlockScopePosPair
{
204 BlockScopePosPair() : block(0) {}
205 BlockScopePosPair(CFGBlock
* b
, LocalScope::const_iterator scopePos
)
206 : block(b
), scopePosition(scopePos
) {}
209 LocalScope::const_iterator scopePosition
;
212 /// CFGBuilder - This class implements CFG construction from an AST.
213 /// The builder is stateful: an instance of the builder should be used to only
214 /// construct a single CFG.
218 /// CFGBuilder builder;
219 /// CFG* cfg = builder.BuildAST(stmt1);
221 /// CFG construction is done via a recursive walk of an AST. We actually parse
222 /// the AST in reverse order so that the successor of a basic block is
223 /// constructed prior to its predecessor. This allows us to nicely capture
224 /// implicit fall-throughs without extra basic blocks.
227 typedef BlockScopePosPair JumpTarget
;
228 typedef BlockScopePosPair JumpSource
;
231 llvm::OwningPtr
<CFG
> cfg
;
235 JumpTarget ContinueJumpTarget
;
236 JumpTarget BreakJumpTarget
;
237 CFGBlock
* SwitchTerminatedBlock
;
238 CFGBlock
* DefaultCaseBlock
;
239 CFGBlock
* TryTerminatedBlock
;
241 // Current position in local scope.
242 LocalScope::const_iterator ScopePos
;
244 // LabelMap records the mapping from Label expressions to their jump targets.
245 typedef llvm::DenseMap
<LabelDecl
*, JumpTarget
> LabelMapTy
;
248 // A list of blocks that end with a "goto" that must be backpatched to their
249 // resolved targets upon completion of CFG construction.
250 typedef std::vector
<JumpSource
> BackpatchBlocksTy
;
251 BackpatchBlocksTy BackpatchBlocks
;
253 // A list of labels whose address has been taken (for indirect gotos).
254 typedef llvm::SmallPtrSet
<LabelDecl
*, 5> LabelSetTy
;
255 LabelSetTy AddressTakenLabels
;
258 CFG::BuildOptions BuildOpts
;
261 explicit CFGBuilder() : cfg(new CFG()), // crew a new CFG
262 Block(NULL
), Succ(NULL
),
263 SwitchTerminatedBlock(NULL
), DefaultCaseBlock(NULL
),
264 TryTerminatedBlock(NULL
), badCFG(false) {}
266 // buildCFG - Used by external clients to construct the CFG.
267 CFG
* buildCFG(const Decl
*D
, Stmt
*Statement
, ASTContext
*C
,
268 CFG::BuildOptions BO
);
271 // Visitors to walk an AST and construct the CFG.
272 CFGBlock
*VisitAddrLabelExpr(AddrLabelExpr
*A
, AddStmtChoice asc
);
273 CFGBlock
*VisitBinaryOperator(BinaryOperator
*B
, AddStmtChoice asc
);
274 CFGBlock
*VisitBlockExpr(BlockExpr
* E
, AddStmtChoice asc
);
275 CFGBlock
*VisitBreakStmt(BreakStmt
*B
);
276 CFGBlock
*VisitCXXCatchStmt(CXXCatchStmt
*S
);
277 CFGBlock
*VisitExprWithCleanups(ExprWithCleanups
*E
,
279 CFGBlock
*VisitCXXThrowExpr(CXXThrowExpr
*T
);
280 CFGBlock
*VisitCXXTryStmt(CXXTryStmt
*S
);
281 CFGBlock
*VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr
*E
,
283 CFGBlock
*VisitCXXConstructExpr(CXXConstructExpr
*C
, AddStmtChoice asc
);
284 CFGBlock
*VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr
*E
,
286 CFGBlock
*VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr
*C
,
288 CFGBlock
*VisitCXXMemberCallExpr(CXXMemberCallExpr
*C
, AddStmtChoice asc
);
289 CFGBlock
*VisitCallExpr(CallExpr
*C
, AddStmtChoice asc
);
290 CFGBlock
*VisitCaseStmt(CaseStmt
*C
);
291 CFGBlock
*VisitChooseExpr(ChooseExpr
*C
, AddStmtChoice asc
);
292 CFGBlock
*VisitCompoundStmt(CompoundStmt
*C
);
293 CFGBlock
*VisitConditionalOperator(AbstractConditionalOperator
*C
,
295 CFGBlock
*VisitContinueStmt(ContinueStmt
*C
);
296 CFGBlock
*VisitDeclStmt(DeclStmt
*DS
);
297 CFGBlock
*VisitDeclSubExpr(DeclStmt
* DS
);
298 CFGBlock
*VisitDefaultStmt(DefaultStmt
*D
);
299 CFGBlock
*VisitDoStmt(DoStmt
*D
);
300 CFGBlock
*VisitForStmt(ForStmt
*F
);
301 CFGBlock
*VisitGotoStmt(GotoStmt
* G
);
302 CFGBlock
*VisitIfStmt(IfStmt
*I
);
303 CFGBlock
*VisitImplicitCastExpr(ImplicitCastExpr
*E
, AddStmtChoice asc
);
304 CFGBlock
*VisitIndirectGotoStmt(IndirectGotoStmt
*I
);
305 CFGBlock
*VisitLabelStmt(LabelStmt
*L
);
306 CFGBlock
*VisitMemberExpr(MemberExpr
*M
, AddStmtChoice asc
);
307 CFGBlock
*VisitObjCAtCatchStmt(ObjCAtCatchStmt
*S
);
308 CFGBlock
*VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt
*S
);
309 CFGBlock
*VisitObjCAtThrowStmt(ObjCAtThrowStmt
*S
);
310 CFGBlock
*VisitObjCAtTryStmt(ObjCAtTryStmt
*S
);
311 CFGBlock
*VisitObjCForCollectionStmt(ObjCForCollectionStmt
*S
);
312 CFGBlock
*VisitReturnStmt(ReturnStmt
* R
);
313 CFGBlock
*VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr
*E
, AddStmtChoice asc
);
314 CFGBlock
*VisitStmtExpr(StmtExpr
*S
, AddStmtChoice asc
);
315 CFGBlock
*VisitSwitchStmt(SwitchStmt
*S
);
316 CFGBlock
*VisitUnaryOperator(UnaryOperator
*U
, AddStmtChoice asc
);
317 CFGBlock
*VisitWhileStmt(WhileStmt
*W
);
319 CFGBlock
*Visit(Stmt
*S
, AddStmtChoice asc
= AddStmtChoice::NotAlwaysAdd
);
320 CFGBlock
*VisitStmt(Stmt
*S
, AddStmtChoice asc
);
321 CFGBlock
*VisitChildren(Stmt
* S
);
323 // Visitors to walk an AST and generate destructors of temporaries in
325 CFGBlock
*VisitForTemporaryDtors(Stmt
*E
, bool BindToTemporary
= false);
326 CFGBlock
*VisitChildrenForTemporaryDtors(Stmt
*E
);
327 CFGBlock
*VisitBinaryOperatorForTemporaryDtors(BinaryOperator
*E
);
328 CFGBlock
*VisitCXXBindTemporaryExprForTemporaryDtors(CXXBindTemporaryExpr
*E
,
329 bool BindToTemporary
);
331 VisitConditionalOperatorForTemporaryDtors(AbstractConditionalOperator
*E
,
332 bool BindToTemporary
);
334 // NYS == Not Yet Supported
340 void autoCreateBlock() { if (!Block
) Block
= createBlock(); }
341 CFGBlock
*createBlock(bool add_successor
= true);
343 CFGBlock
*addStmt(Stmt
*S
) {
344 return Visit(S
, AddStmtChoice::AlwaysAdd
);
346 CFGBlock
*addInitializer(CXXCtorInitializer
*I
);
347 void addAutomaticObjDtors(LocalScope::const_iterator B
,
348 LocalScope::const_iterator E
, Stmt
* S
);
349 void addImplicitDtorsForDestructor(const CXXDestructorDecl
*DD
);
351 // Local scopes creation.
352 LocalScope
* createOrReuseLocalScope(LocalScope
* Scope
);
354 void addLocalScopeForStmt(Stmt
* S
);
355 LocalScope
* addLocalScopeForDeclStmt(DeclStmt
* DS
, LocalScope
* Scope
= NULL
);
356 LocalScope
* addLocalScopeForVarDecl(VarDecl
* VD
, LocalScope
* Scope
= NULL
);
358 void addLocalScopeAndDtors(Stmt
* S
);
360 // Interface to CFGBlock - adding CFGElements.
361 void appendStmt(CFGBlock
*B
, Stmt
*S
,
362 AddStmtChoice asc
= AddStmtChoice::AlwaysAdd
) {
363 B
->appendStmt(S
, cfg
->getBumpVectorContext());
365 void appendInitializer(CFGBlock
*B
, CXXCtorInitializer
*I
) {
366 B
->appendInitializer(I
, cfg
->getBumpVectorContext());
368 void appendBaseDtor(CFGBlock
*B
, const CXXBaseSpecifier
*BS
) {
369 B
->appendBaseDtor(BS
, cfg
->getBumpVectorContext());
371 void appendMemberDtor(CFGBlock
*B
, FieldDecl
*FD
) {
372 B
->appendMemberDtor(FD
, cfg
->getBumpVectorContext());
374 void appendTemporaryDtor(CFGBlock
*B
, CXXBindTemporaryExpr
*E
) {
375 B
->appendTemporaryDtor(E
, cfg
->getBumpVectorContext());
378 void insertAutomaticObjDtors(CFGBlock
* Blk
, CFGBlock::iterator I
,
379 LocalScope::const_iterator B
, LocalScope::const_iterator E
, Stmt
* S
);
380 void appendAutomaticObjDtors(CFGBlock
* Blk
, LocalScope::const_iterator B
,
381 LocalScope::const_iterator E
, Stmt
* S
);
382 void prependAutomaticObjDtorsWithTerminator(CFGBlock
* Blk
,
383 LocalScope::const_iterator B
, LocalScope::const_iterator E
);
385 void addSuccessor(CFGBlock
*B
, CFGBlock
*S
) {
386 B
->addSuccessor(S
, cfg
->getBumpVectorContext());
389 /// TryResult - a class representing a variant over the values
390 /// 'true', 'false', or 'unknown'. This is returned by tryEvaluateBool,
391 /// and is used by the CFGBuilder to decide if a branch condition
392 /// can be decided up front during CFG construction.
396 TryResult(bool b
) : X(b
? 1 : 0) {}
397 TryResult() : X(-1) {}
399 bool isTrue() const { return X
== 1; }
400 bool isFalse() const { return X
== 0; }
401 bool isKnown() const { return X
>= 0; }
408 /// tryEvaluateBool - Try and evaluate the Stmt and return 0 or 1
409 /// if we can evaluate to a known value, otherwise return -1.
410 TryResult
tryEvaluateBool(Expr
*S
) {
411 if (!BuildOpts
.PruneTriviallyFalseEdges
)
414 Expr::EvalResult Result
;
415 if (!S
->isTypeDependent() && !S
->isValueDependent() &&
416 S
->Evaluate(Result
, *Context
) && Result
.Val
.isInt())
417 return Result
.Val
.getInt().getBoolValue();
423 // FIXME: Add support for dependent-sized array types in C++?
424 // Does it even make sense to build a CFG for an uninstantiated template?
425 static const VariableArrayType
*FindVA(const Type
*t
) {
426 while (const ArrayType
*vt
= dyn_cast
<ArrayType
>(t
)) {
427 if (const VariableArrayType
*vat
= dyn_cast
<VariableArrayType
>(vt
))
428 if (vat
->getSizeExpr())
431 t
= vt
->getElementType().getTypePtr();
437 /// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an
438 /// arbitrary statement. Examples include a single expression or a function
439 /// body (compound statement). The ownership of the returned CFG is
440 /// transferred to the caller. If CFG construction fails, this method returns
442 CFG
* CFGBuilder::buildCFG(const Decl
*D
, Stmt
* Statement
, ASTContext
* C
,
443 CFG::BuildOptions BO
) {
452 // Create an empty block that will serve as the exit block for the CFG. Since
453 // this is the first block added to the CFG, it will be implicitly registered
454 // as the exit block.
455 Succ
= createBlock();
456 assert(Succ
== &cfg
->getExit());
457 Block
= NULL
; // the EXIT block is empty. Create all other blocks lazily.
459 if (BuildOpts
.AddImplicitDtors
)
460 if (const CXXDestructorDecl
*DD
= dyn_cast_or_null
<CXXDestructorDecl
>(D
))
461 addImplicitDtorsForDestructor(DD
);
463 // Visit the statements and create the CFG.
464 CFGBlock
*B
= addStmt(Statement
);
469 // For C++ constructor add initializers to CFG.
470 if (const CXXConstructorDecl
*CD
= dyn_cast_or_null
<CXXConstructorDecl
>(D
)) {
471 for (CXXConstructorDecl::init_const_reverse_iterator I
= CD
->init_rbegin(),
472 E
= CD
->init_rend(); I
!= E
; ++I
) {
473 B
= addInitializer(*I
);
482 // Backpatch the gotos whose label -> block mappings we didn't know when we
484 for (BackpatchBlocksTy::iterator I
= BackpatchBlocks
.begin(),
485 E
= BackpatchBlocks
.end(); I
!= E
; ++I
) {
487 CFGBlock
* B
= I
->block
;
488 GotoStmt
* G
= cast
<GotoStmt
>(B
->getTerminator());
489 LabelMapTy::iterator LI
= LabelMap
.find(G
->getLabel());
491 // If there is no target for the goto, then we are looking at an
492 // incomplete AST. Handle this by not registering a successor.
493 if (LI
== LabelMap
.end()) continue;
495 JumpTarget JT
= LI
->second
;
496 prependAutomaticObjDtorsWithTerminator(B
, I
->scopePosition
,
498 addSuccessor(B
, JT
.block
);
501 // Add successors to the Indirect Goto Dispatch block (if we have one).
502 if (CFGBlock
* B
= cfg
->getIndirectGotoBlock())
503 for (LabelSetTy::iterator I
= AddressTakenLabels
.begin(),
504 E
= AddressTakenLabels
.end(); I
!= E
; ++I
) {
506 // Lookup the target block.
507 LabelMapTy::iterator LI
= LabelMap
.find(*I
);
509 // If there is no target block that contains label, then we are looking
510 // at an incomplete AST. Handle this by not registering a successor.
511 if (LI
== LabelMap
.end()) continue;
513 addSuccessor(B
, LI
->second
.block
);
516 // Create an empty entry block that has no predecessors.
517 cfg
->setEntry(createBlock());
522 /// createBlock - Used to lazily create blocks that are connected
523 /// to the current (global) succcessor.
524 CFGBlock
* CFGBuilder::createBlock(bool add_successor
) {
525 CFGBlock
* B
= cfg
->createBlock();
526 if (add_successor
&& Succ
)
527 addSuccessor(B
, Succ
);
531 /// addInitializer - Add C++ base or member initializer element to CFG.
532 CFGBlock
*CFGBuilder::addInitializer(CXXCtorInitializer
*I
) {
533 if (!BuildOpts
.AddInitializers
)
536 bool IsReference
= false;
537 bool HasTemporaries
= false;
539 // Destructors of temporaries in initialization expression should be called
540 // after initialization finishes.
541 Expr
*Init
= I
->getInit();
543 if (FieldDecl
*FD
= I
->getAnyMember())
544 IsReference
= FD
->getType()->isReferenceType();
545 HasTemporaries
= isa
<ExprWithCleanups
>(Init
);
547 if (BuildOpts
.AddImplicitDtors
&& HasTemporaries
) {
548 // Generate destructors for temporaries in initialization expression.
549 VisitForTemporaryDtors(cast
<ExprWithCleanups
>(Init
)->getSubExpr(),
555 appendInitializer(Block
, I
);
558 if (HasTemporaries
) {
559 // For expression with temporaries go directly to subexpression to omit
560 // generating destructors for the second time.
561 return Visit(cast
<ExprWithCleanups
>(Init
)->getSubExpr());
569 /// addAutomaticObjDtors - Add to current block automatic objects destructors
570 /// for objects in range of local scope positions. Use S as trigger statement
572 void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B
,
573 LocalScope::const_iterator E
, Stmt
* S
) {
574 if (!BuildOpts
.AddImplicitDtors
)
581 appendAutomaticObjDtors(Block
, B
, E
, S
);
584 /// addImplicitDtorsForDestructor - Add implicit destructors generated for
585 /// base and member objects in destructor.
586 void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl
*DD
) {
587 assert (BuildOpts
.AddImplicitDtors
588 && "Can be called only when dtors should be added");
589 const CXXRecordDecl
*RD
= DD
->getParent();
591 // At the end destroy virtual base objects.
592 for (CXXRecordDecl::base_class_const_iterator VI
= RD
->vbases_begin(),
593 VE
= RD
->vbases_end(); VI
!= VE
; ++VI
) {
594 const CXXRecordDecl
*CD
= VI
->getType()->getAsCXXRecordDecl();
595 if (!CD
->hasTrivialDestructor()) {
597 appendBaseDtor(Block
, VI
);
601 // Before virtual bases destroy direct base objects.
602 for (CXXRecordDecl::base_class_const_iterator BI
= RD
->bases_begin(),
603 BE
= RD
->bases_end(); BI
!= BE
; ++BI
) {
604 if (!BI
->isVirtual()) {
605 const CXXRecordDecl
*CD
= BI
->getType()->getAsCXXRecordDecl();
606 if (!CD
->hasTrivialDestructor()) {
608 appendBaseDtor(Block
, BI
);
613 // First destroy member objects.
614 for (CXXRecordDecl::field_iterator FI
= RD
->field_begin(),
615 FE
= RD
->field_end(); FI
!= FE
; ++FI
) {
616 // Check for constant size array. Set type to array element type.
617 QualType QT
= FI
->getType();
618 if (const ConstantArrayType
*AT
= Context
->getAsConstantArrayType(QT
)) {
619 if (AT
->getSize() == 0)
621 QT
= AT
->getElementType();
624 if (const CXXRecordDecl
*CD
= QT
->getAsCXXRecordDecl())
625 if (!CD
->hasTrivialDestructor()) {
627 appendMemberDtor(Block
, *FI
);
632 /// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either
633 /// way return valid LocalScope object.
634 LocalScope
* CFGBuilder::createOrReuseLocalScope(LocalScope
* Scope
) {
636 llvm::BumpPtrAllocator
&alloc
= cfg
->getAllocator();
637 Scope
= alloc
.Allocate
<LocalScope
>();
638 BumpVectorContext
ctx(alloc
);
639 new (Scope
) LocalScope(ctx
, ScopePos
);
644 /// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement
645 /// that should create implicit scope (e.g. if/else substatements).
646 void CFGBuilder::addLocalScopeForStmt(Stmt
* S
) {
647 if (!BuildOpts
.AddImplicitDtors
)
650 LocalScope
*Scope
= 0;
652 // For compound statement we will be creating explicit scope.
653 if (CompoundStmt
*CS
= dyn_cast
<CompoundStmt
>(S
)) {
654 for (CompoundStmt::body_iterator BI
= CS
->body_begin(), BE
= CS
->body_end()
657 if (LabelStmt
*LS
= dyn_cast
<LabelStmt
>(SI
))
658 SI
= LS
->getSubStmt();
659 if (DeclStmt
*DS
= dyn_cast
<DeclStmt
>(SI
))
660 Scope
= addLocalScopeForDeclStmt(DS
, Scope
);
665 // For any other statement scope will be implicit and as such will be
666 // interesting only for DeclStmt.
667 if (LabelStmt
*LS
= dyn_cast
<LabelStmt
>(S
))
668 S
= LS
->getSubStmt();
669 if (DeclStmt
*DS
= dyn_cast
<DeclStmt
>(S
))
670 addLocalScopeForDeclStmt(DS
);
673 /// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will
674 /// reuse Scope if not NULL.
675 LocalScope
* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt
* DS
,
677 if (!BuildOpts
.AddImplicitDtors
)
680 for (DeclStmt::decl_iterator DI
= DS
->decl_begin(), DE
= DS
->decl_end()
682 if (VarDecl
* VD
= dyn_cast
<VarDecl
>(*DI
))
683 Scope
= addLocalScopeForVarDecl(VD
, Scope
);
688 /// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will
689 /// create add scope for automatic objects and temporary objects bound to
690 /// const reference. Will reuse Scope if not NULL.
691 LocalScope
* CFGBuilder::addLocalScopeForVarDecl(VarDecl
* VD
,
693 if (!BuildOpts
.AddImplicitDtors
)
696 // Check if variable is local.
697 switch (VD
->getStorageClass()) {
702 default: return Scope
;
705 // Check for const references bound to temporary. Set type to pointee.
706 QualType QT
= VD
->getType();
707 if (const ReferenceType
* RT
= QT
.getTypePtr()->getAs
<ReferenceType
>()) {
708 QT
= RT
->getPointeeType();
709 if (!QT
.isConstQualified())
711 if (!VD
->getInit() || !VD
->getInit()->Classify(*Context
).isRValue())
715 // Check for constant size array. Set type to array element type.
716 if (const ConstantArrayType
*AT
= Context
->getAsConstantArrayType(QT
)) {
717 if (AT
->getSize() == 0)
719 QT
= AT
->getElementType();
722 // Check if type is a C++ class with non-trivial destructor.
723 if (const CXXRecordDecl
* CD
= QT
->getAsCXXRecordDecl())
724 if (!CD
->hasTrivialDestructor()) {
725 // Add the variable to scope
726 Scope
= createOrReuseLocalScope(Scope
);
728 ScopePos
= Scope
->begin();
733 /// addLocalScopeAndDtors - For given statement add local scope for it and
734 /// add destructors that will cleanup the scope. Will reuse Scope if not NULL.
735 void CFGBuilder::addLocalScopeAndDtors(Stmt
* S
) {
736 if (!BuildOpts
.AddImplicitDtors
)
739 LocalScope::const_iterator scopeBeginPos
= ScopePos
;
740 addLocalScopeForStmt(S
);
741 addAutomaticObjDtors(ScopePos
, scopeBeginPos
, S
);
744 /// insertAutomaticObjDtors - Insert destructor CFGElements for variables with
745 /// automatic storage duration to CFGBlock's elements vector. Insertion will be
746 /// performed in place specified with iterator.
747 void CFGBuilder::insertAutomaticObjDtors(CFGBlock
* Blk
, CFGBlock::iterator I
,
748 LocalScope::const_iterator B
, LocalScope::const_iterator E
, Stmt
* S
) {
749 BumpVectorContext
& C
= cfg
->getBumpVectorContext();
750 I
= Blk
->beginAutomaticObjDtorsInsert(I
, B
.distance(E
), C
);
752 I
= Blk
->insertAutomaticObjDtor(I
, *B
++, S
);
755 /// appendAutomaticObjDtors - Append destructor CFGElements for variables with
756 /// automatic storage duration to CFGBlock's elements vector. Elements will be
757 /// appended to physical end of the vector which happens to be logical
759 void CFGBuilder::appendAutomaticObjDtors(CFGBlock
* Blk
,
760 LocalScope::const_iterator B
, LocalScope::const_iterator E
, Stmt
* S
) {
761 insertAutomaticObjDtors(Blk
, Blk
->begin(), B
, E
, S
);
764 /// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for
765 /// variables with automatic storage duration to CFGBlock's elements vector.
766 /// Elements will be prepended to physical beginning of the vector which
767 /// happens to be logical end. Use blocks terminator as statement that specifies
768 /// destructors call site.
769 void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock
* Blk
,
770 LocalScope::const_iterator B
, LocalScope::const_iterator E
) {
771 insertAutomaticObjDtors(Blk
, Blk
->end(), B
, E
, Blk
->getTerminator());
774 /// Visit - Walk the subtree of a statement and add extra
775 /// blocks for ternary operators, &&, and ||. We also process "," and
776 /// DeclStmts (which may contain nested control-flow).
777 CFGBlock
* CFGBuilder::Visit(Stmt
* S
, AddStmtChoice asc
) {
783 switch (S
->getStmtClass()) {
785 return VisitStmt(S
, asc
);
787 case Stmt::AddrLabelExprClass
:
788 return VisitAddrLabelExpr(cast
<AddrLabelExpr
>(S
), asc
);
790 case Stmt::BinaryConditionalOperatorClass
:
791 return VisitConditionalOperator(cast
<BinaryConditionalOperator
>(S
), asc
);
793 case Stmt::BinaryOperatorClass
:
794 return VisitBinaryOperator(cast
<BinaryOperator
>(S
), asc
);
796 case Stmt::BlockExprClass
:
797 return VisitBlockExpr(cast
<BlockExpr
>(S
), asc
);
799 case Stmt::BreakStmtClass
:
800 return VisitBreakStmt(cast
<BreakStmt
>(S
));
802 case Stmt::CallExprClass
:
803 case Stmt::CXXOperatorCallExprClass
:
804 return VisitCallExpr(cast
<CallExpr
>(S
), asc
);
806 case Stmt::CaseStmtClass
:
807 return VisitCaseStmt(cast
<CaseStmt
>(S
));
809 case Stmt::ChooseExprClass
:
810 return VisitChooseExpr(cast
<ChooseExpr
>(S
), asc
);
812 case Stmt::CompoundStmtClass
:
813 return VisitCompoundStmt(cast
<CompoundStmt
>(S
));
815 case Stmt::ConditionalOperatorClass
:
816 return VisitConditionalOperator(cast
<ConditionalOperator
>(S
), asc
);
818 case Stmt::ContinueStmtClass
:
819 return VisitContinueStmt(cast
<ContinueStmt
>(S
));
821 case Stmt::CXXCatchStmtClass
:
822 return VisitCXXCatchStmt(cast
<CXXCatchStmt
>(S
));
824 case Stmt::ExprWithCleanupsClass
:
825 return VisitExprWithCleanups(cast
<ExprWithCleanups
>(S
), asc
);
827 case Stmt::CXXBindTemporaryExprClass
:
828 return VisitCXXBindTemporaryExpr(cast
<CXXBindTemporaryExpr
>(S
), asc
);
830 case Stmt::CXXConstructExprClass
:
831 return VisitCXXConstructExpr(cast
<CXXConstructExpr
>(S
), asc
);
833 case Stmt::CXXFunctionalCastExprClass
:
834 return VisitCXXFunctionalCastExpr(cast
<CXXFunctionalCastExpr
>(S
), asc
);
836 case Stmt::CXXTemporaryObjectExprClass
:
837 return VisitCXXTemporaryObjectExpr(cast
<CXXTemporaryObjectExpr
>(S
), asc
);
839 case Stmt::CXXMemberCallExprClass
:
840 return VisitCXXMemberCallExpr(cast
<CXXMemberCallExpr
>(S
), asc
);
842 case Stmt::CXXThrowExprClass
:
843 return VisitCXXThrowExpr(cast
<CXXThrowExpr
>(S
));
845 case Stmt::CXXTryStmtClass
:
846 return VisitCXXTryStmt(cast
<CXXTryStmt
>(S
));
848 case Stmt::DeclStmtClass
:
849 return VisitDeclStmt(cast
<DeclStmt
>(S
));
851 case Stmt::DefaultStmtClass
:
852 return VisitDefaultStmt(cast
<DefaultStmt
>(S
));
854 case Stmt::DoStmtClass
:
855 return VisitDoStmt(cast
<DoStmt
>(S
));
857 case Stmt::ForStmtClass
:
858 return VisitForStmt(cast
<ForStmt
>(S
));
860 case Stmt::GotoStmtClass
:
861 return VisitGotoStmt(cast
<GotoStmt
>(S
));
863 case Stmt::IfStmtClass
:
864 return VisitIfStmt(cast
<IfStmt
>(S
));
866 case Stmt::ImplicitCastExprClass
:
867 return VisitImplicitCastExpr(cast
<ImplicitCastExpr
>(S
), asc
);
869 case Stmt::IndirectGotoStmtClass
:
870 return VisitIndirectGotoStmt(cast
<IndirectGotoStmt
>(S
));
872 case Stmt::LabelStmtClass
:
873 return VisitLabelStmt(cast
<LabelStmt
>(S
));
875 case Stmt::MemberExprClass
:
876 return VisitMemberExpr(cast
<MemberExpr
>(S
), asc
);
878 case Stmt::ObjCAtCatchStmtClass
:
879 return VisitObjCAtCatchStmt(cast
<ObjCAtCatchStmt
>(S
));
881 case Stmt::ObjCAtSynchronizedStmtClass
:
882 return VisitObjCAtSynchronizedStmt(cast
<ObjCAtSynchronizedStmt
>(S
));
884 case Stmt::ObjCAtThrowStmtClass
:
885 return VisitObjCAtThrowStmt(cast
<ObjCAtThrowStmt
>(S
));
887 case Stmt::ObjCAtTryStmtClass
:
888 return VisitObjCAtTryStmt(cast
<ObjCAtTryStmt
>(S
));
890 case Stmt::ObjCForCollectionStmtClass
:
891 return VisitObjCForCollectionStmt(cast
<ObjCForCollectionStmt
>(S
));
893 case Stmt::ParenExprClass
:
894 S
= cast
<ParenExpr
>(S
)->getSubExpr();
897 case Stmt::NullStmtClass
:
900 case Stmt::ReturnStmtClass
:
901 return VisitReturnStmt(cast
<ReturnStmt
>(S
));
903 case Stmt::SizeOfAlignOfExprClass
:
904 return VisitSizeOfAlignOfExpr(cast
<SizeOfAlignOfExpr
>(S
), asc
);
906 case Stmt::StmtExprClass
:
907 return VisitStmtExpr(cast
<StmtExpr
>(S
), asc
);
909 case Stmt::SwitchStmtClass
:
910 return VisitSwitchStmt(cast
<SwitchStmt
>(S
));
912 case Stmt::UnaryOperatorClass
:
913 return VisitUnaryOperator(cast
<UnaryOperator
>(S
), asc
);
915 case Stmt::WhileStmtClass
:
916 return VisitWhileStmt(cast
<WhileStmt
>(S
));
920 CFGBlock
*CFGBuilder::VisitStmt(Stmt
*S
, AddStmtChoice asc
) {
921 if (asc
.alwaysAdd()) {
923 appendStmt(Block
, S
, asc
);
926 return VisitChildren(S
);
929 /// VisitChildren - Visit the children of a Stmt.
930 CFGBlock
*CFGBuilder::VisitChildren(Stmt
* Terminator
) {
932 for (Stmt::child_range I
= Terminator
->children(); I
; ++I
) {
933 if (*I
) B
= Visit(*I
);
938 CFGBlock
*CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr
*A
,
940 AddressTakenLabels
.insert(A
->getLabel());
942 if (asc
.alwaysAdd()) {
944 appendStmt(Block
, A
, asc
);
950 CFGBlock
*CFGBuilder::VisitUnaryOperator(UnaryOperator
*U
,
952 if (asc
.alwaysAdd()) {
954 appendStmt(Block
, U
, asc
);
957 return Visit(U
->getSubExpr(), AddStmtChoice());
960 CFGBlock
*CFGBuilder::VisitBinaryOperator(BinaryOperator
*B
,
962 if (B
->isLogicalOp()) { // && or ||
963 CFGBlock
* ConfluenceBlock
= Block
? Block
: createBlock();
964 appendStmt(ConfluenceBlock
, B
, asc
);
969 // create the block evaluating the LHS
970 CFGBlock
* LHSBlock
= createBlock(false);
971 LHSBlock
->setTerminator(B
);
973 // create the block evaluating the RHS
974 Succ
= ConfluenceBlock
;
976 CFGBlock
* RHSBlock
= addStmt(B
->getRHS());
982 // Create an empty block for cases where the RHS doesn't require
983 // any explicit statements in the CFG.
984 RHSBlock
= createBlock();
987 // See if this is a known constant.
988 TryResult KnownVal
= tryEvaluateBool(B
->getLHS());
989 if (KnownVal
.isKnown() && (B
->getOpcode() == BO_LOr
))
992 // Now link the LHSBlock with RHSBlock.
993 if (B
->getOpcode() == BO_LOr
) {
994 addSuccessor(LHSBlock
, KnownVal
.isTrue() ? NULL
: ConfluenceBlock
);
995 addSuccessor(LHSBlock
, KnownVal
.isFalse() ? NULL
: RHSBlock
);
997 assert(B
->getOpcode() == BO_LAnd
);
998 addSuccessor(LHSBlock
, KnownVal
.isFalse() ? NULL
: RHSBlock
);
999 addSuccessor(LHSBlock
, KnownVal
.isTrue() ? NULL
: ConfluenceBlock
);
1002 // Generate the blocks for evaluating the LHS.
1004 return addStmt(B
->getLHS());
1007 if (B
->getOpcode() == BO_Comma
) { // ,
1009 appendStmt(Block
, B
, asc
);
1010 addStmt(B
->getRHS());
1011 return addStmt(B
->getLHS());
1014 if (B
->isAssignmentOp()) {
1015 if (asc
.alwaysAdd()) {
1017 appendStmt(Block
, B
, asc
);
1020 return Visit(B
->getRHS());
1023 if (asc
.alwaysAdd()) {
1025 appendStmt(Block
, B
, asc
);
1028 CFGBlock
*RBlock
= Visit(B
->getRHS());
1029 CFGBlock
*LBlock
= Visit(B
->getLHS());
1030 // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr
1031 // containing a DoStmt, and the LHS doesn't create a new block, then we should
1032 // return RBlock. Otherwise we'll incorrectly return NULL.
1033 return (LBlock
? LBlock
: RBlock
);
1036 CFGBlock
*CFGBuilder::VisitBlockExpr(BlockExpr
*E
, AddStmtChoice asc
) {
1037 if (asc
.alwaysAdd()) {
1039 appendStmt(Block
, E
, asc
);
1044 CFGBlock
*CFGBuilder::VisitBreakStmt(BreakStmt
*B
) {
1045 // "break" is a control-flow statement. Thus we stop processing the current
1050 // Now create a new block that ends with the break statement.
1051 Block
= createBlock(false);
1052 Block
->setTerminator(B
);
1054 // If there is no target for the break, then we are looking at an incomplete
1055 // AST. This means that the CFG cannot be constructed.
1056 if (BreakJumpTarget
.block
) {
1057 addAutomaticObjDtors(ScopePos
, BreakJumpTarget
.scopePosition
, B
);
1058 addSuccessor(Block
, BreakJumpTarget
.block
);
1066 static bool CanThrow(Expr
*E
) {
1067 QualType Ty
= E
->getType();
1068 if (Ty
->isFunctionPointerType())
1069 Ty
= Ty
->getAs
<PointerType
>()->getPointeeType();
1070 else if (Ty
->isBlockPointerType())
1071 Ty
= Ty
->getAs
<BlockPointerType
>()->getPointeeType();
1073 const FunctionType
*FT
= Ty
->getAs
<FunctionType
>();
1075 if (const FunctionProtoType
*Proto
= dyn_cast
<FunctionProtoType
>(FT
))
1076 if (Proto
->hasEmptyExceptionSpec())
1082 CFGBlock
*CFGBuilder::VisitCallExpr(CallExpr
*C
, AddStmtChoice asc
) {
1083 // If this is a call to a no-return function, this stops the block here.
1084 bool NoReturn
= false;
1085 if (getFunctionExtInfo(*C
->getCallee()->getType()).getNoReturn()) {
1089 bool AddEHEdge
= false;
1091 // Languages without exceptions are assumed to not throw.
1092 if (Context
->getLangOptions().Exceptions
) {
1093 if (BuildOpts
.AddEHEdges
)
1097 if (FunctionDecl
*FD
= C
->getDirectCallee()) {
1098 if (FD
->hasAttr
<NoReturnAttr
>())
1100 if (FD
->hasAttr
<NoThrowAttr
>())
1104 if (!CanThrow(C
->getCallee()))
1107 if (!NoReturn
&& !AddEHEdge
)
1108 return VisitStmt(C
, asc
.withAlwaysAdd(true));
1116 Block
= createBlock(!NoReturn
);
1117 appendStmt(Block
, C
, asc
);
1120 // Wire this to the exit block directly.
1121 addSuccessor(Block
, &cfg
->getExit());
1124 // Add exceptional edges.
1125 if (TryTerminatedBlock
)
1126 addSuccessor(Block
, TryTerminatedBlock
);
1128 addSuccessor(Block
, &cfg
->getExit());
1131 return VisitChildren(C
);
1134 CFGBlock
*CFGBuilder::VisitChooseExpr(ChooseExpr
*C
,
1135 AddStmtChoice asc
) {
1136 CFGBlock
* ConfluenceBlock
= Block
? Block
: createBlock();
1137 appendStmt(ConfluenceBlock
, C
, asc
);
1141 AddStmtChoice alwaysAdd
= asc
.withAlwaysAdd(true);
1142 Succ
= ConfluenceBlock
;
1144 CFGBlock
* LHSBlock
= Visit(C
->getLHS(), alwaysAdd
);
1148 Succ
= ConfluenceBlock
;
1150 CFGBlock
* RHSBlock
= Visit(C
->getRHS(), alwaysAdd
);
1154 Block
= createBlock(false);
1155 // See if this is a known constant.
1156 const TryResult
& KnownVal
= tryEvaluateBool(C
->getCond());
1157 addSuccessor(Block
, KnownVal
.isFalse() ? NULL
: LHSBlock
);
1158 addSuccessor(Block
, KnownVal
.isTrue() ? NULL
: RHSBlock
);
1159 Block
->setTerminator(C
);
1160 return addStmt(C
->getCond());
1164 CFGBlock
* CFGBuilder::VisitCompoundStmt(CompoundStmt
* C
) {
1165 addLocalScopeAndDtors(C
);
1166 CFGBlock
* LastBlock
= Block
;
1168 for (CompoundStmt::reverse_body_iterator I
=C
->body_rbegin(), E
=C
->body_rend();
1170 // If we hit a segment of code just containing ';' (NullStmts), we can
1171 // get a null block back. In such cases, just use the LastBlock
1172 if (CFGBlock
*newBlock
= addStmt(*I
))
1173 LastBlock
= newBlock
;
1182 CFGBlock
*CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator
*C
,
1183 AddStmtChoice asc
) {
1184 const BinaryConditionalOperator
*BCO
= dyn_cast
<BinaryConditionalOperator
>(C
);
1185 const OpaqueValueExpr
*opaqueValue
= (BCO
? BCO
->getOpaqueValue() : NULL
);
1187 // Create the confluence block that will "merge" the results of the ternary
1189 CFGBlock
* ConfluenceBlock
= Block
? Block
: createBlock();
1190 appendStmt(ConfluenceBlock
, C
, asc
);
1194 AddStmtChoice alwaysAdd
= asc
.withAlwaysAdd(true);
1196 // Create a block for the LHS expression if there is an LHS expression. A
1197 // GCC extension allows LHS to be NULL, causing the condition to be the
1198 // value that is returned instead.
1199 // e.g: x ?: y is shorthand for: x ? x : y;
1200 Succ
= ConfluenceBlock
;
1202 CFGBlock
* LHSBlock
= 0;
1203 const Expr
*trueExpr
= C
->getTrueExpr();
1204 if (trueExpr
!= opaqueValue
) {
1205 LHSBlock
= Visit(C
->getTrueExpr(), alwaysAdd
);
1211 // Create the block for the RHS expression.
1212 Succ
= ConfluenceBlock
;
1213 CFGBlock
* RHSBlock
= Visit(C
->getFalseExpr(), alwaysAdd
);
1217 // Create the block that will contain the condition.
1218 Block
= createBlock(false);
1220 // See if this is a known constant.
1221 const TryResult
& KnownVal
= tryEvaluateBool(C
->getCond());
1223 addSuccessor(Block
, KnownVal
.isFalse() ? NULL
: LHSBlock
);
1224 addSuccessor(Block
, KnownVal
.isTrue() ? NULL
: RHSBlock
);
1225 Block
->setTerminator(C
);
1227 Expr
*condExpr
= C
->getCond();
1228 if (condExpr
!= opaqueValue
) result
= addStmt(condExpr
);
1229 if (BCO
) result
= addStmt(BCO
->getCommon());
1233 CFGBlock
*CFGBuilder::VisitDeclStmt(DeclStmt
*DS
) {
1234 if (DS
->isSingleDecl())
1235 return VisitDeclSubExpr(DS
);
1239 // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy.
1240 typedef llvm::SmallVector
<Decl
*,10> BufTy
;
1241 BufTy
Buf(DS
->decl_begin(), DS
->decl_end());
1243 for (BufTy::reverse_iterator I
= Buf
.rbegin(), E
= Buf
.rend(); I
!= E
; ++I
) {
1244 // Get the alignment of the new DeclStmt, padding out to >=8 bytes.
1245 unsigned A
= llvm::AlignOf
<DeclStmt
>::Alignment
< 8
1246 ? 8 : llvm::AlignOf
<DeclStmt
>::Alignment
;
1248 // Allocate the DeclStmt using the BumpPtrAllocator. It will get
1249 // automatically freed with the CFG.
1250 DeclGroupRef
DG(*I
);
1252 void *Mem
= cfg
->getAllocator().Allocate(sizeof(DeclStmt
), A
);
1253 DeclStmt
*DSNew
= new (Mem
) DeclStmt(DG
, D
->getLocation(), GetEndLoc(D
));
1255 // Append the fake DeclStmt to block.
1256 B
= VisitDeclSubExpr(DSNew
);
1262 /// VisitDeclSubExpr - Utility method to add block-level expressions for
1263 /// DeclStmts and initializers in them.
1264 CFGBlock
*CFGBuilder::VisitDeclSubExpr(DeclStmt
* DS
) {
1265 assert(DS
->isSingleDecl() && "Can handle single declarations only.");
1267 VarDecl
*VD
= dyn_cast
<VarDecl
>(DS
->getSingleDecl());
1271 appendStmt(Block
, DS
);
1275 bool IsReference
= false;
1276 bool HasTemporaries
= false;
1278 // Destructors of temporaries in initialization expression should be called
1279 // after initialization finishes.
1280 Expr
*Init
= VD
->getInit();
1282 IsReference
= VD
->getType()->isReferenceType();
1283 HasTemporaries
= isa
<ExprWithCleanups
>(Init
);
1285 if (BuildOpts
.AddImplicitDtors
&& HasTemporaries
) {
1286 // Generate destructors for temporaries in initialization expression.
1287 VisitForTemporaryDtors(cast
<ExprWithCleanups
>(Init
)->getSubExpr(),
1293 appendStmt(Block
, DS
);
1297 // For expression with temporaries go directly to subexpression to omit
1298 // generating destructors for the second time.
1299 Visit(cast
<ExprWithCleanups
>(Init
)->getSubExpr());
1304 // If the type of VD is a VLA, then we must process its size expressions.
1305 for (const VariableArrayType
* VA
= FindVA(VD
->getType().getTypePtr());
1306 VA
!= 0; VA
= FindVA(VA
->getElementType().getTypePtr()))
1307 Block
= addStmt(VA
->getSizeExpr());
1309 // Remove variable from local scope.
1310 if (ScopePos
&& VD
== *ScopePos
)
1316 CFGBlock
* CFGBuilder::VisitIfStmt(IfStmt
* I
) {
1317 // We may see an if statement in the middle of a basic block, or it may be the
1318 // first statement we are processing. In either case, we create a new basic
1319 // block. First, we create the blocks for the then...else statements, and
1320 // then we create the block containing the if statement. If we were in the
1321 // middle of a block, we stop processing that block. That block is then the
1322 // implicit successor for the "then" and "else" clauses.
1324 // Save local scope position because in case of condition variable ScopePos
1325 // won't be restored when traversing AST.
1326 SaveAndRestore
<LocalScope::const_iterator
> save_scope_pos(ScopePos
);
1328 // Create local scope for possible condition variable.
1329 // Store scope position. Add implicit destructor.
1330 if (VarDecl
* VD
= I
->getConditionVariable()) {
1331 LocalScope::const_iterator BeginScopePos
= ScopePos
;
1332 addLocalScopeForVarDecl(VD
);
1333 addAutomaticObjDtors(ScopePos
, BeginScopePos
, I
);
1336 // The block we were proccessing is now finished. Make it the successor
1344 // Process the false branch.
1345 CFGBlock
* ElseBlock
= Succ
;
1347 if (Stmt
* Else
= I
->getElse()) {
1348 SaveAndRestore
<CFGBlock
*> sv(Succ
);
1350 // NULL out Block so that the recursive call to Visit will
1351 // create a new basic block.
1354 // If branch is not a compound statement create implicit scope
1355 // and add destructors.
1356 if (!isa
<CompoundStmt
>(Else
))
1357 addLocalScopeAndDtors(Else
);
1359 ElseBlock
= addStmt(Else
);
1361 if (!ElseBlock
) // Can occur when the Else body has all NullStmts.
1362 ElseBlock
= sv
.get();
1369 // Process the true branch.
1370 CFGBlock
* ThenBlock
;
1372 Stmt
* Then
= I
->getThen();
1374 SaveAndRestore
<CFGBlock
*> sv(Succ
);
1377 // If branch is not a compound statement create implicit scope
1378 // and add destructors.
1379 if (!isa
<CompoundStmt
>(Then
))
1380 addLocalScopeAndDtors(Then
);
1382 ThenBlock
= addStmt(Then
);
1385 // We can reach here if the "then" body has all NullStmts.
1386 // Create an empty block so we can distinguish between true and false
1387 // branches in path-sensitive analyses.
1388 ThenBlock
= createBlock(false);
1389 addSuccessor(ThenBlock
, sv
.get());
1396 // Now create a new block containing the if statement.
1397 Block
= createBlock(false);
1399 // Set the terminator of the new block to the If statement.
1400 Block
->setTerminator(I
);
1402 // See if this is a known constant.
1403 const TryResult
&KnownVal
= tryEvaluateBool(I
->getCond());
1405 // Now add the successors.
1406 addSuccessor(Block
, KnownVal
.isFalse() ? NULL
: ThenBlock
);
1407 addSuccessor(Block
, KnownVal
.isTrue()? NULL
: ElseBlock
);
1409 // Add the condition as the last statement in the new block. This may create
1410 // new blocks as the condition may contain control-flow. Any newly created
1411 // blocks will be pointed to be "Block".
1412 Block
= addStmt(I
->getCond());
1414 // Finally, if the IfStmt contains a condition variable, add both the IfStmt
1415 // and the condition variable initialization to the CFG.
1416 if (VarDecl
*VD
= I
->getConditionVariable()) {
1417 if (Expr
*Init
= VD
->getInit()) {
1419 appendStmt(Block
, I
, AddStmtChoice::AlwaysAdd
);
1428 CFGBlock
* CFGBuilder::VisitReturnStmt(ReturnStmt
* R
) {
1429 // If we were in the middle of a block we stop processing that block.
1431 // NOTE: If a "return" appears in the middle of a block, this means that the
1432 // code afterwards is DEAD (unreachable). We still keep a basic block
1433 // for that code; a simple "mark-and-sweep" from the entry block will be
1434 // able to report such dead blocks.
1436 // Create the new block.
1437 Block
= createBlock(false);
1439 // The Exit block is the only successor.
1440 addAutomaticObjDtors(ScopePos
, LocalScope::const_iterator(), R
);
1441 addSuccessor(Block
, &cfg
->getExit());
1443 // Add the return statement to the block. This may create new blocks if R
1444 // contains control-flow (short-circuit operations).
1445 return VisitStmt(R
, AddStmtChoice::AlwaysAdd
);
1448 CFGBlock
* CFGBuilder::VisitLabelStmt(LabelStmt
*L
) {
1449 // Get the block of the labeled statement. Add it to our map.
1450 addStmt(L
->getSubStmt());
1451 CFGBlock
*LabelBlock
= Block
;
1453 if (!LabelBlock
) // This can happen when the body is empty, i.e.
1454 LabelBlock
= createBlock(); // scopes that only contains NullStmts.
1456 assert(LabelMap
.find(L
->getDecl()) == LabelMap
.end() &&
1457 "label already in map");
1458 LabelMap
[L
->getDecl()] = JumpTarget(LabelBlock
, ScopePos
);
1460 // Labels partition blocks, so this is the end of the basic block we were
1461 // processing (L is the block's label). Because this is label (and we have
1462 // already processed the substatement) there is no extra control-flow to worry
1464 LabelBlock
->setLabel(L
);
1468 // We set Block to NULL to allow lazy creation of a new block (if necessary);
1471 // This block is now the implicit successor of other blocks.
1477 CFGBlock
* CFGBuilder::VisitGotoStmt(GotoStmt
* G
) {
1478 // Goto is a control-flow statement. Thus we stop processing the current
1479 // block and create a new one.
1481 Block
= createBlock(false);
1482 Block
->setTerminator(G
);
1484 // If we already know the mapping to the label block add the successor now.
1485 LabelMapTy::iterator I
= LabelMap
.find(G
->getLabel());
1487 if (I
== LabelMap
.end())
1488 // We will need to backpatch this block later.
1489 BackpatchBlocks
.push_back(JumpSource(Block
, ScopePos
));
1491 JumpTarget JT
= I
->second
;
1492 addAutomaticObjDtors(ScopePos
, JT
.scopePosition
, G
);
1493 addSuccessor(Block
, JT
.block
);
1499 CFGBlock
* CFGBuilder::VisitForStmt(ForStmt
* F
) {
1500 CFGBlock
* LoopSuccessor
= NULL
;
1502 // Save local scope position because in case of condition variable ScopePos
1503 // won't be restored when traversing AST.
1504 SaveAndRestore
<LocalScope::const_iterator
> save_scope_pos(ScopePos
);
1506 // Create local scope for init statement and possible condition variable.
1507 // Add destructor for init statement and condition variable.
1508 // Store scope position for continue statement.
1509 if (Stmt
* Init
= F
->getInit())
1510 addLocalScopeForStmt(Init
);
1511 LocalScope::const_iterator LoopBeginScopePos
= ScopePos
;
1513 if (VarDecl
* VD
= F
->getConditionVariable())
1514 addLocalScopeForVarDecl(VD
);
1515 LocalScope::const_iterator ContinueScopePos
= ScopePos
;
1517 addAutomaticObjDtors(ScopePos
, save_scope_pos
.get(), F
);
1519 // "for" is a control-flow statement. Thus we stop processing the current
1524 LoopSuccessor
= Block
;
1526 LoopSuccessor
= Succ
;
1528 // Save the current value for the break targets.
1529 // All breaks should go to the code following the loop.
1530 SaveAndRestore
<JumpTarget
> save_break(BreakJumpTarget
);
1531 BreakJumpTarget
= JumpTarget(LoopSuccessor
, ScopePos
);
1533 // Because of short-circuit evaluation, the condition of the loop can span
1534 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
1535 // evaluate the condition.
1536 CFGBlock
* ExitConditionBlock
= createBlock(false);
1537 CFGBlock
* EntryConditionBlock
= ExitConditionBlock
;
1539 // Set the terminator for the "exit" condition block.
1540 ExitConditionBlock
->setTerminator(F
);
1542 // Now add the actual condition to the condition block. Because the condition
1543 // itself may contain control-flow, new blocks may be created.
1544 if (Stmt
* C
= F
->getCond()) {
1545 Block
= ExitConditionBlock
;
1546 EntryConditionBlock
= addStmt(C
);
1549 assert(Block
== EntryConditionBlock
||
1550 (Block
== 0 && EntryConditionBlock
== Succ
));
1552 // If this block contains a condition variable, add both the condition
1553 // variable and initializer to the CFG.
1554 if (VarDecl
*VD
= F
->getConditionVariable()) {
1555 if (Expr
*Init
= VD
->getInit()) {
1557 appendStmt(Block
, F
, AddStmtChoice::AlwaysAdd
);
1558 EntryConditionBlock
= addStmt(Init
);
1559 assert(Block
== EntryConditionBlock
);
1569 // The condition block is the implicit successor for the loop body as well as
1570 // any code above the loop.
1571 Succ
= EntryConditionBlock
;
1573 // See if this is a known constant.
1574 TryResult
KnownVal(true);
1577 KnownVal
= tryEvaluateBool(F
->getCond());
1579 // Now create the loop body.
1581 assert(F
->getBody());
1583 // Save the current values for Block, Succ, and continue targets.
1584 SaveAndRestore
<CFGBlock
*> save_Block(Block
), save_Succ(Succ
);
1585 SaveAndRestore
<JumpTarget
> save_continue(ContinueJumpTarget
);
1587 // Create a new block to contain the (bottom) of the loop body.
1590 // Loop body should end with destructor of Condition variable (if any).
1591 addAutomaticObjDtors(ScopePos
, LoopBeginScopePos
, F
);
1593 if (Stmt
* I
= F
->getInc()) {
1594 // Generate increment code in its own basic block. This is the target of
1595 // continue statements.
1598 // No increment code. Create a special, empty, block that is used as the
1599 // target block for "looping back" to the start of the loop.
1600 assert(Succ
== EntryConditionBlock
);
1601 Succ
= Block
? Block
: createBlock();
1604 // Finish up the increment (or empty) block if it hasn't been already.
1606 assert(Block
== Succ
);
1612 ContinueJumpTarget
= JumpTarget(Succ
, ContinueScopePos
);
1614 // The starting block for the loop increment is the block that should
1615 // represent the 'loop target' for looping back to the start of the loop.
1616 ContinueJumpTarget
.block
->setLoopTarget(F
);
1618 // If body is not a compound statement create implicit scope
1619 // and add destructors.
1620 if (!isa
<CompoundStmt
>(F
->getBody()))
1621 addLocalScopeAndDtors(F
->getBody());
1623 // Now populate the body block, and in the process create new blocks as we
1624 // walk the body of the loop.
1625 CFGBlock
* BodyBlock
= addStmt(F
->getBody());
1628 BodyBlock
= ContinueJumpTarget
.block
;//can happen for "for (...;...;...);"
1632 // This new body block is a successor to our "exit" condition block.
1633 addSuccessor(ExitConditionBlock
, KnownVal
.isFalse() ? NULL
: BodyBlock
);
1636 // Link up the condition block with the code that follows the loop. (the
1638 addSuccessor(ExitConditionBlock
, KnownVal
.isTrue() ? NULL
: LoopSuccessor
);
1640 // If the loop contains initialization, create a new block for those
1641 // statements. This block can also contain statements that precede the loop.
1642 if (Stmt
* I
= F
->getInit()) {
1643 Block
= createBlock();
1647 // There is no loop initialization. We are thus basically a while loop.
1648 // NULL out Block to force lazy block construction.
1650 Succ
= EntryConditionBlock
;
1651 return EntryConditionBlock
;
1654 CFGBlock
*CFGBuilder::VisitMemberExpr(MemberExpr
*M
, AddStmtChoice asc
) {
1655 if (asc
.alwaysAdd()) {
1657 appendStmt(Block
, M
, asc
);
1659 return Visit(M
->getBase());
1662 CFGBlock
* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt
* S
) {
1663 // Objective-C fast enumeration 'for' statements:
1664 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC
1666 // for ( Type newVariable in collection_expression ) { statements }
1671 // 1. collection_expression
1672 // T. jump to loop_entry
1674 // 1. side-effects of element expression
1675 // 1. ObjCForCollectionStmt [performs binding to newVariable]
1676 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil]
1679 // T. jump to loop_entry
1685 // Type existingItem;
1686 // for ( existingItem in expression ) { statements }
1690 // the same with newVariable replaced with existingItem; the binding works
1691 // the same except that for one ObjCForCollectionStmt::getElement() returns
1692 // a DeclStmt and the other returns a DeclRefExpr.
1695 CFGBlock
* LoopSuccessor
= 0;
1700 LoopSuccessor
= Block
;
1703 LoopSuccessor
= Succ
;
1705 // Build the condition blocks.
1706 CFGBlock
* ExitConditionBlock
= createBlock(false);
1707 CFGBlock
* EntryConditionBlock
= ExitConditionBlock
;
1709 // Set the terminator for the "exit" condition block.
1710 ExitConditionBlock
->setTerminator(S
);
1712 // The last statement in the block should be the ObjCForCollectionStmt, which
1713 // performs the actual binding to 'element' and determines if there are any
1714 // more items in the collection.
1715 appendStmt(ExitConditionBlock
, S
);
1716 Block
= ExitConditionBlock
;
1718 // Walk the 'element' expression to see if there are any side-effects. We
1719 // generate new blocks as necesary. We DON'T add the statement by default to
1720 // the CFG unless it contains control-flow.
1721 EntryConditionBlock
= Visit(S
->getElement(), AddStmtChoice::NotAlwaysAdd
);
1728 // The condition block is the implicit successor for the loop body as well as
1729 // any code above the loop.
1730 Succ
= EntryConditionBlock
;
1732 // Now create the true branch.
1734 // Save the current values for Succ, continue and break targets.
1735 SaveAndRestore
<CFGBlock
*> save_Succ(Succ
);
1736 SaveAndRestore
<JumpTarget
> save_continue(ContinueJumpTarget
),
1737 save_break(BreakJumpTarget
);
1739 BreakJumpTarget
= JumpTarget(LoopSuccessor
, ScopePos
);
1740 ContinueJumpTarget
= JumpTarget(EntryConditionBlock
, ScopePos
);
1742 CFGBlock
* BodyBlock
= addStmt(S
->getBody());
1745 BodyBlock
= EntryConditionBlock
; // can happen for "for (X in Y) ;"
1751 // This new body block is a successor to our "exit" condition block.
1752 addSuccessor(ExitConditionBlock
, BodyBlock
);
1755 // Link up the condition block with the code that follows the loop.
1756 // (the false branch).
1757 addSuccessor(ExitConditionBlock
, LoopSuccessor
);
1759 // Now create a prologue block to contain the collection expression.
1760 Block
= createBlock();
1761 return addStmt(S
->getCollection());
1764 CFGBlock
* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt
* S
) {
1765 // FIXME: Add locking 'primitives' to CFG for @synchronized.
1768 CFGBlock
*SyncBlock
= addStmt(S
->getSynchBody());
1770 // The sync body starts its own basic block. This makes it a little easier
1771 // for diagnostic clients.
1780 // Add the @synchronized to the CFG.
1782 appendStmt(Block
, S
, AddStmtChoice::AlwaysAdd
);
1784 // Inline the sync expression.
1785 return addStmt(S
->getSynchExpr());
1788 CFGBlock
* CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt
* S
) {
1793 CFGBlock
* CFGBuilder::VisitWhileStmt(WhileStmt
* W
) {
1794 CFGBlock
* LoopSuccessor
= NULL
;
1796 // Save local scope position because in case of condition variable ScopePos
1797 // won't be restored when traversing AST.
1798 SaveAndRestore
<LocalScope::const_iterator
> save_scope_pos(ScopePos
);
1800 // Create local scope for possible condition variable.
1801 // Store scope position for continue statement.
1802 LocalScope::const_iterator LoopBeginScopePos
= ScopePos
;
1803 if (VarDecl
* VD
= W
->getConditionVariable()) {
1804 addLocalScopeForVarDecl(VD
);
1805 addAutomaticObjDtors(ScopePos
, LoopBeginScopePos
, W
);
1808 // "while" is a control-flow statement. Thus we stop processing the current
1813 LoopSuccessor
= Block
;
1815 LoopSuccessor
= Succ
;
1817 // Because of short-circuit evaluation, the condition of the loop can span
1818 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
1819 // evaluate the condition.
1820 CFGBlock
* ExitConditionBlock
= createBlock(false);
1821 CFGBlock
* EntryConditionBlock
= ExitConditionBlock
;
1823 // Set the terminator for the "exit" condition block.
1824 ExitConditionBlock
->setTerminator(W
);
1826 // Now add the actual condition to the condition block. Because the condition
1827 // itself may contain control-flow, new blocks may be created. Thus we update
1828 // "Succ" after adding the condition.
1829 if (Stmt
* C
= W
->getCond()) {
1830 Block
= ExitConditionBlock
;
1831 EntryConditionBlock
= addStmt(C
);
1832 // The condition might finish the current 'Block'.
1833 Block
= EntryConditionBlock
;
1835 // If this block contains a condition variable, add both the condition
1836 // variable and initializer to the CFG.
1837 if (VarDecl
*VD
= W
->getConditionVariable()) {
1838 if (Expr
*Init
= VD
->getInit()) {
1840 appendStmt(Block
, W
, AddStmtChoice::AlwaysAdd
);
1841 EntryConditionBlock
= addStmt(Init
);
1842 assert(Block
== EntryConditionBlock
);
1852 // The condition block is the implicit successor for the loop body as well as
1853 // any code above the loop.
1854 Succ
= EntryConditionBlock
;
1856 // See if this is a known constant.
1857 const TryResult
& KnownVal
= tryEvaluateBool(W
->getCond());
1859 // Process the loop body.
1861 assert(W
->getBody());
1863 // Save the current values for Block, Succ, and continue and break targets
1864 SaveAndRestore
<CFGBlock
*> save_Block(Block
), save_Succ(Succ
);
1865 SaveAndRestore
<JumpTarget
> save_continue(ContinueJumpTarget
),
1866 save_break(BreakJumpTarget
);
1868 // Create an empty block to represent the transition block for looping back
1869 // to the head of the loop.
1871 assert(Succ
== EntryConditionBlock
);
1872 Succ
= createBlock();
1873 Succ
->setLoopTarget(W
);
1874 ContinueJumpTarget
= JumpTarget(Succ
, LoopBeginScopePos
);
1876 // All breaks should go to the code following the loop.
1877 BreakJumpTarget
= JumpTarget(LoopSuccessor
, ScopePos
);
1879 // NULL out Block to force lazy instantiation of blocks for the body.
1882 // Loop body should end with destructor of Condition variable (if any).
1883 addAutomaticObjDtors(ScopePos
, LoopBeginScopePos
, W
);
1885 // If body is not a compound statement create implicit scope
1886 // and add destructors.
1887 if (!isa
<CompoundStmt
>(W
->getBody()))
1888 addLocalScopeAndDtors(W
->getBody());
1890 // Create the body. The returned block is the entry to the loop body.
1891 CFGBlock
* BodyBlock
= addStmt(W
->getBody());
1894 BodyBlock
= ContinueJumpTarget
.block
; // can happen for "while(...) ;"
1900 // Add the loop body entry as a successor to the condition.
1901 addSuccessor(ExitConditionBlock
, KnownVal
.isFalse() ? NULL
: BodyBlock
);
1904 // Link up the condition block with the code that follows the loop. (the
1906 addSuccessor(ExitConditionBlock
, KnownVal
.isTrue() ? NULL
: LoopSuccessor
);
1908 // There can be no more statements in the condition block since we loop back
1909 // to this block. NULL out Block to force lazy creation of another block.
1912 // Return the condition block, which is the dominating block for the loop.
1913 Succ
= EntryConditionBlock
;
1914 return EntryConditionBlock
;
1918 CFGBlock
*CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt
* S
) {
1919 // FIXME: For now we pretend that @catch and the code it contains does not
1924 CFGBlock
* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt
* S
) {
1925 // FIXME: This isn't complete. We basically treat @throw like a return
1928 // If we were in the middle of a block we stop processing that block.
1932 // Create the new block.
1933 Block
= createBlock(false);
1935 // The Exit block is the only successor.
1936 addSuccessor(Block
, &cfg
->getExit());
1938 // Add the statement to the block. This may create new blocks if S contains
1939 // control-flow (short-circuit operations).
1940 return VisitStmt(S
, AddStmtChoice::AlwaysAdd
);
1943 CFGBlock
* CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr
* T
) {
1944 // If we were in the middle of a block we stop processing that block.
1948 // Create the new block.
1949 Block
= createBlock(false);
1951 if (TryTerminatedBlock
)
1952 // The current try statement is the only successor.
1953 addSuccessor(Block
, TryTerminatedBlock
);
1955 // otherwise the Exit block is the only successor.
1956 addSuccessor(Block
, &cfg
->getExit());
1958 // Add the statement to the block. This may create new blocks if S contains
1959 // control-flow (short-circuit operations).
1960 return VisitStmt(T
, AddStmtChoice::AlwaysAdd
);
1963 CFGBlock
*CFGBuilder::VisitDoStmt(DoStmt
* D
) {
1964 CFGBlock
* LoopSuccessor
= NULL
;
1966 // "do...while" is a control-flow statement. Thus we stop processing the
1971 LoopSuccessor
= Block
;
1973 LoopSuccessor
= Succ
;
1975 // Because of short-circuit evaluation, the condition of the loop can span
1976 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
1977 // evaluate the condition.
1978 CFGBlock
* ExitConditionBlock
= createBlock(false);
1979 CFGBlock
* EntryConditionBlock
= ExitConditionBlock
;
1981 // Set the terminator for the "exit" condition block.
1982 ExitConditionBlock
->setTerminator(D
);
1984 // Now add the actual condition to the condition block. Because the condition
1985 // itself may contain control-flow, new blocks may be created.
1986 if (Stmt
* C
= D
->getCond()) {
1987 Block
= ExitConditionBlock
;
1988 EntryConditionBlock
= addStmt(C
);
1995 // The condition block is the implicit successor for the loop body.
1996 Succ
= EntryConditionBlock
;
1998 // See if this is a known constant.
1999 const TryResult
&KnownVal
= tryEvaluateBool(D
->getCond());
2001 // Process the loop body.
2002 CFGBlock
* BodyBlock
= NULL
;
2004 assert(D
->getBody());
2006 // Save the current values for Block, Succ, and continue and break targets
2007 SaveAndRestore
<CFGBlock
*> save_Block(Block
), save_Succ(Succ
);
2008 SaveAndRestore
<JumpTarget
> save_continue(ContinueJumpTarget
),
2009 save_break(BreakJumpTarget
);
2011 // All continues within this loop should go to the condition block
2012 ContinueJumpTarget
= JumpTarget(EntryConditionBlock
, ScopePos
);
2014 // All breaks should go to the code following the loop.
2015 BreakJumpTarget
= JumpTarget(LoopSuccessor
, ScopePos
);
2017 // NULL out Block to force lazy instantiation of blocks for the body.
2020 // If body is not a compound statement create implicit scope
2021 // and add destructors.
2022 if (!isa
<CompoundStmt
>(D
->getBody()))
2023 addLocalScopeAndDtors(D
->getBody());
2025 // Create the body. The returned block is the entry to the loop body.
2026 BodyBlock
= addStmt(D
->getBody());
2029 BodyBlock
= EntryConditionBlock
; // can happen for "do ; while(...)"
2035 if (!KnownVal
.isFalse()) {
2036 // Add an intermediate block between the BodyBlock and the
2037 // ExitConditionBlock to represent the "loop back" transition. Create an
2038 // empty block to represent the transition block for looping back to the
2039 // head of the loop.
2040 // FIXME: Can we do this more efficiently without adding another block?
2043 CFGBlock
*LoopBackBlock
= createBlock();
2044 LoopBackBlock
->setLoopTarget(D
);
2046 // Add the loop body entry as a successor to the condition.
2047 addSuccessor(ExitConditionBlock
, LoopBackBlock
);
2050 addSuccessor(ExitConditionBlock
, NULL
);
2053 // Link up the condition block with the code that follows the loop.
2054 // (the false branch).
2055 addSuccessor(ExitConditionBlock
, KnownVal
.isTrue() ? NULL
: LoopSuccessor
);
2057 // There can be no more statements in the body block(s) since we loop back to
2058 // the body. NULL out Block to force lazy creation of another block.
2061 // Return the loop body, which is the dominating block for the loop.
2066 CFGBlock
* CFGBuilder::VisitContinueStmt(ContinueStmt
* C
) {
2067 // "continue" is a control-flow statement. Thus we stop processing the
2072 // Now create a new block that ends with the continue statement.
2073 Block
= createBlock(false);
2074 Block
->setTerminator(C
);
2076 // If there is no target for the continue, then we are looking at an
2077 // incomplete AST. This means the CFG cannot be constructed.
2078 if (ContinueJumpTarget
.block
) {
2079 addAutomaticObjDtors(ScopePos
, ContinueJumpTarget
.scopePosition
, C
);
2080 addSuccessor(Block
, ContinueJumpTarget
.block
);
2087 CFGBlock
*CFGBuilder::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr
*E
,
2088 AddStmtChoice asc
) {
2090 if (asc
.alwaysAdd()) {
2092 appendStmt(Block
, E
);
2095 // VLA types have expressions that must be evaluated.
2096 if (E
->isArgumentType()) {
2097 for (const VariableArrayType
*VA
=FindVA(E
->getArgumentType().getTypePtr());
2098 VA
!= 0; VA
= FindVA(VA
->getElementType().getTypePtr()))
2099 addStmt(VA
->getSizeExpr());
2105 /// VisitStmtExpr - Utility method to handle (nested) statement
2106 /// expressions (a GCC extension).
2107 CFGBlock
* CFGBuilder::VisitStmtExpr(StmtExpr
*SE
, AddStmtChoice asc
) {
2108 if (asc
.alwaysAdd()) {
2110 appendStmt(Block
, SE
);
2112 return VisitCompoundStmt(SE
->getSubStmt());
2115 CFGBlock
* CFGBuilder::VisitSwitchStmt(SwitchStmt
* Terminator
) {
2116 // "switch" is a control-flow statement. Thus we stop processing the current
2118 CFGBlock
* SwitchSuccessor
= NULL
;
2120 // Save local scope position because in case of condition variable ScopePos
2121 // won't be restored when traversing AST.
2122 SaveAndRestore
<LocalScope::const_iterator
> save_scope_pos(ScopePos
);
2124 // Create local scope for possible condition variable.
2125 // Store scope position. Add implicit destructor.
2126 if (VarDecl
* VD
= Terminator
->getConditionVariable()) {
2127 LocalScope::const_iterator SwitchBeginScopePos
= ScopePos
;
2128 addLocalScopeForVarDecl(VD
);
2129 addAutomaticObjDtors(ScopePos
, SwitchBeginScopePos
, Terminator
);
2135 SwitchSuccessor
= Block
;
2136 } else SwitchSuccessor
= Succ
;
2138 // Save the current "switch" context.
2139 SaveAndRestore
<CFGBlock
*> save_switch(SwitchTerminatedBlock
),
2140 save_default(DefaultCaseBlock
);
2141 SaveAndRestore
<JumpTarget
> save_break(BreakJumpTarget
);
2143 // Set the "default" case to be the block after the switch statement. If the
2144 // switch statement contains a "default:", this value will be overwritten with
2145 // the block for that code.
2146 DefaultCaseBlock
= SwitchSuccessor
;
2148 // Create a new block that will contain the switch statement.
2149 SwitchTerminatedBlock
= createBlock(false);
2151 // Now process the switch body. The code after the switch is the implicit
2153 Succ
= SwitchSuccessor
;
2154 BreakJumpTarget
= JumpTarget(SwitchSuccessor
, ScopePos
);
2156 // When visiting the body, the case statements should automatically get linked
2157 // up to the switch. We also don't keep a pointer to the body, since all
2158 // control-flow from the switch goes to case/default statements.
2159 assert(Terminator
->getBody() && "switch must contain a non-NULL body");
2162 // If body is not a compound statement create implicit scope
2163 // and add destructors.
2164 if (!isa
<CompoundStmt
>(Terminator
->getBody()))
2165 addLocalScopeAndDtors(Terminator
->getBody());
2167 addStmt(Terminator
->getBody());
2173 // If we have no "default:" case, the default transition is to the code
2174 // following the switch body.
2175 addSuccessor(SwitchTerminatedBlock
, DefaultCaseBlock
);
2177 // Add the terminator and condition in the switch block.
2178 SwitchTerminatedBlock
->setTerminator(Terminator
);
2179 assert(Terminator
->getCond() && "switch condition must be non-NULL");
2180 Block
= SwitchTerminatedBlock
;
2181 Block
= addStmt(Terminator
->getCond());
2183 // Finally, if the SwitchStmt contains a condition variable, add both the
2184 // SwitchStmt and the condition variable initialization to the CFG.
2185 if (VarDecl
*VD
= Terminator
->getConditionVariable()) {
2186 if (Expr
*Init
= VD
->getInit()) {
2188 appendStmt(Block
, Terminator
, AddStmtChoice::AlwaysAdd
);
2196 CFGBlock
* CFGBuilder::VisitCaseStmt(CaseStmt
* CS
) {
2197 // CaseStmts are essentially labels, so they are the first statement in a
2199 CFGBlock
*TopBlock
= 0, *LastBlock
= 0;
2201 if (Stmt
*Sub
= CS
->getSubStmt()) {
2202 // For deeply nested chains of CaseStmts, instead of doing a recursion
2203 // (which can blow out the stack), manually unroll and create blocks
2205 while (isa
<CaseStmt
>(Sub
)) {
2206 CFGBlock
*currentBlock
= createBlock(false);
2207 currentBlock
->setLabel(CS
);
2210 addSuccessor(LastBlock
, currentBlock
);
2212 TopBlock
= currentBlock
;
2214 addSuccessor(SwitchTerminatedBlock
, currentBlock
);
2215 LastBlock
= currentBlock
;
2217 CS
= cast
<CaseStmt
>(Sub
);
2218 Sub
= CS
->getSubStmt();
2224 CFGBlock
* CaseBlock
= Block
;
2226 CaseBlock
= createBlock();
2228 // Cases statements partition blocks, so this is the top of the basic block we
2229 // were processing (the "case XXX:" is the label).
2230 CaseBlock
->setLabel(CS
);
2235 // Add this block to the list of successors for the block with the switch
2237 assert(SwitchTerminatedBlock
);
2238 addSuccessor(SwitchTerminatedBlock
, CaseBlock
);
2240 // We set Block to NULL to allow lazy creation of a new block (if necessary)
2244 addSuccessor(LastBlock
, CaseBlock
);
2247 // This block is now the implicit successor of other blocks.
2254 CFGBlock
* CFGBuilder::VisitDefaultStmt(DefaultStmt
* Terminator
) {
2255 if (Terminator
->getSubStmt())
2256 addStmt(Terminator
->getSubStmt());
2258 DefaultCaseBlock
= Block
;
2260 if (!DefaultCaseBlock
)
2261 DefaultCaseBlock
= createBlock();
2263 // Default statements partition blocks, so this is the top of the basic block
2264 // we were processing (the "default:" is the label).
2265 DefaultCaseBlock
->setLabel(Terminator
);
2270 // Unlike case statements, we don't add the default block to the successors
2271 // for the switch statement immediately. This is done when we finish
2272 // processing the switch statement. This allows for the default case
2273 // (including a fall-through to the code after the switch statement) to always
2274 // be the last successor of a switch-terminated block.
2276 // We set Block to NULL to allow lazy creation of a new block (if necessary)
2279 // This block is now the implicit successor of other blocks.
2280 Succ
= DefaultCaseBlock
;
2282 return DefaultCaseBlock
;
2285 CFGBlock
*CFGBuilder::VisitCXXTryStmt(CXXTryStmt
*Terminator
) {
2286 // "try"/"catch" is a control-flow statement. Thus we stop processing the
2288 CFGBlock
* TrySuccessor
= NULL
;
2293 TrySuccessor
= Block
;
2294 } else TrySuccessor
= Succ
;
2296 CFGBlock
*PrevTryTerminatedBlock
= TryTerminatedBlock
;
2298 // Create a new block that will contain the try statement.
2299 CFGBlock
*NewTryTerminatedBlock
= createBlock(false);
2300 // Add the terminator in the try block.
2301 NewTryTerminatedBlock
->setTerminator(Terminator
);
2303 bool HasCatchAll
= false;
2304 for (unsigned h
= 0; h
<Terminator
->getNumHandlers(); ++h
) {
2305 // The code after the try is the implicit successor.
2306 Succ
= TrySuccessor
;
2307 CXXCatchStmt
*CS
= Terminator
->getHandler(h
);
2308 if (CS
->getExceptionDecl() == 0) {
2312 CFGBlock
*CatchBlock
= VisitCXXCatchStmt(CS
);
2313 if (CatchBlock
== 0)
2315 // Add this block to the list of successors for the block with the try
2317 addSuccessor(NewTryTerminatedBlock
, CatchBlock
);
2320 if (PrevTryTerminatedBlock
)
2321 addSuccessor(NewTryTerminatedBlock
, PrevTryTerminatedBlock
);
2323 addSuccessor(NewTryTerminatedBlock
, &cfg
->getExit());
2326 // The code after the try is the implicit successor.
2327 Succ
= TrySuccessor
;
2329 // Save the current "try" context.
2330 SaveAndRestore
<CFGBlock
*> save_try(TryTerminatedBlock
);
2331 TryTerminatedBlock
= NewTryTerminatedBlock
;
2333 assert(Terminator
->getTryBlock() && "try must contain a non-NULL body");
2335 Block
= addStmt(Terminator
->getTryBlock());
2339 CFGBlock
* CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt
* CS
) {
2340 // CXXCatchStmt are treated like labels, so they are the first statement in a
2343 // Save local scope position because in case of exception variable ScopePos
2344 // won't be restored when traversing AST.
2345 SaveAndRestore
<LocalScope::const_iterator
> save_scope_pos(ScopePos
);
2347 // Create local scope for possible exception variable.
2348 // Store scope position. Add implicit destructor.
2349 if (VarDecl
* VD
= CS
->getExceptionDecl()) {
2350 LocalScope::const_iterator BeginScopePos
= ScopePos
;
2351 addLocalScopeForVarDecl(VD
);
2352 addAutomaticObjDtors(ScopePos
, BeginScopePos
, CS
);
2355 if (CS
->getHandlerBlock())
2356 addStmt(CS
->getHandlerBlock());
2358 CFGBlock
* CatchBlock
= Block
;
2360 CatchBlock
= createBlock();
2362 CatchBlock
->setLabel(CS
);
2367 // We set Block to NULL to allow lazy creation of a new block (if necessary)
2373 CFGBlock
*CFGBuilder::VisitExprWithCleanups(ExprWithCleanups
*E
,
2374 AddStmtChoice asc
) {
2375 if (BuildOpts
.AddImplicitDtors
) {
2376 // If adding implicit destructors visit the full expression for adding
2377 // destructors of temporaries.
2378 VisitForTemporaryDtors(E
->getSubExpr());
2380 // Full expression has to be added as CFGStmt so it will be sequenced
2381 // before destructors of it's temporaries.
2382 asc
= asc
.withAlwaysAdd(true);
2384 return Visit(E
->getSubExpr(), asc
);
2387 CFGBlock
*CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr
*E
,
2388 AddStmtChoice asc
) {
2389 if (asc
.alwaysAdd()) {
2391 appendStmt(Block
, E
, asc
);
2393 // We do not want to propagate the AlwaysAdd property.
2394 asc
= asc
.withAlwaysAdd(false);
2396 return Visit(E
->getSubExpr(), asc
);
2399 CFGBlock
*CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr
*C
,
2400 AddStmtChoice asc
) {
2402 if (!C
->isElidable())
2403 appendStmt(Block
, C
, asc
.withAlwaysAdd(true));
2405 return VisitChildren(C
);
2408 CFGBlock
*CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr
*E
,
2409 AddStmtChoice asc
) {
2410 if (asc
.alwaysAdd()) {
2412 appendStmt(Block
, E
, asc
);
2413 // We do not want to propagate the AlwaysAdd property.
2414 asc
= asc
.withAlwaysAdd(false);
2416 return Visit(E
->getSubExpr(), asc
);
2419 CFGBlock
*CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr
*C
,
2420 AddStmtChoice asc
) {
2422 appendStmt(Block
, C
, asc
.withAlwaysAdd(true));
2423 return VisitChildren(C
);
2426 CFGBlock
*CFGBuilder::VisitCXXMemberCallExpr(CXXMemberCallExpr
*C
,
2427 AddStmtChoice asc
) {
2429 appendStmt(Block
, C
, asc
.withAlwaysAdd(true));
2430 return VisitChildren(C
);
2433 CFGBlock
*CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr
*E
,
2434 AddStmtChoice asc
) {
2435 if (asc
.alwaysAdd()) {
2437 appendStmt(Block
, E
, asc
);
2439 return Visit(E
->getSubExpr(), AddStmtChoice());
2442 CFGBlock
* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt
* I
) {
2443 // Lazily create the indirect-goto dispatch block if there isn't one already.
2444 CFGBlock
* IBlock
= cfg
->getIndirectGotoBlock();
2447 IBlock
= createBlock(false);
2448 cfg
->setIndirectGotoBlock(IBlock
);
2451 // IndirectGoto is a control-flow statement. Thus we stop processing the
2452 // current block and create a new one.
2456 Block
= createBlock(false);
2457 Block
->setTerminator(I
);
2458 addSuccessor(Block
, IBlock
);
2459 return addStmt(I
->getTarget());
2462 CFGBlock
*CFGBuilder::VisitForTemporaryDtors(Stmt
*E
, bool BindToTemporary
) {
2468 switch (E
->getStmtClass()) {
2470 return VisitChildrenForTemporaryDtors(E
);
2472 case Stmt::BinaryOperatorClass
:
2473 return VisitBinaryOperatorForTemporaryDtors(cast
<BinaryOperator
>(E
));
2475 case Stmt::CXXBindTemporaryExprClass
:
2476 return VisitCXXBindTemporaryExprForTemporaryDtors(
2477 cast
<CXXBindTemporaryExpr
>(E
), BindToTemporary
);
2479 case Stmt::BinaryConditionalOperatorClass
:
2480 case Stmt::ConditionalOperatorClass
:
2481 return VisitConditionalOperatorForTemporaryDtors(
2482 cast
<AbstractConditionalOperator
>(E
), BindToTemporary
);
2484 case Stmt::ImplicitCastExprClass
:
2485 // For implicit cast we want BindToTemporary to be passed further.
2486 E
= cast
<CastExpr
>(E
)->getSubExpr();
2489 case Stmt::ParenExprClass
:
2490 E
= cast
<ParenExpr
>(E
)->getSubExpr();
2495 CFGBlock
*CFGBuilder::VisitChildrenForTemporaryDtors(Stmt
*E
) {
2496 // When visiting children for destructors we want to visit them in reverse
2497 // order. Because there's no reverse iterator for children must to reverse
2498 // them in helper vector.
2499 typedef llvm::SmallVector
<Stmt
*, 4> ChildrenVect
;
2500 ChildrenVect ChildrenRev
;
2501 for (Stmt::child_range I
= E
->children(); I
; ++I
) {
2502 if (*I
) ChildrenRev
.push_back(*I
);
2505 CFGBlock
*B
= Block
;
2506 for (ChildrenVect::reverse_iterator I
= ChildrenRev
.rbegin(),
2507 L
= ChildrenRev
.rend(); I
!= L
; ++I
) {
2508 if (CFGBlock
*R
= VisitForTemporaryDtors(*I
))
2514 CFGBlock
*CFGBuilder::VisitBinaryOperatorForTemporaryDtors(BinaryOperator
*E
) {
2515 if (E
->isLogicalOp()) {
2516 // Destructors for temporaries in LHS expression should be called after
2517 // those for RHS expression. Even if this will unnecessarily create a block,
2518 // this block will be used at least by the full expression.
2520 CFGBlock
*ConfluenceBlock
= VisitForTemporaryDtors(E
->getLHS());
2524 Succ
= ConfluenceBlock
;
2526 CFGBlock
*RHSBlock
= VisitForTemporaryDtors(E
->getRHS());
2532 // If RHS expression did produce destructors we need to connect created
2533 // blocks to CFG in same manner as for binary operator itself.
2534 CFGBlock
*LHSBlock
= createBlock(false);
2535 LHSBlock
->setTerminator(CFGTerminator(E
, true));
2537 // For binary operator LHS block is before RHS in list of predecessors
2538 // of ConfluenceBlock.
2539 std::reverse(ConfluenceBlock
->pred_begin(),
2540 ConfluenceBlock
->pred_end());
2542 // See if this is a known constant.
2543 TryResult KnownVal
= tryEvaluateBool(E
->getLHS());
2544 if (KnownVal
.isKnown() && (E
->getOpcode() == BO_LOr
))
2547 // Link LHSBlock with RHSBlock exactly the same way as for binary operator
2549 if (E
->getOpcode() == BO_LOr
) {
2550 addSuccessor(LHSBlock
, KnownVal
.isTrue() ? NULL
: ConfluenceBlock
);
2551 addSuccessor(LHSBlock
, KnownVal
.isFalse() ? NULL
: RHSBlock
);
2553 assert (E
->getOpcode() == BO_LAnd
);
2554 addSuccessor(LHSBlock
, KnownVal
.isFalse() ? NULL
: RHSBlock
);
2555 addSuccessor(LHSBlock
, KnownVal
.isTrue() ? NULL
: ConfluenceBlock
);
2562 Block
= ConfluenceBlock
;
2563 return ConfluenceBlock
;
2566 if (E
->isAssignmentOp()) {
2567 // For assignment operator (=) LHS expression is visited
2568 // before RHS expression. For destructors visit them in reverse order.
2569 CFGBlock
*RHSBlock
= VisitForTemporaryDtors(E
->getRHS());
2570 CFGBlock
*LHSBlock
= VisitForTemporaryDtors(E
->getLHS());
2571 return LHSBlock
? LHSBlock
: RHSBlock
;
2574 // For any other binary operator RHS expression is visited before
2575 // LHS expression (order of children). For destructors visit them in reverse
2577 CFGBlock
*LHSBlock
= VisitForTemporaryDtors(E
->getLHS());
2578 CFGBlock
*RHSBlock
= VisitForTemporaryDtors(E
->getRHS());
2579 return RHSBlock
? RHSBlock
: LHSBlock
;
2582 CFGBlock
*CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors(
2583 CXXBindTemporaryExpr
*E
, bool BindToTemporary
) {
2584 // First add destructors for temporaries in subexpression.
2585 CFGBlock
*B
= VisitForTemporaryDtors(E
->getSubExpr());
2586 if (!BindToTemporary
) {
2587 // If lifetime of temporary is not prolonged (by assigning to constant
2588 // reference) add destructor for it.
2590 appendTemporaryDtor(Block
, E
);
2596 CFGBlock
*CFGBuilder::VisitConditionalOperatorForTemporaryDtors(
2597 AbstractConditionalOperator
*E
, bool BindToTemporary
) {
2598 // First add destructors for condition expression. Even if this will
2599 // unnecessarily create a block, this block will be used at least by the full
2602 CFGBlock
*ConfluenceBlock
= VisitForTemporaryDtors(E
->getCond());
2605 if (BinaryConditionalOperator
*BCO
2606 = dyn_cast
<BinaryConditionalOperator
>(E
)) {
2607 ConfluenceBlock
= VisitForTemporaryDtors(BCO
->getCommon());
2612 // Try to add block with destructors for LHS expression.
2613 CFGBlock
*LHSBlock
= NULL
;
2614 Succ
= ConfluenceBlock
;
2616 LHSBlock
= VisitForTemporaryDtors(E
->getTrueExpr(), BindToTemporary
);
2620 // Try to add block with destructors for RHS expression;
2621 Succ
= ConfluenceBlock
;
2623 CFGBlock
*RHSBlock
= VisitForTemporaryDtors(E
->getFalseExpr(),
2628 if (!RHSBlock
&& !LHSBlock
) {
2629 // If neither LHS nor RHS expression had temporaries to destroy don't create
2631 Block
= ConfluenceBlock
;
2635 Block
= createBlock(false);
2636 Block
->setTerminator(CFGTerminator(E
, true));
2638 // See if this is a known constant.
2639 const TryResult
&KnownVal
= tryEvaluateBool(E
->getCond());
2642 addSuccessor(Block
, KnownVal
.isFalse() ? NULL
: LHSBlock
);
2643 } else if (KnownVal
.isFalse()) {
2644 addSuccessor(Block
, NULL
);
2646 addSuccessor(Block
, ConfluenceBlock
);
2647 std::reverse(ConfluenceBlock
->pred_begin(), ConfluenceBlock
->pred_end());
2651 RHSBlock
= ConfluenceBlock
;
2652 addSuccessor(Block
, KnownVal
.isTrue() ? NULL
: RHSBlock
);
2657 } // end anonymous namespace
2659 /// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has
2660 /// no successors or predecessors. If this is the first block created in the
2661 /// CFG, it is automatically set to be the Entry and Exit of the CFG.
2662 CFGBlock
* CFG::createBlock() {
2663 bool first_block
= begin() == end();
2665 // Create the block.
2666 CFGBlock
*Mem
= getAllocator().Allocate
<CFGBlock
>();
2667 new (Mem
) CFGBlock(NumBlockIDs
++, BlkBVC
);
2668 Blocks
.push_back(Mem
, BlkBVC
);
2670 // If this is the first block, set it as the Entry and Exit.
2672 Entry
= Exit
= &back();
2674 // Return the block.
2678 /// buildCFG - Constructs a CFG from an AST. Ownership of the returned
2679 /// CFG is returned to the caller.
2680 CFG
* CFG::buildCFG(const Decl
*D
, Stmt
* Statement
, ASTContext
*C
,
2683 return Builder
.buildCFG(D
, Statement
, C
, BO
);
2686 //===----------------------------------------------------------------------===//
2687 // CFG: Queries for BlkExprs.
2688 //===----------------------------------------------------------------------===//
2691 typedef llvm::DenseMap
<const Stmt
*,unsigned> BlkExprMapTy
;
2694 static void FindSubExprAssignments(Stmt
*S
,
2695 llvm::SmallPtrSet
<Expr
*,50>& Set
) {
2699 for (Stmt::child_range I
= S
->children(); I
; ++I
) {
2704 if (BinaryOperator
* B
= dyn_cast
<BinaryOperator
>(child
))
2705 if (B
->isAssignmentOp()) Set
.insert(B
);
2707 FindSubExprAssignments(child
, Set
);
2711 static BlkExprMapTy
* PopulateBlkExprMap(CFG
& cfg
) {
2712 BlkExprMapTy
* M
= new BlkExprMapTy();
2714 // Look for assignments that are used as subexpressions. These are the only
2715 // assignments that we want to *possibly* register as a block-level
2716 // expression. Basically, if an assignment occurs both in a subexpression and
2717 // at the block-level, it is a block-level expression.
2718 llvm::SmallPtrSet
<Expr
*,50> SubExprAssignments
;
2720 for (CFG::iterator I
=cfg
.begin(), E
=cfg
.end(); I
!= E
; ++I
)
2721 for (CFGBlock::iterator BI
=(*I
)->begin(), EI
=(*I
)->end(); BI
!= EI
; ++BI
)
2722 if (CFGStmt S
= BI
->getAs
<CFGStmt
>())
2723 FindSubExprAssignments(S
, SubExprAssignments
);
2725 for (CFG::iterator I
=cfg
.begin(), E
=cfg
.end(); I
!= E
; ++I
) {
2727 // Iterate over the statements again on identify the Expr* and Stmt* at the
2728 // block-level that are block-level expressions.
2730 for (CFGBlock::iterator BI
=(*I
)->begin(), EI
=(*I
)->end(); BI
!= EI
; ++BI
) {
2731 CFGStmt CS
= BI
->getAs
<CFGStmt
>();
2734 if (Expr
* Exp
= dyn_cast
<Expr
>(CS
.getStmt())) {
2736 if (BinaryOperator
* B
= dyn_cast
<BinaryOperator
>(Exp
)) {
2737 // Assignment expressions that are not nested within another
2738 // expression are really "statements" whose value is never used by
2739 // another expression.
2740 if (B
->isAssignmentOp() && !SubExprAssignments
.count(Exp
))
2742 } else if (const StmtExpr
* Terminator
= dyn_cast
<StmtExpr
>(Exp
)) {
2743 // Special handling for statement expressions. The last statement in
2744 // the statement expression is also a block-level expr.
2745 const CompoundStmt
* C
= Terminator
->getSubStmt();
2746 if (!C
->body_empty()) {
2747 unsigned x
= M
->size();
2748 (*M
)[C
->body_back()] = x
;
2752 unsigned x
= M
->size();
2757 // Look at terminators. The condition is a block-level expression.
2759 Stmt
* S
= (*I
)->getTerminatorCondition();
2761 if (S
&& M
->find(S
) == M
->end()) {
2762 unsigned x
= M
->size();
2770 CFG::BlkExprNumTy
CFG::getBlkExprNum(const Stmt
* S
) {
2772 if (!BlkExprMap
) { BlkExprMap
= (void*) PopulateBlkExprMap(*this); }
2774 BlkExprMapTy
* M
= reinterpret_cast<BlkExprMapTy
*>(BlkExprMap
);
2775 BlkExprMapTy::iterator I
= M
->find(S
);
2776 return (I
== M
->end()) ? CFG::BlkExprNumTy() : CFG::BlkExprNumTy(I
->second
);
2779 unsigned CFG::getNumBlkExprs() {
2780 if (const BlkExprMapTy
* M
= reinterpret_cast<const BlkExprMapTy
*>(BlkExprMap
))
2783 // We assume callers interested in the number of BlkExprs will want
2784 // the map constructed if it doesn't already exist.
2785 BlkExprMap
= (void*) PopulateBlkExprMap(*this);
2786 return reinterpret_cast<BlkExprMapTy
*>(BlkExprMap
)->size();
2789 //===----------------------------------------------------------------------===//
2790 // Filtered walking of the CFG.
2791 //===----------------------------------------------------------------------===//
2793 bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions
&F
,
2794 const CFGBlock
*From
, const CFGBlock
*To
) {
2796 if (F
.IgnoreDefaultsWithCoveredEnums
) {
2797 // If the 'To' has no label or is labeled but the label isn't a
2798 // CaseStmt then filter this edge.
2799 if (const SwitchStmt
*S
=
2800 dyn_cast_or_null
<SwitchStmt
>(From
->getTerminator().getStmt())) {
2801 if (S
->isAllEnumCasesCovered()) {
2802 const Stmt
*L
= To
->getLabel();
2803 if (!L
|| !isa
<CaseStmt
>(L
))
2812 //===----------------------------------------------------------------------===//
2813 // Cleanup: CFG dstor.
2814 //===----------------------------------------------------------------------===//
2817 delete reinterpret_cast<const BlkExprMapTy
*>(BlkExprMap
);
2820 //===----------------------------------------------------------------------===//
2821 // CFG pretty printing
2822 //===----------------------------------------------------------------------===//
2826 class StmtPrinterHelper
: public PrinterHelper
{
2827 typedef llvm::DenseMap
<Stmt
*,std::pair
<unsigned,unsigned> > StmtMapTy
;
2828 typedef llvm::DenseMap
<Decl
*,std::pair
<unsigned,unsigned> > DeclMapTy
;
2831 signed currentBlock
;
2832 unsigned currentStmt
;
2833 const LangOptions
&LangOpts
;
2836 StmtPrinterHelper(const CFG
* cfg
, const LangOptions
&LO
)
2837 : currentBlock(0), currentStmt(0), LangOpts(LO
) {
2838 for (CFG::const_iterator I
= cfg
->begin(), E
= cfg
->end(); I
!= E
; ++I
) {
2840 for (CFGBlock::const_iterator BI
= (*I
)->begin(), BEnd
= (*I
)->end() ;
2841 BI
!= BEnd
; ++BI
, ++j
) {
2842 if (CFGStmt SE
= BI
->getAs
<CFGStmt
>()) {
2843 std::pair
<unsigned, unsigned> P((*I
)->getBlockID(), j
);
2846 if (DeclStmt
* DS
= dyn_cast
<DeclStmt
>(SE
.getStmt())) {
2847 DeclMap
[DS
->getSingleDecl()] = P
;
2849 } else if (IfStmt
* IS
= dyn_cast
<IfStmt
>(SE
.getStmt())) {
2850 if (VarDecl
* VD
= IS
->getConditionVariable())
2853 } else if (ForStmt
* FS
= dyn_cast
<ForStmt
>(SE
.getStmt())) {
2854 if (VarDecl
* VD
= FS
->getConditionVariable())
2857 } else if (WhileStmt
* WS
= dyn_cast
<WhileStmt
>(SE
.getStmt())) {
2858 if (VarDecl
* VD
= WS
->getConditionVariable())
2861 } else if (SwitchStmt
* SS
= dyn_cast
<SwitchStmt
>(SE
.getStmt())) {
2862 if (VarDecl
* VD
= SS
->getConditionVariable())
2865 } else if (CXXCatchStmt
* CS
= dyn_cast
<CXXCatchStmt
>(SE
.getStmt())) {
2866 if (VarDecl
* VD
= CS
->getExceptionDecl())
2874 virtual ~StmtPrinterHelper() {}
2876 const LangOptions
&getLangOpts() const { return LangOpts
; }
2877 void setBlockID(signed i
) { currentBlock
= i
; }
2878 void setStmtID(unsigned i
) { currentStmt
= i
; }
2880 virtual bool handledStmt(Stmt
* S
, llvm::raw_ostream
& OS
) {
2881 StmtMapTy::iterator I
= StmtMap
.find(S
);
2883 if (I
== StmtMap
.end())
2886 if (currentBlock
>= 0 && I
->second
.first
== (unsigned) currentBlock
2887 && I
->second
.second
== currentStmt
) {
2891 OS
<< "[B" << I
->second
.first
<< "." << I
->second
.second
<< "]";
2895 bool handleDecl(Decl
* D
, llvm::raw_ostream
& OS
) {
2896 DeclMapTy::iterator I
= DeclMap
.find(D
);
2898 if (I
== DeclMap
.end())
2901 if (currentBlock
>= 0 && I
->second
.first
== (unsigned) currentBlock
2902 && I
->second
.second
== currentStmt
) {
2906 OS
<< "[B" << I
->second
.first
<< "." << I
->second
.second
<< "]";
2910 } // end anonymous namespace
2914 class CFGBlockTerminatorPrint
2915 : public StmtVisitor
<CFGBlockTerminatorPrint
,void> {
2917 llvm::raw_ostream
& OS
;
2918 StmtPrinterHelper
* Helper
;
2919 PrintingPolicy Policy
;
2921 CFGBlockTerminatorPrint(llvm::raw_ostream
& os
, StmtPrinterHelper
* helper
,
2922 const PrintingPolicy
&Policy
)
2923 : OS(os
), Helper(helper
), Policy(Policy
) {}
2925 void VisitIfStmt(IfStmt
* I
) {
2927 I
->getCond()->printPretty(OS
,Helper
,Policy
);
2931 void VisitStmt(Stmt
* Terminator
) {
2932 Terminator
->printPretty(OS
, Helper
, Policy
);
2935 void VisitForStmt(ForStmt
* F
) {
2940 if (Stmt
* C
= F
->getCond())
2941 C
->printPretty(OS
, Helper
, Policy
);
2948 void VisitWhileStmt(WhileStmt
* W
) {
2950 if (Stmt
* C
= W
->getCond())
2951 C
->printPretty(OS
, Helper
, Policy
);
2954 void VisitDoStmt(DoStmt
* D
) {
2955 OS
<< "do ... while ";
2956 if (Stmt
* C
= D
->getCond())
2957 C
->printPretty(OS
, Helper
, Policy
);
2960 void VisitSwitchStmt(SwitchStmt
* Terminator
) {
2962 Terminator
->getCond()->printPretty(OS
, Helper
, Policy
);
2965 void VisitCXXTryStmt(CXXTryStmt
* CS
) {
2969 void VisitAbstractConditionalOperator(AbstractConditionalOperator
* C
) {
2970 C
->getCond()->printPretty(OS
, Helper
, Policy
);
2971 OS
<< " ? ... : ...";
2974 void VisitChooseExpr(ChooseExpr
* C
) {
2975 OS
<< "__builtin_choose_expr( ";
2976 C
->getCond()->printPretty(OS
, Helper
, Policy
);
2980 void VisitIndirectGotoStmt(IndirectGotoStmt
* I
) {
2982 I
->getTarget()->printPretty(OS
, Helper
, Policy
);
2985 void VisitBinaryOperator(BinaryOperator
* B
) {
2986 if (!B
->isLogicalOp()) {
2991 B
->getLHS()->printPretty(OS
, Helper
, Policy
);
2993 switch (B
->getOpcode()) {
3001 assert(false && "Invalid logical operator.");
3005 void VisitExpr(Expr
* E
) {
3006 E
->printPretty(OS
, Helper
, Policy
);
3009 } // end anonymous namespace
3011 static void print_elem(llvm::raw_ostream
&OS
, StmtPrinterHelper
* Helper
,
3012 const CFGElement
&E
) {
3013 if (CFGStmt CS
= E
.getAs
<CFGStmt
>()) {
3018 // special printing for statement-expressions.
3019 if (StmtExpr
* SE
= dyn_cast
<StmtExpr
>(S
)) {
3020 CompoundStmt
* Sub
= SE
->getSubStmt();
3022 if (Sub
->children()) {
3024 Helper
->handledStmt(*SE
->getSubStmt()->body_rbegin(),OS
);
3029 // special printing for comma expressions.
3030 if (BinaryOperator
* B
= dyn_cast
<BinaryOperator
>(S
)) {
3031 if (B
->getOpcode() == BO_Comma
) {
3033 Helper
->handledStmt(B
->getRHS(),OS
);
3039 S
->printPretty(OS
, Helper
, PrintingPolicy(Helper
->getLangOpts()));
3041 if (isa
<CXXOperatorCallExpr
>(S
)) {
3042 OS
<< " (OperatorCall)";
3043 } else if (isa
<CXXBindTemporaryExpr
>(S
)) {
3044 OS
<< " (BindTemporary)";
3047 // Expressions need a newline.
3051 } else if (CFGInitializer IE
= E
.getAs
<CFGInitializer
>()) {
3052 CXXCtorInitializer
* I
= IE
;
3053 if (I
->isBaseInitializer())
3054 OS
<< I
->getBaseClass()->getAsCXXRecordDecl()->getName();
3055 else OS
<< I
->getAnyMember()->getName();
3058 if (Expr
* IE
= I
->getInit())
3059 IE
->printPretty(OS
, Helper
, PrintingPolicy(Helper
->getLangOpts()));
3062 if (I
->isBaseInitializer())
3063 OS
<< " (Base initializer)\n";
3064 else OS
<< " (Member initializer)\n";
3066 } else if (CFGAutomaticObjDtor DE
= E
.getAs
<CFGAutomaticObjDtor
>()){
3067 VarDecl
* VD
= DE
.getVarDecl();
3068 Helper
->handleDecl(VD
, OS
);
3070 const Type
* T
= VD
->getType().getTypePtr();
3071 if (const ReferenceType
* RT
= T
->getAs
<ReferenceType
>())
3072 T
= RT
->getPointeeType().getTypePtr();
3073 else if (const Type
*ET
= T
->getArrayElementTypeNoTypeQual())
3076 OS
<< ".~" << T
->getAsCXXRecordDecl()->getName().str() << "()";
3077 OS
<< " (Implicit destructor)\n";
3079 } else if (CFGBaseDtor BE
= E
.getAs
<CFGBaseDtor
>()) {
3080 const CXXBaseSpecifier
*BS
= BE
.getBaseSpecifier();
3081 OS
<< "~" << BS
->getType()->getAsCXXRecordDecl()->getName() << "()";
3082 OS
<< " (Base object destructor)\n";
3084 } else if (CFGMemberDtor ME
= E
.getAs
<CFGMemberDtor
>()) {
3085 FieldDecl
*FD
= ME
.getFieldDecl();
3087 const Type
*T
= FD
->getType().getTypePtr();
3088 if (const Type
*ET
= T
->getArrayElementTypeNoTypeQual())
3091 OS
<< "this->" << FD
->getName();
3092 OS
<< ".~" << T
->getAsCXXRecordDecl()->getName() << "()";
3093 OS
<< " (Member object destructor)\n";
3095 } else if (CFGTemporaryDtor TE
= E
.getAs
<CFGTemporaryDtor
>()) {
3096 CXXBindTemporaryExpr
*BT
= TE
.getBindTemporaryExpr();
3097 OS
<< "~" << BT
->getType()->getAsCXXRecordDecl()->getName() << "()";
3098 OS
<< " (Temporary object destructor)\n";
3102 static void print_block(llvm::raw_ostream
& OS
, const CFG
* cfg
,
3104 StmtPrinterHelper
* Helper
, bool print_edges
) {
3106 if (Helper
) Helper
->setBlockID(B
.getBlockID());
3108 // Print the header.
3109 OS
<< "\n [ B" << B
.getBlockID();
3111 if (&B
== &cfg
->getEntry())
3112 OS
<< " (ENTRY) ]\n";
3113 else if (&B
== &cfg
->getExit())
3114 OS
<< " (EXIT) ]\n";
3115 else if (&B
== cfg
->getIndirectGotoBlock())
3116 OS
<< " (INDIRECT GOTO DISPATCH) ]\n";
3120 // Print the label of this block.
3121 if (Stmt
* Label
= const_cast<Stmt
*>(B
.getLabel())) {
3126 if (LabelStmt
* L
= dyn_cast
<LabelStmt
>(Label
))
3128 else if (CaseStmt
* C
= dyn_cast
<CaseStmt
>(Label
)) {
3130 C
->getLHS()->printPretty(OS
, Helper
,
3131 PrintingPolicy(Helper
->getLangOpts()));
3134 C
->getRHS()->printPretty(OS
, Helper
,
3135 PrintingPolicy(Helper
->getLangOpts()));
3137 } else if (isa
<DefaultStmt
>(Label
))
3139 else if (CXXCatchStmt
*CS
= dyn_cast
<CXXCatchStmt
>(Label
)) {
3141 if (CS
->getExceptionDecl())
3142 CS
->getExceptionDecl()->print(OS
, PrintingPolicy(Helper
->getLangOpts()),
3149 assert(false && "Invalid label statement in CFGBlock.");
3154 // Iterate through the statements in the block and print them.
3157 for (CFGBlock::const_iterator I
= B
.begin(), E
= B
.end() ;
3158 I
!= E
; ++I
, ++j
) {
3160 // Print the statement # in the basic block and the statement itself.
3164 OS
<< llvm::format("%3d", j
) << ": ";
3167 Helper
->setStmtID(j
);
3169 print_elem(OS
,Helper
,*I
);
3172 // Print the terminator of this block.
3173 if (B
.getTerminator()) {
3179 if (Helper
) Helper
->setBlockID(-1);
3181 CFGBlockTerminatorPrint
TPrinter(OS
, Helper
,
3182 PrintingPolicy(Helper
->getLangOpts()));
3183 TPrinter
.Visit(const_cast<Stmt
*>(B
.getTerminator().getStmt()));
3188 // Print the predecessors of this block.
3189 OS
<< " Predecessors (" << B
.pred_size() << "):";
3192 for (CFGBlock::const_pred_iterator I
= B
.pred_begin(), E
= B
.pred_end();
3195 if (i
== 8 || (i
-8) == 0)
3198 OS
<< " B" << (*I
)->getBlockID();
3203 // Print the successors of this block.
3204 OS
<< " Successors (" << B
.succ_size() << "):";
3207 for (CFGBlock::const_succ_iterator I
= B
.succ_begin(), E
= B
.succ_end();
3210 if (i
== 8 || (i
-8) % 10 == 0)
3214 OS
<< " B" << (*I
)->getBlockID();
3224 /// dump - A simple pretty printer of a CFG that outputs to stderr.
3225 void CFG::dump(const LangOptions
&LO
) const { print(llvm::errs(), LO
); }
3227 /// print - A simple pretty printer of a CFG that outputs to an ostream.
3228 void CFG::print(llvm::raw_ostream
&OS
, const LangOptions
&LO
) const {
3229 StmtPrinterHelper
Helper(this, LO
);
3231 // Print the entry block.
3232 print_block(OS
, this, getEntry(), &Helper
, true);
3234 // Iterate through the CFGBlocks and print them one by one.
3235 for (const_iterator I
= Blocks
.begin(), E
= Blocks
.end() ; I
!= E
; ++I
) {
3236 // Skip the entry block, because we already printed it.
3237 if (&(**I
) == &getEntry() || &(**I
) == &getExit())
3240 print_block(OS
, this, **I
, &Helper
, true);
3243 // Print the exit block.
3244 print_block(OS
, this, getExit(), &Helper
, true);
3248 /// dump - A simply pretty printer of a CFGBlock that outputs to stderr.
3249 void CFGBlock::dump(const CFG
* cfg
, const LangOptions
&LO
) const {
3250 print(llvm::errs(), cfg
, LO
);
3253 /// print - A simple pretty printer of a CFGBlock that outputs to an ostream.
3254 /// Generally this will only be called from CFG::print.
3255 void CFGBlock::print(llvm::raw_ostream
& OS
, const CFG
* cfg
,
3256 const LangOptions
&LO
) const {
3257 StmtPrinterHelper
Helper(cfg
, LO
);
3258 print_block(OS
, cfg
, *this, &Helper
, true);
3261 /// printTerminator - A simple pretty printer of the terminator of a CFGBlock.
3262 void CFGBlock::printTerminator(llvm::raw_ostream
&OS
,
3263 const LangOptions
&LO
) const {
3264 CFGBlockTerminatorPrint
TPrinter(OS
, NULL
, PrintingPolicy(LO
));
3265 TPrinter
.Visit(const_cast<Stmt
*>(getTerminator().getStmt()));
3268 Stmt
* CFGBlock::getTerminatorCondition() {
3269 Stmt
*Terminator
= this->Terminator
;
3275 switch (Terminator
->getStmtClass()) {
3279 case Stmt::ForStmtClass
:
3280 E
= cast
<ForStmt
>(Terminator
)->getCond();
3283 case Stmt::WhileStmtClass
:
3284 E
= cast
<WhileStmt
>(Terminator
)->getCond();
3287 case Stmt::DoStmtClass
:
3288 E
= cast
<DoStmt
>(Terminator
)->getCond();
3291 case Stmt::IfStmtClass
:
3292 E
= cast
<IfStmt
>(Terminator
)->getCond();
3295 case Stmt::ChooseExprClass
:
3296 E
= cast
<ChooseExpr
>(Terminator
)->getCond();
3299 case Stmt::IndirectGotoStmtClass
:
3300 E
= cast
<IndirectGotoStmt
>(Terminator
)->getTarget();
3303 case Stmt::SwitchStmtClass
:
3304 E
= cast
<SwitchStmt
>(Terminator
)->getCond();
3307 case Stmt::BinaryConditionalOperatorClass
:
3308 E
= cast
<BinaryConditionalOperator
>(Terminator
)->getCond();
3311 case Stmt::ConditionalOperatorClass
:
3312 E
= cast
<ConditionalOperator
>(Terminator
)->getCond();
3315 case Stmt::BinaryOperatorClass
: // '&&' and '||'
3316 E
= cast
<BinaryOperator
>(Terminator
)->getLHS();
3319 case Stmt::ObjCForCollectionStmtClass
:
3323 return E
? E
->IgnoreParens() : NULL
;
3326 bool CFGBlock::hasBinaryBranchTerminator() const {
3327 const Stmt
*Terminator
= this->Terminator
;
3333 switch (Terminator
->getStmtClass()) {
3337 case Stmt::ForStmtClass
:
3338 case Stmt::WhileStmtClass
:
3339 case Stmt::DoStmtClass
:
3340 case Stmt::IfStmtClass
:
3341 case Stmt::ChooseExprClass
:
3342 case Stmt::BinaryConditionalOperatorClass
:
3343 case Stmt::ConditionalOperatorClass
:
3344 case Stmt::BinaryOperatorClass
:
3348 return E
? E
->IgnoreParens() : NULL
;
3352 //===----------------------------------------------------------------------===//
3353 // CFG Graphviz Visualization
3354 //===----------------------------------------------------------------------===//
3358 static StmtPrinterHelper
* GraphHelper
;
3361 void CFG::viewCFG(const LangOptions
&LO
) const {
3363 StmtPrinterHelper
H(this, LO
);
3365 llvm::ViewGraph(this,"CFG");
3372 struct DOTGraphTraits
<const CFG
*> : public DefaultDOTGraphTraits
{
3374 DOTGraphTraits (bool isSimple
=false) : DefaultDOTGraphTraits(isSimple
) {}
3376 static std::string
getNodeLabel(const CFGBlock
* Node
, const CFG
* Graph
) {
3379 std::string OutSStr
;
3380 llvm::raw_string_ostream
Out(OutSStr
);
3381 print_block(Out
,Graph
, *Node
, GraphHelper
, false);
3382 std::string
& OutStr
= Out
.str();
3384 if (OutStr
[0] == '\n') OutStr
.erase(OutStr
.begin());
3386 // Process string output to make it nicer...
3387 for (unsigned i
= 0; i
!= OutStr
.length(); ++i
)
3388 if (OutStr
[i
] == '\n') { // Left justify
3390 OutStr
.insert(OutStr
.begin()+i
+1, 'l');
3399 } // end namespace llvm