Bug Summary

File:lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp
Warning:line 1417, column 11
Access to field 'isAvailable' results in a dereference of a null pointer (loaded from variable 'BtSU')

Annotated Source Code

1//===----- ScheduleDAGRRList.cpp - Reg pressure reduction 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 bottom-up and top-down register pressure reduction list
11// schedulers, using standard algorithms. The basic approach uses a priority
12// queue of available nodes to schedule. One at a time, nodes are taken from
13// the priority queue (thus in priority order), checked for legality to
14// schedule, and emitted if legal.
15//
16//===----------------------------------------------------------------------===//
17
18#include "llvm/CodeGen/SchedulerRegistry.h"
19#include "ScheduleDAGSDNodes.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/SmallSet.h"
22#include "llvm/ADT/Statistic.h"
23#include "llvm/CodeGen/MachineRegisterInfo.h"
24#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
25#include "llvm/CodeGen/SelectionDAGISel.h"
26#include "llvm/IR/DataLayout.h"
27#include "llvm/IR/InlineAsm.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/ErrorHandling.h"
30#include "llvm/Support/raw_ostream.h"
31#include "llvm/Target/TargetInstrInfo.h"
32#include "llvm/Target/TargetLowering.h"
33#include "llvm/Target/TargetRegisterInfo.h"
34#include "llvm/Target/TargetSubtargetInfo.h"
35#include <climits>
36using namespace llvm;
37
38#define DEBUG_TYPE"pre-RA-sched" "pre-RA-sched"
39
40STATISTIC(NumBacktracks, "Number of times scheduler backtracked")static llvm::Statistic NumBacktracks = {"pre-RA-sched", "NumBacktracks"
, "Number of times scheduler backtracked", {0}, false}
;
41STATISTIC(NumUnfolds, "Number of nodes unfolded")static llvm::Statistic NumUnfolds = {"pre-RA-sched", "NumUnfolds"
, "Number of nodes unfolded", {0}, false}
;
42STATISTIC(NumDups, "Number of duplicated nodes")static llvm::Statistic NumDups = {"pre-RA-sched", "NumDups", "Number of duplicated nodes"
, {0}, false}
;
43STATISTIC(NumPRCopies, "Number of physical register copies")static llvm::Statistic NumPRCopies = {"pre-RA-sched", "NumPRCopies"
, "Number of physical register copies", {0}, false}
;
44
45static RegisterScheduler
46 burrListDAGScheduler("list-burr",
47 "Bottom-up register reduction list scheduling",
48 createBURRListDAGScheduler);
49static RegisterScheduler
50 sourceListDAGScheduler("source",
51 "Similar to list-burr but schedules in source "
52 "order when possible",
53 createSourceListDAGScheduler);
54
55static RegisterScheduler
56 hybridListDAGScheduler("list-hybrid",
57 "Bottom-up register pressure aware list scheduling "
58 "which tries to balance latency and register pressure",
59 createHybridListDAGScheduler);
60
61static RegisterScheduler
62 ILPListDAGScheduler("list-ilp",
63 "Bottom-up register pressure aware list scheduling "
64 "which tries to balance ILP and register pressure",
65 createILPListDAGScheduler);
66
67static cl::opt<bool> DisableSchedCycles(
68 "disable-sched-cycles", cl::Hidden, cl::init(false),
69 cl::desc("Disable cycle-level precision during preRA scheduling"));
70
71// Temporary sched=list-ilp flags until the heuristics are robust.
72// Some options are also available under sched=list-hybrid.
73static cl::opt<bool> DisableSchedRegPressure(
74 "disable-sched-reg-pressure", cl::Hidden, cl::init(false),
75 cl::desc("Disable regpressure priority in sched=list-ilp"));
76static cl::opt<bool> DisableSchedLiveUses(
77 "disable-sched-live-uses", cl::Hidden, cl::init(true),
78 cl::desc("Disable live use priority in sched=list-ilp"));
79static cl::opt<bool> DisableSchedVRegCycle(
80 "disable-sched-vrcycle", cl::Hidden, cl::init(false),
81 cl::desc("Disable virtual register cycle interference checks"));
82static cl::opt<bool> DisableSchedPhysRegJoin(
83 "disable-sched-physreg-join", cl::Hidden, cl::init(false),
84 cl::desc("Disable physreg def-use affinity"));
85static cl::opt<bool> DisableSchedStalls(
86 "disable-sched-stalls", cl::Hidden, cl::init(true),
87 cl::desc("Disable no-stall priority in sched=list-ilp"));
88static cl::opt<bool> DisableSchedCriticalPath(
89 "disable-sched-critical-path", cl::Hidden, cl::init(false),
90 cl::desc("Disable critical path priority in sched=list-ilp"));
91static cl::opt<bool> DisableSchedHeight(
92 "disable-sched-height", cl::Hidden, cl::init(false),
93 cl::desc("Disable scheduled-height priority in sched=list-ilp"));
94static cl::opt<bool> Disable2AddrHack(
95 "disable-2addr-hack", cl::Hidden, cl::init(true),
96 cl::desc("Disable scheduler's two-address hack"));
97
98static cl::opt<int> MaxReorderWindow(
99 "max-sched-reorder", cl::Hidden, cl::init(6),
100 cl::desc("Number of instructions to allow ahead of the critical path "
101 "in sched=list-ilp"));
102
103static cl::opt<unsigned> AvgIPC(
104 "sched-avg-ipc", cl::Hidden, cl::init(1),
105 cl::desc("Average inst/cycle whan no target itinerary exists."));
106
107namespace {
108//===----------------------------------------------------------------------===//
109/// ScheduleDAGRRList - The actual register reduction list scheduler
110/// implementation. This supports both top-down and bottom-up scheduling.
111///
112class ScheduleDAGRRList : public ScheduleDAGSDNodes {
113private:
114 /// NeedLatency - True if the scheduler will make use of latency information.
115 ///
116 bool NeedLatency;
117
118 /// AvailableQueue - The priority queue to use for the available SUnits.
119 SchedulingPriorityQueue *AvailableQueue;
120
121 /// PendingQueue - This contains all of the instructions whose operands have
122 /// been issued, but their results are not ready yet (due to the latency of
123 /// the operation). Once the operands becomes available, the instruction is
124 /// added to the AvailableQueue.
125 std::vector<SUnit*> PendingQueue;
126
127 /// HazardRec - The hazard recognizer to use.
128 ScheduleHazardRecognizer *HazardRec;
129
130 /// CurCycle - The current scheduler state corresponds to this cycle.
131 unsigned CurCycle;
132
133 /// MinAvailableCycle - Cycle of the soonest available instruction.
134 unsigned MinAvailableCycle;
135
136 /// IssueCount - Count instructions issued in this cycle
137 /// Currently valid only for bottom-up scheduling.
138 unsigned IssueCount;
139
140 /// LiveRegDefs - A set of physical registers and their definition
141 /// that are "live". These nodes must be scheduled before any other nodes that
142 /// modifies the registers can be scheduled.
143 unsigned NumLiveRegs;
144 std::unique_ptr<SUnit*[]> LiveRegDefs;
145 std::unique_ptr<SUnit*[]> LiveRegGens;
146
147 // Collect interferences between physical register use/defs.
148 // Each interference is an SUnit and set of physical registers.
149 SmallVector<SUnit*, 4> Interferences;
150 typedef DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMapT;
151 LRegsMapT LRegsMap;
152
153 /// Topo - A topological ordering for SUnits which permits fast IsReachable
154 /// and similar queries.
155 ScheduleDAGTopologicalSort Topo;
156
157 // Hack to keep track of the inverse of FindCallSeqStart without more crazy
158 // DAG crawling.
159 DenseMap<SUnit*, SUnit*> CallSeqEndForStart;
160
161public:
162 ScheduleDAGRRList(MachineFunction &mf, bool needlatency,
163 SchedulingPriorityQueue *availqueue,
164 CodeGenOpt::Level OptLevel)
165 : ScheduleDAGSDNodes(mf),
166 NeedLatency(needlatency), AvailableQueue(availqueue), CurCycle(0),
167 Topo(SUnits, nullptr) {
168
169 const TargetSubtargetInfo &STI = mf.getSubtarget();
170 if (DisableSchedCycles || !NeedLatency)
171 HazardRec = new ScheduleHazardRecognizer();
172 else
173 HazardRec = STI.getInstrInfo()->CreateTargetHazardRecognizer(&STI, this);
174 }
175
176 ~ScheduleDAGRRList() override {
177 delete HazardRec;
178 delete AvailableQueue;
179 }
180
181 void Schedule() override;
182
183 ScheduleHazardRecognizer *getHazardRec() { return HazardRec; }
184
185 /// IsReachable - Checks if SU is reachable from TargetSU.
186 bool IsReachable(const SUnit *SU, const SUnit *TargetSU) {
187 return Topo.IsReachable(SU, TargetSU);
188 }
189
190 /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will
191 /// create a cycle.
192 bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
193 return Topo.WillCreateCycle(SU, TargetSU);
194 }
195
196 /// AddPred - adds a predecessor edge to SUnit SU.
197 /// This returns true if this is a new predecessor.
198 /// Updates the topological ordering if required.
199 void AddPred(SUnit *SU, const SDep &D) {
200 Topo.AddPred(SU, D.getSUnit());
201 SU->addPred(D);
202 }
203
204 /// RemovePred - removes a predecessor edge from SUnit SU.
205 /// This returns true if an edge was removed.
206 /// Updates the topological ordering if required.
207 void RemovePred(SUnit *SU, const SDep &D) {
208 Topo.RemovePred(SU, D.getSUnit());
209 SU->removePred(D);
210 }
211
212private:
213 bool isReady(SUnit *SU) {
214 return DisableSchedCycles || !AvailableQueue->hasReadyFilter() ||
215 AvailableQueue->isReady(SU);
216 }
217
218 void ReleasePred(SUnit *SU, const SDep *PredEdge);
219 void ReleasePredecessors(SUnit *SU);
220 void ReleasePending();
221 void AdvanceToCycle(unsigned NextCycle);
222 void AdvancePastStalls(SUnit *SU);
223 void EmitNode(SUnit *SU);
224 void ScheduleNodeBottomUp(SUnit*);
225 void CapturePred(SDep *PredEdge);
226 void UnscheduleNodeBottomUp(SUnit*);
227 void RestoreHazardCheckerBottomUp();
228 void BacktrackBottomUp(SUnit*, SUnit*);
229 SUnit *CopyAndMoveSuccessors(SUnit*);
230 void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
231 const TargetRegisterClass*,
232 const TargetRegisterClass*,
233 SmallVectorImpl<SUnit*>&);
234 bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl<unsigned>&);
235
236 void releaseInterferences(unsigned Reg = 0);
237
238 SUnit *PickNodeToScheduleBottomUp();
239 void ListScheduleBottomUp();
240
241 /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it.
242 /// Updates the topological ordering if required.
243 SUnit *CreateNewSUnit(SDNode *N) {
244 unsigned NumSUnits = SUnits.size();
245 SUnit *NewNode = newSUnit(N);
246 // Update the topological ordering.
247 if (NewNode->NodeNum >= NumSUnits)
248 Topo.InitDAGTopologicalSorting();
249 return NewNode;
250 }
251
252 /// CreateClone - Creates a new SUnit from an existing one.
253 /// Updates the topological ordering if required.
254 SUnit *CreateClone(SUnit *N) {
255 unsigned NumSUnits = SUnits.size();
256 SUnit *NewNode = Clone(N);
257 // Update the topological ordering.
258 if (NewNode->NodeNum >= NumSUnits)
259 Topo.InitDAGTopologicalSorting();
260 return NewNode;
261 }
262
263 /// forceUnitLatencies - Register-pressure-reducing scheduling doesn't
264 /// need actual latency information but the hybrid scheduler does.
265 bool forceUnitLatencies() const override {
266 return !NeedLatency;
267 }
268};
269} // end anonymous namespace
270
271/// GetCostForDef - Looks up the register class and cost for a given definition.
272/// Typically this just means looking up the representative register class,
273/// but for untyped values (MVT::Untyped) it means inspecting the node's
274/// opcode to determine what register class is being generated.
275static void GetCostForDef(const ScheduleDAGSDNodes::RegDefIter &RegDefPos,
276 const TargetLowering *TLI,
277 const TargetInstrInfo *TII,
278 const TargetRegisterInfo *TRI,
279 unsigned &RegClass, unsigned &Cost,
280 const MachineFunction &MF) {
281 MVT VT = RegDefPos.GetValue();
282
283 // Special handling for untyped values. These values can only come from
284 // the expansion of custom DAG-to-DAG patterns.
285 if (VT == MVT::Untyped) {
286 const SDNode *Node = RegDefPos.GetNode();
287
288 // Special handling for CopyFromReg of untyped values.
289 if (!Node->isMachineOpcode() && Node->getOpcode() == ISD::CopyFromReg) {
290 unsigned Reg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
291 const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(Reg);
292 RegClass = RC->getID();
293 Cost = 1;
294 return;
295 }
296
297 unsigned Opcode = Node->getMachineOpcode();
298 if (Opcode == TargetOpcode::REG_SEQUENCE) {
299 unsigned DstRCIdx = cast<ConstantSDNode>(Node->getOperand(0))->getZExtValue();
300 const TargetRegisterClass *RC = TRI->getRegClass(DstRCIdx);
301 RegClass = RC->getID();
302 Cost = 1;
303 return;
304 }
305
306 unsigned Idx = RegDefPos.GetIdx();
307 const MCInstrDesc Desc = TII->get(Opcode);
308 const TargetRegisterClass *RC = TII->getRegClass(Desc, Idx, TRI, MF);
309 RegClass = RC->getID();
310 // FIXME: Cost arbitrarily set to 1 because there doesn't seem to be a
311 // better way to determine it.
312 Cost = 1;
313 } else {
314 RegClass = TLI->getRepRegClassFor(VT)->getID();
315 Cost = TLI->getRepRegClassCostFor(VT);
316 }
317}
318
319/// Schedule - Schedule the DAG using list scheduling.
320void ScheduleDAGRRList::Schedule() {
321 DEBUG(dbgs()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "********** List Scheduling BB#"
<< BB->getNumber() << " '" << BB->getName
() << "' **********\n"; } } while (false)
322 << "********** List Scheduling BB#" << BB->getNumber()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "********** List Scheduling BB#"
<< BB->getNumber() << " '" << BB->getName
() << "' **********\n"; } } while (false)
323 << " '" << BB->getName() << "' **********\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "********** List Scheduling BB#"
<< BB->getNumber() << " '" << BB->getName
() << "' **********\n"; } } while (false)
;
324
325 CurCycle = 0;
326 IssueCount = 0;
327 MinAvailableCycle = DisableSchedCycles ? 0 : UINT_MAX(2147483647 *2U +1U);
328 NumLiveRegs = 0;
329 // Allocate slots for each physical register, plus one for a special register
330 // to track the virtual resource of a calling sequence.
331 LiveRegDefs.reset(new SUnit*[TRI->getNumRegs() + 1]());
332 LiveRegGens.reset(new SUnit*[TRI->getNumRegs() + 1]());
333 CallSeqEndForStart.clear();
334 assert(Interferences.empty() && LRegsMap.empty() && "stale Interferences")((Interferences.empty() && LRegsMap.empty() &&
"stale Interferences") ? static_cast<void> (0) : __assert_fail
("Interferences.empty() && LRegsMap.empty() && \"stale Interferences\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 334, __PRETTY_FUNCTION__))
;
335
336 // Build the scheduling graph.
337 BuildSchedGraph(nullptr);
338
339 DEBUG(for (SUnit &SU : SUnits)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { for (SUnit &SU : SUnits) SU.dumpAll(this
); } } while (false)
340 SU.dumpAll(this))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { for (SUnit &SU : SUnits) SU.dumpAll(this
); } } while (false)
;
341 Topo.InitDAGTopologicalSorting();
342
343 AvailableQueue->initNodes(SUnits);
344
345 HazardRec->Reset();
346
347 // Execute the actual scheduling loop.
348 ListScheduleBottomUp();
349
350 AvailableQueue->releaseState();
351
352 DEBUG({do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { { dbgs() << "*** Final schedule ***\n"
; dumpSchedule(); dbgs() << '\n'; }; } } while (false)
353 dbgs() << "*** Final schedule ***\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { { dbgs() << "*** Final schedule ***\n"
; dumpSchedule(); dbgs() << '\n'; }; } } while (false)
354 dumpSchedule();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { { dbgs() << "*** Final schedule ***\n"
; dumpSchedule(); dbgs() << '\n'; }; } } while (false)
355 dbgs() << '\n';do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { { dbgs() << "*** Final schedule ***\n"
; dumpSchedule(); dbgs() << '\n'; }; } } while (false)
356 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { { dbgs() << "*** Final schedule ***\n"
; dumpSchedule(); dbgs() << '\n'; }; } } while (false)
;
357}
358
359//===----------------------------------------------------------------------===//
360// Bottom-Up Scheduling
361//===----------------------------------------------------------------------===//
362
363/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
364/// the AvailableQueue if the count reaches zero. Also update its cycle bound.
365void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) {
366 SUnit *PredSU = PredEdge->getSUnit();
367
368#ifndef NDEBUG
369 if (PredSU->NumSuccsLeft == 0) {
370 dbgs() << "*** Scheduling failed! ***\n";
371 PredSU->dump(this);
372 dbgs() << " has been released too many times!\n";
373 llvm_unreachable(nullptr)::llvm::llvm_unreachable_internal(nullptr, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 373)
;
374 }
375#endif
376 --PredSU->NumSuccsLeft;
377
378 if (!forceUnitLatencies()) {
379 // Updating predecessor's height. This is now the cycle when the
380 // predecessor can be scheduled without causing a pipeline stall.
381 PredSU->setHeightToAtLeast(SU->getHeight() + PredEdge->getLatency());
382 }
383
384 // If all the node's successors are scheduled, this node is ready
385 // to be scheduled. Ignore the special EntrySU node.
386 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
387 PredSU->isAvailable = true;
388
389 unsigned Height = PredSU->getHeight();
390 if (Height < MinAvailableCycle)
391 MinAvailableCycle = Height;
392
393 if (isReady(PredSU)) {
394 AvailableQueue->push(PredSU);
395 }
396 // CapturePred and others may have left the node in the pending queue, avoid
397 // adding it twice.
398 else if (!PredSU->isPending) {
399 PredSU->isPending = true;
400 PendingQueue.push_back(PredSU);
401 }
402 }
403}
404
405/// IsChainDependent - Test if Outer is reachable from Inner through
406/// chain dependencies.
407static bool IsChainDependent(SDNode *Outer, SDNode *Inner,
408 unsigned NestLevel,
409 const TargetInstrInfo *TII) {
410 SDNode *N = Outer;
411 for (;;) {
412 if (N == Inner)
413 return true;
414 // For a TokenFactor, examine each operand. There may be multiple ways
415 // to get to the CALLSEQ_BEGIN, but we need to find the path with the
416 // most nesting in order to ensure that we find the corresponding match.
417 if (N->getOpcode() == ISD::TokenFactor) {
418 for (const SDValue &Op : N->op_values())
419 if (IsChainDependent(Op.getNode(), Inner, NestLevel, TII))
420 return true;
421 return false;
422 }
423 // Check for a lowered CALLSEQ_BEGIN or CALLSEQ_END.
424 if (N->isMachineOpcode()) {
425 if (N->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
426 ++NestLevel;
427 } else if (N->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {
428 if (NestLevel == 0)
429 return false;
430 --NestLevel;
431 }
432 }
433 // Otherwise, find the chain and continue climbing.
434 for (const SDValue &Op : N->op_values())
435 if (Op.getValueType() == MVT::Other) {
436 N = Op.getNode();
437 goto found_chain_operand;
438 }
439 return false;
440 found_chain_operand:;
441 if (N->getOpcode() == ISD::EntryToken)
442 return false;
443 }
444}
445
446/// FindCallSeqStart - Starting from the (lowered) CALLSEQ_END node, locate
447/// the corresponding (lowered) CALLSEQ_BEGIN node.
448///
449/// NestLevel and MaxNested are used in recursion to indcate the current level
450/// of nesting of CALLSEQ_BEGIN and CALLSEQ_END pairs, as well as the maximum
451/// level seen so far.
452///
453/// TODO: It would be better to give CALLSEQ_END an explicit operand to point
454/// to the corresponding CALLSEQ_BEGIN to avoid needing to search for it.
455static SDNode *
456FindCallSeqStart(SDNode *N, unsigned &NestLevel, unsigned &MaxNest,
457 const TargetInstrInfo *TII) {
458 for (;;) {
459 // For a TokenFactor, examine each operand. There may be multiple ways
460 // to get to the CALLSEQ_BEGIN, but we need to find the path with the
461 // most nesting in order to ensure that we find the corresponding match.
462 if (N->getOpcode() == ISD::TokenFactor) {
463 SDNode *Best = nullptr;
464 unsigned BestMaxNest = MaxNest;
465 for (const SDValue &Op : N->op_values()) {
466 unsigned MyNestLevel = NestLevel;
467 unsigned MyMaxNest = MaxNest;
468 if (SDNode *New = FindCallSeqStart(Op.getNode(),
469 MyNestLevel, MyMaxNest, TII))
470 if (!Best || (MyMaxNest > BestMaxNest)) {
471 Best = New;
472 BestMaxNest = MyMaxNest;
473 }
474 }
475 assert(Best)((Best) ? static_cast<void> (0) : __assert_fail ("Best"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 475, __PRETTY_FUNCTION__))
;
476 MaxNest = BestMaxNest;
477 return Best;
478 }
479 // Check for a lowered CALLSEQ_BEGIN or CALLSEQ_END.
480 if (N->isMachineOpcode()) {
481 if (N->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
482 ++NestLevel;
483 MaxNest = std::max(MaxNest, NestLevel);
484 } else if (N->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {
485 assert(NestLevel != 0)((NestLevel != 0) ? static_cast<void> (0) : __assert_fail
("NestLevel != 0", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 485, __PRETTY_FUNCTION__))
;
486 --NestLevel;
487 if (NestLevel == 0)
488 return N;
489 }
490 }
491 // Otherwise, find the chain and continue climbing.
492 for (const SDValue &Op : N->op_values())
493 if (Op.getValueType() == MVT::Other) {
494 N = Op.getNode();
495 goto found_chain_operand;
496 }
497 return nullptr;
498 found_chain_operand:;
499 if (N->getOpcode() == ISD::EntryToken)
500 return nullptr;
501 }
502}
503
504/// Call ReleasePred for each predecessor, then update register live def/gen.
505/// Always update LiveRegDefs for a register dependence even if the current SU
506/// also defines the register. This effectively create one large live range
507/// across a sequence of two-address node. This is important because the
508/// entire chain must be scheduled together. Example:
509///
510/// flags = (3) add
511/// flags = (2) addc flags
512/// flags = (1) addc flags
513///
514/// results in
515///
516/// LiveRegDefs[flags] = 3
517/// LiveRegGens[flags] = 1
518///
519/// If (2) addc is unscheduled, then (1) addc must also be unscheduled to avoid
520/// interference on flags.
521void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU) {
522 // Bottom up: release predecessors
523 for (SDep &Pred : SU->Preds) {
524 ReleasePred(SU, &Pred);
525 if (Pred.isAssignedRegDep()) {
526 // This is a physical register dependency and it's impossible or
527 // expensive to copy the register. Make sure nothing that can
528 // clobber the register is scheduled between the predecessor and
529 // this node.
530 SUnit *RegDef = LiveRegDefs[Pred.getReg()]; (void)RegDef;
531 assert((!RegDef || RegDef == SU || RegDef == Pred.getSUnit()) &&(((!RegDef || RegDef == SU || RegDef == Pred.getSUnit()) &&
"interference on register dependence") ? static_cast<void
> (0) : __assert_fail ("(!RegDef || RegDef == SU || RegDef == Pred.getSUnit()) && \"interference on register dependence\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 532, __PRETTY_FUNCTION__))
532 "interference on register dependence")(((!RegDef || RegDef == SU || RegDef == Pred.getSUnit()) &&
"interference on register dependence") ? static_cast<void
> (0) : __assert_fail ("(!RegDef || RegDef == SU || RegDef == Pred.getSUnit()) && \"interference on register dependence\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 532, __PRETTY_FUNCTION__))
;
533 LiveRegDefs[Pred.getReg()] = Pred.getSUnit();
534 if (!LiveRegGens[Pred.getReg()]) {
535 ++NumLiveRegs;
536 LiveRegGens[Pred.getReg()] = SU;
537 }
538 }
539 }
540
541 // If we're scheduling a lowered CALLSEQ_END, find the corresponding
542 // CALLSEQ_BEGIN. Inject an artificial physical register dependence between
543 // these nodes, to prevent other calls from being interscheduled with them.
544 unsigned CallResource = TRI->getNumRegs();
545 if (!LiveRegDefs[CallResource])
546 for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode())
547 if (Node->isMachineOpcode() &&
548 Node->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
549 unsigned NestLevel = 0;
550 unsigned MaxNest = 0;
551 SDNode *N = FindCallSeqStart(Node, NestLevel, MaxNest, TII);
552
553 SUnit *Def = &SUnits[N->getNodeId()];
554 CallSeqEndForStart[Def] = SU;
555
556 ++NumLiveRegs;
557 LiveRegDefs[CallResource] = Def;
558 LiveRegGens[CallResource] = SU;
559 break;
560 }
561}
562
563/// Check to see if any of the pending instructions are ready to issue. If
564/// so, add them to the available queue.
565void ScheduleDAGRRList::ReleasePending() {
566 if (DisableSchedCycles) {
567 assert(PendingQueue.empty() && "pending instrs not allowed in this mode")((PendingQueue.empty() && "pending instrs not allowed in this mode"
) ? static_cast<void> (0) : __assert_fail ("PendingQueue.empty() && \"pending instrs not allowed in this mode\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 567, __PRETTY_FUNCTION__))
;
568 return;
569 }
570
571 // If the available queue is empty, it is safe to reset MinAvailableCycle.
572 if (AvailableQueue->empty())
573 MinAvailableCycle = UINT_MAX(2147483647 *2U +1U);
574
575 // Check to see if any of the pending instructions are ready to issue. If
576 // so, add them to the available queue.
577 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
578 unsigned ReadyCycle = PendingQueue[i]->getHeight();
579 if (ReadyCycle < MinAvailableCycle)
580 MinAvailableCycle = ReadyCycle;
581
582 if (PendingQueue[i]->isAvailable) {
583 if (!isReady(PendingQueue[i]))
584 continue;
585 AvailableQueue->push(PendingQueue[i]);
586 }
587 PendingQueue[i]->isPending = false;
588 PendingQueue[i] = PendingQueue.back();
589 PendingQueue.pop_back();
590 --i; --e;
591 }
592}
593
594/// Move the scheduler state forward by the specified number of Cycles.
595void ScheduleDAGRRList::AdvanceToCycle(unsigned NextCycle) {
596 if (NextCycle <= CurCycle)
597 return;
598
599 IssueCount = 0;
600 AvailableQueue->setCurCycle(NextCycle);
601 if (!HazardRec->isEnabled()) {
602 // Bypass lots of virtual calls in case of long latency.
603 CurCycle = NextCycle;
604 }
605 else {
606 for (; CurCycle != NextCycle; ++CurCycle) {
607 HazardRec->RecedeCycle();
608 }
609 }
610 // FIXME: Instead of visiting the pending Q each time, set a dirty flag on the
611 // available Q to release pending nodes at least once before popping.
612 ReleasePending();
613}
614
615/// Move the scheduler state forward until the specified node's dependents are
616/// ready and can be scheduled with no resource conflicts.
617void ScheduleDAGRRList::AdvancePastStalls(SUnit *SU) {
618 if (DisableSchedCycles)
619 return;
620
621 // FIXME: Nodes such as CopyFromReg probably should not advance the current
622 // cycle. Otherwise, we can wrongly mask real stalls. If the non-machine node
623 // has predecessors the cycle will be advanced when they are scheduled.
624 // But given the crude nature of modeling latency though such nodes, we
625 // currently need to treat these nodes like real instructions.
626 // if (!SU->getNode() || !SU->getNode()->isMachineOpcode()) return;
627
628 unsigned ReadyCycle = SU->getHeight();
629
630 // Bump CurCycle to account for latency. We assume the latency of other
631 // available instructions may be hidden by the stall (not a full pipe stall).
632 // This updates the hazard recognizer's cycle before reserving resources for
633 // this instruction.
634 AdvanceToCycle(ReadyCycle);
635
636 // Calls are scheduled in their preceding cycle, so don't conflict with
637 // hazards from instructions after the call. EmitNode will reset the
638 // scoreboard state before emitting the call.
639 if (SU->isCall)
640 return;
641
642 // FIXME: For resource conflicts in very long non-pipelined stages, we
643 // should probably skip ahead here to avoid useless scoreboard checks.
644 int Stalls = 0;
645 while (true) {
646 ScheduleHazardRecognizer::HazardType HT =
647 HazardRec->getHazardType(SU, -Stalls);
648
649 if (HT == ScheduleHazardRecognizer::NoHazard)
650 break;
651
652 ++Stalls;
653 }
654 AdvanceToCycle(CurCycle + Stalls);
655}
656
657/// Record this SUnit in the HazardRecognizer.
658/// Does not update CurCycle.
659void ScheduleDAGRRList::EmitNode(SUnit *SU) {
660 if (!HazardRec->isEnabled())
661 return;
662
663 // Check for phys reg copy.
664 if (!SU->getNode())
665 return;
666
667 switch (SU->getNode()->getOpcode()) {
668 default:
669 assert(SU->getNode()->isMachineOpcode() &&((SU->getNode()->isMachineOpcode() && "This target-independent node should not be scheduled."
) ? static_cast<void> (0) : __assert_fail ("SU->getNode()->isMachineOpcode() && \"This target-independent node should not be scheduled.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 670, __PRETTY_FUNCTION__))
670 "This target-independent node should not be scheduled.")((SU->getNode()->isMachineOpcode() && "This target-independent node should not be scheduled."
) ? static_cast<void> (0) : __assert_fail ("SU->getNode()->isMachineOpcode() && \"This target-independent node should not be scheduled.\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 670, __PRETTY_FUNCTION__))
;
671 break;
672 case ISD::MERGE_VALUES:
673 case ISD::TokenFactor:
674 case ISD::LIFETIME_START:
675 case ISD::LIFETIME_END:
676 case ISD::CopyToReg:
677 case ISD::CopyFromReg:
678 case ISD::EH_LABEL:
679 // Noops don't affect the scoreboard state. Copies are likely to be
680 // removed.
681 return;
682 case ISD::INLINEASM:
683 // For inline asm, clear the pipeline state.
684 HazardRec->Reset();
685 return;
686 }
687 if (SU->isCall) {
688 // Calls are scheduled with their preceding instructions. For bottom-up
689 // scheduling, clear the pipeline state before emitting.
690 HazardRec->Reset();
691 }
692
693 HazardRec->EmitInstruction(SU);
694}
695
696static void resetVRegCycle(SUnit *SU);
697
698/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
699/// count of its predecessors. If a predecessor pending count is zero, add it to
700/// the Available queue.
701void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU) {
702 DEBUG(dbgs() << "\n*** Scheduling [" << CurCycle << "]: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "\n*** Scheduling [" <<
CurCycle << "]: "; } } while (false)
;
703 DEBUG(SU->dump(this))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { SU->dump(this); } } while (false)
;
704
705#ifndef NDEBUG
706 if (CurCycle < SU->getHeight())
707 DEBUG(dbgs() << " Height [" << SU->getHeight()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Height [" << SU
->getHeight() << "] pipeline stall!\n"; } } while (false
)
708 << "] pipeline stall!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Height [" << SU
->getHeight() << "] pipeline stall!\n"; } } while (false
)
;
709#endif
710
711 // FIXME: Do not modify node height. It may interfere with
712 // backtracking. Instead add a "ready cycle" to SUnit. Before scheduling the
713 // node its ready cycle can aid heuristics, and after scheduling it can
714 // indicate the scheduled cycle.
715 SU->setHeightToAtLeast(CurCycle);
716
717 // Reserve resources for the scheduled instruction.
718 EmitNode(SU);
719
720 Sequence.push_back(SU);
721
722 AvailableQueue->scheduledNode(SU);
723
724 // If HazardRec is disabled, and each inst counts as one cycle, then
725 // advance CurCycle before ReleasePredecessors to avoid useless pushes to
726 // PendingQueue for schedulers that implement HasReadyFilter.
727 if (!HazardRec->isEnabled() && AvgIPC < 2)
728 AdvanceToCycle(CurCycle + 1);
729
730 // Update liveness of predecessors before successors to avoid treating a
731 // two-address node as a live range def.
732 ReleasePredecessors(SU);
733
734 // Release all the implicit physical register defs that are live.
735 for (SDep &Succ : SU->Succs) {
736 // LiveRegDegs[Succ.getReg()] != SU when SU is a two-address node.
737 if (Succ.isAssignedRegDep() && LiveRegDefs[Succ.getReg()] == SU) {
738 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!")((NumLiveRegs > 0 && "NumLiveRegs is already zero!"
) ? static_cast<void> (0) : __assert_fail ("NumLiveRegs > 0 && \"NumLiveRegs is already zero!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 738, __PRETTY_FUNCTION__))
;
739 --NumLiveRegs;
740 LiveRegDefs[Succ.getReg()] = nullptr;
741 LiveRegGens[Succ.getReg()] = nullptr;
742 releaseInterferences(Succ.getReg());
743 }
744 }
745 // Release the special call resource dependence, if this is the beginning
746 // of a call.
747 unsigned CallResource = TRI->getNumRegs();
748 if (LiveRegDefs[CallResource] == SU)
749 for (const SDNode *SUNode = SU->getNode(); SUNode;
750 SUNode = SUNode->getGluedNode()) {
751 if (SUNode->isMachineOpcode() &&
752 SUNode->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {
753 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!")((NumLiveRegs > 0 && "NumLiveRegs is already zero!"
) ? static_cast<void> (0) : __assert_fail ("NumLiveRegs > 0 && \"NumLiveRegs is already zero!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 753, __PRETTY_FUNCTION__))
;
754 --NumLiveRegs;
755 LiveRegDefs[CallResource] = nullptr;
756 LiveRegGens[CallResource] = nullptr;
757 releaseInterferences(CallResource);
758 }
759 }
760
761 resetVRegCycle(SU);
762
763 SU->isScheduled = true;
764
765 // Conditions under which the scheduler should eagerly advance the cycle:
766 // (1) No available instructions
767 // (2) All pipelines full, so available instructions must have hazards.
768 //
769 // If HazardRec is disabled, the cycle was pre-advanced before calling
770 // ReleasePredecessors. In that case, IssueCount should remain 0.
771 //
772 // Check AvailableQueue after ReleasePredecessors in case of zero latency.
773 if (HazardRec->isEnabled() || AvgIPC > 1) {
774 if (SU->getNode() && SU->getNode()->isMachineOpcode())
775 ++IssueCount;
776 if ((HazardRec->isEnabled() && HazardRec->atIssueLimit())
777 || (!HazardRec->isEnabled() && IssueCount == AvgIPC))
778 AdvanceToCycle(CurCycle + 1);
779 }
780}
781
782/// CapturePred - This does the opposite of ReleasePred. Since SU is being
783/// unscheduled, incrcease the succ left count of its predecessors. Remove
784/// them from AvailableQueue if necessary.
785void ScheduleDAGRRList::CapturePred(SDep *PredEdge) {
786 SUnit *PredSU = PredEdge->getSUnit();
787 if (PredSU->isAvailable) {
788 PredSU->isAvailable = false;
789 if (!PredSU->isPending)
790 AvailableQueue->remove(PredSU);
791 }
792
793 assert(PredSU->NumSuccsLeft < UINT_MAX && "NumSuccsLeft will overflow!")((PredSU->NumSuccsLeft < (2147483647 *2U +1U) &&
"NumSuccsLeft will overflow!") ? static_cast<void> (0)
: __assert_fail ("PredSU->NumSuccsLeft < UINT_MAX && \"NumSuccsLeft will overflow!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 793, __PRETTY_FUNCTION__))
;
794 ++PredSU->NumSuccsLeft;
795}
796
797/// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and
798/// its predecessor states to reflect the change.
799void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
800 DEBUG(dbgs() << "*** Unscheduling [" << SU->getHeight() << "]: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "*** Unscheduling [" <<
SU->getHeight() << "]: "; } } while (false)
;
801 DEBUG(SU->dump(this))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { SU->dump(this); } } while (false)
;
802
803 for (SDep &Pred : SU->Preds) {
804 CapturePred(&Pred);
805 if (Pred.isAssignedRegDep() && SU == LiveRegGens[Pred.getReg()]){
806 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!")((NumLiveRegs > 0 && "NumLiveRegs is already zero!"
) ? static_cast<void> (0) : __assert_fail ("NumLiveRegs > 0 && \"NumLiveRegs is already zero!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 806, __PRETTY_FUNCTION__))
;
807 assert(LiveRegDefs[Pred.getReg()] == Pred.getSUnit() &&((LiveRegDefs[Pred.getReg()] == Pred.getSUnit() && "Physical register dependency violated?"
) ? static_cast<void> (0) : __assert_fail ("LiveRegDefs[Pred.getReg()] == Pred.getSUnit() && \"Physical register dependency violated?\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 808, __PRETTY_FUNCTION__))
808 "Physical register dependency violated?")((LiveRegDefs[Pred.getReg()] == Pred.getSUnit() && "Physical register dependency violated?"
) ? static_cast<void> (0) : __assert_fail ("LiveRegDefs[Pred.getReg()] == Pred.getSUnit() && \"Physical register dependency violated?\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 808, __PRETTY_FUNCTION__))
;
809 --NumLiveRegs;
810 LiveRegDefs[Pred.getReg()] = nullptr;
811 LiveRegGens[Pred.getReg()] = nullptr;
812 releaseInterferences(Pred.getReg());
813 }
814 }
815
816 // Reclaim the special call resource dependence, if this is the beginning
817 // of a call.
818 unsigned CallResource = TRI->getNumRegs();
819 for (const SDNode *SUNode = SU->getNode(); SUNode;
820 SUNode = SUNode->getGluedNode()) {
821 if (SUNode->isMachineOpcode() &&
822 SUNode->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {
823 ++NumLiveRegs;
824 LiveRegDefs[CallResource] = SU;
825 LiveRegGens[CallResource] = CallSeqEndForStart[SU];
826 }
827 }
828
829 // Release the special call resource dependence, if this is the end
830 // of a call.
831 if (LiveRegGens[CallResource] == SU)
832 for (const SDNode *SUNode = SU->getNode(); SUNode;
833 SUNode = SUNode->getGluedNode()) {
834 if (SUNode->isMachineOpcode() &&
835 SUNode->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
836 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!")((NumLiveRegs > 0 && "NumLiveRegs is already zero!"
) ? static_cast<void> (0) : __assert_fail ("NumLiveRegs > 0 && \"NumLiveRegs is already zero!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 836, __PRETTY_FUNCTION__))
;
837 --NumLiveRegs;
838 LiveRegDefs[CallResource] = nullptr;
839 LiveRegGens[CallResource] = nullptr;
840 releaseInterferences(CallResource);
841 }
842 }
843
844 for (auto &Succ : SU->Succs) {
845 if (Succ.isAssignedRegDep()) {
846 auto Reg = Succ.getReg();
847 if (!LiveRegDefs[Reg])
848 ++NumLiveRegs;
849 // This becomes the nearest def. Note that an earlier def may still be
850 // pending if this is a two-address node.
851 LiveRegDefs[Reg] = SU;
852
853 // Update LiveRegGen only if was empty before this unscheduling.
854 // This is to avoid incorrect updating LiveRegGen set in previous run.
855 if (!LiveRegGens[Reg]) {
856 // Find the successor with the lowest height.
857 LiveRegGens[Reg] = Succ.getSUnit();
858 for (auto &Succ2 : SU->Succs) {
859 if (Succ2.isAssignedRegDep() && Succ2.getReg() == Reg &&
860 Succ2.getSUnit()->getHeight() < LiveRegGens[Reg]->getHeight())
861 LiveRegGens[Reg] = Succ2.getSUnit();
862 }
863 }
864 }
865 }
866 if (SU->getHeight() < MinAvailableCycle)
867 MinAvailableCycle = SU->getHeight();
868
869 SU->setHeightDirty();
870 SU->isScheduled = false;
871 SU->isAvailable = true;
872 if (!DisableSchedCycles && AvailableQueue->hasReadyFilter()) {
873 // Don't make available until backtracking is complete.
874 SU->isPending = true;
875 PendingQueue.push_back(SU);
876 }
877 else {
878 AvailableQueue->push(SU);
879 }
880 AvailableQueue->unscheduledNode(SU);
881}
882
883/// After backtracking, the hazard checker needs to be restored to a state
884/// corresponding the current cycle.
885void ScheduleDAGRRList::RestoreHazardCheckerBottomUp() {
886 HazardRec->Reset();
887
888 unsigned LookAhead = std::min((unsigned)Sequence.size(),
889 HazardRec->getMaxLookAhead());
890 if (LookAhead == 0)
891 return;
892
893 std::vector<SUnit*>::const_iterator I = (Sequence.end() - LookAhead);
894 unsigned HazardCycle = (*I)->getHeight();
895 for (auto E = Sequence.end(); I != E; ++I) {
896 SUnit *SU = *I;
897 for (; SU->getHeight() > HazardCycle; ++HazardCycle) {
898 HazardRec->RecedeCycle();
899 }
900 EmitNode(SU);
901 }
902}
903
904/// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in
905/// BTCycle in order to schedule a specific node.
906void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, SUnit *BtSU) {
907 SUnit *OldSU = Sequence.back();
908 while (true) {
909 Sequence.pop_back();
910 // FIXME: use ready cycle instead of height
911 CurCycle = OldSU->getHeight();
912 UnscheduleNodeBottomUp(OldSU);
913 AvailableQueue->setCurCycle(CurCycle);
914 if (OldSU == BtSU)
915 break;
916 OldSU = Sequence.back();
917 }
918
919 assert(!SU->isSucc(OldSU) && "Something is wrong!")((!SU->isSucc(OldSU) && "Something is wrong!") ? static_cast
<void> (0) : __assert_fail ("!SU->isSucc(OldSU) && \"Something is wrong!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 919, __PRETTY_FUNCTION__))
;
920
921 RestoreHazardCheckerBottomUp();
922
923 ReleasePending();
924
925 ++NumBacktracks;
926}
927
928static bool isOperandOf(const SUnit *SU, SDNode *N) {
929 for (const SDNode *SUNode = SU->getNode(); SUNode;
930 SUNode = SUNode->getGluedNode()) {
931 if (SUNode->isOperandOf(N))
932 return true;
933 }
934 return false;
935}
936
937/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
938/// successors to the newly created node.
939SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
940 SDNode *N = SU->getNode();
941 if (!N)
942 return nullptr;
943
944 if (SU->getNode()->getGluedNode())
945 return nullptr;
946
947 SUnit *NewSU;
948 bool TryUnfold = false;
949 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
950 MVT VT = N->getSimpleValueType(i);
951 if (VT == MVT::Glue)
952 return nullptr;
953 else if (VT == MVT::Other)
954 TryUnfold = true;
955 }
956 for (const SDValue &Op : N->op_values()) {
957 MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
958 if (VT == MVT::Glue)
959 return nullptr;
960 }
961
962 if (TryUnfold) {
963 SmallVector<SDNode*, 2> NewNodes;
964 if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes))
965 return nullptr;
966
967 // unfolding an x86 DEC64m operation results in store, dec, load which
968 // can't be handled here so quit
969 if (NewNodes.size() == 3)
970 return nullptr;
971
972 DEBUG(dbgs() << "Unfolding SU #" << SU->NodeNum << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "Unfolding SU #" <<
SU->NodeNum << "\n"; } } while (false)
;
973 assert(NewNodes.size() == 2 && "Expected a load folding node!")((NewNodes.size() == 2 && "Expected a load folding node!"
) ? static_cast<void> (0) : __assert_fail ("NewNodes.size() == 2 && \"Expected a load folding node!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 973, __PRETTY_FUNCTION__))
;
974
975 N = NewNodes[1];
976 SDNode *LoadNode = NewNodes[0];
977 unsigned NumVals = N->getNumValues();
978 unsigned OldNumVals = SU->getNode()->getNumValues();
979 for (unsigned i = 0; i != NumVals; ++i)
980 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i));
981 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1),
982 SDValue(LoadNode, 1));
983
984 // LoadNode may already exist. This can happen when there is another
985 // load from the same location and producing the same type of value
986 // but it has different alignment or volatileness.
987 bool isNewLoad = true;
988 SUnit *LoadSU;
989 if (LoadNode->getNodeId() != -1) {
990 LoadSU = &SUnits[LoadNode->getNodeId()];
991 isNewLoad = false;
992 } else {
993 LoadSU = CreateNewSUnit(LoadNode);
994 LoadNode->setNodeId(LoadSU->NodeNum);
995
996 InitNumRegDefsLeft(LoadSU);
997 computeLatency(LoadSU);
998 }
999
1000 SUnit *NewSU = CreateNewSUnit(N);
1001 assert(N->getNodeId() == -1 && "Node already inserted!")((N->getNodeId() == -1 && "Node already inserted!"
) ? static_cast<void> (0) : __assert_fail ("N->getNodeId() == -1 && \"Node already inserted!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 1001, __PRETTY_FUNCTION__))
;
1002 N->setNodeId(NewSU->NodeNum);
1003
1004 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
1005 for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
1006 if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
1007 NewSU->isTwoAddress = true;
1008 break;
1009 }
1010 }
1011 if (MCID.isCommutable())
1012 NewSU->isCommutable = true;
1013
1014 InitNumRegDefsLeft(NewSU);
1015 computeLatency(NewSU);
1016
1017 // Record all the edges to and from the old SU, by category.
1018 SmallVector<SDep, 4> ChainPreds;
1019 SmallVector<SDep, 4> ChainSuccs;
1020 SmallVector<SDep, 4> LoadPreds;
1021 SmallVector<SDep, 4> NodePreds;
1022 SmallVector<SDep, 4> NodeSuccs;
1023 for (SDep &Pred : SU->Preds) {
1024 if (Pred.isCtrl())
1025 ChainPreds.push_back(Pred);
1026 else if (isOperandOf(Pred.getSUnit(), LoadNode))
1027 LoadPreds.push_back(Pred);
1028 else
1029 NodePreds.push_back(Pred);
1030 }
1031 for (SDep &Succ : SU->Succs) {
1032 if (Succ.isCtrl())
1033 ChainSuccs.push_back(Succ);
1034 else
1035 NodeSuccs.push_back(Succ);
1036 }
1037
1038 // Now assign edges to the newly-created nodes.
1039 for (const SDep &Pred : ChainPreds) {
1040 RemovePred(SU, Pred);
1041 if (isNewLoad)
1042 AddPred(LoadSU, Pred);
1043 }
1044 for (const SDep &Pred : LoadPreds) {
1045 RemovePred(SU, Pred);
1046 if (isNewLoad)
1047 AddPred(LoadSU, Pred);
1048 }
1049 for (const SDep &Pred : NodePreds) {
1050 RemovePred(SU, Pred);
1051 AddPred(NewSU, Pred);
1052 }
1053 for (SDep D : NodeSuccs) {
1054 SUnit *SuccDep = D.getSUnit();
1055 D.setSUnit(SU);
1056 RemovePred(SuccDep, D);
1057 D.setSUnit(NewSU);
1058 AddPred(SuccDep, D);
1059 // Balance register pressure.
1060 if (AvailableQueue->tracksRegPressure() && SuccDep->isScheduled
1061 && !D.isCtrl() && NewSU->NumRegDefsLeft > 0)
1062 --NewSU->NumRegDefsLeft;
1063 }
1064 for (SDep D : ChainSuccs) {
1065 SUnit *SuccDep = D.getSUnit();
1066 D.setSUnit(SU);
1067 RemovePred(SuccDep, D);
1068 if (isNewLoad) {
1069 D.setSUnit(LoadSU);
1070 AddPred(SuccDep, D);
1071 }
1072 }
1073
1074 // Add a data dependency to reflect that NewSU reads the value defined
1075 // by LoadSU.
1076 SDep D(LoadSU, SDep::Data, 0);
1077 D.setLatency(LoadSU->Latency);
1078 AddPred(NewSU, D);
1079
1080 if (isNewLoad)
1081 AvailableQueue->addNode(LoadSU);
1082 AvailableQueue->addNode(NewSU);
1083
1084 ++NumUnfolds;
1085
1086 if (NewSU->NumSuccsLeft == 0) {
1087 NewSU->isAvailable = true;
1088 return NewSU;
1089 }
1090 SU = NewSU;
1091 }
1092
1093 DEBUG(dbgs() << " Duplicating SU #" << SU->NodeNum << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Duplicating SU #" <<
SU->NodeNum << "\n"; } } while (false)
;
1094 NewSU = CreateClone(SU);
1095
1096 // New SUnit has the exact same predecessors.
1097 for (SDep &Pred : SU->Preds)
1098 if (!Pred.isArtificial())
1099 AddPred(NewSU, Pred);
1100
1101 // Only copy scheduled successors. Cut them from old node's successor
1102 // list and move them over.
1103 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
1104 for (SDep &Succ : SU->Succs) {
1105 if (Succ.isArtificial())
1106 continue;
1107 SUnit *SuccSU = Succ.getSUnit();
1108 if (SuccSU->isScheduled) {
1109 SDep D = Succ;
1110 D.setSUnit(NewSU);
1111 AddPred(SuccSU, D);
1112 D.setSUnit(SU);
1113 DelDeps.push_back(std::make_pair(SuccSU, D));
1114 }
1115 }
1116 for (auto &DelDep : DelDeps)
1117 RemovePred(DelDep.first, DelDep.second);
1118
1119 AvailableQueue->updateNode(SU);
1120 AvailableQueue->addNode(NewSU);
1121
1122 ++NumDups;
1123 return NewSU;
1124}
1125
1126/// InsertCopiesAndMoveSuccs - Insert register copies and move all
1127/// scheduled successors of the given SUnit to the last copy.
1128void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
1129 const TargetRegisterClass *DestRC,
1130 const TargetRegisterClass *SrcRC,
1131 SmallVectorImpl<SUnit*> &Copies) {
1132 SUnit *CopyFromSU = CreateNewSUnit(nullptr);
1133 CopyFromSU->CopySrcRC = SrcRC;
1134 CopyFromSU->CopyDstRC = DestRC;
1135
1136 SUnit *CopyToSU = CreateNewSUnit(nullptr);
1137 CopyToSU->CopySrcRC = DestRC;
1138 CopyToSU->CopyDstRC = SrcRC;
1139
1140 // Only copy scheduled successors. Cut them from old node's successor
1141 // list and move them over.
1142 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
1143 for (SDep &Succ : SU->Succs) {
1144 if (Succ.isArtificial())
1145 continue;
1146 SUnit *SuccSU = Succ.getSUnit();
1147 if (SuccSU->isScheduled) {
1148 SDep D = Succ;
1149 D.setSUnit(CopyToSU);
1150 AddPred(SuccSU, D);
1151 DelDeps.push_back(std::make_pair(SuccSU, Succ));
1152 }
1153 else {
1154 // Avoid scheduling the def-side copy before other successors. Otherwise
1155 // we could introduce another physreg interference on the copy and
1156 // continue inserting copies indefinitely.
1157 AddPred(SuccSU, SDep(CopyFromSU, SDep::Artificial));
1158 }
1159 }
1160 for (auto &DelDep : DelDeps)
1161 RemovePred(DelDep.first, DelDep.second);
1162
1163 SDep FromDep(SU, SDep::Data, Reg);
1164 FromDep.setLatency(SU->Latency);
1165 AddPred(CopyFromSU, FromDep);
1166 SDep ToDep(CopyFromSU, SDep::Data, 0);
1167 ToDep.setLatency(CopyFromSU->Latency);
1168 AddPred(CopyToSU, ToDep);
1169
1170 AvailableQueue->updateNode(SU);
1171 AvailableQueue->addNode(CopyFromSU);
1172 AvailableQueue->addNode(CopyToSU);
1173 Copies.push_back(CopyFromSU);
1174 Copies.push_back(CopyToSU);
1175
1176 ++NumPRCopies;
1177}
1178
1179/// getPhysicalRegisterVT - Returns the ValueType of the physical register
1180/// definition of the specified node.
1181/// FIXME: Move to SelectionDAG?
1182static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,
1183 const TargetInstrInfo *TII) {
1184 unsigned NumRes;
1185 if (N->getOpcode() == ISD::CopyFromReg) {
1186 // CopyFromReg has: "chain, Val, glue" so operand 1 gives the type.
1187 NumRes = 1;
1188 } else {
1189 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
1190 assert(MCID.ImplicitDefs && "Physical reg def must be in implicit def list!")((MCID.ImplicitDefs && "Physical reg def must be in implicit def list!"
) ? static_cast<void> (0) : __assert_fail ("MCID.ImplicitDefs && \"Physical reg def must be in implicit def list!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 1190, __PRETTY_FUNCTION__))
;
1191 NumRes = MCID.getNumDefs();
1192 for (const MCPhysReg *ImpDef = MCID.getImplicitDefs(); *ImpDef; ++ImpDef) {
1193 if (Reg == *ImpDef)
1194 break;
1195 ++NumRes;
1196 }
1197 }
1198 return N->getSimpleValueType(NumRes);
1199}
1200
1201/// CheckForLiveRegDef - Return true and update live register vector if the
1202/// specified register def of the specified SUnit clobbers any "live" registers.
1203static void CheckForLiveRegDef(SUnit *SU, unsigned Reg,
1204 SUnit **LiveRegDefs,
1205 SmallSet<unsigned, 4> &RegAdded,
1206 SmallVectorImpl<unsigned> &LRegs,
1207 const TargetRegisterInfo *TRI) {
1208 for (MCRegAliasIterator AliasI(Reg, TRI, true); AliasI.isValid(); ++AliasI) {
1209
1210 // Check if Ref is live.
1211 if (!LiveRegDefs[*AliasI]) continue;
1212
1213 // Allow multiple uses of the same def.
1214 if (LiveRegDefs[*AliasI] == SU) continue;
1215
1216 // Add Reg to the set of interfering live regs.
1217 if (RegAdded.insert(*AliasI).second) {
1218 LRegs.push_back(*AliasI);
1219 }
1220 }
1221}
1222
1223/// CheckForLiveRegDefMasked - Check for any live physregs that are clobbered
1224/// by RegMask, and add them to LRegs.
1225static void CheckForLiveRegDefMasked(SUnit *SU, const uint32_t *RegMask,
1226 ArrayRef<SUnit*> LiveRegDefs,
1227 SmallSet<unsigned, 4> &RegAdded,
1228 SmallVectorImpl<unsigned> &LRegs) {
1229 // Look at all live registers. Skip Reg0 and the special CallResource.
1230 for (unsigned i = 1, e = LiveRegDefs.size()-1; i != e; ++i) {
1231 if (!LiveRegDefs[i]) continue;
1232 if (LiveRegDefs[i] == SU) continue;
1233 if (!MachineOperand::clobbersPhysReg(RegMask, i)) continue;
1234 if (RegAdded.insert(i).second)
1235 LRegs.push_back(i);
1236 }
1237}
1238
1239/// getNodeRegMask - Returns the register mask attached to an SDNode, if any.
1240static const uint32_t *getNodeRegMask(const SDNode *N) {
1241 for (const SDValue &Op : N->op_values())
1242 if (const auto *RegOp = dyn_cast<RegisterMaskSDNode>(Op.getNode()))
1243 return RegOp->getRegMask();
1244 return nullptr;
1245}
1246
1247/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
1248/// scheduling of the given node to satisfy live physical register dependencies.
1249/// If the specific node is the last one that's available to schedule, do
1250/// whatever is necessary (i.e. backtracking or cloning) to make it possible.
1251bool ScheduleDAGRRList::
1252DelayForLiveRegsBottomUp(SUnit *SU, SmallVectorImpl<unsigned> &LRegs) {
1253 if (NumLiveRegs == 0)
1254 return false;
1255
1256 SmallSet<unsigned, 4> RegAdded;
1257 // If this node would clobber any "live" register, then it's not ready.
1258 //
1259 // If SU is the currently live definition of the same register that it uses,
1260 // then we are free to schedule it.
1261 for (SDep &Pred : SU->Preds) {
1262 if (Pred.isAssignedRegDep() && LiveRegDefs[Pred.getReg()] != SU)
1263 CheckForLiveRegDef(Pred.getSUnit(), Pred.getReg(), LiveRegDefs.get(),
1264 RegAdded, LRegs, TRI);
1265 }
1266
1267 for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode()) {
1268 if (Node->getOpcode() == ISD::INLINEASM) {
1269 // Inline asm can clobber physical defs.
1270 unsigned NumOps = Node->getNumOperands();
1271 if (Node->getOperand(NumOps-1).getValueType() == MVT::Glue)
1272 --NumOps; // Ignore the glue operand.
1273
1274 for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) {
1275 unsigned Flags =
1276 cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue();
1277 unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags);
1278
1279 ++i; // Skip the ID value.
1280 if (InlineAsm::isRegDefKind(Flags) ||
1281 InlineAsm::isRegDefEarlyClobberKind(Flags) ||
1282 InlineAsm::isClobberKind(Flags)) {
1283 // Check for def of register or earlyclobber register.
1284 for (; NumVals; --NumVals, ++i) {
1285 unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
1286 if (TargetRegisterInfo::isPhysicalRegister(Reg))
1287 CheckForLiveRegDef(SU, Reg, LiveRegDefs.get(), RegAdded, LRegs, TRI);
1288 }
1289 } else
1290 i += NumVals;
1291 }
1292 continue;
1293 }
1294
1295 if (!Node->isMachineOpcode())
1296 continue;
1297 // If we're in the middle of scheduling a call, don't begin scheduling
1298 // another call. Also, don't allow any physical registers to be live across
1299 // the call.
1300 if ((Node->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) ||
1301 (Node->getMachineOpcode() == TII->getCallFrameSetupOpcode())) {
1302 // Check the special calling-sequence resource.
1303 unsigned CallResource = TRI->getNumRegs();
1304 if (LiveRegDefs[CallResource]) {
1305 SDNode *Gen = LiveRegGens[CallResource]->getNode();
1306 while (SDNode *Glued = Gen->getGluedNode())
1307 Gen = Glued;
1308 if (!IsChainDependent(Gen, Node, 0, TII) &&
1309 RegAdded.insert(CallResource).second)
1310 LRegs.push_back(CallResource);
1311 }
1312 }
1313 if (const uint32_t *RegMask = getNodeRegMask(Node))
1314 CheckForLiveRegDefMasked(SU, RegMask,
1315 makeArrayRef(LiveRegDefs.get(), TRI->getNumRegs()),
1316 RegAdded, LRegs);
1317
1318 const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode());
1319 if (MCID.hasOptionalDef()) {
1320 // Most ARM instructions have an OptionalDef for CPSR, to model the S-bit.
1321 // This operand can be either a def of CPSR, if the S bit is set; or a use
1322 // of %noreg. When the OptionalDef is set to a valid register, we need to
1323 // handle it in the same way as an ImplicitDef.
1324 for (unsigned i = 0; i < MCID.getNumDefs(); ++i)
1325 if (MCID.OpInfo[i].isOptionalDef()) {
1326 const SDValue &OptionalDef = Node->getOperand(i - Node->getNumValues());
1327 unsigned Reg = cast<RegisterSDNode>(OptionalDef)->getReg();
1328 CheckForLiveRegDef(SU, Reg, LiveRegDefs.get(), RegAdded, LRegs, TRI);
1329 }
1330 }
1331 if (!MCID.ImplicitDefs)
1332 continue;
1333 for (const MCPhysReg *Reg = MCID.getImplicitDefs(); *Reg; ++Reg)
1334 CheckForLiveRegDef(SU, *Reg, LiveRegDefs.get(), RegAdded, LRegs, TRI);
1335 }
1336
1337 return !LRegs.empty();
1338}
1339
1340void ScheduleDAGRRList::releaseInterferences(unsigned Reg) {
1341 // Add the nodes that aren't ready back onto the available list.
1342 for (unsigned i = Interferences.size(); i > 0; --i) {
1343 SUnit *SU = Interferences[i-1];
1344 LRegsMapT::iterator LRegsPos = LRegsMap.find(SU);
1345 if (Reg) {
1346 SmallVectorImpl<unsigned> &LRegs = LRegsPos->second;
1347 if (!is_contained(LRegs, Reg))
1348 continue;
1349 }
1350 SU->isPending = false;
1351 // The interfering node may no longer be available due to backtracking.
1352 // Furthermore, it may have been made available again, in which case it is
1353 // now already in the AvailableQueue.
1354 if (SU->isAvailable && !SU->NodeQueueId) {
1355 DEBUG(dbgs() << " Repushing SU #" << SU->NodeNum << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Repushing SU #" <<
SU->NodeNum << '\n'; } } while (false)
;
1356 AvailableQueue->push(SU);
1357 }
1358 if (i < Interferences.size())
1359 Interferences[i-1] = Interferences.back();
1360 Interferences.pop_back();
1361 LRegsMap.erase(LRegsPos);
1362 }
1363}
1364
1365/// Return a node that can be scheduled in this cycle. Requirements:
1366/// (1) Ready: latency has been satisfied
1367/// (2) No Hazards: resources are available
1368/// (3) No Interferences: may unschedule to break register interferences.
1369SUnit *ScheduleDAGRRList::PickNodeToScheduleBottomUp() {
1370 SUnit *CurSU = AvailableQueue->empty() ? nullptr : AvailableQueue->pop();
1
Assuming the condition is false
2
'?' condition is false
1371 while (CurSU) {
3
Loop condition is false. Execution continues on line 1392
1372 SmallVector<unsigned, 4> LRegs;
1373 if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
1374 break;
1375 DEBUG(dbgs() << " Interfering reg " <<do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Interfering reg " <<
(LRegs[0] == TRI->getNumRegs() ? "CallResource" : TRI->
getName(LRegs[0])) << " SU #" << CurSU->NodeNum
<< '\n'; } } while (false)
1376 (LRegs[0] == TRI->getNumRegs() ? "CallResource"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Interfering reg " <<
(LRegs[0] == TRI->getNumRegs() ? "CallResource" : TRI->
getName(LRegs[0])) << " SU #" << CurSU->NodeNum
<< '\n'; } } while (false)
1377 : TRI->getName(LRegs[0]))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Interfering reg " <<
(LRegs[0] == TRI->getNumRegs() ? "CallResource" : TRI->
getName(LRegs[0])) << " SU #" << CurSU->NodeNum
<< '\n'; } } while (false)
1378 << " SU #" << CurSU->NodeNum << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Interfering reg " <<
(LRegs[0] == TRI->getNumRegs() ? "CallResource" : TRI->
getName(LRegs[0])) << " SU #" << CurSU->NodeNum
<< '\n'; } } while (false)
;
1379 std::pair<LRegsMapT::iterator, bool> LRegsPair =
1380 LRegsMap.insert(std::make_pair(CurSU, LRegs));
1381 if (LRegsPair.second) {
1382 CurSU->isPending = true; // This SU is not in AvailableQueue right now.
1383 Interferences.push_back(CurSU);
1384 }
1385 else {
1386 assert(CurSU->isPending && "Interferences are pending")((CurSU->isPending && "Interferences are pending")
? static_cast<void> (0) : __assert_fail ("CurSU->isPending && \"Interferences are pending\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 1386, __PRETTY_FUNCTION__))
;
1387 // Update the interference with current live regs.
1388 LRegsPair.first->second = LRegs;
1389 }
1390 CurSU = AvailableQueue->pop();
1391 }
1392 if (CurSU)
4
Taking false branch
1393 return CurSU;
1394
1395 // All candidates are delayed due to live physical reg dependencies.
1396 // Try backtracking, code duplication, or inserting cross class copies
1397 // to resolve it.
1398 for (SUnit *TrySU : Interferences) {
5
Assuming '__begin' is not equal to '__end'
1399 SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
1400
1401 // Try unscheduling up to the point where it's safe to schedule
1402 // this node.
1403 SUnit *BtSU = nullptr;
9
'BtSU' initialized to a null pointer value
1404 unsigned LiveCycle = UINT_MAX(2147483647 *2U +1U);
1405 for (unsigned Reg : LRegs) {
6
Assuming '__begin' is equal to '__end'
10
Assuming '__begin' is equal to '__end'
1406 if (LiveRegGens[Reg]->getHeight() < LiveCycle) {
1407 BtSU = LiveRegGens[Reg];
1408 LiveCycle = BtSU->getHeight();
1409 }
1410 }
1411 if (!WillCreateCycle(TrySU, BtSU)) {
7
Assuming the condition is false
8
Taking false branch
11
Assuming the condition is true
12
Taking true branch
1412 // BacktrackBottomUp mutates Interferences!
1413 BacktrackBottomUp(TrySU, BtSU);
1414
1415 // Force the current node to be scheduled before the node that
1416 // requires the physical reg dep.
1417 if (BtSU->isAvailable) {
13
Access to field 'isAvailable' results in a dereference of a null pointer (loaded from variable 'BtSU')
1418 BtSU->isAvailable = false;
1419 if (!BtSU->isPending)
1420 AvailableQueue->remove(BtSU);
1421 }
1422 DEBUG(dbgs() << "ARTIFICIAL edge from SU(" << BtSU->NodeNum << ") to SU("do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "ARTIFICIAL edge from SU("
<< BtSU->NodeNum << ") to SU(" << TrySU
->NodeNum << ")\n"; } } while (false)
1423 << TrySU->NodeNum << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "ARTIFICIAL edge from SU("
<< BtSU->NodeNum << ") to SU(" << TrySU
->NodeNum << ")\n"; } } while (false)
;
1424 AddPred(TrySU, SDep(BtSU, SDep::Artificial));
1425
1426 // If one or more successors has been unscheduled, then the current
1427 // node is no longer available.
1428 if (!TrySU->isAvailable || !TrySU->NodeQueueId)
1429 CurSU = AvailableQueue->pop();
1430 else {
1431 // Available and in AvailableQueue
1432 AvailableQueue->remove(TrySU);
1433 CurSU = TrySU;
1434 }
1435 // Interferences has been mutated. We must break.
1436 break;
1437 }
1438 }
1439
1440 if (!CurSU) {
1441 // Can't backtrack. If it's too expensive to copy the value, then try
1442 // duplicate the nodes that produces these "too expensive to copy"
1443 // values to break the dependency. In case even that doesn't work,
1444 // insert cross class copies.
1445 // If it's not too expensive, i.e. cost != -1, issue copies.
1446 SUnit *TrySU = Interferences[0];
1447 SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
1448 assert(LRegs.size() == 1 && "Can't handle this yet!")((LRegs.size() == 1 && "Can't handle this yet!") ? static_cast
<void> (0) : __assert_fail ("LRegs.size() == 1 && \"Can't handle this yet!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 1448, __PRETTY_FUNCTION__))
;
1449 unsigned Reg = LRegs[0];
1450 SUnit *LRDef = LiveRegDefs[Reg];
1451 MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
1452 const TargetRegisterClass *RC =
1453 TRI->getMinimalPhysRegClass(Reg, VT);
1454 const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
1455
1456 // If cross copy register class is the same as RC, then it must be possible
1457 // copy the value directly. Do not try duplicate the def.
1458 // If cross copy register class is not the same as RC, then it's possible to
1459 // copy the value but it require cross register class copies and it is
1460 // expensive.
1461 // If cross copy register class is null, then it's not possible to copy
1462 // the value at all.
1463 SUnit *NewDef = nullptr;
1464 if (DestRC != RC) {
1465 NewDef = CopyAndMoveSuccessors(LRDef);
1466 if (!DestRC && !NewDef)
1467 report_fatal_error("Can't handle live physical register dependency!");
1468 }
1469 if (!NewDef) {
1470 // Issue copies, these can be expensive cross register class copies.
1471 SmallVector<SUnit*, 2> Copies;
1472 InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
1473 DEBUG(dbgs() << " Adding an edge from SU #" << TrySU->NodeNumdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Adding an edge from SU #"
<< TrySU->NodeNum << " to SU #" << Copies
.front()->NodeNum << "\n"; } } while (false)
1474 << " to SU #" << Copies.front()->NodeNum << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Adding an edge from SU #"
<< TrySU->NodeNum << " to SU #" << Copies
.front()->NodeNum << "\n"; } } while (false)
;
1475 AddPred(TrySU, SDep(Copies.front(), SDep::Artificial));
1476 NewDef = Copies.back();
1477 }
1478
1479 DEBUG(dbgs() << " Adding an edge from SU #" << NewDef->NodeNumdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Adding an edge from SU #"
<< NewDef->NodeNum << " to SU #" << TrySU
->NodeNum << "\n"; } } while (false)
1480 << " to SU #" << TrySU->NodeNum << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Adding an edge from SU #"
<< NewDef->NodeNum << " to SU #" << TrySU
->NodeNum << "\n"; } } while (false)
;
1481 LiveRegDefs[Reg] = NewDef;
1482 AddPred(NewDef, SDep(TrySU, SDep::Artificial));
1483 TrySU->isAvailable = false;
1484 CurSU = NewDef;
1485 }
1486 assert(CurSU && "Unable to resolve live physical register dependencies!")((CurSU && "Unable to resolve live physical register dependencies!"
) ? static_cast<void> (0) : __assert_fail ("CurSU && \"Unable to resolve live physical register dependencies!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 1486, __PRETTY_FUNCTION__))
;
1487 return CurSU;
1488}
1489
1490/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
1491/// schedulers.
1492void ScheduleDAGRRList::ListScheduleBottomUp() {
1493 // Release any predecessors of the special Exit node.
1494 ReleasePredecessors(&ExitSU);
1495
1496 // Add root to Available queue.
1497 if (!SUnits.empty()) {
1498 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
1499 assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!")((RootSU->Succs.empty() && "Graph root shouldn't have successors!"
) ? static_cast<void> (0) : __assert_fail ("RootSU->Succs.empty() && \"Graph root shouldn't have successors!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 1499, __PRETTY_FUNCTION__))
;
1500 RootSU->isAvailable = true;
1501 AvailableQueue->push(RootSU);
1502 }
1503
1504 // While Available queue is not empty, grab the node with the highest
1505 // priority. If it is not ready put it back. Schedule the node.
1506 Sequence.reserve(SUnits.size());
1507 while (!AvailableQueue->empty() || !Interferences.empty()) {
1508 DEBUG(dbgs() << "\nExamining Available:\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "\nExamining Available:\n"
; AvailableQueue->dump(this); } } while (false)
1509 AvailableQueue->dump(this))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "\nExamining Available:\n"
; AvailableQueue->dump(this); } } while (false)
;
1510
1511 // Pick the best node to schedule taking all constraints into
1512 // consideration.
1513 SUnit *SU = PickNodeToScheduleBottomUp();
1514
1515 AdvancePastStalls(SU);
1516
1517 ScheduleNodeBottomUp(SU);
1518
1519 while (AvailableQueue->empty() && !PendingQueue.empty()) {
1520 // Advance the cycle to free resources. Skip ahead to the next ready SU.
1521 assert(MinAvailableCycle < UINT_MAX && "MinAvailableCycle uninitialized")((MinAvailableCycle < (2147483647 *2U +1U) && "MinAvailableCycle uninitialized"
) ? static_cast<void> (0) : __assert_fail ("MinAvailableCycle < UINT_MAX && \"MinAvailableCycle uninitialized\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 1521, __PRETTY_FUNCTION__))
;
1522 AdvanceToCycle(std::max(CurCycle + 1, MinAvailableCycle));
1523 }
1524 }
1525
1526 // Reverse the order if it is bottom up.
1527 std::reverse(Sequence.begin(), Sequence.end());
1528
1529#ifndef NDEBUG
1530 VerifyScheduledSequence(/*isBottomUp=*/true);
1531#endif
1532}
1533
1534//===----------------------------------------------------------------------===//
1535// RegReductionPriorityQueue Definition
1536//===----------------------------------------------------------------------===//
1537//
1538// This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
1539// to reduce register pressure.
1540//
1541namespace {
1542class RegReductionPQBase;
1543
1544struct queue_sort : public std::binary_function<SUnit*, SUnit*, bool> {
1545 bool isReady(SUnit* SU, unsigned CurCycle) const { return true; }
1546};
1547
1548#ifndef NDEBUG
1549template<class SF>
1550struct reverse_sort : public queue_sort {
1551 SF &SortFunc;
1552 reverse_sort(SF &sf) : SortFunc(sf) {}
1553
1554 bool operator()(SUnit* left, SUnit* right) const {
1555 // reverse left/right rather than simply !SortFunc(left, right)
1556 // to expose different paths in the comparison logic.
1557 return SortFunc(right, left);
1558 }
1559};
1560#endif // NDEBUG
1561
1562/// bu_ls_rr_sort - Priority function for bottom up register pressure
1563// reduction scheduler.
1564struct bu_ls_rr_sort : public queue_sort {
1565 enum {
1566 IsBottomUp = true,
1567 HasReadyFilter = false
1568 };
1569
1570 RegReductionPQBase *SPQ;
1571 bu_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
1572
1573 bool operator()(SUnit* left, SUnit* right) const;
1574};
1575
1576// src_ls_rr_sort - Priority function for source order scheduler.
1577struct src_ls_rr_sort : public queue_sort {
1578 enum {
1579 IsBottomUp = true,
1580 HasReadyFilter = false
1581 };
1582
1583 RegReductionPQBase *SPQ;
1584 src_ls_rr_sort(RegReductionPQBase *spq)
1585 : SPQ(spq) {}
1586
1587 bool operator()(SUnit* left, SUnit* right) const;
1588};
1589
1590// hybrid_ls_rr_sort - Priority function for hybrid scheduler.
1591struct hybrid_ls_rr_sort : public queue_sort {
1592 enum {
1593 IsBottomUp = true,
1594 HasReadyFilter = false
1595 };
1596
1597 RegReductionPQBase *SPQ;
1598 hybrid_ls_rr_sort(RegReductionPQBase *spq)
1599 : SPQ(spq) {}
1600
1601 bool isReady(SUnit *SU, unsigned CurCycle) const;
1602
1603 bool operator()(SUnit* left, SUnit* right) const;
1604};
1605
1606// ilp_ls_rr_sort - Priority function for ILP (instruction level parallelism)
1607// scheduler.
1608struct ilp_ls_rr_sort : public queue_sort {
1609 enum {
1610 IsBottomUp = true,
1611 HasReadyFilter = false
1612 };
1613
1614 RegReductionPQBase *SPQ;
1615 ilp_ls_rr_sort(RegReductionPQBase *spq)
1616 : SPQ(spq) {}
1617
1618 bool isReady(SUnit *SU, unsigned CurCycle) const;
1619
1620 bool operator()(SUnit* left, SUnit* right) const;
1621};
1622
1623class RegReductionPQBase : public SchedulingPriorityQueue {
1624protected:
1625 std::vector<SUnit*> Queue;
1626 unsigned CurQueueId;
1627 bool TracksRegPressure;
1628 bool SrcOrder;
1629
1630 // SUnits - The SUnits for the current graph.
1631 std::vector<SUnit> *SUnits;
1632
1633 MachineFunction &MF;
1634 const TargetInstrInfo *TII;
1635 const TargetRegisterInfo *TRI;
1636 const TargetLowering *TLI;
1637 ScheduleDAGRRList *scheduleDAG;
1638
1639 // SethiUllmanNumbers - The SethiUllman number for each node.
1640 std::vector<unsigned> SethiUllmanNumbers;
1641
1642 /// RegPressure - Tracking current reg pressure per register class.
1643 ///
1644 std::vector<unsigned> RegPressure;
1645
1646 /// RegLimit - Tracking the number of allocatable registers per register
1647 /// class.
1648 std::vector<unsigned> RegLimit;
1649
1650public:
1651 RegReductionPQBase(MachineFunction &mf,
1652 bool hasReadyFilter,
1653 bool tracksrp,
1654 bool srcorder,
1655 const TargetInstrInfo *tii,
1656 const TargetRegisterInfo *tri,
1657 const TargetLowering *tli)
1658 : SchedulingPriorityQueue(hasReadyFilter),
1659 CurQueueId(0), TracksRegPressure(tracksrp), SrcOrder(srcorder),
1660 MF(mf), TII(tii), TRI(tri), TLI(tli), scheduleDAG(nullptr) {
1661 if (TracksRegPressure) {
1662 unsigned NumRC = TRI->getNumRegClasses();
1663 RegLimit.resize(NumRC);
1664 RegPressure.resize(NumRC);
1665 std::fill(RegLimit.begin(), RegLimit.end(), 0);
1666 std::fill(RegPressure.begin(), RegPressure.end(), 0);
1667 for (const TargetRegisterClass *RC : TRI->regclasses())
1668 RegLimit[RC->getID()] = tri->getRegPressureLimit(RC, MF);
1669 }
1670 }
1671
1672 void setScheduleDAG(ScheduleDAGRRList *scheduleDag) {
1673 scheduleDAG = scheduleDag;
1674 }
1675
1676 ScheduleHazardRecognizer* getHazardRec() {
1677 return scheduleDAG->getHazardRec();
1678 }
1679
1680 void initNodes(std::vector<SUnit> &sunits) override;
1681
1682 void addNode(const SUnit *SU) override;
1683
1684 void updateNode(const SUnit *SU) override;
1685
1686 void releaseState() override {
1687 SUnits = nullptr;
1688 SethiUllmanNumbers.clear();
1689 std::fill(RegPressure.begin(), RegPressure.end(), 0);
1690 }
1691
1692 unsigned getNodePriority(const SUnit *SU) const;
1693
1694 unsigned getNodeOrdering(const SUnit *SU) const {
1695 if (!SU->getNode()) return 0;
1696
1697 return SU->getNode()->getIROrder();
1698 }
1699
1700 bool empty() const override { return Queue.empty(); }
1701
1702 void push(SUnit *U) override {
1703 assert(!U->NodeQueueId && "Node in the queue already")((!U->NodeQueueId && "Node in the queue already") ?
static_cast<void> (0) : __assert_fail ("!U->NodeQueueId && \"Node in the queue already\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 1703, __PRETTY_FUNCTION__))
;
1704 U->NodeQueueId = ++CurQueueId;
1705 Queue.push_back(U);
1706 }
1707
1708 void remove(SUnit *SU) override {
1709 assert(!Queue.empty() && "Queue is empty!")((!Queue.empty() && "Queue is empty!") ? static_cast<
void> (0) : __assert_fail ("!Queue.empty() && \"Queue is empty!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 1709, __PRETTY_FUNCTION__))
;
1710 assert(SU->NodeQueueId != 0 && "Not in queue!")((SU->NodeQueueId != 0 && "Not in queue!") ? static_cast
<void> (0) : __assert_fail ("SU->NodeQueueId != 0 && \"Not in queue!\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 1710, __PRETTY_FUNCTION__))
;
1711 std::vector<SUnit *>::iterator I = find(Queue, SU);
1712 if (I != std::prev(Queue.end()))
1713 std::swap(*I, Queue.back());
1714 Queue.pop_back();
1715 SU->NodeQueueId = 0;
1716 }
1717
1718 bool tracksRegPressure() const override { return TracksRegPressure; }
1719
1720 void dumpRegPressure() const;
1721
1722 bool HighRegPressure(const SUnit *SU) const;
1723
1724 bool MayReduceRegPressure(SUnit *SU) const;
1725
1726 int RegPressureDiff(SUnit *SU, unsigned &LiveUses) const;
1727
1728 void scheduledNode(SUnit *SU) override;
1729
1730 void unscheduledNode(SUnit *SU) override;
1731
1732protected:
1733 bool canClobber(const SUnit *SU, const SUnit *Op);
1734 void AddPseudoTwoAddrDeps();
1735 void PrescheduleNodesWithMultipleUses();
1736 void CalculateSethiUllmanNumbers();
1737};
1738
1739template<class SF>
1740static SUnit *popFromQueueImpl(std::vector<SUnit*> &Q, SF &Picker) {
1741 std::vector<SUnit *>::iterator Best = Q.begin();
1742 for (auto I = std::next(Q.begin()), E = Q.end(); I != E; ++I)
1743 if (Picker(*Best, *I))
1744 Best = I;
1745 SUnit *V = *Best;
1746 if (Best != std::prev(Q.end()))
1747 std::swap(*Best, Q.back());
1748 Q.pop_back();
1749 return V;
1750}
1751
1752template<class SF>
1753SUnit *popFromQueue(std::vector<SUnit*> &Q, SF &Picker, ScheduleDAG *DAG) {
1754#ifndef NDEBUG
1755 if (DAG->StressSched) {
1756 reverse_sort<SF> RPicker(Picker);
1757 return popFromQueueImpl(Q, RPicker);
1758 }
1759#endif
1760 (void)DAG;
1761 return popFromQueueImpl(Q, Picker);
1762}
1763
1764template<class SF>
1765class RegReductionPriorityQueue : public RegReductionPQBase {
1766 SF Picker;
1767
1768public:
1769 RegReductionPriorityQueue(MachineFunction &mf,
1770 bool tracksrp,
1771 bool srcorder,
1772 const TargetInstrInfo *tii,
1773 const TargetRegisterInfo *tri,
1774 const TargetLowering *tli)
1775 : RegReductionPQBase(mf, SF::HasReadyFilter, tracksrp, srcorder,
1776 tii, tri, tli),
1777 Picker(this) {}
1778
1779 bool isBottomUp() const override { return SF::IsBottomUp; }
1780
1781 bool isReady(SUnit *U) const override {
1782 return Picker.HasReadyFilter && Picker.isReady(U, getCurCycle());
1783 }
1784
1785 SUnit *pop() override {
1786 if (Queue.empty()) return nullptr;
1787
1788 SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);
1789 V->NodeQueueId = 0;
1790 return V;
1791 }
1792
1793#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1794 LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void dump(ScheduleDAG *DAG) const override {
1795 // Emulate pop() without clobbering NodeQueueIds.
1796 std::vector<SUnit*> DumpQueue = Queue;
1797 SF DumpPicker = Picker;
1798 while (!DumpQueue.empty()) {
1799 SUnit *SU = popFromQueue(DumpQueue, DumpPicker, scheduleDAG);
1800 dbgs() << "Height " << SU->getHeight() << ": ";
1801 SU->dump(DAG);
1802 }
1803 }
1804#endif
1805};
1806
1807typedef RegReductionPriorityQueue<bu_ls_rr_sort>
1808BURegReductionPriorityQueue;
1809
1810typedef RegReductionPriorityQueue<src_ls_rr_sort>
1811SrcRegReductionPriorityQueue;
1812
1813typedef RegReductionPriorityQueue<hybrid_ls_rr_sort>
1814HybridBURRPriorityQueue;
1815
1816typedef RegReductionPriorityQueue<ilp_ls_rr_sort>
1817ILPBURRPriorityQueue;
1818} // end anonymous namespace
1819
1820//===----------------------------------------------------------------------===//
1821// Static Node Priority for Register Pressure Reduction
1822//===----------------------------------------------------------------------===//
1823
1824// Check for special nodes that bypass scheduling heuristics.
1825// Currently this pushes TokenFactor nodes down, but may be used for other
1826// pseudo-ops as well.
1827//
1828// Return -1 to schedule right above left, 1 for left above right.
1829// Return 0 if no bias exists.
1830static int checkSpecialNodes(const SUnit *left, const SUnit *right) {
1831 bool LSchedLow = left->isScheduleLow;
1832 bool RSchedLow = right->isScheduleLow;
1833 if (LSchedLow != RSchedLow)
1834 return LSchedLow < RSchedLow ? 1 : -1;
1835 return 0;
1836}
1837
1838/// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
1839/// Smaller number is the higher priority.
1840static unsigned
1841CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) {
1842 unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum];
1843 if (SethiUllmanNumber != 0)
1844 return SethiUllmanNumber;
1845
1846 unsigned Extra = 0;
1847 for (const SDep &Pred : SU->Preds) {
1848 if (Pred.isCtrl()) continue; // ignore chain preds
1849 SUnit *PredSU = Pred.getSUnit();
1850 unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU, SUNumbers);
1851 if (PredSethiUllman > SethiUllmanNumber) {
1852 SethiUllmanNumber = PredSethiUllman;
1853 Extra = 0;
1854 } else if (PredSethiUllman == SethiUllmanNumber)
1855 ++Extra;
1856 }
1857
1858 SethiUllmanNumber += Extra;
1859
1860 if (SethiUllmanNumber == 0)
1861 SethiUllmanNumber = 1;
1862
1863 return SethiUllmanNumber;
1864}
1865
1866/// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
1867/// scheduling units.
1868void RegReductionPQBase::CalculateSethiUllmanNumbers() {
1869 SethiUllmanNumbers.assign(SUnits->size(), 0);
1870
1871 for (const SUnit &SU : *SUnits)
1872 CalcNodeSethiUllmanNumber(&SU, SethiUllmanNumbers);
1873}
1874
1875void RegReductionPQBase::addNode(const SUnit *SU) {
1876 unsigned SUSize = SethiUllmanNumbers.size();
1877 if (SUnits->size() > SUSize)
1878 SethiUllmanNumbers.resize(SUSize*2, 0);
1879 CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
1880}
1881
1882void RegReductionPQBase::updateNode(const SUnit *SU) {
1883 SethiUllmanNumbers[SU->NodeNum] = 0;
1884 CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
1885}
1886
1887// Lower priority means schedule further down. For bottom-up scheduling, lower
1888// priority SUs are scheduled before higher priority SUs.
1889unsigned RegReductionPQBase::getNodePriority(const SUnit *SU) const {
1890 assert(SU->NodeNum < SethiUllmanNumbers.size())((SU->NodeNum < SethiUllmanNumbers.size()) ? static_cast
<void> (0) : __assert_fail ("SU->NodeNum < SethiUllmanNumbers.size()"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 1890, __PRETTY_FUNCTION__))
;
1891 unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0;
1892 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
1893 // CopyToReg should be close to its uses to facilitate coalescing and
1894 // avoid spilling.
1895 return 0;
1896 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
1897 Opc == TargetOpcode::SUBREG_TO_REG ||
1898 Opc == TargetOpcode::INSERT_SUBREG)
1899 // EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG nodes should be
1900 // close to their uses to facilitate coalescing.
1901 return 0;
1902 if (SU->NumSuccs == 0 && SU->NumPreds != 0)
1903 // If SU does not have a register use, i.e. it doesn't produce a value
1904 // that would be consumed (e.g. store), then it terminates a chain of
1905 // computation. Give it a large SethiUllman number so it will be
1906 // scheduled right before its predecessors that it doesn't lengthen
1907 // their live ranges.
1908 return 0xffff;
1909 if (SU->NumPreds == 0 && SU->NumSuccs != 0)
1910 // If SU does not have a register def, schedule it close to its uses
1911 // because it does not lengthen any live ranges.
1912 return 0;
1913#if 1
1914 return SethiUllmanNumbers[SU->NodeNum];
1915#else
1916 unsigned Priority = SethiUllmanNumbers[SU->NodeNum];
1917 if (SU->isCallOp) {
1918 // FIXME: This assumes all of the defs are used as call operands.
1919 int NP = (int)Priority - SU->getNode()->getNumValues();
1920 return (NP > 0) ? NP : 0;
1921 }
1922 return Priority;
1923#endif
1924}
1925
1926//===----------------------------------------------------------------------===//
1927// Register Pressure Tracking
1928//===----------------------------------------------------------------------===//
1929
1930#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1931LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void RegReductionPQBase::dumpRegPressure() const {
1932 for (const TargetRegisterClass *RC : TRI->regclasses()) {
1933 unsigned Id = RC->getID();
1934 unsigned RP = RegPressure[Id];
1935 if (!RP) continue;
1936 DEBUG(dbgs() << TRI->getRegClassName(RC) << ": " << RP << " / "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << TRI->getRegClassName(RC
) << ": " << RP << " / " << RegLimit[
Id] << '\n'; } } while (false)
1937 << RegLimit[Id] << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << TRI->getRegClassName(RC
) << ": " << RP << " / " << RegLimit[
Id] << '\n'; } } while (false)
;
1938 }
1939}
1940#endif
1941
1942bool RegReductionPQBase::HighRegPressure(const SUnit *SU) const {
1943 if (!TLI)
1944 return false;
1945
1946 for (const SDep &Pred : SU->Preds) {
1947 if (Pred.isCtrl())
1948 continue;
1949 SUnit *PredSU = Pred.getSUnit();
1950 // NumRegDefsLeft is zero when enough uses of this node have been scheduled
1951 // to cover the number of registers defined (they are all live).
1952 if (PredSU->NumRegDefsLeft == 0) {
1953 continue;
1954 }
1955 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);
1956 RegDefPos.IsValid(); RegDefPos.Advance()) {
1957 unsigned RCId, Cost;
1958 GetCostForDef(RegDefPos, TLI, TII, TRI, RCId, Cost, MF);
1959
1960 if ((RegPressure[RCId] + Cost) >= RegLimit[RCId])
1961 return true;
1962 }
1963 }
1964 return false;
1965}
1966
1967bool RegReductionPQBase::MayReduceRegPressure(SUnit *SU) const {
1968 const SDNode *N = SU->getNode();
1969
1970 if (!N->isMachineOpcode() || !SU->NumSuccs)
1971 return false;
1972
1973 unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
1974 for (unsigned i = 0; i != NumDefs; ++i) {
1975 MVT VT = N->getSimpleValueType(i);
1976 if (!N->hasAnyUseOfValue(i))
1977 continue;
1978 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
1979 if (RegPressure[RCId] >= RegLimit[RCId])
1980 return true;
1981 }
1982 return false;
1983}
1984
1985// Compute the register pressure contribution by this instruction by count up
1986// for uses that are not live and down for defs. Only count register classes
1987// that are already under high pressure. As a side effect, compute the number of
1988// uses of registers that are already live.
1989//
1990// FIXME: This encompasses the logic in HighRegPressure and MayReduceRegPressure
1991// so could probably be factored.
1992int RegReductionPQBase::RegPressureDiff(SUnit *SU, unsigned &LiveUses) const {
1993 LiveUses = 0;
1994 int PDiff = 0;
1995 for (const SDep &Pred : SU->Preds) {
1996 if (Pred.isCtrl())
1997 continue;
1998 SUnit *PredSU = Pred.getSUnit();
1999 // NumRegDefsLeft is zero when enough uses of this node have been scheduled
2000 // to cover the number of registers defined (they are all live).
2001 if (PredSU->NumRegDefsLeft == 0) {
2002 if (PredSU->getNode()->isMachineOpcode())
2003 ++LiveUses;
2004 continue;
2005 }
2006 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);
2007 RegDefPos.IsValid(); RegDefPos.Advance()) {
2008 MVT VT = RegDefPos.GetValue();
2009 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2010 if (RegPressure[RCId] >= RegLimit[RCId])
2011 ++PDiff;
2012 }
2013 }
2014 const SDNode *N = SU->getNode();
2015
2016 if (!N || !N->isMachineOpcode() || !SU->NumSuccs)
2017 return PDiff;
2018
2019 unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
2020 for (unsigned i = 0; i != NumDefs; ++i) {
2021 MVT VT = N->getSimpleValueType(i);
2022 if (!N->hasAnyUseOfValue(i))
2023 continue;
2024 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2025 if (RegPressure[RCId] >= RegLimit[RCId])
2026 --PDiff;
2027 }
2028 return PDiff;
2029}
2030
2031void RegReductionPQBase::scheduledNode(SUnit *SU) {
2032 if (!TracksRegPressure)
2033 return;
2034
2035 if (!SU->getNode())
2036 return;
2037
2038 for (const SDep &Pred : SU->Preds) {
2039 if (Pred.isCtrl())
2040 continue;
2041 SUnit *PredSU = Pred.getSUnit();
2042 // NumRegDefsLeft is zero when enough uses of this node have been scheduled
2043 // to cover the number of registers defined (they are all live).
2044 if (PredSU->NumRegDefsLeft == 0) {
2045 continue;
2046 }
2047 // FIXME: The ScheduleDAG currently loses information about which of a
2048 // node's values is consumed by each dependence. Consequently, if the node
2049 // defines multiple register classes, we don't know which to pressurize
2050 // here. Instead the following loop consumes the register defs in an
2051 // arbitrary order. At least it handles the common case of clustered loads
2052 // to the same class. For precise liveness, each SDep needs to indicate the
2053 // result number. But that tightly couples the ScheduleDAG with the
2054 // SelectionDAG making updates tricky. A simpler hack would be to attach a
2055 // value type or register class to SDep.
2056 //
2057 // The most important aspect of register tracking is balancing the increase
2058 // here with the reduction further below. Note that this SU may use multiple
2059 // defs in PredSU. The can't be determined here, but we've already
2060 // compensated by reducing NumRegDefsLeft in PredSU during
2061 // ScheduleDAGSDNodes::AddSchedEdges.
2062 --PredSU->NumRegDefsLeft;
2063 unsigned SkipRegDefs = PredSU->NumRegDefsLeft;
2064 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);
2065 RegDefPos.IsValid(); RegDefPos.Advance(), --SkipRegDefs) {
2066 if (SkipRegDefs)
2067 continue;
2068
2069 unsigned RCId, Cost;
2070 GetCostForDef(RegDefPos, TLI, TII, TRI, RCId, Cost, MF);
2071 RegPressure[RCId] += Cost;
2072 break;
2073 }
2074 }
2075
2076 // We should have this assert, but there may be dead SDNodes that never
2077 // materialize as SUnits, so they don't appear to generate liveness.
2078 //assert(SU->NumRegDefsLeft == 0 && "not all regdefs have scheduled uses");
2079 int SkipRegDefs = (int)SU->NumRegDefsLeft;
2080 for (ScheduleDAGSDNodes::RegDefIter RegDefPos(SU, scheduleDAG);
2081 RegDefPos.IsValid(); RegDefPos.Advance(), --SkipRegDefs) {
2082 if (SkipRegDefs > 0)
2083 continue;
2084 unsigned RCId, Cost;
2085 GetCostForDef(RegDefPos, TLI, TII, TRI, RCId, Cost, MF);
2086 if (RegPressure[RCId] < Cost) {
2087 // Register pressure tracking is imprecise. This can happen. But we try
2088 // hard not to let it happen because it likely results in poor scheduling.
2089 DEBUG(dbgs() << " SU(" << SU->NodeNum << ") has too many regdefs\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " SU(" << SU->NodeNum
<< ") has too many regdefs\n"; } } while (false)
;
2090 RegPressure[RCId] = 0;
2091 }
2092 else {
2093 RegPressure[RCId] -= Cost;
2094 }
2095 }
2096 DEBUG(dumpRegPressure())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dumpRegPressure(); } } while (false)
;
2097}
2098
2099void RegReductionPQBase::unscheduledNode(SUnit *SU) {
2100 if (!TracksRegPressure)
2101 return;
2102
2103 const SDNode *N = SU->getNode();
2104 if (!N) return;
2105
2106 if (!N->isMachineOpcode()) {
2107 if (N->getOpcode() != ISD::CopyToReg)
2108 return;
2109 } else {
2110 unsigned Opc = N->getMachineOpcode();
2111 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2112 Opc == TargetOpcode::INSERT_SUBREG ||
2113 Opc == TargetOpcode::SUBREG_TO_REG ||
2114 Opc == TargetOpcode::REG_SEQUENCE ||
2115 Opc == TargetOpcode::IMPLICIT_DEF)
2116 return;
2117 }
2118
2119 for (const SDep &Pred : SU->Preds) {
2120 if (Pred.isCtrl())
2121 continue;
2122 SUnit *PredSU = Pred.getSUnit();
2123 // NumSuccsLeft counts all deps. Don't compare it with NumSuccs which only
2124 // counts data deps.
2125 if (PredSU->NumSuccsLeft != PredSU->Succs.size())
2126 continue;
2127 const SDNode *PN = PredSU->getNode();
2128 if (!PN->isMachineOpcode()) {
2129 if (PN->getOpcode() == ISD::CopyFromReg) {
2130 MVT VT = PN->getSimpleValueType(0);
2131 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2132 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
2133 }
2134 continue;
2135 }
2136 unsigned POpc = PN->getMachineOpcode();
2137 if (POpc == TargetOpcode::IMPLICIT_DEF)
2138 continue;
2139 if (POpc == TargetOpcode::EXTRACT_SUBREG ||
2140 POpc == TargetOpcode::INSERT_SUBREG ||
2141 POpc == TargetOpcode::SUBREG_TO_REG) {
2142 MVT VT = PN->getSimpleValueType(0);
2143 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2144 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
2145 continue;
2146 }
2147 unsigned NumDefs = TII->get(PN->getMachineOpcode()).getNumDefs();
2148 for (unsigned i = 0; i != NumDefs; ++i) {
2149 MVT VT = PN->getSimpleValueType(i);
2150 if (!PN->hasAnyUseOfValue(i))
2151 continue;
2152 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2153 if (RegPressure[RCId] < TLI->getRepRegClassCostFor(VT))
2154 // Register pressure tracking is imprecise. This can happen.
2155 RegPressure[RCId] = 0;
2156 else
2157 RegPressure[RCId] -= TLI->getRepRegClassCostFor(VT);
2158 }
2159 }
2160
2161 // Check for isMachineOpcode() as PrescheduleNodesWithMultipleUses()
2162 // may transfer data dependencies to CopyToReg.
2163 if (SU->NumSuccs && N->isMachineOpcode()) {
2164 unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
2165 for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
2166 MVT VT = N->getSimpleValueType(i);
2167 if (VT == MVT::Glue || VT == MVT::Other)
2168 continue;
2169 if (!N->hasAnyUseOfValue(i))
2170 continue;
2171 unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
2172 RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
2173 }
2174 }
2175
2176 DEBUG(dumpRegPressure())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dumpRegPressure(); } } while (false)
;
2177}
2178
2179//===----------------------------------------------------------------------===//
2180// Dynamic Node Priority for Register Pressure Reduction
2181//===----------------------------------------------------------------------===//
2182
2183/// closestSucc - Returns the scheduled cycle of the successor which is
2184/// closest to the current cycle.
2185static unsigned closestSucc(const SUnit *SU) {
2186 unsigned MaxHeight = 0;
2187 for (const SDep &Succ : SU->Succs) {
2188 if (Succ.isCtrl()) continue; // ignore chain succs
2189 unsigned Height = Succ.getSUnit()->getHeight();
2190 // If there are bunch of CopyToRegs stacked up, they should be considered
2191 // to be at the same position.
2192 if (Succ.getSUnit()->getNode() &&
2193 Succ.getSUnit()->getNode()->getOpcode() == ISD::CopyToReg)
2194 Height = closestSucc(Succ.getSUnit())+1;
2195 if (Height > MaxHeight)
2196 MaxHeight = Height;
2197 }
2198 return MaxHeight;
2199}
2200
2201/// calcMaxScratches - Returns an cost estimate of the worse case requirement
2202/// for scratch registers, i.e. number of data dependencies.
2203static unsigned calcMaxScratches(const SUnit *SU) {
2204 unsigned Scratches = 0;
2205 for (const SDep &Pred : SU->Preds) {
2206 if (Pred.isCtrl()) continue; // ignore chain preds
2207 Scratches++;
2208 }
2209 return Scratches;
2210}
2211
2212/// hasOnlyLiveInOpers - Return true if SU has only value predecessors that are
2213/// CopyFromReg from a virtual register.
2214static bool hasOnlyLiveInOpers(const SUnit *SU) {
2215 bool RetVal = false;
2216 for (const SDep &Pred : SU->Preds) {
2217 if (Pred.isCtrl()) continue;
2218 const SUnit *PredSU = Pred.getSUnit();
2219 if (PredSU->getNode() &&
2220 PredSU->getNode()->getOpcode() == ISD::CopyFromReg) {
2221 unsigned Reg =
2222 cast<RegisterSDNode>(PredSU->getNode()->getOperand(1))->getReg();
2223 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
2224 RetVal = true;
2225 continue;
2226 }
2227 }
2228 return false;
2229 }
2230 return RetVal;
2231}
2232
2233/// hasOnlyLiveOutUses - Return true if SU has only value successors that are
2234/// CopyToReg to a virtual register. This SU def is probably a liveout and
2235/// it has no other use. It should be scheduled closer to the terminator.
2236static bool hasOnlyLiveOutUses(const SUnit *SU) {
2237 bool RetVal = false;
2238 for (const SDep &Succ : SU->Succs) {
2239 if (Succ.isCtrl()) continue;
2240 const SUnit *SuccSU = Succ.getSUnit();
2241 if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg) {
2242 unsigned Reg =
2243 cast<RegisterSDNode>(SuccSU->getNode()->getOperand(1))->getReg();
2244 if (TargetRegisterInfo::isVirtualRegister(Reg)) {
2245 RetVal = true;
2246 continue;
2247 }
2248 }
2249 return false;
2250 }
2251 return RetVal;
2252}
2253
2254// Set isVRegCycle for a node with only live in opers and live out uses. Also
2255// set isVRegCycle for its CopyFromReg operands.
2256//
2257// This is only relevant for single-block loops, in which case the VRegCycle
2258// node is likely an induction variable in which the operand and target virtual
2259// registers should be coalesced (e.g. pre/post increment values). Setting the
2260// isVRegCycle flag helps the scheduler prioritize other uses of the same
2261// CopyFromReg so that this node becomes the virtual register "kill". This
2262// avoids interference between the values live in and out of the block and
2263// eliminates a copy inside the loop.
2264static void initVRegCycle(SUnit *SU) {
2265 if (DisableSchedVRegCycle)
2266 return;
2267
2268 if (!hasOnlyLiveInOpers(SU) || !hasOnlyLiveOutUses(SU))
2269 return;
2270
2271 DEBUG(dbgs() << "VRegCycle: SU(" << SU->NodeNum << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "VRegCycle: SU(" <<
SU->NodeNum << ")\n"; } } while (false)
;
2272
2273 SU->isVRegCycle = true;
2274
2275 for (const SDep &Pred : SU->Preds) {
2276 if (Pred.isCtrl()) continue;
2277 Pred.getSUnit()->isVRegCycle = true;
2278 }
2279}
2280
2281// After scheduling the definition of a VRegCycle, clear the isVRegCycle flag of
2282// CopyFromReg operands. We should no longer penalize other uses of this VReg.
2283static void resetVRegCycle(SUnit *SU) {
2284 if (!SU->isVRegCycle)
2285 return;
2286
2287 for (const SDep &Pred : SU->Preds) {
2288 if (Pred.isCtrl()) continue; // ignore chain preds
2289 SUnit *PredSU = Pred.getSUnit();
2290 if (PredSU->isVRegCycle) {
2291 assert(PredSU->getNode()->getOpcode() == ISD::CopyFromReg &&((PredSU->getNode()->getOpcode() == ISD::CopyFromReg &&
"VRegCycle def must be CopyFromReg") ? static_cast<void>
(0) : __assert_fail ("PredSU->getNode()->getOpcode() == ISD::CopyFromReg && \"VRegCycle def must be CopyFromReg\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 2292, __PRETTY_FUNCTION__))
2292 "VRegCycle def must be CopyFromReg")((PredSU->getNode()->getOpcode() == ISD::CopyFromReg &&
"VRegCycle def must be CopyFromReg") ? static_cast<void>
(0) : __assert_fail ("PredSU->getNode()->getOpcode() == ISD::CopyFromReg && \"VRegCycle def must be CopyFromReg\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 2292, __PRETTY_FUNCTION__))
;
2293 Pred.getSUnit()->isVRegCycle = false;
2294 }
2295 }
2296}
2297
2298// Return true if this SUnit uses a CopyFromReg node marked as a VRegCycle. This
2299// means a node that defines the VRegCycle has not been scheduled yet.
2300static bool hasVRegCycleUse(const SUnit *SU) {
2301 // If this SU also defines the VReg, don't hoist it as a "use".
2302 if (SU->isVRegCycle)
2303 return false;
2304
2305 for (const SDep &Pred : SU->Preds) {
2306 if (Pred.isCtrl()) continue; // ignore chain preds
2307 if (Pred.getSUnit()->isVRegCycle &&
2308 Pred.getSUnit()->getNode()->getOpcode() == ISD::CopyFromReg) {
2309 DEBUG(dbgs() << " VReg cycle use: SU (" << SU->NodeNum << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " VReg cycle use: SU (" <<
SU->NodeNum << ")\n"; } } while (false)
;
2310 return true;
2311 }
2312 }
2313 return false;
2314}
2315
2316// Check for either a dependence (latency) or resource (hazard) stall.
2317//
2318// Note: The ScheduleHazardRecognizer interface requires a non-const SU.
2319static bool BUHasStall(SUnit *SU, int Height, RegReductionPQBase *SPQ) {
2320 if ((int)SPQ->getCurCycle() < Height) return true;
2321 if (SPQ->getHazardRec()->getHazardType(SU, 0)
2322 != ScheduleHazardRecognizer::NoHazard)
2323 return true;
2324 return false;
2325}
2326
2327// Return -1 if left has higher priority, 1 if right has higher priority.
2328// Return 0 if latency-based priority is equivalent.
2329static int BUCompareLatency(SUnit *left, SUnit *right, bool checkPref,
2330 RegReductionPQBase *SPQ) {
2331 // Scheduling an instruction that uses a VReg whose postincrement has not yet
2332 // been scheduled will induce a copy. Model this as an extra cycle of latency.
2333 int LPenalty = hasVRegCycleUse(left) ? 1 : 0;
2334 int RPenalty = hasVRegCycleUse(right) ? 1 : 0;
2335 int LHeight = (int)left->getHeight() + LPenalty;
2336 int RHeight = (int)right->getHeight() + RPenalty;
2337
2338 bool LStall = (!checkPref || left->SchedulingPref == Sched::ILP) &&
2339 BUHasStall(left, LHeight, SPQ);
2340 bool RStall = (!checkPref || right->SchedulingPref == Sched::ILP) &&
2341 BUHasStall(right, RHeight, SPQ);
2342
2343 // If scheduling one of the node will cause a pipeline stall, delay it.
2344 // If scheduling either one of the node will cause a pipeline stall, sort
2345 // them according to their height.
2346 if (LStall) {
2347 if (!RStall)
2348 return 1;
2349 if (LHeight != RHeight)
2350 return LHeight > RHeight ? 1 : -1;
2351 } else if (RStall)
2352 return -1;
2353
2354 // If either node is scheduling for latency, sort them by height/depth
2355 // and latency.
2356 if (!checkPref || (left->SchedulingPref == Sched::ILP ||
2357 right->SchedulingPref == Sched::ILP)) {
2358 // If neither instruction stalls (!LStall && !RStall) and HazardRecognizer
2359 // is enabled, grouping instructions by cycle, then its height is already
2360 // covered so only its depth matters. We also reach this point if both stall
2361 // but have the same height.
2362 if (!SPQ->getHazardRec()->isEnabled()) {
2363 if (LHeight != RHeight)
2364 return LHeight > RHeight ? 1 : -1;
2365 }
2366 int LDepth = left->getDepth() - LPenalty;
2367 int RDepth = right->getDepth() - RPenalty;
2368 if (LDepth != RDepth) {
2369 DEBUG(dbgs() << " Comparing latency of SU (" << left->NodeNumdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Comparing latency of SU ("
<< left->NodeNum << ") depth " << LDepth
<< " vs SU (" << right->NodeNum << ") depth "
<< RDepth << "\n"; } } while (false)
2370 << ") depth " << LDepth << " vs SU (" << right->NodeNumdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Comparing latency of SU ("
<< left->NodeNum << ") depth " << LDepth
<< " vs SU (" << right->NodeNum << ") depth "
<< RDepth << "\n"; } } while (false)
2371 << ") depth " << RDepth << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Comparing latency of SU ("
<< left->NodeNum << ") depth " << LDepth
<< " vs SU (" << right->NodeNum << ") depth "
<< RDepth << "\n"; } } while (false)
;
2372 return LDepth < RDepth ? 1 : -1;
2373 }
2374 if (left->Latency != right->Latency)
2375 return left->Latency > right->Latency ? 1 : -1;
2376 }
2377 return 0;
2378}
2379
2380static bool BURRSort(SUnit *left, SUnit *right, RegReductionPQBase *SPQ) {
2381 // Schedule physical register definitions close to their use. This is
2382 // motivated by microarchitectures that can fuse cmp+jump macro-ops. But as
2383 // long as shortening physreg live ranges is generally good, we can defer
2384 // creating a subtarget hook.
2385 if (!DisableSchedPhysRegJoin) {
2386 bool LHasPhysReg = left->hasPhysRegDefs;
2387 bool RHasPhysReg = right->hasPhysRegDefs;
2388 if (LHasPhysReg != RHasPhysReg) {
2389 #ifndef NDEBUG
2390 static const char *const PhysRegMsg[] = { " has no physreg",
2391 " defines a physreg" };
2392 #endif
2393 DEBUG(dbgs() << " SU (" << left->NodeNum << ") "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " SU (" << left->
NodeNum << ") " << PhysRegMsg[LHasPhysReg] <<
" SU(" << right->NodeNum << ") " << PhysRegMsg
[RHasPhysReg] << "\n"; } } while (false)
2394 << PhysRegMsg[LHasPhysReg] << " SU(" << right->NodeNum << ") "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " SU (" << left->
NodeNum << ") " << PhysRegMsg[LHasPhysReg] <<
" SU(" << right->NodeNum << ") " << PhysRegMsg
[RHasPhysReg] << "\n"; } } while (false)
2395 << PhysRegMsg[RHasPhysReg] << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " SU (" << left->
NodeNum << ") " << PhysRegMsg[LHasPhysReg] <<
" SU(" << right->NodeNum << ") " << PhysRegMsg
[RHasPhysReg] << "\n"; } } while (false)
;
2396 return LHasPhysReg < RHasPhysReg;
2397 }
2398 }
2399
2400 // Prioritize by Sethi-Ulmann number and push CopyToReg nodes down.
2401 unsigned LPriority = SPQ->getNodePriority(left);
2402 unsigned RPriority = SPQ->getNodePriority(right);
2403
2404 // Be really careful about hoisting call operands above previous calls.
2405 // Only allows it if it would reduce register pressure.
2406 if (left->isCall && right->isCallOp) {
2407 unsigned RNumVals = right->getNode()->getNumValues();
2408 RPriority = (RPriority > RNumVals) ? (RPriority - RNumVals) : 0;
2409 }
2410 if (right->isCall && left->isCallOp) {
2411 unsigned LNumVals = left->getNode()->getNumValues();
2412 LPriority = (LPriority > LNumVals) ? (LPriority - LNumVals) : 0;
2413 }
2414
2415 if (LPriority != RPriority)
2416 return LPriority > RPriority;
2417
2418 // One or both of the nodes are calls and their sethi-ullman numbers are the
2419 // same, then keep source order.
2420 if (left->isCall || right->isCall) {
2421 unsigned LOrder = SPQ->getNodeOrdering(left);
2422 unsigned ROrder = SPQ->getNodeOrdering(right);
2423
2424 // Prefer an ordering where the lower the non-zero order number, the higher
2425 // the preference.
2426 if ((LOrder || ROrder) && LOrder != ROrder)
2427 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
2428 }
2429
2430 // Try schedule def + use closer when Sethi-Ullman numbers are the same.
2431 // e.g.
2432 // t1 = op t2, c1
2433 // t3 = op t4, c2
2434 //
2435 // and the following instructions are both ready.
2436 // t2 = op c3
2437 // t4 = op c4
2438 //
2439 // Then schedule t2 = op first.
2440 // i.e.
2441 // t4 = op c4
2442 // t2 = op c3
2443 // t1 = op t2, c1
2444 // t3 = op t4, c2
2445 //
2446 // This creates more short live intervals.
2447 unsigned LDist = closestSucc(left);
2448 unsigned RDist = closestSucc(right);
2449 if (LDist != RDist)
2450 return LDist < RDist;
2451
2452 // How many registers becomes live when the node is scheduled.
2453 unsigned LScratch = calcMaxScratches(left);
2454 unsigned RScratch = calcMaxScratches(right);
2455 if (LScratch != RScratch)
2456 return LScratch > RScratch;
2457
2458 // Comparing latency against a call makes little sense unless the node
2459 // is register pressure-neutral.
2460 if ((left->isCall && RPriority > 0) || (right->isCall && LPriority > 0))
2461 return (left->NodeQueueId > right->NodeQueueId);
2462
2463 // Do not compare latencies when one or both of the nodes are calls.
2464 if (!DisableSchedCycles &&
2465 !(left->isCall || right->isCall)) {
2466 int result = BUCompareLatency(left, right, false /*checkPref*/, SPQ);
2467 if (result != 0)
2468 return result > 0;
2469 }
2470 else {
2471 if (left->getHeight() != right->getHeight())
2472 return left->getHeight() > right->getHeight();
2473
2474 if (left->getDepth() != right->getDepth())
2475 return left->getDepth() < right->getDepth();
2476 }
2477
2478 assert(left->NodeQueueId && right->NodeQueueId &&((left->NodeQueueId && right->NodeQueueId &&
"NodeQueueId cannot be zero") ? static_cast<void> (0) :
__assert_fail ("left->NodeQueueId && right->NodeQueueId && \"NodeQueueId cannot be zero\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 2479, __PRETTY_FUNCTION__))
2479 "NodeQueueId cannot be zero")((left->NodeQueueId && right->NodeQueueId &&
"NodeQueueId cannot be zero") ? static_cast<void> (0) :
__assert_fail ("left->NodeQueueId && right->NodeQueueId && \"NodeQueueId cannot be zero\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 2479, __PRETTY_FUNCTION__))
;
2480 return (left->NodeQueueId > right->NodeQueueId);
2481}
2482
2483// Bottom up
2484bool bu_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2485 if (int res = checkSpecialNodes(left, right))
2486 return res > 0;
2487
2488 return BURRSort(left, right, SPQ);
2489}
2490
2491// Source order, otherwise bottom up.
2492bool src_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2493 if (int res = checkSpecialNodes(left, right))
2494 return res > 0;
2495
2496 unsigned LOrder = SPQ->getNodeOrdering(left);
2497 unsigned ROrder = SPQ->getNodeOrdering(right);
2498
2499 // Prefer an ordering where the lower the non-zero order number, the higher
2500 // the preference.
2501 if ((LOrder || ROrder) && LOrder != ROrder)
2502 return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
2503
2504 return BURRSort(left, right, SPQ);
2505}
2506
2507// If the time between now and when the instruction will be ready can cover
2508// the spill code, then avoid adding it to the ready queue. This gives long
2509// stalls highest priority and allows hoisting across calls. It should also
2510// speed up processing the available queue.
2511bool hybrid_ls_rr_sort::isReady(SUnit *SU, unsigned CurCycle) const {
2512 static const unsigned ReadyDelay = 3;
2513
2514 if (SPQ->MayReduceRegPressure(SU)) return true;
2515
2516 if (SU->getHeight() > (CurCycle + ReadyDelay)) return false;
2517
2518 if (SPQ->getHazardRec()->getHazardType(SU, -ReadyDelay)
2519 != ScheduleHazardRecognizer::NoHazard)
2520 return false;
2521
2522 return true;
2523}
2524
2525// Return true if right should be scheduled with higher priority than left.
2526bool hybrid_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2527 if (int res = checkSpecialNodes(left, right))
2528 return res > 0;
2529
2530 if (left->isCall || right->isCall)
2531 // No way to compute latency of calls.
2532 return BURRSort(left, right, SPQ);
2533
2534 bool LHigh = SPQ->HighRegPressure(left);
2535 bool RHigh = SPQ->HighRegPressure(right);
2536 // Avoid causing spills. If register pressure is high, schedule for
2537 // register pressure reduction.
2538 if (LHigh && !RHigh) {
2539 DEBUG(dbgs() << " pressure SU(" << left->NodeNum << ") > SU("do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " pressure SU(" <<
left->NodeNum << ") > SU(" << right->NodeNum
<< ")\n"; } } while (false)
2540 << right->NodeNum << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " pressure SU(" <<
left->NodeNum << ") > SU(" << right->NodeNum
<< ")\n"; } } while (false)
;
2541 return true;
2542 }
2543 else if (!LHigh && RHigh) {
2544 DEBUG(dbgs() << " pressure SU(" << right->NodeNum << ") > SU("do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " pressure SU(" <<
right->NodeNum << ") > SU(" << left->NodeNum
<< ")\n"; } } while (false)
2545 << left->NodeNum << ")\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " pressure SU(" <<
right->NodeNum << ") > SU(" << left->NodeNum
<< ")\n"; } } while (false)
;
2546 return false;
2547 }
2548 if (!LHigh && !RHigh) {
2549 int result = BUCompareLatency(left, right, true /*checkPref*/, SPQ);
2550 if (result != 0)
2551 return result > 0;
2552 }
2553 return BURRSort(left, right, SPQ);
2554}
2555
2556// Schedule as many instructions in each cycle as possible. So don't make an
2557// instruction available unless it is ready in the current cycle.
2558bool ilp_ls_rr_sort::isReady(SUnit *SU, unsigned CurCycle) const {
2559 if (SU->getHeight() > CurCycle) return false;
2560
2561 if (SPQ->getHazardRec()->getHazardType(SU, 0)
2562 != ScheduleHazardRecognizer::NoHazard)
2563 return false;
2564
2565 return true;
2566}
2567
2568static bool canEnableCoalescing(SUnit *SU) {
2569 unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0;
2570 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
2571 // CopyToReg should be close to its uses to facilitate coalescing and
2572 // avoid spilling.
2573 return true;
2574
2575 if (Opc == TargetOpcode::EXTRACT_SUBREG ||
2576 Opc == TargetOpcode::SUBREG_TO_REG ||
2577 Opc == TargetOpcode::INSERT_SUBREG)
2578 // EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG nodes should be
2579 // close to their uses to facilitate coalescing.
2580 return true;
2581
2582 if (SU->NumPreds == 0 && SU->NumSuccs != 0)
2583 // If SU does not have a register def, schedule it close to its uses
2584 // because it does not lengthen any live ranges.
2585 return true;
2586
2587 return false;
2588}
2589
2590// list-ilp is currently an experimental scheduler that allows various
2591// heuristics to be enabled prior to the normal register reduction logic.
2592bool ilp_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2593 if (int res = checkSpecialNodes(left, right))
2594 return res > 0;
2595
2596 if (left->isCall || right->isCall)
2597 // No way to compute latency of calls.
2598 return BURRSort(left, right, SPQ);
2599
2600 unsigned LLiveUses = 0, RLiveUses = 0;
2601 int LPDiff = 0, RPDiff = 0;
2602 if (!DisableSchedRegPressure || !DisableSchedLiveUses) {
2603 LPDiff = SPQ->RegPressureDiff(left, LLiveUses);
2604 RPDiff = SPQ->RegPressureDiff(right, RLiveUses);
2605 }
2606 if (!DisableSchedRegPressure && LPDiff != RPDiff) {
2607 DEBUG(dbgs() << "RegPressureDiff SU(" << left->NodeNum << "): " << LPDiffdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "RegPressureDiff SU(" <<
left->NodeNum << "): " << LPDiff << " != SU("
<< right->NodeNum << "): " << RPDiff <<
"\n"; } } while (false)
2608 << " != SU(" << right->NodeNum << "): " << RPDiff << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "RegPressureDiff SU(" <<
left->NodeNum << "): " << LPDiff << " != SU("
<< right->NodeNum << "): " << RPDiff <<
"\n"; } } while (false)
;
2609 return LPDiff > RPDiff;
2610 }
2611
2612 if (!DisableSchedRegPressure && (LPDiff > 0 || RPDiff > 0)) {
2613 bool LReduce = canEnableCoalescing(left);
2614 bool RReduce = canEnableCoalescing(right);
2615 if (LReduce && !RReduce) return false;
2616 if (RReduce && !LReduce) return true;
2617 }
2618
2619 if (!DisableSchedLiveUses && (LLiveUses != RLiveUses)) {
2620 DEBUG(dbgs() << "Live uses SU(" << left->NodeNum << "): " << LLiveUsesdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "Live uses SU(" << left
->NodeNum << "): " << LLiveUses << " != SU("
<< right->NodeNum << "): " << RLiveUses
<< "\n"; } } while (false)
2621 << " != SU(" << right->NodeNum << "): " << RLiveUses << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "Live uses SU(" << left
->NodeNum << "): " << LLiveUses << " != SU("
<< right->NodeNum << "): " << RLiveUses
<< "\n"; } } while (false)
;
2622 return LLiveUses < RLiveUses;
2623 }
2624
2625 if (!DisableSchedStalls) {
2626 bool LStall = BUHasStall(left, left->getHeight(), SPQ);
2627 bool RStall = BUHasStall(right, right->getHeight(), SPQ);
2628 if (LStall != RStall)
2629 return left->getHeight() > right->getHeight();
2630 }
2631
2632 if (!DisableSchedCriticalPath) {
2633 int spread = (int)left->getDepth() - (int)right->getDepth();
2634 if (std::abs(spread) > MaxReorderWindow) {
2635 DEBUG(dbgs() << "Depth of SU(" << left->NodeNum << "): "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "Depth of SU(" << left
->NodeNum << "): " << left->getDepth() <<
" != SU(" << right->NodeNum << "): " <<
right->getDepth() << "\n"; } } while (false)
2636 << left->getDepth() << " != SU(" << right->NodeNum << "): "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "Depth of SU(" << left
->NodeNum << "): " << left->getDepth() <<
" != SU(" << right->NodeNum << "): " <<
right->getDepth() << "\n"; } } while (false)
2637 << right->getDepth() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << "Depth of SU(" << left
->NodeNum << "): " << left->getDepth() <<
" != SU(" << right->NodeNum << "): " <<
right->getDepth() << "\n"; } } while (false)
;
2638 return left->getDepth() < right->getDepth();
2639 }
2640 }
2641
2642 if (!DisableSchedHeight && left->getHeight() != right->getHeight()) {
2643 int spread = (int)left->getHeight() - (int)right->getHeight();
2644 if (std::abs(spread) > MaxReorderWindow)
2645 return left->getHeight() > right->getHeight();
2646 }
2647
2648 return BURRSort(left, right, SPQ);
2649}
2650
2651void RegReductionPQBase::initNodes(std::vector<SUnit> &sunits) {
2652 SUnits = &sunits;
2653 // Add pseudo dependency edges for two-address nodes.
2654 if (!Disable2AddrHack)
2655 AddPseudoTwoAddrDeps();
2656 // Reroute edges to nodes with multiple uses.
2657 if (!TracksRegPressure && !SrcOrder)
2658 PrescheduleNodesWithMultipleUses();
2659 // Calculate node priorities.
2660 CalculateSethiUllmanNumbers();
2661
2662 // For single block loops, mark nodes that look like canonical IV increments.
2663 if (scheduleDAG->BB->isSuccessor(scheduleDAG->BB))
2664 for (SUnit &SU : sunits)
2665 initVRegCycle(&SU);
2666}
2667
2668//===----------------------------------------------------------------------===//
2669// Preschedule for Register Pressure
2670//===----------------------------------------------------------------------===//
2671
2672bool RegReductionPQBase::canClobber(const SUnit *SU, const SUnit *Op) {
2673 if (SU->isTwoAddress) {
2674 unsigned Opc = SU->getNode()->getMachineOpcode();
2675 const MCInstrDesc &MCID = TII->get(Opc);
2676 unsigned NumRes = MCID.getNumDefs();
2677 unsigned NumOps = MCID.getNumOperands() - NumRes;
2678 for (unsigned i = 0; i != NumOps; ++i) {
2679 if (MCID.getOperandConstraint(i+NumRes, MCOI::TIED_TO) != -1) {
2680 SDNode *DU = SU->getNode()->getOperand(i).getNode();
2681 if (DU->getNodeId() != -1 &&
2682 Op->OrigNode == &(*SUnits)[DU->getNodeId()])
2683 return true;
2684 }
2685 }
2686 }
2687 return false;
2688}
2689
2690/// canClobberReachingPhysRegUse - True if SU would clobber one of it's
2691/// successor's explicit physregs whose definition can reach DepSU.
2692/// i.e. DepSU should not be scheduled above SU.
2693static bool canClobberReachingPhysRegUse(const SUnit *DepSU, const SUnit *SU,
2694 ScheduleDAGRRList *scheduleDAG,
2695 const TargetInstrInfo *TII,
2696 const TargetRegisterInfo *TRI) {
2697 const MCPhysReg *ImpDefs
2698 = TII->get(SU->getNode()->getMachineOpcode()).getImplicitDefs();
2699 const uint32_t *RegMask = getNodeRegMask(SU->getNode());
2700 if(!ImpDefs && !RegMask)
2701 return false;
2702
2703 for (const SDep &Succ : SU->Succs) {
2704 SUnit *SuccSU = Succ.getSUnit();
2705 for (const SDep &SuccPred : SuccSU->Preds) {
2706 if (!SuccPred.isAssignedRegDep())
2707 continue;
2708
2709 if (RegMask &&
2710 MachineOperand::clobbersPhysReg(RegMask, SuccPred.getReg()) &&
2711 scheduleDAG->IsReachable(DepSU, SuccPred.getSUnit()))
2712 return true;
2713
2714 if (ImpDefs)
2715 for (const MCPhysReg *ImpDef = ImpDefs; *ImpDef; ++ImpDef)
2716 // Return true if SU clobbers this physical register use and the
2717 // definition of the register reaches from DepSU. IsReachable queries
2718 // a topological forward sort of the DAG (following the successors).
2719 if (TRI->regsOverlap(*ImpDef, SuccPred.getReg()) &&
2720 scheduleDAG->IsReachable(DepSU, SuccPred.getSUnit()))
2721 return true;
2722 }
2723 }
2724 return false;
2725}
2726
2727/// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's
2728/// physical register defs.
2729static bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU,
2730 const TargetInstrInfo *TII,
2731 const TargetRegisterInfo *TRI) {
2732 SDNode *N = SuccSU->getNode();
2733 unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
2734 const MCPhysReg *ImpDefs = TII->get(N->getMachineOpcode()).getImplicitDefs();
2735 assert(ImpDefs && "Caller should check hasPhysRegDefs")((ImpDefs && "Caller should check hasPhysRegDefs") ? static_cast
<void> (0) : __assert_fail ("ImpDefs && \"Caller should check hasPhysRegDefs\""
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 2735, __PRETTY_FUNCTION__))
;
2736 for (const SDNode *SUNode = SU->getNode(); SUNode;
2737 SUNode = SUNode->getGluedNode()) {
2738 if (!SUNode->isMachineOpcode())
2739 continue;
2740 const MCPhysReg *SUImpDefs =
2741 TII->get(SUNode->getMachineOpcode()).getImplicitDefs();
2742 const uint32_t *SURegMask = getNodeRegMask(SUNode);
2743 if (!SUImpDefs && !SURegMask)
2744 continue;
2745 for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
2746 MVT VT = N->getSimpleValueType(i);
2747 if (VT == MVT::Glue || VT == MVT::Other)
2748 continue;
2749 if (!N->hasAnyUseOfValue(i))
2750 continue;
2751 unsigned Reg = ImpDefs[i - NumDefs];
2752 if (SURegMask && MachineOperand::clobbersPhysReg(SURegMask, Reg))
2753 return true;
2754 if (!SUImpDefs)
2755 continue;
2756 for (;*SUImpDefs; ++SUImpDefs) {
2757 unsigned SUReg = *SUImpDefs;
2758 if (TRI->regsOverlap(Reg, SUReg))
2759 return true;
2760 }
2761 }
2762 }
2763 return false;
2764}
2765
2766/// PrescheduleNodesWithMultipleUses - Nodes with multiple uses
2767/// are not handled well by the general register pressure reduction
2768/// heuristics. When presented with code like this:
2769///
2770/// N
2771/// / |
2772/// / |
2773/// U store
2774/// |
2775/// ...
2776///
2777/// the heuristics tend to push the store up, but since the
2778/// operand of the store has another use (U), this would increase
2779/// the length of that other use (the U->N edge).
2780///
2781/// This function transforms code like the above to route U's
2782/// dependence through the store when possible, like this:
2783///
2784/// N
2785/// ||
2786/// ||
2787/// store
2788/// |
2789/// U
2790/// |
2791/// ...
2792///
2793/// This results in the store being scheduled immediately
2794/// after N, which shortens the U->N live range, reducing
2795/// register pressure.
2796///
2797void RegReductionPQBase::PrescheduleNodesWithMultipleUses() {
2798 // Visit all the nodes in topological order, working top-down.
2799 for (SUnit &SU : *SUnits) {
2800 // For now, only look at nodes with no data successors, such as stores.
2801 // These are especially important, due to the heuristics in
2802 // getNodePriority for nodes with no data successors.
2803 if (SU.NumSuccs != 0)
2804 continue;
2805 // For now, only look at nodes with exactly one data predecessor.
2806 if (SU.NumPreds != 1)
2807 continue;
2808 // Avoid prescheduling copies to virtual registers, which don't behave
2809 // like other nodes from the perspective of scheduling heuristics.
2810 if (SDNode *N = SU.getNode())
2811 if (N->getOpcode() == ISD::CopyToReg &&
2812 TargetRegisterInfo::isVirtualRegister
2813 (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
2814 continue;
2815
2816 // Locate the single data predecessor.
2817 SUnit *PredSU = nullptr;
2818 for (const SDep &Pred : SU.Preds)
2819 if (!Pred.isCtrl()) {
2820 PredSU = Pred.getSUnit();
2821 break;
2822 }
2823 assert(PredSU)((PredSU) ? static_cast<void> (0) : __assert_fail ("PredSU"
, "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 2823, __PRETTY_FUNCTION__))
;
2824
2825 // Don't rewrite edges that carry physregs, because that requires additional
2826 // support infrastructure.
2827 if (PredSU->hasPhysRegDefs)
2828 continue;
2829 // Short-circuit the case where SU is PredSU's only data successor.
2830 if (PredSU->NumSuccs == 1)
2831 continue;
2832 // Avoid prescheduling to copies from virtual registers, which don't behave
2833 // like other nodes from the perspective of scheduling heuristics.
2834 if (SDNode *N = SU.getNode())
2835 if (N->getOpcode() == ISD::CopyFromReg &&
2836 TargetRegisterInfo::isVirtualRegister
2837 (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
2838 continue;
2839
2840 // Perform checks on the successors of PredSU.
2841 for (const SDep &PredSucc : PredSU->Succs) {
2842 SUnit *PredSuccSU = PredSucc.getSUnit();
2843 if (PredSuccSU == &SU) continue;
2844 // If PredSU has another successor with no data successors, for
2845 // now don't attempt to choose either over the other.
2846 if (PredSuccSU->NumSuccs == 0)
2847 goto outer_loop_continue;
2848 // Don't break physical register dependencies.
2849 if (SU.hasPhysRegClobbers && PredSuccSU->hasPhysRegDefs)
2850 if (canClobberPhysRegDefs(PredSuccSU, &SU, TII, TRI))
2851 goto outer_loop_continue;
2852 // Don't introduce graph cycles.
2853 if (scheduleDAG->IsReachable(&SU, PredSuccSU))
2854 goto outer_loop_continue;
2855 }
2856
2857 // Ok, the transformation is safe and the heuristics suggest it is
2858 // profitable. Update the graph.
2859 DEBUG(dbgs() << " Prescheduling SU #" << SU.NodeNumdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Prescheduling SU #" <<
SU.NodeNum << " next to PredSU #" << PredSU->
NodeNum << " to guide scheduling in the presence of multiple uses\n"
; } } while (false)
2860 << " next to PredSU #" << PredSU->NodeNumdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Prescheduling SU #" <<
SU.NodeNum << " next to PredSU #" << PredSU->
NodeNum << " to guide scheduling in the presence of multiple uses\n"
; } } while (false)
2861 << " to guide scheduling in the presence of multiple uses\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Prescheduling SU #" <<
SU.NodeNum << " next to PredSU #" << PredSU->
NodeNum << " to guide scheduling in the presence of multiple uses\n"
; } } while (false)
;
2862 for (unsigned i = 0; i != PredSU->Succs.size(); ++i) {
2863 SDep Edge = PredSU->Succs[i];
2864 assert(!Edge.isAssignedRegDep())((!Edge.isAssignedRegDep()) ? static_cast<void> (0) : __assert_fail
("!Edge.isAssignedRegDep()", "/tmp/buildd/llvm-toolchain-snapshot-5.0~svn303373/lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp"
, 2864, __PRETTY_FUNCTION__))
;
2865 SUnit *SuccSU = Edge.getSUnit();
2866 if (SuccSU != &SU) {
2867 Edge.setSUnit(PredSU);
2868 scheduleDAG->RemovePred(SuccSU, Edge);
2869 scheduleDAG->AddPred(&SU, Edge);
2870 Edge.setSUnit(&SU);
2871 scheduleDAG->AddPred(SuccSU, Edge);
2872 --i;
2873 }
2874 }
2875 outer_loop_continue:;
2876 }
2877}
2878
2879/// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
2880/// it as a def&use operand. Add a pseudo control edge from it to the other
2881/// node (if it won't create a cycle) so the two-address one will be scheduled
2882/// first (lower in the schedule). If both nodes are two-address, favor the
2883/// one that has a CopyToReg use (more likely to be a loop induction update).
2884/// If both are two-address, but one is commutable while the other is not
2885/// commutable, favor the one that's not commutable.
2886void RegReductionPQBase::AddPseudoTwoAddrDeps() {
2887 for (SUnit &SU : *SUnits) {
2888 if (!SU.isTwoAddress)
2889 continue;
2890
2891 SDNode *Node = SU.getNode();
2892 if (!Node || !Node->isMachineOpcode() || SU.getNode()->getGluedNode())
2893 continue;
2894
2895 bool isLiveOut = hasOnlyLiveOutUses(&SU);
2896 unsigned Opc = Node->getMachineOpcode();
2897 const MCInstrDesc &MCID = TII->get(Opc);
2898 unsigned NumRes = MCID.getNumDefs();
2899 unsigned NumOps = MCID.getNumOperands() - NumRes;
2900 for (unsigned j = 0; j != NumOps; ++j) {
2901 if (MCID.getOperandConstraint(j+NumRes, MCOI::TIED_TO) == -1)
2902 continue;
2903 SDNode *DU = SU.getNode()->getOperand(j).getNode();
2904 if (DU->getNodeId() == -1)
2905 continue;
2906 const SUnit *DUSU = &(*SUnits)[DU->getNodeId()];
2907 if (!DUSU)
2908 continue;
2909 for (const SDep &Succ : DUSU->Succs) {
2910 if (Succ.isCtrl())
2911 continue;
2912 SUnit *SuccSU = Succ.getSUnit();
2913 if (SuccSU == &SU)
2914 continue;
2915 // Be conservative. Ignore if nodes aren't at roughly the same
2916 // depth and height.
2917 if (SuccSU->getHeight() < SU.getHeight() &&
2918 (SU.getHeight() - SuccSU->getHeight()) > 1)
2919 continue;
2920 // Skip past COPY_TO_REGCLASS nodes, so that the pseudo edge
2921 // constrains whatever is using the copy, instead of the copy
2922 // itself. In the case that the copy is coalesced, this
2923 // preserves the intent of the pseudo two-address heurietics.
2924 while (SuccSU->Succs.size() == 1 &&
2925 SuccSU->getNode()->isMachineOpcode() &&
2926 SuccSU->getNode()->getMachineOpcode() ==
2927 TargetOpcode::COPY_TO_REGCLASS)
2928 SuccSU = SuccSU->Succs.front().getSUnit();
2929 // Don't constrain non-instruction nodes.
2930 if (!SuccSU->getNode() || !SuccSU->getNode()->isMachineOpcode())
2931 continue;
2932 // Don't constrain nodes with physical register defs if the
2933 // predecessor can clobber them.
2934 if (SuccSU->hasPhysRegDefs && SU.hasPhysRegClobbers) {
2935 if (canClobberPhysRegDefs(SuccSU, &SU, TII, TRI))
2936 continue;
2937 }
2938 // Don't constrain EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG;
2939 // these may be coalesced away. We want them close to their uses.
2940 unsigned SuccOpc = SuccSU->getNode()->getMachineOpcode();
2941 if (SuccOpc == TargetOpcode::EXTRACT_SUBREG ||
2942 SuccOpc == TargetOpcode::INSERT_SUBREG ||
2943 SuccOpc == TargetOpcode::SUBREG_TO_REG)
2944 continue;
2945 if (!canClobberReachingPhysRegUse(SuccSU, &SU, scheduleDAG, TII, TRI) &&
2946 (!canClobber(SuccSU, DUSU) ||
2947 (isLiveOut && !hasOnlyLiveOutUses(SuccSU)) ||
2948 (!SU.isCommutable && SuccSU->isCommutable)) &&
2949 !scheduleDAG->IsReachable(SuccSU, &SU)) {
2950 DEBUG(dbgs() << " Adding a pseudo-two-addr edge from SU #"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Adding a pseudo-two-addr edge from SU #"
<< SU.NodeNum << " to SU #" << SuccSU->
NodeNum << "\n"; } } while (false)
2951 << SU.NodeNum << " to SU #" << SuccSU->NodeNum << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("pre-RA-sched")) { dbgs() << " Adding a pseudo-two-addr edge from SU #"
<< SU.NodeNum << " to SU #" << SuccSU->
NodeNum << "\n"; } } while (false)
;
2952 scheduleDAG->AddPred(&SU, SDep(SuccSU, SDep::Artificial));
2953 }
2954 }
2955 }
2956 }
2957}
2958
2959//===----------------------------------------------------------------------===//
2960// Public Constructor Functions
2961//===----------------------------------------------------------------------===//
2962
2963llvm::ScheduleDAGSDNodes *
2964llvm::createBURRListDAGScheduler(SelectionDAGISel *IS,
2965 CodeGenOpt::Level OptLevel) {
2966 const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
2967 const TargetInstrInfo *TII = STI.getInstrInfo();
2968 const TargetRegisterInfo *TRI = STI.getRegisterInfo();
2969
2970 BURegReductionPriorityQueue *PQ =
2971 new BURegReductionPriorityQueue(*IS->MF, false, false, TII, TRI, nullptr);
2972 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, PQ, OptLevel);
2973 PQ->setScheduleDAG(SD);
2974 return SD;
2975}
2976
2977llvm::ScheduleDAGSDNodes *
2978llvm::createSourceListDAGScheduler(SelectionDAGISel *IS,
2979 CodeGenOpt::Level OptLevel) {
2980 const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
2981 const TargetInstrInfo *TII = STI.getInstrInfo();
2982 const TargetRegisterInfo *TRI = STI.getRegisterInfo();
2983
2984 SrcRegReductionPriorityQueue *PQ =
2985 new SrcRegReductionPriorityQueue(*IS->MF, false, true, TII, TRI, nullptr);
2986 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, PQ, OptLevel);
2987 PQ->setScheduleDAG(SD);
2988 return SD;
2989}
2990
2991llvm::ScheduleDAGSDNodes *
2992llvm::createHybridListDAGScheduler(SelectionDAGISel *IS,
2993 CodeGenOpt::Level OptLevel) {
2994 const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
2995 const TargetInstrInfo *TII = STI.getInstrInfo();
2996 const TargetRegisterInfo *TRI = STI.getRegisterInfo();
2997 const TargetLowering *TLI = IS->TLI;
2998
2999 HybridBURRPriorityQueue *PQ =
3000 new HybridBURRPriorityQueue(*IS->MF, true, false, TII, TRI, TLI);
3001
3002 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, PQ, OptLevel);
3003 PQ->setScheduleDAG(SD);
3004 return SD;
3005}
3006
3007llvm::ScheduleDAGSDNodes *
3008llvm::createILPListDAGScheduler(SelectionDAGISel *IS,
3009 CodeGenOpt::Level OptLevel) {
3010 const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
3011 const TargetInstrInfo *TII = STI.getInstrInfo();
3012 const TargetRegisterInfo *TRI = STI.getRegisterInfo();
3013 const TargetLowering *TLI = IS->TLI;
3014
3015 ILPBURRPriorityQueue *PQ =
3016 new ILPBURRPriorityQueue(*IS->MF, true, false, TII, TRI, TLI);
3017 ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, PQ, OptLevel);
3018 PQ->setScheduleDAG(SD);
3019 return SD;
3020}