xref: /freebsd/contrib/llvm-project/llvm/lib/Target/Hexagon/HexagonVLIWPacketizer.cpp (revision 5e801ac66d24704442eba426ed13c3effb8a34e7)
1 //===- HexagonPacketizer.cpp - VLIW packetizer ----------------------------===//
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 // This implements a simple VLIW packetizer using DFA. The packetizer works on
10 // machine basic blocks. For each instruction I in BB, the packetizer consults
11 // the DFA to see if machine resources are available to execute I. If so, the
12 // packetizer checks if I depends on any instruction J in the current packet.
13 // If no dependency is found, I is added to current packet and machine resource
14 // is marked as taken. If any dependency is found, a target API call is made to
15 // prune the dependence.
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #include "HexagonVLIWPacketizer.h"
20 #include "Hexagon.h"
21 #include "HexagonInstrInfo.h"
22 #include "HexagonRegisterInfo.h"
23 #include "HexagonSubtarget.h"
24 #include "llvm/ADT/BitVector.h"
25 #include "llvm/ADT/DenseSet.h"
26 #include "llvm/ADT/STLExtras.h"
27 #include "llvm/ADT/StringExtras.h"
28 #include "llvm/Analysis/AliasAnalysis.h"
29 #include "llvm/CodeGen/MachineBasicBlock.h"
30 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
31 #include "llvm/CodeGen/MachineDominators.h"
32 #include "llvm/CodeGen/MachineFrameInfo.h"
33 #include "llvm/CodeGen/MachineFunction.h"
34 #include "llvm/CodeGen/MachineFunctionPass.h"
35 #include "llvm/CodeGen/MachineInstr.h"
36 #include "llvm/CodeGen/MachineInstrBundle.h"
37 #include "llvm/CodeGen/MachineLoopInfo.h"
38 #include "llvm/CodeGen/MachineOperand.h"
39 #include "llvm/CodeGen/ScheduleDAG.h"
40 #include "llvm/CodeGen/TargetRegisterInfo.h"
41 #include "llvm/CodeGen/TargetSubtargetInfo.h"
42 #include "llvm/IR/DebugLoc.h"
43 #include "llvm/InitializePasses.h"
44 #include "llvm/MC/MCInstrDesc.h"
45 #include "llvm/Pass.h"
46 #include "llvm/Support/CommandLine.h"
47 #include "llvm/Support/Debug.h"
48 #include "llvm/Support/ErrorHandling.h"
49 #include "llvm/Support/raw_ostream.h"
50 #include <cassert>
51 #include <cstdint>
52 #include <iterator>
53 
54 using namespace llvm;
55 
56 #define DEBUG_TYPE "packets"
57 
58 static cl::opt<bool> DisablePacketizer("disable-packetizer", cl::Hidden,
59   cl::ZeroOrMore, cl::init(false),
60   cl::desc("Disable Hexagon packetizer pass"));
61 
62 static cl::opt<bool> Slot1Store("slot1-store-slot0-load", cl::Hidden,
63                                 cl::ZeroOrMore, cl::init(true),
64                                 cl::desc("Allow slot1 store and slot0 load"));
65 
66 static cl::opt<bool> PacketizeVolatiles("hexagon-packetize-volatiles",
67   cl::ZeroOrMore, cl::Hidden, cl::init(true),
68   cl::desc("Allow non-solo packetization of volatile memory references"));
69 
70 static cl::opt<bool> EnableGenAllInsnClass("enable-gen-insn", cl::init(false),
71   cl::Hidden, cl::ZeroOrMore, cl::desc("Generate all instruction with TC"));
72 
73 static cl::opt<bool> DisableVecDblNVStores("disable-vecdbl-nv-stores",
74   cl::init(false), cl::Hidden, cl::ZeroOrMore,
75   cl::desc("Disable vector double new-value-stores"));
76 
77 extern cl::opt<bool> ScheduleInlineAsm;
78 
79 namespace llvm {
80 
81 FunctionPass *createHexagonPacketizer(bool Minimal);
82 void initializeHexagonPacketizerPass(PassRegistry&);
83 
84 } // end namespace llvm
85 
86 namespace {
87 
88   class HexagonPacketizer : public MachineFunctionPass {
89   public:
90     static char ID;
91 
92     HexagonPacketizer(bool Min = false)
93       : MachineFunctionPass(ID), Minimal(Min) {}
94 
95     void getAnalysisUsage(AnalysisUsage &AU) const override {
96       AU.setPreservesCFG();
97       AU.addRequired<AAResultsWrapperPass>();
98       AU.addRequired<MachineBranchProbabilityInfo>();
99       AU.addRequired<MachineDominatorTree>();
100       AU.addRequired<MachineLoopInfo>();
101       AU.addPreserved<MachineDominatorTree>();
102       AU.addPreserved<MachineLoopInfo>();
103       MachineFunctionPass::getAnalysisUsage(AU);
104     }
105 
106     StringRef getPassName() const override { return "Hexagon Packetizer"; }
107     bool runOnMachineFunction(MachineFunction &Fn) override;
108 
109     MachineFunctionProperties getRequiredProperties() const override {
110       return MachineFunctionProperties().set(
111           MachineFunctionProperties::Property::NoVRegs);
112     }
113 
114   private:
115     const HexagonInstrInfo *HII = nullptr;
116     const HexagonRegisterInfo *HRI = nullptr;
117     const bool Minimal = false;
118   };
119 
120 } // end anonymous namespace
121 
122 char HexagonPacketizer::ID = 0;
123 
124 INITIALIZE_PASS_BEGIN(HexagonPacketizer, "hexagon-packetizer",
125                       "Hexagon Packetizer", false, false)
126 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
127 INITIALIZE_PASS_DEPENDENCY(MachineBranchProbabilityInfo)
128 INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
129 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
130 INITIALIZE_PASS_END(HexagonPacketizer, "hexagon-packetizer",
131                     "Hexagon Packetizer", false, false)
132 
133 HexagonPacketizerList::HexagonPacketizerList(MachineFunction &MF,
134       MachineLoopInfo &MLI, AAResults *AA,
135       const MachineBranchProbabilityInfo *MBPI, bool Minimal)
136     : VLIWPacketizerList(MF, MLI, AA), MBPI(MBPI), MLI(&MLI),
137       Minimal(Minimal) {
138   HII = MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
139   HRI = MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
140 
141   addMutation(std::make_unique<HexagonSubtarget::UsrOverflowMutation>());
142   addMutation(std::make_unique<HexagonSubtarget::HVXMemLatencyMutation>());
143   addMutation(std::make_unique<HexagonSubtarget::BankConflictMutation>());
144 }
145 
146 // Check if FirstI modifies a register that SecondI reads.
147 static bool hasWriteToReadDep(const MachineInstr &FirstI,
148                               const MachineInstr &SecondI,
149                               const TargetRegisterInfo *TRI) {
150   for (auto &MO : FirstI.operands()) {
151     if (!MO.isReg() || !MO.isDef())
152       continue;
153     Register R = MO.getReg();
154     if (SecondI.readsRegister(R, TRI))
155       return true;
156   }
157   return false;
158 }
159 
160 
161 static MachineBasicBlock::iterator moveInstrOut(MachineInstr &MI,
162       MachineBasicBlock::iterator BundleIt, bool Before) {
163   MachineBasicBlock::instr_iterator InsertPt;
164   if (Before)
165     InsertPt = BundleIt.getInstrIterator();
166   else
167     InsertPt = std::next(BundleIt).getInstrIterator();
168 
169   MachineBasicBlock &B = *MI.getParent();
170   // The instruction should at least be bundled with the preceding instruction
171   // (there will always be one, i.e. BUNDLE, if nothing else).
172   assert(MI.isBundledWithPred());
173   if (MI.isBundledWithSucc()) {
174     MI.clearFlag(MachineInstr::BundledSucc);
175     MI.clearFlag(MachineInstr::BundledPred);
176   } else {
177     // If it's not bundled with the successor (i.e. it is the last one
178     // in the bundle), then we can simply unbundle it from the predecessor,
179     // which will take care of updating the predecessor's flag.
180     MI.unbundleFromPred();
181   }
182   B.splice(InsertPt, &B, MI.getIterator());
183 
184   // Get the size of the bundle without asserting.
185   MachineBasicBlock::const_instr_iterator I = BundleIt.getInstrIterator();
186   MachineBasicBlock::const_instr_iterator E = B.instr_end();
187   unsigned Size = 0;
188   for (++I; I != E && I->isBundledWithPred(); ++I)
189     ++Size;
190 
191   // If there are still two or more instructions, then there is nothing
192   // else to be done.
193   if (Size > 1)
194     return BundleIt;
195 
196   // Otherwise, extract the single instruction out and delete the bundle.
197   MachineBasicBlock::iterator NextIt = std::next(BundleIt);
198   MachineInstr &SingleI = *BundleIt->getNextNode();
199   SingleI.unbundleFromPred();
200   assert(!SingleI.isBundledWithSucc());
201   BundleIt->eraseFromParent();
202   return NextIt;
203 }
204 
205 bool HexagonPacketizer::runOnMachineFunction(MachineFunction &MF) {
206   // FIXME: This pass causes verification failures.
207   MF.getProperties().set(
208       MachineFunctionProperties::Property::FailsVerification);
209 
210   auto &HST = MF.getSubtarget<HexagonSubtarget>();
211   HII = HST.getInstrInfo();
212   HRI = HST.getRegisterInfo();
213   auto &MLI = getAnalysis<MachineLoopInfo>();
214   auto *AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
215   auto *MBPI = &getAnalysis<MachineBranchProbabilityInfo>();
216 
217   if (EnableGenAllInsnClass)
218     HII->genAllInsnTimingClasses(MF);
219 
220   // Instantiate the packetizer.
221   bool MinOnly = Minimal || DisablePacketizer || !HST.usePackets() ||
222                  skipFunction(MF.getFunction());
223   HexagonPacketizerList Packetizer(MF, MLI, AA, MBPI, MinOnly);
224 
225   // DFA state table should not be empty.
226   assert(Packetizer.getResourceTracker() && "Empty DFA table!");
227 
228   // Loop over all basic blocks and remove KILL pseudo-instructions
229   // These instructions confuse the dependence analysis. Consider:
230   // D0 = ...   (Insn 0)
231   // R0 = KILL R0, D0 (Insn 1)
232   // R0 = ... (Insn 2)
233   // Here, Insn 1 will result in the dependence graph not emitting an output
234   // dependence between Insn 0 and Insn 2. This can lead to incorrect
235   // packetization
236   for (MachineBasicBlock &MB : MF) {
237     for (MachineInstr &MI : llvm::make_early_inc_range(MB))
238       if (MI.isKill())
239         MB.erase(&MI);
240   }
241 
242   // TinyCore with Duplexes: Translate to big-instructions.
243   if (HST.isTinyCoreWithDuplex())
244     HII->translateInstrsForDup(MF, true);
245 
246   // Loop over all of the basic blocks.
247   for (auto &MB : MF) {
248     auto Begin = MB.begin(), End = MB.end();
249     while (Begin != End) {
250       // Find the first non-boundary starting from the end of the last
251       // scheduling region.
252       MachineBasicBlock::iterator RB = Begin;
253       while (RB != End && HII->isSchedulingBoundary(*RB, &MB, MF))
254         ++RB;
255       // Find the first boundary starting from the beginning of the new
256       // region.
257       MachineBasicBlock::iterator RE = RB;
258       while (RE != End && !HII->isSchedulingBoundary(*RE, &MB, MF))
259         ++RE;
260       // Add the scheduling boundary if it's not block end.
261       if (RE != End)
262         ++RE;
263       // If RB == End, then RE == End.
264       if (RB != End)
265         Packetizer.PacketizeMIs(&MB, RB, RE);
266 
267       Begin = RE;
268     }
269   }
270 
271   // TinyCore with Duplexes: Translate to tiny-instructions.
272   if (HST.isTinyCoreWithDuplex())
273     HII->translateInstrsForDup(MF, false);
274 
275   Packetizer.unpacketizeSoloInstrs(MF);
276   return true;
277 }
278 
279 // Reserve resources for a constant extender. Trigger an assertion if the
280 // reservation fails.
281 void HexagonPacketizerList::reserveResourcesForConstExt() {
282   if (!tryAllocateResourcesForConstExt(true))
283     llvm_unreachable("Resources not available");
284 }
285 
286 bool HexagonPacketizerList::canReserveResourcesForConstExt() {
287   return tryAllocateResourcesForConstExt(false);
288 }
289 
290 // Allocate resources (i.e. 4 bytes) for constant extender. If succeeded,
291 // return true, otherwise, return false.
292 bool HexagonPacketizerList::tryAllocateResourcesForConstExt(bool Reserve) {
293   auto *ExtMI = MF.CreateMachineInstr(HII->get(Hexagon::A4_ext), DebugLoc());
294   bool Avail = ResourceTracker->canReserveResources(*ExtMI);
295   if (Reserve && Avail)
296     ResourceTracker->reserveResources(*ExtMI);
297   MF.DeleteMachineInstr(ExtMI);
298   return Avail;
299 }
300 
301 bool HexagonPacketizerList::isCallDependent(const MachineInstr &MI,
302       SDep::Kind DepType, unsigned DepReg) {
303   // Check for LR dependence.
304   if (DepReg == HRI->getRARegister())
305     return true;
306 
307   if (HII->isDeallocRet(MI))
308     if (DepReg == HRI->getFrameRegister() || DepReg == HRI->getStackRegister())
309       return true;
310 
311   // Call-like instructions can be packetized with preceding instructions
312   // that define registers implicitly used or modified by the call. Explicit
313   // uses are still prohibited, as in the case of indirect calls:
314   //   r0 = ...
315   //   J2_jumpr r0
316   if (DepType == SDep::Data) {
317     for (const MachineOperand &MO : MI.operands())
318       if (MO.isReg() && MO.getReg() == DepReg && !MO.isImplicit())
319         return true;
320   }
321 
322   return false;
323 }
324 
325 static bool isRegDependence(const SDep::Kind DepType) {
326   return DepType == SDep::Data || DepType == SDep::Anti ||
327          DepType == SDep::Output;
328 }
329 
330 static bool isDirectJump(const MachineInstr &MI) {
331   return MI.getOpcode() == Hexagon::J2_jump;
332 }
333 
334 static bool isSchedBarrier(const MachineInstr &MI) {
335   switch (MI.getOpcode()) {
336   case Hexagon::Y2_barrier:
337     return true;
338   }
339   return false;
340 }
341 
342 static bool isControlFlow(const MachineInstr &MI) {
343   return MI.getDesc().isTerminator() || MI.getDesc().isCall();
344 }
345 
346 /// Returns true if the instruction modifies a callee-saved register.
347 static bool doesModifyCalleeSavedReg(const MachineInstr &MI,
348                                      const TargetRegisterInfo *TRI) {
349   const MachineFunction &MF = *MI.getParent()->getParent();
350   for (auto *CSR = TRI->getCalleeSavedRegs(&MF); CSR && *CSR; ++CSR)
351     if (MI.modifiesRegister(*CSR, TRI))
352       return true;
353   return false;
354 }
355 
356 // Returns true if an instruction can be promoted to .new predicate or
357 // new-value store.
358 bool HexagonPacketizerList::isNewifiable(const MachineInstr &MI,
359       const TargetRegisterClass *NewRC) {
360   // Vector stores can be predicated, and can be new-value stores, but
361   // they cannot be predicated on a .new predicate value.
362   if (NewRC == &Hexagon::PredRegsRegClass) {
363     if (HII->isHVXVec(MI) && MI.mayStore())
364       return false;
365     return HII->isPredicated(MI) && HII->getDotNewPredOp(MI, nullptr) > 0;
366   }
367   // If the class is not PredRegs, it could only apply to new-value stores.
368   return HII->mayBeNewStore(MI);
369 }
370 
371 // Promote an instructiont to its .cur form.
372 // At this time, we have already made a call to canPromoteToDotCur and made
373 // sure that it can *indeed* be promoted.
374 bool HexagonPacketizerList::promoteToDotCur(MachineInstr &MI,
375       SDep::Kind DepType, MachineBasicBlock::iterator &MII,
376       const TargetRegisterClass* RC) {
377   assert(DepType == SDep::Data);
378   int CurOpcode = HII->getDotCurOp(MI);
379   MI.setDesc(HII->get(CurOpcode));
380   return true;
381 }
382 
383 void HexagonPacketizerList::cleanUpDotCur() {
384   MachineInstr *MI = nullptr;
385   for (auto BI : CurrentPacketMIs) {
386     LLVM_DEBUG(dbgs() << "Cleanup packet has "; BI->dump(););
387     if (HII->isDotCurInst(*BI)) {
388       MI = BI;
389       continue;
390     }
391     if (MI) {
392       for (auto &MO : BI->operands())
393         if (MO.isReg() && MO.getReg() == MI->getOperand(0).getReg())
394           return;
395     }
396   }
397   if (!MI)
398     return;
399   // We did not find a use of the CUR, so de-cur it.
400   MI->setDesc(HII->get(HII->getNonDotCurOp(*MI)));
401   LLVM_DEBUG(dbgs() << "Demoted CUR "; MI->dump(););
402 }
403 
404 // Check to see if an instruction can be dot cur.
405 bool HexagonPacketizerList::canPromoteToDotCur(const MachineInstr &MI,
406       const SUnit *PacketSU, unsigned DepReg, MachineBasicBlock::iterator &MII,
407       const TargetRegisterClass *RC) {
408   if (!HII->isHVXVec(MI))
409     return false;
410   if (!HII->isHVXVec(*MII))
411     return false;
412 
413   // Already a dot new instruction.
414   if (HII->isDotCurInst(MI) && !HII->mayBeCurLoad(MI))
415     return false;
416 
417   if (!HII->mayBeCurLoad(MI))
418     return false;
419 
420   // The "cur value" cannot come from inline asm.
421   if (PacketSU->getInstr()->isInlineAsm())
422     return false;
423 
424   // Make sure candidate instruction uses cur.
425   LLVM_DEBUG(dbgs() << "Can we DOT Cur Vector MI\n"; MI.dump();
426              dbgs() << "in packet\n";);
427   MachineInstr &MJ = *MII;
428   LLVM_DEBUG({
429     dbgs() << "Checking CUR against ";
430     MJ.dump();
431   });
432   Register DestReg = MI.getOperand(0).getReg();
433   bool FoundMatch = false;
434   for (auto &MO : MJ.operands())
435     if (MO.isReg() && MO.getReg() == DestReg)
436       FoundMatch = true;
437   if (!FoundMatch)
438     return false;
439 
440   // Check for existing uses of a vector register within the packet which
441   // would be affected by converting a vector load into .cur formt.
442   for (auto BI : CurrentPacketMIs) {
443     LLVM_DEBUG(dbgs() << "packet has "; BI->dump(););
444     if (BI->readsRegister(DepReg, MF.getSubtarget().getRegisterInfo()))
445       return false;
446   }
447 
448   LLVM_DEBUG(dbgs() << "Can Dot CUR MI\n"; MI.dump(););
449   // We can convert the opcode into a .cur.
450   return true;
451 }
452 
453 // Promote an instruction to its .new form. At this time, we have already
454 // made a call to canPromoteToDotNew and made sure that it can *indeed* be
455 // promoted.
456 bool HexagonPacketizerList::promoteToDotNew(MachineInstr &MI,
457       SDep::Kind DepType, MachineBasicBlock::iterator &MII,
458       const TargetRegisterClass* RC) {
459   assert(DepType == SDep::Data);
460   int NewOpcode;
461   if (RC == &Hexagon::PredRegsRegClass)
462     NewOpcode = HII->getDotNewPredOp(MI, MBPI);
463   else
464     NewOpcode = HII->getDotNewOp(MI);
465   MI.setDesc(HII->get(NewOpcode));
466   return true;
467 }
468 
469 bool HexagonPacketizerList::demoteToDotOld(MachineInstr &MI) {
470   int NewOpcode = HII->getDotOldOp(MI);
471   MI.setDesc(HII->get(NewOpcode));
472   return true;
473 }
474 
475 bool HexagonPacketizerList::useCallersSP(MachineInstr &MI) {
476   unsigned Opc = MI.getOpcode();
477   switch (Opc) {
478     case Hexagon::S2_storerd_io:
479     case Hexagon::S2_storeri_io:
480     case Hexagon::S2_storerh_io:
481     case Hexagon::S2_storerb_io:
482       break;
483     default:
484       llvm_unreachable("Unexpected instruction");
485   }
486   unsigned FrameSize = MF.getFrameInfo().getStackSize();
487   MachineOperand &Off = MI.getOperand(1);
488   int64_t NewOff = Off.getImm() - (FrameSize + HEXAGON_LRFP_SIZE);
489   if (HII->isValidOffset(Opc, NewOff, HRI)) {
490     Off.setImm(NewOff);
491     return true;
492   }
493   return false;
494 }
495 
496 void HexagonPacketizerList::useCalleesSP(MachineInstr &MI) {
497   unsigned Opc = MI.getOpcode();
498   switch (Opc) {
499     case Hexagon::S2_storerd_io:
500     case Hexagon::S2_storeri_io:
501     case Hexagon::S2_storerh_io:
502     case Hexagon::S2_storerb_io:
503       break;
504     default:
505       llvm_unreachable("Unexpected instruction");
506   }
507   unsigned FrameSize = MF.getFrameInfo().getStackSize();
508   MachineOperand &Off = MI.getOperand(1);
509   Off.setImm(Off.getImm() + FrameSize + HEXAGON_LRFP_SIZE);
510 }
511 
512 /// Return true if we can update the offset in MI so that MI and MJ
513 /// can be packetized together.
514 bool HexagonPacketizerList::updateOffset(SUnit *SUI, SUnit *SUJ) {
515   assert(SUI->getInstr() && SUJ->getInstr());
516   MachineInstr &MI = *SUI->getInstr();
517   MachineInstr &MJ = *SUJ->getInstr();
518 
519   unsigned BPI, OPI;
520   if (!HII->getBaseAndOffsetPosition(MI, BPI, OPI))
521     return false;
522   unsigned BPJ, OPJ;
523   if (!HII->getBaseAndOffsetPosition(MJ, BPJ, OPJ))
524     return false;
525   Register Reg = MI.getOperand(BPI).getReg();
526   if (Reg != MJ.getOperand(BPJ).getReg())
527     return false;
528   // Make sure that the dependences do not restrict adding MI to the packet.
529   // That is, ignore anti dependences, and make sure the only data dependence
530   // involves the specific register.
531   for (const auto &PI : SUI->Preds)
532     if (PI.getKind() != SDep::Anti &&
533         (PI.getKind() != SDep::Data || PI.getReg() != Reg))
534       return false;
535   int Incr;
536   if (!HII->getIncrementValue(MJ, Incr))
537     return false;
538 
539   int64_t Offset = MI.getOperand(OPI).getImm();
540   if (!HII->isValidOffset(MI.getOpcode(), Offset+Incr, HRI))
541     return false;
542 
543   MI.getOperand(OPI).setImm(Offset + Incr);
544   ChangedOffset = Offset;
545   return true;
546 }
547 
548 /// Undo the changed offset. This is needed if the instruction cannot be
549 /// added to the current packet due to a different instruction.
550 void HexagonPacketizerList::undoChangedOffset(MachineInstr &MI) {
551   unsigned BP, OP;
552   if (!HII->getBaseAndOffsetPosition(MI, BP, OP))
553     llvm_unreachable("Unable to find base and offset operands.");
554   MI.getOperand(OP).setImm(ChangedOffset);
555 }
556 
557 enum PredicateKind {
558   PK_False,
559   PK_True,
560   PK_Unknown
561 };
562 
563 /// Returns true if an instruction is predicated on p0 and false if it's
564 /// predicated on !p0.
565 static PredicateKind getPredicateSense(const MachineInstr &MI,
566                                        const HexagonInstrInfo *HII) {
567   if (!HII->isPredicated(MI))
568     return PK_Unknown;
569   if (HII->isPredicatedTrue(MI))
570     return PK_True;
571   return PK_False;
572 }
573 
574 static const MachineOperand &getPostIncrementOperand(const MachineInstr &MI,
575       const HexagonInstrInfo *HII) {
576   assert(HII->isPostIncrement(MI) && "Not a post increment operation.");
577 #ifndef NDEBUG
578   // Post Increment means duplicates. Use dense map to find duplicates in the
579   // list. Caution: Densemap initializes with the minimum of 64 buckets,
580   // whereas there are at most 5 operands in the post increment.
581   DenseSet<unsigned> DefRegsSet;
582   for (auto &MO : MI.operands())
583     if (MO.isReg() && MO.isDef())
584       DefRegsSet.insert(MO.getReg());
585 
586   for (auto &MO : MI.operands())
587     if (MO.isReg() && MO.isUse() && DefRegsSet.count(MO.getReg()))
588       return MO;
589 #else
590   if (MI.mayLoad()) {
591     const MachineOperand &Op1 = MI.getOperand(1);
592     // The 2nd operand is always the post increment operand in load.
593     assert(Op1.isReg() && "Post increment operand has be to a register.");
594     return Op1;
595   }
596   if (MI.getDesc().mayStore()) {
597     const MachineOperand &Op0 = MI.getOperand(0);
598     // The 1st operand is always the post increment operand in store.
599     assert(Op0.isReg() && "Post increment operand has be to a register.");
600     return Op0;
601   }
602 #endif
603   // we should never come here.
604   llvm_unreachable("mayLoad or mayStore not set for Post Increment operation");
605 }
606 
607 // Get the value being stored.
608 static const MachineOperand& getStoreValueOperand(const MachineInstr &MI) {
609   // value being stored is always the last operand.
610   return MI.getOperand(MI.getNumOperands()-1);
611 }
612 
613 static bool isLoadAbsSet(const MachineInstr &MI) {
614   unsigned Opc = MI.getOpcode();
615   switch (Opc) {
616     case Hexagon::L4_loadrd_ap:
617     case Hexagon::L4_loadrb_ap:
618     case Hexagon::L4_loadrh_ap:
619     case Hexagon::L4_loadrub_ap:
620     case Hexagon::L4_loadruh_ap:
621     case Hexagon::L4_loadri_ap:
622       return true;
623   }
624   return false;
625 }
626 
627 static const MachineOperand &getAbsSetOperand(const MachineInstr &MI) {
628   assert(isLoadAbsSet(MI));
629   return MI.getOperand(1);
630 }
631 
632 // Can be new value store?
633 // Following restrictions are to be respected in convert a store into
634 // a new value store.
635 // 1. If an instruction uses auto-increment, its address register cannot
636 //    be a new-value register. Arch Spec 5.4.2.1
637 // 2. If an instruction uses absolute-set addressing mode, its address
638 //    register cannot be a new-value register. Arch Spec 5.4.2.1.
639 // 3. If an instruction produces a 64-bit result, its registers cannot be used
640 //    as new-value registers. Arch Spec 5.4.2.2.
641 // 4. If the instruction that sets the new-value register is conditional, then
642 //    the instruction that uses the new-value register must also be conditional,
643 //    and both must always have their predicates evaluate identically.
644 //    Arch Spec 5.4.2.3.
645 // 5. There is an implied restriction that a packet cannot have another store,
646 //    if there is a new value store in the packet. Corollary: if there is
647 //    already a store in a packet, there can not be a new value store.
648 //    Arch Spec: 3.4.4.2
649 bool HexagonPacketizerList::canPromoteToNewValueStore(const MachineInstr &MI,
650       const MachineInstr &PacketMI, unsigned DepReg) {
651   // Make sure we are looking at the store, that can be promoted.
652   if (!HII->mayBeNewStore(MI))
653     return false;
654 
655   // Make sure there is dependency and can be new value'd.
656   const MachineOperand &Val = getStoreValueOperand(MI);
657   if (Val.isReg() && Val.getReg() != DepReg)
658     return false;
659 
660   const MCInstrDesc& MCID = PacketMI.getDesc();
661 
662   // First operand is always the result.
663   const TargetRegisterClass *PacketRC = HII->getRegClass(MCID, 0, HRI, MF);
664   // Double regs can not feed into new value store: PRM section: 5.4.2.2.
665   if (PacketRC == &Hexagon::DoubleRegsRegClass)
666     return false;
667 
668   // New-value stores are of class NV (slot 0), dual stores require class ST
669   // in slot 0 (PRM 5.5).
670   for (auto I : CurrentPacketMIs) {
671     SUnit *PacketSU = MIToSUnit.find(I)->second;
672     if (PacketSU->getInstr()->mayStore())
673       return false;
674   }
675 
676   // Make sure it's NOT the post increment register that we are going to
677   // new value.
678   if (HII->isPostIncrement(MI) &&
679       getPostIncrementOperand(MI, HII).getReg() == DepReg) {
680     return false;
681   }
682 
683   if (HII->isPostIncrement(PacketMI) && PacketMI.mayLoad() &&
684       getPostIncrementOperand(PacketMI, HII).getReg() == DepReg) {
685     // If source is post_inc, or absolute-set addressing, it can not feed
686     // into new value store
687     //   r3 = memw(r2++#4)
688     //   memw(r30 + #-1404) = r2.new -> can not be new value store
689     // arch spec section: 5.4.2.1.
690     return false;
691   }
692 
693   if (isLoadAbsSet(PacketMI) && getAbsSetOperand(PacketMI).getReg() == DepReg)
694     return false;
695 
696   // If the source that feeds the store is predicated, new value store must
697   // also be predicated.
698   if (HII->isPredicated(PacketMI)) {
699     if (!HII->isPredicated(MI))
700       return false;
701 
702     // Check to make sure that they both will have their predicates
703     // evaluate identically.
704     unsigned predRegNumSrc = 0;
705     unsigned predRegNumDst = 0;
706     const TargetRegisterClass* predRegClass = nullptr;
707 
708     // Get predicate register used in the source instruction.
709     for (auto &MO : PacketMI.operands()) {
710       if (!MO.isReg())
711         continue;
712       predRegNumSrc = MO.getReg();
713       predRegClass = HRI->getMinimalPhysRegClass(predRegNumSrc);
714       if (predRegClass == &Hexagon::PredRegsRegClass)
715         break;
716     }
717     assert((predRegClass == &Hexagon::PredRegsRegClass) &&
718         "predicate register not found in a predicated PacketMI instruction");
719 
720     // Get predicate register used in new-value store instruction.
721     for (auto &MO : MI.operands()) {
722       if (!MO.isReg())
723         continue;
724       predRegNumDst = MO.getReg();
725       predRegClass = HRI->getMinimalPhysRegClass(predRegNumDst);
726       if (predRegClass == &Hexagon::PredRegsRegClass)
727         break;
728     }
729     assert((predRegClass == &Hexagon::PredRegsRegClass) &&
730            "predicate register not found in a predicated MI instruction");
731 
732     // New-value register producer and user (store) need to satisfy these
733     // constraints:
734     // 1) Both instructions should be predicated on the same register.
735     // 2) If producer of the new-value register is .new predicated then store
736     // should also be .new predicated and if producer is not .new predicated
737     // then store should not be .new predicated.
738     // 3) Both new-value register producer and user should have same predicate
739     // sense, i.e, either both should be negated or both should be non-negated.
740     if (predRegNumDst != predRegNumSrc ||
741         HII->isDotNewInst(PacketMI) != HII->isDotNewInst(MI) ||
742         getPredicateSense(MI, HII) != getPredicateSense(PacketMI, HII))
743       return false;
744   }
745 
746   // Make sure that other than the new-value register no other store instruction
747   // register has been modified in the same packet. Predicate registers can be
748   // modified by they should not be modified between the producer and the store
749   // instruction as it will make them both conditional on different values.
750   // We already know this to be true for all the instructions before and
751   // including PacketMI. Howerver, we need to perform the check for the
752   // remaining instructions in the packet.
753 
754   unsigned StartCheck = 0;
755 
756   for (auto I : CurrentPacketMIs) {
757     SUnit *TempSU = MIToSUnit.find(I)->second;
758     MachineInstr &TempMI = *TempSU->getInstr();
759 
760     // Following condition is true for all the instructions until PacketMI is
761     // reached (StartCheck is set to 0 before the for loop).
762     // StartCheck flag is 1 for all the instructions after PacketMI.
763     if (&TempMI != &PacketMI && !StartCheck) // Start processing only after
764       continue;                              // encountering PacketMI.
765 
766     StartCheck = 1;
767     if (&TempMI == &PacketMI) // We don't want to check PacketMI for dependence.
768       continue;
769 
770     for (auto &MO : MI.operands())
771       if (MO.isReg() && TempSU->getInstr()->modifiesRegister(MO.getReg(), HRI))
772         return false;
773   }
774 
775   // Make sure that for non-POST_INC stores:
776   // 1. The only use of reg is DepReg and no other registers.
777   //    This handles base+index registers.
778   //    The following store can not be dot new.
779   //    Eg.   r0 = add(r0, #3)
780   //          memw(r1+r0<<#2) = r0
781   if (!HII->isPostIncrement(MI)) {
782     for (unsigned opNum = 0; opNum < MI.getNumOperands()-1; opNum++) {
783       const MachineOperand &MO = MI.getOperand(opNum);
784       if (MO.isReg() && MO.getReg() == DepReg)
785         return false;
786     }
787   }
788 
789   // If data definition is because of implicit definition of the register,
790   // do not newify the store. Eg.
791   // %r9 = ZXTH %r12, implicit %d6, implicit-def %r12
792   // S2_storerh_io %r8, 2, killed %r12; mem:ST2[%scevgep343]
793   for (auto &MO : PacketMI.operands()) {
794     if (MO.isRegMask() && MO.clobbersPhysReg(DepReg))
795       return false;
796     if (!MO.isReg() || !MO.isDef() || !MO.isImplicit())
797       continue;
798     Register R = MO.getReg();
799     if (R == DepReg || HRI->isSuperRegister(DepReg, R))
800       return false;
801   }
802 
803   // Handle imp-use of super reg case. There is a target independent side
804   // change that should prevent this situation but I am handling it for
805   // just-in-case. For example, we cannot newify R2 in the following case:
806   // %r3 = A2_tfrsi 0;
807   // S2_storeri_io killed %r0, 0, killed %r2, implicit killed %d1;
808   for (auto &MO : MI.operands()) {
809     if (MO.isReg() && MO.isUse() && MO.isImplicit() && MO.getReg() == DepReg)
810       return false;
811   }
812 
813   // Can be dot new store.
814   return true;
815 }
816 
817 // Can this MI to promoted to either new value store or new value jump.
818 bool HexagonPacketizerList::canPromoteToNewValue(const MachineInstr &MI,
819       const SUnit *PacketSU, unsigned DepReg,
820       MachineBasicBlock::iterator &MII) {
821   if (!HII->mayBeNewStore(MI))
822     return false;
823 
824   // Check to see the store can be new value'ed.
825   MachineInstr &PacketMI = *PacketSU->getInstr();
826   if (canPromoteToNewValueStore(MI, PacketMI, DepReg))
827     return true;
828 
829   // Check to see the compare/jump can be new value'ed.
830   // This is done as a pass on its own. Don't need to check it here.
831   return false;
832 }
833 
834 static bool isImplicitDependency(const MachineInstr &I, bool CheckDef,
835       unsigned DepReg) {
836   for (auto &MO : I.operands()) {
837     if (CheckDef && MO.isRegMask() && MO.clobbersPhysReg(DepReg))
838       return true;
839     if (!MO.isReg() || MO.getReg() != DepReg || !MO.isImplicit())
840       continue;
841     if (CheckDef == MO.isDef())
842       return true;
843   }
844   return false;
845 }
846 
847 // Check to see if an instruction can be dot new.
848 bool HexagonPacketizerList::canPromoteToDotNew(const MachineInstr &MI,
849       const SUnit *PacketSU, unsigned DepReg, MachineBasicBlock::iterator &MII,
850       const TargetRegisterClass* RC) {
851   // Already a dot new instruction.
852   if (HII->isDotNewInst(MI) && !HII->mayBeNewStore(MI))
853     return false;
854 
855   if (!isNewifiable(MI, RC))
856     return false;
857 
858   const MachineInstr &PI = *PacketSU->getInstr();
859 
860   // The "new value" cannot come from inline asm.
861   if (PI.isInlineAsm())
862     return false;
863 
864   // IMPLICIT_DEFs won't materialize as real instructions, so .new makes no
865   // sense.
866   if (PI.isImplicitDef())
867     return false;
868 
869   // If dependency is trough an implicitly defined register, we should not
870   // newify the use.
871   if (isImplicitDependency(PI, true, DepReg) ||
872       isImplicitDependency(MI, false, DepReg))
873     return false;
874 
875   const MCInstrDesc& MCID = PI.getDesc();
876   const TargetRegisterClass *VecRC = HII->getRegClass(MCID, 0, HRI, MF);
877   if (DisableVecDblNVStores && VecRC == &Hexagon::HvxWRRegClass)
878     return false;
879 
880   // predicate .new
881   if (RC == &Hexagon::PredRegsRegClass)
882     return HII->predCanBeUsedAsDotNew(PI, DepReg);
883 
884   if (RC != &Hexagon::PredRegsRegClass && !HII->mayBeNewStore(MI))
885     return false;
886 
887   // Create a dot new machine instruction to see if resources can be
888   // allocated. If not, bail out now.
889   int NewOpcode = HII->getDotNewOp(MI);
890   const MCInstrDesc &D = HII->get(NewOpcode);
891   MachineInstr *NewMI = MF.CreateMachineInstr(D, DebugLoc());
892   bool ResourcesAvailable = ResourceTracker->canReserveResources(*NewMI);
893   MF.DeleteMachineInstr(NewMI);
894   if (!ResourcesAvailable)
895     return false;
896 
897   // New Value Store only. New Value Jump generated as a separate pass.
898   if (!canPromoteToNewValue(MI, PacketSU, DepReg, MII))
899     return false;
900 
901   return true;
902 }
903 
904 // Go through the packet instructions and search for an anti dependency between
905 // them and DepReg from MI. Consider this case:
906 // Trying to add
907 // a) %r1 = TFRI_cdNotPt %p3, 2
908 // to this packet:
909 // {
910 //   b) %p0 = C2_or killed %p3, killed %p0
911 //   c) %p3 = C2_tfrrp %r23
912 //   d) %r1 = C2_cmovenewit %p3, 4
913 //  }
914 // The P3 from a) and d) will be complements after
915 // a)'s P3 is converted to .new form
916 // Anti-dep between c) and b) is irrelevant for this case
917 bool HexagonPacketizerList::restrictingDepExistInPacket(MachineInstr &MI,
918                                                         unsigned DepReg) {
919   SUnit *PacketSUDep = MIToSUnit.find(&MI)->second;
920 
921   for (auto I : CurrentPacketMIs) {
922     // We only care for dependencies to predicated instructions
923     if (!HII->isPredicated(*I))
924       continue;
925 
926     // Scheduling Unit for current insn in the packet
927     SUnit *PacketSU = MIToSUnit.find(I)->second;
928 
929     // Look at dependencies between current members of the packet and
930     // predicate defining instruction MI. Make sure that dependency is
931     // on the exact register we care about.
932     if (PacketSU->isSucc(PacketSUDep)) {
933       for (unsigned i = 0; i < PacketSU->Succs.size(); ++i) {
934         auto &Dep = PacketSU->Succs[i];
935         if (Dep.getSUnit() == PacketSUDep && Dep.getKind() == SDep::Anti &&
936             Dep.getReg() == DepReg)
937           return true;
938       }
939     }
940   }
941 
942   return false;
943 }
944 
945 /// Gets the predicate register of a predicated instruction.
946 static unsigned getPredicatedRegister(MachineInstr &MI,
947                                       const HexagonInstrInfo *QII) {
948   /// We use the following rule: The first predicate register that is a use is
949   /// the predicate register of a predicated instruction.
950   assert(QII->isPredicated(MI) && "Must be predicated instruction");
951 
952   for (auto &Op : MI.operands()) {
953     if (Op.isReg() && Op.getReg() && Op.isUse() &&
954         Hexagon::PredRegsRegClass.contains(Op.getReg()))
955       return Op.getReg();
956   }
957 
958   llvm_unreachable("Unknown instruction operand layout");
959   return 0;
960 }
961 
962 // Given two predicated instructions, this function detects whether
963 // the predicates are complements.
964 bool HexagonPacketizerList::arePredicatesComplements(MachineInstr &MI1,
965                                                      MachineInstr &MI2) {
966   // If we don't know the predicate sense of the instructions bail out early, we
967   // need it later.
968   if (getPredicateSense(MI1, HII) == PK_Unknown ||
969       getPredicateSense(MI2, HII) == PK_Unknown)
970     return false;
971 
972   // Scheduling unit for candidate.
973   SUnit *SU = MIToSUnit[&MI1];
974 
975   // One corner case deals with the following scenario:
976   // Trying to add
977   // a) %r24 = A2_tfrt %p0, %r25
978   // to this packet:
979   // {
980   //   b) %r25 = A2_tfrf %p0, %r24
981   //   c) %p0 = C2_cmpeqi %r26, 1
982   // }
983   //
984   // On general check a) and b) are complements, but presence of c) will
985   // convert a) to .new form, and then it is not a complement.
986   // We attempt to detect it by analyzing existing dependencies in the packet.
987 
988   // Analyze relationships between all existing members of the packet.
989   // Look for Anti dependecy on the same predicate reg as used in the
990   // candidate.
991   for (auto I : CurrentPacketMIs) {
992     // Scheduling Unit for current insn in the packet.
993     SUnit *PacketSU = MIToSUnit.find(I)->second;
994 
995     // If this instruction in the packet is succeeded by the candidate...
996     if (PacketSU->isSucc(SU)) {
997       for (unsigned i = 0; i < PacketSU->Succs.size(); ++i) {
998         auto Dep = PacketSU->Succs[i];
999         // The corner case exist when there is true data dependency between
1000         // candidate and one of current packet members, this dep is on
1001         // predicate reg, and there already exist anti dep on the same pred in
1002         // the packet.
1003         if (Dep.getSUnit() == SU && Dep.getKind() == SDep::Data &&
1004             Hexagon::PredRegsRegClass.contains(Dep.getReg())) {
1005           // Here I know that I is predicate setting instruction with true
1006           // data dep to candidate on the register we care about - c) in the
1007           // above example. Now I need to see if there is an anti dependency
1008           // from c) to any other instruction in the same packet on the pred
1009           // reg of interest.
1010           if (restrictingDepExistInPacket(*I, Dep.getReg()))
1011             return false;
1012         }
1013       }
1014     }
1015   }
1016 
1017   // If the above case does not apply, check regular complement condition.
1018   // Check that the predicate register is the same and that the predicate
1019   // sense is different We also need to differentiate .old vs. .new: !p0
1020   // is not complementary to p0.new.
1021   unsigned PReg1 = getPredicatedRegister(MI1, HII);
1022   unsigned PReg2 = getPredicatedRegister(MI2, HII);
1023   return PReg1 == PReg2 &&
1024          Hexagon::PredRegsRegClass.contains(PReg1) &&
1025          Hexagon::PredRegsRegClass.contains(PReg2) &&
1026          getPredicateSense(MI1, HII) != getPredicateSense(MI2, HII) &&
1027          HII->isDotNewInst(MI1) == HII->isDotNewInst(MI2);
1028 }
1029 
1030 // Initialize packetizer flags.
1031 void HexagonPacketizerList::initPacketizerState() {
1032   Dependence = false;
1033   PromotedToDotNew = false;
1034   GlueToNewValueJump = false;
1035   GlueAllocframeStore = false;
1036   FoundSequentialDependence = false;
1037   ChangedOffset = INT64_MAX;
1038 }
1039 
1040 // Ignore bundling of pseudo instructions.
1041 bool HexagonPacketizerList::ignorePseudoInstruction(const MachineInstr &MI,
1042                                                     const MachineBasicBlock *) {
1043   if (MI.isDebugInstr())
1044     return true;
1045 
1046   if (MI.isCFIInstruction())
1047     return false;
1048 
1049   // We must print out inline assembly.
1050   if (MI.isInlineAsm())
1051     return false;
1052 
1053   if (MI.isImplicitDef())
1054     return false;
1055 
1056   // We check if MI has any functional units mapped to it. If it doesn't,
1057   // we ignore the instruction.
1058   const MCInstrDesc& TID = MI.getDesc();
1059   auto *IS = ResourceTracker->getInstrItins()->beginStage(TID.getSchedClass());
1060   return !IS->getUnits();
1061 }
1062 
1063 bool HexagonPacketizerList::isSoloInstruction(const MachineInstr &MI) {
1064   // Ensure any bundles created by gather packetize remain separate.
1065   if (MI.isBundle())
1066     return true;
1067 
1068   if (MI.isEHLabel() || MI.isCFIInstruction())
1069     return true;
1070 
1071   // Consider inline asm to not be a solo instruction by default.
1072   // Inline asm will be put in a packet temporarily, but then it will be
1073   // removed, and placed outside of the packet (before or after, depending
1074   // on dependencies).  This is to reduce the impact of inline asm as a
1075   // "packet splitting" instruction.
1076   if (MI.isInlineAsm() && !ScheduleInlineAsm)
1077     return true;
1078 
1079   if (isSchedBarrier(MI))
1080     return true;
1081 
1082   if (HII->isSolo(MI))
1083     return true;
1084 
1085   if (MI.getOpcode() == Hexagon::A2_nop)
1086     return true;
1087 
1088   return false;
1089 }
1090 
1091 // Quick check if instructions MI and MJ cannot coexist in the same packet.
1092 // Limit the tests to be "one-way", e.g.  "if MI->isBranch and MJ->isInlineAsm",
1093 // but not the symmetric case: "if MJ->isBranch and MI->isInlineAsm".
1094 // For full test call this function twice:
1095 //   cannotCoexistAsymm(MI, MJ) || cannotCoexistAsymm(MJ, MI)
1096 // Doing the test only one way saves the amount of code in this function,
1097 // since every test would need to be repeated with the MI and MJ reversed.
1098 static bool cannotCoexistAsymm(const MachineInstr &MI, const MachineInstr &MJ,
1099       const HexagonInstrInfo &HII) {
1100   const MachineFunction *MF = MI.getParent()->getParent();
1101   if (MF->getSubtarget<HexagonSubtarget>().hasV60OpsOnly() &&
1102       HII.isHVXMemWithAIndirect(MI, MJ))
1103     return true;
1104 
1105   // An inline asm cannot be together with a branch, because we may not be
1106   // able to remove the asm out after packetizing (i.e. if the asm must be
1107   // moved past the bundle).  Similarly, two asms cannot be together to avoid
1108   // complications when determining their relative order outside of a bundle.
1109   if (MI.isInlineAsm())
1110     return MJ.isInlineAsm() || MJ.isBranch() || MJ.isBarrier() ||
1111            MJ.isCall() || MJ.isTerminator();
1112 
1113   // New-value stores cannot coexist with any other stores.
1114   if (HII.isNewValueStore(MI) && MJ.mayStore())
1115     return true;
1116 
1117   switch (MI.getOpcode()) {
1118   case Hexagon::S2_storew_locked:
1119   case Hexagon::S4_stored_locked:
1120   case Hexagon::L2_loadw_locked:
1121   case Hexagon::L4_loadd_locked:
1122   case Hexagon::Y2_dccleana:
1123   case Hexagon::Y2_dccleaninva:
1124   case Hexagon::Y2_dcinva:
1125   case Hexagon::Y2_dczeroa:
1126   case Hexagon::Y4_l2fetch:
1127   case Hexagon::Y5_l2fetch: {
1128     // These instructions can only be grouped with ALU32 or non-floating-point
1129     // XTYPE instructions.  Since there is no convenient way of identifying fp
1130     // XTYPE instructions, only allow grouping with ALU32 for now.
1131     unsigned TJ = HII.getType(MJ);
1132     if (TJ != HexagonII::TypeALU32_2op &&
1133         TJ != HexagonII::TypeALU32_3op &&
1134         TJ != HexagonII::TypeALU32_ADDI)
1135       return true;
1136     break;
1137   }
1138   default:
1139     break;
1140   }
1141 
1142   // "False" really means that the quick check failed to determine if
1143   // I and J cannot coexist.
1144   return false;
1145 }
1146 
1147 // Full, symmetric check.
1148 bool HexagonPacketizerList::cannotCoexist(const MachineInstr &MI,
1149       const MachineInstr &MJ) {
1150   return cannotCoexistAsymm(MI, MJ, *HII) || cannotCoexistAsymm(MJ, MI, *HII);
1151 }
1152 
1153 void HexagonPacketizerList::unpacketizeSoloInstrs(MachineFunction &MF) {
1154   for (auto &B : MF) {
1155     MachineBasicBlock::iterator BundleIt;
1156     for (MachineInstr &MI : llvm::make_early_inc_range(B.instrs())) {
1157       if (MI.isBundle())
1158         BundleIt = MI.getIterator();
1159       if (!MI.isInsideBundle())
1160         continue;
1161 
1162       // Decide on where to insert the instruction that we are pulling out.
1163       // Debug instructions always go before the bundle, but the placement of
1164       // INLINE_ASM depends on potential dependencies.  By default, try to
1165       // put it before the bundle, but if the asm writes to a register that
1166       // other instructions in the bundle read, then we need to place it
1167       // after the bundle (to preserve the bundle semantics).
1168       bool InsertBeforeBundle;
1169       if (MI.isInlineAsm())
1170         InsertBeforeBundle = !hasWriteToReadDep(MI, *BundleIt, HRI);
1171       else if (MI.isDebugValue())
1172         InsertBeforeBundle = true;
1173       else
1174         continue;
1175 
1176       BundleIt = moveInstrOut(MI, BundleIt, InsertBeforeBundle);
1177     }
1178   }
1179 }
1180 
1181 // Check if a given instruction is of class "system".
1182 static bool isSystemInstr(const MachineInstr &MI) {
1183   unsigned Opc = MI.getOpcode();
1184   switch (Opc) {
1185     case Hexagon::Y2_barrier:
1186     case Hexagon::Y2_dcfetchbo:
1187     case Hexagon::Y4_l2fetch:
1188     case Hexagon::Y5_l2fetch:
1189       return true;
1190   }
1191   return false;
1192 }
1193 
1194 bool HexagonPacketizerList::hasDeadDependence(const MachineInstr &I,
1195                                               const MachineInstr &J) {
1196   // The dependence graph may not include edges between dead definitions,
1197   // so without extra checks, we could end up packetizing two instruction
1198   // defining the same (dead) register.
1199   if (I.isCall() || J.isCall())
1200     return false;
1201   if (HII->isPredicated(I) || HII->isPredicated(J))
1202     return false;
1203 
1204   BitVector DeadDefs(Hexagon::NUM_TARGET_REGS);
1205   for (auto &MO : I.operands()) {
1206     if (!MO.isReg() || !MO.isDef() || !MO.isDead())
1207       continue;
1208     DeadDefs[MO.getReg()] = true;
1209   }
1210 
1211   for (auto &MO : J.operands()) {
1212     if (!MO.isReg() || !MO.isDef() || !MO.isDead())
1213       continue;
1214     Register R = MO.getReg();
1215     if (R != Hexagon::USR_OVF && DeadDefs[R])
1216       return true;
1217   }
1218   return false;
1219 }
1220 
1221 bool HexagonPacketizerList::hasControlDependence(const MachineInstr &I,
1222                                                  const MachineInstr &J) {
1223   // A save callee-save register function call can only be in a packet
1224   // with instructions that don't write to the callee-save registers.
1225   if ((HII->isSaveCalleeSavedRegsCall(I) &&
1226        doesModifyCalleeSavedReg(J, HRI)) ||
1227       (HII->isSaveCalleeSavedRegsCall(J) &&
1228        doesModifyCalleeSavedReg(I, HRI)))
1229     return true;
1230 
1231   // Two control flow instructions cannot go in the same packet.
1232   if (isControlFlow(I) && isControlFlow(J))
1233     return true;
1234 
1235   // \ref-manual (7.3.4) A loop setup packet in loopN or spNloop0 cannot
1236   // contain a speculative indirect jump,
1237   // a new-value compare jump or a dealloc_return.
1238   auto isBadForLoopN = [this] (const MachineInstr &MI) -> bool {
1239     if (MI.isCall() || HII->isDeallocRet(MI) || HII->isNewValueJump(MI))
1240       return true;
1241     if (HII->isPredicated(MI) && HII->isPredicatedNew(MI) && HII->isJumpR(MI))
1242       return true;
1243     return false;
1244   };
1245 
1246   if (HII->isLoopN(I) && isBadForLoopN(J))
1247     return true;
1248   if (HII->isLoopN(J) && isBadForLoopN(I))
1249     return true;
1250 
1251   // dealloc_return cannot appear in the same packet as a conditional or
1252   // unconditional jump.
1253   return HII->isDeallocRet(I) &&
1254          (J.isBranch() || J.isCall() || J.isBarrier());
1255 }
1256 
1257 bool HexagonPacketizerList::hasRegMaskDependence(const MachineInstr &I,
1258                                                  const MachineInstr &J) {
1259   // Adding I to a packet that has J.
1260 
1261   // Regmasks are not reflected in the scheduling dependency graph, so
1262   // we need to check them manually. This code assumes that regmasks only
1263   // occur on calls, and the problematic case is when we add an instruction
1264   // defining a register R to a packet that has a call that clobbers R via
1265   // a regmask. Those cannot be packetized together, because the call will
1266   // be executed last. That's also a reson why it is ok to add a call
1267   // clobbering R to a packet that defines R.
1268 
1269   // Look for regmasks in J.
1270   for (const MachineOperand &OpJ : J.operands()) {
1271     if (!OpJ.isRegMask())
1272       continue;
1273     assert((J.isCall() || HII->isTailCall(J)) && "Regmask on a non-call");
1274     for (const MachineOperand &OpI : I.operands()) {
1275       if (OpI.isReg()) {
1276         if (OpJ.clobbersPhysReg(OpI.getReg()))
1277           return true;
1278       } else if (OpI.isRegMask()) {
1279         // Both are regmasks. Assume that they intersect.
1280         return true;
1281       }
1282     }
1283   }
1284   return false;
1285 }
1286 
1287 bool HexagonPacketizerList::hasDualStoreDependence(const MachineInstr &I,
1288                                                    const MachineInstr &J) {
1289   bool SysI = isSystemInstr(I), SysJ = isSystemInstr(J);
1290   bool StoreI = I.mayStore(), StoreJ = J.mayStore();
1291   if ((SysI && StoreJ) || (SysJ && StoreI))
1292     return true;
1293 
1294   if (StoreI && StoreJ) {
1295     if (HII->isNewValueInst(J) || HII->isMemOp(J) || HII->isMemOp(I))
1296       return true;
1297   } else {
1298     // A memop cannot be in the same packet with another memop or a store.
1299     // Two stores can be together, but here I and J cannot both be stores.
1300     bool MopStI = HII->isMemOp(I) || StoreI;
1301     bool MopStJ = HII->isMemOp(J) || StoreJ;
1302     if (MopStI && MopStJ)
1303       return true;
1304   }
1305 
1306   return (StoreJ && HII->isDeallocRet(I)) || (StoreI && HII->isDeallocRet(J));
1307 }
1308 
1309 // SUI is the current instruction that is out side of the current packet.
1310 // SUJ is the current instruction inside the current packet against which that
1311 // SUI will be packetized.
1312 bool HexagonPacketizerList::isLegalToPacketizeTogether(SUnit *SUI, SUnit *SUJ) {
1313   assert(SUI->getInstr() && SUJ->getInstr());
1314   MachineInstr &I = *SUI->getInstr();
1315   MachineInstr &J = *SUJ->getInstr();
1316 
1317   // Clear IgnoreDepMIs when Packet starts.
1318   if (CurrentPacketMIs.size() == 1)
1319     IgnoreDepMIs.clear();
1320 
1321   MachineBasicBlock::iterator II = I.getIterator();
1322 
1323   // Solo instructions cannot go in the packet.
1324   assert(!isSoloInstruction(I) && "Unexpected solo instr!");
1325 
1326   if (cannotCoexist(I, J))
1327     return false;
1328 
1329   Dependence = hasDeadDependence(I, J) || hasControlDependence(I, J);
1330   if (Dependence)
1331     return false;
1332 
1333   // Regmasks are not accounted for in the scheduling graph, so we need
1334   // to explicitly check for dependencies caused by them. They should only
1335   // appear on calls, so it's not too pessimistic to reject all regmask
1336   // dependencies.
1337   Dependence = hasRegMaskDependence(I, J);
1338   if (Dependence)
1339     return false;
1340 
1341   // Dual-store does not allow second store, if the first store is not
1342   // in SLOT0. New value store, new value jump, dealloc_return and memop
1343   // always take SLOT0. Arch spec 3.4.4.2.
1344   Dependence = hasDualStoreDependence(I, J);
1345   if (Dependence)
1346     return false;
1347 
1348   // If an instruction feeds new value jump, glue it.
1349   MachineBasicBlock::iterator NextMII = I.getIterator();
1350   ++NextMII;
1351   if (NextMII != I.getParent()->end() && HII->isNewValueJump(*NextMII)) {
1352     MachineInstr &NextMI = *NextMII;
1353 
1354     bool secondRegMatch = false;
1355     const MachineOperand &NOp0 = NextMI.getOperand(0);
1356     const MachineOperand &NOp1 = NextMI.getOperand(1);
1357 
1358     if (NOp1.isReg() && I.getOperand(0).getReg() == NOp1.getReg())
1359       secondRegMatch = true;
1360 
1361     for (MachineInstr *PI : CurrentPacketMIs) {
1362       // NVJ can not be part of the dual jump - Arch Spec: section 7.8.
1363       if (PI->isCall()) {
1364         Dependence = true;
1365         break;
1366       }
1367       // Validate:
1368       // 1. Packet does not have a store in it.
1369       // 2. If the first operand of the nvj is newified, and the second
1370       //    operand is also a reg, it (second reg) is not defined in
1371       //    the same packet.
1372       // 3. If the second operand of the nvj is newified, (which means
1373       //    first operand is also a reg), first reg is not defined in
1374       //    the same packet.
1375       if (PI->getOpcode() == Hexagon::S2_allocframe || PI->mayStore() ||
1376           HII->isLoopN(*PI)) {
1377         Dependence = true;
1378         break;
1379       }
1380       // Check #2/#3.
1381       const MachineOperand &OpR = secondRegMatch ? NOp0 : NOp1;
1382       if (OpR.isReg() && PI->modifiesRegister(OpR.getReg(), HRI)) {
1383         Dependence = true;
1384         break;
1385       }
1386     }
1387 
1388     GlueToNewValueJump = true;
1389     if (Dependence)
1390       return false;
1391   }
1392 
1393   // There no dependency between a prolog instruction and its successor.
1394   if (!SUJ->isSucc(SUI))
1395     return true;
1396 
1397   for (unsigned i = 0; i < SUJ->Succs.size(); ++i) {
1398     if (FoundSequentialDependence)
1399       break;
1400 
1401     if (SUJ->Succs[i].getSUnit() != SUI)
1402       continue;
1403 
1404     SDep::Kind DepType = SUJ->Succs[i].getKind();
1405     // For direct calls:
1406     // Ignore register dependences for call instructions for packetization
1407     // purposes except for those due to r31 and predicate registers.
1408     //
1409     // For indirect calls:
1410     // Same as direct calls + check for true dependences to the register
1411     // used in the indirect call.
1412     //
1413     // We completely ignore Order dependences for call instructions.
1414     //
1415     // For returns:
1416     // Ignore register dependences for return instructions like jumpr,
1417     // dealloc return unless we have dependencies on the explicit uses
1418     // of the registers used by jumpr (like r31) or dealloc return
1419     // (like r29 or r30).
1420     unsigned DepReg = 0;
1421     const TargetRegisterClass *RC = nullptr;
1422     if (DepType == SDep::Data) {
1423       DepReg = SUJ->Succs[i].getReg();
1424       RC = HRI->getMinimalPhysRegClass(DepReg);
1425     }
1426 
1427     if (I.isCall() || HII->isJumpR(I) || I.isReturn() || HII->isTailCall(I)) {
1428       if (!isRegDependence(DepType))
1429         continue;
1430       if (!isCallDependent(I, DepType, SUJ->Succs[i].getReg()))
1431         continue;
1432     }
1433 
1434     if (DepType == SDep::Data) {
1435       if (canPromoteToDotCur(J, SUJ, DepReg, II, RC))
1436         if (promoteToDotCur(J, DepType, II, RC))
1437           continue;
1438     }
1439 
1440     // Data dpendence ok if we have load.cur.
1441     if (DepType == SDep::Data && HII->isDotCurInst(J)) {
1442       if (HII->isHVXVec(I))
1443         continue;
1444     }
1445 
1446     // For instructions that can be promoted to dot-new, try to promote.
1447     if (DepType == SDep::Data) {
1448       if (canPromoteToDotNew(I, SUJ, DepReg, II, RC)) {
1449         if (promoteToDotNew(I, DepType, II, RC)) {
1450           PromotedToDotNew = true;
1451           if (cannotCoexist(I, J))
1452             FoundSequentialDependence = true;
1453           continue;
1454         }
1455       }
1456       if (HII->isNewValueJump(I))
1457         continue;
1458     }
1459 
1460     // For predicated instructions, if the predicates are complements then
1461     // there can be no dependence.
1462     if (HII->isPredicated(I) && HII->isPredicated(J) &&
1463         arePredicatesComplements(I, J)) {
1464       // Not always safe to do this translation.
1465       // DAG Builder attempts to reduce dependence edges using transitive
1466       // nature of dependencies. Here is an example:
1467       //
1468       // r0 = tfr_pt ... (1)
1469       // r0 = tfr_pf ... (2)
1470       // r0 = tfr_pt ... (3)
1471       //
1472       // There will be an output dependence between (1)->(2) and (2)->(3).
1473       // However, there is no dependence edge between (1)->(3). This results
1474       // in all 3 instructions going in the same packet. We ignore dependce
1475       // only once to avoid this situation.
1476       auto Itr = find(IgnoreDepMIs, &J);
1477       if (Itr != IgnoreDepMIs.end()) {
1478         Dependence = true;
1479         return false;
1480       }
1481       IgnoreDepMIs.push_back(&I);
1482       continue;
1483     }
1484 
1485     // Ignore Order dependences between unconditional direct branches
1486     // and non-control-flow instructions.
1487     if (isDirectJump(I) && !J.isBranch() && !J.isCall() &&
1488         DepType == SDep::Order)
1489       continue;
1490 
1491     // Ignore all dependences for jumps except for true and output
1492     // dependences.
1493     if (I.isConditionalBranch() && DepType != SDep::Data &&
1494         DepType != SDep::Output)
1495       continue;
1496 
1497     if (DepType == SDep::Output) {
1498       FoundSequentialDependence = true;
1499       break;
1500     }
1501 
1502     // For Order dependences:
1503     // 1. Volatile loads/stores can be packetized together, unless other
1504     //    rules prevent is.
1505     // 2. Store followed by a load is not allowed.
1506     // 3. Store followed by a store is valid.
1507     // 4. Load followed by any memory operation is allowed.
1508     if (DepType == SDep::Order) {
1509       if (!PacketizeVolatiles) {
1510         bool OrdRefs = I.hasOrderedMemoryRef() || J.hasOrderedMemoryRef();
1511         if (OrdRefs) {
1512           FoundSequentialDependence = true;
1513           break;
1514         }
1515       }
1516       // J is first, I is second.
1517       bool LoadJ = J.mayLoad(), StoreJ = J.mayStore();
1518       bool LoadI = I.mayLoad(), StoreI = I.mayStore();
1519       bool NVStoreJ = HII->isNewValueStore(J);
1520       bool NVStoreI = HII->isNewValueStore(I);
1521       bool IsVecJ = HII->isHVXVec(J);
1522       bool IsVecI = HII->isHVXVec(I);
1523 
1524       if (Slot1Store && MF.getSubtarget<HexagonSubtarget>().hasV65Ops() &&
1525           ((LoadJ && StoreI && !NVStoreI) ||
1526            (StoreJ && LoadI && !NVStoreJ)) &&
1527           (J.getOpcode() != Hexagon::S2_allocframe &&
1528            I.getOpcode() != Hexagon::S2_allocframe) &&
1529           (J.getOpcode() != Hexagon::L2_deallocframe &&
1530            I.getOpcode() != Hexagon::L2_deallocframe) &&
1531           (!HII->isMemOp(J) && !HII->isMemOp(I)) && (!IsVecJ && !IsVecI))
1532         setmemShufDisabled(true);
1533       else
1534         if (StoreJ && LoadI && alias(J, I)) {
1535           FoundSequentialDependence = true;
1536           break;
1537         }
1538 
1539       if (!StoreJ)
1540         if (!LoadJ || (!LoadI && !StoreI)) {
1541           // If J is neither load nor store, assume a dependency.
1542           // If J is a load, but I is neither, also assume a dependency.
1543           FoundSequentialDependence = true;
1544           break;
1545         }
1546       // Store followed by store: not OK on V2.
1547       // Store followed by load: not OK on all.
1548       // Load followed by store: OK on all.
1549       // Load followed by load: OK on all.
1550       continue;
1551     }
1552 
1553     // Special case for ALLOCFRAME: even though there is dependency
1554     // between ALLOCFRAME and subsequent store, allow it to be packetized
1555     // in a same packet. This implies that the store is using the caller's
1556     // SP. Hence, offset needs to be updated accordingly.
1557     if (DepType == SDep::Data && J.getOpcode() == Hexagon::S2_allocframe) {
1558       unsigned Opc = I.getOpcode();
1559       switch (Opc) {
1560         case Hexagon::S2_storerd_io:
1561         case Hexagon::S2_storeri_io:
1562         case Hexagon::S2_storerh_io:
1563         case Hexagon::S2_storerb_io:
1564           if (I.getOperand(0).getReg() == HRI->getStackRegister()) {
1565             // Since this store is to be glued with allocframe in the same
1566             // packet, it will use SP of the previous stack frame, i.e.
1567             // caller's SP. Therefore, we need to recalculate offset
1568             // according to this change.
1569             GlueAllocframeStore = useCallersSP(I);
1570             if (GlueAllocframeStore)
1571               continue;
1572           }
1573           break;
1574         default:
1575           break;
1576       }
1577     }
1578 
1579     // There are certain anti-dependencies that cannot be ignored.
1580     // Specifically:
1581     //   J2_call ... implicit-def %r0   ; SUJ
1582     //   R0 = ...                   ; SUI
1583     // Those cannot be packetized together, since the call will observe
1584     // the effect of the assignment to R0.
1585     if ((DepType == SDep::Anti || DepType == SDep::Output) && J.isCall()) {
1586       // Check if I defines any volatile register. We should also check
1587       // registers that the call may read, but these happen to be a
1588       // subset of the volatile register set.
1589       for (const MachineOperand &Op : I.operands()) {
1590         if (Op.isReg() && Op.isDef()) {
1591           Register R = Op.getReg();
1592           if (!J.readsRegister(R, HRI) && !J.modifiesRegister(R, HRI))
1593             continue;
1594         } else if (!Op.isRegMask()) {
1595           // If I has a regmask assume dependency.
1596           continue;
1597         }
1598         FoundSequentialDependence = true;
1599         break;
1600       }
1601     }
1602 
1603     // Skip over remaining anti-dependences. Two instructions that are
1604     // anti-dependent can share a packet, since in most such cases all
1605     // operands are read before any modifications take place.
1606     // The exceptions are branch and call instructions, since they are
1607     // executed after all other instructions have completed (at least
1608     // conceptually).
1609     if (DepType != SDep::Anti) {
1610       FoundSequentialDependence = true;
1611       break;
1612     }
1613   }
1614 
1615   if (FoundSequentialDependence) {
1616     Dependence = true;
1617     return false;
1618   }
1619 
1620   return true;
1621 }
1622 
1623 bool HexagonPacketizerList::isLegalToPruneDependencies(SUnit *SUI, SUnit *SUJ) {
1624   assert(SUI->getInstr() && SUJ->getInstr());
1625   MachineInstr &I = *SUI->getInstr();
1626   MachineInstr &J = *SUJ->getInstr();
1627 
1628   bool Coexist = !cannotCoexist(I, J);
1629 
1630   if (Coexist && !Dependence)
1631     return true;
1632 
1633   // Check if the instruction was promoted to a dot-new. If so, demote it
1634   // back into a dot-old.
1635   if (PromotedToDotNew)
1636     demoteToDotOld(I);
1637 
1638   cleanUpDotCur();
1639   // Check if the instruction (must be a store) was glued with an allocframe
1640   // instruction. If so, restore its offset to its original value, i.e. use
1641   // current SP instead of caller's SP.
1642   if (GlueAllocframeStore) {
1643     useCalleesSP(I);
1644     GlueAllocframeStore = false;
1645   }
1646 
1647   if (ChangedOffset != INT64_MAX)
1648     undoChangedOffset(I);
1649 
1650   if (GlueToNewValueJump) {
1651     // Putting I and J together would prevent the new-value jump from being
1652     // packetized with the producer. In that case I and J must be separated.
1653     GlueToNewValueJump = false;
1654     return false;
1655   }
1656 
1657   if (!Coexist)
1658     return false;
1659 
1660   if (ChangedOffset == INT64_MAX && updateOffset(SUI, SUJ)) {
1661     FoundSequentialDependence = false;
1662     Dependence = false;
1663     return true;
1664   }
1665 
1666   return false;
1667 }
1668 
1669 
1670 bool HexagonPacketizerList::foundLSInPacket() {
1671   bool FoundLoad = false;
1672   bool FoundStore = false;
1673 
1674   for (auto MJ : CurrentPacketMIs) {
1675     unsigned Opc = MJ->getOpcode();
1676     if (Opc == Hexagon::S2_allocframe || Opc == Hexagon::L2_deallocframe)
1677       continue;
1678     if (HII->isMemOp(*MJ))
1679       continue;
1680     if (MJ->mayLoad())
1681       FoundLoad = true;
1682     if (MJ->mayStore() && !HII->isNewValueStore(*MJ))
1683       FoundStore = true;
1684   }
1685   return FoundLoad && FoundStore;
1686 }
1687 
1688 
1689 MachineBasicBlock::iterator
1690 HexagonPacketizerList::addToPacket(MachineInstr &MI) {
1691   MachineBasicBlock::iterator MII = MI.getIterator();
1692   MachineBasicBlock *MBB = MI.getParent();
1693 
1694   if (CurrentPacketMIs.empty())
1695     PacketStalls = false;
1696   PacketStalls |= producesStall(MI);
1697 
1698   if (MI.isImplicitDef()) {
1699     // Add to the packet to allow subsequent instructions to be checked
1700     // properly.
1701     CurrentPacketMIs.push_back(&MI);
1702     return MII;
1703   }
1704   assert(ResourceTracker->canReserveResources(MI));
1705 
1706   bool ExtMI = HII->isExtended(MI) || HII->isConstExtended(MI);
1707   bool Good = true;
1708 
1709   if (GlueToNewValueJump) {
1710     MachineInstr &NvjMI = *++MII;
1711     // We need to put both instructions in the same packet: MI and NvjMI.
1712     // Either of them can require a constant extender. Try to add both to
1713     // the current packet, and if that fails, end the packet and start a
1714     // new one.
1715     ResourceTracker->reserveResources(MI);
1716     if (ExtMI)
1717       Good = tryAllocateResourcesForConstExt(true);
1718 
1719     bool ExtNvjMI = HII->isExtended(NvjMI) || HII->isConstExtended(NvjMI);
1720     if (Good) {
1721       if (ResourceTracker->canReserveResources(NvjMI))
1722         ResourceTracker->reserveResources(NvjMI);
1723       else
1724         Good = false;
1725     }
1726     if (Good && ExtNvjMI)
1727       Good = tryAllocateResourcesForConstExt(true);
1728 
1729     if (!Good) {
1730       endPacket(MBB, MI);
1731       assert(ResourceTracker->canReserveResources(MI));
1732       ResourceTracker->reserveResources(MI);
1733       if (ExtMI) {
1734         assert(canReserveResourcesForConstExt());
1735         tryAllocateResourcesForConstExt(true);
1736       }
1737       assert(ResourceTracker->canReserveResources(NvjMI));
1738       ResourceTracker->reserveResources(NvjMI);
1739       if (ExtNvjMI) {
1740         assert(canReserveResourcesForConstExt());
1741         reserveResourcesForConstExt();
1742       }
1743     }
1744     CurrentPacketMIs.push_back(&MI);
1745     CurrentPacketMIs.push_back(&NvjMI);
1746     return MII;
1747   }
1748 
1749   ResourceTracker->reserveResources(MI);
1750   if (ExtMI && !tryAllocateResourcesForConstExt(true)) {
1751     endPacket(MBB, MI);
1752     if (PromotedToDotNew)
1753       demoteToDotOld(MI);
1754     if (GlueAllocframeStore) {
1755       useCalleesSP(MI);
1756       GlueAllocframeStore = false;
1757     }
1758     ResourceTracker->reserveResources(MI);
1759     reserveResourcesForConstExt();
1760   }
1761 
1762   CurrentPacketMIs.push_back(&MI);
1763   return MII;
1764 }
1765 
1766 void HexagonPacketizerList::endPacket(MachineBasicBlock *MBB,
1767                                       MachineBasicBlock::iterator EndMI) {
1768   // Replace VLIWPacketizerList::endPacket(MBB, EndMI).
1769   LLVM_DEBUG({
1770     if (!CurrentPacketMIs.empty()) {
1771       dbgs() << "Finalizing packet:\n";
1772       unsigned Idx = 0;
1773       for (MachineInstr *MI : CurrentPacketMIs) {
1774         unsigned R = ResourceTracker->getUsedResources(Idx++);
1775         dbgs() << " * [res:0x" << utohexstr(R) << "] " << *MI;
1776       }
1777     }
1778   });
1779 
1780   bool memShufDisabled = getmemShufDisabled();
1781   if (memShufDisabled && !foundLSInPacket()) {
1782     setmemShufDisabled(false);
1783     LLVM_DEBUG(dbgs() << "  Not added to NoShufPacket\n");
1784   }
1785   memShufDisabled = getmemShufDisabled();
1786 
1787   OldPacketMIs.clear();
1788   for (MachineInstr *MI : CurrentPacketMIs) {
1789     MachineBasicBlock::instr_iterator NextMI = std::next(MI->getIterator());
1790     for (auto &I : make_range(HII->expandVGatherPseudo(*MI), NextMI))
1791       OldPacketMIs.push_back(&I);
1792   }
1793   CurrentPacketMIs.clear();
1794 
1795   if (OldPacketMIs.size() > 1) {
1796     MachineBasicBlock::instr_iterator FirstMI(OldPacketMIs.front());
1797     MachineBasicBlock::instr_iterator LastMI(EndMI.getInstrIterator());
1798     finalizeBundle(*MBB, FirstMI, LastMI);
1799     auto BundleMII = std::prev(FirstMI);
1800     if (memShufDisabled)
1801       HII->setBundleNoShuf(BundleMII);
1802 
1803     setmemShufDisabled(false);
1804   }
1805 
1806   PacketHasDuplex = false;
1807   PacketHasSLOT0OnlyInsn = false;
1808   ResourceTracker->clearResources();
1809   LLVM_DEBUG(dbgs() << "End packet\n");
1810 }
1811 
1812 bool HexagonPacketizerList::shouldAddToPacket(const MachineInstr &MI) {
1813   if (Minimal)
1814     return false;
1815 
1816   // Constrainst for not packetizing this MI with existing instructions in a
1817   // packet.
1818   //	MI is a store instruction.
1819   //	CurrentPacketMIs has a SLOT0 only instruction with constraint
1820   //    A_RESTRICT_NOSLOT1_STORE/isRestrictNoSlot1Store.
1821   if (MI.mayStore() && isPureSlot0InsnWithNoSlot1Store(MI))
1822     return false;
1823 
1824   if (producesStall(MI))
1825     return false;
1826 
1827   // If TinyCore with Duplexes is enabled, check if this MI can form a Duplex
1828   // with any other instruction in the existing packet.
1829   auto &HST = MI.getParent()->getParent()->getSubtarget<HexagonSubtarget>();
1830   // Constraint 1: Only one duplex allowed per packet.
1831   // Constraint 2: Consider duplex checks only if there is atleast one
1832   // instruction in a packet.
1833   // Constraint 3: If one of the existing instructions in the packet has a
1834   // SLOT0 only instruction that can not be duplexed, do not attempt to form
1835   // duplexes. (TODO: This will invalidate the L4_return* instructions to form a
1836   // duplex)
1837   if (HST.isTinyCoreWithDuplex() && CurrentPacketMIs.size() > 0 &&
1838       !PacketHasDuplex) {
1839     // Check for SLOT0 only non-duplexable instruction in packet.
1840     for (auto &MJ : CurrentPacketMIs)
1841       PacketHasSLOT0OnlyInsn |= HII->isPureSlot0(*MJ);
1842     // Get the Big Core Opcode (dup_*).
1843     int Opcode = HII->getDuplexOpcode(MI, false);
1844     if (Opcode >= 0) {
1845       // We now have an instruction that can be duplexed.
1846       for (auto &MJ : CurrentPacketMIs) {
1847         if (HII->isDuplexPair(MI, *MJ) && !PacketHasSLOT0OnlyInsn) {
1848           PacketHasDuplex = true;
1849           return true;
1850         }
1851       }
1852       // If it can not be duplexed, check if there is a valid transition in DFA
1853       // with the original opcode.
1854       MachineInstr &MIRef = const_cast<MachineInstr &>(MI);
1855       MIRef.setDesc(HII->get(Opcode));
1856       return ResourceTracker->canReserveResources(MIRef);
1857     }
1858   }
1859 
1860   return true;
1861 }
1862 
1863 bool HexagonPacketizerList::isPureSlot0InsnWithNoSlot1Store(
1864     const MachineInstr &MI) {
1865   bool noSlot1Store = false;
1866   bool isSlot0Only = false;
1867   for (auto J : CurrentPacketMIs) {
1868     noSlot1Store |= HII->isRestrictNoSlot1Store(*J);
1869     isSlot0Only |= HII->isPureSlot0(*J);
1870   }
1871 
1872   return (noSlot1Store && isSlot0Only);
1873 }
1874 
1875 // V60 forward scheduling.
1876 bool HexagonPacketizerList::producesStall(const MachineInstr &I) {
1877   // If the packet already stalls, then ignore the stall from a subsequent
1878   // instruction in the same packet.
1879   if (PacketStalls)
1880     return false;
1881 
1882   // Check whether the previous packet is in a different loop. If this is the
1883   // case, there is little point in trying to avoid a stall because that would
1884   // favor the rare case (loop entry) over the common case (loop iteration).
1885   //
1886   // TODO: We should really be able to check all the incoming edges if this is
1887   // the first packet in a basic block, so we can avoid stalls from the loop
1888   // backedge.
1889   if (!OldPacketMIs.empty()) {
1890     auto *OldBB = OldPacketMIs.front()->getParent();
1891     auto *ThisBB = I.getParent();
1892     if (MLI->getLoopFor(OldBB) != MLI->getLoopFor(ThisBB))
1893       return false;
1894   }
1895 
1896   SUnit *SUI = MIToSUnit[const_cast<MachineInstr *>(&I)];
1897 
1898   // If the latency is 0 and there is a data dependence between this
1899   // instruction and any instruction in the current packet, we disregard any
1900   // potential stalls due to the instructions in the previous packet. Most of
1901   // the instruction pairs that can go together in the same packet have 0
1902   // latency between them. The exceptions are
1903   // 1. NewValueJumps as they're generated much later and the latencies can't
1904   // be changed at that point.
1905   // 2. .cur instructions, if its consumer has a 0 latency successor (such as
1906   // .new). In this case, the latency between .cur and the consumer stays
1907   // non-zero even though we can have  both .cur and .new in the same packet.
1908   // Changing the latency to 0 is not an option as it causes software pipeliner
1909   // to not pipeline in some cases.
1910 
1911   // For Example:
1912   // {
1913   //   I1:  v6.cur = vmem(r0++#1)
1914   //   I2:  v7 = valign(v6,v4,r2)
1915   //   I3:  vmem(r5++#1) = v7.new
1916   // }
1917   // Here I2 and I3 has 0 cycle latency, but I1 and I2 has 2.
1918 
1919   for (auto J : CurrentPacketMIs) {
1920     SUnit *SUJ = MIToSUnit[J];
1921     for (auto &Pred : SUI->Preds)
1922       if (Pred.getSUnit() == SUJ)
1923         if ((Pred.getLatency() == 0 && Pred.isAssignedRegDep()) ||
1924             HII->isNewValueJump(I) || HII->isToBeScheduledASAP(*J, I))
1925           return false;
1926   }
1927 
1928   // Check if the latency is greater than one between this instruction and any
1929   // instruction in the previous packet.
1930   for (auto J : OldPacketMIs) {
1931     SUnit *SUJ = MIToSUnit[J];
1932     for (auto &Pred : SUI->Preds)
1933       if (Pred.getSUnit() == SUJ && Pred.getLatency() > 1)
1934         return true;
1935   }
1936 
1937   return false;
1938 }
1939 
1940 //===----------------------------------------------------------------------===//
1941 //                         Public Constructor Functions
1942 //===----------------------------------------------------------------------===//
1943 
1944 FunctionPass *llvm::createHexagonPacketizer(bool Minimal) {
1945   return new HexagonPacketizer(Minimal);
1946 }
1947