blob: 27bf16a4d1d53fc4b05c9448713ccff276dcf66e [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 Kremenek0cebe3e2007-08-21 23:26:17 +000018#include "llvm/ADT/DenseMap.h"
Ted Kremenekfddd5182007-08-21 21:42:03 +000019#include <iostream>
20#include <iomanip>
21#include <algorithm>
22using namespace clang;
23
24namespace {
25
26 // SaveAndRestore - A utility class that uses RIIA to save and restore
27 // the value of a variable.
28 template<typename T>
29 struct SaveAndRestore {
30 SaveAndRestore(T& x) : X(x), old_value(x) {}
31 ~SaveAndRestore() { X = old_value; }
32
33 T& X;
34 T old_value;
35 };
36}
37
38/// CFGBuilder - This class is implements CFG construction from an AST.
39/// The builder is stateful: an instance of the builder should be used to only
40/// construct a single CFG.
41///
42/// Example usage:
43///
44/// CFGBuilder builder;
45/// CFG* cfg = builder.BuildAST(stmt1);
46///
Ted Kremenekc310e932007-08-21 22:06:14 +000047/// CFG construction is done via a recursive walk of an AST.
48/// We actually parse the AST in reverse order so that the successor
49/// of a basic block is constructed prior to its predecessor. This
50/// allows us to nicely capture implicit fall-throughs without extra
51/// basic blocks.
52///
53class CFGBuilder : public StmtVisitor<CFGBuilder,CFGBlock*> {
Ted Kremenekfddd5182007-08-21 21:42:03 +000054 CFG* cfg;
55 CFGBlock* Block;
56 CFGBlock* Exit;
57 CFGBlock* Succ;
58 unsigned NumBlocks;
59
Ted Kremenek0cebe3e2007-08-21 23:26:17 +000060 typedef llvm::DenseMap<LabelStmt*,CFGBlock*> LabelMapTy;
61 LabelMapTy LabelMap;
62
Ted Kremenek4a2b8a12007-08-22 15:40:58 +000063 typedef std::vector<CFGBlock*> BackpatchBlocksTy;
Ted Kremenek0cebe3e2007-08-21 23:26:17 +000064 BackpatchBlocksTy BackpatchBlocks;
65
Ted Kremenekfddd5182007-08-21 21:42:03 +000066public:
67 explicit CFGBuilder() : cfg(NULL), Block(NULL), Exit(NULL), Succ(NULL),
68 NumBlocks(0) {
69 // Create an empty CFG.
70 cfg = new CFG();
71 }
72
73 ~CFGBuilder() { delete cfg; }
Ted Kremeneke8ee26b2007-08-22 18:22:34 +000074
Ted Kremenekfddd5182007-08-21 21:42:03 +000075 /// buildCFG - Constructs a CFG from an AST (a Stmt*). The AST can
76 /// represent an arbitrary statement. Examples include a single expression
77 /// or a function body (compound statement). The ownership of the returned
78 /// CFG is transferred to the caller. If CFG construction fails, this method
79 /// returns NULL.
80 CFG* buildCFG(Stmt* Statement) {
81 if (!Statement) return NULL;
82
Ted Kremenek0cebe3e2007-08-21 23:26:17 +000083 assert (!Exit && "CFGBuilder should only be used to construct one CFG");
Ted Kremenekfddd5182007-08-21 21:42:03 +000084
85 // Create the exit block.
86 Block = createBlock();
87 Exit = Block;
88
89 // Visit the statements and create the CFG.
Ted Kremenekc310e932007-08-21 22:06:14 +000090 if (CFGBlock* B = Visit(Statement)) {
Ted Kremeneke8ee26b2007-08-22 18:22:34 +000091 // Finalize the last constructed block. This usually involves
92 // reversing the order of the statements in the block.
93 FinishBlock(B);
Ted Kremenek0cebe3e2007-08-21 23:26:17 +000094
95 // Backpatch the gotos whose label -> block mappings we didn't know
96 // when we encountered them.
97 for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(),
98 E = BackpatchBlocks.end(); I != E; ++I ) {
99
100 CFGBlock* B = *I;
101 GotoStmt* G = cast<GotoStmt>(B->getTerminator());
102 LabelMapTy::iterator LI = LabelMap.find(G->getLabel());
103
104 if (LI == LabelMap.end())
105 return NULL; // No matching label. Bad CFG.
106
107 B->addSuccessor(LI->second);
108 }
109
Ted Kremenekfddd5182007-08-21 21:42:03 +0000110 // NULL out cfg so that repeated calls
111 CFG* t = cfg;
112 cfg = NULL;
113 return t;
114 }
Ted Kremenek0cebe3e2007-08-21 23:26:17 +0000115 else return NULL;
Ted Kremenekfddd5182007-08-21 21:42:03 +0000116 }
Ted Kremenekc310e932007-08-21 22:06:14 +0000117
Ted Kremenekfddd5182007-08-21 21:42:03 +0000118 // createBlock - Used to lazily create blocks that are connected
119 // to the current (global) succcessor.
120 CFGBlock* createBlock( bool add_successor = true ) {
121 CFGBlock* B = cfg->createBlock(NumBlocks++);
122 if (add_successor && Succ) B->addSuccessor(Succ);
123 return B;
124 }
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000125
126 // FinishBlock - When the last statement has been added to the block,
127 // usually we must reverse the statements because they have been inserted
128 // in reverse order. When processing labels, however, there are cases
129 // in the recursion where we may have already reversed the statements
130 // in a block. This method safely tidies up a block: if the block
131 // has a label at the front, it has already been reversed. Otherwise,
132 // we reverse it.
133 void FinishBlock(CFGBlock* B) {
134 assert (B);
135 CFGBlock::iterator I = B->begin();
136 if (I != B->end()) {
137 Stmt* S = *I;
138 if (S->getStmtClass() != Stmt::LabelStmtClass)
139 B->reverseStmts();
140 }
141 }
Ted Kremenekfddd5182007-08-21 21:42:03 +0000142
Ted Kremenekc310e932007-08-21 22:06:14 +0000143 /// Here we handle statements with no branching control flow.
144 CFGBlock* VisitStmt(Stmt* Statement) {
145 // We cannot assume that we are in the middle of a basic block, since
146 // the CFG might only be constructed for this single statement. If
147 // we have no current basic block, just create one lazily.
148 if (!Block) Block = createBlock();
149
150 // Simply add the statement to the current block. We actually
151 // insert statements in reverse order; this order is reversed later
152 // when processing the containing element in the AST.
153 Block->appendStmt(Statement);
Ted Kremenekfddd5182007-08-21 21:42:03 +0000154
155 return Block;
156 }
157
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000158 CFGBlock* VisitNullStmt(NullStmt* Statement) {
159 return Block;
160 }
161
Ted Kremenekc310e932007-08-21 22:06:14 +0000162 CFGBlock* VisitCompoundStmt(CompoundStmt* C) {
163 // The value returned from this function is the last created CFGBlock
164 // that represents the "entry" point for the translated AST node.
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000165 CFGBlock* LastBlock;
166
Ted Kremenekc310e932007-08-21 22:06:14 +0000167 for (CompoundStmt::reverse_body_iterator I = C->body_rbegin(),
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000168 E = C->body_rend(); I != E; ++I )
Ted Kremenekc310e932007-08-21 22:06:14 +0000169 // Add the statement to the current block.
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000170 if (!(LastBlock=Visit(*I)))
171 return NULL;
Ted Kremenekc310e932007-08-21 22:06:14 +0000172
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000173 return LastBlock;
Ted Kremenekc310e932007-08-21 22:06:14 +0000174 }
175
176 CFGBlock* VisitIfStmt(IfStmt* I) {
177
178 // We may see an if statement in the middle of a basic block, or
179 // it may be the first statement we are processing. In either case,
180 // we create a new basic block. First, we create the blocks for
181 // the then...else statements, and then we create the block containing
182 // the if statement. If we were in the middle of a block, we
183 // stop processing that block and reverse its statements. That block
184 // is then the implicit successor for the "then" and "else" clauses.
185
186 // The block we were proccessing is now finished. Make it the
187 // successor block.
188 if (Block) {
189 Succ = Block;
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000190 FinishBlock(Block);
Ted Kremenekc310e932007-08-21 22:06:14 +0000191 }
192
193 // Process the false branch. NULL out Block so that the recursive
194 // call to Visit will create a new basic block.
195 // Null out Block so that all successor
196 CFGBlock* ElseBlock = Succ;
197
198 if (Stmt* Else = I->getElse()) {
199 SaveAndRestore<CFGBlock*> sv(Succ);
200
201 // NULL out Block so that the recursive call to Visit will
202 // create a new basic block.
203 Block = NULL;
204 ElseBlock = Visit(Else);
205 if (!ElseBlock) return NULL;
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000206 FinishBlock(ElseBlock);
Ted Kremenekc310e932007-08-21 22:06:14 +0000207 }
208
209 // Process the true branch. NULL out Block so that the recursive
210 // call to Visit will create a new basic block.
211 // Null out Block so that all successor
212 CFGBlock* ThenBlock;
213 {
214 Stmt* Then = I->getThen();
215 assert (Then);
216 SaveAndRestore<CFGBlock*> sv(Succ);
217 Block = NULL;
218 ThenBlock = Visit(Then);
219 if (!ThenBlock) return NULL;
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000220 FinishBlock(ThenBlock);
Ted Kremenekc310e932007-08-21 22:06:14 +0000221 }
222
223 // Now create a new block containing the if statement.
224 Block = createBlock(false);
225
226 // Add the condition as the last statement in the new block.
227 Block->appendStmt(I->getCond());
228
229 // Set the terminator of the new block to the If statement.
230 Block->setTerminator(I);
231
232 // Now add the successors.
233 Block->addSuccessor(ThenBlock);
234 Block->addSuccessor(ElseBlock);
235
236 return Block;
237 }
238
239 CFGBlock* VisitReturnStmt(ReturnStmt* R) {
240 // If we were in the middle of a block we stop processing that block
241 // and reverse its statements.
242 //
243 // NOTE: If a "return" appears in the middle of a block, this means
244 // that the code afterwards is DEAD (unreachable). We still
245 // keep a basic block for that code; a simple "mark-and-sweep"
246 // from the entry block will be able to report such dead
247 // blocks.
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000248 if (Block) FinishBlock(Block);
Ted Kremenekc310e932007-08-21 22:06:14 +0000249
250 // Create the new block.
251 Block = createBlock(false);
252
253 // The Exit block is the only successor.
254 Block->addSuccessor(Exit);
255
256 // Add the return expression to the block.
257 Block->appendStmt(R);
258
259 // Add the return statement itself to the block.
260 if (R->getRetValue()) Block->appendStmt(R->getRetValue());
261
262 return Block;
Ted Kremenek0cebe3e2007-08-21 23:26:17 +0000263 }
264
265 CFGBlock* VisitLabelStmt(LabelStmt* L) {
266 // Get the block of the labeled statement. Add it to our map.
267 CFGBlock* LabelBlock = Visit(L->getSubStmt());
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000268 assert (LabelBlock);
Ted Kremenek0cebe3e2007-08-21 23:26:17 +0000269
270 assert (LabelMap.find(L) == LabelMap.end() && "label already in map");
271 LabelMap[ L ] = LabelBlock;
272
273 // Labels partition blocks, so this is the end of the basic block
274 // we were processing (the label is the first statement).
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000275 LabelBlock->appendStmt(L);
276 FinishBlock(LabelBlock);
Ted Kremenek0cebe3e2007-08-21 23:26:17 +0000277
278 // We set Block to NULL to allow lazy creation of a new block
279 // (if necessary);
280 Block = NULL;
281
282 // This block is now the implicit successor of other blocks.
283 Succ = LabelBlock;
284
285 return LabelBlock;
286 }
287
288 CFGBlock* VisitGotoStmt(GotoStmt* G) {
289 // Goto is a control-flow statement. Thus we stop processing the
290 // current block and create a new one.
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000291 if (Block) FinishBlock(Block);
Ted Kremenek0cebe3e2007-08-21 23:26:17 +0000292 Block = createBlock(false);
293 Block->setTerminator(G);
294
295 // If we already know the mapping to the label block add the
296 // successor now.
297 LabelMapTy::iterator I = LabelMap.find(G->getLabel());
298
299 if (I == LabelMap.end())
300 // We will need to backpatch this block later.
301 BackpatchBlocks.push_back(Block);
302 else
303 Block->addSuccessor(I->second);
304
305 return Block;
306 }
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000307
308 CFGBlock* VisitForStmt(ForStmt* F) {
309 // For is a control-flow statement. Thus we stop processing the
310 // current block.
311 if (Block) FinishBlock(Block);
312
313 // Besides the loop body, we actually create two new blocks:
314 //
315 // The first contains the initialization statement for the loop.
316 //
317 // The second block evaluates the loop condition.
318 //
319 // We create the initialization block last, as that will be the block
320 // we return for the recursion.
321
322 CFGBlock* CondBlock = createBlock(false);
323 if (Stmt* C = F->getCond()) CondBlock->appendStmt(C);
324 CondBlock->setTerminator(F);
325 Succ = CondBlock;
326
327 // Now create the loop body.
328 {
329 assert (F->getBody());
330 SaveAndRestore<CFGBlock*> sv(Block);
331
332 // create a new block to contain the body.
333 Block = createBlock();
334
335 // If we have increment code, insert it at the end of the body block.
336 if (Stmt* I = F->getInc()) Block->appendStmt(I);
337
338 // Now populate the body block, and in the process create new blocks
339 // as we walk the body of the loop.
340 CFGBlock* BodyBlock = Visit(F->getBody());
341
342 assert (BodyBlock);
343 FinishBlock(BodyBlock);
344
345 // This new body block is a successor to our condition block.
346 CondBlock->addSuccessor(BodyBlock);
347 }
348
349 // Link up the condition block with the code that follows the loop.
350 // (the false branch).
351 CondBlock->addSuccessor(Block);
352
353 // Now create the block to contain the initialization.
354 Succ = CondBlock;
355 Block = createBlock();
356
357 if (Stmt* I = F->getInit()) Block->appendStmt(I);
358 return Block;
359 }
Ted Kremenekfddd5182007-08-21 21:42:03 +0000360};
361
362// BuildCFG - A helper function that builds CFGs from ASTS.
Ted Kremenekc310e932007-08-21 22:06:14 +0000363CFG* CFG::BuildCFG(Stmt* Statement) {
Ted Kremenekfddd5182007-08-21 21:42:03 +0000364 CFGBuilder Builder;
365 return Builder.buildCFG(Statement);
366}
367
368// reverseStmts - A method that reverses the order of the statements within
369// a CFGBlock.
370void CFGBlock::reverseStmts() { std::reverse(Stmts.begin(),Stmts.end()); }
371
372// dump - A simple pretty printer of a CFG that outputs to stderr.
373void CFG::dump() { print(std::cerr); }
374
375// print - A simple pretty printer of a CFG that outputs to an ostream.
376void CFG::print(std::ostream& OS) {
377 // Iterate through the CFGBlocks and print them one by one. Specially
378 // designate the Entry and Exit blocks.
379 for (iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) {
380 OS << "\n [ B" << I->getBlockID();
Ted Kremenek0cebe3e2007-08-21 23:26:17 +0000381 if (&(*I) == &getExit()) OS << " (EXIT) ]\n";
382 else if (&(*I) == &getEntry()) OS << " (ENTRY) ]\n";
Ted Kremenekfddd5182007-08-21 21:42:03 +0000383 else OS << " ]\n";
384 I->print(OS);
385 }
386 OS << "\n";
387}
388
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000389
390namespace {
391
392 class CFGBlockTerminatorPrint : public StmtVisitor<CFGBlockTerminatorPrint,
393 void > {
394 std::ostream& OS;
395 public:
396 CFGBlockTerminatorPrint(std::ostream& os) : OS(os) {}
397
398 void VisitIfStmt(IfStmt* I) {
399 OS << "if ";
400 I->getCond()->printPretty(std::cerr);
401 OS << "\n";
402 }
403
404 // Default case.
405 void VisitStmt(Stmt* S) { S->printPretty(OS); }
406
407 void VisitForStmt(ForStmt* F) {
408 OS << "for (" ;
409 if (Stmt* I = F->getInit()) I->printPretty(OS);
410 OS << " ; ";
411 if (Stmt* C = F->getCond()) C->printPretty(OS);
412 OS << " ; ";
413 if (Stmt* I = F->getInc()) I->printPretty(OS);
414 OS << ")\n";
415 }
416 };
417}
418
Ted Kremenekfddd5182007-08-21 21:42:03 +0000419// dump - A simply pretty printer of a CFGBlock that outputs to stderr.
420void CFGBlock::dump() { print(std::cerr); }
421
422// print - A simple pretty printer of a CFGBlock that outputs to an ostream.
423// Generally this will only be called from CFG::print.
424void CFGBlock::print(std::ostream& OS) {
425
426 // Iterate through the statements in the block and print them.
427 OS << " ------------------------\n";
428 unsigned j = 1;
429 for (iterator I = Stmts.begin(), E = Stmts.end() ; I != E ; ++I, ++j ) {
Ted Kremenek0cebe3e2007-08-21 23:26:17 +0000430 // Print the statement # in the basic block.
431 OS << " " << std::setw(3) << j << ": ";
432
433 // Print the statement/expression.
434 Stmt* S = *I;
435
436 if (LabelStmt* L = dyn_cast<LabelStmt>(S))
437 OS << L->getName() << ": (LABEL)\n";
438 else
439 (*I)->printPretty(OS);
440
441 // Expressions need a newline.
Ted Kremenekfddd5182007-08-21 21:42:03 +0000442 if (isa<Expr>(*I)) OS << '\n';
443 }
444 OS << " ------------------------\n";
445
446 // Print the predecessors of this block.
447 OS << " Predecessors (" << pred_size() << "):";
448 unsigned i = 0;
449 for (pred_iterator I = pred_begin(), E = pred_end(); I != E; ++I, ++i ) {
450 if (i == 8 || (i-8) == 0) {
451 OS << "\n ";
452 }
453 OS << " B" << (*I)->getBlockID();
454 }
455
456 // Print the terminator of this block.
457 OS << "\n Terminator: ";
Ted Kremeneke8ee26b2007-08-22 18:22:34 +0000458 if (ControlFlowStmt)
459 CFGBlockTerminatorPrint(OS).Visit(ControlFlowStmt);
460 else
461 OS << "<NULL>\n";
Ted Kremenekfddd5182007-08-21 21:42:03 +0000462
463 // Print the successors of this block.
464 OS << " Successors (" << succ_size() << "):";
465 i = 0;
466 for (succ_iterator I = succ_begin(), E = succ_end(); I != E; ++I, ++i ) {
467 if (i == 8 || (i-8) % 10 == 0) {
468 OS << "\n ";
469 }
470 OS << " B" << (*I)->getBlockID();
471 }
472 OS << '\n';
473}