lib/Target/Hexagon/MCTargetDesc/HexagonShuffler.cpp

   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 }