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