Line data Source code
1 : //===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===//
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 the ScheduleDAG class, which is a base class used by
11 : // scheduling implementation classes.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #include "ScheduleDAGSDNodes.h"
16 : #include "InstrEmitter.h"
17 : #include "SDNodeDbgValue.h"
18 : #include "llvm/ADT/DenseMap.h"
19 : #include "llvm/ADT/SmallPtrSet.h"
20 : #include "llvm/ADT/SmallSet.h"
21 : #include "llvm/ADT/SmallVector.h"
22 : #include "llvm/ADT/Statistic.h"
23 : #include "llvm/CodeGen/MachineInstrBuilder.h"
24 : #include "llvm/CodeGen/MachineRegisterInfo.h"
25 : #include "llvm/CodeGen/SelectionDAG.h"
26 : #include "llvm/CodeGen/TargetInstrInfo.h"
27 : #include "llvm/CodeGen/TargetLowering.h"
28 : #include "llvm/CodeGen/TargetRegisterInfo.h"
29 : #include "llvm/CodeGen/TargetSubtargetInfo.h"
30 : #include "llvm/Config/llvm-config.h"
31 : #include "llvm/MC/MCInstrItineraries.h"
32 : #include "llvm/Support/CommandLine.h"
33 : #include "llvm/Support/Debug.h"
34 : #include "llvm/Support/raw_ostream.h"
35 : using namespace llvm;
36 :
37 : #define DEBUG_TYPE "pre-RA-sched"
38 :
39 : STATISTIC(LoadsClustered, "Number of loads clustered together");
40 :
41 : // This allows the latency-based scheduler to notice high latency instructions
42 : // without a target itinerary. The choice of number here has more to do with
43 : // balancing scheduler heuristics than with the actual machine latency.
44 : static cl::opt<int> HighLatencyCycles(
45 : "sched-high-latency-cycles", cl::Hidden, cl::init(10),
46 : cl::desc("Roughly estimate the number of cycles that 'long latency'"
47 : "instructions take for targets with no itinerary"));
48 :
49 1269050 : ScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf)
50 : : ScheduleDAG(mf), BB(nullptr), DAG(nullptr),
51 1269050 : InstrItins(mf.getSubtarget().getInstrItineraryData()) {}
52 :
53 : /// Run - perform scheduling.
54 : ///
55 1269050 : void ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb) {
56 1269050 : BB = bb;
57 1269050 : DAG = dag;
58 :
59 : // Clear the scheduler's SUnit DAG.
60 1269050 : ScheduleDAG::clearDAG();
61 : Sequence.clear();
62 :
63 : // Invoke the target's selection of scheduler.
64 1269049 : Schedule();
65 1269049 : }
66 :
67 : /// NewSUnit - Creates a new SUnit and return a ptr to it.
68 : ///
69 16310483 : SUnit *ScheduleDAGSDNodes::newSUnit(SDNode *N) {
70 : #ifndef NDEBUG
71 : const SUnit *Addr = nullptr;
72 : if (!SUnits.empty())
73 : Addr = &SUnits[0];
74 : #endif
75 32620966 : SUnits.emplace_back(N, (unsigned)SUnits.size());
76 : assert((Addr == nullptr || Addr == &SUnits[0]) &&
77 : "SUnits std::vector reallocated on the fly!");
78 16310482 : SUnits.back().OrigNode = &SUnits.back();
79 : SUnit *SU = &SUnits.back();
80 16310482 : const TargetLowering &TLI = DAG->getTargetLoweringInfo();
81 16310482 : if (!N ||
82 16310352 : (N->isMachineOpcode() &&
83 : N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF))
84 27296 : SU->SchedulingPref = Sched::None;
85 : else
86 16283186 : SU->SchedulingPref = TLI.getSchedulingPreference(N);
87 16310483 : return SU;
88 : }
89 :
90 275 : SUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) {
91 275 : SUnit *SU = newSUnit(Old->getNode());
92 275 : SU->OrigNode = Old->OrigNode;
93 275 : SU->Latency = Old->Latency;
94 275 : SU->isVRegCycle = Old->isVRegCycle;
95 275 : SU->isCall = Old->isCall;
96 275 : SU->isCallOp = Old->isCallOp;
97 275 : SU->isTwoAddress = Old->isTwoAddress;
98 275 : SU->isCommutable = Old->isCommutable;
99 275 : SU->hasPhysRegDefs = Old->hasPhysRegDefs;
100 275 : SU->hasPhysRegClobbers = Old->hasPhysRegClobbers;
101 275 : SU->isScheduleHigh = Old->isScheduleHigh;
102 275 : SU->isScheduleLow = Old->isScheduleLow;
103 275 : SU->SchedulingPref = Old->SchedulingPref;
104 275 : Old->isCloned = true;
105 275 : return SU;
106 : }
107 :
108 : /// CheckForPhysRegDependency - Check if the dependency between def and use of
109 : /// a specified operand is a physical register dependency. If so, returns the
110 : /// register and the cost of copying the register.
111 20096981 : static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op,
112 : const TargetRegisterInfo *TRI,
113 : const TargetInstrInfo *TII,
114 : unsigned &PhysReg, int &Cost) {
115 20096981 : if (Op != 2 || User->getOpcode() != ISD::CopyToReg)
116 : return;
117 :
118 7228106 : unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
119 3614053 : if (TargetRegisterInfo::isVirtualRegister(Reg))
120 : return;
121 :
122 2424896 : unsigned ResNo = User->getOperand(2).getResNo();
123 2424896 : if (Def->getOpcode() == ISD::CopyFromReg &&
124 553490 : cast<RegisterSDNode>(Def->getOperand(1))->getReg() == Reg) {
125 10522 : PhysReg = Reg;
126 2414374 : } else if (Def->isMachineOpcode()) {
127 2148151 : const MCInstrDesc &II = TII->get(Def->getMachineOpcode());
128 4296302 : if (ResNo >= II.getNumDefs() &&
129 221295 : II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg)
130 221240 : PhysReg = Reg;
131 : }
132 :
133 2424896 : if (PhysReg != 0) {
134 : const TargetRegisterClass *RC =
135 231762 : TRI->getMinimalPhysRegClass(Reg, Def->getSimpleValueType(ResNo));
136 463524 : Cost = RC->getCopyCost();
137 : }
138 : }
139 :
140 : // Helper for AddGlue to clone node operands.
141 176291 : static void CloneNodeWithValues(SDNode *N, SelectionDAG *DAG, ArrayRef<EVT> VTs,
142 : SDValue ExtraOper = SDValue()) {
143 176291 : SmallVector<SDValue, 8> Ops(N->op_begin(), N->op_end());
144 176291 : if (ExtraOper.getNode())
145 78317 : Ops.push_back(ExtraOper);
146 :
147 176291 : SDVTList VTList = DAG->getVTList(VTs);
148 : MachineSDNode *MN = dyn_cast<MachineSDNode>(N);
149 :
150 : // Store memory references.
151 : SmallVector<MachineMemOperand *, 2> MMOs;
152 176291 : if (MN)
153 : MMOs.assign(MN->memoperands_begin(), MN->memoperands_end());
154 :
155 352582 : DAG->MorphNodeTo(N, N->getOpcode(), VTList, Ops);
156 :
157 : // Reset the memory references
158 176291 : if (MN)
159 176291 : DAG->setNodeMemRefs(MN, MMOs);
160 176291 : }
161 :
162 221999 : static bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG) {
163 221999 : SDNode *GlueDestNode = Glue.getNode();
164 :
165 : // Don't add glue from a node to itself.
166 221999 : if (GlueDestNode == N) return false;
167 :
168 : // Don't add a glue operand to something that already uses glue.
169 221992 : if (GlueDestNode &&
170 235038 : N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {
171 6 : return false;
172 : }
173 : // Don't add glue to something that already has a glue value.
174 443972 : if (N->getValueType(N->getNumValues() - 1) == MVT::Glue) return false;
175 :
176 : SmallVector<EVT, 4> VTs(N->value_begin(), N->value_end());
177 176264 : if (AddGlue)
178 78344 : VTs.push_back(MVT::Glue);
179 :
180 176264 : CloneNodeWithValues(N, DAG, VTs, Glue);
181 :
182 : return true;
183 : }
184 :
185 : // Cleanup after unsuccessful AddGlue. Use the standard method of morphing the
186 : // node even though simply shrinking the value list is sufficient.
187 27 : static void RemoveUnusedGlue(SDNode *N, SelectionDAG *DAG) {
188 : assert((N->getValueType(N->getNumValues() - 1) == MVT::Glue &&
189 : !N->hasAnyUseOfValue(N->getNumValues() - 1)) &&
190 : "expected an unused glue value");
191 :
192 54 : CloneNodeWithValues(N, DAG,
193 54 : makeArrayRef(N->value_begin(), N->getNumValues() - 1));
194 27 : }
195 :
196 : /// ClusterNeighboringLoads - Force nearby loads together by "gluing" them.
197 : /// This function finds loads of the same base and different offsets. If the
198 : /// offsets are not far apart (target specific), it add MVT::Glue inputs and
199 : /// outputs to ensure they are scheduled together and in order. This
200 : /// optimization may benefit some targets by improving cache locality.
201 2552990 : void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) {
202 : SDNode *Chain = nullptr;
203 2552990 : unsigned NumOps = Node->getNumOperands();
204 5105980 : if (Node->getOperand(NumOps-1).getValueType() == MVT::Other)
205 : Chain = Node->getOperand(NumOps-1).getNode();
206 2552990 : if (!Chain)
207 2455043 : return;
208 :
209 : // Look for other loads of the same chain. Find loads that are loading from
210 : // the same base pointer and different offsets.
211 : SmallPtrSet<SDNode*, 16> Visited;
212 : SmallVector<int64_t, 4> Offsets;
213 : DenseMap<long long, SDNode*> O2SMap; // Map from offset to SDNode.
214 : bool Cluster = false;
215 : SDNode *Base = Node;
216 : // This algorithm requires a reasonably low use count before finding a match
217 : // to avoid uselessly blowing up compile time in large blocks.
218 : unsigned UseCount = 0;
219 9738473 : for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end();
220 9738473 : I != E && UseCount < 100; ++I, ++UseCount) {
221 : SDNode *User = *I;
222 7367209 : if (User == Node || !Visited.insert(User).second)
223 6958524 : continue;
224 : int64_t Offset1, Offset2;
225 4949799 : if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) ||
226 408911 : Offset1 == Offset2)
227 : // FIXME: Should be ok if they addresses are identical. But earlier
228 : // optimizations really should have eliminated one of the loads.
229 : continue;
230 408685 : if (O2SMap.insert(std::make_pair(Offset1, Base)).second)
231 115693 : Offsets.push_back(Offset1);
232 408685 : O2SMap.insert(std::make_pair(Offset2, User));
233 408685 : Offsets.push_back(Offset2);
234 408685 : if (Offset2 < Offset1)
235 : Base = User;
236 : Cluster = true;
237 : // Reset UseCount to allow more matches.
238 : UseCount = 0;
239 : }
240 :
241 2371264 : if (!Cluster)
242 : return;
243 :
244 : // Sort them in increasing order.
245 : llvm::sort(Offsets);
246 :
247 : // Check if the loads are close enough.
248 : SmallVector<SDNode*, 4> Loads;
249 : unsigned NumLoads = 0;
250 115693 : int64_t BaseOff = Offsets[0];
251 115693 : SDNode *BaseLoad = O2SMap[BaseOff];
252 115693 : Loads.push_back(BaseLoad);
253 239745 : for (unsigned i = 1, e = Offsets.size(); i != e; ++i) {
254 147807 : int64_t Offset = Offsets[i];
255 147807 : SDNode *Load = O2SMap[Offset];
256 147807 : if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads))
257 : break; // Stop right here. Ignore loads that are further away.
258 124052 : Loads.push_back(Load);
259 124052 : ++NumLoads;
260 : }
261 :
262 115693 : if (NumLoads == 0)
263 : return;
264 :
265 : // Cluster loads by adding MVT::Glue outputs and inputs. This also
266 : // ensure they are scheduled in order of increasing addresses.
267 97947 : SDNode *Lead = Loads[0];
268 : SDValue InGlue = SDValue(nullptr, 0);
269 97947 : if (AddGlue(Lead, InGlue, true, DAG))
270 143232 : InGlue = SDValue(Lead, Lead->getNumValues() - 1);
271 221999 : for (unsigned I = 1, E = Loads.size(); I != E; ++I) {
272 124052 : bool OutGlue = I < E - 1;
273 124052 : SDNode *Load = Loads[I];
274 :
275 : // If AddGlue fails, we could leave an unsused glue value. This should not
276 : // cause any
277 124052 : if (AddGlue(Load, InGlue, OutGlue, DAG)) {
278 104648 : if (OutGlue)
279 13456 : InGlue = SDValue(Load, Load->getNumValues() - 1);
280 :
281 : ++LoadsClustered;
282 : }
283 19404 : else if (!OutGlue && InGlue.getNode())
284 27 : RemoveUnusedGlue(InGlue.getNode(), DAG);
285 : }
286 : }
287 :
288 : /// ClusterNodes - Cluster certain nodes which should be scheduled together.
289 : ///
290 1269036 : void ScheduleDAGSDNodes::ClusterNodes() {
291 39244619 : for (SDNode &NI : DAG->allnodes()) {
292 : SDNode *Node = &NI;
293 37975583 : if (!Node || !Node->isMachineOpcode())
294 : continue;
295 :
296 : unsigned Opc = Node->getMachineOpcode();
297 12152512 : const MCInstrDesc &MCID = TII->get(Opc);
298 24305024 : if (MCID.mayLoad())
299 : // Cluster loads from "near" addresses into combined SUnits.
300 2552990 : ClusterNeighboringLoads(Node);
301 : }
302 1269036 : }
303 :
304 1269036 : void ScheduleDAGSDNodes::BuildSchedUnits() {
305 : // During scheduling, the NodeId field of SDNode is used to map SDNodes
306 : // to their associated SUnits by holding SUnits table indices. A value
307 : // of -1 means the SDNode does not yet have an associated SUnit.
308 : unsigned NumNodes = 0;
309 39244616 : for (SDNode &NI : DAG->allnodes()) {
310 : NI.setNodeId(-1);
311 37975580 : ++NumNodes;
312 : }
313 :
314 : // Reserve entries in the vector for each of the SUnits we are creating. This
315 : // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
316 : // invalidated.
317 : // FIXME: Multiply by 2 because we may clone nodes during scheduling.
318 : // This is a temporary workaround.
319 1269036 : SUnits.reserve(NumNodes * 2);
320 :
321 : // Add all nodes in depth first order.
322 : SmallVector<SDNode*, 64> Worklist;
323 : SmallPtrSet<SDNode*, 32> Visited;
324 1269036 : Worklist.push_back(DAG->getRoot().getNode());
325 1269036 : Visited.insert(DAG->getRoot().getNode());
326 :
327 : SmallVector<SUnit*, 8> CallSUnits;
328 39193291 : while (!Worklist.empty()) {
329 : SDNode *NI = Worklist.pop_back_val();
330 :
331 : // Add all operands to the worklist unless they've already been added.
332 116971593 : for (const SDValue &Op : NI->op_values())
333 79047338 : if (Visited.insert(Op.getNode()).second)
334 36655217 : Worklist.push_back(Op.getNode());
335 :
336 37924255 : if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate.
337 21614447 : continue;
338 :
339 : // If this node has already been processed, stop now.
340 20309250 : if (NI->getNodeId() != -1) continue;
341 :
342 16309808 : SUnit *NodeSUnit = newSUnit(NI);
343 :
344 : // See if anything is glued to this node, if so, add them to glued
345 : // nodes. Nodes can have at most one glue input and one glue output. Glue
346 : // is required to be the last operand and result of a node.
347 :
348 : // Scan up to find glued preds.
349 : SDNode *N = NI;
350 40558888 : while (N->getNumOperands() &&
351 40020930 : N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {
352 : N = N->getOperand(N->getNumOperands()-1).getNode();
353 : assert(N->getNodeId() == -1 && "Node already inserted!");
354 3969636 : N->setNodeId(NodeSUnit->NodeNum);
355 3969636 : if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())
356 998936 : NodeSUnit->isCall = true;
357 : }
358 :
359 : // Scan down to find any glued succs.
360 : N = NI;
361 32649422 : while (N->getValueType(N->getNumValues()-1) == MVT::Glue) {
362 : SDValue GlueVal(N, N->getNumValues()-1);
363 :
364 : // There are either zero or one users of the Glue result.
365 : bool HasGlueUse = false;
366 2057697 : for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
367 4676727 : UI != E; ++UI)
368 2648836 : if (GlueVal.isOperandOf(*UI)) {
369 : HasGlueUse = true;
370 : assert(N->getNodeId() == -1 && "Node already inserted!");
371 29806 : N->setNodeId(NodeSUnit->NodeNum);
372 : N = *UI;
373 29806 : if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())
374 0 : NodeSUnit->isCall = true;
375 : break;
376 : }
377 2057697 : if (!HasGlueUse) break;
378 : }
379 :
380 16309808 : if (NodeSUnit->isCall)
381 998936 : CallSUnits.push_back(NodeSUnit);
382 :
383 : // Schedule zero-latency TokenFactor below any nodes that may increase the
384 : // schedule height. Otherwise, ancestors of the TokenFactor may appear to
385 : // have false stalls.
386 16309808 : if (NI->getOpcode() == ISD::TokenFactor)
387 1411320 : NodeSUnit->isScheduleLow = true;
388 :
389 : // If there are glue operands involved, N is now the bottom-most node
390 : // of the sequence of nodes that are glued together.
391 : // Update the SUnit.
392 16309808 : NodeSUnit->setNode(N);
393 : assert(N->getNodeId() == -1 && "Node already inserted!");
394 16309808 : N->setNodeId(NodeSUnit->NodeNum);
395 :
396 : // Compute NumRegDefsLeft. This must be done before AddSchedEdges.
397 16309808 : InitNumRegDefsLeft(NodeSUnit);
398 :
399 : // Assign the Latency field of NodeSUnit using target-provided information.
400 16309808 : computeLatency(NodeSUnit);
401 : }
402 :
403 : // Find all call operands.
404 2267972 : while (!CallSUnits.empty()) {
405 : SUnit *SU = CallSUnits.pop_back_val();
406 4473494 : for (const SDNode *SUNode = SU->getNode(); SUNode;
407 : SUNode = SUNode->getGluedNode()) {
408 4473494 : if (SUNode->getOpcode() != ISD::CopyToReg)
409 : continue;
410 2064825 : SDNode *SrcN = SUNode->getOperand(2).getNode();
411 2064825 : if (isPassiveNode(SrcN)) continue; // Not scheduled.
412 2017735 : SUnit *SrcSU = &SUnits[SrcN->getNodeId()];
413 2017735 : SrcSU->isCallOp = true;
414 : }
415 : }
416 1269036 : }
417 :
418 1269036 : void ScheduleDAGSDNodes::AddSchedEdges() {
419 1269036 : const TargetSubtargetInfo &ST = MF.getSubtarget();
420 :
421 : // Check to see if the scheduler cares about latencies.
422 1269036 : bool UnitLatencies = forceUnitLatencies();
423 :
424 : // Pass 2: add the preds, succs, etc.
425 18847880 : for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
426 16309808 : SUnit *SU = &SUnits[su];
427 16309808 : SDNode *MainNode = SU->getNode();
428 :
429 16309808 : if (MainNode->isMachineOpcode()) {
430 : unsigned Opc = MainNode->getMachineOpcode();
431 10642256 : const MCInstrDesc &MCID = TII->get(Opc);
432 66027336 : for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
433 : if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
434 514774 : SU->isTwoAddress = true;
435 514774 : break;
436 : }
437 : }
438 21284512 : if (MCID.isCommutable())
439 207919 : SU->isCommutable = true;
440 : }
441 :
442 : // Find all predecessors and successors of the group.
443 20309249 : for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) {
444 20309249 : if (N->isMachineOpcode() &&
445 36443178 : TII->get(N->getMachineOpcode()).getImplicitDefs()) {
446 2910989 : SU->hasPhysRegClobbers = true;
447 2910989 : unsigned NumUsed = InstrEmitter::CountResults(N);
448 5545188 : while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1))
449 : --NumUsed; // Skip over unused values at the end.
450 11643952 : if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs())
451 219158 : SU->hasPhysRegDefs = true;
452 : }
453 :
454 99356584 : for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
455 79047335 : SDNode *OpN = N->getOperand(i).getNode();
456 86900156 : if (isPassiveNode(OpN)) continue; // Not scheduled.
457 27949802 : SUnit *OpSU = &SUnits[OpN->getNodeId()];
458 : assert(OpSU && "Node has no SUnit!");
459 27949802 : if (OpSU == SU) continue; // In the same group.
460 :
461 20096981 : EVT OpVT = N->getOperand(i).getValueType();
462 : assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!");
463 : bool isChain = OpVT == MVT::Other;
464 :
465 20096981 : unsigned PhysReg = 0;
466 20096981 : int Cost = 1;
467 : // Determine if this is a physical register dependency.
468 20096981 : CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost);
469 : assert((PhysReg == 0 || !isChain) &&
470 : "Chain dependence via physreg data?");
471 : // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler
472 : // emits a copy from the physical register to a virtual register unless
473 : // it requires a cross class copy (cost < 0). That means we are only
474 : // treating "expensive to copy" register dependency as physical register
475 : // dependency. This may change in the future though.
476 20096981 : if (Cost >= 0 && !StressSched)
477 19870467 : PhysReg = 0;
478 :
479 : // If this is a ctrl dep, latency is 1.
480 20096981 : unsigned OpLatency = isChain ? 1 : OpSU->Latency;
481 : // Special-case TokenFactor chains as zero-latency.
482 20096981 : if(isChain && OpN->getOpcode() == ISD::TokenFactor)
483 : OpLatency = 0;
484 :
485 : SDep Dep = isChain ? SDep(OpSU, SDep::Barrier)
486 20096981 : : SDep(OpSU, SDep::Data, PhysReg);
487 : Dep.setLatency(OpLatency);
488 20096981 : if (!isChain && !UnitLatencies) {
489 172536 : computeOperandLatency(OpN, N, i, Dep);
490 172536 : ST.adjustSchedDependency(OpSU, SU, Dep);
491 : }
492 :
493 20096981 : if (!SU->addPred(Dep) && !Dep.isCtrl() && OpSU->NumRegDefsLeft > 1) {
494 : // Multiple register uses are combined in the same SUnit. For example,
495 : // we could have a set of glued nodes with all their defs consumed by
496 : // another set of glued nodes. Register pressure tracking sees this as
497 : // a single use, so to keep pressure balanced we reduce the defs.
498 : //
499 : // We can't tell (without more book-keeping) if this results from
500 : // glued nodes or duplicate operands. As long as we don't reduce
501 : // NumRegDefsLeft to zero, we handle the common cases well.
502 42315 : --OpSU->NumRegDefsLeft;
503 : }
504 : }
505 : }
506 : }
507 1269036 : }
508 :
509 : /// BuildSchedGraph - Build the SUnit graph from the selection dag that we
510 : /// are input. This SUnit graph is similar to the SelectionDAG, but
511 : /// excludes nodes that aren't interesting to scheduling, and represents
512 : /// glued together nodes with a single SUnit.
513 1269036 : void ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) {
514 : // Cluster certain nodes which should be scheduled together.
515 1269036 : ClusterNodes();
516 : // Populate the SUnits array.
517 1269036 : BuildSchedUnits();
518 : // Compute all the scheduling dependencies between nodes.
519 1269036 : AddSchedEdges();
520 1269036 : }
521 :
522 : // Initialize NumNodeDefs for the current Node's opcode.
523 21224061 : void ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() {
524 : // Check for phys reg copy.
525 21224061 : if (!Node)
526 8512395 : return;
527 :
528 21224061 : if (!Node->isMachineOpcode()) {
529 8483937 : if (Node->getOpcode() == ISD::CopyFromReg)
530 2259109 : NodeNumDefs = 1;
531 : else
532 6224828 : NodeNumDefs = 0;
533 8483937 : return;
534 : }
535 : unsigned POpc = Node->getMachineOpcode();
536 12740124 : if (POpc == TargetOpcode::IMPLICIT_DEF) {
537 : // No register need be allocated for this.
538 28359 : NodeNumDefs = 0;
539 28359 : return;
540 : }
541 12711765 : if (POpc == TargetOpcode::PATCHPOINT &&
542 146 : Node->getValueType(0) == MVT::Other) {
543 : // PATCHPOINT is defined to have one result, but it might really have none
544 : // if we're not using CallingConv::AnyReg. Don't mistake the chain for a
545 : // real definition.
546 99 : NodeNumDefs = 0;
547 99 : return;
548 : }
549 25423332 : unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs();
550 : // Some instructions define regs that are not represented in the selection DAG
551 : // (e.g. unused flags). See tMOVi8. Make sure we don't access past NumValues.
552 25423332 : NodeNumDefs = std::min(Node->getNumValues(), NRegDefs);
553 12711666 : DefIdx = 0;
554 : }
555 :
556 : // Construct a RegDefIter for this SUnit and find the first valid value.
557 17056983 : ScheduleDAGSDNodes::RegDefIter::RegDefIter(const SUnit *SU,
558 17056983 : const ScheduleDAGSDNodes *SD)
559 17056983 : : SchedDAG(SD), Node(SU->getNode()), DefIdx(0), NodeNumDefs(0) {
560 17056983 : InitNodeNumDefs();
561 17056983 : Advance();
562 17056982 : }
563 :
564 : // Advance to the next valid value defined by the SUnit.
565 24933352 : void ScheduleDAGSDNodes::RegDefIter::Advance() {
566 29100430 : for (;Node;) { // Visit all glued nodes.
567 29192358 : for (;DefIdx < NodeNumDefs; ++DefIdx) {
568 8128331 : if (!Node->hasAnyUseOfValue(DefIdx))
569 : continue;
570 8036403 : ValueType = Node->getSimpleValueType(DefIdx);
571 8036403 : ++DefIdx;
572 8036403 : return; // Found a normal regdef.
573 : }
574 21064027 : Node = Node->getGluedNode();
575 21064027 : if (!Node) {
576 : return; // No values left to visit.
577 : }
578 4167078 : InitNodeNumDefs();
579 : }
580 : }
581 :
582 16310077 : void ScheduleDAGSDNodes::InitNumRegDefsLeft(SUnit *SU) {
583 : assert(SU->NumRegDefsLeft == 0 && "expect a new node");
584 23640848 : for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) {
585 : assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected");
586 7330770 : ++SU->NumRegDefsLeft;
587 : }
588 16310078 : }
589 :
590 16310078 : void ScheduleDAGSDNodes::computeLatency(SUnit *SU) {
591 16310078 : SDNode *N = SU->getNode();
592 :
593 : // TokenFactor operands are considered zero latency, and some schedulers
594 : // (e.g. Top-Down list) may rely on the fact that operand latency is nonzero
595 : // whenever node latency is nonzero.
596 16310078 : if (N && N->getOpcode() == ISD::TokenFactor) {
597 1411320 : SU->Latency = 0;
598 1411320 : return;
599 : }
600 :
601 : // Check to see if the scheduler cares about latencies.
602 14898758 : if (forceUnitLatencies()) {
603 14695744 : SU->Latency = 1;
604 14695744 : return;
605 : }
606 :
607 203014 : if (!InstrItins || InstrItins->isEmpty()) {
608 221467 : if (N && N->isMachineOpcode() &&
609 195536 : TII->isHighLatencyDef(N->getMachineOpcode()))
610 0 : SU->Latency = HighLatencyCycles;
611 : else
612 123699 : SU->Latency = 1;
613 123699 : return;
614 : }
615 :
616 : // Compute the latency for the node. We use the sum of the latencies for
617 : // all nodes glued together into this SUnit.
618 79315 : SU->Latency = 0;
619 104997 : for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
620 104997 : if (N->isMachineOpcode())
621 67150 : SU->Latency += TII->getInstrLatency(InstrItins, N);
622 : }
623 :
624 172536 : void ScheduleDAGSDNodes::computeOperandLatency(SDNode *Def, SDNode *Use,
625 : unsigned OpIdx, SDep& dep) const{
626 : // Check to see if the scheduler cares about latencies.
627 172536 : if (forceUnitLatencies())
628 : return;
629 :
630 172536 : if (dep.getKind() != SDep::Data)
631 : return;
632 :
633 172536 : unsigned DefIdx = Use->getOperand(OpIdx).getResNo();
634 172536 : if (Use->isMachineOpcode())
635 : // Adjust the use operand index by num of defs.
636 531596 : OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs();
637 172536 : int Latency = TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx);
638 172536 : if (Latency > 1 && Use->getOpcode() == ISD::CopyToReg &&
639 6960 : !BB->succ_empty()) {
640 542 : unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
641 271 : if (TargetRegisterInfo::isVirtualRegister(Reg))
642 : // This copy is a liveout value. It is likely coalesced, so reduce the
643 : // latency so not to penalize the def.
644 : // FIXME: need target specific adjustment here?
645 88 : Latency = (Latency > 1) ? Latency - 1 : 1;
646 : }
647 172536 : if (Latency >= 0)
648 64707 : dep.setLatency(Latency);
649 : }
650 :
651 0 : void ScheduleDAGSDNodes::dumpNode(const SUnit &SU) const {
652 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
653 : dumpNodeName(SU);
654 : dbgs() << ": ";
655 :
656 : if (!SU.getNode()) {
657 : dbgs() << "PHYS REG COPY\n";
658 : return;
659 : }
660 :
661 : SU.getNode()->dump(DAG);
662 : dbgs() << "\n";
663 : SmallVector<SDNode *, 4> GluedNodes;
664 : for (SDNode *N = SU.getNode()->getGluedNode(); N; N = N->getGluedNode())
665 : GluedNodes.push_back(N);
666 : while (!GluedNodes.empty()) {
667 : dbgs() << " ";
668 : GluedNodes.back()->dump(DAG);
669 : dbgs() << "\n";
670 : GluedNodes.pop_back();
671 : }
672 : #endif
673 0 : }
674 :
675 0 : void ScheduleDAGSDNodes::dump() const {
676 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
677 : if (EntrySU.getNode() != nullptr)
678 : dumpNodeAll(EntrySU);
679 : for (const SUnit &SU : SUnits)
680 : dumpNodeAll(SU);
681 : if (ExitSU.getNode() != nullptr)
682 : dumpNodeAll(ExitSU);
683 : #endif
684 0 : }
685 :
686 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
687 : void ScheduleDAGSDNodes::dumpSchedule() const {
688 : for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
689 : if (SUnit *SU = Sequence[i])
690 : dumpNode(*SU);
691 : else
692 : dbgs() << "**** NOOP ****\n";
693 : }
694 : }
695 : #endif
696 :
697 : #ifndef NDEBUG
698 : /// VerifyScheduledSequence - Verify that all SUnits were scheduled and that
699 : /// their state is consistent with the nodes listed in Sequence.
700 : ///
701 : void ScheduleDAGSDNodes::VerifyScheduledSequence(bool isBottomUp) {
702 : unsigned ScheduledNodes = ScheduleDAG::VerifyScheduledDAG(isBottomUp);
703 : unsigned Noops = 0;
704 : for (unsigned i = 0, e = Sequence.size(); i != e; ++i)
705 : if (!Sequence[i])
706 : ++Noops;
707 : assert(Sequence.size() - Noops == ScheduledNodes &&
708 : "The number of nodes scheduled doesn't match the expected number!");
709 : }
710 : #endif // NDEBUG
711 :
712 : /// ProcessSDDbgValues - Process SDDbgValues associated with this node.
713 : static void
714 214378 : ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter,
715 : SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders,
716 : DenseMap<SDValue, unsigned> &VRBaseMap, unsigned Order) {
717 214378 : if (!N->getHasDebugValue())
718 : return;
719 :
720 : // Opportunistically insert immediate dbg_value uses, i.e. those with the same
721 : // source order number as N.
722 16010 : MachineBasicBlock *BB = Emitter.getBlock();
723 : MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();
724 65651 : for (auto DV : DAG->GetDbgValues(N)) {
725 33631 : if (DV->isInvalidated())
726 : continue;
727 33629 : unsigned DVOrder = DV->getOrder();
728 33629 : if (!Order || DVOrder == Order) {
729 32154 : MachineInstr *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap);
730 32154 : if (DbgMI) {
731 64308 : Orders.push_back({DVOrder, DbgMI});
732 : BB->insert(InsertPos, DbgMI);
733 : }
734 : DV->setIsInvalidated();
735 : }
736 : }
737 : }
738 :
739 : // ProcessSourceNode - Process nodes with source order numbers. These are added
740 : // to a vector which EmitSchedule uses to determine how to insert dbg_value
741 : // instructions in the right order.
742 : static void
743 230859 : ProcessSourceNode(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter,
744 : DenseMap<SDValue, unsigned> &VRBaseMap,
745 : SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders,
746 : SmallSet<unsigned, 8> &Seen) {
747 230859 : unsigned Order = N->getIROrder();
748 230859 : if (!Order || !Seen.insert(Order).second) {
749 : // Process any valid SDDbgValues even if node does not have any order
750 : // assigned.
751 134139 : ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0);
752 150620 : return;
753 : }
754 :
755 96720 : MachineBasicBlock *BB = Emitter.getBlock();
756 : auto IP = Emitter.getInsertPos();
757 96720 : if (IP == BB->begin() || BB->back().isPHI() ||
758 : // Fast-isel may have inserted some instructions, in which case the
759 : // BB->back().isPHI() test will not fire when we want it to.
760 80239 : std::prev(IP)->isPHI()) {
761 : // Did not insert any instruction.
762 32962 : Orders.push_back({Order, (MachineInstr *)nullptr});
763 16481 : return;
764 : }
765 :
766 80239 : Orders.push_back({Order, &*std::prev(IP)});
767 80239 : ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order);
768 : }
769 :
770 130 : void ScheduleDAGSDNodes::
771 : EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap,
772 : MachineBasicBlock::iterator InsertPos) {
773 0 : for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
774 130 : I != E; ++I) {
775 130 : if (I->isCtrl()) continue; // ignore chain preds
776 130 : if (I->getSUnit()->CopyDstRC) {
777 : // Copy to physical register.
778 65 : DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->getSUnit());
779 : assert(VRI != VRBaseMap.end() && "Node emitted out of order - late");
780 : // Find the destination physical register.
781 : unsigned Reg = 0;
782 12 : for (SUnit::const_succ_iterator II = SU->Succs.begin(),
783 77 : EE = SU->Succs.end(); II != EE; ++II) {
784 77 : if (II->isCtrl()) continue; // ignore chain preds
785 76 : if (II->getReg()) {
786 : Reg = II->getReg();
787 : break;
788 : }
789 : }
790 195 : BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), Reg)
791 65 : .addReg(VRI->second);
792 : } else {
793 : // Copy from physical register.
794 : assert(I->getReg() && "Unknown physical register!");
795 130 : unsigned VRBase = MRI.createVirtualRegister(SU->CopyDstRC);
796 65 : bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second;
797 : (void)isNew; // Silence compiler warning.
798 : assert(isNew && "Node emitted out of order - early");
799 195 : BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), VRBase)
800 65 : .addReg(I->getReg());
801 : }
802 : break;
803 : }
804 130 : }
805 :
806 : /// EmitSchedule - Emit the machine code in scheduled order. Return the new
807 : /// InsertPos and MachineBasicBlock that contains this insertion
808 : /// point. ScheduleDAGSDNodes holds a BB pointer for convenience, but this does
809 : /// not necessarily refer to returned BB. The emitter may split blocks.
810 1269036 : MachineBasicBlock *ScheduleDAGSDNodes::
811 : EmitSchedule(MachineBasicBlock::iterator &InsertPos) {
812 1269036 : InstrEmitter Emitter(BB, InsertPos);
813 : DenseMap<SDValue, unsigned> VRBaseMap;
814 : DenseMap<SUnit*, unsigned> CopyVRBaseMap;
815 : SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders;
816 1269036 : SmallSet<unsigned, 8> Seen;
817 1269035 : bool HasDbg = DAG->hasDebugValues();
818 :
819 : // If this is the first BB, emit byval parameter dbg_value's.
820 1269035 : if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) {
821 : SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin();
822 : SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd();
823 1675 : for (; PDI != PDE; ++PDI) {
824 6 : MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap);
825 6 : if (DbgMI)
826 6 : BB->insert(InsertPos, DbgMI);
827 : }
828 : }
829 :
830 18848416 : for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
831 16310345 : SUnit *SU = Sequence[i];
832 16310345 : if (!SU) {
833 : // Null SUnit* is a noop.
834 0 : TII->insertNoop(*Emitter.getBlock(), InsertPos);
835 130 : continue;
836 : }
837 :
838 : // For pre-regalloc scheduling, create instructions corresponding to the
839 : // SDNode and any glued SDNodes and append them to the block.
840 16310345 : if (!SU->getNode()) {
841 : // Emit a copy.
842 130 : EmitPhysRegCopy(SU, CopyVRBaseMap, InsertPos);
843 130 : continue;
844 : }
845 :
846 : SmallVector<SDNode *, 4> GluedNodes;
847 40350339 : for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode())
848 3999442 : GluedNodes.push_back(N);
849 20309661 : while (!GluedNodes.empty()) {
850 3999444 : SDNode *N = GluedNodes.back();
851 3999444 : Emitter.EmitNode(N, SU->OrigNode != SU, SU->isCloned, VRBaseMap);
852 : // Remember the source order of the inserted instruction.
853 3999444 : if (HasDbg)
854 40525 : ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen);
855 : GluedNodes.pop_back();
856 : }
857 16310217 : Emitter.EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned,
858 : VRBaseMap);
859 : // Remember the source order of the inserted instruction.
860 16310216 : if (HasDbg)
861 190334 : ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders,
862 : Seen);
863 : }
864 :
865 : // Insert all the dbg_values which have not already been inserted in source
866 : // order sequence.
867 1269036 : if (HasDbg) {
868 19224 : MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI();
869 :
870 : // Sort the source order instructions and use the order to insert debug
871 : // values. Use stable_sort so that DBG_VALUEs are inserted in the same order
872 : // regardless of the host's implementation fo std::sort.
873 : std::stable_sort(Orders.begin(), Orders.end(), less_first());
874 19224 : std::stable_sort(DAG->DbgBegin(), DAG->DbgEnd(),
875 : [](const SDDbgValue *LHS, const SDDbgValue *RHS) {
876 0 : return LHS->getOrder() < RHS->getOrder();
877 : });
878 :
879 19224 : SDDbgInfo::DbgIterator DI = DAG->DbgBegin();
880 : SDDbgInfo::DbgIterator DE = DAG->DbgEnd();
881 : // Now emit the rest according to source order.
882 : unsigned LastOrder = 0;
883 122136 : for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) {
884 102912 : unsigned Order = Orders[i].first;
885 102912 : MachineInstr *MI = Orders[i].second;
886 : // Insert all SDDbgValue's whose order(s) are before "Order".
887 102912 : if (!MI)
888 : continue;
889 189525 : for (; DI != DE; ++DI) {
890 171209 : if ((*DI)->getOrder() < LastOrder || (*DI)->getOrder() >= Order)
891 : break;
892 103089 : if ((*DI)->isInvalidated())
893 : continue;
894 :
895 43279 : MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap);
896 43279 : if (DbgMI) {
897 43279 : if (!LastOrder)
898 : // Insert to start of the BB (after PHIs).
899 25452 : BB->insert(BBBegin, DbgMI);
900 : else {
901 : // Insert at the instruction, which may be in a different
902 : // block, if the block was split by a custom inserter.
903 : MachineBasicBlock::iterator Pos = MI;
904 17827 : MI->getParent()->insert(Pos, DbgMI);
905 : }
906 : }
907 : }
908 : LastOrder = Order;
909 : }
910 : // Add trailing DbgValue's before the terminator. FIXME: May want to add
911 : // some of them before one or more conditional branches?
912 : SmallVector<MachineInstr*, 8> DbgMIs;
913 21106 : for (; DI != DE; ++DI) {
914 1882 : if ((*DI)->isInvalidated())
915 : continue;
916 : assert((*DI)->getOrder() >= LastOrder &&
917 : "emitting DBG_VALUE out of order");
918 791 : if (MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap))
919 791 : DbgMIs.push_back(DbgMI);
920 : }
921 :
922 19224 : MachineBasicBlock *InsertBB = Emitter.getBlock();
923 19224 : MachineBasicBlock::iterator Pos = InsertBB->getFirstTerminator();
924 : InsertBB->insert(Pos, DbgMIs.begin(), DbgMIs.end());
925 :
926 19224 : SDDbgInfo::DbgLabelIterator DLI = DAG->DbgLabelBegin();
927 : SDDbgInfo::DbgLabelIterator DLE = DAG->DbgLabelEnd();
928 : // Now emit the rest according to source order.
929 : LastOrder = 0;
930 35566 : for (const auto &InstrOrder : Orders) {
931 35323 : unsigned Order = InstrOrder.first;
932 35323 : MachineInstr *MI = InstrOrder.second;
933 35323 : if (!MI)
934 : continue;
935 :
936 : // Insert all SDDbgLabel's whose order(s) are before "Order".
937 1 : for (; DLI != DLE &&
938 18983 : (*DLI)->getOrder() >= LastOrder && (*DLI)->getOrder() < Order;
939 : ++DLI) {
940 1 : MachineInstr *DbgMI = Emitter.EmitDbgLabel(*DLI);
941 1 : if (DbgMI) {
942 1 : if (!LastOrder)
943 : // Insert to start of the BB (after PHIs).
944 0 : BB->insert(BBBegin, DbgMI);
945 : else {
946 : // Insert at the instruction, which may be in a different
947 : // block, if the block was split by a custom inserter.
948 : MachineBasicBlock::iterator Pos = MI;
949 1 : MI->getParent()->insert(Pos, DbgMI);
950 : }
951 : }
952 : }
953 18982 : if (DLI == DLE)
954 : break;
955 :
956 : LastOrder = Order;
957 : }
958 : }
959 :
960 1269036 : InsertPos = Emitter.getInsertPos();
961 1269036 : return Emitter.getBlock();
962 : }
963 :
964 : /// Return the basic block label.
965 0 : std::string ScheduleDAGSDNodes::getDAGName() const {
966 0 : return "sunit-dag." + BB->getFullName();
967 : }
|
