From 105bfee9d691b56bfa75a7c44b411533c5a369f0 Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Tue, 18 Sep 2007 18:02:44 +0000 Subject: [PATCH] Modified DataFlowValues and DataflowSolver to associate dataflow value with CFG *edges* instead of blocks. This will fascilitate dataflow analyses that are sensitive to block terminators, and also simplifies some reasoning. Updated UninitializedValues to comply to this new interface. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@42099 91177308-0d34-0410-b5e6-96231b3b80d8 --- Analysis/DataflowSolver.h | 152 ++++++++++++++---------- Analysis/UninitializedValues.cpp | 4 - include/clang/Analysis/DataflowValues.h | 85 ++++++++----- 3 files changed, 146 insertions(+), 95 deletions(-) diff --git a/Analysis/DataflowSolver.h b/Analysis/DataflowSolver.h index 5266af3407..e2c4f16a51 100644 --- a/Analysis/DataflowSolver.h +++ b/Analysis/DataflowSolver.h @@ -61,7 +61,7 @@ public: typedef typename _DFValuesTy::AnalysisDirTag AnalysisDirTag; typedef typename _DFValuesTy::ValTy ValTy; - typedef typename _DFValuesTy::BlockDataMapTy BlockDataMapTy; + typedef typename _DFValuesTy::EdgeDataMapTy EdgeDataMapTy; //===--------------------------------------------------------------------===// // External interface: constructing and running the solver. @@ -75,8 +75,9 @@ public: 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()); + // Solve the dataflow equations. This will populate D.EdgeDataMap + // with dataflow values. + SolveDataflowEquations(cfg); } /// runOnBlock - Computes dataflow values for a given block. @@ -85,7 +86,7 @@ public: /// only be used for querying the dataflow values within a block with /// and Observer object. void runOnBlock(const CFGBlock* B) { - if (D.getBlockDataMap().find(B) == D.getBlockDataMap().end()) + if (!hasData(B,AnalysisDirTag())) return; TransferFuncsTy TF (D.getAnalysisData()); @@ -98,39 +99,11 @@ public: 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.getAnalysisData()); - - // 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 + /// SolveDataflowEquations - 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()); + void SolveDataflowEquations(const CFG& cfg) { + + EnqueueFirstBlock(cfg,AnalysisDirTag()); // Create the state for transfer functions. TransferFuncsTy TF(D.getAnalysisData()); @@ -141,16 +114,22 @@ private: // 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(B,TF,AnalysisDirTag()); + UpdateEdges(B,TF.getVal(),AnalysisDirTag()); } } + void EnqueueFirstBlock(const CFG& cfg, dataflow::forward_analysis_tag) { + WorkList.enqueue(&cfg.getEntry()); + } + + void EnqueueFirstBlock(const CFG& cfg, dataflow::backward_analysis_tag) { + WorkList.enqueue(&cfg.getExit()); + } + /// ProcessBlock (FORWARD ANALYSIS) - Process the transfer functions /// for a given block based on a forward analysis. - bool ProcessBlock(const CFGBlock* B, TransferFuncsTy& TF, + void ProcessBlock(const CFGBlock* B, TransferFuncsTy& TF, dataflow::forward_analysis_tag) { ValTy& V = TF.getVal(); @@ -159,12 +138,12 @@ private: V.resetValues(D.getAnalysisData()); MergeOperatorTy Merge; - BlockDataMapTy& M = D.getBlockDataMap(); + EdgeDataMapTy& M = D.getEdgeDataMap(); bool firstMerge = true; for (CFGBlock::const_pred_iterator I=B->pred_begin(), E=B->pred_end(); I!=E; ++I) { - typename BlockDataMapTy::iterator BI = M.find(*I); + typename EdgeDataMapTy::iterator BI = M.find(CFG::Edge(*I,B)); if (BI != M.end()) { if (firstMerge) { firstMerge = false; @@ -177,14 +156,12 @@ private: // 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); + TF.BlockStmt_Visit(const_cast(*I)); } /// ProcessBlock (BACKWARD ANALYSIS) - Process the transfer functions /// for a given block based on a forward analysis. - bool ProcessBlock(const CFGBlock* B, TransferFuncsTy& TF, + void ProcessBlock(const CFGBlock* B, TransferFuncsTy& TF, dataflow::backward_analysis_tag) { ValTy& V = TF.getVal(); @@ -193,12 +170,12 @@ private: V.resetValues(D.getAnalysisData()); MergeOperatorTy Merge; - BlockDataMapTy& M = D.getBlockDataMap(); + EdgeDataMapTy& M = D.getEdgeDataMap(); bool firstMerge = true; for (CFGBlock::const_succ_iterator I=B->succ_begin(), E=B->succ_end(); I!=E; ++I) { - typename BlockDataMapTy::iterator BI = M.find(*I); + typename EdgeDataMapTy::iterator BI = M.find(CFG::Edge(B,*I)); if (BI != M.end()) { if (firstMerge) { firstMerge = false; @@ -211,34 +188,81 @@ private: // 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); + TF.BlockStmt_Visit(const_cast(*I)); + } + + /// UpdateEdges (FORWARD ANALYSIS) - After processing the transfer + /// functions for a block, update the dataflow value associated with the + /// block's outgoing edges. Enqueue any successor blocks for an + /// outgoing edge whose value has changed. + void UpdateEdges(const CFGBlock* B, ValTy& V,dataflow::forward_analysis_tag) { + for (CFGBlock::const_succ_iterator I=B->succ_begin(), E=B->succ_end(); + I!=E; ++I) { + + CFG::Edge E(B,*I); + UpdateEdgeValue(E,V,*I); + } } - /// 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); - + /// UpdateEdges (BACKWARD ANALYSIS) - After processing the transfer + /// functions for a block, update the dataflow value associated with the + /// block's incoming edges. Enqueue any predecessor blocks for an + /// outgoing edge whose value has changed. + void UpdateEdges(const CFGBlock* B, ValTy& V,dataflow::backward_analysis_tag){ + for (CFGBlock::const_pred_iterator I=B->succ_begin(), E=B->succ_end(); + I!=E; ++I) { + + CFG::Edge E(*I,B); + UpdateEdgeValue(E,V,*I); + } + } + + /// UpdateEdgeValue - Update the value associated with a given edge. + void UpdateEdgeValue(CFG::Edge& E, ValTy& V, const CFGBlock* TargetBlock) { + + EdgeDataMapTy& M = D.getEdgeDataMap(); + typename EdgeDataMapTy::iterator I = M.find(E); + if (I == M.end()) { - M[B].copyValues(V); - return true; + // First value for this edge. + M[E].copyValues(V); + WorkList.enqueue(TargetBlock); } else if (!V.equal(I->second)) { I->second.copyValues(V); - return true; + WorkList.enqueue(TargetBlock); } + } + + /// hasData (FORWARD ANALYSIS) - Is there any dataflow values associated + /// with the incoming edges of a block? + bool hasData(const CFGBlock* B, dataflow::forward_analysis_tag) { + EdgeDataMapTy& M = D.getEdgeDataMap(); + + for (CFGBlock::const_pred_iterator I=B->pred_begin(), E=B->pred_end(); + I!=E; ++I) + if (M.find(CFG::Edge(*I,B)) != M.end()) + return true; + + return false; + } + + /// hasData (BACKWARD ANALYSIS) - Is there any dataflow values associated + /// with the outgoing edges of a block? + bool hasData(const CFGBlock* B, dataflow::backward_analysis_tag) { + EdgeDataMapTy& M = D.getEdgeDataMap(); + + for (CFGBlock::const_succ_iterator I=B->succ_begin(), E=B->succ_end(); + I!=E; ++I) + if (M.find(CFG::Edge(B,*I)) != M.end()) + return true; return false; } private: DFValuesTy& D; + DataflowWorkListTy WorkList; }; diff --git a/Analysis/UninitializedValues.cpp b/Analysis/UninitializedValues.cpp index c5b13a4074..c472b3a846 100644 --- a/Analysis/UninitializedValues.cpp +++ b/Analysis/UninitializedValues.cpp @@ -73,10 +73,6 @@ void UninitializedValues::InitializeValues(const CFG& cfg) { for (CFG::const_iterator I=cfg.begin(), E=cfg.end(); I!=E; ++I) for (CFGBlock::const_iterator BI=I->begin(), BE=I->end(); BI!=BE; ++BI) R.BlockStmt_Visit(*BI); - - // Initialize the values of the last block. -// UninitializedValues::ValTy& V = getBlockDataMap()[&cfg.getEntry()]; -// V.resetValues(getAnalysisData()); } //===----------------------------------------------------------------------===// diff --git a/include/clang/Analysis/DataflowValues.h b/include/clang/Analysis/DataflowValues.h index 0b7849bbb0..95ee094153 100644 --- a/include/clang/Analysis/DataflowValues.h +++ b/include/clang/Analysis/DataflowValues.h @@ -19,22 +19,57 @@ #include "clang/AST/CFG.h" #include "llvm/ADT/DenseMap.h" -namespace clang { +//===----------------------------------------------------------------------===// +// DenseMapInfo for CFG::Edge for use with DenseMap +//===----------------------------------------------------------------------===// -namespace dataflow { +namespace llvm { - //===----------------------------------------------------------------------===// - /// Dataflow Directional Tag Classes. These are used for tag dispatching - /// within the dataflow solver/transfer functions to determine what direction - /// a dataflow analysis flows. - //===----------------------------------------------------------------------===// + template <> struct DenseMapInfo { + static inline clang::CFG::Edge getEmptyKey() { + return clang::CFG::Edge(NULL,NULL); + } + + static inline clang::CFG::Edge getTombstoneKey() { + return clang::CFG::Edge(NULL,reinterpret_cast(-1)); + } + + static unsigned getHashValue(const clang::CFG::Edge& E) { + const clang::CFGBlock* P1 = E.getSrc(); + const clang::CFGBlock* P2 = E.getDst(); + return (reinterpret_cast(P1) >> 4) ^ + (reinterpret_cast(P1) >> 9) ^ + (reinterpret_cast(P2) >> 5) ^ + (reinterpret_cast(P2) >> 10); + } + + static bool isEqual(const clang::CFG::Edge& LHS, + const clang::CFG::Edge& RHS) { + return LHS == RHS; + } + + static bool isPod() { return true; } + }; +} // end namespace llvm + +//===----------------------------------------------------------------------===// +/// Dataflow Directional Tag Classes. These are used for tag dispatching +/// within the dataflow solver/transfer functions to determine what direction +/// a dataflow analysis flows. +//===----------------------------------------------------------------------===// + +namespace clang { +namespace dataflow { struct forward_analysis_tag {}; struct backward_analysis_tag {}; - } // end namespace dataflow +//===----------------------------------------------------------------------===// +/// DataflowValues. Container class to store dataflow values for a CFG. +//===----------------------------------------------------------------------===// + template class DataflowValues { @@ -46,8 +81,8 @@ class DataflowValues { public: typedef typename ValueTypes::ValTy ValTy; typedef typename ValueTypes::AnalysisDataTy AnalysisDataTy; - typedef _AnalysisDirTag AnalysisDirTag; - typedef llvm::DenseMap BlockDataMapTy; + typedef _AnalysisDirTag AnalysisDirTag; + typedef llvm::DenseMap EdgeDataMapTy; //===--------------------------------------------------------------------===// // Predicates. @@ -55,19 +90,15 @@ public: 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. + /// from a forward analysis. 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. + /// from a backward analysis. bool isBackwardAnalysis() { return !isForwardAnalysis(); } private: - bool isForwardAnalysis(dataflow::forward_analysis_tag) { return true; } + bool isForwardAnalysis(dataflow::forward_analysis_tag) { return true; } bool isForwardAnalysis(dataflow::backward_analysis_tag) { return false; } //===--------------------------------------------------------------------===// @@ -79,25 +110,25 @@ public: /// dataflow analysis. This method is usually specialized by subclasses. void InitializeValues(const CFG& cfg) {}; - /// getBlockData - Retrieves the dataflow values associated with a + /// getEdgeData - 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."); + ValTy& getEdgeData(const CFG::Edge& E) { + typename EdgeDataMapTy::iterator I = EdgeDataMap.find(E); + assert (I != EdgeDataMap.end() && "No data associated with Edge."); return I->second; } - const ValTy& getBlockData(const CFGBlock*) const { - return reinterpret_cast(this)->getBlockData(); + const ValTy& getEdgeData(const CFG::Edge& E) const { + return reinterpret_cast(this)->getEdgeData(E); } - /// getBlockDataMap - Retrieves the internal map between CFGBlocks and + /// getEdgeDataMap - 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; } + EdgeDataMapTy& getEdgeDataMap() { return EdgeDataMap; } + const EdgeDataMapTy& getEdgeDataMap() const { return EdgeDataMap; } /// getAnalysisData - Retrieves the meta data associated with a /// dataflow analysis for analyzing a particular CFG. @@ -111,7 +142,7 @@ public: //===--------------------------------------------------------------------===// protected: - BlockDataMapTy BlockDataMap; + EdgeDataMapTy EdgeDataMap; AnalysisDataTy AnalysisData; }; -- 2.50.1