 |
|
 |
|
| Files: |
1 |
|
Branches Taken: |
66.7% |
8 / 12 |
| Generated: |
2010-02-10 01:31 |
|
Branches Executed: |
83.3% |
10 / 12 |
| |
|
Line Coverage: |
81.1% |
90 / 111 |
| |
 |
|
 |
1 : //===--- CFG.h - Classes for representing and building CFGs------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file defines the CFG and CFGBuilder classes for representing and
11 : // building Control-Flow Graphs (CFGs) from ASTs.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #ifndef LLVM_CLANG_CFG_H
16 : #define LLVM_CLANG_CFG_H
17 :
18 : #include "llvm/ADT/PointerIntPair.h"
19 : #include "llvm/ADT/GraphTraits.h"
20 : #include "llvm/Support/Allocator.h"
21 : #include "llvm/Support/Casting.h"
22 : #include "clang/Analysis/Support/BumpVector.h"
23 : #include "clang/Basic/SourceLocation.h"
24 : #include <cassert>
25 :
26 : namespace llvm {
27 : class raw_ostream;
28 : }
29 : namespace clang {
30 : class Decl;
31 : class Stmt;
32 : class Expr;
33 : class CFG;
34 : class PrinterHelper;
35 : class LangOptions;
36 : class ASTContext;
37 :
38 : namespace {
39 : // An element of the CFG for implicit descructor calls implied by the language
40 : // rules.
41 : class Dtor {
42 : // Statement that introduces the variable.
43 : Stmt *S;
44 : // A token which ends the scope, return, goto, throw, }.
45 : SourceLocation Loc;
46 : public:
47 : Dtor(Stmt *s, SourceLocation l) : S(s), Loc(l) {
48 : }
49 : SourceLocation getLoc() { return Loc; }
50 : Stmt *getStmt() { return S; }
51 : };
52 : }
53 :
54 : /// CFGElement - Represents a top-level expression in a basic block.
55 3736: class CFGElement {
56 : llvm::PointerIntPair<Stmt *, 2> Data;
57 : public:
58 : enum Type { StartScope, EndScope };
59 230: explicit CFGElement() {}
19: branch 0 taken
18462: branch 1 taken
60 18481: CFGElement(Stmt *S, bool lvalue) : Data(S, lvalue ? 1 : 0) {}
0: branch 0 not taken
0: branch 1 not taken
61 0: CFGElement(Stmt *S, Type t) : Data(S, t == StartScope ? 2 : 3) {}
62 : // CFGElement(Dtor *S, Type t) : Data(reinterpret_cast<Stmt*>(S), 4) {}
63 108837: Stmt *getStmt() const { return Data.getPointer(); }
64 11825: bool asLValue() const { return Data.getInt() == 1; }
65 0: bool asStartScope() const { return Data.getInt() == 2; }
66 0: bool asEndScope() const { return Data.getInt() == 3; }
67 : bool asDtor() const { return Data.getInt() == 4; }
68 67440: operator Stmt*() const { return getStmt(); }
69 6544: operator bool() const { return getStmt() != 0; }
70 : operator Dtor*() const { return reinterpret_cast<Dtor*>(getStmt()); }
71 : };
72 :
73 : /// CFGBlock - Represents a single basic block in a source-level CFG.
74 : /// It consists of:
75 : ///
76 : /// (1) A set of statements/expressions (which may contain subexpressions).
77 : /// (2) A "terminator" statement (not in the set of statements).
78 : /// (3) A list of successors and predecessors.
79 : ///
80 : /// Terminator: The terminator represents the type of control-flow that occurs
81 : /// at the end of the basic block. The terminator is a Stmt* referring to an
82 : /// AST node that has control-flow: if-statements, breaks, loops, etc.
83 : /// If the control-flow is conditional, the condition expression will appear
84 : /// within the set of statements in the block (usually the last statement).
85 : ///
86 : /// Predecessors: the order in the set of predecessors is arbitrary.
87 : ///
88 : /// Successors: the order in the set of successors is NOT arbitrary. We
89 : /// currently have the following orderings based on the terminator:
90 : ///
91 : /// Terminator Successor Ordering
92 : /// -----------------------------------------------------
93 : /// if Then Block; Else Block
94 : /// ? operator LHS expression; RHS expression
95 : /// &&, || expression that uses result of && or ||, RHS
96 : ///
97 : class CFGBlock {
98 : class StatementList {
99 : typedef BumpVector<CFGElement> ImplTy;
100 : ImplTy Impl;
101 : public:
102 21483: StatementList(BumpVectorContext &C) : Impl(C, 4) {}
103 :
104 : typedef std::reverse_iterator<ImplTy::iterator> iterator;
105 : typedef std::reverse_iterator<ImplTy::const_iterator> const_iterator;
106 : typedef ImplTy::iterator reverse_iterator;
107 : typedef ImplTy::const_iterator const_reverse_iterator;
108 :
109 18481: void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); }
110 7146: CFGElement front() const { return Impl.back(); }
111 : CFGElement back() const { return Impl.front(); }
112 :
113 28134: iterator begin() { return Impl.rbegin(); }
114 28134: iterator end() { return Impl.rend(); }
115 124: const_iterator begin() const { return Impl.rbegin(); }
116 124: const_iterator end() const { return Impl.rend(); }
117 : reverse_iterator rbegin() { return Impl.begin(); }
118 : reverse_iterator rend() { return Impl.end(); }
119 25188: const_reverse_iterator rbegin() const { return Impl.begin(); }
120 25188: const_reverse_iterator rend() const { return Impl.end(); }
121 :
122 20719: CFGElement operator[](size_t i) const {
0: branch 1 not taken
20719: branch 2 taken
123 20719: assert(i < Impl.size());
124 20719: return Impl[Impl.size() - 1 - i];
125 : }
126 :
127 21457: size_t size() const { return Impl.size(); }
128 20962: bool empty() const { return Impl.empty(); }
129 : };
130 :
131 : /// Stmts - The set of statements in the basic block.
132 : StatementList Stmts;
133 :
134 : /// Label - An (optional) label that prefixes the executable
135 : /// statements in the block. When this variable is non-NULL, it is
136 : /// either an instance of LabelStmt, SwitchCase or CXXCatchStmt.
137 : Stmt *Label;
138 :
139 : /// Terminator - The terminator for a basic block that
140 : /// indicates the type of control-flow that occurs between a block
141 : /// and its successors.
142 : Stmt *Terminator;
143 :
144 : /// LoopTarget - Some blocks are used to represent the "loop edge" to
145 : /// the start of a loop from within the loop body. This Stmt* will be
146 : /// refer to the loop statement for such blocks (and be null otherwise).
147 : const Stmt *LoopTarget;
148 :
149 : /// BlockID - A numerical ID assigned to a CFGBlock during construction
150 : /// of the CFG.
151 : unsigned BlockID;
152 :
153 : /// Predecessors/Successors - Keep track of the predecessor / successor
154 : /// CFG blocks.
155 : typedef BumpVector<CFGBlock*> AdjacentBlocks;
156 : AdjacentBlocks Preds;
157 : AdjacentBlocks Succs;
158 :
159 : public:
160 21483: explicit CFGBlock(unsigned blockid, BumpVectorContext &C)
161 : : Stmts(C), Label(NULL), Terminator(NULL), LoopTarget(NULL),
162 21483: BlockID(blockid), Preds(C, 1), Succs(C, 1) {}
163 : ~CFGBlock() {}
164 :
165 : // Statement iterators
166 : typedef StatementList::iterator iterator;
167 : typedef StatementList::const_iterator const_iterator;
168 : typedef StatementList::reverse_iterator reverse_iterator;
169 : typedef StatementList::const_reverse_iterator const_reverse_iterator;
170 :
171 7146: CFGElement front() const { return Stmts.front(); }
172 : CFGElement back() const { return Stmts.back(); }
173 :
174 28134: iterator begin() { return Stmts.begin(); }
175 28134: iterator end() { return Stmts.end(); }
176 124: const_iterator begin() const { return Stmts.begin(); }
177 124: const_iterator end() const { return Stmts.end(); }
178 :
179 : reverse_iterator rbegin() { return Stmts.rbegin(); }
180 : reverse_iterator rend() { return Stmts.rend(); }
181 25188: const_reverse_iterator rbegin() const { return Stmts.rbegin(); }
182 25188: const_reverse_iterator rend() const { return Stmts.rend(); }
183 :
184 21457: unsigned size() const { return Stmts.size(); }
185 20962: bool empty() const { return Stmts.empty(); }
186 :
187 20719: CFGElement operator[](size_t i) const { return Stmts[i]; }
188 :
189 : // CFG iterators
190 : typedef AdjacentBlocks::iterator pred_iterator;
191 : typedef AdjacentBlocks::const_iterator const_pred_iterator;
192 : typedef AdjacentBlocks::reverse_iterator pred_reverse_iterator;
193 : typedef AdjacentBlocks::const_reverse_iterator const_pred_reverse_iterator;
194 :
195 : typedef AdjacentBlocks::iterator succ_iterator;
196 : typedef AdjacentBlocks::const_iterator const_succ_iterator;
197 : typedef AdjacentBlocks::reverse_iterator succ_reverse_iterator;
198 : typedef AdjacentBlocks::const_reverse_iterator const_succ_reverse_iterator;
199 :
200 3736: pred_iterator pred_begin() { return Preds.begin(); }
201 3736: pred_iterator pred_end() { return Preds.end(); }
202 15026: const_pred_iterator pred_begin() const { return Preds.begin(); }
203 15026: const_pred_iterator pred_end() const { return Preds.end(); }
204 :
205 : pred_reverse_iterator pred_rbegin() { return Preds.rbegin(); }
206 : pred_reverse_iterator pred_rend() { return Preds.rend(); }
207 : const_pred_reverse_iterator pred_rbegin() const { return Preds.rbegin(); }
208 : const_pred_reverse_iterator pred_rend() const { return Preds.rend(); }
209 :
210 22873: succ_iterator succ_begin() { return Succs.begin(); }
211 12336: succ_iterator succ_end() { return Succs.end(); }
212 15026: const_succ_iterator succ_begin() const { return Succs.begin(); }
213 15026: const_succ_iterator succ_end() const { return Succs.end(); }
214 :
215 52: succ_reverse_iterator succ_rbegin() { return Succs.rbegin(); }
216 36: succ_reverse_iterator succ_rend() { return Succs.rend(); }
217 : const_succ_reverse_iterator succ_rbegin() const { return Succs.rbegin(); }
218 : const_succ_reverse_iterator succ_rend() const { return Succs.rend(); }
219 :
220 8226: unsigned succ_size() const { return Succs.size(); }
221 : bool succ_empty() const { return Succs.empty(); }
222 :
223 21: unsigned pred_size() const { return Preds.size(); }
224 : bool pred_empty() const { return Preds.empty(); }
225 :
226 : // Manipulation of block contents
227 :
228 2483: void setTerminator(Stmt* Statement) { Terminator = Statement; }
229 269: void setLabel(Stmt* Statement) { Label = Statement; }
230 319: void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; }
231 :
232 6528: Stmt* getTerminator() { return Terminator; }
233 958: const Stmt* getTerminator() const { return Terminator; }
234 :
235 : Stmt* getTerminatorCondition();
236 :
237 : const Stmt* getTerminatorCondition() const {
238 : return const_cast<CFGBlock*>(this)->getTerminatorCondition();
239 : }
240 :
241 958: const Stmt *getLoopTarget() const { return LoopTarget; }
242 :
243 : bool hasBinaryBranchTerminator() const;
244 :
245 94: Stmt* getLabel() { return Label; }
246 0: const Stmt* getLabel() const { return Label; }
247 :
248 : void reverseStmts();
249 :
250 42689: unsigned getBlockID() const { return BlockID; }
251 :
252 : void dump(const CFG *cfg, const LangOptions &LO) const;
253 : void print(llvm::raw_ostream &OS, const CFG* cfg, const LangOptions &LO) const;
254 : void printTerminator(llvm::raw_ostream &OS, const LangOptions &LO) const;
255 :
256 18377: void addSuccessor(CFGBlock* Block, BumpVectorContext &C) {
257 18377: if (Block)
258 18051: Block->Preds.push_back(this, C);
259 18377: Succs.push_back(Block, C);
260 18377: }
261 :
262 18481: void appendStmt(Stmt* Statement, BumpVectorContext &C, bool asLValue) {
263 18481: Stmts.push_back(CFGElement(Statement, asLValue), C);
264 18481: }
265 0: void StartScope(Stmt* S, BumpVectorContext &C) {
266 0: Stmts.push_back(CFGElement(S, CFGElement::StartScope), C);
267 0: }
268 0: void EndScope(Stmt* S, BumpVectorContext &C) {
269 0: Stmts.push_back(CFGElement(S, CFGElement::EndScope), C);
270 0: }
271 : };
272 :
273 :
274 : /// CFG - Represents a source-level, intra-procedural CFG that represents the
275 : /// control-flow of a Stmt. The Stmt can represent an entire function body,
276 : /// or a single expression. A CFG will always contain one empty block that
277 : /// represents the Exit point of the CFG. A CFG will also contain a designated
278 : /// Entry block. The CFG solely represents control-flow; it consists of
279 : /// CFGBlocks which are simply containers of Stmt*'s in the AST the CFG
280 : /// was constructed from.
281 : class CFG {
282 : public:
283 : //===--------------------------------------------------------------------===//
284 : // CFG Construction & Manipulation.
285 : //===--------------------------------------------------------------------===//
286 :
287 : /// buildCFG - Builds a CFG from an AST. The responsibility to free the
288 : /// constructed CFG belongs to the caller.
289 : static CFG* buildCFG(const Decl *D, Stmt* AST, ASTContext *C,
290 : bool AddEHEdges = false,
291 : bool AddScopes = false);
292 :
293 : /// createBlock - Create a new block in the CFG. The CFG owns the block;
294 : /// the caller should not directly free it.
295 : CFGBlock* createBlock();
296 :
297 : /// setEntry - Set the entry block of the CFG. This is typically used
298 : /// only during CFG construction. Most CFG clients expect that the
299 : /// entry block has no predecessors and contains no statements.
300 5486: void setEntry(CFGBlock *B) { Entry = B; }
301 :
302 : /// setIndirectGotoBlock - Set the block used for indirect goto jumps.
303 : /// This is typically used only during CFG construction.
304 13: void setIndirectGotoBlock(CFGBlock* B) { IndirectGotoBlock = B; }
305 :
306 : //===--------------------------------------------------------------------===//
307 : // Block Iterators
308 : //===--------------------------------------------------------------------===//
309 :
310 : typedef BumpVector<CFGBlock*> CFGBlockListTy;
311 : typedef CFGBlockListTy::iterator iterator;
312 : typedef CFGBlockListTy::const_iterator const_iterator;
313 : typedef std::reverse_iterator<iterator> reverse_iterator;
314 : typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
315 :
316 : CFGBlock& front() { return *Blocks.front(); }
317 26969: CFGBlock& back() { return *Blocks.back(); }
318 :
319 27637: iterator begin() { return Blocks.begin(); }
320 27637: iterator end() { return Blocks.end(); }
321 4524: const_iterator begin() const { return Blocks.begin(); }
322 4524: const_iterator end() const { return Blocks.end(); }
323 :
324 : reverse_iterator rbegin() { return Blocks.rbegin(); }
325 : reverse_iterator rend() { return Blocks.rend(); }
326 : const_reverse_iterator rbegin() const { return Blocks.rbegin(); }
327 : const_reverse_iterator rend() const { return Blocks.rend(); }
328 :
329 5612: CFGBlock& getEntry() { return *Entry; }
330 0: const CFGBlock& getEntry() const { return *Entry; }
331 29470: CFGBlock& getExit() { return *Exit; }
332 0: const CFGBlock& getExit() const { return *Exit; }
333 :
334 5499: CFGBlock* getIndirectGotoBlock() { return IndirectGotoBlock; }
335 0: const CFGBlock* getIndirectGotoBlock() const { return IndirectGotoBlock; }
336 :
337 : //===--------------------------------------------------------------------===//
338 : // Member templates useful for various batch operations over CFGs.
339 : //===--------------------------------------------------------------------===//
340 :
341 : template <typename CALLBACK>
342 2262: void VisitBlockStmts(CALLBACK& O) const {
8942: branch 2 taken
2010: branch 3 taken
343 12548: for (const_iterator I=begin(), E=end(); I != E; ++I)
9945: branch 6 taken
8942: branch 7 taken
344 21881: for (CFGBlock::const_iterator BI=(*I)->begin(), BE=(*I)->end();
345 : BI != BE; ++BI)
346 11595: O(*BI);
347 2262: }
348 :
349 : //===--------------------------------------------------------------------===//
350 : // CFG Introspection.
351 : //===--------------------------------------------------------------------===//
352 :
353 : struct BlkExprNumTy {
354 : const signed Idx;
355 77777: explicit BlkExprNumTy(signed idx) : Idx(idx) {}
356 134579: explicit BlkExprNumTy() : Idx(-1) {}
357 212356: operator bool() const { return Idx >= 0; }
0: branch 0 not taken
36579: branch 1 taken
358 36579: operator unsigned() const { assert(Idx >=0); return (unsigned) Idx; }
359 : };
360 :
361 175777: bool isBlkExpr(const Stmt* S) { return getBlkExprNum(S); }
362 : BlkExprNumTy getBlkExprNum(const Stmt* S);
363 : unsigned getNumBlkExprs();
364 :
365 : /// getNumBlockIDs - Returns the total number of BlockIDs allocated (which
366 : /// start at 0).
367 6960: unsigned getNumBlockIDs() const { return NumBlockIDs; }
368 :
369 : //===--------------------------------------------------------------------===//
370 : // CFG Debugging: Pretty-Printing and Visualization.
371 : //===--------------------------------------------------------------------===//
372 :
373 : void viewCFG(const LangOptions &LO) const;
374 : void print(llvm::raw_ostream& OS, const LangOptions &LO) const;
375 : void dump(const LangOptions &LO) const;
376 :
377 : //===--------------------------------------------------------------------===//
378 : // Internal: constructors and data.
379 : //===--------------------------------------------------------------------===//
380 :
381 5486: CFG() : Entry(NULL), Exit(NULL), IndirectGotoBlock(NULL), NumBlockIDs(0),
382 5486: BlkExprMap(NULL), Blocks(BlkBVC, 10) {}
383 :
384 : ~CFG();
385 :
386 21733: llvm::BumpPtrAllocator& getAllocator() {
387 21733: return BlkBVC.getAllocator();
388 : }
389 :
390 36858: BumpVectorContext &getBumpVectorContext() {
391 36858: return BlkBVC;
392 : }
393 :
394 : private:
395 : CFGBlock* Entry;
396 : CFGBlock* Exit;
397 : CFGBlock* IndirectGotoBlock; // Special block to contain collective dispatch
398 : // for indirect gotos
399 : unsigned NumBlockIDs;
400 :
401 : // BlkExprMap - An opaque pointer to prevent inclusion of DenseMap.h.
402 : // It represents a map from Expr* to integers to record the set of
403 : // block-level expressions and their "statement number" in the CFG.
404 : void* BlkExprMap;
405 :
406 : BumpVectorContext BlkBVC;
407 :
408 : CFGBlockListTy Blocks;
409 :
410 : };
411 : } // end namespace clang
412 :
413 : //===----------------------------------------------------------------------===//
414 : // GraphTraits specializations for CFG basic block graphs (source-level CFGs)
415 : //===----------------------------------------------------------------------===//
416 :
417 : namespace llvm {
418 :
419 : /// Implement simplify_type for CFGElement, so that we can dyn_cast from
420 : /// CFGElement to a specific Stmt class.
421 : template <> struct simplify_type<const ::clang::CFGElement> {
422 : typedef ::clang::Stmt* SimpleType;
423 22106: static SimpleType getSimplifiedValue(const ::clang::CFGElement &Val) {
424 22106: return Val.getStmt();
425 : }
426 : };
427 :
428 : template <> struct simplify_type< ::clang::CFGElement>
429 : : public simplify_type<const ::clang::CFGElement> {};
430 :
431 : // Traits for: CFGBlock
432 :
433 : template <> struct GraphTraits< ::clang::CFGBlock* > {
434 : typedef ::clang::CFGBlock NodeType;
435 : typedef ::clang::CFGBlock::succ_iterator ChildIteratorType;
436 :
437 : static NodeType* getEntryNode(::clang::CFGBlock* BB)
438 : { return BB; }
439 :
440 : static inline ChildIteratorType child_begin(NodeType* N)
441 : { return N->succ_begin(); }
442 :
443 : static inline ChildIteratorType child_end(NodeType* N)
444 : { return N->succ_end(); }
445 : };
446 :
447 : template <> struct GraphTraits< const ::clang::CFGBlock* > {
448 : typedef const ::clang::CFGBlock NodeType;
449 : typedef ::clang::CFGBlock::const_succ_iterator ChildIteratorType;
450 :
451 : static NodeType* getEntryNode(const clang::CFGBlock* BB)
452 : { return BB; }
453 :
454 0: static inline ChildIteratorType child_begin(NodeType* N)
455 0: { return N->succ_begin(); }
456 :
457 0: static inline ChildIteratorType child_end(NodeType* N)
458 0: { return N->succ_end(); }
459 : };
460 :
461 : template <> struct GraphTraits<Inverse<const ::clang::CFGBlock*> > {
462 : typedef const ::clang::CFGBlock NodeType;
463 : typedef ::clang::CFGBlock::const_pred_iterator ChildIteratorType;
464 :
465 : static NodeType *getEntryNode(Inverse<const ::clang::CFGBlock*> G)
466 : { return G.Graph; }
467 :
468 : static inline ChildIteratorType child_begin(NodeType* N)
469 : { return N->pred_begin(); }
470 :
471 : static inline ChildIteratorType child_end(NodeType* N)
472 : { return N->pred_end(); }
473 : };
474 :
475 : // Traits for: CFG
476 :
477 : template <> struct GraphTraits< ::clang::CFG* >
478 : : public GraphTraits< ::clang::CFGBlock* > {
479 :
480 : typedef ::clang::CFG::iterator nodes_iterator;
481 :
482 : static NodeType *getEntryNode(::clang::CFG* F) { return &F->getEntry(); }
483 : static nodes_iterator nodes_begin(::clang::CFG* F) { return F->begin(); }
484 : static nodes_iterator nodes_end(::clang::CFG* F) { return F->end(); }
485 : };
486 :
487 : template <> struct GraphTraits<const ::clang::CFG* >
488 : : public GraphTraits<const ::clang::CFGBlock* > {
489 :
490 : typedef ::clang::CFG::const_iterator nodes_iterator;
491 :
492 : static NodeType *getEntryNode( const ::clang::CFG* F) {
493 : return &F->getEntry();
494 : }
495 0: static nodes_iterator nodes_begin( const ::clang::CFG* F) {
496 0: return F->begin();
497 : }
498 0: static nodes_iterator nodes_end( const ::clang::CFG* F) {
499 0: return F->end();
500 : }
501 : };
502 :
503 : template <> struct GraphTraits<Inverse<const ::clang::CFG*> >
504 : : public GraphTraits<Inverse<const ::clang::CFGBlock*> > {
505 :
506 : typedef ::clang::CFG::const_iterator nodes_iterator;
507 :
508 : static NodeType *getEntryNode(const ::clang::CFG* F) { return &F->getExit(); }
509 : static nodes_iterator nodes_begin(const ::clang::CFG* F) { return F->begin();}
510 : static nodes_iterator nodes_end(const ::clang::CFG* F) { return F->end(); }
511 : };
512 : } // end llvm namespace
513 : #endif
Generated: 2010-02-10 01:31 by zcov