llvm/lib/CodeGen/GlobalISel/Utils.cpp

   1 //===- llvm/CodeGen/GlobalISel/Utils.cpp -------------------------*- C++ -*-==//
   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 /// \file This file implements the utility functions used by the GlobalISel
   9 /// pipeline.
  10 //===----------------------------------------------------------------------===//
  11
  12 #include "llvm/CodeGen/GlobalISel/Utils.h"
  13 #include "llvm/ADT/APFloat.h"
  14 #include "llvm/ADT/APInt.h"
  15 #include "llvm/Analysis/ValueTracking.h"
  16 #include "llvm/CodeGen/CodeGenCommonISel.h"
  17 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
  18 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
  19 #include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"
  20 #include "llvm/CodeGen/GlobalISel/LostDebugLocObserver.h"
  21 #include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
  22 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
  23 #include "llvm/CodeGen/MachineInstr.h"
  24 #include "llvm/CodeGen/MachineInstrBuilder.h"
  25 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
  26 #include "llvm/CodeGen/MachineRegisterInfo.h"
  27 #include "llvm/CodeGen/MachineSizeOpts.h"
  28 #include "llvm/CodeGen/RegisterBankInfo.h"
  29 #include "llvm/CodeGen/StackProtector.h"
  30 #include "llvm/CodeGen/TargetInstrInfo.h"
  31 #include "llvm/CodeGen/TargetLowering.h"
  32 #include "llvm/CodeGen/TargetOpcodes.h"
  33 #include "llvm/CodeGen/TargetPassConfig.h"
  34 #include "llvm/CodeGen/TargetRegisterInfo.h"
  35 #include "llvm/IR/Constants.h"
  36 #include "llvm/Target/TargetMachine.h"
  37 #include "llvm/Transforms/Utils/SizeOpts.h"
  38 #include <numeric>
  39 #include <optional>
  40
  41 #define DEBUG_TYPE "globalisel-utils"
  42
  43 using namespace llvm;
  44 using namespace MIPatternMatch;
  45
  46 Register llvm::constrainRegToClass(MachineRegisterInfo &MRI,
  47                                    const TargetInstrInfo &TII,
  48                                    const RegisterBankInfo &RBI, Register Reg,
  49                                    const TargetRegisterClass &RegClass) {
  50   if (!RBI.constrainGenericRegister(Reg, RegClass, MRI))
  51     return MRI.createVirtualRegister(&RegClass);
  52
  53   return Reg;
  54 }
  55
  56 Register llvm::constrainOperandRegClass(
  57     const MachineFunction &MF, const TargetRegisterInfo &TRI,
  58     MachineRegisterInfo &MRI, const TargetInstrInfo &TII,
  59     const RegisterBankInfo &RBI, MachineInstr &InsertPt,
  60     const TargetRegisterClass &RegClass, MachineOperand &RegMO) {
  61   Register Reg = RegMO.getReg();
  62   // Assume physical registers are properly constrained.
  63   assert(Reg.isVirtual() && "PhysReg not implemented");
  64
  65   // Save the old register class to check whether
  66   // the change notifications will be required.
  67   // TODO: A better approach would be to pass
  68   // the observers to constrainRegToClass().
  69   auto *OldRegClass = MRI.getRegClassOrNull(Reg);
  70   Register ConstrainedReg = constrainRegToClass(MRI, TII, RBI, Reg, RegClass);
  71   // If we created a new virtual register because the class is not compatible
  72   // then create a copy between the new and the old register.
  73   if (ConstrainedReg != Reg) {
  74     MachineBasicBlock::iterator InsertIt(&InsertPt);
  75     MachineBasicBlock &MBB = *InsertPt.getParent();
  76     // FIXME: The copy needs to have the classes constrained for its operands.
  77     // Use operand's regbank to get the class for old register (Reg).
  78     if (RegMO.isUse()) {
  79       BuildMI(MBB, InsertIt, InsertPt.getDebugLoc(),
  80               TII.get(TargetOpcode::COPY), ConstrainedReg)
  81           .addReg(Reg);
  82     } else {
  83       assert(RegMO.isDef() && "Must be a definition");
  84       BuildMI(MBB, std::next(InsertIt), InsertPt.getDebugLoc(),
  85               TII.get(TargetOpcode::COPY), Reg)
  86           .addReg(ConstrainedReg);
  87     }
  88     if (GISelChangeObserver *Observer = MF.getObserver()) {
  89       Observer->changingInstr(*RegMO.getParent());
  90     }
  91     RegMO.setReg(ConstrainedReg);
  92     if (GISelChangeObserver *Observer = MF.getObserver()) {
  93       Observer->changedInstr(*RegMO.getParent());
  94     }
  95   } else if (OldRegClass != MRI.getRegClassOrNull(Reg)) {
  96     if (GISelChangeObserver *Observer = MF.getObserver()) {
  97       if (!RegMO.isDef()) {
  98         MachineInstr *RegDef = MRI.getVRegDef(Reg);
  99         Observer->changedInstr(*RegDef);
 100       }
 101       Observer->changingAllUsesOfReg(MRI, Reg);
 102       Observer->finishedChangingAllUsesOfReg();
 103     }
 104   }
 105   return ConstrainedReg;
 106 }
 107
 108 Register llvm::constrainOperandRegClass(
 109     const MachineFunction &MF, const TargetRegisterInfo &TRI,
 110     MachineRegisterInfo &MRI, const TargetInstrInfo &TII,
 111     const RegisterBankInfo &RBI, MachineInstr &InsertPt, const MCInstrDesc &II,
 112     MachineOperand &RegMO, unsigned OpIdx) {
 113   Register Reg = RegMO.getReg();
 114   // Assume physical registers are properly constrained.
 115   assert(Reg.isVirtual() && "PhysReg not implemented");
 116
 117   const TargetRegisterClass *OpRC = TII.getRegClass(II, OpIdx, &TRI, MF);
 118   // Some of the target independent instructions, like COPY, may not impose any
 119   // register class constraints on some of their operands: If it's a use, we can
 120   // skip constraining as the instruction defining the register would constrain
 121   // it.
 122
 123   if (OpRC) {
 124     // Obtain the RC from incoming regbank if it is a proper sub-class. Operands
 125     // can have multiple regbanks for a superclass that combine different
 126     // register types (E.g., AMDGPU's VGPR and AGPR). The regbank ambiguity
 127     // resolved by targets during regbankselect should not be overridden.
 128     if (const auto *SubRC = TRI.getCommonSubClass(
 129             OpRC, TRI.getConstrainedRegClassForOperand(RegMO, MRI)))
 130       OpRC = SubRC;
 131
 132     OpRC = TRI.getAllocatableClass(OpRC);
 133   }
 134
 135   if (!OpRC) {
 136     assert((!isTargetSpecificOpcode(II.getOpcode()) || RegMO.isUse()) &&
 137            "Register class constraint is required unless either the "
 138            "instruction is target independent or the operand is a use");
 139     // FIXME: Just bailing out like this here could be not enough, unless we
 140     // expect the users of this function to do the right thing for PHIs and
 141     // COPY:
 142     //   v1 = COPY v0
 143     //   v2 = COPY v1
 144     // v1 here may end up not being constrained at all. Please notice that to
 145     // reproduce the issue we likely need a destination pattern of a selection
 146     // rule producing such extra copies, not just an input GMIR with them as
 147     // every existing target using selectImpl handles copies before calling it
 148     // and they never reach this function.
 149     return Reg;
 150   }
 151   return constrainOperandRegClass(MF, TRI, MRI, TII, RBI, InsertPt, *OpRC,
 152                                   RegMO);
 153 }
 154
 155 bool llvm::constrainSelectedInstRegOperands(MachineInstr &I,
 156                                             const TargetInstrInfo &TII,
 157                                             const TargetRegisterInfo &TRI,
 158                                             const RegisterBankInfo &RBI) {
 159   assert(!isPreISelGenericOpcode(I.getOpcode()) &&
 160          "A selected instruction is expected");
 161   MachineBasicBlock &MBB = *I.getParent();
 162   MachineFunction &MF = *MBB.getParent();
 163   MachineRegisterInfo &MRI = MF.getRegInfo();
 164
 165   for (unsigned OpI = 0, OpE = I.getNumExplicitOperands(); OpI != OpE; ++OpI) {
 166     MachineOperand &MO = I.getOperand(OpI);
 167
 168     // There's nothing to be done on non-register operands.
 169     if (!MO.isReg())
 170       continue;
 171
 172     LLVM_DEBUG(dbgs() << "Converting operand: " << MO << '\n');
 173     assert(MO.isReg() && "Unsupported non-reg operand");
 174
 175     Register Reg = MO.getReg();
 176     // Physical registers don't need to be constrained.
 177     if (Reg.isPhysical())
 178       continue;
 179
 180     // Register operands with a value of 0 (e.g. predicate operands) don't need
 181     // to be constrained.
 182     if (Reg == 0)
 183       continue;
 184
 185     // If the operand is a vreg, we should constrain its regclass, and only
 186     // insert COPYs if that's impossible.
 187     // constrainOperandRegClass does that for us.
 188     constrainOperandRegClass(MF, TRI, MRI, TII, RBI, I, I.getDesc(), MO, OpI);
 189
 190     // Tie uses to defs as indicated in MCInstrDesc if this hasn't already been
 191     // done.
 192     if (MO.isUse()) {
 193       int DefIdx = I.getDesc().getOperandConstraint(OpI, MCOI::TIED_TO);
 194       if (DefIdx != -1 && !I.isRegTiedToUseOperand(DefIdx))
 195         I.tieOperands(DefIdx, OpI);
 196     }
 197   }
 198   return true;
 199 }
 200
 201 bool llvm::canReplaceReg(Register DstReg, Register SrcReg,
 202                          MachineRegisterInfo &MRI) {
 203   // Give up if either DstReg or SrcReg  is a physical register.
 204   if (DstReg.isPhysical() || SrcReg.isPhysical())
 205     return false;
 206   // Give up if the types don't match.
 207   if (MRI.getType(DstReg) != MRI.getType(SrcReg))
 208     return false;
 209   // Replace if either DstReg has no constraints or the register
 210   // constraints match.
 211   const auto &DstRBC = MRI.getRegClassOrRegBank(DstReg);
 212   if (!DstRBC || DstRBC == MRI.getRegClassOrRegBank(SrcReg))
 213     return true;
 214
 215   // Otherwise match if the Src is already a regclass that is covered by the Dst
 216   // RegBank.
 217   return isa<const RegisterBank *>(DstRBC) && MRI.getRegClassOrNull(SrcReg) &&
 218          cast<const RegisterBank *>(DstRBC)->covers(
 219              *MRI.getRegClassOrNull(SrcReg));
 220 }
 221
 222 bool llvm::isTriviallyDead(const MachineInstr &MI,
 223                            const MachineRegisterInfo &MRI) {
 224   // Instructions without side-effects are dead iff they only define dead regs.
 225   // This function is hot and this loop returns early in the common case,
 226   // so only perform additional checks before this if absolutely necessary.
 227   for (const auto &MO : MI.all_defs()) {
 228     Register Reg = MO.getReg();
 229     if (Reg.isPhysical() || !MRI.use_nodbg_empty(Reg))
 230       return false;
 231   }
 232   return MI.wouldBeTriviallyDead();
 233 }
 234
 235 static void reportGISelDiagnostic(DiagnosticSeverity Severity,
 236                                   MachineFunction &MF,
 237                                   const TargetPassConfig &TPC,
 238                                   MachineOptimizationRemarkEmitter &MORE,
 239                                   MachineOptimizationRemarkMissed &R) {
 240   bool IsFatal = Severity == DS_Error &&
 241                  TPC.isGlobalISelAbortEnabled();
 242   // Print the function name explicitly if we don't have a debug location (which
 243   // makes the diagnostic less useful) or if we're going to emit a raw error.
 244   if (!R.getLocation().isValid() || IsFatal)
 245     R << (" (in function: " + MF.getName() + ")").str();
 246
 247   if (IsFatal)
 248     report_fatal_error(Twine(R.getMsg()));
 249   else
 250     MORE.emit(R);
 251 }
 252
 253 void llvm::reportGISelWarning(MachineFunction &MF, const TargetPassConfig &TPC,
 254                               MachineOptimizationRemarkEmitter &MORE,
 255                               MachineOptimizationRemarkMissed &R) {
 256   reportGISelDiagnostic(DS_Warning, MF, TPC, MORE, R);
 257 }
 258
 259 void llvm::reportGISelFailure(MachineFunction &MF, const TargetPassConfig &TPC,
 260                               MachineOptimizationRemarkEmitter &MORE,
 261                               MachineOptimizationRemarkMissed &R) {
 262   MF.getProperties().set(MachineFunctionProperties::Property::FailedISel);
 263   reportGISelDiagnostic(DS_Error, MF, TPC, MORE, R);
 264 }
 265
 266 void llvm::reportGISelFailure(MachineFunction &MF, const TargetPassConfig &TPC,
 267                               MachineOptimizationRemarkEmitter &MORE,
 268                               const char *PassName, StringRef Msg,
 269                               const MachineInstr &MI) {
 270   MachineOptimizationRemarkMissed R(PassName, "GISelFailure: ",
 271                                     MI.getDebugLoc(), MI.getParent());
 272   R << Msg;
 273   // Printing MI is expensive;  only do it if expensive remarks are enabled.
 274   if (TPC.isGlobalISelAbortEnabled() || MORE.allowExtraAnalysis(PassName))
 275     R << ": " << ore::MNV("Inst", MI);
 276   reportGISelFailure(MF, TPC, MORE, R);
 277 }
 278
 279 unsigned llvm::getInverseGMinMaxOpcode(unsigned MinMaxOpc) {
 280   switch (MinMaxOpc) {
 281   case TargetOpcode::G_SMIN:
 282     return TargetOpcode::G_SMAX;
 283   case TargetOpcode::G_SMAX:
 284     return TargetOpcode::G_SMIN;
 285   case TargetOpcode::G_UMIN:
 286     return TargetOpcode::G_UMAX;
 287   case TargetOpcode::G_UMAX:
 288     return TargetOpcode::G_UMIN;
 289   default:
 290     llvm_unreachable("unrecognized opcode");
 291   }
 292 }
 293
 294 std::optional<APInt> llvm::getIConstantVRegVal(Register VReg,
 295                                                const MachineRegisterInfo &MRI) {
 296   std::optional<ValueAndVReg> ValAndVReg = getIConstantVRegValWithLookThrough(
 297       VReg, MRI, /*LookThroughInstrs*/ false);
 298   assert((!ValAndVReg || ValAndVReg->VReg == VReg) &&
 299          "Value found while looking through instrs");
 300   if (!ValAndVReg)
 301     return std::nullopt;
 302   return ValAndVReg->Value;
 303 }
 304
 305 const APInt &llvm::getIConstantFromReg(Register Reg,
 306                                        const MachineRegisterInfo &MRI) {
 307   MachineInstr *Const = MRI.getVRegDef(Reg);
 308   assert((Const && Const->getOpcode() == TargetOpcode::G_CONSTANT) &&
 309          "expected a G_CONSTANT on Reg");
 310   return Const->getOperand(1).getCImm()->getValue();
 311 }
 312
 313 std::optional<int64_t>
 314 llvm::getIConstantVRegSExtVal(Register VReg, const MachineRegisterInfo &MRI) {
 315   std::optional<APInt> Val = getIConstantVRegVal(VReg, MRI);
 316   if (Val && Val->getBitWidth() <= 64)
 317     return Val->getSExtValue();
 318   return std::nullopt;
 319 }
 320
 321 namespace {
 322
 323 // This function is used in many places, and as such, it has some
 324 // micro-optimizations to try and make it as fast as it can be.
 325 //
 326 // - We use template arguments to avoid an indirect call caused by passing a
 327 // function_ref/std::function
 328 // - GetAPCstValue does not return std::optional<APInt> as that's expensive.
 329 // Instead it returns true/false and places the result in a pre-constructed
 330 // APInt.
 331 //
 332 // Please change this function carefully and benchmark your changes.
 333 template <bool (*IsConstantOpcode)(const MachineInstr *),
 334           bool (*GetAPCstValue)(const MachineInstr *MI, APInt &)>
 335 std::optional<ValueAndVReg>
 336 getConstantVRegValWithLookThrough(Register VReg, const MachineRegisterInfo &MRI,
 337                                   bool LookThroughInstrs = true,
 338                                   bool LookThroughAnyExt = false) {
 339   SmallVector<std::pair<unsigned, unsigned>, 4> SeenOpcodes;
 340   MachineInstr *MI;
 341
 342   while ((MI = MRI.getVRegDef(VReg)) && !IsConstantOpcode(MI) &&
 343          LookThroughInstrs) {
 344     switch (MI->getOpcode()) {
 345     case TargetOpcode::G_ANYEXT:
 346       if (!LookThroughAnyExt)
 347         return std::nullopt;
 348       [[fallthrough]];
 349     case TargetOpcode::G_TRUNC:
 350     case TargetOpcode::G_SEXT:
 351     case TargetOpcode::G_ZEXT:
 352       SeenOpcodes.push_back(std::make_pair(
 353           MI->getOpcode(),
 354           MRI.getType(MI->getOperand(0).getReg()).getSizeInBits()));
 355       VReg = MI->getOperand(1).getReg();
 356       break;
 357     case TargetOpcode::COPY:
 358       VReg = MI->getOperand(1).getReg();
 359       if (VReg.isPhysical())
 360         return std::nullopt;
 361       break;
 362     case TargetOpcode::G_INTTOPTR:
 363       VReg = MI->getOperand(1).getReg();
 364       break;
 365     default:
 366       return std::nullopt;
 367     }
 368   }
 369   if (!MI || !IsConstantOpcode(MI))
 370     return std::nullopt;
 371
 372   APInt Val;
 373   if (!GetAPCstValue(MI, Val))
 374     return std::nullopt;
 375   for (auto &Pair : reverse(SeenOpcodes)) {
 376     switch (Pair.first) {
 377     case TargetOpcode::G_TRUNC:
 378       Val = Val.trunc(Pair.second);
 379       break;
 380     case TargetOpcode::G_ANYEXT:
 381     case TargetOpcode::G_SEXT:
 382       Val = Val.sext(Pair.second);
 383       break;
 384     case TargetOpcode::G_ZEXT:
 385       Val = Val.zext(Pair.second);
 386       break;
 387     }
 388   }
 389
 390   return ValueAndVReg{std::move(Val), VReg};
 391 }
 392
 393 bool isIConstant(const MachineInstr *MI) {
 394   if (!MI)
 395     return false;
 396   return MI->getOpcode() == TargetOpcode::G_CONSTANT;
 397 }
 398
 399 bool isFConstant(const MachineInstr *MI) {
 400   if (!MI)
 401     return false;
 402   return MI->getOpcode() == TargetOpcode::G_FCONSTANT;
 403 }
 404
 405 bool isAnyConstant(const MachineInstr *MI) {
 406   if (!MI)
 407     return false;
 408   unsigned Opc = MI->getOpcode();
 409   return Opc == TargetOpcode::G_CONSTANT || Opc == TargetOpcode::G_FCONSTANT;
 410 }
 411
 412 bool getCImmAsAPInt(const MachineInstr *MI, APInt &Result) {
 413   const MachineOperand &CstVal = MI->getOperand(1);
 414   if (!CstVal.isCImm())
 415     return false;
 416   Result = CstVal.getCImm()->getValue();
 417   return true;
 418 }
 419
 420 bool getCImmOrFPImmAsAPInt(const MachineInstr *MI, APInt &Result) {
 421   const MachineOperand &CstVal = MI->getOperand(1);
 422   if (CstVal.isCImm())
 423     Result = CstVal.getCImm()->getValue();
 424   else if (CstVal.isFPImm())
 425     Result = CstVal.getFPImm()->getValueAPF().bitcastToAPInt();
 426   else
 427     return false;
 428   return true;
 429 }
 430
 431 } // end anonymous namespace
 432
 433 std::optional<ValueAndVReg> llvm::getIConstantVRegValWithLookThrough(
 434     Register VReg, const MachineRegisterInfo &MRI, bool LookThroughInstrs) {
 435   return getConstantVRegValWithLookThrough<isIConstant, getCImmAsAPInt>(
 436       VReg, MRI, LookThroughInstrs);
 437 }
 438
 439 std::optional<ValueAndVReg> llvm::getAnyConstantVRegValWithLookThrough(
 440     Register VReg, const MachineRegisterInfo &MRI, bool LookThroughInstrs,
 441     bool LookThroughAnyExt) {
 442   return getConstantVRegValWithLookThrough<isAnyConstant,
 443                                            getCImmOrFPImmAsAPInt>(
 444       VReg, MRI, LookThroughInstrs, LookThroughAnyExt);
 445 }
 446
 447 std::optional<FPValueAndVReg> llvm::getFConstantVRegValWithLookThrough(
 448     Register VReg, const MachineRegisterInfo &MRI, bool LookThroughInstrs) {
 449   auto Reg =
 450       getConstantVRegValWithLookThrough<isFConstant, getCImmOrFPImmAsAPInt>(
 451           VReg, MRI, LookThroughInstrs);
 452   if (!Reg)
 453     return std::nullopt;
 454   return FPValueAndVReg{getConstantFPVRegVal(Reg->VReg, MRI)->getValueAPF(),
 455                         Reg->VReg};
 456 }
 457
 458 const ConstantFP *
 459 llvm::getConstantFPVRegVal(Register VReg, const MachineRegisterInfo &MRI) {
 460   MachineInstr *MI = MRI.getVRegDef(VReg);
 461   if (TargetOpcode::G_FCONSTANT != MI->getOpcode())
 462     return nullptr;
 463   return MI->getOperand(1).getFPImm();
 464 }
 465
 466 std::optional<DefinitionAndSourceRegister>
 467 llvm::getDefSrcRegIgnoringCopies(Register Reg, const MachineRegisterInfo &MRI) {
 468   Register DefSrcReg = Reg;
 469   auto *DefMI = MRI.getVRegDef(Reg);
 470   auto DstTy = MRI.getType(DefMI->getOperand(0).getReg());
 471   if (!DstTy.isValid())
 472     return std::nullopt;
 473   unsigned Opc = DefMI->getOpcode();
 474   while (Opc == TargetOpcode::COPY || isPreISelGenericOptimizationHint(Opc)) {
 475     Register SrcReg = DefMI->getOperand(1).getReg();
 476     auto SrcTy = MRI.getType(SrcReg);
 477     if (!SrcTy.isValid())
 478       break;
 479     DefMI = MRI.getVRegDef(SrcReg);
 480     DefSrcReg = SrcReg;
 481     Opc = DefMI->getOpcode();
 482   }
 483   return DefinitionAndSourceRegister{DefMI, DefSrcReg};
 484 }
 485
 486 MachineInstr *llvm::getDefIgnoringCopies(Register Reg,
 487                                          const MachineRegisterInfo &MRI) {
 488   std::optional<DefinitionAndSourceRegister> DefSrcReg =
 489       getDefSrcRegIgnoringCopies(Reg, MRI);
 490   return DefSrcReg ? DefSrcReg->MI : nullptr;
 491 }
 492
 493 Register llvm::getSrcRegIgnoringCopies(Register Reg,
 494                                        const MachineRegisterInfo &MRI) {
 495   std::optional<DefinitionAndSourceRegister> DefSrcReg =
 496       getDefSrcRegIgnoringCopies(Reg, MRI);
 497   return DefSrcReg ? DefSrcReg->Reg : Register();
 498 }
 499
 500 void llvm::extractParts(Register Reg, LLT Ty, int NumParts,
 501                         SmallVectorImpl<Register> &VRegs,
 502                         MachineIRBuilder &MIRBuilder,
 503                         MachineRegisterInfo &MRI) {
 504   for (int i = 0; i < NumParts; ++i)
 505     VRegs.push_back(MRI.createGenericVirtualRegister(Ty));
 506   MIRBuilder.buildUnmerge(VRegs, Reg);
 507 }
 508
 509 bool llvm::extractParts(Register Reg, LLT RegTy, LLT MainTy, LLT &LeftoverTy,
 510                         SmallVectorImpl<Register> &VRegs,
 511                         SmallVectorImpl<Register> &LeftoverRegs,
 512                         MachineIRBuilder &MIRBuilder,
 513                         MachineRegisterInfo &MRI) {
 514   assert(!LeftoverTy.isValid() && "this is an out argument");
 515
 516   unsigned RegSize = RegTy.getSizeInBits();
 517   unsigned MainSize = MainTy.getSizeInBits();
 518   unsigned NumParts = RegSize / MainSize;
 519   unsigned LeftoverSize = RegSize - NumParts * MainSize;
 520
 521   // Use an unmerge when possible.
 522   if (LeftoverSize == 0) {
 523     for (unsigned I = 0; I < NumParts; ++I)
 524       VRegs.push_back(MRI.createGenericVirtualRegister(MainTy));
 525     MIRBuilder.buildUnmerge(VRegs, Reg);
 526     return true;
 527   }
 528
 529   // Try to use unmerge for irregular vector split where possible
 530   // For example when splitting a <6 x i32> into <4 x i32> with <2 x i32>
 531   // leftover, it becomes:
 532   //  <2 x i32> %2, <2 x i32>%3, <2 x i32> %4 = G_UNMERGE_VALUE <6 x i32> %1
 533   //  <4 x i32> %5 = G_CONCAT_VECTOR <2 x i32> %2, <2 x i32> %3
 534   if (RegTy.isVector() && MainTy.isVector()) {
 535     unsigned RegNumElts = RegTy.getNumElements();
 536     unsigned MainNumElts = MainTy.getNumElements();
 537     unsigned LeftoverNumElts = RegNumElts % MainNumElts;
 538     // If can unmerge to LeftoverTy, do it
 539     if (MainNumElts % LeftoverNumElts == 0 &&
 540         RegNumElts % LeftoverNumElts == 0 &&
 541         RegTy.getScalarSizeInBits() == MainTy.getScalarSizeInBits() &&
 542         LeftoverNumElts > 1) {
 543       LeftoverTy = LLT::fixed_vector(LeftoverNumElts, RegTy.getElementType());
 544
 545       // Unmerge the SrcReg to LeftoverTy vectors
 546       SmallVector<Register, 4> UnmergeValues;
 547       extractParts(Reg, LeftoverTy, RegNumElts / LeftoverNumElts, UnmergeValues,
 548                    MIRBuilder, MRI);
 549
 550       // Find how many LeftoverTy makes one MainTy
 551       unsigned LeftoverPerMain = MainNumElts / LeftoverNumElts;
 552       unsigned NumOfLeftoverVal =
 553           ((RegNumElts % MainNumElts) / LeftoverNumElts);
 554
 555       // Create as many MainTy as possible using unmerged value
 556       SmallVector<Register, 4> MergeValues;
 557       for (unsigned I = 0; I < UnmergeValues.size() - NumOfLeftoverVal; I++) {
 558         MergeValues.push_back(UnmergeValues[I]);
 559         if (MergeValues.size() == LeftoverPerMain) {
 560           VRegs.push_back(
 561               MIRBuilder.buildMergeLikeInstr(MainTy, MergeValues).getReg(0));
 562           MergeValues.clear();
 563         }
 564       }
 565       // Populate LeftoverRegs with the leftovers
 566       for (unsigned I = UnmergeValues.size() - NumOfLeftoverVal;
 567            I < UnmergeValues.size(); I++) {
 568         LeftoverRegs.push_back(UnmergeValues[I]);
 569       }
 570       return true;
 571     }
 572   }
 573   // Perform irregular split. Leftover is last element of RegPieces.
 574   if (MainTy.isVector()) {
 575     SmallVector<Register, 8> RegPieces;
 576     extractVectorParts(Reg, MainTy.getNumElements(), RegPieces, MIRBuilder,
 577                        MRI);
 578     for (unsigned i = 0; i < RegPieces.size() - 1; ++i)
 579       VRegs.push_back(RegPieces[i]);
 580     LeftoverRegs.push_back(RegPieces[RegPieces.size() - 1]);
 581     LeftoverTy = MRI.getType(LeftoverRegs[0]);
 582     return true;
 583   }
 584
 585   LeftoverTy = LLT::scalar(LeftoverSize);
 586   // For irregular sizes, extract the individual parts.
 587   for (unsigned I = 0; I != NumParts; ++I) {
 588     Register NewReg = MRI.createGenericVirtualRegister(MainTy);
 589     VRegs.push_back(NewReg);
 590     MIRBuilder.buildExtract(NewReg, Reg, MainSize * I);
 591   }
 592
 593   for (unsigned Offset = MainSize * NumParts; Offset < RegSize;
 594        Offset += LeftoverSize) {
 595     Register NewReg = MRI.createGenericVirtualRegister(LeftoverTy);
 596     LeftoverRegs.push_back(NewReg);
 597     MIRBuilder.buildExtract(NewReg, Reg, Offset);
 598   }
 599
 600   return true;
 601 }
 602
 603 void llvm::extractVectorParts(Register Reg, unsigned NumElts,
 604                               SmallVectorImpl<Register> &VRegs,
 605                               MachineIRBuilder &MIRBuilder,
 606                               MachineRegisterInfo &MRI) {
 607   LLT RegTy = MRI.getType(Reg);
 608   assert(RegTy.isVector() && "Expected a vector type");
 609
 610   LLT EltTy = RegTy.getElementType();
 611   LLT NarrowTy = (NumElts == 1) ? EltTy : LLT::fixed_vector(NumElts, EltTy);
 612   unsigned RegNumElts = RegTy.getNumElements();
 613   unsigned LeftoverNumElts = RegNumElts % NumElts;
 614   unsigned NumNarrowTyPieces = RegNumElts / NumElts;
 615
 616   // Perfect split without leftover
 617   if (LeftoverNumElts == 0)
 618     return extractParts(Reg, NarrowTy, NumNarrowTyPieces, VRegs, MIRBuilder,
 619                         MRI);
 620
 621   // Irregular split. Provide direct access to all elements for artifact
 622   // combiner using unmerge to elements. Then build vectors with NumElts
 623   // elements. Remaining element(s) will be (used to build vector) Leftover.
 624   SmallVector<Register, 8> Elts;
 625   extractParts(Reg, EltTy, RegNumElts, Elts, MIRBuilder, MRI);
 626
 627   unsigned Offset = 0;
 628   // Requested sub-vectors of NarrowTy.
 629   for (unsigned i = 0; i < NumNarrowTyPieces; ++i, Offset += NumElts) {
 630     ArrayRef<Register> Pieces(&Elts[Offset], NumElts);
 631     VRegs.push_back(MIRBuilder.buildMergeLikeInstr(NarrowTy, Pieces).getReg(0));
 632   }
 633
 634   // Leftover element(s).
 635   if (LeftoverNumElts == 1) {
 636     VRegs.push_back(Elts[Offset]);
 637   } else {
 638     LLT LeftoverTy = LLT::fixed_vector(LeftoverNumElts, EltTy);
 639     ArrayRef<Register> Pieces(&Elts[Offset], LeftoverNumElts);
 640     VRegs.push_back(
 641         MIRBuilder.buildMergeLikeInstr(LeftoverTy, Pieces).getReg(0));
 642   }
 643 }
 644
 645 MachineInstr *llvm::getOpcodeDef(unsigned Opcode, Register Reg,
 646                                  const MachineRegisterInfo &MRI) {
 647   MachineInstr *DefMI = getDefIgnoringCopies(Reg, MRI);
 648   return DefMI && DefMI->getOpcode() == Opcode ? DefMI : nullptr;
 649 }
 650
 651 APFloat llvm::getAPFloatFromSize(double Val, unsigned Size) {
 652   if (Size == 32)
 653     return APFloat(float(Val));
 654   if (Size == 64)
 655     return APFloat(Val);
 656   if (Size != 16)
 657     llvm_unreachable("Unsupported FPConstant size");
 658   bool Ignored;
 659   APFloat APF(Val);
 660   APF.convert(APFloat::IEEEhalf(), APFloat::rmNearestTiesToEven, &Ignored);
 661   return APF;
 662 }
 663
 664 std::optional<APInt> llvm::ConstantFoldBinOp(unsigned Opcode,
 665                                              const Register Op1,
 666                                              const Register Op2,
 667                                              const MachineRegisterInfo &MRI) {
 668   auto MaybeOp2Cst = getAnyConstantVRegValWithLookThrough(Op2, MRI, false);
 669   if (!MaybeOp2Cst)
 670     return std::nullopt;
 671
 672   auto MaybeOp1Cst = getAnyConstantVRegValWithLookThrough(Op1, MRI, false);
 673   if (!MaybeOp1Cst)
 674     return std::nullopt;
 675
 676   const APInt &C1 = MaybeOp1Cst->Value;
 677   const APInt &C2 = MaybeOp2Cst->Value;
 678   switch (Opcode) {
 679   default:
 680     break;
 681   case TargetOpcode::G_ADD:
 682     return C1 + C2;
 683   case TargetOpcode::G_PTR_ADD:
 684     // Types can be of different width here.
 685     // Result needs to be the same width as C1, so trunc or sext C2.
 686     return C1 + C2.sextOrTrunc(C1.getBitWidth());
 687   case TargetOpcode::G_AND:
 688     return C1 & C2;
 689   case TargetOpcode::G_ASHR:
 690     return C1.ashr(C2);
 691   case TargetOpcode::G_LSHR:
 692     return C1.lshr(C2);
 693   case TargetOpcode::G_MUL:
 694     return C1 * C2;
 695   case TargetOpcode::G_OR:
 696     return C1 | C2;
 697   case TargetOpcode::G_SHL:
 698     return C1 << C2;
 699   case TargetOpcode::G_SUB:
 700     return C1 - C2;
 701   case TargetOpcode::G_XOR:
 702     return C1 ^ C2;
 703   case TargetOpcode::G_UDIV:
 704     if (!C2.getBoolValue())
 705       break;
 706     return C1.udiv(C2);
 707   case TargetOpcode::G_SDIV:
 708     if (!C2.getBoolValue())
 709       break;
 710     return C1.sdiv(C2);
 711   case TargetOpcode::G_UREM:
 712     if (!C2.getBoolValue())
 713       break;
 714     return C1.urem(C2);
 715   case TargetOpcode::G_SREM:
 716     if (!C2.getBoolValue())
 717       break;
 718     return C1.srem(C2);
 719   case TargetOpcode::G_SMIN:
 720     return APIntOps::smin(C1, C2);
 721   case TargetOpcode::G_SMAX:
 722     return APIntOps::smax(C1, C2);
 723   case TargetOpcode::G_UMIN:
 724     return APIntOps::umin(C1, C2);
 725   case TargetOpcode::G_UMAX:
 726     return APIntOps::umax(C1, C2);
 727   }
 728
 729   return std::nullopt;
 730 }
 731
 732 std::optional<APFloat>
 733 llvm::ConstantFoldFPBinOp(unsigned Opcode, const Register Op1,
 734                           const Register Op2, const MachineRegisterInfo &MRI) {
 735   const ConstantFP *Op2Cst = getConstantFPVRegVal(Op2, MRI);
 736   if (!Op2Cst)
 737     return std::nullopt;
 738
 739   const ConstantFP *Op1Cst = getConstantFPVRegVal(Op1, MRI);
 740   if (!Op1Cst)
 741     return std::nullopt;
 742
 743   APFloat C1 = Op1Cst->getValueAPF();
 744   const APFloat &C2 = Op2Cst->getValueAPF();
 745   switch (Opcode) {
 746   case TargetOpcode::G_FADD:
 747     C1.add(C2, APFloat::rmNearestTiesToEven);
 748     return C1;
 749   case TargetOpcode::G_FSUB:
 750     C1.subtract(C2, APFloat::rmNearestTiesToEven);
 751     return C1;
 752   case TargetOpcode::G_FMUL:
 753     C1.multiply(C2, APFloat::rmNearestTiesToEven);
 754     return C1;
 755   case TargetOpcode::G_FDIV:
 756     C1.divide(C2, APFloat::rmNearestTiesToEven);
 757     return C1;
 758   case TargetOpcode::G_FREM:
 759     C1.mod(C2);
 760     return C1;
 761   case TargetOpcode::G_FCOPYSIGN:
 762     C1.copySign(C2);
 763     return C1;
 764   case TargetOpcode::G_FMINNUM:
 765     return minnum(C1, C2);
 766   case TargetOpcode::G_FMAXNUM:
 767     return maxnum(C1, C2);
 768   case TargetOpcode::G_FMINIMUM:
 769     return minimum(C1, C2);
 770   case TargetOpcode::G_FMAXIMUM:
 771     return maximum(C1, C2);
 772   case TargetOpcode::G_FMINNUM_IEEE:
 773   case TargetOpcode::G_FMAXNUM_IEEE:
 774     // FIXME: These operations were unfortunately named. fminnum/fmaxnum do not
 775     // follow the IEEE behavior for signaling nans and follow libm's fmin/fmax,
 776     // and currently there isn't a nice wrapper in APFloat for the version with
 777     // correct snan handling.
 778     break;
 779   default:
 780     break;
 781   }
 782
 783   return std::nullopt;
 784 }
 785
 786 SmallVector<APInt>
 787 llvm::ConstantFoldVectorBinop(unsigned Opcode, const Register Op1,
 788                               const Register Op2,
 789                               const MachineRegisterInfo &MRI) {
 790   auto *SrcVec2 = getOpcodeDef<GBuildVector>(Op2, MRI);
 791   if (!SrcVec2)
 792     return SmallVector<APInt>();
 793
 794   auto *SrcVec1 = getOpcodeDef<GBuildVector>(Op1, MRI);
 795   if (!SrcVec1)
 796     return SmallVector<APInt>();
 797
 798   SmallVector<APInt> FoldedElements;
 799   for (unsigned Idx = 0, E = SrcVec1->getNumSources(); Idx < E; ++Idx) {
 800     auto MaybeCst = ConstantFoldBinOp(Opcode, SrcVec1->getSourceReg(Idx),
 801                                       SrcVec2->getSourceReg(Idx), MRI);
 802     if (!MaybeCst)
 803       return SmallVector<APInt>();
 804     FoldedElements.push_back(*MaybeCst);
 805   }
 806   return FoldedElements;
 807 }
 808
 809 bool llvm::isKnownNeverNaN(Register Val, const MachineRegisterInfo &MRI,
 810                            bool SNaN) {
 811   const MachineInstr *DefMI = MRI.getVRegDef(Val);
 812   if (!DefMI)
 813     return false;
 814
 815   const TargetMachine& TM = DefMI->getMF()->getTarget();
 816   if (DefMI->getFlag(MachineInstr::FmNoNans) || TM.Options.NoNaNsFPMath)
 817     return true;
 818
 819   // If the value is a constant, we can obviously see if it is a NaN or not.
 820   if (const ConstantFP *FPVal = getConstantFPVRegVal(Val, MRI)) {
 821     return !FPVal->getValueAPF().isNaN() ||
 822            (SNaN && !FPVal->getValueAPF().isSignaling());
 823   }
 824
 825   if (DefMI->getOpcode() == TargetOpcode::G_BUILD_VECTOR) {
 826     for (const auto &Op : DefMI->uses())
 827       if (!isKnownNeverNaN(Op.getReg(), MRI, SNaN))
 828         return false;
 829     return true;
 830   }
 831
 832   switch (DefMI->getOpcode()) {
 833   default:
 834     break;
 835   case TargetOpcode::G_FADD:
 836   case TargetOpcode::G_FSUB:
 837   case TargetOpcode::G_FMUL:
 838   case TargetOpcode::G_FDIV:
 839   case TargetOpcode::G_FREM:
 840   case TargetOpcode::G_FSIN:
 841   case TargetOpcode::G_FCOS:
 842   case TargetOpcode::G_FTAN:
 843   case TargetOpcode::G_FACOS:
 844   case TargetOpcode::G_FASIN:
 845   case TargetOpcode::G_FATAN:
 846   case TargetOpcode::G_FATAN2:
 847   case TargetOpcode::G_FCOSH:
 848   case TargetOpcode::G_FSINH:
 849   case TargetOpcode::G_FTANH:
 850   case TargetOpcode::G_FMA:
 851   case TargetOpcode::G_FMAD:
 852     if (SNaN)
 853       return true;
 854
 855     // TODO: Need isKnownNeverInfinity
 856     return false;
 857   case TargetOpcode::G_FMINNUM_IEEE:
 858   case TargetOpcode::G_FMAXNUM_IEEE: {
 859     if (SNaN)
 860       return true;
 861     // This can return a NaN if either operand is an sNaN, or if both operands
 862     // are NaN.
 863     return (isKnownNeverNaN(DefMI->getOperand(1).getReg(), MRI) &&
 864             isKnownNeverSNaN(DefMI->getOperand(2).getReg(), MRI)) ||
 865            (isKnownNeverSNaN(DefMI->getOperand(1).getReg(), MRI) &&
 866             isKnownNeverNaN(DefMI->getOperand(2).getReg(), MRI));
 867   }
 868   case TargetOpcode::G_FMINNUM:
 869   case TargetOpcode::G_FMAXNUM: {
 870     // Only one needs to be known not-nan, since it will be returned if the
 871     // other ends up being one.
 872     return isKnownNeverNaN(DefMI->getOperand(1).getReg(), MRI, SNaN) ||
 873            isKnownNeverNaN(DefMI->getOperand(2).getReg(), MRI, SNaN);
 874   }
 875   }
 876
 877   if (SNaN) {
 878     // FP operations quiet. For now, just handle the ones inserted during
 879     // legalization.
 880     switch (DefMI->getOpcode()) {
 881     case TargetOpcode::G_FPEXT:
 882     case TargetOpcode::G_FPTRUNC:
 883     case TargetOpcode::G_FCANONICALIZE:
 884       return true;
 885     default:
 886       return false;
 887     }
 888   }
 889
 890   return false;
 891 }
 892
 893 Align llvm::inferAlignFromPtrInfo(MachineFunction &MF,
 894                                   const MachinePointerInfo &MPO) {
 895   auto PSV = dyn_cast_if_present<const PseudoSourceValue *>(MPO.V);
 896   if (auto FSPV = dyn_cast_or_null<FixedStackPseudoSourceValue>(PSV)) {
 897     MachineFrameInfo &MFI = MF.getFrameInfo();
 898     return commonAlignment(MFI.getObjectAlign(FSPV->getFrameIndex()),
 899                            MPO.Offset);
 900   }
 901
 902   if (const Value *V = dyn_cast_if_present<const Value *>(MPO.V)) {
 903     const Module *M = MF.getFunction().getParent();
 904     return V->getPointerAlignment(M->getDataLayout());
 905   }
 906
 907   return Align(1);
 908 }
 909
 910 Register llvm::getFunctionLiveInPhysReg(MachineFunction &MF,
 911                                         const TargetInstrInfo &TII,
 912                                         MCRegister PhysReg,
 913                                         const TargetRegisterClass &RC,
 914                                         const DebugLoc &DL, LLT RegTy) {
 915   MachineBasicBlock &EntryMBB = MF.front();
 916   MachineRegisterInfo &MRI = MF.getRegInfo();
 917   Register LiveIn = MRI.getLiveInVirtReg(PhysReg);
 918   if (LiveIn) {
 919     MachineInstr *Def = MRI.getVRegDef(LiveIn);
 920     if (Def) {
 921       // FIXME: Should the verifier check this is in the entry block?
 922       assert(Def->getParent() == &EntryMBB && "live-in copy not in entry block");
 923       return LiveIn;
 924     }
 925
 926     // It's possible the incoming argument register and copy was added during
 927     // lowering, but later deleted due to being/becoming dead. If this happens,
 928     // re-insert the copy.
 929   } else {
 930     // The live in register was not present, so add it.
 931     LiveIn = MF.addLiveIn(PhysReg, &RC);
 932     if (RegTy.isValid())
 933       MRI.setType(LiveIn, RegTy);
 934   }
 935
 936   BuildMI(EntryMBB, EntryMBB.begin(), DL, TII.get(TargetOpcode::COPY), LiveIn)
 937     .addReg(PhysReg);
 938   if (!EntryMBB.isLiveIn(PhysReg))
 939     EntryMBB.addLiveIn(PhysReg);
 940   return LiveIn;
 941 }
 942
 943 std::optional<APInt> llvm::ConstantFoldExtOp(unsigned Opcode,
 944                                              const Register Op1, uint64_t Imm,
 945                                              const MachineRegisterInfo &MRI) {
 946   auto MaybeOp1Cst = getIConstantVRegVal(Op1, MRI);
 947   if (MaybeOp1Cst) {
 948     switch (Opcode) {
 949     default:
 950       break;
 951     case TargetOpcode::G_SEXT_INREG: {
 952       LLT Ty = MRI.getType(Op1);
 953       return MaybeOp1Cst->trunc(Imm).sext(Ty.getScalarSizeInBits());
 954     }
 955     }
 956   }
 957   return std::nullopt;
 958 }
 959
 960 std::optional<APInt> llvm::ConstantFoldCastOp(unsigned Opcode, LLT DstTy,
 961                                               const Register Op0,
 962                                               const MachineRegisterInfo &MRI) {
 963   std::optional<APInt> Val = getIConstantVRegVal(Op0, MRI);
 964   if (!Val)
 965     return Val;
 966
 967   const unsigned DstSize = DstTy.getScalarSizeInBits();
 968
 969   switch (Opcode) {
 970   case TargetOpcode::G_SEXT:
 971     return Val->sext(DstSize);
 972   case TargetOpcode::G_ZEXT:
 973   case TargetOpcode::G_ANYEXT:
 974     // TODO: DAG considers target preference when constant folding any_extend.
 975     return Val->zext(DstSize);
 976   default:
 977     break;
 978   }
 979
 980   llvm_unreachable("unexpected cast opcode to constant fold");
 981 }
 982
 983 std::optional<APFloat>
 984 llvm::ConstantFoldIntToFloat(unsigned Opcode, LLT DstTy, Register Src,
 985                              const MachineRegisterInfo &MRI) {
 986   assert(Opcode == TargetOpcode::G_SITOFP || Opcode == TargetOpcode::G_UITOFP);
 987   if (auto MaybeSrcVal = getIConstantVRegVal(Src, MRI)) {
 988     APFloat DstVal(getFltSemanticForLLT(DstTy));
 989     DstVal.convertFromAPInt(*MaybeSrcVal, Opcode == TargetOpcode::G_SITOFP,
 990                             APFloat::rmNearestTiesToEven);
 991     return DstVal;
 992   }
 993   return std::nullopt;
 994 }
 995
 996 std::optional<SmallVector<unsigned>>
 997 llvm::ConstantFoldCountZeros(Register Src, const MachineRegisterInfo &MRI,
 998                              std::function<unsigned(APInt)> CB) {
 999   LLT Ty = MRI.getType(Src);
1000   SmallVector<unsigned> FoldedCTLZs;
1001   auto tryFoldScalar = [&](Register R) -> std::optional<unsigned> {
1002     auto MaybeCst = getIConstantVRegVal(R, MRI);
1003     if (!MaybeCst)
1004       return std::nullopt;
1005     return CB(*MaybeCst);
1006   };
1007   if (Ty.isVector()) {
1008     // Try to constant fold each element.
1009     auto *BV = getOpcodeDef<GBuildVector>(Src, MRI);
1010     if (!BV)
1011       return std::nullopt;
1012     for (unsigned SrcIdx = 0; SrcIdx < BV->getNumSources(); ++SrcIdx) {
1013       if (auto MaybeFold = tryFoldScalar(BV->getSourceReg(SrcIdx))) {
1014         FoldedCTLZs.emplace_back(*MaybeFold);
1015         continue;
1016       }
1017       return std::nullopt;
1018     }
1019     return FoldedCTLZs;
1020   }
1021   if (auto MaybeCst = tryFoldScalar(Src)) {
1022     FoldedCTLZs.emplace_back(*MaybeCst);
1023     return FoldedCTLZs;
1024   }
1025   return std::nullopt;
1026 }
1027
1028 std::optional<SmallVector<APInt>>
1029 llvm::ConstantFoldICmp(unsigned Pred, const Register Op1, const Register Op2,
1030                        const MachineRegisterInfo &MRI) {
1031   LLT Ty = MRI.getType(Op1);
1032   if (Ty != MRI.getType(Op2))
1033     return std::nullopt;
1034
1035   auto TryFoldScalar = [&MRI, Pred](Register LHS,
1036                                     Register RHS) -> std::optional<APInt> {
1037     auto LHSCst = getIConstantVRegVal(LHS, MRI);
1038     auto RHSCst = getIConstantVRegVal(RHS, MRI);
1039     if (!LHSCst || !RHSCst)
1040       return std::nullopt;
1041
1042     switch (Pred) {
1043     case CmpInst::Predicate::ICMP_EQ:
1044       return APInt(/*numBits=*/1, LHSCst->eq(*RHSCst));
1045     case CmpInst::Predicate::ICMP_NE:
1046       return APInt(/*numBits=*/1, LHSCst->ne(*RHSCst));
1047     case CmpInst::Predicate::ICMP_UGT:
1048       return APInt(/*numBits=*/1, LHSCst->ugt(*RHSCst));
1049     case CmpInst::Predicate::ICMP_UGE:
1050       return APInt(/*numBits=*/1, LHSCst->uge(*RHSCst));
1051     case CmpInst::Predicate::ICMP_ULT:
1052       return APInt(/*numBits=*/1, LHSCst->ult(*RHSCst));
1053     case CmpInst::Predicate::ICMP_ULE:
1054       return APInt(/*numBits=*/1, LHSCst->ule(*RHSCst));
1055     case CmpInst::Predicate::ICMP_SGT:
1056       return APInt(/*numBits=*/1, LHSCst->sgt(*RHSCst));
1057     case CmpInst::Predicate::ICMP_SGE:
1058       return APInt(/*numBits=*/1, LHSCst->sge(*RHSCst));
1059     case CmpInst::Predicate::ICMP_SLT:
1060       return APInt(/*numBits=*/1, LHSCst->slt(*RHSCst));
1061     case CmpInst::Predicate::ICMP_SLE:
1062       return APInt(/*numBits=*/1, LHSCst->sle(*RHSCst));
1063     default:
1064       return std::nullopt;
1065     }
1066   };
1067
1068   SmallVector<APInt> FoldedICmps;
1069
1070   if (Ty.isVector()) {
1071     // Try to constant fold each element.
1072     auto *BV1 = getOpcodeDef<GBuildVector>(Op1, MRI);
1073     auto *BV2 = getOpcodeDef<GBuildVector>(Op2, MRI);
1074     if (!BV1 || !BV2)
1075       return std::nullopt;
1076     assert(BV1->getNumSources() == BV2->getNumSources() && "Invalid vectors");
1077     for (unsigned I = 0; I < BV1->getNumSources(); ++I) {
1078       if (auto MaybeFold =
1079               TryFoldScalar(BV1->getSourceReg(I), BV2->getSourceReg(I))) {
1080         FoldedICmps.emplace_back(*MaybeFold);
1081         continue;
1082       }
1083       return std::nullopt;
1084     }
1085     return FoldedICmps;
1086   }
1087
1088   if (auto MaybeCst = TryFoldScalar(Op1, Op2)) {
1089     FoldedICmps.emplace_back(*MaybeCst);
1090     return FoldedICmps;
1091   }
1092
1093   return std::nullopt;
1094 }
1095
1096 bool llvm::isKnownToBeAPowerOfTwo(Register Reg, const MachineRegisterInfo &MRI,
1097                                   GISelKnownBits *KB) {
1098   std::optional<DefinitionAndSourceRegister> DefSrcReg =
1099       getDefSrcRegIgnoringCopies(Reg, MRI);
1100   if (!DefSrcReg)
1101     return false;
1102
1103   const MachineInstr &MI = *DefSrcReg->MI;
1104   const LLT Ty = MRI.getType(Reg);
1105
1106   switch (MI.getOpcode()) {
1107   case TargetOpcode::G_CONSTANT: {
1108     unsigned BitWidth = Ty.getScalarSizeInBits();
1109     const ConstantInt *CI = MI.getOperand(1).getCImm();
1110     return CI->getValue().zextOrTrunc(BitWidth).isPowerOf2();
1111   }
1112   case TargetOpcode::G_SHL: {
1113     // A left-shift of a constant one will have exactly one bit set because
1114     // shifting the bit off the end is undefined.
1115
1116     // TODO: Constant splat
1117     if (auto ConstLHS = getIConstantVRegVal(MI.getOperand(1).getReg(), MRI)) {
1118       if (*ConstLHS == 1)
1119         return true;
1120     }
1121
1122     break;
1123   }
1124   case TargetOpcode::G_LSHR: {
1125     if (auto ConstLHS = getIConstantVRegVal(MI.getOperand(1).getReg(), MRI)) {
1126       if (ConstLHS->isSignMask())
1127         return true;
1128     }
1129
1130     break;
1131   }
1132   case TargetOpcode::G_BUILD_VECTOR: {
1133     // TODO: Probably should have a recursion depth guard since you could have
1134     // bitcasted vector elements.
1135     for (const MachineOperand &MO : llvm::drop_begin(MI.operands()))
1136       if (!isKnownToBeAPowerOfTwo(MO.getReg(), MRI, KB))
1137         return false;
1138
1139     return true;
1140   }
1141   case TargetOpcode::G_BUILD_VECTOR_TRUNC: {
1142     // Only handle constants since we would need to know if number of leading
1143     // zeros is greater than the truncation amount.
1144     const unsigned BitWidth = Ty.getScalarSizeInBits();
1145     for (const MachineOperand &MO : llvm::drop_begin(MI.operands())) {
1146       auto Const = getIConstantVRegVal(MO.getReg(), MRI);
1147       if (!Const || !Const->zextOrTrunc(BitWidth).isPowerOf2())
1148         return false;
1149     }
1150
1151     return true;
1152   }
1153   default:
1154     break;
1155   }
1156
1157   if (!KB)
1158     return false;
1159
1160   // More could be done here, though the above checks are enough
1161   // to handle some common cases.
1162
1163   // Fall back to computeKnownBits to catch other known cases.
1164   KnownBits Known = KB->getKnownBits(Reg);
1165   return (Known.countMaxPopulation() == 1) && (Known.countMinPopulation() == 1);
1166 }
1167
1168 void llvm::getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU) {
1169   AU.addPreserved<StackProtector>();
1170 }
1171
1172 LLT llvm::getLCMType(LLT OrigTy, LLT TargetTy) {
1173   if (OrigTy.getSizeInBits() == TargetTy.getSizeInBits())
1174     return OrigTy;
1175
1176   if (OrigTy.isVector() && TargetTy.isVector()) {
1177     LLT OrigElt = OrigTy.getElementType();
1178     LLT TargetElt = TargetTy.getElementType();
1179
1180     // TODO: The docstring for this function says the intention is to use this
1181     // function to build MERGE/UNMERGE instructions. It won't be the case that
1182     // we generate a MERGE/UNMERGE between fixed and scalable vector types. We
1183     // could implement getLCMType between the two in the future if there was a
1184     // need, but it is not worth it now as this function should not be used in
1185     // that way.
1186     assert(((OrigTy.isScalableVector() && !TargetTy.isFixedVector()) ||
1187             (OrigTy.isFixedVector() && !TargetTy.isScalableVector())) &&
1188            "getLCMType not implemented between fixed and scalable vectors.");
1189
1190     if (OrigElt.getSizeInBits() == TargetElt.getSizeInBits()) {
1191       int GCDMinElts = std::gcd(OrigTy.getElementCount().getKnownMinValue(),
1192                                 TargetTy.getElementCount().getKnownMinValue());
1193       // Prefer the original element type.
1194       ElementCount Mul = OrigTy.getElementCount().multiplyCoefficientBy(
1195           TargetTy.getElementCount().getKnownMinValue());
1196       return LLT::vector(Mul.divideCoefficientBy(GCDMinElts),
1197                          OrigTy.getElementType());
1198     }
1199     unsigned LCM = std::lcm(OrigTy.getSizeInBits().getKnownMinValue(),
1200                             TargetTy.getSizeInBits().getKnownMinValue());
1201     return LLT::vector(
1202         ElementCount::get(LCM / OrigElt.getSizeInBits(), OrigTy.isScalable()),
1203         OrigElt);
1204   }
1205
1206   // One type is scalar, one type is vector
1207   if (OrigTy.isVector() || TargetTy.isVector()) {
1208     LLT VecTy = OrigTy.isVector() ? OrigTy : TargetTy;
1209     LLT ScalarTy = OrigTy.isVector() ? TargetTy : OrigTy;
1210     LLT EltTy = VecTy.getElementType();
1211     LLT OrigEltTy = OrigTy.isVector() ? OrigTy.getElementType() : OrigTy;
1212
1213     // Prefer scalar type from OrigTy.
1214     if (EltTy.getSizeInBits() == ScalarTy.getSizeInBits())
1215       return LLT::vector(VecTy.getElementCount(), OrigEltTy);
1216
1217     // Different size scalars. Create vector with the same total size.
1218     // LCM will take fixed/scalable from VecTy.
1219     unsigned LCM = std::lcm(EltTy.getSizeInBits().getFixedValue() *
1220                                 VecTy.getElementCount().getKnownMinValue(),
1221                             ScalarTy.getSizeInBits().getFixedValue());
1222     // Prefer type from OrigTy
1223     return LLT::vector(ElementCount::get(LCM / OrigEltTy.getSizeInBits(),
1224                                          VecTy.getElementCount().isScalable()),
1225                        OrigEltTy);
1226   }
1227
1228   // At this point, both types are scalars of different size
1229   unsigned LCM = std::lcm(OrigTy.getSizeInBits().getFixedValue(),
1230                           TargetTy.getSizeInBits().getFixedValue());
1231   // Preserve pointer types.
1232   if (LCM == OrigTy.getSizeInBits())
1233     return OrigTy;
1234   if (LCM == TargetTy.getSizeInBits())
1235     return TargetTy;
1236   return LLT::scalar(LCM);
1237 }
1238
1239 LLT llvm::getCoverTy(LLT OrigTy, LLT TargetTy) {
1240
1241   if ((OrigTy.isScalableVector() && TargetTy.isFixedVector()) ||
1242       (OrigTy.isFixedVector() && TargetTy.isScalableVector()))
1243     llvm_unreachable(
1244         "getCoverTy not implemented between fixed and scalable vectors.");
1245
1246   if (!OrigTy.isVector() || !TargetTy.isVector() || OrigTy == TargetTy ||
1247       (OrigTy.getScalarSizeInBits() != TargetTy.getScalarSizeInBits()))
1248     return getLCMType(OrigTy, TargetTy);
1249
1250   unsigned OrigTyNumElts = OrigTy.getElementCount().getKnownMinValue();
1251   unsigned TargetTyNumElts = TargetTy.getElementCount().getKnownMinValue();
1252   if (OrigTyNumElts % TargetTyNumElts == 0)
1253     return OrigTy;
1254
1255   unsigned NumElts = alignTo(OrigTyNumElts, TargetTyNumElts);
1256   return LLT::scalarOrVector(ElementCount::getFixed(NumElts),
1257                              OrigTy.getElementType());
1258 }
1259
1260 LLT llvm::getGCDType(LLT OrigTy, LLT TargetTy) {
1261   if (OrigTy.getSizeInBits() == TargetTy.getSizeInBits())
1262     return OrigTy;
1263
1264   if (OrigTy.isVector() && TargetTy.isVector()) {
1265     LLT OrigElt = OrigTy.getElementType();
1266
1267     // TODO: The docstring for this function says the intention is to use this
1268     // function to build MERGE/UNMERGE instructions. It won't be the case that
1269     // we generate a MERGE/UNMERGE between fixed and scalable vector types. We
1270     // could implement getGCDType between the two in the future if there was a
1271     // need, but it is not worth it now as this function should not be used in
1272     // that way.
1273     assert(((OrigTy.isScalableVector() && !TargetTy.isFixedVector()) ||
1274             (OrigTy.isFixedVector() && !TargetTy.isScalableVector())) &&
1275            "getGCDType not implemented between fixed and scalable vectors.");
1276
1277     unsigned GCD = std::gcd(OrigTy.getSizeInBits().getKnownMinValue(),
1278                             TargetTy.getSizeInBits().getKnownMinValue());
1279     if (GCD == OrigElt.getSizeInBits())
1280       return LLT::scalarOrVector(ElementCount::get(1, OrigTy.isScalable()),
1281                                  OrigElt);
1282
1283     // Cannot produce original element type, but both have vscale in common.
1284     if (GCD < OrigElt.getSizeInBits())
1285       return LLT::scalarOrVector(ElementCount::get(1, OrigTy.isScalable()),
1286                                  GCD);
1287
1288     return LLT::vector(
1289         ElementCount::get(GCD / OrigElt.getSizeInBits().getFixedValue(),
1290                           OrigTy.isScalable()),
1291         OrigElt);
1292   }
1293
1294   // If one type is vector and the element size matches the scalar size, then
1295   // the gcd is the scalar type.
1296   if (OrigTy.isVector() &&
1297       OrigTy.getElementType().getSizeInBits() == TargetTy.getSizeInBits())
1298     return OrigTy.getElementType();
1299   if (TargetTy.isVector() &&
1300       TargetTy.getElementType().getSizeInBits() == OrigTy.getSizeInBits())
1301     return OrigTy;
1302
1303   // At this point, both types are either scalars of different type or one is a
1304   // vector and one is a scalar. If both types are scalars, the GCD type is the
1305   // GCD between the two scalar sizes. If one is vector and one is scalar, then
1306   // the GCD type is the GCD between the scalar and the vector element size.
1307   LLT OrigScalar = OrigTy.getScalarType();
1308   LLT TargetScalar = TargetTy.getScalarType();
1309   unsigned GCD = std::gcd(OrigScalar.getSizeInBits().getFixedValue(),
1310                           TargetScalar.getSizeInBits().getFixedValue());
1311   return LLT::scalar(GCD);
1312 }
1313
1314 std::optional<int> llvm::getSplatIndex(MachineInstr &MI) {
1315   assert(MI.getOpcode() == TargetOpcode::G_SHUFFLE_VECTOR &&
1316          "Only G_SHUFFLE_VECTOR can have a splat index!");
1317   ArrayRef<int> Mask = MI.getOperand(3).getShuffleMask();
1318   auto FirstDefinedIdx = find_if(Mask, [](int Elt) { return Elt >= 0; });
1319
1320   // If all elements are undefined, this shuffle can be considered a splat.
1321   // Return 0 for better potential for callers to simplify.
1322   if (FirstDefinedIdx == Mask.end())
1323     return 0;
1324
1325   // Make sure all remaining elements are either undef or the same
1326   // as the first non-undef value.
1327   int SplatValue = *FirstDefinedIdx;
1328   if (any_of(make_range(std::next(FirstDefinedIdx), Mask.end()),
1329              [&SplatValue](int Elt) { return Elt >= 0 && Elt != SplatValue; }))
1330     return std::nullopt;
1331
1332   return SplatValue;
1333 }
1334
1335 static bool isBuildVectorOp(unsigned Opcode) {
1336   return Opcode == TargetOpcode::G_BUILD_VECTOR ||
1337          Opcode == TargetOpcode::G_BUILD_VECTOR_TRUNC;
1338 }
1339
1340 namespace {
1341
1342 std::optional<ValueAndVReg> getAnyConstantSplat(Register VReg,
1343                                                 const MachineRegisterInfo &MRI,
1344                                                 bool AllowUndef) {
1345   MachineInstr *MI = getDefIgnoringCopies(VReg, MRI);
1346   if (!MI)
1347     return std::nullopt;
1348
1349   bool isConcatVectorsOp = MI->getOpcode() == TargetOpcode::G_CONCAT_VECTORS;
1350   if (!isBuildVectorOp(MI->getOpcode()) && !isConcatVectorsOp)
1351     return std::nullopt;
1352
1353   std::optional<ValueAndVReg> SplatValAndReg;
1354   for (MachineOperand &Op : MI->uses()) {
1355     Register Element = Op.getReg();
1356     // If we have a G_CONCAT_VECTOR, we recursively look into the
1357     // vectors that we're concatenating to see if they're splats.
1358     auto ElementValAndReg =
1359         isConcatVectorsOp
1360             ? getAnyConstantSplat(Element, MRI, AllowUndef)
1361             : getAnyConstantVRegValWithLookThrough(Element, MRI, true, true);
1362
1363     // If AllowUndef, treat undef as value that will result in a constant splat.
1364     if (!ElementValAndReg) {
1365       if (AllowUndef && isa<GImplicitDef>(MRI.getVRegDef(Element)))
1366         continue;
1367       return std::nullopt;
1368     }
1369
1370     // Record splat value
1371     if (!SplatValAndReg)
1372       SplatValAndReg = ElementValAndReg;
1373
1374     // Different constant than the one already recorded, not a constant splat.
1375     if (SplatValAndReg->Value != ElementValAndReg->Value)
1376       return std::nullopt;
1377   }
1378
1379   return SplatValAndReg;
1380 }
1381
1382 } // end anonymous namespace
1383
1384 bool llvm::isBuildVectorConstantSplat(const Register Reg,
1385                                       const MachineRegisterInfo &MRI,
1386                                       int64_t SplatValue, bool AllowUndef) {
1387   if (auto SplatValAndReg = getAnyConstantSplat(Reg, MRI, AllowUndef))
1388     return mi_match(SplatValAndReg->VReg, MRI, m_SpecificICst(SplatValue));
1389   return false;
1390 }
1391
1392 bool llvm::isBuildVectorConstantSplat(const MachineInstr &MI,
1393                                       const MachineRegisterInfo &MRI,
1394                                       int64_t SplatValue, bool AllowUndef) {
1395   return isBuildVectorConstantSplat(MI.getOperand(0).getReg(), MRI, SplatValue,
1396                                     AllowUndef);
1397 }
1398
1399 std::optional<APInt>
1400 llvm::getIConstantSplatVal(const Register Reg, const MachineRegisterInfo &MRI) {
1401   if (auto SplatValAndReg =
1402           getAnyConstantSplat(Reg, MRI, /* AllowUndef */ false)) {
1403     if (std::optional<ValueAndVReg> ValAndVReg =
1404         getIConstantVRegValWithLookThrough(SplatValAndReg->VReg, MRI))
1405       return ValAndVReg->Value;
1406   }
1407
1408   return std::nullopt;
1409 }
1410
1411 std::optional<APInt>
1412 llvm::getIConstantSplatVal(const MachineInstr &MI,
1413                            const MachineRegisterInfo &MRI) {
1414   return getIConstantSplatVal(MI.getOperand(0).getReg(), MRI);
1415 }
1416
1417 std::optional<int64_t>
1418 llvm::getIConstantSplatSExtVal(const Register Reg,
1419                                const MachineRegisterInfo &MRI) {
1420   if (auto SplatValAndReg =
1421           getAnyConstantSplat(Reg, MRI, /* AllowUndef */ false))
1422     return getIConstantVRegSExtVal(SplatValAndReg->VReg, MRI);
1423   return std::nullopt;
1424 }
1425
1426 std::optional<int64_t>
1427 llvm::getIConstantSplatSExtVal(const MachineInstr &MI,
1428                                const MachineRegisterInfo &MRI) {
1429   return getIConstantSplatSExtVal(MI.getOperand(0).getReg(), MRI);
1430 }
1431
1432 std::optional<FPValueAndVReg>
1433 llvm::getFConstantSplat(Register VReg, const MachineRegisterInfo &MRI,
1434                         bool AllowUndef) {
1435   if (auto SplatValAndReg = getAnyConstantSplat(VReg, MRI, AllowUndef))
1436     return getFConstantVRegValWithLookThrough(SplatValAndReg->VReg, MRI);
1437   return std::nullopt;
1438 }
1439
1440 bool llvm::isBuildVectorAllZeros(const MachineInstr &MI,
1441                                  const MachineRegisterInfo &MRI,
1442                                  bool AllowUndef) {
1443   return isBuildVectorConstantSplat(MI, MRI, 0, AllowUndef);
1444 }
1445
1446 bool llvm::isBuildVectorAllOnes(const MachineInstr &MI,
1447                                 const MachineRegisterInfo &MRI,
1448                                 bool AllowUndef) {
1449   return isBuildVectorConstantSplat(MI, MRI, -1, AllowUndef);
1450 }
1451
1452 std::optional<RegOrConstant>
1453 llvm::getVectorSplat(const MachineInstr &MI, const MachineRegisterInfo &MRI) {
1454   unsigned Opc = MI.getOpcode();
1455   if (!isBuildVectorOp(Opc))
1456     return std::nullopt;
1457   if (auto Splat = getIConstantSplatSExtVal(MI, MRI))
1458     return RegOrConstant(*Splat);
1459   auto Reg = MI.getOperand(1).getReg();
1460   if (any_of(drop_begin(MI.operands(), 2),
1461              [&Reg](const MachineOperand &Op) { return Op.getReg() != Reg; }))
1462     return std::nullopt;
1463   return RegOrConstant(Reg);
1464 }
1465
1466 static bool isConstantScalar(const MachineInstr &MI,
1467                              const MachineRegisterInfo &MRI,
1468                              bool AllowFP = true,
1469                              bool AllowOpaqueConstants = true) {
1470   switch (MI.getOpcode()) {
1471   case TargetOpcode::G_CONSTANT:
1472   case TargetOpcode::G_IMPLICIT_DEF:
1473     return true;
1474   case TargetOpcode::G_FCONSTANT:
1475     return AllowFP;
1476   case TargetOpcode::G_GLOBAL_VALUE:
1477   case TargetOpcode::G_FRAME_INDEX:
1478   case TargetOpcode::G_BLOCK_ADDR:
1479   case TargetOpcode::G_JUMP_TABLE:
1480     return AllowOpaqueConstants;
1481   default:
1482     return false;
1483   }
1484 }
1485
1486 bool llvm::isConstantOrConstantVector(MachineInstr &MI,
1487                                       const MachineRegisterInfo &MRI) {
1488   Register Def = MI.getOperand(0).getReg();
1489   if (auto C = getIConstantVRegValWithLookThrough(Def, MRI))
1490     return true;
1491   GBuildVector *BV = dyn_cast<GBuildVector>(&MI);
1492   if (!BV)
1493     return false;
1494   for (unsigned SrcIdx = 0; SrcIdx < BV->getNumSources(); ++SrcIdx) {
1495     if (getIConstantVRegValWithLookThrough(BV->getSourceReg(SrcIdx), MRI) ||
1496         getOpcodeDef<GImplicitDef>(BV->getSourceReg(SrcIdx), MRI))
1497       continue;
1498     return false;
1499   }
1500   return true;
1501 }
1502
1503 bool llvm::isConstantOrConstantVector(const MachineInstr &MI,
1504                                       const MachineRegisterInfo &MRI,
1505                                       bool AllowFP, bool AllowOpaqueConstants) {
1506   if (isConstantScalar(MI, MRI, AllowFP, AllowOpaqueConstants))
1507     return true;
1508
1509   if (!isBuildVectorOp(MI.getOpcode()))
1510     return false;
1511
1512   const unsigned NumOps = MI.getNumOperands();
1513   for (unsigned I = 1; I != NumOps; ++I) {
1514     const MachineInstr *ElementDef = MRI.getVRegDef(MI.getOperand(I).getReg());
1515     if (!isConstantScalar(*ElementDef, MRI, AllowFP, AllowOpaqueConstants))
1516       return false;
1517   }
1518
1519   return true;
1520 }
1521
1522 std::optional<APInt>
1523 llvm::isConstantOrConstantSplatVector(MachineInstr &MI,
1524                                       const MachineRegisterInfo &MRI) {
1525   Register Def = MI.getOperand(0).getReg();
1526   if (auto C = getIConstantVRegValWithLookThrough(Def, MRI))
1527     return C->Value;
1528   auto MaybeCst = getIConstantSplatSExtVal(MI, MRI);
1529   if (!MaybeCst)
1530     return std::nullopt;
1531   const unsigned ScalarSize = MRI.getType(Def).getScalarSizeInBits();
1532   return APInt(ScalarSize, *MaybeCst, true);
1533 }
1534
1535 std::optional<APFloat>
1536 llvm::isConstantOrConstantSplatVectorFP(MachineInstr &MI,
1537                                         const MachineRegisterInfo &MRI) {
1538   Register Def = MI.getOperand(0).getReg();
1539   if (auto FpConst = getFConstantVRegValWithLookThrough(Def, MRI))
1540     return FpConst->Value;
1541   auto MaybeCstFP = getFConstantSplat(Def, MRI, /*allowUndef=*/false);
1542   if (!MaybeCstFP)
1543     return std::nullopt;
1544   return MaybeCstFP->Value;
1545 }
1546
1547 bool llvm::isNullOrNullSplat(const MachineInstr &MI,
1548                              const MachineRegisterInfo &MRI, bool AllowUndefs) {
1549   switch (MI.getOpcode()) {
1550   case TargetOpcode::G_IMPLICIT_DEF:
1551     return AllowUndefs;
1552   case TargetOpcode::G_CONSTANT:
1553     return MI.getOperand(1).getCImm()->isNullValue();
1554   case TargetOpcode::G_FCONSTANT: {
1555     const ConstantFP *FPImm = MI.getOperand(1).getFPImm();
1556     return FPImm->isZero() && !FPImm->isNegative();
1557   }
1558   default:
1559     if (!AllowUndefs) // TODO: isBuildVectorAllZeros assumes undef is OK already
1560       return false;
1561     return isBuildVectorAllZeros(MI, MRI);
1562   }
1563 }
1564
1565 bool llvm::isAllOnesOrAllOnesSplat(const MachineInstr &MI,
1566                                    const MachineRegisterInfo &MRI,
1567                                    bool AllowUndefs) {
1568   switch (MI.getOpcode()) {
1569   case TargetOpcode::G_IMPLICIT_DEF:
1570     return AllowUndefs;
1571   case TargetOpcode::G_CONSTANT:
1572     return MI.getOperand(1).getCImm()->isAllOnesValue();
1573   default:
1574     if (!AllowUndefs) // TODO: isBuildVectorAllOnes assumes undef is OK already
1575       return false;
1576     return isBuildVectorAllOnes(MI, MRI);
1577   }
1578 }
1579
1580 bool llvm::matchUnaryPredicate(
1581     const MachineRegisterInfo &MRI, Register Reg,
1582     std::function<bool(const Constant *ConstVal)> Match, bool AllowUndefs) {
1583
1584   const MachineInstr *Def = getDefIgnoringCopies(Reg, MRI);
1585   if (AllowUndefs && Def->getOpcode() == TargetOpcode::G_IMPLICIT_DEF)
1586     return Match(nullptr);
1587
1588   // TODO: Also handle fconstant
1589   if (Def->getOpcode() == TargetOpcode::G_CONSTANT)
1590     return Match(Def->getOperand(1).getCImm());
1591
1592   if (Def->getOpcode() != TargetOpcode::G_BUILD_VECTOR)
1593     return false;
1594
1595   for (unsigned I = 1, E = Def->getNumOperands(); I != E; ++I) {
1596     Register SrcElt = Def->getOperand(I).getReg();
1597     const MachineInstr *SrcDef = getDefIgnoringCopies(SrcElt, MRI);
1598     if (AllowUndefs && SrcDef->getOpcode() == TargetOpcode::G_IMPLICIT_DEF) {
1599       if (!Match(nullptr))
1600         return false;
1601       continue;
1602     }
1603
1604     if (SrcDef->getOpcode() != TargetOpcode::G_CONSTANT ||
1605         !Match(SrcDef->getOperand(1).getCImm()))
1606       return false;
1607   }
1608
1609   return true;
1610 }
1611
1612 bool llvm::isConstTrueVal(const TargetLowering &TLI, int64_t Val, bool IsVector,
1613                           bool IsFP) {
1614   switch (TLI.getBooleanContents(IsVector, IsFP)) {
1615   case TargetLowering::UndefinedBooleanContent:
1616     return Val & 0x1;
1617   case TargetLowering::ZeroOrOneBooleanContent:
1618     return Val == 1;
1619   case TargetLowering::ZeroOrNegativeOneBooleanContent:
1620     return Val == -1;
1621   }
1622   llvm_unreachable("Invalid boolean contents");
1623 }
1624
1625 bool llvm::isConstFalseVal(const TargetLowering &TLI, int64_t Val,
1626                            bool IsVector, bool IsFP) {
1627   switch (TLI.getBooleanContents(IsVector, IsFP)) {
1628   case TargetLowering::UndefinedBooleanContent:
1629     return ~Val & 0x1;
1630   case TargetLowering::ZeroOrOneBooleanContent:
1631   case TargetLowering::ZeroOrNegativeOneBooleanContent:
1632     return Val == 0;
1633   }
1634   llvm_unreachable("Invalid boolean contents");
1635 }
1636
1637 int64_t llvm::getICmpTrueVal(const TargetLowering &TLI, bool IsVector,
1638                              bool IsFP) {
1639   switch (TLI.getBooleanContents(IsVector, IsFP)) {
1640   case TargetLowering::UndefinedBooleanContent:
1641   case TargetLowering::ZeroOrOneBooleanContent:
1642     return 1;
1643   case TargetLowering::ZeroOrNegativeOneBooleanContent:
1644     return -1;
1645   }
1646   llvm_unreachable("Invalid boolean contents");
1647 }
1648
1649 void llvm::saveUsesAndErase(MachineInstr &MI, MachineRegisterInfo &MRI,
1650                             LostDebugLocObserver *LocObserver,
1651                             SmallInstListTy &DeadInstChain) {
1652   for (MachineOperand &Op : MI.uses()) {
1653     if (Op.isReg() && Op.getReg().isVirtual())
1654       DeadInstChain.insert(MRI.getVRegDef(Op.getReg()));
1655   }
1656   LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
1657   DeadInstChain.remove(&MI);
1658   MI.eraseFromParent();
1659   if (LocObserver)
1660     LocObserver->checkpoint(false);
1661 }
1662
1663 void llvm::eraseInstrs(ArrayRef<MachineInstr *> DeadInstrs,
1664                        MachineRegisterInfo &MRI,
1665                        LostDebugLocObserver *LocObserver) {
1666   SmallInstListTy DeadInstChain;
1667   for (MachineInstr *MI : DeadInstrs)
1668     saveUsesAndErase(*MI, MRI, LocObserver, DeadInstChain);
1669
1670   while (!DeadInstChain.empty()) {
1671     MachineInstr *Inst = DeadInstChain.pop_back_val();
1672     if (!isTriviallyDead(*Inst, MRI))
1673       continue;
1674     saveUsesAndErase(*Inst, MRI, LocObserver, DeadInstChain);
1675   }
1676 }
1677
1678 void llvm::eraseInstr(MachineInstr &MI, MachineRegisterInfo &MRI,
1679                       LostDebugLocObserver *LocObserver) {
1680   return eraseInstrs({&MI}, MRI, LocObserver);
1681 }
1682
1683 void llvm::salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI) {
1684   for (auto &Def : MI.defs()) {
1685     assert(Def.isReg() && "Must be a reg");
1686
1687     SmallVector<MachineOperand *, 16> DbgUsers;
1688     for (auto &MOUse : MRI.use_operands(Def.getReg())) {
1689       MachineInstr *DbgValue = MOUse.getParent();
1690       // Ignore partially formed DBG_VALUEs.
1691       if (DbgValue->isNonListDebugValue() && DbgValue->getNumOperands() == 4) {
1692         DbgUsers.push_back(&MOUse);
1693       }
1694     }
1695
1696     if (!DbgUsers.empty()) {
1697       salvageDebugInfoForDbgValue(MRI, MI, DbgUsers);
1698     }
1699   }
1700 }
1701
1702 bool llvm::isPreISelGenericFloatingPointOpcode(unsigned Opc) {
1703   switch (Opc) {
1704   case TargetOpcode::G_FABS:
1705   case TargetOpcode::G_FADD:
1706   case TargetOpcode::G_FCANONICALIZE:
1707   case TargetOpcode::G_FCEIL:
1708   case TargetOpcode::G_FCONSTANT:
1709   case TargetOpcode::G_FCOPYSIGN:
1710   case TargetOpcode::G_FCOS:
1711   case TargetOpcode::G_FDIV:
1712   case TargetOpcode::G_FEXP2:
1713   case TargetOpcode::G_FEXP:
1714   case TargetOpcode::G_FFLOOR:
1715   case TargetOpcode::G_FLOG10:
1716   case TargetOpcode::G_FLOG2:
1717   case TargetOpcode::G_FLOG:
1718   case TargetOpcode::G_FMA:
1719   case TargetOpcode::G_FMAD:
1720   case TargetOpcode::G_FMAXIMUM:
1721   case TargetOpcode::G_FMAXNUM:
1722   case TargetOpcode::G_FMAXNUM_IEEE:
1723   case TargetOpcode::G_FMINIMUM:
1724   case TargetOpcode::G_FMINNUM:
1725   case TargetOpcode::G_FMINNUM_IEEE:
1726   case TargetOpcode::G_FMUL:
1727   case TargetOpcode::G_FNEARBYINT:
1728   case TargetOpcode::G_FNEG:
1729   case TargetOpcode::G_FPEXT:
1730   case TargetOpcode::G_FPOW:
1731   case TargetOpcode::G_FPTRUNC:
1732   case TargetOpcode::G_FREM:
1733   case TargetOpcode::G_FRINT:
1734   case TargetOpcode::G_FSIN:
1735   case TargetOpcode::G_FTAN:
1736   case TargetOpcode::G_FACOS:
1737   case TargetOpcode::G_FASIN:
1738   case TargetOpcode::G_FATAN:
1739   case TargetOpcode::G_FATAN2:
1740   case TargetOpcode::G_FCOSH:
1741   case TargetOpcode::G_FSINH:
1742   case TargetOpcode::G_FTANH:
1743   case TargetOpcode::G_FSQRT:
1744   case TargetOpcode::G_FSUB:
1745   case TargetOpcode::G_INTRINSIC_ROUND:
1746   case TargetOpcode::G_INTRINSIC_ROUNDEVEN:
1747   case TargetOpcode::G_INTRINSIC_TRUNC:
1748     return true;
1749   default:
1750     return false;
1751   }
1752 }
1753
1754 /// Shifts return poison if shiftwidth is larger than the bitwidth.
1755 static bool shiftAmountKnownInRange(Register ShiftAmount,
1756                                     const MachineRegisterInfo &MRI) {
1757   LLT Ty = MRI.getType(ShiftAmount);
1758
1759   if (Ty.isScalableVector())
1760     return false; // Can't tell, just return false to be safe
1761
1762   if (Ty.isScalar()) {
1763     std::optional<ValueAndVReg> Val =
1764         getIConstantVRegValWithLookThrough(ShiftAmount, MRI);
1765     if (!Val)
1766       return false;
1767     return Val->Value.ult(Ty.getScalarSizeInBits());
1768   }
1769
1770   GBuildVector *BV = getOpcodeDef<GBuildVector>(ShiftAmount, MRI);
1771   if (!BV)
1772     return false;
1773
1774   unsigned Sources = BV->getNumSources();
1775   for (unsigned I = 0; I < Sources; ++I) {
1776     std::optional<ValueAndVReg> Val =
1777         getIConstantVRegValWithLookThrough(BV->getSourceReg(I), MRI);
1778     if (!Val)
1779       return false;
1780     if (!Val->Value.ult(Ty.getScalarSizeInBits()))
1781       return false;
1782   }
1783
1784   return true;
1785 }
1786
1787 namespace {
1788 enum class UndefPoisonKind {
1789   PoisonOnly = (1 << 0),
1790   UndefOnly = (1 << 1),
1791   UndefOrPoison = PoisonOnly | UndefOnly,
1792 };
1793 }
1794
1795 static bool includesPoison(UndefPoisonKind Kind) {
1796   return (unsigned(Kind) & unsigned(UndefPoisonKind::PoisonOnly)) != 0;
1797 }
1798
1799 static bool includesUndef(UndefPoisonKind Kind) {
1800   return (unsigned(Kind) & unsigned(UndefPoisonKind::UndefOnly)) != 0;
1801 }
1802
1803 static bool canCreateUndefOrPoison(Register Reg, const MachineRegisterInfo &MRI,
1804                                    bool ConsiderFlagsAndMetadata,
1805                                    UndefPoisonKind Kind) {
1806   MachineInstr *RegDef = MRI.getVRegDef(Reg);
1807
1808   if (ConsiderFlagsAndMetadata && includesPoison(Kind))
1809     if (auto *GMI = dyn_cast<GenericMachineInstr>(RegDef))
1810       if (GMI->hasPoisonGeneratingFlags())
1811         return true;
1812
1813   // Check whether opcode is a poison/undef-generating operation.
1814   switch (RegDef->getOpcode()) {
1815   case TargetOpcode::G_BUILD_VECTOR:
1816   case TargetOpcode::G_CONSTANT_FOLD_BARRIER:
1817     return false;
1818   case TargetOpcode::G_SHL:
1819   case TargetOpcode::G_ASHR:
1820   case TargetOpcode::G_LSHR:
1821     return includesPoison(Kind) &&
1822            !shiftAmountKnownInRange(RegDef->getOperand(2).getReg(), MRI);
1823   case TargetOpcode::G_FPTOSI:
1824   case TargetOpcode::G_FPTOUI:
1825     // fptosi/ui yields poison if the resulting value does not fit in the
1826     // destination type.
1827     return true;
1828   case TargetOpcode::G_CTLZ:
1829   case TargetOpcode::G_CTTZ:
1830   case TargetOpcode::G_ABS:
1831   case TargetOpcode::G_CTPOP:
1832   case TargetOpcode::G_BSWAP:
1833   case TargetOpcode::G_BITREVERSE:
1834   case TargetOpcode::G_FSHL:
1835   case TargetOpcode::G_FSHR:
1836   case TargetOpcode::G_SMAX:
1837   case TargetOpcode::G_SMIN:
1838   case TargetOpcode::G_UMAX:
1839   case TargetOpcode::G_UMIN:
1840   case TargetOpcode::G_PTRMASK:
1841   case TargetOpcode::G_SADDO:
1842   case TargetOpcode::G_SSUBO:
1843   case TargetOpcode::G_UADDO:
1844   case TargetOpcode::G_USUBO:
1845   case TargetOpcode::G_SMULO:
1846   case TargetOpcode::G_UMULO:
1847   case TargetOpcode::G_SADDSAT:
1848   case TargetOpcode::G_UADDSAT:
1849   case TargetOpcode::G_SSUBSAT:
1850   case TargetOpcode::G_USUBSAT:
1851     return false;
1852   case TargetOpcode::G_SSHLSAT:
1853   case TargetOpcode::G_USHLSAT:
1854     return includesPoison(Kind) &&
1855            !shiftAmountKnownInRange(RegDef->getOperand(2).getReg(), MRI);
1856   case TargetOpcode::G_INSERT_VECTOR_ELT: {
1857     GInsertVectorElement *Insert = cast<GInsertVectorElement>(RegDef);
1858     if (includesPoison(Kind)) {
1859       std::optional<ValueAndVReg> Index =
1860           getIConstantVRegValWithLookThrough(Insert->getIndexReg(), MRI);
1861       if (!Index)
1862         return true;
1863       LLT VecTy = MRI.getType(Insert->getVectorReg());
1864       return Index->Value.uge(VecTy.getElementCount().getKnownMinValue());
1865     }
1866     return false;
1867   }
1868   case TargetOpcode::G_EXTRACT_VECTOR_ELT: {
1869     GExtractVectorElement *Extract = cast<GExtractVectorElement>(RegDef);
1870     if (includesPoison(Kind)) {
1871       std::optional<ValueAndVReg> Index =
1872           getIConstantVRegValWithLookThrough(Extract->getIndexReg(), MRI);
1873       if (!Index)
1874         return true;
1875       LLT VecTy = MRI.getType(Extract->getVectorReg());
1876       return Index->Value.uge(VecTy.getElementCount().getKnownMinValue());
1877     }
1878     return false;
1879   }
1880   case TargetOpcode::G_SHUFFLE_VECTOR: {
1881     GShuffleVector *Shuffle = cast<GShuffleVector>(RegDef);
1882     ArrayRef<int> Mask = Shuffle->getMask();
1883     return includesPoison(Kind) && is_contained(Mask, -1);
1884   }
1885   case TargetOpcode::G_FNEG:
1886   case TargetOpcode::G_PHI:
1887   case TargetOpcode::G_SELECT:
1888   case TargetOpcode::G_UREM:
1889   case TargetOpcode::G_SREM:
1890   case TargetOpcode::G_FREEZE:
1891   case TargetOpcode::G_ICMP:
1892   case TargetOpcode::G_FCMP:
1893   case TargetOpcode::G_FADD:
1894   case TargetOpcode::G_FSUB:
1895   case TargetOpcode::G_FMUL:
1896   case TargetOpcode::G_FDIV:
1897   case TargetOpcode::G_FREM:
1898   case TargetOpcode::G_PTR_ADD:
1899     return false;
1900   default:
1901     return !isa<GCastOp>(RegDef) && !isa<GBinOp>(RegDef);
1902   }
1903 }
1904
1905 static bool isGuaranteedNotToBeUndefOrPoison(Register Reg,
1906                                              const MachineRegisterInfo &MRI,
1907                                              unsigned Depth,
1908                                              UndefPoisonKind Kind) {
1909   if (Depth >= MaxAnalysisRecursionDepth)
1910     return false;
1911
1912   MachineInstr *RegDef = MRI.getVRegDef(Reg);
1913
1914   switch (RegDef->getOpcode()) {
1915   case TargetOpcode::G_FREEZE:
1916     return true;
1917   case TargetOpcode::G_IMPLICIT_DEF:
1918     return !includesUndef(Kind);
1919   case TargetOpcode::G_CONSTANT:
1920   case TargetOpcode::G_FCONSTANT:
1921     return true;
1922   case TargetOpcode::G_BUILD_VECTOR: {
1923     GBuildVector *BV = cast<GBuildVector>(RegDef);
1924     unsigned NumSources = BV->getNumSources();
1925     for (unsigned I = 0; I < NumSources; ++I)
1926       if (!::isGuaranteedNotToBeUndefOrPoison(BV->getSourceReg(I), MRI,
1927                                               Depth + 1, Kind))
1928         return false;
1929     return true;
1930   }
1931   case TargetOpcode::G_PHI: {
1932     GPhi *Phi = cast<GPhi>(RegDef);
1933     unsigned NumIncoming = Phi->getNumIncomingValues();
1934     for (unsigned I = 0; I < NumIncoming; ++I)
1935       if (!::isGuaranteedNotToBeUndefOrPoison(Phi->getIncomingValue(I), MRI,
1936                                               Depth + 1, Kind))
1937         return false;
1938     return true;
1939   }
1940   default: {
1941     auto MOCheck = [&](const MachineOperand &MO) {
1942       if (!MO.isReg())
1943         return true;
1944       return ::isGuaranteedNotToBeUndefOrPoison(MO.getReg(), MRI, Depth + 1,
1945                                                 Kind);
1946     };
1947     return !::canCreateUndefOrPoison(Reg, MRI,
1948                                      /*ConsiderFlagsAndMetadata=*/true, Kind) &&
1949            all_of(RegDef->uses(), MOCheck);
1950   }
1951   }
1952 }
1953
1954 bool llvm::canCreateUndefOrPoison(Register Reg, const MachineRegisterInfo &MRI,
1955                                   bool ConsiderFlagsAndMetadata) {
1956   return ::canCreateUndefOrPoison(Reg, MRI, ConsiderFlagsAndMetadata,
1957                                   UndefPoisonKind::UndefOrPoison);
1958 }
1959
1960 bool canCreatePoison(Register Reg, const MachineRegisterInfo &MRI,
1961                      bool ConsiderFlagsAndMetadata = true) {
1962   return ::canCreateUndefOrPoison(Reg, MRI, ConsiderFlagsAndMetadata,
1963                                   UndefPoisonKind::PoisonOnly);
1964 }
1965
1966 bool llvm::isGuaranteedNotToBeUndefOrPoison(Register Reg,
1967                                             const MachineRegisterInfo &MRI,
1968                                             unsigned Depth) {
1969   return ::isGuaranteedNotToBeUndefOrPoison(Reg, MRI, Depth,
1970                                             UndefPoisonKind::UndefOrPoison);
1971 }
1972
1973 bool llvm::isGuaranteedNotToBePoison(Register Reg,
1974                                      const MachineRegisterInfo &MRI,
1975                                      unsigned Depth) {
1976   return ::isGuaranteedNotToBeUndefOrPoison(Reg, MRI, Depth,
1977                                             UndefPoisonKind::PoisonOnly);
1978 }
1979
1980 bool llvm::isGuaranteedNotToBeUndef(Register Reg,
1981                                     const MachineRegisterInfo &MRI,
1982                                     unsigned Depth) {
1983   return ::isGuaranteedNotToBeUndefOrPoison(Reg, MRI, Depth,
1984                                             UndefPoisonKind::UndefOnly);
1985 }
1986
1987 Type *llvm::getTypeForLLT(LLT Ty, LLVMContext &C) {
1988   if (Ty.isVector())
1989     return VectorType::get(IntegerType::get(C, Ty.getScalarSizeInBits()),
1990                            Ty.getElementCount());
1991   return IntegerType::get(C, Ty.getSizeInBits());
1992 }
1993
1994 APInt llvm::GIConstant::getScalarValue() const {
1995   assert(Kind == GIConstantKind::Scalar && "Expected scalar constant");
1996
1997   return Value;
1998 }
1999
2000 std::optional<GIConstant>
2001 llvm::GIConstant::getConstant(Register Const, const MachineRegisterInfo &MRI) {
2002   MachineInstr *Constant = getDefIgnoringCopies(Const, MRI);
2003
2004   if (GSplatVector *Splat = dyn_cast<GSplatVector>(Constant)) {
2005     std::optional<ValueAndVReg> MayBeConstant =
2006         getIConstantVRegValWithLookThrough(Splat->getScalarReg(), MRI);
2007     if (!MayBeConstant)
2008       return std::nullopt;
2009     return GIConstant(MayBeConstant->Value, GIConstantKind::ScalableVector);
2010   }
2011
2012   if (GBuildVector *Build = dyn_cast<GBuildVector>(Constant)) {
2013     SmallVector<APInt> Values;
2014     unsigned NumSources = Build->getNumSources();
2015     for (unsigned I = 0; I < NumSources; ++I) {
2016       Register SrcReg = Build->getSourceReg(I);
2017       std::optional<ValueAndVReg> MayBeConstant =
2018           getIConstantVRegValWithLookThrough(SrcReg, MRI);
2019       if (!MayBeConstant)
2020         return std::nullopt;
2021       Values.push_back(MayBeConstant->Value);
2022     }
2023     return GIConstant(Values);
2024   }
2025
2026   std::optional<ValueAndVReg> MayBeConstant =
2027       getIConstantVRegValWithLookThrough(Const, MRI);
2028   if (!MayBeConstant)
2029     return std::nullopt;
2030
2031   return GIConstant(MayBeConstant->Value, GIConstantKind::Scalar);
2032 }
2033
2034 APFloat llvm::GFConstant::getScalarValue() const {
2035   assert(Kind == GFConstantKind::Scalar && "Expected scalar constant");
2036
2037   return Values[0];
2038 }
2039
2040 std::optional<GFConstant>
2041 llvm::GFConstant::getConstant(Register Const, const MachineRegisterInfo &MRI) {
2042   MachineInstr *Constant = getDefIgnoringCopies(Const, MRI);
2043
2044   if (GSplatVector *Splat = dyn_cast<GSplatVector>(Constant)) {
2045     std::optional<FPValueAndVReg> MayBeConstant =
2046         getFConstantVRegValWithLookThrough(Splat->getScalarReg(), MRI);
2047     if (!MayBeConstant)
2048       return std::nullopt;
2049     return GFConstant(MayBeConstant->Value, GFConstantKind::ScalableVector);
2050   }
2051
2052   if (GBuildVector *Build = dyn_cast<GBuildVector>(Constant)) {
2053     SmallVector<APFloat> Values;
2054     unsigned NumSources = Build->getNumSources();
2055     for (unsigned I = 0; I < NumSources; ++I) {
2056       Register SrcReg = Build->getSourceReg(I);
2057       std::optional<FPValueAndVReg> MayBeConstant =
2058           getFConstantVRegValWithLookThrough(SrcReg, MRI);
2059       if (!MayBeConstant)
2060         return std::nullopt;
2061       Values.push_back(MayBeConstant->Value);
2062     }
2063     return GFConstant(Values);
2064   }
2065
2066   std::optional<FPValueAndVReg> MayBeConstant =
2067       getFConstantVRegValWithLookThrough(Const, MRI);
2068   if (!MayBeConstant)
2069     return std::nullopt;
2070
2071   return GFConstant(MayBeConstant->Value, GFConstantKind::Scalar);
2072 }