OpenASIP  2.0
OperationDAGBuilder.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 OperationDAGBuilder.cc
26  *
27  * Declaration of OperationDAGBuilder class.
28  *
29  * @author Mikael Lepistö 2007 (tmlepist-no.spam-cs.tut.fi)
30  * @note rating: red
31  */
32 
33 #include "OperationDAGBuilder.hh"
35 
36 #include "OperationPool.hh"
37 #include "OperationNode.hh"
38 #include "OperationDAGEdge.hh"
39 #include "TerminalNode.hh"
40 #include "ConstantNode.hh"
41 #include "Operation.hh"
42 #include "Operand.hh"
43 #include "OperationPimpl.hh"
44 #include "OperationDAG.hh"
45 #include "OperationDAGNode.hh"
46 
47 /**
48  * Constructor.
49  *
50  * @param dag OperationDAG where to create DAG representation of operation.
51  * @param root Tokenized OSAL DAG Language code.
52  */
54  const OperationPimpl& operation,
55  OperationDAG& dag, const TokenizerData::TokenTreeNode& root) :
56  dag_(&dag), rootNode_(root), currentOperation_(NULL),
57  operation_(operation) {
58 }
59 
60 /**
61  * Parses token tree presentation of OSAL DAG language to OperationDAG.
62  */
63 void
65 
66  // Print out tokenized dag form...
67  // std::cerr << rootNode_.toStr() << std::endl;
68 
69  // Loop through all leafs of root node and call finalization.
70  for (int i = 0; i < rootNode_.leafCount();i++) {
71  const TokenizerData::TokenTreeNode* currNode =
72  &(rootNode_.leaf(i));
73  parseNode(currNode);
74  }
75  finalize();
76 }
77 
78 /**
79  * Parses one token tree node to DAG representation.
80  *
81  * @param node Node to parse.
82  */
83 void
85  const TokenizerData::TokenTreeNode* node) {
86 
87  switch(node->token().type_) {
89  // ignore empty expressions
90  if (node->leafCount() == 1) {
91  parseNode(&node->leaf(0));
92  }
93  } break;
94 
96  for (int i = 1; i < node->leafCount(); i++) {
97  // TODO: check thata init declarator doesn't
98  // doesnt't have leafs
99  declareVariable(&node->leaf(i));
100  }
101  } break;
102 
104  if (node->leafCount() == 1) {
105  parseNode(&node->leaf(0));
106 
107  } else if (node->isAssignment()) {
108  assignVariable(&node->leaf(0), &node->leaf(2));
109 
110  } else if (node->isFunctionCall()) {
111  // TODO: check if is execution macro
112  // get postfixpart
113  node = &node->leaf(1);
114 
115  // leaf(0) create operation node
117 
118  // leaf(1)- ... connect nodes..
119  for (int i = 1; i < node->leafCount(); i++) {
120  connectOperandToNode(&node->leaf(i), i);
121  }
122 
123  } else {
124  std::cerr << "Cannot parse: " << node->toStr();
125  }
126  } break;
127 
128  default:
129  std::cerr << "Failed parsing: " << node->token().stringValue()
130  << std::endl;
131  }
132 }
133 
134 /**
135  * Starts creation of new operation node.
136  *
137  * @param operation Name of operation which is referred by this node.
138  * @exception IllegalParameters Operation by requested name doesn't exist.
139  */
140 void
141 OperationDAGBuilder::createOperationNode(const std::string& operation) {
142  OperationPool opPool;
143  Operation& op = opPool.operation(operation.c_str());
144 
145  if (&op == &NullOperation::instance()) {
146  throw IllegalParameters(__FILE__, __LINE__, __func__,
147  "Operation: \"" + operation + "\" doesn't exist.");
148  }
151 }
152 
153 /**
154  * Connects a variable node to given operand index of last created
155  * operation node.
156  *
157  * @param var Variable to connect to operand of created operation node.
158  * @param operandIndex Index of operand to which variable is connected.
159  * @exception IllegalParameters Operand with requested index doesn't exist.
160  */
161 void
163  const TokenizerData::TokenTreeNode* var, unsigned int operandIndex) {
164 
165  // check if input or output
167  if (operandIndex > (unsigned)currOp.operandCount()) {
168  throw IllegalParameters(
169  __FILE__, __LINE__, __func__,
170  "Operation doesn't have operand number: " +
171  Conversion::toString(operandIndex));
172  }
173 
174  if (currOp.operand(operandIndex).isInput()) {
175  VariableBinding* srcNode = &getBinding(var);
176  if (srcNode->first == NULL) {
177  throw IllegalParameters(
178  __FILE__,__LINE__,__func__,
179  TCEString("Source node: ") + Conversion::toString(operandIndex)
180  + " of operation " + currentOperation_->toString()
181  + " is NULL. Maybe it is temp variable that has not been"
182  + " written yet? This happens in DAG of operation: " + operation_.name());
183  }
184 
185  if (!dag_->hasNode(*srcNode->first)) {
186  throw IllegalParameters(
187  __FILE__,__LINE__,__func__,
188  TCEString("Source node: ") + Conversion::toString(operandIndex)
189  + " of operation " + currentOperation_->toString()
190  + " not in dag. This happens in DAG of operation: " + operation_.name());
191  }
192 
193  OperationDAGEdge* newEdge =
194  new OperationDAGEdge(srcNode->second, operandIndex);
195  dag_->connectNodes(*srcNode->first, *currentOperation_, *newEdge);
196 
197  } else if (currOp.operand(operandIndex).isOutput()) {
198  // set node, operandIndex pair for the variable
199  VariableBinding varBind =
200  VariableBinding(currentOperation_, operandIndex);
201  assignVariable(var, varBind);
202 
203  } else {
204  throw IllegalParameters(
205  __FILE__, __LINE__, __func__,
206  "Operation doesn't have operand number: " +
207  Conversion::toString(operandIndex));
208  }
209 }
210 
211 /**
212  * Finalizes DAG by creating output terminals.
213  *
214  * TerminalNode objects are created for Those IO() operands, which are
215  * referred, but doesn't already have TerminalNode objects.
216  */
217 void
219  // find IO(x) references, which doesn't has yet terminal
220  unsigned int inputCount = operation_.numberOfInputs();
221  unsigned int outputCount = operation_.numberOfOutputs();
222 
223  std::set<unsigned int> unwrittenOutputs;
224  for (unsigned int i = 1; i <= outputCount; i++) {
225  unwrittenOutputs.insert(i + inputCount);
226  }
227 
228  for (std::map<std::string,TerminalBinding>::iterator iter =
229  ioVariables_.begin(); iter != ioVariables_.end(); iter++) {
230 
231  unwrittenOutputs.erase(iter->second.second);
232 
233  if (iter->second.first == NULL) {
234  VariableBinding& ioVar = getBinding(iter->second.second);
235  if (iter->second.second > inputCount + outputCount) {
236  throw IllegalParameters(
237  __FILE__, __LINE__, __func__,
238  TCEString("Operation ") + operation_.name() +
239  TCEString(" doesn't have result operand number: ") +
240  Conversion::toString(iter->second.second));
241  }
242  iter->second.first = new TerminalNode(iter->second.second);
243  dag_->addNode(*(iter->second.first));
244  OperationDAGEdge* newEdge =
245  new OperationDAGEdge(ioVar.second,1);
247  *(ioVar.first), *(iter->second.first), *newEdge);
248  }
249  }
250  if (!unwrittenOutputs.empty()) {
251  TCEString message = TCEString("DAG of operation: ") +
252  operation_.name() + " Does not write to output operand(s): ";
253  while (!unwrittenOutputs.empty()) {
254  message << Conversion::toString(*unwrittenOutputs.begin()) <<" ";
255  unwrittenOutputs.erase(unwrittenOutputs.begin());
256  }
257  throw IllegalParameters(__FILE__,__LINE__,__func__, message);
258  }
259  // TODO: verify IO variable information of operation description
260 }
261 
262 /**
263  * Declared new variable which can be used for temporary storage of
264  * IO() variables.
265  *
266  * @param var Token tree node containing variable name.
267  * @exception IllegalParameters If variable already exists.
268  */
269 void
271  const TokenizerData::TokenTreeNode* var) {
272  std::string varName = getVariableName(var);
273  if (variableBindings_.find(varName) != variableBindings_.end()) {
274  throw IllegalParameters(
275  __FILE__, __LINE__, __func__,
276  "Variable \"" + var->token().stringValue() +
277  "\" already exists.");
278  }
279  variableBindings_[varName] = VariableBinding(NULL, 0);
280 }
281 
282 /**
283  * Assign binding of destination variable to be source binding.
284  *
285  * @param src Tree node variable whose binding is set to destination.
286  * @param dst Binding that is set to source's binding.
287  */
288 void
291  std::string dstName = getVariableName(dst);
292 
293  if (variableBindings_.find(dstName) == variableBindings_.end() &&
294  ioVariables_.find(dstName) == ioVariables_.end()) {
295  throw IllegalParameters(
296  __FILE__, __LINE__, __func__,
297  "Variable \"" + dst->token().stringValue() +
298  "\" was not declared.");
299  }
300 
301  variableBindings_[dstName] = src;
302 }
303 
304 /**
305  * Assign binding of destination variable to be same than source.
306  *
307  * @param src Tree node variable whose binding is set to destination.
308  * @param dst Tree node variable whose binding is set to same that source's.
309  */
310 void
312  const TokenizerData::TokenTreeNode* dst,
313  const TokenizerData::TokenTreeNode* src) {
314  std::string dstName = getVariableName(dst);
315  variableBindings_[dstName] = getBinding(src);
316 }
317 
318 /**
319  * Retuns name of variable, for token tree node containing IO() call or
320  * variable name.
321  *
322  * @param var IO() call or variable name.
323  * @return Generated variable name for internal variable map.
324  * @exception IllegalParameter Parameter is not variable..
325  */
326 std::string
328  const TokenizerData::TokenTreeNode* var) {
329  // check if variable is function IO(2) or normal var
330  if (var->isFunctionCall()) {
331  unsigned int srcOperand = getIOOperand(var);
332 
333  std::string retVal =
334  "IO(" + Conversion::toString(srcOperand) + ")";
335 
336  // mark terminal as referenced, but not created
337  if (ioVariables_.find(retVal) == ioVariables_.end()) {
338  ioVariables_[retVal] = TerminalBinding(NULL, srcOperand);
339  }
340 
341  return retVal;
342 
343  } else if (var->token().isIdentifier()) {
344  return var->token().stringValue();
345 
346  } else {
347  throw IllegalParameters(
348  __FILE__, __LINE__, __func__,
349  "Parameter \"" + var->token().stringValue() +
350  "\" is not variable.");
351  }
352 }
353 
354 /**
355  * Returns node and operand index of any existing variable, IO() call or
356  * constant.
357  *
358  * @param var Funcion call or single identifier type of token tree node.
359  * @return Node and operand index of any existing variable or IO() call.
360  * @exception IllegalParameter Parameter isn't function call or variable name.
361  */
364 
365  // check if variable is function IO(2) or normal var
366  if (var->isFunctionCall()) {
367  unsigned int srcOperand = getIOOperand(var);
368  return getBinding(srcOperand);
369 
370  } else if (var->token().isIdentifier()) {
371  std::string varName = getVariableName(var);
372  return getBinding(varName);
373 
374  } else if (var->isInteger()) {
375  return getConstantBinding(var->intValue());
376 
377  } else {
378  throw IllegalParameters(
379  __FILE__, __LINE__, __func__,
380  "Parameter \"" + var->token().stringValue() +
381  "\" is not variable.");
382  }
383 }
384 
385 /**
386  * Returns node and operand index of any existing variable.
387  *
388  * @param varName Name of the variable whose current binding is requested.
389  * @return Node and operand index where variable is currently assigned.
390  * @exception IllegalParameters Variable is not declared.
391  */
393 OperationDAGBuilder::getBinding(std::string varName) {
394  if (variableBindings_.find(varName) == variableBindings_.end()) {
395  throw IllegalParameters(
396  __FILE__, __LINE__, __func__,
397  "Trying to use uninitialized variable: " + varName);
398  }
399  return variableBindings_[varName];
400 }
401 
402 /**
403  * Returns node and operand index of any existing variable.
404  *
405  * @param varName Name of the variable whose current binding is requested.
406  * @return Node and operand index where variable is currently assigned.
407  * @exception IllegalParameters Variable is not declared.
408  */
411  if (constantBindings_.find(value) == constantBindings_.end()) {
412  ConstantNode* newNode = new ConstantNode(value);
413  constantBindings_[value] = VariableBinding(newNode, 1);
414  dag_->addNode(*newNode);
415  }
416 
417  return constantBindings_[value];
418 }
419 
420 /**
421  * Returns node and operand index of IO() variable.
422  *
423  * If called first time creates TerminalNode and binds IO() to that
424  * node with operand index 1.
425  *
426  * @param operandIndex Number of IO whose current binding is requested.
427  * @return Node and operand index where IO() is currently assigned.
428  */
430 OperationDAGBuilder::getBinding(unsigned int operandIndex) {
431 
432  // if first reference, and its never set before,
433  // create startnode for variable and set
434  // outputbind to be 1
435 
436  // if variable name is used, it has to be created
437  // and initialized before
438  std::string varName =
439  "IO(" + Conversion::toString(operandIndex) + ")";
440 
441  if (variableBindings_.find(varName) == variableBindings_.end()) {
442  TerminalNode* newNode = new TerminalNode(operandIndex);
443  variableBindings_[varName] = VariableBinding(newNode, 1);
444  dag_->addNode(*newNode);
445 
446  // mark terminal as created for check phase in finalize
447  ioVariables_[varName] = TerminalBinding(newNode, operandIndex);
448  }
449 
450  return getBinding(varName);
451 }
452 
453 /**
454  * Returns operand's number of tree node, which contains reference to
455  * IO() variable.
456  *
457  * @param var Token tree node, which contains parsed IO(x) call.
458  * @return Operand number of IO(x) type of token tree node.
459  * @exception IllegalParameters If var isn't parsed IO() call.
460  */
461 unsigned int
463  if (var->leafCount() != 2 ||
464  var->leaf(0).token().stringValue() != "IO" ||
465  !var->leaf(1).leaf(0).token().isIntegerLiteral()) {
466  throw IllegalParameters(
467  __FILE__, __LINE__, __func__,
468  "Invalid parameter node \"" + var->token().stringValue() +
469  "\" != \"IO(x)\" call.");
470  }
471  return var->leaf(1).leaf(0).token().intValue();
472 }
TokenizerData::TokenTreeNode::intValue
long intValue() const
Definition: OperationDAGLanguageParser.hh:460
TokenizerData::EXPRESSION_STATEMENT
@ EXPRESSION_STATEMENT
Definition: OperationDAGLanguageParser.hh:214
OperationDAGLanguageParser.hh
OperationDAGBuilder::VariableBinding
std::pair< OperationDAGNode *, int > VariableBinding
Node and operand which is referred by a variable.
Definition: OperationDAGBuilder.hh:58
TokenizerData::Token::isIdentifier
bool isIdentifier() const
Definition: OperationDAGLanguageParser.hh:321
OperationDAGNode.hh
BoostGraph::connectNodes
virtual void connectNodes(const Node &nTail, const Node &nHead, Edge &e)
OperationPool::operation
Operation & operation(const char *name)
Definition: OperationPool.cc:99
OperationPimpl::name
TCEString name() const
Definition: OperationPimpl.cc:121
TokenizerData::TokenTreeNode::isAssignment
bool isAssignment() const
Definition: OperationDAGLanguageParser.hh:427
OperationPimpl
Definition: OperationPimpl.hh:54
OperationDAGBuilder::currentOperation_
OperationNode * currentOperation_
Currently created handled operation.
Definition: OperationDAGBuilder.hh:95
TokenizerData::Token::isIntegerLiteral
bool isIntegerLiteral() const
Definition: OperationDAGLanguageParser.hh:323
TerminalNode
Definition: TerminalNode.hh:47
OperationDAGBuilder::variableBindings_
std::map< std::string, VariableBinding > variableBindings_
Node and operand which are referred by IO(x) or declared variable.
Definition: OperationDAGBuilder.hh:98
OperationNode::referencedOperation
Operation & referencedOperation() const
Definition: OperationNode.cc:70
TokenizerData::TokenTreeNode::isInteger
bool isInteger() const
Definition: OperationDAGLanguageParser.hh:442
OperationDAGBuilder::rootNode_
const TokenizerData::TokenTreeNode & rootNode_
Root of tokenized data parsed from OSAL DAG source code.
Definition: OperationDAGBuilder.hh:92
BoostGraph::addNode
virtual void addNode(Node &node)
OperationNode
Definition: OperationNode.hh:47
Operand::isOutput
virtual bool isOutput() const
Definition: Operand.cc:155
NullOperation::instance
static NullOperation & instance()
OperationDAGEdge
Definition: OperationDAGEdge.hh:38
Conversion::toString
static std::string toString(const T &source)
OperationDAGBuilder::constantBindings_
std::map< long, VariableBinding > constantBindings_
Node representing constant value.
Definition: OperationDAGBuilder.hh:101
OperationDAGBuilder::parse
void parse()
Definition: OperationDAGBuilder.cc:64
OperationPimpl::numberOfOutputs
int numberOfOutputs() const
TokenizerData::TokenTreeNode::leaf
TokenTreeNode & leaf(int index) const
Definition: OperationDAGLanguageParser.hh:513
OperationDAGBuilder::ioVariables_
std::map< std::string, TerminalBinding > ioVariables_
IO(x) variables and corresponding TerminalNodes and operand indices.
Definition: OperationDAGBuilder.hh:104
OperationDAGBuilder::getConstantBinding
VariableBinding & getConstantBinding(long value)
Definition: OperationDAGBuilder.cc:410
OperationDAGEdge.hh
IllegalParameters
Definition: Exception.hh:113
OperationNode::toString
virtual std::string toString() const
Definition: OperationNode.cc:76
TokenizerData::DECLARATION
@ DECLARATION
Definition: OperationDAGLanguageParser.hh:184
OperationDAGBuilder::OperationDAGBuilder
OperationDAGBuilder(const OperationPimpl &operation, OperationDAG &dag, const TokenizerData::TokenTreeNode &root)
Definition: OperationDAGBuilder.cc:53
TokenizerData::TokenTreeNode
Definition: OperationDAGLanguageParser.hh:397
OperationDAG.hh
OperationDAG
Definition: OperationDAG.hh:43
__func__
#define __func__
Definition: Application.hh:67
TokenizerData::TokenTreeNode::leafCount
int leafCount() const
Definition: OperationDAGLanguageParser.hh:503
ConstantNode
Definition: ConstantNode.hh:43
Operation.hh
TokenizerData::TokenTreeNode::toStr
std::string toStr() const
Definition: OperationDAGLanguageParser.hh:524
TokenizerData::TokenTreeNode::isFunctionCall
bool isFunctionCall() const
Definition: OperationDAGLanguageParser.hh:410
OperationPimpl.hh
OperationDAGBuilder::assignVariable
void assignVariable(const TokenizerData::TokenTreeNode *dst, VariableBinding &src)
Definition: OperationDAGBuilder.cc:289
BoostGraph::hasNode
bool hasNode(const Node &) const
Operation
Definition: Operation.hh:59
Operation::operandCount
virtual int operandCount() const
Definition: Operation.cc:212
Operand.hh
TokenizerData::Token::stringValue
std::string stringValue() const
Definition: OperationDAGLanguageParser.hh:341
OperationDAGBuilder::connectOperandToNode
void connectOperandToNode(const TokenizerData::TokenTreeNode *var, unsigned int operandIndex)
Definition: OperationDAGBuilder.cc:162
Operation::operand
virtual Operand & operand(int id) const
Definition: Operation.cc:541
OperationDAGBuilder::operation_
const OperationPimpl & operation_
Definition: OperationDAGBuilder.hh:106
OperationDAGBuilder::dag_
OperationDAG * dag_
DAG where all nodes and edges are added.
Definition: OperationDAGBuilder.hh:89
OperationDAGBuilder::getVariableName
std::string getVariableName(const TokenizerData::TokenTreeNode *var)
Definition: OperationDAGBuilder.cc:327
OperationDAGBuilder::parseNode
void parseNode(const TokenizerData::TokenTreeNode *node)
Definition: OperationDAGBuilder.cc:84
TCEString
Definition: TCEString.hh:53
OperationDAGBuilder.hh
TerminalNode.hh
TokenizerData::ASSIGNMENT_EXPRESSION
@ ASSIGNMENT_EXPRESSION
Definition: OperationDAGLanguageParser.hh:180
ConstantNode.hh
OperationDAGBuilder::createOperationNode
void createOperationNode(const std::string &operation)
Definition: OperationDAGBuilder.cc:141
TokenizerData::Token::intValue
long intValue() const
Definition: OperationDAGLanguageParser.hh:333
OperationDAGBuilder::declareVariable
void declareVariable(const TokenizerData::TokenTreeNode *var)
Definition: OperationDAGBuilder.cc:270
OperationNode.hh
OperationDAGBuilder::finalize
void finalize()
Definition: OperationDAGBuilder.cc:218
OperationPool
Definition: OperationPool.hh:52
TokenizerData::Token::type_
OperationID type_
Definition: OperationDAGLanguageParser.hh:369
OperationDAGBuilder::getIOOperand
unsigned int getIOOperand(const TokenizerData::TokenTreeNode *var)
Definition: OperationDAGBuilder.cc:462
Operand::isInput
virtual bool isInput() const
Definition: Operand.cc:145
OperationDAGBuilder::TerminalBinding
std::pair< TerminalNode *, unsigned int > TerminalBinding
Information of object and index of operand of a variable.
Definition: OperationDAGBuilder.hh:61
OperationPool.hh
TokenizerData::TokenTreeNode::token
const Token & token() const
Definition: OperationDAGLanguageParser.hh:494
OperationDAGBuilder::getBinding
VariableBinding & getBinding(const TokenizerData::TokenTreeNode *var)
Definition: OperationDAGBuilder.cc:363
OperationPimpl::numberOfInputs
int numberOfInputs() const