contrib/llvm/lib/Target/Hexagon/MCTargetDesc/HexagonShuffler.cpp

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