OpenASIP  2.0
DataDependenceGraph.hh
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 DataDependenceGraph.hh
26  *
27  * Declaration of data dependence graph class
28  *
29  * @author Heikki Kultala 2006-2009 (heikki.kultala-no.spam-tut.fi)
30  * @note rating: red
31  */
32 
33 #ifndef TTA_DATA_DEPENDENCE_GRAPH_HH
34 #define TTA_DATA_DEPENDENCE_GRAPH_HH
35 
36 #include <map>
37 #include <set>
38 #include <list>
39 #include <utility>
40 #include <vector>
41 #include <utility>
42 
43 #include "BoostGraph.hh"
44 #include "DataDependenceEdge.hh"
45 #include "MoveNode.hh"
46 #include "ProgramOperation.hh"
47 
48 typedef std::vector<ProgramOperationPtr> POList;
49 typedef POList::iterator POLIter;
50 
51 class BasicBlockNode;
52 class DataGraphBuilder;
53 class ControlFlowGraph;
54 class MoveNodeUse;
55 struct LiveRange;
56 
57 namespace TTAMachine {
58  class BaseRegisterFile;
59  class Machine;
60 }
61 
62 namespace TTAProgram {
63  class CodeSnippet;
64  class BasicBlock;
65 }
66 
68  public BoostGraph<MoveNode, DataDependenceEdge> {
69 public:
70 
71  struct UndoData {
74  std::map<DataDependenceEdge*,
75  TCEString, DataDependenceEdge::Comparator> changedDataEdges;
76  };
77 
83  };
84 
88  };
89 
91  EWH_HEURISTIC, ///< Weights memory dependencies more, etc.
92  EWH_REAL, ///< Height returns the minimum cycle count for the
93  ///< schedule given enough resources.
95  };
96 
98  std::set<TCEString> allParamRegs,
99  const TCEString& name="",
100  AntidependenceLevel antidependenceLevel = ALL_ANTIDEPS,
101  BasicBlockNode* ownedBBN = NULL,
102  bool containsProcedure=false, bool noLoopEdges=false);
103 
104  virtual ~DataDependenceGraph();
105 
106  /* Gets the BB in which this move belongs. This should be moved to
107  a better place: DDG API should not deal with basic blocks. Correct
108  place BasicBlockNode?
109 
110  This information is needed for PDG construction, and putting it to
111  BBN does not work. I know this is ugly, but currently these is no
112  better place for this.
113  */
114  const BasicBlockNode& getBasicBlockNode(const MoveNode& mn) const;
116  void setBasicBlockNode(const MoveNode& mn, BasicBlockNode& bbn);
117 
118  int programOperationCount() const;
120  const ProgramOperation& programOperation(int index) const;
122 
125 
126  // should not be called by the user, only by a DataDependenceGraphBuilder
127  void addNode(MoveNode& moveNode);
128  void addNode(MoveNode& moveNode, MoveNode& relatedNode);
129  void addNode(MoveNode& moveNode, BasicBlockNode& bblock);
132 
134 
135  int edgeLatency(const DataDependenceEdge& edge, int ii,
136  const MoveNode* tail, const MoveNode* head) const;
137 
138  int earliestCycle(
139  const MoveNode& moveNode, unsigned int ii = UINT_MAX,
140  bool ignoreRegWaRs = false,
141  bool ignoreRegWaWs = false, bool ignoreGuards = false,
142  bool ignoreFUDeps = false,
143  bool ignoreSameOperationEdges = false,
144  bool assumeBypassing = false) const;
145 
146  int latestCycle(
147  const MoveNode& moveNode, unsigned int ii = UINT_MAX,
148  bool ignoreRegAntideps = false,
149  bool ignoreUnscheduledSuccessors = true,
150  bool ignoreGuards = false,
151  bool ignoreFUDeps = false,
152  bool ignoreSameOperationEdges = false) const;
153 
154  bool hasUnscheduledSuccessors(const MoveNode& mn) const;
155  bool hasUnscheduledPredecessors(const MoveNode& mn) const;
156 
157  int smallestCycle() const;
158  int largestCycle() const;
159  int scheduledNodeCount() const;
160 
161  NodeSet unscheduledMoves() const;
162  NodeSet scheduledMoves() const;
163  NodeSet movesAtCycle(int cycle) const;
164 
166  MoveNode* lastGuardDefMove(MoveNode& moveNode);
167  NodeSet guardDefMoves(const MoveNode& moveNode);
168 
169  MoveNode*
172  int registerIndex,
173  int lastCycleToTest = INT_MAX) const;
174 
175  NodeSet
177  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const;
178 
179  NodeSet
181  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const;
182 
183  NodeSet
185  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const;
186 
187  MoveNode*
189  const TTAMachine::BaseRegisterFile& rf,
190  int registerIndex,
191  int firstCycleToTest = 0) const;
192 
193  MoveNode*
195  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const;
196 
197  NodeSet
199  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const;
200 
201  NodeSet
203  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const;
204 
205  MoveNode*
207  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const;
208 
209  MoveNode*
211  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const;
212 
213  int lastRegisterCycle(
214  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const;
215 
216  int firstRegisterCycle(
217  const TTAMachine::BaseRegisterFile& rf, int registerIndex) const;
218 
219  void sanityCheck() const;
220 
221  /// Dot printing related methods
222  virtual TCEString dotString() const;
223  virtual void setCycleGrouping(bool flag);
224  virtual void setProgramOperationNodes(bool flag) {
226  }
227  // XML dumping
228  void writeToXMLFile(std::string fileName) const;
229 
230  bool mergeAndKeepAllowed(MoveNode& sourceNode, MoveNode& userNode);
231  TCEString removeRAWEdges(MoveNode& sourceNode, MoveNode& userNode);
232  bool isLoopBypass(MoveNode& sourceNode, MoveNode& userNode);
233 
234  bool mergeAndKeepUser(
235  MoveNode& resultNode, MoveNode& userNode, bool force = false);
236  bool mergeAndKeepSource(
237  MoveNode& resultNode, MoveNode& userNode, bool force = false);
238  void unMergeUser(MoveNode& resultNode, MoveNode& mergedNode, bool loopBypass = false);
239 
240  // guard converted from register guard to portguard.
241  void guardConverted(MoveNode& guardSrc, MoveNode& dst);
242 
243  // guard converted back from portguard to register guard.
244  void guardRestored(MoveNode& guardSrc, MoveNode& dst);
245 
246  bool resultUsed(MoveNode& resultNode);
247  bool resultUsed(MoveNode& resultNode, MoveNode* regCopy);
248 
249  void removeNode(MoveNode& node);
250  void deleteNode(MoveNode& node);
251 
253 
254  int edgeWeight(DataDependenceEdge& e, const MoveNode& hNode) const;
255  bool predecessorsReady(MoveNode& node) const;
256  bool successorsReady(MoveNode& node) const;
257  bool otherSuccessorsScheduled(MoveNode& node, const NodeSet& ignoredNodes) const;
258 
260  const TTAMachine::Machine& machine() const { return *machine_; }
261 
262  bool connectOrDeleteEdge(
263  const MoveNode& tailNode, const MoveNode& headNode,
265 
267  NodeSet& nodes, bool includeLoops = false);
268 
270  TTAProgram::CodeSnippet& cs, bool includeLoops = false);
271 
273  std::list<TTAProgram::CodeSnippet*>& codeSnippets,
274  bool includeLoops = false);
275 
277  bool removeMemAntideps=true, bool ignoreMemDeps=false);
280 
281  MoveNode& nodeOfMove(const TTAProgram::Move& move);
282 
283  void dropBackEdges();
284 
285  void fixInterBBAntiEdges(
286  BasicBlockNode& bbn1, BasicBlockNode& bbn2, bool loopEdges);
287 
288  // Duplicates all in- and outgoing edges in dst to src
289  void copyDependencies(
290  const MoveNode& src, MoveNode& dst, bool ignoreSameBBBackedges,
291  bool moveOverLoopEdge = true);
292 
293  void copyIncomingGuardEdges(const MoveNode& src, MoveNode& dst);
294  void copyOutgoingGuardWarEdges(const MoveNode& src, MoveNode& dst);
295 
297 
300  const MoveNode& mn, int allowGuardEdges = 2, int backEdges = 0) const;
301 
303  const MoveNode& mn,
304  bool allowGuardEdges = false,
305  bool allowBackEdges = false) const;
306 
307  std::map<DataDependenceEdge*, MoveNode*, DataDependenceEdge::Comparator>
309  const MoveNode& mn, bool allowBackEdges) const;
310 
311  NodeSet regWarSuccessors(const MoveNode& node) const;
312  NodeSet regRawSuccessors(const MoveNode& node) const;
313  NodeSet regWawSuccessors(const MoveNode& node) const;
314  NodeSet regDepSiblings(const MoveNode& mn) const;
315  NodeSet regRawPredecessors(const MoveNode& node, int backedges=0) const;
316 
318 
319  bool exclusingGuards(const MoveNode& mn1, const MoveNode& mn2) const;
320  bool sameGuards(const MoveNode& mn1, const MoveNode& mn2) const;
321 
322  int rWarEdgesOut(MoveNode& mn);
323  int regRawSuccessorCount(const MoveNode& mn, bool onlyScheduled);
324 
325  bool guardsAllowBypass(const MoveNode& defNode,
326  const MoveNode& useNode,
327  bool loopBypass = false);
328 
330  const MoveNode& node, const std::string& sp) const;
331 
332  EdgeSet copyDepsOver(MoveNode& node, bool anti, bool raw);
333 
334  void copyDepsOver(MoveNode& node1, MoveNode& node2, bool anti, bool raw);
335 
336  void combineNodes(
337  MoveNode& node1, MoveNode& node2, MoveNode& destination);
338 
339  std::pair<MoveNode*, MoveNode*> findLoopLimitAndIndex(MoveNode& jumpMove);
340 
341  std::pair<MoveNode*, int> findLoopIndexUpdate(MoveNode* indexMove);
342 
343  MoveNode* findLoopIndexInit(MoveNode& updateMove);
344 
345  bool writesJumpGuard(const MoveNode& moveNode);
346 
347  void moveFUDependenciesToTrigger(MoveNode& trigger);
348 
350  MoveNode& lrNode, bool writingNode, bool guardUseNode) const;
351 
354 
358 
360  MoveNode& src, MoveNode& dest, MoveNode& antidepPoint,
361  DataDependenceEdge& lrEdge,
362  const TCEString& oldReg, const TCEString& newReg);
363 
364  void copyExternalInEdges(MoveNode& nodeCopy, const MoveNode& source);
365  void copyExternalOutEdges(MoveNode& nodeCopy, const MoveNode& source);
366 
369  const MoveNodeUse& mnd, const TCEString& reg,
371 
372  void updateRegUse(
373  const MoveNodeUse& mnd, const TCEString& reg,
375 
378 
381  }
382 
385  }
386 
389  }
390 
391  bool hasRegWaw(const MoveNodeUse& mnu, std::set<MoveNodeUse> targets) const;
392 
393  bool isNotAvoidable(const DataDependenceEdge& edge) const;
394 
395  bool isLoopInvariant(const MoveNode& mn) const;
396 
397  bool hasOtherRegWawSources(const MoveNode& mn) const;
398 
399  MoveNode* findBypassSource(const MoveNode& mn);
400 
401  void copyIncomingRawEdges(const MoveNode& src, MoveNode& dst);
402 
404  MoveNode& sourceNode, MoveNode& mergedNode, const TCEString& reg);
405 
406  void setNodeBB(
407  MoveNode& mn, BasicBlockNode& bblock, DataDependenceGraph* updater);
408 
409  void undo(UndoData& undoData);
410 
411  EdgeSet operationInEdges(const MoveNode& node) const;
413 private:
414 
416  NodeSet& queue, NodeSet& finalDest, NodeSet& predQueue,
417  NodeSet& predFinalDest, bool guard) const;
418 
420  int rAntiEdgesIn(MoveNode& mn);
421 
423 
424  bool hasEqualEdge(
425  const MoveNode& tailNode, const MoveNode& headNode,
426  const DataDependenceEdge& edge) const;
427 
428  int getOperationLatency(const TCEString& name) const;
429 
430  std::set<TCEString> allParamRegs_;
431 
432  // cache to make things faster
433  // may not be used with iterator.
434  std::map<const TTAProgram::Move*, MoveNode*> nodesOfMoves_;
435 
436  // own all the programoperations
438  std::map<const MoveNode*, BasicBlockNode*> moveNodeBlocks_;
439 
440  /// Dot printing related variables.
441  /// Group the printed MoveNodes according to their cycles.
443  /// The moves belonging to the same program operation
444  /// are merged to a single node. Reduces the complexity of the graph.
446 
447  // Machine related variables.
450  std::map<TCEString, int> operationLatencies_;
451  int rrCost_;
452 
456 
457  /// The heuristics to use to weight edges in the longest path computation.
459 };
460 
461 #endif
DataDependenceGraph::registerAndRAInEdges
EdgeSet registerAndRAInEdges(const MoveNode &node) const
Definition: DataDependenceGraph.cc:5930
DataDependenceGraph::EWH_DEFAULT
@ EWH_DEFAULT
Definition: DataDependenceGraph.hh:94
DataDependenceGraph::predecessorsReady
bool predecessorsReady(MoveNode &node) const
Definition: DataDependenceGraph.cc:3176
DataDependenceGraph::lastScheduledRegisterRead
MoveNode * lastScheduledRegisterRead(const TTAMachine::BaseRegisterFile &rf, int registerIndex, int lastCycleToTest=INT_MAX) const
Definition: DataDependenceGraph.cc:766
DataDependenceGraph::onlyRegisterRawDestinationsWithEdges
std::map< DataDependenceEdge *, MoveNode *, DataDependenceEdge::Comparator > onlyRegisterRawDestinationsWithEdges(const MoveNode &mn, bool allowBackEdges) const
Definition: DataDependenceGraph.cc:4124
TTAProgram
Definition: Estimator.hh:65
DataDependenceGraph::SINGLE_BB_LOOP_ANTIDEPS
@ SINGLE_BB_LOOP_ANTIDEPS
Definition: DataDependenceGraph.hh:81
DataDependenceGraph::isLoopBypass
bool isLoopBypass(MoveNode &sourceNode, MoveNode &userNode)
Definition: DataDependenceGraph.cc:1916
DataDependenceGraph::removeIncomingGuardEdges
void removeIncomingGuardEdges(MoveNode &node)
Definition: DataDependenceGraph.cc:5466
DataDependenceGraph::firstRegisterCycle
int firstRegisterCycle(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:981
DataDependenceGraph::lastScheduledRegisterWrites
NodeSet lastScheduledRegisterWrites(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1206
DataDependenceGraph::dotProgramOperationNodes_
bool dotProgramOperationNodes_
The moves belonging to the same program operation are merged to a single node. Reduces the complexity...
Definition: DataDependenceGraph.hh:445
DataDependenceGraph::regRawSuccessors
NodeSet regRawSuccessors(const MoveNode &node) const
Definition: DataDependenceGraph.cc:4272
DataDependenceGraph::delaySlots_
int delaySlots_
Definition: DataDependenceGraph.hh:449
DataDependenceGraph::machine
const TTAMachine::Machine & machine() const
Definition: DataDependenceGraph.hh:260
BoostGraph< MoveNode, DataDependenceEdge >::tailNode
virtual Node & tailNode(const Edge &edge) const
DataDependenceGraph::scheduledNodeCount
int scheduledNodeCount() const
Definition: DataDependenceGraph.cc:1859
DataDependenceGraph::programOperation
ProgramOperation & programOperation(int index)
Definition: DataDependenceGraph.cc:227
DataDependenceGraph::edgeLatency
int edgeLatency(const DataDependenceEdge &edge, int ii, const MoveNode *tail, const MoveNode *head) const
Definition: DataDependenceGraph.cc:311
DataDependenceGraph::firstScheduledRegisterWrite
MoveNode * firstScheduledRegisterWrite(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:847
DataDependenceGraph::renamedSimpleLiveRange
void renamedSimpleLiveRange(MoveNode &src, MoveNode &dest, MoveNode &antidepPoint, DataDependenceEdge &lrEdge, const TCEString &oldReg, const TCEString &newReg)
Definition: DataDependenceGraph.cc:5182
BoostGraph< MoveNode, DataDependenceEdge >::headNode
virtual Node & headNode(const Edge &edge) const
DataDependenceGraph::registerAntidependenceLevel_
AntidependenceLevel registerAntidependenceLevel_
Definition: DataDependenceGraph.hh:455
BoostGraph< MoveNode, DataDependenceEdge >::node
Node & node(const int index) const
DataDependenceGraph::edgeWeight
int edgeWeight(DataDependenceEdge &e, const MoveNode &hNode) const
Definition: DataDependenceGraph.cc:2910
DataDependenceGraph::fixInterBBAntiEdges
void fixInterBBAntiEdges(BasicBlockNode &bbn1, BasicBlockNode &bbn2, bool loopEdges)
Definition: DataDependenceGraph.cc:3689
DataDependenceGraph::resultUsed
bool resultUsed(MoveNode &resultNode)
Definition: DataDependenceGraph.cc:2348
DataDependenceGraph::setBasicBlockNode
void setBasicBlockNode(const MoveNode &mn, BasicBlockNode &bbn)
Definition: DataDependenceGraph.cc:216
DataDependenceGraph::copyIncomingRawEdges
void copyIncomingRawEdges(const MoveNode &src, MoveNode &dst)
Definition: DataDependenceGraph.cc:5770
DataDependenceGraph::findLimitingAntidependenceSource
MoveNode * findLimitingAntidependenceSource(MoveNode &mn)
Definition: DataDependenceGraph.cc:5272
DataDependenceGraph::sameGuards
bool sameGuards(const MoveNode &mn1, const MoveNode &mn2) const
Definition: DataDependenceGraph.cc:4506
DataDependenceGraph::findLoopLimitAndIndex
std::pair< MoveNode *, MoveNode * > findLoopLimitAndIndex(MoveNode &jumpMove)
Definition: DataDependenceGraph.cc:4618
BoostGraph< MoveNode, DataDependenceEdge >::NodeSet
std::set< MoveNode *, typename MoveNode ::Comparator > NodeSet
Definition: BoostGraph.hh:86
BoostGraph.hh
DataDependenceGraph::rWawRawEdgesOutUncond
bool rWawRawEdgesOutUncond(MoveNode &mn)
Definition: DataDependenceGraph.cc:3978
MoveNodeUse
Definition: MoveNodeUse.hh:20
DataDependenceGraph::addProgramOperation
void addProgramOperation(ProgramOperationPtr po)
Definition: DataDependenceGraph.cc:298
DataDependenceGraph::onlyRegisterRawAncestor
const MoveNode * onlyRegisterRawAncestor(const MoveNode &node, const std::string &sp) const
Definition: DataDependenceGraph.cc:4203
DataDependenceGraph::guardRenamed
DataDependenceGraph::UndoData guardRenamed(MoveNode &mn)
Definition: DataDependenceGraph.cc:5006
DataDependenceGraph::~DataDependenceGraph
virtual ~DataDependenceGraph()
Definition: DataDependenceGraph.cc:95
DataDependenceGraph::scheduledMoves
NodeSet scheduledMoves() const
Definition: DataDependenceGraph.cc:1375
DataDependenceGraph::lastScheduledRegisterGuardReads
NodeSet lastScheduledRegisterGuardReads(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1163
BoostGraph< MoveNode, DataDependenceEdge >::RemovedEdgeMap
std::set< RemovedEdgeDatum > RemovedEdgeMap
Definition: BoostGraph.hh:236
DataDependenceGraph::createRegisterAntiDependenciesBetweenNodes
void createRegisterAntiDependenciesBetweenNodes(NodeSet &nodes)
Definition: DataDependenceGraph.cc:4381
ProgramOperation
Definition: ProgramOperation.hh:70
DataDependenceGraph::setMachine
void setMachine(const TTAMachine::Machine &machine)
Definition: DataDependenceGraph.cc:3116
MoveNode
Definition: MoveNode.hh:65
DataDependenceGraph::regRawPredecessors
NodeSet regRawPredecessors(const MoveNode &node, int backedges=0) const
Definition: DataDependenceGraph.cc:4310
DataDependenceGraph::findLiveRange
LiveRange * findLiveRange(MoveNode &lrNode, bool writingNode, bool guardUseNode) const
Definition: DataDependenceGraph.cc:4827
DataDependenceGraph::rrCost_
int rrCost_
Definition: DataDependenceGraph.hh:451
DataDependenceGraph::nodesOfMoves_
std::map< const TTAProgram::Move *, MoveNode * > nodesOfMoves_
Definition: DataDependenceGraph.hh:434
DataDependenceGraph::rWarEdgesOut
int rWarEdgesOut(MoveNode &mn)
Definition: DataDependenceGraph.cc:3930
DataDependenceGraph::sanityCheck
void sanityCheck() const
Definition: DataDependenceGraph.cc:1399
DataDependenceGraph::EdgeWeightHeuristics
EdgeWeightHeuristics
Definition: DataDependenceGraph.hh:90
DataDependenceGraph::onlyRegisterRawSource
MoveNode * onlyRegisterRawSource(const MoveNode &mn, int allowGuardEdges=2, int backEdges=0) const
Definition: DataDependenceGraph.cc:4083
DataDependenceEdge.hh
DataDependenceGraph::moveFUDependenciesToTrigger
void moveFUDependenciesToTrigger(MoveNode &trigger)
Definition: DataDependenceGraph.cc:4785
DataDependenceGraph::lastScheduledRegisterKill
MoveNode * lastScheduledRegisterKill(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1285
DataDependenceGraph::guardDefMoves
NodeSet guardDefMoves(const MoveNode &moveNode)
Definition: DataDependenceGraph.cc:743
DataDependenceGraph::EWH_HEURISTIC
@ EWH_HEURISTIC
Weights memory dependencies more, etc.
Definition: DataDependenceGraph.hh:91
DataDependenceGraph::guardRawPredecessors
NodeSet guardRawPredecessors(const MoveNode &node) const
Definition: DataDependenceGraph.cc:4048
ProgramOperationPtr
std::shared_ptr< ProgramOperation > ProgramOperationPtr
Definition: MoveNode.hh:52
DataDependenceGraph::onlyRegisterRawDestinations
NodeSet onlyRegisterRawDestinations(const MoveNode &mn, bool allowGuardEdges=false, bool allowBackEdges=false) const
Definition: DataDependenceGraph.cc:4163
DataDependenceGraph::mergeAndKeepUser
bool mergeAndKeepUser(MoveNode &resultNode, MoveNode &userNode, bool force=false)
Definition: DataDependenceGraph.cc:2079
DataDependenceGraph::setCycleGrouping
virtual void setCycleGrouping(bool flag)
Definition: DataDependenceGraph.cc:1738
DataDependenceGraph::combineNodes
void combineNodes(MoveNode &node1, MoveNode &node2, MoveNode &destination)
Definition: DataDependenceGraph.cc:2782
DataDependenceGraph::regWarSuccessors
NodeSet regWarSuccessors(const MoveNode &node) const
Definition: DataDependenceGraph.cc:4239
DataDependenceGraph::regDepSiblings
NodeSet regDepSiblings(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:5620
DataDependenceGraph::deleteNode
void deleteNode(MoveNode &node)
Definition: DataDependenceGraph.cc:2882
DataDependenceGraph::setNodeBB
void setNodeBB(MoveNode &mn, BasicBlockNode &bblock, DataDependenceGraph *updater)
Definition: DataDependenceGraph.cc:119
DataDependenceGraph::queueRawPredecessors
bool queueRawPredecessors(NodeSet &queue, NodeSet &finalDest, NodeSet &predQueue, NodeSet &predFinalDest, bool guard) const
Definition: DataDependenceGraph.cc:4918
DataDependenceGraph::createSubgraph
DataDependenceGraph * createSubgraph(NodeSet &nodes, bool includeLoops=false)
Definition: DataDependenceGraph.cc:3377
DataDependenceGraph::undo
void undo(UndoData &undoData)
Definition: DataDependenceGraph.cc:5898
DataDependenceGraph::regWawSuccessors
NodeSet regWawSuccessors(const MoveNode &node) const
Definition: DataDependenceGraph.cc:4347
DataDependenceGraph::writeToXMLFile
void writeToXMLFile(std::string fileName) const
Definition: DataDependenceGraph.cc:1747
DataDependenceGraph::programOperations_
POList programOperations_
Definition: DataDependenceGraph.hh:437
DataDependenceGraph::setProgramOperationNodes
virtual void setProgramOperationNodes(bool flag)
Definition: DataDependenceGraph.hh:224
TTAMachine::BaseRegisterFile
Definition: BaseRegisterFile.hh:48
DataDependenceGraph::operationInEdges
EdgeSet operationInEdges(const MoveNode &node) const
Definition: DataDependenceGraph.cc:5913
DataDependenceGraph::dotString
virtual TCEString dotString() const
Dot printing related methods.
Definition: DataDependenceGraph.cc:1562
DataDependenceGraph::procedureDDG_
bool procedureDDG_
Definition: DataDependenceGraph.hh:454
DataDependenceGraph::ALL_ANTIDEPS
@ ALL_ANTIDEPS
Definition: DataDependenceGraph.hh:82
DataDependenceGraph::largestCycle
int largestCycle() const
Definition: DataDependenceGraph.cc:1838
BoostGraph< MoveNode, DataDependenceEdge >::EdgeSet
std::set< DataDependenceEdge *, typename DataDependenceEdge ::Comparator > EdgeSet
Definition: BoostGraph.hh:87
DataDependenceGraph::UndoData::changedDataEdges
std::map< DataDependenceEdge *, TCEString, DataDependenceEdge::Comparator > changedDataEdges
Definition: DataDependenceGraph.hh:75
DataDependenceGraph::hasSingleBBLoopRegisterAntidependencies
bool hasSingleBBLoopRegisterAntidependencies()
Definition: DataDependenceGraph.hh:383
DataDependenceGraph::copyExternalOutEdges
void copyExternalOutEdges(MoveNode &nodeCopy, const MoveNode &source)
Definition: DataDependenceGraph.cc:5346
DataDependenceGraph::INTRA_BB_ANTIDEPS
@ INTRA_BB_ANTIDEPS
Definition: DataDependenceGraph.hh:80
DataDependenceGraph::updateRegUse
void updateRegUse(const MoveNodeUse &mnd, const TCEString &reg, TTAProgram::BasicBlock &bb)
Definition: DataDependenceGraph.cc:5367
DataDependenceGraph::UndoData::removedEdges
RemovedEdgeMap removedEdges
Definition: DataDependenceGraph.hh:73
DataDependenceGraph::DUMP_XML
@ DUMP_XML
Definition: DataDependenceGraph.hh:87
DataDependenceGraph::firstScheduledRegisterRead
MoveNode * firstScheduledRegisterRead(const TTAMachine::BaseRegisterFile &rf, int registerIndex, int firstCycleToTest=0) const
Definition: DataDependenceGraph.cc:808
DataDependenceGraph::nodeOfMove
MoveNode & nodeOfMove(const TTAProgram::Move &move)
Definition: DataDependenceGraph.cc:3600
DataDependenceGraph::machine_
const TTAMachine::Machine * machine_
Definition: DataDependenceGraph.hh:448
DataDependenceGraph::otherSuccessorsScheduled
bool otherSuccessorsScheduled(MoveNode &node, const NodeSet &ignoredNodes) const
Definition: DataDependenceGraph.cc:3266
DataDependenceGraph::removeNode
void removeNode(MoveNode &node)
Definition: DataDependenceGraph.cc:2843
BasicBlockNode
Definition: BasicBlockNode.hh:64
DataDependenceGraph::hasUnscheduledPredecessors
bool hasUnscheduledPredecessors(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:5594
DataDependenceGraph::onlyGuardDefOfMove
MoveNode * onlyGuardDefOfMove(MoveNode &moveNode)
Definition: DataDependenceGraph.cc:4581
POList
std::vector< ProgramOperationPtr > POList
Definition: DataDependenceGraph.hh:48
DataDependenceGraph::hasOtherRegWawSources
bool hasOtherRegWawSources(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:5701
DataDependenceGraph::findLoopIndexUpdate
std::pair< MoveNode *, int > findLoopIndexUpdate(MoveNode *indexMove)
Definition: DataDependenceGraph.cc:4704
DataDependenceGraph::connectOrDeleteEdge
bool connectOrDeleteEdge(const MoveNode &tailNode, const MoveNode &headNode, DataDependenceEdge *edge)
Definition: DataDependenceGraph.cc:3355
DataDependenceGraph::smallestCycle
int smallestCycle() const
Definition: DataDependenceGraph.cc:1818
DataDependenceGraph::copyIncomingGuardEdges
void copyIncomingGuardEdges(const MoveNode &src, MoveNode &dst)
Definition: DataDependenceGraph.cc:3865
DataDependenceGraph::programOperationCount
int programOperationCount() const
Definition: DataDependenceGraph.cc:246
DataDependenceGraph::DUMP_DOT
@ DUMP_DOT
Definition: DataDependenceGraph.hh:86
TTAProgram::Move
Definition: Move.hh:55
DataDependenceGraph::unMergeUser
void unMergeUser(MoveNode &resultNode, MoveNode &mergedNode, bool loopBypass=false)
Definition: DataDependenceGraph.cc:2240
DataDependenceGraph::ownedBBN_
BasicBlockNode * ownedBBN_
Definition: DataDependenceGraph.hh:453
DataDependenceGraph::fixAntidepsAfterLoopUnmergeUser
void fixAntidepsAfterLoopUnmergeUser(MoveNode &sourceNode, MoveNode &mergedNode, const TCEString &reg)
Definition: DataDependenceGraph.cc:2213
DataDependenceGraph::findLimitingAntidependenceDestination
MoveNode * findLimitingAntidependenceDestination(MoveNode &mn)
Definition: DataDependenceGraph.cc:5293
DataDependenceGraph::cycleGrouping_
bool cycleGrouping_
Dot printing related variables. Group the printed MoveNodes according to their cycles.
Definition: DataDependenceGraph.hh:442
DataDependenceGraph::hasEqualEdge
bool hasEqualEdge(const MoveNode &tailNode, const MoveNode &headNode, const DataDependenceEdge &edge) const
Definition: DataDependenceGraph.cc:3324
DataDependenceGraph::onlyIncomingGuard
DataDependenceEdge * onlyIncomingGuard(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:4024
DataDependenceGraph::guardRestored
void guardRestored(MoveNode &guardSrc, MoveNode &dst)
Definition: DataDependenceGraph.cc:5849
TTAProgram::CodeSnippet
Definition: CodeSnippet.hh:59
DataDependenceGraph::isLoopInvariant
bool isLoopInvariant(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:5688
DataDependenceGraph::earliestCycle
int earliestCycle(const MoveNode &moveNode, unsigned int ii=UINT_MAX, bool ignoreRegWaRs=false, bool ignoreRegWaWs=false, bool ignoreGuards=false, bool ignoreFUDeps=false, bool ignoreSameOperationEdges=false, bool assumeBypassing=false) const
Definition: DataDependenceGraph.cc:388
DataDependenceGraph::movesAtCycle
NodeSet movesAtCycle(int cycle) const
Definition: DataDependenceGraph.cc:699
ProgramOperation.hh
DataDependenceGraph::isRootGraphProcedureDDG
bool isRootGraphProcedureDDG()
Definition: DataDependenceGraph.cc:3669
BoostGraph< MoveNode, DataDependenceEdge >::edge
virtual Edge & edge(const int index) const
DataDependenceGraph::lastGuardDefMove
MoveNode * lastGuardDefMove(MoveNode &moveNode)
Definition: DataDependenceGraph.cc:721
DataDependenceGraph::addNode
void addNode(MoveNode &moveNode)
Definition: DataDependenceGraph.cc:144
TTAProgram::BasicBlock
Definition: BasicBlock.hh:85
DataDependenceGraph::lastRegisterCycle
int lastRegisterCycle(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:882
DataDependenceGraph::UndoData
Definition: DataDependenceGraph.hh:71
DataDependenceGraph::trueDependenceGraph
DataDependenceGraph * trueDependenceGraph(bool removeMemAntideps=true, bool ignoreMemDeps=false)
Definition: DataDependenceGraph.cc:3417
DataDependenceGraph::destRenamed
DataDependenceGraph::UndoData destRenamed(MoveNode &mn)
Definition: DataDependenceGraph.cc:5055
DataDependenceGraph::guardConverted
void guardConverted(MoveNode &guardSrc, MoveNode &dst)
Definition: DataDependenceGraph.cc:5795
DataDependenceGraph::DataDependenceGraph
DataDependenceGraph(std::set< TCEString > allParamRegs, const TCEString &name="", AntidependenceLevel antidependenceLevel=ALL_ANTIDEPS, BasicBlockNode *ownedBBN=NULL, bool containsProcedure=false, bool noLoopEdges=false)
Definition: DataDependenceGraph.cc:78
DataDependenceGraph::isNotAvoidable
bool isNotAvoidable(const DataDependenceEdge &edge) const
Definition: DataDependenceGraph.cc:5553
DataDependenceGraph::onlyRegisterEdgeOut
DataDependenceEdge * onlyRegisterEdgeOut(MoveNode &mn) const
Definition: DataDependenceGraph.cc:276
DataDependenceGraph::exclusingGuards
bool exclusingGuards(const MoveNode &mn1, const MoveNode &mn2) const
Definition: DataDependenceGraph.cc:4480
TCEString
Definition: TCEString.hh:53
DataDependenceGraph::guardsAllowBypass
bool guardsAllowBypass(const MoveNode &defNode, const MoveNode &useNode, bool loopBypass=false)
Definition: DataDependenceGraph.cc:4543
DataDependenceGraph::programOperationPtr
ProgramOperationPtr programOperationPtr(int index)
Definition: DataDependenceGraph.cc:237
DataDependenceGraph::firstScheduledRegisterKill
MoveNode * firstScheduledRegisterKill(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1320
DataDependenceGraph
Definition: DataDependenceGraph.hh:67
DataDependenceGraph::dropBackEdges
void dropBackEdges()
Definition: DataDependenceGraph.cc:3620
DataDependenceGraph::copyOutgoingGuardWarEdges
void copyOutgoingGuardWarEdges(const MoveNode &src, MoveNode &dst)
Definition: DataDependenceGraph.cc:3897
DataDependenceGraph::criticalPathGraph
DataDependenceGraph * criticalPathGraph()
Definition: DataDependenceGraph.cc:3458
DataDependenceGraph::memoryDependenceGraph
DataDependenceGraph * memoryDependenceGraph()
Definition: DataDependenceGraph.cc:3482
DataDependenceGraph::firstScheduledRegisterWrites
NodeSet firstScheduledRegisterWrites(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1245
DataDependenceGraph::AntidependenceLevel
AntidependenceLevel
Definition: DataDependenceGraph.hh:78
DataDependenceGraph::EWH_REAL
@ EWH_REAL
Height returns the minimum cycle count for the schedule given enough resources.
Definition: DataDependenceGraph.hh:92
DataDependenceEdge
Definition: DataDependenceEdge.hh:43
BoostGraph
Definition: BoostGraph.hh:83
DataDependenceGraph::operationLatencies_
std::map< TCEString, int > operationLatencies_
Definition: DataDependenceGraph.hh:450
DataDependenceGraph::UndoData::newEdges
EdgeSet newEdges
Definition: DataDependenceGraph.hh:72
DataDependenceGraph::findLoopIndexInit
MoveNode * findLoopIndexInit(MoveNode &updateMove)
Definition: DataDependenceGraph.cc:4755
DataDependenceGraph::removeOutgoingGuardWarEdges
void removeOutgoingGuardWarEdges(MoveNode &node)
Definition: DataDependenceGraph.cc:5496
DataDependenceGraph::DumpFileFormat
DumpFileFormat
Definition: DataDependenceGraph.hh:85
DataDependenceGraph::allParamRegs_
std::set< TCEString > allParamRegs_
Definition: DataDependenceGraph.hh:430
DataDependenceGraph::rAntiEdgesIn
int rAntiEdgesIn(MoveNode &mn)
Definition: DataDependenceGraph.cc:4001
DataDependenceGraph::onlyRegisterEdgeIn
DataDependenceEdge * onlyRegisterEdgeIn(MoveNode &mn) const
Definition: DataDependenceGraph.cc:255
TTAMachine
Definition: Assembler.hh:48
DataDependenceGraph::firstScheduledRegisterReads
NodeSet firstScheduledRegisterReads(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1121
MoveNode.hh
BoostGraph< MoveNode, DataDependenceEdge >::name
virtual const TCEString & name() const
DataDependenceGraph::lastScheduledRegisterReads
NodeSet lastScheduledRegisterReads(const TTAMachine::BaseRegisterFile &rf, int registerIndex) const
Definition: DataDependenceGraph.cc:1080
DataDependenceGraph::copyDepsOver
EdgeSet copyDepsOver(MoveNode &node, bool anti, bool raw)
Definition: DataDependenceGraph.cc:2422
DataDependenceGraph::copyExternalInEdges
void copyExternalInEdges(MoveNode &nodeCopy, const MoveNode &source)
Definition: DataDependenceGraph.cc:5323
DataDependenceGraph::updateRegWrite
DataDependenceGraph::EdgeSet updateRegWrite(const MoveNodeUse &mnd, const TCEString &reg, TTAProgram::BasicBlock &bb)
Definition: DataDependenceGraph.cc:5401
DataDependenceGraph::regRawSuccessorCount
int regRawSuccessorCount(const MoveNode &mn, bool onlyScheduled)
Definition: DataDependenceGraph.cc:3952
DataDependenceGraph::successorsReady
bool successorsReady(MoveNode &node) const
Definition: DataDependenceGraph.cc:3228
DataDependenceGraph::unscheduledMoves
NodeSet unscheduledMoves() const
Definition: DataDependenceGraph.cc:1355
LiveRange
Definition: LiveRange.hh:38
DataDependenceGraph::moveNodeBlocks_
std::map< const MoveNode *, BasicBlockNode * > moveNodeBlocks_
Definition: DataDependenceGraph.hh:438
DataDependenceGraph::copyDependencies
void copyDependencies(const MoveNode &src, MoveNode &dst, bool ignoreSameBBBackedges, bool moveOverLoopEdge=true)
Definition: DataDependenceGraph.cc:3816
DataDependenceGraph::edgeWeightHeuristics_
EdgeWeightHeuristics edgeWeightHeuristics_
The heuristics to use to weight edges in the longest path computation.
Definition: DataDependenceGraph.hh:458
DataDependenceGraph::hasAllRegisterAntidependencies
bool hasAllRegisterAntidependencies()
Definition: DataDependenceGraph.hh:379
DataDependenceGraph::removeRAWEdges
TCEString removeRAWEdges(MoveNode &sourceNode, MoveNode &userNode)
Definition: DataDependenceGraph.cc:1937
DataDependenceGraph::findBypassSource
MoveNode * findBypassSource(const MoveNode &mn)
Definition: DataDependenceGraph.cc:5734
DataDependenceGraph::getBasicBlockNode
const BasicBlockNode & getBasicBlockNode(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:186
DataDependenceGraph::writesJumpGuard
bool writesJumpGuard(const MoveNode &moveNode)
Definition: DataDependenceGraph.cc:4593
DataDependenceGraph::getOperationLatency
int getOperationLatency(const TCEString &name) const
Definition: DataDependenceGraph.cc:3304
DataDependenceGraph::hasRegWaw
bool hasRegWaw(const MoveNodeUse &mnu, std::set< MoveNodeUse > targets) const
Definition: DataDependenceGraph.cc:5518
POLIter
POList::iterator POLIter
Definition: DataDependenceGraph.hh:49
DataDependenceGraph::mergeAndKeepSource
bool mergeAndKeepSource(MoveNode &resultNode, MoveNode &userNode, bool force=false)
Definition: DataDependenceGraph.cc:1962
ControlFlowGraph
Definition: ControlFlowGraph.hh:100
DataDependenceGraph::NO_ANTIDEPS
@ NO_ANTIDEPS
Definition: DataDependenceGraph.hh:79
TTAMachine::Machine
Definition: Machine.hh:73
DataDependenceGraph::sourceRenamed
DataDependenceGraph::UndoData sourceRenamed(MoveNode &mn)
Definition: DataDependenceGraph.cc:4970
DataDependenceGraph::hasUnscheduledSuccessors
bool hasUnscheduledSuccessors(const MoveNode &mn) const
Definition: DataDependenceGraph.cc:5607
DataDependenceGraph::setEdgeWeightHeuristics
void setEdgeWeightHeuristics(EdgeWeightHeuristics ewh)
Definition: DataDependenceGraph.cc:5716
DataDependenceGraph::dropProgramOperation
void dropProgramOperation(ProgramOperationPtr po)
Definition: DataDependenceGraph.cc:361
DataDependenceGraph::hasIntraBBRegisterAntidependencies
bool hasIntraBBRegisterAntidependencies()
Definition: DataDependenceGraph.hh:387
DataDependenceGraph::latestCycle
int latestCycle(const MoveNode &moveNode, unsigned int ii=UINT_MAX, bool ignoreRegAntideps=false, bool ignoreUnscheduledSuccessors=true, bool ignoreGuards=false, bool ignoreFUDeps=false, bool ignoreSameOperationEdges=false) const
Definition: DataDependenceGraph.cc:543
DataDependenceGraph::mergeAndKeepAllowed
bool mergeAndKeepAllowed(MoveNode &sourceNode, MoveNode &userNode)
Definition: DataDependenceGraph.cc:1880