CFG.cpp revision 55f988efeb08b84c2dd9e4c05990b88c81fe2b58
1fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek//===--- CFG.cpp - Classes for representing and building CFGs----*- C++ -*-===// 2fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// 3fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// The LLVM Compiler Infrastructure 4fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// 50bc735ffcfb223c0186419547abaa5c84482663eChris Lattner// This file is distributed under the University of Illinois Open Source 60bc735ffcfb223c0186419547abaa5c84482663eChris Lattner// License. See LICENSE.TXT for details. 7fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// 8fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek//===----------------------------------------------------------------------===// 9fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// 10fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// This file defines the CFG and CFGBuilder classes for representing and 11fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// building Control-Flow Graphs (CFGs) from ASTs. 12fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// 13fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek//===----------------------------------------------------------------------===// 14fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 15bd0487825751230a4396952b770349d2beac60b3Ted Kremenek#include "clang/Analysis/Support/SaveAndRestore.h" 16e41611aa2237d06a0ef61db4528fb2883a8defcdTed Kremenek#include "clang/Analysis/CFG.h" 17b978a441c7d8bf59e7fede938e1f3b672573b443Mike Stump#include "clang/AST/DeclCXX.h" 18c310e933a9b023a280f3aa02e5a0c75398555e13Ted Kremenek#include "clang/AST/StmtVisitor.h" 1942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek#include "clang/AST/PrettyPrinter.h" 207dba8607e59096014b7139ff20ef00870041d518Ted Kremenek#include "llvm/Support/GraphWriter.h" 216cb7c1a43b0c8f739d1f54b7fdae5ede86033496Benjamin Kramer#include "llvm/Support/Allocator.h" 226cb7c1a43b0c8f739d1f54b7fdae5ede86033496Benjamin Kramer#include "llvm/Support/Format.h" 236cb7c1a43b0c8f739d1f54b7fdae5ede86033496Benjamin Kramer#include "llvm/ADT/DenseMap.h" 246cb7c1a43b0c8f739d1f54b7fdae5ede86033496Benjamin Kramer#include "llvm/ADT/SmallPtrSet.h" 250ba497be27170c2a23c0217366f97eeecefa1ed8Ted Kremenek#include "llvm/ADT/OwningPtr.h" 2683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 27fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenekusing namespace clang; 28fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 29fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremeneknamespace { 30fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 314afa39deaa245592977136d367251ee2c173dd8dDouglas Gregorstatic SourceLocation GetEndLoc(Decl* D) { 32c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek if (VarDecl* VD = dyn_cast<VarDecl>(D)) 33c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek if (Expr* Ex = VD->getInit()) 34c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek return Ex->getSourceRange().getEnd(); 356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return D->getLocation(); 37c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek} 38852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek 39852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenekclass AddStmtChoice { 40852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenekpublic: 41852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek enum Kind { NotAlwaysAdd = 0, AlwaysAdd, AlwaysAddAsLValue }; 42852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenekpublic: 43852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AddStmtChoice(Kind kind) : k(kind) {} 44852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek bool alwaysAdd() const { return k != NotAlwaysAdd; } 45852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek bool asLValue() const { return k == AlwaysAddAsLValue; } 46852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenekprivate: 47852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek Kind k; 48852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek}; 496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 50a34ea072371154c9042ce86321d17fbb4df1f84dTed Kremenek/// CFGBuilder - This class implements CFG construction from an AST. 51fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// The builder is stateful: an instance of the builder should be used to only 52fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// construct a single CFG. 53fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 54fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// Example usage: 55fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 56fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// CFGBuilder builder; 57fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// CFG* cfg = builder.BuildAST(stmt1); 58fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 596d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// CFG construction is done via a recursive walk of an AST. We actually parse 606d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// the AST in reverse order so that the successor of a basic block is 616d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// constructed prior to its predecessor. This allows us to nicely capture 626d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// implicit fall-throughs without extra basic blocks. 63c310e933a9b023a280f3aa02e5a0c75398555e13Ted Kremenek/// 64ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamclass CFGBuilder { 65e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump ASTContext *Context; 660ba497be27170c2a23c0217366f97eeecefa1ed8Ted Kremenek llvm::OwningPtr<CFG> cfg; 67ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek 68fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek CFGBlock* Block; 69fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek CFGBlock* Succ; 70bf15b278a439d73b605ec00a8d3977ef305712f4Ted Kremenek CFGBlock* ContinueTargetBlock; 718a294713e032e4a27bae61c040abb41397952676Ted Kremenek CFGBlock* BreakTargetBlock; 72b5c13b0f4e438391b31dacb87641be7a1b990b57Ted Kremenek CFGBlock* SwitchTerminatedBlock; 73eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek CFGBlock* DefaultCaseBlock; 745d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump CFGBlock* TryTerminatedBlock; 756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 7619bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // LabelMap records the mapping from Label expressions to their blocks. 770cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek typedef llvm::DenseMap<LabelStmt*,CFGBlock*> LabelMapTy; 780cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek LabelMapTy LabelMap; 796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 806d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // A list of blocks that end with a "goto" that must be backpatched to their 816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // resolved targets upon completion of CFG construction. 824a2b8a10c4730eb2ceeec24505bef26eb7d829edTed Kremenek typedef std::vector<CFGBlock*> BackpatchBlocksTy; 830cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek BackpatchBlocksTy BackpatchBlocks; 846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8519bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // A list of labels whose address has been taken (for indirect gotos). 8619bb356317952445b03ee341c02f6147083c9eeaTed Kremenek typedef llvm::SmallPtrSet<LabelStmt*,5> LabelSetTy; 8719bb356317952445b03ee341c02f6147083c9eeaTed Kremenek LabelSetTy AddressTakenLabels; 886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 896d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stumppublic: 90ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek explicit CFGBuilder() : cfg(new CFG()), // crew a new CFG 91ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek Block(NULL), Succ(NULL), 928a294713e032e4a27bae61c040abb41397952676Ted Kremenek ContinueTargetBlock(NULL), BreakTargetBlock(NULL), 935d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL), 945d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump TryTerminatedBlock(NULL) {} 956d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 96d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // buildCFG - Used by external clients to construct the CFG. 974c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump CFG* buildCFG(const Decl *D, Stmt *Statement, ASTContext *C, bool AddEHEdges, 984c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump bool AddScopes); 996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1004f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenekprivate: 1014f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Visitors to walk an AST and construct the CFG. 102852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc); 103852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc); 104852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek CFGBlock *VisitBlockExpr(BlockExpr* E, AddStmtChoice asc); 1054f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitBreakStmt(BreakStmt *B); 106852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc); 1074f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitCaseStmt(CaseStmt *C); 108852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc); 1093fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek CFGBlock *VisitCompoundStmt(CompoundStmt *C); 110852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek CFGBlock *VisitConditionalOperator(ConditionalOperator *C, 111852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AddStmtChoice asc); 1123fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek CFGBlock *VisitContinueStmt(ContinueStmt *C); 1135d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S); 1140979d80615df97c675423de631c1b884819f4712Mike Stump CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T); 1155d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump CFGBlock *VisitCXXTryStmt(CXXTryStmt *S); 1164f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitDeclStmt(DeclStmt *DS); 1174f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitDeclSubExpr(Decl* D); 1183fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek CFGBlock *VisitDefaultStmt(DefaultStmt *D); 1193fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek CFGBlock *VisitDoStmt(DoStmt *D); 1203fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek CFGBlock *VisitForStmt(ForStmt *F); 1214f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitGotoStmt(GotoStmt* G); 1224f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitIfStmt(IfStmt *I); 1234f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I); 1244f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitLabelStmt(LabelStmt *L); 1254f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S); 1264f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S); 1274f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S); 1284f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S); 1294f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S); 1304f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitReturnStmt(ReturnStmt* R); 131852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek CFGBlock *VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, AddStmtChoice asc); 132852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc); 1334f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitSwitchStmt(SwitchStmt *S); 1344f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitWhileStmt(WhileStmt *W); 1354f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 136852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd); 137852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc); 1384f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitChildren(Stmt* S); 139cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump 140274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek // NYS == Not Yet Supported 141274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek CFGBlock* NYS() { 1424102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek badCFG = true; 1434102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek return Block; 1444102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek } 1456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 146079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump CFGBlock *StartScope(Stmt *S, CFGBlock *B) { 147079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump if (!AddScopes) 148079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump return B; 149079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump 150079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump if (B == 0) 151079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump B = createBlock(); 152079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump B->StartScope(S, cfg->getBumpVectorContext()); 153079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump return B; 154079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump } 155079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump 156079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump void EndScope(Stmt *S) { 157079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump if (!AddScopes) 158079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump return; 159079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump 160079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump if (Block == 0) 161079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump Block = createBlock(); 162079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump Block->EndScope(S, cfg->getBumpVectorContext()); 163079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump } 164079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump 1654f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek void autoCreateBlock() { if (!Block) Block = createBlock(); } 1664f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *createBlock(bool add_successor = true); 1674e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek bool FinishBlock(CFGBlock* B); 168852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek CFGBlock *addStmt(Stmt *S, AddStmtChoice asc = AddStmtChoice::AlwaysAdd) { 169852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek return Visit(S, asc); 170852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek } 171ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek 172852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek void AppendStmt(CFGBlock *B, Stmt *S, 173852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AddStmtChoice asc = AddStmtChoice::AlwaysAdd) { 174852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek B->appendStmt(S, cfg->getBumpVectorContext(), asc.asLValue()); 175ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek } 176ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek 177ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek void AddSuccessor(CFGBlock *B, CFGBlock *S) { 178ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek B->addSuccessor(S, cfg->getBumpVectorContext()); 179ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek } 1801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 181fadc9eaeac18b470b6dfcf9efcf5c4f8caea89bcTed Kremenek /// TryResult - a class representing a variant over the values 182fadc9eaeac18b470b6dfcf9efcf5c4f8caea89bcTed Kremenek /// 'true', 'false', or 'unknown'. This is returned by TryEvaluateBool, 183fadc9eaeac18b470b6dfcf9efcf5c4f8caea89bcTed Kremenek /// and is used by the CFGBuilder to decide if a branch condition 184fadc9eaeac18b470b6dfcf9efcf5c4f8caea89bcTed Kremenek /// can be decided up front during CFG construction. 185941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek class TryResult { 186941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek int X; 187941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek public: 188941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek TryResult(bool b) : X(b ? 1 : 0) {} 189941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek TryResult() : X(-1) {} 1901eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 191941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek bool isTrue() const { return X == 1; } 192941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek bool isFalse() const { return X == 0; } 193941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek bool isKnown() const { return X >= 0; } 194941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek void negate() { 195941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek assert(isKnown()); 196941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek X ^= 0x1; 197941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek } 198941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek }; 1991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 20000998a068e50945118f334c98af05ed44d7c22a6Mike Stump /// TryEvaluateBool - Try and evaluate the Stmt and return 0 or 1 20100998a068e50945118f334c98af05ed44d7c22a6Mike Stump /// if we can evaluate to a known value, otherwise return -1. 202941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek TryResult TryEvaluateBool(Expr *S) { 20300998a068e50945118f334c98af05ed44d7c22a6Mike Stump Expr::EvalResult Result; 2049983cc110422a2e976191a0ce6ac4f1d7b634cc0Douglas Gregor if (!S->isTypeDependent() && !S->isValueDependent() && 2059983cc110422a2e976191a0ce6ac4f1d7b634cc0Douglas Gregor S->Evaluate(Result, *Context) && Result.Val.isInt()) 206fadc9eaeac18b470b6dfcf9efcf5c4f8caea89bcTed Kremenek return Result.Val.getInt().getBoolValue(); 207941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek 208941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek return TryResult(); 20900998a068e50945118f334c98af05ed44d7c22a6Mike Stump } 21000998a068e50945118f334c98af05ed44d7c22a6Mike Stump 2114102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek bool badCFG; 2124c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump 2134c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump // True iff EH edges on CallExprs should be added to the CFG. 2144c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump bool AddEHEdges; 2154c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump 2164c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump // True iff scope start and scope end notes should be added to the CFG. 217079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump bool AddScopes; 218d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek}; 2196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 220898574e7496ba8fd76290079d3a9d06954992734Douglas Gregor// FIXME: Add support for dependent-sized array types in C++? 221898574e7496ba8fd76290079d3a9d06954992734Douglas Gregor// Does it even make sense to build a CFG for an uninstantiated template? 222610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenekstatic VariableArrayType* FindVA(Type* t) { 223610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek while (ArrayType* vt = dyn_cast<ArrayType>(t)) { 224610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek if (VariableArrayType* vat = dyn_cast<VariableArrayType>(vt)) 225610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek if (vat->getSizeExpr()) 226610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek return vat; 2276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 228610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek t = vt->getElementType().getTypePtr(); 229610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek } 2306d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 231610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek return 0; 232610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek} 2336d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an 2356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// arbitrary statement. Examples include a single expression or a function 2366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// body (compound statement). The ownership of the returned CFG is 2376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// transferred to the caller. If CFG construction fails, this method returns 2386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// NULL. 239b978a441c7d8bf59e7fede938e1f3b672573b443Mike StumpCFG* CFGBuilder::buildCFG(const Decl *D, Stmt* Statement, ASTContext* C, 24055f988efeb08b84c2dd9e4c05990b88c81fe2b58Mike Stump bool addehedges, bool AddScopes) { 24155f988efeb08b84c2dd9e4c05990b88c81fe2b58Mike Stump AddEHEdges = addehedges; 242e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump Context = C; 2430ba497be27170c2a23c0217366f97eeecefa1ed8Ted Kremenek assert(cfg.get()); 2444f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (!Statement) 2454f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return NULL; 246d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 247079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump this->AddScopes = AddScopes; 2484102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek badCFG = false; 2496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2506d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Create an empty block that will serve as the exit block for the CFG. Since 2516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // this is the first block added to the CFG, it will be implicitly registered 2526d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // as the exit block. 25349af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Succ = createBlock(); 254ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek assert(Succ == &cfg->getExit()); 25549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Block = NULL; // the EXIT block is empty. Create all other blocks lazily. 2566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 257d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Visit the statements and create the CFG. 2584f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* B = addStmt(Statement); 259b978a441c7d8bf59e7fede938e1f3b672573b443Mike Stump 260b978a441c7d8bf59e7fede938e1f3b672573b443Mike Stump if (const CXXConstructorDecl *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) { 261b978a441c7d8bf59e7fede938e1f3b672573b443Mike Stump // FIXME: Add code for base initializers and member initializers. 262b978a441c7d8bf59e7fede938e1f3b672573b443Mike Stump (void)CD; 263b978a441c7d8bf59e7fede938e1f3b672573b443Mike Stump } 2640ba497be27170c2a23c0217366f97eeecefa1ed8Ted Kremenek if (!B) 2650ba497be27170c2a23c0217366f97eeecefa1ed8Ted Kremenek B = Succ; 2666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2670d99ecf1d8b9c72f2c4130f5f1be6cf13556b031Ted Kremenek if (B) { 2686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Finalize the last constructed block. This usually involves reversing the 2696d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // order of the statements in the block. 27049af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek if (Block) FinishBlock(B); 2716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Backpatch the gotos whose label -> block mappings we didn't know when we 2736d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // encountered them. 2746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(), 275d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek E = BackpatchBlocks.end(); I != E; ++I ) { 2766d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 277d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* B = *I; 278d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek GotoStmt* G = cast<GotoStmt>(B->getTerminator()); 279d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); 280d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 281d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // If there is no target for the goto, then we are looking at an 282d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // incomplete AST. Handle this by not registering a successor. 283d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (LI == LabelMap.end()) continue; 2846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 285ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(B, LI->second); 28619bb356317952445b03ee341c02f6147083c9eeaTed Kremenek } 2876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 28819bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // Add successors to the Indirect Goto Dispatch block (if we have one). 28919bb356317952445b03ee341c02f6147083c9eeaTed Kremenek if (CFGBlock* B = cfg->getIndirectGotoBlock()) 29019bb356317952445b03ee341c02f6147083c9eeaTed Kremenek for (LabelSetTy::iterator I = AddressTakenLabels.begin(), 29119bb356317952445b03ee341c02f6147083c9eeaTed Kremenek E = AddressTakenLabels.end(); I != E; ++I ) { 29219bb356317952445b03ee341c02f6147083c9eeaTed Kremenek 29319bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // Lookup the target block. 29419bb356317952445b03ee341c02f6147083c9eeaTed Kremenek LabelMapTy::iterator LI = LabelMap.find(*I); 29519bb356317952445b03ee341c02f6147083c9eeaTed Kremenek 29619bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // If there is no target block that contains label, then we are looking 29719bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // at an incomplete AST. Handle this by not registering a successor. 29819bb356317952445b03ee341c02f6147083c9eeaTed Kremenek if (LI == LabelMap.end()) continue; 2996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 300ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(B, LI->second); 30119bb356317952445b03ee341c02f6147083c9eeaTed Kremenek } 3026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 30394b3316ee37743cb60bf552d5616b03d17e277daTed Kremenek Succ = B; 30494b3316ee37743cb60bf552d5616b03d17e277daTed Kremenek } 3056d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3066d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Create an empty entry block that has no predecessors. 307322f58d3830da13b419646c071e3ab801518a09cTed Kremenek cfg->setEntry(createBlock()); 3086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 309da9b30ea415af1de659524c28793e2597342f6e8Ted Kremenek return badCFG ? NULL : cfg.take(); 310d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 3116d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 312d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek/// createBlock - Used to lazily create blocks that are connected 313d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek/// to the current (global) succcessor. 3146d9828c82c9321f042ab416fd2ffaa3034347d45Mike StumpCFGBlock* CFGBuilder::createBlock(bool add_successor) { 3159438252ad2ecae5338df565ca33c6969e4fbfa41Ted Kremenek CFGBlock* B = cfg->createBlock(); 3164f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (add_successor && Succ) 317ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(B, Succ); 318d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek return B; 319d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 3206d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3216c2497248bc4f7fd8e5fb0a206d20abbf0e16645Ted Kremenek/// FinishBlock - "Finalize" the block by checking if we have a bad CFG. 3224e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenekbool CFGBuilder::FinishBlock(CFGBlock* B) { 3234e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (badCFG) 3244e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return false; 3254e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek 3264f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek assert(B); 3274e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return true; 328d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 329d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 3304f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek/// Visit - Walk the subtree of a statement and add extra 3316d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// blocks for ternary operators, &&, and ||. We also process "," and 3326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// DeclStmts (which may contain nested control-flow). 333852274d4257134906995cb252fb3dfd2d71deae8Ted KremenekCFGBlock* CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) { 3344f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenektryAgain: 3354f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek switch (S->getStmtClass()) { 3364f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek default: 337852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek return VisitStmt(S, asc); 3384f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3394f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::AddrLabelExprClass: 340852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc); 3411eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3424f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::BinaryOperatorClass: 343852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek return VisitBinaryOperator(cast<BinaryOperator>(S), asc); 3441eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3454f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::BlockExprClass: 346852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek return VisitBlockExpr(cast<BlockExpr>(S), asc); 3474f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3484f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::BreakStmtClass: 3494f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitBreakStmt(cast<BreakStmt>(S)); 3501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3514f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::CallExprClass: 352852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek return VisitCallExpr(cast<CallExpr>(S), asc); 3531eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3544f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::CaseStmtClass: 3554f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitCaseStmt(cast<CaseStmt>(S)); 3564f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3574f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ChooseExprClass: 358852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek return VisitChooseExpr(cast<ChooseExpr>(S), asc); 3591eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3604f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::CompoundStmtClass: 3614f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitCompoundStmt(cast<CompoundStmt>(S)); 3621eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3634f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ConditionalOperatorClass: 364852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek return VisitConditionalOperator(cast<ConditionalOperator>(S), asc); 3651eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3664f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ContinueStmtClass: 3674f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitContinueStmt(cast<ContinueStmt>(S)); 3681eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 369021c8afbab95c71fbdd95c0b5cea36fd316281f9Ted Kremenek case Stmt::CXXCatchStmtClass: 370021c8afbab95c71fbdd95c0b5cea36fd316281f9Ted Kremenek return VisitCXXCatchStmt(cast<CXXCatchStmt>(S)); 371021c8afbab95c71fbdd95c0b5cea36fd316281f9Ted Kremenek 372021c8afbab95c71fbdd95c0b5cea36fd316281f9Ted Kremenek case Stmt::CXXThrowExprClass: 373021c8afbab95c71fbdd95c0b5cea36fd316281f9Ted Kremenek return VisitCXXThrowExpr(cast<CXXThrowExpr>(S)); 374021c8afbab95c71fbdd95c0b5cea36fd316281f9Ted Kremenek 375021c8afbab95c71fbdd95c0b5cea36fd316281f9Ted Kremenek case Stmt::CXXTryStmtClass: 376021c8afbab95c71fbdd95c0b5cea36fd316281f9Ted Kremenek return VisitCXXTryStmt(cast<CXXTryStmt>(S)); 377021c8afbab95c71fbdd95c0b5cea36fd316281f9Ted Kremenek 3784f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::DeclStmtClass: 3794f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitDeclStmt(cast<DeclStmt>(S)); 3801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3814f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::DefaultStmtClass: 3824f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitDefaultStmt(cast<DefaultStmt>(S)); 3831eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3844f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::DoStmtClass: 3854f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitDoStmt(cast<DoStmt>(S)); 3861eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3874f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ForStmtClass: 3884f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitForStmt(cast<ForStmt>(S)); 3891eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3904f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::GotoStmtClass: 3914f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitGotoStmt(cast<GotoStmt>(S)); 3921eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3934f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::IfStmtClass: 3944f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitIfStmt(cast<IfStmt>(S)); 3951eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3964f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::IndirectGotoStmtClass: 3974f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S)); 3981eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 3994f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::LabelStmtClass: 4004f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitLabelStmt(cast<LabelStmt>(S)); 4011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4024f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ObjCAtCatchStmtClass: 4031eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S)); 4041eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4054f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ObjCAtSynchronizedStmtClass: 4064f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S)); 4071eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4084f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ObjCAtThrowStmtClass: 4094f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S)); 4101eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4114f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ObjCAtTryStmtClass: 4124f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S)); 4131eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4144f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ObjCForCollectionStmtClass: 4154f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S)); 4161eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4174f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ParenExprClass: 4184f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek S = cast<ParenExpr>(S)->getSubExpr(); 4191eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump goto tryAgain; 4201eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4214f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::NullStmtClass: 4224f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return Block; 4231eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4244f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ReturnStmtClass: 4254f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitReturnStmt(cast<ReturnStmt>(S)); 4261eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4274f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::SizeOfAlignOfExprClass: 428852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek return VisitSizeOfAlignOfExpr(cast<SizeOfAlignOfExpr>(S), asc); 4291eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4304f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::StmtExprClass: 431852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek return VisitStmtExpr(cast<StmtExpr>(S), asc); 4321eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4334f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::SwitchStmtClass: 4344f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitSwitchStmt(cast<SwitchStmt>(S)); 4351eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4364f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::WhileStmtClass: 4374f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitWhileStmt(cast<WhileStmt>(S)); 4384f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } 4394f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 4401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 441852274d4257134906995cb252fb3dfd2d71deae8Ted KremenekCFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) { 442852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek if (asc.alwaysAdd()) { 4434f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek autoCreateBlock(); 444852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AppendStmt(Block, S, asc); 4456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 4461eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4474f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitChildren(S); 4484f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 4496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 4504f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek/// VisitChildren - Visit the children of a Stmt. 4514f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitChildren(Stmt* Terminator) { 4524f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *B = Block; 4534f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek for (Stmt::child_iterator I = Terminator->child_begin(), 4544f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek E = Terminator->child_end(); I != E; ++I) { 4554f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (*I) B = Visit(*I); 4566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 4574f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return B; 4584f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 4591eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 460852274d4257134906995cb252fb3dfd2d71deae8Ted KremenekCFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, 461852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AddStmtChoice asc) { 4624f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek AddressTakenLabels.insert(A->getLabel()); 4636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 464852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek if (asc.alwaysAdd()) { 4654f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek autoCreateBlock(); 466852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AppendStmt(Block, A, asc); 4676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 4686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 4694f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return Block; 4704f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 4711eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 472852274d4257134906995cb252fb3dfd2d71deae8Ted KremenekCFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, 473852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AddStmtChoice asc) { 4744f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (B->isLogicalOp()) { // && or || 4754f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 476852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AppendStmt(ConfluenceBlock, B, asc); 4771eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4784f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (!FinishBlock(ConfluenceBlock)) 4794f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return 0; 4801eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4814f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // create the block evaluating the LHS 4824f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* LHSBlock = createBlock(false); 4834f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LHSBlock->setTerminator(B); 4841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 4854f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // create the block evaluating the RHS 4864f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Succ = ConfluenceBlock; 4874f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block = NULL; 4884f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* RHSBlock = addStmt(B->getRHS()); 4894f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (!FinishBlock(RHSBlock)) 4904f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return 0; 4911eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 49200998a068e50945118f334c98af05ed44d7c22a6Mike Stump // See if this is a known constant. 493941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek TryResult KnownVal = TryEvaluateBool(B->getLHS()); 494941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek if (KnownVal.isKnown() && (B->getOpcode() == BinaryOperator::LOr)) 495941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek KnownVal.negate(); 49600998a068e50945118f334c98af05ed44d7c22a6Mike Stump 4974f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Now link the LHSBlock with RHSBlock. 4984f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (B->getOpcode() == BinaryOperator::LOr) { 499ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 500ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 5011eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } else { 5026db0ad32fa0987ff76d4c41393991ef4b6895ea3Ted Kremenek assert(B->getOpcode() == BinaryOperator::LAnd); 503ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 504ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 50519bb356317952445b03ee341c02f6147083c9eeaTed Kremenek } 5061eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5074f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Generate the blocks for evaluating the LHS. 5084f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block = LHSBlock; 5094f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return addStmt(B->getLHS()); 5101eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 5114f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek else if (B->getOpcode() == BinaryOperator::Comma) { // , 5126dc534ecc19a045ebcfe93eefa45da509968e888Ted Kremenek autoCreateBlock(); 513852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AppendStmt(Block, B, asc); 5144f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek addStmt(B->getRHS()); 5154f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return addStmt(B->getLHS()); 5166d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 5171eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 518852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek return VisitStmt(B, asc); 5194f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 5206d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 521852274d4257134906995cb252fb3dfd2d71deae8Ted KremenekCFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) { 522852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek if (asc.alwaysAdd()) { 523721903eca33f6115296083aed17685eaa73d3e8cTed Kremenek autoCreateBlock(); 524852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AppendStmt(Block, E, asc); 525721903eca33f6115296083aed17685eaa73d3e8cTed Kremenek } 526721903eca33f6115296083aed17685eaa73d3e8cTed Kremenek return Block; 5274f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 528cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump 5294f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { 5304f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // "break" is a control-flow statement. Thus we stop processing the current 5314f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // block. 5324f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (Block && !FinishBlock(Block)) 5334f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return 0; 5341eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5354f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Now create a new block that ends with the break statement. 5364f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block = createBlock(false); 5374f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block->setTerminator(B); 5381eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5394f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // If there is no target for the break, then we are looking at an incomplete 5404f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // AST. This means that the CFG cannot be constructed. 5414f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (BreakTargetBlock) 542ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(Block, BreakTargetBlock); 5434f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek else 5444f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek badCFG = true; 5451eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5461eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5474f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return Block; 5484f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 5491eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 5504c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stumpstatic bool CanThrow(Expr *E) { 5514c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump QualType Ty = E->getType(); 5524c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump if (Ty->isFunctionPointerType()) 5534c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump Ty = Ty->getAs<PointerType>()->getPointeeType(); 5544c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump else if (Ty->isBlockPointerType()) 5554c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump Ty = Ty->getAs<BlockPointerType>()->getPointeeType(); 5564c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump 5574c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump const FunctionType *FT = Ty->getAs<FunctionType>(); 5584c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump if (FT) { 5594c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT)) 5604c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump if (Proto->hasEmptyExceptionSpec()) 5614c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump return false; 5624c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump } 5634c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump return true; 5644c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump} 5654c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump 566852274d4257134906995cb252fb3dfd2d71deae8Ted KremenekCFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { 5674f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // If this is a call to a no-return function, this stops the block here. 5682455636163fdd18581d7fdae816433f886d88213Mike Stump bool NoReturn = false; 5692455636163fdd18581d7fdae816433f886d88213Mike Stump if (C->getCallee()->getType().getNoReturnAttr()) { 5702455636163fdd18581d7fdae816433f886d88213Mike Stump NoReturn = true; 5712455636163fdd18581d7fdae816433f886d88213Mike Stump } 5722455636163fdd18581d7fdae816433f886d88213Mike Stump 5734c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump bool AddEHEdge = false; 574079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump 575079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump // Languages without exceptions are assumed to not throw. 576079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump if (Context->getLangOptions().Exceptions) { 5774c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump if (AddEHEdges) 5784c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump AddEHEdge = true; 579079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump } 580079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump 581079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump if (FunctionDecl *FD = C->getDirectCallee()) { 5822455636163fdd18581d7fdae816433f886d88213Mike Stump if (FD->hasAttr<NoReturnAttr>()) 5832455636163fdd18581d7fdae816433f886d88213Mike Stump NoReturn = true; 584079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump if (FD->hasAttr<NoThrowAttr>()) 5854c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump AddEHEdge = false; 586079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump } 5872455636163fdd18581d7fdae816433f886d88213Mike Stump 5884c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump if (!CanThrow(C->getCallee())) 5894c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump AddEHEdge = false; 5904c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump 5914c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump if (!NoReturn && !AddEHEdge) 592852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek return VisitStmt(C, asc); 5931eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 594079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump if (Block) { 595079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump Succ = Block; 596079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump if (!FinishBlock(Block)) 597079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump return 0; 598079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump } 5991eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 600079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump Block = createBlock(!NoReturn); 601852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AppendStmt(Block, C, asc); 6022455636163fdd18581d7fdae816433f886d88213Mike Stump 603079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump if (NoReturn) { 604079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump // Wire this to the exit block directly. 605079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump AddSuccessor(Block, &cfg->getExit()); 606079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump } 6074c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump if (AddEHEdge) { 608079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump // Add exceptional edges. 609079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump if (TryTerminatedBlock) 610079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump AddSuccessor(Block, TryTerminatedBlock); 611079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump else 612079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump AddSuccessor(Block, &cfg->getExit()); 613079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump } 6141eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6152455636163fdd18581d7fdae816433f886d88213Mike Stump return VisitChildren(C); 616d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 617d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 618852274d4257134906995cb252fb3dfd2d71deae8Ted KremenekCFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C, 619852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AddStmtChoice asc) { 6203fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 621852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AppendStmt(ConfluenceBlock, C, asc); 6223fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek if (!FinishBlock(ConfluenceBlock)) 6233fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek return 0; 6241eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6253fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek Succ = ConfluenceBlock; 6263fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek Block = NULL; 6274f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* LHSBlock = addStmt(C->getLHS()); 6283fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek if (!FinishBlock(LHSBlock)) 6293fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek return 0; 6301eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6313fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek Succ = ConfluenceBlock; 6323fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek Block = NULL; 6334f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* RHSBlock = addStmt(C->getRHS()); 6343fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek if (!FinishBlock(RHSBlock)) 6353fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek return 0; 6361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6373fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek Block = createBlock(false); 63800998a068e50945118f334c98af05ed44d7c22a6Mike Stump // See if this is a known constant. 639941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek const TryResult& KnownVal = TryEvaluateBool(C->getCond()); 640ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); 641ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); 6423fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek Block->setTerminator(C); 6431eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump return addStmt(C->getCond()); 6443fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek} 6451eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6461eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 6471eb4433ac451dc16f4133a88af2d002ac26c58efMike StumpCFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) { 648079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump EndScope(C); 649079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump 6501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump CFGBlock* LastBlock = Block; 6514f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 6524f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); 6534f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek I != E; ++I ) { 6544f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LastBlock = addStmt(*I); 6551eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 656e8d6d2b9a2c5d3f0e7e0f88f54f1711bbc6c6f78Ted Kremenek if (badCFG) 657e8d6d2b9a2c5d3f0e7e0f88f54f1711bbc6c6f78Ted Kremenek return NULL; 6581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump } 659079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump 660079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump LastBlock = StartScope(C, LastBlock); 661079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump 6624f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return LastBlock; 6634f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 6641eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 665852274d4257134906995cb252fb3dfd2d71deae8Ted KremenekCFGBlock *CFGBuilder::VisitConditionalOperator(ConditionalOperator *C, 666852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AddStmtChoice asc) { 667f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // Create the confluence block that will "merge" the results of the ternary 668f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // expression. 669f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 670852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AppendStmt(ConfluenceBlock, C, asc); 671f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek if (!FinishBlock(ConfluenceBlock)) 672f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek return 0; 6731eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 674f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // Create a block for the LHS expression if there is an LHS expression. A 675f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // GCC extension allows LHS to be NULL, causing the condition to be the 676f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // value that is returned instead. 677f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // e.g: x ?: y is shorthand for: x ? x : y; 678f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek Succ = ConfluenceBlock; 679f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek Block = NULL; 680f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek CFGBlock* LHSBlock = NULL; 681f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek if (C->getLHS()) { 6824f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LHSBlock = addStmt(C->getLHS()); 683f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek if (!FinishBlock(LHSBlock)) 684f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek return 0; 685f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek Block = NULL; 686f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek } 6871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 688f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // Create the block for the RHS expression. 689f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek Succ = ConfluenceBlock; 6904f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* RHSBlock = addStmt(C->getRHS()); 691f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek if (!FinishBlock(RHSBlock)) 692f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek return 0; 6931eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 694f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // Create the block that will contain the condition. 695f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek Block = createBlock(false); 6961eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 69700998a068e50945118f334c98af05ed44d7c22a6Mike Stump // See if this is a known constant. 698941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek const TryResult& KnownVal = TryEvaluateBool(C->getCond()); 699e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (LHSBlock) { 700ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); 701e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump } else { 702941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek if (KnownVal.isFalse()) { 703e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // If we know the condition is false, add NULL as the successor for 704e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // the block containing the condition. In this case, the confluence 705e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // block will have just one predecessor. 706ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(Block, 0); 707941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek assert(ConfluenceBlock->pred_size() == 1); 708e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump } else { 709e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // If we have no LHS expression, add the ConfluenceBlock as a direct 710e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // successor for the block containing the condition. Moreover, we need to 711e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // reverse the order of the predecessors in the ConfluenceBlock because 712e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // the RHSBlock will have been added to the succcessors already, and we 713e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // want the first predecessor to the the block containing the expression 714e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // for the case when the ternary expression evaluates to true. 715ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(Block, ConfluenceBlock); 716941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek assert(ConfluenceBlock->pred_size() == 2); 717e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump std::reverse(ConfluenceBlock->pred_begin(), 718e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump ConfluenceBlock->pred_end()); 719e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump } 720f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek } 7211eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 722ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); 723f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek Block->setTerminator(C); 724f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek return addStmt(C->getCond()); 725f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek} 726f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek 7274f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) { 7284f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek autoCreateBlock(); 7296d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 7304f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (DS->isSingleDecl()) { 731ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AppendStmt(Block, DS); 7324f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitDeclSubExpr(DS->getSingleDecl()); 733d34066c224f782056c18f154abe04ef590473fd9Ted Kremenek } 7341eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7354f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *B = 0; 7361eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7374f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy. 7384f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek typedef llvm::SmallVector<Decl*,10> BufTy; 7394f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek BufTy Buf(DS->decl_begin(), DS->decl_end()); 7401eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7414f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek for (BufTy::reverse_iterator I = Buf.rbegin(), E = Buf.rend(); I != E; ++I) { 7424f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Get the alignment of the new DeclStmt, padding out to >=8 bytes. 7434f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8 7444f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek ? 8 : llvm::AlignOf<DeclStmt>::Alignment; 7451eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7464f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Allocate the DeclStmt using the BumpPtrAllocator. It will get 7474f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // automatically freed with the CFG. 7484f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek DeclGroupRef DG(*I); 7494f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Decl *D = *I; 7501eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A); 7514f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); 7521eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7534f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Append the fake DeclStmt to block. 754ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AppendStmt(Block, DSNew); 7554f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek B = VisitDeclSubExpr(D); 7564f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } 7571eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7581eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump return B; 7594f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 7601eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7614f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek/// VisitDeclSubExpr - Utility method to add block-level expressions for 7624f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek/// initializers in Decls. 7634f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitDeclSubExpr(Decl* D) { 7644f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek assert(Block); 765d34066c224f782056c18f154abe04ef590473fd9Ted Kremenek 7664f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek VarDecl *VD = dyn_cast<VarDecl>(D); 7671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7684f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (!VD) 7694f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return Block; 7701eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7714f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Expr *Init = VD->getInit(); 7721eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7734f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (Init) { 7744f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Optimization: Don't create separate block-level statements for literals. 7754f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek switch (Init->getStmtClass()) { 7764f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::IntegerLiteralClass: 7774f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::CharacterLiteralClass: 7784f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::StringLiteralClass: 7794f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek break; 7804f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek default: 781852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek Block = addStmt(Init, 782852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek VD->getType()->isReferenceType() 783852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek ? AddStmtChoice::AlwaysAddAsLValue 784852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek : AddStmtChoice::AlwaysAdd); 7854f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } 7864f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } 7871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7884f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // If the type of VD is a VLA, then we must process its size expressions. 7894f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek for (VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); VA != 0; 7904f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek VA = FindVA(VA->getElementType().getTypePtr())) 7914f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block = addStmt(VA->getSizeExpr()); 7921eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 7934f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return Block; 794d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 795fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 796d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { 7976d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // We may see an if statement in the middle of a basic block, or it may be the 7986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // first statement we are processing. In either case, we create a new basic 7996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block. First, we create the blocks for the then...else statements, and 8006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // then we create the block containing the if statement. If we were in the 8016c2497248bc4f7fd8e5fb0a206d20abbf0e16645Ted Kremenek // middle of a block, we stop processing that block. That block is then the 8026c2497248bc4f7fd8e5fb0a206d20abbf0e16645Ted Kremenek // implicit successor for the "then" and "else" clauses. 8036d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8046d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // The block we were proccessing is now finished. Make it the successor 8056d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block. 8066d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (Block) { 807d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Succ = Block; 8084e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 8094e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 810c310e933a9b023a280f3aa02e5a0c75398555e13Ted Kremenek } 8116d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 812b6f1d782e0dc5fad138a17e6aa0ff6f9bc4788c6Ted Kremenek // Process the false branch. 813d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* ElseBlock = Succ; 8146d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 815d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Stmt* Else = I->getElse()) { 816d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> sv(Succ); 8176d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 818d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // NULL out Block so that the recursive call to Visit will 8196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // create a new basic block. 820d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = NULL; 8214f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek ElseBlock = addStmt(Else); 8226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 823b6f7b72047b3fd3f96a5040e1e4d520a9dea01cdTed Kremenek if (!ElseBlock) // Can occur when the Else body has all NullStmts. 824b6f7b72047b3fd3f96a5040e1e4d520a9dea01cdTed Kremenek ElseBlock = sv.get(); 8254e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek else if (Block) { 8264e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(ElseBlock)) 8274e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 8284e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 829c310e933a9b023a280f3aa02e5a0c75398555e13Ted Kremenek } 8306d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 831b6f1d782e0dc5fad138a17e6aa0ff6f9bc4788c6Ted Kremenek // Process the true branch. 832d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* ThenBlock; 833d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek { 834d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Stmt* Then = I->getThen(); 8356db0ad32fa0987ff76d4c41393991ef4b6895ea3Ted Kremenek assert(Then); 836d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> sv(Succ); 8376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block = NULL; 8384f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek ThenBlock = addStmt(Then); 8396d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 840dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek if (!ThenBlock) { 841dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek // We can reach here if the "then" body has all NullStmts. 842dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek // Create an empty block so we can distinguish between true and false 843dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek // branches in path-sensitive analyses. 844dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek ThenBlock = createBlock(false); 845ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(ThenBlock, sv.get()); 8466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else if (Block) { 8474e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(ThenBlock)) 8484e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 8496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 8500cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek } 851d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 8526d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now create a new block containing the if statement. 853d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(false); 8546d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 855d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Set the terminator of the new block to the If statement. 856d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->setTerminator(I); 8576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 85800998a068e50945118f334c98af05ed44d7c22a6Mike Stump // See if this is a known constant. 859941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek const TryResult &KnownVal = TryEvaluateBool(I->getCond()); 86000998a068e50945118f334c98af05ed44d7c22a6Mike Stump 861d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Now add the successors. 862ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(Block, KnownVal.isFalse() ? NULL : ThenBlock); 863ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(Block, KnownVal.isTrue()? NULL : ElseBlock); 8646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8656d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Add the condition as the last statement in the new block. This may create 8666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // new blocks as the condition may contain control-flow. Any newly created 8676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // blocks will be pointed to be "Block". 86861dfbecd8e6181b2ba42ffb5feede27a2bab3b8aTed Kremenek Block = addStmt(I->getCond()); 86961dfbecd8e6181b2ba42ffb5feede27a2bab3b8aTed Kremenek 87061dfbecd8e6181b2ba42ffb5feede27a2bab3b8aTed Kremenek // Finally, if the IfStmt contains a condition variable, add both the IfStmt 87161dfbecd8e6181b2ba42ffb5feede27a2bab3b8aTed Kremenek // and the condition variable initialization to the CFG. 87261dfbecd8e6181b2ba42ffb5feede27a2bab3b8aTed Kremenek if (VarDecl *VD = I->getConditionVariable()) { 87361dfbecd8e6181b2ba42ffb5feede27a2bab3b8aTed Kremenek if (Expr *Init = VD->getInit()) { 87461dfbecd8e6181b2ba42ffb5feede27a2bab3b8aTed Kremenek autoCreateBlock(); 87561dfbecd8e6181b2ba42ffb5feede27a2bab3b8aTed Kremenek AppendStmt(Block, I, AddStmtChoice::AlwaysAdd); 87661dfbecd8e6181b2ba42ffb5feede27a2bab3b8aTed Kremenek addStmt(Init); 87761dfbecd8e6181b2ba42ffb5feede27a2bab3b8aTed Kremenek } 87861dfbecd8e6181b2ba42ffb5feede27a2bab3b8aTed Kremenek } 87961dfbecd8e6181b2ba42ffb5feede27a2bab3b8aTed Kremenek 88061dfbecd8e6181b2ba42ffb5feede27a2bab3b8aTed Kremenek return Block; 881d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 8826d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 884d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitReturnStmt(ReturnStmt* R) { 8856c2497248bc4f7fd8e5fb0a206d20abbf0e16645Ted Kremenek // If we were in the middle of a block we stop processing that block. 886d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // 8876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // NOTE: If a "return" appears in the middle of a block, this means that the 8886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // code afterwards is DEAD (unreachable). We still keep a basic block 8896d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // for that code; a simple "mark-and-sweep" from the entry block will be 8906d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // able to report such dead blocks. 8916c2497248bc4f7fd8e5fb0a206d20abbf0e16645Ted Kremenek if (Block) 8926c2497248bc4f7fd8e5fb0a206d20abbf0e16645Ted Kremenek FinishBlock(Block); 893d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 894d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Create the new block. 895d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(false); 8966d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 897d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // The Exit block is the only successor. 898ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(Block, &cfg->getExit()); 8996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Add the return statement to the block. This may create new blocks if R 9016d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // contains control-flow (short-circuit operations). 902852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek return VisitStmt(R, AddStmtChoice::AlwaysAdd); 903d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 9040cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek 905d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt* L) { 906d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Get the block of the labeled statement. Add it to our map. 9074f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek addStmt(L->getSubStmt()); 9082677ea871a25aa79f9db360f6ed10584c02267adTed Kremenek CFGBlock* LabelBlock = Block; 9096d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9104f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (!LabelBlock) // This can happen when the body is empty, i.e. 9114f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LabelBlock = createBlock(); // scopes that only contains NullStmts. 9126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9134f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek assert(LabelMap.find(L) == LabelMap.end() && "label already in map"); 914d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LabelMap[ L ] = LabelBlock; 9156d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9166d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Labels partition blocks, so this is the end of the basic block we were 9176d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // processing (L is the block's label). Because this is label (and we have 9186d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // already processed the substatement) there is no extra control-flow to worry 9196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // about. 9209cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek LabelBlock->setLabel(L); 9214e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(LabelBlock)) 9224e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 9236d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9246d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // We set Block to NULL to allow lazy creation of a new block (if necessary); 925d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = NULL; 9266d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 927d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // This block is now the implicit successor of other blocks. 928d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Succ = LabelBlock; 9296d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 930d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek return LabelBlock; 931d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 93231dcd3c8c4df5a656f58f50ea73afc177c101c67Ted Kremenek 933d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) { 9346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Goto is a control-flow statement. Thus we stop processing the current 9356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block and create a new one. 9364f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (Block) 9374f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek FinishBlock(Block); 9384f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 939d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(false); 940d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->setTerminator(G); 9416d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9426d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // If we already know the mapping to the label block add the successor now. 943d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LabelMapTy::iterator I = LabelMap.find(G->getLabel()); 9446d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 945d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (I == LabelMap.end()) 946d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // We will need to backpatch this block later. 947d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek BackpatchBlocks.push_back(Block); 948d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek else 949ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(Block, I->second); 950d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 9516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return Block; 952d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 953d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 954d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { 955d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* LoopSuccessor = NULL; 9566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 957fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump // "for" is a control-flow statement. Thus we stop processing the current 958fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump // block. 959d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Block) { 9604e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 9614e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 962d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LoopSuccessor = Block; 9634f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } else 9644f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LoopSuccessor = Succ; 9656d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Because of short-circuit evaluation, the condition of the loop can span 9676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 9686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // evaluate the condition. 96949af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* ExitConditionBlock = createBlock(false); 97049af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* EntryConditionBlock = ExitConditionBlock; 9716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 97249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek // Set the terminator for the "exit" condition block. 9736d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ExitConditionBlock->setTerminator(F); 9746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now add the actual condition to the condition block. Because the condition 9766d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // itself may contain control-flow, new blocks may be created. 97749af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek if (Stmt* C = F->getCond()) { 97849af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Block = ExitConditionBlock; 97949af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek EntryConditionBlock = addStmt(C); 98058b87feeaedce7ef09c2931a39d82e5aea189f41Ted Kremenek assert(Block == EntryConditionBlock); 98158b87feeaedce7ef09c2931a39d82e5aea189f41Ted Kremenek 98258b87feeaedce7ef09c2931a39d82e5aea189f41Ted Kremenek // If this block contains a condition variable, add both the condition 98358b87feeaedce7ef09c2931a39d82e5aea189f41Ted Kremenek // variable and initializer to the CFG. 98458b87feeaedce7ef09c2931a39d82e5aea189f41Ted Kremenek if (VarDecl *VD = F->getConditionVariable()) { 98558b87feeaedce7ef09c2931a39d82e5aea189f41Ted Kremenek if (Expr *Init = VD->getInit()) { 98658b87feeaedce7ef09c2931a39d82e5aea189f41Ted Kremenek autoCreateBlock(); 98758b87feeaedce7ef09c2931a39d82e5aea189f41Ted Kremenek AppendStmt(Block, F, AddStmtChoice::AlwaysAdd); 98858b87feeaedce7ef09c2931a39d82e5aea189f41Ted Kremenek EntryConditionBlock = addStmt(Init); 98958b87feeaedce7ef09c2931a39d82e5aea189f41Ted Kremenek assert(Block == EntryConditionBlock); 99058b87feeaedce7ef09c2931a39d82e5aea189f41Ted Kremenek } 99158b87feeaedce7ef09c2931a39d82e5aea189f41Ted Kremenek } 99258b87feeaedce7ef09c2931a39d82e5aea189f41Ted Kremenek 9934e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 9944e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(EntryConditionBlock)) 9954e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 9964e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 99749af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek } 998d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 9996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // The condition block is the implicit successor for the loop body as well as 10006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // any code above the loop. 100149af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Succ = EntryConditionBlock; 10026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 100300998a068e50945118f334c98af05ed44d7c22a6Mike Stump // See if this is a known constant. 1004941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek TryResult KnownVal(true); 10051eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 100600998a068e50945118f334c98af05ed44d7c22a6Mike Stump if (F->getCond()) 100700998a068e50945118f334c98af05ed44d7c22a6Mike Stump KnownVal = TryEvaluateBool(F->getCond()); 100800998a068e50945118f334c98af05ed44d7c22a6Mike Stump 1009d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Now create the loop body. 1010d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek { 10116db0ad32fa0987ff76d4c41393991ef4b6895ea3Ted Kremenek assert(F->getBody()); 10126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1013d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Save the current values for Block, Succ, and continue and break targets 1014d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 10155d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump save_continue(ContinueTargetBlock), 10165d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump save_break(BreakTargetBlock); 10176d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1018af603f742491dc4707138c0293d295171fdd51baTed Kremenek // Create a new block to contain the (bottom) of the loop body. 1019af603f742491dc4707138c0293d295171fdd51baTed Kremenek Block = NULL; 10206d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1021e933450535ab077b95e59f929a4ccb25b6f360e6Ted Kremenek if (Stmt* I = F->getInc()) { 10226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Generate increment code in its own basic block. This is the target of 10236d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // continue statements. 10244f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Succ = addStmt(I); 10256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else { 10266d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // No increment code. Create a special, empty, block that is used as the 10276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // target block for "looping back" to the start of the loop. 10283575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek assert(Succ == EntryConditionBlock); 10293575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek Succ = createBlock(); 1030e933450535ab077b95e59f929a4ccb25b6f360e6Ted Kremenek } 10316d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10323575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek // Finish up the increment (or empty) block if it hasn't been already. 10333575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek if (Block) { 10343575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek assert(Block == Succ); 10354e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 10364e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 10373575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek Block = 0; 10383575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek } 10396d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10403575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek ContinueTargetBlock = Succ; 10416d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10423575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek // The starting block for the loop increment is the block that should 10433575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek // represent the 'loop target' for looping back to the start of the loop. 10443575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek ContinueTargetBlock->setLoopTarget(F); 10453575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek 1046e933450535ab077b95e59f929a4ccb25b6f360e6Ted Kremenek // All breaks should go to the code following the loop. 10476d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump BreakTargetBlock = LoopSuccessor; 10486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now populate the body block, and in the process create new blocks as we 10506d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // walk the body of the loop. 10514f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* BodyBlock = addStmt(F->getBody()); 1052af603f742491dc4707138c0293d295171fdd51baTed Kremenek 1053af603f742491dc4707138c0293d295171fdd51baTed Kremenek if (!BodyBlock) 10541d4b218fa55239f2a7350f48be14090d2753c22cZhongxing Xu BodyBlock = ContinueTargetBlock; // can happen for "for (...;...;...) ;" 1055941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek else if (Block && !FinishBlock(BodyBlock)) 1056941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek return 0; 10576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1058941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek // This new body block is a successor to our "exit" condition block. 1059ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); 1060d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek } 10616d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1062941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek // Link up the condition block with the code that follows the loop. (the 1063941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek // false branch). 1064ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 10656d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1066d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // If the loop contains initialization, create a new block for those 10676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // statements. This block can also contain statements that precede the loop. 1068d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Stmt* I = F->getInit()) { 1069d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(); 107049af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek return addStmt(I); 10716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else { 10726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // There is no loop initialization. We are thus basically a while loop. 10736d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // NULL out Block to force lazy block construction. 10742bac4ea765a4a6e1f6149964663f62d4bca6743bTed Kremenek Block = NULL; 10755482713d70ecbfe608940018046aa248b3d03443Ted Kremenek Succ = EntryConditionBlock; 107649af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek return EntryConditionBlock; 10772bac4ea765a4a6e1f6149964663f62d4bca6743bTed Kremenek } 1078d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 1079d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1080514de5a21645900c92cf4f4f7313d6f66945d134Ted KremenekCFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { 1081514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // Objective-C fast enumeration 'for' statements: 1082514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC 1083514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1084514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // for ( Type newVariable in collection_expression ) { statements } 1085514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1086514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // becomes: 1087514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1088514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // prologue: 1089514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1. collection_expression 1090514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // T. jump to loop_entry 1091514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // loop_entry: 10924cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // 1. side-effects of element expression 1093514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1. ObjCForCollectionStmt [performs binding to newVariable] 1094514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil] 1095514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // TB: 1096514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // statements 1097514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // T. jump to loop_entry 1098514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // FB: 1099514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // what comes after 1100514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1101514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // and 1102514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1103514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // Type existingItem; 1104514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // for ( existingItem in expression ) { statements } 1105514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1106514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // becomes: 1107514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 11086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the same with newVariable replaced with existingItem; the binding works 11096d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the same except that for one ObjCForCollectionStmt::getElement() returns 11106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // a DeclStmt and the other returns a DeclRefExpr. 1111514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 11126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1113514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* LoopSuccessor = 0; 11146d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1115514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek if (Block) { 11164e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 11174e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 1118514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek LoopSuccessor = Block; 1119514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek Block = 0; 11204f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } else 11214f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LoopSuccessor = Succ; 11226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11234cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Build the condition blocks. 11244cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek CFGBlock* ExitConditionBlock = createBlock(false); 11254cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek CFGBlock* EntryConditionBlock = ExitConditionBlock; 11266d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11274cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Set the terminator for the "exit" condition block. 11286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ExitConditionBlock->setTerminator(S); 11296d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11306d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // The last statement in the block should be the ObjCForCollectionStmt, which 11316d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // performs the actual binding to 'element' and determines if there are any 11326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // more items in the collection. 1133ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AppendStmt(ExitConditionBlock, S); 11344cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek Block = ExitConditionBlock; 11356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11364cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Walk the 'element' expression to see if there are any side-effects. We 11376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // generate new blocks as necesary. We DON'T add the statement by default to 11386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the CFG unless it contains control-flow. 1139852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek EntryConditionBlock = Visit(S->getElement(), AddStmtChoice::NotAlwaysAdd); 11406d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (Block) { 11414e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(EntryConditionBlock)) 11424e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 11434e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek Block = 0; 11444e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 11456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // The condition block is the implicit successor for the loop body as well as 11476d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // any code above the loop. 11484cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek Succ = EntryConditionBlock; 11496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11504cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Now create the true branch. 11516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump { 11524cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Save the current values for Succ, continue and break targets. 11534cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek SaveAndRestore<CFGBlock*> save_Succ(Succ), 11546d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump save_continue(ContinueTargetBlock), save_break(BreakTargetBlock); 11556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11564cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek BreakTargetBlock = LoopSuccessor; 11576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ContinueTargetBlock = EntryConditionBlock; 11586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11594f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* BodyBlock = addStmt(S->getBody()); 11606d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11614cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek if (!BodyBlock) 11624cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;" 11634e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek else if (Block) { 11644e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(BodyBlock)) 11654e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 11664e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 11676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11684cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // This new body block is a successor to our "exit" condition block. 1169ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(ExitConditionBlock, BodyBlock); 11704cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek } 11716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11724cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Link up the condition block with the code that follows the loop. 11734cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // (the false branch). 1174ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(ExitConditionBlock, LoopSuccessor); 11754cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek 1176514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // Now create a prologue block to contain the collection expression. 11774cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek Block = createBlock(); 1178514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek return addStmt(S->getCollection()); 11796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump} 11806d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1181b3b0b3624e462c2940f65b86e773bfc300005203Ted KremenekCFGBlock* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S) { 1182b3b0b3624e462c2940f65b86e773bfc300005203Ted Kremenek // FIXME: Add locking 'primitives' to CFG for @synchronized. 11836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1184b3b0b3624e462c2940f65b86e773bfc300005203Ted Kremenek // Inline the body. 11854f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *SyncBlock = addStmt(S->getSynchBody()); 11866d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1187da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek // The sync body starts its own basic block. This makes it a little easier 1188da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek // for diagnostic clients. 1189da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek if (SyncBlock) { 1190da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek if (!FinishBlock(SyncBlock)) 1191da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek return 0; 11926d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1193da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek Block = 0; 1194da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek } 11956d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1196da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek Succ = SyncBlock; 11976d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1198b3b0b3624e462c2940f65b86e773bfc300005203Ted Kremenek // Inline the sync expression. 11994f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return addStmt(S->getSynchExpr()); 1200b3b0b3624e462c2940f65b86e773bfc300005203Ted Kremenek} 12016d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1202e31c0d206b872b056dc42c3af21b11d5de4edfd9Ted KremenekCFGBlock* CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt* S) { 12034f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // FIXME 120490658ec72542df44eb462c69056184d2946bdbceTed Kremenek return NYS(); 1205e31c0d206b872b056dc42c3af21b11d5de4edfd9Ted Kremenek} 1206514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek 1207d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { 1208d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* LoopSuccessor = NULL; 12096d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1210fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump // "while" is a control-flow statement. Thus we stop processing the current 1211fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump // block. 1212d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Block) { 12134e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 12144e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 1215d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LoopSuccessor = Block; 12164f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } else 12174f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LoopSuccessor = Succ; 12186d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Because of short-circuit evaluation, the condition of the loop can span 12206d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 12216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // evaluate the condition. 122249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* ExitConditionBlock = createBlock(false); 122349af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* EntryConditionBlock = ExitConditionBlock; 12246d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 122549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek // Set the terminator for the "exit" condition block. 122649af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek ExitConditionBlock->setTerminator(W); 12276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now add the actual condition to the condition block. Because the condition 12296d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // itself may contain control-flow, new blocks may be created. Thus we update 12306d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // "Succ" after adding the condition. 123149af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek if (Stmt* C = W->getCond()) { 123249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Block = ExitConditionBlock; 123349af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek EntryConditionBlock = addStmt(C); 1234f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek assert(Block == EntryConditionBlock); 12354ec010a6ccf4db2ab2ef9e68942642d50f7f193cTed Kremenek 12364ec010a6ccf4db2ab2ef9e68942642d50f7f193cTed Kremenek // If this block contains a condition variable, add both the condition 12374ec010a6ccf4db2ab2ef9e68942642d50f7f193cTed Kremenek // variable and initializer to the CFG. 12384ec010a6ccf4db2ab2ef9e68942642d50f7f193cTed Kremenek if (VarDecl *VD = W->getConditionVariable()) { 12394ec010a6ccf4db2ab2ef9e68942642d50f7f193cTed Kremenek if (Expr *Init = VD->getInit()) { 12404ec010a6ccf4db2ab2ef9e68942642d50f7f193cTed Kremenek autoCreateBlock(); 12414ec010a6ccf4db2ab2ef9e68942642d50f7f193cTed Kremenek AppendStmt(Block, W, AddStmtChoice::AlwaysAdd); 12424ec010a6ccf4db2ab2ef9e68942642d50f7f193cTed Kremenek EntryConditionBlock = addStmt(Init); 12434ec010a6ccf4db2ab2ef9e68942642d50f7f193cTed Kremenek assert(Block == EntryConditionBlock); 12444ec010a6ccf4db2ab2ef9e68942642d50f7f193cTed Kremenek } 12454ec010a6ccf4db2ab2ef9e68942642d50f7f193cTed Kremenek } 12464ec010a6ccf4db2ab2ef9e68942642d50f7f193cTed Kremenek 12474e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 12484e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(EntryConditionBlock)) 12494e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 12504e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 125149af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek } 12526d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12536d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // The condition block is the implicit successor for the loop body as well as 12546d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // any code above the loop. 125549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Succ = EntryConditionBlock; 12566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 125700998a068e50945118f334c98af05ed44d7c22a6Mike Stump // See if this is a known constant. 1258941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek const TryResult& KnownVal = TryEvaluateBool(W->getCond()); 125900998a068e50945118f334c98af05ed44d7c22a6Mike Stump 1260d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Process the loop body. 1261d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek { 1262f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek assert(W->getBody()); 1263d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1264d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Save the current values for Block, Succ, and continue and break targets 1265d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1266d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek save_continue(ContinueTargetBlock), 1267d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek save_break(BreakTargetBlock); 1268f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek 12696d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Create an empty block to represent the transition block for looping back 12706d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // to the head of the loop. 1271f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek Block = 0; 1272f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek assert(Succ == EntryConditionBlock); 1273f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek Succ = createBlock(); 1274f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek Succ->setLoopTarget(W); 12756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ContinueTargetBlock = Succ; 12766d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1277d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // All breaks should go to the code following the loop. 1278d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek BreakTargetBlock = LoopSuccessor; 12796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1280d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // NULL out Block to force lazy instantiation of blocks for the body. 1281f752fcfae84fbf21b78383bf2461633382d51844Ted Kremenek Block = NULL; 12826d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1283d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Create the body. The returned block is the entry to the loop body. 12844f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* BodyBlock = addStmt(W->getBody()); 12856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1286af603f742491dc4707138c0293d295171fdd51baTed Kremenek if (!BodyBlock) 1287d5c3b1339e842619fc3ae79482424f901aeb89f3Zhongxing Xu BodyBlock = ContinueTargetBlock; // can happen for "while(...) ;" 12884e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek else if (Block) { 12894e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(BodyBlock)) 12904e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 12914e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 12926d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1293941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek // Add the loop body entry as a successor to the condition. 1294ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); 1295bf15b278a439d73b605ec00a8d3977ef305712f4Ted Kremenek } 12966d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1297941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek // Link up the condition block with the code that follows the loop. (the 1298941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek // false branch). 1299ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 13006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13016d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // There can be no more statements in the condition block since we loop back 13026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // to this block. NULL out Block to force lazy creation of another block. 1303d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = NULL; 13046d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13054ec010a6ccf4db2ab2ef9e68942642d50f7f193cTed Kremenek // Return the condition block, which is the dominating block for the loop. 13065482713d70ecbfe608940018046aa248b3d03443Ted Kremenek Succ = EntryConditionBlock; 130749af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek return EntryConditionBlock; 1308d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 13091eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 13101eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 13114f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt* S) { 13124f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // FIXME: For now we pretend that @catch and the code it contains does not 13134f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // exit. 13144f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return Block; 13154f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 13166d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13172fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted KremenekCFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) { 13182fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek // FIXME: This isn't complete. We basically treat @throw like a return 13192fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek // statement. 13206d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13216c2497248bc4f7fd8e5fb0a206d20abbf0e16645Ted Kremenek // If we were in the middle of a block we stop processing that block. 13224f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (Block && !FinishBlock(Block)) 13234f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return 0; 13246d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13252fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek // Create the new block. 13262fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek Block = createBlock(false); 13276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13282fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek // The Exit block is the only successor. 1329ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(Block, &cfg->getExit()); 13306d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13316d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Add the statement to the block. This may create new blocks if S contains 13326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // control-flow (short-circuit operations). 1333852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek return VisitStmt(S, AddStmtChoice::AlwaysAdd); 13342fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek} 1335989d52d469df0c202f7de82f54407066c7db2e63Ted Kremenek 13360979d80615df97c675423de631c1b884819f4712Mike StumpCFGBlock* CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr* T) { 13376c2497248bc4f7fd8e5fb0a206d20abbf0e16645Ted Kremenek // If we were in the middle of a block we stop processing that block. 13380979d80615df97c675423de631c1b884819f4712Mike Stump if (Block && !FinishBlock(Block)) 13390979d80615df97c675423de631c1b884819f4712Mike Stump return 0; 13400979d80615df97c675423de631c1b884819f4712Mike Stump 13410979d80615df97c675423de631c1b884819f4712Mike Stump // Create the new block. 13420979d80615df97c675423de631c1b884819f4712Mike Stump Block = createBlock(false); 13430979d80615df97c675423de631c1b884819f4712Mike Stump 13445d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump if (TryTerminatedBlock) 13455d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump // The current try statement is the only successor. 13465d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump AddSuccessor(Block, TryTerminatedBlock); 13475d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump else 13485d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump // otherwise the Exit block is the only successor. 13495d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump AddSuccessor(Block, &cfg->getExit()); 13500979d80615df97c675423de631c1b884819f4712Mike Stump 13510979d80615df97c675423de631c1b884819f4712Mike Stump // Add the statement to the block. This may create new blocks if S contains 13520979d80615df97c675423de631c1b884819f4712Mike Stump // control-flow (short-circuit operations). 1353852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek return VisitStmt(T, AddStmtChoice::AlwaysAdd); 13540979d80615df97c675423de631c1b884819f4712Mike Stump} 13550979d80615df97c675423de631c1b884819f4712Mike Stump 13564f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { 1357d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* LoopSuccessor = NULL; 13586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13598f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump // "do...while" is a control-flow statement. Thus we stop processing the 13608f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump // current block. 1361d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Block) { 13624e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 13634e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 1364d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LoopSuccessor = Block; 13654f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } else 13664f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LoopSuccessor = Succ; 13676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Because of short-circuit evaluation, the condition of the loop can span 13696d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 13706d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // evaluate the condition. 137149af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* ExitConditionBlock = createBlock(false); 137249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* EntryConditionBlock = ExitConditionBlock; 13736d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 137449af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek // Set the terminator for the "exit" condition block. 13756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ExitConditionBlock->setTerminator(D); 13766d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13776d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now add the actual condition to the condition block. Because the condition 13786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // itself may contain control-flow, new blocks may be created. 137949af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek if (Stmt* C = D->getCond()) { 138049af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Block = ExitConditionBlock; 138149af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek EntryConditionBlock = addStmt(C); 13824e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 13834e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(EntryConditionBlock)) 13844e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 13854e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 138649af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek } 13876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13885482713d70ecbfe608940018046aa248b3d03443Ted Kremenek // The condition block is the implicit successor for the loop body. 138949af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Succ = EntryConditionBlock; 139049af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek 139100998a068e50945118f334c98af05ed44d7c22a6Mike Stump // See if this is a known constant. 1392941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek const TryResult &KnownVal = TryEvaluateBool(D->getCond()); 139300998a068e50945118f334c98af05ed44d7c22a6Mike Stump 1394d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Process the loop body. 139549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* BodyBlock = NULL; 1396d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek { 13976db0ad32fa0987ff76d4c41393991ef4b6895ea3Ted Kremenek assert(D->getBody()); 13986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1399d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Save the current values for Block, Succ, and continue and break targets 1400d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 14015d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump save_continue(ContinueTargetBlock), 14025d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump save_break(BreakTargetBlock); 14036d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1404d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // All continues within this loop should go to the condition block 140549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek ContinueTargetBlock = EntryConditionBlock; 14066d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1407d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // All breaks should go to the code following the loop. 1408d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek BreakTargetBlock = LoopSuccessor; 14096d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1410d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // NULL out Block to force lazy instantiation of blocks for the body. 1411b5c13b0f4e438391b31dacb87641be7a1b990b57Ted Kremenek Block = NULL; 14126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1413d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Create the body. The returned block is the entry to the loop body. 14144f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek BodyBlock = addStmt(D->getBody()); 14156d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1416af603f742491dc4707138c0293d295171fdd51baTed Kremenek if (!BodyBlock) 1417a9d996dbeb719200c4a9d86f68166a237583025fTed Kremenek BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" 14184e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek else if (Block) { 14194e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(BodyBlock)) 14204e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 14214e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 14226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 14238f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek // Add an intermediate block between the BodyBlock and the 14246d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // ExitConditionBlock to represent the "loop back" transition. Create an 14256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // empty block to represent the transition block for looping back to the 14266d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // head of the loop. 14278f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek // FIXME: Can we do this more efficiently without adding another block? 14288f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek Block = NULL; 14298f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek Succ = BodyBlock; 14308f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek CFGBlock *LoopBackBlock = createBlock(); 14318f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek LoopBackBlock->setLoopTarget(D); 14326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1433941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek // Add the loop body entry as a successor to the condition. 1434ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : LoopBackBlock); 1435b5c13b0f4e438391b31dacb87641be7a1b990b57Ted Kremenek } 14366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1437941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek // Link up the condition block with the code that follows the loop. 1438941fde8019d47c694b8483db45d5878818fa69d1Ted Kremenek // (the false branch). 1439ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 14406d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 14416d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // There can be no more statements in the body block(s) since we loop back to 14426d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the body. NULL out Block to force lazy creation of another block. 1443d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = NULL; 14446d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1445d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Return the loop body, which is the dominating block for the loop. 14465482713d70ecbfe608940018046aa248b3d03443Ted Kremenek Succ = BodyBlock; 1447d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek return BodyBlock; 1448d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 1449d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1450d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) { 1451d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // "continue" is a control-flow statement. Thus we stop processing the 1452d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // current block. 14534f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (Block && !FinishBlock(Block)) 14544e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 14556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1456d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Now create a new block that ends with the continue statement. 1457d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(false); 1458d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->setTerminator(C); 14596d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1460d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // If there is no target for the continue, then we are looking at an 1461235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek // incomplete AST. This means the CFG cannot be constructed. 1462235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek if (ContinueTargetBlock) 1463ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(Block, ContinueTargetBlock); 1464235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek else 1465235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek badCFG = true; 14666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1467d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek return Block; 1468d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 14691eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 147013fc08a323b29dd97a46def1e3a15bf082476efaTed KremenekCFGBlock *CFGBuilder::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, 1471852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek AddStmtChoice asc) { 147213fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek 1473852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek if (asc.alwaysAdd()) { 147413fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek autoCreateBlock(); 1475ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AppendStmt(Block, E); 147613fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek } 14771eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 14784f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // VLA types have expressions that must be evaluated. 14794f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (E->isArgumentType()) { 14804f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek for (VariableArrayType* VA = FindVA(E->getArgumentType().getTypePtr()); 14814f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) 14824f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek addStmt(VA->getSizeExpr()); 14834e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 14841eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 14856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return Block; 1486d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 14871eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 14884f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek/// VisitStmtExpr - Utility method to handle (nested) statement 14894f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek/// expressions (a GCC extension). 1490852274d4257134906995cb252fb3dfd2d71deae8Ted KremenekCFGBlock* CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) { 1491852274d4257134906995cb252fb3dfd2d71deae8Ted Kremenek if (asc.alwaysAdd()) { 149213fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek autoCreateBlock(); 1493ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AppendStmt(Block, SE); 149413fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek } 14954f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitCompoundStmt(SE->getSubStmt()); 14964f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 1497d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1498411cdee0b490f79428c9eb977f25199eb7d21cd8Ted KremenekCFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { 14996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // "switch" is a control-flow statement. Thus we stop processing the current 15006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block. 1501d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* SwitchSuccessor = NULL; 15026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1503d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Block) { 15044e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 15054e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 1506d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SwitchSuccessor = Block; 15076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else SwitchSuccessor = Succ; 1508d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1509d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Save the current "switch" context. 1510d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), 1511eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek save_break(BreakTargetBlock), 1512eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek save_default(DefaultCaseBlock); 1513eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek 15146d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Set the "default" case to be the block after the switch statement. If the 15156d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // switch statement contains a "default:", this value will be overwritten with 15166d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the block for that code. 1517eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek DefaultCaseBlock = SwitchSuccessor; 15186d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1519d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Create a new block that will contain the switch statement. 1520d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SwitchTerminatedBlock = createBlock(false); 15216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1522d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Now process the switch body. The code after the switch is the implicit 1523d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // successor. 1524d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Succ = SwitchSuccessor; 1525d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek BreakTargetBlock = SwitchSuccessor; 15266d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 15276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // When visiting the body, the case statements should automatically get linked 15286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // up to the switch. We also don't keep a pointer to the body, since all 15296d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // control-flow from the switch goes to case/default statements. 15306db0ad32fa0987ff76d4c41393991ef4b6895ea3Ted Kremenek assert(Terminator->getBody() && "switch must contain a non-NULL body"); 153149af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Block = NULL; 15324f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *BodyBlock = addStmt(Terminator->getBody()); 15334e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 15344e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(BodyBlock)) 15354e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 15364e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 153749af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek 15386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // If we have no "default:" case, the default transition is to the code 15396d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // following the switch body. 1540ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(SwitchTerminatedBlock, DefaultCaseBlock); 15416d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 154249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek // Add the terminator and condition in the switch block. 1543411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek SwitchTerminatedBlock->setTerminator(Terminator); 15446db0ad32fa0987ff76d4c41393991ef4b6895ea3Ted Kremenek assert(Terminator->getCond() && "switch condition must be non-NULL"); 1545d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = SwitchTerminatedBlock; 15466b501ebaf172b28d6d7e1737db27f915175ad3c8Ted Kremenek Block = addStmt(Terminator->getCond()); 15476b501ebaf172b28d6d7e1737db27f915175ad3c8Ted Kremenek 15486b501ebaf172b28d6d7e1737db27f915175ad3c8Ted Kremenek // Finally, if the SwitchStmt contains a condition variable, add both the 15496b501ebaf172b28d6d7e1737db27f915175ad3c8Ted Kremenek // SwitchStmt and the condition variable initialization to the CFG. 15506b501ebaf172b28d6d7e1737db27f915175ad3c8Ted Kremenek if (VarDecl *VD = Terminator->getConditionVariable()) { 15516b501ebaf172b28d6d7e1737db27f915175ad3c8Ted Kremenek if (Expr *Init = VD->getInit()) { 15526b501ebaf172b28d6d7e1737db27f915175ad3c8Ted Kremenek autoCreateBlock(); 15536b501ebaf172b28d6d7e1737db27f915175ad3c8Ted Kremenek AppendStmt(Block, Terminator, AddStmtChoice::AlwaysAdd); 15546b501ebaf172b28d6d7e1737db27f915175ad3c8Ted Kremenek addStmt(Init); 15556b501ebaf172b28d6d7e1737db27f915175ad3c8Ted Kremenek } 15566b501ebaf172b28d6d7e1737db27f915175ad3c8Ted Kremenek } 15576b501ebaf172b28d6d7e1737db27f915175ad3c8Ted Kremenek 15586b501ebaf172b28d6d7e1737db27f915175ad3c8Ted Kremenek return Block; 1559d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 1560d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 15614f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) { 15626d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // CaseStmts are essentially labels, so they are the first statement in a 15636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block. 156429ccaa186ac27bcb414c5acb069f6438b27dd5e7Ted Kremenek 15654f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (CS->getSubStmt()) 15664f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek addStmt(CS->getSubStmt()); 15671eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 156829ccaa186ac27bcb414c5acb069f6438b27dd5e7Ted Kremenek CFGBlock* CaseBlock = Block; 15694f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (!CaseBlock) 15704f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CaseBlock = createBlock(); 15716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 15726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Cases statements partition blocks, so this is the top of the basic block we 15736d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // were processing (the "case XXX:" is the label). 15744f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CaseBlock->setLabel(CS); 15754f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 15764e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(CaseBlock)) 15774e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 15786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 15796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Add this block to the list of successors for the block with the switch 15806d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // statement. 15814f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek assert(SwitchTerminatedBlock); 1582ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(SwitchTerminatedBlock, CaseBlock); 15836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1584d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // We set Block to NULL to allow lazy creation of a new block (if necessary) 1585d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = NULL; 15866d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1587d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // This block is now the implicit successor of other blocks. 1588d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Succ = CaseBlock; 15896d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 15902677ea871a25aa79f9db360f6ed10584c02267adTed Kremenek return CaseBlock; 1591d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 15926d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1593411cdee0b490f79428c9eb977f25199eb7d21cd8Ted KremenekCFGBlock* CFGBuilder::VisitDefaultStmt(DefaultStmt* Terminator) { 15944f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (Terminator->getSubStmt()) 15954f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek addStmt(Terminator->getSubStmt()); 15961eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 1597eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek DefaultCaseBlock = Block; 15984f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 15994f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (!DefaultCaseBlock) 16004f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek DefaultCaseBlock = createBlock(); 16016d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 16026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Default statements partition blocks, so this is the top of the basic block 16036d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // we were processing (the "default:" is the label). 1604411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek DefaultCaseBlock->setLabel(Terminator); 16051eb4433ac451dc16f4133a88af2d002ac26c58efMike Stump 16064e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(DefaultCaseBlock)) 16074e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 1608eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek 16096d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Unlike case statements, we don't add the default block to the successors 16106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // for the switch statement immediately. This is done when we finish 16116d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // processing the switch statement. This allows for the default case 16126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // (including a fall-through to the code after the switch statement) to always 16136d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // be the last successor of a switch-terminated block. 16146d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1615eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek // We set Block to NULL to allow lazy creation of a new block (if necessary) 1616eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek Block = NULL; 16176d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1618eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek // This block is now the implicit successor of other blocks. 1619eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek Succ = DefaultCaseBlock; 16206d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 16216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return DefaultCaseBlock; 1622295222c1f0926d84de77f076e79903523eeb5dbfTed Kremenek} 1623d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 16245d1d20227878cd03db8b2dd23efd4cedfe874feeMike StumpCFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) { 16255d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump // "try"/"catch" is a control-flow statement. Thus we stop processing the 16265d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump // current block. 16275d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump CFGBlock* TrySuccessor = NULL; 16285d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 16295d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump if (Block) { 16305d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump if (!FinishBlock(Block)) 16315d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump return 0; 16325d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump TrySuccessor = Block; 16335d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump } else TrySuccessor = Succ; 16345d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 1635a1f93631a84621d77aeb627691da85a8991af188Mike Stump CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock; 16365d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 16375d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump // Create a new block that will contain the try statement. 1638f00cca5e05bb9ea51a3a21c8014ff9f3508d46e9Mike Stump CFGBlock *NewTryTerminatedBlock = createBlock(false); 16395d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump // Add the terminator in the try block. 1640f00cca5e05bb9ea51a3a21c8014ff9f3508d46e9Mike Stump NewTryTerminatedBlock->setTerminator(Terminator); 16415d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 1642a1f93631a84621d77aeb627691da85a8991af188Mike Stump bool HasCatchAll = false; 16435d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump for (unsigned h = 0; h <Terminator->getNumHandlers(); ++h) { 16445d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump // The code after the try is the implicit successor. 16455d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump Succ = TrySuccessor; 16465d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump CXXCatchStmt *CS = Terminator->getHandler(h); 1647a1f93631a84621d77aeb627691da85a8991af188Mike Stump if (CS->getExceptionDecl() == 0) { 1648a1f93631a84621d77aeb627691da85a8991af188Mike Stump HasCatchAll = true; 1649a1f93631a84621d77aeb627691da85a8991af188Mike Stump } 16505d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump Block = NULL; 16515d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump CFGBlock *CatchBlock = VisitCXXCatchStmt(CS); 16525d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump if (CatchBlock == 0) 16535d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump return 0; 16545d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump // Add this block to the list of successors for the block with the try 16555d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump // statement. 1656f00cca5e05bb9ea51a3a21c8014ff9f3508d46e9Mike Stump AddSuccessor(NewTryTerminatedBlock, CatchBlock); 16575d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump } 1658a1f93631a84621d77aeb627691da85a8991af188Mike Stump if (!HasCatchAll) { 1659a1f93631a84621d77aeb627691da85a8991af188Mike Stump if (PrevTryTerminatedBlock) 1660f00cca5e05bb9ea51a3a21c8014ff9f3508d46e9Mike Stump AddSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock); 1661a1f93631a84621d77aeb627691da85a8991af188Mike Stump else 1662f00cca5e05bb9ea51a3a21c8014ff9f3508d46e9Mike Stump AddSuccessor(NewTryTerminatedBlock, &cfg->getExit()); 1663a1f93631a84621d77aeb627691da85a8991af188Mike Stump } 16645d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 16655d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump // The code after the try is the implicit successor. 16665d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump Succ = TrySuccessor; 16675d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 1668f00cca5e05bb9ea51a3a21c8014ff9f3508d46e9Mike Stump // Save the current "try" context. 1669f00cca5e05bb9ea51a3a21c8014ff9f3508d46e9Mike Stump SaveAndRestore<CFGBlock*> save_try(TryTerminatedBlock); 1670f00cca5e05bb9ea51a3a21c8014ff9f3508d46e9Mike Stump TryTerminatedBlock = NewTryTerminatedBlock; 1671f00cca5e05bb9ea51a3a21c8014ff9f3508d46e9Mike Stump 16726db0ad32fa0987ff76d4c41393991ef4b6895ea3Ted Kremenek assert(Terminator->getTryBlock() && "try must contain a non-NULL body"); 16735d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump Block = NULL; 16743fa1e4b27300a4ea4cf273182d4b6427ef87f3f8Ted Kremenek Block = addStmt(Terminator->getTryBlock()); 16755d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump return Block; 16765d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump} 16775d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 16785d1d20227878cd03db8b2dd23efd4cedfe874feeMike StumpCFGBlock* CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt* CS) { 16795d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump // CXXCatchStmt are treated like labels, so they are the first statement in a 16805d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump // block. 16815d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 16825d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump if (CS->getHandlerBlock()) 16835d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump addStmt(CS->getHandlerBlock()); 16845d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 16855d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump CFGBlock* CatchBlock = Block; 16865d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump if (!CatchBlock) 16875d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump CatchBlock = createBlock(); 16885d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 16895d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump CatchBlock->setLabel(CS); 16905d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 16915d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump if (!FinishBlock(CatchBlock)) 16925d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump return 0; 16935d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 16945d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump // We set Block to NULL to allow lazy creation of a new block (if necessary) 16955d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump Block = NULL; 16965d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 16975d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump return CatchBlock; 16985d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump} 16995d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 170019bb356317952445b03ee341c02f6147083c9eeaTed KremenekCFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { 17016d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Lazily create the indirect-goto dispatch block if there isn't one already. 170219bb356317952445b03ee341c02f6147083c9eeaTed Kremenek CFGBlock* IBlock = cfg->getIndirectGotoBlock(); 17036d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 170419bb356317952445b03ee341c02f6147083c9eeaTed Kremenek if (!IBlock) { 170519bb356317952445b03ee341c02f6147083c9eeaTed Kremenek IBlock = createBlock(false); 170619bb356317952445b03ee341c02f6147083c9eeaTed Kremenek cfg->setIndirectGotoBlock(IBlock); 170719bb356317952445b03ee341c02f6147083c9eeaTed Kremenek } 17086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 170919bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // IndirectGoto is a control-flow statement. Thus we stop processing the 171019bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // current block and create a new one. 17114f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (Block && !FinishBlock(Block)) 17124f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return 0; 17134f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 171419bb356317952445b03ee341c02f6147083c9eeaTed Kremenek Block = createBlock(false); 171519bb356317952445b03ee341c02f6147083c9eeaTed Kremenek Block->setTerminator(I); 1716ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek AddSuccessor(Block, IBlock); 171719bb356317952445b03ee341c02f6147083c9eeaTed Kremenek return addStmt(I->getTarget()); 171819bb356317952445b03ee341c02f6147083c9eeaTed Kremenek} 171919bb356317952445b03ee341c02f6147083c9eeaTed Kremenek 1720befef2f69759d7338e2b7c5ce6c8b6f47fe6e667Ted Kremenek} // end anonymous namespace 1721026473c2175424a039f51ca8949937268721b965Ted Kremenek 17226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has 17236d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// no successors or predecessors. If this is the first block created in the 17246d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// CFG, it is automatically set to be the Entry and Exit of the CFG. 17259438252ad2ecae5338df565ca33c6969e4fbfa41Ted KremenekCFGBlock* CFG::createBlock() { 1726026473c2175424a039f51ca8949937268721b965Ted Kremenek bool first_block = begin() == end(); 1727026473c2175424a039f51ca8949937268721b965Ted Kremenek 1728026473c2175424a039f51ca8949937268721b965Ted Kremenek // Create the block. 1729ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek CFGBlock *Mem = getAllocator().Allocate<CFGBlock>(); 1730ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek new (Mem) CFGBlock(NumBlockIDs++, BlkBVC); 1731ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek Blocks.push_back(Mem, BlkBVC); 1732026473c2175424a039f51ca8949937268721b965Ted Kremenek 1733026473c2175424a039f51ca8949937268721b965Ted Kremenek // If this is the first block, set it as the Entry and Exit. 1734ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek if (first_block) 1735ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek Entry = Exit = &back(); 1736026473c2175424a039f51ca8949937268721b965Ted Kremenek 1737026473c2175424a039f51ca8949937268721b965Ted Kremenek // Return the block. 1738ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek return &back(); 1739026473c2175424a039f51ca8949937268721b965Ted Kremenek} 1740026473c2175424a039f51ca8949937268721b965Ted Kremenek 1741026473c2175424a039f51ca8949937268721b965Ted Kremenek/// buildCFG - Constructs a CFG from an AST. Ownership of the returned 1742026473c2175424a039f51ca8949937268721b965Ted Kremenek/// CFG is returned to the caller. 1743b978a441c7d8bf59e7fede938e1f3b672573b443Mike StumpCFG* CFG::buildCFG(const Decl *D, Stmt* Statement, ASTContext *C, 17444c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump bool AddEHEdges, bool AddScopes) { 1745fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek CFGBuilder Builder; 17464c45aa1b00b91847acfb082acfaced3ffa294d1dMike Stump return Builder.buildCFG(D, Statement, C, AddEHEdges, AddScopes); 1747fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek} 1748fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 174963f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek//===----------------------------------------------------------------------===// 175063f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek// CFG: Queries for BlkExprs. 175163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek//===----------------------------------------------------------------------===// 175263f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 175363f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremeneknamespace { 175486946745225096243f6969dc745267b78fc211a6Ted Kremenek typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy; 175563f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek} 175663f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 17578a69366a1cd8fe1e9fd312048c0d5ce58eabeeb2Ted Kremenekstatic void FindSubExprAssignments(Stmt *S, 17588a69366a1cd8fe1e9fd312048c0d5ce58eabeeb2Ted Kremenek llvm::SmallPtrSet<Expr*,50>& Set) { 17598a69366a1cd8fe1e9fd312048c0d5ce58eabeeb2Ted Kremenek if (!S) 176033d4aab80f31bd06257526fe2883ea920529456bTed Kremenek return; 17616d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 17628a69366a1cd8fe1e9fd312048c0d5ce58eabeeb2Ted Kremenek for (Stmt::child_iterator I=S->child_begin(), E=S->child_end(); I!=E; ++I) { 17638a69366a1cd8fe1e9fd312048c0d5ce58eabeeb2Ted Kremenek Stmt *child = *I; 17648a69366a1cd8fe1e9fd312048c0d5ce58eabeeb2Ted Kremenek if (!child) 17658a69366a1cd8fe1e9fd312048c0d5ce58eabeeb2Ted Kremenek continue; 17668a69366a1cd8fe1e9fd312048c0d5ce58eabeeb2Ted Kremenek 17678a69366a1cd8fe1e9fd312048c0d5ce58eabeeb2Ted Kremenek if (BinaryOperator* B = dyn_cast<BinaryOperator>(child)) 176833d4aab80f31bd06257526fe2883ea920529456bTed Kremenek if (B->isAssignmentOp()) Set.insert(B); 17696d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 17708a69366a1cd8fe1e9fd312048c0d5ce58eabeeb2Ted Kremenek FindSubExprAssignments(child, Set); 177133d4aab80f31bd06257526fe2883ea920529456bTed Kremenek } 177233d4aab80f31bd06257526fe2883ea920529456bTed Kremenek} 177333d4aab80f31bd06257526fe2883ea920529456bTed Kremenek 177463f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenekstatic BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { 177563f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek BlkExprMapTy* M = new BlkExprMapTy(); 17766d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 17776d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Look for assignments that are used as subexpressions. These are the only 17786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // assignments that we want to *possibly* register as a block-level 17796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // expression. Basically, if an assignment occurs both in a subexpression and 17806d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // at the block-level, it is a block-level expression. 178133d4aab80f31bd06257526fe2883ea920529456bTed Kremenek llvm::SmallPtrSet<Expr*,50> SubExprAssignments; 17826d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 178363f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) 1784ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) 178533d4aab80f31bd06257526fe2883ea920529456bTed Kremenek FindSubExprAssignments(*BI, SubExprAssignments); 178686946745225096243f6969dc745267b78fc211a6Ted Kremenek 1787411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { 17886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 17896d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Iterate over the statements again on identify the Expr* and Stmt* at the 17906d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block-level that are block-level expressions. 1791411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek 1792ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) 1793411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (Expr* Exp = dyn_cast<Expr>(*BI)) { 17946d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1795411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { 179633d4aab80f31bd06257526fe2883ea920529456bTed Kremenek // Assignment expressions that are not nested within another 17976d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // expression are really "statements" whose value is never used by 17986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // another expression. 1799411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (B->isAssignmentOp() && !SubExprAssignments.count(Exp)) 180033d4aab80f31bd06257526fe2883ea920529456bTed Kremenek continue; 18016d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else if (const StmtExpr* Terminator = dyn_cast<StmtExpr>(Exp)) { 18026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Special handling for statement expressions. The last statement in 18036d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the statement expression is also a block-level expr. 1804411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek const CompoundStmt* C = Terminator->getSubStmt(); 180586946745225096243f6969dc745267b78fc211a6Ted Kremenek if (!C->body_empty()) { 180633d4aab80f31bd06257526fe2883ea920529456bTed Kremenek unsigned x = M->size(); 180786946745225096243f6969dc745267b78fc211a6Ted Kremenek (*M)[C->body_back()] = x; 180886946745225096243f6969dc745267b78fc211a6Ted Kremenek } 180986946745225096243f6969dc745267b78fc211a6Ted Kremenek } 1810e2dcd783a04f654c50bd8b13fb08a440afbd67e7Ted Kremenek 181133d4aab80f31bd06257526fe2883ea920529456bTed Kremenek unsigned x = M->size(); 1812411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek (*M)[Exp] = x; 181333d4aab80f31bd06257526fe2883ea920529456bTed Kremenek } 18146d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1815411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek // Look at terminators. The condition is a block-level expression. 18166d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1817ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek Stmt* S = (*I)->getTerminatorCondition(); 18186d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1819390e48b15ad93f85bfd1e33b9992c198fa0db475Ted Kremenek if (S && M->find(S) == M->end()) { 1820411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek unsigned x = M->size(); 1821390e48b15ad93f85bfd1e33b9992c198fa0db475Ted Kremenek (*M)[S] = x; 1822411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek } 1823411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek } 18246d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 182586946745225096243f6969dc745267b78fc211a6Ted Kremenek return M; 182663f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek} 182763f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 182886946745225096243f6969dc745267b78fc211a6Ted KremenekCFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) { 182986946745225096243f6969dc745267b78fc211a6Ted Kremenek assert(S != NULL); 183063f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } 18316d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 183263f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap); 183386946745225096243f6969dc745267b78fc211a6Ted Kremenek BlkExprMapTy::iterator I = M->find(S); 18343fa1e4b27300a4ea4cf273182d4b6427ef87f3f8Ted Kremenek return (I == M->end()) ? CFG::BlkExprNumTy() : CFG::BlkExprNumTy(I->second); 183563f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek} 18367dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 183763f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenekunsigned CFG::getNumBlkExprs() { 183863f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) 183963f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek return M->size(); 184063f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek else { 184163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek // We assume callers interested in the number of BlkExprs will want 184263f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek // the map constructed if it doesn't already exist. 184363f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek BlkExprMap = (void*) PopulateBlkExprMap(*this); 184463f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); 184563f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek } 184663f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek} 184763f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 1848274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek//===----------------------------------------------------------------------===// 1849274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek// Cleanup: CFG dstor. 1850274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek//===----------------------------------------------------------------------===// 1851274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek 185263f5887f316fb52d243fcbb3631c039de6c4b993Ted KremenekCFG::~CFG() { 185363f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); 185463f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek} 18556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 18567dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 18577dba8607e59096014b7139ff20ef00870041d518Ted Kremenek// CFG pretty printing 18587dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 18597dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 186042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremeneknamespace { 18612bac4ea765a4a6e1f6149964663f62d4bca6743bTed Kremenek 1862ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamclass StmtPrinterHelper : public PrinterHelper { 186342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; 186442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek StmtMapTy StmtMap; 186542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek signed CurrentBlock; 186642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek unsigned CurrentStmt; 1867e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner const LangOptions &LangOpts; 186842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenekpublic: 18691c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek 1870e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) 1871e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner : CurrentBlock(0), CurrentStmt(0), LangOpts(LO) { 187242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { 187342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek unsigned j = 1; 1874ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ; 187542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek BI != BEnd; ++BI, ++j ) 1876ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek StmtMap[*BI] = std::make_pair((*I)->getBlockID(),j); 187742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek } 1878fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 18796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 188042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek virtual ~StmtPrinterHelper() {} 18816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1882e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner const LangOptions &getLangOpts() const { return LangOpts; } 188342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek void setBlockID(signed i) { CurrentBlock = i; } 188442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek void setStmtID(unsigned i) { CurrentStmt = i; } 18856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1886a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek virtual bool handledStmt(Stmt* Terminator, llvm::raw_ostream& OS) { 18876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1888411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek StmtMapTy::iterator I = StmtMap.find(Terminator); 1889fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 189042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (I == StmtMap.end()) 189142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek return false; 18926d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 18936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (CurrentBlock >= 0 && I->second.first == (unsigned) CurrentBlock 18943fa1e4b27300a4ea4cf273182d4b6427ef87f3f8Ted Kremenek && I->second.second == CurrentStmt) { 189542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek return false; 18963fa1e4b27300a4ea4cf273182d4b6427ef87f3f8Ted Kremenek } 18976d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 18983fa1e4b27300a4ea4cf273182d4b6427ef87f3f8Ted Kremenek OS << "[B" << I->second.first << "." << I->second.second << "]"; 18991c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek return true; 190042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek } 190142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek}; 1902e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner} // end anonymous namespace 1903e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner 1904e8ee26b49d68ae3ffdf9a990ff7511ef55afa04cTed Kremenek 1905e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnernamespace { 1906ba5fb5a955c896815c439289fc51c03cf0635129Kovarththanan Rajaratnamclass CFGBlockTerminatorPrint 19076fa9b88e2c3d47d606a273df2f8d03509bcff0b9Ted Kremenek : public StmtVisitor<CFGBlockTerminatorPrint,void> { 19086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1909a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek llvm::raw_ostream& OS; 191042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek StmtPrinterHelper* Helper; 1911d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor PrintingPolicy Policy; 1912d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenekpublic: 1913d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor CFGBlockTerminatorPrint(llvm::raw_ostream& os, StmtPrinterHelper* helper, 1914e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner const PrintingPolicy &Policy) 1915d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor : OS(os), Helper(helper), Policy(Policy) {} 19166d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1917d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek void VisitIfStmt(IfStmt* I) { 1918d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek OS << "if "; 1919d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor I->getCond()->printPretty(OS,Helper,Policy); 1920d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek } 19216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1922d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Default case. 19236d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump void VisitStmt(Stmt* Terminator) { 19246d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Terminator->printPretty(OS, Helper, Policy); 19256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 19266d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1927d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek void VisitForStmt(ForStmt* F) { 1928d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek OS << "for (" ; 19293fa1e4b27300a4ea4cf273182d4b6427ef87f3f8Ted Kremenek if (F->getInit()) 19303fa1e4b27300a4ea4cf273182d4b6427ef87f3f8Ted Kremenek OS << "..."; 1931535bb20b6e252809bc17cc59b5d71b5e5e549e70Ted Kremenek OS << "; "; 19323fa1e4b27300a4ea4cf273182d4b6427ef87f3f8Ted Kremenek if (Stmt* C = F->getCond()) 19333fa1e4b27300a4ea4cf273182d4b6427ef87f3f8Ted Kremenek C->printPretty(OS, Helper, Policy); 1934535bb20b6e252809bc17cc59b5d71b5e5e549e70Ted Kremenek OS << "; "; 19353fa1e4b27300a4ea4cf273182d4b6427ef87f3f8Ted Kremenek if (F->getInc()) 19363fa1e4b27300a4ea4cf273182d4b6427ef87f3f8Ted Kremenek OS << "..."; 1937a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek OS << ")"; 1938d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek } 19396d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1940d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek void VisitWhileStmt(WhileStmt* W) { 1941d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek OS << "while " ; 19423fa1e4b27300a4ea4cf273182d4b6427ef87f3f8Ted Kremenek if (Stmt* C = W->getCond()) 19433fa1e4b27300a4ea4cf273182d4b6427ef87f3f8Ted Kremenek C->printPretty(OS, Helper, Policy); 1944d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek } 19456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1946d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek void VisitDoStmt(DoStmt* D) { 1947d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek OS << "do ... while "; 19483fa1e4b27300a4ea4cf273182d4b6427ef87f3f8Ted Kremenek if (Stmt* C = D->getCond()) 19493fa1e4b27300a4ea4cf273182d4b6427ef87f3f8Ted Kremenek C->printPretty(OS, Helper, Policy); 19509da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek } 19516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1952411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek void VisitSwitchStmt(SwitchStmt* Terminator) { 19539da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek OS << "switch "; 1954d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor Terminator->getCond()->printPretty(OS, Helper, Policy); 19559da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek } 19566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 19575d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump void VisitCXXTryStmt(CXXTryStmt* CS) { 19585d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump OS << "try ..."; 19595d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump } 19605d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 1961805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek void VisitConditionalOperator(ConditionalOperator* C) { 1962d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor C->getCond()->printPretty(OS, Helper, Policy); 19636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump OS << " ? ... : ..."; 1964805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek } 19656d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1966aeddbf689eb3e3afca5117ca83c7b2e18260b0d8Ted Kremenek void VisitChooseExpr(ChooseExpr* C) { 1967aeddbf689eb3e3afca5117ca83c7b2e18260b0d8Ted Kremenek OS << "__builtin_choose_expr( "; 1968d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor C->getCond()->printPretty(OS, Helper, Policy); 1969a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek OS << " )"; 1970aeddbf689eb3e3afca5117ca83c7b2e18260b0d8Ted Kremenek } 19716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 19721c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek void VisitIndirectGotoStmt(IndirectGotoStmt* I) { 19731c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek OS << "goto *"; 1974d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor I->getTarget()->printPretty(OS, Helper, Policy); 19751c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek } 19766d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1977805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek void VisitBinaryOperator(BinaryOperator* B) { 1978805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek if (!B->isLogicalOp()) { 1979805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek VisitExpr(B); 1980805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek return; 1981805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek } 19826d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1983d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor B->getLHS()->printPretty(OS, Helper, Policy); 19846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1985805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek switch (B->getOpcode()) { 1986805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek case BinaryOperator::LOr: 1987a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek OS << " || ..."; 1988805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek return; 1989805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek case BinaryOperator::LAnd: 1990a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek OS << " && ..."; 1991805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek return; 1992805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek default: 1993805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek assert(false && "Invalid logical operator."); 19946d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 1995805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek } 19966d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 19970b1d9b7557437176f9cea1283bfac2510812beceTed Kremenek void VisitExpr(Expr* E) { 1998d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor E->printPretty(OS, Helper, Policy); 19996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 2000d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek}; 2001e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner} // end anonymous namespace 2002e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner 20036d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2004e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnerstatic void print_stmt(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, 2005079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump const CFGElement &E) { 2006079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump Stmt *Terminator = E; 2007079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump 2008079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump if (E.asStartScope()) { 2009079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump OS << "start scope\n"; 2010079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump return; 2011079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump } 2012079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump if (E.asEndScope()) { 2013079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump OS << "end scope\n"; 2014079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump return; 2015079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump } 2016079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump 20171c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek if (Helper) { 20181c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek // special printing for statement-expressions. 2019411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (StmtExpr* SE = dyn_cast<StmtExpr>(Terminator)) { 20201c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek CompoundStmt* Sub = SE->getSubStmt(); 20216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 20221c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek if (Sub->child_begin() != Sub->child_end()) { 202360266e8a9a4cd941af5e0006a18377dc03f0421bTed Kremenek OS << "({ ... ; "; 20247a9d9d71fa208dc23fd67d03ce052d4ef60a8d04Ted Kremenek Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); 202560266e8a9a4cd941af5e0006a18377dc03f0421bTed Kremenek OS << " })\n"; 20261c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek return; 20271c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek } 20281c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek } 20296d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 20301c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek // special printing for comma expressions. 2031411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (BinaryOperator* B = dyn_cast<BinaryOperator>(Terminator)) { 20321c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek if (B->getOpcode() == BinaryOperator::Comma) { 20331c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek OS << "... , "; 20341c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek Helper->handledStmt(B->getRHS(),OS); 20351c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek OS << '\n'; 20361c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek return; 20376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 20386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 20391c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek } 20406d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2041e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner Terminator->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 20426d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 20431c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek // Expressions need a newline. 2044411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (isa<Expr>(Terminator)) OS << '\n'; 20451c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek} 20466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2047e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnerstatic void print_block(llvm::raw_ostream& OS, const CFG* cfg, 2048e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner const CFGBlock& B, 2049e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner StmtPrinterHelper* Helper, bool print_edges) { 20506d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 205142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (Helper) Helper->setBlockID(B.getBlockID()); 20526d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 20537dba8607e59096014b7139ff20ef00870041d518Ted Kremenek // Print the header. 20546d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump OS << "\n [ B" << B.getBlockID(); 20556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 205642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (&B == &cfg->getEntry()) 205742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " (ENTRY) ]\n"; 205842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek else if (&B == &cfg->getExit()) 205942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " (EXIT) ]\n"; 206042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek else if (&B == cfg->getIndirectGotoBlock()) 20617dba8607e59096014b7139ff20ef00870041d518Ted Kremenek OS << " (INDIRECT GOTO DISPATCH) ]\n"; 206242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek else 206342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " ]\n"; 20646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 20659cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek // Print the label of this block. 2066079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump if (Stmt* Label = const_cast<Stmt*>(B.getLabel())) { 206742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 206842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (print_edges) 206942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " "; 20706d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2071079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump if (LabelStmt* L = dyn_cast<LabelStmt>(Label)) 20729cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << L->getName(); 2073079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump else if (CaseStmt* C = dyn_cast<CaseStmt>(Label)) { 20749cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << "case "; 2075e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner C->getLHS()->printPretty(OS, Helper, 2076e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner PrintingPolicy(Helper->getLangOpts())); 20779cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek if (C->getRHS()) { 20789cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << " ... "; 2079e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner C->getRHS()->printPretty(OS, Helper, 2080e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner PrintingPolicy(Helper->getLangOpts())); 20819cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek } 2082079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump } else if (isa<DefaultStmt>(Label)) 20839cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << "default"; 2084079bd72439448b78629a28da6b1f8abe2cdeaf4dMike Stump else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Label)) { 20855d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump OS << "catch ("; 2086a1f93631a84621d77aeb627691da85a8991af188Mike Stump if (CS->getExceptionDecl()) 2087a1f93631a84621d77aeb627691da85a8991af188Mike Stump CS->getExceptionDecl()->print(OS, PrintingPolicy(Helper->getLangOpts()), 2088a1f93631a84621d77aeb627691da85a8991af188Mike Stump 0); 2089a1f93631a84621d77aeb627691da85a8991af188Mike Stump else 2090a1f93631a84621d77aeb627691da85a8991af188Mike Stump OS << "..."; 20915d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump OS << ")"; 20925d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump 20935d1d20227878cd03db8b2dd23efd4cedfe874feeMike Stump } else 209442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek assert(false && "Invalid label statement in CFGBlock."); 20956d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 20969cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << ":\n"; 20979cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek } 20986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2099fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek // Iterate through the statements in the block and print them. 2100fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek unsigned j = 1; 21016d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 210242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; 210342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek I != E ; ++I, ++j ) { 21046d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21059cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek // Print the statement # in the basic block and the statement itself. 210642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (print_edges) 210742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " "; 21086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2109a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek OS << llvm::format("%3d", j) << ": "; 21106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 211142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (Helper) 211242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek Helper->setStmtID(j); 21136d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21141c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek print_stmt(OS,Helper,*I); 2115fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 21166d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21179cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek // Print the terminator of this block. 211842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (B.getTerminator()) { 211942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (print_edges) 212042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " "; 21216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21229cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << " T: "; 21236d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 212442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (Helper) Helper->setBlockID(-1); 21256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2126e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner CFGBlockTerminatorPrint TPrinter(OS, Helper, 2127e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner PrintingPolicy(Helper->getLangOpts())); 212842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek TPrinter.Visit(const_cast<Stmt*>(B.getTerminator())); 2129a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek OS << '\n'; 2130fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 21316d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21329cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek if (print_edges) { 21339cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek // Print the predecessors of this block. 213442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " Predecessors (" << B.pred_size() << "):"; 21359cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek unsigned i = 0; 213642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 213742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); 213842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek I != E; ++I, ++i) { 21396d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 214042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (i == 8 || (i-8) == 0) 21419cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << "\n "; 21426d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21439cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << " B" << (*I)->getBlockID(); 21449cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek } 21456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21469cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << '\n'; 21476d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21489cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek // Print the successors of this block. 214942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " Successors (" << B.succ_size() << "):"; 21509cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek i = 0; 215142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 215242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); 215342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek I != E; ++I, ++i) { 21546d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 215542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (i == 8 || (i-8) % 10 == 0) 21569cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << "\n "; 215742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 2158e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (*I) 2159e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump OS << " B" << (*I)->getBlockID(); 2160e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump else 2161e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump OS << " NULL"; 2162fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 21636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21649cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << '\n'; 2165fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 21666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump} 216742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 216842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 216942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek/// dump - A simple pretty printer of a CFG that outputs to stderr. 2170e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); } 217142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 217242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek/// print - A simple pretty printer of a CFG that outputs to an ostream. 2173e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFG::print(llvm::raw_ostream &OS, const LangOptions &LO) const { 2174e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner StmtPrinterHelper Helper(this, LO); 21756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 217642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek // Print the entry block. 217742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek print_block(OS, this, getEntry(), &Helper, true); 21786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 217942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek // Iterate through the CFGBlocks and print them one by one. 218042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { 218142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek // Skip the entry block, because we already printed it. 2182ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek if (&(**I) == &getEntry() || &(**I) == &getExit()) 218342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek continue; 21846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2185ee82d9bdc5025b82de8ce2a4ad4685e0a8b79da9Ted Kremenek print_block(OS, this, **I, &Helper, true); 218642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek } 21876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 218842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek // Print the exit block. 218942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek print_block(OS, this, getExit(), &Helper, true); 2190d0172439194b28bae62a94a0a25d58e6d21e7a14Ted Kremenek OS.flush(); 21916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump} 219242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 219342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek/// dump - A simply pretty printer of a CFGBlock that outputs to stderr. 2194e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const { 2195e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner print(llvm::errs(), cfg, LO); 2196e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner} 219742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 219842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek/// print - A simple pretty printer of a CFGBlock that outputs to an ostream. 219942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek/// Generally this will only be called from CFG::print. 2200e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFGBlock::print(llvm::raw_ostream& OS, const CFG* cfg, 2201e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner const LangOptions &LO) const { 2202e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner StmtPrinterHelper Helper(cfg, LO); 220342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek print_block(OS, cfg, *this, &Helper, true); 2204026473c2175424a039f51ca8949937268721b965Ted Kremenek} 22057dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 2206a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek/// printTerminator - A simple pretty printer of the terminator of a CFGBlock. 2207e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFGBlock::printTerminator(llvm::raw_ostream &OS, 22086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump const LangOptions &LO) const { 2209e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); 2210a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek TPrinter.Visit(const_cast<Stmt*>(getTerminator())); 2211a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek} 2212a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek 2213390e48b15ad93f85bfd1e33b9992c198fa0db475Ted KremenekStmt* CFGBlock::getTerminatorCondition() { 22146d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2215411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (!Terminator) 2216411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek return NULL; 22176d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2218411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek Expr* E = NULL; 22196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2220411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek switch (Terminator->getStmtClass()) { 2221411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek default: 2222411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 22236d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2224411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::ForStmtClass: 2225411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<ForStmt>(Terminator)->getCond(); 2226411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 22276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2228411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::WhileStmtClass: 2229411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<WhileStmt>(Terminator)->getCond(); 2230411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 22316d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2232411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::DoStmtClass: 2233411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<DoStmt>(Terminator)->getCond(); 2234411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 22356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2236411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::IfStmtClass: 2237411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<IfStmt>(Terminator)->getCond(); 2238411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 22396d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2240411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::ChooseExprClass: 2241411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<ChooseExpr>(Terminator)->getCond(); 2242411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 22436d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2244411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::IndirectGotoStmtClass: 2245411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<IndirectGotoStmt>(Terminator)->getTarget(); 2246411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 22476d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2248411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::SwitchStmtClass: 2249411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<SwitchStmt>(Terminator)->getCond(); 2250411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 22516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2252411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::ConditionalOperatorClass: 2253411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<ConditionalOperator>(Terminator)->getCond(); 2254411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 22556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2256411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::BinaryOperatorClass: // '&&' and '||' 2257411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<BinaryOperator>(Terminator)->getLHS(); 2258390e48b15ad93f85bfd1e33b9992c198fa0db475Ted Kremenek break; 22596d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2260390e48b15ad93f85bfd1e33b9992c198fa0db475Ted Kremenek case Stmt::ObjCForCollectionStmtClass: 22616d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return Terminator; 2262411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek } 22636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2264411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek return E ? E->IgnoreParens() : NULL; 2265411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek} 2266411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek 22679c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenekbool CFGBlock::hasBinaryBranchTerminator() const { 22686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 22699c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek if (!Terminator) 22709c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek return false; 22716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 22729c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek Expr* E = NULL; 22736d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 22749c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek switch (Terminator->getStmtClass()) { 22759c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek default: 22769c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek return false; 22776d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 22786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump case Stmt::ForStmtClass: 22799c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::WhileStmtClass: 22809c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::DoStmtClass: 22819c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::IfStmtClass: 22829c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::ChooseExprClass: 22839c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::ConditionalOperatorClass: 22849c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::BinaryOperatorClass: 22856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return true; 22869c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek } 22876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 22889c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek return E ? E->IgnoreParens() : NULL; 22899c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek} 22909c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek 2291a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek 22927dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 22937dba8607e59096014b7139ff20ef00870041d518Ted Kremenek// CFG Graphviz Visualization 22947dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 22957dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 229642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 229742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek#ifndef NDEBUG 22986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stumpstatic StmtPrinterHelper* GraphHelper; 229942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek#endif 230042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 2301e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFG::viewCFG(const LangOptions &LO) const { 230242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek#ifndef NDEBUG 2303e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner StmtPrinterHelper H(this, LO); 230442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek GraphHelper = &H; 230542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek llvm::ViewGraph(this,"CFG"); 230642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek GraphHelper = NULL; 230742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek#endif 230842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek} 230942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 23107dba8607e59096014b7139ff20ef00870041d518Ted Kremeneknamespace llvm { 23117dba8607e59096014b7139ff20ef00870041d518Ted Kremenektemplate<> 23127dba8607e59096014b7139ff20ef00870041d518Ted Kremenekstruct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { 2313006b0eb3e11162d8c06372db813ac9f71a7a16e8Tobias Grosser 2314006b0eb3e11162d8c06372db813ac9f71a7a16e8Tobias Grosser DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 2315006b0eb3e11162d8c06372db813ac9f71a7a16e8Tobias Grosser 2316006b0eb3e11162d8c06372db813ac9f71a7a16e8Tobias Grosser static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph) { 23177dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 2318bd250b44d60622e7c0b60c6def6f6fe7e347addfHartmut Kaiser#ifndef NDEBUG 2319a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek std::string OutSStr; 2320a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek llvm::raw_string_ostream Out(OutSStr); 232142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek print_block(Out,Graph, *Node, GraphHelper, false); 2322a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek std::string& OutStr = Out.str(); 23237dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 23247dba8607e59096014b7139ff20ef00870041d518Ted Kremenek if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 23257dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 23267dba8607e59096014b7139ff20ef00870041d518Ted Kremenek // Process string output to make it nicer... 23277dba8607e59096014b7139ff20ef00870041d518Ted Kremenek for (unsigned i = 0; i != OutStr.length(); ++i) 23287dba8607e59096014b7139ff20ef00870041d518Ted Kremenek if (OutStr[i] == '\n') { // Left justify 23297dba8607e59096014b7139ff20ef00870041d518Ted Kremenek OutStr[i] = '\\'; 23307dba8607e59096014b7139ff20ef00870041d518Ted Kremenek OutStr.insert(OutStr.begin()+i+1, 'l'); 23317dba8607e59096014b7139ff20ef00870041d518Ted Kremenek } 23326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 23337dba8607e59096014b7139ff20ef00870041d518Ted Kremenek return OutStr; 2334bd250b44d60622e7c0b60c6def6f6fe7e347addfHartmut Kaiser#else 2335bd250b44d60622e7c0b60c6def6f6fe7e347addfHartmut Kaiser return ""; 2336bd250b44d60622e7c0b60c6def6f6fe7e347addfHartmut Kaiser#endif 23377dba8607e59096014b7139ff20ef00870041d518Ted Kremenek } 23387dba8607e59096014b7139ff20ef00870041d518Ted Kremenek}; 23397dba8607e59096014b7139ff20ef00870041d518Ted Kremenek} // end namespace llvm 2340