1 //===-- SchedPriorities.h - Encapsulate scheduling heuristics --*- C++ -*--===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
11 // Priority ordering rules:
12 // (1) Max delay, which is the order of the heap S.candsAsHeap.
13 // (2) Instruction that frees up a register.
14 // (3) Instruction that has the maximum number of dependent instructions.
15 // Note that rules 2 and 3 are only used if issue conflicts prevent
16 // choosing a higher priority instruction by rule 1.
18 //===----------------------------------------------------------------------===//
20 #ifndef LLVM_CODEGEN_SCHEDPRIORITIES_H
21 #define LLVM_CODEGEN_SCHEDPRIORITIES_H
23 #include "SchedGraph.h"
24 #include "llvm/CodeGen/InstrScheduling.h"
25 #include "llvm/Target/TargetSchedInfo.h"
26 #include "Support/hash_set"
33 class SchedulingManager;
34 class FunctionLiveVarInfo;
36 //---------------------------------------------------------------------------
37 // Debug option levels for instruction scheduling
39 enum SchedDebugLevel_t {
42 Sched_PrintMachineCode,
43 Sched_PrintSchedTrace,
44 Sched_PrintSchedGraphs,
47 extern SchedDebugLevel_t SchedDebugLevel;
49 //---------------------------------------------------------------------------
50 // Function: instrIsFeasible
53 // Used by the priority analysis to filter out instructions
54 // that are not feasible to issue in the current cycle.
55 // Should only be used during schedule construction..
56 //---------------------------------------------------------------------------
58 bool instrIsFeasible(const SchedulingManager &S, MachineOpCode opCode);
62 struct NodeDelayPair {
63 const SchedGraphNode* node;
65 NodeDelayPair(const SchedGraphNode* n, cycles_t d) : node(n), delay(d) {}
66 inline bool operator<(const NodeDelayPair& np) { return delay < np.delay; }
70 NDPLessThan(const NodeDelayPair* np1, const NodeDelayPair* np2)
72 return np1->delay < np2->delay;
75 class NodeHeap : public std::list<NodeDelayPair*> {
76 NodeHeap(const NodeHeap&); // DO NOT IMPLEMENT
77 void operator=(const NodeHeap&); // DO NOT IMPLEMENT
79 typedef std::list<NodeDelayPair*>::iterator iterator;
80 typedef std::list<NodeDelayPair*>::const_iterator const_iterator;
83 NodeHeap() : _size(0) {}
85 inline unsigned size() const { return _size; }
87 const SchedGraphNode* getNode (const_iterator i) const { return (*i)->node; }
88 cycles_t getDelay(const_iterator i) const { return (*i)->delay;}
90 inline void makeHeap() {
91 // make_heap(begin(), end(), NDPLessThan);
94 inline iterator findNode(const SchedGraphNode* node) {
95 for (iterator I=begin(); I != end(); ++I)
96 if (getNode(I) == node)
101 inline void removeNode (const SchedGraphNode* node) {
102 iterator ndpPtr = findNode(node);
111 void insert(const SchedGraphNode* node, cycles_t delay) {
112 NodeDelayPair* ndp = new NodeDelayPair(node, delay);
113 if (_size == 0 || front()->delay < delay)
118 for ( ; I != end() && getDelay(I) >= delay; ++I)
120 std::list<NodeDelayPair*>::insert(I, ndp);
129 class SchedPriorities {
130 SchedPriorities(const SchedPriorities&); // DO NOT IMPLEMENT
131 void operator=(const SchedPriorities &); // DO NOT IMPLEMENT
133 SchedPriorities(const Function *F, const SchedGraph *G,
134 FunctionLiveVarInfo &LVI);
137 // This must be called before scheduling begins.
140 cycles_t getTime () const { return curTime; }
141 cycles_t getEarliestReadyTime () const { return earliestReadyTime; }
142 unsigned getNumReady () const { return candsAsHeap.size(); }
143 bool nodeIsReady (const SchedGraphNode* node) const {
144 return (candsAsSet.find(node) != candsAsSet.end());
147 void issuedReadyNodeAt (cycles_t curTime,
148 const SchedGraphNode* node);
150 void insertReady (const SchedGraphNode* node);
152 void updateTime (cycles_t /*unused*/);
154 const SchedGraphNode* getNextHighest (const SchedulingManager& S,
156 // choose next highest priority instr
159 typedef NodeHeap::iterator candIndex;
163 const SchedGraph* graph;
164 FunctionLiveVarInfo &methodLiveVarInfo;
165 hash_map<const MachineInstr*, bool> lastUseMap;
166 std::vector<cycles_t> nodeDelayVec;
167 std::vector<cycles_t> nodeEarliestUseVec;
168 std::vector<cycles_t> earliestReadyTimeForNode;
169 cycles_t earliestReadyTime;
170 NodeHeap candsAsHeap; // candidate nodes, ready to go
171 hash_set<const SchedGraphNode*> candsAsSet; //same entries as candsAsHeap,
172 // but as set for fast lookup
173 std::vector<candIndex> mcands; // holds pointers into cands
174 candIndex nextToTry; // next cand after the last
175 // one tried in this cycle
177 int chooseByRule1 (std::vector<candIndex>& mcands);
178 int chooseByRule2 (std::vector<candIndex>& mcands);
179 int chooseByRule3 (std::vector<candIndex>& mcands);
181 void findSetWithMaxDelay (std::vector<candIndex>& mcands,
182 const SchedulingManager& S);
184 void computeDelays (const SchedGraph* graph);
186 void initializeReadyHeap (const SchedGraph* graph);
188 bool instructionHasLastUse (FunctionLiveVarInfo& LVI,
189 const SchedGraphNode* graphNode);
191 // NOTE: The next two return references to the actual vector entries.
192 // Use the following two if you don't need to modify the value.
193 cycles_t& getNodeDelayRef (const SchedGraphNode* node) {
194 assert(node->getNodeId() < nodeDelayVec.size());
195 return nodeDelayVec[node->getNodeId()];
197 cycles_t& getEarliestReadyTimeForNodeRef (const SchedGraphNode* node) {
198 assert(node->getNodeId() < earliestReadyTimeForNode.size());
199 return earliestReadyTimeForNode[node->getNodeId()];
202 cycles_t getNodeDelay (const SchedGraphNode* node) const {
203 return ((SchedPriorities*) this)->getNodeDelayRef(node);
205 cycles_t getEarliestReadyTimeForNode(const SchedGraphNode* node) const {
206 return ((SchedPriorities*) this)->getEarliestReadyTimeForNodeRef(node);
211 inline void SchedPriorities::updateTime(cycles_t c) {
213 nextToTry = candsAsHeap.begin();
217 std::ostream &operator<<(std::ostream &os, const NodeDelayPair* nd);
219 } // End llvm namespace