From 13ed7fea9728a89abc8fe1530d148a3589867b4c Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Fri, 14 Sep 2007 22:49:21 +0000 Subject: [PATCH] Prototype implementation of new template-based dataflow solver. Preliminary implementation of UninitializedValues, which is based on new solver (doesn't work yet, but compiles). git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@41970 91177308-0d34-0410-b5e6-96231b3b80d8 --- Analysis/DataflowSolver.h | 221 +++++++++++++++++++ Analysis/UnintializedValues.cpp | 109 +++++++++ include/clang/Analysis/CFGVarDeclVisitor.h | 65 ++++++ include/clang/Analysis/DataflowValues.h | 120 ++++++++++ include/clang/Analysis/UninitializedValues.h | 84 +++++++ 5 files changed, 599 insertions(+) create mode 100644 Analysis/DataflowSolver.h create mode 100644 Analysis/UnintializedValues.cpp create mode 100644 include/clang/Analysis/CFGVarDeclVisitor.h create mode 100644 include/clang/Analysis/DataflowValues.h create mode 100644 include/clang/Analysis/UninitializedValues.h diff --git a/Analysis/DataflowSolver.h b/Analysis/DataflowSolver.h new file mode 100644 index 0000000000..e2150004bb --- /dev/null +++ b/Analysis/DataflowSolver.h @@ -0,0 +1,221 @@ +//===--- DataflowSolver.h - Skeleton Dataflow Analysis Code -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by Ted Kremenek and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines skeleton code for implementing dataflow analyses. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSES_DATAFLOW_SOLVER +#define LLVM_CLANG_ANALYSES_DATAFLOW_SOLVER + +#include "clang/AST/CFG.h" +#include "llvm/ADT/SmallPtrSet.h" + +namespace clang { + +//===----------------------------------------------------------------------===// +/// DataflowWorkListTy - Data structure representing the worklist used for +/// dataflow algorithms. + +class DataflowWorkListTy { + typedef llvm::SmallPtrSet BlockSet; + BlockSet wlist; +public: + /// enqueue - Add a block to the worklist. Blocks already on the worklist + /// are not added a second time. + void enqueue(const CFGBlock* B) { wlist.insert(B); } + + /// dequeue - Remove a block from the worklist. + const CFGBlock* dequeue() { + assert (!wlist.empty()); + const CFGBlock* B = *wlist.begin(); + wlist.erase(B); + return B; + } + + /// isEmpty - Return true if the worklist is empty. + bool isEmpty() const { return wlist.empty(); } +}; + +//===----------------------------------------------------------------------===// +/// DataflowSolverTy - Generic dataflow solver. +template +class DataflowSolver { + + //===--------------------------------------------------------------------===// + // Type declarations. + //===--------------------------------------------------------------------===// + +public: + typedef _DFValuesTy DFValuesTy; + typedef _TransferFuncsTy TransferFuncsTy; + typedef _MergeOperatorTy MergeOperatorTy; + + typedef typename _DFValuesTy::AnalysisDirTag AnalysisDirTag; + typedef typename _DFValuesTy::ValTy ValTy; + typedef typename _DFValuesTy::BlockDataMapTy BlockDataMapTy; + typedef typename _DFValuesTy::ObserverTy ObserverTy; + + //===--------------------------------------------------------------------===// + // External interface: constructing and running the solver. + //===--------------------------------------------------------------------===// + +public: + DataflowSolver(DFValuesTy& d, ObserverTy* o = NULL) : D(d), O(o) {} + ~DataflowSolver() {} + + /// runOnCFG - Computes dataflow values for all blocks in a CFG. + void runOnCFG(const CFG& cfg) { + // Set initial dataflow values and boundary conditions. + D.InitializeValues(cfg); + // Tag dispatch to the kind of analysis we do: forward or backwards. + SolveDataflowEquations(cfg,typename _DFValuesTy::AnalysisDirTag()); + } + + /// runOnBlock - Computes dataflow values for a given block. + /// This should usually be invoked only after previously computing + /// dataflow values using runOnCFG, as runOnBlock is intended to + /// only be used for querying the dataflow values within a block with + /// and Observer object. + void runOnBlock(const CFGBlock* B) { + TransferFuncsTy TF (D.getMetaData(),O); + ProcessBlock(B,TF,AnalysisDirTag()); + } + + //===--------------------------------------------------------------------===// + // Internal solver logic. + //===--------------------------------------------------------------------===// + +private: + + /// SolveDataflowEquations (FORWARD ANALYSIS) - Perform the actual + /// worklist algorithm to compute dataflow values. + void SolveDataflowEquations(const CFG& cfg, dataflow::forward_analysis_tag) { + // Create the worklist. + DataflowWorkListTy WorkList; + + // Enqueue the ENTRY block. + WorkList.enqueue(&cfg.getEntry()); + + // Create the state for transfer functions. + TransferFuncsTy TF(D.getMetaData(),O); + + // Process the worklist until it is empty. + while (!WorkList.isEmpty()) { + const CFGBlock* B = WorkList.dequeue(); + // If the dataflow values at the block's exit have changed, + // enqueue all successor blocks onto the worklist to have + // their values updated. + if (ProcessBlock(B,TF,AnalysisDirTag())) + for (CFGBlock::const_succ_iterator I=B->succ_begin(), E=B->succ_end(); + I != E; ++I) + WorkList.enqueue(*I); + } + } + + /// SolveDataflowEquations (BACKWARD ANALYSIS) - Perform the actual + /// worklist algorithm to compute dataflow values. + void SolveDataflowEquations(const CFG& cfg, dataflow::backward_analysis_tag) { + // Create the worklist. + DataflowWorkListTy WorkList; + + // Enqueue the EXIT block. + WorkList.enqueue(&cfg.getExit()); + + // Create the state for transfer functions. + TransferFuncsTy TF(D.getMetaData(),O); + + // Process the worklist until it is empty. + while (!WorkList.isEmpty()) { + const CFGBlock* B = WorkList.dequeue(); + // If the dataflow values at the block's entry have changed, + // enqueue all predecessor blocks onto the worklist to have + // their values updated. + if (ProcessBlock(B,TF,AnalysisDirTag())) + for (CFGBlock::const_pred_iterator I=B->pred_begin(), E=B->pred_end(); + I != E; ++I) + WorkList.enqueue(*I); + } + } + + /// ProcessBlock (FORWARD ANALYSIS) - Process the transfer functions + /// for a given block based on a forward analysis. + bool ProcessBlock(const CFGBlock* B, TransferFuncsTy& TF, + dataflow::forward_analysis_tag) { + + ValTy& V = TF.getVal(); + + // Merge dataflow values from all predecessors of this block. + V.resetValues(); + MergeOperatorTy Merge; + + for (CFGBlock::const_pred_iterator I=B->pred_begin(), + E=B->pred_end(); I!=E; ++I) + Merge(V,D.getBlockData(*I)); + + // Process the statements in the block in the forward direction. + for (CFGBlock::const_iterator I=B->begin(), E=B->end(); I!=E; ++I) + TF.BlockStmt_Visit(const_cast(*I)); + + return UpdateBlockValue(B,V); + } + + /// ProcessBlock (BACKWARD ANALYSIS) - Process the transfer functions + /// for a given block based on a forward analysis. + bool ProcessBlock(const CFGBlock* B, TransferFuncsTy& TF, + dataflow::backward_analysis_tag) { + + ValTy& V = TF.getVal(); + + // Merge dataflow values from all predecessors of this block. + V.resetValues(); + MergeOperatorTy Merge; + + for (CFGBlock::const_succ_iterator I=B->succ_begin(), + E=B->succ_end(); I!=E; ++I) + Merge(V,D.getBlockData(*I)); + + // Process the statements in the block in the forward direction. + for (CFGBlock::const_reverse_iterator I=B->begin(), E=B->end(); I!=E; ++I) + TF.BlockStmt_Visit(const_cast(*I)); + + return UpdateBlockValue(B,V); + } + + /// UpdateBlockValue - After processing the transfer functions for a block, + /// update the dataflow value associated with the block. Return true + /// if the block's value has changed. We do lazy instantiation of block + /// values, so if the block value has not been previously computed we + /// obviously return true. + bool UpdateBlockValue(const CFGBlock* B, ValTy& V) { + BlockDataMapTy& M = D.getBlockDataMap(); + typename BlockDataMapTy::iterator I = M.find(B); + + if (I == M.end()) { + M[B].copyValues(V); + return true; + } + else if (!V.equal(I->second)) { + I->second.copyValues(V); + return true; + } + + return false; + } + +private: + DFValuesTy& D; + ObserverTy* O; +}; + + +} // end namespace clang +#endif diff --git a/Analysis/UnintializedValues.cpp b/Analysis/UnintializedValues.cpp new file mode 100644 index 0000000000..58e263c12d --- /dev/null +++ b/Analysis/UnintializedValues.cpp @@ -0,0 +1,109 @@ +//==- UninitializedValues.cpp - Find Unintialized Values --------*- C++ --*-==// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by Ted Kremenek and 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/UninitializedValues.h" +#include "clang/Analysis/CFGVarDeclVisitor.h" +#include "clang/Analysis/CFGStmtVisitor.h" +#include "DataflowSolver.h" + +using namespace clang; + +//===--------------------------------------------------------------------===// +// Dataflow initialization logic. +//===--------------------------------------------------------------------===// + +namespace { + +class RegisterDecls : public CFGVarDeclVisitor { + UninitializedValues::MetaDataTy& M; +public: + RegisterDecls(const CFG& cfg, UninitializedValues::MetaDataTy& m) : + CFGVarDeclVisitor(cfg), M(m) {} + + void VisitVarDecl(VarDecl* D) { + if (M.Map.find(D) == M.Map.end()) { + M.Map[D] = M.NumDecls++; + } + } +}; + +} // end anonymous namespace + +void UninitializedValues::InitializeValues(const CFG& cfg) { + RegisterDecls R(cfg,this->getMetaData()); + R.VisitAllDecls(); + + getBlockDataMap()[ &cfg.getEntry() ].resize( getMetaData().NumDecls ); +} + +//===--------------------------------------------------------------------===// +// Transfer functions. +//===--------------------------------------------------------------------===// + +namespace { +class TransferFuncs : public CFGStmtVisitor { + UninitializedValues::ValTy V; + UninitializedValues::MetaDataTy& M; + UninitializedValues::ObserverTy* O; +public: + TransferFuncs(UninitializedValues::MetaDataTy& m, + UninitializedValues::ObserverTy* o) : M(m), O(o) { + V.resize(M.NumDecls); + } + + UninitializedValues::ValTy& getVal() { return V; } +}; +} // end anonymous namespace + +//===--------------------------------------------------------------------===// +// Merge operator. +//===--------------------------------------------------------------------===// + +namespace { +struct Merge { + void operator()(UninitializedValues::ValTy& Dst, + UninitializedValues::ValTy& Src) { + assert (Dst.size() == Src.size() && "Bitvector sizes do not match."); + Src |= Dst; + } +}; +} // end anonymous namespace + +//===--------------------------------------------------------------------===// +// Observer to flag warnings for uses of uninitialized variables. +//===--------------------------------------------------------------------===// + + + + +//===--------------------------------------------------------------------===// +// External interface (driver logic). +//===--------------------------------------------------------------------===// + +void UninitializedValues::CheckUninitializedValues(const CFG& cfg) { + + typedef DataflowSolver Solver; + + UninitializedValues U; + + { // Compute the unitialized values information. + Solver S(U); + S.runOnCFG(cfg); + } + +// WarnObserver O; + Solver S(U); + + for (CFG::const_iterator I=cfg.begin(), E=cfg.end(); I!=E; ++I) + S.runOnBlock(&*I); +} diff --git a/include/clang/Analysis/CFGVarDeclVisitor.h b/include/clang/Analysis/CFGVarDeclVisitor.h new file mode 100644 index 0000000000..75da32874e --- /dev/null +++ b/include/clang/Analysis/CFGVarDeclVisitor.h @@ -0,0 +1,65 @@ +//==- CFGVarDeclVisitor - Generic visitor of VarDecls in a CFG --*- C++ --*-==// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by Ted Kremenek and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements the template class CFGVarDeclVisitor, which provides +// a generic way to visit all the VarDecl's in a CFG. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSIS_CFG_VARDECL_VISITOR_H +#define LLVM_CLANG_ANALYSIS_CFG_VARDECL_VISITOR_H + +#include "clang/AST/StmtVisitor.h" +#include "clang/AST/Decl.h" +#include "clang/AST/Stmt.h" +#include "clang/AST/CFG.h" + +namespace clang { + +template +class CFGVarDeclVisitor : public StmtVisitor { + const CFG& cfg; +public: + CFGVarDeclVisitor(const CFG& c) : cfg(c) {} + + void VisitStmt(Stmt* S) { + for (Stmt::child_iterator I=S->child_begin(), E=S->child_end(); I!=E; ++I) + static_cast(this)->Visit(*I); + } + + void VisitDeclRefExpr(DeclRefExpr* DR) { + static_cast(this)->VisitDeclChain(DR->getDecl()); + } + + void VisitDeclStmt(DeclStmt* DS) { + static_cast(this)->VisitDeclChain(DS->getDecl()); + } + + void VisitDeclChain(ScopedDecl* D) { + for (; D != NULL ; D = D->getNextDeclarator()) + static_cast(this)->VisitScopedDecl(D); + } + + void VisitScopedDecl(ScopedDecl* D) { + if (VarDecl* V = dyn_cast(D)) + static_cast(this)->VisitVarDecl(V); + } + + void VisitVarDecl(VarDecl* D) {} + + void VisitAllDecls() { + for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) + for (CFGBlock::const_iterator SI=BI->begin(),SE = BI->end();SI != SE;++SI) + static_cast(this)->Visit(const_cast(*SI)); + } +}; + +} // end namespace clang + +#endif diff --git a/include/clang/Analysis/DataflowValues.h b/include/clang/Analysis/DataflowValues.h new file mode 100644 index 0000000000..118c588b4f --- /dev/null +++ b/include/clang/Analysis/DataflowValues.h @@ -0,0 +1,120 @@ +//===--- DataflowValues.h - Data structure for dataflow values --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by Ted Kremenek and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines a skeleton data structure for encapsulating the dataflow +// values for a CFG. Typically this is subclassed to provide methods for +// computing these values from a CFG. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_ANALYSES_DATAFLOW_VALUES +#define LLVM_CLANG_ANALYSES_DATAFLOW_VALUES + +#include "clang/AST/CFG.h" +#include "llvm/ADT/DenseMap.h" + +namespace clang { + +namespace dataflow { + + //===----------------------------------------------------------------------===// + /// Dataflow Directional Tag Classes. These are used for tag dispatching + /// within the dataflow solver/transfer functions to determine what direction + /// a dataflow analysis flows. + //===----------------------------------------------------------------------===// + + struct forward_analysis_tag {}; + struct backward_analysis_tag {}; + +} // end namespace dataflow + + +template +class DataflowValues { + + //===--------------------------------------------------------------------===// + // Type declarations. + //===--------------------------------------------------------------------===// + +public: + typedef typename TypeClass::ValTy ValTy; + typedef typename TypeClass::MetaDataTy MetaDataTy; + typedef typename TypeClass::ObserverTy ObserverTy; + + typedef _AnalysisDirTag AnalysisDirTag; + typedef llvm::DenseMap BlockDataMapTy; + + //===--------------------------------------------------------------------===// + // Predicates. + //===--------------------------------------------------------------------===// + +public: + /// isForwardAnalysis - Returns true if the dataflow values are computed + /// from a forward analysis. If this returns true, the value returned + /// from getBlockData() is the dataflow values associated with the END of + /// the block. + bool isForwardAnalysis() { return isForwardAnalysis(AnalysisDirTag()); } + + /// isBackwardAnalysis - Returns true if the dataflow values are computed + /// from a backward analysis. If this returns true, the value returned + /// from getBlockData() is the dataflow values associated with the ENTRY of + /// the block. + bool isBackwardAnalysis() { return !isForwardAnalysis(); } + +private: + bool isForwardAnalysis(dataflow::forward_analysis_tag) { return true; } + bool isForwardAnalysis(dataflow::backward_analysis_tag) { return false; } + + //===--------------------------------------------------------------------===// + // Initialization and accessors methods. + //===--------------------------------------------------------------------===// + +public: + /// InitializeValues - Invoked by the solver to initialize state needed for + /// dataflow analysis. This method is usually specialized by subclasses. + void InitializeValues(const CFG& cfg) {}; + + /// getBlockData - Retrieves the dataflow values associated with a + /// specified CFGBlock. If the dataflow analysis is a forward analysis, + /// this data is associated with the END of the block. If the analysis + /// is a backwards analysis, it is associated with the ENTRY of the block. + ValTy& getBlockData(const CFGBlock* B) { + typename BlockDataMapTy::iterator I = BlockDataMap.find(B); + assert (I != BlockDataMap.end() && "No data associated with CFGBlock."); + return I->second; + } + + const ValTy& getBlockData(const CFGBlock*) const { + return reinterpret_cast(this)->getBlockData(); + } + + /// getBlockDataMap - Retrieves the internal map between CFGBlocks and + /// dataflow values. Usually used by a dataflow solver to compute + /// values for blocks. + BlockDataMapTy& getBlockDataMap() { return BlockDataMap; } + const BlockDataMapTy& getBlockDataMap() const { return BlockDataMap; } + + /// getMetaData - Retrieves the meta data associated with a dataflow analysis. + /// This is typically consumed by transfer function code (via the solver). + /// This can also be used by subclasses to interpret the dataflow values. + MetaDataTy& getMetaData() { return Meta; } + const MetaDataTy& getMetaData() const { return Meta; } + + //===--------------------------------------------------------------------===// + // Internal data. + //===--------------------------------------------------------------------===// + +protected: + BlockDataMapTy BlockDataMap; + MetaDataTy Meta; +}; + +} // end namespace clang +#endif diff --git a/include/clang/Analysis/UninitializedValues.h b/include/clang/Analysis/UninitializedValues.h new file mode 100644 index 0000000000..c7067e035c --- /dev/null +++ b/include/clang/Analysis/UninitializedValues.h @@ -0,0 +1,84 @@ +//===- UninitializedValues.h - unintialized values analysis ----*- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by Ted Kremenek and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file provides the interface for the Unintialized Values analysis, +// a flow-sensitive analysis that detects when variable values are unintialized. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_UNITVALS_H +#define LLVM_CLANG_UNITVALS_H + +#include "llvm/ADT/BitVector.h" +#include "clang/Analysis/DataflowValues.h" + +namespace clang { + + class VarDecl; + +/// UninitializedValuesTypes - Utility class to wrap type declarations +/// used for defining the UninitializedValues class. +class UninitializedValuesTypes { +public: + class ValTy { + llvm::BitVector BV; + public: + // Accessors to internal bitvector. + unsigned size() const { return BV.size(); } + void resize(unsigned i) { BV.resize(i); } + llvm::BitVector::reference operator[](unsigned i) { return BV[i]; } + void operator|=(const ValTy& RHS) { BV |= RHS.BV; } + + // Used by the solver. + void resetValues() { BV.reset(); } + bool equal(ValTy& RHS) const { return BV == RHS.BV; } + void copyValues(ValTy& RHS) { BV = RHS.BV; } + }; + + struct MetaDataTy { + llvm::DenseMap Map; + unsigned NumDecls; + + MetaDataTy() : NumDecls(0) {} + }; + + class ObserverTy { + virtual ~ObserverTy(); + virtual void ObserveStmt(Stmt* S, MetaDataTy& M, ValTy& V) {} + virtual void ObserveBlockExit(const CFGBlock* B, MetaDataTy& M, ValTy& V) {} + }; +}; + + +/// UninitializedValues - Objects of this class encapsulate dataflow analysis +/// information regarding what variable declarations in a function are +/// potentially unintialized. +class UninitializedValues : public DataflowValues { + + //===--------------------------------------------------------------------===// + // Public interface. + //===--------------------------------------------------------------------===// + + static void CheckUninitializedValues(const CFG& cfg); + + //===--------------------------------------------------------------------===// + // Internal logic. + //===--------------------------------------------------------------------===// + +private: + UninitializedValues() {} + +public: + /// IntializeValues - Create initial dataflow values and meta data for + /// a given CFG. This is intended to be called by the dataflow solver. + void InitializeValues(const CFG& cfg); +}; + +} // end namespace clang +#endif -- 2.40.0