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