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