blob: 724b4a4fbb91383cb60c81bf31f91b18f90feb65 [file] [log] [blame]
//===--- 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<const CFGBlock*,20> 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 <typename _DFValuesTy, // Usually a subclass of DataflowValues
typename _TransferFuncsTy,
typename _MergeOperatorTy >
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;
//===--------------------------------------------------------------------===//
// 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(const CFG& cfg) {
// Set initial dataflow values and boundary conditions.
D.InitializeValues(cfg);
// Solve the dataflow equations. This will populate D.EdgeDataMap
// with dataflow values.
SolveDataflowEquations(cfg);
}
/// 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) {
if (hasData(B,AnalysisDirTag()))
ProcessBlock(B,AnalysisDirTag());
}
//===--------------------------------------------------------------------===//
// Internal solver logic.
//===--------------------------------------------------------------------===//
private:
/// SolveDataflowEquations - Perform the actual
/// worklist algorithm to compute dataflow values.
void SolveDataflowEquations(const CFG& cfg) {
EnqueueFirstBlock(cfg,AnalysisDirTag());
// 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.
ProcessBlock(B,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.
void ProcessBlock(const CFGBlock* B, dataflow::forward_analysis_tag) {
// Merge dataflow values from all predecessors of this block.
ValTy& V = TF.getVal();
V.resetValues(D.getAnalysisData());
MergeOperatorTy Merge;
EdgeDataMapTy& M = D.getEdgeDataMap();
bool firstMerge = true;
for (CFGBlock::const_pred_iterator I=B->pred_begin(),
E=B->pred_end(); I!=E; ++I) {
typename EdgeDataMapTy::iterator BI = M.find(CFG::Edge(*I,B));
if (BI != M.end()) {
if (firstMerge) {
firstMerge = false;
V.copyValues(BI->second);
}
else
Merge(V,BI->second);
}
}
// 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<Stmt*>(*I));
}
/// ProcessBlock (BACKWARD ANALYSIS) - Process the transfer functions
/// for a given block based on a forward analysis.
void ProcessBlock(const CFGBlock* B, TransferFuncsTy& TF,
dataflow::backward_analysis_tag) {
// Merge dataflow values from all predecessors of this block.
ValTy& V = TF.getVal();
V.resetValues(D.getAnalysisData());
MergeOperatorTy Merge;
EdgeDataMapTy& M = D.getEdgeDataMap();
bool firstMerge = true;
for (CFGBlock::const_succ_iterator I=B->succ_begin(),
E=B->succ_end(); I!=E; ++I) {
typename EdgeDataMapTy::iterator BI = M.find(CFG::Edge(B,*I));
if (BI != M.end()) {
if (firstMerge) {
firstMerge = false;
V.copyValues(BI->second);
}
else
Merge(V,BI->second);
}
}
// 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<Stmt*>(*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);
}
}
/// 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()) {
// First value for this edge.
M[E].copyValues(V);
WorkList.enqueue(TargetBlock);
}
else if (!V.equal(I->second)) {
I->second.copyValues(V);
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;
TransferFuncsTy TF;
};
} // end namespace clang
#endif