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