yosys-master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
Public Member Functions | Data Fields
SccWorker Struct Reference
+ Collaboration diagram for SccWorker:

Public Member Functions

void run (RTLIL::Cell *cell, int depth, int maxDepth)
 
 SccWorker (RTLIL::Design *design, RTLIL::Module *module, bool allCellTypes, int maxDepth)
 
void select (RTLIL::Selection &sel)
 

Data Fields

RTLIL::Design * design
 
RTLIL::Module * module
 
SigMap sigmap
 
CellTypes ct
 
std::set< RTLIL::Cell * > workQueue
 
std::map< RTLIL::Cell
*, std::set< RTLIL::Cell * > > 		cellToNextCell
 
std::map< RTLIL::Cell
*, RTLIL::SigSpec > 		cellToPrevSig
 
std::map< RTLIL::Cell
*, RTLIL::SigSpec > 		cellToNextSig
 
std::map< RTLIL::Cell
*, std::pair< int, int > > 		cellLabels
 
std::map< RTLIL::Cell *, int > cellDepth
 
std::set< RTLIL::Cell * > cellsOnStack
 
std::vector< RTLIL::Cell * > cellStack
 
int labelCounter
 
std::map< RTLIL::Cell *, int > cell2scc
 
std::vector< std::set
< RTLIL::Cell * > > 		sccList
 

Detailed Description

Definition at line 35 of file scc.cc.

Constructor & Destructor Documentation

SccWorker::SccWorker ( RTLIL::Design *  design,
RTLIL::Module *  module,
bool  allCellTypes,
int  maxDepth 
)
inline

Definition at line 103 of file scc.cc.

103  : design(design), module(module), sigmap(module)
104  {
105  if (module->processes.size() > 0) {
106  log("Skipping module %s as it contains processes (run 'proc' pass first).\n", module->name.c_str());
107  return;
108  }
109 
110  if (allCellTypes) {
111  ct.setup(design);
112  } else {
113  ct.setup_internals();
114  ct.setup_stdcells();
115  }
116 
117  SigPool selectedSignals;
118  SigSet<RTLIL::Cell*> sigToNextCells;
119 
120  for (auto &it : module->wires_)
121  if (design->selected(module, it.second))
122  selectedSignals.add(sigmap(RTLIL::SigSpec(it.second)));
123 
124  for (auto &it : module->cells_)
125  {
126  RTLIL::Cell *cell = it.second;
127 
128  if (!design->selected(module, cell))
129  continue;
130 
131  if (!allCellTypes && !ct.cell_known(cell->type))
132  continue;
133 
134  workQueue.insert(cell);
135 
136  RTLIL::SigSpec inputSignals, outputSignals;
137 
138  for (auto &conn : cell->connections())
139  {
140  bool isInput = true, isOutput = true;
141 
142  if (ct.cell_known(cell->type)) {
143  isInput = ct.cell_input(cell->type, conn.first);
144  isOutput = ct.cell_output(cell->type, conn.first);
145  }
146 
147  RTLIL::SigSpec sig = selectedSignals.extract(sigmap(conn.second));
148  sig.sort_and_unify();
149 
150  if (isInput)
151  inputSignals.append(sig);
152  if (isOutput)
153  outputSignals.append(sig);
154  }
155 
156  inputSignals.sort_and_unify();
157  outputSignals.sort_and_unify();
158 
159  cellToPrevSig[cell] = inputSignals;
160  cellToNextSig[cell] = outputSignals;
161  sigToNextCells.insert(inputSignals, cell);
162  }
163 
164  for (auto cell : workQueue)
165  cellToNextCell[cell] = sigToNextCells.find(cellToNextSig[cell]);
166 
167  labelCounter = 0;
168  cellLabels.clear();
169 
170  while (workQueue.size() > 0) {
171  RTLIL::Cell *cell = *workQueue.begin();
172  log_assert(cellStack.size() == 0);
173  cellDepth.clear();
174  run(cell, 0, maxDepth);
175  }
176 
177  log("Found %d SCCs in module %s.\n", int(sccList.size()), RTLIL::id2cstr(module->name));
178  }
RTLIL::IdString::c_str
const char * c_str() const
Definition: rtlil.h:178
RTLIL::Design::selected
bool selected(T1 *module) const
Definition: rtlil.h:551
SigPool::extract
RTLIL::SigSpec extract(RTLIL::SigSpec sig)
Definition: sigtools.h:77
CellTypes::setup_stdcells
void setup_stdcells()
Definition: celltypes.h:132
SccWorker::run
void run(RTLIL::Cell *cell, int depth, int maxDepth)
Definition: scc.cc:55
CellTypes::setup
void setup(RTLIL::Design *design=NULL)
Definition: celltypes.h:47
SccWorker::labelCounter
int labelCounter
Definition: scc.cc:50
SccWorker::ct
CellTypes ct
Definition: scc.cc:40
RTLIL::Module::wires_
std::map< RTLIL::IdString, RTLIL::Wire * > wires_
Definition: rtlil.h:595
RTLIL::Cell::type
RTLIL::IdString type
Definition: rtlil.h:854
SccWorker::cellDepth
std::map< RTLIL::Cell *, int > cellDepth
Definition: scc.cc:47
SccWorker::cellLabels
std::map< RTLIL::Cell *, std::pair< int, int > > cellLabels
Definition: scc.cc:46
CellTypes::cell_known
bool cell_known(RTLIL::IdString type)
Definition: celltypes.h:188
SccWorker::module
RTLIL::Module * module
Definition: scc.cc:38
CellTypes::cell_output
bool cell_output(RTLIL::IdString type, RTLIL::IdString port)
Definition: celltypes.h:193
log_assert
#define log_assert(_assert_expr_)
Definition: log.h:85
RTLIL::Module::name
RTLIL::IdString name
Definition: rtlil.h:599
SccWorker::cellToNextCell
std::map< RTLIL::Cell *, std::set< RTLIL::Cell * > > cellToNextCell
Definition: scc.cc:43
SccWorker::design
RTLIL::Design * design
Definition: scc.cc:37
RTLIL::id2cstr
static const char * id2cstr(const RTLIL::IdString &str)
Definition: rtlil.h:267
RTLIL::Module::processes
std::map< RTLIL::IdString, RTLIL::Process * > processes
Definition: rtlil.h:602
SigPool::add
void add(RTLIL::SigSpec sig)
Definition: sigtools.h:41
RTLIL::SigSpec::sort_and_unify
void sort_and_unify()
Definition: rtlil.cc:2291
SccWorker::sccList
std::vector< std::set< RTLIL::Cell * > > sccList
Definition: scc.cc:53
RTLIL::Module::cells_
std::map< RTLIL::IdString, RTLIL::Cell * > cells_
Definition: rtlil.h:596
log
void log(const char *format,...)
Definition: log.cc:180
CellTypes::setup_internals
void setup_internals()
Definition: celltypes.h:83
SccWorker::sigmap
SigMap sigmap
Definition: scc.cc:39
SccWorker::cellStack
std::vector< RTLIL::Cell * > cellStack
Definition: scc.cc:49
RTLIL::SigSpec::append
void append(const RTLIL::SigSpec &signal)
Definition: rtlil.cc:2523
CellTypes::cell_input
bool cell_input(RTLIL::IdString type, RTLIL::IdString port)
Definition: celltypes.h:199
SccWorker::cellToNextSig
std::map< RTLIL::Cell *, RTLIL::SigSpec > cellToNextSig
Definition: scc.cc:44
SccWorker::workQueue
std::set< RTLIL::Cell * > workQueue
Definition: scc.cc:42
RTLIL::Cell::connections
const std::map< RTLIL::IdString, RTLIL::SigSpec > & connections() const
Definition: rtlil.cc:1814
SigSet::find
void find(RTLIL::SigSpec sig, std::set< T > &result)
Definition: sigtools.h:187
SigSet::insert
void insert(RTLIL::SigSpec sig, T data)
Definition: sigtools.h:152
SccWorker::cellToPrevSig
std::map< RTLIL::Cell *, RTLIL::SigSpec > cellToPrevSig
Definition: scc.cc:44

+ Here is the call graph for this function:

Member Function Documentation

void SccWorker::run ( RTLIL::Cell *  cell,
int  depth,
int  maxDepth 
)
inline

Definition at line 55 of file scc.cc.

56  {
57  log_assert(workQueue.count(cell) > 0);
58 
59  workQueue.erase(cell);
60  cellLabels[cell] = std::pair<int, int>(labelCounter, labelCounter);
61  labelCounter++;
62 
63  cellsOnStack.insert(cell);
64  cellStack.push_back(cell);
65 
66  if (maxDepth >= 0)
67  cellDepth[cell] = depth;
68 
69  for (auto nextCell : cellToNextCell[cell])
70  if (cellLabels.count(nextCell) == 0) {
71  run(nextCell, depth+1, maxDepth);
72  cellLabels[cell].second = std::min(cellLabels[cell].second, cellLabels[nextCell].second);
73  } else
74  if (cellsOnStack.count(nextCell) > 0 && (maxDepth < 0 || cellDepth[nextCell] + maxDepth > depth)) {
75  cellLabels[cell].second = std::min(cellLabels[cell].second, cellLabels[nextCell].second);
76  }
77 
78  if (cellLabels[cell].first == cellLabels[cell].second)
79  {
80  if (cellStack.back() == cell)
81  {
82  cellStack.pop_back();
83  cellsOnStack.erase(cell);
84  }
85  else
86  {
87  log("Found an SCC:");
88  std::set<RTLIL::Cell*> scc;
89  while (cellsOnStack.count(cell) > 0) {
90  RTLIL::Cell *c = cellStack.back();
91  cellStack.pop_back();
92  cellsOnStack.erase(c);
93  log(" %s", RTLIL::id2cstr(c->name));
94  cell2scc[c] = sccList.size();
95  scc.insert(c);
96  }
97  sccList.push_back(scc);
98  log("\n");
99  }
100  }
101  }
SccWorker::run
void run(RTLIL::Cell *cell, int depth, int maxDepth)
Definition: scc.cc:55
SccWorker::cell2scc
std::map< RTLIL::Cell *, int > cell2scc
Definition: scc.cc:52
SccWorker::labelCounter
int labelCounter
Definition: scc.cc:50
RTLIL::Cell::name
RTLIL::IdString name
Definition: rtlil.h:853
SccWorker::cellDepth
std::map< RTLIL::Cell *, int > cellDepth
Definition: scc.cc:47
SccWorker::cellLabels
std::map< RTLIL::Cell *, std::pair< int, int > > cellLabels
Definition: scc.cc:46
log_assert
#define log_assert(_assert_expr_)
Definition: log.h:85
SccWorker::cellToNextCell
std::map< RTLIL::Cell *, std::set< RTLIL::Cell * > > cellToNextCell
Definition: scc.cc:43
RTLIL::id2cstr
static const char * id2cstr(const RTLIL::IdString &str)
Definition: rtlil.h:267
SccWorker::sccList
std::vector< std::set< RTLIL::Cell * > > sccList
Definition: scc.cc:53
log
void log(const char *format,...)
Definition: log.cc:180
SccWorker::cellStack
std::vector< RTLIL::Cell * > cellStack
Definition: scc.cc:49
SccWorker::workQueue
std::set< RTLIL::Cell * > workQueue
Definition: scc.cc:42
SccWorker::cellsOnStack
std::set< RTLIL::Cell * > cellsOnStack
Definition: scc.cc:48

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

void SccWorker::select ( RTLIL::Selection &  sel)
inline

Definition at line 180 of file scc.cc.

181  {
182  for (int i = 0; i < int(sccList.size()); i++)
183  {
184  std::set<RTLIL::Cell*> &cells = sccList[i];
185  RTLIL::SigSpec prevsig, nextsig, sig;
186 
187  for (auto cell : cells) {
188  sel.selected_members[module->name].insert(cell->name);
189  prevsig.append(cellToPrevSig[cell]);
190  nextsig.append(cellToNextSig[cell]);
191  }
192 
193  prevsig.sort_and_unify();
194  nextsig.sort_and_unify();
195  sig = prevsig.extract(nextsig);
196 
197  for (auto &chunk : sig.chunks())
198  if (chunk.wire != NULL)
199  sel.selected_members[module->name].insert(chunk.wire->name);
200  }
201  }
RTLIL::Selection::selected_members
std::map< RTLIL::IdString, std::set< RTLIL::IdString > > selected_members
Definition: rtlil.h:464
SccWorker::module
RTLIL::Module * module
Definition: scc.cc:38
RTLIL::Module::name
RTLIL::IdString name
Definition: rtlil.h:599
RTLIL::SigSpec::sort_and_unify
void sort_and_unify()
Definition: rtlil.cc:2291
SccWorker::sccList
std::vector< std::set< RTLIL::Cell * > > sccList
Definition: scc.cc:53
NULL
#define NULL
Definition: NumberlikeArray.hh:6
RTLIL::SigSpec::extract
RTLIL::SigSpec extract(const RTLIL::SigSpec &pattern, const RTLIL::SigSpec *other=NULL) const
Definition: rtlil.cc:2414
RTLIL::SigSpec::append
void append(const RTLIL::SigSpec &signal)
Definition: rtlil.cc:2523
SccWorker::cellToNextSig
std::map< RTLIL::Cell *, RTLIL::SigSpec > cellToNextSig
Definition: scc.cc:44
SccWorker::cellToPrevSig
std::map< RTLIL::Cell *, RTLIL::SigSpec > cellToPrevSig
Definition: scc.cc:44
RTLIL::SigSpec::chunks
const std::vector< RTLIL::SigChunk > & chunks() const
Definition: rtlil.h:1016

+ Here is the call graph for this function:

+ Here is the caller graph for this function:

Field Documentation

std::map<RTLIL::Cell*, int> SccWorker::cell2scc

Definition at line 52 of file scc.cc.

std::map<RTLIL::Cell*, int> SccWorker::cellDepth

Definition at line 47 of file scc.cc.

std::map<RTLIL::Cell*, std::pair<int, int> > SccWorker::cellLabels

Definition at line 46 of file scc.cc.

std::set<RTLIL::Cell*> SccWorker::cellsOnStack

Definition at line 48 of file scc.cc.

std::vector<RTLIL::Cell*> SccWorker::cellStack

Definition at line 49 of file scc.cc.

std::map<RTLIL::Cell*, std::set<RTLIL::Cell*> > SccWorker::cellToNextCell

Definition at line 43 of file scc.cc.

std::map<RTLIL::Cell*, RTLIL::SigSpec> SccWorker::cellToNextSig

Definition at line 44 of file scc.cc.

std::map<RTLIL::Cell*, RTLIL::SigSpec> SccWorker::cellToPrevSig

Definition at line 44 of file scc.cc.

CellTypes SccWorker::ct

Definition at line 40 of file scc.cc.

RTLIL::Design* SccWorker::design

Definition at line 37 of file scc.cc.

int SccWorker::labelCounter

Definition at line 50 of file scc.cc.

RTLIL::Module* SccWorker::module

Definition at line 38 of file scc.cc.

std::vector<std::set<RTLIL::Cell*> > SccWorker::sccList

Definition at line 53 of file scc.cc.

SigMap SccWorker::sigmap

Definition at line 39 of file scc.cc.

std::set<RTLIL::Cell*> SccWorker::workQueue

Definition at line 42 of file scc.cc.

The documentation for this struct was generated from the following file: