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