diff options
Diffstat (limited to 'contrib/llvm/tools/clang/lib/Analysis')
11 files changed, 2309 insertions, 494 deletions
diff --git a/contrib/llvm/tools/clang/lib/Analysis/AnalysisContext.cpp b/contrib/llvm/tools/clang/lib/Analysis/AnalysisContext.cpp index bf9f967..5233d3b 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/AnalysisContext.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/AnalysisContext.cpp @@ -59,7 +59,11 @@ CFG *AnalysisContext::getCFG() { return getUnoptimizedCFG(); if (!builtCFG) { - cfg = CFG::buildCFG(D, getBody(), &D->getASTContext(), true, AddEHEdges); + CFG::BuildOptions B; + B.AddEHEdges = AddEHEdges; + B.AddImplicitDtors = AddImplicitDtors; + B.AddInitializers = AddInitializers; + cfg = CFG::buildCFG(D, getBody(), &D->getASTContext(), B); // Even when the cfg is not successfully built, we don't // want to try building it again. builtCFG = true; @@ -69,8 +73,12 @@ CFG *AnalysisContext::getCFG() { CFG *AnalysisContext::getUnoptimizedCFG() { if (!builtCompleteCFG) { - completeCFG = CFG::buildCFG(D, getBody(), &D->getASTContext(), - false, AddEHEdges); + CFG::BuildOptions B; + B.PruneTriviallyFalseEdges = false; + B.AddEHEdges = AddEHEdges; + B.AddImplicitDtors = AddImplicitDtors; + B.AddInitializers = AddInitializers; + completeCFG = CFG::buildCFG(D, getBody(), &D->getASTContext(), B); // Even when the cfg is not successfully built, we don't // want to try building it again. builtCompleteCFG = true; @@ -78,6 +86,10 @@ CFG *AnalysisContext::getUnoptimizedCFG() { return completeCFG; } +void AnalysisContext::dumpCFG() { + getCFG()->dump(getASTContext().getLangOptions()); +} + ParentMap &AnalysisContext::getParentMap() { if (!PM) PM = new ParentMap(getBody()); @@ -122,7 +134,8 @@ AnalysisContext *AnalysisContextManager::getContext(const Decl *D, idx::TranslationUnit *TU) { AnalysisContext *&AC = Contexts[D]; if (!AC) - AC = new AnalysisContext(D, TU, UseUnoptimizedCFG); + AC = new AnalysisContext(D, TU, UseUnoptimizedCFG, false, + AddImplicitDtors, AddInitializers); return AC; } @@ -179,8 +192,8 @@ LocationContextManager::getLocationContext(AnalysisContext *ctx, const StackFrameContext* LocationContextManager::getStackFrame(AnalysisContext *ctx, const LocationContext *parent, - const Stmt *s, const CFGBlock *blk, - unsigned idx) { + const Stmt *s, + const CFGBlock *blk, unsigned idx) { llvm::FoldingSetNodeID ID; StackFrameContext::Profile(ID, ctx, parent, s, blk, idx); void *InsertPos; @@ -260,7 +273,7 @@ public: } void VisitStmt(Stmt *S) { - for (Stmt::child_iterator I = S->child_begin(), E = S->child_end();I!=E;++I) + for (Stmt::child_range I = S->children(); I; ++I) if (Stmt *child = *I) Visit(child); } diff --git a/contrib/llvm/tools/clang/lib/Analysis/CFG.cpp b/contrib/llvm/tools/clang/lib/Analysis/CFG.cpp index c97b916..a0ec5fe 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/CFG.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/CFG.cpp @@ -32,24 +32,181 @@ static SourceLocation GetEndLoc(Decl* D) { if (VarDecl* VD = dyn_cast<VarDecl>(D)) if (Expr* Ex = VD->getInit()) return Ex->getSourceRange().getEnd(); - return D->getLocation(); } +/// The CFG builder uses a recursive algorithm to build the CFG. When +/// we process an expression, sometimes we know that we must add the +/// subexpressions as block-level expressions. For example: +/// +/// exp1 || exp2 +/// +/// When processing the '||' expression, we know that exp1 and exp2 +/// need to be added as block-level expressions, even though they +/// might not normally need to be. AddStmtChoice records this +/// contextual information. If AddStmtChoice is 'NotAlwaysAdd', then +/// the builder has an option not to add a subexpression as a +/// block-level expression. +/// class AddStmtChoice { public: - enum Kind { NotAlwaysAdd = 0, - AlwaysAdd = 1, - AsLValueNotAlwaysAdd = 2, - AlwaysAddAsLValue = 3 }; + enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 }; - AddStmtChoice(Kind kind) : k(kind) {} + AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {} - bool alwaysAdd() const { return (unsigned)k & 0x1; } - bool asLValue() const { return k >= AsLValueNotAlwaysAdd; } + bool alwaysAdd() const { return kind & AlwaysAdd; } + + /// Return a copy of this object, except with the 'always-add' bit + /// set as specified. + AddStmtChoice withAlwaysAdd(bool alwaysAdd) const { + return AddStmtChoice(alwaysAdd ? Kind(kind | AlwaysAdd) : + Kind(kind & ~AlwaysAdd)); + } private: - Kind k; + Kind kind; +}; + +/// LocalScope - Node in tree of local scopes created for C++ implicit +/// destructor calls generation. It contains list of automatic variables +/// declared in the scope and link to position in previous scope this scope +/// began in. +/// +/// The process of creating local scopes is as follows: +/// - Init CFGBuilder::ScopePos with invalid position (equivalent for null), +/// - Before processing statements in scope (e.g. CompoundStmt) create +/// LocalScope object using CFGBuilder::ScopePos as link to previous scope +/// and set CFGBuilder::ScopePos to the end of new scope, +/// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points +/// at this VarDecl, +/// - For every normal (without jump) end of scope add to CFGBlock destructors +/// for objects in the current scope, +/// - For every jump add to CFGBlock destructors for objects +/// between CFGBuilder::ScopePos and local scope position saved for jump +/// target. Thanks to C++ restrictions on goto jumps we can be sure that +/// jump target position will be on the path to root from CFGBuilder::ScopePos +/// (adding any variable that doesn't need constructor to be called to +/// LocalScope can break this assumption), +/// +class LocalScope { +public: + typedef BumpVector<VarDecl*> AutomaticVarsTy; + + /// const_iterator - Iterates local scope backwards and jumps to previous + /// scope on reaching the beginning of currently iterated scope. + class const_iterator { + const LocalScope* Scope; + + /// VarIter is guaranteed to be greater then 0 for every valid iterator. + /// Invalid iterator (with null Scope) has VarIter equal to 0. + unsigned VarIter; + + public: + /// Create invalid iterator. Dereferencing invalid iterator is not allowed. + /// Incrementing invalid iterator is allowed and will result in invalid + /// iterator. + const_iterator() + : Scope(NULL), VarIter(0) {} + + /// Create valid iterator. In case when S.Prev is an invalid iterator and + /// I is equal to 0, this will create invalid iterator. + const_iterator(const LocalScope& S, unsigned I) + : Scope(&S), VarIter(I) { + // Iterator to "end" of scope is not allowed. Handle it by going up + // in scopes tree possibly up to invalid iterator in the root. + if (VarIter == 0 && Scope) + *this = Scope->Prev; + } + + VarDecl* const* operator->() const { + assert (Scope && "Dereferencing invalid iterator is not allowed"); + assert (VarIter != 0 && "Iterator has invalid value of VarIter member"); + return &Scope->Vars[VarIter - 1]; + } + VarDecl* operator*() const { + return *this->operator->(); + } + + const_iterator& operator++() { + if (!Scope) + return *this; + + assert (VarIter != 0 && "Iterator has invalid value of VarIter member"); + --VarIter; + if (VarIter == 0) + *this = Scope->Prev; + return *this; + } + const_iterator operator++(int) { + const_iterator P = *this; + ++*this; + return P; + } + + bool operator==(const const_iterator& rhs) const { + return Scope == rhs.Scope && VarIter == rhs.VarIter; + } + bool operator!=(const const_iterator& rhs) const { + return !(*this == rhs); + } + + operator bool() const { + return *this != const_iterator(); + } + + int distance(const_iterator L); + }; + + friend class const_iterator; + +private: + BumpVectorContext ctx; + + /// Automatic variables in order of declaration. + AutomaticVarsTy Vars; + /// Iterator to variable in previous scope that was declared just before + /// begin of this scope. + const_iterator Prev; + +public: + /// Constructs empty scope linked to previous scope in specified place. + LocalScope(BumpVectorContext &ctx, const_iterator P) + : ctx(ctx), Vars(ctx, 4), Prev(P) {} + + /// Begin of scope in direction of CFG building (backwards). + const_iterator begin() const { return const_iterator(*this, Vars.size()); } + + void addVar(VarDecl* VD) { + Vars.push_back(VD, ctx); + } +}; + +/// distance - Calculates distance from this to L. L must be reachable from this +/// (with use of ++ operator). Cost of calculating the distance is linear w.r.t. +/// number of scopes between this and L. +int LocalScope::const_iterator::distance(LocalScope::const_iterator L) { + int D = 0; + const_iterator F = *this; + while (F.Scope != L.Scope) { + assert (F != const_iterator() + && "L iterator is not reachable from F iterator."); + D += F.VarIter; + F = F.Scope->Prev; + } + D += F.VarIter - L.VarIter; + return D; +} + +/// BlockScopePosPair - Structure for specifying position in CFG during its +/// build process. It consists of CFGBlock that specifies position in CFG graph +/// and LocalScope::const_iterator that specifies position in LocalScope graph. +struct BlockScopePosPair { + BlockScopePosPair() : block(0) {} + BlockScopePosPair(CFGBlock* b, LocalScope::const_iterator scopePos) + : block(b), scopePosition(scopePos) {} + + CFGBlock *block; + LocalScope::const_iterator scopePosition; }; /// CFGBuilder - This class implements CFG construction from an AST. @@ -67,41 +224,48 @@ private: /// implicit fall-throughs without extra basic blocks. /// class CFGBuilder { + typedef BlockScopePosPair JumpTarget; + typedef BlockScopePosPair JumpSource; + ASTContext *Context; llvm::OwningPtr<CFG> cfg; CFGBlock* Block; CFGBlock* Succ; - CFGBlock* ContinueTargetBlock; - CFGBlock* BreakTargetBlock; + JumpTarget ContinueJumpTarget; + JumpTarget BreakJumpTarget; CFGBlock* SwitchTerminatedBlock; CFGBlock* DefaultCaseBlock; CFGBlock* TryTerminatedBlock; - // LabelMap records the mapping from Label expressions to their blocks. - typedef llvm::DenseMap<LabelStmt*,CFGBlock*> LabelMapTy; + // Current position in local scope. + LocalScope::const_iterator ScopePos; + + // LabelMap records the mapping from Label expressions to their jump targets. + typedef llvm::DenseMap<LabelDecl*, JumpTarget> LabelMapTy; LabelMapTy LabelMap; // A list of blocks that end with a "goto" that must be backpatched to their // resolved targets upon completion of CFG construction. - typedef std::vector<CFGBlock*> BackpatchBlocksTy; + typedef std::vector<JumpSource> BackpatchBlocksTy; BackpatchBlocksTy BackpatchBlocks; // A list of labels whose address has been taken (for indirect gotos). - typedef llvm::SmallPtrSet<LabelStmt*,5> LabelSetTy; + typedef llvm::SmallPtrSet<LabelDecl*, 5> LabelSetTy; LabelSetTy AddressTakenLabels; + bool badCFG; + CFG::BuildOptions BuildOpts; + public: explicit CFGBuilder() : cfg(new CFG()), // crew a new CFG Block(NULL), Succ(NULL), - ContinueTargetBlock(NULL), BreakTargetBlock(NULL), SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL), - TryTerminatedBlock(NULL) {} + TryTerminatedBlock(NULL), badCFG(false) {} // buildCFG - Used by external clients to construct the CFG. CFG* buildCFG(const Decl *D, Stmt *Statement, ASTContext *C, - bool pruneTriviallyFalseEdges, bool AddEHEdges, - bool AddScopes); + CFG::BuildOptions BO); private: // Visitors to walk an AST and construct the CFG. @@ -110,22 +274,33 @@ private: CFGBlock *VisitBlockExpr(BlockExpr* E, AddStmtChoice asc); CFGBlock *VisitBreakStmt(BreakStmt *B); CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S); + CFGBlock *VisitExprWithCleanups(ExprWithCleanups *E, + AddStmtChoice asc); CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T); CFGBlock *VisitCXXTryStmt(CXXTryStmt *S); + CFGBlock *VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E, + AddStmtChoice asc); + CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc); + CFGBlock *VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E, + AddStmtChoice asc); + CFGBlock *VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C, + AddStmtChoice asc); CFGBlock *VisitCXXMemberCallExpr(CXXMemberCallExpr *C, AddStmtChoice asc); CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc); CFGBlock *VisitCaseStmt(CaseStmt *C); CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc); CFGBlock *VisitCompoundStmt(CompoundStmt *C); - CFGBlock *VisitConditionalOperator(ConditionalOperator *C, AddStmtChoice asc); + CFGBlock *VisitConditionalOperator(AbstractConditionalOperator *C, + AddStmtChoice asc); CFGBlock *VisitContinueStmt(ContinueStmt *C); CFGBlock *VisitDeclStmt(DeclStmt *DS); - CFGBlock *VisitDeclSubExpr(Decl* D); + CFGBlock *VisitDeclSubExpr(DeclStmt* DS); CFGBlock *VisitDefaultStmt(DefaultStmt *D); CFGBlock *VisitDoStmt(DoStmt *D); CFGBlock *VisitForStmt(ForStmt *F); CFGBlock *VisitGotoStmt(GotoStmt* G); CFGBlock *VisitIfStmt(IfStmt *I); + CFGBlock *VisitImplicitCastExpr(ImplicitCastExpr *E, AddStmtChoice asc); CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I); CFGBlock *VisitLabelStmt(LabelStmt *L); CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc); @@ -138,55 +313,81 @@ private: CFGBlock *VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, AddStmtChoice asc); CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc); CFGBlock *VisitSwitchStmt(SwitchStmt *S); + CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc); CFGBlock *VisitWhileStmt(WhileStmt *W); CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd); CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc); CFGBlock *VisitChildren(Stmt* S); + // Visitors to walk an AST and generate destructors of temporaries in + // full expression. + CFGBlock *VisitForTemporaryDtors(Stmt *E, bool BindToTemporary = false); + CFGBlock *VisitChildrenForTemporaryDtors(Stmt *E); + CFGBlock *VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E); + CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors(CXXBindTemporaryExpr *E, + bool BindToTemporary); + CFGBlock * + VisitConditionalOperatorForTemporaryDtors(AbstractConditionalOperator *E, + bool BindToTemporary); + // NYS == Not Yet Supported CFGBlock* NYS() { badCFG = true; return Block; } - CFGBlock *StartScope(Stmt *S, CFGBlock *B) { - if (!AddScopes) - return B; - - if (B == 0) - B = createBlock(); - B->StartScope(S, cfg->getBumpVectorContext()); - return B; - } - - void EndScope(Stmt *S) { - if (!AddScopes) - return; - - if (Block == 0) - Block = createBlock(); - Block->EndScope(S, cfg->getBumpVectorContext()); - } - void autoCreateBlock() { if (!Block) Block = createBlock(); } CFGBlock *createBlock(bool add_successor = true); - bool FinishBlock(CFGBlock* B); + CFGBlock *addStmt(Stmt *S) { return Visit(S, AddStmtChoice::AlwaysAdd); } + CFGBlock *addInitializer(CXXCtorInitializer *I); + void addAutomaticObjDtors(LocalScope::const_iterator B, + LocalScope::const_iterator E, Stmt* S); + void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD); + + // Local scopes creation. + LocalScope* createOrReuseLocalScope(LocalScope* Scope); + + void addLocalScopeForStmt(Stmt* S); + LocalScope* addLocalScopeForDeclStmt(DeclStmt* DS, LocalScope* Scope = NULL); + LocalScope* addLocalScopeForVarDecl(VarDecl* VD, LocalScope* Scope = NULL); - void AppendStmt(CFGBlock *B, Stmt *S, + void addLocalScopeAndDtors(Stmt* S); + + // Interface to CFGBlock - adding CFGElements. + void appendStmt(CFGBlock *B, Stmt *S, AddStmtChoice asc = AddStmtChoice::AlwaysAdd) { - B->appendStmt(S, cfg->getBumpVectorContext(), asc.asLValue()); + B->appendStmt(S, cfg->getBumpVectorContext()); + } + void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) { + B->appendInitializer(I, cfg->getBumpVectorContext()); + } + void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) { + B->appendBaseDtor(BS, cfg->getBumpVectorContext()); + } + void appendMemberDtor(CFGBlock *B, FieldDecl *FD) { + B->appendMemberDtor(FD, cfg->getBumpVectorContext()); } + void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) { + B->appendTemporaryDtor(E, cfg->getBumpVectorContext()); + } + + void insertAutomaticObjDtors(CFGBlock* Blk, CFGBlock::iterator I, + LocalScope::const_iterator B, LocalScope::const_iterator E, Stmt* S); + void appendAutomaticObjDtors(CFGBlock* Blk, LocalScope::const_iterator B, + LocalScope::const_iterator E, Stmt* S); + void prependAutomaticObjDtorsWithTerminator(CFGBlock* Blk, + LocalScope::const_iterator B, LocalScope::const_iterator E); - void AddSuccessor(CFGBlock *B, CFGBlock *S) { + void addSuccessor(CFGBlock *B, CFGBlock *S) { B->addSuccessor(S, cfg->getBumpVectorContext()); } /// TryResult - a class representing a variant over the values - /// 'true', 'false', or 'unknown'. This is returned by TryEvaluateBool, + /// 'true', 'false', or 'unknown'. This is returned by tryEvaluateBool, /// and is used by the CFGBuilder to decide if a branch condition /// can be decided up front during CFG construction. class TryResult { @@ -204,10 +405,10 @@ private: } }; - /// TryEvaluateBool - Try and evaluate the Stmt and return 0 or 1 + /// tryEvaluateBool - Try and evaluate the Stmt and return 0 or 1 /// if we can evaluate to a known value, otherwise return -1. - TryResult TryEvaluateBool(Expr *S) { - if (!PruneTriviallyFalseEdges) + TryResult tryEvaluateBool(Expr *S) { + if (!BuildOpts.PruneTriviallyFalseEdges) return TryResult(); Expr::EvalResult Result; @@ -217,24 +418,13 @@ private: return TryResult(); } - - bool badCFG; - - // True iff trivially false edges should be pruned from the CFG. - bool PruneTriviallyFalseEdges; - - // True iff EH edges on CallExprs should be added to the CFG. - bool AddEHEdges; - - // True iff scope start and scope end notes should be added to the CFG. - bool AddScopes; }; // FIXME: Add support for dependent-sized array types in C++? // Does it even make sense to build a CFG for an uninstantiated template? -static VariableArrayType* FindVA(Type* t) { - while (ArrayType* vt = dyn_cast<ArrayType>(t)) { - if (VariableArrayType* vat = dyn_cast<VariableArrayType>(vt)) +static const VariableArrayType *FindVA(const Type *t) { + while (const ArrayType *vt = dyn_cast<ArrayType>(t)) { + if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(vt)) if (vat->getSizeExpr()) return vat; @@ -250,19 +440,14 @@ static VariableArrayType* FindVA(Type* t) { /// transferred to the caller. If CFG construction fails, this method returns /// NULL. CFG* CFGBuilder::buildCFG(const Decl *D, Stmt* Statement, ASTContext* C, - bool pruneTriviallyFalseEdges, - bool addehedges, bool AddScopes) { - - AddEHEdges = addehedges; - PruneTriviallyFalseEdges = pruneTriviallyFalseEdges; + CFG::BuildOptions BO) { Context = C; assert(cfg.get()); if (!Statement) return NULL; - this->AddScopes = AddScopes; - badCFG = false; + BuildOpts = BO; // Create an empty block that will serve as the exit block for the CFG. Since // this is the first block added to the CFG, it will be implicitly registered @@ -271,59 +456,67 @@ CFG* CFGBuilder::buildCFG(const Decl *D, Stmt* Statement, ASTContext* C, assert(Succ == &cfg->getExit()); Block = NULL; // the EXIT block is empty. Create all other blocks lazily. + if (BuildOpts.AddImplicitDtors) + if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D)) + addImplicitDtorsForDestructor(DD); + // Visit the statements and create the CFG. - CFGBlock* B = addStmt(Statement); + CFGBlock *B = addStmt(Statement); + if (badCFG) + return NULL; + + // For C++ constructor add initializers to CFG. if (const CXXConstructorDecl *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) { - // FIXME: Add code for base initializers and member initializers. - (void)CD; + for (CXXConstructorDecl::init_const_reverse_iterator I = CD->init_rbegin(), + E = CD->init_rend(); I != E; ++I) { + B = addInitializer(*I); + if (badCFG) + return NULL; + } } - if (!B) - B = Succ; - - if (B) { - // Finalize the last constructed block. This usually involves reversing the - // order of the statements in the block. - if (Block) FinishBlock(B); - - // Backpatch the gotos whose label -> block mappings we didn't know when we - // encountered them. - for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(), - E = BackpatchBlocks.end(); I != E; ++I ) { - CFGBlock* B = *I; - GotoStmt* G = cast<GotoStmt>(B->getTerminator()); - LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); - - // If there is no target for the goto, then we are looking at an - // incomplete AST. Handle this by not registering a successor. - if (LI == LabelMap.end()) continue; + if (B) + Succ = B; - AddSuccessor(B, LI->second); - } + // Backpatch the gotos whose label -> block mappings we didn't know when we + // encountered them. + for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(), + E = BackpatchBlocks.end(); I != E; ++I ) { - // Add successors to the Indirect Goto Dispatch block (if we have one). - if (CFGBlock* B = cfg->getIndirectGotoBlock()) - for (LabelSetTy::iterator I = AddressTakenLabels.begin(), - E = AddressTakenLabels.end(); I != E; ++I ) { + CFGBlock* B = I->block; + GotoStmt* G = cast<GotoStmt>(B->getTerminator()); + LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); - // Lookup the target block. - LabelMapTy::iterator LI = LabelMap.find(*I); + // If there is no target for the goto, then we are looking at an + // incomplete AST. Handle this by not registering a successor. + if (LI == LabelMap.end()) continue; - // If there is no target block that contains label, then we are looking - // at an incomplete AST. Handle this by not registering a successor. - if (LI == LabelMap.end()) continue; + JumpTarget JT = LI->second; + prependAutomaticObjDtorsWithTerminator(B, I->scopePosition, + JT.scopePosition); + addSuccessor(B, JT.block); + } - AddSuccessor(B, LI->second); - } + // Add successors to the Indirect Goto Dispatch block (if we have one). + if (CFGBlock* B = cfg->getIndirectGotoBlock()) + for (LabelSetTy::iterator I = AddressTakenLabels.begin(), + E = AddressTakenLabels.end(); I != E; ++I ) { + + // Lookup the target block. + LabelMapTy::iterator LI = LabelMap.find(*I); - Succ = B; - } + // If there is no target block that contains label, then we are looking + // at an incomplete AST. Handle this by not registering a successor. + if (LI == LabelMap.end()) continue; + + addSuccessor(B, LI->second.block); + } // Create an empty entry block that has no predecessors. cfg->setEntry(createBlock()); - return badCFG ? NULL : cfg.take(); + return cfg.take(); } /// createBlock - Used to lazily create blocks that are connected @@ -331,17 +524,251 @@ CFG* CFGBuilder::buildCFG(const Decl *D, Stmt* Statement, ASTContext* C, CFGBlock* CFGBuilder::createBlock(bool add_successor) { CFGBlock* B = cfg->createBlock(); if (add_successor && Succ) - AddSuccessor(B, Succ); + addSuccessor(B, Succ); return B; } -/// FinishBlock - "Finalize" the block by checking if we have a bad CFG. -bool CFGBuilder::FinishBlock(CFGBlock* B) { - if (badCFG) - return false; +/// addInitializer - Add C++ base or member initializer element to CFG. +CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) { + if (!BuildOpts.AddInitializers) + return Block; - assert(B); - return true; + bool IsReference = false; + bool HasTemporaries = false; + + // Destructors of temporaries in initialization expression should be called + // after initialization finishes. + Expr *Init = I->getInit(); + if (Init) { + if (FieldDecl *FD = I->getAnyMember()) + IsReference = FD->getType()->isReferenceType(); + HasTemporaries = isa<ExprWithCleanups>(Init); + + if (BuildOpts.AddImplicitDtors && HasTemporaries) { + // Generate destructors for temporaries in initialization expression. + VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(), + IsReference); + } + } + + autoCreateBlock(); + appendInitializer(Block, I); + + if (Init) { + if (HasTemporaries) { + // For expression with temporaries go directly to subexpression to omit + // generating destructors for the second time. + return Visit(cast<ExprWithCleanups>(Init)->getSubExpr()); + } + return Visit(Init); + } + + return Block; +} + +/// addAutomaticObjDtors - Add to current block automatic objects destructors +/// for objects in range of local scope positions. Use S as trigger statement +/// for destructors. +void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B, + LocalScope::const_iterator E, Stmt* S) { + if (!BuildOpts.AddImplicitDtors) + return; + + if (B == E) + return; + + autoCreateBlock(); + appendAutomaticObjDtors(Block, B, E, S); +} + +/// addImplicitDtorsForDestructor - Add implicit destructors generated for +/// base and member objects in destructor. +void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) { + assert (BuildOpts.AddImplicitDtors + && "Can be called only when dtors should be added"); + const CXXRecordDecl *RD = DD->getParent(); + + // At the end destroy virtual base objects. + for (CXXRecordDecl::base_class_const_iterator VI = RD->vbases_begin(), + VE = RD->vbases_end(); VI != VE; ++VI) { + const CXXRecordDecl *CD = VI->getType()->getAsCXXRecordDecl(); + if (!CD->hasTrivialDestructor()) { + autoCreateBlock(); + appendBaseDtor(Block, VI); + } + } + + // Before virtual bases destroy direct base objects. + for (CXXRecordDecl::base_class_const_iterator BI = RD->bases_begin(), + BE = RD->bases_end(); BI != BE; ++BI) { + if (!BI->isVirtual()) { + const CXXRecordDecl *CD = BI->getType()->getAsCXXRecordDecl(); + if (!CD->hasTrivialDestructor()) { + autoCreateBlock(); + appendBaseDtor(Block, BI); + } + } + } + + // First destroy member objects. + for (CXXRecordDecl::field_iterator FI = RD->field_begin(), + FE = RD->field_end(); FI != FE; ++FI) { + // Check for constant size array. Set type to array element type. + QualType QT = FI->getType(); + if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) { + if (AT->getSize() == 0) + continue; + QT = AT->getElementType(); + } + + if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl()) + if (!CD->hasTrivialDestructor()) { + autoCreateBlock(); + appendMemberDtor(Block, *FI); + } + } +} + +/// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either +/// way return valid LocalScope object. +LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) { + if (!Scope) { + llvm::BumpPtrAllocator &alloc = cfg->getAllocator(); + Scope = alloc.Allocate<LocalScope>(); + BumpVectorContext ctx(alloc); + new (Scope) LocalScope(ctx, ScopePos); + } + return Scope; +} + +/// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement +/// that should create implicit scope (e.g. if/else substatements). +void CFGBuilder::addLocalScopeForStmt(Stmt* S) { + if (!BuildOpts.AddImplicitDtors) + return; + + LocalScope *Scope = 0; + + // For compound statement we will be creating explicit scope. + if (CompoundStmt *CS = dyn_cast<CompoundStmt>(S)) { + for (CompoundStmt::body_iterator BI = CS->body_begin(), BE = CS->body_end() + ; BI != BE; ++BI) { + Stmt *SI = *BI; + if (LabelStmt *LS = dyn_cast<LabelStmt>(SI)) + SI = LS->getSubStmt(); + if (DeclStmt *DS = dyn_cast<DeclStmt>(SI)) + Scope = addLocalScopeForDeclStmt(DS, Scope); + } + return; + } + + // For any other statement scope will be implicit and as such will be + // interesting only for DeclStmt. + if (LabelStmt *LS = dyn_cast<LabelStmt>(S)) + S = LS->getSubStmt(); + if (DeclStmt *DS = dyn_cast<DeclStmt>(S)) + addLocalScopeForDeclStmt(DS); +} + +/// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will +/// reuse Scope if not NULL. +LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt* DS, + LocalScope* Scope) { + if (!BuildOpts.AddImplicitDtors) + return Scope; + + for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end() + ; DI != DE; ++DI) { + if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) + Scope = addLocalScopeForVarDecl(VD, Scope); + } + return Scope; +} + +/// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will +/// create add scope for automatic objects and temporary objects bound to +/// const reference. Will reuse Scope if not NULL. +LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl* VD, + LocalScope* Scope) { + if (!BuildOpts.AddImplicitDtors) + return Scope; + + // Check if variable is local. + switch (VD->getStorageClass()) { + case SC_None: + case SC_Auto: + case SC_Register: + break; + default: return Scope; + } + + // Check for const references bound to temporary. Set type to pointee. + QualType QT = VD->getType(); + if (const ReferenceType* RT = QT.getTypePtr()->getAs<ReferenceType>()) { + QT = RT->getPointeeType(); + if (!QT.isConstQualified()) + return Scope; + if (!VD->getInit() || !VD->getInit()->Classify(*Context).isRValue()) + return Scope; + } + + // Check for constant size array. Set type to array element type. + if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) { + if (AT->getSize() == 0) + return Scope; + QT = AT->getElementType(); + } + + // Check if type is a C++ class with non-trivial destructor. + if (const CXXRecordDecl* CD = QT->getAsCXXRecordDecl()) + if (!CD->hasTrivialDestructor()) { + // Add the variable to scope + Scope = createOrReuseLocalScope(Scope); + Scope->addVar(VD); + ScopePos = Scope->begin(); + } + return Scope; +} + +/// addLocalScopeAndDtors - For given statement add local scope for it and +/// add destructors that will cleanup the scope. Will reuse Scope if not NULL. +void CFGBuilder::addLocalScopeAndDtors(Stmt* S) { + if (!BuildOpts.AddImplicitDtors) + return; + + LocalScope::const_iterator scopeBeginPos = ScopePos; + addLocalScopeForStmt(S); + addAutomaticObjDtors(ScopePos, scopeBeginPos, S); +} + +/// insertAutomaticObjDtors - Insert destructor CFGElements for variables with +/// automatic storage duration to CFGBlock's elements vector. Insertion will be +/// performed in place specified with iterator. +void CFGBuilder::insertAutomaticObjDtors(CFGBlock* Blk, CFGBlock::iterator I, + LocalScope::const_iterator B, LocalScope::const_iterator E, Stmt* S) { + BumpVectorContext& C = cfg->getBumpVectorContext(); + I = Blk->beginAutomaticObjDtorsInsert(I, B.distance(E), C); + while (B != E) + I = Blk->insertAutomaticObjDtor(I, *B++, S); +} + +/// appendAutomaticObjDtors - Append destructor CFGElements for variables with +/// automatic storage duration to CFGBlock's elements vector. Elements will be +/// appended to physical end of the vector which happens to be logical +/// beginning. +void CFGBuilder::appendAutomaticObjDtors(CFGBlock* Blk, + LocalScope::const_iterator B, LocalScope::const_iterator E, Stmt* S) { + insertAutomaticObjDtors(Blk, Blk->begin(), B, E, S); +} + +/// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for +/// variables with automatic storage duration to CFGBlock's elements vector. +/// Elements will be prepended to physical beginning of the vector which +/// happens to be logical end. Use blocks terminator as statement that specifies +/// destructors call site. +void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock* Blk, + LocalScope::const_iterator B, LocalScope::const_iterator E) { + insertAutomaticObjDtors(Blk, Blk->end(), B, E, Blk->getTerminator()); } /// Visit - Walk the subtree of a statement and add extra @@ -360,6 +787,9 @@ tryAgain: case Stmt::AddrLabelExprClass: return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc); + case Stmt::BinaryConditionalOperatorClass: + return VisitConditionalOperator(cast<BinaryConditionalOperator>(S), asc); + case Stmt::BinaryOperatorClass: return VisitBinaryOperator(cast<BinaryOperator>(S), asc); @@ -391,11 +821,20 @@ tryAgain: case Stmt::CXXCatchStmtClass: return VisitCXXCatchStmt(cast<CXXCatchStmt>(S)); - case Stmt::CXXExprWithTemporariesClass: { - // FIXME: Handle temporaries. For now, just visit the subexpression - // so we don't artificially create extra blocks. - return Visit(cast<CXXExprWithTemporaries>(S)->getSubExpr(), asc); - } + case Stmt::ExprWithCleanupsClass: + return VisitExprWithCleanups(cast<ExprWithCleanups>(S), asc); + + case Stmt::CXXBindTemporaryExprClass: + return VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), asc); + + case Stmt::CXXConstructExprClass: + return VisitCXXConstructExpr(cast<CXXConstructExpr>(S), asc); + + case Stmt::CXXFunctionalCastExprClass: + return VisitCXXFunctionalCastExpr(cast<CXXFunctionalCastExpr>(S), asc); + + case Stmt::CXXTemporaryObjectExprClass: + return VisitCXXTemporaryObjectExpr(cast<CXXTemporaryObjectExpr>(S), asc); case Stmt::CXXMemberCallExprClass: return VisitCXXMemberCallExpr(cast<CXXMemberCallExpr>(S), asc); @@ -424,6 +863,9 @@ tryAgain: case Stmt::IfStmtClass: return VisitIfStmt(cast<IfStmt>(S)); + case Stmt::ImplicitCastExprClass: + return VisitImplicitCastExpr(cast<ImplicitCastExpr>(S), asc); + case Stmt::IndirectGotoStmtClass: return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S)); @@ -467,6 +909,9 @@ tryAgain: case Stmt::SwitchStmtClass: return VisitSwitchStmt(cast<SwitchStmt>(S)); + case Stmt::UnaryOperatorClass: + return VisitUnaryOperator(cast<UnaryOperator>(S), asc); + case Stmt::WhileStmtClass: return VisitWhileStmt(cast<WhileStmt>(S)); } @@ -475,7 +920,7 @@ tryAgain: CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) { if (asc.alwaysAdd()) { autoCreateBlock(); - AppendStmt(Block, S, asc); + appendStmt(Block, S, asc); } return VisitChildren(S); @@ -484,8 +929,7 @@ CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) { /// VisitChildren - Visit the children of a Stmt. CFGBlock *CFGBuilder::VisitChildren(Stmt* Terminator) { CFGBlock *B = Block; - for (Stmt::child_iterator I = Terminator->child_begin(), - E = Terminator->child_end(); I != E; ++I) { + for (Stmt::child_range I = Terminator->children(); I; ++I) { if (*I) B = Visit(*I); } return B; @@ -497,19 +941,29 @@ CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, if (asc.alwaysAdd()) { autoCreateBlock(); - AppendStmt(Block, A, asc); + appendStmt(Block, A, asc); } return Block; } +CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U, + AddStmtChoice asc) { + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, U, asc); + } + + return Visit(U->getSubExpr(), AddStmtChoice()); +} + CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc) { if (B->isLogicalOp()) { // && or || CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); - AppendStmt(ConfluenceBlock, B, asc); + appendStmt(ConfluenceBlock, B, asc); - if (!FinishBlock(ConfluenceBlock)) + if (badCFG) return 0; // create the block evaluating the LHS @@ -522,57 +976,67 @@ CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, CFGBlock* RHSBlock = addStmt(B->getRHS()); if (RHSBlock) { - if (!FinishBlock(RHSBlock)) + if (badCFG) return 0; - } - else { + } else { // Create an empty block for cases where the RHS doesn't require // any explicit statements in the CFG. RHSBlock = createBlock(); } // See if this is a known constant. - TryResult KnownVal = TryEvaluateBool(B->getLHS()); + TryResult KnownVal = tryEvaluateBool(B->getLHS()); if (KnownVal.isKnown() && (B->getOpcode() == BO_LOr)) KnownVal.negate(); // Now link the LHSBlock with RHSBlock. if (B->getOpcode() == BO_LOr) { - AddSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); - AddSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); + addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); + addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); } else { assert(B->getOpcode() == BO_LAnd); - AddSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); - AddSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); + addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); + addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); } // Generate the blocks for evaluating the LHS. Block = LHSBlock; return addStmt(B->getLHS()); } - else if (B->getOpcode() == BO_Comma) { // , + + if (B->getOpcode() == BO_Comma) { // , autoCreateBlock(); - AppendStmt(Block, B, asc); + appendStmt(Block, B, asc); addStmt(B->getRHS()); return addStmt(B->getLHS()); } - else if (B->isAssignmentOp()) { + + if (B->isAssignmentOp()) { if (asc.alwaysAdd()) { autoCreateBlock(); - AppendStmt(Block, B, asc); + appendStmt(Block, B, asc); } + Visit(B->getLHS()); + return Visit(B->getRHS()); + } - Visit(B->getRHS()); - return Visit(B->getLHS(), AddStmtChoice::AsLValueNotAlwaysAdd); + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, B, asc); } - return VisitStmt(B, asc); + CFGBlock *RBlock = Visit(B->getRHS()); + CFGBlock *LBlock = Visit(B->getLHS()); + // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr + // containing a DoStmt, and the LHS doesn't create a new block, then we should + // return RBlock. Otherwise we'll incorrectly return NULL. + return (LBlock ? LBlock : RBlock); } CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) { if (asc.alwaysAdd()) { autoCreateBlock(); - AppendStmt(Block, E, asc); + appendStmt(Block, E, asc); } return Block; } @@ -580,8 +1044,8 @@ CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) { CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { // "break" is a control-flow statement. Thus we stop processing the current // block. - if (Block && !FinishBlock(Block)) - return 0; + if (badCFG) + return 0; // Now create a new block that ends with the break statement. Block = createBlock(false); @@ -589,9 +1053,10 @@ CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { // If there is no target for the break, then we are looking at an incomplete // AST. This means that the CFG cannot be constructed. - if (BreakTargetBlock) - AddSuccessor(Block, BreakTargetBlock); - else + if (BreakJumpTarget.block) { + addAutomaticObjDtors(ScopePos, BreakJumpTarget.scopePosition, B); + addSuccessor(Block, BreakJumpTarget.block); + } else badCFG = true; @@ -624,8 +1089,8 @@ CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { bool AddEHEdge = false; // Languages without exceptions are assumed to not throw. - if (Context->getLangOptions().Exceptions) { - if (AddEHEdges) + if (Context->getLangOptions().areExceptionsEnabled()) { + if (BuildOpts.AddEHEdges) AddEHEdge = true; } @@ -639,32 +1104,28 @@ CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { if (!CanThrow(C->getCallee())) AddEHEdge = false; - if (!NoReturn && !AddEHEdge) { - if (asc.asLValue()) - return VisitStmt(C, AddStmtChoice::AlwaysAddAsLValue); - else - return VisitStmt(C, AddStmtChoice::AlwaysAdd); - } + if (!NoReturn && !AddEHEdge) + return VisitStmt(C, asc.withAlwaysAdd(true)); if (Block) { Succ = Block; - if (!FinishBlock(Block)) + if (badCFG) return 0; } Block = createBlock(!NoReturn); - AppendStmt(Block, C, asc); + appendStmt(Block, C, asc); if (NoReturn) { // Wire this to the exit block directly. - AddSuccessor(Block, &cfg->getExit()); + addSuccessor(Block, &cfg->getExit()); } if (AddEHEdge) { // Add exceptional edges. if (TryTerminatedBlock) - AddSuccessor(Block, TryTerminatedBlock); + addSuccessor(Block, TryTerminatedBlock); else - AddSuccessor(Block, &cfg->getExit()); + addSuccessor(Block, &cfg->getExit()); } return VisitChildren(C); @@ -673,38 +1134,35 @@ CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc) { CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); - AppendStmt(ConfluenceBlock, C, asc); - if (!FinishBlock(ConfluenceBlock)) + appendStmt(ConfluenceBlock, C, asc); + if (badCFG) return 0; - asc = asc.asLValue() ? AddStmtChoice::AlwaysAddAsLValue - : AddStmtChoice::AlwaysAdd; - + AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true); Succ = ConfluenceBlock; Block = NULL; - CFGBlock* LHSBlock = Visit(C->getLHS(), asc); - if (!FinishBlock(LHSBlock)) + CFGBlock* LHSBlock = Visit(C->getLHS(), alwaysAdd); + if (badCFG) return 0; Succ = ConfluenceBlock; Block = NULL; - CFGBlock* RHSBlock = Visit(C->getRHS(), asc); - if (!FinishBlock(RHSBlock)) + CFGBlock* RHSBlock = Visit(C->getRHS(), alwaysAdd); + if (badCFG) return 0; Block = createBlock(false); // See if this is a known constant. - const TryResult& KnownVal = TryEvaluateBool(C->getCond()); - AddSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); - AddSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); + const TryResult& KnownVal = tryEvaluateBool(C->getCond()); + addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); + addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); Block->setTerminator(C); return addStmt(C->getCond()); } CFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) { - EndScope(C); - + addLocalScopeAndDtors(C); CFGBlock* LastBlock = Block; for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); @@ -718,22 +1176,22 @@ CFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) { return NULL; } - LastBlock = StartScope(C, LastBlock); - return LastBlock; } -CFGBlock *CFGBuilder::VisitConditionalOperator(ConditionalOperator *C, +CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C, AddStmtChoice asc) { + const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(C); + const OpaqueValueExpr *opaqueValue = (BCO ? BCO->getOpaqueValue() : NULL); + // Create the confluence block that will "merge" the results of the ternary // expression. CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); - AppendStmt(ConfluenceBlock, C, asc); - if (!FinishBlock(ConfluenceBlock)) + appendStmt(ConfluenceBlock, C, asc); + if (badCFG) return 0; - asc = asc.asLValue() ? AddStmtChoice::AlwaysAddAsLValue - : AddStmtChoice::AlwaysAdd; + AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true); // Create a block for the LHS expression if there is an LHS expression. A // GCC extension allows LHS to be NULL, causing the condition to be the @@ -741,60 +1199,48 @@ CFGBlock *CFGBuilder::VisitConditionalOperator(ConditionalOperator *C, // e.g: x ?: y is shorthand for: x ? x : y; Succ = ConfluenceBlock; Block = NULL; - CFGBlock* LHSBlock = NULL; - if (C->getLHS()) { - LHSBlock = Visit(C->getLHS(), asc); - if (!FinishBlock(LHSBlock)) + CFGBlock* LHSBlock = 0; + const Expr *trueExpr = C->getTrueExpr(); + if (trueExpr != opaqueValue) { + LHSBlock = Visit(C->getTrueExpr(), alwaysAdd); + if (badCFG) return 0; Block = NULL; } // Create the block for the RHS expression. Succ = ConfluenceBlock; - CFGBlock* RHSBlock = Visit(C->getRHS(), asc); - if (!FinishBlock(RHSBlock)) + CFGBlock* RHSBlock = Visit(C->getFalseExpr(), alwaysAdd); + if (badCFG) return 0; // Create the block that will contain the condition. Block = createBlock(false); // See if this is a known constant. - const TryResult& KnownVal = TryEvaluateBool(C->getCond()); - if (LHSBlock) { - AddSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); - } else { - if (KnownVal.isFalse()) { - // If we know the condition is false, add NULL as the successor for - // the block containing the condition. In this case, the confluence - // block will have just one predecessor. - AddSuccessor(Block, 0); - assert(ConfluenceBlock->pred_size() == 1); - } else { - // If we have no LHS expression, add the ConfluenceBlock as a direct - // successor for the block containing the condition. Moreover, we need to - // reverse the order of the predecessors in the ConfluenceBlock because - // the RHSBlock will have been added to the succcessors already, and we - // want the first predecessor to the the block containing the expression - // for the case when the ternary expression evaluates to true. - AddSuccessor(Block, ConfluenceBlock); - assert(ConfluenceBlock->pred_size() == 2); - std::reverse(ConfluenceBlock->pred_begin(), - ConfluenceBlock->pred_end()); - } - } - - AddSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); + const TryResult& KnownVal = tryEvaluateBool(C->getCond()); + if (LHSBlock) + addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); + addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); Block->setTerminator(C); - return addStmt(C->getCond()); + Expr *condExpr = C->getCond(); + + CFGBlock *result = 0; + + // Run the condition expression if it's not trivially expressed in + // terms of the opaque value (or if there is no opaque value). + if (condExpr != opaqueValue) result = addStmt(condExpr); + + // Before that, run the common subexpression if there was one. + // At least one of this or the above will be run. + if (opaqueValue) result = addStmt(BCO->getCommon()); + + return result; } CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) { - autoCreateBlock(); - - if (DS->isSingleDecl()) { - AppendStmt(Block, DS); - return VisitDeclSubExpr(DS->getSingleDecl()); - } + if (DS->isSingleDecl()) + return VisitDeclSubExpr(DS); CFGBlock *B = 0; @@ -815,37 +1261,63 @@ CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) { DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); // Append the fake DeclStmt to block. - AppendStmt(Block, DSNew); - B = VisitDeclSubExpr(D); + B = VisitDeclSubExpr(DSNew); } return B; } /// VisitDeclSubExpr - Utility method to add block-level expressions for -/// initializers in Decls. -CFGBlock *CFGBuilder::VisitDeclSubExpr(Decl* D) { - assert(Block); +/// DeclStmts and initializers in them. +CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt* DS) { + assert(DS->isSingleDecl() && "Can handle single declarations only."); - VarDecl *VD = dyn_cast<VarDecl>(D); + VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl()); - if (!VD) + if (!VD) { + autoCreateBlock(); + appendStmt(Block, DS); return Block; + } + bool IsReference = false; + bool HasTemporaries = false; + + // Destructors of temporaries in initialization expression should be called + // after initialization finishes. Expr *Init = VD->getInit(); + if (Init) { + IsReference = VD->getType()->isReferenceType(); + HasTemporaries = isa<ExprWithCleanups>(Init); + + if (BuildOpts.AddImplicitDtors && HasTemporaries) { + // Generate destructors for temporaries in initialization expression. + VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(), + IsReference); + } + } + + autoCreateBlock(); + appendStmt(Block, DS); if (Init) { - AddStmtChoice::Kind k = - VD->getType()->isReferenceType() ? AddStmtChoice::AsLValueNotAlwaysAdd - : AddStmtChoice::NotAlwaysAdd; - Visit(Init, AddStmtChoice(k)); + if (HasTemporaries) + // For expression with temporaries go directly to subexpression to omit + // generating destructors for the second time. + Visit(cast<ExprWithCleanups>(Init)->getSubExpr()); + else + Visit(Init); } // If the type of VD is a VLA, then we must process its size expressions. - for (VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); VA != 0; - VA = FindVA(VA->getElementType().getTypePtr())) + for (const VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); + VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) Block = addStmt(VA->getSizeExpr()); + // Remove variable from local scope. + if (ScopePos && VD == *ScopePos) + ++ScopePos; + return Block; } @@ -857,11 +1329,23 @@ CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { // middle of a block, we stop processing that block. That block is then the // implicit successor for the "then" and "else" clauses. + // Save local scope position because in case of condition variable ScopePos + // won't be restored when traversing AST. + SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); + + // Create local scope for possible condition variable. + // Store scope position. Add implicit destructor. + if (VarDecl* VD = I->getConditionVariable()) { + LocalScope::const_iterator BeginScopePos = ScopePos; + addLocalScopeForVarDecl(VD); + addAutomaticObjDtors(ScopePos, BeginScopePos, I); + } + // The block we were proccessing is now finished. Make it the successor // block. if (Block) { Succ = Block; - if (!FinishBlock(Block)) + if (badCFG) return 0; } @@ -874,12 +1358,18 @@ CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { // NULL out Block so that the recursive call to Visit will // create a new basic block. Block = NULL; + + // If branch is not a compound statement create implicit scope + // and add destructors. + if (!isa<CompoundStmt>(Else)) + addLocalScopeAndDtors(Else); + ElseBlock = addStmt(Else); if (!ElseBlock) // Can occur when the Else body has all NullStmts. ElseBlock = sv.get(); else if (Block) { - if (!FinishBlock(ElseBlock)) + if (badCFG) return 0; } } @@ -891,6 +1381,12 @@ CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { assert(Then); SaveAndRestore<CFGBlock*> sv(Succ); Block = NULL; + + // If branch is not a compound statement create implicit scope + // and add destructors. + if (!isa<CompoundStmt>(Then)) + addLocalScopeAndDtors(Then); + ThenBlock = addStmt(Then); if (!ThenBlock) { @@ -898,9 +1394,9 @@ CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { // Create an empty block so we can distinguish between true and false // branches in path-sensitive analyses. ThenBlock = createBlock(false); - AddSuccessor(ThenBlock, sv.get()); + addSuccessor(ThenBlock, sv.get()); } else if (Block) { - if (!FinishBlock(ThenBlock)) + if (badCFG) return 0; } } @@ -912,11 +1408,11 @@ CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { Block->setTerminator(I); // See if this is a known constant. - const TryResult &KnownVal = TryEvaluateBool(I->getCond()); + const TryResult &KnownVal = tryEvaluateBool(I->getCond()); // Now add the successors. - AddSuccessor(Block, KnownVal.isFalse() ? NULL : ThenBlock); - AddSuccessor(Block, KnownVal.isTrue()? NULL : ElseBlock); + addSuccessor(Block, KnownVal.isFalse() ? NULL : ThenBlock); + addSuccessor(Block, KnownVal.isTrue()? NULL : ElseBlock); // Add the condition as the last statement in the new block. This may create // new blocks as the condition may contain control-flow. Any newly created @@ -928,7 +1424,7 @@ CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { if (VarDecl *VD = I->getConditionVariable()) { if (Expr *Init = VD->getInit()) { autoCreateBlock(); - AppendStmt(Block, I, AddStmtChoice::AlwaysAdd); + appendStmt(Block, I, AddStmtChoice::AlwaysAdd); addStmt(Init); } } @@ -944,37 +1440,37 @@ CFGBlock* CFGBuilder::VisitReturnStmt(ReturnStmt* R) { // code afterwards is DEAD (unreachable). We still keep a basic block // for that code; a simple "mark-and-sweep" from the entry block will be // able to report such dead blocks. - if (Block) - FinishBlock(Block); // Create the new block. Block = createBlock(false); // The Exit block is the only successor. - AddSuccessor(Block, &cfg->getExit()); + addAutomaticObjDtors(ScopePos, LocalScope::const_iterator(), R); + addSuccessor(Block, &cfg->getExit()); // Add the return statement to the block. This may create new blocks if R // contains control-flow (short-circuit operations). return VisitStmt(R, AddStmtChoice::AlwaysAdd); } -CFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt* L) { +CFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt *L) { // Get the block of the labeled statement. Add it to our map. addStmt(L->getSubStmt()); - CFGBlock* LabelBlock = Block; + CFGBlock *LabelBlock = Block; if (!LabelBlock) // This can happen when the body is empty, i.e. LabelBlock = createBlock(); // scopes that only contains NullStmts. - assert(LabelMap.find(L) == LabelMap.end() && "label already in map"); - LabelMap[ L ] = LabelBlock; + assert(LabelMap.find(L->getDecl()) == LabelMap.end() && + "label already in map"); + LabelMap[L->getDecl()] = JumpTarget(LabelBlock, ScopePos); // Labels partition blocks, so this is the end of the basic block we were // processing (L is the block's label). Because this is label (and we have // already processed the substatement) there is no extra control-flow to worry // about. LabelBlock->setLabel(L); - if (!FinishBlock(LabelBlock)) + if (badCFG) return 0; // We set Block to NULL to allow lazy creation of a new block (if necessary); @@ -989,8 +1485,6 @@ CFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt* L) { CFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) { // Goto is a control-flow statement. Thus we stop processing the current // block and create a new one. - if (Block) - FinishBlock(Block); Block = createBlock(false); Block->setTerminator(G); @@ -1000,9 +1494,12 @@ CFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) { if (I == LabelMap.end()) // We will need to backpatch this block later. - BackpatchBlocks.push_back(Block); - else - AddSuccessor(Block, I->second); + BackpatchBlocks.push_back(JumpSource(Block, ScopePos)); + else { + JumpTarget JT = I->second; + addAutomaticObjDtors(ScopePos, JT.scopePosition, G); + addSuccessor(Block, JT.block); + } return Block; } @@ -1010,10 +1507,27 @@ CFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) { CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { CFGBlock* LoopSuccessor = NULL; + // Save local scope position because in case of condition variable ScopePos + // won't be restored when traversing AST. + SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); + + // Create local scope for init statement and possible condition variable. + // Add destructor for init statement and condition variable. + // Store scope position for continue statement. + if (Stmt* Init = F->getInit()) + addLocalScopeForStmt(Init); + LocalScope::const_iterator LoopBeginScopePos = ScopePos; + + if (VarDecl* VD = F->getConditionVariable()) + addLocalScopeForVarDecl(VD); + LocalScope::const_iterator ContinueScopePos = ScopePos; + + addAutomaticObjDtors(ScopePos, save_scope_pos.get(), F); + // "for" is a control-flow statement. Thus we stop processing the current // block. if (Block) { - if (!FinishBlock(Block)) + if (badCFG) return 0; LoopSuccessor = Block; } else @@ -1021,8 +1535,8 @@ CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { // Save the current value for the break targets. // All breaks should go to the code following the loop. - SaveAndRestore<CFGBlock*> save_break(BreakTargetBlock); - BreakTargetBlock = LoopSuccessor; + SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); + BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); // Because of short-circuit evaluation, the condition of the loop can span // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that @@ -1038,21 +1552,24 @@ CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { if (Stmt* C = F->getCond()) { Block = ExitConditionBlock; EntryConditionBlock = addStmt(C); - assert(Block == EntryConditionBlock); + if (badCFG) + return 0; + assert(Block == EntryConditionBlock || + (Block == 0 && EntryConditionBlock == Succ)); // If this block contains a condition variable, add both the condition // variable and initializer to the CFG. if (VarDecl *VD = F->getConditionVariable()) { if (Expr *Init = VD->getInit()) { autoCreateBlock(); - AppendStmt(Block, F, AddStmtChoice::AlwaysAdd); + appendStmt(Block, F, AddStmtChoice::AlwaysAdd); EntryConditionBlock = addStmt(Init); assert(Block == EntryConditionBlock); } } if (Block) { - if (!FinishBlock(EntryConditionBlock)) + if (badCFG) return 0; } } @@ -1065,18 +1582,21 @@ CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { TryResult KnownVal(true); if (F->getCond()) - KnownVal = TryEvaluateBool(F->getCond()); + KnownVal = tryEvaluateBool(F->getCond()); // Now create the loop body. { assert(F->getBody()); // Save the current values for Block, Succ, and continue targets. - SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), - save_continue(ContinueTargetBlock); + SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); + SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget); // Create a new block to contain the (bottom) of the loop body. Block = NULL; + + // Loop body should end with destructor of Condition variable (if any). + addAutomaticObjDtors(ScopePos, LoopBeginScopePos, F); if (Stmt* I = F->getInc()) { // Generate increment code in its own basic block. This is the target of @@ -1086,62 +1606,65 @@ CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { // No increment code. Create a special, empty, block that is used as the // target block for "looping back" to the start of the loop. assert(Succ == EntryConditionBlock); - Succ = createBlock(); + Succ = Block ? Block : createBlock(); } // Finish up the increment (or empty) block if it hasn't been already. if (Block) { assert(Block == Succ); - if (!FinishBlock(Block)) + if (badCFG) return 0; Block = 0; } - ContinueTargetBlock = Succ; + ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos); // The starting block for the loop increment is the block that should // represent the 'loop target' for looping back to the start of the loop. - ContinueTargetBlock->setLoopTarget(F); + ContinueJumpTarget.block->setLoopTarget(F); + + // If body is not a compound statement create implicit scope + // and add destructors. + if (!isa<CompoundStmt>(F->getBody())) + addLocalScopeAndDtors(F->getBody()); // Now populate the body block, and in the process create new blocks as we // walk the body of the loop. CFGBlock* BodyBlock = addStmt(F->getBody()); if (!BodyBlock) - BodyBlock = ContinueTargetBlock; // can happen for "for (...;...;...) ;" - else if (Block && !FinishBlock(BodyBlock)) + BodyBlock = ContinueJumpTarget.block;//can happen for "for (...;...;...);" + else if (badCFG) return 0; // This new body block is a successor to our "exit" condition block. - AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); + addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); } // Link up the condition block with the code that follows the loop. (the // false branch). - AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); + addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); // If the loop contains initialization, create a new block for those // statements. This block can also contain statements that precede the loop. if (Stmt* I = F->getInit()) { Block = createBlock(); return addStmt(I); - } else { - // There is no loop initialization. We are thus basically a while loop. - // NULL out Block to force lazy block construction. - Block = NULL; - Succ = EntryConditionBlock; - return EntryConditionBlock; } + + // There is no loop initialization. We are thus basically a while loop. + // NULL out Block to force lazy block construction. + Block = NULL; + Succ = EntryConditionBlock; + return EntryConditionBlock; } CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) { if (asc.alwaysAdd()) { autoCreateBlock(); - AppendStmt(Block, M, asc); + appendStmt(Block, M, asc); } - return Visit(M->getBase(), - M->isArrow() ? AddStmtChoice::NotAlwaysAdd - : AddStmtChoice::AsLValueNotAlwaysAdd); + return Visit(M->getBase()); } CFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { @@ -1180,7 +1703,7 @@ CFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { CFGBlock* LoopSuccessor = 0; if (Block) { - if (!FinishBlock(Block)) + if (badCFG) return 0; LoopSuccessor = Block; Block = 0; @@ -1197,7 +1720,7 @@ CFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { // The last statement in the block should be the ObjCForCollectionStmt, which // performs the actual binding to 'element' and determines if there are any // more items in the collection. - AppendStmt(ExitConditionBlock, S); + appendStmt(ExitConditionBlock, S); Block = ExitConditionBlock; // Walk the 'element' expression to see if there are any side-effects. We @@ -1205,7 +1728,7 @@ CFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { // the CFG unless it contains control-flow. EntryConditionBlock = Visit(S->getElement(), AddStmtChoice::NotAlwaysAdd); if (Block) { - if (!FinishBlock(EntryConditionBlock)) + if (badCFG) return 0; Block = 0; } @@ -1217,28 +1740,29 @@ CFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { // Now create the true branch. { // Save the current values for Succ, continue and break targets. - SaveAndRestore<CFGBlock*> save_Succ(Succ), - save_continue(ContinueTargetBlock), save_break(BreakTargetBlock); + SaveAndRestore<CFGBlock*> save_Succ(Succ); + SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), + save_break(BreakJumpTarget); - BreakTargetBlock = LoopSuccessor; - ContinueTargetBlock = EntryConditionBlock; + BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); + ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos); CFGBlock* BodyBlock = addStmt(S->getBody()); if (!BodyBlock) BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;" else if (Block) { - if (!FinishBlock(BodyBlock)) + if (badCFG) return 0; } // This new body block is a successor to our "exit" condition block. - AddSuccessor(ExitConditionBlock, BodyBlock); + addSuccessor(ExitConditionBlock, BodyBlock); } // Link up the condition block with the code that follows the loop. // (the false branch). - AddSuccessor(ExitConditionBlock, LoopSuccessor); + addSuccessor(ExitConditionBlock, LoopSuccessor); // Now create a prologue block to contain the collection expression. Block = createBlock(); @@ -1254,13 +1778,17 @@ CFGBlock* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S) { // The sync body starts its own basic block. This makes it a little easier // for diagnostic clients. if (SyncBlock) { - if (!FinishBlock(SyncBlock)) + if (badCFG) return 0; Block = 0; Succ = SyncBlock; } + // Add the @synchronized to the CFG. + autoCreateBlock(); + appendStmt(Block, S, AddStmtChoice::AlwaysAdd); + // Inline the sync expression. return addStmt(S->getSynchExpr()); } @@ -1273,10 +1801,22 @@ CFGBlock* CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt* S) { CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { CFGBlock* LoopSuccessor = NULL; + // Save local scope position because in case of condition variable ScopePos + // won't be restored when traversing AST. + SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); + + // Create local scope for possible condition variable. + // Store scope position for continue statement. + LocalScope::const_iterator LoopBeginScopePos = ScopePos; + if (VarDecl* VD = W->getConditionVariable()) { + addLocalScopeForVarDecl(VD); + addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W); + } + // "while" is a control-flow statement. Thus we stop processing the current // block. if (Block) { - if (!FinishBlock(Block)) + if (badCFG) return 0; LoopSuccessor = Block; } else @@ -1297,21 +1837,22 @@ CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { if (Stmt* C = W->getCond()) { Block = ExitConditionBlock; EntryConditionBlock = addStmt(C); - assert(Block == EntryConditionBlock); + // The condition might finish the current 'Block'. + Block = EntryConditionBlock; // If this block contains a condition variable, add both the condition // variable and initializer to the CFG. if (VarDecl *VD = W->getConditionVariable()) { if (Expr *Init = VD->getInit()) { autoCreateBlock(); - AppendStmt(Block, W, AddStmtChoice::AlwaysAdd); + appendStmt(Block, W, AddStmtChoice::AlwaysAdd); EntryConditionBlock = addStmt(Init); assert(Block == EntryConditionBlock); } } if (Block) { - if (!FinishBlock(EntryConditionBlock)) + if (badCFG) return 0; } } @@ -1321,16 +1862,16 @@ CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { Succ = EntryConditionBlock; // See if this is a known constant. - const TryResult& KnownVal = TryEvaluateBool(W->getCond()); + const TryResult& KnownVal = tryEvaluateBool(W->getCond()); // Process the loop body. { assert(W->getBody()); // Save the current values for Block, Succ, and continue and break targets - SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), - save_continue(ContinueTargetBlock), - save_break(BreakTargetBlock); + SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); + SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), + save_break(BreakJumpTarget); // Create an empty block to represent the transition block for looping back // to the head of the loop. @@ -1338,31 +1879,39 @@ CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { assert(Succ == EntryConditionBlock); Succ = createBlock(); Succ->setLoopTarget(W); - ContinueTargetBlock = Succ; + ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos); // All breaks should go to the code following the loop. - BreakTargetBlock = LoopSuccessor; + BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); // NULL out Block to force lazy instantiation of blocks for the body. Block = NULL; + // Loop body should end with destructor of Condition variable (if any). + addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W); + + // If body is not a compound statement create implicit scope + // and add destructors. + if (!isa<CompoundStmt>(W->getBody())) + addLocalScopeAndDtors(W->getBody()); + // Create the body. The returned block is the entry to the loop body. CFGBlock* BodyBlock = addStmt(W->getBody()); if (!BodyBlock) - BodyBlock = ContinueTargetBlock; // can happen for "while(...) ;" + BodyBlock = ContinueJumpTarget.block; // can happen for "while(...) ;" else if (Block) { - if (!FinishBlock(BodyBlock)) + if (badCFG) return 0; } // Add the loop body entry as a successor to the condition. - AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); + addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); } // Link up the condition block with the code that follows the loop. (the // false branch). - AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); + addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); // There can be no more statements in the condition block since we loop back // to this block. NULL out Block to force lazy creation of another block. @@ -1385,14 +1934,14 @@ CFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) { // statement. // If we were in the middle of a block we stop processing that block. - if (Block && !FinishBlock(Block)) + if (badCFG) return 0; // Create the new block. Block = createBlock(false); // The Exit block is the only successor. - AddSuccessor(Block, &cfg->getExit()); + addSuccessor(Block, &cfg->getExit()); // Add the statement to the block. This may create new blocks if S contains // control-flow (short-circuit operations). @@ -1401,7 +1950,7 @@ CFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) { CFGBlock* CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr* T) { // If we were in the middle of a block we stop processing that block. - if (Block && !FinishBlock(Block)) + if (badCFG) return 0; // Create the new block. @@ -1409,10 +1958,10 @@ CFGBlock* CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr* T) { if (TryTerminatedBlock) // The current try statement is the only successor. - AddSuccessor(Block, TryTerminatedBlock); + addSuccessor(Block, TryTerminatedBlock); else // otherwise the Exit block is the only successor. - AddSuccessor(Block, &cfg->getExit()); + addSuccessor(Block, &cfg->getExit()); // Add the statement to the block. This may create new blocks if S contains // control-flow (short-circuit operations). @@ -1425,7 +1974,7 @@ CFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { // "do...while" is a control-flow statement. Thus we stop processing the // current block. if (Block) { - if (!FinishBlock(Block)) + if (badCFG) return 0; LoopSuccessor = Block; } else @@ -1446,7 +1995,7 @@ CFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { Block = ExitConditionBlock; EntryConditionBlock = addStmt(C); if (Block) { - if (!FinishBlock(EntryConditionBlock)) + if (badCFG) return 0; } } @@ -1455,7 +2004,7 @@ CFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { Succ = EntryConditionBlock; // See if this is a known constant. - const TryResult &KnownVal = TryEvaluateBool(D->getCond()); + const TryResult &KnownVal = tryEvaluateBool(D->getCond()); // Process the loop body. CFGBlock* BodyBlock = NULL; @@ -1463,26 +2012,31 @@ CFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { assert(D->getBody()); // Save the current values for Block, Succ, and continue and break targets - SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), - save_continue(ContinueTargetBlock), - save_break(BreakTargetBlock); + SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); + SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), + save_break(BreakJumpTarget); // All continues within this loop should go to the condition block - ContinueTargetBlock = EntryConditionBlock; + ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos); // All breaks should go to the code following the loop. - BreakTargetBlock = LoopSuccessor; + BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); // NULL out Block to force lazy instantiation of blocks for the body. Block = NULL; + // If body is not a compound statement create implicit scope + // and add destructors. + if (!isa<CompoundStmt>(D->getBody())) + addLocalScopeAndDtors(D->getBody()); + // Create the body. The returned block is the entry to the loop body. BodyBlock = addStmt(D->getBody()); if (!BodyBlock) BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" else if (Block) { - if (!FinishBlock(BodyBlock)) + if (badCFG) return 0; } @@ -1498,15 +2052,15 @@ CFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { LoopBackBlock->setLoopTarget(D); // Add the loop body entry as a successor to the condition. - AddSuccessor(ExitConditionBlock, LoopBackBlock); + addSuccessor(ExitConditionBlock, LoopBackBlock); } else - AddSuccessor(ExitConditionBlock, NULL); + addSuccessor(ExitConditionBlock, NULL); } // Link up the condition block with the code that follows the loop. // (the false branch). - AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); + addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); // There can be no more statements in the body block(s) since we loop back to // the body. NULL out Block to force lazy creation of another block. @@ -1520,8 +2074,8 @@ CFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { CFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) { // "continue" is a control-flow statement. Thus we stop processing the // current block. - if (Block && !FinishBlock(Block)) - return 0; + if (badCFG) + return 0; // Now create a new block that ends with the continue statement. Block = createBlock(false); @@ -1529,9 +2083,10 @@ CFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) { // If there is no target for the continue, then we are looking at an // incomplete AST. This means the CFG cannot be constructed. - if (ContinueTargetBlock) - AddSuccessor(Block, ContinueTargetBlock); - else + if (ContinueJumpTarget.block) { + addAutomaticObjDtors(ScopePos, ContinueJumpTarget.scopePosition, C); + addSuccessor(Block, ContinueJumpTarget.block); + } else badCFG = true; return Block; @@ -1542,12 +2097,12 @@ CFGBlock *CFGBuilder::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, if (asc.alwaysAdd()) { autoCreateBlock(); - AppendStmt(Block, E); + appendStmt(Block, E); } // VLA types have expressions that must be evaluated. if (E->isArgumentType()) { - for (VariableArrayType* VA = FindVA(E->getArgumentType().getTypePtr()); + for (const VariableArrayType *VA =FindVA(E->getArgumentType().getTypePtr()); VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) addStmt(VA->getSizeExpr()); } @@ -1560,7 +2115,7 @@ CFGBlock *CFGBuilder::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, CFGBlock* CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) { if (asc.alwaysAdd()) { autoCreateBlock(); - AppendStmt(Block, SE); + appendStmt(Block, SE); } return VisitCompoundStmt(SE->getSubStmt()); } @@ -1570,16 +2125,28 @@ CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { // block. CFGBlock* SwitchSuccessor = NULL; + // Save local scope position because in case of condition variable ScopePos + // won't be restored when traversing AST. + SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); + + // Create local scope for possible condition variable. + // Store scope position. Add implicit destructor. + if (VarDecl* VD = Terminator->getConditionVariable()) { + LocalScope::const_iterator SwitchBeginScopePos = ScopePos; + addLocalScopeForVarDecl(VD); + addAutomaticObjDtors(ScopePos, SwitchBeginScopePos, Terminator); + } + if (Block) { - if (!FinishBlock(Block)) + if (badCFG) return 0; SwitchSuccessor = Block; } else SwitchSuccessor = Succ; // Save the current "switch" context. SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), - save_break(BreakTargetBlock), save_default(DefaultCaseBlock); + SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); // Set the "default" case to be the block after the switch statement. If the // switch statement contains a "default:", this value will be overwritten with @@ -1592,22 +2159,28 @@ CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { // Now process the switch body. The code after the switch is the implicit // successor. Succ = SwitchSuccessor; - BreakTargetBlock = SwitchSuccessor; + BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos); // When visiting the body, the case statements should automatically get linked // up to the switch. We also don't keep a pointer to the body, since all // control-flow from the switch goes to case/default statements. assert(Terminator->getBody() && "switch must contain a non-NULL body"); Block = NULL; - CFGBlock *BodyBlock = addStmt(Terminator->getBody()); + + // If body is not a compound statement create implicit scope + // and add destructors. + if (!isa<CompoundStmt>(Terminator->getBody())) + addLocalScopeAndDtors(Terminator->getBody()); + + addStmt(Terminator->getBody()); if (Block) { - if (!FinishBlock(BodyBlock)) + if (badCFG) return 0; } // If we have no "default:" case, the default transition is to the code // following the switch body. - AddSuccessor(SwitchTerminatedBlock, DefaultCaseBlock); + addSuccessor(SwitchTerminatedBlock, DefaultCaseBlock); // Add the terminator and condition in the switch block. SwitchTerminatedBlock->setTerminator(Terminator); @@ -1620,7 +2193,7 @@ CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { if (VarDecl *VD = Terminator->getConditionVariable()) { if (Expr *Init = VD->getInit()) { autoCreateBlock(); - AppendStmt(Block, Terminator, AddStmtChoice::AlwaysAdd); + appendStmt(Block, Terminator, AddStmtChoice::AlwaysAdd); addStmt(Init); } } @@ -1638,16 +2211,16 @@ CFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) { // (which can blow out the stack), manually unroll and create blocks // along the way. while (isa<CaseStmt>(Sub)) { - CFGBlock *CurrentBlock = createBlock(false); - CurrentBlock->setLabel(CS); + CFGBlock *currentBlock = createBlock(false); + currentBlock->setLabel(CS); if (TopBlock) - AddSuccessor(LastBlock, CurrentBlock); + addSuccessor(LastBlock, currentBlock); else - TopBlock = CurrentBlock; + TopBlock = currentBlock; - AddSuccessor(SwitchTerminatedBlock, CurrentBlock); - LastBlock = CurrentBlock; + addSuccessor(SwitchTerminatedBlock, currentBlock); + LastBlock = currentBlock; CS = cast<CaseStmt>(Sub); Sub = CS->getSubStmt(); @@ -1664,22 +2237,21 @@ CFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) { // were processing (the "case XXX:" is the label). CaseBlock->setLabel(CS); - if (!FinishBlock(CaseBlock)) + if (badCFG) return 0; // Add this block to the list of successors for the block with the switch // statement. assert(SwitchTerminatedBlock); - AddSuccessor(SwitchTerminatedBlock, CaseBlock); + addSuccessor(SwitchTerminatedBlock, CaseBlock); // We set Block to NULL to allow lazy creation of a new block (if necessary) Block = NULL; if (TopBlock) { - AddSuccessor(LastBlock, CaseBlock); + addSuccessor(LastBlock, CaseBlock); Succ = TopBlock; - } - else { + } else { // This block is now the implicit successor of other blocks. Succ = CaseBlock; } @@ -1700,7 +2272,7 @@ CFGBlock* CFGBuilder::VisitDefaultStmt(DefaultStmt* Terminator) { // we were processing (the "default:" is the label). DefaultCaseBlock->setLabel(Terminator); - if (!FinishBlock(DefaultCaseBlock)) + if (badCFG) return 0; // Unlike case statements, we don't add the default block to the successors @@ -1724,7 +2296,7 @@ CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) { CFGBlock* TrySuccessor = NULL; if (Block) { - if (!FinishBlock(Block)) + if (badCFG) return 0; TrySuccessor = Block; } else TrySuccessor = Succ; @@ -1750,13 +2322,13 @@ CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) { return 0; // Add this block to the list of successors for the block with the try // statement. - AddSuccessor(NewTryTerminatedBlock, CatchBlock); + addSuccessor(NewTryTerminatedBlock, CatchBlock); } if (!HasCatchAll) { if (PrevTryTerminatedBlock) - AddSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock); + addSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock); else - AddSuccessor(NewTryTerminatedBlock, &cfg->getExit()); + addSuccessor(NewTryTerminatedBlock, &cfg->getExit()); } // The code after the try is the implicit successor. @@ -1776,6 +2348,18 @@ CFGBlock* CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt* CS) { // CXXCatchStmt are treated like labels, so they are the first statement in a // block. + // Save local scope position because in case of exception variable ScopePos + // won't be restored when traversing AST. + SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); + + // Create local scope for possible exception variable. + // Store scope position. Add implicit destructor. + if (VarDecl* VD = CS->getExceptionDecl()) { + LocalScope::const_iterator BeginScopePos = ScopePos; + addLocalScopeForVarDecl(VD); + addAutomaticObjDtors(ScopePos, BeginScopePos, CS); + } + if (CS->getHandlerBlock()) addStmt(CS->getHandlerBlock()); @@ -1785,7 +2369,7 @@ CFGBlock* CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt* CS) { CatchBlock->setLabel(CS); - if (!FinishBlock(CatchBlock)) + if (badCFG) return 0; // We set Block to NULL to allow lazy creation of a new block (if necessary) @@ -1794,15 +2378,75 @@ CFGBlock* CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt* CS) { return CatchBlock; } +CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E, + AddStmtChoice asc) { + if (BuildOpts.AddImplicitDtors) { + // If adding implicit destructors visit the full expression for adding + // destructors of temporaries. + VisitForTemporaryDtors(E->getSubExpr()); + + // Full expression has to be added as CFGStmt so it will be sequenced + // before destructors of it's temporaries. + asc = asc.withAlwaysAdd(true); + } + return Visit(E->getSubExpr(), asc); +} + +CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E, + AddStmtChoice asc) { + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, E, asc); + + // We do not want to propagate the AlwaysAdd property. + asc = asc.withAlwaysAdd(false); + } + return Visit(E->getSubExpr(), asc); +} + +CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C, + AddStmtChoice asc) { + autoCreateBlock(); + if (!C->isElidable()) + appendStmt(Block, C, asc.withAlwaysAdd(true)); + + return VisitChildren(C); +} + +CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E, + AddStmtChoice asc) { + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, E, asc); + // We do not want to propagate the AlwaysAdd property. + asc = asc.withAlwaysAdd(false); + } + return Visit(E->getSubExpr(), asc); +} + +CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C, + AddStmtChoice asc) { + autoCreateBlock(); + appendStmt(Block, C, asc.withAlwaysAdd(true)); + return VisitChildren(C); +} + CFGBlock *CFGBuilder::VisitCXXMemberCallExpr(CXXMemberCallExpr *C, AddStmtChoice asc) { - AddStmtChoice::Kind K = asc.asLValue() ? AddStmtChoice::AlwaysAddAsLValue - : AddStmtChoice::AlwaysAdd; autoCreateBlock(); - AppendStmt(Block, C, AddStmtChoice(K)); + appendStmt(Block, C, asc.withAlwaysAdd(true)); return VisitChildren(C); } +CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E, + AddStmtChoice asc) { + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, E, asc); + } + return Visit(E->getSubExpr(), AddStmtChoice()); +} + CFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { // Lazily create the indirect-goto dispatch block if there isn't one already. CFGBlock* IBlock = cfg->getIndirectGotoBlock(); @@ -1814,15 +2458,210 @@ CFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { // IndirectGoto is a control-flow statement. Thus we stop processing the // current block and create a new one. - if (Block && !FinishBlock(Block)) + if (badCFG) return 0; Block = createBlock(false); Block->setTerminator(I); - AddSuccessor(Block, IBlock); + addSuccessor(Block, IBlock); return addStmt(I->getTarget()); } +CFGBlock *CFGBuilder::VisitForTemporaryDtors(Stmt *E, bool BindToTemporary) { +tryAgain: + if (!E) { + badCFG = true; + return NULL; + } + switch (E->getStmtClass()) { + default: + return VisitChildrenForTemporaryDtors(E); + + case Stmt::BinaryOperatorClass: + return VisitBinaryOperatorForTemporaryDtors(cast<BinaryOperator>(E)); + + case Stmt::CXXBindTemporaryExprClass: + return VisitCXXBindTemporaryExprForTemporaryDtors( + cast<CXXBindTemporaryExpr>(E), BindToTemporary); + + case Stmt::BinaryConditionalOperatorClass: + case Stmt::ConditionalOperatorClass: + return VisitConditionalOperatorForTemporaryDtors( + cast<AbstractConditionalOperator>(E), BindToTemporary); + + case Stmt::ImplicitCastExprClass: + // For implicit cast we want BindToTemporary to be passed further. + E = cast<CastExpr>(E)->getSubExpr(); + goto tryAgain; + + case Stmt::ParenExprClass: + E = cast<ParenExpr>(E)->getSubExpr(); + goto tryAgain; + } +} + +CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E) { + // When visiting children for destructors we want to visit them in reverse + // order. Because there's no reverse iterator for children must to reverse + // them in helper vector. + typedef llvm::SmallVector<Stmt *, 4> ChildrenVect; + ChildrenVect ChildrenRev; + for (Stmt::child_range I = E->children(); I; ++I) { + if (*I) ChildrenRev.push_back(*I); + } + + CFGBlock *B = Block; + for (ChildrenVect::reverse_iterator I = ChildrenRev.rbegin(), + L = ChildrenRev.rend(); I != L; ++I) { + if (CFGBlock *R = VisitForTemporaryDtors(*I)) + B = R; + } + return B; +} + +CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E) { + if (E->isLogicalOp()) { + // Destructors for temporaries in LHS expression should be called after + // those for RHS expression. Even if this will unnecessarily create a block, + // this block will be used at least by the full expression. + autoCreateBlock(); + CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getLHS()); + if (badCFG) + return NULL; + + Succ = ConfluenceBlock; + Block = NULL; + CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS()); + + if (RHSBlock) { + if (badCFG) + return NULL; + + // If RHS expression did produce destructors we need to connect created + // blocks to CFG in same manner as for binary operator itself. + CFGBlock *LHSBlock = createBlock(false); + LHSBlock->setTerminator(CFGTerminator(E, true)); + + // For binary operator LHS block is before RHS in list of predecessors + // of ConfluenceBlock. + std::reverse(ConfluenceBlock->pred_begin(), + ConfluenceBlock->pred_end()); + + // See if this is a known constant. + TryResult KnownVal = tryEvaluateBool(E->getLHS()); + if (KnownVal.isKnown() && (E->getOpcode() == BO_LOr)) + KnownVal.negate(); + + // Link LHSBlock with RHSBlock exactly the same way as for binary operator + // itself. + if (E->getOpcode() == BO_LOr) { + addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); + addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); + } else { + assert (E->getOpcode() == BO_LAnd); + addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); + addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); + } + + Block = LHSBlock; + return LHSBlock; + } + + Block = ConfluenceBlock; + return ConfluenceBlock; + } + + if (E->isAssignmentOp()) { + // For assignment operator (=) LHS expression is visited + // before RHS expression. For destructors visit them in reverse order. + CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS()); + CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS()); + return LHSBlock ? LHSBlock : RHSBlock; + } + + // For any other binary operator RHS expression is visited before + // LHS expression (order of children). For destructors visit them in reverse + // order. + CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS()); + CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS()); + return RHSBlock ? RHSBlock : LHSBlock; +} + +CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors( + CXXBindTemporaryExpr *E, bool BindToTemporary) { + // First add destructors for temporaries in subexpression. + CFGBlock *B = VisitForTemporaryDtors(E->getSubExpr()); + if (!BindToTemporary) { + // If lifetime of temporary is not prolonged (by assigning to constant + // reference) add destructor for it. + autoCreateBlock(); + appendTemporaryDtor(Block, E); + B = Block; + } + return B; +} + +CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors( + AbstractConditionalOperator *E, bool BindToTemporary) { + // First add destructors for condition expression. Even if this will + // unnecessarily create a block, this block will be used at least by the full + // expression. + autoCreateBlock(); + CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getCond()); + if (badCFG) + return NULL; + if (BinaryConditionalOperator *BCO + = dyn_cast<BinaryConditionalOperator>(E)) { + ConfluenceBlock = VisitForTemporaryDtors(BCO->getCommon()); + if (badCFG) + return NULL; + } + + // Try to add block with destructors for LHS expression. + CFGBlock *LHSBlock = NULL; + Succ = ConfluenceBlock; + Block = NULL; + LHSBlock = VisitForTemporaryDtors(E->getTrueExpr(), BindToTemporary); + if (badCFG) + return NULL; + + // Try to add block with destructors for RHS expression; + Succ = ConfluenceBlock; + Block = NULL; + CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getFalseExpr(), + BindToTemporary); + if (badCFG) + return NULL; + + if (!RHSBlock && !LHSBlock) { + // If neither LHS nor RHS expression had temporaries to destroy don't create + // more blocks. + Block = ConfluenceBlock; + return Block; + } + + Block = createBlock(false); + Block->setTerminator(CFGTerminator(E, true)); + + // See if this is a known constant. + const TryResult &KnownVal = tryEvaluateBool(E->getCond()); + + if (LHSBlock) { + addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); + } else if (KnownVal.isFalse()) { + addSuccessor(Block, NULL); + } else { + addSuccessor(Block, ConfluenceBlock); + std::reverse(ConfluenceBlock->pred_begin(), ConfluenceBlock->pred_end()); + } + + if (!RHSBlock) + RHSBlock = ConfluenceBlock; + addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); + + return Block; +} + } // end anonymous namespace /// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has @@ -1847,11 +2686,9 @@ CFGBlock* CFG::createBlock() { /// buildCFG - Constructs a CFG from an AST. Ownership of the returned /// CFG is returned to the caller. CFG* CFG::buildCFG(const Decl *D, Stmt* Statement, ASTContext *C, - bool PruneTriviallyFalse, - bool AddEHEdges, bool AddScopes) { + BuildOptions BO) { CFGBuilder Builder; - return Builder.buildCFG(D, Statement, C, PruneTriviallyFalse, - AddEHEdges, AddScopes); + return Builder.buildCFG(D, Statement, C, BO); } //===----------------------------------------------------------------------===// @@ -1867,7 +2704,7 @@ static void FindSubExprAssignments(Stmt *S, if (!S) return; - for (Stmt::child_iterator I=S->child_begin(), E=S->child_end(); I!=E; ++I) { + for (Stmt::child_range I = S->children(); I; ++I) { Stmt *child = *I; if (!child) continue; @@ -1890,15 +2727,19 @@ static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) - FindSubExprAssignments(*BI, SubExprAssignments); + if (CFGStmt S = BI->getAs<CFGStmt>()) + FindSubExprAssignments(S, SubExprAssignments); for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { // Iterate over the statements again on identify the Expr* and Stmt* at the // block-level that are block-level expressions. - for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) - if (Expr* Exp = dyn_cast<Expr>(*BI)) { + for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) { + CFGStmt CS = BI->getAs<CFGStmt>(); + if (!CS.isValid()) + continue; + if (Expr* Exp = dyn_cast<Expr>(CS.getStmt())) { if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { // Assignment expressions that are not nested within another @@ -1919,6 +2760,7 @@ static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { unsigned x = M->size(); (*M)[Exp] = x; } + } // Look at terminators. The condition is a block-level expression. @@ -1945,12 +2787,34 @@ CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) { unsigned CFG::getNumBlkExprs() { if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) return M->size(); - else { - // We assume callers interested in the number of BlkExprs will want - // the map constructed if it doesn't already exist. - BlkExprMap = (void*) PopulateBlkExprMap(*this); - return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); + + // We assume callers interested in the number of BlkExprs will want + // the map constructed if it doesn't already exist. + BlkExprMap = (void*) PopulateBlkExprMap(*this); + return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); +} + +//===----------------------------------------------------------------------===// +// Filtered walking of the CFG. +//===----------------------------------------------------------------------===// + +bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F, + const CFGBlock *From, const CFGBlock *To) { + + if (F.IgnoreDefaultsWithCoveredEnums) { + // If the 'To' has no label or is labeled but the label isn't a + // CaseStmt then filter this edge. + if (const SwitchStmt *S = + dyn_cast_or_null<SwitchStmt>(From->getTerminator().getStmt())) { + if (S->isAllEnumCasesCovered()) { + const Stmt *L = To->getLabel(); + if (!L || !isa<CaseStmt>(L)) + return true; + } + } } + + return false; } //===----------------------------------------------------------------------===// @@ -1969,37 +2833,81 @@ namespace { class StmtPrinterHelper : public PrinterHelper { typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; + typedef llvm::DenseMap<Decl*,std::pair<unsigned,unsigned> > DeclMapTy; StmtMapTy StmtMap; - signed CurrentBlock; - unsigned CurrentStmt; + DeclMapTy DeclMap; + signed currentBlock; + unsigned currentStmt; const LangOptions &LangOpts; public: StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) - : CurrentBlock(0), CurrentStmt(0), LangOpts(LO) { + : currentBlock(0), currentStmt(0), LangOpts(LO) { for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { unsigned j = 1; for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ; - BI != BEnd; ++BI, ++j ) - StmtMap[*BI] = std::make_pair((*I)->getBlockID(),j); + BI != BEnd; ++BI, ++j ) { + if (CFGStmt SE = BI->getAs<CFGStmt>()) { + std::pair<unsigned, unsigned> P((*I)->getBlockID(), j); + StmtMap[SE] = P; + + if (DeclStmt* DS = dyn_cast<DeclStmt>(SE.getStmt())) { + DeclMap[DS->getSingleDecl()] = P; + + } else if (IfStmt* IS = dyn_cast<IfStmt>(SE.getStmt())) { + if (VarDecl* VD = IS->getConditionVariable()) + DeclMap[VD] = P; + + } else if (ForStmt* FS = dyn_cast<ForStmt>(SE.getStmt())) { + if (VarDecl* VD = FS->getConditionVariable()) + DeclMap[VD] = P; + + } else if (WhileStmt* WS = dyn_cast<WhileStmt>(SE.getStmt())) { + if (VarDecl* VD = WS->getConditionVariable()) + DeclMap[VD] = P; + + } else if (SwitchStmt* SS = dyn_cast<SwitchStmt>(SE.getStmt())) { + if (VarDecl* VD = SS->getConditionVariable()) + DeclMap[VD] = P; + + } else if (CXXCatchStmt* CS = dyn_cast<CXXCatchStmt>(SE.getStmt())) { + if (VarDecl* VD = CS->getExceptionDecl()) + DeclMap[VD] = P; + } + } } + } } virtual ~StmtPrinterHelper() {} const LangOptions &getLangOpts() const { return LangOpts; } - void setBlockID(signed i) { CurrentBlock = i; } - void setStmtID(unsigned i) { CurrentStmt = i; } - - virtual bool handledStmt(Stmt* Terminator, llvm::raw_ostream& OS) { + void setBlockID(signed i) { currentBlock = i; } + void setStmtID(unsigned i) { currentStmt = i; } - StmtMapTy::iterator I = StmtMap.find(Terminator); + virtual bool handledStmt(Stmt* S, llvm::raw_ostream& OS) { + StmtMapTy::iterator I = StmtMap.find(S); if (I == StmtMap.end()) return false; - if (CurrentBlock >= 0 && I->second.first == (unsigned) CurrentBlock - && I->second.second == CurrentStmt) { + if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock + && I->second.second == currentStmt) { + return false; + } + + OS << "[B" << I->second.first << "." << I->second.second << "]"; + return true; + } + + bool handleDecl(Decl* D, llvm::raw_ostream& OS) { + DeclMapTy::iterator I = DeclMap.find(D); + + if (I == DeclMap.end()) + return false; + + if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock + && I->second.second == currentStmt) { return false; } @@ -2066,7 +2974,7 @@ public: OS << "try ..."; } - void VisitConditionalOperator(ConditionalOperator* C) { + void VisitAbstractConditionalOperator(AbstractConditionalOperator* C) { C->getCond()->printPretty(OS, Helper, Policy); OS << " ? ... : ..."; } @@ -2108,58 +3016,95 @@ public: }; } // end anonymous namespace - -static void print_stmt(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, +static void print_elem(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, const CFGElement &E) { - - if (E.asStartScope()) { - OS << "start scope\n"; - return; - } - if (E.asEndScope()) { - OS << "end scope\n"; - return; - } - - Stmt *S = E; - - if (Helper) { - // special printing for statement-expressions. - if (StmtExpr* SE = dyn_cast<StmtExpr>(S)) { - CompoundStmt* Sub = SE->getSubStmt(); - - if (Sub->child_begin() != Sub->child_end()) { - OS << "({ ... ; "; - Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); - OS << " })\n"; - return; + if (CFGStmt CS = E.getAs<CFGStmt>()) { + Stmt *S = CS; + + if (Helper) { + + // special printing for statement-expressions. + if (StmtExpr* SE = dyn_cast<StmtExpr>(S)) { + CompoundStmt* Sub = SE->getSubStmt(); + + if (Sub->children()) { + OS << "({ ... ; "; + Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); + OS << " })\n"; + return; + } + } + // special printing for comma expressions. + if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { + if (B->getOpcode() == BO_Comma) { + OS << "... , "; + Helper->handledStmt(B->getRHS(),OS); + OS << '\n'; + return; + } } } + S->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); - // special printing for comma expressions. - if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { - if (B->getOpcode() == BO_Comma) { - OS << "... , "; - Helper->handledStmt(B->getRHS(),OS); - OS << '\n'; - return; - } + if (isa<CXXOperatorCallExpr>(S)) { + OS << " (OperatorCall)"; + } else if (isa<CXXBindTemporaryExpr>(S)) { + OS << " (BindTemporary)"; } - } - S->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); - - if (isa<CXXOperatorCallExpr>(S)) { - OS << " (OperatorCall)"; - } - else if (isa<CXXBindTemporaryExpr>(S)) { - OS << " (BindTemporary)"; - } + // Expressions need a newline. + if (isa<Expr>(S)) + OS << '\n'; + } else if (CFGInitializer IE = E.getAs<CFGInitializer>()) { + CXXCtorInitializer* I = IE; + if (I->isBaseInitializer()) + OS << I->getBaseClass()->getAsCXXRecordDecl()->getName(); + else OS << I->getAnyMember()->getName(); - // Expressions need a newline. - if (isa<Expr>(S)) - OS << '\n'; + OS << "("; + if (Expr* IE = I->getInit()) + IE->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); + OS << ")"; + + if (I->isBaseInitializer()) + OS << " (Base initializer)\n"; + else OS << " (Member initializer)\n"; + + } else if (CFGAutomaticObjDtor DE = E.getAs<CFGAutomaticObjDtor>()){ + VarDecl* VD = DE.getVarDecl(); + Helper->handleDecl(VD, OS); + + const Type* T = VD->getType().getTypePtr(); + if (const ReferenceType* RT = T->getAs<ReferenceType>()) + T = RT->getPointeeType().getTypePtr(); + else if (const Type *ET = T->getArrayElementTypeNoTypeQual()) + T = ET; + + OS << ".~" << T->getAsCXXRecordDecl()->getName().str() << "()"; + OS << " (Implicit destructor)\n"; + + } else if (CFGBaseDtor BE = E.getAs<CFGBaseDtor>()) { + const CXXBaseSpecifier *BS = BE.getBaseSpecifier(); + OS << "~" << BS->getType()->getAsCXXRecordDecl()->getName() << "()"; + OS << " (Base object destructor)\n"; + + } else if (CFGMemberDtor ME = E.getAs<CFGMemberDtor>()) { + FieldDecl *FD = ME.getFieldDecl(); + + const Type *T = FD->getType().getTypePtr(); + if (const Type *ET = T->getArrayElementTypeNoTypeQual()) + T = ET; + + OS << "this->" << FD->getName(); + OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()"; + OS << " (Member object destructor)\n"; + + } else if (CFGTemporaryDtor TE = E.getAs<CFGTemporaryDtor>()) { + CXXBindTemporaryExpr *BT = TE.getBindTemporaryExpr(); + OS << "~" << BT->getType()->getAsCXXRecordDecl()->getName() << "()"; + OS << " (Temporary object destructor)\n"; + } } static void print_block(llvm::raw_ostream& OS, const CFG* cfg, @@ -2229,7 +3174,7 @@ static void print_block(llvm::raw_ostream& OS, const CFG* cfg, if (Helper) Helper->setStmtID(j); - print_stmt(OS,Helper,*I); + print_elem(OS,Helper,*I); } // Print the terminator of this block. @@ -2243,7 +3188,7 @@ static void print_block(llvm::raw_ostream& OS, const CFG* cfg, CFGBlockTerminatorPrint TPrinter(OS, Helper, PrintingPolicy(Helper->getLangOpts())); - TPrinter.Visit(const_cast<Stmt*>(B.getTerminator())); + TPrinter.Visit(const_cast<Stmt*>(B.getTerminator().getStmt())); OS << '\n'; } @@ -2325,11 +3270,11 @@ void CFGBlock::print(llvm::raw_ostream& OS, const CFG* cfg, void CFGBlock::printTerminator(llvm::raw_ostream &OS, const LangOptions &LO) const { CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); - TPrinter.Visit(const_cast<Stmt*>(getTerminator())); + TPrinter.Visit(const_cast<Stmt*>(getTerminator().getStmt())); } Stmt* CFGBlock::getTerminatorCondition() { - + Stmt *Terminator = this->Terminator; if (!Terminator) return NULL; @@ -2367,6 +3312,10 @@ Stmt* CFGBlock::getTerminatorCondition() { E = cast<SwitchStmt>(Terminator)->getCond(); break; + case Stmt::BinaryConditionalOperatorClass: + E = cast<BinaryConditionalOperator>(Terminator)->getCond(); + break; + case Stmt::ConditionalOperatorClass: E = cast<ConditionalOperator>(Terminator)->getCond(); break; @@ -2383,7 +3332,7 @@ Stmt* CFGBlock::getTerminatorCondition() { } bool CFGBlock::hasBinaryBranchTerminator() const { - + const Stmt *Terminator = this->Terminator; if (!Terminator) return false; @@ -2398,6 +3347,7 @@ bool CFGBlock::hasBinaryBranchTerminator() const { case Stmt::DoStmtClass: case Stmt::IfStmtClass: case Stmt::ChooseExprClass: + case Stmt::BinaryConditionalOperatorClass: case Stmt::ConditionalOperatorClass: case Stmt::BinaryOperatorClass: return true; diff --git a/contrib/llvm/tools/clang/lib/Analysis/CFGStmtMap.cpp b/contrib/llvm/tools/clang/lib/Analysis/CFGStmtMap.cpp index 965eca1..3a030f9 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/CFGStmtMap.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/CFGStmtMap.cpp @@ -50,15 +50,18 @@ static void Accumulate(SMap &SM, CFGBlock *B) { // First walk the block-level expressions. for (CFGBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) { const CFGElement &CE = *I; - if (Stmt *S = CE.getStmt()) { - CFGBlock *&Entry = SM[S]; - // If 'Entry' is already initialized (e.g., a terminator was already), - // skip. - if (Entry) - continue; + CFGStmt CS = CE.getAs<CFGStmt>(); + if (!CS.isValid()) + continue; + + CFGBlock *&Entry = SM[CS]; + // If 'Entry' is already initialized (e.g., a terminator was already), + // skip. + if (Entry) + continue; - Entry = B; - } + Entry = B; + } // Look at the label of the block. diff --git a/contrib/llvm/tools/clang/lib/Analysis/CocoaConventions.cpp b/contrib/llvm/tools/clang/lib/Analysis/CocoaConventions.cpp new file mode 100644 index 0000000..22b6c1a --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/CocoaConventions.cpp @@ -0,0 +1,180 @@ +//===- CocoaConventions.h - Special handling of Cocoa conventions -*- C++ -*--// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/DomainSpecific/CocoaConventions.h" +#include "clang/AST/Type.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclObjC.h" +#include "llvm/ADT/StringExtras.h" + +using namespace clang; +using namespace ento; + +using llvm::StringRef; + +// The "fundamental rule" for naming conventions of methods: +// (url broken into two lines) +// http://developer.apple.com/documentation/Cocoa/Conceptual/ +// MemoryMgmt/Tasks/MemoryManagementRules.html +// +// "You take ownership of an object if you create it using a method whose name +// begins with "alloc" or "new" or contains "copy" (for example, alloc, +// newObject, or mutableCopy), or if you send it a retain message. You are +// responsible for relinquishing ownership of objects you own using release +// or autorelease. Any other time you receive an object, you must +// not release it." +// + +static bool isWordEnd(char ch, char prev, char next) { + return ch == '\0' + || (islower(prev) && isupper(ch)) // xxxC + || (isupper(prev) && isupper(ch) && islower(next)) // XXCreate + || !isalpha(ch); +} + +static const char* parseWord(const char* s) { + char ch = *s, prev = '\0'; + assert(ch != '\0'); + char next = *(s+1); + while (!isWordEnd(ch, prev, next)) { + prev = ch; + ch = next; + next = *((++s)+1); + } + return s; +} + +cocoa::NamingConvention cocoa::deriveNamingConvention(Selector S, + bool ignorePrefix) { + IdentifierInfo *II = S.getIdentifierInfoForSlot(0); + + if (!II) + return NoConvention; + + const char *s = II->getNameStart(); + + const char *orig = s; + // A method/function name may contain a prefix. We don't know it is there, + // however, until we encounter the first '_'. + while (*s != '\0') { + // Skip '_', numbers, ':', etc. + if (*s == '_' || !isalpha(*s)) { + ++s; + continue; + } + break; + } + + if (!ignorePrefix && s != orig) + return NoConvention; + + // Parse the first word, and look for specific keywords. + const char *wordEnd = parseWord(s); + assert(wordEnd > s); + unsigned len = wordEnd - s; + + switch (len) { + default: + return NoConvention; + case 3: + // Methods starting with 'new' follow the create rule. + return (memcmp(s, "new", 3) == 0) ? CreateRule : NoConvention; + case 4: + // Methods starting with 'copy' follow the create rule. + if (memcmp(s, "copy", 4) == 0) + return CreateRule; + // Methods starting with 'init' follow the init rule. + if (memcmp(s, "init", 4) == 0) + return InitRule; + return NoConvention; + case 5: + return (memcmp(s, "alloc", 5) == 0) ? CreateRule : NoConvention; + case 7: + // Methods starting with 'mutableCopy' follow the create rule. + if (memcmp(s, "mutable", 7) == 0) { + // Look at the next word to see if it is "Copy". + s = wordEnd; + if (*s != '\0') { + wordEnd = parseWord(s); + len = wordEnd - s; + if (len == 4 && memcmp(s, "Copy", 4) == 0) + return CreateRule; + } + } + return NoConvention; + } +} + +bool cocoa::isRefType(QualType RetTy, llvm::StringRef Prefix, + llvm::StringRef Name) { + // Recursively walk the typedef stack, allowing typedefs of reference types. + while (const TypedefType *TD = dyn_cast<TypedefType>(RetTy.getTypePtr())) { + llvm::StringRef TDName = TD->getDecl()->getIdentifier()->getName(); + if (TDName.startswith(Prefix) && TDName.endswith("Ref")) + return true; + + RetTy = TD->getDecl()->getUnderlyingType(); + } + + if (Name.empty()) + return false; + + // Is the type void*? + const PointerType* PT = RetTy->getAs<PointerType>(); + if (!(PT->getPointeeType().getUnqualifiedType()->isVoidType())) + return false; + + // Does the name start with the prefix? + return Name.startswith(Prefix); +} + +bool cocoa::isCFObjectRef(QualType T) { + return isRefType(T, "CF") || // Core Foundation. + isRefType(T, "CG") || // Core Graphics. + isRefType(T, "DADisk") || // Disk Arbitration API. + isRefType(T, "DADissenter") || + isRefType(T, "DASessionRef"); +} + + +bool cocoa::isCocoaObjectRef(QualType Ty) { + if (!Ty->isObjCObjectPointerType()) + return false; + + const ObjCObjectPointerType *PT = Ty->getAs<ObjCObjectPointerType>(); + + // Can be true for objects with the 'NSObject' attribute. + if (!PT) + return true; + + // We assume that id<..>, id, Class, and Class<..> all represent tracked + // objects. + if (PT->isObjCIdType() || PT->isObjCQualifiedIdType() || + PT->isObjCClassType() || PT->isObjCQualifiedClassType()) + return true; + + // Does the interface subclass NSObject? + // FIXME: We can memoize here if this gets too expensive. + const ObjCInterfaceDecl *ID = PT->getInterfaceDecl(); + + // Assume that anything declared with a forward declaration and no + // @interface subclasses NSObject. + if (ID->isForwardDecl()) + return true; + + for ( ; ID ; ID = ID->getSuperClass()) + if (ID->getIdentifier()->getName() == "NSObject") + return true; + + return false; +} diff --git a/contrib/llvm/tools/clang/lib/Analysis/FormatString.cpp b/contrib/llvm/tools/clang/lib/Analysis/FormatString.cpp index e57258e..a6d6108 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/FormatString.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/FormatString.cpp @@ -296,8 +296,8 @@ bool ArgTypeResult::matchesType(ASTContext &C, QualType argTy) const { } case CPointerTy: - return argTy->getAs<PointerType>() != NULL || - argTy->getAs<ObjCObjectPointerType>() != NULL; + return argTy->isPointerType() || argTy->isObjCObjectPointerType() || + argTy->isNullPtrType(); case ObjCPointerTy: return argTy->getAs<ObjCObjectPointerType>() != NULL; @@ -423,7 +423,7 @@ bool FormatSpecifier::hasValidLengthModifier() const { case ConversionSpecifier::xArg: case ConversionSpecifier::XArg: case ConversionSpecifier::nArg: - case ConversionSpecifier::rArg: + case ConversionSpecifier::rArg: return true; default: return false; @@ -449,7 +449,7 @@ bool FormatSpecifier::hasValidLengthModifier() const { case ConversionSpecifier::nArg: case ConversionSpecifier::cArg: case ConversionSpecifier::sArg: - case ConversionSpecifier::rArg: + case ConversionSpecifier::rArg: return true; default: return false; diff --git a/contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp b/contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp index 47b2e3d..303dc0f 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp @@ -104,8 +104,9 @@ namespace { class TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{ LiveVariables::AnalysisDataTy& AD; LiveVariables::ValTy LiveState; + const CFGBlock *currentBlock; public: - TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad) {} + TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad), currentBlock(0) {} LiveVariables::ValTy& getVal() { return LiveState; } CFG& getCFG() { return AD.getCFG(); } @@ -128,7 +129,10 @@ public: void SetTopValue(LiveVariables::ValTy& V) { V = AD.AlwaysLive; } - + + void setCurrentBlock(const CFGBlock *block) { + currentBlock = block; + } }; void TransferFuncs::Visit(Stmt *S) { @@ -136,7 +140,7 @@ void TransferFuncs::Visit(Stmt *S) { if (S == getCurrentBlkStmt()) { if (AD.Observer) - AD.Observer->ObserveStmt(S,AD,LiveState); + AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState); if (getCFG().isBlkExpr(S)) LiveState(S, AD) = Dead; @@ -146,7 +150,7 @@ void TransferFuncs::Visit(Stmt *S) { else if (!getCFG().isBlkExpr(S)) { if (AD.Observer) - AD.Observer->ObserveStmt(S,AD,LiveState); + AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState); StmtVisitor<TransferFuncs,void>::Visit(S); diff --git a/contrib/llvm/tools/clang/lib/Analysis/PrintfFormatString.cpp b/contrib/llvm/tools/clang/lib/Analysis/PrintfFormatString.cpp index 1e9601a..ef5c0fb 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/PrintfFormatString.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/PrintfFormatString.cpp @@ -101,6 +101,10 @@ static PrintfSpecifierResult ParsePrintfSpecifier(FormatStringHandler &H, for ( ; I != E; ++I) { switch (*I) { default: hasMore = false; break; + case '\'': + // FIXME: POSIX specific. Always accept? + FS.setHasThousandsGrouping(I); + break; case '-': FS.setIsLeftJustified(I); break; case '+': FS.setHasPlusPrefix(I); break; case ' ': FS.setHasSpacePrefix(I); break; @@ -186,7 +190,7 @@ static PrintfSpecifierResult ParsePrintfSpecifier(FormatStringHandler &H, case 's': k = ConversionSpecifier::sArg; break; case 'u': k = ConversionSpecifier::uArg; break; case 'x': k = ConversionSpecifier::xArg; break; - // Mac OS X (unicode) specific + // POSIX specific. case 'C': k = ConversionSpecifier::CArg; break; case 'S': k = ConversionSpecifier::SArg; break; // Objective-C. @@ -209,7 +213,7 @@ static PrintfSpecifierResult ParsePrintfSpecifier(FormatStringHandler &H, if (k == ConversionSpecifier::InvalidSpecifier) { // Assume the conversion takes one argument. - return !H.HandleInvalidPrintfConversionSpecifier(FS, Beg, I - Beg); + return !H.HandleInvalidPrintfConversionSpecifier(FS, Start, I - Start); } return PrintfSpecifierResult(Start, FS); } @@ -293,7 +297,7 @@ const char *ConversionSpecifier::toString() const { ArgTypeResult PrintfSpecifier::getArgType(ASTContext &Ctx) const { const PrintfConversionSpecifier &CS = getConversionSpecifier(); - + if (!CS.consumesDataArgument()) return ArgTypeResult::Invalid(); @@ -304,7 +308,7 @@ ArgTypeResult PrintfSpecifier::getArgType(ASTContext &Ctx) const { default: return ArgTypeResult::Invalid(); } - + if (CS.isIntArg()) switch (LM.getKind()) { case LengthModifier::AsLongDouble: @@ -398,7 +402,20 @@ bool PrintfSpecifier::fixType(QualType QT) { LM.setKind(LengthModifier::None); break; - case BuiltinType::WChar: + case BuiltinType::Char_U: + case BuiltinType::UChar: + case BuiltinType::Char_S: + case BuiltinType::SChar: + LM.setKind(LengthModifier::AsChar); + break; + + case BuiltinType::Short: + case BuiltinType::UShort: + LM.setKind(LengthModifier::AsShort); + break; + + case BuiltinType::WChar_S: + case BuiltinType::WChar_U: case BuiltinType::Long: case BuiltinType::ULong: LM.setKind(LengthModifier::AsLong); @@ -415,8 +432,10 @@ bool PrintfSpecifier::fixType(QualType QT) { } // Set conversion specifier and disable any flags which do not apply to it. - if (QT->isAnyCharacterType()) { + // Let typedefs to char fall through to int, as %c is silly for uint8_t. + if (isa<TypedefType>(QT) && QT->isAnyCharacterType()) { CS.setKind(ConversionSpecifier::cArg); + LM.setKind(LengthModifier::None); Precision.setHowSpecified(OptionalAmount::NotSpecified); HasAlternativeForm = 0; HasLeadingZeroes = 0; @@ -451,7 +470,7 @@ bool PrintfSpecifier::fixType(QualType QT) { void PrintfSpecifier::toString(llvm::raw_ostream &os) const { // Whilst some features have no defined order, we are using the order - // appearing in the C99 standard (ISO/IEC 9899:1999 (E) ยค7.19.6.1) + // appearing in the C99 standard (ISO/IEC 9899:1999 (E) 7.19.6.1) os << "%"; // Positional args @@ -504,10 +523,11 @@ bool PrintfSpecifier::hasValidAlternativeForm() const { if (!HasAlternativeForm) return true; - // Alternate form flag only valid with the oxaAeEfFgG conversions + // Alternate form flag only valid with the oxXaAeEfFgG conversions switch (CS.getKind()) { case ConversionSpecifier::oArg: case ConversionSpecifier::xArg: + case ConversionSpecifier::XArg: case ConversionSpecifier::aArg: case ConversionSpecifier::AArg: case ConversionSpecifier::eArg: @@ -588,6 +608,24 @@ bool PrintfSpecifier::hasValidLeftJustified() const { } } +bool PrintfSpecifier::hasValidThousandsGroupingPrefix() const { + if (!HasThousandsGrouping) + return true; + + switch (CS.getKind()) { + case ConversionSpecifier::dArg: + case ConversionSpecifier::iArg: + case ConversionSpecifier::uArg: + case ConversionSpecifier::fArg: + case ConversionSpecifier::FArg: + case ConversionSpecifier::gArg: + case ConversionSpecifier::GArg: + return true; + default: + return false; + } +} + bool PrintfSpecifier::hasValidPrecision() const { if (Precision.getHowSpecified() == OptionalAmount::NotSpecified) return true; diff --git a/contrib/llvm/tools/clang/lib/Analysis/PseudoConstantAnalysis.cpp b/contrib/llvm/tools/clang/lib/Analysis/PseudoConstantAnalysis.cpp index ff43fc2..ff96eb4 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/PseudoConstantAnalysis.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/PseudoConstantAnalysis.cpp @@ -86,6 +86,9 @@ void PseudoConstantAnalysis::RunAnalysis() { const Stmt* Head = WorkList.front(); WorkList.pop_front(); + if (const Expr *Ex = dyn_cast<Expr>(Head)) + Head = Ex->IgnoreParenCasts(); + switch (Head->getStmtClass()) { // Case 1: Assignment operators modifying VarDecls case Stmt::BinaryOperatorClass: { @@ -225,13 +228,12 @@ void PseudoConstantAnalysis::RunAnalysis() { continue; } - default: - break; + default: + break; } // switch (head->getStmtClass()) // Add all substatements to the worklist - for (Stmt::const_child_iterator I = Head->child_begin(), - E = Head->child_end(); I != E; ++I) + for (Stmt::const_child_range I = Head->children(); I; ++I) if (*I) WorkList.push_back(*I); } // while (!WorkList.empty()) diff --git a/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp b/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp index 0543939..7afa586 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp @@ -30,20 +30,26 @@ static SourceLocation GetUnreachableLoc(const CFGBlock &b, SourceRange &R1, unsigned sn = 0; R1 = R2 = SourceRange(); -top: - if (sn < b.size()) - S = b[sn].getStmt(); - else if (b.getTerminator()) + if (sn < b.size()) { + CFGStmt CS = b[sn].getAs<CFGStmt>(); + if (!CS) + return SourceLocation(); + + S = CS.getStmt(); + } else if (b.getTerminator()) S = b.getTerminator(); else return SourceLocation(); + if (const Expr *Ex = dyn_cast<Expr>(S)) + S = Ex->IgnoreParenImpCasts(); + switch (S->getStmtClass()) { case Expr::BinaryOperatorClass: { const BinaryOperator *BO = cast<BinaryOperator>(S); if (BO->getOpcode() == BO_Comma) { if (sn+1 < b.size()) - return b[sn+1].getStmt()->getLocStart(); + return b[sn+1].getAs<CFGStmt>().getStmt()->getLocStart(); const CFGBlock *n = &b; while (1) { if (n->getTerminator()) @@ -54,7 +60,7 @@ top: if (n->pred_size() != 1) return SourceLocation(); if (!n->empty()) - return n[0][0].getStmt()->getLocStart(); + return n[0][0].getAs<CFGStmt>().getStmt()->getLocStart(); } } R1 = BO->getLHS()->getSourceRange(); @@ -72,8 +78,10 @@ top: R2 = CAO->getRHS()->getSourceRange(); return CAO->getOperatorLoc(); } + case Expr::BinaryConditionalOperatorClass: case Expr::ConditionalOperatorClass: { - const ConditionalOperator *CO = cast<ConditionalOperator>(S); + const AbstractConditionalOperator *CO = + cast<AbstractConditionalOperator>(S); return CO->getQuestionLoc(); } case Expr::MemberExprClass: { @@ -97,9 +105,6 @@ top: R1 = CE->getSubExpr()->getSourceRange(); return CE->getTypeBeginLoc(); } - case Expr::ImplicitCastExprClass: - ++sn; - goto top; case Stmt::CXXTryStmtClass: { return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc(); } @@ -131,6 +136,9 @@ static SourceLocation MarkLiveTop(const CFGBlock *Start, } // Solve + CFGBlock::FilterOptions FO; + FO.IgnoreDefaultsWithCoveredEnums = 1; + while (!WL.empty()) { const CFGBlock *item = WL.back(); WL.pop_back(); @@ -147,8 +155,8 @@ static SourceLocation MarkLiveTop(const CFGBlock *Start, } reachable.set(item->getBlockID()); - for (CFGBlock::const_succ_iterator I=item->succ_begin(), E=item->succ_end(); - I != E; ++I) + for (CFGBlock::filtered_succ_iterator I = + item->filtered_succ_start_end(FO); I.hasMore(); ++I) if (const CFGBlock *B = *I) { unsigned blockID = B->getBlockID(); if (!reachable[blockID]) { @@ -190,14 +198,17 @@ unsigned ScanReachableFromBlock(const CFGBlock &Start, ++count; WL.push_back(&Start); - // Find the reachable blocks from 'Start'. + // Find the reachable blocks from 'Start'. + CFGBlock::FilterOptions FO; + FO.IgnoreDefaultsWithCoveredEnums = 1; + while (!WL.empty()) { const CFGBlock *item = WL.back(); WL.pop_back(); // Look at the successors and mark then reachable. - for (CFGBlock::const_succ_iterator I=item->succ_begin(), E=item->succ_end(); - I != E; ++I) + for (CFGBlock::filtered_succ_iterator I= item->filtered_succ_start_end(FO); + I.hasMore(); ++I) if (const CFGBlock *B = *I) { unsigned blockID = B->getBlockID(); if (!Reachable[blockID]) { @@ -234,7 +245,8 @@ void FindUnreachableCode(AnalysisContext &AC, Callback &CB) { CFGBlock &b = **I; if (!reachable[b.getBlockID()]) { if (b.pred_empty()) { - if (!AddEHEdges && dyn_cast_or_null<CXXTryStmt>(b.getTerminator())) { + if (!AddEHEdges + && dyn_cast_or_null<CXXTryStmt>(b.getTerminator().getStmt())) { // When not adding EH edges from calls, catch clauses // can otherwise seem dead. Avoid noting them as dead. numReachable += ScanReachableFromBlock(b, reachable); diff --git a/contrib/llvm/tools/clang/lib/Analysis/UninitializedValues.cpp b/contrib/llvm/tools/clang/lib/Analysis/UninitializedValues.cpp index 0f43efa..c08cbed 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/UninitializedValues.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/UninitializedValues.cpp @@ -72,13 +72,15 @@ public: bool VisitStmt(Stmt* S); bool VisitCallExpr(CallExpr* C); bool VisitDeclStmt(DeclStmt* D); - bool VisitConditionalOperator(ConditionalOperator* C); + bool VisitAbstractConditionalOperator(AbstractConditionalOperator* C); bool BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S); bool Visit(Stmt *S); bool BlockStmt_VisitExpr(Expr* E); void VisitTerminator(CFGBlock* B) { } + + void setCurrentBlock(const CFGBlock *block) {} }; static const bool Initialized = false; @@ -87,7 +89,7 @@ static const bool Uninitialized = true; bool TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) { if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) - if (VD->isBlockVarDecl()) { + if (VD->isLocalVarDecl()) { if (AD.Observer) AD.Observer->ObserveDeclRefExpr(V, AD, DR, VD); @@ -112,7 +114,7 @@ static VarDecl* FindBlockVarDecl(Expr* E) { if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParenCasts())) if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) - if (VD->isBlockVarDecl()) return VD; + if (VD->isLocalVarDecl()) return VD; return NULL; } @@ -133,7 +135,7 @@ bool TransferFuncs::VisitBinaryOperator(BinaryOperator* B) { bool TransferFuncs::VisitDeclStmt(DeclStmt* S) { for (DeclStmt::decl_iterator I=S->decl_begin(), E=S->decl_end(); I!=E; ++I) { VarDecl *VD = dyn_cast<VarDecl>(*I); - if (VD && VD->isBlockVarDecl()) { + if (VD && VD->isLocalVarDecl()) { if (Stmt* I = VD->getInit()) { // Visit the subexpression to check for uses of uninitialized values, // even if we don't propagate that value. @@ -170,7 +172,7 @@ bool TransferFuncs::VisitUnaryOperator(UnaryOperator* U) { switch (U->getOpcode()) { case UO_AddrOf: { VarDecl* VD = FindBlockVarDecl(U->getSubExpr()); - if (VD && VD->isBlockVarDecl()) + if (VD && VD->isLocalVarDecl()) return V(VD,AD) = Initialized; break; } @@ -211,13 +213,14 @@ TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { } -bool TransferFuncs::VisitConditionalOperator(ConditionalOperator* C) { +bool TransferFuncs:: +VisitAbstractConditionalOperator(AbstractConditionalOperator* C) { Visit(C->getCond()); - bool rhsResult = Visit(C->getRHS()); + bool rhsResult = Visit(C->getFalseExpr()); // Handle the GNU extension for missing LHS. - if (Expr *lhs = C->getLHS()) - return Visit(lhs) & rhsResult; // Yes: we want &, not &&. + if (isa<ConditionalOperator>(C)) + return Visit(C->getTrueExpr()) & rhsResult; // Yes: we want &, not &&. else return rhsResult; } @@ -228,7 +231,7 @@ bool TransferFuncs::VisitStmt(Stmt* S) { // We don't stop at the first subexpression that is Uninitialized because // evaluating some subexpressions may result in propogating "Uninitialized" // or "Initialized" to variables referenced in the other subexpressions. - for (Stmt::child_iterator I=S->child_begin(), E=S->child_end(); I!=E; ++I) + for (Stmt::child_range I = S->children(); I; ++I) if (*I && Visit(*I) == Uninitialized) x = Uninitialized; return x; diff --git a/contrib/llvm/tools/clang/lib/Analysis/UninitializedValuesV2.cpp b/contrib/llvm/tools/clang/lib/Analysis/UninitializedValuesV2.cpp new file mode 100644 index 0000000..75eccbf --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/UninitializedValuesV2.cpp @@ -0,0 +1,610 @@ +//==- UninitializedValuesV2.cpp - Find Uninitialized Values -----*- C++ --*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements uninitialized values analysis for source-level CFGs. +// +//===----------------------------------------------------------------------===// + +#include <utility> +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "clang/AST/Decl.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" +#include "clang/Analysis/Analyses/UninitializedValuesV2.h" +#include "clang/Analysis/Support/SaveAndRestore.h" + +using namespace clang; + +static bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { + return vd->isLocalVarDecl() && !vd->hasGlobalStorage() && + vd->getType()->isScalarType() && + vd->getDeclContext() == dc; +} + +//------------------------------------------------------------------------====// +// DeclToBit: a mapping from Decls we track to bitvector indices. +//====------------------------------------------------------------------------// + +namespace { +class DeclToBit { + llvm::DenseMap<const VarDecl *, unsigned> map; +public: + DeclToBit() {} + + /// Compute the actual mapping from declarations to bits. + void computeMap(const DeclContext &dc); + + /// Return the number of declarations in the map. + unsigned size() const { return map.size(); } + + /// Returns the bit vector index for a given declaration. + llvm::Optional<unsigned> getBitVectorIndex(const VarDecl *d); +}; +} + +void DeclToBit::computeMap(const DeclContext &dc) { + unsigned count = 0; + DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()), + E(dc.decls_end()); + for ( ; I != E; ++I) { + const VarDecl *vd = *I; + if (isTrackedVar(vd, &dc)) + map[vd] = count++; + } +} + +llvm::Optional<unsigned> DeclToBit::getBitVectorIndex(const VarDecl *d) { + llvm::DenseMap<const VarDecl *, unsigned>::iterator I = map.find(d); + if (I == map.end()) + return llvm::Optional<unsigned>(); + return I->second; +} + +//------------------------------------------------------------------------====// +// CFGBlockValues: dataflow values for CFG blocks. +//====------------------------------------------------------------------------// + +typedef std::pair<llvm::BitVector *, llvm::BitVector *> BVPair; + +namespace { +class CFGBlockValues { + const CFG &cfg; + BVPair *vals; + llvm::BitVector scratch; + DeclToBit declToBit; + + llvm::BitVector &lazyCreate(llvm::BitVector *&bv); +public: + CFGBlockValues(const CFG &cfg); + ~CFGBlockValues(); + + void computeSetOfDeclarations(const DeclContext &dc); + llvm::BitVector &getBitVector(const CFGBlock *block, + const CFGBlock *dstBlock); + + BVPair &getBitVectors(const CFGBlock *block, bool shouldLazyCreate); + + void mergeIntoScratch(llvm::BitVector const &source, bool isFirst); + bool updateBitVectorWithScratch(const CFGBlock *block); + bool updateBitVectors(const CFGBlock *block, const BVPair &newVals); + + bool hasNoDeclarations() const { + return declToBit.size() == 0; + } + + void resetScratch(); + llvm::BitVector &getScratch() { return scratch; } + + llvm::BitVector::reference operator[](const VarDecl *vd); +}; +} + +CFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) { + unsigned n = cfg.getNumBlockIDs(); + if (!n) + return; + vals = new std::pair<llvm::BitVector*, llvm::BitVector*>[n]; + memset(vals, 0, sizeof(*vals) * n); +} + +CFGBlockValues::~CFGBlockValues() { + unsigned n = cfg.getNumBlockIDs(); + if (n == 0) + return; + for (unsigned i = 0; i < n; ++i) { + delete vals[i].first; + delete vals[i].second; + } + delete [] vals; +} + +void CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { + declToBit.computeMap(dc); + scratch.resize(declToBit.size()); +} + +llvm::BitVector &CFGBlockValues::lazyCreate(llvm::BitVector *&bv) { + if (!bv) + bv = new llvm::BitVector(declToBit.size()); + return *bv; +} + +/// This function pattern matches for a '&&' or '||' that appears at +/// the beginning of a CFGBlock that also (1) has a terminator and +/// (2) has no other elements. If such an expression is found, it is returned. +static BinaryOperator *getLogicalOperatorInChain(const CFGBlock *block) { + if (block->empty()) + return 0; + + CFGStmt cstmt = block->front().getAs<CFGStmt>(); + BinaryOperator *b = llvm::dyn_cast_or_null<BinaryOperator>(cstmt.getStmt()); + + if (!b || !b->isLogicalOp()) + return 0; + + if (block->pred_size() == 2 && + ((block->succ_size() == 2 && block->getTerminatorCondition() == b) || + block->size() == 1)) + return b; + + return 0; +} + +llvm::BitVector &CFGBlockValues::getBitVector(const CFGBlock *block, + const CFGBlock *dstBlock) { + unsigned idx = block->getBlockID(); + if (dstBlock && getLogicalOperatorInChain(block)) { + if (*block->succ_begin() == dstBlock) + return lazyCreate(vals[idx].first); + assert(*(block->succ_begin()+1) == dstBlock); + return lazyCreate(vals[idx].second); + } + + assert(vals[idx].second == 0); + return lazyCreate(vals[idx].first); +} + +BVPair &CFGBlockValues::getBitVectors(const clang::CFGBlock *block, + bool shouldLazyCreate) { + unsigned idx = block->getBlockID(); + lazyCreate(vals[idx].first); + if (shouldLazyCreate) + lazyCreate(vals[idx].second); + return vals[idx]; +} + +void CFGBlockValues::mergeIntoScratch(llvm::BitVector const &source, + bool isFirst) { + if (isFirst) + scratch = source; + else + scratch |= source; +} +#if 0 +static void printVector(const CFGBlock *block, llvm::BitVector &bv, + unsigned num) { + + llvm::errs() << block->getBlockID() << " :"; + for (unsigned i = 0; i < bv.size(); ++i) { + llvm::errs() << ' ' << bv[i]; + } + llvm::errs() << " : " << num << '\n'; +} +#endif + +bool CFGBlockValues::updateBitVectorWithScratch(const CFGBlock *block) { + llvm::BitVector &dst = getBitVector(block, 0); + bool changed = (dst != scratch); + if (changed) + dst = scratch; +#if 0 + printVector(block, scratch, 0); +#endif + return changed; +} + +bool CFGBlockValues::updateBitVectors(const CFGBlock *block, + const BVPair &newVals) { + BVPair &vals = getBitVectors(block, true); + bool changed = *newVals.first != *vals.first || + *newVals.second != *vals.second; + *vals.first = *newVals.first; + *vals.second = *newVals.second; +#if 0 + printVector(block, *vals.first, 1); + printVector(block, *vals.second, 2); +#endif + return changed; +} + +void CFGBlockValues::resetScratch() { + scratch.reset(); +} + +llvm::BitVector::reference CFGBlockValues::operator[](const VarDecl *vd) { + const llvm::Optional<unsigned> &idx = declToBit.getBitVectorIndex(vd); + assert(idx.hasValue()); + return scratch[idx.getValue()]; +} + +//------------------------------------------------------------------------====// +// Worklist: worklist for dataflow analysis. +//====------------------------------------------------------------------------// + +namespace { +class DataflowWorklist { + llvm::SmallVector<const CFGBlock *, 20> worklist; + llvm::BitVector enqueuedBlocks; +public: + DataflowWorklist(const CFG &cfg) : enqueuedBlocks(cfg.getNumBlockIDs()) {} + + void enqueue(const CFGBlock *block); + void enqueueSuccessors(const CFGBlock *block); + const CFGBlock *dequeue(); + +}; +} + +void DataflowWorklist::enqueue(const CFGBlock *block) { + if (!block) + return; + unsigned idx = block->getBlockID(); + if (enqueuedBlocks[idx]) + return; + worklist.push_back(block); + enqueuedBlocks[idx] = true; +} + +void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { + for (CFGBlock::const_succ_iterator I = block->succ_begin(), + E = block->succ_end(); I != E; ++I) { + enqueue(*I); + } +} + +const CFGBlock *DataflowWorklist::dequeue() { + if (worklist.empty()) + return 0; + const CFGBlock *b = worklist.back(); + worklist.pop_back(); + enqueuedBlocks[b->getBlockID()] = false; + return b; +} + +//------------------------------------------------------------------------====// +// Transfer function for uninitialized values analysis. +//====------------------------------------------------------------------------// + +static const bool Initialized = false; +static const bool Uninitialized = true; + +namespace { +class FindVarResult { + const VarDecl *vd; + const DeclRefExpr *dr; +public: + FindVarResult(VarDecl *vd, DeclRefExpr *dr) : vd(vd), dr(dr) {} + + const DeclRefExpr *getDeclRefExpr() const { return dr; } + const VarDecl *getDecl() const { return vd; } +}; + +class TransferFunctions : public CFGRecStmtVisitor<TransferFunctions> { + CFGBlockValues &vals; + const CFG &cfg; + AnalysisContext ∾ + UninitVariablesHandler *handler; + const DeclRefExpr *currentDR; + const Expr *currentVoidCast; + const bool flagBlockUses; +public: + TransferFunctions(CFGBlockValues &vals, const CFG &cfg, + AnalysisContext &ac, + UninitVariablesHandler *handler, + bool flagBlockUses) + : vals(vals), cfg(cfg), ac(ac), handler(handler), currentDR(0), + currentVoidCast(0), flagBlockUses(flagBlockUses) {} + + const CFG &getCFG() { return cfg; } + void reportUninit(const DeclRefExpr *ex, const VarDecl *vd); + + void VisitBlockExpr(BlockExpr *be); + void VisitDeclStmt(DeclStmt *ds); + void VisitDeclRefExpr(DeclRefExpr *dr); + void VisitUnaryOperator(UnaryOperator *uo); + void VisitBinaryOperator(BinaryOperator *bo); + void VisitCastExpr(CastExpr *ce); + void VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *se); + void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt *fs); + + bool isTrackedVar(const VarDecl *vd) { + return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl())); + } + + FindVarResult findBlockVarDecl(Expr *ex); +}; +} + +void TransferFunctions::reportUninit(const DeclRefExpr *ex, + const VarDecl *vd) { + if (handler) handler->handleUseOfUninitVariable(ex, vd); +} + +FindVarResult TransferFunctions::findBlockVarDecl(Expr* ex) { + if (DeclRefExpr* dr = dyn_cast<DeclRefExpr>(ex->IgnoreParenCasts())) + if (VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl())) + if (isTrackedVar(vd)) + return FindVarResult(vd, dr); + return FindVarResult(0, 0); +} + +void TransferFunctions::BlockStmt_VisitObjCForCollectionStmt( + ObjCForCollectionStmt *fs) { + + Visit(fs->getCollection()); + + // This represents an initialization of the 'element' value. + Stmt *element = fs->getElement(); + const VarDecl* vd = 0; + + if (DeclStmt* ds = dyn_cast<DeclStmt>(element)) { + vd = cast<VarDecl>(ds->getSingleDecl()); + if (!isTrackedVar(vd)) + vd = 0; + } + else { + // Initialize the value of the reference variable. + const FindVarResult &res = findBlockVarDecl(cast<Expr>(element)); + vd = res.getDecl(); + if (!vd) { + Visit(element); + return; + } + } + + if (vd) + vals[vd] = Initialized; +} + +void TransferFunctions::VisitBlockExpr(BlockExpr *be) { + if (!flagBlockUses || !handler) + return; + AnalysisContext::referenced_decls_iterator i, e; + llvm::tie(i, e) = ac.getReferencedBlockVars(be->getBlockDecl()); + for ( ; i != e; ++i) { + const VarDecl *vd = *i; + if (vd->getAttr<BlocksAttr>() || !vd->hasLocalStorage() || + !isTrackedVar(vd)) + continue; + if (vals[vd] == Uninitialized) + handler->handleUseOfUninitVariable(be, vd); + } +} + +void TransferFunctions::VisitDeclStmt(DeclStmt *ds) { + for (DeclStmt::decl_iterator DI = ds->decl_begin(), DE = ds->decl_end(); + DI != DE; ++DI) { + if (VarDecl *vd = dyn_cast<VarDecl>(*DI)) { + if (isTrackedVar(vd)) { + vals[vd] = Uninitialized; + if (Stmt *init = vd->getInit()) { + Visit(init); + vals[vd] = Initialized; + } + } + else if (Stmt *init = vd->getInit()) { + Visit(init); + } + } + } +} + +void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { + // We assume that DeclRefExprs wrapped in an lvalue-to-rvalue cast + // cannot be block-level expressions. Therefore, we determine if + // a DeclRefExpr is involved in a "load" by comparing it to the current + // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. + // If a DeclRefExpr is not involved in a load, we are essentially computing + // its address, either for assignment to a reference or via the '&' operator. + // In such cases, treat the variable as being initialized, since this + // analysis isn't powerful enough to do alias tracking. + if (dr != currentDR) + if (const VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl())) + if (isTrackedVar(vd)) + vals[vd] = Initialized; +} + +void TransferFunctions::VisitBinaryOperator(clang::BinaryOperator *bo) { + if (bo->isAssignmentOp()) { + const FindVarResult &res = findBlockVarDecl(bo->getLHS()); + if (const VarDecl* vd = res.getDecl()) { + // We assume that DeclRefExprs wrapped in a BinaryOperator "assignment" + // cannot be block-level expressions. Therefore, we determine if + // a DeclRefExpr is involved in a "load" by comparing it to the current + // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. + SaveAndRestore<const DeclRefExpr*> lastDR(currentDR, + res.getDeclRefExpr()); + Visit(bo->getRHS()); + Visit(bo->getLHS()); + + llvm::BitVector::reference bit = vals[vd]; + if (bit == Uninitialized) { + if (bo->getOpcode() != BO_Assign) + reportUninit(res.getDeclRefExpr(), vd); + bit = Initialized; + } + return; + } + } + Visit(bo->getRHS()); + Visit(bo->getLHS()); +} + +void TransferFunctions::VisitUnaryOperator(clang::UnaryOperator *uo) { + switch (uo->getOpcode()) { + case clang::UO_PostDec: + case clang::UO_PostInc: + case clang::UO_PreDec: + case clang::UO_PreInc: { + const FindVarResult &res = findBlockVarDecl(uo->getSubExpr()); + if (const VarDecl *vd = res.getDecl()) { + // We assume that DeclRefExprs wrapped in a unary operator ++/-- + // cannot be block-level expressions. Therefore, we determine if + // a DeclRefExpr is involved in a "load" by comparing it to the current + // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. + SaveAndRestore<const DeclRefExpr*> lastDR(currentDR, + res.getDeclRefExpr()); + Visit(uo->getSubExpr()); + + llvm::BitVector::reference bit = vals[vd]; + if (bit == Uninitialized) { + reportUninit(res.getDeclRefExpr(), vd); + bit = Initialized; + } + return; + } + break; + } + default: + break; + } + Visit(uo->getSubExpr()); +} + +void TransferFunctions::VisitCastExpr(clang::CastExpr *ce) { + if (ce->getCastKind() == CK_LValueToRValue) { + const FindVarResult &res = findBlockVarDecl(ce->getSubExpr()); + if (const VarDecl *vd = res.getDecl()) { + // We assume that DeclRefExprs wrapped in an lvalue-to-rvalue cast + // cannot be block-level expressions. Therefore, we determine if + // a DeclRefExpr is involved in a "load" by comparing it to the current + // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. + // Here we update 'currentDR' to be the one associated with this + // lvalue-to-rvalue cast. Then, when we analyze the DeclRefExpr, we + // will know that we are not computing its lvalue for other purposes + // than to perform a load. + SaveAndRestore<const DeclRefExpr*> lastDR(currentDR, + res.getDeclRefExpr()); + Visit(ce->getSubExpr()); + if (currentVoidCast != ce && vals[vd] == Uninitialized) { + reportUninit(res.getDeclRefExpr(), vd); + // Don't cascade warnings. + vals[vd] = Initialized; + } + return; + } + } + else if (CStyleCastExpr *cse = dyn_cast<CStyleCastExpr>(ce)) { + if (cse->getType()->isVoidType()) { + // e.g. (void) x; + SaveAndRestore<const Expr *> + lastVoidCast(currentVoidCast, cse->getSubExpr()->IgnoreParens()); + Visit(cse->getSubExpr()); + return; + } + } + Visit(ce->getSubExpr()); +} + +void TransferFunctions::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *se) { + if (se->isSizeOf()) { + if (se->getType()->isConstantSizeType()) + return; + // Handle VLAs. + Visit(se->getArgumentExpr()); + } +} + +//------------------------------------------------------------------------====// +// High-level "driver" logic for uninitialized values analysis. +//====------------------------------------------------------------------------// + +static bool runOnBlock(const CFGBlock *block, const CFG &cfg, + AnalysisContext &ac, CFGBlockValues &vals, + UninitVariablesHandler *handler = 0, + bool flagBlockUses = false) { + + if (const BinaryOperator *b = getLogicalOperatorInChain(block)) { + CFGBlock::const_pred_iterator itr = block->pred_begin(); + BVPair vA = vals.getBitVectors(*itr, false); + ++itr; + BVPair vB = vals.getBitVectors(*itr, false); + + BVPair valsAB; + + if (b->getOpcode() == BO_LAnd) { + // Merge the 'F' bits from the first and second. + vals.mergeIntoScratch(*(vA.second ? vA.second : vA.first), true); + vals.mergeIntoScratch(*(vB.second ? vB.second : vB.first), false); + valsAB.first = vA.first; + valsAB.second = &vals.getScratch(); + } + else { + // Merge the 'T' bits from the first and second. + assert(b->getOpcode() == BO_LOr); + vals.mergeIntoScratch(*vA.first, true); + vals.mergeIntoScratch(*vB.first, false); + valsAB.first = &vals.getScratch(); + valsAB.second = vA.second ? vA.second : vA.first; + } + return vals.updateBitVectors(block, valsAB); + } + + // Default behavior: merge in values of predecessor blocks. + vals.resetScratch(); + bool isFirst = true; + for (CFGBlock::const_pred_iterator I = block->pred_begin(), + E = block->pred_end(); I != E; ++I) { + vals.mergeIntoScratch(vals.getBitVector(*I, block), isFirst); + isFirst = false; + } + // Apply the transfer function. + TransferFunctions tf(vals, cfg, ac, handler, flagBlockUses); + for (CFGBlock::const_iterator I = block->begin(), E = block->end(); + I != E; ++I) { + if (const CFGStmt *cs = dyn_cast<CFGStmt>(&*I)) { + tf.BlockStmt_Visit(cs->getStmt()); + } + } + return vals.updateBitVectorWithScratch(block); +} + +void clang::runUninitializedVariablesAnalysis(const DeclContext &dc, + const CFG &cfg, + AnalysisContext &ac, + UninitVariablesHandler &handler) { + CFGBlockValues vals(cfg); + vals.computeSetOfDeclarations(dc); + if (vals.hasNoDeclarations()) + return; + DataflowWorklist worklist(cfg); + llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); + + worklist.enqueueSuccessors(&cfg.getEntry()); + + while (const CFGBlock *block = worklist.dequeue()) { + // Did the block change? + bool changed = runOnBlock(block, cfg, ac, vals); + if (changed || !previouslyVisited[block->getBlockID()]) + worklist.enqueueSuccessors(block); + previouslyVisited[block->getBlockID()] = true; + } + + // Run through the blocks one more time, and report uninitialized variabes. + for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { + runOnBlock(*BI, cfg, ac, vals, &handler, /* flagBlockUses */ true); + } +} + +UninitVariablesHandler::~UninitVariablesHandler() {} + |
