OpenASIP  2.0
OperationDAGBehavior.cc
Go to the documentation of this file.
1 /*
2  Copyright (c) 2002-2009 Tampere University.
3 
4  This file is part of TTA-Based Codesign Environment (TCE).
5 
6  Permission is hereby granted, free of charge, to any person obtaining a
7  copy of this software and associated documentation files (the "Software"),
8  to deal in the Software without restriction, including without limitation
9  the rights to use, copy, modify, merge, publish, distribute, sublicense,
10  and/or sell copies of the Software, and to permit persons to whom the
11  Software is furnished to do so, subject to the following conditions:
12 
13  The above copyright notice and this permission notice shall be included in
14  all copies or substantial portions of the Software.
15 
16  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19  THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22  DEALINGS IN THE SOFTWARE.
23  */
24 /**
25  * @file OperationDAGBehavior.cc
26  *
27  * Implementations of OperationDAGBehavior class.
28  *
29  * @author Mikael Lepistö 2007 (mikael.lepisto-no.spam-tut.fi)
30  * @note rating: red
31  */
32 
33 #include <string>
34 #include <set>
35 
36 #include "OperationDAGBehavior.hh"
37 #include "OperationDAGNode.hh"
38 #include "OperationDAGEdge.hh"
39 #include "OperationDAG.hh"
40 #include "Operation.hh"
41 #include "SimValue.hh"
42 #include "OperationNode.hh"
43 #include "TerminalNode.hh"
44 #include "ConstantNode.hh"
45 #include "TCEString.hh"
46 
47 /**
48  * Initilized class to be easier to simulate.
49  *
50  * Basically goes through DAG and schedules operation nodes to calculation
51  * levels.
52  */
54  OperationDAG& dag, int operandCount, const Operation& parent) :
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 }
204 
205 /**
206  * Destructor.
207  */
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 }
219 
220 /**
221  * Simulates the process of starting the execution of an operation.
222  *
223  * Clients should invoke isTriggerLocking() before any attempt to call
224  * simulateTrigger() in current clock cycle. By default, an operation
225  * invocations are successful.
226  *
227  *
228  * @param io The input operands and the results of the operation.
229  * @param context The operation context affecting the operation results.
230  * @return bool True if all values could be computed, false otherwise.
231  * @exception Exception Depends on the implementation.
232  */
233 bool
235  SimValue** operands, OperationContext& context) const {
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 }
252 
253 /**
254  * Checks that the input operands for the OperationDag are valid.
255  */
256 bool
259  const OperationContext& context) const {
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 }
305 
306 /**
307  * Checks whether any of the pending results of an operation initiated in
308  * earlier cycle is ready.
309  *
310  * @param io The results of the operation.
311  * @param context The operation context affecting the operation results.
312  * @return bool True if at least one new result of the operation could be
313  * computed, false otherwise. Returns false when all results are already
314  * computed.
315  */
316 bool
318  SimValue**, OperationContext&) const {
319 
320  return false;
321 }
322 
323 /**
324  * Creates the instance of operation state for this operation and adds it to
325  * its operation context.
326  *
327  * By default this function does nothing (assumes that the operation has no
328  * state). If the operation context already contains the required operation
329  * state instance, nothing is done.
330  *
331  * @param context The operation context to add the state to.
332  */
333 void
335 }
336 
337 /**
338  * Deletes the instance of operation state for this operation from its
339  * operation context.
340  *
341  * By default this function does nothing (assumes that the operation has no
342  * state). If the operation context does not contain the required operation
343  * state instance, nothing is done.
344  *
345  * @param context The operation context to delete the state from.
346  */
347 void
349 }
350 
351 /**
352  * Returns the name of the state of this operation behavior.
353  *
354  * By default returns an empty string which denotes that there is no state.
355  *
356  * @return The state name for this operation behavior.
357  */
358 const char*
360  return "";
361 }
362 
363 /**
364  * If behavior can be simulated.
365  *
366  * Check that every node can be simulated and recognize
367  * cyclic depency.
368  *
369  * @return true If simulation of behavior is possible.
370  */
371 bool
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 }
393 
OperationDAGEdge::dstOperand
int dstOperand() const
Definition: OperationDAGEdge.cc:54
OperationDAGNode.hh
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
OperationDAGBehavior.hh
OperationDAGBehavior::areValid
virtual bool areValid(const InputOperandVector &inputs, const OperationContext &context) const override
Definition: OperationDAGBehavior.cc:257
BoostGraph::headNode
virtual Node & headNode(const Edge &edge) const
BoostGraph::node
Node & node(const int index) const
OperationContext
Definition: OperationContext.hh:56
OperationDAGBehavior::SimulationStep::params
SimValue ** params
Definition: OperationDAGBehavior.hh:81
TerminalNode
Definition: TerminalNode.hh:47
Operation::numberOfInputs
virtual int numberOfInputs() const
Definition: Operation.cc:192
OperationDAGBehavior::canBeSimulated
virtual bool canBeSimulated() const override
Definition: OperationDAGBehavior.cc:372
OperationDAGBehavior::stateName
virtual const char * stateName() const override
Definition: OperationDAGBehavior.cc:359
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
TCEString.hh
assert
#define assert(condition)
Definition: Application.hh:86
OperationDAGBehavior::ios_
SimValue * ios_
Table of parameters for simulate trigger.
Definition: OperationDAGBehavior.hh:90
OperationDAGEdge.hh
OperationDAGEdge::srcOperand
int srcOperand() const
Definition: OperationDAGEdge.cc:49
OperationContext::branchDelayCycles
int branchDelayCycles() const
Definition: OperationContext.cc:308
OperationDAGNode
Definition: OperationDAGNode.hh:45
BoostGraph::inEdge
virtual Edge & inEdge(const Node &node, const int index) const
OperationDAG.hh
OperationDAGBehavior::cycleFound_
bool cycleFound_
For checking if there is cyclic dependency in DAG.
Definition: OperationDAGBehavior.hh:99
OperationDAG
Definition: OperationDAG.hh:43
OperationDAGBehavior::simulationSteps_
std::vector< SimulationStep > simulationSteps_
Definition: OperationDAGBehavior.hh:93
ConstantNode
Definition: ConstantNode.hh:43
Operation.hh
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
OperationDAGBehavior::lateResult
virtual bool lateResult(SimValue **io, OperationContext &context) const
Definition: OperationDAGBehavior.cc:317
Operation
Definition: Operation.hh:59
OperationDAGBehavior::createState
virtual void createState(OperationContext &context) const override
Definition: OperationDAGBehavior.cc:334
OperationDAGBehavior::~OperationDAGBehavior
virtual ~OperationDAGBehavior()
Definition: OperationDAGBehavior.cc:208
OperationBehavior::InputOperandVector
std::vector< SimValue > InputOperandVector
Input operand type for areValid()
Definition: OperationBehavior.hh:57
OperationDAGBehavior::simulateTrigger
virtual bool simulateTrigger(SimValue **io, OperationContext &context) const override
Definition: OperationDAGBehavior.cc:234
OperationContext::programCounter
InstructionAddress & programCounter()
Definition: OperationContext.cc:152
OperationBehavior
Definition: OperationBehavior.hh:53
ConstantNode::value
virtual long value() const
Definition: ConstantNode.cc:60
false
find Finds info of the inner loops in the false
Definition: InnerLoopFinder.cc:81
SimValue.hh
OperationDAGBehavior::SimulationStep
Definition: OperationDAGBehavior.hh:79
TerminalNode.hh
ConstantNode.hh
OperationPimpl::dag
OperationDAG & dag(int index) const
Definition: OperationPimpl.cc:186
OperationNode.hh
BoostGraph::nodeCount
int nodeCount() const
OperationDAGBehavior::deleteState
virtual void deleteState(OperationContext &context) const override
Definition: OperationDAGBehavior.cc:348
OperationDAGBehavior::SimulationStep::op
Operation * op
Definition: OperationDAGBehavior.hh:80
Operation::numberOfOutputs
virtual int numberOfOutputs() const
Definition: Operation.cc:202
OperationContext::returnAddress
SimValue & returnAddress()
Definition: OperationContext.cc:207
OperationDAGBehavior::dag_
OperationDAG & dag_
Definition: OperationDAGBehavior.hh:84
OperationDAGBehavior::OperationDAGBehavior
OperationDAGBehavior(OperationDAG &dag, int operandCount, const Operation &parent=NullOperation::instance())
Definition: OperationDAGBehavior.cc:53
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