CFG.cpp revision b6f1d782e0dc5fad138a17e6aa0ff6f9bc4788c6
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 15e41611aa2237d06a0ef61db4528fb2883a8defcdTed Kremenek#include "clang/Analysis/CFG.h" 16c310e933a9b023a280f3aa02e5a0c75398555e13Ted Kremenek#include "clang/AST/StmtVisitor.h" 1742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek#include "clang/AST/PrettyPrinter.h" 180cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek#include "llvm/ADT/DenseMap.h" 1919bb356317952445b03ee341c02f6147083c9eeaTed Kremenek#include "llvm/ADT/SmallPtrSet.h" 207dba8607e59096014b7139ff20ef00870041d518Ted Kremenek#include "llvm/Support/GraphWriter.h" 217e3a89db59513acaf7ecfb51ef8998efbb51a5b8Ted Kremenek#include "llvm/Support/Streams.h" 226fa9b88e2c3d47d606a273df2f8d03509bcff0b9Ted Kremenek#include "llvm/Support/Compiler.h" 23274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek#include <llvm/Support/Allocator.h> 24a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek#include <llvm/Support/Format.h> 2583c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 26fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenekusing namespace clang; 27fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 28fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremeneknamespace { 29fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 30befef2f69759d7338e2b7c5ce6c8b6f47fe6e667Ted Kremenek// SaveAndRestore - A utility class that uses RIIA to save and restore 31befef2f69759d7338e2b7c5ce6c8b6f47fe6e667Ted Kremenek// the value of a variable. 32befef2f69759d7338e2b7c5ce6c8b6f47fe6e667Ted Kremenektemplate<typename T> 336fa9b88e2c3d47d606a273df2f8d03509bcff0b9Ted Kremenekstruct VISIBILITY_HIDDEN SaveAndRestore { 34befef2f69759d7338e2b7c5ce6c8b6f47fe6e667Ted Kremenek SaveAndRestore(T& x) : X(x), old_value(x) {} 35befef2f69759d7338e2b7c5ce6c8b6f47fe6e667Ted Kremenek ~SaveAndRestore() { X = old_value; } 36b6f7b72047b3fd3f96a5040e1e4d520a9dea01cdTed Kremenek T get() { return old_value; } 37b6f7b72047b3fd3f96a5040e1e4d520a9dea01cdTed Kremenek 38befef2f69759d7338e2b7c5ce6c8b6f47fe6e667Ted Kremenek T& X; 39befef2f69759d7338e2b7c5ce6c8b6f47fe6e667Ted Kremenek T old_value; 40befef2f69759d7338e2b7c5ce6c8b6f47fe6e667Ted Kremenek}; 416d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 424afa39deaa245592977136d367251ee2c173dd8dDouglas Gregorstatic SourceLocation GetEndLoc(Decl* D) { 43c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek if (VarDecl* VD = dyn_cast<VarDecl>(D)) 44c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek if (Expr* Ex = VD->getInit()) 45c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek return Ex->getSourceRange().getEnd(); 466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 476d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return D->getLocation(); 48c7eb9031159f30a63db960fad4640d779f1617c8Ted 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/// 646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stumpclass VISIBILITY_HIDDEN CFGBuilder : public StmtVisitor<CFGBuilder,CFGBlock*> { 65fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek CFG* cfg; 66fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek CFGBlock* Block; 67fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek CFGBlock* Succ; 68bf15b278a439d73b605ec00a8d3977ef305712f4Ted Kremenek CFGBlock* ContinueTargetBlock; 698a294713e032e4a27bae61c040abb41397952676Ted Kremenek CFGBlock* BreakTargetBlock; 70b5c13b0f4e438391b31dacb87641be7a1b990b57Ted Kremenek CFGBlock* SwitchTerminatedBlock; 71eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek CFGBlock* DefaultCaseBlock; 726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 7319bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // LabelMap records the mapping from Label expressions to their blocks. 740cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek typedef llvm::DenseMap<LabelStmt*,CFGBlock*> LabelMapTy; 750cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek LabelMapTy LabelMap; 766d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 776d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // A list of blocks that end with a "goto" that must be backpatched to their 786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // resolved targets upon completion of CFG construction. 794a2b8a10c4730eb2ceeec24505bef26eb7d829edTed Kremenek typedef std::vector<CFGBlock*> BackpatchBlocksTy; 800cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek BackpatchBlocksTy BackpatchBlocks; 816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8219bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // A list of labels whose address has been taken (for indirect gotos). 8319bb356317952445b03ee341c02f6147083c9eeaTed Kremenek typedef llvm::SmallPtrSet<LabelStmt*,5> LabelSetTy; 8419bb356317952445b03ee341c02f6147083c9eeaTed Kremenek LabelSetTy AddressTakenLabels; 856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 866d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stumppublic: 87026473c2175424a039f51ca8949937268721b965Ted Kremenek explicit CFGBuilder() : cfg(NULL), Block(NULL), Succ(NULL), 888a294713e032e4a27bae61c040abb41397952676Ted Kremenek ContinueTargetBlock(NULL), BreakTargetBlock(NULL), 89eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL) { 90fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek // Create an empty CFG. 916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump cfg = new CFG(); 92fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 94fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek ~CFGBuilder() { delete cfg; } 956d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 96d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // buildCFG - Used by external clients to construct the CFG. 97d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFG* buildCFG(Stmt* Statement); 986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Visitors to walk an AST and construct the CFG. Called by buildCFG. Do not 1006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // call directly! 1016d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 102d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* VisitBreakStmt(BreakStmt* B); 103411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek CFGBlock* VisitCaseStmt(CaseStmt* Terminator); 104514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* VisitCompoundStmt(CompoundStmt* C); 105514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* VisitContinueStmt(ContinueStmt* C); 106295222c1f0926d84de77f076e79903523eeb5dbfTed Kremenek CFGBlock* VisitDefaultStmt(DefaultStmt* D); 107514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* VisitDoStmt(DoStmt* D); 108514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* VisitForStmt(ForStmt* F); 109514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* VisitGotoStmt(GotoStmt* G); 110514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* VisitIfStmt(IfStmt* I); 11119bb356317952445b03ee341c02f6147083c9eeaTed Kremenek CFGBlock* VisitIndirectGotoStmt(IndirectGotoStmt* I); 112514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* VisitLabelStmt(LabelStmt* L); 113514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* VisitNullStmt(NullStmt* Statement); 114514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* VisitObjCForCollectionStmt(ObjCForCollectionStmt* S); 115514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* VisitReturnStmt(ReturnStmt* R); 116514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* VisitStmt(Stmt* Statement); 117514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* VisitSwitchStmt(SwitchStmt* Terminator); 118514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* VisitWhileStmt(WhileStmt* W); 119cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump 1204102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek // FIXME: Add support for ObjC-specific control-flow structures. 121cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump 122274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek // NYS == Not Yet Supported 123274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek CFGBlock* NYS() { 1244102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek badCFG = true; 1254102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek return Block; 1264102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek } 1276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 128e31c0d206b872b056dc42c3af21b11d5de4edfd9Ted Kremenek CFGBlock* VisitObjCAtTryStmt(ObjCAtTryStmt* S); 1296d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump CFGBlock* VisitObjCAtCatchStmt(ObjCAtCatchStmt* S) { 1306d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // FIXME: For now we pretend that @catch and the code it contains does not 1316d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // exit. 132e31c0d206b872b056dc42c3af21b11d5de4edfd9Ted Kremenek return Block; 133e31c0d206b872b056dc42c3af21b11d5de4edfd9Ted Kremenek } 134e31c0d206b872b056dc42c3af21b11d5de4edfd9Ted Kremenek 1356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // FIXME: This is not completely supported. We basically @throw like a 1366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // 'return'. 1372fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek CFGBlock* VisitObjCAtThrowStmt(ObjCAtThrowStmt* S); 138274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek 139b3b0b3624e462c2940f65b86e773bfc300005203Ted Kremenek CFGBlock* VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S); 1406d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 14100c0a30acd5a5c6a1ef837b9bdd2c4c086b70204Ted Kremenek // Blocks. 14200c0a30acd5a5c6a1ef837b9bdd2c4c086b70204Ted Kremenek CFGBlock* VisitBlockExpr(BlockExpr* E) { return NYS(); } 1436d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump CFGBlock* VisitBlockDeclRefExpr(BlockDeclRefExpr* E) { return NYS(); } 1446d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 145d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenekprivate: 146d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* createBlock(bool add_successor = true); 147411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek CFGBlock* addStmt(Stmt* Terminator); 148411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek CFGBlock* WalkAST(Stmt* Terminator, bool AlwaysAddStmt); 149411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek CFGBlock* WalkAST_VisitChildren(Stmt* Terminator); 1504afa39deaa245592977136d367251ee2c173dd8dDouglas Gregor CFGBlock* WalkAST_VisitDeclSubExpr(Decl* D); 151411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek CFGBlock* WalkAST_VisitStmtExpr(StmtExpr* Terminator); 1524e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek bool FinishBlock(CFGBlock* B); 1536d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1544102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek bool badCFG; 155d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek}; 1566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 157898574e7496ba8fd76290079d3a9d06954992734Douglas Gregor// FIXME: Add support for dependent-sized array types in C++? 158898574e7496ba8fd76290079d3a9d06954992734Douglas Gregor// Does it even make sense to build a CFG for an uninstantiated template? 159610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenekstatic VariableArrayType* FindVA(Type* t) { 160610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek while (ArrayType* vt = dyn_cast<ArrayType>(t)) { 161610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek if (VariableArrayType* vat = dyn_cast<VariableArrayType>(vt)) 162610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek if (vat->getSizeExpr()) 163610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek return vat; 1646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 165610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek t = vt->getElementType().getTypePtr(); 166610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek } 1676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 168610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek return 0; 169610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek} 1706d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an 1726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// arbitrary statement. Examples include a single expression or a function 1736d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// body (compound statement). The ownership of the returned CFG is 1746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// transferred to the caller. If CFG construction fails, this method returns 1756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// NULL. 176d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFG* CFGBuilder::buildCFG(Stmt* Statement) { 17719bb356317952445b03ee341c02f6147083c9eeaTed Kremenek assert (cfg); 178d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (!Statement) return NULL; 179d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1804102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek badCFG = false; 1816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1826d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Create an empty block that will serve as the exit block for the CFG. Since 1836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // this is the first block added to the CFG, it will be implicitly registered 1846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // as the exit block. 18549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Succ = createBlock(); 18649af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek assert (Succ == &cfg->getExit()); 18749af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Block = NULL; // the EXIT block is empty. Create all other blocks lazily. 1886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 189d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Visit the statements and create the CFG. 1900d99ecf1d8b9c72f2c4130f5f1be6cf13556b031Ted Kremenek CFGBlock* B = Visit(Statement); 1910d99ecf1d8b9c72f2c4130f5f1be6cf13556b031Ted Kremenek if (!B) B = Succ; 1926d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1930d99ecf1d8b9c72f2c4130f5f1be6cf13556b031Ted Kremenek if (B) { 1946d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Finalize the last constructed block. This usually involves reversing the 1956d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // order of the statements in the block. 19649af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek if (Block) FinishBlock(B); 1976d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Backpatch the gotos whose label -> block mappings we didn't know when we 1996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // encountered them. 2006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(), 201d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek E = BackpatchBlocks.end(); I != E; ++I ) { 2026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 203d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* B = *I; 204d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek GotoStmt* G = cast<GotoStmt>(B->getTerminator()); 205d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); 206d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 207d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // If there is no target for the goto, then we are looking at an 208d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // incomplete AST. Handle this by not registering a successor. 209d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (LI == LabelMap.end()) continue; 2106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2116d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump B->addSuccessor(LI->second); 21219bb356317952445b03ee341c02f6147083c9eeaTed Kremenek } 2136d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21419bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // Add successors to the Indirect Goto Dispatch block (if we have one). 21519bb356317952445b03ee341c02f6147083c9eeaTed Kremenek if (CFGBlock* B = cfg->getIndirectGotoBlock()) 21619bb356317952445b03ee341c02f6147083c9eeaTed Kremenek for (LabelSetTy::iterator I = AddressTakenLabels.begin(), 21719bb356317952445b03ee341c02f6147083c9eeaTed Kremenek E = AddressTakenLabels.end(); I != E; ++I ) { 21819bb356317952445b03ee341c02f6147083c9eeaTed Kremenek 21919bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // Lookup the target block. 22019bb356317952445b03ee341c02f6147083c9eeaTed Kremenek LabelMapTy::iterator LI = LabelMap.find(*I); 22119bb356317952445b03ee341c02f6147083c9eeaTed Kremenek 22219bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // If there is no target block that contains label, then we are looking 22319bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // at an incomplete AST. Handle this by not registering a successor. 22419bb356317952445b03ee341c02f6147083c9eeaTed Kremenek if (LI == LabelMap.end()) continue; 2256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2266d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump B->addSuccessor(LI->second); 22719bb356317952445b03ee341c02f6147083c9eeaTed Kremenek } 2286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 22994b3316ee37743cb60bf552d5616b03d17e277daTed Kremenek Succ = B; 23094b3316ee37743cb60bf552d5616b03d17e277daTed Kremenek } 2316d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Create an empty entry block that has no predecessors. 233322f58d3830da13b419646c071e3ab801518a09cTed Kremenek cfg->setEntry(createBlock()); 2346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2354102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek if (badCFG) { 2364102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek delete cfg; 2374102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek cfg = NULL; 2384102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek return NULL; 2394102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek } 2406d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2416d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // NULL out cfg so that repeated calls to the builder will fail and that the 2426d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // ownership of the constructed CFG is passed to the caller. 243322f58d3830da13b419646c071e3ab801518a09cTed Kremenek CFG* t = cfg; 244322f58d3830da13b419646c071e3ab801518a09cTed Kremenek cfg = NULL; 245322f58d3830da13b419646c071e3ab801518a09cTed Kremenek return t; 246d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 2476d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 248d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek/// createBlock - Used to lazily create blocks that are connected 249d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek/// to the current (global) succcessor. 2506d9828c82c9321f042ab416fd2ffaa3034347d45Mike StumpCFGBlock* CFGBuilder::createBlock(bool add_successor) { 2519438252ad2ecae5338df565ca33c6969e4fbfa41Ted Kremenek CFGBlock* B = cfg->createBlock(); 252d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (add_successor && Succ) B->addSuccessor(Succ); 253d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek return B; 254d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 2556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// FinishBlock - When the last statement has been added to the block, we must 2576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// reverse the statements because they have been inserted in reverse order. 2584e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenekbool CFGBuilder::FinishBlock(CFGBlock* B) { 2594e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (badCFG) 2604e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return false; 2614e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek 262d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek assert (B); 26349af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek B->reverseStmts(); 2644e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return true; 265d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 266d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 2676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// addStmt - Used to add statements/expressions to the current CFGBlock 2689da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek/// "Block". This method calls WalkAST on the passed statement to see if it 2696d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// contains any short-circuit expressions. If so, it recursively creates the 2706d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// necessary blocks for such expressions. It returns the "topmost" block of 2716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// the created blocks, or the original value of "Block" when this method was 2726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// called if no additional blocks are created. 273411cdee0b490f79428c9eb977f25199eb7d21cd8Ted KremenekCFGBlock* CFGBuilder::addStmt(Stmt* Terminator) { 274af603f742491dc4707138c0293d295171fdd51baTed Kremenek if (!Block) Block = createBlock(); 275411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek return WalkAST(Terminator,true); 2769da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek} 2779da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek 2786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// WalkAST - Used by addStmt to walk the subtree of a statement and add extra 2796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// blocks for ternary operators, &&, and ||. We also process "," and 2806d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// DeclStmts (which may contain nested control-flow). 281cd7bf230a77c550115e4a78ee371fc49a7563692Mike StumpCFGBlock* CFGBuilder::WalkAST(Stmt* Terminator, bool AlwaysAddStmt = false) { 282411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek switch (Terminator->getStmtClass()) { 2836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump case Stmt::ConditionalOperatorClass: { 2846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ConditionalOperator* C = cast<ConditionalOperator>(Terminator); 2856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2866d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Create the confluence block that will "merge" the results of the ternary 2876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // expression. 2886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump CFGBlock* ConfluenceBlock = (Block) ? Block : createBlock(); 2896d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ConfluenceBlock->appendStmt(C); 2906d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (!FinishBlock(ConfluenceBlock)) 2916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return 0; 292ecc04c925412f935a936226452407bf8a51ed027Ted Kremenek 2936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Create a block for the LHS expression if there is an LHS expression. A 2946d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // GCC extension allows LHS to be NULL, causing the condition to be the 2956d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // value that is returned instead. 2966d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // e.g: x ?: y is shorthand for: x ? x : y; 2976d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Succ = ConfluenceBlock; 2986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block = NULL; 2996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump CFGBlock* LHSBlock = NULL; 3006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (C->getLHS()) { 3016d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump LHSBlock = Visit(C->getLHS()); 3026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (!FinishBlock(LHSBlock)) 3034e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 3049da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek Block = NULL; 3056d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 3064e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek 3076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Create the block for the RHS expression. 3086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Succ = ConfluenceBlock; 3096d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump CFGBlock* RHSBlock = Visit(C->getRHS()); 3106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (!FinishBlock(RHSBlock)) 3116d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return 0; 3126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3136d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Create the block that will contain the condition. 3146d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block = createBlock(false); 3156d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3166d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (LHSBlock) 3176d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block->addSuccessor(LHSBlock); 3186d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump else { 3196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // If we have no LHS expression, add the ConfluenceBlock as a direct 3206d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // successor for the block containing the condition. Moreover, we need to 3216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // reverse the order of the predecessors in the ConfluenceBlock because 3226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the RHSBlock will have been added to the succcessors already, and we 3236d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // want the first predecessor to the the block containing the expression 3246d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // for the case when the ternary expression evaluates to true. 3256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block->addSuccessor(ConfluenceBlock); 3266d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump assert (ConfluenceBlock->pred_size() == 2); 3276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump std::reverse(ConfluenceBlock->pred_begin(), 3286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ConfluenceBlock->pred_end()); 3296d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 3306d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3316d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block->addSuccessor(RHSBlock); 3326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3336d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block->setTerminator(C); 3346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return addStmt(C->getCond()); 3356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 3366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump case Stmt::ChooseExprClass: { 3386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ChooseExpr* C = cast<ChooseExpr>(Terminator); 3396d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3406d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 3416d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ConfluenceBlock->appendStmt(C); 3426d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (!FinishBlock(ConfluenceBlock)) 3436d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return 0; 3446d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Succ = ConfluenceBlock; 3466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block = NULL; 3476d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump CFGBlock* LHSBlock = Visit(C->getLHS()); 3486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (!FinishBlock(LHSBlock)) 3496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return 0; 3506d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Succ = ConfluenceBlock; 3526d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block = NULL; 3536d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump CFGBlock* RHSBlock = Visit(C->getRHS()); 3546d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (!FinishBlock(RHSBlock)) 3556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return 0; 3566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block = createBlock(false); 3586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block->addSuccessor(LHSBlock); 3596d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block->addSuccessor(RHSBlock); 3606d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block->setTerminator(C); 3616d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return addStmt(C->getCond()); 3626d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 3636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump case Stmt::DeclStmtClass: { 3656d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump DeclStmt *DS = cast<DeclStmt>(Terminator); 3666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (DS->isSingleDecl()) { 3676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block->appendStmt(Terminator); 3686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return WalkAST_VisitDeclSubExpr(DS->getSingleDecl()); 36949a436de368c18c3fc669037aa5211b973b076a9Ted Kremenek } 3706d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump CFGBlock* B = 0; 3726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3736d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy. 3746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump typedef llvm::SmallVector<Decl*,10> BufTy; 3756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump BufTy Buf(DS->decl_begin(), DS->decl_end()); 3766d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3776d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump for (BufTy::reverse_iterator I=Buf.rbegin(), E=Buf.rend(); I!=E; ++I) { 3786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Get the alignment of the new DeclStmt, padding out to >=8 bytes. 3796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8 3806d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ? 8 : llvm::AlignOf<DeclStmt>::Alignment; 3816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3826d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Allocate the DeclStmt using the BumpPtrAllocator. It will get 3836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // automatically freed with the CFG. 3846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump DeclGroupRef DG(*I); 3856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Decl* D = *I; 3866d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump void* Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A); 3876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump DeclStmt* DS = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); 3896d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3906d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Append the fake DeclStmt to block. 3916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block->appendStmt(DS); 3926d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump B = WalkAST_VisitDeclSubExpr(D); 3936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 3946d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return B; 3956d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 3966d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3976d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump case Stmt::AddrLabelExprClass: { 3986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump AddrLabelExpr* A = cast<AddrLabelExpr>(Terminator); 3996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump AddressTakenLabels.insert(A->getLabel()); 4006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 4016d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (AlwaysAddStmt) Block->appendStmt(Terminator); 4026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return Block; 4036d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 4046d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 4056d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump case Stmt::StmtExprClass: 4066d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return WalkAST_VisitStmtExpr(cast<StmtExpr>(Terminator)); 4076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 4086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump case Stmt::SizeOfAlignOfExprClass: { 4096d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump SizeOfAlignOfExpr* E = cast<SizeOfAlignOfExpr>(Terminator); 4106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 4116d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // VLA types have expressions that must be evaluated. 4126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (E->isArgumentType()) { 4136d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump for (VariableArrayType* VA = FindVA(E->getArgumentType().getTypePtr()); 4146d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) 4156d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump addStmt(VA->getSizeExpr()); 4166d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 4176d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Expressions in sizeof/alignof are not evaluated and thus have no 4186d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // control flow. 4196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump else 4206d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block->appendStmt(Terminator); 4216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 4226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return Block; 4236d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 4246d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 4256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump case Stmt::BinaryOperatorClass: { 4266d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump BinaryOperator* B = cast<BinaryOperator>(Terminator); 4276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 4286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (B->isLogicalOp()) { // && or || 4296d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump CFGBlock* ConfluenceBlock = (Block) ? Block : createBlock(); 4306d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ConfluenceBlock->appendStmt(B); 4314e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(ConfluenceBlock)) 4324e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 433f50ec1026d23282d94699f079ffb5edb9dfd951fTed Kremenek 4346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // create the block evaluating the LHS 4356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump CFGBlock* LHSBlock = createBlock(false); 4366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump LHSBlock->setTerminator(B); 4376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 4386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // create the block evaluating the RHS 43949a436de368c18c3fc669037aa5211b973b076a9Ted Kremenek Succ = ConfluenceBlock; 44049a436de368c18c3fc669037aa5211b973b076a9Ted Kremenek Block = NULL; 4416d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump CFGBlock* RHSBlock = Visit(B->getRHS()); 4424e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(RHSBlock)) 4434e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 4447926f7c45c53862f516ea9f504ba38fe89eac329Ted Kremenek 4456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now link the LHSBlock with RHSBlock. 4466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (B->getOpcode() == BinaryOperator::LOr) { 4476d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump LHSBlock->addSuccessor(ConfluenceBlock); 4486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump LHSBlock->addSuccessor(RHSBlock); 4496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else { 4506d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump assert (B->getOpcode() == BinaryOperator::LAnd); 4516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump LHSBlock->addSuccessor(RHSBlock); 4526d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump LHSBlock->addSuccessor(ConfluenceBlock); 453c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek } 454c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek 4556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Generate the blocks for evaluating the LHS. 4566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block = LHSBlock; 4576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return addStmt(B->getLHS()); 4586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else if (B->getOpcode() == BinaryOperator::Comma) { // , 4596d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block->appendStmt(B); 4606d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump addStmt(B->getRHS()); 4616d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return addStmt(B->getLHS()); 46219bb356317952445b03ee341c02f6147083c9eeaTed Kremenek } 463610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek 4646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump break; 4656d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 4666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 46700c0a30acd5a5c6a1ef837b9bdd2c4c086b70204Ted Kremenek // Blocks: No support for blocks ... yet 4686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump case Stmt::BlockExprClass: 4696d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump case Stmt::BlockDeclRefExprClass: 4706d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return NYS(); 4716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 4726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump case Stmt::ParenExprClass: 4736d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return WalkAST(cast<ParenExpr>(Terminator)->getSubExpr(), AlwaysAddStmt); 4746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 475cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump case Stmt::CallExprClass: { 47601bc160ffccc03e4c0583acf82bd7ab80494219aChris Lattner // If this is a call to a no-return function, this stops the block here. 47701bc160ffccc03e4c0583acf82bd7ab80494219aChris Lattner FunctionDecl *FD = cast<CallExpr>(Terminator)->getDirectCallee(); 47801bc160ffccc03e4c0583acf82bd7ab80494219aChris Lattner if (FD == 0 || !FD->hasAttr<NoReturnAttr>()) 479cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump break; 480cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump 48101bc160ffccc03e4c0583acf82bd7ab80494219aChris Lattner if (Block && !FinishBlock(Block)) 48201bc160ffccc03e4c0583acf82bd7ab80494219aChris Lattner return 0; 483cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump 484cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump // Create new block with no successor for the remaining pieces. 485cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump Block = createBlock(false); 486cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump Block->appendStmt(Terminator); 487cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump 488cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump // Wire this to the exit block directly. 489cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump Block->addSuccessor(&cfg->getExit()); 490cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump 491cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump return WalkAST_VisitChildren(Terminator); 492cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump } 493cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump 4946d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump default: 49501bc160ffccc03e4c0583acf82bd7ab80494219aChris Lattner // TODO: We can follow objective-c methods (message sends). 4966d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump break; 4979da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek }; 4986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 499411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (AlwaysAddStmt) Block->appendStmt(Terminator); 500411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek return WalkAST_VisitChildren(Terminator); 5019da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek} 5026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 5036d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// WalkAST_VisitDeclSubExpr - Utility method to add block-level expressions for 5046d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// initializers in Decls. 5054afa39deaa245592977136d367251ee2c173dd8dDouglas GregorCFGBlock* CFGBuilder::WalkAST_VisitDeclSubExpr(Decl* D) { 506c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek VarDecl* VD = dyn_cast<VarDecl>(D); 507c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek 508c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek if (!VD) 509d660322ccf21fc9a319a62ad42907c631504d4cdTed Kremenek return Block; 5106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 511c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek Expr* Init = VD->getInit(); 5126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 513fcd06f77beadf0642bd008fdf596378f8570b55cTed Kremenek if (Init) { 51454cc43fd6687a0e7db06b6e0ae6602d86fe09e37Mike Stump // Optimization: Don't create separate block-level statements for literals. 515fcd06f77beadf0642bd008fdf596378f8570b55cTed Kremenek switch (Init->getStmtClass()) { 516fcd06f77beadf0642bd008fdf596378f8570b55cTed Kremenek case Stmt::IntegerLiteralClass: 517fcd06f77beadf0642bd008fdf596378f8570b55cTed Kremenek case Stmt::CharacterLiteralClass: 518fcd06f77beadf0642bd008fdf596378f8570b55cTed Kremenek case Stmt::StringLiteralClass: 519fcd06f77beadf0642bd008fdf596378f8570b55cTed Kremenek break; 520fcd06f77beadf0642bd008fdf596378f8570b55cTed Kremenek default: 521fcd06f77beadf0642bd008fdf596378f8570b55cTed Kremenek Block = addStmt(Init); 522fcd06f77beadf0642bd008fdf596378f8570b55cTed Kremenek } 523ae2a98cd35a67ce5e5d1eeec94c0ce7851b6b72cTed Kremenek } 5246d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 525fcd06f77beadf0642bd008fdf596378f8570b55cTed Kremenek // If the type of VD is a VLA, then we must process its size expressions. 526fcd06f77beadf0642bd008fdf596378f8570b55cTed Kremenek for (VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); VA != 0; 527fcd06f77beadf0642bd008fdf596378f8570b55cTed Kremenek VA = FindVA(VA->getElementType().getTypePtr())) 5286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block = addStmt(VA->getSizeExpr()); 5296d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 530b49e1aa3ef2ec0d84dfc36e85c41e5f8fd145100Ted Kremenek return Block; 531b49e1aa3ef2ec0d84dfc36e85c41e5f8fd145100Ted Kremenek} 532b49e1aa3ef2ec0d84dfc36e85c41e5f8fd145100Ted Kremenek 5336d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// WalkAST_VisitChildren - Utility method to call WalkAST on the children of a 5346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// Stmt. 535411cdee0b490f79428c9eb977f25199eb7d21cd8Ted KremenekCFGBlock* CFGBuilder::WalkAST_VisitChildren(Stmt* Terminator) { 5369da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek CFGBlock* B = Block; 53754cc43fd6687a0e7db06b6e0ae6602d86fe09e37Mike Stump for (Stmt::child_iterator I = Terminator->child_begin(), 53854cc43fd6687a0e7db06b6e0ae6602d86fe09e37Mike Stump E = Terminator->child_end(); 5399da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek I != E; ++I) 540322f58d3830da13b419646c071e3ab801518a09cTed Kremenek if (*I) B = WalkAST(*I); 5416d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 5429da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek return B; 5439da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek} 5449da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek 54515c27a84e529f1195286c122affe0b2991fcb5ffTed Kremenek/// WalkAST_VisitStmtExpr - Utility method to handle (nested) statement 54615c27a84e529f1195286c122affe0b2991fcb5ffTed Kremenek/// expressions (a GCC extension). 547411cdee0b490f79428c9eb977f25199eb7d21cd8Ted KremenekCFGBlock* CFGBuilder::WalkAST_VisitStmtExpr(StmtExpr* Terminator) { 548411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek Block->appendStmt(Terminator); 5496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return VisitCompoundStmt(Terminator->getSubStmt()); 55015c27a84e529f1195286c122affe0b2991fcb5ffTed Kremenek} 55115c27a84e529f1195286c122affe0b2991fcb5ffTed Kremenek 552d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek/// VisitStmt - Handle statements with no branching control flow. 553d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitStmt(Stmt* Statement) { 5546d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // We cannot assume that we are in the middle of a basic block, since the CFG 5556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // might only be constructed for this single statement. If we have no current 5566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // basic block, just create one lazily. 557d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (!Block) Block = createBlock(); 5586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 5596d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Simply add the statement to the current block. We actually insert 5606d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // statements in reverse order; this order is reversed later when processing 5616d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the containing element in the AST. 56249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek addStmt(Statement); 56349af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek 564d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek return Block; 565d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 566d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 567d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitNullStmt(NullStmt* Statement) { 568d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek return Block; 569d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 570d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 571d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) { 5726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 573ed47fc67b8eeabacbbbdf853ba45f4900619904bTed Kremenek CFGBlock* LastBlock = Block; 574d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 575d34066c224f782056c18f154abe04ef590473fd9Ted Kremenek for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); 576d34066c224f782056c18f154abe04ef590473fd9Ted Kremenek I != E; ++I ) { 577a716d7a575c55805c4b90e07cccf61b9cc0960b8Ted Kremenek LastBlock = Visit(*I); 578d34066c224f782056c18f154abe04ef590473fd9Ted Kremenek } 579d34066c224f782056c18f154abe04ef590473fd9Ted Kremenek 580a716d7a575c55805c4b90e07cccf61b9cc0960b8Ted Kremenek return LastBlock; 581d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 582fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 583d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { 5846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // We may see an if statement in the middle of a basic block, or it may be the 5856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // first statement we are processing. In either case, we create a new basic 5866d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block. First, we create the blocks for the then...else statements, and 5876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // then we create the block containing the if statement. If we were in the 5886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // middle of a block, we stop processing that block and reverse its 5896d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // statements. That block is then the implicit successor for the "then" and 5906d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // "else" clauses. 5916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 5926d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // The block we were proccessing is now finished. Make it the successor 5936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block. 5946d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (Block) { 595d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Succ = Block; 5964e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 5974e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 598c310e933a9b023a280f3aa02e5a0c75398555e13Ted Kremenek } 5996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 600b6f1d782e0dc5fad138a17e6aa0ff6f9bc4788c6Ted Kremenek // Process the false branch. 601d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* ElseBlock = Succ; 6026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 603d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Stmt* Else = I->getElse()) { 604d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> sv(Succ); 6056d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 606d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // NULL out Block so that the recursive call to Visit will 6076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // create a new basic block. 608d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = NULL; 609b6f7b72047b3fd3f96a5040e1e4d520a9dea01cdTed Kremenek ElseBlock = Visit(Else); 6106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 611b6f7b72047b3fd3f96a5040e1e4d520a9dea01cdTed Kremenek if (!ElseBlock) // Can occur when the Else body has all NullStmts. 612b6f7b72047b3fd3f96a5040e1e4d520a9dea01cdTed Kremenek ElseBlock = sv.get(); 6134e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek else if (Block) { 6144e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(ElseBlock)) 6154e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 6164e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 617c310e933a9b023a280f3aa02e5a0c75398555e13Ted Kremenek } 6186d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 619b6f1d782e0dc5fad138a17e6aa0ff6f9bc4788c6Ted Kremenek // Process the true branch. 620d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* ThenBlock; 621d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek { 622d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Stmt* Then = I->getThen(); 623d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek assert (Then); 624d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> sv(Succ); 6256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block = NULL; 626b6f7b72047b3fd3f96a5040e1e4d520a9dea01cdTed Kremenek ThenBlock = Visit(Then); 6276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 628dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek if (!ThenBlock) { 629dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek // We can reach here if the "then" body has all NullStmts. 630dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek // Create an empty block so we can distinguish between true and false 631dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek // branches in path-sensitive analyses. 632dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek ThenBlock = createBlock(false); 633dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek ThenBlock->addSuccessor(sv.get()); 6346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else if (Block) { 6354e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(ThenBlock)) 6364e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 6376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 6380cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek } 639d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 6406d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now create a new block containing the if statement. 641d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(false); 6426d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 643d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Set the terminator of the new block to the If statement. 644d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->setTerminator(I); 6456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 646d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Now add the successors. 647d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->addSuccessor(ThenBlock); 648d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->addSuccessor(ElseBlock); 6496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 6506d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Add the condition as the last statement in the new block. This may create 6516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // new blocks as the condition may contain control-flow. Any newly created 6526d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // blocks will be pointed to be "Block". 653a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek return addStmt(I->getCond()->IgnoreParens()); 654d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 6556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 6566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 657d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitReturnStmt(ReturnStmt* R) { 6586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // If we were in the middle of a block we stop processing that block and 6596d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // reverse its statements. 660d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // 6616d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // NOTE: If a "return" appears in the middle of a block, this means that the 6626d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // code afterwards is DEAD (unreachable). We still keep a basic block 6636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // for that code; a simple "mark-and-sweep" from the entry block will be 6646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // able to report such dead blocks. 665d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Block) FinishBlock(Block); 666d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 667d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Create the new block. 668d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(false); 6696d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 670d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // The Exit block is the only successor. 671d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->addSuccessor(&cfg->getExit()); 6726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 6736d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Add the return statement to the block. This may create new blocks if R 6746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // contains control-flow (short-circuit operations). 67549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek return addStmt(R); 676d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 6770cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek 678d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt* L) { 679d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Get the block of the labeled statement. Add it to our map. 6802677ea871a25aa79f9db360f6ed10584c02267adTed Kremenek Visit(L->getSubStmt()); 6812677ea871a25aa79f9db360f6ed10584c02267adTed Kremenek CFGBlock* LabelBlock = Block; 6826d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 68316e4dc8073449ebbeee098941c062ad8b2d3bcd5Ted Kremenek if (!LabelBlock) // This can happen when the body is empty, i.e. 68416e4dc8073449ebbeee098941c062ad8b2d3bcd5Ted Kremenek LabelBlock=createBlock(); // scopes that only contains NullStmts. 6856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 686d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek assert (LabelMap.find(L) == LabelMap.end() && "label already in map"); 687d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LabelMap[ L ] = LabelBlock; 6886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 6896d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Labels partition blocks, so this is the end of the basic block we were 6906d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // processing (L is the block's label). Because this is label (and we have 6916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // already processed the substatement) there is no extra control-flow to worry 6926d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // about. 6939cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek LabelBlock->setLabel(L); 6944e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(LabelBlock)) 6954e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 6966d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 6976d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // We set Block to NULL to allow lazy creation of a new block (if necessary); 698d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = NULL; 6996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 700d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // This block is now the implicit successor of other blocks. 701d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Succ = LabelBlock; 7026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 703d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek return LabelBlock; 704d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 70531dcd3c8c4df5a656f58f50ea73afc177c101c67Ted Kremenek 706d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) { 7076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Goto is a control-flow statement. Thus we stop processing the current 7086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block and create a new one. 709d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Block) FinishBlock(Block); 710d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(false); 711d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->setTerminator(G); 7126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 7136d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // If we already know the mapping to the label block add the successor now. 714d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LabelMapTy::iterator I = LabelMap.find(G->getLabel()); 7156d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 716d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (I == LabelMap.end()) 717d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // We will need to backpatch this block later. 718d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek BackpatchBlocks.push_back(Block); 719d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek else 720d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->addSuccessor(I->second); 721d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 7226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return Block; 723d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 724d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 725d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { 7266d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // "for" is a control-flow statement. Thus we stop processing the current 7276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block. 7286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 729d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* LoopSuccessor = NULL; 7306d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 731d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Block) { 7324e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 7334e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 734d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LoopSuccessor = Block; 7356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else LoopSuccessor = Succ; 7366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 7376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Because of short-circuit evaluation, the condition of the loop can span 7386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 7396d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // evaluate the condition. 74049af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* ExitConditionBlock = createBlock(false); 74149af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* EntryConditionBlock = ExitConditionBlock; 7426d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 74349af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek // Set the terminator for the "exit" condition block. 7446d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ExitConditionBlock->setTerminator(F); 7456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 7466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now add the actual condition to the condition block. Because the condition 7476d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // itself may contain control-flow, new blocks may be created. 74849af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek if (Stmt* C = F->getCond()) { 74949af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Block = ExitConditionBlock; 75049af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek EntryConditionBlock = addStmt(C); 7514e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 7524e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(EntryConditionBlock)) 7534e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 7544e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 75549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek } 756d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 7576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // The condition block is the implicit successor for the loop body as well as 7586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // any code above the loop. 75949af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Succ = EntryConditionBlock; 7606d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 761d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Now create the loop body. 762d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek { 763d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek assert (F->getBody()); 7646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 765d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Save the current values for Block, Succ, and continue and break targets 766d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 767d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek save_continue(ContinueTargetBlock), 7686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump save_break(BreakTargetBlock); 7696d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 770af603f742491dc4707138c0293d295171fdd51baTed Kremenek // Create a new block to contain the (bottom) of the loop body. 771af603f742491dc4707138c0293d295171fdd51baTed Kremenek Block = NULL; 7726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 773e933450535ab077b95e59f929a4ccb25b6f360e6Ted Kremenek if (Stmt* I = F->getInc()) { 7746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Generate increment code in its own basic block. This is the target of 7756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // continue statements. 776d0172439194b28bae62a94a0a25d58e6d21e7a14Ted Kremenek Succ = Visit(I); 7776d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else { 7786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // No increment code. Create a special, empty, block that is used as the 7796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // target block for "looping back" to the start of the loop. 7803575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek assert(Succ == EntryConditionBlock); 7813575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek Succ = createBlock(); 782e933450535ab077b95e59f929a4ccb25b6f360e6Ted Kremenek } 7836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 7843575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek // Finish up the increment (or empty) block if it hasn't been already. 7853575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek if (Block) { 7863575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek assert(Block == Succ); 7874e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 7884e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 7893575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek Block = 0; 7903575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek } 7916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 7923575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek ContinueTargetBlock = Succ; 7936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 7943575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek // The starting block for the loop increment is the block that should 7953575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek // represent the 'loop target' for looping back to the start of the loop. 7963575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek ContinueTargetBlock->setLoopTarget(F); 7973575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek 798e933450535ab077b95e59f929a4ccb25b6f360e6Ted Kremenek // All breaks should go to the code following the loop. 7996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump BreakTargetBlock = LoopSuccessor; 8006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8016d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now populate the body block, and in the process create new blocks as we 8026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // walk the body of the loop. 8036d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump CFGBlock* BodyBlock = Visit(F->getBody()); 804af603f742491dc4707138c0293d295171fdd51baTed Kremenek 805af603f742491dc4707138c0293d295171fdd51baTed Kremenek if (!BodyBlock) 806a9d996dbeb719200c4a9d86f68166a237583025fTed Kremenek BodyBlock = EntryConditionBlock; // can happen for "for (...;...; ) ;" 8074e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek else if (Block) { 8084e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(BodyBlock)) 8094e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 8106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 8116d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 81249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek // This new body block is a successor to our "exit" condition block. 81349af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek ExitConditionBlock->addSuccessor(BodyBlock); 814d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek } 8156d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8166d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Link up the condition block with the code that follows the loop. (the 8176d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // false branch). 81849af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek ExitConditionBlock->addSuccessor(LoopSuccessor); 8196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 820d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // If the loop contains initialization, create a new block for those 8216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // statements. This block can also contain statements that precede the loop. 822d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Stmt* I = F->getInit()) { 823d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(); 82449af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek return addStmt(I); 8256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else { 8266d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // There is no loop initialization. We are thus basically a while loop. 8276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // NULL out Block to force lazy block construction. 8282bac4ea765a4a6e1f6149964663f62d4bca6743bTed Kremenek Block = NULL; 8295482713d70ecbfe608940018046aa248b3d03443Ted Kremenek Succ = EntryConditionBlock; 83049af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek return EntryConditionBlock; 8312bac4ea765a4a6e1f6149964663f62d4bca6743bTed Kremenek } 832d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 833d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 834514de5a21645900c92cf4f4f7313d6f66945d134Ted KremenekCFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { 835514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // Objective-C fast enumeration 'for' statements: 836514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC 837514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 838514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // for ( Type newVariable in collection_expression ) { statements } 839514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 840514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // becomes: 841514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 842514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // prologue: 843514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1. collection_expression 844514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // T. jump to loop_entry 845514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // loop_entry: 8464cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // 1. side-effects of element expression 847514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1. ObjCForCollectionStmt [performs binding to newVariable] 848514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil] 849514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // TB: 850514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // statements 851514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // T. jump to loop_entry 852514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // FB: 853514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // what comes after 854514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 855514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // and 856514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 857514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // Type existingItem; 858514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // for ( existingItem in expression ) { statements } 859514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 860514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // becomes: 861514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 8626d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the same with newVariable replaced with existingItem; the binding works 8636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the same except that for one ObjCForCollectionStmt::getElement() returns 8646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // a DeclStmt and the other returns a DeclRefExpr. 865514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 8666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 867514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* LoopSuccessor = 0; 8686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 869514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek if (Block) { 8704e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 8714e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 872514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek LoopSuccessor = Block; 873514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek Block = 0; 8746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else LoopSuccessor = Succ; 8756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8764cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Build the condition blocks. 8774cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek CFGBlock* ExitConditionBlock = createBlock(false); 8784cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek CFGBlock* EntryConditionBlock = ExitConditionBlock; 8796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8804cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Set the terminator for the "exit" condition block. 8816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ExitConditionBlock->setTerminator(S); 8826d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // The last statement in the block should be the ObjCForCollectionStmt, which 8846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // performs the actual binding to 'element' and determines if there are any 8856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // more items in the collection. 8864cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek ExitConditionBlock->appendStmt(S); 8874cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek Block = ExitConditionBlock; 8886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8894cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Walk the 'element' expression to see if there are any side-effects. We 8906d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // generate new blocks as necesary. We DON'T add the statement by default to 8916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the CFG unless it contains control-flow. 8924cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek EntryConditionBlock = WalkAST(S->getElement(), false); 8936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (Block) { 8944e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(EntryConditionBlock)) 8954e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 8964e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek Block = 0; 8974e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 8986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // The condition block is the implicit successor for the loop body as well as 9006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // any code above the loop. 9014cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek Succ = EntryConditionBlock; 9026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9034cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Now create the true branch. 9046d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump { 9054cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Save the current values for Succ, continue and break targets. 9064cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek SaveAndRestore<CFGBlock*> save_Succ(Succ), 9076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump save_continue(ContinueTargetBlock), save_break(BreakTargetBlock); 9086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9094cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek BreakTargetBlock = LoopSuccessor; 9106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ContinueTargetBlock = EntryConditionBlock; 9116d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9124cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek CFGBlock* BodyBlock = Visit(S->getBody()); 9136d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9144cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek if (!BodyBlock) 9154cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;" 9164e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek else if (Block) { 9174e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(BodyBlock)) 9184e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 9194e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 9206d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9214cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // This new body block is a successor to our "exit" condition block. 9224cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek ExitConditionBlock->addSuccessor(BodyBlock); 9234cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek } 9246d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9254cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Link up the condition block with the code that follows the loop. 9264cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // (the false branch). 9274cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek ExitConditionBlock->addSuccessor(LoopSuccessor); 9284cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek 929514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // Now create a prologue block to contain the collection expression. 9304cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek Block = createBlock(); 931514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek return addStmt(S->getCollection()); 9326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump} 9336d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 934b3b0b3624e462c2940f65b86e773bfc300005203Ted KremenekCFGBlock* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S) { 935b3b0b3624e462c2940f65b86e773bfc300005203Ted Kremenek // FIXME: Add locking 'primitives' to CFG for @synchronized. 9366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 937b3b0b3624e462c2940f65b86e773bfc300005203Ted Kremenek // Inline the body. 938da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek CFGBlock *SyncBlock = Visit(S->getSynchBody()); 9396d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 940da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek // The sync body starts its own basic block. This makes it a little easier 941da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek // for diagnostic clients. 942da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek if (SyncBlock) { 943da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek if (!FinishBlock(SyncBlock)) 944da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek return 0; 9456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 946da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek Block = 0; 947da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek } 9486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 949da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek Succ = SyncBlock; 9506d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 951b3b0b3624e462c2940f65b86e773bfc300005203Ted Kremenek // Inline the sync expression. 952b3b0b3624e462c2940f65b86e773bfc300005203Ted Kremenek return Visit(S->getSynchExpr()); 953b3b0b3624e462c2940f65b86e773bfc300005203Ted Kremenek} 9546d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 955e31c0d206b872b056dc42c3af21b11d5de4edfd9Ted KremenekCFGBlock* CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt* S) { 95690658ec72542df44eb462c69056184d2946bdbceTed Kremenek return NYS(); 957e31c0d206b872b056dc42c3af21b11d5de4edfd9Ted Kremenek} 958514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek 959d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { 9606d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // "while" is a control-flow statement. Thus we stop processing the current 9616d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block. 9626d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 963d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* LoopSuccessor = NULL; 9646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 965d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Block) { 9664e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 9674e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 968d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LoopSuccessor = Block; 9696d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else LoopSuccessor = Succ; 9706d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Because of short-circuit evaluation, the condition of the loop can span 9726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 9736d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // evaluate the condition. 97449af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* ExitConditionBlock = createBlock(false); 97549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* EntryConditionBlock = ExitConditionBlock; 9766d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 97749af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek // Set the terminator for the "exit" condition block. 97849af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek ExitConditionBlock->setTerminator(W); 9796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9806d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now add the actual condition to the condition block. Because the condition 9816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // itself may contain control-flow, new blocks may be created. Thus we update 9826d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // "Succ" after adding the condition. 98349af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek if (Stmt* C = W->getCond()) { 98449af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Block = ExitConditionBlock; 98549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek EntryConditionBlock = addStmt(C); 986f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek assert(Block == EntryConditionBlock); 9874e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 9884e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(EntryConditionBlock)) 9894e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 9904e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 99149af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek } 9926d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // The condition block is the implicit successor for the loop body as well as 9946d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // any code above the loop. 99549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Succ = EntryConditionBlock; 9966d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 997d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Process the loop body. 998d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek { 999f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek assert(W->getBody()); 1000d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1001d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Save the current values for Block, Succ, and continue and break targets 1002d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1003d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek save_continue(ContinueTargetBlock), 1004d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek save_break(BreakTargetBlock); 1005f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek 10066d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Create an empty block to represent the transition block for looping back 10076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // to the head of the loop. 1008f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek Block = 0; 1009f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek assert(Succ == EntryConditionBlock); 1010f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek Succ = createBlock(); 1011f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek Succ->setLoopTarget(W); 10126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ContinueTargetBlock = Succ; 10136d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1014d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // All breaks should go to the code following the loop. 1015d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek BreakTargetBlock = LoopSuccessor; 10166d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1017d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // NULL out Block to force lazy instantiation of blocks for the body. 1018f752fcfae84fbf21b78383bf2461633382d51844Ted Kremenek Block = NULL; 10196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1020d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Create the body. The returned block is the entry to the loop body. 1021d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* BodyBlock = Visit(W->getBody()); 10226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1023af603f742491dc4707138c0293d295171fdd51baTed Kremenek if (!BodyBlock) 1024a9d996dbeb719200c4a9d86f68166a237583025fTed Kremenek BodyBlock = EntryConditionBlock; // can happen for "while(...) ;" 10254e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek else if (Block) { 10264e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(BodyBlock)) 10274e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 10284e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 10296d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1030d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Add the loop body entry as a successor to the condition. 103149af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek ExitConditionBlock->addSuccessor(BodyBlock); 1032bf15b278a439d73b605ec00a8d3977ef305712f4Ted Kremenek } 10336d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Link up the condition block with the code that follows the loop. (the 10356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // false branch). 103649af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek ExitConditionBlock->addSuccessor(LoopSuccessor); 10376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // There can be no more statements in the condition block since we loop back 10396d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // to this block. NULL out Block to force lazy creation of another block. 1040d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = NULL; 10416d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1042d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Return the condition block, which is the dominating block for the loop. 10435482713d70ecbfe608940018046aa248b3d03443Ted Kremenek Succ = EntryConditionBlock; 104449af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek return EntryConditionBlock; 1045d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 10466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10472fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted KremenekCFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) { 10482fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek // FIXME: This isn't complete. We basically treat @throw like a return 10492fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek // statement. 10506d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // If we were in the middle of a block we stop processing that block and 10526d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // reverse its statements. 10534e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 10544e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 10554e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 10564e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 10576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10582fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek // Create the new block. 10592fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek Block = createBlock(false); 10606d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10612fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek // The Exit block is the only successor. 10622fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek Block->addSuccessor(&cfg->getExit()); 10636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Add the statement to the block. This may create new blocks if S contains 10656d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // control-flow (short-circuit operations). 10662fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek return addStmt(S); 10672fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek} 1068989d52d469df0c202f7de82f54407066c7db2e63Ted Kremenek 1069d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitDoStmt(DoStmt* D) { 1070d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // "do...while" is a control-flow statement. Thus we stop processing the 1071d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // current block. 10726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1073d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* LoopSuccessor = NULL; 10746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1075d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Block) { 10764e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 10774e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 1078d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LoopSuccessor = Block; 10796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else LoopSuccessor = Succ; 10806d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Because of short-circuit evaluation, the condition of the loop can span 10826d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 10836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // evaluate the condition. 108449af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* ExitConditionBlock = createBlock(false); 108549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* EntryConditionBlock = ExitConditionBlock; 10866d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 108749af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek // Set the terminator for the "exit" condition block. 10886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ExitConditionBlock->setTerminator(D); 10896d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10906d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now add the actual condition to the condition block. Because the condition 10916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // itself may contain control-flow, new blocks may be created. 109249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek if (Stmt* C = D->getCond()) { 109349af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Block = ExitConditionBlock; 109449af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek EntryConditionBlock = addStmt(C); 10954e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 10964e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(EntryConditionBlock)) 10974e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 10984e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 109949af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek } 11006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11015482713d70ecbfe608940018046aa248b3d03443Ted Kremenek // The condition block is the implicit successor for the loop body. 110249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Succ = EntryConditionBlock; 110349af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek 1104d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Process the loop body. 110549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* BodyBlock = NULL; 1106d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek { 1107d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek assert (D->getBody()); 11086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1109d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Save the current values for Block, Succ, and continue and break targets 1110d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1111d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek save_continue(ContinueTargetBlock), 1112d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek save_break(BreakTargetBlock); 11136d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1114d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // All continues within this loop should go to the condition block 111549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek ContinueTargetBlock = EntryConditionBlock; 11166d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1117d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // All breaks should go to the code following the loop. 1118d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek BreakTargetBlock = LoopSuccessor; 11196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1120d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // NULL out Block to force lazy instantiation of blocks for the body. 1121b5c13b0f4e438391b31dacb87641be7a1b990b57Ted Kremenek Block = NULL; 11226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1123d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Create the body. The returned block is the entry to the loop body. 1124d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek BodyBlock = Visit(D->getBody()); 11256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1126af603f742491dc4707138c0293d295171fdd51baTed Kremenek if (!BodyBlock) 1127a9d996dbeb719200c4a9d86f68166a237583025fTed Kremenek BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" 11284e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek else if (Block) { 11294e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(BodyBlock)) 11304e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 11314e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 11326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11338f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek // Add an intermediate block between the BodyBlock and the 11346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // ExitConditionBlock to represent the "loop back" transition. Create an 11356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // empty block to represent the transition block for looping back to the 11366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // head of the loop. 11378f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek // FIXME: Can we do this more efficiently without adding another block? 11388f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek Block = NULL; 11398f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek Succ = BodyBlock; 11408f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek CFGBlock *LoopBackBlock = createBlock(); 11418f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek LoopBackBlock->setLoopTarget(D); 11426d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1143d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Add the loop body entry as a successor to the condition. 11448f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek ExitConditionBlock->addSuccessor(LoopBackBlock); 1145b5c13b0f4e438391b31dacb87641be7a1b990b57Ted Kremenek } 11466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1147d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Link up the condition block with the code that follows the loop. 1148d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // (the false branch). 114949af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek ExitConditionBlock->addSuccessor(LoopSuccessor); 11506d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // There can be no more statements in the body block(s) since we loop back to 11526d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the body. NULL out Block to force lazy creation of another block. 1153d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = NULL; 11546d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1155d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Return the loop body, which is the dominating block for the loop. 11565482713d70ecbfe608940018046aa248b3d03443Ted Kremenek Succ = BodyBlock; 1157d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek return BodyBlock; 1158d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 1159d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1160d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) { 1161d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // "continue" is a control-flow statement. Thus we stop processing the 1162d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // current block. 11634e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 11644e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 11654e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 11664e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 11676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1168d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Now create a new block that ends with the continue statement. 1169d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(false); 1170d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->setTerminator(C); 11716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1172d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // If there is no target for the continue, then we are looking at an 1173235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek // incomplete AST. This means the CFG cannot be constructed. 1174235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek if (ContinueTargetBlock) 1175235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek Block->addSuccessor(ContinueTargetBlock); 1176235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek else 1177235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek badCFG = true; 11786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1179d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek return Block; 1180d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 1181d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1182d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitBreakStmt(BreakStmt* B) { 11836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // "break" is a control-flow statement. Thus we stop processing the current 11846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block. 11854e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 11864e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 11874e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 11884e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 11896d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1190cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump // Now create a new block that ends with the break statement. 1191d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(false); 1192d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->setTerminator(B); 11936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11946d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // If there is no target for the break, then we are looking at an incomplete 11956d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // AST. This means that the CFG cannot be constructed. 1196235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek if (BreakTargetBlock) 1197235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek Block->addSuccessor(BreakTargetBlock); 11986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump else 1199235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek badCFG = true; 1200235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek 1201d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 12026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return Block; 1203d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 1204d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1205411cdee0b490f79428c9eb977f25199eb7d21cd8Ted KremenekCFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { 12066d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // "switch" is a control-flow statement. Thus we stop processing the current 12076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block. 1208d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* SwitchSuccessor = NULL; 12096d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1210d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Block) { 12114e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 12124e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 1213d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SwitchSuccessor = Block; 12146d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else SwitchSuccessor = Succ; 1215d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1216d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Save the current "switch" context. 1217d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), 1218eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek save_break(BreakTargetBlock), 1219eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek save_default(DefaultCaseBlock); 1220eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek 12216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Set the "default" case to be the block after the switch statement. If the 12226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // switch statement contains a "default:", this value will be overwritten with 12236d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the block for that code. 1224eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek DefaultCaseBlock = SwitchSuccessor; 12256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1226d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Create a new block that will contain the switch statement. 1227d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SwitchTerminatedBlock = createBlock(false); 12286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1229d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Now process the switch body. The code after the switch is the implicit 1230d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // successor. 1231d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Succ = SwitchSuccessor; 1232d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek BreakTargetBlock = SwitchSuccessor; 12336d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // When visiting the body, the case statements should automatically get linked 12356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // up to the switch. We also don't keep a pointer to the body, since all 12366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // control-flow from the switch goes to case/default statements. 1237411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek assert (Terminator->getBody() && "switch must contain a non-NULL body"); 123849af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Block = NULL; 1239411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek CFGBlock *BodyBlock = Visit(Terminator->getBody()); 12404e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 12414e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(BodyBlock)) 12424e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 12434e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 124449af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek 12456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // If we have no "default:" case, the default transition is to the code 12466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // following the switch body. 1247eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek SwitchTerminatedBlock->addSuccessor(DefaultCaseBlock); 12486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 124949af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek // Add the terminator and condition in the switch block. 1250411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek SwitchTerminatedBlock->setTerminator(Terminator); 1251411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek assert (Terminator->getCond() && "switch condition must be non-NULL"); 1252d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = SwitchTerminatedBlock; 12536d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1254411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek return addStmt(Terminator->getCond()); 1255d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 1256d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1257411cdee0b490f79428c9eb977f25199eb7d21cd8Ted KremenekCFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* Terminator) { 12586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // CaseStmts are essentially labels, so they are the first statement in a 12596d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block. 126029ccaa186ac27bcb414c5acb069f6438b27dd5e7Ted Kremenek 1261411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (Terminator->getSubStmt()) Visit(Terminator->getSubStmt()); 126229ccaa186ac27bcb414c5acb069f6438b27dd5e7Ted Kremenek CFGBlock* CaseBlock = Block; 12636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (!CaseBlock) CaseBlock = createBlock(); 12646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12656d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Cases statements partition blocks, so this is the top of the basic block we 12666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // were processing (the "case XXX:" is the label). 1267411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek CaseBlock->setLabel(Terminator); 12684e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(CaseBlock)) 12694e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 12706d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Add this block to the list of successors for the block with the switch 12726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // statement. 1273eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek assert (SwitchTerminatedBlock); 1274eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek SwitchTerminatedBlock->addSuccessor(CaseBlock); 12756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1276d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // We set Block to NULL to allow lazy creation of a new block (if necessary) 1277d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = NULL; 12786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1279d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // This block is now the implicit successor of other blocks. 1280d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Succ = CaseBlock; 12816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12822677ea871a25aa79f9db360f6ed10584c02267adTed Kremenek return CaseBlock; 1283d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 12846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1285411cdee0b490f79428c9eb977f25199eb7d21cd8Ted KremenekCFGBlock* CFGBuilder::VisitDefaultStmt(DefaultStmt* Terminator) { 1286411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (Terminator->getSubStmt()) Visit(Terminator->getSubStmt()); 1287eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek DefaultCaseBlock = Block; 12886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (!DefaultCaseBlock) DefaultCaseBlock = createBlock(); 12896d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12906d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Default statements partition blocks, so this is the top of the basic block 12916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // we were processing (the "default:" is the label). 1292411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek DefaultCaseBlock->setLabel(Terminator); 12934e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(DefaultCaseBlock)) 12944e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 1295eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek 12966d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Unlike case statements, we don't add the default block to the successors 12976d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // for the switch statement immediately. This is done when we finish 12986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // processing the switch statement. This allows for the default case 12996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // (including a fall-through to the code after the switch statement) to always 13006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // be the last successor of a switch-terminated block. 13016d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1302eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek // We set Block to NULL to allow lazy creation of a new block (if necessary) 1303eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek Block = NULL; 13046d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1305eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek // This block is now the implicit successor of other blocks. 1306eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek Succ = DefaultCaseBlock; 13076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return DefaultCaseBlock; 1309295222c1f0926d84de77f076e79903523eeb5dbfTed Kremenek} 1310d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 131119bb356317952445b03ee341c02f6147083c9eeaTed KremenekCFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { 13126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Lazily create the indirect-goto dispatch block if there isn't one already. 131319bb356317952445b03ee341c02f6147083c9eeaTed Kremenek CFGBlock* IBlock = cfg->getIndirectGotoBlock(); 13146d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 131519bb356317952445b03ee341c02f6147083c9eeaTed Kremenek if (!IBlock) { 131619bb356317952445b03ee341c02f6147083c9eeaTed Kremenek IBlock = createBlock(false); 131719bb356317952445b03ee341c02f6147083c9eeaTed Kremenek cfg->setIndirectGotoBlock(IBlock); 131819bb356317952445b03ee341c02f6147083c9eeaTed Kremenek } 13196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 132019bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // IndirectGoto is a control-flow statement. Thus we stop processing the 132119bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // current block and create a new one. 13224e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 13234e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 13244e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 13254e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 132619bb356317952445b03ee341c02f6147083c9eeaTed Kremenek Block = createBlock(false); 132719bb356317952445b03ee341c02f6147083c9eeaTed Kremenek Block->setTerminator(I); 132819bb356317952445b03ee341c02f6147083c9eeaTed Kremenek Block->addSuccessor(IBlock); 132919bb356317952445b03ee341c02f6147083c9eeaTed Kremenek return addStmt(I->getTarget()); 133019bb356317952445b03ee341c02f6147083c9eeaTed Kremenek} 133119bb356317952445b03ee341c02f6147083c9eeaTed Kremenek 1332b5c13b0f4e438391b31dacb87641be7a1b990b57Ted Kremenek 1333befef2f69759d7338e2b7c5ce6c8b6f47fe6e667Ted Kremenek} // end anonymous namespace 1334026473c2175424a039f51ca8949937268721b965Ted Kremenek 13356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has 13366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// no successors or predecessors. If this is the first block created in the 13376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// CFG, it is automatically set to be the Entry and Exit of the CFG. 13389438252ad2ecae5338df565ca33c6969e4fbfa41Ted KremenekCFGBlock* CFG::createBlock() { 1339026473c2175424a039f51ca8949937268721b965Ted Kremenek bool first_block = begin() == end(); 1340026473c2175424a039f51ca8949937268721b965Ted Kremenek 1341026473c2175424a039f51ca8949937268721b965Ted Kremenek // Create the block. 13429438252ad2ecae5338df565ca33c6969e4fbfa41Ted Kremenek Blocks.push_front(CFGBlock(NumBlockIDs++)); 1343026473c2175424a039f51ca8949937268721b965Ted Kremenek 1344026473c2175424a039f51ca8949937268721b965Ted Kremenek // If this is the first block, set it as the Entry and Exit. 1345026473c2175424a039f51ca8949937268721b965Ted Kremenek if (first_block) Entry = Exit = &front(); 1346026473c2175424a039f51ca8949937268721b965Ted Kremenek 1347026473c2175424a039f51ca8949937268721b965Ted Kremenek // Return the block. 1348026473c2175424a039f51ca8949937268721b965Ted Kremenek return &front(); 1349026473c2175424a039f51ca8949937268721b965Ted Kremenek} 1350026473c2175424a039f51ca8949937268721b965Ted Kremenek 1351026473c2175424a039f51ca8949937268721b965Ted Kremenek/// buildCFG - Constructs a CFG from an AST. Ownership of the returned 1352026473c2175424a039f51ca8949937268721b965Ted Kremenek/// CFG is returned to the caller. 1353026473c2175424a039f51ca8949937268721b965Ted KremenekCFG* CFG::buildCFG(Stmt* Statement) { 1354fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek CFGBuilder Builder; 1355026473c2175424a039f51ca8949937268721b965Ted Kremenek return Builder.buildCFG(Statement); 1356fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek} 1357fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 1358026473c2175424a039f51ca8949937268721b965Ted Kremenek/// reverseStmts - Reverses the orders of statements within a CFGBlock. 1359fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenekvoid CFGBlock::reverseStmts() { std::reverse(Stmts.begin(),Stmts.end()); } 1360fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 136163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek//===----------------------------------------------------------------------===// 136263f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek// CFG: Queries for BlkExprs. 136363f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek//===----------------------------------------------------------------------===// 136463f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 136563f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremeneknamespace { 136686946745225096243f6969dc745267b78fc211a6Ted Kremenek typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy; 136763f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek} 136863f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 1369411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenekstatic void FindSubExprAssignments(Stmt* Terminator, llvm::SmallPtrSet<Expr*,50>& Set) { 1370411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (!Terminator) 137133d4aab80f31bd06257526fe2883ea920529456bTed Kremenek return; 13726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1373411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek for (Stmt::child_iterator I=Terminator->child_begin(), E=Terminator->child_end(); I!=E; ++I) { 137433d4aab80f31bd06257526fe2883ea920529456bTed Kremenek if (!*I) continue; 13756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 137633d4aab80f31bd06257526fe2883ea920529456bTed Kremenek if (BinaryOperator* B = dyn_cast<BinaryOperator>(*I)) 137733d4aab80f31bd06257526fe2883ea920529456bTed Kremenek if (B->isAssignmentOp()) Set.insert(B); 13786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 137933d4aab80f31bd06257526fe2883ea920529456bTed Kremenek FindSubExprAssignments(*I, Set); 138033d4aab80f31bd06257526fe2883ea920529456bTed Kremenek } 138133d4aab80f31bd06257526fe2883ea920529456bTed Kremenek} 138233d4aab80f31bd06257526fe2883ea920529456bTed Kremenek 138363f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenekstatic BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { 138463f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek BlkExprMapTy* M = new BlkExprMapTy(); 13856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13866d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Look for assignments that are used as subexpressions. These are the only 13876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // assignments that we want to *possibly* register as a block-level 13886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // expression. Basically, if an assignment occurs both in a subexpression and 13896d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // at the block-level, it is a block-level expression. 139033d4aab80f31bd06257526fe2883ea920529456bTed Kremenek llvm::SmallPtrSet<Expr*,50> SubExprAssignments; 13916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 139263f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) 139363f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek for (CFGBlock::iterator BI=I->begin(), EI=I->end(); BI != EI; ++BI) 139433d4aab80f31bd06257526fe2883ea920529456bTed Kremenek FindSubExprAssignments(*BI, SubExprAssignments); 139586946745225096243f6969dc745267b78fc211a6Ted Kremenek 1396411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { 13976d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Iterate over the statements again on identify the Expr* and Stmt* at the 13996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block-level that are block-level expressions. 1400411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek 140133d4aab80f31bd06257526fe2883ea920529456bTed Kremenek for (CFGBlock::iterator BI=I->begin(), EI=I->end(); BI != EI; ++BI) 1402411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (Expr* Exp = dyn_cast<Expr>(*BI)) { 14036d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1404411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { 140533d4aab80f31bd06257526fe2883ea920529456bTed Kremenek // Assignment expressions that are not nested within another 14066d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // expression are really "statements" whose value is never used by 14076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // another expression. 1408411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (B->isAssignmentOp() && !SubExprAssignments.count(Exp)) 140933d4aab80f31bd06257526fe2883ea920529456bTed Kremenek continue; 14106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else if (const StmtExpr* Terminator = dyn_cast<StmtExpr>(Exp)) { 14116d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Special handling for statement expressions. The last statement in 14126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the statement expression is also a block-level expr. 1413411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek const CompoundStmt* C = Terminator->getSubStmt(); 141486946745225096243f6969dc745267b78fc211a6Ted Kremenek if (!C->body_empty()) { 141533d4aab80f31bd06257526fe2883ea920529456bTed Kremenek unsigned x = M->size(); 141686946745225096243f6969dc745267b78fc211a6Ted Kremenek (*M)[C->body_back()] = x; 141786946745225096243f6969dc745267b78fc211a6Ted Kremenek } 141886946745225096243f6969dc745267b78fc211a6Ted Kremenek } 1419e2dcd783a04f654c50bd8b13fb08a440afbd67e7Ted Kremenek 142033d4aab80f31bd06257526fe2883ea920529456bTed Kremenek unsigned x = M->size(); 1421411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek (*M)[Exp] = x; 142233d4aab80f31bd06257526fe2883ea920529456bTed Kremenek } 14236d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1424411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek // Look at terminators. The condition is a block-level expression. 14256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1426390e48b15ad93f85bfd1e33b9992c198fa0db475Ted Kremenek Stmt* S = I->getTerminatorCondition(); 14276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1428390e48b15ad93f85bfd1e33b9992c198fa0db475Ted Kremenek if (S && M->find(S) == M->end()) { 1429411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek unsigned x = M->size(); 1430390e48b15ad93f85bfd1e33b9992c198fa0db475Ted Kremenek (*M)[S] = x; 1431411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek } 1432411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek } 14336d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 143486946745225096243f6969dc745267b78fc211a6Ted Kremenek return M; 143563f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek} 143663f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 143786946745225096243f6969dc745267b78fc211a6Ted KremenekCFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) { 143886946745225096243f6969dc745267b78fc211a6Ted Kremenek assert(S != NULL); 143963f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } 14406d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 144163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap); 144286946745225096243f6969dc745267b78fc211a6Ted Kremenek BlkExprMapTy::iterator I = M->find(S); 14436d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 144463f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek if (I == M->end()) return CFG::BlkExprNumTy(); 144563f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek else return CFG::BlkExprNumTy(I->second); 144663f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek} 14477dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 144863f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenekunsigned CFG::getNumBlkExprs() { 144963f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) 145063f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek return M->size(); 145163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek else { 145263f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek // We assume callers interested in the number of BlkExprs will want 145363f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek // the map constructed if it doesn't already exist. 145463f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek BlkExprMap = (void*) PopulateBlkExprMap(*this); 145563f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); 145663f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek } 145763f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek} 145863f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 1459274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek//===----------------------------------------------------------------------===// 1460274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek// Cleanup: CFG dstor. 1461274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek//===----------------------------------------------------------------------===// 1462274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek 146363f5887f316fb52d243fcbb3631c039de6c4b993Ted KremenekCFG::~CFG() { 146463f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); 146563f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek} 14666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 14677dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 14687dba8607e59096014b7139ff20ef00870041d518Ted Kremenek// CFG pretty printing 14697dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 14707dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 147142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremeneknamespace { 14722bac4ea765a4a6e1f6149964663f62d4bca6743bTed Kremenek 14736fa9b88e2c3d47d606a273df2f8d03509bcff0b9Ted Kremenekclass VISIBILITY_HIDDEN StmtPrinterHelper : public PrinterHelper { 14746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 147542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; 147642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek StmtMapTy StmtMap; 147742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek signed CurrentBlock; 147842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek unsigned CurrentStmt; 1479e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner const LangOptions &LangOpts; 148042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenekpublic: 14811c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek 1482e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) 1483e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner : CurrentBlock(0), CurrentStmt(0), LangOpts(LO) { 148442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { 148542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek unsigned j = 1; 148642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (CFGBlock::const_iterator BI = I->begin(), BEnd = I->end() ; 148742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek BI != BEnd; ++BI, ++j ) 148842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek StmtMap[*BI] = std::make_pair(I->getBlockID(),j); 148942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek } 1490fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 14916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 149242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek virtual ~StmtPrinterHelper() {} 14936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1494e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner const LangOptions &getLangOpts() const { return LangOpts; } 149542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek void setBlockID(signed i) { CurrentBlock = i; } 149642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek void setStmtID(unsigned i) { CurrentStmt = i; } 14976d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1498a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek virtual bool handledStmt(Stmt* Terminator, llvm::raw_ostream& OS) { 14996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1500411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek StmtMapTy::iterator I = StmtMap.find(Terminator); 1501fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 150242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (I == StmtMap.end()) 150342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek return false; 15046d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 15056d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (CurrentBlock >= 0 && I->second.first == (unsigned) CurrentBlock 150642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek && I->second.second == CurrentStmt) 150742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek return false; 15086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 15091c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek OS << "[B" << I->second.first << "." << I->second.second << "]"; 15101c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek return true; 151142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek } 151242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek}; 1513e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner} // end anonymous namespace 1514e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner 1515e8ee26b49d68ae3ffdf9a990ff7511ef55afa04cTed Kremenek 1516e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnernamespace { 15176fa9b88e2c3d47d606a273df2f8d03509bcff0b9Ted Kremenekclass VISIBILITY_HIDDEN CFGBlockTerminatorPrint 15186fa9b88e2c3d47d606a273df2f8d03509bcff0b9Ted Kremenek : public StmtVisitor<CFGBlockTerminatorPrint,void> { 15196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1520a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek llvm::raw_ostream& OS; 152142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek StmtPrinterHelper* Helper; 1522d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor PrintingPolicy Policy; 1523d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor 1524d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenekpublic: 1525d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor CFGBlockTerminatorPrint(llvm::raw_ostream& os, StmtPrinterHelper* helper, 1526e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner const PrintingPolicy &Policy) 1527d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor : OS(os), Helper(helper), Policy(Policy) {} 15286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1529d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek void VisitIfStmt(IfStmt* I) { 1530d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek OS << "if "; 1531d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor I->getCond()->printPretty(OS,Helper,Policy); 1532d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek } 15336d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1534d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Default case. 15356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump void VisitStmt(Stmt* Terminator) { 15366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Terminator->printPretty(OS, Helper, Policy); 15376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 15386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1539d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek void VisitForStmt(ForStmt* F) { 1540d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek OS << "for (" ; 1541535bb20b6e252809bc17cc59b5d71b5e5e549e70Ted Kremenek if (F->getInit()) OS << "..."; 1542535bb20b6e252809bc17cc59b5d71b5e5e549e70Ted Kremenek OS << "; "; 1543d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor if (Stmt* C = F->getCond()) C->printPretty(OS, Helper, Policy); 1544535bb20b6e252809bc17cc59b5d71b5e5e549e70Ted Kremenek OS << "; "; 1545535bb20b6e252809bc17cc59b5d71b5e5e549e70Ted Kremenek if (F->getInc()) OS << "..."; 1546a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek OS << ")"; 1547d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek } 15486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1549d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek void VisitWhileStmt(WhileStmt* W) { 1550d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek OS << "while " ; 1551d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor if (Stmt* C = W->getCond()) C->printPretty(OS, Helper, Policy); 1552d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek } 15536d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1554d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek void VisitDoStmt(DoStmt* D) { 1555d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek OS << "do ... while "; 1556d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor if (Stmt* C = D->getCond()) C->printPretty(OS, Helper, Policy); 15579da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek } 15586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1559411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek void VisitSwitchStmt(SwitchStmt* Terminator) { 15609da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek OS << "switch "; 1561d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor Terminator->getCond()->printPretty(OS, Helper, Policy); 15629da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek } 15636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1564805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek void VisitConditionalOperator(ConditionalOperator* C) { 1565d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor C->getCond()->printPretty(OS, Helper, Policy); 15666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump OS << " ? ... : ..."; 1567805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek } 15686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1569aeddbf689eb3e3afca5117ca83c7b2e18260b0d8Ted Kremenek void VisitChooseExpr(ChooseExpr* C) { 1570aeddbf689eb3e3afca5117ca83c7b2e18260b0d8Ted Kremenek OS << "__builtin_choose_expr( "; 1571d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor C->getCond()->printPretty(OS, Helper, Policy); 1572a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek OS << " )"; 1573aeddbf689eb3e3afca5117ca83c7b2e18260b0d8Ted Kremenek } 15746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 15751c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek void VisitIndirectGotoStmt(IndirectGotoStmt* I) { 15761c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek OS << "goto *"; 1577d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor I->getTarget()->printPretty(OS, Helper, Policy); 15781c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek } 15796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1580805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek void VisitBinaryOperator(BinaryOperator* B) { 1581805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek if (!B->isLogicalOp()) { 1582805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek VisitExpr(B); 1583805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek return; 1584805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek } 15856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1586d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor B->getLHS()->printPretty(OS, Helper, Policy); 15876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1588805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek switch (B->getOpcode()) { 1589805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek case BinaryOperator::LOr: 1590a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek OS << " || ..."; 1591805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek return; 1592805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek case BinaryOperator::LAnd: 1593a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek OS << " && ..."; 1594805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek return; 1595805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek default: 1596805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek assert(false && "Invalid logical operator."); 15976d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 1598805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek } 15996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 16000b1d9b7557437176f9cea1283bfac2510812beceTed Kremenek void VisitExpr(Expr* E) { 1601d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor E->printPretty(OS, Helper, Policy); 16026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 1603d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek}; 1604e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner} // end anonymous namespace 1605e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner 16066d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1607e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnerstatic void print_stmt(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, 1608e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner Stmt* Terminator) { 16091c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek if (Helper) { 16101c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek // special printing for statement-expressions. 1611411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (StmtExpr* SE = dyn_cast<StmtExpr>(Terminator)) { 16121c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek CompoundStmt* Sub = SE->getSubStmt(); 16136d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 16141c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek if (Sub->child_begin() != Sub->child_end()) { 161560266e8a9a4cd941af5e0006a18377dc03f0421bTed Kremenek OS << "({ ... ; "; 16167a9d9d71fa208dc23fd67d03ce052d4ef60a8d04Ted Kremenek Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); 161760266e8a9a4cd941af5e0006a18377dc03f0421bTed Kremenek OS << " })\n"; 16181c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek return; 16191c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek } 16201c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek } 16216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 16221c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek // special printing for comma expressions. 1623411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (BinaryOperator* B = dyn_cast<BinaryOperator>(Terminator)) { 16241c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek if (B->getOpcode() == BinaryOperator::Comma) { 16251c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek OS << "... , "; 16261c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek Helper->handledStmt(B->getRHS(),OS); 16271c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek OS << '\n'; 16281c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek return; 16296d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 16306d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 16311c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek } 16326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1633e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner Terminator->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 16346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 16351c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek // Expressions need a newline. 1636411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (isa<Expr>(Terminator)) OS << '\n'; 16371c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek} 16386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1639e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnerstatic void print_block(llvm::raw_ostream& OS, const CFG* cfg, 1640e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner const CFGBlock& B, 1641e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner StmtPrinterHelper* Helper, bool print_edges) { 16426d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 164342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (Helper) Helper->setBlockID(B.getBlockID()); 16446d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 16457dba8607e59096014b7139ff20ef00870041d518Ted Kremenek // Print the header. 16466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump OS << "\n [ B" << B.getBlockID(); 16476d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 164842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (&B == &cfg->getEntry()) 164942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " (ENTRY) ]\n"; 165042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek else if (&B == &cfg->getExit()) 165142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " (EXIT) ]\n"; 165242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek else if (&B == cfg->getIndirectGotoBlock()) 16537dba8607e59096014b7139ff20ef00870041d518Ted Kremenek OS << " (INDIRECT GOTO DISPATCH) ]\n"; 165442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek else 165542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " ]\n"; 16566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 16579cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek // Print the label of this block. 1658411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (Stmt* Terminator = const_cast<Stmt*>(B.getLabel())) { 165942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 166042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (print_edges) 166142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " "; 16626d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1663411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (LabelStmt* L = dyn_cast<LabelStmt>(Terminator)) 16649cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << L->getName(); 1665411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek else if (CaseStmt* C = dyn_cast<CaseStmt>(Terminator)) { 16669cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << "case "; 1667e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner C->getLHS()->printPretty(OS, Helper, 1668e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner PrintingPolicy(Helper->getLangOpts())); 16699cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek if (C->getRHS()) { 16709cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << " ... "; 1671e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner C->getRHS()->printPretty(OS, Helper, 1672e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner PrintingPolicy(Helper->getLangOpts())); 16739cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek } 16746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else if (isa<DefaultStmt>(Terminator)) 16759cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << "default"; 167642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek else 167742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek assert(false && "Invalid label statement in CFGBlock."); 16786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 16799cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << ":\n"; 16809cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek } 16816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1682fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek // Iterate through the statements in the block and print them. 1683fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek unsigned j = 1; 16846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 168542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; 168642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek I != E ; ++I, ++j ) { 16876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 16889cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek // Print the statement # in the basic block and the statement itself. 168942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (print_edges) 169042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " "; 16916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1692a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek OS << llvm::format("%3d", j) << ": "; 16936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 169442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (Helper) 169542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek Helper->setStmtID(j); 16966d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 16971c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek print_stmt(OS,Helper,*I); 1698fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 16996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 17009cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek // Print the terminator of this block. 170142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (B.getTerminator()) { 170242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (print_edges) 170342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " "; 17046d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 17059cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << " T: "; 17066d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 170742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (Helper) Helper->setBlockID(-1); 17086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1709e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner CFGBlockTerminatorPrint TPrinter(OS, Helper, 1710e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner PrintingPolicy(Helper->getLangOpts())); 171142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek TPrinter.Visit(const_cast<Stmt*>(B.getTerminator())); 1712a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek OS << '\n'; 1713fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 17146d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 17159cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek if (print_edges) { 17169cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek // Print the predecessors of this block. 171742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " Predecessors (" << B.pred_size() << "):"; 17189cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek unsigned i = 0; 171942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 172042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); 172142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek I != E; ++I, ++i) { 17226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 172342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (i == 8 || (i-8) == 0) 17249cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << "\n "; 17256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 17269cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << " B" << (*I)->getBlockID(); 17279cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek } 17286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 17299cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << '\n'; 17306d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 17319cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek // Print the successors of this block. 173242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " Successors (" << B.succ_size() << "):"; 17339cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek i = 0; 173442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 173542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); 173642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek I != E; ++I, ++i) { 17376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 173842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (i == 8 || (i-8) % 10 == 0) 17399cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << "\n "; 174042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 17419cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << " B" << (*I)->getBlockID(); 1742fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 17436d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 17449cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << '\n'; 1745fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 17466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump} 174742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 174842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 174942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek/// dump - A simple pretty printer of a CFG that outputs to stderr. 1750e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); } 175142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 175242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek/// print - A simple pretty printer of a CFG that outputs to an ostream. 1753e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFG::print(llvm::raw_ostream &OS, const LangOptions &LO) const { 1754e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner StmtPrinterHelper Helper(this, LO); 17556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 175642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek // Print the entry block. 175742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek print_block(OS, this, getEntry(), &Helper, true); 17586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 175942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek // Iterate through the CFGBlocks and print them one by one. 176042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { 176142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek // Skip the entry block, because we already printed it. 176242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (&(*I) == &getEntry() || &(*I) == &getExit()) 176342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek continue; 17646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 176542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek print_block(OS, this, *I, &Helper, true); 176642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek } 17676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 176842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek // Print the exit block. 176942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek print_block(OS, this, getExit(), &Helper, true); 1770d0172439194b28bae62a94a0a25d58e6d21e7a14Ted Kremenek OS.flush(); 17716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump} 177242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 177342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek/// dump - A simply pretty printer of a CFGBlock that outputs to stderr. 1774e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const { 1775e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner print(llvm::errs(), cfg, LO); 1776e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner} 177742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 177842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek/// print - A simple pretty printer of a CFGBlock that outputs to an ostream. 177942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek/// Generally this will only be called from CFG::print. 1780e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFGBlock::print(llvm::raw_ostream& OS, const CFG* cfg, 1781e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner const LangOptions &LO) const { 1782e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner StmtPrinterHelper Helper(cfg, LO); 178342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek print_block(OS, cfg, *this, &Helper, true); 1784026473c2175424a039f51ca8949937268721b965Ted Kremenek} 17857dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 1786a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek/// printTerminator - A simple pretty printer of the terminator of a CFGBlock. 1787e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFGBlock::printTerminator(llvm::raw_ostream &OS, 17886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump const LangOptions &LO) const { 1789e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); 1790a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek TPrinter.Visit(const_cast<Stmt*>(getTerminator())); 1791a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek} 1792a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek 1793390e48b15ad93f85bfd1e33b9992c198fa0db475Ted KremenekStmt* CFGBlock::getTerminatorCondition() { 17946d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1795411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (!Terminator) 1796411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek return NULL; 17976d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1798411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek Expr* E = NULL; 17996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1800411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek switch (Terminator->getStmtClass()) { 1801411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek default: 1802411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 18036d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1804411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::ForStmtClass: 1805411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<ForStmt>(Terminator)->getCond(); 1806411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 18076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1808411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::WhileStmtClass: 1809411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<WhileStmt>(Terminator)->getCond(); 1810411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 18116d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1812411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::DoStmtClass: 1813411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<DoStmt>(Terminator)->getCond(); 1814411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 18156d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1816411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::IfStmtClass: 1817411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<IfStmt>(Terminator)->getCond(); 1818411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 18196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1820411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::ChooseExprClass: 1821411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<ChooseExpr>(Terminator)->getCond(); 1822411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 18236d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1824411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::IndirectGotoStmtClass: 1825411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<IndirectGotoStmt>(Terminator)->getTarget(); 1826411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 18276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1828411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::SwitchStmtClass: 1829411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<SwitchStmt>(Terminator)->getCond(); 1830411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 18316d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1832411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::ConditionalOperatorClass: 1833411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<ConditionalOperator>(Terminator)->getCond(); 1834411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 18356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1836411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::BinaryOperatorClass: // '&&' and '||' 1837411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<BinaryOperator>(Terminator)->getLHS(); 1838390e48b15ad93f85bfd1e33b9992c198fa0db475Ted Kremenek break; 18396d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1840390e48b15ad93f85bfd1e33b9992c198fa0db475Ted Kremenek case Stmt::ObjCForCollectionStmtClass: 18416d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return Terminator; 1842411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek } 18436d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1844411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek return E ? E->IgnoreParens() : NULL; 1845411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek} 1846411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek 18479c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenekbool CFGBlock::hasBinaryBranchTerminator() const { 18486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 18499c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek if (!Terminator) 18509c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek return false; 18516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 18529c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek Expr* E = NULL; 18536d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 18549c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek switch (Terminator->getStmtClass()) { 18559c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek default: 18569c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek return false; 18576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 18586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump case Stmt::ForStmtClass: 18599c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::WhileStmtClass: 18609c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::DoStmtClass: 18619c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::IfStmtClass: 18629c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::ChooseExprClass: 18639c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::ConditionalOperatorClass: 18649c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::BinaryOperatorClass: 18656d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return true; 18669c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek } 18676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 18689c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek return E ? E->IgnoreParens() : NULL; 18699c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek} 18709c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek 1871a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek 18727dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 18737dba8607e59096014b7139ff20ef00870041d518Ted Kremenek// CFG Graphviz Visualization 18747dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 18757dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 187642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 187742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek#ifndef NDEBUG 18786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stumpstatic StmtPrinterHelper* GraphHelper; 187942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek#endif 188042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 1881e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFG::viewCFG(const LangOptions &LO) const { 188242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek#ifndef NDEBUG 1883e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner StmtPrinterHelper H(this, LO); 188442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek GraphHelper = &H; 188542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek llvm::ViewGraph(this,"CFG"); 188642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek GraphHelper = NULL; 188742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek#endif 188842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek} 188942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 18907dba8607e59096014b7139ff20ef00870041d518Ted Kremeneknamespace llvm { 18917dba8607e59096014b7139ff20ef00870041d518Ted Kremenektemplate<> 18927dba8607e59096014b7139ff20ef00870041d518Ted Kremenekstruct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { 189302995ce680d1bcf9f17bcfdf759bd74b08aa3948Owen Anderson static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph, 189402995ce680d1bcf9f17bcfdf759bd74b08aa3948Owen Anderson bool ShortNames) { 18957dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 1896bd250b44d60622e7c0b60c6def6f6fe7e347addfHartmut Kaiser#ifndef NDEBUG 1897a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek std::string OutSStr; 1898a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek llvm::raw_string_ostream Out(OutSStr); 189942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek print_block(Out,Graph, *Node, GraphHelper, false); 1900a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek std::string& OutStr = Out.str(); 19017dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 19027dba8607e59096014b7139ff20ef00870041d518Ted Kremenek if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 19037dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 19047dba8607e59096014b7139ff20ef00870041d518Ted Kremenek // Process string output to make it nicer... 19057dba8607e59096014b7139ff20ef00870041d518Ted Kremenek for (unsigned i = 0; i != OutStr.length(); ++i) 19067dba8607e59096014b7139ff20ef00870041d518Ted Kremenek if (OutStr[i] == '\n') { // Left justify 19077dba8607e59096014b7139ff20ef00870041d518Ted Kremenek OutStr[i] = '\\'; 19087dba8607e59096014b7139ff20ef00870041d518Ted Kremenek OutStr.insert(OutStr.begin()+i+1, 'l'); 19097dba8607e59096014b7139ff20ef00870041d518Ted Kremenek } 19106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 19117dba8607e59096014b7139ff20ef00870041d518Ted Kremenek return OutStr; 1912bd250b44d60622e7c0b60c6def6f6fe7e347addfHartmut Kaiser#else 1913bd250b44d60622e7c0b60c6def6f6fe7e347addfHartmut Kaiser return ""; 1914bd250b44d60622e7c0b60c6def6f6fe7e347addfHartmut Kaiser#endif 19157dba8607e59096014b7139ff20ef00870041d518Ted Kremenek } 19167dba8607e59096014b7139ff20ef00870041d518Ted Kremenek}; 19177dba8607e59096014b7139ff20ef00870041d518Ted Kremenek} // end namespace llvm 1918