1 //===- MachinePipeliner.cpp - Machine Software Pipeliner Pass -------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // An implementation of the Swing Modulo Scheduling (SMS) software pipeliner.
10 //
11 // This SMS implementation is a target-independent back-end pass. When enabled,
12 // the pass runs just prior to the register allocation pass, while the machine
13 // IR is in SSA form. If software pipelining is successful, then the original
14 // loop is replaced by the optimized loop. The optimized loop contains one or
15 // more prolog blocks, the pipelined kernel, and one or more epilog blocks. If
16 // the instructions cannot be scheduled in a given MII, we increase the MII by
17 // one and try again.
18 //
19 // The SMS implementation is an extension of the ScheduleDAGInstrs class. We
20 // represent loop carried dependences in the DAG as order edges to the Phi
21 // nodes. We also perform several passes over the DAG to eliminate unnecessary
22 // edges that inhibit the ability to pipeline. The implementation uses the
23 // DFAPacketizer class to compute the minimum initiation interval and the check
24 // where an instruction may be inserted in the pipelined schedule.
25 //
26 // In order for the SMS pass to work, several target specific hooks need to be
27 // implemented to get information about the loop structure and to rewrite
28 // instructions.
29 //
30 //===----------------------------------------------------------------------===//
31
32 #include "llvm/ADT/ArrayRef.h"
33 #include "llvm/ADT/BitVector.h"
34 #include "llvm/ADT/DenseMap.h"
35 #include "llvm/ADT/MapVector.h"
36 #include "llvm/ADT/PriorityQueue.h"
37 #include "llvm/ADT/SetVector.h"
38 #include "llvm/ADT/SmallPtrSet.h"
39 #include "llvm/ADT/SmallSet.h"
40 #include "llvm/ADT/SmallVector.h"
41 #include "llvm/ADT/Statistic.h"
42 #include "llvm/ADT/iterator_range.h"
43 #include "llvm/Analysis/AliasAnalysis.h"
44 #include "llvm/Analysis/MemoryLocation.h"
45 #include "llvm/Analysis/ValueTracking.h"
46 #include "llvm/CodeGen/DFAPacketizer.h"
47 #include "llvm/CodeGen/LiveIntervals.h"
48 #include "llvm/CodeGen/MachineBasicBlock.h"
49 #include "llvm/CodeGen/MachineDominators.h"
50 #include "llvm/CodeGen/MachineFunction.h"
51 #include "llvm/CodeGen/MachineFunctionPass.h"
52 #include "llvm/CodeGen/MachineInstr.h"
53 #include "llvm/CodeGen/MachineInstrBuilder.h"
54 #include "llvm/CodeGen/MachineLoopInfo.h"
55 #include "llvm/CodeGen/MachineMemOperand.h"
56 #include "llvm/CodeGen/MachineOperand.h"
57 #include "llvm/CodeGen/MachinePipeliner.h"
58 #include "llvm/CodeGen/MachineRegisterInfo.h"
59 #include "llvm/CodeGen/ModuloSchedule.h"
60 #include "llvm/CodeGen/RegisterPressure.h"
61 #include "llvm/CodeGen/ScheduleDAG.h"
62 #include "llvm/CodeGen/ScheduleDAGMutation.h"
63 #include "llvm/CodeGen/TargetOpcodes.h"
64 #include "llvm/CodeGen/TargetRegisterInfo.h"
65 #include "llvm/CodeGen/TargetSubtargetInfo.h"
66 #include "llvm/Config/llvm-config.h"
67 #include "llvm/IR/Attributes.h"
68 #include "llvm/IR/DebugLoc.h"
69 #include "llvm/IR/Function.h"
70 #include "llvm/MC/LaneBitmask.h"
71 #include "llvm/MC/MCInstrDesc.h"
72 #include "llvm/MC/MCInstrItineraries.h"
73 #include "llvm/MC/MCRegisterInfo.h"
74 #include "llvm/Pass.h"
75 #include "llvm/Support/CommandLine.h"
76 #include "llvm/Support/Compiler.h"
77 #include "llvm/Support/Debug.h"
78 #include "llvm/Support/MathExtras.h"
79 #include "llvm/Support/raw_ostream.h"
80 #include <algorithm>
81 #include <cassert>
82 #include <climits>
83 #include <cstdint>
84 #include <deque>
85 #include <functional>
86 #include <iterator>
87 #include <map>
88 #include <memory>
89 #include <tuple>
90 #include <utility>
91 #include <vector>
92
93 using namespace llvm;
94
95 #define DEBUG_TYPE "pipeliner"
96
97 STATISTIC(NumTrytoPipeline, "Number of loops that we attempt to pipeline");
98 STATISTIC(NumPipelined, "Number of loops software pipelined");
99 STATISTIC(NumNodeOrderIssues, "Number of node order issues found");
100 STATISTIC(NumFailBranch, "Pipeliner abort due to unknown branch");
101 STATISTIC(NumFailLoop, "Pipeliner abort due to unsupported loop");
102 STATISTIC(NumFailPreheader, "Pipeliner abort due to missing preheader");
103 STATISTIC(NumFailLargeMaxMII, "Pipeliner abort due to MaxMII too large");
104 STATISTIC(NumFailZeroMII, "Pipeliner abort due to zero MII");
105 STATISTIC(NumFailNoSchedule, "Pipeliner abort due to no schedule found");
106 STATISTIC(NumFailZeroStage, "Pipeliner abort due to zero stage");
107 STATISTIC(NumFailLargeMaxStage, "Pipeliner abort due to too many stages");
108
109 /// A command line option to turn software pipelining on or off.
110 static cl::opt<bool> EnableSWP("enable-pipeliner", cl::Hidden, cl::init(true),
111 cl::ZeroOrMore,
112 cl::desc("Enable Software Pipelining"));
113
114 /// A command line option to enable SWP at -Os.
115 static cl::opt<bool> EnableSWPOptSize("enable-pipeliner-opt-size",
116 cl::desc("Enable SWP at Os."), cl::Hidden,
117 cl::init(false));
118
119 /// A command line argument to limit minimum initial interval for pipelining.
120 static cl::opt<int> SwpMaxMii("pipeliner-max-mii",
121 cl::desc("Size limit for the MII."),
122 cl::Hidden, cl::init(27));
123
124 /// A command line argument to limit the number of stages in the pipeline.
125 static cl::opt<int>
126 SwpMaxStages("pipeliner-max-stages",
127 cl::desc("Maximum stages allowed in the generated scheduled."),
128 cl::Hidden, cl::init(3));
129
130 /// A command line option to disable the pruning of chain dependences due to
131 /// an unrelated Phi.
132 static cl::opt<bool>
133 SwpPruneDeps("pipeliner-prune-deps",
134 cl::desc("Prune dependences between unrelated Phi nodes."),
135 cl::Hidden, cl::init(true));
136
137 /// A command line option to disable the pruning of loop carried order
138 /// dependences.
139 static cl::opt<bool>
140 SwpPruneLoopCarried("pipeliner-prune-loop-carried",
141 cl::desc("Prune loop carried order dependences."),
142 cl::Hidden, cl::init(true));
143
144 #ifndef NDEBUG
145 static cl::opt<int> SwpLoopLimit("pipeliner-max", cl::Hidden, cl::init(-1));
146 #endif
147
148 static cl::opt<bool> SwpIgnoreRecMII("pipeliner-ignore-recmii",
149 cl::ReallyHidden, cl::init(false),
150 cl::ZeroOrMore, cl::desc("Ignore RecMII"));
151
152 static cl::opt<bool> SwpShowResMask("pipeliner-show-mask", cl::Hidden,
153 cl::init(false));
154 static cl::opt<bool> SwpDebugResource("pipeliner-dbg-res", cl::Hidden,
155 cl::init(false));
156
157 static cl::opt<bool> EmitTestAnnotations(
158 "pipeliner-annotate-for-testing", cl::Hidden, cl::init(false),
159 cl::desc("Instead of emitting the pipelined code, annotate instructions "
160 "with the generated schedule for feeding into the "
161 "-modulo-schedule-test pass"));
162
163 static cl::opt<bool> ExperimentalCodeGen(
164 "pipeliner-experimental-cg", cl::Hidden, cl::init(false),
165 cl::desc(
166 "Use the experimental peeling code generator for software pipelining"));
167
168 namespace llvm {
169
170 // A command line option to enable the CopyToPhi DAG mutation.
171 cl::opt<bool>
172 SwpEnableCopyToPhi("pipeliner-enable-copytophi", cl::ReallyHidden,
173 cl::init(true), cl::ZeroOrMore,
174 cl::desc("Enable CopyToPhi DAG Mutation"));
175
176 } // end namespace llvm
177
178 unsigned SwingSchedulerDAG::Circuits::MaxPaths = 5;
179 char MachinePipeliner::ID = 0;
180 #ifndef NDEBUG
181 int MachinePipeliner::NumTries = 0;
182 #endif
183 char &llvm::MachinePipelinerID = MachinePipeliner::ID;
184
185 INITIALIZE_PASS_BEGIN(MachinePipeliner, DEBUG_TYPE,
186 "Modulo Software Pipelining", false, false)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)187 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
188 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
189 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
190 INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
191 INITIALIZE_PASS_END(MachinePipeliner, DEBUG_TYPE,
192 "Modulo Software Pipelining", false, false)
193
194 /// The "main" function for implementing Swing Modulo Scheduling.
195 bool MachinePipeliner::runOnMachineFunction(MachineFunction &mf) {
196 if (skipFunction(mf.getFunction()))
197 return false;
198
199 if (!EnableSWP)
200 return false;
201
202 if (mf.getFunction().getAttributes().hasAttribute(
203 AttributeList::FunctionIndex, Attribute::OptimizeForSize) &&
204 !EnableSWPOptSize.getPosition())
205 return false;
206
207 if (!mf.getSubtarget().enableMachinePipeliner())
208 return false;
209
210 // Cannot pipeline loops without instruction itineraries if we are using
211 // DFA for the pipeliner.
212 if (mf.getSubtarget().useDFAforSMS() &&
213 (!mf.getSubtarget().getInstrItineraryData() ||
214 mf.getSubtarget().getInstrItineraryData()->isEmpty()))
215 return false;
216
217 MF = &mf;
218 MLI = &getAnalysis<MachineLoopInfo>();
219 MDT = &getAnalysis<MachineDominatorTree>();
220 ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
221 TII = MF->getSubtarget().getInstrInfo();
222 RegClassInfo.runOnMachineFunction(*MF);
223
224 for (auto &L : *MLI)
225 scheduleLoop(*L);
226
227 return false;
228 }
229
230 /// Attempt to perform the SMS algorithm on the specified loop. This function is
231 /// the main entry point for the algorithm. The function identifies candidate
232 /// loops, calculates the minimum initiation interval, and attempts to schedule
233 /// the loop.
scheduleLoop(MachineLoop & L)234 bool MachinePipeliner::scheduleLoop(MachineLoop &L) {
235 bool Changed = false;
236 for (auto &InnerLoop : L)
237 Changed |= scheduleLoop(*InnerLoop);
238
239 #ifndef NDEBUG
240 // Stop trying after reaching the limit (if any).
241 int Limit = SwpLoopLimit;
242 if (Limit >= 0) {
243 if (NumTries >= SwpLoopLimit)
244 return Changed;
245 NumTries++;
246 }
247 #endif
248
249 setPragmaPipelineOptions(L);
250 if (!canPipelineLoop(L)) {
251 LLVM_DEBUG(dbgs() << "\n!!! Can not pipeline loop.\n");
252 ORE->emit([&]() {
253 return MachineOptimizationRemarkMissed(DEBUG_TYPE, "canPipelineLoop",
254 L.getStartLoc(), L.getHeader())
255 << "Failed to pipeline loop";
256 });
257
258 return Changed;
259 }
260
261 ++NumTrytoPipeline;
262
263 Changed = swingModuloScheduler(L);
264
265 return Changed;
266 }
267
setPragmaPipelineOptions(MachineLoop & L)268 void MachinePipeliner::setPragmaPipelineOptions(MachineLoop &L) {
269 // Reset the pragma for the next loop in iteration.
270 disabledByPragma = false;
271 II_setByPragma = 0;
272
273 MachineBasicBlock *LBLK = L.getTopBlock();
274
275 if (LBLK == nullptr)
276 return;
277
278 const BasicBlock *BBLK = LBLK->getBasicBlock();
279 if (BBLK == nullptr)
280 return;
281
282 const Instruction *TI = BBLK->getTerminator();
283 if (TI == nullptr)
284 return;
285
286 MDNode *LoopID = TI->getMetadata(LLVMContext::MD_loop);
287 if (LoopID == nullptr)
288 return;
289
290 assert(LoopID->getNumOperands() > 0 && "requires atleast one operand");
291 assert(LoopID->getOperand(0) == LoopID && "invalid loop");
292
293 for (unsigned i = 1, e = LoopID->getNumOperands(); i < e; ++i) {
294 MDNode *MD = dyn_cast<MDNode>(LoopID->getOperand(i));
295
296 if (MD == nullptr)
297 continue;
298
299 MDString *S = dyn_cast<MDString>(MD->getOperand(0));
300
301 if (S == nullptr)
302 continue;
303
304 if (S->getString() == "llvm.loop.pipeline.initiationinterval") {
305 assert(MD->getNumOperands() == 2 &&
306 "Pipeline initiation interval hint metadata should have two operands.");
307 II_setByPragma =
308 mdconst::extract<ConstantInt>(MD->getOperand(1))->getZExtValue();
309 assert(II_setByPragma >= 1 && "Pipeline initiation interval must be positive.");
310 } else if (S->getString() == "llvm.loop.pipeline.disable") {
311 disabledByPragma = true;
312 }
313 }
314 }
315
316 /// Return true if the loop can be software pipelined. The algorithm is
317 /// restricted to loops with a single basic block. Make sure that the
318 /// branch in the loop can be analyzed.
canPipelineLoop(MachineLoop & L)319 bool MachinePipeliner::canPipelineLoop(MachineLoop &L) {
320 if (L.getNumBlocks() != 1) {
321 ORE->emit([&]() {
322 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
323 L.getStartLoc(), L.getHeader())
324 << "Not a single basic block: "
325 << ore::NV("NumBlocks", L.getNumBlocks());
326 });
327 return false;
328 }
329
330 if (disabledByPragma) {
331 ORE->emit([&]() {
332 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
333 L.getStartLoc(), L.getHeader())
334 << "Disabled by Pragma.";
335 });
336 return false;
337 }
338
339 // Check if the branch can't be understood because we can't do pipelining
340 // if that's the case.
341 LI.TBB = nullptr;
342 LI.FBB = nullptr;
343 LI.BrCond.clear();
344 if (TII->analyzeBranch(*L.getHeader(), LI.TBB, LI.FBB, LI.BrCond)) {
345 LLVM_DEBUG(dbgs() << "Unable to analyzeBranch, can NOT pipeline Loop\n");
346 NumFailBranch++;
347 ORE->emit([&]() {
348 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
349 L.getStartLoc(), L.getHeader())
350 << "The branch can't be understood";
351 });
352 return false;
353 }
354
355 LI.LoopInductionVar = nullptr;
356 LI.LoopCompare = nullptr;
357 if (!TII->analyzeLoopForPipelining(L.getTopBlock())) {
358 LLVM_DEBUG(dbgs() << "Unable to analyzeLoop, can NOT pipeline Loop\n");
359 NumFailLoop++;
360 ORE->emit([&]() {
361 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
362 L.getStartLoc(), L.getHeader())
363 << "The loop structure is not supported";
364 });
365 return false;
366 }
367
368 if (!L.getLoopPreheader()) {
369 LLVM_DEBUG(dbgs() << "Preheader not found, can NOT pipeline Loop\n");
370 NumFailPreheader++;
371 ORE->emit([&]() {
372 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
373 L.getStartLoc(), L.getHeader())
374 << "No loop preheader found";
375 });
376 return false;
377 }
378
379 // Remove any subregisters from inputs to phi nodes.
380 preprocessPhiNodes(*L.getHeader());
381 return true;
382 }
383
preprocessPhiNodes(MachineBasicBlock & B)384 void MachinePipeliner::preprocessPhiNodes(MachineBasicBlock &B) {
385 MachineRegisterInfo &MRI = MF->getRegInfo();
386 SlotIndexes &Slots = *getAnalysis<LiveIntervals>().getSlotIndexes();
387
388 for (MachineInstr &PI : make_range(B.begin(), B.getFirstNonPHI())) {
389 MachineOperand &DefOp = PI.getOperand(0);
390 assert(DefOp.getSubReg() == 0);
391 auto *RC = MRI.getRegClass(DefOp.getReg());
392
393 for (unsigned i = 1, n = PI.getNumOperands(); i != n; i += 2) {
394 MachineOperand &RegOp = PI.getOperand(i);
395 if (RegOp.getSubReg() == 0)
396 continue;
397
398 // If the operand uses a subregister, replace it with a new register
399 // without subregisters, and generate a copy to the new register.
400 Register NewReg = MRI.createVirtualRegister(RC);
401 MachineBasicBlock &PredB = *PI.getOperand(i+1).getMBB();
402 MachineBasicBlock::iterator At = PredB.getFirstTerminator();
403 const DebugLoc &DL = PredB.findDebugLoc(At);
404 auto Copy = BuildMI(PredB, At, DL, TII->get(TargetOpcode::COPY), NewReg)
405 .addReg(RegOp.getReg(), getRegState(RegOp),
406 RegOp.getSubReg());
407 Slots.insertMachineInstrInMaps(*Copy);
408 RegOp.setReg(NewReg);
409 RegOp.setSubReg(0);
410 }
411 }
412 }
413
414 /// The SMS algorithm consists of the following main steps:
415 /// 1. Computation and analysis of the dependence graph.
416 /// 2. Ordering of the nodes (instructions).
417 /// 3. Attempt to Schedule the loop.
swingModuloScheduler(MachineLoop & L)418 bool MachinePipeliner::swingModuloScheduler(MachineLoop &L) {
419 assert(L.getBlocks().size() == 1 && "SMS works on single blocks only.");
420
421 SwingSchedulerDAG SMS(*this, L, getAnalysis<LiveIntervals>(), RegClassInfo,
422 II_setByPragma);
423
424 MachineBasicBlock *MBB = L.getHeader();
425 // The kernel should not include any terminator instructions. These
426 // will be added back later.
427 SMS.startBlock(MBB);
428
429 // Compute the number of 'real' instructions in the basic block by
430 // ignoring terminators.
431 unsigned size = MBB->size();
432 for (MachineBasicBlock::iterator I = MBB->getFirstTerminator(),
433 E = MBB->instr_end();
434 I != E; ++I, --size)
435 ;
436
437 SMS.enterRegion(MBB, MBB->begin(), MBB->getFirstTerminator(), size);
438 SMS.schedule();
439 SMS.exitRegion();
440
441 SMS.finishBlock();
442 return SMS.hasNewSchedule();
443 }
444
getAnalysisUsage(AnalysisUsage & AU) const445 void MachinePipeliner::getAnalysisUsage(AnalysisUsage &AU) const {
446 AU.addRequired<AAResultsWrapperPass>();
447 AU.addPreserved<AAResultsWrapperPass>();
448 AU.addRequired<MachineLoopInfo>();
449 AU.addRequired<MachineDominatorTree>();
450 AU.addRequired<LiveIntervals>();
451 AU.addRequired<MachineOptimizationRemarkEmitterPass>();
452 MachineFunctionPass::getAnalysisUsage(AU);
453 }
454
setMII(unsigned ResMII,unsigned RecMII)455 void SwingSchedulerDAG::setMII(unsigned ResMII, unsigned RecMII) {
456 if (II_setByPragma > 0)
457 MII = II_setByPragma;
458 else
459 MII = std::max(ResMII, RecMII);
460 }
461
setMAX_II()462 void SwingSchedulerDAG::setMAX_II() {
463 if (II_setByPragma > 0)
464 MAX_II = II_setByPragma;
465 else
466 MAX_II = MII + 10;
467 }
468
469 /// We override the schedule function in ScheduleDAGInstrs to implement the
470 /// scheduling part of the Swing Modulo Scheduling algorithm.
schedule()471 void SwingSchedulerDAG::schedule() {
472 AliasAnalysis *AA = &Pass.getAnalysis<AAResultsWrapperPass>().getAAResults();
473 buildSchedGraph(AA);
474 addLoopCarriedDependences(AA);
475 updatePhiDependences();
476 Topo.InitDAGTopologicalSorting();
477 changeDependences();
478 postprocessDAG();
479 LLVM_DEBUG(dump());
480
481 NodeSetType NodeSets;
482 findCircuits(NodeSets);
483 NodeSetType Circuits = NodeSets;
484
485 // Calculate the MII.
486 unsigned ResMII = calculateResMII();
487 unsigned RecMII = calculateRecMII(NodeSets);
488
489 fuseRecs(NodeSets);
490
491 // This flag is used for testing and can cause correctness problems.
492 if (SwpIgnoreRecMII)
493 RecMII = 0;
494
495 setMII(ResMII, RecMII);
496 setMAX_II();
497
498 LLVM_DEBUG(dbgs() << "MII = " << MII << " MAX_II = " << MAX_II
499 << " (rec=" << RecMII << ", res=" << ResMII << ")\n");
500
501 // Can't schedule a loop without a valid MII.
502 if (MII == 0) {
503 LLVM_DEBUG(dbgs() << "Invalid Minimal Initiation Interval: 0\n");
504 NumFailZeroMII++;
505 Pass.ORE->emit([&]() {
506 return MachineOptimizationRemarkAnalysis(
507 DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
508 << "Invalid Minimal Initiation Interval: 0";
509 });
510 return;
511 }
512
513 // Don't pipeline large loops.
514 if (SwpMaxMii != -1 && (int)MII > SwpMaxMii) {
515 LLVM_DEBUG(dbgs() << "MII > " << SwpMaxMii
516 << ", we don't pipleline large loops\n");
517 NumFailLargeMaxMII++;
518 Pass.ORE->emit([&]() {
519 return MachineOptimizationRemarkAnalysis(
520 DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
521 << "Minimal Initiation Interval too large: "
522 << ore::NV("MII", (int)MII) << " > "
523 << ore::NV("SwpMaxMii", SwpMaxMii) << "."
524 << "Refer to -pipeliner-max-mii.";
525 });
526 return;
527 }
528
529 computeNodeFunctions(NodeSets);
530
531 registerPressureFilter(NodeSets);
532
533 colocateNodeSets(NodeSets);
534
535 checkNodeSets(NodeSets);
536
537 LLVM_DEBUG({
538 for (auto &I : NodeSets) {
539 dbgs() << " Rec NodeSet ";
540 I.dump();
541 }
542 });
543
544 llvm::stable_sort(NodeSets, std::greater<NodeSet>());
545
546 groupRemainingNodes(NodeSets);
547
548 removeDuplicateNodes(NodeSets);
549
550 LLVM_DEBUG({
551 for (auto &I : NodeSets) {
552 dbgs() << " NodeSet ";
553 I.dump();
554 }
555 });
556
557 computeNodeOrder(NodeSets);
558
559 // check for node order issues
560 checkValidNodeOrder(Circuits);
561
562 SMSchedule Schedule(Pass.MF);
563 Scheduled = schedulePipeline(Schedule);
564
565 if (!Scheduled){
566 LLVM_DEBUG(dbgs() << "No schedule found, return\n");
567 NumFailNoSchedule++;
568 Pass.ORE->emit([&]() {
569 return MachineOptimizationRemarkAnalysis(
570 DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
571 << "Unable to find schedule";
572 });
573 return;
574 }
575
576 unsigned numStages = Schedule.getMaxStageCount();
577 // No need to generate pipeline if there are no overlapped iterations.
578 if (numStages == 0) {
579 LLVM_DEBUG(dbgs() << "No overlapped iterations, skip.\n");
580 NumFailZeroStage++;
581 Pass.ORE->emit([&]() {
582 return MachineOptimizationRemarkAnalysis(
583 DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
584 << "No need to pipeline - no overlapped iterations in schedule.";
585 });
586 return;
587 }
588 // Check that the maximum stage count is less than user-defined limit.
589 if (SwpMaxStages > -1 && (int)numStages > SwpMaxStages) {
590 LLVM_DEBUG(dbgs() << "numStages:" << numStages << ">" << SwpMaxStages
591 << " : too many stages, abort\n");
592 NumFailLargeMaxStage++;
593 Pass.ORE->emit([&]() {
594 return MachineOptimizationRemarkAnalysis(
595 DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
596 << "Too many stages in schedule: "
597 << ore::NV("numStages", (int)numStages) << " > "
598 << ore::NV("SwpMaxStages", SwpMaxStages)
599 << ". Refer to -pipeliner-max-stages.";
600 });
601 return;
602 }
603
604 Pass.ORE->emit([&]() {
605 return MachineOptimizationRemark(DEBUG_TYPE, "schedule", Loop.getStartLoc(),
606 Loop.getHeader())
607 << "Pipelined succesfully!";
608 });
609
610 // Generate the schedule as a ModuloSchedule.
611 DenseMap<MachineInstr *, int> Cycles, Stages;
612 std::vector<MachineInstr *> OrderedInsts;
613 for (int Cycle = Schedule.getFirstCycle(); Cycle <= Schedule.getFinalCycle();
614 ++Cycle) {
615 for (SUnit *SU : Schedule.getInstructions(Cycle)) {
616 OrderedInsts.push_back(SU->getInstr());
617 Cycles[SU->getInstr()] = Cycle;
618 Stages[SU->getInstr()] = Schedule.stageScheduled(SU);
619 }
620 }
621 DenseMap<MachineInstr *, std::pair<unsigned, int64_t>> NewInstrChanges;
622 for (auto &KV : NewMIs) {
623 Cycles[KV.first] = Cycles[KV.second];
624 Stages[KV.first] = Stages[KV.second];
625 NewInstrChanges[KV.first] = InstrChanges[getSUnit(KV.first)];
626 }
627
628 ModuloSchedule MS(MF, &Loop, std::move(OrderedInsts), std::move(Cycles),
629 std::move(Stages));
630 if (EmitTestAnnotations) {
631 assert(NewInstrChanges.empty() &&
632 "Cannot serialize a schedule with InstrChanges!");
633 ModuloScheduleTestAnnotater MSTI(MF, MS);
634 MSTI.annotate();
635 return;
636 }
637 // The experimental code generator can't work if there are InstChanges.
638 if (ExperimentalCodeGen && NewInstrChanges.empty()) {
639 PeelingModuloScheduleExpander MSE(MF, MS, &LIS);
640 MSE.expand();
641 } else {
642 ModuloScheduleExpander MSE(MF, MS, LIS, std::move(NewInstrChanges));
643 MSE.expand();
644 MSE.cleanup();
645 }
646 ++NumPipelined;
647 }
648
649 /// Clean up after the software pipeliner runs.
finishBlock()650 void SwingSchedulerDAG::finishBlock() {
651 for (auto &KV : NewMIs)
652 MF.DeleteMachineInstr(KV.second);
653 NewMIs.clear();
654
655 // Call the superclass.
656 ScheduleDAGInstrs::finishBlock();
657 }
658
659 /// Return the register values for the operands of a Phi instruction.
660 /// This function assume the instruction is a Phi.
getPhiRegs(MachineInstr & Phi,MachineBasicBlock * Loop,unsigned & InitVal,unsigned & LoopVal)661 static void getPhiRegs(MachineInstr &Phi, MachineBasicBlock *Loop,
662 unsigned &InitVal, unsigned &LoopVal) {
663 assert(Phi.isPHI() && "Expecting a Phi.");
664
665 InitVal = 0;
666 LoopVal = 0;
667 for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
668 if (Phi.getOperand(i + 1).getMBB() != Loop)
669 InitVal = Phi.getOperand(i).getReg();
670 else
671 LoopVal = Phi.getOperand(i).getReg();
672
673 assert(InitVal != 0 && LoopVal != 0 && "Unexpected Phi structure.");
674 }
675
676 /// Return the Phi register value that comes the loop block.
getLoopPhiReg(MachineInstr & Phi,MachineBasicBlock * LoopBB)677 static unsigned getLoopPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) {
678 for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
679 if (Phi.getOperand(i + 1).getMBB() == LoopBB)
680 return Phi.getOperand(i).getReg();
681 return 0;
682 }
683
684 /// Return true if SUb can be reached from SUa following the chain edges.
isSuccOrder(SUnit * SUa,SUnit * SUb)685 static bool isSuccOrder(SUnit *SUa, SUnit *SUb) {
686 SmallPtrSet<SUnit *, 8> Visited;
687 SmallVector<SUnit *, 8> Worklist;
688 Worklist.push_back(SUa);
689 while (!Worklist.empty()) {
690 const SUnit *SU = Worklist.pop_back_val();
691 for (auto &SI : SU->Succs) {
692 SUnit *SuccSU = SI.getSUnit();
693 if (SI.getKind() == SDep::Order) {
694 if (Visited.count(SuccSU))
695 continue;
696 if (SuccSU == SUb)
697 return true;
698 Worklist.push_back(SuccSU);
699 Visited.insert(SuccSU);
700 }
701 }
702 }
703 return false;
704 }
705
706 /// Return true if the instruction causes a chain between memory
707 /// references before and after it.
isDependenceBarrier(MachineInstr & MI,AliasAnalysis * AA)708 static bool isDependenceBarrier(MachineInstr &MI, AliasAnalysis *AA) {
709 return MI.isCall() || MI.mayRaiseFPException() ||
710 MI.hasUnmodeledSideEffects() ||
711 (MI.hasOrderedMemoryRef() &&
712 (!MI.mayLoad() || !MI.isDereferenceableInvariantLoad(AA)));
713 }
714
715 /// Return the underlying objects for the memory references of an instruction.
716 /// This function calls the code in ValueTracking, but first checks that the
717 /// instruction has a memory operand.
getUnderlyingObjects(const MachineInstr * MI,SmallVectorImpl<const Value * > & Objs)718 static void getUnderlyingObjects(const MachineInstr *MI,
719 SmallVectorImpl<const Value *> &Objs) {
720 if (!MI->hasOneMemOperand())
721 return;
722 MachineMemOperand *MM = *MI->memoperands_begin();
723 if (!MM->getValue())
724 return;
725 getUnderlyingObjects(MM->getValue(), Objs);
726 for (const Value *V : Objs) {
727 if (!isIdentifiedObject(V)) {
728 Objs.clear();
729 return;
730 }
731 Objs.push_back(V);
732 }
733 }
734
735 /// Add a chain edge between a load and store if the store can be an
736 /// alias of the load on a subsequent iteration, i.e., a loop carried
737 /// dependence. This code is very similar to the code in ScheduleDAGInstrs
738 /// but that code doesn't create loop carried dependences.
addLoopCarriedDependences(AliasAnalysis * AA)739 void SwingSchedulerDAG::addLoopCarriedDependences(AliasAnalysis *AA) {
740 MapVector<const Value *, SmallVector<SUnit *, 4>> PendingLoads;
741 Value *UnknownValue =
742 UndefValue::get(Type::getVoidTy(MF.getFunction().getContext()));
743 for (auto &SU : SUnits) {
744 MachineInstr &MI = *SU.getInstr();
745 if (isDependenceBarrier(MI, AA))
746 PendingLoads.clear();
747 else if (MI.mayLoad()) {
748 SmallVector<const Value *, 4> Objs;
749 ::getUnderlyingObjects(&MI, Objs);
750 if (Objs.empty())
751 Objs.push_back(UnknownValue);
752 for (auto V : Objs) {
753 SmallVector<SUnit *, 4> &SUs = PendingLoads[V];
754 SUs.push_back(&SU);
755 }
756 } else if (MI.mayStore()) {
757 SmallVector<const Value *, 4> Objs;
758 ::getUnderlyingObjects(&MI, Objs);
759 if (Objs.empty())
760 Objs.push_back(UnknownValue);
761 for (auto V : Objs) {
762 MapVector<const Value *, SmallVector<SUnit *, 4>>::iterator I =
763 PendingLoads.find(V);
764 if (I == PendingLoads.end())
765 continue;
766 for (auto Load : I->second) {
767 if (isSuccOrder(Load, &SU))
768 continue;
769 MachineInstr &LdMI = *Load->getInstr();
770 // First, perform the cheaper check that compares the base register.
771 // If they are the same and the load offset is less than the store
772 // offset, then mark the dependence as loop carried potentially.
773 const MachineOperand *BaseOp1, *BaseOp2;
774 int64_t Offset1, Offset2;
775 bool Offset1IsScalable, Offset2IsScalable;
776 if (TII->getMemOperandWithOffset(LdMI, BaseOp1, Offset1,
777 Offset1IsScalable, TRI) &&
778 TII->getMemOperandWithOffset(MI, BaseOp2, Offset2,
779 Offset2IsScalable, TRI)) {
780 if (BaseOp1->isIdenticalTo(*BaseOp2) &&
781 Offset1IsScalable == Offset2IsScalable &&
782 (int)Offset1 < (int)Offset2) {
783 assert(TII->areMemAccessesTriviallyDisjoint(LdMI, MI) &&
784 "What happened to the chain edge?");
785 SDep Dep(Load, SDep::Barrier);
786 Dep.setLatency(1);
787 SU.addPred(Dep);
788 continue;
789 }
790 }
791 // Second, the more expensive check that uses alias analysis on the
792 // base registers. If they alias, and the load offset is less than
793 // the store offset, the mark the dependence as loop carried.
794 if (!AA) {
795 SDep Dep(Load, SDep::Barrier);
796 Dep.setLatency(1);
797 SU.addPred(Dep);
798 continue;
799 }
800 MachineMemOperand *MMO1 = *LdMI.memoperands_begin();
801 MachineMemOperand *MMO2 = *MI.memoperands_begin();
802 if (!MMO1->getValue() || !MMO2->getValue()) {
803 SDep Dep(Load, SDep::Barrier);
804 Dep.setLatency(1);
805 SU.addPred(Dep);
806 continue;
807 }
808 if (MMO1->getValue() == MMO2->getValue() &&
809 MMO1->getOffset() <= MMO2->getOffset()) {
810 SDep Dep(Load, SDep::Barrier);
811 Dep.setLatency(1);
812 SU.addPred(Dep);
813 continue;
814 }
815 AliasResult AAResult = AA->alias(
816 MemoryLocation::getAfter(MMO1->getValue(), MMO1->getAAInfo()),
817 MemoryLocation::getAfter(MMO2->getValue(), MMO2->getAAInfo()));
818
819 if (AAResult != NoAlias) {
820 SDep Dep(Load, SDep::Barrier);
821 Dep.setLatency(1);
822 SU.addPred(Dep);
823 }
824 }
825 }
826 }
827 }
828 }
829
830 /// Update the phi dependences to the DAG because ScheduleDAGInstrs no longer
831 /// processes dependences for PHIs. This function adds true dependences
832 /// from a PHI to a use, and a loop carried dependence from the use to the
833 /// PHI. The loop carried dependence is represented as an anti dependence
834 /// edge. This function also removes chain dependences between unrelated
835 /// PHIs.
updatePhiDependences()836 void SwingSchedulerDAG::updatePhiDependences() {
837 SmallVector<SDep, 4> RemoveDeps;
838 const TargetSubtargetInfo &ST = MF.getSubtarget<TargetSubtargetInfo>();
839
840 // Iterate over each DAG node.
841 for (SUnit &I : SUnits) {
842 RemoveDeps.clear();
843 // Set to true if the instruction has an operand defined by a Phi.
844 unsigned HasPhiUse = 0;
845 unsigned HasPhiDef = 0;
846 MachineInstr *MI = I.getInstr();
847 // Iterate over each operand, and we process the definitions.
848 for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
849 MOE = MI->operands_end();
850 MOI != MOE; ++MOI) {
851 if (!MOI->isReg())
852 continue;
853 Register Reg = MOI->getReg();
854 if (MOI->isDef()) {
855 // If the register is used by a Phi, then create an anti dependence.
856 for (MachineRegisterInfo::use_instr_iterator
857 UI = MRI.use_instr_begin(Reg),
858 UE = MRI.use_instr_end();
859 UI != UE; ++UI) {
860 MachineInstr *UseMI = &*UI;
861 SUnit *SU = getSUnit(UseMI);
862 if (SU != nullptr && UseMI->isPHI()) {
863 if (!MI->isPHI()) {
864 SDep Dep(SU, SDep::Anti, Reg);
865 Dep.setLatency(1);
866 I.addPred(Dep);
867 } else {
868 HasPhiDef = Reg;
869 // Add a chain edge to a dependent Phi that isn't an existing
870 // predecessor.
871 if (SU->NodeNum < I.NodeNum && !I.isPred(SU))
872 I.addPred(SDep(SU, SDep::Barrier));
873 }
874 }
875 }
876 } else if (MOI->isUse()) {
877 // If the register is defined by a Phi, then create a true dependence.
878 MachineInstr *DefMI = MRI.getUniqueVRegDef(Reg);
879 if (DefMI == nullptr)
880 continue;
881 SUnit *SU = getSUnit(DefMI);
882 if (SU != nullptr && DefMI->isPHI()) {
883 if (!MI->isPHI()) {
884 SDep Dep(SU, SDep::Data, Reg);
885 Dep.setLatency(0);
886 ST.adjustSchedDependency(SU, 0, &I, MI->getOperandNo(MOI), Dep);
887 I.addPred(Dep);
888 } else {
889 HasPhiUse = Reg;
890 // Add a chain edge to a dependent Phi that isn't an existing
891 // predecessor.
892 if (SU->NodeNum < I.NodeNum && !I.isPred(SU))
893 I.addPred(SDep(SU, SDep::Barrier));
894 }
895 }
896 }
897 }
898 // Remove order dependences from an unrelated Phi.
899 if (!SwpPruneDeps)
900 continue;
901 for (auto &PI : I.Preds) {
902 MachineInstr *PMI = PI.getSUnit()->getInstr();
903 if (PMI->isPHI() && PI.getKind() == SDep::Order) {
904 if (I.getInstr()->isPHI()) {
905 if (PMI->getOperand(0).getReg() == HasPhiUse)
906 continue;
907 if (getLoopPhiReg(*PMI, PMI->getParent()) == HasPhiDef)
908 continue;
909 }
910 RemoveDeps.push_back(PI);
911 }
912 }
913 for (int i = 0, e = RemoveDeps.size(); i != e; ++i)
914 I.removePred(RemoveDeps[i]);
915 }
916 }
917
918 /// Iterate over each DAG node and see if we can change any dependences
919 /// in order to reduce the recurrence MII.
changeDependences()920 void SwingSchedulerDAG::changeDependences() {
921 // See if an instruction can use a value from the previous iteration.
922 // If so, we update the base and offset of the instruction and change
923 // the dependences.
924 for (SUnit &I : SUnits) {
925 unsigned BasePos = 0, OffsetPos = 0, NewBase = 0;
926 int64_t NewOffset = 0;
927 if (!canUseLastOffsetValue(I.getInstr(), BasePos, OffsetPos, NewBase,
928 NewOffset))
929 continue;
930
931 // Get the MI and SUnit for the instruction that defines the original base.
932 Register OrigBase = I.getInstr()->getOperand(BasePos).getReg();
933 MachineInstr *DefMI = MRI.getUniqueVRegDef(OrigBase);
934 if (!DefMI)
935 continue;
936 SUnit *DefSU = getSUnit(DefMI);
937 if (!DefSU)
938 continue;
939 // Get the MI and SUnit for the instruction that defins the new base.
940 MachineInstr *LastMI = MRI.getUniqueVRegDef(NewBase);
941 if (!LastMI)
942 continue;
943 SUnit *LastSU = getSUnit(LastMI);
944 if (!LastSU)
945 continue;
946
947 if (Topo.IsReachable(&I, LastSU))
948 continue;
949
950 // Remove the dependence. The value now depends on a prior iteration.
951 SmallVector<SDep, 4> Deps;
952 for (SUnit::pred_iterator P = I.Preds.begin(), E = I.Preds.end(); P != E;
953 ++P)
954 if (P->getSUnit() == DefSU)
955 Deps.push_back(*P);
956 for (int i = 0, e = Deps.size(); i != e; i++) {
957 Topo.RemovePred(&I, Deps[i].getSUnit());
958 I.removePred(Deps[i]);
959 }
960 // Remove the chain dependence between the instructions.
961 Deps.clear();
962 for (auto &P : LastSU->Preds)
963 if (P.getSUnit() == &I && P.getKind() == SDep::Order)
964 Deps.push_back(P);
965 for (int i = 0, e = Deps.size(); i != e; i++) {
966 Topo.RemovePred(LastSU, Deps[i].getSUnit());
967 LastSU->removePred(Deps[i]);
968 }
969
970 // Add a dependence between the new instruction and the instruction
971 // that defines the new base.
972 SDep Dep(&I, SDep::Anti, NewBase);
973 Topo.AddPred(LastSU, &I);
974 LastSU->addPred(Dep);
975
976 // Remember the base and offset information so that we can update the
977 // instruction during code generation.
978 InstrChanges[&I] = std::make_pair(NewBase, NewOffset);
979 }
980 }
981
982 namespace {
983
984 // FuncUnitSorter - Comparison operator used to sort instructions by
985 // the number of functional unit choices.
986 struct FuncUnitSorter {
987 const InstrItineraryData *InstrItins;
988 const MCSubtargetInfo *STI;
989 DenseMap<InstrStage::FuncUnits, unsigned> Resources;
990
FuncUnitSorter__anonb9cc22090d11::FuncUnitSorter991 FuncUnitSorter(const TargetSubtargetInfo &TSI)
992 : InstrItins(TSI.getInstrItineraryData()), STI(&TSI) {}
993
994 // Compute the number of functional unit alternatives needed
995 // at each stage, and take the minimum value. We prioritize the
996 // instructions by the least number of choices first.
minFuncUnits__anonb9cc22090d11::FuncUnitSorter997 unsigned minFuncUnits(const MachineInstr *Inst,
998 InstrStage::FuncUnits &F) const {
999 unsigned SchedClass = Inst->getDesc().getSchedClass();
1000 unsigned min = UINT_MAX;
1001 if (InstrItins && !InstrItins->isEmpty()) {
1002 for (const InstrStage &IS :
1003 make_range(InstrItins->beginStage(SchedClass),
1004 InstrItins->endStage(SchedClass))) {
1005 InstrStage::FuncUnits funcUnits = IS.getUnits();
1006 unsigned numAlternatives = countPopulation(funcUnits);
1007 if (numAlternatives < min) {
1008 min = numAlternatives;
1009 F = funcUnits;
1010 }
1011 }
1012 return min;
1013 }
1014 if (STI && STI->getSchedModel().hasInstrSchedModel()) {
1015 const MCSchedClassDesc *SCDesc =
1016 STI->getSchedModel().getSchedClassDesc(SchedClass);
1017 if (!SCDesc->isValid())
1018 // No valid Schedule Class Desc for schedClass, should be
1019 // Pseudo/PostRAPseudo
1020 return min;
1021
1022 for (const MCWriteProcResEntry &PRE :
1023 make_range(STI->getWriteProcResBegin(SCDesc),
1024 STI->getWriteProcResEnd(SCDesc))) {
1025 if (!PRE.Cycles)
1026 continue;
1027 const MCProcResourceDesc *ProcResource =
1028 STI->getSchedModel().getProcResource(PRE.ProcResourceIdx);
1029 unsigned NumUnits = ProcResource->NumUnits;
1030 if (NumUnits < min) {
1031 min = NumUnits;
1032 F = PRE.ProcResourceIdx;
1033 }
1034 }
1035 return min;
1036 }
1037 llvm_unreachable("Should have non-empty InstrItins or hasInstrSchedModel!");
1038 }
1039
1040 // Compute the critical resources needed by the instruction. This
1041 // function records the functional units needed by instructions that
1042 // must use only one functional unit. We use this as a tie breaker
1043 // for computing the resource MII. The instrutions that require
1044 // the same, highly used, functional unit have high priority.
calcCriticalResources__anonb9cc22090d11::FuncUnitSorter1045 void calcCriticalResources(MachineInstr &MI) {
1046 unsigned SchedClass = MI.getDesc().getSchedClass();
1047 if (InstrItins && !InstrItins->isEmpty()) {
1048 for (const InstrStage &IS :
1049 make_range(InstrItins->beginStage(SchedClass),
1050 InstrItins->endStage(SchedClass))) {
1051 InstrStage::FuncUnits FuncUnits = IS.getUnits();
1052 if (countPopulation(FuncUnits) == 1)
1053 Resources[FuncUnits]++;
1054 }
1055 return;
1056 }
1057 if (STI && STI->getSchedModel().hasInstrSchedModel()) {
1058 const MCSchedClassDesc *SCDesc =
1059 STI->getSchedModel().getSchedClassDesc(SchedClass);
1060 if (!SCDesc->isValid())
1061 // No valid Schedule Class Desc for schedClass, should be
1062 // Pseudo/PostRAPseudo
1063 return;
1064
1065 for (const MCWriteProcResEntry &PRE :
1066 make_range(STI->getWriteProcResBegin(SCDesc),
1067 STI->getWriteProcResEnd(SCDesc))) {
1068 if (!PRE.Cycles)
1069 continue;
1070 Resources[PRE.ProcResourceIdx]++;
1071 }
1072 return;
1073 }
1074 llvm_unreachable("Should have non-empty InstrItins or hasInstrSchedModel!");
1075 }
1076
1077 /// Return true if IS1 has less priority than IS2.
operator ()__anonb9cc22090d11::FuncUnitSorter1078 bool operator()(const MachineInstr *IS1, const MachineInstr *IS2) const {
1079 InstrStage::FuncUnits F1 = 0, F2 = 0;
1080 unsigned MFUs1 = minFuncUnits(IS1, F1);
1081 unsigned MFUs2 = minFuncUnits(IS2, F2);
1082 if (MFUs1 == MFUs2)
1083 return Resources.lookup(F1) < Resources.lookup(F2);
1084 return MFUs1 > MFUs2;
1085 }
1086 };
1087
1088 } // end anonymous namespace
1089
1090 /// Calculate the resource constrained minimum initiation interval for the
1091 /// specified loop. We use the DFA to model the resources needed for
1092 /// each instruction, and we ignore dependences. A different DFA is created
1093 /// for each cycle that is required. When adding a new instruction, we attempt
1094 /// to add it to each existing DFA, until a legal space is found. If the
1095 /// instruction cannot be reserved in an existing DFA, we create a new one.
calculateResMII()1096 unsigned SwingSchedulerDAG::calculateResMII() {
1097
1098 LLVM_DEBUG(dbgs() << "calculateResMII:\n");
1099 SmallVector<ResourceManager*, 8> Resources;
1100 MachineBasicBlock *MBB = Loop.getHeader();
1101 Resources.push_back(new ResourceManager(&MF.getSubtarget()));
1102
1103 // Sort the instructions by the number of available choices for scheduling,
1104 // least to most. Use the number of critical resources as the tie breaker.
1105 FuncUnitSorter FUS = FuncUnitSorter(MF.getSubtarget());
1106 for (MachineBasicBlock::iterator I = MBB->getFirstNonPHI(),
1107 E = MBB->getFirstTerminator();
1108 I != E; ++I)
1109 FUS.calcCriticalResources(*I);
1110 PriorityQueue<MachineInstr *, std::vector<MachineInstr *>, FuncUnitSorter>
1111 FuncUnitOrder(FUS);
1112
1113 for (MachineBasicBlock::iterator I = MBB->getFirstNonPHI(),
1114 E = MBB->getFirstTerminator();
1115 I != E; ++I)
1116 FuncUnitOrder.push(&*I);
1117
1118 while (!FuncUnitOrder.empty()) {
1119 MachineInstr *MI = FuncUnitOrder.top();
1120 FuncUnitOrder.pop();
1121 if (TII->isZeroCost(MI->getOpcode()))
1122 continue;
1123 // Attempt to reserve the instruction in an existing DFA. At least one
1124 // DFA is needed for each cycle.
1125 unsigned NumCycles = getSUnit(MI)->Latency;
1126 unsigned ReservedCycles = 0;
1127 SmallVectorImpl<ResourceManager *>::iterator RI = Resources.begin();
1128 SmallVectorImpl<ResourceManager *>::iterator RE = Resources.end();
1129 LLVM_DEBUG({
1130 dbgs() << "Trying to reserve resource for " << NumCycles
1131 << " cycles for \n";
1132 MI->dump();
1133 });
1134 for (unsigned C = 0; C < NumCycles; ++C)
1135 while (RI != RE) {
1136 if ((*RI)->canReserveResources(*MI)) {
1137 (*RI)->reserveResources(*MI);
1138 ++ReservedCycles;
1139 break;
1140 }
1141 RI++;
1142 }
1143 LLVM_DEBUG(dbgs() << "ReservedCycles:" << ReservedCycles
1144 << ", NumCycles:" << NumCycles << "\n");
1145 // Add new DFAs, if needed, to reserve resources.
1146 for (unsigned C = ReservedCycles; C < NumCycles; ++C) {
1147 LLVM_DEBUG(if (SwpDebugResource) dbgs()
1148 << "NewResource created to reserve resources"
1149 << "\n");
1150 ResourceManager *NewResource = new ResourceManager(&MF.getSubtarget());
1151 assert(NewResource->canReserveResources(*MI) && "Reserve error.");
1152 NewResource->reserveResources(*MI);
1153 Resources.push_back(NewResource);
1154 }
1155 }
1156 int Resmii = Resources.size();
1157 LLVM_DEBUG(dbgs() << "Return Res MII:" << Resmii << "\n");
1158 // Delete the memory for each of the DFAs that were created earlier.
1159 for (ResourceManager *RI : Resources) {
1160 ResourceManager *D = RI;
1161 delete D;
1162 }
1163 Resources.clear();
1164 return Resmii;
1165 }
1166
1167 /// Calculate the recurrence-constrainted minimum initiation interval.
1168 /// Iterate over each circuit. Compute the delay(c) and distance(c)
1169 /// for each circuit. The II needs to satisfy the inequality
1170 /// delay(c) - II*distance(c) <= 0. For each circuit, choose the smallest
1171 /// II that satisfies the inequality, and the RecMII is the maximum
1172 /// of those values.
calculateRecMII(NodeSetType & NodeSets)1173 unsigned SwingSchedulerDAG::calculateRecMII(NodeSetType &NodeSets) {
1174 unsigned RecMII = 0;
1175
1176 for (NodeSet &Nodes : NodeSets) {
1177 if (Nodes.empty())
1178 continue;
1179
1180 unsigned Delay = Nodes.getLatency();
1181 unsigned Distance = 1;
1182
1183 // ii = ceil(delay / distance)
1184 unsigned CurMII = (Delay + Distance - 1) / Distance;
1185 Nodes.setRecMII(CurMII);
1186 if (CurMII > RecMII)
1187 RecMII = CurMII;
1188 }
1189
1190 return RecMII;
1191 }
1192
1193 /// Swap all the anti dependences in the DAG. That means it is no longer a DAG,
1194 /// but we do this to find the circuits, and then change them back.
swapAntiDependences(std::vector<SUnit> & SUnits)1195 static void swapAntiDependences(std::vector<SUnit> &SUnits) {
1196 SmallVector<std::pair<SUnit *, SDep>, 8> DepsAdded;
1197 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
1198 SUnit *SU = &SUnits[i];
1199 for (SUnit::pred_iterator IP = SU->Preds.begin(), EP = SU->Preds.end();
1200 IP != EP; ++IP) {
1201 if (IP->getKind() != SDep::Anti)
1202 continue;
1203 DepsAdded.push_back(std::make_pair(SU, *IP));
1204 }
1205 }
1206 for (SmallVector<std::pair<SUnit *, SDep>, 8>::iterator I = DepsAdded.begin(),
1207 E = DepsAdded.end();
1208 I != E; ++I) {
1209 // Remove this anti dependency and add one in the reverse direction.
1210 SUnit *SU = I->first;
1211 SDep &D = I->second;
1212 SUnit *TargetSU = D.getSUnit();
1213 unsigned Reg = D.getReg();
1214 unsigned Lat = D.getLatency();
1215 SU->removePred(D);
1216 SDep Dep(SU, SDep::Anti, Reg);
1217 Dep.setLatency(Lat);
1218 TargetSU->addPred(Dep);
1219 }
1220 }
1221
1222 /// Create the adjacency structure of the nodes in the graph.
createAdjacencyStructure(SwingSchedulerDAG * DAG)1223 void SwingSchedulerDAG::Circuits::createAdjacencyStructure(
1224 SwingSchedulerDAG *DAG) {
1225 BitVector Added(SUnits.size());
1226 DenseMap<int, int> OutputDeps;
1227 for (int i = 0, e = SUnits.size(); i != e; ++i) {
1228 Added.reset();
1229 // Add any successor to the adjacency matrix and exclude duplicates.
1230 for (auto &SI : SUnits[i].Succs) {
1231 // Only create a back-edge on the first and last nodes of a dependence
1232 // chain. This records any chains and adds them later.
1233 if (SI.getKind() == SDep::Output) {
1234 int N = SI.getSUnit()->NodeNum;
1235 int BackEdge = i;
1236 auto Dep = OutputDeps.find(BackEdge);
1237 if (Dep != OutputDeps.end()) {
1238 BackEdge = Dep->second;
1239 OutputDeps.erase(Dep);
1240 }
1241 OutputDeps[N] = BackEdge;
1242 }
1243 // Do not process a boundary node, an artificial node.
1244 // A back-edge is processed only if it goes to a Phi.
1245 if (SI.getSUnit()->isBoundaryNode() || SI.isArtificial() ||
1246 (SI.getKind() == SDep::Anti && !SI.getSUnit()->getInstr()->isPHI()))
1247 continue;
1248 int N = SI.getSUnit()->NodeNum;
1249 if (!Added.test(N)) {
1250 AdjK[i].push_back(N);
1251 Added.set(N);
1252 }
1253 }
1254 // A chain edge between a store and a load is treated as a back-edge in the
1255 // adjacency matrix.
1256 for (auto &PI : SUnits[i].Preds) {
1257 if (!SUnits[i].getInstr()->mayStore() ||
1258 !DAG->isLoopCarriedDep(&SUnits[i], PI, false))
1259 continue;
1260 if (PI.getKind() == SDep::Order && PI.getSUnit()->getInstr()->mayLoad()) {
1261 int N = PI.getSUnit()->NodeNum;
1262 if (!Added.test(N)) {
1263 AdjK[i].push_back(N);
1264 Added.set(N);
1265 }
1266 }
1267 }
1268 }
1269 // Add back-edges in the adjacency matrix for the output dependences.
1270 for (auto &OD : OutputDeps)
1271 if (!Added.test(OD.second)) {
1272 AdjK[OD.first].push_back(OD.second);
1273 Added.set(OD.second);
1274 }
1275 }
1276
1277 /// Identify an elementary circuit in the dependence graph starting at the
1278 /// specified node.
circuit(int V,int S,NodeSetType & NodeSets,bool HasBackedge)1279 bool SwingSchedulerDAG::Circuits::circuit(int V, int S, NodeSetType &NodeSets,
1280 bool HasBackedge) {
1281 SUnit *SV = &SUnits[V];
1282 bool F = false;
1283 Stack.insert(SV);
1284 Blocked.set(V);
1285
1286 for (auto W : AdjK[V]) {
1287 if (NumPaths > MaxPaths)
1288 break;
1289 if (W < S)
1290 continue;
1291 if (W == S) {
1292 if (!HasBackedge)
1293 NodeSets.push_back(NodeSet(Stack.begin(), Stack.end()));
1294 F = true;
1295 ++NumPaths;
1296 break;
1297 } else if (!Blocked.test(W)) {
1298 if (circuit(W, S, NodeSets,
1299 Node2Idx->at(W) < Node2Idx->at(V) ? true : HasBackedge))
1300 F = true;
1301 }
1302 }
1303
1304 if (F)
1305 unblock(V);
1306 else {
1307 for (auto W : AdjK[V]) {
1308 if (W < S)
1309 continue;
1310 if (B[W].count(SV) == 0)
1311 B[W].insert(SV);
1312 }
1313 }
1314 Stack.pop_back();
1315 return F;
1316 }
1317
1318 /// Unblock a node in the circuit finding algorithm.
unblock(int U)1319 void SwingSchedulerDAG::Circuits::unblock(int U) {
1320 Blocked.reset(U);
1321 SmallPtrSet<SUnit *, 4> &BU = B[U];
1322 while (!BU.empty()) {
1323 SmallPtrSet<SUnit *, 4>::iterator SI = BU.begin();
1324 assert(SI != BU.end() && "Invalid B set.");
1325 SUnit *W = *SI;
1326 BU.erase(W);
1327 if (Blocked.test(W->NodeNum))
1328 unblock(W->NodeNum);
1329 }
1330 }
1331
1332 /// Identify all the elementary circuits in the dependence graph using
1333 /// Johnson's circuit algorithm.
findCircuits(NodeSetType & NodeSets)1334 void SwingSchedulerDAG::findCircuits(NodeSetType &NodeSets) {
1335 // Swap all the anti dependences in the DAG. That means it is no longer a DAG,
1336 // but we do this to find the circuits, and then change them back.
1337 swapAntiDependences(SUnits);
1338
1339 Circuits Cir(SUnits, Topo);
1340 // Create the adjacency structure.
1341 Cir.createAdjacencyStructure(this);
1342 for (int i = 0, e = SUnits.size(); i != e; ++i) {
1343 Cir.reset();
1344 Cir.circuit(i, i, NodeSets);
1345 }
1346
1347 // Change the dependences back so that we've created a DAG again.
1348 swapAntiDependences(SUnits);
1349 }
1350
1351 // Create artificial dependencies between the source of COPY/REG_SEQUENCE that
1352 // is loop-carried to the USE in next iteration. This will help pipeliner avoid
1353 // additional copies that are needed across iterations. An artificial dependence
1354 // edge is added from USE to SOURCE of COPY/REG_SEQUENCE.
1355
1356 // PHI-------Anti-Dep-----> COPY/REG_SEQUENCE (loop-carried)
1357 // SRCOfCopY------True-Dep---> COPY/REG_SEQUENCE
1358 // PHI-------True-Dep------> USEOfPhi
1359
1360 // The mutation creates
1361 // USEOfPHI -------Artificial-Dep---> SRCOfCopy
1362
1363 // This overall will ensure, the USEOfPHI is scheduled before SRCOfCopy
1364 // (since USE is a predecessor), implies, the COPY/ REG_SEQUENCE is scheduled
1365 // late to avoid additional copies across iterations. The possible scheduling
1366 // order would be
1367 // USEOfPHI --- SRCOfCopy--- COPY/REG_SEQUENCE.
1368
apply(ScheduleDAGInstrs * DAG)1369 void SwingSchedulerDAG::CopyToPhiMutation::apply(ScheduleDAGInstrs *DAG) {
1370 for (SUnit &SU : DAG->SUnits) {
1371 // Find the COPY/REG_SEQUENCE instruction.
1372 if (!SU.getInstr()->isCopy() && !SU.getInstr()->isRegSequence())
1373 continue;
1374
1375 // Record the loop carried PHIs.
1376 SmallVector<SUnit *, 4> PHISUs;
1377 // Record the SrcSUs that feed the COPY/REG_SEQUENCE instructions.
1378 SmallVector<SUnit *, 4> SrcSUs;
1379
1380 for (auto &Dep : SU.Preds) {
1381 SUnit *TmpSU = Dep.getSUnit();
1382 MachineInstr *TmpMI = TmpSU->getInstr();
1383 SDep::Kind DepKind = Dep.getKind();
1384 // Save the loop carried PHI.
1385 if (DepKind == SDep::Anti && TmpMI->isPHI())
1386 PHISUs.push_back(TmpSU);
1387 // Save the source of COPY/REG_SEQUENCE.
1388 // If the source has no pre-decessors, we will end up creating cycles.
1389 else if (DepKind == SDep::Data && !TmpMI->isPHI() && TmpSU->NumPreds > 0)
1390 SrcSUs.push_back(TmpSU);
1391 }
1392
1393 if (PHISUs.size() == 0 || SrcSUs.size() == 0)
1394 continue;
1395
1396 // Find the USEs of PHI. If the use is a PHI or REG_SEQUENCE, push back this
1397 // SUnit to the container.
1398 SmallVector<SUnit *, 8> UseSUs;
1399 // Do not use iterator based loop here as we are updating the container.
1400 for (size_t Index = 0; Index < PHISUs.size(); ++Index) {
1401 for (auto &Dep : PHISUs[Index]->Succs) {
1402 if (Dep.getKind() != SDep::Data)
1403 continue;
1404
1405 SUnit *TmpSU = Dep.getSUnit();
1406 MachineInstr *TmpMI = TmpSU->getInstr();
1407 if (TmpMI->isPHI() || TmpMI->isRegSequence()) {
1408 PHISUs.push_back(TmpSU);
1409 continue;
1410 }
1411 UseSUs.push_back(TmpSU);
1412 }
1413 }
1414
1415 if (UseSUs.size() == 0)
1416 continue;
1417
1418 SwingSchedulerDAG *SDAG = cast<SwingSchedulerDAG>(DAG);
1419 // Add the artificial dependencies if it does not form a cycle.
1420 for (auto I : UseSUs) {
1421 for (auto Src : SrcSUs) {
1422 if (!SDAG->Topo.IsReachable(I, Src) && Src != I) {
1423 Src->addPred(SDep(I, SDep::Artificial));
1424 SDAG->Topo.AddPred(Src, I);
1425 }
1426 }
1427 }
1428 }
1429 }
1430
1431 /// Return true for DAG nodes that we ignore when computing the cost functions.
1432 /// We ignore the back-edge recurrence in order to avoid unbounded recursion
1433 /// in the calculation of the ASAP, ALAP, etc functions.
ignoreDependence(const SDep & D,bool isPred)1434 static bool ignoreDependence(const SDep &D, bool isPred) {
1435 if (D.isArtificial())
1436 return true;
1437 return D.getKind() == SDep::Anti && isPred;
1438 }
1439
1440 /// Compute several functions need to order the nodes for scheduling.
1441 /// ASAP - Earliest time to schedule a node.
1442 /// ALAP - Latest time to schedule a node.
1443 /// MOV - Mobility function, difference between ALAP and ASAP.
1444 /// D - Depth of each node.
1445 /// H - Height of each node.
computeNodeFunctions(NodeSetType & NodeSets)1446 void SwingSchedulerDAG::computeNodeFunctions(NodeSetType &NodeSets) {
1447 ScheduleInfo.resize(SUnits.size());
1448
1449 LLVM_DEBUG({
1450 for (ScheduleDAGTopologicalSort::const_iterator I = Topo.begin(),
1451 E = Topo.end();
1452 I != E; ++I) {
1453 const SUnit &SU = SUnits[*I];
1454 dumpNode(SU);
1455 }
1456 });
1457
1458 int maxASAP = 0;
1459 // Compute ASAP and ZeroLatencyDepth.
1460 for (ScheduleDAGTopologicalSort::const_iterator I = Topo.begin(),
1461 E = Topo.end();
1462 I != E; ++I) {
1463 int asap = 0;
1464 int zeroLatencyDepth = 0;
1465 SUnit *SU = &SUnits[*I];
1466 for (SUnit::const_pred_iterator IP = SU->Preds.begin(),
1467 EP = SU->Preds.end();
1468 IP != EP; ++IP) {
1469 SUnit *pred = IP->getSUnit();
1470 if (IP->getLatency() == 0)
1471 zeroLatencyDepth =
1472 std::max(zeroLatencyDepth, getZeroLatencyDepth(pred) + 1);
1473 if (ignoreDependence(*IP, true))
1474 continue;
1475 asap = std::max(asap, (int)(getASAP(pred) + IP->getLatency() -
1476 getDistance(pred, SU, *IP) * MII));
1477 }
1478 maxASAP = std::max(maxASAP, asap);
1479 ScheduleInfo[*I].ASAP = asap;
1480 ScheduleInfo[*I].ZeroLatencyDepth = zeroLatencyDepth;
1481 }
1482
1483 // Compute ALAP, ZeroLatencyHeight, and MOV.
1484 for (ScheduleDAGTopologicalSort::const_reverse_iterator I = Topo.rbegin(),
1485 E = Topo.rend();
1486 I != E; ++I) {
1487 int alap = maxASAP;
1488 int zeroLatencyHeight = 0;
1489 SUnit *SU = &SUnits[*I];
1490 for (SUnit::const_succ_iterator IS = SU->Succs.begin(),
1491 ES = SU->Succs.end();
1492 IS != ES; ++IS) {
1493 SUnit *succ = IS->getSUnit();
1494 if (IS->getLatency() == 0)
1495 zeroLatencyHeight =
1496 std::max(zeroLatencyHeight, getZeroLatencyHeight(succ) + 1);
1497 if (ignoreDependence(*IS, true))
1498 continue;
1499 alap = std::min(alap, (int)(getALAP(succ) - IS->getLatency() +
1500 getDistance(SU, succ, *IS) * MII));
1501 }
1502
1503 ScheduleInfo[*I].ALAP = alap;
1504 ScheduleInfo[*I].ZeroLatencyHeight = zeroLatencyHeight;
1505 }
1506
1507 // After computing the node functions, compute the summary for each node set.
1508 for (NodeSet &I : NodeSets)
1509 I.computeNodeSetInfo(this);
1510
1511 LLVM_DEBUG({
1512 for (unsigned i = 0; i < SUnits.size(); i++) {
1513 dbgs() << "\tNode " << i << ":\n";
1514 dbgs() << "\t ASAP = " << getASAP(&SUnits[i]) << "\n";
1515 dbgs() << "\t ALAP = " << getALAP(&SUnits[i]) << "\n";
1516 dbgs() << "\t MOV = " << getMOV(&SUnits[i]) << "\n";
1517 dbgs() << "\t D = " << getDepth(&SUnits[i]) << "\n";
1518 dbgs() << "\t H = " << getHeight(&SUnits[i]) << "\n";
1519 dbgs() << "\t ZLD = " << getZeroLatencyDepth(&SUnits[i]) << "\n";
1520 dbgs() << "\t ZLH = " << getZeroLatencyHeight(&SUnits[i]) << "\n";
1521 }
1522 });
1523 }
1524
1525 /// Compute the Pred_L(O) set, as defined in the paper. The set is defined
1526 /// as the predecessors of the elements of NodeOrder that are not also in
1527 /// NodeOrder.
pred_L(SetVector<SUnit * > & NodeOrder,SmallSetVector<SUnit *,8> & Preds,const NodeSet * S=nullptr)1528 static bool pred_L(SetVector<SUnit *> &NodeOrder,
1529 SmallSetVector<SUnit *, 8> &Preds,
1530 const NodeSet *S = nullptr) {
1531 Preds.clear();
1532 for (SetVector<SUnit *>::iterator I = NodeOrder.begin(), E = NodeOrder.end();
1533 I != E; ++I) {
1534 for (SUnit::pred_iterator PI = (*I)->Preds.begin(), PE = (*I)->Preds.end();
1535 PI != PE; ++PI) {
1536 if (S && S->count(PI->getSUnit()) == 0)
1537 continue;
1538 if (ignoreDependence(*PI, true))
1539 continue;
1540 if (NodeOrder.count(PI->getSUnit()) == 0)
1541 Preds.insert(PI->getSUnit());
1542 }
1543 // Back-edges are predecessors with an anti-dependence.
1544 for (SUnit::const_succ_iterator IS = (*I)->Succs.begin(),
1545 ES = (*I)->Succs.end();
1546 IS != ES; ++IS) {
1547 if (IS->getKind() != SDep::Anti)
1548 continue;
1549 if (S && S->count(IS->getSUnit()) == 0)
1550 continue;
1551 if (NodeOrder.count(IS->getSUnit()) == 0)
1552 Preds.insert(IS->getSUnit());
1553 }
1554 }
1555 return !Preds.empty();
1556 }
1557
1558 /// Compute the Succ_L(O) set, as defined in the paper. The set is defined
1559 /// as the successors of the elements of NodeOrder that are not also in
1560 /// NodeOrder.
succ_L(SetVector<SUnit * > & NodeOrder,SmallSetVector<SUnit *,8> & Succs,const NodeSet * S=nullptr)1561 static bool succ_L(SetVector<SUnit *> &NodeOrder,
1562 SmallSetVector<SUnit *, 8> &Succs,
1563 const NodeSet *S = nullptr) {
1564 Succs.clear();
1565 for (SetVector<SUnit *>::iterator I = NodeOrder.begin(), E = NodeOrder.end();
1566 I != E; ++I) {
1567 for (SUnit::succ_iterator SI = (*I)->Succs.begin(), SE = (*I)->Succs.end();
1568 SI != SE; ++SI) {
1569 if (S && S->count(SI->getSUnit()) == 0)
1570 continue;
1571 if (ignoreDependence(*SI, false))
1572 continue;
1573 if (NodeOrder.count(SI->getSUnit()) == 0)
1574 Succs.insert(SI->getSUnit());
1575 }
1576 for (SUnit::const_pred_iterator PI = (*I)->Preds.begin(),
1577 PE = (*I)->Preds.end();
1578 PI != PE; ++PI) {
1579 if (PI->getKind() != SDep::Anti)
1580 continue;
1581 if (S && S->count(PI->getSUnit()) == 0)
1582 continue;
1583 if (NodeOrder.count(PI->getSUnit()) == 0)
1584 Succs.insert(PI->getSUnit());
1585 }
1586 }
1587 return !Succs.empty();
1588 }
1589
1590 /// Return true if there is a path from the specified node to any of the nodes
1591 /// in DestNodes. Keep track and return the nodes in any path.
computePath(SUnit * Cur,SetVector<SUnit * > & Path,SetVector<SUnit * > & DestNodes,SetVector<SUnit * > & Exclude,SmallPtrSet<SUnit *,8> & Visited)1592 static bool computePath(SUnit *Cur, SetVector<SUnit *> &Path,
1593 SetVector<SUnit *> &DestNodes,
1594 SetVector<SUnit *> &Exclude,
1595 SmallPtrSet<SUnit *, 8> &Visited) {
1596 if (Cur->isBoundaryNode())
1597 return false;
1598 if (Exclude.contains(Cur))
1599 return false;
1600 if (DestNodes.contains(Cur))
1601 return true;
1602 if (!Visited.insert(Cur).second)
1603 return Path.contains(Cur);
1604 bool FoundPath = false;
1605 for (auto &SI : Cur->Succs)
1606 FoundPath |= computePath(SI.getSUnit(), Path, DestNodes, Exclude, Visited);
1607 for (auto &PI : Cur->Preds)
1608 if (PI.getKind() == SDep::Anti)
1609 FoundPath |=
1610 computePath(PI.getSUnit(), Path, DestNodes, Exclude, Visited);
1611 if (FoundPath)
1612 Path.insert(Cur);
1613 return FoundPath;
1614 }
1615
1616 /// Return true if Set1 is a subset of Set2.
isSubset(S1Ty & Set1,S2Ty & Set2)1617 template <class S1Ty, class S2Ty> static bool isSubset(S1Ty &Set1, S2Ty &Set2) {
1618 for (typename S1Ty::iterator I = Set1.begin(), E = Set1.end(); I != E; ++I)
1619 if (Set2.count(*I) == 0)
1620 return false;
1621 return true;
1622 }
1623
1624 /// Compute the live-out registers for the instructions in a node-set.
1625 /// The live-out registers are those that are defined in the node-set,
1626 /// but not used. Except for use operands of Phis.
computeLiveOuts(MachineFunction & MF,RegPressureTracker & RPTracker,NodeSet & NS)1627 static void computeLiveOuts(MachineFunction &MF, RegPressureTracker &RPTracker,
1628 NodeSet &NS) {
1629 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
1630 MachineRegisterInfo &MRI = MF.getRegInfo();
1631 SmallVector<RegisterMaskPair, 8> LiveOutRegs;
1632 SmallSet<unsigned, 4> Uses;
1633 for (SUnit *SU : NS) {
1634 const MachineInstr *MI = SU->getInstr();
1635 if (MI->isPHI())
1636 continue;
1637 for (const MachineOperand &MO : MI->operands())
1638 if (MO.isReg() && MO.isUse()) {
1639 Register Reg = MO.getReg();
1640 if (Register::isVirtualRegister(Reg))
1641 Uses.insert(Reg);
1642 else if (MRI.isAllocatable(Reg))
1643 for (MCRegUnitIterator Units(Reg.asMCReg(), TRI); Units.isValid();
1644 ++Units)
1645 Uses.insert(*Units);
1646 }
1647 }
1648 for (SUnit *SU : NS)
1649 for (const MachineOperand &MO : SU->getInstr()->operands())
1650 if (MO.isReg() && MO.isDef() && !MO.isDead()) {
1651 Register Reg = MO.getReg();
1652 if (Register::isVirtualRegister(Reg)) {
1653 if (!Uses.count(Reg))
1654 LiveOutRegs.push_back(RegisterMaskPair(Reg,
1655 LaneBitmask::getNone()));
1656 } else if (MRI.isAllocatable(Reg)) {
1657 for (MCRegUnitIterator Units(Reg.asMCReg(), TRI); Units.isValid();
1658 ++Units)
1659 if (!Uses.count(*Units))
1660 LiveOutRegs.push_back(RegisterMaskPair(*Units,
1661 LaneBitmask::getNone()));
1662 }
1663 }
1664 RPTracker.addLiveRegs(LiveOutRegs);
1665 }
1666
1667 /// A heuristic to filter nodes in recurrent node-sets if the register
1668 /// pressure of a set is too high.
registerPressureFilter(NodeSetType & NodeSets)1669 void SwingSchedulerDAG::registerPressureFilter(NodeSetType &NodeSets) {
1670 for (auto &NS : NodeSets) {
1671 // Skip small node-sets since they won't cause register pressure problems.
1672 if (NS.size() <= 2)
1673 continue;
1674 IntervalPressure RecRegPressure;
1675 RegPressureTracker RecRPTracker(RecRegPressure);
1676 RecRPTracker.init(&MF, &RegClassInfo, &LIS, BB, BB->end(), false, true);
1677 computeLiveOuts(MF, RecRPTracker, NS);
1678 RecRPTracker.closeBottom();
1679
1680 std::vector<SUnit *> SUnits(NS.begin(), NS.end());
1681 llvm::sort(SUnits, [](const SUnit *A, const SUnit *B) {
1682 return A->NodeNum > B->NodeNum;
1683 });
1684
1685 for (auto &SU : SUnits) {
1686 // Since we're computing the register pressure for a subset of the
1687 // instructions in a block, we need to set the tracker for each
1688 // instruction in the node-set. The tracker is set to the instruction
1689 // just after the one we're interested in.
1690 MachineBasicBlock::const_iterator CurInstI = SU->getInstr();
1691 RecRPTracker.setPos(std::next(CurInstI));
1692
1693 RegPressureDelta RPDelta;
1694 ArrayRef<PressureChange> CriticalPSets;
1695 RecRPTracker.getMaxUpwardPressureDelta(SU->getInstr(), nullptr, RPDelta,
1696 CriticalPSets,
1697 RecRegPressure.MaxSetPressure);
1698 if (RPDelta.Excess.isValid()) {
1699 LLVM_DEBUG(
1700 dbgs() << "Excess register pressure: SU(" << SU->NodeNum << ") "
1701 << TRI->getRegPressureSetName(RPDelta.Excess.getPSet())
1702 << ":" << RPDelta.Excess.getUnitInc());
1703 NS.setExceedPressure(SU);
1704 break;
1705 }
1706 RecRPTracker.recede();
1707 }
1708 }
1709 }
1710
1711 /// A heuristic to colocate node sets that have the same set of
1712 /// successors.
colocateNodeSets(NodeSetType & NodeSets)1713 void SwingSchedulerDAG::colocateNodeSets(NodeSetType &NodeSets) {
1714 unsigned Colocate = 0;
1715 for (int i = 0, e = NodeSets.size(); i < e; ++i) {
1716 NodeSet &N1 = NodeSets[i];
1717 SmallSetVector<SUnit *, 8> S1;
1718 if (N1.empty() || !succ_L(N1, S1))
1719 continue;
1720 for (int j = i + 1; j < e; ++j) {
1721 NodeSet &N2 = NodeSets[j];
1722 if (N1.compareRecMII(N2) != 0)
1723 continue;
1724 SmallSetVector<SUnit *, 8> S2;
1725 if (N2.empty() || !succ_L(N2, S2))
1726 continue;
1727 if (isSubset(S1, S2) && S1.size() == S2.size()) {
1728 N1.setColocate(++Colocate);
1729 N2.setColocate(Colocate);
1730 break;
1731 }
1732 }
1733 }
1734 }
1735
1736 /// Check if the existing node-sets are profitable. If not, then ignore the
1737 /// recurrent node-sets, and attempt to schedule all nodes together. This is
1738 /// a heuristic. If the MII is large and all the recurrent node-sets are small,
1739 /// then it's best to try to schedule all instructions together instead of
1740 /// starting with the recurrent node-sets.
checkNodeSets(NodeSetType & NodeSets)1741 void SwingSchedulerDAG::checkNodeSets(NodeSetType &NodeSets) {
1742 // Look for loops with a large MII.
1743 if (MII < 17)
1744 return;
1745 // Check if the node-set contains only a simple add recurrence.
1746 for (auto &NS : NodeSets) {
1747 if (NS.getRecMII() > 2)
1748 return;
1749 if (NS.getMaxDepth() > MII)
1750 return;
1751 }
1752 NodeSets.clear();
1753 LLVM_DEBUG(dbgs() << "Clear recurrence node-sets\n");
1754 }
1755
1756 /// Add the nodes that do not belong to a recurrence set into groups
1757 /// based upon connected componenets.
groupRemainingNodes(NodeSetType & NodeSets)1758 void SwingSchedulerDAG::groupRemainingNodes(NodeSetType &NodeSets) {
1759 SetVector<SUnit *> NodesAdded;
1760 SmallPtrSet<SUnit *, 8> Visited;
1761 // Add the nodes that are on a path between the previous node sets and
1762 // the current node set.
1763 for (NodeSet &I : NodeSets) {
1764 SmallSetVector<SUnit *, 8> N;
1765 // Add the nodes from the current node set to the previous node set.
1766 if (succ_L(I, N)) {
1767 SetVector<SUnit *> Path;
1768 for (SUnit *NI : N) {
1769 Visited.clear();
1770 computePath(NI, Path, NodesAdded, I, Visited);
1771 }
1772 if (!Path.empty())
1773 I.insert(Path.begin(), Path.end());
1774 }
1775 // Add the nodes from the previous node set to the current node set.
1776 N.clear();
1777 if (succ_L(NodesAdded, N)) {
1778 SetVector<SUnit *> Path;
1779 for (SUnit *NI : N) {
1780 Visited.clear();
1781 computePath(NI, Path, I, NodesAdded, Visited);
1782 }
1783 if (!Path.empty())
1784 I.insert(Path.begin(), Path.end());
1785 }
1786 NodesAdded.insert(I.begin(), I.end());
1787 }
1788
1789 // Create a new node set with the connected nodes of any successor of a node
1790 // in a recurrent set.
1791 NodeSet NewSet;
1792 SmallSetVector<SUnit *, 8> N;
1793 if (succ_L(NodesAdded, N))
1794 for (SUnit *I : N)
1795 addConnectedNodes(I, NewSet, NodesAdded);
1796 if (!NewSet.empty())
1797 NodeSets.push_back(NewSet);
1798
1799 // Create a new node set with the connected nodes of any predecessor of a node
1800 // in a recurrent set.
1801 NewSet.clear();
1802 if (pred_L(NodesAdded, N))
1803 for (SUnit *I : N)
1804 addConnectedNodes(I, NewSet, NodesAdded);
1805 if (!NewSet.empty())
1806 NodeSets.push_back(NewSet);
1807
1808 // Create new nodes sets with the connected nodes any remaining node that
1809 // has no predecessor.
1810 for (unsigned i = 0; i < SUnits.size(); ++i) {
1811 SUnit *SU = &SUnits[i];
1812 if (NodesAdded.count(SU) == 0) {
1813 NewSet.clear();
1814 addConnectedNodes(SU, NewSet, NodesAdded);
1815 if (!NewSet.empty())
1816 NodeSets.push_back(NewSet);
1817 }
1818 }
1819 }
1820
1821 /// Add the node to the set, and add all of its connected nodes to the set.
addConnectedNodes(SUnit * SU,NodeSet & NewSet,SetVector<SUnit * > & NodesAdded)1822 void SwingSchedulerDAG::addConnectedNodes(SUnit *SU, NodeSet &NewSet,
1823 SetVector<SUnit *> &NodesAdded) {
1824 NewSet.insert(SU);
1825 NodesAdded.insert(SU);
1826 for (auto &SI : SU->Succs) {
1827 SUnit *Successor = SI.getSUnit();
1828 if (!SI.isArtificial() && NodesAdded.count(Successor) == 0)
1829 addConnectedNodes(Successor, NewSet, NodesAdded);
1830 }
1831 for (auto &PI : SU->Preds) {
1832 SUnit *Predecessor = PI.getSUnit();
1833 if (!PI.isArtificial() && NodesAdded.count(Predecessor) == 0)
1834 addConnectedNodes(Predecessor, NewSet, NodesAdded);
1835 }
1836 }
1837
1838 /// Return true if Set1 contains elements in Set2. The elements in common
1839 /// are returned in a different container.
isIntersect(SmallSetVector<SUnit *,8> & Set1,const NodeSet & Set2,SmallSetVector<SUnit *,8> & Result)1840 static bool isIntersect(SmallSetVector<SUnit *, 8> &Set1, const NodeSet &Set2,
1841 SmallSetVector<SUnit *, 8> &Result) {
1842 Result.clear();
1843 for (unsigned i = 0, e = Set1.size(); i != e; ++i) {
1844 SUnit *SU = Set1[i];
1845 if (Set2.count(SU) != 0)
1846 Result.insert(SU);
1847 }
1848 return !Result.empty();
1849 }
1850
1851 /// Merge the recurrence node sets that have the same initial node.
fuseRecs(NodeSetType & NodeSets)1852 void SwingSchedulerDAG::fuseRecs(NodeSetType &NodeSets) {
1853 for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E;
1854 ++I) {
1855 NodeSet &NI = *I;
1856 for (NodeSetType::iterator J = I + 1; J != E;) {
1857 NodeSet &NJ = *J;
1858 if (NI.getNode(0)->NodeNum == NJ.getNode(0)->NodeNum) {
1859 if (NJ.compareRecMII(NI) > 0)
1860 NI.setRecMII(NJ.getRecMII());
1861 for (NodeSet::iterator NII = J->begin(), ENI = J->end(); NII != ENI;
1862 ++NII)
1863 I->insert(*NII);
1864 NodeSets.erase(J);
1865 E = NodeSets.end();
1866 } else {
1867 ++J;
1868 }
1869 }
1870 }
1871 }
1872
1873 /// Remove nodes that have been scheduled in previous NodeSets.
removeDuplicateNodes(NodeSetType & NodeSets)1874 void SwingSchedulerDAG::removeDuplicateNodes(NodeSetType &NodeSets) {
1875 for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E;
1876 ++I)
1877 for (NodeSetType::iterator J = I + 1; J != E;) {
1878 J->remove_if([&](SUnit *SUJ) { return I->count(SUJ); });
1879
1880 if (J->empty()) {
1881 NodeSets.erase(J);
1882 E = NodeSets.end();
1883 } else {
1884 ++J;
1885 }
1886 }
1887 }
1888
1889 /// Compute an ordered list of the dependence graph nodes, which
1890 /// indicates the order that the nodes will be scheduled. This is a
1891 /// two-level algorithm. First, a partial order is created, which
1892 /// consists of a list of sets ordered from highest to lowest priority.
computeNodeOrder(NodeSetType & NodeSets)1893 void SwingSchedulerDAG::computeNodeOrder(NodeSetType &NodeSets) {
1894 SmallSetVector<SUnit *, 8> R;
1895 NodeOrder.clear();
1896
1897 for (auto &Nodes : NodeSets) {
1898 LLVM_DEBUG(dbgs() << "NodeSet size " << Nodes.size() << "\n");
1899 OrderKind Order;
1900 SmallSetVector<SUnit *, 8> N;
1901 if (pred_L(NodeOrder, N) && isSubset(N, Nodes)) {
1902 R.insert(N.begin(), N.end());
1903 Order = BottomUp;
1904 LLVM_DEBUG(dbgs() << " Bottom up (preds) ");
1905 } else if (succ_L(NodeOrder, N) && isSubset(N, Nodes)) {
1906 R.insert(N.begin(), N.end());
1907 Order = TopDown;
1908 LLVM_DEBUG(dbgs() << " Top down (succs) ");
1909 } else if (isIntersect(N, Nodes, R)) {
1910 // If some of the successors are in the existing node-set, then use the
1911 // top-down ordering.
1912 Order = TopDown;
1913 LLVM_DEBUG(dbgs() << " Top down (intersect) ");
1914 } else if (NodeSets.size() == 1) {
1915 for (auto &N : Nodes)
1916 if (N->Succs.size() == 0)
1917 R.insert(N);
1918 Order = BottomUp;
1919 LLVM_DEBUG(dbgs() << " Bottom up (all) ");
1920 } else {
1921 // Find the node with the highest ASAP.
1922 SUnit *maxASAP = nullptr;
1923 for (SUnit *SU : Nodes) {
1924 if (maxASAP == nullptr || getASAP(SU) > getASAP(maxASAP) ||
1925 (getASAP(SU) == getASAP(maxASAP) && SU->NodeNum > maxASAP->NodeNum))
1926 maxASAP = SU;
1927 }
1928 R.insert(maxASAP);
1929 Order = BottomUp;
1930 LLVM_DEBUG(dbgs() << " Bottom up (default) ");
1931 }
1932
1933 while (!R.empty()) {
1934 if (Order == TopDown) {
1935 // Choose the node with the maximum height. If more than one, choose
1936 // the node wiTH the maximum ZeroLatencyHeight. If still more than one,
1937 // choose the node with the lowest MOV.
1938 while (!R.empty()) {
1939 SUnit *maxHeight = nullptr;
1940 for (SUnit *I : R) {
1941 if (maxHeight == nullptr || getHeight(I) > getHeight(maxHeight))
1942 maxHeight = I;
1943 else if (getHeight(I) == getHeight(maxHeight) &&
1944 getZeroLatencyHeight(I) > getZeroLatencyHeight(maxHeight))
1945 maxHeight = I;
1946 else if (getHeight(I) == getHeight(maxHeight) &&
1947 getZeroLatencyHeight(I) ==
1948 getZeroLatencyHeight(maxHeight) &&
1949 getMOV(I) < getMOV(maxHeight))
1950 maxHeight = I;
1951 }
1952 NodeOrder.insert(maxHeight);
1953 LLVM_DEBUG(dbgs() << maxHeight->NodeNum << " ");
1954 R.remove(maxHeight);
1955 for (const auto &I : maxHeight->Succs) {
1956 if (Nodes.count(I.getSUnit()) == 0)
1957 continue;
1958 if (NodeOrder.contains(I.getSUnit()))
1959 continue;
1960 if (ignoreDependence(I, false))
1961 continue;
1962 R.insert(I.getSUnit());
1963 }
1964 // Back-edges are predecessors with an anti-dependence.
1965 for (const auto &I : maxHeight->Preds) {
1966 if (I.getKind() != SDep::Anti)
1967 continue;
1968 if (Nodes.count(I.getSUnit()) == 0)
1969 continue;
1970 if (NodeOrder.contains(I.getSUnit()))
1971 continue;
1972 R.insert(I.getSUnit());
1973 }
1974 }
1975 Order = BottomUp;
1976 LLVM_DEBUG(dbgs() << "\n Switching order to bottom up ");
1977 SmallSetVector<SUnit *, 8> N;
1978 if (pred_L(NodeOrder, N, &Nodes))
1979 R.insert(N.begin(), N.end());
1980 } else {
1981 // Choose the node with the maximum depth. If more than one, choose
1982 // the node with the maximum ZeroLatencyDepth. If still more than one,
1983 // choose the node with the lowest MOV.
1984 while (!R.empty()) {
1985 SUnit *maxDepth = nullptr;
1986 for (SUnit *I : R) {
1987 if (maxDepth == nullptr || getDepth(I) > getDepth(maxDepth))
1988 maxDepth = I;
1989 else if (getDepth(I) == getDepth(maxDepth) &&
1990 getZeroLatencyDepth(I) > getZeroLatencyDepth(maxDepth))
1991 maxDepth = I;
1992 else if (getDepth(I) == getDepth(maxDepth) &&
1993 getZeroLatencyDepth(I) == getZeroLatencyDepth(maxDepth) &&
1994 getMOV(I) < getMOV(maxDepth))
1995 maxDepth = I;
1996 }
1997 NodeOrder.insert(maxDepth);
1998 LLVM_DEBUG(dbgs() << maxDepth->NodeNum << " ");
1999 R.remove(maxDepth);
2000 if (Nodes.isExceedSU(maxDepth)) {
2001 Order = TopDown;
2002 R.clear();
2003 R.insert(Nodes.getNode(0));
2004 break;
2005 }
2006 for (const auto &I : maxDepth->Preds) {
2007 if (Nodes.count(I.getSUnit()) == 0)
2008 continue;
2009 if (NodeOrder.contains(I.getSUnit()))
2010 continue;
2011 R.insert(I.getSUnit());
2012 }
2013 // Back-edges are predecessors with an anti-dependence.
2014 for (const auto &I : maxDepth->Succs) {
2015 if (I.getKind() != SDep::Anti)
2016 continue;
2017 if (Nodes.count(I.getSUnit()) == 0)
2018 continue;
2019 if (NodeOrder.contains(I.getSUnit()))
2020 continue;
2021 R.insert(I.getSUnit());
2022 }
2023 }
2024 Order = TopDown;
2025 LLVM_DEBUG(dbgs() << "\n Switching order to top down ");
2026 SmallSetVector<SUnit *, 8> N;
2027 if (succ_L(NodeOrder, N, &Nodes))
2028 R.insert(N.begin(), N.end());
2029 }
2030 }
2031 LLVM_DEBUG(dbgs() << "\nDone with Nodeset\n");
2032 }
2033
2034 LLVM_DEBUG({
2035 dbgs() << "Node order: ";
2036 for (SUnit *I : NodeOrder)
2037 dbgs() << " " << I->NodeNum << " ";
2038 dbgs() << "\n";
2039 });
2040 }
2041
2042 /// Process the nodes in the computed order and create the pipelined schedule
2043 /// of the instructions, if possible. Return true if a schedule is found.
schedulePipeline(SMSchedule & Schedule)2044 bool SwingSchedulerDAG::schedulePipeline(SMSchedule &Schedule) {
2045
2046 if (NodeOrder.empty()){
2047 LLVM_DEBUG(dbgs() << "NodeOrder is empty! abort scheduling\n" );
2048 return false;
2049 }
2050
2051 bool scheduleFound = false;
2052 unsigned II = 0;
2053 // Keep increasing II until a valid schedule is found.
2054 for (II = MII; II <= MAX_II && !scheduleFound; ++II) {
2055 Schedule.reset();
2056 Schedule.setInitiationInterval(II);
2057 LLVM_DEBUG(dbgs() << "Try to schedule with " << II << "\n");
2058
2059 SetVector<SUnit *>::iterator NI = NodeOrder.begin();
2060 SetVector<SUnit *>::iterator NE = NodeOrder.end();
2061 do {
2062 SUnit *SU = *NI;
2063
2064 // Compute the schedule time for the instruction, which is based
2065 // upon the scheduled time for any predecessors/successors.
2066 int EarlyStart = INT_MIN;
2067 int LateStart = INT_MAX;
2068 // These values are set when the size of the schedule window is limited
2069 // due to chain dependences.
2070 int SchedEnd = INT_MAX;
2071 int SchedStart = INT_MIN;
2072 Schedule.computeStart(SU, &EarlyStart, &LateStart, &SchedEnd, &SchedStart,
2073 II, this);
2074 LLVM_DEBUG({
2075 dbgs() << "\n";
2076 dbgs() << "Inst (" << SU->NodeNum << ") ";
2077 SU->getInstr()->dump();
2078 dbgs() << "\n";
2079 });
2080 LLVM_DEBUG({
2081 dbgs() << format("\tes: %8x ls: %8x me: %8x ms: %8x\n", EarlyStart,
2082 LateStart, SchedEnd, SchedStart);
2083 });
2084
2085 if (EarlyStart > LateStart || SchedEnd < EarlyStart ||
2086 SchedStart > LateStart)
2087 scheduleFound = false;
2088 else if (EarlyStart != INT_MIN && LateStart == INT_MAX) {
2089 SchedEnd = std::min(SchedEnd, EarlyStart + (int)II - 1);
2090 scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II);
2091 } else if (EarlyStart == INT_MIN && LateStart != INT_MAX) {
2092 SchedStart = std::max(SchedStart, LateStart - (int)II + 1);
2093 scheduleFound = Schedule.insert(SU, LateStart, SchedStart, II);
2094 } else if (EarlyStart != INT_MIN && LateStart != INT_MAX) {
2095 SchedEnd =
2096 std::min(SchedEnd, std::min(LateStart, EarlyStart + (int)II - 1));
2097 // When scheduling a Phi it is better to start at the late cycle and go
2098 // backwards. The default order may insert the Phi too far away from
2099 // its first dependence.
2100 if (SU->getInstr()->isPHI())
2101 scheduleFound = Schedule.insert(SU, SchedEnd, EarlyStart, II);
2102 else
2103 scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II);
2104 } else {
2105 int FirstCycle = Schedule.getFirstCycle();
2106 scheduleFound = Schedule.insert(SU, FirstCycle + getASAP(SU),
2107 FirstCycle + getASAP(SU) + II - 1, II);
2108 }
2109 // Even if we find a schedule, make sure the schedule doesn't exceed the
2110 // allowable number of stages. We keep trying if this happens.
2111 if (scheduleFound)
2112 if (SwpMaxStages > -1 &&
2113 Schedule.getMaxStageCount() > (unsigned)SwpMaxStages)
2114 scheduleFound = false;
2115
2116 LLVM_DEBUG({
2117 if (!scheduleFound)
2118 dbgs() << "\tCan't schedule\n";
2119 });
2120 } while (++NI != NE && scheduleFound);
2121
2122 // If a schedule is found, check if it is a valid schedule too.
2123 if (scheduleFound)
2124 scheduleFound = Schedule.isValidSchedule(this);
2125 }
2126
2127 LLVM_DEBUG(dbgs() << "Schedule Found? " << scheduleFound << " (II=" << II
2128 << ")\n");
2129
2130 if (scheduleFound) {
2131 Schedule.finalizeSchedule(this);
2132 Pass.ORE->emit([&]() {
2133 return MachineOptimizationRemarkAnalysis(
2134 DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
2135 << "Schedule found with Initiation Interval: " << ore::NV("II", II)
2136 << ", MaxStageCount: "
2137 << ore::NV("MaxStageCount", Schedule.getMaxStageCount());
2138 });
2139 } else
2140 Schedule.reset();
2141
2142 return scheduleFound && Schedule.getMaxStageCount() > 0;
2143 }
2144
2145 /// Return true if we can compute the amount the instruction changes
2146 /// during each iteration. Set Delta to the amount of the change.
computeDelta(MachineInstr & MI,unsigned & Delta)2147 bool SwingSchedulerDAG::computeDelta(MachineInstr &MI, unsigned &Delta) {
2148 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
2149 const MachineOperand *BaseOp;
2150 int64_t Offset;
2151 bool OffsetIsScalable;
2152 if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable, TRI))
2153 return false;
2154
2155 // FIXME: This algorithm assumes instructions have fixed-size offsets.
2156 if (OffsetIsScalable)
2157 return false;
2158
2159 if (!BaseOp->isReg())
2160 return false;
2161
2162 Register BaseReg = BaseOp->getReg();
2163
2164 MachineRegisterInfo &MRI = MF.getRegInfo();
2165 // Check if there is a Phi. If so, get the definition in the loop.
2166 MachineInstr *BaseDef = MRI.getVRegDef(BaseReg);
2167 if (BaseDef && BaseDef->isPHI()) {
2168 BaseReg = getLoopPhiReg(*BaseDef, MI.getParent());
2169 BaseDef = MRI.getVRegDef(BaseReg);
2170 }
2171 if (!BaseDef)
2172 return false;
2173
2174 int D = 0;
2175 if (!TII->getIncrementValue(*BaseDef, D) && D >= 0)
2176 return false;
2177
2178 Delta = D;
2179 return true;
2180 }
2181
2182 /// Check if we can change the instruction to use an offset value from the
2183 /// previous iteration. If so, return true and set the base and offset values
2184 /// so that we can rewrite the load, if necessary.
2185 /// v1 = Phi(v0, v3)
2186 /// v2 = load v1, 0
2187 /// v3 = post_store v1, 4, x
2188 /// This function enables the load to be rewritten as v2 = load v3, 4.
canUseLastOffsetValue(MachineInstr * MI,unsigned & BasePos,unsigned & OffsetPos,unsigned & NewBase,int64_t & Offset)2189 bool SwingSchedulerDAG::canUseLastOffsetValue(MachineInstr *MI,
2190 unsigned &BasePos,
2191 unsigned &OffsetPos,
2192 unsigned &NewBase,
2193 int64_t &Offset) {
2194 // Get the load instruction.
2195 if (TII->isPostIncrement(*MI))
2196 return false;
2197 unsigned BasePosLd, OffsetPosLd;
2198 if (!TII->getBaseAndOffsetPosition(*MI, BasePosLd, OffsetPosLd))
2199 return false;
2200 Register BaseReg = MI->getOperand(BasePosLd).getReg();
2201
2202 // Look for the Phi instruction.
2203 MachineRegisterInfo &MRI = MI->getMF()->getRegInfo();
2204 MachineInstr *Phi = MRI.getVRegDef(BaseReg);
2205 if (!Phi || !Phi->isPHI())
2206 return false;
2207 // Get the register defined in the loop block.
2208 unsigned PrevReg = getLoopPhiReg(*Phi, MI->getParent());
2209 if (!PrevReg)
2210 return false;
2211
2212 // Check for the post-increment load/store instruction.
2213 MachineInstr *PrevDef = MRI.getVRegDef(PrevReg);
2214 if (!PrevDef || PrevDef == MI)
2215 return false;
2216
2217 if (!TII->isPostIncrement(*PrevDef))
2218 return false;
2219
2220 unsigned BasePos1 = 0, OffsetPos1 = 0;
2221 if (!TII->getBaseAndOffsetPosition(*PrevDef, BasePos1, OffsetPos1))
2222 return false;
2223
2224 // Make sure that the instructions do not access the same memory location in
2225 // the next iteration.
2226 int64_t LoadOffset = MI->getOperand(OffsetPosLd).getImm();
2227 int64_t StoreOffset = PrevDef->getOperand(OffsetPos1).getImm();
2228 MachineInstr *NewMI = MF.CloneMachineInstr(MI);
2229 NewMI->getOperand(OffsetPosLd).setImm(LoadOffset + StoreOffset);
2230 bool Disjoint = TII->areMemAccessesTriviallyDisjoint(*NewMI, *PrevDef);
2231 MF.DeleteMachineInstr(NewMI);
2232 if (!Disjoint)
2233 return false;
2234
2235 // Set the return value once we determine that we return true.
2236 BasePos = BasePosLd;
2237 OffsetPos = OffsetPosLd;
2238 NewBase = PrevReg;
2239 Offset = StoreOffset;
2240 return true;
2241 }
2242
2243 /// Apply changes to the instruction if needed. The changes are need
2244 /// to improve the scheduling and depend up on the final schedule.
applyInstrChange(MachineInstr * MI,SMSchedule & Schedule)2245 void SwingSchedulerDAG::applyInstrChange(MachineInstr *MI,
2246 SMSchedule &Schedule) {
2247 SUnit *SU = getSUnit(MI);
2248 DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It =
2249 InstrChanges.find(SU);
2250 if (It != InstrChanges.end()) {
2251 std::pair<unsigned, int64_t> RegAndOffset = It->second;
2252 unsigned BasePos, OffsetPos;
2253 if (!TII->getBaseAndOffsetPosition(*MI, BasePos, OffsetPos))
2254 return;
2255 Register BaseReg = MI->getOperand(BasePos).getReg();
2256 MachineInstr *LoopDef = findDefInLoop(BaseReg);
2257 int DefStageNum = Schedule.stageScheduled(getSUnit(LoopDef));
2258 int DefCycleNum = Schedule.cycleScheduled(getSUnit(LoopDef));
2259 int BaseStageNum = Schedule.stageScheduled(SU);
2260 int BaseCycleNum = Schedule.cycleScheduled(SU);
2261 if (BaseStageNum < DefStageNum) {
2262 MachineInstr *NewMI = MF.CloneMachineInstr(MI);
2263 int OffsetDiff = DefStageNum - BaseStageNum;
2264 if (DefCycleNum < BaseCycleNum) {
2265 NewMI->getOperand(BasePos).setReg(RegAndOffset.first);
2266 if (OffsetDiff > 0)
2267 --OffsetDiff;
2268 }
2269 int64_t NewOffset =
2270 MI->getOperand(OffsetPos).getImm() + RegAndOffset.second * OffsetDiff;
2271 NewMI->getOperand(OffsetPos).setImm(NewOffset);
2272 SU->setInstr(NewMI);
2273 MISUnitMap[NewMI] = SU;
2274 NewMIs[MI] = NewMI;
2275 }
2276 }
2277 }
2278
2279 /// Return the instruction in the loop that defines the register.
2280 /// If the definition is a Phi, then follow the Phi operand to
2281 /// the instruction in the loop.
findDefInLoop(Register Reg)2282 MachineInstr *SwingSchedulerDAG::findDefInLoop(Register Reg) {
2283 SmallPtrSet<MachineInstr *, 8> Visited;
2284 MachineInstr *Def = MRI.getVRegDef(Reg);
2285 while (Def->isPHI()) {
2286 if (!Visited.insert(Def).second)
2287 break;
2288 for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2)
2289 if (Def->getOperand(i + 1).getMBB() == BB) {
2290 Def = MRI.getVRegDef(Def->getOperand(i).getReg());
2291 break;
2292 }
2293 }
2294 return Def;
2295 }
2296
2297 /// Return true for an order or output dependence that is loop carried
2298 /// potentially. A dependence is loop carried if the destination defines a valu
2299 /// that may be used or defined by the source in a subsequent iteration.
isLoopCarriedDep(SUnit * Source,const SDep & Dep,bool isSucc)2300 bool SwingSchedulerDAG::isLoopCarriedDep(SUnit *Source, const SDep &Dep,
2301 bool isSucc) {
2302 if ((Dep.getKind() != SDep::Order && Dep.getKind() != SDep::Output) ||
2303 Dep.isArtificial())
2304 return false;
2305
2306 if (!SwpPruneLoopCarried)
2307 return true;
2308
2309 if (Dep.getKind() == SDep::Output)
2310 return true;
2311
2312 MachineInstr *SI = Source->getInstr();
2313 MachineInstr *DI = Dep.getSUnit()->getInstr();
2314 if (!isSucc)
2315 std::swap(SI, DI);
2316 assert(SI != nullptr && DI != nullptr && "Expecting SUnit with an MI.");
2317
2318 // Assume ordered loads and stores may have a loop carried dependence.
2319 if (SI->hasUnmodeledSideEffects() || DI->hasUnmodeledSideEffects() ||
2320 SI->mayRaiseFPException() || DI->mayRaiseFPException() ||
2321 SI->hasOrderedMemoryRef() || DI->hasOrderedMemoryRef())
2322 return true;
2323
2324 // Only chain dependences between a load and store can be loop carried.
2325 if (!DI->mayStore() || !SI->mayLoad())
2326 return false;
2327
2328 unsigned DeltaS, DeltaD;
2329 if (!computeDelta(*SI, DeltaS) || !computeDelta(*DI, DeltaD))
2330 return true;
2331
2332 const MachineOperand *BaseOpS, *BaseOpD;
2333 int64_t OffsetS, OffsetD;
2334 bool OffsetSIsScalable, OffsetDIsScalable;
2335 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
2336 if (!TII->getMemOperandWithOffset(*SI, BaseOpS, OffsetS, OffsetSIsScalable,
2337 TRI) ||
2338 !TII->getMemOperandWithOffset(*DI, BaseOpD, OffsetD, OffsetDIsScalable,
2339 TRI))
2340 return true;
2341
2342 assert(!OffsetSIsScalable && !OffsetDIsScalable &&
2343 "Expected offsets to be byte offsets");
2344
2345 if (!BaseOpS->isIdenticalTo(*BaseOpD))
2346 return true;
2347
2348 // Check that the base register is incremented by a constant value for each
2349 // iteration.
2350 MachineInstr *Def = MRI.getVRegDef(BaseOpS->getReg());
2351 if (!Def || !Def->isPHI())
2352 return true;
2353 unsigned InitVal = 0;
2354 unsigned LoopVal = 0;
2355 getPhiRegs(*Def, BB, InitVal, LoopVal);
2356 MachineInstr *LoopDef = MRI.getVRegDef(LoopVal);
2357 int D = 0;
2358 if (!LoopDef || !TII->getIncrementValue(*LoopDef, D))
2359 return true;
2360
2361 uint64_t AccessSizeS = (*SI->memoperands_begin())->getSize();
2362 uint64_t AccessSizeD = (*DI->memoperands_begin())->getSize();
2363
2364 // This is the main test, which checks the offset values and the loop
2365 // increment value to determine if the accesses may be loop carried.
2366 if (AccessSizeS == MemoryLocation::UnknownSize ||
2367 AccessSizeD == MemoryLocation::UnknownSize)
2368 return true;
2369
2370 if (DeltaS != DeltaD || DeltaS < AccessSizeS || DeltaD < AccessSizeD)
2371 return true;
2372
2373 return (OffsetS + (int64_t)AccessSizeS < OffsetD + (int64_t)AccessSizeD);
2374 }
2375
postprocessDAG()2376 void SwingSchedulerDAG::postprocessDAG() {
2377 for (auto &M : Mutations)
2378 M->apply(this);
2379 }
2380
2381 /// Try to schedule the node at the specified StartCycle and continue
2382 /// until the node is schedule or the EndCycle is reached. This function
2383 /// returns true if the node is scheduled. This routine may search either
2384 /// forward or backward for a place to insert the instruction based upon
2385 /// the relative values of StartCycle and EndCycle.
insert(SUnit * SU,int StartCycle,int EndCycle,int II)2386 bool SMSchedule::insert(SUnit *SU, int StartCycle, int EndCycle, int II) {
2387 bool forward = true;
2388 LLVM_DEBUG({
2389 dbgs() << "Trying to insert node between " << StartCycle << " and "
2390 << EndCycle << " II: " << II << "\n";
2391 });
2392 if (StartCycle > EndCycle)
2393 forward = false;
2394
2395 // The terminating condition depends on the direction.
2396 int termCycle = forward ? EndCycle + 1 : EndCycle - 1;
2397 for (int curCycle = StartCycle; curCycle != termCycle;
2398 forward ? ++curCycle : --curCycle) {
2399
2400 // Add the already scheduled instructions at the specified cycle to the
2401 // DFA.
2402 ProcItinResources.clearResources();
2403 for (int checkCycle = FirstCycle + ((curCycle - FirstCycle) % II);
2404 checkCycle <= LastCycle; checkCycle += II) {
2405 std::deque<SUnit *> &cycleInstrs = ScheduledInstrs[checkCycle];
2406
2407 for (std::deque<SUnit *>::iterator I = cycleInstrs.begin(),
2408 E = cycleInstrs.end();
2409 I != E; ++I) {
2410 if (ST.getInstrInfo()->isZeroCost((*I)->getInstr()->getOpcode()))
2411 continue;
2412 assert(ProcItinResources.canReserveResources(*(*I)->getInstr()) &&
2413 "These instructions have already been scheduled.");
2414 ProcItinResources.reserveResources(*(*I)->getInstr());
2415 }
2416 }
2417 if (ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode()) ||
2418 ProcItinResources.canReserveResources(*SU->getInstr())) {
2419 LLVM_DEBUG({
2420 dbgs() << "\tinsert at cycle " << curCycle << " ";
2421 SU->getInstr()->dump();
2422 });
2423
2424 ScheduledInstrs[curCycle].push_back(SU);
2425 InstrToCycle.insert(std::make_pair(SU, curCycle));
2426 if (curCycle > LastCycle)
2427 LastCycle = curCycle;
2428 if (curCycle < FirstCycle)
2429 FirstCycle = curCycle;
2430 return true;
2431 }
2432 LLVM_DEBUG({
2433 dbgs() << "\tfailed to insert at cycle " << curCycle << " ";
2434 SU->getInstr()->dump();
2435 });
2436 }
2437 return false;
2438 }
2439
2440 // Return the cycle of the earliest scheduled instruction in the chain.
earliestCycleInChain(const SDep & Dep)2441 int SMSchedule::earliestCycleInChain(const SDep &Dep) {
2442 SmallPtrSet<SUnit *, 8> Visited;
2443 SmallVector<SDep, 8> Worklist;
2444 Worklist.push_back(Dep);
2445 int EarlyCycle = INT_MAX;
2446 while (!Worklist.empty()) {
2447 const SDep &Cur = Worklist.pop_back_val();
2448 SUnit *PrevSU = Cur.getSUnit();
2449 if (Visited.count(PrevSU))
2450 continue;
2451 std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(PrevSU);
2452 if (it == InstrToCycle.end())
2453 continue;
2454 EarlyCycle = std::min(EarlyCycle, it->second);
2455 for (const auto &PI : PrevSU->Preds)
2456 if (PI.getKind() == SDep::Order || PI.getKind() == SDep::Output)
2457 Worklist.push_back(PI);
2458 Visited.insert(PrevSU);
2459 }
2460 return EarlyCycle;
2461 }
2462
2463 // Return the cycle of the latest scheduled instruction in the chain.
latestCycleInChain(const SDep & Dep)2464 int SMSchedule::latestCycleInChain(const SDep &Dep) {
2465 SmallPtrSet<SUnit *, 8> Visited;
2466 SmallVector<SDep, 8> Worklist;
2467 Worklist.push_back(Dep);
2468 int LateCycle = INT_MIN;
2469 while (!Worklist.empty()) {
2470 const SDep &Cur = Worklist.pop_back_val();
2471 SUnit *SuccSU = Cur.getSUnit();
2472 if (Visited.count(SuccSU))
2473 continue;
2474 std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SuccSU);
2475 if (it == InstrToCycle.end())
2476 continue;
2477 LateCycle = std::max(LateCycle, it->second);
2478 for (const auto &SI : SuccSU->Succs)
2479 if (SI.getKind() == SDep::Order || SI.getKind() == SDep::Output)
2480 Worklist.push_back(SI);
2481 Visited.insert(SuccSU);
2482 }
2483 return LateCycle;
2484 }
2485
2486 /// If an instruction has a use that spans multiple iterations, then
2487 /// return true. These instructions are characterized by having a back-ege
2488 /// to a Phi, which contains a reference to another Phi.
multipleIterations(SUnit * SU,SwingSchedulerDAG * DAG)2489 static SUnit *multipleIterations(SUnit *SU, SwingSchedulerDAG *DAG) {
2490 for (auto &P : SU->Preds)
2491 if (DAG->isBackedge(SU, P) && P.getSUnit()->getInstr()->isPHI())
2492 for (auto &S : P.getSUnit()->Succs)
2493 if (S.getKind() == SDep::Data && S.getSUnit()->getInstr()->isPHI())
2494 return P.getSUnit();
2495 return nullptr;
2496 }
2497
2498 /// Compute the scheduling start slot for the instruction. The start slot
2499 /// depends on any predecessor or successor nodes scheduled already.
computeStart(SUnit * SU,int * MaxEarlyStart,int * MinLateStart,int * MinEnd,int * MaxStart,int II,SwingSchedulerDAG * DAG)2500 void SMSchedule::computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart,
2501 int *MinEnd, int *MaxStart, int II,
2502 SwingSchedulerDAG *DAG) {
2503 // Iterate over each instruction that has been scheduled already. The start
2504 // slot computation depends on whether the previously scheduled instruction
2505 // is a predecessor or successor of the specified instruction.
2506 for (int cycle = getFirstCycle(); cycle <= LastCycle; ++cycle) {
2507
2508 // Iterate over each instruction in the current cycle.
2509 for (SUnit *I : getInstructions(cycle)) {
2510 // Because we're processing a DAG for the dependences, we recognize
2511 // the back-edge in recurrences by anti dependences.
2512 for (unsigned i = 0, e = (unsigned)SU->Preds.size(); i != e; ++i) {
2513 const SDep &Dep = SU->Preds[i];
2514 if (Dep.getSUnit() == I) {
2515 if (!DAG->isBackedge(SU, Dep)) {
2516 int EarlyStart = cycle + Dep.getLatency() -
2517 DAG->getDistance(Dep.getSUnit(), SU, Dep) * II;
2518 *MaxEarlyStart = std::max(*MaxEarlyStart, EarlyStart);
2519 if (DAG->isLoopCarriedDep(SU, Dep, false)) {
2520 int End = earliestCycleInChain(Dep) + (II - 1);
2521 *MinEnd = std::min(*MinEnd, End);
2522 }
2523 } else {
2524 int LateStart = cycle - Dep.getLatency() +
2525 DAG->getDistance(SU, Dep.getSUnit(), Dep) * II;
2526 *MinLateStart = std::min(*MinLateStart, LateStart);
2527 }
2528 }
2529 // For instruction that requires multiple iterations, make sure that
2530 // the dependent instruction is not scheduled past the definition.
2531 SUnit *BE = multipleIterations(I, DAG);
2532 if (BE && Dep.getSUnit() == BE && !SU->getInstr()->isPHI() &&
2533 !SU->isPred(I))
2534 *MinLateStart = std::min(*MinLateStart, cycle);
2535 }
2536 for (unsigned i = 0, e = (unsigned)SU->Succs.size(); i != e; ++i) {
2537 if (SU->Succs[i].getSUnit() == I) {
2538 const SDep &Dep = SU->Succs[i];
2539 if (!DAG->isBackedge(SU, Dep)) {
2540 int LateStart = cycle - Dep.getLatency() +
2541 DAG->getDistance(SU, Dep.getSUnit(), Dep) * II;
2542 *MinLateStart = std::min(*MinLateStart, LateStart);
2543 if (DAG->isLoopCarriedDep(SU, Dep)) {
2544 int Start = latestCycleInChain(Dep) + 1 - II;
2545 *MaxStart = std::max(*MaxStart, Start);
2546 }
2547 } else {
2548 int EarlyStart = cycle + Dep.getLatency() -
2549 DAG->getDistance(Dep.getSUnit(), SU, Dep) * II;
2550 *MaxEarlyStart = std::max(*MaxEarlyStart, EarlyStart);
2551 }
2552 }
2553 }
2554 }
2555 }
2556 }
2557
2558 /// Order the instructions within a cycle so that the definitions occur
2559 /// before the uses. Returns true if the instruction is added to the start
2560 /// of the list, or false if added to the end.
orderDependence(SwingSchedulerDAG * SSD,SUnit * SU,std::deque<SUnit * > & Insts)2561 void SMSchedule::orderDependence(SwingSchedulerDAG *SSD, SUnit *SU,
2562 std::deque<SUnit *> &Insts) {
2563 MachineInstr *MI = SU->getInstr();
2564 bool OrderBeforeUse = false;
2565 bool OrderAfterDef = false;
2566 bool OrderBeforeDef = false;
2567 unsigned MoveDef = 0;
2568 unsigned MoveUse = 0;
2569 int StageInst1 = stageScheduled(SU);
2570
2571 unsigned Pos = 0;
2572 for (std::deque<SUnit *>::iterator I = Insts.begin(), E = Insts.end(); I != E;
2573 ++I, ++Pos) {
2574 for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) {
2575 MachineOperand &MO = MI->getOperand(i);
2576 if (!MO.isReg() || !Register::isVirtualRegister(MO.getReg()))
2577 continue;
2578
2579 Register Reg = MO.getReg();
2580 unsigned BasePos, OffsetPos;
2581 if (ST.getInstrInfo()->getBaseAndOffsetPosition(*MI, BasePos, OffsetPos))
2582 if (MI->getOperand(BasePos).getReg() == Reg)
2583 if (unsigned NewReg = SSD->getInstrBaseReg(SU))
2584 Reg = NewReg;
2585 bool Reads, Writes;
2586 std::tie(Reads, Writes) =
2587 (*I)->getInstr()->readsWritesVirtualRegister(Reg);
2588 if (MO.isDef() && Reads && stageScheduled(*I) <= StageInst1) {
2589 OrderBeforeUse = true;
2590 if (MoveUse == 0)
2591 MoveUse = Pos;
2592 } else if (MO.isDef() && Reads && stageScheduled(*I) > StageInst1) {
2593 // Add the instruction after the scheduled instruction.
2594 OrderAfterDef = true;
2595 MoveDef = Pos;
2596 } else if (MO.isUse() && Writes && stageScheduled(*I) == StageInst1) {
2597 if (cycleScheduled(*I) == cycleScheduled(SU) && !(*I)->isSucc(SU)) {
2598 OrderBeforeUse = true;
2599 if (MoveUse == 0)
2600 MoveUse = Pos;
2601 } else {
2602 OrderAfterDef = true;
2603 MoveDef = Pos;
2604 }
2605 } else if (MO.isUse() && Writes && stageScheduled(*I) > StageInst1) {
2606 OrderBeforeUse = true;
2607 if (MoveUse == 0)
2608 MoveUse = Pos;
2609 if (MoveUse != 0) {
2610 OrderAfterDef = true;
2611 MoveDef = Pos - 1;
2612 }
2613 } else if (MO.isUse() && Writes && stageScheduled(*I) < StageInst1) {
2614 // Add the instruction before the scheduled instruction.
2615 OrderBeforeUse = true;
2616 if (MoveUse == 0)
2617 MoveUse = Pos;
2618 } else if (MO.isUse() && stageScheduled(*I) == StageInst1 &&
2619 isLoopCarriedDefOfUse(SSD, (*I)->getInstr(), MO)) {
2620 if (MoveUse == 0) {
2621 OrderBeforeDef = true;
2622 MoveUse = Pos;
2623 }
2624 }
2625 }
2626 // Check for order dependences between instructions. Make sure the source
2627 // is ordered before the destination.
2628 for (auto &S : SU->Succs) {
2629 if (S.getSUnit() != *I)
2630 continue;
2631 if (S.getKind() == SDep::Order && stageScheduled(*I) == StageInst1) {
2632 OrderBeforeUse = true;
2633 if (Pos < MoveUse)
2634 MoveUse = Pos;
2635 }
2636 // We did not handle HW dependences in previous for loop,
2637 // and we normally set Latency = 0 for Anti deps,
2638 // so may have nodes in same cycle with Anti denpendent on HW regs.
2639 else if (S.getKind() == SDep::Anti && stageScheduled(*I) == StageInst1) {
2640 OrderBeforeUse = true;
2641 if ((MoveUse == 0) || (Pos < MoveUse))
2642 MoveUse = Pos;
2643 }
2644 }
2645 for (auto &P : SU->Preds) {
2646 if (P.getSUnit() != *I)
2647 continue;
2648 if (P.getKind() == SDep::Order && stageScheduled(*I) == StageInst1) {
2649 OrderAfterDef = true;
2650 MoveDef = Pos;
2651 }
2652 }
2653 }
2654
2655 // A circular dependence.
2656 if (OrderAfterDef && OrderBeforeUse && MoveUse == MoveDef)
2657 OrderBeforeUse = false;
2658
2659 // OrderAfterDef takes precedences over OrderBeforeDef. The latter is due
2660 // to a loop-carried dependence.
2661 if (OrderBeforeDef)
2662 OrderBeforeUse = !OrderAfterDef || (MoveUse > MoveDef);
2663
2664 // The uncommon case when the instruction order needs to be updated because
2665 // there is both a use and def.
2666 if (OrderBeforeUse && OrderAfterDef) {
2667 SUnit *UseSU = Insts.at(MoveUse);
2668 SUnit *DefSU = Insts.at(MoveDef);
2669 if (MoveUse > MoveDef) {
2670 Insts.erase(Insts.begin() + MoveUse);
2671 Insts.erase(Insts.begin() + MoveDef);
2672 } else {
2673 Insts.erase(Insts.begin() + MoveDef);
2674 Insts.erase(Insts.begin() + MoveUse);
2675 }
2676 orderDependence(SSD, UseSU, Insts);
2677 orderDependence(SSD, SU, Insts);
2678 orderDependence(SSD, DefSU, Insts);
2679 return;
2680 }
2681 // Put the new instruction first if there is a use in the list. Otherwise,
2682 // put it at the end of the list.
2683 if (OrderBeforeUse)
2684 Insts.push_front(SU);
2685 else
2686 Insts.push_back(SU);
2687 }
2688
2689 /// Return true if the scheduled Phi has a loop carried operand.
isLoopCarried(SwingSchedulerDAG * SSD,MachineInstr & Phi)2690 bool SMSchedule::isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr &Phi) {
2691 if (!Phi.isPHI())
2692 return false;
2693 assert(Phi.isPHI() && "Expecting a Phi.");
2694 SUnit *DefSU = SSD->getSUnit(&Phi);
2695 unsigned DefCycle = cycleScheduled(DefSU);
2696 int DefStage = stageScheduled(DefSU);
2697
2698 unsigned InitVal = 0;
2699 unsigned LoopVal = 0;
2700 getPhiRegs(Phi, Phi.getParent(), InitVal, LoopVal);
2701 SUnit *UseSU = SSD->getSUnit(MRI.getVRegDef(LoopVal));
2702 if (!UseSU)
2703 return true;
2704 if (UseSU->getInstr()->isPHI())
2705 return true;
2706 unsigned LoopCycle = cycleScheduled(UseSU);
2707 int LoopStage = stageScheduled(UseSU);
2708 return (LoopCycle > DefCycle) || (LoopStage <= DefStage);
2709 }
2710
2711 /// Return true if the instruction is a definition that is loop carried
2712 /// and defines the use on the next iteration.
2713 /// v1 = phi(v2, v3)
2714 /// (Def) v3 = op v1
2715 /// (MO) = v1
2716 /// If MO appears before Def, then then v1 and v3 may get assigned to the same
2717 /// register.
isLoopCarriedDefOfUse(SwingSchedulerDAG * SSD,MachineInstr * Def,MachineOperand & MO)2718 bool SMSchedule::isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD,
2719 MachineInstr *Def, MachineOperand &MO) {
2720 if (!MO.isReg())
2721 return false;
2722 if (Def->isPHI())
2723 return false;
2724 MachineInstr *Phi = MRI.getVRegDef(MO.getReg());
2725 if (!Phi || !Phi->isPHI() || Phi->getParent() != Def->getParent())
2726 return false;
2727 if (!isLoopCarried(SSD, *Phi))
2728 return false;
2729 unsigned LoopReg = getLoopPhiReg(*Phi, Phi->getParent());
2730 for (unsigned i = 0, e = Def->getNumOperands(); i != e; ++i) {
2731 MachineOperand &DMO = Def->getOperand(i);
2732 if (!DMO.isReg() || !DMO.isDef())
2733 continue;
2734 if (DMO.getReg() == LoopReg)
2735 return true;
2736 }
2737 return false;
2738 }
2739
2740 // Check if the generated schedule is valid. This function checks if
2741 // an instruction that uses a physical register is scheduled in a
2742 // different stage than the definition. The pipeliner does not handle
2743 // physical register values that may cross a basic block boundary.
isValidSchedule(SwingSchedulerDAG * SSD)2744 bool SMSchedule::isValidSchedule(SwingSchedulerDAG *SSD) {
2745 for (int i = 0, e = SSD->SUnits.size(); i < e; ++i) {
2746 SUnit &SU = SSD->SUnits[i];
2747 if (!SU.hasPhysRegDefs)
2748 continue;
2749 int StageDef = stageScheduled(&SU);
2750 assert(StageDef != -1 && "Instruction should have been scheduled.");
2751 for (auto &SI : SU.Succs)
2752 if (SI.isAssignedRegDep())
2753 if (Register::isPhysicalRegister(SI.getReg()))
2754 if (stageScheduled(SI.getSUnit()) != StageDef)
2755 return false;
2756 }
2757 return true;
2758 }
2759
2760 /// A property of the node order in swing-modulo-scheduling is
2761 /// that for nodes outside circuits the following holds:
2762 /// none of them is scheduled after both a successor and a
2763 /// predecessor.
2764 /// The method below checks whether the property is met.
2765 /// If not, debug information is printed and statistics information updated.
2766 /// Note that we do not use an assert statement.
2767 /// The reason is that although an invalid node oder may prevent
2768 /// the pipeliner from finding a pipelined schedule for arbitrary II,
2769 /// it does not lead to the generation of incorrect code.
checkValidNodeOrder(const NodeSetType & Circuits) const2770 void SwingSchedulerDAG::checkValidNodeOrder(const NodeSetType &Circuits) const {
2771
2772 // a sorted vector that maps each SUnit to its index in the NodeOrder
2773 typedef std::pair<SUnit *, unsigned> UnitIndex;
2774 std::vector<UnitIndex> Indices(NodeOrder.size(), std::make_pair(nullptr, 0));
2775
2776 for (unsigned i = 0, s = NodeOrder.size(); i < s; ++i)
2777 Indices.push_back(std::make_pair(NodeOrder[i], i));
2778
2779 auto CompareKey = [](UnitIndex i1, UnitIndex i2) {
2780 return std::get<0>(i1) < std::get<0>(i2);
2781 };
2782
2783 // sort, so that we can perform a binary search
2784 llvm::sort(Indices, CompareKey);
2785
2786 bool Valid = true;
2787 (void)Valid;
2788 // for each SUnit in the NodeOrder, check whether
2789 // it appears after both a successor and a predecessor
2790 // of the SUnit. If this is the case, and the SUnit
2791 // is not part of circuit, then the NodeOrder is not
2792 // valid.
2793 for (unsigned i = 0, s = NodeOrder.size(); i < s; ++i) {
2794 SUnit *SU = NodeOrder[i];
2795 unsigned Index = i;
2796
2797 bool PredBefore = false;
2798 bool SuccBefore = false;
2799
2800 SUnit *Succ;
2801 SUnit *Pred;
2802 (void)Succ;
2803 (void)Pred;
2804
2805 for (SDep &PredEdge : SU->Preds) {
2806 SUnit *PredSU = PredEdge.getSUnit();
2807 unsigned PredIndex = std::get<1>(
2808 *llvm::lower_bound(Indices, std::make_pair(PredSU, 0), CompareKey));
2809 if (!PredSU->getInstr()->isPHI() && PredIndex < Index) {
2810 PredBefore = true;
2811 Pred = PredSU;
2812 break;
2813 }
2814 }
2815
2816 for (SDep &SuccEdge : SU->Succs) {
2817 SUnit *SuccSU = SuccEdge.getSUnit();
2818 // Do not process a boundary node, it was not included in NodeOrder,
2819 // hence not in Indices either, call to std::lower_bound() below will
2820 // return Indices.end().
2821 if (SuccSU->isBoundaryNode())
2822 continue;
2823 unsigned SuccIndex = std::get<1>(
2824 *llvm::lower_bound(Indices, std::make_pair(SuccSU, 0), CompareKey));
2825 if (!SuccSU->getInstr()->isPHI() && SuccIndex < Index) {
2826 SuccBefore = true;
2827 Succ = SuccSU;
2828 break;
2829 }
2830 }
2831
2832 if (PredBefore && SuccBefore && !SU->getInstr()->isPHI()) {
2833 // instructions in circuits are allowed to be scheduled
2834 // after both a successor and predecessor.
2835 bool InCircuit = llvm::any_of(
2836 Circuits, [SU](const NodeSet &Circuit) { return Circuit.count(SU); });
2837 if (InCircuit)
2838 LLVM_DEBUG(dbgs() << "In a circuit, predecessor ";);
2839 else {
2840 Valid = false;
2841 NumNodeOrderIssues++;
2842 LLVM_DEBUG(dbgs() << "Predecessor ";);
2843 }
2844 LLVM_DEBUG(dbgs() << Pred->NodeNum << " and successor " << Succ->NodeNum
2845 << " are scheduled before node " << SU->NodeNum
2846 << "\n";);
2847 }
2848 }
2849
2850 LLVM_DEBUG({
2851 if (!Valid)
2852 dbgs() << "Invalid node order found!\n";
2853 });
2854 }
2855
2856 /// Attempt to fix the degenerate cases when the instruction serialization
2857 /// causes the register lifetimes to overlap. For example,
2858 /// p' = store_pi(p, b)
2859 /// = load p, offset
2860 /// In this case p and p' overlap, which means that two registers are needed.
2861 /// Instead, this function changes the load to use p' and updates the offset.
fixupRegisterOverlaps(std::deque<SUnit * > & Instrs)2862 void SwingSchedulerDAG::fixupRegisterOverlaps(std::deque<SUnit *> &Instrs) {
2863 unsigned OverlapReg = 0;
2864 unsigned NewBaseReg = 0;
2865 for (SUnit *SU : Instrs) {
2866 MachineInstr *MI = SU->getInstr();
2867 for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) {
2868 const MachineOperand &MO = MI->getOperand(i);
2869 // Look for an instruction that uses p. The instruction occurs in the
2870 // same cycle but occurs later in the serialized order.
2871 if (MO.isReg() && MO.isUse() && MO.getReg() == OverlapReg) {
2872 // Check that the instruction appears in the InstrChanges structure,
2873 // which contains instructions that can have the offset updated.
2874 DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It =
2875 InstrChanges.find(SU);
2876 if (It != InstrChanges.end()) {
2877 unsigned BasePos, OffsetPos;
2878 // Update the base register and adjust the offset.
2879 if (TII->getBaseAndOffsetPosition(*MI, BasePos, OffsetPos)) {
2880 MachineInstr *NewMI = MF.CloneMachineInstr(MI);
2881 NewMI->getOperand(BasePos).setReg(NewBaseReg);
2882 int64_t NewOffset =
2883 MI->getOperand(OffsetPos).getImm() - It->second.second;
2884 NewMI->getOperand(OffsetPos).setImm(NewOffset);
2885 SU->setInstr(NewMI);
2886 MISUnitMap[NewMI] = SU;
2887 NewMIs[MI] = NewMI;
2888 }
2889 }
2890 OverlapReg = 0;
2891 NewBaseReg = 0;
2892 break;
2893 }
2894 // Look for an instruction of the form p' = op(p), which uses and defines
2895 // two virtual registers that get allocated to the same physical register.
2896 unsigned TiedUseIdx = 0;
2897 if (MI->isRegTiedToUseOperand(i, &TiedUseIdx)) {
2898 // OverlapReg is p in the example above.
2899 OverlapReg = MI->getOperand(TiedUseIdx).getReg();
2900 // NewBaseReg is p' in the example above.
2901 NewBaseReg = MI->getOperand(i).getReg();
2902 break;
2903 }
2904 }
2905 }
2906 }
2907
2908 /// After the schedule has been formed, call this function to combine
2909 /// the instructions from the different stages/cycles. That is, this
2910 /// function creates a schedule that represents a single iteration.
finalizeSchedule(SwingSchedulerDAG * SSD)2911 void SMSchedule::finalizeSchedule(SwingSchedulerDAG *SSD) {
2912 // Move all instructions to the first stage from later stages.
2913 for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) {
2914 for (int stage = 1, lastStage = getMaxStageCount(); stage <= lastStage;
2915 ++stage) {
2916 std::deque<SUnit *> &cycleInstrs =
2917 ScheduledInstrs[cycle + (stage * InitiationInterval)];
2918 for (std::deque<SUnit *>::reverse_iterator I = cycleInstrs.rbegin(),
2919 E = cycleInstrs.rend();
2920 I != E; ++I)
2921 ScheduledInstrs[cycle].push_front(*I);
2922 }
2923 }
2924
2925 // Erase all the elements in the later stages. Only one iteration should
2926 // remain in the scheduled list, and it contains all the instructions.
2927 for (int cycle = getFinalCycle() + 1; cycle <= LastCycle; ++cycle)
2928 ScheduledInstrs.erase(cycle);
2929
2930 // Change the registers in instruction as specified in the InstrChanges
2931 // map. We need to use the new registers to create the correct order.
2932 for (int i = 0, e = SSD->SUnits.size(); i != e; ++i) {
2933 SUnit *SU = &SSD->SUnits[i];
2934 SSD->applyInstrChange(SU->getInstr(), *this);
2935 }
2936
2937 // Reorder the instructions in each cycle to fix and improve the
2938 // generated code.
2939 for (int Cycle = getFirstCycle(), E = getFinalCycle(); Cycle <= E; ++Cycle) {
2940 std::deque<SUnit *> &cycleInstrs = ScheduledInstrs[Cycle];
2941 std::deque<SUnit *> newOrderPhi;
2942 for (unsigned i = 0, e = cycleInstrs.size(); i < e; ++i) {
2943 SUnit *SU = cycleInstrs[i];
2944 if (SU->getInstr()->isPHI())
2945 newOrderPhi.push_back(SU);
2946 }
2947 std::deque<SUnit *> newOrderI;
2948 for (unsigned i = 0, e = cycleInstrs.size(); i < e; ++i) {
2949 SUnit *SU = cycleInstrs[i];
2950 if (!SU->getInstr()->isPHI())
2951 orderDependence(SSD, SU, newOrderI);
2952 }
2953 // Replace the old order with the new order.
2954 cycleInstrs.swap(newOrderPhi);
2955 llvm::append_range(cycleInstrs, newOrderI);
2956 SSD->fixupRegisterOverlaps(cycleInstrs);
2957 }
2958
2959 LLVM_DEBUG(dump(););
2960 }
2961
print(raw_ostream & os) const2962 void NodeSet::print(raw_ostream &os) const {
2963 os << "Num nodes " << size() << " rec " << RecMII << " mov " << MaxMOV
2964 << " depth " << MaxDepth << " col " << Colocate << "\n";
2965 for (const auto &I : Nodes)
2966 os << " SU(" << I->NodeNum << ") " << *(I->getInstr());
2967 os << "\n";
2968 }
2969
2970 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2971 /// Print the schedule information to the given output.
print(raw_ostream & os) const2972 void SMSchedule::print(raw_ostream &os) const {
2973 // Iterate over each cycle.
2974 for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) {
2975 // Iterate over each instruction in the cycle.
2976 const_sched_iterator cycleInstrs = ScheduledInstrs.find(cycle);
2977 for (SUnit *CI : cycleInstrs->second) {
2978 os << "cycle " << cycle << " (" << stageScheduled(CI) << ") ";
2979 os << "(" << CI->NodeNum << ") ";
2980 CI->getInstr()->print(os);
2981 os << "\n";
2982 }
2983 }
2984 }
2985
2986 /// Utility function used for debugging to print the schedule.
dump() const2987 LLVM_DUMP_METHOD void SMSchedule::dump() const { print(dbgs()); }
dump() const2988 LLVM_DUMP_METHOD void NodeSet::dump() const { print(dbgs()); }
2989
2990 #endif
2991
initProcResourceVectors(const MCSchedModel & SM,SmallVectorImpl<uint64_t> & Masks)2992 void ResourceManager::initProcResourceVectors(
2993 const MCSchedModel &SM, SmallVectorImpl<uint64_t> &Masks) {
2994 unsigned ProcResourceID = 0;
2995
2996 // We currently limit the resource kinds to 64 and below so that we can use
2997 // uint64_t for Masks
2998 assert(SM.getNumProcResourceKinds() < 64 &&
2999 "Too many kinds of resources, unsupported");
3000 // Create a unique bitmask for every processor resource unit.
3001 // Skip resource at index 0, since it always references 'InvalidUnit'.
3002 Masks.resize(SM.getNumProcResourceKinds());
3003 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
3004 const MCProcResourceDesc &Desc = *SM.getProcResource(I);
3005 if (Desc.SubUnitsIdxBegin)
3006 continue;
3007 Masks[I] = 1ULL << ProcResourceID;
3008 ProcResourceID++;
3009 }
3010 // Create a unique bitmask for every processor resource group.
3011 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
3012 const MCProcResourceDesc &Desc = *SM.getProcResource(I);
3013 if (!Desc.SubUnitsIdxBegin)
3014 continue;
3015 Masks[I] = 1ULL << ProcResourceID;
3016 for (unsigned U = 0; U < Desc.NumUnits; ++U)
3017 Masks[I] |= Masks[Desc.SubUnitsIdxBegin[U]];
3018 ProcResourceID++;
3019 }
3020 LLVM_DEBUG({
3021 if (SwpShowResMask) {
3022 dbgs() << "ProcResourceDesc:\n";
3023 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
3024 const MCProcResourceDesc *ProcResource = SM.getProcResource(I);
3025 dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n",
3026 ProcResource->Name, I, Masks[I],
3027 ProcResource->NumUnits);
3028 }
3029 dbgs() << " -----------------\n";
3030 }
3031 });
3032 }
3033
canReserveResources(const MCInstrDesc * MID) const3034 bool ResourceManager::canReserveResources(const MCInstrDesc *MID) const {
3035
3036 LLVM_DEBUG({
3037 if (SwpDebugResource)
3038 dbgs() << "canReserveResources:\n";
3039 });
3040 if (UseDFA)
3041 return DFAResources->canReserveResources(MID);
3042
3043 unsigned InsnClass = MID->getSchedClass();
3044 const MCSchedClassDesc *SCDesc = SM.getSchedClassDesc(InsnClass);
3045 if (!SCDesc->isValid()) {
3046 LLVM_DEBUG({
3047 dbgs() << "No valid Schedule Class Desc for schedClass!\n";
3048 dbgs() << "isPseduo:" << MID->isPseudo() << "\n";
3049 });
3050 return true;
3051 }
3052
3053 const MCWriteProcResEntry *I = STI->getWriteProcResBegin(SCDesc);
3054 const MCWriteProcResEntry *E = STI->getWriteProcResEnd(SCDesc);
3055 for (; I != E; ++I) {
3056 if (!I->Cycles)
3057 continue;
3058 const MCProcResourceDesc *ProcResource =
3059 SM.getProcResource(I->ProcResourceIdx);
3060 unsigned NumUnits = ProcResource->NumUnits;
3061 LLVM_DEBUG({
3062 if (SwpDebugResource)
3063 dbgs() << format(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n",
3064 ProcResource->Name, I->ProcResourceIdx,
3065 ProcResourceCount[I->ProcResourceIdx], NumUnits,
3066 I->Cycles);
3067 });
3068 if (ProcResourceCount[I->ProcResourceIdx] >= NumUnits)
3069 return false;
3070 }
3071 LLVM_DEBUG(if (SwpDebugResource) dbgs() << "return true\n\n";);
3072 return true;
3073 }
3074
reserveResources(const MCInstrDesc * MID)3075 void ResourceManager::reserveResources(const MCInstrDesc *MID) {
3076 LLVM_DEBUG({
3077 if (SwpDebugResource)
3078 dbgs() << "reserveResources:\n";
3079 });
3080 if (UseDFA)
3081 return DFAResources->reserveResources(MID);
3082
3083 unsigned InsnClass = MID->getSchedClass();
3084 const MCSchedClassDesc *SCDesc = SM.getSchedClassDesc(InsnClass);
3085 if (!SCDesc->isValid()) {
3086 LLVM_DEBUG({
3087 dbgs() << "No valid Schedule Class Desc for schedClass!\n";
3088 dbgs() << "isPseduo:" << MID->isPseudo() << "\n";
3089 });
3090 return;
3091 }
3092 for (const MCWriteProcResEntry &PRE :
3093 make_range(STI->getWriteProcResBegin(SCDesc),
3094 STI->getWriteProcResEnd(SCDesc))) {
3095 if (!PRE.Cycles)
3096 continue;
3097 ++ProcResourceCount[PRE.ProcResourceIdx];
3098 LLVM_DEBUG({
3099 if (SwpDebugResource) {
3100 const MCProcResourceDesc *ProcResource =
3101 SM.getProcResource(PRE.ProcResourceIdx);
3102 dbgs() << format(" %16s(%2d): Count: %2d, NumUnits:%2d, Cycles:%2d\n",
3103 ProcResource->Name, PRE.ProcResourceIdx,
3104 ProcResourceCount[PRE.ProcResourceIdx],
3105 ProcResource->NumUnits, PRE.Cycles);
3106 }
3107 });
3108 }
3109 LLVM_DEBUG({
3110 if (SwpDebugResource)
3111 dbgs() << "reserveResources: done!\n\n";
3112 });
3113 }
3114
canReserveResources(const MachineInstr & MI) const3115 bool ResourceManager::canReserveResources(const MachineInstr &MI) const {
3116 return canReserveResources(&MI.getDesc());
3117 }
3118
reserveResources(const MachineInstr & MI)3119 void ResourceManager::reserveResources(const MachineInstr &MI) {
3120 return reserveResources(&MI.getDesc());
3121 }
3122
clearResources()3123 void ResourceManager::clearResources() {
3124 if (UseDFA)
3125 return DFAResources->clearResources();
3126 std::fill(ProcResourceCount.begin(), ProcResourceCount.end(), 0);
3127 }
3128