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