1 //===----- HexagonShuffler.cpp - Instruction bundle shuffling -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the shuffling of insns inside a bundle according to the
11 // packet formation rules of the Hexagon ISA.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "hexagon-shuffle"
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"
31 // Insn shuffling priority.
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.
40 HexagonBid() : Bid(0){};
41 HexagonBid(unsigned B) { Bid = B ? MAX / countPopulation(B) : 0; };
43 // Check if the insn priority is overflowed.
44 bool isSold() const { return (Bid >= MAX); };
46 HexagonBid &operator+=(const HexagonBid &B) {
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;
59 HexagonUnitAuction() : isSold(0){};
62 bool bid(unsigned B) {
63 // Exclude already auctioned slots from the bid.
64 unsigned b = B & ~isSold;
66 for (unsigned i = 0; i < HEXAGON_PACKET_SIZE; ++i)
68 // Request candidate slots.
69 Scores[i] += HexagonBid(b);
70 isSold |= Scores[i].isSold() << i;
75 // Error if the desired slots are already full.
79 } // end anonymous namespace
81 unsigned HexagonResource::setWeight(unsigned s) {
82 const unsigned SlotWeight = 8;
83 const unsigned MaskWeight = SlotWeight - 1;
84 bool Key = (1 << s) & getUnits();
86 // TODO: Improve this API so that we can prevent misuse statically.
87 assert(SlotWeight * s < 32 && "Argument to setWeight too large.");
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.
93 (Key << (SlotWeight * s)) * ((MaskWeight - countPopulation(getUnits()))
94 << countTrailingZeros(getUnits()));
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);
121 HexagonCVIResource::HexagonCVIResource(TypeUnitsAndLanes *TUL,
122 MCInstrInfo const &MCII, unsigned s,
124 : HexagonResource(s), TUL(TUL) {
125 unsigned T = HexagonMCInstrInfo::getType(MCII, *id);
130 setUnits((*TUL)[T].first);
131 setLanes((*TUL)[T].second);
132 setLoad(HexagonMCInstrInfo::getDesc(MCII, *id).mayLoad());
133 setStore(HexagonMCInstrInfo::getDesc(MCII, *id).mayStore());
144 HexagonShuffler::HexagonShuffler(MCInstrInfo const &MCII,
145 MCSubtargetInfo const &STI)
146 : MCII(MCII), STI(STI) {
148 HexagonCVIResource::SetupTUL(&TUL, STI.getCPU());
151 void HexagonShuffler::reset() {
154 Error = SHUFFLE_SUCCESS;
157 void HexagonShuffler::append(MCInst const *ID, MCInst const *Extender,
158 unsigned S, bool X) {
159 HexagonInstr PI(&TUL, MCII, ID, Extender, S, X);
161 Packet.push_back(PI);
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
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();
193 // Collect information from the insns in the packet.
194 for (iterator ISJ = begin(); ISJ != end(); ++ISJ) {
195 MCInst const *ID = ISJ->getDesc();
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)
206 if (HexagonMCInstrInfo::prefersSlot3(MCII, *ID)) {
211 switch (HexagonMCInstrInfo::getType(MCII, *ID)) {
212 case HexagonII::TypeXTYPE:
213 if (HexagonMCInstrInfo::isFloat(MCII, *ID))
216 case HexagonII::TypeJR:
219 case HexagonII::TypeJ:
222 case HexagonII::TypeCVI_VM_VP_LDU:
224 case HexagonII::TypeCVI_VM_LD:
225 case HexagonII::TypeCVI_VM_TMP_LD:
226 case HexagonII::TypeCVI_VM_CUR_LD:
228 case HexagonII::TypeLD:
231 if (ISJ->Core.getUnits() == slotSingleLoad)
233 if (HexagonMCInstrInfo::getDesc(MCII, *ID).isReturn())
234 ++jumps, ++jump1; // DEALLOC_RETURN is of type LD.
236 case HexagonII::TypeCVI_VM_STU:
238 case HexagonII::TypeCVI_VM_ST:
239 case HexagonII::TypeCVI_VM_NEW_ST:
241 case HexagonII::TypeST:
244 if (ISJ->Core.getUnits() == slotSingleStore)
247 case HexagonII::TypeMEMOP:
253 case HexagonII::TypeNV:
254 ++memory; // NV insns are memory-like.
255 if (HexagonMCInstrInfo::getDesc(MCII, *ID).isBranch())
258 case HexagonII::TypeCR:
259 // Legacy conditional branch predicated on a register.
260 case HexagonII::TypeSYSTEM:
261 if (HexagonMCInstrInfo::getDesc(MCII, *ID).mayLoad())
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;
275 if (jump1 && jumps > 1) {
276 // Error if single branch with another branch.
277 Error = SHUFFLE_ERROR_BRANCHES;
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();
287 if (!ISJ->Core.getUnits()) {
288 // Error if insn may not be executed in any slot.
289 Error = SHUFFLE_ERROR_UNKNOWN;
293 // Exclude from slot #1 any insn but A2_nop.
294 if (HexagonMCInstrInfo::getDesc(MCII, *ID).getOpcode() != Hexagon::A2_nop)
296 ISJ->Core.setUnits(ISJ->Core.getUnits() & ~slotOne);
298 // Exclude from slot #1 any insn but A-type.
299 if (HexagonMCInstrInfo::getType(MCII, *ID) != HexagonII::TypeALU32)
301 ISJ->Core.setUnits(ISJ->Core.getUnits() & ~slotOne);
303 // Branches must keep the original order.
304 if (HexagonMCInstrInfo::getDesc(MCII, *ID).isBranch() ||
305 HexagonMCInstrInfo::getDesc(MCII, *ID).isCall())
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;
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.
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);
326 // A single store must use slot #0.
327 if (HexagonMCInstrInfo::getDesc(MCII, *ID).mayStore()) {
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;
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.
343 if (store1 && stores > 1) {
344 // Error if a single store with another store.
345 Error = SHUFFLE_ERROR_STORES;
350 // flag if an instruction can only be executed in slot 3
351 if (ISJ->Core.getUnits() == slotThree)
354 if (!ISJ->Core.getUnits()) {
355 // Error if insn may not be executed in any slot.
356 Error = SHUFFLE_ERROR_NOSLOTS;
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);
368 HexagonUnitAuction AuctionCore;
369 std::sort(begin(), end(), HexagonInstr::lessCore);
371 // see if things ok with that instruction being pinned to slot #3
373 for (iterator I = begin(); I != end() && bFail != true; ++I)
374 if (!AuctionCore.bid(I->Core.getUnits()))
377 // if yes, great, if not then restore original slot mask
379 validateSlots = false; // all good, no need to re-do auction
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);
388 // Check if any slot, core, is over-subscribed.
389 // Verify the core slot subscriptions.
391 HexagonUnitAuction AuctionCore;
393 std::sort(begin(), end(), HexagonInstr::lessCore);
395 for (iterator I = begin(); I != end(); ++I)
396 if (!AuctionCore.bid(I->Core.getUnits())) {
397 Error = SHUFFLE_ERROR_SLOTS;
401 // Verify the CVI slot subscriptions.
403 HexagonUnitAuction AuctionCVI;
405 std::sort(begin(), end(), HexagonInstr::lessCVI);
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;
415 Error = SHUFFLE_SUCCESS;
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;
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;
433 unsigned slotSkip, slotWeight;
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.
442 // Calculate the weight of the slot.
443 slotWeight += ISK->Core.setWeight(HEXAGON_PACKET_SIZE - nSlot - 1);
446 // Sort the packet, favoring source order,
447 // beginning after the previous slot.
448 std::sort(ISJ, Packet.end());
454 for (iterator ISJ = begin(); ISJ != end(); ++ISJ)
455 DEBUG(dbgs().write_hex(ISJ->Core.getUnits());
457 << HexagonMCInstrInfo::getDesc(MCII, *ISJ->getDesc())
460 DEBUG(dbgs() << '\n');
462 return (!getError());