CFG.cpp revision 0979d80615df97c675423de631c1b884819f4712
1fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek//===--- CFG.cpp - Classes for representing and building CFGs----*- C++ -*-===// 2fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// 3fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// The LLVM Compiler Infrastructure 4fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// 50bc735ffcfb223c0186419547abaa5c84482663eChris Lattner// This file is distributed under the University of Illinois Open Source 60bc735ffcfb223c0186419547abaa5c84482663eChris Lattner// License. See LICENSE.TXT for details. 7fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// 8fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek//===----------------------------------------------------------------------===// 9fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// 10fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// This file defines the CFG and CFGBuilder classes for representing and 11fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// building Control-Flow Graphs (CFGs) from ASTs. 12fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek// 13fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek//===----------------------------------------------------------------------===// 14fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 15bd0487825751230a4396952b770349d2beac60b3Ted Kremenek#include "clang/Analysis/Support/SaveAndRestore.h" 16e41611aa2237d06a0ef61db4528fb2883a8defcdTed Kremenek#include "clang/Analysis/CFG.h" 17c310e933a9b023a280f3aa02e5a0c75398555e13Ted Kremenek#include "clang/AST/StmtVisitor.h" 1842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek#include "clang/AST/PrettyPrinter.h" 190cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek#include "llvm/ADT/DenseMap.h" 2019bb356317952445b03ee341c02f6147083c9eeaTed Kremenek#include "llvm/ADT/SmallPtrSet.h" 217dba8607e59096014b7139ff20ef00870041d518Ted Kremenek#include "llvm/Support/GraphWriter.h" 227e3a89db59513acaf7ecfb51ef8998efbb51a5b8Ted Kremenek#include "llvm/Support/Streams.h" 236fa9b88e2c3d47d606a273df2f8d03509bcff0b9Ted Kremenek#include "llvm/Support/Compiler.h" 24274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek#include <llvm/Support/Allocator.h> 25a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek#include <llvm/Support/Format.h> 2683c01da96f57cf732a5da9a83e2981241f205dc4Ted Kremenek 27fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenekusing namespace clang; 28fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 29fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremeneknamespace { 30fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 314afa39deaa245592977136d367251ee2c173dd8dDouglas Gregorstatic SourceLocation GetEndLoc(Decl* D) { 32c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek if (VarDecl* VD = dyn_cast<VarDecl>(D)) 33c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek if (Expr* Ex = VD->getInit()) 34c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek return Ex->getSourceRange().getEnd(); 356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return D->getLocation(); 37c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek} 386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 39a34ea072371154c9042ce86321d17fbb4df1f84dTed Kremenek/// CFGBuilder - This class implements CFG construction from an AST. 40fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// The builder is stateful: an instance of the builder should be used to only 41fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// construct a single CFG. 42fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 43fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// Example usage: 44fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 45fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// CFGBuilder builder; 46fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// CFG* cfg = builder.BuildAST(stmt1); 47fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek/// 486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// CFG construction is done via a recursive walk of an AST. We actually parse 496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// the AST in reverse order so that the successor of a basic block is 506d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// constructed prior to its predecessor. This allows us to nicely capture 516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// implicit fall-throughs without extra basic blocks. 52c310e933a9b023a280f3aa02e5a0c75398555e13Ted Kremenek/// 534f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenekclass VISIBILITY_HIDDEN CFGBuilder { 54e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump ASTContext *Context; 55fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek CFG* cfg; 56fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek CFGBlock* Block; 57fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek CFGBlock* Succ; 58bf15b278a439d73b605ec00a8d3977ef305712f4Ted Kremenek CFGBlock* ContinueTargetBlock; 598a294713e032e4a27bae61c040abb41397952676Ted Kremenek CFGBlock* BreakTargetBlock; 60b5c13b0f4e438391b31dacb87641be7a1b990b57Ted Kremenek CFGBlock* SwitchTerminatedBlock; 61eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek CFGBlock* DefaultCaseBlock; 626d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 6319bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // LabelMap records the mapping from Label expressions to their blocks. 640cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek typedef llvm::DenseMap<LabelStmt*,CFGBlock*> LabelMapTy; 650cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek LabelMapTy LabelMap; 666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // A list of blocks that end with a "goto" that must be backpatched to their 686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // resolved targets upon completion of CFG construction. 694a2b8a10c4730eb2ceeec24505bef26eb7d829edTed Kremenek typedef std::vector<CFGBlock*> BackpatchBlocksTy; 700cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek BackpatchBlocksTy BackpatchBlocks; 716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 7219bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // A list of labels whose address has been taken (for indirect gotos). 7319bb356317952445b03ee341c02f6147083c9eeaTed Kremenek typedef llvm::SmallPtrSet<LabelStmt*,5> LabelSetTy; 7419bb356317952445b03ee341c02f6147083c9eeaTed Kremenek LabelSetTy AddressTakenLabels; 756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 766d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stumppublic: 77026473c2175424a039f51ca8949937268721b965Ted Kremenek explicit CFGBuilder() : cfg(NULL), Block(NULL), Succ(NULL), 788a294713e032e4a27bae61c040abb41397952676Ted Kremenek ContinueTargetBlock(NULL), BreakTargetBlock(NULL), 79eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL) { 80fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek // Create an empty CFG. 816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump cfg = new CFG(); 82fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 84fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek ~CFGBuilder() { delete cfg; } 856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 86d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // buildCFG - Used by external clients to construct the CFG. 87e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump CFG* buildCFG(Stmt *Statement, ASTContext *C); 886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 894f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenekprivate: 904f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Visitors to walk an AST and construct the CFG. 914f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, bool alwaysAdd); 924f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitBinaryOperator(BinaryOperator *B, bool alwaysAdd); 9313fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek CFGBlock *VisitBlockExpr(BlockExpr* E, bool alwaysAdd); 9413fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek CFGBlock *VisitBlockDeclRefExpr(BlockDeclRefExpr* E, bool alwaysAdd); 954f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitBreakStmt(BreakStmt *B); 964f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitCallExpr(CallExpr *C, bool alwaysAdd); 974f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitCaseStmt(CaseStmt *C); 983fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek CFGBlock *VisitChooseExpr(ChooseExpr *C); 993fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek CFGBlock *VisitCompoundStmt(CompoundStmt *C); 1003fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek CFGBlock *VisitConditionalOperator(ConditionalOperator *C); 1013fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek CFGBlock *VisitContinueStmt(ContinueStmt *C); 1020979d80615df97c675423de631c1b884819f4712Mike Stump CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T); 1034f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitDeclStmt(DeclStmt *DS); 1044f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitDeclSubExpr(Decl* D); 1053fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek CFGBlock *VisitDefaultStmt(DefaultStmt *D); 1063fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek CFGBlock *VisitDoStmt(DoStmt *D); 1073fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek CFGBlock *VisitForStmt(ForStmt *F); 1084f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitGotoStmt(GotoStmt* G); 1094f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitIfStmt(IfStmt *I); 1104f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I); 1114f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitLabelStmt(LabelStmt *L); 1124f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S); 1134f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S); 1144f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S); 1154f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S); 1164f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S); 1174f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitReturnStmt(ReturnStmt* R); 11813fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek CFGBlock *VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, bool alwaysAdd); 11913fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek CFGBlock *VisitStmtExpr(StmtExpr *S, bool alwaysAdd); 1204f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitSwitchStmt(SwitchStmt *S); 1214f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitWhileStmt(WhileStmt *W); 1224f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 1234f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *Visit(Stmt *S, bool alwaysAdd = false); 1244f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitStmt(Stmt *S, bool alwaysAdd); 1254f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *VisitChildren(Stmt* S); 126cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump 127274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek // NYS == Not Yet Supported 128274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek CFGBlock* NYS() { 1294102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek badCFG = true; 1304102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek return Block; 1314102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek } 1326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1334f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek void autoCreateBlock() { if (!Block) Block = createBlock(); } 1344f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *createBlock(bool add_successor = true); 1354e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek bool FinishBlock(CFGBlock* B); 1364f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *addStmt(Stmt *S) { return Visit(S, true); } 1374f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 1384102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek bool badCFG; 139d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek}; 1406d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 141898574e7496ba8fd76290079d3a9d06954992734Douglas Gregor// FIXME: Add support for dependent-sized array types in C++? 142898574e7496ba8fd76290079d3a9d06954992734Douglas Gregor// Does it even make sense to build a CFG for an uninstantiated template? 143610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenekstatic VariableArrayType* FindVA(Type* t) { 144610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek while (ArrayType* vt = dyn_cast<ArrayType>(t)) { 145610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek if (VariableArrayType* vat = dyn_cast<VariableArrayType>(vt)) 146610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek if (vat->getSizeExpr()) 147610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek return vat; 1486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 149610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek t = vt->getElementType().getTypePtr(); 150610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek } 1516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 152610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek return 0; 153610a09e409bea151a42dd907768f1e0c4b103f1fTed Kremenek} 1546d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an 1566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// arbitrary statement. Examples include a single expression or a function 1576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// body (compound statement). The ownership of the returned CFG is 1586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// transferred to the caller. If CFG construction fails, this method returns 1596d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// NULL. 160e5af3ce53ec58995b09381ba645ab2117a46647bMike StumpCFG* CFGBuilder::buildCFG(Stmt* Statement, ASTContext* C) { 161e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump Context = C; 1624f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek assert(cfg); 1634f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (!Statement) 1644f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return NULL; 165d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1664102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek badCFG = false; 1676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Create an empty block that will serve as the exit block for the CFG. Since 1696d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // this is the first block added to the CFG, it will be implicitly registered 1706d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // as the exit block. 17149af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Succ = createBlock(); 17249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek assert (Succ == &cfg->getExit()); 17349af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Block = NULL; // the EXIT block is empty. Create all other blocks lazily. 1746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 175d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Visit the statements and create the CFG. 1764f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* B = addStmt(Statement); 1770d99ecf1d8b9c72f2c4130f5f1be6cf13556b031Ted Kremenek if (!B) B = Succ; 1786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1790d99ecf1d8b9c72f2c4130f5f1be6cf13556b031Ted Kremenek if (B) { 1806d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Finalize the last constructed block. This usually involves reversing the 1816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // order of the statements in the block. 18249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek if (Block) FinishBlock(B); 1836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Backpatch the gotos whose label -> block mappings we didn't know when we 1856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // encountered them. 1866d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(), 187d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek E = BackpatchBlocks.end(); I != E; ++I ) { 1886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 189d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* B = *I; 190d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek GotoStmt* G = cast<GotoStmt>(B->getTerminator()); 191d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); 192d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 193d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // If there is no target for the goto, then we are looking at an 194d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // incomplete AST. Handle this by not registering a successor. 195d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (LI == LabelMap.end()) continue; 1966d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1976d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump B->addSuccessor(LI->second); 19819bb356317952445b03ee341c02f6147083c9eeaTed Kremenek } 1996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 20019bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // Add successors to the Indirect Goto Dispatch block (if we have one). 20119bb356317952445b03ee341c02f6147083c9eeaTed Kremenek if (CFGBlock* B = cfg->getIndirectGotoBlock()) 20219bb356317952445b03ee341c02f6147083c9eeaTed Kremenek for (LabelSetTy::iterator I = AddressTakenLabels.begin(), 20319bb356317952445b03ee341c02f6147083c9eeaTed Kremenek E = AddressTakenLabels.end(); I != E; ++I ) { 20419bb356317952445b03ee341c02f6147083c9eeaTed Kremenek 20519bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // Lookup the target block. 20619bb356317952445b03ee341c02f6147083c9eeaTed Kremenek LabelMapTy::iterator LI = LabelMap.find(*I); 20719bb356317952445b03ee341c02f6147083c9eeaTed Kremenek 20819bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // If there is no target block that contains label, then we are looking 20919bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // at an incomplete AST. Handle this by not registering a successor. 21019bb356317952445b03ee341c02f6147083c9eeaTed Kremenek if (LI == LabelMap.end()) continue; 2116d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump B->addSuccessor(LI->second); 21319bb356317952445b03ee341c02f6147083c9eeaTed Kremenek } 2146d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21594b3316ee37743cb60bf552d5616b03d17e277daTed Kremenek Succ = B; 21694b3316ee37743cb60bf552d5616b03d17e277daTed Kremenek } 2176d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2186d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Create an empty entry block that has no predecessors. 219322f58d3830da13b419646c071e3ab801518a09cTed Kremenek cfg->setEntry(createBlock()); 2206d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2214102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek if (badCFG) { 2224102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek delete cfg; 2234102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek cfg = NULL; 2244102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek return NULL; 2254102af916d52310c3deedd84d6fd5e2fd3c09bfeTed Kremenek } 2266d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // NULL out cfg so that repeated calls to the builder will fail and that the 2286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // ownership of the constructed CFG is passed to the caller. 229322f58d3830da13b419646c071e3ab801518a09cTed Kremenek CFG* t = cfg; 230322f58d3830da13b419646c071e3ab801518a09cTed Kremenek cfg = NULL; 231322f58d3830da13b419646c071e3ab801518a09cTed Kremenek return t; 232d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 2336d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 234d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek/// createBlock - Used to lazily create blocks that are connected 235d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek/// to the current (global) succcessor. 2366d9828c82c9321f042ab416fd2ffaa3034347d45Mike StumpCFGBlock* CFGBuilder::createBlock(bool add_successor) { 2379438252ad2ecae5338df565ca33c6969e4fbfa41Ted Kremenek CFGBlock* B = cfg->createBlock(); 2384f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (add_successor && Succ) 2394f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek B->addSuccessor(Succ); 240d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek return B; 241d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 2426d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2436d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// FinishBlock - When the last statement has been added to the block, we must 2446d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// reverse the statements because they have been inserted in reverse order. 2454e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenekbool CFGBuilder::FinishBlock(CFGBlock* B) { 2464e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (badCFG) 2474e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return false; 2484e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek 2494f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek assert(B); 25049af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek B->reverseStmts(); 2514e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return true; 252d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 253d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 2544f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek/// Visit - Walk the subtree of a statement and add extra 2556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// blocks for ternary operators, &&, and ||. We also process "," and 2566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// DeclStmts (which may contain nested control-flow). 2574f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock* CFGBuilder::Visit(Stmt * S, bool alwaysAdd) { 2584f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenektryAgain: 2594f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek switch (S->getStmtClass()) { 2604f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek default: 2614f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitStmt(S, alwaysAdd); 2624f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 2634f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::AddrLabelExprClass: 2644f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), alwaysAdd); 2654f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 2664f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::BinaryOperatorClass: 2674f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitBinaryOperator(cast<BinaryOperator>(S), alwaysAdd); 2684f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 2694f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::BlockExprClass: 27013fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek return VisitBlockExpr(cast<BlockExpr>(S), alwaysAdd); 2714f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 2724f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::BlockDeclRefExprClass: 27313fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek return VisitBlockDeclRefExpr(cast<BlockDeclRefExpr>(S), alwaysAdd); 2744f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 2754f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::BreakStmtClass: 2764f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitBreakStmt(cast<BreakStmt>(S)); 2774f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 2784f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::CallExprClass: 2794f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitCallExpr(cast<CallExpr>(S), alwaysAdd); 2804f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 2814f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::CaseStmtClass: 2824f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitCaseStmt(cast<CaseStmt>(S)); 2834f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 2844f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ChooseExprClass: 2854f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitChooseExpr(cast<ChooseExpr>(S)); 2864f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 2874f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::CompoundStmtClass: 2884f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitCompoundStmt(cast<CompoundStmt>(S)); 2894f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 2904f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ConditionalOperatorClass: 2914f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitConditionalOperator(cast<ConditionalOperator>(S)); 2924f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 2934f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ContinueStmtClass: 2944f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitContinueStmt(cast<ContinueStmt>(S)); 2954f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 2964f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::DeclStmtClass: 2974f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitDeclStmt(cast<DeclStmt>(S)); 2984f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 2994f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::DefaultStmtClass: 3004f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitDefaultStmt(cast<DefaultStmt>(S)); 3014f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3024f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::DoStmtClass: 3034f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitDoStmt(cast<DoStmt>(S)); 3044f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3054f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ForStmtClass: 3064f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitForStmt(cast<ForStmt>(S)); 3074f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3084f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::GotoStmtClass: 3094f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitGotoStmt(cast<GotoStmt>(S)); 3104f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3114f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::IfStmtClass: 3124f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitIfStmt(cast<IfStmt>(S)); 3134f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3144f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::IndirectGotoStmtClass: 3154f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S)); 3164f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3174f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::LabelStmtClass: 3184f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitLabelStmt(cast<LabelStmt>(S)); 3194f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3204f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ObjCAtCatchStmtClass: 3214f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S)); 3224f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3230979d80615df97c675423de631c1b884819f4712Mike Stump case Stmt::CXXThrowExprClass: 3240979d80615df97c675423de631c1b884819f4712Mike Stump return VisitCXXThrowExpr(cast<CXXThrowExpr>(S)); 3250979d80615df97c675423de631c1b884819f4712Mike Stump 3264f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ObjCAtSynchronizedStmtClass: 3274f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S)); 3284f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3294f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ObjCAtThrowStmtClass: 3304f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S)); 3314f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3324f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ObjCAtTryStmtClass: 3334f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S)); 3344f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3354f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ObjCForCollectionStmtClass: 3364f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S)); 3374f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3384f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ParenExprClass: 3394f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek S = cast<ParenExpr>(S)->getSubExpr(); 3404f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek goto tryAgain; 3414f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3424f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::NullStmtClass: 3434f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return Block; 3444f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3454f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::ReturnStmtClass: 3464f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitReturnStmt(cast<ReturnStmt>(S)); 3474f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3484f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::SizeOfAlignOfExprClass: 34913fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek return VisitSizeOfAlignOfExpr(cast<SizeOfAlignOfExpr>(S), alwaysAdd); 3504f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3514f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::StmtExprClass: 35213fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek return VisitStmtExpr(cast<StmtExpr>(S), alwaysAdd); 3534f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3544f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::SwitchStmtClass: 3554f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitSwitchStmt(cast<SwitchStmt>(S)); 3564f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3574f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::WhileStmtClass: 3584f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitWhileStmt(cast<WhileStmt>(S)); 3594f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } 3604f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 361f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek 3624f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitStmt(Stmt *S, bool alwaysAdd) { 3634f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (alwaysAdd) { 3644f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek autoCreateBlock(); 3654f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block->appendStmt(S); 3666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 3674f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3684f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitChildren(S); 3694f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 3706d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3714f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek/// VisitChildren - Visit the children of a Stmt. 3724f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitChildren(Stmt* Terminator) { 3734f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *B = Block; 3744f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek for (Stmt::child_iterator I = Terminator->child_begin(), 3754f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek E = Terminator->child_end(); I != E; ++I) { 3764f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (*I) B = Visit(*I); 3776d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 3784f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return B; 3794f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 3804f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3814f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, bool alwaysAdd) { 3824f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek AddressTakenLabels.insert(A->getLabel()); 3836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3844f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (alwaysAdd) { 3854f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek autoCreateBlock(); 3864f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block->appendStmt(A); 3876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 3886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 3894f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return Block; 3904f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 3914f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 3924f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, bool alwaysAdd) { 3934f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (B->isLogicalOp()) { // && or || 394c7eb9031159f30a63db960fad4640d779f1617c8Ted Kremenek 395e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // See if this is a known constant. 396e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump bool KnownTrue = false; 397e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump bool KnownFalse = false; 398e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump Expr::EvalResult Result; 399e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (B->getLHS()->Evaluate(Result, *Context) 400e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump && Result.Val.isInt()) { 401e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if ((B->getOpcode() == BinaryOperator::LAnd) 402e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump == Result.Val.getInt().getBoolValue()) 403e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump KnownTrue = true; 404e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump else 405e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump KnownFalse = true; 406e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump } 407e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump 4084f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 4094f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek ConfluenceBlock->appendStmt(B); 4104f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 4114f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (!FinishBlock(ConfluenceBlock)) 4124f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return 0; 4134f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 4144f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // create the block evaluating the LHS 4154f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* LHSBlock = createBlock(false); 4164f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LHSBlock->setTerminator(B); 4174f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 4184f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // create the block evaluating the RHS 4194f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Succ = ConfluenceBlock; 4204f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block = NULL; 4214f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* RHSBlock = addStmt(B->getRHS()); 4224f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (!FinishBlock(RHSBlock)) 4234f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return 0; 4244f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 4254f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Now link the LHSBlock with RHSBlock. 4264f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (B->getOpcode() == BinaryOperator::LOr) { 427e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (KnownTrue) 428e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump LHSBlock->addSuccessor(0); 429e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump else 430e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump LHSBlock->addSuccessor(ConfluenceBlock); 431e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (KnownFalse) 432e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump LHSBlock->addSuccessor(0); 433e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump else 434e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump LHSBlock->addSuccessor(RHSBlock); 4354f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } else { 4364f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek assert (B->getOpcode() == BinaryOperator::LAnd); 437e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (KnownFalse) 438e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump LHSBlock->addSuccessor(0); 439e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump else 440e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump LHSBlock->addSuccessor(RHSBlock); 441e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (KnownTrue) 442e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump LHSBlock->addSuccessor(0); 443e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump else 444e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump LHSBlock->addSuccessor(ConfluenceBlock); 44519bb356317952445b03ee341c02f6147083c9eeaTed Kremenek } 4464f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 4474f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Generate the blocks for evaluating the LHS. 4484f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block = LHSBlock; 4494f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return addStmt(B->getLHS()); 4504f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } 4514f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek else if (B->getOpcode() == BinaryOperator::Comma) { // , 4526dc534ecc19a045ebcfe93eefa45da509968e888Ted Kremenek autoCreateBlock(); 4534f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block->appendStmt(B); 4544f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek addStmt(B->getRHS()); 4554f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return addStmt(B->getLHS()); 4566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 4574f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 4584f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitStmt(B, alwaysAdd); 4594f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 4606d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 46113fc08a323b29dd97a46def1e3a15bf082476efaTed KremenekCFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr* E, bool alwaysAdd) { 4624f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // FIXME 4634f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return NYS(); 4644f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 465cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump 46613fc08a323b29dd97a46def1e3a15bf082476efaTed KremenekCFGBlock *CFGBuilder::VisitBlockDeclRefExpr(BlockDeclRefExpr* E, 46713fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek bool alwaysAdd) { 4684f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // FIXME 4694f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return NYS(); 4704f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 4714f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 4724f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { 4734f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // "break" is a control-flow statement. Thus we stop processing the current 4744f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // block. 4754f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (Block && !FinishBlock(Block)) 4764f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return 0; 4774f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 4784f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Now create a new block that ends with the break statement. 4794f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block = createBlock(false); 4804f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block->setTerminator(B); 4814f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 4824f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // If there is no target for the break, then we are looking at an incomplete 4834f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // AST. This means that the CFG cannot be constructed. 4844f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (BreakTargetBlock) 4854f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block->addSuccessor(BreakTargetBlock); 4864f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek else 4874f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek badCFG = true; 4884f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 4894f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 4904f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return Block; 4914f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 4924f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 4934f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, bool alwaysAdd) { 4944f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // If this is a call to a no-return function, this stops the block here. 4954f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (FunctionDecl *FD = C->getDirectCallee()) { 4964f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 4974f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (!FD->hasAttr<NoReturnAttr>()) 4984f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitStmt(C, alwaysAdd); 4994f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 50001bc160ffccc03e4c0583acf82bd7ab80494219aChris Lattner if (Block && !FinishBlock(Block)) 50101bc160ffccc03e4c0583acf82bd7ab80494219aChris Lattner return 0; 5024f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 503cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump // Create new block with no successor for the remaining pieces. 504cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump Block = createBlock(false); 5054f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block->appendStmt(C); 5064f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 507cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump // Wire this to the exit block directly. 508cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump Block->addSuccessor(&cfg->getExit()); 5094f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 5104f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitChildren(C); 511cd7bf230a77c550115e4a78ee371fc49a7563692Mike Stump } 5124f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 5134f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitStmt(C, alwaysAdd); 514d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 515d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 5163fc8ef574cdc09c613c329ee511852d219263c15Ted KremenekCFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C) { 51722cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump // See if this is a known constant. 51822cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump bool KnownTrue = false; 51922cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump bool KnownFalse = false; 52022cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump Expr::EvalResult Result; 52122cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump if (C->getCond()->Evaluate(Result, *Context) 52222cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump && Result.Val.isInt()) { 52322cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump if (Result.Val.getInt().getBoolValue()) 52422cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump KnownTrue = true; 52522cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump else 52622cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump KnownFalse = true; 52722cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump } 52822cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump 5293fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 5303fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek ConfluenceBlock->appendStmt(C); 5313fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek if (!FinishBlock(ConfluenceBlock)) 5323fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek return 0; 5333fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek 5343fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek Succ = ConfluenceBlock; 5353fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek Block = NULL; 5364f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* LHSBlock = addStmt(C->getLHS()); 5373fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek if (!FinishBlock(LHSBlock)) 5383fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek return 0; 5393fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek 5403fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek Succ = ConfluenceBlock; 5413fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek Block = NULL; 5424f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* RHSBlock = addStmt(C->getRHS()); 5433fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek if (!FinishBlock(RHSBlock)) 5443fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek return 0; 5453fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek 5463fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek Block = createBlock(false); 54722cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump if (KnownFalse) 54822cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump Block->addSuccessor(0); 54922cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump else 55022cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump Block->addSuccessor(LHSBlock); 55122cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump if (KnownTrue) 55222cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump Block->addSuccessor(0); 55322cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump else 55422cd6581188bbbc6bedaca64ab171b1187a1c06aMike Stump Block->addSuccessor(RHSBlock); 5553fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek Block->setTerminator(C); 5563fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek return addStmt(C->getCond()); 5573fc8ef574cdc09c613c329ee511852d219263c15Ted Kremenek} 558f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek 5594f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 5604f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) { 5614f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* LastBlock = Block; 5624f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 5634f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); 5644f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek I != E; ++I ) { 5654f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LastBlock = addStmt(*I); 5664f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } 5674f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return LastBlock; 5684f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 5694f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 570f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted KremenekCFGBlock *CFGBuilder::VisitConditionalOperator(ConditionalOperator *C) { 571e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // See if this is a known constant. 572e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump bool KnownTrue = false; 573e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump bool KnownFalse = false; 574e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump Expr::EvalResult Result; 575e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (C->getCond()->Evaluate(Result, *Context) 576e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump && Result.Val.isInt()) { 577e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (Result.Val.getInt().getBoolValue()) 578e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump KnownTrue = true; 579e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump else 580e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump KnownFalse = true; 581e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump } 582e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump 583f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // Create the confluence block that will "merge" the results of the ternary 584f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // expression. 585f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 586f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek ConfluenceBlock->appendStmt(C); 587f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek if (!FinishBlock(ConfluenceBlock)) 588f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek return 0; 589f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek 590f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // Create a block for the LHS expression if there is an LHS expression. A 591f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // GCC extension allows LHS to be NULL, causing the condition to be the 592f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // value that is returned instead. 593f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // e.g: x ?: y is shorthand for: x ? x : y; 594f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek Succ = ConfluenceBlock; 595f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek Block = NULL; 596f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek CFGBlock* LHSBlock = NULL; 597f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek if (C->getLHS()) { 5984f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LHSBlock = addStmt(C->getLHS()); 599f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek if (!FinishBlock(LHSBlock)) 600f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek return 0; 601f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek Block = NULL; 602f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek } 603f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek 604f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // Create the block for the RHS expression. 605f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek Succ = ConfluenceBlock; 6064f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* RHSBlock = addStmt(C->getRHS()); 607f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek if (!FinishBlock(RHSBlock)) 608f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek return 0; 609f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek 610f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek // Create the block that will contain the condition. 611f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek Block = createBlock(false); 612f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek 613e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (LHSBlock) { 614e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (KnownFalse) 615e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump Block->addSuccessor(0); 616e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump else 617e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump Block->addSuccessor(LHSBlock); 618e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump } else { 619e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (KnownFalse) { 620e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // If we know the condition is false, add NULL as the successor for 621e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // the block containing the condition. In this case, the confluence 622e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // block will have just one predecessor. 623e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump Block->addSuccessor(0); 624e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump assert (ConfluenceBlock->pred_size() == 1); 625e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump } else { 626e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // If we have no LHS expression, add the ConfluenceBlock as a direct 627e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // successor for the block containing the condition. Moreover, we need to 628e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // reverse the order of the predecessors in the ConfluenceBlock because 629e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // the RHSBlock will have been added to the succcessors already, and we 630e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // want the first predecessor to the the block containing the expression 631e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump // for the case when the ternary expression evaluates to true. 632e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump Block->addSuccessor(ConfluenceBlock); 633e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump assert (ConfluenceBlock->pred_size() == 2); 634e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump std::reverse(ConfluenceBlock->pred_begin(), 635e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump ConfluenceBlock->pred_end()); 636e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump } 637f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek } 638f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek 639e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (KnownTrue) 640e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump Block->addSuccessor(0); 641e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump else 642e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump Block->addSuccessor(RHSBlock); 643f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek 644f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek Block->setTerminator(C); 645f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek return addStmt(C->getCond()); 646f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek} 647f34bb2eaa87aa28bcc8b6ff0dfc696cd75605b11Ted Kremenek 6484f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) { 6494f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek autoCreateBlock(); 6506d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 6514f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (DS->isSingleDecl()) { 6524f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block->appendStmt(DS); 6534f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitDeclSubExpr(DS->getSingleDecl()); 654d34066c224f782056c18f154abe04ef590473fd9Ted Kremenek } 6554f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 6564f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *B = 0; 6574f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 6584f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy. 6594f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek typedef llvm::SmallVector<Decl*,10> BufTy; 6604f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek BufTy Buf(DS->decl_begin(), DS->decl_end()); 6614f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 6624f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek for (BufTy::reverse_iterator I = Buf.rbegin(), E = Buf.rend(); I != E; ++I) { 6634f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Get the alignment of the new DeclStmt, padding out to >=8 bytes. 6644f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8 6654f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek ? 8 : llvm::AlignOf<DeclStmt>::Alignment; 6664f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 6674f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Allocate the DeclStmt using the BumpPtrAllocator. It will get 6684f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // automatically freed with the CFG. 6694f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek DeclGroupRef DG(*I); 6704f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Decl *D = *I; 6714f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A); 6724f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); 6734f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 6744f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Append the fake DeclStmt to block. 6754f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block->appendStmt(DSNew); 6764f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek B = VisitDeclSubExpr(D); 6774f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } 6784f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 6794f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return B; 6804f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 6814f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 6824f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek/// VisitDeclSubExpr - Utility method to add block-level expressions for 6834f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek/// initializers in Decls. 6844f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitDeclSubExpr(Decl* D) { 6854f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek assert(Block); 686d34066c224f782056c18f154abe04ef590473fd9Ted Kremenek 6874f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek VarDecl *VD = dyn_cast<VarDecl>(D); 6884f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 6894f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (!VD) 6904f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return Block; 6914f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 6924f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Expr *Init = VD->getInit(); 6934f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 6944f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (Init) { 6954f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // Optimization: Don't create separate block-level statements for literals. 6964f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek switch (Init->getStmtClass()) { 6974f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::IntegerLiteralClass: 6984f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::CharacterLiteralClass: 6994f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek case Stmt::StringLiteralClass: 7004f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek break; 7014f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek default: 7024f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block = addStmt(Init); 7034f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } 7044f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } 7054f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 7064f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // If the type of VD is a VLA, then we must process its size expressions. 7074f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek for (VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); VA != 0; 7084f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek VA = FindVA(VA->getElementType().getTypePtr())) 7094f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Block = addStmt(VA->getSizeExpr()); 7104f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 7114f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return Block; 712d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 713fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 714d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { 7155f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump // See if this is a known constant. 716e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump bool KnownTrue = false; 717e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump bool KnownFalse = false; 718e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump Expr::EvalResult Result; 719e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (I->getCond()->Evaluate(Result, *Context) 720e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump && Result.Val.isInt()) { 721e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (Result.Val.getInt().getBoolValue()) 722e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump KnownTrue = true; 723e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump else 724e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump KnownFalse = true; 725e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump } 726e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump 7276d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // We may see an if statement in the middle of a basic block, or it may be the 7286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // first statement we are processing. In either case, we create a new basic 7296d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block. First, we create the blocks for the then...else statements, and 7306d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // then we create the block containing the if statement. If we were in the 7316d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // middle of a block, we stop processing that block and reverse its 7326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // statements. That block is then the implicit successor for the "then" and 7336d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // "else" clauses. 7346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 7356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // The block we were proccessing is now finished. Make it the successor 7366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block. 7376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (Block) { 738d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Succ = Block; 7394e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 7404e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 741c310e933a9b023a280f3aa02e5a0c75398555e13Ted Kremenek } 7426d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 743b6f1d782e0dc5fad138a17e6aa0ff6f9bc4788c6Ted Kremenek // Process the false branch. 744d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* ElseBlock = Succ; 7456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 746d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Stmt* Else = I->getElse()) { 747d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> sv(Succ); 7486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 749d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // NULL out Block so that the recursive call to Visit will 7506d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // create a new basic block. 751d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = NULL; 7524f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek ElseBlock = addStmt(Else); 7536d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 754b6f7b72047b3fd3f96a5040e1e4d520a9dea01cdTed Kremenek if (!ElseBlock) // Can occur when the Else body has all NullStmts. 755b6f7b72047b3fd3f96a5040e1e4d520a9dea01cdTed Kremenek ElseBlock = sv.get(); 7564e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek else if (Block) { 7574e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(ElseBlock)) 7584e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 7594e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 760c310e933a9b023a280f3aa02e5a0c75398555e13Ted Kremenek } 7616d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 762b6f1d782e0dc5fad138a17e6aa0ff6f9bc4788c6Ted Kremenek // Process the true branch. 763d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* ThenBlock; 764d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek { 765d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Stmt* Then = I->getThen(); 766d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek assert (Then); 767d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> sv(Succ); 7686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Block = NULL; 7694f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek ThenBlock = addStmt(Then); 7706d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 771dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek if (!ThenBlock) { 772dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek // We can reach here if the "then" body has all NullStmts. 773dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek // Create an empty block so we can distinguish between true and false 774dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek // branches in path-sensitive analyses. 775dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek ThenBlock = createBlock(false); 776dbdf7949a7a50f5a65055a3e95f6432ecc541056Ted Kremenek ThenBlock->addSuccessor(sv.get()); 7776d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else if (Block) { 7784e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(ThenBlock)) 7794e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 7806d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 7810cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek } 782d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 7836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now create a new block containing the if statement. 784d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(false); 7856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 786d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Set the terminator of the new block to the If statement. 787d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->setTerminator(I); 7886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 789d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Now add the successors. 790e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (KnownFalse) 791e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump Block->addSuccessor(0); 792e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump else 793e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump Block->addSuccessor(ThenBlock); 794e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (KnownTrue) 795e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump Block->addSuccessor(0); 796e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump else 797e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump Block->addSuccessor(ElseBlock); 7986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 7996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Add the condition as the last statement in the new block. This may create 8006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // new blocks as the condition may contain control-flow. Any newly created 8016d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // blocks will be pointed to be "Block". 8024f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return addStmt(I->getCond()); 803d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 8046d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8056d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 806d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitReturnStmt(ReturnStmt* R) { 8076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // If we were in the middle of a block we stop processing that block and 8086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // reverse its statements. 809d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // 8106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // NOTE: If a "return" appears in the middle of a block, this means that the 8116d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // code afterwards is DEAD (unreachable). We still keep a basic block 8126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // for that code; a simple "mark-and-sweep" from the entry block will be 8136d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // able to report such dead blocks. 814d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Block) FinishBlock(Block); 815d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 816d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Create the new block. 817d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(false); 8186d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 819d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // The Exit block is the only successor. 820d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->addSuccessor(&cfg->getExit()); 8216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Add the return statement to the block. This may create new blocks if R 8236d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // contains control-flow (short-circuit operations). 8244f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitStmt(R, true); 825d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 8260cebe3e29b22d11f2c65ef28fcfb5f0431877266Ted Kremenek 827d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt* L) { 828d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Get the block of the labeled statement. Add it to our map. 8294f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek addStmt(L->getSubStmt()); 8302677ea871a25aa79f9db360f6ed10584c02267adTed Kremenek CFGBlock* LabelBlock = Block; 8316d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8324f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (!LabelBlock) // This can happen when the body is empty, i.e. 8334f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LabelBlock = createBlock(); // scopes that only contains NullStmts. 8346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8354f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek assert(LabelMap.find(L) == LabelMap.end() && "label already in map"); 836d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LabelMap[ L ] = LabelBlock; 8376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Labels partition blocks, so this is the end of the basic block we were 8396d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // processing (L is the block's label). Because this is label (and we have 8406d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // already processed the substatement) there is no extra control-flow to worry 8416d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // about. 8429cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek LabelBlock->setLabel(L); 8434e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(LabelBlock)) 8444e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 8456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // We set Block to NULL to allow lazy creation of a new block (if necessary); 847d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = NULL; 8486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 849d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // This block is now the implicit successor of other blocks. 850d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Succ = LabelBlock; 8516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 852d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek return LabelBlock; 853d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 85431dcd3c8c4df5a656f58f50ea73afc177c101c67Ted Kremenek 855d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) { 8566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Goto is a control-flow statement. Thus we stop processing the current 8576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block and create a new one. 8584f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (Block) 8594f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek FinishBlock(Block); 8604f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 861d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(false); 862d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->setTerminator(G); 8636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 8646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // If we already know the mapping to the label block add the successor now. 865d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LabelMapTy::iterator I = LabelMap.find(G->getLabel()); 8666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 867d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (I == LabelMap.end()) 868d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // We will need to backpatch this block later. 869d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek BackpatchBlocks.push_back(Block); 870d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek else 871d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->addSuccessor(I->second); 872d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 8736d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return Block; 874d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 875d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 876d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { 877fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump // See if this is a known constant. 878fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump bool KnownTrue = false; 879fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump bool KnownFalse = false; 880fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump Expr::EvalResult Result; 881fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump if (F->getCond() && F->getCond()->Evaluate(Result, *Context) 882fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump && Result.Val.isInt()) { 883fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump if (Result.Val.getInt().getBoolValue()) 884fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump KnownTrue = true; 885fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump else 886fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump KnownFalse = true; 887fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump } 888fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump if (F->getCond() == 0) 889fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump KnownTrue = true; 890fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump 891d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* LoopSuccessor = NULL; 8926d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 893fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump // "for" is a control-flow statement. Thus we stop processing the current 894fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump // block. 895d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Block) { 8964e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 8974e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 898d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LoopSuccessor = Block; 8994f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } else 9004f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LoopSuccessor = Succ; 9016d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Because of short-circuit evaluation, the condition of the loop can span 9036d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 9046d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // evaluate the condition. 90549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* ExitConditionBlock = createBlock(false); 90649af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* EntryConditionBlock = ExitConditionBlock; 9076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 90849af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek // Set the terminator for the "exit" condition block. 9096d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ExitConditionBlock->setTerminator(F); 9106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9116d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now add the actual condition to the condition block. Because the condition 9126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // itself may contain control-flow, new blocks may be created. 91349af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek if (Stmt* C = F->getCond()) { 91449af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Block = ExitConditionBlock; 91549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek EntryConditionBlock = addStmt(C); 9164e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 9174e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(EntryConditionBlock)) 9184e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 9194e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 92049af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek } 921d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 9226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // The condition block is the implicit successor for the loop body as well as 9236d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // any code above the loop. 92449af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Succ = EntryConditionBlock; 9256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 926d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Now create the loop body. 927d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek { 928d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek assert (F->getBody()); 9296d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 930d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Save the current values for Block, Succ, and continue and break targets 931d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 932d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek save_continue(ContinueTargetBlock), 9336d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump save_break(BreakTargetBlock); 9346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 935af603f742491dc4707138c0293d295171fdd51baTed Kremenek // Create a new block to contain the (bottom) of the loop body. 936af603f742491dc4707138c0293d295171fdd51baTed Kremenek Block = NULL; 9376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 938e933450535ab077b95e59f929a4ccb25b6f360e6Ted Kremenek if (Stmt* I = F->getInc()) { 9396d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Generate increment code in its own basic block. This is the target of 9406d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // continue statements. 9414f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek Succ = addStmt(I); 9426d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else { 9436d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // No increment code. Create a special, empty, block that is used as the 9446d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // target block for "looping back" to the start of the loop. 9453575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek assert(Succ == EntryConditionBlock); 9463575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek Succ = createBlock(); 947e933450535ab077b95e59f929a4ccb25b6f360e6Ted Kremenek } 9486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9493575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek // Finish up the increment (or empty) block if it hasn't been already. 9503575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek if (Block) { 9513575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek assert(Block == Succ); 9524e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 9534e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 9543575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek Block = 0; 9553575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek } 9566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9573575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek ContinueTargetBlock = Succ; 9586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9593575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek // The starting block for the loop increment is the block that should 9603575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek // represent the 'loop target' for looping back to the start of the loop. 9613575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek ContinueTargetBlock->setLoopTarget(F); 9623575f84e459033d6427b84b4b795b22c85c4d27dTed Kremenek 963e933450535ab077b95e59f929a4ccb25b6f360e6Ted Kremenek // All breaks should go to the code following the loop. 9646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump BreakTargetBlock = LoopSuccessor; 9656d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 9666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now populate the body block, and in the process create new blocks as we 9676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // walk the body of the loop. 9684f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* BodyBlock = addStmt(F->getBody()); 969af603f742491dc4707138c0293d295171fdd51baTed Kremenek 970af603f742491dc4707138c0293d295171fdd51baTed Kremenek if (!BodyBlock) 971a9d996dbeb719200c4a9d86f68166a237583025fTed Kremenek BodyBlock = EntryConditionBlock; // can happen for "for (...;...; ) ;" 9724e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek else if (Block) { 9734e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(BodyBlock)) 9744e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 9756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 9766d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 977fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump if (KnownFalse) 978fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump ExitConditionBlock->addSuccessor(0); 979fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump else { 980fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump // This new body block is a successor to our "exit" condition block. 981fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump ExitConditionBlock->addSuccessor(BodyBlock); 982fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump } 983d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek } 9846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 985fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump if (KnownTrue) 986fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump ExitConditionBlock->addSuccessor(0); 987fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump else { 988fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump // Link up the condition block with the code that follows the loop. (the 989fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump // false branch). 990fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump ExitConditionBlock->addSuccessor(LoopSuccessor); 991fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump } 9926d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 993d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // If the loop contains initialization, create a new block for those 9946d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // statements. This block can also contain statements that precede the loop. 995d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Stmt* I = F->getInit()) { 996d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(); 99749af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek return addStmt(I); 9986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else { 9996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // There is no loop initialization. We are thus basically a while loop. 10006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // NULL out Block to force lazy block construction. 10012bac4ea765a4a6e1f6149964663f62d4bca6743bTed Kremenek Block = NULL; 10025482713d70ecbfe608940018046aa248b3d03443Ted Kremenek Succ = EntryConditionBlock; 100349af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek return EntryConditionBlock; 10042bac4ea765a4a6e1f6149964663f62d4bca6743bTed Kremenek } 1005d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 1006d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1007514de5a21645900c92cf4f4f7313d6f66945d134Ted KremenekCFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { 1008514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // Objective-C fast enumeration 'for' statements: 1009514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC 1010514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1011514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // for ( Type newVariable in collection_expression ) { statements } 1012514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1013514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // becomes: 1014514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1015514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // prologue: 1016514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1. collection_expression 1017514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // T. jump to loop_entry 1018514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // loop_entry: 10194cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // 1. side-effects of element expression 1020514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1. ObjCForCollectionStmt [performs binding to newVariable] 1021514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil] 1022514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // TB: 1023514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // statements 1024514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // T. jump to loop_entry 1025514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // FB: 1026514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // what comes after 1027514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1028514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // and 1029514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1030514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // Type existingItem; 1031514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // for ( existingItem in expression ) { statements } 1032514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 1033514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // becomes: 1034514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 10356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the same with newVariable replaced with existingItem; the binding works 10366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the same except that for one ObjCForCollectionStmt::getElement() returns 10376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // a DeclStmt and the other returns a DeclRefExpr. 1038514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // 10396d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1040514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek CFGBlock* LoopSuccessor = 0; 10416d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1042514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek if (Block) { 10434e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 10444e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 1045514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek LoopSuccessor = Block; 1046514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek Block = 0; 10474f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } else 10484f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LoopSuccessor = Succ; 10496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10504cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Build the condition blocks. 10514cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek CFGBlock* ExitConditionBlock = createBlock(false); 10524cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek CFGBlock* EntryConditionBlock = ExitConditionBlock; 10536d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10544cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Set the terminator for the "exit" condition block. 10556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ExitConditionBlock->setTerminator(S); 10566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // The last statement in the block should be the ObjCForCollectionStmt, which 10586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // performs the actual binding to 'element' and determines if there are any 10596d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // more items in the collection. 10604cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek ExitConditionBlock->appendStmt(S); 10614cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek Block = ExitConditionBlock; 10626d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10634cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Walk the 'element' expression to see if there are any side-effects. We 10646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // generate new blocks as necesary. We DON'T add the statement by default to 10656d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the CFG unless it contains control-flow. 10664f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek EntryConditionBlock = Visit(S->getElement(), false); 10676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (Block) { 10684e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(EntryConditionBlock)) 10694e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 10704e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek Block = 0; 10714e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 10726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10736d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // The condition block is the implicit successor for the loop body as well as 10746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // any code above the loop. 10754cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek Succ = EntryConditionBlock; 10766d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10774cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Now create the true branch. 10786d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump { 10794cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Save the current values for Succ, continue and break targets. 10804cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek SaveAndRestore<CFGBlock*> save_Succ(Succ), 10816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump save_continue(ContinueTargetBlock), save_break(BreakTargetBlock); 10826d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10834cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek BreakTargetBlock = LoopSuccessor; 10846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ContinueTargetBlock = EntryConditionBlock; 10856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10864f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* BodyBlock = addStmt(S->getBody()); 10876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10884cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek if (!BodyBlock) 10894cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;" 10904e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek else if (Block) { 10914e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(BodyBlock)) 10924e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 10934e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 10946d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10954cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // This new body block is a successor to our "exit" condition block. 10964cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek ExitConditionBlock->addSuccessor(BodyBlock); 10974cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek } 10986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 10994cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // Link up the condition block with the code that follows the loop. 11004cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek // (the false branch). 11014cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek ExitConditionBlock->addSuccessor(LoopSuccessor); 11024cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek 1103514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek // Now create a prologue block to contain the collection expression. 11044cb3a855df3b3f8d551565cae9f43939a301ea89Ted Kremenek Block = createBlock(); 1105514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek return addStmt(S->getCollection()); 11066d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump} 11076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1108b3b0b3624e462c2940f65b86e773bfc300005203Ted KremenekCFGBlock* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S) { 1109b3b0b3624e462c2940f65b86e773bfc300005203Ted Kremenek // FIXME: Add locking 'primitives' to CFG for @synchronized. 11106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1111b3b0b3624e462c2940f65b86e773bfc300005203Ted Kremenek // Inline the body. 11124f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *SyncBlock = addStmt(S->getSynchBody()); 11136d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1114da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek // The sync body starts its own basic block. This makes it a little easier 1115da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek // for diagnostic clients. 1116da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek if (SyncBlock) { 1117da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek if (!FinishBlock(SyncBlock)) 1118da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek return 0; 11196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1120da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek Block = 0; 1121da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek } 11226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1123da5348eda7bb45d715561249dec9833d51dfda67Ted Kremenek Succ = SyncBlock; 11246d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1125b3b0b3624e462c2940f65b86e773bfc300005203Ted Kremenek // Inline the sync expression. 11264f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return addStmt(S->getSynchExpr()); 1127b3b0b3624e462c2940f65b86e773bfc300005203Ted Kremenek} 11286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1129e31c0d206b872b056dc42c3af21b11d5de4edfd9Ted KremenekCFGBlock* CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt* S) { 11304f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // FIXME 113190658ec72542df44eb462c69056184d2946bdbceTed Kremenek return NYS(); 1132e31c0d206b872b056dc42c3af21b11d5de4edfd9Ted Kremenek} 1133514de5a21645900c92cf4f4f7313d6f66945d134Ted Kremenek 1134d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { 11355f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump // See if this is a known constant. 11365f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump bool KnownTrue = false; 11375f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump bool KnownFalse = false; 11385f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump Expr::EvalResult Result; 11395f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump if (W->getCond()->Evaluate(Result, *Context) 11405f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump && Result.Val.isInt()) { 11415f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump if (Result.Val.getInt().getBoolValue()) 11425f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump KnownTrue = true; 11435f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump else 11445f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump KnownFalse = true; 11455f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump } 11465f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump 1147d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* LoopSuccessor = NULL; 11486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1149fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump // "while" is a control-flow statement. Thus we stop processing the current 1150fefb9f7009702befaf715e7a8debc9505c3c8634Mike Stump // block. 1151d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Block) { 11524e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 11534e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 1154d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LoopSuccessor = Block; 11554f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } else 11564f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LoopSuccessor = Succ; 11576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Because of short-circuit evaluation, the condition of the loop can span 11596d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 11606d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // evaluate the condition. 116149af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* ExitConditionBlock = createBlock(false); 116249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* EntryConditionBlock = ExitConditionBlock; 11636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 116449af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek // Set the terminator for the "exit" condition block. 116549af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek ExitConditionBlock->setTerminator(W); 11666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11676d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now add the actual condition to the condition block. Because the condition 11686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // itself may contain control-flow, new blocks may be created. Thus we update 11696d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // "Succ" after adding the condition. 117049af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek if (Stmt* C = W->getCond()) { 117149af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Block = ExitConditionBlock; 117249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek EntryConditionBlock = addStmt(C); 1173f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek assert(Block == EntryConditionBlock); 11744e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 11754e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(EntryConditionBlock)) 11764e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 11774e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 117849af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek } 11796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 11806d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // The condition block is the implicit successor for the loop body as well as 11816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // any code above the loop. 118249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Succ = EntryConditionBlock; 11836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1184d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Process the loop body. 1185d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek { 1186f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek assert(W->getBody()); 1187d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1188d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Save the current values for Block, Succ, and continue and break targets 1189d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1190d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek save_continue(ContinueTargetBlock), 1191d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek save_break(BreakTargetBlock); 1192f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek 11936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Create an empty block to represent the transition block for looping back 11946d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // to the head of the loop. 1195f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek Block = 0; 1196f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek assert(Succ == EntryConditionBlock); 1197f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek Succ = createBlock(); 1198f6e8541dd884029b85483a319ce7d32f3e476dccTed Kremenek Succ->setLoopTarget(W); 11996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ContinueTargetBlock = Succ; 12006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1201d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // All breaks should go to the code following the loop. 1202d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek BreakTargetBlock = LoopSuccessor; 12036d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1204d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // NULL out Block to force lazy instantiation of blocks for the body. 1205f752fcfae84fbf21b78383bf2461633382d51844Ted Kremenek Block = NULL; 12066d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1207d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Create the body. The returned block is the entry to the loop body. 12084f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock* BodyBlock = addStmt(W->getBody()); 12096d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1210af603f742491dc4707138c0293d295171fdd51baTed Kremenek if (!BodyBlock) 1211a9d996dbeb719200c4a9d86f68166a237583025fTed Kremenek BodyBlock = EntryConditionBlock; // can happen for "while(...) ;" 12124e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek else if (Block) { 12134e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(BodyBlock)) 12144e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 12154e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 12166d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12175f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump if (KnownFalse) 12185f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump ExitConditionBlock->addSuccessor(0); 12195f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump else { 12205f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump // Add the loop body entry as a successor to the condition. 12215f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump ExitConditionBlock->addSuccessor(BodyBlock); 12225f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump } 1223bf15b278a439d73b605ec00a8d3977ef305712f4Ted Kremenek } 12246d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12255f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump if (KnownTrue) 12265f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump ExitConditionBlock->addSuccessor(0); 12275f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump else { 12285f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump // Link up the condition block with the code that follows the loop. (the 12295f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump // false branch). 12305f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump ExitConditionBlock->addSuccessor(LoopSuccessor); 12315f20363dc8ea094b3f6139f52084beb10d6fcd85Mike Stump } 12326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12336d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // There can be no more statements in the condition block since we loop back 12346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // to this block. NULL out Block to force lazy creation of another block. 1235d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = NULL; 12366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1237d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Return the condition block, which is the dominating block for the loop. 12385482713d70ecbfe608940018046aa248b3d03443Ted Kremenek Succ = EntryConditionBlock; 123949af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek return EntryConditionBlock; 1240d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 12414f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 12424f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 12434f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt* S) { 12444f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // FIXME: For now we pretend that @catch and the code it contains does not 12454f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // exit. 12464f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return Block; 12474f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 12486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12492fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted KremenekCFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) { 12502fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek // FIXME: This isn't complete. We basically treat @throw like a return 12512fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek // statement. 12526d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12536d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // If we were in the middle of a block we stop processing that block and 12546d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // reverse its statements. 12554f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (Block && !FinishBlock(Block)) 12564f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return 0; 12576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12582fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek // Create the new block. 12592fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek Block = createBlock(false); 12606d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12612fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek // The Exit block is the only successor. 12622fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek Block->addSuccessor(&cfg->getExit()); 12636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 12646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Add the statement to the block. This may create new blocks if S contains 12656d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // control-flow (short-circuit operations). 12664f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitStmt(S, true); 12672fda504dccd79f91ac9a7d82acecfbab3eaa1719Ted Kremenek} 1268989d52d469df0c202f7de82f54407066c7db2e63Ted Kremenek 12690979d80615df97c675423de631c1b884819f4712Mike StumpCFGBlock* CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr* T) { 12700979d80615df97c675423de631c1b884819f4712Mike Stump // If we were in the middle of a block we stop processing that block and 12710979d80615df97c675423de631c1b884819f4712Mike Stump // reverse its statements. 12720979d80615df97c675423de631c1b884819f4712Mike Stump if (Block && !FinishBlock(Block)) 12730979d80615df97c675423de631c1b884819f4712Mike Stump return 0; 12740979d80615df97c675423de631c1b884819f4712Mike Stump 12750979d80615df97c675423de631c1b884819f4712Mike Stump // Create the new block. 12760979d80615df97c675423de631c1b884819f4712Mike Stump Block = createBlock(false); 12770979d80615df97c675423de631c1b884819f4712Mike Stump 12780979d80615df97c675423de631c1b884819f4712Mike Stump // The Exit block is the only successor. 12790979d80615df97c675423de631c1b884819f4712Mike Stump Block->addSuccessor(&cfg->getExit()); 12800979d80615df97c675423de631c1b884819f4712Mike Stump 12810979d80615df97c675423de631c1b884819f4712Mike Stump // Add the statement to the block. This may create new blocks if S contains 12820979d80615df97c675423de631c1b884819f4712Mike Stump // control-flow (short-circuit operations). 12830979d80615df97c675423de631c1b884819f4712Mike Stump return VisitStmt(T, true); 12840979d80615df97c675423de631c1b884819f4712Mike Stump} 12850979d80615df97c675423de631c1b884819f4712Mike Stump 12864f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { 12878f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump // See if this is a known constant. 12888f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump bool KnownTrue = false; 12898f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump bool KnownFalse = false; 12908f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump Expr::EvalResult Result; 12918f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump if (D->getCond()->Evaluate(Result, *Context) 12928f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump && Result.Val.isInt()) { 12938f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump if (Result.Val.getInt().getBoolValue()) 12948f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump KnownTrue = true; 12958f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump else 12968f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump KnownFalse = true; 12978f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump } 12986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1299d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* LoopSuccessor = NULL; 13006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13018f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump // "do...while" is a control-flow statement. Thus we stop processing the 13028f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump // current block. 1303d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Block) { 13044e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 13054e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 1306d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek LoopSuccessor = Block; 13074f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek } else 13084f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek LoopSuccessor = Succ; 13096d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Because of short-circuit evaluation, the condition of the loop can span 13116d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 13126d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // evaluate the condition. 131349af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* ExitConditionBlock = createBlock(false); 131449af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* EntryConditionBlock = ExitConditionBlock; 13156d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 131649af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek // Set the terminator for the "exit" condition block. 13176d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump ExitConditionBlock->setTerminator(D); 13186d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Now add the actual condition to the condition block. Because the condition 13206d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // itself may contain control-flow, new blocks may be created. 132149af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek if (Stmt* C = D->getCond()) { 132249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Block = ExitConditionBlock; 132349af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek EntryConditionBlock = addStmt(C); 13244e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 13254e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(EntryConditionBlock)) 13264e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 13274e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 132849af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek } 13296d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13305482713d70ecbfe608940018046aa248b3d03443Ted Kremenek // The condition block is the implicit successor for the loop body. 133149af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Succ = EntryConditionBlock; 133249af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek 1333d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Process the loop body. 133449af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek CFGBlock* BodyBlock = NULL; 1335d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek { 1336d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek assert (D->getBody()); 13376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1338d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Save the current values for Block, Succ, and continue and break targets 1339d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1340d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek save_continue(ContinueTargetBlock), 1341d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek save_break(BreakTargetBlock); 13426d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1343d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // All continues within this loop should go to the condition block 134449af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek ContinueTargetBlock = EntryConditionBlock; 13456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1346d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // All breaks should go to the code following the loop. 1347d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek BreakTargetBlock = LoopSuccessor; 13486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1349d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // NULL out Block to force lazy instantiation of blocks for the body. 1350b5c13b0f4e438391b31dacb87641be7a1b990b57Ted Kremenek Block = NULL; 13516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1352d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Create the body. The returned block is the entry to the loop body. 13534f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek BodyBlock = addStmt(D->getBody()); 13546d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1355af603f742491dc4707138c0293d295171fdd51baTed Kremenek if (!BodyBlock) 1356a9d996dbeb719200c4a9d86f68166a237583025fTed Kremenek BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" 13574e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek else if (Block) { 13584e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(BodyBlock)) 13594e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 13604e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 13616d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13628f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek // Add an intermediate block between the BodyBlock and the 13636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // ExitConditionBlock to represent the "loop back" transition. Create an 13646d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // empty block to represent the transition block for looping back to the 13656d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // head of the loop. 13668f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek // FIXME: Can we do this more efficiently without adding another block? 13678f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek Block = NULL; 13688f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek Succ = BodyBlock; 13698f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek CFGBlock *LoopBackBlock = createBlock(); 13708f08c9d83fdabb6f27c44a4dbce78487519c89ebTed Kremenek LoopBackBlock->setLoopTarget(D); 13716d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13728f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump if (KnownFalse) 13738f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump ExitConditionBlock->addSuccessor(0); 13748f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump else { 13758f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump // Add the loop body entry as a successor to the condition. 13768f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump ExitConditionBlock->addSuccessor(LoopBackBlock); 13778f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump } 1378b5c13b0f4e438391b31dacb87641be7a1b990b57Ted Kremenek } 13796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13808f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump if (KnownTrue) 13818f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump ExitConditionBlock->addSuccessor(0); 13828f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump else { 13838f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump // Link up the condition block with the code that follows the loop. (the 13848f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump // false branch). 13858f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump ExitConditionBlock->addSuccessor(LoopSuccessor); 13868f9893a2beeacd5149bd2d3d4c6e130516915068Mike Stump } 13876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 13886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // There can be no more statements in the body block(s) since we loop back to 13896d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the body. NULL out Block to force lazy creation of another block. 1390d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = NULL; 13916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1392d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Return the loop body, which is the dominating block for the loop. 13935482713d70ecbfe608940018046aa248b3d03443Ted Kremenek Succ = BodyBlock; 1394d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek return BodyBlock; 1395d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 1396d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1397d4fdee35477e439759eea5f67ea03ff0c570fabaTed KremenekCFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) { 1398d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // "continue" is a control-flow statement. Thus we stop processing the 1399d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // current block. 14004f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (Block && !FinishBlock(Block)) 14014e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 14026d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1403d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Now create a new block that ends with the continue statement. 1404d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = createBlock(false); 1405d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block->setTerminator(C); 14066d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1407d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // If there is no target for the continue, then we are looking at an 1408235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek // incomplete AST. This means the CFG cannot be constructed. 1409235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek if (ContinueTargetBlock) 1410235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek Block->addSuccessor(ContinueTargetBlock); 1411235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek else 1412235c5ed8bee5bbcb45de1707d6988635e49b10b8Ted Kremenek badCFG = true; 14136d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1414d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek return Block; 1415d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 14164f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 141713fc08a323b29dd97a46def1e3a15bf082476efaTed KremenekCFGBlock *CFGBuilder::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, 141813fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek bool alwaysAdd) { 141913fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek 142013fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek if (alwaysAdd) { 142113fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek autoCreateBlock(); 142213fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek Block->appendStmt(E); 142313fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek } 142413fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek 14254f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek // VLA types have expressions that must be evaluated. 14264f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (E->isArgumentType()) { 14274f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek for (VariableArrayType* VA = FindVA(E->getArgumentType().getTypePtr()); 14284f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) 14294f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek addStmt(VA->getSizeExpr()); 14304e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 14314f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 14326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return Block; 1433d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 14344f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 14354f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek/// VisitStmtExpr - Utility method to handle (nested) statement 14364f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek/// expressions (a GCC extension). 143713fc08a323b29dd97a46def1e3a15bf082476efaTed KremenekCFGBlock* CFGBuilder::VisitStmtExpr(StmtExpr *SE, bool alwaysAdd) { 143813fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek if (alwaysAdd) { 143913fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek autoCreateBlock(); 144013fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek Block->appendStmt(SE); 144113fc08a323b29dd97a46def1e3a15bf082476efaTed Kremenek } 14424f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return VisitCompoundStmt(SE->getSubStmt()); 14434f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek} 1444d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1445411cdee0b490f79428c9eb977f25199eb7d21cd8Ted KremenekCFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { 14466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // "switch" is a control-flow statement. Thus we stop processing the current 14476d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block. 1448d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek CFGBlock* SwitchSuccessor = NULL; 14496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1450d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek if (Block) { 14514e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(Block)) 14524e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 1453d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SwitchSuccessor = Block; 14546d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else SwitchSuccessor = Succ; 1455d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 1456d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Save the current "switch" context. 1457d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), 1458eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek save_break(BreakTargetBlock), 1459eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek save_default(DefaultCaseBlock); 1460eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek 14616d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Set the "default" case to be the block after the switch statement. If the 14626d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // switch statement contains a "default:", this value will be overwritten with 14636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the block for that code. 1464eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek DefaultCaseBlock = SwitchSuccessor; 14656d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1466d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Create a new block that will contain the switch statement. 1467d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek SwitchTerminatedBlock = createBlock(false); 14686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1469d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Now process the switch body. The code after the switch is the implicit 1470d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // successor. 1471d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Succ = SwitchSuccessor; 1472d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek BreakTargetBlock = SwitchSuccessor; 14736d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 14746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // When visiting the body, the case statements should automatically get linked 14756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // up to the switch. We also don't keep a pointer to the body, since all 14766d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // control-flow from the switch goes to case/default statements. 1477411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek assert (Terminator->getBody() && "switch must contain a non-NULL body"); 147849af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek Block = NULL; 14794f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CFGBlock *BodyBlock = addStmt(Terminator->getBody()); 14804e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (Block) { 14814e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(BodyBlock)) 14824e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 14834e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek } 148449af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek 14856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // If we have no "default:" case, the default transition is to the code 14866d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // following the switch body. 1487eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek SwitchTerminatedBlock->addSuccessor(DefaultCaseBlock); 14886d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 148949af7cb8a3aca79783e7a0708b97a8f856f0da22Ted Kremenek // Add the terminator and condition in the switch block. 1490411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek SwitchTerminatedBlock->setTerminator(Terminator); 1491411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek assert (Terminator->getCond() && "switch condition must be non-NULL"); 1492d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = SwitchTerminatedBlock; 14936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1494411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek return addStmt(Terminator->getCond()); 1495d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 1496d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 14974f88063677a2d990a44bb0d5f8437d2498b91d7fTed KremenekCFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) { 14986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // CaseStmts are essentially labels, so they are the first statement in a 14996d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block. 150029ccaa186ac27bcb414c5acb069f6438b27dd5e7Ted Kremenek 15014f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (CS->getSubStmt()) 15024f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek addStmt(CS->getSubStmt()); 15034f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 150429ccaa186ac27bcb414c5acb069f6438b27dd5e7Ted Kremenek CFGBlock* CaseBlock = Block; 15054f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (!CaseBlock) 15064f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CaseBlock = createBlock(); 15076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 15086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Cases statements partition blocks, so this is the top of the basic block we 15096d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // were processing (the "case XXX:" is the label). 15104f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek CaseBlock->setLabel(CS); 15114f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 15124e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(CaseBlock)) 15134e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 15146d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 15156d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Add this block to the list of successors for the block with the switch 15166d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // statement. 15174f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek assert(SwitchTerminatedBlock); 1518eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek SwitchTerminatedBlock->addSuccessor(CaseBlock); 15196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1520d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // We set Block to NULL to allow lazy creation of a new block (if necessary) 1521d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Block = NULL; 15226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1523d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // This block is now the implicit successor of other blocks. 1524d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek Succ = CaseBlock; 15256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 15262677ea871a25aa79f9db360f6ed10584c02267adTed Kremenek return CaseBlock; 1527d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek} 15286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1529411cdee0b490f79428c9eb977f25199eb7d21cd8Ted KremenekCFGBlock* CFGBuilder::VisitDefaultStmt(DefaultStmt* Terminator) { 15304f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (Terminator->getSubStmt()) 15314f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek addStmt(Terminator->getSubStmt()); 15324f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 1533eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek DefaultCaseBlock = Block; 15344f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 15354f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (!DefaultCaseBlock) 15364f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek DefaultCaseBlock = createBlock(); 15376d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 15386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Default statements partition blocks, so this is the top of the basic block 15396d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // we were processing (the "default:" is the label). 1540411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek DefaultCaseBlock->setLabel(Terminator); 15414f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 15424e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek if (!FinishBlock(DefaultCaseBlock)) 15434e8df2eb7072db8f66572c3db31a2a08b12a752eTed Kremenek return 0; 1544eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek 15456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Unlike case statements, we don't add the default block to the successors 15466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // for the switch statement immediately. This is done when we finish 15476d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // processing the switch statement. This allows for the default case 15486d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // (including a fall-through to the code after the switch statement) to always 15496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // be the last successor of a switch-terminated block. 15506d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1551eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek // We set Block to NULL to allow lazy creation of a new block (if necessary) 1552eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek Block = NULL; 15536d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1554eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek // This block is now the implicit successor of other blocks. 1555eef5a9ac59f4f8b868ef0657ccf6bec81b4fe37aTed Kremenek Succ = DefaultCaseBlock; 15566d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 15576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return DefaultCaseBlock; 1558295222c1f0926d84de77f076e79903523eeb5dbfTed Kremenek} 1559d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek 156019bb356317952445b03ee341c02f6147083c9eeaTed KremenekCFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { 15616d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Lazily create the indirect-goto dispatch block if there isn't one already. 156219bb356317952445b03ee341c02f6147083c9eeaTed Kremenek CFGBlock* IBlock = cfg->getIndirectGotoBlock(); 15636d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 156419bb356317952445b03ee341c02f6147083c9eeaTed Kremenek if (!IBlock) { 156519bb356317952445b03ee341c02f6147083c9eeaTed Kremenek IBlock = createBlock(false); 156619bb356317952445b03ee341c02f6147083c9eeaTed Kremenek cfg->setIndirectGotoBlock(IBlock); 156719bb356317952445b03ee341c02f6147083c9eeaTed Kremenek } 15686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 156919bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // IndirectGoto is a control-flow statement. Thus we stop processing the 157019bb356317952445b03ee341c02f6147083c9eeaTed Kremenek // current block and create a new one. 15714f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek if (Block && !FinishBlock(Block)) 15724f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek return 0; 15734f88063677a2d990a44bb0d5f8437d2498b91d7fTed Kremenek 157419bb356317952445b03ee341c02f6147083c9eeaTed Kremenek Block = createBlock(false); 157519bb356317952445b03ee341c02f6147083c9eeaTed Kremenek Block->setTerminator(I); 157619bb356317952445b03ee341c02f6147083c9eeaTed Kremenek Block->addSuccessor(IBlock); 157719bb356317952445b03ee341c02f6147083c9eeaTed Kremenek return addStmt(I->getTarget()); 157819bb356317952445b03ee341c02f6147083c9eeaTed Kremenek} 157919bb356317952445b03ee341c02f6147083c9eeaTed Kremenek 1580befef2f69759d7338e2b7c5ce6c8b6f47fe6e667Ted Kremenek} // end anonymous namespace 1581026473c2175424a039f51ca8949937268721b965Ted Kremenek 15826d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has 15836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// no successors or predecessors. If this is the first block created in the 15846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump/// CFG, it is automatically set to be the Entry and Exit of the CFG. 15859438252ad2ecae5338df565ca33c6969e4fbfa41Ted KremenekCFGBlock* CFG::createBlock() { 1586026473c2175424a039f51ca8949937268721b965Ted Kremenek bool first_block = begin() == end(); 1587026473c2175424a039f51ca8949937268721b965Ted Kremenek 1588026473c2175424a039f51ca8949937268721b965Ted Kremenek // Create the block. 15899438252ad2ecae5338df565ca33c6969e4fbfa41Ted Kremenek Blocks.push_front(CFGBlock(NumBlockIDs++)); 1590026473c2175424a039f51ca8949937268721b965Ted Kremenek 1591026473c2175424a039f51ca8949937268721b965Ted Kremenek // If this is the first block, set it as the Entry and Exit. 1592026473c2175424a039f51ca8949937268721b965Ted Kremenek if (first_block) Entry = Exit = &front(); 1593026473c2175424a039f51ca8949937268721b965Ted Kremenek 1594026473c2175424a039f51ca8949937268721b965Ted Kremenek // Return the block. 1595026473c2175424a039f51ca8949937268721b965Ted Kremenek return &front(); 1596026473c2175424a039f51ca8949937268721b965Ted Kremenek} 1597026473c2175424a039f51ca8949937268721b965Ted Kremenek 1598026473c2175424a039f51ca8949937268721b965Ted Kremenek/// buildCFG - Constructs a CFG from an AST. Ownership of the returned 1599026473c2175424a039f51ca8949937268721b965Ted Kremenek/// CFG is returned to the caller. 1600e5af3ce53ec58995b09381ba645ab2117a46647bMike StumpCFG* CFG::buildCFG(Stmt* Statement, ASTContext *C) { 1601fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek CFGBuilder Builder; 1602e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump return Builder.buildCFG(Statement, C); 1603fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek} 1604fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 1605026473c2175424a039f51ca8949937268721b965Ted Kremenek/// reverseStmts - Reverses the orders of statements within a CFGBlock. 1606fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenekvoid CFGBlock::reverseStmts() { std::reverse(Stmts.begin(),Stmts.end()); } 1607fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 160863f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek//===----------------------------------------------------------------------===// 160963f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek// CFG: Queries for BlkExprs. 161063f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek//===----------------------------------------------------------------------===// 161163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 161263f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremeneknamespace { 161386946745225096243f6969dc745267b78fc211a6Ted Kremenek typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy; 161463f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek} 161563f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 1616411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenekstatic void FindSubExprAssignments(Stmt* Terminator, llvm::SmallPtrSet<Expr*,50>& Set) { 1617411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (!Terminator) 161833d4aab80f31bd06257526fe2883ea920529456bTed Kremenek return; 16196d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1620411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek for (Stmt::child_iterator I=Terminator->child_begin(), E=Terminator->child_end(); I!=E; ++I) { 162133d4aab80f31bd06257526fe2883ea920529456bTed Kremenek if (!*I) continue; 16226d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 162333d4aab80f31bd06257526fe2883ea920529456bTed Kremenek if (BinaryOperator* B = dyn_cast<BinaryOperator>(*I)) 162433d4aab80f31bd06257526fe2883ea920529456bTed Kremenek if (B->isAssignmentOp()) Set.insert(B); 16256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 162633d4aab80f31bd06257526fe2883ea920529456bTed Kremenek FindSubExprAssignments(*I, Set); 162733d4aab80f31bd06257526fe2883ea920529456bTed Kremenek } 162833d4aab80f31bd06257526fe2883ea920529456bTed Kremenek} 162933d4aab80f31bd06257526fe2883ea920529456bTed Kremenek 163063f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenekstatic BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { 163163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek BlkExprMapTy* M = new BlkExprMapTy(); 16326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 16336d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Look for assignments that are used as subexpressions. These are the only 16346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // assignments that we want to *possibly* register as a block-level 16356d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // expression. Basically, if an assignment occurs both in a subexpression and 16366d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // at the block-level, it is a block-level expression. 163733d4aab80f31bd06257526fe2883ea920529456bTed Kremenek llvm::SmallPtrSet<Expr*,50> SubExprAssignments; 16386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 163963f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) 164063f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek for (CFGBlock::iterator BI=I->begin(), EI=I->end(); BI != EI; ++BI) 164133d4aab80f31bd06257526fe2883ea920529456bTed Kremenek FindSubExprAssignments(*BI, SubExprAssignments); 164286946745225096243f6969dc745267b78fc211a6Ted Kremenek 1643411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { 16446d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 16456d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Iterate over the statements again on identify the Expr* and Stmt* at the 16466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // block-level that are block-level expressions. 1647411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek 164833d4aab80f31bd06257526fe2883ea920529456bTed Kremenek for (CFGBlock::iterator BI=I->begin(), EI=I->end(); BI != EI; ++BI) 1649411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (Expr* Exp = dyn_cast<Expr>(*BI)) { 16506d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1651411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { 165233d4aab80f31bd06257526fe2883ea920529456bTed Kremenek // Assignment expressions that are not nested within another 16536d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // expression are really "statements" whose value is never used by 16546d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // another expression. 1655411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (B->isAssignmentOp() && !SubExprAssignments.count(Exp)) 165633d4aab80f31bd06257526fe2883ea920529456bTed Kremenek continue; 16576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else if (const StmtExpr* Terminator = dyn_cast<StmtExpr>(Exp)) { 16586d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // Special handling for statement expressions. The last statement in 16596d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump // the statement expression is also a block-level expr. 1660411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek const CompoundStmt* C = Terminator->getSubStmt(); 166186946745225096243f6969dc745267b78fc211a6Ted Kremenek if (!C->body_empty()) { 166233d4aab80f31bd06257526fe2883ea920529456bTed Kremenek unsigned x = M->size(); 166386946745225096243f6969dc745267b78fc211a6Ted Kremenek (*M)[C->body_back()] = x; 166486946745225096243f6969dc745267b78fc211a6Ted Kremenek } 166586946745225096243f6969dc745267b78fc211a6Ted Kremenek } 1666e2dcd783a04f654c50bd8b13fb08a440afbd67e7Ted Kremenek 166733d4aab80f31bd06257526fe2883ea920529456bTed Kremenek unsigned x = M->size(); 1668411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek (*M)[Exp] = x; 166933d4aab80f31bd06257526fe2883ea920529456bTed Kremenek } 16706d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1671411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek // Look at terminators. The condition is a block-level expression. 16726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1673390e48b15ad93f85bfd1e33b9992c198fa0db475Ted Kremenek Stmt* S = I->getTerminatorCondition(); 16746d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1675390e48b15ad93f85bfd1e33b9992c198fa0db475Ted Kremenek if (S && M->find(S) == M->end()) { 1676411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek unsigned x = M->size(); 1677390e48b15ad93f85bfd1e33b9992c198fa0db475Ted Kremenek (*M)[S] = x; 1678411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek } 1679411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek } 16806d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 168186946745225096243f6969dc745267b78fc211a6Ted Kremenek return M; 168263f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek} 168363f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 168486946745225096243f6969dc745267b78fc211a6Ted KremenekCFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) { 168586946745225096243f6969dc745267b78fc211a6Ted Kremenek assert(S != NULL); 168663f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } 16876d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 168863f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap); 168986946745225096243f6969dc745267b78fc211a6Ted Kremenek BlkExprMapTy::iterator I = M->find(S); 16906d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 169163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek if (I == M->end()) return CFG::BlkExprNumTy(); 169263f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek else return CFG::BlkExprNumTy(I->second); 169363f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek} 16947dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 169563f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenekunsigned CFG::getNumBlkExprs() { 169663f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) 169763f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek return M->size(); 169863f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek else { 169963f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek // We assume callers interested in the number of BlkExprs will want 170063f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek // the map constructed if it doesn't already exist. 170163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek BlkExprMap = (void*) PopulateBlkExprMap(*this); 170263f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); 170363f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek } 170463f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek} 170563f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek 1706274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek//===----------------------------------------------------------------------===// 1707274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek// Cleanup: CFG dstor. 1708274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek//===----------------------------------------------------------------------===// 1709274f4334f6dd35239e5c3d4b86198f7f5804b059Ted Kremenek 171063f5887f316fb52d243fcbb3631c039de6c4b993Ted KremenekCFG::~CFG() { 171163f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); 171263f5887f316fb52d243fcbb3631c039de6c4b993Ted Kremenek} 17136d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 17147dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 17157dba8607e59096014b7139ff20ef00870041d518Ted Kremenek// CFG pretty printing 17167dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 17177dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 171842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremeneknamespace { 17192bac4ea765a4a6e1f6149964663f62d4bca6743bTed Kremenek 17206fa9b88e2c3d47d606a273df2f8d03509bcff0b9Ted Kremenekclass VISIBILITY_HIDDEN StmtPrinterHelper : public PrinterHelper { 17216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 172242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; 172342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek StmtMapTy StmtMap; 172442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek signed CurrentBlock; 172542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek unsigned CurrentStmt; 1726e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner const LangOptions &LangOpts; 172742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenekpublic: 17281c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek 1729e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) 1730e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner : CurrentBlock(0), CurrentStmt(0), LangOpts(LO) { 173142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { 173242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek unsigned j = 1; 173342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (CFGBlock::const_iterator BI = I->begin(), BEnd = I->end() ; 173442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek BI != BEnd; ++BI, ++j ) 173542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek StmtMap[*BI] = std::make_pair(I->getBlockID(),j); 173642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek } 1737fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 17386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 173942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek virtual ~StmtPrinterHelper() {} 17406d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1741e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner const LangOptions &getLangOpts() const { return LangOpts; } 174242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek void setBlockID(signed i) { CurrentBlock = i; } 174342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek void setStmtID(unsigned i) { CurrentStmt = i; } 17446d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1745a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek virtual bool handledStmt(Stmt* Terminator, llvm::raw_ostream& OS) { 17466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1747411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek StmtMapTy::iterator I = StmtMap.find(Terminator); 1748fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek 174942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (I == StmtMap.end()) 175042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek return false; 17516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 17526d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump if (CurrentBlock >= 0 && I->second.first == (unsigned) CurrentBlock 175342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek && I->second.second == CurrentStmt) 175442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek return false; 17556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 17561c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek OS << "[B" << I->second.first << "." << I->second.second << "]"; 17571c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek return true; 175842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek } 175942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek}; 1760e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner} // end anonymous namespace 1761e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner 1762e8ee26b49d68ae3ffdf9a990ff7511ef55afa04cTed Kremenek 1763e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnernamespace { 17646fa9b88e2c3d47d606a273df2f8d03509bcff0b9Ted Kremenekclass VISIBILITY_HIDDEN CFGBlockTerminatorPrint 17656fa9b88e2c3d47d606a273df2f8d03509bcff0b9Ted Kremenek : public StmtVisitor<CFGBlockTerminatorPrint,void> { 17666d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1767a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek llvm::raw_ostream& OS; 176842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek StmtPrinterHelper* Helper; 1769d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor PrintingPolicy Policy; 1770d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor 1771d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenekpublic: 1772d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor CFGBlockTerminatorPrint(llvm::raw_ostream& os, StmtPrinterHelper* helper, 1773e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner const PrintingPolicy &Policy) 1774d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor : OS(os), Helper(helper), Policy(Policy) {} 17756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1776d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek void VisitIfStmt(IfStmt* I) { 1777d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek OS << "if "; 1778d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor I->getCond()->printPretty(OS,Helper,Policy); 1779d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek } 17806d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1781d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek // Default case. 17826d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump void VisitStmt(Stmt* Terminator) { 17836d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump Terminator->printPretty(OS, Helper, Policy); 17846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 17856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1786d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek void VisitForStmt(ForStmt* F) { 1787d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek OS << "for (" ; 1788535bb20b6e252809bc17cc59b5d71b5e5e549e70Ted Kremenek if (F->getInit()) OS << "..."; 1789535bb20b6e252809bc17cc59b5d71b5e5e549e70Ted Kremenek OS << "; "; 1790d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor if (Stmt* C = F->getCond()) C->printPretty(OS, Helper, Policy); 1791535bb20b6e252809bc17cc59b5d71b5e5e549e70Ted Kremenek OS << "; "; 1792535bb20b6e252809bc17cc59b5d71b5e5e549e70Ted Kremenek if (F->getInc()) OS << "..."; 1793a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek OS << ")"; 1794d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek } 17956d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1796d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek void VisitWhileStmt(WhileStmt* W) { 1797d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek OS << "while " ; 1798d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor if (Stmt* C = W->getCond()) C->printPretty(OS, Helper, Policy); 1799d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek } 18006d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1801d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek void VisitDoStmt(DoStmt* D) { 1802d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek OS << "do ... while "; 1803d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor if (Stmt* C = D->getCond()) C->printPretty(OS, Helper, Policy); 18049da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek } 18056d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1806411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek void VisitSwitchStmt(SwitchStmt* Terminator) { 18079da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek OS << "switch "; 1808d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor Terminator->getCond()->printPretty(OS, Helper, Policy); 18099da2fb773c473b989c78c513c5ce61641e9bbb4dTed Kremenek } 18106d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1811805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek void VisitConditionalOperator(ConditionalOperator* C) { 1812d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor C->getCond()->printPretty(OS, Helper, Policy); 18136d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump OS << " ? ... : ..."; 1814805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek } 18156d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1816aeddbf689eb3e3afca5117ca83c7b2e18260b0d8Ted Kremenek void VisitChooseExpr(ChooseExpr* C) { 1817aeddbf689eb3e3afca5117ca83c7b2e18260b0d8Ted Kremenek OS << "__builtin_choose_expr( "; 1818d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor C->getCond()->printPretty(OS, Helper, Policy); 1819a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek OS << " )"; 1820aeddbf689eb3e3afca5117ca83c7b2e18260b0d8Ted Kremenek } 18216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 18221c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek void VisitIndirectGotoStmt(IndirectGotoStmt* I) { 18231c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek OS << "goto *"; 1824d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor I->getTarget()->printPretty(OS, Helper, Policy); 18251c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek } 18266d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1827805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek void VisitBinaryOperator(BinaryOperator* B) { 1828805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek if (!B->isLogicalOp()) { 1829805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek VisitExpr(B); 1830805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek return; 1831805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek } 18326d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1833d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor B->getLHS()->printPretty(OS, Helper, Policy); 18346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1835805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek switch (B->getOpcode()) { 1836805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek case BinaryOperator::LOr: 1837a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek OS << " || ..."; 1838805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek return; 1839805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek case BinaryOperator::LAnd: 1840a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek OS << " && ..."; 1841805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek return; 1842805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek default: 1843805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek assert(false && "Invalid logical operator."); 18446d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 1845805e9a8300af9489ec13cd804c070267b7c4cfecTed Kremenek } 18466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 18470b1d9b7557437176f9cea1283bfac2510812beceTed Kremenek void VisitExpr(Expr* E) { 1848d249e1d1f1498b81314459ceda19d6ff25c278adDouglas Gregor E->printPretty(OS, Helper, Policy); 18496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 1850d4fdee35477e439759eea5f67ea03ff0c570fabaTed Kremenek}; 1851e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner} // end anonymous namespace 1852e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner 18536d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1854e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnerstatic void print_stmt(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, 1855e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner Stmt* Terminator) { 18561c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek if (Helper) { 18571c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek // special printing for statement-expressions. 1858411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (StmtExpr* SE = dyn_cast<StmtExpr>(Terminator)) { 18591c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek CompoundStmt* Sub = SE->getSubStmt(); 18606d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 18611c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek if (Sub->child_begin() != Sub->child_end()) { 186260266e8a9a4cd941af5e0006a18377dc03f0421bTed Kremenek OS << "({ ... ; "; 18637a9d9d71fa208dc23fd67d03ce052d4ef60a8d04Ted Kremenek Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); 186460266e8a9a4cd941af5e0006a18377dc03f0421bTed Kremenek OS << " })\n"; 18651c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek return; 18661c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek } 18671c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek } 18686d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 18691c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek // special printing for comma expressions. 1870411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (BinaryOperator* B = dyn_cast<BinaryOperator>(Terminator)) { 18711c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek if (B->getOpcode() == BinaryOperator::Comma) { 18721c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek OS << "... , "; 18731c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek Helper->handledStmt(B->getRHS(),OS); 18741c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek OS << '\n'; 18751c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek return; 18766d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 18776d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } 18781c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek } 18796d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1880e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner Terminator->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 18816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 18821c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek // Expressions need a newline. 1883411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (isa<Expr>(Terminator)) OS << '\n'; 18841c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek} 18856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1886e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnerstatic void print_block(llvm::raw_ostream& OS, const CFG* cfg, 1887e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner const CFGBlock& B, 1888e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner StmtPrinterHelper* Helper, bool print_edges) { 18896d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 189042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (Helper) Helper->setBlockID(B.getBlockID()); 18916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 18927dba8607e59096014b7139ff20ef00870041d518Ted Kremenek // Print the header. 18936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump OS << "\n [ B" << B.getBlockID(); 18946d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 189542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (&B == &cfg->getEntry()) 189642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " (ENTRY) ]\n"; 189742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek else if (&B == &cfg->getExit()) 189842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " (EXIT) ]\n"; 189942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek else if (&B == cfg->getIndirectGotoBlock()) 19007dba8607e59096014b7139ff20ef00870041d518Ted Kremenek OS << " (INDIRECT GOTO DISPATCH) ]\n"; 190142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek else 190242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " ]\n"; 19036d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 19049cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek // Print the label of this block. 1905411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (Stmt* Terminator = const_cast<Stmt*>(B.getLabel())) { 190642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 190742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (print_edges) 190842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " "; 19096d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1910411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (LabelStmt* L = dyn_cast<LabelStmt>(Terminator)) 19119cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << L->getName(); 1912411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek else if (CaseStmt* C = dyn_cast<CaseStmt>(Terminator)) { 19139cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << "case "; 1914e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner C->getLHS()->printPretty(OS, Helper, 1915e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner PrintingPolicy(Helper->getLangOpts())); 19169cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek if (C->getRHS()) { 19179cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << " ... "; 1918e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner C->getRHS()->printPretty(OS, Helper, 1919e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner PrintingPolicy(Helper->getLangOpts())); 19209cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek } 19216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump } else if (isa<DefaultStmt>(Terminator)) 19229cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << "default"; 192342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek else 192442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek assert(false && "Invalid label statement in CFGBlock."); 19256d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 19269cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << ":\n"; 19279cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek } 19286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1929fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek // Iterate through the statements in the block and print them. 1930fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek unsigned j = 1; 19316d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 193242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; 193342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek I != E ; ++I, ++j ) { 19346d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 19359cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek // Print the statement # in the basic block and the statement itself. 193642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (print_edges) 193742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " "; 19386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1939a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek OS << llvm::format("%3d", j) << ": "; 19406d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 194142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (Helper) 194242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek Helper->setStmtID(j); 19436d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 19441c29bba6da40bbe59fb1f81c4cd5ab5471554ffeTed Kremenek print_stmt(OS,Helper,*I); 1945fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 19466d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 19479cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek // Print the terminator of this block. 194842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (B.getTerminator()) { 194942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (print_edges) 195042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " "; 19516d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 19529cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << " T: "; 19536d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 195442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (Helper) Helper->setBlockID(-1); 19556d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 1956e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner CFGBlockTerminatorPrint TPrinter(OS, Helper, 1957e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner PrintingPolicy(Helper->getLangOpts())); 195842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek TPrinter.Visit(const_cast<Stmt*>(B.getTerminator())); 1959a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek OS << '\n'; 1960fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 19616d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 19629cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek if (print_edges) { 19639cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek // Print the predecessors of this block. 196442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " Predecessors (" << B.pred_size() << "):"; 19659cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek unsigned i = 0; 196642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 196742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); 196842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek I != E; ++I, ++i) { 19696d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 197042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (i == 8 || (i-8) == 0) 19719cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << "\n "; 19726d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 19739cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << " B" << (*I)->getBlockID(); 19749cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek } 19756d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 19769cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << '\n'; 19776d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 19789cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek // Print the successors of this block. 197942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek OS << " Successors (" << B.succ_size() << "):"; 19809cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek i = 0; 198142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 198242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); 198342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek I != E; ++I, ++i) { 19846d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 198542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (i == 8 || (i-8) % 10 == 0) 19869cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << "\n "; 198742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 1988e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump if (*I) 1989e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump OS << " B" << (*I)->getBlockID(); 1990e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump else 1991e5af3ce53ec58995b09381ba645ab2117a46647bMike Stump OS << " NULL"; 1992fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 19936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 19949cffe7366ea3beb33c2d58f43a8c3a04c1873e11Ted Kremenek OS << '\n'; 1995fddd51853f8ccaa1df2476376e6fd74d2f315c73Ted Kremenek } 19966d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump} 199742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 199842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 199942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek/// dump - A simple pretty printer of a CFG that outputs to stderr. 2000e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); } 200142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 200242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek/// print - A simple pretty printer of a CFG that outputs to an ostream. 2003e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFG::print(llvm::raw_ostream &OS, const LangOptions &LO) const { 2004e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner StmtPrinterHelper Helper(this, LO); 20056d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 200642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek // Print the entry block. 200742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek print_block(OS, this, getEntry(), &Helper, true); 20086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 200942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek // Iterate through the CFGBlocks and print them one by one. 201042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { 201142a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek // Skip the entry block, because we already printed it. 201242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek if (&(*I) == &getEntry() || &(*I) == &getExit()) 201342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek continue; 20146d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 201542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek print_block(OS, this, *I, &Helper, true); 201642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek } 20176d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 201842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek // Print the exit block. 201942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek print_block(OS, this, getExit(), &Helper, true); 2020d0172439194b28bae62a94a0a25d58e6d21e7a14Ted Kremenek OS.flush(); 20216d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump} 202242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 202342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek/// dump - A simply pretty printer of a CFGBlock that outputs to stderr. 2024e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const { 2025e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner print(llvm::errs(), cfg, LO); 2026e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner} 202742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 202842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek/// print - A simple pretty printer of a CFGBlock that outputs to an ostream. 202942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek/// Generally this will only be called from CFG::print. 2030e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFGBlock::print(llvm::raw_ostream& OS, const CFG* cfg, 2031e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner const LangOptions &LO) const { 2032e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner StmtPrinterHelper Helper(cfg, LO); 203342a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek print_block(OS, cfg, *this, &Helper, true); 2034026473c2175424a039f51ca8949937268721b965Ted Kremenek} 20357dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 2036a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek/// printTerminator - A simple pretty printer of the terminator of a CFGBlock. 2037e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFGBlock::printTerminator(llvm::raw_ostream &OS, 20386d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump const LangOptions &LO) const { 2039e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); 2040a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek TPrinter.Visit(const_cast<Stmt*>(getTerminator())); 2041a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek} 2042a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek 2043390e48b15ad93f85bfd1e33b9992c198fa0db475Ted KremenekStmt* CFGBlock::getTerminatorCondition() { 20446d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2045411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek if (!Terminator) 2046411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek return NULL; 20476d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2048411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek Expr* E = NULL; 20496d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2050411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek switch (Terminator->getStmtClass()) { 2051411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek default: 2052411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 20536d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2054411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::ForStmtClass: 2055411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<ForStmt>(Terminator)->getCond(); 2056411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 20576d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2058411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::WhileStmtClass: 2059411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<WhileStmt>(Terminator)->getCond(); 2060411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 20616d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2062411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::DoStmtClass: 2063411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<DoStmt>(Terminator)->getCond(); 2064411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 20656d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2066411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::IfStmtClass: 2067411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<IfStmt>(Terminator)->getCond(); 2068411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 20696d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2070411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::ChooseExprClass: 2071411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<ChooseExpr>(Terminator)->getCond(); 2072411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 20736d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2074411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::IndirectGotoStmtClass: 2075411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<IndirectGotoStmt>(Terminator)->getTarget(); 2076411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 20776d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2078411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::SwitchStmtClass: 2079411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<SwitchStmt>(Terminator)->getCond(); 2080411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 20816d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2082411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::ConditionalOperatorClass: 2083411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<ConditionalOperator>(Terminator)->getCond(); 2084411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek break; 20856d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2086411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek case Stmt::BinaryOperatorClass: // '&&' and '||' 2087411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek E = cast<BinaryOperator>(Terminator)->getLHS(); 2088390e48b15ad93f85bfd1e33b9992c198fa0db475Ted Kremenek break; 20896d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2090390e48b15ad93f85bfd1e33b9992c198fa0db475Ted Kremenek case Stmt::ObjCForCollectionStmtClass: 20916d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return Terminator; 2092411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek } 20936d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 2094411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek return E ? E->IgnoreParens() : NULL; 2095411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek} 2096411cdee0b490f79428c9eb977f25199eb7d21cd8Ted Kremenek 20979c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenekbool CFGBlock::hasBinaryBranchTerminator() const { 20986d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 20999c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek if (!Terminator) 21009c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek return false; 21016d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21029c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek Expr* E = NULL; 21036d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21049c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek switch (Terminator->getStmtClass()) { 21059c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek default: 21069c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek return false; 21076d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21086d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump case Stmt::ForStmtClass: 21099c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::WhileStmtClass: 21109c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::DoStmtClass: 21119c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::IfStmtClass: 21129c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::ChooseExprClass: 21139c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::ConditionalOperatorClass: 21149c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek case Stmt::BinaryOperatorClass: 21156d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump return true; 21169c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek } 21176d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21189c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek return E ? E->IgnoreParens() : NULL; 21199c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek} 21209c2535a35db35b3a821a0d0c36a01a16f52f1ad0Ted Kremenek 2121a292585207adbf6dcf6347db3526a7ec861d8eacTed Kremenek 21227dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 21237dba8607e59096014b7139ff20ef00870041d518Ted Kremenek// CFG Graphviz Visualization 21247dba8607e59096014b7139ff20ef00870041d518Ted Kremenek//===----------------------------------------------------------------------===// 21257dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 212642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 212742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek#ifndef NDEBUG 21286d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stumpstatic StmtPrinterHelper* GraphHelper; 212942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek#endif 213042a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 2131e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattnervoid CFG::viewCFG(const LangOptions &LO) const { 213242a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek#ifndef NDEBUG 2133e4f2142d00fa5fdb580c4e2413da91882d955381Chris Lattner StmtPrinterHelper H(this, LO); 213442a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek GraphHelper = &H; 213542a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek llvm::ViewGraph(this,"CFG"); 213642a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek GraphHelper = NULL; 213742a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek#endif 213842a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek} 213942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek 21407dba8607e59096014b7139ff20ef00870041d518Ted Kremeneknamespace llvm { 21417dba8607e59096014b7139ff20ef00870041d518Ted Kremenektemplate<> 21427dba8607e59096014b7139ff20ef00870041d518Ted Kremenekstruct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { 214302995ce680d1bcf9f17bcfdf759bd74b08aa3948Owen Anderson static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph, 214402995ce680d1bcf9f17bcfdf759bd74b08aa3948Owen Anderson bool ShortNames) { 21457dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 2146bd250b44d60622e7c0b60c6def6f6fe7e347addfHartmut Kaiser#ifndef NDEBUG 2147a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek std::string OutSStr; 2148a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek llvm::raw_string_ostream Out(OutSStr); 214942a509f6a4f71bb805cc4abbb26722a34dffdddeTed Kremenek print_block(Out,Graph, *Node, GraphHelper, false); 2150a95d3750441ac8ad03e36af8e6e74039c9a3109dTed Kremenek std::string& OutStr = Out.str(); 21517dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 21527dba8607e59096014b7139ff20ef00870041d518Ted Kremenek if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 21537dba8607e59096014b7139ff20ef00870041d518Ted Kremenek 21547dba8607e59096014b7139ff20ef00870041d518Ted Kremenek // Process string output to make it nicer... 21557dba8607e59096014b7139ff20ef00870041d518Ted Kremenek for (unsigned i = 0; i != OutStr.length(); ++i) 21567dba8607e59096014b7139ff20ef00870041d518Ted Kremenek if (OutStr[i] == '\n') { // Left justify 21577dba8607e59096014b7139ff20ef00870041d518Ted Kremenek OutStr[i] = '\\'; 21587dba8607e59096014b7139ff20ef00870041d518Ted Kremenek OutStr.insert(OutStr.begin()+i+1, 'l'); 21597dba8607e59096014b7139ff20ef00870041d518Ted Kremenek } 21606d9828c82c9321f042ab416fd2ffaa3034347d45Mike Stump 21617dba8607e59096014b7139ff20ef00870041d518Ted Kremenek return OutStr; 2162bd250b44d60622e7c0b60c6def6f6fe7e347addfHartmut Kaiser#else 2163bd250b44d60622e7c0b60c6def6f6fe7e347addfHartmut Kaiser return ""; 2164bd250b44d60622e7c0b60c6def6f6fe7e347addfHartmut Kaiser#endif 21657dba8607e59096014b7139ff20ef00870041d518Ted Kremenek } 21667dba8607e59096014b7139ff20ef00870041d518Ted Kremenek}; 21677dba8607e59096014b7139ff20ef00870041d518Ted Kremenek} // end namespace llvm 2168