LLVM  9.0.0svn
LegalizerInfo.cpp
Go to the documentation of this file.
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 
26 #include "llvm/MC/MCInstrDesc.h"
27 #include "llvm/MC/MCInstrInfo.h"
28 #include "llvm/Support/Debug.h"
32 #include <algorithm>
33 #include <map>
34 
35 using namespace llvm;
36 using namespace LegalizeActions;
37 
38 #define DEBUG_TYPE "legalizer-info"
39 
41  "disable-gisel-legality-check",
42  cl::desc("Don't verify that MIR is fully legal between GlobalISel passes"),
43  cl::Hidden);
44 
46  OS << Opcode << ", Tys={";
47  for (const auto &Type : Types) {
48  OS << Type << ", ";
49  }
50  OS << "}, Opcode=";
51 
52  OS << Opcode << ", MMOs={";
53  for (const auto &MMODescr : MMODescrs) {
54  OS << MMODescr.SizeInBits << ", ";
55  }
56  OS << "}";
57 
58  return OS;
59 }
60 
61 #ifndef NDEBUG
62 // Make sure the rule won't (trivially) loop forever.
63 static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q,
64  const std::pair<unsigned, LLT> &Mutation) {
65  switch (Rule.getAction()) {
66  case Custom:
67  case Lower:
68  case MoreElements:
69  case FewerElements:
70  break;
71  default:
72  return Q.Types[Mutation.first] != Mutation.second;
73  }
74  return true;
75 }
76 
77 // Make sure the returned mutation makes sense for the match type.
78 static bool mutationIsSane(const LegalizeRule &Rule,
79  const LegalityQuery &Q,
80  std::pair<unsigned, LLT> Mutation) {
81  // If the user wants a custom mutation, then we can't really say much about
82  // it. Return true, and trust that they're doing the right thing.
83  if (Rule.getAction() == Custom)
84  return true;
85 
86  const unsigned TypeIdx = Mutation.first;
87  const LLT OldTy = Q.Types[TypeIdx];
88  const LLT NewTy = Mutation.second;
89 
90  switch (Rule.getAction()) {
91  case FewerElements:
92  case MoreElements: {
93  if (!OldTy.isVector())
94  return false;
95 
96  if (NewTy.isVector()) {
97  if (Rule.getAction() == FewerElements) {
98  // Make sure the element count really decreased.
99  if (NewTy.getNumElements() >= OldTy.getNumElements())
100  return false;
101  } else {
102  // Make sure the element count really increased.
103  if (NewTy.getNumElements() <= OldTy.getNumElements())
104  return false;
105  }
106  }
107 
108  // Make sure the element type didn't change.
109  return NewTy.getScalarType() == OldTy.getElementType();
110  }
111  case NarrowScalar:
112  case WidenScalar: {
113  if (OldTy.isVector()) {
114  // Number of elements should not change.
115  if (!NewTy.isVector() || OldTy.getNumElements() != NewTy.getNumElements())
116  return false;
117  } else {
118  // Both types must be vectors
119  if (NewTy.isVector())
120  return false;
121  }
122 
123  if (Rule.getAction() == NarrowScalar) {
124  // Make sure the size really decreased.
125  if (NewTy.getScalarSizeInBits() >= OldTy.getScalarSizeInBits())
126  return false;
127  } else {
128  // Make sure the size really increased.
129  if (NewTy.getScalarSizeInBits() <= OldTy.getScalarSizeInBits())
130  return false;
131  }
132 
133  return true;
134  }
135  default:
136  return true;
137  }
138 }
139 #endif
140 
142  LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
143  dbgs() << "\n");
144  if (Rules.empty()) {
145  LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
146  return {LegalizeAction::UseLegacyRules, 0, LLT{}};
147  }
148  for (const LegalizeRule &Rule : Rules) {
149  if (Rule.match(Query)) {
150  LLVM_DEBUG(dbgs() << ".. match\n");
151  std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
152  LLVM_DEBUG(dbgs() << ".. .. " << (unsigned)Rule.getAction() << ", "
153  << Mutation.first << ", " << Mutation.second << "\n");
154  assert(mutationIsSane(Rule, Query, Mutation) &&
155  "legality mutation invalid for match");
156  assert(hasNoSimpleLoops(Rule, Query, Mutation) && "Simple loop detected");
157  return {Rule.getAction(), Mutation.first, Mutation.second};
158  } else
159  LLVM_DEBUG(dbgs() << ".. no match\n");
160  }
161  LLVM_DEBUG(dbgs() << ".. unsupported\n");
162  return {LegalizeAction::Unsupported, 0, LLT{}};
163 }
164 
165 bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const {
166 #ifndef NDEBUG
167  if (Rules.empty()) {
168  LLVM_DEBUG(
169  dbgs() << ".. type index coverage check SKIPPED: no rules defined\n");
170  return true;
171  }
172  const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset();
173  if (FirstUncovered < 0) {
174  LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:"
175  " user-defined predicate detected\n");
176  return true;
177  }
178  const bool AllCovered = (FirstUncovered >= NumTypeIdxs);
179  LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered
180  << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
181  return AllCovered;
182 #else
183  return true;
184 #endif
185 }
186 
187 LegalizerInfo::LegalizerInfo() : TablesInitialized(false) {
188  // Set defaults.
189  // FIXME: these two (G_ANYEXT and G_TRUNC?) can be legalized to the
190  // fundamental load/store Jakob proposed. Once loads & stores are supported.
191  setScalarAction(TargetOpcode::G_ANYEXT, 1, {{1, Legal}});
192  setScalarAction(TargetOpcode::G_ZEXT, 1, {{1, Legal}});
193  setScalarAction(TargetOpcode::G_SEXT, 1, {{1, Legal}});
194  setScalarAction(TargetOpcode::G_TRUNC, 0, {{1, Legal}});
195  setScalarAction(TargetOpcode::G_TRUNC, 1, {{1, Legal}});
196 
197  setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}});
198  setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}});
199 
201  TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall);
203  TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
205  TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest);
207  TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
209  TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
210 
212  TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
214  TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
216  TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
218  TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
219  setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}});
220 }
221 
223  assert(TablesInitialized == false);
224 
225  for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) {
226  const unsigned Opcode = FirstOp + OpcodeIdx;
227  for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size();
228  ++TypeIdx) {
229  // 0. Collect information specified through the setAction API, i.e.
230  // for specific bit sizes.
231  // For scalar types:
232  SizeAndActionsVec ScalarSpecifiedActions;
233  // For pointer types:
234  std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions;
235  // For vector types:
236  std::map<uint16_t, SizeAndActionsVec> ElemSize2SpecifiedActions;
237  for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) {
238  const LLT Type = LLT2Action.first;
239  const LegalizeAction Action = LLT2Action.second;
240 
241  auto SizeAction = std::make_pair(Type.getSizeInBits(), Action);
242  if (Type.isPointer())
243  AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(
244  SizeAction);
245  else if (Type.isVector())
246  ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()]
247  .push_back(SizeAction);
248  else
249  ScalarSpecifiedActions.push_back(SizeAction);
250  }
251 
252  // 1. Handle scalar types
253  {
254  // Decide how to handle bit sizes for which no explicit specification
255  // was given.
257  if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() &&
258  ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
259  S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx];
260  llvm::sort(ScalarSpecifiedActions);
261  checkPartialSizeAndActionsVector(ScalarSpecifiedActions);
262  setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions));
263  }
264 
265  // 2. Handle pointer types
266  for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) {
267  llvm::sort(PointerSpecifiedActions.second);
268  checkPartialSizeAndActionsVector(PointerSpecifiedActions.second);
269  // For pointer types, we assume that there isn't a meaningfull way
270  // to change the number of bits used in the pointer.
271  setPointerAction(
272  Opcode, TypeIdx, PointerSpecifiedActions.first,
273  unsupportedForDifferentSizes(PointerSpecifiedActions.second));
274  }
275 
276  // 3. Handle vector types
277  SizeAndActionsVec ElementSizesSeen;
278  for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) {
279  llvm::sort(VectorSpecifiedActions.second);
280  const uint16_t ElementSize = VectorSpecifiedActions.first;
281  ElementSizesSeen.push_back({ElementSize, Legal});
282  checkPartialSizeAndActionsVector(VectorSpecifiedActions.second);
283  // For vector types, we assume that the best way to adapt the number
284  // of elements is to the next larger number of elements type for which
285  // the vector type is legal, unless there is no such type. In that case,
286  // legalize towards a vector type with a smaller number of elements.
287  SizeAndActionsVec NumElementsActions;
288  for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) {
289  assert(BitsizeAndAction.first % ElementSize == 0);
290  const uint16_t NumElements = BitsizeAndAction.first / ElementSize;
291  NumElementsActions.push_back({NumElements, BitsizeAndAction.second});
292  }
293  setVectorNumElementAction(
294  Opcode, TypeIdx, ElementSize,
295  moreToWiderTypesAndLessToWidest(NumElementsActions));
296  }
297  llvm::sort(ElementSizesSeen);
298  SizeChangeStrategy VectorElementSizeChangeStrategy =
300  if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() &&
301  VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
302  VectorElementSizeChangeStrategy =
303  VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx];
304  setScalarInVectorAction(
305  Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen));
306  }
307  }
308 
309  TablesInitialized = true;
310 }
311 
312 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
313 // probably going to need specialized lookup structures for various types before
314 // we have any hope of doing well with something like <13 x i3>. Even the common
315 // cases should do better than what we have now.
316 std::pair<LegalizeAction, LLT>
317 LegalizerInfo::getAspectAction(const InstrAspect &Aspect) const {
318  assert(TablesInitialized && "backend forgot to call computeTables");
319  // These *have* to be implemented for now, they're the fundamental basis of
320  // how everything else is transformed.
321  if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
322  return findScalarLegalAction(Aspect);
323  assert(Aspect.Type.isVector());
324  return findVectorLegalAction(Aspect);
325 }
326 
327 /// Helper function to get LLT for the given type index.
329  const MachineRegisterInfo &MRI, unsigned OpIdx,
330  unsigned TypeIdx) {
331  assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
332  // G_UNMERGE_VALUES has variable number of operands, but there is only
333  // one source type and one destination type as all destinations must be the
334  // same type. So, get the last operand if TypeIdx == 1.
335  if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
336  return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
337  return MRI.getType(MI.getOperand(OpIdx).getReg());
338 }
339 
340 unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
341  assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
342  return Opcode - FirstOp;
343 }
344 
345 unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
346  unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
347  if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
348  LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
349  << "\n");
350  OpcodeIdx = getOpcodeIdxForOpcode(Alias);
351  LLVM_DEBUG(dbgs() << ".. opcode " << Alias << " is aliased to "
352  << RulesForOpcode[OpcodeIdx].getAlias() << "\n");
353  assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
354  }
355 
356  return OpcodeIdx;
357 }
358 
359 const LegalizeRuleSet &
360 LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
361  unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
362  return RulesForOpcode[OpcodeIdx];
363 }
364 
366  unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
367  auto &Result = RulesForOpcode[OpcodeIdx];
368  assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
369  return Result;
370 }
371 
373  std::initializer_list<unsigned> Opcodes) {
374  unsigned Representative = *Opcodes.begin();
375 
376  assert(!empty(Opcodes) && Opcodes.begin() + 1 != Opcodes.end() &&
377  "Initializer list must have at least two opcodes");
378 
379  for (auto I = Opcodes.begin() + 1, E = Opcodes.end(); I != E; ++I)
380  aliasActionDefinitions(Representative, *I);
381 
382  auto &Return = getActionDefinitionsBuilder(Representative);
383  Return.setIsAliasedByAnother();
384  return Return;
385 }
386 
388  unsigned OpcodeFrom) {
389  assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
390  assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
391  const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
392  RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
393 }
394 
399  return Step;
400  }
401 
402  for (unsigned i = 0; i < Query.Types.size(); ++i) {
403  auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]});
404  if (Action.first != Legal) {
405  LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i
406  << " Action=" << (unsigned)Action.first << ", "
407  << Action.second << "\n");
408  return {Action.first, i, Action.second};
409  } else
410  LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n");
411  }
412  LLVM_DEBUG(dbgs() << ".. (legacy) Legal\n");
413  return {Legal, 0, LLT{}};
414 }
415 
418  const MachineRegisterInfo &MRI) const {
419  SmallVector<LLT, 2> Types;
420  SmallBitVector SeenTypes(8);
421  const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
422  // FIXME: probably we'll need to cache the results here somehow?
423  for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
424  if (!OpInfo[i].isGenericType())
425  continue;
426 
427  // We must only record actions once for each TypeIdx; otherwise we'd
428  // try to legalize operands multiple times down the line.
429  unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
430  if (SeenTypes[TypeIdx])
431  continue;
432 
433  SeenTypes.set(TypeIdx);
434 
435  LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
436  Types.push_back(Ty);
437  }
438 
440  for (const auto &MMO : MI.memoperands())
441  MemDescrs.push_back({8 * MMO->getSize() /* in bits */,
442  8 * MMO->getAlignment(),
443  MMO->getOrdering()});
444 
445  return getAction({MI.getOpcode(), Types, MemDescrs});
446 }
447 
449  const MachineRegisterInfo &MRI) const {
450  return getAction(MI, MRI).Action == Legal;
451 }
452 
454  const MachineRegisterInfo &MRI) const {
455  auto Action = getAction(MI, MRI).Action;
456  // If the action is custom, it may not necessarily modify the instruction,
457  // so we have to assume it's legal.
458  return Action == Legal || Action == Custom;
459 }
460 
462  MachineIRBuilder &MIRBuilder,
463  GISelChangeObserver &Observer) const {
464  return false;
465 }
466 
469  const SizeAndActionsVec &v, LegalizeAction IncreaseAction,
470  LegalizeAction DecreaseAction) {
471  SizeAndActionsVec result;
472  unsigned LargestSizeSoFar = 0;
473  if (v.size() >= 1 && v[0].first != 1)
474  result.push_back({1, IncreaseAction});
475  for (size_t i = 0; i < v.size(); ++i) {
476  result.push_back(v[i]);
477  LargestSizeSoFar = v[i].first;
478  if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) {
479  result.push_back({LargestSizeSoFar + 1, IncreaseAction});
480  LargestSizeSoFar = v[i].first + 1;
481  }
482  }
483  result.push_back({LargestSizeSoFar + 1, DecreaseAction});
484  return result;
485 }
486 
489  const SizeAndActionsVec &v, LegalizeAction DecreaseAction,
490  LegalizeAction IncreaseAction) {
491  SizeAndActionsVec result;
492  if (v.size() == 0 || v[0].first != 1)
493  result.push_back({1, IncreaseAction});
494  for (size_t i = 0; i < v.size(); ++i) {
495  result.push_back(v[i]);
496  if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) {
497  result.push_back({v[i].first + 1, DecreaseAction});
498  }
499  }
500  return result;
501 }
502 
504 LegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
505  assert(Size >= 1);
506  // Find the last element in Vec that has a bitsize equal to or smaller than
507  // the requested bit size.
508  // That is the element just before the first element that is bigger than Size.
509  auto VecIt = llvm::bsearch(
510  Vec, [=](const SizeAndAction &A) { return Size < A.first; });
511  assert(VecIt != Vec.begin() && "Does Vec not start with size 1?");
512  --VecIt;
513  int VecIdx = VecIt - Vec.begin();
514 
515  LegalizeAction Action = Vec[VecIdx].second;
516  switch (Action) {
517  case Legal:
518  case Lower:
519  case Libcall:
520  case Custom:
521  return {Size, Action};
522  case FewerElements:
523  // FIXME: is this special case still needed and correct?
524  // Special case for scalarization:
525  if (Vec == SizeAndActionsVec({{1, FewerElements}}))
526  return {1, FewerElements};
528  case NarrowScalar: {
529  // The following needs to be a loop, as for now, we do allow needing to
530  // go over "Unsupported" bit sizes before finding a legalizable bit size.
531  // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8,
532  // we need to iterate over s9, and then to s32 to return (s32, Legal).
533  // If we want to get rid of the below loop, we should have stronger asserts
534  // when building the SizeAndActionsVecs, probably not allowing
535  // "Unsupported" unless at the ends of the vector.
536  for (int i = VecIdx - 1; i >= 0; --i)
537  if (!needsLegalizingToDifferentSize(Vec[i].second) &&
538  Vec[i].second != Unsupported)
539  return {Vec[i].first, Action};
540  llvm_unreachable("");
541  }
542  case WidenScalar:
543  case MoreElements: {
544  // See above, the following needs to be a loop, at least for now.
545  for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
546  if (!needsLegalizingToDifferentSize(Vec[i].second) &&
547  Vec[i].second != Unsupported)
548  return {Vec[i].first, Action};
549  llvm_unreachable("");
550  }
551  case Unsupported:
552  return {Size, Unsupported};
553  case NotFound:
554  case UseLegacyRules:
555  llvm_unreachable("NotFound");
556  }
557  llvm_unreachable("Action has an unknown enum value");
558 }
559 
560 std::pair<LegalizeAction, LLT>
561 LegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
562  assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
563  if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
564  return {NotFound, LLT()};
565  const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
566  if (Aspect.Type.isPointer() &&
567  AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
568  AddrSpace2PointerActions[OpcodeIdx].end()) {
569  return {NotFound, LLT()};
570  }
571  const SmallVector<SizeAndActionsVec, 1> &Actions =
572  Aspect.Type.isPointer()
573  ? AddrSpace2PointerActions[OpcodeIdx]
574  .find(Aspect.Type.getAddressSpace())
575  ->second
576  : ScalarActions[OpcodeIdx];
577  if (Aspect.Idx >= Actions.size())
578  return {NotFound, LLT()};
579  const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
580  // FIXME: speed up this search, e.g. by using a results cache for repeated
581  // queries?
582  auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
583  return {SizeAndAction.second,
584  Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)
585  : LLT::pointer(Aspect.Type.getAddressSpace(),
586  SizeAndAction.first)};
587 }
588 
589 std::pair<LegalizeAction, LLT>
590 LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
591  assert(Aspect.Type.isVector());
592  // First legalize the vector element size, then legalize the number of
593  // lanes in the vector.
594  if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
595  return {NotFound, Aspect.Type};
596  const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
597  const unsigned TypeIdx = Aspect.Idx;
598  if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
599  return {NotFound, Aspect.Type};
600  const SizeAndActionsVec &ElemSizeVec =
601  ScalarInVectorActions[OpcodeIdx][TypeIdx];
602 
603  LLT IntermediateType;
604  auto ElementSizeAndAction =
605  findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
606  IntermediateType =
607  LLT::vector(Aspect.Type.getNumElements(), ElementSizeAndAction.first);
608  if (ElementSizeAndAction.second != Legal)
609  return {ElementSizeAndAction.second, IntermediateType};
610 
611  auto i = NumElements2Actions[OpcodeIdx].find(
612  IntermediateType.getScalarSizeInBits());
613  if (i == NumElements2Actions[OpcodeIdx].end()) {
614  return {NotFound, IntermediateType};
615  }
616  const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
617  auto NumElementsAndAction =
618  findAction(NumElementsVec, IntermediateType.getNumElements());
619  return {NumElementsAndAction.second,
620  LLT::vector(NumElementsAndAction.first,
621  IntermediateType.getScalarSizeInBits())};
622 }
623 
624 /// \pre Type indices of every opcode form a dense set starting from 0.
625 void LegalizerInfo::verify(const MCInstrInfo &MII) const {
626 #ifndef NDEBUG
627  std::vector<unsigned> FailedOpcodes;
628  for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
629  const MCInstrDesc &MCID = MII.get(Opcode);
630  const unsigned NumTypeIdxs = std::accumulate(
631  MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
632  [](unsigned Acc, const MCOperandInfo &OpInfo) {
633  return OpInfo.isGenericType()
634  ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
635  : Acc;
636  });
637  LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
638  << "): " << NumTypeIdxs << " type ind"
639  << (NumTypeIdxs == 1 ? "ex" : "ices") << "\n");
640  const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode);
641  if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
642  FailedOpcodes.push_back(Opcode);
643  }
644  if (!FailedOpcodes.empty()) {
645  errs() << "The following opcodes have ill-defined legalization rules:";
646  for (unsigned Opcode : FailedOpcodes)
647  errs() << " " << MII.getName(Opcode);
648  errs() << "\n";
649 
650  report_fatal_error("ill-defined LegalizerInfo"
651  ", try -debug-only=legalizer-info for details");
652  }
653 #endif
654 }
655 
656 #ifndef NDEBUG
657 // FIXME: This should be in the MachineVerifier, but it can't use the
658 // LegalizerInfo as it's currently in the separate GlobalISel library.
659 // Note that RegBankSelected property already checked in the verifier
660 // has the same layering problem, but we only use inline methods so
661 // end up not needing to link against the GlobalISel library.
663  if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
664  const MachineRegisterInfo &MRI = MF.getRegInfo();
665  for (const MachineBasicBlock &MBB : MF)
666  for (const MachineInstr &MI : MBB)
667  if (isPreISelGenericOpcode(MI.getOpcode()) &&
668  !MLI->isLegalOrCustom(MI, MRI))
669  return &MI;
670  }
671  return nullptr;
672 }
673 #endif
bool isLegalOrCustom(const MachineInstr &MI, const MachineRegisterInfo &MRI) const
const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:233
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
static LLT pointer(unsigned AddressSpace, unsigned SizeInBits)
Get a low-level pointer in the given address space.
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
This is a &#39;bitvector&#39; (really, a variable-sized bit array), optimized for the case when the array is ...
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:139
This class represents lattice values for constants.
Definition: AllocatorList.h:23
The result of a query.
static SizeAndActionsVec increaseToLargerTypesAndDecreaseToLargest(const SizeAndActionsVec &v, LegalizeAction IncreaseAction, LegalizeAction DecreaseAction)
Helper function to implement many typical SizeChangeStrategy functions.
unsigned getScalarSizeInBits() const
The operation should be implemented in terms of a wider scalar base-type.
Definition: LegalizerInfo.h:57
raw_ostream & print(raw_ostream &OS) const
std::function< SizeAndActionsVec(const SizeAndActionsVec &v)> SizeChangeStrategy
The LegalityQuery object bundles together all the information that&#39;s needed to decide whether a given...
bool isScalar() const
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:163
unsigned getReg() const
getReg - Returns the register number.
static LLT getTypeFromTypeIdx(const MachineInstr &MI, const MachineRegisterInfo &MRI, unsigned OpIdx, unsigned TypeIdx)
Helper function to get LLT for the given type index.
std::vector< SizeAndAction > SizeAndActionsVec
The (vector) operation should be implemented by splitting it into sub-vectors where the operation is ...
Definition: LegalizerInfo.h:62
Libcall
RTLIB::Libcall enum - This enum defines all of the runtime library calls the backend can emit...
static SizeAndActionsVec narrowToSmallerAndUnsupportedIfTooSmall(const SizeAndActionsVec &v)
LLT getScalarType() const
LLT getType(unsigned Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register...
const_opInfo_iterator opInfo_begin() const
Definition: MCInstrDesc.h:214
unsigned second
const LegalizeRuleSet & getActionDefinitions(unsigned Opcode) const
Get the action definitions for the given opcode.
static SizeAndActionsVec unsupportedForDifferentSizes(const SizeAndActionsVec &v)
A SizeChangeStrategy for the common case where legalization for a particular operation consists of on...
The operation should be synthesized from multiple instructions acting on a narrower scalar base-type...
Definition: LegalizerInfo.h:52
bool isVector() const
LegalizeActionStep getAction(const LegalityQuery &Query) const
Determine what action should be taken to legalize the described instruction.
static SizeAndActionsVec widenToLargerTypesUnsupportedOtherwise(const SizeAndActionsVec &v)
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:210
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:411
LegalizeAction getAction() const
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:408
This operation is completely unsupported on the target.
Definition: LegalizerInfo.h:85
LLT getElementType() const
Returns the vector&#39;s element type. Only valid for vector types.
void verify(const MCInstrInfo &MII) const
Perform simple self-diagnostic and assert if there is anything obviously wrong with the actions set u...
PowerPC VSX FMA Mutation
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:405
The (vector) operation should be implemented by widening the input vector and ignoring the lanes adde...
Definition: LegalizerInfo.h:68
void computeTables()
Compute any ancillary tables needed to quickly decide how an operation should be handled.
void aliasActionDefinitions(unsigned OpcodeTo, unsigned OpcodeFrom)
static LLT scalar(unsigned SizeInBits)
Get a low-level scalar or aggregate "bag of bits".
The operation itself must be expressed in terms of simpler actions on this target.
Definition: LegalizerInfo.h:72
size_t bsearch(size_t Lo, size_t Hi, Predicate P)
Binary search for the first index where a predicate is true.
Definition: STLExtras.h:1329
bool isGenericType() const
Definition: MCInstrDesc.h:97
virtual const LegalizerInfo * getLegalizerInfo() const
Abstract class that contains various methods for clients to notify about changes. ...
static SizeAndActionsVec decreaseToSmallerTypesAndIncreaseToSmallest(const SizeAndActionsVec &v, LegalizeAction DecreaseAction, LegalizeAction IncreaseAction)
Helper function to implement many typical SizeChangeStrategy functions.
unsigned const MachineRegisterInfo * MRI
ArrayRef< MachineMemOperand * > memoperands() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:515
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
Sentinel value for when no action was found in the specified table.
Definition: LegalizerInfo.h:88
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Helper class to build MachineInstr.
Interface to description of machine instruction set.
Definition: MCInstrInfo.h:23
bool isLegal(const LegalityQuery &Query) const
bool verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const
Check if there is no type index which is obviously not handled by the LegalizeRuleSet in any way at a...
unsigned getAddressSpace() const
Legalization is decided based on an instruction&#39;s opcode, which type slot we&#39;re considering, and what the existing type is.
StringRef getName(unsigned Opcode) const
Returns the name for the instructions with the given opcode.
Definition: MCInstrInfo.h:50
size_t size() const
Definition: SmallVector.h:52
cl::opt< bool > DisableGISelLegalityCheck
LegalizeRuleSet & getActionDefinitionsBuilder(unsigned Opcode)
Get the action definition builder for the given opcode.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1115
SmallBitVector & set()
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:209
const MachineInstr * machineFunctionIsIllegal(const MachineFunction &MF)
Checks that MIR is fully legal, returns an illegal instruction if it&#39;s not, nullptr otherwise...
auto size(R &&Range, typename std::enable_if< std::is_same< typename std::iterator_traits< decltype(Range.begin())>::iterator_category, std::random_access_iterator_tag >::value, void >::type *=nullptr) -> decltype(std::distance(Range.begin(), Range.end()))
Get the size of a range.
Definition: STLExtras.h:1166
static bool mutationIsSane(const LegalizeRule &Rule, const LegalityQuery &Q, std::pair< unsigned, LLT > Mutation)
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
unsigned getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
The target wants to do something special with this combination of operand and type.
Definition: LegalizerInfo.h:81
unsigned getOpcodeIdxForOpcode(unsigned Opcode) const
virtual bool legalizeCustom(MachineInstr &MI, MachineRegisterInfo &MRI, MachineIRBuilder &MIRBuilder, GISelChangeObserver &Observer) const
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
static unsigned getReg(const void *D, unsigned RC, unsigned RegNo)
A single rule in a legalizer info ruleset.
bool isPointer() const
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
Representation of each machine instruction.
Definition: MachineInstr.h:63
LegalizeAction Action
The action to take or the final answer.
static bool needsLegalizingToDifferentSize(const LegalizeAction Action)
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Fall back onto the old rules.
Definition: LegalizerInfo.h:92
static SizeAndActionsVec widenToLargerTypesAndNarrowToLargest(const SizeAndActionsVec &v)
A SizeChangeStrategy for the common case where legalization for a particular operation consists of wi...
static SizeAndActionsVec moreToWiderTypesAndLessToWidest(const SizeAndActionsVec &v)
A SizeChangeStrategy for the common case where legalization for a particular vector operation consist...
LegalizeActionStep apply(const LegalityQuery &Query) const
Apply the ruleset to the given LegalityQuery.
ArrayRef< LLT > Types
const_opInfo_iterator opInfo_end() const
Definition: MCInstrDesc.h:215
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:44
void aliasTo(unsigned Opcode)
#define I(x, y, z)
Definition: MD5.cpp:58
void setLegalizeScalarToDifferentSizeStrategy(const unsigned Opcode, const unsigned TypeIdx, SizeChangeStrategy S)
The setAction calls record the non-size-changing legalization actions to take on specificly-sized typ...
uint32_t Size
Definition: Profile.cpp:46
static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q, const std::pair< unsigned, LLT > &Mutation)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool isPreISelGenericOpcode(unsigned Opcode)
Check whether the given Opcode is a generic opcode that is not supposed to appear after ISel...
Definition: TargetOpcodes.h:30
uint16_t getNumElements() const
Returns the number of elements in a vector LLT.
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:250
const MCOperandInfo * OpInfo
Definition: MCInstrDesc.h:174
unsigned getActionDefinitionsIdx(unsigned Opcode) const
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
unsigned getGenericTypeIndex() const
Definition: MCInstrDesc.h:102
IRTranslator LLVM IR MI
static LLT vector(uint16_t NumElements, unsigned ScalarSizeInBits)
Get a low-level vector of some number of elements and element width.
This holds information about one operand of a machine instruction, indicating the register class for ...
Definition: MCInstrDesc.h:66
#define LLVM_DEBUG(X)
Definition: Debug.h:122
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:413
The operation is expected to be selectable directly by the target, and no transformation is necessary...
Definition: LegalizerInfo.h:47
std::pair< uint16_t, LegalizeAction > SizeAndAction