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 <algorithm>
  18 #include <utility>
  19 #include "Hexagon.h"
  20 #include "MCTargetDesc/HexagonBaseInfo.h"
  21 #include "MCTargetDesc/HexagonMCTargetDesc.h"
  22 #include "MCTargetDesc/HexagonMCInstrInfo.h"
  23 #include "HexagonShuffler.h"
  24 #include "llvm/Support/Debug.h"
  25 #include "llvm/Support/MathExtras.h"
  26 #include "llvm/Support/raw_ostream.h"
  27
  28 using namespace llvm;
  29
  30 namespace {
  31 // Insn shuffling priority.
  32 class HexagonBid {
  33   // The priority is directly proportional to how restricted the insn is based
  34   // on its flexibility to run on the available slots.  So, the fewer slots it
  35   // may run on, the higher its priority.
  36   enum { MAX = 360360 }; // LCD of 1/2, 1/3, 1/4,... 1/15.
  37   unsigned Bid;
  38
  39 public:
  40   HexagonBid() : Bid(0){};
  41   HexagonBid(unsigned B) { Bid = B ? MAX / countPopulation(B) : 0; };
  42
  43   // Check if the insn priority is overflowed.
  44   bool isSold() const { return (Bid >= MAX); };
  45
  46   HexagonBid &operator+=(const HexagonBid &B) {
  47     Bid += B.Bid;
  48     return *this;
  49   };
  50 };
  51
  52 // Slot shuffling allocation.
  53 class HexagonUnitAuction {
  54   HexagonBid Scores[HEXAGON_PACKET_SIZE];
  55   // Mask indicating which slot is unavailable.
  56   unsigned isSold : HEXAGON_PACKET_SIZE;
  57
  58 public:
  59   HexagonUnitAuction() : isSold(0){};
  60
  61   // Allocate slots.
  62   bool bid(unsigned B) {
  63     // Exclude already auctioned slots from the bid.
  64     unsigned b = B & ~isSold;
  65     if (b) {
  66       for (unsigned i = 0; i < HEXAGON_PACKET_SIZE; ++i)
  67         if (b & (1 << i)) {
  68           // Request candidate slots.
  69           Scores[i] += HexagonBid(b);
  70           isSold |= Scores[i].isSold() << i;
  71         }
  72       return true;
  73       ;
  74     } else
  75       // Error if the desired slots are already full.
  76       return false;
  77   };
  78 };
  79 } // end anonymous namespace
  80
  81 unsigned HexagonResource::setWeight(unsigned s) {
  82   const unsigned SlotWeight = 8;
  83   const unsigned MaskWeight = SlotWeight - 1;
  84   bool Key = (1 << s) & getUnits();
  85
  86   // TODO: Improve this API so that we can prevent misuse statically.
  87   assert(SlotWeight * s < 32 && "Argument to setWeight too large.");
  88
  89   // Calculate relative weight of the insn for the given slot, weighing it the
  90   // heavier the more restrictive the insn is and the lowest the slots that the
  91   // insn may be executed in.
  92   Weight =
  93       (Key << (SlotWeight * s)) * ((MaskWeight - countPopulation(getUnits()))
  94                                    << countTrailingZeros(getUnits()));
  95   return (Weight);
  96 }
  97
  98 HexagonCVIResource::TypeUnitsAndLanes *HexagonCVIResource::TUL;
  99
 100 bool HexagonCVIResource::SetUp = HexagonCVIResource::setup();
 101
 102 bool HexagonCVIResource::setup() {
 103   assert(!TUL);
 104   TUL = new (TypeUnitsAndLanes);
 105
 106   (*TUL)[HexagonII::TypeCVI_VA] =
 107       UnitsAndLanes(CVI_XLANE | CVI_SHIFT | CVI_MPY0 | CVI_MPY1, 1);
 108   (*TUL)[HexagonII::TypeCVI_VA_DV] = UnitsAndLanes(CVI_XLANE | CVI_MPY0, 2);
 109   (*TUL)[HexagonII::TypeCVI_VX] = UnitsAndLanes(CVI_MPY0 | CVI_MPY1, 1);
 110   (*TUL)[HexagonII::TypeCVI_VX_DV] = UnitsAndLanes(CVI_MPY0, 2);
 111   (*TUL)[HexagonII::TypeCVI_VP] = UnitsAndLanes(CVI_XLANE, 1);
 112   (*TUL)[HexagonII::TypeCVI_VP_VS] = UnitsAndLanes(CVI_XLANE, 2);
 113   (*TUL)[HexagonII::TypeCVI_VS] = UnitsAndLanes(CVI_SHIFT, 1);
 114   (*TUL)[HexagonII::TypeCVI_VINLANESAT] = UnitsAndLanes(CVI_SHIFT, 1);
 115   (*TUL)[HexagonII::TypeCVI_VM_LD] =
 116       UnitsAndLanes(CVI_XLANE | CVI_SHIFT | CVI_MPY0 | CVI_MPY1, 1);
 117   (*TUL)[HexagonII::TypeCVI_VM_TMP_LD] = UnitsAndLanes(CVI_NONE, 0);
 118   (*TUL)[HexagonII::TypeCVI_VM_CUR_LD] =
 119       UnitsAndLanes(CVI_XLANE | CVI_SHIFT | CVI_MPY0 | CVI_MPY1, 1);
 120   (*TUL)[HexagonII::TypeCVI_VM_VP_LDU] = UnitsAndLanes(CVI_XLANE, 1);
 121   (*TUL)[HexagonII::TypeCVI_VM_ST] =
 122       UnitsAndLanes(CVI_XLANE | CVI_SHIFT | CVI_MPY0 | CVI_MPY1, 1);
 123   (*TUL)[HexagonII::TypeCVI_VM_NEW_ST] = UnitsAndLanes(CVI_NONE, 0);
 124   (*TUL)[HexagonII::TypeCVI_VM_STU] = UnitsAndLanes(CVI_XLANE, 1);
 125   (*TUL)[HexagonII::TypeCVI_HIST] = UnitsAndLanes(CVI_XLANE, 4);
 126
 127   return true;
 128 }
 129
 130 HexagonCVIResource::HexagonCVIResource(MCInstrInfo const &MCII, unsigned s,
 131                                        MCInst const *id)
 132     : HexagonResource(s) {
 133   unsigned T = HexagonMCInstrInfo::getType(MCII, *id);
 134
 135   if (TUL->count(T)) {
 136     // For an HVX insn.
 137     Valid = true;
 138     setUnits((*TUL)[T].first);
 139     setLanes((*TUL)[T].second);
 140     setLoad(HexagonMCInstrInfo::getDesc(MCII, *id).mayLoad());
 141     setStore(HexagonMCInstrInfo::getDesc(MCII, *id).mayStore());
 142   } else {
 143     // For core insns.
 144     Valid = false;
 145     setUnits(0);
 146     setLanes(0);
 147     setLoad(false);
 148     setStore(false);
 149   }
 150 }
 151
 152 HexagonShuffler::HexagonShuffler(MCInstrInfo const &MCII,
 153                                  MCSubtargetInfo const &STI)
 154     : MCII(MCII), STI(STI) {
 155   reset();
 156 }
 157
 158 void HexagonShuffler::reset() {
 159   Packet.clear();
 160   BundleFlags = 0;
 161   Error = SHUFFLE_SUCCESS;
 162 }
 163
 164 void HexagonShuffler::append(MCInst const *ID, MCInst const *Extender,
 165                              unsigned S, bool X) {
 166   HexagonInstr PI(MCII, ID, Extender, S, X);
 167
 168   Packet.push_back(PI);
 169 }
 170
 171 /// Check that the packet is legal and enforce relative insn order.
 172 bool HexagonShuffler::check() {
 173   // Descriptive slot masks.
 174   const unsigned slotSingleLoad = 0x1, slotSingleStore = 0x1, slotOne = 0x2,
 175                  slotThree = 0x8, slotFirstJump = 0x8, slotLastJump = 0x4,
 176                  slotFirstLoadStore = 0x2, slotLastLoadStore = 0x1;
 177   // Highest slots for branches and stores used to keep their original order.
 178   unsigned slotJump = slotFirstJump;
 179   unsigned slotLoadStore = slotFirstLoadStore;
 180   // Number of branches, solo branches, indirect branches.
 181   unsigned jumps = 0, jump1 = 0, jumpr = 0;
 182   // Number of memory operations, loads, solo loads, stores, solo stores, single
 183   // stores.
 184   unsigned memory = 0, loads = 0, load0 = 0, stores = 0, store0 = 0, store1 = 0;
 185   // Number of HVX loads, HVX stores.
 186   unsigned CVIloads = 0, CVIstores = 0;
 187   // Number of duplex insns, solo insns.
 188   unsigned duplex = 0, solo = 0;
 189   // Number of insns restricting other insns in the packet to A and X types,
 190   // which is neither A or X types.
 191   unsigned onlyAX = 0, neitherAnorX = 0;
 192   // Number of insns restricting other insns in slot #1 to A type.
 193   unsigned onlyAin1 = 0;
 194   // Number of insns restricting any insn in slot #1, except A2_nop.
 195   unsigned onlyNo1 = 0;
 196   unsigned xtypeFloat = 0;
 197   unsigned pSlot3Cnt = 0;
 198   iterator slot3ISJ = end();
 199
 200   // Collect information from the insns in the packet.
 201   for (iterator ISJ = begin(); ISJ != end(); ++ISJ) {
 202     MCInst const *ID = ISJ->getDesc();
 203
 204     if (HexagonMCInstrInfo::isSolo(MCII, *ID))
 205       solo += !ISJ->isSoloException();
 206     else if (HexagonMCInstrInfo::isSoloAX(MCII, *ID))
 207       onlyAX += !ISJ->isSoloException();
 208     else if (HexagonMCInstrInfo::isSoloAin1(MCII, *ID))
 209       onlyAin1 += !ISJ->isSoloException();
 210     if (HexagonMCInstrInfo::getType(MCII, *ID) != HexagonII::TypeALU32 &&
 211         HexagonMCInstrInfo::getType(MCII, *ID) != HexagonII::TypeXTYPE)
 212       ++neitherAnorX;
 213     if (HexagonMCInstrInfo::prefersSlot3(MCII, *ID)) {
 214       ++pSlot3Cnt;
 215       slot3ISJ = ISJ;
 216     }
 217
 218     switch (HexagonMCInstrInfo::getType(MCII, *ID)) {
 219     case HexagonII::TypeXTYPE:
 220       if (HexagonMCInstrInfo::isFloat(MCII, *ID))
 221         ++xtypeFloat;
 222       break;
 223     case HexagonII::TypeJR:
 224       ++jumpr;
 225     // Fall-through.
 226     case HexagonII::TypeJ:
 227       ++jumps;
 228       break;
 229     case HexagonII::TypeCVI_VM_VP_LDU:
 230       ++onlyNo1;
 231     case HexagonII::TypeCVI_VM_LD:
 232     case HexagonII::TypeCVI_VM_TMP_LD:
 233     case HexagonII::TypeCVI_VM_CUR_LD:
 234       ++CVIloads;
 235     case HexagonII::TypeLD:
 236       ++loads;
 237       ++memory;
 238       if (ISJ->Core.getUnits() == slotSingleLoad)
 239         ++load0;
 240       if (HexagonMCInstrInfo::getDesc(MCII, *ID).isReturn())
 241         ++jumps, ++jump1; // DEALLOC_RETURN is of type LD.
 242       break;
 243     case HexagonII::TypeCVI_VM_STU:
 244       ++onlyNo1;
 245     case HexagonII::TypeCVI_VM_ST:
 246     case HexagonII::TypeCVI_VM_NEW_ST:
 247       ++CVIstores;
 248     case HexagonII::TypeST:
 249       ++stores;
 250       ++memory;
 251       if (ISJ->Core.getUnits() == slotSingleStore)
 252         ++store0;
 253       break;
 254     case HexagonII::TypeMEMOP:
 255       ++loads;
 256       ++stores;
 257       ++store1;
 258       ++memory;
 259       break;
 260     case HexagonII::TypeNV:
 261       ++memory; // NV insns are memory-like.
 262       if (HexagonMCInstrInfo::getDesc(MCII, *ID).isBranch())
 263         ++jumps, ++jump1;
 264       break;
 265     case HexagonII::TypeCR:
 266     // Legacy conditional branch predicated on a register.
 267     case HexagonII::TypeSYSTEM:
 268       if (HexagonMCInstrInfo::getDesc(MCII, *ID).mayLoad())
 269         ++loads;
 270       break;
 271     }
 272   }
 273
 274   // Check if the packet is legal.
 275   if ((load0 > 1 || store0 > 1 || CVIloads > 1 || CVIstores > 1) ||
 276       (duplex > 1 || (duplex && memory)) || (solo && size() > 1) ||
 277       (onlyAX && neitherAnorX > 1) || (onlyAX && xtypeFloat)) {
 278     Error = SHUFFLE_ERROR_INVALID;
 279     return false;
 280   }
 281
 282   if (jump1 && jumps > 1) {
 283     // Error if single branch with another branch.
 284     Error = SHUFFLE_ERROR_BRANCHES;
 285     return false;
 286   }
 287
 288   // Modify packet accordingly.
 289   // TODO: need to reserve slots #0 and #1 for duplex insns.
 290   bool bOnlySlot3 = false;
 291   for (iterator ISJ = begin(); ISJ != end(); ++ISJ) {
 292     MCInst const *ID = ISJ->getDesc();
 293
 294     if (!ISJ->Core.getUnits()) {
 295       // Error if insn may not be executed in any slot.
 296       Error = SHUFFLE_ERROR_UNKNOWN;
 297       return false;
 298     }
 299
 300     // Exclude from slot #1 any insn but A2_nop.
 301     if (HexagonMCInstrInfo::getDesc(MCII, *ID).getOpcode() != Hexagon::A2_nop)
 302       if (onlyNo1)
 303         ISJ->Core.setUnits(ISJ->Core.getUnits() & ~slotOne);
 304
 305     // Exclude from slot #1 any insn but A-type.
 306     if (HexagonMCInstrInfo::getType(MCII, *ID) != HexagonII::TypeALU32)
 307       if (onlyAin1)
 308         ISJ->Core.setUnits(ISJ->Core.getUnits() & ~slotOne);
 309
 310     // Branches must keep the original order.
 311     if (HexagonMCInstrInfo::getDesc(MCII, *ID).isBranch() ||
 312         HexagonMCInstrInfo::getDesc(MCII, *ID).isCall())
 313       if (jumps > 1) {
 314         if (jumpr || slotJump < slotLastJump) {
 315           // Error if indirect branch with another branch or
 316           // no more slots available for branches.
 317           Error = SHUFFLE_ERROR_BRANCHES;
 318           return false;
 319         }
 320         // Pin the branch to the highest slot available to it.
 321         ISJ->Core.setUnits(ISJ->Core.getUnits() & slotJump);
 322         // Update next highest slot available to branches.
 323         slotJump >>= 1;
 324       }
 325
 326     // A single load must use slot #0.
 327     if (HexagonMCInstrInfo::getDesc(MCII, *ID).mayLoad()) {
 328       if (loads == 1 && loads == memory)
 329         // Pin the load to slot #0.
 330         ISJ->Core.setUnits(ISJ->Core.getUnits() & slotSingleLoad);
 331     }
 332
 333     // A single store must use slot #0.
 334     if (HexagonMCInstrInfo::getDesc(MCII, *ID).mayStore()) {
 335       if (!store0) {
 336         if (stores == 1)
 337           ISJ->Core.setUnits(ISJ->Core.getUnits() & slotSingleStore);
 338         else if (stores > 1) {
 339           if (slotLoadStore < slotLastLoadStore) {
 340             // Error if no more slots available for stores.
 341             Error = SHUFFLE_ERROR_STORES;
 342             return false;
 343           }
 344           // Pin the store to the highest slot available to it.
 345           ISJ->Core.setUnits(ISJ->Core.getUnits() & slotLoadStore);
 346           // Update the next highest slot available to stores.
 347           slotLoadStore >>= 1;
 348         }
 349       }
 350       if (store1 && stores > 1) {
 351         // Error if a single store with another store.
 352         Error = SHUFFLE_ERROR_STORES;
 353         return false;
 354       }
 355     }
 356
 357     // flag if an instruction can only be executed in slot 3
 358     if (ISJ->Core.getUnits() == slotThree)
 359       bOnlySlot3 = true;
 360
 361     if (!ISJ->Core.getUnits()) {
 362       // Error if insn may not be executed in any slot.
 363       Error = SHUFFLE_ERROR_NOSLOTS;
 364       return false;
 365     }
 366   }
 367
 368   bool validateSlots = true;
 369   if (bOnlySlot3 == false && pSlot3Cnt == 1 && slot3ISJ != end()) {
 370     // save off slot mask of instruction marked with A_PREFER_SLOT3
 371     // and then pin it to slot #3
 372     unsigned saveUnits = slot3ISJ->Core.getUnits();
 373     slot3ISJ->Core.setUnits(saveUnits & slotThree);
 374
 375     HexagonUnitAuction AuctionCore;
 376     std::sort(begin(), end(), HexagonInstr::lessCore);
 377
 378     // see if things ok with that instruction being pinned to slot #3
 379     bool bFail = false;
 380     for (iterator I = begin(); I != end() && bFail != true; ++I)
 381       if (!AuctionCore.bid(I->Core.getUnits()))
 382         bFail = true;
 383
 384     // if yes, great, if not then restore original slot mask
 385     if (!bFail)
 386       validateSlots = false; // all good, no need to re-do auction
 387     else
 388       for (iterator ISJ = begin(); ISJ != end(); ++ISJ) {
 389         MCInst const *ID = ISJ->getDesc();
 390         if (HexagonMCInstrInfo::prefersSlot3(MCII, *ID))
 391           ISJ->Core.setUnits(saveUnits);
 392       }
 393   }
 394
 395   // Check if any slot, core, is over-subscribed.
 396   // Verify the core slot subscriptions.
 397   if (validateSlots) {
 398     HexagonUnitAuction AuctionCore;
 399
 400     std::sort(begin(), end(), HexagonInstr::lessCore);
 401
 402     for (iterator I = begin(); I != end(); ++I)
 403       if (!AuctionCore.bid(I->Core.getUnits())) {
 404         Error = SHUFFLE_ERROR_SLOTS;
 405         return false;
 406       }
 407   }
 408   // Verify the CVI slot subscriptions.
 409   {
 410     HexagonUnitAuction AuctionCVI;
 411
 412     std::sort(begin(), end(), HexagonInstr::lessCVI);
 413
 414     for (iterator I = begin(); I != end(); ++I)
 415       for (unsigned i = 0; i < I->CVI.getLanes(); ++i) // TODO: I->CVI.isValid?
 416         if (!AuctionCVI.bid(I->CVI.getUnits() << i)) {
 417           Error = SHUFFLE_ERROR_SLOTS;
 418           return false;
 419         }
 420   }
 421
 422   Error = SHUFFLE_SUCCESS;
 423   return true;
 424 }
 425
 426 bool HexagonShuffler::shuffle() {
 427   if (size() > HEXAGON_PACKET_SIZE) {
 428     // Ignore a packet with with more than what a packet can hold
 429     // or with compound or duplex insns for now.
 430     Error = SHUFFLE_ERROR_INVALID;
 431     return false;
 432   }
 433
 434   // Check and prepare packet.
 435   if (size() > 1 && check())
 436     // Reorder the handles for each slot.
 437     for (unsigned nSlot = 0, emptySlots = 0; nSlot < HEXAGON_PACKET_SIZE;
 438          ++nSlot) {
 439       iterator ISJ, ISK;
 440       unsigned slotSkip, slotWeight;
 441
 442       // Prioritize the handles considering their restrictions.
 443       for (ISJ = ISK = Packet.begin(), slotSkip = slotWeight = 0;
 444            ISK != Packet.end(); ++ISK, ++slotSkip)
 445         if (slotSkip < nSlot - emptySlots)
 446           // Note which handle to begin at.
 447           ++ISJ;
 448         else
 449           // Calculate the weight of the slot.
 450           slotWeight += ISK->Core.setWeight(HEXAGON_PACKET_SIZE - nSlot - 1);
 451
 452       if (slotWeight)
 453         // Sort the packet, favoring source order,
 454         // beginning after the previous slot.
 455         std::sort(ISJ, Packet.end());
 456       else
 457         // Skip unused slot.
 458         ++emptySlots;
 459     }
 460
 461   for (iterator ISJ = begin(); ISJ != end(); ++ISJ)
 462     DEBUG(dbgs().write_hex(ISJ->Core.getUnits());
 463           dbgs() << ':'
 464                  << HexagonMCInstrInfo::getDesc(MCII, *ISJ->getDesc())
 465                         .getOpcode();
 466           dbgs() << '\n');
 467   DEBUG(dbgs() << '\n');
 468
 469   return (!getError());
 470 }