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/CodeGen/MachinePipeliner.h"
33#include "llvm/ADT/ArrayRef.h"
34#include "llvm/ADT/BitVector.h"
35#include "llvm/ADT/DenseMap.h"
36#include "llvm/ADT/PriorityQueue.h"
37#include "llvm/ADT/STLExtras.h"
38#include "llvm/ADT/SetOperations.h"
39#include "llvm/ADT/SetVector.h"
40#include "llvm/ADT/SmallPtrSet.h"
41#include "llvm/ADT/SmallSet.h"
42#include "llvm/ADT/SmallVector.h"
43#include "llvm/ADT/Statistic.h"
44#include "llvm/ADT/iterator_range.h"
45#include "llvm/Analysis/AliasAnalysis.h"
46#include "llvm/Analysis/MemoryLocation.h"
47#include "llvm/Analysis/OptimizationRemarkEmitter.h"
48#include "llvm/Analysis/ValueTracking.h"
49#include "llvm/CodeGen/DFAPacketizer.h"
50#include "llvm/CodeGen/LiveIntervals.h"
51#include "llvm/CodeGen/MachineBasicBlock.h"
52#include "llvm/CodeGen/MachineFunction.h"
53#include "llvm/CodeGen/MachineFunctionPass.h"
54#include "llvm/CodeGen/MachineInstr.h"
55#include "llvm/CodeGen/MachineInstrBuilder.h"
56#include "llvm/CodeGen/MachineLoopInfo.h"
57#include "llvm/CodeGen/MachineMemOperand.h"
58#include "llvm/CodeGen/MachineOperand.h"
59#include "llvm/CodeGen/MachineRegisterInfo.h"
60#include "llvm/CodeGen/ModuloSchedule.h"
61#include "llvm/CodeGen/Register.h"
62#include "llvm/CodeGen/RegisterClassInfo.h"
63#include "llvm/CodeGen/RegisterPressure.h"
64#include "llvm/CodeGen/ScheduleDAG.h"
65#include "llvm/CodeGen/ScheduleDAGMutation.h"
66#include "llvm/CodeGen/TargetInstrInfo.h"
67#include "llvm/CodeGen/TargetOpcodes.h"
68#include "llvm/CodeGen/TargetPassConfig.h"
69#include "llvm/CodeGen/TargetRegisterInfo.h"
70#include "llvm/CodeGen/TargetSubtargetInfo.h"
71#include "llvm/Config/llvm-config.h"
72#include "llvm/IR/Attributes.h"
73#include "llvm/IR/Function.h"
74#include "llvm/InitializePasses.h"
75#include "llvm/MC/LaneBitmask.h"
76#include "llvm/MC/MCInstrDesc.h"
77#include "llvm/MC/MCInstrItineraries.h"
78#include "llvm/Pass.h"
79#include "llvm/Support/CommandLine.h"
80#include "llvm/Support/Compiler.h"
81#include "llvm/Support/Debug.h"
82#include "llvm/Support/raw_ostream.h"
83#include <algorithm>
84#include <cassert>
85#include <climits>
86#include <cstdint>
87#include <deque>
88#include <functional>
89#include <iomanip>
90#include <iterator>
91#include <map>
92#include <memory>
93#include <sstream>
94#include <tuple>
95#include <utility>
96#include <vector>
97
98using namespace llvm;
99
100#define DEBUG_TYPE "pipeliner"
101
102STATISTIC(NumTrytoPipeline, "Number of loops that we attempt to pipeline");
103STATISTIC(NumPipelined, "Number of loops software pipelined");
104STATISTIC(NumNodeOrderIssues, "Number of node order issues found");
105STATISTIC(NumFailBranch, "Pipeliner abort due to unknown branch");
106STATISTIC(NumFailLoop, "Pipeliner abort due to unsupported loop");
107STATISTIC(NumFailPreheader, "Pipeliner abort due to missing preheader");
108STATISTIC(NumFailLargeMaxMII, "Pipeliner abort due to MaxMII too large");
109STATISTIC(NumFailZeroMII, "Pipeliner abort due to zero MII");
110STATISTIC(NumFailNoSchedule, "Pipeliner abort due to no schedule found");
111STATISTIC(NumFailZeroStage, "Pipeliner abort due to zero stage");
112STATISTIC(NumFailLargeMaxStage, "Pipeliner abort due to too many stages");
113STATISTIC(NumFailTooManyStores, "Pipeliner abort due to too many stores");
114
115/// A command line option to turn software pipelining on or off.
116static cl::opt<bool> EnableSWP("enable-pipeliner", cl::Hidden, cl::init(Val: true),
117 cl::desc("Enable Software Pipelining"));
118
119/// A command line option to enable SWP at -Os.
120static cl::opt<bool> EnableSWPOptSize("enable-pipeliner-opt-size",
121 cl::desc("Enable SWP at Os."), cl::Hidden,
122 cl::init(Val: false));
123
124/// A command line argument to limit minimum initial interval for pipelining.
125static cl::opt<int> SwpMaxMii("pipeliner-max-mii",
126 cl::desc("Size limit for the MII."),
127 cl::Hidden, cl::init(Val: 27));
128
129/// A command line argument to force pipeliner to use specified initial
130/// interval.
131static cl::opt<int> SwpForceII("pipeliner-force-ii",
132 cl::desc("Force pipeliner to use specified II."),
133 cl::Hidden, cl::init(Val: -1));
134
135/// A command line argument to limit the number of stages in the pipeline.
136static cl::opt<int>
137 SwpMaxStages("pipeliner-max-stages",
138 cl::desc("Maximum stages allowed in the generated scheduled."),
139 cl::Hidden, cl::init(Val: 3));
140
141/// A command line option to disable the pruning of chain dependences due to
142/// an unrelated Phi.
143static cl::opt<bool>
144 SwpPruneDeps("pipeliner-prune-deps",
145 cl::desc("Prune dependences between unrelated Phi nodes."),
146 cl::Hidden, cl::init(Val: true));
147
148/// A command line option to disable the pruning of loop carried order
149/// dependences.
150static cl::opt<bool>
151 SwpPruneLoopCarried("pipeliner-prune-loop-carried",
152 cl::desc("Prune loop carried order dependences."),
153 cl::Hidden, cl::init(Val: true));
154
155#ifndef NDEBUG
156static cl::opt<int> SwpLoopLimit("pipeliner-max", cl::Hidden, cl::init(-1));
157#endif
158
159static cl::opt<bool> SwpIgnoreRecMII("pipeliner-ignore-recmii",
160 cl::ReallyHidden,
161 cl::desc("Ignore RecMII"));
162
163static cl::opt<bool> SwpShowResMask("pipeliner-show-mask", cl::Hidden,
164 cl::init(Val: false));
165static cl::opt<bool> SwpDebugResource("pipeliner-dbg-res", cl::Hidden,
166 cl::init(Val: false));
167
168static cl::opt<bool> EmitTestAnnotations(
169 "pipeliner-annotate-for-testing", cl::Hidden, cl::init(Val: false),
170 cl::desc("Instead of emitting the pipelined code, annotate instructions "
171 "with the generated schedule for feeding into the "
172 "-modulo-schedule-test pass"));
173
174static cl::opt<bool> ExperimentalCodeGen(
175 "pipeliner-experimental-cg", cl::Hidden, cl::init(Val: false),
176 cl::desc(
177 "Use the experimental peeling code generator for software pipelining"));
178
179static cl::opt<int> SwpIISearchRange("pipeliner-ii-search-range",
180 cl::desc("Range to search for II"),
181 cl::Hidden, cl::init(Val: 10));
182
183static cl::opt<bool>
184 LimitRegPressure("pipeliner-register-pressure", cl::Hidden, cl::init(Val: false),
185 cl::desc("Limit register pressure of scheduled loop"));
186
187static cl::opt<int>
188 RegPressureMargin("pipeliner-register-pressure-margin", cl::Hidden,
189 cl::init(Val: 5),
190 cl::desc("Margin representing the unused percentage of "
191 "the register pressure limit"));
192
193static cl::opt<bool>
194 MVECodeGen("pipeliner-mve-cg", cl::Hidden, cl::init(Val: false),
195 cl::desc("Use the MVE code generator for software pipelining"));
196
197/// A command line argument to limit the number of store instructions in the
198/// target basic block.
199static cl::opt<unsigned> SwpMaxNumStores(
200 "pipeliner-max-num-stores",
201 cl::desc("Maximum number of stores allwed in the target loop."), cl::Hidden,
202 cl::init(Val: 200));
203
204// A command line option to enable the CopyToPhi DAG mutation.
205cl::opt<bool>
206 llvm::SwpEnableCopyToPhi("pipeliner-enable-copytophi", cl::ReallyHidden,
207 cl::init(Val: true),
208 cl::desc("Enable CopyToPhi DAG Mutation"));
209
210/// A command line argument to force pipeliner to use specified issue
211/// width.
212cl::opt<int> llvm::SwpForceIssueWidth(
213 "pipeliner-force-issue-width",
214 cl::desc("Force pipeliner to use specified issue width."), cl::Hidden,
215 cl::init(Val: -1));
216
217/// A command line argument to set the window scheduling option.
218static cl::opt<WindowSchedulingFlag> WindowSchedulingOption(
219 "window-sched", cl::Hidden, cl::init(Val: WindowSchedulingFlag::WS_On),
220 cl::desc("Set how to use window scheduling algorithm."),
221 cl::values(clEnumValN(WindowSchedulingFlag::WS_Off, "off",
222 "Turn off window algorithm."),
223 clEnumValN(WindowSchedulingFlag::WS_On, "on",
224 "Use window algorithm after SMS algorithm fails."),
225 clEnumValN(WindowSchedulingFlag::WS_Force, "force",
226 "Use window algorithm instead of SMS algorithm.")));
227
228unsigned SwingSchedulerDAG::Circuits::MaxPaths = 5;
229char MachinePipeliner::ID = 0;
230#ifndef NDEBUG
231int MachinePipeliner::NumTries = 0;
232#endif
233char &llvm::MachinePipelinerID = MachinePipeliner::ID;
234
235INITIALIZE_PASS_BEGIN(MachinePipeliner, DEBUG_TYPE,
236 "Modulo Software Pipelining", false, false)
237INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
238INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
239INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
240INITIALIZE_PASS_DEPENDENCY(MachineRegisterClassInfoWrapperPass)
241INITIALIZE_PASS_END(MachinePipeliner, DEBUG_TYPE,
242 "Modulo Software Pipelining", false, false)
243
244namespace {
245
246/// This class holds an SUnit corresponding to a memory operation and other
247/// information related to the instruction.
248struct SUnitWithMemInfo {
249 SUnit *SU;
250 SmallVector<const Value *, 2> UnderlyingObjs;
251
252 /// The value of a memory operand.
253 const Value *MemOpValue = nullptr;
254
255 /// The offset of a memory operand.
256 int64_t MemOpOffset = 0;
257
258 AAMDNodes AATags;
259
260 /// True if all the underlying objects are identified.
261 bool IsAllIdentified = false;
262
263 SUnitWithMemInfo(SUnit *SU);
264
265 bool isTriviallyDisjoint(const SUnitWithMemInfo &Other) const;
266
267 bool isUnknown() const { return MemOpValue == nullptr; }
268
269private:
270 bool getUnderlyingObjects();
271};
272
273/// Add loop-carried chain dependencies. This class handles the same type of
274/// dependencies added by `ScheduleDAGInstrs::buildSchedGraph`, but takes into
275/// account dependencies across iterations.
276class LoopCarriedOrderDepsTracker {
277 // Type of instruction that is relevant to order-dependencies
278 enum class InstrTag {
279 Barrier = 0, ///< A barrier event instruction.
280 LoadOrStore = 1, ///< An instruction that may load or store memory, but is
281 ///< not a barrier event.
282 FPExceptions = 2, ///< An instruction that does not match above, but may
283 ///< raise floatin-point exceptions.
284 };
285
286 struct TaggedSUnit : PointerIntPair<SUnit *, 2> {
287 TaggedSUnit(SUnit *SU, InstrTag Tag)
288 : PointerIntPair<SUnit *, 2>(SU, unsigned(Tag)) {}
289
290 InstrTag getTag() const { return InstrTag(getInt()); }
291 };
292
293 /// Holds instructions that may form loop-carried order-dependencies, but not
294 /// global barriers.
295 struct NoBarrierInstsChunk {
296 SmallVector<SUnitWithMemInfo, 4> Loads;
297 SmallVector<SUnitWithMemInfo, 4> Stores;
298 SmallVector<SUnitWithMemInfo, 1> FPExceptions;
299
300 void append(SUnit *SU);
301 };
302
303 SwingSchedulerDAG *DAG;
304 BatchAAResults *BAA;
305 std::vector<SUnit> &SUnits;
306
307 /// The size of SUnits, for convenience.
308 const unsigned N;
309
310 /// Loop-carried Edges.
311 std::vector<BitVector> LoopCarried;
312
313 /// Instructions related to chain dependencies. They are one of the
314 /// following:
315 ///
316 /// 1. Barrier event.
317 /// 2. Load, but neither a barrier event, invariant load, nor may load trap
318 /// value.
319 /// 3. Store, but not a barrier event.
320 /// 4. None of them, but may raise floating-point exceptions.
321 ///
322 /// This is used when analyzing loop-carried dependencies that access global
323 /// barrier instructions.
324 std::vector<TaggedSUnit> TaggedSUnits;
325
326 const TargetInstrInfo *TII = nullptr;
327 const TargetRegisterInfo *TRI = nullptr;
328
329public:
330 LoopCarriedOrderDepsTracker(SwingSchedulerDAG *SSD, BatchAAResults *BAA,
331 const TargetInstrInfo *TII,
332 const TargetRegisterInfo *TRI);
333
334 /// The main function to compute loop-carried order-dependencies.
335 void computeDependencies();
336
337 const BitVector &getLoopCarried(unsigned Idx) const {
338 return LoopCarried[Idx];
339 }
340
341private:
342 /// Tags to \p SU if the instruction may affect the order-dependencies.
343 std::optional<InstrTag> getInstrTag(SUnit *SU) const;
344
345 void addLoopCarriedDepenenciesForChunks(const NoBarrierInstsChunk &From,
346 const NoBarrierInstsChunk &To);
347
348 /// Add a loop-carried order dependency between \p Src and \p Dst if we
349 /// cannot prove they are independent.
350 void addDependenciesBetweenSUs(const SUnitWithMemInfo &Src,
351 const SUnitWithMemInfo &Dst);
352
353 void computeDependenciesAux();
354
355 void setLoopCarriedDep(const SUnit *Src, const SUnit *Dst) {
356 LoopCarried[Src->NodeNum].set(Dst->NodeNum);
357 }
358};
359
360} // end anonymous namespace
361
362/// The "main" function for implementing Swing Modulo Scheduling.
363bool MachinePipeliner::runOnMachineFunction(MachineFunction &mf) {
364 if (skipFunction(F: mf.getFunction()))
365 return false;
366
367 if (!EnableSWP)
368 return false;
369
370 if (mf.getFunction().getAttributes().hasFnAttr(Kind: Attribute::OptimizeForSize) &&
371 !EnableSWPOptSize.getPosition())
372 return false;
373
374 if (!mf.getSubtarget().enableMachinePipeliner())
375 return false;
376
377 // Cannot pipeline loops without instruction itineraries if we are using
378 // DFA for the pipeliner.
379 if (mf.getSubtarget().useDFAforSMS() &&
380 (!mf.getSubtarget().getInstrItineraryData() ||
381 mf.getSubtarget().getInstrItineraryData()->isEmpty()))
382 return false;
383
384 MF = &mf;
385 MLI = &getAnalysis<MachineLoopInfoWrapperPass>().getLI();
386 ORE = &getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
387 RegClassInfo = &getAnalysis<MachineRegisterClassInfoWrapperPass>().getRCI();
388 TII = MF->getSubtarget().getInstrInfo();
389
390 for (const auto &L : *MLI)
391 scheduleLoop(L&: *L);
392
393 return false;
394}
395
396/// Attempt to perform the SMS algorithm on the specified loop. This function is
397/// the main entry point for the algorithm. The function identifies candidate
398/// loops, calculates the minimum initiation interval, and attempts to schedule
399/// the loop.
400bool MachinePipeliner::scheduleLoop(MachineLoop &L) {
401 bool Changed = false;
402 for (const auto &InnerLoop : L)
403 Changed |= scheduleLoop(L&: *InnerLoop);
404
405#ifndef NDEBUG
406 // Stop trying after reaching the limit (if any).
407 int Limit = SwpLoopLimit;
408 if (Limit >= 0) {
409 if (NumTries >= SwpLoopLimit)
410 return Changed;
411 NumTries++;
412 }
413#endif
414
415 setPragmaPipelineOptions(L);
416 if (!canPipelineLoop(L)) {
417 LLVM_DEBUG(dbgs() << "\n!!! Can not pipeline loop.\n");
418 ORE->emit(RemarkBuilder: [&]() {
419 return MachineOptimizationRemarkMissed(DEBUG_TYPE, "canPipelineLoop",
420 L.getStartLoc(), L.getHeader())
421 << "Failed to pipeline loop";
422 });
423
424 LI.LoopPipelinerInfo.reset();
425 return Changed;
426 }
427
428 ++NumTrytoPipeline;
429 if (useSwingModuloScheduler())
430 Changed = swingModuloScheduler(L);
431
432 if (useWindowScheduler(Changed))
433 Changed = runWindowScheduler(L);
434
435 LI.LoopPipelinerInfo.reset();
436 return Changed;
437}
438
439void MachinePipeliner::setPragmaPipelineOptions(MachineLoop &L) {
440 // Reset the pragma for the next loop in iteration.
441 disabledByPragma = false;
442 II_setByPragma = 0;
443
444 MachineBasicBlock *LBLK = L.getTopBlock();
445
446 if (LBLK == nullptr)
447 return;
448
449 const BasicBlock *BBLK = LBLK->getBasicBlock();
450 if (BBLK == nullptr)
451 return;
452
453 const Instruction *TI = BBLK->getTerminator();
454 if (TI == nullptr)
455 return;
456
457 MDNode *LoopID = TI->getMetadata(KindID: LLVMContext::MD_loop);
458 if (LoopID == nullptr)
459 return;
460
461 assert(LoopID->getNumOperands() > 0 && "requires atleast one operand");
462 assert(LoopID->getOperand(0) == LoopID && "invalid loop");
463
464 for (const MDOperand &MDO : llvm::drop_begin(RangeOrContainer: LoopID->operands())) {
465 MDNode *MD = dyn_cast<MDNode>(Val: MDO);
466
467 if (MD == nullptr)
468 continue;
469
470 MDString *S = dyn_cast<MDString>(Val: MD->getOperand(I: 0));
471
472 if (S == nullptr)
473 continue;
474
475 if (S->getString() == "llvm.loop.pipeline.initiationinterval") {
476 assert(MD->getNumOperands() == 2 &&
477 "Pipeline initiation interval hint metadata should have two operands.");
478 II_setByPragma =
479 mdconst::extract<ConstantInt>(MD: MD->getOperand(I: 1))->getZExtValue();
480 assert(II_setByPragma >= 1 && "Pipeline initiation interval must be positive.");
481 } else if (S->getString() == "llvm.loop.pipeline.disable") {
482 disabledByPragma = true;
483 }
484 }
485}
486
487/// Depth-first search to detect cycles among PHI dependencies.
488/// Returns true if a cycle is detected within the PHI-only subgraph.
489static bool hasPHICycleDFS(
490 unsigned Reg, const DenseMap<unsigned, SmallVector<unsigned, 2>> &PhiDeps,
491 SmallSet<unsigned, 8> &Visited, SmallSet<unsigned, 8> &RecStack) {
492
493 // If Reg is not a PHI-def it cannot contribute to a PHI cycle.
494 auto It = PhiDeps.find(Val: Reg);
495 if (It == PhiDeps.end())
496 return false;
497
498 if (RecStack.count(V: Reg))
499 return true; // backedge.
500 if (Visited.count(V: Reg))
501 return false;
502
503 Visited.insert(V: Reg);
504 RecStack.insert(V: Reg);
505
506 for (unsigned Dep : It->second) {
507 if (hasPHICycleDFS(Reg: Dep, PhiDeps, Visited, RecStack))
508 return true;
509 }
510
511 RecStack.erase(V: Reg);
512 return false;
513}
514
515static bool hasPHICycle(const MachineBasicBlock *LoopHeader,
516 const MachineRegisterInfo &MRI) {
517 DenseMap<unsigned, SmallVector<unsigned, 2>> PhiDeps;
518
519 // Collect PHI nodes and their dependencies.
520 for (const MachineInstr &MI : LoopHeader->phis()) {
521 unsigned DefReg = MI.getOperand(i: 0).getReg();
522 auto Ins = PhiDeps.try_emplace(Key: DefReg).first;
523
524 // PHI operands are (Reg, MBB) pairs starting at index 1.
525 for (unsigned I = 1; I < MI.getNumOperands(); I += 2)
526 Ins->second.push_back(Elt: MI.getOperand(i: I).getReg());
527 }
528
529 // DFS to detect cycles among PHI nodes.
530 SmallSet<unsigned, 8> Visited, RecStack;
531
532 // Start DFS from each PHI-def.
533 for (const auto &KV : PhiDeps) {
534 unsigned Reg = KV.first;
535 if (hasPHICycleDFS(Reg, PhiDeps, Visited, RecStack))
536 return true;
537 }
538
539 return false;
540}
541
542/// Return true if the loop can be software pipelined. The algorithm is
543/// restricted to loops with a single basic block. Make sure that the
544/// branch in the loop can be analyzed.
545bool MachinePipeliner::canPipelineLoop(MachineLoop &L) {
546 if (L.getNumBlocks() != 1) {
547 ORE->emit(RemarkBuilder: [&]() {
548 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
549 L.getStartLoc(), L.getHeader())
550 << "Not a single basic block: "
551 << ore::NV("NumBlocks", L.getNumBlocks());
552 });
553 return false;
554 }
555
556 if (hasPHICycle(LoopHeader: L.getHeader(), MRI: MF->getRegInfo())) {
557 LLVM_DEBUG(dbgs() << "Cannot pipeline loop due to PHI cycle\n");
558 return false;
559 }
560
561 if (disabledByPragma) {
562 ORE->emit(RemarkBuilder: [&]() {
563 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
564 L.getStartLoc(), L.getHeader())
565 << "Disabled by Pragma.";
566 });
567 return false;
568 }
569
570 // Check if the branch can't be understood because we can't do pipelining
571 // if that's the case.
572 LI.TBB = nullptr;
573 LI.FBB = nullptr;
574 LI.BrCond.clear();
575 if (TII->analyzeBranch(MBB&: *L.getHeader(), TBB&: LI.TBB, FBB&: LI.FBB, Cond&: LI.BrCond)) {
576 LLVM_DEBUG(dbgs() << "Unable to analyzeBranch, can NOT pipeline Loop\n");
577 NumFailBranch++;
578 ORE->emit(RemarkBuilder: [&]() {
579 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
580 L.getStartLoc(), L.getHeader())
581 << "The branch can't be understood";
582 });
583 return false;
584 }
585
586 LI.LoopInductionVar = nullptr;
587 LI.LoopCompare = nullptr;
588 LI.LoopPipelinerInfo = TII->analyzeLoopForPipelining(LoopBB: L.getTopBlock());
589 if (!LI.LoopPipelinerInfo) {
590 LLVM_DEBUG(dbgs() << "Unable to analyzeLoop, can NOT pipeline Loop\n");
591 NumFailLoop++;
592 ORE->emit(RemarkBuilder: [&]() {
593 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
594 L.getStartLoc(), L.getHeader())
595 << "The loop structure is not supported";
596 });
597 return false;
598 }
599
600 if (!L.getLoopPreheader()) {
601 LLVM_DEBUG(dbgs() << "Preheader not found, can NOT pipeline Loop\n");
602 NumFailPreheader++;
603 ORE->emit(RemarkBuilder: [&]() {
604 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
605 L.getStartLoc(), L.getHeader())
606 << "No loop preheader found";
607 });
608 return false;
609 }
610
611 unsigned NumStores = 0;
612 for (MachineInstr &MI : *L.getHeader())
613 if (MI.mayStore())
614 ++NumStores;
615 if (NumStores > SwpMaxNumStores) {
616 LLVM_DEBUG(dbgs() << "Too many stores\n");
617 NumFailTooManyStores++;
618 ORE->emit(RemarkBuilder: [&]() {
619 return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
620 L.getStartLoc(), L.getHeader())
621 << "Too many store instructions in the loop: "
622 << ore::NV("NumStores", NumStores) << " > "
623 << ore::NV("SwpMaxNumStores", SwpMaxNumStores) << ".";
624 });
625 return false;
626 }
627
628 // Remove any subregisters from inputs to phi nodes.
629 preprocessPhiNodes(B&: *L.getHeader());
630 return true;
631}
632
633void MachinePipeliner::preprocessPhiNodes(MachineBasicBlock &B) {
634 MachineRegisterInfo &MRI = MF->getRegInfo();
635 SlotIndexes &Slots =
636 *getAnalysis<LiveIntervalsWrapperPass>().getLIS().getSlotIndexes();
637
638 for (MachineInstr &PI : B.phis()) {
639 MachineOperand &DefOp = PI.getOperand(i: 0);
640 assert(DefOp.getSubReg() == 0);
641 auto *RC = MRI.getRegClass(Reg: DefOp.getReg());
642
643 for (unsigned i = 1, n = PI.getNumOperands(); i != n; i += 2) {
644 MachineOperand &RegOp = PI.getOperand(i);
645 if (RegOp.getSubReg() == 0)
646 continue;
647
648 // If the operand uses a subregister, replace it with a new register
649 // without subregisters, and generate a copy to the new register.
650 Register NewReg = MRI.createVirtualRegister(RegClass: RC);
651 MachineBasicBlock &PredB = *PI.getOperand(i: i+1).getMBB();
652 MachineBasicBlock::iterator At = PredB.getFirstTerminator();
653 const DebugLoc &DL = PredB.findDebugLoc(MBBI: At);
654 auto Copy = BuildMI(BB&: PredB, I: At, MIMD: DL, MCID: TII->get(Opcode: TargetOpcode::COPY), DestReg: NewReg)
655 .addReg(RegNo: RegOp.getReg(), Flags: getRegState(RegOp),
656 SubReg: RegOp.getSubReg());
657 Slots.insertMachineInstrInMaps(MI&: *Copy);
658 RegOp.setReg(NewReg);
659 RegOp.setSubReg(0);
660 }
661 }
662}
663
664/// The SMS algorithm consists of the following main steps:
665/// 1. Computation and analysis of the dependence graph.
666/// 2. Ordering of the nodes (instructions).
667/// 3. Attempt to Schedule the loop.
668bool MachinePipeliner::swingModuloScheduler(MachineLoop &L) {
669 assert(L.getBlocks().size() == 1 && "SMS works on single blocks only.");
670
671 AliasAnalysis *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
672 SwingSchedulerDAG SMS(
673 *this, L, getAnalysis<LiveIntervalsWrapperPass>().getLIS(), *RegClassInfo,
674 II_setByPragma, LI.LoopPipelinerInfo.get(), AA);
675
676 MachineBasicBlock *MBB = L.getHeader();
677 // The kernel should not include any terminator instructions. These
678 // will be added back later.
679 SMS.startBlock(BB: MBB);
680
681 // Compute the number of 'real' instructions in the basic block by
682 // ignoring terminators.
683 unsigned size = MBB->size();
684 for (MachineBasicBlock::iterator I = MBB->getFirstTerminator(),
685 E = MBB->instr_end();
686 I != E; ++I, --size)
687 ;
688
689 SMS.enterRegion(bb: MBB, begin: MBB->begin(), end: MBB->getFirstTerminator(), regioninstrs: size);
690 SMS.schedule();
691 SMS.exitRegion();
692
693 SMS.finishBlock();
694 return SMS.hasNewSchedule();
695}
696
697void MachinePipeliner::getAnalysisUsage(AnalysisUsage &AU) const {
698 AU.addRequired<AAResultsWrapperPass>();
699 AU.addPreserved<AAResultsWrapperPass>();
700 AU.addRequired<MachineLoopInfoWrapperPass>();
701 AU.addRequired<LiveIntervalsWrapperPass>();
702 AU.addRequired<MachineOptimizationRemarkEmitterPass>();
703 AU.addRequired<MachineRegisterClassInfoWrapperPass>();
704 AU.addPreserved<MachineRegisterClassInfoWrapperPass>();
705 AU.addRequired<TargetPassConfig>();
706 MachineFunctionPass::getAnalysisUsage(AU);
707}
708
709bool MachinePipeliner::runWindowScheduler(MachineLoop &L) {
710 MachineSchedContext Context;
711 Context.MF = MF;
712 Context.MLI = MLI;
713 Context.TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
714 Context.AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
715 Context.LIS = &getAnalysis<LiveIntervalsWrapperPass>().getLIS();
716 Context.RegClassInfo =
717 &getAnalysis<MachineRegisterClassInfoWrapperPass>().getRCI();
718 WindowScheduler WS(&Context, L);
719 return WS.run();
720}
721
722bool MachinePipeliner::useSwingModuloScheduler() {
723 // SwingModuloScheduler does not work when WindowScheduler is forced.
724 return WindowSchedulingOption != WindowSchedulingFlag::WS_Force;
725}
726
727bool MachinePipeliner::useWindowScheduler(bool Changed) {
728 // WindowScheduler does not work for following cases:
729 // 1. when it is off.
730 // 2. when SwingModuloScheduler is successfully scheduled.
731 // 3. when pragma II is enabled.
732 if (II_setByPragma) {
733 LLVM_DEBUG(dbgs() << "Window scheduling is disabled when "
734 "llvm.loop.pipeline.initiationinterval is set.\n");
735 return false;
736 }
737
738 return WindowSchedulingOption == WindowSchedulingFlag::WS_Force ||
739 (WindowSchedulingOption == WindowSchedulingFlag::WS_On && !Changed);
740}
741
742void SwingSchedulerDAG::setMII(unsigned ResMII, unsigned RecMII) {
743 if (SwpForceII > 0)
744 MII = SwpForceII;
745 else if (II_setByPragma > 0)
746 MII = II_setByPragma;
747 else
748 MII = std::max(a: ResMII, b: RecMII);
749}
750
751void SwingSchedulerDAG::setMAX_II() {
752 if (SwpForceII > 0)
753 MAX_II = SwpForceII;
754 else if (II_setByPragma > 0)
755 MAX_II = II_setByPragma;
756 else
757 MAX_II = MII + SwpIISearchRange;
758}
759
760/// We override the schedule function in ScheduleDAGInstrs to implement the
761/// scheduling part of the Swing Modulo Scheduling algorithm.
762void SwingSchedulerDAG::schedule() {
763 buildSchedGraph(AA);
764 const LoopCarriedEdges LCE = addLoopCarriedDependences();
765 updatePhiDependences();
766 Topo.InitDAGTopologicalSorting();
767 changeDependences();
768 postProcessDAG();
769 DDG = std::make_unique<SwingSchedulerDDG>(args&: SUnits, args: &EntrySU, args: &ExitSU, args: LCE);
770 LLVM_DEBUG({
771 dump();
772 dbgs() << "===== Loop Carried Edges Begin =====\n";
773 for (SUnit &SU : SUnits)
774 LCE.dump(&SU, TRI, &MRI);
775 dbgs() << "===== Loop Carried Edges End =====\n";
776 });
777
778 NodeSetType NodeSets;
779 findCircuits(NodeSets);
780 NodeSetType Circuits = NodeSets;
781
782 // Calculate the MII.
783 unsigned ResMII = calculateResMII();
784 unsigned RecMII = calculateRecMII(RecNodeSets&: NodeSets);
785
786 fuseRecs(NodeSets);
787
788 // This flag is used for testing and can cause correctness problems.
789 if (SwpIgnoreRecMII)
790 RecMII = 0;
791
792 setMII(ResMII, RecMII);
793 setMAX_II();
794
795 LLVM_DEBUG(dbgs() << "MII = " << MII << " MAX_II = " << MAX_II
796 << " (rec=" << RecMII << ", res=" << ResMII << ")\n");
797
798 // Can't schedule a loop without a valid MII.
799 if (MII == 0) {
800 LLVM_DEBUG(dbgs() << "Invalid Minimal Initiation Interval: 0\n");
801 NumFailZeroMII++;
802 Pass.ORE->emit(RemarkBuilder: [&]() {
803 return MachineOptimizationRemarkAnalysis(
804 DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
805 << "Invalid Minimal Initiation Interval: 0";
806 });
807 return;
808 }
809
810 // Don't pipeline large loops.
811 if (SwpMaxMii != -1 && (int)MII > SwpMaxMii) {
812 LLVM_DEBUG(dbgs() << "MII > " << SwpMaxMii
813 << ", we don't pipeline large loops\n");
814 NumFailLargeMaxMII++;
815 Pass.ORE->emit(RemarkBuilder: [&]() {
816 return MachineOptimizationRemarkAnalysis(
817 DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
818 << "Minimal Initiation Interval too large: "
819 << ore::NV("MII", (int)MII) << " > "
820 << ore::NV("SwpMaxMii", SwpMaxMii) << "."
821 << "Refer to -pipeliner-max-mii.";
822 });
823 return;
824 }
825
826 computeNodeFunctions(NodeSets);
827
828 registerPressureFilter(NodeSets);
829
830 colocateNodeSets(NodeSets);
831
832 checkNodeSets(NodeSets);
833
834 LLVM_DEBUG({
835 for (auto &I : NodeSets) {
836 dbgs() << " Rec NodeSet ";
837 I.dump();
838 }
839 });
840
841 llvm::stable_sort(Range&: NodeSets, C: std::greater<NodeSet>());
842
843 groupRemainingNodes(NodeSets);
844
845 removeDuplicateNodes(NodeSets);
846
847 LLVM_DEBUG({
848 for (auto &I : NodeSets) {
849 dbgs() << " NodeSet ";
850 I.dump();
851 }
852 });
853
854 computeNodeOrder(NodeSets);
855
856 // check for node order issues
857 checkValidNodeOrder(Circuits);
858
859 SMSchedule Schedule(Pass.MF, this);
860 Scheduled = schedulePipeline(Schedule);
861
862 if (!Scheduled){
863 LLVM_DEBUG(dbgs() << "No schedule found, return\n");
864 NumFailNoSchedule++;
865 Pass.ORE->emit(RemarkBuilder: [&]() {
866 return MachineOptimizationRemarkAnalysis(
867 DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
868 << "Unable to find schedule";
869 });
870 return;
871 }
872
873 unsigned numStages = Schedule.getMaxStageCount();
874 // No need to generate pipeline if there are no overlapped iterations.
875 if (numStages == 0) {
876 LLVM_DEBUG(dbgs() << "No overlapped iterations, skip.\n");
877 NumFailZeroStage++;
878 Pass.ORE->emit(RemarkBuilder: [&]() {
879 return MachineOptimizationRemarkAnalysis(
880 DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
881 << "No need to pipeline - no overlapped iterations in schedule.";
882 });
883 return;
884 }
885 // Check that the maximum stage count is less than user-defined limit.
886 if (SwpMaxStages > -1 && (int)numStages > SwpMaxStages) {
887 LLVM_DEBUG(dbgs() << "numStages:" << numStages << ">" << SwpMaxStages
888 << " : too many stages, abort\n");
889 NumFailLargeMaxStage++;
890 Pass.ORE->emit(RemarkBuilder: [&]() {
891 return MachineOptimizationRemarkAnalysis(
892 DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
893 << "Too many stages in schedule: "
894 << ore::NV("numStages", (int)numStages) << " > "
895 << ore::NV("SwpMaxStages", SwpMaxStages)
896 << ". Refer to -pipeliner-max-stages.";
897 });
898 return;
899 }
900
901 Pass.ORE->emit(RemarkBuilder: [&]() {
902 return MachineOptimizationRemark(DEBUG_TYPE, "schedule", Loop.getStartLoc(),
903 Loop.getHeader())
904 << "Pipelined succesfully!";
905 });
906
907 // Generate the schedule as a ModuloSchedule.
908 DenseMap<MachineInstr *, int> Cycles, Stages;
909 std::vector<MachineInstr *> OrderedInsts;
910 for (int Cycle = Schedule.getFirstCycle(); Cycle <= Schedule.getFinalCycle();
911 ++Cycle) {
912 for (SUnit *SU : Schedule.getInstructions(cycle: Cycle)) {
913 OrderedInsts.push_back(x: SU->getInstr());
914 Cycles[SU->getInstr()] = Cycle;
915 Stages[SU->getInstr()] = Schedule.stageScheduled(SU);
916 }
917 }
918 DenseMap<MachineInstr *, std::pair<Register, int64_t>> NewInstrChanges;
919 for (auto &KV : NewMIs) {
920 Cycles[KV.first] = Cycles[KV.second];
921 Stages[KV.first] = Stages[KV.second];
922 NewInstrChanges[KV.first] = InstrChanges[getSUnit(MI: KV.first)];
923 }
924
925 ModuloSchedule MS(MF, &Loop, std::move(OrderedInsts), std::move(Cycles),
926 std::move(Stages));
927 if (EmitTestAnnotations) {
928 assert(NewInstrChanges.empty() &&
929 "Cannot serialize a schedule with InstrChanges!");
930 ModuloScheduleTestAnnotater MSTI(MF, MS);
931 MSTI.annotate();
932 return;
933 }
934 // The experimental code generator can't work if there are InstChanges.
935 if (ExperimentalCodeGen && NewInstrChanges.empty()) {
936 PeelingModuloScheduleExpander MSE(MF, MS, &LIS);
937 MSE.expand();
938 } else if (MVECodeGen && NewInstrChanges.empty() &&
939 LoopPipelinerInfo->isMVEExpanderSupported() &&
940 ModuloScheduleExpanderMVE::canApply(L&: Loop)) {
941 ModuloScheduleExpanderMVE MSE(MF, MS, LIS);
942 MSE.expand();
943 } else {
944 ModuloScheduleExpander MSE(MF, MS, LIS, std::move(NewInstrChanges));
945 MSE.expand();
946 MSE.cleanup();
947 }
948 ++NumPipelined;
949}
950
951/// Clean up after the software pipeliner runs.
952void SwingSchedulerDAG::finishBlock() {
953 for (auto &KV : NewMIs)
954 MF.deleteMachineInstr(MI: KV.second);
955 NewMIs.clear();
956
957 // Call the superclass.
958 ScheduleDAGInstrs::finishBlock();
959}
960
961/// Return the register values for the operands of a Phi instruction.
962/// This function assume the instruction is a Phi.
963static void getPhiRegs(MachineInstr &Phi, MachineBasicBlock *Loop,
964 Register &InitVal, Register &LoopVal) {
965 assert(Phi.isPHI() && "Expecting a Phi.");
966
967 InitVal = Register();
968 LoopVal = Register();
969 for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
970 if (Phi.getOperand(i: i + 1).getMBB() != Loop)
971 InitVal = Phi.getOperand(i).getReg();
972 else
973 LoopVal = Phi.getOperand(i).getReg();
974
975 assert(InitVal && LoopVal && "Unexpected Phi structure.");
976}
977
978/// Return the Phi register value that comes the loop block.
979static Register getLoopPhiReg(const MachineInstr &Phi,
980 const MachineBasicBlock *LoopBB) {
981 for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
982 if (Phi.getOperand(i: i + 1).getMBB() == LoopBB)
983 return Phi.getOperand(i).getReg();
984 return Register();
985}
986
987/// Return true if SUb can be reached from SUa following the chain edges.
988static bool isSuccOrder(SUnit *SUa, SUnit *SUb) {
989 SmallPtrSet<SUnit *, 8> Visited;
990 SmallVector<SUnit *, 8> Worklist;
991 Worklist.push_back(Elt: SUa);
992 while (!Worklist.empty()) {
993 const SUnit *SU = Worklist.pop_back_val();
994 for (const auto &SI : SU->Succs) {
995 SUnit *SuccSU = SI.getSUnit();
996 if (SI.getKind() == SDep::Order) {
997 if (Visited.count(Ptr: SuccSU))
998 continue;
999 if (SuccSU == SUb)
1000 return true;
1001 Worklist.push_back(Elt: SuccSU);
1002 Visited.insert(Ptr: SuccSU);
1003 }
1004 }
1005 }
1006 return false;
1007}
1008
1009SUnitWithMemInfo::SUnitWithMemInfo(SUnit *SU) : SU(SU) {
1010 if (!getUnderlyingObjects())
1011 return;
1012 for (const Value *Obj : UnderlyingObjs)
1013 if (!isIdentifiedObject(V: Obj)) {
1014 IsAllIdentified = false;
1015 break;
1016 }
1017}
1018
1019bool SUnitWithMemInfo::isTriviallyDisjoint(
1020 const SUnitWithMemInfo &Other) const {
1021 // If all underlying objects are identified objects and there is no overlap
1022 // between them, then these two instructions are disjoint.
1023 if (!IsAllIdentified || !Other.IsAllIdentified)
1024 return false;
1025 for (const Value *Obj : UnderlyingObjs)
1026 if (llvm::is_contained(Range: Other.UnderlyingObjs, Element: Obj))
1027 return false;
1028 return true;
1029}
1030
1031/// Collect the underlying objects for the memory references of an instruction.
1032/// This function calls the code in ValueTracking, but first checks that the
1033/// instruction has a memory operand.
1034/// Returns false if we cannot find the underlying objects.
1035bool SUnitWithMemInfo::getUnderlyingObjects() {
1036 const MachineInstr *MI = SU->getInstr();
1037 if (!MI->hasOneMemOperand())
1038 return false;
1039 MachineMemOperand *MM = *MI->memoperands_begin();
1040 if (!MM->getValue())
1041 return false;
1042 MemOpValue = MM->getValue();
1043 MemOpOffset = MM->getOffset();
1044 llvm::getUnderlyingObjects(V: MemOpValue, Objects&: UnderlyingObjs);
1045
1046 // TODO: A no alias scope may be valid only in a single iteration. In this
1047 // case we need to peel off it like LoopAccessAnalysis does.
1048 AATags = MM->getAAInfo();
1049 return true;
1050}
1051
1052/// Returns true if there is a loop-carried order dependency from \p Src to \p
1053/// Dst.
1054static bool hasLoopCarriedMemDep(const SUnitWithMemInfo &Src,
1055 const SUnitWithMemInfo &Dst,
1056 BatchAAResults &BAA,
1057 const TargetInstrInfo *TII,
1058 const TargetRegisterInfo *TRI,
1059 const SwingSchedulerDAG *SSD) {
1060 if (Src.isTriviallyDisjoint(Other: Dst))
1061 return false;
1062 if (isSuccOrder(SUa: Src.SU, SUb: Dst.SU))
1063 return false;
1064
1065 MachineInstr &SrcMI = *Src.SU->getInstr();
1066 MachineInstr &DstMI = *Dst.SU->getInstr();
1067
1068 if (!SSD->mayOverlapInLaterIter(BaseMI: &SrcMI, OtherMI: &DstMI))
1069 return false;
1070
1071 // Second, the more expensive check that uses alias analysis on the
1072 // base registers. If they alias, and the load offset is less than
1073 // the store offset, the mark the dependence as loop carried.
1074 if (Src.isUnknown() || Dst.isUnknown())
1075 return true;
1076 if (Src.MemOpValue == Dst.MemOpValue && Src.MemOpOffset <= Dst.MemOpOffset)
1077 return true;
1078
1079 if (BAA.isNoAlias(
1080 LocA: MemoryLocation::getBeforeOrAfter(Ptr: Src.MemOpValue, AATags: Src.AATags),
1081 LocB: MemoryLocation::getBeforeOrAfter(Ptr: Dst.MemOpValue, AATags: Dst.AATags)))
1082 return false;
1083
1084 // AliasAnalysis sometimes gives up on following the underlying
1085 // object. In such a case, separate checks for underlying objects may
1086 // prove that there are no aliases between two accesses.
1087 for (const Value *SrcObj : Src.UnderlyingObjs)
1088 for (const Value *DstObj : Dst.UnderlyingObjs)
1089 if (!BAA.isNoAlias(LocA: MemoryLocation::getBeforeOrAfter(Ptr: SrcObj, AATags: Src.AATags),
1090 LocB: MemoryLocation::getBeforeOrAfter(Ptr: DstObj, AATags: Dst.AATags)))
1091 return true;
1092
1093 return false;
1094}
1095
1096void LoopCarriedOrderDepsTracker::NoBarrierInstsChunk::append(SUnit *SU) {
1097 const MachineInstr *MI = SU->getInstr();
1098 if (MI->mayStore())
1099 Stores.emplace_back(Args&: SU);
1100 else if (MI->mayLoad())
1101 Loads.emplace_back(Args&: SU);
1102 else if (MI->mayRaiseFPException())
1103 FPExceptions.emplace_back(Args&: SU);
1104 else
1105 llvm_unreachable("Unexpected instruction type.");
1106}
1107
1108LoopCarriedOrderDepsTracker::LoopCarriedOrderDepsTracker(
1109 SwingSchedulerDAG *SSD, BatchAAResults *BAA, const TargetInstrInfo *TII,
1110 const TargetRegisterInfo *TRI)
1111 : DAG(SSD), BAA(BAA), SUnits(DAG->SUnits), N(SUnits.size()),
1112 LoopCarried(N, BitVector(N)), TII(TII), TRI(TRI) {}
1113
1114void LoopCarriedOrderDepsTracker::computeDependencies() {
1115 // Traverse all instructions and extract only what we are targetting.
1116 for (auto &SU : SUnits) {
1117 auto Tagged = getInstrTag(SU: &SU);
1118
1119 // This instruction has no loop-carried order-dependencies.
1120 if (!Tagged)
1121 continue;
1122 TaggedSUnits.emplace_back(args: &SU, args&: *Tagged);
1123 }
1124
1125 computeDependenciesAux();
1126}
1127
1128std::optional<LoopCarriedOrderDepsTracker::InstrTag>
1129LoopCarriedOrderDepsTracker::getInstrTag(SUnit *SU) const {
1130 MachineInstr *MI = SU->getInstr();
1131 if (TII->isGlobalMemoryObject(MI))
1132 return InstrTag::Barrier;
1133
1134 if (MI->mayStore() ||
1135 (MI->mayLoad() && !MI->isDereferenceableInvariantLoad()))
1136 return InstrTag::LoadOrStore;
1137
1138 if (MI->mayRaiseFPException())
1139 return InstrTag::FPExceptions;
1140
1141 return std::nullopt;
1142}
1143
1144void LoopCarriedOrderDepsTracker::addDependenciesBetweenSUs(
1145 const SUnitWithMemInfo &Src, const SUnitWithMemInfo &Dst) {
1146 // Avoid self-dependencies.
1147 if (Src.SU == Dst.SU)
1148 return;
1149
1150 if (hasLoopCarriedMemDep(Src, Dst, BAA&: *BAA, TII, TRI, SSD: DAG))
1151 setLoopCarriedDep(Src: Src.SU, Dst: Dst.SU);
1152}
1153
1154void LoopCarriedOrderDepsTracker::addLoopCarriedDepenenciesForChunks(
1155 const NoBarrierInstsChunk &From, const NoBarrierInstsChunk &To) {
1156 // Add load-to-store dependencies (WAR).
1157 for (const SUnitWithMemInfo &Src : From.Loads)
1158 for (const SUnitWithMemInfo &Dst : To.Stores)
1159 addDependenciesBetweenSUs(Src, Dst);
1160
1161 // Add store-to-load dependencies (RAW).
1162 for (const SUnitWithMemInfo &Src : From.Stores)
1163 for (const SUnitWithMemInfo &Dst : To.Loads)
1164 addDependenciesBetweenSUs(Src, Dst);
1165
1166 // Add store-to-store dependencies (WAW).
1167 for (const SUnitWithMemInfo &Src : From.Stores)
1168 for (const SUnitWithMemInfo &Dst : To.Stores)
1169 addDependenciesBetweenSUs(Src, Dst);
1170}
1171
1172void LoopCarriedOrderDepsTracker::computeDependenciesAux() {
1173 SmallVector<NoBarrierInstsChunk, 2> Chunks(1);
1174 SUnit *FirstBarrier = nullptr;
1175 SUnit *LastBarrier = nullptr;
1176 for (const auto &TSU : TaggedSUnits) {
1177 InstrTag Tag = TSU.getTag();
1178 SUnit *SU = TSU.getPointer();
1179 switch (Tag) {
1180 case InstrTag::Barrier:
1181 if (!FirstBarrier)
1182 FirstBarrier = SU;
1183 LastBarrier = SU;
1184 Chunks.emplace_back();
1185 break;
1186 case InstrTag::LoadOrStore:
1187 case InstrTag::FPExceptions:
1188 Chunks.back().append(SU);
1189 break;
1190 }
1191 }
1192
1193 // Add dependencies between memory operations. If there are one or more
1194 // barrier events between two memory instructions, we don't add a
1195 // loop-carried dependence for them.
1196 for (const NoBarrierInstsChunk &Chunk : Chunks)
1197 addLoopCarriedDepenenciesForChunks(From: Chunk, To: Chunk);
1198
1199 // There is no barrier instruction between load/store/fp-exception
1200 // instructions in the same chunk. If there are one or more barrier
1201 // instructions, the instructions sequence is as follows:
1202 //
1203 // Loads/Stores/FPExceptions (Chunks.front())
1204 // Barrier (FirstBarrier)
1205 // Loads/Stores/FPExceptions
1206 // Barrier
1207 // ...
1208 // Loads/Stores/FPExceptions
1209 // Barrier (LastBarrier)
1210 // Loads/Stores/FPExceptions (Chunks.back())
1211 //
1212 // Since loads/stores/fp-exceptions must not be reordered across barrier
1213 // instructions, and the order of barrier instructions must be preserved, add
1214 // the following loop-carried dependences:
1215 //
1216 // Loads/Stores/FPExceptions (Chunks.front()) <-----+
1217 // +--> Barrier (FirstBarrier) <----------------------+ |
1218 // | Loads/Stores/FPExceptions | |
1219 // | Barrier | |
1220 // | ... | |
1221 // | Loads/Stores/FPExceptions | |
1222 // | Barrier (LastBarrier) ------------------------+--+
1223 // +--- Loads/Stores/FPExceptions (Chunks.back())
1224 //
1225 if (FirstBarrier) {
1226 assert(LastBarrier && "Both barriers should be set.");
1227
1228 // LastBarrier -> Loads/Stores/FPExceptions in Chunks.front()
1229 for (const SUnitWithMemInfo &Dst : Chunks.front().Loads)
1230 setLoopCarriedDep(Src: LastBarrier, Dst: Dst.SU);
1231 for (const SUnitWithMemInfo &Dst : Chunks.front().Stores)
1232 setLoopCarriedDep(Src: LastBarrier, Dst: Dst.SU);
1233 for (const SUnitWithMemInfo &Dst : Chunks.front().FPExceptions)
1234 setLoopCarriedDep(Src: LastBarrier, Dst: Dst.SU);
1235
1236 // Loads/Stores/FPExceptions in Chunks.back() -> FirstBarrier
1237 for (const SUnitWithMemInfo &Src : Chunks.back().Loads)
1238 setLoopCarriedDep(Src: Src.SU, Dst: FirstBarrier);
1239 for (const SUnitWithMemInfo &Src : Chunks.back().Stores)
1240 setLoopCarriedDep(Src: Src.SU, Dst: FirstBarrier);
1241 for (const SUnitWithMemInfo &Src : Chunks.back().FPExceptions)
1242 setLoopCarriedDep(Src: Src.SU, Dst: FirstBarrier);
1243
1244 // LastBarrier -> FirstBarrier (if they are different)
1245 if (FirstBarrier != LastBarrier)
1246 setLoopCarriedDep(Src: LastBarrier, Dst: FirstBarrier);
1247 }
1248}
1249
1250/// Add a chain edge between a load and store if the store can be an
1251/// alias of the load on a subsequent iteration, i.e., a loop carried
1252/// dependence. This code is very similar to the code in ScheduleDAGInstrs
1253/// but that code doesn't create loop carried dependences.
1254/// TODO: Also compute output-dependencies.
1255LoopCarriedEdges SwingSchedulerDAG::addLoopCarriedDependences() {
1256 LoopCarriedEdges LCE;
1257
1258 // Add loop-carried order-dependencies
1259 LoopCarriedOrderDepsTracker LCODTracker(this, &BAA, TII, TRI);
1260 LCODTracker.computeDependencies();
1261 for (unsigned I = 0; I != SUnits.size(); I++)
1262 for (const int Succ : LCODTracker.getLoopCarried(Idx: I).set_bits())
1263 LCE.OrderDeps[&SUnits[I]].insert(X: &SUnits[Succ]);
1264
1265 LCE.modifySUnits(SUnits, TII);
1266 return LCE;
1267}
1268
1269/// Update the phi dependences to the DAG because ScheduleDAGInstrs no longer
1270/// processes dependences for PHIs. This function adds true dependences
1271/// from a PHI to a use, and a loop carried dependence from the use to the
1272/// PHI. The loop carried dependence is represented as an anti dependence
1273/// edge. This function also removes chain dependences between unrelated
1274/// PHIs.
1275void SwingSchedulerDAG::updatePhiDependences() {
1276 SmallVector<SDep, 4> RemoveDeps;
1277 const TargetSubtargetInfo &ST = MF.getSubtarget<TargetSubtargetInfo>();
1278
1279 // Iterate over each DAG node.
1280 for (SUnit &I : SUnits) {
1281 RemoveDeps.clear();
1282 // Set to true if the instruction has an operand defined by a Phi.
1283 Register HasPhiUse;
1284 Register HasPhiDef;
1285 MachineInstr *MI = I.getInstr();
1286 // Iterate over each operand, and we process the definitions.
1287 for (const MachineOperand &MO : MI->operands()) {
1288 if (!MO.isReg())
1289 continue;
1290 Register Reg = MO.getReg();
1291 if (MO.isDef()) {
1292 // If the register is used by a Phi, then create an anti dependence.
1293 for (MachineRegisterInfo::use_instr_iterator
1294 UI = MRI.use_instr_begin(RegNo: Reg),
1295 UE = MRI.use_instr_end();
1296 UI != UE; ++UI) {
1297 MachineInstr *UseMI = &*UI;
1298 SUnit *SU = getSUnit(MI: UseMI);
1299 if (SU != nullptr && UseMI->isPHI()) {
1300 if (!MI->isPHI()) {
1301 SDep Dep(SU, SDep::Anti, Reg);
1302 Dep.setLatency(1);
1303 I.addPred(D: Dep);
1304 } else {
1305 HasPhiDef = Reg;
1306 // Add a chain edge to a dependent Phi that isn't an existing
1307 // predecessor.
1308
1309 // %3:intregs = PHI %21:intregs, %bb.6, %7:intregs, %bb.1 - SU0
1310 // %7:intregs = PHI %21:intregs, %bb.6, %13:intregs, %bb.1 - SU1
1311 // %27:intregs = A2_zxtb %3:intregs - SU2
1312 // %13:intregs = C2_muxri %45:predregs, 0, %46:intreg
1313 // If we have dependent phis, SU0 should be the successor of SU1
1314 // not the other way around. (it used to be SU1 is the successor
1315 // of SU0). In some cases, SU0 is scheduled earlier than SU1
1316 // resulting in bad IR as we do not have a value that can be used
1317 // by SU2.
1318
1319 if (SU->NodeNum < I.NodeNum && !SU->isPred(N: &I))
1320 SU->addPred(D: SDep(&I, SDep::Barrier));
1321 }
1322 }
1323 }
1324 } else if (MO.isUse()) {
1325 // If the register is defined by a Phi, then create a true dependence.
1326 MachineInstr *DefMI = MRI.getUniqueVRegDef(Reg);
1327 if (DefMI == nullptr)
1328 continue;
1329 SUnit *SU = getSUnit(MI: DefMI);
1330 if (SU != nullptr && DefMI->isPHI()) {
1331 if (!MI->isPHI()) {
1332 SDep Dep(SU, SDep::Data, Reg);
1333 Dep.setLatency(0);
1334 ST.adjustSchedDependency(Def: SU, DefOpIdx: 0, Use: &I, UseOpIdx: MO.getOperandNo(), Dep,
1335 SchedModel: &SchedModel);
1336 I.addPred(D: Dep);
1337 } else {
1338 HasPhiUse = Reg;
1339 // Add a chain edge to a dependent Phi that isn't an existing
1340 // predecessor.
1341 if (SU->NodeNum < I.NodeNum && !I.isPred(N: SU))
1342 I.addPred(D: SDep(SU, SDep::Barrier));
1343 }
1344 }
1345 }
1346 }
1347 // Remove order dependences from an unrelated Phi.
1348 if (!SwpPruneDeps)
1349 continue;
1350 for (auto &PI : I.Preds) {
1351 MachineInstr *PMI = PI.getSUnit()->getInstr();
1352 if (PMI->isPHI() && PI.getKind() == SDep::Order) {
1353 if (I.getInstr()->isPHI()) {
1354 if (PMI->getOperand(i: 0).getReg() == HasPhiUse)
1355 continue;
1356 if (getLoopPhiReg(Phi: *PMI, LoopBB: PMI->getParent()) == HasPhiDef)
1357 continue;
1358 }
1359 RemoveDeps.push_back(Elt: PI);
1360 }
1361 }
1362 for (const SDep &D : RemoveDeps)
1363 I.removePred(D);
1364 }
1365}
1366
1367/// Iterate over each DAG node and see if we can change any dependences
1368/// in order to reduce the recurrence MII.
1369void SwingSchedulerDAG::changeDependences() {
1370 // See if an instruction can use a value from the previous iteration.
1371 // If so, we update the base and offset of the instruction and change
1372 // the dependences.
1373 for (SUnit &I : SUnits) {
1374 unsigned BasePos = 0, OffsetPos = 0;
1375 Register NewBase;
1376 int64_t NewOffset = 0;
1377 if (!canUseLastOffsetValue(MI: I.getInstr(), BasePos, OffsetPos, NewBase,
1378 NewOffset))
1379 continue;
1380
1381 // Get the MI and SUnit for the instruction that defines the original base.
1382 Register OrigBase = I.getInstr()->getOperand(i: BasePos).getReg();
1383 MachineInstr *DefMI = MRI.getUniqueVRegDef(Reg: OrigBase);
1384 if (!DefMI)
1385 continue;
1386 SUnit *DefSU = getSUnit(MI: DefMI);
1387 if (!DefSU)
1388 continue;
1389 // Get the MI and SUnit for the instruction that defins the new base.
1390 MachineInstr *LastMI = MRI.getUniqueVRegDef(Reg: NewBase);
1391 if (!LastMI)
1392 continue;
1393 SUnit *LastSU = getSUnit(MI: LastMI);
1394 if (!LastSU)
1395 continue;
1396
1397 if (Topo.IsReachable(SU: &I, TargetSU: LastSU))
1398 continue;
1399
1400 // Remove the dependence. The value now depends on a prior iteration.
1401 SmallVector<SDep, 4> Deps;
1402 for (const SDep &P : I.Preds)
1403 if (P.getSUnit() == DefSU)
1404 Deps.push_back(Elt: P);
1405 for (const SDep &D : Deps) {
1406 Topo.RemovePred(M: &I, N: D.getSUnit());
1407 I.removePred(D);
1408 }
1409 // Remove the chain dependence between the instructions.
1410 Deps.clear();
1411 for (auto &P : LastSU->Preds)
1412 if (P.getSUnit() == &I && P.getKind() == SDep::Order)
1413 Deps.push_back(Elt: P);
1414 for (const SDep &D : Deps) {
1415 Topo.RemovePred(M: LastSU, N: D.getSUnit());
1416 LastSU->removePred(D);
1417 }
1418
1419 // Add a dependence between the new instruction and the instruction
1420 // that defines the new base.
1421 SDep Dep(&I, SDep::Anti, NewBase);
1422 Topo.AddPred(Y: LastSU, X: &I);
1423 LastSU->addPred(D: Dep);
1424
1425 // Remember the base and offset information so that we can update the
1426 // instruction during code generation.
1427 InstrChanges[&I] = std::make_pair(x&: NewBase, y&: NewOffset);
1428 }
1429}
1430
1431/// Create an instruction stream that represents a single iteration and stage of
1432/// each instruction. This function differs from SMSchedule::finalizeSchedule in
1433/// that this doesn't have any side-effect to SwingSchedulerDAG. That is, this
1434/// function is an approximation of SMSchedule::finalizeSchedule with all
1435/// non-const operations removed.
1436static void computeScheduledInsts(const SwingSchedulerDAG *SSD,
1437 SMSchedule &Schedule,
1438 std::vector<MachineInstr *> &OrderedInsts,
1439 DenseMap<MachineInstr *, unsigned> &Stages) {
1440 DenseMap<int, std::deque<SUnit *>> Instrs;
1441
1442 // Move all instructions to the first stage from the later stages.
1443 for (int Cycle = Schedule.getFirstCycle(); Cycle <= Schedule.getFinalCycle();
1444 ++Cycle) {
1445 for (int Stage = 0, LastStage = Schedule.getMaxStageCount();
1446 Stage <= LastStage; ++Stage) {
1447 for (SUnit *SU : llvm::reverse(C&: Schedule.getInstructions(
1448 cycle: Cycle + Stage * Schedule.getInitiationInterval()))) {
1449 Instrs[Cycle].push_front(x: SU);
1450 }
1451 }
1452 }
1453
1454 for (int Cycle = Schedule.getFirstCycle(); Cycle <= Schedule.getFinalCycle();
1455 ++Cycle) {
1456 std::deque<SUnit *> &CycleInstrs = Instrs[Cycle];
1457 CycleInstrs = Schedule.reorderInstructions(SSD, Instrs: CycleInstrs);
1458 for (SUnit *SU : CycleInstrs) {
1459 MachineInstr *MI = SU->getInstr();
1460 OrderedInsts.push_back(x: MI);
1461 Stages[MI] = Schedule.stageScheduled(SU);
1462 }
1463 }
1464}
1465
1466namespace {
1467
1468// FuncUnitSorter - Comparison operator used to sort instructions by
1469// the number of functional unit choices.
1470struct FuncUnitSorter {
1471 const InstrItineraryData *InstrItins;
1472 const MCSubtargetInfo *STI;
1473 DenseMap<InstrStage::FuncUnits, unsigned> Resources;
1474
1475 FuncUnitSorter(const TargetSubtargetInfo &TSI)
1476 : InstrItins(TSI.getInstrItineraryData()), STI(&TSI) {}
1477
1478 // Compute the number of functional unit alternatives needed
1479 // at each stage, and take the minimum value. We prioritize the
1480 // instructions by the least number of choices first.
1481 unsigned minFuncUnits(const MachineInstr *Inst,
1482 InstrStage::FuncUnits &F) const {
1483 unsigned SchedClass = Inst->getDesc().getSchedClass();
1484 unsigned min = UINT_MAX;
1485 if (InstrItins && !InstrItins->isEmpty()) {
1486 for (const InstrStage &IS :
1487 make_range(x: InstrItins->beginStage(ItinClassIndx: SchedClass),
1488 y: InstrItins->endStage(ItinClassIndx: SchedClass))) {
1489 InstrStage::FuncUnits funcUnits = IS.getUnits();
1490 unsigned numAlternatives = llvm::popcount(Value: funcUnits);
1491 if (numAlternatives < min) {
1492 min = numAlternatives;
1493 F = funcUnits;
1494 }
1495 }
1496 return min;
1497 }
1498 if (STI && STI->getSchedModel().hasInstrSchedModel()) {
1499 const MCSchedClassDesc *SCDesc =
1500 STI->getSchedModel().getSchedClassDesc(SchedClassIdx: SchedClass);
1501 if (!SCDesc->isValid())
1502 // No valid Schedule Class Desc for schedClass, should be
1503 // Pseudo/PostRAPseudo
1504 return min;
1505
1506 for (const MCWriteProcResEntry &PRE :
1507 make_range(x: STI->getWriteProcResBegin(SC: SCDesc),
1508 y: STI->getWriteProcResEnd(SC: SCDesc))) {
1509 if (!PRE.ReleaseAtCycle)
1510 continue;
1511 const MCProcResourceDesc *ProcResource =
1512 STI->getSchedModel().getProcResource(ProcResourceIdx: PRE.ProcResourceIdx);
1513 unsigned NumUnits = ProcResource->NumUnits;
1514 if (NumUnits < min) {
1515 min = NumUnits;
1516 F = PRE.ProcResourceIdx;
1517 }
1518 }
1519 return min;
1520 }
1521 llvm_unreachable("Should have non-empty InstrItins or hasInstrSchedModel!");
1522 }
1523
1524 // Compute the critical resources needed by the instruction. This
1525 // function records the functional units needed by instructions that
1526 // must use only one functional unit. We use this as a tie breaker
1527 // for computing the resource MII. The instrutions that require
1528 // the same, highly used, functional unit have high priority.
1529 void calcCriticalResources(MachineInstr &MI) {
1530 unsigned SchedClass = MI.getDesc().getSchedClass();
1531 if (InstrItins && !InstrItins->isEmpty()) {
1532 for (const InstrStage &IS :
1533 make_range(x: InstrItins->beginStage(ItinClassIndx: SchedClass),
1534 y: InstrItins->endStage(ItinClassIndx: SchedClass))) {
1535 InstrStage::FuncUnits FuncUnits = IS.getUnits();
1536 if (llvm::popcount(Value: FuncUnits) == 1)
1537 Resources[FuncUnits]++;
1538 }
1539 return;
1540 }
1541 if (STI && STI->getSchedModel().hasInstrSchedModel()) {
1542 const MCSchedClassDesc *SCDesc =
1543 STI->getSchedModel().getSchedClassDesc(SchedClassIdx: SchedClass);
1544 if (!SCDesc->isValid())
1545 // No valid Schedule Class Desc for schedClass, should be
1546 // Pseudo/PostRAPseudo
1547 return;
1548
1549 for (const MCWriteProcResEntry &PRE :
1550 make_range(x: STI->getWriteProcResBegin(SC: SCDesc),
1551 y: STI->getWriteProcResEnd(SC: SCDesc))) {
1552 if (!PRE.ReleaseAtCycle)
1553 continue;
1554 Resources[PRE.ProcResourceIdx]++;
1555 }
1556 return;
1557 }
1558 llvm_unreachable("Should have non-empty InstrItins or hasInstrSchedModel!");
1559 }
1560
1561 /// Return true if IS1 has less priority than IS2.
1562 bool operator()(const MachineInstr *IS1, const MachineInstr *IS2) const {
1563 InstrStage::FuncUnits F1 = 0, F2 = 0;
1564 unsigned MFUs1 = minFuncUnits(Inst: IS1, F&: F1);
1565 unsigned MFUs2 = minFuncUnits(Inst: IS2, F&: F2);
1566 if (MFUs1 == MFUs2)
1567 return Resources.lookup(Val: F1) < Resources.lookup(Val: F2);
1568 return MFUs1 > MFUs2;
1569 }
1570};
1571
1572/// Calculate the maximum register pressure of the scheduled instructions stream
1573class HighRegisterPressureDetector {
1574 MachineBasicBlock *OrigMBB;
1575 const MachineRegisterInfo &MRI;
1576 const TargetRegisterInfo *TRI;
1577
1578 const unsigned PSetNum;
1579
1580 // Indexed by PSet ID
1581 // InitSetPressure takes into account the register pressure of live-in
1582 // registers. It's not depend on how the loop is scheduled, so it's enough to
1583 // calculate them once at the beginning.
1584 std::vector<unsigned> InitSetPressure;
1585
1586 // Indexed by PSet ID
1587 // Upper limit for each register pressure set
1588 std::vector<unsigned> PressureSetLimit;
1589
1590 DenseMap<MachineInstr *, RegisterOperands> ROMap;
1591
1592 using Instr2LastUsesTy = DenseMap<MachineInstr *, SmallDenseSet<Register, 4>>;
1593
1594public:
1595 using OrderedInstsTy = std::vector<MachineInstr *>;
1596 using Instr2StageTy = DenseMap<MachineInstr *, unsigned>;
1597
1598private:
1599 static void dumpRegisterPressures(const std::vector<unsigned> &Pressures) {
1600 if (Pressures.size() == 0) {
1601 dbgs() << "[]";
1602 } else {
1603 char Prefix = '[';
1604 for (unsigned P : Pressures) {
1605 dbgs() << Prefix << P;
1606 Prefix = ' ';
1607 }
1608 dbgs() << ']';
1609 }
1610 }
1611
1612 void dumpPSet(Register Reg) const {
1613 dbgs() << "Reg=" << printReg(Reg, TRI, SubIdx: 0, MRI: &MRI) << " PSet=";
1614 // FIXME: The static_cast is a bug compensating bugs in the callers.
1615 VirtRegOrUnit VRegOrUnit =
1616 Reg.isVirtual() ? VirtRegOrUnit(Reg)
1617 : VirtRegOrUnit(static_cast<MCRegUnit>(Reg.id()));
1618 for (auto PSetIter = MRI.getPressureSets(VRegOrUnit); PSetIter.isValid();
1619 ++PSetIter) {
1620 dbgs() << *PSetIter << ' ';
1621 }
1622 dbgs() << '\n';
1623 }
1624
1625 void increaseRegisterPressure(std::vector<unsigned> &Pressure,
1626 Register Reg) const {
1627 // FIXME: The static_cast is a bug compensating bugs in the callers.
1628 VirtRegOrUnit VRegOrUnit =
1629 Reg.isVirtual() ? VirtRegOrUnit(Reg)
1630 : VirtRegOrUnit(static_cast<MCRegUnit>(Reg.id()));
1631 auto PSetIter = MRI.getPressureSets(VRegOrUnit);
1632 unsigned Weight = PSetIter.getWeight();
1633 for (; PSetIter.isValid(); ++PSetIter)
1634 Pressure[*PSetIter] += Weight;
1635 }
1636
1637 void decreaseRegisterPressure(std::vector<unsigned> &Pressure,
1638 Register Reg) const {
1639 auto PSetIter = MRI.getPressureSets(VRegOrUnit: VirtRegOrUnit(Reg));
1640 unsigned Weight = PSetIter.getWeight();
1641 for (; PSetIter.isValid(); ++PSetIter) {
1642 auto &P = Pressure[*PSetIter];
1643 assert(P >= Weight &&
1644 "register pressure must be greater than or equal weight");
1645 P -= Weight;
1646 }
1647 }
1648
1649 // Return true if Reg is reserved one, for example, stack pointer
1650 bool isReservedRegister(Register Reg) const {
1651 return Reg.isPhysical() && MRI.isReserved(PhysReg: Reg.asMCReg());
1652 }
1653
1654 bool isDefinedInThisLoop(Register Reg) const {
1655 return Reg.isVirtual() && MRI.getDefBlock(Reg) == OrigMBB;
1656 }
1657
1658 // Search for live-in variables. They are factored into the register pressure
1659 // from the begining. Live-in variables used by every iteration should be
1660 // considered as alive throughout the loop. For example, the variable `c` in
1661 // following code. \code
1662 // int c = ...;
1663 // for (int i = 0; i < n; i++)
1664 // a[i] += b[i] + c;
1665 // \endcode
1666 void computeLiveIn() {
1667 DenseSet<Register> Used;
1668 for (auto &MI : *OrigMBB) {
1669 if (MI.isDebugInstr())
1670 continue;
1671 for (auto &Use : ROMap[&MI].Uses) {
1672 // FIXME: The static_cast is a bug.
1673 Register Reg =
1674 Use.VRegOrUnit.isVirtualReg()
1675 ? Use.VRegOrUnit.asVirtualReg()
1676 : Register(static_cast<unsigned>(Use.VRegOrUnit.asMCRegUnit()));
1677 // Ignore the variable that appears only on one side of phi instruction
1678 // because it's used only at the first iteration.
1679 if (MI.isPHI() && Reg != getLoopPhiReg(Phi: MI, LoopBB: OrigMBB))
1680 continue;
1681 if (isReservedRegister(Reg))
1682 continue;
1683 if (isDefinedInThisLoop(Reg))
1684 continue;
1685 Used.insert(V: Reg);
1686 }
1687 }
1688
1689 for (auto LiveIn : Used)
1690 increaseRegisterPressure(Pressure&: InitSetPressure, Reg: LiveIn);
1691 }
1692
1693 // Calculate the upper limit of each pressure set
1694 void computePressureSetLimit(const RegisterClassInfo &RCI) {
1695 for (unsigned PSet = 0; PSet < PSetNum; PSet++)
1696 PressureSetLimit[PSet] = RCI.getRegPressureSetLimit(Idx: PSet);
1697 }
1698
1699 // There are two patterns of last-use.
1700 // - by an instruction of the current iteration
1701 // - by a phi instruction of the next iteration (loop carried value)
1702 //
1703 // Furthermore, following two groups of instructions are executed
1704 // simultaneously
1705 // - next iteration's phi instructions in i-th stage
1706 // - current iteration's instructions in i+1-th stage
1707 //
1708 // This function calculates the last-use of each register while taking into
1709 // account the above two patterns.
1710 Instr2LastUsesTy computeLastUses(const OrderedInstsTy &OrderedInsts,
1711 Instr2StageTy &Stages) const {
1712 // We treat virtual registers that are defined and used in this loop.
1713 // Following virtual register will be ignored
1714 // - live-in one
1715 // - defined but not used in the loop (potentially live-out)
1716 DenseSet<Register> TargetRegs;
1717 const auto UpdateTargetRegs = [this, &TargetRegs](Register Reg) {
1718 if (isDefinedInThisLoop(Reg))
1719 TargetRegs.insert(V: Reg);
1720 };
1721 for (MachineInstr *MI : OrderedInsts) {
1722 if (MI->isPHI()) {
1723 Register Reg = getLoopPhiReg(Phi: *MI, LoopBB: OrigMBB);
1724 UpdateTargetRegs(Reg);
1725 } else {
1726 for (auto &Use : ROMap.find(Val: MI)->getSecond().Uses) {
1727 // FIXME: The static_cast is a bug.
1728 Register Reg = Use.VRegOrUnit.isVirtualReg()
1729 ? Use.VRegOrUnit.asVirtualReg()
1730 : Register(static_cast<unsigned>(
1731 Use.VRegOrUnit.asMCRegUnit()));
1732 UpdateTargetRegs(Reg);
1733 }
1734 }
1735 }
1736
1737 const auto InstrScore = [&Stages](MachineInstr *MI) {
1738 return Stages[MI] + MI->isPHI();
1739 };
1740
1741 DenseMap<Register, MachineInstr *> LastUseMI;
1742 for (MachineInstr *MI : llvm::reverse(C: OrderedInsts)) {
1743 for (auto &Use : ROMap.find(Val: MI)->getSecond().Uses) {
1744 // FIXME: The static_cast is a bug.
1745 Register Reg =
1746 Use.VRegOrUnit.isVirtualReg()
1747 ? Use.VRegOrUnit.asVirtualReg()
1748 : Register(static_cast<unsigned>(Use.VRegOrUnit.asMCRegUnit()));
1749 if (!TargetRegs.contains(V: Reg))
1750 continue;
1751 auto [Ite, Inserted] = LastUseMI.try_emplace(Key: Reg, Args&: MI);
1752 if (!Inserted) {
1753 MachineInstr *Orig = Ite->second;
1754 MachineInstr *New = MI;
1755 if (InstrScore(Orig) < InstrScore(New))
1756 Ite->second = New;
1757 }
1758 }
1759 }
1760
1761 Instr2LastUsesTy LastUses;
1762 for (auto [Reg, MI] : LastUseMI)
1763 LastUses[MI].insert(V: Reg);
1764 return LastUses;
1765 }
1766
1767 // Compute the maximum register pressure of the kernel. We'll simulate #Stage
1768 // iterations and check the register pressure at the point where all stages
1769 // overlapping.
1770 //
1771 // An example of unrolled loop where #Stage is 4..
1772 // Iter i+0 i+1 i+2 i+3
1773 // ------------------------
1774 // Stage 0
1775 // Stage 1 0
1776 // Stage 2 1 0
1777 // Stage 3 2 1 0 <- All stages overlap
1778 //
1779 std::vector<unsigned>
1780 computeMaxSetPressure(const OrderedInstsTy &OrderedInsts,
1781 Instr2StageTy &Stages,
1782 const unsigned StageCount) const {
1783 using RegSetTy = SmallDenseSet<Register, 16>;
1784
1785 // Indexed by #Iter. To treat "local" variables of each stage separately, we
1786 // manage the liveness of the registers independently by iterations.
1787 SmallVector<RegSetTy> LiveRegSets(StageCount);
1788
1789 auto CurSetPressure = InitSetPressure;
1790 auto MaxSetPressure = InitSetPressure;
1791 auto LastUses = computeLastUses(OrderedInsts, Stages);
1792
1793 LLVM_DEBUG({
1794 dbgs() << "Ordered instructions:\n";
1795 for (MachineInstr *MI : OrderedInsts) {
1796 dbgs() << "Stage " << Stages[MI] << ": ";
1797 MI->dump();
1798 }
1799 });
1800
1801 const auto InsertReg = [this, &CurSetPressure](RegSetTy &RegSet,
1802 VirtRegOrUnit VRegOrUnit) {
1803 // FIXME: The static_cast is a bug.
1804 Register Reg =
1805 VRegOrUnit.isVirtualReg()
1806 ? VRegOrUnit.asVirtualReg()
1807 : Register(static_cast<unsigned>(VRegOrUnit.asMCRegUnit()));
1808 if (!Reg.isValid() || isReservedRegister(Reg))
1809 return;
1810
1811 bool Inserted = RegSet.insert(V: Reg).second;
1812 if (!Inserted)
1813 return;
1814
1815 LLVM_DEBUG(dbgs() << "insert " << printReg(Reg, TRI, 0, &MRI) << "\n");
1816 increaseRegisterPressure(Pressure&: CurSetPressure, Reg);
1817 LLVM_DEBUG(dumpPSet(Reg));
1818 };
1819
1820 const auto EraseReg = [this, &CurSetPressure](RegSetTy &RegSet,
1821 Register Reg) {
1822 if (!Reg.isValid() || isReservedRegister(Reg))
1823 return;
1824
1825 // live-in register
1826 if (!RegSet.contains(V: Reg))
1827 return;
1828
1829 LLVM_DEBUG(dbgs() << "erase " << printReg(Reg, TRI, 0, &MRI) << "\n");
1830 RegSet.erase(V: Reg);
1831 decreaseRegisterPressure(Pressure&: CurSetPressure, Reg);
1832 LLVM_DEBUG(dumpPSet(Reg));
1833 };
1834
1835 for (unsigned I = 0; I < StageCount; I++) {
1836 for (MachineInstr *MI : OrderedInsts) {
1837 const auto Stage = Stages[MI];
1838 if (I < Stage)
1839 continue;
1840
1841 const unsigned Iter = I - Stage;
1842
1843 for (auto &Def : ROMap.find(Val: MI)->getSecond().Defs)
1844 InsertReg(LiveRegSets[Iter], Def.VRegOrUnit);
1845
1846 for (auto LastUse : LastUses[MI]) {
1847 if (MI->isPHI()) {
1848 if (Iter != 0)
1849 EraseReg(LiveRegSets[Iter - 1], LastUse);
1850 } else {
1851 EraseReg(LiveRegSets[Iter], LastUse);
1852 }
1853 }
1854
1855 for (unsigned PSet = 0; PSet < PSetNum; PSet++)
1856 MaxSetPressure[PSet] =
1857 std::max(a: MaxSetPressure[PSet], b: CurSetPressure[PSet]);
1858
1859 LLVM_DEBUG({
1860 dbgs() << "CurSetPressure=";
1861 dumpRegisterPressures(CurSetPressure);
1862 dbgs() << " iter=" << Iter << " stage=" << Stage << ":";
1863 MI->dump();
1864 });
1865 }
1866 }
1867
1868 return MaxSetPressure;
1869 }
1870
1871public:
1872 HighRegisterPressureDetector(MachineBasicBlock *OrigMBB,
1873 const MachineFunction &MF)
1874 : OrigMBB(OrigMBB), MRI(MF.getRegInfo()),
1875 TRI(MF.getSubtarget().getRegisterInfo()),
1876 PSetNum(TRI->getNumRegPressureSets()), InitSetPressure(PSetNum, 0),
1877 PressureSetLimit(PSetNum, 0) {}
1878
1879 // Used to calculate register pressure, which is independent of loop
1880 // scheduling.
1881 void init(const RegisterClassInfo &RCI) {
1882 for (MachineInstr &MI : *OrigMBB) {
1883 if (MI.isDebugInstr())
1884 continue;
1885 ROMap[&MI].collect(MI, TRI: *TRI, MRI, TrackLaneMasks: false, IgnoreDead: true);
1886 }
1887
1888 computeLiveIn();
1889 computePressureSetLimit(RCI);
1890 }
1891
1892 // Calculate the maximum register pressures of the loop and check if they
1893 // exceed the limit
1894 bool detect(const SwingSchedulerDAG *SSD, SMSchedule &Schedule,
1895 const unsigned MaxStage) const {
1896 assert(0 <= RegPressureMargin && RegPressureMargin <= 100 &&
1897 "the percentage of the margin must be between 0 to 100");
1898
1899 OrderedInstsTy OrderedInsts;
1900 Instr2StageTy Stages;
1901 computeScheduledInsts(SSD, Schedule, OrderedInsts, Stages);
1902 const auto MaxSetPressure =
1903 computeMaxSetPressure(OrderedInsts, Stages, StageCount: MaxStage + 1);
1904
1905 LLVM_DEBUG({
1906 dbgs() << "Dump MaxSetPressure:\n";
1907 for (unsigned I = 0; I < MaxSetPressure.size(); I++) {
1908 dbgs() << format("MaxSetPressure[%d]=%d\n", I, MaxSetPressure[I]);
1909 }
1910 dbgs() << '\n';
1911 });
1912
1913 for (unsigned PSet = 0; PSet < PSetNum; PSet++) {
1914 unsigned Limit = PressureSetLimit[PSet];
1915 unsigned Margin = Limit * RegPressureMargin / 100;
1916 LLVM_DEBUG(dbgs() << "PSet=" << PSet << " Limit=" << Limit
1917 << " Margin=" << Margin << "\n");
1918 if (Limit < MaxSetPressure[PSet] + Margin) {
1919 LLVM_DEBUG(
1920 dbgs()
1921 << "Rejected the schedule because of too high register pressure\n");
1922 return true;
1923 }
1924 }
1925 return false;
1926 }
1927};
1928
1929} // end anonymous namespace
1930
1931/// Calculate the resource constrained minimum initiation interval for the
1932/// specified loop. We use the DFA to model the resources needed for
1933/// each instruction, and we ignore dependences. A different DFA is created
1934/// for each cycle that is required. When adding a new instruction, we attempt
1935/// to add it to each existing DFA, until a legal space is found. If the
1936/// instruction cannot be reserved in an existing DFA, we create a new one.
1937unsigned SwingSchedulerDAG::calculateResMII() {
1938 LLVM_DEBUG(dbgs() << "calculateResMII:\n");
1939 ResourceManager RM(&MF.getSubtarget(), this);
1940 return RM.calculateResMII();
1941}
1942
1943/// Calculate the recurrence-constrainted minimum initiation interval.
1944/// Iterate over each circuit. Compute the delay(c) and distance(c)
1945/// for each circuit. The II needs to satisfy the inequality
1946/// delay(c) - II*distance(c) <= 0. For each circuit, choose the smallest
1947/// II that satisfies the inequality, and the RecMII is the maximum
1948/// of those values.
1949unsigned SwingSchedulerDAG::calculateRecMII(NodeSetType &NodeSets) {
1950 unsigned RecMII = 0;
1951
1952 for (NodeSet &Nodes : NodeSets) {
1953 if (Nodes.empty())
1954 continue;
1955
1956 unsigned Delay = Nodes.getLatency();
1957 unsigned Distance = 1;
1958
1959 // ii = ceil(delay / distance)
1960 unsigned CurMII = (Delay + Distance - 1) / Distance;
1961 Nodes.setRecMII(CurMII);
1962 if (CurMII > RecMII)
1963 RecMII = CurMII;
1964 }
1965
1966 return RecMII;
1967}
1968
1969/// Create the adjacency structure of the nodes in the graph.
1970void SwingSchedulerDAG::Circuits::createAdjacencyStructure(
1971 SwingSchedulerDDG *DDG) {
1972 BitVector Added(SUnits.size());
1973 DenseMap<int, int> OutputDeps;
1974 for (int i = 0, e = SUnits.size(); i != e; ++i) {
1975 Added.reset();
1976 // Add any successor to the adjacency matrix and exclude duplicates.
1977 for (auto &OE : DDG->getOutEdges(SU: &SUnits[i])) {
1978 // Only create a back-edge on the first and last nodes of a dependence
1979 // chain. This records any chains and adds them later.
1980 if (OE.isOutputDep()) {
1981 int N = OE.getDst()->NodeNum;
1982 int BackEdge = i;
1983 auto Dep = OutputDeps.find(Val: BackEdge);
1984 if (Dep != OutputDeps.end()) {
1985 BackEdge = Dep->second;
1986 OutputDeps.erase(I: Dep);
1987 }
1988 OutputDeps[N] = BackEdge;
1989 }
1990 // Do not process a boundary node, an artificial node.
1991 if (OE.getDst()->isBoundaryNode() || OE.isArtificial())
1992 continue;
1993
1994 // This code is retained o preserve previous behavior and prevent
1995 // regression. This condition means that anti-dependnecies within an
1996 // iteration are ignored when searching circuits. Therefore it's natural
1997 // to consider this dependence as well.
1998 // FIXME: Remove this code if it doesn't have significant impact on
1999 // performance.
2000 if (OE.isAntiDep())
2001 continue;
2002
2003 int N = OE.getDst()->NodeNum;
2004 if (!Added.test(Idx: N)) {
2005 AdjK[i].push_back(Elt: N);
2006 Added.set(N);
2007 }
2008 }
2009
2010 // Also add any extra out edges to the adjacency matrix.
2011 for (const SUnit *Dst : DDG->getExtraOutEdges(SU: &SUnits[i])) {
2012 int N = Dst->NodeNum;
2013 if (!Added.test(Idx: N)) {
2014 AdjK[i].push_back(Elt: N);
2015 Added.set(N);
2016 }
2017 }
2018 }
2019
2020 // Add back-edges in the adjacency matrix for the output dependences.
2021 for (auto &OD : OutputDeps)
2022 if (!Added.test(Idx: OD.second)) {
2023 AdjK[OD.first].push_back(Elt: OD.second);
2024 Added.set(OD.second);
2025 }
2026}
2027
2028/// Identify an elementary circuit in the dependence graph starting at the
2029/// specified node.
2030bool SwingSchedulerDAG::Circuits::circuit(int V, int S, NodeSetType &NodeSets,
2031 const SwingSchedulerDAG *DAG,
2032 bool HasBackedge) {
2033 SUnit *SV = &SUnits[V];
2034 bool F = false;
2035 Stack.insert(X: SV);
2036 Blocked.set(V);
2037
2038 for (auto W : AdjK[V]) {
2039 if (NumPaths > MaxPaths)
2040 break;
2041 if (W < S)
2042 continue;
2043 if (W == S) {
2044 if (!HasBackedge)
2045 NodeSets.push_back(Elt: NodeSet(Stack.begin(), Stack.end(), DAG));
2046 F = true;
2047 ++NumPaths;
2048 break;
2049 }
2050 if (!Blocked.test(Idx: W)) {
2051 if (circuit(V: W, S, NodeSets, DAG,
2052 HasBackedge: Node2Idx->at(n: W) < Node2Idx->at(n: V) ? true : HasBackedge))
2053 F = true;
2054 }
2055 }
2056
2057 if (F)
2058 unblock(U: V);
2059 else {
2060 for (auto W : AdjK[V]) {
2061 if (W < S)
2062 continue;
2063 B[W].insert(Ptr: SV);
2064 }
2065 }
2066 Stack.pop_back();
2067 return F;
2068}
2069
2070/// Unblock a node in the circuit finding algorithm.
2071void SwingSchedulerDAG::Circuits::unblock(int U) {
2072 Blocked.reset(Idx: U);
2073 SmallPtrSet<SUnit *, 4> &BU = B[U];
2074 while (!BU.empty()) {
2075 SmallPtrSet<SUnit *, 4>::iterator SI = BU.begin();
2076 assert(SI != BU.end() && "Invalid B set.");
2077 SUnit *W = *SI;
2078 BU.erase(Ptr: W);
2079 if (Blocked.test(Idx: W->NodeNum))
2080 unblock(U: W->NodeNum);
2081 }
2082}
2083
2084/// Identify all the elementary circuits in the dependence graph using
2085/// Johnson's circuit algorithm.
2086void SwingSchedulerDAG::findCircuits(NodeSetType &NodeSets) {
2087 Circuits Cir(SUnits, Topo);
2088 // Create the adjacency structure.
2089 Cir.createAdjacencyStructure(DDG: &*DDG);
2090 for (int I = 0, E = SUnits.size(); I != E; ++I) {
2091 Cir.reset();
2092 Cir.circuit(V: I, S: I, NodeSets, DAG: this);
2093 }
2094}
2095
2096// Create artificial dependencies between the source of COPY/REG_SEQUENCE that
2097// is loop-carried to the USE in next iteration. This will help pipeliner avoid
2098// additional copies that are needed across iterations. An artificial dependence
2099// edge is added from USE to SOURCE of COPY/REG_SEQUENCE.
2100
2101// PHI-------Anti-Dep-----> COPY/REG_SEQUENCE (loop-carried)
2102// SRCOfCopY------True-Dep---> COPY/REG_SEQUENCE
2103// PHI-------True-Dep------> USEOfPhi
2104
2105// The mutation creates
2106// USEOfPHI -------Artificial-Dep---> SRCOfCopy
2107
2108// This overall will ensure, the USEOfPHI is scheduled before SRCOfCopy
2109// (since USE is a predecessor), implies, the COPY/ REG_SEQUENCE is scheduled
2110// late to avoid additional copies across iterations. The possible scheduling
2111// order would be
2112// USEOfPHI --- SRCOfCopy--- COPY/REG_SEQUENCE.
2113
2114void SwingSchedulerDAG::CopyToPhiMutation::apply(ScheduleDAGInstrs *DAG) {
2115 for (SUnit &SU : DAG->SUnits) {
2116 // Find the COPY/REG_SEQUENCE instruction.
2117 if (!SU.getInstr()->isCopy() && !SU.getInstr()->isRegSequence())
2118 continue;
2119
2120 // Record the loop carried PHIs.
2121 SmallVector<SUnit *, 4> PHISUs;
2122 // Record the SrcSUs that feed the COPY/REG_SEQUENCE instructions.
2123 SmallVector<SUnit *, 4> SrcSUs;
2124
2125 for (auto &Dep : SU.Preds) {
2126 SUnit *TmpSU = Dep.getSUnit();
2127 MachineInstr *TmpMI = TmpSU->getInstr();
2128 SDep::Kind DepKind = Dep.getKind();
2129 // Save the loop carried PHI.
2130 if (DepKind == SDep::Anti && TmpMI->isPHI())
2131 PHISUs.push_back(Elt: TmpSU);
2132 // Save the source of COPY/REG_SEQUENCE.
2133 // If the source has no pre-decessors, we will end up creating cycles.
2134 else if (DepKind == SDep::Data && !TmpMI->isPHI() && TmpSU->NumPreds > 0)
2135 SrcSUs.push_back(Elt: TmpSU);
2136 }
2137
2138 if (PHISUs.size() == 0 || SrcSUs.size() == 0)
2139 continue;
2140
2141 // Find the USEs of PHI. If the use is a PHI or REG_SEQUENCE, push back this
2142 // SUnit to the container.
2143 SmallVector<SUnit *, 8> UseSUs;
2144 // Do not use iterator based loop here as we are updating the container.
2145 for (size_t Index = 0; Index < PHISUs.size(); ++Index) {
2146 for (auto &Dep : PHISUs[Index]->Succs) {
2147 if (Dep.getKind() != SDep::Data)
2148 continue;
2149
2150 SUnit *TmpSU = Dep.getSUnit();
2151 MachineInstr *TmpMI = TmpSU->getInstr();
2152 if (TmpMI->isPHI() || TmpMI->isRegSequence()) {
2153 PHISUs.push_back(Elt: TmpSU);
2154 continue;
2155 }
2156 UseSUs.push_back(Elt: TmpSU);
2157 }
2158 }
2159
2160 if (UseSUs.size() == 0)
2161 continue;
2162
2163 SwingSchedulerDAG *SDAG = cast<SwingSchedulerDAG>(Val: DAG);
2164 // Add the artificial dependencies if it does not form a cycle.
2165 for (auto *I : UseSUs) {
2166 for (auto *Src : SrcSUs) {
2167 if (!SDAG->Topo.IsReachable(SU: I, TargetSU: Src) && Src != I) {
2168 Src->addPred(D: SDep(I, SDep::Artificial));
2169 SDAG->Topo.AddPred(Y: Src, X: I);
2170 }
2171 }
2172 }
2173 }
2174}
2175
2176/// Compute several functions need to order the nodes for scheduling.
2177/// ASAP - Earliest time to schedule a node.
2178/// ALAP - Latest time to schedule a node.
2179/// MOV - Mobility function, difference between ALAP and ASAP.
2180/// D - Depth of each node.
2181/// H - Height of each node.
2182void SwingSchedulerDAG::computeNodeFunctions(NodeSetType &NodeSets) {
2183 ScheduleInfo.resize(new_size: SUnits.size());
2184
2185 LLVM_DEBUG({
2186 for (int I : Topo) {
2187 const SUnit &SU = SUnits[I];
2188 dumpNode(SU);
2189 }
2190 });
2191
2192 int maxASAP = 0;
2193 // Compute ASAP and ZeroLatencyDepth.
2194 for (int I : Topo) {
2195 int asap = 0;
2196 int zeroLatencyDepth = 0;
2197 SUnit *SU = &SUnits[I];
2198 for (const auto &IE : DDG->getInEdges(SU)) {
2199 SUnit *Pred = IE.getSrc();
2200 if (IE.getLatency() == 0)
2201 zeroLatencyDepth =
2202 std::max(a: zeroLatencyDepth, b: getZeroLatencyDepth(Node: Pred) + 1);
2203 if (IE.ignoreDependence(IgnoreAnti: true))
2204 continue;
2205 asap = std::max(a: asap, b: (int)(getASAP(Node: Pred) + IE.getLatency() -
2206 IE.getDistance() * MII));
2207 }
2208 maxASAP = std::max(a: maxASAP, b: asap);
2209 ScheduleInfo[I].ASAP = asap;
2210 ScheduleInfo[I].ZeroLatencyDepth = zeroLatencyDepth;
2211 }
2212
2213 // Compute ALAP, ZeroLatencyHeight, and MOV.
2214 for (int I : llvm::reverse(C&: Topo)) {
2215 int alap = maxASAP;
2216 int zeroLatencyHeight = 0;
2217 SUnit *SU = &SUnits[I];
2218 for (const auto &OE : DDG->getOutEdges(SU)) {
2219 SUnit *Succ = OE.getDst();
2220 if (Succ->isBoundaryNode())
2221 continue;
2222 if (OE.getLatency() == 0)
2223 zeroLatencyHeight =
2224 std::max(a: zeroLatencyHeight, b: getZeroLatencyHeight(Node: Succ) + 1);
2225 if (OE.ignoreDependence(IgnoreAnti: true))
2226 continue;
2227 alap = std::min(a: alap, b: (int)(getALAP(Node: Succ) - OE.getLatency() +
2228 OE.getDistance() * MII));
2229 }
2230
2231 ScheduleInfo[I].ALAP = alap;
2232 ScheduleInfo[I].ZeroLatencyHeight = zeroLatencyHeight;
2233 }
2234
2235 // After computing the node functions, compute the summary for each node set.
2236 for (NodeSet &I : NodeSets)
2237 I.computeNodeSetInfo(SSD: this);
2238
2239 LLVM_DEBUG({
2240 for (unsigned i = 0; i < SUnits.size(); i++) {
2241 dbgs() << "\tNode " << i << ":\n";
2242 dbgs() << "\t ASAP = " << getASAP(&SUnits[i]) << "\n";
2243 dbgs() << "\t ALAP = " << getALAP(&SUnits[i]) << "\n";
2244 dbgs() << "\t MOV = " << getMOV(&SUnits[i]) << "\n";
2245 dbgs() << "\t D = " << getDepth(&SUnits[i]) << "\n";
2246 dbgs() << "\t H = " << getHeight(&SUnits[i]) << "\n";
2247 dbgs() << "\t ZLD = " << getZeroLatencyDepth(&SUnits[i]) << "\n";
2248 dbgs() << "\t ZLH = " << getZeroLatencyHeight(&SUnits[i]) << "\n";
2249 }
2250 });
2251}
2252
2253/// Compute the Pred_L(O) set, as defined in the paper. The set is defined
2254/// as the predecessors of the elements of NodeOrder that are not also in
2255/// NodeOrder.
2256static bool pred_L(SetVector<SUnit *> &NodeOrder,
2257 SmallSetVector<SUnit *, 8> &Preds, SwingSchedulerDDG *DDG,
2258 const NodeSet *S = nullptr) {
2259 Preds.clear();
2260
2261 for (SUnit *SU : NodeOrder) {
2262 for (const auto &IE : DDG->getInEdges(SU)) {
2263 SUnit *PredSU = IE.getSrc();
2264 if (S && S->count(SU: PredSU) == 0)
2265 continue;
2266 if (IE.ignoreDependence(IgnoreAnti: true))
2267 continue;
2268 if (NodeOrder.count(key: PredSU) == 0)
2269 Preds.insert(X: PredSU);
2270 }
2271
2272 // FIXME: The following loop-carried dependencies may also need to be
2273 // considered.
2274 // - Physical register dependencies (true-dependence and WAW).
2275 // - Memory dependencies.
2276 for (const auto &OE : DDG->getOutEdges(SU)) {
2277 SUnit *SuccSU = OE.getDst();
2278 if (!OE.isAntiDep())
2279 continue;
2280 if (S && S->count(SU: SuccSU) == 0)
2281 continue;
2282 if (NodeOrder.count(key: SuccSU) == 0)
2283 Preds.insert(X: SuccSU);
2284 }
2285 }
2286 return !Preds.empty();
2287}
2288
2289/// Compute the Succ_L(O) set, as defined in the paper. The set is defined
2290/// as the successors of the elements of NodeOrder that are not also in
2291/// NodeOrder.
2292static bool succ_L(SetVector<SUnit *> &NodeOrder,
2293 SmallSetVector<SUnit *, 8> &Succs, SwingSchedulerDDG *DDG,
2294 const NodeSet *S = nullptr) {
2295 Succs.clear();
2296
2297 for (SUnit *SU : NodeOrder) {
2298 for (const auto &OE : DDG->getOutEdges(SU)) {
2299 SUnit *SuccSU = OE.getDst();
2300 if (S && S->count(SU: SuccSU) == 0)
2301 continue;
2302 if (OE.ignoreDependence(IgnoreAnti: false))
2303 continue;
2304 if (NodeOrder.count(key: SuccSU) == 0)
2305 Succs.insert(X: SuccSU);
2306 }
2307
2308 // FIXME: The following loop-carried dependencies may also need to be
2309 // considered.
2310 // - Physical register dependnecies (true-dependnece and WAW).
2311 // - Memory dependencies.
2312 for (const auto &IE : DDG->getInEdges(SU)) {
2313 SUnit *PredSU = IE.getSrc();
2314 if (!IE.isAntiDep())
2315 continue;
2316 if (S && S->count(SU: PredSU) == 0)
2317 continue;
2318 if (NodeOrder.count(key: PredSU) == 0)
2319 Succs.insert(X: PredSU);
2320 }
2321 }
2322 return !Succs.empty();
2323}
2324
2325/// Return true if there is a path from the specified node to any of the nodes
2326/// in DestNodes. Keep track and return the nodes in any path.
2327static bool computePath(SUnit *Cur, SetVector<SUnit *> &Path,
2328 SetVector<SUnit *> &DestNodes,
2329 SetVector<SUnit *> &Exclude,
2330 SmallPtrSet<SUnit *, 8> &Visited,
2331 SwingSchedulerDDG *DDG) {
2332 if (Cur->isBoundaryNode())
2333 return false;
2334 if (Exclude.contains(key: Cur))
2335 return false;
2336 if (DestNodes.contains(key: Cur))
2337 return true;
2338 if (!Visited.insert(Ptr: Cur).second)
2339 return Path.contains(key: Cur);
2340 bool FoundPath = false;
2341 for (const auto &OE : DDG->getOutEdges(SU: Cur))
2342 if (!OE.ignoreDependence(IgnoreAnti: false))
2343 FoundPath |=
2344 computePath(Cur: OE.getDst(), Path, DestNodes, Exclude, Visited, DDG);
2345 for (const auto &IE : DDG->getInEdges(SU: Cur))
2346 if (IE.isAntiDep() && IE.getDistance() == 0)
2347 FoundPath |=
2348 computePath(Cur: IE.getSrc(), Path, DestNodes, Exclude, Visited, DDG);
2349 if (FoundPath)
2350 Path.insert(X: Cur);
2351 return FoundPath;
2352}
2353
2354/// Compute the live-out registers for the instructions in a node-set.
2355/// The live-out registers are those that are defined in the node-set,
2356/// but not used. Except for use operands of Phis.
2357static void computeLiveOuts(MachineFunction &MF, RegPressureTracker &RPTracker,
2358 NodeSet &NS) {
2359 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
2360 MachineRegisterInfo &MRI = MF.getRegInfo();
2361 SmallVector<VRegMaskOrUnit, 8> LiveOutRegs;
2362 SmallSet<VirtRegOrUnit, 4> Uses;
2363 for (SUnit *SU : NS) {
2364 const MachineInstr *MI = SU->getInstr();
2365 if (MI->isPHI())
2366 continue;
2367 for (const MachineOperand &MO : MI->all_uses()) {
2368 Register Reg = MO.getReg();
2369 if (Reg.isVirtual())
2370 Uses.insert(V: VirtRegOrUnit(Reg));
2371 else if (MRI.isAllocatable(PhysReg: Reg))
2372 for (MCRegUnit Unit : TRI->regunits(Reg: Reg.asMCReg()))
2373 Uses.insert(V: VirtRegOrUnit(Unit));
2374 }
2375 }
2376 for (SUnit *SU : NS)
2377 for (const MachineOperand &MO : SU->getInstr()->all_defs())
2378 if (!MO.isDead()) {
2379 Register Reg = MO.getReg();
2380 if (Reg.isVirtual()) {
2381 if (!Uses.count(V: VirtRegOrUnit(Reg)))
2382 LiveOutRegs.emplace_back(Args: VirtRegOrUnit(Reg),
2383 Args: LaneBitmask::getNone());
2384 } else if (MRI.isAllocatable(PhysReg: Reg)) {
2385 for (MCRegUnit Unit : TRI->regunits(Reg: Reg.asMCReg()))
2386 if (!Uses.count(V: VirtRegOrUnit(Unit)))
2387 LiveOutRegs.emplace_back(Args: VirtRegOrUnit(Unit),
2388 Args: LaneBitmask::getNone());
2389 }
2390 }
2391 RPTracker.addLiveRegs(Regs: LiveOutRegs);
2392}
2393
2394/// A heuristic to filter nodes in recurrent node-sets if the register
2395/// pressure of a set is too high.
2396void SwingSchedulerDAG::registerPressureFilter(NodeSetType &NodeSets) {
2397 for (auto &NS : NodeSets) {
2398 // Skip small node-sets since they won't cause register pressure problems.
2399 if (NS.size() <= 2)
2400 continue;
2401 IntervalPressure RecRegPressure;
2402 RegPressureTracker RecRPTracker(RecRegPressure);
2403 RecRPTracker.init(mf: &MF, rci: &RegClassInfo, lis: &LIS, mbb: BB, pos: BB->end(), TrackLaneMasks: false, TrackUntiedDefs: true);
2404 computeLiveOuts(MF, RPTracker&: RecRPTracker, NS);
2405 RecRPTracker.closeBottom();
2406
2407 std::vector<SUnit *> SUnits(NS.begin(), NS.end());
2408 llvm::sort(C&: SUnits, Comp: [](const SUnit *A, const SUnit *B) {
2409 return A->NodeNum > B->NodeNum;
2410 });
2411
2412 for (auto &SU : SUnits) {
2413 // Since we're computing the register pressure for a subset of the
2414 // instructions in a block, we need to set the tracker for each
2415 // instruction in the node-set. The tracker is set to the instruction
2416 // just after the one we're interested in.
2417 MachineBasicBlock::const_iterator CurInstI = SU->getInstr();
2418 RecRPTracker.setPos(std::next(x: CurInstI));
2419
2420 RegPressureDelta RPDelta;
2421 ArrayRef<PressureChange> CriticalPSets;
2422 RecRPTracker.getMaxUpwardPressureDelta(MI: SU->getInstr(), PDiff: nullptr, Delta&: RPDelta,
2423 CriticalPSets,
2424 MaxPressureLimit: RecRegPressure.MaxSetPressure);
2425 if (RPDelta.Excess.isValid()) {
2426 LLVM_DEBUG(
2427 dbgs() << "Excess register pressure: SU(" << SU->NodeNum << ") "
2428 << TRI->getRegPressureSetName(RPDelta.Excess.getPSet())
2429 << ":" << RPDelta.Excess.getUnitInc() << "\n");
2430 NS.setExceedPressure(SU);
2431 break;
2432 }
2433 RecRPTracker.recede();
2434 }
2435 }
2436}
2437
2438/// A heuristic to colocate node sets that have the same set of
2439/// successors.
2440void SwingSchedulerDAG::colocateNodeSets(NodeSetType &NodeSets) {
2441 unsigned Colocate = 0;
2442 for (int i = 0, e = NodeSets.size(); i < e; ++i) {
2443 NodeSet &N1 = NodeSets[i];
2444 SmallSetVector<SUnit *, 8> S1;
2445 if (N1.empty() || !succ_L(NodeOrder&: N1, Succs&: S1, DDG: DDG.get()))
2446 continue;
2447 for (int j = i + 1; j < e; ++j) {
2448 NodeSet &N2 = NodeSets[j];
2449 if (N1.compareRecMII(RHS&: N2) != 0)
2450 continue;
2451 SmallSetVector<SUnit *, 8> S2;
2452 if (N2.empty() || !succ_L(NodeOrder&: N2, Succs&: S2, DDG: DDG.get()))
2453 continue;
2454 if (llvm::set_is_subset(S1, S2) && S1.size() == S2.size()) {
2455 N1.setColocate(++Colocate);
2456 N2.setColocate(Colocate);
2457 break;
2458 }
2459 }
2460 }
2461}
2462
2463/// Check if the existing node-sets are profitable. If not, then ignore the
2464/// recurrent node-sets, and attempt to schedule all nodes together. This is
2465/// a heuristic. If the MII is large and all the recurrent node-sets are small,
2466/// then it's best to try to schedule all instructions together instead of
2467/// starting with the recurrent node-sets.
2468void SwingSchedulerDAG::checkNodeSets(NodeSetType &NodeSets) {
2469 // Look for loops with a large MII.
2470 if (MII < 17)
2471 return;
2472 // Check if the node-set contains only a simple add recurrence.
2473 for (auto &NS : NodeSets) {
2474 if (NS.getRecMII() > 2)
2475 return;
2476 if (NS.getMaxDepth() > MII)
2477 return;
2478 }
2479 NodeSets.clear();
2480 LLVM_DEBUG(dbgs() << "Clear recurrence node-sets\n");
2481}
2482
2483/// Add the nodes that do not belong to a recurrence set into groups
2484/// based upon connected components.
2485void SwingSchedulerDAG::groupRemainingNodes(NodeSetType &NodeSets) {
2486 SetVector<SUnit *> NodesAdded;
2487 SmallPtrSet<SUnit *, 8> Visited;
2488 // Add the nodes that are on a path between the previous node sets and
2489 // the current node set.
2490 for (NodeSet &I : NodeSets) {
2491 SmallSetVector<SUnit *, 8> N;
2492 // Add the nodes from the current node set to the previous node set.
2493 if (succ_L(NodeOrder&: I, Succs&: N, DDG: DDG.get())) {
2494 SetVector<SUnit *> Path;
2495 for (SUnit *NI : N) {
2496 Visited.clear();
2497 computePath(Cur: NI, Path, DestNodes&: NodesAdded, Exclude&: I, Visited, DDG: DDG.get());
2498 }
2499 if (!Path.empty())
2500 I.insert(S: Path.begin(), E: Path.end());
2501 }
2502 // Add the nodes from the previous node set to the current node set.
2503 N.clear();
2504 if (succ_L(NodeOrder&: NodesAdded, Succs&: N, DDG: DDG.get())) {
2505 SetVector<SUnit *> Path;
2506 for (SUnit *NI : N) {
2507 Visited.clear();
2508 computePath(Cur: NI, Path, DestNodes&: I, Exclude&: NodesAdded, Visited, DDG: DDG.get());
2509 }
2510 if (!Path.empty())
2511 I.insert(S: Path.begin(), E: Path.end());
2512 }
2513 NodesAdded.insert_range(R&: I);
2514 }
2515
2516 // Create a new node set with the connected nodes of any successor of a node
2517 // in a recurrent set.
2518 NodeSet NewSet;
2519 SmallSetVector<SUnit *, 8> N;
2520 if (succ_L(NodeOrder&: NodesAdded, Succs&: N, DDG: DDG.get()))
2521 for (SUnit *I : N)
2522 addConnectedNodes(SU: I, NewSet, NodesAdded);
2523 if (!NewSet.empty())
2524 NodeSets.push_back(Elt: NewSet);
2525
2526 // Create a new node set with the connected nodes of any predecessor of a node
2527 // in a recurrent set.
2528 NewSet.clear();
2529 if (pred_L(NodeOrder&: NodesAdded, Preds&: N, DDG: DDG.get()))
2530 for (SUnit *I : N)
2531 addConnectedNodes(SU: I, NewSet, NodesAdded);
2532 if (!NewSet.empty())
2533 NodeSets.push_back(Elt: NewSet);
2534
2535 // Create new nodes sets with the connected nodes any remaining node that
2536 // has no predecessor.
2537 for (SUnit &SU : SUnits) {
2538 if (NodesAdded.count(key: &SU) == 0) {
2539 NewSet.clear();
2540 addConnectedNodes(SU: &SU, NewSet, NodesAdded);
2541 if (!NewSet.empty())
2542 NodeSets.push_back(Elt: NewSet);
2543 }
2544 }
2545}
2546
2547/// Add the node to the set, and add all of its connected nodes to the set.
2548void SwingSchedulerDAG::addConnectedNodes(SUnit *SU, NodeSet &NewSet,
2549 SetVector<SUnit *> &NodesAdded) {
2550 NewSet.insert(SU);
2551 NodesAdded.insert(X: SU);
2552 for (auto &OE : DDG->getOutEdges(SU)) {
2553 SUnit *Successor = OE.getDst();
2554 if (!OE.isArtificial() && !Successor->isBoundaryNode() &&
2555 NodesAdded.count(key: Successor) == 0)
2556 addConnectedNodes(SU: Successor, NewSet, NodesAdded);
2557 }
2558 for (auto &IE : DDG->getInEdges(SU)) {
2559 SUnit *Predecessor = IE.getSrc();
2560 if (!IE.isArtificial() && NodesAdded.count(key: Predecessor) == 0)
2561 addConnectedNodes(SU: Predecessor, NewSet, NodesAdded);
2562 }
2563}
2564
2565/// Return true if Set1 contains elements in Set2. The elements in common
2566/// are returned in a different container.
2567static bool isIntersect(SmallSetVector<SUnit *, 8> &Set1, const NodeSet &Set2,
2568 SmallSetVector<SUnit *, 8> &Result) {
2569 Result.clear();
2570 for (SUnit *SU : Set1) {
2571 if (Set2.count(SU) != 0)
2572 Result.insert(X: SU);
2573 }
2574 return !Result.empty();
2575}
2576
2577/// Merge the recurrence node sets that have the same initial node.
2578void SwingSchedulerDAG::fuseRecs(NodeSetType &NodeSets) {
2579 for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E;
2580 ++I) {
2581 NodeSet &NI = *I;
2582 for (NodeSetType::iterator J = I + 1; J != E;) {
2583 NodeSet &NJ = *J;
2584 if (NI.getNode(i: 0)->NodeNum == NJ.getNode(i: 0)->NodeNum) {
2585 if (NJ.compareRecMII(RHS&: NI) > 0)
2586 NI.setRecMII(NJ.getRecMII());
2587 for (SUnit *SU : *J)
2588 I->insert(SU);
2589 NodeSets.erase(CI: J);
2590 E = NodeSets.end();
2591 } else {
2592 ++J;
2593 }
2594 }
2595 }
2596}
2597
2598/// Remove nodes that have been scheduled in previous NodeSets.
2599void SwingSchedulerDAG::removeDuplicateNodes(NodeSetType &NodeSets) {
2600 for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E;
2601 ++I)
2602 for (NodeSetType::iterator J = I + 1; J != E;) {
2603 J->remove_if(P: [&](SUnit *SUJ) { return I->count(SU: SUJ); });
2604
2605 if (J->empty()) {
2606 NodeSets.erase(CI: J);
2607 E = NodeSets.end();
2608 } else {
2609 ++J;
2610 }
2611 }
2612}
2613
2614/// Compute an ordered list of the dependence graph nodes, which
2615/// indicates the order that the nodes will be scheduled. This is a
2616/// two-level algorithm. First, a partial order is created, which
2617/// consists of a list of sets ordered from highest to lowest priority.
2618void SwingSchedulerDAG::computeNodeOrder(NodeSetType &NodeSets) {
2619 SmallSetVector<SUnit *, 8> R;
2620 NodeOrder.clear();
2621
2622 for (auto &Nodes : NodeSets) {
2623 LLVM_DEBUG(dbgs() << "NodeSet size " << Nodes.size() << "\n");
2624 OrderKind Order;
2625 SmallSetVector<SUnit *, 8> N;
2626 if (pred_L(NodeOrder, Preds&: N, DDG: DDG.get()) && llvm::set_is_subset(S1: N, S2: Nodes)) {
2627 R.insert_range(R&: N);
2628 Order = BottomUp;
2629 LLVM_DEBUG(dbgs() << " Bottom up (preds) ");
2630 } else if (succ_L(NodeOrder, Succs&: N, DDG: DDG.get()) &&
2631 llvm::set_is_subset(S1: N, S2: Nodes)) {
2632 R.insert_range(R&: N);
2633 Order = TopDown;
2634 LLVM_DEBUG(dbgs() << " Top down (succs) ");
2635 } else if (isIntersect(Set1&: N, Set2: Nodes, Result&: R)) {
2636 // If some of the successors are in the existing node-set, then use the
2637 // top-down ordering.
2638 Order = TopDown;
2639 LLVM_DEBUG(dbgs() << " Top down (intersect) ");
2640 } else if (NodeSets.size() == 1) {
2641 for (const auto &N : Nodes)
2642 if (N->Succs.size() == 0)
2643 R.insert(X: N);
2644 Order = BottomUp;
2645 LLVM_DEBUG(dbgs() << " Bottom up (all) ");
2646 } else {
2647 // Find the node with the highest ASAP.
2648 SUnit *maxASAP = nullptr;
2649 for (SUnit *SU : Nodes) {
2650 if (maxASAP == nullptr || getASAP(Node: SU) > getASAP(Node: maxASAP) ||
2651 (getASAP(Node: SU) == getASAP(Node: maxASAP) && SU->NodeNum > maxASAP->NodeNum))
2652 maxASAP = SU;
2653 }
2654 R.insert(X: maxASAP);
2655 Order = BottomUp;
2656 LLVM_DEBUG(dbgs() << " Bottom up (default) ");
2657 }
2658
2659 while (!R.empty()) {
2660 if (Order == TopDown) {
2661 // Choose the node with the maximum height. If more than one, choose
2662 // the node wiTH the maximum ZeroLatencyHeight. If still more than one,
2663 // choose the node with the lowest MOV.
2664 while (!R.empty()) {
2665 SUnit *maxHeight = nullptr;
2666 for (SUnit *I : R) {
2667 if (maxHeight == nullptr || getHeight(Node: I) > getHeight(Node: maxHeight))
2668 maxHeight = I;
2669 else if (getHeight(Node: I) == getHeight(Node: maxHeight) &&
2670 getZeroLatencyHeight(Node: I) > getZeroLatencyHeight(Node: maxHeight))
2671 maxHeight = I;
2672 else if (getHeight(Node: I) == getHeight(Node: maxHeight) &&
2673 getZeroLatencyHeight(Node: I) ==
2674 getZeroLatencyHeight(Node: maxHeight) &&
2675 getMOV(Node: I) < getMOV(Node: maxHeight))
2676 maxHeight = I;
2677 }
2678 NodeOrder.insert(X: maxHeight);
2679 LLVM_DEBUG(dbgs() << maxHeight->NodeNum << " ");
2680 R.remove(X: maxHeight);
2681 for (const auto &OE : DDG->getOutEdges(SU: maxHeight)) {
2682 SUnit *SU = OE.getDst();
2683 if (Nodes.count(SU) == 0)
2684 continue;
2685 if (NodeOrder.contains(key: SU))
2686 continue;
2687 if (OE.ignoreDependence(IgnoreAnti: false))
2688 continue;
2689 R.insert(X: SU);
2690 }
2691
2692 // FIXME: The following loop-carried dependencies may also need to be
2693 // considered.
2694 // - Physical register dependnecies (true-dependnece and WAW).
2695 // - Memory dependencies.
2696 for (const auto &IE : DDG->getInEdges(SU: maxHeight)) {
2697 SUnit *SU = IE.getSrc();
2698 if (!IE.isAntiDep())
2699 continue;
2700 if (Nodes.count(SU) == 0)
2701 continue;
2702 if (NodeOrder.contains(key: SU))
2703 continue;
2704 R.insert(X: SU);
2705 }
2706 }
2707 Order = BottomUp;
2708 LLVM_DEBUG(dbgs() << "\n Switching order to bottom up ");
2709 SmallSetVector<SUnit *, 8> N;
2710 if (pred_L(NodeOrder, Preds&: N, DDG: DDG.get(), S: &Nodes))
2711 R.insert_range(R&: N);
2712 } else {
2713 // Choose the node with the maximum depth. If more than one, choose
2714 // the node with the maximum ZeroLatencyDepth. If still more than one,
2715 // choose the node with the lowest MOV.
2716 while (!R.empty()) {
2717 SUnit *maxDepth = nullptr;
2718 for (SUnit *I : R) {
2719 if (maxDepth == nullptr || getDepth(Node: I) > getDepth(Node: maxDepth))
2720 maxDepth = I;
2721 else if (getDepth(Node: I) == getDepth(Node: maxDepth) &&
2722 getZeroLatencyDepth(Node: I) > getZeroLatencyDepth(Node: maxDepth))
2723 maxDepth = I;
2724 else if (getDepth(Node: I) == getDepth(Node: maxDepth) &&
2725 getZeroLatencyDepth(Node: I) == getZeroLatencyDepth(Node: maxDepth) &&
2726 getMOV(Node: I) < getMOV(Node: maxDepth))
2727 maxDepth = I;
2728 }
2729 NodeOrder.insert(X: maxDepth);
2730 LLVM_DEBUG(dbgs() << maxDepth->NodeNum << " ");
2731 R.remove(X: maxDepth);
2732 if (Nodes.isExceedSU(SU: maxDepth)) {
2733 Order = TopDown;
2734 R.clear();
2735 R.insert(X: Nodes.getNode(i: 0));
2736 break;
2737 }
2738 for (const auto &IE : DDG->getInEdges(SU: maxDepth)) {
2739 SUnit *SU = IE.getSrc();
2740 if (Nodes.count(SU) == 0)
2741 continue;
2742 if (NodeOrder.contains(key: SU))
2743 continue;
2744 R.insert(X: SU);
2745 }
2746
2747 // FIXME: The following loop-carried dependencies may also need to be
2748 // considered.
2749 // - Physical register dependnecies (true-dependnece and WAW).
2750 // - Memory dependencies.
2751 for (const auto &OE : DDG->getOutEdges(SU: maxDepth)) {
2752 SUnit *SU = OE.getDst();
2753 if (!OE.isAntiDep())
2754 continue;
2755 if (Nodes.count(SU) == 0)
2756 continue;
2757 if (NodeOrder.contains(key: SU))
2758 continue;
2759 R.insert(X: SU);
2760 }
2761 }
2762 Order = TopDown;
2763 LLVM_DEBUG(dbgs() << "\n Switching order to top down ");
2764 SmallSetVector<SUnit *, 8> N;
2765 if (succ_L(NodeOrder, Succs&: N, DDG: DDG.get(), S: &Nodes))
2766 R.insert_range(R&: N);
2767 }
2768 }
2769 LLVM_DEBUG(dbgs() << "\nDone with Nodeset\n");
2770 }
2771
2772 LLVM_DEBUG({
2773 dbgs() << "Node order: ";
2774 for (SUnit *I : NodeOrder)
2775 dbgs() << " " << I->NodeNum << " ";
2776 dbgs() << "\n";
2777 });
2778}
2779
2780/// Set the policy for this loop, allowing the target to override it.
2781void SwingSchedulerDAG::initPolicy() {
2782 MF.getSubtarget().overridePipelinerPolicy(Policy);
2783
2784 // After subtarget overrides, apply command line options.
2785 if (LimitRegPressure.getNumOccurrences())
2786 Policy.ShouldLimitRegPressure = LimitRegPressure;
2787}
2788
2789/// Process the nodes in the computed order and create the pipelined schedule
2790/// of the instructions, if possible. Return true if a schedule is found.
2791bool SwingSchedulerDAG::schedulePipeline(SMSchedule &Schedule) {
2792
2793 if (NodeOrder.empty()){
2794 LLVM_DEBUG(dbgs() << "NodeOrder is empty! abort scheduling\n" );
2795 return false;
2796 }
2797
2798 bool scheduleFound = false;
2799 std::unique_ptr<HighRegisterPressureDetector> HRPDetector;
2800 if (Policy.ShouldLimitRegPressure) {
2801 HRPDetector =
2802 std::make_unique<HighRegisterPressureDetector>(args: Loop.getHeader(), args&: MF);
2803 HRPDetector->init(RCI: RegClassInfo);
2804 }
2805 // Keep increasing II until a valid schedule is found.
2806 for (unsigned II = MII; II <= MAX_II && !scheduleFound; ++II) {
2807 Schedule.reset();
2808 Schedule.setInitiationInterval(II);
2809 LLVM_DEBUG(dbgs() << "Try to schedule with " << II << "\n");
2810
2811 SetVector<SUnit *>::iterator NI = NodeOrder.begin();
2812 SetVector<SUnit *>::iterator NE = NodeOrder.end();
2813 do {
2814 SUnit *SU = *NI;
2815
2816 // Compute the schedule time for the instruction, which is based
2817 // upon the scheduled time for any predecessors/successors.
2818 int EarlyStart = INT_MIN;
2819 int LateStart = INT_MAX;
2820 Schedule.computeStart(SU, MaxEarlyStart: &EarlyStart, MinLateStart: &LateStart, II, DAG: this);
2821 LLVM_DEBUG({
2822 dbgs() << "\n";
2823 dbgs() << "Inst (" << SU->NodeNum << ") ";
2824 SU->getInstr()->dump();
2825 dbgs() << "\n";
2826 });
2827 LLVM_DEBUG(
2828 dbgs() << format("\tes: %8x ls: %8x\n", EarlyStart, LateStart));
2829
2830 if (EarlyStart > LateStart)
2831 scheduleFound = false;
2832 else if (EarlyStart != INT_MIN && LateStart == INT_MAX)
2833 scheduleFound =
2834 Schedule.insert(SU, StartCycle: EarlyStart, EndCycle: EarlyStart + (int)II - 1, II);
2835 else if (EarlyStart == INT_MIN && LateStart != INT_MAX)
2836 scheduleFound =
2837 Schedule.insert(SU, StartCycle: LateStart, EndCycle: LateStart - (int)II + 1, II);
2838 else if (EarlyStart != INT_MIN && LateStart != INT_MAX) {
2839 LateStart = std::min(a: LateStart, b: EarlyStart + (int)II - 1);
2840 // When scheduling a Phi it is better to start at the late cycle and
2841 // go backwards. The default order may insert the Phi too far away
2842 // from its first dependence.
2843 // Also, do backward search when all scheduled predecessors are
2844 // loop-carried output/order dependencies. Empirically, there are also
2845 // cases where scheduling becomes possible with backward search.
2846 if (SU->getInstr()->isPHI() ||
2847 Schedule.onlyHasLoopCarriedOutputOrOrderPreds(SU, DDG: this->getDDG()))
2848 scheduleFound = Schedule.insert(SU, StartCycle: LateStart, EndCycle: EarlyStart, II);
2849 else
2850 scheduleFound = Schedule.insert(SU, StartCycle: EarlyStart, EndCycle: LateStart, II);
2851 } else {
2852 int FirstCycle = Schedule.getFirstCycle();
2853 scheduleFound = Schedule.insert(SU, StartCycle: FirstCycle + getASAP(Node: SU),
2854 EndCycle: FirstCycle + getASAP(Node: SU) + II - 1, II);
2855 }
2856
2857 // Even if we find a schedule, make sure the schedule doesn't exceed the
2858 // allowable number of stages. We keep trying if this happens.
2859 if (scheduleFound)
2860 if (SwpMaxStages > -1 &&
2861 Schedule.getMaxStageCount() > (unsigned)SwpMaxStages)
2862 scheduleFound = false;
2863
2864 LLVM_DEBUG({
2865 if (!scheduleFound)
2866 dbgs() << "\tCan't schedule\n";
2867 });
2868 } while (++NI != NE && scheduleFound);
2869
2870 // If a schedule is found, validate it against the validation-only
2871 // dependencies.
2872 if (scheduleFound)
2873 scheduleFound = DDG->isValidSchedule(Schedule);
2874
2875 // If a schedule is found, ensure non-pipelined instructions are in stage 0
2876 if (scheduleFound)
2877 scheduleFound =
2878 Schedule.normalizeNonPipelinedInstructions(SSD: this, PLI: LoopPipelinerInfo);
2879
2880 // If a schedule is found, check if it is a valid schedule too.
2881 if (scheduleFound)
2882 scheduleFound = Schedule.isValidSchedule(SSD: this);
2883
2884 // If a schedule was found and the detector is enabled, check if the
2885 // schedule might generate additional register spills/fills.
2886 if (scheduleFound && HRPDetector)
2887 scheduleFound =
2888 !HRPDetector->detect(SSD: this, Schedule, MaxStage: Schedule.getMaxStageCount());
2889 }
2890
2891 LLVM_DEBUG(dbgs() << "Schedule Found? " << scheduleFound
2892 << " (II=" << Schedule.getInitiationInterval()
2893 << ")\n");
2894
2895 if (scheduleFound) {
2896 scheduleFound = LoopPipelinerInfo->shouldUseSchedule(SSD&: *this, SMS&: Schedule);
2897 if (!scheduleFound)
2898 LLVM_DEBUG(dbgs() << "Target rejected schedule\n");
2899 }
2900
2901 if (scheduleFound) {
2902 Schedule.finalizeSchedule(SSD: this);
2903 Pass.ORE->emit(RemarkBuilder: [&]() {
2904 return MachineOptimizationRemarkAnalysis(
2905 DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
2906 << "Schedule found with Initiation Interval: "
2907 << ore::NV("II", Schedule.getInitiationInterval())
2908 << ", MaxStageCount: "
2909 << ore::NV("MaxStageCount", Schedule.getMaxStageCount());
2910 });
2911 } else
2912 Schedule.reset();
2913
2914 return scheduleFound && Schedule.getMaxStageCount() > 0;
2915}
2916
2917static Register findUniqueOperandDefinedInLoop(const MachineInstr &MI) {
2918 const MachineRegisterInfo &MRI = MI.getParent()->getParent()->getRegInfo();
2919 Register Result;
2920 for (const MachineOperand &Use : MI.all_uses()) {
2921 Register Reg = Use.getReg();
2922 if (!Reg.isVirtual())
2923 return Register();
2924 if (MRI.getDefBlock(Reg) != MI.getParent())
2925 continue;
2926 if (Result)
2927 return Register();
2928 Result = Reg;
2929 }
2930 return Result;
2931}
2932
2933/// When Op is a value that is incremented recursively in a loop and there is a
2934/// unique instruction that increments it, returns true and sets Value.
2935static bool findLoopIncrementValue(const MachineOperand &Op, int &Value) {
2936 if (!Op.isReg() || !Op.getReg().isVirtual())
2937 return false;
2938
2939 Register OrgReg = Op.getReg();
2940 Register CurReg = OrgReg;
2941 const MachineBasicBlock *LoopBB = Op.getParent()->getParent();
2942 const MachineRegisterInfo &MRI = LoopBB->getParent()->getRegInfo();
2943
2944 const TargetInstrInfo *TII =
2945 LoopBB->getParent()->getSubtarget().getInstrInfo();
2946 const TargetRegisterInfo *TRI =
2947 LoopBB->getParent()->getSubtarget().getRegisterInfo();
2948
2949 MachineInstr *Phi = nullptr;
2950 MachineInstr *Increment = nullptr;
2951
2952 // Traverse definitions until it reaches Op or an instruction that does not
2953 // satisfy the condition.
2954 // Acceptable example:
2955 // bb.0:
2956 // %0 = PHI %3, %bb.0, ...
2957 // %2 = ADD %0, Value
2958 // ... = LOAD %2(Op)
2959 // %3 = COPY %2
2960 while (true) {
2961 if (!CurReg.isValid() || !CurReg.isVirtual())
2962 return false;
2963 MachineInstr *Def = MRI.getVRegDef(Reg: CurReg);
2964 if (Def->getParent() != LoopBB)
2965 return false;
2966
2967 if (Def->isCopy()) {
2968 // Ignore copy instructions unless they contain subregisters
2969 if (Def->getOperand(i: 0).getSubReg() || Def->getOperand(i: 1).getSubReg())
2970 return false;
2971 CurReg = Def->getOperand(i: 1).getReg();
2972 } else if (Def->isPHI()) {
2973 // There must be just one Phi
2974 if (Phi)
2975 return false;
2976 Phi = Def;
2977 CurReg = getLoopPhiReg(Phi: *Def, LoopBB);
2978 } else if (TII->getIncrementValue(MI: *Def, Value)) {
2979 // Potentially a unique increment
2980 if (Increment)
2981 // Multiple increments exist
2982 return false;
2983
2984 const MachineOperand *BaseOp;
2985 int64_t Offset;
2986 bool OffsetIsScalable;
2987 if (TII->getMemOperandWithOffset(MI: *Def, BaseOp, Offset, OffsetIsScalable,
2988 TRI)) {
2989 // Pre/post increment instruction
2990 CurReg = BaseOp->getReg();
2991 } else {
2992 // If only one of the operands is defined within the loop, it is assumed
2993 // to be an incremented value.
2994 CurReg = findUniqueOperandDefinedInLoop(MI: *Def);
2995 if (!CurReg.isValid())
2996 return false;
2997 }
2998 Increment = Def;
2999 } else {
3000 return false;
3001 }
3002 if (CurReg == OrgReg)
3003 break;
3004 }
3005
3006 if (!Phi || !Increment)
3007 return false;
3008
3009 return true;
3010}
3011
3012/// Return true if we can compute the amount the instruction changes
3013/// during each iteration. Set Delta to the amount of the change.
3014bool SwingSchedulerDAG::computeDelta(const MachineInstr &MI, int &Delta) const {
3015 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
3016 const MachineOperand *BaseOp;
3017 int64_t Offset;
3018 bool OffsetIsScalable;
3019 if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable, TRI))
3020 return false;
3021
3022 // FIXME: This algorithm assumes instructions have fixed-size offsets.
3023 if (OffsetIsScalable)
3024 return false;
3025
3026 if (!BaseOp->isReg())
3027 return false;
3028
3029 return findLoopIncrementValue(Op: *BaseOp, Value&: Delta);
3030}
3031
3032/// Check if we can change the instruction to use an offset value from the
3033/// previous iteration. If so, return true and set the base and offset values
3034/// so that we can rewrite the load, if necessary.
3035/// v1 = Phi(v0, v3)
3036/// v2 = load v1, 0
3037/// v3 = post_store v1, 4, x
3038/// This function enables the load to be rewritten as v2 = load v3, 4.
3039bool SwingSchedulerDAG::canUseLastOffsetValue(MachineInstr *MI,
3040 unsigned &BasePos,
3041 unsigned &OffsetPos,
3042 Register &NewBase,
3043 int64_t &Offset) {
3044 // Get the load instruction.
3045 if (TII->isPostIncrement(MI: *MI))
3046 return false;
3047 unsigned BasePosLd, OffsetPosLd;
3048 if (!TII->getBaseAndOffsetPosition(MI: *MI, BasePos&: BasePosLd, OffsetPos&: OffsetPosLd))
3049 return false;
3050 Register BaseReg = MI->getOperand(i: BasePosLd).getReg();
3051
3052 // Look for the Phi instruction.
3053 MachineRegisterInfo &MRI = MI->getMF()->getRegInfo();
3054 MachineInstr *Phi = MRI.getVRegDef(Reg: BaseReg);
3055 if (!Phi || !Phi->isPHI())
3056 return false;
3057 // Get the register defined in the loop block.
3058 Register PrevReg = getLoopPhiReg(Phi: *Phi, LoopBB: MI->getParent());
3059 if (!PrevReg)
3060 return false;
3061
3062 // Check for the post-increment load/store instruction.
3063 MachineInstr *PrevDef = MRI.getVRegDef(Reg: PrevReg);
3064 if (!PrevDef || PrevDef == MI)
3065 return false;
3066
3067 if (!TII->isPostIncrement(MI: *PrevDef))
3068 return false;
3069
3070 unsigned BasePos1 = 0, OffsetPos1 = 0;
3071 if (!TII->getBaseAndOffsetPosition(MI: *PrevDef, BasePos&: BasePos1, OffsetPos&: OffsetPos1))
3072 return false;
3073
3074 // Make sure that the instructions do not access the same memory location in
3075 // the next iteration.
3076 int64_t LoadOffset = MI->getOperand(i: OffsetPosLd).getImm();
3077 int64_t StoreOffset = PrevDef->getOperand(i: OffsetPos1).getImm();
3078 MachineInstr *NewMI = MF.CloneMachineInstr(Orig: MI);
3079 NewMI->getOperand(i: OffsetPosLd).setImm(LoadOffset + StoreOffset);
3080 bool Disjoint = TII->areMemAccessesTriviallyDisjoint(MIa: *NewMI, MIb: *PrevDef);
3081 MF.deleteMachineInstr(MI: NewMI);
3082 if (!Disjoint)
3083 return false;
3084
3085 // Set the return value once we determine that we return true.
3086 BasePos = BasePosLd;
3087 OffsetPos = OffsetPosLd;
3088 NewBase = PrevReg;
3089 Offset = StoreOffset;
3090 return true;
3091}
3092
3093/// Apply changes to the instruction if needed. The changes are need
3094/// to improve the scheduling and depend up on the final schedule.
3095void SwingSchedulerDAG::applyInstrChange(MachineInstr *MI,
3096 SMSchedule &Schedule) {
3097 SUnit *SU = getSUnit(MI);
3098 DenseMap<SUnit *, std::pair<Register, int64_t>>::iterator It =
3099 InstrChanges.find(Val: SU);
3100 if (It != InstrChanges.end()) {
3101 std::pair<Register, int64_t> RegAndOffset = It->second;
3102 unsigned BasePos, OffsetPos;
3103 if (!TII->getBaseAndOffsetPosition(MI: *MI, BasePos, OffsetPos))
3104 return;
3105 Register BaseReg = MI->getOperand(i: BasePos).getReg();
3106 MachineInstr *LoopDef = findDefInLoop(Reg: BaseReg);
3107 int DefStageNum = Schedule.stageScheduled(SU: getSUnit(MI: LoopDef));
3108 int DefCycleNum = Schedule.cycleScheduled(SU: getSUnit(MI: LoopDef));
3109 int BaseStageNum = Schedule.stageScheduled(SU);
3110 int BaseCycleNum = Schedule.cycleScheduled(SU);
3111 if (BaseStageNum < DefStageNum) {
3112 MachineInstr *NewMI = MF.CloneMachineInstr(Orig: MI);
3113 int OffsetDiff = DefStageNum - BaseStageNum;
3114 if (DefCycleNum < BaseCycleNum) {
3115 NewMI->getOperand(i: BasePos).setReg(RegAndOffset.first);
3116 if (OffsetDiff > 0)
3117 --OffsetDiff;
3118 }
3119 int64_t NewOffset =
3120 MI->getOperand(i: OffsetPos).getImm() + RegAndOffset.second * OffsetDiff;
3121 NewMI->getOperand(i: OffsetPos).setImm(NewOffset);
3122 SU->setInstr(NewMI);
3123 MISUnitMap[NewMI] = SU;
3124 NewMIs[MI] = NewMI;
3125 }
3126 }
3127}
3128
3129/// Return the instruction in the loop that defines the register.
3130/// If the definition is a Phi, then follow the Phi operand to
3131/// the instruction in the loop.
3132MachineInstr *SwingSchedulerDAG::findDefInLoop(Register Reg) {
3133 SmallPtrSet<MachineInstr *, 8> Visited;
3134 MachineInstr *Def = MRI.getVRegDef(Reg);
3135 while (Def->isPHI()) {
3136 if (!Visited.insert(Ptr: Def).second)
3137 break;
3138 for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2)
3139 if (Def->getOperand(i: i + 1).getMBB() == BB) {
3140 Def = MRI.getVRegDef(Reg: Def->getOperand(i).getReg());
3141 break;
3142 }
3143 }
3144 return Def;
3145}
3146
3147/// Return false if there is no overlap between the region accessed by BaseMI in
3148/// an iteration and the region accessed by OtherMI in subsequent iterations.
3149bool SwingSchedulerDAG::mayOverlapInLaterIter(
3150 const MachineInstr *BaseMI, const MachineInstr *OtherMI) const {
3151 int DeltaB, DeltaO, Delta;
3152 if (!computeDelta(MI: *BaseMI, Delta&: DeltaB) || !computeDelta(MI: *OtherMI, Delta&: DeltaO) ||
3153 DeltaB != DeltaO)
3154 return true;
3155 Delta = DeltaB;
3156
3157 const MachineOperand *BaseOpB, *BaseOpO;
3158 int64_t OffsetB, OffsetO;
3159 bool OffsetBIsScalable, OffsetOIsScalable;
3160 const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
3161 if (!TII->getMemOperandWithOffset(MI: *BaseMI, BaseOp&: BaseOpB, Offset&: OffsetB,
3162 OffsetIsScalable&: OffsetBIsScalable, TRI) ||
3163 !TII->getMemOperandWithOffset(MI: *OtherMI, BaseOp&: BaseOpO, Offset&: OffsetO,
3164 OffsetIsScalable&: OffsetOIsScalable, TRI))
3165 return true;
3166
3167 if (OffsetBIsScalable || OffsetOIsScalable)
3168 return true;
3169
3170 if (!BaseOpB->isIdenticalTo(Other: *BaseOpO)) {
3171 // Pass cases with different base operands but same initial values.
3172 // Typically for when pre/post increment is used.
3173
3174 if (!BaseOpB->isReg() || !BaseOpO->isReg())
3175 return true;
3176 Register RegB = BaseOpB->getReg(), RegO = BaseOpO->getReg();
3177 if (!RegB.isVirtual() || !RegO.isVirtual())
3178 return true;
3179
3180 MachineInstr *DefB = MRI.getVRegDef(Reg: BaseOpB->getReg());
3181 MachineInstr *DefO = MRI.getVRegDef(Reg: BaseOpO->getReg());
3182 if (!DefB || !DefO || !DefB->isPHI() || !DefO->isPHI())
3183 return true;
3184
3185 Register InitValB;
3186 Register LoopValB;
3187 Register InitValO;
3188 Register LoopValO;
3189 getPhiRegs(Phi&: *DefB, Loop: BB, InitVal&: InitValB, LoopVal&: LoopValB);
3190 getPhiRegs(Phi&: *DefO, Loop: BB, InitVal&: InitValO, LoopVal&: LoopValO);
3191 MachineInstr *InitDefB = MRI.getVRegDef(Reg: InitValB);
3192 MachineInstr *InitDefO = MRI.getVRegDef(Reg: InitValO);
3193
3194 if (!InitDefB->isIdenticalTo(Other: *InitDefO))
3195 return true;
3196 }
3197
3198 LocationSize AccessSizeB = (*BaseMI->memoperands_begin())->getSize();
3199 LocationSize AccessSizeO = (*OtherMI->memoperands_begin())->getSize();
3200
3201 // This is the main test, which checks the offset values and the loop
3202 // increment value to determine if the accesses may be loop carried.
3203 if (!AccessSizeB.hasValue() || !AccessSizeO.hasValue())
3204 return true;
3205
3206 LLVM_DEBUG({
3207 dbgs() << "Overlap check:\n";
3208 dbgs() << " BaseMI: ";
3209 BaseMI->dump();
3210 dbgs() << " Base + " << OffsetB << " + I * " << Delta
3211 << ", Len: " << AccessSizeB.getValue() << "\n";
3212 dbgs() << " OtherMI: ";
3213 OtherMI->dump();
3214 dbgs() << " Base + " << OffsetO << " + I * " << Delta
3215 << ", Len: " << AccessSizeO.getValue() << "\n";
3216 });
3217
3218 // Excessive overlap may be detected in strided patterns.
3219 // For example, the memory addresses of the store and the load in
3220 // for (i=0; i<n; i+=2) a[i+1] = a[i];
3221 // are assumed to overlap.
3222 if (Delta < 0) {
3223 int64_t BaseMinAddr = OffsetB;
3224 int64_t OhterNextIterMaxAddr = OffsetO + Delta + AccessSizeO.getValue() - 1;
3225 if (BaseMinAddr > OhterNextIterMaxAddr) {
3226 LLVM_DEBUG(dbgs() << " Result: No overlap\n");
3227 return false;
3228 }
3229 } else {
3230 int64_t BaseMaxAddr = OffsetB + AccessSizeB.getValue() - 1;
3231 int64_t OtherNextIterMinAddr = OffsetO + Delta;
3232 if (BaseMaxAddr < OtherNextIterMinAddr) {
3233 LLVM_DEBUG(dbgs() << " Result: No overlap\n");
3234 return false;
3235 }
3236 }
3237 LLVM_DEBUG(dbgs() << " Result: Overlap\n");
3238 return true;
3239}
3240
3241void SwingSchedulerDAG::postProcessDAG() {
3242 for (auto &M : Mutations)
3243 M->apply(DAG: this);
3244}
3245
3246/// Try to schedule the node at the specified StartCycle and continue
3247/// until the node is schedule or the EndCycle is reached. This function
3248/// returns true if the node is scheduled. This routine may search either
3249/// forward or backward for a place to insert the instruction based upon
3250/// the relative values of StartCycle and EndCycle.
3251bool SMSchedule::insert(SUnit *SU, int StartCycle, int EndCycle, int II) {
3252 bool forward = true;
3253 LLVM_DEBUG({
3254 dbgs() << "Trying to insert node between " << StartCycle << " and "
3255 << EndCycle << " II: " << II << "\n";
3256 });
3257 if (StartCycle > EndCycle)
3258 forward = false;
3259
3260 // The terminating condition depends on the direction.
3261 int termCycle = forward ? EndCycle + 1 : EndCycle - 1;
3262 for (int curCycle = StartCycle; curCycle != termCycle;
3263 forward ? ++curCycle : --curCycle) {
3264
3265 if (ST.getInstrInfo()->isZeroCost(Opcode: SU->getInstr()->getOpcode()) ||
3266 ProcItinResources.canReserveResources(SU&: *SU, Cycle: curCycle)) {
3267 LLVM_DEBUG({
3268 dbgs() << "\tinsert at cycle " << curCycle << " ";
3269 SU->getInstr()->dump();
3270 });
3271
3272 if (!ST.getInstrInfo()->isZeroCost(Opcode: SU->getInstr()->getOpcode()))
3273 ProcItinResources.reserveResources(SU&: *SU, Cycle: curCycle);
3274 ScheduledInstrs[curCycle].push_back(x: SU);
3275 InstrToCycle.insert(x: std::make_pair(x&: SU, y&: curCycle));
3276 if (curCycle > LastCycle)
3277 LastCycle = curCycle;
3278 if (curCycle < FirstCycle)
3279 FirstCycle = curCycle;
3280 return true;
3281 }
3282 LLVM_DEBUG({
3283 dbgs() << "\tfailed to insert at cycle " << curCycle << " ";
3284 SU->getInstr()->dump();
3285 });
3286 }
3287 return false;
3288}
3289
3290/// If an instruction has a use that spans multiple iterations, then
3291/// return true. These instructions are characterized by having a back-ege
3292/// to a Phi, which contains a reference to another Phi.
3293static SUnit *multipleIterations(SUnit *SU, SwingSchedulerDAG *DAG) {
3294 for (auto &P : SU->Preds)
3295 if (P.getKind() == SDep::Anti && P.getSUnit()->getInstr()->isPHI())
3296 for (auto &S : P.getSUnit()->Succs)
3297 if (S.getKind() == SDep::Data && S.getSUnit()->getInstr()->isPHI())
3298 return P.getSUnit();
3299 return nullptr;
3300}
3301
3302/// Compute the scheduling start slot for the instruction. The start slot
3303/// depends on any predecessor or successor nodes scheduled already.
3304void SMSchedule::computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart,
3305 int II, SwingSchedulerDAG *DAG) {
3306 const SwingSchedulerDDG *DDG = DAG->getDDG();
3307
3308 // Iterate over each instruction that has been scheduled already. The start
3309 // slot computation depends on whether the previously scheduled instruction
3310 // is a predecessor or successor of the specified instruction.
3311 for (int cycle = getFirstCycle(); cycle <= LastCycle; ++cycle) {
3312 for (SUnit *I : getInstructions(cycle)) {
3313 for (const auto &IE : DDG->getInEdges(SU)) {
3314 if (IE.getSrc() == I) {
3315 int EarlyStart = cycle + IE.getLatency() - IE.getDistance() * II;
3316 *MaxEarlyStart = std::max(a: *MaxEarlyStart, b: EarlyStart);
3317 }
3318 }
3319
3320 for (const auto &OE : DDG->getOutEdges(SU)) {
3321 if (OE.getDst() == I) {
3322 int LateStart = cycle - OE.getLatency() + OE.getDistance() * II;
3323 *MinLateStart = std::min(a: *MinLateStart, b: LateStart);
3324 }
3325 }
3326
3327 SUnit *BE = multipleIterations(SU: I, DAG);
3328 for (const auto &Dep : SU->Preds) {
3329 // For instruction that requires multiple iterations, make sure that
3330 // the dependent instruction is not scheduled past the definition.
3331 if (BE && Dep.getSUnit() == BE && !SU->getInstr()->isPHI() &&
3332 !SU->isPred(N: I))
3333 *MinLateStart = std::min(a: *MinLateStart, b: cycle);
3334 }
3335 }
3336 }
3337}
3338
3339/// Order the instructions within a cycle so that the definitions occur
3340/// before the uses. Returns true if the instruction is added to the start
3341/// of the list, or false if added to the end.
3342void SMSchedule::orderDependence(const SwingSchedulerDAG *SSD, SUnit *SU,
3343 std::deque<SUnit *> &Insts) const {
3344 MachineInstr *MI = SU->getInstr();
3345 bool OrderBeforeUse = false;
3346 bool OrderAfterDef = false;
3347 bool OrderBeforeDef = false;
3348 unsigned MoveDef = 0;
3349 unsigned MoveUse = 0;
3350 int StageInst1 = stageScheduled(SU);
3351 const SwingSchedulerDDG *DDG = SSD->getDDG();
3352
3353 unsigned Pos = 0;
3354 for (std::deque<SUnit *>::iterator I = Insts.begin(), E = Insts.end(); I != E;
3355 ++I, ++Pos) {
3356 for (MachineOperand &MO : MI->operands()) {
3357 if (!MO.isReg() || !MO.getReg().isVirtual())
3358 continue;
3359
3360 Register Reg = MO.getReg();
3361 unsigned BasePos, OffsetPos;
3362 if (ST.getInstrInfo()->getBaseAndOffsetPosition(MI: *MI, BasePos, OffsetPos))
3363 if (MI->getOperand(i: BasePos).getReg() == Reg)
3364 if (Register NewReg = SSD->getInstrBaseReg(SU))
3365 Reg = NewReg;
3366 bool Reads, Writes;
3367 std::tie(args&: Reads, args&: Writes) =
3368 (*I)->getInstr()->readsWritesVirtualRegister(Reg);
3369 if (MO.isDef() && Reads && stageScheduled(SU: *I) <= StageInst1) {
3370 OrderBeforeUse = true;
3371 if (MoveUse == 0)
3372 MoveUse = Pos;
3373 } else if (MO.isDef() && Reads && stageScheduled(SU: *I) > StageInst1) {
3374 // Add the instruction after the scheduled instruction.
3375 OrderAfterDef = true;
3376 MoveDef = Pos;
3377 } else if (MO.isUse() && Writes && stageScheduled(SU: *I) == StageInst1) {
3378 if (cycleScheduled(SU: *I) == cycleScheduled(SU) && !(*I)->isSucc(N: SU)) {
3379 OrderBeforeUse = true;
3380 if (MoveUse == 0)
3381 MoveUse = Pos;
3382 } else {
3383 OrderAfterDef = true;
3384 MoveDef = Pos;
3385 }
3386 } else if (MO.isUse() && Writes && stageScheduled(SU: *I) > StageInst1) {
3387 OrderBeforeUse = true;
3388 if (MoveUse == 0)
3389 MoveUse = Pos;
3390 if (MoveUse != 0) {
3391 OrderAfterDef = true;
3392 MoveDef = Pos - 1;
3393 }
3394 } else if (MO.isUse() && Writes && stageScheduled(SU: *I) < StageInst1) {
3395 // Add the instruction before the scheduled instruction.
3396 OrderBeforeUse = true;
3397 if (MoveUse == 0)
3398 MoveUse = Pos;
3399 } else if (MO.isUse() && stageScheduled(SU: *I) == StageInst1 &&
3400 isLoopCarriedDefOfUse(SSD, Def: (*I)->getInstr(), MO)) {
3401 if (MoveUse == 0) {
3402 OrderBeforeDef = true;
3403 MoveUse = Pos;
3404 }
3405 }
3406 }
3407 // Check for order dependences between instructions. Make sure the source
3408 // is ordered before the destination.
3409 for (auto &OE : DDG->getOutEdges(SU)) {
3410 if (OE.getDst() != *I)
3411 continue;
3412 if (OE.isOrderDep() && stageScheduled(SU: *I) == StageInst1) {
3413 OrderBeforeUse = true;
3414 if (Pos < MoveUse)
3415 MoveUse = Pos;
3416 }
3417 // We did not handle HW dependences in previous for loop,
3418 // and we normally set Latency = 0 for Anti/Output deps,
3419 // so may have nodes in same cycle with Anti/Output dependent on HW regs.
3420 else if ((OE.isAntiDep() || OE.isOutputDep()) &&
3421 stageScheduled(SU: *I) == StageInst1) {
3422 OrderBeforeUse = true;
3423 if ((MoveUse == 0) || (Pos < MoveUse))
3424 MoveUse = Pos;
3425 }
3426 }
3427 for (auto &IE : DDG->getInEdges(SU)) {
3428 if (IE.getSrc() != *I)
3429 continue;
3430 if ((IE.isAntiDep() || IE.isOutputDep() || IE.isOrderDep()) &&
3431 stageScheduled(SU: *I) == StageInst1) {
3432 OrderAfterDef = true;
3433 MoveDef = Pos;
3434 }
3435 }
3436 }
3437
3438 // A circular dependence.
3439 if (OrderAfterDef && OrderBeforeUse && MoveUse == MoveDef)
3440 OrderBeforeUse = false;
3441
3442 // OrderAfterDef takes precedences over OrderBeforeDef. The latter is due
3443 // to a loop-carried dependence.
3444 if (OrderBeforeDef)
3445 OrderBeforeUse = !OrderAfterDef || (MoveUse > MoveDef);
3446
3447 // The uncommon case when the instruction order needs to be updated because
3448 // there is both a use and def.
3449 if (OrderBeforeUse && OrderAfterDef) {
3450 SUnit *UseSU = Insts.at(n: MoveUse);
3451 SUnit *DefSU = Insts.at(n: MoveDef);
3452 if (MoveUse > MoveDef) {
3453 Insts.erase(position: Insts.begin() + MoveUse);
3454 Insts.erase(position: Insts.begin() + MoveDef);
3455 } else {
3456 Insts.erase(position: Insts.begin() + MoveDef);
3457 Insts.erase(position: Insts.begin() + MoveUse);
3458 }
3459 orderDependence(SSD, SU: UseSU, Insts);
3460 orderDependence(SSD, SU, Insts);
3461 orderDependence(SSD, SU: DefSU, Insts);
3462 return;
3463 }
3464 // Put the new instruction first if there is a use in the list. Otherwise,
3465 // put it at the end of the list.
3466 if (OrderBeforeUse)
3467 Insts.push_front(x: SU);
3468 else
3469 Insts.push_back(x: SU);
3470}
3471
3472/// Return true if the scheduled Phi has a loop carried operand.
3473bool SMSchedule::isLoopCarried(const SwingSchedulerDAG *SSD,
3474 MachineInstr &Phi) const {
3475 if (!Phi.isPHI())
3476 return false;
3477 assert(Phi.isPHI() && "Expecting a Phi.");
3478 SUnit *DefSU = SSD->getSUnit(MI: &Phi);
3479 unsigned DefCycle = cycleScheduled(SU: DefSU);
3480 int DefStage = stageScheduled(SU: DefSU);
3481
3482 Register InitVal;
3483 Register LoopVal;
3484 getPhiRegs(Phi, Loop: Phi.getParent(), InitVal, LoopVal);
3485 SUnit *UseSU = SSD->getSUnit(MI: MRI.getVRegDef(Reg: LoopVal));
3486 if (!UseSU)
3487 return true;
3488 if (UseSU->getInstr()->isPHI())
3489 return true;
3490 unsigned LoopCycle = cycleScheduled(SU: UseSU);
3491 int LoopStage = stageScheduled(SU: UseSU);
3492 return (LoopCycle > DefCycle) || (LoopStage <= DefStage);
3493}
3494
3495/// Return true if the instruction is a definition that is loop carried
3496/// and defines the use on the next iteration.
3497/// v1 = phi(v2, v3)
3498/// (Def) v3 = op v1
3499/// (MO) = v1
3500/// If MO appears before Def, then v1 and v3 may get assigned to the same
3501/// register.
3502bool SMSchedule::isLoopCarriedDefOfUse(const SwingSchedulerDAG *SSD,
3503 MachineInstr *Def,
3504 MachineOperand &MO) const {
3505 if (!MO.isReg())
3506 return false;
3507 if (Def->isPHI())
3508 return false;
3509 MachineInstr *Phi = MRI.getVRegDef(Reg: MO.getReg());
3510 if (!Phi || !Phi->isPHI() || Phi->getParent() != Def->getParent())
3511 return false;
3512 if (!isLoopCarried(SSD, Phi&: *Phi))
3513 return false;
3514 Register LoopReg = getLoopPhiReg(Phi: *Phi, LoopBB: Phi->getParent());
3515 for (MachineOperand &DMO : Def->all_defs()) {
3516 if (DMO.getReg() == LoopReg)
3517 return true;
3518 }
3519 return false;
3520}
3521
3522/// Return true if all scheduled predecessors are loop-carried output/order
3523/// dependencies.
3524bool SMSchedule::onlyHasLoopCarriedOutputOrOrderPreds(
3525 SUnit *SU, const SwingSchedulerDDG *DDG) const {
3526 for (const auto &IE : DDG->getInEdges(SU))
3527 if (InstrToCycle.count(x: IE.getSrc()))
3528 return false;
3529 return true;
3530}
3531
3532/// Determine transitive dependences of unpipelineable instructions
3533SmallPtrSet<SUnit *, 8> SMSchedule::computeUnpipelineableNodes(
3534 SwingSchedulerDAG *SSD, TargetInstrInfo::PipelinerLoopInfo *PLI) {
3535 SmallPtrSet<SUnit *, 8> DoNotPipeline;
3536 SmallVector<SUnit *, 8> Worklist;
3537
3538 for (auto &SU : SSD->SUnits)
3539 if (SU.isInstr() && PLI->shouldIgnoreForPipelining(MI: SU.getInstr()))
3540 Worklist.push_back(Elt: &SU);
3541
3542 const SwingSchedulerDDG *DDG = SSD->getDDG();
3543 while (!Worklist.empty()) {
3544 auto SU = Worklist.pop_back_val();
3545 if (DoNotPipeline.count(Ptr: SU))
3546 continue;
3547 LLVM_DEBUG(dbgs() << "Do not pipeline SU(" << SU->NodeNum << ")\n");
3548 DoNotPipeline.insert(Ptr: SU);
3549 for (const auto &IE : DDG->getInEdges(SU))
3550 Worklist.push_back(Elt: IE.getSrc());
3551
3552 // To preserve previous behavior and prevent regression
3553 // FIXME: Remove if this doesn't have significant impact on
3554 for (const auto &OE : DDG->getOutEdges(SU))
3555 if (OE.getDistance() == 1)
3556 Worklist.push_back(Elt: OE.getDst());
3557 }
3558 return DoNotPipeline;
3559}
3560
3561// Determine all instructions upon which any unpipelineable instruction depends
3562// and ensure that they are in stage 0. If unable to do so, return false.
3563bool SMSchedule::normalizeNonPipelinedInstructions(
3564 SwingSchedulerDAG *SSD, TargetInstrInfo::PipelinerLoopInfo *PLI) {
3565 SmallPtrSet<SUnit *, 8> DNP = computeUnpipelineableNodes(SSD, PLI);
3566
3567 int NewLastCycle = INT_MIN;
3568 for (SUnit &SU : SSD->SUnits) {
3569 if (!SU.isInstr())
3570 continue;
3571 if (!DNP.contains(Ptr: &SU) || stageScheduled(SU: &SU) == 0) {
3572 NewLastCycle = std::max(a: NewLastCycle, b: InstrToCycle[&SU]);
3573 continue;
3574 }
3575
3576 // Put the non-pipelined instruction as early as possible in the schedule
3577 int NewCycle = getFirstCycle();
3578 for (const auto &IE : SSD->getDDG()->getInEdges(SU: &SU))
3579 if (IE.getDistance() == 0)
3580 NewCycle = std::max(a: InstrToCycle[IE.getSrc()], b: NewCycle);
3581
3582 // To preserve previous behavior and prevent regression
3583 // FIXME: Remove if this doesn't have significant impact on performance
3584 for (auto &OE : SSD->getDDG()->getOutEdges(SU: &SU))
3585 if (OE.getDistance() == 1)
3586 NewCycle = std::max(a: InstrToCycle[OE.getDst()], b: NewCycle);
3587
3588 int OldCycle = InstrToCycle[&SU];
3589 if (OldCycle != NewCycle) {
3590 InstrToCycle[&SU] = NewCycle;
3591 auto &OldS = getInstructions(cycle: OldCycle);
3592 llvm::erase(C&: OldS, V: &SU);
3593 getInstructions(cycle: NewCycle).emplace_back(args: &SU);
3594 LLVM_DEBUG(dbgs() << "SU(" << SU.NodeNum
3595 << ") is not pipelined; moving from cycle " << OldCycle
3596 << " to " << NewCycle << " Instr:" << *SU.getInstr());
3597 }
3598
3599 // We traverse the SUs in the order of the original basic block. Computing
3600 // NewCycle in this order normally works fine because all dependencies
3601 // (except for loop-carried dependencies) don't violate the original order.
3602 // However, an artificial dependency (e.g., added by CopyToPhiMutation) can
3603 // break it. That is, there may be exist an artificial dependency from
3604 // bottom to top. In such a case, NewCycle may become too large to be
3605 // scheduled in Stage 0. For example, assume that Inst0 is in DNP in the
3606 // following case:
3607 //
3608 // | Inst0 <-+
3609 // SU order | | artificial dep
3610 // | Inst1 --+
3611 // v
3612 //
3613 // If Inst1 is scheduled at cycle N and is not at Stage 0, then NewCycle of
3614 // Inst0 must be greater than or equal to N so that Inst0 is not be
3615 // scheduled at Stage 0. In such cases, we reject this schedule at this
3616 // time.
3617 // FIXME: The reason for this is the existence of artificial dependencies
3618 // that are contradict to the original SU order. If ignoring artificial
3619 // dependencies does not affect correctness, then it is better to ignore
3620 // them.
3621 if (FirstCycle + InitiationInterval <= NewCycle)
3622 return false;
3623
3624 NewLastCycle = std::max(a: NewLastCycle, b: NewCycle);
3625 }
3626 LastCycle = NewLastCycle;
3627 return true;
3628}
3629
3630// Check if the generated schedule is valid. This function checks if
3631// an instruction that uses a physical register is scheduled in a
3632// different stage than the definition. The pipeliner does not handle
3633// physical register values that may cross a basic block boundary.
3634// Furthermore, if a physical def/use pair is assigned to the same
3635// cycle, orderDependence does not guarantee def/use ordering, so that
3636// case should be considered invalid. (The test checks for both
3637// earlier and same-cycle use to be more robust.)
3638bool SMSchedule::isValidSchedule(SwingSchedulerDAG *SSD) {
3639 for (SUnit &SU : SSD->SUnits) {
3640 if (!SU.hasPhysRegDefs)
3641 continue;
3642 int StageDef = stageScheduled(SU: &SU);
3643 int CycleDef = InstrToCycle[&SU];
3644 assert(StageDef != -1 && "Instruction should have been scheduled.");
3645 for (auto &OE : SSD->getDDG()->getOutEdges(SU: &SU)) {
3646 SUnit *Dst = OE.getDst();
3647 if (OE.isAssignedRegDep() && !Dst->isBoundaryNode())
3648 if (OE.getReg().isPhysical()) {
3649 if (stageScheduled(SU: Dst) != StageDef)
3650 return false;
3651 if (InstrToCycle[Dst] <= CycleDef)
3652 return false;
3653 }
3654 }
3655 }
3656 return true;
3657}
3658
3659/// A property of the node order in swing-modulo-scheduling is
3660/// that for nodes outside circuits the following holds:
3661/// none of them is scheduled after both a successor and a
3662/// predecessor.
3663/// The method below checks whether the property is met.
3664/// If not, debug information is printed and statistics information updated.
3665/// Note that we do not use an assert statement.
3666/// The reason is that although an invalid node order may prevent
3667/// the pipeliner from finding a pipelined schedule for arbitrary II,
3668/// it does not lead to the generation of incorrect code.
3669void SwingSchedulerDAG::checkValidNodeOrder(const NodeSetType &Circuits) const {
3670
3671 // a sorted vector that maps each SUnit to its index in the NodeOrder
3672 typedef std::pair<SUnit *, unsigned> UnitIndex;
3673 std::vector<UnitIndex> Indices(NodeOrder.size(), std::make_pair(x: nullptr, y: 0));
3674
3675 for (unsigned i = 0, s = NodeOrder.size(); i < s; ++i)
3676 Indices.push_back(x: std::make_pair(x: NodeOrder[i], y&: i));
3677
3678 auto CompareKey = [](UnitIndex i1, UnitIndex i2) {
3679 return std::get<0>(in&: i1) < std::get<0>(in&: i2);
3680 };
3681
3682 // sort, so that we can perform a binary search
3683 llvm::sort(C&: Indices, Comp: CompareKey);
3684
3685 bool Valid = true;
3686 (void)Valid;
3687 // for each SUnit in the NodeOrder, check whether
3688 // it appears after both a successor and a predecessor
3689 // of the SUnit. If this is the case, and the SUnit
3690 // is not part of circuit, then the NodeOrder is not
3691 // valid.
3692 for (unsigned i = 0, s = NodeOrder.size(); i < s; ++i) {
3693 SUnit *SU = NodeOrder[i];
3694 unsigned Index = i;
3695
3696 bool PredBefore = false;
3697 bool SuccBefore = false;
3698
3699 SUnit *Succ;
3700 SUnit *Pred;
3701 (void)Succ;
3702 (void)Pred;
3703
3704 for (const auto &IE : DDG->getInEdges(SU)) {
3705 SUnit *PredSU = IE.getSrc();
3706 unsigned PredIndex = std::get<1>(
3707 in&: *llvm::lower_bound(Range&: Indices, Value: std::make_pair(x&: PredSU, y: 0), C: CompareKey));
3708 if (!PredSU->getInstr()->isPHI() && PredIndex < Index) {
3709 PredBefore = true;
3710 Pred = PredSU;
3711 break;
3712 }
3713 }
3714
3715 for (const auto &OE : DDG->getOutEdges(SU)) {
3716 SUnit *SuccSU = OE.getDst();
3717 // Do not process a boundary node, it was not included in NodeOrder,
3718 // hence not in Indices either, call to std::lower_bound() below will
3719 // return Indices.end().
3720 if (SuccSU->isBoundaryNode())
3721 continue;
3722 unsigned SuccIndex = std::get<1>(
3723 in&: *llvm::lower_bound(Range&: Indices, Value: std::make_pair(x&: SuccSU, y: 0), C: CompareKey));
3724 if (!SuccSU->getInstr()->isPHI() && SuccIndex < Index) {
3725 SuccBefore = true;
3726 Succ = SuccSU;
3727 break;
3728 }
3729 }
3730
3731 if (PredBefore && SuccBefore && !SU->getInstr()->isPHI()) {
3732 // instructions in circuits are allowed to be scheduled
3733 // after both a successor and predecessor.
3734 bool InCircuit = llvm::any_of(
3735 Range: Circuits, P: [SU](const NodeSet &Circuit) { return Circuit.count(SU); });
3736 if (InCircuit)
3737 LLVM_DEBUG(dbgs() << "In a circuit, predecessor ");
3738 else {
3739 Valid = false;
3740 NumNodeOrderIssues++;
3741 LLVM_DEBUG(dbgs() << "Predecessor ");
3742 }
3743 LLVM_DEBUG(dbgs() << Pred->NodeNum << " and successor " << Succ->NodeNum
3744 << " are scheduled before node " << SU->NodeNum
3745 << "\n");
3746 }
3747 }
3748
3749 LLVM_DEBUG({
3750 if (!Valid)
3751 dbgs() << "Invalid node order found!\n";
3752 });
3753}
3754
3755/// Attempt to fix the degenerate cases when the instruction serialization
3756/// causes the register lifetimes to overlap. For example,
3757/// p' = store_pi(p, b)
3758/// = load p, offset
3759/// In this case p and p' overlap, which means that two registers are needed.
3760/// Instead, this function changes the load to use p' and updates the offset.
3761void SwingSchedulerDAG::fixupRegisterOverlaps(std::deque<SUnit *> &Instrs) {
3762 Register OverlapReg;
3763 Register NewBaseReg;
3764 for (SUnit *SU : Instrs) {
3765 MachineInstr *MI = SU->getInstr();
3766 for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) {
3767 const MachineOperand &MO = MI->getOperand(i);
3768 // Look for an instruction that uses p. The instruction occurs in the
3769 // same cycle but occurs later in the serialized order.
3770 if (MO.isReg() && MO.isUse() && MO.getReg() == OverlapReg) {
3771 // Check that the instruction appears in the InstrChanges structure,
3772 // which contains instructions that can have the offset updated.
3773 DenseMap<SUnit *, std::pair<Register, int64_t>>::iterator It =
3774 InstrChanges.find(Val: SU);
3775 if (It != InstrChanges.end()) {
3776 unsigned BasePos, OffsetPos;
3777 // Update the base register and adjust the offset.
3778 if (TII->getBaseAndOffsetPosition(MI: *MI, BasePos, OffsetPos)) {
3779 MachineInstr *NewMI = MF.CloneMachineInstr(Orig: MI);
3780 NewMI->getOperand(i: BasePos).setReg(NewBaseReg);
3781 int64_t NewOffset =
3782 MI->getOperand(i: OffsetPos).getImm() - It->second.second;
3783 NewMI->getOperand(i: OffsetPos).setImm(NewOffset);
3784 SU->setInstr(NewMI);
3785 MISUnitMap[NewMI] = SU;
3786 NewMIs[MI] = NewMI;
3787 }
3788 }
3789 OverlapReg = Register();
3790 NewBaseReg = Register();
3791 break;
3792 }
3793 // Look for an instruction of the form p' = op(p), which uses and defines
3794 // two virtual registers that get allocated to the same physical register.
3795 unsigned TiedUseIdx = 0;
3796 if (MI->isRegTiedToUseOperand(DefOpIdx: i, UseOpIdx: &TiedUseIdx)) {
3797 // OverlapReg is p in the example above.
3798 OverlapReg = MI->getOperand(i: TiedUseIdx).getReg();
3799 // NewBaseReg is p' in the example above.
3800 NewBaseReg = MI->getOperand(i).getReg();
3801 break;
3802 }
3803 }
3804 }
3805}
3806
3807std::deque<SUnit *>
3808SMSchedule::reorderInstructions(const SwingSchedulerDAG *SSD,
3809 const std::deque<SUnit *> &Instrs) const {
3810 std::deque<SUnit *> NewOrderPhi;
3811 for (SUnit *SU : Instrs) {
3812 if (SU->getInstr()->isPHI())
3813 NewOrderPhi.push_back(x: SU);
3814 }
3815 std::deque<SUnit *> NewOrderI;
3816 for (SUnit *SU : Instrs) {
3817 if (!SU->getInstr()->isPHI())
3818 orderDependence(SSD, SU, Insts&: NewOrderI);
3819 }
3820 llvm::append_range(C&: NewOrderPhi, R&: NewOrderI);
3821 return NewOrderPhi;
3822}
3823
3824/// After the schedule has been formed, call this function to combine
3825/// the instructions from the different stages/cycles. That is, this
3826/// function creates a schedule that represents a single iteration.
3827void SMSchedule::finalizeSchedule(SwingSchedulerDAG *SSD) {
3828 // Move all instructions to the first stage from later stages.
3829 for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) {
3830 for (int stage = 1, lastStage = getMaxStageCount(); stage <= lastStage;
3831 ++stage) {
3832 std::deque<SUnit *> &cycleInstrs =
3833 ScheduledInstrs[cycle + (stage * InitiationInterval)];
3834 for (SUnit *SU : llvm::reverse(C&: cycleInstrs))
3835 ScheduledInstrs[cycle].push_front(x: SU);
3836 }
3837 }
3838
3839 // Erase all the elements in the later stages. Only one iteration should
3840 // remain in the scheduled list, and it contains all the instructions.
3841 for (int cycle = getFinalCycle() + 1; cycle <= LastCycle; ++cycle)
3842 ScheduledInstrs.erase(Val: cycle);
3843
3844 // Change the registers in instruction as specified in the InstrChanges
3845 // map. We need to use the new registers to create the correct order.
3846 for (const SUnit &SU : SSD->SUnits)
3847 SSD->applyInstrChange(MI: SU.getInstr(), Schedule&: *this);
3848
3849 // Reorder the instructions in each cycle to fix and improve the
3850 // generated code.
3851 for (int Cycle = getFirstCycle(), E = getFinalCycle(); Cycle <= E; ++Cycle) {
3852 std::deque<SUnit *> &cycleInstrs = ScheduledInstrs[Cycle];
3853 cycleInstrs = reorderInstructions(SSD, Instrs: cycleInstrs);
3854 SSD->fixupRegisterOverlaps(Instrs&: cycleInstrs);
3855 }
3856
3857 LLVM_DEBUG(dump(););
3858}
3859
3860void NodeSet::print(raw_ostream &os) const {
3861 os << "Num nodes " << size() << " rec " << RecMII << " mov " << MaxMOV
3862 << " depth " << MaxDepth << " col " << Colocate << "\n";
3863 for (const auto &I : Nodes)
3864 os << " SU(" << I->NodeNum << ") " << *(I->getInstr());
3865 os << "\n";
3866}
3867
3868#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3869/// Print the schedule information to the given output.
3870void SMSchedule::print(raw_ostream &os) const {
3871 // Iterate over each cycle.
3872 for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) {
3873 // Iterate over each instruction in the cycle.
3874 const_sched_iterator cycleInstrs = ScheduledInstrs.find(cycle);
3875 for (SUnit *CI : cycleInstrs->second) {
3876 os << "cycle " << cycle << " (" << stageScheduled(CI) << ") ";
3877 os << "(" << CI->NodeNum << ") ";
3878 CI->getInstr()->print(os);
3879 os << "\n";
3880 }
3881 }
3882}
3883
3884/// Utility function used for debugging to print the schedule.
3885LLVM_DUMP_METHOD void SMSchedule::dump() const { print(dbgs()); }
3886LLVM_DUMP_METHOD void NodeSet::dump() const { print(dbgs()); }
3887
3888void ResourceManager::dumpMRT() const {
3889 LLVM_DEBUG({
3890 if (UseDFA)
3891 return;
3892 std::stringstream SS;
3893 SS << "MRT:\n";
3894 SS << std::setw(4) << "Slot";
3895 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I)
3896 SS << std::setw(3) << I;
3897 SS << std::setw(7) << "#Mops"
3898 << "\n";
3899 for (int Slot = 0; Slot < InitiationInterval; ++Slot) {
3900 SS << std::setw(4) << Slot;
3901 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I)
3902 SS << std::setw(3) << MRT[Slot][I];
3903 SS << std::setw(7) << NumScheduledMops[Slot] << "\n";
3904 }
3905 dbgs() << SS.str();
3906 });
3907}
3908#endif
3909
3910void ResourceManager::initProcResourceVectors(
3911 const MCSchedModel &SM, SmallVectorImpl<uint64_t> &Masks) {
3912 unsigned ProcResourceID = 0;
3913
3914 // We currently limit the resource kinds to 64 and below so that we can use
3915 // uint64_t for Masks
3916 assert(SM.getNumProcResourceKinds() < 64 &&
3917 "Too many kinds of resources, unsupported");
3918 // Create a unique bitmask for every processor resource unit.
3919 // Skip resource at index 0, since it always references 'InvalidUnit'.
3920 Masks.resize(N: SM.getNumProcResourceKinds());
3921 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
3922 const MCProcResourceDesc &Desc = *SM.getProcResource(ProcResourceIdx: I);
3923 if (Desc.SubUnitsIdxBegin)
3924 continue;
3925 Masks[I] = 1ULL << ProcResourceID;
3926 ProcResourceID++;
3927 }
3928 // Create a unique bitmask for every processor resource group.
3929 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
3930 const MCProcResourceDesc &Desc = *SM.getProcResource(ProcResourceIdx: I);
3931 if (!Desc.SubUnitsIdxBegin)
3932 continue;
3933 Masks[I] = 1ULL << ProcResourceID;
3934 for (unsigned U = 0; U < Desc.NumUnits; ++U)
3935 Masks[I] |= Masks[Desc.SubUnitsIdxBegin[U]];
3936 ProcResourceID++;
3937 }
3938 LLVM_DEBUG({
3939 if (SwpShowResMask) {
3940 dbgs() << "ProcResourceDesc:\n";
3941 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
3942 const MCProcResourceDesc *ProcResource = SM.getProcResource(I);
3943 dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n",
3944 ProcResource->Name, I, Masks[I],
3945 ProcResource->NumUnits);
3946 }
3947 dbgs() << " -----------------\n";
3948 }
3949 });
3950}
3951
3952bool ResourceManager::canReserveResources(SUnit &SU, int Cycle) {
3953 LLVM_DEBUG({
3954 if (SwpDebugResource)
3955 dbgs() << "canReserveResources:\n";
3956 });
3957 if (UseDFA)
3958 return DFAResources[positiveModulo(Dividend: Cycle, Divisor: InitiationInterval)]
3959 ->canReserveResources(MID: &SU.getInstr()->getDesc());
3960
3961 const MCSchedClassDesc *SCDesc = DAG->getSchedClass(SU: &SU);
3962 if (!SCDesc->isValid()) {
3963 LLVM_DEBUG({
3964 dbgs() << "No valid Schedule Class Desc for schedClass!\n";
3965 dbgs() << "isPseudo:" << SU.getInstr()->isPseudo() << "\n";
3966 });
3967 return true;
3968 }
3969
3970 reserveResources(SCDesc, Cycle);
3971 bool Result = !isOverbooked();
3972 unreserveResources(SCDesc, Cycle);
3973
3974 LLVM_DEBUG(if (SwpDebugResource) dbgs() << "return " << Result << "\n\n");
3975 return Result;
3976}
3977
3978void ResourceManager::reserveResources(SUnit &SU, int Cycle) {
3979 LLVM_DEBUG({
3980 if (SwpDebugResource)
3981 dbgs() << "reserveResources:\n";
3982 });
3983 if (UseDFA)
3984 return DFAResources[positiveModulo(Dividend: Cycle, Divisor: InitiationInterval)]
3985 ->reserveResources(MID: &SU.getInstr()->getDesc());
3986
3987 const MCSchedClassDesc *SCDesc = DAG->getSchedClass(SU: &SU);
3988 if (!SCDesc->isValid()) {
3989 LLVM_DEBUG({
3990 dbgs() << "No valid Schedule Class Desc for schedClass!\n";
3991 dbgs() << "isPseudo:" << SU.getInstr()->isPseudo() << "\n";
3992 });
3993 return;
3994 }
3995
3996 reserveResources(SCDesc, Cycle);
3997
3998 LLVM_DEBUG({
3999 if (SwpDebugResource) {
4000 dumpMRT();
4001 dbgs() << "reserveResources: done!\n\n";
4002 }
4003 });
4004}
4005
4006void ResourceManager::reserveResources(const MCSchedClassDesc *SCDesc,
4007 int Cycle) {
4008 assert(!UseDFA);
4009 for (const MCWriteProcResEntry &PRE : make_range(
4010 x: STI->getWriteProcResBegin(SC: SCDesc), y: STI->getWriteProcResEnd(SC: SCDesc)))
4011 for (int C = Cycle; C < Cycle + PRE.ReleaseAtCycle; ++C)
4012 ++MRT[positiveModulo(Dividend: C, Divisor: InitiationInterval)][PRE.ProcResourceIdx];
4013
4014 for (int C = Cycle; C < Cycle + SCDesc->NumMicroOps; ++C)
4015 ++NumScheduledMops[positiveModulo(Dividend: C, Divisor: InitiationInterval)];
4016}
4017
4018void ResourceManager::unreserveResources(const MCSchedClassDesc *SCDesc,
4019 int Cycle) {
4020 assert(!UseDFA);
4021 for (const MCWriteProcResEntry &PRE : make_range(
4022 x: STI->getWriteProcResBegin(SC: SCDesc), y: STI->getWriteProcResEnd(SC: SCDesc)))
4023 for (int C = Cycle; C < Cycle + PRE.ReleaseAtCycle; ++C)
4024 --MRT[positiveModulo(Dividend: C, Divisor: InitiationInterval)][PRE.ProcResourceIdx];
4025
4026 for (int C = Cycle; C < Cycle + SCDesc->NumMicroOps; ++C)
4027 --NumScheduledMops[positiveModulo(Dividend: C, Divisor: InitiationInterval)];
4028}
4029
4030bool ResourceManager::isOverbooked() const {
4031 assert(!UseDFA);
4032 for (int Slot = 0; Slot < InitiationInterval; ++Slot) {
4033 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
4034 const MCProcResourceDesc *Desc = SM.getProcResource(ProcResourceIdx: I);
4035 if (MRT[Slot][I] > Desc->NumUnits)
4036 return true;
4037 }
4038 if (NumScheduledMops[Slot] > IssueWidth)
4039 return true;
4040 }
4041 return false;
4042}
4043
4044int ResourceManager::calculateResMIIDFA() const {
4045 assert(UseDFA);
4046
4047 // Sort the instructions by the number of available choices for scheduling,
4048 // least to most. Use the number of critical resources as the tie breaker.
4049 FuncUnitSorter FUS = FuncUnitSorter(*ST);
4050 for (SUnit &SU : DAG->SUnits)
4051 FUS.calcCriticalResources(MI&: *SU.getInstr());
4052 PriorityQueue<MachineInstr *, std::vector<MachineInstr *>, FuncUnitSorter>
4053 FuncUnitOrder(FUS);
4054
4055 for (SUnit &SU : DAG->SUnits)
4056 FuncUnitOrder.push(x: SU.getInstr());
4057
4058 SmallVector<std::unique_ptr<DFAPacketizer>, 8> Resources;
4059 Resources.push_back(
4060 Elt: std::unique_ptr<DFAPacketizer>(TII->CreateTargetScheduleState(*ST)));
4061
4062 while (!FuncUnitOrder.empty()) {
4063 MachineInstr *MI = FuncUnitOrder.top();
4064 FuncUnitOrder.pop();
4065 if (TII->isZeroCost(Opcode: MI->getOpcode()))
4066 continue;
4067
4068 // Attempt to reserve the instruction in an existing DFA. At least one
4069 // DFA is needed for each cycle.
4070 unsigned NumCycles = DAG->getSUnit(MI)->Latency;
4071 unsigned ReservedCycles = 0;
4072 auto *RI = Resources.begin();
4073 auto *RE = Resources.end();
4074 LLVM_DEBUG({
4075 dbgs() << "Trying to reserve resource for " << NumCycles
4076 << " cycles for \n";
4077 MI->dump();
4078 });
4079 for (unsigned C = 0; C < NumCycles; ++C)
4080 while (RI != RE) {
4081 if ((*RI)->canReserveResources(MI&: *MI)) {
4082 (*RI)->reserveResources(MI&: *MI);
4083 ++ReservedCycles;
4084 break;
4085 }
4086 RI++;
4087 }
4088 LLVM_DEBUG(dbgs() << "ReservedCycles:" << ReservedCycles
4089 << ", NumCycles:" << NumCycles << "\n");
4090 // Add new DFAs, if needed, to reserve resources.
4091 for (unsigned C = ReservedCycles; C < NumCycles; ++C) {
4092 LLVM_DEBUG(if (SwpDebugResource) dbgs()
4093 << "NewResource created to reserve resources"
4094 << "\n");
4095 auto *NewResource = TII->CreateTargetScheduleState(*ST);
4096 assert(NewResource->canReserveResources(*MI) && "Reserve error.");
4097 NewResource->reserveResources(MI&: *MI);
4098 Resources.push_back(Elt: std::unique_ptr<DFAPacketizer>(NewResource));
4099 }
4100 }
4101
4102 int Resmii = Resources.size();
4103 LLVM_DEBUG(dbgs() << "Return Res MII:" << Resmii << "\n");
4104 return Resmii;
4105}
4106
4107int ResourceManager::calculateResMII() const {
4108 if (UseDFA)
4109 return calculateResMIIDFA();
4110
4111 // Count each resource consumption and divide it by the number of units.
4112 // ResMII is the max value among them.
4113
4114 int NumMops = 0;
4115 SmallVector<uint64_t> ResourceCount(SM.getNumProcResourceKinds());
4116 for (SUnit &SU : DAG->SUnits) {
4117 if (TII->isZeroCost(Opcode: SU.getInstr()->getOpcode()))
4118 continue;
4119
4120 const MCSchedClassDesc *SCDesc = DAG->getSchedClass(SU: &SU);
4121 if (!SCDesc->isValid())
4122 continue;
4123
4124 LLVM_DEBUG({
4125 if (SwpDebugResource) {
4126 DAG->dumpNode(SU);
4127 dbgs() << " #Mops: " << SCDesc->NumMicroOps << "\n"
4128 << " WriteProcRes: ";
4129 }
4130 });
4131 NumMops += SCDesc->NumMicroOps;
4132 for (const MCWriteProcResEntry &PRE :
4133 make_range(x: STI->getWriteProcResBegin(SC: SCDesc),
4134 y: STI->getWriteProcResEnd(SC: SCDesc))) {
4135 LLVM_DEBUG({
4136 if (SwpDebugResource) {
4137 const MCProcResourceDesc *Desc =
4138 SM.getProcResource(PRE.ProcResourceIdx);
4139 dbgs() << Desc->Name << ": " << PRE.ReleaseAtCycle << ", ";
4140 }
4141 });
4142 ResourceCount[PRE.ProcResourceIdx] += PRE.ReleaseAtCycle;
4143 }
4144 LLVM_DEBUG(if (SwpDebugResource) dbgs() << "\n");
4145 }
4146
4147 int Result = (NumMops + IssueWidth - 1) / IssueWidth;
4148 LLVM_DEBUG({
4149 if (SwpDebugResource)
4150 dbgs() << "#Mops: " << NumMops << ", "
4151 << "IssueWidth: " << IssueWidth << ", "
4152 << "Cycles: " << Result << "\n";
4153 });
4154
4155 LLVM_DEBUG({
4156 if (SwpDebugResource) {
4157 std::stringstream SS;
4158 SS << std::setw(2) << "ID" << std::setw(16) << "Name" << std::setw(10)
4159 << "Units" << std::setw(10) << "Consumed" << std::setw(10) << "Cycles"
4160 << "\n";
4161 dbgs() << SS.str();
4162 }
4163 });
4164 for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
4165 const MCProcResourceDesc *Desc = SM.getProcResource(ProcResourceIdx: I);
4166 int Cycles = (ResourceCount[I] + Desc->NumUnits - 1) / Desc->NumUnits;
4167 LLVM_DEBUG({
4168 if (SwpDebugResource) {
4169 std::stringstream SS;
4170 SS << std::setw(2) << I << std::setw(16) << Desc->Name << std::setw(10)
4171 << Desc->NumUnits << std::setw(10) << ResourceCount[I]
4172 << std::setw(10) << Cycles << "\n";
4173 dbgs() << SS.str();
4174 }
4175 });
4176 if (Cycles > Result)
4177 Result = Cycles;
4178 }
4179 return Result;
4180}
4181
4182void ResourceManager::init(int II) {
4183 InitiationInterval = II;
4184 DFAResources.clear();
4185 DFAResources.resize(N: II);
4186 for (auto &I : DFAResources)
4187 I.reset(p: ST->getInstrInfo()->CreateTargetScheduleState(*ST));
4188 MRT.clear();
4189 MRT.resize(N: II, NV: SmallVector<uint64_t>(SM.getNumProcResourceKinds()));
4190 NumScheduledMops.clear();
4191 NumScheduledMops.resize(N: II);
4192}
4193
4194bool SwingSchedulerDDGEdge::ignoreDependence(bool IgnoreAnti) const {
4195 if (Pred.isArtificial() || Dst->isBoundaryNode())
4196 return true;
4197 // Currently, dependence that is an anti-dependences but not a loop-carried is
4198 // also ignored. This behavior is preserved to prevent regression.
4199 // FIXME: Remove if this doesn't have significant impact on performance
4200 return IgnoreAnti && (Pred.getKind() == SDep::Kind::Anti || Distance != 0);
4201}
4202
4203SwingSchedulerDDG::SwingSchedulerDDGEdges &
4204SwingSchedulerDDG::getEdges(const SUnit *SU) {
4205 if (SU == EntrySU)
4206 return EntrySUEdges;
4207 if (SU == ExitSU)
4208 return ExitSUEdges;
4209 return EdgesVec[SU->NodeNum];
4210}
4211
4212const SwingSchedulerDDG::SwingSchedulerDDGEdges &
4213SwingSchedulerDDG::getEdges(const SUnit *SU) const {
4214 if (SU == EntrySU)
4215 return EntrySUEdges;
4216 if (SU == ExitSU)
4217 return ExitSUEdges;
4218 return EdgesVec[SU->NodeNum];
4219}
4220
4221void SwingSchedulerDDG::addEdge(const SUnit *SU,
4222 const SwingSchedulerDDGEdge &Edge) {
4223 assert(!Edge.isValidationOnly() &&
4224 "Validation-only edges are not expected here.");
4225
4226 auto &Edges = getEdges(SU);
4227 if (Edge.getSrc() == SU)
4228 Edges.Succs.push_back(Elt: Edge);
4229 else
4230 Edges.Preds.push_back(Elt: Edge);
4231}
4232
4233void SwingSchedulerDDG::initEdges(SUnit *SU) {
4234 for (const auto &PI : SU->Preds) {
4235 SwingSchedulerDDGEdge Edge(SU, PI, /*IsSucc=*/false,
4236 /*IsValidationOnly=*/false);
4237 addEdge(SU, Edge);
4238 }
4239
4240 for (const auto &SI : SU->Succs) {
4241 SwingSchedulerDDGEdge Edge(SU, SI, /*IsSucc=*/true,
4242 /*IsValidationOnly=*/false);
4243 addEdge(SU, Edge);
4244 }
4245}
4246
4247SwingSchedulerDDG::SwingSchedulerDDG(std::vector<SUnit> &SUnits, SUnit *EntrySU,
4248 SUnit *ExitSU, const LoopCarriedEdges &LCE)
4249 : EntrySU(EntrySU), ExitSU(ExitSU) {
4250 EdgesVec.resize(new_size: SUnits.size());
4251
4252 // Add non-loop-carried edges based on the DAG.
4253 initEdges(SU: EntrySU);
4254 initEdges(SU: ExitSU);
4255 for (auto &SU : SUnits)
4256 initEdges(SU: &SU);
4257
4258 // Add loop-carried edges, which are not represented in the DAG.
4259 for (SUnit &SU : SUnits) {
4260 SUnit *Src = &SU;
4261 if (const LoopCarriedEdges::OrderDep *OD = LCE.getOrderDepOrNull(Key: Src)) {
4262 SDep Base(Src, SDep::Barrier);
4263 Base.setLatency(1);
4264 for (SUnit *Dst : *OD) {
4265 SwingSchedulerDDGEdge Edge(Dst, Base, /*IsSucc=*/false,
4266 /*IsValidationOnly=*/true);
4267 Edge.setDistance(1);
4268 ValidationOnlyEdges.push_back(Elt: Edge);
4269
4270 // Store the edge as an extra edge if it meets the following conditions:
4271 //
4272 // - The edge is a loop-carried order dependency.
4273 // - The edge is a back edge in terms of the original instruction
4274 // order.
4275 // - The destination instruction may load.
4276 // - The source instruction may store but does not load.
4277 //
4278 // These conditions are inherited from a previous implementation to
4279 // preserve the existing behavior and avoid regressions.
4280 bool UseAsExtraEdge = [&]() {
4281 if (Edge.getDistance() == 0 || !Edge.isOrderDep())
4282 return false;
4283
4284 SUnit *Src = Edge.getSrc();
4285 SUnit *Dst = Edge.getDst();
4286 if (Src->NodeNum < Dst->NodeNum)
4287 return false;
4288
4289 MachineInstr *SrcMI = Src->getInstr();
4290 MachineInstr *DstMI = Dst->getInstr();
4291 return DstMI->mayLoad() && !SrcMI->mayLoad() && SrcMI->mayStore();
4292 }();
4293 if (UseAsExtraEdge)
4294 getEdges(SU: Edge.getSrc()).ExtraSuccs.push_back(Elt: Edge.getDst());
4295 }
4296 }
4297 }
4298}
4299
4300const SwingSchedulerDDG::EdgesType &
4301SwingSchedulerDDG::getInEdges(const SUnit *SU) const {
4302 return getEdges(SU).Preds;
4303}
4304
4305const SwingSchedulerDDG::EdgesType &
4306SwingSchedulerDDG::getOutEdges(const SUnit *SU) const {
4307 return getEdges(SU).Succs;
4308}
4309
4310ArrayRef<SUnit *> SwingSchedulerDDG::getExtraOutEdges(const SUnit *SU) const {
4311 return getEdges(SU).ExtraSuccs;
4312}
4313
4314/// Check if \p Schedule doesn't violate the validation-only dependencies.
4315bool SwingSchedulerDDG::isValidSchedule(const SMSchedule &Schedule) const {
4316 unsigned II = Schedule.getInitiationInterval();
4317
4318 auto ExpandCycle = [&](SUnit *SU) {
4319 int Stage = Schedule.stageScheduled(SU);
4320 int Cycle = Schedule.cycleScheduled(SU);
4321 return Cycle + (Stage * II);
4322 };
4323
4324 for (const SwingSchedulerDDGEdge &Edge : ValidationOnlyEdges) {
4325 SUnit *Src = Edge.getSrc();
4326 SUnit *Dst = Edge.getDst();
4327 if (!Src->isInstr() || !Dst->isInstr())
4328 continue;
4329 int CycleSrc = ExpandCycle(Src);
4330 int CycleDst = ExpandCycle(Dst);
4331 int MaxLateStart = CycleDst + Edge.getDistance() * II - Edge.getLatency();
4332 if (CycleSrc > MaxLateStart) {
4333 LLVM_DEBUG({
4334 dbgs() << "Validation failed for edge from " << Src->NodeNum << " to "
4335 << Dst->NodeNum << "\n";
4336 });
4337 return false;
4338 }
4339 }
4340 return true;
4341}
4342
4343void LoopCarriedEdges::modifySUnits(std::vector<SUnit> &SUnits,
4344 const TargetInstrInfo *TII) {
4345 for (SUnit &SU : SUnits) {
4346 SUnit *Src = &SU;
4347 if (auto *OrderDep = getOrderDepOrNull(Key: Src)) {
4348 SDep Dep(Src, SDep::Barrier);
4349 Dep.setLatency(1);
4350 for (SUnit *Dst : *OrderDep) {
4351 SUnit *From = Src;
4352 SUnit *To = Dst;
4353 if (From->NodeNum > To->NodeNum)
4354 std::swap(a&: From, b&: To);
4355
4356 // Add a forward edge if the following conditions are met:
4357 //
4358 // - The instruction of the source node (FromMI) may read memory.
4359 // - The instruction of the target node (ToMI) may modify memory, but
4360 // does not read it.
4361 // - Neither instruction is a global barrier.
4362 // - The load appears before the store in the original basic block.
4363 // - There are no barrier or store instructions between the two nodes.
4364 // - The target node is unreachable from the source node in the current
4365 // DAG.
4366 //
4367 // TODO: These conditions are inherited from a previous implementation,
4368 // and some may no longer be necessary. For now, we conservatively
4369 // retain all of them to avoid regressions, but the logic could
4370 // potentially be simplified
4371 MachineInstr *FromMI = From->getInstr();
4372 MachineInstr *ToMI = To->getInstr();
4373 if (FromMI->mayLoad() && !ToMI->mayLoad() && ToMI->mayStore() &&
4374 !TII->isGlobalMemoryObject(MI: FromMI) &&
4375 !TII->isGlobalMemoryObject(MI: ToMI) && !isSuccOrder(SUa: From, SUb: To)) {
4376 SDep Pred = Dep;
4377 Pred.setSUnit(From);
4378 To->addPred(D: Pred);
4379 }
4380 }
4381 }
4382 }
4383}
4384
4385void LoopCarriedEdges::dump(SUnit *SU, const TargetRegisterInfo *TRI,
4386 const MachineRegisterInfo *MRI) const {
4387 const auto *Order = getOrderDepOrNull(Key: SU);
4388
4389 if (!Order)
4390 return;
4391
4392 const auto DumpSU = [](const SUnit *SU) {
4393 std::ostringstream OSS;
4394 OSS << "SU(" << SU->NodeNum << ")";
4395 return OSS.str();
4396 };
4397
4398 dbgs() << " Loop carried edges from " << DumpSU(SU) << "\n"
4399 << " Order\n";
4400 for (SUnit *Dst : *Order)
4401 dbgs() << " " << DumpSU(Dst) << "\n";
4402}
4403