1 //===- HexagonShuffler.h - Instruction bundle shuffling ---------*- C++ -*-===//
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 #ifndef LLVM_LIB_TARGET_HEXAGON_MCTARGETDESC_HEXAGONSHUFFLER_H
15 #define LLVM_LIB_TARGET_HEXAGON_MCTARGETDESC_HEXAGONSHUFFLER_H
16 
17 #include "MCTargetDesc/HexagonMCInstrInfo.h"
18 #include "MCTargetDesc/HexagonMCTargetDesc.h"
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/StringRef.h"
23 #include "llvm/Support/MathExtras.h"
24 #include "llvm/Support/SMLoc.h"
25 #include <cstdint>
26 #include <functional>
27 #include <utility>
28 
29 namespace llvm {
30 
31 class MCContext;
32 class MCInst;
33 class MCInstrInfo;
34 class MCSubtargetInfo;
35 
36 // Insn resources.
37 class HexagonResource {
38   // Mask of the slots or units that may execute the insn and
39   // the weight or priority that the insn requires to be assigned a slot.
40   unsigned Slots, Weight;
41 
42 public:
43   HexagonResource(unsigned s) { setUnits(s); }
44 
45   void setUnits(unsigned s) {
46     Slots = s & ((1u << HEXAGON_PACKET_SIZE) - 1);
47     setWeight(s);
48   }
49 
50   void setAllUnits() {
51     setUnits(((1u << HEXAGON_PACKET_SIZE) - 1));
52   }
53   unsigned setWeight(unsigned s);
54 
55   unsigned getUnits() const { return (Slots); }
56   unsigned getWeight() const { return (Weight); }
57 
58   // Check if the resources are in ascending slot order.
59   static bool lessUnits(const HexagonResource &A, const HexagonResource &B) {
60     return (countPopulation(A.getUnits()) < countPopulation(B.getUnits()));
61   }
62 
63   // Check if the resources are in ascending weight order.
64   static bool lessWeight(const HexagonResource &A, const HexagonResource &B) {
65     return (A.getWeight() < B.getWeight());
66   }
67 };
68 
69 // HVX insn resources.
70 class HexagonCVIResource : public HexagonResource {
71 public:
72   using UnitsAndLanes = std::pair<unsigned, unsigned>;
73 
74 private:
75   // Available HVX slots.
76   enum {
77     CVI_NONE = 0,
78     CVI_XLANE = 1 << 0,
79     CVI_SHIFT = 1 << 1,
80     CVI_MPY0 = 1 << 2,
81     CVI_MPY1 = 1 << 3,
82     CVI_ZW = 1 << 4
83   };
84 
85   // Count of adjacent slots that the insn requires to be executed.
86   unsigned Lanes;
87   // Flag whether the insn is a load or a store.
88   bool Load, Store;
89   // Flag whether the HVX resources are valid.
90   bool Valid;
91 
92   void setLanes(unsigned l) { Lanes = l; }
93   void setLoad(bool f = true) { Load = f; }
94   void setStore(bool f = true) { Store = f; }
95 
96 public:
97   HexagonCVIResource(MCInstrInfo const &MCII,
98                      MCSubtargetInfo const &STI,
99                      unsigned s, MCInst const *id);
100 
101   bool isValid() const { return Valid; }
102   unsigned getLanes() const { return Lanes; }
103   bool mayLoad() const { return Load; }
104   bool mayStore() const { return Store; }
105 };
106 
107 // Handle to an insn used by the shuffling algorithm.
108 class HexagonInstr {
109   friend class HexagonShuffler;
110 
111   MCInst const *ID;
112   MCInst const *Extender;
113   HexagonResource Core;
114   HexagonCVIResource CVI;
115 
116 public:
117   HexagonInstr(MCInstrInfo const &MCII,
118                MCSubtargetInfo const &STI, MCInst const *id,
119                MCInst const *Extender, unsigned s)
120       : ID(id), Extender(Extender), Core(s), CVI(MCII, STI, s, id){};
121 
122   MCInst const &getDesc() const { return *ID; }
123   MCInst const *getExtender() const { return Extender; }
124 
125   // Check if the handles are in ascending order for shuffling purposes.
126   bool operator<(const HexagonInstr &B) const {
127     return (HexagonResource::lessWeight(B.Core, Core));
128   }
129 
130   // Check if the handles are in ascending order by core slots.
131   static bool lessCore(const HexagonInstr &A, const HexagonInstr &B) {
132     return (HexagonResource::lessUnits(A.Core, B.Core));
133   }
134 
135   // Check if the handles are in ascending order by HVX slots.
136   static bool lessCVI(const HexagonInstr &A, const HexagonInstr &B) {
137     return (HexagonResource::lessUnits(A.CVI, B.CVI));
138   }
139 };
140 
141 // Bundle shuffler.
142 class HexagonShuffler {
143   using HexagonPacket =
144       SmallVector<HexagonInstr, HEXAGON_PRESHUFFLE_PACKET_SIZE>;
145 
146   struct HexagonPacketSummary {
147     // Number of memory operations, loads, solo loads, stores, solo stores,
148     // single stores.
149     unsigned memory;
150     unsigned loads;
151     unsigned load0;
152     unsigned stores;
153     unsigned store0;
154     unsigned store1;
155     unsigned NonZCVIloads;
156     unsigned AllCVIloads;
157     unsigned CVIstores;
158     // Number of duplex insns
159     unsigned duplex;
160     unsigned pSlot3Cnt;
161     Optional<HexagonInstr *> PrefSlot3Inst;
162     unsigned memops;
163     unsigned ReservedSlotMask;
164     SmallVector<HexagonInstr *, HEXAGON_PRESHUFFLE_PACKET_SIZE> branchInsts;
165     Optional<SMLoc> Slot1AOKLoc;
166     Optional<SMLoc> NoSlot1StoreLoc;
167   };
168   // Insn handles in a bundle.
169   HexagonPacket Packet;
170 
171 protected:
172   MCContext &Context;
173   int64_t BundleFlags;
174   MCInstrInfo const &MCII;
175   MCSubtargetInfo const &STI;
176   SMLoc Loc;
177   bool ReportErrors;
178   bool CheckFailure;
179   std::vector<std::pair<SMLoc, std::string>> AppliedRestrictions;
180   bool applySlotRestrictions(HexagonPacketSummary const &Summary);
181   void restrictSlot1AOK(HexagonPacketSummary const &Summary);
182   void restrictNoSlot1Store(HexagonPacketSummary const &Summary);
183   void restrictNoSlot1();
184   bool restrictStoreLoadOrder(HexagonPacketSummary const &Summary);
185   void restrictBranchOrder(HexagonPacketSummary const &Summary);
186   void restrictPreferSlot3(HexagonPacketSummary const &Summary);
187   void permitNonSlot();
188 
189   Optional<HexagonPacket> tryAuction(HexagonPacketSummary const &Summary) const;
190 
191   HexagonPacketSummary GetPacketSummary();
192   bool ValidPacketMemoryOps(HexagonPacketSummary const &Summary) const;
193   bool ValidResourceUsage(HexagonPacketSummary const &Summary);
194   bool validPacketInsts() const;
195 
196 public:
197   using iterator = HexagonPacket::iterator;
198   using const_iterator = HexagonPacket::const_iterator;
199   using packet_range = iterator_range<HexagonPacket::iterator>;
200   using const_packet_range = iterator_range<HexagonPacket::const_iterator>;
201 
202   HexagonShuffler(MCContext &Context, bool ReportErrors,
203                   MCInstrInfo const &MCII, MCSubtargetInfo const &STI);
204 
205   // Reset to initial state.
206   void reset();
207   // Check if the bundle may be validly shuffled.
208   bool check();
209   // Reorder the insn handles in the bundle.
210   bool shuffle();
211 
212   unsigned size() const { return (Packet.size()); }
213 
214   bool isMemReorderDisabled() const {
215     return (BundleFlags & HexagonMCInstrInfo::memReorderDisabledMask) != 0;
216   }
217 
218   iterator begin() { return (Packet.begin()); }
219   iterator end() { return (Packet.end()); }
220   const_iterator cbegin() const { return (Packet.begin()); }
221   const_iterator cend() const { return (Packet.end()); }
222   packet_range insts(HexagonPacket &P) {
223     return make_range(P.begin(), P.end());
224   }
225   const_packet_range insts(HexagonPacket const &P) const {
226     return make_range(P.begin(), P.end());
227   }
228   packet_range insts() { return make_range(begin(), end()); }
229   const_packet_range insts() const { return make_range(cbegin(), cend()); }
230 
231   using InstPredicate = bool (*)(MCInstrInfo const &, MCInst const &);
232 
233   bool HasInstWith(InstPredicate Pred) const {
234     return llvm::any_of(insts(), [&](HexagonInstr const &I) {
235       MCInst const &Inst = I.getDesc();
236       return (*Pred)(MCII, Inst);
237     });
238   }
239 
240   // Add insn handle to the bundle .
241   void append(MCInst const &ID, MCInst const *Extender, unsigned S);
242 
243   // Return the error code for the last check or shuffling of the bundle.
244   void reportError(Twine const &Msg);
245 };
246 
247 } // end namespace llvm
248 
249 #endif //  LLVM_LIB_TARGET_HEXAGON_MCTARGETDESC_HEXAGONSHUFFLER_H
250