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