llvm/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 #include "MCTargetDesc/HexagonShuffler.h"
  15 #include "MCTargetDesc/HexagonBaseInfo.h"
  16 #include "MCTargetDesc/HexagonMCInstrInfo.h"
  17 #include "MCTargetDesc/HexagonMCTargetDesc.h"
  18 #include "llvm/ADT/SmallVector.h"
  19 #include "llvm/ADT/Twine.h"
  20 #include "llvm/MC/MCContext.h"
  21 #include "llvm/MC/MCInst.h"
  22 #include "llvm/MC/MCInstrDesc.h"
  23 #include "llvm/MC/MCSubtargetInfo.h"
  24 #include "llvm/Support/Compiler.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/Support/MathExtras.h"
  27 #include "llvm/Support/SourceMgr.h"
  28 #include "llvm/Support/raw_ostream.h"
  29 #include <algorithm>
  30 #include <cassert>
  31 #include <utility>
  32 #include <vector>
  33
  34 #define DEBUG_TYPE "hexagon-shuffle"
  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 HexagonCVIResource::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
 135 struct CVIUnits {
 136   unsigned Units;
 137   unsigned Lanes;
 138 };
 139 using HVXInstsT = SmallVector<struct CVIUnits, 8>;
 140
 141 static 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
 148 static 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
 167 HexagonShuffler::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
 174 void HexagonShuffler::reset() {
 175   Packet.clear();
 176   BundleFlags = 0;
 177   CheckFailure = false;
 178 }
 179
 180 void 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
 188 static const unsigned Slot0Mask = 1 << 0;
 189 static const unsigned Slot1Mask = 1 << 1;
 190 static const unsigned Slot3Mask = 1 << 3;
 191 static const unsigned slotSingleLoad = Slot0Mask;
 192 static const unsigned slotSingleStore = Slot0Mask;
 193
 194 void 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
 217 void 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
 247 bool 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
 269 void 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
 310 void 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
 318 bool 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   llvm::stable_sort(*this, 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
 355 bool 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
 441 HexagonShuffler::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
 555 bool 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
 568 void 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.
 593 bool 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
 608 llvm::Optional<HexagonShuffler::HexagonPacket>
 609 HexagonShuffler::tryAuction(HexagonPacketSummary const &Summary) const {
 610   HexagonPacket PacketResult = Packet;
 611   HexagonUnitAuction AuctionCore(Summary.ReservedSlotMask);
 612   llvm::stable_sort(PacketResult, HexagonInstr::lessCore);
 613
 614   const bool ValidSlots =
 615       llvm::all_of(insts(PacketResult), [&AuctionCore](HexagonInstr const &I) {
 616         return AuctionCore.bid(I.Core.getUnits());
 617       });
 618
 619   LLVM_DEBUG(
 620     dbgs() << "Shuffle attempt: " << (ValidSlots ? "passed" : "failed")
 621            << "\n";
 622     for (HexagonInstr const &ISJ : insts(PacketResult))
 623       dbgs() << "\t" << HexagonMCInstrInfo::getName(MCII, *ISJ.ID) << ": "
 624              << llvm::format_hex(ISJ.Core.getUnits(), 4, true) << "\n";
 625   );
 626
 627   Optional<HexagonPacket> Res;
 628   if (ValidSlots)
 629     Res = PacketResult;
 630
 631   return Res;
 632 }
 633
 634 bool HexagonShuffler::shuffle() {
 635   if (size() > HEXAGON_PACKET_SIZE) {
 636     // Ignore a packet with with more than what a packet can hold
 637     // or with compound or duplex insns for now.
 638     reportError(Twine("invalid instruction packet"));
 639     return false;
 640   }
 641
 642   // Check and prepare packet.
 643   bool Ok = true;
 644   if (size() > 1 && (Ok = check()))
 645     // Reorder the handles for each slot.
 646     for (unsigned nSlot = 0, emptySlots = 0; nSlot < HEXAGON_PACKET_SIZE;
 647          ++nSlot) {
 648       iterator ISJ, ISK;
 649       unsigned slotSkip, slotWeight;
 650
 651       // Prioritize the handles considering their restrictions.
 652       for (ISJ = ISK = Packet.begin(), slotSkip = slotWeight = 0;
 653            ISK != Packet.end(); ++ISK, ++slotSkip)
 654         if (slotSkip < nSlot - emptySlots)
 655           // Note which handle to begin at.
 656           ++ISJ;
 657         else
 658           // Calculate the weight of the slot.
 659           slotWeight += ISK->Core.setWeight(HEXAGON_PACKET_SIZE - nSlot - 1);
 660
 661       if (slotWeight)
 662         // Sort the packet, favoring source order,
 663         // beginning after the previous slot.
 664         std::stable_sort(ISJ, Packet.end());
 665       else
 666         // Skip unused slot.
 667         ++emptySlots;
 668     }
 669
 670   LLVM_DEBUG(
 671     for (HexagonInstr const &ISJ : insts()) {
 672       dbgs().write_hex(ISJ.Core.getUnits());
 673       if (ISJ.CVI.isValid()) {
 674         dbgs() << '/';
 675         dbgs().write_hex(ISJ.CVI.getUnits()) << '|';
 676         dbgs() << ISJ.CVI.getLanes();
 677       }
 678       dbgs() << ':'
 679              << HexagonMCInstrInfo::getDesc(MCII, ISJ.getDesc()).getOpcode()
 680              << '\n';
 681     } dbgs() << '\n';
 682   );
 683
 684   return Ok;
 685 }
 686
 687 void HexagonShuffler::reportError(Twine const &Msg) {
 688   CheckFailure = true;
 689   if (ReportErrors) {
 690     for (auto const &I : AppliedRestrictions) {
 691       auto SM = Context.getSourceManager();
 692       if (SM)
 693         SM->PrintMessage(I.first, SourceMgr::DK_Note, I.second);
 694     }
 695     Context.reportError(Loc, Msg);
 696   }
 697 }