blob: da06ebd9654ebc18cd4865709617b5775ae29cdf [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//
5// This file was developed by Ted Kremenek and is distributed under
6// the University of Illinois Open Source 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#include "clang/AST/CFG.h"
16#include "clang/AST/Expr.h"
Ted Kremenekc310e932007-08-21 22:06:14 +000017#include "clang/AST/StmtVisitor.h"
Ted Kremenek42a509f2007-08-31 21:30:12 +000018#include "clang/AST/PrettyPrinter.h"
Ted Kremenek0cebe3e2007-08-21 23:26:17 +000019#include "llvm/ADT/DenseMap.h"
Ted Kremenek19bb3562007-08-28 19:26:49 +000020#include "llvm/ADT/SmallPtrSet.h"
Ted Kremenek7dba8602007-08-29 21:56:09 +000021#include "llvm/Support/GraphWriter.h"
22#include "llvm/Config/config.h"
Ted Kremenekfddd5182007-08-21 21:42:03 +000023#include <iostream>
24#include <iomanip>
25#include <algorithm>
Ted Kremenek7dba8602007-08-29 21:56:09 +000026#include <sstream>
27
Ted Kremenekfddd5182007-08-21 21:42:03 +000028using namespace clang;
29
30namespace {
31
Ted Kremenekbefef2f2007-08-23 21:26:19 +000032// SaveAndRestore - A utility class that uses RIIA to save and restore
33// the value of a variable.
34template<typename T>
35struct SaveAndRestore {
36 SaveAndRestore(T& x) : X(x), old_value(x) {}
37 ~SaveAndRestore() { X = old_value; }
Ted Kremenekb6f7b722007-08-30 18:13:31 +000038 T get() { return old_value; }
39
Ted Kremenekbefef2f2007-08-23 21:26:19 +000040 T& X;
41 T old_value;
42};
Ted Kremenekfddd5182007-08-21 21:42:03 +000043
44/// CFGBuilder - This class is implements CFG construction from an AST.
45/// The builder is stateful: an instance of the builder should be used to only
46/// construct a single CFG.
47///
48/// Example usage:
49///
50/// CFGBuilder builder;
51/// CFG* cfg = builder.BuildAST(stmt1);
52///
Ted Kremenekc310e932007-08-21 22:06:14 +000053/// CFG construction is done via a recursive walk of an AST.
54/// We actually parse the AST in reverse order so that the successor
55/// of a basic block is constructed prior to its predecessor. This
56/// allows us to nicely capture implicit fall-throughs without extra
57/// basic blocks.
58///
59class CFGBuilder : public StmtVisitor<CFGBuilder,CFGBlock*> {
Ted Kremenekfddd5182007-08-21 21:42:03 +000060 CFG* cfg;
61 CFGBlock* Block;
Ted Kremenekfddd5182007-08-21 21:42:03 +000062 CFGBlock* Succ;
Ted Kremenekbf15b272007-08-22 21:36:54 +000063 CFGBlock* ContinueTargetBlock;
Ted Kremenek8a294712007-08-22 21:51:58 +000064 CFGBlock* BreakTargetBlock;
Ted Kremenekb5c13b02007-08-23 18:43:24 +000065 CFGBlock* SwitchTerminatedBlock;
Ted Kremenekfddd5182007-08-21 21:42:03 +000066 unsigned NumBlocks;
67
Ted Kremenek19bb3562007-08-28 19:26:49 +000068 // LabelMap records the mapping from Label expressions to their blocks.
Ted Kremenek0cebe3e2007-08-21 23:26:17 +000069 typedef llvm::DenseMap<LabelStmt*,CFGBlock*> LabelMapTy;
70 LabelMapTy LabelMap;
71
Ted Kremenek19bb3562007-08-28 19:26:49 +000072 // A list of blocks that end with a "goto" that must be backpatched to
73 // their resolved targets upon completion of CFG construction.
Ted Kremenek4a2b8a12007-08-22 15:40:58 +000074 typedef std::vector<CFGBlock*> BackpatchBlocksTy;
Ted Kremenek0cebe3e2007-08-21 23:26:17 +000075 BackpatchBlocksTy BackpatchBlocks;
76
Ted Kremenek19bb3562007-08-28 19:26:49 +000077 // A list of labels whose address has been taken (for indirect gotos).
78 typedef llvm::SmallPtrSet<LabelStmt*,5> LabelSetTy;
79 LabelSetTy AddressTakenLabels;
80
Ted Kremenekfddd5182007-08-21 21:42:03 +000081public:
Ted Kremenek026473c2007-08-23 16:51:22 +000082 explicit CFGBuilder() : cfg(NULL), Block(NULL), Succ(NULL),
Ted Kremenek8a294712007-08-22 21:51:58 +000083 ContinueTargetBlock(NULL), BreakTargetBlock(NULL),
Ted Kremenekb5c13b02007-08-23 18:43:24 +000084 SwitchTerminatedBlock(NULL),
Ted Kremenekfddd5182007-08-21 21:42:03 +000085 NumBlocks(0) {
86 // Create an empty CFG.
87 cfg = new CFG();
88 }
89
90 ~CFGBuilder() { delete cfg; }
Ted Kremenekfddd5182007-08-21 21:42:03 +000091
Ted Kremenekd4fdee32007-08-23 21:42:29 +000092 // buildCFG - Used by external clients to construct the CFG.
93 CFG* buildCFG(Stmt* Statement);
Ted Kremenekc310e932007-08-21 22:06:14 +000094
Ted Kremenekd4fdee32007-08-23 21:42:29 +000095 // Visitors to walk an AST and construct the CFG. Called by
96 // buildCFG. Do not call directly!
Ted Kremeneke8ee26b2007-08-22 18:22:34 +000097
Ted Kremenekd4fdee32007-08-23 21:42:29 +000098 CFGBlock* VisitStmt(Stmt* Statement);
99 CFGBlock* VisitNullStmt(NullStmt* Statement);
100 CFGBlock* VisitCompoundStmt(CompoundStmt* C);
101 CFGBlock* VisitIfStmt(IfStmt* I);
102 CFGBlock* VisitReturnStmt(ReturnStmt* R);
103 CFGBlock* VisitLabelStmt(LabelStmt* L);
104 CFGBlock* VisitGotoStmt(GotoStmt* G);
105 CFGBlock* VisitForStmt(ForStmt* F);
106 CFGBlock* VisitWhileStmt(WhileStmt* W);
107 CFGBlock* VisitDoStmt(DoStmt* D);
108 CFGBlock* VisitContinueStmt(ContinueStmt* C);
109 CFGBlock* VisitBreakStmt(BreakStmt* B);
110 CFGBlock* VisitSwitchStmt(SwitchStmt* S);
111 CFGBlock* VisitSwitchCase(SwitchCase* S);
Ted Kremenek19bb3562007-08-28 19:26:49 +0000112 CFGBlock* VisitIndirectGotoStmt(IndirectGotoStmt* I);
Ted Kremenekfddd5182007-08-21 21:42:03 +0000113
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000114private:
115 CFGBlock* createBlock(bool add_successor = true);
Ted Kremenek9da2fb72007-08-27 21:27:44 +0000116 CFGBlock* addStmt(Stmt* S);
117 CFGBlock* WalkAST(Stmt* S, bool AlwaysAddStmt);
118 CFGBlock* WalkAST_VisitChildren(Stmt* S);
Ted Kremenekb49e1aa2007-08-28 18:14:37 +0000119 CFGBlock* WalkAST_VisitVarDecl(VarDecl* D);
Ted Kremenek15c27a82007-08-28 18:30:10 +0000120 CFGBlock* WalkAST_VisitStmtExpr(StmtExpr* S);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000121 void FinishBlock(CFGBlock* B);
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000122
Ted Kremenekfddd5182007-08-21 21:42:03 +0000123};
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000124
125/// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can
126/// represent an arbitrary statement. Examples include a single expression
127/// or a function body (compound statement). The ownership of the returned
128/// CFG is transferred to the caller. If CFG construction fails, this method
129/// returns NULL.
130CFG* CFGBuilder::buildCFG(Stmt* Statement) {
Ted Kremenek19bb3562007-08-28 19:26:49 +0000131 assert (cfg);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000132 if (!Statement) return NULL;
133
134 // Create an empty block that will serve as the exit block for the CFG.
135 // Since this is the first block added to the CFG, it will be implicitly
136 // registered as the exit block.
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000137 Succ = createBlock();
138 assert (Succ == &cfg->getExit());
139 Block = NULL; // the EXIT block is empty. Create all other blocks lazily.
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000140
141 // Visit the statements and create the CFG.
142 if (CFGBlock* B = Visit(Statement)) {
143 // Finalize the last constructed block. This usually involves
144 // reversing the order of the statements in the block.
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000145 if (Block) FinishBlock(B);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000146
147 // Backpatch the gotos whose label -> block mappings we didn't know
148 // when we encountered them.
149 for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(),
150 E = BackpatchBlocks.end(); I != E; ++I ) {
151
152 CFGBlock* B = *I;
153 GotoStmt* G = cast<GotoStmt>(B->getTerminator());
154 LabelMapTy::iterator LI = LabelMap.find(G->getLabel());
155
156 // If there is no target for the goto, then we are looking at an
157 // incomplete AST. Handle this by not registering a successor.
158 if (LI == LabelMap.end()) continue;
159
160 B->addSuccessor(LI->second);
Ted Kremenek19bb3562007-08-28 19:26:49 +0000161 }
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000162
Ted Kremenek19bb3562007-08-28 19:26:49 +0000163 // Add successors to the Indirect Goto Dispatch block (if we have one).
164 if (CFGBlock* B = cfg->getIndirectGotoBlock())
165 for (LabelSetTy::iterator I = AddressTakenLabels.begin(),
166 E = AddressTakenLabels.end(); I != E; ++I ) {
167
168 // Lookup the target block.
169 LabelMapTy::iterator LI = LabelMap.find(*I);
170
171 // If there is no target block that contains label, then we are looking
172 // at an incomplete AST. Handle this by not registering a successor.
173 if (LI == LabelMap.end()) continue;
174
175 B->addSuccessor(LI->second);
176 }
177
178 // Create an empty entry block that has no predecessors.
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000179 if (B->pred_size() > 0) {
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000180 Succ = B;
181 cfg->setEntry(createBlock());
182 }
183 else cfg->setEntry(B);
184
Ted Kremenek19bb3562007-08-28 19:26:49 +0000185 // NULL out cfg so that repeated calls to the builder will fail and that
186 // the ownership of the constructed CFG is passed to the caller.
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000187 CFG* t = cfg;
188 cfg = NULL;
189 return t;
190 }
191 else return NULL;
192}
193
194/// createBlock - Used to lazily create blocks that are connected
195/// to the current (global) succcessor.
196CFGBlock* CFGBuilder::createBlock(bool add_successor) {
197 CFGBlock* B = cfg->createBlock(NumBlocks++);
198 if (add_successor && Succ) B->addSuccessor(Succ);
199 return B;
200}
201
202/// FinishBlock - When the last statement has been added to the block,
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000203/// we must reverse the statements because they have been inserted
204/// in reverse order.
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000205void CFGBuilder::FinishBlock(CFGBlock* B) {
206 assert (B);
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000207 B->reverseStmts();
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000208}
209
Ted Kremenek9da2fb72007-08-27 21:27:44 +0000210/// addStmt - Used to add statements/expressions to the current CFGBlock
211/// "Block". This method calls WalkAST on the passed statement to see if it
212/// contains any short-circuit expressions. If so, it recursively creates
213/// the necessary blocks for such expressions. It returns the "topmost" block
214/// of the created blocks, or the original value of "Block" when this method
215/// was called if no additional blocks are created.
216CFGBlock* CFGBuilder::addStmt(Stmt* S) {
Ted Kremenekaf603f72007-08-30 18:39:40 +0000217 if (!Block) Block = createBlock();
Ted Kremenek9da2fb72007-08-27 21:27:44 +0000218 return WalkAST(S,true);
219}
220
221/// WalkAST - Used by addStmt to walk the subtree of a statement and
Ted Kremenekb49e1aa2007-08-28 18:14:37 +0000222/// add extra blocks for ternary operators, &&, and ||. We also
223/// process "," and DeclStmts (which may contain nested control-flow).
Ted Kremenek9da2fb72007-08-27 21:27:44 +0000224CFGBlock* CFGBuilder::WalkAST(Stmt* S, bool AlwaysAddStmt = false) {
225 switch (S->getStmtClass()) {
226 case Stmt::ConditionalOperatorClass: {
227 ConditionalOperator* C = cast<ConditionalOperator>(S);
228
229 CFGBlock* ConfluenceBlock = (Block) ? Block : createBlock();
230 ConfluenceBlock->appendStmt(C);
231 FinishBlock(ConfluenceBlock);
232
233 Succ = ConfluenceBlock;
234 Block = NULL;
235 CFGBlock* LHSBlock = Visit(C->getLHS());
236
237 Succ = ConfluenceBlock;
238 Block = NULL;
239 CFGBlock* RHSBlock = Visit(C->getRHS());
240
241 Block = createBlock(false);
242 Block->addSuccessor(LHSBlock);
243 Block->addSuccessor(RHSBlock);
244 Block->setTerminator(C);
245 return addStmt(C->getCond());
246 }
Ted Kremenek49a436d2007-08-31 17:03:41 +0000247
248 case Stmt::ChooseExprClass: {
249 ChooseExpr* C = cast<ChooseExpr>(S);
250
251 CFGBlock* ConfluenceBlock = (Block) ? Block : createBlock();
252 ConfluenceBlock->appendStmt(C);
253 FinishBlock(ConfluenceBlock);
254
255 Succ = ConfluenceBlock;
256 Block = NULL;
257 CFGBlock* LHSBlock = Visit(C->getLHS());
258
259 Succ = ConfluenceBlock;
260 Block = NULL;
261 CFGBlock* RHSBlock = Visit(C->getRHS());
262
263 Block = createBlock(false);
264 Block->addSuccessor(LHSBlock);
265 Block->addSuccessor(RHSBlock);
266 Block->setTerminator(C);
267 return addStmt(C->getCond());
268 }
Ted Kremenek7926f7c2007-08-28 16:18:58 +0000269
Ted Kremenekb49e1aa2007-08-28 18:14:37 +0000270 case Stmt::DeclStmtClass:
271 if (VarDecl* V = dyn_cast<VarDecl>(cast<DeclStmt>(S)->getDecl())) {
272 Block->appendStmt(S);
273 return WalkAST_VisitVarDecl(V);
274 }
275 else return Block;
Ted Kremenek15c27a82007-08-28 18:30:10 +0000276
Ted Kremenek19bb3562007-08-28 19:26:49 +0000277 case Stmt::AddrLabelExprClass: {
278 AddrLabelExpr* A = cast<AddrLabelExpr>(S);
279 AddressTakenLabels.insert(A->getLabel());
280
281 if (AlwaysAddStmt) Block->appendStmt(S);
282 return Block;
283 }
284
Ted Kremenek15c27a82007-08-28 18:30:10 +0000285 case Stmt::StmtExprClass:
286 return WalkAST_VisitStmtExpr(cast<StmtExpr>(S));
Ted Kremenekb49e1aa2007-08-28 18:14:37 +0000287
Ted Kremenek0b1d9b72007-08-27 21:54:41 +0000288 case Stmt::BinaryOperatorClass: {
289 BinaryOperator* B = cast<BinaryOperator>(S);
290
291 if (B->isLogicalOp()) { // && or ||
292 CFGBlock* ConfluenceBlock = (Block) ? Block : createBlock();
293 ConfluenceBlock->appendStmt(B);
294 FinishBlock(ConfluenceBlock);
295
296 // create the block evaluating the LHS
297 CFGBlock* LHSBlock = createBlock(false);
298 LHSBlock->addSuccessor(ConfluenceBlock);
299 LHSBlock->setTerminator(B);
300
301 // create the block evaluating the RHS
302 Succ = ConfluenceBlock;
303 Block = NULL;
304 CFGBlock* RHSBlock = Visit(B->getRHS());
305 LHSBlock->addSuccessor(RHSBlock);
306
307 // Generate the blocks for evaluating the LHS.
308 Block = LHSBlock;
309 return addStmt(B->getLHS());
Ted Kremenekb49e1aa2007-08-28 18:14:37 +0000310 }
311 else if (B->getOpcode() == BinaryOperator::Comma) { // ,
312 Block->appendStmt(B);
313 addStmt(B->getRHS());
314 return addStmt(B->getLHS());
Ted Kremenek0b1d9b72007-08-27 21:54:41 +0000315 }
316
317 // Fall through to the default case.
318 }
319
Ted Kremenek9da2fb72007-08-27 21:27:44 +0000320 default:
321 if (AlwaysAddStmt) Block->appendStmt(S);
322 return WalkAST_VisitChildren(S);
323 };
324}
325
Ted Kremenekb49e1aa2007-08-28 18:14:37 +0000326/// WalkAST_VisitVarDecl - Utility method to handle VarDecls contained in
327/// DeclStmts. Because the initialization code for declarations can
328/// contain arbitrary expressions, we must linearize declarations
329/// to handle arbitrary control-flow induced by those expressions.
330CFGBlock* CFGBuilder::WalkAST_VisitVarDecl(VarDecl* V) {
331 // We actually must parse the LAST declaration in a chain of
332 // declarations first, because we are building the CFG in reverse
333 // order.
334 if (Decl* D = V->getNextDeclarator())
335 if (VarDecl* Next = cast<VarDecl>(D))
336 Block = WalkAST_VisitVarDecl(Next);
337
338 if (Expr* E = V->getInit())
339 return addStmt(E);
340
341 assert (Block);
342 return Block;
343}
344
Ted Kremenek9da2fb72007-08-27 21:27:44 +0000345/// WalkAST_VisitChildren - Utility method to call WalkAST on the
346/// children of a Stmt.
Ted Kremenek0b1d9b72007-08-27 21:54:41 +0000347CFGBlock* CFGBuilder::WalkAST_VisitChildren(Stmt* S) {
Ted Kremenek9da2fb72007-08-27 21:27:44 +0000348 CFGBlock* B = Block;
349 for (Stmt::child_iterator I = S->child_begin(), E = S->child_end() ;
350 I != E; ++I)
351 B = WalkAST(*I);
352
353 return B;
354}
355
Ted Kremenek15c27a82007-08-28 18:30:10 +0000356/// WalkAST_VisitStmtExpr - Utility method to handle (nested) statement
357/// expressions (a GCC extension).
358CFGBlock* CFGBuilder::WalkAST_VisitStmtExpr(StmtExpr* S) {
359 Block->appendStmt(S);
360 return VisitCompoundStmt(S->getSubStmt());
361}
362
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000363/// VisitStmt - Handle statements with no branching control flow.
364CFGBlock* CFGBuilder::VisitStmt(Stmt* Statement) {
365 // We cannot assume that we are in the middle of a basic block, since
366 // the CFG might only be constructed for this single statement. If
367 // we have no current basic block, just create one lazily.
368 if (!Block) Block = createBlock();
369
370 // Simply add the statement to the current block. We actually
371 // insert statements in reverse order; this order is reversed later
372 // when processing the containing element in the AST.
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000373 addStmt(Statement);
374
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000375 return Block;
376}
377
378CFGBlock* CFGBuilder::VisitNullStmt(NullStmt* Statement) {
379 return Block;
380}
381
382CFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) {
383 // The value returned from this function is the last created CFGBlock
384 // that represents the "entry" point for the translated AST node.
385 CFGBlock* LastBlock;
386
387 for (CompoundStmt::reverse_body_iterator I = C->body_rbegin(),
388 E = C->body_rend(); I != E; ++I )
389 // Add the statement to the current block.
390 if (!(LastBlock=Visit(*I)))
391 return NULL;
392
393 return LastBlock;
394}
395
396CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) {
397 // We may see an if statement in the middle of a basic block, or
398 // it may be the first statement we are processing. In either case,
399 // we create a new basic block. First, we create the blocks for
400 // the then...else statements, and then we create the block containing
401 // the if statement. If we were in the middle of a block, we
402 // stop processing that block and reverse its statements. That block
403 // is then the implicit successor for the "then" and "else" clauses.
404
405 // The block we were proccessing is now finished. Make it the
406 // successor block.
407 if (Block) {
408 Succ = Block;
409 FinishBlock(Block);
410 }
411
412 // Process the false branch. NULL out Block so that the recursive
413 // call to Visit will create a new basic block.
414 // Null out Block so that all successor
415 CFGBlock* ElseBlock = Succ;
416
417 if (Stmt* Else = I->getElse()) {
418 SaveAndRestore<CFGBlock*> sv(Succ);
419
420 // NULL out Block so that the recursive call to Visit will
421 // create a new basic block.
422 Block = NULL;
Ted Kremenekb6f7b722007-08-30 18:13:31 +0000423 ElseBlock = Visit(Else);
424
425 if (!ElseBlock) // Can occur when the Else body has all NullStmts.
426 ElseBlock = sv.get();
427 else if (Block)
428 FinishBlock(ElseBlock);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000429 }
430
431 // Process the true branch. NULL out Block so that the recursive
432 // call to Visit will create a new basic block.
433 // Null out Block so that all successor
434 CFGBlock* ThenBlock;
435 {
436 Stmt* Then = I->getThen();
437 assert (Then);
438 SaveAndRestore<CFGBlock*> sv(Succ);
439 Block = NULL;
Ted Kremenekb6f7b722007-08-30 18:13:31 +0000440 ThenBlock = Visit(Then);
441
442 if (!ThenBlock) // Can occur when the Then body has all NullStmts.
443 ThenBlock = sv.get();
444 else if (Block)
445 FinishBlock(ThenBlock);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000446 }
447
448 // Now create a new block containing the if statement.
449 Block = createBlock(false);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000450
451 // Set the terminator of the new block to the If statement.
452 Block->setTerminator(I);
453
454 // Now add the successors.
455 Block->addSuccessor(ThenBlock);
456 Block->addSuccessor(ElseBlock);
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000457
458 // Add the condition as the last statement in the new block. This
459 // may create new blocks as the condition may contain control-flow. Any
460 // newly created blocks will be pointed to be "Block".
461 return addStmt(I->getCond());
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000462}
463
464CFGBlock* CFGBuilder::VisitReturnStmt(ReturnStmt* R) {
465 // If we were in the middle of a block we stop processing that block
466 // and reverse its statements.
467 //
468 // NOTE: If a "return" appears in the middle of a block, this means
469 // that the code afterwards is DEAD (unreachable). We still
470 // keep a basic block for that code; a simple "mark-and-sweep"
471 // from the entry block will be able to report such dead
472 // blocks.
473 if (Block) FinishBlock(Block);
474
475 // Create the new block.
476 Block = createBlock(false);
477
478 // The Exit block is the only successor.
479 Block->addSuccessor(&cfg->getExit());
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000480
481 // Add the return statement to the block. This may create new blocks
482 // if R contains control-flow (short-circuit operations).
483 return addStmt(R);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000484}
485
486CFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt* L) {
487 // Get the block of the labeled statement. Add it to our map.
488 CFGBlock* LabelBlock = Visit(L->getSubStmt());
Ted Kremenek16e4dc82007-08-30 18:20:57 +0000489
490 if (!LabelBlock) // This can happen when the body is empty, i.e.
491 LabelBlock=createBlock(); // scopes that only contains NullStmts.
492
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000493 assert (LabelMap.find(L) == LabelMap.end() && "label already in map");
494 LabelMap[ L ] = LabelBlock;
495
496 // Labels partition blocks, so this is the end of the basic block
Ted Kremenek9cffe732007-08-29 23:20:49 +0000497 // we were processing (L is the block's label). Because this is
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000498 // label (and we have already processed the substatement) there is no
499 // extra control-flow to worry about.
Ted Kremenek9cffe732007-08-29 23:20:49 +0000500 LabelBlock->setLabel(L);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000501 FinishBlock(LabelBlock);
502
503 // We set Block to NULL to allow lazy creation of a new block
504 // (if necessary);
505 Block = NULL;
506
507 // This block is now the implicit successor of other blocks.
508 Succ = LabelBlock;
509
510 return LabelBlock;
511}
512
513CFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) {
514 // Goto is a control-flow statement. Thus we stop processing the
515 // current block and create a new one.
516 if (Block) FinishBlock(Block);
517 Block = createBlock(false);
518 Block->setTerminator(G);
519
520 // If we already know the mapping to the label block add the
521 // successor now.
522 LabelMapTy::iterator I = LabelMap.find(G->getLabel());
523
524 if (I == LabelMap.end())
525 // We will need to backpatch this block later.
526 BackpatchBlocks.push_back(Block);
527 else
528 Block->addSuccessor(I->second);
529
530 return Block;
531}
532
533CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) {
534 // "for" is a control-flow statement. Thus we stop processing the
535 // current block.
536
537 CFGBlock* LoopSuccessor = NULL;
538
539 if (Block) {
540 FinishBlock(Block);
541 LoopSuccessor = Block;
542 }
543 else LoopSuccessor = Succ;
544
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000545 // Because of short-circuit evaluation, the condition of the loop
546 // can span multiple basic blocks. Thus we need the "Entry" and "Exit"
547 // blocks that evaluate the condition.
548 CFGBlock* ExitConditionBlock = createBlock(false);
549 CFGBlock* EntryConditionBlock = ExitConditionBlock;
550
551 // Set the terminator for the "exit" condition block.
552 ExitConditionBlock->setTerminator(F);
553
554 // Now add the actual condition to the condition block. Because the
555 // condition itself may contain control-flow, new blocks may be created.
556 if (Stmt* C = F->getCond()) {
557 Block = ExitConditionBlock;
558 EntryConditionBlock = addStmt(C);
559 if (Block) FinishBlock(EntryConditionBlock);
560 }
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000561
562 // The condition block is the implicit successor for the loop body as
563 // well as any code above the loop.
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000564 Succ = EntryConditionBlock;
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000565
566 // Now create the loop body.
567 {
568 assert (F->getBody());
569
570 // Save the current values for Block, Succ, and continue and break targets
571 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ),
572 save_continue(ContinueTargetBlock),
573 save_break(BreakTargetBlock);
574
575 // All continues within this loop should go to the condition block
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000576 ContinueTargetBlock = EntryConditionBlock;
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000577
578 // All breaks should go to the code following the loop.
579 BreakTargetBlock = LoopSuccessor;
580
Ted Kremenekaf603f72007-08-30 18:39:40 +0000581 // Create a new block to contain the (bottom) of the loop body.
582 Block = NULL;
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000583
584 // If we have increment code, insert it at the end of the body block.
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000585 if (Stmt* I = F->getInc()) Block = addStmt(I);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000586
587 // Now populate the body block, and in the process create new blocks
588 // as we walk the body of the loop.
589 CFGBlock* BodyBlock = Visit(F->getBody());
Ted Kremenekaf603f72007-08-30 18:39:40 +0000590
591 if (!BodyBlock)
592 BodyBlock = ExitConditionBlock; // can happen for "for (...;...; ) ;"
593 else if (Block)
594 FinishBlock(BodyBlock);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000595
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000596 // This new body block is a successor to our "exit" condition block.
597 ExitConditionBlock->addSuccessor(BodyBlock);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000598 }
599
600 // Link up the condition block with the code that follows the loop.
601 // (the false branch).
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000602 ExitConditionBlock->addSuccessor(LoopSuccessor);
603
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000604 // If the loop contains initialization, create a new block for those
605 // statements. This block can also contain statements that precede
606 // the loop.
607 if (Stmt* I = F->getInit()) {
608 Block = createBlock();
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000609 return addStmt(I);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000610 }
611 else {
612 // There is no loop initialization. We are thus basically a while
613 // loop. NULL out Block to force lazy block construction.
614 Block = NULL;
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000615 return EntryConditionBlock;
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000616 }
617}
618
619CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) {
620 // "while" is a control-flow statement. Thus we stop processing the
621 // current block.
622
623 CFGBlock* LoopSuccessor = NULL;
624
625 if (Block) {
626 FinishBlock(Block);
627 LoopSuccessor = Block;
628 }
629 else LoopSuccessor = Succ;
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000630
631 // Because of short-circuit evaluation, the condition of the loop
632 // can span multiple basic blocks. Thus we need the "Entry" and "Exit"
633 // blocks that evaluate the condition.
634 CFGBlock* ExitConditionBlock = createBlock(false);
635 CFGBlock* EntryConditionBlock = ExitConditionBlock;
636
637 // Set the terminator for the "exit" condition block.
638 ExitConditionBlock->setTerminator(W);
639
640 // Now add the actual condition to the condition block. Because the
641 // condition itself may contain control-flow, new blocks may be created.
642 // Thus we update "Succ" after adding the condition.
643 if (Stmt* C = W->getCond()) {
644 Block = ExitConditionBlock;
645 EntryConditionBlock = addStmt(C);
646 if (Block) FinishBlock(EntryConditionBlock);
647 }
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000648
649 // The condition block is the implicit successor for the loop body as
650 // well as any code above the loop.
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000651 Succ = EntryConditionBlock;
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000652
653 // Process the loop body.
654 {
655 assert (W->getBody());
656
657 // Save the current values for Block, Succ, and continue and break targets
658 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ),
659 save_continue(ContinueTargetBlock),
660 save_break(BreakTargetBlock);
661
662 // All continues within this loop should go to the condition block
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000663 ContinueTargetBlock = EntryConditionBlock;
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000664
665 // All breaks should go to the code following the loop.
666 BreakTargetBlock = LoopSuccessor;
667
668 // NULL out Block to force lazy instantiation of blocks for the body.
669 Block = NULL;
670
671 // Create the body. The returned block is the entry to the loop body.
672 CFGBlock* BodyBlock = Visit(W->getBody());
Ted Kremenekaf603f72007-08-30 18:39:40 +0000673
674 if (!BodyBlock)
675 BodyBlock = ExitConditionBlock; // can happen for "while(...) ;"
676 else if (Block)
677 FinishBlock(BodyBlock);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000678
679 // Add the loop body entry as a successor to the condition.
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000680 ExitConditionBlock->addSuccessor(BodyBlock);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000681 }
682
683 // Link up the condition block with the code that follows the loop.
684 // (the false branch).
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000685 ExitConditionBlock->addSuccessor(LoopSuccessor);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000686
687 // There can be no more statements in the condition block
688 // since we loop back to this block. NULL out Block to force
689 // lazy creation of another block.
690 Block = NULL;
691
692 // Return the condition block, which is the dominating block for the loop.
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000693 return EntryConditionBlock;
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000694}
695
696CFGBlock* CFGBuilder::VisitDoStmt(DoStmt* D) {
697 // "do...while" is a control-flow statement. Thus we stop processing the
698 // current block.
699
700 CFGBlock* LoopSuccessor = NULL;
701
702 if (Block) {
703 FinishBlock(Block);
704 LoopSuccessor = Block;
705 }
706 else LoopSuccessor = Succ;
707
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000708 // Because of short-circuit evaluation, the condition of the loop
709 // can span multiple basic blocks. Thus we need the "Entry" and "Exit"
710 // blocks that evaluate the condition.
711 CFGBlock* ExitConditionBlock = createBlock(false);
712 CFGBlock* EntryConditionBlock = ExitConditionBlock;
713
714 // Set the terminator for the "exit" condition block.
715 ExitConditionBlock->setTerminator(D);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000716
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000717 // Now add the actual condition to the condition block. Because the
718 // condition itself may contain control-flow, new blocks may be created.
719 if (Stmt* C = D->getCond()) {
720 Block = ExitConditionBlock;
721 EntryConditionBlock = addStmt(C);
722 if (Block) FinishBlock(EntryConditionBlock);
723 }
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000724
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000725 // The condition block is the implicit successor for the loop body as
726 // well as any code above the loop.
727 Succ = EntryConditionBlock;
728
729
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000730 // Process the loop body.
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000731 CFGBlock* BodyBlock = NULL;
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000732 {
733 assert (D->getBody());
734
735 // Save the current values for Block, Succ, and continue and break targets
736 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ),
737 save_continue(ContinueTargetBlock),
738 save_break(BreakTargetBlock);
739
740 // All continues within this loop should go to the condition block
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000741 ContinueTargetBlock = EntryConditionBlock;
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000742
743 // All breaks should go to the code following the loop.
744 BreakTargetBlock = LoopSuccessor;
745
746 // NULL out Block to force lazy instantiation of blocks for the body.
747 Block = NULL;
748
749 // Create the body. The returned block is the entry to the loop body.
750 BodyBlock = Visit(D->getBody());
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000751
Ted Kremenekaf603f72007-08-30 18:39:40 +0000752 if (!BodyBlock)
753 BodyBlock = ExitConditionBlock; // can happen for "do ; while(...)"
754 else if (Block)
755 FinishBlock(BodyBlock);
756
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000757 // Add the loop body entry as a successor to the condition.
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000758 ExitConditionBlock->addSuccessor(BodyBlock);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000759 }
760
761 // Link up the condition block with the code that follows the loop.
762 // (the false branch).
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000763 ExitConditionBlock->addSuccessor(LoopSuccessor);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000764
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000765 // There can be no more statements in the body block(s)
766 // since we loop back to the body. NULL out Block to force
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000767 // lazy creation of another block.
768 Block = NULL;
769
770 // Return the loop body, which is the dominating block for the loop.
771 return BodyBlock;
772}
773
774CFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) {
775 // "continue" is a control-flow statement. Thus we stop processing the
776 // current block.
777 if (Block) FinishBlock(Block);
778
779 // Now create a new block that ends with the continue statement.
780 Block = createBlock(false);
781 Block->setTerminator(C);
782
783 // If there is no target for the continue, then we are looking at an
784 // incomplete AST. Handle this by not registering a successor.
785 if (ContinueTargetBlock) Block->addSuccessor(ContinueTargetBlock);
786
787 return Block;
788}
789
790CFGBlock* CFGBuilder::VisitBreakStmt(BreakStmt* B) {
791 // "break" is a control-flow statement. Thus we stop processing the
792 // current block.
793 if (Block) FinishBlock(Block);
794
795 // Now create a new block that ends with the continue statement.
796 Block = createBlock(false);
797 Block->setTerminator(B);
798
799 // If there is no target for the break, then we are looking at an
800 // incomplete AST. Handle this by not registering a successor.
801 if (BreakTargetBlock) Block->addSuccessor(BreakTargetBlock);
802
803 return Block;
804}
805
806CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* S) {
807 // "switch" is a control-flow statement. Thus we stop processing the
808 // current block.
809 CFGBlock* SwitchSuccessor = NULL;
810
811 if (Block) {
812 FinishBlock(Block);
813 SwitchSuccessor = Block;
814 }
815 else SwitchSuccessor = Succ;
816
817 // Save the current "switch" context.
818 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock),
819 save_break(BreakTargetBlock);
820
821 // Create a new block that will contain the switch statement.
822 SwitchTerminatedBlock = createBlock(false);
823
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000824 // Now process the switch body. The code after the switch is the implicit
825 // successor.
826 Succ = SwitchSuccessor;
827 BreakTargetBlock = SwitchSuccessor;
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000828
829 // When visiting the body, the case statements should automatically get
830 // linked up to the switch. We also don't keep a pointer to the body,
831 // since all control-flow from the switch goes to case/default statements.
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000832 assert (S->getBody() && "switch must contain a non-NULL body");
833 Block = NULL;
834 CFGBlock *BodyBlock = Visit(S->getBody());
835 if (Block) FinishBlock(BodyBlock);
836
837 // Add the terminator and condition in the switch block.
838 SwitchTerminatedBlock->setTerminator(S);
839 assert (S->getCond() && "switch condition must be non-NULL");
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000840 Block = SwitchTerminatedBlock;
Ted Kremenek49af7cb2007-08-27 19:46:09 +0000841 return addStmt(S->getCond());
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000842}
843
844CFGBlock* CFGBuilder::VisitSwitchCase(SwitchCase* S) {
845 // A SwitchCase is either a "default" or "case" statement. We handle
846 // both in the same way. They are essentially labels, so they are the
847 // first statement in a block.
Ted Kremenek29ccaa12007-08-30 18:48:11 +0000848
849 if (S->getSubStmt()) Visit(S->getSubStmt());
850 CFGBlock* CaseBlock = Block;
851 if (!CaseBlock) CaseBlock = createBlock();
852
Ted Kremenek9cffe732007-08-29 23:20:49 +0000853 // Cases/Default statements partition block, so this is the top of
854 // the basic block we were processing (the case/default is the label).
855 CaseBlock->setLabel(S);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000856 FinishBlock(CaseBlock);
857
858 // Add this block to the list of successors for the block with the
859 // switch statement.
860 if (SwitchTerminatedBlock) SwitchTerminatedBlock->addSuccessor(CaseBlock);
861
862 // We set Block to NULL to allow lazy creation of a new block (if necessary)
863 Block = NULL;
864
865 // This block is now the implicit successor of other blocks.
866 Succ = CaseBlock;
867
868 return CaseBlock;
869}
870
Ted Kremenek19bb3562007-08-28 19:26:49 +0000871CFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) {
872 // Lazily create the indirect-goto dispatch block if there isn't one
873 // already.
874 CFGBlock* IBlock = cfg->getIndirectGotoBlock();
875
876 if (!IBlock) {
877 IBlock = createBlock(false);
878 cfg->setIndirectGotoBlock(IBlock);
879 }
880
881 // IndirectGoto is a control-flow statement. Thus we stop processing the
882 // current block and create a new one.
883 if (Block) FinishBlock(Block);
884 Block = createBlock(false);
885 Block->setTerminator(I);
886 Block->addSuccessor(IBlock);
887 return addStmt(I->getTarget());
888}
889
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000890
Ted Kremenekbefef2f2007-08-23 21:26:19 +0000891} // end anonymous namespace
Ted Kremenek026473c2007-08-23 16:51:22 +0000892
893/// createBlock - Constructs and adds a new CFGBlock to the CFG. The
894/// block has no successors or predecessors. If this is the first block
895/// created in the CFG, it is automatically set to be the Entry and Exit
896/// of the CFG.
897CFGBlock* CFG::createBlock(unsigned blockID) {
898 bool first_block = begin() == end();
899
900 // Create the block.
901 Blocks.push_front(CFGBlock(blockID));
902
903 // If this is the first block, set it as the Entry and Exit.
904 if (first_block) Entry = Exit = &front();
905
906 // Return the block.
907 return &front();
Ted Kremenekfddd5182007-08-21 21:42:03 +0000908}
909
Ted Kremenek026473c2007-08-23 16:51:22 +0000910/// buildCFG - Constructs a CFG from an AST. Ownership of the returned
911/// CFG is returned to the caller.
912CFG* CFG::buildCFG(Stmt* Statement) {
913 CFGBuilder Builder;
914 return Builder.buildCFG(Statement);
915}
916
917/// reverseStmts - Reverses the orders of statements within a CFGBlock.
Ted Kremenekfddd5182007-08-21 21:42:03 +0000918void CFGBlock::reverseStmts() { std::reverse(Stmts.begin(),Stmts.end()); }
919
Ted Kremenek7dba8602007-08-29 21:56:09 +0000920
921//===----------------------------------------------------------------------===//
922// CFG pretty printing
923//===----------------------------------------------------------------------===//
924
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000925namespace {
926
Ted Kremenek1c29bba2007-08-31 22:26:13 +0000927class StmtPrinterHelper : public PrinterHelper {
928
Ted Kremenek42a509f2007-08-31 21:30:12 +0000929 typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy;
930 StmtMapTy StmtMap;
931 signed CurrentBlock;
932 unsigned CurrentStmt;
Ted Kremenek1c29bba2007-08-31 22:26:13 +0000933
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000934public:
Ted Kremenek1c29bba2007-08-31 22:26:13 +0000935
Ted Kremenek42a509f2007-08-31 21:30:12 +0000936 StmtPrinterHelper(const CFG* cfg) : CurrentBlock(0), CurrentStmt(0) {
937 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) {
938 unsigned j = 1;
939 for (CFGBlock::const_iterator BI = I->begin(), BEnd = I->end() ;
940 BI != BEnd; ++BI, ++j )
941 StmtMap[*BI] = std::make_pair(I->getBlockID(),j);
942 }
943 }
944
945 virtual ~StmtPrinterHelper() {}
946
947 void setBlockID(signed i) { CurrentBlock = i; }
948 void setStmtID(unsigned i) { CurrentStmt = i; }
949
Ted Kremenek1c29bba2007-08-31 22:26:13 +0000950 virtual bool handledStmt(Stmt* S, std::ostream& OS) {
951
952 StmtMapTy::iterator I = StmtMap.find(S);
Ted Kremenek42a509f2007-08-31 21:30:12 +0000953
954 if (I == StmtMap.end())
955 return false;
956
957 if (CurrentBlock >= 0 && I->second.first == (unsigned) CurrentBlock
958 && I->second.second == CurrentStmt)
959 return false;
960
Ted Kremenek1c29bba2007-08-31 22:26:13 +0000961 OS << "[B" << I->second.first << "." << I->second.second << "]";
962 return true;
Ted Kremenek42a509f2007-08-31 21:30:12 +0000963 }
964};
965
966class CFGBlockTerminatorPrint : public StmtVisitor<CFGBlockTerminatorPrint,
Ted Kremenek805e9a82007-08-31 21:49:40 +0000967 void >
968{
Ted Kremenek42a509f2007-08-31 21:30:12 +0000969 std::ostream& OS;
970 StmtPrinterHelper* Helper;
971public:
972 CFGBlockTerminatorPrint(std::ostream& os, StmtPrinterHelper* helper)
973 : OS(os), Helper(helper) {}
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000974
975 void VisitIfStmt(IfStmt* I) {
976 OS << "if ";
Ted Kremenek42a509f2007-08-31 21:30:12 +0000977 I->getCond()->printPretty(OS,Helper);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000978 OS << "\n";
979 }
980
981 // Default case.
Ted Kremenek805e9a82007-08-31 21:49:40 +0000982 void VisitStmt(Stmt* S) { S->printPretty(OS); }
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000983
984 void VisitForStmt(ForStmt* F) {
985 OS << "for (" ;
Ted Kremenek535bb202007-08-30 21:28:02 +0000986 if (F->getInit()) OS << "...";
987 OS << "; ";
Ted Kremenek42a509f2007-08-31 21:30:12 +0000988 if (Stmt* C = F->getCond()) C->printPretty(OS,Helper);
Ted Kremenek535bb202007-08-30 21:28:02 +0000989 OS << "; ";
990 if (F->getInc()) OS << "...";
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000991 OS << ")\n";
992 }
993
994 void VisitWhileStmt(WhileStmt* W) {
995 OS << "while " ;
Ted Kremenek42a509f2007-08-31 21:30:12 +0000996 if (Stmt* C = W->getCond()) C->printPretty(OS,Helper);
Ted Kremenekd4fdee32007-08-23 21:42:29 +0000997 OS << "\n";
998 }
999
1000 void VisitDoStmt(DoStmt* D) {
1001 OS << "do ... while ";
Ted Kremenek42a509f2007-08-31 21:30:12 +00001002 if (Stmt* C = D->getCond()) C->printPretty(OS,Helper);
Ted Kremenek9da2fb72007-08-27 21:27:44 +00001003 OS << '\n';
1004 }
Ted Kremenek42a509f2007-08-31 21:30:12 +00001005
Ted Kremenek9da2fb72007-08-27 21:27:44 +00001006 void VisitSwitchStmt(SwitchStmt* S) {
1007 OS << "switch ";
Ted Kremenek42a509f2007-08-31 21:30:12 +00001008 S->getCond()->printPretty(OS,Helper);
Ted Kremenek9da2fb72007-08-27 21:27:44 +00001009 OS << '\n';
1010 }
1011
Ted Kremenek805e9a82007-08-31 21:49:40 +00001012 void VisitConditionalOperator(ConditionalOperator* C) {
1013 C->getCond()->printPretty(OS,Helper);
1014 OS << " ? ... : ...\n";
1015 }
1016
Ted Kremenek1c29bba2007-08-31 22:26:13 +00001017 void VisitIndirectGotoStmt(IndirectGotoStmt* I) {
1018 OS << "goto *";
1019 I->getTarget()->printPretty(OS,Helper);
1020 OS << '\n';
1021 }
1022
Ted Kremenek805e9a82007-08-31 21:49:40 +00001023 void VisitBinaryOperator(BinaryOperator* B) {
1024 if (!B->isLogicalOp()) {
1025 VisitExpr(B);
1026 return;
1027 }
1028
1029 B->getLHS()->printPretty(OS,Helper);
1030
1031 switch (B->getOpcode()) {
1032 case BinaryOperator::LOr:
1033 OS << " || ...\n";
1034 return;
1035 case BinaryOperator::LAnd:
1036 OS << " && ...\n";
1037 return;
1038 default:
1039 assert(false && "Invalid logical operator.");
1040 }
1041 }
1042
Ted Kremenek0b1d9b72007-08-27 21:54:41 +00001043 void VisitExpr(Expr* E) {
Ted Kremenek42a509f2007-08-31 21:30:12 +00001044 E->printPretty(OS,Helper);
Ted Kremenek9da2fb72007-08-27 21:27:44 +00001045 OS << '\n';
Ted Kremenek0b1d9b72007-08-27 21:54:41 +00001046 }
Ted Kremenekd4fdee32007-08-23 21:42:29 +00001047};
Ted Kremenek42a509f2007-08-31 21:30:12 +00001048
1049
Ted Kremenek1c29bba2007-08-31 22:26:13 +00001050void print_stmt(std::ostream&OS, StmtPrinterHelper* Helper, Stmt* S) {
1051 if (Helper) {
1052 // special printing for statement-expressions.
1053 if (StmtExpr* SE = dyn_cast<StmtExpr>(S)) {
1054 CompoundStmt* Sub = SE->getSubStmt();
1055
1056 if (Sub->child_begin() != Sub->child_end()) {
1057 OS << "{ ... ; ";
1058 Helper->handledStmt(*SE->getSubStmt()->child_rbegin(),OS);
1059 OS << " }\n";
1060 return;
1061 }
1062 }
1063
1064 // special printing for comma expressions.
1065 if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {
1066 if (B->getOpcode() == BinaryOperator::Comma) {
1067 OS << "... , ";
1068 Helper->handledStmt(B->getRHS(),OS);
1069 OS << '\n';
1070 return;
1071 }
1072 }
1073 }
1074
1075 S->printPretty(OS, Helper);
1076
1077 // Expressions need a newline.
1078 if (isa<Expr>(S)) OS << '\n';
1079}
1080
Ted Kremenek42a509f2007-08-31 21:30:12 +00001081void print_block(std::ostream& OS, const CFG* cfg, const CFGBlock& B,
1082 StmtPrinterHelper* Helper, bool print_edges) {
1083
1084 if (Helper) Helper->setBlockID(B.getBlockID());
1085
Ted Kremenek7dba8602007-08-29 21:56:09 +00001086 // Print the header.
Ted Kremenek42a509f2007-08-31 21:30:12 +00001087 OS << "\n [ B" << B.getBlockID();
1088
1089 if (&B == &cfg->getEntry())
1090 OS << " (ENTRY) ]\n";
1091 else if (&B == &cfg->getExit())
1092 OS << " (EXIT) ]\n";
1093 else if (&B == cfg->getIndirectGotoBlock())
Ted Kremenek7dba8602007-08-29 21:56:09 +00001094 OS << " (INDIRECT GOTO DISPATCH) ]\n";
Ted Kremenek42a509f2007-08-31 21:30:12 +00001095 else
1096 OS << " ]\n";
1097
Ted Kremenek9cffe732007-08-29 23:20:49 +00001098 // Print the label of this block.
Ted Kremenek42a509f2007-08-31 21:30:12 +00001099 if (Stmt* S = const_cast<Stmt*>(B.getLabel())) {
1100
1101 if (print_edges)
1102 OS << " ";
1103
Ted Kremenek9cffe732007-08-29 23:20:49 +00001104 if (LabelStmt* L = dyn_cast<LabelStmt>(S))
1105 OS << L->getName();
1106 else if (CaseStmt* C = dyn_cast<CaseStmt>(S)) {
1107 OS << "case ";
1108 C->getLHS()->printPretty(OS);
1109 if (C->getRHS()) {
1110 OS << " ... ";
1111 C->getRHS()->printPretty(OS);
1112 }
Ted Kremenek42a509f2007-08-31 21:30:12 +00001113 }
1114 else if (DefaultStmt* D = dyn_cast<DefaultStmt>(D))
Ted Kremenek9cffe732007-08-29 23:20:49 +00001115 OS << "default";
Ted Kremenek42a509f2007-08-31 21:30:12 +00001116 else
1117 assert(false && "Invalid label statement in CFGBlock.");
1118
Ted Kremenek9cffe732007-08-29 23:20:49 +00001119 OS << ":\n";
1120 }
Ted Kremenek42a509f2007-08-31 21:30:12 +00001121
Ted Kremenekfddd5182007-08-21 21:42:03 +00001122 // Iterate through the statements in the block and print them.
Ted Kremenekfddd5182007-08-21 21:42:03 +00001123 unsigned j = 1;
Ted Kremenek42a509f2007-08-31 21:30:12 +00001124
1125 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ;
1126 I != E ; ++I, ++j ) {
1127
Ted Kremenek9cffe732007-08-29 23:20:49 +00001128 // Print the statement # in the basic block and the statement itself.
Ted Kremenek42a509f2007-08-31 21:30:12 +00001129 if (print_edges)
1130 OS << " ";
1131
1132 OS << std::setw(3) << j << ": ";
1133
1134 if (Helper)
1135 Helper->setStmtID(j);
Ted Kremenek1c29bba2007-08-31 22:26:13 +00001136
1137 print_stmt(OS,Helper,*I);
Ted Kremenekfddd5182007-08-21 21:42:03 +00001138 }
Ted Kremenek42a509f2007-08-31 21:30:12 +00001139
Ted Kremenek9cffe732007-08-29 23:20:49 +00001140 // Print the terminator of this block.
Ted Kremenek42a509f2007-08-31 21:30:12 +00001141 if (B.getTerminator()) {
1142 if (print_edges)
1143 OS << " ";
1144
Ted Kremenek9cffe732007-08-29 23:20:49 +00001145 OS << " T: ";
Ted Kremenek42a509f2007-08-31 21:30:12 +00001146
1147 if (Helper) Helper->setBlockID(-1);
1148
1149 CFGBlockTerminatorPrint TPrinter(OS,Helper);
1150 TPrinter.Visit(const_cast<Stmt*>(B.getTerminator()));
Ted Kremenekfddd5182007-08-21 21:42:03 +00001151 }
Ted Kremenek42a509f2007-08-31 21:30:12 +00001152
Ted Kremenek9cffe732007-08-29 23:20:49 +00001153 if (print_edges) {
1154 // Print the predecessors of this block.
Ted Kremenek42a509f2007-08-31 21:30:12 +00001155 OS << " Predecessors (" << B.pred_size() << "):";
Ted Kremenek9cffe732007-08-29 23:20:49 +00001156 unsigned i = 0;
Ted Kremenek9cffe732007-08-29 23:20:49 +00001157
Ted Kremenek42a509f2007-08-31 21:30:12 +00001158 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end();
1159 I != E; ++I, ++i) {
1160
1161 if (i == 8 || (i-8) == 0)
1162 OS << "\n ";
1163
Ted Kremenek9cffe732007-08-29 23:20:49 +00001164 OS << " B" << (*I)->getBlockID();
1165 }
Ted Kremenek42a509f2007-08-31 21:30:12 +00001166
1167 OS << '\n';
1168
1169 // Print the successors of this block.
1170 OS << " Successors (" << B.succ_size() << "):";
1171 i = 0;
1172
1173 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end();
1174 I != E; ++I, ++i) {
1175
1176 if (i == 8 || (i-8) % 10 == 0)
1177 OS << "\n ";
1178
1179 OS << " B" << (*I)->getBlockID();
1180 }
1181
Ted Kremenek9cffe732007-08-29 23:20:49 +00001182 OS << '\n';
Ted Kremenekfddd5182007-08-21 21:42:03 +00001183 }
Ted Kremenek42a509f2007-08-31 21:30:12 +00001184}
1185
1186} // end anonymous namespace
1187
1188/// dump - A simple pretty printer of a CFG that outputs to stderr.
1189void CFG::dump() const { print(std::cerr); }
1190
1191/// print - A simple pretty printer of a CFG that outputs to an ostream.
1192void CFG::print(std::ostream& OS) const {
1193
1194 StmtPrinterHelper Helper(this);
1195
1196 // Print the entry block.
1197 print_block(OS, this, getEntry(), &Helper, true);
1198
1199 // Iterate through the CFGBlocks and print them one by one.
1200 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) {
1201 // Skip the entry block, because we already printed it.
1202 if (&(*I) == &getEntry() || &(*I) == &getExit())
1203 continue;
1204
1205 print_block(OS, this, *I, &Helper, true);
1206 }
1207
1208 // Print the exit block.
1209 print_block(OS, this, getExit(), &Helper, true);
1210}
1211
1212/// dump - A simply pretty printer of a CFGBlock that outputs to stderr.
1213void CFGBlock::dump(const CFG* cfg) const { print(std::cerr, cfg); }
1214
1215/// print - A simple pretty printer of a CFGBlock that outputs to an ostream.
1216/// Generally this will only be called from CFG::print.
1217void CFGBlock::print(std::ostream& OS, const CFG* cfg) const {
1218 StmtPrinterHelper Helper(cfg);
1219 print_block(OS, cfg, *this, &Helper, true);
Ted Kremenek026473c2007-08-23 16:51:22 +00001220}
Ted Kremenek7dba8602007-08-29 21:56:09 +00001221
1222//===----------------------------------------------------------------------===//
1223// CFG Graphviz Visualization
1224//===----------------------------------------------------------------------===//
1225
Ted Kremenek42a509f2007-08-31 21:30:12 +00001226
1227#ifndef NDEBUG
1228namespace {
1229 StmtPrinterHelper* GraphHelper;
1230}
1231#endif
1232
1233void CFG::viewCFG() const {
1234#ifndef NDEBUG
1235 StmtPrinterHelper H(this);
1236 GraphHelper = &H;
1237 llvm::ViewGraph(this,"CFG");
1238 GraphHelper = NULL;
1239#else
1240 std::cerr << "CFG::viewCFG is only available in debug builds on "
1241 << "systems with Graphviz or gv!" << std::endl;
1242#endif
1243}
1244
Ted Kremenek7dba8602007-08-29 21:56:09 +00001245namespace llvm {
1246template<>
1247struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits {
1248 static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph) {
1249
1250 std::ostringstream Out;
Ted Kremenek42a509f2007-08-31 21:30:12 +00001251 print_block(Out,Graph, *Node, GraphHelper, false);
Ted Kremenek7dba8602007-08-29 21:56:09 +00001252 std::string OutStr = Out.str();
1253
1254 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin());
1255
1256 // Process string output to make it nicer...
1257 for (unsigned i = 0; i != OutStr.length(); ++i)
1258 if (OutStr[i] == '\n') { // Left justify
1259 OutStr[i] = '\\';
1260 OutStr.insert(OutStr.begin()+i+1, 'l');
1261 }
1262
1263 return OutStr;
1264 }
1265};
1266} // end namespace llvm