aboutsummaryrefslogtreecommitdiffstats
path: root/lib/CodeGen/InstrSched/SchedPriorities.h
blob: 74704678066088137f9fc3b9e72e0e9c2774d313 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
//===-- SchedPriorities.h - Encapsulate scheduling heuristics --*- C++ -*--===//
// 
//                     The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
// 
//===----------------------------------------------------------------------===//
// 
// Strategy:
//    Priority ordering rules:
//    (1) Max delay, which is the order of the heap S.candsAsHeap.
//    (2) Instruction that frees up a register.
//    (3) Instruction that has the maximum number of dependent instructions.
//    Note that rules 2 and 3 are only used if issue conflicts prevent
//    choosing a higher priority instruction by rule 1.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_CODEGEN_SCHEDPRIORITIES_H
#define LLVM_CODEGEN_SCHEDPRIORITIES_H

#include "SchedGraph.h"
#include "llvm/CodeGen/InstrScheduling.h"
#include "llvm/Target/TargetSchedInfo.h"
#include "Support/hash_set"
#include <list>

namespace llvm {

class Function;
class MachineInstr;
class SchedulingManager;
class FunctionLiveVarInfo;

//---------------------------------------------------------------------------
// Debug option levels for instruction scheduling

enum SchedDebugLevel_t {
  Sched_NoDebugInfo,
  Sched_Disable,
  Sched_PrintMachineCode, 
  Sched_PrintSchedTrace,
  Sched_PrintSchedGraphs,
};

extern SchedDebugLevel_t SchedDebugLevel;

//---------------------------------------------------------------------------
// Function: instrIsFeasible
// 
// Purpose:
//   Used by the priority analysis to filter out instructions
//   that are not feasible to issue in the current cycle.
//   Should only be used during schedule construction..
//---------------------------------------------------------------------------

bool instrIsFeasible(const SchedulingManager &S, MachineOpCode opCode);



struct NodeDelayPair {
  const SchedGraphNode* node;
  cycles_t delay;
  NodeDelayPair(const SchedGraphNode* n, cycles_t d) :  node(n), delay(d) {}
  inline bool operator<(const NodeDelayPair& np) { return delay < np.delay; }
};

inline bool
NDPLessThan(const NodeDelayPair* np1, const NodeDelayPair* np2)
{
  return np1->delay < np2->delay;
}

class NodeHeap : public std::list<NodeDelayPair*> {
  NodeHeap(const NodeHeap&);          // DO NOT IMPLEMENT
  void operator=(const NodeHeap&);    // DO NOT IMPLEMENT
public:
  typedef std::list<NodeDelayPair*>::iterator iterator;
  typedef std::list<NodeDelayPair*>::const_iterator const_iterator;
  
public:
  NodeHeap() : _size(0) {}
  
  inline unsigned       size() const { return _size; }
  
  const SchedGraphNode* getNode	(const_iterator i) const { return (*i)->node; }
  cycles_t		getDelay(const_iterator i) const { return (*i)->delay;}
  
  inline void		makeHeap() { 
    // make_heap(begin(), end(), NDPLessThan);
  }
  
  inline iterator	findNode(const SchedGraphNode* node) {
    for (iterator I=begin(); I != end(); ++I)
      if (getNode(I) == node)
	return I;
    return end();
  }
  
  inline void	  removeNode	(const SchedGraphNode* node) {
    iterator ndpPtr = findNode(node);
    if (ndpPtr != end())
      {
	delete *ndpPtr;
	erase(ndpPtr);
	--_size;
      }
  };
  
  void		  insert(const SchedGraphNode* node, cycles_t delay) {
    NodeDelayPair* ndp = new NodeDelayPair(node, delay);
    if (_size == 0 || front()->delay < delay)
      push_front(ndp);
    else
      {
	iterator I=begin();
	for ( ; I != end() && getDelay(I) >= delay; ++I)
	  ;
	std::list<NodeDelayPair*>::insert(I, ndp);
      }
    _size++;
  }
private:
  unsigned int _size;
};


class SchedPriorities {
  SchedPriorities(const SchedPriorities&); // DO NOT IMPLEMENT
  void operator=(const SchedPriorities &); // DO NOT IMPLEMENT
public:
  SchedPriorities(const Function *F, const SchedGraph *G,
                  FunctionLiveVarInfo &LVI);
                  
  
  // This must be called before scheduling begins.
  void		initialize		();
  
  cycles_t	getTime			() const { return curTime; }
  cycles_t	getEarliestReadyTime	() const { return earliestReadyTime; }
  unsigned	getNumReady		() const { return candsAsHeap.size(); }
  bool		nodeIsReady		(const SchedGraphNode* node) const {
    return (candsAsSet.find(node) != candsAsSet.end());
  }
  
  void		issuedReadyNodeAt	(cycles_t curTime,
					 const SchedGraphNode* node);
  
  void		insertReady		(const SchedGraphNode* node);
  
  void		updateTime		(cycles_t /*unused*/);
  
  const SchedGraphNode* getNextHighest	(const SchedulingManager& S,
					 cycles_t curTime);
					// choose next highest priority instr
  
private:
  typedef NodeHeap::iterator candIndex;
  
private:
  cycles_t curTime;
  const SchedGraph* graph;
  FunctionLiveVarInfo &methodLiveVarInfo;
  hash_map<const MachineInstr*, bool> lastUseMap;
  std::vector<cycles_t> nodeDelayVec;
  std::vector<cycles_t> nodeEarliestUseVec;
  std::vector<cycles_t> earliestReadyTimeForNode;
  cycles_t earliestReadyTime;
  NodeHeap candsAsHeap;				// candidate nodes, ready to go
  hash_set<const SchedGraphNode*> candsAsSet;   //same entries as candsAsHeap,
						//   but as set for fast lookup
  std::vector<candIndex> mcands;                // holds pointers into cands
  candIndex nextToTry;				// next cand after the last
						//   one tried in this cycle
  
  int		chooseByRule1		(std::vector<candIndex>& mcands);
  int		chooseByRule2		(std::vector<candIndex>& mcands);
  int		chooseByRule3		(std::vector<candIndex>& mcands);
  
  void		findSetWithMaxDelay	(std::vector<candIndex>& mcands,
					 const SchedulingManager& S);
  
  void		computeDelays		(const SchedGraph* graph);
  
  void		initializeReadyHeap	(const SchedGraph* graph);
  
  bool		instructionHasLastUse	(FunctionLiveVarInfo& LVI,
					 const SchedGraphNode* graphNode);
  
  // NOTE: The next two return references to the actual vector entries.
  //       Use the following two if you don't need to modify the value.
  cycles_t&	getNodeDelayRef		(const SchedGraphNode* node) {
    assert(node->getNodeId() < nodeDelayVec.size());
    return nodeDelayVec[node->getNodeId()];
  }
  cycles_t&     getEarliestReadyTimeForNodeRef   (const SchedGraphNode* node) {
    assert(node->getNodeId() < earliestReadyTimeForNode.size());
    return earliestReadyTimeForNode[node->getNodeId()];
  }
  
  cycles_t      getNodeDelay            (const SchedGraphNode* node) const {
    return ((SchedPriorities*) this)->getNodeDelayRef(node); 
  }
  cycles_t      getEarliestReadyTimeForNode(const SchedGraphNode* node) const {
    return ((SchedPriorities*) this)->getEarliestReadyTimeForNodeRef(node);
  }
};


inline void SchedPriorities::updateTime(cycles_t c) {
  curTime = c;
  nextToTry = candsAsHeap.begin();
  mcands.clear();
}

std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd);

} // End llvm namespace

#endif