Evan Cheng | cd1419a | 2006-01-25 09:14:32 +0000 | [diff] [blame] | 1 | //===---- ScheduleDAGList.cpp - Implement a list scheduler for isel DAG ---===// |
Evan Cheng | f0f9c90 | 2006-01-23 08:26:10 +0000 | [diff] [blame] | 2 | // |
| 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
Chris Lattner | 4ee451d | 2007-12-29 20:36:04 +0000 | [diff] [blame^] | 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
Evan Cheng | f0f9c90 | 2006-01-23 08:26:10 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 10 | // This implements a top-down list scheduler, using standard algorithms. |
| 11 | // The basic approach uses a priority queue of available nodes to schedule. |
| 12 | // One at a time, nodes are taken from the priority queue (thus in priority |
| 13 | // order), checked for legality to schedule, and emitted if legal. |
Chris Lattner | 6af7ef8 | 2006-03-06 17:58:04 +0000 | [diff] [blame] | 14 | // |
| 15 | // Nodes may not be legal to schedule either due to structural hazards (e.g. |
| 16 | // pipeline or resource constraints) or because an input to the instruction has |
| 17 | // not completed execution. |
Evan Cheng | f0f9c90 | 2006-01-23 08:26:10 +0000 | [diff] [blame] | 18 | // |
| 19 | //===----------------------------------------------------------------------===// |
| 20 | |
Dale Johannesen | e7e7d0d | 2007-07-13 17:13:54 +0000 | [diff] [blame] | 21 | #define DEBUG_TYPE "pre-RA-sched" |
Evan Cheng | f0f9c90 | 2006-01-23 08:26:10 +0000 | [diff] [blame] | 22 | #include "llvm/CodeGen/ScheduleDAG.h" |
Jim Laskey | eb577ba | 2006-08-02 12:30:23 +0000 | [diff] [blame] | 23 | #include "llvm/CodeGen/SchedulerRegistry.h" |
Jim Laskey | 9ff542f | 2006-08-01 18:29:48 +0000 | [diff] [blame] | 24 | #include "llvm/CodeGen/SelectionDAGISel.h" |
Evan Cheng | 14a6db8 | 2006-05-04 19:16:39 +0000 | [diff] [blame] | 25 | #include "llvm/CodeGen/SSARegMap.h" |
| 26 | #include "llvm/Target/MRegisterInfo.h" |
Owen Anderson | 07000c6 | 2006-05-12 06:33:49 +0000 | [diff] [blame] | 27 | #include "llvm/Target/TargetData.h" |
Evan Cheng | f0f9c90 | 2006-01-23 08:26:10 +0000 | [diff] [blame] | 28 | #include "llvm/Target/TargetMachine.h" |
| 29 | #include "llvm/Target/TargetInstrInfo.h" |
Evan Cheng | cd1419a | 2006-01-25 09:14:32 +0000 | [diff] [blame] | 30 | #include "llvm/Support/Debug.h" |
Chris Lattner | a4f0b3a | 2006-08-27 12:54:02 +0000 | [diff] [blame] | 31 | #include "llvm/Support/Compiler.h" |
Chris Lattner | 6cc3f0a | 2006-03-05 23:13:56 +0000 | [diff] [blame] | 32 | #include "llvm/ADT/Statistic.h" |
Evan Cheng | cd1419a | 2006-01-25 09:14:32 +0000 | [diff] [blame] | 33 | #include <climits> |
Evan Cheng | f0f9c90 | 2006-01-23 08:26:10 +0000 | [diff] [blame] | 34 | #include <queue> |
| 35 | using namespace llvm; |
| 36 | |
Chris Lattner | cd3245a | 2006-12-19 22:41:21 +0000 | [diff] [blame] | 37 | STATISTIC(NumNoops , "Number of noops inserted"); |
| 38 | STATISTIC(NumStalls, "Number of pipeline stalls"); |
Evan Cheng | cd1419a | 2006-01-25 09:14:32 +0000 | [diff] [blame] | 39 | |
Jim Laskey | 13ec702 | 2006-08-01 14:21:23 +0000 | [diff] [blame] | 40 | static RegisterScheduler |
| 41 | tdListDAGScheduler("list-td", " Top-down list scheduler", |
| 42 | createTDListDAGScheduler); |
| 43 | |
Chris Lattner | 5874f82 | 2006-03-08 04:37:58 +0000 | [diff] [blame] | 44 | namespace { |
Chris Lattner | e87c5c8 | 2006-03-09 06:37:29 +0000 | [diff] [blame] | 45 | //===----------------------------------------------------------------------===// |
| 46 | /// ScheduleDAGList - The actual list scheduler implementation. This supports |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 47 | /// top-down scheduling. |
Chris Lattner | e87c5c8 | 2006-03-09 06:37:29 +0000 | [diff] [blame] | 48 | /// |
Chris Lattner | f8c68f6 | 2006-06-28 22:17:39 +0000 | [diff] [blame] | 49 | class VISIBILITY_HIDDEN ScheduleDAGList : public ScheduleDAG { |
Evan Cheng | f0f9c90 | 2006-01-23 08:26:10 +0000 | [diff] [blame] | 50 | private: |
Chris Lattner | 8469031 | 2006-03-11 22:44:37 +0000 | [diff] [blame] | 51 | /// AvailableQueue - The priority queue to use for the available SUnits. |
| 52 | /// |
| 53 | SchedulingPriorityQueue *AvailableQueue; |
Chris Lattner | e32178d | 2006-03-09 06:35:14 +0000 | [diff] [blame] | 54 | |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 55 | /// PendingQueue - This contains all of the instructions whose operands have |
| 56 | /// been issued, but their results are not ready yet (due to the latency of |
| 57 | /// the operation). Once the operands becomes available, the instruction is |
| 58 | /// added to the AvailableQueue. This keeps track of each SUnit and the |
| 59 | /// number of cycles left to execute before the operation is available. |
| 60 | std::vector<std::pair<unsigned, SUnit*> > PendingQueue; |
Evan Cheng | 14a6db8 | 2006-05-04 19:16:39 +0000 | [diff] [blame] | 61 | |
Chris Lattner | ad0f78a | 2006-03-05 22:45:01 +0000 | [diff] [blame] | 62 | /// HazardRec - The hazard recognizer to use. |
Chris Lattner | b0d21ef | 2006-03-08 04:25:59 +0000 | [diff] [blame] | 63 | HazardRecognizer *HazardRec; |
Evan Cheng | 14a6db8 | 2006-05-04 19:16:39 +0000 | [diff] [blame] | 64 | |
Evan Cheng | f0f9c90 | 2006-01-23 08:26:10 +0000 | [diff] [blame] | 65 | public: |
| 66 | ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb, |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 67 | const TargetMachine &tm, |
Chris Lattner | 8469031 | 2006-03-11 22:44:37 +0000 | [diff] [blame] | 68 | SchedulingPriorityQueue *availqueue, |
Chris Lattner | b0d21ef | 2006-03-08 04:25:59 +0000 | [diff] [blame] | 69 | HazardRecognizer *HR) |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 70 | : ScheduleDAG(dag, bb, tm), |
Chris Lattner | 8469031 | 2006-03-11 22:44:37 +0000 | [diff] [blame] | 71 | AvailableQueue(availqueue), HazardRec(HR) { |
Chris Lattner | ad0f78a | 2006-03-05 22:45:01 +0000 | [diff] [blame] | 72 | } |
Evan Cheng | cd1419a | 2006-01-25 09:14:32 +0000 | [diff] [blame] | 73 | |
| 74 | ~ScheduleDAGList() { |
Chris Lattner | b0d21ef | 2006-03-08 04:25:59 +0000 | [diff] [blame] | 75 | delete HazardRec; |
Chris Lattner | 8469031 | 2006-03-11 22:44:37 +0000 | [diff] [blame] | 76 | delete AvailableQueue; |
Evan Cheng | cd1419a | 2006-01-25 09:14:32 +0000 | [diff] [blame] | 77 | } |
Evan Cheng | f0f9c90 | 2006-01-23 08:26:10 +0000 | [diff] [blame] | 78 | |
| 79 | void Schedule(); |
Evan Cheng | f0f9c90 | 2006-01-23 08:26:10 +0000 | [diff] [blame] | 80 | |
Evan Cheng | cd1419a | 2006-01-25 09:14:32 +0000 | [diff] [blame] | 81 | private: |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 82 | void ReleaseSucc(SUnit *SuccSU, bool isChain); |
Chris Lattner | c1c078c | 2006-03-11 22:34:41 +0000 | [diff] [blame] | 83 | void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); |
Chris Lattner | 0324ba8 | 2006-03-09 06:48:37 +0000 | [diff] [blame] | 84 | void ListScheduleTopDown(); |
Evan Cheng | cd1419a | 2006-01-25 09:14:32 +0000 | [diff] [blame] | 85 | }; |
Chris Lattner | 5874f82 | 2006-03-08 04:37:58 +0000 | [diff] [blame] | 86 | } // end anonymous namespace |
Evan Cheng | cd1419a | 2006-01-25 09:14:32 +0000 | [diff] [blame] | 87 | |
Chris Lattner | 03fc53c | 2006-03-06 00:22:00 +0000 | [diff] [blame] | 88 | HazardRecognizer::~HazardRecognizer() {} |
| 89 | |
Evan Cheng | cdf3838 | 2006-01-26 00:30:29 +0000 | [diff] [blame] | 90 | |
Chris Lattner | 7d82b00 | 2006-03-11 22:28:35 +0000 | [diff] [blame] | 91 | /// Schedule - Schedule the DAG using list scheduling. |
Chris Lattner | 7d82b00 | 2006-03-11 22:28:35 +0000 | [diff] [blame] | 92 | void ScheduleDAGList::Schedule() { |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 93 | DOUT << "********** List Scheduling **********\n"; |
Chris Lattner | 7d82b00 | 2006-03-11 22:28:35 +0000 | [diff] [blame] | 94 | |
| 95 | // Build scheduling units. |
| 96 | BuildSchedUnits(); |
Evan Cheng | b63b067 | 2006-05-09 07:13:34 +0000 | [diff] [blame] | 97 | |
Evan Cheng | 95f6ede | 2006-11-04 09:44:31 +0000 | [diff] [blame] | 98 | AvailableQueue->initNodes(SUnitMap, SUnits); |
Chris Lattner | 7d82b00 | 2006-03-11 22:28:35 +0000 | [diff] [blame] | 99 | |
Evan Cheng | e165a78 | 2006-05-11 23:55:42 +0000 | [diff] [blame] | 100 | ListScheduleTopDown(); |
Chris Lattner | 7d82b00 | 2006-03-11 22:28:35 +0000 | [diff] [blame] | 101 | |
Chris Lattner | 8469031 | 2006-03-11 22:44:37 +0000 | [diff] [blame] | 102 | AvailableQueue->releaseState(); |
Chris Lattner | 7d82b00 | 2006-03-11 22:28:35 +0000 | [diff] [blame] | 103 | |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 104 | DOUT << "*** Final schedule ***\n"; |
Chris Lattner | 7d82b00 | 2006-03-11 22:28:35 +0000 | [diff] [blame] | 105 | DEBUG(dumpSchedule()); |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 106 | DOUT << "\n"; |
Chris Lattner | 7d82b00 | 2006-03-11 22:28:35 +0000 | [diff] [blame] | 107 | |
| 108 | // Emit in scheduled order |
| 109 | EmitSchedule(); |
| 110 | } |
| 111 | |
| 112 | //===----------------------------------------------------------------------===// |
Chris Lattner | 7d82b00 | 2006-03-11 22:28:35 +0000 | [diff] [blame] | 113 | // Top-Down Scheduling |
| 114 | //===----------------------------------------------------------------------===// |
| 115 | |
| 116 | /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 117 | /// the PendingQueue if the count reaches zero. |
| 118 | void ScheduleDAGList::ReleaseSucc(SUnit *SuccSU, bool isChain) { |
Evan Cheng | 74d2fd8 | 2007-09-28 19:24:24 +0000 | [diff] [blame] | 119 | SuccSU->NumPredsLeft--; |
Chris Lattner | 7d82b00 | 2006-03-11 22:28:35 +0000 | [diff] [blame] | 120 | |
Evan Cheng | 74d2fd8 | 2007-09-28 19:24:24 +0000 | [diff] [blame] | 121 | assert(SuccSU->NumPredsLeft >= 0 && |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 122 | "List scheduling internal error"); |
Chris Lattner | 7d82b00 | 2006-03-11 22:28:35 +0000 | [diff] [blame] | 123 | |
Evan Cheng | 74d2fd8 | 2007-09-28 19:24:24 +0000 | [diff] [blame] | 124 | if (SuccSU->NumPredsLeft == 0) { |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 125 | // Compute how many cycles it will be before this actually becomes |
| 126 | // available. This is the max of the start time of all predecessors plus |
| 127 | // their latencies. |
| 128 | unsigned AvailableCycle = 0; |
Chris Lattner | 228a18e | 2006-08-17 00:09:56 +0000 | [diff] [blame] | 129 | for (SUnit::pred_iterator I = SuccSU->Preds.begin(), |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 130 | E = SuccSU->Preds.end(); I != E; ++I) { |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 131 | // If this is a token edge, we don't need to wait for the latency of the |
| 132 | // preceeding instruction (e.g. a long-latency load) unless there is also |
| 133 | // some other data dependence. |
Evan Cheng | 713a98d | 2007-09-19 01:38:40 +0000 | [diff] [blame] | 134 | SUnit &Pred = *I->Dep; |
Chris Lattner | 228a18e | 2006-08-17 00:09:56 +0000 | [diff] [blame] | 135 | unsigned PredDoneCycle = Pred.Cycle; |
Evan Cheng | 713a98d | 2007-09-19 01:38:40 +0000 | [diff] [blame] | 136 | if (!I->isCtrl) |
Chris Lattner | 228a18e | 2006-08-17 00:09:56 +0000 | [diff] [blame] | 137 | PredDoneCycle += Pred.Latency; |
| 138 | else if (Pred.Latency) |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 139 | PredDoneCycle += 1; |
Chris Lattner | b221503 | 2006-03-12 03:52:09 +0000 | [diff] [blame] | 140 | |
| 141 | AvailableCycle = std::max(AvailableCycle, PredDoneCycle); |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 142 | } |
| 143 | |
| 144 | PendingQueue.push_back(std::make_pair(AvailableCycle, SuccSU)); |
Chris Lattner | 7d82b00 | 2006-03-11 22:28:35 +0000 | [diff] [blame] | 145 | } |
| 146 | } |
| 147 | |
| 148 | /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending |
| 149 | /// count of its successors. If a successor pending count is zero, add it to |
| 150 | /// the Available queue. |
Chris Lattner | 8469031 | 2006-03-11 22:44:37 +0000 | [diff] [blame] | 151 | void ScheduleDAGList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 152 | DOUT << "*** Scheduling [" << CurCycle << "]: "; |
Chris Lattner | 7d82b00 | 2006-03-11 22:28:35 +0000 | [diff] [blame] | 153 | DEBUG(SU->dump(&DAG)); |
| 154 | |
| 155 | Sequence.push_back(SU); |
Chris Lattner | 8469031 | 2006-03-11 22:44:37 +0000 | [diff] [blame] | 156 | SU->Cycle = CurCycle; |
Chris Lattner | 7d82b00 | 2006-03-11 22:28:35 +0000 | [diff] [blame] | 157 | |
| 158 | // Bottom up: release successors. |
Chris Lattner | 228a18e | 2006-08-17 00:09:56 +0000 | [diff] [blame] | 159 | for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); |
| 160 | I != E; ++I) |
Evan Cheng | 713a98d | 2007-09-19 01:38:40 +0000 | [diff] [blame] | 161 | ReleaseSucc(I->Dep, I->isCtrl); |
Chris Lattner | 7d82b00 | 2006-03-11 22:28:35 +0000 | [diff] [blame] | 162 | } |
| 163 | |
Chris Lattner | a5de484 | 2006-03-05 21:10:33 +0000 | [diff] [blame] | 164 | /// ListScheduleTopDown - The main loop of list scheduling for top-down |
| 165 | /// schedulers. |
Chris Lattner | 0324ba8 | 2006-03-09 06:48:37 +0000 | [diff] [blame] | 166 | void ScheduleDAGList::ListScheduleTopDown() { |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 167 | unsigned CurCycle = 0; |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 168 | SUnit *Entry = SUnitMap[DAG.getEntryNode().Val].front(); |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 169 | |
Chris Lattner | a5de484 | 2006-03-05 21:10:33 +0000 | [diff] [blame] | 170 | // All leaves to Available queue. |
Chris Lattner | c45a59b | 2006-03-08 04:54:34 +0000 | [diff] [blame] | 171 | for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { |
Chris Lattner | a5de484 | 2006-03-05 21:10:33 +0000 | [diff] [blame] | 172 | // It is available if it has no predecessors. |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 173 | if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) { |
Chris Lattner | 8469031 | 2006-03-11 22:44:37 +0000 | [diff] [blame] | 174 | AvailableQueue->push(&SUnits[i]); |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 175 | SUnits[i].isAvailable = SUnits[i].isPending = true; |
| 176 | } |
Chris Lattner | a5de484 | 2006-03-05 21:10:33 +0000 | [diff] [blame] | 177 | } |
| 178 | |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 179 | // Emit the entry node first. |
| 180 | ScheduleNodeTopDown(Entry, CurCycle); |
| 181 | HazardRec->EmitInstruction(Entry->Node); |
| 182 | |
Chris Lattner | a5de484 | 2006-03-05 21:10:33 +0000 | [diff] [blame] | 183 | // While Available queue is not empty, grab the node with the highest |
| 184 | // priority. If it is not ready put it back. Schedule the node. |
| 185 | std::vector<SUnit*> NotReady; |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 186 | while (!AvailableQueue->empty() || !PendingQueue.empty()) { |
| 187 | // Check to see if any of the pending instructions are ready to issue. If |
| 188 | // so, add them to the available queue. |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 189 | for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 190 | if (PendingQueue[i].first == CurCycle) { |
| 191 | AvailableQueue->push(PendingQueue[i].second); |
| 192 | PendingQueue[i].second->isAvailable = true; |
| 193 | PendingQueue[i] = PendingQueue.back(); |
| 194 | PendingQueue.pop_back(); |
| 195 | --i; --e; |
| 196 | } else { |
| 197 | assert(PendingQueue[i].first > CurCycle && "Negative latency?"); |
| 198 | } |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 199 | } |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 200 | |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 201 | // If there are no instructions available, don't try to issue anything, and |
| 202 | // don't advance the hazard recognizer. |
| 203 | if (AvailableQueue->empty()) { |
| 204 | ++CurCycle; |
| 205 | continue; |
| 206 | } |
Chris Lattner | a5de484 | 2006-03-05 21:10:33 +0000 | [diff] [blame] | 207 | |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 208 | SUnit *FoundSUnit = 0; |
| 209 | SDNode *FoundNode = 0; |
| 210 | |
Chris Lattner | ad0f78a | 2006-03-05 22:45:01 +0000 | [diff] [blame] | 211 | bool HasNoopHazards = false; |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 212 | while (!AvailableQueue->empty()) { |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 213 | SUnit *CurSUnit = AvailableQueue->pop(); |
Chris Lattner | b2d6358 | 2006-03-07 05:40:43 +0000 | [diff] [blame] | 214 | |
| 215 | // Get the node represented by this SUnit. |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 216 | FoundNode = CurSUnit->Node; |
| 217 | |
Chris Lattner | b2d6358 | 2006-03-07 05:40:43 +0000 | [diff] [blame] | 218 | // If this is a pseudo op, like copyfromreg, look to see if there is a |
| 219 | // real target node flagged to it. If so, use the target node. |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 220 | for (unsigned i = 0, e = CurSUnit->FlaggedNodes.size(); |
| 221 | FoundNode->getOpcode() < ISD::BUILTIN_OP_END && i != e; ++i) |
| 222 | FoundNode = CurSUnit->FlaggedNodes[i]; |
Chris Lattner | b2d6358 | 2006-03-07 05:40:43 +0000 | [diff] [blame] | 223 | |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 224 | HazardRecognizer::HazardType HT = HazardRec->getHazardType(FoundNode); |
Chris Lattner | ad0f78a | 2006-03-05 22:45:01 +0000 | [diff] [blame] | 225 | if (HT == HazardRecognizer::NoHazard) { |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 226 | FoundSUnit = CurSUnit; |
Chris Lattner | ad0f78a | 2006-03-05 22:45:01 +0000 | [diff] [blame] | 227 | break; |
| 228 | } |
| 229 | |
| 230 | // Remember if this is a noop hazard. |
| 231 | HasNoopHazards |= HT == HazardRecognizer::NoopHazard; |
| 232 | |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 233 | NotReady.push_back(CurSUnit); |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 234 | } |
Chris Lattner | ad0f78a | 2006-03-05 22:45:01 +0000 | [diff] [blame] | 235 | |
Chris Lattner | a5de484 | 2006-03-05 21:10:33 +0000 | [diff] [blame] | 236 | // Add the nodes that aren't ready back onto the available list. |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 237 | if (!NotReady.empty()) { |
| 238 | AvailableQueue->push_all(NotReady); |
| 239 | NotReady.clear(); |
| 240 | } |
Chris Lattner | ad0f78a | 2006-03-05 22:45:01 +0000 | [diff] [blame] | 241 | |
| 242 | // If we found a node to schedule, do it now. |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 243 | if (FoundSUnit) { |
| 244 | ScheduleNodeTopDown(FoundSUnit, CurCycle); |
| 245 | HazardRec->EmitInstruction(FoundNode); |
| 246 | FoundSUnit->isScheduled = true; |
| 247 | AvailableQueue->ScheduledNode(FoundSUnit); |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 248 | |
| 249 | // If this is a pseudo-op node, we don't want to increment the current |
| 250 | // cycle. |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 251 | if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops! |
| 252 | ++CurCycle; |
Chris Lattner | ad0f78a | 2006-03-05 22:45:01 +0000 | [diff] [blame] | 253 | } else if (!HasNoopHazards) { |
| 254 | // Otherwise, we have a pipeline stall, but no other problem, just advance |
| 255 | // the current cycle and try again. |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 256 | DOUT << "*** Advancing cycle, no work to do\n"; |
Chris Lattner | b0d21ef | 2006-03-08 04:25:59 +0000 | [diff] [blame] | 257 | HazardRec->AdvanceCycle(); |
Chris Lattner | 6cc3f0a | 2006-03-05 23:13:56 +0000 | [diff] [blame] | 258 | ++NumStalls; |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 259 | ++CurCycle; |
Chris Lattner | ad0f78a | 2006-03-05 22:45:01 +0000 | [diff] [blame] | 260 | } else { |
| 261 | // Otherwise, we have no instructions to issue and we have instructions |
| 262 | // that will fault if we don't do this right. This is the case for |
| 263 | // processors without pipeline interlocks and other cases. |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 264 | DOUT << "*** Emitting noop\n"; |
Chris Lattner | b0d21ef | 2006-03-08 04:25:59 +0000 | [diff] [blame] | 265 | HazardRec->EmitNoop(); |
Chris Lattner | 6772730 | 2006-03-05 23:59:20 +0000 | [diff] [blame] | 266 | Sequence.push_back(0); // NULL SUnit* -> noop |
Chris Lattner | 6cc3f0a | 2006-03-05 23:13:56 +0000 | [diff] [blame] | 267 | ++NumNoops; |
Chris Lattner | fc3549e | 2006-03-12 09:01:41 +0000 | [diff] [blame] | 268 | ++CurCycle; |
Chris Lattner | ad0f78a | 2006-03-05 22:45:01 +0000 | [diff] [blame] | 269 | } |
Chris Lattner | a5de484 | 2006-03-05 21:10:33 +0000 | [diff] [blame] | 270 | } |
| 271 | |
| 272 | #ifndef NDEBUG |
| 273 | // Verify that all SUnits were scheduled. |
| 274 | bool AnyNotSched = false; |
Chris Lattner | c45a59b | 2006-03-08 04:54:34 +0000 | [diff] [blame] | 275 | for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { |
Evan Cheng | 74d2fd8 | 2007-09-28 19:24:24 +0000 | [diff] [blame] | 276 | if (SUnits[i].NumPredsLeft != 0) { |
Chris Lattner | a5de484 | 2006-03-05 21:10:33 +0000 | [diff] [blame] | 277 | if (!AnyNotSched) |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 278 | cerr << "*** List scheduling failed! ***\n"; |
Chris Lattner | c45a59b | 2006-03-08 04:54:34 +0000 | [diff] [blame] | 279 | SUnits[i].dump(&DAG); |
Bill Wendling | 832171c | 2006-12-07 20:04:42 +0000 | [diff] [blame] | 280 | cerr << "has not been scheduled!\n"; |
Chris Lattner | a5de484 | 2006-03-05 21:10:33 +0000 | [diff] [blame] | 281 | AnyNotSched = true; |
| 282 | } |
| 283 | } |
| 284 | assert(!AnyNotSched); |
| 285 | #endif |
| 286 | } |
| 287 | |
Chris Lattner | e32178d | 2006-03-09 06:35:14 +0000 | [diff] [blame] | 288 | //===----------------------------------------------------------------------===// |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 289 | // LatencyPriorityQueue Implementation |
| 290 | //===----------------------------------------------------------------------===// |
| 291 | // |
| 292 | // This is a SchedulingPriorityQueue that schedules using latency information to |
| 293 | // reduce the length of the critical path through the basic block. |
| 294 | // |
| 295 | namespace { |
| 296 | class LatencyPriorityQueue; |
| 297 | |
| 298 | /// Sorting functions for the Available queue. |
| 299 | struct latency_sort : public std::binary_function<SUnit*, SUnit*, bool> { |
| 300 | LatencyPriorityQueue *PQ; |
| 301 | latency_sort(LatencyPriorityQueue *pq) : PQ(pq) {} |
| 302 | latency_sort(const latency_sort &RHS) : PQ(RHS.PQ) {} |
| 303 | |
| 304 | bool operator()(const SUnit* left, const SUnit* right) const; |
| 305 | }; |
| 306 | } // end anonymous namespace |
| 307 | |
| 308 | namespace { |
| 309 | class LatencyPriorityQueue : public SchedulingPriorityQueue { |
| 310 | // SUnits - The SUnits for the current graph. |
Chris Lattner | 228a18e | 2006-08-17 00:09:56 +0000 | [diff] [blame] | 311 | std::vector<SUnit> *SUnits; |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 312 | |
| 313 | // Latencies - The latency (max of latency from this node to the bb exit) |
| 314 | // for each node. |
| 315 | std::vector<int> Latencies; |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 316 | |
| 317 | /// NumNodesSolelyBlocking - This vector contains, for every node in the |
| 318 | /// Queue, the number of nodes that the node is the sole unscheduled |
| 319 | /// predecessor for. This is used as a tie-breaker heuristic for better |
| 320 | /// mobility. |
| 321 | std::vector<unsigned> NumNodesSolelyBlocking; |
| 322 | |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 323 | std::priority_queue<SUnit*, std::vector<SUnit*>, latency_sort> Queue; |
| 324 | public: |
| 325 | LatencyPriorityQueue() : Queue(latency_sort(this)) { |
| 326 | } |
| 327 | |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 328 | void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap, |
Evan Cheng | 95f6ede | 2006-11-04 09:44:31 +0000 | [diff] [blame] | 329 | std::vector<SUnit> &sunits) { |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 330 | SUnits = &sunits; |
| 331 | // Calculate node priorities. |
| 332 | CalculatePriorities(); |
| 333 | } |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 334 | |
| 335 | void addNode(const SUnit *SU) { |
| 336 | Latencies.resize(SUnits->size(), -1); |
| 337 | NumNodesSolelyBlocking.resize(SUnits->size(), 0); |
| 338 | CalcLatency(*SU); |
| 339 | } |
| 340 | |
| 341 | void updateNode(const SUnit *SU) { |
| 342 | Latencies[SU->NodeNum] = -1; |
| 343 | CalcLatency(*SU); |
| 344 | } |
| 345 | |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 346 | void releaseState() { |
| 347 | SUnits = 0; |
| 348 | Latencies.clear(); |
| 349 | } |
| 350 | |
| 351 | unsigned getLatency(unsigned NodeNum) const { |
| 352 | assert(NodeNum < Latencies.size()); |
| 353 | return Latencies[NodeNum]; |
| 354 | } |
| 355 | |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 356 | unsigned getNumSolelyBlockNodes(unsigned NodeNum) const { |
| 357 | assert(NodeNum < NumNodesSolelyBlocking.size()); |
| 358 | return NumNodesSolelyBlocking[NodeNum]; |
| 359 | } |
| 360 | |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 361 | unsigned size() const { return Queue.size(); } |
| 362 | |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 363 | bool empty() const { return Queue.empty(); } |
| 364 | |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 365 | virtual void push(SUnit *U) { |
| 366 | push_impl(U); |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 367 | } |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 368 | void push_impl(SUnit *U); |
| 369 | |
Chris Lattner | f83a47d | 2006-03-10 04:32:49 +0000 | [diff] [blame] | 370 | void push_all(const std::vector<SUnit *> &Nodes) { |
| 371 | for (unsigned i = 0, e = Nodes.size(); i != e; ++i) |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 372 | push_impl(Nodes[i]); |
Chris Lattner | f83a47d | 2006-03-10 04:32:49 +0000 | [diff] [blame] | 373 | } |
| 374 | |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 375 | SUnit *pop() { |
Evan Cheng | 19564e3 | 2006-05-30 18:04:34 +0000 | [diff] [blame] | 376 | if (empty()) return NULL; |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 377 | SUnit *V = Queue.top(); |
| 378 | Queue.pop(); |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 379 | return V; |
| 380 | } |
Evan Cheng | b63b067 | 2006-05-09 07:13:34 +0000 | [diff] [blame] | 381 | |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 382 | /// remove - This is a really inefficient way to remove a node from a |
| 383 | /// priority queue. We should roll our own heap to make this better or |
| 384 | /// something. |
| 385 | void remove(SUnit *SU) { |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 386 | std::vector<SUnit*> Temp; |
| 387 | |
| 388 | assert(!Queue.empty() && "Not in queue!"); |
| 389 | while (Queue.top() != SU) { |
| 390 | Temp.push_back(Queue.top()); |
| 391 | Queue.pop(); |
| 392 | assert(!Queue.empty() && "Not in queue!"); |
| 393 | } |
| 394 | |
| 395 | // Remove the node from the PQ. |
| 396 | Queue.pop(); |
| 397 | |
| 398 | // Add all the other nodes back. |
| 399 | for (unsigned i = 0, e = Temp.size(); i != e; ++i) |
| 400 | Queue.push(Temp[i]); |
| 401 | } |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 402 | |
| 403 | // ScheduledNode - As nodes are scheduled, we look to see if there are any |
| 404 | // successor nodes that have a single unscheduled predecessor. If so, that |
| 405 | // single predecessor has a higher priority, since scheduling it will make |
| 406 | // the node available. |
| 407 | void ScheduledNode(SUnit *Node); |
| 408 | |
| 409 | private: |
| 410 | void CalculatePriorities(); |
| 411 | int CalcLatency(const SUnit &SU); |
| 412 | void AdjustPriorityOfUnscheduledPreds(SUnit *SU); |
| 413 | SUnit *getSingleUnscheduledPred(SUnit *SU); |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 414 | }; |
| 415 | } |
| 416 | |
| 417 | bool latency_sort::operator()(const SUnit *LHS, const SUnit *RHS) const { |
| 418 | unsigned LHSNum = LHS->NodeNum; |
| 419 | unsigned RHSNum = RHS->NodeNum; |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 420 | |
| 421 | // The most important heuristic is scheduling the critical path. |
| 422 | unsigned LHSLatency = PQ->getLatency(LHSNum); |
| 423 | unsigned RHSLatency = PQ->getLatency(RHSNum); |
| 424 | if (LHSLatency < RHSLatency) return true; |
| 425 | if (LHSLatency > RHSLatency) return false; |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 426 | |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 427 | // After that, if two nodes have identical latencies, look to see if one will |
| 428 | // unblock more other nodes than the other. |
| 429 | unsigned LHSBlocked = PQ->getNumSolelyBlockNodes(LHSNum); |
| 430 | unsigned RHSBlocked = PQ->getNumSolelyBlockNodes(RHSNum); |
| 431 | if (LHSBlocked < RHSBlocked) return true; |
| 432 | if (LHSBlocked > RHSBlocked) return false; |
| 433 | |
| 434 | // Finally, just to provide a stable ordering, use the node number as a |
| 435 | // deciding factor. |
| 436 | return LHSNum < RHSNum; |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 437 | } |
| 438 | |
| 439 | |
| 440 | /// CalcNodePriority - Calculate the maximal path from the node to the exit. |
| 441 | /// |
| 442 | int LatencyPriorityQueue::CalcLatency(const SUnit &SU) { |
| 443 | int &Latency = Latencies[SU.NodeNum]; |
| 444 | if (Latency != -1) |
| 445 | return Latency; |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 446 | |
Evan Cheng | 4859e27 | 2007-10-15 21:33:22 +0000 | [diff] [blame] | 447 | std::vector<const SUnit*> WorkList; |
| 448 | WorkList.push_back(&SU); |
| 449 | while (!WorkList.empty()) { |
| 450 | const SUnit *Cur = WorkList.back(); |
| 451 | bool AllDone = true; |
| 452 | int MaxSuccLatency = 0; |
| 453 | for (SUnit::const_succ_iterator I = Cur->Succs.begin(),E = Cur->Succs.end(); |
| 454 | I != E; ++I) { |
| 455 | int SuccLatency = Latencies[I->Dep->NodeNum]; |
| 456 | if (SuccLatency == -1) { |
| 457 | AllDone = false; |
| 458 | WorkList.push_back(I->Dep); |
| 459 | } else { |
| 460 | MaxSuccLatency = std::max(MaxSuccLatency, SuccLatency); |
| 461 | } |
| 462 | } |
| 463 | if (AllDone) { |
| 464 | Latencies[Cur->NodeNum] = MaxSuccLatency + Cur->Latency; |
| 465 | WorkList.pop_back(); |
| 466 | } |
| 467 | } |
| 468 | |
| 469 | return Latency; |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 470 | } |
| 471 | |
| 472 | /// CalculatePriorities - Calculate priorities of all scheduling units. |
| 473 | void LatencyPriorityQueue::CalculatePriorities() { |
| 474 | Latencies.assign(SUnits->size(), -1); |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 475 | NumNodesSolelyBlocking.assign(SUnits->size(), 0); |
Evan Cheng | 4859e27 | 2007-10-15 21:33:22 +0000 | [diff] [blame] | 476 | |
| 477 | // For each node, calculate the maximal path from the node to the exit. |
| 478 | std::vector<std::pair<const SUnit*, unsigned> > WorkList; |
| 479 | for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { |
| 480 | const SUnit *SU = &(*SUnits)[i]; |
| 481 | if (SU->Succs.size() == 0) |
| 482 | WorkList.push_back(std::make_pair(SU, 0U)); |
| 483 | } |
| 484 | |
| 485 | while (!WorkList.empty()) { |
| 486 | const SUnit *SU = WorkList.back().first; |
| 487 | unsigned SuccLat = WorkList.back().second; |
| 488 | WorkList.pop_back(); |
| 489 | int &Latency = Latencies[SU->NodeNum]; |
| 490 | if (Latency == -1 || (SU->Latency + SuccLat) > (unsigned)Latency) { |
| 491 | Latency = SU->Latency + SuccLat; |
| 492 | for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end(); |
| 493 | I != E; ++I) |
| 494 | WorkList.push_back(std::make_pair(I->Dep, Latency)); |
| 495 | } |
| 496 | } |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 497 | } |
| 498 | |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 499 | /// getSingleUnscheduledPred - If there is exactly one unscheduled predecessor |
| 500 | /// of SU, return it, otherwise return null. |
Chris Lattner | 228a18e | 2006-08-17 00:09:56 +0000 | [diff] [blame] | 501 | SUnit *LatencyPriorityQueue::getSingleUnscheduledPred(SUnit *SU) { |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 502 | SUnit *OnlyAvailablePred = 0; |
Chris Lattner | 228a18e | 2006-08-17 00:09:56 +0000 | [diff] [blame] | 503 | for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); |
| 504 | I != E; ++I) { |
Evan Cheng | 713a98d | 2007-09-19 01:38:40 +0000 | [diff] [blame] | 505 | SUnit &Pred = *I->Dep; |
Chris Lattner | 228a18e | 2006-08-17 00:09:56 +0000 | [diff] [blame] | 506 | if (!Pred.isScheduled) { |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 507 | // We found an available, but not scheduled, predecessor. If it's the |
| 508 | // only one we have found, keep track of it... otherwise give up. |
Chris Lattner | 228a18e | 2006-08-17 00:09:56 +0000 | [diff] [blame] | 509 | if (OnlyAvailablePred && OnlyAvailablePred != &Pred) |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 510 | return 0; |
Chris Lattner | 228a18e | 2006-08-17 00:09:56 +0000 | [diff] [blame] | 511 | OnlyAvailablePred = &Pred; |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 512 | } |
Chris Lattner | 228a18e | 2006-08-17 00:09:56 +0000 | [diff] [blame] | 513 | } |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 514 | |
| 515 | return OnlyAvailablePred; |
| 516 | } |
| 517 | |
| 518 | void LatencyPriorityQueue::push_impl(SUnit *SU) { |
| 519 | // Look at all of the successors of this node. Count the number of nodes that |
| 520 | // this node is the sole unscheduled node for. |
| 521 | unsigned NumNodesBlocking = 0; |
Chris Lattner | 228a18e | 2006-08-17 00:09:56 +0000 | [diff] [blame] | 522 | for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); |
| 523 | I != E; ++I) |
Evan Cheng | 713a98d | 2007-09-19 01:38:40 +0000 | [diff] [blame] | 524 | if (getSingleUnscheduledPred(I->Dep) == SU) |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 525 | ++NumNodesBlocking; |
Chris Lattner | 309cf8a | 2006-03-11 22:24:20 +0000 | [diff] [blame] | 526 | NumNodesSolelyBlocking[SU->NodeNum] = NumNodesBlocking; |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 527 | |
| 528 | Queue.push(SU); |
| 529 | } |
| 530 | |
| 531 | |
| 532 | // ScheduledNode - As nodes are scheduled, we look to see if there are any |
| 533 | // successor nodes that have a single unscheduled predecessor. If so, that |
| 534 | // single predecessor has a higher priority, since scheduling it will make |
| 535 | // the node available. |
| 536 | void LatencyPriorityQueue::ScheduledNode(SUnit *SU) { |
Chris Lattner | 228a18e | 2006-08-17 00:09:56 +0000 | [diff] [blame] | 537 | for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); |
| 538 | I != E; ++I) |
Evan Cheng | 713a98d | 2007-09-19 01:38:40 +0000 | [diff] [blame] | 539 | AdjustPriorityOfUnscheduledPreds(I->Dep); |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 540 | } |
| 541 | |
| 542 | /// AdjustPriorityOfUnscheduledPreds - One of the predecessors of SU was just |
| 543 | /// scheduled. If SU is not itself available, then there is at least one |
| 544 | /// predecessor node that has not been scheduled yet. If SU has exactly ONE |
| 545 | /// unscheduled predecessor, we want to increase its priority: it getting |
| 546 | /// scheduled will make this node available, so it is better than some other |
| 547 | /// node of the same priority that will not make a node available. |
| 548 | void LatencyPriorityQueue::AdjustPriorityOfUnscheduledPreds(SUnit *SU) { |
Chris Lattner | 53fbf2a | 2006-03-12 00:38:57 +0000 | [diff] [blame] | 549 | if (SU->isPending) return; // All preds scheduled. |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 550 | |
| 551 | SUnit *OnlyAvailablePred = getSingleUnscheduledPred(SU); |
| 552 | if (OnlyAvailablePred == 0 || !OnlyAvailablePred->isAvailable) return; |
| 553 | |
| 554 | // Okay, we found a single predecessor that is available, but not scheduled. |
| 555 | // Since it is available, it must be in the priority queue. First remove it. |
Evan Cheng | a6fb1b6 | 2007-09-25 01:54:36 +0000 | [diff] [blame] | 556 | remove(OnlyAvailablePred); |
Chris Lattner | da4ff69 | 2006-03-10 05:51:05 +0000 | [diff] [blame] | 557 | |
| 558 | // Reinsert the node into the priority queue, which recomputes its |
| 559 | // NumNodesSolelyBlocking value. |
| 560 | push(OnlyAvailablePred); |
| 561 | } |
| 562 | |
Chris Lattner | e32178d | 2006-03-09 06:35:14 +0000 | [diff] [blame] | 563 | |
| 564 | //===----------------------------------------------------------------------===// |
| 565 | // Public Constructor Functions |
| 566 | //===----------------------------------------------------------------------===// |
| 567 | |
Jim Laskey | 13ec702 | 2006-08-01 14:21:23 +0000 | [diff] [blame] | 568 | /// createTDListDAGScheduler - This creates a top-down list scheduler with a |
| 569 | /// new hazard recognizer. This scheduler takes ownership of the hazard |
| 570 | /// recognizer and deletes it when done. |
Jim Laskey | 9ff542f | 2006-08-01 18:29:48 +0000 | [diff] [blame] | 571 | ScheduleDAG* llvm::createTDListDAGScheduler(SelectionDAGISel *IS, |
| 572 | SelectionDAG *DAG, |
Jim Laskey | 13ec702 | 2006-08-01 14:21:23 +0000 | [diff] [blame] | 573 | MachineBasicBlock *BB) { |
| 574 | return new ScheduleDAGList(*DAG, BB, DAG->getTarget(), |
Chris Lattner | 6a4b70b | 2006-03-09 07:38:27 +0000 | [diff] [blame] | 575 | new LatencyPriorityQueue(), |
Jim Laskey | 9ff542f | 2006-08-01 18:29:48 +0000 | [diff] [blame] | 576 | IS->CreateTargetHazardRecognizer()); |
Evan Cheng | f0f9c90 | 2006-01-23 08:26:10 +0000 | [diff] [blame] | 577 | } |