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
108void 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
144HexagonCVIResource::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
167struct CVIUnits {
168  unsigned Units;
169  unsigned Lanes;
170};
171using HVXInstsT = SmallVector<struct CVIUnits, 8>;
172
173static 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
180static 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
199HexagonShuffler::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
207void HexagonShuffler::reset() {
208  Packet.clear();
209  BundleFlags = 0;
210}
211
212void 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
219static 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
225void 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
256void 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
287void HexagonShuffler::applySlotRestrictions() {
288  restrictSlot1AOK();
289  restrictNoSlot1Store();
290}
291
292/// Check that the packet is legal and enforce relative insn order.
293bool 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
620bool 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
669void 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