CFG.cpp revision e41611aa2237d06a0ef61db4528fb2883a8defcd
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===--- CFG.cpp - Classes for representing and building CFGs----*- C++ -*-===// 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// The LLVM Compiler Infrastructure 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file is distributed under the University of Illinois Open Source 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// License. See LICENSE.TXT for details. 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// 8eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch//===----------------------------------------------------------------------===// 92a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This file defines the CFG and CFGBuilder classes for representing and 11eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch// building Control-Flow Graphs (CFGs) from ASTs. 122a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//===----------------------------------------------------------------------===// 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "clang/Analysis/CFG.h" 162a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "clang/AST/StmtVisitor.h" 172a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "clang/AST/PrettyPrinter.h" 182a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/ADT/DenseMap.h" 192a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/ADT/SmallPtrSet.h" 202a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/Support/GraphWriter.h" 212a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include "llvm/Support/Streams.h" 22eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch#include "llvm/Support/Compiler.h" 232a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)#include <llvm/Support/Allocator.h> 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <llvm/Support/Format.h> 252a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 262a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)using namespace clang; 272a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 29c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SaveAndRestore - A utility class that uses RIIA to save and restore 312a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)// the value of a variable. 322a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)template<typename T> 332a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)struct VISIBILITY_HIDDEN SaveAndRestore { 342a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SaveAndRestore(T& x) : X(x), old_value(x) {} 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ~SaveAndRestore() { X = old_value; } 362a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T get() { return old_value; } 372a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 38eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch T& X; 392a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) T old_value; 402a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles)}; 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 42eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdochstatic SourceLocation GetEndLoc(Decl* D) { 43eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch if (VarDecl* VD = dyn_cast<VarDecl>(D)) 44eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch if (Expr* Ex = VD->getInit()) 45eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch return Ex->getSourceRange().getEnd(); 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 47eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch return D->getLocation(); 48eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch} 49eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 50eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch/// CFGBuilder - This class implements CFG construction from an AST. 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/// The builder is stateful: an instance of the builder should be used to only 52eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch/// construct a single CFG. 53eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch/// 54eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch/// Example usage: 55eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch/// 56eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch/// CFGBuilder builder; 57eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch/// CFG* cfg = builder.BuildAST(stmt1); 58eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch/// 59eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch/// CFG construction is done via a recursive walk of an AST. 60eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch/// We actually parse the AST in reverse order so that the successor 61eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch/// of a basic block is constructed prior to its predecessor. This 62eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch/// allows us to nicely capture implicit fall-throughs without extra 63eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch/// basic blocks. 64eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch/// 65eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdochclass VISIBILITY_HIDDEN CFGBuilder : public StmtVisitor<CFGBuilder,CFGBlock*> { 66eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch CFG* cfg; 67eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch CFGBlock* Block; 68eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch CFGBlock* Succ; 69eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch CFGBlock* ContinueTargetBlock; 70eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch CFGBlock* BreakTargetBlock; 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CFGBlock* SwitchTerminatedBlock; 722a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) CFGBlock* DefaultCaseBlock; 732a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 742a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // LabelMap records the mapping from Label expressions to their blocks. 75eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch typedef llvm::DenseMap<LabelStmt*,CFGBlock*> LabelMapTy; 76eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch LabelMapTy LabelMap; 77eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 78eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch // A list of blocks that end with a "goto" that must be backpatched to 79eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch // their resolved targets upon completion of CFG construction. 80eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch typedef std::vector<CFGBlock*> BackpatchBlocksTy; 81eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch BackpatchBlocksTy BackpatchBlocks; 82eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch 83eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch // A list of labels whose address has been taken (for indirect gotos). 84eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdoch typedef llvm::SmallPtrSet<LabelStmt*,5> LabelSetTy; 852a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) LabelSetTy AddressTakenLabels; 862a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 87eb525c5499e34cc9c4b825d6d9e75bb07cc06aceBen Murdochpublic: 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit CFGBuilder() : cfg(NULL), Block(NULL), Succ(NULL), 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ContinueTargetBlock(NULL), BreakTargetBlock(NULL), 902a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL) { 912a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // Create an empty CFG. 922a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) cfg = new CFG(); 932a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) } 942a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 952a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) ~CFGBuilder() { delete cfg; } 962a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 972a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // buildCFG - Used by external clients to construct the CFG. 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CFG* buildCFG(Stmt* Statement); 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Visitors to walk an AST and construct the CFG. Called by 1012a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) // buildCFG. Do not call directly! 1022a99a7e74a7f215066514fe81d2bfa6639d9edddTorne (Richard Coles) 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CFGBlock* VisitBreakStmt(BreakStmt* B); 104c2e0dbddbe15c98d52c4786dac06cb8952a8ae6dTorne (Richard Coles) CFGBlock* VisitCaseStmt(CaseStmt* Terminator); 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CFGBlock* VisitCompoundStmt(CompoundStmt* C); 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CFGBlock* VisitContinueStmt(ContinueStmt* C); 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CFGBlock* VisitDefaultStmt(DefaultStmt* D); 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CFGBlock* VisitDoStmt(DoStmt* D); 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CFGBlock* VisitForStmt(ForStmt* F); 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CFGBlock* VisitGotoStmt(GotoStmt* G); 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CFGBlock* VisitIfStmt(IfStmt* I); 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CFGBlock* VisitIndirectGotoStmt(IndirectGotoStmt* I); 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CFGBlock* VisitLabelStmt(LabelStmt* L); 114 CFGBlock* VisitNullStmt(NullStmt* Statement); 115 CFGBlock* VisitObjCForCollectionStmt(ObjCForCollectionStmt* S); 116 CFGBlock* VisitReturnStmt(ReturnStmt* R); 117 CFGBlock* VisitStmt(Stmt* Statement); 118 CFGBlock* VisitSwitchStmt(SwitchStmt* Terminator); 119 CFGBlock* VisitWhileStmt(WhileStmt* W); 120 121 // FIXME: Add support for ObjC-specific control-flow structures. 122 123 // NYS == Not Yet Supported 124 CFGBlock* NYS() { 125 badCFG = true; 126 return Block; 127 } 128 129 CFGBlock* VisitObjCAtTryStmt(ObjCAtTryStmt* S); 130 CFGBlock* VisitObjCAtCatchStmt(ObjCAtCatchStmt* S) { 131 // FIXME: For now we pretend that @catch and the code it contains 132 // does not exit. 133 return Block; 134 } 135 136 // FIXME: This is not completely supported. We basically @throw like 137 // a 'return'. 138 CFGBlock* VisitObjCAtThrowStmt(ObjCAtThrowStmt* S); 139 140 CFGBlock* VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S); 141 142 // Blocks. 143 CFGBlock* VisitBlockExpr(BlockExpr* E) { return NYS(); } 144 CFGBlock* VisitBlockDeclRefExpr(BlockDeclRefExpr* E) { return NYS(); } 145 146private: 147 CFGBlock* createBlock(bool add_successor = true); 148 CFGBlock* addStmt(Stmt* Terminator); 149 CFGBlock* WalkAST(Stmt* Terminator, bool AlwaysAddStmt); 150 CFGBlock* WalkAST_VisitChildren(Stmt* Terminator); 151 CFGBlock* WalkAST_VisitDeclSubExpr(Decl* D); 152 CFGBlock* WalkAST_VisitStmtExpr(StmtExpr* Terminator); 153 bool FinishBlock(CFGBlock* B); 154 155 bool badCFG; 156}; 157 158// FIXME: Add support for dependent-sized array types in C++? 159// Does it even make sense to build a CFG for an uninstantiated template? 160static VariableArrayType* FindVA(Type* t) { 161 while (ArrayType* vt = dyn_cast<ArrayType>(t)) { 162 if (VariableArrayType* vat = dyn_cast<VariableArrayType>(vt)) 163 if (vat->getSizeExpr()) 164 return vat; 165 166 t = vt->getElementType().getTypePtr(); 167 } 168 169 return 0; 170} 171 172/// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can 173/// represent an arbitrary statement. Examples include a single expression 174/// or a function body (compound statement). The ownership of the returned 175/// CFG is transferred to the caller. If CFG construction fails, this method 176/// returns NULL. 177CFG* CFGBuilder::buildCFG(Stmt* Statement) { 178 assert (cfg); 179 if (!Statement) return NULL; 180 181 badCFG = false; 182 183 // Create an empty block that will serve as the exit block for the CFG. 184 // Since this is the first block added to the CFG, it will be implicitly 185 // registered as the exit block. 186 Succ = createBlock(); 187 assert (Succ == &cfg->getExit()); 188 Block = NULL; // the EXIT block is empty. Create all other blocks lazily. 189 190 // Visit the statements and create the CFG. 191 CFGBlock* B = Visit(Statement); 192 if (!B) B = Succ; 193 194 if (B) { 195 // Finalize the last constructed block. This usually involves 196 // reversing the order of the statements in the block. 197 if (Block) FinishBlock(B); 198 199 // Backpatch the gotos whose label -> block mappings we didn't know 200 // when we encountered them. 201 for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(), 202 E = BackpatchBlocks.end(); I != E; ++I ) { 203 204 CFGBlock* B = *I; 205 GotoStmt* G = cast<GotoStmt>(B->getTerminator()); 206 LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); 207 208 // If there is no target for the goto, then we are looking at an 209 // incomplete AST. Handle this by not registering a successor. 210 if (LI == LabelMap.end()) continue; 211 212 B->addSuccessor(LI->second); 213 } 214 215 // Add successors to the Indirect Goto Dispatch block (if we have one). 216 if (CFGBlock* B = cfg->getIndirectGotoBlock()) 217 for (LabelSetTy::iterator I = AddressTakenLabels.begin(), 218 E = AddressTakenLabels.end(); I != E; ++I ) { 219 220 // Lookup the target block. 221 LabelMapTy::iterator LI = LabelMap.find(*I); 222 223 // If there is no target block that contains label, then we are looking 224 // at an incomplete AST. Handle this by not registering a successor. 225 if (LI == LabelMap.end()) continue; 226 227 B->addSuccessor(LI->second); 228 } 229 230 Succ = B; 231 } 232 233 // Create an empty entry block that has no predecessors. 234 cfg->setEntry(createBlock()); 235 236 if (badCFG) { 237 delete cfg; 238 cfg = NULL; 239 return NULL; 240 } 241 242 // NULL out cfg so that repeated calls to the builder will fail and that 243 // the ownership of the constructed CFG is passed to the caller. 244 CFG* t = cfg; 245 cfg = NULL; 246 return t; 247} 248 249/// createBlock - Used to lazily create blocks that are connected 250/// to the current (global) succcessor. 251CFGBlock* CFGBuilder::createBlock(bool add_successor) { 252 CFGBlock* B = cfg->createBlock(); 253 if (add_successor && Succ) B->addSuccessor(Succ); 254 return B; 255} 256 257/// FinishBlock - When the last statement has been added to the block, 258/// we must reverse the statements because they have been inserted 259/// in reverse order. 260bool CFGBuilder::FinishBlock(CFGBlock* B) { 261 if (badCFG) 262 return false; 263 264 assert (B); 265 B->reverseStmts(); 266 return true; 267} 268 269/// addStmt - Used to add statements/expressions to the current CFGBlock 270/// "Block". This method calls WalkAST on the passed statement to see if it 271/// contains any short-circuit expressions. If so, it recursively creates 272/// the necessary blocks for such expressions. It returns the "topmost" block 273/// of the created blocks, or the original value of "Block" when this method 274/// was called if no additional blocks are created. 275CFGBlock* CFGBuilder::addStmt(Stmt* Terminator) { 276 if (!Block) Block = createBlock(); 277 return WalkAST(Terminator,true); 278} 279 280/// WalkAST - Used by addStmt to walk the subtree of a statement and 281/// add extra blocks for ternary operators, &&, and ||. We also 282/// process "," and DeclStmts (which may contain nested control-flow). 283CFGBlock* CFGBuilder::WalkAST(Stmt* Terminator, bool AlwaysAddStmt = false) { 284 switch (Terminator->getStmtClass()) { 285 case Stmt::ConditionalOperatorClass: { 286 ConditionalOperator* C = cast<ConditionalOperator>(Terminator); 287 288 // Create the confluence block that will "merge" the results 289 // of the ternary expression. 290 CFGBlock* ConfluenceBlock = (Block) ? Block : createBlock(); 291 ConfluenceBlock->appendStmt(C); 292 if (!FinishBlock(ConfluenceBlock)) 293 return 0; 294 295 // Create a block for the LHS expression if there is an LHS expression. 296 // A GCC extension allows LHS to be NULL, causing the condition to 297 // be the value that is returned instead. 298 // e.g: x ?: y is shorthand for: x ? x : y; 299 Succ = ConfluenceBlock; 300 Block = NULL; 301 CFGBlock* LHSBlock = NULL; 302 if (C->getLHS()) { 303 LHSBlock = Visit(C->getLHS()); 304 if (!FinishBlock(LHSBlock)) 305 return 0; 306 Block = NULL; 307 } 308 309 // Create the block for the RHS expression. 310 Succ = ConfluenceBlock; 311 CFGBlock* RHSBlock = Visit(C->getRHS()); 312 if (!FinishBlock(RHSBlock)) 313 return 0; 314 315 // Create the block that will contain the condition. 316 Block = createBlock(false); 317 318 if (LHSBlock) 319 Block->addSuccessor(LHSBlock); 320 else { 321 // If we have no LHS expression, add the ConfluenceBlock as a direct 322 // successor for the block containing the condition. Moreover, 323 // we need to reverse the order of the predecessors in the 324 // ConfluenceBlock because the RHSBlock will have been added to 325 // the succcessors already, and we want the first predecessor to the 326 // the block containing the expression for the case when the ternary 327 // expression evaluates to true. 328 Block->addSuccessor(ConfluenceBlock); 329 assert (ConfluenceBlock->pred_size() == 2); 330 std::reverse(ConfluenceBlock->pred_begin(), 331 ConfluenceBlock->pred_end()); 332 } 333 334 Block->addSuccessor(RHSBlock); 335 336 Block->setTerminator(C); 337 return addStmt(C->getCond()); 338 } 339 340 case Stmt::ChooseExprClass: { 341 ChooseExpr* C = cast<ChooseExpr>(Terminator); 342 343 CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 344 ConfluenceBlock->appendStmt(C); 345 if (!FinishBlock(ConfluenceBlock)) 346 return 0; 347 348 Succ = ConfluenceBlock; 349 Block = NULL; 350 CFGBlock* LHSBlock = Visit(C->getLHS()); 351 if (!FinishBlock(LHSBlock)) 352 return 0; 353 354 Succ = ConfluenceBlock; 355 Block = NULL; 356 CFGBlock* RHSBlock = Visit(C->getRHS()); 357 if (!FinishBlock(RHSBlock)) 358 return 0; 359 360 Block = createBlock(false); 361 Block->addSuccessor(LHSBlock); 362 Block->addSuccessor(RHSBlock); 363 Block->setTerminator(C); 364 return addStmt(C->getCond()); 365 } 366 367 case Stmt::DeclStmtClass: { 368 DeclStmt *DS = cast<DeclStmt>(Terminator); 369 if (DS->isSingleDecl()) { 370 Block->appendStmt(Terminator); 371 return WalkAST_VisitDeclSubExpr(DS->getSingleDecl()); 372 } 373 374 CFGBlock* B = 0; 375 376 // FIXME: Add a reverse iterator for DeclStmt to avoid this 377 // extra copy. 378 typedef llvm::SmallVector<Decl*,10> BufTy; 379 BufTy Buf(DS->decl_begin(), DS->decl_end()); 380 381 for (BufTy::reverse_iterator I=Buf.rbegin(), E=Buf.rend(); I!=E; ++I) { 382 // Get the alignment of the new DeclStmt, padding out to >=8 bytes. 383 unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8 384 ? 8 : llvm::AlignOf<DeclStmt>::Alignment; 385 386 // Allocate the DeclStmt using the BumpPtrAllocator. It will 387 // get automatically freed with the CFG. 388 DeclGroupRef DG(*I); 389 Decl* D = *I; 390 void* Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A); 391 392 DeclStmt* DS = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); 393 394 // Append the fake DeclStmt to block. 395 Block->appendStmt(DS); 396 B = WalkAST_VisitDeclSubExpr(D); 397 } 398 return B; 399 } 400 401 case Stmt::AddrLabelExprClass: { 402 AddrLabelExpr* A = cast<AddrLabelExpr>(Terminator); 403 AddressTakenLabels.insert(A->getLabel()); 404 405 if (AlwaysAddStmt) Block->appendStmt(Terminator); 406 return Block; 407 } 408 409 case Stmt::StmtExprClass: 410 return WalkAST_VisitStmtExpr(cast<StmtExpr>(Terminator)); 411 412 case Stmt::SizeOfAlignOfExprClass: { 413 SizeOfAlignOfExpr* E = cast<SizeOfAlignOfExpr>(Terminator); 414 415 // VLA types have expressions that must be evaluated. 416 if (E->isArgumentType()) { 417 for (VariableArrayType* VA = FindVA(E->getArgumentType().getTypePtr()); 418 VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) 419 addStmt(VA->getSizeExpr()); 420 } 421 // Expressions in sizeof/alignof are not evaluated and thus have no 422 // control flow. 423 else 424 Block->appendStmt(Terminator); 425 426 return Block; 427 } 428 429 case Stmt::BinaryOperatorClass: { 430 BinaryOperator* B = cast<BinaryOperator>(Terminator); 431 432 if (B->isLogicalOp()) { // && or || 433 CFGBlock* ConfluenceBlock = (Block) ? Block : createBlock(); 434 ConfluenceBlock->appendStmt(B); 435 if (!FinishBlock(ConfluenceBlock)) 436 return 0; 437 438 // create the block evaluating the LHS 439 CFGBlock* LHSBlock = createBlock(false); 440 LHSBlock->setTerminator(B); 441 442 // create the block evaluating the RHS 443 Succ = ConfluenceBlock; 444 Block = NULL; 445 CFGBlock* RHSBlock = Visit(B->getRHS()); 446 if (!FinishBlock(RHSBlock)) 447 return 0; 448 449 // Now link the LHSBlock with RHSBlock. 450 if (B->getOpcode() == BinaryOperator::LOr) { 451 LHSBlock->addSuccessor(ConfluenceBlock); 452 LHSBlock->addSuccessor(RHSBlock); 453 } 454 else { 455 assert (B->getOpcode() == BinaryOperator::LAnd); 456 LHSBlock->addSuccessor(RHSBlock); 457 LHSBlock->addSuccessor(ConfluenceBlock); 458 } 459 460 // Generate the blocks for evaluating the LHS. 461 Block = LHSBlock; 462 return addStmt(B->getLHS()); 463 } 464 else if (B->getOpcode() == BinaryOperator::Comma) { // , 465 Block->appendStmt(B); 466 addStmt(B->getRHS()); 467 return addStmt(B->getLHS()); 468 } 469 470 break; 471 } 472 473 // Blocks: No support for blocks ... yet 474 case Stmt::BlockExprClass: 475 case Stmt::BlockDeclRefExprClass: 476 return NYS(); 477 478 case Stmt::ParenExprClass: 479 return WalkAST(cast<ParenExpr>(Terminator)->getSubExpr(), AlwaysAddStmt); 480 481 default: 482 break; 483 }; 484 485 if (AlwaysAddStmt) Block->appendStmt(Terminator); 486 return WalkAST_VisitChildren(Terminator); 487} 488 489/// WalkAST_VisitDeclSubExpr - Utility method to add block-level expressions 490/// for initializers in Decls. 491CFGBlock* CFGBuilder::WalkAST_VisitDeclSubExpr(Decl* D) { 492 VarDecl* VD = dyn_cast<VarDecl>(D); 493 494 if (!VD) 495 return Block; 496 497 Expr* Init = VD->getInit(); 498 499 if (Init) { 500 // Optimization: Don't create separate block-level statements for literals. 501 switch (Init->getStmtClass()) { 502 case Stmt::IntegerLiteralClass: 503 case Stmt::CharacterLiteralClass: 504 case Stmt::StringLiteralClass: 505 break; 506 default: 507 Block = addStmt(Init); 508 } 509 } 510 511 // If the type of VD is a VLA, then we must process its size expressions. 512 for (VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); VA != 0; 513 VA = FindVA(VA->getElementType().getTypePtr())) 514 Block = addStmt(VA->getSizeExpr()); 515 516 return Block; 517} 518 519/// WalkAST_VisitChildren - Utility method to call WalkAST on the 520/// children of a Stmt. 521CFGBlock* CFGBuilder::WalkAST_VisitChildren(Stmt* Terminator) { 522 CFGBlock* B = Block; 523 for (Stmt::child_iterator I = Terminator->child_begin(), 524 E = Terminator->child_end(); 525 I != E; ++I) 526 if (*I) B = WalkAST(*I); 527 528 return B; 529} 530 531/// WalkAST_VisitStmtExpr - Utility method to handle (nested) statement 532/// expressions (a GCC extension). 533CFGBlock* CFGBuilder::WalkAST_VisitStmtExpr(StmtExpr* Terminator) { 534 Block->appendStmt(Terminator); 535 return VisitCompoundStmt(Terminator->getSubStmt()); 536} 537 538/// VisitStmt - Handle statements with no branching control flow. 539CFGBlock* CFGBuilder::VisitStmt(Stmt* Statement) { 540 // We cannot assume that we are in the middle of a basic block, since 541 // the CFG might only be constructed for this single statement. If 542 // we have no current basic block, just create one lazily. 543 if (!Block) Block = createBlock(); 544 545 // Simply add the statement to the current block. We actually 546 // insert statements in reverse order; this order is reversed later 547 // when processing the containing element in the AST. 548 addStmt(Statement); 549 550 return Block; 551} 552 553CFGBlock* CFGBuilder::VisitNullStmt(NullStmt* Statement) { 554 return Block; 555} 556 557CFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) { 558 559 CFGBlock* LastBlock = Block; 560 561 for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); 562 I != E; ++I ) { 563 LastBlock = Visit(*I); 564 } 565 566 return LastBlock; 567} 568 569CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { 570 // We may see an if statement in the middle of a basic block, or 571 // it may be the first statement we are processing. In either case, 572 // we create a new basic block. First, we create the blocks for 573 // the then...else statements, and then we create the block containing 574 // the if statement. If we were in the middle of a block, we 575 // stop processing that block and reverse its statements. That block 576 // is then the implicit successor for the "then" and "else" clauses. 577 578 // The block we were proccessing is now finished. Make it the 579 // successor block. 580 if (Block) { 581 Succ = Block; 582 if (!FinishBlock(Block)) 583 return 0; 584 } 585 586 // Process the false branch. NULL out Block so that the recursive 587 // call to Visit will create a new basic block. 588 // Null out Block so that all successor 589 CFGBlock* ElseBlock = Succ; 590 591 if (Stmt* Else = I->getElse()) { 592 SaveAndRestore<CFGBlock*> sv(Succ); 593 594 // NULL out Block so that the recursive call to Visit will 595 // create a new basic block. 596 Block = NULL; 597 ElseBlock = Visit(Else); 598 599 if (!ElseBlock) // Can occur when the Else body has all NullStmts. 600 ElseBlock = sv.get(); 601 else if (Block) { 602 if (!FinishBlock(ElseBlock)) 603 return 0; 604 } 605 } 606 607 // Process the true branch. NULL out Block so that the recursive 608 // call to Visit will create a new basic block. 609 // Null out Block so that all successor 610 CFGBlock* ThenBlock; 611 { 612 Stmt* Then = I->getThen(); 613 assert (Then); 614 SaveAndRestore<CFGBlock*> sv(Succ); 615 Block = NULL; 616 ThenBlock = Visit(Then); 617 618 if (!ThenBlock) { 619 // We can reach here if the "then" body has all NullStmts. 620 // Create an empty block so we can distinguish between true and false 621 // branches in path-sensitive analyses. 622 ThenBlock = createBlock(false); 623 ThenBlock->addSuccessor(sv.get()); 624 } 625 else if (Block) { 626 if (!FinishBlock(ThenBlock)) 627 return 0; 628 } 629 } 630 631 // Now create a new block containing the if statement. 632 Block = createBlock(false); 633 634 // Set the terminator of the new block to the If statement. 635 Block->setTerminator(I); 636 637 // Now add the successors. 638 Block->addSuccessor(ThenBlock); 639 Block->addSuccessor(ElseBlock); 640 641 // Add the condition as the last statement in the new block. This 642 // may create new blocks as the condition may contain control-flow. Any 643 // newly created blocks will be pointed to be "Block". 644 return addStmt(I->getCond()->IgnoreParens()); 645} 646 647 648CFGBlock* CFGBuilder::VisitReturnStmt(ReturnStmt* R) { 649 // If we were in the middle of a block we stop processing that block 650 // and reverse its statements. 651 // 652 // NOTE: If a "return" appears in the middle of a block, this means 653 // that the code afterwards is DEAD (unreachable). We still 654 // keep a basic block for that code; a simple "mark-and-sweep" 655 // from the entry block will be able to report such dead 656 // blocks. 657 if (Block) FinishBlock(Block); 658 659 // Create the new block. 660 Block = createBlock(false); 661 662 // The Exit block is the only successor. 663 Block->addSuccessor(&cfg->getExit()); 664 665 // Add the return statement to the block. This may create new blocks 666 // if R contains control-flow (short-circuit operations). 667 return addStmt(R); 668} 669 670CFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt* L) { 671 // Get the block of the labeled statement. Add it to our map. 672 Visit(L->getSubStmt()); 673 CFGBlock* LabelBlock = Block; 674 675 if (!LabelBlock) // This can happen when the body is empty, i.e. 676 LabelBlock=createBlock(); // scopes that only contains NullStmts. 677 678 assert (LabelMap.find(L) == LabelMap.end() && "label already in map"); 679 LabelMap[ L ] = LabelBlock; 680 681 // Labels partition blocks, so this is the end of the basic block 682 // we were processing (L is the block's label). Because this is 683 // label (and we have already processed the substatement) there is no 684 // extra control-flow to worry about. 685 LabelBlock->setLabel(L); 686 if (!FinishBlock(LabelBlock)) 687 return 0; 688 689 // We set Block to NULL to allow lazy creation of a new block 690 // (if necessary); 691 Block = NULL; 692 693 // This block is now the implicit successor of other blocks. 694 Succ = LabelBlock; 695 696 return LabelBlock; 697} 698 699CFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) { 700 // Goto is a control-flow statement. Thus we stop processing the 701 // current block and create a new one. 702 if (Block) FinishBlock(Block); 703 Block = createBlock(false); 704 Block->setTerminator(G); 705 706 // If we already know the mapping to the label block add the 707 // successor now. 708 LabelMapTy::iterator I = LabelMap.find(G->getLabel()); 709 710 if (I == LabelMap.end()) 711 // We will need to backpatch this block later. 712 BackpatchBlocks.push_back(Block); 713 else 714 Block->addSuccessor(I->second); 715 716 return Block; 717} 718 719CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { 720 // "for" is a control-flow statement. Thus we stop processing the 721 // current block. 722 723 CFGBlock* LoopSuccessor = NULL; 724 725 if (Block) { 726 if (!FinishBlock(Block)) 727 return 0; 728 LoopSuccessor = Block; 729 } 730 else LoopSuccessor = Succ; 731 732 // Because of short-circuit evaluation, the condition of the loop 733 // can span multiple basic blocks. Thus we need the "Entry" and "Exit" 734 // blocks that evaluate the condition. 735 CFGBlock* ExitConditionBlock = createBlock(false); 736 CFGBlock* EntryConditionBlock = ExitConditionBlock; 737 738 // Set the terminator for the "exit" condition block. 739 ExitConditionBlock->setTerminator(F); 740 741 // Now add the actual condition to the condition block. Because the 742 // condition itself may contain control-flow, new blocks may be created. 743 if (Stmt* C = F->getCond()) { 744 Block = ExitConditionBlock; 745 EntryConditionBlock = addStmt(C); 746 if (Block) { 747 if (!FinishBlock(EntryConditionBlock)) 748 return 0; 749 } 750 } 751 752 // The condition block is the implicit successor for the loop body as 753 // well as any code above the loop. 754 Succ = EntryConditionBlock; 755 756 // Now create the loop body. 757 { 758 assert (F->getBody()); 759 760 // Save the current values for Block, Succ, and continue and break targets 761 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 762 save_continue(ContinueTargetBlock), 763 save_break(BreakTargetBlock); 764 765 // Create a new block to contain the (bottom) of the loop body. 766 Block = NULL; 767 768 if (Stmt* I = F->getInc()) { 769 // Generate increment code in its own basic block. This is the target 770 // of continue statements. 771 Succ = Visit(I); 772 } 773 else { 774 // No increment code. Create a special, empty, block that is used as 775 // the target block for "looping back" to the start of the loop. 776 assert(Succ == EntryConditionBlock); 777 Succ = createBlock(); 778 } 779 780 // Finish up the increment (or empty) block if it hasn't been already. 781 if (Block) { 782 assert(Block == Succ); 783 if (!FinishBlock(Block)) 784 return 0; 785 Block = 0; 786 } 787 788 ContinueTargetBlock = Succ; 789 790 // The starting block for the loop increment is the block that should 791 // represent the 'loop target' for looping back to the start of the loop. 792 ContinueTargetBlock->setLoopTarget(F); 793 794 // All breaks should go to the code following the loop. 795 BreakTargetBlock = LoopSuccessor; 796 797 // Now populate the body block, and in the process create new blocks 798 // as we walk the body of the loop. 799 CFGBlock* BodyBlock = Visit(F->getBody()); 800 801 if (!BodyBlock) 802 BodyBlock = EntryConditionBlock; // can happen for "for (...;...; ) ;" 803 else if (Block) { 804 if (!FinishBlock(BodyBlock)) 805 return 0; 806 } 807 808 // This new body block is a successor to our "exit" condition block. 809 ExitConditionBlock->addSuccessor(BodyBlock); 810 } 811 812 // Link up the condition block with the code that follows the loop. 813 // (the false branch). 814 ExitConditionBlock->addSuccessor(LoopSuccessor); 815 816 // If the loop contains initialization, create a new block for those 817 // statements. This block can also contain statements that precede 818 // the loop. 819 if (Stmt* I = F->getInit()) { 820 Block = createBlock(); 821 return addStmt(I); 822 } 823 else { 824 // There is no loop initialization. We are thus basically a while 825 // loop. NULL out Block to force lazy block construction. 826 Block = NULL; 827 Succ = EntryConditionBlock; 828 return EntryConditionBlock; 829 } 830} 831 832CFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { 833 // Objective-C fast enumeration 'for' statements: 834 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC 835 // 836 // for ( Type newVariable in collection_expression ) { statements } 837 // 838 // becomes: 839 // 840 // prologue: 841 // 1. collection_expression 842 // T. jump to loop_entry 843 // loop_entry: 844 // 1. side-effects of element expression 845 // 1. ObjCForCollectionStmt [performs binding to newVariable] 846 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil] 847 // TB: 848 // statements 849 // T. jump to loop_entry 850 // FB: 851 // what comes after 852 // 853 // and 854 // 855 // Type existingItem; 856 // for ( existingItem in expression ) { statements } 857 // 858 // becomes: 859 // 860 // the same with newVariable replaced with existingItem; the binding 861 // works the same except that for one ObjCForCollectionStmt::getElement() 862 // returns a DeclStmt and the other returns a DeclRefExpr. 863 // 864 865 CFGBlock* LoopSuccessor = 0; 866 867 if (Block) { 868 if (!FinishBlock(Block)) 869 return 0; 870 LoopSuccessor = Block; 871 Block = 0; 872 } 873 else LoopSuccessor = Succ; 874 875 // Build the condition blocks. 876 CFGBlock* ExitConditionBlock = createBlock(false); 877 CFGBlock* EntryConditionBlock = ExitConditionBlock; 878 879 // Set the terminator for the "exit" condition block. 880 ExitConditionBlock->setTerminator(S); 881 882 // The last statement in the block should be the ObjCForCollectionStmt, 883 // which performs the actual binding to 'element' and determines if there 884 // are any more items in the collection. 885 ExitConditionBlock->appendStmt(S); 886 Block = ExitConditionBlock; 887 888 // Walk the 'element' expression to see if there are any side-effects. We 889 // generate new blocks as necesary. We DON'T add the statement by default 890 // to the CFG unless it contains control-flow. 891 EntryConditionBlock = WalkAST(S->getElement(), false); 892 if (Block) { 893 if (!FinishBlock(EntryConditionBlock)) 894 return 0; 895 Block = 0; 896 } 897 898 // The condition block is the implicit successor for the loop body as 899 // well as any code above the loop. 900 Succ = EntryConditionBlock; 901 902 // Now create the true branch. 903 { 904 // Save the current values for Succ, continue and break targets. 905 SaveAndRestore<CFGBlock*> save_Succ(Succ), 906 save_continue(ContinueTargetBlock), save_break(BreakTargetBlock); 907 908 BreakTargetBlock = LoopSuccessor; 909 ContinueTargetBlock = EntryConditionBlock; 910 911 CFGBlock* BodyBlock = Visit(S->getBody()); 912 913 if (!BodyBlock) 914 BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;" 915 else if (Block) { 916 if (!FinishBlock(BodyBlock)) 917 return 0; 918 } 919 920 // This new body block is a successor to our "exit" condition block. 921 ExitConditionBlock->addSuccessor(BodyBlock); 922 } 923 924 // Link up the condition block with the code that follows the loop. 925 // (the false branch). 926 ExitConditionBlock->addSuccessor(LoopSuccessor); 927 928 // Now create a prologue block to contain the collection expression. 929 Block = createBlock(); 930 return addStmt(S->getCollection()); 931} 932 933CFGBlock* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S) { 934 // FIXME: Add locking 'primitives' to CFG for @synchronized. 935 936 // Inline the body. 937 CFGBlock *SyncBlock = Visit(S->getSynchBody()); 938 939 // The sync body starts its own basic block. This makes it a little easier 940 // for diagnostic clients. 941 if (SyncBlock) { 942 if (!FinishBlock(SyncBlock)) 943 return 0; 944 945 Block = 0; 946 } 947 948 Succ = SyncBlock; 949 950 // Inline the sync expression. 951 return Visit(S->getSynchExpr()); 952} 953 954CFGBlock* CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt* S) { 955 return NYS(); 956} 957 958CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { 959 // "while" is a control-flow statement. Thus we stop processing the 960 // current block. 961 962 CFGBlock* LoopSuccessor = NULL; 963 964 if (Block) { 965 if (!FinishBlock(Block)) 966 return 0; 967 LoopSuccessor = Block; 968 } 969 else LoopSuccessor = Succ; 970 971 // Because of short-circuit evaluation, the condition of the loop 972 // can span multiple basic blocks. Thus we need the "Entry" and "Exit" 973 // blocks that evaluate the condition. 974 CFGBlock* ExitConditionBlock = createBlock(false); 975 CFGBlock* EntryConditionBlock = ExitConditionBlock; 976 977 // Set the terminator for the "exit" condition block. 978 ExitConditionBlock->setTerminator(W); 979 980 // Now add the actual condition to the condition block. Because the 981 // condition itself may contain control-flow, new blocks may be created. 982 // Thus we update "Succ" after adding the condition. 983 if (Stmt* C = W->getCond()) { 984 Block = ExitConditionBlock; 985 EntryConditionBlock = addStmt(C); 986 assert(Block == EntryConditionBlock); 987 if (Block) { 988 if (!FinishBlock(EntryConditionBlock)) 989 return 0; 990 } 991 } 992 993 // The condition block is the implicit successor for the loop body as 994 // well as any code above the loop. 995 Succ = EntryConditionBlock; 996 997 // Process the loop body. 998 { 999 assert(W->getBody()); 1000 1001 // Save the current values for Block, Succ, and continue and break targets 1002 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1003 save_continue(ContinueTargetBlock), 1004 save_break(BreakTargetBlock); 1005 1006 // Create an empty block to represent the transition block for looping 1007 // back to the head of the loop. 1008 Block = 0; 1009 assert(Succ == EntryConditionBlock); 1010 Succ = createBlock(); 1011 Succ->setLoopTarget(W); 1012 ContinueTargetBlock = Succ; 1013 1014 // All breaks should go to the code following the loop. 1015 BreakTargetBlock = LoopSuccessor; 1016 1017 // NULL out Block to force lazy instantiation of blocks for the body. 1018 Block = NULL; 1019 1020 // Create the body. The returned block is the entry to the loop body. 1021 CFGBlock* BodyBlock = Visit(W->getBody()); 1022 1023 if (!BodyBlock) 1024 BodyBlock = EntryConditionBlock; // can happen for "while(...) ;" 1025 else if (Block) { 1026 if (!FinishBlock(BodyBlock)) 1027 return 0; 1028 } 1029 1030 // Add the loop body entry as a successor to the condition. 1031 ExitConditionBlock->addSuccessor(BodyBlock); 1032 } 1033 1034 // Link up the condition block with the code that follows the loop. 1035 // (the false branch). 1036 ExitConditionBlock->addSuccessor(LoopSuccessor); 1037 1038 // There can be no more statements in the condition block 1039 // since we loop back to this block. NULL out Block to force 1040 // lazy creation of another block. 1041 Block = NULL; 1042 1043 // Return the condition block, which is the dominating block for the loop. 1044 Succ = EntryConditionBlock; 1045 return EntryConditionBlock; 1046} 1047 1048CFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) { 1049 // FIXME: This isn't complete. We basically treat @throw like a return 1050 // statement. 1051 1052 // If we were in the middle of a block we stop processing that block 1053 // and reverse its statements. 1054 if (Block) { 1055 if (!FinishBlock(Block)) 1056 return 0; 1057 } 1058 1059 // Create the new block. 1060 Block = createBlock(false); 1061 1062 // The Exit block is the only successor. 1063 Block->addSuccessor(&cfg->getExit()); 1064 1065 // Add the statement to the block. This may create new blocks 1066 // if S contains control-flow (short-circuit operations). 1067 return addStmt(S); 1068} 1069 1070CFGBlock* CFGBuilder::VisitDoStmt(DoStmt* D) { 1071 // "do...while" is a control-flow statement. Thus we stop processing the 1072 // current block. 1073 1074 CFGBlock* LoopSuccessor = NULL; 1075 1076 if (Block) { 1077 if (!FinishBlock(Block)) 1078 return 0; 1079 LoopSuccessor = Block; 1080 } 1081 else LoopSuccessor = Succ; 1082 1083 // Because of short-circuit evaluation, the condition of the loop 1084 // can span multiple basic blocks. Thus we need the "Entry" and "Exit" 1085 // blocks that evaluate the condition. 1086 CFGBlock* ExitConditionBlock = createBlock(false); 1087 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1088 1089 // Set the terminator for the "exit" condition block. 1090 ExitConditionBlock->setTerminator(D); 1091 1092 // Now add the actual condition to the condition block. Because the 1093 // condition itself may contain control-flow, new blocks may be created. 1094 if (Stmt* C = D->getCond()) { 1095 Block = ExitConditionBlock; 1096 EntryConditionBlock = addStmt(C); 1097 if (Block) { 1098 if (!FinishBlock(EntryConditionBlock)) 1099 return 0; 1100 } 1101 } 1102 1103 // The condition block is the implicit successor for the loop body. 1104 Succ = EntryConditionBlock; 1105 1106 // Process the loop body. 1107 CFGBlock* BodyBlock = NULL; 1108 { 1109 assert (D->getBody()); 1110 1111 // Save the current values for Block, Succ, and continue and break targets 1112 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1113 save_continue(ContinueTargetBlock), 1114 save_break(BreakTargetBlock); 1115 1116 // All continues within this loop should go to the condition block 1117 ContinueTargetBlock = EntryConditionBlock; 1118 1119 // All breaks should go to the code following the loop. 1120 BreakTargetBlock = LoopSuccessor; 1121 1122 // NULL out Block to force lazy instantiation of blocks for the body. 1123 Block = NULL; 1124 1125 // Create the body. The returned block is the entry to the loop body. 1126 BodyBlock = Visit(D->getBody()); 1127 1128 if (!BodyBlock) 1129 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" 1130 else if (Block) { 1131 if (!FinishBlock(BodyBlock)) 1132 return 0; 1133 } 1134 1135 // Add an intermediate block between the BodyBlock and the 1136 // ExitConditionBlock to represent the "loop back" transition. 1137 // Create an empty block to represent the transition block for looping 1138 // back to the head of the loop. 1139 // FIXME: Can we do this more efficiently without adding another block? 1140 Block = NULL; 1141 Succ = BodyBlock; 1142 CFGBlock *LoopBackBlock = createBlock(); 1143 LoopBackBlock->setLoopTarget(D); 1144 1145 // Add the loop body entry as a successor to the condition. 1146 ExitConditionBlock->addSuccessor(LoopBackBlock); 1147 } 1148 1149 // Link up the condition block with the code that follows the loop. 1150 // (the false branch). 1151 ExitConditionBlock->addSuccessor(LoopSuccessor); 1152 1153 // There can be no more statements in the body block(s) 1154 // since we loop back to the body. NULL out Block to force 1155 // lazy creation of another block. 1156 Block = NULL; 1157 1158 // Return the loop body, which is the dominating block for the loop. 1159 Succ = BodyBlock; 1160 return BodyBlock; 1161} 1162 1163CFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) { 1164 // "continue" is a control-flow statement. Thus we stop processing the 1165 // current block. 1166 if (Block) { 1167 if (!FinishBlock(Block)) 1168 return 0; 1169 } 1170 1171 // Now create a new block that ends with the continue statement. 1172 Block = createBlock(false); 1173 Block->setTerminator(C); 1174 1175 // If there is no target for the continue, then we are looking at an 1176 // incomplete AST. This means the CFG cannot be constructed. 1177 if (ContinueTargetBlock) 1178 Block->addSuccessor(ContinueTargetBlock); 1179 else 1180 badCFG = true; 1181 1182 return Block; 1183} 1184 1185CFGBlock* CFGBuilder::VisitBreakStmt(BreakStmt* B) { 1186 // "break" is a control-flow statement. Thus we stop processing the 1187 // current block. 1188 if (Block) { 1189 if (!FinishBlock(Block)) 1190 return 0; 1191 } 1192 1193 // Now create a new block that ends with the continue statement. 1194 Block = createBlock(false); 1195 Block->setTerminator(B); 1196 1197 // If there is no target for the break, then we are looking at an 1198 // incomplete AST. This means that the CFG cannot be constructed. 1199 if (BreakTargetBlock) 1200 Block->addSuccessor(BreakTargetBlock); 1201 else 1202 badCFG = true; 1203 1204 1205 return Block; 1206} 1207 1208CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { 1209 // "switch" is a control-flow statement. Thus we stop processing the 1210 // current block. 1211 CFGBlock* SwitchSuccessor = NULL; 1212 1213 if (Block) { 1214 if (!FinishBlock(Block)) 1215 return 0; 1216 SwitchSuccessor = Block; 1217 } 1218 else SwitchSuccessor = Succ; 1219 1220 // Save the current "switch" context. 1221 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), 1222 save_break(BreakTargetBlock), 1223 save_default(DefaultCaseBlock); 1224 1225 // Set the "default" case to be the block after the switch statement. 1226 // If the switch statement contains a "default:", this value will 1227 // be overwritten with the block for that code. 1228 DefaultCaseBlock = SwitchSuccessor; 1229 1230 // Create a new block that will contain the switch statement. 1231 SwitchTerminatedBlock = createBlock(false); 1232 1233 // Now process the switch body. The code after the switch is the implicit 1234 // successor. 1235 Succ = SwitchSuccessor; 1236 BreakTargetBlock = SwitchSuccessor; 1237 1238 // When visiting the body, the case statements should automatically get 1239 // linked up to the switch. We also don't keep a pointer to the body, 1240 // since all control-flow from the switch goes to case/default statements. 1241 assert (Terminator->getBody() && "switch must contain a non-NULL body"); 1242 Block = NULL; 1243 CFGBlock *BodyBlock = Visit(Terminator->getBody()); 1244 if (Block) { 1245 if (!FinishBlock(BodyBlock)) 1246 return 0; 1247 } 1248 1249 // If we have no "default:" case, the default transition is to the 1250 // code following the switch body. 1251 SwitchTerminatedBlock->addSuccessor(DefaultCaseBlock); 1252 1253 // Add the terminator and condition in the switch block. 1254 SwitchTerminatedBlock->setTerminator(Terminator); 1255 assert (Terminator->getCond() && "switch condition must be non-NULL"); 1256 Block = SwitchTerminatedBlock; 1257 1258 return addStmt(Terminator->getCond()); 1259} 1260 1261CFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* Terminator) { 1262 // CaseStmts are essentially labels, so they are the 1263 // first statement in a block. 1264 1265 if (Terminator->getSubStmt()) Visit(Terminator->getSubStmt()); 1266 CFGBlock* CaseBlock = Block; 1267 if (!CaseBlock) CaseBlock = createBlock(); 1268 1269 // Cases statements partition blocks, so this is the top of 1270 // the basic block we were processing (the "case XXX:" is the label). 1271 CaseBlock->setLabel(Terminator); 1272 if (!FinishBlock(CaseBlock)) 1273 return 0; 1274 1275 // Add this block to the list of successors for the block with the 1276 // switch statement. 1277 assert (SwitchTerminatedBlock); 1278 SwitchTerminatedBlock->addSuccessor(CaseBlock); 1279 1280 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1281 Block = NULL; 1282 1283 // This block is now the implicit successor of other blocks. 1284 Succ = CaseBlock; 1285 1286 return CaseBlock; 1287} 1288 1289CFGBlock* CFGBuilder::VisitDefaultStmt(DefaultStmt* Terminator) { 1290 if (Terminator->getSubStmt()) Visit(Terminator->getSubStmt()); 1291 DefaultCaseBlock = Block; 1292 if (!DefaultCaseBlock) DefaultCaseBlock = createBlock(); 1293 1294 // Default statements partition blocks, so this is the top of 1295 // the basic block we were processing (the "default:" is the label). 1296 DefaultCaseBlock->setLabel(Terminator); 1297 if (!FinishBlock(DefaultCaseBlock)) 1298 return 0; 1299 1300 // Unlike case statements, we don't add the default block to the 1301 // successors for the switch statement immediately. This is done 1302 // when we finish processing the switch statement. This allows for 1303 // the default case (including a fall-through to the code after the 1304 // switch statement) to always be the last successor of a switch-terminated 1305 // block. 1306 1307 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1308 Block = NULL; 1309 1310 // This block is now the implicit successor of other blocks. 1311 Succ = DefaultCaseBlock; 1312 1313 return DefaultCaseBlock; 1314} 1315 1316CFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1317 // Lazily create the indirect-goto dispatch block if there isn't one 1318 // already. 1319 CFGBlock* IBlock = cfg->getIndirectGotoBlock(); 1320 1321 if (!IBlock) { 1322 IBlock = createBlock(false); 1323 cfg->setIndirectGotoBlock(IBlock); 1324 } 1325 1326 // IndirectGoto is a control-flow statement. Thus we stop processing the 1327 // current block and create a new one. 1328 if (Block) { 1329 if (!FinishBlock(Block)) 1330 return 0; 1331 } 1332 Block = createBlock(false); 1333 Block->setTerminator(I); 1334 Block->addSuccessor(IBlock); 1335 return addStmt(I->getTarget()); 1336} 1337 1338 1339} // end anonymous namespace 1340 1341/// createBlock - Constructs and adds a new CFGBlock to the CFG. The 1342/// block has no successors or predecessors. If this is the first block 1343/// created in the CFG, it is automatically set to be the Entry and Exit 1344/// of the CFG. 1345CFGBlock* CFG::createBlock() { 1346 bool first_block = begin() == end(); 1347 1348 // Create the block. 1349 Blocks.push_front(CFGBlock(NumBlockIDs++)); 1350 1351 // If this is the first block, set it as the Entry and Exit. 1352 if (first_block) Entry = Exit = &front(); 1353 1354 // Return the block. 1355 return &front(); 1356} 1357 1358/// buildCFG - Constructs a CFG from an AST. Ownership of the returned 1359/// CFG is returned to the caller. 1360CFG* CFG::buildCFG(Stmt* Statement) { 1361 CFGBuilder Builder; 1362 return Builder.buildCFG(Statement); 1363} 1364 1365/// reverseStmts - Reverses the orders of statements within a CFGBlock. 1366void CFGBlock::reverseStmts() { std::reverse(Stmts.begin(),Stmts.end()); } 1367 1368//===----------------------------------------------------------------------===// 1369// CFG: Queries for BlkExprs. 1370//===----------------------------------------------------------------------===// 1371 1372namespace { 1373 typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy; 1374} 1375 1376static void FindSubExprAssignments(Stmt* Terminator, llvm::SmallPtrSet<Expr*,50>& Set) { 1377 if (!Terminator) 1378 return; 1379 1380 for (Stmt::child_iterator I=Terminator->child_begin(), E=Terminator->child_end(); I!=E; ++I) { 1381 if (!*I) continue; 1382 1383 if (BinaryOperator* B = dyn_cast<BinaryOperator>(*I)) 1384 if (B->isAssignmentOp()) Set.insert(B); 1385 1386 FindSubExprAssignments(*I, Set); 1387 } 1388} 1389 1390static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { 1391 BlkExprMapTy* M = new BlkExprMapTy(); 1392 1393 // Look for assignments that are used as subexpressions. These are the 1394 // only assignments that we want to *possibly* register as a block-level 1395 // expression. Basically, if an assignment occurs both in a subexpression 1396 // and at the block-level, it is a block-level expression. 1397 llvm::SmallPtrSet<Expr*,50> SubExprAssignments; 1398 1399 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) 1400 for (CFGBlock::iterator BI=I->begin(), EI=I->end(); BI != EI; ++BI) 1401 FindSubExprAssignments(*BI, SubExprAssignments); 1402 1403 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { 1404 1405 // Iterate over the statements again on identify the Expr* and Stmt* at 1406 // the block-level that are block-level expressions. 1407 1408 for (CFGBlock::iterator BI=I->begin(), EI=I->end(); BI != EI; ++BI) 1409 if (Expr* Exp = dyn_cast<Expr>(*BI)) { 1410 1411 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { 1412 // Assignment expressions that are not nested within another 1413 // expression are really "statements" whose value is never 1414 // used by another expression. 1415 if (B->isAssignmentOp() && !SubExprAssignments.count(Exp)) 1416 continue; 1417 } 1418 else if (const StmtExpr* Terminator = dyn_cast<StmtExpr>(Exp)) { 1419 // Special handling for statement expressions. The last statement 1420 // in the statement expression is also a block-level expr. 1421 const CompoundStmt* C = Terminator->getSubStmt(); 1422 if (!C->body_empty()) { 1423 unsigned x = M->size(); 1424 (*M)[C->body_back()] = x; 1425 } 1426 } 1427 1428 unsigned x = M->size(); 1429 (*M)[Exp] = x; 1430 } 1431 1432 // Look at terminators. The condition is a block-level expression. 1433 1434 Stmt* S = I->getTerminatorCondition(); 1435 1436 if (S && M->find(S) == M->end()) { 1437 unsigned x = M->size(); 1438 (*M)[S] = x; 1439 } 1440 } 1441 1442 return M; 1443} 1444 1445CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) { 1446 assert(S != NULL); 1447 if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } 1448 1449 BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap); 1450 BlkExprMapTy::iterator I = M->find(S); 1451 1452 if (I == M->end()) return CFG::BlkExprNumTy(); 1453 else return CFG::BlkExprNumTy(I->second); 1454} 1455 1456unsigned CFG::getNumBlkExprs() { 1457 if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) 1458 return M->size(); 1459 else { 1460 // We assume callers interested in the number of BlkExprs will want 1461 // the map constructed if it doesn't already exist. 1462 BlkExprMap = (void*) PopulateBlkExprMap(*this); 1463 return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); 1464 } 1465} 1466 1467//===----------------------------------------------------------------------===// 1468// Cleanup: CFG dstor. 1469//===----------------------------------------------------------------------===// 1470 1471CFG::~CFG() { 1472 delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); 1473} 1474 1475//===----------------------------------------------------------------------===// 1476// CFG pretty printing 1477//===----------------------------------------------------------------------===// 1478 1479namespace { 1480 1481class VISIBILITY_HIDDEN StmtPrinterHelper : public PrinterHelper { 1482 1483 typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; 1484 StmtMapTy StmtMap; 1485 signed CurrentBlock; 1486 unsigned CurrentStmt; 1487 const LangOptions &LangOpts; 1488public: 1489 1490 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) 1491 : CurrentBlock(0), CurrentStmt(0), LangOpts(LO) { 1492 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { 1493 unsigned j = 1; 1494 for (CFGBlock::const_iterator BI = I->begin(), BEnd = I->end() ; 1495 BI != BEnd; ++BI, ++j ) 1496 StmtMap[*BI] = std::make_pair(I->getBlockID(),j); 1497 } 1498 } 1499 1500 virtual ~StmtPrinterHelper() {} 1501 1502 const LangOptions &getLangOpts() const { return LangOpts; } 1503 void setBlockID(signed i) { CurrentBlock = i; } 1504 void setStmtID(unsigned i) { CurrentStmt = i; } 1505 1506 virtual bool handledStmt(Stmt* Terminator, llvm::raw_ostream& OS) { 1507 1508 StmtMapTy::iterator I = StmtMap.find(Terminator); 1509 1510 if (I == StmtMap.end()) 1511 return false; 1512 1513 if (CurrentBlock >= 0 && I->second.first == (unsigned) CurrentBlock 1514 && I->second.second == CurrentStmt) 1515 return false; 1516 1517 OS << "[B" << I->second.first << "." << I->second.second << "]"; 1518 return true; 1519 } 1520}; 1521} // end anonymous namespace 1522 1523 1524namespace { 1525class VISIBILITY_HIDDEN CFGBlockTerminatorPrint 1526 : public StmtVisitor<CFGBlockTerminatorPrint,void> { 1527 1528 llvm::raw_ostream& OS; 1529 StmtPrinterHelper* Helper; 1530 PrintingPolicy Policy; 1531 1532public: 1533 CFGBlockTerminatorPrint(llvm::raw_ostream& os, StmtPrinterHelper* helper, 1534 const PrintingPolicy &Policy) 1535 : OS(os), Helper(helper), Policy(Policy) {} 1536 1537 void VisitIfStmt(IfStmt* I) { 1538 OS << "if "; 1539 I->getCond()->printPretty(OS,Helper,Policy); 1540 } 1541 1542 // Default case. 1543 void VisitStmt(Stmt* Terminator) { Terminator->printPretty(OS, Helper, Policy); } 1544 1545 void VisitForStmt(ForStmt* F) { 1546 OS << "for (" ; 1547 if (F->getInit()) OS << "..."; 1548 OS << "; "; 1549 if (Stmt* C = F->getCond()) C->printPretty(OS, Helper, Policy); 1550 OS << "; "; 1551 if (F->getInc()) OS << "..."; 1552 OS << ")"; 1553 } 1554 1555 void VisitWhileStmt(WhileStmt* W) { 1556 OS << "while " ; 1557 if (Stmt* C = W->getCond()) C->printPretty(OS, Helper, Policy); 1558 } 1559 1560 void VisitDoStmt(DoStmt* D) { 1561 OS << "do ... while "; 1562 if (Stmt* C = D->getCond()) C->printPretty(OS, Helper, Policy); 1563 } 1564 1565 void VisitSwitchStmt(SwitchStmt* Terminator) { 1566 OS << "switch "; 1567 Terminator->getCond()->printPretty(OS, Helper, Policy); 1568 } 1569 1570 void VisitConditionalOperator(ConditionalOperator* C) { 1571 C->getCond()->printPretty(OS, Helper, Policy); 1572 OS << " ? ... : ..."; 1573 } 1574 1575 void VisitChooseExpr(ChooseExpr* C) { 1576 OS << "__builtin_choose_expr( "; 1577 C->getCond()->printPretty(OS, Helper, Policy); 1578 OS << " )"; 1579 } 1580 1581 void VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1582 OS << "goto *"; 1583 I->getTarget()->printPretty(OS, Helper, Policy); 1584 } 1585 1586 void VisitBinaryOperator(BinaryOperator* B) { 1587 if (!B->isLogicalOp()) { 1588 VisitExpr(B); 1589 return; 1590 } 1591 1592 B->getLHS()->printPretty(OS, Helper, Policy); 1593 1594 switch (B->getOpcode()) { 1595 case BinaryOperator::LOr: 1596 OS << " || ..."; 1597 return; 1598 case BinaryOperator::LAnd: 1599 OS << " && ..."; 1600 return; 1601 default: 1602 assert(false && "Invalid logical operator."); 1603 } 1604 } 1605 1606 void VisitExpr(Expr* E) { 1607 E->printPretty(OS, Helper, Policy); 1608 } 1609}; 1610} // end anonymous namespace 1611 1612 1613static void print_stmt(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, 1614 Stmt* Terminator) { 1615 if (Helper) { 1616 // special printing for statement-expressions. 1617 if (StmtExpr* SE = dyn_cast<StmtExpr>(Terminator)) { 1618 CompoundStmt* Sub = SE->getSubStmt(); 1619 1620 if (Sub->child_begin() != Sub->child_end()) { 1621 OS << "({ ... ; "; 1622 Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); 1623 OS << " })\n"; 1624 return; 1625 } 1626 } 1627 1628 // special printing for comma expressions. 1629 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Terminator)) { 1630 if (B->getOpcode() == BinaryOperator::Comma) { 1631 OS << "... , "; 1632 Helper->handledStmt(B->getRHS(),OS); 1633 OS << '\n'; 1634 return; 1635 } 1636 } 1637 } 1638 1639 Terminator->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 1640 1641 // Expressions need a newline. 1642 if (isa<Expr>(Terminator)) OS << '\n'; 1643} 1644 1645static void print_block(llvm::raw_ostream& OS, const CFG* cfg, 1646 const CFGBlock& B, 1647 StmtPrinterHelper* Helper, bool print_edges) { 1648 1649 if (Helper) Helper->setBlockID(B.getBlockID()); 1650 1651 // Print the header. 1652 OS << "\n [ B" << B.getBlockID(); 1653 1654 if (&B == &cfg->getEntry()) 1655 OS << " (ENTRY) ]\n"; 1656 else if (&B == &cfg->getExit()) 1657 OS << " (EXIT) ]\n"; 1658 else if (&B == cfg->getIndirectGotoBlock()) 1659 OS << " (INDIRECT GOTO DISPATCH) ]\n"; 1660 else 1661 OS << " ]\n"; 1662 1663 // Print the label of this block. 1664 if (Stmt* Terminator = const_cast<Stmt*>(B.getLabel())) { 1665 1666 if (print_edges) 1667 OS << " "; 1668 1669 if (LabelStmt* L = dyn_cast<LabelStmt>(Terminator)) 1670 OS << L->getName(); 1671 else if (CaseStmt* C = dyn_cast<CaseStmt>(Terminator)) { 1672 OS << "case "; 1673 C->getLHS()->printPretty(OS, Helper, 1674 PrintingPolicy(Helper->getLangOpts())); 1675 if (C->getRHS()) { 1676 OS << " ... "; 1677 C->getRHS()->printPretty(OS, Helper, 1678 PrintingPolicy(Helper->getLangOpts())); 1679 } 1680 } 1681 else if (isa<DefaultStmt>(Terminator)) 1682 OS << "default"; 1683 else 1684 assert(false && "Invalid label statement in CFGBlock."); 1685 1686 OS << ":\n"; 1687 } 1688 1689 // Iterate through the statements in the block and print them. 1690 unsigned j = 1; 1691 1692 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; 1693 I != E ; ++I, ++j ) { 1694 1695 // Print the statement # in the basic block and the statement itself. 1696 if (print_edges) 1697 OS << " "; 1698 1699 OS << llvm::format("%3d", j) << ": "; 1700 1701 if (Helper) 1702 Helper->setStmtID(j); 1703 1704 print_stmt(OS,Helper,*I); 1705 } 1706 1707 // Print the terminator of this block. 1708 if (B.getTerminator()) { 1709 if (print_edges) 1710 OS << " "; 1711 1712 OS << " T: "; 1713 1714 if (Helper) Helper->setBlockID(-1); 1715 1716 CFGBlockTerminatorPrint TPrinter(OS, Helper, 1717 PrintingPolicy(Helper->getLangOpts())); 1718 TPrinter.Visit(const_cast<Stmt*>(B.getTerminator())); 1719 OS << '\n'; 1720 } 1721 1722 if (print_edges) { 1723 // Print the predecessors of this block. 1724 OS << " Predecessors (" << B.pred_size() << "):"; 1725 unsigned i = 0; 1726 1727 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); 1728 I != E; ++I, ++i) { 1729 1730 if (i == 8 || (i-8) == 0) 1731 OS << "\n "; 1732 1733 OS << " B" << (*I)->getBlockID(); 1734 } 1735 1736 OS << '\n'; 1737 1738 // Print the successors of this block. 1739 OS << " Successors (" << B.succ_size() << "):"; 1740 i = 0; 1741 1742 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); 1743 I != E; ++I, ++i) { 1744 1745 if (i == 8 || (i-8) % 10 == 0) 1746 OS << "\n "; 1747 1748 OS << " B" << (*I)->getBlockID(); 1749 } 1750 1751 OS << '\n'; 1752 } 1753} 1754 1755 1756/// dump - A simple pretty printer of a CFG that outputs to stderr. 1757void CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); } 1758 1759/// print - A simple pretty printer of a CFG that outputs to an ostream. 1760void CFG::print(llvm::raw_ostream &OS, const LangOptions &LO) const { 1761 StmtPrinterHelper Helper(this, LO); 1762 1763 // Print the entry block. 1764 print_block(OS, this, getEntry(), &Helper, true); 1765 1766 // Iterate through the CFGBlocks and print them one by one. 1767 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { 1768 // Skip the entry block, because we already printed it. 1769 if (&(*I) == &getEntry() || &(*I) == &getExit()) 1770 continue; 1771 1772 print_block(OS, this, *I, &Helper, true); 1773 } 1774 1775 // Print the exit block. 1776 print_block(OS, this, getExit(), &Helper, true); 1777 OS.flush(); 1778} 1779 1780/// dump - A simply pretty printer of a CFGBlock that outputs to stderr. 1781void CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const { 1782 print(llvm::errs(), cfg, LO); 1783} 1784 1785/// print - A simple pretty printer of a CFGBlock that outputs to an ostream. 1786/// Generally this will only be called from CFG::print. 1787void CFGBlock::print(llvm::raw_ostream& OS, const CFG* cfg, 1788 const LangOptions &LO) const { 1789 StmtPrinterHelper Helper(cfg, LO); 1790 print_block(OS, cfg, *this, &Helper, true); 1791} 1792 1793/// printTerminator - A simple pretty printer of the terminator of a CFGBlock. 1794void CFGBlock::printTerminator(llvm::raw_ostream &OS, 1795 const LangOptions &LO) const { 1796 CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); 1797 TPrinter.Visit(const_cast<Stmt*>(getTerminator())); 1798} 1799 1800Stmt* CFGBlock::getTerminatorCondition() { 1801 1802 if (!Terminator) 1803 return NULL; 1804 1805 Expr* E = NULL; 1806 1807 switch (Terminator->getStmtClass()) { 1808 default: 1809 break; 1810 1811 case Stmt::ForStmtClass: 1812 E = cast<ForStmt>(Terminator)->getCond(); 1813 break; 1814 1815 case Stmt::WhileStmtClass: 1816 E = cast<WhileStmt>(Terminator)->getCond(); 1817 break; 1818 1819 case Stmt::DoStmtClass: 1820 E = cast<DoStmt>(Terminator)->getCond(); 1821 break; 1822 1823 case Stmt::IfStmtClass: 1824 E = cast<IfStmt>(Terminator)->getCond(); 1825 break; 1826 1827 case Stmt::ChooseExprClass: 1828 E = cast<ChooseExpr>(Terminator)->getCond(); 1829 break; 1830 1831 case Stmt::IndirectGotoStmtClass: 1832 E = cast<IndirectGotoStmt>(Terminator)->getTarget(); 1833 break; 1834 1835 case Stmt::SwitchStmtClass: 1836 E = cast<SwitchStmt>(Terminator)->getCond(); 1837 break; 1838 1839 case Stmt::ConditionalOperatorClass: 1840 E = cast<ConditionalOperator>(Terminator)->getCond(); 1841 break; 1842 1843 case Stmt::BinaryOperatorClass: // '&&' and '||' 1844 E = cast<BinaryOperator>(Terminator)->getLHS(); 1845 break; 1846 1847 case Stmt::ObjCForCollectionStmtClass: 1848 return Terminator; 1849 } 1850 1851 return E ? E->IgnoreParens() : NULL; 1852} 1853 1854bool CFGBlock::hasBinaryBranchTerminator() const { 1855 1856 if (!Terminator) 1857 return false; 1858 1859 Expr* E = NULL; 1860 1861 switch (Terminator->getStmtClass()) { 1862 default: 1863 return false; 1864 1865 case Stmt::ForStmtClass: 1866 case Stmt::WhileStmtClass: 1867 case Stmt::DoStmtClass: 1868 case Stmt::IfStmtClass: 1869 case Stmt::ChooseExprClass: 1870 case Stmt::ConditionalOperatorClass: 1871 case Stmt::BinaryOperatorClass: 1872 return true; 1873 } 1874 1875 return E ? E->IgnoreParens() : NULL; 1876} 1877 1878 1879//===----------------------------------------------------------------------===// 1880// CFG Graphviz Visualization 1881//===----------------------------------------------------------------------===// 1882 1883 1884#ifndef NDEBUG 1885static StmtPrinterHelper* GraphHelper; 1886#endif 1887 1888void CFG::viewCFG(const LangOptions &LO) const { 1889#ifndef NDEBUG 1890 StmtPrinterHelper H(this, LO); 1891 GraphHelper = &H; 1892 llvm::ViewGraph(this,"CFG"); 1893 GraphHelper = NULL; 1894#endif 1895} 1896 1897namespace llvm { 1898template<> 1899struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { 1900 static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph, 1901 bool ShortNames) { 1902 1903#ifndef NDEBUG 1904 std::string OutSStr; 1905 llvm::raw_string_ostream Out(OutSStr); 1906 print_block(Out,Graph, *Node, GraphHelper, false); 1907 std::string& OutStr = Out.str(); 1908 1909 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 1910 1911 // Process string output to make it nicer... 1912 for (unsigned i = 0; i != OutStr.length(); ++i) 1913 if (OutStr[i] == '\n') { // Left justify 1914 OutStr[i] = '\\'; 1915 OutStr.insert(OutStr.begin()+i+1, 'l'); 1916 } 1917 1918 return OutStr; 1919#else 1920 return ""; 1921#endif 1922 } 1923}; 1924} // end namespace llvm 1925