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/StringExtras.h" 20 #include "llvm/ADT/Twine.h" 21 #include "llvm/MC/MCContext.h" 22 #include "llvm/MC/MCInst.h" 23 #include "llvm/MC/MCInstrDesc.h" 24 #include "llvm/MC/MCSubtargetInfo.h" 25 #include "llvm/Support/Compiler.h" 26 #include "llvm/Support/Debug.h" 27 #include "llvm/Support/MathExtras.h" 28 #include "llvm/Support/SourceMgr.h" 29 #include "llvm/Support/raw_ostream.h" 30 #include <algorithm> 31 #include <cassert> 32 #include <optional> 33 #include <utility> 34 35 #define DEBUG_TYPE "hexagon-shuffle" 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 / llvm::popcount(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 = llvm::popcount(Units); 104 unsigned Cttz = llvm::countr_zero(Units); 105 Weight = (1u << (SlotWeight * s)) * ((MaskWeight - Ctpop) << Cttz); 106 return Weight; 107 } 108 109 HexagonCVIResource::HexagonCVIResource(MCInstrInfo const &MCII, 110 MCSubtargetInfo const &STI, 111 unsigned s, 112 MCInst const *id) 113 : HexagonResource(s) { 114 115 const unsigned ItinUnits = HexagonMCInstrInfo::getCVIResources(MCII, STI, *id); 116 unsigned Lanes; 117 const unsigned Units = HexagonConvertUnits(ItinUnits, &Lanes); 118 119 if (Units == 0 && Lanes == 0) { 120 // For core insns. 121 Valid = false; 122 setUnits(0); 123 setLanes(0); 124 setLoad(false); 125 setStore(false); 126 } else { 127 // For an HVX insn. 128 Valid = true; 129 setUnits(Units); 130 setLanes(Lanes); 131 setLoad(HexagonMCInstrInfo::getDesc(MCII, *id).mayLoad()); 132 setStore(HexagonMCInstrInfo::getDesc(MCII, *id).mayStore()); 133 } 134 } 135 136 struct CVIUnits { 137 unsigned Units; 138 unsigned Lanes; 139 }; 140 using HVXInstsT = SmallVector<struct CVIUnits, 8>; 141 142 static unsigned makeAllBits(unsigned startBit, unsigned Lanes) 143 { 144 for (unsigned i = 1; i < Lanes; ++i) 145 startBit = (startBit << 1) | startBit; 146 return startBit; 147 } 148 149 static bool checkHVXPipes(const HVXInstsT &hvxInsts, unsigned startIdx, 150 unsigned usedUnits) { 151 if (startIdx < hvxInsts.size()) { 152 if (!hvxInsts[startIdx].Units) 153 return checkHVXPipes(hvxInsts, startIdx + 1, usedUnits); 154 for (unsigned b = 0x1; b <= 0x8; b <<= 1) { 155 if ((hvxInsts[startIdx].Units & b) == 0) 156 continue; 157 unsigned allBits = makeAllBits(b, hvxInsts[startIdx].Lanes); 158 if ((allBits & usedUnits) == 0) { 159 if (checkHVXPipes(hvxInsts, startIdx + 1, usedUnits | allBits)) 160 return true; 161 } 162 } 163 return false; 164 } 165 return true; 166 } 167 168 HexagonShuffler::HexagonShuffler(MCContext &Context, bool ReportErrors, 169 MCInstrInfo const &MCII, 170 MCSubtargetInfo const &STI) 171 : Context(Context), BundleFlags(), MCII(MCII), STI(STI), 172 ReportErrors(ReportErrors), CheckFailure() { 173 reset(); 174 } 175 176 void HexagonShuffler::reset() { 177 Packet.clear(); 178 BundleFlags = 0; 179 CheckFailure = false; 180 } 181 182 void HexagonShuffler::append(MCInst const &ID, MCInst const *Extender, 183 unsigned S) { 184 HexagonInstr PI(MCII, STI, &ID, Extender, S); 185 186 Packet.push_back(PI); 187 } 188 189 190 static const unsigned Slot0Mask = 1 << 0; 191 static const unsigned Slot1Mask = 1 << 1; 192 static const unsigned Slot3Mask = 1 << 3; 193 static const unsigned slotSingleLoad = Slot0Mask; 194 static const unsigned slotSingleStore = Slot0Mask; 195 196 void HexagonShuffler::restrictSlot1AOK(HexagonPacketSummary const &Summary) { 197 if (Summary.Slot1AOKLoc) 198 for (HexagonInstr &ISJ : insts()) { 199 MCInst const &Inst = ISJ.getDesc(); 200 const unsigned Type = HexagonMCInstrInfo::getType(MCII, Inst); 201 if (Type != HexagonII::TypeALU32_2op && 202 Type != HexagonII::TypeALU32_3op && 203 Type != HexagonII::TypeALU32_ADDI) { 204 const unsigned Units = ISJ.Core.getUnits(); 205 206 if (Units & Slot1Mask) { 207 AppliedRestrictions.push_back(std::make_pair( 208 Inst.getLoc(), 209 "Instruction was restricted from being in slot 1")); 210 AppliedRestrictions.push_back(std::make_pair( 211 *Summary.Slot1AOKLoc, "Instruction can only be combined " 212 "with an ALU instruction in slot 1")); 213 ISJ.Core.setUnits(Units & ~Slot1Mask); 214 } 215 } 216 } 217 } 218 219 void HexagonShuffler::restrictNoSlot1Store( 220 HexagonPacketSummary const &Summary) { 221 // If this packet contains an instruction that bars slot-1 stores, 222 // we should mask off slot 1 from all of the store instructions in 223 // this packet. 224 225 if (!Summary.NoSlot1StoreLoc) 226 return; 227 228 bool AppliedRestriction = false; 229 230 for (HexagonInstr &ISJ : insts()) { 231 MCInst const &Inst = ISJ.getDesc(); 232 if (HexagonMCInstrInfo::getDesc(MCII, Inst).mayStore()) { 233 unsigned Units = ISJ.Core.getUnits(); 234 if (Units & Slot1Mask) { 235 AppliedRestriction = true; 236 AppliedRestrictions.push_back(std::make_pair( 237 Inst.getLoc(), "Instruction was restricted from being in slot 1")); 238 ISJ.Core.setUnits(Units & ~Slot1Mask); 239 } 240 } 241 } 242 243 if (AppliedRestriction) 244 AppliedRestrictions.push_back( 245 std::make_pair(*Summary.NoSlot1StoreLoc, 246 "Instruction does not allow a store in slot 1")); 247 } 248 249 bool HexagonShuffler::applySlotRestrictions(HexagonPacketSummary const &Summary, 250 const bool DoShuffle) { 251 // These restrictions can modify the slot masks in the instructions 252 // in the Packet member. They should run unconditionally and their 253 // order does not matter. 254 restrictSlot1AOK(Summary); 255 restrictNoSlot1Store(Summary); 256 257 permitNonSlot(); 258 259 // These restrictions can modify the slot masks in the instructions 260 // in the Packet member, but they can also detect constraint failures 261 // which are fatal. 262 if (!CheckFailure) 263 restrictStoreLoadOrder(Summary); 264 if (!CheckFailure) 265 restrictBranchOrder(Summary); 266 if (!CheckFailure) 267 restrictPreferSlot3(Summary, DoShuffle); 268 return !CheckFailure; 269 } 270 271 void HexagonShuffler::restrictBranchOrder(HexagonPacketSummary const &Summary) { 272 // preserve branch order 273 const bool HasMultipleBranches = Summary.branchInsts.size() > 1; 274 if (!HasMultipleBranches) 275 return; 276 277 if (Summary.branchInsts.size() > 2) { 278 reportError(Twine("too many branches in packet")); 279 return; 280 } 281 282 const static std::pair<unsigned, unsigned> jumpSlots[] = { 283 {8, 4}, {8, 2}, {8, 1}, {4, 2}, {4, 1}, {2, 1}}; 284 // try all possible choices 285 for (std::pair<unsigned, unsigned> jumpSlot : jumpSlots) { 286 // validate first jump with this slot rule 287 if (!(jumpSlot.first & Summary.branchInsts[0]->Core.getUnits())) 288 continue; 289 290 // validate second jump with this slot rule 291 if (!(jumpSlot.second & Summary.branchInsts[1]->Core.getUnits())) 292 continue; 293 294 // both valid for this configuration, set new slot rules 295 const HexagonPacket PacketSave = Packet; 296 Summary.branchInsts[0]->Core.setUnits(jumpSlot.first); 297 Summary.branchInsts[1]->Core.setUnits(jumpSlot.second); 298 299 const bool HasShuffledPacket = tryAuction(Summary).has_value(); 300 if (HasShuffledPacket) 301 return; 302 303 // if yes, great, if not then restore original slot mask 304 // restore original values 305 Packet = PacketSave; 306 } 307 308 reportResourceError(Summary, "out of slots"); 309 } 310 311 void HexagonShuffler::permitNonSlot() { 312 for (HexagonInstr &ISJ : insts()) { 313 const bool RequiresSlot = HexagonMCInstrInfo::requiresSlot(STI, *ISJ.ID); 314 if (!RequiresSlot) 315 ISJ.Core.setAllUnits(); 316 } 317 } 318 319 bool HexagonShuffler::ValidResourceUsage(HexagonPacketSummary const &Summary) { 320 std::optional<HexagonPacket> ShuffledPacket = tryAuction(Summary); 321 322 if (!ShuffledPacket) { 323 reportResourceError(Summary, "slot error"); 324 return false; 325 } 326 327 // Verify the CVI slot subscriptions. 328 llvm::stable_sort(*ShuffledPacket, HexagonInstr::lessCVI); 329 // create vector of hvx instructions to check 330 HVXInstsT hvxInsts; 331 hvxInsts.clear(); 332 for (const auto &I : *ShuffledPacket) { 333 struct CVIUnits inst; 334 inst.Units = I.CVI.getUnits(); 335 inst.Lanes = I.CVI.getLanes(); 336 if (inst.Units == 0) 337 continue; // not an hvx inst or an hvx inst that doesn't uses any pipes 338 hvxInsts.push_back(inst); 339 } 340 341 // if there are any hvx instructions in this packet, check pipe usage 342 if (hvxInsts.size() > 0) { 343 unsigned startIdx, usedUnits; 344 startIdx = usedUnits = 0x0; 345 if (!checkHVXPipes(hvxInsts, startIdx, usedUnits)) { 346 // too many pipes used to be valid 347 reportError(Twine("invalid instruction packet: slot error")); 348 return false; 349 } 350 } 351 352 Packet = *ShuffledPacket; 353 354 return true; 355 } 356 357 bool HexagonShuffler::restrictStoreLoadOrder( 358 HexagonPacketSummary const &Summary) { 359 // Modify packet accordingly. 360 // TODO: need to reserve slots #0 and #1 for duplex insns. 361 static const unsigned slotFirstLoadStore = Slot1Mask; 362 static const unsigned slotLastLoadStore = Slot0Mask; 363 unsigned slotLoadStore = slotFirstLoadStore; 364 365 for (iterator ISJ = begin(); ISJ != end(); ++ISJ) { 366 MCInst const &ID = ISJ->getDesc(); 367 368 if (!ISJ->Core.getUnits()) 369 // Error if insn may not be executed in any slot. 370 return false; 371 372 // A single load must use slot #0. 373 if (HexagonMCInstrInfo::getDesc(MCII, ID).mayLoad()) { 374 if (Summary.loads == 1 && Summary.loads == Summary.memory && 375 Summary.memops == 0) 376 // Pin the load to slot #0. 377 switch (ID.getOpcode()) { 378 case Hexagon::V6_vgathermw: 379 case Hexagon::V6_vgathermh: 380 case Hexagon::V6_vgathermhw: 381 case Hexagon::V6_vgathermwq: 382 case Hexagon::V6_vgathermhq: 383 case Hexagon::V6_vgathermhwq: 384 // Slot1 only loads 385 break; 386 default: 387 ISJ->Core.setUnits(ISJ->Core.getUnits() & slotSingleLoad); 388 break; 389 } 390 else if (Summary.loads >= 1 && isMemReorderDisabled()) { // }:mem_noshuf 391 // Loads must keep the original order ONLY if 392 // isMemReorderDisabled() == true 393 if (slotLoadStore < slotLastLoadStore) { 394 // Error if no more slots available for loads. 395 reportError("invalid instruction packet: too many loads"); 396 return false; 397 } 398 // Pin the load to the highest slot available to it. 399 ISJ->Core.setUnits(ISJ->Core.getUnits() & slotLoadStore); 400 // Update the next highest slot available to loads. 401 slotLoadStore >>= 1; 402 } 403 } 404 405 // A single store must use slot #0. 406 if (HexagonMCInstrInfo::getDesc(MCII, ID).mayStore()) { 407 if (!Summary.store0) { 408 const bool PacketHasNoOnlySlot0 = 409 llvm::none_of(insts(), [&](HexagonInstr const &I) { 410 return I.Core.getUnits() == Slot0Mask && 411 I.ID->getOpcode() != ID.getOpcode(); 412 }); 413 const bool SafeToMoveToSlot0 = 414 (Summary.loads == 0) || 415 (!isMemReorderDisabled() && PacketHasNoOnlySlot0); 416 417 if (Summary.stores == 1 && SafeToMoveToSlot0) 418 // Pin the store to slot #0 only if isMemReorderDisabled() == false 419 ISJ->Core.setUnits(ISJ->Core.getUnits() & slotSingleStore); 420 else if (Summary.stores >= 1) { 421 if (slotLoadStore < slotLastLoadStore) { 422 // Error if no more slots available for stores. 423 reportError("invalid instruction packet: too many stores"); 424 return false; 425 } 426 // Pin the store to the highest slot available to it. 427 ISJ->Core.setUnits(ISJ->Core.getUnits() & slotLoadStore); 428 // Update the next highest slot available to stores. 429 slotLoadStore >>= 1; 430 } 431 } 432 if (Summary.store1 && Summary.stores > 1) { 433 // Error if a single store with another store. 434 reportError("invalid instruction packet: too many stores"); 435 return false; 436 } 437 } 438 } 439 440 return true; 441 } 442 443 static std::string SlotMaskToText(unsigned SlotMask) { 444 SmallVector<std::string, HEXAGON_PRESHUFFLE_PACKET_SIZE> Slots; 445 for (unsigned SlotNum = 0; SlotNum < HEXAGON_PACKET_SIZE; SlotNum++) 446 if ((SlotMask & (1 << SlotNum)) != 0) 447 Slots.push_back(utostr(SlotNum)); 448 449 return llvm::join(Slots, StringRef(", ")); 450 } 451 452 HexagonShuffler::HexagonPacketSummary HexagonShuffler::GetPacketSummary() { 453 HexagonPacketSummary Summary = HexagonPacketSummary(); 454 455 // Collect information from the insns in the packet. 456 for (iterator ISJ = begin(); ISJ != end(); ++ISJ) { 457 MCInst const &ID = ISJ->getDesc(); 458 459 if (HexagonMCInstrInfo::isRestrictSlot1AOK(MCII, ID)) 460 Summary.Slot1AOKLoc = ID.getLoc(); 461 if (HexagonMCInstrInfo::isRestrictNoSlot1Store(MCII, ID)) 462 Summary.NoSlot1StoreLoc = ID.getLoc(); 463 464 if (HexagonMCInstrInfo::prefersSlot3(MCII, ID)) { 465 ++Summary.pSlot3Cnt; 466 Summary.PrefSlot3Inst = ISJ; 467 } 468 const unsigned ReservedSlots = 469 HexagonMCInstrInfo::getOtherReservedSlots(MCII, STI, ID); 470 Summary.ReservedSlotMask |= ReservedSlots; 471 if (ReservedSlots != 0) 472 AppliedRestrictions.push_back(std::make_pair(ID.getLoc(), 473 (Twine("Instruction has reserved slots: ") + 474 SlotMaskToText(ReservedSlots)).str())); 475 476 switch (HexagonMCInstrInfo::getType(MCII, ID)) { 477 case HexagonII::TypeS_2op: 478 case HexagonII::TypeS_3op: 479 case HexagonII::TypeALU64: 480 break; 481 case HexagonII::TypeJ: 482 if (HexagonMCInstrInfo::IsABranchingInst(MCII, STI, *ISJ->ID)) 483 Summary.branchInsts.push_back(ISJ); 484 break; 485 case HexagonII::TypeCVI_VM_VP_LDU: 486 case HexagonII::TypeCVI_VM_LD: 487 case HexagonII::TypeCVI_VM_TMP_LD: 488 case HexagonII::TypeCVI_GATHER: 489 case HexagonII::TypeCVI_GATHER_DV: 490 case HexagonII::TypeCVI_GATHER_RST: 491 ++Summary.NonZCVIloads; 492 [[fallthrough]]; 493 case HexagonII::TypeCVI_ZW: 494 ++Summary.AllCVIloads; 495 [[fallthrough]]; 496 case HexagonII::TypeLD: 497 ++Summary.loads; 498 ++Summary.memory; 499 if (ISJ->Core.getUnits() == slotSingleLoad || 500 HexagonMCInstrInfo::getType(MCII, ID) == HexagonII::TypeCVI_VM_VP_LDU) 501 ++Summary.load0; 502 if (HexagonMCInstrInfo::getDesc(MCII, ID).isReturn()) 503 Summary.branchInsts.push_back(ISJ); 504 break; 505 case HexagonII::TypeCVI_VM_STU: 506 case HexagonII::TypeCVI_VM_ST: 507 case HexagonII::TypeCVI_VM_NEW_ST: 508 case HexagonII::TypeCVI_SCATTER: 509 case HexagonII::TypeCVI_SCATTER_DV: 510 case HexagonII::TypeCVI_SCATTER_RST: 511 case HexagonII::TypeCVI_SCATTER_NEW_RST: 512 case HexagonII::TypeCVI_SCATTER_NEW_ST: 513 ++Summary.CVIstores; 514 [[fallthrough]]; 515 case HexagonII::TypeST: 516 ++Summary.stores; 517 ++Summary.memory; 518 if (ISJ->Core.getUnits() == slotSingleStore || 519 HexagonMCInstrInfo::getType(MCII, ID) == HexagonII::TypeCVI_VM_STU) 520 ++Summary.store0; 521 break; 522 case HexagonII::TypeV4LDST: 523 ++Summary.loads; 524 ++Summary.stores; 525 ++Summary.store1; 526 ++Summary.memops; 527 ++Summary.memory; 528 break; 529 case HexagonII::TypeNCJ: 530 ++Summary.memory; // NV insns are memory-like. 531 Summary.branchInsts.push_back(ISJ); 532 break; 533 case HexagonII::TypeV2LDST: 534 if (HexagonMCInstrInfo::getDesc(MCII, ID).mayLoad()) { 535 ++Summary.loads; 536 ++Summary.memory; 537 if (ISJ->Core.getUnits() == slotSingleLoad || 538 HexagonMCInstrInfo::getType(MCII, ID) == 539 HexagonII::TypeCVI_VM_VP_LDU) 540 ++Summary.load0; 541 } else { 542 assert(HexagonMCInstrInfo::getDesc(MCII, ID).mayStore()); 543 ++Summary.memory; 544 ++Summary.stores; 545 } 546 break; 547 case HexagonII::TypeCR: 548 // Legacy conditional branch predicated on a register. 549 case HexagonII::TypeCJ: 550 if (HexagonMCInstrInfo::getDesc(MCII, ID).isBranch()) 551 Summary.branchInsts.push_back(ISJ); 552 break; 553 case HexagonII::TypeDUPLEX: { 554 ++Summary.duplex; 555 MCInst const &Inst0 = *ID.getOperand(0).getInst(); 556 MCInst const &Inst1 = *ID.getOperand(1).getInst(); 557 if (HexagonMCInstrInfo::getDesc(MCII, Inst0).isBranch()) 558 Summary.branchInsts.push_back(ISJ); 559 if (HexagonMCInstrInfo::getDesc(MCII, Inst1).isBranch()) 560 Summary.branchInsts.push_back(ISJ); 561 if (HexagonMCInstrInfo::getDesc(MCII, Inst0).isReturn()) 562 Summary.branchInsts.push_back(ISJ); 563 if (HexagonMCInstrInfo::getDesc(MCII, Inst1).isReturn()) 564 Summary.branchInsts.push_back(ISJ); 565 break; 566 } 567 } 568 } 569 return Summary; 570 } 571 572 bool HexagonShuffler::ValidPacketMemoryOps( 573 HexagonPacketSummary const &Summary) const { 574 // Check if the packet is legal. 575 const unsigned ZCVIloads = Summary.AllCVIloads - Summary.NonZCVIloads; 576 const bool ValidHVXMem = 577 Summary.NonZCVIloads <= 1 && ZCVIloads <= 1 && Summary.CVIstores <= 1; 578 const bool InvalidPacket = 579 ((Summary.load0 > 1 || Summary.store0 > 1 || !ValidHVXMem) || 580 (Summary.duplex > 1 || (Summary.duplex && Summary.memory))); 581 582 return !InvalidPacket; 583 } 584 585 void HexagonShuffler::restrictPreferSlot3(HexagonPacketSummary const &Summary, 586 const bool DoShuffle) { 587 // flag if an instruction requires to be in slot 3 588 const bool HasOnlySlot3 = llvm::any_of(insts(), [&](HexagonInstr const &I) { 589 return (I.Core.getUnits() == Slot3Mask); 590 }); 591 const bool NeedsPrefSlot3Shuffle = Summary.branchInsts.size() <= 1 && 592 !HasOnlySlot3 && Summary.pSlot3Cnt == 1 && 593 Summary.PrefSlot3Inst && DoShuffle; 594 595 if (!NeedsPrefSlot3Shuffle) 596 return; 597 598 HexagonInstr *PrefSlot3Inst = *Summary.PrefSlot3Inst; 599 // save off slot mask of instruction marked with A_PREFER_SLOT3 600 // and then pin it to slot #3 601 const unsigned saveUnits = PrefSlot3Inst->Core.getUnits(); 602 PrefSlot3Inst->Core.setUnits(saveUnits & Slot3Mask); 603 const bool HasShuffledPacket = tryAuction(Summary).has_value(); 604 if (HasShuffledPacket) 605 return; 606 607 PrefSlot3Inst->Core.setUnits(saveUnits); 608 } 609 610 /// Check that the packet is legal and enforce relative insn order. 611 bool HexagonShuffler::check(const bool RequireShuffle) { 612 const HexagonPacketSummary Summary = GetPacketSummary(); 613 if (!applySlotRestrictions(Summary, RequireShuffle)) 614 return false; 615 616 if (!ValidPacketMemoryOps(Summary)) { 617 reportError("invalid instruction packet"); 618 return false; 619 } 620 621 if (RequireShuffle) 622 ValidResourceUsage(Summary); 623 624 return !CheckFailure; 625 } 626 627 std::optional<HexagonShuffler::HexagonPacket> 628 HexagonShuffler::tryAuction(HexagonPacketSummary const &Summary) { 629 HexagonPacket PacketResult = Packet; 630 HexagonUnitAuction AuctionCore(Summary.ReservedSlotMask); 631 llvm::stable_sort(PacketResult, HexagonInstr::lessCore); 632 633 const bool ValidSlots = 634 llvm::all_of(insts(PacketResult), [&AuctionCore](HexagonInstr const &I) { 635 return AuctionCore.bid(I.Core.getUnits()); 636 }); 637 638 LLVM_DEBUG( 639 dbgs() << "Shuffle attempt: " << (ValidSlots ? "passed" : "failed") 640 << "\n"; 641 for (HexagonInstr const &ISJ : insts(PacketResult)) 642 dbgs() << "\t" << HexagonMCInstrInfo::getName(MCII, *ISJ.ID) << ": " 643 << llvm::format_hex(ISJ.Core.getUnits(), 4, true) << "\n"; 644 ); 645 646 std::optional<HexagonPacket> Res; 647 if (ValidSlots) 648 Res = PacketResult; 649 650 return Res; 651 } 652 653 bool HexagonShuffler::shuffle() { 654 if (size() > HEXAGON_PACKET_SIZE) { 655 // Ignore a packet with more than what a packet can hold 656 // or with compound or duplex insns for now. 657 reportError("invalid instruction packet"); 658 return false; 659 } 660 661 // Check and prepare packet. 662 bool Ok = check(); 663 if (size() > 1 && Ok) 664 // Reorder the handles for each slot. 665 for (unsigned nSlot = 0, emptySlots = 0; nSlot < HEXAGON_PACKET_SIZE; 666 ++nSlot) { 667 iterator ISJ, ISK; 668 unsigned slotSkip, slotWeight; 669 670 // Prioritize the handles considering their restrictions. 671 for (ISJ = ISK = Packet.begin(), slotSkip = slotWeight = 0; 672 ISK != Packet.end(); ++ISK, ++slotSkip) 673 if (slotSkip < nSlot - emptySlots) 674 // Note which handle to begin at. 675 ++ISJ; 676 else 677 // Calculate the weight of the slot. 678 slotWeight += ISK->Core.setWeight(HEXAGON_PACKET_SIZE - nSlot - 1); 679 680 if (slotWeight) 681 // Sort the packet, favoring source order, 682 // beginning after the previous slot. 683 std::stable_sort(ISJ, Packet.end()); 684 else 685 // Skip unused slot. 686 ++emptySlots; 687 } 688 689 LLVM_DEBUG( 690 for (HexagonInstr const &ISJ : insts()) { 691 dbgs().write_hex(ISJ.Core.getUnits()); 692 if (ISJ.CVI.isValid()) { 693 dbgs() << '/'; 694 dbgs().write_hex(ISJ.CVI.getUnits()) << '|'; 695 dbgs() << ISJ.CVI.getLanes(); 696 } 697 dbgs() << ':' 698 << HexagonMCInstrInfo::getDesc(MCII, ISJ.getDesc()).getOpcode() 699 << '\n'; 700 } dbgs() << '\n'; 701 ); 702 703 return Ok; 704 } 705 706 void HexagonShuffler::reportResourceError(HexagonPacketSummary const &Summary, StringRef Err) { 707 if (ReportErrors) 708 reportResourceUsage(Summary); 709 reportError(Twine("invalid instruction packet: ") + Err); 710 } 711 712 713 void HexagonShuffler::reportResourceUsage(HexagonPacketSummary const &Summary) { 714 auto SM = Context.getSourceManager(); 715 if (SM) { 716 for (HexagonInstr const &I : insts()) { 717 const unsigned Units = I.Core.getUnits(); 718 719 if (HexagonMCInstrInfo::requiresSlot(STI, *I.ID)) { 720 const std::string UnitsText = Units ? SlotMaskToText(Units) : "<None>"; 721 SM->PrintMessage(I.ID->getLoc(), SourceMgr::DK_Note, 722 Twine("Instruction can utilize slots: ") + 723 UnitsText); 724 } 725 else if (!HexagonMCInstrInfo::isImmext(*I.ID)) 726 SM->PrintMessage(I.ID->getLoc(), SourceMgr::DK_Note, 727 "Instruction does not require a slot"); 728 } 729 } 730 } 731 732 void HexagonShuffler::reportError(Twine const &Msg) { 733 CheckFailure = true; 734 if (ReportErrors) { 735 for (auto const &I : AppliedRestrictions) { 736 auto SM = Context.getSourceManager(); 737 if (SM) 738 SM->PrintMessage(I.first, SourceMgr::DK_Note, I.second); 739 } 740 Context.reportError(Loc, Msg); 741 } 742 } 743