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