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