llvm/lib/CodeGen/GlobalISel/LegalizerInfo.cpp - llvm-project - Git at Google

 //===- lib/CodeGen/GlobalISel/LegalizerInfo.cpp - Legalizer ---------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Implement an interface to specify and query how an illegal operation on a
 // given type should be expanded.
 //
 //===----------------------------------------------------------------------===//

 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
 #include "llvm/ADT/SmallBitVector.h"
 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
 #include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineOperand.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/TargetOpcodes.h"
 #include "llvm/MC/MCInstrDesc.h"
 #include "llvm/MC/MCInstrInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/LowLevelTypeImpl.h"
 #include "llvm/Support/MathExtras.h"
 #include <algorithm>
 #include <map>

 using namespace llvm;
 using namespace LegalizeActions;

 #define DEBUG_TYPE "legalizer-info"

 cl::opt<bool> llvm::DisableGISelLegalityCheck(
     "disable-gisel-legality-check",
     cl::desc("Don't verify that MIR is fully legal between GlobalISel passes"),
     cl::Hidden);

 raw_ostream &llvm::operator<<(raw_ostream &OS, LegalizeAction Action) {
   switch (Action) {
   case Legal:
     OS << "Legal";
     break;
   case NarrowScalar:
     OS << "NarrowScalar";
     break;
   case WidenScalar:
     OS << "WidenScalar";
     break;
   case FewerElements:
     OS << "FewerElements";
     break;
   case MoreElements:
     OS << "MoreElements";
     break;
   case Bitcast:
     OS << "Bitcast";
     break;
   case Lower:
     OS << "Lower";
     break;
   case Libcall:
     OS << "Libcall";
     break;
   case Custom:
     OS << "Custom";
     break;
   case Unsupported:
     OS << "Unsupported";
     break;
   case NotFound:
     OS << "NotFound";
     break;
   case UseLegacyRules:
     OS << "UseLegacyRules";
     break;
   }
   return OS;
 }

 raw_ostream &LegalityQuery::print(raw_ostream &OS) const {
   OS << Opcode << ", Tys={";
   for (const auto &Type : Types) {
     OS << Type << ", ";
   }
   OS << "}, Opcode=";

   OS << Opcode << ", MMOs={";
   for (const auto &MMODescr : MMODescrs) {
     OS << MMODescr.MemoryTy << ", ";
   }
   OS << "}";

   return OS;
 }

 #ifndef NDEBUG
 // Make sure the rule won't (trivially) loop forever.
 static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q,
                              const std::pair<unsigned, LLT> &Mutation) {
   switch (Rule.getAction()) {
   case Legal:
   case Custom:
   case Lower:
   case MoreElements:
   case FewerElements:
     break;
   default:
     return Q.Types[Mutation.first] != Mutation.second;
   }
   return true;
 }

 // Make sure the returned mutation makes sense for the match type.
 static bool mutationIsSane(const LegalizeRule &Rule,
                            const LegalityQuery &Q,
                            std::pair<unsigned, LLT> Mutation) {
   // If the user wants a custom mutation, then we can't really say much about
   // it. Return true, and trust that they're doing the right thing.
   if (Rule.getAction() == Custom || Rule.getAction() == Legal)
     return true;

   const unsigned TypeIdx = Mutation.first;
   const LLT OldTy = Q.Types[TypeIdx];
   const LLT NewTy = Mutation.second;

   switch (Rule.getAction()) {
   case FewerElements:
     if (!OldTy.isVector())
       return false;
     LLVM_FALLTHROUGH;
   case MoreElements: {
     // MoreElements can go from scalar to vector.
     const unsigned OldElts = OldTy.isVector() ? OldTy.getNumElements() : 1;
     if (NewTy.isVector()) {
       if (Rule.getAction() == FewerElements) {
         // Make sure the element count really decreased.
         if (NewTy.getNumElements() >= OldElts)
           return false;
       } else {
         // Make sure the element count really increased.
         if (NewTy.getNumElements() <= OldElts)
           return false;
       }
     } else if (Rule.getAction() == MoreElements)
       return false;

     // Make sure the element type didn't change.
     return NewTy.getScalarType() == OldTy.getScalarType();
   }
   case NarrowScalar:
   case WidenScalar: {
     if (OldTy.isVector()) {
       // Number of elements should not change.
       if (!NewTy.isVector() || OldTy.getNumElements() != NewTy.getNumElements())
         return false;
     } else {
       // Both types must be vectors
       if (NewTy.isVector())
         return false;
     }

     if (Rule.getAction() == NarrowScalar)  {
       // Make sure the size really decreased.
       if (NewTy.getScalarSizeInBits() >= OldTy.getScalarSizeInBits())
         return false;
     } else {
       // Make sure the size really increased.
       if (NewTy.getScalarSizeInBits() <= OldTy.getScalarSizeInBits())
         return false;
     }

     return true;
   }
   case Bitcast: {
     return OldTy != NewTy && OldTy.getSizeInBits() == NewTy.getSizeInBits();
   }
   default:
     return true;
   }
 }
 #endif

 LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const {
   LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
              dbgs() << "\n");
   if (Rules.empty()) {
     LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
     return {LegalizeAction::UseLegacyRules, 0, LLT{}};
   }
   for (const LegalizeRule &Rule : Rules) {
     if (Rule.match(Query)) {
       LLVM_DEBUG(dbgs() << ".. match\n");
       std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
       LLVM_DEBUG(dbgs() << ".. .. " << Rule.getAction() << ", "
                         << Mutation.first << ", " << Mutation.second << "\n");
       assert(mutationIsSane(Rule, Query, Mutation) &&
              "legality mutation invalid for match");
       assert(hasNoSimpleLoops(Rule, Query, Mutation) && "Simple loop detected");
       return {Rule.getAction(), Mutation.first, Mutation.second};
     } else
       LLVM_DEBUG(dbgs() << ".. no match\n");
   }
   LLVM_DEBUG(dbgs() << ".. unsupported\n");
   return {LegalizeAction::Unsupported, 0, LLT{}};
 }

 bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const {
 #ifndef NDEBUG
   if (Rules.empty()) {
     LLVM_DEBUG(
         dbgs() << ".. type index coverage check SKIPPED: no rules defined\n");
     return true;
   }
   const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset();
   if (FirstUncovered < 0) {
     LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:"
                          " user-defined predicate detected\n");
     return true;
   }
   const bool AllCovered = (FirstUncovered >= NumTypeIdxs);
   if (NumTypeIdxs > 0)
     LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered
                       << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
   return AllCovered;
 #else
   return true;
 #endif
 }

 bool LegalizeRuleSet::verifyImmIdxsCoverage(unsigned NumImmIdxs) const {
 #ifndef NDEBUG
   if (Rules.empty()) {
     LLVM_DEBUG(
         dbgs() << ".. imm index coverage check SKIPPED: no rules defined\n");
     return true;
   }
   const int64_t FirstUncovered = ImmIdxsCovered.find_first_unset();
   if (FirstUncovered < 0) {
     LLVM_DEBUG(dbgs() << ".. imm index coverage check SKIPPED:"
                          " user-defined predicate detected\n");
     return true;
   }
   const bool AllCovered = (FirstUncovered >= NumImmIdxs);
   LLVM_DEBUG(dbgs() << ".. the first uncovered imm index: " << FirstUncovered
                     << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
   return AllCovered;
 #else
   return true;
 #endif
 }

 /// Helper function to get LLT for the given type index.
 static LLT getTypeFromTypeIdx(const MachineInstr &MI,
                               const MachineRegisterInfo &MRI, unsigned OpIdx,
                               unsigned TypeIdx) {
   assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
   // G_UNMERGE_VALUES has variable number of operands, but there is only
   // one source type and one destination type as all destinations must be the
   // same type. So, get the last operand if TypeIdx == 1.
   if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
     return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
   return MRI.getType(MI.getOperand(OpIdx).getReg());
 }

 unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
   assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
   return Opcode - FirstOp;
 }

 unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
   unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
   if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
     LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
                       << "\n");
     OpcodeIdx = getOpcodeIdxForOpcode(Alias);
     assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
   }

   return OpcodeIdx;
 }

 const LegalizeRuleSet &
 LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
   unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
   return RulesForOpcode[OpcodeIdx];
 }

 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) {
   unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
   auto &Result = RulesForOpcode[OpcodeIdx];
   assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
   return Result;
 }

 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(
     std::initializer_list<unsigned> Opcodes) {
   unsigned Representative = *Opcodes.begin();

   assert(!llvm::empty(Opcodes) && Opcodes.begin() + 1 != Opcodes.end() &&
          "Initializer list must have at least two opcodes");

   for (unsigned Op : llvm::drop_begin(Opcodes))
     aliasActionDefinitions(Representative, Op);

   auto &Return = getActionDefinitionsBuilder(Representative);
   Return.setIsAliasedByAnother();
   return Return;
 }

 void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo,
                                            unsigned OpcodeFrom) {
   assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
   assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
   const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
   RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
 }

 LegalizeActionStep
 LegalizerInfo::getAction(const LegalityQuery &Query) const {
   LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query);
   if (Step.Action != LegalizeAction::UseLegacyRules) {
     return Step;
   }

   return getLegacyLegalizerInfo().getAction(Query);
 }

 LegalizeActionStep
 LegalizerInfo::getAction(const MachineInstr &MI,
                          const MachineRegisterInfo &MRI) const {
   SmallVector<LLT, 8> Types;
   SmallBitVector SeenTypes(8);
   const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
   // FIXME: probably we'll need to cache the results here somehow?
   for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
     if (!OpInfo[i].isGenericType())
       continue;

     // We must only record actions once for each TypeIdx; otherwise we'd
     // try to legalize operands multiple times down the line.
     unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
     if (SeenTypes[TypeIdx])
       continue;

     SeenTypes.set(TypeIdx);

     LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
     Types.push_back(Ty);
   }

   SmallVector<LegalityQuery::MemDesc, 2> MemDescrs;
   for (const auto &MMO : MI.memoperands())
     MemDescrs.push_back({*MMO});

   return getAction({MI.getOpcode(), Types, MemDescrs});
 }

 bool LegalizerInfo::isLegal(const MachineInstr &MI,
                             const MachineRegisterInfo &MRI) const {
   return getAction(MI, MRI).Action == Legal;
 }

 bool LegalizerInfo::isLegalOrCustom(const MachineInstr &MI,
                                     const MachineRegisterInfo &MRI) const {
   auto Action = getAction(MI, MRI).Action;
   // If the action is custom, it may not necessarily modify the instruction,
   // so we have to assume it's legal.
   return Action == Legal || Action == Custom;
 }

 unsigned LegalizerInfo::getExtOpcodeForWideningConstant(LLT SmallTy) const {
   return SmallTy.isByteSized() ? TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT;
 }

 /// \pre Type indices of every opcode form a dense set starting from 0.
 void LegalizerInfo::verify(const MCInstrInfo &MII) const {
 #ifndef NDEBUG
   std::vector<unsigned> FailedOpcodes;
   for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
     const MCInstrDesc &MCID = MII.get(Opcode);
     const unsigned NumTypeIdxs = std::accumulate(
         MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
         [](unsigned Acc, const MCOperandInfo &OpInfo) {
           return OpInfo.isGenericType()
                      ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
                      : Acc;
         });
     const unsigned NumImmIdxs = std::accumulate(
         MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
         [](unsigned Acc, const MCOperandInfo &OpInfo) {
           return OpInfo.isGenericImm()
                      ? std::max(OpInfo.getGenericImmIndex() + 1U, Acc)
                      : Acc;
         });
     LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
                       << "): " << NumTypeIdxs << " type ind"
                       << (NumTypeIdxs == 1 ? "ex" : "ices") << ", "
                       << NumImmIdxs << " imm ind"
                       << (NumImmIdxs == 1 ? "ex" : "ices") << "\n");
     const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode);
     if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
       FailedOpcodes.push_back(Opcode);
     else if (!RuleSet.verifyImmIdxsCoverage(NumImmIdxs))
       FailedOpcodes.push_back(Opcode);
   }
   if (!FailedOpcodes.empty()) {
     errs() << "The following opcodes have ill-defined legalization rules:";
     for (unsigned Opcode : FailedOpcodes)
       errs() << " " << MII.getName(Opcode);
     errs() << "\n";

     report_fatal_error("ill-defined LegalizerInfo"
                        ", try -debug-only=legalizer-info for details");
   }
 #endif
 }

 #ifndef NDEBUG
 // FIXME: This should be in the MachineVerifier, but it can't use the
 // LegalizerInfo as it's currently in the separate GlobalISel library.
 // Note that RegBankSelected property already checked in the verifier
 // has the same layering problem, but we only use inline methods so
 // end up not needing to link against the GlobalISel library.
 const MachineInstr *llvm::machineFunctionIsIllegal(const MachineFunction &MF) {
   if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
     const MachineRegisterInfo &MRI = MF.getRegInfo();
     for (const MachineBasicBlock &MBB : MF)
       for (const MachineInstr &MI : MBB)
         if (isPreISelGenericOpcode(MI.getOpcode()) &&
             !MLI->isLegalOrCustom(MI, MRI))
           return &MI;
   }
   return nullptr;
 }
 #endif
	//===- lib/CodeGen/GlobalISel/LegalizerInfo.cpp - Legalizer ---------------===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//
	//
	// Implement an interface to specify and query how an illegal operation on a
	// given type should be expanded.
	//
	//===----------------------------------------------------------------------===//

	#include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
	#include "llvm/ADT/SmallBitVector.h"
	#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
	#include "llvm/CodeGen/MachineInstr.h"
	#include "llvm/CodeGen/MachineOperand.h"
	#include "llvm/CodeGen/MachineRegisterInfo.h"
	#include "llvm/CodeGen/TargetOpcodes.h"
	#include "llvm/MC/MCInstrDesc.h"
	#include "llvm/MC/MCInstrInfo.h"
	#include "llvm/Support/Debug.h"
	#include "llvm/Support/ErrorHandling.h"
	#include "llvm/Support/LowLevelTypeImpl.h"
	#include "llvm/Support/MathExtras.h"
	#include <algorithm>
	#include <map>

	using namespace llvm;
	using namespace LegalizeActions;

	#define DEBUG_TYPE "legalizer-info"

	cl::opt<bool> llvm::DisableGISelLegalityCheck(
	"disable-gisel-legality-check",
	cl::desc("Don't verify that MIR is fully legal between GlobalISel passes"),
	cl::Hidden);

	raw_ostream &llvm::operator<<(raw_ostream &OS, LegalizeAction Action) {
	switch (Action) {
	case Legal:
	OS << "Legal";
	break;
	case NarrowScalar:
	OS << "NarrowScalar";
	break;
	case WidenScalar:
	OS << "WidenScalar";
	break;
	case FewerElements:
	OS << "FewerElements";
	break;
	case MoreElements:
	OS << "MoreElements";
	break;
	case Bitcast:
	OS << "Bitcast";
	break;
	case Lower:
	OS << "Lower";
	break;
	case Libcall:
	OS << "Libcall";
	break;
	case Custom:
	OS << "Custom";
	break;
	case Unsupported:
	OS << "Unsupported";
	break;
	case NotFound:
	OS << "NotFound";
	break;
	case UseLegacyRules:
	OS << "UseLegacyRules";
	break;
	}
	return OS;
	}

	raw_ostream &LegalityQuery::print(raw_ostream &OS) const {
	OS << Opcode << ", Tys={";
	for (const auto &Type : Types) {
	OS << Type << ", ";
	}
	OS << "}, Opcode=";

	OS << Opcode << ", MMOs={";
	for (const auto &MMODescr : MMODescrs) {
	OS << MMODescr.MemoryTy << ", ";
	}
	OS << "}";

	return OS;
	}

	#ifndef NDEBUG
	// Make sure the rule won't (trivially) loop forever.
	static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q,
	const std::pair<unsigned, LLT> &Mutation) {
	switch (Rule.getAction()) {
	case Legal:
	case Custom:
	case Lower:
	case MoreElements:
	case FewerElements:
	break;
	default:
	return Q.Types[Mutation.first] != Mutation.second;
	}
	return true;
	}

	// Make sure the returned mutation makes sense for the match type.
	static bool mutationIsSane(const LegalizeRule &Rule,
	const LegalityQuery &Q,
	std::pair<unsigned, LLT> Mutation) {
	// If the user wants a custom mutation, then we can't really say much about
	// it. Return true, and trust that they're doing the right thing.
	if (Rule.getAction() == Custom \|\| Rule.getAction() == Legal)
	return true;

	const unsigned TypeIdx = Mutation.first;
	const LLT OldTy = Q.Types[TypeIdx];
	const LLT NewTy = Mutation.second;

	switch (Rule.getAction()) {
	case FewerElements:
	if (!OldTy.isVector())
	return false;
	LLVM_FALLTHROUGH;
	case MoreElements: {
	// MoreElements can go from scalar to vector.
	const unsigned OldElts = OldTy.isVector() ? OldTy.getNumElements() : 1;
	if (NewTy.isVector()) {
	if (Rule.getAction() == FewerElements) {
	// Make sure the element count really decreased.
	if (NewTy.getNumElements() >= OldElts)
	return false;
	} else {
	// Make sure the element count really increased.
	if (NewTy.getNumElements() <= OldElts)
	return false;
	}
	} else if (Rule.getAction() == MoreElements)
	return false;

	// Make sure the element type didn't change.
	return NewTy.getScalarType() == OldTy.getScalarType();
	}
	case NarrowScalar:
	case WidenScalar: {
	if (OldTy.isVector()) {
	// Number of elements should not change.
	if (!NewTy.isVector() \|\| OldTy.getNumElements() != NewTy.getNumElements())
	return false;
	} else {
	// Both types must be vectors
	if (NewTy.isVector())
	return false;
	}

	if (Rule.getAction() == NarrowScalar) {
	// Make sure the size really decreased.
	if (NewTy.getScalarSizeInBits() >= OldTy.getScalarSizeInBits())
	return false;
	} else {
	// Make sure the size really increased.
	if (NewTy.getScalarSizeInBits() <= OldTy.getScalarSizeInBits())
	return false;
	}

	return true;
	}
	case Bitcast: {
	return OldTy != NewTy && OldTy.getSizeInBits() == NewTy.getSizeInBits();
	}
	default:
	return true;
	}
	}
	#endif

	LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const {
	LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
	dbgs() << "\n");
	if (Rules.empty()) {
	LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
	return {LegalizeAction::UseLegacyRules, 0, LLT{}};
	}
	for (const LegalizeRule &Rule : Rules) {
	if (Rule.match(Query)) {
	LLVM_DEBUG(dbgs() << ".. match\n");
	std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
	LLVM_DEBUG(dbgs() << ".. .. " << Rule.getAction() << ", "
	<< Mutation.first << ", " << Mutation.second << "\n");
	assert(mutationIsSane(Rule, Query, Mutation) &&
	"legality mutation invalid for match");
	assert(hasNoSimpleLoops(Rule, Query, Mutation) && "Simple loop detected");
	return {Rule.getAction(), Mutation.first, Mutation.second};
	} else
	LLVM_DEBUG(dbgs() << ".. no match\n");
	}
	LLVM_DEBUG(dbgs() << ".. unsupported\n");
	return {LegalizeAction::Unsupported, 0, LLT{}};
	}

	bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const {
	#ifndef NDEBUG
	if (Rules.empty()) {
	LLVM_DEBUG(
	dbgs() << ".. type index coverage check SKIPPED: no rules defined\n");
	return true;
	}
	const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset();
	if (FirstUncovered < 0) {
	LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:"
	" user-defined predicate detected\n");
	return true;
	}
	const bool AllCovered = (FirstUncovered >= NumTypeIdxs);
	if (NumTypeIdxs > 0)
	LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered
	<< ", " << (AllCovered ? "OK" : "FAIL") << "\n");
	return AllCovered;
	#else
	return true;
	#endif
	}

	bool LegalizeRuleSet::verifyImmIdxsCoverage(unsigned NumImmIdxs) const {
	#ifndef NDEBUG
	if (Rules.empty()) {
	LLVM_DEBUG(
	dbgs() << ".. imm index coverage check SKIPPED: no rules defined\n");
	return true;
	}
	const int64_t FirstUncovered = ImmIdxsCovered.find_first_unset();
	if (FirstUncovered < 0) {
	LLVM_DEBUG(dbgs() << ".. imm index coverage check SKIPPED:"
	" user-defined predicate detected\n");
	return true;
	}
	const bool AllCovered = (FirstUncovered >= NumImmIdxs);
	LLVM_DEBUG(dbgs() << ".. the first uncovered imm index: " << FirstUncovered
	<< ", " << (AllCovered ? "OK" : "FAIL") << "\n");
	return AllCovered;
	#else
	return true;
	#endif
	}

	/// Helper function to get LLT for the given type index.
	static LLT getTypeFromTypeIdx(const MachineInstr &MI,
	const MachineRegisterInfo &MRI, unsigned OpIdx,
	unsigned TypeIdx) {
	assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
	// G_UNMERGE_VALUES has variable number of operands, but there is only
	// one source type and one destination type as all destinations must be the
	// same type. So, get the last operand if TypeIdx == 1.
	if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
	return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
	return MRI.getType(MI.getOperand(OpIdx).getReg());
	}

	unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
	assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
	return Opcode - FirstOp;
	}

	unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
	unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
	if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
	LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
	<< "\n");
	OpcodeIdx = getOpcodeIdxForOpcode(Alias);
	assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
	}

	return OpcodeIdx;
	}

	const LegalizeRuleSet &
	LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
	unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
	return RulesForOpcode[OpcodeIdx];
	}

	LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) {
	unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
	auto &Result = RulesForOpcode[OpcodeIdx];
	assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
	return Result;
	}

	LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(
	std::initializer_list<unsigned> Opcodes) {
	unsigned Representative = *Opcodes.begin();

	assert(!llvm::empty(Opcodes) && Opcodes.begin() + 1 != Opcodes.end() &&
	"Initializer list must have at least two opcodes");

	for (unsigned Op : llvm::drop_begin(Opcodes))
	aliasActionDefinitions(Representative, Op);

	auto &Return = getActionDefinitionsBuilder(Representative);
	Return.setIsAliasedByAnother();
	return Return;
	}

	void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo,
	unsigned OpcodeFrom) {
	assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
	assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
	const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
	RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
	}

	LegalizeActionStep
	LegalizerInfo::getAction(const LegalityQuery &Query) const {
	LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query);
	if (Step.Action != LegalizeAction::UseLegacyRules) {
	return Step;
	}

	return getLegacyLegalizerInfo().getAction(Query);
	}

	LegalizeActionStep
	LegalizerInfo::getAction(const MachineInstr &MI,
	const MachineRegisterInfo &MRI) const {
	SmallVector<LLT, 8> Types;
	SmallBitVector SeenTypes(8);
	const MCOperandInfo *OpInfo = MI.getDesc().OpInfo;
	// FIXME: probably we'll need to cache the results here somehow?
	for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
	if (!OpInfo[i].isGenericType())
	continue;

	// We must only record actions once for each TypeIdx; otherwise we'd
	// try to legalize operands multiple times down the line.
	unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
	if (SeenTypes[TypeIdx])
	continue;

	SeenTypes.set(TypeIdx);

	LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
	Types.push_back(Ty);
	}

	SmallVector<LegalityQuery::MemDesc, 2> MemDescrs;
	for (const auto &MMO : MI.memoperands())
	MemDescrs.push_back({*MMO});

	return getAction({MI.getOpcode(), Types, MemDescrs});
	}

	bool LegalizerInfo::isLegal(const MachineInstr &MI,
	const MachineRegisterInfo &MRI) const {
	return getAction(MI, MRI).Action == Legal;
	}

	bool LegalizerInfo::isLegalOrCustom(const MachineInstr &MI,
	const MachineRegisterInfo &MRI) const {
	auto Action = getAction(MI, MRI).Action;
	// If the action is custom, it may not necessarily modify the instruction,
	// so we have to assume it's legal.
	return Action == Legal \|\| Action == Custom;
	}

	unsigned LegalizerInfo::getExtOpcodeForWideningConstant(LLT SmallTy) const {
	return SmallTy.isByteSized() ? TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT;
	}

	/// \pre Type indices of every opcode form a dense set starting from 0.
	void LegalizerInfo::verify(const MCInstrInfo &MII) const {
	#ifndef NDEBUG
	std::vector<unsigned> FailedOpcodes;
	for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
	const MCInstrDesc &MCID = MII.get(Opcode);
	const unsigned NumTypeIdxs = std::accumulate(
	MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
	[](unsigned Acc, const MCOperandInfo &OpInfo) {
	return OpInfo.isGenericType()
	? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
	: Acc;
	});
	const unsigned NumImmIdxs = std::accumulate(
	MCID.opInfo_begin(), MCID.opInfo_end(), 0U,
	[](unsigned Acc, const MCOperandInfo &OpInfo) {
	return OpInfo.isGenericImm()
	? std::max(OpInfo.getGenericImmIndex() + 1U, Acc)
	: Acc;
	});
	LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
	<< "): " << NumTypeIdxs << " type ind"
	<< (NumTypeIdxs == 1 ? "ex" : "ices") << ", "
	<< NumImmIdxs << " imm ind"
	<< (NumImmIdxs == 1 ? "ex" : "ices") << "\n");
	const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode);
	if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
	FailedOpcodes.push_back(Opcode);
	else if (!RuleSet.verifyImmIdxsCoverage(NumImmIdxs))
	FailedOpcodes.push_back(Opcode);
	}
	if (!FailedOpcodes.empty()) {
	errs() << "The following opcodes have ill-defined legalization rules:";
	for (unsigned Opcode : FailedOpcodes)
	errs() << " " << MII.getName(Opcode);
	errs() << "\n";

	report_fatal_error("ill-defined LegalizerInfo"
	", try -debug-only=legalizer-info for details");
	}
	#endif
	}

	#ifndef NDEBUG
	// FIXME: This should be in the MachineVerifier, but it can't use the
	// LegalizerInfo as it's currently in the separate GlobalISel library.
	// Note that RegBankSelected property already checked in the verifier
	// has the same layering problem, but we only use inline methods so
	// end up not needing to link against the GlobalISel library.
	const MachineInstr *llvm::machineFunctionIsIllegal(const MachineFunction &MF) {
	if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
	const MachineRegisterInfo &MRI = MF.getRegInfo();
	for (const MachineBasicBlock &MBB : MF)
	for (const MachineInstr &MI : MBB)
	if (isPreISelGenericOpcode(MI.getOpcode()) &&
	!MLI->isLegalOrCustom(MI, MRI))
	return &MI;
	}
	return nullptr;
	}
	#endif