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 VecIt = llvm::bsearch(
548  Vec, [=](const SizeAndAction &A) { return Size < A.first; });
549  assert(VecIt != Vec.begin() && "Does Vec not start with size 1?");
550  --VecIt;
551  int VecIdx = VecIt - Vec.begin();
552 
553  LegalizeAction Action = Vec[VecIdx].second;
554  switch (Action) {
555  case Legal:
556  case Lower:
557  case Libcall:
558  case Custom:
559  return {Size, Action};
560  case FewerElements:
561  // FIXME: is this special case still needed and correct?
562  // Special case for scalarization:
563  if (Vec == SizeAndActionsVec({{1, FewerElements}}))
564  return {1, FewerElements};
566  case NarrowScalar: {
567  // The following needs to be a loop, as for now, we do allow needing to
568  // go over "Unsupported" bit sizes before finding a legalizable bit size.
569  // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8,
570  // we need to iterate over s9, and then to s32 to return (s32, Legal).
571  // If we want to get rid of the below loop, we should have stronger asserts
572  // when building the SizeAndActionsVecs, probably not allowing
573  // "Unsupported" unless at the ends of the vector.
574  for (int i = VecIdx - 1; i >= 0; --i)
575  if (!needsLegalizingToDifferentSize(Vec[i].second) &&
576  Vec[i].second != Unsupported)
577  return {Vec[i].first, Action};
578  llvm_unreachable("");
579  }
580  case WidenScalar:
581  case MoreElements: {
582  // See above, the following needs to be a loop, at least for now.
583  for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
584  if (!needsLegalizingToDifferentSize(Vec[i].second) &&
585  Vec[i].second != Unsupported)
586  return {Vec[i].first, Action};
587  llvm_unreachable("");
588  }
589  case Unsupported:
590  return {Size, Unsupported};
591  case NotFound:
592  case UseLegacyRules:
593  llvm_unreachable("NotFound");
594  }
595  llvm_unreachable("Action has an unknown enum value");
596 }
597 
598 std::pair<LegalizeAction, LLT>
599 LegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
600  assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
601  if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
602  return {NotFound, LLT()};
603  const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
604  if (Aspect.Type.isPointer() &&
605  AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
606  AddrSpace2PointerActions[OpcodeIdx].end()) {
607  return {NotFound, LLT()};
608  }
609  const SmallVector<SizeAndActionsVec, 1> &Actions =
610  Aspect.Type.isPointer()
611  ? AddrSpace2PointerActions[OpcodeIdx]
612  .find(Aspect.Type.getAddressSpace())
613  ->second
614  : ScalarActions[OpcodeIdx];
615  if (Aspect.Idx >= Actions.size())
616  return {NotFound, LLT()};
617  const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
618  // FIXME: speed up this search, e.g. by using a results cache for repeated
619  // queries?
620  auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
621  return {SizeAndAction.second,
622  Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)
623  : LLT::pointer(Aspect.Type.getAddressSpace(),
624  SizeAndAction.first)};
625 }
626 
627 std::pair<LegalizeAction, LLT>
628 LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
629  assert(Aspect.Type.isVector());
630  // First legalize the vector element size, then legalize the number of
631  // lanes in the vector.
632  if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
633  return {NotFound, Aspect.Type};
634  const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
635  const unsigned TypeIdx = Aspect.Idx;
636  if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
637  return {NotFound, Aspect.Type};
638  const SizeAndActionsVec &ElemSizeVec =
639  ScalarInVectorActions[OpcodeIdx][TypeIdx];
640 
641  LLT IntermediateType;
642  auto ElementSizeAndAction =
643  findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
644  IntermediateType =
645  LLT::vector(Aspect.Type.getNumElements(), ElementSizeAndAction.first);
646  if (ElementSizeAndAction.second != Legal)
647  return {ElementSizeAndAction.second, IntermediateType};
648 
649  auto i = NumElements2Actions[OpcodeIdx].find(
650  IntermediateType.getScalarSizeInBits());
651  if (i == NumElements2Actions[OpcodeIdx].end()) {
652  return {NotFound, IntermediateType};
653  }
654  const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
655  auto NumElementsAndAction =
656  findAction(NumElementsVec, IntermediateType.getNumElements());
657  return {NumElementsAndAction.second,
658  LLT::vector(NumElementsAndAction.first,
659  IntermediateType.getScalarSizeInBits())};
660 }
661 
662 /// \pre Type indices of every opcode form a dense set starting from 0.
663 void LegalizerInfo::verify(const MCInstrInfo &MII) const {
664 #ifndef NDEBUG
665  std::vector<unsigned> FailedOpcodes;
666  for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
667  const MCInstrDesc &MCID = MII.get(Opcode);
668  const unsigned NumTypeIdxs = std::accumulate(
669  MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
670  [](unsigned Acc, const MCOperandInfo &OpInfo) {
671  return OpInfo.isGenericType()
672  ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
673  : Acc;
674  });
675  LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
676  << "): " << NumTypeIdxs << " type ind"
677  << (NumTypeIdxs == 1 ? "ex" : "ices") << "\n");
678  const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode);
679  if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
680  FailedOpcodes.push_back(Opcode);
681  }
682  if (!FailedOpcodes.empty()) {
683  errs() << "The following opcodes have ill-defined legalization rules:";
684  for (unsigned Opcode : FailedOpcodes)
685  errs() << " " << MII.getName(Opcode);
686  errs() << "\n";
687 
688  report_fatal_error("ill-defined LegalizerInfo"
689  ", try -debug-only=legalizer-info for details");
690  }
691 #endif
692 }
693 
694 #ifndef NDEBUG
695 // FIXME: This should be in the MachineVerifier, but it can't use the
696 // LegalizerInfo as it's currently in the separate GlobalISel library.
697 // Note that RegBankSelected property already checked in the verifier
698 // has the same layering problem, but we only use inline methods so
699 // end up not needing to link against the GlobalISel library.
701  if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
702  const MachineRegisterInfo &MRI = MF.getRegInfo();
703  for (const MachineBasicBlock &MBB : MF)
704  for (const MachineInstr &MI : MBB)
705  if (isPreISelGenericOpcode(MI.getOpcode()) &&
706  !MLI->isLegalOrCustom(MI, MRI))
707  return &MI;
708  }
709  return nullptr;
710 }
711 #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
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: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
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: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