OpenASIP  2.0
Public Types | Public Member Functions | Private Types | Private Member Functions | Private Attributes | List of all members
MachineInstrDDG Class Reference

#include <MachineInstrDDG.hh>

Inheritance diagram for MachineInstrDDG:
Inheritance graph
Collaboration diagram for MachineInstrDDG:
Collaboration graph

Public Types

typedef unsigned Register
 
typedef std::set< RegisterRegisterSet
 
- Public Types inherited from BoostGraph< MIDDGNode, MIDDGEdge >
typedef std::set< MIDDGNode *, typename MIDDGNode ::Comparator > NodeSet
 
typedef std::set< MIDDGEdge *, typename MIDDGEdge ::Comparator > EdgeSet
 
typedef MIDDGNode Node
 The (base) node type managed by this graph. More...
 
typedef MIDDGEdge Edge
 The (base) edge type managed by this graph. More...
 
- Public Types inherited from GraphBase< MIDDGNode, MIDDGEdge >
typedef std::set< MIDDGNode *, typename MIDDGNode ::Comparator > NodeSet
 
typedef std::set< MIDDGEdge *, typename MIDDGEdge ::Comparator > EdgeSet
 
typedef MIDDGNode Node
 Node type of this graph (possibly, a base class). More...
 
typedef MIDDGEdge Edge
 Edge type of this graph (possibly, a base class). More...
 

Public Member Functions

 MachineInstrDDG (const MachineInstrDDG &parent)
 
 MachineInstrDDG (llvm::MachineFunction &mf, bool onlyTrueDeps=true)
 
virtual ~MachineInstrDDG ()
 
RegisterSet allRegisters () const
 
MIDDGNodevregDefiner (Register vreg) const
 
MIDDGNodelastVregUser (Register vreg) const
 
int falseDepHeightDelta (Register vreg, Register physReg) const
 
void assignPhysReg (Register vreg, Register physReg)
 
bool preceedingNodeUsesOrDefinesReg (const MIDDGNode &node, Register physReg) const
 
void computeOptimalSchedule ()
 
TCEString dotString () const
 
void setPrintOnlyCriticalPath (bool flag)
 
- Public Member Functions inherited from BoostGraph< MIDDGNode, MIDDGEdge >
 BoostGraph (bool allowLoopEdges=true)
 
 BoostGraph (const TCEString &name, bool allowLoopEdges=true)
 
 BoostGraph (const BoostGraph &other, bool allowLoopEdges=true)
 
 ~BoostGraph ()
 
int nodeCount () const
 
int edgeCount () const
 
Nodenode (const int index) const
 
Nodenode (const int index, bool cacheResult) const
 
virtual Edgeedge (const int index) const
 
virtual void addNode (Node &node)
 
virtual EdgeoutEdge (const Node &node, const int index) const
 
virtual EdgeinEdge (const Node &node, const int index) const
 
virtual EdgeSet outEdges (const Node &node) const
 
virtual EdgeSet inEdges (const Node &node) const
 
virtual EdgeSet rootGraphOutEdges (const Node &node) const
 
virtual EdgeSet rootGraphInEdges (const Node &node) const
 
virtual EdgerootGraphInEdge (const Node &node, const int index) const
 
virtual EdgerootGraphOutEdge (const Node &node, const int index) const
 
virtual int rootGraphInDegree (const Node &node) const
 
virtual int rootGraphOutDegree (const Node &node) const
 
virtual int outDegree (const Node &node) const
 
virtual int inDegree (const Node &node) const
 
virtual NodetailNode (const Edge &edge) const
 
virtual NodeheadNode (const Edge &edge) const
 
virtual void connectNodes (const Node &nTail, const Node &nHead, Edge &e)
 
virtual void disconnectNodes (const Node &nTail, const Node &nHead)
 
virtual void moveInEdges (const Node &source, const Node &destination)
 
virtual void moveOutEdges (const Node &source, const Node &destination)
 
virtual void moveInEdge (const Node &source, const Node &destination, Edge &edge, const Node *tail=NULL, bool childs=false)
 
virtual void moveOutEdge (const Node &source, const Node &destination, Edge &edge, const Node *head=NULL, bool childs=false)
 
virtual void copyInEdge (const Node &destination, Edge &edge, const Node *tail=NULL)
 
virtual void copyOutEdge (const Node &destination, Edge &edge, const Node *head=NULL)
 
virtual void removeNode (Node &node)
 
virtual void removeEdge (Edge &e)
 
virtual void dropNode (Node &node)
 
virtual void dropEdge (Edge &edge)
 
virtual bool hasEdge (const Node &nTail, const Node &nHead) const
 
virtual NodeSet rootNodes () const
 useful utility functions More...
 
virtual NodeSet sinkNodes () const
 
virtual NodeSet successors (const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
 
virtual NodeSet predecessors (const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
 
int maxPathLength (const MIDDGNode &node) const
 
int maxSinkDistance (const MIDDGNode &node) const
 
int maxSourceDistance (const MIDDGNode &node) const
 
bool isInCriticalPath (const MIDDGNode &node) const
 
int height () const
 
void findAllPaths () const
 
void detachSubgraph (BoostGraph &subGraph)
 
BoostGraphparentGraph ()
 
BoostGraphrootGraph ()
 
const BoostGraphrootGraph () const
 
bool hasNode (const Node &) const
 
virtual const TCEStringname () const
 
void setName (const TCEString &newName)
 
bool hasPath (MIDDGNode &src, const MIDDGNode &dest) const
 
void restoreNodeFromParent (MIDDGNode &node)
 
bool detectIllegalCycles () const
 
EdgeSet connectingEdges (const Node &nTail, const Node &nHead) const
 
- Public Member Functions inherited from GraphBase< MIDDGNode, MIDDGEdge >
 GraphBase ()
 
virtual ~GraphBase ()
 
virtual TCEString dotString () const
 
virtual void writeToDotFile (const TCEString &fileName) const
 

Private Types

typedef std::map< Register, MIDDGNode * > DefinerMap
 
typedef std::map< Register, NodeSetUserMap
 
typedef std::map< Register, RegisterRegisterMap
 

Private Member Functions

std::pair< MIDDGNode *, MIDDGNode * > createFalseDepEdge (Register vreg, Register physReg) const
 

Private Attributes

RegisterSet allRegisters_
 
DefinerMap definers_
 
UserMap users_
 
NodeSet nodes_
 
std::set< MIDDGEdge * > edges_
 
std::map< Register, MIDDGNode * > lastPhysRegUsers_
 
std::map< Register, MIDDGNode * > lastPhysRegDefiners_
 
RegisterMap regAssignments_
 
const bool onlyTrueDeps_
 
int smallestCycle_
 
int largestCycle_
 
std::map< int, std::list< MIDDGNode * > > schedule_
 
llvm::MachineFunction & mf_
 
const llvm::TargetRegisterInfo * regInfo_
 
bool printOnlyCriticalPath_
 

Additional Inherited Members

- Protected Types inherited from BoostGraph< MIDDGNode, MIDDGEdge >
typedef std::set< RemovedEdgeDatum > RemovedEdgeMap
 
typedef boost::adjacency_list< boost::listS, boost::vecS, boost::bidirectionalS, Node *, Edge * > Graph
 Internal graph type, providing actual graph-like operations. This type definition relies on bundled properties of boost library, which need the host compiler to support partial template specialisation. More...
 
typedef boost::graph_traits< GraphGraphTraits
 Traits characterising the internal graph type. More...
 
typedef GraphTraits::out_edge_iterator OutEdgeIter
 Output edge iterator type. More...
 
typedef GraphTraits::in_edge_iterator InEdgeIter
 Input edge iterator type. More...
 
typedef GraphTraits::edge_iterator EdgeIter
 Iterator type for the list of all edges in the graph. More...
 
typedef GraphTraits::vertex_iterator NodeIter
 Iterator type for the list of all nodes in the graph. More...
 
typedef GraphTraits::edge_descriptor EdgeDescriptor
 Type with which edges of the graph are seen internally. More...
 
typedef GraphTraits::vertex_descriptor NodeDescriptor
 Type with which nodes of the graph are seen internally. More...
 
typedef hash_map< const Edge *, EdgeDescriptor, GraphHashFunctions > EdgeDescMap
 
typedef hash_map< const Node *, NodeDescriptor, GraphHashFunctions > NodeDescMap
 
typedef std::vector< std::vector< int > > PathCache
 
- Protected Member Functions inherited from BoostGraph< MIDDGNode, MIDDGEdge >
NodetailNode (const Edge &edge, const NodeDescriptor &headNode) const
 
NodeheadNode (const Edge &edge, const NodeDescriptor &tailNode) const
 
virtual void connectNodes (const Node &nTail, const Node &nHead, Edge &e, GraphBase< MIDDGNode, MIDDGEdge > *modifier, bool creatingSG=false)
 
void moveInEdges (const Node &source, const Node &destination, BoostGraph *modifierGraph)
 
virtual void moveOutEdges (const Node &source, const Node &destination, BoostGraph *modifierGraph)
 
virtual void removeNode (Node &node, BoostGraph *modifierGraph)
 
virtual void removeEdge (Edge &e, const MIDDGNode *tailNode, const MIDDGNode *headNode, BoostGraph *modifierGraph=NULL)
 
bool hasEdge (const Node &nTail, const Node &nHead, const Edge &edge) const
 
bool hasEdge (const Edge &edge, const Node *nTail=NULL, const Node *nHead=NULL) const
 
void restoreRemovedEdges (RemovedEdgeMap removedEdges)
 
EdgeDescriptor descriptor (const Edge &e) const
 
NodeDescriptor descriptor (const Node &n) const
 
EdgeDescriptor edgeDescriptor (const NodeDescriptor &tailNode, const Edge &e) const
 
EdgeDescriptor edgeDescriptor (const Edge &e, const NodeDescriptor &headNode) const
 
EdgeDescriptor connectingEdge (const Node &nTail, const Node &nHead) const
 
void replaceNodeWithLastNode (MIDDGNode &dest)
 
void calculatePathLengths () const
 
void calculatePathLengthsFast () const
 
void calculateSinkDistance (const MIDDGNode &node, int len, bool looping=false) const
 
void calculateSourceDistances (const MIDDGNode *startNode=NULL, int startingLength=0, bool looping=false) const
 
void calculatePathLengthsOnConnect (const MIDDGNode &nTail, const MIDDGNode &nHead, MIDDGEdge &e)
 
void sinkDistDecreased (const MIDDGNode &n) const
 
void sourceDistDecreased (const MIDDGNode &n) const
 
virtual int edgeWeight (MIDDGEdge &e, const MIDDGNode &n) const
 
void clearDescriptorCache (EdgeSet edges)
 
void constructSubGraph (BoostGraph &subGraph, NodeSet &nodes)
 
- Protected Attributes inherited from BoostGraph< MIDDGNode, MIDDGEdge >
std::map< const MIDDGNode *, int, typename MIDDGNode ::Comparator > sourceDistances_
 
std::map< const MIDDGNode *, int, typename MIDDGNode ::Comparator > sinkDistances_
 
std::map< const MIDDGNode *, int, typename MIDDGNode ::Comparator > loopingSourceDistances_
 
std::map< const MIDDGNode *, int, typename MIDDGNode ::Comparator > loopingSinkDistances_
 
int height_
 
Graph graph_
 The internal graph structure. More...
 
EdgeDescMap edgeDescriptors_
 
NodeDescMap nodeDescriptors_
 
BoostGraph< MIDDGNode, MIDDGEdge > * parentGraph_
 
std::vector< BoostGraph< MIDDGNode, MIDDGEdge > * > childGraphs_
 
TCEString name_
 
int sgCounter_
 
std::set< Edge * > ownedEdges_
 
bool allowLoopEdges_
 
PathCachepathCache_
 

Detailed Description

Data Dependence Graph constructed from non-register allocated LLVM MachineInstructions.

Only true dependencies supported at the moment. Later we can might add support for adding the false dependencies introduced by the register allocator, if needed.

Definition at line 140 of file MachineInstrDDG.hh.

Member Typedef Documentation

◆ DefinerMap

typedef std::map<Register, MIDDGNode*> MachineInstrDDG::DefinerMap
private

Definition at line 173 of file MachineInstrDDG.hh.

◆ Register

typedef unsigned MachineInstrDDG::Register

Definition at line 143 of file MachineInstrDDG.hh.

◆ RegisterMap

typedef std::map<Register, Register> MachineInstrDDG::RegisterMap
private

Definition at line 175 of file MachineInstrDDG.hh.

◆ RegisterSet

Definition at line 144 of file MachineInstrDDG.hh.

◆ UserMap

typedef std::map<Register, NodeSet> MachineInstrDDG::UserMap
private

Definition at line 174 of file MachineInstrDDG.hh.

Constructor & Destructor Documentation

◆ MachineInstrDDG() [1/2]

MachineInstrDDG::MachineInstrDDG ( const MachineInstrDDG parent)
explicit

Constructor for creating a subgraph.

Definition at line 181 of file MachineInstrDDG.cc.

181  :
183  std::string(parent.name(), true)),
184  onlyTrueDeps_(parent.onlyTrueDeps_), mf_(parent.mf_) {
185 }

◆ MachineInstrDDG() [2/2]

POP_COMPILER_DIAGS MachineInstrDDG::MachineInstrDDG ( llvm::MachineFunction &  mf,
bool  onlyTrueDeps = true 
)

Constructs a DDG out of MachineInstructions.

Only true dependencies are supported at the moment.

Definition at line 66 of file MachineInstrDDG.cc.

68  :
70  std::string(mf.getFunction().getName().str()) + "_middg", true),
71  onlyTrueDeps_(onlyTrueDeps), mf_(mf),
72  regInfo_(mf_.getTarget().getSubtargetImpl(
73  mf_.getFunction())->getRegisterInfo())
74  , printOnlyCriticalPath_(false) {
75  int instructions = 0;
76  for (llvm::MachineFunction::const_iterator bbi = mf.begin();
77  bbi != mf.end(); ++bbi) {
78  const llvm::MachineBasicBlock& bb = *bbi;
79  for (llvm::MachineBasicBlock::const_iterator ii = bb.begin();
80  ii != bb.end(); ++ii) {
81  const llvm::MachineInstr& i = *ii;
82  MIDDGNode* node = new MIDDGNode(i, instructions);
83  nodes_.insert(node);
84  addNode(*node);
85  assert(hasNode(*node));
86  ++instructions;
87  for (unsigned oi = 0; oi < i.getNumOperands(); ++oi) {
88  const llvm::MachineOperand& operand = i.getOperand(oi);
89  if (!operand.isReg())
90  continue;
91 
92  if (operand.isUndef()) {
93  // this is probably a global register defined in some other
94  // function, thus it can be ignored (only reads from it in this func)
95  continue;
96  }
97  if (operand.isImplicit()) {
98  // the call clobbered regs
99  continue;
100  }
101 
102  if (llvm::Register::isPhysicalRegister(
103  operand.getReg())) {
104 
105  // only physical reg at this point should be the stack pointer,
106  // which is a global reg we can ignore
107 #ifdef DEBUG_MI_DDG
109  << "found a phys reg " << operand.getReg()
110  << std::endl;
111  if (operand.getType() == llvm::MachineOperand::MO_FrameIndex)
112  Application::logStream() << "SP";
113 #endif
114  continue;
115  }
116 
117  if (operand.isUse()) {
118  users_[operand.getReg()].insert(node);
119 #ifdef DEBUG_MI_DDG
121  << "uses: " << operand.getReg() << std::endl;
122 #endif
123  } else if (operand.isDef()) {
124  if (definers_[operand.getReg()] != NULL) {
125  // in case we already have a definer, use the
126  // one from the different basic block to avoid loops
127  if (definers_[operand.getReg()]->machineInstr()->
128  getParent() != &bb) {
129 #ifdef DEBUG_MI_DDG
131  << "found a potential back edge case, "
132  << "using the definer from another BB"
133  << std::endl;
134 #endif
135  continue;
136  }
137  } else {
138  definers_[operand.getReg()] = node;
139  }
140  } else {
141 #ifdef DEBUG_MI_DDG
143  << "unknown operand " << oi << std::endl;
144 #endif
145  continue;
146  }
147  allRegisters_.insert(operand.getReg());
148  }
149  }
150  }
151 
152 
153  for (DefinerMap::iterator i = definers_.begin(); i != definers_.end();
154  ++i) {
155  Register reg = (*i).first;
156  MIDDGNode* source = (*i).second;
157  NodeSet& users = users_[reg];
158  for (std::set<MIDDGNode*>::iterator u = users.begin(); u != users.end();
159  ++u) {
160  MIDDGNode* dest = *u;
161 
162  if (hasPath(*dest, *source)) {
163 #ifdef DEBUG_MI_DDG
165  << "ignoring edge that would create a loop"
166  << std::endl;
167 #endif
168  continue;
169  }
170 
171  MIDDGEdge* edge = new MIDDGEdge(reg);
172  edges_.insert(edge);
173  connectNodes(*source, *dest, *edge);
174  }
175  }
176 }

References BoostGraph< MIDDGNode, MIDDGEdge >::addNode(), allRegisters_, assert, BoostGraph< MIDDGNode, MIDDGEdge >::connectNodes(), definers_, BoostGraph< MIDDGNode, MIDDGEdge >::edge(), edges_, BoostGraph< MIDDGNode, MIDDGEdge >::hasNode(), BoostGraph< MIDDGNode, MIDDGEdge >::hasPath(), Application::logStream(), BoostGraph< MIDDGNode, MIDDGEdge >::node(), nodes_, and users_.

Here is the call graph for this function:

◆ ~MachineInstrDDG()

MachineInstrDDG::~MachineInstrDDG ( )
virtual

Definition at line 188 of file MachineInstrDDG.cc.

188  {
189 }

Member Function Documentation

◆ allRegisters()

RegisterSet MachineInstrDDG::allRegisters ( ) const
inline

Definition at line 154 of file MachineInstrDDG.hh.

154 { return allRegisters_; }

References allRegisters_.

Referenced by VirtRegIndependenceGraph::VirtRegIndependenceGraph().

◆ assignPhysReg()

void MachineInstrDDG::assignPhysReg ( Register  vreg,
Register  physReg 
)

Assigns the given physical register to the given virtual register.

Does not yet add false dependence edges, just updates the last phys reg use bookkeeping.

Definition at line 506 of file MachineInstrDDG.cc.

506  {
507 
508  regAssignments_[vreg] = physReg;
509 
510  MIDDGNode* lastDefiner = vregDefiner(vreg);
511 
512  if (lastPhysRegDefiners_.find(physReg) != lastPhysRegDefiners_.end()) {
513  MIDDGNode* previousDefiner = lastPhysRegDefiners_[physReg];
514  if (lastDefiner == NULL ||
515  previousDefiner->sequentialAddress() >
516  lastDefiner->sequentialAddress()) {
517  lastDefiner = previousDefiner;
518  }
519  }
520  if (lastDefiner != NULL) {
521  lastPhysRegDefiners_[physReg] = lastDefiner;
522  }
523 
524  MIDDGNode* lastUser = NULL;
525  if (lastPhysRegUsers_.find(physReg) != lastPhysRegUsers_.end()) {
526  lastUser = lastPhysRegUsers_[physReg];
527  }
528 
529  MIDDGNode* lastVregUser = this->lastVregUser(vreg);
530  if (lastVregUser != NULL) {
531  if (lastUser == NULL ||
533  lastUser->sequentialAddress()) {
534  lastUser = lastVregUser;
535  }
536  }
537  if (lastUser != NULL) {
538  lastPhysRegUsers_[physReg] = lastUser;
539  }
540 
541  std::pair<MIDDGNode*, MIDDGNode*> fdep =
542  createFalseDepEdge(vreg, physReg);
543 
544  if (fdep.first != NULL && fdep.second != NULL &&
545  fdep.first != fdep.second) {
546  MIDDGEdge* edge = new MIDDGEdge(physReg, MIDDGEdge::DEP_WAR);
547  edges_.insert(edge);
548 #if 0
550  << "adding edge: " << edge->toString() << " from "
551  << fdep.first->sequentialAddress() << " to "
552  << fdep.second->sequentialAddress() << std::endl;
553 #endif
554  connectNodes(*fdep.first, *fdep.second, *edge);
555  }
556 }

References BoostGraph< MIDDGNode, MIDDGEdge >::connectNodes(), createFalseDepEdge(), MIDDGEdge::DEP_WAR, BoostGraph< MIDDGNode, MIDDGEdge >::edge(), edges_, lastPhysRegDefiners_, lastPhysRegUsers_, lastVregUser(), Application::logStream(), regAssignments_, MIDDGNode::sequentialAddress(), MIDDGEdge::toString(), and vregDefiner().

Here is the call graph for this function:

◆ computeOptimalSchedule()

void MachineInstrDDG::computeOptimalSchedule ( )

Computes optimal top-down schedule assuming infinite resources and that each operation completes in one cycle.

Definition at line 356 of file MachineInstrDDG.cc.

356  {
357  smallestCycle_ = 0;
358  largestCycle_ = 0;
359  schedule_.clear();
360  for (int nc = 0; nc < nodeCount(); ++nc) {
361  MIDDGNode& n = node(nc);
362  int cycle = maxSourceDistance(n);
363  n.setOptimalCycle(cycle);
364  largestCycle_ = std::max(cycle, largestCycle_);
365  schedule_[cycle].push_back(&n);
366  }
367 }

References largestCycle_, BoostGraph< MIDDGNode, MIDDGEdge >::maxSourceDistance(), BoostGraph< MIDDGNode, MIDDGEdge >::node(), BoostGraph< MIDDGNode, MIDDGEdge >::nodeCount(), schedule_, MIDDGNode::setOptimalCycle(), and smallestCycle_.

Referenced by InstructionPatternAnalyzer::runOnMachineFunction().

Here is the call graph for this function:

◆ createFalseDepEdge()

std::pair< MIDDGNode *, MIDDGNode * > MachineInstrDDG::createFalseDepEdge ( Register  vreg,
Register  physReg 
) const
private

Creates a false dependency edge introduced when the given virtual reg is assigned the given physical register.

Does not add the edge to the graph. Note, only creates a single edge although in a multi-BB DDG there is usually many in case edge spans CFG branch points. Returns a pair with NULLs in case no false dep is introduced.

Definition at line 202 of file MachineInstrDDG.cc.

202  {
203 
204  MIDDGNode* null = NULL;
205  std::pair<MIDDGNode*, MIDDGNode*> none = std::make_pair(null, null);
206 
207 
208  if (lastPhysRegUsers_.find(physReg) == lastPhysRegUsers_.end()) {
209  return none;
210  }
211 
212  MIDDGNode* lastPhysRegUser = (*lastPhysRegUsers_.find(physReg)).second;
213 
214  if (this->vregDefiner(vreg) == NULL) {
215  // could not find a definer for the given vreg, thus probably
216  // a global register such as stack pointer, there won't be
217  // many assignment possibilities for them anyways
218  return none;
219  }
220  MIDDGNode* vregDefiner = this->vregDefiner(vreg);
221  MIDDGNode* lastVregUser = this->lastVregUser(vreg);
222 
223  MIDDGNode* lastPhysRegDefiner = NULL;
224  if (lastPhysRegDefiners_.find(physReg) != lastPhysRegDefiners_.end()) {
225  lastPhysRegDefiner = (*lastPhysRegDefiners_.find(physReg)).second;
226  }
227 
228  assert(vregDefiner != NULL);
229 
230  // the source and destination nodes for the introduced antidep
231  MIDDGNode* source = NULL;
232  MIDDGNode* dest = NULL;
233 
234  // the sequential instruction ordering defines the dep direction
236  lastPhysRegUser->sequentialAddress()) {
237  source = lastPhysRegUser;
238  dest = vregDefiner;
239  } else {
240  if (lastVregUser == NULL) {
241  // only writes to the vreg, thus it would be WaW
242  source = vregDefiner;
243  } else {
244  source = lastVregUser;
245  }
246 
247  if (lastPhysRegDefiner != NULL) {
248  dest = lastPhysRegDefiner;
249  } else {
250  dest = lastPhysRegUser;
251  }
252  }
253 
254  // ignore loop edges for now, but signal edges to itself as they are
255  // cheap false deps which should be treated as such
256  if (dest != source && hasPath(*dest, *source))
257  return none;
258 
259  return std::make_pair(source, dest);
260 }

References assert, BoostGraph< MIDDGNode, MIDDGEdge >::hasPath(), lastPhysRegDefiners_, lastPhysRegUsers_, lastVregUser(), MIDDGNode::sequentialAddress(), and vregDefiner().

Referenced by assignPhysReg(), and falseDepHeightDelta().

Here is the call graph for this function:

◆ dotString()

TCEString MachineInstrDDG::dotString ( ) const

Definition at line 370 of file MachineInstrDDG.cc.

370  {
371  std::ostringstream s;
372  s << "digraph " << name() << " {" << std::endl;
373 
374  const bool scheduled = nodeCount() > 1 && node(0).optimalCycle() != -1;
375 
376  if (scheduled) {
377  // print the "time line" to visualize the schedule
378  s << "\t{" << std::endl
379  << "\t\tnode [shape=plaintext];" << std::endl
380  << "\t\t";
381  const int smallest = smallestCycle_;
382  const int largest = largestCycle_;
383  for (int c = smallest; c <= largest; ++c) {
384  s << "\"cycle " << c << "\" -> ";
385  }
386  s << "\"cycle " << largest + 1 << "\"; "
387  << std::endl << "\t}" << std::endl;
388 
389  // print the nodes that have cycles
390  for (int c = smallest; c <= largest; ++c) {
391  std::list<MIDDGNode*> ops = schedule_[c];
392  if (ops.size() > 0) {
393  s << "\t{ rank = same; \"cycle " << c << "\"; ";
394  for (std::list<MIDDGNode*>::iterator i = ops.begin();
395  i != ops.end(); ++i) {
396  MIDDGNode& n = **i;
397  if (n.osalOperationName() == "llvm::DBG_VALUE")
398  continue;
400  continue;
401  s << "n" << n.nodeID() << "; ";
402  }
403  s << "}" << std::endl;
404  }
405  }
406 
407 
408  typedef std::map<TCEString, int> OpCountMap;
409  // Count how many times each operation could be potentially
410  // executed in parallel in an optimal schedule. This can direct
411  // the intial architecture design.
412  OpCountMap maxParallelOps;
413  // The operation mix. I.e., the static occurence of operations
414  // in the code.
415  OpCountMap operationMix;
416 
417  for (int c = smallest; c <= largest; ++c) {
418  std::list<MIDDGNode*> ops = schedule_[c];
419  if (ops.size() == 0) continue;
420 
421  std::map<TCEString, int> parallelOpsAtCycle;
422  for (std::list<MIDDGNode*>::iterator i = ops.begin();
423  i != ops.end(); ++i) {
424  MIDDGNode& n = **i;
425  TCEString opName = n.osalOperationName();
426  if (opName == "" || opName == "?jump") continue;
427  operationMix[opName]++;
428  parallelOpsAtCycle[opName]++;
429  }
430 
431  for (OpCountMap::const_iterator i = parallelOpsAtCycle.begin();
432  i != parallelOpsAtCycle.end(); ++i) {
433  TCEString opName = (*i).first;
434  int count = (*i).second;
435  maxParallelOps[opName] =
436  std::max(maxParallelOps[opName], count);
437  }
438  }
439 
440  const int COL_WIDTH = 14;
441  // print statistics of the graph as a comment
442  s << "/* statistics: " << std::endl << std::endl;
443  s << std::setw(COL_WIDTH) << std::right << "virtual regs: ";
444  s << definers_.size() << std::endl << std::endl;
445  s << std::setw(COL_WIDTH) << std::right << "operation stats: ";
446  s << std::endl << std::endl;
447 
448  for (OpCountMap::const_iterator i = maxParallelOps.begin();
449  i != maxParallelOps.end(); ++i) {
450  TCEString opName = (*i).first;
451  int parCount = (*i).second;
452  int total = operationMix[opName];
453  s << std::setw(COL_WIDTH) << std::right << opName + ": ";
454  s << std::setw(COL_WIDTH) << std::right << total;
455  s << " total, " << std::setw(COL_WIDTH) << std::right
456  << parCount << " at most in parallel" << std::endl;
457  }
458  s << "*/" << std::endl;
459  }
460  // first print all the nodes and their properties
461  for (int i = 0; i < nodeCount(); ++i) {
462  Node& n = node(i);
463  if (n.osalOperationName() == "llvm::DBG_VALUE")
464  continue;
466  continue;
467 
468  s << "\tn" << n.nodeID()
469  << " [" << n.dotString();
470  if (isInCriticalPath(n))
471  s << ",shape=box,color=\"red\"";
472  s << "]; " << std::endl;
473  }
474 
475  // edges
476  for (int count = edgeCount(), i = 0; i < count ; ++i) {
477  Edge& e = edge(i);
478  Node& tail = tailNode(e);
479  Node& head = headNode(e);
480 
482  !isInCriticalPath(head))
483  continue;
484 
485  s << "\tn" << tail.nodeID() << " -> n"
486  << head.nodeID() << "["
487  << e.dotString();
488  if (isInCriticalPath(tail) && isInCriticalPath(head))
489  s << ",color=red";
490  s << "];" << std::endl;
491  }
492 
493  s << "}" << std::endl;
494 
495  return s.str();
496 
497 }

References definers_, MIDDGNode::dotString(), MIDDGEdge::dotString(), BoostGraph< MIDDGNode, MIDDGEdge >::edge(), BoostGraph< MIDDGNode, MIDDGEdge >::edgeCount(), BoostGraph< MIDDGNode, MIDDGEdge >::headNode(), BoostGraph< MIDDGNode, MIDDGEdge >::isInCriticalPath(), largestCycle_, BoostGraph< MIDDGNode, MIDDGEdge >::name(), BoostGraph< MIDDGNode, MIDDGEdge >::node(), BoostGraph< MIDDGNode, MIDDGEdge >::nodeCount(), GraphNode::nodeID(), MIDDGNode::optimalCycle(), MIDDGNode::osalOperationName(), printOnlyCriticalPath_, schedule_, smallestCycle_, and BoostGraph< MIDDGNode, MIDDGEdge >::tailNode().

Here is the call graph for this function:

◆ falseDepHeightDelta()

int MachineInstrDDG::falseDepHeightDelta ( Register  vreg,
Register  physReg 
) const

Returns the "height delta" of an antidep edge created in case the given virtual register is assigned the given physical register.

Height delta is the difference between the DDG height of the source definer node and the DDG height of the latest read node of the physReg. The direction of the introduced false dep edge is determined from the sequential instruction order, direction is assumed to be from the earlier instruction to the later. Thus, an edge with 0 or greater height dep potentially constraints the schedule by potentially heightening the DDG. However, this is not generally the case in case the critical path length is not increased by the assignment.

Parameters
vregThe virtual register to test.
physRegThe physical register assigment to test.
Returns
The height delta of the false dep from the assignment, or INT_MIN in case no false dep would be produced.

Definition at line 281 of file MachineInstrDDG.cc.

281  {
282 
283  std::pair<MIDDGNode*, MIDDGNode*> fdep =
284  createFalseDepEdge(vreg, physReg);
285 
286  int hdelta = INT_MIN;
287  if (fdep.first != NULL && fdep.second != NULL) {
288  if (fdep.first == fdep.second)
289  return -1; // treat fdep to itself as the least harmful one
290  hdelta =
291  maxSourceDistance(*fdep.first) - maxSourceDistance(*fdep.second);
292  }
293  return hdelta;
294 }

References createFalseDepEdge(), and BoostGraph< MIDDGNode, MIDDGEdge >::maxSourceDistance().

Here is the call graph for this function:

◆ lastVregUser()

MIDDGNode * MachineInstrDDG::lastVregUser ( Register  vreg) const

Definition at line 297 of file MachineInstrDDG.cc.

297  {
298  int lastUse = -1;
299  MIDDGNode* lastUser = NULL;
300  if (users_.find(vreg) == users_.end())
301  return NULL;
302 
303  NodeSet& users = (*users_.find(vreg)).second;
304  for (NodeSet::const_iterator i = users.begin(); i != users.end();
305  ++i) {
306  MIDDGNode* node = *i;
307  if (lastUse < node->sequentialAddress()) {
308  lastUse = node->sequentialAddress();
309  lastUser = node;
310  }
311  }
312  return lastUser;
313 }

References BoostGraph< MIDDGNode, MIDDGEdge >::node(), MIDDGNode::sequentialAddress(), and users_.

Referenced by assignPhysReg(), and createFalseDepEdge().

Here is the call graph for this function:

◆ preceedingNodeUsesOrDefinesReg()

bool MachineInstrDDG::preceedingNodeUsesOrDefinesReg ( const MIDDGNode node,
Register  physReg 
) const

Checks if there is at least one preceeding node to the given node that defines or uses the given physical register.

Also the uses in the same node are considered.

Definition at line 322 of file MachineInstrDDG.cc.

323  {
324 
325  NodeSet pred = predecessors(node);
326  pred.insert(const_cast<MIDDGNode*>(&node));
327  for (NodeSet::const_iterator i = pred.begin(); i != pred.end(); ++i) {
328  MIDDGNode& p = (**i);
329  const llvm::MachineInstr* instr = p.machineInstr();
330  for (unsigned operand = 0; operand < instr->getNumOperands();
331  ++operand) {
332  const llvm::MachineOperand& mo = instr->getOperand(operand);
333  if (!mo.isReg())
334  continue;
335  if (mo.getReg() == physReg ||
336  (regAssignments_.find(mo.getReg()) != regAssignments_.end() &&
337  (*regAssignments_.find(mo.getReg())).second == physReg)) {
338  return true;
339  }
340  }
341 
342  if (instr->readsRegister(physReg) ||
343  instr->modifiesRegister(physReg, regInfo_)) {
344  return true;
345  }
346  }
347  return false;
348 }

References MIDDGNode::machineInstr(), BoostGraph< MIDDGNode, MIDDGEdge >::node(), BoostGraph< MIDDGNode, MIDDGEdge >::predecessors(), regAssignments_, and regInfo_.

Here is the call graph for this function:

◆ setPrintOnlyCriticalPath()

void MachineInstrDDG::setPrintOnlyCriticalPath ( bool  flag)
inline

Definition at line 170 of file MachineInstrDDG.hh.

170 { printOnlyCriticalPath_ = flag; }

References printOnlyCriticalPath_.

Referenced by InstructionPatternAnalyzer::runOnMachineFunction().

◆ vregDefiner()

MIDDGNode* MachineInstrDDG::vregDefiner ( Register  vreg) const
inline

Definition at line 156 of file MachineInstrDDG.hh.

156 { return definers_[vreg]; };

References definers_.

Referenced by assignPhysReg(), createFalseDepEdge(), and VirtRegIndependenceGraph::VirtRegIndependenceGraph().

Member Data Documentation

◆ allRegisters_

RegisterSet MachineInstrDDG::allRegisters_
private

Definition at line 181 of file MachineInstrDDG.hh.

Referenced by allRegisters(), and MachineInstrDDG().

◆ definers_

DefinerMap MachineInstrDDG::definers_
mutableprivate

Definition at line 183 of file MachineInstrDDG.hh.

Referenced by dotString(), MachineInstrDDG(), and vregDefiner().

◆ edges_

std::set<MIDDGEdge*> MachineInstrDDG::edges_
private

Definition at line 187 of file MachineInstrDDG.hh.

Referenced by assignPhysReg(), and MachineInstrDDG().

◆ largestCycle_

int MachineInstrDDG::largestCycle_
private

Definition at line 197 of file MachineInstrDDG.hh.

Referenced by computeOptimalSchedule(), and dotString().

◆ lastPhysRegDefiners_

std::map<Register, MIDDGNode*> MachineInstrDDG::lastPhysRegDefiners_
private

Definition at line 189 of file MachineInstrDDG.hh.

Referenced by assignPhysReg(), and createFalseDepEdge().

◆ lastPhysRegUsers_

std::map<Register, MIDDGNode*> MachineInstrDDG::lastPhysRegUsers_
private

Definition at line 188 of file MachineInstrDDG.hh.

Referenced by assignPhysReg(), and createFalseDepEdge().

◆ mf_

llvm::MachineFunction& MachineInstrDDG::mf_
private

Definition at line 200 of file MachineInstrDDG.hh.

◆ nodes_

NodeSet MachineInstrDDG::nodes_
private

Definition at line 186 of file MachineInstrDDG.hh.

Referenced by MachineInstrDDG().

◆ onlyTrueDeps_

const bool MachineInstrDDG::onlyTrueDeps_
private

Definition at line 193 of file MachineInstrDDG.hh.

◆ printOnlyCriticalPath_

bool MachineInstrDDG::printOnlyCriticalPath_
private

Definition at line 203 of file MachineInstrDDG.hh.

Referenced by dotString(), and setPrintOnlyCriticalPath().

◆ regAssignments_

RegisterMap MachineInstrDDG::regAssignments_
private

Definition at line 190 of file MachineInstrDDG.hh.

Referenced by assignPhysReg(), and preceedingNodeUsesOrDefinesReg().

◆ regInfo_

const llvm::TargetRegisterInfo* MachineInstrDDG::regInfo_
private

Definition at line 201 of file MachineInstrDDG.hh.

Referenced by preceedingNodeUsesOrDefinesReg().

◆ schedule_

std::map<int, std::list<MIDDGNode*> > MachineInstrDDG::schedule_
mutableprivate

Definition at line 198 of file MachineInstrDDG.hh.

Referenced by computeOptimalSchedule(), and dotString().

◆ smallestCycle_

int MachineInstrDDG::smallestCycle_
private

Definition at line 196 of file MachineInstrDDG.hh.

Referenced by computeOptimalSchedule(), and dotString().

◆ users_

UserMap MachineInstrDDG::users_
mutableprivate

Definition at line 184 of file MachineInstrDDG.hh.

Referenced by lastVregUser(), and MachineInstrDDG().


The documentation for this class was generated from the following files:
MIDDGNode::osalOperationName
TCEString osalOperationName() const
Definition: MachineInstrDDG.cc:566
BoostGraph< MIDDGNode, MIDDGEdge >::predecessors
virtual NodeSet predecessors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
MIDDGEdge
Definition: MachineInstrDDG.hh:86
BoostGraph< MIDDGNode, MIDDGEdge >::connectNodes
virtual void connectNodes(const Node &nTail, const Node &nHead, Edge &e)
MachineInstrDDG::largestCycle_
int largestCycle_
Definition: MachineInstrDDG.hh:197
MachineInstrDDG::lastPhysRegUsers_
std::map< Register, MIDDGNode * > lastPhysRegUsers_
Definition: MachineInstrDDG.hh:188
BoostGraph< MIDDGNode, MIDDGEdge >::tailNode
virtual Node & tailNode(const Edge &edge) const
BoostGraph< MIDDGNode, MIDDGEdge >::headNode
virtual Node & headNode(const Edge &edge) const
BoostGraph< MIDDGNode, MIDDGEdge >::node
Node & node(const int index) const
BoostGraph< MIDDGNode, MIDDGEdge >::hasPath
bool hasPath(MIDDGNode &src, const MIDDGNode &dest) const
BoostGraph< MIDDGNode, MIDDGEdge >::maxSourceDistance
int maxSourceDistance(const MIDDGNode &node) const
BoostGraph< MIDDGNode, MIDDGEdge >::NodeSet
std::set< MIDDGNode *, typename MIDDGNode ::Comparator > NodeSet
Definition: BoostGraph.hh:86
BoostGraph< MIDDGNode, MIDDGEdge >::Edge
MIDDGEdge Edge
The (base) edge type managed by this graph.
Definition: BoostGraph.hh:92
GraphNode::nodeID
int nodeID() const
MachineInstrDDG::lastPhysRegDefiners_
std::map< Register, MIDDGNode * > lastPhysRegDefiners_
Definition: MachineInstrDDG.hh:189
MIDDGNode::optimalCycle
int optimalCycle() const
Definition: MachineInstrDDG.hh:79
Application::logStream
static std::ostream & logStream()
Definition: Application.cc:155
BoostGraph< MIDDGNode, MIDDGEdge >::addNode
virtual void addNode(Node &node)
MachineInstrDDG::regInfo_
const llvm::TargetRegisterInfo * regInfo_
Definition: MachineInstrDDG.hh:201
BoostGraph< MIDDGNode, MIDDGEdge >::edgeCount
int edgeCount() const
MachineInstrDDG::allRegisters_
RegisterSet allRegisters_
Definition: MachineInstrDDG.hh:181
MIDDGEdge::toString
TCEString toString() const
Definition: MachineInstrDDG.hh:111
MachineInstrDDG::schedule_
std::map< int, std::list< MIDDGNode * > > schedule_
Definition: MachineInstrDDG.hh:198
assert
#define assert(condition)
Definition: Application.hh:86
MIDDGNode::setOptimalCycle
void setOptimalCycle(int cycle)
Definition: MachineInstrDDG.hh:78
MachineInstrDDG::createFalseDepEdge
std::pair< MIDDGNode *, MIDDGNode * > createFalseDepEdge(Register vreg, Register physReg) const
Definition: MachineInstrDDG.cc:202
MIDDGEdge::DEP_WAR
@ DEP_WAR
Definition: MachineInstrDDG.hh:90
MachineInstrDDG::lastVregUser
MIDDGNode * lastVregUser(Register vreg) const
Definition: MachineInstrDDG.cc:297
MIDDGNode
Definition: MachineInstrDDG.hh:58
MachineInstrDDG::definers_
DefinerMap definers_
Definition: MachineInstrDDG.hh:183
MachineInstrDDG::onlyTrueDeps_
const bool onlyTrueDeps_
Definition: MachineInstrDDG.hh:193
BoostGraph< MIDDGNode, MIDDGEdge >::Node
MIDDGNode Node
The (base) node type managed by this graph.
Definition: BoostGraph.hh:90
BoostGraph< MIDDGNode, MIDDGEdge >::hasNode
bool hasNode(const Node &) const
MachineInstrDDG::smallestCycle_
int smallestCycle_
Definition: MachineInstrDDG.hh:196
BoostGraph< MIDDGNode, MIDDGEdge >::edge
virtual Edge & edge(const int index) const
BoostGraph< MIDDGNode, MIDDGEdge >::isInCriticalPath
bool isInCriticalPath(const MIDDGNode &node) const
Definition: BoostGraph.hh:179
MachineInstrDDG::users_
UserMap users_
Definition: MachineInstrDDG.hh:184
MachineInstrDDG::nodes_
NodeSet nodes_
Definition: MachineInstrDDG.hh:186
MachineInstrDDG::Register
unsigned Register
Definition: MachineInstrDDG.hh:143
TCEString
Definition: TCEString.hh:53
MachineInstrDDG::edges_
std::set< MIDDGEdge * > edges_
Definition: MachineInstrDDG.hh:187
BoostGraph< MIDDGNode, MIDDGEdge >
BoostGraph::name
virtual const TCEString & name() const
BoostGraph< MIDDGNode, MIDDGEdge >::nodeCount
int nodeCount() const
MachineInstrDDG::printOnlyCriticalPath_
bool printOnlyCriticalPath_
Definition: MachineInstrDDG.hh:203
MachineInstrDDG::vregDefiner
MIDDGNode * vregDefiner(Register vreg) const
Definition: MachineInstrDDG.hh:156
MIDDGNode::sequentialAddress
int sequentialAddress() const
Definition: MachineInstrDDG.hh:73
MIDDGNode::machineInstr
const llvm::MachineInstr * machineInstr() const
Definition: MachineInstrDDG.hh:72
MachineInstrDDG::regAssignments_
RegisterMap regAssignments_
Definition: MachineInstrDDG.hh:190
MachineInstrDDG::mf_
llvm::MachineFunction & mf_
Definition: MachineInstrDDG.hh:200