llvm/lib/CodeGen/GlobalISel/LegalizerInfo.cpp

   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 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
  15 #include "llvm/ADT/SmallBitVector.h"
  16 #include "llvm/CodeGen/MachineInstr.h"
  17 #include "llvm/CodeGen/MachineOperand.h"
  18 #include "llvm/CodeGen/MachineRegisterInfo.h"
  19 #include "llvm/CodeGen/TargetOpcodes.h"
  20 #include "llvm/CodeGenTypes/LowLevelType.h"
  21 #include "llvm/MC/MCInstrDesc.h"
  22 #include "llvm/MC/MCInstrInfo.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/ErrorHandling.h"
  25 #include <algorithm>
  26
  27 using namespace llvm;
  28 using namespace LegalizeActions;
  29
  30 #define DEBUG_TYPE "legalizer-info"
  31
  32 cl::opt<bool> llvm::DisableGISelLegalityCheck(
  33     "disable-gisel-legality-check",
  34     cl::desc("Don't verify that MIR is fully legal between GlobalISel passes"),
  35     cl::Hidden);
  36
  37 raw_ostream &llvm::operator<<(raw_ostream &OS, LegalizeAction Action) {
  38   switch (Action) {
  39   case Legal:
  40     OS << "Legal";
  41     break;
  42   case NarrowScalar:
  43     OS << "NarrowScalar";
  44     break;
  45   case WidenScalar:
  46     OS << "WidenScalar";
  47     break;
  48   case FewerElements:
  49     OS << "FewerElements";
  50     break;
  51   case MoreElements:
  52     OS << "MoreElements";
  53     break;
  54   case Bitcast:
  55     OS << "Bitcast";
  56     break;
  57   case Lower:
  58     OS << "Lower";
  59     break;
  60   case Libcall:
  61     OS << "Libcall";
  62     break;
  63   case Custom:
  64     OS << "Custom";
  65     break;
  66   case Unsupported:
  67     OS << "Unsupported";
  68     break;
  69   case NotFound:
  70     OS << "NotFound";
  71     break;
  72   case UseLegacyRules:
  73     OS << "UseLegacyRules";
  74     break;
  75   }
  76   return OS;
  77 }
  78
  79 raw_ostream &LegalityQuery::print(raw_ostream &OS) const {
  80   OS << "Opcode=" << Opcode << ", Tys={";
  81   for (const auto &Type : Types) {
  82     OS << Type << ", ";
  83   }
  84   OS << "}, MMOs={";
  85   for (const auto &MMODescr : MMODescrs) {
  86     OS << MMODescr.MemoryTy << ", ";
  87   }
  88   OS << "}";
  89
  90   return OS;
  91 }
  92
  93 #ifndef NDEBUG
  94 // Make sure the rule won't (trivially) loop forever.
  95 static bool hasNoSimpleLoops(const LegalizeRule &Rule, const LegalityQuery &Q,
  96                              const std::pair<unsigned, LLT> &Mutation) {
  97   switch (Rule.getAction()) {
  98   case Legal:
  99   case Custom:
 100   case Lower:
 101   case MoreElements:
 102   case FewerElements:
 103   case Libcall:
 104     break;
 105   default:
 106     return Q.Types[Mutation.first] != Mutation.second;
 107   }
 108   return true;
 109 }
 110
 111 // Make sure the returned mutation makes sense for the match type.
 112 static bool mutationIsSane(const LegalizeRule &Rule,
 113                            const LegalityQuery &Q,
 114                            std::pair<unsigned, LLT> Mutation) {
 115   // If the user wants a custom mutation, then we can't really say much about
 116   // it. Return true, and trust that they're doing the right thing.
 117   if (Rule.getAction() == Custom || Rule.getAction() == Legal)
 118     return true;
 119
 120   // Skip null mutation.
 121   if (!Mutation.second.isValid())
 122     return true;
 123
 124   const unsigned TypeIdx = Mutation.first;
 125   const LLT OldTy = Q.Types[TypeIdx];
 126   const LLT NewTy = Mutation.second;
 127
 128   switch (Rule.getAction()) {
 129   case FewerElements:
 130     if (!OldTy.isVector())
 131       return false;
 132     [[fallthrough]];
 133   case MoreElements: {
 134     // MoreElements can go from scalar to vector.
 135     const ElementCount OldElts = OldTy.isVector() ?
 136       OldTy.getElementCount() : ElementCount::getFixed(1);
 137     if (NewTy.isVector()) {
 138       if (Rule.getAction() == FewerElements) {
 139         // Make sure the element count really decreased.
 140         if (ElementCount::isKnownGE(NewTy.getElementCount(), OldElts))
 141           return false;
 142       } else {
 143         // Make sure the element count really increased.
 144         if (ElementCount::isKnownLE(NewTy.getElementCount(), OldElts))
 145           return false;
 146       }
 147     } else if (Rule.getAction() == MoreElements)
 148       return false;
 149
 150     // Make sure the element type didn't change.
 151     return NewTy.getScalarType() == OldTy.getScalarType();
 152   }
 153   case NarrowScalar:
 154   case WidenScalar: {
 155     if (OldTy.isVector()) {
 156       // Number of elements should not change.
 157       if (!NewTy.isVector() ||
 158           OldTy.getElementCount() != NewTy.getElementCount())
 159         return false;
 160     } else {
 161       // Both types must be vectors
 162       if (NewTy.isVector())
 163         return false;
 164     }
 165
 166     if (Rule.getAction() == NarrowScalar)  {
 167       // Make sure the size really decreased.
 168       if (NewTy.getScalarSizeInBits() >= OldTy.getScalarSizeInBits())
 169         return false;
 170     } else {
 171       // Make sure the size really increased.
 172       if (NewTy.getScalarSizeInBits() <= OldTy.getScalarSizeInBits())
 173         return false;
 174     }
 175
 176     return true;
 177   }
 178   case Bitcast: {
 179     return OldTy != NewTy && OldTy.getSizeInBits() == NewTy.getSizeInBits();
 180   }
 181   default:
 182     return true;
 183   }
 184 }
 185 #endif
 186
 187 LegalizeActionStep LegalizeRuleSet::apply(const LegalityQuery &Query) const {
 188   LLVM_DEBUG(dbgs() << "Applying legalizer ruleset to: "; Query.print(dbgs());
 189              dbgs() << "\n");
 190   if (Rules.empty()) {
 191     LLVM_DEBUG(dbgs() << ".. fallback to legacy rules (no rules defined)\n");
 192     return {LegalizeAction::UseLegacyRules, 0, LLT{}};
 193   }
 194   for (const LegalizeRule &Rule : Rules) {
 195     if (Rule.match(Query)) {
 196       LLVM_DEBUG(dbgs() << ".. match\n");
 197       std::pair<unsigned, LLT> Mutation = Rule.determineMutation(Query);
 198       LLVM_DEBUG(dbgs() << ".. .. " << Rule.getAction() << ", "
 199                         << Mutation.first << ", " << Mutation.second << "\n");
 200       assert(mutationIsSane(Rule, Query, Mutation) &&
 201              "legality mutation invalid for match");
 202       assert(hasNoSimpleLoops(Rule, Query, Mutation) && "Simple loop detected");
 203       return {Rule.getAction(), Mutation.first, Mutation.second};
 204     } else
 205       LLVM_DEBUG(dbgs() << ".. no match\n");
 206   }
 207   LLVM_DEBUG(dbgs() << ".. unsupported\n");
 208   return {LegalizeAction::Unsupported, 0, LLT{}};
 209 }
 210
 211 bool LegalizeRuleSet::verifyTypeIdxsCoverage(unsigned NumTypeIdxs) const {
 212 #ifndef NDEBUG
 213   if (Rules.empty()) {
 214     LLVM_DEBUG(
 215         dbgs() << ".. type index coverage check SKIPPED: no rules defined\n");
 216     return true;
 217   }
 218   const int64_t FirstUncovered = TypeIdxsCovered.find_first_unset();
 219   if (FirstUncovered < 0) {
 220     LLVM_DEBUG(dbgs() << ".. type index coverage check SKIPPED:"
 221                          " user-defined predicate detected\n");
 222     return true;
 223   }
 224   const bool AllCovered = (FirstUncovered >= NumTypeIdxs);
 225   if (NumTypeIdxs > 0)
 226     LLVM_DEBUG(dbgs() << ".. the first uncovered type index: " << FirstUncovered
 227                       << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
 228   return AllCovered;
 229 #else
 230   return true;
 231 #endif
 232 }
 233
 234 bool LegalizeRuleSet::verifyImmIdxsCoverage(unsigned NumImmIdxs) const {
 235 #ifndef NDEBUG
 236   if (Rules.empty()) {
 237     LLVM_DEBUG(
 238         dbgs() << ".. imm index coverage check SKIPPED: no rules defined\n");
 239     return true;
 240   }
 241   const int64_t FirstUncovered = ImmIdxsCovered.find_first_unset();
 242   if (FirstUncovered < 0) {
 243     LLVM_DEBUG(dbgs() << ".. imm index coverage check SKIPPED:"
 244                          " user-defined predicate detected\n");
 245     return true;
 246   }
 247   const bool AllCovered = (FirstUncovered >= NumImmIdxs);
 248   LLVM_DEBUG(dbgs() << ".. the first uncovered imm index: " << FirstUncovered
 249                     << ", " << (AllCovered ? "OK" : "FAIL") << "\n");
 250   return AllCovered;
 251 #else
 252   return true;
 253 #endif
 254 }
 255
 256 /// Helper function to get LLT for the given type index.
 257 static LLT getTypeFromTypeIdx(const MachineInstr &MI,
 258                               const MachineRegisterInfo &MRI, unsigned OpIdx,
 259                               unsigned TypeIdx) {
 260   assert(TypeIdx < MI.getNumOperands() && "Unexpected TypeIdx");
 261   // G_UNMERGE_VALUES has variable number of operands, but there is only
 262   // one source type and one destination type as all destinations must be the
 263   // same type. So, get the last operand if TypeIdx == 1.
 264   if (MI.getOpcode() == TargetOpcode::G_UNMERGE_VALUES && TypeIdx == 1)
 265     return MRI.getType(MI.getOperand(MI.getNumOperands() - 1).getReg());
 266   return MRI.getType(MI.getOperand(OpIdx).getReg());
 267 }
 268
 269 unsigned LegalizerInfo::getOpcodeIdxForOpcode(unsigned Opcode) const {
 270   assert(Opcode >= FirstOp && Opcode <= LastOp && "Unsupported opcode");
 271   return Opcode - FirstOp;
 272 }
 273
 274 unsigned LegalizerInfo::getActionDefinitionsIdx(unsigned Opcode) const {
 275   unsigned OpcodeIdx = getOpcodeIdxForOpcode(Opcode);
 276   if (unsigned Alias = RulesForOpcode[OpcodeIdx].getAlias()) {
 277     LLVM_DEBUG(dbgs() << ".. opcode " << Opcode << " is aliased to " << Alias
 278                       << "\n");
 279     OpcodeIdx = getOpcodeIdxForOpcode(Alias);
 280     assert(RulesForOpcode[OpcodeIdx].getAlias() == 0 && "Cannot chain aliases");
 281   }
 282
 283   return OpcodeIdx;
 284 }
 285
 286 const LegalizeRuleSet &
 287 LegalizerInfo::getActionDefinitions(unsigned Opcode) const {
 288   unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
 289   return RulesForOpcode[OpcodeIdx];
 290 }
 291
 292 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(unsigned Opcode) {
 293   unsigned OpcodeIdx = getActionDefinitionsIdx(Opcode);
 294   auto &Result = RulesForOpcode[OpcodeIdx];
 295   assert(!Result.isAliasedByAnother() && "Modifying this opcode will modify aliases");
 296   return Result;
 297 }
 298
 299 LegalizeRuleSet &LegalizerInfo::getActionDefinitionsBuilder(
 300     std::initializer_list<unsigned> Opcodes) {
 301   unsigned Representative = *Opcodes.begin();
 302
 303   assert(Opcodes.size() >= 2 &&
 304          "Initializer list must have at least two opcodes");
 305
 306   for (unsigned Op : llvm::drop_begin(Opcodes))
 307     aliasActionDefinitions(Representative, Op);
 308
 309   auto &Return = getActionDefinitionsBuilder(Representative);
 310   Return.setIsAliasedByAnother();
 311   return Return;
 312 }
 313
 314 void LegalizerInfo::aliasActionDefinitions(unsigned OpcodeTo,
 315                                            unsigned OpcodeFrom) {
 316   assert(OpcodeTo != OpcodeFrom && "Cannot alias to self");
 317   assert(OpcodeTo >= FirstOp && OpcodeTo <= LastOp && "Unsupported opcode");
 318   const unsigned OpcodeFromIdx = getOpcodeIdxForOpcode(OpcodeFrom);
 319   RulesForOpcode[OpcodeFromIdx].aliasTo(OpcodeTo);
 320 }
 321
 322 LegalizeActionStep
 323 LegalizerInfo::getAction(const LegalityQuery &Query) const {
 324   LegalizeActionStep Step = getActionDefinitions(Query.Opcode).apply(Query);
 325   if (Step.Action != LegalizeAction::UseLegacyRules) {
 326     return Step;
 327   }
 328
 329   return getLegacyLegalizerInfo().getAction(Query);
 330 }
 331
 332 LegalizeActionStep
 333 LegalizerInfo::getAction(const MachineInstr &MI,
 334                          const MachineRegisterInfo &MRI) const {
 335   SmallVector<LLT, 8> Types;
 336   SmallBitVector SeenTypes(8);
 337   ArrayRef<MCOperandInfo> OpInfo = MI.getDesc().operands();
 338   // FIXME: probably we'll need to cache the results here somehow?
 339   for (unsigned i = 0; i < MI.getDesc().getNumOperands(); ++i) {
 340     if (!OpInfo[i].isGenericType())
 341       continue;
 342
 343     // We must only record actions once for each TypeIdx; otherwise we'd
 344     // try to legalize operands multiple times down the line.
 345     unsigned TypeIdx = OpInfo[i].getGenericTypeIndex();
 346     if (SeenTypes[TypeIdx])
 347       continue;
 348
 349     SeenTypes.set(TypeIdx);
 350
 351     LLT Ty = getTypeFromTypeIdx(MI, MRI, i, TypeIdx);
 352     Types.push_back(Ty);
 353   }
 354
 355   SmallVector<LegalityQuery::MemDesc, 2> MemDescrs;
 356   for (const auto &MMO : MI.memoperands())
 357     MemDescrs.push_back({*MMO});
 358
 359   return getAction({MI.getOpcode(), Types, MemDescrs});
 360 }
 361
 362 bool LegalizerInfo::isLegal(const MachineInstr &MI,
 363                             const MachineRegisterInfo &MRI) const {
 364   return getAction(MI, MRI).Action == Legal;
 365 }
 366
 367 bool LegalizerInfo::isLegalOrCustom(const MachineInstr &MI,
 368                                     const MachineRegisterInfo &MRI) const {
 369   auto Action = getAction(MI, MRI).Action;
 370   // If the action is custom, it may not necessarily modify the instruction,
 371   // so we have to assume it's legal.
 372   return Action == Legal || Action == Custom;
 373 }
 374
 375 unsigned LegalizerInfo::getExtOpcodeForWideningConstant(LLT SmallTy) const {
 376   return SmallTy.isByteSized() ? TargetOpcode::G_SEXT : TargetOpcode::G_ZEXT;
 377 }
 378
 379 /// \pre Type indices of every opcode form a dense set starting from 0.
 380 void LegalizerInfo::verify(const MCInstrInfo &MII) const {
 381 #ifndef NDEBUG
 382   std::vector<unsigned> FailedOpcodes;
 383   for (unsigned Opcode = FirstOp; Opcode <= LastOp; ++Opcode) {
 384     const MCInstrDesc &MCID = MII.get(Opcode);
 385     const unsigned NumTypeIdxs = std::accumulate(
 386         MCID.operands().begin(), MCID.operands().end(), 0U,
 387         [](unsigned Acc, const MCOperandInfo &OpInfo) {
 388           return OpInfo.isGenericType()
 389                      ? std::max(OpInfo.getGenericTypeIndex() + 1U, Acc)
 390                      : Acc;
 391         });
 392     const unsigned NumImmIdxs = std::accumulate(
 393         MCID.operands().begin(), MCID.operands().end(), 0U,
 394         [](unsigned Acc, const MCOperandInfo &OpInfo) {
 395           return OpInfo.isGenericImm()
 396                      ? std::max(OpInfo.getGenericImmIndex() + 1U, Acc)
 397                      : Acc;
 398         });
 399     LLVM_DEBUG(dbgs() << MII.getName(Opcode) << " (opcode " << Opcode
 400                       << "): " << NumTypeIdxs << " type ind"
 401                       << (NumTypeIdxs == 1 ? "ex" : "ices") << ", "
 402                       << NumImmIdxs << " imm ind"
 403                       << (NumImmIdxs == 1 ? "ex" : "ices") << "\n");
 404     const LegalizeRuleSet &RuleSet = getActionDefinitions(Opcode);
 405     if (!RuleSet.verifyTypeIdxsCoverage(NumTypeIdxs))
 406       FailedOpcodes.push_back(Opcode);
 407     else if (!RuleSet.verifyImmIdxsCoverage(NumImmIdxs))
 408       FailedOpcodes.push_back(Opcode);
 409   }
 410   if (!FailedOpcodes.empty()) {
 411     errs() << "The following opcodes have ill-defined legalization rules:";
 412     for (unsigned Opcode : FailedOpcodes)
 413       errs() << " " << MII.getName(Opcode);
 414     errs() << "\n";
 415
 416     report_fatal_error("ill-defined LegalizerInfo"
 417                        ", try -debug-only=legalizer-info for details");
 418   }
 419 #endif
 420 }
 421
 422 #ifndef NDEBUG
 423 // FIXME: This should be in the MachineVerifier, but it can't use the
 424 // LegalizerInfo as it's currently in the separate GlobalISel library.
 425 // Note that RegBankSelected property already checked in the verifier
 426 // has the same layering problem, but we only use inline methods so
 427 // end up not needing to link against the GlobalISel library.
 428 const MachineInstr *llvm::machineFunctionIsIllegal(const MachineFunction &MF) {
 429   if (const LegalizerInfo *MLI = MF.getSubtarget().getLegalizerInfo()) {
 430     const MachineRegisterInfo &MRI = MF.getRegInfo();
 431     for (const MachineBasicBlock &MBB : MF)
 432       for (const MachineInstr &MI : MBB)
 433         if (isPreISelGenericOpcode(MI.getOpcode()) &&
 434             !MLI->isLegalOrCustom(MI, MRI))
 435           return &MI;
 436   }
 437   return nullptr;
 438 }
 439 #endif