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