1 //===- lib/CodeGen/GlobalISel/LegalizerInfo.cpp - Legalizer ---------------===//
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 // Implement an interface to specify and query how an illegal operation on a
10 // given type should be expanded.
11 //
12 // Issues to be resolved:
13 //   + Make it fast.
14 //   + Support weird types like i3, <7 x i3>, ...
15 //   + Operations with more than one type (ICMP, CMPXCHG, intrinsics, ...)
16 //
17 //===----------------------------------------------------------------------===//
18 
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"
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 
operator <<(raw_ostream & OS,LegalizeAction Action)45 raw_ostream &llvm::operator<<(raw_ostream &OS, LegalizeAction Action) {
46   switch (Action) {
47   case Legal:
48     OS << "Legal";
49     break;
50   case NarrowScalar:
51     OS << "NarrowScalar";
52     break;
53   case WidenScalar:
54     OS << "WidenScalar";
55     break;
56   case FewerElements:
57     OS << "FewerElements";
58     break;
59   case MoreElements:
60     OS << "MoreElements";
61     break;
62   case Bitcast:
63     OS << "Bitcast";
64     break;
65   case Lower:
66     OS << "Lower";
67     break;
68   case Libcall:
69     OS << "Libcall";
70     break;
71   case Custom:
72     OS << "Custom";
73     break;
74   case Unsupported:
75     OS << "Unsupported";
76     break;
77   case NotFound:
78     OS << "NotFound";
79     break;
80   case UseLegacyRules:
81     OS << "UseLegacyRules";
82     break;
83   }
84   return OS;
85 }
86 
print(raw_ostream & OS) const87 raw_ostream &LegalityQuery::print(raw_ostream &OS) const {
88   OS << Opcode << ", Tys={";
89   for (const auto &Type : Types) {
90     OS << Type << ", ";
91   }
92   OS << "}, Opcode=";
93 
94   OS << Opcode << ", MMOs={";
95   for (const auto &MMODescr : MMODescrs) {
96     OS << MMODescr.SizeInBits << ", ";
97   }
98   OS << "}";
99 
100   return OS;
101 }
102 
103 #ifndef NDEBUG
104 // Make sure the rule won't (trivially) loop forever.
hasNoSimpleLoops(const LegalizeRule & Rule,const LegalityQuery & Q,const std::pair<unsigned,LLT> & Mutation)105 static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q,
106                              const std::pair<unsigned, LLT> &Mutation) {
107   switch (Rule.getAction()) {
108   case Legal:
109   case Custom:
110   case Lower:
111   case MoreElements:
112   case FewerElements:
113     break;
114   default:
115     return Q.Types[Mutation.first] != Mutation.second;
116   }
117   return true;
118 }
119 
120 // Make sure the returned mutation makes sense for the match type.
mutationIsSane(const LegalizeRule & Rule,const LegalityQuery & Q,std::pair<unsigned,LLT> Mutation)121 static bool mutationIsSane(const LegalizeRule &Rule,
122                            const LegalityQuery &Q,
123                            std::pair<unsigned, LLT> Mutation) {
124   // If the user wants a custom mutation, then we can't really say much about
125   // it. Return true, and trust that they're doing the right thing.
126   if (Rule.getAction() == Custom || Rule.getAction() == Legal)
127     return true;
128 
129   const unsigned TypeIdx = Mutation.first;
130   const LLT OldTy = Q.Types[TypeIdx];
131   const LLT NewTy = Mutation.second;
132 
133   switch (Rule.getAction()) {
134   case FewerElements:
135     if (!OldTy.isVector())
136       return false;
137     LLVM_FALLTHROUGH;
138   case MoreElements: {
139     // MoreElements can go from scalar to vector.
140     const unsigned OldElts = OldTy.isVector() ? OldTy.getNumElements() : 1;
141     if (NewTy.isVector()) {
142       if (Rule.getAction() == FewerElements) {
143         // Make sure the element count really decreased.
144         if (NewTy.getNumElements() >= OldElts)
145           return false;
146       } else {
147         // Make sure the element count really increased.
148         if (NewTy.getNumElements() <= OldElts)
149           return false;
150       }
151     } else if (Rule.getAction() == MoreElements)
152       return false;
153 
154     // Make sure the element type didn't change.
155     return NewTy.getScalarType() == OldTy.getScalarType();
156   }
157   case NarrowScalar:
158   case WidenScalar: {
159     if (OldTy.isVector()) {
160       // Number of elements should not change.
161       if (!NewTy.isVector() || OldTy.getNumElements() != NewTy.getNumElements())
162         return false;
163     } else {
164       // Both types must be vectors
165       if (NewTy.isVector())
166         return false;
167     }
168 
169     if (Rule.getAction() == NarrowScalar)  {
170       // Make sure the size really decreased.
171       if (NewTy.getScalarSizeInBits() >= OldTy.getScalarSizeInBits())
172         return false;
173     } else {
174       // Make sure the size really increased.
175       if (NewTy.getScalarSizeInBits() <= OldTy.getScalarSizeInBits())
176         return false;
177     }
178 
179     return true;
180   }
181   case Bitcast: {
182     return OldTy != NewTy && OldTy.getSizeInBits() == NewTy.getSizeInBits();
183   }
184   default:
185     return true;
186   }
187 }
188 #endif
189 
apply(const LegalityQuery & Query) const190 LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const {
191   LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
192              dbgs() << "\n");
193   if (Rules.empty()) {
194     LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
195     return {LegalizeAction::UseLegacyRules, 0, LLT{}};
196   }
197   for (const LegalizeRule &Rule : Rules) {
198     if (Rule.match(Query)) {
199       LLVM_DEBUG(dbgs() << ".. match\n");
200       std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
201       LLVM_DEBUG(dbgs() << ".. .. " << Rule.getAction() << ", "
202                         << Mutation.first << ", " << Mutation.second << "\n");
203       assert(mutationIsSane(Rule, Query, Mutation) &&
204              "legality mutation invalid for match");
205       assert(hasNoSimpleLoops(Rule, Query, Mutation) && "Simple loop detected");
206       return {Rule.getAction(), Mutation.first, Mutation.second};
207     } else
208       LLVM_DEBUG(dbgs() << ".. no match\n");
209   }
210   LLVM_DEBUG(dbgs() << ".. unsupported\n");
211   return {LegalizeAction::Unsupported, 0, LLT{}};
212 }
213 
verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const214 bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const {
215 #ifndef NDEBUG
216   if (Rules.empty()) {
217     LLVM_DEBUG(
218         dbgs() << ".. type index coverage check SKIPPED: no rules defined\n");
219     return true;
220   }
221   const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset();
222   if (FirstUncovered < 0) {
223     LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:"
224                          " user-defined predicate detected\n");
225     return true;
226   }
227   const bool AllCovered = (FirstUncovered >= NumTypeIdxs);
228   if (NumTypeIdxs > 0)
229     LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered
230                       << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
231   return AllCovered;
232 #else
233   return true;
234 #endif
235 }
236 
verifyImmIdxsCoverage(unsigned NumImmIdxs) const237 bool LegalizeRuleSet::verifyImmIdxsCoverage(unsigned NumImmIdxs) const {
238 #ifndef NDEBUG
239   if (Rules.empty()) {
240     LLVM_DEBUG(
241         dbgs() << ".. imm index coverage check SKIPPED: no rules defined\n");
242     return true;
243   }
244   const int64_t FirstUncovered = ImmIdxsCovered.find_first_unset();
245   if (FirstUncovered < 0) {
246     LLVM_DEBUG(dbgs() << ".. imm index coverage check SKIPPED:"
247                          " user-defined predicate detected\n");
248     return true;
249   }
250   const bool AllCovered = (FirstUncovered >= NumImmIdxs);
251   LLVM_DEBUG(dbgs() << ".. the first uncovered imm index: " << FirstUncovered
252                     << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
253   return AllCovered;
254 #else
255   return true;
256 #endif
257 }
258 
LegalizerInfo()259 LegalizerInfo::LegalizerInfo() : TablesInitialized(false) {
260   // Set defaults.
261   // FIXME: these two (G_ANYEXT and G_TRUNC?) can be legalized to the
262   // fundamental load/store Jakob proposed. Once loads & stores are supported.
263   setScalarAction(TargetOpcode::G_ANYEXT, 1, {{1, Legal}});
264   setScalarAction(TargetOpcode::G_ZEXT, 1, {{1, Legal}});
265   setScalarAction(TargetOpcode::G_SEXT, 1, {{1, Legal}});
266   setScalarAction(TargetOpcode::G_TRUNC, 0, {{1, Legal}});
267   setScalarAction(TargetOpcode::G_TRUNC, 1, {{1, Legal}});
268 
269   setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}});
270   setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}});
271 
272   setLegalizeScalarToDifferentSizeStrategy(
273       TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall);
274   setLegalizeScalarToDifferentSizeStrategy(
275       TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
276   setLegalizeScalarToDifferentSizeStrategy(
277       TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest);
278   setLegalizeScalarToDifferentSizeStrategy(
279       TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
280   setLegalizeScalarToDifferentSizeStrategy(
281       TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
282 
283   setLegalizeScalarToDifferentSizeStrategy(
284       TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
285   setLegalizeScalarToDifferentSizeStrategy(
286       TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
287   setLegalizeScalarToDifferentSizeStrategy(
288       TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
289   setLegalizeScalarToDifferentSizeStrategy(
290       TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
291   setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}});
292 }
293 
computeTables()294 void LegalizerInfo::computeTables() {
295   assert(TablesInitialized == false);
296 
297   for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) {
298     const unsigned Opcode = FirstOp + OpcodeIdx;
299     for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size();
300          ++TypeIdx) {
301       // 0. Collect information specified through the setAction API, i.e.
302       // for specific bit sizes.
303       // For scalar types:
304       SizeAndActionsVec ScalarSpecifiedActions;
305       // For pointer types:
306       std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions;
307       // For vector types:
308       std::map<uint16_t, SizeAndActionsVec> ElemSize2SpecifiedActions;
309       for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) {
310         const LLT Type = LLT2Action.first;
311         const LegalizeAction Action = LLT2Action.second;
312 
313         auto SizeAction = std::make_pair(Type.getSizeInBits(), Action);
314         if (Type.isPointer())
315           AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(
316               SizeAction);
317         else if (Type.isVector())
318           ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()]
319               .push_back(SizeAction);
320         else
321           ScalarSpecifiedActions.push_back(SizeAction);
322       }
323 
324       // 1. Handle scalar types
325       {
326         // Decide how to handle bit sizes for which no explicit specification
327         // was given.
328         SizeChangeStrategy S = &unsupportedForDifferentSizes;
329         if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() &&
330             ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
331           S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx];
332         llvm::sort(ScalarSpecifiedActions);
333         checkPartialSizeAndActionsVector(ScalarSpecifiedActions);
334         setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions));
335       }
336 
337       // 2. Handle pointer types
338       for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) {
339         llvm::sort(PointerSpecifiedActions.second);
340         checkPartialSizeAndActionsVector(PointerSpecifiedActions.second);
341         // For pointer types, we assume that there isn't a meaningfull way
342         // to change the number of bits used in the pointer.
343         setPointerAction(
344             Opcode, TypeIdx, PointerSpecifiedActions.first,
345             unsupportedForDifferentSizes(PointerSpecifiedActions.second));
346       }
347 
348       // 3. Handle vector types
349       SizeAndActionsVec ElementSizesSeen;
350       for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) {
351         llvm::sort(VectorSpecifiedActions.second);
352         const uint16_t ElementSize = VectorSpecifiedActions.first;
353         ElementSizesSeen.push_back({ElementSize, Legal});
354         checkPartialSizeAndActionsVector(VectorSpecifiedActions.second);
355         // For vector types, we assume that the best way to adapt the number
356         // of elements is to the next larger number of elements type for which
357         // the vector type is legal, unless there is no such type. In that case,
358         // legalize towards a vector type with a smaller number of elements.
359         SizeAndActionsVec NumElementsActions;
360         for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) {
361           assert(BitsizeAndAction.first % ElementSize == 0);
362           const uint16_t NumElements = BitsizeAndAction.first / ElementSize;
363           NumElementsActions.push_back({NumElements, BitsizeAndAction.second});
364         }
365         setVectorNumElementAction(
366             Opcode, TypeIdx, ElementSize,
367             moreToWiderTypesAndLessToWidest(NumElementsActions));
368       }
369       llvm::sort(ElementSizesSeen);
370       SizeChangeStrategy VectorElementSizeChangeStrategy =
371           &unsupportedForDifferentSizes;
372       if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() &&
373           VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
374         VectorElementSizeChangeStrategy =
375             VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx];
376       setScalarInVectorAction(
377           Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen));
378     }
379   }
380 
381   TablesInitialized = true;
382 }
383 
384 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
385 // probably going to need specialized lookup structures for various types before
386 // we have any hope of doing well with something like <13 x i3>. Even the common
387 // cases should do better than what we have now.
388 std::pair<LegalizeAction, LLT>
getAspectAction(const InstrAspect & Aspect) const389 LegalizerInfo::getAspectAction(const InstrAspect &Aspect) const {
390   assert(TablesInitialized && "backend forgot to call computeTables");
391   // These *have* to be implemented for now, they're the fundamental basis of
392   // how everything else is transformed.
393   if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
394     return findScalarLegalAction(Aspect);
395   assert(Aspect.Type.isVector());
396   return findVectorLegalAction(Aspect);
397 }
398 
399 /// Helper function to get LLT for the given type index.
getTypeFromTypeIdx(const MachineInstr & MI,const MachineRegisterInfo & MRI,unsigned OpIdx,unsigned TypeIdx)400 static LLT getTypeFromTypeIdx(const MachineInstr &MI,
401                               const MachineRegisterInfo &MRI, unsigned OpIdx,
402                               unsigned TypeIdx) {
403   assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
404   // G_UNMERGE_VALUES has variable number of operands, but there is only
405   // one source type and one destination type as all destinations must be the
406   // same type. So, get the last operand if TypeIdx == 1.
407   if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
408     return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
409   return MRI.getType(MI.getOperand(OpIdx).getReg());
410 }
411 
getOpcodeIdxForOpcode(unsigned Opcode) const412 unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
413   assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
414   return Opcode - FirstOp;
415 }
416 
getActionDefinitionsIdx(unsigned Opcode) const417 unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
418   unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
419   if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
420     LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
421                       << "\n");
422     OpcodeIdx = getOpcodeIdxForOpcode(Alias);
423     assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
424   }
425 
426   return OpcodeIdx;
427 }
428 
429 const LegalizeRuleSet &
getActionDefinitions(unsigned Opcode) const430 LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
431   unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
432   return RulesForOpcode[OpcodeIdx];
433 }
434 
getActionDefinitionsBuilder(unsigned Opcode)435 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) {
436   unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
437   auto &Result = RulesForOpcode[OpcodeIdx];
438   assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
439   return Result;
440 }
441 
getActionDefinitionsBuilder(std::initializer_list<unsigned> Opcodes)442 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(
443     std::initializer_list<unsigned> Opcodes) {
444   unsigned Representative = *Opcodes.begin();
445 
446   assert(!llvm::empty(Opcodes) && Opcodes.begin() + 1 != Opcodes.end() &&
447          "Initializer list must have at least two opcodes");
448 
449   for (unsigned Op : llvm::drop_begin(Opcodes))
450     aliasActionDefinitions(Representative, Op);
451 
452   auto &Return = getActionDefinitionsBuilder(Representative);
453   Return.setIsAliasedByAnother();
454   return Return;
455 }
456 
aliasActionDefinitions(unsigned OpcodeTo,unsigned OpcodeFrom)457 void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo,
458                                            unsigned OpcodeFrom) {
459   assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
460   assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
461   const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
462   RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
463 }
464 
465 LegalizeActionStep
getAction(const LegalityQuery & Query) const466 LegalizerInfo::getAction(const LegalityQuery &Query) const {
467   LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query);
468   if (Step.Action != LegalizeAction::UseLegacyRules) {
469     return Step;
470   }
471 
472   for (unsigned i = 0; i < Query.Types.size(); ++i) {
473     auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]});
474     if (Action.first != Legal) {
475       LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Action="
476                         << Action.first << ", " << Action.second << "\n");
477       return {Action.first, i, Action.second};
478     } else
479       LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n");
480   }
481   LLVM_DEBUG(dbgs() << ".. (legacy) Legal\n");
482   return {Legal, 0, LLT{}};
483 }
484 
485 LegalizeActionStep
getAction(const MachineInstr & MI,const MachineRegisterInfo & MRI) const486 LegalizerInfo::getAction(const MachineInstr &MI,
487                          const MachineRegisterInfo &MRI) const {
488   SmallVector<LLT, 8> Types;
489   SmallBitVector SeenTypes(8);
490   const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
491   // FIXME: probably we'll need to cache the results here somehow?
492   for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
493     if (!OpInfo[i].isGenericType())
494       continue;
495 
496     // We must only record actions once for each TypeIdx; otherwise we'd
497     // try to legalize operands multiple times down the line.
498     unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
499     if (SeenTypes[TypeIdx])
500       continue;
501 
502     SeenTypes.set(TypeIdx);
503 
504     LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
505     Types.push_back(Ty);
506   }
507 
508   SmallVector<LegalityQuery::MemDesc, 2> MemDescrs;
509   for (const auto &MMO : MI.memoperands())
510     MemDescrs.push_back({8 * MMO->getSize() /* in bits */,
511                          8 * MMO->getAlign().value(), MMO->getOrdering()});
512 
513   return getAction({MI.getOpcode(), Types, MemDescrs});
514 }
515 
isLegal(const MachineInstr & MI,const MachineRegisterInfo & MRI) const516 bool LegalizerInfo::isLegal(const MachineInstr &MI,
517                             const MachineRegisterInfo &MRI) const {
518   return getAction(MI, MRI).Action == Legal;
519 }
520 
isLegalOrCustom(const MachineInstr & MI,const MachineRegisterInfo & MRI) const521 bool LegalizerInfo::isLegalOrCustom(const MachineInstr &MI,
522                                     const MachineRegisterInfo &MRI) const {
523   auto Action = getAction(MI, MRI).Action;
524   // If the action is custom, it may not necessarily modify the instruction,
525   // so we have to assume it's legal.
526   return Action == Legal || Action == Custom;
527 }
528 
529 LegalizerInfo::SizeAndActionsVec
increaseToLargerTypesAndDecreaseToLargest(const SizeAndActionsVec & v,LegalizeAction IncreaseAction,LegalizeAction DecreaseAction)530 LegalizerInfo::increaseToLargerTypesAndDecreaseToLargest(
531     const SizeAndActionsVec &v, LegalizeAction IncreaseAction,
532     LegalizeAction DecreaseAction) {
533   SizeAndActionsVec result;
534   unsigned LargestSizeSoFar = 0;
535   if (v.size() >= 1 && v[0].first != 1)
536     result.push_back({1, IncreaseAction});
537   for (size_t i = 0; i < v.size(); ++i) {
538     result.push_back(v[i]);
539     LargestSizeSoFar = v[i].first;
540     if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) {
541       result.push_back({LargestSizeSoFar + 1, IncreaseAction});
542       LargestSizeSoFar = v[i].first + 1;
543     }
544   }
545   result.push_back({LargestSizeSoFar + 1, DecreaseAction});
546   return result;
547 }
548 
549 LegalizerInfo::SizeAndActionsVec
decreaseToSmallerTypesAndIncreaseToSmallest(const SizeAndActionsVec & v,LegalizeAction DecreaseAction,LegalizeAction IncreaseAction)550 LegalizerInfo::decreaseToSmallerTypesAndIncreaseToSmallest(
551     const SizeAndActionsVec &v, LegalizeAction DecreaseAction,
552     LegalizeAction IncreaseAction) {
553   SizeAndActionsVec result;
554   if (v.size() == 0 || v[0].first != 1)
555     result.push_back({1, IncreaseAction});
556   for (size_t i = 0; i < v.size(); ++i) {
557     result.push_back(v[i]);
558     if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) {
559       result.push_back({v[i].first + 1, DecreaseAction});
560     }
561   }
562   return result;
563 }
564 
565 LegalizerInfo::SizeAndAction
findAction(const SizeAndActionsVec & Vec,const uint32_t Size)566 LegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
567   assert(Size >= 1);
568   // Find the last element in Vec that has a bitsize equal to or smaller than
569   // the requested bit size.
570   // That is the element just before the first element that is bigger than Size.
571   auto It = partition_point(
572       Vec, [=](const SizeAndAction &A) { return A.first <= Size; });
573   assert(It != Vec.begin() && "Does Vec not start with size 1?");
574   int VecIdx = It - Vec.begin() - 1;
575 
576   LegalizeAction Action = Vec[VecIdx].second;
577   switch (Action) {
578   case Legal:
579   case Bitcast:
580   case Lower:
581   case Libcall:
582   case Custom:
583     return {Size, Action};
584   case FewerElements:
585     // FIXME: is this special case still needed and correct?
586     // Special case for scalarization:
587     if (Vec == SizeAndActionsVec({{1, FewerElements}}))
588       return {1, FewerElements};
589     LLVM_FALLTHROUGH;
590   case NarrowScalar: {
591     // The following needs to be a loop, as for now, we do allow needing to
592     // go over "Unsupported" bit sizes before finding a legalizable bit size.
593     // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8,
594     // we need to iterate over s9, and then to s32 to return (s32, Legal).
595     // If we want to get rid of the below loop, we should have stronger asserts
596     // when building the SizeAndActionsVecs, probably not allowing
597     // "Unsupported" unless at the ends of the vector.
598     for (int i = VecIdx - 1; i >= 0; --i)
599       if (!needsLegalizingToDifferentSize(Vec[i].second) &&
600           Vec[i].second != Unsupported)
601         return {Vec[i].first, Action};
602     llvm_unreachable("");
603   }
604   case WidenScalar:
605   case MoreElements: {
606     // See above, the following needs to be a loop, at least for now.
607     for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
608       if (!needsLegalizingToDifferentSize(Vec[i].second) &&
609           Vec[i].second != Unsupported)
610         return {Vec[i].first, Action};
611     llvm_unreachable("");
612   }
613   case Unsupported:
614     return {Size, Unsupported};
615   case NotFound:
616   case UseLegacyRules:
617     llvm_unreachable("NotFound");
618   }
619   llvm_unreachable("Action has an unknown enum value");
620 }
621 
622 std::pair<LegalizeAction, LLT>
findScalarLegalAction(const InstrAspect & Aspect) const623 LegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
624   assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
625   if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
626     return {NotFound, LLT()};
627   const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
628   if (Aspect.Type.isPointer() &&
629       AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
630           AddrSpace2PointerActions[OpcodeIdx].end()) {
631     return {NotFound, LLT()};
632   }
633   const SmallVector<SizeAndActionsVec, 1> &Actions =
634       Aspect.Type.isPointer()
635           ? AddrSpace2PointerActions[OpcodeIdx]
636                 .find(Aspect.Type.getAddressSpace())
637                 ->second
638           : ScalarActions[OpcodeIdx];
639   if (Aspect.Idx >= Actions.size())
640     return {NotFound, LLT()};
641   const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
642   // FIXME: speed up this search, e.g. by using a results cache for repeated
643   // queries?
644   auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
645   return {SizeAndAction.second,
646           Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)
647                                  : LLT::pointer(Aspect.Type.getAddressSpace(),
648                                                 SizeAndAction.first)};
649 }
650 
651 std::pair<LegalizeAction, LLT>
findVectorLegalAction(const InstrAspect & Aspect) const652 LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
653   assert(Aspect.Type.isVector());
654   // First legalize the vector element size, then legalize the number of
655   // lanes in the vector.
656   if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
657     return {NotFound, Aspect.Type};
658   const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
659   const unsigned TypeIdx = Aspect.Idx;
660   if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
661     return {NotFound, Aspect.Type};
662   const SizeAndActionsVec &ElemSizeVec =
663       ScalarInVectorActions[OpcodeIdx][TypeIdx];
664 
665   LLT IntermediateType;
666   auto ElementSizeAndAction =
667       findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
668   IntermediateType =
669       LLT::vector(Aspect.Type.getNumElements(), ElementSizeAndAction.first);
670   if (ElementSizeAndAction.second != Legal)
671     return {ElementSizeAndAction.second, IntermediateType};
672 
673   auto i = NumElements2Actions[OpcodeIdx].find(
674       IntermediateType.getScalarSizeInBits());
675   if (i == NumElements2Actions[OpcodeIdx].end()) {
676     return {NotFound, IntermediateType};
677   }
678   const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
679   auto NumElementsAndAction =
680       findAction(NumElementsVec, IntermediateType.getNumElements());
681   return {NumElementsAndAction.second,
682           LLT::vector(NumElementsAndAction.first,
683                       IntermediateType.getScalarSizeInBits())};
684 }
685 
getExtOpcodeForWideningConstant(LLT SmallTy) const686 unsigned LegalizerInfo::getExtOpcodeForWideningConstant(LLT SmallTy) const {
687   return SmallTy.isByteSized() ? TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT;
688 }
689 
690 /// \pre Type indices of every opcode form a dense set starting from 0.
verify(const MCInstrInfo & MII) const691 void LegalizerInfo::verify(const MCInstrInfo &MII) const {
692 #ifndef NDEBUG
693   std::vector<unsigned> FailedOpcodes;
694   for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
695     const MCInstrDesc &MCID = MII.get(Opcode);
696     const unsigned NumTypeIdxs = std::accumulate(
697         MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
698         [](unsigned Acc, const MCOperandInfo &OpInfo) {
699           return OpInfo.isGenericType()
700                      ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
701                      : Acc;
702         });
703     const unsigned NumImmIdxs = std::accumulate(
704         MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
705         [](unsigned Acc, const MCOperandInfo &OpInfo) {
706           return OpInfo.isGenericImm()
707                      ? std::max(OpInfo.getGenericImmIndex() + 1U, Acc)
708                      : Acc;
709         });
710     LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
711                       << "): " << NumTypeIdxs << " type ind"
712                       << (NumTypeIdxs == 1 ? "ex" : "ices") << ", "
713                       << NumImmIdxs << " imm ind"
714                       << (NumImmIdxs == 1 ? "ex" : "ices") << "\n");
715     const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode);
716     if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
717       FailedOpcodes.push_back(Opcode);
718     else if (!RuleSet.verifyImmIdxsCoverage(NumImmIdxs))
719       FailedOpcodes.push_back(Opcode);
720   }
721   if (!FailedOpcodes.empty()) {
722     errs() << "The following opcodes have ill-defined legalization rules:";
723     for (unsigned Opcode : FailedOpcodes)
724       errs() << " " << MII.getName(Opcode);
725     errs() << "\n";
726 
727     report_fatal_error("ill-defined LegalizerInfo"
728                        ", try -debug-only=legalizer-info for details");
729   }
730 #endif
731 }
732 
733 #ifndef NDEBUG
734 // FIXME: This should be in the MachineVerifier, but it can't use the
735 // LegalizerInfo as it's currently in the separate GlobalISel library.
736 // Note that RegBankSelected property already checked in the verifier
737 // has the same layering problem, but we only use inline methods so
738 // end up not needing to link against the GlobalISel library.
machineFunctionIsIllegal(const MachineFunction & MF)739 const MachineInstr *llvm::machineFunctionIsIllegal(const MachineFunction &MF) {
740   if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
741     const MachineRegisterInfo &MRI = MF.getRegInfo();
742     for (const MachineBasicBlock &MBB : MF)
743       for (const MachineInstr &MI : MBB)
744         if (isPreISelGenericOpcode(MI.getOpcode()) &&
745             !MLI->isLegalOrCustom(MI, MRI))
746           return &MI;
747   }
748   return nullptr;
749 }
750 #endif
751