1 //===- lib/CodeGen/GlobalISel/LegalizerInfo.cpp - Legalizer ---------------===//
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
7 //===----------------------------------------------------------------------===//
9 // Implement an interface to specify and query how an illegal operation on a
10 // given type should be expanded.
12 // Issues to be resolved:
14 // + Support weird types like i3, <7 x i3>, ...
15 // + Operations with more than one type (ICMP, CMPXCHG, intrinsics, ...)
17 //===----------------------------------------------------------------------===//
19 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
20 #include "llvm/ADT/SmallBitVector.h"
21 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.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"
36 using namespace LegalizeActions;
38 #define DEBUG_TYPE "legalizer-info"
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"),
45 raw_ostream &llvm::operator<<(raw_ostream &OS, LegalizeAction Action) {
57 OS << "FewerElements";
81 OS << "UseLegacyRules";
87 raw_ostream &LegalityQuery::print(raw_ostream &OS) const {
88 OS << Opcode << ", Tys={";
89 for (const auto &Type : Types) {
94 OS << Opcode << ", MMOs={";
95 for (const auto &MMODescr : MMODescrs) {
96 OS << MMODescr.SizeInBits << ", ";
104 // Make sure the rule won't (trivially) loop forever.
105 static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q,
106 const std::pair<unsigned, LLT> &Mutation) {
107 switch (Rule.getAction()) {
114 return Q.Types[Mutation.first] != Mutation.second;
119 // Make sure the returned mutation makes sense for the match type.
120 static bool mutationIsSane(const LegalizeRule &Rule,
121 const LegalityQuery &Q,
122 std::pair<unsigned, LLT> Mutation) {
123 // If the user wants a custom mutation, then we can't really say much about
124 // it. Return true, and trust that they're doing the right thing.
125 if (Rule.getAction() == Custom)
128 const unsigned TypeIdx = Mutation.first;
129 const LLT OldTy = Q.Types[TypeIdx];
130 const LLT NewTy = Mutation.second;
132 switch (Rule.getAction()) {
134 if (!OldTy.isVector())
138 // MoreElements can go from scalar to vector.
139 const unsigned OldElts = OldTy.isVector() ? OldTy.getNumElements() : 1;
140 if (NewTy.isVector()) {
141 if (Rule.getAction() == FewerElements) {
142 // Make sure the element count really decreased.
143 if (NewTy.getNumElements() >= OldElts)
146 // Make sure the element count really increased.
147 if (NewTy.getNumElements() <= OldElts)
152 // Make sure the element type didn't change.
153 return NewTy.getScalarType() == OldTy.getScalarType();
157 if (OldTy.isVector()) {
158 // Number of elements should not change.
159 if (!NewTy.isVector() || OldTy.getNumElements() != NewTy.getNumElements())
162 // Both types must be vectors
163 if (NewTy.isVector())
167 if (Rule.getAction() == NarrowScalar) {
168 // Make sure the size really decreased.
169 if (NewTy.getScalarSizeInBits() >= OldTy.getScalarSizeInBits())
172 // Make sure the size really increased.
173 if (NewTy.getScalarSizeInBits() <= OldTy.getScalarSizeInBits())
180 return OldTy != NewTy && OldTy.getSizeInBits() == NewTy.getSizeInBits();
188 LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const {
189 LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
192 LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
193 return {LegalizeAction::UseLegacyRules, 0, LLT{}};
195 for (const LegalizeRule &Rule : Rules) {
196 if (Rule.match(Query)) {
197 LLVM_DEBUG(dbgs() << ".. match\n");
198 std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
199 LLVM_DEBUG(dbgs() << ".. .. " << Rule.getAction() << ", "
200 << Mutation.first << ", " << Mutation.second << "\n");
201 assert(mutationIsSane(Rule, Query, Mutation) &&
202 "legality mutation invalid for match");
203 assert(hasNoSimpleLoops(Rule, Query, Mutation) && "Simple loop detected");
204 return {Rule.getAction(), Mutation.first, Mutation.second};
206 LLVM_DEBUG(dbgs() << ".. no match\n");
208 LLVM_DEBUG(dbgs() << ".. unsupported\n");
209 return {LegalizeAction::Unsupported, 0, LLT{}};
212 bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const {
216 dbgs() << ".. type index coverage check SKIPPED: no rules defined\n");
219 const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset();
220 if (FirstUncovered < 0) {
221 LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:"
222 " user-defined predicate detected\n");
225 const bool AllCovered = (FirstUncovered >= NumTypeIdxs);
227 LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered
228 << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
235 bool LegalizeRuleSet::verifyImmIdxsCoverage(unsigned NumImmIdxs) const {
239 dbgs() << ".. imm index coverage check SKIPPED: no rules defined\n");
242 const int64_t FirstUncovered = ImmIdxsCovered.find_first_unset();
243 if (FirstUncovered < 0) {
244 LLVM_DEBUG(dbgs() << ".. imm index coverage check SKIPPED:"
245 " user-defined predicate detected\n");
248 const bool AllCovered = (FirstUncovered >= NumImmIdxs);
249 LLVM_DEBUG(dbgs() << ".. the first uncovered imm index: " << FirstUncovered
250 << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
257 LegalizerInfo::LegalizerInfo() : TablesInitialized(false) {
259 // FIXME: these two (G_ANYEXT and G_TRUNC?) can be legalized to the
260 // fundamental load/store Jakob proposed. Once loads & stores are supported.
261 setScalarAction(TargetOpcode::G_ANYEXT, 1, {{1, Legal}});
262 setScalarAction(TargetOpcode::G_ZEXT, 1, {{1, Legal}});
263 setScalarAction(TargetOpcode::G_SEXT, 1, {{1, Legal}});
264 setScalarAction(TargetOpcode::G_TRUNC, 0, {{1, Legal}});
265 setScalarAction(TargetOpcode::G_TRUNC, 1, {{1, Legal}});
267 setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}});
268 setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}});
270 setLegalizeScalarToDifferentSizeStrategy(
271 TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall);
272 setLegalizeScalarToDifferentSizeStrategy(
273 TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
274 setLegalizeScalarToDifferentSizeStrategy(
275 TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest);
276 setLegalizeScalarToDifferentSizeStrategy(
277 TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
278 setLegalizeScalarToDifferentSizeStrategy(
279 TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
281 setLegalizeScalarToDifferentSizeStrategy(
282 TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
283 setLegalizeScalarToDifferentSizeStrategy(
284 TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
285 setLegalizeScalarToDifferentSizeStrategy(
286 TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
287 setLegalizeScalarToDifferentSizeStrategy(
288 TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
289 setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}});
292 void LegalizerInfo::computeTables() {
293 assert(TablesInitialized == false);
295 for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) {
296 const unsigned Opcode = FirstOp + OpcodeIdx;
297 for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size();
299 // 0. Collect information specified through the setAction API, i.e.
300 // for specific bit sizes.
302 SizeAndActionsVec ScalarSpecifiedActions;
303 // For pointer types:
304 std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions;
306 std::map<uint16_t, SizeAndActionsVec> ElemSize2SpecifiedActions;
307 for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) {
308 const LLT Type = LLT2Action.first;
309 const LegalizeAction Action = LLT2Action.second;
311 auto SizeAction = std::make_pair(Type.getSizeInBits(), Action);
312 if (Type.isPointer())
313 AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(
315 else if (Type.isVector())
316 ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()]
317 .push_back(SizeAction);
319 ScalarSpecifiedActions.push_back(SizeAction);
322 // 1. Handle scalar types
324 // Decide how to handle bit sizes for which no explicit specification
326 SizeChangeStrategy S = &unsupportedForDifferentSizes;
327 if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() &&
328 ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
329 S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx];
330 llvm::sort(ScalarSpecifiedActions);
331 checkPartialSizeAndActionsVector(ScalarSpecifiedActions);
332 setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions));
335 // 2. Handle pointer types
336 for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) {
337 llvm::sort(PointerSpecifiedActions.second);
338 checkPartialSizeAndActionsVector(PointerSpecifiedActions.second);
339 // For pointer types, we assume that there isn't a meaningfull way
340 // to change the number of bits used in the pointer.
342 Opcode, TypeIdx, PointerSpecifiedActions.first,
343 unsupportedForDifferentSizes(PointerSpecifiedActions.second));
346 // 3. Handle vector types
347 SizeAndActionsVec ElementSizesSeen;
348 for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) {
349 llvm::sort(VectorSpecifiedActions.second);
350 const uint16_t ElementSize = VectorSpecifiedActions.first;
351 ElementSizesSeen.push_back({ElementSize, Legal});
352 checkPartialSizeAndActionsVector(VectorSpecifiedActions.second);
353 // For vector types, we assume that the best way to adapt the number
354 // of elements is to the next larger number of elements type for which
355 // the vector type is legal, unless there is no such type. In that case,
356 // legalize towards a vector type with a smaller number of elements.
357 SizeAndActionsVec NumElementsActions;
358 for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) {
359 assert(BitsizeAndAction.first % ElementSize == 0);
360 const uint16_t NumElements = BitsizeAndAction.first / ElementSize;
361 NumElementsActions.push_back({NumElements, BitsizeAndAction.second});
363 setVectorNumElementAction(
364 Opcode, TypeIdx, ElementSize,
365 moreToWiderTypesAndLessToWidest(NumElementsActions));
367 llvm::sort(ElementSizesSeen);
368 SizeChangeStrategy VectorElementSizeChangeStrategy =
369 &unsupportedForDifferentSizes;
370 if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() &&
371 VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
372 VectorElementSizeChangeStrategy =
373 VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx];
374 setScalarInVectorAction(
375 Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen));
379 TablesInitialized = true;
382 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
383 // probably going to need specialized lookup structures for various types before
384 // we have any hope of doing well with something like <13 x i3>. Even the common
385 // cases should do better than what we have now.
386 std::pair<LegalizeAction, LLT>
387 LegalizerInfo::getAspectAction(const InstrAspect &Aspect) const {
388 assert(TablesInitialized && "backend forgot to call computeTables");
389 // These *have* to be implemented for now, they're the fundamental basis of
390 // how everything else is transformed.
391 if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
392 return findScalarLegalAction(Aspect);
393 assert(Aspect.Type.isVector());
394 return findVectorLegalAction(Aspect);
397 /// Helper function to get LLT for the given type index.
398 static LLT getTypeFromTypeIdx(const MachineInstr &MI,
399 const MachineRegisterInfo &MRI, unsigned OpIdx,
401 assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
402 // G_UNMERGE_VALUES has variable number of operands, but there is only
403 // one source type and one destination type as all destinations must be the
404 // same type. So, get the last operand if TypeIdx == 1.
405 if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
406 return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
407 return MRI.getType(MI.getOperand(OpIdx).getReg());
410 unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
411 assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
412 return Opcode - FirstOp;
415 unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
416 unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
417 if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
418 LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
420 OpcodeIdx = getOpcodeIdxForOpcode(Alias);
421 assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
427 const LegalizeRuleSet &
428 LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
429 unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
430 return RulesForOpcode[OpcodeIdx];
433 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) {
434 unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
435 auto &Result = RulesForOpcode[OpcodeIdx];
436 assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
440 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(
441 std::initializer_list<unsigned> Opcodes) {
442 unsigned Representative = *Opcodes.begin();
444 assert(!llvm::empty(Opcodes) && Opcodes.begin() + 1 != Opcodes.end() &&
445 "Initializer list must have at least two opcodes");
447 for (auto I = Opcodes.begin() + 1, E = Opcodes.end(); I != E; ++I)
448 aliasActionDefinitions(Representative, *I);
450 auto &Return = getActionDefinitionsBuilder(Representative);
451 Return.setIsAliasedByAnother();
455 void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo,
456 unsigned OpcodeFrom) {
457 assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
458 assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
459 const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
460 RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
464 LegalizerInfo::getAction(const LegalityQuery &Query) const {
465 LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query);
466 if (Step.Action != LegalizeAction::UseLegacyRules) {
470 for (unsigned i = 0; i < Query.Types.size(); ++i) {
471 auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]});
472 if (Action.first != Legal) {
473 LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Action="
474 << Action.first << ", " << Action.second << "\n");
475 return {Action.first, i, Action.second};
477 LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n");
479 LLVM_DEBUG(dbgs() << ".. (legacy) Legal\n");
480 return {Legal, 0, LLT{}};
484 LegalizerInfo::getAction(const MachineInstr &MI,
485 const MachineRegisterInfo &MRI) const {
486 SmallVector<LLT, 2> Types;
487 SmallBitVector SeenTypes(8);
488 const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
489 // FIXME: probably we'll need to cache the results here somehow?
490 for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
491 if (!OpInfo[i].isGenericType())
494 // We must only record actions once for each TypeIdx; otherwise we'd
495 // try to legalize operands multiple times down the line.
496 unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
497 if (SeenTypes[TypeIdx])
500 SeenTypes.set(TypeIdx);
502 LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
506 SmallVector<LegalityQuery::MemDesc, 2> MemDescrs;
507 for (const auto &MMO : MI.memoperands())
508 MemDescrs.push_back({8 * MMO->getSize() /* in bits */,
509 8 * MMO->getAlign().value(), MMO->getOrdering()});
511 return getAction({MI.getOpcode(), Types, MemDescrs});
514 bool LegalizerInfo::isLegal(const MachineInstr &MI,
515 const MachineRegisterInfo &MRI) const {
516 return getAction(MI, MRI).Action == Legal;
519 bool LegalizerInfo::isLegalOrCustom(const MachineInstr &MI,
520 const MachineRegisterInfo &MRI) const {
521 auto Action = getAction(MI, MRI).Action;
522 // If the action is custom, it may not necessarily modify the instruction,
523 // so we have to assume it's legal.
524 return Action == Legal || Action == Custom;
527 LegalizerInfo::SizeAndActionsVec
528 LegalizerInfo::increaseToLargerTypesAndDecreaseToLargest(
529 const SizeAndActionsVec &v, LegalizeAction IncreaseAction,
530 LegalizeAction DecreaseAction) {
531 SizeAndActionsVec result;
532 unsigned LargestSizeSoFar = 0;
533 if (v.size() >= 1 && v[0].first != 1)
534 result.push_back({1, IncreaseAction});
535 for (size_t i = 0; i < v.size(); ++i) {
536 result.push_back(v[i]);
537 LargestSizeSoFar = v[i].first;
538 if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) {
539 result.push_back({LargestSizeSoFar + 1, IncreaseAction});
540 LargestSizeSoFar = v[i].first + 1;
543 result.push_back({LargestSizeSoFar + 1, DecreaseAction});
547 LegalizerInfo::SizeAndActionsVec
548 LegalizerInfo::decreaseToSmallerTypesAndIncreaseToSmallest(
549 const SizeAndActionsVec &v, LegalizeAction DecreaseAction,
550 LegalizeAction IncreaseAction) {
551 SizeAndActionsVec result;
552 if (v.size() == 0 || v[0].first != 1)
553 result.push_back({1, IncreaseAction});
554 for (size_t i = 0; i < v.size(); ++i) {
555 result.push_back(v[i]);
556 if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) {
557 result.push_back({v[i].first + 1, DecreaseAction});
563 LegalizerInfo::SizeAndAction
564 LegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
566 // Find the last element in Vec that has a bitsize equal to or smaller than
567 // the requested bit size.
568 // That is the element just before the first element that is bigger than Size.
569 auto It = partition_point(
570 Vec, [=](const SizeAndAction &A) { return A.first <= Size; });
571 assert(It != Vec.begin() && "Does Vec not start with size 1?");
572 int VecIdx = It - Vec.begin() - 1;
574 LegalizeAction Action = Vec[VecIdx].second;
581 return {Size, Action};
583 // FIXME: is this special case still needed and correct?
584 // Special case for scalarization:
585 if (Vec == SizeAndActionsVec({{1, FewerElements}}))
586 return {1, FewerElements};
589 // The following needs to be a loop, as for now, we do allow needing to
590 // go over "Unsupported" bit sizes before finding a legalizable bit size.
591 // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8,
592 // we need to iterate over s9, and then to s32 to return (s32, Legal).
593 // If we want to get rid of the below loop, we should have stronger asserts
594 // when building the SizeAndActionsVecs, probably not allowing
595 // "Unsupported" unless at the ends of the vector.
596 for (int i = VecIdx - 1; i >= 0; --i)
597 if (!needsLegalizingToDifferentSize(Vec[i].second) &&
598 Vec[i].second != Unsupported)
599 return {Vec[i].first, Action};
600 llvm_unreachable("");
604 // See above, the following needs to be a loop, at least for now.
605 for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
606 if (!needsLegalizingToDifferentSize(Vec[i].second) &&
607 Vec[i].second != Unsupported)
608 return {Vec[i].first, Action};
609 llvm_unreachable("");
612 return {Size, Unsupported};
615 llvm_unreachable("NotFound");
617 llvm_unreachable("Action has an unknown enum value");
620 std::pair<LegalizeAction, LLT>
621 LegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
622 assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
623 if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
624 return {NotFound, LLT()};
625 const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
626 if (Aspect.Type.isPointer() &&
627 AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
628 AddrSpace2PointerActions[OpcodeIdx].end()) {
629 return {NotFound, LLT()};
631 const SmallVector<SizeAndActionsVec, 1> &Actions =
632 Aspect.Type.isPointer()
633 ? AddrSpace2PointerActions[OpcodeIdx]
634 .find(Aspect.Type.getAddressSpace())
636 : ScalarActions[OpcodeIdx];
637 if (Aspect.Idx >= Actions.size())
638 return {NotFound, LLT()};
639 const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
640 // FIXME: speed up this search, e.g. by using a results cache for repeated
642 auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
643 return {SizeAndAction.second,
644 Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)
645 : LLT::pointer(Aspect.Type.getAddressSpace(),
646 SizeAndAction.first)};
649 std::pair<LegalizeAction, LLT>
650 LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
651 assert(Aspect.Type.isVector());
652 // First legalize the vector element size, then legalize the number of
653 // lanes in the vector.
654 if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
655 return {NotFound, Aspect.Type};
656 const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
657 const unsigned TypeIdx = Aspect.Idx;
658 if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
659 return {NotFound, Aspect.Type};
660 const SizeAndActionsVec &ElemSizeVec =
661 ScalarInVectorActions[OpcodeIdx][TypeIdx];
663 LLT IntermediateType;
664 auto ElementSizeAndAction =
665 findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
667 LLT::vector(Aspect.Type.getNumElements(), ElementSizeAndAction.first);
668 if (ElementSizeAndAction.second != Legal)
669 return {ElementSizeAndAction.second, IntermediateType};
671 auto i = NumElements2Actions[OpcodeIdx].find(
672 IntermediateType.getScalarSizeInBits());
673 if (i == NumElements2Actions[OpcodeIdx].end()) {
674 return {NotFound, IntermediateType};
676 const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
677 auto NumElementsAndAction =
678 findAction(NumElementsVec, IntermediateType.getNumElements());
679 return {NumElementsAndAction.second,
680 LLT::vector(NumElementsAndAction.first,
681 IntermediateType.getScalarSizeInBits())};
684 unsigned LegalizerInfo::getExtOpcodeForWideningConstant(LLT SmallTy) const {
685 return SmallTy.isByteSized() ? TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT;
688 /// \pre Type indices of every opcode form a dense set starting from 0.
689 void LegalizerInfo::verify(const MCInstrInfo &MII) const {
691 std::vector<unsigned> FailedOpcodes;
692 for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
693 const MCInstrDesc &MCID = MII.get(Opcode);
694 const unsigned NumTypeIdxs = std::accumulate(
695 MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
696 [](unsigned Acc, const MCOperandInfo &OpInfo) {
697 return OpInfo.isGenericType()
698 ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
701 const unsigned NumImmIdxs = std::accumulate(
702 MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
703 [](unsigned Acc, const MCOperandInfo &OpInfo) {
704 return OpInfo.isGenericImm()
705 ? std::max(OpInfo.getGenericImmIndex() + 1U, Acc)
708 LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
709 << "): " << NumTypeIdxs << " type ind"
710 << (NumTypeIdxs == 1 ? "ex" : "ices") << ", "
711 << NumImmIdxs << " imm ind"
712 << (NumImmIdxs == 1 ? "ex" : "ices") << "\n");
713 const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode);
714 if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
715 FailedOpcodes.push_back(Opcode);
716 else if (!RuleSet.verifyImmIdxsCoverage(NumImmIdxs))
717 FailedOpcodes.push_back(Opcode);
719 if (!FailedOpcodes.empty()) {
720 errs() << "The following opcodes have ill-defined legalization rules:";
721 for (unsigned Opcode : FailedOpcodes)
722 errs() << " " << MII.getName(Opcode);
725 report_fatal_error("ill-defined LegalizerInfo"
726 ", try -debug-only=legalizer-info for details");
732 // FIXME: This should be in the MachineVerifier, but it can't use the
733 // LegalizerInfo as it's currently in the separate GlobalISel library.
734 // Note that RegBankSelected property already checked in the verifier
735 // has the same layering problem, but we only use inline methods so
736 // end up not needing to link against the GlobalISel library.
737 const MachineInstr *llvm::machineFunctionIsIllegal(const MachineFunction &MF) {
738 if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
739 const MachineRegisterInfo &MRI = MF.getRegInfo();
740 for (const MachineBasicBlock &MBB : MF)
741 for (const MachineInstr &MI : MBB)
742 if (isPreISelGenericOpcode(MI.getOpcode()) &&
743 !MLI->isLegalOrCustom(MI, MRI))