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