From 33b7885c8287317c464729e9f05e836a23830b7b Mon Sep 17 00:00:00 2001 From: Richard Smith Date: Mon, 19 May 2014 22:20:41 +0000 Subject: [PATCH] [module] Remove a header that isn't used and doesn't compile. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@209168 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Analysis/FlowSensitive/DataflowSolver.h | 342 ------------------ 1 file changed, 342 deletions(-) delete mode 100644 include/clang/Analysis/FlowSensitive/DataflowSolver.h diff --git a/include/clang/Analysis/FlowSensitive/DataflowSolver.h b/include/clang/Analysis/FlowSensitive/DataflowSolver.h deleted file mode 100644 index 5b99f1d882..0000000000 --- a/include/clang/Analysis/FlowSensitive/DataflowSolver.h +++ /dev/null @@ -1,342 +0,0 @@ -//===--- DataflowSolver.h - Skeleton Dataflow Analysis Code -----*- 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 skeleton code for implementing dataflow analyses. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CLANG_ANALYSES_DATAFLOW_SOLVER -#define LLVM_CLANG_ANALYSES_DATAFLOW_SOLVER - -#include "clang/Analysis/CFG.h" -#include "clang/Analysis/FlowSensitive/DataflowValues.h" -#include "clang/Analysis/ProgramPoint.h" -#include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallVector.h" -#include - -namespace clang { - -//===----------------------------------------------------------------------===// -/// DataflowWorkListTy - Data structure representing the worklist used for -/// dataflow algorithms. -//===----------------------------------------------------------------------===// - -class DataflowWorkListTy { - llvm::DenseMap BlockSet; - SmallVector BlockQueue; -public: - /// enqueue - Add a block to the worklist. Blocks already on the - /// worklist are not added a second time. - void enqueue(const CFGBlock *B) { - unsigned char &x = BlockSet[B]; - if (x == 1) - return; - x = 1; - BlockQueue.push_back(B); - } - - /// dequeue - Remove a block from the worklist. - const CFGBlock *dequeue() { - assert(!BlockQueue.empty()); - const CFGBlock *B = BlockQueue.pop_back_val(); - BlockSet[B] = 0; - return B; - } - - /// isEmpty - Return true if the worklist is empty. - bool isEmpty() const { return BlockQueue.empty(); } -}; - -//===----------------------------------------------------------------------===// -// BlockItrTraits - Traits classes that allow transparent iteration -// over successors/predecessors of a block depending on the direction -// of our dataflow analysis. -//===----------------------------------------------------------------------===// - -namespace dataflow { -template struct ItrTraits {}; - -template <> struct ItrTraits { - typedef CFGBlock::const_pred_iterator PrevBItr; - typedef CFGBlock::const_succ_iterator NextBItr; - typedef CFGBlock::const_iterator StmtItr; - - static PrevBItr PrevBegin(const CFGBlock *B) { return B->pred_begin(); } - static PrevBItr PrevEnd(const CFGBlock *B) { return B->pred_end(); } - - static NextBItr NextBegin(const CFGBlock *B) { return B->succ_begin(); } - static NextBItr NextEnd(const CFGBlock *B) { return B->succ_end(); } - - static StmtItr StmtBegin(const CFGBlock *B) { return B->begin(); } - static StmtItr StmtEnd(const CFGBlock *B) { return B->end(); } - - static BlockEdge PrevEdge(const CFGBlock *B, const CFGBlock *Prev) { - return BlockEdge(Prev, B, 0); - } - - static BlockEdge NextEdge(const CFGBlock *B, const CFGBlock *Next) { - return BlockEdge(B, Next, 0); - } -}; - -template <> struct ItrTraits { - typedef CFGBlock::const_succ_iterator PrevBItr; - typedef CFGBlock::const_pred_iterator NextBItr; - typedef CFGBlock::const_reverse_iterator StmtItr; - - static PrevBItr PrevBegin(const CFGBlock *B) { return B->succ_begin(); } - static PrevBItr PrevEnd(const CFGBlock *B) { return B->succ_end(); } - - static NextBItr NextBegin(const CFGBlock *B) { return B->pred_begin(); } - static NextBItr NextEnd(const CFGBlock *B) { return B->pred_end(); } - - static StmtItr StmtBegin(const CFGBlock *B) { return B->rbegin(); } - static StmtItr StmtEnd(const CFGBlock *B) { return B->rend(); } - - static BlockEdge PrevEdge(const CFGBlock *B, const CFGBlock *Prev) { - return BlockEdge(B, Prev, 0); - } - - static BlockEdge NextEdge(const CFGBlock *B, const CFGBlock *Next) { - return BlockEdge(Next, B, 0); - } -}; -} // end namespace dataflow - -//===----------------------------------------------------------------------===// -/// 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::EdgeDataMapTy EdgeDataMapTy; - typedef typename _DFValuesTy::BlockDataMapTy BlockDataMapTy; - - typedef dataflow::ItrTraits ItrTraits; - typedef typename ItrTraits::NextBItr NextBItr; - typedef typename ItrTraits::PrevBItr PrevBItr; - typedef typename ItrTraits::StmtItr StmtItr; - - //===----------------------------------------------------===// - // External interface: constructing and running the solver. - //===----------------------------------------------------===// - -public: - DataflowSolver(DFValuesTy& d) : D(d), TF(d.getAnalysisData()) {} - ~DataflowSolver() {} - - /// runOnCFG - Computes dataflow values for all blocks in a CFG. - void runOnCFG(CFG& cfg, bool recordStmtValues = false) { - // Set initial dataflow values and boundary conditions. - D.InitializeValues(cfg); - // Solve the dataflow equations. This will populate D.EdgeDataMap - // with dataflow values. - SolveDataflowEquations(cfg, recordStmtValues); - } - - /// 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, bool recordStmtValues) { - BlockDataMapTy& M = D.getBlockDataMap(); - typename BlockDataMapTy::iterator I = M.find(B); - - if (I != M.end()) { - TF.getVal().copyValues(I->second); - ProcessBlock(B, recordStmtValues, AnalysisDirTag()); - } - } - - void runOnBlock(const CFGBlock &B, bool recordStmtValues) { - runOnBlock(&B, recordStmtValues); - } - void runOnBlock(CFG::iterator &I, bool recordStmtValues) { - runOnBlock(*I, recordStmtValues); - } - void runOnBlock(CFG::const_iterator &I, bool recordStmtValues) { - runOnBlock(*I, recordStmtValues); - } - - void runOnAllBlocks(const CFG& cfg, bool recordStmtValues = false) { - for (CFG::const_iterator I=cfg.begin(), E=cfg.end(); I!=E; ++I) - runOnBlock(I, recordStmtValues); - } - - //===----------------------------------------------------===// - // Internal solver logic. - //===----------------------------------------------------===// - -private: - - /// SolveDataflowEquations - Perform the actual worklist algorithm - /// to compute dataflow values. - void SolveDataflowEquations(CFG& cfg, bool recordStmtValues) { - EnqueueBlocksOnWorklist(cfg, AnalysisDirTag()); - - while (!WorkList.isEmpty()) { - const CFGBlock *B = WorkList.dequeue(); - ProcessMerge(cfg, B); - ProcessBlock(B, recordStmtValues, AnalysisDirTag()); - UpdateEdges(cfg, B, TF.getVal()); - } - } - - void EnqueueBlocksOnWorklist(CFG &cfg, dataflow::forward_analysis_tag) { - // Enqueue all blocks to ensure the dataflow values are computed - // for every block. Not all blocks are guaranteed to reach the exit block. - for (CFG::iterator I=cfg.begin(), E=cfg.end(); I!=E; ++I) - WorkList.enqueue(&**I); - } - - void EnqueueBlocksOnWorklist(CFG &cfg, dataflow::backward_analysis_tag) { - // Enqueue all blocks to ensure the dataflow values are computed - // for every block. Not all blocks are guaranteed to reach the exit block. - // Enqueue in reverse order since that will more likely match with - // the order they should ideally processed by the dataflow algorithm. - for (CFG::reverse_iterator I=cfg.rbegin(), E=cfg.rend(); I!=E; ++I) - WorkList.enqueue(&**I); - } - - void ProcessMerge(CFG& cfg, const CFGBlock *B) { - ValTy& V = TF.getVal(); - TF.SetTopValue(V); - - // Merge dataflow values from all predecessors of this block. - MergeOperatorTy Merge; - - EdgeDataMapTy& M = D.getEdgeDataMap(); - bool firstMerge = true; - bool noEdges = true; - for (PrevBItr I=ItrTraits::PrevBegin(B),E=ItrTraits::PrevEnd(B); I!=E; ++I){ - - CFGBlock *PrevBlk = *I; - - if (!PrevBlk) - continue; - - typename EdgeDataMapTy::iterator EI = - M.find(ItrTraits::PrevEdge(B, PrevBlk)); - - if (EI != M.end()) { - noEdges = false; - if (firstMerge) { - firstMerge = false; - V.copyValues(EI->second); - } - else - Merge(V, EI->second); - } - } - - bool isInitialized = true; - typename BlockDataMapTy::iterator BI = D.getBlockDataMap().find(B); - if(BI == D.getBlockDataMap().end()) { - isInitialized = false; - BI = D.getBlockDataMap().insert( std::make_pair(B,ValTy()) ).first; - } - // If no edges have been found, it means this is the first time the solver - // has been called on block B, we copy the initialization values (if any) - // as current value for V (which will be used as edge data) - if(noEdges && isInitialized) - Merge(V, BI->second); - - // Set the data for the block. - BI->second.copyValues(V); - } - - /// ProcessBlock - Process the transfer functions for a given block. - void ProcessBlock(const CFGBlock *B, bool recordStmtValues, - dataflow::forward_analysis_tag) { - - TF.setCurrentBlock(B); - - for (StmtItr I=ItrTraits::StmtBegin(B), E=ItrTraits::StmtEnd(B); I!=E;++I) { - CFGElement El = *I; - if (const CFGStmt *S = El.getAs()) - ProcessStmt(S->getStmt(), recordStmtValues, AnalysisDirTag()); - } - - TF.VisitTerminator(const_cast(B)); - } - - void ProcessBlock(const CFGBlock *B, bool recordStmtValues, - dataflow::backward_analysis_tag) { - - TF.setCurrentBlock(B); - - TF.VisitTerminator(const_cast(B)); - - for (StmtItr I=ItrTraits::StmtBegin(B), E=ItrTraits::StmtEnd(B); I!=E;++I) { - CFGElement El = *I; - if (const CFGStmt *S = El.getAs()) - ProcessStmt(S->getStmt(), recordStmtValues, AnalysisDirTag()); - } - } - - void ProcessStmt(const Stmt *S, bool record, dataflow::forward_analysis_tag) { - if (record) D.getStmtDataMap()[S] = TF.getVal(); - TF.BlockStmt_Visit(const_cast(S)); - } - - void ProcessStmt(const Stmt *S, bool record, dataflow::backward_analysis_tag){ - TF.BlockStmt_Visit(const_cast(S)); - if (record) D.getStmtDataMap()[S] = TF.getVal(); - } - - /// UpdateEdges - After processing the transfer functions for a - /// block, update the dataflow value associated with the block's - /// outgoing/incoming edges (depending on whether we do a - // forward/backward analysis respectively) - void UpdateEdges(CFG& cfg, const CFGBlock *B, ValTy& V) { - for (NextBItr I=ItrTraits::NextBegin(B), E=ItrTraits::NextEnd(B); I!=E; ++I) - if (CFGBlock *NextBlk = *I) - UpdateEdgeValue(ItrTraits::NextEdge(B, NextBlk),V, NextBlk); - } - - /// UpdateEdgeValue - Update the value associated with a given edge. - void UpdateEdgeValue(BlockEdge E, ValTy& V, const CFGBlock *TargetBlock) { - EdgeDataMapTy& M = D.getEdgeDataMap(); - typename EdgeDataMapTy::iterator I = M.find(E); - - if (I == M.end()) { // First computed value for this edge? - M[E].copyValues(V); - WorkList.enqueue(TargetBlock); - } - else if (!_Equal()(V,I->second)) { - I->second.copyValues(V); - WorkList.enqueue(TargetBlock); - } - } - -private: - DFValuesTy& D; - DataflowWorkListTy WorkList; - TransferFuncsTy TF; -}; - -} // end namespace clang -#endif -- 2.40.0