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/CommandLine.h"
22 #include "llvm/Support/Debug.h"
27 //===----------------------------------------------------------------------===//
29 /// BitsIterator - Provides iteration through individual bits in a bit vector.
34 T Bits; // Bits left to iterate through
38 BitsIterator(T Initial) : Bits(Initial) {}
40 /// Next - Returns the next bit set or zero if exhausted.
42 // Get the rightmost bit set
43 T Result = Bits & -Bits;
46 // Return single bit or zero
51 //===----------------------------------------------------------------------===//
54 //===----------------------------------------------------------------------===//
56 /// ResourceTally - Manages the use of resources over time intervals. Each
57 /// item (slot) in the tally vector represents the resources used at a given
58 /// moment. A bit set to 1 indicates that a resource is in use, otherwise
59 /// available. An assumption is made that the tally is large enough to schedule
60 /// all current instructions (asserts otherwise.)
65 std::vector<T> Tally; // Resources used per slot
66 typedef typename std::vector<T>::iterator Iter;
69 /// SlotsAvailable - Returns true if all units are available.
71 bool SlotsAvailable(Iter Begin, unsigned N, unsigned ResourceSet,
73 assert(N && "Must check availability with N != 0");
74 // Determine end of interval
76 assert(End <= Tally.end() && "Tally is not large enough for schedule");
78 // Iterate thru each resource
79 BitsIterator<T> Resources(ResourceSet & ~*Begin);
80 while (unsigned Res = Resources.Next()) {
81 // Check if resource is available for next N slots
85 if (*Interval & Res) break;
86 } while (Interval != Begin);
89 if (Interval == Begin) {
101 /// RetrySlot - Finds a good candidate slot to retry search.
102 Iter RetrySlot(Iter Begin, unsigned N, unsigned ResourceSet) {
103 assert(N && "Must check availability with N != 0");
104 // Determine end of interval
105 Iter End = Begin + N;
106 assert(End <= Tally.end() && "Tally is not large enough for schedule");
108 while (Begin != End--) {
109 // Clear units in use
110 ResourceSet &= ~*End;
111 // If no units left then we should go no further
112 if (!ResourceSet) return End + 1;
114 // Made it all the way through
118 /// FindAndReserveStages - Return true if the stages can be completed. If
120 bool FindAndReserveStages(Iter Begin,
121 InstrStage *Stage, InstrStage *StageEnd) {
122 // If at last stage then we're done
123 if (Stage == StageEnd) return true;
124 // Get number of cycles for current stage
125 unsigned N = Stage->Cycles;
126 // Check to see if N slots are available, if not fail
128 if (!SlotsAvailable(Begin, N, Stage->Units, Resource)) return false;
129 // Check to see if remaining stages are available, if not fail
130 if (!FindAndReserveStages(Begin + N, Stage + 1, StageEnd)) return false;
132 Reserve(Begin, N, Resource);
137 /// Reserve - Mark busy (set) the specified N slots.
138 void Reserve(Iter Begin, unsigned N, unsigned Resource) {
139 // Determine end of interval
140 Iter End = Begin + N;
141 assert(End <= Tally.end() && "Tally is not large enough for schedule");
143 // Set resource bit in each slot
144 for (; Begin < End; Begin++)
148 /// FindSlots - Starting from Begin, locate consecutive slots where all stages
149 /// can be completed. Returns the address of first slot.
150 Iter FindSlots(Iter Begin, InstrStage *StageBegin, InstrStage *StageEnd) {
154 // Try all possible slots forward
156 // Try at cursor, if successful return position.
157 if (FindAndReserveStages(Cursor, StageBegin, StageEnd)) return Cursor;
158 // Locate a better position
159 Cursor = RetrySlot(Cursor + 1, StageBegin->Cycles, StageBegin->Units);
164 /// Initialize - Resize and zero the tally to the specified number of time
166 inline void Initialize(unsigned N) {
167 Tally.assign(N, 0); // Initialize tally to all zeros.
170 // FindAndReserve - Locate an ideal slot for the specified stages and mark
172 unsigned FindAndReserve(unsigned Slot, InstrStage *StageBegin,
173 InstrStage *StageEnd) {
175 Iter Begin = Tally.begin() + Slot;
177 Iter Where = FindSlots(Begin, StageBegin, StageEnd);
178 // Distance is slot number
179 unsigned Final = Where - Tally.begin();
185 //===----------------------------------------------------------------------===//
187 /// ScheduleDAGSimple - Simple two pass scheduler.
189 class ScheduleDAGSimple : public ScheduleDAG {
191 ResourceTally<unsigned> Tally; // Resource usage tally
192 unsigned NSlots; // Total latency
193 static const unsigned NotFound = ~0U; // Search marker
198 ScheduleDAGSimple(SchedHeuristics hstc, SelectionDAG &dag,
199 MachineBasicBlock *bb, const TargetMachine &tm)
200 : ScheduleDAG(hstc, dag, bb, tm), Tally(), NSlots(0) {
201 assert(&TII && "Target doesn't provide instr info?");
202 assert(&MRI && "Target doesn't provide register info?");
205 virtual ~ScheduleDAGSimple() {};
208 static bool isDefiner(NodeInfo *A, NodeInfo *B);
209 void IncludeNode(NodeInfo *NI);
212 void GatherSchedulingInfo();
213 void FakeGroupDominators();
214 bool isStrongDependency(NodeInfo *A, NodeInfo *B);
215 bool isWeakDependency(NodeInfo *A, NodeInfo *B);
216 void ScheduleBackward();
217 void ScheduleForward();
220 //===----------------------------------------------------------------------===//
221 /// Special case itineraries.
224 CallLatency = 40, // To push calls back in time
226 RSInteger = 0xC0000000, // Two integer units
227 RSFloat = 0x30000000, // Two float units
228 RSLoadStore = 0x0C000000, // Two load store units
229 RSBranch = 0x02000000 // One branch unit
231 static InstrStage CallStage = { CallLatency, RSBranch };
232 static InstrStage LoadStage = { 5, RSLoadStore };
233 static InstrStage StoreStage = { 2, RSLoadStore };
234 static InstrStage IntStage = { 2, RSInteger };
235 static InstrStage FloatStage = { 3, RSFloat };
236 //===----------------------------------------------------------------------===//
240 //===----------------------------------------------------------------------===//
243 //===----------------------------------------------------------------------===//
244 /// isDefiner - Return true if node A is a definer for B.
246 bool ScheduleDAGSimple::isDefiner(NodeInfo *A, NodeInfo *B) {
247 // While there are A nodes
248 NodeGroupIterator NII(A);
249 while (NodeInfo *NI = NII.next()) {
251 SDNode *Node = NI->Node;
252 // While there operands in nodes of B
253 NodeGroupOpIterator NGOI(B);
254 while (!NGOI.isEnd()) {
255 SDOperand Op = NGOI.next();
256 // If node from A defines a node in B
257 if (Node == Op.Val) return true;
263 /// IncludeNode - Add node to NodeInfo vector.
265 void ScheduleDAGSimple::IncludeNode(NodeInfo *NI) {
267 SDNode *Node = NI->Node;
269 if (Node->getOpcode() == ISD::EntryToken) return;
270 // Check current count for node
271 int Count = NI->getPending();
272 // If the node is already in list
273 if (Count < 0) return;
274 // Decrement count to indicate a visit
276 // If count has gone to zero then add node to list
279 if (NI->isInGroup()) {
280 Ordering.push_back(NI->Group->getDominator());
282 Ordering.push_back(NI);
284 // indicate node has been added
287 // Mark as visited with new count
288 NI->setPending(Count);
291 /// GatherSchedulingInfo - Get latency and resource information about each node.
293 void ScheduleDAGSimple::GatherSchedulingInfo() {
294 // Get instruction itineraries for the target
295 const InstrItineraryData InstrItins = TM.getInstrItineraryData();
298 for (unsigned i = 0, N = NodeCount; i < N; i++) {
300 NodeInfo* NI = &Info[i];
301 SDNode *Node = NI->Node;
303 // If there are itineraries and it is a machine instruction
304 if (InstrItins.isEmpty() || Heuristic == simpleNoItinScheduling) {
306 if (Node->isTargetOpcode()) {
307 // Get return type to guess which processing unit
308 MVT::ValueType VT = Node->getValueType(0);
309 // Get machine opcode
310 MachineOpCode TOpc = Node->getTargetOpcode();
311 NI->IsCall = TII->isCall(TOpc);
312 NI->IsLoad = TII->isLoad(TOpc);
313 NI->IsStore = TII->isStore(TOpc);
315 if (TII->isLoad(TOpc)) NI->StageBegin = &LoadStage;
316 else if (TII->isStore(TOpc)) NI->StageBegin = &StoreStage;
317 else if (MVT::isInteger(VT)) NI->StageBegin = &IntStage;
318 else if (MVT::isFloatingPoint(VT)) NI->StageBegin = &FloatStage;
319 if (NI->StageBegin) NI->StageEnd = NI->StageBegin + 1;
321 } else if (Node->isTargetOpcode()) {
322 // get machine opcode
323 MachineOpCode TOpc = Node->getTargetOpcode();
324 // Check to see if it is a call
325 NI->IsCall = TII->isCall(TOpc);
326 // Get itinerary stages for instruction
327 unsigned II = TII->getSchedClass(TOpc);
328 NI->StageBegin = InstrItins.begin(II);
329 NI->StageEnd = InstrItins.end(II);
332 // One slot for the instruction itself
335 // Add long latency for a call to push it back in time
336 if (NI->IsCall) NI->Latency += CallLatency;
338 // Sum up all the latencies
339 for (InstrStage *Stage = NI->StageBegin, *E = NI->StageEnd;
340 Stage != E; Stage++) {
341 NI->Latency += Stage->Cycles;
344 // Sum up all the latencies for max tally size
345 NSlots += NI->Latency;
348 // Unify metrics if in a group
350 for (unsigned i = 0, N = NodeCount; i < N; i++) {
351 NodeInfo* NI = &Info[i];
353 if (NI->isInGroup()) {
354 NodeGroup *Group = NI->Group;
356 if (!Group->getDominator()) {
357 NIIterator NGI = Group->group_begin(), NGE = Group->group_end();
358 NodeInfo *Dominator = *NGI;
359 unsigned Latency = 0;
361 for (NGI++; NGI != NGE; NGI++) {
362 NodeInfo* NGNI = *NGI;
363 Latency += NGNI->Latency;
364 if (Dominator->Latency < NGNI->Latency) Dominator = NGNI;
367 Dominator->Latency = Latency;
368 Group->setDominator(Dominator);
375 /// VisitAll - Visit each node breadth-wise to produce an initial ordering.
376 /// Note that the ordering in the Nodes vector is reversed.
377 void ScheduleDAGSimple::VisitAll() {
378 // Add first element to list
379 NodeInfo *NI = getNI(DAG.getRoot().Val);
380 if (NI->isInGroup()) {
381 Ordering.push_back(NI->Group->getDominator());
383 Ordering.push_back(NI);
386 // Iterate through all nodes that have been added
387 for (unsigned i = 0; i < Ordering.size(); i++) { // note: size() varies
388 // Visit all operands
389 NodeGroupOpIterator NGI(Ordering[i]);
390 while (!NGI.isEnd()) {
392 SDOperand Op = NGI.next();
394 SDNode *Node = Op.Val;
395 // Ignore passive nodes
396 if (isPassiveNode(Node)) continue;
398 IncludeNode(getNI(Node));
402 // Add entry node last (IncludeNode filters entry nodes)
403 if (DAG.getEntryNode().Val != DAG.getRoot().Val)
404 Ordering.push_back(getNI(DAG.getEntryNode().Val));
407 std::reverse(Ordering.begin(), Ordering.end());
410 /// FakeGroupDominators - Set dominators for non-scheduling.
412 void ScheduleDAGSimple::FakeGroupDominators() {
413 for (unsigned i = 0, N = NodeCount; i < N; i++) {
414 NodeInfo* NI = &Info[i];
416 if (NI->isInGroup()) {
417 NodeGroup *Group = NI->Group;
419 if (!Group->getDominator()) {
420 Group->setDominator(NI);
426 /// isStrongDependency - Return true if node A has results used by node B.
427 /// I.E., B must wait for latency of A.
428 bool ScheduleDAGSimple::isStrongDependency(NodeInfo *A, NodeInfo *B) {
429 // If A defines for B then it's a strong dependency or
430 // if a load follows a store (may be dependent but why take a chance.)
431 return isDefiner(A, B) || (A->IsStore && B->IsLoad);
434 /// isWeakDependency Return true if node A produces a result that will
435 /// conflict with operands of B. It is assumed that we have called
436 /// isStrongDependency prior.
437 bool ScheduleDAGSimple::isWeakDependency(NodeInfo *A, NodeInfo *B) {
438 // TODO check for conflicting real registers and aliases
439 #if 0 // FIXME - Since we are in SSA form and not checking register aliasing
440 return A->Node->getOpcode() == ISD::EntryToken || isStrongDependency(B, A);
442 return A->Node->getOpcode() == ISD::EntryToken;
446 /// ScheduleBackward - Schedule instructions so that any long latency
447 /// instructions and the critical path get pushed back in time. Time is run in
448 /// reverse to allow code reuse of the Tally and eliminate the overhead of
449 /// biasing every slot indices against NSlots.
450 void ScheduleDAGSimple::ScheduleBackward() {
451 // Size and clear the resource tally
452 Tally.Initialize(NSlots);
453 // Get number of nodes to schedule
454 unsigned N = Ordering.size();
456 // For each node being scheduled
457 for (unsigned i = N; 0 < i--;) {
458 NodeInfo *NI = Ordering[i];
460 unsigned Slot = NotFound;
462 // Compare against those previously scheduled nodes
465 // Get following instruction
466 NodeInfo *Other = Ordering[j];
468 // Check dependency against previously inserted nodes
469 if (isStrongDependency(NI, Other)) {
470 Slot = Other->Slot + Other->Latency;
472 } else if (isWeakDependency(NI, Other)) {
478 // If independent of others (or first entry)
479 if (Slot == NotFound) Slot = 0;
481 #if 0 // FIXME - measure later
482 // Find a slot where the needed resources are available
483 if (NI->StageBegin != NI->StageEnd)
484 Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd);
490 // Insert sort based on slot
493 // Get following instruction
494 NodeInfo *Other = Ordering[j];
495 // Should we look further (remember slots are in reverse time)
496 if (Slot >= Other->Slot) break;
497 // Shuffle other into ordering
498 Ordering[j - 1] = Other;
500 // Insert node in proper slot
501 if (j != i + 1) Ordering[j - 1] = NI;
505 /// ScheduleForward - Schedule instructions to maximize packing.
507 void ScheduleDAGSimple::ScheduleForward() {
508 // Size and clear the resource tally
509 Tally.Initialize(NSlots);
510 // Get number of nodes to schedule
511 unsigned N = Ordering.size();
513 // For each node being scheduled
514 for (unsigned i = 0; i < N; i++) {
515 NodeInfo *NI = Ordering[i];
517 unsigned Slot = NotFound;
519 // Compare against those previously scheduled nodes
522 // Get following instruction
523 NodeInfo *Other = Ordering[j];
525 // Check dependency against previously inserted nodes
526 if (isStrongDependency(Other, NI)) {
527 Slot = Other->Slot + Other->Latency;
529 } else if (Other->IsCall || isWeakDependency(Other, NI)) {
535 // If independent of others (or first entry)
536 if (Slot == NotFound) Slot = 0;
538 // Find a slot where the needed resources are available
539 if (NI->StageBegin != NI->StageEnd)
540 Slot = Tally.FindAndReserve(Slot, NI->StageBegin, NI->StageEnd);
545 // Insert sort based on slot
548 // Get prior instruction
549 NodeInfo *Other = Ordering[j];
550 // Should we look further
551 if (Slot >= Other->Slot) break;
552 // Shuffle other into ordering
553 Ordering[j + 1] = Other;
555 // Insert node in proper slot
556 if (j != i) Ordering[j + 1] = NI;
560 /// Schedule - Order nodes according to selected style.
562 void ScheduleDAGSimple::Schedule() {
563 // Test to see if scheduling should occur
564 bool ShouldSchedule = NodeCount > 3 && Heuristic != noScheduling;
565 // Don't waste time if is only entry and return
566 if (ShouldSchedule) {
567 // Get latency and resource requirements
568 GatherSchedulingInfo();
569 } else if (HasGroups) {
570 // Make sure all the groups have dominators
571 FakeGroupDominators();
574 // Breadth first walk of DAG
578 static unsigned Count = 0;
580 for (unsigned i = 0, N = Ordering.size(); i < N; i++) {
581 NodeInfo *NI = Ordering[i];
586 // Don't waste time if is only entry and return
587 if (ShouldSchedule) {
588 // Push back long instructions and critical path
591 // Pack instructions to maximize resource utilization
595 DEBUG(printChanges(Count));
597 // Emit in scheduled order
602 /// createSimpleDAGScheduler - This creates a simple two pass instruction
604 llvm::ScheduleDAG* llvm::createSimpleDAGScheduler(SchedHeuristics Heuristic,
606 MachineBasicBlock *BB) {
607 return new ScheduleDAGSimple(Heuristic, DAG, BB, DAG.getTarget());