blob: 4ccbf595a7401f3e60162d133c901b11584d91c2 [file] [log] [blame]
Ted Kremenekfddd5182007-08-21 21:42:03 +00001//===--- CFG.cpp - Classes for representing and building CFGs----*- C++ -*-===//
2//
3// The LLVM Compiler Infrastructure
4//
Chris Lattner0bc735f2007-12-29 19:59:25 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Ted Kremenekfddd5182007-08-21 21:42:03 +00007//
8//===----------------------------------------------------------------------===//
9//
10// This file defines the CFG and CFGBuilder classes for representing and
11// building Control-Flow Graphs (CFGs) from ASTs.
12//
13//===----------------------------------------------------------------------===//
14
Ted Kremenekbd048782009-07-22 21:45:16 +000015#include "clang/Analysis/Support/SaveAndRestore.h"
Ted Kremeneke41611a2009-07-16 18:13:04 +000016#include "clang/Analysis/CFG.h"
Mike Stumpb978a442010-01-21 02:21:40 +000017#include "clang/AST/DeclCXX.h"
Ted Kremenekc310e932007-08-21 22:06:14 +000018#include "clang/AST/StmtVisitor.h"
Ted Kremenek42a509f2007-08-31 21:30:12 +000019#include "clang/AST/PrettyPrinter.h"
Ted Kremenekc56c0042011-02-23 05:11:46 +000020#include "clang/AST/CharUnits.h"
Benjamin Kramer6cb7c1a2009-08-23 12:08:50 +000021#include "llvm/Support/GraphWriter.h"
Benjamin Kramer6cb7c1a2009-08-23 12:08:50 +000022#include "llvm/Support/Allocator.h"
23#include "llvm/Support/Format.h"
Ted Kremenek0cebe3e2007-08-21 23:26:17 +000024#include "llvm/ADT/DenseMap.h"
Ted Kremenek19bb3562007-08-28 19:26:49 +000025#include "llvm/ADT/SmallPtrSet.h"
Ted Kremenek0ba497b2009-10-20 23:46:25 +000026#include "llvm/ADT/OwningPtr.h"
Ted Kremenek83c01da2008-01-11 00:40:29 +000027
Ted Kremenekfddd5182007-08-21 21:42:03 +000028using namespace clang;
29
30namespace {
31
Ted Kremenek9c378f72011-08-12 23:37:29 +000032static SourceLocation GetEndLoc(Decl *D) {
33 if (VarDecl *VD = dyn_cast<VarDecl>(D))
34 if (Expr *Ex = VD->getInit())
Ted Kremenekc7eb9032008-08-06 23:20:50 +000035 return Ex->getSourceRange().getEnd();
Mike Stump6d9828c2009-07-17 01:31:16 +000036 return D->getLocation();
Ted Kremenekc7eb9032008-08-06 23:20:50 +000037}
Ted Kremenekad5a8942010-08-02 23:46:59 +000038
Ted Kremenek3179a452011-03-10 01:14:11 +000039class CFGBuilder;
40
Zhanyong Wan94a3dcf2010-11-24 03:28:53 +000041/// The CFG builder uses a recursive algorithm to build the CFG. When
42/// we process an expression, sometimes we know that we must add the
43/// subexpressions as block-level expressions. For example:
44///
45/// exp1 || exp2
46///
47/// When processing the '||' expression, we know that exp1 and exp2
48/// need to be added as block-level expressions, even though they
49/// might not normally need to be. AddStmtChoice records this
50/// contextual information. If AddStmtChoice is 'NotAlwaysAdd', then
51/// the builder has an option not to add a subexpression as a
52/// block-level expression.
53///
Ted Kremenek852274d2009-12-16 03:18:58 +000054class AddStmtChoice {
55public:
Ted Kremenek892697d2010-12-16 07:46:53 +000056 enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 };
Ted Kremenek5ba290a2010-03-02 21:43:54 +000057
Zhanyong Wan94a3dcf2010-11-24 03:28:53 +000058 AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {}
Ted Kremenek5ba290a2010-03-02 21:43:54 +000059
Ted Kremenek3179a452011-03-10 01:14:11 +000060 bool alwaysAdd(CFGBuilder &builder,
61 const Stmt *stmt) const;
Zhanyong Wan94a3dcf2010-11-24 03:28:53 +000062
63 /// Return a copy of this object, except with the 'always-add' bit
64 /// set as specified.
65 AddStmtChoice withAlwaysAdd(bool alwaysAdd) const {
Ted Kremenek3179a452011-03-10 01:14:11 +000066 return AddStmtChoice(alwaysAdd ? AlwaysAdd : NotAlwaysAdd);
Zhanyong Wan94a3dcf2010-11-24 03:28:53 +000067 }
68
Ted Kremenek852274d2009-12-16 03:18:58 +000069private:
Zhanyong Wan94a3dcf2010-11-24 03:28:53 +000070 Kind kind;
Ted Kremenek852274d2009-12-16 03:18:58 +000071};
Mike Stump6d9828c2009-07-17 01:31:16 +000072
Marcin Swiderskif1308c72010-09-25 11:05:21 +000073/// LocalScope - Node in tree of local scopes created for C++ implicit
74/// destructor calls generation. It contains list of automatic variables
75/// declared in the scope and link to position in previous scope this scope
76/// began in.
77///
78/// The process of creating local scopes is as follows:
79/// - Init CFGBuilder::ScopePos with invalid position (equivalent for null),
80/// - Before processing statements in scope (e.g. CompoundStmt) create
81/// LocalScope object using CFGBuilder::ScopePos as link to previous scope
82/// and set CFGBuilder::ScopePos to the end of new scope,
Marcin Swiderski35387a02010-09-30 22:42:32 +000083/// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points
Marcin Swiderskif1308c72010-09-25 11:05:21 +000084/// at this VarDecl,
85/// - For every normal (without jump) end of scope add to CFGBlock destructors
86/// for objects in the current scope,
87/// - For every jump add to CFGBlock destructors for objects
88/// between CFGBuilder::ScopePos and local scope position saved for jump
89/// target. Thanks to C++ restrictions on goto jumps we can be sure that
90/// jump target position will be on the path to root from CFGBuilder::ScopePos
91/// (adding any variable that doesn't need constructor to be called to
92/// LocalScope can break this assumption),
93///
94class LocalScope {
95public:
Ted Kremenekfe59b742011-02-15 02:47:45 +000096 typedef BumpVector<VarDecl*> AutomaticVarsTy;
Marcin Swiderskif1308c72010-09-25 11:05:21 +000097
98 /// const_iterator - Iterates local scope backwards and jumps to previous
Marcin Swiderski35387a02010-09-30 22:42:32 +000099 /// scope on reaching the beginning of currently iterated scope.
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000100 class const_iterator {
101 const LocalScope* Scope;
102
103 /// VarIter is guaranteed to be greater then 0 for every valid iterator.
104 /// Invalid iterator (with null Scope) has VarIter equal to 0.
105 unsigned VarIter;
106
107 public:
108 /// Create invalid iterator. Dereferencing invalid iterator is not allowed.
109 /// Incrementing invalid iterator is allowed and will result in invalid
110 /// iterator.
111 const_iterator()
112 : Scope(NULL), VarIter(0) {}
113
114 /// Create valid iterator. In case when S.Prev is an invalid iterator and
115 /// I is equal to 0, this will create invalid iterator.
116 const_iterator(const LocalScope& S, unsigned I)
117 : Scope(&S), VarIter(I) {
118 // Iterator to "end" of scope is not allowed. Handle it by going up
119 // in scopes tree possibly up to invalid iterator in the root.
120 if (VarIter == 0 && Scope)
121 *this = Scope->Prev;
122 }
123
Ted Kremenek9c378f72011-08-12 23:37:29 +0000124 VarDecl *const* operator->() const {
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000125 assert (Scope && "Dereferencing invalid iterator is not allowed");
126 assert (VarIter != 0 && "Iterator has invalid value of VarIter member");
127 return &Scope->Vars[VarIter - 1];
128 }
Ted Kremenek9c378f72011-08-12 23:37:29 +0000129 VarDecl *operator*() const {
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000130 return *this->operator->();
131 }
132
Ted Kremenek9c378f72011-08-12 23:37:29 +0000133 const_iterator &operator++() {
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000134 if (!Scope)
135 return *this;
136
137 assert (VarIter != 0 && "Iterator has invalid value of VarIter member");
138 --VarIter;
139 if (VarIter == 0)
140 *this = Scope->Prev;
141 return *this;
142 }
Marcin Swiderski35387a02010-09-30 22:42:32 +0000143 const_iterator operator++(int) {
144 const_iterator P = *this;
145 ++*this;
146 return P;
147 }
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000148
Ted Kremenek9c378f72011-08-12 23:37:29 +0000149 bool operator==(const const_iterator &rhs) const {
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000150 return Scope == rhs.Scope && VarIter == rhs.VarIter;
151 }
Ted Kremenek9c378f72011-08-12 23:37:29 +0000152 bool operator!=(const const_iterator &rhs) const {
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000153 return !(*this == rhs);
154 }
Marcin Swiderski35387a02010-09-30 22:42:32 +0000155
156 operator bool() const {
157 return *this != const_iterator();
158 }
159
160 int distance(const_iterator L);
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000161 };
162
163 friend class const_iterator;
164
165private:
Ted Kremenekfe59b742011-02-15 02:47:45 +0000166 BumpVectorContext ctx;
167
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000168 /// Automatic variables in order of declaration.
169 AutomaticVarsTy Vars;
170 /// Iterator to variable in previous scope that was declared just before
171 /// begin of this scope.
172 const_iterator Prev;
173
174public:
175 /// Constructs empty scope linked to previous scope in specified place.
Ted Kremenekfe59b742011-02-15 02:47:45 +0000176 LocalScope(BumpVectorContext &ctx, const_iterator P)
177 : ctx(ctx), Vars(ctx, 4), Prev(P) {}
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000178
179 /// Begin of scope in direction of CFG building (backwards).
180 const_iterator begin() const { return const_iterator(*this, Vars.size()); }
Marcin Swiderski35387a02010-09-30 22:42:32 +0000181
Ted Kremenek9c378f72011-08-12 23:37:29 +0000182 void addVar(VarDecl *VD) {
Ted Kremenekfe59b742011-02-15 02:47:45 +0000183 Vars.push_back(VD, ctx);
Marcin Swiderski35387a02010-09-30 22:42:32 +0000184 }
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000185};
186
Marcin Swiderski35387a02010-09-30 22:42:32 +0000187/// distance - Calculates distance from this to L. L must be reachable from this
188/// (with use of ++ operator). Cost of calculating the distance is linear w.r.t.
189/// number of scopes between this and L.
190int LocalScope::const_iterator::distance(LocalScope::const_iterator L) {
191 int D = 0;
192 const_iterator F = *this;
193 while (F.Scope != L.Scope) {
Ted Kremenek5290c802011-08-12 14:41:23 +0000194 assert (F != const_iterator()
195 && "L iterator is not reachable from F iterator.");
Marcin Swiderski35387a02010-09-30 22:42:32 +0000196 D += F.VarIter;
197 F = F.Scope->Prev;
198 }
199 D += F.VarIter - L.VarIter;
200 return D;
201}
202
203/// BlockScopePosPair - Structure for specifying position in CFG during its
204/// build process. It consists of CFGBlock that specifies position in CFG graph
205/// and LocalScope::const_iterator that specifies position in LocalScope graph.
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000206struct BlockScopePosPair {
Ted Kremenek9ce52702011-01-07 19:37:16 +0000207 BlockScopePosPair() : block(0) {}
Ted Kremenek9c378f72011-08-12 23:37:29 +0000208 BlockScopePosPair(CFGBlock *b, LocalScope::const_iterator scopePos)
Ted Kremenek9ce52702011-01-07 19:37:16 +0000209 : block(b), scopePosition(scopePos) {}
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000210
Ted Kremenek9ce52702011-01-07 19:37:16 +0000211 CFGBlock *block;
212 LocalScope::const_iterator scopePosition;
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000213};
214
Ted Kremeneke71f3d52011-03-01 23:12:55 +0000215/// TryResult - a class representing a variant over the values
216/// 'true', 'false', or 'unknown'. This is returned by tryEvaluateBool,
217/// and is used by the CFGBuilder to decide if a branch condition
218/// can be decided up front during CFG construction.
219class TryResult {
220 int X;
221public:
222 TryResult(bool b) : X(b ? 1 : 0) {}
223 TryResult() : X(-1) {}
224
225 bool isTrue() const { return X == 1; }
226 bool isFalse() const { return X == 0; }
227 bool isKnown() const { return X >= 0; }
228 void negate() {
229 assert(isKnown());
230 X ^= 0x1;
231 }
232};
233
Ted Kremeneka34ea072008-08-04 22:51:42 +0000234/// CFGBuilder - This class implements CFG construction from an AST.
Ted Kremenekfddd5182007-08-21 21:42:03 +0000235/// The builder is stateful: an instance of the builder should be used to only
236/// construct a single CFG.
237///
238/// Example usage:
239///
240/// CFGBuilder builder;
241/// CFG* cfg = builder.BuildAST(stmt1);
242///
Mike Stump6d9828c2009-07-17 01:31:16 +0000243/// CFG construction is done via a recursive walk of an AST. We actually parse
244/// the AST in reverse order so that the successor of a basic block is
245/// constructed prior to its predecessor. This allows us to nicely capture
246/// implicit fall-throughs without extra basic blocks.
Ted Kremenekc310e932007-08-21 22:06:14 +0000247///
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +0000248class CFGBuilder {
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000249 typedef BlockScopePosPair JumpTarget;
250 typedef BlockScopePosPair JumpSource;
251
Mike Stumpe5af3ce2009-07-20 23:24:15 +0000252 ASTContext *Context;
Ted Kremenek0ba497b2009-10-20 23:46:25 +0000253 llvm::OwningPtr<CFG> cfg;
Ted Kremenekee82d9b2009-10-12 20:55:07 +0000254
Ted Kremenek9c378f72011-08-12 23:37:29 +0000255 CFGBlock *Block;
256 CFGBlock *Succ;
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000257 JumpTarget ContinueJumpTarget;
258 JumpTarget BreakJumpTarget;
Ted Kremenek9c378f72011-08-12 23:37:29 +0000259 CFGBlock *SwitchTerminatedBlock;
260 CFGBlock *DefaultCaseBlock;
261 CFGBlock *TryTerminatedBlock;
Ted Kremeneke71f3d52011-03-01 23:12:55 +0000262
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000263 // Current position in local scope.
264 LocalScope::const_iterator ScopePos;
265
266 // LabelMap records the mapping from Label expressions to their jump targets.
Chris Lattnerad8dcf42011-02-17 07:39:24 +0000267 typedef llvm::DenseMap<LabelDecl*, JumpTarget> LabelMapTy;
Ted Kremenek0cebe3e2007-08-21 23:26:17 +0000268 LabelMapTy LabelMap;
Mike Stump6d9828c2009-07-17 01:31:16 +0000269
270 // A list of blocks that end with a "goto" that must be backpatched to their
271 // resolved targets upon completion of CFG construction.
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000272 typedef std::vector<JumpSource> BackpatchBlocksTy;
Ted Kremenek0cebe3e2007-08-21 23:26:17 +0000273 BackpatchBlocksTy BackpatchBlocks;
Mike Stump6d9828c2009-07-17 01:31:16 +0000274
Ted Kremenek19bb3562007-08-28 19:26:49 +0000275 // A list of labels whose address has been taken (for indirect gotos).
Chris Lattnerad8dcf42011-02-17 07:39:24 +0000276 typedef llvm::SmallPtrSet<LabelDecl*, 5> LabelSetTy;
Ted Kremenek19bb3562007-08-28 19:26:49 +0000277 LabelSetTy AddressTakenLabels;
Mike Stump6d9828c2009-07-17 01:31:16 +0000278
Zhongxing Xu49b4ef32010-09-16 03:28:18 +0000279 bool badCFG;
Ted Kremenekb8ad5ee2011-03-10 01:14:05 +0000280 const CFG::BuildOptions &BuildOpts;
Ted Kremeneke71f3d52011-03-01 23:12:55 +0000281
282 // State to track for building switch statements.
283 bool switchExclusivelyCovered;
Ted Kremenek04982472011-03-04 01:03:41 +0000284 Expr::EvalResult *switchCond;
Ted Kremenek0d28d362011-03-10 03:50:34 +0000285
286 CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry;
Ted Kremeneka8d459e2011-03-23 21:33:21 +0000287 const Stmt *lastLookup;
Zhongxing Xu49b4ef32010-09-16 03:28:18 +0000288
Mike Stump6d9828c2009-07-17 01:31:16 +0000289public:
Ted Kremenekb8ad5ee2011-03-10 01:14:05 +0000290 explicit CFGBuilder(ASTContext *astContext,
291 const CFG::BuildOptions &buildOpts)
292 : Context(astContext), cfg(new CFG()), // crew a new CFG
293 Block(NULL), Succ(NULL),
294 SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL),
295 TryTerminatedBlock(NULL), badCFG(false), BuildOpts(buildOpts),
Ted Kremenek0d28d362011-03-10 03:50:34 +0000296 switchExclusivelyCovered(false), switchCond(0),
Ted Kremeneka8d459e2011-03-23 21:33:21 +0000297 cachedEntry(0), lastLookup(0) {}
Mike Stump6d9828c2009-07-17 01:31:16 +0000298
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000299 // buildCFG - Used by external clients to construct the CFG.
Ted Kremenekb8ad5ee2011-03-10 01:14:05 +0000300 CFG* buildCFG(const Decl *D, Stmt *Statement);
Mike Stump6d9828c2009-07-17 01:31:16 +0000301
Ted Kremenek0d28d362011-03-10 03:50:34 +0000302 bool alwaysAdd(const Stmt *stmt);
303
Ted Kremenek4f880632009-07-17 22:18:43 +0000304private:
305 // Visitors to walk an AST and construct the CFG.
Ted Kremenek852274d2009-12-16 03:18:58 +0000306 CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc);
307 CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc);
Ted Kremenek9c378f72011-08-12 23:37:29 +0000308 CFGBlock *VisitBlockExpr(BlockExpr *E, AddStmtChoice asc);
Ted Kremenek4f880632009-07-17 22:18:43 +0000309 CFGBlock *VisitBreakStmt(BreakStmt *B);
Ted Kremenek7ea21362010-04-11 17:01:59 +0000310 CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S);
John McCall4765fa02010-12-06 08:20:24 +0000311 CFGBlock *VisitExprWithCleanups(ExprWithCleanups *E,
Marcin Swiderski8599e762010-11-03 06:19:35 +0000312 AddStmtChoice asc);
Ted Kremenek7ea21362010-04-11 17:01:59 +0000313 CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T);
314 CFGBlock *VisitCXXTryStmt(CXXTryStmt *S);
Richard Smithad762fc2011-04-14 22:09:26 +0000315 CFGBlock *VisitCXXForRangeStmt(CXXForRangeStmt *S);
Zhongxing Xua725ed42010-11-01 13:04:58 +0000316 CFGBlock *VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
317 AddStmtChoice asc);
Zhongxing Xu81bc7d02010-11-01 06:46:05 +0000318 CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc);
Zhongxing Xua725ed42010-11-01 13:04:58 +0000319 CFGBlock *VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
320 AddStmtChoice asc);
Zhongxing Xu81bc7d02010-11-01 06:46:05 +0000321 CFGBlock *VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C,
322 AddStmtChoice asc);
Ted Kremenek852274d2009-12-16 03:18:58 +0000323 CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc);
Ted Kremenek4f880632009-07-17 22:18:43 +0000324 CFGBlock *VisitCaseStmt(CaseStmt *C);
Ted Kremenek852274d2009-12-16 03:18:58 +0000325 CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc);
Ted Kremenek3fc8ef52009-07-17 18:20:32 +0000326 CFGBlock *VisitCompoundStmt(CompoundStmt *C);
John McCall56ca35d2011-02-17 10:25:35 +0000327 CFGBlock *VisitConditionalOperator(AbstractConditionalOperator *C,
328 AddStmtChoice asc);
Ted Kremenek3fc8ef52009-07-17 18:20:32 +0000329 CFGBlock *VisitContinueStmt(ContinueStmt *C);
Ted Kremenek4f880632009-07-17 22:18:43 +0000330 CFGBlock *VisitDeclStmt(DeclStmt *DS);
Ted Kremenek9c378f72011-08-12 23:37:29 +0000331 CFGBlock *VisitDeclSubExpr(DeclStmt *DS);
Ted Kremenek3fc8ef52009-07-17 18:20:32 +0000332 CFGBlock *VisitDefaultStmt(DefaultStmt *D);
333 CFGBlock *VisitDoStmt(DoStmt *D);
334 CFGBlock *VisitForStmt(ForStmt *F);
Ted Kremenek9c378f72011-08-12 23:37:29 +0000335 CFGBlock *VisitGotoStmt(GotoStmt *G);
Ted Kremenek4f880632009-07-17 22:18:43 +0000336 CFGBlock *VisitIfStmt(IfStmt *I);
Zhongxing Xua725ed42010-11-01 13:04:58 +0000337 CFGBlock *VisitImplicitCastExpr(ImplicitCastExpr *E, AddStmtChoice asc);
Ted Kremenek4f880632009-07-17 22:18:43 +0000338 CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I);
339 CFGBlock *VisitLabelStmt(LabelStmt *L);
Ted Kremenek115c1b92010-04-11 17:02:10 +0000340 CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc);
Ted Kremenek4f880632009-07-17 22:18:43 +0000341 CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S);
342 CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S);
343 CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S);
344 CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S);
345 CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S);
Ted Kremenek9c378f72011-08-12 23:37:29 +0000346 CFGBlock *VisitReturnStmt(ReturnStmt *R);
John McCall4b9c2d22011-11-06 09:01:30 +0000347 CFGBlock *VisitPseudoObjectExpr(PseudoObjectExpr *E);
Peter Collingbournef4e3cfb2011-03-11 19:24:49 +0000348 CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
349 AddStmtChoice asc);
Ted Kremenek852274d2009-12-16 03:18:58 +0000350 CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc);
Ted Kremenek4f880632009-07-17 22:18:43 +0000351 CFGBlock *VisitSwitchStmt(SwitchStmt *S);
Zhanyong Wan99cae5b2010-11-22 08:45:56 +0000352 CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc);
Ted Kremenek4f880632009-07-17 22:18:43 +0000353 CFGBlock *VisitWhileStmt(WhileStmt *W);
Mike Stumpcd7bf232009-07-17 01:04:31 +0000354
Ted Kremenek852274d2009-12-16 03:18:58 +0000355 CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd);
356 CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc);
Ted Kremenek9c378f72011-08-12 23:37:29 +0000357 CFGBlock *VisitChildren(Stmt *S);
Mike Stumpcd7bf232009-07-17 01:04:31 +0000358
Marcin Swiderski8599e762010-11-03 06:19:35 +0000359 // Visitors to walk an AST and generate destructors of temporaries in
360 // full expression.
361 CFGBlock *VisitForTemporaryDtors(Stmt *E, bool BindToTemporary = false);
362 CFGBlock *VisitChildrenForTemporaryDtors(Stmt *E);
363 CFGBlock *VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E);
364 CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors(CXXBindTemporaryExpr *E,
365 bool BindToTemporary);
John McCall56ca35d2011-02-17 10:25:35 +0000366 CFGBlock *
367 VisitConditionalOperatorForTemporaryDtors(AbstractConditionalOperator *E,
368 bool BindToTemporary);
Marcin Swiderski8599e762010-11-03 06:19:35 +0000369
Ted Kremenek274f4332008-04-28 18:00:46 +0000370 // NYS == Not Yet Supported
Ted Kremenek9c378f72011-08-12 23:37:29 +0000371 CFGBlock *NYS() {
Ted Kremenek4102af92008-03-13 03:04:22 +0000372 badCFG = true;
373 return Block;
374 }
Mike Stump6d9828c2009-07-17 01:31:16 +0000375
Ted Kremenek4f880632009-07-17 22:18:43 +0000376 void autoCreateBlock() { if (!Block) Block = createBlock(); }
377 CFGBlock *createBlock(bool add_successor = true);
Chandler Carruthdba3fb52011-09-13 09:13:49 +0000378 CFGBlock *createNoReturnBlock();
Zhongxing Xud438b3d2010-09-06 07:32:31 +0000379
Zhongxing Xudf119892010-06-03 06:43:23 +0000380 CFGBlock *addStmt(Stmt *S) {
381 return Visit(S, AddStmtChoice::AlwaysAdd);
Ted Kremenek852274d2009-12-16 03:18:58 +0000382 }
Sean Huntcbb67482011-01-08 20:30:50 +0000383 CFGBlock *addInitializer(CXXCtorInitializer *I);
Zhongxing Xu6a16a302010-10-01 03:22:39 +0000384 void addAutomaticObjDtors(LocalScope::const_iterator B,
Ted Kremenek9c378f72011-08-12 23:37:29 +0000385 LocalScope::const_iterator E, Stmt *S);
Marcin Swiderski7c625d82010-10-05 05:37:00 +0000386 void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD);
Ted Kremenekad5a8942010-08-02 23:46:59 +0000387
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000388 // Local scopes creation.
389 LocalScope* createOrReuseLocalScope(LocalScope* Scope);
390
Ted Kremenek9c378f72011-08-12 23:37:29 +0000391 void addLocalScopeForStmt(Stmt *S);
392 LocalScope* addLocalScopeForDeclStmt(DeclStmt *DS, LocalScope* Scope = NULL);
393 LocalScope* addLocalScopeForVarDecl(VarDecl *VD, LocalScope* Scope = NULL);
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000394
Ted Kremenek9c378f72011-08-12 23:37:29 +0000395 void addLocalScopeAndDtors(Stmt *S);
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000396
397 // Interface to CFGBlock - adding CFGElements.
Ted Kremenekd40066b2011-04-04 23:29:12 +0000398 void appendStmt(CFGBlock *B, const Stmt *S) {
Ted Kremenek74fb1a42011-07-19 14:18:43 +0000399 if (alwaysAdd(S) && cachedEntry)
Ted Kremenek0d28d362011-03-10 03:50:34 +0000400 cachedEntry->second = B;
Ted Kremenek0d28d362011-03-10 03:50:34 +0000401
Jordy Roseac73ea82011-06-10 08:49:37 +0000402 // All block-level expressions should have already been IgnoreParens()ed.
403 assert(!isa<Expr>(S) || cast<Expr>(S)->IgnoreParens() == S);
Ted Kremenekd40066b2011-04-04 23:29:12 +0000404 B->appendStmt(const_cast<Stmt*>(S), cfg->getBumpVectorContext());
Ted Kremenekee82d9b2009-10-12 20:55:07 +0000405 }
Sean Huntcbb67482011-01-08 20:30:50 +0000406 void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) {
Marcin Swiderski82bc3fd2010-10-04 03:38:22 +0000407 B->appendInitializer(I, cfg->getBumpVectorContext());
408 }
Marcin Swiderski7c625d82010-10-05 05:37:00 +0000409 void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) {
410 B->appendBaseDtor(BS, cfg->getBumpVectorContext());
411 }
412 void appendMemberDtor(CFGBlock *B, FieldDecl *FD) {
413 B->appendMemberDtor(FD, cfg->getBumpVectorContext());
414 }
Marcin Swiderski8599e762010-11-03 06:19:35 +0000415 void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) {
416 B->appendTemporaryDtor(E, cfg->getBumpVectorContext());
417 }
Chandler Carruthc8cfc742011-09-13 06:09:01 +0000418 void appendAutomaticObjDtor(CFGBlock *B, VarDecl *VD, Stmt *S) {
419 B->appendAutomaticObjDtor(VD, S, cfg->getBumpVectorContext());
420 }
Ted Kremenekad5a8942010-08-02 23:46:59 +0000421
Ted Kremenek9c378f72011-08-12 23:37:29 +0000422 void prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
Marcin Swiderski53de1342010-09-30 22:54:37 +0000423 LocalScope::const_iterator B, LocalScope::const_iterator E);
424
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000425 void addSuccessor(CFGBlock *B, CFGBlock *S) {
Ted Kremenekee82d9b2009-10-12 20:55:07 +0000426 B->addSuccessor(S, cfg->getBumpVectorContext());
427 }
Mike Stump1eb44332009-09-09 15:08:12 +0000428
Ted Kremeneke71f3d52011-03-01 23:12:55 +0000429 /// Try and evaluate an expression to an integer constant.
430 bool tryEvaluate(Expr *S, Expr::EvalResult &outResult) {
431 if (!BuildOpts.PruneTriviallyFalseEdges)
432 return false;
433 return !S->isTypeDependent() &&
Ted Kremenekf8adeef2011-04-04 20:30:58 +0000434 !S->isValueDependent() &&
Richard Smith51f47082011-10-29 00:50:52 +0000435 S->EvaluateAsRValue(outResult, *Context);
Ted Kremeneke71f3d52011-03-01 23:12:55 +0000436 }
Mike Stump1eb44332009-09-09 15:08:12 +0000437
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000438 /// tryEvaluateBool - Try and evaluate the Stmt and return 0 or 1
Mike Stump00998a02009-07-23 23:25:26 +0000439 /// if we can evaluate to a known value, otherwise return -1.
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000440 TryResult tryEvaluateBool(Expr *S) {
Richard Smith85df96c2011-10-14 20:22:00 +0000441 bool Result;
442 if (!BuildOpts.PruneTriviallyFalseEdges ||
443 S->isTypeDependent() || S->isValueDependent() ||
444 !S->EvaluateAsBooleanCondition(Result, *Context))
Ted Kremeneke71f3d52011-03-01 23:12:55 +0000445 return TryResult();
Richard Smith85df96c2011-10-14 20:22:00 +0000446 return Result;
Mike Stump00998a02009-07-23 23:25:26 +0000447 }
Ted Kremeneke71f3d52011-03-01 23:12:55 +0000448
Ted Kremenekfddd5182007-08-21 21:42:03 +0000449};
Mike Stump6d9828c2009-07-17 01:31:16 +0000450
Ted Kremenek0d28d362011-03-10 03:50:34 +0000451inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder,
452 const Stmt *stmt) const {
453 return builder.alwaysAdd(stmt) || kind == AlwaysAdd;
454}
Ted Kremeneka8d459e2011-03-23 21:33:21 +0000455
Ted Kremenek0d28d362011-03-10 03:50:34 +0000456bool CFGBuilder::alwaysAdd(const Stmt *stmt) {
Ted Kremenek74fb1a42011-07-19 14:18:43 +0000457 bool shouldAdd = BuildOpts.alwaysAdd(stmt);
458
Ted Kremenek0d28d362011-03-10 03:50:34 +0000459 if (!BuildOpts.forcedBlkExprs)
Ted Kremenek74fb1a42011-07-19 14:18:43 +0000460 return shouldAdd;
Ted Kremeneka8d459e2011-03-23 21:33:21 +0000461
462 if (lastLookup == stmt) {
463 if (cachedEntry) {
464 assert(cachedEntry->first == stmt);
465 return true;
466 }
Ted Kremenek74fb1a42011-07-19 14:18:43 +0000467 return shouldAdd;
Ted Kremeneka8d459e2011-03-23 21:33:21 +0000468 }
Ted Kremenek0d28d362011-03-10 03:50:34 +0000469
Ted Kremeneka8d459e2011-03-23 21:33:21 +0000470 lastLookup = stmt;
471
472 // Perform the lookup!
Ted Kremenek0d28d362011-03-10 03:50:34 +0000473 CFG::BuildOptions::ForcedBlkExprs *fb = *BuildOpts.forcedBlkExprs;
474
Ted Kremeneka8d459e2011-03-23 21:33:21 +0000475 if (!fb) {
476 // No need to update 'cachedEntry', since it will always be null.
477 assert(cachedEntry == 0);
Ted Kremenek74fb1a42011-07-19 14:18:43 +0000478 return shouldAdd;
Ted Kremeneka8d459e2011-03-23 21:33:21 +0000479 }
Ted Kremenek0d28d362011-03-10 03:50:34 +0000480
481 CFG::BuildOptions::ForcedBlkExprs::iterator itr = fb->find(stmt);
Ted Kremeneka8d459e2011-03-23 21:33:21 +0000482 if (itr == fb->end()) {
483 cachedEntry = 0;
Ted Kremenek74fb1a42011-07-19 14:18:43 +0000484 return shouldAdd;
Ted Kremeneka8d459e2011-03-23 21:33:21 +0000485 }
486
Ted Kremenek0d28d362011-03-10 03:50:34 +0000487 cachedEntry = &*itr;
488 return true;
Ted Kremenek3179a452011-03-10 01:14:11 +0000489}
490
Douglas Gregor898574e2008-12-05 23:32:09 +0000491// FIXME: Add support for dependent-sized array types in C++?
492// Does it even make sense to build a CFG for an uninstantiated template?
John McCallf4c73712011-01-19 06:33:43 +0000493static const VariableArrayType *FindVA(const Type *t) {
494 while (const ArrayType *vt = dyn_cast<ArrayType>(t)) {
495 if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(vt))
Ted Kremenek610a09e2008-09-26 22:58:57 +0000496 if (vat->getSizeExpr())
497 return vat;
Mike Stump6d9828c2009-07-17 01:31:16 +0000498
Ted Kremenek610a09e2008-09-26 22:58:57 +0000499 t = vt->getElementType().getTypePtr();
500 }
Mike Stump6d9828c2009-07-17 01:31:16 +0000501
Ted Kremenek610a09e2008-09-26 22:58:57 +0000502 return 0;
503}
Mike Stump6d9828c2009-07-17 01:31:16 +0000504
505/// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an
506/// arbitrary statement. Examples include a single expression or a function
507/// body (compound statement). The ownership of the returned CFG is
508/// transferred to the caller. If CFG construction fails, this method returns
509/// NULL.
Ted Kremenek9c378f72011-08-12 23:37:29 +0000510CFG* CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) {
Ted Kremenek0ba497b2009-10-20 23:46:25 +0000511 assert(cfg.get());
Ted Kremenek4f880632009-07-17 22:18:43 +0000512 if (!Statement)
513 return NULL;
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000514
Mike Stump6d9828c2009-07-17 01:31:16 +0000515 // Create an empty block that will serve as the exit block for the CFG. Since
516 // this is the first block added to the CFG, it will be implicitly registered
517 // as the exit block.
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000518 Succ = createBlock();
Ted Kremenekee82d9b2009-10-12 20:55:07 +0000519 assert(Succ == &cfg->getExit());
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000520 Block = NULL; // the EXIT block is empty. Create all other blocks lazily.
Mike Stump6d9828c2009-07-17 01:31:16 +0000521
Marcin Swiderski7c625d82010-10-05 05:37:00 +0000522 if (BuildOpts.AddImplicitDtors)
523 if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D))
524 addImplicitDtorsForDestructor(DD);
525
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000526 // Visit the statements and create the CFG.
Zhongxing Xu1b3b7cb2010-09-06 07:04:06 +0000527 CFGBlock *B = addStmt(Statement);
528
529 if (badCFG)
530 return NULL;
531
Marcin Swiderski82bc3fd2010-10-04 03:38:22 +0000532 // For C++ constructor add initializers to CFG.
533 if (const CXXConstructorDecl *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) {
534 for (CXXConstructorDecl::init_const_reverse_iterator I = CD->init_rbegin(),
535 E = CD->init_rend(); I != E; ++I) {
536 B = addInitializer(*I);
537 if (badCFG)
538 return NULL;
539 }
540 }
541
Zhongxing Xu1b3b7cb2010-09-06 07:04:06 +0000542 if (B)
543 Succ = B;
Mike Stumpb978a442010-01-21 02:21:40 +0000544
Zhongxing Xu1b3b7cb2010-09-06 07:04:06 +0000545 // Backpatch the gotos whose label -> block mappings we didn't know when we
546 // encountered them.
547 for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(),
548 E = BackpatchBlocks.end(); I != E; ++I ) {
Mike Stump6d9828c2009-07-17 01:31:16 +0000549
Ted Kremenek9c378f72011-08-12 23:37:29 +0000550 CFGBlock *B = I->block;
551 GotoStmt *G = cast<GotoStmt>(B->getTerminator());
Zhongxing Xu1b3b7cb2010-09-06 07:04:06 +0000552 LabelMapTy::iterator LI = LabelMap.find(G->getLabel());
Mike Stump6d9828c2009-07-17 01:31:16 +0000553
Zhongxing Xu1b3b7cb2010-09-06 07:04:06 +0000554 // If there is no target for the goto, then we are looking at an
555 // incomplete AST. Handle this by not registering a successor.
556 if (LI == LabelMap.end()) continue;
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000557
Marcin Swiderskif1308c72010-09-25 11:05:21 +0000558 JumpTarget JT = LI->second;
Ted Kremenek9ce52702011-01-07 19:37:16 +0000559 prependAutomaticObjDtorsWithTerminator(B, I->scopePosition,
560 JT.scopePosition);
561 addSuccessor(B, JT.block);
Zhongxing Xu1b3b7cb2010-09-06 07:04:06 +0000562 }
563
564 // Add successors to the Indirect Goto Dispatch block (if we have one).
Ted Kremenek9c378f72011-08-12 23:37:29 +0000565 if (CFGBlock *B = cfg->getIndirectGotoBlock())
Zhongxing Xu1b3b7cb2010-09-06 07:04:06 +0000566 for (LabelSetTy::iterator I = AddressTakenLabels.begin(),
567 E = AddressTakenLabels.end(); I != E; ++I ) {
568
569 // Lookup the target block.
570 LabelMapTy::iterator LI = LabelMap.find(*I);
571
572 // If there is no target block that contains label, then we are looking
573 // at an incomplete AST. Handle this by not registering a successor.
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000574 if (LI == LabelMap.end()) continue;
Zhongxing Xu1b3b7cb2010-09-06 07:04:06 +0000575
Ted Kremenek9ce52702011-01-07 19:37:16 +0000576 addSuccessor(B, LI->second.block);
Ted Kremenek19bb3562007-08-28 19:26:49 +0000577 }
Mike Stump6d9828c2009-07-17 01:31:16 +0000578
Mike Stump6d9828c2009-07-17 01:31:16 +0000579 // Create an empty entry block that has no predecessors.
Ted Kremenek322f58d2007-09-26 21:23:31 +0000580 cfg->setEntry(createBlock());
Mike Stump6d9828c2009-07-17 01:31:16 +0000581
Zhongxing Xu1b3b7cb2010-09-06 07:04:06 +0000582 return cfg.take();
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000583}
Mike Stump6d9828c2009-07-17 01:31:16 +0000584
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000585/// createBlock - Used to lazily create blocks that are connected
586/// to the current (global) succcessor.
Ted Kremenek9c378f72011-08-12 23:37:29 +0000587CFGBlock *CFGBuilder::createBlock(bool add_successor) {
588 CFGBlock *B = cfg->createBlock();
Ted Kremenek4f880632009-07-17 22:18:43 +0000589 if (add_successor && Succ)
Ted Kremenek0a3ed312010-12-17 04:44:39 +0000590 addSuccessor(B, Succ);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000591 return B;
592}
Mike Stump6d9828c2009-07-17 01:31:16 +0000593
Chandler Carruthdba3fb52011-09-13 09:13:49 +0000594/// createNoReturnBlock - Used to create a block is a 'noreturn' point in the
595/// CFG. It is *not* connected to the current (global) successor, and instead
596/// directly tied to the exit block in order to be reachable.
597CFGBlock *CFGBuilder::createNoReturnBlock() {
598 CFGBlock *B = createBlock(false);
Chandler Carruth83754162011-09-13 09:53:55 +0000599 B->setHasNoReturnElement();
Chandler Carruthdba3fb52011-09-13 09:13:49 +0000600 addSuccessor(B, &cfg->getExit());
601 return B;
602}
603
Marcin Swiderski82bc3fd2010-10-04 03:38:22 +0000604/// addInitializer - Add C++ base or member initializer element to CFG.
Sean Huntcbb67482011-01-08 20:30:50 +0000605CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) {
Marcin Swiderski82bc3fd2010-10-04 03:38:22 +0000606 if (!BuildOpts.AddInitializers)
607 return Block;
608
Marcin Swiderski8599e762010-11-03 06:19:35 +0000609 bool IsReference = false;
610 bool HasTemporaries = false;
611
612 // Destructors of temporaries in initialization expression should be called
613 // after initialization finishes.
614 Expr *Init = I->getInit();
615 if (Init) {
Francois Pichet00eb3f92010-12-04 09:14:42 +0000616 if (FieldDecl *FD = I->getAnyMember())
Marcin Swiderski8599e762010-11-03 06:19:35 +0000617 IsReference = FD->getType()->isReferenceType();
John McCall4765fa02010-12-06 08:20:24 +0000618 HasTemporaries = isa<ExprWithCleanups>(Init);
Marcin Swiderski8599e762010-11-03 06:19:35 +0000619
620 if (BuildOpts.AddImplicitDtors && HasTemporaries) {
621 // Generate destructors for temporaries in initialization expression.
John McCall4765fa02010-12-06 08:20:24 +0000622 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),
Marcin Swiderski8599e762010-11-03 06:19:35 +0000623 IsReference);
624 }
625 }
626
Marcin Swiderski82bc3fd2010-10-04 03:38:22 +0000627 autoCreateBlock();
628 appendInitializer(Block, I);
629
Marcin Swiderski8599e762010-11-03 06:19:35 +0000630 if (Init) {
Ted Kremenek892697d2010-12-16 07:46:53 +0000631 if (HasTemporaries) {
Marcin Swiderski8599e762010-11-03 06:19:35 +0000632 // For expression with temporaries go directly to subexpression to omit
633 // generating destructors for the second time.
Ted Kremenek892697d2010-12-16 07:46:53 +0000634 return Visit(cast<ExprWithCleanups>(Init)->getSubExpr());
635 }
636 return Visit(Init);
Marcin Swiderski82bc3fd2010-10-04 03:38:22 +0000637 }
Marcin Swiderski8599e762010-11-03 06:19:35 +0000638
Marcin Swiderski82bc3fd2010-10-04 03:38:22 +0000639 return Block;
640}
641
Douglas Gregor2d9eb212011-11-15 15:29:30 +0000642/// \brief Retrieve the type of the temporary object whose lifetime was
643/// extended by a local reference with the given initializer.
644static QualType getReferenceInitTemporaryType(ASTContext &Context,
645 const Expr *Init) {
646 while (true) {
647 // Skip parentheses.
648 Init = Init->IgnoreParens();
649
650 // Skip through cleanups.
651 if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Init)) {
652 Init = EWC->getSubExpr();
653 continue;
654 }
655
656 // Skip through the temporary-materialization expression.
657 if (const MaterializeTemporaryExpr *MTE
658 = dyn_cast<MaterializeTemporaryExpr>(Init)) {
659 Init = MTE->GetTemporaryExpr();
660 continue;
661 }
662
663 // Skip derived-to-base and no-op casts.
664 if (const CastExpr *CE = dyn_cast<CastExpr>(Init)) {
665 if ((CE->getCastKind() == CK_DerivedToBase ||
666 CE->getCastKind() == CK_UncheckedDerivedToBase ||
667 CE->getCastKind() == CK_NoOp) &&
668 Init->getType()->isRecordType()) {
669 Init = CE->getSubExpr();
670 continue;
671 }
672 }
673
674 // Skip member accesses into rvalues.
675 if (const MemberExpr *ME = dyn_cast<MemberExpr>(Init)) {
676 if (!ME->isArrow() && ME->getBase()->isRValue()) {
677 Init = ME->getBase();
678 continue;
679 }
680 }
681
682 break;
683 }
684
685 return Init->getType();
686}
687
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000688/// addAutomaticObjDtors - Add to current block automatic objects destructors
689/// for objects in range of local scope positions. Use S as trigger statement
690/// for destructors.
Zhongxing Xu6a16a302010-10-01 03:22:39 +0000691void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B,
Ted Kremenek9c378f72011-08-12 23:37:29 +0000692 LocalScope::const_iterator E, Stmt *S) {
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000693 if (!BuildOpts.AddImplicitDtors)
Zhongxing Xu6a16a302010-10-01 03:22:39 +0000694 return;
695
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000696 if (B == E)
Zhongxing Xu6a16a302010-10-01 03:22:39 +0000697 return;
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000698
Chandler Carruthc8cfc742011-09-13 06:09:01 +0000699 CFGBlock::iterator InsertPos;
700
701 // We need to append the destructors in reverse order, but any one of them
702 // may be a no-return destructor which changes the CFG. As a result, buffer
703 // this sequence up and replay them in reverse order when appending onto the
704 // CFGBlock(s).
705 SmallVector<VarDecl*, 10> Decls;
706 Decls.reserve(B.distance(E));
707 for (LocalScope::const_iterator I = B; I != E; ++I)
708 Decls.push_back(*I);
709
710 for (SmallVectorImpl<VarDecl*>::reverse_iterator I = Decls.rbegin(),
711 E = Decls.rend();
712 I != E; ++I) {
713 // If this destructor is marked as a no-return destructor, we need to
714 // create a new block for the destructor which does not have as a successor
715 // anything built thus far: control won't flow out of this block.
Douglas Gregor2d9eb212011-11-15 15:29:30 +0000716 QualType Ty;
717 if ((*I)->getType()->isReferenceType()) {
718 Ty = getReferenceInitTemporaryType(*Context, (*I)->getInit());
719 } else {
720 Ty = Context->getBaseElementType((*I)->getType());
721 }
722
Chandler Carruthc8cfc742011-09-13 06:09:01 +0000723 const CXXDestructorDecl *Dtor = Ty->getAsCXXRecordDecl()->getDestructor();
Chandler Carruthdba3fb52011-09-13 09:13:49 +0000724 if (cast<FunctionType>(Dtor->getType())->getNoReturnAttr())
725 Block = createNoReturnBlock();
726 else
Chandler Carruthc8cfc742011-09-13 06:09:01 +0000727 autoCreateBlock();
Chandler Carruthc8cfc742011-09-13 06:09:01 +0000728
729 appendAutomaticObjDtor(Block, *I, S);
730 }
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000731}
732
Marcin Swiderski7c625d82010-10-05 05:37:00 +0000733/// addImplicitDtorsForDestructor - Add implicit destructors generated for
734/// base and member objects in destructor.
735void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) {
736 assert (BuildOpts.AddImplicitDtors
737 && "Can be called only when dtors should be added");
738 const CXXRecordDecl *RD = DD->getParent();
739
740 // At the end destroy virtual base objects.
741 for (CXXRecordDecl::base_class_const_iterator VI = RD->vbases_begin(),
742 VE = RD->vbases_end(); VI != VE; ++VI) {
743 const CXXRecordDecl *CD = VI->getType()->getAsCXXRecordDecl();
744 if (!CD->hasTrivialDestructor()) {
745 autoCreateBlock();
746 appendBaseDtor(Block, VI);
747 }
748 }
749
750 // Before virtual bases destroy direct base objects.
751 for (CXXRecordDecl::base_class_const_iterator BI = RD->bases_begin(),
752 BE = RD->bases_end(); BI != BE; ++BI) {
753 if (!BI->isVirtual()) {
754 const CXXRecordDecl *CD = BI->getType()->getAsCXXRecordDecl();
755 if (!CD->hasTrivialDestructor()) {
756 autoCreateBlock();
757 appendBaseDtor(Block, BI);
758 }
759 }
760 }
761
762 // First destroy member objects.
763 for (CXXRecordDecl::field_iterator FI = RD->field_begin(),
764 FE = RD->field_end(); FI != FE; ++FI) {
Marcin Swiderski8c5e5d62010-10-25 07:05:54 +0000765 // Check for constant size array. Set type to array element type.
766 QualType QT = FI->getType();
767 if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {
768 if (AT->getSize() == 0)
769 continue;
770 QT = AT->getElementType();
771 }
772
773 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
Marcin Swiderski7c625d82010-10-05 05:37:00 +0000774 if (!CD->hasTrivialDestructor()) {
775 autoCreateBlock();
776 appendMemberDtor(Block, *FI);
777 }
778 }
779}
780
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000781/// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either
782/// way return valid LocalScope object.
783LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) {
784 if (!Scope) {
Ted Kremenekfe59b742011-02-15 02:47:45 +0000785 llvm::BumpPtrAllocator &alloc = cfg->getAllocator();
786 Scope = alloc.Allocate<LocalScope>();
787 BumpVectorContext ctx(alloc);
788 new (Scope) LocalScope(ctx, ScopePos);
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000789 }
790 return Scope;
791}
792
793/// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement
Zhongxing Xu02acdfa2010-10-01 03:00:16 +0000794/// that should create implicit scope (e.g. if/else substatements).
Ted Kremenek9c378f72011-08-12 23:37:29 +0000795void CFGBuilder::addLocalScopeForStmt(Stmt *S) {
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000796 if (!BuildOpts.AddImplicitDtors)
Zhongxing Xu02acdfa2010-10-01 03:00:16 +0000797 return;
798
799 LocalScope *Scope = 0;
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000800
801 // For compound statement we will be creating explicit scope.
Chris Lattnerad8dcf42011-02-17 07:39:24 +0000802 if (CompoundStmt *CS = dyn_cast<CompoundStmt>(S)) {
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000803 for (CompoundStmt::body_iterator BI = CS->body_begin(), BE = CS->body_end()
804 ; BI != BE; ++BI) {
Chandler Carrutha1364be2011-09-10 00:02:34 +0000805 Stmt *SI = (*BI)->stripLabelLikeStatements();
Chris Lattnerad8dcf42011-02-17 07:39:24 +0000806 if (DeclStmt *DS = dyn_cast<DeclStmt>(SI))
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000807 Scope = addLocalScopeForDeclStmt(DS, Scope);
808 }
Zhongxing Xu02acdfa2010-10-01 03:00:16 +0000809 return;
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000810 }
811
812 // For any other statement scope will be implicit and as such will be
813 // interesting only for DeclStmt.
Chandler Carrutha1364be2011-09-10 00:02:34 +0000814 if (DeclStmt *DS = dyn_cast<DeclStmt>(S->stripLabelLikeStatements()))
Zhongxing Xub6edff52010-10-01 03:09:09 +0000815 addLocalScopeForDeclStmt(DS);
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000816}
817
818/// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will
819/// reuse Scope if not NULL.
Ted Kremenek9c378f72011-08-12 23:37:29 +0000820LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt *DS,
Zhongxing Xub6edff52010-10-01 03:09:09 +0000821 LocalScope* Scope) {
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000822 if (!BuildOpts.AddImplicitDtors)
823 return Scope;
824
825 for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end()
826 ; DI != DE; ++DI) {
Ted Kremenek9c378f72011-08-12 23:37:29 +0000827 if (VarDecl *VD = dyn_cast<VarDecl>(*DI))
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000828 Scope = addLocalScopeForVarDecl(VD, Scope);
829 }
830 return Scope;
831}
832
833/// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will
834/// create add scope for automatic objects and temporary objects bound to
835/// const reference. Will reuse Scope if not NULL.
Ted Kremenek9c378f72011-08-12 23:37:29 +0000836LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD,
Zhongxing Xub6edff52010-10-01 03:09:09 +0000837 LocalScope* Scope) {
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000838 if (!BuildOpts.AddImplicitDtors)
839 return Scope;
840
841 // Check if variable is local.
842 switch (VD->getStorageClass()) {
843 case SC_None:
844 case SC_Auto:
845 case SC_Register:
846 break;
847 default: return Scope;
848 }
849
850 // Check for const references bound to temporary. Set type to pointee.
851 QualType QT = VD->getType();
Douglas Gregor2d9eb212011-11-15 15:29:30 +0000852 if (QT.getTypePtr()->isReferenceType()) {
Douglas Gregor03e80032011-06-21 17:03:29 +0000853 if (!VD->extendsLifetimeOfTemporary())
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000854 return Scope;
Douglas Gregor2d9eb212011-11-15 15:29:30 +0000855
856 QT = getReferenceInitTemporaryType(*Context, VD->getInit());
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000857 }
858
Marcin Swiderskib1c52872010-10-25 07:00:40 +0000859 // Check for constant size array. Set type to array element type.
Douglas Gregor2d9eb212011-11-15 15:29:30 +0000860 while (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {
Marcin Swiderskib1c52872010-10-25 07:00:40 +0000861 if (AT->getSize() == 0)
862 return Scope;
863 QT = AT->getElementType();
864 }
Zhongxing Xu4e493e02010-10-05 08:38:06 +0000865
Marcin Swiderskib1c52872010-10-25 07:00:40 +0000866 // Check if type is a C++ class with non-trivial destructor.
Ted Kremenek9c378f72011-08-12 23:37:29 +0000867 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())
Zhongxing Xu4e493e02010-10-05 08:38:06 +0000868 if (!CD->hasTrivialDestructor()) {
869 // Add the variable to scope
870 Scope = createOrReuseLocalScope(Scope);
871 Scope->addVar(VD);
872 ScopePos = Scope->begin();
873 }
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000874 return Scope;
875}
876
877/// addLocalScopeAndDtors - For given statement add local scope for it and
878/// add destructors that will cleanup the scope. Will reuse Scope if not NULL.
Ted Kremenek9c378f72011-08-12 23:37:29 +0000879void CFGBuilder::addLocalScopeAndDtors(Stmt *S) {
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000880 if (!BuildOpts.AddImplicitDtors)
881 return;
882
883 LocalScope::const_iterator scopeBeginPos = ScopePos;
Zhongxing Xu02acdfa2010-10-01 03:00:16 +0000884 addLocalScopeForStmt(S);
Marcin Swiderski239a7c42010-09-30 23:05:00 +0000885 addAutomaticObjDtors(ScopePos, scopeBeginPos, S);
886}
887
Marcin Swiderski53de1342010-09-30 22:54:37 +0000888/// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for
889/// variables with automatic storage duration to CFGBlock's elements vector.
890/// Elements will be prepended to physical beginning of the vector which
891/// happens to be logical end. Use blocks terminator as statement that specifies
892/// destructors call site.
Chandler Carruthc8cfc742011-09-13 06:09:01 +0000893/// FIXME: This mechanism for adding automatic destructors doesn't handle
894/// no-return destructors properly.
Ted Kremenek9c378f72011-08-12 23:37:29 +0000895void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
Marcin Swiderski53de1342010-09-30 22:54:37 +0000896 LocalScope::const_iterator B, LocalScope::const_iterator E) {
Chandler Carruthc8cfc742011-09-13 06:09:01 +0000897 BumpVectorContext &C = cfg->getBumpVectorContext();
898 CFGBlock::iterator InsertPos
899 = Blk->beginAutomaticObjDtorsInsert(Blk->end(), B.distance(E), C);
900 for (LocalScope::const_iterator I = B; I != E; ++I)
901 InsertPos = Blk->insertAutomaticObjDtor(InsertPos, *I,
902 Blk->getTerminator());
Marcin Swiderski53de1342010-09-30 22:54:37 +0000903}
904
Ted Kremenek4f880632009-07-17 22:18:43 +0000905/// Visit - Walk the subtree of a statement and add extra
Mike Stump6d9828c2009-07-17 01:31:16 +0000906/// blocks for ternary operators, &&, and ||. We also process "," and
907/// DeclStmts (which may contain nested control-flow).
Ted Kremenek9c378f72011-08-12 23:37:29 +0000908CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) {
Ted Kremenekf42e3372010-04-30 22:25:53 +0000909 if (!S) {
910 badCFG = true;
911 return 0;
912 }
Jordy Roseac73ea82011-06-10 08:49:37 +0000913
914 if (Expr *E = dyn_cast<Expr>(S))
915 S = E->IgnoreParens();
916
Ted Kremenek4f880632009-07-17 22:18:43 +0000917 switch (S->getStmtClass()) {
918 default:
Ted Kremenek852274d2009-12-16 03:18:58 +0000919 return VisitStmt(S, asc);
Ted Kremenek4f880632009-07-17 22:18:43 +0000920
921 case Stmt::AddrLabelExprClass:
Ted Kremenek852274d2009-12-16 03:18:58 +0000922 return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc);
Mike Stump1eb44332009-09-09 15:08:12 +0000923
John McCall56ca35d2011-02-17 10:25:35 +0000924 case Stmt::BinaryConditionalOperatorClass:
925 return VisitConditionalOperator(cast<BinaryConditionalOperator>(S), asc);
926
Ted Kremenek4f880632009-07-17 22:18:43 +0000927 case Stmt::BinaryOperatorClass:
Ted Kremenek852274d2009-12-16 03:18:58 +0000928 return VisitBinaryOperator(cast<BinaryOperator>(S), asc);
Mike Stump1eb44332009-09-09 15:08:12 +0000929
Ted Kremenek4f880632009-07-17 22:18:43 +0000930 case Stmt::BlockExprClass:
Ted Kremenek852274d2009-12-16 03:18:58 +0000931 return VisitBlockExpr(cast<BlockExpr>(S), asc);
Ted Kremenek4f880632009-07-17 22:18:43 +0000932
Ted Kremenek4f880632009-07-17 22:18:43 +0000933 case Stmt::BreakStmtClass:
934 return VisitBreakStmt(cast<BreakStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +0000935
Ted Kremenek4f880632009-07-17 22:18:43 +0000936 case Stmt::CallExprClass:
Ted Kremeneka427f1d2010-08-31 18:47:34 +0000937 case Stmt::CXXOperatorCallExprClass:
John McCall1de85332011-05-11 07:19:11 +0000938 case Stmt::CXXMemberCallExprClass:
Ted Kremenek852274d2009-12-16 03:18:58 +0000939 return VisitCallExpr(cast<CallExpr>(S), asc);
Mike Stump1eb44332009-09-09 15:08:12 +0000940
Ted Kremenek4f880632009-07-17 22:18:43 +0000941 case Stmt::CaseStmtClass:
942 return VisitCaseStmt(cast<CaseStmt>(S));
943
944 case Stmt::ChooseExprClass:
Ted Kremenek852274d2009-12-16 03:18:58 +0000945 return VisitChooseExpr(cast<ChooseExpr>(S), asc);
Mike Stump1eb44332009-09-09 15:08:12 +0000946
Ted Kremenek4f880632009-07-17 22:18:43 +0000947 case Stmt::CompoundStmtClass:
948 return VisitCompoundStmt(cast<CompoundStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +0000949
Ted Kremenek4f880632009-07-17 22:18:43 +0000950 case Stmt::ConditionalOperatorClass:
Ted Kremenek852274d2009-12-16 03:18:58 +0000951 return VisitConditionalOperator(cast<ConditionalOperator>(S), asc);
Mike Stump1eb44332009-09-09 15:08:12 +0000952
Ted Kremenek4f880632009-07-17 22:18:43 +0000953 case Stmt::ContinueStmtClass:
954 return VisitContinueStmt(cast<ContinueStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +0000955
Ted Kremenek021c8af2010-01-19 20:40:33 +0000956 case Stmt::CXXCatchStmtClass:
957 return VisitCXXCatchStmt(cast<CXXCatchStmt>(S));
958
John McCall4765fa02010-12-06 08:20:24 +0000959 case Stmt::ExprWithCleanupsClass:
960 return VisitExprWithCleanups(cast<ExprWithCleanups>(S), asc);
Ted Kremenek47e331e2010-08-28 00:19:02 +0000961
Zhongxing Xua725ed42010-11-01 13:04:58 +0000962 case Stmt::CXXBindTemporaryExprClass:
963 return VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), asc);
964
Zhongxing Xu81bc7d02010-11-01 06:46:05 +0000965 case Stmt::CXXConstructExprClass:
966 return VisitCXXConstructExpr(cast<CXXConstructExpr>(S), asc);
967
Zhongxing Xua725ed42010-11-01 13:04:58 +0000968 case Stmt::CXXFunctionalCastExprClass:
969 return VisitCXXFunctionalCastExpr(cast<CXXFunctionalCastExpr>(S), asc);
970
Zhongxing Xu81bc7d02010-11-01 06:46:05 +0000971 case Stmt::CXXTemporaryObjectExprClass:
972 return VisitCXXTemporaryObjectExpr(cast<CXXTemporaryObjectExpr>(S), asc);
973
Ted Kremenek021c8af2010-01-19 20:40:33 +0000974 case Stmt::CXXThrowExprClass:
975 return VisitCXXThrowExpr(cast<CXXThrowExpr>(S));
Ted Kremenekad5a8942010-08-02 23:46:59 +0000976
Ted Kremenek021c8af2010-01-19 20:40:33 +0000977 case Stmt::CXXTryStmtClass:
978 return VisitCXXTryStmt(cast<CXXTryStmt>(S));
Ted Kremenekad5a8942010-08-02 23:46:59 +0000979
Richard Smithad762fc2011-04-14 22:09:26 +0000980 case Stmt::CXXForRangeStmtClass:
981 return VisitCXXForRangeStmt(cast<CXXForRangeStmt>(S));
982
Ted Kremenek4f880632009-07-17 22:18:43 +0000983 case Stmt::DeclStmtClass:
984 return VisitDeclStmt(cast<DeclStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +0000985
Ted Kremenek4f880632009-07-17 22:18:43 +0000986 case Stmt::DefaultStmtClass:
987 return VisitDefaultStmt(cast<DefaultStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +0000988
Ted Kremenek4f880632009-07-17 22:18:43 +0000989 case Stmt::DoStmtClass:
990 return VisitDoStmt(cast<DoStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +0000991
Ted Kremenek4f880632009-07-17 22:18:43 +0000992 case Stmt::ForStmtClass:
993 return VisitForStmt(cast<ForStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +0000994
Ted Kremenek4f880632009-07-17 22:18:43 +0000995 case Stmt::GotoStmtClass:
996 return VisitGotoStmt(cast<GotoStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +0000997
Ted Kremenek4f880632009-07-17 22:18:43 +0000998 case Stmt::IfStmtClass:
999 return VisitIfStmt(cast<IfStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +00001000
Ted Kremenek892697d2010-12-16 07:46:53 +00001001 case Stmt::ImplicitCastExprClass:
1002 return VisitImplicitCastExpr(cast<ImplicitCastExpr>(S), asc);
Zhongxing Xua725ed42010-11-01 13:04:58 +00001003
Ted Kremenek4f880632009-07-17 22:18:43 +00001004 case Stmt::IndirectGotoStmtClass:
1005 return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +00001006
Ted Kremenek4f880632009-07-17 22:18:43 +00001007 case Stmt::LabelStmtClass:
1008 return VisitLabelStmt(cast<LabelStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +00001009
Ted Kremenek115c1b92010-04-11 17:02:10 +00001010 case Stmt::MemberExprClass:
1011 return VisitMemberExpr(cast<MemberExpr>(S), asc);
1012
Ted Kremenek6a9065a2011-11-05 00:10:15 +00001013 case Stmt::NullStmtClass:
1014 return Block;
1015
Ted Kremenek4f880632009-07-17 22:18:43 +00001016 case Stmt::ObjCAtCatchStmtClass:
Mike Stump1eb44332009-09-09 15:08:12 +00001017 return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S));
1018
Ted Kremenek4f880632009-07-17 22:18:43 +00001019 case Stmt::ObjCAtSynchronizedStmtClass:
1020 return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +00001021
Ted Kremenek4f880632009-07-17 22:18:43 +00001022 case Stmt::ObjCAtThrowStmtClass:
1023 return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +00001024
Ted Kremenek4f880632009-07-17 22:18:43 +00001025 case Stmt::ObjCAtTryStmtClass:
1026 return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +00001027
Ted Kremenek4f880632009-07-17 22:18:43 +00001028 case Stmt::ObjCForCollectionStmtClass:
1029 return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +00001030
Ted Kremenek6a9065a2011-11-05 00:10:15 +00001031 case Stmt::OpaqueValueExprClass:
Ted Kremenek4f880632009-07-17 22:18:43 +00001032 return Block;
Mike Stump1eb44332009-09-09 15:08:12 +00001033
John McCall4b9c2d22011-11-06 09:01:30 +00001034 case Stmt::PseudoObjectExprClass:
1035 return VisitPseudoObjectExpr(cast<PseudoObjectExpr>(S));
1036
Ted Kremenek4f880632009-07-17 22:18:43 +00001037 case Stmt::ReturnStmtClass:
1038 return VisitReturnStmt(cast<ReturnStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +00001039
Peter Collingbournef4e3cfb2011-03-11 19:24:49 +00001040 case Stmt::UnaryExprOrTypeTraitExprClass:
1041 return VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),
1042 asc);
Mike Stump1eb44332009-09-09 15:08:12 +00001043
Ted Kremenek4f880632009-07-17 22:18:43 +00001044 case Stmt::StmtExprClass:
Ted Kremenek852274d2009-12-16 03:18:58 +00001045 return VisitStmtExpr(cast<StmtExpr>(S), asc);
Mike Stump1eb44332009-09-09 15:08:12 +00001046
Ted Kremenek4f880632009-07-17 22:18:43 +00001047 case Stmt::SwitchStmtClass:
1048 return VisitSwitchStmt(cast<SwitchStmt>(S));
Mike Stump1eb44332009-09-09 15:08:12 +00001049
Zhanyong Wan99cae5b2010-11-22 08:45:56 +00001050 case Stmt::UnaryOperatorClass:
1051 return VisitUnaryOperator(cast<UnaryOperator>(S), asc);
1052
Ted Kremenek4f880632009-07-17 22:18:43 +00001053 case Stmt::WhileStmtClass:
1054 return VisitWhileStmt(cast<WhileStmt>(S));
1055 }
1056}
Mike Stump1eb44332009-09-09 15:08:12 +00001057
Ted Kremenek852274d2009-12-16 03:18:58 +00001058CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) {
Ted Kremenek3179a452011-03-10 01:14:11 +00001059 if (asc.alwaysAdd(*this, S)) {
Ted Kremenek4f880632009-07-17 22:18:43 +00001060 autoCreateBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00001061 appendStmt(Block, S);
Mike Stump6d9828c2009-07-17 01:31:16 +00001062 }
Mike Stump1eb44332009-09-09 15:08:12 +00001063
Ted Kremenek4f880632009-07-17 22:18:43 +00001064 return VisitChildren(S);
Ted Kremenek9da2fb72007-08-27 21:27:44 +00001065}
Mike Stump6d9828c2009-07-17 01:31:16 +00001066
Ted Kremenek4f880632009-07-17 22:18:43 +00001067/// VisitChildren - Visit the children of a Stmt.
Ted Kremenek9c378f72011-08-12 23:37:29 +00001068CFGBlock *CFGBuilder::VisitChildren(Stmt *Terminator) {
Ted Kremenek6b12da92011-02-21 22:11:26 +00001069 CFGBlock *lastBlock = Block;
1070 for (Stmt::child_range I = Terminator->children(); I; ++I)
1071 if (Stmt *child = *I)
1072 if (CFGBlock *b = Visit(child))
1073 lastBlock = b;
1074
1075 return lastBlock;
Ted Kremenek9da2fb72007-08-27 21:27:44 +00001076}
Mike Stump1eb44332009-09-09 15:08:12 +00001077
Ted Kremenek852274d2009-12-16 03:18:58 +00001078CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A,
1079 AddStmtChoice asc) {
Ted Kremenek4f880632009-07-17 22:18:43 +00001080 AddressTakenLabels.insert(A->getLabel());
Ted Kremenek9da2fb72007-08-27 21:27:44 +00001081
Ted Kremenek3179a452011-03-10 01:14:11 +00001082 if (asc.alwaysAdd(*this, A)) {
Ted Kremenek4f880632009-07-17 22:18:43 +00001083 autoCreateBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00001084 appendStmt(Block, A);
Ted Kremenek4f880632009-07-17 22:18:43 +00001085 }
Ted Kremenek49af7cb2007-08-27 19:46:09 +00001086
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001087 return Block;
1088}
Mike Stump1eb44332009-09-09 15:08:12 +00001089
Zhanyong Wan99cae5b2010-11-22 08:45:56 +00001090CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U,
Ted Kremenek892697d2010-12-16 07:46:53 +00001091 AddStmtChoice asc) {
Ted Kremenek3179a452011-03-10 01:14:11 +00001092 if (asc.alwaysAdd(*this, U)) {
Zhanyong Wan99cae5b2010-11-22 08:45:56 +00001093 autoCreateBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00001094 appendStmt(Block, U);
Zhanyong Wan99cae5b2010-11-22 08:45:56 +00001095 }
1096
Ted Kremenek892697d2010-12-16 07:46:53 +00001097 return Visit(U->getSubExpr(), AddStmtChoice());
Zhanyong Wan99cae5b2010-11-22 08:45:56 +00001098}
1099
Ted Kremenek852274d2009-12-16 03:18:58 +00001100CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B,
1101 AddStmtChoice asc) {
Ted Kremenek4f880632009-07-17 22:18:43 +00001102 if (B->isLogicalOp()) { // && or ||
Ted Kremenek9c378f72011-08-12 23:37:29 +00001103 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00001104 appendStmt(ConfluenceBlock, B);
Mike Stump1eb44332009-09-09 15:08:12 +00001105
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001106 if (badCFG)
Ted Kremenek4f880632009-07-17 22:18:43 +00001107 return 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001108
Ted Kremenek4f880632009-07-17 22:18:43 +00001109 // create the block evaluating the LHS
Ted Kremenek9c378f72011-08-12 23:37:29 +00001110 CFGBlock *LHSBlock = createBlock(false);
Ted Kremenek4f880632009-07-17 22:18:43 +00001111 LHSBlock->setTerminator(B);
Mike Stump1eb44332009-09-09 15:08:12 +00001112
Ted Kremenek4f880632009-07-17 22:18:43 +00001113 // create the block evaluating the RHS
1114 Succ = ConfluenceBlock;
1115 Block = NULL;
Ted Kremenek9c378f72011-08-12 23:37:29 +00001116 CFGBlock *RHSBlock = addStmt(B->getRHS());
Ted Kremenek862b24f2010-04-29 01:10:26 +00001117
1118 if (RHSBlock) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001119 if (badCFG)
Ted Kremenek862b24f2010-04-29 01:10:26 +00001120 return 0;
Zhanyong Wan36f327c2010-11-22 19:32:14 +00001121 } else {
Ted Kremenek862b24f2010-04-29 01:10:26 +00001122 // Create an empty block for cases where the RHS doesn't require
1123 // any explicit statements in the CFG.
1124 RHSBlock = createBlock();
1125 }
Mike Stump1eb44332009-09-09 15:08:12 +00001126
Mike Stump00998a02009-07-23 23:25:26 +00001127 // See if this is a known constant.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001128 TryResult KnownVal = tryEvaluateBool(B->getLHS());
John McCall2de56d12010-08-25 11:45:40 +00001129 if (KnownVal.isKnown() && (B->getOpcode() == BO_LOr))
Ted Kremenek941fde82009-07-24 04:47:11 +00001130 KnownVal.negate();
Mike Stump00998a02009-07-23 23:25:26 +00001131
Ted Kremenek4f880632009-07-17 22:18:43 +00001132 // Now link the LHSBlock with RHSBlock.
John McCall2de56d12010-08-25 11:45:40 +00001133 if (B->getOpcode() == BO_LOr) {
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001134 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock);
1135 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock);
Mike Stump1eb44332009-09-09 15:08:12 +00001136 } else {
John McCall2de56d12010-08-25 11:45:40 +00001137 assert(B->getOpcode() == BO_LAnd);
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001138 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock);
1139 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock);
Ted Kremenek4f880632009-07-17 22:18:43 +00001140 }
Mike Stump1eb44332009-09-09 15:08:12 +00001141
Ted Kremenek4f880632009-07-17 22:18:43 +00001142 // Generate the blocks for evaluating the LHS.
1143 Block = LHSBlock;
1144 return addStmt(B->getLHS());
Mike Stump1eb44332009-09-09 15:08:12 +00001145 }
Zhanyong Wan36f327c2010-11-22 19:32:14 +00001146
1147 if (B->getOpcode() == BO_Comma) { // ,
Ted Kremenek6dc534e2009-07-17 22:57:50 +00001148 autoCreateBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00001149 appendStmt(Block, B);
Ted Kremenek4f880632009-07-17 22:18:43 +00001150 addStmt(B->getRHS());
1151 return addStmt(B->getLHS());
1152 }
Zhanyong Wan36f327c2010-11-22 19:32:14 +00001153
1154 if (B->isAssignmentOp()) {
Ted Kremenek3179a452011-03-10 01:14:11 +00001155 if (asc.alwaysAdd(*this, B)) {
Zhongxing Xufc61d942010-06-03 06:23:18 +00001156 autoCreateBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00001157 appendStmt(Block, B);
Zhongxing Xufc61d942010-06-03 06:23:18 +00001158 }
Ted Kremenek892697d2010-12-16 07:46:53 +00001159 Visit(B->getLHS());
Marcin Swiderskie1667192010-10-24 08:21:40 +00001160 return Visit(B->getRHS());
Zhongxing Xufc61d942010-06-03 06:23:18 +00001161 }
Mike Stump1eb44332009-09-09 15:08:12 +00001162
Ted Kremenek3179a452011-03-10 01:14:11 +00001163 if (asc.alwaysAdd(*this, B)) {
Marcin Swiderskie1667192010-10-24 08:21:40 +00001164 autoCreateBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00001165 appendStmt(Block, B);
Marcin Swiderskie1667192010-10-24 08:21:40 +00001166 }
1167
Zhongxing Xua1898dd2010-10-27 03:23:10 +00001168 CFGBlock *RBlock = Visit(B->getRHS());
1169 CFGBlock *LBlock = Visit(B->getLHS());
1170 // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr
1171 // containing a DoStmt, and the LHS doesn't create a new block, then we should
1172 // return RBlock. Otherwise we'll incorrectly return NULL.
1173 return (LBlock ? LBlock : RBlock);
Ted Kremenek4f880632009-07-17 22:18:43 +00001174}
1175
Ted Kremenek852274d2009-12-16 03:18:58 +00001176CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) {
Ted Kremenek3179a452011-03-10 01:14:11 +00001177 if (asc.alwaysAdd(*this, E)) {
Ted Kremenek721903e2009-11-25 01:34:30 +00001178 autoCreateBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00001179 appendStmt(Block, E);
Ted Kremenek721903e2009-11-25 01:34:30 +00001180 }
1181 return Block;
Ted Kremenek4f880632009-07-17 22:18:43 +00001182}
1183
Ted Kremenek4f880632009-07-17 22:18:43 +00001184CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) {
1185 // "break" is a control-flow statement. Thus we stop processing the current
1186 // block.
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001187 if (badCFG)
1188 return 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001189
Ted Kremenek4f880632009-07-17 22:18:43 +00001190 // Now create a new block that ends with the break statement.
1191 Block = createBlock(false);
1192 Block->setTerminator(B);
Mike Stump1eb44332009-09-09 15:08:12 +00001193
Ted Kremenek4f880632009-07-17 22:18:43 +00001194 // If there is no target for the break, then we are looking at an incomplete
1195 // AST. This means that the CFG cannot be constructed.
Ted Kremenek9ce52702011-01-07 19:37:16 +00001196 if (BreakJumpTarget.block) {
1197 addAutomaticObjDtors(ScopePos, BreakJumpTarget.scopePosition, B);
1198 addSuccessor(Block, BreakJumpTarget.block);
Marcin Swiderskif1308c72010-09-25 11:05:21 +00001199 } else
Ted Kremenek4f880632009-07-17 22:18:43 +00001200 badCFG = true;
Mike Stump1eb44332009-09-09 15:08:12 +00001201
1202
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001203 return Block;
1204}
Mike Stump1eb44332009-09-09 15:08:12 +00001205
Sebastian Redl8026f6d2011-03-13 17:09:40 +00001206static bool CanThrow(Expr *E, ASTContext &Ctx) {
Mike Stump4c45aa12010-01-21 15:20:48 +00001207 QualType Ty = E->getType();
1208 if (Ty->isFunctionPointerType())
1209 Ty = Ty->getAs<PointerType>()->getPointeeType();
1210 else if (Ty->isBlockPointerType())
1211 Ty = Ty->getAs<BlockPointerType>()->getPointeeType();
Ted Kremenekad5a8942010-08-02 23:46:59 +00001212
Mike Stump4c45aa12010-01-21 15:20:48 +00001213 const FunctionType *FT = Ty->getAs<FunctionType>();
1214 if (FT) {
1215 if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT))
Sebastian Redl8026f6d2011-03-13 17:09:40 +00001216 if (Proto->isNothrow(Ctx))
Mike Stump4c45aa12010-01-21 15:20:48 +00001217 return false;
1218 }
1219 return true;
1220}
1221
Ted Kremenek852274d2009-12-16 03:18:58 +00001222CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) {
John McCall1de85332011-05-11 07:19:11 +00001223 // Compute the callee type.
1224 QualType calleeType = C->getCallee()->getType();
1225 if (calleeType == Context->BoundMemberTy) {
1226 QualType boundType = Expr::findBoundMemberType(C->getCallee());
1227
1228 // We should only get a null bound type if processing a dependent
1229 // CFG. Recover by assuming nothing.
1230 if (!boundType.isNull()) calleeType = boundType;
Ted Kremenek4f880632009-07-17 22:18:43 +00001231 }
Mike Stump24556362009-07-25 21:26:53 +00001232
John McCall1de85332011-05-11 07:19:11 +00001233 // If this is a call to a no-return function, this stops the block here.
1234 bool NoReturn = getFunctionExtInfo(*calleeType).getNoReturn();
1235
Mike Stump4c45aa12010-01-21 15:20:48 +00001236 bool AddEHEdge = false;
Mike Stump079bd722010-01-19 22:00:14 +00001237
1238 // Languages without exceptions are assumed to not throw.
Anders Carlsson7a178512011-02-28 00:33:03 +00001239 if (Context->getLangOptions().Exceptions) {
Ted Kremenek6c52c782010-09-14 23:41:16 +00001240 if (BuildOpts.AddEHEdges)
Mike Stump4c45aa12010-01-21 15:20:48 +00001241 AddEHEdge = true;
Mike Stump079bd722010-01-19 22:00:14 +00001242 }
1243
1244 if (FunctionDecl *FD = C->getDirectCallee()) {
Mike Stump24556362009-07-25 21:26:53 +00001245 if (FD->hasAttr<NoReturnAttr>())
1246 NoReturn = true;
Mike Stump079bd722010-01-19 22:00:14 +00001247 if (FD->hasAttr<NoThrowAttr>())
Mike Stump4c45aa12010-01-21 15:20:48 +00001248 AddEHEdge = false;
Mike Stump079bd722010-01-19 22:00:14 +00001249 }
Mike Stump24556362009-07-25 21:26:53 +00001250
Sebastian Redl8026f6d2011-03-13 17:09:40 +00001251 if (!CanThrow(C->getCallee(), *Context))
Mike Stump4c45aa12010-01-21 15:20:48 +00001252 AddEHEdge = false;
1253
Zhanyong Wan94a3dcf2010-11-24 03:28:53 +00001254 if (!NoReturn && !AddEHEdge)
1255 return VisitStmt(C, asc.withAlwaysAdd(true));
Mike Stump1eb44332009-09-09 15:08:12 +00001256
Mike Stump079bd722010-01-19 22:00:14 +00001257 if (Block) {
1258 Succ = Block;
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001259 if (badCFG)
Mike Stump079bd722010-01-19 22:00:14 +00001260 return 0;
1261 }
Mike Stump1eb44332009-09-09 15:08:12 +00001262
Chandler Carruthdba3fb52011-09-13 09:13:49 +00001263 if (NoReturn)
1264 Block = createNoReturnBlock();
1265 else
1266 Block = createBlock();
1267
Ted Kremenek247e9662011-03-10 01:14:08 +00001268 appendStmt(Block, C);
Mike Stump24556362009-07-25 21:26:53 +00001269
Mike Stump4c45aa12010-01-21 15:20:48 +00001270 if (AddEHEdge) {
Mike Stump079bd722010-01-19 22:00:14 +00001271 // Add exceptional edges.
1272 if (TryTerminatedBlock)
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001273 addSuccessor(Block, TryTerminatedBlock);
Mike Stump079bd722010-01-19 22:00:14 +00001274 else
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001275 addSuccessor(Block, &cfg->getExit());
Mike Stump079bd722010-01-19 22:00:14 +00001276 }
Mike Stump1eb44332009-09-09 15:08:12 +00001277
Mike Stump24556362009-07-25 21:26:53 +00001278 return VisitChildren(C);
Ted Kremenek4f880632009-07-17 22:18:43 +00001279}
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001280
Ted Kremenek852274d2009-12-16 03:18:58 +00001281CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C,
1282 AddStmtChoice asc) {
Ted Kremenek9c378f72011-08-12 23:37:29 +00001283 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00001284 appendStmt(ConfluenceBlock, C);
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001285 if (badCFG)
Ted Kremenek3fc8ef52009-07-17 18:20:32 +00001286 return 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001287
Zhanyong Wan94a3dcf2010-11-24 03:28:53 +00001288 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);
Ted Kremenek3fc8ef52009-07-17 18:20:32 +00001289 Succ = ConfluenceBlock;
1290 Block = NULL;
Ted Kremenek9c378f72011-08-12 23:37:29 +00001291 CFGBlock *LHSBlock = Visit(C->getLHS(), alwaysAdd);
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001292 if (badCFG)
Ted Kremenek3fc8ef52009-07-17 18:20:32 +00001293 return 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001294
Ted Kremenek3fc8ef52009-07-17 18:20:32 +00001295 Succ = ConfluenceBlock;
1296 Block = NULL;
Ted Kremenek9c378f72011-08-12 23:37:29 +00001297 CFGBlock *RHSBlock = Visit(C->getRHS(), alwaysAdd);
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001298 if (badCFG)
Ted Kremenek3fc8ef52009-07-17 18:20:32 +00001299 return 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001300
Ted Kremenek3fc8ef52009-07-17 18:20:32 +00001301 Block = createBlock(false);
Mike Stump00998a02009-07-23 23:25:26 +00001302 // See if this is a known constant.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001303 const TryResult& KnownVal = tryEvaluateBool(C->getCond());
1304 addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock);
1305 addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock);
Ted Kremenek3fc8ef52009-07-17 18:20:32 +00001306 Block->setTerminator(C);
Mike Stump1eb44332009-09-09 15:08:12 +00001307 return addStmt(C->getCond());
Ted Kremenek3fc8ef52009-07-17 18:20:32 +00001308}
Mike Stump1eb44332009-09-09 15:08:12 +00001309
1310
Ted Kremenek9c378f72011-08-12 23:37:29 +00001311CFGBlock *CFGBuilder::VisitCompoundStmt(CompoundStmt *C) {
Marcin Swiderskifcb72ac2010-10-01 00:23:17 +00001312 addLocalScopeAndDtors(C);
Ted Kremenek9c378f72011-08-12 23:37:29 +00001313 CFGBlock *LastBlock = Block;
Ted Kremenek4f880632009-07-17 22:18:43 +00001314
1315 for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend();
1316 I != E; ++I ) {
Ted Kremenek334c1952010-08-17 21:00:06 +00001317 // If we hit a segment of code just containing ';' (NullStmts), we can
1318 // get a null block back. In such cases, just use the LastBlock
1319 if (CFGBlock *newBlock = addStmt(*I))
1320 LastBlock = newBlock;
Mike Stump1eb44332009-09-09 15:08:12 +00001321
Ted Kremeneke8d6d2b2009-08-27 23:16:26 +00001322 if (badCFG)
1323 return NULL;
Mike Stump1eb44332009-09-09 15:08:12 +00001324 }
Mike Stump079bd722010-01-19 22:00:14 +00001325
Ted Kremenek4f880632009-07-17 22:18:43 +00001326 return LastBlock;
1327}
Mike Stump1eb44332009-09-09 15:08:12 +00001328
John McCall56ca35d2011-02-17 10:25:35 +00001329CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C,
Ted Kremenek852274d2009-12-16 03:18:58 +00001330 AddStmtChoice asc) {
John McCall56ca35d2011-02-17 10:25:35 +00001331 const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(C);
1332 const OpaqueValueExpr *opaqueValue = (BCO ? BCO->getOpaqueValue() : NULL);
1333
Ted Kremenekf34bb2e2009-07-17 18:15:54 +00001334 // Create the confluence block that will "merge" the results of the ternary
1335 // expression.
Ted Kremenek9c378f72011-08-12 23:37:29 +00001336 CFGBlock *ConfluenceBlock = Block ? Block : createBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00001337 appendStmt(ConfluenceBlock, C);
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001338 if (badCFG)
Ted Kremenekf34bb2e2009-07-17 18:15:54 +00001339 return 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001340
Zhanyong Wan94a3dcf2010-11-24 03:28:53 +00001341 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);
Ted Kremenek115c1b92010-04-11 17:02:10 +00001342
Ted Kremenekf34bb2e2009-07-17 18:15:54 +00001343 // Create a block for the LHS expression if there is an LHS expression. A
1344 // GCC extension allows LHS to be NULL, causing the condition to be the
1345 // value that is returned instead.
1346 // e.g: x ?: y is shorthand for: x ? x : y;
1347 Succ = ConfluenceBlock;
1348 Block = NULL;
Ted Kremenek9c378f72011-08-12 23:37:29 +00001349 CFGBlock *LHSBlock = 0;
John McCall56ca35d2011-02-17 10:25:35 +00001350 const Expr *trueExpr = C->getTrueExpr();
1351 if (trueExpr != opaqueValue) {
1352 LHSBlock = Visit(C->getTrueExpr(), alwaysAdd);
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001353 if (badCFG)
Ted Kremenekf34bb2e2009-07-17 18:15:54 +00001354 return 0;
1355 Block = NULL;
1356 }
Ted Kremenekf226d182011-02-24 03:09:15 +00001357 else
1358 LHSBlock = ConfluenceBlock;
Mike Stump1eb44332009-09-09 15:08:12 +00001359
Ted Kremenekf34bb2e2009-07-17 18:15:54 +00001360 // Create the block for the RHS expression.
1361 Succ = ConfluenceBlock;
Ted Kremenek9c378f72011-08-12 23:37:29 +00001362 CFGBlock *RHSBlock = Visit(C->getFalseExpr(), alwaysAdd);
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001363 if (badCFG)
Ted Kremenekf34bb2e2009-07-17 18:15:54 +00001364 return 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001365
Ted Kremenekf34bb2e2009-07-17 18:15:54 +00001366 // Create the block that will contain the condition.
1367 Block = createBlock(false);
Mike Stump1eb44332009-09-09 15:08:12 +00001368
Mike Stump00998a02009-07-23 23:25:26 +00001369 // See if this is a known constant.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001370 const TryResult& KnownVal = tryEvaluateBool(C->getCond());
Ted Kremenekf226d182011-02-24 03:09:15 +00001371 addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock);
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001372 addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock);
Ted Kremenekf34bb2e2009-07-17 18:15:54 +00001373 Block->setTerminator(C);
John McCall56ca35d2011-02-17 10:25:35 +00001374 Expr *condExpr = C->getCond();
John McCalld40baf62011-02-19 03:13:26 +00001375
Ted Kremenekf226d182011-02-24 03:09:15 +00001376 if (opaqueValue) {
1377 // Run the condition expression if it's not trivially expressed in
1378 // terms of the opaque value (or if there is no opaque value).
1379 if (condExpr != opaqueValue)
1380 addStmt(condExpr);
John McCalld40baf62011-02-19 03:13:26 +00001381
Ted Kremenekf226d182011-02-24 03:09:15 +00001382 // Before that, run the common subexpression if there was one.
1383 // At least one of this or the above will be run.
1384 return addStmt(BCO->getCommon());
1385 }
1386
1387 return addStmt(condExpr);
Ted Kremenekf34bb2e2009-07-17 18:15:54 +00001388}
1389
Ted Kremenek4f880632009-07-17 22:18:43 +00001390CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) {
Ted Kremenekbc869de2011-05-10 18:42:15 +00001391 // Check if the Decl is for an __label__. If so, elide it from the
1392 // CFG entirely.
1393 if (isa<LabelDecl>(*DS->decl_begin()))
1394 return Block;
1395
Ted Kremenek29c9e622011-05-24 20:41:31 +00001396 // This case also handles static_asserts.
Marcin Swiderski8599e762010-11-03 06:19:35 +00001397 if (DS->isSingleDecl())
1398 return VisitDeclSubExpr(DS);
Mike Stump1eb44332009-09-09 15:08:12 +00001399
Ted Kremenek4f880632009-07-17 22:18:43 +00001400 CFGBlock *B = 0;
Mike Stump1eb44332009-09-09 15:08:12 +00001401
Ted Kremenek4f880632009-07-17 22:18:43 +00001402 // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy.
Chris Lattner5f9e2722011-07-23 10:55:15 +00001403 typedef SmallVector<Decl*,10> BufTy;
Ted Kremenek4f880632009-07-17 22:18:43 +00001404 BufTy Buf(DS->decl_begin(), DS->decl_end());
Mike Stump1eb44332009-09-09 15:08:12 +00001405
Ted Kremenek4f880632009-07-17 22:18:43 +00001406 for (BufTy::reverse_iterator I = Buf.rbegin(), E = Buf.rend(); I != E; ++I) {
1407 // Get the alignment of the new DeclStmt, padding out to >=8 bytes.
1408 unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8
1409 ? 8 : llvm::AlignOf<DeclStmt>::Alignment;
Mike Stump1eb44332009-09-09 15:08:12 +00001410
Ted Kremenek4f880632009-07-17 22:18:43 +00001411 // Allocate the DeclStmt using the BumpPtrAllocator. It will get
1412 // automatically freed with the CFG.
1413 DeclGroupRef DG(*I);
1414 Decl *D = *I;
Mike Stump1eb44332009-09-09 15:08:12 +00001415 void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A);
Ted Kremenek4f880632009-07-17 22:18:43 +00001416 DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D));
Mike Stump1eb44332009-09-09 15:08:12 +00001417
Ted Kremenek4f880632009-07-17 22:18:43 +00001418 // Append the fake DeclStmt to block.
Marcin Swiderski8599e762010-11-03 06:19:35 +00001419 B = VisitDeclSubExpr(DSNew);
Ted Kremenek4f880632009-07-17 22:18:43 +00001420 }
Mike Stump1eb44332009-09-09 15:08:12 +00001421
1422 return B;
Ted Kremenek4f880632009-07-17 22:18:43 +00001423}
Mike Stump1eb44332009-09-09 15:08:12 +00001424
Ted Kremenek4f880632009-07-17 22:18:43 +00001425/// VisitDeclSubExpr - Utility method to add block-level expressions for
Marcin Swiderski8599e762010-11-03 06:19:35 +00001426/// DeclStmts and initializers in them.
Ted Kremenek9c378f72011-08-12 23:37:29 +00001427CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) {
Marcin Swiderski8599e762010-11-03 06:19:35 +00001428 assert(DS->isSingleDecl() && "Can handle single declarations only.");
Ted Kremenek29c9e622011-05-24 20:41:31 +00001429 Decl *D = DS->getSingleDecl();
1430
1431 if (isa<StaticAssertDecl>(D)) {
1432 // static_asserts aren't added to the CFG because they do not impact
1433 // runtime semantics.
1434 return Block;
1435 }
1436
Marcin Swiderski8599e762010-11-03 06:19:35 +00001437 VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl());
Mike Stump1eb44332009-09-09 15:08:12 +00001438
Marcin Swiderski8599e762010-11-03 06:19:35 +00001439 if (!VD) {
1440 autoCreateBlock();
Ted Kremenek892697d2010-12-16 07:46:53 +00001441 appendStmt(Block, DS);
Ted Kremenek4f880632009-07-17 22:18:43 +00001442 return Block;
Marcin Swiderski8599e762010-11-03 06:19:35 +00001443 }
Mike Stump1eb44332009-09-09 15:08:12 +00001444
Marcin Swiderski8599e762010-11-03 06:19:35 +00001445 bool IsReference = false;
1446 bool HasTemporaries = false;
1447
1448 // Destructors of temporaries in initialization expression should be called
1449 // after initialization finishes.
Ted Kremenek4f880632009-07-17 22:18:43 +00001450 Expr *Init = VD->getInit();
Marcin Swiderski8599e762010-11-03 06:19:35 +00001451 if (Init) {
1452 IsReference = VD->getType()->isReferenceType();
John McCall4765fa02010-12-06 08:20:24 +00001453 HasTemporaries = isa<ExprWithCleanups>(Init);
Marcin Swiderski8599e762010-11-03 06:19:35 +00001454
1455 if (BuildOpts.AddImplicitDtors && HasTemporaries) {
1456 // Generate destructors for temporaries in initialization expression.
John McCall4765fa02010-12-06 08:20:24 +00001457 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),
Marcin Swiderski8599e762010-11-03 06:19:35 +00001458 IsReference);
1459 }
1460 }
1461
1462 autoCreateBlock();
Ted Kremenek892697d2010-12-16 07:46:53 +00001463 appendStmt(Block, DS);
Mike Stump1eb44332009-09-09 15:08:12 +00001464
Ted Kremenek4f880632009-07-17 22:18:43 +00001465 if (Init) {
Marcin Swiderski8599e762010-11-03 06:19:35 +00001466 if (HasTemporaries)
1467 // For expression with temporaries go directly to subexpression to omit
1468 // generating destructors for the second time.
Ted Kremenek892697d2010-12-16 07:46:53 +00001469 Visit(cast<ExprWithCleanups>(Init)->getSubExpr());
Marcin Swiderski8599e762010-11-03 06:19:35 +00001470 else
Ted Kremenek892697d2010-12-16 07:46:53 +00001471 Visit(Init);
Ted Kremenek4f880632009-07-17 22:18:43 +00001472 }
Mike Stump1eb44332009-09-09 15:08:12 +00001473
Ted Kremenek4f880632009-07-17 22:18:43 +00001474 // If the type of VD is a VLA, then we must process its size expressions.
John McCallf4c73712011-01-19 06:33:43 +00001475 for (const VariableArrayType* VA = FindVA(VD->getType().getTypePtr());
1476 VA != 0; VA = FindVA(VA->getElementType().getTypePtr()))
Ted Kremenek4f880632009-07-17 22:18:43 +00001477 Block = addStmt(VA->getSizeExpr());
Mike Stump1eb44332009-09-09 15:08:12 +00001478
Marcin Swiderskifcb72ac2010-10-01 00:23:17 +00001479 // Remove variable from local scope.
1480 if (ScopePos && VD == *ScopePos)
1481 ++ScopePos;
1482
Ted Kremenek4f880632009-07-17 22:18:43 +00001483 return Block;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001484}
1485
Ted Kremenek9c378f72011-08-12 23:37:29 +00001486CFGBlock *CFGBuilder::VisitIfStmt(IfStmt *I) {
Mike Stump6d9828c2009-07-17 01:31:16 +00001487 // We may see an if statement in the middle of a basic block, or it may be the
1488 // first statement we are processing. In either case, we create a new basic
1489 // block. First, we create the blocks for the then...else statements, and
1490 // then we create the block containing the if statement. If we were in the
Ted Kremenek6c249722009-09-24 18:45:41 +00001491 // middle of a block, we stop processing that block. That block is then the
1492 // implicit successor for the "then" and "else" clauses.
Mike Stump6d9828c2009-07-17 01:31:16 +00001493
Marcin Swiderski04e046c2010-10-01 00:52:17 +00001494 // Save local scope position because in case of condition variable ScopePos
1495 // won't be restored when traversing AST.
1496 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
1497
1498 // Create local scope for possible condition variable.
1499 // Store scope position. Add implicit destructor.
Ted Kremenek9c378f72011-08-12 23:37:29 +00001500 if (VarDecl *VD = I->getConditionVariable()) {
Marcin Swiderski04e046c2010-10-01 00:52:17 +00001501 LocalScope::const_iterator BeginScopePos = ScopePos;
1502 addLocalScopeForVarDecl(VD);
1503 addAutomaticObjDtors(ScopePos, BeginScopePos, I);
1504 }
1505
Chris Lattnerfc8f0e12011-04-15 05:22:18 +00001506 // The block we were processing is now finished. Make it the successor
Mike Stump6d9828c2009-07-17 01:31:16 +00001507 // block.
1508 if (Block) {
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001509 Succ = Block;
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001510 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00001511 return 0;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001512 }
Mike Stump6d9828c2009-07-17 01:31:16 +00001513
Ted Kremenekb6f1d782009-07-17 18:04:55 +00001514 // Process the false branch.
Ted Kremenek9c378f72011-08-12 23:37:29 +00001515 CFGBlock *ElseBlock = Succ;
Mike Stump6d9828c2009-07-17 01:31:16 +00001516
Ted Kremenek9c378f72011-08-12 23:37:29 +00001517 if (Stmt *Else = I->getElse()) {
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001518 SaveAndRestore<CFGBlock*> sv(Succ);
Mike Stump6d9828c2009-07-17 01:31:16 +00001519
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001520 // NULL out Block so that the recursive call to Visit will
Mike Stump6d9828c2009-07-17 01:31:16 +00001521 // create a new basic block.
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001522 Block = NULL;
Marcin Swiderski04e046c2010-10-01 00:52:17 +00001523
1524 // If branch is not a compound statement create implicit scope
1525 // and add destructors.
1526 if (!isa<CompoundStmt>(Else))
1527 addLocalScopeAndDtors(Else);
1528
Ted Kremenek4f880632009-07-17 22:18:43 +00001529 ElseBlock = addStmt(Else);
Mike Stump6d9828c2009-07-17 01:31:16 +00001530
Ted Kremenekb6f7b722007-08-30 18:13:31 +00001531 if (!ElseBlock) // Can occur when the Else body has all NullStmts.
1532 ElseBlock = sv.get();
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00001533 else if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001534 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00001535 return 0;
1536 }
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001537 }
Mike Stump6d9828c2009-07-17 01:31:16 +00001538
Ted Kremenekb6f1d782009-07-17 18:04:55 +00001539 // Process the true branch.
Ted Kremenek9c378f72011-08-12 23:37:29 +00001540 CFGBlock *ThenBlock;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001541 {
Ted Kremenek9c378f72011-08-12 23:37:29 +00001542 Stmt *Then = I->getThen();
Ted Kremenek6db0ad32010-01-19 20:46:35 +00001543 assert(Then);
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001544 SaveAndRestore<CFGBlock*> sv(Succ);
Mike Stump6d9828c2009-07-17 01:31:16 +00001545 Block = NULL;
Marcin Swiderski04e046c2010-10-01 00:52:17 +00001546
1547 // If branch is not a compound statement create implicit scope
1548 // and add destructors.
1549 if (!isa<CompoundStmt>(Then))
1550 addLocalScopeAndDtors(Then);
1551
Ted Kremenek4f880632009-07-17 22:18:43 +00001552 ThenBlock = addStmt(Then);
Mike Stump6d9828c2009-07-17 01:31:16 +00001553
Ted Kremenekdbdf7942009-04-01 03:52:47 +00001554 if (!ThenBlock) {
1555 // We can reach here if the "then" body has all NullStmts.
1556 // Create an empty block so we can distinguish between true and false
1557 // branches in path-sensitive analyses.
1558 ThenBlock = createBlock(false);
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001559 addSuccessor(ThenBlock, sv.get());
Mike Stump6d9828c2009-07-17 01:31:16 +00001560 } else if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001561 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00001562 return 0;
Mike Stump6d9828c2009-07-17 01:31:16 +00001563 }
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001564 }
1565
Mike Stump6d9828c2009-07-17 01:31:16 +00001566 // Now create a new block containing the if statement.
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001567 Block = createBlock(false);
Mike Stump6d9828c2009-07-17 01:31:16 +00001568
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001569 // Set the terminator of the new block to the If statement.
1570 Block->setTerminator(I);
Mike Stump6d9828c2009-07-17 01:31:16 +00001571
Mike Stump00998a02009-07-23 23:25:26 +00001572 // See if this is a known constant.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001573 const TryResult &KnownVal = tryEvaluateBool(I->getCond());
Mike Stump00998a02009-07-23 23:25:26 +00001574
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001575 // Now add the successors.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001576 addSuccessor(Block, KnownVal.isFalse() ? NULL : ThenBlock);
1577 addSuccessor(Block, KnownVal.isTrue()? NULL : ElseBlock);
Mike Stump6d9828c2009-07-17 01:31:16 +00001578
1579 // Add the condition as the last statement in the new block. This may create
1580 // new blocks as the condition may contain control-flow. Any newly created
1581 // blocks will be pointed to be "Block".
Ted Kremenek61dfbec2009-12-23 04:49:01 +00001582 Block = addStmt(I->getCond());
Ted Kremenekad5a8942010-08-02 23:46:59 +00001583
Ted Kremenek61dfbec2009-12-23 04:49:01 +00001584 // Finally, if the IfStmt contains a condition variable, add both the IfStmt
1585 // and the condition variable initialization to the CFG.
1586 if (VarDecl *VD = I->getConditionVariable()) {
1587 if (Expr *Init = VD->getInit()) {
1588 autoCreateBlock();
Ted Kremenekd40066b2011-04-04 23:29:12 +00001589 appendStmt(Block, I->getConditionVariableDeclStmt());
Ted Kremenek61dfbec2009-12-23 04:49:01 +00001590 addStmt(Init);
1591 }
1592 }
Ted Kremenekad5a8942010-08-02 23:46:59 +00001593
Ted Kremenek61dfbec2009-12-23 04:49:01 +00001594 return Block;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001595}
Mike Stump6d9828c2009-07-17 01:31:16 +00001596
1597
Ted Kremenek9c378f72011-08-12 23:37:29 +00001598CFGBlock *CFGBuilder::VisitReturnStmt(ReturnStmt *R) {
Ted Kremenek6c249722009-09-24 18:45:41 +00001599 // If we were in the middle of a block we stop processing that block.
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001600 //
Mike Stump6d9828c2009-07-17 01:31:16 +00001601 // NOTE: If a "return" appears in the middle of a block, this means that the
1602 // code afterwards is DEAD (unreachable). We still keep a basic block
1603 // for that code; a simple "mark-and-sweep" from the entry block will be
1604 // able to report such dead blocks.
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001605
1606 // Create the new block.
1607 Block = createBlock(false);
Mike Stump6d9828c2009-07-17 01:31:16 +00001608
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001609 // The Exit block is the only successor.
Marcin Swiderskifcb72ac2010-10-01 00:23:17 +00001610 addAutomaticObjDtors(ScopePos, LocalScope::const_iterator(), R);
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001611 addSuccessor(Block, &cfg->getExit());
Mike Stump6d9828c2009-07-17 01:31:16 +00001612
1613 // Add the return statement to the block. This may create new blocks if R
1614 // contains control-flow (short-circuit operations).
Ted Kremenek852274d2009-12-16 03:18:58 +00001615 return VisitStmt(R, AddStmtChoice::AlwaysAdd);
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001616}
1617
Ted Kremenek9c378f72011-08-12 23:37:29 +00001618CFGBlock *CFGBuilder::VisitLabelStmt(LabelStmt *L) {
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001619 // Get the block of the labeled statement. Add it to our map.
Ted Kremenek4f880632009-07-17 22:18:43 +00001620 addStmt(L->getSubStmt());
Chris Lattnerad8dcf42011-02-17 07:39:24 +00001621 CFGBlock *LabelBlock = Block;
Mike Stump6d9828c2009-07-17 01:31:16 +00001622
Ted Kremenek4f880632009-07-17 22:18:43 +00001623 if (!LabelBlock) // This can happen when the body is empty, i.e.
1624 LabelBlock = createBlock(); // scopes that only contains NullStmts.
Mike Stump6d9828c2009-07-17 01:31:16 +00001625
Chris Lattnerad8dcf42011-02-17 07:39:24 +00001626 assert(LabelMap.find(L->getDecl()) == LabelMap.end() &&
1627 "label already in map");
1628 LabelMap[L->getDecl()] = JumpTarget(LabelBlock, ScopePos);
Mike Stump6d9828c2009-07-17 01:31:16 +00001629
1630 // Labels partition blocks, so this is the end of the basic block we were
1631 // processing (L is the block's label). Because this is label (and we have
1632 // already processed the substatement) there is no extra control-flow to worry
1633 // about.
Ted Kremenek9cffe732007-08-29 23:20:49 +00001634 LabelBlock->setLabel(L);
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001635 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00001636 return 0;
Mike Stump6d9828c2009-07-17 01:31:16 +00001637
1638 // We set Block to NULL to allow lazy creation of a new block (if necessary);
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001639 Block = NULL;
Mike Stump6d9828c2009-07-17 01:31:16 +00001640
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001641 // This block is now the implicit successor of other blocks.
1642 Succ = LabelBlock;
Mike Stump6d9828c2009-07-17 01:31:16 +00001643
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001644 return LabelBlock;
1645}
1646
Ted Kremenek9c378f72011-08-12 23:37:29 +00001647CFGBlock *CFGBuilder::VisitGotoStmt(GotoStmt *G) {
Mike Stump6d9828c2009-07-17 01:31:16 +00001648 // Goto is a control-flow statement. Thus we stop processing the current
1649 // block and create a new one.
Ted Kremenek4f880632009-07-17 22:18:43 +00001650
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001651 Block = createBlock(false);
1652 Block->setTerminator(G);
Mike Stump6d9828c2009-07-17 01:31:16 +00001653
1654 // If we already know the mapping to the label block add the successor now.
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001655 LabelMapTy::iterator I = LabelMap.find(G->getLabel());
Mike Stump6d9828c2009-07-17 01:31:16 +00001656
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001657 if (I == LabelMap.end())
1658 // We will need to backpatch this block later.
Marcin Swiderskif1308c72010-09-25 11:05:21 +00001659 BackpatchBlocks.push_back(JumpSource(Block, ScopePos));
1660 else {
1661 JumpTarget JT = I->second;
Ted Kremenek9ce52702011-01-07 19:37:16 +00001662 addAutomaticObjDtors(ScopePos, JT.scopePosition, G);
1663 addSuccessor(Block, JT.block);
Marcin Swiderskif1308c72010-09-25 11:05:21 +00001664 }
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001665
Mike Stump6d9828c2009-07-17 01:31:16 +00001666 return Block;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001667}
1668
Ted Kremenek9c378f72011-08-12 23:37:29 +00001669CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) {
1670 CFGBlock *LoopSuccessor = NULL;
Mike Stump6d9828c2009-07-17 01:31:16 +00001671
Marcin Swiderski47575f12010-10-01 01:38:14 +00001672 // Save local scope position because in case of condition variable ScopePos
1673 // won't be restored when traversing AST.
1674 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
1675
1676 // Create local scope for init statement and possible condition variable.
1677 // Add destructor for init statement and condition variable.
1678 // Store scope position for continue statement.
Ted Kremenek9c378f72011-08-12 23:37:29 +00001679 if (Stmt *Init = F->getInit())
Marcin Swiderski47575f12010-10-01 01:38:14 +00001680 addLocalScopeForStmt(Init);
Marcin Swiderskif1308c72010-09-25 11:05:21 +00001681 LocalScope::const_iterator LoopBeginScopePos = ScopePos;
1682
Ted Kremenek9c378f72011-08-12 23:37:29 +00001683 if (VarDecl *VD = F->getConditionVariable())
Marcin Swiderski47575f12010-10-01 01:38:14 +00001684 addLocalScopeForVarDecl(VD);
1685 LocalScope::const_iterator ContinueScopePos = ScopePos;
1686
1687 addAutomaticObjDtors(ScopePos, save_scope_pos.get(), F);
1688
Mike Stumpfefb9f72009-07-21 01:12:51 +00001689 // "for" is a control-flow statement. Thus we stop processing the current
1690 // block.
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001691 if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001692 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00001693 return 0;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001694 LoopSuccessor = Block;
Ted Kremenek4f880632009-07-17 22:18:43 +00001695 } else
1696 LoopSuccessor = Succ;
Mike Stump6d9828c2009-07-17 01:31:16 +00001697
Ted Kremenek3f64a0e2010-05-21 20:30:15 +00001698 // Save the current value for the break targets.
1699 // All breaks should go to the code following the loop.
Marcin Swiderskif1308c72010-09-25 11:05:21 +00001700 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
Marcin Swiderski47575f12010-10-01 01:38:14 +00001701 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
Ted Kremenek3f64a0e2010-05-21 20:30:15 +00001702
Mike Stump6d9828c2009-07-17 01:31:16 +00001703 // Because of short-circuit evaluation, the condition of the loop can span
1704 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
1705 // evaluate the condition.
Ted Kremenek9c378f72011-08-12 23:37:29 +00001706 CFGBlock *ExitConditionBlock = createBlock(false);
1707 CFGBlock *EntryConditionBlock = ExitConditionBlock;
Mike Stump6d9828c2009-07-17 01:31:16 +00001708
Ted Kremenek49af7cb2007-08-27 19:46:09 +00001709 // Set the terminator for the "exit" condition block.
Mike Stump6d9828c2009-07-17 01:31:16 +00001710 ExitConditionBlock->setTerminator(F);
1711
1712 // Now add the actual condition to the condition block. Because the condition
1713 // itself may contain control-flow, new blocks may be created.
Ted Kremenek9c378f72011-08-12 23:37:29 +00001714 if (Stmt *C = F->getCond()) {
Ted Kremenek49af7cb2007-08-27 19:46:09 +00001715 Block = ExitConditionBlock;
1716 EntryConditionBlock = addStmt(C);
Ted Kremenek9ce52702011-01-07 19:37:16 +00001717 if (badCFG)
1718 return 0;
Ted Kremenek8f3b8342010-09-15 07:01:20 +00001719 assert(Block == EntryConditionBlock ||
1720 (Block == 0 && EntryConditionBlock == Succ));
Ted Kremenek58b87fe2009-12-24 01:49:06 +00001721
1722 // If this block contains a condition variable, add both the condition
1723 // variable and initializer to the CFG.
1724 if (VarDecl *VD = F->getConditionVariable()) {
1725 if (Expr *Init = VD->getInit()) {
1726 autoCreateBlock();
Ted Kremenekd40066b2011-04-04 23:29:12 +00001727 appendStmt(Block, F->getConditionVariableDeclStmt());
Ted Kremenek58b87fe2009-12-24 01:49:06 +00001728 EntryConditionBlock = addStmt(Init);
1729 assert(Block == EntryConditionBlock);
1730 }
1731 }
Ted Kremenekad5a8942010-08-02 23:46:59 +00001732
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00001733 if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001734 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00001735 return 0;
1736 }
Ted Kremenek49af7cb2007-08-27 19:46:09 +00001737 }
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001738
Mike Stump6d9828c2009-07-17 01:31:16 +00001739 // The condition block is the implicit successor for the loop body as well as
1740 // any code above the loop.
Ted Kremenek49af7cb2007-08-27 19:46:09 +00001741 Succ = EntryConditionBlock;
Mike Stump6d9828c2009-07-17 01:31:16 +00001742
Mike Stump00998a02009-07-23 23:25:26 +00001743 // See if this is a known constant.
Ted Kremenek941fde82009-07-24 04:47:11 +00001744 TryResult KnownVal(true);
Mike Stump1eb44332009-09-09 15:08:12 +00001745
Mike Stump00998a02009-07-23 23:25:26 +00001746 if (F->getCond())
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001747 KnownVal = tryEvaluateBool(F->getCond());
Mike Stump00998a02009-07-23 23:25:26 +00001748
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001749 // Now create the loop body.
1750 {
Ted Kremenek6db0ad32010-01-19 20:46:35 +00001751 assert(F->getBody());
Mike Stump6d9828c2009-07-17 01:31:16 +00001752
Ted Kremenek3f64a0e2010-05-21 20:30:15 +00001753 // Save the current values for Block, Succ, and continue targets.
Marcin Swiderskif1308c72010-09-25 11:05:21 +00001754 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
1755 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget);
Mike Stump6d9828c2009-07-17 01:31:16 +00001756
Ted Kremenekaf603f72007-08-30 18:39:40 +00001757 // Create a new block to contain the (bottom) of the loop body.
1758 Block = NULL;
Marcin Swiderski47575f12010-10-01 01:38:14 +00001759
1760 // Loop body should end with destructor of Condition variable (if any).
1761 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, F);
Mike Stump6d9828c2009-07-17 01:31:16 +00001762
Ted Kremenek9c378f72011-08-12 23:37:29 +00001763 if (Stmt *I = F->getInc()) {
Mike Stump6d9828c2009-07-17 01:31:16 +00001764 // Generate increment code in its own basic block. This is the target of
1765 // continue statements.
Ted Kremenek4f880632009-07-17 22:18:43 +00001766 Succ = addStmt(I);
Mike Stump6d9828c2009-07-17 01:31:16 +00001767 } else {
1768 // No increment code. Create a special, empty, block that is used as the
1769 // target block for "looping back" to the start of the loop.
Ted Kremenek3575f842009-04-28 00:51:56 +00001770 assert(Succ == EntryConditionBlock);
Marcin Swiderski47575f12010-10-01 01:38:14 +00001771 Succ = Block ? Block : createBlock();
Ted Kremeneke9334502008-09-04 21:48:47 +00001772 }
Mike Stump6d9828c2009-07-17 01:31:16 +00001773
Ted Kremenek3575f842009-04-28 00:51:56 +00001774 // Finish up the increment (or empty) block if it hasn't been already.
1775 if (Block) {
1776 assert(Block == Succ);
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001777 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00001778 return 0;
Ted Kremenek3575f842009-04-28 00:51:56 +00001779 Block = 0;
1780 }
Mike Stump6d9828c2009-07-17 01:31:16 +00001781
Marcin Swiderski47575f12010-10-01 01:38:14 +00001782 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
Mike Stump6d9828c2009-07-17 01:31:16 +00001783
Ted Kremenek3575f842009-04-28 00:51:56 +00001784 // The starting block for the loop increment is the block that should
1785 // represent the 'loop target' for looping back to the start of the loop.
Ted Kremenek9ce52702011-01-07 19:37:16 +00001786 ContinueJumpTarget.block->setLoopTarget(F);
Ted Kremenek3575f842009-04-28 00:51:56 +00001787
Marcin Swiderski47575f12010-10-01 01:38:14 +00001788 // If body is not a compound statement create implicit scope
1789 // and add destructors.
1790 if (!isa<CompoundStmt>(F->getBody()))
1791 addLocalScopeAndDtors(F->getBody());
1792
Mike Stump6d9828c2009-07-17 01:31:16 +00001793 // Now populate the body block, and in the process create new blocks as we
1794 // walk the body of the loop.
Ted Kremenek9c378f72011-08-12 23:37:29 +00001795 CFGBlock *BodyBlock = addStmt(F->getBody());
Ted Kremenekaf603f72007-08-30 18:39:40 +00001796
1797 if (!BodyBlock)
Ted Kremenek9ce52702011-01-07 19:37:16 +00001798 BodyBlock = ContinueJumpTarget.block;//can happen for "for (...;...;...);"
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001799 else if (badCFG)
Ted Kremenek941fde82009-07-24 04:47:11 +00001800 return 0;
Mike Stump6d9828c2009-07-17 01:31:16 +00001801
Ted Kremenek941fde82009-07-24 04:47:11 +00001802 // This new body block is a successor to our "exit" condition block.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001803 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock);
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001804 }
Mike Stump6d9828c2009-07-17 01:31:16 +00001805
Ted Kremenek941fde82009-07-24 04:47:11 +00001806 // Link up the condition block with the code that follows the loop. (the
1807 // false branch).
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001808 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor);
Mike Stump6d9828c2009-07-17 01:31:16 +00001809
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001810 // If the loop contains initialization, create a new block for those
Mike Stump6d9828c2009-07-17 01:31:16 +00001811 // statements. This block can also contain statements that precede the loop.
Ted Kremenek9c378f72011-08-12 23:37:29 +00001812 if (Stmt *I = F->getInit()) {
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001813 Block = createBlock();
Ted Kremenek49af7cb2007-08-27 19:46:09 +00001814 return addStmt(I);
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001815 }
Zhanyong Wan36f327c2010-11-22 19:32:14 +00001816
1817 // There is no loop initialization. We are thus basically a while loop.
1818 // NULL out Block to force lazy block construction.
1819 Block = NULL;
1820 Succ = EntryConditionBlock;
1821 return EntryConditionBlock;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001822}
1823
Ted Kremenek115c1b92010-04-11 17:02:10 +00001824CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) {
Ted Kremenek3179a452011-03-10 01:14:11 +00001825 if (asc.alwaysAdd(*this, M)) {
Ted Kremenek115c1b92010-04-11 17:02:10 +00001826 autoCreateBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00001827 appendStmt(Block, M);
Ted Kremenek115c1b92010-04-11 17:02:10 +00001828 }
Ted Kremenek892697d2010-12-16 07:46:53 +00001829 return Visit(M->getBase());
Ted Kremenek115c1b92010-04-11 17:02:10 +00001830}
1831
Ted Kremenek9c378f72011-08-12 23:37:29 +00001832CFGBlock *CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt *S) {
Ted Kremenek514de5a2008-11-11 17:10:00 +00001833 // Objective-C fast enumeration 'for' statements:
1834 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC
1835 //
1836 // for ( Type newVariable in collection_expression ) { statements }
1837 //
1838 // becomes:
1839 //
1840 // prologue:
1841 // 1. collection_expression
1842 // T. jump to loop_entry
1843 // loop_entry:
Ted Kremenek4cb3a852008-11-14 01:57:41 +00001844 // 1. side-effects of element expression
Ted Kremenek514de5a2008-11-11 17:10:00 +00001845 // 1. ObjCForCollectionStmt [performs binding to newVariable]
1846 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil]
1847 // TB:
1848 // statements
1849 // T. jump to loop_entry
1850 // FB:
1851 // what comes after
1852 //
1853 // and
1854 //
1855 // Type existingItem;
1856 // for ( existingItem in expression ) { statements }
1857 //
1858 // becomes:
1859 //
Mike Stump6d9828c2009-07-17 01:31:16 +00001860 // the same with newVariable replaced with existingItem; the binding works
1861 // the same except that for one ObjCForCollectionStmt::getElement() returns
1862 // a DeclStmt and the other returns a DeclRefExpr.
Ted Kremenek514de5a2008-11-11 17:10:00 +00001863 //
Mike Stump6d9828c2009-07-17 01:31:16 +00001864
Ted Kremenek9c378f72011-08-12 23:37:29 +00001865 CFGBlock *LoopSuccessor = 0;
Mike Stump6d9828c2009-07-17 01:31:16 +00001866
Ted Kremenek514de5a2008-11-11 17:10:00 +00001867 if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001868 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00001869 return 0;
Ted Kremenek514de5a2008-11-11 17:10:00 +00001870 LoopSuccessor = Block;
1871 Block = 0;
Ted Kremenek4f880632009-07-17 22:18:43 +00001872 } else
1873 LoopSuccessor = Succ;
Mike Stump6d9828c2009-07-17 01:31:16 +00001874
Ted Kremenek4cb3a852008-11-14 01:57:41 +00001875 // Build the condition blocks.
Ted Kremenek9c378f72011-08-12 23:37:29 +00001876 CFGBlock *ExitConditionBlock = createBlock(false);
Mike Stump6d9828c2009-07-17 01:31:16 +00001877
Ted Kremenek4cb3a852008-11-14 01:57:41 +00001878 // Set the terminator for the "exit" condition block.
Mike Stump6d9828c2009-07-17 01:31:16 +00001879 ExitConditionBlock->setTerminator(S);
1880
1881 // The last statement in the block should be the ObjCForCollectionStmt, which
1882 // performs the actual binding to 'element' and determines if there are any
1883 // more items in the collection.
Ted Kremenek892697d2010-12-16 07:46:53 +00001884 appendStmt(ExitConditionBlock, S);
Ted Kremenek4cb3a852008-11-14 01:57:41 +00001885 Block = ExitConditionBlock;
Mike Stump6d9828c2009-07-17 01:31:16 +00001886
Ted Kremenek4cb3a852008-11-14 01:57:41 +00001887 // Walk the 'element' expression to see if there are any side-effects. We
Chris Lattnerfc8f0e12011-04-15 05:22:18 +00001888 // generate new blocks as necessary. We DON'T add the statement by default to
Mike Stump6d9828c2009-07-17 01:31:16 +00001889 // the CFG unless it contains control-flow.
Ted Kremenek012614e2011-08-17 21:04:19 +00001890 CFGBlock *EntryConditionBlock = Visit(S->getElement(),
1891 AddStmtChoice::NotAlwaysAdd);
Mike Stump6d9828c2009-07-17 01:31:16 +00001892 if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001893 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00001894 return 0;
1895 Block = 0;
1896 }
Mike Stump6d9828c2009-07-17 01:31:16 +00001897
1898 // The condition block is the implicit successor for the loop body as well as
1899 // any code above the loop.
Ted Kremenek4cb3a852008-11-14 01:57:41 +00001900 Succ = EntryConditionBlock;
Mike Stump6d9828c2009-07-17 01:31:16 +00001901
Ted Kremenek514de5a2008-11-11 17:10:00 +00001902 // Now create the true branch.
Mike Stump6d9828c2009-07-17 01:31:16 +00001903 {
Ted Kremenek4cb3a852008-11-14 01:57:41 +00001904 // Save the current values for Succ, continue and break targets.
Marcin Swiderskif1308c72010-09-25 11:05:21 +00001905 SaveAndRestore<CFGBlock*> save_Succ(Succ);
1906 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
1907 save_break(BreakJumpTarget);
Mike Stump6d9828c2009-07-17 01:31:16 +00001908
Marcin Swiderskif1308c72010-09-25 11:05:21 +00001909 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
1910 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos);
Mike Stump6d9828c2009-07-17 01:31:16 +00001911
Ted Kremenek9c378f72011-08-12 23:37:29 +00001912 CFGBlock *BodyBlock = addStmt(S->getBody());
Mike Stump6d9828c2009-07-17 01:31:16 +00001913
Ted Kremenek4cb3a852008-11-14 01:57:41 +00001914 if (!BodyBlock)
1915 BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;"
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00001916 else if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001917 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00001918 return 0;
1919 }
Mike Stump6d9828c2009-07-17 01:31:16 +00001920
Ted Kremenek4cb3a852008-11-14 01:57:41 +00001921 // This new body block is a successor to our "exit" condition block.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001922 addSuccessor(ExitConditionBlock, BodyBlock);
Ted Kremenek4cb3a852008-11-14 01:57:41 +00001923 }
Mike Stump6d9828c2009-07-17 01:31:16 +00001924
Ted Kremenek4cb3a852008-11-14 01:57:41 +00001925 // Link up the condition block with the code that follows the loop.
1926 // (the false branch).
Ted Kremenek0a3ed312010-12-17 04:44:39 +00001927 addSuccessor(ExitConditionBlock, LoopSuccessor);
Ted Kremenek4cb3a852008-11-14 01:57:41 +00001928
Ted Kremenek514de5a2008-11-11 17:10:00 +00001929 // Now create a prologue block to contain the collection expression.
Ted Kremenek4cb3a852008-11-14 01:57:41 +00001930 Block = createBlock();
Ted Kremenek514de5a2008-11-11 17:10:00 +00001931 return addStmt(S->getCollection());
Mike Stump6d9828c2009-07-17 01:31:16 +00001932}
1933
Ted Kremenek9c378f72011-08-12 23:37:29 +00001934CFGBlock *CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S) {
Ted Kremenekb3b0b362009-05-02 01:49:13 +00001935 // FIXME: Add locking 'primitives' to CFG for @synchronized.
Mike Stump6d9828c2009-07-17 01:31:16 +00001936
Ted Kremenekb3b0b362009-05-02 01:49:13 +00001937 // Inline the body.
Ted Kremenek4f880632009-07-17 22:18:43 +00001938 CFGBlock *SyncBlock = addStmt(S->getSynchBody());
Mike Stump6d9828c2009-07-17 01:31:16 +00001939
Ted Kremenekda5348e2009-05-05 23:11:51 +00001940 // The sync body starts its own basic block. This makes it a little easier
1941 // for diagnostic clients.
1942 if (SyncBlock) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00001943 if (badCFG)
Ted Kremenekda5348e2009-05-05 23:11:51 +00001944 return 0;
Mike Stump6d9828c2009-07-17 01:31:16 +00001945
Ted Kremenekda5348e2009-05-05 23:11:51 +00001946 Block = 0;
Ted Kremenekfadebba2010-05-13 16:38:08 +00001947 Succ = SyncBlock;
Ted Kremenekda5348e2009-05-05 23:11:51 +00001948 }
Mike Stump6d9828c2009-07-17 01:31:16 +00001949
Ted Kremenek4beaa9f2010-09-10 03:05:33 +00001950 // Add the @synchronized to the CFG.
1951 autoCreateBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00001952 appendStmt(Block, S);
Ted Kremenek4beaa9f2010-09-10 03:05:33 +00001953
Ted Kremenekb3b0b362009-05-02 01:49:13 +00001954 // Inline the sync expression.
Ted Kremenek4f880632009-07-17 22:18:43 +00001955 return addStmt(S->getSynchExpr());
Ted Kremenekb3b0b362009-05-02 01:49:13 +00001956}
Mike Stump6d9828c2009-07-17 01:31:16 +00001957
Ted Kremenek9c378f72011-08-12 23:37:29 +00001958CFGBlock *CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt *S) {
Ted Kremenek4f880632009-07-17 22:18:43 +00001959 // FIXME
Ted Kremenek90658ec2009-04-07 04:26:02 +00001960 return NYS();
Ted Kremeneke31c0d22009-03-30 22:29:21 +00001961}
Ted Kremenek514de5a2008-11-11 17:10:00 +00001962
John McCall4b9c2d22011-11-06 09:01:30 +00001963CFGBlock *CFGBuilder::VisitPseudoObjectExpr(PseudoObjectExpr *E) {
1964 autoCreateBlock();
1965
1966 // Add the PseudoObject as the last thing.
1967 appendStmt(Block, E);
1968
1969 CFGBlock *lastBlock = Block;
1970
1971 // Before that, evaluate all of the semantics in order. In
1972 // CFG-land, that means appending them in reverse order.
1973 for (unsigned i = E->getNumSemanticExprs(); i != 0; ) {
1974 Expr *Semantic = E->getSemanticExpr(--i);
1975
1976 // If the semantic is an opaque value, we're being asked to bind
1977 // it to its source expression.
1978 if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic))
1979 Semantic = OVE->getSourceExpr();
1980
1981 if (CFGBlock *B = Visit(Semantic))
1982 lastBlock = B;
1983 }
1984
1985 return lastBlock;
1986}
1987
Ted Kremenek9c378f72011-08-12 23:37:29 +00001988CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) {
1989 CFGBlock *LoopSuccessor = NULL;
Mike Stump6d9828c2009-07-17 01:31:16 +00001990
Marcin Swiderski05adedc2010-10-01 01:14:17 +00001991 // Save local scope position because in case of condition variable ScopePos
1992 // won't be restored when traversing AST.
1993 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
1994
1995 // Create local scope for possible condition variable.
1996 // Store scope position for continue statement.
Marcin Swiderskif1308c72010-09-25 11:05:21 +00001997 LocalScope::const_iterator LoopBeginScopePos = ScopePos;
Ted Kremenek9c378f72011-08-12 23:37:29 +00001998 if (VarDecl *VD = W->getConditionVariable()) {
Marcin Swiderski05adedc2010-10-01 01:14:17 +00001999 addLocalScopeForVarDecl(VD);
2000 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W);
2001 }
Marcin Swiderskif1308c72010-09-25 11:05:21 +00002002
Mike Stumpfefb9f72009-07-21 01:12:51 +00002003 // "while" is a control-flow statement. Thus we stop processing the current
2004 // block.
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002005 if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002006 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00002007 return 0;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002008 LoopSuccessor = Block;
Ted Kremenek6b12da92011-02-21 22:11:26 +00002009 Block = 0;
Ted Kremenek4f880632009-07-17 22:18:43 +00002010 } else
2011 LoopSuccessor = Succ;
Mike Stump6d9828c2009-07-17 01:31:16 +00002012
2013 // Because of short-circuit evaluation, the condition of the loop can span
2014 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
2015 // evaluate the condition.
Ted Kremenek9c378f72011-08-12 23:37:29 +00002016 CFGBlock *ExitConditionBlock = createBlock(false);
2017 CFGBlock *EntryConditionBlock = ExitConditionBlock;
Mike Stump6d9828c2009-07-17 01:31:16 +00002018
Ted Kremenek49af7cb2007-08-27 19:46:09 +00002019 // Set the terminator for the "exit" condition block.
2020 ExitConditionBlock->setTerminator(W);
Mike Stump6d9828c2009-07-17 01:31:16 +00002021
2022 // Now add the actual condition to the condition block. Because the condition
2023 // itself may contain control-flow, new blocks may be created. Thus we update
2024 // "Succ" after adding the condition.
Ted Kremenek9c378f72011-08-12 23:37:29 +00002025 if (Stmt *C = W->getCond()) {
Ted Kremenek49af7cb2007-08-27 19:46:09 +00002026 Block = ExitConditionBlock;
2027 EntryConditionBlock = addStmt(C);
Zhongxing Xua1898dd2010-10-27 03:23:10 +00002028 // The condition might finish the current 'Block'.
2029 Block = EntryConditionBlock;
Ted Kremenekad5a8942010-08-02 23:46:59 +00002030
Ted Kremenek4ec010a2009-12-24 01:34:10 +00002031 // If this block contains a condition variable, add both the condition
2032 // variable and initializer to the CFG.
2033 if (VarDecl *VD = W->getConditionVariable()) {
2034 if (Expr *Init = VD->getInit()) {
2035 autoCreateBlock();
Ted Kremenekd40066b2011-04-04 23:29:12 +00002036 appendStmt(Block, W->getConditionVariableDeclStmt());
Ted Kremenek4ec010a2009-12-24 01:34:10 +00002037 EntryConditionBlock = addStmt(Init);
2038 assert(Block == EntryConditionBlock);
2039 }
2040 }
2041
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00002042 if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002043 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00002044 return 0;
2045 }
Ted Kremenek49af7cb2007-08-27 19:46:09 +00002046 }
Mike Stump6d9828c2009-07-17 01:31:16 +00002047
2048 // The condition block is the implicit successor for the loop body as well as
2049 // any code above the loop.
Ted Kremenek49af7cb2007-08-27 19:46:09 +00002050 Succ = EntryConditionBlock;
Mike Stump6d9828c2009-07-17 01:31:16 +00002051
Mike Stump00998a02009-07-23 23:25:26 +00002052 // See if this is a known constant.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002053 const TryResult& KnownVal = tryEvaluateBool(W->getCond());
Mike Stump00998a02009-07-23 23:25:26 +00002054
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002055 // Process the loop body.
2056 {
Ted Kremenekf6e85412009-04-28 03:09:44 +00002057 assert(W->getBody());
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002058
2059 // Save the current values for Block, Succ, and continue and break targets
Marcin Swiderskif1308c72010-09-25 11:05:21 +00002060 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
2061 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
2062 save_break(BreakJumpTarget);
Ted Kremenekf6e85412009-04-28 03:09:44 +00002063
Mike Stump6d9828c2009-07-17 01:31:16 +00002064 // Create an empty block to represent the transition block for looping back
2065 // to the head of the loop.
Ted Kremenekf6e85412009-04-28 03:09:44 +00002066 Block = 0;
2067 assert(Succ == EntryConditionBlock);
2068 Succ = createBlock();
2069 Succ->setLoopTarget(W);
Marcin Swiderskif1308c72010-09-25 11:05:21 +00002070 ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos);
Mike Stump6d9828c2009-07-17 01:31:16 +00002071
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002072 // All breaks should go to the code following the loop.
Marcin Swiderski05adedc2010-10-01 01:14:17 +00002073 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
Mike Stump6d9828c2009-07-17 01:31:16 +00002074
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002075 // NULL out Block to force lazy instantiation of blocks for the body.
2076 Block = NULL;
Mike Stump6d9828c2009-07-17 01:31:16 +00002077
Marcin Swiderski05adedc2010-10-01 01:14:17 +00002078 // Loop body should end with destructor of Condition variable (if any).
2079 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W);
2080
2081 // If body is not a compound statement create implicit scope
2082 // and add destructors.
2083 if (!isa<CompoundStmt>(W->getBody()))
2084 addLocalScopeAndDtors(W->getBody());
2085
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002086 // Create the body. The returned block is the entry to the loop body.
Ted Kremenek9c378f72011-08-12 23:37:29 +00002087 CFGBlock *BodyBlock = addStmt(W->getBody());
Mike Stump6d9828c2009-07-17 01:31:16 +00002088
Ted Kremenekaf603f72007-08-30 18:39:40 +00002089 if (!BodyBlock)
Ted Kremenek9ce52702011-01-07 19:37:16 +00002090 BodyBlock = ContinueJumpTarget.block; // can happen for "while(...) ;"
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00002091 else if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002092 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00002093 return 0;
2094 }
Mike Stump6d9828c2009-07-17 01:31:16 +00002095
Ted Kremenek941fde82009-07-24 04:47:11 +00002096 // Add the loop body entry as a successor to the condition.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002097 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock);
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002098 }
Mike Stump6d9828c2009-07-17 01:31:16 +00002099
Ted Kremenek941fde82009-07-24 04:47:11 +00002100 // Link up the condition block with the code that follows the loop. (the
2101 // false branch).
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002102 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor);
Mike Stump6d9828c2009-07-17 01:31:16 +00002103
2104 // There can be no more statements in the condition block since we loop back
2105 // to this block. NULL out Block to force lazy creation of another block.
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002106 Block = NULL;
Mike Stump6d9828c2009-07-17 01:31:16 +00002107
Ted Kremenek4ec010a2009-12-24 01:34:10 +00002108 // Return the condition block, which is the dominating block for the loop.
Ted Kremenek54827132008-02-27 07:20:00 +00002109 Succ = EntryConditionBlock;
Ted Kremenek49af7cb2007-08-27 19:46:09 +00002110 return EntryConditionBlock;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002111}
Mike Stump1eb44332009-09-09 15:08:12 +00002112
2113
Ted Kremenek9c378f72011-08-12 23:37:29 +00002114CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt *S) {
Ted Kremenek4f880632009-07-17 22:18:43 +00002115 // FIXME: For now we pretend that @catch and the code it contains does not
2116 // exit.
2117 return Block;
2118}
Mike Stump6d9828c2009-07-17 01:31:16 +00002119
Ted Kremenek9c378f72011-08-12 23:37:29 +00002120CFGBlock *CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt *S) {
Ted Kremenek2fda5042008-12-09 20:20:09 +00002121 // FIXME: This isn't complete. We basically treat @throw like a return
2122 // statement.
Mike Stump6d9828c2009-07-17 01:31:16 +00002123
Ted Kremenek6c249722009-09-24 18:45:41 +00002124 // If we were in the middle of a block we stop processing that block.
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002125 if (badCFG)
Ted Kremenek4f880632009-07-17 22:18:43 +00002126 return 0;
Mike Stump6d9828c2009-07-17 01:31:16 +00002127
Ted Kremenek2fda5042008-12-09 20:20:09 +00002128 // Create the new block.
2129 Block = createBlock(false);
Mike Stump6d9828c2009-07-17 01:31:16 +00002130
Ted Kremenek2fda5042008-12-09 20:20:09 +00002131 // The Exit block is the only successor.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002132 addSuccessor(Block, &cfg->getExit());
Mike Stump6d9828c2009-07-17 01:31:16 +00002133
2134 // Add the statement to the block. This may create new blocks if S contains
2135 // control-flow (short-circuit operations).
Ted Kremenek852274d2009-12-16 03:18:58 +00002136 return VisitStmt(S, AddStmtChoice::AlwaysAdd);
Ted Kremenek2fda5042008-12-09 20:20:09 +00002137}
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002138
Ted Kremenek9c378f72011-08-12 23:37:29 +00002139CFGBlock *CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr *T) {
Ted Kremenek6c249722009-09-24 18:45:41 +00002140 // If we were in the middle of a block we stop processing that block.
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002141 if (badCFG)
Mike Stump0979d802009-07-22 22:56:04 +00002142 return 0;
2143
2144 // Create the new block.
2145 Block = createBlock(false);
2146
Mike Stump5d1d2022010-01-19 02:20:09 +00002147 if (TryTerminatedBlock)
2148 // The current try statement is the only successor.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002149 addSuccessor(Block, TryTerminatedBlock);
Ted Kremenekad5a8942010-08-02 23:46:59 +00002150 else
Mike Stump5d1d2022010-01-19 02:20:09 +00002151 // otherwise the Exit block is the only successor.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002152 addSuccessor(Block, &cfg->getExit());
Mike Stump0979d802009-07-22 22:56:04 +00002153
2154 // Add the statement to the block. This may create new blocks if S contains
2155 // control-flow (short-circuit operations).
Ted Kremenek852274d2009-12-16 03:18:58 +00002156 return VisitStmt(T, AddStmtChoice::AlwaysAdd);
Mike Stump0979d802009-07-22 22:56:04 +00002157}
2158
Ted Kremenek9c378f72011-08-12 23:37:29 +00002159CFGBlock *CFGBuilder::VisitDoStmt(DoStmt *D) {
2160 CFGBlock *LoopSuccessor = NULL;
Mike Stump6d9828c2009-07-17 01:31:16 +00002161
Mike Stump8f9893a2009-07-21 01:27:50 +00002162 // "do...while" is a control-flow statement. Thus we stop processing the
2163 // current block.
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002164 if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002165 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00002166 return 0;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002167 LoopSuccessor = Block;
Ted Kremenek4f880632009-07-17 22:18:43 +00002168 } else
2169 LoopSuccessor = Succ;
Mike Stump6d9828c2009-07-17 01:31:16 +00002170
2171 // Because of short-circuit evaluation, the condition of the loop can span
2172 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that
2173 // evaluate the condition.
Ted Kremenek9c378f72011-08-12 23:37:29 +00002174 CFGBlock *ExitConditionBlock = createBlock(false);
2175 CFGBlock *EntryConditionBlock = ExitConditionBlock;
Mike Stump6d9828c2009-07-17 01:31:16 +00002176
Ted Kremenek49af7cb2007-08-27 19:46:09 +00002177 // Set the terminator for the "exit" condition block.
Mike Stump6d9828c2009-07-17 01:31:16 +00002178 ExitConditionBlock->setTerminator(D);
2179
2180 // Now add the actual condition to the condition block. Because the condition
2181 // itself may contain control-flow, new blocks may be created.
Ted Kremenek9c378f72011-08-12 23:37:29 +00002182 if (Stmt *C = D->getCond()) {
Ted Kremenek49af7cb2007-08-27 19:46:09 +00002183 Block = ExitConditionBlock;
2184 EntryConditionBlock = addStmt(C);
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00002185 if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002186 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00002187 return 0;
2188 }
Ted Kremenek49af7cb2007-08-27 19:46:09 +00002189 }
Mike Stump6d9828c2009-07-17 01:31:16 +00002190
Ted Kremenek54827132008-02-27 07:20:00 +00002191 // The condition block is the implicit successor for the loop body.
Ted Kremenek49af7cb2007-08-27 19:46:09 +00002192 Succ = EntryConditionBlock;
2193
Mike Stump00998a02009-07-23 23:25:26 +00002194 // See if this is a known constant.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002195 const TryResult &KnownVal = tryEvaluateBool(D->getCond());
Mike Stump00998a02009-07-23 23:25:26 +00002196
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002197 // Process the loop body.
Ted Kremenek9c378f72011-08-12 23:37:29 +00002198 CFGBlock *BodyBlock = NULL;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002199 {
Ted Kremenek6db0ad32010-01-19 20:46:35 +00002200 assert(D->getBody());
Mike Stump6d9828c2009-07-17 01:31:16 +00002201
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002202 // Save the current values for Block, Succ, and continue and break targets
Marcin Swiderskif1308c72010-09-25 11:05:21 +00002203 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
2204 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget),
2205 save_break(BreakJumpTarget);
Mike Stump6d9828c2009-07-17 01:31:16 +00002206
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002207 // All continues within this loop should go to the condition block
Marcin Swiderskif1308c72010-09-25 11:05:21 +00002208 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos);
Mike Stump6d9828c2009-07-17 01:31:16 +00002209
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002210 // All breaks should go to the code following the loop.
Marcin Swiderskif1308c72010-09-25 11:05:21 +00002211 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
Mike Stump6d9828c2009-07-17 01:31:16 +00002212
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002213 // NULL out Block to force lazy instantiation of blocks for the body.
2214 Block = NULL;
Mike Stump6d9828c2009-07-17 01:31:16 +00002215
Marcin Swiderski05adedc2010-10-01 01:14:17 +00002216 // If body is not a compound statement create implicit scope
2217 // and add destructors.
2218 if (!isa<CompoundStmt>(D->getBody()))
2219 addLocalScopeAndDtors(D->getBody());
2220
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002221 // Create the body. The returned block is the entry to the loop body.
Ted Kremenek4f880632009-07-17 22:18:43 +00002222 BodyBlock = addStmt(D->getBody());
Mike Stump6d9828c2009-07-17 01:31:16 +00002223
Ted Kremenekaf603f72007-08-30 18:39:40 +00002224 if (!BodyBlock)
Ted Kremeneka9d996d2008-02-27 00:28:17 +00002225 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)"
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00002226 else if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002227 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00002228 return 0;
2229 }
Mike Stump6d9828c2009-07-17 01:31:16 +00002230
Ted Kremenekd173dc72010-08-17 20:59:56 +00002231 if (!KnownVal.isFalse()) {
2232 // Add an intermediate block between the BodyBlock and the
2233 // ExitConditionBlock to represent the "loop back" transition. Create an
2234 // empty block to represent the transition block for looping back to the
2235 // head of the loop.
2236 // FIXME: Can we do this more efficiently without adding another block?
2237 Block = NULL;
2238 Succ = BodyBlock;
2239 CFGBlock *LoopBackBlock = createBlock();
2240 LoopBackBlock->setLoopTarget(D);
Mike Stump6d9828c2009-07-17 01:31:16 +00002241
Ted Kremenekd173dc72010-08-17 20:59:56 +00002242 // Add the loop body entry as a successor to the condition.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002243 addSuccessor(ExitConditionBlock, LoopBackBlock);
Ted Kremenekd173dc72010-08-17 20:59:56 +00002244 }
2245 else
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002246 addSuccessor(ExitConditionBlock, NULL);
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002247 }
Mike Stump6d9828c2009-07-17 01:31:16 +00002248
Ted Kremenek941fde82009-07-24 04:47:11 +00002249 // Link up the condition block with the code that follows the loop.
2250 // (the false branch).
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002251 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor);
Mike Stump6d9828c2009-07-17 01:31:16 +00002252
2253 // There can be no more statements in the body block(s) since we loop back to
2254 // the body. NULL out Block to force lazy creation of another block.
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002255 Block = NULL;
Mike Stump6d9828c2009-07-17 01:31:16 +00002256
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002257 // Return the loop body, which is the dominating block for the loop.
Ted Kremenek54827132008-02-27 07:20:00 +00002258 Succ = BodyBlock;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002259 return BodyBlock;
2260}
2261
Ted Kremenek9c378f72011-08-12 23:37:29 +00002262CFGBlock *CFGBuilder::VisitContinueStmt(ContinueStmt *C) {
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002263 // "continue" is a control-flow statement. Thus we stop processing the
2264 // current block.
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002265 if (badCFG)
2266 return 0;
Mike Stump6d9828c2009-07-17 01:31:16 +00002267
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002268 // Now create a new block that ends with the continue statement.
2269 Block = createBlock(false);
2270 Block->setTerminator(C);
Mike Stump6d9828c2009-07-17 01:31:16 +00002271
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002272 // If there is no target for the continue, then we are looking at an
Ted Kremenek235c5ed2009-04-07 18:53:24 +00002273 // incomplete AST. This means the CFG cannot be constructed.
Ted Kremenek9ce52702011-01-07 19:37:16 +00002274 if (ContinueJumpTarget.block) {
2275 addAutomaticObjDtors(ScopePos, ContinueJumpTarget.scopePosition, C);
2276 addSuccessor(Block, ContinueJumpTarget.block);
Marcin Swiderskif1308c72010-09-25 11:05:21 +00002277 } else
Ted Kremenek235c5ed2009-04-07 18:53:24 +00002278 badCFG = true;
Mike Stump6d9828c2009-07-17 01:31:16 +00002279
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002280 return Block;
2281}
Mike Stump1eb44332009-09-09 15:08:12 +00002282
Peter Collingbournef4e3cfb2011-03-11 19:24:49 +00002283CFGBlock *CFGBuilder::VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,
2284 AddStmtChoice asc) {
Ted Kremenek13fc08a2009-07-18 00:47:21 +00002285
Ted Kremenek3179a452011-03-10 01:14:11 +00002286 if (asc.alwaysAdd(*this, E)) {
Ted Kremenek13fc08a2009-07-18 00:47:21 +00002287 autoCreateBlock();
Ted Kremenek892697d2010-12-16 07:46:53 +00002288 appendStmt(Block, E);
Ted Kremenek13fc08a2009-07-18 00:47:21 +00002289 }
Mike Stump1eb44332009-09-09 15:08:12 +00002290
Ted Kremenek4f880632009-07-17 22:18:43 +00002291 // VLA types have expressions that must be evaluated.
Ted Kremenek97e50712011-04-14 01:50:50 +00002292 CFGBlock *lastBlock = Block;
2293
Ted Kremenek4f880632009-07-17 22:18:43 +00002294 if (E->isArgumentType()) {
John McCallf4c73712011-01-19 06:33:43 +00002295 for (const VariableArrayType *VA =FindVA(E->getArgumentType().getTypePtr());
Ted Kremenek4f880632009-07-17 22:18:43 +00002296 VA != 0; VA = FindVA(VA->getElementType().getTypePtr()))
Ted Kremenek97e50712011-04-14 01:50:50 +00002297 lastBlock = addStmt(VA->getSizeExpr());
Ted Kremenekf91a5b02011-08-06 00:30:00 +00002298 }
Ted Kremenek97e50712011-04-14 01:50:50 +00002299 return lastBlock;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002300}
Mike Stump1eb44332009-09-09 15:08:12 +00002301
Ted Kremenek4f880632009-07-17 22:18:43 +00002302/// VisitStmtExpr - Utility method to handle (nested) statement
2303/// expressions (a GCC extension).
Ted Kremenek9c378f72011-08-12 23:37:29 +00002304CFGBlock *CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) {
Ted Kremenek3179a452011-03-10 01:14:11 +00002305 if (asc.alwaysAdd(*this, SE)) {
Ted Kremenek13fc08a2009-07-18 00:47:21 +00002306 autoCreateBlock();
Ted Kremenek892697d2010-12-16 07:46:53 +00002307 appendStmt(Block, SE);
Ted Kremenek13fc08a2009-07-18 00:47:21 +00002308 }
Ted Kremenek4f880632009-07-17 22:18:43 +00002309 return VisitCompoundStmt(SE->getSubStmt());
2310}
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002311
Ted Kremenek9c378f72011-08-12 23:37:29 +00002312CFGBlock *CFGBuilder::VisitSwitchStmt(SwitchStmt *Terminator) {
Mike Stump6d9828c2009-07-17 01:31:16 +00002313 // "switch" is a control-flow statement. Thus we stop processing the current
2314 // block.
Ted Kremenek9c378f72011-08-12 23:37:29 +00002315 CFGBlock *SwitchSuccessor = NULL;
Mike Stump6d9828c2009-07-17 01:31:16 +00002316
Marcin Swiderski8ae60582010-10-01 01:24:41 +00002317 // Save local scope position because in case of condition variable ScopePos
2318 // won't be restored when traversing AST.
2319 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2320
2321 // Create local scope for possible condition variable.
2322 // Store scope position. Add implicit destructor.
Ted Kremenek9c378f72011-08-12 23:37:29 +00002323 if (VarDecl *VD = Terminator->getConditionVariable()) {
Marcin Swiderski8ae60582010-10-01 01:24:41 +00002324 LocalScope::const_iterator SwitchBeginScopePos = ScopePos;
2325 addLocalScopeForVarDecl(VD);
2326 addAutomaticObjDtors(ScopePos, SwitchBeginScopePos, Terminator);
2327 }
2328
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002329 if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002330 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00002331 return 0;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002332 SwitchSuccessor = Block;
Mike Stump6d9828c2009-07-17 01:31:16 +00002333 } else SwitchSuccessor = Succ;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002334
2335 // Save the current "switch" context.
2336 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock),
Ted Kremenekeef5a9a2008-02-13 22:05:39 +00002337 save_default(DefaultCaseBlock);
Marcin Swiderskif1308c72010-09-25 11:05:21 +00002338 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
Ted Kremenekeef5a9a2008-02-13 22:05:39 +00002339
Mike Stump6d9828c2009-07-17 01:31:16 +00002340 // Set the "default" case to be the block after the switch statement. If the
2341 // switch statement contains a "default:", this value will be overwritten with
2342 // the block for that code.
Ted Kremenekeef5a9a2008-02-13 22:05:39 +00002343 DefaultCaseBlock = SwitchSuccessor;
Mike Stump6d9828c2009-07-17 01:31:16 +00002344
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002345 // Create a new block that will contain the switch statement.
2346 SwitchTerminatedBlock = createBlock(false);
Mike Stump6d9828c2009-07-17 01:31:16 +00002347
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002348 // Now process the switch body. The code after the switch is the implicit
2349 // successor.
2350 Succ = SwitchSuccessor;
Marcin Swiderskif1308c72010-09-25 11:05:21 +00002351 BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos);
Mike Stump6d9828c2009-07-17 01:31:16 +00002352
2353 // When visiting the body, the case statements should automatically get linked
2354 // up to the switch. We also don't keep a pointer to the body, since all
2355 // control-flow from the switch goes to case/default statements.
Ted Kremenek6db0ad32010-01-19 20:46:35 +00002356 assert(Terminator->getBody() && "switch must contain a non-NULL body");
Ted Kremenek49af7cb2007-08-27 19:46:09 +00002357 Block = NULL;
Marcin Swiderski8ae60582010-10-01 01:24:41 +00002358
Ted Kremeneke71f3d52011-03-01 23:12:55 +00002359 // For pruning unreachable case statements, save the current state
2360 // for tracking the condition value.
2361 SaveAndRestore<bool> save_switchExclusivelyCovered(switchExclusivelyCovered,
2362 false);
Ted Kremenek04982472011-03-04 01:03:41 +00002363
Ted Kremeneke71f3d52011-03-01 23:12:55 +00002364 // Determine if the switch condition can be explicitly evaluated.
2365 assert(Terminator->getCond() && "switch condition must be non-NULL");
Ted Kremenek04982472011-03-04 01:03:41 +00002366 Expr::EvalResult result;
Ted Kremeneke9cd9c02011-03-13 03:48:04 +00002367 bool b = tryEvaluate(Terminator->getCond(), result);
2368 SaveAndRestore<Expr::EvalResult*> save_switchCond(switchCond,
2369 b ? &result : 0);
Ted Kremenek04982472011-03-04 01:03:41 +00002370
Marcin Swiderski8ae60582010-10-01 01:24:41 +00002371 // If body is not a compound statement create implicit scope
2372 // and add destructors.
2373 if (!isa<CompoundStmt>(Terminator->getBody()))
2374 addLocalScopeAndDtors(Terminator->getBody());
2375
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002376 addStmt(Terminator->getBody());
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00002377 if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002378 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00002379 return 0;
2380 }
Ted Kremenek49af7cb2007-08-27 19:46:09 +00002381
Mike Stump6d9828c2009-07-17 01:31:16 +00002382 // If we have no "default:" case, the default transition is to the code
Ted Kremenek432c4782011-03-16 04:32:01 +00002383 // following the switch body. Moreover, take into account if all the
2384 // cases of a switch are covered (e.g., switching on an enum value).
Ted Kremeneke71f3d52011-03-01 23:12:55 +00002385 addSuccessor(SwitchTerminatedBlock,
Ted Kremenek432c4782011-03-16 04:32:01 +00002386 switchExclusivelyCovered || Terminator->isAllEnumCasesCovered()
2387 ? 0 : DefaultCaseBlock);
Mike Stump6d9828c2009-07-17 01:31:16 +00002388
Ted Kremenek49af7cb2007-08-27 19:46:09 +00002389 // Add the terminator and condition in the switch block.
Ted Kremenek411cdee2008-04-16 21:10:48 +00002390 SwitchTerminatedBlock->setTerminator(Terminator);
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002391 Block = SwitchTerminatedBlock;
Ted Kremenek6b501eb2009-12-24 00:39:26 +00002392 Block = addStmt(Terminator->getCond());
Ted Kremenekad5a8942010-08-02 23:46:59 +00002393
Ted Kremenek6b501eb2009-12-24 00:39:26 +00002394 // Finally, if the SwitchStmt contains a condition variable, add both the
2395 // SwitchStmt and the condition variable initialization to the CFG.
2396 if (VarDecl *VD = Terminator->getConditionVariable()) {
2397 if (Expr *Init = VD->getInit()) {
2398 autoCreateBlock();
Ted Kremenekd40066b2011-04-04 23:29:12 +00002399 appendStmt(Block, Terminator->getConditionVariableDeclStmt());
Ted Kremenek6b501eb2009-12-24 00:39:26 +00002400 addStmt(Init);
2401 }
2402 }
Ted Kremenekad5a8942010-08-02 23:46:59 +00002403
Ted Kremenek6b501eb2009-12-24 00:39:26 +00002404 return Block;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002405}
Ted Kremeneke71f3d52011-03-01 23:12:55 +00002406
2407static bool shouldAddCase(bool &switchExclusivelyCovered,
Ted Kremeneke9cd9c02011-03-13 03:48:04 +00002408 const Expr::EvalResult *switchCond,
Ted Kremeneke71f3d52011-03-01 23:12:55 +00002409 const CaseStmt *CS,
2410 ASTContext &Ctx) {
Ted Kremeneke9cd9c02011-03-13 03:48:04 +00002411 if (!switchCond)
2412 return true;
2413
Ted Kremeneke71f3d52011-03-01 23:12:55 +00002414 bool addCase = false;
Ted Kremenek04982472011-03-04 01:03:41 +00002415
Ted Kremeneke71f3d52011-03-01 23:12:55 +00002416 if (!switchExclusivelyCovered) {
Ted Kremeneke9cd9c02011-03-13 03:48:04 +00002417 if (switchCond->Val.isInt()) {
Ted Kremeneke71f3d52011-03-01 23:12:55 +00002418 // Evaluate the LHS of the case value.
Richard Smith85df96c2011-10-14 20:22:00 +00002419 const llvm::APSInt &lhsInt = CS->getLHS()->EvaluateKnownConstInt(Ctx);
Ted Kremeneke9cd9c02011-03-13 03:48:04 +00002420 const llvm::APSInt &condInt = switchCond->Val.getInt();
Ted Kremeneke71f3d52011-03-01 23:12:55 +00002421
2422 if (condInt == lhsInt) {
2423 addCase = true;
2424 switchExclusivelyCovered = true;
2425 }
2426 else if (condInt < lhsInt) {
2427 if (const Expr *RHS = CS->getRHS()) {
2428 // Evaluate the RHS of the case value.
Richard Smith85df96c2011-10-14 20:22:00 +00002429 const llvm::APSInt &V2 = RHS->EvaluateKnownConstInt(Ctx);
2430 if (V2 <= condInt) {
Ted Kremeneke71f3d52011-03-01 23:12:55 +00002431 addCase = true;
2432 switchExclusivelyCovered = true;
2433 }
2434 }
2435 }
2436 }
2437 else
2438 addCase = true;
2439 }
2440 return addCase;
2441}
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002442
Ted Kremenek9c378f72011-08-12 23:37:29 +00002443CFGBlock *CFGBuilder::VisitCaseStmt(CaseStmt *CS) {
Mike Stump6d9828c2009-07-17 01:31:16 +00002444 // CaseStmts are essentially labels, so they are the first statement in a
2445 // block.
Ted Kremenek0fc67e22010-08-04 23:54:30 +00002446 CFGBlock *TopBlock = 0, *LastBlock = 0;
Ted Kremenek04982472011-03-04 01:03:41 +00002447
Ted Kremenek0fc67e22010-08-04 23:54:30 +00002448 if (Stmt *Sub = CS->getSubStmt()) {
2449 // For deeply nested chains of CaseStmts, instead of doing a recursion
2450 // (which can blow out the stack), manually unroll and create blocks
2451 // along the way.
2452 while (isa<CaseStmt>(Sub)) {
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002453 CFGBlock *currentBlock = createBlock(false);
2454 currentBlock->setLabel(CS);
Ted Kremenek29ccaa12007-08-30 18:48:11 +00002455
Ted Kremenek0fc67e22010-08-04 23:54:30 +00002456 if (TopBlock)
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002457 addSuccessor(LastBlock, currentBlock);
Ted Kremenek0fc67e22010-08-04 23:54:30 +00002458 else
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002459 TopBlock = currentBlock;
Ted Kremenek0fc67e22010-08-04 23:54:30 +00002460
Ted Kremeneke71f3d52011-03-01 23:12:55 +00002461 addSuccessor(SwitchTerminatedBlock,
Ted Kremeneke9cd9c02011-03-13 03:48:04 +00002462 shouldAddCase(switchExclusivelyCovered, switchCond,
Ted Kremeneke71f3d52011-03-01 23:12:55 +00002463 CS, *Context)
2464 ? currentBlock : 0);
Ted Kremenek0fc67e22010-08-04 23:54:30 +00002465
Ted Kremeneke71f3d52011-03-01 23:12:55 +00002466 LastBlock = currentBlock;
Ted Kremenek0fc67e22010-08-04 23:54:30 +00002467 CS = cast<CaseStmt>(Sub);
2468 Sub = CS->getSubStmt();
2469 }
2470
2471 addStmt(Sub);
2472 }
Mike Stump1eb44332009-09-09 15:08:12 +00002473
Ted Kremenek9c378f72011-08-12 23:37:29 +00002474 CFGBlock *CaseBlock = Block;
Ted Kremenek4f880632009-07-17 22:18:43 +00002475 if (!CaseBlock)
2476 CaseBlock = createBlock();
Mike Stump6d9828c2009-07-17 01:31:16 +00002477
2478 // Cases statements partition blocks, so this is the top of the basic block we
2479 // were processing (the "case XXX:" is the label).
Ted Kremenek4f880632009-07-17 22:18:43 +00002480 CaseBlock->setLabel(CS);
2481
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002482 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00002483 return 0;
Mike Stump6d9828c2009-07-17 01:31:16 +00002484
2485 // Add this block to the list of successors for the block with the switch
2486 // statement.
Ted Kremenek4f880632009-07-17 22:18:43 +00002487 assert(SwitchTerminatedBlock);
Ted Kremeneke71f3d52011-03-01 23:12:55 +00002488 addSuccessor(SwitchTerminatedBlock,
Ted Kremeneke9cd9c02011-03-13 03:48:04 +00002489 shouldAddCase(switchExclusivelyCovered, switchCond,
Ted Kremeneke71f3d52011-03-01 23:12:55 +00002490 CS, *Context)
2491 ? CaseBlock : 0);
Mike Stump6d9828c2009-07-17 01:31:16 +00002492
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002493 // We set Block to NULL to allow lazy creation of a new block (if necessary)
2494 Block = NULL;
Mike Stump6d9828c2009-07-17 01:31:16 +00002495
Ted Kremenek0fc67e22010-08-04 23:54:30 +00002496 if (TopBlock) {
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002497 addSuccessor(LastBlock, CaseBlock);
Ted Kremenek0fc67e22010-08-04 23:54:30 +00002498 Succ = TopBlock;
Zhanyong Wan36f327c2010-11-22 19:32:14 +00002499 } else {
Ted Kremenek0fc67e22010-08-04 23:54:30 +00002500 // This block is now the implicit successor of other blocks.
2501 Succ = CaseBlock;
2502 }
Mike Stump6d9828c2009-07-17 01:31:16 +00002503
Ted Kremenek0fc67e22010-08-04 23:54:30 +00002504 return Succ;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002505}
Mike Stump6d9828c2009-07-17 01:31:16 +00002506
Ted Kremenek9c378f72011-08-12 23:37:29 +00002507CFGBlock *CFGBuilder::VisitDefaultStmt(DefaultStmt *Terminator) {
Ted Kremenek4f880632009-07-17 22:18:43 +00002508 if (Terminator->getSubStmt())
2509 addStmt(Terminator->getSubStmt());
Mike Stump1eb44332009-09-09 15:08:12 +00002510
Ted Kremenekeef5a9a2008-02-13 22:05:39 +00002511 DefaultCaseBlock = Block;
Ted Kremenek4f880632009-07-17 22:18:43 +00002512
2513 if (!DefaultCaseBlock)
2514 DefaultCaseBlock = createBlock();
Mike Stump6d9828c2009-07-17 01:31:16 +00002515
2516 // Default statements partition blocks, so this is the top of the basic block
2517 // we were processing (the "default:" is the label).
Ted Kremenek411cdee2008-04-16 21:10:48 +00002518 DefaultCaseBlock->setLabel(Terminator);
Mike Stump1eb44332009-09-09 15:08:12 +00002519
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002520 if (badCFG)
Ted Kremenek4e8df2e2009-05-02 00:13:27 +00002521 return 0;
Ted Kremenekeef5a9a2008-02-13 22:05:39 +00002522
Mike Stump6d9828c2009-07-17 01:31:16 +00002523 // Unlike case statements, we don't add the default block to the successors
2524 // for the switch statement immediately. This is done when we finish
2525 // processing the switch statement. This allows for the default case
2526 // (including a fall-through to the code after the switch statement) to always
2527 // be the last successor of a switch-terminated block.
2528
Ted Kremenekeef5a9a2008-02-13 22:05:39 +00002529 // We set Block to NULL to allow lazy creation of a new block (if necessary)
2530 Block = NULL;
Mike Stump6d9828c2009-07-17 01:31:16 +00002531
Ted Kremenekeef5a9a2008-02-13 22:05:39 +00002532 // This block is now the implicit successor of other blocks.
2533 Succ = DefaultCaseBlock;
Mike Stump6d9828c2009-07-17 01:31:16 +00002534
2535 return DefaultCaseBlock;
Ted Kremenek295222c2008-02-13 21:46:34 +00002536}
Ted Kremenekd4fdee32007-08-23 21:42:29 +00002537
Mike Stump5d1d2022010-01-19 02:20:09 +00002538CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) {
2539 // "try"/"catch" is a control-flow statement. Thus we stop processing the
2540 // current block.
Ted Kremenek9c378f72011-08-12 23:37:29 +00002541 CFGBlock *TrySuccessor = NULL;
Mike Stump5d1d2022010-01-19 02:20:09 +00002542
2543 if (Block) {
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002544 if (badCFG)
Mike Stump5d1d2022010-01-19 02:20:09 +00002545 return 0;
2546 TrySuccessor = Block;
2547 } else TrySuccessor = Succ;
2548
Mike Stumpa1f93632010-01-20 01:15:34 +00002549 CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock;
Mike Stump5d1d2022010-01-19 02:20:09 +00002550
2551 // Create a new block that will contain the try statement.
Mike Stumpf00cca52010-01-20 01:30:58 +00002552 CFGBlock *NewTryTerminatedBlock = createBlock(false);
Mike Stump5d1d2022010-01-19 02:20:09 +00002553 // Add the terminator in the try block.
Mike Stumpf00cca52010-01-20 01:30:58 +00002554 NewTryTerminatedBlock->setTerminator(Terminator);
Mike Stump5d1d2022010-01-19 02:20:09 +00002555
Mike Stumpa1f93632010-01-20 01:15:34 +00002556 bool HasCatchAll = false;
Mike Stump5d1d2022010-01-19 02:20:09 +00002557 for (unsigned h = 0; h <Terminator->getNumHandlers(); ++h) {
2558 // The code after the try is the implicit successor.
2559 Succ = TrySuccessor;
2560 CXXCatchStmt *CS = Terminator->getHandler(h);
Mike Stumpa1f93632010-01-20 01:15:34 +00002561 if (CS->getExceptionDecl() == 0) {
2562 HasCatchAll = true;
2563 }
Mike Stump5d1d2022010-01-19 02:20:09 +00002564 Block = NULL;
2565 CFGBlock *CatchBlock = VisitCXXCatchStmt(CS);
2566 if (CatchBlock == 0)
2567 return 0;
2568 // Add this block to the list of successors for the block with the try
2569 // statement.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002570 addSuccessor(NewTryTerminatedBlock, CatchBlock);
Mike Stump5d1d2022010-01-19 02:20:09 +00002571 }
Mike Stumpa1f93632010-01-20 01:15:34 +00002572 if (!HasCatchAll) {
2573 if (PrevTryTerminatedBlock)
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002574 addSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock);
Mike Stumpa1f93632010-01-20 01:15:34 +00002575 else
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002576 addSuccessor(NewTryTerminatedBlock, &cfg->getExit());
Mike Stumpa1f93632010-01-20 01:15:34 +00002577 }
Mike Stump5d1d2022010-01-19 02:20:09 +00002578
2579 // The code after the try is the implicit successor.
2580 Succ = TrySuccessor;
2581
Mike Stumpf00cca52010-01-20 01:30:58 +00002582 // Save the current "try" context.
Ted Kremenekf0e71ae2011-08-23 23:05:07 +00002583 SaveAndRestore<CFGBlock*> save_try(TryTerminatedBlock, NewTryTerminatedBlock);
2584 cfg->addTryDispatchBlock(TryTerminatedBlock);
Mike Stumpf00cca52010-01-20 01:30:58 +00002585
Ted Kremenek6db0ad32010-01-19 20:46:35 +00002586 assert(Terminator->getTryBlock() && "try must contain a non-NULL body");
Mike Stump5d1d2022010-01-19 02:20:09 +00002587 Block = NULL;
Ted Kremenek3fa1e4b2010-01-19 20:52:05 +00002588 Block = addStmt(Terminator->getTryBlock());
Mike Stump5d1d2022010-01-19 02:20:09 +00002589 return Block;
2590}
2591
Ted Kremenek9c378f72011-08-12 23:37:29 +00002592CFGBlock *CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt *CS) {
Mike Stump5d1d2022010-01-19 02:20:09 +00002593 // CXXCatchStmt are treated like labels, so they are the first statement in a
2594 // block.
2595
Marcin Swiderski0e97bcb2010-10-01 01:46:52 +00002596 // Save local scope position because in case of exception variable ScopePos
2597 // won't be restored when traversing AST.
2598 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2599
2600 // Create local scope for possible exception variable.
2601 // Store scope position. Add implicit destructor.
Ted Kremenek9c378f72011-08-12 23:37:29 +00002602 if (VarDecl *VD = CS->getExceptionDecl()) {
Marcin Swiderski0e97bcb2010-10-01 01:46:52 +00002603 LocalScope::const_iterator BeginScopePos = ScopePos;
2604 addLocalScopeForVarDecl(VD);
2605 addAutomaticObjDtors(ScopePos, BeginScopePos, CS);
2606 }
2607
Mike Stump5d1d2022010-01-19 02:20:09 +00002608 if (CS->getHandlerBlock())
2609 addStmt(CS->getHandlerBlock());
2610
Ted Kremenek9c378f72011-08-12 23:37:29 +00002611 CFGBlock *CatchBlock = Block;
Mike Stump5d1d2022010-01-19 02:20:09 +00002612 if (!CatchBlock)
2613 CatchBlock = createBlock();
2614
2615 CatchBlock->setLabel(CS);
2616
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002617 if (badCFG)
Mike Stump5d1d2022010-01-19 02:20:09 +00002618 return 0;
2619
2620 // We set Block to NULL to allow lazy creation of a new block (if necessary)
2621 Block = NULL;
2622
2623 return CatchBlock;
2624}
2625
Ted Kremenek9c378f72011-08-12 23:37:29 +00002626CFGBlock *CFGBuilder::VisitCXXForRangeStmt(CXXForRangeStmt *S) {
Richard Smithad762fc2011-04-14 22:09:26 +00002627 // C++0x for-range statements are specified as [stmt.ranged]:
2628 //
2629 // {
2630 // auto && __range = range-init;
2631 // for ( auto __begin = begin-expr,
2632 // __end = end-expr;
2633 // __begin != __end;
2634 // ++__begin ) {
2635 // for-range-declaration = *__begin;
2636 // statement
2637 // }
2638 // }
2639
2640 // Save local scope position before the addition of the implicit variables.
2641 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos);
2642
2643 // Create local scopes and destructors for range, begin and end variables.
2644 if (Stmt *Range = S->getRangeStmt())
2645 addLocalScopeForStmt(Range);
2646 if (Stmt *BeginEnd = S->getBeginEndStmt())
2647 addLocalScopeForStmt(BeginEnd);
2648 addAutomaticObjDtors(ScopePos, save_scope_pos.get(), S);
2649
2650 LocalScope::const_iterator ContinueScopePos = ScopePos;
2651
2652 // "for" is a control-flow statement. Thus we stop processing the current
2653 // block.
Ted Kremenek9c378f72011-08-12 23:37:29 +00002654 CFGBlock *LoopSuccessor = NULL;
Richard Smithad762fc2011-04-14 22:09:26 +00002655 if (Block) {
2656 if (badCFG)
2657 return 0;
2658 LoopSuccessor = Block;
2659 } else
2660 LoopSuccessor = Succ;
2661
2662 // Save the current value for the break targets.
2663 // All breaks should go to the code following the loop.
2664 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget);
2665 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);
2666
2667 // The block for the __begin != __end expression.
Ted Kremenek9c378f72011-08-12 23:37:29 +00002668 CFGBlock *ConditionBlock = createBlock(false);
Richard Smithad762fc2011-04-14 22:09:26 +00002669 ConditionBlock->setTerminator(S);
2670
2671 // Now add the actual condition to the condition block.
2672 if (Expr *C = S->getCond()) {
2673 Block = ConditionBlock;
2674 CFGBlock *BeginConditionBlock = addStmt(C);
2675 if (badCFG)
2676 return 0;
2677 assert(BeginConditionBlock == ConditionBlock &&
2678 "condition block in for-range was unexpectedly complex");
2679 (void)BeginConditionBlock;
2680 }
2681
2682 // The condition block is the implicit successor for the loop body as well as
2683 // any code above the loop.
2684 Succ = ConditionBlock;
2685
2686 // See if this is a known constant.
2687 TryResult KnownVal(true);
2688
2689 if (S->getCond())
2690 KnownVal = tryEvaluateBool(S->getCond());
2691
2692 // Now create the loop body.
2693 {
2694 assert(S->getBody());
2695
2696 // Save the current values for Block, Succ, and continue targets.
2697 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ);
2698 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget);
2699
2700 // Generate increment code in its own basic block. This is the target of
2701 // continue statements.
2702 Block = 0;
2703 Succ = addStmt(S->getInc());
2704 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);
2705
2706 // The starting block for the loop increment is the block that should
2707 // represent the 'loop target' for looping back to the start of the loop.
2708 ContinueJumpTarget.block->setLoopTarget(S);
2709
2710 // Finish up the increment block and prepare to start the loop body.
2711 assert(Block);
2712 if (badCFG)
2713 return 0;
2714 Block = 0;
2715
2716
2717 // Add implicit scope and dtors for loop variable.
2718 addLocalScopeAndDtors(S->getLoopVarStmt());
2719
2720 // Populate a new block to contain the loop body and loop variable.
2721 Block = addStmt(S->getBody());
2722 if (badCFG)
2723 return 0;
2724 Block = addStmt(S->getLoopVarStmt());
2725 if (badCFG)
2726 return 0;
2727
2728 // This new body block is a successor to our condition block.
2729 addSuccessor(ConditionBlock, KnownVal.isFalse() ? 0 : Block);
2730 }
2731
2732 // Link up the condition block with the code that follows the loop (the
2733 // false branch).
2734 addSuccessor(ConditionBlock, KnownVal.isTrue() ? 0 : LoopSuccessor);
2735
2736 // Add the initialization statements.
2737 Block = createBlock();
Richard Smithb403d6d2011-04-18 15:49:25 +00002738 addStmt(S->getBeginEndStmt());
2739 return addStmt(S->getRangeStmt());
Richard Smithad762fc2011-04-14 22:09:26 +00002740}
2741
John McCall4765fa02010-12-06 08:20:24 +00002742CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E,
Marcin Swiderski8599e762010-11-03 06:19:35 +00002743 AddStmtChoice asc) {
2744 if (BuildOpts.AddImplicitDtors) {
2745 // If adding implicit destructors visit the full expression for adding
2746 // destructors of temporaries.
2747 VisitForTemporaryDtors(E->getSubExpr());
2748
2749 // Full expression has to be added as CFGStmt so it will be sequenced
2750 // before destructors of it's temporaries.
Zhanyong Wan94a3dcf2010-11-24 03:28:53 +00002751 asc = asc.withAlwaysAdd(true);
Marcin Swiderski8599e762010-11-03 06:19:35 +00002752 }
2753 return Visit(E->getSubExpr(), asc);
2754}
2755
Zhongxing Xua725ed42010-11-01 13:04:58 +00002756CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,
2757 AddStmtChoice asc) {
Ted Kremenek3179a452011-03-10 01:14:11 +00002758 if (asc.alwaysAdd(*this, E)) {
Zhongxing Xua725ed42010-11-01 13:04:58 +00002759 autoCreateBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00002760 appendStmt(Block, E);
Zhongxing Xua725ed42010-11-01 13:04:58 +00002761
2762 // We do not want to propagate the AlwaysAdd property.
Zhanyong Wan94a3dcf2010-11-24 03:28:53 +00002763 asc = asc.withAlwaysAdd(false);
Zhongxing Xua725ed42010-11-01 13:04:58 +00002764 }
2765 return Visit(E->getSubExpr(), asc);
2766}
2767
Zhongxing Xu81bc7d02010-11-01 06:46:05 +00002768CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C,
2769 AddStmtChoice asc) {
Zhongxing Xu81bc7d02010-11-01 06:46:05 +00002770 autoCreateBlock();
Zhongxing Xu97a72c32012-01-11 02:39:07 +00002771 appendStmt(Block, C);
Zhanyong Wan94a3dcf2010-11-24 03:28:53 +00002772
Zhongxing Xu81bc7d02010-11-01 06:46:05 +00002773 return VisitChildren(C);
2774}
2775
Zhongxing Xua725ed42010-11-01 13:04:58 +00002776CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,
2777 AddStmtChoice asc) {
Ted Kremenek3179a452011-03-10 01:14:11 +00002778 if (asc.alwaysAdd(*this, E)) {
Zhongxing Xua725ed42010-11-01 13:04:58 +00002779 autoCreateBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00002780 appendStmt(Block, E);
Zhongxing Xua725ed42010-11-01 13:04:58 +00002781 // We do not want to propagate the AlwaysAdd property.
Zhanyong Wan94a3dcf2010-11-24 03:28:53 +00002782 asc = asc.withAlwaysAdd(false);
Zhongxing Xua725ed42010-11-01 13:04:58 +00002783 }
2784 return Visit(E->getSubExpr(), asc);
2785}
2786
Zhongxing Xu81bc7d02010-11-01 06:46:05 +00002787CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C,
2788 AddStmtChoice asc) {
Zhongxing Xu81bc7d02010-11-01 06:46:05 +00002789 autoCreateBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00002790 appendStmt(Block, C);
Zhongxing Xu81bc7d02010-11-01 06:46:05 +00002791 return VisitChildren(C);
2792}
2793
Zhongxing Xua725ed42010-11-01 13:04:58 +00002794CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E,
2795 AddStmtChoice asc) {
Ted Kremenek3179a452011-03-10 01:14:11 +00002796 if (asc.alwaysAdd(*this, E)) {
Zhongxing Xua725ed42010-11-01 13:04:58 +00002797 autoCreateBlock();
Ted Kremenek247e9662011-03-10 01:14:08 +00002798 appendStmt(Block, E);
Zhongxing Xua725ed42010-11-01 13:04:58 +00002799 }
Ted Kremenek892697d2010-12-16 07:46:53 +00002800 return Visit(E->getSubExpr(), AddStmtChoice());
Zhongxing Xua725ed42010-11-01 13:04:58 +00002801}
2802
Ted Kremenek9c378f72011-08-12 23:37:29 +00002803CFGBlock *CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt *I) {
Mike Stump6d9828c2009-07-17 01:31:16 +00002804 // Lazily create the indirect-goto dispatch block if there isn't one already.
Ted Kremenek9c378f72011-08-12 23:37:29 +00002805 CFGBlock *IBlock = cfg->getIndirectGotoBlock();
Mike Stump6d9828c2009-07-17 01:31:16 +00002806
Ted Kremenek19bb3562007-08-28 19:26:49 +00002807 if (!IBlock) {
2808 IBlock = createBlock(false);
2809 cfg->setIndirectGotoBlock(IBlock);
2810 }
Mike Stump6d9828c2009-07-17 01:31:16 +00002811
Ted Kremenek19bb3562007-08-28 19:26:49 +00002812 // IndirectGoto is a control-flow statement. Thus we stop processing the
2813 // current block and create a new one.
Zhongxing Xud438b3d2010-09-06 07:32:31 +00002814 if (badCFG)
Ted Kremenek4f880632009-07-17 22:18:43 +00002815 return 0;
2816
Ted Kremenek19bb3562007-08-28 19:26:49 +00002817 Block = createBlock(false);
2818 Block->setTerminator(I);
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002819 addSuccessor(Block, IBlock);
Ted Kremenek19bb3562007-08-28 19:26:49 +00002820 return addStmt(I->getTarget());
2821}
2822
Marcin Swiderski8599e762010-11-03 06:19:35 +00002823CFGBlock *CFGBuilder::VisitForTemporaryDtors(Stmt *E, bool BindToTemporary) {
2824tryAgain:
2825 if (!E) {
2826 badCFG = true;
2827 return NULL;
2828 }
2829 switch (E->getStmtClass()) {
2830 default:
2831 return VisitChildrenForTemporaryDtors(E);
2832
2833 case Stmt::BinaryOperatorClass:
2834 return VisitBinaryOperatorForTemporaryDtors(cast<BinaryOperator>(E));
2835
2836 case Stmt::CXXBindTemporaryExprClass:
2837 return VisitCXXBindTemporaryExprForTemporaryDtors(
2838 cast<CXXBindTemporaryExpr>(E), BindToTemporary);
2839
John McCall56ca35d2011-02-17 10:25:35 +00002840 case Stmt::BinaryConditionalOperatorClass:
Marcin Swiderski8599e762010-11-03 06:19:35 +00002841 case Stmt::ConditionalOperatorClass:
2842 return VisitConditionalOperatorForTemporaryDtors(
John McCall56ca35d2011-02-17 10:25:35 +00002843 cast<AbstractConditionalOperator>(E), BindToTemporary);
Marcin Swiderski8599e762010-11-03 06:19:35 +00002844
2845 case Stmt::ImplicitCastExprClass:
2846 // For implicit cast we want BindToTemporary to be passed further.
2847 E = cast<CastExpr>(E)->getSubExpr();
2848 goto tryAgain;
2849
2850 case Stmt::ParenExprClass:
2851 E = cast<ParenExpr>(E)->getSubExpr();
2852 goto tryAgain;
Douglas Gregor03e80032011-06-21 17:03:29 +00002853
2854 case Stmt::MaterializeTemporaryExprClass:
2855 E = cast<MaterializeTemporaryExpr>(E)->GetTemporaryExpr();
2856 goto tryAgain;
Marcin Swiderski8599e762010-11-03 06:19:35 +00002857 }
2858}
2859
2860CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E) {
2861 // When visiting children for destructors we want to visit them in reverse
2862 // order. Because there's no reverse iterator for children must to reverse
2863 // them in helper vector.
Chris Lattner5f9e2722011-07-23 10:55:15 +00002864 typedef SmallVector<Stmt *, 4> ChildrenVect;
Marcin Swiderski8599e762010-11-03 06:19:35 +00002865 ChildrenVect ChildrenRev;
John McCall7502c1d2011-02-13 04:07:26 +00002866 for (Stmt::child_range I = E->children(); I; ++I) {
Marcin Swiderski8599e762010-11-03 06:19:35 +00002867 if (*I) ChildrenRev.push_back(*I);
2868 }
2869
2870 CFGBlock *B = Block;
2871 for (ChildrenVect::reverse_iterator I = ChildrenRev.rbegin(),
2872 L = ChildrenRev.rend(); I != L; ++I) {
2873 if (CFGBlock *R = VisitForTemporaryDtors(*I))
2874 B = R;
2875 }
2876 return B;
2877}
2878
2879CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E) {
2880 if (E->isLogicalOp()) {
2881 // Destructors for temporaries in LHS expression should be called after
2882 // those for RHS expression. Even if this will unnecessarily create a block,
2883 // this block will be used at least by the full expression.
2884 autoCreateBlock();
2885 CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getLHS());
2886 if (badCFG)
2887 return NULL;
2888
2889 Succ = ConfluenceBlock;
2890 Block = NULL;
2891 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS());
2892
2893 if (RHSBlock) {
2894 if (badCFG)
2895 return NULL;
2896
2897 // If RHS expression did produce destructors we need to connect created
2898 // blocks to CFG in same manner as for binary operator itself.
2899 CFGBlock *LHSBlock = createBlock(false);
2900 LHSBlock->setTerminator(CFGTerminator(E, true));
2901
2902 // For binary operator LHS block is before RHS in list of predecessors
2903 // of ConfluenceBlock.
2904 std::reverse(ConfluenceBlock->pred_begin(),
2905 ConfluenceBlock->pred_end());
2906
2907 // See if this is a known constant.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002908 TryResult KnownVal = tryEvaluateBool(E->getLHS());
Marcin Swiderski8599e762010-11-03 06:19:35 +00002909 if (KnownVal.isKnown() && (E->getOpcode() == BO_LOr))
2910 KnownVal.negate();
2911
2912 // Link LHSBlock with RHSBlock exactly the same way as for binary operator
2913 // itself.
2914 if (E->getOpcode() == BO_LOr) {
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002915 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock);
2916 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock);
Marcin Swiderski8599e762010-11-03 06:19:35 +00002917 } else {
2918 assert (E->getOpcode() == BO_LAnd);
Ted Kremenek0a3ed312010-12-17 04:44:39 +00002919 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock);
2920 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock);
Marcin Swiderski8599e762010-11-03 06:19:35 +00002921 }
2922
2923 Block = LHSBlock;
2924 return LHSBlock;
2925 }
2926
2927 Block = ConfluenceBlock;
2928 return ConfluenceBlock;
2929 }
2930
Zhanyong Wan36f327c2010-11-22 19:32:14 +00002931 if (E->isAssignmentOp()) {
Marcin Swiderski8599e762010-11-03 06:19:35 +00002932 // For assignment operator (=) LHS expression is visited
2933 // before RHS expression. For destructors visit them in reverse order.
2934 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS());
2935 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS());
2936 return LHSBlock ? LHSBlock : RHSBlock;
2937 }
2938
2939 // For any other binary operator RHS expression is visited before
2940 // LHS expression (order of children). For destructors visit them in reverse
2941 // order.
2942 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS());
2943 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS());
2944 return RHSBlock ? RHSBlock : LHSBlock;
2945}
2946
2947CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors(
2948 CXXBindTemporaryExpr *E, bool BindToTemporary) {
2949 // First add destructors for temporaries in subexpression.
2950 CFGBlock *B = VisitForTemporaryDtors(E->getSubExpr());
Zhongxing Xu249c9452010-11-14 15:23:50 +00002951 if (!BindToTemporary) {
Marcin Swiderski8599e762010-11-03 06:19:35 +00002952 // If lifetime of temporary is not prolonged (by assigning to constant
2953 // reference) add destructor for it.
Chandler Carruthc8cfc742011-09-13 06:09:01 +00002954
2955 // If the destructor is marked as a no-return destructor, we need to create
2956 // a new block for the destructor which does not have as a successor
2957 // anything built thus far. Control won't flow out of this block.
2958 const CXXDestructorDecl *Dtor = E->getTemporary()->getDestructor();
Chandler Carruthdba3fb52011-09-13 09:13:49 +00002959 if (cast<FunctionType>(Dtor->getType())->getNoReturnAttr())
2960 Block = createNoReturnBlock();
2961 else
Chandler Carruthc8cfc742011-09-13 06:09:01 +00002962 autoCreateBlock();
Chandler Carruthc8cfc742011-09-13 06:09:01 +00002963
Marcin Swiderski8599e762010-11-03 06:19:35 +00002964 appendTemporaryDtor(Block, E);
2965 B = Block;
2966 }
2967 return B;
2968}
2969
2970CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors(
John McCall56ca35d2011-02-17 10:25:35 +00002971 AbstractConditionalOperator *E, bool BindToTemporary) {
Marcin Swiderski8599e762010-11-03 06:19:35 +00002972 // First add destructors for condition expression. Even if this will
2973 // unnecessarily create a block, this block will be used at least by the full
2974 // expression.
2975 autoCreateBlock();
2976 CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getCond());
2977 if (badCFG)
2978 return NULL;
John McCall56ca35d2011-02-17 10:25:35 +00002979 if (BinaryConditionalOperator *BCO
2980 = dyn_cast<BinaryConditionalOperator>(E)) {
2981 ConfluenceBlock = VisitForTemporaryDtors(BCO->getCommon());
Marcin Swiderski8599e762010-11-03 06:19:35 +00002982 if (badCFG)
2983 return NULL;
2984 }
2985
John McCall56ca35d2011-02-17 10:25:35 +00002986 // Try to add block with destructors for LHS expression.
2987 CFGBlock *LHSBlock = NULL;
2988 Succ = ConfluenceBlock;
2989 Block = NULL;
2990 LHSBlock = VisitForTemporaryDtors(E->getTrueExpr(), BindToTemporary);
2991 if (badCFG)
2992 return NULL;
2993
Marcin Swiderski8599e762010-11-03 06:19:35 +00002994 // Try to add block with destructors for RHS expression;
2995 Succ = ConfluenceBlock;
2996 Block = NULL;
John McCall56ca35d2011-02-17 10:25:35 +00002997 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getFalseExpr(),
2998 BindToTemporary);
Marcin Swiderski8599e762010-11-03 06:19:35 +00002999 if (badCFG)
3000 return NULL;
3001
3002 if (!RHSBlock && !LHSBlock) {
3003 // If neither LHS nor RHS expression had temporaries to destroy don't create
3004 // more blocks.
3005 Block = ConfluenceBlock;
3006 return Block;
3007 }
3008
3009 Block = createBlock(false);
3010 Block->setTerminator(CFGTerminator(E, true));
3011
3012 // See if this is a known constant.
Ted Kremenek0a3ed312010-12-17 04:44:39 +00003013 const TryResult &KnownVal = tryEvaluateBool(E->getCond());
Marcin Swiderski8599e762010-11-03 06:19:35 +00003014
3015 if (LHSBlock) {
Ted Kremenek0a3ed312010-12-17 04:44:39 +00003016 addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock);
Marcin Swiderski8599e762010-11-03 06:19:35 +00003017 } else if (KnownVal.isFalse()) {
Ted Kremenek0a3ed312010-12-17 04:44:39 +00003018 addSuccessor(Block, NULL);
Marcin Swiderski8599e762010-11-03 06:19:35 +00003019 } else {
Ted Kremenek0a3ed312010-12-17 04:44:39 +00003020 addSuccessor(Block, ConfluenceBlock);
Marcin Swiderski8599e762010-11-03 06:19:35 +00003021 std::reverse(ConfluenceBlock->pred_begin(), ConfluenceBlock->pred_end());
3022 }
3023
3024 if (!RHSBlock)
3025 RHSBlock = ConfluenceBlock;
Ted Kremenek0a3ed312010-12-17 04:44:39 +00003026 addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock);
Marcin Swiderski8599e762010-11-03 06:19:35 +00003027
3028 return Block;
3029}
3030
Ted Kremenekbefef2f2007-08-23 21:26:19 +00003031} // end anonymous namespace
Ted Kremenek026473c2007-08-23 16:51:22 +00003032
Mike Stump6d9828c2009-07-17 01:31:16 +00003033/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has
3034/// no successors or predecessors. If this is the first block created in the
3035/// CFG, it is automatically set to be the Entry and Exit of the CFG.
Ted Kremenek9c378f72011-08-12 23:37:29 +00003036CFGBlock *CFG::createBlock() {
Ted Kremenek026473c2007-08-23 16:51:22 +00003037 bool first_block = begin() == end();
3038
3039 // Create the block.
Ted Kremenekee82d9b2009-10-12 20:55:07 +00003040 CFGBlock *Mem = getAllocator().Allocate<CFGBlock>();
Anna Zaks02f34c52011-12-05 21:33:11 +00003041 new (Mem) CFGBlock(NumBlockIDs++, BlkBVC, this);
Ted Kremenekee82d9b2009-10-12 20:55:07 +00003042 Blocks.push_back(Mem, BlkBVC);
Ted Kremenek026473c2007-08-23 16:51:22 +00003043
3044 // If this is the first block, set it as the Entry and Exit.
Ted Kremenekee82d9b2009-10-12 20:55:07 +00003045 if (first_block)
3046 Entry = Exit = &back();
Ted Kremenek026473c2007-08-23 16:51:22 +00003047
3048 // Return the block.
Ted Kremenekee82d9b2009-10-12 20:55:07 +00003049 return &back();
Ted Kremenekfddd5182007-08-21 21:42:03 +00003050}
3051
Ted Kremenek026473c2007-08-23 16:51:22 +00003052/// buildCFG - Constructs a CFG from an AST. Ownership of the returned
3053/// CFG is returned to the caller.
Ted Kremenek9c378f72011-08-12 23:37:29 +00003054CFG* CFG::buildCFG(const Decl *D, Stmt *Statement, ASTContext *C,
Ted Kremenekb8ad5ee2011-03-10 01:14:05 +00003055 const BuildOptions &BO) {
3056 CFGBuilder Builder(C, BO);
3057 return Builder.buildCFG(D, Statement);
Ted Kremenek026473c2007-08-23 16:51:22 +00003058}
3059
Ted Kremenekc5aff442011-03-03 01:21:32 +00003060const CXXDestructorDecl *
3061CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const {
Ted Kremenekc9f8f5a2011-03-02 20:32:29 +00003062 switch (getKind()) {
3063 case CFGElement::Invalid:
3064 case CFGElement::Statement:
3065 case CFGElement::Initializer:
3066 llvm_unreachable("getDestructorDecl should only be used with "
3067 "ImplicitDtors");
3068 case CFGElement::AutomaticObjectDtor: {
3069 const VarDecl *var = cast<CFGAutomaticObjDtor>(this)->getVarDecl();
3070 QualType ty = var->getType();
Ted Kremenek697d42d2011-03-03 01:01:03 +00003071 ty = ty.getNonReferenceType();
Ted Kremenekc5aff442011-03-03 01:21:32 +00003072 if (const ArrayType *arrayType = astContext.getAsArrayType(ty)) {
3073 ty = arrayType->getElementType();
3074 }
Ted Kremenekc9f8f5a2011-03-02 20:32:29 +00003075 const RecordType *recordType = ty->getAs<RecordType>();
3076 const CXXRecordDecl *classDecl =
Ted Kremenek697d42d2011-03-03 01:01:03 +00003077 cast<CXXRecordDecl>(recordType->getDecl());
Ted Kremenekc9f8f5a2011-03-02 20:32:29 +00003078 return classDecl->getDestructor();
3079 }
3080 case CFGElement::TemporaryDtor: {
3081 const CXXBindTemporaryExpr *bindExpr =
3082 cast<CFGTemporaryDtor>(this)->getBindTemporaryExpr();
3083 const CXXTemporary *temp = bindExpr->getTemporary();
3084 return temp->getDestructor();
3085 }
3086 case CFGElement::BaseDtor:
3087 case CFGElement::MemberDtor:
3088
3089 // Not yet supported.
3090 return 0;
3091 }
Ted Kremenek697d42d2011-03-03 01:01:03 +00003092 llvm_unreachable("getKind() returned bogus value");
Matt Beaumont-Gay2ae00542011-03-03 00:48:05 +00003093 return 0;
Ted Kremenekc9f8f5a2011-03-02 20:32:29 +00003094}
3095
Ted Kremenekc5aff442011-03-03 01:21:32 +00003096bool CFGImplicitDtor::isNoReturn(ASTContext &astContext) const {
3097 if (const CXXDestructorDecl *cdecl = getDestructorDecl(astContext)) {
Ted Kremenekc9f8f5a2011-03-02 20:32:29 +00003098 QualType ty = cdecl->getType();
3099 return cast<FunctionType>(ty)->getNoReturnAttr();
3100 }
3101 return false;
Ted Kremenek3c0349e2011-03-01 03:15:10 +00003102}
3103
Ted Kremenek63f58872007-10-01 19:33:33 +00003104//===----------------------------------------------------------------------===//
3105// CFG: Queries for BlkExprs.
3106//===----------------------------------------------------------------------===//
Ted Kremenek7dba8602007-08-29 21:56:09 +00003107
Ted Kremenek63f58872007-10-01 19:33:33 +00003108namespace {
Ted Kremenek86946742008-01-17 20:48:37 +00003109 typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy;
Ted Kremenek63f58872007-10-01 19:33:33 +00003110}
3111
Ted Kremenekf1d10d92011-08-23 23:05:04 +00003112static void FindSubExprAssignments(const Stmt *S,
3113 llvm::SmallPtrSet<const Expr*,50>& Set) {
Ted Kremenek8a693662009-12-23 23:37:10 +00003114 if (!S)
Ted Kremenek33d4aab2008-01-26 00:03:27 +00003115 return;
Mike Stump6d9828c2009-07-17 01:31:16 +00003116
Ted Kremenekf1d10d92011-08-23 23:05:04 +00003117 for (Stmt::const_child_range I = S->children(); I; ++I) {
3118 const Stmt *child = *I;
Ted Kremenek8a693662009-12-23 23:37:10 +00003119 if (!child)
3120 continue;
Ted Kremenekad5a8942010-08-02 23:46:59 +00003121
Ted Kremenekf1d10d92011-08-23 23:05:04 +00003122 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(child))
Ted Kremenek33d4aab2008-01-26 00:03:27 +00003123 if (B->isAssignmentOp()) Set.insert(B);
Mike Stump6d9828c2009-07-17 01:31:16 +00003124
Ted Kremenek8a693662009-12-23 23:37:10 +00003125 FindSubExprAssignments(child, Set);
Ted Kremenek33d4aab2008-01-26 00:03:27 +00003126 }
3127}
3128
Ted Kremenek63f58872007-10-01 19:33:33 +00003129static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) {
3130 BlkExprMapTy* M = new BlkExprMapTy();
Mike Stump6d9828c2009-07-17 01:31:16 +00003131
3132 // Look for assignments that are used as subexpressions. These are the only
3133 // assignments that we want to *possibly* register as a block-level
3134 // expression. Basically, if an assignment occurs both in a subexpression and
3135 // at the block-level, it is a block-level expression.
Ted Kremenekf1d10d92011-08-23 23:05:04 +00003136 llvm::SmallPtrSet<const Expr*,50> SubExprAssignments;
Mike Stump6d9828c2009-07-17 01:31:16 +00003137
Ted Kremenek63f58872007-10-01 19:33:33 +00003138 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I)
Ted Kremenekee82d9b2009-10-12 20:55:07 +00003139 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI)
Ted Kremenek3c0349e2011-03-01 03:15:10 +00003140 if (const CFGStmt *S = BI->getAs<CFGStmt>())
3141 FindSubExprAssignments(S->getStmt(), SubExprAssignments);
Ted Kremenek86946742008-01-17 20:48:37 +00003142
Ted Kremenek411cdee2008-04-16 21:10:48 +00003143 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) {
Mike Stump6d9828c2009-07-17 01:31:16 +00003144
3145 // Iterate over the statements again on identify the Expr* and Stmt* at the
3146 // block-level that are block-level expressions.
Ted Kremenek411cdee2008-04-16 21:10:48 +00003147
Zhongxing Xub36cd3e2010-09-16 01:25:47 +00003148 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) {
Ted Kremenek3c0349e2011-03-01 03:15:10 +00003149 const CFGStmt *CS = BI->getAs<CFGStmt>();
3150 if (!CS)
Zhongxing Xub36cd3e2010-09-16 01:25:47 +00003151 continue;
Ted Kremenekf1d10d92011-08-23 23:05:04 +00003152 if (const Expr *Exp = dyn_cast<Expr>(CS->getStmt())) {
Jordy Roseac73ea82011-06-10 08:49:37 +00003153 assert((Exp->IgnoreParens() == Exp) && "No parens on block-level exps");
Mike Stump6d9828c2009-07-17 01:31:16 +00003154
Ted Kremenekf1d10d92011-08-23 23:05:04 +00003155 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) {
Ted Kremenek33d4aab2008-01-26 00:03:27 +00003156 // Assignment expressions that are not nested within another
Mike Stump6d9828c2009-07-17 01:31:16 +00003157 // expression are really "statements" whose value is never used by
3158 // another expression.
Ted Kremenek411cdee2008-04-16 21:10:48 +00003159 if (B->isAssignmentOp() && !SubExprAssignments.count(Exp))
Ted Kremenek33d4aab2008-01-26 00:03:27 +00003160 continue;
Ted Kremenek9c378f72011-08-12 23:37:29 +00003161 } else if (const StmtExpr *SE = dyn_cast<StmtExpr>(Exp)) {
Mike Stump6d9828c2009-07-17 01:31:16 +00003162 // Special handling for statement expressions. The last statement in
3163 // the statement expression is also a block-level expr.
Ted Kremenek9c378f72011-08-12 23:37:29 +00003164 const CompoundStmt *C = SE->getSubStmt();
Ted Kremenek86946742008-01-17 20:48:37 +00003165 if (!C->body_empty()) {
Jordy Roseac73ea82011-06-10 08:49:37 +00003166 const Stmt *Last = C->body_back();
3167 if (const Expr *LastEx = dyn_cast<Expr>(Last))
3168 Last = LastEx->IgnoreParens();
Ted Kremenek33d4aab2008-01-26 00:03:27 +00003169 unsigned x = M->size();
Jordy Roseac73ea82011-06-10 08:49:37 +00003170 (*M)[Last] = x;
Ted Kremenek86946742008-01-17 20:48:37 +00003171 }
3172 }
Ted Kremeneke2dcd782008-01-25 23:22:27 +00003173
Ted Kremenek33d4aab2008-01-26 00:03:27 +00003174 unsigned x = M->size();
Ted Kremenek411cdee2008-04-16 21:10:48 +00003175 (*M)[Exp] = x;
Ted Kremenek33d4aab2008-01-26 00:03:27 +00003176 }
Zhongxing Xub36cd3e2010-09-16 01:25:47 +00003177 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003178
Ted Kremenek411cdee2008-04-16 21:10:48 +00003179 // Look at terminators. The condition is a block-level expression.
Mike Stump6d9828c2009-07-17 01:31:16 +00003180
Ted Kremenek9c378f72011-08-12 23:37:29 +00003181 Stmt *S = (*I)->getTerminatorCondition();
Mike Stump6d9828c2009-07-17 01:31:16 +00003182
Ted Kremenek390e48b2008-11-12 21:11:49 +00003183 if (S && M->find(S) == M->end()) {
Jordy Roseac73ea82011-06-10 08:49:37 +00003184 unsigned x = M->size();
3185 (*M)[S] = x;
Ted Kremenek411cdee2008-04-16 21:10:48 +00003186 }
3187 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003188
Ted Kremenek63f58872007-10-01 19:33:33 +00003189 return M;
3190}
3191
Ted Kremenek9c378f72011-08-12 23:37:29 +00003192CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt *S) {
Ted Kremenek86946742008-01-17 20:48:37 +00003193 assert(S != NULL);
Ted Kremenek63f58872007-10-01 19:33:33 +00003194 if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); }
Mike Stump6d9828c2009-07-17 01:31:16 +00003195
Ted Kremenek63f58872007-10-01 19:33:33 +00003196 BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap);
Ted Kremenek86946742008-01-17 20:48:37 +00003197 BlkExprMapTy::iterator I = M->find(S);
Ted Kremenek3fa1e4b2010-01-19 20:52:05 +00003198 return (I == M->end()) ? CFG::BlkExprNumTy() : CFG::BlkExprNumTy(I->second);
Ted Kremenek63f58872007-10-01 19:33:33 +00003199}
3200
3201unsigned CFG::getNumBlkExprs() {
3202 if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap))
3203 return M->size();
Zhanyong Wan36f327c2010-11-22 19:32:14 +00003204
3205 // We assume callers interested in the number of BlkExprs will want
3206 // the map constructed if it doesn't already exist.
3207 BlkExprMap = (void*) PopulateBlkExprMap(*this);
3208 return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size();
Ted Kremenek63f58872007-10-01 19:33:33 +00003209}
3210
Ted Kremenek274f4332008-04-28 18:00:46 +00003211//===----------------------------------------------------------------------===//
Ted Kremenekee7f84d2010-09-09 00:06:04 +00003212// Filtered walking of the CFG.
3213//===----------------------------------------------------------------------===//
3214
3215bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F,
Ted Kremenekbe39a562010-09-09 02:57:48 +00003216 const CFGBlock *From, const CFGBlock *To) {
Ted Kremenekee7f84d2010-09-09 00:06:04 +00003217
Ted Kremenek6e400352011-03-07 22:04:39 +00003218 if (To && F.IgnoreDefaultsWithCoveredEnums) {
Ted Kremenekee7f84d2010-09-09 00:06:04 +00003219 // If the 'To' has no label or is labeled but the label isn't a
3220 // CaseStmt then filter this edge.
3221 if (const SwitchStmt *S =
Ted Kremenek6e400352011-03-07 22:04:39 +00003222 dyn_cast_or_null<SwitchStmt>(From->getTerminator().getStmt())) {
Ted Kremenekee7f84d2010-09-09 00:06:04 +00003223 if (S->isAllEnumCasesCovered()) {
Ted Kremenek6e400352011-03-07 22:04:39 +00003224 const Stmt *L = To->getLabel();
3225 if (!L || !isa<CaseStmt>(L))
3226 return true;
Ted Kremenekee7f84d2010-09-09 00:06:04 +00003227 }
3228 }
3229 }
3230
3231 return false;
3232}
3233
3234//===----------------------------------------------------------------------===//
Ted Kremenek274f4332008-04-28 18:00:46 +00003235// Cleanup: CFG dstor.
3236//===----------------------------------------------------------------------===//
3237
Ted Kremenek63f58872007-10-01 19:33:33 +00003238CFG::~CFG() {
3239 delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap);
3240}
Mike Stump6d9828c2009-07-17 01:31:16 +00003241
Ted Kremenek7dba8602007-08-29 21:56:09 +00003242//===----------------------------------------------------------------------===//
3243// CFG pretty printing
3244//===----------------------------------------------------------------------===//
3245
Ted Kremeneke8ee26b2007-08-22 18:22:34 +00003246namespace {
3247
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +00003248class StmtPrinterHelper : public PrinterHelper {
Ted Kremenek3c0349e2011-03-01 03:15:10 +00003249 typedef llvm::DenseMap<const Stmt*,std::pair<unsigned,unsigned> > StmtMapTy;
3250 typedef llvm::DenseMap<const Decl*,std::pair<unsigned,unsigned> > DeclMapTy;
Ted Kremenek42a509f2007-08-31 21:30:12 +00003251 StmtMapTy StmtMap;
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003252 DeclMapTy DeclMap;
Ted Kremenek0a3ed312010-12-17 04:44:39 +00003253 signed currentBlock;
3254 unsigned currentStmt;
Chris Lattnere4f21422009-06-30 01:26:17 +00003255 const LangOptions &LangOpts;
Ted Kremenekd4fdee32007-08-23 21:42:29 +00003256public:
Ted Kremenek1c29bba2007-08-31 22:26:13 +00003257
Chris Lattnere4f21422009-06-30 01:26:17 +00003258 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO)
Ted Kremenek3c0349e2011-03-01 03:15:10 +00003259 : currentBlock(0), currentStmt(0), LangOpts(LO)
3260 {
Ted Kremenek42a509f2007-08-31 21:30:12 +00003261 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) {
3262 unsigned j = 1;
Ted Kremenekee82d9b2009-10-12 20:55:07 +00003263 for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ;
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003264 BI != BEnd; ++BI, ++j ) {
Ted Kremenek3c0349e2011-03-01 03:15:10 +00003265 if (const CFGStmt *SE = BI->getAs<CFGStmt>()) {
3266 const Stmt *stmt= SE->getStmt();
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003267 std::pair<unsigned, unsigned> P((*I)->getBlockID(), j);
Ted Kremenek3c0349e2011-03-01 03:15:10 +00003268 StmtMap[stmt] = P;
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003269
Ted Kremenek3c0349e2011-03-01 03:15:10 +00003270 switch (stmt->getStmtClass()) {
3271 case Stmt::DeclStmtClass:
3272 DeclMap[cast<DeclStmt>(stmt)->getSingleDecl()] = P;
3273 break;
3274 case Stmt::IfStmtClass: {
3275 const VarDecl *var = cast<IfStmt>(stmt)->getConditionVariable();
3276 if (var)
3277 DeclMap[var] = P;
3278 break;
3279 }
3280 case Stmt::ForStmtClass: {
3281 const VarDecl *var = cast<ForStmt>(stmt)->getConditionVariable();
3282 if (var)
3283 DeclMap[var] = P;
3284 break;
3285 }
3286 case Stmt::WhileStmtClass: {
3287 const VarDecl *var =
3288 cast<WhileStmt>(stmt)->getConditionVariable();
3289 if (var)
3290 DeclMap[var] = P;
3291 break;
3292 }
3293 case Stmt::SwitchStmtClass: {
3294 const VarDecl *var =
3295 cast<SwitchStmt>(stmt)->getConditionVariable();
3296 if (var)
3297 DeclMap[var] = P;
3298 break;
3299 }
3300 case Stmt::CXXCatchStmtClass: {
3301 const VarDecl *var =
3302 cast<CXXCatchStmt>(stmt)->getExceptionDecl();
3303 if (var)
3304 DeclMap[var] = P;
3305 break;
3306 }
3307 default:
3308 break;
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003309 }
3310 }
Ted Kremenek42a509f2007-08-31 21:30:12 +00003311 }
Zhongxing Xub36cd3e2010-09-16 01:25:47 +00003312 }
Ted Kremenek42a509f2007-08-31 21:30:12 +00003313 }
Ted Kremenek3c0349e2011-03-01 03:15:10 +00003314
Mike Stump6d9828c2009-07-17 01:31:16 +00003315
Ted Kremenek42a509f2007-08-31 21:30:12 +00003316 virtual ~StmtPrinterHelper() {}
Mike Stump6d9828c2009-07-17 01:31:16 +00003317
Chris Lattnere4f21422009-06-30 01:26:17 +00003318 const LangOptions &getLangOpts() const { return LangOpts; }
Ted Kremenek0a3ed312010-12-17 04:44:39 +00003319 void setBlockID(signed i) { currentBlock = i; }
3320 void setStmtID(unsigned i) { currentStmt = i; }
Mike Stump6d9828c2009-07-17 01:31:16 +00003321
Ted Kremenek9c378f72011-08-12 23:37:29 +00003322 virtual bool handledStmt(Stmt *S, raw_ostream &OS) {
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003323 StmtMapTy::iterator I = StmtMap.find(S);
Ted Kremenek42a509f2007-08-31 21:30:12 +00003324
3325 if (I == StmtMap.end())
3326 return false;
Mike Stump6d9828c2009-07-17 01:31:16 +00003327
Ted Kremenek0a3ed312010-12-17 04:44:39 +00003328 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
3329 && I->second.second == currentStmt) {
Ted Kremenek42a509f2007-08-31 21:30:12 +00003330 return false;
Ted Kremenek3fa1e4b2010-01-19 20:52:05 +00003331 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003332
Ted Kremenek3fa1e4b2010-01-19 20:52:05 +00003333 OS << "[B" << I->second.first << "." << I->second.second << "]";
Ted Kremenek1c29bba2007-08-31 22:26:13 +00003334 return true;
Ted Kremenek42a509f2007-08-31 21:30:12 +00003335 }
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003336
Ted Kremenek9c378f72011-08-12 23:37:29 +00003337 bool handleDecl(const Decl *D, raw_ostream &OS) {
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003338 DeclMapTy::iterator I = DeclMap.find(D);
3339
3340 if (I == DeclMap.end())
3341 return false;
3342
Ted Kremenek0a3ed312010-12-17 04:44:39 +00003343 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock
3344 && I->second.second == currentStmt) {
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003345 return false;
3346 }
3347
3348 OS << "[B" << I->second.first << "." << I->second.second << "]";
3349 return true;
3350 }
Ted Kremenek42a509f2007-08-31 21:30:12 +00003351};
Chris Lattnere4f21422009-06-30 01:26:17 +00003352} // end anonymous namespace
Ted Kremenek42a509f2007-08-31 21:30:12 +00003353
Chris Lattnere4f21422009-06-30 01:26:17 +00003354
3355namespace {
Kovarththanan Rajaratnamba5fb5a2009-11-28 06:07:30 +00003356class CFGBlockTerminatorPrint
Ted Kremenek6fa9b882008-01-08 18:15:10 +00003357 : public StmtVisitor<CFGBlockTerminatorPrint,void> {
Mike Stump6d9828c2009-07-17 01:31:16 +00003358
Ted Kremenek9c378f72011-08-12 23:37:29 +00003359 raw_ostream &OS;
Ted Kremenek42a509f2007-08-31 21:30:12 +00003360 StmtPrinterHelper* Helper;
Douglas Gregord249e1d1f2009-05-29 20:38:28 +00003361 PrintingPolicy Policy;
Ted Kremenek42a509f2007-08-31 21:30:12 +00003362public:
Ted Kremenek9c378f72011-08-12 23:37:29 +00003363 CFGBlockTerminatorPrint(raw_ostream &os, StmtPrinterHelper* helper,
Chris Lattnere4f21422009-06-30 01:26:17 +00003364 const PrintingPolicy &Policy)
Douglas Gregord249e1d1f2009-05-29 20:38:28 +00003365 : OS(os), Helper(helper), Policy(Policy) {}
Mike Stump6d9828c2009-07-17 01:31:16 +00003366
Ted Kremenek9c378f72011-08-12 23:37:29 +00003367 void VisitIfStmt(IfStmt *I) {
Ted Kremenekd4fdee32007-08-23 21:42:29 +00003368 OS << "if ";
Douglas Gregord249e1d1f2009-05-29 20:38:28 +00003369 I->getCond()->printPretty(OS,Helper,Policy);
Ted Kremenekd4fdee32007-08-23 21:42:29 +00003370 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003371
Ted Kremenekd4fdee32007-08-23 21:42:29 +00003372 // Default case.
Ted Kremenek9c378f72011-08-12 23:37:29 +00003373 void VisitStmt(Stmt *Terminator) {
Mike Stump6d9828c2009-07-17 01:31:16 +00003374 Terminator->printPretty(OS, Helper, Policy);
3375 }
3376
Ted Kremenek9c378f72011-08-12 23:37:29 +00003377 void VisitForStmt(ForStmt *F) {
Ted Kremenekd4fdee32007-08-23 21:42:29 +00003378 OS << "for (" ;
Ted Kremenek3fa1e4b2010-01-19 20:52:05 +00003379 if (F->getInit())
3380 OS << "...";
Ted Kremenek535bb202007-08-30 21:28:02 +00003381 OS << "; ";
Ted Kremenek9c378f72011-08-12 23:37:29 +00003382 if (Stmt *C = F->getCond())
Ted Kremenek3fa1e4b2010-01-19 20:52:05 +00003383 C->printPretty(OS, Helper, Policy);
Ted Kremenek535bb202007-08-30 21:28:02 +00003384 OS << "; ";
Ted Kremenek3fa1e4b2010-01-19 20:52:05 +00003385 if (F->getInc())
3386 OS << "...";
Ted Kremeneka2925852008-01-30 23:02:42 +00003387 OS << ")";
Ted Kremenekd4fdee32007-08-23 21:42:29 +00003388 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003389
Ted Kremenek9c378f72011-08-12 23:37:29 +00003390 void VisitWhileStmt(WhileStmt *W) {
Ted Kremenekd4fdee32007-08-23 21:42:29 +00003391 OS << "while " ;
Ted Kremenek9c378f72011-08-12 23:37:29 +00003392 if (Stmt *C = W->getCond())
Ted Kremenek3fa1e4b2010-01-19 20:52:05 +00003393 C->printPretty(OS, Helper, Policy);
Ted Kremenekd4fdee32007-08-23 21:42:29 +00003394 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003395
Ted Kremenek9c378f72011-08-12 23:37:29 +00003396 void VisitDoStmt(DoStmt *D) {
Ted Kremenekd4fdee32007-08-23 21:42:29 +00003397 OS << "do ... while ";
Ted Kremenek9c378f72011-08-12 23:37:29 +00003398 if (Stmt *C = D->getCond())
Ted Kremenek3fa1e4b2010-01-19 20:52:05 +00003399 C->printPretty(OS, Helper, Policy);
Ted Kremenek9da2fb72007-08-27 21:27:44 +00003400 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003401
Ted Kremenek9c378f72011-08-12 23:37:29 +00003402 void VisitSwitchStmt(SwitchStmt *Terminator) {
Ted Kremenek9da2fb72007-08-27 21:27:44 +00003403 OS << "switch ";
Douglas Gregord249e1d1f2009-05-29 20:38:28 +00003404 Terminator->getCond()->printPretty(OS, Helper, Policy);
Ted Kremenek9da2fb72007-08-27 21:27:44 +00003405 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003406
Ted Kremenek9c378f72011-08-12 23:37:29 +00003407 void VisitCXXTryStmt(CXXTryStmt *CS) {
Mike Stump5d1d2022010-01-19 02:20:09 +00003408 OS << "try ...";
3409 }
3410
John McCall56ca35d2011-02-17 10:25:35 +00003411 void VisitAbstractConditionalOperator(AbstractConditionalOperator* C) {
Douglas Gregord249e1d1f2009-05-29 20:38:28 +00003412 C->getCond()->printPretty(OS, Helper, Policy);
Mike Stump6d9828c2009-07-17 01:31:16 +00003413 OS << " ? ... : ...";
Ted Kremenek805e9a82007-08-31 21:49:40 +00003414 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003415
Ted Kremenek9c378f72011-08-12 23:37:29 +00003416 void VisitChooseExpr(ChooseExpr *C) {
Ted Kremenekaeddbf62007-08-31 22:29:13 +00003417 OS << "__builtin_choose_expr( ";
Douglas Gregord249e1d1f2009-05-29 20:38:28 +00003418 C->getCond()->printPretty(OS, Helper, Policy);
Ted Kremeneka2925852008-01-30 23:02:42 +00003419 OS << " )";
Ted Kremenekaeddbf62007-08-31 22:29:13 +00003420 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003421
Ted Kremenek9c378f72011-08-12 23:37:29 +00003422 void VisitIndirectGotoStmt(IndirectGotoStmt *I) {
Ted Kremenek1c29bba2007-08-31 22:26:13 +00003423 OS << "goto *";
Douglas Gregord249e1d1f2009-05-29 20:38:28 +00003424 I->getTarget()->printPretty(OS, Helper, Policy);
Ted Kremenek1c29bba2007-08-31 22:26:13 +00003425 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003426
Ted Kremenek805e9a82007-08-31 21:49:40 +00003427 void VisitBinaryOperator(BinaryOperator* B) {
3428 if (!B->isLogicalOp()) {
3429 VisitExpr(B);
3430 return;
3431 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003432
Douglas Gregord249e1d1f2009-05-29 20:38:28 +00003433 B->getLHS()->printPretty(OS, Helper, Policy);
Mike Stump6d9828c2009-07-17 01:31:16 +00003434
Ted Kremenek805e9a82007-08-31 21:49:40 +00003435 switch (B->getOpcode()) {
John McCall2de56d12010-08-25 11:45:40 +00003436 case BO_LOr:
Ted Kremeneka2925852008-01-30 23:02:42 +00003437 OS << " || ...";
Ted Kremenek805e9a82007-08-31 21:49:40 +00003438 return;
John McCall2de56d12010-08-25 11:45:40 +00003439 case BO_LAnd:
Ted Kremeneka2925852008-01-30 23:02:42 +00003440 OS << " && ...";
Ted Kremenek805e9a82007-08-31 21:49:40 +00003441 return;
3442 default:
David Blaikieb219cfc2011-09-23 05:06:16 +00003443 llvm_unreachable("Invalid logical operator.");
Mike Stump6d9828c2009-07-17 01:31:16 +00003444 }
Ted Kremenek805e9a82007-08-31 21:49:40 +00003445 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003446
Ted Kremenek9c378f72011-08-12 23:37:29 +00003447 void VisitExpr(Expr *E) {
Douglas Gregord249e1d1f2009-05-29 20:38:28 +00003448 E->printPretty(OS, Helper, Policy);
Mike Stump6d9828c2009-07-17 01:31:16 +00003449 }
Ted Kremenekd4fdee32007-08-23 21:42:29 +00003450};
Chris Lattnere4f21422009-06-30 01:26:17 +00003451} // end anonymous namespace
3452
Chris Lattner5f9e2722011-07-23 10:55:15 +00003453static void print_elem(raw_ostream &OS, StmtPrinterHelper* Helper,
Mike Stump079bd722010-01-19 22:00:14 +00003454 const CFGElement &E) {
Ted Kremenek3c0349e2011-03-01 03:15:10 +00003455 if (const CFGStmt *CS = E.getAs<CFGStmt>()) {
Ted Kremenekf1d10d92011-08-23 23:05:04 +00003456 const Stmt *S = CS->getStmt();
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003457
3458 if (Helper) {
Mike Stump6d9828c2009-07-17 01:31:16 +00003459
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003460 // special printing for statement-expressions.
Ted Kremenekf1d10d92011-08-23 23:05:04 +00003461 if (const StmtExpr *SE = dyn_cast<StmtExpr>(S)) {
3462 const CompoundStmt *Sub = SE->getSubStmt();
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003463
John McCall7502c1d2011-02-13 04:07:26 +00003464 if (Sub->children()) {
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003465 OS << "({ ... ; ";
3466 Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS);
3467 OS << " })\n";
3468 return;
3469 }
3470 }
3471 // special printing for comma expressions.
Ted Kremenekf1d10d92011-08-23 23:05:04 +00003472 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003473 if (B->getOpcode() == BO_Comma) {
3474 OS << "... , ";
3475 Helper->handledStmt(B->getRHS(),OS);
3476 OS << '\n';
3477 return;
3478 }
Ted Kremenek1c29bba2007-08-31 22:26:13 +00003479 }
3480 }
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003481 S->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts()));
Mike Stump6d9828c2009-07-17 01:31:16 +00003482
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003483 if (isa<CXXOperatorCallExpr>(S)) {
Zhanyong Wan36f327c2010-11-22 19:32:14 +00003484 OS << " (OperatorCall)";
Ted Kremenek893d4142011-12-21 19:32:38 +00003485 }
3486 else if (isa<CXXBindTemporaryExpr>(S)) {
Zhanyong Wan36f327c2010-11-22 19:32:14 +00003487 OS << " (BindTemporary)";
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003488 }
Ted Kremenek3b7a48f2011-12-21 19:39:59 +00003489 else if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(S)) {
3490 OS << " (CXXConstructExpr, " << CCE->getType().getAsString() << ")";
3491 }
Ted Kremenek893d4142011-12-21 19:32:38 +00003492 else if (const CastExpr *CE = dyn_cast<CastExpr>(S)) {
3493 OS << " (" << CE->getStmtClassName() << ", "
3494 << CE->getCastKindName()
3495 << ", " << CE->getType().getAsString()
3496 << ")";
3497 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003498
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003499 // Expressions need a newline.
3500 if (isa<Expr>(S))
3501 OS << '\n';
Ted Kremenek4e0cfa82010-08-31 18:47:37 +00003502
Ted Kremenek3c0349e2011-03-01 03:15:10 +00003503 } else if (const CFGInitializer *IE = E.getAs<CFGInitializer>()) {
3504 const CXXCtorInitializer *I = IE->getInitializer();
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003505 if (I->isBaseInitializer())
3506 OS << I->getBaseClass()->getAsCXXRecordDecl()->getName();
Francois Pichet00eb3f92010-12-04 09:14:42 +00003507 else OS << I->getAnyMember()->getName();
Mike Stump6d9828c2009-07-17 01:31:16 +00003508
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003509 OS << "(";
Ted Kremenek9c378f72011-08-12 23:37:29 +00003510 if (Expr *IE = I->getInit())
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003511 IE->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts()));
3512 OS << ")";
3513
3514 if (I->isBaseInitializer())
3515 OS << " (Base initializer)\n";
3516 else OS << " (Member initializer)\n";
3517
Ted Kremenek3c0349e2011-03-01 03:15:10 +00003518 } else if (const CFGAutomaticObjDtor *DE = E.getAs<CFGAutomaticObjDtor>()){
Ted Kremenek9c378f72011-08-12 23:37:29 +00003519 const VarDecl *VD = DE->getVarDecl();
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003520 Helper->handleDecl(VD, OS);
3521
Marcin Swiderskib1c52872010-10-25 07:00:40 +00003522 const Type* T = VD->getType().getTypePtr();
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003523 if (const ReferenceType* RT = T->getAs<ReferenceType>())
3524 T = RT->getPointeeType().getTypePtr();
Marcin Swiderskib1c52872010-10-25 07:00:40 +00003525 else if (const Type *ET = T->getArrayElementTypeNoTypeQual())
3526 T = ET;
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003527
3528 OS << ".~" << T->getAsCXXRecordDecl()->getName().str() << "()";
3529 OS << " (Implicit destructor)\n";
Marcin Swiderski7c625d82010-10-05 05:37:00 +00003530
Ted Kremenek3c0349e2011-03-01 03:15:10 +00003531 } else if (const CFGBaseDtor *BE = E.getAs<CFGBaseDtor>()) {
3532 const CXXBaseSpecifier *BS = BE->getBaseSpecifier();
Marcin Swiderski7c625d82010-10-05 05:37:00 +00003533 OS << "~" << BS->getType()->getAsCXXRecordDecl()->getName() << "()";
Zhongxing Xu4e493e02010-10-05 08:38:06 +00003534 OS << " (Base object destructor)\n";
Marcin Swiderski7c625d82010-10-05 05:37:00 +00003535
Ted Kremenek3c0349e2011-03-01 03:15:10 +00003536 } else if (const CFGMemberDtor *ME = E.getAs<CFGMemberDtor>()) {
3537 const FieldDecl *FD = ME->getFieldDecl();
Marcin Swiderski8c5e5d62010-10-25 07:05:54 +00003538
3539 const Type *T = FD->getType().getTypePtr();
3540 if (const Type *ET = T->getArrayElementTypeNoTypeQual())
3541 T = ET;
3542
Marcin Swiderski7c625d82010-10-05 05:37:00 +00003543 OS << "this->" << FD->getName();
Marcin Swiderski8c5e5d62010-10-25 07:05:54 +00003544 OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()";
Zhongxing Xu4e493e02010-10-05 08:38:06 +00003545 OS << " (Member object destructor)\n";
Marcin Swiderski8599e762010-11-03 06:19:35 +00003546
Ted Kremenek3c0349e2011-03-01 03:15:10 +00003547 } else if (const CFGTemporaryDtor *TE = E.getAs<CFGTemporaryDtor>()) {
3548 const CXXBindTemporaryExpr *BT = TE->getBindTemporaryExpr();
Marcin Swiderski8599e762010-11-03 06:19:35 +00003549 OS << "~" << BT->getType()->getAsCXXRecordDecl()->getName() << "()";
3550 OS << " (Temporary object destructor)\n";
Marcin Swiderski1cff1322010-09-21 05:58:15 +00003551 }
Zhongxing Xu81bc7d02010-11-01 06:46:05 +00003552}
Mike Stump6d9828c2009-07-17 01:31:16 +00003553
Ted Kremenek9c378f72011-08-12 23:37:29 +00003554static void print_block(raw_ostream &OS, const CFG* cfg,
3555 const CFGBlock &B,
Ted Kremenek682060c2011-12-22 23:33:52 +00003556 StmtPrinterHelper* Helper, bool print_edges,
3557 bool ShowColors) {
Mike Stump6d9828c2009-07-17 01:31:16 +00003558
Ted Kremenek682060c2011-12-22 23:33:52 +00003559 if (Helper)
3560 Helper->setBlockID(B.getBlockID());
Mike Stump6d9828c2009-07-17 01:31:16 +00003561
Ted Kremenek7dba8602007-08-29 21:56:09 +00003562 // Print the header.
Ted Kremenek682060c2011-12-22 23:33:52 +00003563 if (ShowColors)
3564 OS.changeColor(raw_ostream::YELLOW, true);
3565
3566 OS << "\n [B" << B.getBlockID();
Mike Stump6d9828c2009-07-17 01:31:16 +00003567
Ted Kremenek42a509f2007-08-31 21:30:12 +00003568 if (&B == &cfg->getEntry())
Ted Kremenek682060c2011-12-22 23:33:52 +00003569 OS << " (ENTRY)]\n";
Ted Kremenek42a509f2007-08-31 21:30:12 +00003570 else if (&B == &cfg->getExit())
Ted Kremenek682060c2011-12-22 23:33:52 +00003571 OS << " (EXIT)]\n";
Ted Kremenek42a509f2007-08-31 21:30:12 +00003572 else if (&B == cfg->getIndirectGotoBlock())
Ted Kremenek682060c2011-12-22 23:33:52 +00003573 OS << " (INDIRECT GOTO DISPATCH)]\n";
Ted Kremenek42a509f2007-08-31 21:30:12 +00003574 else
Ted Kremenek682060c2011-12-22 23:33:52 +00003575 OS << "]\n";
3576
3577 if (ShowColors)
3578 OS.resetColor();
Mike Stump6d9828c2009-07-17 01:31:16 +00003579
Ted Kremenek9cffe732007-08-29 23:20:49 +00003580 // Print the label of this block.
Ted Kremenek9c378f72011-08-12 23:37:29 +00003581 if (Stmt *Label = const_cast<Stmt*>(B.getLabel())) {
Ted Kremenek42a509f2007-08-31 21:30:12 +00003582
3583 if (print_edges)
Ted Kremenek682060c2011-12-22 23:33:52 +00003584 OS << " ";
Mike Stump6d9828c2009-07-17 01:31:16 +00003585
Ted Kremenek9c378f72011-08-12 23:37:29 +00003586 if (LabelStmt *L = dyn_cast<LabelStmt>(Label))
Ted Kremenek9cffe732007-08-29 23:20:49 +00003587 OS << L->getName();
Ted Kremenek9c378f72011-08-12 23:37:29 +00003588 else if (CaseStmt *C = dyn_cast<CaseStmt>(Label)) {
Ted Kremenek9cffe732007-08-29 23:20:49 +00003589 OS << "case ";
Chris Lattnere4f21422009-06-30 01:26:17 +00003590 C->getLHS()->printPretty(OS, Helper,
3591 PrintingPolicy(Helper->getLangOpts()));
Ted Kremenek9cffe732007-08-29 23:20:49 +00003592 if (C->getRHS()) {
3593 OS << " ... ";
Chris Lattnere4f21422009-06-30 01:26:17 +00003594 C->getRHS()->printPretty(OS, Helper,
3595 PrintingPolicy(Helper->getLangOpts()));
Ted Kremenek9cffe732007-08-29 23:20:49 +00003596 }
Mike Stump079bd722010-01-19 22:00:14 +00003597 } else if (isa<DefaultStmt>(Label))
Ted Kremenek9cffe732007-08-29 23:20:49 +00003598 OS << "default";
Mike Stump079bd722010-01-19 22:00:14 +00003599 else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Label)) {
Mike Stump5d1d2022010-01-19 02:20:09 +00003600 OS << "catch (";
Mike Stumpa1f93632010-01-20 01:15:34 +00003601 if (CS->getExceptionDecl())
3602 CS->getExceptionDecl()->print(OS, PrintingPolicy(Helper->getLangOpts()),
3603 0);
3604 else
3605 OS << "...";
Mike Stump5d1d2022010-01-19 02:20:09 +00003606 OS << ")";
3607
3608 } else
David Blaikieb219cfc2011-09-23 05:06:16 +00003609 llvm_unreachable("Invalid label statement in CFGBlock.");
Mike Stump6d9828c2009-07-17 01:31:16 +00003610
Ted Kremenek9cffe732007-08-29 23:20:49 +00003611 OS << ":\n";
3612 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003613
Ted Kremenekfddd5182007-08-21 21:42:03 +00003614 // Iterate through the statements in the block and print them.
Ted Kremenekfddd5182007-08-21 21:42:03 +00003615 unsigned j = 1;
Mike Stump6d9828c2009-07-17 01:31:16 +00003616
Ted Kremenek42a509f2007-08-31 21:30:12 +00003617 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ;
3618 I != E ; ++I, ++j ) {
Mike Stump6d9828c2009-07-17 01:31:16 +00003619
Ted Kremenek9cffe732007-08-29 23:20:49 +00003620 // Print the statement # in the basic block and the statement itself.
Ted Kremenek42a509f2007-08-31 21:30:12 +00003621 if (print_edges)
Ted Kremenek682060c2011-12-22 23:33:52 +00003622 OS << " ";
Mike Stump6d9828c2009-07-17 01:31:16 +00003623
Ted Kremeneka95d3752008-09-13 05:16:45 +00003624 OS << llvm::format("%3d", j) << ": ";
Mike Stump6d9828c2009-07-17 01:31:16 +00003625
Ted Kremenek42a509f2007-08-31 21:30:12 +00003626 if (Helper)
3627 Helper->setStmtID(j);
Mike Stump6d9828c2009-07-17 01:31:16 +00003628
Ted Kremenek682060c2011-12-22 23:33:52 +00003629 print_elem(OS, Helper, *I);
Ted Kremenekfddd5182007-08-21 21:42:03 +00003630 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003631
Ted Kremenek9cffe732007-08-29 23:20:49 +00003632 // Print the terminator of this block.
Ted Kremenek42a509f2007-08-31 21:30:12 +00003633 if (B.getTerminator()) {
Ted Kremenek682060c2011-12-22 23:33:52 +00003634 if (ShowColors)
3635 OS.changeColor(raw_ostream::GREEN);
Mike Stump6d9828c2009-07-17 01:31:16 +00003636
Ted Kremenek682060c2011-12-22 23:33:52 +00003637 OS << " T: ";
Mike Stump6d9828c2009-07-17 01:31:16 +00003638
Ted Kremenek42a509f2007-08-31 21:30:12 +00003639 if (Helper) Helper->setBlockID(-1);
Mike Stump6d9828c2009-07-17 01:31:16 +00003640
Chris Lattnere4f21422009-06-30 01:26:17 +00003641 CFGBlockTerminatorPrint TPrinter(OS, Helper,
3642 PrintingPolicy(Helper->getLangOpts()));
Marcin Swiderski4ba72a02010-10-29 05:21:47 +00003643 TPrinter.Visit(const_cast<Stmt*>(B.getTerminator().getStmt()));
Ted Kremeneka2925852008-01-30 23:02:42 +00003644 OS << '\n';
Ted Kremenek682060c2011-12-22 23:33:52 +00003645
3646 if (ShowColors)
3647 OS.resetColor();
Ted Kremenekfddd5182007-08-21 21:42:03 +00003648 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003649
Ted Kremenek9cffe732007-08-29 23:20:49 +00003650 if (print_edges) {
3651 // Print the predecessors of this block.
Ted Kremenek682060c2011-12-22 23:33:52 +00003652 if (!B.pred_empty()) {
3653 const raw_ostream::Colors Color = raw_ostream::BLUE;
3654 if (ShowColors)
3655 OS.changeColor(Color);
3656 OS << " Preds " ;
3657 if (ShowColors)
3658 OS.resetColor();
3659 OS << '(' << B.pred_size() << "):";
3660 unsigned i = 0;
Ted Kremenek9cffe732007-08-29 23:20:49 +00003661
Ted Kremenek682060c2011-12-22 23:33:52 +00003662 if (ShowColors)
3663 OS.changeColor(Color);
3664
3665 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end();
3666 I != E; ++I, ++i) {
Mike Stump6d9828c2009-07-17 01:31:16 +00003667
Ted Kremenek682060c2011-12-22 23:33:52 +00003668 if (i == 8 || (i-8) == 0)
3669 OS << "\n ";
Mike Stump6d9828c2009-07-17 01:31:16 +00003670
Ted Kremenek682060c2011-12-22 23:33:52 +00003671 OS << " B" << (*I)->getBlockID();
3672 }
3673
3674 if (ShowColors)
3675 OS.resetColor();
3676
3677 OS << '\n';
Ted Kremenek9cffe732007-08-29 23:20:49 +00003678 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003679
Ted Kremenek42a509f2007-08-31 21:30:12 +00003680 // Print the successors of this block.
Ted Kremenek682060c2011-12-22 23:33:52 +00003681 if (!B.succ_empty()) {
3682 const raw_ostream::Colors Color = raw_ostream::MAGENTA;
3683 if (ShowColors)
3684 OS.changeColor(Color);
3685 OS << " Succs ";
3686 if (ShowColors)
3687 OS.resetColor();
3688 OS << '(' << B.succ_size() << "):";
3689 unsigned i = 0;
Ted Kremenek42a509f2007-08-31 21:30:12 +00003690
Ted Kremenek682060c2011-12-22 23:33:52 +00003691 if (ShowColors)
3692 OS.changeColor(Color);
Mike Stump6d9828c2009-07-17 01:31:16 +00003693
Ted Kremenek682060c2011-12-22 23:33:52 +00003694 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end();
3695 I != E; ++I, ++i) {
Ted Kremenek42a509f2007-08-31 21:30:12 +00003696
Ted Kremenek682060c2011-12-22 23:33:52 +00003697 if (i == 8 || (i-8) % 10 == 0)
3698 OS << "\n ";
3699
3700 if (*I)
3701 OS << " B" << (*I)->getBlockID();
3702 else
3703 OS << " NULL";
3704 }
3705
3706 if (ShowColors)
3707 OS.resetColor();
3708 OS << '\n';
Ted Kremenek42a509f2007-08-31 21:30:12 +00003709 }
Ted Kremenekfddd5182007-08-21 21:42:03 +00003710 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003711}
Ted Kremenek42a509f2007-08-31 21:30:12 +00003712
Ted Kremenek42a509f2007-08-31 21:30:12 +00003713
3714/// dump - A simple pretty printer of a CFG that outputs to stderr.
Ted Kremenek682060c2011-12-22 23:33:52 +00003715void CFG::dump(const LangOptions &LO, bool ShowColors) const {
3716 print(llvm::errs(), LO, ShowColors);
3717}
Ted Kremenek42a509f2007-08-31 21:30:12 +00003718
3719/// print - A simple pretty printer of a CFG that outputs to an ostream.
Ted Kremenek682060c2011-12-22 23:33:52 +00003720void CFG::print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const {
Chris Lattnere4f21422009-06-30 01:26:17 +00003721 StmtPrinterHelper Helper(this, LO);
Mike Stump6d9828c2009-07-17 01:31:16 +00003722
Ted Kremenek42a509f2007-08-31 21:30:12 +00003723 // Print the entry block.
Ted Kremenek682060c2011-12-22 23:33:52 +00003724 print_block(OS, this, getEntry(), &Helper, true, ShowColors);
Mike Stump6d9828c2009-07-17 01:31:16 +00003725
Ted Kremenek42a509f2007-08-31 21:30:12 +00003726 // Iterate through the CFGBlocks and print them one by one.
3727 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) {
3728 // Skip the entry block, because we already printed it.
Ted Kremenekee82d9b2009-10-12 20:55:07 +00003729 if (&(**I) == &getEntry() || &(**I) == &getExit())
Ted Kremenek42a509f2007-08-31 21:30:12 +00003730 continue;
Mike Stump6d9828c2009-07-17 01:31:16 +00003731
Ted Kremenek682060c2011-12-22 23:33:52 +00003732 print_block(OS, this, **I, &Helper, true, ShowColors);
Ted Kremenek42a509f2007-08-31 21:30:12 +00003733 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003734
Ted Kremenek42a509f2007-08-31 21:30:12 +00003735 // Print the exit block.
Ted Kremenek682060c2011-12-22 23:33:52 +00003736 print_block(OS, this, getExit(), &Helper, true, ShowColors);
3737 OS << '\n';
Ted Kremenekd0172432008-11-24 20:50:24 +00003738 OS.flush();
Mike Stump6d9828c2009-07-17 01:31:16 +00003739}
Ted Kremenek42a509f2007-08-31 21:30:12 +00003740
3741/// dump - A simply pretty printer of a CFGBlock that outputs to stderr.
Ted Kremenek682060c2011-12-22 23:33:52 +00003742void CFGBlock::dump(const CFG* cfg, const LangOptions &LO,
3743 bool ShowColors) const {
3744 print(llvm::errs(), cfg, LO, ShowColors);
Chris Lattnere4f21422009-06-30 01:26:17 +00003745}
Ted Kremenek42a509f2007-08-31 21:30:12 +00003746
3747/// print - A simple pretty printer of a CFGBlock that outputs to an ostream.
3748/// Generally this will only be called from CFG::print.
Ted Kremenek9c378f72011-08-12 23:37:29 +00003749void CFGBlock::print(raw_ostream &OS, const CFG* cfg,
Ted Kremenek682060c2011-12-22 23:33:52 +00003750 const LangOptions &LO, bool ShowColors) const {
Chris Lattnere4f21422009-06-30 01:26:17 +00003751 StmtPrinterHelper Helper(cfg, LO);
Ted Kremenek682060c2011-12-22 23:33:52 +00003752 print_block(OS, cfg, *this, &Helper, true, ShowColors);
3753 OS << '\n';
Ted Kremenek026473c2007-08-23 16:51:22 +00003754}
Ted Kremenek7dba8602007-08-29 21:56:09 +00003755
Ted Kremeneka2925852008-01-30 23:02:42 +00003756/// printTerminator - A simple pretty printer of the terminator of a CFGBlock.
Chris Lattner5f9e2722011-07-23 10:55:15 +00003757void CFGBlock::printTerminator(raw_ostream &OS,
Mike Stump6d9828c2009-07-17 01:31:16 +00003758 const LangOptions &LO) const {
Chris Lattnere4f21422009-06-30 01:26:17 +00003759 CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO));
Marcin Swiderski4ba72a02010-10-29 05:21:47 +00003760 TPrinter.Visit(const_cast<Stmt*>(getTerminator().getStmt()));
Ted Kremeneka2925852008-01-30 23:02:42 +00003761}
3762
Ted Kremenek9c378f72011-08-12 23:37:29 +00003763Stmt *CFGBlock::getTerminatorCondition() {
Marcin Swiderski4ba72a02010-10-29 05:21:47 +00003764 Stmt *Terminator = this->Terminator;
Ted Kremenek411cdee2008-04-16 21:10:48 +00003765 if (!Terminator)
3766 return NULL;
Mike Stump6d9828c2009-07-17 01:31:16 +00003767
Ted Kremenek9c378f72011-08-12 23:37:29 +00003768 Expr *E = NULL;
Mike Stump6d9828c2009-07-17 01:31:16 +00003769
Ted Kremenek411cdee2008-04-16 21:10:48 +00003770 switch (Terminator->getStmtClass()) {
3771 default:
3772 break;
Mike Stump6d9828c2009-07-17 01:31:16 +00003773
Ted Kremenek411cdee2008-04-16 21:10:48 +00003774 case Stmt::ForStmtClass:
3775 E = cast<ForStmt>(Terminator)->getCond();
3776 break;
Mike Stump6d9828c2009-07-17 01:31:16 +00003777
Ted Kremenek411cdee2008-04-16 21:10:48 +00003778 case Stmt::WhileStmtClass:
3779 E = cast<WhileStmt>(Terminator)->getCond();
3780 break;
Mike Stump6d9828c2009-07-17 01:31:16 +00003781
Ted Kremenek411cdee2008-04-16 21:10:48 +00003782 case Stmt::DoStmtClass:
3783 E = cast<DoStmt>(Terminator)->getCond();
3784 break;
Mike Stump6d9828c2009-07-17 01:31:16 +00003785
Ted Kremenek411cdee2008-04-16 21:10:48 +00003786 case Stmt::IfStmtClass:
3787 E = cast<IfStmt>(Terminator)->getCond();
3788 break;
Mike Stump6d9828c2009-07-17 01:31:16 +00003789
Ted Kremenek411cdee2008-04-16 21:10:48 +00003790 case Stmt::ChooseExprClass:
3791 E = cast<ChooseExpr>(Terminator)->getCond();
3792 break;
Mike Stump6d9828c2009-07-17 01:31:16 +00003793
Ted Kremenek411cdee2008-04-16 21:10:48 +00003794 case Stmt::IndirectGotoStmtClass:
3795 E = cast<IndirectGotoStmt>(Terminator)->getTarget();
3796 break;
Mike Stump6d9828c2009-07-17 01:31:16 +00003797
Ted Kremenek411cdee2008-04-16 21:10:48 +00003798 case Stmt::SwitchStmtClass:
3799 E = cast<SwitchStmt>(Terminator)->getCond();
3800 break;
Mike Stump6d9828c2009-07-17 01:31:16 +00003801
John McCall56ca35d2011-02-17 10:25:35 +00003802 case Stmt::BinaryConditionalOperatorClass:
3803 E = cast<BinaryConditionalOperator>(Terminator)->getCond();
3804 break;
3805
Ted Kremenek411cdee2008-04-16 21:10:48 +00003806 case Stmt::ConditionalOperatorClass:
3807 E = cast<ConditionalOperator>(Terminator)->getCond();
3808 break;
Mike Stump6d9828c2009-07-17 01:31:16 +00003809
Ted Kremenek411cdee2008-04-16 21:10:48 +00003810 case Stmt::BinaryOperatorClass: // '&&' and '||'
3811 E = cast<BinaryOperator>(Terminator)->getLHS();
Ted Kremenek390e48b2008-11-12 21:11:49 +00003812 break;
Mike Stump6d9828c2009-07-17 01:31:16 +00003813
Ted Kremenek390e48b2008-11-12 21:11:49 +00003814 case Stmt::ObjCForCollectionStmtClass:
Mike Stump6d9828c2009-07-17 01:31:16 +00003815 return Terminator;
Ted Kremenek411cdee2008-04-16 21:10:48 +00003816 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003817
Ted Kremenek411cdee2008-04-16 21:10:48 +00003818 return E ? E->IgnoreParens() : NULL;
3819}
3820
Ted Kremenek7dba8602007-08-29 21:56:09 +00003821//===----------------------------------------------------------------------===//
3822// CFG Graphviz Visualization
3823//===----------------------------------------------------------------------===//
3824
Ted Kremenek42a509f2007-08-31 21:30:12 +00003825
3826#ifndef NDEBUG
Mike Stump6d9828c2009-07-17 01:31:16 +00003827static StmtPrinterHelper* GraphHelper;
Ted Kremenek42a509f2007-08-31 21:30:12 +00003828#endif
3829
Chris Lattnere4f21422009-06-30 01:26:17 +00003830void CFG::viewCFG(const LangOptions &LO) const {
Ted Kremenek42a509f2007-08-31 21:30:12 +00003831#ifndef NDEBUG
Chris Lattnere4f21422009-06-30 01:26:17 +00003832 StmtPrinterHelper H(this, LO);
Ted Kremenek42a509f2007-08-31 21:30:12 +00003833 GraphHelper = &H;
3834 llvm::ViewGraph(this,"CFG");
3835 GraphHelper = NULL;
Ted Kremenek42a509f2007-08-31 21:30:12 +00003836#endif
3837}
3838
Ted Kremenek7dba8602007-08-29 21:56:09 +00003839namespace llvm {
3840template<>
3841struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits {
Tobias Grosser006b0eb2009-11-30 14:16:05 +00003842
3843 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
3844
Ted Kremenek9c378f72011-08-12 23:37:29 +00003845 static std::string getNodeLabel(const CFGBlock *Node, const CFG* Graph) {
Ted Kremenek7dba8602007-08-29 21:56:09 +00003846
Hartmut Kaiserbd250b42007-09-16 00:28:28 +00003847#ifndef NDEBUG
Ted Kremeneka95d3752008-09-13 05:16:45 +00003848 std::string OutSStr;
3849 llvm::raw_string_ostream Out(OutSStr);
Ted Kremenek682060c2011-12-22 23:33:52 +00003850 print_block(Out,Graph, *Node, GraphHelper, false, false);
Ted Kremeneka95d3752008-09-13 05:16:45 +00003851 std::string& OutStr = Out.str();
Ted Kremenek7dba8602007-08-29 21:56:09 +00003852
3853 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin());
3854
3855 // Process string output to make it nicer...
3856 for (unsigned i = 0; i != OutStr.length(); ++i)
3857 if (OutStr[i] == '\n') { // Left justify
3858 OutStr[i] = '\\';
3859 OutStr.insert(OutStr.begin()+i+1, 'l');
3860 }
Mike Stump6d9828c2009-07-17 01:31:16 +00003861
Ted Kremenek7dba8602007-08-29 21:56:09 +00003862 return OutStr;
Hartmut Kaiserbd250b42007-09-16 00:28:28 +00003863#else
3864 return "";
3865#endif
Ted Kremenek7dba8602007-08-29 21:56:09 +00003866 }
3867};
3868} // end namespace llvm