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
37using namespace llvm;
38
39namespace {
40
41// Insn shuffling priority.
42class 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
49public:
50 HexagonBid() = default;
51 HexagonBid(unsigned B) { Bid = B ? MAX / llvm::popcount(Value: 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.
63class HexagonUnitAuction {
64 HexagonBid Scores[HEXAGON_PACKET_SIZE];
65 // Mask indicating which slot is unavailable.
66 unsigned isSold : HEXAGON_PACKET_SIZE;
67
68public:
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
91unsigned 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(Value: Units);
104 unsigned Cttz = llvm::countr_zero(Val: Units);
105 Weight = (1u << (SlotWeight * s)) * ((MaskWeight - Ctpop) << Cttz);
106 return Weight;
107}
108
109HexagonCVIResource::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, MCI: *id);
116 unsigned Lanes;
117 const unsigned Units = HexagonConvertUnits(ItinUnits, Lanes: &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, MCI: *id).mayLoad());
132 setStore(HexagonMCInstrInfo::getDesc(MCII, MCI: *id).mayStore());
133 }
134}
135
136struct CVIUnits {
137 unsigned Units;
138 unsigned Lanes;
139};
140using HVXInstsT = SmallVector<struct CVIUnits, 8>;
141
142static 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
149static 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: 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(startBit: b, Lanes: hvxInsts[startIdx].Lanes);
158 if ((allBits & usedUnits) == 0) {
159 if (checkHVXPipes(hvxInsts, startIdx: startIdx + 1, usedUnits: usedUnits | allBits))
160 return true;
161 }
162 }
163 return false;
164 }
165 return true;
166}
167
168HexagonShuffler::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
176void HexagonShuffler::reset() {
177 Packet.clear();
178 BundleFlags = 0;
179 CheckFailure = false;
180}
181
182void HexagonShuffler::append(MCInst const &ID, MCInst const *Extender,
183 unsigned S) {
184 HexagonInstr PI(MCII, STI, &ID, Extender, S);
185
186 Packet.push_back(Elt: PI);
187}
188
189
190static const unsigned Slot0Mask = 1 << 0;
191static const unsigned Slot1Mask = 1 << 1;
192static const unsigned Slot3Mask = 1 << 3;
193static const unsigned slotSingleLoad = Slot0Mask;
194static const unsigned slotSingleStore = Slot0Mask;
195
196void 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, MCI: 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(x: std::make_pair(
208 x: Inst.getLoc(),
209 y: "Instruction was restricted from being in slot 1"));
210 AppliedRestrictions.push_back(x: std::make_pair(
211 x: *Summary.Slot1AOKLoc, y: "Instruction can only be combined "
212 "with an ALU instruction in slot 1"));
213 ISJ.Core.setUnits(Units & ~Slot1Mask);
214 }
215 }
216 }
217}
218
219void 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, MCI: Inst).mayStore()) {
233 unsigned Units = ISJ.Core.getUnits();
234 if (Units & Slot1Mask) {
235 AppliedRestriction = true;
236 AppliedRestrictions.push_back(x: std::make_pair(
237 x: Inst.getLoc(), y: "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 x: std::make_pair(x: *Summary.NoSlot1StoreLoc,
246 y: "Instruction does not allow a store in slot 1"));
247}
248
249bool 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
271void 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(Msg: 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, Err: "out of slots");
309}
310
311void HexagonShuffler::permitNonSlot() {
312 for (HexagonInstr &ISJ : insts()) {
313 const bool RequiresSlot = HexagonMCInstrInfo::requiresSlot(STI, MCI: *ISJ.ID);
314 if (!RequiresSlot)
315 ISJ.Core.setAllUnits();
316 }
317}
318
319bool HexagonShuffler::ValidResourceUsage(HexagonPacketSummary const &Summary) {
320 std::optional<HexagonPacket> ShuffledPacket = tryAuction(Summary);
321
322 if (!ShuffledPacket) {
323 reportResourceError(Summary, Err: "slot error");
324 return false;
325 }
326
327 // Verify the CVI slot subscriptions.
328 llvm::stable_sort(Range&: *ShuffledPacket, C: 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(Elt: 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(Msg: Twine("invalid instruction packet: slot error"));
348 return false;
349 }
350 }
351
352 Packet = *ShuffledPacket;
353
354 return true;
355}
356
357bool 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, MCI: 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(Msg: "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, MCI: ID).mayStore()) {
407 if (!Summary.store0) {
408 const bool PacketHasNoOnlySlot0 =
409 llvm::none_of(Range: insts(), P: [&](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(Msg: "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(Msg: "invalid instruction packet: too many stores");
435 return false;
436 }
437 }
438 }
439
440 return true;
441}
442
443static 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(Elt: utostr(X: SlotNum));
448
449 return llvm::join(R&: Slots, Separator: StringRef(", "));
450}
451
452HexagonShuffler::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, MCI: ID))
460 Summary.Slot1AOKLoc = ID.getLoc();
461 if (HexagonMCInstrInfo::isRestrictNoSlot1Store(MCII, MCI: ID))
462 Summary.NoSlot1StoreLoc = ID.getLoc();
463
464 if (HexagonMCInstrInfo::prefersSlot3(MCII, MCI: ID)) {
465 ++Summary.pSlot3Cnt;
466 Summary.PrefSlot3Inst = ISJ;
467 }
468 const unsigned ReservedSlots =
469 HexagonMCInstrInfo::getOtherReservedSlots(MCII, STI, MCI: ID);
470 Summary.ReservedSlotMask |= ReservedSlots;
471 if (ReservedSlots != 0)
472 AppliedRestrictions.push_back(x: std::make_pair(x: ID.getLoc(),
473 y: (Twine("Instruction has reserved slots: ") +
474 SlotMaskToText(SlotMask: ReservedSlots)).str()));
475
476 switch (HexagonMCInstrInfo::getType(MCII, MCI: 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, I: *ISJ->ID))
483 Summary.branchInsts.push_back(Elt: 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, MCI: ID) == HexagonII::TypeCVI_VM_VP_LDU)
501 ++Summary.load0;
502 if (HexagonMCInstrInfo::getDesc(MCII, MCI: ID).isReturn())
503 Summary.branchInsts.push_back(Elt: 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, MCI: 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(Elt: ISJ);
532 break;
533 case HexagonII::TypeV2LDST:
534 if (HexagonMCInstrInfo::getDesc(MCII, MCI: ID).mayLoad()) {
535 ++Summary.loads;
536 ++Summary.memory;
537 if (ISJ->Core.getUnits() == slotSingleLoad ||
538 HexagonMCInstrInfo::getType(MCII, MCI: 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, MCI: ID).isBranch())
551 Summary.branchInsts.push_back(Elt: ISJ);
552 break;
553 case HexagonII::TypeDUPLEX: {
554 ++Summary.duplex;
555 MCInst const &Inst0 = *ID.getOperand(i: 0).getInst();
556 MCInst const &Inst1 = *ID.getOperand(i: 1).getInst();
557 if (HexagonMCInstrInfo::getDesc(MCII, MCI: Inst0).isBranch())
558 Summary.branchInsts.push_back(Elt: ISJ);
559 if (HexagonMCInstrInfo::getDesc(MCII, MCI: Inst1).isBranch())
560 Summary.branchInsts.push_back(Elt: ISJ);
561 if (HexagonMCInstrInfo::getDesc(MCII, MCI: Inst0).isReturn())
562 Summary.branchInsts.push_back(Elt: ISJ);
563 if (HexagonMCInstrInfo::getDesc(MCII, MCI: Inst1).isReturn())
564 Summary.branchInsts.push_back(Elt: ISJ);
565 break;
566 }
567 }
568 }
569 return Summary;
570}
571
572bool 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
585void 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(Range: insts(), P: [&](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.
611bool HexagonShuffler::check(const bool RequireShuffle) {
612 const HexagonPacketSummary Summary = GetPacketSummary();
613 if (!applySlotRestrictions(Summary, DoShuffle: RequireShuffle))
614 return false;
615
616 if (!ValidPacketMemoryOps(Summary)) {
617 reportError(Msg: "invalid instruction packet");
618 return false;
619 }
620
621 if (RequireShuffle)
622 ValidResourceUsage(Summary);
623
624 return !CheckFailure;
625}
626
627std::optional<HexagonShuffler::HexagonPacket>
628HexagonShuffler::tryAuction(HexagonPacketSummary const &Summary) {
629 HexagonPacket PacketResult = Packet;
630 HexagonUnitAuction AuctionCore(Summary.ReservedSlotMask);
631 llvm::stable_sort(Range&: PacketResult, C: HexagonInstr::lessCore);
632
633 const bool ValidSlots =
634 llvm::all_of(Range: insts(P&: PacketResult), P: [&AuctionCore](HexagonInstr const &I) {
635 return AuctionCore.bid(B: 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
653bool 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(Msg: "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(first: ISJ, last: 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
706void HexagonShuffler::reportResourceError(HexagonPacketSummary const &Summary, StringRef Err) {
707 if (ReportErrors)
708 reportResourceUsage(Summary);
709 reportError(Msg: Twine("invalid instruction packet: ") + Err);
710}
711
712
713void 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, MCI: *I.ID)) {
720 const std::string UnitsText = Units ? SlotMaskToText(SlotMask: Units) : "<None>";
721 SM->PrintMessage(Loc: I.ID->getLoc(), Kind: SourceMgr::DK_Note,
722 Msg: Twine("Instruction can utilize slots: ") +
723 UnitsText);
724 }
725 else if (!HexagonMCInstrInfo::isImmext(MCI: *I.ID))
726 SM->PrintMessage(Loc: I.ID->getLoc(), Kind: SourceMgr::DK_Note,
727 Msg: "Instruction does not require a slot");
728 }
729 }
730}
731
732void 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(Loc: I.first, Kind: SourceMgr::DK_Note, Msg: I.second);
739 }
740 Context.reportError(L: Loc, Msg);
741 }
742}
743