1//===- llvm/CodeGen/GlobalISel/LegacyLegalizerInfo.h ------------*- 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/// \file
9/// Interface for Targets to specify which operations they can successfully
10/// select and how the others should be expanded most efficiently.
11/// This implementation has been deprecated for a long time but it still in use
12/// in a few places.
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CODEGEN_GLOBALISEL_LEGACYLEGALIZERINFO_H
16#define LLVM_CODEGEN_GLOBALISEL_LEGACYLEGALIZERINFO_H
17
18#include "llvm/ADT/DenseMap.h"
19#include "llvm/CodeGen/TargetOpcodes.h"
20#include "llvm/CodeGenTypes/LowLevelType.h"
21#include <unordered_map>
22#include <vector>
23
24namespace llvm {
25struct LegalityQuery;
26
27namespace LegacyLegalizeActions {
28enum LegacyLegalizeAction : std::uint8_t {
29 /// The operation is expected to be selectable directly by the target, and
30 /// no transformation is necessary.
31 Legal,
32
33 /// The operation should be synthesized from multiple instructions acting on
34 /// a narrower scalar base-type. For example a 64-bit add might be
35 /// implemented in terms of 32-bit add-with-carry.
36 NarrowScalar,
37
38 /// The operation should be implemented in terms of a wider scalar
39 /// base-type. For example a <2 x s8> add could be implemented as a <2
40 /// x s32> add (ignoring the high bits).
41 WidenScalar,
42
43 /// The (vector) operation should be implemented by splitting it into
44 /// sub-vectors where the operation is legal. For example a <8 x s64> add
45 /// might be implemented as 4 separate <2 x s64> adds.
46 FewerElements,
47
48 /// The (vector) operation should be implemented by widening the input
49 /// vector and ignoring the lanes added by doing so. For example <2 x i8> is
50 /// rarely legal, but you might perform an <8 x i8> and then only look at
51 /// the first two results.
52 MoreElements,
53
54 /// Perform the operation on a different, but equivalently sized type.
55 Bitcast,
56
57 /// The operation itself must be expressed in terms of simpler actions on
58 /// this target. E.g. a SREM replaced by an SDIV and subtraction.
59 Lower,
60
61 /// The operation should be implemented as a call to some kind of runtime
62 /// support library. For example this usually happens on machines that don't
63 /// support floating-point operations natively.
64 Libcall,
65
66 /// The target wants to do something special with this combination of
67 /// operand and type. A callback will be issued when it is needed.
68 Custom,
69
70 /// This operation is completely unsupported on the target. A programming
71 /// error has occurred.
72 Unsupported,
73
74 /// Sentinel value for when no action was found in the specified table.
75 NotFound,
76};
77} // end namespace LegacyLegalizeActions
78raw_ostream &operator<<(raw_ostream &OS,
79 LegacyLegalizeActions::LegacyLegalizeAction Action);
80
81/// Legalization is decided based on an instruction's opcode, which type slot
82/// we're considering, and what the existing type is. These aspects are gathered
83/// together for convenience in the InstrAspect class.
84struct InstrAspect {
85 unsigned Opcode;
86 unsigned Idx = 0;
87 LLT Type;
88
89 InstrAspect(unsigned Opcode, LLT Type) : Opcode(Opcode), Type(Type) {}
90 InstrAspect(unsigned Opcode, unsigned Idx, LLT Type)
91 : Opcode(Opcode), Idx(Idx), Type(Type) {}
92
93 bool operator==(const InstrAspect &RHS) const {
94 return Opcode == RHS.Opcode && Idx == RHS.Idx && Type == RHS.Type;
95 }
96};
97
98/// The result of a query. It either indicates a final answer of Legal or
99/// Unsupported or describes an action that must be taken to make an operation
100/// more legal.
101struct LegacyLegalizeActionStep {
102 /// The action to take or the final answer.
103 LegacyLegalizeActions::LegacyLegalizeAction Action;
104 /// If describing an action, the type index to change. Otherwise zero.
105 unsigned TypeIdx;
106 /// If describing an action, the new type for TypeIdx. Otherwise LLT{}.
107 LLT NewType;
108
109 LegacyLegalizeActionStep(LegacyLegalizeActions::LegacyLegalizeAction Action,
110 unsigned TypeIdx, const LLT NewType)
111 : Action(Action), TypeIdx(TypeIdx), NewType(NewType) {}
112
113 bool operator==(const LegacyLegalizeActionStep &RHS) const {
114 return std::tie(args: Action, args: TypeIdx, args: NewType) ==
115 std::tie(args: RHS.Action, args: RHS.TypeIdx, args: RHS.NewType);
116 }
117};
118
119
120class LegacyLegalizerInfo {
121public:
122 using SizeAndAction =
123 std::pair<uint16_t, LegacyLegalizeActions::LegacyLegalizeAction>;
124 using SizeAndActionsVec = std::vector<SizeAndAction>;
125 using SizeChangeStrategy =
126 std::function<SizeAndActionsVec(const SizeAndActionsVec &v)>;
127
128 LegacyLegalizerInfo();
129
130 static bool needsLegalizingToDifferentSize(
131 const LegacyLegalizeActions::LegacyLegalizeAction Action) {
132 using namespace LegacyLegalizeActions;
133 switch (Action) {
134 case NarrowScalar:
135 case WidenScalar:
136 case FewerElements:
137 case MoreElements:
138 case Unsupported:
139 return true;
140 default:
141 return false;
142 }
143 }
144
145 /// Compute any ancillary tables needed to quickly decide how an operation
146 /// should be handled. This must be called after all "set*Action"methods but
147 /// before any query is made or incorrect results may be returned.
148 void computeTables();
149
150 /// More friendly way to set an action for common types that have an LLT
151 /// representation.
152 /// The LegacyLegalizeAction must be one for which
153 /// NeedsLegalizingToDifferentSize returns false.
154 void setAction(const InstrAspect &Aspect,
155 LegacyLegalizeActions::LegacyLegalizeAction Action) {
156 assert(!needsLegalizingToDifferentSize(Action));
157 TablesInitialized = false;
158 const unsigned OpcodeIdx = Aspect.Opcode - FirstOp;
159 if (SpecifiedActions[OpcodeIdx].size() <= Aspect.Idx)
160 SpecifiedActions[OpcodeIdx].resize(N: Aspect.Idx + 1);
161 SpecifiedActions[OpcodeIdx][Aspect.Idx][Aspect.Type] = Action;
162 }
163
164 /// The setAction calls record the non-size-changing legalization actions
165 /// to take on specificly-sized types. The SizeChangeStrategy defines what
166 /// to do when the size of the type needs to be changed to reach a legally
167 /// sized type (i.e., one that was defined through a setAction call).
168 /// e.g.
169 /// setAction ({G_ADD, 0, LLT::scalar(32)}, Legal);
170 /// setLegalizeScalarToDifferentSizeStrategy(
171 /// G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
172 /// will end up defining getAction({G_ADD, 0, T}) to return the following
173 /// actions for different scalar types T:
174 /// LLT::scalar(1)..LLT::scalar(31): {WidenScalar, 0, LLT::scalar(32)}
175 /// LLT::scalar(32): {Legal, 0, LLT::scalar(32)}
176 /// LLT::scalar(33)..: {NarrowScalar, 0, LLT::scalar(32)}
177 ///
178 /// If no SizeChangeAction gets defined, through this function,
179 /// the default is unsupportedForDifferentSizes.
180 void setLegalizeScalarToDifferentSizeStrategy(const unsigned Opcode,
181 const unsigned TypeIdx,
182 SizeChangeStrategy S) {
183 const unsigned OpcodeIdx = Opcode - FirstOp;
184 if (ScalarSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
185 ScalarSizeChangeStrategies[OpcodeIdx].resize(N: TypeIdx + 1);
186 ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
187 }
188
189 /// See also setLegalizeScalarToDifferentSizeStrategy.
190 /// This function allows to set the SizeChangeStrategy for vector elements.
191 void setLegalizeVectorElementToDifferentSizeStrategy(const unsigned Opcode,
192 const unsigned TypeIdx,
193 SizeChangeStrategy S) {
194 const unsigned OpcodeIdx = Opcode - FirstOp;
195 if (VectorElementSizeChangeStrategies[OpcodeIdx].size() <= TypeIdx)
196 VectorElementSizeChangeStrategies[OpcodeIdx].resize(N: TypeIdx + 1);
197 VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] = S;
198 }
199
200 /// A SizeChangeStrategy for the common case where legalization for a
201 /// particular operation consists of only supporting a specific set of type
202 /// sizes. E.g.
203 /// setAction ({G_DIV, 0, LLT::scalar(32)}, Legal);
204 /// setAction ({G_DIV, 0, LLT::scalar(64)}, Legal);
205 /// setLegalizeScalarToDifferentSizeStrategy(
206 /// G_DIV, 0, unsupportedForDifferentSizes);
207 /// will result in getAction({G_DIV, 0, T}) to return Legal for s32 and s64,
208 /// and Unsupported for all other scalar types T.
209 static SizeAndActionsVec
210 unsupportedForDifferentSizes(const SizeAndActionsVec &v) {
211 using namespace LegacyLegalizeActions;
212 return increaseToLargerTypesAndDecreaseToLargest(v, IncreaseAction: Unsupported,
213 DecreaseAction: Unsupported);
214 }
215
216 /// A SizeChangeStrategy for the common case where legalization for a
217 /// particular operation consists of widening the type to a large legal type,
218 /// unless there is no such type and then instead it should be narrowed to the
219 /// largest legal type.
220 static SizeAndActionsVec
221 widenToLargerTypesAndNarrowToLargest(const SizeAndActionsVec &v) {
222 using namespace LegacyLegalizeActions;
223 assert(v.size() > 0 &&
224 "At least one size that can be legalized towards is needed"
225 " for this SizeChangeStrategy");
226 return increaseToLargerTypesAndDecreaseToLargest(v, IncreaseAction: WidenScalar,
227 DecreaseAction: NarrowScalar);
228 }
229
230 static SizeAndActionsVec
231 widenToLargerTypesUnsupportedOtherwise(const SizeAndActionsVec &v) {
232 using namespace LegacyLegalizeActions;
233 return increaseToLargerTypesAndDecreaseToLargest(v, IncreaseAction: WidenScalar,
234 DecreaseAction: Unsupported);
235 }
236
237 static SizeAndActionsVec
238 narrowToSmallerAndUnsupportedIfTooSmall(const SizeAndActionsVec &v) {
239 using namespace LegacyLegalizeActions;
240 return decreaseToSmallerTypesAndIncreaseToSmallest(v, DecreaseAction: NarrowScalar,
241 IncreaseAction: Unsupported);
242 }
243
244 /// A SizeChangeStrategy for the common case where legalization for a
245 /// particular vector operation consists of having more elements in the
246 /// vector, to a type that is legal. Unless there is no such type and then
247 /// instead it should be legalized towards the widest vector that's still
248 /// legal. E.g.
249 /// setAction({G_ADD, LLT::vector(8, 8)}, Legal);
250 /// setAction({G_ADD, LLT::vector(16, 8)}, Legal);
251 /// setAction({G_ADD, LLT::vector(2, 32)}, Legal);
252 /// setAction({G_ADD, LLT::vector(4, 32)}, Legal);
253 /// setLegalizeVectorElementToDifferentSizeStrategy(
254 /// G_ADD, 0, moreToWiderTypesAndLessToWidest);
255 /// will result in the following getAction results:
256 /// * getAction({G_ADD, LLT::vector(8,8)}) returns
257 /// (Legal, vector(8,8)).
258 /// * getAction({G_ADD, LLT::vector(9,8)}) returns
259 /// (MoreElements, vector(16,8)).
260 /// * getAction({G_ADD, LLT::vector(8,32)}) returns
261 /// (FewerElements, vector(4,32)).
262 static SizeAndActionsVec
263 moreToWiderTypesAndLessToWidest(const SizeAndActionsVec &v) {
264 using namespace LegacyLegalizeActions;
265 return increaseToLargerTypesAndDecreaseToLargest(v, IncreaseAction: MoreElements,
266 DecreaseAction: FewerElements);
267 }
268
269 /// Helper function to implement many typical SizeChangeStrategy functions.
270 static SizeAndActionsVec increaseToLargerTypesAndDecreaseToLargest(
271 const SizeAndActionsVec &v,
272 LegacyLegalizeActions::LegacyLegalizeAction IncreaseAction,
273 LegacyLegalizeActions::LegacyLegalizeAction DecreaseAction);
274 /// Helper function to implement many typical SizeChangeStrategy functions.
275 static SizeAndActionsVec decreaseToSmallerTypesAndIncreaseToSmallest(
276 const SizeAndActionsVec &v,
277 LegacyLegalizeActions::LegacyLegalizeAction DecreaseAction,
278 LegacyLegalizeActions::LegacyLegalizeAction IncreaseAction);
279
280 LegacyLegalizeActionStep getAction(const LegalityQuery &Query) const;
281
282 unsigned getOpcodeIdxForOpcode(unsigned Opcode) const;
283
284private:
285 /// Determine what action should be taken to legalize the given generic
286 /// instruction opcode, type-index and type. Requires computeTables to have
287 /// been called.
288 ///
289 /// \returns a pair consisting of the kind of legalization that should be
290 /// performed and the destination type.
291 std::pair<LegacyLegalizeActions::LegacyLegalizeAction, LLT>
292 getAspectAction(const InstrAspect &Aspect) const;
293
294 /// The SizeAndActionsVec is a representation mapping between all natural
295 /// numbers and an Action. The natural number represents the bit size of
296 /// the InstrAspect. For example, for a target with native support for 32-bit
297 /// and 64-bit additions, you'd express that as:
298 /// setScalarAction(G_ADD, 0,
299 /// {{1, WidenScalar}, // bit sizes [ 1, 31[
300 /// {32, Legal}, // bit sizes [32, 33[
301 /// {33, WidenScalar}, // bit sizes [33, 64[
302 /// {64, Legal}, // bit sizes [64, 65[
303 /// {65, NarrowScalar} // bit sizes [65, +inf[
304 /// });
305 /// It may be that only 64-bit pointers are supported on your target:
306 /// setPointerAction(G_PTR_ADD, 0, LLT:pointer(1),
307 /// {{1, Unsupported}, // bit sizes [ 1, 63[
308 /// {64, Legal}, // bit sizes [64, 65[
309 /// {65, Unsupported}, // bit sizes [65, +inf[
310 /// });
311 void setScalarAction(const unsigned Opcode, const unsigned TypeIndex,
312 const SizeAndActionsVec &SizeAndActions) {
313 const unsigned OpcodeIdx = Opcode - FirstOp;
314 SmallVector<SizeAndActionsVec, 1> &Actions = ScalarActions[OpcodeIdx];
315 setActions(TypeIndex, Actions, SizeAndActions);
316 }
317 void setPointerAction(const unsigned Opcode, const unsigned TypeIndex,
318 const unsigned AddressSpace,
319 const SizeAndActionsVec &SizeAndActions) {
320 const unsigned OpcodeIdx = Opcode - FirstOp;
321 if (AddrSpace2PointerActions[OpcodeIdx].find(x: AddressSpace) ==
322 AddrSpace2PointerActions[OpcodeIdx].end())
323 AddrSpace2PointerActions[OpcodeIdx][AddressSpace] = {{}};
324 SmallVector<SizeAndActionsVec, 1> &Actions =
325 AddrSpace2PointerActions[OpcodeIdx].find(x: AddressSpace)->second;
326 setActions(TypeIndex, Actions, SizeAndActions);
327 }
328
329 /// If an operation on a given vector type (say <M x iN>) isn't explicitly
330 /// specified, we proceed in 2 stages. First we legalize the underlying scalar
331 /// (so that there's at least one legal vector with that scalar), then we
332 /// adjust the number of elements in the vector so that it is legal. The
333 /// desired action in the first step is controlled by this function.
334 void setScalarInVectorAction(const unsigned Opcode, const unsigned TypeIndex,
335 const SizeAndActionsVec &SizeAndActions) {
336 unsigned OpcodeIdx = Opcode - FirstOp;
337 SmallVector<SizeAndActionsVec, 1> &Actions =
338 ScalarInVectorActions[OpcodeIdx];
339 setActions(TypeIndex, Actions, SizeAndActions);
340 }
341
342 /// See also setScalarInVectorAction.
343 /// This function let's you specify the number of elements in a vector that
344 /// are legal for a legal element size.
345 void setVectorNumElementAction(const unsigned Opcode,
346 const unsigned TypeIndex,
347 const unsigned ElementSize,
348 const SizeAndActionsVec &SizeAndActions) {
349 const unsigned OpcodeIdx = Opcode - FirstOp;
350 if (NumElements2Actions[OpcodeIdx].find(x: ElementSize) ==
351 NumElements2Actions[OpcodeIdx].end())
352 NumElements2Actions[OpcodeIdx][ElementSize] = {{}};
353 SmallVector<SizeAndActionsVec, 1> &Actions =
354 NumElements2Actions[OpcodeIdx].find(x: ElementSize)->second;
355 setActions(TypeIndex, Actions, SizeAndActions);
356 }
357
358 /// A partial SizeAndActionsVec potentially doesn't cover all bit sizes,
359 /// i.e. it's OK if it doesn't start from size 1.
360 static void checkPartialSizeAndActionsVector(const SizeAndActionsVec& v) {
361 using namespace LegacyLegalizeActions;
362#ifndef NDEBUG
363 // The sizes should be in increasing order
364 int prev_size = -1;
365 for(auto SizeAndAction: v) {
366 assert(SizeAndAction.first > prev_size);
367 prev_size = SizeAndAction.first;
368 }
369 // - for every Widen action, there should be a larger bitsize that
370 // can be legalized towards (e.g. Legal, Lower, Libcall or Custom
371 // action).
372 // - for every Narrow action, there should be a smaller bitsize that
373 // can be legalized towards.
374 int SmallestNarrowIdx = -1;
375 int LargestWidenIdx = -1;
376 int SmallestLegalizableToSameSizeIdx = -1;
377 int LargestLegalizableToSameSizeIdx = -1;
378 for(size_t i=0; i<v.size(); ++i) {
379 switch (v[i].second) {
380 case FewerElements:
381 case NarrowScalar:
382 if (SmallestNarrowIdx == -1)
383 SmallestNarrowIdx = i;
384 break;
385 case WidenScalar:
386 case MoreElements:
387 LargestWidenIdx = i;
388 break;
389 case Unsupported:
390 break;
391 default:
392 if (SmallestLegalizableToSameSizeIdx == -1)
393 SmallestLegalizableToSameSizeIdx = i;
394 LargestLegalizableToSameSizeIdx = i;
395 }
396 }
397 if (SmallestNarrowIdx != -1) {
398 assert(SmallestLegalizableToSameSizeIdx != -1);
399 assert(SmallestNarrowIdx > SmallestLegalizableToSameSizeIdx);
400 }
401 if (LargestWidenIdx != -1)
402 assert(LargestWidenIdx < LargestLegalizableToSameSizeIdx);
403#endif
404 }
405
406 /// A full SizeAndActionsVec must cover all bit sizes, i.e. must start with
407 /// from size 1.
408 static void checkFullSizeAndActionsVector(const SizeAndActionsVec& v) {
409#ifndef NDEBUG
410 // Data structure invariant: The first bit size must be size 1.
411 assert(v.size() >= 1);
412 assert(v[0].first == 1);
413 checkPartialSizeAndActionsVector(v);
414#endif
415 }
416
417 /// Sets actions for all bit sizes on a particular generic opcode, type
418 /// index and scalar or pointer type.
419 void setActions(unsigned TypeIndex,
420 SmallVector<SizeAndActionsVec, 1> &Actions,
421 const SizeAndActionsVec &SizeAndActions) {
422 checkFullSizeAndActionsVector(v: SizeAndActions);
423 if (Actions.size() <= TypeIndex)
424 Actions.resize(N: TypeIndex + 1);
425 Actions[TypeIndex] = SizeAndActions;
426 }
427
428 static SizeAndAction findAction(const SizeAndActionsVec &Vec,
429 const uint32_t Size);
430
431 /// Returns the next action needed to get the scalar or pointer type closer
432 /// to being legal
433 /// E.g. findLegalAction({G_REM, 13}) should return
434 /// (WidenScalar, 32). After that, findLegalAction({G_REM, 32}) will
435 /// probably be called, which should return (Lower, 32).
436 /// This is assuming the setScalarAction on G_REM was something like:
437 /// setScalarAction(G_REM, 0,
438 /// {{1, WidenScalar}, // bit sizes [ 1, 31[
439 /// {32, Lower}, // bit sizes [32, 33[
440 /// {33, NarrowScalar} // bit sizes [65, +inf[
441 /// });
442 std::pair<LegacyLegalizeActions::LegacyLegalizeAction, LLT>
443 findScalarLegalAction(const InstrAspect &Aspect) const;
444
445 /// Returns the next action needed towards legalizing the vector type.
446 std::pair<LegacyLegalizeActions::LegacyLegalizeAction, LLT>
447 findVectorLegalAction(const InstrAspect &Aspect) const;
448
449 static const int FirstOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_START;
450 static const int LastOp = TargetOpcode::PRE_ISEL_GENERIC_OPCODE_END;
451
452 // Data structures used temporarily during construction of legality data:
453 using TypeMap = DenseMap<LLT, LegacyLegalizeActions::LegacyLegalizeAction>;
454 SmallVector<TypeMap, 1> SpecifiedActions[LastOp - FirstOp + 1];
455 SmallVector<SizeChangeStrategy, 1>
456 ScalarSizeChangeStrategies[LastOp - FirstOp + 1];
457 SmallVector<SizeChangeStrategy, 1>
458 VectorElementSizeChangeStrategies[LastOp - FirstOp + 1];
459 bool TablesInitialized = false;
460
461 // Data structures used by getAction:
462 SmallVector<SizeAndActionsVec, 1> ScalarActions[LastOp - FirstOp + 1];
463 SmallVector<SizeAndActionsVec, 1> ScalarInVectorActions[LastOp - FirstOp + 1];
464 std::unordered_map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
465 AddrSpace2PointerActions[LastOp - FirstOp + 1];
466 std::unordered_map<uint16_t, SmallVector<SizeAndActionsVec, 1>>
467 NumElements2Actions[LastOp - FirstOp + 1];
468};
469
470} // end namespace llvm
471
472#endif // LLVM_CODEGEN_GLOBALISEL_LEGACYLEGALIZERINFO_H
473

source code of llvm/include/llvm/CodeGen/GlobalISel/LegacyLegalizerInfo.h