OpenASIP  2.0
Classes | Public Member Functions | Private Attributes | List of all members
OperationDAGBehavior Class Reference

#include <OperationDAGBehavior.hh>

Inheritance diagram for OperationDAGBehavior:
Inheritance graph
Collaboration diagram for OperationDAGBehavior:
Collaboration graph

Classes

struct  SimulationStep
 

Public Member Functions

 OperationDAGBehavior (OperationDAG &dag, int operandCount, const Operation &parent=NullOperation::instance())
 
virtual ~OperationDAGBehavior ()
 
virtual bool simulateTrigger (SimValue **io, OperationContext &context) const override
 
virtual bool areValid (const InputOperandVector &inputs, const OperationContext &context) const override
 
virtual bool lateResult (SimValue **io, OperationContext &context) const
 
virtual void createState (OperationContext &context) const override
 
virtual void deleteState (OperationContext &context) const override
 
virtual const char * stateName () const override
 
virtual bool canBeSimulated () const override
 
- Public Member Functions inherited from OperationBehavior
virtual void writeOutput (const char *text) const
 
 OperationBehavior ()
 
 OperationBehavior (const Operation &parent)
 
virtual ~OperationBehavior ()
 

Private Attributes

OperationDAGdag_
 
int operandCount_
 Number of operands of this operation. More...
 
SimValueios_
 Table of parameters for simulate trigger. More...
 
std::vector< SimulationStepsimulationSteps_
 
std::vector< SimValue * > cleanUpTable_
 Contain list of pointers to delete in destructor. More...
 
bool cycleFound_
 For checking if there is cyclic dependency in DAG. More...
 

Additional Inherited Members

- Public Types inherited from OperationBehavior
typedef std::vector< SimValueInputOperandVector
 Input operand type for areValid() More...
 
- Protected Attributes inherited from OperationBehavior
const Operationparent_
 

Detailed Description

Implementation of OperationBehavior which uses OperationDAG for execution of operation.

Definition at line 54 of file OperationDAGBehavior.hh.

Constructor & Destructor Documentation

◆ OperationDAGBehavior()

OperationDAGBehavior::OperationDAGBehavior ( OperationDAG dag,
int  operandCount,
const Operation parent = NullOperation::instance() 
)

Initilized class to be easier to simulate.

Basically goes through DAG and schedules operation nodes to calculation levels.

Definition at line 53 of file OperationDAGBehavior.cc.

54  :
55  OperationBehavior(parent), dag_(dag), operandCount_(operandCount),
56  cycleFound_(false) {
57 
59 
60  std::vector<std::set<OperationDAGNode*, OperationDAGNode::Comparator> >
61  nodeLevels;
62  std::set<OperationDAGNode*, OperationDAGNode::Comparator> addedNodes;
63 
64  // organize all the nodes calculation levels, in first level we calculate
65  // nodes whose inputs are read straight from TerminalNodes or
66  // ConstantNodes, in the second are added nodes whose inputs are read
67  // from TerminalNodes or first level nodes etc.
68  while (static_cast<int>(addedNodes.size()) < dag_.nodeCount()) {
69  std::set<OperationDAGNode*, OperationDAGNode::Comparator> currSet;
70 
71  for (int i = 0; i < dag_.nodeCount(); i++) {
72  OperationDAGNode& currNode = dag_.node(i);
73 
74  // check if the node is already handled
75  if (addedNodes.find(&currNode) != addedNodes.end()) {
76  continue;
77  }
78 
79  // if node doesn't have in edges it can always be added
80  bool canBeAddedToCurrentLevel = true;
81 
82  for (int j = 0; j < dag_.inDegree(currNode); j++) {
83  OperationDAGNode& parentNode =
84  dag_.tailNode(dag_.inEdge(currNode, j));
85 
86  // find node from previous levels
87  bool wasFound = false;
88  for (unsigned int k = 0; k < nodeLevels.size(); k++) {
89  if (nodeLevels[k].find(&parentNode) !=
90  nodeLevels[k].end()) {
91  wasFound = true;
92  break;
93  }
94  }
95 
96  // it was not found... too bad.
97  if (!wasFound) {
98  canBeAddedToCurrentLevel = false;
99  }
100  }
101 
102  // current level is ok for currently checked node
103  if (canBeAddedToCurrentLevel) {
104  currSet.insert(&currNode);
105  addedNodes.insert(&currNode);
106  }
107  }
108 
109  nodeLevels.push_back(currSet);
110  currSet.clear();
111  }
112 
113  // create execution steps for all operation nodes and add them to
114  // executionStep table
115  std::map<OperationNode*, int> stepOfNode;
116 
117  for (unsigned int i = 0; i < nodeLevels.size(); i++) {
118  for (std::set<OperationDAGNode*,OperationDAGNode::Comparator>::
119  iterator nodeIter =
120  nodeLevels[i].begin(); nodeIter != nodeLevels[i].end();
121  nodeIter++) {
122 
123  OperationNode* opNode = dynamic_cast<OperationNode*>(*nodeIter);
124 
125  if (opNode != NULL) {
126  SimulationStep step;
127  step.op = &opNode->referencedOperation();
128 
129  step.params =
130  new SimValue*[step.op->numberOfInputs() +
131  step.op->numberOfOutputs()];
132 
133  // set input variables
134  for (int j = 0; j < dag_.inDegree(*opNode); j++) {
135  OperationDAGEdge* currEdge = &dag_.inEdge(*opNode, j);
136  OperationDAGNode* paramNode = &(dag_.tailNode(*currEdge));
137 
138  TerminalNode* termNode =
139  dynamic_cast<TerminalNode*>(paramNode);
140 
141  OperationNode* operNode =
142  dynamic_cast<OperationNode*>(paramNode);
143 
144  ConstantNode* constNode =
145  dynamic_cast<ConstantNode*>(paramNode);
146 
147  if (termNode != NULL) {
148  // if terminal node, read stuff from ios_ table
149  step.params[currEdge->dstOperand() - 1] =
150  &ios_[termNode->operandIndex() - 1];
151 
152  } else if (constNode != NULL) {
153  // if constant node, read constant to SimValue
154  // and give it to operation
155  SimValue* newVal = new SimValue();
156  *newVal = constNode->value();
157  cleanUpTable_.push_back(newVal);
158  step.params[currEdge->dstOperand() - 1] = newVal;
159 
160  } else if (operNode != NULL) {
161  // if normal operation, read stuff from parent operand
162  SimulationStep &refStep =
163  simulationSteps_[stepOfNode[operNode]];
164 
165  step.params[currEdge->dstOperand() - 1] =
166  refStep.params[currEdge->srcOperand() - 1];
167  } else {
168  assert(false && "Invalid node type");
169  }
170  }
171 
172  // set output variables and also create them if needed.
173  for (int j = 0; j < dag_.outDegree(*opNode); j++) {
174  OperationDAGEdge* currEdge = &dag_.outEdge(*opNode, j);
175  OperationDAGNode* paramNode = &(dag_.headNode(*currEdge));
176 
177  TerminalNode* termNode =
178  dynamic_cast<TerminalNode*>(paramNode);
179 
180  OperationNode* operNode =
181  dynamic_cast<OperationNode*>(paramNode);
182 
183  if (termNode != NULL) {
184  // if terminal node, write stuff to ios_ table
185  step.params[currEdge->srcOperand() - 1] =
186  &ios_[termNode->operandIndex() - 1];
187 
188  } else if (operNode != NULL) {
189  // if normal operation, write stuff to temp
190  SimValue* newVal = new SimValue();
191  cleanUpTable_.push_back(newVal);
192  step.params[currEdge->srcOperand() - 1] = newVal;
193 
194  } else {
195  assert(false && "Invalid node type");
196  }
197  }
198  stepOfNode[opNode] = simulationSteps_.size();
199  simulationSteps_.push_back(step);
200  }
201  }
202  }
203 }

References assert, cleanUpTable_, dag_, OperationDAGEdge::dstOperand(), BoostGraph< GraphNode, GraphEdge >::headNode(), BoostGraph< GraphNode, GraphEdge >::inDegree(), BoostGraph< GraphNode, GraphEdge >::inEdge(), ios_, BoostGraph< GraphNode, GraphEdge >::node(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), Operation::numberOfInputs(), Operation::numberOfOutputs(), OperationDAGBehavior::SimulationStep::op, operandCount_, TerminalNode::operandIndex(), BoostGraph< GraphNode, GraphEdge >::outDegree(), BoostGraph< GraphNode, GraphEdge >::outEdge(), OperationDAGBehavior::SimulationStep::params, OperationNode::referencedOperation(), simulationSteps_, OperationDAGEdge::srcOperand(), BoostGraph< GraphNode, GraphEdge >::tailNode(), and ConstantNode::value().

Here is the call graph for this function:

◆ ~OperationDAGBehavior()

OperationDAGBehavior::~OperationDAGBehavior ( )
virtual

Destructor.

Definition at line 208 of file OperationDAGBehavior.cc.

208  {
209  delete[] ios_;
210 
211  for (unsigned int i = 0; i < cleanUpTable_.size(); i++) {
212  delete cleanUpTable_[i];
213  }
214 
215  for (unsigned int i = 0; i < simulationSteps_.size(); i++) {
216  delete[] simulationSteps_[i].params;
217  }
218 }

References cleanUpTable_, ios_, and simulationSteps_.

Member Function Documentation

◆ areValid()

bool OperationDAGBehavior::areValid ( const InputOperandVector inputs,
const OperationContext context 
) const
overridevirtual

Checks that the input operands for the OperationDag are valid.

Reimplemented from OperationBehavior.

Definition at line 257 of file OperationDAGBehavior.cc.

259  {
260 
261  assert(simulationSteps_.size() != 0);
262 
263  InstructionAddress sandboxedProgramCounter = context.programCounter();
264  SimValue sandboxedReturnAddress = context.returnAddress();
265  OperationContext sandBoxContext(
266  NULL, // Todo Add sandboxed memory proxy
267  sandboxedProgramCounter,
268  sandboxedReturnAddress,
269  context.branchDelayCycles());
270 
271  for (size_t i = 0; i < inputs.size(); i++) {
272  ios_[i].deepCopy(inputs.at(i));
273  }
274  bool valid = true;
275 
276  // Check validity of inputs for each step.
277  for (unsigned int stepi = 0; stepi < simulationSteps_.size(); stepi++) {
278  // Ugly copying values back and forth just to accommodate arguments for
279  // areValid().
281  tmp.resize(simulationSteps_.at(stepi).op->numberOfInputs());
282  for (int inputi = 0;
283  inputi < simulationSteps_.at(stepi).op->numberOfInputs();
284  inputi++) {
285  tmp.at(inputi).deepCopy(*simulationSteps_[stepi].params[inputi]);
286  }
287 
288  // Note: OperationState may not be preserved sanely even if the
289  // context is sandboxed (concern is that copying OperationContext does
290  // not deep copy the OperationState mannerly).
291  assert(!simulationSteps_[stepi].op->hasSideEffects());
292 
293  if (simulationSteps_[stepi].op->areValid(tmp, context)) {
294  // Simulate the step to get new inputs for the next step.
295  simulationSteps_[stepi].op->simulateTrigger(
296  simulationSteps_[stepi].params, sandBoxContext);
297  } else {
298  valid = false;
299  break;
300  }
301  }
302 
303  return valid;
304 }

References assert, OperationContext::branchDelayCycles(), SimValue::deepCopy(), ios_, OperationContext::programCounter(), OperationContext::returnAddress(), and simulationSteps_.

Here is the call graph for this function:

◆ canBeSimulated()

bool OperationDAGBehavior::canBeSimulated ( ) const
overridevirtual

If behavior can be simulated.

Check that every node can be simulated and recognize cyclic depency.

Returns
true If simulation of behavior is possible.

Reimplemented from OperationBehavior.

Definition at line 372 of file OperationDAGBehavior.cc.

372  {
373 
374  if (cycleFound_ || dag_.isNull()) {
375  cycleFound_ = false;
376  return false;
377  }
378 
379  cycleFound_ = true;
380  for (int i = 0; i < dag_.nodeCount(); i++) {
381  OperationNode* node = dynamic_cast<OperationNode*>(&dag_.node(i));
382 
383  if (node != NULL) {
384  if (!node->referencedOperation().canBeSimulated()) {
385  return false;
386  }
387  }
388  }
389 
390  cycleFound_ = false;
391  return true;
392 }

References Operation::canBeSimulated(), cycleFound_, dag_, OperationDAG::isNull(), BoostGraph< GraphNode, GraphEdge >::node(), BoostGraph< GraphNode, GraphEdge >::nodeCount(), and OperationNode::referencedOperation().

Here is the call graph for this function:

◆ createState()

void OperationDAGBehavior::createState ( OperationContext context) const
overridevirtual

Creates the instance of operation state for this operation and adds it to its operation context.

By default this function does nothing (assumes that the operation has no state). If the operation context already contains the required operation state instance, nothing is done.

Parameters
contextThe operation context to add the state to.

Reimplemented from OperationBehavior.

Definition at line 334 of file OperationDAGBehavior.cc.

334  {
335 }

◆ deleteState()

void OperationDAGBehavior::deleteState ( OperationContext context) const
overridevirtual

Deletes the instance of operation state for this operation from its operation context.

By default this function does nothing (assumes that the operation has no state). If the operation context does not contain the required operation state instance, nothing is done.

Parameters
contextThe operation context to delete the state from.

Reimplemented from OperationBehavior.

Definition at line 348 of file OperationDAGBehavior.cc.

348  {
349 }

◆ lateResult()

bool OperationDAGBehavior::lateResult ( SimValue **  io,
OperationContext context 
) const
virtual

Checks whether any of the pending results of an operation initiated in earlier cycle is ready.

Parameters
ioThe results of the operation.
contextThe operation context affecting the operation results.
Returns
bool True if at least one new result of the operation could be computed, false otherwise. Returns false when all results are already computed.

Definition at line 317 of file OperationDAGBehavior.cc.

318  {
319 
320  return false;
321 }

◆ simulateTrigger()

bool OperationDAGBehavior::simulateTrigger ( SimValue **  operands,
OperationContext context 
) const
overridevirtual

Simulates the process of starting the execution of an operation.

Clients should invoke isTriggerLocking() before any attempt to call simulateTrigger() in current clock cycle. By default, an operation invocations are successful.

Parameters
ioThe input operands and the results of the operation.
contextThe operation context affecting the operation results.
Returns
bool True if all values could be computed, false otherwise.
Exceptions
ExceptionDepends on the implementation.

Implements OperationBehavior.

Definition at line 234 of file OperationDAGBehavior.cc.

235  {
236 
237  for (int i = 0; i < operandCount_; i++) {
238  ios_[i].deepCopy(*(operands[i]));
239  }
240 
241  for (unsigned int i = 0; i < simulationSteps_.size(); i++) {
242  simulationSteps_[i].op->simulateTrigger(
243  simulationSteps_[i].params, context);
244  }
245 
246  for (int i = 0; i < operandCount_; i++) {
247  operands[i]->deepCopy(ios_[i]);
248  }
249 
250  return true;
251 }

References SimValue::deepCopy(), ios_, operandCount_, and simulationSteps_.

Here is the call graph for this function:

◆ stateName()

const char * OperationDAGBehavior::stateName ( ) const
overridevirtual

Returns the name of the state of this operation behavior.

By default returns an empty string which denotes that there is no state.

Returns
The state name for this operation behavior.

Reimplemented from OperationBehavior.

Definition at line 359 of file OperationDAGBehavior.cc.

359  {
360  return "";
361 }

Member Data Documentation

◆ cleanUpTable_

std::vector<SimValue*> OperationDAGBehavior::cleanUpTable_
private

Contain list of pointers to delete in destructor.

Definition at line 96 of file OperationDAGBehavior.hh.

Referenced by OperationDAGBehavior(), and ~OperationDAGBehavior().

◆ cycleFound_

bool OperationDAGBehavior::cycleFound_
mutableprivate

For checking if there is cyclic dependency in DAG.

Definition at line 99 of file OperationDAGBehavior.hh.

Referenced by canBeSimulated().

◆ dag_

OperationDAG& OperationDAGBehavior::dag_
private

Definition at line 84 of file OperationDAGBehavior.hh.

Referenced by canBeSimulated(), and OperationDAGBehavior().

◆ ios_

SimValue* OperationDAGBehavior::ios_
private

Table of parameters for simulate trigger.

Definition at line 90 of file OperationDAGBehavior.hh.

Referenced by areValid(), OperationDAGBehavior(), simulateTrigger(), and ~OperationDAGBehavior().

◆ operandCount_

int OperationDAGBehavior::operandCount_
private

Number of operands of this operation.

Definition at line 87 of file OperationDAGBehavior.hh.

Referenced by OperationDAGBehavior(), and simulateTrigger().

◆ simulationSteps_

std::vector<SimulationStep> OperationDAGBehavior::simulationSteps_
private

The documentation for this class was generated from the following files:
OperationDAGEdge::dstOperand
int dstOperand() const
Definition: OperationDAGEdge.cc:54
BoostGraph::outEdge
virtual Edge & outEdge(const Node &node, const int index) const
InstructionAddress
UInt32 InstructionAddress
Definition: BaseType.hh:175
OperationDAG::isNull
bool isNull() const
Definition: OperationDAG.hh:48
BoostGraph::tailNode
virtual Node & tailNode(const Edge &edge) const
BoostGraph::headNode
virtual Node & headNode(const Edge &edge) const
BoostGraph::node
Node & node(const int index) const
OperationContext
Definition: OperationContext.hh:56
TerminalNode
Definition: TerminalNode.hh:47
Operation::canBeSimulated
virtual bool canBeSimulated() const
Definition: Operation.cc:612
OperationNode::referencedOperation
Operation & referencedOperation() const
Definition: OperationNode.cc:70
OperationNode
Definition: OperationNode.hh:47
OperationDAGEdge
Definition: OperationDAGEdge.hh:38
SimValue
Definition: SimValue.hh:96
BoostGraph::outDegree
virtual int outDegree(const Node &node) const
assert
#define assert(condition)
Definition: Application.hh:86
OperationDAGBehavior::ios_
SimValue * ios_
Table of parameters for simulate trigger.
Definition: OperationDAGBehavior.hh:90
OperationDAGEdge::srcOperand
int srcOperand() const
Definition: OperationDAGEdge.cc:49
OperationContext::branchDelayCycles
int branchDelayCycles() const
Definition: OperationContext.cc:308
OperationDAGNode
Definition: OperationDAGNode.hh:45
OperationBehavior::OperationBehavior
OperationBehavior()
Definition: OperationBehavior.cc:52
BoostGraph::inEdge
virtual Edge & inEdge(const Node &node, const int index) const
OperationDAGBehavior::cycleFound_
bool cycleFound_
For checking if there is cyclic dependency in DAG.
Definition: OperationDAGBehavior.hh:99
OperationDAGBehavior::simulationSteps_
std::vector< SimulationStep > simulationSteps_
Definition: OperationDAGBehavior.hh:93
ConstantNode
Definition: ConstantNode.hh:43
OperationDAGBehavior::cleanUpTable_
std::vector< SimValue * > cleanUpTable_
Contain list of pointers to delete in destructor.
Definition: OperationDAGBehavior.hh:96
BoostGraph::inDegree
virtual int inDegree(const Node &node) const
OperationBehavior::InputOperandVector
std::vector< SimValue > InputOperandVector
Input operand type for areValid()
Definition: OperationBehavior.hh:57
OperationContext::programCounter
InstructionAddress & programCounter()
Definition: OperationContext.cc:152
ConstantNode::value
virtual long value() const
Definition: ConstantNode.cc:60
BoostGraph::nodeCount
int nodeCount() const
OperationContext::returnAddress
SimValue & returnAddress()
Definition: OperationContext.cc:207
OperationDAGBehavior::dag_
OperationDAG & dag_
Definition: OperationDAGBehavior.hh:84
TerminalNode::operandIndex
virtual int operandIndex() const
Definition: TerminalNode.cc:60
OperationDAGBehavior::operandCount_
int operandCount_
Number of operands of this operation.
Definition: OperationDAGBehavior.hh:87
SimValue::deepCopy
void deepCopy(const SimValue &source)
Definition: SimValue.cc:307