OpenASIP  2.0
DataDependenceEdge.cc
Go to the documentation of this file.
1 /*
2  Copyright (c) 2002-2011 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 DataDependenceEdge.cc
26  *
27  * Implementation of data dependence edge class
28  *
29  * @author Heikki Kultala 2006 (heikki.kultala-no.spam-tut.fi)
30  * @note rating: red
31  */
32 
33 #include <cstring>
34 #include <climits>
35 
36 #include "DataDependenceEdge.hh"
37 
38 #include "TCEString.hh"
39 
40 #include "Conversion.hh"
41 
42 #include "MoveNode.hh"
43 #include "HWOperation.hh"
44 #include "ObjectState.hh"
45 #include "TerminalFUPort.hh"
46 #include "TerminalRegister.hh"
47 #include "Move.hh"
48 
50 
51 /**
52  * Constructor.
53  *
54  * @param edgereason which kind of data caused this dependence,
55  * is it register, memory, operation, ra etc.
56  * @param deptype whether this is real dependence(raw),
57  * antidependence(war) or output dependence(waw)
58  * @param data some data about the dependence, for example reg name.
59  * @param guard if this dependence is a guard use.
60  * @param certainAlias if this memory dep is a known to always alias.
61  * @param tailPS whether the tail of the dep is a pseudo data usage
62  * @param headPS whether the head of the dep is a pseudo data usage
63  * @param loopEdge loop iteration depth if the dependence goes over a loop
64  */
66  EdgeReason edgereason,
67  DependenceType deptype,
68  TCEString data, bool guard,
69  bool certainAlias, bool tailPs,
70  bool headPs, int loopEdge) :
71  dependenceType_(deptype), edgeReason_(edgereason),
72  loopEdge_(loopEdge) {
73 
74  edgeProperties_ = 0;
75  if (guard)
77 
78  if (certainAlias)
80 
81  if (tailPs)
83 
84  if (headPs)
86 
87  assert(loopEdge < UCHAR_MAX);
88  loopEdge = (unsigned char)loopEdge_;
89 
90  data_ = NULL;
91  setData(data);
92  if (edgeReason_ == EDGE_REGISTER) {
93  assert(data_ != NULL && "Register name required for reg deps");
94  }
95 }
96 
97 /**
98  * Constructor.
99  *
100  * @param edgereason which kind of data caused this dependence,
101  * is it register, memory, operation, ra etc.
102  * @param deptype whether this is real dependence(raw),
103  * antidependence(war) or output dependence(waw)
104  * @param guard if this dependence is a guard use.
105  * @param certainAlias if this memory dep is a known to always alias.
106  * @param tailPS whether the tail of the dep is a pseudo data usage
107  * @param headPS whether the head of the dep is a pseudo data usage
108  * @param loopEdge loop iteration depth if the dependence goes over a loop
109  */
111  EdgeReason edgereason,
112  DependenceType deptype,
113  bool guard, bool certainAlias,
114  bool tailPs, bool headPs,
115  int loopEdge) :
116  dependenceType_(deptype), edgeReason_(edgereason),
117  loopEdge_(loopEdge) {
118 
119  edgeProperties_ = 0;
120  if (guard)
122 
123  if (certainAlias)
125 
126  if (tailPs)
128 
129  if (headPs)
131 
132  assert(loopEdge < UCHAR_MAX);
133  loopEdge = (unsigned char)loopEdge_;
134  data_ = NULL;
135  if (edgeReason_ == EDGE_REGISTER) {
136  assert(0 && "Register name required for reg deps");
137  }
138 
139 }
140 
141 /**
142  * Copy constructor.
143  *
144  * Because of data_ that needs to be deep copied.
145  */
147  GraphEdge() {
148  this->dependenceType_ = other.dependenceType_;
149  this->edgeReason_ = other.edgeReason_;
150  this->edgeProperties_ = other.edgeProperties_;
151  this->loopEdge_ = other.loopEdge_;
152  if (other.data_ != NULL) {
153  data_ = new char[strlen(other.data_)+1];
154  strcpy(data_, other.data_);
155  } else {
156  data_ = NULL;
157  }
158 }
159 
160 /**
161  * Copy constructor which may modify the loop property
162  *
163  * @param other edge to copy
164  * @invertLoop whether to invent oop propert 0->1, 1->0
165  */
167  const DataDependenceEdge& other, bool invertLoop) :
168  GraphEdge() {
169  this->dependenceType_ = other.dependenceType_;
170  this->edgeReason_ = other.edgeReason_;
171  this->edgeProperties_ = other.edgeProperties_;
172  if (!invertLoop || other.loopEdge_ > 1) {
173  this->loopEdge_ = other.loopEdge_;
174  } else {
175  this->loopEdge_ = !other.loopEdge_;
176  }
177  if (other.data_ != NULL) {
178  data_ = new char[strlen(other.data_)+1];
179  strcpy(data_, other.data_);
180  } else {
181  data_ = NULL;
182  }
183 }
184 
185 
186 /**
187  * Prints statistics about the created edges to the given
188  * output stream.
189  */
190 void
191 DataDependenceEdge::printStats(std::ostream& out) {
192  out << "register anti-dependencies: " << regAntidepCount_ << std::endl;
193 }
194 
195 /**
196  * Returns a textual representation of the edge.
197  *
198  * This is used in the generated dot files.
199  */
200 TCEString
202  if (loopEdge_ != 0) {
203  return TCEString("LOOP:") + Conversion::toString(int(loopEdge_)) + "_" +
204  edgeReasonSt() + guardSt() + depTypeSt() + pseudoSt() +
205  ':' + data();
206  }
207  return edgeReasonSt() + guardSt() + depTypeSt() + pseudoSt() + ':' + data();
208 }
209 
210 /**
211  * Returns a textual representation of the edge.
212  *
213  * @param tail the source node of the dependence. Needed
214  * for looking up operation latencies in scheduled code.
215  *
216  * @todo This should be refactored.
217  *
218  * This is used in the generated dot files.
219  */
220 TCEString
222  if (loopEdge_ !=0) {
223  return TCEString("LOOP:") + Conversion::toString(int(loopEdge_)) +
224  "_" + edgeReasonSt() + guardSt() + depTypeSt() + pseudoSt() +
225  ':' + data() + latencySt(tail);
226  }
227  return edgeReasonSt() + guardSt() + depTypeSt() + pseudoSt() +
228  ':' + data() + latencySt(tail);
229 }
230 
231 /**
232  * Helper method for creating the toString string.
233  */
234 TCEString
236  switch (edgeReason_) {
237  case EDGE_REGISTER:
238  return "R";
239  case EDGE_MEMORY:
240  if (certainAlias())
241  return "M_T";
242  else
243  return "M";
244  case EDGE_FUSTATE:
245  return "F";
246  case EDGE_OPERATION:
247  return "O";
248  case EDGE_RA:
249  return "RA";
250  }
251  return "BUG";
252 }
253 
254 /**
255  * Helper method for creating the toString string.
256  */
257 TCEString
259  switch (dependenceType_) {
260  case DEP_RAW:
261  return "_raw";
262  case DEP_WAR:
263  return "_war";
264  case DEP_WAW:
265  return "_waw";
266  case DEP_UNKNOWN:
267  default:
268  return "";
269  }
270 }
271 
272 /**
273  * Helper method for creating the toString string.
274  */
275 TCEString
277  return guardUse() ? "_G" : "";
278 }
279 
280 /**
281  * Helper method for creating the toString string.
282  */
283 TCEString
285  return TCEString(tailPseudo() ? "_TP" : "") + (headPseudo() ? "_HP" : "");
286 }
287 
288 /**
289  * Helper method for creating the toString string.
290  * Finds out the latency of operation dependences.
291  */
292 
293 TCEString
295  if (edgeReason_ == EDGE_OPERATION && node.isAssigned()) {
296  if (node.move().isTriggering()) {
298  = dynamic_cast<TTAProgram::TerminalFUPort&>
299  (node.move().destination());
300  std::stringstream ss;
301  std::string lat;
302  ss << tfu.hwOperation()->latency();
303  ss >> lat;
304  return ":" + lat;
305  } else {
306  return ":0";
307  }
308  } else {
309  return "";
310  }
311 }
312 
313 /**
314  * Comparator.
315  *
316  * Checks whether the two edges are identical.
317  */
318 bool
320  return dependenceType_ == other.dependenceType_ &&
321  edgeReason_ == other.edgeReason_ &&
322  data() == other.data() &&
323  guardUse() == other.guardUse() &&
324  certainAlias() == other.certainAlias() &&
325  tailPseudo() == other.tailPseudo() &&
326  headPseudo() == other.headPseudo() &&
327  isBackEdge() == other.isBackEdge();
328 }
329 
330 void
332  delete[] data_;
333  data_ = new char[newData.length() + 1];
334  strncpy(data_, newData.c_str(), newData.length() + 1);
335 }
336 
337 /**
338  * State dumping for XML generation.
339  *
340  * @param tail source node of the edge
341  * @param head sink node of the edge
342  */
343 
346  const MoveNode& tail,
347  const MoveNode& head) {
348 
349  ObjectState* edgeOS = new ObjectState("edge");
350  ObjectState* tailOS = new ObjectState("nref", edgeOS);
351  ObjectState* headOS = new ObjectState("nref", edgeOS);
352  ObjectState* typeOS = new ObjectState("type", edgeOS);
353  ObjectState* reasonOS = new ObjectState("reason", edgeOS);
354 
355  tailOS->setValue(tail.nodeID());
356  headOS->setValue(head.nodeID());
357 
358  switch (dependenceType_) {
359  case DEP_UNKNOWN:
360  typeOS->setName("unknown");
361  break;
362  case DEP_RAW:
363  typeOS->setName("raw");
364  break;
365  case DEP_WAR:
366  typeOS->setName("war");
367  break;
368  case DEP_WAW:
369  typeOS->setName("waw");
370  break;
371  case DEP_TRIGGER:
372  typeOS->setName("trg");
373  break;
374  }
375 
376  switch (edgeReason_) {
377  case EDGE_REGISTER:
378  reasonOS->setName("reg");
379  break;
380  case EDGE_MEMORY:
381  reasonOS->setName("mem");
382  break;
383  case EDGE_FUSTATE:
384  reasonOS->setName("fu");
385  break;
386  case EDGE_OPERATION:
387  reasonOS->setName("op");
388  break;
389  case EDGE_RA:
390  reasonOS->setName("ra");
391  break;
392  }
393 
394  // Add operation latency information to trigger moves
395  if (tail.isMove() && tail.move().isTriggering()) {
397  = dynamic_cast<TTAProgram::TerminalFUPort&>
398  (tail.move().destination());
399 
400  ObjectState* latencyOS = new ObjectState("lat", edgeOS);
401  latencyOS->setValue(Conversion::toString(tfu.hwOperation()->latency()));
402  }
403 
404  if (loopEdge_ != 0) {
405  ObjectState* loopEdgeOS = new ObjectState("dist", edgeOS);
406  loopEdgeOS->setValue(Conversion::toString(static_cast<int>(loopEdge_)));
407  }
408 
409  return edgeOS;
410 }
411 
DataDependenceEdge::edgeReasonSt
TCEString edgeReasonSt() const
Definition: DataDependenceEdge.cc:235
TTAProgram::Move::isTriggering
bool isTriggering() const
Definition: Move.cc:284
DataDependenceEdge::latencySt
TCEString latencySt(MoveNode &node) const
Definition: DataDependenceEdge.cc:294
DataDependenceEdge::DEP_TRIGGER
@ DEP_TRIGGER
Definition: DataDependenceEdge.hh:50
DataDependenceEdge::isBackEdge
bool isBackEdge() const
Definition: DataDependenceEdge.hh:118
DataDependenceEdge::pseudoSt
TCEString pseudoSt() const
Definition: DataDependenceEdge.cc:284
TTAProgram::Move::destination
Terminal & destination() const
Definition: Move.cc:323
GraphNode::nodeID
int nodeID() const
DataDependenceEdge::setData
void setData(const TCEString &newData)
Definition: DataDependenceEdge.cc:331
ObjectState
Definition: ObjectState.hh:59
MoveNode
Definition: MoveNode.hh:65
DataDependenceEdge::EDGE_REGISTER
@ EDGE_REGISTER
Definition: DataDependenceEdge.hh:53
DataDependenceEdge::DependenceType
DependenceType
Definition: DataDependenceEdge.hh:45
ObjectState::setName
void setName(const std::string &name)
Conversion::toString
static std::string toString(const T &source)
DataDependenceEdge::tailPseudo
bool tailPseudo() const
Definition: DataDependenceEdge.hh:109
DataDependenceEdge.hh
DataDependenceEdge::guardSt
TCEString guardSt() const
Definition: DataDependenceEdge.cc:276
TerminalRegister.hh
TCEString.hh
DataDependenceEdge::edgeProperties_
unsigned char edgeProperties_
Definition: DataDependenceEdge.hh:178
DataDependenceEdge::DataDependenceEdge
DataDependenceEdge(EdgeReason edgereason, DependenceType deptype, TCEString data, bool guard=false, bool certainAlias=false, bool tailPseudo=false, bool headPseudo=false, int loop=0)
Definition: DataDependenceEdge.cc:65
assert
#define assert(condition)
Definition: Application.hh:86
DataDependenceEdge::DEP_UNKNOWN
@ DEP_UNKNOWN
Definition: DataDependenceEdge.hh:46
MoveNode::isMove
bool isMove() const
HWOperation.hh
DataDependenceEdge::EPF_CERTAIN_ALIAS
@ EPF_CERTAIN_ALIAS
Definition: DataDependenceEdge.hh:171
DataDependenceEdge::DEP_RAW
@ DEP_RAW
Definition: DataDependenceEdge.hh:47
Conversion.hh
DataDependenceEdge::loopEdge_
unsigned char loopEdge_
Definition: DataDependenceEdge.hh:179
DataDependenceEdge::EDGE_FUSTATE
@ EDGE_FUSTATE
Definition: DataDependenceEdge.hh:55
DataDependenceEdge::EDGE_OPERATION
@ EDGE_OPERATION
Definition: DataDependenceEdge.hh:56
ObjectState.hh
DataDependenceEdge::toString
TCEString toString() const
Definition: DataDependenceEdge.cc:201
DataDependenceEdge::EPF_GUARD
@ EPF_GUARD
Definition: DataDependenceEdge.hh:170
TerminalFUPort.hh
DataDependenceEdge::certainAlias
bool certainAlias() const
Definition: DataDependenceEdge.hh:103
DataDependenceEdge::data
const TCEString data() const
Definition: DataDependenceEdge.hh:142
DataDependenceEdge::EPF_HEAD_PSEUDO
@ EPF_HEAD_PSEUDO
Definition: DataDependenceEdge.hh:173
DataDependenceEdge::DEP_WAW
@ DEP_WAW
Definition: DataDependenceEdge.hh:49
TTAProgram::TerminalFUPort
Definition: TerminalFUPort.hh:56
DataDependenceEdge::guardUse
bool guardUse() const
Definition: DataDependenceEdge.hh:100
DataDependenceEdge::dependenceType_
unsigned char dependenceType_
Definition: DataDependenceEdge.hh:176
DataDependenceEdge::operator==
bool operator==(const DataDependenceEdge &other) const
Definition: DataDependenceEdge.cc:319
MoveNode::move
TTAProgram::Move & move()
DataDependenceEdge::EDGE_MEMORY
@ EDGE_MEMORY
Definition: DataDependenceEdge.hh:54
GraphEdge
Definition: GraphEdge.hh:52
TCEString
Definition: TCEString.hh:53
TTAProgram::TerminalFUPort::hwOperation
virtual const TTAMachine::HWOperation * hwOperation() const
Definition: TerminalFUPort.cc:379
DataDependenceEdge::printStats
static void printStats(std::ostream &out)
Definition: DataDependenceEdge.cc:191
DataDependenceEdge::saveState
ObjectState * saveState(const MoveNode &tail, const MoveNode &head)
Definition: DataDependenceEdge.cc:345
DataDependenceEdge
Definition: DataDependenceEdge.hh:43
TTAMachine::HWOperation::latency
int latency() const
Definition: HWOperation.cc:216
MoveNode::isAssigned
bool isAssigned() const
Definition: MoveNode.cc:367
Move.hh
DataDependenceEdge::headPseudo
bool headPseudo() const
Definition: DataDependenceEdge.hh:115
DataDependenceEdge::DEP_WAR
@ DEP_WAR
Definition: DataDependenceEdge.hh:48
MoveNode.hh
DataDependenceEdge::EDGE_RA
@ EDGE_RA
Definition: DataDependenceEdge.hh:57
DataDependenceEdge::depTypeSt
TCEString depTypeSt() const
Definition: DataDependenceEdge.cc:258
ObjectState::setValue
void setValue(const std::string &value)
DataDependenceEdge::data_
char * data_
Definition: DataDependenceEdge.hh:181
DataDependenceEdge::EdgeReason
EdgeReason
Definition: DataDependenceEdge.hh:52
DataDependenceEdge::EPF_TAIL_PSEUDO
@ EPF_TAIL_PSEUDO
Definition: DataDependenceEdge.hh:172
DataDependenceEdge::edgeReason_
unsigned char edgeReason_
Definition: DataDependenceEdge.hh:177
DataDependenceEdge::regAntidepCount_
static int regAntidepCount_
Definition: DataDependenceEdge.hh:154