OpenASIP 2.2
Loading...
Searching...
No Matches
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.
 
SimValueios_
 Table of parameters for simulate trigger.
 
std::vector< SimulationStepsimulationSteps_
 
std::vector< SimValue * > cleanUpTable_
 Contain list of pointers to delete in destructor.
 
bool cycleFound_
 For checking if there is cyclic dependency in DAG.
 

Additional Inherited Members

- Public Types inherited from OperationBehavior
typedef std::vector< SimValueInputOperandVector
 Input operand type for areValid()
 
- 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}
#define assert(condition)
virtual Node & headNode(const Edge &edge) const
int nodeCount() const
virtual Edge & outEdge(const Node &node, const int index) const
virtual Edge & inEdge(const Node &node, const int index) const
Node & node(const int index) const
virtual int inDegree(const Node &node) const
virtual int outDegree(const Node &node) const
virtual Node & tailNode(const Edge &edge) const
virtual long value() const
std::vector< SimulationStep > simulationSteps_
std::vector< SimValue * > cleanUpTable_
Contain list of pointers to delete in destructor.
SimValue * ios_
Table of parameters for simulate trigger.
int operandCount_
Number of operands of this operation.
bool cycleFound_
For checking if there is cyclic dependency in DAG.
Operation & referencedOperation() const
virtual int operandIndex() const

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}
UInt32 InstructionAddress
Definition BaseType.hh:175
std::vector< SimValue > InputOperandVector
Input operand type for areValid()
int branchDelayCycles() const
SimValue & returnAddress()
InstructionAddress & programCounter()
void deepCopy(const SimValue &source)
Definition SimValue.cc:307

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}
bool isNull() const
virtual bool canBeSimulated() const
Definition Operation.cc:612

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: