1 //===- HexagonShuffler.cpp - Instruction bundle shuffling -----------------===//
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 the shuffling of insns inside a bundle according to the
10 // packet formation rules of the Hexagon ISA.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "MCTargetDesc/HexagonShuffler.h"
15 #include "MCTargetDesc/HexagonBaseInfo.h"
16 #include "MCTargetDesc/HexagonMCInstrInfo.h"
17 #include "MCTargetDesc/HexagonMCTargetDesc.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/ADT/Twine.h"
20 #include "llvm/MC/MCContext.h"
21 #include "llvm/MC/MCInst.h"
22 #include "llvm/MC/MCInstrDesc.h"
23 #include "llvm/MC/MCSubtargetInfo.h"
24 #include "llvm/Support/Compiler.h"
25 #include "llvm/Support/Debug.h"
26 #include "llvm/Support/MathExtras.h"
27 #include "llvm/Support/SourceMgr.h"
28 #include "llvm/Support/raw_ostream.h"
29 #include <algorithm>
30 #include <cassert>
31 #include <optional>
32 #include <utility>
33 #include <vector>
34 
35 #define DEBUG_TYPE "hexagon-shuffle"
36 
37 using namespace llvm;
38 
39 namespace {
40 
41 // Insn shuffling priority.
42 class HexagonBid {
43   // The priority is directly proportional to how restricted the insn is based
44   // on its flexibility to run on the available slots.  So, the fewer slots it
45   // may run on, the higher its priority.
46   enum { MAX = 360360 }; // LCD of 1/2, 1/3, 1/4,... 1/15.
47   unsigned Bid = 0;
48 
49 public:
50   HexagonBid() = default;
HexagonBid(unsigned B)51   HexagonBid(unsigned B) { Bid = B ? MAX / llvm::popcount(B) : 0; }
52 
53   // Check if the insn priority is overflowed.
isSold() const54   bool isSold() const { return (Bid >= MAX); }
55 
operator +=(const HexagonBid & B)56   HexagonBid &operator+=(const HexagonBid &B) {
57     Bid += B.Bid;
58     return *this;
59   }
60 };
61 
62 // Slot shuffling allocation.
63 class HexagonUnitAuction {
64   HexagonBid Scores[HEXAGON_PACKET_SIZE];
65   // Mask indicating which slot is unavailable.
66   unsigned isSold : HEXAGON_PACKET_SIZE;
67 
68 public:
HexagonUnitAuction(unsigned cs=0)69   HexagonUnitAuction(unsigned cs = 0) : isSold(cs) {}
70 
71   // Allocate slots.
bid(unsigned B)72   bool bid(unsigned B) {
73     // Exclude already auctioned slots from the bid.
74     unsigned b = B & ~isSold;
75     if (b) {
76       for (unsigned i = 0; i < HEXAGON_PACKET_SIZE; ++i)
77         if (b & (1 << i)) {
78           // Request candidate slots.
79           Scores[i] += HexagonBid(b);
80           isSold |= Scores[i].isSold() << i;
81         }
82       return true;
83     } else
84       // Error if the desired slots are already full.
85       return false;
86   }
87 };
88 
89 } // end anonymous namespace
90 
setWeight(unsigned s)91 unsigned HexagonResource::setWeight(unsigned s) {
92   const unsigned SlotWeight = 8;
93   const unsigned MaskWeight = SlotWeight - 1;
94   unsigned Units = getUnits();
95   unsigned Key = ((1u << s) & Units) != 0;
96 
97   // Calculate relative weight of the insn for the given slot, weighing it the
98   // heavier the more restrictive the insn is and the lowest the slots that the
99   // insn may be executed in.
100   if (Key == 0 || Units == 0 || (SlotWeight * s >= 32))
101     return Weight = 0;
102 
103   unsigned Ctpop = llvm::popcount(Units);
104   unsigned Cttz = countTrailingZeros(Units);
105   Weight = (1u << (SlotWeight * s)) * ((MaskWeight - Ctpop) << Cttz);
106   return Weight;
107 }
108 
HexagonCVIResource(MCInstrInfo const & MCII,MCSubtargetInfo const & STI,unsigned s,MCInst const * id)109 HexagonCVIResource::HexagonCVIResource(MCInstrInfo const &MCII,
110                                        MCSubtargetInfo const &STI,
111                                        unsigned s,
112                                        MCInst const *id)
113     : HexagonResource(s) {
114 
115   const unsigned ItinUnits = HexagonMCInstrInfo::getCVIResources(MCII, STI, *id);
116   unsigned Lanes;
117   const unsigned Units = HexagonConvertUnits(ItinUnits, &Lanes);
118 
119   if (Units == 0 && Lanes == 0) {
120     // For core insns.
121     Valid = false;
122     setUnits(0);
123     setLanes(0);
124     setLoad(false);
125     setStore(false);
126   } else {
127     // For an HVX insn.
128     Valid = true;
129     setUnits(Units);
130     setLanes(Lanes);
131     setLoad(HexagonMCInstrInfo::getDesc(MCII, *id).mayLoad());
132     setStore(HexagonMCInstrInfo::getDesc(MCII, *id).mayStore());
133   }
134 }
135 
136 struct CVIUnits {
137   unsigned Units;
138   unsigned Lanes;
139 };
140 using HVXInstsT = SmallVector<struct CVIUnits, 8>;
141 
makeAllBits(unsigned startBit,unsigned Lanes)142 static unsigned makeAllBits(unsigned startBit, unsigned Lanes)
143 {
144   for (unsigned i = 1; i < Lanes; ++i)
145     startBit = (startBit << 1) | startBit;
146   return startBit;
147 }
148 
checkHVXPipes(const HVXInstsT & hvxInsts,unsigned startIdx,unsigned usedUnits)149 static bool checkHVXPipes(const HVXInstsT &hvxInsts, unsigned startIdx,
150                           unsigned usedUnits) {
151   if (startIdx < hvxInsts.size()) {
152     if (!hvxInsts[startIdx].Units)
153       return checkHVXPipes(hvxInsts, startIdx + 1, usedUnits);
154     for (unsigned b = 0x1; b <= 0x8; b <<= 1) {
155       if ((hvxInsts[startIdx].Units & b) == 0)
156         continue;
157       unsigned allBits = makeAllBits(b, hvxInsts[startIdx].Lanes);
158       if ((allBits & usedUnits) == 0) {
159         if (checkHVXPipes(hvxInsts, startIdx + 1, usedUnits | allBits))
160           return true;
161       }
162     }
163     return false;
164   }
165   return true;
166 }
167 
HexagonShuffler(MCContext & Context,bool ReportErrors,MCInstrInfo const & MCII,MCSubtargetInfo const & STI)168 HexagonShuffler::HexagonShuffler(MCContext &Context, bool ReportErrors,
169                                  MCInstrInfo const &MCII,
170                                  MCSubtargetInfo const &STI)
171     : Context(Context), BundleFlags(), MCII(MCII), STI(STI),
172       ReportErrors(ReportErrors), CheckFailure() {
173   reset();
174 }
175 
reset()176 void HexagonShuffler::reset() {
177   Packet.clear();
178   BundleFlags = 0;
179   CheckFailure = false;
180 }
181 
append(MCInst const & ID,MCInst const * Extender,unsigned S)182 void HexagonShuffler::append(MCInst const &ID, MCInst const *Extender,
183                              unsigned S) {
184   HexagonInstr PI(MCII, STI, &ID, Extender, S);
185 
186   Packet.push_back(PI);
187 }
188 
189 
190 static const unsigned Slot0Mask = 1 << 0;
191 static const unsigned Slot1Mask = 1 << 1;
192 static const unsigned Slot3Mask = 1 << 3;
193 static const unsigned slotSingleLoad = Slot0Mask;
194 static const unsigned slotSingleStore = Slot0Mask;
195 
restrictSlot1AOK(HexagonPacketSummary const & Summary)196 void HexagonShuffler::restrictSlot1AOK(HexagonPacketSummary const &Summary) {
197   if (Summary.Slot1AOKLoc)
198     for (HexagonInstr &ISJ : insts()) {
199       MCInst const &Inst = ISJ.getDesc();
200       const unsigned Type = HexagonMCInstrInfo::getType(MCII, Inst);
201       if (Type != HexagonII::TypeALU32_2op &&
202           Type != HexagonII::TypeALU32_3op &&
203           Type != HexagonII::TypeALU32_ADDI) {
204         const unsigned Units = ISJ.Core.getUnits();
205 
206         if (Units & Slot1Mask) {
207           AppliedRestrictions.push_back(std::make_pair(
208               Inst.getLoc(),
209               "Instruction was restricted from being in slot 1"));
210           AppliedRestrictions.push_back(std::make_pair(
211               *Summary.Slot1AOKLoc, "Instruction can only be combined "
212                                     "with an ALU instruction in slot 1"));
213           ISJ.Core.setUnits(Units & ~Slot1Mask);
214         }
215       }
216     }
217 }
218 
restrictNoSlot1Store(HexagonPacketSummary const & Summary)219 void HexagonShuffler::restrictNoSlot1Store(
220     HexagonPacketSummary const &Summary) {
221   // If this packet contains an instruction that bars slot-1 stores,
222   // we should mask off slot 1 from all of the store instructions in
223   // this packet.
224 
225   if (!Summary.NoSlot1StoreLoc)
226     return;
227 
228   bool AppliedRestriction = false;
229 
230   for (HexagonInstr &ISJ : insts()) {
231     MCInst const &Inst = ISJ.getDesc();
232     if (HexagonMCInstrInfo::getDesc(MCII, Inst).mayStore()) {
233       unsigned Units = ISJ.Core.getUnits();
234       if (Units & Slot1Mask) {
235         AppliedRestriction = true;
236         AppliedRestrictions.push_back(std::make_pair(
237             Inst.getLoc(), "Instruction was restricted from being in slot 1"));
238         ISJ.Core.setUnits(Units & ~Slot1Mask);
239       }
240     }
241   }
242 
243   if (AppliedRestriction)
244     AppliedRestrictions.push_back(
245         std::make_pair(*Summary.NoSlot1StoreLoc,
246                        "Instruction does not allow a store in slot 1"));
247 }
248 
applySlotRestrictions(HexagonPacketSummary const & Summary,const bool DoShuffle)249 bool HexagonShuffler::applySlotRestrictions(HexagonPacketSummary const &Summary,
250                                             const bool DoShuffle) {
251   // These restrictions can modify the slot masks in the instructions
252   // in the Packet member.  They should run unconditionally and their
253   // order does not matter.
254   restrictSlot1AOK(Summary);
255   restrictNoSlot1Store(Summary);
256 
257   permitNonSlot();
258 
259   // These restrictions can modify the slot masks in the instructions
260   // in the Packet member, but they can also detect constraint failures
261   // which are fatal.
262   if (!CheckFailure)
263     restrictStoreLoadOrder(Summary);
264   if (!CheckFailure)
265     restrictBranchOrder(Summary);
266   if (!CheckFailure)
267     restrictPreferSlot3(Summary, DoShuffle);
268   return !CheckFailure;
269 }
270 
restrictBranchOrder(HexagonPacketSummary const & Summary)271 void HexagonShuffler::restrictBranchOrder(HexagonPacketSummary const &Summary) {
272   // preserve branch order
273   const bool HasMultipleBranches = Summary.branchInsts.size() > 1;
274   if (!HasMultipleBranches)
275     return;
276 
277   if (Summary.branchInsts.size() > 2) {
278     reportError(Twine("too many branches in packet"));
279     return;
280   }
281 
282   const static std::pair<unsigned, unsigned> jumpSlots[] = {
283       {8, 4}, {8, 2}, {8, 1}, {4, 2}, {4, 1}, {2, 1}};
284   // try all possible choices
285   for (std::pair<unsigned, unsigned> jumpSlot : jumpSlots) {
286     // validate first jump with this slot rule
287     if (!(jumpSlot.first & Summary.branchInsts[0]->Core.getUnits()))
288       continue;
289 
290     // validate second jump with this slot rule
291     if (!(jumpSlot.second & Summary.branchInsts[1]->Core.getUnits()))
292       continue;
293 
294     // both valid for this configuration, set new slot rules
295     const HexagonPacket PacketSave = Packet;
296     Summary.branchInsts[0]->Core.setUnits(jumpSlot.first);
297     Summary.branchInsts[1]->Core.setUnits(jumpSlot.second);
298 
299     const bool HasShuffledPacket = tryAuction(Summary).has_value();
300     if (HasShuffledPacket)
301       return;
302 
303     // if yes, great, if not then restore original slot mask
304     // restore original values
305     Packet = PacketSave;
306   }
307 
308   reportResourceError(Summary, "out of slots");
309 }
310 
permitNonSlot()311 void HexagonShuffler::permitNonSlot() {
312   for (HexagonInstr &ISJ : insts()) {
313     const bool RequiresSlot = HexagonMCInstrInfo::requiresSlot(STI, *ISJ.ID);
314     if (!RequiresSlot)
315       ISJ.Core.setAllUnits();
316   }
317 }
318 
ValidResourceUsage(HexagonPacketSummary const & Summary)319 bool HexagonShuffler::ValidResourceUsage(HexagonPacketSummary const &Summary) {
320   std::optional<HexagonPacket> ShuffledPacket = tryAuction(Summary);
321 
322   if (!ShuffledPacket) {
323     reportResourceError(Summary, "slot error");
324     return false;
325   }
326 
327   // Verify the CVI slot subscriptions.
328   llvm::stable_sort(*ShuffledPacket, HexagonInstr::lessCVI);
329   // create vector of hvx instructions to check
330   HVXInstsT hvxInsts;
331   hvxInsts.clear();
332   for (const auto &I : *ShuffledPacket) {
333     struct CVIUnits inst;
334     inst.Units = I.CVI.getUnits();
335     inst.Lanes = I.CVI.getLanes();
336     if (inst.Units == 0)
337       continue; // not an hvx inst or an hvx inst that doesn't uses any pipes
338     hvxInsts.push_back(inst);
339   }
340 
341   // if there are any hvx instructions in this packet, check pipe usage
342   if (hvxInsts.size() > 0) {
343     unsigned startIdx, usedUnits;
344     startIdx = usedUnits = 0x0;
345     if (!checkHVXPipes(hvxInsts, startIdx, usedUnits)) {
346       // too many pipes used to be valid
347       reportError(Twine("invalid instruction packet: slot error"));
348       return false;
349     }
350   }
351 
352   Packet = *ShuffledPacket;
353 
354   return true;
355 }
356 
restrictStoreLoadOrder(HexagonPacketSummary const & Summary)357 bool HexagonShuffler::restrictStoreLoadOrder(
358     HexagonPacketSummary const &Summary) {
359   // Modify packet accordingly.
360   // TODO: need to reserve slots #0 and #1 for duplex insns.
361   static const unsigned slotFirstLoadStore = Slot1Mask;
362   static const unsigned slotLastLoadStore = Slot0Mask;
363   unsigned slotLoadStore = slotFirstLoadStore;
364 
365   for (iterator ISJ = begin(); ISJ != end(); ++ISJ) {
366     MCInst const &ID = ISJ->getDesc();
367 
368     if (!ISJ->Core.getUnits())
369       // Error if insn may not be executed in any slot.
370       return false;
371 
372     // A single load must use slot #0.
373     if (HexagonMCInstrInfo::getDesc(MCII, ID).mayLoad()) {
374       if (Summary.loads == 1 && Summary.loads == Summary.memory &&
375           Summary.memops == 0)
376         // Pin the load to slot #0.
377         switch (ID.getOpcode()) {
378         case Hexagon::V6_vgathermw:
379         case Hexagon::V6_vgathermh:
380         case Hexagon::V6_vgathermhw:
381         case Hexagon::V6_vgathermwq:
382         case Hexagon::V6_vgathermhq:
383         case Hexagon::V6_vgathermhwq:
384           // Slot1 only loads
385           break;
386         default:
387           ISJ->Core.setUnits(ISJ->Core.getUnits() & slotSingleLoad);
388           break;
389         }
390       else if (Summary.loads >= 1 && isMemReorderDisabled()) { // }:mem_noshuf
391         // Loads must keep the original order ONLY if
392         // isMemReorderDisabled() == true
393         if (slotLoadStore < slotLastLoadStore) {
394           // Error if no more slots available for loads.
395           reportError("invalid instruction packet: too many loads");
396           return false;
397         }
398         // Pin the load to the highest slot available to it.
399         ISJ->Core.setUnits(ISJ->Core.getUnits() & slotLoadStore);
400         // Update the next highest slot available to loads.
401         slotLoadStore >>= 1;
402       }
403     }
404 
405     // A single store must use slot #0.
406     if (HexagonMCInstrInfo::getDesc(MCII, ID).mayStore()) {
407       if (!Summary.store0) {
408         const bool PacketHasNoOnlySlot0 =
409             llvm::none_of(insts(), [&](HexagonInstr const &I) {
410               return I.Core.getUnits() == Slot0Mask &&
411                      I.ID->getOpcode() != ID.getOpcode();
412             });
413         const bool SafeToMoveToSlot0 =
414             (Summary.loads == 0) ||
415             (!isMemReorderDisabled() && PacketHasNoOnlySlot0);
416 
417         if (Summary.stores == 1 && SafeToMoveToSlot0)
418           // Pin the store to slot #0 only if isMemReorderDisabled() == false
419           ISJ->Core.setUnits(ISJ->Core.getUnits() & slotSingleStore);
420         else if (Summary.stores >= 1) {
421           if (slotLoadStore < slotLastLoadStore) {
422             // Error if no more slots available for stores.
423             reportError("invalid instruction packet: too many stores");
424             return false;
425           }
426           // Pin the store to the highest slot available to it.
427           ISJ->Core.setUnits(ISJ->Core.getUnits() & slotLoadStore);
428           // Update the next highest slot available to stores.
429           slotLoadStore >>= 1;
430         }
431       }
432       if (Summary.store1 && Summary.stores > 1) {
433         // Error if a single store with another store.
434         reportError("invalid instruction packet: too many stores");
435         return false;
436       }
437     }
438   }
439 
440   return true;
441 }
442 
SlotMaskToText(unsigned SlotMask)443 static std::string SlotMaskToText(unsigned SlotMask) {
444     SmallVector<std::string, HEXAGON_PRESHUFFLE_PACKET_SIZE> Slots;
445     for (unsigned SlotNum = 0; SlotNum < HEXAGON_PACKET_SIZE; SlotNum++)
446         if ((SlotMask & (1 << SlotNum)) != 0)
447             Slots.push_back(utostr(SlotNum));
448 
449     return llvm::join(Slots, StringRef(", "));
450 }
451 
GetPacketSummary()452 HexagonShuffler::HexagonPacketSummary HexagonShuffler::GetPacketSummary() {
453   HexagonPacketSummary Summary = HexagonPacketSummary();
454 
455   // Collect information from the insns in the packet.
456   for (iterator ISJ = begin(); ISJ != end(); ++ISJ) {
457     MCInst const &ID = ISJ->getDesc();
458 
459     if (HexagonMCInstrInfo::isRestrictSlot1AOK(MCII, ID))
460       Summary.Slot1AOKLoc = ID.getLoc();
461     if (HexagonMCInstrInfo::isRestrictNoSlot1Store(MCII, ID))
462       Summary.NoSlot1StoreLoc = ID.getLoc();
463 
464     if (HexagonMCInstrInfo::prefersSlot3(MCII, ID)) {
465       ++Summary.pSlot3Cnt;
466       Summary.PrefSlot3Inst = ISJ;
467     }
468     const unsigned ReservedSlots =
469         HexagonMCInstrInfo::getOtherReservedSlots(MCII, STI, ID);
470     Summary.ReservedSlotMask |= ReservedSlots;
471     if (ReservedSlots != 0)
472       AppliedRestrictions.push_back(std::make_pair(ID.getLoc(),
473                   (Twine("Instruction has reserved slots: ") +
474                    SlotMaskToText(ReservedSlots)).str()));
475 
476     switch (HexagonMCInstrInfo::getType(MCII, ID)) {
477     case HexagonII::TypeS_2op:
478     case HexagonII::TypeS_3op:
479     case HexagonII::TypeALU64:
480       break;
481     case HexagonII::TypeJ:
482       if (HexagonMCInstrInfo::IsABranchingInst(MCII, STI, *ISJ->ID))
483         Summary.branchInsts.push_back(ISJ);
484       break;
485     case HexagonII::TypeCVI_VM_VP_LDU:
486     case HexagonII::TypeCVI_VM_LD:
487     case HexagonII::TypeCVI_VM_TMP_LD:
488     case HexagonII::TypeCVI_GATHER:
489     case HexagonII::TypeCVI_GATHER_DV:
490     case HexagonII::TypeCVI_GATHER_RST:
491       ++Summary.NonZCVIloads;
492       [[fallthrough]];
493     case HexagonII::TypeCVI_ZW:
494       ++Summary.AllCVIloads;
495       [[fallthrough]];
496     case HexagonII::TypeLD:
497       ++Summary.loads;
498       ++Summary.memory;
499       if (ISJ->Core.getUnits() == slotSingleLoad ||
500           HexagonMCInstrInfo::getType(MCII, ID) == HexagonII::TypeCVI_VM_VP_LDU)
501         ++Summary.load0;
502       if (HexagonMCInstrInfo::getDesc(MCII, ID).isReturn())
503         Summary.branchInsts.push_back(ISJ);
504       break;
505     case HexagonII::TypeCVI_VM_STU:
506     case HexagonII::TypeCVI_VM_ST:
507     case HexagonII::TypeCVI_VM_NEW_ST:
508     case HexagonII::TypeCVI_SCATTER:
509     case HexagonII::TypeCVI_SCATTER_DV:
510     case HexagonII::TypeCVI_SCATTER_RST:
511     case HexagonII::TypeCVI_SCATTER_NEW_RST:
512     case HexagonII::TypeCVI_SCATTER_NEW_ST:
513       ++Summary.CVIstores;
514       [[fallthrough]];
515     case HexagonII::TypeST:
516       ++Summary.stores;
517       ++Summary.memory;
518       if (ISJ->Core.getUnits() == slotSingleStore ||
519           HexagonMCInstrInfo::getType(MCII, ID) == HexagonII::TypeCVI_VM_STU)
520         ++Summary.store0;
521       break;
522     case HexagonII::TypeV4LDST:
523       ++Summary.loads;
524       ++Summary.stores;
525       ++Summary.store1;
526       ++Summary.memops;
527       ++Summary.memory;
528       break;
529     case HexagonII::TypeNCJ:
530       ++Summary.memory; // NV insns are memory-like.
531       Summary.branchInsts.push_back(ISJ);
532       break;
533     case HexagonII::TypeV2LDST:
534       if (HexagonMCInstrInfo::getDesc(MCII, ID).mayLoad()) {
535         ++Summary.loads;
536         ++Summary.memory;
537         if (ISJ->Core.getUnits() == slotSingleLoad ||
538             HexagonMCInstrInfo::getType(MCII, ID) ==
539                 HexagonII::TypeCVI_VM_VP_LDU)
540           ++Summary.load0;
541       } else {
542         assert(HexagonMCInstrInfo::getDesc(MCII, ID).mayStore());
543         ++Summary.memory;
544         ++Summary.stores;
545       }
546       break;
547     case HexagonII::TypeCR:
548     // Legacy conditional branch predicated on a register.
549     case HexagonII::TypeCJ:
550       if (HexagonMCInstrInfo::getDesc(MCII, ID).isBranch())
551         Summary.branchInsts.push_back(ISJ);
552       break;
553     case HexagonII::TypeDUPLEX: {
554       ++Summary.duplex;
555       MCInst const &Inst0 = *ID.getOperand(0).getInst();
556       MCInst const &Inst1 = *ID.getOperand(1).getInst();
557       if (HexagonMCInstrInfo::getDesc(MCII, Inst0).isBranch())
558         Summary.branchInsts.push_back(ISJ);
559       if (HexagonMCInstrInfo::getDesc(MCII, Inst1).isBranch())
560         Summary.branchInsts.push_back(ISJ);
561       if (HexagonMCInstrInfo::getDesc(MCII, Inst0).isReturn())
562         Summary.branchInsts.push_back(ISJ);
563       if (HexagonMCInstrInfo::getDesc(MCII, Inst1).isReturn())
564         Summary.branchInsts.push_back(ISJ);
565       break;
566     }
567     }
568   }
569   return Summary;
570 }
571 
ValidPacketMemoryOps(HexagonPacketSummary const & Summary) const572 bool HexagonShuffler::ValidPacketMemoryOps(
573     HexagonPacketSummary const &Summary) const {
574   // Check if the packet is legal.
575   const unsigned ZCVIloads = Summary.AllCVIloads - Summary.NonZCVIloads;
576   const bool ValidHVXMem =
577       Summary.NonZCVIloads <= 1 && ZCVIloads <= 1 && Summary.CVIstores <= 1;
578   const bool InvalidPacket =
579       ((Summary.load0 > 1 || Summary.store0 > 1 || !ValidHVXMem) ||
580        (Summary.duplex > 1 || (Summary.duplex && Summary.memory)));
581 
582   return !InvalidPacket;
583 }
584 
restrictPreferSlot3(HexagonPacketSummary const & Summary,const bool DoShuffle)585 void HexagonShuffler::restrictPreferSlot3(HexagonPacketSummary const &Summary,
586                                           const bool DoShuffle) {
587   // flag if an instruction requires to be in slot 3
588   const bool HasOnlySlot3 = llvm::any_of(insts(), [&](HexagonInstr const &I) {
589     return (I.Core.getUnits() == Slot3Mask);
590   });
591   const bool NeedsPrefSlot3Shuffle = Summary.branchInsts.size() <= 1 &&
592                                      !HasOnlySlot3 && Summary.pSlot3Cnt == 1 &&
593                                      Summary.PrefSlot3Inst && DoShuffle;
594 
595   if (!NeedsPrefSlot3Shuffle)
596     return;
597 
598   HexagonInstr *PrefSlot3Inst = *Summary.PrefSlot3Inst;
599   // save off slot mask of instruction marked with A_PREFER_SLOT3
600   // and then pin it to slot #3
601   const unsigned saveUnits = PrefSlot3Inst->Core.getUnits();
602   PrefSlot3Inst->Core.setUnits(saveUnits & Slot3Mask);
603   const bool HasShuffledPacket = tryAuction(Summary).has_value();
604   if (HasShuffledPacket)
605     return;
606 
607   PrefSlot3Inst->Core.setUnits(saveUnits);
608 }
609 
610 /// Check that the packet is legal and enforce relative insn order.
check(const bool RequireShuffle)611 bool HexagonShuffler::check(const bool RequireShuffle) {
612   const HexagonPacketSummary Summary = GetPacketSummary();
613   if (!applySlotRestrictions(Summary, RequireShuffle))
614     return false;
615 
616   if (!ValidPacketMemoryOps(Summary)) {
617     reportError("invalid instruction packet");
618     return false;
619   }
620 
621   if (RequireShuffle)
622     ValidResourceUsage(Summary);
623 
624   return !CheckFailure;
625 }
626 
627 std::optional<HexagonShuffler::HexagonPacket>
tryAuction(HexagonPacketSummary const & Summary)628 HexagonShuffler::tryAuction(HexagonPacketSummary const &Summary) {
629   HexagonPacket PacketResult = Packet;
630   HexagonUnitAuction AuctionCore(Summary.ReservedSlotMask);
631   llvm::stable_sort(PacketResult, HexagonInstr::lessCore);
632 
633   const bool ValidSlots =
634       llvm::all_of(insts(PacketResult), [&AuctionCore](HexagonInstr const &I) {
635         return AuctionCore.bid(I.Core.getUnits());
636       });
637 
638   LLVM_DEBUG(
639     dbgs() << "Shuffle attempt: " << (ValidSlots ? "passed" : "failed")
640            << "\n";
641     for (HexagonInstr const &ISJ : insts(PacketResult))
642       dbgs() << "\t" << HexagonMCInstrInfo::getName(MCII, *ISJ.ID) << ": "
643              << llvm::format_hex(ISJ.Core.getUnits(), 4, true) << "\n";
644   );
645 
646   std::optional<HexagonPacket> Res;
647   if (ValidSlots)
648     Res = PacketResult;
649 
650   return Res;
651 }
652 
shuffle()653 bool HexagonShuffler::shuffle() {
654   if (size() > HEXAGON_PACKET_SIZE) {
655     // Ignore a packet with with more than what a packet can hold
656     // or with compound or duplex insns for now.
657     reportError("invalid instruction packet");
658     return false;
659   }
660 
661   // Check and prepare packet.
662   bool Ok = check();
663   if (size() > 1 && Ok)
664     // Reorder the handles for each slot.
665     for (unsigned nSlot = 0, emptySlots = 0; nSlot < HEXAGON_PACKET_SIZE;
666          ++nSlot) {
667       iterator ISJ, ISK;
668       unsigned slotSkip, slotWeight;
669 
670       // Prioritize the handles considering their restrictions.
671       for (ISJ = ISK = Packet.begin(), slotSkip = slotWeight = 0;
672            ISK != Packet.end(); ++ISK, ++slotSkip)
673         if (slotSkip < nSlot - emptySlots)
674           // Note which handle to begin at.
675           ++ISJ;
676         else
677           // Calculate the weight of the slot.
678           slotWeight += ISK->Core.setWeight(HEXAGON_PACKET_SIZE - nSlot - 1);
679 
680       if (slotWeight)
681         // Sort the packet, favoring source order,
682         // beginning after the previous slot.
683         std::stable_sort(ISJ, Packet.end());
684       else
685         // Skip unused slot.
686         ++emptySlots;
687     }
688 
689   LLVM_DEBUG(
690     for (HexagonInstr const &ISJ : insts()) {
691       dbgs().write_hex(ISJ.Core.getUnits());
692       if (ISJ.CVI.isValid()) {
693         dbgs() << '/';
694         dbgs().write_hex(ISJ.CVI.getUnits()) << '|';
695         dbgs() << ISJ.CVI.getLanes();
696       }
697       dbgs() << ':'
698              << HexagonMCInstrInfo::getDesc(MCII, ISJ.getDesc()).getOpcode()
699              << '\n';
700     } dbgs() << '\n';
701   );
702 
703   return Ok;
704 }
705 
reportResourceError(HexagonPacketSummary const & Summary,StringRef Err)706 void HexagonShuffler::reportResourceError(HexagonPacketSummary const &Summary, StringRef Err) {
707   if (ReportErrors)
708     reportResourceUsage(Summary);
709   reportError(Twine("invalid instruction packet: ") + Err);
710 }
711 
712 
reportResourceUsage(HexagonPacketSummary const & Summary)713 void HexagonShuffler::reportResourceUsage(HexagonPacketSummary const &Summary) {
714   auto SM = Context.getSourceManager();
715   if (SM) {
716     for (HexagonInstr const &I : insts()) {
717       const unsigned Units = I.Core.getUnits();
718 
719       if (HexagonMCInstrInfo::requiresSlot(STI, *I.ID)) {
720         const std::string UnitsText = Units ? SlotMaskToText(Units) : "<None>";
721         SM->PrintMessage(I.ID->getLoc(), SourceMgr::DK_Note,
722                 Twine("Instruction can utilize slots: ") +
723                 UnitsText);
724       }
725       else if (!HexagonMCInstrInfo::isImmext(*I.ID))
726         SM->PrintMessage(I.ID->getLoc(), SourceMgr::DK_Note,
727                        "Instruction does not require a slot");
728     }
729   }
730 }
731 
reportError(Twine const & Msg)732 void HexagonShuffler::reportError(Twine const &Msg) {
733   CheckFailure = true;
734   if (ReportErrors) {
735     for (auto const &I : AppliedRestrictions) {
736       auto SM = Context.getSourceManager();
737       if (SM)
738         SM->PrintMessage(I.first, SourceMgr::DK_Note, I.second);
739     }
740     Context.reportError(Loc, Msg);
741   }
742 }
743