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