• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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:
HexagonBid()40   HexagonBid() : Bid(0){};
HexagonBid(unsigned B)41   HexagonBid(unsigned B) { Bid = B ? MAX / countPopulation(B) : 0; };
42 
43   // Check if the insn priority is overflowed.
isSold() const44   bool isSold() const { return (Bid >= MAX); };
45 
operator +=(const HexagonBid & B)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:
HexagonUnitAuction()59   HexagonUnitAuction() : isSold(0){};
60 
61   // Allocate slots.
bid(unsigned B)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 
setWeight(unsigned s)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 
SetupTUL(TypeUnitsAndLanes * TUL,StringRef CPU)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 
HexagonCVIResource(TypeUnitsAndLanes * TUL,MCInstrInfo const & MCII,unsigned s,MCInst const * id)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 
HexagonShuffler(MCInstrInfo const & MCII,MCSubtargetInfo const & STI)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 
reset()151 void HexagonShuffler::reset() {
152   Packet.clear();
153   BundleFlags = 0;
154   Error = SHUFFLE_SUCCESS;
155 }
156 
append(MCInst const * ID,MCInst const * Extender,unsigned S,bool X)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.
check()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 
shuffle()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