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/GlobalISel/GISelChangeObserver.h"
17 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
18 #include "llvm/CodeGen/GlobalISel/MIPatternMatch.h"
19 #include "llvm/CodeGen/GlobalISel/RegisterBankInfo.h"
20 #include "llvm/CodeGen/MachineInstr.h"
21 #include "llvm/CodeGen/MachineInstrBuilder.h"
22 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
23 #include "llvm/CodeGen/MachineRegisterInfo.h"
24 #include "llvm/CodeGen/StackProtector.h"
25 #include "llvm/CodeGen/TargetInstrInfo.h"
26 #include "llvm/CodeGen/TargetLowering.h"
27 #include "llvm/CodeGen/TargetPassConfig.h"
28 #include "llvm/CodeGen/TargetRegisterInfo.h"
29 #include "llvm/IR/Constants.h"
30 #include "llvm/Target/TargetMachine.h"
31 
32 #define DEBUG_TYPE "globalisel-utils"
33 
34 using namespace llvm;
35 using namespace MIPatternMatch;
36 
37 Register llvm::constrainRegToClass(MachineRegisterInfo &MRI,
38                                    const TargetInstrInfo &TII,
39                                    const RegisterBankInfo &RBI, Register Reg,
40                                    const TargetRegisterClass &RegClass) {
41   if (!RBI.constrainGenericRegister(Reg, RegClass, MRI))
42     return MRI.createVirtualRegister(&RegClass);
43 
44   return Reg;
45 }
46 
47 Register llvm::constrainOperandRegClass(
48     const MachineFunction &MF, const TargetRegisterInfo &TRI,
49     MachineRegisterInfo &MRI, const TargetInstrInfo &TII,
50     const RegisterBankInfo &RBI, MachineInstr &InsertPt,
51     const TargetRegisterClass &RegClass, MachineOperand &RegMO) {
52   Register Reg = RegMO.getReg();
53   // Assume physical registers are properly constrained.
54   assert(Register::isVirtualRegister(Reg) && "PhysReg not implemented");
55 
56   Register ConstrainedReg = constrainRegToClass(MRI, TII, RBI, Reg, RegClass);
57   // If we created a new virtual register because the class is not compatible
58   // then create a copy between the new and the old register.
59   if (ConstrainedReg != Reg) {
60     MachineBasicBlock::iterator InsertIt(&InsertPt);
61     MachineBasicBlock &MBB = *InsertPt.getParent();
62     if (RegMO.isUse()) {
63       BuildMI(MBB, InsertIt, InsertPt.getDebugLoc(),
64               TII.get(TargetOpcode::COPY), ConstrainedReg)
65           .addReg(Reg);
66     } else {
67       assert(RegMO.isDef() && "Must be a definition");
68       BuildMI(MBB, std::next(InsertIt), InsertPt.getDebugLoc(),
69               TII.get(TargetOpcode::COPY), Reg)
70           .addReg(ConstrainedReg);
71     }
72     if (GISelChangeObserver *Observer = MF.getObserver()) {
73       Observer->changingInstr(*RegMO.getParent());
74     }
75     RegMO.setReg(ConstrainedReg);
76     if (GISelChangeObserver *Observer = MF.getObserver()) {
77       Observer->changedInstr(*RegMO.getParent());
78     }
79   } else {
80     if (GISelChangeObserver *Observer = MF.getObserver()) {
81       if (!RegMO.isDef()) {
82         MachineInstr *RegDef = MRI.getVRegDef(Reg);
83         Observer->changedInstr(*RegDef);
84       }
85       Observer->changingAllUsesOfReg(MRI, Reg);
86       Observer->finishedChangingAllUsesOfReg();
87     }
88   }
89   return ConstrainedReg;
90 }
91 
92 Register llvm::constrainOperandRegClass(
93     const MachineFunction &MF, const TargetRegisterInfo &TRI,
94     MachineRegisterInfo &MRI, const TargetInstrInfo &TII,
95     const RegisterBankInfo &RBI, MachineInstr &InsertPt, const MCInstrDesc &II,
96     MachineOperand &RegMO, unsigned OpIdx) {
97   Register Reg = RegMO.getReg();
98   // Assume physical registers are properly constrained.
99   assert(Register::isVirtualRegister(Reg) && "PhysReg not implemented");
100 
101   const TargetRegisterClass *RegClass = TII.getRegClass(II, OpIdx, &TRI, MF);
102   // Some of the target independent instructions, like COPY, may not impose any
103   // register class constraints on some of their operands: If it's a use, we can
104   // skip constraining as the instruction defining the register would constrain
105   // it.
106 
107   // We can't constrain unallocatable register classes, because we can't create
108   // virtual registers for these classes, so we need to let targets handled this
109   // case.
110   if (RegClass && !RegClass->isAllocatable())
111     RegClass = TRI.getConstrainedRegClassForOperand(RegMO, MRI);
112 
113   if (!RegClass) {
114     assert((!isTargetSpecificOpcode(II.getOpcode()) || RegMO.isUse()) &&
115            "Register class constraint is required unless either the "
116            "instruction is target independent or the operand is a use");
117     // FIXME: Just bailing out like this here could be not enough, unless we
118     // expect the users of this function to do the right thing for PHIs and
119     // COPY:
120     //   v1 = COPY v0
121     //   v2 = COPY v1
122     // v1 here may end up not being constrained at all. Please notice that to
123     // reproduce the issue we likely need a destination pattern of a selection
124     // rule producing such extra copies, not just an input GMIR with them as
125     // every existing target using selectImpl handles copies before calling it
126     // and they never reach this function.
127     return Reg;
128   }
129   return constrainOperandRegClass(MF, TRI, MRI, TII, RBI, InsertPt, *RegClass,
130                                   RegMO);
131 }
132 
133 bool llvm::constrainSelectedInstRegOperands(MachineInstr &I,
134                                             const TargetInstrInfo &TII,
135                                             const TargetRegisterInfo &TRI,
136                                             const RegisterBankInfo &RBI) {
137   assert(!isPreISelGenericOpcode(I.getOpcode()) &&
138          "A selected instruction is expected");
139   MachineBasicBlock &MBB = *I.getParent();
140   MachineFunction &MF = *MBB.getParent();
141   MachineRegisterInfo &MRI = MF.getRegInfo();
142 
143   for (unsigned OpI = 0, OpE = I.getNumExplicitOperands(); OpI != OpE; ++OpI) {
144     MachineOperand &MO = I.getOperand(OpI);
145 
146     // There's nothing to be done on non-register operands.
147     if (!MO.isReg())
148       continue;
149 
150     LLVM_DEBUG(dbgs() << "Converting operand: " << MO << '\n');
151     assert(MO.isReg() && "Unsupported non-reg operand");
152 
153     Register Reg = MO.getReg();
154     // Physical registers don't need to be constrained.
155     if (Register::isPhysicalRegister(Reg))
156       continue;
157 
158     // Register operands with a value of 0 (e.g. predicate operands) don't need
159     // to be constrained.
160     if (Reg == 0)
161       continue;
162 
163     // If the operand is a vreg, we should constrain its regclass, and only
164     // insert COPYs if that's impossible.
165     // constrainOperandRegClass does that for us.
166     constrainOperandRegClass(MF, TRI, MRI, TII, RBI, I, I.getDesc(), MO, OpI);
167 
168     // Tie uses to defs as indicated in MCInstrDesc if this hasn't already been
169     // done.
170     if (MO.isUse()) {
171       int DefIdx = I.getDesc().getOperandConstraint(OpI, MCOI::TIED_TO);
172       if (DefIdx != -1 && !I.isRegTiedToUseOperand(DefIdx))
173         I.tieOperands(DefIdx, OpI);
174     }
175   }
176   return true;
177 }
178 
179 bool llvm::canReplaceReg(Register DstReg, Register SrcReg,
180                          MachineRegisterInfo &MRI) {
181   // Give up if either DstReg or SrcReg  is a physical register.
182   if (DstReg.isPhysical() || SrcReg.isPhysical())
183     return false;
184   // Give up if the types don't match.
185   if (MRI.getType(DstReg) != MRI.getType(SrcReg))
186     return false;
187   // Replace if either DstReg has no constraints or the register
188   // constraints match.
189   return !MRI.getRegClassOrRegBank(DstReg) ||
190          MRI.getRegClassOrRegBank(DstReg) == MRI.getRegClassOrRegBank(SrcReg);
191 }
192 
193 bool llvm::isTriviallyDead(const MachineInstr &MI,
194                            const MachineRegisterInfo &MRI) {
195   // FIXME: This logical is mostly duplicated with
196   // DeadMachineInstructionElim::isDead. Why is LOCAL_ESCAPE not considered in
197   // MachineInstr::isLabel?
198 
199   // Don't delete frame allocation labels.
200   if (MI.getOpcode() == TargetOpcode::LOCAL_ESCAPE)
201     return false;
202 
203   // If we can move an instruction, we can remove it.  Otherwise, it has
204   // a side-effect of some sort.
205   bool SawStore = false;
206   if (!MI.isSafeToMove(/*AA=*/nullptr, SawStore) && !MI.isPHI())
207     return false;
208 
209   // Instructions without side-effects are dead iff they only define dead vregs.
210   for (auto &MO : MI.operands()) {
211     if (!MO.isReg() || !MO.isDef())
212       continue;
213 
214     Register Reg = MO.getReg();
215     if (Register::isPhysicalRegister(Reg) || !MRI.use_nodbg_empty(Reg))
216       return false;
217   }
218   return true;
219 }
220 
221 static void reportGISelDiagnostic(DiagnosticSeverity Severity,
222                                   MachineFunction &MF,
223                                   const TargetPassConfig &TPC,
224                                   MachineOptimizationRemarkEmitter &MORE,
225                                   MachineOptimizationRemarkMissed &R) {
226   bool IsFatal = Severity == DS_Error &&
227                  TPC.isGlobalISelAbortEnabled();
228   // Print the function name explicitly if we don't have a debug location (which
229   // makes the diagnostic less useful) or if we're going to emit a raw error.
230   if (!R.getLocation().isValid() || IsFatal)
231     R << (" (in function: " + MF.getName() + ")").str();
232 
233   if (IsFatal)
234     report_fatal_error(R.getMsg());
235   else
236     MORE.emit(R);
237 }
238 
239 void llvm::reportGISelWarning(MachineFunction &MF, const TargetPassConfig &TPC,
240                               MachineOptimizationRemarkEmitter &MORE,
241                               MachineOptimizationRemarkMissed &R) {
242   reportGISelDiagnostic(DS_Warning, MF, TPC, MORE, R);
243 }
244 
245 void llvm::reportGISelFailure(MachineFunction &MF, const TargetPassConfig &TPC,
246                               MachineOptimizationRemarkEmitter &MORE,
247                               MachineOptimizationRemarkMissed &R) {
248   MF.getProperties().set(MachineFunctionProperties::Property::FailedISel);
249   reportGISelDiagnostic(DS_Error, MF, TPC, MORE, R);
250 }
251 
252 void llvm::reportGISelFailure(MachineFunction &MF, const TargetPassConfig &TPC,
253                               MachineOptimizationRemarkEmitter &MORE,
254                               const char *PassName, StringRef Msg,
255                               const MachineInstr &MI) {
256   MachineOptimizationRemarkMissed R(PassName, "GISelFailure: ",
257                                     MI.getDebugLoc(), MI.getParent());
258   R << Msg;
259   // Printing MI is expensive;  only do it if expensive remarks are enabled.
260   if (TPC.isGlobalISelAbortEnabled() || MORE.allowExtraAnalysis(PassName))
261     R << ": " << ore::MNV("Inst", MI);
262   reportGISelFailure(MF, TPC, MORE, R);
263 }
264 
265 Optional<APInt> llvm::getConstantVRegVal(Register VReg,
266                                          const MachineRegisterInfo &MRI) {
267   Optional<ValueAndVReg> ValAndVReg =
268       getConstantVRegValWithLookThrough(VReg, MRI, /*LookThroughInstrs*/ false);
269   assert((!ValAndVReg || ValAndVReg->VReg == VReg) &&
270          "Value found while looking through instrs");
271   if (!ValAndVReg)
272     return None;
273   return ValAndVReg->Value;
274 }
275 
276 Optional<int64_t> llvm::getConstantVRegSExtVal(Register VReg,
277                                                const MachineRegisterInfo &MRI) {
278   Optional<APInt> Val = getConstantVRegVal(VReg, MRI);
279   if (Val && Val->getBitWidth() <= 64)
280     return Val->getSExtValue();
281   return None;
282 }
283 
284 Optional<ValueAndVReg> llvm::getConstantVRegValWithLookThrough(
285     Register VReg, const MachineRegisterInfo &MRI, bool LookThroughInstrs,
286     bool HandleFConstant, bool LookThroughAnyExt) {
287   SmallVector<std::pair<unsigned, unsigned>, 4> SeenOpcodes;
288   MachineInstr *MI;
289   auto IsConstantOpcode = [HandleFConstant](unsigned Opcode) {
290     return Opcode == TargetOpcode::G_CONSTANT ||
291            (HandleFConstant && Opcode == TargetOpcode::G_FCONSTANT);
292   };
293   auto GetImmediateValue = [HandleFConstant,
294                             &MRI](const MachineInstr &MI) -> Optional<APInt> {
295     const MachineOperand &CstVal = MI.getOperand(1);
296     if (!CstVal.isImm() && !CstVal.isCImm() &&
297         (!HandleFConstant || !CstVal.isFPImm()))
298       return None;
299     if (!CstVal.isFPImm()) {
300       unsigned BitWidth =
301           MRI.getType(MI.getOperand(0).getReg()).getSizeInBits();
302       APInt Val = CstVal.isImm() ? APInt(BitWidth, CstVal.getImm())
303                                  : CstVal.getCImm()->getValue();
304       assert(Val.getBitWidth() == BitWidth &&
305              "Value bitwidth doesn't match definition type");
306       return Val;
307     }
308     return CstVal.getFPImm()->getValueAPF().bitcastToAPInt();
309   };
310   while ((MI = MRI.getVRegDef(VReg)) && !IsConstantOpcode(MI->getOpcode()) &&
311          LookThroughInstrs) {
312     switch (MI->getOpcode()) {
313     case TargetOpcode::G_ANYEXT:
314       if (!LookThroughAnyExt)
315         return None;
316       LLVM_FALLTHROUGH;
317     case TargetOpcode::G_TRUNC:
318     case TargetOpcode::G_SEXT:
319     case TargetOpcode::G_ZEXT:
320       SeenOpcodes.push_back(std::make_pair(
321           MI->getOpcode(),
322           MRI.getType(MI->getOperand(0).getReg()).getSizeInBits()));
323       VReg = MI->getOperand(1).getReg();
324       break;
325     case TargetOpcode::COPY:
326       VReg = MI->getOperand(1).getReg();
327       if (Register::isPhysicalRegister(VReg))
328         return None;
329       break;
330     case TargetOpcode::G_INTTOPTR:
331       VReg = MI->getOperand(1).getReg();
332       break;
333     default:
334       return None;
335     }
336   }
337   if (!MI || !IsConstantOpcode(MI->getOpcode()))
338     return None;
339 
340   Optional<APInt> MaybeVal = GetImmediateValue(*MI);
341   if (!MaybeVal)
342     return None;
343   APInt &Val = *MaybeVal;
344   while (!SeenOpcodes.empty()) {
345     std::pair<unsigned, unsigned> OpcodeAndSize = SeenOpcodes.pop_back_val();
346     switch (OpcodeAndSize.first) {
347     case TargetOpcode::G_TRUNC:
348       Val = Val.trunc(OpcodeAndSize.second);
349       break;
350     case TargetOpcode::G_ANYEXT:
351     case TargetOpcode::G_SEXT:
352       Val = Val.sext(OpcodeAndSize.second);
353       break;
354     case TargetOpcode::G_ZEXT:
355       Val = Val.zext(OpcodeAndSize.second);
356       break;
357     }
358   }
359 
360   return ValueAndVReg{Val, VReg};
361 }
362 
363 const ConstantFP *
364 llvm::getConstantFPVRegVal(Register VReg, const MachineRegisterInfo &MRI) {
365   MachineInstr *MI = MRI.getVRegDef(VReg);
366   if (TargetOpcode::G_FCONSTANT != MI->getOpcode())
367     return nullptr;
368   return MI->getOperand(1).getFPImm();
369 }
370 
371 Optional<DefinitionAndSourceRegister>
372 llvm::getDefSrcRegIgnoringCopies(Register Reg, const MachineRegisterInfo &MRI) {
373   Register DefSrcReg = Reg;
374   auto *DefMI = MRI.getVRegDef(Reg);
375   auto DstTy = MRI.getType(DefMI->getOperand(0).getReg());
376   if (!DstTy.isValid())
377     return None;
378   while (DefMI->getOpcode() == TargetOpcode::COPY) {
379     Register SrcReg = DefMI->getOperand(1).getReg();
380     auto SrcTy = MRI.getType(SrcReg);
381     if (!SrcTy.isValid())
382       break;
383     DefMI = MRI.getVRegDef(SrcReg);
384     DefSrcReg = SrcReg;
385   }
386   return DefinitionAndSourceRegister{DefMI, DefSrcReg};
387 }
388 
389 MachineInstr *llvm::getDefIgnoringCopies(Register Reg,
390                                          const MachineRegisterInfo &MRI) {
391   Optional<DefinitionAndSourceRegister> DefSrcReg =
392       getDefSrcRegIgnoringCopies(Reg, MRI);
393   return DefSrcReg ? DefSrcReg->MI : nullptr;
394 }
395 
396 Register llvm::getSrcRegIgnoringCopies(Register Reg,
397                                        const MachineRegisterInfo &MRI) {
398   Optional<DefinitionAndSourceRegister> DefSrcReg =
399       getDefSrcRegIgnoringCopies(Reg, MRI);
400   return DefSrcReg ? DefSrcReg->Reg : Register();
401 }
402 
403 MachineInstr *llvm::getOpcodeDef(unsigned Opcode, Register Reg,
404                                  const MachineRegisterInfo &MRI) {
405   MachineInstr *DefMI = getDefIgnoringCopies(Reg, MRI);
406   return DefMI && DefMI->getOpcode() == Opcode ? DefMI : nullptr;
407 }
408 
409 APFloat llvm::getAPFloatFromSize(double Val, unsigned Size) {
410   if (Size == 32)
411     return APFloat(float(Val));
412   if (Size == 64)
413     return APFloat(Val);
414   if (Size != 16)
415     llvm_unreachable("Unsupported FPConstant size");
416   bool Ignored;
417   APFloat APF(Val);
418   APF.convert(APFloat::IEEEhalf(), APFloat::rmNearestTiesToEven, &Ignored);
419   return APF;
420 }
421 
422 Optional<APInt> llvm::ConstantFoldBinOp(unsigned Opcode, const Register Op1,
423                                         const Register Op2,
424                                         const MachineRegisterInfo &MRI) {
425   auto MaybeOp2Cst = getConstantVRegVal(Op2, MRI);
426   if (!MaybeOp2Cst)
427     return None;
428 
429   auto MaybeOp1Cst = getConstantVRegVal(Op1, MRI);
430   if (!MaybeOp1Cst)
431     return None;
432 
433   const APInt &C1 = *MaybeOp1Cst;
434   const APInt &C2 = *MaybeOp2Cst;
435   switch (Opcode) {
436   default:
437     break;
438   case TargetOpcode::G_ADD:
439     return C1 + C2;
440   case TargetOpcode::G_AND:
441     return C1 & C2;
442   case TargetOpcode::G_ASHR:
443     return C1.ashr(C2);
444   case TargetOpcode::G_LSHR:
445     return C1.lshr(C2);
446   case TargetOpcode::G_MUL:
447     return C1 * C2;
448   case TargetOpcode::G_OR:
449     return C1 | C2;
450   case TargetOpcode::G_SHL:
451     return C1 << C2;
452   case TargetOpcode::G_SUB:
453     return C1 - C2;
454   case TargetOpcode::G_XOR:
455     return C1 ^ C2;
456   case TargetOpcode::G_UDIV:
457     if (!C2.getBoolValue())
458       break;
459     return C1.udiv(C2);
460   case TargetOpcode::G_SDIV:
461     if (!C2.getBoolValue())
462       break;
463     return C1.sdiv(C2);
464   case TargetOpcode::G_UREM:
465     if (!C2.getBoolValue())
466       break;
467     return C1.urem(C2);
468   case TargetOpcode::G_SREM:
469     if (!C2.getBoolValue())
470       break;
471     return C1.srem(C2);
472   }
473 
474   return None;
475 }
476 
477 bool llvm::isKnownNeverNaN(Register Val, const MachineRegisterInfo &MRI,
478                            bool SNaN) {
479   const MachineInstr *DefMI = MRI.getVRegDef(Val);
480   if (!DefMI)
481     return false;
482 
483   const TargetMachine& TM = DefMI->getMF()->getTarget();
484   if (DefMI->getFlag(MachineInstr::FmNoNans) || TM.Options.NoNaNsFPMath)
485     return true;
486 
487   if (SNaN) {
488     // FP operations quiet. For now, just handle the ones inserted during
489     // legalization.
490     switch (DefMI->getOpcode()) {
491     case TargetOpcode::G_FPEXT:
492     case TargetOpcode::G_FPTRUNC:
493     case TargetOpcode::G_FCANONICALIZE:
494       return true;
495     default:
496       return false;
497     }
498   }
499 
500   return false;
501 }
502 
503 Align llvm::inferAlignFromPtrInfo(MachineFunction &MF,
504                                   const MachinePointerInfo &MPO) {
505   auto PSV = MPO.V.dyn_cast<const PseudoSourceValue *>();
506   if (auto FSPV = dyn_cast_or_null<FixedStackPseudoSourceValue>(PSV)) {
507     MachineFrameInfo &MFI = MF.getFrameInfo();
508     return commonAlignment(MFI.getObjectAlign(FSPV->getFrameIndex()),
509                            MPO.Offset);
510   }
511 
512   return Align(1);
513 }
514 
515 Register llvm::getFunctionLiveInPhysReg(MachineFunction &MF,
516                                         const TargetInstrInfo &TII,
517                                         MCRegister PhysReg,
518                                         const TargetRegisterClass &RC,
519                                         LLT RegTy) {
520   DebugLoc DL; // FIXME: Is no location the right choice?
521   MachineBasicBlock &EntryMBB = MF.front();
522   MachineRegisterInfo &MRI = MF.getRegInfo();
523   Register LiveIn = MRI.getLiveInVirtReg(PhysReg);
524   if (LiveIn) {
525     MachineInstr *Def = MRI.getVRegDef(LiveIn);
526     if (Def) {
527       // FIXME: Should the verifier check this is in the entry block?
528       assert(Def->getParent() == &EntryMBB && "live-in copy not in entry block");
529       return LiveIn;
530     }
531 
532     // It's possible the incoming argument register and copy was added during
533     // lowering, but later deleted due to being/becoming dead. If this happens,
534     // re-insert the copy.
535   } else {
536     // The live in register was not present, so add it.
537     LiveIn = MF.addLiveIn(PhysReg, &RC);
538     if (RegTy.isValid())
539       MRI.setType(LiveIn, RegTy);
540   }
541 
542   BuildMI(EntryMBB, EntryMBB.begin(), DL, TII.get(TargetOpcode::COPY), LiveIn)
543     .addReg(PhysReg);
544   if (!EntryMBB.isLiveIn(PhysReg))
545     EntryMBB.addLiveIn(PhysReg);
546   return LiveIn;
547 }
548 
549 Optional<APInt> llvm::ConstantFoldExtOp(unsigned Opcode, const Register Op1,
550                                         uint64_t Imm,
551                                         const MachineRegisterInfo &MRI) {
552   auto MaybeOp1Cst = getConstantVRegVal(Op1, MRI);
553   if (MaybeOp1Cst) {
554     switch (Opcode) {
555     default:
556       break;
557     case TargetOpcode::G_SEXT_INREG: {
558       LLT Ty = MRI.getType(Op1);
559       return MaybeOp1Cst->trunc(Imm).sext(Ty.getScalarSizeInBits());
560     }
561     }
562   }
563   return None;
564 }
565 
566 bool llvm::isKnownToBeAPowerOfTwo(Register Reg, const MachineRegisterInfo &MRI,
567                                   GISelKnownBits *KB) {
568   Optional<DefinitionAndSourceRegister> DefSrcReg =
569       getDefSrcRegIgnoringCopies(Reg, MRI);
570   if (!DefSrcReg)
571     return false;
572 
573   const MachineInstr &MI = *DefSrcReg->MI;
574   const LLT Ty = MRI.getType(Reg);
575 
576   switch (MI.getOpcode()) {
577   case TargetOpcode::G_CONSTANT: {
578     unsigned BitWidth = Ty.getScalarSizeInBits();
579     const ConstantInt *CI = MI.getOperand(1).getCImm();
580     return CI->getValue().zextOrTrunc(BitWidth).isPowerOf2();
581   }
582   case TargetOpcode::G_SHL: {
583     // A left-shift of a constant one will have exactly one bit set because
584     // shifting the bit off the end is undefined.
585 
586     // TODO: Constant splat
587     if (auto ConstLHS = getConstantVRegVal(MI.getOperand(1).getReg(), MRI)) {
588       if (*ConstLHS == 1)
589         return true;
590     }
591 
592     break;
593   }
594   case TargetOpcode::G_LSHR: {
595     if (auto ConstLHS = getConstantVRegVal(MI.getOperand(1).getReg(), MRI)) {
596       if (ConstLHS->isSignMask())
597         return true;
598     }
599 
600     break;
601   }
602   default:
603     break;
604   }
605 
606   // TODO: Are all operands of a build vector constant powers of two?
607   if (!KB)
608     return false;
609 
610   // More could be done here, though the above checks are enough
611   // to handle some common cases.
612 
613   // Fall back to computeKnownBits to catch other known cases.
614   KnownBits Known = KB->getKnownBits(Reg);
615   return (Known.countMaxPopulation() == 1) && (Known.countMinPopulation() == 1);
616 }
617 
618 void llvm::getSelectionDAGFallbackAnalysisUsage(AnalysisUsage &AU) {
619   AU.addPreserved<StackProtector>();
620 }
621 
622 static unsigned getLCMSize(unsigned OrigSize, unsigned TargetSize) {
623   unsigned Mul = OrigSize * TargetSize;
624   unsigned GCDSize = greatestCommonDivisor(OrigSize, TargetSize);
625   return Mul / GCDSize;
626 }
627 
628 LLT llvm::getLCMType(LLT OrigTy, LLT TargetTy) {
629   const unsigned OrigSize = OrigTy.getSizeInBits();
630   const unsigned TargetSize = TargetTy.getSizeInBits();
631 
632   if (OrigSize == TargetSize)
633     return OrigTy;
634 
635   if (OrigTy.isVector()) {
636     const LLT OrigElt = OrigTy.getElementType();
637 
638     if (TargetTy.isVector()) {
639       const LLT TargetElt = TargetTy.getElementType();
640 
641       if (OrigElt.getSizeInBits() == TargetElt.getSizeInBits()) {
642         int GCDElts = greatestCommonDivisor(OrigTy.getNumElements(),
643                                             TargetTy.getNumElements());
644         // Prefer the original element type.
645         int Mul = OrigTy.getNumElements() * TargetTy.getNumElements();
646         return LLT::vector(Mul / GCDElts, OrigTy.getElementType());
647       }
648     } else {
649       if (OrigElt.getSizeInBits() == TargetSize)
650         return OrigTy;
651     }
652 
653     unsigned LCMSize = getLCMSize(OrigSize, TargetSize);
654     return LLT::vector(LCMSize / OrigElt.getSizeInBits(), OrigElt);
655   }
656 
657   if (TargetTy.isVector()) {
658     unsigned LCMSize = getLCMSize(OrigSize, TargetSize);
659     return LLT::vector(LCMSize / OrigSize, OrigTy);
660   }
661 
662   unsigned LCMSize = getLCMSize(OrigSize, TargetSize);
663 
664   // Preserve pointer types.
665   if (LCMSize == OrigSize)
666     return OrigTy;
667   if (LCMSize == TargetSize)
668     return TargetTy;
669 
670   return LLT::scalar(LCMSize);
671 }
672 
673 LLT llvm::getGCDType(LLT OrigTy, LLT TargetTy) {
674   const unsigned OrigSize = OrigTy.getSizeInBits();
675   const unsigned TargetSize = TargetTy.getSizeInBits();
676 
677   if (OrigSize == TargetSize)
678     return OrigTy;
679 
680   if (OrigTy.isVector()) {
681     LLT OrigElt = OrigTy.getElementType();
682     if (TargetTy.isVector()) {
683       LLT TargetElt = TargetTy.getElementType();
684       if (OrigElt.getSizeInBits() == TargetElt.getSizeInBits()) {
685         int GCD = greatestCommonDivisor(OrigTy.getNumElements(),
686                                         TargetTy.getNumElements());
687         return LLT::scalarOrVector(GCD, OrigElt);
688       }
689     } else {
690       // If the source is a vector of pointers, return a pointer element.
691       if (OrigElt.getSizeInBits() == TargetSize)
692         return OrigElt;
693     }
694 
695     unsigned GCD = greatestCommonDivisor(OrigSize, TargetSize);
696     if (GCD == OrigElt.getSizeInBits())
697       return OrigElt;
698 
699     // If we can't produce the original element type, we have to use a smaller
700     // scalar.
701     if (GCD < OrigElt.getSizeInBits())
702       return LLT::scalar(GCD);
703     return LLT::vector(GCD / OrigElt.getSizeInBits(), OrigElt);
704   }
705 
706   if (TargetTy.isVector()) {
707     // Try to preserve the original element type.
708     LLT TargetElt = TargetTy.getElementType();
709     if (TargetElt.getSizeInBits() == OrigSize)
710       return OrigTy;
711   }
712 
713   unsigned GCD = greatestCommonDivisor(OrigSize, TargetSize);
714   return LLT::scalar(GCD);
715 }
716 
717 Optional<int> llvm::getSplatIndex(MachineInstr &MI) {
718   assert(MI.getOpcode() == TargetOpcode::G_SHUFFLE_VECTOR &&
719          "Only G_SHUFFLE_VECTOR can have a splat index!");
720   ArrayRef<int> Mask = MI.getOperand(3).getShuffleMask();
721   auto FirstDefinedIdx = find_if(Mask, [](int Elt) { return Elt >= 0; });
722 
723   // If all elements are undefined, this shuffle can be considered a splat.
724   // Return 0 for better potential for callers to simplify.
725   if (FirstDefinedIdx == Mask.end())
726     return 0;
727 
728   // Make sure all remaining elements are either undef or the same
729   // as the first non-undef value.
730   int SplatValue = *FirstDefinedIdx;
731   if (any_of(make_range(std::next(FirstDefinedIdx), Mask.end()),
732              [&SplatValue](int Elt) { return Elt >= 0 && Elt != SplatValue; }))
733     return None;
734 
735   return SplatValue;
736 }
737 
738 static bool isBuildVectorOp(unsigned Opcode) {
739   return Opcode == TargetOpcode::G_BUILD_VECTOR ||
740          Opcode == TargetOpcode::G_BUILD_VECTOR_TRUNC;
741 }
742 
743 // TODO: Handle mixed undef elements.
744 static bool isBuildVectorConstantSplat(const MachineInstr &MI,
745                                        const MachineRegisterInfo &MRI,
746                                        int64_t SplatValue) {
747   if (!isBuildVectorOp(MI.getOpcode()))
748     return false;
749 
750   const unsigned NumOps = MI.getNumOperands();
751   for (unsigned I = 1; I != NumOps; ++I) {
752     Register Element = MI.getOperand(I).getReg();
753     if (!mi_match(Element, MRI, m_SpecificICst(SplatValue)))
754       return false;
755   }
756 
757   return true;
758 }
759 
760 Optional<int64_t>
761 llvm::getBuildVectorConstantSplat(const MachineInstr &MI,
762                                   const MachineRegisterInfo &MRI) {
763   if (!isBuildVectorOp(MI.getOpcode()))
764     return None;
765 
766   const unsigned NumOps = MI.getNumOperands();
767   Optional<int64_t> Scalar;
768   for (unsigned I = 1; I != NumOps; ++I) {
769     Register Element = MI.getOperand(I).getReg();
770     int64_t ElementValue;
771     if (!mi_match(Element, MRI, m_ICst(ElementValue)))
772       return None;
773     if (!Scalar)
774       Scalar = ElementValue;
775     else if (*Scalar != ElementValue)
776       return None;
777   }
778 
779   return Scalar;
780 }
781 
782 bool llvm::isBuildVectorAllZeros(const MachineInstr &MI,
783                                  const MachineRegisterInfo &MRI) {
784   return isBuildVectorConstantSplat(MI, MRI, 0);
785 }
786 
787 bool llvm::isBuildVectorAllOnes(const MachineInstr &MI,
788                                 const MachineRegisterInfo &MRI) {
789   return isBuildVectorConstantSplat(MI, MRI, -1);
790 }
791 
792 bool llvm::isConstTrueVal(const TargetLowering &TLI, int64_t Val, bool IsVector,
793                           bool IsFP) {
794   switch (TLI.getBooleanContents(IsVector, IsFP)) {
795   case TargetLowering::UndefinedBooleanContent:
796     return Val & 0x1;
797   case TargetLowering::ZeroOrOneBooleanContent:
798     return Val == 1;
799   case TargetLowering::ZeroOrNegativeOneBooleanContent:
800     return Val == -1;
801   }
802   llvm_unreachable("Invalid boolean contents");
803 }
804 
805 int64_t llvm::getICmpTrueVal(const TargetLowering &TLI, bool IsVector,
806                              bool IsFP) {
807   switch (TLI.getBooleanContents(IsVector, IsFP)) {
808   case TargetLowering::UndefinedBooleanContent:
809   case TargetLowering::ZeroOrOneBooleanContent:
810     return 1;
811   case TargetLowering::ZeroOrNegativeOneBooleanContent:
812     return -1;
813   }
814   llvm_unreachable("Invalid boolean contents");
815 }
816