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