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