CFG.cpp revision 58b87feeaedce7ef09c2931a39d82e5aea189f41
1b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru//===--- CFG.cpp - Classes for representing and building CFGs----*- C++ -*-===// 2b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// 38393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius// The LLVM Compiler Infrastructure 4b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// 5b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// This file is distributed under the University of Illinois Open Source 6b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// License. See LICENSE.TXT for details. 7b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// 8b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru//===----------------------------------------------------------------------===// 9b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// 10b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// This file defines the CFG and CFGBuilder classes for representing and 11b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru// building Control-Flow Graphs (CFGs) from ASTs. 1254dcd9b6a06071f647dac967e9e267abb9410720Craig Cornelius// 1327f654740f2a26ad62a5c155af9199af9e69b889claireho//===----------------------------------------------------------------------===// 14b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 15b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "clang/Analysis/Support/SaveAndRestore.h" 16b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "clang/Analysis/CFG.h" 17b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "clang/AST/StmtVisitor.h" 18b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "clang/AST/PrettyPrinter.h" 19b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "llvm/Support/GraphWriter.h" 20b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "llvm/Support/Allocator.h" 21b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "llvm/Support/Format.h" 22b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "llvm/ADT/DenseMap.h" 23b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "llvm/ADT/SmallPtrSet.h" 24b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru#include "llvm/ADT/OwningPtr.h" 25b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 2650294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehousing namespace clang; 27b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 288393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Corneliusnamespace { 29b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 30b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querustatic SourceLocation GetEndLoc(Decl* D) { 31b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (VarDecl* VD = dyn_cast<VarDecl>(D)) 32b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (Expr* Ex = VD->getInit()) 33b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return Ex->getSourceRange().getEnd(); 34b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 35b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return D->getLocation(); 36b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 37b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 38b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruclass AddStmtChoice { 39b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querupublic: 40b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru enum Kind { NotAlwaysAdd = 0, AlwaysAdd, AlwaysAddAsLValue }; 41b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querupublic: 42b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddStmtChoice(Kind kind) : k(kind) {} 43b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru bool alwaysAdd() const { return k != NotAlwaysAdd; } 44b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru bool asLValue() const { return k == AlwaysAddAsLValue; } 45b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruprivate: 46b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Kind k; 47b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru}; 48b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 49b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/// CFGBuilder - This class implements CFG construction from an AST. 50b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/// The builder is stateful: an instance of the builder should be used to only 51b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/// construct a single CFG. 5250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// 5350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// Example usage: 5450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// 5550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// CFGBuilder builder; 5627f654740f2a26ad62a5c155af9199af9e69b889claireho/// CFG* cfg = builder.BuildAST(stmt1); 5750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// 5850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// CFG construction is done via a recursive walk of an AST. We actually parse 5950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// the AST in reverse order so that the successor of a basic block is 6050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// constructed prior to its predecessor. This allows us to nicely capture 6150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// implicit fall-throughs without extra basic blocks. 6250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// 6350294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehoclass CFGBuilder { 6450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho ASTContext *Context; 6550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho llvm::OwningPtr<CFG> cfg; 66b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 67b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock* Block; 6850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock* Succ; 6950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock* ContinueTargetBlock; 7050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock* BreakTargetBlock; 7150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock* SwitchTerminatedBlock; 7250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock* DefaultCaseBlock; 7350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 7450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // LabelMap records the mapping from Label expressions to their blocks. 7550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho typedef llvm::DenseMap<LabelStmt*,CFGBlock*> LabelMapTy; 7650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho LabelMapTy LabelMap; 7750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 78b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // A list of blocks that end with a "goto" that must be backpatched to their 79b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // resolved targets upon completion of CFG construction. 80b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru typedef std::vector<CFGBlock*> BackpatchBlocksTy; 81b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru BackpatchBlocksTy BackpatchBlocks; 82b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 83b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // A list of labels whose address has been taken (for indirect gotos). 84b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru typedef llvm::SmallPtrSet<LabelStmt*,5> LabelSetTy; 85b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru LabelSetTy AddressTakenLabels; 86b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 87b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querupublic: 88b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru explicit CFGBuilder() : cfg(new CFG()), // crew a new CFG 89b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block(NULL), Succ(NULL), 90b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ContinueTargetBlock(NULL), BreakTargetBlock(NULL), 91b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL) {} 92b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 93b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // buildCFG - Used by external clients to construct the CFG. 94b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFG* buildCFG(Stmt *Statement, ASTContext *C); 95b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 96b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queruprivate: 97b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Visitors to walk an AST and construct the CFG. 98b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc); 99b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc); 10050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock *VisitBlockExpr(BlockExpr* E, AddStmtChoice asc); 10150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock *VisitBreakStmt(BreakStmt *B); 10250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc); 10350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock *VisitCaseStmt(CaseStmt *C); 10450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc); 105b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitCompoundStmt(CompoundStmt *C); 10650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock *VisitConditionalOperator(ConditionalOperator *C, 10750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AddStmtChoice asc); 10850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock *VisitContinueStmt(ContinueStmt *C); 109b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S) { return NYS(); } 110b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T); 111b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitCXXTryStmt(CXXTryStmt *S) { return NYS(); } 112b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitDeclStmt(DeclStmt *DS); 113b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitDeclSubExpr(Decl* D); 114b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitDefaultStmt(DefaultStmt *D); 115b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitDoStmt(DoStmt *D); 116b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitForStmt(ForStmt *F); 117b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitGotoStmt(GotoStmt* G); 118b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitIfStmt(IfStmt *I); 119b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I); 120b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho CFGBlock *VisitLabelStmt(LabelStmt *L); 121b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S); 12259d709d503bab6e2b61931737e662dd293b40578ccornelius CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S); 123b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S); 124b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S); 125b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S); 126b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitReturnStmt(ReturnStmt* R); 127b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, AddStmtChoice asc); 128b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc); 129b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitSwitchStmt(SwitchStmt *S); 130b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitWhileStmt(WhileStmt *W); 131b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 132b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd); 133b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc); 13450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock *VisitChildren(Stmt* S); 13550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 13650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // NYS == Not Yet Supported 13750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock* NYS() { 13850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho badCFG = true; 13950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return Block; 14050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 14150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 14250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void autoCreateBlock() { if (!Block) Block = createBlock(); } 14350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock *createBlock(bool add_successor = true); 14450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho bool FinishBlock(CFGBlock* B); 14550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock *addStmt(Stmt *S, AddStmtChoice asc = AddStmtChoice::AlwaysAdd) { 14650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return Visit(S, asc); 14750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 148b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 149b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru void AppendStmt(CFGBlock *B, Stmt *S, 150b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddStmtChoice asc = AddStmtChoice::AlwaysAdd) { 15150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho B->appendStmt(S, cfg->getBumpVectorContext(), asc.asLValue()); 15250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 15350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 15450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void AddSuccessor(CFGBlock *B, CFGBlock *S) { 15550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho B->addSuccessor(S, cfg->getBumpVectorContext()); 15650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 15750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 15850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho /// TryResult - a class representing a variant over the values 15950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho /// 'true', 'false', or 'unknown'. This is returned by TryEvaluateBool, 16050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho /// and is used by the CFGBuilder to decide if a branch condition 161b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru /// can be decided up front during CFG construction. 162b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru class TryResult { 16350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho int X; 16450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho public: 16550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho TryResult(bool b) : X(b ? 1 : 0) {} 16650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho TryResult() : X(-1) {} 16750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 16850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho bool isTrue() const { return X == 1; } 16950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho bool isFalse() const { return X == 0; } 17050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho bool isKnown() const { return X >= 0; } 17150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho void negate() { 17250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho assert(isKnown()); 17350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho X ^= 0x1; 174b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 175b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru }; 176b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 17750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho /// TryEvaluateBool - Try and evaluate the Stmt and return 0 or 1 17850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho /// if we can evaluate to a known value, otherwise return -1. 17950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho TryResult TryEvaluateBool(Expr *S) { 18050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho Expr::EvalResult Result; 181b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!S->isTypeDependent() && !S->isValueDependent() && 182b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru S->Evaluate(Result, *Context) && Result.Val.isInt()) 18350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return Result.Val.getInt().getBoolValue(); 18450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 18550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return TryResult(); 18650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 18750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 18850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho bool badCFG; 18950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho}; 19050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 19150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho// FIXME: Add support for dependent-sized array types in C++? 19250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho// Does it even make sense to build a CFG for an uninstantiated template? 19350294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehostatic VariableArrayType* FindVA(Type* t) { 19450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho while (ArrayType* vt = dyn_cast<ArrayType>(t)) { 19550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (VariableArrayType* vat = dyn_cast<VariableArrayType>(vt)) 196b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (vat->getSizeExpr()) 197b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return vat; 198b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 19950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho t = vt->getElementType().getTypePtr(); 20050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 20150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 20250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return 0; 20350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho} 20450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 20550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an 20650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// arbitrary statement. Examples include a single expression or a function 20750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// body (compound statement). The ownership of the returned CFG is 20850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// transferred to the caller. If CFG construction fails, this method returns 20950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// NULL. 21050294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehoCFG* CFGBuilder::buildCFG(Stmt* Statement, ASTContext* C) { 21150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho Context = C; 21250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho assert(cfg.get()); 21350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (!Statement) 21450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return NULL; 21550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 21650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho badCFG = false; 21750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 21850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // Create an empty block that will serve as the exit block for the CFG. Since 21950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // this is the first block added to the CFG, it will be implicitly registered 22050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // as the exit block. 22150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho Succ = createBlock(); 222b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru assert(Succ == &cfg->getExit()); 22350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho Block = NULL; // the EXIT block is empty. Create all other blocks lazily. 22450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 22550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // Visit the statements and create the CFG. 22650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock* B = addStmt(Statement); 22750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (!B) 22850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho B = Succ; 22950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 23050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (B) { 23150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // Finalize the last constructed block. This usually involves reversing the 23250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // order of the statements in the block. 23350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (Block) FinishBlock(B); 23450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 23550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // Backpatch the gotos whose label -> block mappings we didn't know when we 23650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // encountered them. 23750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(), 23850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho E = BackpatchBlocks.end(); I != E; ++I ) { 23950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 24050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock* B = *I; 24150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho GotoStmt* G = cast<GotoStmt>(B->getTerminator()); 24250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); 243b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 24450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // If there is no target for the goto, then we are looking at an 24550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // incomplete AST. Handle this by not registering a successor. 246b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (LI == LabelMap.end()) continue; 24750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 24850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AddSuccessor(B, LI->second); 24950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 25050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 251b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Add successors to the Indirect Goto Dispatch block (if we have one). 25250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (CFGBlock* B = cfg->getIndirectGotoBlock()) 253b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho for (LabelSetTy::iterator I = AddressTakenLabels.begin(), 254b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho E = AddressTakenLabels.end(); I != E; ++I ) { 255b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho 256b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Lookup the target block. 257b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru LabelMapTy::iterator LI = LabelMap.find(*I); 258b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 259b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // If there is no target block that contains label, then we are looking 260b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // at an incomplete AST. Handle this by not registering a successor. 261b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (LI == LabelMap.end()) continue; 262b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 263b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddSuccessor(B, LI->second); 264b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 265b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 266b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Succ = B; 267b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 268b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 269b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Create an empty entry block that has no predecessors. 270b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru cfg->setEntry(createBlock()); 271b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 272b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return badCFG ? NULL : cfg.take(); 273b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 274b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 275b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho/// createBlock - Used to lazily create blocks that are connected 276b26ce3a7367e4ed2ee7ddddcdc3f3d3377a455c2claireho/// to the current (global) succcessor. 27750294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehoCFGBlock* CFGBuilder::createBlock(bool add_successor) { 27850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock* B = cfg->createBlock(); 27950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (add_successor && Succ) 28050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AddSuccessor(B, Succ); 28150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return B; 28250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho} 28350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 28450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// FinishBlock - "Finalize" the block by checking if we have a bad CFG. 285b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Querubool CFGBuilder::FinishBlock(CFGBlock* B) { 286b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (badCFG) 28750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return false; 28850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 289b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru assert(B); 290b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return true; 291b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 29250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 29350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// Visit - Walk the subtree of a statement and add extra 29450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// blocks for ternary operators, &&, and ||. We also process "," and 29550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// DeclStmts (which may contain nested control-flow). 296b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruCFGBlock* CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) { 29750294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehotryAgain: 298b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru switch (S->getStmtClass()) { 299b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru default: 300b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitStmt(S, asc); 301b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 302b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::AddrLabelExprClass: 303b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc); 304b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 305b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::BinaryOperatorClass: 306b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitBinaryOperator(cast<BinaryOperator>(S), asc); 307b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 308b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::BlockExprClass: 309b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitBlockExpr(cast<BlockExpr>(S), asc); 310b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 311b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::BreakStmtClass: 312b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitBreakStmt(cast<BreakStmt>(S)); 313b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 31427f654740f2a26ad62a5c155af9199af9e69b889claireho case Stmt::CallExprClass: 315b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitCallExpr(cast<CallExpr>(S), asc); 316b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 317b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::CaseStmtClass: 318b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitCaseStmt(cast<CaseStmt>(S)); 319b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 320b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::ChooseExprClass: 321b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitChooseExpr(cast<ChooseExpr>(S), asc); 322b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 323b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::CompoundStmtClass: 324b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitCompoundStmt(cast<CompoundStmt>(S)); 325b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 326b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::ConditionalOperatorClass: 327b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitConditionalOperator(cast<ConditionalOperator>(S), asc); 328b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 329b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::ContinueStmtClass: 330b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitContinueStmt(cast<ContinueStmt>(S)); 331b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 332b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::DeclStmtClass: 333b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitDeclStmt(cast<DeclStmt>(S)); 334b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 335b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::DefaultStmtClass: 336b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitDefaultStmt(cast<DefaultStmt>(S)); 337b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 338b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::DoStmtClass: 339b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitDoStmt(cast<DoStmt>(S)); 340b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 341b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::ForStmtClass: 342b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitForStmt(cast<ForStmt>(S)); 343b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 344b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::GotoStmtClass: 345b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitGotoStmt(cast<GotoStmt>(S)); 346b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 347b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::IfStmtClass: 348b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitIfStmt(cast<IfStmt>(S)); 349b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 350b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::IndirectGotoStmtClass: 351b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S)); 352b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 353b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::LabelStmtClass: 354b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitLabelStmt(cast<LabelStmt>(S)); 355b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 356b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::ObjCAtCatchStmtClass: 357b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S)); 358b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 359b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::CXXThrowExprClass: 360b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitCXXThrowExpr(cast<CXXThrowExpr>(S)); 361b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 362b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::ObjCAtSynchronizedStmtClass: 363b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S)); 364b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 365b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::ObjCAtThrowStmtClass: 366b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S)); 367b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 368b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::ObjCAtTryStmtClass: 369b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S)); 370b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 371b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::ObjCForCollectionStmtClass: 372b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S)); 373b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 37450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho case Stmt::ParenExprClass: 375b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru S = cast<ParenExpr>(S)->getSubExpr(); 376b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru goto tryAgain; 377b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 378b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::NullStmtClass: 379b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return Block; 380b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 381b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::ReturnStmtClass: 382b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitReturnStmt(cast<ReturnStmt>(S)); 383b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 384b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::SizeOfAlignOfExprClass: 385b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitSizeOfAlignOfExpr(cast<SizeOfAlignOfExpr>(S), asc); 386b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 387b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::StmtExprClass: 388b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitStmtExpr(cast<StmtExpr>(S), asc); 389b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 390b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::SwitchStmtClass: 391b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitSwitchStmt(cast<SwitchStmt>(S)); 392b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 393b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::WhileStmtClass: 39450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return VisitWhileStmt(cast<WhileStmt>(S)); 395b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 396b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 397b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 398b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruCFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) { 399b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (asc.alwaysAdd()) { 400b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru autoCreateBlock(); 401b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AppendStmt(Block, S, asc); 402b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 4038393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius 404b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitChildren(S); 405b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 406b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 40750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho/// VisitChildren - Visit the children of a Stmt. 408b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruCFGBlock *CFGBuilder::VisitChildren(Stmt* Terminator) { 409b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock *B = Block; 410b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (Stmt::child_iterator I = Terminator->child_begin(), 411b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru E = Terminator->child_end(); I != E; ++I) { 412b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (*I) B = Visit(*I); 413b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 414b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return B; 415b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 416b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 417b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruCFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, 418b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddStmtChoice asc) { 419b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddressTakenLabels.insert(A->getLabel()); 420b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 421b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (asc.alwaysAdd()) { 422b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru autoCreateBlock(); 423b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AppendStmt(Block, A, asc); 424b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 425b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 426b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return Block; 427b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 428b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 429b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruCFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, 430b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddStmtChoice asc) { 431b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (B->isLogicalOp()) { // && or || 432b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 433b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AppendStmt(ConfluenceBlock, B, asc); 434b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 435b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!FinishBlock(ConfluenceBlock)) 436b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 437b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 438b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // create the block evaluating the LHS 439b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock* LHSBlock = createBlock(false); 440b0ac937921a2c196d8b9da665135bf6ba01a1ccfJean-Baptiste Queru LHSBlock->setTerminator(B); 441b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 442b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // create the block evaluating the RHS 443b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Succ = ConfluenceBlock; 444b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = NULL; 445b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock* RHSBlock = addStmt(B->getRHS()); 446b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!FinishBlock(RHSBlock)) 447b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 44850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 44950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // See if this is a known constant. 45050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho TryResult KnownVal = TryEvaluateBool(B->getLHS()); 45150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (KnownVal.isKnown() && (B->getOpcode() == BinaryOperator::LOr)) 45250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho KnownVal.negate(); 45350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 45450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // Now link the LHSBlock with RHSBlock. 45550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (B->getOpcode() == BinaryOperator::LOr) { 45650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AddSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 45750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AddSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 45850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } else { 45950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho assert (B->getOpcode() == BinaryOperator::LAnd); 46050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AddSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 46150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AddSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 46250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 46350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 46450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // Generate the blocks for evaluating the LHS. 46550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho Block = LHSBlock; 46650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return addStmt(B->getLHS()); 46759d709d503bab6e2b61931737e662dd293b40578ccornelius } 46859d709d503bab6e2b61931737e662dd293b40578ccornelius else if (B->getOpcode() == BinaryOperator::Comma) { // , 46959d709d503bab6e2b61931737e662dd293b40578ccornelius autoCreateBlock(); 47059d709d503bab6e2b61931737e662dd293b40578ccornelius AppendStmt(Block, B, asc); 47159d709d503bab6e2b61931737e662dd293b40578ccornelius addStmt(B->getRHS()); 472b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return addStmt(B->getLHS()); 473b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 474b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 475b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitStmt(B, asc); 476b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 477b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 478b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruCFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) { 479b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (asc.alwaysAdd()) { 480b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru autoCreateBlock(); 48150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AppendStmt(Block, E, asc); 48250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 48350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return Block; 484b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 48550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 48650294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehoCFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { 48750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // "break" is a control-flow statement. Thus we stop processing the current 48850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // block. 48950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (Block && !FinishBlock(Block)) 49050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return 0; 49150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 49250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // Now create a new block that ends with the break statement. 49350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho Block = createBlock(false); 49450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho Block->setTerminator(B); 49550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 49659d709d503bab6e2b61931737e662dd293b40578ccornelius // If there is no target for the break, then we are looking at an incomplete 49750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // AST. This means that the CFG cannot be constructed. 49850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (BreakTargetBlock) 49950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AddSuccessor(Block, BreakTargetBlock); 50050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho else 50150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho badCFG = true; 50250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 50350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 50450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return Block; 50550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho} 50650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 50750294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehoCFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { 50850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // If this is a call to a no-return function, this stops the block here. 50950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho bool NoReturn = false; 51050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (C->getCallee()->getType().getNoReturnAttr()) { 51150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho NoReturn = true; 51250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 51350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 51450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (FunctionDecl *FD = C->getDirectCallee()) 51550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (FD->hasAttr<NoReturnAttr>()) 51650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho NoReturn = true; 51750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 51850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (!NoReturn) 51950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return VisitStmt(C, asc); 52050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 521b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (Block && !FinishBlock(Block)) 52250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return 0; 52350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 52450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // Create new block with no successor for the remaining pieces. 52550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho Block = createBlock(false); 52650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AppendStmt(Block, C, asc); 52750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 52850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // Wire this to the exit block directly. 52950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AddSuccessor(Block, &cfg->getExit()); 53050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 53150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return VisitChildren(C); 53250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho} 53350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 53450294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehoCFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C, 53550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AddStmtChoice asc) { 536b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 537b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AppendStmt(ConfluenceBlock, C, asc); 53850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (!FinishBlock(ConfluenceBlock)) 53950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return 0; 54050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 541b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Succ = ConfluenceBlock; 54250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho Block = NULL; 54350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock* LHSBlock = addStmt(C->getLHS()); 54450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (!FinishBlock(LHSBlock)) 545b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 546b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 547b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Succ = ConfluenceBlock; 54850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho Block = NULL; 54950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock* RHSBlock = addStmt(C->getRHS()); 550b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!FinishBlock(RHSBlock)) 551b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 552b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 553b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = createBlock(false); 554b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // See if this is a known constant. 555b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const TryResult& KnownVal = TryEvaluateBool(C->getCond()); 556b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); 557b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); 558b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block->setTerminator(C); 559b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return addStmt(C->getCond()); 560b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 561b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 562b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 563b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruCFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) { 564b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock* LastBlock = Block; 56550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 56650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); 56750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho I != E; ++I ) { 568b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru LastBlock = addStmt(*I); 569b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 57050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (badCFG) 57150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return NULL; 57250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 573b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return LastBlock; 57450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho} 57550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 576b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruCFGBlock *CFGBuilder::VisitConditionalOperator(ConditionalOperator *C, 577b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddStmtChoice asc) { 578b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Create the confluence block that will "merge" the results of the ternary 57950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // expression. 5808393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 58150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AppendStmt(ConfluenceBlock, C, asc); 582b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!FinishBlock(ConfluenceBlock)) 583b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 58450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 58550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // Create a block for the LHS expression if there is an LHS expression. A 586b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // GCC extension allows LHS to be NULL, causing the condition to be the 587b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // value that is returned instead. 588b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // e.g: x ?: y is shorthand for: x ? x : y; 589b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Succ = ConfluenceBlock; 590b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = NULL; 591b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock* LHSBlock = NULL; 592b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (C->getLHS()) { 59350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho LHSBlock = addStmt(C->getLHS()); 594b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!FinishBlock(LHSBlock)) 595b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 596b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = NULL; 597b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 598b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 599b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Create the block for the RHS expression. 600b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Succ = ConfluenceBlock; 601b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock* RHSBlock = addStmt(C->getRHS()); 602b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!FinishBlock(RHSBlock)) 603b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 604b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 605b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Create the block that will contain the condition. 606b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = createBlock(false); 607b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 608b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // See if this is a known constant. 609b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const TryResult& KnownVal = TryEvaluateBool(C->getCond()); 610b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (LHSBlock) { 611b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); 61227f654740f2a26ad62a5c155af9199af9e69b889claireho } else { 61327f654740f2a26ad62a5c155af9199af9e69b889claireho if (KnownVal.isFalse()) { 614b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // If we know the condition is false, add NULL as the successor for 615b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // the block containing the condition. In this case, the confluence 616b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // block will have just one predecessor. 61750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AddSuccessor(Block, 0); 618b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru assert(ConfluenceBlock->pred_size() == 1); 619b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else { 62050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // If we have no LHS expression, add the ConfluenceBlock as a direct 621b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // successor for the block containing the condition. Moreover, we need to 622b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // reverse the order of the predecessors in the ConfluenceBlock because 623b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // the RHSBlock will have been added to the succcessors already, and we 62450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // want the first predecessor to the the block containing the expression 62550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // for the case when the ternary expression evaluates to true. 62627f654740f2a26ad62a5c155af9199af9e69b889claireho AddSuccessor(Block, ConfluenceBlock); 62727f654740f2a26ad62a5c155af9199af9e69b889claireho assert(ConfluenceBlock->pred_size() == 2); 62827f654740f2a26ad62a5c155af9199af9e69b889claireho std::reverse(ConfluenceBlock->pred_begin(), 62950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho ConfluenceBlock->pred_end()); 63050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 63150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 63250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 63350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AddSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); 63450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho Block->setTerminator(C); 63550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return addStmt(C->getCond()); 63650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho} 63750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 63850294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehoCFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) { 63950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho autoCreateBlock(); 64050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 64150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (DS->isSingleDecl()) { 64250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AppendStmt(Block, DS); 64350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return VisitDeclSubExpr(DS->getSingleDecl()); 644b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 64550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 64650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock *B = 0; 64750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 64850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy. 64950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho typedef llvm::SmallVector<Decl*,10> BufTy; 650b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru BufTy Buf(DS->decl_begin(), DS->decl_end()); 651b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 652b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru for (BufTy::reverse_iterator I = Buf.rbegin(), E = Buf.rend(); I != E; ++I) { 653b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Get the alignment of the new DeclStmt, padding out to >=8 bytes. 654b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8 655b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ? 8 : llvm::AlignOf<DeclStmt>::Alignment; 656b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 657b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Allocate the DeclStmt using the BumpPtrAllocator. It will get 658b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // automatically freed with the CFG. 659b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru DeclGroupRef DG(*I); 660b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Decl *D = *I; 66159d709d503bab6e2b61931737e662dd293b40578ccornelius void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A); 662b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); 663b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 664b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Append the fake DeclStmt to block. 665b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AppendStmt(Block, DSNew); 666b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru B = VisitDeclSubExpr(D); 667b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 668b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 669b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return B; 670b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 671b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 672b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/// VisitDeclSubExpr - Utility method to add block-level expressions for 673b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru/// initializers in Decls. 674b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruCFGBlock *CFGBuilder::VisitDeclSubExpr(Decl* D) { 675b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru assert(Block); 676b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 677b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru VarDecl *VD = dyn_cast<VarDecl>(D); 678b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 679b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!VD) 680b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return Block; 681b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 682b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Expr *Init = VD->getInit(); 683b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 684b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (Init) { 685b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Optimization: Don't create separate block-level statements for literals. 686b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru switch (Init->getStmtClass()) { 687b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::IntegerLiteralClass: 688b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru case Stmt::CharacterLiteralClass: 6898393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius case Stmt::StringLiteralClass: 6908393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius break; 6918393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius default: 6928393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius Block = addStmt(Init, 69359d709d503bab6e2b61931737e662dd293b40578ccornelius VD->getType()->isReferenceType() 69459d709d503bab6e2b61931737e662dd293b40578ccornelius ? AddStmtChoice::AlwaysAddAsLValue 69559d709d503bab6e2b61931737e662dd293b40578ccornelius : AddStmtChoice::AlwaysAdd); 69659d709d503bab6e2b61931737e662dd293b40578ccornelius } 6978393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius } 6988393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius 69959d709d503bab6e2b61931737e662dd293b40578ccornelius // If the type of VD is a VLA, then we must process its size expressions. 70059d709d503bab6e2b61931737e662dd293b40578ccornelius for (VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); VA != 0; 7018393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius VA = FindVA(VA->getElementType().getTypePtr())) 7028393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius Block = addStmt(VA->getSizeExpr()); 703b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 704b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return Block; 705b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 706b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 707b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruCFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { 708b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // We may see an if statement in the middle of a basic block, or it may be the 709b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // first statement we are processing. In either case, we create a new basic 710b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // block. First, we create the blocks for the then...else statements, and 711b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // then we create the block containing the if statement. If we were in the 712b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // middle of a block, we stop processing that block. That block is then the 713b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // implicit successor for the "then" and "else" clauses. 714b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 715b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // The block we were proccessing is now finished. Make it the successor 716b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // block. 71750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (Block) { 71850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho Succ = Block; 71950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (!FinishBlock(Block)) 72050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return 0; 72150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 72250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 72350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // Process the false branch. 72450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock* ElseBlock = Succ; 72550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 72650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (Stmt* Else = I->getElse()) { 727b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SaveAndRestore<CFGBlock*> sv(Succ); 72850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 72950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // NULL out Block so that the recursive call to Visit will 73050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // create a new basic block. 731b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = NULL; 73250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho ElseBlock = addStmt(Else); 73350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 73450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (!ElseBlock) // Can occur when the Else body has all NullStmts. 735b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ElseBlock = sv.get(); 73650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho else if (Block) { 73750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (!FinishBlock(ElseBlock)) 738b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 739b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 74050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 741b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 74250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // Process the true branch. 743b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock* ThenBlock; 744b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru { 745b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Stmt* Then = I->getThen(); 74650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho assert (Then); 747b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SaveAndRestore<CFGBlock*> sv(Succ); 748b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = NULL; 749b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ThenBlock = addStmt(Then); 750b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 751b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!ThenBlock) { 752b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // We can reach here if the "then" body has all NullStmts. 753b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Create an empty block so we can distinguish between true and false 754b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // branches in path-sensitive analyses. 75550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho ThenBlock = createBlock(false); 75650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AddSuccessor(ThenBlock, sv.get()); 75750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } else if (Block) { 75850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (!FinishBlock(ThenBlock)) 759b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 760b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 761b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 762b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 763b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Now create a new block containing the if statement. 764b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = createBlock(false); 765b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 76650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // Set the terminator of the new block to the If statement. 76750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho Block->setTerminator(I); 768b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 769b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // See if this is a known constant. 770b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru const TryResult &KnownVal = TryEvaluateBool(I->getCond()); 771b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 772b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Now add the successors. 773b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddSuccessor(Block, KnownVal.isFalse() ? NULL : ThenBlock); 774b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddSuccessor(Block, KnownVal.isTrue()? NULL : ElseBlock); 775b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 776b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Add the condition as the last statement in the new block. This may create 777b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // new blocks as the condition may contain control-flow. Any newly created 778b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // blocks will be pointed to be "Block". 779b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = addStmt(I->getCond()); 780b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 781b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Finally, if the IfStmt contains a condition variable, add both the IfStmt 782b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // and the condition variable initialization to the CFG. 783b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (VarDecl *VD = I->getConditionVariable()) { 784c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru if (Expr *Init = VD->getInit()) { 785c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru autoCreateBlock(); 786c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru AppendStmt(Block, I, AddStmtChoice::AlwaysAdd); 787c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru addStmt(Init); 788c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru } 789c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru } 790b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 791b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return Block; 792b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 793b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 794b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 79550294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehoCFGBlock* CFGBuilder::VisitReturnStmt(ReturnStmt* R) { 79650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // If we were in the middle of a block we stop processing that block. 797b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // 798c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru // NOTE: If a "return" appears in the middle of a block, this means that the 799c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru // code afterwards is DEAD (unreachable). We still keep a basic block 800c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru // for that code; a simple "mark-and-sweep" from the entry block will be 801c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru // able to report such dead blocks. 802c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru if (Block) 803c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru FinishBlock(Block); 804b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 805b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Create the new block. 806b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = createBlock(false); 807b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 80850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // The Exit block is the only successor. 809b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddSuccessor(Block, &cfg->getExit()); 81050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 811b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Add the return statement to the block. This may create new blocks if R 812b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // contains control-flow (short-circuit operations). 813b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return VisitStmt(R, AddStmtChoice::AlwaysAdd); 814b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 81550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 81650294ead5e5d23f5bbfed76e00e6b510bd41eee1clairehoCFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt* L) { 81750294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // Get the block of the labeled statement. Add it to our map. 818b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru addStmt(L->getSubStmt()); 819b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock* LabelBlock = Block; 820c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru 821c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru if (!LabelBlock) // This can happen when the body is empty, i.e. 822c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru LabelBlock = createBlock(); // scopes that only contains NullStmts. 823c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru 824c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru assert(LabelMap.find(L) == LabelMap.end() && "label already in map"); 825c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru LabelMap[ L ] = LabelBlock; 82650294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 827b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Labels partition blocks, so this is the end of the basic block we were 828b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // processing (L is the block's label). Because this is label (and we have 829b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // already processed the substatement) there is no extra control-flow to worry 830b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // about. 831c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru LabelBlock->setLabel(L); 832c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru if (!FinishBlock(LabelBlock)) 833c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru return 0; 834c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru 835c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru // We set Block to NULL to allow lazy creation of a new block (if necessary); 836c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru Block = NULL; 837b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 838b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // This block is now the implicit successor of other blocks. 83950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho Succ = LabelBlock; 840b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 84150294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho return LabelBlock; 842c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru} 843c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru 844c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste QueruCFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) { 845c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru // Goto is a control-flow statement. Thus we stop processing the current 846c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru // block and create a new one. 847b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (Block) 848b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru FinishBlock(Block); 849b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 850c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru Block = createBlock(false); 851c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru Block->setTerminator(G); 852c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru 853c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru // If we already know the mapping to the label block add the successor now. 854c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru LabelMapTy::iterator I = LabelMap.find(G->getLabel()); 855c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru 856b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (I == LabelMap.end()) 857b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // We will need to backpatch this block later. 85850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho BackpatchBlocks.push_back(Block); 85950294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho else 860b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddSuccessor(Block, I->second); 861b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 862b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return Block; 863b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 864b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 865b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruCFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { 866c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru CFGBlock* LoopSuccessor = NULL; 867c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru 868c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru // "for" is a control-flow statement. Thus we stop processing the current 869c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru // block. 870c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru if (Block) { 871c69afcec261fc345fda8daf46f0ea6b4351dc777Jean-Baptiste Queru if (!FinishBlock(Block)) 872b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 873b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru LoopSuccessor = Block; 874b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else 875b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru LoopSuccessor = Succ; 876b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 877b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Because of short-circuit evaluation, the condition of the loop can span 878b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 8798393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius // evaluate the condition. 880b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock* ExitConditionBlock = createBlock(false); 8818393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius CFGBlock* EntryConditionBlock = ExitConditionBlock; 882b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 883b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Set the terminator for the "exit" condition block. 884b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ExitConditionBlock->setTerminator(F); 885b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 886b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Now add the actual condition to the condition block. Because the condition 887b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // itself may contain control-flow, new blocks may be created. 888b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (Stmt* C = F->getCond()) { 889b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = ExitConditionBlock; 890b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru EntryConditionBlock = addStmt(C); 891b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru assert(Block == EntryConditionBlock); 892b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 893b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // If this block contains a condition variable, add both the condition 894b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // variable and initializer to the CFG. 895b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (VarDecl *VD = F->getConditionVariable()) { 896b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (Expr *Init = VD->getInit()) { 897b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru autoCreateBlock(); 898b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AppendStmt(Block, F, AddStmtChoice::AlwaysAdd); 899b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru EntryConditionBlock = addStmt(Init); 900b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru assert(Block == EntryConditionBlock); 901b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 90250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho } 90350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 904b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (Block) { 90550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho if (!FinishBlock(EntryConditionBlock)) 906b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 907b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 908b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 909b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 91050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // The condition block is the implicit successor for the loop body as well as 911b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // any code above the loop. 912b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Succ = EntryConditionBlock; 913b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 914b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // See if this is a known constant. 915b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru TryResult KnownVal(true); 916b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 917b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (F->getCond()) 918b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru KnownVal = TryEvaluateBool(F->getCond()); 919b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 920b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Now create the loop body. 921b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru { 92250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho assert (F->getBody()); 92350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 92450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // Save the current values for Block, Succ, and continue and break targets 925b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 926b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru save_continue(ContinueTargetBlock), 927b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru save_break(BreakTargetBlock); 928b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 929b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Create a new block to contain the (bottom) of the loop body. 930b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = NULL; 931b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 932b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (Stmt* I = F->getInc()) { 933b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Generate increment code in its own basic block. This is the target of 934b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // continue statements. 935b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Succ = addStmt(I); 936b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else { 937b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // No increment code. Create a special, empty, block that is used as the 938b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // target block for "looping back" to the start of the loop. 939b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru assert(Succ == EntryConditionBlock); 940b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Succ = createBlock(); 941b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 942b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 943b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Finish up the increment (or empty) block if it hasn't been already. 9448393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius if (Block) { 945b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru assert(Block == Succ); 9468393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius if (!FinishBlock(Block)) 947b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 948b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = 0; 949b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 950b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 951b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ContinueTargetBlock = Succ; 952b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 953b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // The starting block for the loop increment is the block that should 954b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // represent the 'loop target' for looping back to the start of the loop. 955b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ContinueTargetBlock->setLoopTarget(F); 956b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 957b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // All breaks should go to the code following the loop. 958b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru BreakTargetBlock = LoopSuccessor; 959b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 960b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Now populate the body block, and in the process create new blocks as we 961b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // walk the body of the loop. 96250294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho CFGBlock* BodyBlock = addStmt(F->getBody()); 963b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 964b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!BodyBlock) 965b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru BodyBlock = ContinueTargetBlock; // can happen for "for (...;...;...) ;" 966b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru else if (Block && !FinishBlock(BodyBlock)) 967b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 96850294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho 969b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // This new body block is a successor to our "exit" condition block. 97050294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); 971b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 972b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 973b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Link up the condition block with the code that follows the loop. (the 974b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // false branch). 975b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 976b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 977b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // If the loop contains initialization, create a new block for those 978b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // statements. This block can also contain statements that precede the loop. 979b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (Stmt* I = F->getInit()) { 980b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = createBlock(); 981b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return addStmt(I); 982b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else { 98350294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // There is no loop initialization. We are thus basically a while loop. 98450294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho // NULL out Block to force lazy block construction. 98550294ead5e5d23f5bbfed76e00e6b510bd41eee1claireho Block = NULL; 986b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Succ = EntryConditionBlock; 987b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return EntryConditionBlock; 988b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 989b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru} 990b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 991b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste QueruCFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { 992b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Objective-C fast enumeration 'for' statements: 993b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC 994b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // 995b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // for ( Type newVariable in collection_expression ) { statements } 996b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // 997b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // becomes: 998b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // 999b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // prologue: 1000b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // 1. collection_expression 1001b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // T. jump to loop_entry 1002b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // loop_entry: 1003b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // 1. side-effects of element expression 1004b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // 1. ObjCForCollectionStmt [performs binding to newVariable] 10058393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil] 1006b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // TB: 1007b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // statements 1008b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // T. jump to loop_entry 10098393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius // FB: 1010b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // what comes after 1011b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // 1012b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // and 1013b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // 1014b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Type existingItem; 1015b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // for ( existingItem in expression ) { statements } 1016b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // 1017b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // becomes: 1018b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // 1019b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // the same with newVariable replaced with existingItem; the binding works 1020b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // the same except that for one ObjCForCollectionStmt::getElement() returns 1021b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // a DeclStmt and the other returns a DeclRefExpr. 1022b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // 1023b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1024b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock* LoopSuccessor = 0; 1025b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1026b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (Block) { 1027b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!FinishBlock(Block)) 1028b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 1029b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru LoopSuccessor = Block; 1030b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = 0; 1031b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } else 1032b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru LoopSuccessor = Succ; 1033b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1034b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Build the condition blocks. 1035b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock* ExitConditionBlock = createBlock(false); 1036b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock* EntryConditionBlock = ExitConditionBlock; 1037b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 10388393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius // Set the terminator for the "exit" condition block. 1039b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ExitConditionBlock->setTerminator(S); 1040b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1041b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // The last statement in the block should be the ObjCForCollectionStmt, which 10428393335b955da7340c9f19b1b4b2d6c0c2c04be7Craig Cornelius // performs the actual binding to 'element' and determines if there are any 1043b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // more items in the collection. 1044b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AppendStmt(ExitConditionBlock, S); 1045b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = ExitConditionBlock; 1046b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1047b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Walk the 'element' expression to see if there are any side-effects. We 1048b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // generate new blocks as necesary. We DON'T add the statement by default to 1049b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // the CFG unless it contains control-flow. 1050b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru EntryConditionBlock = Visit(S->getElement(), AddStmtChoice::NotAlwaysAdd); 1051b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (Block) { 1052b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!FinishBlock(EntryConditionBlock)) 1053b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 1054b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Block = 0; 1055b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 1056b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1057b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // The condition block is the implicit successor for the loop body as well as 1058b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // any code above the loop. 1059b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru Succ = EntryConditionBlock; 1060b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1061b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Now create the true branch. 1062b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru { 1063b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // Save the current values for Succ, continue and break targets. 1064b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru SaveAndRestore<CFGBlock*> save_Succ(Succ), 1065b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru save_continue(ContinueTargetBlock), save_break(BreakTargetBlock); 1066b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1067b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru BreakTargetBlock = LoopSuccessor; 1068b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru ContinueTargetBlock = EntryConditionBlock; 1069b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1070b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru CFGBlock* BodyBlock = addStmt(S->getBody()); 1071b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1072b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!BodyBlock) 1073b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;" 1074b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru else if (Block) { 1075b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru if (!FinishBlock(BodyBlock)) 1076b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru return 0; 1077b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 1078b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru 1079b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru // This new body block is a successor to our "exit" condition block. 1080b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru AddSuccessor(ExitConditionBlock, BodyBlock); 1081b13da9df870a61b11249bf741347908dbea0edd8Jean-Baptiste Queru } 1082 1083 // Link up the condition block with the code that follows the loop. 1084 // (the false branch). 1085 AddSuccessor(ExitConditionBlock, LoopSuccessor); 1086 1087 // Now create a prologue block to contain the collection expression. 1088 Block = createBlock(); 1089 return addStmt(S->getCollection()); 1090} 1091 1092CFGBlock* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S) { 1093 // FIXME: Add locking 'primitives' to CFG for @synchronized. 1094 1095 // Inline the body. 1096 CFGBlock *SyncBlock = addStmt(S->getSynchBody()); 1097 1098 // The sync body starts its own basic block. This makes it a little easier 1099 // for diagnostic clients. 1100 if (SyncBlock) { 1101 if (!FinishBlock(SyncBlock)) 1102 return 0; 1103 1104 Block = 0; 1105 } 1106 1107 Succ = SyncBlock; 1108 1109 // Inline the sync expression. 1110 return addStmt(S->getSynchExpr()); 1111} 1112 1113CFGBlock* CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt* S) { 1114 // FIXME 1115 return NYS(); 1116} 1117 1118CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { 1119 CFGBlock* LoopSuccessor = NULL; 1120 1121 // "while" is a control-flow statement. Thus we stop processing the current 1122 // block. 1123 if (Block) { 1124 if (!FinishBlock(Block)) 1125 return 0; 1126 LoopSuccessor = Block; 1127 } else 1128 LoopSuccessor = Succ; 1129 1130 // Because of short-circuit evaluation, the condition of the loop can span 1131 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1132 // evaluate the condition. 1133 CFGBlock* ExitConditionBlock = createBlock(false); 1134 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1135 1136 // Set the terminator for the "exit" condition block. 1137 ExitConditionBlock->setTerminator(W); 1138 1139 // Now add the actual condition to the condition block. Because the condition 1140 // itself may contain control-flow, new blocks may be created. Thus we update 1141 // "Succ" after adding the condition. 1142 if (Stmt* C = W->getCond()) { 1143 Block = ExitConditionBlock; 1144 EntryConditionBlock = addStmt(C); 1145 assert(Block == EntryConditionBlock); 1146 1147 // If this block contains a condition variable, add both the condition 1148 // variable and initializer to the CFG. 1149 if (VarDecl *VD = W->getConditionVariable()) { 1150 if (Expr *Init = VD->getInit()) { 1151 autoCreateBlock(); 1152 AppendStmt(Block, W, AddStmtChoice::AlwaysAdd); 1153 EntryConditionBlock = addStmt(Init); 1154 assert(Block == EntryConditionBlock); 1155 } 1156 } 1157 1158 if (Block) { 1159 if (!FinishBlock(EntryConditionBlock)) 1160 return 0; 1161 } 1162 } 1163 1164 // The condition block is the implicit successor for the loop body as well as 1165 // any code above the loop. 1166 Succ = EntryConditionBlock; 1167 1168 // See if this is a known constant. 1169 const TryResult& KnownVal = TryEvaluateBool(W->getCond()); 1170 1171 // Process the loop body. 1172 { 1173 assert(W->getBody()); 1174 1175 // Save the current values for Block, Succ, and continue and break targets 1176 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1177 save_continue(ContinueTargetBlock), 1178 save_break(BreakTargetBlock); 1179 1180 // Create an empty block to represent the transition block for looping back 1181 // to the head of the loop. 1182 Block = 0; 1183 assert(Succ == EntryConditionBlock); 1184 Succ = createBlock(); 1185 Succ->setLoopTarget(W); 1186 ContinueTargetBlock = Succ; 1187 1188 // All breaks should go to the code following the loop. 1189 BreakTargetBlock = LoopSuccessor; 1190 1191 // NULL out Block to force lazy instantiation of blocks for the body. 1192 Block = NULL; 1193 1194 // Create the body. The returned block is the entry to the loop body. 1195 CFGBlock* BodyBlock = addStmt(W->getBody()); 1196 1197 if (!BodyBlock) 1198 BodyBlock = ContinueTargetBlock; // can happen for "while(...) ;" 1199 else if (Block) { 1200 if (!FinishBlock(BodyBlock)) 1201 return 0; 1202 } 1203 1204 // Add the loop body entry as a successor to the condition. 1205 AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); 1206 } 1207 1208 // Link up the condition block with the code that follows the loop. (the 1209 // false branch). 1210 AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 1211 1212 // There can be no more statements in the condition block since we loop back 1213 // to this block. NULL out Block to force lazy creation of another block. 1214 Block = NULL; 1215 1216 // Return the condition block, which is the dominating block for the loop. 1217 Succ = EntryConditionBlock; 1218 return EntryConditionBlock; 1219} 1220 1221 1222CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt* S) { 1223 // FIXME: For now we pretend that @catch and the code it contains does not 1224 // exit. 1225 return Block; 1226} 1227 1228CFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) { 1229 // FIXME: This isn't complete. We basically treat @throw like a return 1230 // statement. 1231 1232 // If we were in the middle of a block we stop processing that block. 1233 if (Block && !FinishBlock(Block)) 1234 return 0; 1235 1236 // Create the new block. 1237 Block = createBlock(false); 1238 1239 // The Exit block is the only successor. 1240 AddSuccessor(Block, &cfg->getExit()); 1241 1242 // Add the statement to the block. This may create new blocks if S contains 1243 // control-flow (short-circuit operations). 1244 return VisitStmt(S, AddStmtChoice::AlwaysAdd); 1245} 1246 1247CFGBlock* CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr* T) { 1248 // If we were in the middle of a block we stop processing that block. 1249 if (Block && !FinishBlock(Block)) 1250 return 0; 1251 1252 // Create the new block. 1253 Block = createBlock(false); 1254 1255 // The Exit block is the only successor. 1256 AddSuccessor(Block, &cfg->getExit()); 1257 1258 // Add the statement to the block. This may create new blocks if S contains 1259 // control-flow (short-circuit operations). 1260 return VisitStmt(T, AddStmtChoice::AlwaysAdd); 1261} 1262 1263CFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { 1264 CFGBlock* LoopSuccessor = NULL; 1265 1266 // "do...while" is a control-flow statement. Thus we stop processing the 1267 // current block. 1268 if (Block) { 1269 if (!FinishBlock(Block)) 1270 return 0; 1271 LoopSuccessor = Block; 1272 } else 1273 LoopSuccessor = Succ; 1274 1275 // Because of short-circuit evaluation, the condition of the loop can span 1276 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1277 // evaluate the condition. 1278 CFGBlock* ExitConditionBlock = createBlock(false); 1279 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1280 1281 // Set the terminator for the "exit" condition block. 1282 ExitConditionBlock->setTerminator(D); 1283 1284 // Now add the actual condition to the condition block. Because the condition 1285 // itself may contain control-flow, new blocks may be created. 1286 if (Stmt* C = D->getCond()) { 1287 Block = ExitConditionBlock; 1288 EntryConditionBlock = addStmt(C); 1289 if (Block) { 1290 if (!FinishBlock(EntryConditionBlock)) 1291 return 0; 1292 } 1293 } 1294 1295 // The condition block is the implicit successor for the loop body. 1296 Succ = EntryConditionBlock; 1297 1298 // See if this is a known constant. 1299 const TryResult &KnownVal = TryEvaluateBool(D->getCond()); 1300 1301 // Process the loop body. 1302 CFGBlock* BodyBlock = NULL; 1303 { 1304 assert (D->getBody()); 1305 1306 // Save the current values for Block, Succ, and continue and break targets 1307 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1308 save_continue(ContinueTargetBlock), 1309 save_break(BreakTargetBlock); 1310 1311 // All continues within this loop should go to the condition block 1312 ContinueTargetBlock = EntryConditionBlock; 1313 1314 // All breaks should go to the code following the loop. 1315 BreakTargetBlock = LoopSuccessor; 1316 1317 // NULL out Block to force lazy instantiation of blocks for the body. 1318 Block = NULL; 1319 1320 // Create the body. The returned block is the entry to the loop body. 1321 BodyBlock = addStmt(D->getBody()); 1322 1323 if (!BodyBlock) 1324 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" 1325 else if (Block) { 1326 if (!FinishBlock(BodyBlock)) 1327 return 0; 1328 } 1329 1330 // Add an intermediate block between the BodyBlock and the 1331 // ExitConditionBlock to represent the "loop back" transition. Create an 1332 // empty block to represent the transition block for looping back to the 1333 // head of the loop. 1334 // FIXME: Can we do this more efficiently without adding another block? 1335 Block = NULL; 1336 Succ = BodyBlock; 1337 CFGBlock *LoopBackBlock = createBlock(); 1338 LoopBackBlock->setLoopTarget(D); 1339 1340 // Add the loop body entry as a successor to the condition. 1341 AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : LoopBackBlock); 1342 } 1343 1344 // Link up the condition block with the code that follows the loop. 1345 // (the false branch). 1346 AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 1347 1348 // There can be no more statements in the body block(s) since we loop back to 1349 // the body. NULL out Block to force lazy creation of another block. 1350 Block = NULL; 1351 1352 // Return the loop body, which is the dominating block for the loop. 1353 Succ = BodyBlock; 1354 return BodyBlock; 1355} 1356 1357CFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) { 1358 // "continue" is a control-flow statement. Thus we stop processing the 1359 // current block. 1360 if (Block && !FinishBlock(Block)) 1361 return 0; 1362 1363 // Now create a new block that ends with the continue statement. 1364 Block = createBlock(false); 1365 Block->setTerminator(C); 1366 1367 // If there is no target for the continue, then we are looking at an 1368 // incomplete AST. This means the CFG cannot be constructed. 1369 if (ContinueTargetBlock) 1370 AddSuccessor(Block, ContinueTargetBlock); 1371 else 1372 badCFG = true; 1373 1374 return Block; 1375} 1376 1377CFGBlock *CFGBuilder::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, 1378 AddStmtChoice asc) { 1379 1380 if (asc.alwaysAdd()) { 1381 autoCreateBlock(); 1382 AppendStmt(Block, E); 1383 } 1384 1385 // VLA types have expressions that must be evaluated. 1386 if (E->isArgumentType()) { 1387 for (VariableArrayType* VA = FindVA(E->getArgumentType().getTypePtr()); 1388 VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) 1389 addStmt(VA->getSizeExpr()); 1390 } 1391 1392 return Block; 1393} 1394 1395/// VisitStmtExpr - Utility method to handle (nested) statement 1396/// expressions (a GCC extension). 1397CFGBlock* CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) { 1398 if (asc.alwaysAdd()) { 1399 autoCreateBlock(); 1400 AppendStmt(Block, SE); 1401 } 1402 return VisitCompoundStmt(SE->getSubStmt()); 1403} 1404 1405CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { 1406 // "switch" is a control-flow statement. Thus we stop processing the current 1407 // block. 1408 CFGBlock* SwitchSuccessor = NULL; 1409 1410 if (Block) { 1411 if (!FinishBlock(Block)) 1412 return 0; 1413 SwitchSuccessor = Block; 1414 } else SwitchSuccessor = Succ; 1415 1416 // Save the current "switch" context. 1417 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), 1418 save_break(BreakTargetBlock), 1419 save_default(DefaultCaseBlock); 1420 1421 // Set the "default" case to be the block after the switch statement. If the 1422 // switch statement contains a "default:", this value will be overwritten with 1423 // the block for that code. 1424 DefaultCaseBlock = SwitchSuccessor; 1425 1426 // Create a new block that will contain the switch statement. 1427 SwitchTerminatedBlock = createBlock(false); 1428 1429 // Now process the switch body. The code after the switch is the implicit 1430 // successor. 1431 Succ = SwitchSuccessor; 1432 BreakTargetBlock = SwitchSuccessor; 1433 1434 // When visiting the body, the case statements should automatically get linked 1435 // up to the switch. We also don't keep a pointer to the body, since all 1436 // control-flow from the switch goes to case/default statements. 1437 assert (Terminator->getBody() && "switch must contain a non-NULL body"); 1438 Block = NULL; 1439 CFGBlock *BodyBlock = addStmt(Terminator->getBody()); 1440 if (Block) { 1441 if (!FinishBlock(BodyBlock)) 1442 return 0; 1443 } 1444 1445 // If we have no "default:" case, the default transition is to the code 1446 // following the switch body. 1447 AddSuccessor(SwitchTerminatedBlock, DefaultCaseBlock); 1448 1449 // Add the terminator and condition in the switch block. 1450 SwitchTerminatedBlock->setTerminator(Terminator); 1451 assert (Terminator->getCond() && "switch condition must be non-NULL"); 1452 Block = SwitchTerminatedBlock; 1453 Block = addStmt(Terminator->getCond()); 1454 1455 // Finally, if the SwitchStmt contains a condition variable, add both the 1456 // SwitchStmt and the condition variable initialization to the CFG. 1457 if (VarDecl *VD = Terminator->getConditionVariable()) { 1458 if (Expr *Init = VD->getInit()) { 1459 autoCreateBlock(); 1460 AppendStmt(Block, Terminator, AddStmtChoice::AlwaysAdd); 1461 addStmt(Init); 1462 } 1463 } 1464 1465 return Block; 1466} 1467 1468CFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) { 1469 // CaseStmts are essentially labels, so they are the first statement in a 1470 // block. 1471 1472 if (CS->getSubStmt()) 1473 addStmt(CS->getSubStmt()); 1474 1475 CFGBlock* CaseBlock = Block; 1476 if (!CaseBlock) 1477 CaseBlock = createBlock(); 1478 1479 // Cases statements partition blocks, so this is the top of the basic block we 1480 // were processing (the "case XXX:" is the label). 1481 CaseBlock->setLabel(CS); 1482 1483 if (!FinishBlock(CaseBlock)) 1484 return 0; 1485 1486 // Add this block to the list of successors for the block with the switch 1487 // statement. 1488 assert(SwitchTerminatedBlock); 1489 AddSuccessor(SwitchTerminatedBlock, CaseBlock); 1490 1491 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1492 Block = NULL; 1493 1494 // This block is now the implicit successor of other blocks. 1495 Succ = CaseBlock; 1496 1497 return CaseBlock; 1498} 1499 1500CFGBlock* CFGBuilder::VisitDefaultStmt(DefaultStmt* Terminator) { 1501 if (Terminator->getSubStmt()) 1502 addStmt(Terminator->getSubStmt()); 1503 1504 DefaultCaseBlock = Block; 1505 1506 if (!DefaultCaseBlock) 1507 DefaultCaseBlock = createBlock(); 1508 1509 // Default statements partition blocks, so this is the top of the basic block 1510 // we were processing (the "default:" is the label). 1511 DefaultCaseBlock->setLabel(Terminator); 1512 1513 if (!FinishBlock(DefaultCaseBlock)) 1514 return 0; 1515 1516 // Unlike case statements, we don't add the default block to the successors 1517 // for the switch statement immediately. This is done when we finish 1518 // processing the switch statement. This allows for the default case 1519 // (including a fall-through to the code after the switch statement) to always 1520 // be the last successor of a switch-terminated block. 1521 1522 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1523 Block = NULL; 1524 1525 // This block is now the implicit successor of other blocks. 1526 Succ = DefaultCaseBlock; 1527 1528 return DefaultCaseBlock; 1529} 1530 1531CFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1532 // Lazily create the indirect-goto dispatch block if there isn't one already. 1533 CFGBlock* IBlock = cfg->getIndirectGotoBlock(); 1534 1535 if (!IBlock) { 1536 IBlock = createBlock(false); 1537 cfg->setIndirectGotoBlock(IBlock); 1538 } 1539 1540 // IndirectGoto is a control-flow statement. Thus we stop processing the 1541 // current block and create a new one. 1542 if (Block && !FinishBlock(Block)) 1543 return 0; 1544 1545 Block = createBlock(false); 1546 Block->setTerminator(I); 1547 AddSuccessor(Block, IBlock); 1548 return addStmt(I->getTarget()); 1549} 1550 1551} // end anonymous namespace 1552 1553/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has 1554/// no successors or predecessors. If this is the first block created in the 1555/// CFG, it is automatically set to be the Entry and Exit of the CFG. 1556CFGBlock* CFG::createBlock() { 1557 bool first_block = begin() == end(); 1558 1559 // Create the block. 1560 CFGBlock *Mem = getAllocator().Allocate<CFGBlock>(); 1561 new (Mem) CFGBlock(NumBlockIDs++, BlkBVC); 1562 Blocks.push_back(Mem, BlkBVC); 1563 1564 // If this is the first block, set it as the Entry and Exit. 1565 if (first_block) 1566 Entry = Exit = &back(); 1567 1568 // Return the block. 1569 return &back(); 1570} 1571 1572/// buildCFG - Constructs a CFG from an AST. Ownership of the returned 1573/// CFG is returned to the caller. 1574CFG* CFG::buildCFG(Stmt* Statement, ASTContext *C) { 1575 CFGBuilder Builder; 1576 return Builder.buildCFG(Statement, C); 1577} 1578 1579//===----------------------------------------------------------------------===// 1580// CFG: Queries for BlkExprs. 1581//===----------------------------------------------------------------------===// 1582 1583namespace { 1584 typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy; 1585} 1586 1587static void FindSubExprAssignments(Stmt *S, 1588 llvm::SmallPtrSet<Expr*,50>& Set) { 1589 if (!S) 1590 return; 1591 1592 for (Stmt::child_iterator I=S->child_begin(), E=S->child_end(); I!=E; ++I) { 1593 Stmt *child = *I; 1594 if (!child) 1595 continue; 1596 1597 if (BinaryOperator* B = dyn_cast<BinaryOperator>(child)) 1598 if (B->isAssignmentOp()) Set.insert(B); 1599 1600 FindSubExprAssignments(child, Set); 1601 } 1602} 1603 1604static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { 1605 BlkExprMapTy* M = new BlkExprMapTy(); 1606 1607 // Look for assignments that are used as subexpressions. These are the only 1608 // assignments that we want to *possibly* register as a block-level 1609 // expression. Basically, if an assignment occurs both in a subexpression and 1610 // at the block-level, it is a block-level expression. 1611 llvm::SmallPtrSet<Expr*,50> SubExprAssignments; 1612 1613 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) 1614 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) 1615 FindSubExprAssignments(*BI, SubExprAssignments); 1616 1617 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { 1618 1619 // Iterate over the statements again on identify the Expr* and Stmt* at the 1620 // block-level that are block-level expressions. 1621 1622 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) 1623 if (Expr* Exp = dyn_cast<Expr>(*BI)) { 1624 1625 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { 1626 // Assignment expressions that are not nested within another 1627 // expression are really "statements" whose value is never used by 1628 // another expression. 1629 if (B->isAssignmentOp() && !SubExprAssignments.count(Exp)) 1630 continue; 1631 } else if (const StmtExpr* Terminator = dyn_cast<StmtExpr>(Exp)) { 1632 // Special handling for statement expressions. The last statement in 1633 // the statement expression is also a block-level expr. 1634 const CompoundStmt* C = Terminator->getSubStmt(); 1635 if (!C->body_empty()) { 1636 unsigned x = M->size(); 1637 (*M)[C->body_back()] = x; 1638 } 1639 } 1640 1641 unsigned x = M->size(); 1642 (*M)[Exp] = x; 1643 } 1644 1645 // Look at terminators. The condition is a block-level expression. 1646 1647 Stmt* S = (*I)->getTerminatorCondition(); 1648 1649 if (S && M->find(S) == M->end()) { 1650 unsigned x = M->size(); 1651 (*M)[S] = x; 1652 } 1653 } 1654 1655 return M; 1656} 1657 1658CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) { 1659 assert(S != NULL); 1660 if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } 1661 1662 BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap); 1663 BlkExprMapTy::iterator I = M->find(S); 1664 1665 if (I == M->end()) return CFG::BlkExprNumTy(); 1666 else return CFG::BlkExprNumTy(I->second); 1667} 1668 1669unsigned CFG::getNumBlkExprs() { 1670 if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) 1671 return M->size(); 1672 else { 1673 // We assume callers interested in the number of BlkExprs will want 1674 // the map constructed if it doesn't already exist. 1675 BlkExprMap = (void*) PopulateBlkExprMap(*this); 1676 return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); 1677 } 1678} 1679 1680//===----------------------------------------------------------------------===// 1681// Cleanup: CFG dstor. 1682//===----------------------------------------------------------------------===// 1683 1684CFG::~CFG() { 1685 delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); 1686} 1687 1688//===----------------------------------------------------------------------===// 1689// CFG pretty printing 1690//===----------------------------------------------------------------------===// 1691 1692namespace { 1693 1694class StmtPrinterHelper : public PrinterHelper { 1695 1696 typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; 1697 StmtMapTy StmtMap; 1698 signed CurrentBlock; 1699 unsigned CurrentStmt; 1700 const LangOptions &LangOpts; 1701public: 1702 1703 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) 1704 : CurrentBlock(0), CurrentStmt(0), LangOpts(LO) { 1705 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { 1706 unsigned j = 1; 1707 for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ; 1708 BI != BEnd; ++BI, ++j ) 1709 StmtMap[*BI] = std::make_pair((*I)->getBlockID(),j); 1710 } 1711 } 1712 1713 virtual ~StmtPrinterHelper() {} 1714 1715 const LangOptions &getLangOpts() const { return LangOpts; } 1716 void setBlockID(signed i) { CurrentBlock = i; } 1717 void setStmtID(unsigned i) { CurrentStmt = i; } 1718 1719 virtual bool handledStmt(Stmt* Terminator, llvm::raw_ostream& OS) { 1720 1721 StmtMapTy::iterator I = StmtMap.find(Terminator); 1722 1723 if (I == StmtMap.end()) 1724 return false; 1725 1726 if (CurrentBlock >= 0 && I->second.first == (unsigned) CurrentBlock 1727 && I->second.second == CurrentStmt) 1728 return false; 1729 1730 OS << "[B" << I->second.first << "." << I->second.second << "]"; 1731 return true; 1732 } 1733}; 1734} // end anonymous namespace 1735 1736 1737namespace { 1738class CFGBlockTerminatorPrint 1739 : public StmtVisitor<CFGBlockTerminatorPrint,void> { 1740 1741 llvm::raw_ostream& OS; 1742 StmtPrinterHelper* Helper; 1743 PrintingPolicy Policy; 1744 1745public: 1746 CFGBlockTerminatorPrint(llvm::raw_ostream& os, StmtPrinterHelper* helper, 1747 const PrintingPolicy &Policy) 1748 : OS(os), Helper(helper), Policy(Policy) {} 1749 1750 void VisitIfStmt(IfStmt* I) { 1751 OS << "if "; 1752 I->getCond()->printPretty(OS,Helper,Policy); 1753 } 1754 1755 // Default case. 1756 void VisitStmt(Stmt* Terminator) { 1757 Terminator->printPretty(OS, Helper, Policy); 1758 } 1759 1760 void VisitForStmt(ForStmt* F) { 1761 OS << "for (" ; 1762 if (F->getInit()) OS << "..."; 1763 OS << "; "; 1764 if (Stmt* C = F->getCond()) C->printPretty(OS, Helper, Policy); 1765 OS << "; "; 1766 if (F->getInc()) OS << "..."; 1767 OS << ")"; 1768 } 1769 1770 void VisitWhileStmt(WhileStmt* W) { 1771 OS << "while " ; 1772 if (Stmt* C = W->getCond()) C->printPretty(OS, Helper, Policy); 1773 } 1774 1775 void VisitDoStmt(DoStmt* D) { 1776 OS << "do ... while "; 1777 if (Stmt* C = D->getCond()) C->printPretty(OS, Helper, Policy); 1778 } 1779 1780 void VisitSwitchStmt(SwitchStmt* Terminator) { 1781 OS << "switch "; 1782 Terminator->getCond()->printPretty(OS, Helper, Policy); 1783 } 1784 1785 void VisitConditionalOperator(ConditionalOperator* C) { 1786 C->getCond()->printPretty(OS, Helper, Policy); 1787 OS << " ? ... : ..."; 1788 } 1789 1790 void VisitChooseExpr(ChooseExpr* C) { 1791 OS << "__builtin_choose_expr( "; 1792 C->getCond()->printPretty(OS, Helper, Policy); 1793 OS << " )"; 1794 } 1795 1796 void VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1797 OS << "goto *"; 1798 I->getTarget()->printPretty(OS, Helper, Policy); 1799 } 1800 1801 void VisitBinaryOperator(BinaryOperator* B) { 1802 if (!B->isLogicalOp()) { 1803 VisitExpr(B); 1804 return; 1805 } 1806 1807 B->getLHS()->printPretty(OS, Helper, Policy); 1808 1809 switch (B->getOpcode()) { 1810 case BinaryOperator::LOr: 1811 OS << " || ..."; 1812 return; 1813 case BinaryOperator::LAnd: 1814 OS << " && ..."; 1815 return; 1816 default: 1817 assert(false && "Invalid logical operator."); 1818 } 1819 } 1820 1821 void VisitExpr(Expr* E) { 1822 E->printPretty(OS, Helper, Policy); 1823 } 1824}; 1825} // end anonymous namespace 1826 1827 1828static void print_stmt(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, 1829 Stmt* Terminator) { 1830 if (Helper) { 1831 // special printing for statement-expressions. 1832 if (StmtExpr* SE = dyn_cast<StmtExpr>(Terminator)) { 1833 CompoundStmt* Sub = SE->getSubStmt(); 1834 1835 if (Sub->child_begin() != Sub->child_end()) { 1836 OS << "({ ... ; "; 1837 Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); 1838 OS << " })\n"; 1839 return; 1840 } 1841 } 1842 1843 // special printing for comma expressions. 1844 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Terminator)) { 1845 if (B->getOpcode() == BinaryOperator::Comma) { 1846 OS << "... , "; 1847 Helper->handledStmt(B->getRHS(),OS); 1848 OS << '\n'; 1849 return; 1850 } 1851 } 1852 } 1853 1854 Terminator->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 1855 1856 // Expressions need a newline. 1857 if (isa<Expr>(Terminator)) OS << '\n'; 1858} 1859 1860static void print_block(llvm::raw_ostream& OS, const CFG* cfg, 1861 const CFGBlock& B, 1862 StmtPrinterHelper* Helper, bool print_edges) { 1863 1864 if (Helper) Helper->setBlockID(B.getBlockID()); 1865 1866 // Print the header. 1867 OS << "\n [ B" << B.getBlockID(); 1868 1869 if (&B == &cfg->getEntry()) 1870 OS << " (ENTRY) ]\n"; 1871 else if (&B == &cfg->getExit()) 1872 OS << " (EXIT) ]\n"; 1873 else if (&B == cfg->getIndirectGotoBlock()) 1874 OS << " (INDIRECT GOTO DISPATCH) ]\n"; 1875 else 1876 OS << " ]\n"; 1877 1878 // Print the label of this block. 1879 if (Stmt* Terminator = const_cast<Stmt*>(B.getLabel())) { 1880 1881 if (print_edges) 1882 OS << " "; 1883 1884 if (LabelStmt* L = dyn_cast<LabelStmt>(Terminator)) 1885 OS << L->getName(); 1886 else if (CaseStmt* C = dyn_cast<CaseStmt>(Terminator)) { 1887 OS << "case "; 1888 C->getLHS()->printPretty(OS, Helper, 1889 PrintingPolicy(Helper->getLangOpts())); 1890 if (C->getRHS()) { 1891 OS << " ... "; 1892 C->getRHS()->printPretty(OS, Helper, 1893 PrintingPolicy(Helper->getLangOpts())); 1894 } 1895 } else if (isa<DefaultStmt>(Terminator)) 1896 OS << "default"; 1897 else 1898 assert(false && "Invalid label statement in CFGBlock."); 1899 1900 OS << ":\n"; 1901 } 1902 1903 // Iterate through the statements in the block and print them. 1904 unsigned j = 1; 1905 1906 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; 1907 I != E ; ++I, ++j ) { 1908 1909 // Print the statement # in the basic block and the statement itself. 1910 if (print_edges) 1911 OS << " "; 1912 1913 OS << llvm::format("%3d", j) << ": "; 1914 1915 if (Helper) 1916 Helper->setStmtID(j); 1917 1918 print_stmt(OS,Helper,*I); 1919 } 1920 1921 // Print the terminator of this block. 1922 if (B.getTerminator()) { 1923 if (print_edges) 1924 OS << " "; 1925 1926 OS << " T: "; 1927 1928 if (Helper) Helper->setBlockID(-1); 1929 1930 CFGBlockTerminatorPrint TPrinter(OS, Helper, 1931 PrintingPolicy(Helper->getLangOpts())); 1932 TPrinter.Visit(const_cast<Stmt*>(B.getTerminator())); 1933 OS << '\n'; 1934 } 1935 1936 if (print_edges) { 1937 // Print the predecessors of this block. 1938 OS << " Predecessors (" << B.pred_size() << "):"; 1939 unsigned i = 0; 1940 1941 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); 1942 I != E; ++I, ++i) { 1943 1944 if (i == 8 || (i-8) == 0) 1945 OS << "\n "; 1946 1947 OS << " B" << (*I)->getBlockID(); 1948 } 1949 1950 OS << '\n'; 1951 1952 // Print the successors of this block. 1953 OS << " Successors (" << B.succ_size() << "):"; 1954 i = 0; 1955 1956 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); 1957 I != E; ++I, ++i) { 1958 1959 if (i == 8 || (i-8) % 10 == 0) 1960 OS << "\n "; 1961 1962 if (*I) 1963 OS << " B" << (*I)->getBlockID(); 1964 else 1965 OS << " NULL"; 1966 } 1967 1968 OS << '\n'; 1969 } 1970} 1971 1972 1973/// dump - A simple pretty printer of a CFG that outputs to stderr. 1974void CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); } 1975 1976/// print - A simple pretty printer of a CFG that outputs to an ostream. 1977void CFG::print(llvm::raw_ostream &OS, const LangOptions &LO) const { 1978 StmtPrinterHelper Helper(this, LO); 1979 1980 // Print the entry block. 1981 print_block(OS, this, getEntry(), &Helper, true); 1982 1983 // Iterate through the CFGBlocks and print them one by one. 1984 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { 1985 // Skip the entry block, because we already printed it. 1986 if (&(**I) == &getEntry() || &(**I) == &getExit()) 1987 continue; 1988 1989 print_block(OS, this, **I, &Helper, true); 1990 } 1991 1992 // Print the exit block. 1993 print_block(OS, this, getExit(), &Helper, true); 1994 OS.flush(); 1995} 1996 1997/// dump - A simply pretty printer of a CFGBlock that outputs to stderr. 1998void CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const { 1999 print(llvm::errs(), cfg, LO); 2000} 2001 2002/// print - A simple pretty printer of a CFGBlock that outputs to an ostream. 2003/// Generally this will only be called from CFG::print. 2004void CFGBlock::print(llvm::raw_ostream& OS, const CFG* cfg, 2005 const LangOptions &LO) const { 2006 StmtPrinterHelper Helper(cfg, LO); 2007 print_block(OS, cfg, *this, &Helper, true); 2008} 2009 2010/// printTerminator - A simple pretty printer of the terminator of a CFGBlock. 2011void CFGBlock::printTerminator(llvm::raw_ostream &OS, 2012 const LangOptions &LO) const { 2013 CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); 2014 TPrinter.Visit(const_cast<Stmt*>(getTerminator())); 2015} 2016 2017Stmt* CFGBlock::getTerminatorCondition() { 2018 2019 if (!Terminator) 2020 return NULL; 2021 2022 Expr* E = NULL; 2023 2024 switch (Terminator->getStmtClass()) { 2025 default: 2026 break; 2027 2028 case Stmt::ForStmtClass: 2029 E = cast<ForStmt>(Terminator)->getCond(); 2030 break; 2031 2032 case Stmt::WhileStmtClass: 2033 E = cast<WhileStmt>(Terminator)->getCond(); 2034 break; 2035 2036 case Stmt::DoStmtClass: 2037 E = cast<DoStmt>(Terminator)->getCond(); 2038 break; 2039 2040 case Stmt::IfStmtClass: 2041 E = cast<IfStmt>(Terminator)->getCond(); 2042 break; 2043 2044 case Stmt::ChooseExprClass: 2045 E = cast<ChooseExpr>(Terminator)->getCond(); 2046 break; 2047 2048 case Stmt::IndirectGotoStmtClass: 2049 E = cast<IndirectGotoStmt>(Terminator)->getTarget(); 2050 break; 2051 2052 case Stmt::SwitchStmtClass: 2053 E = cast<SwitchStmt>(Terminator)->getCond(); 2054 break; 2055 2056 case Stmt::ConditionalOperatorClass: 2057 E = cast<ConditionalOperator>(Terminator)->getCond(); 2058 break; 2059 2060 case Stmt::BinaryOperatorClass: // '&&' and '||' 2061 E = cast<BinaryOperator>(Terminator)->getLHS(); 2062 break; 2063 2064 case Stmt::ObjCForCollectionStmtClass: 2065 return Terminator; 2066 } 2067 2068 return E ? E->IgnoreParens() : NULL; 2069} 2070 2071bool CFGBlock::hasBinaryBranchTerminator() const { 2072 2073 if (!Terminator) 2074 return false; 2075 2076 Expr* E = NULL; 2077 2078 switch (Terminator->getStmtClass()) { 2079 default: 2080 return false; 2081 2082 case Stmt::ForStmtClass: 2083 case Stmt::WhileStmtClass: 2084 case Stmt::DoStmtClass: 2085 case Stmt::IfStmtClass: 2086 case Stmt::ChooseExprClass: 2087 case Stmt::ConditionalOperatorClass: 2088 case Stmt::BinaryOperatorClass: 2089 return true; 2090 } 2091 2092 return E ? E->IgnoreParens() : NULL; 2093} 2094 2095 2096//===----------------------------------------------------------------------===// 2097// CFG Graphviz Visualization 2098//===----------------------------------------------------------------------===// 2099 2100 2101#ifndef NDEBUG 2102static StmtPrinterHelper* GraphHelper; 2103#endif 2104 2105void CFG::viewCFG(const LangOptions &LO) const { 2106#ifndef NDEBUG 2107 StmtPrinterHelper H(this, LO); 2108 GraphHelper = &H; 2109 llvm::ViewGraph(this,"CFG"); 2110 GraphHelper = NULL; 2111#endif 2112} 2113 2114namespace llvm { 2115template<> 2116struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { 2117 2118 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 2119 2120 static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph) { 2121 2122#ifndef NDEBUG 2123 std::string OutSStr; 2124 llvm::raw_string_ostream Out(OutSStr); 2125 print_block(Out,Graph, *Node, GraphHelper, false); 2126 std::string& OutStr = Out.str(); 2127 2128 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 2129 2130 // Process string output to make it nicer... 2131 for (unsigned i = 0; i != OutStr.length(); ++i) 2132 if (OutStr[i] == '\n') { // Left justify 2133 OutStr[i] = '\\'; 2134 OutStr.insert(OutStr.begin()+i+1, 'l'); 2135 } 2136 2137 return OutStr; 2138#else 2139 return ""; 2140#endif 2141 } 2142}; 2143} // end namespace llvm 2144