Line data Source code
1 : //===- lib/CodeGen/GlobalISel/LegalizerInfo.cpp - Legalizer ---------------===//
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 : // Implement an interface to specify and query how an illegal operation on a
11 : // given type should be expanded.
12 : //
13 : // Issues to be resolved:
14 : // + Make it fast.
15 : // + Support weird types like i3, <7 x i3>, ...
16 : // + Operations with more than one type (ICMP, CMPXCHG, intrinsics, ...)
17 : //
18 : //===----------------------------------------------------------------------===//
19 :
20 : #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
21 : #include "llvm/ADT/SmallBitVector.h"
22 : #include "llvm/CodeGen/MachineInstr.h"
23 : #include "llvm/CodeGen/MachineOperand.h"
24 : #include "llvm/CodeGen/MachineRegisterInfo.h"
25 : #include "llvm/CodeGen/TargetOpcodes.h"
26 : #include "llvm/MC/MCInstrDesc.h"
27 : #include "llvm/MC/MCInstrInfo.h"
28 : #include "llvm/Support/Debug.h"
29 : #include "llvm/Support/ErrorHandling.h"
30 : #include "llvm/Support/LowLevelTypeImpl.h"
31 : #include "llvm/Support/MathExtras.h"
32 : #include <algorithm>
33 : #include <map>
34 :
35 : using namespace llvm;
36 : using namespace LegalizeActions;
37 :
38 : #define DEBUG_TYPE "legalizer-info"
39 :
40 : cl::opt<bool> llvm::DisableGISelLegalityCheck(
41 : "disable-gisel-legality-check",
42 : cl::desc("Don't verify that MIR is fully legal between GlobalISel passes"),
43 : cl::Hidden);
44 :
45 0 : raw_ostream &LegalityQuery::print(raw_ostream &OS) const {
46 0 : OS << Opcode << ", Tys={";
47 0 : for (const auto &Type : Types) {
48 0 : OS << Type << ", ";
49 : }
50 0 : OS << "}, Opcode=";
51 :
52 0 : OS << Opcode << ", MMOs={";
53 0 : for (const auto &MMODescr : MMODescrs) {
54 0 : OS << MMODescr.Size << ", ";
55 : }
56 0 : OS << "}";
57 :
58 0 : return OS;
59 : }
60 :
61 6774 : LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const {
62 : LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
63 : dbgs() << "\n");
64 6774 : if (Rules.empty()) {
65 : LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
66 2324 : return {LegalizeAction::UseLegacyRules, 0, LLT{}};
67 : }
68 5042 : for (const auto &Rule : Rules) {
69 5039 : if (Rule.match(Query)) {
70 : LLVM_DEBUG(dbgs() << ".. match\n");
71 4447 : std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
72 : LLVM_DEBUG(dbgs() << ".. .. " << (unsigned)Rule.getAction() << ", "
73 : << Mutation.first << ", " << Mutation.second << "\n");
74 : assert((Query.Types[Mutation.first] != Mutation.second ||
75 : Rule.getAction() == Lower ||
76 : Rule.getAction() == MoreElements ||
77 : Rule.getAction() == FewerElements) &&
78 : "Simple loop detected");
79 8894 : return {Rule.getAction(), Mutation.first, Mutation.second};
80 : } else
81 : LLVM_DEBUG(dbgs() << ".. no match\n");
82 : }
83 : LLVM_DEBUG(dbgs() << ".. unsupported\n");
84 3 : return {LegalizeAction::Unsupported, 0, LLT{}};
85 : }
86 :
87 0 : bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const {
88 : #ifndef NDEBUG
89 : if (Rules.empty()) {
90 : LLVM_DEBUG(
91 : dbgs() << ".. type index coverage check SKIPPED: no rules defined\n");
92 : return true;
93 : }
94 : const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset();
95 : if (FirstUncovered < 0) {
96 : LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:"
97 : " user-defined predicate detected\n");
98 : return true;
99 : }
100 : const bool AllCovered = (FirstUncovered >= NumTypeIdxs);
101 : LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered
102 : << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
103 : return AllCovered;
104 : #else
105 0 : return true;
106 : #endif
107 : }
108 :
109 29468098 : LegalizerInfo::LegalizerInfo() : TablesInitialized(false) {
110 : // Set defaults.
111 : // FIXME: these two (G_ANYEXT and G_TRUNC?) can be legalized to the
112 : // fundamental load/store Jakob proposed. Once loads & stores are supported.
113 35720 : setScalarAction(TargetOpcode::G_ANYEXT, 1, {{1, Legal}});
114 35720 : setScalarAction(TargetOpcode::G_ZEXT, 1, {{1, Legal}});
115 35720 : setScalarAction(TargetOpcode::G_SEXT, 1, {{1, Legal}});
116 35720 : setScalarAction(TargetOpcode::G_TRUNC, 0, {{1, Legal}});
117 35720 : setScalarAction(TargetOpcode::G_TRUNC, 1, {{1, Legal}});
118 :
119 35720 : setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}});
120 35720 : setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}});
121 :
122 71440 : setLegalizeScalarToDifferentSizeStrategy(
123 : TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall);
124 71440 : setLegalizeScalarToDifferentSizeStrategy(
125 : TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
126 71440 : setLegalizeScalarToDifferentSizeStrategy(
127 : TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest);
128 71440 : setLegalizeScalarToDifferentSizeStrategy(
129 : TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
130 71440 : setLegalizeScalarToDifferentSizeStrategy(
131 : TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
132 :
133 71440 : setLegalizeScalarToDifferentSizeStrategy(
134 : TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
135 71440 : setLegalizeScalarToDifferentSizeStrategy(
136 : TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
137 71440 : setLegalizeScalarToDifferentSizeStrategy(
138 : TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
139 71440 : setLegalizeScalarToDifferentSizeStrategy(
140 : TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
141 35720 : setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}});
142 35720 : }
143 :
144 35720 : void LegalizerInfo::computeTables() {
145 : assert(TablesInitialized == false);
146 :
147 3714880 : for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) {
148 3679160 : const unsigned Opcode = FirstOp + OpcodeIdx;
149 4381081 : for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size();
150 : ++TypeIdx) {
151 : // 0. Collect information specified through the setAction API, i.e.
152 : // for specific bit sizes.
153 : // For scalar types:
154 : SizeAndActionsVec ScalarSpecifiedActions;
155 : // For pointer types:
156 : std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions;
157 : // For vector types:
158 : std::map<uint16_t, SizeAndActionsVec> ElemSize2SpecifiedActions;
159 4092358 : for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) {
160 2688516 : const LLT Type = LLT2Action.first;
161 : const LegalizeAction Action = LLT2Action.second;
162 :
163 2688516 : auto SizeAction = std::make_pair(Type.getSizeInBits(), Action);
164 2688516 : if (Type.isPointer())
165 383148 : AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(
166 : SizeAction);
167 1661490 : else if (Type.isVector())
168 835452 : ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()]
169 835452 : .push_back(SizeAction);
170 : else
171 1661491 : ScalarSpecifiedActions.push_back(SizeAction);
172 : }
173 :
174 : // 1. Handle scalar types
175 : {
176 : // Decide how to handle bit sizes for which no explicit specification
177 : // was given.
178 : SizeChangeStrategy S = &unsupportedForDifferentSizes;
179 701921 : if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() &&
180 : ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
181 235562 : S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx];
182 : llvm::sort(ScalarSpecifiedActions.begin(),
183 : ScalarSpecifiedActions.end());
184 : checkPartialSizeAndActionsVector(ScalarSpecifiedActions);
185 701921 : setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions));
186 : }
187 :
188 : // 2. Handle pointer types
189 893495 : for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) {
190 : llvm::sort(PointerSpecifiedActions.second.begin(),
191 : PointerSpecifiedActions.second.end());
192 : checkPartialSizeAndActionsVector(PointerSpecifiedActions.second);
193 : // For pointer types, we assume that there isn't a meaningfull way
194 : // to change the number of bits used in the pointer.
195 191574 : setPointerAction(
196 191574 : Opcode, TypeIdx, PointerSpecifiedActions.first,
197 191574 : unsupportedForDifferentSizes(PointerSpecifiedActions.second));
198 : }
199 :
200 : // 3. Handle vector types
201 : SizeAndActionsVec ElementSizesSeen;
202 1306480 : for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) {
203 : llvm::sort(VectorSpecifiedActions.second.begin(),
204 : VectorSpecifiedActions.second.end());
205 604559 : const uint16_t ElementSize = VectorSpecifiedActions.first;
206 604559 : ElementSizesSeen.push_back({ElementSize, Legal});
207 : checkPartialSizeAndActionsVector(VectorSpecifiedActions.second);
208 : // For vector types, we assume that the best way to adapt the number
209 : // of elements is to the next larger number of elements type for which
210 : // the vector type is legal, unless there is no such type. In that case,
211 : // legalize towards a vector type with a smaller number of elements.
212 : SizeAndActionsVec NumElementsActions;
213 1440011 : for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) {
214 : assert(BitsizeAndAction.first % ElementSize == 0);
215 835452 : const uint16_t NumElements = BitsizeAndAction.first / ElementSize;
216 835452 : NumElementsActions.push_back({NumElements, BitsizeAndAction.second});
217 : }
218 604559 : setVectorNumElementAction(
219 : Opcode, TypeIdx, ElementSize,
220 604558 : moreToWiderTypesAndLessToWidest(NumElementsActions));
221 : }
222 : llvm::sort(ElementSizesSeen);
223 : SizeChangeStrategy VectorElementSizeChangeStrategy =
224 : &unsupportedForDifferentSizes;
225 701921 : if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() &&
226 : VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
227 : VectorElementSizeChangeStrategy =
228 1 : VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx];
229 : setScalarInVectorAction(
230 701921 : Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen));
231 : }
232 : }
233 :
234 35720 : TablesInitialized = true;
235 35720 : }
236 :
237 : // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
238 : // probably going to need specialized lookup structures for various types before
239 : // we have any hope of doing well with something like <13 x i3>. Even the common
240 : // cases should do better than what we have now.
241 : std::pair<LegalizeAction, LLT>
242 3381 : LegalizerInfo::getAspectAction(const InstrAspect &Aspect) const {
243 : assert(TablesInitialized && "backend forgot to call computeTables");
244 : // These *have* to be implemented for now, they're the fundamental basis of
245 : // how everything else is transformed.
246 3950 : if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
247 2960 : return findScalarLegalAction(Aspect);
248 : assert(Aspect.Type.isVector());
249 421 : return findVectorLegalAction(Aspect);
250 : }
251 :
252 : /// Helper function to get LLT for the given type index.
253 8599 : static LLT getTypeFromTypeIdx(const MachineInstr &MI,
254 : const MachineRegisterInfo &MRI, unsigned OpIdx,
255 : unsigned TypeIdx) {
256 : assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
257 : // G_UNMERGE_VALUES has variable number of operands, but there is only
258 : // one source type and one destination type as all destinations must be the
259 : // same type. So, get the last operand if TypeIdx == 1.
260 17198 : if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
261 160 : return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
262 17038 : return MRI.getType(MI.getOperand(OpIdx).getReg());
263 : }
264 :
265 692236 : unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
266 : assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
267 692236 : return Opcode - FirstOp;
268 : }
269 :
270 391620 : unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
271 391620 : unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
272 391619 : if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
273 : LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
274 : << "\n");
275 1226 : OpcodeIdx = getOpcodeIdxForOpcode(Alias);
276 : LLVM_DEBUG(dbgs() << ".. opcode " << Alias << " is aliased to "
277 : << RulesForOpcode[OpcodeIdx].getAlias() << "\n");
278 : assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
279 : }
280 :
281 391619 : return OpcodeIdx;
282 : }
283 :
284 : const LegalizeRuleSet &
285 6774 : LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
286 6774 : unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
287 6774 : return RulesForOpcode[OpcodeIdx];
288 : }
289 :
290 384846 : LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) {
291 384846 : unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
292 384846 : auto &Result = RulesForOpcode[OpcodeIdx];
293 : assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
294 384846 : return Result;
295 : }
296 :
297 106204 : LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(
298 : std::initializer_list<unsigned> Opcodes) {
299 106204 : unsigned Representative = *Opcodes.begin();
300 :
301 : assert(Opcodes.begin() != Opcodes.end() &&
302 : Opcodes.begin() + 1 != Opcodes.end() &&
303 : "Initializer list must have at least two opcodes");
304 :
305 402214 : for (auto I = Opcodes.begin() + 1, E = Opcodes.end(); I != E; ++I)
306 296010 : aliasActionDefinitions(Representative, *I);
307 :
308 106204 : auto &Return = getActionDefinitionsBuilder(Representative);
309 : Return.setIsAliasedByAnother();
310 106204 : return Return;
311 : }
312 :
313 296010 : void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo,
314 : unsigned OpcodeFrom) {
315 : assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
316 : assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
317 296010 : const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
318 296010 : RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
319 296010 : }
320 :
321 : LegalizeActionStep
322 6774 : LegalizerInfo::getAction(const LegalityQuery &Query) const {
323 6774 : LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query);
324 6774 : if (Step.Action != LegalizeAction::UseLegacyRules) {
325 4450 : return Step;
326 : }
327 :
328 5492 : for (unsigned i = 0; i < Query.Types.size(); ++i) {
329 6762 : auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]});
330 3381 : if (Action.first != Legal) {
331 : LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i
332 : << " Action=" << (unsigned)Action.first << ", "
333 : << Action.second << "\n");
334 213 : return {Action.first, i, Action.second};
335 : } else
336 : LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n");
337 : }
338 : LLVM_DEBUG(dbgs() << ".. (legacy) Legal\n");
339 2111 : return {Legal, 0, LLT{}};
340 : }
341 :
342 : LegalizeActionStep
343 5877 : LegalizerInfo::getAction(const MachineInstr &MI,
344 : const MachineRegisterInfo &MRI) const {
345 : SmallVector<LLT, 2> Types;
346 5877 : SmallBitVector SeenTypes(8);
347 5877 : const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
348 : // FIXME: probably we'll need to cache the results here somehow?
349 26023 : for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
350 28538 : if (!OpInfo[i].isGenericType())
351 5670 : continue;
352 :
353 : // We must only record actions once for each TypeIdx; otherwise we'd
354 : // try to legalize operands multiple times down the line.
355 : unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
356 12405 : if (SeenTypes[TypeIdx])
357 : continue;
358 :
359 8599 : SeenTypes.set(TypeIdx);
360 :
361 8599 : LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
362 8599 : Types.push_back(Ty);
363 : }
364 :
365 : SmallVector<LegalityQuery::MemDesc, 2> MemDescrs;
366 6790 : for (const auto &MMO : MI.memoperands())
367 913 : MemDescrs.push_back(
368 913 : {MMO->getSize() /* in bytes */ * 8, MMO->getOrdering()});
369 :
370 11754 : return getAction({MI.getOpcode(), Types, MemDescrs});
371 : }
372 :
373 0 : bool LegalizerInfo::isLegal(const MachineInstr &MI,
374 : const MachineRegisterInfo &MRI) const {
375 0 : return getAction(MI, MRI).Action == Legal;
376 : }
377 :
378 0 : bool LegalizerInfo::legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI,
379 : MachineIRBuilder &MIRBuilder) const {
380 0 : return false;
381 : }
382 :
383 : LegalizerInfo::SizeAndActionsVec
384 2034533 : LegalizerInfo::increaseToLargerTypesAndDecreaseToLargest(
385 : const SizeAndActionsVec &v, LegalizeAction IncreaseAction,
386 : LegalizeAction DecreaseAction) {
387 : SizeAndActionsVec result;
388 : unsigned LargestSizeSoFar = 0;
389 2034533 : if (v.size() >= 1 && v[0].first != 1)
390 1399177 : result.push_back({1, IncreaseAction});
391 9446414 : for (size_t i = 0; i < v.size(); ++i) {
392 2688672 : result.push_back(v[i]);
393 2688672 : LargestSizeSoFar = v[i].first;
394 5377344 : if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) {
395 1230678 : result.push_back({LargestSizeSoFar + 1, IncreaseAction});
396 2461356 : LargestSizeSoFar = v[i].first + 1;
397 : }
398 : }
399 2034535 : result.push_back({LargestSizeSoFar + 1, DecreaseAction});
400 2034535 : return result;
401 : }
402 :
403 : LegalizerInfo::SizeAndActionsVec
404 57642 : LegalizerInfo::decreaseToSmallerTypesAndIncreaseToSmallest(
405 : const SizeAndActionsVec &v, LegalizeAction DecreaseAction,
406 : LegalizeAction IncreaseAction) {
407 : SizeAndActionsVec result;
408 57642 : if (v.size() == 0 || v[0].first != 1)
409 41359 : result.push_back({1, IncreaseAction});
410 551648 : for (size_t i = 0; i < v.size(); ++i) {
411 218182 : result.push_back(v[i]);
412 436364 : if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) {
413 218182 : result.push_back({v[i].first + 1, DecreaseAction});
414 : }
415 : }
416 57642 : return result;
417 : }
418 :
419 : LegalizerInfo::SizeAndAction
420 3792 : LegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
421 : assert(Size >= 1);
422 : // Find the last element in Vec that has a bitsize equal to or smaller than
423 : // the requested bit size.
424 : // That is the element just before the first element that is bigger than Size.
425 : auto VecIt = std::upper_bound(
426 : Vec.begin(), Vec.end(), Size,
427 : [](const uint32_t Size, const SizeAndAction lhs) -> bool {
428 8841 : return Size < lhs.first;
429 3792 : });
430 : assert(VecIt != Vec.begin() && "Does Vec not start with size 1?");
431 : --VecIt;
432 3792 : int VecIdx = VecIt - Vec.begin();
433 :
434 3792 : LegalizeAction Action = Vec[VecIdx].second;
435 3792 : switch (Action) {
436 : case Legal:
437 : case Lower:
438 : case Libcall:
439 : case Custom:
440 3643 : return {Size, Action};
441 : case FewerElements:
442 : // FIXME: is this special case still needed and correct?
443 : // Special case for scalarization:
444 62 : if (Vec == SizeAndActionsVec({{1, FewerElements}}))
445 0 : return {1, FewerElements};
446 : LLVM_FALLTHROUGH;
447 : case NarrowScalar: {
448 : // The following needs to be a loop, as for now, we do allow needing to
449 : // go over "Unsupported" bit sizes before finding a legalizable bit size.
450 : // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8,
451 : // we need to iterate over s9, and then to s32 to return (s32, Legal).
452 : // If we want to get rid of the below loop, we should have stronger asserts
453 : // when building the SizeAndActionsVecs, probably not allowing
454 : // "Unsupported" unless at the ends of the vector.
455 47 : for (int i = VecIdx - 1; i >= 0; --i)
456 141 : if (!needsLegalizingToDifferentSize(Vec[i].second) &&
457 : Vec[i].second != Unsupported)
458 47 : return {Vec[i].first, Action};
459 0 : llvm_unreachable("");
460 : }
461 100 : case WidenScalar:
462 : case MoreElements: {
463 : // See above, the following needs to be a loop, at least for now.
464 174 : for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
465 274 : if (!needsLegalizingToDifferentSize(Vec[i].second) &&
466 : Vec[i].second != Unsupported)
467 100 : return {Vec[i].first, Action};
468 0 : llvm_unreachable("");
469 : }
470 2 : case Unsupported:
471 2 : return {Size, Unsupported};
472 : case NotFound:
473 : case UseLegacyRules:
474 : llvm_unreachable("NotFound");
475 : }
476 0 : llvm_unreachable("Action has an unknown enum value");
477 : }
478 :
479 : std::pair<LegalizeAction, LLT>
480 2960 : LegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
481 : assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
482 2960 : if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
483 0 : return {NotFound, LLT()};
484 2960 : const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
485 2960 : if (Aspect.Type.isPointer() &&
486 3527 : AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
487 569 : AddrSpace2PointerActions[OpcodeIdx].end()) {
488 2 : return {NotFound, LLT()};
489 : }
490 : const SmallVector<SizeAndActionsVec, 1> &Actions =
491 2958 : Aspect.Type.isPointer()
492 : ? AddrSpace2PointerActions[OpcodeIdx]
493 1134 : .find(Aspect.Type.getAddressSpace())
494 : ->second
495 2958 : : ScalarActions[OpcodeIdx];
496 2958 : if (Aspect.Idx >= Actions.size())
497 6 : return {NotFound, LLT()};
498 : const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
499 : // FIXME: speed up this search, e.g. by using a results cache for repeated
500 : // queries?
501 2952 : auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
502 : return {SizeAndAction.second,
503 2952 : Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)
504 : : LLT::pointer(Aspect.Type.getAddressSpace(),
505 2952 : SizeAndAction.first)};
506 : }
507 :
508 : std::pair<LegalizeAction, LLT>
509 421 : LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
510 : assert(Aspect.Type.isVector());
511 : // First legalize the vector element size, then legalize the number of
512 : // lanes in the vector.
513 421 : if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
514 0 : return {NotFound, Aspect.Type};
515 421 : const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
516 421 : const unsigned TypeIdx = Aspect.Idx;
517 421 : if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
518 0 : return {NotFound, Aspect.Type};
519 : const SizeAndActionsVec &ElemSizeVec =
520 : ScalarInVectorActions[OpcodeIdx][TypeIdx];
521 :
522 : LLT IntermediateType;
523 : auto ElementSizeAndAction =
524 421 : findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
525 : IntermediateType =
526 421 : LLT::vector(Aspect.Type.getNumElements(), ElementSizeAndAction.first);
527 421 : if (ElementSizeAndAction.second != Legal)
528 2 : return {ElementSizeAndAction.second, IntermediateType};
529 :
530 : auto i = NumElements2Actions[OpcodeIdx].find(
531 838 : IntermediateType.getScalarSizeInBits());
532 419 : if (i == NumElements2Actions[OpcodeIdx].end()) {
533 0 : return {NotFound, IntermediateType};
534 : }
535 : const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
536 : auto NumElementsAndAction =
537 419 : findAction(NumElementsVec, IntermediateType.getNumElements());
538 : return {NumElementsAndAction.second,
539 419 : LLT::vector(NumElementsAndAction.first,
540 419 : IntermediateType.getScalarSizeInBits())};
541 : }
542 :
543 : /// \pre Type indices of every opcode form a dense set starting from 0.
544 35715 : void LegalizerInfo::verify(const MCInstrInfo &MII) const {
545 : #ifndef NDEBUG
546 : std::vector<unsigned> FailedOpcodes;
547 : for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
548 : const MCInstrDesc &MCID = MII.get(Opcode);
549 : const unsigned NumTypeIdxs = std::accumulate(
550 : MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
551 : [](unsigned Acc, const MCOperandInfo &OpInfo) {
552 : return OpInfo.isGenericType()
553 : ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
554 : : Acc;
555 : });
556 : LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
557 : << "): " << NumTypeIdxs << " type ind"
558 : << (NumTypeIdxs == 1 ? "ex" : "ices") << "\n");
559 : const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode);
560 : if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
561 : FailedOpcodes.push_back(Opcode);
562 : }
563 : if (!FailedOpcodes.empty()) {
564 : errs() << "The following opcodes have ill-defined legalization rules:";
565 : for (unsigned Opcode : FailedOpcodes)
566 : errs() << " " << MII.getName(Opcode);
567 : errs() << "\n";
568 :
569 : report_fatal_error("ill-defined LegalizerInfo"
570 : ", try -debug-only=legalizer-info for details");
571 : }
572 : #endif
573 35715 : }
574 :
575 : #ifndef NDEBUG
576 : // FIXME: This should be in the MachineVerifier, but it can't use the
577 : // LegalizerInfo as it's currently in the separate GlobalISel library.
578 : // Note that RegBankSelected property already checked in the verifier
579 : // has the same layering problem, but we only use inline methods so
580 : // end up not needing to link against the GlobalISel library.
581 : const MachineInstr *llvm::machineFunctionIsIllegal(const MachineFunction &MF) {
582 : if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
583 : const MachineRegisterInfo &MRI = MF.getRegInfo();
584 : for (const MachineBasicBlock &MBB : MF)
585 : for (const MachineInstr &MI : MBB)
586 : if (isPreISelGenericOpcode(MI.getOpcode()) && !MLI->isLegal(MI, MRI))
587 : return &MI;
588 : }
589 : return nullptr;
590 : }
591 : #endif
|
