1 //===-- ScheduleDAGSimple.cpp - Implement a trivial DAG scheduler ---------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by James M. Laskey and is distributed under the
6 // University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements a simple two pass scheduler. The first pass attempts to push
11 // backward any lengthy instructions and critical paths. The second pass packs
12 // instructions into semi-optimal time slots.
14 //===----------------------------------------------------------------------===//
16 #define DEBUG_TYPE "sched"
17 #include "llvm/CodeGen/ScheduleDAG.h"
18 #include "llvm/CodeGen/SelectionDAG.h"
19 #include "llvm/Target/TargetMachine.h"
20 #include "llvm/Target/TargetInstrInfo.h"
21 #include "llvm/Support/Debug.h"
25 //===----------------------------------------------------------------------===//
27 /// BitsIterator - Provides iteration through individual bits in a bit vector.
32 T Bits; // Bits left to iterate through
36 BitsIterator(T Initial) : Bits(Initial) {}
38 /// Next - Returns the next bit set or zero if exhausted.
40 // Get the rightmost bit set
41 T Result = Bits & -Bits;
44 // Return single bit or zero
49 //===----------------------------------------------------------------------===//
52 //===----------------------------------------------------------------------===//
54 /// ResourceTally - Manages the use of resources over time intervals. Each
55 /// item (slot) in the tally vector represents the resources used at a given
56 /// moment. A bit set to 1 indicates that a resource is in use, otherwise
57 /// available. An assumption is made that the tally is large enough to schedule
58 /// all current instructions (asserts otherwise.)
63 std::vector<T> Tally; // Resources used per slot
64 typedef typename std::vector<T>::iterator Iter;
67 /// SlotsAvailable - Returns true if all units are available.
69 bool SlotsAvailable(Iter Begin, unsigned N, unsigned ResourceSet,
71 assert(N && "Must check availability with N != 0");
72 // Determine end of interval
74 assert(End <= Tally.end() && "Tally is not large enough for schedule");
76 // Iterate thru each resource
77 BitsIterator<T> Resources(ResourceSet & ~*Begin);
78 while (unsigned Res = Resources.Next()) {
79 // Check if resource is available for next N slots
83 if (*Interval & Res) break;
84 } while (Interval != Begin);
87 if (Interval == Begin) {
99 /// RetrySlot - Finds a good candidate slot to retry search.
100 Iter RetrySlot(Iter Begin, unsigned N, unsigned ResourceSet) {
101 assert(N && "Must check availability with N != 0");
102 // Determine end of interval
103 Iter End = Begin + N;
104 assert(End <= Tally.end() && "Tally is not large enough for schedule");
106 while (Begin != End--) {
107 // Clear units in use
108 ResourceSet &= ~*End;
109 // If no units left then we should go no further
110 if (!ResourceSet) return End + 1;
112 // Made it all the way through
116 /// FindAndReserveStages - Return true if the stages can be completed. If
118 bool FindAndReserveStages(Iter Begin,
119 InstrStage *Stage, InstrStage *StageEnd) {
120 // If at last stage then we're done
121 if (Stage == StageEnd) return true;
122 // Get number of cycles for current stage
123 unsigned N = Stage->Cycles;
124 // Check to see if N slots are available, if not fail
126 if (!SlotsAvailable(Begin, N, Stage->Units, Resource)) return false;
127 // Check to see if remaining stages are available, if not fail
128 if (!FindAndReserveStages(Begin + N, Stage + 1, StageEnd)) return false;
130 Reserve(Begin, N, Resource);
135 /// Reserve - Mark busy (set) the specified N slots.
136 void Reserve(Iter Begin, unsigned N, unsigned Resource) {
137 // Determine end of interval
138 Iter End = Begin + N;
139 assert(End <= Tally.end() && "Tally is not large enough for schedule");
141 // Set resource bit in each slot
142 for (; Begin < End; Begin++)
146 /// FindSlots - Starting from Begin, locate consecutive slots where all stages
147 /// can be completed. Returns the address of first slot.
148 Iter FindSlots(Iter Begin, InstrStage *StageBegin, InstrStage *StageEnd) {
152 // Try all possible slots forward
154 // Try at cursor, if successful return position.
155 if (FindAndReserveStages(Cursor, StageBegin, StageEnd)) return Cursor;
156 // Locate a better position
157 Cursor = RetrySlot(Cursor + 1, StageBegin->Cycles, StageBegin->Units);
162 /// Initialize - Resize and zero the tally to the specified number of time
164 inline void Initialize(unsigned N) {
165 Tally.assign(N, 0); // Initialize tally to all zeros.
168 // FindAndReserve - Locate an ideal slot for the specified stages and mark
170 unsigned FindAndReserve(unsigned Slot, InstrStage *StageBegin,
171 InstrStage *StageEnd) {
173 Iter Begin = Tally.begin() + Slot;
175 Iter Where = FindSlots(Begin, StageBegin, StageEnd);
176 // Distance is slot number
177 unsigned Final = Where - Tally.begin();
183 //===----------------------------------------------------------------------===//
185 /// ScheduleDAGSimple - Simple two pass scheduler.
187 class ScheduleDAGSimple : public ScheduleDAG {
189 ResourceTally<unsigned> Tally; // Resource usage tally
190 unsigned NSlots; // Total latency
191 static const unsigned NotFound = ~0U; // Search marker
196 ScheduleDAGSimple(SchedHeuristics hstc, SelectionDAG &dag,
197 MachineBasicBlock *bb, const TargetMachine &tm)
198 : ScheduleDAG(hstc, dag, bb, tm), Tally(), NSlots(0) {
199 assert(&TII && "Target doesn't provide instr info?");
200 assert(&MRI && "Target doesn't provide register info?");
203 virtual ~ScheduleDAGSimple() {};
208 static bool isDefiner(NodeInfo *A, NodeInfo *B);
209 void IncludeNode(NodeInfo *NI);
211 void GatherSchedulingInfo();
212 void FakeGroupDominators();
213 bool isStrongDependency(NodeInfo *A, NodeInfo *B);
214 bool isWeakDependency(NodeInfo *A, NodeInfo *B);
215 void ScheduleBackward();
216 void ScheduleForward();
219 //===----------------------------------------------------------------------===//
220 /// Special case itineraries.
223 CallLatency = 40, // To push calls back in time
225 RSInteger = 0xC0000000, // Two integer units
226 RSFloat = 0x30000000, // Two float units
227 RSLoadStore = 0x0C000000, // Two load store units
228 RSBranch = 0x02000000 // One branch unit
230 static InstrStage CallStage = { CallLatency, RSBranch };
231 static InstrStage LoadStage = { 5, RSLoadStore };
232 static InstrStage StoreStage = { 2, RSLoadStore };
233 static InstrStage IntStage = { 2, RSInteger };
234 static InstrStage FloatStage = { 3, RSFloat };
235 //===----------------------------------------------------------------------===//
239 //===----------------------------------------------------------------------===//
242 //===----------------------------------------------------------------------===//
243 /// isDefiner - Return true if node A is a definer for B.
245 bool ScheduleDAGSimple::isDefiner(NodeInfo *A, NodeInfo *B) {
246 // While there are A nodes
247 NodeGroupIterator NII(A);
248 while (NodeInfo *NI = NII.next()) {
250 SDNode *Node = NI->Node;
251 // While there operands in nodes of B
252 NodeGroupOpIterator NGOI(B);
253 while (!NGOI.isEnd()) {
254 SDOperand Op = NGOI.next();
255 // If node from A defines a node in B
256 if (Node == Op.Val) return true;
262 /// IncludeNode - Add node to NodeInfo vector.
264 void ScheduleDAGSimple::IncludeNode(NodeInfo *NI) {
266 SDNode *Node = NI->Node;
268 if (Node->getOpcode() == ISD::EntryToken) return;
269 // Check current count for node
270 int Count = NI->getPending();
271 // If the node is already in list
272 if (Count < 0) return;
273 // Decrement count to indicate a visit
275 // If count has gone to zero then add node to list
278 if (NI->isInGroup()) {
279 Ordering.push_back(NI->Group->getDominator());
281 Ordering.push_back(NI);
283 // indicate node has been added
286 // Mark as visited with new count
287 NI->setPending(Count);
290 /// GatherSchedulingInfo - Get latency and resource information about each node.
292 void ScheduleDAGSimple::GatherSchedulingInfo() {
293 // Get instruction itineraries for the target
294 const InstrItineraryData InstrItins = TM.getInstrItineraryData();
297 for (unsigned i = 0, N = NodeCount; i < N; i++) {
299 NodeInfo* NI = &Info[i];
300 SDNode *Node = NI->Node;
302 // If there are itineraries and it is a machine instruction
303 if (InstrItins.isEmpty() || Heuristic == simpleNoItinScheduling) {
305 if (Node->isTargetOpcode()) {
306 // Get return type to guess which processing unit
307 MVT::ValueType VT = Node->getValueType(0);
308 // Get machine opcode
309 MachineOpCode TOpc = Node->getTargetOpcode();
310 NI->IsCall = TII->isCall(TOpc);
311 NI->IsLoad = TII->isLoad(TOpc);
312 NI->IsStore = TII->isStore(TOpc);
314 if (TII->isLoad(TOpc)) NI->StageBegin = &LoadStage;
315 else if (TII->isStore(TOpc)) NI->StageBegin = &StoreStage;
316 else if (MVT::isInteger(VT)) NI->StageBegin = &IntStage;
317 else if (MVT::isFloatingPoint(VT)) NI->StageBegin = &FloatStage;
318 if (NI->StageBegin) NI->StageEnd = NI->StageBegin + 1;
320 } else if (Node->isTargetOpcode()) {
321 // get machine opcode
322 MachineOpCode TOpc = Node->getTargetOpcode();
323 // Check to see if it is a call
324 NI->IsCall = TII->isCall(TOpc);
325 // Get itinerary stages for instruction
326 unsigned II = TII->getSchedClass(TOpc);
327 NI->StageBegin = InstrItins.begin(II);
328 NI->StageEnd = InstrItins.end(II);
331 // One slot for the instruction itself
334 // Add long latency for a call to push it back in time
335 if (NI->IsCall) NI->Latency += CallLatency;
337 // Sum up all the latencies
338 for (InstrStage *Stage = NI->StageBegin, *E = NI->StageEnd;
339 Stage != E; Stage++) {
340 NI->Latency += Stage->Cycles;
343 // Sum up all the latencies for max tally size
344 NSlots += NI->Latency;
347 // Unify metrics if in a group
349 for (unsigned i = 0, N = NodeCount; i < N; i++) {
350 NodeInfo* NI = &Info[i];
352 if (NI->isInGroup()) {
353 NodeGroup *Group = NI->Group;
355 if (!Group->getDominator()) {
356 NIIterator NGI = Group->group_begin(), NGE = Group->group_end();
357 NodeInfo *Dominator = *NGI;
358 unsigned Latency = 0;
360 for (NGI++; NGI != NGE; NGI++) {
361 NodeInfo* NGNI = *NGI;
362 Latency += NGNI->Latency;
363 if (Dominator->Latency < NGNI->Latency) Dominator = NGNI;
366 Dominator->Latency = Latency;
367 Group->setDominator(Dominator);
374 /// VisitAll - Visit each node breadth-wise to produce an initial ordering.
375 /// Note that the ordering in the Nodes vector is reversed.
376 void ScheduleDAGSimple::VisitAll() {
377 // Add first element to list
378 NodeInfo *NI = getNI(DAG.getRoot().Val);
379 if (NI->isInGroup()) {
380 Ordering.push_back(NI->Group->getDominator());
382 Ordering.push_back(NI);
385 // Iterate through all nodes that have been added
386 for (unsigned i = 0; i < Ordering.size(); i++) { // note: size() varies
387 // Visit all operands
388 NodeGroupOpIterator NGI(Ordering[i]);
389 while (!NGI.isEnd()) {
391 SDOperand Op = NGI.next();
393 SDNode *Node = Op.Val;
394 // Ignore passive nodes
395 if (isPassiveNode(Node)) continue;
397 IncludeNode(getNI(Node));
401 // Add entry node last (IncludeNode filters entry nodes)
402 if (DAG.getEntryNode().Val != DAG.getRoot().Val)
403 Ordering.push_back(getNI(DAG.getEntryNode().Val));
406 std::reverse(Ordering.begin(), Ordering.end());
409 /// FakeGroupDominators - Set dominators for non-scheduling.
411 void ScheduleDAGSimple::FakeGroupDominators() {
412 for (unsigned i = 0, N = NodeCount; i < N; i++) {
413 NodeInfo* NI = &Info[i];
415 if (NI->isInGroup()) {
416 NodeGroup *Group = NI->Group;
418 if (!Group->getDominator()) {
419 Group->setDominator(NI);
425 /// isStrongDependency - Return true if node A has results used by node B.
426 /// I.E., B must wait for latency of A.
427 bool ScheduleDAGSimple::isStrongDependency(NodeInfo *A, NodeInfo *B) {
428 // If A defines for B then it's a strong dependency or
429 // if a load follows a store (may be dependent but why take a chance.)
430 return isDefiner(A, B) || (A->IsStore && B->IsLoad);
433 /// isWeakDependency Return true if node A produces a result that will
434 /// conflict with operands of B. It is assumed that we have called
435 /// isStrongDependency prior.
436 bool ScheduleDAGSimple::isWeakDependency(NodeInfo *A, NodeInfo *B) {
437 // TODO check for conflicting real registers and aliases
438 #if 0 // FIXME - Since we are in SSA form and not checking register aliasing
439 return A->Node->getOpcode() == ISD::EntryToken || isStrongDependency(B, A);
441 return A->Node->getOpcode() == ISD::EntryToken;
445 /// ScheduleBackward - Schedule instructions so that any long latency
446 /// instructions and the critical path get pushed back in time. Time is run in
447 /// reverse to allow code reuse of the Tally and eliminate the overhead of
448 /// biasing every slot indices against NSlots.
449 void ScheduleDAGSimple::ScheduleBackward() {
450 // Size and clear the resource tally
451 Tally.Initialize(NSlots);
452 // Get number of nodes to schedule
453 unsigned N = Ordering.size();
455 // For each node being scheduled
456 for (unsigned i = N; 0 < i--;) {
457 NodeInfo *NI = Ordering[i];
459 unsigned Slot = NotFound;
461 // Compare against those previously scheduled nodes
464 // Get following instruction
465 NodeInfo *Other = Ordering[j];
467 // Check dependency against previously inserted nodes
468 if (isStrongDependency(NI, Other)) {
469 Slot = Other->Slot + Other->Latency;
471 } else if (isWeakDependency(NI, Other)) {
477 // If independent of others (or first entry)
478 if (Slot == NotFound) Slot = 0;
480 #if 0 // FIXME - measure later
481 // Find a slot where the needed resources are available
482 if (NI->StageBegin != NI->StageEnd)
483 Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd);
489 // Insert sort based on slot
492 // Get following instruction
493 NodeInfo *Other = Ordering[j];
494 // Should we look further (remember slots are in reverse time)
495 if (Slot >= Other->Slot) break;
496 // Shuffle other into ordering
497 Ordering[j - 1] = Other;
499 // Insert node in proper slot
500 if (j != i + 1) Ordering[j - 1] = NI;
504 /// ScheduleForward - Schedule instructions to maximize packing.
506 void ScheduleDAGSimple::ScheduleForward() {
507 // Size and clear the resource tally
508 Tally.Initialize(NSlots);
509 // Get number of nodes to schedule
510 unsigned N = Ordering.size();
512 // For each node being scheduled
513 for (unsigned i = 0; i < N; i++) {
514 NodeInfo *NI = Ordering[i];
516 unsigned Slot = NotFound;
518 // Compare against those previously scheduled nodes
521 // Get following instruction
522 NodeInfo *Other = Ordering[j];
524 // Check dependency against previously inserted nodes
525 if (isStrongDependency(Other, NI)) {
526 Slot = Other->Slot + Other->Latency;
528 } else if (Other->IsCall || isWeakDependency(Other, NI)) {
534 // If independent of others (or first entry)
535 if (Slot == NotFound) Slot = 0;
537 // Find a slot where the needed resources are available
538 if (NI->StageBegin != NI->StageEnd)
539 Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd);
544 // Insert sort based on slot
547 // Get prior instruction
548 NodeInfo *Other = Ordering[j];
549 // Should we look further
550 if (Slot >= Other->Slot) break;
551 // Shuffle other into ordering
552 Ordering[j + 1] = Other;
554 // Insert node in proper slot
555 if (j != i) Ordering[j + 1] = NI;
559 /// Schedule - Order nodes according to selected style.
561 void ScheduleDAGSimple::Schedule() {
562 // Test to see if scheduling should occur
563 bool ShouldSchedule = NodeCount > 3 && Heuristic != noScheduling;
564 // Don't waste time if is only entry and return
565 if (ShouldSchedule) {
566 // Get latency and resource requirements
567 GatherSchedulingInfo();
568 } else if (HasGroups) {
569 // Make sure all the groups have dominators
570 FakeGroupDominators();
573 // Breadth first walk of DAG
577 static unsigned Count = 0;
579 for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
580 NodeInfo *NI = Ordering[i];
585 // Don't waste time if is only entry and return
586 if (ShouldSchedule) {
587 // Push back long instructions and critical path
590 // Pack instructions to maximize resource utilization
594 DEBUG(printChanges(Count));
596 // Emit in scheduled order
601 /// createSimpleDAGScheduler - This creates a simple two pass instruction
603 llvm::ScheduleDAG* llvm::createSimpleDAGScheduler(SchedHeuristics Heuristic,
605 MachineBasicBlock *BB) {
606 return new ScheduleDAGSimple(Heuristic, DAG, BB, DAG.getTarget());