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