| //==- UninitializedValues.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 "clang/Analysis/Analyses/UninitializedValues.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" |
| |
| using namespace clang; |
| |
| //===----------------------------------------------------------------------===// |
| // Dataflow initialization logic. |
| //===----------------------------------------------------------------------===// |
| |
| namespace { |
| |
| class RegisterDecls |
| : public CFGRecStmtDeclVisitor<RegisterDecls> { |
| |
| UninitializedValues::AnalysisDataTy& AD; |
| public: |
| RegisterDecls(UninitializedValues::AnalysisDataTy& ad) : AD(ad) {} |
| |
| void VisitVarDecl(VarDecl* VD) { AD.Register(VD); } |
| CFG& getCFG() { return AD.getCFG(); } |
| }; |
| |
| } // end anonymous namespace |
| |
| void UninitializedValues::InitializeValues(const CFG& cfg) { |
| RegisterDecls R(getAnalysisData()); |
| cfg.VisitBlockStmts(R); |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Transfer functions. |
| //===----------------------------------------------------------------------===// |
| |
| namespace { |
| class TransferFuncs |
| : public CFGStmtVisitor<TransferFuncs,bool> { |
| |
| UninitializedValues::ValTy V; |
| UninitializedValues::AnalysisDataTy& AD; |
| public: |
| TransferFuncs(UninitializedValues::AnalysisDataTy& ad) : AD(ad) {} |
| |
| UninitializedValues::ValTy& getVal() { return V; } |
| CFG& getCFG() { return AD.getCFG(); } |
| |
| void SetTopValue(UninitializedValues::ValTy& X) { |
| X.setDeclValues(AD); |
| X.resetBlkExprValues(AD); |
| } |
| |
| 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 VisitConditionalOperator(ConditionalOperator* C); |
| bool BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S); |
| |
| bool Visit(Stmt *S); |
| bool BlockStmt_VisitExpr(Expr* E); |
| |
| void VisitTerminator(CFGBlock* B) { } |
| }; |
| |
| static const bool Initialized = false; |
| static const bool Uninitialized = true; |
| |
| bool TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) { |
| |
| if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) |
| if (VD->isBlockVarDecl()) { |
| |
| if (AD.Observer) |
| AD.Observer->ObserveDeclRefExpr(V, AD, DR, VD); |
| |
| // 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. |
| |
| if (AD.FullUninitTaint) |
| return V(VD,AD); |
| } |
| |
| return Initialized; |
| } |
| |
| static VarDecl* FindBlockVarDecl(Expr* E) { |
| |
| // Blast through casts and parentheses to find any DeclRefExprs that |
| // refer to a block VarDecl. |
| |
| if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParenCasts())) |
| if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) |
| if (VD->isBlockVarDecl()) return VD; |
| |
| return NULL; |
| } |
| |
| bool TransferFuncs::VisitBinaryOperator(BinaryOperator* B) { |
| |
| if (VarDecl* VD = FindBlockVarDecl(B->getLHS())) |
| if (B->isAssignmentOp()) { |
| if (B->getOpcode() == BinaryOperator::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()); |
| } |
| |
| return VisitStmt(B); |
| } |
| |
| bool TransferFuncs::VisitDeclStmt(DeclStmt* S) { |
| for (DeclStmt::decl_iterator I=S->decl_begin(), E=S->decl_end(); I!=E; ++I) { |
| VarDecl *VD = dyn_cast<VarDecl>(*I); |
| if (VD && VD->isBlockVarDecl()) { |
| if (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; |
| } |
| } |
| } |
| return Uninitialized; // Value is never consumed. |
| } |
| |
| bool TransferFuncs::VisitCallExpr(CallExpr* C) { |
| VisitChildren(C); |
| return Initialized; |
| } |
| |
| bool TransferFuncs::VisitUnaryOperator(UnaryOperator* U) { |
| switch (U->getOpcode()) { |
| case UnaryOperator::AddrOf: { |
| VarDecl* VD = FindBlockVarDecl(U->getSubExpr()); |
| if (VD && VD->isBlockVarDecl()) |
| return V(VD,AD) = Initialized; |
| break; |
| } |
| |
| default: |
| break; |
| } |
| |
| return Visit(U->getSubExpr()); |
| } |
| |
| bool |
| TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { |
| // This represents a use of the 'collection' |
| bool x = Visit(S->getCollection()); |
| |
| if (x == Uninitialized) |
| return Uninitialized; |
| |
| // 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()); |
| 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); |
| } |
| |
| V(VD,AD) = Initialized; |
| return Initialized; |
| } |
| |
| |
| bool TransferFuncs::VisitConditionalOperator(ConditionalOperator* C) { |
| Visit(C->getCond()); |
| |
| bool rhsResult = Visit(C->getRHS()); |
| // Handle the GNU extension for missing LHS. |
| if (Expr *lhs = C->getLHS()) |
| return Visit(lhs) & rhsResult; // Yes: we want &, not &&. |
| else |
| return rhsResult; |
| } |
| |
| 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_iterator I=S->child_begin(), E=S->child_end(); I!=E; ++I) |
| if (*I && Visit(*I) == Uninitialized) x = Uninitialized; |
| |
| return x; |
| } |
| |
| 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); |
| } |
| |
| 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; |
| } |
| |
| } // 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; |
| } |
| |
| //===----------------------------------------------------------------------===// |
| // Uninitialized values checker. Scan an AST and flag variable uses |
| //===----------------------------------------------------------------------===// |
| |
| UninitializedValues_ValueTypes::ObserverTy::~ObserverTy() {} |
| |
| namespace { |
| class UninitializedValuesChecker |
| : public UninitializedValues::ObserverTy { |
| |
| ASTContext &Ctx; |
| Diagnostic &Diags; |
| llvm::SmallPtrSet<VarDecl*,10> AlreadyWarned; |
| |
| public: |
| UninitializedValuesChecker(ASTContext &ctx, Diagnostic &diags) |
| : Ctx(ctx), Diags(diags) {} |
| |
| virtual void ObserveDeclRefExpr(UninitializedValues::ValTy& V, |
| UninitializedValues::AnalysisDataTy& AD, |
| DeclRefExpr* DR, VarDecl* VD) { |
| |
| assert ( AD.isTracked(VD) && "Unknown VarDecl."); |
| |
| if (V(VD,AD) == Uninitialized) |
| if (AlreadyWarned.insert(VD)) |
| Diags.Report(Ctx.getFullLoc(DR->getSourceRange().getBegin()), |
| diag::warn_uninit_val); |
| } |
| }; |
| } // end anonymous namespace |
| |
| namespace clang { |
| void CheckUninitializedValues(CFG& cfg, ASTContext &Ctx, Diagnostic &Diags, |
| bool FullUninitTaint) { |
| |
| // Compute the uninitialized values information. |
| UninitializedValues U(cfg); |
| U.getAnalysisData().FullUninitTaint = FullUninitTaint; |
| Solver S(U); |
| S.runOnCFG(cfg); |
| |
| // Scan for DeclRefExprs that use uninitialized values. |
| UninitializedValuesChecker Observer(Ctx,Diags); |
| U.getAnalysisData().Observer = &Observer; |
| S.runOnAllBlocks(cfg); |
| } |
| } // end namespace clang |