LLVM  10.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  if (NumTypeIdxs > 0)
219  LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered
220  << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
221  return AllCovered;
222 #else
223  return true;
224 #endif
225 }
226 
227 bool LegalizeRuleSet::verifyImmIdxsCoverage(unsigned NumImmIdxs) const {
228 #ifndef NDEBUG
229  if (Rules.empty()) {
230  LLVM_DEBUG(
231  dbgs() << ".. imm index coverage check SKIPPED: no rules defined\n");
232  return true;
233  }
234  const int64_t FirstUncovered = ImmIdxsCovered.find_first_unset();
235  if (FirstUncovered < 0) {
236  LLVM_DEBUG(dbgs() << ".. imm index coverage check SKIPPED:"
237  " user-defined predicate detected\n");
238  return true;
239  }
240  const bool AllCovered = (FirstUncovered >= NumImmIdxs);
241  LLVM_DEBUG(dbgs() << ".. the first uncovered imm index: " << FirstUncovered
242  << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
243  return AllCovered;
244 #else
245  return true;
246 #endif
247 }
248 
249 LegalizerInfo::LegalizerInfo() : TablesInitialized(false) {
250  // Set defaults.
251  // FIXME: these two (G_ANYEXT and G_TRUNC?) can be legalized to the
252  // fundamental load/store Jakob proposed. Once loads & stores are supported.
253  setScalarAction(TargetOpcode::G_ANYEXT, 1, {{1, Legal}});
254  setScalarAction(TargetOpcode::G_ZEXT, 1, {{1, Legal}});
255  setScalarAction(TargetOpcode::G_SEXT, 1, {{1, Legal}});
256  setScalarAction(TargetOpcode::G_TRUNC, 0, {{1, Legal}});
257  setScalarAction(TargetOpcode::G_TRUNC, 1, {{1, Legal}});
258 
259  setScalarAction(TargetOpcode::G_INTRINSIC, 0, {{1, Legal}});
260  setScalarAction(TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS, 0, {{1, Legal}});
261 
263  TargetOpcode::G_IMPLICIT_DEF, 0, narrowToSmallerAndUnsupportedIfTooSmall);
265  TargetOpcode::G_ADD, 0, widenToLargerTypesAndNarrowToLargest);
267  TargetOpcode::G_OR, 0, widenToLargerTypesAndNarrowToLargest);
269  TargetOpcode::G_LOAD, 0, narrowToSmallerAndUnsupportedIfTooSmall);
271  TargetOpcode::G_STORE, 0, narrowToSmallerAndUnsupportedIfTooSmall);
272 
274  TargetOpcode::G_BRCOND, 0, widenToLargerTypesUnsupportedOtherwise);
276  TargetOpcode::G_INSERT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
278  TargetOpcode::G_EXTRACT, 0, narrowToSmallerAndUnsupportedIfTooSmall);
280  TargetOpcode::G_EXTRACT, 1, narrowToSmallerAndUnsupportedIfTooSmall);
281  setScalarAction(TargetOpcode::G_FNEG, 0, {{1, Lower}});
282 }
283 
285  assert(TablesInitialized == false);
286 
287  for (unsigned OpcodeIdx = 0; OpcodeIdx <= LastOp - FirstOp; ++OpcodeIdx) {
288  const unsigned Opcode = FirstOp + OpcodeIdx;
289  for (unsigned TypeIdx = 0; TypeIdx != SpecifiedActions[OpcodeIdx].size();
290  ++TypeIdx) {
291  // 0. Collect information specified through the setAction API, i.e.
292  // for specific bit sizes.
293  // For scalar types:
294  SizeAndActionsVec ScalarSpecifiedActions;
295  // For pointer types:
296  std::map<uint16_t, SizeAndActionsVec> AddressSpace2SpecifiedActions;
297  // For vector types:
298  std::map<uint16_t, SizeAndActionsVec> ElemSize2SpecifiedActions;
299  for (auto LLT2Action : SpecifiedActions[OpcodeIdx][TypeIdx]) {
300  const LLT Type = LLT2Action.first;
301  const LegalizeAction Action = LLT2Action.second;
302 
303  auto SizeAction = std::make_pair(Type.getSizeInBits(), Action);
304  if (Type.isPointer())
305  AddressSpace2SpecifiedActions[Type.getAddressSpace()].push_back(
306  SizeAction);
307  else if (Type.isVector())
308  ElemSize2SpecifiedActions[Type.getElementType().getSizeInBits()]
309  .push_back(SizeAction);
310  else
311  ScalarSpecifiedActions.push_back(SizeAction);
312  }
313 
314  // 1. Handle scalar types
315  {
316  // Decide how to handle bit sizes for which no explicit specification
317  // was given.
319  if (TypeIdx < ScalarSizeChangeStrategies[OpcodeIdx].size() &&
320  ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
321  S = ScalarSizeChangeStrategies[OpcodeIdx][TypeIdx];
322  llvm::sort(ScalarSpecifiedActions);
323  checkPartialSizeAndActionsVector(ScalarSpecifiedActions);
324  setScalarAction(Opcode, TypeIdx, S(ScalarSpecifiedActions));
325  }
326 
327  // 2. Handle pointer types
328  for (auto PointerSpecifiedActions : AddressSpace2SpecifiedActions) {
329  llvm::sort(PointerSpecifiedActions.second);
330  checkPartialSizeAndActionsVector(PointerSpecifiedActions.second);
331  // For pointer types, we assume that there isn't a meaningfull way
332  // to change the number of bits used in the pointer.
333  setPointerAction(
334  Opcode, TypeIdx, PointerSpecifiedActions.first,
335  unsupportedForDifferentSizes(PointerSpecifiedActions.second));
336  }
337 
338  // 3. Handle vector types
339  SizeAndActionsVec ElementSizesSeen;
340  for (auto VectorSpecifiedActions : ElemSize2SpecifiedActions) {
341  llvm::sort(VectorSpecifiedActions.second);
342  const uint16_t ElementSize = VectorSpecifiedActions.first;
343  ElementSizesSeen.push_back({ElementSize, Legal});
344  checkPartialSizeAndActionsVector(VectorSpecifiedActions.second);
345  // For vector types, we assume that the best way to adapt the number
346  // of elements is to the next larger number of elements type for which
347  // the vector type is legal, unless there is no such type. In that case,
348  // legalize towards a vector type with a smaller number of elements.
349  SizeAndActionsVec NumElementsActions;
350  for (SizeAndAction BitsizeAndAction : VectorSpecifiedActions.second) {
351  assert(BitsizeAndAction.first % ElementSize == 0);
352  const uint16_t NumElements = BitsizeAndAction.first / ElementSize;
353  NumElementsActions.push_back({NumElements, BitsizeAndAction.second});
354  }
355  setVectorNumElementAction(
356  Opcode, TypeIdx, ElementSize,
357  moreToWiderTypesAndLessToWidest(NumElementsActions));
358  }
359  llvm::sort(ElementSizesSeen);
360  SizeChangeStrategy VectorElementSizeChangeStrategy =
362  if (TypeIdx < VectorElementSizeChangeStrategies[OpcodeIdx].size() &&
363  VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx] != nullptr)
364  VectorElementSizeChangeStrategy =
365  VectorElementSizeChangeStrategies[OpcodeIdx][TypeIdx];
366  setScalarInVectorAction(
367  Opcode, TypeIdx, VectorElementSizeChangeStrategy(ElementSizesSeen));
368  }
369  }
370 
371  TablesInitialized = true;
372 }
373 
374 // FIXME: inefficient implementation for now. Without ComputeValueVTs we're
375 // probably going to need specialized lookup structures for various types before
376 // we have any hope of doing well with something like <13 x i3>. Even the common
377 // cases should do better than what we have now.
378 std::pair<LegalizeAction, LLT>
379 LegalizerInfo::getAspectAction(const InstrAspect &Aspect) const {
380  assert(TablesInitialized && "backend forgot to call computeTables");
381  // These *have* to be implemented for now, they're the fundamental basis of
382  // how everything else is transformed.
383  if (Aspect.Type.isScalar() || Aspect.Type.isPointer())
384  return findScalarLegalAction(Aspect);
385  assert(Aspect.Type.isVector());
386  return findVectorLegalAction(Aspect);
387 }
388 
389 /// Helper function to get LLT for the given type index.
391  const MachineRegisterInfo &MRI, unsigned OpIdx,
392  unsigned TypeIdx) {
393  assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
394  // G_UNMERGE_VALUES has variable number of operands, but there is only
395  // one source type and one destination type as all destinations must be the
396  // same type. So, get the last operand if TypeIdx == 1.
397  if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
398  return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
399  return MRI.getType(MI.getOperand(OpIdx).getReg());
400 }
401 
402 unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
403  assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
404  return Opcode - FirstOp;
405 }
406 
407 unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
408  unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
409  if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
410  LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
411  << "\n");
412  OpcodeIdx = getOpcodeIdxForOpcode(Alias);
413  assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
414  }
415 
416  return OpcodeIdx;
417 }
418 
419 const LegalizeRuleSet &
420 LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
421  unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
422  return RulesForOpcode[OpcodeIdx];
423 }
424 
426  unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
427  auto &Result = RulesForOpcode[OpcodeIdx];
428  assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
429  return Result;
430 }
431 
433  std::initializer_list<unsigned> Opcodes) {
434  unsigned Representative = *Opcodes.begin();
435 
436  assert(!empty(Opcodes) && Opcodes.begin() + 1 != Opcodes.end() &&
437  "Initializer list must have at least two opcodes");
438 
439  for (auto I = Opcodes.begin() + 1, E = Opcodes.end(); I != E; ++I)
440  aliasActionDefinitions(Representative, *I);
441 
442  auto &Return = getActionDefinitionsBuilder(Representative);
443  Return.setIsAliasedByAnother();
444  return Return;
445 }
446 
448  unsigned OpcodeFrom) {
449  assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
450  assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
451  const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
452  RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
453 }
454 
459  return Step;
460  }
461 
462  for (unsigned i = 0; i < Query.Types.size(); ++i) {
463  auto Action = getAspectAction({Query.Opcode, i, Query.Types[i]});
464  if (Action.first != Legal) {
465  LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Action="
466  << Action.first << ", " << Action.second << "\n");
467  return {Action.first, i, Action.second};
468  } else
469  LLVM_DEBUG(dbgs() << ".. (legacy) Type " << i << " Legal\n");
470  }
471  LLVM_DEBUG(dbgs() << ".. (legacy) Legal\n");
472  return {Legal, 0, LLT{}};
473 }
474 
477  const MachineRegisterInfo &MRI) const {
478  SmallVector<LLT, 2> Types;
479  SmallBitVector SeenTypes(8);
480  const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
481  // FIXME: probably we'll need to cache the results here somehow?
482  for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
483  if (!OpInfo[i].isGenericType())
484  continue;
485 
486  // We must only record actions once for each TypeIdx; otherwise we'd
487  // try to legalize operands multiple times down the line.
488  unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
489  if (SeenTypes[TypeIdx])
490  continue;
491 
492  SeenTypes.set(TypeIdx);
493 
494  LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
495  Types.push_back(Ty);
496  }
497 
499  for (const auto &MMO : MI.memoperands())
500  MemDescrs.push_back({8 * MMO->getSize() /* in bits */,
501  8 * MMO->getAlignment(),
502  MMO->getOrdering()});
503 
504  return getAction({MI.getOpcode(), Types, MemDescrs});
505 }
506 
508  const MachineRegisterInfo &MRI) const {
509  return getAction(MI, MRI).Action == Legal;
510 }
511 
513  const MachineRegisterInfo &MRI) const {
514  auto Action = getAction(MI, MRI).Action;
515  // If the action is custom, it may not necessarily modify the instruction,
516  // so we have to assume it's legal.
517  return Action == Legal || Action == Custom;
518 }
519 
521  MachineIRBuilder &MIRBuilder,
522  GISelChangeObserver &Observer) const {
523  return false;
524 }
525 
528  const SizeAndActionsVec &v, LegalizeAction IncreaseAction,
529  LegalizeAction DecreaseAction) {
530  SizeAndActionsVec result;
531  unsigned LargestSizeSoFar = 0;
532  if (v.size() >= 1 && v[0].first != 1)
533  result.push_back({1, IncreaseAction});
534  for (size_t i = 0; i < v.size(); ++i) {
535  result.push_back(v[i]);
536  LargestSizeSoFar = v[i].first;
537  if (i + 1 < v.size() && v[i + 1].first != v[i].first + 1) {
538  result.push_back({LargestSizeSoFar + 1, IncreaseAction});
539  LargestSizeSoFar = v[i].first + 1;
540  }
541  }
542  result.push_back({LargestSizeSoFar + 1, DecreaseAction});
543  return result;
544 }
545 
548  const SizeAndActionsVec &v, LegalizeAction DecreaseAction,
549  LegalizeAction IncreaseAction) {
550  SizeAndActionsVec result;
551  if (v.size() == 0 || v[0].first != 1)
552  result.push_back({1, IncreaseAction});
553  for (size_t i = 0; i < v.size(); ++i) {
554  result.push_back(v[i]);
555  if (i + 1 == v.size() || v[i + 1].first != v[i].first + 1) {
556  result.push_back({v[i].first + 1, DecreaseAction});
557  }
558  }
559  return result;
560 }
561 
563 LegalizerInfo::findAction(const SizeAndActionsVec &Vec, const uint32_t Size) {
564  assert(Size >= 1);
565  // Find the last element in Vec that has a bitsize equal to or smaller than
566  // the requested bit size.
567  // That is the element just before the first element that is bigger than Size.
568  auto It = partition_point(
569  Vec, [=](const SizeAndAction &A) { return A.first <= Size; });
570  assert(It != Vec.begin() && "Does Vec not start with size 1?");
571  int VecIdx = It - Vec.begin() - 1;
572 
573  LegalizeAction Action = Vec[VecIdx].second;
574  switch (Action) {
575  case Legal:
576  case Lower:
577  case Libcall:
578  case Custom:
579  return {Size, Action};
580  case FewerElements:
581  // FIXME: is this special case still needed and correct?
582  // Special case for scalarization:
583  if (Vec == SizeAndActionsVec({{1, FewerElements}}))
584  return {1, FewerElements};
586  case NarrowScalar: {
587  // The following needs to be a loop, as for now, we do allow needing to
588  // go over "Unsupported" bit sizes before finding a legalizable bit size.
589  // e.g. (s8, WidenScalar), (s9, Unsupported), (s32, Legal). if Size==8,
590  // we need to iterate over s9, and then to s32 to return (s32, Legal).
591  // If we want to get rid of the below loop, we should have stronger asserts
592  // when building the SizeAndActionsVecs, probably not allowing
593  // "Unsupported" unless at the ends of the vector.
594  for (int i = VecIdx - 1; i >= 0; --i)
595  if (!needsLegalizingToDifferentSize(Vec[i].second) &&
596  Vec[i].second != Unsupported)
597  return {Vec[i].first, Action};
598  llvm_unreachable("");
599  }
600  case WidenScalar:
601  case MoreElements: {
602  // See above, the following needs to be a loop, at least for now.
603  for (std::size_t i = VecIdx + 1; i < Vec.size(); ++i)
604  if (!needsLegalizingToDifferentSize(Vec[i].second) &&
605  Vec[i].second != Unsupported)
606  return {Vec[i].first, Action};
607  llvm_unreachable("");
608  }
609  case Unsupported:
610  return {Size, Unsupported};
611  case NotFound:
612  case UseLegacyRules:
613  llvm_unreachable("NotFound");
614  }
615  llvm_unreachable("Action has an unknown enum value");
616 }
617 
618 std::pair<LegalizeAction, LLT>
619 LegalizerInfo::findScalarLegalAction(const InstrAspect &Aspect) const {
620  assert(Aspect.Type.isScalar() || Aspect.Type.isPointer());
621  if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
622  return {NotFound, LLT()};
623  const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
624  if (Aspect.Type.isPointer() &&
625  AddrSpace2PointerActions[OpcodeIdx].find(Aspect.Type.getAddressSpace()) ==
626  AddrSpace2PointerActions[OpcodeIdx].end()) {
627  return {NotFound, LLT()};
628  }
629  const SmallVector<SizeAndActionsVec, 1> &Actions =
630  Aspect.Type.isPointer()
631  ? AddrSpace2PointerActions[OpcodeIdx]
632  .find(Aspect.Type.getAddressSpace())
633  ->second
634  : ScalarActions[OpcodeIdx];
635  if (Aspect.Idx >= Actions.size())
636  return {NotFound, LLT()};
637  const SizeAndActionsVec &Vec = Actions[Aspect.Idx];
638  // FIXME: speed up this search, e.g. by using a results cache for repeated
639  // queries?
640  auto SizeAndAction = findAction(Vec, Aspect.Type.getSizeInBits());
641  return {SizeAndAction.second,
642  Aspect.Type.isScalar() ? LLT::scalar(SizeAndAction.first)
643  : LLT::pointer(Aspect.Type.getAddressSpace(),
644  SizeAndAction.first)};
645 }
646 
647 std::pair<LegalizeAction, LLT>
648 LegalizerInfo::findVectorLegalAction(const InstrAspect &Aspect) const {
649  assert(Aspect.Type.isVector());
650  // First legalize the vector element size, then legalize the number of
651  // lanes in the vector.
652  if (Aspect.Opcode < FirstOp || Aspect.Opcode > LastOp)
653  return {NotFound, Aspect.Type};
654  const unsigned OpcodeIdx = getOpcodeIdxForOpcode(Aspect.Opcode);
655  const unsigned TypeIdx = Aspect.Idx;
656  if (TypeIdx >= ScalarInVectorActions[OpcodeIdx].size())
657  return {NotFound, Aspect.Type};
658  const SizeAndActionsVec &ElemSizeVec =
659  ScalarInVectorActions[OpcodeIdx][TypeIdx];
660 
661  LLT IntermediateType;
662  auto ElementSizeAndAction =
663  findAction(ElemSizeVec, Aspect.Type.getScalarSizeInBits());
664  IntermediateType =
665  LLT::vector(Aspect.Type.getNumElements(), ElementSizeAndAction.first);
666  if (ElementSizeAndAction.second != Legal)
667  return {ElementSizeAndAction.second, IntermediateType};
668 
669  auto i = NumElements2Actions[OpcodeIdx].find(
670  IntermediateType.getScalarSizeInBits());
671  if (i == NumElements2Actions[OpcodeIdx].end()) {
672  return {NotFound, IntermediateType};
673  }
674  const SizeAndActionsVec &NumElementsVec = (*i).second[TypeIdx];
675  auto NumElementsAndAction =
676  findAction(NumElementsVec, IntermediateType.getNumElements());
677  return {NumElementsAndAction.second,
678  LLT::vector(NumElementsAndAction.first,
679  IntermediateType.getScalarSizeInBits())};
680 }
681 
684  MachineIRBuilder &MIRBuilder) const {
685  return true;
686 }
687 
688 /// \pre Type indices of every opcode form a dense set starting from 0.
689 void LegalizerInfo::verify(const MCInstrInfo &MII) const {
690 #ifndef NDEBUG
691  std::vector<unsigned> FailedOpcodes;
692  for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
693  const MCInstrDesc &MCID = MII.get(Opcode);
694  const unsigned NumTypeIdxs = std::accumulate(
695  MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
696  [](unsigned Acc, const MCOperandInfo &OpInfo) {
697  return OpInfo.isGenericType()
698  ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
699  : Acc;
700  });
701  const unsigned NumImmIdxs = std::accumulate(
702  MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
703  [](unsigned Acc, const MCOperandInfo &OpInfo) {
704  return OpInfo.isGenericImm()
705  ? std::max(OpInfo.getGenericImmIndex() + 1U, Acc)
706  : Acc;
707  });
708  LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
709  << "): " << NumTypeIdxs << " type ind"
710  << (NumTypeIdxs == 1 ? "ex" : "ices") << ", "
711  << NumImmIdxs << " imm ind"
712  << (NumImmIdxs == 1 ? "ex" : "ices") << "\n");
713  const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode);
714  if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
715  FailedOpcodes.push_back(Opcode);
716  else if (!RuleSet.verifyImmIdxsCoverage(NumImmIdxs))
717  FailedOpcodes.push_back(Opcode);
718  }
719  if (!FailedOpcodes.empty()) {
720  errs() << "The following opcodes have ill-defined legalization rules:";
721  for (unsigned Opcode : FailedOpcodes)
722  errs() << " " << MII.getName(Opcode);
723  errs() << "\n";
724 
725  report_fatal_error("ill-defined LegalizerInfo"
726  ", try -debug-only=legalizer-info for details");
727  }
728 #endif
729 }
730 
731 #ifndef NDEBUG
732 // FIXME: This should be in the MachineVerifier, but it can't use the
733 // LegalizerInfo as it's currently in the separate GlobalISel library.
734 // Note that RegBankSelected property already checked in the verifier
735 // has the same layering problem, but we only use inline methods so
736 // end up not needing to link against the GlobalISel library.
738  if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
739  const MachineRegisterInfo &MRI = MF.getRegInfo();
740  for (const MachineBasicBlock &MBB : MF)
741  for (const MachineInstr &MI : MBB)
742  if (isPreISelGenericOpcode(MI.getOpcode()) &&
743  !MLI->isLegalOrCustom(MI, MRI))
744  return &MI;
745  }
746  return nullptr;
747 }
748 #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:178
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:229
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:225
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:1302
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:101
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:534
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
bool verifyImmIdxsCoverage(unsigned NumImmIdxs) const
Check if there is no imm index which is obviously not handled by the LegalizeRuleSet in any way at al...
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:1095
SmallBitVector & set()
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:197
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:1146
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:230
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...
bool isGenericImm() const
Definition: MCInstrDesc.h:111
uint32_t Size
Definition: Profile.cpp:46
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2047
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:265
const MCOperandInfo * OpInfo
Definition: MCInstrDesc.h:189
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:106
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:70
#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