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/CodeGen/CodeGenCommonISel.h"
  16 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
  17 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
  18 #include "llvm/CodeGen/GlobalISel/GenericMachineInstrs.h"
  19 #include "llvm/CodeGen/GlobalISel/LostDebugLocObserver.h"
  20 #include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
  21 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
  22 #include "llvm/CodeGen/MachineInstr.h"
  23 #include "llvm/CodeGen/MachineInstrBuilder.h"
  24 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
  25 #include "llvm/CodeGen/MachineRegisterInfo.h"
  26 #include "llvm/CodeGen/MachineSizeOpts.h"
  27 #include "llvm/CodeGen/RegisterBankInfo.h"
  28 #include "llvm/CodeGen/StackProtector.h"
  29 #include "llvm/CodeGen/TargetInstrInfo.h"
  30 #include "llvm/CodeGen/TargetLowering.h"
  31 #include "llvm/CodeGen/TargetPassConfig.h"
  32 #include "llvm/CodeGen/TargetRegisterInfo.h"
  33 #include "llvm/IR/Constants.h"
  34 #include "llvm/Target/TargetMachine.h"
  35 #include "llvm/Transforms/Utils/SizeOpts.h"
  36 #include <numeric>
  37 #include <optional>
  38
  39 #define DEBUG_TYPE "globalisel-utils"
  40
  41 using namespace llvm;
  42 using namespace MIPatternMatch;
  43
  44 Register llvm::constrainRegToClass(MachineRegisterInfo &MRI,
  45                                    const TargetInstrInfo &TII,
  46                                    const RegisterBankInfo &RBI, Register Reg,
  47                                    const TargetRegisterClass &RegClass) {
  48   if (!RBI.constrainGenericRegister(Reg, RegClass, MRI))
  49     return MRI.createVirtualRegister(&RegClass);
  50
  51   return Reg;
  52 }
  53
  54 Register llvm::constrainOperandRegClass(
  55     const MachineFunction &MF, const TargetRegisterInfo &TRI,
  56     MachineRegisterInfo &MRI, const TargetInstrInfo &TII,
  57     const RegisterBankInfo &RBI, MachineInstr &InsertPt,
  58     const TargetRegisterClass &RegClass, MachineOperand &RegMO) {
  59   Register Reg = RegMO.getReg();
  60   // Assume physical registers are properly constrained.
  61   assert(Reg.isVirtual() && "PhysReg not implemented");
  62
  63   // Save the old register class to check whether
  64   // the change notifications will be required.
  65   // TODO: A better approach would be to pass
  66   // the observers to constrainRegToClass().
  67   auto *OldRegClass = MRI.getRegClassOrNull(Reg);
  68   Register ConstrainedReg = constrainRegToClass(MRI, TII, RBI, Reg, RegClass);
  69   // If we created a new virtual register because the class is not compatible
  70   // then create a copy between the new and the old register.
  71   if (ConstrainedReg != Reg) {
  72     MachineBasicBlock::iterator InsertIt(&InsertPt);
  73     MachineBasicBlock &MBB = *InsertPt.getParent();
  74     // FIXME: The copy needs to have the classes constrained for its operands.
  75     // Use operand's regbank to get the class for old register (Reg).
  76     if (RegMO.isUse()) {
  77       BuildMI(MBB, InsertIt, InsertPt.getDebugLoc(),
  78               TII.get(TargetOpcode::COPY), ConstrainedReg)
  79           .addReg(Reg);
  80     } else {
  81       assert(RegMO.isDef() && "Must be a definition");
  82       BuildMI(MBB, std::next(InsertIt), InsertPt.getDebugLoc(),
  83               TII.get(TargetOpcode::COPY), Reg)
  84           .addReg(ConstrainedReg);
  85     }
  86     if (GISelChangeObserver *Observer = MF.getObserver()) {
  87       Observer->changingInstr(*RegMO.getParent());
  88     }
  89     RegMO.setReg(ConstrainedReg);
  90     if (GISelChangeObserver *Observer = MF.getObserver()) {
  91       Observer->changedInstr(*RegMO.getParent());
  92     }
  93   } else if (OldRegClass != MRI.getRegClassOrNull(Reg)) {
  94     if (GISelChangeObserver *Observer = MF.getObserver()) {
  95       if (!RegMO.isDef()) {
  96         MachineInstr *RegDef = MRI.getVRegDef(Reg);
  97         Observer->changedInstr(*RegDef);
  98       }
  99       Observer->changingAllUsesOfReg(MRI, Reg);
 100       Observer->finishedChangingAllUsesOfReg();
 101     }
 102   }
 103   return ConstrainedReg;
 104 }
 105
 106 Register llvm::constrainOperandRegClass(
 107     const MachineFunction &MF, const TargetRegisterInfo &TRI,
 108     MachineRegisterInfo &MRI, const TargetInstrInfo &TII,
 109     const RegisterBankInfo &RBI, MachineInstr &InsertPt, const MCInstrDesc &II,
 110     MachineOperand &RegMO, unsigned OpIdx) {
 111   Register Reg = RegMO.getReg();
 112   // Assume physical registers are properly constrained.
 113   assert(Reg.isVirtual() && "PhysReg not implemented");
 114
 115   const TargetRegisterClass *OpRC = TII.getRegClass(II, OpIdx, &TRI, MF);
 116   // Some of the target independent instructions, like COPY, may not impose any
 117   // register class constraints on some of their operands: If it's a use, we can
 118   // skip constraining as the instruction defining the register would constrain
 119   // it.
 120
 121   if (OpRC) {
 122     // Obtain the RC from incoming regbank if it is a proper sub-class. Operands
 123     // can have multiple regbanks for a superclass that combine different
 124     // register types (E.g., AMDGPU's VGPR and AGPR). The regbank ambiguity
 125     // resolved by targets during regbankselect should not be overridden.
 126     if (const auto *SubRC = TRI.getCommonSubClass(
 127             OpRC, TRI.getConstrainedRegClassForOperand(RegMO, MRI)))
 128       OpRC = SubRC;
 129
 130     OpRC = TRI.getAllocatableClass(OpRC);
 131   }
 132
 133   if (!OpRC) {
 134     assert((!isTargetSpecificOpcode(II.getOpcode()) || RegMO.isUse()) &&
 135            "Register class constraint is required unless either the "
 136            "instruction is target independent or the operand is a use");
 137     // FIXME: Just bailing out like this here could be not enough, unless we
 138     // expect the users of this function to do the right thing for PHIs and
 139     // COPY:
 140     //   v1 = COPY v0
 141     //   v2 = COPY v1
 142     // v1 here may end up not being constrained at all. Please notice that to
 143     // reproduce the issue we likely need a destination pattern of a selection
 144     // rule producing such extra copies, not just an input GMIR with them as
 145     // every existing target using selectImpl handles copies before calling it
 146     // and they never reach this function.
 147     return Reg;
 148   }
 149   return constrainOperandRegClass(MF, TRI, MRI, TII, RBI, InsertPt, *OpRC,
 150                                   RegMO);
 151 }
 152
 153 bool llvm::constrainSelectedInstRegOperands(MachineInstr &I,
 154                                             const TargetInstrInfo &TII,
 155                                             const TargetRegisterInfo &TRI,
 156                                             const RegisterBankInfo &RBI) {
 157   assert(!isPreISelGenericOpcode(I.getOpcode()) &&
 158          "A selected instruction is expected");
 159   MachineBasicBlock &MBB = *I.getParent();
 160   MachineFunction &MF = *MBB.getParent();
 161   MachineRegisterInfo &MRI = MF.getRegInfo();
 162
 163   for (unsigned OpI = 0, OpE = I.getNumExplicitOperands(); OpI != OpE; ++OpI) {
 164     MachineOperand &MO = I.getOperand(OpI);
 165
 166     // There's nothing to be done on non-register operands.
 167     if (!MO.isReg())
 168       continue;
 169
 170     LLVM_DEBUG(dbgs() << "Converting operand: " << MO << '\n');
 171     assert(MO.isReg() && "Unsupported non-reg operand");
 172
 173     Register Reg = MO.getReg();
 174     // Physical registers don't need to be constrained.
 175     if (Reg.isPhysical())
 176       continue;
 177
 178     // Register operands with a value of 0 (e.g. predicate operands) don't need
 179     // to be constrained.
 180     if (Reg == 0)
 181       continue;
 182
 183     // If the operand is a vreg, we should constrain its regclass, and only
 184     // insert COPYs if that's impossible.
 185     // constrainOperandRegClass does that for us.
 186     constrainOperandRegClass(MF, TRI, MRI, TII, RBI, I, I.getDesc(), MO, OpI);
 187
 188     // Tie uses to defs as indicated in MCInstrDesc if this hasn't already been
 189     // done.
 190     if (MO.isUse()) {
 191       int DefIdx = I.getDesc().getOperandConstraint(OpI, MCOI::TIED_TO);
 192       if (DefIdx != -1 && !I.isRegTiedToUseOperand(DefIdx))
 193         I.tieOperands(DefIdx, OpI);
 194     }
 195   }
 196   return true;
 197 }
 198
 199 bool llvm::canReplaceReg(Register DstReg, Register SrcReg,
 200                          MachineRegisterInfo &MRI) {
 201   // Give up if either DstReg or SrcReg  is a physical register.
 202   if (DstReg.isPhysical() || SrcReg.isPhysical())
 203     return false;
 204   // Give up if the types don't match.
 205   if (MRI.getType(DstReg) != MRI.getType(SrcReg))
 206     return false;
 207   // Replace if either DstReg has no constraints or the register
 208   // constraints match.
 209   const auto &DstRBC = MRI.getRegClassOrRegBank(DstReg);
 210   if (!DstRBC || DstRBC == MRI.getRegClassOrRegBank(SrcReg))
 211     return true;
 212
 213   // Otherwise match if the Src is already a regclass that is covered by the Dst
 214   // RegBank.
 215   return DstRBC.is<const RegisterBank *>() && MRI.getRegClassOrNull(SrcReg) &&
 216          DstRBC.get<const RegisterBank *>()->covers(
 217              *MRI.getRegClassOrNull(SrcReg));
 218 }
 219
 220 bool llvm::isTriviallyDead(const MachineInstr &MI,
 221                            const MachineRegisterInfo &MRI) {
 222   // FIXME: This logical is mostly duplicated with
 223   // DeadMachineInstructionElim::isDead. Why is LOCAL_ESCAPE not considered in
 224   // MachineInstr::isLabel?
 225
 226   // Don't delete frame allocation labels.
 227   if (MI.getOpcode() == TargetOpcode::LOCAL_ESCAPE)
 228     return false;
 229   // LIFETIME markers should be preserved even if they seem dead.
 230   if (MI.getOpcode() == TargetOpcode::LIFETIME_START ||
 231       MI.getOpcode() == TargetOpcode::LIFETIME_END)
 232     return false;
 233
 234   // If we can move an instruction, we can remove it.  Otherwise, it has
 235   // a side-effect of some sort.
 236   bool SawStore = false;
 237   if (!MI.isSafeToMove(/*AA=*/nullptr, SawStore) && !MI.isPHI())
 238     return false;
 239
 240   // Instructions without side-effects are dead iff they only define dead vregs.
 241   for (const auto &MO : MI.all_defs()) {
 242     Register Reg = MO.getReg();
 243     if (Reg.isPhysical() || !MRI.use_nodbg_empty(Reg))
 244       return false;
 245   }
 246   return true;
 247 }
 248
 249 static void reportGISelDiagnostic(DiagnosticSeverity Severity,
 250                                   MachineFunction &MF,
 251                                   const TargetPassConfig &TPC,
 252                                   MachineOptimizationRemarkEmitter &MORE,
 253                                   MachineOptimizationRemarkMissed &R) {
 254   bool IsFatal = Severity == DS_Error &&
 255                  TPC.isGlobalISelAbortEnabled();
 256   // Print the function name explicitly if we don't have a debug location (which
 257   // makes the diagnostic less useful) or if we're going to emit a raw error.
 258   if (!R.getLocation().isValid() || IsFatal)
 259     R << (" (in function: " + MF.getName() + ")").str();
 260
 261   if (IsFatal)
 262     report_fatal_error(Twine(R.getMsg()));
 263   else
 264     MORE.emit(R);
 265 }
 266
 267 void llvm::reportGISelWarning(MachineFunction &MF, const TargetPassConfig &TPC,
 268                               MachineOptimizationRemarkEmitter &MORE,
 269                               MachineOptimizationRemarkMissed &R) {
 270   reportGISelDiagnostic(DS_Warning, MF, TPC, MORE, R);
 271 }
 272
 273 void llvm::reportGISelFailure(MachineFunction &MF, const TargetPassConfig &TPC,
 274                               MachineOptimizationRemarkEmitter &MORE,
 275                               MachineOptimizationRemarkMissed &R) {
 276   MF.getProperties().set(MachineFunctionProperties::Property::FailedISel);
 277   reportGISelDiagnostic(DS_Error, MF, TPC, MORE, R);
 278 }
 279
 280 void llvm::reportGISelFailure(MachineFunction &MF, const TargetPassConfig &TPC,
 281                               MachineOptimizationRemarkEmitter &MORE,
 282                               const char *PassName, StringRef Msg,
 283                               const MachineInstr &MI) {
 284   MachineOptimizationRemarkMissed R(PassName, "GISelFailure: ",
 285                                     MI.getDebugLoc(), MI.getParent());
 286   R << Msg;
 287   // Printing MI is expensive;  only do it if expensive remarks are enabled.
 288   if (TPC.isGlobalISelAbortEnabled() || MORE.allowExtraAnalysis(PassName))
 289     R << ": " << ore::MNV("Inst", MI);
 290   reportGISelFailure(MF, TPC, MORE, R);
 291 }
 292
 293 std::optional<APInt> llvm::getIConstantVRegVal(Register VReg,
 294                                                const MachineRegisterInfo &MRI) {
 295   std::optional<ValueAndVReg> ValAndVReg = getIConstantVRegValWithLookThrough(
 296       VReg, MRI, /*LookThroughInstrs*/ false);
 297   assert((!ValAndVReg || ValAndVReg->VReg == VReg) &&
 298          "Value found while looking through instrs");
 299   if (!ValAndVReg)
 300     return std::nullopt;
 301   return ValAndVReg->Value;
 302 }
 303
 304 std::optional<int64_t>
 305 llvm::getIConstantVRegSExtVal(Register VReg, const MachineRegisterInfo &MRI) {
 306   std::optional<APInt> Val = getIConstantVRegVal(VReg, MRI);
 307   if (Val && Val->getBitWidth() <= 64)
 308     return Val->getSExtValue();
 309   return std::nullopt;
 310 }
 311
 312 namespace {
 313
 314 typedef std::function<bool(const MachineInstr *)> IsOpcodeFn;
 315 typedef std::function<std::optional<APInt>(const MachineInstr *MI)> GetAPCstFn;
 316
 317 std::optional<ValueAndVReg> getConstantVRegValWithLookThrough(
 318     Register VReg, const MachineRegisterInfo &MRI, IsOpcodeFn IsConstantOpcode,
 319     GetAPCstFn getAPCstValue, bool LookThroughInstrs = true,
 320     bool LookThroughAnyExt = false) {
 321   SmallVector<std::pair<unsigned, unsigned>, 4> SeenOpcodes;
 322   MachineInstr *MI;
 323
 324   while ((MI = MRI.getVRegDef(VReg)) && !IsConstantOpcode(MI) &&
 325          LookThroughInstrs) {
 326     switch (MI->getOpcode()) {
 327     case TargetOpcode::G_ANYEXT:
 328       if (!LookThroughAnyExt)
 329         return std::nullopt;
 330       [[fallthrough]];
 331     case TargetOpcode::G_TRUNC:
 332     case TargetOpcode::G_SEXT:
 333     case TargetOpcode::G_ZEXT:
 334       SeenOpcodes.push_back(std::make_pair(
 335           MI->getOpcode(),
 336           MRI.getType(MI->getOperand(0).getReg()).getSizeInBits()));
 337       VReg = MI->getOperand(1).getReg();
 338       break;
 339     case TargetOpcode::COPY:
 340       VReg = MI->getOperand(1).getReg();
 341       if (VReg.isPhysical())
 342         return std::nullopt;
 343       break;
 344     case TargetOpcode::G_INTTOPTR:
 345       VReg = MI->getOperand(1).getReg();
 346       break;
 347     default:
 348       return std::nullopt;
 349     }
 350   }
 351   if (!MI || !IsConstantOpcode(MI))
 352     return std::nullopt;
 353
 354   std::optional<APInt> MaybeVal = getAPCstValue(MI);
 355   if (!MaybeVal)
 356     return std::nullopt;
 357   APInt &Val = *MaybeVal;
 358   while (!SeenOpcodes.empty()) {
 359     std::pair<unsigned, unsigned> OpcodeAndSize = SeenOpcodes.pop_back_val();
 360     switch (OpcodeAndSize.first) {
 361     case TargetOpcode::G_TRUNC:
 362       Val = Val.trunc(OpcodeAndSize.second);
 363       break;
 364     case TargetOpcode::G_ANYEXT:
 365     case TargetOpcode::G_SEXT:
 366       Val = Val.sext(OpcodeAndSize.second);
 367       break;
 368     case TargetOpcode::G_ZEXT:
 369       Val = Val.zext(OpcodeAndSize.second);
 370       break;
 371     }
 372   }
 373
 374   return ValueAndVReg{Val, VReg};
 375 }
 376
 377 bool isIConstant(const MachineInstr *MI) {
 378   if (!MI)
 379     return false;
 380   return MI->getOpcode() == TargetOpcode::G_CONSTANT;
 381 }
 382
 383 bool isFConstant(const MachineInstr *MI) {
 384   if (!MI)
 385     return false;
 386   return MI->getOpcode() == TargetOpcode::G_FCONSTANT;
 387 }
 388
 389 bool isAnyConstant(const MachineInstr *MI) {
 390   if (!MI)
 391     return false;
 392   unsigned Opc = MI->getOpcode();
 393   return Opc == TargetOpcode::G_CONSTANT || Opc == TargetOpcode::G_FCONSTANT;
 394 }
 395
 396 std::optional<APInt> getCImmAsAPInt(const MachineInstr *MI) {
 397   const MachineOperand &CstVal = MI->getOperand(1);
 398   if (CstVal.isCImm())
 399     return CstVal.getCImm()->getValue();
 400   return std::nullopt;
 401 }
 402
 403 std::optional<APInt> getCImmOrFPImmAsAPInt(const MachineInstr *MI) {
 404   const MachineOperand &CstVal = MI->getOperand(1);
 405   if (CstVal.isCImm())
 406     return CstVal.getCImm()->getValue();
 407   if (CstVal.isFPImm())
 408     return CstVal.getFPImm()->getValueAPF().bitcastToAPInt();
 409   return std::nullopt;
 410 }
 411
 412 } // end anonymous namespace
 413
 414 std::optional<ValueAndVReg> llvm::getIConstantVRegValWithLookThrough(
 415     Register VReg, const MachineRegisterInfo &MRI, bool LookThroughInstrs) {
 416   return getConstantVRegValWithLookThrough(VReg, MRI, isIConstant,
 417                                            getCImmAsAPInt, LookThroughInstrs);
 418 }
 419
 420 std::optional<ValueAndVReg> llvm::getAnyConstantVRegValWithLookThrough(
 421     Register VReg, const MachineRegisterInfo &MRI, bool LookThroughInstrs,
 422     bool LookThroughAnyExt) {
 423   return getConstantVRegValWithLookThrough(
 424       VReg, MRI, isAnyConstant, getCImmOrFPImmAsAPInt, LookThroughInstrs,
 425       LookThroughAnyExt);
 426 }
 427
 428 std::optional<FPValueAndVReg> llvm::getFConstantVRegValWithLookThrough(
 429     Register VReg, const MachineRegisterInfo &MRI, bool LookThroughInstrs) {
 430   auto Reg = getConstantVRegValWithLookThrough(
 431       VReg, MRI, isFConstant, getCImmOrFPImmAsAPInt, LookThroughInstrs);
 432   if (!Reg)
 433     return std::nullopt;
 434   return FPValueAndVReg{getConstantFPVRegVal(Reg->VReg, MRI)->getValueAPF(),
 435                         Reg->VReg};
 436 }
 437
 438 const ConstantFP *
 439 llvm::getConstantFPVRegVal(Register VReg, const MachineRegisterInfo &MRI) {
 440   MachineInstr *MI = MRI.getVRegDef(VReg);
 441   if (TargetOpcode::G_FCONSTANT != MI->getOpcode())
 442     return nullptr;
 443   return MI->getOperand(1).getFPImm();
 444 }
 445
 446 std::optional<DefinitionAndSourceRegister>
 447 llvm::getDefSrcRegIgnoringCopies(Register Reg, const MachineRegisterInfo &MRI) {
 448   Register DefSrcReg = Reg;
 449   auto *DefMI = MRI.getVRegDef(Reg);
 450   auto DstTy = MRI.getType(DefMI->getOperand(0).getReg());
 451   if (!DstTy.isValid())
 452     return std::nullopt;
 453   unsigned Opc = DefMI->getOpcode();
 454   while (Opc == TargetOpcode::COPY || isPreISelGenericOptimizationHint(Opc)) {
 455     Register SrcReg = DefMI->getOperand(1).getReg();
 456     auto SrcTy = MRI.getType(SrcReg);
 457     if (!SrcTy.isValid())
 458       break;
 459     DefMI = MRI.getVRegDef(SrcReg);
 460     DefSrcReg = SrcReg;
 461     Opc = DefMI->getOpcode();
 462   }
 463   return DefinitionAndSourceRegister{DefMI, DefSrcReg};
 464 }
 465
 466 MachineInstr *llvm::getDefIgnoringCopies(Register Reg,
 467                                          const MachineRegisterInfo &MRI) {
 468   std::optional<DefinitionAndSourceRegister> DefSrcReg =
 469       getDefSrcRegIgnoringCopies(Reg, MRI);
 470   return DefSrcReg ? DefSrcReg->MI : nullptr;
 471 }
 472
 473 Register llvm::getSrcRegIgnoringCopies(Register Reg,
 474                                        const MachineRegisterInfo &MRI) {
 475   std::optional<DefinitionAndSourceRegister> DefSrcReg =
 476       getDefSrcRegIgnoringCopies(Reg, MRI);
 477   return DefSrcReg ? DefSrcReg->Reg : Register();
 478 }
 479
 480 void llvm::extractParts(Register Reg, LLT Ty, int NumParts,
 481                         SmallVectorImpl<Register> &VRegs,
 482                         MachineIRBuilder &MIRBuilder,
 483                         MachineRegisterInfo &MRI) {
 484   for (int i = 0; i < NumParts; ++i)
 485     VRegs.push_back(MRI.createGenericVirtualRegister(Ty));
 486   MIRBuilder.buildUnmerge(VRegs, Reg);
 487 }
 488
 489 bool llvm::extractParts(Register Reg, LLT RegTy, LLT MainTy, LLT &LeftoverTy,
 490                         SmallVectorImpl<Register> &VRegs,
 491                         SmallVectorImpl<Register> &LeftoverRegs,
 492                         MachineIRBuilder &MIRBuilder,
 493                         MachineRegisterInfo &MRI) {
 494   assert(!LeftoverTy.isValid() && "this is an out argument");
 495
 496   unsigned RegSize = RegTy.getSizeInBits();
 497   unsigned MainSize = MainTy.getSizeInBits();
 498   unsigned NumParts = RegSize / MainSize;
 499   unsigned LeftoverSize = RegSize - NumParts * MainSize;
 500
 501   // Use an unmerge when possible.
 502   if (LeftoverSize == 0) {
 503     for (unsigned I = 0; I < NumParts; ++I)
 504       VRegs.push_back(MRI.createGenericVirtualRegister(MainTy));
 505     MIRBuilder.buildUnmerge(VRegs, Reg);
 506     return true;
 507   }
 508
 509   // Try to use unmerge for irregular vector split where possible
 510   // For example when splitting a <6 x i32> into <4 x i32> with <2 x i32>
 511   // leftover, it becomes:
 512   //  <2 x i32> %2, <2 x i32>%3, <2 x i32> %4 = G_UNMERGE_VALUE <6 x i32> %1
 513   //  <4 x i32> %5 = G_CONCAT_VECTOR <2 x i32> %2, <2 x i32> %3
 514   if (RegTy.isVector() && MainTy.isVector()) {
 515     unsigned RegNumElts = RegTy.getNumElements();
 516     unsigned MainNumElts = MainTy.getNumElements();
 517     unsigned LeftoverNumElts = RegNumElts % MainNumElts;
 518     // If can unmerge to LeftoverTy, do it
 519     if (MainNumElts % LeftoverNumElts == 0 &&
 520         RegNumElts % LeftoverNumElts == 0 &&
 521         RegTy.getScalarSizeInBits() == MainTy.getScalarSizeInBits() &&
 522         LeftoverNumElts > 1) {
 523       LeftoverTy =
 524           LLT::fixed_vector(LeftoverNumElts, RegTy.getScalarSizeInBits());
 525
 526       // Unmerge the SrcReg to LeftoverTy vectors
 527       SmallVector<Register, 4> UnmergeValues;
 528       extractParts(Reg, LeftoverTy, RegNumElts / LeftoverNumElts, UnmergeValues,
 529                    MIRBuilder, MRI);
 530
 531       // Find how many LeftoverTy makes one MainTy
 532       unsigned LeftoverPerMain = MainNumElts / LeftoverNumElts;
 533       unsigned NumOfLeftoverVal =
 534           ((RegNumElts % MainNumElts) / LeftoverNumElts);
 535
 536       // Create as many MainTy as possible using unmerged value
 537       SmallVector<Register, 4> MergeValues;
 538       for (unsigned I = 0; I < UnmergeValues.size() - NumOfLeftoverVal; I++) {
 539         MergeValues.push_back(UnmergeValues[I]);
 540         if (MergeValues.size() == LeftoverPerMain) {
 541           VRegs.push_back(
 542               MIRBuilder.buildMergeLikeInstr(MainTy, MergeValues).getReg(0));
 543           MergeValues.clear();
 544         }
 545       }
 546       // Populate LeftoverRegs with the leftovers
 547       for (unsigned I = UnmergeValues.size() - NumOfLeftoverVal;
 548            I < UnmergeValues.size(); I++) {
 549         LeftoverRegs.push_back(UnmergeValues[I]);
 550       }
 551       return true;
 552     }
 553   }
 554   // Perform irregular split. Leftover is last element of RegPieces.
 555   if (MainTy.isVector()) {
 556     SmallVector<Register, 8> RegPieces;
 557     extractVectorParts(Reg, MainTy.getNumElements(), RegPieces, MIRBuilder,
 558                        MRI);
 559     for (unsigned i = 0; i < RegPieces.size() - 1; ++i)
 560       VRegs.push_back(RegPieces[i]);
 561     LeftoverRegs.push_back(RegPieces[RegPieces.size() - 1]);
 562     LeftoverTy = MRI.getType(LeftoverRegs[0]);
 563     return true;
 564   }
 565
 566   LeftoverTy = LLT::scalar(LeftoverSize);
 567   // For irregular sizes, extract the individual parts.
 568   for (unsigned I = 0; I != NumParts; ++I) {
 569     Register NewReg = MRI.createGenericVirtualRegister(MainTy);
 570     VRegs.push_back(NewReg);
 571     MIRBuilder.buildExtract(NewReg, Reg, MainSize * I);
 572   }
 573
 574   for (unsigned Offset = MainSize * NumParts; Offset < RegSize;
 575        Offset += LeftoverSize) {
 576     Register NewReg = MRI.createGenericVirtualRegister(LeftoverTy);
 577     LeftoverRegs.push_back(NewReg);
 578     MIRBuilder.buildExtract(NewReg, Reg, Offset);
 579   }
 580
 581   return true;
 582 }
 583
 584 void llvm::extractVectorParts(Register Reg, unsigned NumElts,
 585                               SmallVectorImpl<Register> &VRegs,
 586                               MachineIRBuilder &MIRBuilder,
 587                               MachineRegisterInfo &MRI) {
 588   LLT RegTy = MRI.getType(Reg);
 589   assert(RegTy.isVector() && "Expected a vector type");
 590
 591   LLT EltTy = RegTy.getElementType();
 592   LLT NarrowTy = (NumElts == 1) ? EltTy : LLT::fixed_vector(NumElts, EltTy);
 593   unsigned RegNumElts = RegTy.getNumElements();
 594   unsigned LeftoverNumElts = RegNumElts % NumElts;
 595   unsigned NumNarrowTyPieces = RegNumElts / NumElts;
 596
 597   // Perfect split without leftover
 598   if (LeftoverNumElts == 0)
 599     return extractParts(Reg, NarrowTy, NumNarrowTyPieces, VRegs, MIRBuilder,
 600                         MRI);
 601
 602   // Irregular split. Provide direct access to all elements for artifact
 603   // combiner using unmerge to elements. Then build vectors with NumElts
 604   // elements. Remaining element(s) will be (used to build vector) Leftover.
 605   SmallVector<Register, 8> Elts;
 606   extractParts(Reg, EltTy, RegNumElts, Elts, MIRBuilder, MRI);
 607
 608   unsigned Offset = 0;
 609   // Requested sub-vectors of NarrowTy.
 610   for (unsigned i = 0; i < NumNarrowTyPieces; ++i, Offset += NumElts) {
 611     ArrayRef<Register> Pieces(&Elts[Offset], NumElts);
 612     VRegs.push_back(MIRBuilder.buildMergeLikeInstr(NarrowTy, Pieces).getReg(0));
 613   }
 614
 615   // Leftover element(s).
 616   if (LeftoverNumElts == 1) {
 617     VRegs.push_back(Elts[Offset]);
 618   } else {
 619     LLT LeftoverTy = LLT::fixed_vector(LeftoverNumElts, EltTy);
 620     ArrayRef<Register> Pieces(&Elts[Offset], LeftoverNumElts);
 621     VRegs.push_back(
 622         MIRBuilder.buildMergeLikeInstr(LeftoverTy, Pieces).getReg(0));
 623   }
 624 }
 625
 626 MachineInstr *llvm::getOpcodeDef(unsigned Opcode, Register Reg,
 627                                  const MachineRegisterInfo &MRI) {
 628   MachineInstr *DefMI = getDefIgnoringCopies(Reg, MRI);
 629   return DefMI && DefMI->getOpcode() == Opcode ? DefMI : nullptr;
 630 }
 631
 632 APFloat llvm::getAPFloatFromSize(double Val, unsigned Size) {
 633   if (Size == 32)
 634     return APFloat(float(Val));
 635   if (Size == 64)
 636     return APFloat(Val);
 637   if (Size != 16)
 638     llvm_unreachable("Unsupported FPConstant size");
 639   bool Ignored;
 640   APFloat APF(Val);
 641   APF.convert(APFloat::IEEEhalf(), APFloat::rmNearestTiesToEven, &Ignored);
 642   return APF;
 643 }
 644
 645 std::optional<APInt> llvm::ConstantFoldBinOp(unsigned Opcode,
 646                                              const Register Op1,
 647                                              const Register Op2,
 648                                              const MachineRegisterInfo &MRI) {
 649   auto MaybeOp2Cst = getAnyConstantVRegValWithLookThrough(Op2, MRI, false);
 650   if (!MaybeOp2Cst)
 651     return std::nullopt;
 652
 653   auto MaybeOp1Cst = getAnyConstantVRegValWithLookThrough(Op1, MRI, false);
 654   if (!MaybeOp1Cst)
 655     return std::nullopt;
 656
 657   const APInt &C1 = MaybeOp1Cst->Value;
 658   const APInt &C2 = MaybeOp2Cst->Value;
 659   switch (Opcode) {
 660   default:
 661     break;
 662   case TargetOpcode::G_ADD:
 663   case TargetOpcode::G_PTR_ADD:
 664     return C1 + C2;
 665   case TargetOpcode::G_AND:
 666     return C1 & C2;
 667   case TargetOpcode::G_ASHR:
 668     return C1.ashr(C2);
 669   case TargetOpcode::G_LSHR:
 670     return C1.lshr(C2);
 671   case TargetOpcode::G_MUL:
 672     return C1 * C2;
 673   case TargetOpcode::G_OR:
 674     return C1 | C2;
 675   case TargetOpcode::G_SHL:
 676     return C1 << C2;
 677   case TargetOpcode::G_SUB:
 678     return C1 - C2;
 679   case TargetOpcode::G_XOR:
 680     return C1 ^ C2;
 681   case TargetOpcode::G_UDIV:
 682     if (!C2.getBoolValue())
 683       break;
 684     return C1.udiv(C2);
 685   case TargetOpcode::G_SDIV:
 686     if (!C2.getBoolValue())
 687       break;
 688     return C1.sdiv(C2);
 689   case TargetOpcode::G_UREM:
 690     if (!C2.getBoolValue())
 691       break;
 692     return C1.urem(C2);
 693   case TargetOpcode::G_SREM:
 694     if (!C2.getBoolValue())
 695       break;
 696     return C1.srem(C2);
 697   case TargetOpcode::G_SMIN:
 698     return APIntOps::smin(C1, C2);
 699   case TargetOpcode::G_SMAX:
 700     return APIntOps::smax(C1, C2);
 701   case TargetOpcode::G_UMIN:
 702     return APIntOps::umin(C1, C2);
 703   case TargetOpcode::G_UMAX:
 704     return APIntOps::umax(C1, C2);
 705   }
 706
 707   return std::nullopt;
 708 }
 709
 710 std::optional<APFloat>
 711 llvm::ConstantFoldFPBinOp(unsigned Opcode, const Register Op1,
 712                           const Register Op2, const MachineRegisterInfo &MRI) {
 713   const ConstantFP *Op2Cst = getConstantFPVRegVal(Op2, MRI);
 714   if (!Op2Cst)
 715     return std::nullopt;
 716
 717   const ConstantFP *Op1Cst = getConstantFPVRegVal(Op1, MRI);
 718   if (!Op1Cst)
 719     return std::nullopt;
 720
 721   APFloat C1 = Op1Cst->getValueAPF();
 722   const APFloat &C2 = Op2Cst->getValueAPF();
 723   switch (Opcode) {
 724   case TargetOpcode::G_FADD:
 725     C1.add(C2, APFloat::rmNearestTiesToEven);
 726     return C1;
 727   case TargetOpcode::G_FSUB:
 728     C1.subtract(C2, APFloat::rmNearestTiesToEven);
 729     return C1;
 730   case TargetOpcode::G_FMUL:
 731     C1.multiply(C2, APFloat::rmNearestTiesToEven);
 732     return C1;
 733   case TargetOpcode::G_FDIV:
 734     C1.divide(C2, APFloat::rmNearestTiesToEven);
 735     return C1;
 736   case TargetOpcode::G_FREM:
 737     C1.mod(C2);
 738     return C1;
 739   case TargetOpcode::G_FCOPYSIGN:
 740     C1.copySign(C2);
 741     return C1;
 742   case TargetOpcode::G_FMINNUM:
 743     return minnum(C1, C2);
 744   case TargetOpcode::G_FMAXNUM:
 745     return maxnum(C1, C2);
 746   case TargetOpcode::G_FMINIMUM:
 747     return minimum(C1, C2);
 748   case TargetOpcode::G_FMAXIMUM:
 749     return maximum(C1, C2);
 750   case TargetOpcode::G_FMINNUM_IEEE:
 751   case TargetOpcode::G_FMAXNUM_IEEE:
 752     // FIXME: These operations were unfortunately named. fminnum/fmaxnum do not
 753     // follow the IEEE behavior for signaling nans and follow libm's fmin/fmax,
 754     // and currently there isn't a nice wrapper in APFloat for the version with
 755     // correct snan handling.
 756     break;
 757   default:
 758     break;
 759   }
 760
 761   return std::nullopt;
 762 }
 763
 764 SmallVector<APInt>
 765 llvm::ConstantFoldVectorBinop(unsigned Opcode, const Register Op1,
 766                               const Register Op2,
 767                               const MachineRegisterInfo &MRI) {
 768   auto *SrcVec2 = getOpcodeDef<GBuildVector>(Op2, MRI);
 769   if (!SrcVec2)
 770     return SmallVector<APInt>();
 771
 772   auto *SrcVec1 = getOpcodeDef<GBuildVector>(Op1, MRI);
 773   if (!SrcVec1)
 774     return SmallVector<APInt>();
 775
 776   SmallVector<APInt> FoldedElements;
 777   for (unsigned Idx = 0, E = SrcVec1->getNumSources(); Idx < E; ++Idx) {
 778     auto MaybeCst = ConstantFoldBinOp(Opcode, SrcVec1->getSourceReg(Idx),
 779                                       SrcVec2->getSourceReg(Idx), MRI);
 780     if (!MaybeCst)
 781       return SmallVector<APInt>();
 782     FoldedElements.push_back(*MaybeCst);
 783   }
 784   return FoldedElements;
 785 }
 786
 787 bool llvm::isKnownNeverNaN(Register Val, const MachineRegisterInfo &MRI,
 788                            bool SNaN) {
 789   const MachineInstr *DefMI = MRI.getVRegDef(Val);
 790   if (!DefMI)
 791     return false;
 792
 793   const TargetMachine& TM = DefMI->getMF()->getTarget();
 794   if (DefMI->getFlag(MachineInstr::FmNoNans) || TM.Options.NoNaNsFPMath)
 795     return true;
 796
 797   // If the value is a constant, we can obviously see if it is a NaN or not.
 798   if (const ConstantFP *FPVal = getConstantFPVRegVal(Val, MRI)) {
 799     return !FPVal->getValueAPF().isNaN() ||
 800            (SNaN && !FPVal->getValueAPF().isSignaling());
 801   }
 802
 803   if (DefMI->getOpcode() == TargetOpcode::G_BUILD_VECTOR) {
 804     for (const auto &Op : DefMI->uses())
 805       if (!isKnownNeverNaN(Op.getReg(), MRI, SNaN))
 806         return false;
 807     return true;
 808   }
 809
 810   switch (DefMI->getOpcode()) {
 811   default:
 812     break;
 813   case TargetOpcode::G_FADD:
 814   case TargetOpcode::G_FSUB:
 815   case TargetOpcode::G_FMUL:
 816   case TargetOpcode::G_FDIV:
 817   case TargetOpcode::G_FREM:
 818   case TargetOpcode::G_FSIN:
 819   case TargetOpcode::G_FCOS:
 820   case TargetOpcode::G_FMA:
 821   case TargetOpcode::G_FMAD:
 822     if (SNaN)
 823       return true;
 824
 825     // TODO: Need isKnownNeverInfinity
 826     return false;
 827   case TargetOpcode::G_FMINNUM_IEEE:
 828   case TargetOpcode::G_FMAXNUM_IEEE: {
 829     if (SNaN)
 830       return true;
 831     // This can return a NaN if either operand is an sNaN, or if both operands
 832     // are NaN.
 833     return (isKnownNeverNaN(DefMI->getOperand(1).getReg(), MRI) &&
 834             isKnownNeverSNaN(DefMI->getOperand(2).getReg(), MRI)) ||
 835            (isKnownNeverSNaN(DefMI->getOperand(1).getReg(), MRI) &&
 836             isKnownNeverNaN(DefMI->getOperand(2).getReg(), MRI));
 837   }
 838   case TargetOpcode::G_FMINNUM:
 839   case TargetOpcode::G_FMAXNUM: {
 840     // Only one needs to be known not-nan, since it will be returned if the
 841     // other ends up being one.
 842     return isKnownNeverNaN(DefMI->getOperand(1).getReg(), MRI, SNaN) ||
 843            isKnownNeverNaN(DefMI->getOperand(2).getReg(), MRI, SNaN);
 844   }
 845   }
 846
 847   if (SNaN) {
 848     // FP operations quiet. For now, just handle the ones inserted during
 849     // legalization.
 850     switch (DefMI->getOpcode()) {
 851     case TargetOpcode::G_FPEXT:
 852     case TargetOpcode::G_FPTRUNC:
 853     case TargetOpcode::G_FCANONICALIZE:
 854       return true;
 855     default:
 856       return false;
 857     }
 858   }
 859
 860   return false;
 861 }
 862
 863 Align llvm::inferAlignFromPtrInfo(MachineFunction &MF,
 864                                   const MachinePointerInfo &MPO) {
 865   auto PSV = dyn_cast_if_present<const PseudoSourceValue *>(MPO.V);
 866   if (auto FSPV = dyn_cast_or_null<FixedStackPseudoSourceValue>(PSV)) {
 867     MachineFrameInfo &MFI = MF.getFrameInfo();
 868     return commonAlignment(MFI.getObjectAlign(FSPV->getFrameIndex()),
 869                            MPO.Offset);
 870   }
 871
 872   if (const Value *V = dyn_cast_if_present<const Value *>(MPO.V)) {
 873     const Module *M = MF.getFunction().getParent();
 874     return V->getPointerAlignment(M->getDataLayout());
 875   }
 876
 877   return Align(1);
 878 }
 879
 880 Register llvm::getFunctionLiveInPhysReg(MachineFunction &MF,
 881                                         const TargetInstrInfo &TII,
 882                                         MCRegister PhysReg,
 883                                         const TargetRegisterClass &RC,
 884                                         const DebugLoc &DL, LLT RegTy) {
 885   MachineBasicBlock &EntryMBB = MF.front();
 886   MachineRegisterInfo &MRI = MF.getRegInfo();
 887   Register LiveIn = MRI.getLiveInVirtReg(PhysReg);
 888   if (LiveIn) {
 889     MachineInstr *Def = MRI.getVRegDef(LiveIn);
 890     if (Def) {
 891       // FIXME: Should the verifier check this is in the entry block?
 892       assert(Def->getParent() == &EntryMBB && "live-in copy not in entry block");
 893       return LiveIn;
 894     }
 895
 896     // It's possible the incoming argument register and copy was added during
 897     // lowering, but later deleted due to being/becoming dead. If this happens,
 898     // re-insert the copy.
 899   } else {
 900     // The live in register was not present, so add it.
 901     LiveIn = MF.addLiveIn(PhysReg, &RC);
 902     if (RegTy.isValid())
 903       MRI.setType(LiveIn, RegTy);
 904   }
 905
 906   BuildMI(EntryMBB, EntryMBB.begin(), DL, TII.get(TargetOpcode::COPY), LiveIn)
 907     .addReg(PhysReg);
 908   if (!EntryMBB.isLiveIn(PhysReg))
 909     EntryMBB.addLiveIn(PhysReg);
 910   return LiveIn;
 911 }
 912
 913 std::optional<APInt> llvm::ConstantFoldExtOp(unsigned Opcode,
 914                                              const Register Op1, uint64_t Imm,
 915                                              const MachineRegisterInfo &MRI) {
 916   auto MaybeOp1Cst = getIConstantVRegVal(Op1, MRI);
 917   if (MaybeOp1Cst) {
 918     switch (Opcode) {
 919     default:
 920       break;
 921     case TargetOpcode::G_SEXT_INREG: {
 922       LLT Ty = MRI.getType(Op1);
 923       return MaybeOp1Cst->trunc(Imm).sext(Ty.getScalarSizeInBits());
 924     }
 925     }
 926   }
 927   return std::nullopt;
 928 }
 929
 930 std::optional<APInt> llvm::ConstantFoldCastOp(unsigned Opcode, LLT DstTy,
 931                                               const Register Op0,
 932                                               const MachineRegisterInfo &MRI) {
 933   std::optional<APInt> Val = getIConstantVRegVal(Op0, MRI);
 934   if (!Val)
 935     return Val;
 936
 937   const unsigned DstSize = DstTy.getScalarSizeInBits();
 938
 939   switch (Opcode) {
 940   case TargetOpcode::G_SEXT:
 941     return Val->sext(DstSize);
 942   case TargetOpcode::G_ZEXT:
 943   case TargetOpcode::G_ANYEXT:
 944     // TODO: DAG considers target preference when constant folding any_extend.
 945     return Val->zext(DstSize);
 946   default:
 947     break;
 948   }
 949
 950   llvm_unreachable("unexpected cast opcode to constant fold");
 951 }
 952
 953 std::optional<APFloat>
 954 llvm::ConstantFoldIntToFloat(unsigned Opcode, LLT DstTy, Register Src,
 955                              const MachineRegisterInfo &MRI) {
 956   assert(Opcode == TargetOpcode::G_SITOFP || Opcode == TargetOpcode::G_UITOFP);
 957   if (auto MaybeSrcVal = getIConstantVRegVal(Src, MRI)) {
 958     APFloat DstVal(getFltSemanticForLLT(DstTy));
 959     DstVal.convertFromAPInt(*MaybeSrcVal, Opcode == TargetOpcode::G_SITOFP,
 960                             APFloat::rmNearestTiesToEven);
 961     return DstVal;
 962   }
 963   return std::nullopt;
 964 }
 965
 966 std::optional<SmallVector<unsigned>>
 967 llvm::ConstantFoldCTLZ(Register Src, const MachineRegisterInfo &MRI) {
 968   LLT Ty = MRI.getType(Src);
 969   SmallVector<unsigned> FoldedCTLZs;
 970   auto tryFoldScalar = [&](Register R) -> std::optional<unsigned> {
 971     auto MaybeCst = getIConstantVRegVal(R, MRI);
 972     if (!MaybeCst)
 973       return std::nullopt;
 974     return MaybeCst->countl_zero();
 975   };
 976   if (Ty.isVector()) {
 977     // Try to constant fold each element.
 978     auto *BV = getOpcodeDef<GBuildVector>(Src, MRI);
 979     if (!BV)
 980       return std::nullopt;
 981     for (unsigned SrcIdx = 0; SrcIdx < BV->getNumSources(); ++SrcIdx) {
 982       if (auto MaybeFold = tryFoldScalar(BV->getSourceReg(SrcIdx))) {
 983         FoldedCTLZs.emplace_back(*MaybeFold);
 984         continue;
 985       }
 986       return std::nullopt;
 987     }
 988     return FoldedCTLZs;
 989   }
 990   if (auto MaybeCst = tryFoldScalar(Src)) {
 991     FoldedCTLZs.emplace_back(*MaybeCst);
 992     return FoldedCTLZs;
 993   }
 994   return std::nullopt;
 995 }
 996
 997 bool llvm::isKnownToBeAPowerOfTwo(Register Reg, const MachineRegisterInfo &MRI,
 998                                   GISelKnownBits *KB) {
 999   std::optional<DefinitionAndSourceRegister> DefSrcReg =
1000       getDefSrcRegIgnoringCopies(Reg, MRI);
1001   if (!DefSrcReg)
1002     return false;
1003
1004   const MachineInstr &MI = *DefSrcReg->MI;
1005   const LLT Ty = MRI.getType(Reg);
1006
1007   switch (MI.getOpcode()) {
1008   case TargetOpcode::G_CONSTANT: {
1009     unsigned BitWidth = Ty.getScalarSizeInBits();
1010     const ConstantInt *CI = MI.getOperand(1).getCImm();
1011     return CI->getValue().zextOrTrunc(BitWidth).isPowerOf2();
1012   }
1013   case TargetOpcode::G_SHL: {
1014     // A left-shift of a constant one will have exactly one bit set because
1015     // shifting the bit off the end is undefined.
1016
1017     // TODO: Constant splat
1018     if (auto ConstLHS = getIConstantVRegVal(MI.getOperand(1).getReg(), MRI)) {
1019       if (*ConstLHS == 1)
1020         return true;
1021     }
1022
1023     break;
1024   }
1025   case TargetOpcode::G_LSHR: {
1026     if (auto ConstLHS = getIConstantVRegVal(MI.getOperand(1).getReg(), MRI)) {
1027       if (ConstLHS->isSignMask())
1028         return true;
1029     }
1030
1031     break;
1032   }
1033   case TargetOpcode::G_BUILD_VECTOR: {
1034     // TODO: Probably should have a recursion depth guard since you could have
1035     // bitcasted vector elements.
1036     for (const MachineOperand &MO : llvm::drop_begin(MI.operands()))
1037       if (!isKnownToBeAPowerOfTwo(MO.getReg(), MRI, KB))
1038         return false;
1039
1040     return true;
1041   }
1042   case TargetOpcode::G_BUILD_VECTOR_TRUNC: {
1043     // Only handle constants since we would need to know if number of leading
1044     // zeros is greater than the truncation amount.
1045     const unsigned BitWidth = Ty.getScalarSizeInBits();
1046     for (const MachineOperand &MO : llvm::drop_begin(MI.operands())) {
1047       auto Const = getIConstantVRegVal(MO.getReg(), MRI);
1048       if (!Const || !Const->zextOrTrunc(BitWidth).isPowerOf2())
1049         return false;
1050     }
1051
1052     return true;
1053   }
1054   default:
1055     break;
1056   }
1057
1058   if (!KB)
1059     return false;
1060
1061   // More could be done here, though the above checks are enough
1062   // to handle some common cases.
1063
1064   // Fall back to computeKnownBits to catch other known cases.
1065   KnownBits Known = KB->getKnownBits(Reg);
1066   return (Known.countMaxPopulation() == 1) && (Known.countMinPopulation() == 1);
1067 }
1068
1069 void llvm::getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU) {
1070   AU.addPreserved<StackProtector>();
1071 }
1072
1073 LLT llvm::getLCMType(LLT OrigTy, LLT TargetTy) {
1074   const unsigned OrigSize = OrigTy.getSizeInBits();
1075   const unsigned TargetSize = TargetTy.getSizeInBits();
1076
1077   if (OrigSize == TargetSize)
1078     return OrigTy;
1079
1080   if (OrigTy.isVector()) {
1081     const LLT OrigElt = OrigTy.getElementType();
1082
1083     if (TargetTy.isVector()) {
1084       const LLT TargetElt = TargetTy.getElementType();
1085
1086       if (OrigElt.getSizeInBits() == TargetElt.getSizeInBits()) {
1087         int GCDElts =
1088             std::gcd(OrigTy.getNumElements(), TargetTy.getNumElements());
1089         // Prefer the original element type.
1090         ElementCount Mul = OrigTy.getElementCount() * TargetTy.getNumElements();
1091         return LLT::vector(Mul.divideCoefficientBy(GCDElts),
1092                            OrigTy.getElementType());
1093       }
1094     } else {
1095       if (OrigElt.getSizeInBits() == TargetSize)
1096         return OrigTy;
1097     }
1098
1099     unsigned LCMSize = std::lcm(OrigSize, TargetSize);
1100     return LLT::fixed_vector(LCMSize / OrigElt.getSizeInBits(), OrigElt);
1101   }
1102
1103   if (TargetTy.isVector()) {
1104     unsigned LCMSize = std::lcm(OrigSize, TargetSize);
1105     return LLT::fixed_vector(LCMSize / OrigSize, OrigTy);
1106   }
1107
1108   unsigned LCMSize = std::lcm(OrigSize, TargetSize);
1109
1110   // Preserve pointer types.
1111   if (LCMSize == OrigSize)
1112     return OrigTy;
1113   if (LCMSize == TargetSize)
1114     return TargetTy;
1115
1116   return LLT::scalar(LCMSize);
1117 }
1118
1119 LLT llvm::getCoverTy(LLT OrigTy, LLT TargetTy) {
1120   if (!OrigTy.isVector() || !TargetTy.isVector() || OrigTy == TargetTy ||
1121       (OrigTy.getScalarSizeInBits() != TargetTy.getScalarSizeInBits()))
1122     return getLCMType(OrigTy, TargetTy);
1123
1124   unsigned OrigTyNumElts = OrigTy.getNumElements();
1125   unsigned TargetTyNumElts = TargetTy.getNumElements();
1126   if (OrigTyNumElts % TargetTyNumElts == 0)
1127     return OrigTy;
1128
1129   unsigned NumElts = alignTo(OrigTyNumElts, TargetTyNumElts);
1130   return LLT::scalarOrVector(ElementCount::getFixed(NumElts),
1131                              OrigTy.getElementType());
1132 }
1133
1134 LLT llvm::getGCDType(LLT OrigTy, LLT TargetTy) {
1135   const unsigned OrigSize = OrigTy.getSizeInBits();
1136   const unsigned TargetSize = TargetTy.getSizeInBits();
1137
1138   if (OrigSize == TargetSize)
1139     return OrigTy;
1140
1141   if (OrigTy.isVector()) {
1142     LLT OrigElt = OrigTy.getElementType();
1143     if (TargetTy.isVector()) {
1144       LLT TargetElt = TargetTy.getElementType();
1145       if (OrigElt.getSizeInBits() == TargetElt.getSizeInBits()) {
1146         int GCD = std::gcd(OrigTy.getNumElements(), TargetTy.getNumElements());
1147         return LLT::scalarOrVector(ElementCount::getFixed(GCD), OrigElt);
1148       }
1149     } else {
1150       // If the source is a vector of pointers, return a pointer element.
1151       if (OrigElt.getSizeInBits() == TargetSize)
1152         return OrigElt;
1153     }
1154
1155     unsigned GCD = std::gcd(OrigSize, TargetSize);
1156     if (GCD == OrigElt.getSizeInBits())
1157       return OrigElt;
1158
1159     // If we can't produce the original element type, we have to use a smaller
1160     // scalar.
1161     if (GCD < OrigElt.getSizeInBits())
1162       return LLT::scalar(GCD);
1163     return LLT::fixed_vector(GCD / OrigElt.getSizeInBits(), OrigElt);
1164   }
1165
1166   if (TargetTy.isVector()) {
1167     // Try to preserve the original element type.
1168     LLT TargetElt = TargetTy.getElementType();
1169     if (TargetElt.getSizeInBits() == OrigSize)
1170       return OrigTy;
1171   }
1172
1173   unsigned GCD = std::gcd(OrigSize, TargetSize);
1174   return LLT::scalar(GCD);
1175 }
1176
1177 std::optional<int> llvm::getSplatIndex(MachineInstr &MI) {
1178   assert(MI.getOpcode() == TargetOpcode::G_SHUFFLE_VECTOR &&
1179          "Only G_SHUFFLE_VECTOR can have a splat index!");
1180   ArrayRef<int> Mask = MI.getOperand(3).getShuffleMask();
1181   auto FirstDefinedIdx = find_if(Mask, [](int Elt) { return Elt >= 0; });
1182
1183   // If all elements are undefined, this shuffle can be considered a splat.
1184   // Return 0 for better potential for callers to simplify.
1185   if (FirstDefinedIdx == Mask.end())
1186     return 0;
1187
1188   // Make sure all remaining elements are either undef or the same
1189   // as the first non-undef value.
1190   int SplatValue = *FirstDefinedIdx;
1191   if (any_of(make_range(std::next(FirstDefinedIdx), Mask.end()),
1192              [&SplatValue](int Elt) { return Elt >= 0 && Elt != SplatValue; }))
1193     return std::nullopt;
1194
1195   return SplatValue;
1196 }
1197
1198 static bool isBuildVectorOp(unsigned Opcode) {
1199   return Opcode == TargetOpcode::G_BUILD_VECTOR ||
1200          Opcode == TargetOpcode::G_BUILD_VECTOR_TRUNC;
1201 }
1202
1203 namespace {
1204
1205 std::optional<ValueAndVReg> getAnyConstantSplat(Register VReg,
1206                                                 const MachineRegisterInfo &MRI,
1207                                                 bool AllowUndef) {
1208   MachineInstr *MI = getDefIgnoringCopies(VReg, MRI);
1209   if (!MI)
1210     return std::nullopt;
1211
1212   bool isConcatVectorsOp = MI->getOpcode() == TargetOpcode::G_CONCAT_VECTORS;
1213   if (!isBuildVectorOp(MI->getOpcode()) && !isConcatVectorsOp)
1214     return std::nullopt;
1215
1216   std::optional<ValueAndVReg> SplatValAndReg;
1217   for (MachineOperand &Op : MI->uses()) {
1218     Register Element = Op.getReg();
1219     // If we have a G_CONCAT_VECTOR, we recursively look into the
1220     // vectors that we're concatenating to see if they're splats.
1221     auto ElementValAndReg =
1222         isConcatVectorsOp
1223             ? getAnyConstantSplat(Element, MRI, AllowUndef)
1224             : getAnyConstantVRegValWithLookThrough(Element, MRI, true, true);
1225
1226     // If AllowUndef, treat undef as value that will result in a constant splat.
1227     if (!ElementValAndReg) {
1228       if (AllowUndef && isa<GImplicitDef>(MRI.getVRegDef(Element)))
1229         continue;
1230       return std::nullopt;
1231     }
1232
1233     // Record splat value
1234     if (!SplatValAndReg)
1235       SplatValAndReg = ElementValAndReg;
1236
1237     // Different constant than the one already recorded, not a constant splat.
1238     if (SplatValAndReg->Value != ElementValAndReg->Value)
1239       return std::nullopt;
1240   }
1241
1242   return SplatValAndReg;
1243 }
1244
1245 } // end anonymous namespace
1246
1247 bool llvm::isBuildVectorConstantSplat(const Register Reg,
1248                                       const MachineRegisterInfo &MRI,
1249                                       int64_t SplatValue, bool AllowUndef) {
1250   if (auto SplatValAndReg = getAnyConstantSplat(Reg, MRI, AllowUndef))
1251     return mi_match(SplatValAndReg->VReg, MRI, m_SpecificICst(SplatValue));
1252   return false;
1253 }
1254
1255 bool llvm::isBuildVectorConstantSplat(const MachineInstr &MI,
1256                                       const MachineRegisterInfo &MRI,
1257                                       int64_t SplatValue, bool AllowUndef) {
1258   return isBuildVectorConstantSplat(MI.getOperand(0).getReg(), MRI, SplatValue,
1259                                     AllowUndef);
1260 }
1261
1262 std::optional<APInt>
1263 llvm::getIConstantSplatVal(const Register Reg, const MachineRegisterInfo &MRI) {
1264   if (auto SplatValAndReg =
1265           getAnyConstantSplat(Reg, MRI, /* AllowUndef */ false)) {
1266     if (std::optional<ValueAndVReg> ValAndVReg =
1267         getIConstantVRegValWithLookThrough(SplatValAndReg->VReg, MRI))
1268       return ValAndVReg->Value;
1269   }
1270
1271   return std::nullopt;
1272 }
1273
1274 std::optional<APInt>
1275 llvm::getIConstantSplatVal(const MachineInstr &MI,
1276                            const MachineRegisterInfo &MRI) {
1277   return getIConstantSplatVal(MI.getOperand(0).getReg(), MRI);
1278 }
1279
1280 std::optional<int64_t>
1281 llvm::getIConstantSplatSExtVal(const Register Reg,
1282                                const MachineRegisterInfo &MRI) {
1283   if (auto SplatValAndReg =
1284           getAnyConstantSplat(Reg, MRI, /* AllowUndef */ false))
1285     return getIConstantVRegSExtVal(SplatValAndReg->VReg, MRI);
1286   return std::nullopt;
1287 }
1288
1289 std::optional<int64_t>
1290 llvm::getIConstantSplatSExtVal(const MachineInstr &MI,
1291                                const MachineRegisterInfo &MRI) {
1292   return getIConstantSplatSExtVal(MI.getOperand(0).getReg(), MRI);
1293 }
1294
1295 std::optional<FPValueAndVReg>
1296 llvm::getFConstantSplat(Register VReg, const MachineRegisterInfo &MRI,
1297                         bool AllowUndef) {
1298   if (auto SplatValAndReg = getAnyConstantSplat(VReg, MRI, AllowUndef))
1299     return getFConstantVRegValWithLookThrough(SplatValAndReg->VReg, MRI);
1300   return std::nullopt;
1301 }
1302
1303 bool llvm::isBuildVectorAllZeros(const MachineInstr &MI,
1304                                  const MachineRegisterInfo &MRI,
1305                                  bool AllowUndef) {
1306   return isBuildVectorConstantSplat(MI, MRI, 0, AllowUndef);
1307 }
1308
1309 bool llvm::isBuildVectorAllOnes(const MachineInstr &MI,
1310                                 const MachineRegisterInfo &MRI,
1311                                 bool AllowUndef) {
1312   return isBuildVectorConstantSplat(MI, MRI, -1, AllowUndef);
1313 }
1314
1315 std::optional<RegOrConstant>
1316 llvm::getVectorSplat(const MachineInstr &MI, const MachineRegisterInfo &MRI) {
1317   unsigned Opc = MI.getOpcode();
1318   if (!isBuildVectorOp(Opc))
1319     return std::nullopt;
1320   if (auto Splat = getIConstantSplatSExtVal(MI, MRI))
1321     return RegOrConstant(*Splat);
1322   auto Reg = MI.getOperand(1).getReg();
1323   if (any_of(drop_begin(MI.operands(), 2),
1324              [&Reg](const MachineOperand &Op) { return Op.getReg() != Reg; }))
1325     return std::nullopt;
1326   return RegOrConstant(Reg);
1327 }
1328
1329 static bool isConstantScalar(const MachineInstr &MI,
1330                              const MachineRegisterInfo &MRI,
1331                              bool AllowFP = true,
1332                              bool AllowOpaqueConstants = true) {
1333   switch (MI.getOpcode()) {
1334   case TargetOpcode::G_CONSTANT:
1335   case TargetOpcode::G_IMPLICIT_DEF:
1336     return true;
1337   case TargetOpcode::G_FCONSTANT:
1338     return AllowFP;
1339   case TargetOpcode::G_GLOBAL_VALUE:
1340   case TargetOpcode::G_FRAME_INDEX:
1341   case TargetOpcode::G_BLOCK_ADDR:
1342   case TargetOpcode::G_JUMP_TABLE:
1343     return AllowOpaqueConstants;
1344   default:
1345     return false;
1346   }
1347 }
1348
1349 bool llvm::isConstantOrConstantVector(MachineInstr &MI,
1350                                       const MachineRegisterInfo &MRI) {
1351   Register Def = MI.getOperand(0).getReg();
1352   if (auto C = getIConstantVRegValWithLookThrough(Def, MRI))
1353     return true;
1354   GBuildVector *BV = dyn_cast<GBuildVector>(&MI);
1355   if (!BV)
1356     return false;
1357   for (unsigned SrcIdx = 0; SrcIdx < BV->getNumSources(); ++SrcIdx) {
1358     if (getIConstantVRegValWithLookThrough(BV->getSourceReg(SrcIdx), MRI) ||
1359         getOpcodeDef<GImplicitDef>(BV->getSourceReg(SrcIdx), MRI))
1360       continue;
1361     return false;
1362   }
1363   return true;
1364 }
1365
1366 bool llvm::isConstantOrConstantVector(const MachineInstr &MI,
1367                                       const MachineRegisterInfo &MRI,
1368                                       bool AllowFP, bool AllowOpaqueConstants) {
1369   if (isConstantScalar(MI, MRI, AllowFP, AllowOpaqueConstants))
1370     return true;
1371
1372   if (!isBuildVectorOp(MI.getOpcode()))
1373     return false;
1374
1375   const unsigned NumOps = MI.getNumOperands();
1376   for (unsigned I = 1; I != NumOps; ++I) {
1377     const MachineInstr *ElementDef = MRI.getVRegDef(MI.getOperand(I).getReg());
1378     if (!isConstantScalar(*ElementDef, MRI, AllowFP, AllowOpaqueConstants))
1379       return false;
1380   }
1381
1382   return true;
1383 }
1384
1385 std::optional<APInt>
1386 llvm::isConstantOrConstantSplatVector(MachineInstr &MI,
1387                                       const MachineRegisterInfo &MRI) {
1388   Register Def = MI.getOperand(0).getReg();
1389   if (auto C = getIConstantVRegValWithLookThrough(Def, MRI))
1390     return C->Value;
1391   auto MaybeCst = getIConstantSplatSExtVal(MI, MRI);
1392   if (!MaybeCst)
1393     return std::nullopt;
1394   const unsigned ScalarSize = MRI.getType(Def).getScalarSizeInBits();
1395   return APInt(ScalarSize, *MaybeCst, true);
1396 }
1397
1398 bool llvm::isNullOrNullSplat(const MachineInstr &MI,
1399                              const MachineRegisterInfo &MRI, bool AllowUndefs) {
1400   switch (MI.getOpcode()) {
1401   case TargetOpcode::G_IMPLICIT_DEF:
1402     return AllowUndefs;
1403   case TargetOpcode::G_CONSTANT:
1404     return MI.getOperand(1).getCImm()->isNullValue();
1405   case TargetOpcode::G_FCONSTANT: {
1406     const ConstantFP *FPImm = MI.getOperand(1).getFPImm();
1407     return FPImm->isZero() && !FPImm->isNegative();
1408   }
1409   default:
1410     if (!AllowUndefs) // TODO: isBuildVectorAllZeros assumes undef is OK already
1411       return false;
1412     return isBuildVectorAllZeros(MI, MRI);
1413   }
1414 }
1415
1416 bool llvm::isAllOnesOrAllOnesSplat(const MachineInstr &MI,
1417                                    const MachineRegisterInfo &MRI,
1418                                    bool AllowUndefs) {
1419   switch (MI.getOpcode()) {
1420   case TargetOpcode::G_IMPLICIT_DEF:
1421     return AllowUndefs;
1422   case TargetOpcode::G_CONSTANT:
1423     return MI.getOperand(1).getCImm()->isAllOnesValue();
1424   default:
1425     if (!AllowUndefs) // TODO: isBuildVectorAllOnes assumes undef is OK already
1426       return false;
1427     return isBuildVectorAllOnes(MI, MRI);
1428   }
1429 }
1430
1431 bool llvm::matchUnaryPredicate(
1432     const MachineRegisterInfo &MRI, Register Reg,
1433     std::function<bool(const Constant *ConstVal)> Match, bool AllowUndefs) {
1434
1435   const MachineInstr *Def = getDefIgnoringCopies(Reg, MRI);
1436   if (AllowUndefs && Def->getOpcode() == TargetOpcode::G_IMPLICIT_DEF)
1437     return Match(nullptr);
1438
1439   // TODO: Also handle fconstant
1440   if (Def->getOpcode() == TargetOpcode::G_CONSTANT)
1441     return Match(Def->getOperand(1).getCImm());
1442
1443   if (Def->getOpcode() != TargetOpcode::G_BUILD_VECTOR)
1444     return false;
1445
1446   for (unsigned I = 1, E = Def->getNumOperands(); I != E; ++I) {
1447     Register SrcElt = Def->getOperand(I).getReg();
1448     const MachineInstr *SrcDef = getDefIgnoringCopies(SrcElt, MRI);
1449     if (AllowUndefs && SrcDef->getOpcode() == TargetOpcode::G_IMPLICIT_DEF) {
1450       if (!Match(nullptr))
1451         return false;
1452       continue;
1453     }
1454
1455     if (SrcDef->getOpcode() != TargetOpcode::G_CONSTANT ||
1456         !Match(SrcDef->getOperand(1).getCImm()))
1457       return false;
1458   }
1459
1460   return true;
1461 }
1462
1463 bool llvm::isConstTrueVal(const TargetLowering &TLI, int64_t Val, bool IsVector,
1464                           bool IsFP) {
1465   switch (TLI.getBooleanContents(IsVector, IsFP)) {
1466   case TargetLowering::UndefinedBooleanContent:
1467     return Val & 0x1;
1468   case TargetLowering::ZeroOrOneBooleanContent:
1469     return Val == 1;
1470   case TargetLowering::ZeroOrNegativeOneBooleanContent:
1471     return Val == -1;
1472   }
1473   llvm_unreachable("Invalid boolean contents");
1474 }
1475
1476 bool llvm::isConstFalseVal(const TargetLowering &TLI, int64_t Val,
1477                            bool IsVector, bool IsFP) {
1478   switch (TLI.getBooleanContents(IsVector, IsFP)) {
1479   case TargetLowering::UndefinedBooleanContent:
1480     return ~Val & 0x1;
1481   case TargetLowering::ZeroOrOneBooleanContent:
1482   case TargetLowering::ZeroOrNegativeOneBooleanContent:
1483     return Val == 0;
1484   }
1485   llvm_unreachable("Invalid boolean contents");
1486 }
1487
1488 int64_t llvm::getICmpTrueVal(const TargetLowering &TLI, bool IsVector,
1489                              bool IsFP) {
1490   switch (TLI.getBooleanContents(IsVector, IsFP)) {
1491   case TargetLowering::UndefinedBooleanContent:
1492   case TargetLowering::ZeroOrOneBooleanContent:
1493     return 1;
1494   case TargetLowering::ZeroOrNegativeOneBooleanContent:
1495     return -1;
1496   }
1497   llvm_unreachable("Invalid boolean contents");
1498 }
1499
1500 bool llvm::shouldOptForSize(const MachineBasicBlock &MBB,
1501                             ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI) {
1502   const auto &F = MBB.getParent()->getFunction();
1503   return F.hasOptSize() || F.hasMinSize() ||
1504          llvm::shouldOptimizeForSize(MBB.getBasicBlock(), PSI, BFI);
1505 }
1506
1507 void llvm::saveUsesAndErase(MachineInstr &MI, MachineRegisterInfo &MRI,
1508                             LostDebugLocObserver *LocObserver,
1509                             SmallInstListTy &DeadInstChain) {
1510   for (MachineOperand &Op : MI.uses()) {
1511     if (Op.isReg() && Op.getReg().isVirtual())
1512       DeadInstChain.insert(MRI.getVRegDef(Op.getReg()));
1513   }
1514   LLVM_DEBUG(dbgs() << MI << "Is dead; erasing.\n");
1515   DeadInstChain.remove(&MI);
1516   MI.eraseFromParent();
1517   if (LocObserver)
1518     LocObserver->checkpoint(false);
1519 }
1520
1521 void llvm::eraseInstrs(ArrayRef<MachineInstr *> DeadInstrs,
1522                        MachineRegisterInfo &MRI,
1523                        LostDebugLocObserver *LocObserver) {
1524   SmallInstListTy DeadInstChain;
1525   for (MachineInstr *MI : DeadInstrs)
1526     saveUsesAndErase(*MI, MRI, LocObserver, DeadInstChain);
1527
1528   while (!DeadInstChain.empty()) {
1529     MachineInstr *Inst = DeadInstChain.pop_back_val();
1530     if (!isTriviallyDead(*Inst, MRI))
1531       continue;
1532     saveUsesAndErase(*Inst, MRI, LocObserver, DeadInstChain);
1533   }
1534 }
1535
1536 void llvm::eraseInstr(MachineInstr &MI, MachineRegisterInfo &MRI,
1537                       LostDebugLocObserver *LocObserver) {
1538   return eraseInstrs({&MI}, MRI, LocObserver);
1539 }
1540
1541 void llvm::salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI) {
1542   for (auto &Def : MI.defs()) {
1543     assert(Def.isReg() && "Must be a reg");
1544
1545     SmallVector<MachineOperand *, 16> DbgUsers;
1546     for (auto &MOUse : MRI.use_operands(Def.getReg())) {
1547       MachineInstr *DbgValue = MOUse.getParent();
1548       // Ignore partially formed DBG_VALUEs.
1549       if (DbgValue->isNonListDebugValue() && DbgValue->getNumOperands() == 4) {
1550         DbgUsers.push_back(&MOUse);
1551       }
1552     }
1553
1554     if (!DbgUsers.empty()) {
1555       salvageDebugInfoForDbgValue(MRI, MI, DbgUsers);
1556     }
1557   }
1558 }