From 610068c8cd2321f90e147b12cf794e1f840b6405 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Sat, 15 Jan 2011 02:58:47 +0000 Subject: [PATCH] Add initial prototype for implementation of -Wuninitialized based on CFG dataflow analysis. WIP. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@123512 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Analysis/Analyses/UninitializedValuesV2.h | 38 ++ include/clang/Basic/DiagnosticSemaKinds.td | 2 + lib/Analysis/CMakeLists.txt | 1 + lib/Analysis/UninitializedValuesV2.cpp | 362 ++++++++++++++++++ lib/Sema/AnalysisBasedWarnings.cpp | 30 ++ test/Sema/uninit-variables.c | 88 +++++ 6 files changed, 521 insertions(+) create mode 100644 include/clang/Analysis/Analyses/UninitializedValuesV2.h create mode 100644 lib/Analysis/UninitializedValuesV2.cpp create mode 100644 test/Sema/uninit-variables.c diff --git a/include/clang/Analysis/Analyses/UninitializedValuesV2.h b/include/clang/Analysis/Analyses/UninitializedValuesV2.h new file mode 100644 index 0000000000..65390b644e --- /dev/null +++ b/include/clang/Analysis/Analyses/UninitializedValuesV2.h @@ -0,0 +1,38 @@ +//= UninitializedValuesV2.h - Finding uses of 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 defines APIs for invoking and reported uninitialized values +// warnings. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_UNINIT_VALS_H +#define LLVM_CLANG_UNINIT_VALS_H + +namespace clang { + +class CFG; +class DeclContext; +class DeclRefExpr; +class VarDecl; + +class UninitVariablesHandler { +public: + UninitVariablesHandler() {} + virtual ~UninitVariablesHandler(); + + virtual void handleUseOfUninitVariable(const DeclRefExpr *dr, + const VarDecl *vd) {} +}; + +void runUninitializedVariablesAnalysis(const DeclContext &dc, const CFG &cfg, + UninitVariablesHandler &handler); + +} +#endif diff --git a/include/clang/Basic/DiagnosticSemaKinds.td b/include/clang/Basic/DiagnosticSemaKinds.td index a5a3d83833..aaccaabd75 100644 --- a/include/clang/Basic/DiagnosticSemaKinds.td +++ b/include/clang/Basic/DiagnosticSemaKinds.td @@ -815,6 +815,8 @@ def note_uninit_reference_member : Note< "uninitialized reference member is here">; def warn_field_is_uninit : Warning<"field is uninitialized when used here">, InGroup>; +def warn_var_is_uninit : Warning<"use of uninitialized variable %0">, + InGroup>, DefaultIgnore; def err_init_incomplete_type : Error<"initialization of incomplete type %0">; def err_temp_copy_no_viable : Error< diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index 1709f6d6b7..a7bd8c193f 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -14,6 +14,7 @@ add_clang_library(clangAnalysis ReachableCode.cpp ScanfFormatString.cpp UninitializedValues.cpp + UninitializedValuesV2.cpp ) add_dependencies(clangAnalysis ClangAttrClasses ClangAttrList diff --git a/lib/Analysis/UninitializedValuesV2.cpp b/lib/Analysis/UninitializedValuesV2.cpp new file mode 100644 index 0000000000..da94490bca --- /dev/null +++ b/lib/Analysis/UninitializedValuesV2.cpp @@ -0,0 +1,362 @@ +//==- 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 "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/Visitors/CFGRecStmtDeclVisitor.h" +#include "clang/Analysis/Analyses/UninitializedValuesV2.h" + +using namespace clang; + +//------------------------------------------------------------------------====// +// DeclToBit: a mapping from Decls we track to bitvector indices. +//====------------------------------------------------------------------------// + +namespace { +class DeclToBit { + llvm::DenseMap 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 getBitVectorIndex(const VarDecl *d); +}; +} + +void DeclToBit::computeMap(const DeclContext &dc) { + unsigned count = 0; + DeclContext::specific_decl_iterator I(dc.decls_begin()), + E(dc.decls_end()); + for ( ; I != E; ++I) { + const VarDecl *vd = *I; + if (vd->isLocalVarDecl() && !vd->hasGlobalStorage()) + map[vd] = count++; + } +} + +llvm::Optional DeclToBit::getBitVectorIndex(const VarDecl *d) { + llvm::DenseMap::iterator I = map.find(d); + if (I == map.end()) + return llvm::Optional(); + return I->second; +} + +//------------------------------------------------------------------------====// +// CFGBlockValues: dataflow values for CFG blocks. +//====------------------------------------------------------------------------// + +namespace { +class CFGBlockValues { + const CFG &cfg; + llvm::BitVector **vals; + llvm::BitVector scratch; + DeclToBit declToBit; +public: + CFGBlockValues(const CFG &cfg); + ~CFGBlockValues(); + + void computeSetOfDeclarations(const DeclContext &dc); + llvm::BitVector &getBitVector(const CFGBlock *block); + void mergeIntoScratch(llvm::BitVector const &source, bool isFirst); + bool updateBitVectorWithScratch(const CFGBlock *block); + + bool hasNoDeclarations() const { + return declToBit.size() == 0; + } + + void resetScratch(); + 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 llvm::BitVector*[n]; + bzero(vals, sizeof(*vals) * n); +} + +CFGBlockValues::~CFGBlockValues() { + unsigned n = cfg.getNumBlockIDs(); + if (n == 0) + return; + for (unsigned i = 0; i < n; ++i) + delete vals[i]; + delete [] vals; +} + +void CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { + declToBit.computeMap(dc); + scratch.resize(declToBit.size()); +} + +llvm::BitVector &CFGBlockValues::getBitVector(const CFGBlock *block) { + unsigned idx = block->getBlockID(); + llvm::BitVector *bv = vals[idx]; + if (!bv) { + bv = new llvm::BitVector(declToBit.size()); + vals[idx] = bv; + } + return *bv; +} + +void CFGBlockValues::mergeIntoScratch(llvm::BitVector const &source, + bool isFirst) { + if (isFirst) + scratch = source; + else + scratch &= source; +} + +bool CFGBlockValues::updateBitVectorWithScratch(const CFGBlock *block) { + llvm::BitVector &dst = getBitVector(block); + bool changed = (dst != scratch); + if (changed) + dst = scratch; + return changed; +} + +void CFGBlockValues::resetScratch() { + scratch.reset(); +} + +llvm::BitVector::reference CFGBlockValues::operator[](const VarDecl *vd) { + const llvm::Optional &idx = declToBit.getBitVectorIndex(vd); + assert(idx.hasValue()); + return scratch[idx.getValue()]; +} + +//------------------------------------------------------------------------====// +// Worklist: worklist for dataflow analysis. +//====------------------------------------------------------------------------// + +namespace { +class DataflowWorklist { + llvm::SmallVector 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) { + 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 = true; +static const bool Uninitialized = false; + +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 { + CFGBlockValues &vals; + const CFG &cfg; + UninitVariablesHandler *handler; +public: + TransferFunctions(CFGBlockValues &vals, const CFG &cfg, + UninitVariablesHandler *handler) + : vals(vals), cfg(cfg), handler(handler) {} + + const CFG &getCFG() { return cfg; } + void reportUninit(const DeclRefExpr *ex, const VarDecl *vd); + + void VisitDeclStmt(DeclStmt *ds); + void VisitUnaryOperator(UnaryOperator *uo); + void VisitBinaryOperator(BinaryOperator *bo); + void VisitCastExpr(CastExpr *ce); +}; +} + +void TransferFunctions::reportUninit(const DeclRefExpr *ex, + const VarDecl *vd) { + if (handler) handler->handleUseOfUninitVariable(ex, 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(*DI)) { + if (vd->isLocalVarDecl() && !vd->hasGlobalStorage()) { + if (Stmt *init = vd->getInit()) { + vals[vd] = Initialized; + Visit(init); + } + } + } + } +} + +static FindVarResult findBlockVarDecl(Expr* ex) { + if (DeclRefExpr* dr = dyn_cast(ex->IgnoreParenCasts())) + if (VarDecl *vd = dyn_cast(dr->getDecl())) + if (vd->isLocalVarDecl() && !vd->hasGlobalStorage()) + return FindVarResult(vd, dr); + + return FindVarResult(0, 0); +} + +void TransferFunctions::VisitBinaryOperator(clang::BinaryOperator *bo) { + Visit(bo->getRHS()); + Visit(bo->getLHS()); + if (bo->isAssignmentOp()) { + const FindVarResult &res = findBlockVarDecl(bo->getLHS()); + if (const VarDecl* vd = res.getDecl()) { + llvm::BitVector::reference bit = vals[vd]; + if (bit == Uninitialized) { + if (bo->getOpcode() != BO_Assign) + reportUninit(res.getDeclRefExpr(), vd); + bit = Initialized; + } + } + } +} + +void TransferFunctions::VisitUnaryOperator(clang::UnaryOperator *uo) { + Visit(uo->getSubExpr()); + switch (uo->getOpcode()) { + case clang::UO_AddrOf: + if (const VarDecl *vd = findBlockVarDecl(uo->getSubExpr()).getDecl()) + vals[vd] = Initialized; + break; + 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()) { + llvm::BitVector::reference bit = vals[vd]; + if (bit == Uninitialized) { + reportUninit(res.getDeclRefExpr(), vd); + bit = Initialized; + } + } + break; + } + default: + break; + } +} + +void TransferFunctions::VisitCastExpr(clang::CastExpr *ce) { + Visit(ce->getSubExpr()); + if (ce->getCastKind() == CK_LValueToRValue) { + const FindVarResult &res = findBlockVarDecl(ce->getSubExpr()); + if (const VarDecl *vd = res.getDecl()) + if (vals[vd] == Uninitialized) + reportUninit(res.getDeclRefExpr(), vd); + } +} + +//------------------------------------------------------------------------====// +// High-level "driver" logic for uninitialized values analysis. +//====------------------------------------------------------------------------// + +static void runOnBlock(const CFGBlock *block, const CFG &cfg, + CFGBlockValues &vals, + UninitVariablesHandler *handler = 0) { + // 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), isFirst); + isFirst = false; + } + // Apply the transfer function. + TransferFunctions tf(vals, cfg, handler); + for (CFGBlock::const_iterator I = block->begin(), E = block->end(); + I != E; ++I) { + if (const CFGStmt *cs = dyn_cast(&*I)) { + tf.BlockStmt_Visit(cs->getStmt()); + } + } +} + +void clang::runUninitializedVariablesAnalysis(const DeclContext &dc, + const CFG &cfg, + 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()) { + runOnBlock(block, cfg, vals); + // Did the block change? + bool changed = vals.updateBitVectorWithScratch(block); + 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, vals, &handler); + } +} + +UninitVariablesHandler::~UninitVariablesHandler() {} + diff --git a/lib/Sema/AnalysisBasedWarnings.cpp b/lib/Sema/AnalysisBasedWarnings.cpp index 20a503d6a5..14d75338e0 100644 --- a/lib/Sema/AnalysisBasedWarnings.cpp +++ b/lib/Sema/AnalysisBasedWarnings.cpp @@ -25,6 +25,7 @@ #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/Analyses/ReachableCode.h" +#include "clang/Analysis/Analyses/UninitializedValuesV2.h" #include "llvm/ADT/BitVector.h" #include "llvm/Support/Casting.h" @@ -343,6 +344,23 @@ static void CheckFallThroughForBody(Sema &S, const Decl *D, const Stmt *Body, } } +//===----------------------------------------------------------------------===// +// -Wuninitialized +//===----------------------------------------------------------------------===// + +namespace { +class UninitValsDiagReporter : public UninitVariablesHandler { + Sema &S; +public: + UninitValsDiagReporter(Sema &S) : S(S) {} + + void handleUseOfUninitVariable(const DeclRefExpr *dr, const VarDecl *vd) { + S.Diag(dr->getLocStart(), diag::warn_var_is_uninit) + << vd->getDeclName() << dr->getSourceRange(); + } +}; +} + //===----------------------------------------------------------------------===// // AnalysisBasedWarnings - Worker object used by Sema to execute analysis-based // warnings on a function, method, or block. @@ -406,6 +424,18 @@ AnalysisBasedWarnings::IssueWarnings(sema::AnalysisBasedWarnings::Policy P, // Warning: check for unreachable code if (P.enableCheckUnreachable) CheckUnreachable(S, AC); + + if (Diags.getDiagnosticLevel(diag::warn_var_is_uninit, D->getLocStart()) + != Diagnostic::Ignored) { + if (!S.getLangOptions().CPlusPlus) { + CFG *cfg = AC.getCFG(); + if (cfg) { + UninitValsDiagReporter reporter(S); + runUninitializedVariablesAnalysis(*cast(D), *cfg, + reporter); + } + } + } } void clang::sema:: diff --git a/test/Sema/uninit-variables.c b/test/Sema/uninit-variables.c new file mode 100644 index 0000000000..c2d98c40fe --- /dev/null +++ b/test/Sema/uninit-variables.c @@ -0,0 +1,88 @@ +// RUN: %clang -Wuninitialized-experimental -fsyntax-only %s + +int test1() { + int x; + return x; // expected-warning{{use of uninitialized variable 'x'}} +} + +int test2() { + int x = 0; + return x; // no-warning +} + +int test3() { + int x; + x = 0; + return x; // no-warning +} + +int test4() { + int x; + ++x; // expected-warning{{use of uninitialized variable 'x'}} + return x; +} + +int test5() { + int x, y; + x = y; // expected-warning{{use of uninitialized variable 'y'}} + return x; +} + +int test6() { + int x; + x += 2; // expected-warning{{use of uninitialized variable 'x'}} + return x; +} + +int test7(int y) { + int x; + if (y) + x = 1; + return x; // expected-warning{{use of uninitialized variable 'x'}} +} + +int test8(int y) { + int x; + if (y) + x = 1; + else + x = 0; + return x; // no-warning +} + +int test9(int n) { + int x; + for (unsigned i = 0 ; i < n; ++i) { + if (i == n - 1) + break; + x = 1; + } + return x; // expected-warning{{use of uninitialized variable 'x'}} +} + +int test10(unsigned n) { + int x; + for (unsigned i = 0 ; i < n; ++i) { + x = 1; + } + return x; // expected-warning{{use of uninitialized variable 'x'}} +} + +int test11(unsigned n) { + int x; + for (unsigned i = 0 ; i <= n; ++i) { + x = 1; + } + return x; // expected-warning{{use of uninitialized variable 'x'}} +} + +void test12(unsigned n) { + for (unsigned i ; n ; ++i) ; // expected-warning{{use of uninitialized variable 'i'}} +} + +int test13() { + static int i; + return i; // no-warning +} + + -- 2.40.0