]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===----- ScheduleDAGFast.cpp - Fast poor list scheduler -----------------===// |
2 | // | |
3 | // The LLVM Compiler Infrastructure | |
4 | // | |
5 | // This file is distributed under the University of Illinois Open Source | |
6 | // License. See LICENSE.TXT for details. | |
7 | // | |
8 | //===----------------------------------------------------------------------===// | |
9 | // | |
10 | // This implements a fast scheduler. | |
11 | // | |
12 | //===----------------------------------------------------------------------===// | |
13 | ||
223e47cc | 14 | #include "llvm/CodeGen/SchedulerRegistry.h" |
970d7e83 LB |
15 | #include "InstrEmitter.h" |
16 | #include "ScheduleDAGSDNodes.h" | |
17 | #include "llvm/ADT/STLExtras.h" | |
223e47cc LB |
18 | #include "llvm/ADT/SmallSet.h" |
19 | #include "llvm/ADT/Statistic.h" | |
970d7e83 LB |
20 | #include "llvm/CodeGen/SelectionDAGISel.h" |
21 | #include "llvm/IR/DataLayout.h" | |
22 | #include "llvm/IR/InlineAsm.h" | |
23 | #include "llvm/Support/Debug.h" | |
223e47cc LB |
24 | #include "llvm/Support/ErrorHandling.h" |
25 | #include "llvm/Support/raw_ostream.h" | |
970d7e83 LB |
26 | #include "llvm/Target/TargetInstrInfo.h" |
27 | #include "llvm/Target/TargetRegisterInfo.h" | |
223e47cc LB |
28 | using namespace llvm; |
29 | ||
1a4d82fc JJ |
30 | #define DEBUG_TYPE "pre-RA-sched" |
31 | ||
223e47cc LB |
32 | STATISTIC(NumUnfolds, "Number of nodes unfolded"); |
33 | STATISTIC(NumDups, "Number of duplicated nodes"); | |
34 | STATISTIC(NumPRCopies, "Number of physical copies"); | |
35 | ||
36 | static RegisterScheduler | |
37 | fastDAGScheduler("fast", "Fast suboptimal list scheduling", | |
38 | createFastDAGScheduler); | |
970d7e83 LB |
39 | static RegisterScheduler |
40 | linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling", | |
41 | createDAGLinearizer); | |
42 | ||
223e47cc LB |
43 | |
44 | namespace { | |
45 | /// FastPriorityQueue - A degenerate priority queue that considers | |
46 | /// all nodes to have the same priority. | |
47 | /// | |
48 | struct FastPriorityQueue { | |
49 | SmallVector<SUnit *, 16> Queue; | |
50 | ||
51 | bool empty() const { return Queue.empty(); } | |
52 | ||
53 | void push(SUnit *U) { | |
54 | Queue.push_back(U); | |
55 | } | |
56 | ||
57 | SUnit *pop() { | |
1a4d82fc | 58 | if (empty()) return nullptr; |
223e47cc LB |
59 | SUnit *V = Queue.back(); |
60 | Queue.pop_back(); | |
61 | return V; | |
62 | } | |
63 | }; | |
64 | ||
65 | //===----------------------------------------------------------------------===// | |
66 | /// ScheduleDAGFast - The actual "fast" list scheduler implementation. | |
67 | /// | |
68 | class ScheduleDAGFast : public ScheduleDAGSDNodes { | |
69 | private: | |
70 | /// AvailableQueue - The priority queue to use for the available SUnits. | |
71 | FastPriorityQueue AvailableQueue; | |
72 | ||
73 | /// LiveRegDefs - A set of physical registers and their definition | |
74 | /// that are "live". These nodes must be scheduled before any other nodes that | |
75 | /// modifies the registers can be scheduled. | |
76 | unsigned NumLiveRegs; | |
77 | std::vector<SUnit*> LiveRegDefs; | |
78 | std::vector<unsigned> LiveRegCycles; | |
79 | ||
80 | public: | |
81 | ScheduleDAGFast(MachineFunction &mf) | |
82 | : ScheduleDAGSDNodes(mf) {} | |
83 | ||
1a4d82fc | 84 | void Schedule() override; |
223e47cc LB |
85 | |
86 | /// AddPred - adds a predecessor edge to SUnit SU. | |
87 | /// This returns true if this is a new predecessor. | |
88 | void AddPred(SUnit *SU, const SDep &D) { | |
89 | SU->addPred(D); | |
90 | } | |
91 | ||
92 | /// RemovePred - removes a predecessor edge from SUnit SU. | |
93 | /// This returns true if an edge was removed. | |
94 | void RemovePred(SUnit *SU, const SDep &D) { | |
95 | SU->removePred(D); | |
96 | } | |
97 | ||
98 | private: | |
99 | void ReleasePred(SUnit *SU, SDep *PredEdge); | |
100 | void ReleasePredecessors(SUnit *SU, unsigned CurCycle); | |
101 | void ScheduleNodeBottomUp(SUnit*, unsigned); | |
102 | SUnit *CopyAndMoveSuccessors(SUnit*); | |
103 | void InsertCopiesAndMoveSuccs(SUnit*, unsigned, | |
104 | const TargetRegisterClass*, | |
105 | const TargetRegisterClass*, | |
1a4d82fc JJ |
106 | SmallVectorImpl<SUnit*>&); |
107 | bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl<unsigned>&); | |
223e47cc LB |
108 | void ListScheduleBottomUp(); |
109 | ||
110 | /// forceUnitLatencies - The fast scheduler doesn't care about real latencies. | |
1a4d82fc | 111 | bool forceUnitLatencies() const override { return true; } |
223e47cc LB |
112 | }; |
113 | } // end anonymous namespace | |
114 | ||
115 | ||
116 | /// Schedule - Schedule the DAG using list scheduling. | |
117 | void ScheduleDAGFast::Schedule() { | |
118 | DEBUG(dbgs() << "********** List Scheduling **********\n"); | |
119 | ||
120 | NumLiveRegs = 0; | |
1a4d82fc | 121 | LiveRegDefs.resize(TRI->getNumRegs(), nullptr); |
223e47cc LB |
122 | LiveRegCycles.resize(TRI->getNumRegs(), 0); |
123 | ||
124 | // Build the scheduling graph. | |
1a4d82fc | 125 | BuildSchedGraph(nullptr); |
223e47cc LB |
126 | |
127 | DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) | |
128 | SUnits[su].dumpAll(this)); | |
129 | ||
130 | // Execute the actual scheduling loop. | |
131 | ListScheduleBottomUp(); | |
132 | } | |
133 | ||
134 | //===----------------------------------------------------------------------===// | |
135 | // Bottom-Up Scheduling | |
136 | //===----------------------------------------------------------------------===// | |
137 | ||
138 | /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to | |
139 | /// the AvailableQueue if the count reaches zero. Also update its cycle bound. | |
140 | void ScheduleDAGFast::ReleasePred(SUnit *SU, SDep *PredEdge) { | |
141 | SUnit *PredSU = PredEdge->getSUnit(); | |
142 | ||
143 | #ifndef NDEBUG | |
144 | if (PredSU->NumSuccsLeft == 0) { | |
145 | dbgs() << "*** Scheduling failed! ***\n"; | |
146 | PredSU->dump(this); | |
147 | dbgs() << " has been released too many times!\n"; | |
1a4d82fc | 148 | llvm_unreachable(nullptr); |
223e47cc LB |
149 | } |
150 | #endif | |
151 | --PredSU->NumSuccsLeft; | |
152 | ||
153 | // If all the node's successors are scheduled, this node is ready | |
154 | // to be scheduled. Ignore the special EntrySU node. | |
155 | if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) { | |
156 | PredSU->isAvailable = true; | |
157 | AvailableQueue.push(PredSU); | |
158 | } | |
159 | } | |
160 | ||
161 | void ScheduleDAGFast::ReleasePredecessors(SUnit *SU, unsigned CurCycle) { | |
162 | // Bottom up: release predecessors | |
163 | for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); | |
164 | I != E; ++I) { | |
165 | ReleasePred(SU, &*I); | |
166 | if (I->isAssignedRegDep()) { | |
167 | // This is a physical register dependency and it's impossible or | |
168 | // expensive to copy the register. Make sure nothing that can | |
169 | // clobber the register is scheduled between the predecessor and | |
170 | // this node. | |
171 | if (!LiveRegDefs[I->getReg()]) { | |
172 | ++NumLiveRegs; | |
173 | LiveRegDefs[I->getReg()] = I->getSUnit(); | |
174 | LiveRegCycles[I->getReg()] = CurCycle; | |
175 | } | |
176 | } | |
177 | } | |
178 | } | |
179 | ||
180 | /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending | |
181 | /// count of its predecessors. If a predecessor pending count is zero, add it to | |
182 | /// the Available queue. | |
183 | void ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { | |
184 | DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); | |
185 | DEBUG(SU->dump(this)); | |
186 | ||
187 | assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!"); | |
188 | SU->setHeightToAtLeast(CurCycle); | |
189 | Sequence.push_back(SU); | |
190 | ||
191 | ReleasePredecessors(SU, CurCycle); | |
192 | ||
193 | // Release all the implicit physical register defs that are live. | |
194 | for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); | |
195 | I != E; ++I) { | |
196 | if (I->isAssignedRegDep()) { | |
197 | if (LiveRegCycles[I->getReg()] == I->getSUnit()->getHeight()) { | |
198 | assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!"); | |
199 | assert(LiveRegDefs[I->getReg()] == SU && | |
200 | "Physical register dependency violated?"); | |
201 | --NumLiveRegs; | |
1a4d82fc | 202 | LiveRegDefs[I->getReg()] = nullptr; |
223e47cc LB |
203 | LiveRegCycles[I->getReg()] = 0; |
204 | } | |
205 | } | |
206 | } | |
207 | ||
208 | SU->isScheduled = true; | |
209 | } | |
210 | ||
211 | /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled | |
212 | /// successors to the newly created node. | |
213 | SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) { | |
214 | if (SU->getNode()->getGluedNode()) | |
1a4d82fc | 215 | return nullptr; |
223e47cc LB |
216 | |
217 | SDNode *N = SU->getNode(); | |
218 | if (!N) | |
1a4d82fc | 219 | return nullptr; |
223e47cc LB |
220 | |
221 | SUnit *NewSU; | |
222 | bool TryUnfold = false; | |
223 | for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { | |
85aaf69f | 224 | MVT VT = N->getSimpleValueType(i); |
223e47cc | 225 | if (VT == MVT::Glue) |
1a4d82fc | 226 | return nullptr; |
223e47cc LB |
227 | else if (VT == MVT::Other) |
228 | TryUnfold = true; | |
229 | } | |
230 | for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { | |
231 | const SDValue &Op = N->getOperand(i); | |
85aaf69f | 232 | MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo()); |
223e47cc | 233 | if (VT == MVT::Glue) |
1a4d82fc | 234 | return nullptr; |
223e47cc LB |
235 | } |
236 | ||
237 | if (TryUnfold) { | |
238 | SmallVector<SDNode*, 2> NewNodes; | |
239 | if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes)) | |
1a4d82fc | 240 | return nullptr; |
223e47cc LB |
241 | |
242 | DEBUG(dbgs() << "Unfolding SU # " << SU->NodeNum << "\n"); | |
243 | assert(NewNodes.size() == 2 && "Expected a load folding node!"); | |
244 | ||
245 | N = NewNodes[1]; | |
246 | SDNode *LoadNode = NewNodes[0]; | |
247 | unsigned NumVals = N->getNumValues(); | |
248 | unsigned OldNumVals = SU->getNode()->getNumValues(); | |
249 | for (unsigned i = 0; i != NumVals; ++i) | |
250 | DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i)); | |
251 | DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1), | |
252 | SDValue(LoadNode, 1)); | |
253 | ||
254 | SUnit *NewSU = newSUnit(N); | |
255 | assert(N->getNodeId() == -1 && "Node already inserted!"); | |
256 | N->setNodeId(NewSU->NodeNum); | |
257 | ||
258 | const MCInstrDesc &MCID = TII->get(N->getMachineOpcode()); | |
259 | for (unsigned i = 0; i != MCID.getNumOperands(); ++i) { | |
260 | if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) { | |
261 | NewSU->isTwoAddress = true; | |
262 | break; | |
263 | } | |
264 | } | |
265 | if (MCID.isCommutable()) | |
266 | NewSU->isCommutable = true; | |
267 | ||
268 | // LoadNode may already exist. This can happen when there is another | |
269 | // load from the same location and producing the same type of value | |
270 | // but it has different alignment or volatileness. | |
271 | bool isNewLoad = true; | |
272 | SUnit *LoadSU; | |
273 | if (LoadNode->getNodeId() != -1) { | |
274 | LoadSU = &SUnits[LoadNode->getNodeId()]; | |
275 | isNewLoad = false; | |
276 | } else { | |
277 | LoadSU = newSUnit(LoadNode); | |
278 | LoadNode->setNodeId(LoadSU->NodeNum); | |
279 | } | |
280 | ||
281 | SDep ChainPred; | |
282 | SmallVector<SDep, 4> ChainSuccs; | |
283 | SmallVector<SDep, 4> LoadPreds; | |
284 | SmallVector<SDep, 4> NodePreds; | |
285 | SmallVector<SDep, 4> NodeSuccs; | |
286 | for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); | |
287 | I != E; ++I) { | |
288 | if (I->isCtrl()) | |
289 | ChainPred = *I; | |
290 | else if (I->getSUnit()->getNode() && | |
291 | I->getSUnit()->getNode()->isOperandOf(LoadNode)) | |
292 | LoadPreds.push_back(*I); | |
293 | else | |
294 | NodePreds.push_back(*I); | |
295 | } | |
296 | for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); | |
297 | I != E; ++I) { | |
298 | if (I->isCtrl()) | |
299 | ChainSuccs.push_back(*I); | |
300 | else | |
301 | NodeSuccs.push_back(*I); | |
302 | } | |
303 | ||
304 | if (ChainPred.getSUnit()) { | |
305 | RemovePred(SU, ChainPred); | |
306 | if (isNewLoad) | |
307 | AddPred(LoadSU, ChainPred); | |
308 | } | |
309 | for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) { | |
310 | const SDep &Pred = LoadPreds[i]; | |
311 | RemovePred(SU, Pred); | |
312 | if (isNewLoad) { | |
313 | AddPred(LoadSU, Pred); | |
314 | } | |
315 | } | |
316 | for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) { | |
317 | const SDep &Pred = NodePreds[i]; | |
318 | RemovePred(SU, Pred); | |
319 | AddPred(NewSU, Pred); | |
320 | } | |
321 | for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) { | |
322 | SDep D = NodeSuccs[i]; | |
323 | SUnit *SuccDep = D.getSUnit(); | |
324 | D.setSUnit(SU); | |
325 | RemovePred(SuccDep, D); | |
326 | D.setSUnit(NewSU); | |
327 | AddPred(SuccDep, D); | |
328 | } | |
329 | for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) { | |
330 | SDep D = ChainSuccs[i]; | |
331 | SUnit *SuccDep = D.getSUnit(); | |
332 | D.setSUnit(SU); | |
333 | RemovePred(SuccDep, D); | |
334 | if (isNewLoad) { | |
335 | D.setSUnit(LoadSU); | |
336 | AddPred(SuccDep, D); | |
337 | } | |
338 | } | |
339 | if (isNewLoad) { | |
970d7e83 LB |
340 | SDep D(LoadSU, SDep::Barrier); |
341 | D.setLatency(LoadSU->Latency); | |
342 | AddPred(NewSU, D); | |
223e47cc LB |
343 | } |
344 | ||
345 | ++NumUnfolds; | |
346 | ||
347 | if (NewSU->NumSuccsLeft == 0) { | |
348 | NewSU->isAvailable = true; | |
349 | return NewSU; | |
350 | } | |
351 | SU = NewSU; | |
352 | } | |
353 | ||
354 | DEBUG(dbgs() << "Duplicating SU # " << SU->NodeNum << "\n"); | |
355 | NewSU = Clone(SU); | |
356 | ||
357 | // New SUnit has the exact same predecessors. | |
358 | for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); | |
359 | I != E; ++I) | |
360 | if (!I->isArtificial()) | |
361 | AddPred(NewSU, *I); | |
362 | ||
363 | // Only copy scheduled successors. Cut them from old node's successor | |
364 | // list and move them over. | |
365 | SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; | |
366 | for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); | |
367 | I != E; ++I) { | |
368 | if (I->isArtificial()) | |
369 | continue; | |
370 | SUnit *SuccSU = I->getSUnit(); | |
371 | if (SuccSU->isScheduled) { | |
372 | SDep D = *I; | |
373 | D.setSUnit(NewSU); | |
374 | AddPred(SuccSU, D); | |
375 | D.setSUnit(SU); | |
376 | DelDeps.push_back(std::make_pair(SuccSU, D)); | |
377 | } | |
378 | } | |
379 | for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) | |
380 | RemovePred(DelDeps[i].first, DelDeps[i].second); | |
381 | ||
382 | ++NumDups; | |
383 | return NewSU; | |
384 | } | |
385 | ||
386 | /// InsertCopiesAndMoveSuccs - Insert register copies and move all | |
387 | /// scheduled successors of the given SUnit to the last copy. | |
388 | void ScheduleDAGFast::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg, | |
389 | const TargetRegisterClass *DestRC, | |
390 | const TargetRegisterClass *SrcRC, | |
1a4d82fc JJ |
391 | SmallVectorImpl<SUnit*> &Copies) { |
392 | SUnit *CopyFromSU = newSUnit(static_cast<SDNode *>(nullptr)); | |
223e47cc LB |
393 | CopyFromSU->CopySrcRC = SrcRC; |
394 | CopyFromSU->CopyDstRC = DestRC; | |
395 | ||
1a4d82fc | 396 | SUnit *CopyToSU = newSUnit(static_cast<SDNode *>(nullptr)); |
223e47cc LB |
397 | CopyToSU->CopySrcRC = DestRC; |
398 | CopyToSU->CopyDstRC = SrcRC; | |
399 | ||
400 | // Only copy scheduled successors. Cut them from old node's successor | |
401 | // list and move them over. | |
402 | SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; | |
403 | for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); | |
404 | I != E; ++I) { | |
405 | if (I->isArtificial()) | |
406 | continue; | |
407 | SUnit *SuccSU = I->getSUnit(); | |
408 | if (SuccSU->isScheduled) { | |
409 | SDep D = *I; | |
410 | D.setSUnit(CopyToSU); | |
411 | AddPred(SuccSU, D); | |
412 | DelDeps.push_back(std::make_pair(SuccSU, *I)); | |
413 | } | |
414 | } | |
415 | for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) { | |
416 | RemovePred(DelDeps[i].first, DelDeps[i].second); | |
417 | } | |
970d7e83 LB |
418 | SDep FromDep(SU, SDep::Data, Reg); |
419 | FromDep.setLatency(SU->Latency); | |
420 | AddPred(CopyFromSU, FromDep); | |
421 | SDep ToDep(CopyFromSU, SDep::Data, 0); | |
422 | ToDep.setLatency(CopyFromSU->Latency); | |
423 | AddPred(CopyToSU, ToDep); | |
223e47cc LB |
424 | |
425 | Copies.push_back(CopyFromSU); | |
426 | Copies.push_back(CopyToSU); | |
427 | ||
428 | ++NumPRCopies; | |
429 | } | |
430 | ||
431 | /// getPhysicalRegisterVT - Returns the ValueType of the physical register | |
432 | /// definition of the specified node. | |
433 | /// FIXME: Move to SelectionDAG? | |
85aaf69f | 434 | static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, |
223e47cc | 435 | const TargetInstrInfo *TII) { |
85aaf69f SL |
436 | unsigned NumRes; |
437 | if (N->getOpcode() == ISD::CopyFromReg) { | |
438 | // CopyFromReg has: "chain, Val, glue" so operand 1 gives the type. | |
439 | NumRes = 1; | |
440 | } else { | |
441 | const MCInstrDesc &MCID = TII->get(N->getMachineOpcode()); | |
442 | assert(MCID.ImplicitDefs && "Physical reg def must be in implicit def list!"); | |
443 | NumRes = MCID.getNumDefs(); | |
444 | for (const uint16_t *ImpDef = MCID.getImplicitDefs(); *ImpDef; ++ImpDef) { | |
445 | if (Reg == *ImpDef) | |
446 | break; | |
447 | ++NumRes; | |
448 | } | |
223e47cc | 449 | } |
85aaf69f | 450 | return N->getSimpleValueType(NumRes); |
223e47cc LB |
451 | } |
452 | ||
453 | /// CheckForLiveRegDef - Return true and update live register vector if the | |
454 | /// specified register def of the specified SUnit clobbers any "live" registers. | |
455 | static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg, | |
456 | std::vector<SUnit*> &LiveRegDefs, | |
457 | SmallSet<unsigned, 4> &RegAdded, | |
1a4d82fc | 458 | SmallVectorImpl<unsigned> &LRegs, |
223e47cc LB |
459 | const TargetRegisterInfo *TRI) { |
460 | bool Added = false; | |
461 | for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { | |
462 | if (LiveRegDefs[*AI] && LiveRegDefs[*AI] != SU) { | |
85aaf69f | 463 | if (RegAdded.insert(*AI).second) { |
223e47cc LB |
464 | LRegs.push_back(*AI); |
465 | Added = true; | |
466 | } | |
467 | } | |
468 | } | |
469 | return Added; | |
470 | } | |
471 | ||
472 | /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay | |
473 | /// scheduling of the given node to satisfy live physical register dependencies. | |
474 | /// If the specific node is the last one that's available to schedule, do | |
475 | /// whatever is necessary (i.e. backtracking or cloning) to make it possible. | |
476 | bool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU, | |
1a4d82fc | 477 | SmallVectorImpl<unsigned> &LRegs){ |
223e47cc LB |
478 | if (NumLiveRegs == 0) |
479 | return false; | |
480 | ||
481 | SmallSet<unsigned, 4> RegAdded; | |
482 | // If this node would clobber any "live" register, then it's not ready. | |
483 | for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); | |
484 | I != E; ++I) { | |
485 | if (I->isAssignedRegDep()) { | |
486 | CheckForLiveRegDef(I->getSUnit(), I->getReg(), LiveRegDefs, | |
487 | RegAdded, LRegs, TRI); | |
488 | } | |
489 | } | |
490 | ||
491 | for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode()) { | |
492 | if (Node->getOpcode() == ISD::INLINEASM) { | |
493 | // Inline asm can clobber physical defs. | |
494 | unsigned NumOps = Node->getNumOperands(); | |
495 | if (Node->getOperand(NumOps-1).getValueType() == MVT::Glue) | |
496 | --NumOps; // Ignore the glue operand. | |
497 | ||
498 | for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) { | |
499 | unsigned Flags = | |
500 | cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue(); | |
501 | unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags); | |
502 | ||
503 | ++i; // Skip the ID value. | |
504 | if (InlineAsm::isRegDefKind(Flags) || | |
505 | InlineAsm::isRegDefEarlyClobberKind(Flags) || | |
506 | InlineAsm::isClobberKind(Flags)) { | |
507 | // Check for def of register or earlyclobber register. | |
508 | for (; NumVals; --NumVals, ++i) { | |
509 | unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg(); | |
510 | if (TargetRegisterInfo::isPhysicalRegister(Reg)) | |
511 | CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI); | |
512 | } | |
513 | } else | |
514 | i += NumVals; | |
515 | } | |
516 | continue; | |
517 | } | |
518 | if (!Node->isMachineOpcode()) | |
519 | continue; | |
520 | const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode()); | |
521 | if (!MCID.ImplicitDefs) | |
522 | continue; | |
523 | for (const uint16_t *Reg = MCID.getImplicitDefs(); *Reg; ++Reg) { | |
524 | CheckForLiveRegDef(SU, *Reg, LiveRegDefs, RegAdded, LRegs, TRI); | |
525 | } | |
526 | } | |
527 | return !LRegs.empty(); | |
528 | } | |
529 | ||
530 | ||
531 | /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up | |
532 | /// schedulers. | |
533 | void ScheduleDAGFast::ListScheduleBottomUp() { | |
534 | unsigned CurCycle = 0; | |
535 | ||
536 | // Release any predecessors of the special Exit node. | |
537 | ReleasePredecessors(&ExitSU, CurCycle); | |
538 | ||
539 | // Add root to Available queue. | |
540 | if (!SUnits.empty()) { | |
541 | SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()]; | |
542 | assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!"); | |
543 | RootSU->isAvailable = true; | |
544 | AvailableQueue.push(RootSU); | |
545 | } | |
546 | ||
547 | // While Available queue is not empty, grab the node with the highest | |
548 | // priority. If it is not ready put it back. Schedule the node. | |
549 | SmallVector<SUnit*, 4> NotReady; | |
550 | DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap; | |
551 | Sequence.reserve(SUnits.size()); | |
552 | while (!AvailableQueue.empty()) { | |
553 | bool Delayed = false; | |
554 | LRegsMap.clear(); | |
555 | SUnit *CurSU = AvailableQueue.pop(); | |
556 | while (CurSU) { | |
557 | SmallVector<unsigned, 4> LRegs; | |
558 | if (!DelayForLiveRegsBottomUp(CurSU, LRegs)) | |
559 | break; | |
560 | Delayed = true; | |
561 | LRegsMap.insert(std::make_pair(CurSU, LRegs)); | |
562 | ||
563 | CurSU->isPending = true; // This SU is not in AvailableQueue right now. | |
564 | NotReady.push_back(CurSU); | |
565 | CurSU = AvailableQueue.pop(); | |
566 | } | |
567 | ||
568 | // All candidates are delayed due to live physical reg dependencies. | |
569 | // Try code duplication or inserting cross class copies | |
570 | // to resolve it. | |
571 | if (Delayed && !CurSU) { | |
572 | if (!CurSU) { | |
573 | // Try duplicating the nodes that produces these | |
574 | // "expensive to copy" values to break the dependency. In case even | |
575 | // that doesn't work, insert cross class copies. | |
576 | SUnit *TrySU = NotReady[0]; | |
1a4d82fc | 577 | SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU]; |
223e47cc LB |
578 | assert(LRegs.size() == 1 && "Can't handle this yet!"); |
579 | unsigned Reg = LRegs[0]; | |
580 | SUnit *LRDef = LiveRegDefs[Reg]; | |
85aaf69f | 581 | MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII); |
223e47cc LB |
582 | const TargetRegisterClass *RC = |
583 | TRI->getMinimalPhysRegClass(Reg, VT); | |
584 | const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC); | |
585 | ||
586 | // If cross copy register class is the same as RC, then it must be | |
587 | // possible copy the value directly. Do not try duplicate the def. | |
588 | // If cross copy register class is not the same as RC, then it's | |
589 | // possible to copy the value but it require cross register class copies | |
590 | // and it is expensive. | |
591 | // If cross copy register class is null, then it's not possible to copy | |
592 | // the value at all. | |
1a4d82fc | 593 | SUnit *NewDef = nullptr; |
223e47cc LB |
594 | if (DestRC != RC) { |
595 | NewDef = CopyAndMoveSuccessors(LRDef); | |
596 | if (!DestRC && !NewDef) | |
597 | report_fatal_error("Can't handle live physical " | |
598 | "register dependency!"); | |
599 | } | |
600 | if (!NewDef) { | |
601 | // Issue copies, these can be expensive cross register class copies. | |
602 | SmallVector<SUnit*, 2> Copies; | |
603 | InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies); | |
604 | DEBUG(dbgs() << "Adding an edge from SU # " << TrySU->NodeNum | |
605 | << " to SU #" << Copies.front()->NodeNum << "\n"); | |
970d7e83 | 606 | AddPred(TrySU, SDep(Copies.front(), SDep::Artificial)); |
223e47cc LB |
607 | NewDef = Copies.back(); |
608 | } | |
609 | ||
610 | DEBUG(dbgs() << "Adding an edge from SU # " << NewDef->NodeNum | |
611 | << " to SU #" << TrySU->NodeNum << "\n"); | |
612 | LiveRegDefs[Reg] = NewDef; | |
970d7e83 | 613 | AddPred(NewDef, SDep(TrySU, SDep::Artificial)); |
223e47cc LB |
614 | TrySU->isAvailable = false; |
615 | CurSU = NewDef; | |
616 | } | |
617 | ||
618 | if (!CurSU) { | |
619 | llvm_unreachable("Unable to resolve live physical register dependencies!"); | |
620 | } | |
621 | } | |
622 | ||
623 | // Add the nodes that aren't ready back onto the available list. | |
624 | for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { | |
625 | NotReady[i]->isPending = false; | |
626 | // May no longer be available due to backtracking. | |
627 | if (NotReady[i]->isAvailable) | |
628 | AvailableQueue.push(NotReady[i]); | |
629 | } | |
630 | NotReady.clear(); | |
631 | ||
632 | if (CurSU) | |
633 | ScheduleNodeBottomUp(CurSU, CurCycle); | |
634 | ++CurCycle; | |
635 | } | |
636 | ||
637 | // Reverse the order since it is bottom up. | |
638 | std::reverse(Sequence.begin(), Sequence.end()); | |
639 | ||
640 | #ifndef NDEBUG | |
641 | VerifyScheduledSequence(/*isBottomUp=*/true); | |
642 | #endif | |
643 | } | |
644 | ||
970d7e83 LB |
645 | |
646 | namespace { | |
647 | //===----------------------------------------------------------------------===// | |
648 | // ScheduleDAGLinearize - No scheduling scheduler, it simply linearize the | |
649 | // DAG in topological order. | |
650 | // IMPORTANT: this may not work for targets with phyreg dependency. | |
651 | // | |
652 | class ScheduleDAGLinearize : public ScheduleDAGSDNodes { | |
653 | public: | |
654 | ScheduleDAGLinearize(MachineFunction &mf) : ScheduleDAGSDNodes(mf) {} | |
655 | ||
1a4d82fc | 656 | void Schedule() override; |
970d7e83 | 657 | |
1a4d82fc JJ |
658 | MachineBasicBlock * |
659 | EmitSchedule(MachineBasicBlock::iterator &InsertPos) override; | |
970d7e83 LB |
660 | |
661 | private: | |
662 | std::vector<SDNode*> Sequence; | |
663 | DenseMap<SDNode*, SDNode*> GluedMap; // Cache glue to its user | |
664 | ||
665 | void ScheduleNode(SDNode *N); | |
666 | }; | |
667 | } // end anonymous namespace | |
668 | ||
669 | void ScheduleDAGLinearize::ScheduleNode(SDNode *N) { | |
670 | if (N->getNodeId() != 0) | |
1a4d82fc | 671 | llvm_unreachable(nullptr); |
970d7e83 LB |
672 | |
673 | if (!N->isMachineOpcode() && | |
674 | (N->getOpcode() == ISD::EntryToken || isPassiveNode(N))) | |
675 | // These nodes do not need to be translated into MIs. | |
676 | return; | |
677 | ||
678 | DEBUG(dbgs() << "\n*** Scheduling: "); | |
679 | DEBUG(N->dump(DAG)); | |
680 | Sequence.push_back(N); | |
681 | ||
682 | unsigned NumOps = N->getNumOperands(); | |
683 | if (unsigned NumLeft = NumOps) { | |
1a4d82fc | 684 | SDNode *GluedOpN = nullptr; |
970d7e83 LB |
685 | do { |
686 | const SDValue &Op = N->getOperand(NumLeft-1); | |
687 | SDNode *OpN = Op.getNode(); | |
688 | ||
689 | if (NumLeft == NumOps && Op.getValueType() == MVT::Glue) { | |
690 | // Schedule glue operand right above N. | |
691 | GluedOpN = OpN; | |
692 | assert(OpN->getNodeId() != 0 && "Glue operand not ready?"); | |
693 | OpN->setNodeId(0); | |
694 | ScheduleNode(OpN); | |
695 | continue; | |
696 | } | |
697 | ||
698 | if (OpN == GluedOpN) | |
699 | // Glue operand is already scheduled. | |
700 | continue; | |
701 | ||
702 | DenseMap<SDNode*, SDNode*>::iterator DI = GluedMap.find(OpN); | |
703 | if (DI != GluedMap.end() && DI->second != N) | |
704 | // Users of glues are counted against the glued users. | |
705 | OpN = DI->second; | |
706 | ||
707 | unsigned Degree = OpN->getNodeId(); | |
708 | assert(Degree > 0 && "Predecessor over-released!"); | |
709 | OpN->setNodeId(--Degree); | |
710 | if (Degree == 0) | |
711 | ScheduleNode(OpN); | |
712 | } while (--NumLeft); | |
713 | } | |
714 | } | |
715 | ||
716 | /// findGluedUser - Find the representative use of a glue value by walking | |
717 | /// the use chain. | |
718 | static SDNode *findGluedUser(SDNode *N) { | |
719 | while (SDNode *Glued = N->getGluedUser()) | |
720 | N = Glued; | |
721 | return N; | |
722 | } | |
723 | ||
724 | void ScheduleDAGLinearize::Schedule() { | |
725 | DEBUG(dbgs() << "********** DAG Linearization **********\n"); | |
726 | ||
727 | SmallVector<SDNode*, 8> Glues; | |
728 | unsigned DAGSize = 0; | |
729 | for (SelectionDAG::allnodes_iterator I = DAG->allnodes_begin(), | |
730 | E = DAG->allnodes_end(); I != E; ++I) { | |
731 | SDNode *N = I; | |
732 | ||
733 | // Use node id to record degree. | |
734 | unsigned Degree = N->use_size(); | |
735 | N->setNodeId(Degree); | |
736 | unsigned NumVals = N->getNumValues(); | |
737 | if (NumVals && N->getValueType(NumVals-1) == MVT::Glue && | |
738 | N->hasAnyUseOfValue(NumVals-1)) { | |
739 | SDNode *User = findGluedUser(N); | |
740 | if (User) { | |
741 | Glues.push_back(N); | |
742 | GluedMap.insert(std::make_pair(N, User)); | |
743 | } | |
744 | } | |
745 | ||
746 | if (N->isMachineOpcode() || | |
747 | (N->getOpcode() != ISD::EntryToken && !isPassiveNode(N))) | |
748 | ++DAGSize; | |
749 | } | |
750 | ||
751 | for (unsigned i = 0, e = Glues.size(); i != e; ++i) { | |
752 | SDNode *Glue = Glues[i]; | |
753 | SDNode *GUser = GluedMap[Glue]; | |
754 | unsigned Degree = Glue->getNodeId(); | |
755 | unsigned UDegree = GUser->getNodeId(); | |
756 | ||
757 | // Glue user must be scheduled together with the glue operand. So other | |
758 | // users of the glue operand must be treated as its users. | |
759 | SDNode *ImmGUser = Glue->getGluedUser(); | |
760 | for (SDNode::use_iterator ui = Glue->use_begin(), ue = Glue->use_end(); | |
761 | ui != ue; ++ui) | |
762 | if (*ui == ImmGUser) | |
763 | --Degree; | |
764 | GUser->setNodeId(UDegree + Degree); | |
765 | Glue->setNodeId(1); | |
766 | } | |
767 | ||
768 | Sequence.reserve(DAGSize); | |
769 | ScheduleNode(DAG->getRoot().getNode()); | |
770 | } | |
771 | ||
772 | MachineBasicBlock* | |
773 | ScheduleDAGLinearize::EmitSchedule(MachineBasicBlock::iterator &InsertPos) { | |
774 | InstrEmitter Emitter(BB, InsertPos); | |
775 | DenseMap<SDValue, unsigned> VRBaseMap; | |
776 | ||
777 | DEBUG({ | |
778 | dbgs() << "\n*** Final schedule ***\n"; | |
779 | }); | |
780 | ||
781 | // FIXME: Handle dbg_values. | |
782 | unsigned NumNodes = Sequence.size(); | |
783 | for (unsigned i = 0; i != NumNodes; ++i) { | |
784 | SDNode *N = Sequence[NumNodes-i-1]; | |
785 | DEBUG(N->dump(DAG)); | |
786 | Emitter.EmitNode(N, false, false, VRBaseMap); | |
787 | } | |
788 | ||
789 | DEBUG(dbgs() << '\n'); | |
790 | ||
791 | InsertPos = Emitter.getInsertPos(); | |
792 | return Emitter.getBlock(); | |
793 | } | |
794 | ||
223e47cc LB |
795 | //===----------------------------------------------------------------------===// |
796 | // Public Constructor Functions | |
797 | //===----------------------------------------------------------------------===// | |
798 | ||
799 | llvm::ScheduleDAGSDNodes * | |
800 | llvm::createFastDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { | |
801 | return new ScheduleDAGFast(*IS->MF); | |
802 | } | |
970d7e83 LB |
803 | |
804 | llvm::ScheduleDAGSDNodes * | |
805 | llvm::createDAGLinearizer(SelectionDAGISel *IS, CodeGenOpt::Level) { | |
806 | return new ScheduleDAGLinearize(*IS->MF); | |
807 | } |