xref: /llvm-project/llvm/lib/CodeGen/GlobalISel/IRTranslator.cpp (revision 4048c64306e23b622443bbe7293057a9b07a13bb)
1 //===- llvm/CodeGen/GlobalISel/IRTranslator.cpp - IRTranslator ---*- 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
9 /// This file implements the IRTranslator class.
10 //===----------------------------------------------------------------------===//
11 
12 #include "llvm/CodeGen/GlobalISel/IRTranslator.h"
13 #include "llvm/ADT/PostOrderIterator.h"
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/ADT/ScopeExit.h"
16 #include "llvm/ADT/SmallSet.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/Analysis/AliasAnalysis.h"
19 #include "llvm/Analysis/AssumptionCache.h"
20 #include "llvm/Analysis/BranchProbabilityInfo.h"
21 #include "llvm/Analysis/Loads.h"
22 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
23 #include "llvm/Analysis/ValueTracking.h"
24 #include "llvm/Analysis/VectorUtils.h"
25 #include "llvm/CodeGen/Analysis.h"
26 #include "llvm/CodeGen/GlobalISel/CSEInfo.h"
27 #include "llvm/CodeGen/GlobalISel/CSEMIRBuilder.h"
28 #include "llvm/CodeGen/GlobalISel/CallLowering.h"
29 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
30 #include "llvm/CodeGen/GlobalISel/InlineAsmLowering.h"
31 #include "llvm/CodeGen/GlobalISel/MachineIRBuilder.h"
32 #include "llvm/CodeGen/LowLevelTypeUtils.h"
33 #include "llvm/CodeGen/MachineBasicBlock.h"
34 #include "llvm/CodeGen/MachineFrameInfo.h"
35 #include "llvm/CodeGen/MachineFunction.h"
36 #include "llvm/CodeGen/MachineInstrBuilder.h"
37 #include "llvm/CodeGen/MachineMemOperand.h"
38 #include "llvm/CodeGen/MachineModuleInfo.h"
39 #include "llvm/CodeGen/MachineOperand.h"
40 #include "llvm/CodeGen/MachineRegisterInfo.h"
41 #include "llvm/CodeGen/StackProtector.h"
42 #include "llvm/CodeGen/SwitchLoweringUtils.h"
43 #include "llvm/CodeGen/TargetFrameLowering.h"
44 #include "llvm/CodeGen/TargetInstrInfo.h"
45 #include "llvm/CodeGen/TargetLowering.h"
46 #include "llvm/CodeGen/TargetOpcodes.h"
47 #include "llvm/CodeGen/TargetPassConfig.h"
48 #include "llvm/CodeGen/TargetRegisterInfo.h"
49 #include "llvm/CodeGen/TargetSubtargetInfo.h"
50 #include "llvm/CodeGenTypes/LowLevelType.h"
51 #include "llvm/IR/BasicBlock.h"
52 #include "llvm/IR/CFG.h"
53 #include "llvm/IR/Constant.h"
54 #include "llvm/IR/Constants.h"
55 #include "llvm/IR/DataLayout.h"
56 #include "llvm/IR/DerivedTypes.h"
57 #include "llvm/IR/DiagnosticInfo.h"
58 #include "llvm/IR/Function.h"
59 #include "llvm/IR/GetElementPtrTypeIterator.h"
60 #include "llvm/IR/InlineAsm.h"
61 #include "llvm/IR/InstrTypes.h"
62 #include "llvm/IR/Instructions.h"
63 #include "llvm/IR/IntrinsicInst.h"
64 #include "llvm/IR/Intrinsics.h"
65 #include "llvm/IR/IntrinsicsAMDGPU.h"
66 #include "llvm/IR/LLVMContext.h"
67 #include "llvm/IR/Metadata.h"
68 #include "llvm/IR/PatternMatch.h"
69 #include "llvm/IR/Statepoint.h"
70 #include "llvm/IR/Type.h"
71 #include "llvm/IR/User.h"
72 #include "llvm/IR/Value.h"
73 #include "llvm/InitializePasses.h"
74 #include "llvm/MC/MCContext.h"
75 #include "llvm/Pass.h"
76 #include "llvm/Support/Casting.h"
77 #include "llvm/Support/CodeGen.h"
78 #include "llvm/Support/Debug.h"
79 #include "llvm/Support/ErrorHandling.h"
80 #include "llvm/Support/MathExtras.h"
81 #include "llvm/Support/raw_ostream.h"
82 #include "llvm/Target/TargetIntrinsicInfo.h"
83 #include "llvm/Target/TargetMachine.h"
84 #include "llvm/Transforms/Utils/Local.h"
85 #include "llvm/Transforms/Utils/MemoryOpRemark.h"
86 #include <algorithm>
87 #include <cassert>
88 #include <cstdint>
89 #include <iterator>
90 #include <optional>
91 #include <string>
92 #include <utility>
93 #include <vector>
94 
95 #define DEBUG_TYPE "irtranslator"
96 
97 using namespace llvm;
98 
99 static cl::opt<bool>
100     EnableCSEInIRTranslator("enable-cse-in-irtranslator",
101                             cl::desc("Should enable CSE in irtranslator"),
102                             cl::Optional, cl::init(false));
103 char IRTranslator::ID = 0;
104 
105 INITIALIZE_PASS_BEGIN(IRTranslator, DEBUG_TYPE, "IRTranslator LLVM IR -> MI",
106                 false, false)
107 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
108 INITIALIZE_PASS_DEPENDENCY(GISelCSEAnalysisWrapperPass)
109 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
110 INITIALIZE_PASS_DEPENDENCY(StackProtector)
111 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
112 INITIALIZE_PASS_END(IRTranslator, DEBUG_TYPE, "IRTranslator LLVM IR -> MI",
113                 false, false)
114 
115 static void reportTranslationError(MachineFunction &MF,
116                                    const TargetPassConfig &TPC,
117                                    OptimizationRemarkEmitter &ORE,
118                                    OptimizationRemarkMissed &R) {
119   MF.getProperties().set(MachineFunctionProperties::Property::FailedISel);
120 
121   // Print the function name explicitly if we don't have a debug location (which
122   // makes the diagnostic less useful) or if we're going to emit a raw error.
123   if (!R.getLocation().isValid() || TPC.isGlobalISelAbortEnabled())
124     R << (" (in function: " + MF.getName() + ")").str();
125 
126   if (TPC.isGlobalISelAbortEnabled())
127     report_fatal_error(Twine(R.getMsg()));
128   else
129     ORE.emit(R);
130 }
131 
132 IRTranslator::IRTranslator(CodeGenOptLevel optlevel)
133     : MachineFunctionPass(ID), OptLevel(optlevel) {}
134 
135 #ifndef NDEBUG
136 namespace {
137 /// Verify that every instruction created has the same DILocation as the
138 /// instruction being translated.
139 class DILocationVerifier : public GISelChangeObserver {
140   const Instruction *CurrInst = nullptr;
141 
142 public:
143   DILocationVerifier() = default;
144   ~DILocationVerifier() = default;
145 
146   const Instruction *getCurrentInst() const { return CurrInst; }
147   void setCurrentInst(const Instruction *Inst) { CurrInst = Inst; }
148 
149   void erasingInstr(MachineInstr &MI) override {}
150   void changingInstr(MachineInstr &MI) override {}
151   void changedInstr(MachineInstr &MI) override {}
152 
153   void createdInstr(MachineInstr &MI) override {
154     assert(getCurrentInst() && "Inserted instruction without a current MI");
155 
156     // Only print the check message if we're actually checking it.
157 #ifndef NDEBUG
158     LLVM_DEBUG(dbgs() << "Checking DILocation from " << *CurrInst
159                       << " was copied to " << MI);
160 #endif
161     // We allow insts in the entry block to have no debug loc because
162     // they could have originated from constants, and we don't want a jumpy
163     // debug experience.
164     assert((CurrInst->getDebugLoc() == MI.getDebugLoc() ||
165             (MI.getParent()->isEntryBlock() && !MI.getDebugLoc()) ||
166             (MI.isDebugInstr())) &&
167            "Line info was not transferred to all instructions");
168   }
169 };
170 } // namespace
171 #endif // ifndef NDEBUG
172 
173 
174 void IRTranslator::getAnalysisUsage(AnalysisUsage &AU) const {
175   AU.addRequired<StackProtector>();
176   AU.addRequired<TargetPassConfig>();
177   AU.addRequired<GISelCSEAnalysisWrapperPass>();
178   AU.addRequired<AssumptionCacheTracker>();
179   if (OptLevel != CodeGenOptLevel::None) {
180     AU.addRequired<BranchProbabilityInfoWrapperPass>();
181     AU.addRequired<AAResultsWrapperPass>();
182   }
183   AU.addRequired<TargetLibraryInfoWrapperPass>();
184   AU.addPreserved<TargetLibraryInfoWrapperPass>();
185   getSelectionDAGFallbackAnalysisUsage(AU);
186   MachineFunctionPass::getAnalysisUsage(AU);
187 }
188 
189 IRTranslator::ValueToVRegInfo::VRegListT &
190 IRTranslator::allocateVRegs(const Value &Val) {
191   auto VRegsIt = VMap.findVRegs(Val);
192   if (VRegsIt != VMap.vregs_end())
193     return *VRegsIt->second;
194   auto *Regs = VMap.getVRegs(Val);
195   auto *Offsets = VMap.getOffsets(Val);
196   SmallVector<LLT, 4> SplitTys;
197   computeValueLLTs(*DL, *Val.getType(), SplitTys,
198                    Offsets->empty() ? Offsets : nullptr);
199   for (unsigned i = 0; i < SplitTys.size(); ++i)
200     Regs->push_back(0);
201   return *Regs;
202 }
203 
204 ArrayRef<Register> IRTranslator::getOrCreateVRegs(const Value &Val) {
205   auto VRegsIt = VMap.findVRegs(Val);
206   if (VRegsIt != VMap.vregs_end())
207     return *VRegsIt->second;
208 
209   if (Val.getType()->isVoidTy())
210     return *VMap.getVRegs(Val);
211 
212   // Create entry for this type.
213   auto *VRegs = VMap.getVRegs(Val);
214   auto *Offsets = VMap.getOffsets(Val);
215 
216   if (!Val.getType()->isTokenTy())
217     assert(Val.getType()->isSized() &&
218            "Don't know how to create an empty vreg");
219 
220   SmallVector<LLT, 4> SplitTys;
221   computeValueLLTs(*DL, *Val.getType(), SplitTys,
222                    Offsets->empty() ? Offsets : nullptr);
223 
224   if (!isa<Constant>(Val)) {
225     for (auto Ty : SplitTys)
226       VRegs->push_back(MRI->createGenericVirtualRegister(Ty));
227     return *VRegs;
228   }
229 
230   if (Val.getType()->isAggregateType()) {
231     // UndefValue, ConstantAggregateZero
232     auto &C = cast<Constant>(Val);
233     unsigned Idx = 0;
234     while (auto Elt = C.getAggregateElement(Idx++)) {
235       auto EltRegs = getOrCreateVRegs(*Elt);
236       llvm::copy(EltRegs, std::back_inserter(*VRegs));
237     }
238   } else {
239     assert(SplitTys.size() == 1 && "unexpectedly split LLT");
240     VRegs->push_back(MRI->createGenericVirtualRegister(SplitTys[0]));
241     bool Success = translate(cast<Constant>(Val), VRegs->front());
242     if (!Success) {
243       OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure",
244                                  MF->getFunction().getSubprogram(),
245                                  &MF->getFunction().getEntryBlock());
246       R << "unable to translate constant: " << ore::NV("Type", Val.getType());
247       reportTranslationError(*MF, *TPC, *ORE, R);
248       return *VRegs;
249     }
250   }
251 
252   return *VRegs;
253 }
254 
255 int IRTranslator::getOrCreateFrameIndex(const AllocaInst &AI) {
256   auto MapEntry = FrameIndices.find(&AI);
257   if (MapEntry != FrameIndices.end())
258     return MapEntry->second;
259 
260   uint64_t ElementSize = DL->getTypeAllocSize(AI.getAllocatedType());
261   uint64_t Size =
262       ElementSize * cast<ConstantInt>(AI.getArraySize())->getZExtValue();
263 
264   // Always allocate at least one byte.
265   Size = std::max<uint64_t>(Size, 1u);
266 
267   int &FI = FrameIndices[&AI];
268   FI = MF->getFrameInfo().CreateStackObject(Size, AI.getAlign(), false, &AI);
269   return FI;
270 }
271 
272 Align IRTranslator::getMemOpAlign(const Instruction &I) {
273   if (const StoreInst *SI = dyn_cast<StoreInst>(&I))
274     return SI->getAlign();
275   if (const LoadInst *LI = dyn_cast<LoadInst>(&I))
276     return LI->getAlign();
277   if (const AtomicCmpXchgInst *AI = dyn_cast<AtomicCmpXchgInst>(&I))
278     return AI->getAlign();
279   if (const AtomicRMWInst *AI = dyn_cast<AtomicRMWInst>(&I))
280     return AI->getAlign();
281 
282   OptimizationRemarkMissed R("gisel-irtranslator", "", &I);
283   R << "unable to translate memop: " << ore::NV("Opcode", &I);
284   reportTranslationError(*MF, *TPC, *ORE, R);
285   return Align(1);
286 }
287 
288 MachineBasicBlock &IRTranslator::getMBB(const BasicBlock &BB) {
289   MachineBasicBlock *MBB = FuncInfo.getMBB(&BB);
290   assert(MBB && "BasicBlock was not encountered before");
291   return *MBB;
292 }
293 
294 void IRTranslator::addMachineCFGPred(CFGEdge Edge, MachineBasicBlock *NewPred) {
295   assert(NewPred && "new predecessor must be a real MachineBasicBlock");
296   MachinePreds[Edge].push_back(NewPred);
297 }
298 
299 bool IRTranslator::translateBinaryOp(unsigned Opcode, const User &U,
300                                      MachineIRBuilder &MIRBuilder) {
301   // Get or create a virtual register for each value.
302   // Unless the value is a Constant => loadimm cst?
303   // or inline constant each time?
304   // Creation of a virtual register needs to have a size.
305   Register Op0 = getOrCreateVReg(*U.getOperand(0));
306   Register Op1 = getOrCreateVReg(*U.getOperand(1));
307   Register Res = getOrCreateVReg(U);
308   uint32_t Flags = 0;
309   if (isa<Instruction>(U)) {
310     const Instruction &I = cast<Instruction>(U);
311     Flags = MachineInstr::copyFlagsFromInstruction(I);
312   }
313 
314   MIRBuilder.buildInstr(Opcode, {Res}, {Op0, Op1}, Flags);
315   return true;
316 }
317 
318 bool IRTranslator::translateUnaryOp(unsigned Opcode, const User &U,
319                                     MachineIRBuilder &MIRBuilder) {
320   Register Op0 = getOrCreateVReg(*U.getOperand(0));
321   Register Res = getOrCreateVReg(U);
322   uint32_t Flags = 0;
323   if (isa<Instruction>(U)) {
324     const Instruction &I = cast<Instruction>(U);
325     Flags = MachineInstr::copyFlagsFromInstruction(I);
326   }
327   MIRBuilder.buildInstr(Opcode, {Res}, {Op0}, Flags);
328   return true;
329 }
330 
331 bool IRTranslator::translateFNeg(const User &U, MachineIRBuilder &MIRBuilder) {
332   return translateUnaryOp(TargetOpcode::G_FNEG, U, MIRBuilder);
333 }
334 
335 bool IRTranslator::translateCompare(const User &U,
336                                     MachineIRBuilder &MIRBuilder) {
337   auto *CI = cast<CmpInst>(&U);
338   Register Op0 = getOrCreateVReg(*U.getOperand(0));
339   Register Op1 = getOrCreateVReg(*U.getOperand(1));
340   Register Res = getOrCreateVReg(U);
341   CmpInst::Predicate Pred = CI->getPredicate();
342   uint32_t Flags = MachineInstr::copyFlagsFromInstruction(*CI);
343   if (CmpInst::isIntPredicate(Pred))
344     MIRBuilder.buildICmp(Pred, Res, Op0, Op1, Flags);
345   else if (Pred == CmpInst::FCMP_FALSE)
346     MIRBuilder.buildCopy(
347         Res, getOrCreateVReg(*Constant::getNullValue(U.getType())));
348   else if (Pred == CmpInst::FCMP_TRUE)
349     MIRBuilder.buildCopy(
350         Res, getOrCreateVReg(*Constant::getAllOnesValue(U.getType())));
351   else
352     MIRBuilder.buildFCmp(Pred, Res, Op0, Op1, Flags);
353 
354   return true;
355 }
356 
357 bool IRTranslator::translateRet(const User &U, MachineIRBuilder &MIRBuilder) {
358   const ReturnInst &RI = cast<ReturnInst>(U);
359   const Value *Ret = RI.getReturnValue();
360   if (Ret && DL->getTypeStoreSize(Ret->getType()).isZero())
361     Ret = nullptr;
362 
363   ArrayRef<Register> VRegs;
364   if (Ret)
365     VRegs = getOrCreateVRegs(*Ret);
366 
367   Register SwiftErrorVReg = 0;
368   if (CLI->supportSwiftError() && SwiftError.getFunctionArg()) {
369     SwiftErrorVReg = SwiftError.getOrCreateVRegUseAt(
370         &RI, &MIRBuilder.getMBB(), SwiftError.getFunctionArg());
371   }
372 
373   // The target may mess up with the insertion point, but
374   // this is not important as a return is the last instruction
375   // of the block anyway.
376   return CLI->lowerReturn(MIRBuilder, Ret, VRegs, FuncInfo, SwiftErrorVReg);
377 }
378 
379 void IRTranslator::emitBranchForMergedCondition(
380     const Value *Cond, MachineBasicBlock *TBB, MachineBasicBlock *FBB,
381     MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB,
382     BranchProbability TProb, BranchProbability FProb, bool InvertCond) {
383   // If the leaf of the tree is a comparison, merge the condition into
384   // the caseblock.
385   if (const CmpInst *BOp = dyn_cast<CmpInst>(Cond)) {
386     CmpInst::Predicate Condition;
387     if (const ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) {
388       Condition = InvertCond ? IC->getInversePredicate() : IC->getPredicate();
389     } else {
390       const FCmpInst *FC = cast<FCmpInst>(Cond);
391       Condition = InvertCond ? FC->getInversePredicate() : FC->getPredicate();
392     }
393 
394     SwitchCG::CaseBlock CB(Condition, false, BOp->getOperand(0),
395                            BOp->getOperand(1), nullptr, TBB, FBB, CurBB,
396                            CurBuilder->getDebugLoc(), TProb, FProb);
397     SL->SwitchCases.push_back(CB);
398     return;
399   }
400 
401   // Create a CaseBlock record representing this branch.
402   CmpInst::Predicate Pred = InvertCond ? CmpInst::ICMP_NE : CmpInst::ICMP_EQ;
403   SwitchCG::CaseBlock CB(
404       Pred, false, Cond, ConstantInt::getTrue(MF->getFunction().getContext()),
405       nullptr, TBB, FBB, CurBB, CurBuilder->getDebugLoc(), TProb, FProb);
406   SL->SwitchCases.push_back(CB);
407 }
408 
409 static bool isValInBlock(const Value *V, const BasicBlock *BB) {
410   if (const Instruction *I = dyn_cast<Instruction>(V))
411     return I->getParent() == BB;
412   return true;
413 }
414 
415 void IRTranslator::findMergedConditions(
416     const Value *Cond, MachineBasicBlock *TBB, MachineBasicBlock *FBB,
417     MachineBasicBlock *CurBB, MachineBasicBlock *SwitchBB,
418     Instruction::BinaryOps Opc, BranchProbability TProb,
419     BranchProbability FProb, bool InvertCond) {
420   using namespace PatternMatch;
421   assert((Opc == Instruction::And || Opc == Instruction::Or) &&
422          "Expected Opc to be AND/OR");
423   // Skip over not part of the tree and remember to invert op and operands at
424   // next level.
425   Value *NotCond;
426   if (match(Cond, m_OneUse(m_Not(m_Value(NotCond)))) &&
427       isValInBlock(NotCond, CurBB->getBasicBlock())) {
428     findMergedConditions(NotCond, TBB, FBB, CurBB, SwitchBB, Opc, TProb, FProb,
429                          !InvertCond);
430     return;
431   }
432 
433   const Instruction *BOp = dyn_cast<Instruction>(Cond);
434   const Value *BOpOp0, *BOpOp1;
435   // Compute the effective opcode for Cond, taking into account whether it needs
436   // to be inverted, e.g.
437   //   and (not (or A, B)), C
438   // gets lowered as
439   //   and (and (not A, not B), C)
440   Instruction::BinaryOps BOpc = (Instruction::BinaryOps)0;
441   if (BOp) {
442     BOpc = match(BOp, m_LogicalAnd(m_Value(BOpOp0), m_Value(BOpOp1)))
443                ? Instruction::And
444                : (match(BOp, m_LogicalOr(m_Value(BOpOp0), m_Value(BOpOp1)))
445                       ? Instruction::Or
446                       : (Instruction::BinaryOps)0);
447     if (InvertCond) {
448       if (BOpc == Instruction::And)
449         BOpc = Instruction::Or;
450       else if (BOpc == Instruction::Or)
451         BOpc = Instruction::And;
452     }
453   }
454 
455   // If this node is not part of the or/and tree, emit it as a branch.
456   // Note that all nodes in the tree should have same opcode.
457   bool BOpIsInOrAndTree = BOpc && BOpc == Opc && BOp->hasOneUse();
458   if (!BOpIsInOrAndTree || BOp->getParent() != CurBB->getBasicBlock() ||
459       !isValInBlock(BOpOp0, CurBB->getBasicBlock()) ||
460       !isValInBlock(BOpOp1, CurBB->getBasicBlock())) {
461     emitBranchForMergedCondition(Cond, TBB, FBB, CurBB, SwitchBB, TProb, FProb,
462                                  InvertCond);
463     return;
464   }
465 
466   //  Create TmpBB after CurBB.
467   MachineFunction::iterator BBI(CurBB);
468   MachineBasicBlock *TmpBB =
469       MF->CreateMachineBasicBlock(CurBB->getBasicBlock());
470   CurBB->getParent()->insert(++BBI, TmpBB);
471 
472   if (Opc == Instruction::Or) {
473     // Codegen X | Y as:
474     // BB1:
475     //   jmp_if_X TBB
476     //   jmp TmpBB
477     // TmpBB:
478     //   jmp_if_Y TBB
479     //   jmp FBB
480     //
481 
482     // We have flexibility in setting Prob for BB1 and Prob for TmpBB.
483     // The requirement is that
484     //   TrueProb for BB1 + (FalseProb for BB1 * TrueProb for TmpBB)
485     //     = TrueProb for original BB.
486     // Assuming the original probabilities are A and B, one choice is to set
487     // BB1's probabilities to A/2 and A/2+B, and set TmpBB's probabilities to
488     // A/(1+B) and 2B/(1+B). This choice assumes that
489     //   TrueProb for BB1 == FalseProb for BB1 * TrueProb for TmpBB.
490     // Another choice is to assume TrueProb for BB1 equals to TrueProb for
491     // TmpBB, but the math is more complicated.
492 
493     auto NewTrueProb = TProb / 2;
494     auto NewFalseProb = TProb / 2 + FProb;
495     // Emit the LHS condition.
496     findMergedConditions(BOpOp0, TBB, TmpBB, CurBB, SwitchBB, Opc, NewTrueProb,
497                          NewFalseProb, InvertCond);
498 
499     // Normalize A/2 and B to get A/(1+B) and 2B/(1+B).
500     SmallVector<BranchProbability, 2> Probs{TProb / 2, FProb};
501     BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
502     // Emit the RHS condition into TmpBB.
503     findMergedConditions(BOpOp1, TBB, FBB, TmpBB, SwitchBB, Opc, Probs[0],
504                          Probs[1], InvertCond);
505   } else {
506     assert(Opc == Instruction::And && "Unknown merge op!");
507     // Codegen X & Y as:
508     // BB1:
509     //   jmp_if_X TmpBB
510     //   jmp FBB
511     // TmpBB:
512     //   jmp_if_Y TBB
513     //   jmp FBB
514     //
515     //  This requires creation of TmpBB after CurBB.
516 
517     // We have flexibility in setting Prob for BB1 and Prob for TmpBB.
518     // The requirement is that
519     //   FalseProb for BB1 + (TrueProb for BB1 * FalseProb for TmpBB)
520     //     = FalseProb for original BB.
521     // Assuming the original probabilities are A and B, one choice is to set
522     // BB1's probabilities to A+B/2 and B/2, and set TmpBB's probabilities to
523     // 2A/(1+A) and B/(1+A). This choice assumes that FalseProb for BB1 ==
524     // TrueProb for BB1 * FalseProb for TmpBB.
525 
526     auto NewTrueProb = TProb + FProb / 2;
527     auto NewFalseProb = FProb / 2;
528     // Emit the LHS condition.
529     findMergedConditions(BOpOp0, TmpBB, FBB, CurBB, SwitchBB, Opc, NewTrueProb,
530                          NewFalseProb, InvertCond);
531 
532     // Normalize A and B/2 to get 2A/(1+A) and B/(1+A).
533     SmallVector<BranchProbability, 2> Probs{TProb, FProb / 2};
534     BranchProbability::normalizeProbabilities(Probs.begin(), Probs.end());
535     // Emit the RHS condition into TmpBB.
536     findMergedConditions(BOpOp1, TBB, FBB, TmpBB, SwitchBB, Opc, Probs[0],
537                          Probs[1], InvertCond);
538   }
539 }
540 
541 bool IRTranslator::shouldEmitAsBranches(
542     const std::vector<SwitchCG::CaseBlock> &Cases) {
543   // For multiple cases, it's better to emit as branches.
544   if (Cases.size() != 2)
545     return true;
546 
547   // If this is two comparisons of the same values or'd or and'd together, they
548   // will get folded into a single comparison, so don't emit two blocks.
549   if ((Cases[0].CmpLHS == Cases[1].CmpLHS &&
550        Cases[0].CmpRHS == Cases[1].CmpRHS) ||
551       (Cases[0].CmpRHS == Cases[1].CmpLHS &&
552        Cases[0].CmpLHS == Cases[1].CmpRHS)) {
553     return false;
554   }
555 
556   // Handle: (X != null) | (Y != null) --> (X|Y) != 0
557   // Handle: (X == null) & (Y == null) --> (X|Y) == 0
558   if (Cases[0].CmpRHS == Cases[1].CmpRHS &&
559       Cases[0].PredInfo.Pred == Cases[1].PredInfo.Pred &&
560       isa<Constant>(Cases[0].CmpRHS) &&
561       cast<Constant>(Cases[0].CmpRHS)->isNullValue()) {
562     if (Cases[0].PredInfo.Pred == CmpInst::ICMP_EQ &&
563         Cases[0].TrueBB == Cases[1].ThisBB)
564       return false;
565     if (Cases[0].PredInfo.Pred == CmpInst::ICMP_NE &&
566         Cases[0].FalseBB == Cases[1].ThisBB)
567       return false;
568   }
569 
570   return true;
571 }
572 
573 bool IRTranslator::translateBr(const User &U, MachineIRBuilder &MIRBuilder) {
574   const BranchInst &BrInst = cast<BranchInst>(U);
575   auto &CurMBB = MIRBuilder.getMBB();
576   auto *Succ0MBB = &getMBB(*BrInst.getSuccessor(0));
577 
578   if (BrInst.isUnconditional()) {
579     // If the unconditional target is the layout successor, fallthrough.
580     if (OptLevel == CodeGenOptLevel::None ||
581         !CurMBB.isLayoutSuccessor(Succ0MBB))
582       MIRBuilder.buildBr(*Succ0MBB);
583 
584     // Link successors.
585     for (const BasicBlock *Succ : successors(&BrInst))
586       CurMBB.addSuccessor(&getMBB(*Succ));
587     return true;
588   }
589 
590   // If this condition is one of the special cases we handle, do special stuff
591   // now.
592   const Value *CondVal = BrInst.getCondition();
593   MachineBasicBlock *Succ1MBB = &getMBB(*BrInst.getSuccessor(1));
594 
595   // If this is a series of conditions that are or'd or and'd together, emit
596   // this as a sequence of branches instead of setcc's with and/or operations.
597   // As long as jumps are not expensive (exceptions for multi-use logic ops,
598   // unpredictable branches, and vector extracts because those jumps are likely
599   // expensive for any target), this should improve performance.
600   // For example, instead of something like:
601   //     cmp A, B
602   //     C = seteq
603   //     cmp D, E
604   //     F = setle
605   //     or C, F
606   //     jnz foo
607   // Emit:
608   //     cmp A, B
609   //     je foo
610   //     cmp D, E
611   //     jle foo
612   using namespace PatternMatch;
613   const Instruction *CondI = dyn_cast<Instruction>(CondVal);
614   if (!TLI->isJumpExpensive() && CondI && CondI->hasOneUse() &&
615       !BrInst.hasMetadata(LLVMContext::MD_unpredictable)) {
616     Instruction::BinaryOps Opcode = (Instruction::BinaryOps)0;
617     Value *Vec;
618     const Value *BOp0, *BOp1;
619     if (match(CondI, m_LogicalAnd(m_Value(BOp0), m_Value(BOp1))))
620       Opcode = Instruction::And;
621     else if (match(CondI, m_LogicalOr(m_Value(BOp0), m_Value(BOp1))))
622       Opcode = Instruction::Or;
623 
624     if (Opcode && !(match(BOp0, m_ExtractElt(m_Value(Vec), m_Value())) &&
625                     match(BOp1, m_ExtractElt(m_Specific(Vec), m_Value())))) {
626       findMergedConditions(CondI, Succ0MBB, Succ1MBB, &CurMBB, &CurMBB, Opcode,
627                            getEdgeProbability(&CurMBB, Succ0MBB),
628                            getEdgeProbability(&CurMBB, Succ1MBB),
629                            /*InvertCond=*/false);
630       assert(SL->SwitchCases[0].ThisBB == &CurMBB && "Unexpected lowering!");
631 
632       // Allow some cases to be rejected.
633       if (shouldEmitAsBranches(SL->SwitchCases)) {
634         // Emit the branch for this block.
635         emitSwitchCase(SL->SwitchCases[0], &CurMBB, *CurBuilder);
636         SL->SwitchCases.erase(SL->SwitchCases.begin());
637         return true;
638       }
639 
640       // Okay, we decided not to do this, remove any inserted MBB's and clear
641       // SwitchCases.
642       for (unsigned I = 1, E = SL->SwitchCases.size(); I != E; ++I)
643         MF->erase(SL->SwitchCases[I].ThisBB);
644 
645       SL->SwitchCases.clear();
646     }
647   }
648 
649   // Create a CaseBlock record representing this branch.
650   SwitchCG::CaseBlock CB(CmpInst::ICMP_EQ, false, CondVal,
651                          ConstantInt::getTrue(MF->getFunction().getContext()),
652                          nullptr, Succ0MBB, Succ1MBB, &CurMBB,
653                          CurBuilder->getDebugLoc());
654 
655   // Use emitSwitchCase to actually insert the fast branch sequence for this
656   // cond branch.
657   emitSwitchCase(CB, &CurMBB, *CurBuilder);
658   return true;
659 }
660 
661 void IRTranslator::addSuccessorWithProb(MachineBasicBlock *Src,
662                                         MachineBasicBlock *Dst,
663                                         BranchProbability Prob) {
664   if (!FuncInfo.BPI) {
665     Src->addSuccessorWithoutProb(Dst);
666     return;
667   }
668   if (Prob.isUnknown())
669     Prob = getEdgeProbability(Src, Dst);
670   Src->addSuccessor(Dst, Prob);
671 }
672 
673 BranchProbability
674 IRTranslator::getEdgeProbability(const MachineBasicBlock *Src,
675                                  const MachineBasicBlock *Dst) const {
676   const BasicBlock *SrcBB = Src->getBasicBlock();
677   const BasicBlock *DstBB = Dst->getBasicBlock();
678   if (!FuncInfo.BPI) {
679     // If BPI is not available, set the default probability as 1 / N, where N is
680     // the number of successors.
681     auto SuccSize = std::max<uint32_t>(succ_size(SrcBB), 1);
682     return BranchProbability(1, SuccSize);
683   }
684   return FuncInfo.BPI->getEdgeProbability(SrcBB, DstBB);
685 }
686 
687 bool IRTranslator::translateSwitch(const User &U, MachineIRBuilder &MIB) {
688   using namespace SwitchCG;
689   // Extract cases from the switch.
690   const SwitchInst &SI = cast<SwitchInst>(U);
691   BranchProbabilityInfo *BPI = FuncInfo.BPI;
692   CaseClusterVector Clusters;
693   Clusters.reserve(SI.getNumCases());
694   for (const auto &I : SI.cases()) {
695     MachineBasicBlock *Succ = &getMBB(*I.getCaseSuccessor());
696     assert(Succ && "Could not find successor mbb in mapping");
697     const ConstantInt *CaseVal = I.getCaseValue();
698     BranchProbability Prob =
699         BPI ? BPI->getEdgeProbability(SI.getParent(), I.getSuccessorIndex())
700             : BranchProbability(1, SI.getNumCases() + 1);
701     Clusters.push_back(CaseCluster::range(CaseVal, CaseVal, Succ, Prob));
702   }
703 
704   MachineBasicBlock *DefaultMBB = &getMBB(*SI.getDefaultDest());
705 
706   // Cluster adjacent cases with the same destination. We do this at all
707   // optimization levels because it's cheap to do and will make codegen faster
708   // if there are many clusters.
709   sortAndRangeify(Clusters);
710 
711   MachineBasicBlock *SwitchMBB = &getMBB(*SI.getParent());
712 
713   // If there is only the default destination, jump there directly.
714   if (Clusters.empty()) {
715     SwitchMBB->addSuccessor(DefaultMBB);
716     if (DefaultMBB != SwitchMBB->getNextNode())
717       MIB.buildBr(*DefaultMBB);
718     return true;
719   }
720 
721   SL->findJumpTables(Clusters, &SI, std::nullopt, DefaultMBB, nullptr, nullptr);
722   SL->findBitTestClusters(Clusters, &SI);
723 
724   LLVM_DEBUG({
725     dbgs() << "Case clusters: ";
726     for (const CaseCluster &C : Clusters) {
727       if (C.Kind == CC_JumpTable)
728         dbgs() << "JT:";
729       if (C.Kind == CC_BitTests)
730         dbgs() << "BT:";
731 
732       C.Low->getValue().print(dbgs(), true);
733       if (C.Low != C.High) {
734         dbgs() << '-';
735         C.High->getValue().print(dbgs(), true);
736       }
737       dbgs() << ' ';
738     }
739     dbgs() << '\n';
740   });
741 
742   assert(!Clusters.empty());
743   SwitchWorkList WorkList;
744   CaseClusterIt First = Clusters.begin();
745   CaseClusterIt Last = Clusters.end() - 1;
746   auto DefaultProb = getEdgeProbability(SwitchMBB, DefaultMBB);
747   WorkList.push_back({SwitchMBB, First, Last, nullptr, nullptr, DefaultProb});
748 
749   while (!WorkList.empty()) {
750     SwitchWorkListItem W = WorkList.pop_back_val();
751 
752     unsigned NumClusters = W.LastCluster - W.FirstCluster + 1;
753     // For optimized builds, lower large range as a balanced binary tree.
754     if (NumClusters > 3 &&
755         MF->getTarget().getOptLevel() != CodeGenOptLevel::None &&
756         !DefaultMBB->getParent()->getFunction().hasMinSize()) {
757       splitWorkItem(WorkList, W, SI.getCondition(), SwitchMBB, MIB);
758       continue;
759     }
760 
761     if (!lowerSwitchWorkItem(W, SI.getCondition(), SwitchMBB, DefaultMBB, MIB))
762       return false;
763   }
764   return true;
765 }
766 
767 void IRTranslator::splitWorkItem(SwitchCG::SwitchWorkList &WorkList,
768                                  const SwitchCG::SwitchWorkListItem &W,
769                                  Value *Cond, MachineBasicBlock *SwitchMBB,
770                                  MachineIRBuilder &MIB) {
771   using namespace SwitchCG;
772   assert(W.FirstCluster->Low->getValue().slt(W.LastCluster->Low->getValue()) &&
773          "Clusters not sorted?");
774   assert(W.LastCluster - W.FirstCluster + 1 >= 2 && "Too small to split!");
775 
776   auto [LastLeft, FirstRight, LeftProb, RightProb] =
777       SL->computeSplitWorkItemInfo(W);
778 
779   // Use the first element on the right as pivot since we will make less-than
780   // comparisons against it.
781   CaseClusterIt PivotCluster = FirstRight;
782   assert(PivotCluster > W.FirstCluster);
783   assert(PivotCluster <= W.LastCluster);
784 
785   CaseClusterIt FirstLeft = W.FirstCluster;
786   CaseClusterIt LastRight = W.LastCluster;
787 
788   const ConstantInt *Pivot = PivotCluster->Low;
789 
790   // New blocks will be inserted immediately after the current one.
791   MachineFunction::iterator BBI(W.MBB);
792   ++BBI;
793 
794   // We will branch to the LHS if Value < Pivot. If LHS is a single cluster,
795   // we can branch to its destination directly if it's squeezed exactly in
796   // between the known lower bound and Pivot - 1.
797   MachineBasicBlock *LeftMBB;
798   if (FirstLeft == LastLeft && FirstLeft->Kind == CC_Range &&
799       FirstLeft->Low == W.GE &&
800       (FirstLeft->High->getValue() + 1LL) == Pivot->getValue()) {
801     LeftMBB = FirstLeft->MBB;
802   } else {
803     LeftMBB = FuncInfo.MF->CreateMachineBasicBlock(W.MBB->getBasicBlock());
804     FuncInfo.MF->insert(BBI, LeftMBB);
805     WorkList.push_back(
806         {LeftMBB, FirstLeft, LastLeft, W.GE, Pivot, W.DefaultProb / 2});
807   }
808 
809   // Similarly, we will branch to the RHS if Value >= Pivot. If RHS is a
810   // single cluster, RHS.Low == Pivot, and we can branch to its destination
811   // directly if RHS.High equals the current upper bound.
812   MachineBasicBlock *RightMBB;
813   if (FirstRight == LastRight && FirstRight->Kind == CC_Range && W.LT &&
814       (FirstRight->High->getValue() + 1ULL) == W.LT->getValue()) {
815     RightMBB = FirstRight->MBB;
816   } else {
817     RightMBB = FuncInfo.MF->CreateMachineBasicBlock(W.MBB->getBasicBlock());
818     FuncInfo.MF->insert(BBI, RightMBB);
819     WorkList.push_back(
820         {RightMBB, FirstRight, LastRight, Pivot, W.LT, W.DefaultProb / 2});
821   }
822 
823   // Create the CaseBlock record that will be used to lower the branch.
824   CaseBlock CB(ICmpInst::Predicate::ICMP_SLT, false, Cond, Pivot, nullptr,
825                LeftMBB, RightMBB, W.MBB, MIB.getDebugLoc(), LeftProb,
826                RightProb);
827 
828   if (W.MBB == SwitchMBB)
829     emitSwitchCase(CB, SwitchMBB, MIB);
830   else
831     SL->SwitchCases.push_back(CB);
832 }
833 
834 void IRTranslator::emitJumpTable(SwitchCG::JumpTable &JT,
835                                  MachineBasicBlock *MBB) {
836   // Emit the code for the jump table
837   assert(JT.Reg && "Should lower JT Header first!");
838   MachineIRBuilder MIB(*MBB->getParent());
839   MIB.setMBB(*MBB);
840   MIB.setDebugLoc(CurBuilder->getDebugLoc());
841 
842   Type *PtrIRTy = PointerType::getUnqual(MF->getFunction().getContext());
843   const LLT PtrTy = getLLTForType(*PtrIRTy, *DL);
844 
845   auto Table = MIB.buildJumpTable(PtrTy, JT.JTI);
846   MIB.buildBrJT(Table.getReg(0), JT.JTI, JT.Reg);
847 }
848 
849 bool IRTranslator::emitJumpTableHeader(SwitchCG::JumpTable &JT,
850                                        SwitchCG::JumpTableHeader &JTH,
851                                        MachineBasicBlock *HeaderBB) {
852   MachineIRBuilder MIB(*HeaderBB->getParent());
853   MIB.setMBB(*HeaderBB);
854   MIB.setDebugLoc(CurBuilder->getDebugLoc());
855 
856   const Value &SValue = *JTH.SValue;
857   // Subtract the lowest switch case value from the value being switched on.
858   const LLT SwitchTy = getLLTForType(*SValue.getType(), *DL);
859   Register SwitchOpReg = getOrCreateVReg(SValue);
860   auto FirstCst = MIB.buildConstant(SwitchTy, JTH.First);
861   auto Sub = MIB.buildSub({SwitchTy}, SwitchOpReg, FirstCst);
862 
863   // This value may be smaller or larger than the target's pointer type, and
864   // therefore require extension or truncating.
865   auto *PtrIRTy = PointerType::getUnqual(SValue.getContext());
866   const LLT PtrScalarTy = LLT::scalar(DL->getTypeSizeInBits(PtrIRTy));
867   Sub = MIB.buildZExtOrTrunc(PtrScalarTy, Sub);
868 
869   JT.Reg = Sub.getReg(0);
870 
871   if (JTH.FallthroughUnreachable) {
872     if (JT.MBB != HeaderBB->getNextNode())
873       MIB.buildBr(*JT.MBB);
874     return true;
875   }
876 
877   // Emit the range check for the jump table, and branch to the default block
878   // for the switch statement if the value being switched on exceeds the
879   // largest case in the switch.
880   auto Cst = getOrCreateVReg(
881       *ConstantInt::get(SValue.getType(), JTH.Last - JTH.First));
882   Cst = MIB.buildZExtOrTrunc(PtrScalarTy, Cst).getReg(0);
883   auto Cmp = MIB.buildICmp(CmpInst::ICMP_UGT, LLT::scalar(1), Sub, Cst);
884 
885   auto BrCond = MIB.buildBrCond(Cmp.getReg(0), *JT.Default);
886 
887   // Avoid emitting unnecessary branches to the next block.
888   if (JT.MBB != HeaderBB->getNextNode())
889     BrCond = MIB.buildBr(*JT.MBB);
890   return true;
891 }
892 
893 void IRTranslator::emitSwitchCase(SwitchCG::CaseBlock &CB,
894                                   MachineBasicBlock *SwitchBB,
895                                   MachineIRBuilder &MIB) {
896   Register CondLHS = getOrCreateVReg(*CB.CmpLHS);
897   Register Cond;
898   DebugLoc OldDbgLoc = MIB.getDebugLoc();
899   MIB.setDebugLoc(CB.DbgLoc);
900   MIB.setMBB(*CB.ThisBB);
901 
902   if (CB.PredInfo.NoCmp) {
903     // Branch or fall through to TrueBB.
904     addSuccessorWithProb(CB.ThisBB, CB.TrueBB, CB.TrueProb);
905     addMachineCFGPred({SwitchBB->getBasicBlock(), CB.TrueBB->getBasicBlock()},
906                       CB.ThisBB);
907     CB.ThisBB->normalizeSuccProbs();
908     if (CB.TrueBB != CB.ThisBB->getNextNode())
909       MIB.buildBr(*CB.TrueBB);
910     MIB.setDebugLoc(OldDbgLoc);
911     return;
912   }
913 
914   const LLT i1Ty = LLT::scalar(1);
915   // Build the compare.
916   if (!CB.CmpMHS) {
917     const auto *CI = dyn_cast<ConstantInt>(CB.CmpRHS);
918     // For conditional branch lowering, we might try to do something silly like
919     // emit an G_ICMP to compare an existing G_ICMP i1 result with true. If so,
920     // just re-use the existing condition vreg.
921     if (MRI->getType(CondLHS).getSizeInBits() == 1 && CI && CI->isOne() &&
922         CB.PredInfo.Pred == CmpInst::ICMP_EQ) {
923       Cond = CondLHS;
924     } else {
925       Register CondRHS = getOrCreateVReg(*CB.CmpRHS);
926       if (CmpInst::isFPPredicate(CB.PredInfo.Pred))
927         Cond =
928             MIB.buildFCmp(CB.PredInfo.Pred, i1Ty, CondLHS, CondRHS).getReg(0);
929       else
930         Cond =
931             MIB.buildICmp(CB.PredInfo.Pred, i1Ty, CondLHS, CondRHS).getReg(0);
932     }
933   } else {
934     assert(CB.PredInfo.Pred == CmpInst::ICMP_SLE &&
935            "Can only handle SLE ranges");
936 
937     const APInt& Low = cast<ConstantInt>(CB.CmpLHS)->getValue();
938     const APInt& High = cast<ConstantInt>(CB.CmpRHS)->getValue();
939 
940     Register CmpOpReg = getOrCreateVReg(*CB.CmpMHS);
941     if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(true)) {
942       Register CondRHS = getOrCreateVReg(*CB.CmpRHS);
943       Cond =
944           MIB.buildICmp(CmpInst::ICMP_SLE, i1Ty, CmpOpReg, CondRHS).getReg(0);
945     } else {
946       const LLT CmpTy = MRI->getType(CmpOpReg);
947       auto Sub = MIB.buildSub({CmpTy}, CmpOpReg, CondLHS);
948       auto Diff = MIB.buildConstant(CmpTy, High - Low);
949       Cond = MIB.buildICmp(CmpInst::ICMP_ULE, i1Ty, Sub, Diff).getReg(0);
950     }
951   }
952 
953   // Update successor info
954   addSuccessorWithProb(CB.ThisBB, CB.TrueBB, CB.TrueProb);
955 
956   addMachineCFGPred({SwitchBB->getBasicBlock(), CB.TrueBB->getBasicBlock()},
957                     CB.ThisBB);
958 
959   // TrueBB and FalseBB are always different unless the incoming IR is
960   // degenerate. This only happens when running llc on weird IR.
961   if (CB.TrueBB != CB.FalseBB)
962     addSuccessorWithProb(CB.ThisBB, CB.FalseBB, CB.FalseProb);
963   CB.ThisBB->normalizeSuccProbs();
964 
965   addMachineCFGPred({SwitchBB->getBasicBlock(), CB.FalseBB->getBasicBlock()},
966                     CB.ThisBB);
967 
968   MIB.buildBrCond(Cond, *CB.TrueBB);
969   MIB.buildBr(*CB.FalseBB);
970   MIB.setDebugLoc(OldDbgLoc);
971 }
972 
973 bool IRTranslator::lowerJumpTableWorkItem(SwitchCG::SwitchWorkListItem W,
974                                           MachineBasicBlock *SwitchMBB,
975                                           MachineBasicBlock *CurMBB,
976                                           MachineBasicBlock *DefaultMBB,
977                                           MachineIRBuilder &MIB,
978                                           MachineFunction::iterator BBI,
979                                           BranchProbability UnhandledProbs,
980                                           SwitchCG::CaseClusterIt I,
981                                           MachineBasicBlock *Fallthrough,
982                                           bool FallthroughUnreachable) {
983   using namespace SwitchCG;
984   MachineFunction *CurMF = SwitchMBB->getParent();
985   // FIXME: Optimize away range check based on pivot comparisons.
986   JumpTableHeader *JTH = &SL->JTCases[I->JTCasesIndex].first;
987   SwitchCG::JumpTable *JT = &SL->JTCases[I->JTCasesIndex].second;
988   BranchProbability DefaultProb = W.DefaultProb;
989 
990   // The jump block hasn't been inserted yet; insert it here.
991   MachineBasicBlock *JumpMBB = JT->MBB;
992   CurMF->insert(BBI, JumpMBB);
993 
994   // Since the jump table block is separate from the switch block, we need
995   // to keep track of it as a machine predecessor to the default block,
996   // otherwise we lose the phi edges.
997   addMachineCFGPred({SwitchMBB->getBasicBlock(), DefaultMBB->getBasicBlock()},
998                     CurMBB);
999   addMachineCFGPred({SwitchMBB->getBasicBlock(), DefaultMBB->getBasicBlock()},
1000                     JumpMBB);
1001 
1002   auto JumpProb = I->Prob;
1003   auto FallthroughProb = UnhandledProbs;
1004 
1005   // If the default statement is a target of the jump table, we evenly
1006   // distribute the default probability to successors of CurMBB. Also
1007   // update the probability on the edge from JumpMBB to Fallthrough.
1008   for (MachineBasicBlock::succ_iterator SI = JumpMBB->succ_begin(),
1009                                         SE = JumpMBB->succ_end();
1010        SI != SE; ++SI) {
1011     if (*SI == DefaultMBB) {
1012       JumpProb += DefaultProb / 2;
1013       FallthroughProb -= DefaultProb / 2;
1014       JumpMBB->setSuccProbability(SI, DefaultProb / 2);
1015       JumpMBB->normalizeSuccProbs();
1016     } else {
1017       // Also record edges from the jump table block to it's successors.
1018       addMachineCFGPred({SwitchMBB->getBasicBlock(), (*SI)->getBasicBlock()},
1019                         JumpMBB);
1020     }
1021   }
1022 
1023   if (FallthroughUnreachable)
1024     JTH->FallthroughUnreachable = true;
1025 
1026   if (!JTH->FallthroughUnreachable)
1027     addSuccessorWithProb(CurMBB, Fallthrough, FallthroughProb);
1028   addSuccessorWithProb(CurMBB, JumpMBB, JumpProb);
1029   CurMBB->normalizeSuccProbs();
1030 
1031   // The jump table header will be inserted in our current block, do the
1032   // range check, and fall through to our fallthrough block.
1033   JTH->HeaderBB = CurMBB;
1034   JT->Default = Fallthrough; // FIXME: Move Default to JumpTableHeader.
1035 
1036   // If we're in the right place, emit the jump table header right now.
1037   if (CurMBB == SwitchMBB) {
1038     if (!emitJumpTableHeader(*JT, *JTH, CurMBB))
1039       return false;
1040     JTH->Emitted = true;
1041   }
1042   return true;
1043 }
1044 bool IRTranslator::lowerSwitchRangeWorkItem(SwitchCG::CaseClusterIt I,
1045                                             Value *Cond,
1046                                             MachineBasicBlock *Fallthrough,
1047                                             bool FallthroughUnreachable,
1048                                             BranchProbability UnhandledProbs,
1049                                             MachineBasicBlock *CurMBB,
1050                                             MachineIRBuilder &MIB,
1051                                             MachineBasicBlock *SwitchMBB) {
1052   using namespace SwitchCG;
1053   const Value *RHS, *LHS, *MHS;
1054   CmpInst::Predicate Pred;
1055   if (I->Low == I->High) {
1056     // Check Cond == I->Low.
1057     Pred = CmpInst::ICMP_EQ;
1058     LHS = Cond;
1059     RHS = I->Low;
1060     MHS = nullptr;
1061   } else {
1062     // Check I->Low <= Cond <= I->High.
1063     Pred = CmpInst::ICMP_SLE;
1064     LHS = I->Low;
1065     MHS = Cond;
1066     RHS = I->High;
1067   }
1068 
1069   // If Fallthrough is unreachable, fold away the comparison.
1070   // The false probability is the sum of all unhandled cases.
1071   CaseBlock CB(Pred, FallthroughUnreachable, LHS, RHS, MHS, I->MBB, Fallthrough,
1072                CurMBB, MIB.getDebugLoc(), I->Prob, UnhandledProbs);
1073 
1074   emitSwitchCase(CB, SwitchMBB, MIB);
1075   return true;
1076 }
1077 
1078 void IRTranslator::emitBitTestHeader(SwitchCG::BitTestBlock &B,
1079                                      MachineBasicBlock *SwitchBB) {
1080   MachineIRBuilder &MIB = *CurBuilder;
1081   MIB.setMBB(*SwitchBB);
1082 
1083   // Subtract the minimum value.
1084   Register SwitchOpReg = getOrCreateVReg(*B.SValue);
1085 
1086   LLT SwitchOpTy = MRI->getType(SwitchOpReg);
1087   Register MinValReg = MIB.buildConstant(SwitchOpTy, B.First).getReg(0);
1088   auto RangeSub = MIB.buildSub(SwitchOpTy, SwitchOpReg, MinValReg);
1089 
1090   Type *PtrIRTy = PointerType::getUnqual(MF->getFunction().getContext());
1091   const LLT PtrTy = getLLTForType(*PtrIRTy, *DL);
1092 
1093   LLT MaskTy = SwitchOpTy;
1094   if (MaskTy.getSizeInBits() > PtrTy.getSizeInBits() ||
1095       !llvm::has_single_bit<uint32_t>(MaskTy.getSizeInBits()))
1096     MaskTy = LLT::scalar(PtrTy.getSizeInBits());
1097   else {
1098     // Ensure that the type will fit the mask value.
1099     for (unsigned I = 0, E = B.Cases.size(); I != E; ++I) {
1100       if (!isUIntN(SwitchOpTy.getSizeInBits(), B.Cases[I].Mask)) {
1101         // Switch table case range are encoded into series of masks.
1102         // Just use pointer type, it's guaranteed to fit.
1103         MaskTy = LLT::scalar(PtrTy.getSizeInBits());
1104         break;
1105       }
1106     }
1107   }
1108   Register SubReg = RangeSub.getReg(0);
1109   if (SwitchOpTy != MaskTy)
1110     SubReg = MIB.buildZExtOrTrunc(MaskTy, SubReg).getReg(0);
1111 
1112   B.RegVT = getMVTForLLT(MaskTy);
1113   B.Reg = SubReg;
1114 
1115   MachineBasicBlock *MBB = B.Cases[0].ThisBB;
1116 
1117   if (!B.FallthroughUnreachable)
1118     addSuccessorWithProb(SwitchBB, B.Default, B.DefaultProb);
1119   addSuccessorWithProb(SwitchBB, MBB, B.Prob);
1120 
1121   SwitchBB->normalizeSuccProbs();
1122 
1123   if (!B.FallthroughUnreachable) {
1124     // Conditional branch to the default block.
1125     auto RangeCst = MIB.buildConstant(SwitchOpTy, B.Range);
1126     auto RangeCmp = MIB.buildICmp(CmpInst::Predicate::ICMP_UGT, LLT::scalar(1),
1127                                   RangeSub, RangeCst);
1128     MIB.buildBrCond(RangeCmp, *B.Default);
1129   }
1130 
1131   // Avoid emitting unnecessary branches to the next block.
1132   if (MBB != SwitchBB->getNextNode())
1133     MIB.buildBr(*MBB);
1134 }
1135 
1136 void IRTranslator::emitBitTestCase(SwitchCG::BitTestBlock &BB,
1137                                    MachineBasicBlock *NextMBB,
1138                                    BranchProbability BranchProbToNext,
1139                                    Register Reg, SwitchCG::BitTestCase &B,
1140                                    MachineBasicBlock *SwitchBB) {
1141   MachineIRBuilder &MIB = *CurBuilder;
1142   MIB.setMBB(*SwitchBB);
1143 
1144   LLT SwitchTy = getLLTForMVT(BB.RegVT);
1145   Register Cmp;
1146   unsigned PopCount = llvm::popcount(B.Mask);
1147   if (PopCount == 1) {
1148     // Testing for a single bit; just compare the shift count with what it
1149     // would need to be to shift a 1 bit in that position.
1150     auto MaskTrailingZeros =
1151         MIB.buildConstant(SwitchTy, llvm::countr_zero(B.Mask));
1152     Cmp =
1153         MIB.buildICmp(ICmpInst::ICMP_EQ, LLT::scalar(1), Reg, MaskTrailingZeros)
1154             .getReg(0);
1155   } else if (PopCount == BB.Range) {
1156     // There is only one zero bit in the range, test for it directly.
1157     auto MaskTrailingOnes =
1158         MIB.buildConstant(SwitchTy, llvm::countr_one(B.Mask));
1159     Cmp = MIB.buildICmp(CmpInst::ICMP_NE, LLT::scalar(1), Reg, MaskTrailingOnes)
1160               .getReg(0);
1161   } else {
1162     // Make desired shift.
1163     auto CstOne = MIB.buildConstant(SwitchTy, 1);
1164     auto SwitchVal = MIB.buildShl(SwitchTy, CstOne, Reg);
1165 
1166     // Emit bit tests and jumps.
1167     auto CstMask = MIB.buildConstant(SwitchTy, B.Mask);
1168     auto AndOp = MIB.buildAnd(SwitchTy, SwitchVal, CstMask);
1169     auto CstZero = MIB.buildConstant(SwitchTy, 0);
1170     Cmp = MIB.buildICmp(CmpInst::ICMP_NE, LLT::scalar(1), AndOp, CstZero)
1171               .getReg(0);
1172   }
1173 
1174   // The branch probability from SwitchBB to B.TargetBB is B.ExtraProb.
1175   addSuccessorWithProb(SwitchBB, B.TargetBB, B.ExtraProb);
1176   // The branch probability from SwitchBB to NextMBB is BranchProbToNext.
1177   addSuccessorWithProb(SwitchBB, NextMBB, BranchProbToNext);
1178   // It is not guaranteed that the sum of B.ExtraProb and BranchProbToNext is
1179   // one as they are relative probabilities (and thus work more like weights),
1180   // and hence we need to normalize them to let the sum of them become one.
1181   SwitchBB->normalizeSuccProbs();
1182 
1183   // Record the fact that the IR edge from the header to the bit test target
1184   // will go through our new block. Neeeded for PHIs to have nodes added.
1185   addMachineCFGPred({BB.Parent->getBasicBlock(), B.TargetBB->getBasicBlock()},
1186                     SwitchBB);
1187 
1188   MIB.buildBrCond(Cmp, *B.TargetBB);
1189 
1190   // Avoid emitting unnecessary branches to the next block.
1191   if (NextMBB != SwitchBB->getNextNode())
1192     MIB.buildBr(*NextMBB);
1193 }
1194 
1195 bool IRTranslator::lowerBitTestWorkItem(
1196     SwitchCG::SwitchWorkListItem W, MachineBasicBlock *SwitchMBB,
1197     MachineBasicBlock *CurMBB, MachineBasicBlock *DefaultMBB,
1198     MachineIRBuilder &MIB, MachineFunction::iterator BBI,
1199     BranchProbability DefaultProb, BranchProbability UnhandledProbs,
1200     SwitchCG::CaseClusterIt I, MachineBasicBlock *Fallthrough,
1201     bool FallthroughUnreachable) {
1202   using namespace SwitchCG;
1203   MachineFunction *CurMF = SwitchMBB->getParent();
1204   // FIXME: Optimize away range check based on pivot comparisons.
1205   BitTestBlock *BTB = &SL->BitTestCases[I->BTCasesIndex];
1206   // The bit test blocks haven't been inserted yet; insert them here.
1207   for (BitTestCase &BTC : BTB->Cases)
1208     CurMF->insert(BBI, BTC.ThisBB);
1209 
1210   // Fill in fields of the BitTestBlock.
1211   BTB->Parent = CurMBB;
1212   BTB->Default = Fallthrough;
1213 
1214   BTB->DefaultProb = UnhandledProbs;
1215   // If the cases in bit test don't form a contiguous range, we evenly
1216   // distribute the probability on the edge to Fallthrough to two
1217   // successors of CurMBB.
1218   if (!BTB->ContiguousRange) {
1219     BTB->Prob += DefaultProb / 2;
1220     BTB->DefaultProb -= DefaultProb / 2;
1221   }
1222 
1223   if (FallthroughUnreachable)
1224     BTB->FallthroughUnreachable = true;
1225 
1226   // If we're in the right place, emit the bit test header right now.
1227   if (CurMBB == SwitchMBB) {
1228     emitBitTestHeader(*BTB, SwitchMBB);
1229     BTB->Emitted = true;
1230   }
1231   return true;
1232 }
1233 
1234 bool IRTranslator::lowerSwitchWorkItem(SwitchCG::SwitchWorkListItem W,
1235                                        Value *Cond,
1236                                        MachineBasicBlock *SwitchMBB,
1237                                        MachineBasicBlock *DefaultMBB,
1238                                        MachineIRBuilder &MIB) {
1239   using namespace SwitchCG;
1240   MachineFunction *CurMF = FuncInfo.MF;
1241   MachineBasicBlock *NextMBB = nullptr;
1242   MachineFunction::iterator BBI(W.MBB);
1243   if (++BBI != FuncInfo.MF->end())
1244     NextMBB = &*BBI;
1245 
1246   if (EnableOpts) {
1247     // Here, we order cases by probability so the most likely case will be
1248     // checked first. However, two clusters can have the same probability in
1249     // which case their relative ordering is non-deterministic. So we use Low
1250     // as a tie-breaker as clusters are guaranteed to never overlap.
1251     llvm::sort(W.FirstCluster, W.LastCluster + 1,
1252                [](const CaseCluster &a, const CaseCluster &b) {
1253                  return a.Prob != b.Prob
1254                             ? a.Prob > b.Prob
1255                             : a.Low->getValue().slt(b.Low->getValue());
1256                });
1257 
1258     // Rearrange the case blocks so that the last one falls through if possible
1259     // without changing the order of probabilities.
1260     for (CaseClusterIt I = W.LastCluster; I > W.FirstCluster;) {
1261       --I;
1262       if (I->Prob > W.LastCluster->Prob)
1263         break;
1264       if (I->Kind == CC_Range && I->MBB == NextMBB) {
1265         std::swap(*I, *W.LastCluster);
1266         break;
1267       }
1268     }
1269   }
1270 
1271   // Compute total probability.
1272   BranchProbability DefaultProb = W.DefaultProb;
1273   BranchProbability UnhandledProbs = DefaultProb;
1274   for (CaseClusterIt I = W.FirstCluster; I <= W.LastCluster; ++I)
1275     UnhandledProbs += I->Prob;
1276 
1277   MachineBasicBlock *CurMBB = W.MBB;
1278   for (CaseClusterIt I = W.FirstCluster, E = W.LastCluster; I <= E; ++I) {
1279     bool FallthroughUnreachable = false;
1280     MachineBasicBlock *Fallthrough;
1281     if (I == W.LastCluster) {
1282       // For the last cluster, fall through to the default destination.
1283       Fallthrough = DefaultMBB;
1284       FallthroughUnreachable = isa<UnreachableInst>(
1285           DefaultMBB->getBasicBlock()->getFirstNonPHIOrDbg());
1286     } else {
1287       Fallthrough = CurMF->CreateMachineBasicBlock(CurMBB->getBasicBlock());
1288       CurMF->insert(BBI, Fallthrough);
1289     }
1290     UnhandledProbs -= I->Prob;
1291 
1292     switch (I->Kind) {
1293     case CC_BitTests: {
1294       if (!lowerBitTestWorkItem(W, SwitchMBB, CurMBB, DefaultMBB, MIB, BBI,
1295                                 DefaultProb, UnhandledProbs, I, Fallthrough,
1296                                 FallthroughUnreachable)) {
1297         LLVM_DEBUG(dbgs() << "Failed to lower bit test for switch");
1298         return false;
1299       }
1300       break;
1301     }
1302 
1303     case CC_JumpTable: {
1304       if (!lowerJumpTableWorkItem(W, SwitchMBB, CurMBB, DefaultMBB, MIB, BBI,
1305                                   UnhandledProbs, I, Fallthrough,
1306                                   FallthroughUnreachable)) {
1307         LLVM_DEBUG(dbgs() << "Failed to lower jump table");
1308         return false;
1309       }
1310       break;
1311     }
1312     case CC_Range: {
1313       if (!lowerSwitchRangeWorkItem(I, Cond, Fallthrough,
1314                                     FallthroughUnreachable, UnhandledProbs,
1315                                     CurMBB, MIB, SwitchMBB)) {
1316         LLVM_DEBUG(dbgs() << "Failed to lower switch range");
1317         return false;
1318       }
1319       break;
1320     }
1321     }
1322     CurMBB = Fallthrough;
1323   }
1324 
1325   return true;
1326 }
1327 
1328 bool IRTranslator::translateIndirectBr(const User &U,
1329                                        MachineIRBuilder &MIRBuilder) {
1330   const IndirectBrInst &BrInst = cast<IndirectBrInst>(U);
1331 
1332   const Register Tgt = getOrCreateVReg(*BrInst.getAddress());
1333   MIRBuilder.buildBrIndirect(Tgt);
1334 
1335   // Link successors.
1336   SmallPtrSet<const BasicBlock *, 32> AddedSuccessors;
1337   MachineBasicBlock &CurBB = MIRBuilder.getMBB();
1338   for (const BasicBlock *Succ : successors(&BrInst)) {
1339     // It's legal for indirectbr instructions to have duplicate blocks in the
1340     // destination list. We don't allow this in MIR. Skip anything that's
1341     // already a successor.
1342     if (!AddedSuccessors.insert(Succ).second)
1343       continue;
1344     CurBB.addSuccessor(&getMBB(*Succ));
1345   }
1346 
1347   return true;
1348 }
1349 
1350 static bool isSwiftError(const Value *V) {
1351   if (auto Arg = dyn_cast<Argument>(V))
1352     return Arg->hasSwiftErrorAttr();
1353   if (auto AI = dyn_cast<AllocaInst>(V))
1354     return AI->isSwiftError();
1355   return false;
1356 }
1357 
1358 bool IRTranslator::translateLoad(const User &U, MachineIRBuilder &MIRBuilder) {
1359   const LoadInst &LI = cast<LoadInst>(U);
1360   TypeSize StoreSize = DL->getTypeStoreSize(LI.getType());
1361   if (StoreSize.isZero())
1362     return true;
1363 
1364   ArrayRef<Register> Regs = getOrCreateVRegs(LI);
1365   ArrayRef<uint64_t> Offsets = *VMap.getOffsets(LI);
1366   Register Base = getOrCreateVReg(*LI.getPointerOperand());
1367   AAMDNodes AAInfo = LI.getAAMetadata();
1368 
1369   const Value *Ptr = LI.getPointerOperand();
1370   Type *OffsetIRTy = DL->getIndexType(Ptr->getType());
1371   LLT OffsetTy = getLLTForType(*OffsetIRTy, *DL);
1372 
1373   if (CLI->supportSwiftError() && isSwiftError(Ptr)) {
1374     assert(Regs.size() == 1 && "swifterror should be single pointer");
1375     Register VReg =
1376         SwiftError.getOrCreateVRegUseAt(&LI, &MIRBuilder.getMBB(), Ptr);
1377     MIRBuilder.buildCopy(Regs[0], VReg);
1378     return true;
1379   }
1380 
1381   MachineMemOperand::Flags Flags =
1382       TLI->getLoadMemOperandFlags(LI, *DL, AC, LibInfo);
1383   if (AA && !(Flags & MachineMemOperand::MOInvariant)) {
1384     if (AA->pointsToConstantMemory(
1385             MemoryLocation(Ptr, LocationSize::precise(StoreSize), AAInfo))) {
1386       Flags |= MachineMemOperand::MOInvariant;
1387     }
1388   }
1389 
1390   const MDNode *Ranges =
1391       Regs.size() == 1 ? LI.getMetadata(LLVMContext::MD_range) : nullptr;
1392   for (unsigned i = 0; i < Regs.size(); ++i) {
1393     Register Addr;
1394     MIRBuilder.materializePtrAdd(Addr, Base, OffsetTy, Offsets[i] / 8);
1395 
1396     MachinePointerInfo Ptr(LI.getPointerOperand(), Offsets[i] / 8);
1397     Align BaseAlign = getMemOpAlign(LI);
1398     auto MMO = MF->getMachineMemOperand(
1399         Ptr, Flags, MRI->getType(Regs[i]),
1400         commonAlignment(BaseAlign, Offsets[i] / 8), AAInfo, Ranges,
1401         LI.getSyncScopeID(), LI.getOrdering());
1402     MIRBuilder.buildLoad(Regs[i], Addr, *MMO);
1403   }
1404 
1405   return true;
1406 }
1407 
1408 bool IRTranslator::translateStore(const User &U, MachineIRBuilder &MIRBuilder) {
1409   const StoreInst &SI = cast<StoreInst>(U);
1410   if (DL->getTypeStoreSize(SI.getValueOperand()->getType()).isZero())
1411     return true;
1412 
1413   ArrayRef<Register> Vals = getOrCreateVRegs(*SI.getValueOperand());
1414   ArrayRef<uint64_t> Offsets = *VMap.getOffsets(*SI.getValueOperand());
1415   Register Base = getOrCreateVReg(*SI.getPointerOperand());
1416 
1417   Type *OffsetIRTy = DL->getIndexType(SI.getPointerOperandType());
1418   LLT OffsetTy = getLLTForType(*OffsetIRTy, *DL);
1419 
1420   if (CLI->supportSwiftError() && isSwiftError(SI.getPointerOperand())) {
1421     assert(Vals.size() == 1 && "swifterror should be single pointer");
1422 
1423     Register VReg = SwiftError.getOrCreateVRegDefAt(&SI, &MIRBuilder.getMBB(),
1424                                                     SI.getPointerOperand());
1425     MIRBuilder.buildCopy(VReg, Vals[0]);
1426     return true;
1427   }
1428 
1429   MachineMemOperand::Flags Flags = TLI->getStoreMemOperandFlags(SI, *DL);
1430 
1431   for (unsigned i = 0; i < Vals.size(); ++i) {
1432     Register Addr;
1433     MIRBuilder.materializePtrAdd(Addr, Base, OffsetTy, Offsets[i] / 8);
1434 
1435     MachinePointerInfo Ptr(SI.getPointerOperand(), Offsets[i] / 8);
1436     Align BaseAlign = getMemOpAlign(SI);
1437     auto MMO = MF->getMachineMemOperand(
1438         Ptr, Flags, MRI->getType(Vals[i]),
1439         commonAlignment(BaseAlign, Offsets[i] / 8), SI.getAAMetadata(), nullptr,
1440         SI.getSyncScopeID(), SI.getOrdering());
1441     MIRBuilder.buildStore(Vals[i], Addr, *MMO);
1442   }
1443   return true;
1444 }
1445 
1446 static uint64_t getOffsetFromIndices(const User &U, const DataLayout &DL) {
1447   const Value *Src = U.getOperand(0);
1448   Type *Int32Ty = Type::getInt32Ty(U.getContext());
1449 
1450   // getIndexedOffsetInType is designed for GEPs, so the first index is the
1451   // usual array element rather than looking into the actual aggregate.
1452   SmallVector<Value *, 1> Indices;
1453   Indices.push_back(ConstantInt::get(Int32Ty, 0));
1454 
1455   if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(&U)) {
1456     for (auto Idx : EVI->indices())
1457       Indices.push_back(ConstantInt::get(Int32Ty, Idx));
1458   } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(&U)) {
1459     for (auto Idx : IVI->indices())
1460       Indices.push_back(ConstantInt::get(Int32Ty, Idx));
1461   } else {
1462     for (Value *Op : drop_begin(U.operands()))
1463       Indices.push_back(Op);
1464   }
1465 
1466   return 8 * static_cast<uint64_t>(
1467                  DL.getIndexedOffsetInType(Src->getType(), Indices));
1468 }
1469 
1470 bool IRTranslator::translateExtractValue(const User &U,
1471                                          MachineIRBuilder &MIRBuilder) {
1472   const Value *Src = U.getOperand(0);
1473   uint64_t Offset = getOffsetFromIndices(U, *DL);
1474   ArrayRef<Register> SrcRegs = getOrCreateVRegs(*Src);
1475   ArrayRef<uint64_t> Offsets = *VMap.getOffsets(*Src);
1476   unsigned Idx = llvm::lower_bound(Offsets, Offset) - Offsets.begin();
1477   auto &DstRegs = allocateVRegs(U);
1478 
1479   for (unsigned i = 0; i < DstRegs.size(); ++i)
1480     DstRegs[i] = SrcRegs[Idx++];
1481 
1482   return true;
1483 }
1484 
1485 bool IRTranslator::translateInsertValue(const User &U,
1486                                         MachineIRBuilder &MIRBuilder) {
1487   const Value *Src = U.getOperand(0);
1488   uint64_t Offset = getOffsetFromIndices(U, *DL);
1489   auto &DstRegs = allocateVRegs(U);
1490   ArrayRef<uint64_t> DstOffsets = *VMap.getOffsets(U);
1491   ArrayRef<Register> SrcRegs = getOrCreateVRegs(*Src);
1492   ArrayRef<Register> InsertedRegs = getOrCreateVRegs(*U.getOperand(1));
1493   auto *InsertedIt = InsertedRegs.begin();
1494 
1495   for (unsigned i = 0; i < DstRegs.size(); ++i) {
1496     if (DstOffsets[i] >= Offset && InsertedIt != InsertedRegs.end())
1497       DstRegs[i] = *InsertedIt++;
1498     else
1499       DstRegs[i] = SrcRegs[i];
1500   }
1501 
1502   return true;
1503 }
1504 
1505 bool IRTranslator::translateSelect(const User &U,
1506                                    MachineIRBuilder &MIRBuilder) {
1507   Register Tst = getOrCreateVReg(*U.getOperand(0));
1508   ArrayRef<Register> ResRegs = getOrCreateVRegs(U);
1509   ArrayRef<Register> Op0Regs = getOrCreateVRegs(*U.getOperand(1));
1510   ArrayRef<Register> Op1Regs = getOrCreateVRegs(*U.getOperand(2));
1511 
1512   uint32_t Flags = 0;
1513   if (const SelectInst *SI = dyn_cast<SelectInst>(&U))
1514     Flags = MachineInstr::copyFlagsFromInstruction(*SI);
1515 
1516   for (unsigned i = 0; i < ResRegs.size(); ++i) {
1517     MIRBuilder.buildSelect(ResRegs[i], Tst, Op0Regs[i], Op1Regs[i], Flags);
1518   }
1519 
1520   return true;
1521 }
1522 
1523 bool IRTranslator::translateCopy(const User &U, const Value &V,
1524                                  MachineIRBuilder &MIRBuilder) {
1525   Register Src = getOrCreateVReg(V);
1526   auto &Regs = *VMap.getVRegs(U);
1527   if (Regs.empty()) {
1528     Regs.push_back(Src);
1529     VMap.getOffsets(U)->push_back(0);
1530   } else {
1531     // If we already assigned a vreg for this instruction, we can't change that.
1532     // Emit a copy to satisfy the users we already emitted.
1533     MIRBuilder.buildCopy(Regs[0], Src);
1534   }
1535   return true;
1536 }
1537 
1538 bool IRTranslator::translateBitCast(const User &U,
1539                                     MachineIRBuilder &MIRBuilder) {
1540   // If we're bitcasting to the source type, we can reuse the source vreg.
1541   if (getLLTForType(*U.getOperand(0)->getType(), *DL) ==
1542       getLLTForType(*U.getType(), *DL)) {
1543     // If the source is a ConstantInt then it was probably created by
1544     // ConstantHoisting and we should leave it alone.
1545     if (isa<ConstantInt>(U.getOperand(0)))
1546       return translateCast(TargetOpcode::G_CONSTANT_FOLD_BARRIER, U,
1547                            MIRBuilder);
1548     return translateCopy(U, *U.getOperand(0), MIRBuilder);
1549   }
1550 
1551   return translateCast(TargetOpcode::G_BITCAST, U, MIRBuilder);
1552 }
1553 
1554 bool IRTranslator::translateCast(unsigned Opcode, const User &U,
1555                                  MachineIRBuilder &MIRBuilder) {
1556   if (U.getType()->getScalarType()->isBFloatTy() ||
1557       U.getOperand(0)->getType()->getScalarType()->isBFloatTy())
1558     return false;
1559 
1560   uint32_t Flags = 0;
1561   if (const Instruction *I = dyn_cast<Instruction>(&U))
1562     Flags = MachineInstr::copyFlagsFromInstruction(*I);
1563 
1564   Register Op = getOrCreateVReg(*U.getOperand(0));
1565   Register Res = getOrCreateVReg(U);
1566   MIRBuilder.buildInstr(Opcode, {Res}, {Op}, Flags);
1567   return true;
1568 }
1569 
1570 bool IRTranslator::translateGetElementPtr(const User &U,
1571                                           MachineIRBuilder &MIRBuilder) {
1572   Value &Op0 = *U.getOperand(0);
1573   Register BaseReg = getOrCreateVReg(Op0);
1574   Type *PtrIRTy = Op0.getType();
1575   LLT PtrTy = getLLTForType(*PtrIRTy, *DL);
1576   Type *OffsetIRTy = DL->getIndexType(PtrIRTy);
1577   LLT OffsetTy = getLLTForType(*OffsetIRTy, *DL);
1578 
1579   uint32_t Flags = 0;
1580   if (const Instruction *I = dyn_cast<Instruction>(&U))
1581     Flags = MachineInstr::copyFlagsFromInstruction(*I);
1582 
1583   // Normalize Vector GEP - all scalar operands should be converted to the
1584   // splat vector.
1585   unsigned VectorWidth = 0;
1586 
1587   // True if we should use a splat vector; using VectorWidth alone is not
1588   // sufficient.
1589   bool WantSplatVector = false;
1590   if (auto *VT = dyn_cast<VectorType>(U.getType())) {
1591     VectorWidth = cast<FixedVectorType>(VT)->getNumElements();
1592     // We don't produce 1 x N vectors; those are treated as scalars.
1593     WantSplatVector = VectorWidth > 1;
1594   }
1595 
1596   // We might need to splat the base pointer into a vector if the offsets
1597   // are vectors.
1598   if (WantSplatVector && !PtrTy.isVector()) {
1599     BaseReg = MIRBuilder
1600                   .buildSplatBuildVector(LLT::fixed_vector(VectorWidth, PtrTy),
1601                                          BaseReg)
1602                   .getReg(0);
1603     PtrIRTy = FixedVectorType::get(PtrIRTy, VectorWidth);
1604     PtrTy = getLLTForType(*PtrIRTy, *DL);
1605     OffsetIRTy = DL->getIndexType(PtrIRTy);
1606     OffsetTy = getLLTForType(*OffsetIRTy, *DL);
1607   }
1608 
1609   int64_t Offset = 0;
1610   for (gep_type_iterator GTI = gep_type_begin(&U), E = gep_type_end(&U);
1611        GTI != E; ++GTI) {
1612     const Value *Idx = GTI.getOperand();
1613     if (StructType *StTy = GTI.getStructTypeOrNull()) {
1614       unsigned Field = cast<Constant>(Idx)->getUniqueInteger().getZExtValue();
1615       Offset += DL->getStructLayout(StTy)->getElementOffset(Field);
1616       continue;
1617     } else {
1618       uint64_t ElementSize = GTI.getSequentialElementStride(*DL);
1619 
1620       // If this is a scalar constant or a splat vector of constants,
1621       // handle it quickly.
1622       if (const auto *CI = dyn_cast<ConstantInt>(Idx)) {
1623         if (std::optional<int64_t> Val = CI->getValue().trySExtValue()) {
1624           Offset += ElementSize * *Val;
1625           continue;
1626         }
1627       }
1628 
1629       if (Offset != 0) {
1630         auto OffsetMIB = MIRBuilder.buildConstant({OffsetTy}, Offset);
1631         BaseReg = MIRBuilder.buildPtrAdd(PtrTy, BaseReg, OffsetMIB.getReg(0))
1632                       .getReg(0);
1633         Offset = 0;
1634       }
1635 
1636       Register IdxReg = getOrCreateVReg(*Idx);
1637       LLT IdxTy = MRI->getType(IdxReg);
1638       if (IdxTy != OffsetTy) {
1639         if (!IdxTy.isVector() && WantSplatVector) {
1640           IdxReg = MIRBuilder
1641                        .buildSplatBuildVector(OffsetTy.changeElementType(IdxTy),
1642                                               IdxReg)
1643                        .getReg(0);
1644         }
1645 
1646         IdxReg = MIRBuilder.buildSExtOrTrunc(OffsetTy, IdxReg).getReg(0);
1647       }
1648 
1649       // N = N + Idx * ElementSize;
1650       // Avoid doing it for ElementSize of 1.
1651       Register GepOffsetReg;
1652       if (ElementSize != 1) {
1653         auto ElementSizeMIB = MIRBuilder.buildConstant(
1654             getLLTForType(*OffsetIRTy, *DL), ElementSize);
1655         GepOffsetReg =
1656             MIRBuilder.buildMul(OffsetTy, IdxReg, ElementSizeMIB).getReg(0);
1657       } else
1658         GepOffsetReg = IdxReg;
1659 
1660       BaseReg = MIRBuilder.buildPtrAdd(PtrTy, BaseReg, GepOffsetReg).getReg(0);
1661     }
1662   }
1663 
1664   if (Offset != 0) {
1665     auto OffsetMIB =
1666         MIRBuilder.buildConstant(OffsetTy, Offset);
1667 
1668     if (int64_t(Offset) >= 0 && cast<GEPOperator>(U).isInBounds())
1669       Flags |= MachineInstr::MIFlag::NoUWrap;
1670 
1671     MIRBuilder.buildPtrAdd(getOrCreateVReg(U), BaseReg, OffsetMIB.getReg(0),
1672                            Flags);
1673     return true;
1674   }
1675 
1676   MIRBuilder.buildCopy(getOrCreateVReg(U), BaseReg);
1677   return true;
1678 }
1679 
1680 bool IRTranslator::translateMemFunc(const CallInst &CI,
1681                                     MachineIRBuilder &MIRBuilder,
1682                                     unsigned Opcode) {
1683   const Value *SrcPtr = CI.getArgOperand(1);
1684   // If the source is undef, then just emit a nop.
1685   if (isa<UndefValue>(SrcPtr))
1686     return true;
1687 
1688   SmallVector<Register, 3> SrcRegs;
1689 
1690   unsigned MinPtrSize = UINT_MAX;
1691   for (auto AI = CI.arg_begin(), AE = CI.arg_end(); std::next(AI) != AE; ++AI) {
1692     Register SrcReg = getOrCreateVReg(**AI);
1693     LLT SrcTy = MRI->getType(SrcReg);
1694     if (SrcTy.isPointer())
1695       MinPtrSize = std::min<unsigned>(SrcTy.getSizeInBits(), MinPtrSize);
1696     SrcRegs.push_back(SrcReg);
1697   }
1698 
1699   LLT SizeTy = LLT::scalar(MinPtrSize);
1700 
1701   // The size operand should be the minimum of the pointer sizes.
1702   Register &SizeOpReg = SrcRegs[SrcRegs.size() - 1];
1703   if (MRI->getType(SizeOpReg) != SizeTy)
1704     SizeOpReg = MIRBuilder.buildZExtOrTrunc(SizeTy, SizeOpReg).getReg(0);
1705 
1706   auto ICall = MIRBuilder.buildInstr(Opcode);
1707   for (Register SrcReg : SrcRegs)
1708     ICall.addUse(SrcReg);
1709 
1710   Align DstAlign;
1711   Align SrcAlign;
1712   unsigned IsVol =
1713       cast<ConstantInt>(CI.getArgOperand(CI.arg_size() - 1))->getZExtValue();
1714 
1715   ConstantInt *CopySize = nullptr;
1716 
1717   if (auto *MCI = dyn_cast<MemCpyInst>(&CI)) {
1718     DstAlign = MCI->getDestAlign().valueOrOne();
1719     SrcAlign = MCI->getSourceAlign().valueOrOne();
1720     CopySize = dyn_cast<ConstantInt>(MCI->getArgOperand(2));
1721   } else if (auto *MCI = dyn_cast<MemCpyInlineInst>(&CI)) {
1722     DstAlign = MCI->getDestAlign().valueOrOne();
1723     SrcAlign = MCI->getSourceAlign().valueOrOne();
1724     CopySize = dyn_cast<ConstantInt>(MCI->getArgOperand(2));
1725   } else if (auto *MMI = dyn_cast<MemMoveInst>(&CI)) {
1726     DstAlign = MMI->getDestAlign().valueOrOne();
1727     SrcAlign = MMI->getSourceAlign().valueOrOne();
1728     CopySize = dyn_cast<ConstantInt>(MMI->getArgOperand(2));
1729   } else {
1730     auto *MSI = cast<MemSetInst>(&CI);
1731     DstAlign = MSI->getDestAlign().valueOrOne();
1732   }
1733 
1734   if (Opcode != TargetOpcode::G_MEMCPY_INLINE) {
1735     // We need to propagate the tail call flag from the IR inst as an argument.
1736     // Otherwise, we have to pessimize and assume later that we cannot tail call
1737     // any memory intrinsics.
1738     ICall.addImm(CI.isTailCall() ? 1 : 0);
1739   }
1740 
1741   // Create mem operands to store the alignment and volatile info.
1742   MachineMemOperand::Flags LoadFlags = MachineMemOperand::MOLoad;
1743   MachineMemOperand::Flags StoreFlags = MachineMemOperand::MOStore;
1744   if (IsVol) {
1745     LoadFlags |= MachineMemOperand::MOVolatile;
1746     StoreFlags |= MachineMemOperand::MOVolatile;
1747   }
1748 
1749   AAMDNodes AAInfo = CI.getAAMetadata();
1750   if (AA && CopySize &&
1751       AA->pointsToConstantMemory(MemoryLocation(
1752           SrcPtr, LocationSize::precise(CopySize->getZExtValue()), AAInfo))) {
1753     LoadFlags |= MachineMemOperand::MOInvariant;
1754 
1755     // FIXME: pointsToConstantMemory probably does not imply dereferenceable,
1756     // but the previous usage implied it did. Probably should check
1757     // isDereferenceableAndAlignedPointer.
1758     LoadFlags |= MachineMemOperand::MODereferenceable;
1759   }
1760 
1761   ICall.addMemOperand(
1762       MF->getMachineMemOperand(MachinePointerInfo(CI.getArgOperand(0)),
1763                                StoreFlags, 1, DstAlign, AAInfo));
1764   if (Opcode != TargetOpcode::G_MEMSET)
1765     ICall.addMemOperand(MF->getMachineMemOperand(
1766         MachinePointerInfo(SrcPtr), LoadFlags, 1, SrcAlign, AAInfo));
1767 
1768   return true;
1769 }
1770 
1771 bool IRTranslator::translateTrap(const CallInst &CI,
1772                                  MachineIRBuilder &MIRBuilder,
1773                                  unsigned Opcode) {
1774   StringRef TrapFuncName =
1775       CI.getAttributes().getFnAttr("trap-func-name").getValueAsString();
1776   if (TrapFuncName.empty()) {
1777     if (Opcode == TargetOpcode::G_UBSANTRAP) {
1778       uint64_t Code = cast<ConstantInt>(CI.getOperand(0))->getZExtValue();
1779       MIRBuilder.buildInstr(Opcode, {}, ArrayRef<llvm::SrcOp>{Code});
1780     } else {
1781       MIRBuilder.buildInstr(Opcode);
1782     }
1783     return true;
1784   }
1785 
1786   CallLowering::CallLoweringInfo Info;
1787   if (Opcode == TargetOpcode::G_UBSANTRAP)
1788     Info.OrigArgs.push_back({getOrCreateVRegs(*CI.getArgOperand(0)),
1789                              CI.getArgOperand(0)->getType(), 0});
1790 
1791   Info.Callee = MachineOperand::CreateES(TrapFuncName.data());
1792   Info.CB = &CI;
1793   Info.OrigRet = {Register(), Type::getVoidTy(CI.getContext()), 0};
1794   return CLI->lowerCall(MIRBuilder, Info);
1795 }
1796 
1797 bool IRTranslator::translateVectorInterleave2Intrinsic(
1798     const CallInst &CI, MachineIRBuilder &MIRBuilder) {
1799   assert(CI.getIntrinsicID() == Intrinsic::vector_interleave2 &&
1800          "This function can only be called on the interleave2 intrinsic!");
1801   // Canonicalize interleave2 to G_SHUFFLE_VECTOR (similar to SelectionDAG).
1802   Register Op0 = getOrCreateVReg(*CI.getOperand(0));
1803   Register Op1 = getOrCreateVReg(*CI.getOperand(1));
1804   Register Res = getOrCreateVReg(CI);
1805 
1806   LLT OpTy = MRI->getType(Op0);
1807   MIRBuilder.buildShuffleVector(Res, Op0, Op1,
1808                                 createInterleaveMask(OpTy.getNumElements(), 2));
1809 
1810   return true;
1811 }
1812 
1813 bool IRTranslator::translateVectorDeinterleave2Intrinsic(
1814     const CallInst &CI, MachineIRBuilder &MIRBuilder) {
1815   assert(CI.getIntrinsicID() == Intrinsic::vector_deinterleave2 &&
1816          "This function can only be called on the deinterleave2 intrinsic!");
1817   // Canonicalize deinterleave2 to shuffles that extract sub-vectors (similar to
1818   // SelectionDAG).
1819   Register Op = getOrCreateVReg(*CI.getOperand(0));
1820   auto Undef = MIRBuilder.buildUndef(MRI->getType(Op));
1821   ArrayRef<Register> Res = getOrCreateVRegs(CI);
1822 
1823   LLT ResTy = MRI->getType(Res[0]);
1824   MIRBuilder.buildShuffleVector(Res[0], Op, Undef,
1825                                 createStrideMask(0, 2, ResTy.getNumElements()));
1826   MIRBuilder.buildShuffleVector(Res[1], Op, Undef,
1827                                 createStrideMask(1, 2, ResTy.getNumElements()));
1828 
1829   return true;
1830 }
1831 
1832 void IRTranslator::getStackGuard(Register DstReg,
1833                                  MachineIRBuilder &MIRBuilder) {
1834   const TargetRegisterInfo *TRI = MF->getSubtarget().getRegisterInfo();
1835   MRI->setRegClass(DstReg, TRI->getPointerRegClass(*MF));
1836   auto MIB =
1837       MIRBuilder.buildInstr(TargetOpcode::LOAD_STACK_GUARD, {DstReg}, {});
1838 
1839   Value *Global = TLI->getSDagStackGuard(*MF->getFunction().getParent());
1840   if (!Global)
1841     return;
1842 
1843   unsigned AddrSpace = Global->getType()->getPointerAddressSpace();
1844   LLT PtrTy = LLT::pointer(AddrSpace, DL->getPointerSizeInBits(AddrSpace));
1845 
1846   MachinePointerInfo MPInfo(Global);
1847   auto Flags = MachineMemOperand::MOLoad | MachineMemOperand::MOInvariant |
1848                MachineMemOperand::MODereferenceable;
1849   MachineMemOperand *MemRef = MF->getMachineMemOperand(
1850       MPInfo, Flags, PtrTy, DL->getPointerABIAlignment(AddrSpace));
1851   MIB.setMemRefs({MemRef});
1852 }
1853 
1854 bool IRTranslator::translateOverflowIntrinsic(const CallInst &CI, unsigned Op,
1855                                               MachineIRBuilder &MIRBuilder) {
1856   ArrayRef<Register> ResRegs = getOrCreateVRegs(CI);
1857   MIRBuilder.buildInstr(
1858       Op, {ResRegs[0], ResRegs[1]},
1859       {getOrCreateVReg(*CI.getOperand(0)), getOrCreateVReg(*CI.getOperand(1))});
1860 
1861   return true;
1862 }
1863 
1864 bool IRTranslator::translateFixedPointIntrinsic(unsigned Op, const CallInst &CI,
1865                                                 MachineIRBuilder &MIRBuilder) {
1866   Register Dst = getOrCreateVReg(CI);
1867   Register Src0 = getOrCreateVReg(*CI.getOperand(0));
1868   Register Src1 = getOrCreateVReg(*CI.getOperand(1));
1869   uint64_t Scale = cast<ConstantInt>(CI.getOperand(2))->getZExtValue();
1870   MIRBuilder.buildInstr(Op, {Dst}, { Src0, Src1, Scale });
1871   return true;
1872 }
1873 
1874 unsigned IRTranslator::getSimpleIntrinsicOpcode(Intrinsic::ID ID) {
1875   switch (ID) {
1876     default:
1877       break;
1878     case Intrinsic::acos:
1879       return TargetOpcode::G_FACOS;
1880     case Intrinsic::asin:
1881       return TargetOpcode::G_FASIN;
1882     case Intrinsic::atan:
1883       return TargetOpcode::G_FATAN;
1884     case Intrinsic::atan2:
1885       return TargetOpcode::G_FATAN2;
1886     case Intrinsic::bswap:
1887       return TargetOpcode::G_BSWAP;
1888     case Intrinsic::bitreverse:
1889       return TargetOpcode::G_BITREVERSE;
1890     case Intrinsic::fshl:
1891       return TargetOpcode::G_FSHL;
1892     case Intrinsic::fshr:
1893       return TargetOpcode::G_FSHR;
1894     case Intrinsic::ceil:
1895       return TargetOpcode::G_FCEIL;
1896     case Intrinsic::cos:
1897       return TargetOpcode::G_FCOS;
1898     case Intrinsic::cosh:
1899       return TargetOpcode::G_FCOSH;
1900     case Intrinsic::ctpop:
1901       return TargetOpcode::G_CTPOP;
1902     case Intrinsic::exp:
1903       return TargetOpcode::G_FEXP;
1904     case Intrinsic::exp2:
1905       return TargetOpcode::G_FEXP2;
1906     case Intrinsic::exp10:
1907       return TargetOpcode::G_FEXP10;
1908     case Intrinsic::fabs:
1909       return TargetOpcode::G_FABS;
1910     case Intrinsic::copysign:
1911       return TargetOpcode::G_FCOPYSIGN;
1912     case Intrinsic::minnum:
1913       return TargetOpcode::G_FMINNUM;
1914     case Intrinsic::maxnum:
1915       return TargetOpcode::G_FMAXNUM;
1916     case Intrinsic::minimum:
1917       return TargetOpcode::G_FMINIMUM;
1918     case Intrinsic::maximum:
1919       return TargetOpcode::G_FMAXIMUM;
1920     case Intrinsic::canonicalize:
1921       return TargetOpcode::G_FCANONICALIZE;
1922     case Intrinsic::floor:
1923       return TargetOpcode::G_FFLOOR;
1924     case Intrinsic::fma:
1925       return TargetOpcode::G_FMA;
1926     case Intrinsic::log:
1927       return TargetOpcode::G_FLOG;
1928     case Intrinsic::log2:
1929       return TargetOpcode::G_FLOG2;
1930     case Intrinsic::log10:
1931       return TargetOpcode::G_FLOG10;
1932     case Intrinsic::ldexp:
1933       return TargetOpcode::G_FLDEXP;
1934     case Intrinsic::nearbyint:
1935       return TargetOpcode::G_FNEARBYINT;
1936     case Intrinsic::pow:
1937       return TargetOpcode::G_FPOW;
1938     case Intrinsic::powi:
1939       return TargetOpcode::G_FPOWI;
1940     case Intrinsic::rint:
1941       return TargetOpcode::G_FRINT;
1942     case Intrinsic::round:
1943       return TargetOpcode::G_INTRINSIC_ROUND;
1944     case Intrinsic::roundeven:
1945       return TargetOpcode::G_INTRINSIC_ROUNDEVEN;
1946     case Intrinsic::sin:
1947       return TargetOpcode::G_FSIN;
1948     case Intrinsic::sinh:
1949       return TargetOpcode::G_FSINH;
1950     case Intrinsic::sqrt:
1951       return TargetOpcode::G_FSQRT;
1952     case Intrinsic::tan:
1953       return TargetOpcode::G_FTAN;
1954     case Intrinsic::tanh:
1955       return TargetOpcode::G_FTANH;
1956     case Intrinsic::trunc:
1957       return TargetOpcode::G_INTRINSIC_TRUNC;
1958     case Intrinsic::readcyclecounter:
1959       return TargetOpcode::G_READCYCLECOUNTER;
1960     case Intrinsic::readsteadycounter:
1961       return TargetOpcode::G_READSTEADYCOUNTER;
1962     case Intrinsic::ptrmask:
1963       return TargetOpcode::G_PTRMASK;
1964     case Intrinsic::lrint:
1965       return TargetOpcode::G_INTRINSIC_LRINT;
1966     case Intrinsic::llrint:
1967       return TargetOpcode::G_INTRINSIC_LLRINT;
1968     // FADD/FMUL require checking the FMF, so are handled elsewhere.
1969     case Intrinsic::vector_reduce_fmin:
1970       return TargetOpcode::G_VECREDUCE_FMIN;
1971     case Intrinsic::vector_reduce_fmax:
1972       return TargetOpcode::G_VECREDUCE_FMAX;
1973     case Intrinsic::vector_reduce_fminimum:
1974       return TargetOpcode::G_VECREDUCE_FMINIMUM;
1975     case Intrinsic::vector_reduce_fmaximum:
1976       return TargetOpcode::G_VECREDUCE_FMAXIMUM;
1977     case Intrinsic::vector_reduce_add:
1978       return TargetOpcode::G_VECREDUCE_ADD;
1979     case Intrinsic::vector_reduce_mul:
1980       return TargetOpcode::G_VECREDUCE_MUL;
1981     case Intrinsic::vector_reduce_and:
1982       return TargetOpcode::G_VECREDUCE_AND;
1983     case Intrinsic::vector_reduce_or:
1984       return TargetOpcode::G_VECREDUCE_OR;
1985     case Intrinsic::vector_reduce_xor:
1986       return TargetOpcode::G_VECREDUCE_XOR;
1987     case Intrinsic::vector_reduce_smax:
1988       return TargetOpcode::G_VECREDUCE_SMAX;
1989     case Intrinsic::vector_reduce_smin:
1990       return TargetOpcode::G_VECREDUCE_SMIN;
1991     case Intrinsic::vector_reduce_umax:
1992       return TargetOpcode::G_VECREDUCE_UMAX;
1993     case Intrinsic::vector_reduce_umin:
1994       return TargetOpcode::G_VECREDUCE_UMIN;
1995     case Intrinsic::experimental_vector_compress:
1996       return TargetOpcode::G_VECTOR_COMPRESS;
1997     case Intrinsic::lround:
1998       return TargetOpcode::G_LROUND;
1999     case Intrinsic::llround:
2000       return TargetOpcode::G_LLROUND;
2001     case Intrinsic::get_fpenv:
2002       return TargetOpcode::G_GET_FPENV;
2003     case Intrinsic::get_fpmode:
2004       return TargetOpcode::G_GET_FPMODE;
2005   }
2006   return Intrinsic::not_intrinsic;
2007 }
2008 
2009 bool IRTranslator::translateSimpleIntrinsic(const CallInst &CI,
2010                                             Intrinsic::ID ID,
2011                                             MachineIRBuilder &MIRBuilder) {
2012 
2013   unsigned Op = getSimpleIntrinsicOpcode(ID);
2014 
2015   // Is this a simple intrinsic?
2016   if (Op == Intrinsic::not_intrinsic)
2017     return false;
2018 
2019   // Yes. Let's translate it.
2020   SmallVector<llvm::SrcOp, 4> VRegs;
2021   for (const auto &Arg : CI.args())
2022     VRegs.push_back(getOrCreateVReg(*Arg));
2023 
2024   MIRBuilder.buildInstr(Op, {getOrCreateVReg(CI)}, VRegs,
2025                         MachineInstr::copyFlagsFromInstruction(CI));
2026   return true;
2027 }
2028 
2029 // TODO: Include ConstainedOps.def when all strict instructions are defined.
2030 static unsigned getConstrainedOpcode(Intrinsic::ID ID) {
2031   switch (ID) {
2032   case Intrinsic::experimental_constrained_fadd:
2033     return TargetOpcode::G_STRICT_FADD;
2034   case Intrinsic::experimental_constrained_fsub:
2035     return TargetOpcode::G_STRICT_FSUB;
2036   case Intrinsic::experimental_constrained_fmul:
2037     return TargetOpcode::G_STRICT_FMUL;
2038   case Intrinsic::experimental_constrained_fdiv:
2039     return TargetOpcode::G_STRICT_FDIV;
2040   case Intrinsic::experimental_constrained_frem:
2041     return TargetOpcode::G_STRICT_FREM;
2042   case Intrinsic::experimental_constrained_fma:
2043     return TargetOpcode::G_STRICT_FMA;
2044   case Intrinsic::experimental_constrained_sqrt:
2045     return TargetOpcode::G_STRICT_FSQRT;
2046   case Intrinsic::experimental_constrained_ldexp:
2047     return TargetOpcode::G_STRICT_FLDEXP;
2048   default:
2049     return 0;
2050   }
2051 }
2052 
2053 bool IRTranslator::translateConstrainedFPIntrinsic(
2054   const ConstrainedFPIntrinsic &FPI, MachineIRBuilder &MIRBuilder) {
2055   fp::ExceptionBehavior EB = *FPI.getExceptionBehavior();
2056 
2057   unsigned Opcode = getConstrainedOpcode(FPI.getIntrinsicID());
2058   if (!Opcode)
2059     return false;
2060 
2061   uint32_t Flags = MachineInstr::copyFlagsFromInstruction(FPI);
2062   if (EB == fp::ExceptionBehavior::ebIgnore)
2063     Flags |= MachineInstr::NoFPExcept;
2064 
2065   SmallVector<llvm::SrcOp, 4> VRegs;
2066   for (unsigned I = 0, E = FPI.getNonMetadataArgCount(); I != E; ++I)
2067     VRegs.push_back(getOrCreateVReg(*FPI.getArgOperand(I)));
2068 
2069   MIRBuilder.buildInstr(Opcode, {getOrCreateVReg(FPI)}, VRegs, Flags);
2070   return true;
2071 }
2072 
2073 std::optional<MCRegister> IRTranslator::getArgPhysReg(Argument &Arg) {
2074   auto VRegs = getOrCreateVRegs(Arg);
2075   if (VRegs.size() != 1)
2076     return std::nullopt;
2077 
2078   // Arguments are lowered as a copy of a livein physical register.
2079   auto *VRegDef = MF->getRegInfo().getVRegDef(VRegs[0]);
2080   if (!VRegDef || !VRegDef->isCopy())
2081     return std::nullopt;
2082   return VRegDef->getOperand(1).getReg().asMCReg();
2083 }
2084 
2085 bool IRTranslator::translateIfEntryValueArgument(bool isDeclare, Value *Val,
2086                                                  const DILocalVariable *Var,
2087                                                  const DIExpression *Expr,
2088                                                  const DebugLoc &DL,
2089                                                  MachineIRBuilder &MIRBuilder) {
2090   auto *Arg = dyn_cast<Argument>(Val);
2091   if (!Arg)
2092     return false;
2093 
2094   if (!Expr->isEntryValue())
2095     return false;
2096 
2097   std::optional<MCRegister> PhysReg = getArgPhysReg(*Arg);
2098   if (!PhysReg) {
2099     LLVM_DEBUG(dbgs() << "Dropping dbg." << (isDeclare ? "declare" : "value")
2100                       << ": expression is entry_value but "
2101                       << "couldn't find a physical register\n");
2102     LLVM_DEBUG(dbgs() << *Var << "\n");
2103     return true;
2104   }
2105 
2106   if (isDeclare) {
2107     // Append an op deref to account for the fact that this is a dbg_declare.
2108     Expr = DIExpression::append(Expr, dwarf::DW_OP_deref);
2109     MF->setVariableDbgInfo(Var, Expr, *PhysReg, DL);
2110   } else {
2111     MIRBuilder.buildDirectDbgValue(*PhysReg, Var, Expr);
2112   }
2113 
2114   return true;
2115 }
2116 
2117 static unsigned getConvOpcode(Intrinsic::ID ID) {
2118   switch (ID) {
2119   default:
2120     llvm_unreachable("Unexpected intrinsic");
2121   case Intrinsic::experimental_convergence_anchor:
2122     return TargetOpcode::CONVERGENCECTRL_ANCHOR;
2123   case Intrinsic::experimental_convergence_entry:
2124     return TargetOpcode::CONVERGENCECTRL_ENTRY;
2125   case Intrinsic::experimental_convergence_loop:
2126     return TargetOpcode::CONVERGENCECTRL_LOOP;
2127   }
2128 }
2129 
2130 bool IRTranslator::translateConvergenceControlIntrinsic(
2131     const CallInst &CI, Intrinsic::ID ID, MachineIRBuilder &MIRBuilder) {
2132   MachineInstrBuilder MIB = MIRBuilder.buildInstr(getConvOpcode(ID));
2133   Register OutputReg = getOrCreateConvergenceTokenVReg(CI);
2134   MIB.addDef(OutputReg);
2135 
2136   if (ID == Intrinsic::experimental_convergence_loop) {
2137     auto Bundle = CI.getOperandBundle(LLVMContext::OB_convergencectrl);
2138     assert(Bundle && "Expected a convergence control token.");
2139     Register InputReg =
2140         getOrCreateConvergenceTokenVReg(*Bundle->Inputs[0].get());
2141     MIB.addUse(InputReg);
2142   }
2143 
2144   return true;
2145 }
2146 
2147 bool IRTranslator::translateKnownIntrinsic(const CallInst &CI, Intrinsic::ID ID,
2148                                            MachineIRBuilder &MIRBuilder) {
2149   if (auto *MI = dyn_cast<AnyMemIntrinsic>(&CI)) {
2150     if (ORE->enabled()) {
2151       if (MemoryOpRemark::canHandle(MI, *LibInfo)) {
2152         MemoryOpRemark R(*ORE, "gisel-irtranslator-memsize", *DL, *LibInfo);
2153         R.visit(MI);
2154       }
2155     }
2156   }
2157 
2158   // If this is a simple intrinsic (that is, we just need to add a def of
2159   // a vreg, and uses for each arg operand, then translate it.
2160   if (translateSimpleIntrinsic(CI, ID, MIRBuilder))
2161     return true;
2162 
2163   switch (ID) {
2164   default:
2165     break;
2166   case Intrinsic::lifetime_start:
2167   case Intrinsic::lifetime_end: {
2168     // No stack colouring in O0, discard region information.
2169     if (MF->getTarget().getOptLevel() == CodeGenOptLevel::None ||
2170         MF->getFunction().hasOptNone())
2171       return true;
2172 
2173     unsigned Op = ID == Intrinsic::lifetime_start ? TargetOpcode::LIFETIME_START
2174                                                   : TargetOpcode::LIFETIME_END;
2175 
2176     // Get the underlying objects for the location passed on the lifetime
2177     // marker.
2178     SmallVector<const Value *, 4> Allocas;
2179     getUnderlyingObjects(CI.getArgOperand(1), Allocas);
2180 
2181     // Iterate over each underlying object, creating lifetime markers for each
2182     // static alloca. Quit if we find a non-static alloca.
2183     for (const Value *V : Allocas) {
2184       const AllocaInst *AI = dyn_cast<AllocaInst>(V);
2185       if (!AI)
2186         continue;
2187 
2188       if (!AI->isStaticAlloca())
2189         return true;
2190 
2191       MIRBuilder.buildInstr(Op).addFrameIndex(getOrCreateFrameIndex(*AI));
2192     }
2193     return true;
2194   }
2195   case Intrinsic::fake_use: {
2196     SmallVector<llvm::SrcOp, 4> VRegs;
2197     for (const auto &Arg : CI.args())
2198       for (auto VReg : getOrCreateVRegs(*Arg))
2199         VRegs.push_back(VReg);
2200     MIRBuilder.buildInstr(TargetOpcode::FAKE_USE, {}, VRegs);
2201     MF->setHasFakeUses(true);
2202     return true;
2203   }
2204   case Intrinsic::dbg_declare: {
2205     const DbgDeclareInst &DI = cast<DbgDeclareInst>(CI);
2206     assert(DI.getVariable() && "Missing variable");
2207     translateDbgDeclareRecord(DI.getAddress(), DI.hasArgList(), DI.getVariable(),
2208                        DI.getExpression(), DI.getDebugLoc(), MIRBuilder);
2209     return true;
2210   }
2211   case Intrinsic::dbg_label: {
2212     const DbgLabelInst &DI = cast<DbgLabelInst>(CI);
2213     assert(DI.getLabel() && "Missing label");
2214 
2215     assert(DI.getLabel()->isValidLocationForIntrinsic(
2216                MIRBuilder.getDebugLoc()) &&
2217            "Expected inlined-at fields to agree");
2218 
2219     MIRBuilder.buildDbgLabel(DI.getLabel());
2220     return true;
2221   }
2222   case Intrinsic::vaend:
2223     // No target I know of cares about va_end. Certainly no in-tree target
2224     // does. Simplest intrinsic ever!
2225     return true;
2226   case Intrinsic::vastart: {
2227     Value *Ptr = CI.getArgOperand(0);
2228     unsigned ListSize = TLI->getVaListSizeInBits(*DL) / 8;
2229     Align Alignment = getKnownAlignment(Ptr, *DL);
2230 
2231     MIRBuilder.buildInstr(TargetOpcode::G_VASTART, {}, {getOrCreateVReg(*Ptr)})
2232         .addMemOperand(MF->getMachineMemOperand(MachinePointerInfo(Ptr),
2233                                                 MachineMemOperand::MOStore,
2234                                                 ListSize, Alignment));
2235     return true;
2236   }
2237   case Intrinsic::dbg_assign:
2238     // A dbg.assign is a dbg.value with more information about stack locations,
2239     // typically produced during optimisation of variables with leaked
2240     // addresses. We can treat it like a normal dbg_value intrinsic here; to
2241     // benefit from the full analysis of stack/SSA locations, GlobalISel would
2242     // need to register for and use the AssignmentTrackingAnalysis pass.
2243     [[fallthrough]];
2244   case Intrinsic::dbg_value: {
2245     // This form of DBG_VALUE is target-independent.
2246     const DbgValueInst &DI = cast<DbgValueInst>(CI);
2247     translateDbgValueRecord(DI.getValue(), DI.hasArgList(), DI.getVariable(),
2248                        DI.getExpression(), DI.getDebugLoc(), MIRBuilder);
2249     return true;
2250   }
2251   case Intrinsic::uadd_with_overflow:
2252     return translateOverflowIntrinsic(CI, TargetOpcode::G_UADDO, MIRBuilder);
2253   case Intrinsic::sadd_with_overflow:
2254     return translateOverflowIntrinsic(CI, TargetOpcode::G_SADDO, MIRBuilder);
2255   case Intrinsic::usub_with_overflow:
2256     return translateOverflowIntrinsic(CI, TargetOpcode::G_USUBO, MIRBuilder);
2257   case Intrinsic::ssub_with_overflow:
2258     return translateOverflowIntrinsic(CI, TargetOpcode::G_SSUBO, MIRBuilder);
2259   case Intrinsic::umul_with_overflow:
2260     return translateOverflowIntrinsic(CI, TargetOpcode::G_UMULO, MIRBuilder);
2261   case Intrinsic::smul_with_overflow:
2262     return translateOverflowIntrinsic(CI, TargetOpcode::G_SMULO, MIRBuilder);
2263   case Intrinsic::uadd_sat:
2264     return translateBinaryOp(TargetOpcode::G_UADDSAT, CI, MIRBuilder);
2265   case Intrinsic::sadd_sat:
2266     return translateBinaryOp(TargetOpcode::G_SADDSAT, CI, MIRBuilder);
2267   case Intrinsic::usub_sat:
2268     return translateBinaryOp(TargetOpcode::G_USUBSAT, CI, MIRBuilder);
2269   case Intrinsic::ssub_sat:
2270     return translateBinaryOp(TargetOpcode::G_SSUBSAT, CI, MIRBuilder);
2271   case Intrinsic::ushl_sat:
2272     return translateBinaryOp(TargetOpcode::G_USHLSAT, CI, MIRBuilder);
2273   case Intrinsic::sshl_sat:
2274     return translateBinaryOp(TargetOpcode::G_SSHLSAT, CI, MIRBuilder);
2275   case Intrinsic::umin:
2276     return translateBinaryOp(TargetOpcode::G_UMIN, CI, MIRBuilder);
2277   case Intrinsic::umax:
2278     return translateBinaryOp(TargetOpcode::G_UMAX, CI, MIRBuilder);
2279   case Intrinsic::smin:
2280     return translateBinaryOp(TargetOpcode::G_SMIN, CI, MIRBuilder);
2281   case Intrinsic::smax:
2282     return translateBinaryOp(TargetOpcode::G_SMAX, CI, MIRBuilder);
2283   case Intrinsic::abs:
2284     // TODO: Preserve "int min is poison" arg in GMIR?
2285     return translateUnaryOp(TargetOpcode::G_ABS, CI, MIRBuilder);
2286   case Intrinsic::smul_fix:
2287     return translateFixedPointIntrinsic(TargetOpcode::G_SMULFIX, CI, MIRBuilder);
2288   case Intrinsic::umul_fix:
2289     return translateFixedPointIntrinsic(TargetOpcode::G_UMULFIX, CI, MIRBuilder);
2290   case Intrinsic::smul_fix_sat:
2291     return translateFixedPointIntrinsic(TargetOpcode::G_SMULFIXSAT, CI, MIRBuilder);
2292   case Intrinsic::umul_fix_sat:
2293     return translateFixedPointIntrinsic(TargetOpcode::G_UMULFIXSAT, CI, MIRBuilder);
2294   case Intrinsic::sdiv_fix:
2295     return translateFixedPointIntrinsic(TargetOpcode::G_SDIVFIX, CI, MIRBuilder);
2296   case Intrinsic::udiv_fix:
2297     return translateFixedPointIntrinsic(TargetOpcode::G_UDIVFIX, CI, MIRBuilder);
2298   case Intrinsic::sdiv_fix_sat:
2299     return translateFixedPointIntrinsic(TargetOpcode::G_SDIVFIXSAT, CI, MIRBuilder);
2300   case Intrinsic::udiv_fix_sat:
2301     return translateFixedPointIntrinsic(TargetOpcode::G_UDIVFIXSAT, CI, MIRBuilder);
2302   case Intrinsic::fmuladd: {
2303     const TargetMachine &TM = MF->getTarget();
2304     Register Dst = getOrCreateVReg(CI);
2305     Register Op0 = getOrCreateVReg(*CI.getArgOperand(0));
2306     Register Op1 = getOrCreateVReg(*CI.getArgOperand(1));
2307     Register Op2 = getOrCreateVReg(*CI.getArgOperand(2));
2308     if (TM.Options.AllowFPOpFusion != FPOpFusion::Strict &&
2309         TLI->isFMAFasterThanFMulAndFAdd(*MF,
2310                                         TLI->getValueType(*DL, CI.getType()))) {
2311       // TODO: Revisit this to see if we should move this part of the
2312       // lowering to the combiner.
2313       MIRBuilder.buildFMA(Dst, Op0, Op1, Op2,
2314                           MachineInstr::copyFlagsFromInstruction(CI));
2315     } else {
2316       LLT Ty = getLLTForType(*CI.getType(), *DL);
2317       auto FMul = MIRBuilder.buildFMul(
2318           Ty, Op0, Op1, MachineInstr::copyFlagsFromInstruction(CI));
2319       MIRBuilder.buildFAdd(Dst, FMul, Op2,
2320                            MachineInstr::copyFlagsFromInstruction(CI));
2321     }
2322     return true;
2323   }
2324   case Intrinsic::convert_from_fp16:
2325     // FIXME: This intrinsic should probably be removed from the IR.
2326     MIRBuilder.buildFPExt(getOrCreateVReg(CI),
2327                           getOrCreateVReg(*CI.getArgOperand(0)),
2328                           MachineInstr::copyFlagsFromInstruction(CI));
2329     return true;
2330   case Intrinsic::convert_to_fp16:
2331     // FIXME: This intrinsic should probably be removed from the IR.
2332     MIRBuilder.buildFPTrunc(getOrCreateVReg(CI),
2333                             getOrCreateVReg(*CI.getArgOperand(0)),
2334                             MachineInstr::copyFlagsFromInstruction(CI));
2335     return true;
2336   case Intrinsic::frexp: {
2337     ArrayRef<Register> VRegs = getOrCreateVRegs(CI);
2338     MIRBuilder.buildFFrexp(VRegs[0], VRegs[1],
2339                            getOrCreateVReg(*CI.getArgOperand(0)),
2340                            MachineInstr::copyFlagsFromInstruction(CI));
2341     return true;
2342   }
2343   case Intrinsic::sincos: {
2344     ArrayRef<Register> VRegs = getOrCreateVRegs(CI);
2345     MIRBuilder.buildFSincos(VRegs[0], VRegs[1],
2346                             getOrCreateVReg(*CI.getArgOperand(0)),
2347                             MachineInstr::copyFlagsFromInstruction(CI));
2348     return true;
2349   }
2350   case Intrinsic::fptosi_sat:
2351     MIRBuilder.buildFPTOSI_SAT(getOrCreateVReg(CI),
2352                                getOrCreateVReg(*CI.getArgOperand(0)));
2353     return true;
2354   case Intrinsic::fptoui_sat:
2355     MIRBuilder.buildFPTOUI_SAT(getOrCreateVReg(CI),
2356                                getOrCreateVReg(*CI.getArgOperand(0)));
2357     return true;
2358   case Intrinsic::memcpy_inline:
2359     return translateMemFunc(CI, MIRBuilder, TargetOpcode::G_MEMCPY_INLINE);
2360   case Intrinsic::memcpy:
2361     return translateMemFunc(CI, MIRBuilder, TargetOpcode::G_MEMCPY);
2362   case Intrinsic::memmove:
2363     return translateMemFunc(CI, MIRBuilder, TargetOpcode::G_MEMMOVE);
2364   case Intrinsic::memset:
2365     return translateMemFunc(CI, MIRBuilder, TargetOpcode::G_MEMSET);
2366   case Intrinsic::eh_typeid_for: {
2367     GlobalValue *GV = ExtractTypeInfo(CI.getArgOperand(0));
2368     Register Reg = getOrCreateVReg(CI);
2369     unsigned TypeID = MF->getTypeIDFor(GV);
2370     MIRBuilder.buildConstant(Reg, TypeID);
2371     return true;
2372   }
2373   case Intrinsic::objectsize:
2374     llvm_unreachable("llvm.objectsize.* should have been lowered already");
2375 
2376   case Intrinsic::is_constant:
2377     llvm_unreachable("llvm.is.constant.* should have been lowered already");
2378 
2379   case Intrinsic::stackguard:
2380     getStackGuard(getOrCreateVReg(CI), MIRBuilder);
2381     return true;
2382   case Intrinsic::stackprotector: {
2383     LLT PtrTy = getLLTForType(*CI.getArgOperand(0)->getType(), *DL);
2384     Register GuardVal;
2385     if (TLI->useLoadStackGuardNode(*CI.getModule())) {
2386       GuardVal = MRI->createGenericVirtualRegister(PtrTy);
2387       getStackGuard(GuardVal, MIRBuilder);
2388     } else
2389       GuardVal = getOrCreateVReg(*CI.getArgOperand(0)); // The guard's value.
2390 
2391     AllocaInst *Slot = cast<AllocaInst>(CI.getArgOperand(1));
2392     int FI = getOrCreateFrameIndex(*Slot);
2393     MF->getFrameInfo().setStackProtectorIndex(FI);
2394 
2395     MIRBuilder.buildStore(
2396         GuardVal, getOrCreateVReg(*Slot),
2397         *MF->getMachineMemOperand(MachinePointerInfo::getFixedStack(*MF, FI),
2398                                   MachineMemOperand::MOStore |
2399                                       MachineMemOperand::MOVolatile,
2400                                   PtrTy, Align(8)));
2401     return true;
2402   }
2403   case Intrinsic::stacksave: {
2404     MIRBuilder.buildInstr(TargetOpcode::G_STACKSAVE, {getOrCreateVReg(CI)}, {});
2405     return true;
2406   }
2407   case Intrinsic::stackrestore: {
2408     MIRBuilder.buildInstr(TargetOpcode::G_STACKRESTORE, {},
2409                           {getOrCreateVReg(*CI.getArgOperand(0))});
2410     return true;
2411   }
2412   case Intrinsic::cttz:
2413   case Intrinsic::ctlz: {
2414     ConstantInt *Cst = cast<ConstantInt>(CI.getArgOperand(1));
2415     bool isTrailing = ID == Intrinsic::cttz;
2416     unsigned Opcode = isTrailing
2417                           ? Cst->isZero() ? TargetOpcode::G_CTTZ
2418                                           : TargetOpcode::G_CTTZ_ZERO_UNDEF
2419                           : Cst->isZero() ? TargetOpcode::G_CTLZ
2420                                           : TargetOpcode::G_CTLZ_ZERO_UNDEF;
2421     MIRBuilder.buildInstr(Opcode, {getOrCreateVReg(CI)},
2422                           {getOrCreateVReg(*CI.getArgOperand(0))});
2423     return true;
2424   }
2425   case Intrinsic::invariant_start: {
2426     LLT PtrTy = getLLTForType(*CI.getArgOperand(0)->getType(), *DL);
2427     Register Undef = MRI->createGenericVirtualRegister(PtrTy);
2428     MIRBuilder.buildUndef(Undef);
2429     return true;
2430   }
2431   case Intrinsic::invariant_end:
2432     return true;
2433   case Intrinsic::expect:
2434   case Intrinsic::annotation:
2435   case Intrinsic::ptr_annotation:
2436   case Intrinsic::launder_invariant_group:
2437   case Intrinsic::strip_invariant_group: {
2438     // Drop the intrinsic, but forward the value.
2439     MIRBuilder.buildCopy(getOrCreateVReg(CI),
2440                          getOrCreateVReg(*CI.getArgOperand(0)));
2441     return true;
2442   }
2443   case Intrinsic::assume:
2444   case Intrinsic::experimental_noalias_scope_decl:
2445   case Intrinsic::var_annotation:
2446   case Intrinsic::sideeffect:
2447     // Discard annotate attributes, assumptions, and artificial side-effects.
2448     return true;
2449   case Intrinsic::read_volatile_register:
2450   case Intrinsic::read_register: {
2451     Value *Arg = CI.getArgOperand(0);
2452     MIRBuilder
2453         .buildInstr(TargetOpcode::G_READ_REGISTER, {getOrCreateVReg(CI)}, {})
2454         .addMetadata(cast<MDNode>(cast<MetadataAsValue>(Arg)->getMetadata()));
2455     return true;
2456   }
2457   case Intrinsic::write_register: {
2458     Value *Arg = CI.getArgOperand(0);
2459     MIRBuilder.buildInstr(TargetOpcode::G_WRITE_REGISTER)
2460       .addMetadata(cast<MDNode>(cast<MetadataAsValue>(Arg)->getMetadata()))
2461       .addUse(getOrCreateVReg(*CI.getArgOperand(1)));
2462     return true;
2463   }
2464   case Intrinsic::localescape: {
2465     MachineBasicBlock &EntryMBB = MF->front();
2466     StringRef EscapedName = GlobalValue::dropLLVMManglingEscape(MF->getName());
2467 
2468     // Directly emit some LOCAL_ESCAPE machine instrs. Label assignment emission
2469     // is the same on all targets.
2470     for (unsigned Idx = 0, E = CI.arg_size(); Idx < E; ++Idx) {
2471       Value *Arg = CI.getArgOperand(Idx)->stripPointerCasts();
2472       if (isa<ConstantPointerNull>(Arg))
2473         continue; // Skip null pointers. They represent a hole in index space.
2474 
2475       int FI = getOrCreateFrameIndex(*cast<AllocaInst>(Arg));
2476       MCSymbol *FrameAllocSym =
2477           MF->getContext().getOrCreateFrameAllocSymbol(EscapedName, Idx);
2478 
2479       // This should be inserted at the start of the entry block.
2480       auto LocalEscape =
2481           MIRBuilder.buildInstrNoInsert(TargetOpcode::LOCAL_ESCAPE)
2482               .addSym(FrameAllocSym)
2483               .addFrameIndex(FI);
2484 
2485       EntryMBB.insert(EntryMBB.begin(), LocalEscape);
2486     }
2487 
2488     return true;
2489   }
2490   case Intrinsic::vector_reduce_fadd:
2491   case Intrinsic::vector_reduce_fmul: {
2492     // Need to check for the reassoc flag to decide whether we want a
2493     // sequential reduction opcode or not.
2494     Register Dst = getOrCreateVReg(CI);
2495     Register ScalarSrc = getOrCreateVReg(*CI.getArgOperand(0));
2496     Register VecSrc = getOrCreateVReg(*CI.getArgOperand(1));
2497     unsigned Opc = 0;
2498     if (!CI.hasAllowReassoc()) {
2499       // The sequential ordering case.
2500       Opc = ID == Intrinsic::vector_reduce_fadd
2501                 ? TargetOpcode::G_VECREDUCE_SEQ_FADD
2502                 : TargetOpcode::G_VECREDUCE_SEQ_FMUL;
2503       MIRBuilder.buildInstr(Opc, {Dst}, {ScalarSrc, VecSrc},
2504                             MachineInstr::copyFlagsFromInstruction(CI));
2505       return true;
2506     }
2507     // We split the operation into a separate G_FADD/G_FMUL + the reduce,
2508     // since the associativity doesn't matter.
2509     unsigned ScalarOpc;
2510     if (ID == Intrinsic::vector_reduce_fadd) {
2511       Opc = TargetOpcode::G_VECREDUCE_FADD;
2512       ScalarOpc = TargetOpcode::G_FADD;
2513     } else {
2514       Opc = TargetOpcode::G_VECREDUCE_FMUL;
2515       ScalarOpc = TargetOpcode::G_FMUL;
2516     }
2517     LLT DstTy = MRI->getType(Dst);
2518     auto Rdx = MIRBuilder.buildInstr(
2519         Opc, {DstTy}, {VecSrc}, MachineInstr::copyFlagsFromInstruction(CI));
2520     MIRBuilder.buildInstr(ScalarOpc, {Dst}, {ScalarSrc, Rdx},
2521                           MachineInstr::copyFlagsFromInstruction(CI));
2522 
2523     return true;
2524   }
2525   case Intrinsic::trap:
2526     return translateTrap(CI, MIRBuilder, TargetOpcode::G_TRAP);
2527   case Intrinsic::debugtrap:
2528     return translateTrap(CI, MIRBuilder, TargetOpcode::G_DEBUGTRAP);
2529   case Intrinsic::ubsantrap:
2530     return translateTrap(CI, MIRBuilder, TargetOpcode::G_UBSANTRAP);
2531   case Intrinsic::allow_runtime_check:
2532   case Intrinsic::allow_ubsan_check:
2533     MIRBuilder.buildCopy(getOrCreateVReg(CI),
2534                          getOrCreateVReg(*ConstantInt::getTrue(CI.getType())));
2535     return true;
2536   case Intrinsic::amdgcn_cs_chain:
2537     return translateCallBase(CI, MIRBuilder);
2538   case Intrinsic::fptrunc_round: {
2539     uint32_t Flags = MachineInstr::copyFlagsFromInstruction(CI);
2540 
2541     // Convert the metadata argument to a constant integer
2542     Metadata *MD = cast<MetadataAsValue>(CI.getArgOperand(1))->getMetadata();
2543     std::optional<RoundingMode> RoundMode =
2544         convertStrToRoundingMode(cast<MDString>(MD)->getString());
2545 
2546     // Add the Rounding mode as an integer
2547     MIRBuilder
2548         .buildInstr(TargetOpcode::G_INTRINSIC_FPTRUNC_ROUND,
2549                     {getOrCreateVReg(CI)},
2550                     {getOrCreateVReg(*CI.getArgOperand(0))}, Flags)
2551         .addImm((int)*RoundMode);
2552 
2553     return true;
2554   }
2555   case Intrinsic::is_fpclass: {
2556     Value *FpValue = CI.getOperand(0);
2557     ConstantInt *TestMaskValue = cast<ConstantInt>(CI.getOperand(1));
2558 
2559     MIRBuilder
2560         .buildInstr(TargetOpcode::G_IS_FPCLASS, {getOrCreateVReg(CI)},
2561                     {getOrCreateVReg(*FpValue)})
2562         .addImm(TestMaskValue->getZExtValue());
2563 
2564     return true;
2565   }
2566   case Intrinsic::set_fpenv: {
2567     Value *FPEnv = CI.getOperand(0);
2568     MIRBuilder.buildSetFPEnv(getOrCreateVReg(*FPEnv));
2569     return true;
2570   }
2571   case Intrinsic::reset_fpenv:
2572     MIRBuilder.buildResetFPEnv();
2573     return true;
2574   case Intrinsic::set_fpmode: {
2575     Value *FPState = CI.getOperand(0);
2576     MIRBuilder.buildSetFPMode(getOrCreateVReg(*FPState));
2577     return true;
2578   }
2579   case Intrinsic::reset_fpmode:
2580     MIRBuilder.buildResetFPMode();
2581     return true;
2582   case Intrinsic::vscale: {
2583     MIRBuilder.buildVScale(getOrCreateVReg(CI), 1);
2584     return true;
2585   }
2586   case Intrinsic::scmp:
2587     MIRBuilder.buildSCmp(getOrCreateVReg(CI),
2588                          getOrCreateVReg(*CI.getOperand(0)),
2589                          getOrCreateVReg(*CI.getOperand(1)));
2590     return true;
2591   case Intrinsic::ucmp:
2592     MIRBuilder.buildUCmp(getOrCreateVReg(CI),
2593                          getOrCreateVReg(*CI.getOperand(0)),
2594                          getOrCreateVReg(*CI.getOperand(1)));
2595     return true;
2596   case Intrinsic::vector_extract:
2597     return translateExtractVector(CI, MIRBuilder);
2598   case Intrinsic::vector_insert:
2599     return translateInsertVector(CI, MIRBuilder);
2600   case Intrinsic::stepvector: {
2601     MIRBuilder.buildStepVector(getOrCreateVReg(CI), 1);
2602     return true;
2603   }
2604   case Intrinsic::prefetch: {
2605     Value *Addr = CI.getOperand(0);
2606     unsigned RW = cast<ConstantInt>(CI.getOperand(1))->getZExtValue();
2607     unsigned Locality = cast<ConstantInt>(CI.getOperand(2))->getZExtValue();
2608     unsigned CacheType = cast<ConstantInt>(CI.getOperand(3))->getZExtValue();
2609 
2610     auto Flags = RW ? MachineMemOperand::MOStore : MachineMemOperand::MOLoad;
2611     auto &MMO = *MF->getMachineMemOperand(MachinePointerInfo(Addr), Flags,
2612                                           LLT(), Align());
2613 
2614     MIRBuilder.buildPrefetch(getOrCreateVReg(*Addr), RW, Locality, CacheType,
2615                              MMO);
2616 
2617     return true;
2618   }
2619 
2620   case Intrinsic::vector_interleave2:
2621   case Intrinsic::vector_deinterleave2: {
2622     // Both intrinsics have at least one operand.
2623     Value *Op0 = CI.getOperand(0);
2624     LLT ResTy = getLLTForType(*Op0->getType(), MIRBuilder.getDataLayout());
2625     if (!ResTy.isFixedVector())
2626       return false;
2627 
2628     if (CI.getIntrinsicID() == Intrinsic::vector_interleave2)
2629       return translateVectorInterleave2Intrinsic(CI, MIRBuilder);
2630 
2631     return translateVectorDeinterleave2Intrinsic(CI, MIRBuilder);
2632   }
2633 
2634 #define INSTRUCTION(NAME, NARG, ROUND_MODE, INTRINSIC)  \
2635   case Intrinsic::INTRINSIC:
2636 #include "llvm/IR/ConstrainedOps.def"
2637     return translateConstrainedFPIntrinsic(cast<ConstrainedFPIntrinsic>(CI),
2638                                            MIRBuilder);
2639   case Intrinsic::experimental_convergence_anchor:
2640   case Intrinsic::experimental_convergence_entry:
2641   case Intrinsic::experimental_convergence_loop:
2642     return translateConvergenceControlIntrinsic(CI, ID, MIRBuilder);
2643   }
2644   return false;
2645 }
2646 
2647 bool IRTranslator::translateInlineAsm(const CallBase &CB,
2648                                       MachineIRBuilder &MIRBuilder) {
2649 
2650   const InlineAsmLowering *ALI = MF->getSubtarget().getInlineAsmLowering();
2651 
2652   if (!ALI) {
2653     LLVM_DEBUG(
2654         dbgs() << "Inline asm lowering is not supported for this target yet\n");
2655     return false;
2656   }
2657 
2658   return ALI->lowerInlineAsm(
2659       MIRBuilder, CB, [&](const Value &Val) { return getOrCreateVRegs(Val); });
2660 }
2661 
2662 bool IRTranslator::translateCallBase(const CallBase &CB,
2663                                      MachineIRBuilder &MIRBuilder) {
2664   ArrayRef<Register> Res = getOrCreateVRegs(CB);
2665 
2666   SmallVector<ArrayRef<Register>, 8> Args;
2667   Register SwiftInVReg = 0;
2668   Register SwiftErrorVReg = 0;
2669   for (const auto &Arg : CB.args()) {
2670     if (CLI->supportSwiftError() && isSwiftError(Arg)) {
2671       assert(SwiftInVReg == 0 && "Expected only one swift error argument");
2672       LLT Ty = getLLTForType(*Arg->getType(), *DL);
2673       SwiftInVReg = MRI->createGenericVirtualRegister(Ty);
2674       MIRBuilder.buildCopy(SwiftInVReg, SwiftError.getOrCreateVRegUseAt(
2675                                             &CB, &MIRBuilder.getMBB(), Arg));
2676       Args.emplace_back(ArrayRef(SwiftInVReg));
2677       SwiftErrorVReg =
2678           SwiftError.getOrCreateVRegDefAt(&CB, &MIRBuilder.getMBB(), Arg);
2679       continue;
2680     }
2681     Args.push_back(getOrCreateVRegs(*Arg));
2682   }
2683 
2684   if (auto *CI = dyn_cast<CallInst>(&CB)) {
2685     if (ORE->enabled()) {
2686       if (MemoryOpRemark::canHandle(CI, *LibInfo)) {
2687         MemoryOpRemark R(*ORE, "gisel-irtranslator-memsize", *DL, *LibInfo);
2688         R.visit(CI);
2689       }
2690     }
2691   }
2692 
2693   std::optional<CallLowering::PtrAuthInfo> PAI;
2694   if (auto Bundle = CB.getOperandBundle(LLVMContext::OB_ptrauth)) {
2695     // Functions should never be ptrauth-called directly.
2696     assert(!CB.getCalledFunction() && "invalid direct ptrauth call");
2697 
2698     const Value *Key = Bundle->Inputs[0];
2699     const Value *Discriminator = Bundle->Inputs[1];
2700 
2701     // Look through ptrauth constants to try to eliminate the matching bundle
2702     // and turn this into a direct call with no ptrauth.
2703     // CallLowering will use the raw pointer if it doesn't find the PAI.
2704     const auto *CalleeCPA = dyn_cast<ConstantPtrAuth>(CB.getCalledOperand());
2705     if (!CalleeCPA || !isa<Function>(CalleeCPA->getPointer()) ||
2706         !CalleeCPA->isKnownCompatibleWith(Key, Discriminator, *DL)) {
2707       // If we can't make it direct, package the bundle into PAI.
2708       Register DiscReg = getOrCreateVReg(*Discriminator);
2709       PAI = CallLowering::PtrAuthInfo{cast<ConstantInt>(Key)->getZExtValue(),
2710                                       DiscReg};
2711     }
2712   }
2713 
2714   Register ConvergenceCtrlToken = 0;
2715   if (auto Bundle = CB.getOperandBundle(LLVMContext::OB_convergencectrl)) {
2716     const auto &Token = *Bundle->Inputs[0].get();
2717     ConvergenceCtrlToken = getOrCreateConvergenceTokenVReg(Token);
2718   }
2719 
2720   // We don't set HasCalls on MFI here yet because call lowering may decide to
2721   // optimize into tail calls. Instead, we defer that to selection where a final
2722   // scan is done to check if any instructions are calls.
2723   bool Success = CLI->lowerCall(
2724       MIRBuilder, CB, Res, Args, SwiftErrorVReg, PAI, ConvergenceCtrlToken,
2725       [&]() { return getOrCreateVReg(*CB.getCalledOperand()); });
2726 
2727   // Check if we just inserted a tail call.
2728   if (Success) {
2729     assert(!HasTailCall && "Can't tail call return twice from block?");
2730     const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
2731     HasTailCall = TII->isTailCall(*std::prev(MIRBuilder.getInsertPt()));
2732   }
2733 
2734   return Success;
2735 }
2736 
2737 bool IRTranslator::translateCall(const User &U, MachineIRBuilder &MIRBuilder) {
2738   const CallInst &CI = cast<CallInst>(U);
2739   auto TII = MF->getTarget().getIntrinsicInfo();
2740   const Function *F = CI.getCalledFunction();
2741 
2742   // FIXME: support Windows dllimport function calls and calls through
2743   // weak symbols.
2744   if (F && (F->hasDLLImportStorageClass() ||
2745             (MF->getTarget().getTargetTriple().isOSWindows() &&
2746              F->hasExternalWeakLinkage())))
2747     return false;
2748 
2749   // FIXME: support control flow guard targets.
2750   if (CI.countOperandBundlesOfType(LLVMContext::OB_cfguardtarget))
2751     return false;
2752 
2753   // FIXME: support statepoints and related.
2754   if (isa<GCStatepointInst, GCRelocateInst, GCResultInst>(U))
2755     return false;
2756 
2757   if (CI.isInlineAsm())
2758     return translateInlineAsm(CI, MIRBuilder);
2759 
2760   diagnoseDontCall(CI);
2761 
2762   Intrinsic::ID ID = Intrinsic::not_intrinsic;
2763   if (F && F->isIntrinsic()) {
2764     ID = F->getIntrinsicID();
2765     if (TII && ID == Intrinsic::not_intrinsic)
2766       ID = static_cast<Intrinsic::ID>(TII->getIntrinsicID(F));
2767   }
2768 
2769   if (!F || !F->isIntrinsic() || ID == Intrinsic::not_intrinsic)
2770     return translateCallBase(CI, MIRBuilder);
2771 
2772   assert(ID != Intrinsic::not_intrinsic && "unknown intrinsic");
2773 
2774   if (translateKnownIntrinsic(CI, ID, MIRBuilder))
2775     return true;
2776 
2777   ArrayRef<Register> ResultRegs;
2778   if (!CI.getType()->isVoidTy())
2779     ResultRegs = getOrCreateVRegs(CI);
2780 
2781   // Ignore the callsite attributes. Backend code is most likely not expecting
2782   // an intrinsic to sometimes have side effects and sometimes not.
2783   MachineInstrBuilder MIB = MIRBuilder.buildIntrinsic(ID, ResultRegs);
2784   if (isa<FPMathOperator>(CI))
2785     MIB->copyIRFlags(CI);
2786 
2787   for (const auto &Arg : enumerate(CI.args())) {
2788     // If this is required to be an immediate, don't materialize it in a
2789     // register.
2790     if (CI.paramHasAttr(Arg.index(), Attribute::ImmArg)) {
2791       if (ConstantInt *CI = dyn_cast<ConstantInt>(Arg.value())) {
2792         // imm arguments are more convenient than cimm (and realistically
2793         // probably sufficient), so use them.
2794         assert(CI->getBitWidth() <= 64 &&
2795                "large intrinsic immediates not handled");
2796         MIB.addImm(CI->getSExtValue());
2797       } else {
2798         MIB.addFPImm(cast<ConstantFP>(Arg.value()));
2799       }
2800     } else if (auto *MDVal = dyn_cast<MetadataAsValue>(Arg.value())) {
2801       auto *MD = MDVal->getMetadata();
2802       auto *MDN = dyn_cast<MDNode>(MD);
2803       if (!MDN) {
2804         if (auto *ConstMD = dyn_cast<ConstantAsMetadata>(MD))
2805           MDN = MDNode::get(MF->getFunction().getContext(), ConstMD);
2806         else // This was probably an MDString.
2807           return false;
2808       }
2809       MIB.addMetadata(MDN);
2810     } else {
2811       ArrayRef<Register> VRegs = getOrCreateVRegs(*Arg.value());
2812       if (VRegs.size() > 1)
2813         return false;
2814       MIB.addUse(VRegs[0]);
2815     }
2816   }
2817 
2818   // Add a MachineMemOperand if it is a target mem intrinsic.
2819   TargetLowering::IntrinsicInfo Info;
2820   // TODO: Add a GlobalISel version of getTgtMemIntrinsic.
2821   if (TLI->getTgtMemIntrinsic(Info, CI, *MF, ID)) {
2822     Align Alignment = Info.align.value_or(
2823         DL->getABITypeAlign(Info.memVT.getTypeForEVT(F->getContext())));
2824     LLT MemTy = Info.memVT.isSimple()
2825                     ? getLLTForMVT(Info.memVT.getSimpleVT())
2826                     : LLT::scalar(Info.memVT.getStoreSizeInBits());
2827 
2828     // TODO: We currently just fallback to address space 0 if getTgtMemIntrinsic
2829     //       didn't yield anything useful.
2830     MachinePointerInfo MPI;
2831     if (Info.ptrVal)
2832       MPI = MachinePointerInfo(Info.ptrVal, Info.offset);
2833     else if (Info.fallbackAddressSpace)
2834       MPI = MachinePointerInfo(*Info.fallbackAddressSpace);
2835     MIB.addMemOperand(
2836         MF->getMachineMemOperand(MPI, Info.flags, MemTy, Alignment, CI.getAAMetadata()));
2837   }
2838 
2839   if (CI.isConvergent()) {
2840     if (auto Bundle = CI.getOperandBundle(LLVMContext::OB_convergencectrl)) {
2841       auto *Token = Bundle->Inputs[0].get();
2842       Register TokenReg = getOrCreateVReg(*Token);
2843       MIB.addUse(TokenReg, RegState::Implicit);
2844     }
2845   }
2846 
2847   return true;
2848 }
2849 
2850 bool IRTranslator::findUnwindDestinations(
2851     const BasicBlock *EHPadBB,
2852     BranchProbability Prob,
2853     SmallVectorImpl<std::pair<MachineBasicBlock *, BranchProbability>>
2854         &UnwindDests) {
2855   EHPersonality Personality = classifyEHPersonality(
2856       EHPadBB->getParent()->getFunction().getPersonalityFn());
2857   bool IsMSVCCXX = Personality == EHPersonality::MSVC_CXX;
2858   bool IsCoreCLR = Personality == EHPersonality::CoreCLR;
2859   bool IsWasmCXX = Personality == EHPersonality::Wasm_CXX;
2860   bool IsSEH = isAsynchronousEHPersonality(Personality);
2861 
2862   if (IsWasmCXX) {
2863     // Ignore this for now.
2864     return false;
2865   }
2866 
2867   while (EHPadBB) {
2868     const Instruction *Pad = EHPadBB->getFirstNonPHI();
2869     BasicBlock *NewEHPadBB = nullptr;
2870     if (isa<LandingPadInst>(Pad)) {
2871       // Stop on landingpads. They are not funclets.
2872       UnwindDests.emplace_back(&getMBB(*EHPadBB), Prob);
2873       break;
2874     }
2875     if (isa<CleanupPadInst>(Pad)) {
2876       // Stop on cleanup pads. Cleanups are always funclet entries for all known
2877       // personalities.
2878       UnwindDests.emplace_back(&getMBB(*EHPadBB), Prob);
2879       UnwindDests.back().first->setIsEHScopeEntry();
2880       UnwindDests.back().first->setIsEHFuncletEntry();
2881       break;
2882     }
2883     if (auto *CatchSwitch = dyn_cast<CatchSwitchInst>(Pad)) {
2884       // Add the catchpad handlers to the possible destinations.
2885       for (const BasicBlock *CatchPadBB : CatchSwitch->handlers()) {
2886         UnwindDests.emplace_back(&getMBB(*CatchPadBB), Prob);
2887         // For MSVC++ and the CLR, catchblocks are funclets and need prologues.
2888         if (IsMSVCCXX || IsCoreCLR)
2889           UnwindDests.back().first->setIsEHFuncletEntry();
2890         if (!IsSEH)
2891           UnwindDests.back().first->setIsEHScopeEntry();
2892       }
2893       NewEHPadBB = CatchSwitch->getUnwindDest();
2894     } else {
2895       continue;
2896     }
2897 
2898     BranchProbabilityInfo *BPI = FuncInfo.BPI;
2899     if (BPI && NewEHPadBB)
2900       Prob *= BPI->getEdgeProbability(EHPadBB, NewEHPadBB);
2901     EHPadBB = NewEHPadBB;
2902   }
2903   return true;
2904 }
2905 
2906 bool IRTranslator::translateInvoke(const User &U,
2907                                    MachineIRBuilder &MIRBuilder) {
2908   const InvokeInst &I = cast<InvokeInst>(U);
2909   MCContext &Context = MF->getContext();
2910 
2911   const BasicBlock *ReturnBB = I.getSuccessor(0);
2912   const BasicBlock *EHPadBB = I.getSuccessor(1);
2913 
2914   const Function *Fn = I.getCalledFunction();
2915 
2916   // FIXME: support invoking patchpoint and statepoint intrinsics.
2917   if (Fn && Fn->isIntrinsic())
2918     return false;
2919 
2920   // FIXME: support whatever these are.
2921   if (I.hasDeoptState())
2922     return false;
2923 
2924   // FIXME: support control flow guard targets.
2925   if (I.countOperandBundlesOfType(LLVMContext::OB_cfguardtarget))
2926     return false;
2927 
2928   // FIXME: support Windows exception handling.
2929   if (!isa<LandingPadInst>(EHPadBB->getFirstNonPHI()))
2930     return false;
2931 
2932   // FIXME: support Windows dllimport function calls and calls through
2933   // weak symbols.
2934   if (Fn && (Fn->hasDLLImportStorageClass() ||
2935             (MF->getTarget().getTargetTriple().isOSWindows() &&
2936              Fn->hasExternalWeakLinkage())))
2937     return false;
2938 
2939   bool LowerInlineAsm = I.isInlineAsm();
2940   bool NeedEHLabel = true;
2941 
2942   // Emit the actual call, bracketed by EH_LABELs so that the MF knows about
2943   // the region covered by the try.
2944   MCSymbol *BeginSymbol = nullptr;
2945   if (NeedEHLabel) {
2946     MIRBuilder.buildInstr(TargetOpcode::G_INVOKE_REGION_START);
2947     BeginSymbol = Context.createTempSymbol();
2948     MIRBuilder.buildInstr(TargetOpcode::EH_LABEL).addSym(BeginSymbol);
2949   }
2950 
2951   if (LowerInlineAsm) {
2952     if (!translateInlineAsm(I, MIRBuilder))
2953       return false;
2954   } else if (!translateCallBase(I, MIRBuilder))
2955     return false;
2956 
2957   MCSymbol *EndSymbol = nullptr;
2958   if (NeedEHLabel) {
2959     EndSymbol = Context.createTempSymbol();
2960     MIRBuilder.buildInstr(TargetOpcode::EH_LABEL).addSym(EndSymbol);
2961   }
2962 
2963   SmallVector<std::pair<MachineBasicBlock *, BranchProbability>, 1> UnwindDests;
2964   BranchProbabilityInfo *BPI = FuncInfo.BPI;
2965   MachineBasicBlock *InvokeMBB = &MIRBuilder.getMBB();
2966   BranchProbability EHPadBBProb =
2967       BPI ? BPI->getEdgeProbability(InvokeMBB->getBasicBlock(), EHPadBB)
2968           : BranchProbability::getZero();
2969 
2970   if (!findUnwindDestinations(EHPadBB, EHPadBBProb, UnwindDests))
2971     return false;
2972 
2973   MachineBasicBlock &EHPadMBB = getMBB(*EHPadBB),
2974                     &ReturnMBB = getMBB(*ReturnBB);
2975   // Update successor info.
2976   addSuccessorWithProb(InvokeMBB, &ReturnMBB);
2977   for (auto &UnwindDest : UnwindDests) {
2978     UnwindDest.first->setIsEHPad();
2979     addSuccessorWithProb(InvokeMBB, UnwindDest.first, UnwindDest.second);
2980   }
2981   InvokeMBB->normalizeSuccProbs();
2982 
2983   if (NeedEHLabel) {
2984     assert(BeginSymbol && "Expected a begin symbol!");
2985     assert(EndSymbol && "Expected an end symbol!");
2986     MF->addInvoke(&EHPadMBB, BeginSymbol, EndSymbol);
2987   }
2988 
2989   MIRBuilder.buildBr(ReturnMBB);
2990   return true;
2991 }
2992 
2993 bool IRTranslator::translateCallBr(const User &U,
2994                                    MachineIRBuilder &MIRBuilder) {
2995   // FIXME: Implement this.
2996   return false;
2997 }
2998 
2999 bool IRTranslator::translateLandingPad(const User &U,
3000                                        MachineIRBuilder &MIRBuilder) {
3001   const LandingPadInst &LP = cast<LandingPadInst>(U);
3002 
3003   MachineBasicBlock &MBB = MIRBuilder.getMBB();
3004 
3005   MBB.setIsEHPad();
3006 
3007   // If there aren't registers to copy the values into (e.g., during SjLj
3008   // exceptions), then don't bother.
3009   const Constant *PersonalityFn = MF->getFunction().getPersonalityFn();
3010   if (TLI->getExceptionPointerRegister(PersonalityFn) == 0 &&
3011       TLI->getExceptionSelectorRegister(PersonalityFn) == 0)
3012     return true;
3013 
3014   // If landingpad's return type is token type, we don't create DAG nodes
3015   // for its exception pointer and selector value. The extraction of exception
3016   // pointer or selector value from token type landingpads is not currently
3017   // supported.
3018   if (LP.getType()->isTokenTy())
3019     return true;
3020 
3021   // Add a label to mark the beginning of the landing pad.  Deletion of the
3022   // landing pad can thus be detected via the MachineModuleInfo.
3023   MIRBuilder.buildInstr(TargetOpcode::EH_LABEL)
3024     .addSym(MF->addLandingPad(&MBB));
3025 
3026   // If the unwinder does not preserve all registers, ensure that the
3027   // function marks the clobbered registers as used.
3028   const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();
3029   if (auto *RegMask = TRI.getCustomEHPadPreservedMask(*MF))
3030     MF->getRegInfo().addPhysRegsUsedFromRegMask(RegMask);
3031 
3032   LLT Ty = getLLTForType(*LP.getType(), *DL);
3033   Register Undef = MRI->createGenericVirtualRegister(Ty);
3034   MIRBuilder.buildUndef(Undef);
3035 
3036   SmallVector<LLT, 2> Tys;
3037   for (Type *Ty : cast<StructType>(LP.getType())->elements())
3038     Tys.push_back(getLLTForType(*Ty, *DL));
3039   assert(Tys.size() == 2 && "Only two-valued landingpads are supported");
3040 
3041   // Mark exception register as live in.
3042   Register ExceptionReg = TLI->getExceptionPointerRegister(PersonalityFn);
3043   if (!ExceptionReg)
3044     return false;
3045 
3046   MBB.addLiveIn(ExceptionReg);
3047   ArrayRef<Register> ResRegs = getOrCreateVRegs(LP);
3048   MIRBuilder.buildCopy(ResRegs[0], ExceptionReg);
3049 
3050   Register SelectorReg = TLI->getExceptionSelectorRegister(PersonalityFn);
3051   if (!SelectorReg)
3052     return false;
3053 
3054   MBB.addLiveIn(SelectorReg);
3055   Register PtrVReg = MRI->createGenericVirtualRegister(Tys[0]);
3056   MIRBuilder.buildCopy(PtrVReg, SelectorReg);
3057   MIRBuilder.buildCast(ResRegs[1], PtrVReg);
3058 
3059   return true;
3060 }
3061 
3062 bool IRTranslator::translateAlloca(const User &U,
3063                                    MachineIRBuilder &MIRBuilder) {
3064   auto &AI = cast<AllocaInst>(U);
3065 
3066   if (AI.isSwiftError())
3067     return true;
3068 
3069   if (AI.isStaticAlloca()) {
3070     Register Res = getOrCreateVReg(AI);
3071     int FI = getOrCreateFrameIndex(AI);
3072     MIRBuilder.buildFrameIndex(Res, FI);
3073     return true;
3074   }
3075 
3076   // FIXME: support stack probing for Windows.
3077   if (MF->getTarget().getTargetTriple().isOSWindows())
3078     return false;
3079 
3080   // Now we're in the harder dynamic case.
3081   Register NumElts = getOrCreateVReg(*AI.getArraySize());
3082   Type *IntPtrIRTy = DL->getIntPtrType(AI.getType());
3083   LLT IntPtrTy = getLLTForType(*IntPtrIRTy, *DL);
3084   if (MRI->getType(NumElts) != IntPtrTy) {
3085     Register ExtElts = MRI->createGenericVirtualRegister(IntPtrTy);
3086     MIRBuilder.buildZExtOrTrunc(ExtElts, NumElts);
3087     NumElts = ExtElts;
3088   }
3089 
3090   Type *Ty = AI.getAllocatedType();
3091 
3092   Register AllocSize = MRI->createGenericVirtualRegister(IntPtrTy);
3093   Register TySize =
3094       getOrCreateVReg(*ConstantInt::get(IntPtrIRTy, DL->getTypeAllocSize(Ty)));
3095   MIRBuilder.buildMul(AllocSize, NumElts, TySize);
3096 
3097   // Round the size of the allocation up to the stack alignment size
3098   // by add SA-1 to the size. This doesn't overflow because we're computing
3099   // an address inside an alloca.
3100   Align StackAlign = MF->getSubtarget().getFrameLowering()->getStackAlign();
3101   auto SAMinusOne = MIRBuilder.buildConstant(IntPtrTy, StackAlign.value() - 1);
3102   auto AllocAdd = MIRBuilder.buildAdd(IntPtrTy, AllocSize, SAMinusOne,
3103                                       MachineInstr::NoUWrap);
3104   auto AlignCst =
3105       MIRBuilder.buildConstant(IntPtrTy, ~(uint64_t)(StackAlign.value() - 1));
3106   auto AlignedAlloc = MIRBuilder.buildAnd(IntPtrTy, AllocAdd, AlignCst);
3107 
3108   Align Alignment = std::max(AI.getAlign(), DL->getPrefTypeAlign(Ty));
3109   if (Alignment <= StackAlign)
3110     Alignment = Align(1);
3111   MIRBuilder.buildDynStackAlloc(getOrCreateVReg(AI), AlignedAlloc, Alignment);
3112 
3113   MF->getFrameInfo().CreateVariableSizedObject(Alignment, &AI);
3114   assert(MF->getFrameInfo().hasVarSizedObjects());
3115   return true;
3116 }
3117 
3118 bool IRTranslator::translateVAArg(const User &U, MachineIRBuilder &MIRBuilder) {
3119   // FIXME: We may need more info about the type. Because of how LLT works,
3120   // we're completely discarding the i64/double distinction here (amongst
3121   // others). Fortunately the ABIs I know of where that matters don't use va_arg
3122   // anyway but that's not guaranteed.
3123   MIRBuilder.buildInstr(TargetOpcode::G_VAARG, {getOrCreateVReg(U)},
3124                         {getOrCreateVReg(*U.getOperand(0)),
3125                          DL->getABITypeAlign(U.getType()).value()});
3126   return true;
3127 }
3128 
3129 bool IRTranslator::translateUnreachable(const User &U, MachineIRBuilder &MIRBuilder) {
3130   if (!MF->getTarget().Options.TrapUnreachable)
3131     return true;
3132 
3133   auto &UI = cast<UnreachableInst>(U);
3134 
3135   // We may be able to ignore unreachable behind a noreturn call.
3136   if (const CallInst *Call = dyn_cast_or_null<CallInst>(UI.getPrevNode());
3137       Call && Call->doesNotReturn()) {
3138     if (MF->getTarget().Options.NoTrapAfterNoreturn)
3139       return true;
3140     // Do not emit an additional trap instruction.
3141     if (Call->isNonContinuableTrap())
3142       return true;
3143   }
3144 
3145   MIRBuilder.buildTrap();
3146   return true;
3147 }
3148 
3149 bool IRTranslator::translateInsertElement(const User &U,
3150                                           MachineIRBuilder &MIRBuilder) {
3151   // If it is a <1 x Ty> vector, use the scalar as it is
3152   // not a legal vector type in LLT.
3153   if (auto *FVT = dyn_cast<FixedVectorType>(U.getType());
3154       FVT && FVT->getNumElements() == 1)
3155     return translateCopy(U, *U.getOperand(1), MIRBuilder);
3156 
3157   Register Res = getOrCreateVReg(U);
3158   Register Val = getOrCreateVReg(*U.getOperand(0));
3159   Register Elt = getOrCreateVReg(*U.getOperand(1));
3160   unsigned PreferredVecIdxWidth = TLI->getVectorIdxTy(*DL).getSizeInBits();
3161   Register Idx;
3162   if (auto *CI = dyn_cast<ConstantInt>(U.getOperand(2))) {
3163     if (CI->getBitWidth() != PreferredVecIdxWidth) {
3164       APInt NewIdx = CI->getValue().zextOrTrunc(PreferredVecIdxWidth);
3165       auto *NewIdxCI = ConstantInt::get(CI->getContext(), NewIdx);
3166       Idx = getOrCreateVReg(*NewIdxCI);
3167     }
3168   }
3169   if (!Idx)
3170     Idx = getOrCreateVReg(*U.getOperand(2));
3171   if (MRI->getType(Idx).getSizeInBits() != PreferredVecIdxWidth) {
3172     const LLT VecIdxTy = LLT::scalar(PreferredVecIdxWidth);
3173     Idx = MIRBuilder.buildZExtOrTrunc(VecIdxTy, Idx).getReg(0);
3174   }
3175   MIRBuilder.buildInsertVectorElement(Res, Val, Elt, Idx);
3176   return true;
3177 }
3178 
3179 bool IRTranslator::translateInsertVector(const User &U,
3180                                          MachineIRBuilder &MIRBuilder) {
3181   Register Dst = getOrCreateVReg(U);
3182   Register Vec = getOrCreateVReg(*U.getOperand(0));
3183   Register Elt = getOrCreateVReg(*U.getOperand(1));
3184 
3185   ConstantInt *CI = cast<ConstantInt>(U.getOperand(2));
3186   unsigned PreferredVecIdxWidth = TLI->getVectorIdxTy(*DL).getSizeInBits();
3187 
3188   // Resize Index to preferred index width.
3189   if (CI->getBitWidth() != PreferredVecIdxWidth) {
3190     APInt NewIdx = CI->getValue().zextOrTrunc(PreferredVecIdxWidth);
3191     CI = ConstantInt::get(CI->getContext(), NewIdx);
3192   }
3193 
3194   // If it is a <1 x Ty> vector, we have to use other means.
3195   if (auto *ResultType = dyn_cast<FixedVectorType>(U.getOperand(1)->getType());
3196       ResultType && ResultType->getNumElements() == 1) {
3197     if (auto *InputType = dyn_cast<FixedVectorType>(U.getOperand(0)->getType());
3198         InputType && InputType->getNumElements() == 1) {
3199       // We are inserting an illegal fixed vector into an illegal
3200       // fixed vector, use the scalar as it is not a legal vector type
3201       // in LLT.
3202       return translateCopy(U, *U.getOperand(0), MIRBuilder);
3203     }
3204     if (isa<FixedVectorType>(U.getOperand(0)->getType())) {
3205       // We are inserting an illegal fixed vector into a legal fixed
3206       // vector, use the scalar as it is not a legal vector type in
3207       // LLT.
3208       Register Idx = getOrCreateVReg(*CI);
3209       MIRBuilder.buildInsertVectorElement(Dst, Vec, Elt, Idx);
3210       return true;
3211     }
3212     if (isa<ScalableVectorType>(U.getOperand(0)->getType())) {
3213       // We are inserting an illegal fixed vector into a scalable
3214       // vector, use a scalar element insert.
3215       LLT VecIdxTy = LLT::scalar(PreferredVecIdxWidth);
3216       Register Idx = getOrCreateVReg(*CI);
3217       auto ScaledIndex = MIRBuilder.buildMul(
3218           VecIdxTy, MIRBuilder.buildVScale(VecIdxTy, 1), Idx);
3219       MIRBuilder.buildInsertVectorElement(Dst, Vec, Elt, ScaledIndex);
3220       return true;
3221     }
3222   }
3223 
3224   MIRBuilder.buildInsertSubvector(
3225       getOrCreateVReg(U), getOrCreateVReg(*U.getOperand(0)),
3226       getOrCreateVReg(*U.getOperand(1)), CI->getZExtValue());
3227   return true;
3228 }
3229 
3230 bool IRTranslator::translateExtractElement(const User &U,
3231                                            MachineIRBuilder &MIRBuilder) {
3232   // If it is a <1 x Ty> vector, use the scalar as it is
3233   // not a legal vector type in LLT.
3234   if (const FixedVectorType *FVT =
3235           dyn_cast<FixedVectorType>(U.getOperand(0)->getType()))
3236     if (FVT->getNumElements() == 1)
3237       return translateCopy(U, *U.getOperand(0), MIRBuilder);
3238 
3239   Register Res = getOrCreateVReg(U);
3240   Register Val = getOrCreateVReg(*U.getOperand(0));
3241   unsigned PreferredVecIdxWidth = TLI->getVectorIdxTy(*DL).getSizeInBits();
3242   Register Idx;
3243   if (auto *CI = dyn_cast<ConstantInt>(U.getOperand(1))) {
3244     if (CI->getBitWidth() != PreferredVecIdxWidth) {
3245       APInt NewIdx = CI->getValue().zextOrTrunc(PreferredVecIdxWidth);
3246       auto *NewIdxCI = ConstantInt::get(CI->getContext(), NewIdx);
3247       Idx = getOrCreateVReg(*NewIdxCI);
3248     }
3249   }
3250   if (!Idx)
3251     Idx = getOrCreateVReg(*U.getOperand(1));
3252   if (MRI->getType(Idx).getSizeInBits() != PreferredVecIdxWidth) {
3253     const LLT VecIdxTy = LLT::scalar(PreferredVecIdxWidth);
3254     Idx = MIRBuilder.buildZExtOrTrunc(VecIdxTy, Idx).getReg(0);
3255   }
3256   MIRBuilder.buildExtractVectorElement(Res, Val, Idx);
3257   return true;
3258 }
3259 
3260 bool IRTranslator::translateExtractVector(const User &U,
3261                                           MachineIRBuilder &MIRBuilder) {
3262   Register Res = getOrCreateVReg(U);
3263   Register Vec = getOrCreateVReg(*U.getOperand(0));
3264   ConstantInt *CI = cast<ConstantInt>(U.getOperand(1));
3265   unsigned PreferredVecIdxWidth = TLI->getVectorIdxTy(*DL).getSizeInBits();
3266 
3267   // Resize Index to preferred index width.
3268   if (CI->getBitWidth() != PreferredVecIdxWidth) {
3269     APInt NewIdx = CI->getValue().zextOrTrunc(PreferredVecIdxWidth);
3270     CI = ConstantInt::get(CI->getContext(), NewIdx);
3271   }
3272 
3273   // If it is a <1 x Ty> vector, we have to use other means.
3274   if (auto *ResultType = dyn_cast<FixedVectorType>(U.getType());
3275       ResultType && ResultType->getNumElements() == 1) {
3276     if (auto *InputType = dyn_cast<FixedVectorType>(U.getOperand(0)->getType());
3277         InputType && InputType->getNumElements() == 1) {
3278       // We are extracting an illegal fixed vector from an illegal fixed vector,
3279       // use the scalar as it is not a legal vector type in LLT.
3280       return translateCopy(U, *U.getOperand(0), MIRBuilder);
3281     }
3282     if (isa<FixedVectorType>(U.getOperand(0)->getType())) {
3283       // We are extracting an illegal fixed vector from a legal fixed
3284       // vector, use the scalar as it is not a legal vector type in
3285       // LLT.
3286       Register Idx = getOrCreateVReg(*CI);
3287       MIRBuilder.buildExtractVectorElement(Res, Vec, Idx);
3288       return true;
3289     }
3290     if (isa<ScalableVectorType>(U.getOperand(0)->getType())) {
3291       // We are extracting an illegal fixed vector from a scalable
3292       // vector, use a scalar element extract.
3293       LLT VecIdxTy = LLT::scalar(PreferredVecIdxWidth);
3294       Register Idx = getOrCreateVReg(*CI);
3295       auto ScaledIndex = MIRBuilder.buildMul(
3296           VecIdxTy, MIRBuilder.buildVScale(VecIdxTy, 1), Idx);
3297       MIRBuilder.buildExtractVectorElement(Res, Vec, ScaledIndex);
3298       return true;
3299     }
3300   }
3301 
3302   MIRBuilder.buildExtractSubvector(getOrCreateVReg(U),
3303                                    getOrCreateVReg(*U.getOperand(0)),
3304                                    CI->getZExtValue());
3305   return true;
3306 }
3307 
3308 bool IRTranslator::translateShuffleVector(const User &U,
3309                                           MachineIRBuilder &MIRBuilder) {
3310   // A ShuffleVector that operates on scalable vectors is a splat vector where
3311   // the value of the splat vector is the 0th element of the first operand,
3312   // since the index mask operand is the zeroinitializer (undef and
3313   // poison are treated as zeroinitializer here).
3314   if (U.getOperand(0)->getType()->isScalableTy()) {
3315     Register Val = getOrCreateVReg(*U.getOperand(0));
3316     auto SplatVal = MIRBuilder.buildExtractVectorElementConstant(
3317         MRI->getType(Val).getElementType(), Val, 0);
3318     MIRBuilder.buildSplatVector(getOrCreateVReg(U), SplatVal);
3319     return true;
3320   }
3321 
3322   ArrayRef<int> Mask;
3323   if (auto *SVI = dyn_cast<ShuffleVectorInst>(&U))
3324     Mask = SVI->getShuffleMask();
3325   else
3326     Mask = cast<ConstantExpr>(U).getShuffleMask();
3327   ArrayRef<int> MaskAlloc = MF->allocateShuffleMask(Mask);
3328   MIRBuilder
3329       .buildInstr(TargetOpcode::G_SHUFFLE_VECTOR, {getOrCreateVReg(U)},
3330                   {getOrCreateVReg(*U.getOperand(0)),
3331                    getOrCreateVReg(*U.getOperand(1))})
3332       .addShuffleMask(MaskAlloc);
3333   return true;
3334 }
3335 
3336 bool IRTranslator::translatePHI(const User &U, MachineIRBuilder &MIRBuilder) {
3337   const PHINode &PI = cast<PHINode>(U);
3338 
3339   SmallVector<MachineInstr *, 4> Insts;
3340   for (auto Reg : getOrCreateVRegs(PI)) {
3341     auto MIB = MIRBuilder.buildInstr(TargetOpcode::G_PHI, {Reg}, {});
3342     Insts.push_back(MIB.getInstr());
3343   }
3344 
3345   PendingPHIs.emplace_back(&PI, std::move(Insts));
3346   return true;
3347 }
3348 
3349 bool IRTranslator::translateAtomicCmpXchg(const User &U,
3350                                           MachineIRBuilder &MIRBuilder) {
3351   const AtomicCmpXchgInst &I = cast<AtomicCmpXchgInst>(U);
3352 
3353   auto Flags = TLI->getAtomicMemOperandFlags(I, *DL);
3354 
3355   auto Res = getOrCreateVRegs(I);
3356   Register OldValRes = Res[0];
3357   Register SuccessRes = Res[1];
3358   Register Addr = getOrCreateVReg(*I.getPointerOperand());
3359   Register Cmp = getOrCreateVReg(*I.getCompareOperand());
3360   Register NewVal = getOrCreateVReg(*I.getNewValOperand());
3361 
3362   MIRBuilder.buildAtomicCmpXchgWithSuccess(
3363       OldValRes, SuccessRes, Addr, Cmp, NewVal,
3364       *MF->getMachineMemOperand(
3365           MachinePointerInfo(I.getPointerOperand()), Flags, MRI->getType(Cmp),
3366           getMemOpAlign(I), I.getAAMetadata(), nullptr, I.getSyncScopeID(),
3367           I.getSuccessOrdering(), I.getFailureOrdering()));
3368   return true;
3369 }
3370 
3371 bool IRTranslator::translateAtomicRMW(const User &U,
3372                                       MachineIRBuilder &MIRBuilder) {
3373   const AtomicRMWInst &I = cast<AtomicRMWInst>(U);
3374   auto Flags = TLI->getAtomicMemOperandFlags(I, *DL);
3375 
3376   Register Res = getOrCreateVReg(I);
3377   Register Addr = getOrCreateVReg(*I.getPointerOperand());
3378   Register Val = getOrCreateVReg(*I.getValOperand());
3379 
3380   unsigned Opcode = 0;
3381   switch (I.getOperation()) {
3382   default:
3383     return false;
3384   case AtomicRMWInst::Xchg:
3385     Opcode = TargetOpcode::G_ATOMICRMW_XCHG;
3386     break;
3387   case AtomicRMWInst::Add:
3388     Opcode = TargetOpcode::G_ATOMICRMW_ADD;
3389     break;
3390   case AtomicRMWInst::Sub:
3391     Opcode = TargetOpcode::G_ATOMICRMW_SUB;
3392     break;
3393   case AtomicRMWInst::And:
3394     Opcode = TargetOpcode::G_ATOMICRMW_AND;
3395     break;
3396   case AtomicRMWInst::Nand:
3397     Opcode = TargetOpcode::G_ATOMICRMW_NAND;
3398     break;
3399   case AtomicRMWInst::Or:
3400     Opcode = TargetOpcode::G_ATOMICRMW_OR;
3401     break;
3402   case AtomicRMWInst::Xor:
3403     Opcode = TargetOpcode::G_ATOMICRMW_XOR;
3404     break;
3405   case AtomicRMWInst::Max:
3406     Opcode = TargetOpcode::G_ATOMICRMW_MAX;
3407     break;
3408   case AtomicRMWInst::Min:
3409     Opcode = TargetOpcode::G_ATOMICRMW_MIN;
3410     break;
3411   case AtomicRMWInst::UMax:
3412     Opcode = TargetOpcode::G_ATOMICRMW_UMAX;
3413     break;
3414   case AtomicRMWInst::UMin:
3415     Opcode = TargetOpcode::G_ATOMICRMW_UMIN;
3416     break;
3417   case AtomicRMWInst::FAdd:
3418     Opcode = TargetOpcode::G_ATOMICRMW_FADD;
3419     break;
3420   case AtomicRMWInst::FSub:
3421     Opcode = TargetOpcode::G_ATOMICRMW_FSUB;
3422     break;
3423   case AtomicRMWInst::FMax:
3424     Opcode = TargetOpcode::G_ATOMICRMW_FMAX;
3425     break;
3426   case AtomicRMWInst::FMin:
3427     Opcode = TargetOpcode::G_ATOMICRMW_FMIN;
3428     break;
3429   case AtomicRMWInst::UIncWrap:
3430     Opcode = TargetOpcode::G_ATOMICRMW_UINC_WRAP;
3431     break;
3432   case AtomicRMWInst::UDecWrap:
3433     Opcode = TargetOpcode::G_ATOMICRMW_UDEC_WRAP;
3434     break;
3435   case AtomicRMWInst::USubCond:
3436     Opcode = TargetOpcode::G_ATOMICRMW_USUB_COND;
3437     break;
3438   case AtomicRMWInst::USubSat:
3439     Opcode = TargetOpcode::G_ATOMICRMW_USUB_SAT;
3440     break;
3441   }
3442 
3443   MIRBuilder.buildAtomicRMW(
3444       Opcode, Res, Addr, Val,
3445       *MF->getMachineMemOperand(MachinePointerInfo(I.getPointerOperand()),
3446                                 Flags, MRI->getType(Val), getMemOpAlign(I),
3447                                 I.getAAMetadata(), nullptr, I.getSyncScopeID(),
3448                                 I.getOrdering()));
3449   return true;
3450 }
3451 
3452 bool IRTranslator::translateFence(const User &U,
3453                                   MachineIRBuilder &MIRBuilder) {
3454   const FenceInst &Fence = cast<FenceInst>(U);
3455   MIRBuilder.buildFence(static_cast<unsigned>(Fence.getOrdering()),
3456                         Fence.getSyncScopeID());
3457   return true;
3458 }
3459 
3460 bool IRTranslator::translateFreeze(const User &U,
3461                                    MachineIRBuilder &MIRBuilder) {
3462   const ArrayRef<Register> DstRegs = getOrCreateVRegs(U);
3463   const ArrayRef<Register> SrcRegs = getOrCreateVRegs(*U.getOperand(0));
3464 
3465   assert(DstRegs.size() == SrcRegs.size() &&
3466          "Freeze with different source and destination type?");
3467 
3468   for (unsigned I = 0; I < DstRegs.size(); ++I) {
3469     MIRBuilder.buildFreeze(DstRegs[I], SrcRegs[I]);
3470   }
3471 
3472   return true;
3473 }
3474 
3475 void IRTranslator::finishPendingPhis() {
3476 #ifndef NDEBUG
3477   DILocationVerifier Verifier;
3478   GISelObserverWrapper WrapperObserver(&Verifier);
3479   RAIIMFObsDelInstaller ObsInstall(*MF, WrapperObserver);
3480 #endif // ifndef NDEBUG
3481   for (auto &Phi : PendingPHIs) {
3482     const PHINode *PI = Phi.first;
3483     if (PI->getType()->isEmptyTy())
3484       continue;
3485     ArrayRef<MachineInstr *> ComponentPHIs = Phi.second;
3486     MachineBasicBlock *PhiMBB = ComponentPHIs[0]->getParent();
3487     EntryBuilder->setDebugLoc(PI->getDebugLoc());
3488 #ifndef NDEBUG
3489     Verifier.setCurrentInst(PI);
3490 #endif // ifndef NDEBUG
3491 
3492     SmallSet<const MachineBasicBlock *, 16> SeenPreds;
3493     for (unsigned i = 0; i < PI->getNumIncomingValues(); ++i) {
3494       auto IRPred = PI->getIncomingBlock(i);
3495       ArrayRef<Register> ValRegs = getOrCreateVRegs(*PI->getIncomingValue(i));
3496       for (auto *Pred : getMachinePredBBs({IRPred, PI->getParent()})) {
3497         if (SeenPreds.count(Pred) || !PhiMBB->isPredecessor(Pred))
3498           continue;
3499         SeenPreds.insert(Pred);
3500         for (unsigned j = 0; j < ValRegs.size(); ++j) {
3501           MachineInstrBuilder MIB(*MF, ComponentPHIs[j]);
3502           MIB.addUse(ValRegs[j]);
3503           MIB.addMBB(Pred);
3504         }
3505       }
3506     }
3507   }
3508 }
3509 
3510 void IRTranslator::translateDbgValueRecord(Value *V, bool HasArgList,
3511                                      const DILocalVariable *Variable,
3512                                      const DIExpression *Expression,
3513                                      const DebugLoc &DL,
3514                                      MachineIRBuilder &MIRBuilder) {
3515   assert(Variable->isValidLocationForIntrinsic(DL) &&
3516          "Expected inlined-at fields to agree");
3517   // Act as if we're handling a debug intrinsic.
3518   MIRBuilder.setDebugLoc(DL);
3519 
3520   if (!V || HasArgList) {
3521     // DI cannot produce a valid DBG_VALUE, so produce an undef DBG_VALUE to
3522     // terminate any prior location.
3523     MIRBuilder.buildIndirectDbgValue(0, Variable, Expression);
3524     return;
3525   }
3526 
3527   if (const auto *CI = dyn_cast<Constant>(V)) {
3528     MIRBuilder.buildConstDbgValue(*CI, Variable, Expression);
3529     return;
3530   }
3531 
3532   if (auto *AI = dyn_cast<AllocaInst>(V);
3533       AI && AI->isStaticAlloca() && Expression->startsWithDeref()) {
3534     // If the value is an alloca and the expression starts with a
3535     // dereference, track a stack slot instead of a register, as registers
3536     // may be clobbered.
3537     auto ExprOperands = Expression->getElements();
3538     auto *ExprDerefRemoved =
3539         DIExpression::get(AI->getContext(), ExprOperands.drop_front());
3540     MIRBuilder.buildFIDbgValue(getOrCreateFrameIndex(*AI), Variable,
3541                                ExprDerefRemoved);
3542     return;
3543   }
3544   if (translateIfEntryValueArgument(false, V, Variable, Expression, DL,
3545                                     MIRBuilder))
3546     return;
3547   for (Register Reg : getOrCreateVRegs(*V)) {
3548     // FIXME: This does not handle register-indirect values at offset 0. The
3549     // direct/indirect thing shouldn't really be handled by something as
3550     // implicit as reg+noreg vs reg+imm in the first place, but it seems
3551     // pretty baked in right now.
3552     MIRBuilder.buildDirectDbgValue(Reg, Variable, Expression);
3553   }
3554 }
3555 
3556 void IRTranslator::translateDbgDeclareRecord(Value *Address, bool HasArgList,
3557                                      const DILocalVariable *Variable,
3558                                      const DIExpression *Expression,
3559                                      const DebugLoc &DL,
3560                                      MachineIRBuilder &MIRBuilder) {
3561   if (!Address || isa<UndefValue>(Address)) {
3562     LLVM_DEBUG(dbgs() << "Dropping debug info for " << *Variable << "\n");
3563     return;
3564   }
3565 
3566   assert(Variable->isValidLocationForIntrinsic(DL) &&
3567          "Expected inlined-at fields to agree");
3568   auto AI = dyn_cast<AllocaInst>(Address);
3569   if (AI && AI->isStaticAlloca()) {
3570     // Static allocas are tracked at the MF level, no need for DBG_VALUE
3571     // instructions (in fact, they get ignored if they *do* exist).
3572     MF->setVariableDbgInfo(Variable, Expression,
3573                            getOrCreateFrameIndex(*AI), DL);
3574     return;
3575   }
3576 
3577   if (translateIfEntryValueArgument(true, Address, Variable,
3578                                     Expression, DL,
3579                                     MIRBuilder))
3580     return;
3581 
3582   // A dbg.declare describes the address of a source variable, so lower it
3583   // into an indirect DBG_VALUE.
3584   MIRBuilder.setDebugLoc(DL);
3585   MIRBuilder.buildIndirectDbgValue(getOrCreateVReg(*Address),
3586                                    Variable, Expression);
3587   return;
3588 }
3589 
3590 void IRTranslator::translateDbgInfo(const Instruction &Inst,
3591                                       MachineIRBuilder &MIRBuilder) {
3592   for (DbgRecord &DR : Inst.getDbgRecordRange()) {
3593     if (DbgLabelRecord *DLR = dyn_cast<DbgLabelRecord>(&DR)) {
3594       MIRBuilder.setDebugLoc(DLR->getDebugLoc());
3595       assert(DLR->getLabel() && "Missing label");
3596       assert(DLR->getLabel()->isValidLocationForIntrinsic(
3597                  MIRBuilder.getDebugLoc()) &&
3598              "Expected inlined-at fields to agree");
3599       MIRBuilder.buildDbgLabel(DLR->getLabel());
3600       continue;
3601     }
3602     DbgVariableRecord &DVR = cast<DbgVariableRecord>(DR);
3603     const DILocalVariable *Variable = DVR.getVariable();
3604     const DIExpression *Expression = DVR.getExpression();
3605     Value *V = DVR.getVariableLocationOp(0);
3606     if (DVR.isDbgDeclare())
3607       translateDbgDeclareRecord(V, DVR.hasArgList(), Variable, Expression,
3608                                 DVR.getDebugLoc(), MIRBuilder);
3609     else
3610       translateDbgValueRecord(V, DVR.hasArgList(), Variable, Expression,
3611                               DVR.getDebugLoc(), MIRBuilder);
3612   }
3613 }
3614 
3615 bool IRTranslator::translate(const Instruction &Inst) {
3616   CurBuilder->setDebugLoc(Inst.getDebugLoc());
3617   CurBuilder->setPCSections(Inst.getMetadata(LLVMContext::MD_pcsections));
3618   CurBuilder->setMMRAMetadata(Inst.getMetadata(LLVMContext::MD_mmra));
3619 
3620   if (TLI->fallBackToDAGISel(Inst))
3621     return false;
3622 
3623   switch (Inst.getOpcode()) {
3624 #define HANDLE_INST(NUM, OPCODE, CLASS)                                        \
3625   case Instruction::OPCODE:                                                    \
3626     return translate##OPCODE(Inst, *CurBuilder.get());
3627 #include "llvm/IR/Instruction.def"
3628   default:
3629     return false;
3630   }
3631 }
3632 
3633 bool IRTranslator::translate(const Constant &C, Register Reg) {
3634   // We only emit constants into the entry block from here. To prevent jumpy
3635   // debug behaviour remove debug line.
3636   if (auto CurrInstDL = CurBuilder->getDL())
3637     EntryBuilder->setDebugLoc(DebugLoc());
3638 
3639   if (auto CI = dyn_cast<ConstantInt>(&C))
3640     EntryBuilder->buildConstant(Reg, *CI);
3641   else if (auto CF = dyn_cast<ConstantFP>(&C))
3642     EntryBuilder->buildFConstant(Reg, *CF);
3643   else if (isa<UndefValue>(C))
3644     EntryBuilder->buildUndef(Reg);
3645   else if (isa<ConstantPointerNull>(C))
3646     EntryBuilder->buildConstant(Reg, 0);
3647   else if (auto GV = dyn_cast<GlobalValue>(&C))
3648     EntryBuilder->buildGlobalValue(Reg, GV);
3649   else if (auto CPA = dyn_cast<ConstantPtrAuth>(&C)) {
3650     Register Addr = getOrCreateVReg(*CPA->getPointer());
3651     Register AddrDisc = getOrCreateVReg(*CPA->getAddrDiscriminator());
3652     EntryBuilder->buildConstantPtrAuth(Reg, CPA, Addr, AddrDisc);
3653   } else if (auto CAZ = dyn_cast<ConstantAggregateZero>(&C)) {
3654     Constant &Elt = *CAZ->getElementValue(0u);
3655     if (isa<ScalableVectorType>(CAZ->getType())) {
3656       EntryBuilder->buildSplatVector(Reg, getOrCreateVReg(Elt));
3657       return true;
3658     }
3659     // Return the scalar if it is a <1 x Ty> vector.
3660     unsigned NumElts = CAZ->getElementCount().getFixedValue();
3661     if (NumElts == 1)
3662       return translateCopy(C, Elt, *EntryBuilder);
3663     // All elements are zero so we can just use the first one.
3664     EntryBuilder->buildSplatBuildVector(Reg, getOrCreateVReg(Elt));
3665   } else if (auto CV = dyn_cast<ConstantDataVector>(&C)) {
3666     // Return the scalar if it is a <1 x Ty> vector.
3667     if (CV->getNumElements() == 1)
3668       return translateCopy(C, *CV->getElementAsConstant(0), *EntryBuilder);
3669     SmallVector<Register, 4> Ops;
3670     for (unsigned i = 0; i < CV->getNumElements(); ++i) {
3671       Constant &Elt = *CV->getElementAsConstant(i);
3672       Ops.push_back(getOrCreateVReg(Elt));
3673     }
3674     EntryBuilder->buildBuildVector(Reg, Ops);
3675   } else if (auto CE = dyn_cast<ConstantExpr>(&C)) {
3676     switch(CE->getOpcode()) {
3677 #define HANDLE_INST(NUM, OPCODE, CLASS)                                        \
3678   case Instruction::OPCODE:                                                    \
3679     return translate##OPCODE(*CE, *EntryBuilder.get());
3680 #include "llvm/IR/Instruction.def"
3681     default:
3682       return false;
3683     }
3684   } else if (auto CV = dyn_cast<ConstantVector>(&C)) {
3685     if (CV->getNumOperands() == 1)
3686       return translateCopy(C, *CV->getOperand(0), *EntryBuilder);
3687     SmallVector<Register, 4> Ops;
3688     for (unsigned i = 0; i < CV->getNumOperands(); ++i) {
3689       Ops.push_back(getOrCreateVReg(*CV->getOperand(i)));
3690     }
3691     EntryBuilder->buildBuildVector(Reg, Ops);
3692   } else if (auto *BA = dyn_cast<BlockAddress>(&C)) {
3693     EntryBuilder->buildBlockAddress(Reg, BA);
3694   } else
3695     return false;
3696 
3697   return true;
3698 }
3699 
3700 bool IRTranslator::finalizeBasicBlock(const BasicBlock &BB,
3701                                       MachineBasicBlock &MBB) {
3702   for (auto &BTB : SL->BitTestCases) {
3703     // Emit header first, if it wasn't already emitted.
3704     if (!BTB.Emitted)
3705       emitBitTestHeader(BTB, BTB.Parent);
3706 
3707     BranchProbability UnhandledProb = BTB.Prob;
3708     for (unsigned j = 0, ej = BTB.Cases.size(); j != ej; ++j) {
3709       UnhandledProb -= BTB.Cases[j].ExtraProb;
3710       // Set the current basic block to the mbb we wish to insert the code into
3711       MachineBasicBlock *MBB = BTB.Cases[j].ThisBB;
3712       // If all cases cover a contiguous range, it is not necessary to jump to
3713       // the default block after the last bit test fails. This is because the
3714       // range check during bit test header creation has guaranteed that every
3715       // case here doesn't go outside the range. In this case, there is no need
3716       // to perform the last bit test, as it will always be true. Instead, make
3717       // the second-to-last bit-test fall through to the target of the last bit
3718       // test, and delete the last bit test.
3719 
3720       MachineBasicBlock *NextMBB;
3721       if ((BTB.ContiguousRange || BTB.FallthroughUnreachable) && j + 2 == ej) {
3722         // Second-to-last bit-test with contiguous range: fall through to the
3723         // target of the final bit test.
3724         NextMBB = BTB.Cases[j + 1].TargetBB;
3725       } else if (j + 1 == ej) {
3726         // For the last bit test, fall through to Default.
3727         NextMBB = BTB.Default;
3728       } else {
3729         // Otherwise, fall through to the next bit test.
3730         NextMBB = BTB.Cases[j + 1].ThisBB;
3731       }
3732 
3733       emitBitTestCase(BTB, NextMBB, UnhandledProb, BTB.Reg, BTB.Cases[j], MBB);
3734 
3735       if ((BTB.ContiguousRange || BTB.FallthroughUnreachable) && j + 2 == ej) {
3736         // We need to record the replacement phi edge here that normally
3737         // happens in emitBitTestCase before we delete the case, otherwise the
3738         // phi edge will be lost.
3739         addMachineCFGPred({BTB.Parent->getBasicBlock(),
3740                            BTB.Cases[ej - 1].TargetBB->getBasicBlock()},
3741                           MBB);
3742         // Since we're not going to use the final bit test, remove it.
3743         BTB.Cases.pop_back();
3744         break;
3745       }
3746     }
3747     // This is "default" BB. We have two jumps to it. From "header" BB and from
3748     // last "case" BB, unless the latter was skipped.
3749     CFGEdge HeaderToDefaultEdge = {BTB.Parent->getBasicBlock(),
3750                                    BTB.Default->getBasicBlock()};
3751     addMachineCFGPred(HeaderToDefaultEdge, BTB.Parent);
3752     if (!BTB.ContiguousRange) {
3753       addMachineCFGPred(HeaderToDefaultEdge, BTB.Cases.back().ThisBB);
3754     }
3755   }
3756   SL->BitTestCases.clear();
3757 
3758   for (auto &JTCase : SL->JTCases) {
3759     // Emit header first, if it wasn't already emitted.
3760     if (!JTCase.first.Emitted)
3761       emitJumpTableHeader(JTCase.second, JTCase.first, JTCase.first.HeaderBB);
3762 
3763     emitJumpTable(JTCase.second, JTCase.second.MBB);
3764   }
3765   SL->JTCases.clear();
3766 
3767   for (auto &SwCase : SL->SwitchCases)
3768     emitSwitchCase(SwCase, &CurBuilder->getMBB(), *CurBuilder);
3769   SL->SwitchCases.clear();
3770 
3771   // Check if we need to generate stack-protector guard checks.
3772   StackProtector &SP = getAnalysis<StackProtector>();
3773   if (SP.shouldEmitSDCheck(BB)) {
3774     bool FunctionBasedInstrumentation =
3775         TLI->getSSPStackGuardCheck(*MF->getFunction().getParent());
3776     SPDescriptor.initialize(&BB, &MBB, FunctionBasedInstrumentation);
3777   }
3778   // Handle stack protector.
3779   if (SPDescriptor.shouldEmitFunctionBasedCheckStackProtector()) {
3780     LLVM_DEBUG(dbgs() << "Unimplemented stack protector case\n");
3781     return false;
3782   } else if (SPDescriptor.shouldEmitStackProtector()) {
3783     MachineBasicBlock *ParentMBB = SPDescriptor.getParentMBB();
3784     MachineBasicBlock *SuccessMBB = SPDescriptor.getSuccessMBB();
3785 
3786     // Find the split point to split the parent mbb. At the same time copy all
3787     // physical registers used in the tail of parent mbb into virtual registers
3788     // before the split point and back into physical registers after the split
3789     // point. This prevents us needing to deal with Live-ins and many other
3790     // register allocation issues caused by us splitting the parent mbb. The
3791     // register allocator will clean up said virtual copies later on.
3792     MachineBasicBlock::iterator SplitPoint = findSplitPointForStackProtector(
3793         ParentMBB, *MF->getSubtarget().getInstrInfo());
3794 
3795     // Splice the terminator of ParentMBB into SuccessMBB.
3796     SuccessMBB->splice(SuccessMBB->end(), ParentMBB, SplitPoint,
3797                        ParentMBB->end());
3798 
3799     // Add compare/jump on neq/jump to the parent BB.
3800     if (!emitSPDescriptorParent(SPDescriptor, ParentMBB))
3801       return false;
3802 
3803     // CodeGen Failure MBB if we have not codegened it yet.
3804     MachineBasicBlock *FailureMBB = SPDescriptor.getFailureMBB();
3805     if (FailureMBB->empty()) {
3806       if (!emitSPDescriptorFailure(SPDescriptor, FailureMBB))
3807         return false;
3808     }
3809 
3810     // Clear the Per-BB State.
3811     SPDescriptor.resetPerBBState();
3812   }
3813   return true;
3814 }
3815 
3816 bool IRTranslator::emitSPDescriptorParent(StackProtectorDescriptor &SPD,
3817                                           MachineBasicBlock *ParentBB) {
3818   CurBuilder->setInsertPt(*ParentBB, ParentBB->end());
3819   // First create the loads to the guard/stack slot for the comparison.
3820   Type *PtrIRTy = PointerType::getUnqual(MF->getFunction().getContext());
3821   const LLT PtrTy = getLLTForType(*PtrIRTy, *DL);
3822   LLT PtrMemTy = getLLTForMVT(TLI->getPointerMemTy(*DL));
3823 
3824   MachineFrameInfo &MFI = ParentBB->getParent()->getFrameInfo();
3825   int FI = MFI.getStackProtectorIndex();
3826 
3827   Register Guard;
3828   Register StackSlotPtr = CurBuilder->buildFrameIndex(PtrTy, FI).getReg(0);
3829   const Module &M = *ParentBB->getParent()->getFunction().getParent();
3830   Align Align = DL->getPrefTypeAlign(PointerType::getUnqual(M.getContext()));
3831 
3832   // Generate code to load the content of the guard slot.
3833   Register GuardVal =
3834       CurBuilder
3835           ->buildLoad(PtrMemTy, StackSlotPtr,
3836                       MachinePointerInfo::getFixedStack(*MF, FI), Align,
3837                       MachineMemOperand::MOLoad | MachineMemOperand::MOVolatile)
3838           .getReg(0);
3839 
3840   if (TLI->useStackGuardXorFP()) {
3841     LLVM_DEBUG(dbgs() << "Stack protector xor'ing with FP not yet implemented");
3842     return false;
3843   }
3844 
3845   // Retrieve guard check function, nullptr if instrumentation is inlined.
3846   if (const Function *GuardCheckFn = TLI->getSSPStackGuardCheck(M)) {
3847     // This path is currently untestable on GlobalISel, since the only platform
3848     // that needs this seems to be Windows, and we fall back on that currently.
3849     // The code still lives here in case that changes.
3850     // Silence warning about unused variable until the code below that uses
3851     // 'GuardCheckFn' is enabled.
3852     (void)GuardCheckFn;
3853     return false;
3854 #if 0
3855     // The target provides a guard check function to validate the guard value.
3856     // Generate a call to that function with the content of the guard slot as
3857     // argument.
3858     FunctionType *FnTy = GuardCheckFn->getFunctionType();
3859     assert(FnTy->getNumParams() == 1 && "Invalid function signature");
3860     ISD::ArgFlagsTy Flags;
3861     if (GuardCheckFn->hasAttribute(1, Attribute::AttrKind::InReg))
3862       Flags.setInReg();
3863     CallLowering::ArgInfo GuardArgInfo(
3864         {GuardVal, FnTy->getParamType(0), {Flags}});
3865 
3866     CallLowering::CallLoweringInfo Info;
3867     Info.OrigArgs.push_back(GuardArgInfo);
3868     Info.CallConv = GuardCheckFn->getCallingConv();
3869     Info.Callee = MachineOperand::CreateGA(GuardCheckFn, 0);
3870     Info.OrigRet = {Register(), FnTy->getReturnType()};
3871     if (!CLI->lowerCall(MIRBuilder, Info)) {
3872       LLVM_DEBUG(dbgs() << "Failed to lower call to stack protector check\n");
3873       return false;
3874     }
3875     return true;
3876 #endif
3877   }
3878 
3879   // If useLoadStackGuardNode returns true, generate LOAD_STACK_GUARD.
3880   // Otherwise, emit a volatile load to retrieve the stack guard value.
3881   if (TLI->useLoadStackGuardNode(*ParentBB->getBasicBlock()->getModule())) {
3882     Guard =
3883         MRI->createGenericVirtualRegister(LLT::scalar(PtrTy.getSizeInBits()));
3884     getStackGuard(Guard, *CurBuilder);
3885   } else {
3886     // TODO: test using android subtarget when we support @llvm.thread.pointer.
3887     const Value *IRGuard = TLI->getSDagStackGuard(M);
3888     Register GuardPtr = getOrCreateVReg(*IRGuard);
3889 
3890     Guard = CurBuilder
3891                 ->buildLoad(PtrMemTy, GuardPtr,
3892                             MachinePointerInfo::getFixedStack(*MF, FI), Align,
3893                             MachineMemOperand::MOLoad |
3894                                 MachineMemOperand::MOVolatile)
3895                 .getReg(0);
3896   }
3897 
3898   // Perform the comparison.
3899   auto Cmp =
3900       CurBuilder->buildICmp(CmpInst::ICMP_NE, LLT::scalar(1), Guard, GuardVal);
3901   // If the guard/stackslot do not equal, branch to failure MBB.
3902   CurBuilder->buildBrCond(Cmp, *SPD.getFailureMBB());
3903   // Otherwise branch to success MBB.
3904   CurBuilder->buildBr(*SPD.getSuccessMBB());
3905   return true;
3906 }
3907 
3908 bool IRTranslator::emitSPDescriptorFailure(StackProtectorDescriptor &SPD,
3909                                            MachineBasicBlock *FailureBB) {
3910   CurBuilder->setInsertPt(*FailureBB, FailureBB->end());
3911 
3912   const RTLIB::Libcall Libcall = RTLIB::STACKPROTECTOR_CHECK_FAIL;
3913   const char *Name = TLI->getLibcallName(Libcall);
3914 
3915   CallLowering::CallLoweringInfo Info;
3916   Info.CallConv = TLI->getLibcallCallingConv(Libcall);
3917   Info.Callee = MachineOperand::CreateES(Name);
3918   Info.OrigRet = {Register(), Type::getVoidTy(MF->getFunction().getContext()),
3919                   0};
3920   if (!CLI->lowerCall(*CurBuilder, Info)) {
3921     LLVM_DEBUG(dbgs() << "Failed to lower call to stack protector fail\n");
3922     return false;
3923   }
3924 
3925   // Emit a trap instruction if we are required to do so.
3926   const TargetOptions &TargetOpts = TLI->getTargetMachine().Options;
3927   if (TargetOpts.TrapUnreachable && !TargetOpts.NoTrapAfterNoreturn)
3928     CurBuilder->buildInstr(TargetOpcode::G_TRAP);
3929 
3930   return true;
3931 }
3932 
3933 void IRTranslator::finalizeFunction() {
3934   // Release the memory used by the different maps we
3935   // needed during the translation.
3936   PendingPHIs.clear();
3937   VMap.reset();
3938   FrameIndices.clear();
3939   MachinePreds.clear();
3940   // MachineIRBuilder::DebugLoc can outlive the DILocation it holds. Clear it
3941   // to avoid accessing free’d memory (in runOnMachineFunction) and to avoid
3942   // destroying it twice (in ~IRTranslator() and ~LLVMContext())
3943   EntryBuilder.reset();
3944   CurBuilder.reset();
3945   FuncInfo.clear();
3946   SPDescriptor.resetPerFunctionState();
3947 }
3948 
3949 /// Returns true if a BasicBlock \p BB within a variadic function contains a
3950 /// variadic musttail call.
3951 static bool checkForMustTailInVarArgFn(bool IsVarArg, const BasicBlock &BB) {
3952   if (!IsVarArg)
3953     return false;
3954 
3955   // Walk the block backwards, because tail calls usually only appear at the end
3956   // of a block.
3957   return llvm::any_of(llvm::reverse(BB), [](const Instruction &I) {
3958     const auto *CI = dyn_cast<CallInst>(&I);
3959     return CI && CI->isMustTailCall();
3960   });
3961 }
3962 
3963 bool IRTranslator::runOnMachineFunction(MachineFunction &CurMF) {
3964   MF = &CurMF;
3965   const Function &F = MF->getFunction();
3966   GISelCSEAnalysisWrapper &Wrapper =
3967       getAnalysis<GISelCSEAnalysisWrapperPass>().getCSEWrapper();
3968   // Set the CSEConfig and run the analysis.
3969   GISelCSEInfo *CSEInfo = nullptr;
3970   TPC = &getAnalysis<TargetPassConfig>();
3971   bool EnableCSE = EnableCSEInIRTranslator.getNumOccurrences()
3972                        ? EnableCSEInIRTranslator
3973                        : TPC->isGISelCSEEnabled();
3974   TLI = MF->getSubtarget().getTargetLowering();
3975 
3976   if (EnableCSE) {
3977     EntryBuilder = std::make_unique<CSEMIRBuilder>(CurMF);
3978     CSEInfo = &Wrapper.get(TPC->getCSEConfig());
3979     EntryBuilder->setCSEInfo(CSEInfo);
3980     CurBuilder = std::make_unique<CSEMIRBuilder>(CurMF);
3981     CurBuilder->setCSEInfo(CSEInfo);
3982   } else {
3983     EntryBuilder = std::make_unique<MachineIRBuilder>();
3984     CurBuilder = std::make_unique<MachineIRBuilder>();
3985   }
3986   CLI = MF->getSubtarget().getCallLowering();
3987   CurBuilder->setMF(*MF);
3988   EntryBuilder->setMF(*MF);
3989   MRI = &MF->getRegInfo();
3990   DL = &F.getDataLayout();
3991   ORE = std::make_unique<OptimizationRemarkEmitter>(&F);
3992   const TargetMachine &TM = MF->getTarget();
3993   TM.resetTargetOptions(F);
3994   EnableOpts = OptLevel != CodeGenOptLevel::None && !skipFunction(F);
3995   FuncInfo.MF = MF;
3996   if (EnableOpts) {
3997     AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
3998     FuncInfo.BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
3999   } else {
4000     AA = nullptr;
4001     FuncInfo.BPI = nullptr;
4002   }
4003 
4004   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
4005       MF->getFunction());
4006   LibInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
4007   FuncInfo.CanLowerReturn = CLI->checkReturnTypeForCallConv(*MF);
4008 
4009   SL = std::make_unique<GISelSwitchLowering>(this, FuncInfo);
4010   SL->init(*TLI, TM, *DL);
4011 
4012   assert(PendingPHIs.empty() && "stale PHIs");
4013 
4014   // Targets which want to use big endian can enable it using
4015   // enableBigEndian()
4016   if (!DL->isLittleEndian() && !CLI->enableBigEndian()) {
4017     // Currently we don't properly handle big endian code.
4018     OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure",
4019                                F.getSubprogram(), &F.getEntryBlock());
4020     R << "unable to translate in big endian mode";
4021     reportTranslationError(*MF, *TPC, *ORE, R);
4022     return false;
4023   }
4024 
4025   // Release the per-function state when we return, whether we succeeded or not.
4026   auto FinalizeOnReturn = make_scope_exit([this]() { finalizeFunction(); });
4027 
4028   // Setup a separate basic-block for the arguments and constants
4029   MachineBasicBlock *EntryBB = MF->CreateMachineBasicBlock();
4030   MF->push_back(EntryBB);
4031   EntryBuilder->setMBB(*EntryBB);
4032 
4033   DebugLoc DbgLoc = F.getEntryBlock().getFirstNonPHI()->getDebugLoc();
4034   SwiftError.setFunction(CurMF);
4035   SwiftError.createEntriesInEntryBlock(DbgLoc);
4036 
4037   bool IsVarArg = F.isVarArg();
4038   bool HasMustTailInVarArgFn = false;
4039 
4040   // Create all blocks, in IR order, to preserve the layout.
4041   FuncInfo.MBBMap.resize(F.getMaxBlockNumber());
4042   for (const BasicBlock &BB: F) {
4043     auto *&MBB = FuncInfo.MBBMap[BB.getNumber()];
4044 
4045     MBB = MF->CreateMachineBasicBlock(&BB);
4046     MF->push_back(MBB);
4047 
4048     if (BB.hasAddressTaken())
4049       MBB->setAddressTakenIRBlock(const_cast<BasicBlock *>(&BB));
4050 
4051     if (!HasMustTailInVarArgFn)
4052       HasMustTailInVarArgFn = checkForMustTailInVarArgFn(IsVarArg, BB);
4053   }
4054 
4055   MF->getFrameInfo().setHasMustTailInVarArgFunc(HasMustTailInVarArgFn);
4056 
4057   // Make our arguments/constants entry block fallthrough to the IR entry block.
4058   EntryBB->addSuccessor(&getMBB(F.front()));
4059 
4060   if (CLI->fallBackToDAGISel(*MF)) {
4061     OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure",
4062                                F.getSubprogram(), &F.getEntryBlock());
4063     R << "unable to lower function: "
4064       << ore::NV("Prototype", F.getFunctionType());
4065     reportTranslationError(*MF, *TPC, *ORE, R);
4066     return false;
4067   }
4068 
4069   // Lower the actual args into this basic block.
4070   SmallVector<ArrayRef<Register>, 8> VRegArgs;
4071   for (const Argument &Arg: F.args()) {
4072     if (DL->getTypeStoreSize(Arg.getType()).isZero())
4073       continue; // Don't handle zero sized types.
4074     ArrayRef<Register> VRegs = getOrCreateVRegs(Arg);
4075     VRegArgs.push_back(VRegs);
4076 
4077     if (Arg.hasSwiftErrorAttr()) {
4078       assert(VRegs.size() == 1 && "Too many vregs for Swift error");
4079       SwiftError.setCurrentVReg(EntryBB, SwiftError.getFunctionArg(), VRegs[0]);
4080     }
4081   }
4082 
4083   if (!CLI->lowerFormalArguments(*EntryBuilder, F, VRegArgs, FuncInfo)) {
4084     OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure",
4085                                F.getSubprogram(), &F.getEntryBlock());
4086     R << "unable to lower arguments: "
4087       << ore::NV("Prototype", F.getFunctionType());
4088     reportTranslationError(*MF, *TPC, *ORE, R);
4089     return false;
4090   }
4091 
4092   // Need to visit defs before uses when translating instructions.
4093   GISelObserverWrapper WrapperObserver;
4094   if (EnableCSE && CSEInfo)
4095     WrapperObserver.addObserver(CSEInfo);
4096   {
4097     ReversePostOrderTraversal<const Function *> RPOT(&F);
4098 #ifndef NDEBUG
4099     DILocationVerifier Verifier;
4100     WrapperObserver.addObserver(&Verifier);
4101 #endif // ifndef NDEBUG
4102     RAIIMFObsDelInstaller ObsInstall(*MF, WrapperObserver);
4103     for (const BasicBlock *BB : RPOT) {
4104       MachineBasicBlock &MBB = getMBB(*BB);
4105       // Set the insertion point of all the following translations to
4106       // the end of this basic block.
4107       CurBuilder->setMBB(MBB);
4108       HasTailCall = false;
4109       for (const Instruction &Inst : *BB) {
4110         // If we translated a tail call in the last step, then we know
4111         // everything after the call is either a return, or something that is
4112         // handled by the call itself. (E.g. a lifetime marker or assume
4113         // intrinsic.) In this case, we should stop translating the block and
4114         // move on.
4115         if (HasTailCall)
4116           break;
4117 #ifndef NDEBUG
4118         Verifier.setCurrentInst(&Inst);
4119 #endif // ifndef NDEBUG
4120 
4121         // Translate any debug-info attached to the instruction.
4122         translateDbgInfo(Inst, *CurBuilder);
4123 
4124         if (translate(Inst))
4125           continue;
4126 
4127         OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure",
4128                                    Inst.getDebugLoc(), BB);
4129         R << "unable to translate instruction: " << ore::NV("Opcode", &Inst);
4130 
4131         if (ORE->allowExtraAnalysis("gisel-irtranslator")) {
4132           std::string InstStrStorage;
4133           raw_string_ostream InstStr(InstStrStorage);
4134           InstStr << Inst;
4135 
4136           R << ": '" << InstStrStorage << "'";
4137         }
4138 
4139         reportTranslationError(*MF, *TPC, *ORE, R);
4140         return false;
4141       }
4142 
4143       if (!finalizeBasicBlock(*BB, MBB)) {
4144         OptimizationRemarkMissed R("gisel-irtranslator", "GISelFailure",
4145                                    BB->getTerminator()->getDebugLoc(), BB);
4146         R << "unable to translate basic block";
4147         reportTranslationError(*MF, *TPC, *ORE, R);
4148         return false;
4149       }
4150     }
4151 #ifndef NDEBUG
4152     WrapperObserver.removeObserver(&Verifier);
4153 #endif
4154   }
4155 
4156   finishPendingPhis();
4157 
4158   SwiftError.propagateVRegs();
4159 
4160   // Merge the argument lowering and constants block with its single
4161   // successor, the LLVM-IR entry block.  We want the basic block to
4162   // be maximal.
4163   assert(EntryBB->succ_size() == 1 &&
4164          "Custom BB used for lowering should have only one successor");
4165   // Get the successor of the current entry block.
4166   MachineBasicBlock &NewEntryBB = **EntryBB->succ_begin();
4167   assert(NewEntryBB.pred_size() == 1 &&
4168          "LLVM-IR entry block has a predecessor!?");
4169   // Move all the instruction from the current entry block to the
4170   // new entry block.
4171   NewEntryBB.splice(NewEntryBB.begin(), EntryBB, EntryBB->begin(),
4172                     EntryBB->end());
4173 
4174   // Update the live-in information for the new entry block.
4175   for (const MachineBasicBlock::RegisterMaskPair &LiveIn : EntryBB->liveins())
4176     NewEntryBB.addLiveIn(LiveIn);
4177   NewEntryBB.sortUniqueLiveIns();
4178 
4179   // Get rid of the now empty basic block.
4180   EntryBB->removeSuccessor(&NewEntryBB);
4181   MF->remove(EntryBB);
4182   MF->deleteMachineBasicBlock(EntryBB);
4183 
4184   assert(&MF->front() == &NewEntryBB &&
4185          "New entry wasn't next in the list of basic block!");
4186 
4187   // Initialize stack protector information.
4188   StackProtector &SP = getAnalysis<StackProtector>();
4189   SP.copyToMachineFrameInfo(MF->getFrameInfo());
4190 
4191   return false;
4192 }
4193