diff options
Diffstat (limited to 'lib/Analysis')
| -rw-r--r-- | lib/Analysis/AnalysisContext.cpp | 118 | ||||
| -rw-r--r-- | lib/Analysis/CFG.cpp | 652 | ||||
| -rw-r--r-- | lib/Analysis/CFGReachabilityAnalysis.cpp | 6 | ||||
| -rw-r--r-- | lib/Analysis/CFGStmtMap.cpp | 6 | ||||
| -rw-r--r-- | lib/Analysis/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | lib/Analysis/CocoaConventions.cpp | 92 | ||||
| -rw-r--r-- | lib/Analysis/PrintfFormatString.cpp | 43 | ||||
| -rw-r--r-- | lib/Analysis/ReachableCode.cpp | 10 | ||||
| -rw-r--r-- | lib/Analysis/UninitializedValues.cpp | 874 | ||||
| -rw-r--r-- | lib/Analysis/UninitializedValuesV2.cpp | 610 |
10 files changed, 1237 insertions, 1175 deletions
diff --git a/lib/Analysis/AnalysisContext.cpp b/lib/Analysis/AnalysisContext.cpp index 62097ef20dd9..ddc5e887031b 100644 --- a/lib/Analysis/AnalysisContext.cpp +++ b/lib/Analysis/AnalysisContext.cpp @@ -29,6 +29,24 @@ using namespace clang; +AnalysisContext::AnalysisContext(const Decl *d, + idx::TranslationUnit *tu, + bool useUnoptimizedCFG, + bool addehedges, + bool addImplicitDtors, + bool addInitializers) + : D(d), TU(tu), + forcedBlkExprs(0), + builtCFG(false), builtCompleteCFG(false), + useUnoptimizedCFG(useUnoptimizedCFG), + ReferencedBlockVars(0) +{ + cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs; + cfgBuildOptions.AddEHEdges = addehedges; + cfgBuildOptions.AddImplicitDtors = addImplicitDtors; + cfgBuildOptions.AddInitializers = addInitializers; +} + void AnalysisContextManager::clear() { for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) delete I->second; @@ -56,57 +74,71 @@ const ImplicitParamDecl *AnalysisContext::getSelfDecl() const { return NULL; } +void AnalysisContext::registerForcedBlockExpression(const Stmt *stmt) { + if (!forcedBlkExprs) + forcedBlkExprs = new CFG::BuildOptions::ForcedBlkExprs(); + // Default construct an entry for 'stmt'. + if (const ParenExpr *pe = dyn_cast<ParenExpr>(stmt)) + stmt = pe->IgnoreParens(); + (void) (*forcedBlkExprs)[stmt]; +} + +const CFGBlock * +AnalysisContext::getBlockForRegisteredExpression(const Stmt *stmt) { + assert(forcedBlkExprs); + if (const ParenExpr *pe = dyn_cast<ParenExpr>(stmt)) + stmt = pe->IgnoreParens(); + CFG::BuildOptions::ForcedBlkExprs::const_iterator itr = + forcedBlkExprs->find(stmt); + assert(itr != forcedBlkExprs->end()); + return itr->second; +} + CFG *AnalysisContext::getCFG() { - if (UseUnoptimizedCFG) + if (useUnoptimizedCFG) return getUnoptimizedCFG(); if (!builtCFG) { - CFG::BuildOptions B; - B.AddEHEdges = AddEHEdges; - B.AddImplicitDtors = AddImplicitDtors; - B.AddInitializers = AddInitializers; - cfg = CFG::buildCFG(D, getBody(), &D->getASTContext(), B); + cfg.reset(CFG::buildCFG(D, getBody(), + &D->getASTContext(), cfgBuildOptions)); // Even when the cfg is not successfully built, we don't // want to try building it again. builtCFG = true; } - return cfg; + return cfg.get(); } CFG *AnalysisContext::getUnoptimizedCFG() { if (!builtCompleteCFG) { - CFG::BuildOptions B; + CFG::BuildOptions B = cfgBuildOptions; B.PruneTriviallyFalseEdges = false; - B.AddEHEdges = AddEHEdges; - B.AddImplicitDtors = AddImplicitDtors; - B.AddInitializers = AddInitializers; - completeCFG = CFG::buildCFG(D, getBody(), &D->getASTContext(), B); + completeCFG.reset(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; } - return completeCFG; + return completeCFG.get(); } CFGStmtMap *AnalysisContext::getCFGStmtMap() { if (cfgStmtMap) - return cfgStmtMap; + return cfgStmtMap.get(); if (CFG *c = getCFG()) { - cfgStmtMap = CFGStmtMap::Build(c, &getParentMap()); - return cfgStmtMap; + cfgStmtMap.reset(CFGStmtMap::Build(c, &getParentMap())); + return cfgStmtMap.get(); } return 0; } -CFGReachabilityAnalysis *AnalysisContext::getCFGReachablityAnalysis() { +CFGReverseBlockReachabilityAnalysis *AnalysisContext::getCFGReachablityAnalysis() { if (CFA) - return CFA; + return CFA.get(); if (CFG *c = getCFG()) { - CFA = new CFGReachabilityAnalysis(*c); - return CFA; + CFA.reset(new CFGReverseBlockReachabilityAnalysis(*c)); + return CFA.get(); } return 0; @@ -118,42 +150,37 @@ void AnalysisContext::dumpCFG() { ParentMap &AnalysisContext::getParentMap() { if (!PM) - PM = new ParentMap(getBody()); + PM.reset(new ParentMap(getBody())); return *PM; } PseudoConstantAnalysis *AnalysisContext::getPseudoConstantAnalysis() { if (!PCA) - PCA = new PseudoConstantAnalysis(getBody()); - return PCA; + PCA.reset(new PseudoConstantAnalysis(getBody())); + return PCA.get(); } LiveVariables *AnalysisContext::getLiveVariables() { if (!liveness) { - CFG *c = getCFG(); - if (!c) - return 0; - - liveness = new LiveVariables(*this); - liveness->runOnCFG(*c); - liveness->runOnAllBlocks(*c, 0, true); + if (CFG *c = getCFG()) { + liveness.reset(new LiveVariables(*this)); + liveness->runOnCFG(*c); + liveness->runOnAllBlocks(*c, 0, true); + } } - return liveness; + return liveness.get(); } LiveVariables *AnalysisContext::getRelaxedLiveVariables() { - if (!relaxedLiveness) { - CFG *c = getCFG(); - if (!c) - return 0; - - relaxedLiveness = new LiveVariables(*this, false); - relaxedLiveness->runOnCFG(*c); - relaxedLiveness->runOnAllBlocks(*c, 0, true); - } + if (!relaxedLiveness) + if (CFG *c = getCFG()) { + relaxedLiveness.reset(new LiveVariables(*this, false)); + relaxedLiveness->runOnCFG(*c); + relaxedLiveness->runOnAllBlocks(*c, 0, true); + } - return relaxedLiveness; + return relaxedLiveness.get(); } AnalysisContext *AnalysisContextManager::getContext(const Decl *D, @@ -370,14 +397,7 @@ AnalysisContext::getReferencedBlockVars(const BlockDecl *BD) { //===----------------------------------------------------------------------===// AnalysisContext::~AnalysisContext() { - delete cfg; - delete completeCFG; - delete cfgStmtMap; - delete liveness; - delete relaxedLiveness; - delete PM; - delete PCA; - delete CFA; + delete forcedBlkExprs; delete ReferencedBlockVars; } diff --git a/lib/Analysis/CFG.cpp b/lib/Analysis/CFG.cpp index cc6e9c592a1e..de16334ce137 100644 --- a/lib/Analysis/CFG.cpp +++ b/lib/Analysis/CFG.cpp @@ -36,6 +36,8 @@ static SourceLocation GetEndLoc(Decl* D) { return D->getLocation(); } +class CFGBuilder; + /// 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: @@ -55,13 +57,13 @@ public: AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {} - bool alwaysAdd() const { return kind & AlwaysAdd; } + bool alwaysAdd(CFGBuilder &builder, + const Stmt *stmt) const; /// 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)); + return AddStmtChoice(alwaysAdd ? AlwaysAdd : NotAlwaysAdd); } private: @@ -210,6 +212,25 @@ struct BlockScopePosPair { LocalScope::const_iterator scopePosition; }; +/// TryResult - a class representing a variant over the values +/// '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 { + int X; +public: + TryResult(bool b) : X(b ? 1 : 0) {} + TryResult() : X(-1) {} + + bool isTrue() const { return X == 1; } + bool isFalse() const { return X == 0; } + bool isKnown() const { return X >= 0; } + void negate() { + assert(isKnown()); + X ^= 0x1; + } +}; + /// CFGBuilder - This class implements CFG construction from an AST. /// The builder is stateful: an instance of the builder should be used to only /// construct a single CFG. @@ -238,7 +259,7 @@ class CFGBuilder { CFGBlock* SwitchTerminatedBlock; CFGBlock* DefaultCaseBlock; CFGBlock* TryTerminatedBlock; - + // Current position in local scope. LocalScope::const_iterator ScopePos; @@ -256,18 +277,30 @@ class CFGBuilder { LabelSetTy AddressTakenLabels; bool badCFG; - CFG::BuildOptions BuildOpts; + const CFG::BuildOptions &BuildOpts; + + // State to track for building switch statements. + bool switchExclusivelyCovered; + Expr::EvalResult *switchCond; + + CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry; + const Stmt *lastLookup; public: - explicit CFGBuilder() : cfg(new CFG()), // crew a new CFG - Block(NULL), Succ(NULL), - SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL), - TryTerminatedBlock(NULL), badCFG(false) {} + explicit CFGBuilder(ASTContext *astContext, + const CFG::BuildOptions &buildOpts) + : Context(astContext), cfg(new CFG()), // crew a new CFG + Block(NULL), Succ(NULL), + SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL), + TryTerminatedBlock(NULL), badCFG(false), BuildOpts(buildOpts), + switchExclusivelyCovered(false), switchCond(0), + cachedEntry(0), lastLookup(0) {} // buildCFG - Used by external clients to construct the CFG. - CFG* buildCFG(const Decl *D, Stmt *Statement, ASTContext *C, - CFG::BuildOptions BO); + CFG* buildCFG(const Decl *D, Stmt *Statement); + bool alwaysAdd(const Stmt *stmt); + private: // Visitors to walk an AST and construct the CFG. CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc); @@ -279,6 +312,7 @@ private: AddStmtChoice asc); CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T); CFGBlock *VisitCXXTryStmt(CXXTryStmt *S); + CFGBlock *VisitCXXForRangeStmt(CXXForRangeStmt *S); CFGBlock *VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E, AddStmtChoice asc); CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc); @@ -311,7 +345,8 @@ private: CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S); CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S); CFGBlock *VisitReturnStmt(ReturnStmt* R); - CFGBlock *VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, AddStmtChoice asc); + CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E, + AddStmtChoice asc); CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc); CFGBlock *VisitSwitchStmt(SwitchStmt *S); CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc); @@ -359,9 +394,11 @@ private: void addLocalScopeAndDtors(Stmt* S); // Interface to CFGBlock - adding CFGElements. - void appendStmt(CFGBlock *B, Stmt *S, - AddStmtChoice asc = AddStmtChoice::AlwaysAdd) { - B->appendStmt(S, cfg->getBumpVectorContext()); + void appendStmt(CFGBlock *B, const Stmt *S) { + if (alwaysAdd(S)) + cachedEntry->second = B; + + B->appendStmt(const_cast<Stmt*>(S), cfg->getBumpVectorContext()); } void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) { B->appendInitializer(I, cfg->getBumpVectorContext()); @@ -387,47 +424,74 @@ private: B->addSuccessor(S, cfg->getBumpVectorContext()); } - /// TryResult - a class representing a variant over the values - /// '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 { - int X; - public: - TryResult(bool b) : X(b ? 1 : 0) {} - TryResult() : X(-1) {} - - bool isTrue() const { return X == 1; } - bool isFalse() const { return X == 0; } - bool isKnown() const { return X >= 0; } - void negate() { - assert(isKnown()); - X ^= 0x1; - } - }; + /// Try and evaluate an expression to an integer constant. + bool tryEvaluate(Expr *S, Expr::EvalResult &outResult) { + if (!BuildOpts.PruneTriviallyFalseEdges) + return false; + return !S->isTypeDependent() && + !S->isValueDependent() && + S->Evaluate(outResult, *Context); + } /// 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 (!BuildOpts.PruneTriviallyFalseEdges) - return TryResult(); - Expr::EvalResult Result; - if (!S->isTypeDependent() && !S->isValueDependent() && - S->Evaluate(Result, *Context)) { - if (Result.Val.isInt()) - return Result.Val.getInt().getBoolValue(); - if (Result.Val.isLValue()) { - Expr *e = Result.Val.getLValueBase(); - const CharUnits &c = Result.Val.getLValueOffset(); - if (!e && c.isZero()) - return false; - } + if (!tryEvaluate(S, Result)) + return TryResult(); + + if (Result.Val.isInt()) + return Result.Val.getInt().getBoolValue(); + + if (Result.Val.isLValue()) { + Expr *e = Result.Val.getLValueBase(); + const CharUnits &c = Result.Val.getLValueOffset(); + if (!e && c.isZero()) + return false; } return TryResult(); } + }; +inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder, + const Stmt *stmt) const { + return builder.alwaysAdd(stmt) || kind == AlwaysAdd; +} + +bool CFGBuilder::alwaysAdd(const Stmt *stmt) { + if (!BuildOpts.forcedBlkExprs) + return false; + + if (lastLookup == stmt) { + if (cachedEntry) { + assert(cachedEntry->first == stmt); + return true; + } + return false; + } + + lastLookup = stmt; + + // Perform the lookup! + CFG::BuildOptions::ForcedBlkExprs *fb = *BuildOpts.forcedBlkExprs; + + if (!fb) { + // No need to update 'cachedEntry', since it will always be null. + assert(cachedEntry == 0); + return false; + } + + CFG::BuildOptions::ForcedBlkExprs::iterator itr = fb->find(stmt); + if (itr == fb->end()) { + cachedEntry = 0; + return false; + } + + cachedEntry = &*itr; + return true; +} + // FIXME: Add support for dependent-sized array types in C++? // Does it even make sense to build a CFG for an uninstantiated template? static const VariableArrayType *FindVA(const Type *t) { @@ -447,16 +511,11 @@ static const VariableArrayType *FindVA(const Type *t) { /// body (compound statement). The ownership of the returned CFG is /// transferred to the caller. If CFG construction fails, this method returns /// NULL. -CFG* CFGBuilder::buildCFG(const Decl *D, Stmt* Statement, ASTContext* C, - CFG::BuildOptions BO) { - - Context = C; +CFG* CFGBuilder::buildCFG(const Decl *D, Stmt* Statement) { assert(cfg.get()); if (!Statement) return NULL; - 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 // as the exit block. @@ -853,6 +912,9 @@ tryAgain: case Stmt::CXXTryStmtClass: return VisitCXXTryStmt(cast<CXXTryStmt>(S)); + case Stmt::CXXForRangeStmtClass: + return VisitCXXForRangeStmt(cast<CXXForRangeStmt>(S)); + case Stmt::DeclStmtClass: return VisitDeclStmt(cast<DeclStmt>(S)); @@ -908,8 +970,9 @@ tryAgain: case Stmt::ReturnStmtClass: return VisitReturnStmt(cast<ReturnStmt>(S)); - case Stmt::SizeOfAlignOfExprClass: - return VisitSizeOfAlignOfExpr(cast<SizeOfAlignOfExpr>(S), asc); + case Stmt::UnaryExprOrTypeTraitExprClass: + return VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S), + asc); case Stmt::StmtExprClass: return VisitStmtExpr(cast<StmtExpr>(S), asc); @@ -926,9 +989,9 @@ tryAgain: } CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) { - if (asc.alwaysAdd()) { + if (asc.alwaysAdd(*this, S)) { autoCreateBlock(); - appendStmt(Block, S, asc); + appendStmt(Block, S); } return VisitChildren(S); @@ -949,9 +1012,9 @@ CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc) { AddressTakenLabels.insert(A->getLabel()); - if (asc.alwaysAdd()) { + if (asc.alwaysAdd(*this, A)) { autoCreateBlock(); - appendStmt(Block, A, asc); + appendStmt(Block, A); } return Block; @@ -959,9 +1022,9 @@ CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc) { - if (asc.alwaysAdd()) { + if (asc.alwaysAdd(*this, U)) { autoCreateBlock(); - appendStmt(Block, U, asc); + appendStmt(Block, U); } return Visit(U->getSubExpr(), AddStmtChoice()); @@ -971,7 +1034,7 @@ CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc) { if (B->isLogicalOp()) { // && or || CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); - appendStmt(ConfluenceBlock, B, asc); + appendStmt(ConfluenceBlock, B); if (badCFG) return 0; @@ -1016,23 +1079,23 @@ CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, if (B->getOpcode() == BO_Comma) { // , autoCreateBlock(); - appendStmt(Block, B, asc); + appendStmt(Block, B); addStmt(B->getRHS()); return addStmt(B->getLHS()); } if (B->isAssignmentOp()) { - if (asc.alwaysAdd()) { + if (asc.alwaysAdd(*this, B)) { autoCreateBlock(); - appendStmt(Block, B, asc); + appendStmt(Block, B); } Visit(B->getLHS()); return Visit(B->getRHS()); } - if (asc.alwaysAdd()) { + if (asc.alwaysAdd(*this, B)) { autoCreateBlock(); - appendStmt(Block, B, asc); + appendStmt(Block, B); } CFGBlock *RBlock = Visit(B->getRHS()); @@ -1044,9 +1107,9 @@ CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, } CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) { - if (asc.alwaysAdd()) { + if (asc.alwaysAdd(*this, E)) { autoCreateBlock(); - appendStmt(Block, E, asc); + appendStmt(Block, E); } return Block; } @@ -1073,7 +1136,7 @@ CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { return Block; } -static bool CanThrow(Expr *E) { +static bool CanThrow(Expr *E, ASTContext &Ctx) { QualType Ty = E->getType(); if (Ty->isFunctionPointerType()) Ty = Ty->getAs<PointerType>()->getPointeeType(); @@ -1083,7 +1146,7 @@ static bool CanThrow(Expr *E) { const FunctionType *FT = Ty->getAs<FunctionType>(); if (FT) { if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT)) - if (Proto->hasEmptyExceptionSpec()) + if (Proto->isNothrow(Ctx)) return false; } return true; @@ -1099,7 +1162,7 @@ CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { bool AddEHEdge = false; // Languages without exceptions are assumed to not throw. - if (Context->getLangOptions().areExceptionsEnabled()) { + if (Context->getLangOptions().Exceptions) { if (BuildOpts.AddEHEdges) AddEHEdge = true; } @@ -1111,7 +1174,7 @@ CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { AddEHEdge = false; } - if (!CanThrow(C->getCallee())) + if (!CanThrow(C->getCallee(), *Context)) AddEHEdge = false; if (!NoReturn && !AddEHEdge) @@ -1124,7 +1187,7 @@ CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { } Block = createBlock(!NoReturn); - appendStmt(Block, C, asc); + appendStmt(Block, C); if (NoReturn) { // Wire this to the exit block directly. @@ -1144,7 +1207,7 @@ CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc) { CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); - appendStmt(ConfluenceBlock, C, asc); + appendStmt(ConfluenceBlock, C); if (badCFG) return 0; @@ -1197,7 +1260,7 @@ CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C, // Create the confluence block that will "merge" the results of the ternary // expression. CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); - appendStmt(ConfluenceBlock, C, asc); + appendStmt(ConfluenceBlock, C); if (badCFG) return 0; @@ -1353,7 +1416,7 @@ CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { addAutomaticObjDtors(ScopePos, BeginScopePos, I); } - // The block we were proccessing is now finished. Make it the successor + // The block we were processing is now finished. Make it the successor // block. if (Block) { Succ = Block; @@ -1436,7 +1499,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->getConditionVariableDeclStmt()); addStmt(Init); } } @@ -1574,7 +1637,7 @@ CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { if (VarDecl *VD = F->getConditionVariable()) { if (Expr *Init = VD->getInit()) { autoCreateBlock(); - appendStmt(Block, F, AddStmtChoice::AlwaysAdd); + appendStmt(Block, F->getConditionVariableDeclStmt()); EntryConditionBlock = addStmt(Init); assert(Block == EntryConditionBlock); } @@ -1672,9 +1735,9 @@ CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { } CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) { - if (asc.alwaysAdd()) { + if (asc.alwaysAdd(*this, M)) { autoCreateBlock(); - appendStmt(Block, M, asc); + appendStmt(Block, M); } return Visit(M->getBase()); } @@ -1736,7 +1799,7 @@ CFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { Block = ExitConditionBlock; // Walk the 'element' expression to see if there are any side-effects. We - // generate new blocks as necesary. We DON'T add the statement by default to + // generate new blocks as necessary. We DON'T add the statement by default to // the CFG unless it contains control-flow. EntryConditionBlock = Visit(S->getElement(), AddStmtChoice::NotAlwaysAdd); if (Block) { @@ -1799,7 +1862,7 @@ CFGBlock* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S) { // Add the @synchronized to the CFG. autoCreateBlock(); - appendStmt(Block, S, AddStmtChoice::AlwaysAdd); + appendStmt(Block, S); // Inline the sync expression. return addStmt(S->getSynchExpr()); @@ -1858,7 +1921,7 @@ CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { if (VarDecl *VD = W->getConditionVariable()) { if (Expr *Init = VD->getInit()) { autoCreateBlock(); - appendStmt(Block, W, AddStmtChoice::AlwaysAdd); + appendStmt(Block, W->getConditionVariableDeclStmt()); EntryConditionBlock = addStmt(Init); assert(Block == EntryConditionBlock); } @@ -2105,28 +2168,30 @@ CFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) { return Block; } -CFGBlock *CFGBuilder::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, - AddStmtChoice asc) { +CFGBlock *CFGBuilder::VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E, + AddStmtChoice asc) { - if (asc.alwaysAdd()) { + if (asc.alwaysAdd(*this, E)) { autoCreateBlock(); appendStmt(Block, E); } // VLA types have expressions that must be evaluated. + CFGBlock *lastBlock = Block; + if (E->isArgumentType()) { for (const VariableArrayType *VA =FindVA(E->getArgumentType().getTypePtr()); VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) - addStmt(VA->getSizeExpr()); + lastBlock = addStmt(VA->getSizeExpr()); } - return Block; + return lastBlock; } /// VisitStmtExpr - Utility method to handle (nested) statement /// expressions (a GCC extension). CFGBlock* CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) { - if (asc.alwaysAdd()) { + if (asc.alwaysAdd(*this, SE)) { autoCreateBlock(); appendStmt(Block, SE); } @@ -2180,6 +2245,18 @@ CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { assert(Terminator->getBody() && "switch must contain a non-NULL body"); Block = NULL; + // For pruning unreachable case statements, save the current state + // for tracking the condition value. + SaveAndRestore<bool> save_switchExclusivelyCovered(switchExclusivelyCovered, + false); + + // Determine if the switch condition can be explicitly evaluated. + assert(Terminator->getCond() && "switch condition must be non-NULL"); + Expr::EvalResult result; + bool b = tryEvaluate(Terminator->getCond(), result); + SaveAndRestore<Expr::EvalResult*> save_switchCond(switchCond, + b ? &result : 0); + // If body is not a compound statement create implicit scope // and add destructors. if (!isa<CompoundStmt>(Terminator->getBody())) @@ -2192,12 +2269,14 @@ CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { } // If we have no "default:" case, the default transition is to the code - // following the switch body. - addSuccessor(SwitchTerminatedBlock, DefaultCaseBlock); + // following the switch body. Moreover, take into account if all the + // cases of a switch are covered (e.g., switching on an enum value). + addSuccessor(SwitchTerminatedBlock, + switchExclusivelyCovered || Terminator->isAllEnumCasesCovered() + ? 0 : DefaultCaseBlock); // Add the terminator and condition in the switch block. SwitchTerminatedBlock->setTerminator(Terminator); - assert(Terminator->getCond() && "switch condition must be non-NULL"); Block = SwitchTerminatedBlock; Block = addStmt(Terminator->getCond()); @@ -2206,19 +2285,60 @@ CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { if (VarDecl *VD = Terminator->getConditionVariable()) { if (Expr *Init = VD->getInit()) { autoCreateBlock(); - appendStmt(Block, Terminator, AddStmtChoice::AlwaysAdd); + appendStmt(Block, Terminator->getConditionVariableDeclStmt()); addStmt(Init); } } return Block; } + +static bool shouldAddCase(bool &switchExclusivelyCovered, + const Expr::EvalResult *switchCond, + const CaseStmt *CS, + ASTContext &Ctx) { + if (!switchCond) + return true; + + bool addCase = false; + + if (!switchExclusivelyCovered) { + if (switchCond->Val.isInt()) { + // Evaluate the LHS of the case value. + Expr::EvalResult V1; + CS->getLHS()->Evaluate(V1, Ctx); + assert(V1.Val.isInt()); + const llvm::APSInt &condInt = switchCond->Val.getInt(); + const llvm::APSInt &lhsInt = V1.Val.getInt(); + + if (condInt == lhsInt) { + addCase = true; + switchExclusivelyCovered = true; + } + else if (condInt < lhsInt) { + if (const Expr *RHS = CS->getRHS()) { + // Evaluate the RHS of the case value. + Expr::EvalResult V2; + RHS->Evaluate(V2, Ctx); + assert(V2.Val.isInt()); + if (V2.Val.getInt() <= condInt) { + addCase = true; + switchExclusivelyCovered = true; + } + } + } + } + else + addCase = true; + } + return addCase; +} CFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) { // CaseStmts are essentially labels, so they are the first statement in a // block. CFGBlock *TopBlock = 0, *LastBlock = 0; - + if (Stmt *Sub = CS->getSubStmt()) { // For deeply nested chains of CaseStmts, instead of doing a recursion // (which can blow out the stack), manually unroll and create blocks @@ -2232,9 +2352,12 @@ CFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) { else TopBlock = currentBlock; - addSuccessor(SwitchTerminatedBlock, currentBlock); - LastBlock = currentBlock; + addSuccessor(SwitchTerminatedBlock, + shouldAddCase(switchExclusivelyCovered, switchCond, + CS, *Context) + ? currentBlock : 0); + LastBlock = currentBlock; CS = cast<CaseStmt>(Sub); Sub = CS->getSubStmt(); } @@ -2256,7 +2379,10 @@ CFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) { // Add this block to the list of successors for the block with the switch // statement. assert(SwitchTerminatedBlock); - addSuccessor(SwitchTerminatedBlock, CaseBlock); + addSuccessor(SwitchTerminatedBlock, + shouldAddCase(switchExclusivelyCovered, switchCond, + CS, *Context) + ? CaseBlock : 0); // We set Block to NULL to allow lazy creation of a new block (if necessary) Block = NULL; @@ -2391,6 +2517,122 @@ CFGBlock* CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt* CS) { return CatchBlock; } +CFGBlock* CFGBuilder::VisitCXXForRangeStmt(CXXForRangeStmt* S) { + // C++0x for-range statements are specified as [stmt.ranged]: + // + // { + // auto && __range = range-init; + // for ( auto __begin = begin-expr, + // __end = end-expr; + // __begin != __end; + // ++__begin ) { + // for-range-declaration = *__begin; + // statement + // } + // } + + // Save local scope position before the addition of the implicit variables. + SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); + + // Create local scopes and destructors for range, begin and end variables. + if (Stmt *Range = S->getRangeStmt()) + addLocalScopeForStmt(Range); + if (Stmt *BeginEnd = S->getBeginEndStmt()) + addLocalScopeForStmt(BeginEnd); + addAutomaticObjDtors(ScopePos, save_scope_pos.get(), S); + + LocalScope::const_iterator ContinueScopePos = ScopePos; + + // "for" is a control-flow statement. Thus we stop processing the current + // block. + CFGBlock* LoopSuccessor = NULL; + if (Block) { + if (badCFG) + return 0; + LoopSuccessor = Block; + } else + LoopSuccessor = Succ; + + // Save the current value for the break targets. + // All breaks should go to the code following the loop. + SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); + BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); + + // The block for the __begin != __end expression. + CFGBlock* ConditionBlock = createBlock(false); + ConditionBlock->setTerminator(S); + + // Now add the actual condition to the condition block. + if (Expr *C = S->getCond()) { + Block = ConditionBlock; + CFGBlock *BeginConditionBlock = addStmt(C); + if (badCFG) + return 0; + assert(BeginConditionBlock == ConditionBlock && + "condition block in for-range was unexpectedly complex"); + (void)BeginConditionBlock; + } + + // The condition block is the implicit successor for the loop body as well as + // any code above the loop. + Succ = ConditionBlock; + + // See if this is a known constant. + TryResult KnownVal(true); + + if (S->getCond()) + KnownVal = tryEvaluateBool(S->getCond()); + + // Now create the loop body. + { + assert(S->getBody()); + + // Save the current values for Block, Succ, and continue targets. + SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); + SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget); + + // Generate increment code in its own basic block. This is the target of + // continue statements. + Block = 0; + Succ = addStmt(S->getInc()); + 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. + ContinueJumpTarget.block->setLoopTarget(S); + + // Finish up the increment block and prepare to start the loop body. + assert(Block); + if (badCFG) + return 0; + Block = 0; + + + // Add implicit scope and dtors for loop variable. + addLocalScopeAndDtors(S->getLoopVarStmt()); + + // Populate a new block to contain the loop body and loop variable. + Block = addStmt(S->getBody()); + if (badCFG) + return 0; + Block = addStmt(S->getLoopVarStmt()); + if (badCFG) + return 0; + + // This new body block is a successor to our condition block. + addSuccessor(ConditionBlock, KnownVal.isFalse() ? 0 : Block); + } + + // Link up the condition block with the code that follows the loop (the + // false branch). + addSuccessor(ConditionBlock, KnownVal.isTrue() ? 0 : LoopSuccessor); + + // Add the initialization statements. + Block = createBlock(); + addStmt(S->getBeginEndStmt()); + return addStmt(S->getRangeStmt()); +} + CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E, AddStmtChoice asc) { if (BuildOpts.AddImplicitDtors) { @@ -2407,9 +2649,9 @@ CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E, CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E, AddStmtChoice asc) { - if (asc.alwaysAdd()) { + if (asc.alwaysAdd(*this, E)) { autoCreateBlock(); - appendStmt(Block, E, asc); + appendStmt(Block, E); // We do not want to propagate the AlwaysAdd property. asc = asc.withAlwaysAdd(false); @@ -2421,16 +2663,16 @@ CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc) { autoCreateBlock(); if (!C->isElidable()) - appendStmt(Block, C, asc.withAlwaysAdd(true)); + appendStmt(Block, C); return VisitChildren(C); } CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E, AddStmtChoice asc) { - if (asc.alwaysAdd()) { + if (asc.alwaysAdd(*this, E)) { autoCreateBlock(); - appendStmt(Block, E, asc); + appendStmt(Block, E); // We do not want to propagate the AlwaysAdd property. asc = asc.withAlwaysAdd(false); } @@ -2440,22 +2682,22 @@ CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E, CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C, AddStmtChoice asc) { autoCreateBlock(); - appendStmt(Block, C, asc.withAlwaysAdd(true)); + appendStmt(Block, C); return VisitChildren(C); } CFGBlock *CFGBuilder::VisitCXXMemberCallExpr(CXXMemberCallExpr *C, AddStmtChoice asc) { autoCreateBlock(); - appendStmt(Block, C, asc.withAlwaysAdd(true)); + appendStmt(Block, C); return VisitChildren(C); } CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E, AddStmtChoice asc) { - if (asc.alwaysAdd()) { + if (asc.alwaysAdd(*this, E)) { autoCreateBlock(); - appendStmt(Block, E, asc); + appendStmt(Block, E); } return Visit(E->getSubExpr(), AddStmtChoice()); } @@ -2699,9 +2941,53 @@ 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, - BuildOptions BO) { - CFGBuilder Builder; - return Builder.buildCFG(D, Statement, C, BO); + const BuildOptions &BO) { + CFGBuilder Builder(C, BO); + return Builder.buildCFG(D, Statement); +} + +const CXXDestructorDecl * +CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const { + switch (getKind()) { + case CFGElement::Invalid: + case CFGElement::Statement: + case CFGElement::Initializer: + llvm_unreachable("getDestructorDecl should only be used with " + "ImplicitDtors"); + case CFGElement::AutomaticObjectDtor: { + const VarDecl *var = cast<CFGAutomaticObjDtor>(this)->getVarDecl(); + QualType ty = var->getType(); + ty = ty.getNonReferenceType(); + if (const ArrayType *arrayType = astContext.getAsArrayType(ty)) { + ty = arrayType->getElementType(); + } + const RecordType *recordType = ty->getAs<RecordType>(); + const CXXRecordDecl *classDecl = + cast<CXXRecordDecl>(recordType->getDecl()); + return classDecl->getDestructor(); + } + case CFGElement::TemporaryDtor: { + const CXXBindTemporaryExpr *bindExpr = + cast<CFGTemporaryDtor>(this)->getBindTemporaryExpr(); + const CXXTemporary *temp = bindExpr->getTemporary(); + return temp->getDestructor(); + } + case CFGElement::BaseDtor: + case CFGElement::MemberDtor: + + // Not yet supported. + return 0; + } + llvm_unreachable("getKind() returned bogus value"); + return 0; +} + +bool CFGImplicitDtor::isNoReturn(ASTContext &astContext) const { + if (const CXXDestructorDecl *cdecl = getDestructorDecl(astContext)) { + QualType ty = cdecl->getType(); + return cast<FunctionType>(ty)->getNoReturnAttr(); + } + return false; } //===----------------------------------------------------------------------===// @@ -2740,8 +3026,8 @@ 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) - if (CFGStmt S = BI->getAs<CFGStmt>()) - FindSubExprAssignments(S, SubExprAssignments); + if (const CFGStmt *S = BI->getAs<CFGStmt>()) + FindSubExprAssignments(S->getStmt(), SubExprAssignments); for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { @@ -2749,10 +3035,10 @@ static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { // block-level that are block-level expressions. for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) { - CFGStmt CS = BI->getAs<CFGStmt>(); - if (!CS.isValid()) + const CFGStmt *CS = BI->getAs<CFGStmt>(); + if (!CS) continue; - if (Expr* Exp = dyn_cast<Expr>(CS.getStmt())) { + if (Expr* Exp = dyn_cast<Expr>(CS->getStmt())) { if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { // Assignment expressions that are not nested within another @@ -2814,15 +3100,15 @@ unsigned CFG::getNumBlkExprs() { bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F, const CFGBlock *From, const CFGBlock *To) { - if (F.IgnoreDefaultsWithCoveredEnums) { + if (To && 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())) { + dyn_cast_or_null<SwitchStmt>(From->getTerminator().getStmt())) { if (S->isAllEnumCasesCovered()) { - const Stmt *L = To->getLabel(); - if (!L || !isa<CaseStmt>(L)) - return true; + const Stmt *L = To->getLabel(); + if (!L || !isa<CaseStmt>(L)) + return true; } } } @@ -2845,8 +3131,8 @@ CFG::~CFG() { namespace { class StmtPrinterHelper : public PrinterHelper { - typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; - typedef llvm::DenseMap<Decl*,std::pair<unsigned,unsigned> > DeclMapTy; + typedef llvm::DenseMap<const Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; + typedef llvm::DenseMap<const Decl*,std::pair<unsigned,unsigned> > DeclMapTy; StmtMapTy StmtMap; DeclMapTy DeclMap; signed currentBlock; @@ -2855,42 +3141,62 @@ class StmtPrinterHelper : public PrinterHelper { 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 ) { - if (CFGStmt SE = BI->getAs<CFGStmt>()) { + if (const CFGStmt *SE = BI->getAs<CFGStmt>()) { + const Stmt *stmt= SE->getStmt(); 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; + StmtMap[stmt] = P; + + switch (stmt->getStmtClass()) { + case Stmt::DeclStmtClass: + DeclMap[cast<DeclStmt>(stmt)->getSingleDecl()] = P; + break; + case Stmt::IfStmtClass: { + const VarDecl *var = cast<IfStmt>(stmt)->getConditionVariable(); + if (var) + DeclMap[var] = P; + break; + } + case Stmt::ForStmtClass: { + const VarDecl *var = cast<ForStmt>(stmt)->getConditionVariable(); + if (var) + DeclMap[var] = P; + break; + } + case Stmt::WhileStmtClass: { + const VarDecl *var = + cast<WhileStmt>(stmt)->getConditionVariable(); + if (var) + DeclMap[var] = P; + break; + } + case Stmt::SwitchStmtClass: { + const VarDecl *var = + cast<SwitchStmt>(stmt)->getConditionVariable(); + if (var) + DeclMap[var] = P; + break; + } + case Stmt::CXXCatchStmtClass: { + const VarDecl *var = + cast<CXXCatchStmt>(stmt)->getExceptionDecl(); + if (var) + DeclMap[var] = P; + break; + } + default: + break; } } } } } + virtual ~StmtPrinterHelper() {} @@ -2913,7 +3219,7 @@ public: return true; } - bool handleDecl(Decl* D, llvm::raw_ostream& OS) { + bool handleDecl(const Decl* D, llvm::raw_ostream& OS) { DeclMapTy::iterator I = DeclMap.find(D); if (I == DeclMap.end()) @@ -3031,8 +3337,8 @@ public: static void print_elem(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, const CFGElement &E) { - if (CFGStmt CS = E.getAs<CFGStmt>()) { - Stmt *S = CS; + if (const CFGStmt *CS = E.getAs<CFGStmt>()) { + Stmt *S = CS->getStmt(); if (Helper) { @@ -3069,8 +3375,8 @@ static void print_elem(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, if (isa<Expr>(S)) OS << '\n'; - } else if (CFGInitializer IE = E.getAs<CFGInitializer>()) { - CXXCtorInitializer* I = IE; + } else if (const CFGInitializer *IE = E.getAs<CFGInitializer>()) { + const CXXCtorInitializer *I = IE->getInitializer(); if (I->isBaseInitializer()) OS << I->getBaseClass()->getAsCXXRecordDecl()->getName(); else OS << I->getAnyMember()->getName(); @@ -3084,8 +3390,8 @@ static void print_elem(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, OS << " (Base initializer)\n"; else OS << " (Member initializer)\n"; - } else if (CFGAutomaticObjDtor DE = E.getAs<CFGAutomaticObjDtor>()){ - VarDecl* VD = DE.getVarDecl(); + } else if (const CFGAutomaticObjDtor *DE = E.getAs<CFGAutomaticObjDtor>()){ + const VarDecl* VD = DE->getVarDecl(); Helper->handleDecl(VD, OS); const Type* T = VD->getType().getTypePtr(); @@ -3097,13 +3403,13 @@ static void print_elem(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, OS << ".~" << T->getAsCXXRecordDecl()->getName().str() << "()"; OS << " (Implicit destructor)\n"; - } else if (CFGBaseDtor BE = E.getAs<CFGBaseDtor>()) { - const CXXBaseSpecifier *BS = BE.getBaseSpecifier(); + } else if (const 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(); + } else if (const CFGMemberDtor *ME = E.getAs<CFGMemberDtor>()) { + const FieldDecl *FD = ME->getFieldDecl(); const Type *T = FD->getType().getTypePtr(); if (const Type *ET = T->getArrayElementTypeNoTypeQual()) @@ -3113,8 +3419,8 @@ static void print_elem(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()"; OS << " (Member object destructor)\n"; - } else if (CFGTemporaryDtor TE = E.getAs<CFGTemporaryDtor>()) { - CXXBindTemporaryExpr *BT = TE.getBindTemporaryExpr(); + } else if (const CFGTemporaryDtor *TE = E.getAs<CFGTemporaryDtor>()) { + const CXXBindTemporaryExpr *BT = TE->getBindTemporaryExpr(); OS << "~" << BT->getType()->getAsCXXRecordDecl()->getName() << "()"; OS << " (Temporary object destructor)\n"; } @@ -3344,32 +3650,6 @@ Stmt* CFGBlock::getTerminatorCondition() { return E ? E->IgnoreParens() : NULL; } -bool CFGBlock::hasBinaryBranchTerminator() const { - const Stmt *Terminator = this->Terminator; - if (!Terminator) - return false; - - Expr* E = NULL; - - switch (Terminator->getStmtClass()) { - default: - return false; - - case Stmt::ForStmtClass: - case Stmt::WhileStmtClass: - case Stmt::DoStmtClass: - case Stmt::IfStmtClass: - case Stmt::ChooseExprClass: - case Stmt::BinaryConditionalOperatorClass: - case Stmt::ConditionalOperatorClass: - case Stmt::BinaryOperatorClass: - return true; - } - - return E ? E->IgnoreParens() : NULL; -} - - //===----------------------------------------------------------------------===// // CFG Graphviz Visualization //===----------------------------------------------------------------------===// diff --git a/lib/Analysis/CFGReachabilityAnalysis.cpp b/lib/Analysis/CFGReachabilityAnalysis.cpp index 77865849014a..65cd0898573c 100644 --- a/lib/Analysis/CFGReachabilityAnalysis.cpp +++ b/lib/Analysis/CFGReachabilityAnalysis.cpp @@ -19,10 +19,10 @@ using namespace clang; -CFGReachabilityAnalysis::CFGReachabilityAnalysis(const CFG &cfg) +CFGReverseBlockReachabilityAnalysis::CFGReverseBlockReachabilityAnalysis(const CFG &cfg) : analyzed(cfg.getNumBlockIDs(), false) {} -bool CFGReachabilityAnalysis::isReachable(const CFGBlock *Src, +bool CFGReverseBlockReachabilityAnalysis::isReachable(const CFGBlock *Src, const CFGBlock *Dst) { const unsigned DstBlockID = Dst->getBlockID(); @@ -39,7 +39,7 @@ bool CFGReachabilityAnalysis::isReachable(const CFGBlock *Src, // Maps reachability to a common node by walking the predecessors of the // destination node. -void CFGReachabilityAnalysis::mapReachability(const CFGBlock *Dst) { +void CFGReverseBlockReachabilityAnalysis::mapReachability(const CFGBlock *Dst) { llvm::SmallVector<const CFGBlock *, 11> worklist; llvm::BitVector visited(analyzed.size()); diff --git a/lib/Analysis/CFGStmtMap.cpp b/lib/Analysis/CFGStmtMap.cpp index 3a030f9bdd1e..1fd5eedfeb86 100644 --- a/lib/Analysis/CFGStmtMap.cpp +++ b/lib/Analysis/CFGStmtMap.cpp @@ -50,11 +50,11 @@ 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; - CFGStmt CS = CE.getAs<CFGStmt>(); - if (!CS.isValid()) + const CFGStmt *CS = CE.getAs<CFGStmt>(); + if (!CS) continue; - CFGBlock *&Entry = SM[CS]; + CFGBlock *&Entry = SM[CS->getStmt()]; // If 'Entry' is already initialized (e.g., a terminator was already), // skip. if (Entry) diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index 84b211f2cfca..967fc2930f42 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -13,7 +13,6 @@ add_clang_library(clangAnalysis ReachableCode.cpp ScanfFormatString.cpp UninitializedValues.cpp - UninitializedValuesV2.cpp ) add_dependencies(clangAnalysis ClangAttrClasses ClangAttrList diff --git a/lib/Analysis/CocoaConventions.cpp b/lib/Analysis/CocoaConventions.cpp index 22b6c1aaf021..4c62f36e6c92 100644 --- a/lib/Analysis/CocoaConventions.cpp +++ b/lib/Analysis/CocoaConventions.cpp @@ -16,6 +16,7 @@ #include "clang/AST/Decl.h" #include "clang/AST/DeclObjC.h" #include "llvm/ADT/StringExtras.h" +#include "llvm/Support/ErrorHandling.h" using namespace clang; using namespace ento; @@ -35,84 +36,27 @@ using llvm::StringRef; // 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) +cocoa::NamingConvention cocoa::deriveNamingConvention(Selector S) { + switch (S.getMethodFamily()) { + case OMF_None: + case OMF_autorelease: + case OMF_dealloc: + case OMF_release: + case OMF_retain: + case OMF_retainCount: return NoConvention; - // Parse the first word, and look for specific keywords. - const char *wordEnd = parseWord(s); - assert(wordEnd > s); - unsigned len = wordEnd - s; + case OMF_init: + return InitRule; - 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; + case OMF_alloc: + case OMF_copy: + case OMF_mutableCopy: + case OMF_new: + return CreateRule; } + llvm_unreachable("unexpected naming convention"); + return NoConvention; } bool cocoa::isRefType(QualType RetTy, llvm::StringRef Prefix, diff --git a/lib/Analysis/PrintfFormatString.cpp b/lib/Analysis/PrintfFormatString.cpp index db9f7f2c834e..00b0b279e4a0 100644 --- a/lib/Analysis/PrintfFormatString.cpp +++ b/lib/Analysis/PrintfFormatString.cpp @@ -381,8 +381,32 @@ bool PrintfSpecifier::fixType(QualType QT) { // Set length modifier switch (BT->getKind()) { - default: - // The rest of the conversions are either optional or for non-builtin types + case BuiltinType::Bool: + case BuiltinType::WChar_U: + case BuiltinType::WChar_S: + case BuiltinType::Char16: + case BuiltinType::Char32: + case BuiltinType::UInt128: + case BuiltinType::Int128: + // Integral types which are non-trivial to correct. + return false; + + case BuiltinType::Void: + case BuiltinType::NullPtr: + case BuiltinType::ObjCId: + case BuiltinType::ObjCClass: + case BuiltinType::ObjCSel: + case BuiltinType::Dependent: + case BuiltinType::Overload: + case BuiltinType::BoundMember: + case BuiltinType::UnknownAny: + // Misc other stuff which doesn't make sense here. + return false; + + case BuiltinType::UInt: + case BuiltinType::Int: + case BuiltinType::Float: + case BuiltinType::Double: LM.setKind(LengthModifier::None); break; @@ -398,8 +422,6 @@ bool PrintfSpecifier::fixType(QualType QT) { LM.setKind(LengthModifier::AsShort); break; - case BuiltinType::WChar_S: - case BuiltinType::WChar_U: case BuiltinType::Long: case BuiltinType::ULong: LM.setKind(LengthModifier::AsLong); @@ -429,24 +451,19 @@ bool PrintfSpecifier::fixType(QualType QT) { else if (QT->isRealFloatingType()) { CS.setKind(ConversionSpecifier::fArg); } - else if (QT->isPointerType()) { - CS.setKind(ConversionSpecifier::pArg); - Precision.setHowSpecified(OptionalAmount::NotSpecified); - HasAlternativeForm = 0; - HasLeadingZeroes = 0; - HasPlusPrefix = 0; - } else if (QT->isSignedIntegerType()) { CS.setKind(ConversionSpecifier::dArg); HasAlternativeForm = 0; } else if (QT->isUnsignedIntegerType()) { - CS.setKind(ConversionSpecifier::uArg); + // Preserve the original formatting, e.g. 'X', 'o'. + if (!cast<PrintfConversionSpecifier>(CS).isUIntArg()) + CS.setKind(ConversionSpecifier::uArg); HasAlternativeForm = 0; HasPlusPrefix = 0; } else { - return false; + assert(0 && "Unexpected type"); } return true; diff --git a/lib/Analysis/ReachableCode.cpp b/lib/Analysis/ReachableCode.cpp index 7afa586479b3..9ac456f53a67 100644 --- a/lib/Analysis/ReachableCode.cpp +++ b/lib/Analysis/ReachableCode.cpp @@ -31,11 +31,11 @@ static SourceLocation GetUnreachableLoc(const CFGBlock &b, SourceRange &R1, R1 = R2 = SourceRange(); if (sn < b.size()) { - CFGStmt CS = b[sn].getAs<CFGStmt>(); + const CFGStmt *CS = b[sn].getAs<CFGStmt>(); if (!CS) return SourceLocation(); - S = CS.getStmt(); + S = CS->getStmt(); } else if (b.getTerminator()) S = b.getTerminator(); else @@ -49,7 +49,7 @@ static SourceLocation GetUnreachableLoc(const CFGBlock &b, SourceRange &R1, const BinaryOperator *BO = cast<BinaryOperator>(S); if (BO->getOpcode() == BO_Comma) { if (sn+1 < b.size()) - return b[sn+1].getAs<CFGStmt>().getStmt()->getLocStart(); + return b[sn+1].getAs<CFGStmt>()->getStmt()->getLocStart(); const CFGBlock *n = &b; while (1) { if (n->getTerminator()) @@ -60,7 +60,7 @@ static SourceLocation GetUnreachableLoc(const CFGBlock &b, SourceRange &R1, if (n->pred_size() != 1) return SourceLocation(); if (!n->empty()) - return n[0][0].getAs<CFGStmt>().getStmt()->getLocStart(); + return n[0][0].getAs<CFGStmt>()->getStmt()->getLocStart(); } } R1 = BO->getLHS()->getSourceRange(); @@ -193,7 +193,7 @@ unsigned ScanReachableFromBlock(const CFGBlock &Start, unsigned count = 0; llvm::SmallVector<const CFGBlock*, 32> WL; - // Prep work queue + // Prep work queue Reachable.set(Start.getBlockID()); ++count; WL.push_back(&Start); diff --git a/lib/Analysis/UninitializedValues.cpp b/lib/Analysis/UninitializedValues.cpp index c08cbedf4b94..88a2db751a43 100644 --- a/lib/Analysis/UninitializedValues.cpp +++ b/lib/Analysis/UninitializedValues.cpp @@ -7,311 +7,723 @@ // //===----------------------------------------------------------------------===// // -// This file implements Uninitialized Values analysis for source-level CFGs. +// This file implements uninitialized values analysis for source-level CFGs. // //===----------------------------------------------------------------------===// -#include "clang/Analysis/Analyses/UninitializedValues.h" +#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/AnalysisDiagnostic.h" -#include "clang/AST/ASTContext.h" -#include "clang/Analysis/FlowSensitive/DataflowSolver.h" - -#include "llvm/ADT/SmallPtrSet.h" +#include "clang/Analysis/Analyses/UninitializedValues.h" +#include "clang/Analysis/Support/SaveAndRestore.h" using namespace clang; -//===----------------------------------------------------------------------===// -// Dataflow initialization logic. -//===----------------------------------------------------------------------===// - -namespace { +static bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { + if (vd->isLocalVarDecl() && !vd->hasGlobalStorage() && + !vd->isExceptionVariable() && + vd->getDeclContext() == dc) { + QualType ty = vd->getType(); + return ty->isScalarType() || ty->isVectorType(); + } + return false; +} -class RegisterDecls - : public CFGRecStmtDeclVisitor<RegisterDecls> { +//------------------------------------------------------------------------====// +// DeclToIndex: a mapping from Decls we track to value indices. +//====------------------------------------------------------------------------// - UninitializedValues::AnalysisDataTy& AD; +namespace { +class DeclToIndex { + llvm::DenseMap<const VarDecl *, unsigned> map; public: - RegisterDecls(UninitializedValues::AnalysisDataTy& ad) : AD(ad) {} - - void VisitVarDecl(VarDecl* VD) { AD.Register(VD); } - CFG& getCFG() { return AD.getCFG(); } + DeclToIndex() {} + + /// 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> getValueIndex(const VarDecl *d) const; }; +} -} // end anonymous namespace +void DeclToIndex::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++; + } +} -void UninitializedValues::InitializeValues(const CFG& cfg) { - RegisterDecls R(getAnalysisData()); - cfg.VisitBlockStmts(R); +llvm::Optional<unsigned> DeclToIndex::getValueIndex(const VarDecl *d) const { + llvm::DenseMap<const VarDecl *, unsigned>::const_iterator I = map.find(d); + if (I == map.end()) + return llvm::Optional<unsigned>(); + return I->second; } -//===----------------------------------------------------------------------===// -// Transfer functions. -//===----------------------------------------------------------------------===// +//------------------------------------------------------------------------====// +// CFGBlockValues: dataflow values for CFG blocks. +//====------------------------------------------------------------------------// -namespace { -class TransferFuncs - : public CFGStmtVisitor<TransferFuncs,bool> { +// These values are defined in such a way that a merge can be done using +// a bitwise OR. +enum Value { Unknown = 0x0, /* 00 */ + Initialized = 0x1, /* 01 */ + Uninitialized = 0x2, /* 10 */ + MayUninitialized = 0x3 /* 11 */ }; - UninitializedValues::ValTy V; - UninitializedValues::AnalysisDataTy& AD; +static bool isUninitialized(const Value v) { + return v >= Uninitialized; +} +static bool isAlwaysUninit(const Value v) { + return v == Uninitialized; +} + +namespace { +class ValueVector { + llvm::BitVector vec; public: - TransferFuncs(UninitializedValues::AnalysisDataTy& ad) : AD(ad) {} + ValueVector() {} + ValueVector(unsigned size) : vec(size << 1) {} + void resize(unsigned n) { vec.resize(n << 1); } + void merge(const ValueVector &rhs) { vec |= rhs.vec; } + bool operator!=(const ValueVector &rhs) const { return vec != rhs.vec; } + void reset() { vec.reset(); } + + class reference { + ValueVector &vv; + const unsigned idx; + + reference(); // Undefined + public: + reference(ValueVector &vv, unsigned idx) : vv(vv), idx(idx) {} + ~reference() {} + + reference &operator=(Value v) { + vv.vec[idx << 1] = (((unsigned) v) & 0x1) ? true : false; + vv.vec[(idx << 1) | 1] = (((unsigned) v) & 0x2) ? true : false; + return *this; + } + operator Value() { + unsigned x = (vv.vec[idx << 1] ? 1 : 0) | (vv.vec[(idx << 1) | 1] ? 2 :0); + return (Value) x; + } + }; + + reference operator[](unsigned idx) { return reference(*this, idx); } +}; - UninitializedValues::ValTy& getVal() { return V; } - CFG& getCFG() { return AD.getCFG(); } +typedef std::pair<ValueVector *, ValueVector *> BVPair; - void SetTopValue(UninitializedValues::ValTy& X) { - X.setDeclValues(AD); - X.resetBlkExprValues(AD); +class CFGBlockValues { + const CFG &cfg; + BVPair *vals; + ValueVector scratch; + DeclToIndex declToIndex; + + ValueVector &lazyCreate(ValueVector *&bv); +public: + CFGBlockValues(const CFG &cfg); + ~CFGBlockValues(); + + unsigned getNumEntries() const { return declToIndex.size(); } + + void computeSetOfDeclarations(const DeclContext &dc); + ValueVector &getValueVector(const CFGBlock *block, + const CFGBlock *dstBlock); + + BVPair &getValueVectors(const CFGBlock *block, bool shouldLazyCreate); + + void mergeIntoScratch(ValueVector const &source, bool isFirst); + bool updateValueVectorWithScratch(const CFGBlock *block); + bool updateValueVectors(const CFGBlock *block, const BVPair &newVals); + + bool hasNoDeclarations() const { + return declToIndex.size() == 0; } + + bool hasEntry(const VarDecl *vd) const { + return declToIndex.getValueIndex(vd).hasValue(); + } + + bool hasValues(const CFGBlock *block); + + void resetScratch(); + ValueVector &getScratch() { return scratch; } + + ValueVector::reference operator[](const VarDecl *vd); +}; +} // end anonymous namespace - bool VisitDeclRefExpr(DeclRefExpr* DR); - bool VisitBinaryOperator(BinaryOperator* B); - bool VisitUnaryOperator(UnaryOperator* U); - bool VisitStmt(Stmt* S); - bool VisitCallExpr(CallExpr* C); - bool VisitDeclStmt(DeclStmt* D); - bool VisitAbstractConditionalOperator(AbstractConditionalOperator* C); - bool BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S); - - bool Visit(Stmt *S); - bool BlockStmt_VisitExpr(Expr* E); +CFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) { + unsigned n = cfg.getNumBlockIDs(); + if (!n) + return; + vals = new std::pair<ValueVector*, ValueVector*>[n]; + memset((void*)vals, 0, sizeof(*vals) * n); +} - void VisitTerminator(CFGBlock* B) { } - - void setCurrentBlock(const CFGBlock *block) {} -}; +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; +} -static const bool Initialized = false; -static const bool Uninitialized = true; +void CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { + declToIndex.computeMap(dc); + scratch.resize(declToIndex.size()); +} -bool TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) { +ValueVector &CFGBlockValues::lazyCreate(ValueVector *&bv) { + if (!bv) + bv = new ValueVector(declToIndex.size()); + return *bv; +} - if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) - if (VD->isLocalVarDecl()) { +/// 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; + + const CFGStmt *cstmt = block->front().getAs<CFGStmt>(); + if (!cstmt) + return 0; + + 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; +} - if (AD.Observer) - AD.Observer->ObserveDeclRefExpr(V, AD, DR, VD); +ValueVector &CFGBlockValues::getValueVector(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); + } - // Pseudo-hack to prevent cascade of warnings. If an accessed variable - // is uninitialized, then we are already going to flag a warning for - // this variable, which a "source" of uninitialized values. - // We can otherwise do a full "taint" of uninitialized values. The - // client has both options by toggling AD.FullUninitTaint. + assert(vals[idx].second == 0); + return lazyCreate(vals[idx].first); +} - if (AD.FullUninitTaint) - return V(VD,AD); - } +bool CFGBlockValues::hasValues(const CFGBlock *block) { + unsigned idx = block->getBlockID(); + return vals[idx].second != 0; +} - return Initialized; +BVPair &CFGBlockValues::getValueVectors(const clang::CFGBlock *block, + bool shouldLazyCreate) { + unsigned idx = block->getBlockID(); + lazyCreate(vals[idx].first); + if (shouldLazyCreate) + lazyCreate(vals[idx].second); + return vals[idx]; } -static VarDecl* FindBlockVarDecl(Expr* E) { +void CFGBlockValues::mergeIntoScratch(ValueVector const &source, + bool isFirst) { + if (isFirst) + scratch = source; + else + scratch.merge(source); +} +#if 0 +static void printVector(const CFGBlock *block, ValueVector &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::updateValueVectorWithScratch(const CFGBlock *block) { + ValueVector &dst = getValueVector(block, 0); + bool changed = (dst != scratch); + if (changed) + dst = scratch; +#if 0 + printVector(block, scratch, 0); +#endif + return changed; +} - // Blast through casts and parentheses to find any DeclRefExprs that - // refer to a block VarDecl. +bool CFGBlockValues::updateValueVectors(const CFGBlock *block, + const BVPair &newVals) { + BVPair &vals = getValueVectors(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; +} - if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParenCasts())) - if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) - if (VD->isLocalVarDecl()) return VD; +void CFGBlockValues::resetScratch() { + scratch.reset(); +} - return NULL; +ValueVector::reference CFGBlockValues::operator[](const VarDecl *vd) { + const llvm::Optional<unsigned> &idx = declToIndex.getValueIndex(vd); + assert(idx.hasValue()); + return scratch[idx.getValue()]; } -bool TransferFuncs::VisitBinaryOperator(BinaryOperator* B) { +//------------------------------------------------------------------------====// +// Worklist: worklist for dataflow analysis. +//====------------------------------------------------------------------------// - if (VarDecl* VD = FindBlockVarDecl(B->getLHS())) - if (B->isAssignmentOp()) { - if (B->getOpcode() == BO_Assign) - return V(VD,AD) = Visit(B->getRHS()); - else // Handle +=, -=, *=, etc. We do want '&', not '&&'. - return V(VD,AD) = Visit(B->getLHS()) & Visit(B->getRHS()); - } +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(); + +}; +} - return VisitStmt(B); +void DataflowWorklist::enqueue(const CFGBlock *block) { + if (!block) + return; + unsigned idx = block->getBlockID(); + if (enqueuedBlocks[idx]) + return; + worklist.push_back(block); + enqueuedBlocks[idx] = true; } -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->isLocalVarDecl()) { - if (Stmt* I = VD->getInit()) { - // Visit the subexpression to check for uses of uninitialized values, - // even if we don't propagate that value. - bool isSubExprUninit = Visit(I); - V(VD,AD) = AD.FullUninitTaint ? isSubExprUninit : Initialized; - } - else { - // Special case for declarations of array types. For things like: - // - // char x[10]; - // - // we should treat "x" as being initialized, because the variable - // "x" really refers to the memory block. Clearly x[1] is - // uninitialized, but expressions like "(char *) x" really do refer to - // an initialized value. This simple dataflow analysis does not reason - // about the contents of arrays, although it could be potentially - // extended to do so if the array were of constant size. - if (VD->getType()->isArrayType()) - V(VD,AD) = Initialized; - else - V(VD,AD) = Uninitialized; - } - } +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); } - return Uninitialized; // Value is never consumed. } -bool TransferFuncs::VisitCallExpr(CallExpr* C) { - VisitChildren(C); - return Initialized; +const CFGBlock *DataflowWorklist::dequeue() { + if (worklist.empty()) + return 0; + const CFGBlock *b = worklist.back(); + worklist.pop_back(); + enqueuedBlocks[b->getBlockID()] = false; + return b; } -bool TransferFuncs::VisitUnaryOperator(UnaryOperator* U) { - switch (U->getOpcode()) { - case UO_AddrOf: { - VarDecl* VD = FindBlockVarDecl(U->getSubExpr()); - if (VD && VD->isLocalVarDecl()) - return V(VD,AD) = Initialized; - break; - } +//------------------------------------------------------------------------====// +// Transfer function for uninitialized values analysis. +//====------------------------------------------------------------------------// - default: - break; +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, + bool isAlwaysUninit); + + 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 VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *se); + void VisitCXXTypeidExpr(CXXTypeidExpr *E); + void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt *fs); + + bool isTrackedVar(const VarDecl *vd) { + return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl())); } - - return Visit(U->getSubExpr()); + + FindVarResult findBlockVarDecl(Expr *ex); +}; } -bool -TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { - // This represents a use of the 'collection' - bool x = Visit(S->getCollection()); +void TransferFunctions::reportUninit(const DeclRefExpr *ex, + const VarDecl *vd, bool isAlwaysUnit) { + if (handler) handler->handleUseOfUninitVariable(ex, vd, isAlwaysUnit); +} - if (x == Uninitialized) - return Uninitialized; +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 = S->getElement(); - VarDecl* VD = 0; - - if (DeclStmt* DS = dyn_cast<DeclStmt>(Element)) - VD = cast<VarDecl>(DS->getSingleDecl()); + 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 { - Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens(); - // Initialize the value of the reference variable. - if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(ElemExpr)) - VD = cast<VarDecl>(DR->getDecl()); - else - return Visit(ElemExpr); + const FindVarResult &res = findBlockVarDecl(cast<Expr>(element)); + vd = res.getDecl(); + if (!vd) { + Visit(element); + return; + } } - - V(VD,AD) = Initialized; - return Initialized; + + if (vd) + vals[vd] = Initialized; } - -bool TransferFuncs:: -VisitAbstractConditionalOperator(AbstractConditionalOperator* C) { - Visit(C->getCond()); - - bool rhsResult = Visit(C->getFalseExpr()); - // Handle the GNU extension for missing LHS. - if (isa<ConditionalOperator>(C)) - return Visit(C->getTrueExpr()) & rhsResult; // Yes: we want &, not &&. - else - return rhsResult; +void TransferFunctions::VisitBlockExpr(BlockExpr *be) { + if (!flagBlockUses || !handler) + return; + const BlockDecl *bd = be->getBlockDecl(); + for (BlockDecl::capture_const_iterator i = bd->capture_begin(), + e = bd->capture_end() ; i != e; ++i) { + const VarDecl *vd = i->getVariable(); + if (!vd->hasLocalStorage()) + continue; + if (!isTrackedVar(vd)) + continue; + if (i->isByRef()) { + vals[vd] = Initialized; + continue; + } + Value v = vals[vd]; + if (isUninitialized(v)) + handler->handleUseOfUninitVariable(be, vd, isAlwaysUninit(v)); + } } -bool TransferFuncs::VisitStmt(Stmt* S) { - bool x = Initialized; - - // 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_range I = S->children(); I; ++I) - if (*I && Visit(*I) == Uninitialized) x = Uninitialized; - - return x; +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)) { + if (Expr *init = vd->getInit()) { + Visit(init); + + // If the initializer consists solely of a reference to itself, we + // explicitly mark the variable as uninitialized. This allows code + // like the following: + // + // int x = x; + // + // to deliberately leave a variable uninitialized. Different analysis + // clients can detect this pattern and adjust their reporting + // appropriately, but we need to continue to analyze subsequent uses + // of the variable. + DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(init->IgnoreParenImpCasts()); + vals[vd] = (DRE && DRE->getDecl() == vd) ? Uninitialized + : Initialized; + } + } else if (Stmt *init = vd->getInit()) { + Visit(init); + } + } + } } -bool TransferFuncs::Visit(Stmt *S) { - if (AD.isTracked(static_cast<Expr*>(S))) return V(static_cast<Expr*>(S),AD); - else return static_cast<CFGStmtVisitor<TransferFuncs,bool>*>(this)->Visit(S); +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; } -bool TransferFuncs::BlockStmt_VisitExpr(Expr* E) { - bool x = static_cast<CFGStmtVisitor<TransferFuncs,bool>*>(this)->Visit(E); - if (AD.isTracked(E)) V(E,AD) = x; - return x; +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()); + + ValueVector::reference val = vals[vd]; + if (isUninitialized(val)) { + if (bo->getOpcode() != BO_Assign) + reportUninit(res.getDeclRefExpr(), vd, isAlwaysUninit(val)); + val = Initialized; + } + return; + } + } + Visit(bo->getRHS()); + Visit(bo->getLHS()); } -} // end anonymous namespace - -//===----------------------------------------------------------------------===// -// Merge operator. -// -// In our transfer functions we take the approach that any -// combination of uninitialized values, e.g. -// Uninitialized + ___ = Uninitialized. -// -// Merges take the same approach, preferring soundness. At a confluence point, -// if any predecessor has a variable marked uninitialized, the value is -// uninitialized at the confluence point. -//===----------------------------------------------------------------------===// - -namespace { - typedef StmtDeclBitVector_Types::Union Merge; - typedef DataflowSolver<UninitializedValues,TransferFuncs,Merge> Solver; +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()); + + ValueVector::reference val = vals[vd]; + if (isUninitialized(val)) { + reportUninit(res.getDeclRefExpr(), vd, isAlwaysUninit(val)); + // Don't cascade warnings. + val = Initialized; + } + return; + } + break; + } + default: + break; + } + Visit(uo->getSubExpr()); } -//===----------------------------------------------------------------------===// -// Uninitialized values checker. Scan an AST and flag variable uses -//===----------------------------------------------------------------------===// - -UninitializedValues_ValueTypes::ObserverTy::~ObserverTy() {} - -namespace { -class UninitializedValuesChecker - : public UninitializedValues::ObserverTy { +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) { + Value val = vals[vd]; + if (isUninitialized(val)) { + reportUninit(res.getDeclRefExpr(), vd, isAlwaysUninit(val)); + // 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()); +} - ASTContext &Ctx; - Diagnostic &Diags; - llvm::SmallPtrSet<VarDecl*,10> AlreadyWarned; +void TransferFunctions::VisitUnaryExprOrTypeTraitExpr( + UnaryExprOrTypeTraitExpr *se) { + if (se->getKind() == UETT_SizeOf) { + if (se->getType()->isConstantSizeType()) + return; + // Handle VLAs. + Visit(se->getArgumentExpr()); + } +} -public: - UninitializedValuesChecker(ASTContext &ctx, Diagnostic &diags) - : Ctx(ctx), Diags(diags) {} +void TransferFunctions::VisitCXXTypeidExpr(CXXTypeidExpr *E) { + // typeid(expression) is potentially evaluated when the argument is + // a glvalue of polymorphic type. (C++ 5.2.8p2-3) + if (!E->isTypeOperand() && E->Classify(ac.getASTContext()).isGLValue()) { + QualType SubExprTy = E->getExprOperand()->getType(); + if (const RecordType *Record = SubExprTy->getAs<RecordType>()) + if (cast<CXXRecordDecl>(Record->getDecl())->isPolymorphic()) + Visit(E->getExprOperand()); + } +} - virtual void ObserveDeclRefExpr(UninitializedValues::ValTy& V, - UninitializedValues::AnalysisDataTy& AD, - DeclRefExpr* DR, VarDecl* VD) { +//------------------------------------------------------------------------====// +// High-level "driver" logic for uninitialized values analysis. +//====------------------------------------------------------------------------// + +static bool runOnBlock(const CFGBlock *block, const CFG &cfg, + AnalysisContext &ac, CFGBlockValues &vals, + llvm::BitVector &wasAnalyzed, + UninitVariablesHandler *handler = 0, + bool flagBlockUses = false) { + + wasAnalyzed[block->getBlockID()] = true; + + if (const BinaryOperator *b = getLogicalOperatorInChain(block)) { + CFGBlock::const_pred_iterator itr = block->pred_begin(); + BVPair vA = vals.getValueVectors(*itr, false); + ++itr; + BVPair vB = vals.getValueVectors(*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.updateValueVectors(block, valsAB); + } - assert ( AD.isTracked(VD) && "Unknown VarDecl."); + // 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.getValueVector(*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.updateValueVectorWithScratch(block); +} - if (V(VD,AD) == Uninitialized) - if (AlreadyWarned.insert(VD)) - Diags.Report(Ctx.getFullLoc(DR->getSourceRange().getBegin()), - diag::warn_uninit_val); +void clang::runUninitializedVariablesAnalysis(const DeclContext &dc, + const CFG &cfg, + AnalysisContext &ac, + UninitVariablesHandler &handler) { + CFGBlockValues vals(cfg); + vals.computeSetOfDeclarations(dc); + if (vals.hasNoDeclarations()) + return; + + // Mark all variables uninitialized at the entry. + const CFGBlock &entry = cfg.getEntry(); + for (CFGBlock::const_succ_iterator i = entry.succ_begin(), + e = entry.succ_end(); i != e; ++i) { + if (const CFGBlock *succ = *i) { + ValueVector &vec = vals.getValueVector(&entry, succ); + const unsigned n = vals.getNumEntries(); + for (unsigned j = 0; j < n ; ++j) { + vec[j] = Uninitialized; + } + } } -}; -} // end anonymous namespace -namespace clang { -void CheckUninitializedValues(CFG& cfg, ASTContext &Ctx, Diagnostic &Diags, - bool FullUninitTaint) { + // Proceed with the workist. + DataflowWorklist worklist(cfg); + llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); + worklist.enqueueSuccessors(&cfg.getEntry()); + llvm::BitVector wasAnalyzed(cfg.getNumBlockIDs(), false); + + while (const CFGBlock *block = worklist.dequeue()) { + // Did the block change? + bool changed = runOnBlock(block, cfg, ac, vals, wasAnalyzed); + 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) { + if (wasAnalyzed[(*BI)->getBlockID()]) + runOnBlock(*BI, cfg, ac, vals, wasAnalyzed, &handler, + /* flagBlockUses */ true); + } +} - // Compute the uninitialized values information. - UninitializedValues U(cfg); - U.getAnalysisData().FullUninitTaint = FullUninitTaint; - Solver S(U); - S.runOnCFG(cfg); +UninitVariablesHandler::~UninitVariablesHandler() {} - // Scan for DeclRefExprs that use uninitialized values. - UninitializedValuesChecker Observer(Ctx,Diags); - U.getAnalysisData().Observer = &Observer; - S.runOnAllBlocks(cfg); -} -} // end namespace clang diff --git a/lib/Analysis/UninitializedValuesV2.cpp b/lib/Analysis/UninitializedValuesV2.cpp deleted file mode 100644 index 75eccbf7a3c8..000000000000 --- a/lib/Analysis/UninitializedValuesV2.cpp +++ /dev/null @@ -1,610 +0,0 @@ -//==- 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() {} - |