xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/SelectionDAG/FastISel.cpp (revision 0d8fe2373503aeac48492f28073049a8bfa4feb5)
1 //===- FastISel.cpp - Implementation of the FastISel class ----------------===//
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 //
9 // This file contains the implementation of the FastISel class.
10 //
11 // "Fast" instruction selection is designed to emit very poor code quickly.
12 // Also, it is not designed to be able to do much lowering, so most illegal
13 // types (e.g. i64 on 32-bit targets) and operations are not supported.  It is
14 // also not intended to be able to do much optimization, except in a few cases
15 // where doing optimizations reduces overall compile time.  For example, folding
16 // constants into immediate fields is often done, because it's cheap and it
17 // reduces the number of instructions later phases have to examine.
18 //
19 // "Fast" instruction selection is able to fail gracefully and transfer
20 // control to the SelectionDAG selector for operations that it doesn't
21 // support.  In many cases, this allows us to avoid duplicating a lot of
22 // the complicated lowering logic that SelectionDAG currently has.
23 //
24 // The intended use for "fast" instruction selection is "-O0" mode
25 // compilation, where the quality of the generated code is irrelevant when
26 // weighed against the speed at which the code can be generated.  Also,
27 // at -O0, the LLVM optimizers are not running, and this makes the
28 // compile time of codegen a much higher portion of the overall compile
29 // time.  Despite its limitations, "fast" instruction selection is able to
30 // handle enough code on its own to provide noticeable overall speedups
31 // in -O0 compiles.
32 //
33 // Basic operations are supported in a target-independent way, by reading
34 // the same instruction descriptions that the SelectionDAG selector reads,
35 // and identifying simple arithmetic operations that can be directly selected
36 // from simple operators.  More complicated operations currently require
37 // target-specific code.
38 //
39 //===----------------------------------------------------------------------===//
40 
41 #include "llvm/CodeGen/FastISel.h"
42 #include "llvm/ADT/APFloat.h"
43 #include "llvm/ADT/APSInt.h"
44 #include "llvm/ADT/DenseMap.h"
45 #include "llvm/ADT/Optional.h"
46 #include "llvm/ADT/SmallPtrSet.h"
47 #include "llvm/ADT/SmallString.h"
48 #include "llvm/ADT/SmallVector.h"
49 #include "llvm/ADT/Statistic.h"
50 #include "llvm/Analysis/BranchProbabilityInfo.h"
51 #include "llvm/Analysis/TargetLibraryInfo.h"
52 #include "llvm/CodeGen/Analysis.h"
53 #include "llvm/CodeGen/FunctionLoweringInfo.h"
54 #include "llvm/CodeGen/ISDOpcodes.h"
55 #include "llvm/CodeGen/MachineBasicBlock.h"
56 #include "llvm/CodeGen/MachineFrameInfo.h"
57 #include "llvm/CodeGen/MachineInstr.h"
58 #include "llvm/CodeGen/MachineInstrBuilder.h"
59 #include "llvm/CodeGen/MachineMemOperand.h"
60 #include "llvm/CodeGen/MachineModuleInfo.h"
61 #include "llvm/CodeGen/MachineOperand.h"
62 #include "llvm/CodeGen/MachineRegisterInfo.h"
63 #include "llvm/CodeGen/StackMaps.h"
64 #include "llvm/CodeGen/TargetInstrInfo.h"
65 #include "llvm/CodeGen/TargetLowering.h"
66 #include "llvm/CodeGen/TargetSubtargetInfo.h"
67 #include "llvm/CodeGen/ValueTypes.h"
68 #include "llvm/IR/Argument.h"
69 #include "llvm/IR/Attributes.h"
70 #include "llvm/IR/BasicBlock.h"
71 #include "llvm/IR/CallingConv.h"
72 #include "llvm/IR/Constant.h"
73 #include "llvm/IR/Constants.h"
74 #include "llvm/IR/DataLayout.h"
75 #include "llvm/IR/DebugInfo.h"
76 #include "llvm/IR/DebugLoc.h"
77 #include "llvm/IR/DerivedTypes.h"
78 #include "llvm/IR/Function.h"
79 #include "llvm/IR/GetElementPtrTypeIterator.h"
80 #include "llvm/IR/GlobalValue.h"
81 #include "llvm/IR/InlineAsm.h"
82 #include "llvm/IR/InstrTypes.h"
83 #include "llvm/IR/Instruction.h"
84 #include "llvm/IR/Instructions.h"
85 #include "llvm/IR/IntrinsicInst.h"
86 #include "llvm/IR/LLVMContext.h"
87 #include "llvm/IR/Mangler.h"
88 #include "llvm/IR/Metadata.h"
89 #include "llvm/IR/Operator.h"
90 #include "llvm/IR/PatternMatch.h"
91 #include "llvm/IR/Type.h"
92 #include "llvm/IR/User.h"
93 #include "llvm/IR/Value.h"
94 #include "llvm/MC/MCContext.h"
95 #include "llvm/MC/MCInstrDesc.h"
96 #include "llvm/MC/MCRegisterInfo.h"
97 #include "llvm/Support/Casting.h"
98 #include "llvm/Support/Debug.h"
99 #include "llvm/Support/ErrorHandling.h"
100 #include "llvm/Support/MachineValueType.h"
101 #include "llvm/Support/MathExtras.h"
102 #include "llvm/Support/raw_ostream.h"
103 #include "llvm/Target/TargetMachine.h"
104 #include "llvm/Target/TargetOptions.h"
105 #include <algorithm>
106 #include <cassert>
107 #include <cstdint>
108 #include <iterator>
109 #include <utility>
110 
111 using namespace llvm;
112 using namespace PatternMatch;
113 
114 #define DEBUG_TYPE "isel"
115 
116 STATISTIC(NumFastIselSuccessIndependent, "Number of insts selected by "
117                                          "target-independent selector");
118 STATISTIC(NumFastIselSuccessTarget, "Number of insts selected by "
119                                     "target-specific selector");
120 STATISTIC(NumFastIselDead, "Number of dead insts removed on failure");
121 
122 /// Set the current block to which generated machine instructions will be
123 /// appended.
124 void FastISel::startNewBlock() {
125   assert(LocalValueMap.empty() &&
126          "local values should be cleared after finishing a BB");
127 
128   // Instructions are appended to FuncInfo.MBB. If the basic block already
129   // contains labels or copies, use the last instruction as the last local
130   // value.
131   EmitStartPt = nullptr;
132   if (!FuncInfo.MBB->empty())
133     EmitStartPt = &FuncInfo.MBB->back();
134   LastLocalValue = EmitStartPt;
135 }
136 
137 void FastISel::finishBasicBlock() { flushLocalValueMap(); }
138 
139 bool FastISel::lowerArguments() {
140   if (!FuncInfo.CanLowerReturn)
141     // Fallback to SDISel argument lowering code to deal with sret pointer
142     // parameter.
143     return false;
144 
145   if (!fastLowerArguments())
146     return false;
147 
148   // Enter arguments into ValueMap for uses in non-entry BBs.
149   for (Function::const_arg_iterator I = FuncInfo.Fn->arg_begin(),
150                                     E = FuncInfo.Fn->arg_end();
151        I != E; ++I) {
152     DenseMap<const Value *, Register>::iterator VI = LocalValueMap.find(&*I);
153     assert(VI != LocalValueMap.end() && "Missed an argument?");
154     FuncInfo.ValueMap[&*I] = VI->second;
155   }
156   return true;
157 }
158 
159 /// Return the defined register if this instruction defines exactly one
160 /// virtual register and uses no other virtual registers. Otherwise return 0.
161 static Register findLocalRegDef(MachineInstr &MI) {
162   Register RegDef;
163   for (const MachineOperand &MO : MI.operands()) {
164     if (!MO.isReg())
165       continue;
166     if (MO.isDef()) {
167       if (RegDef)
168         return Register();
169       RegDef = MO.getReg();
170     } else if (MO.getReg().isVirtual()) {
171       // This is another use of a vreg. Don't delete it.
172       return Register();
173     }
174   }
175   return RegDef;
176 }
177 
178 static bool isRegUsedByPhiNodes(Register DefReg,
179                                 FunctionLoweringInfo &FuncInfo) {
180   for (auto &P : FuncInfo.PHINodesToUpdate)
181     if (P.second == DefReg)
182       return true;
183   return false;
184 }
185 
186 void FastISel::flushLocalValueMap() {
187   // If FastISel bails out, it could leave local value instructions behind
188   // that aren't used for anything.  Detect and erase those.
189   if (LastLocalValue != EmitStartPt) {
190     // Save the first instruction after local values, for later.
191     MachineBasicBlock::iterator FirstNonValue(LastLocalValue);
192     ++FirstNonValue;
193 
194     MachineBasicBlock::reverse_iterator RE =
195         EmitStartPt ? MachineBasicBlock::reverse_iterator(EmitStartPt)
196                     : FuncInfo.MBB->rend();
197     MachineBasicBlock::reverse_iterator RI(LastLocalValue);
198     for (; RI != RE;) {
199       MachineInstr &LocalMI = *RI;
200       // Increment before erasing what it points to.
201       ++RI;
202       Register DefReg = findLocalRegDef(LocalMI);
203       if (!DefReg)
204         continue;
205       if (FuncInfo.RegsWithFixups.count(DefReg))
206         continue;
207       bool UsedByPHI = isRegUsedByPhiNodes(DefReg, FuncInfo);
208       if (!UsedByPHI && MRI.use_nodbg_empty(DefReg)) {
209         if (EmitStartPt == &LocalMI)
210           EmitStartPt = EmitStartPt->getPrevNode();
211         LLVM_DEBUG(dbgs() << "removing dead local value materialization"
212                           << LocalMI);
213         LocalMI.eraseFromParent();
214       }
215     }
216 
217     if (FirstNonValue != FuncInfo.MBB->end()) {
218       // See if there are any local value instructions left.  If so, we want to
219       // make sure the first one has a debug location; if it doesn't, use the
220       // first non-value instruction's debug location.
221 
222       // If EmitStartPt is non-null, this block had copies at the top before
223       // FastISel started doing anything; it points to the last one, so the
224       // first local value instruction is the one after EmitStartPt.
225       // If EmitStartPt is null, the first local value instruction is at the
226       // top of the block.
227       MachineBasicBlock::iterator FirstLocalValue =
228           EmitStartPt ? ++MachineBasicBlock::iterator(EmitStartPt)
229                       : FuncInfo.MBB->begin();
230       if (FirstLocalValue != FirstNonValue && !FirstLocalValue->getDebugLoc())
231         FirstLocalValue->setDebugLoc(FirstNonValue->getDebugLoc());
232     }
233   }
234 
235   LocalValueMap.clear();
236   LastLocalValue = EmitStartPt;
237   recomputeInsertPt();
238   SavedInsertPt = FuncInfo.InsertPt;
239 }
240 
241 bool FastISel::hasTrivialKill(const Value *V) {
242   // Don't consider constants or arguments to have trivial kills.
243   const Instruction *I = dyn_cast<Instruction>(V);
244   if (!I)
245     return false;
246 
247   // No-op casts are trivially coalesced by fast-isel.
248   if (const auto *Cast = dyn_cast<CastInst>(I))
249     if (Cast->isNoopCast(DL) && !hasTrivialKill(Cast->getOperand(0)))
250       return false;
251 
252   // Even the value might have only one use in the LLVM IR, it is possible that
253   // FastISel might fold the use into another instruction and now there is more
254   // than one use at the Machine Instruction level.
255   Register Reg = lookUpRegForValue(V);
256   if (Reg && !MRI.use_empty(Reg))
257     return false;
258 
259   // GEPs with all zero indices are trivially coalesced by fast-isel.
260   if (const auto *GEP = dyn_cast<GetElementPtrInst>(I))
261     if (GEP->hasAllZeroIndices() && !hasTrivialKill(GEP->getOperand(0)))
262       return false;
263 
264   // Casts and extractvalues may be trivially coalesced by fast-isel.
265   if (I->getOpcode() == Instruction::BitCast ||
266       I->getOpcode() == Instruction::PtrToInt ||
267       I->getOpcode() == Instruction::IntToPtr ||
268       I->getOpcode() == Instruction::ExtractValue)
269     return false;
270 
271   // Only instructions with a single use in the same basic block are considered
272   // to have trivial kills.
273   return I->hasOneUse() &&
274          cast<Instruction>(*I->user_begin())->getParent() == I->getParent();
275 }
276 
277 Register FastISel::getRegForValue(const Value *V) {
278   EVT RealVT = TLI.getValueType(DL, V->getType(), /*AllowUnknown=*/true);
279   // Don't handle non-simple values in FastISel.
280   if (!RealVT.isSimple())
281     return Register();
282 
283   // Ignore illegal types. We must do this before looking up the value
284   // in ValueMap because Arguments are given virtual registers regardless
285   // of whether FastISel can handle them.
286   MVT VT = RealVT.getSimpleVT();
287   if (!TLI.isTypeLegal(VT)) {
288     // Handle integer promotions, though, because they're common and easy.
289     if (VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16)
290       VT = TLI.getTypeToTransformTo(V->getContext(), VT).getSimpleVT();
291     else
292       return Register();
293   }
294 
295   // Look up the value to see if we already have a register for it.
296   Register Reg = lookUpRegForValue(V);
297   if (Reg)
298     return Reg;
299 
300   // In bottom-up mode, just create the virtual register which will be used
301   // to hold the value. It will be materialized later.
302   if (isa<Instruction>(V) &&
303       (!isa<AllocaInst>(V) ||
304        !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(V))))
305     return FuncInfo.InitializeRegForValue(V);
306 
307   SavePoint SaveInsertPt = enterLocalValueArea();
308 
309   // Materialize the value in a register. Emit any instructions in the
310   // local value area.
311   Reg = materializeRegForValue(V, VT);
312 
313   leaveLocalValueArea(SaveInsertPt);
314 
315   return Reg;
316 }
317 
318 Register FastISel::materializeConstant(const Value *V, MVT VT) {
319   Register Reg;
320   if (const auto *CI = dyn_cast<ConstantInt>(V)) {
321     if (CI->getValue().getActiveBits() <= 64)
322       Reg = fastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue());
323   } else if (isa<AllocaInst>(V))
324     Reg = fastMaterializeAlloca(cast<AllocaInst>(V));
325   else if (isa<ConstantPointerNull>(V))
326     // Translate this as an integer zero so that it can be
327     // local-CSE'd with actual integer zeros.
328     Reg =
329         getRegForValue(Constant::getNullValue(DL.getIntPtrType(V->getType())));
330   else if (const auto *CF = dyn_cast<ConstantFP>(V)) {
331     if (CF->isNullValue())
332       Reg = fastMaterializeFloatZero(CF);
333     else
334       // Try to emit the constant directly.
335       Reg = fastEmit_f(VT, VT, ISD::ConstantFP, CF);
336 
337     if (!Reg) {
338       // Try to emit the constant by using an integer constant with a cast.
339       const APFloat &Flt = CF->getValueAPF();
340       EVT IntVT = TLI.getPointerTy(DL);
341       uint32_t IntBitWidth = IntVT.getSizeInBits();
342       APSInt SIntVal(IntBitWidth, /*isUnsigned=*/false);
343       bool isExact;
344       (void)Flt.convertToInteger(SIntVal, APFloat::rmTowardZero, &isExact);
345       if (isExact) {
346         Register IntegerReg =
347             getRegForValue(ConstantInt::get(V->getContext(), SIntVal));
348         if (IntegerReg)
349           Reg = fastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP, IntegerReg,
350                            /*Op0IsKill=*/false);
351       }
352     }
353   } else if (const auto *Op = dyn_cast<Operator>(V)) {
354     if (!selectOperator(Op, Op->getOpcode()))
355       if (!isa<Instruction>(Op) ||
356           !fastSelectInstruction(cast<Instruction>(Op)))
357         return 0;
358     Reg = lookUpRegForValue(Op);
359   } else if (isa<UndefValue>(V)) {
360     Reg = createResultReg(TLI.getRegClassFor(VT));
361     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
362             TII.get(TargetOpcode::IMPLICIT_DEF), Reg);
363   }
364   return Reg;
365 }
366 
367 /// Helper for getRegForValue. This function is called when the value isn't
368 /// already available in a register and must be materialized with new
369 /// instructions.
370 Register FastISel::materializeRegForValue(const Value *V, MVT VT) {
371   Register Reg;
372   // Give the target-specific code a try first.
373   if (isa<Constant>(V))
374     Reg = fastMaterializeConstant(cast<Constant>(V));
375 
376   // If target-specific code couldn't or didn't want to handle the value, then
377   // give target-independent code a try.
378   if (!Reg)
379     Reg = materializeConstant(V, VT);
380 
381   // Don't cache constant materializations in the general ValueMap.
382   // To do so would require tracking what uses they dominate.
383   if (Reg) {
384     LocalValueMap[V] = Reg;
385     LastLocalValue = MRI.getVRegDef(Reg);
386   }
387   return Reg;
388 }
389 
390 Register FastISel::lookUpRegForValue(const Value *V) {
391   // Look up the value to see if we already have a register for it. We
392   // cache values defined by Instructions across blocks, and other values
393   // only locally. This is because Instructions already have the SSA
394   // def-dominates-use requirement enforced.
395   DenseMap<const Value *, Register>::iterator I = FuncInfo.ValueMap.find(V);
396   if (I != FuncInfo.ValueMap.end())
397     return I->second;
398   return LocalValueMap[V];
399 }
400 
401 void FastISel::updateValueMap(const Value *I, Register Reg, unsigned NumRegs) {
402   if (!isa<Instruction>(I)) {
403     LocalValueMap[I] = Reg;
404     return;
405   }
406 
407   Register &AssignedReg = FuncInfo.ValueMap[I];
408   if (!AssignedReg)
409     // Use the new register.
410     AssignedReg = Reg;
411   else if (Reg != AssignedReg) {
412     // Arrange for uses of AssignedReg to be replaced by uses of Reg.
413     for (unsigned i = 0; i < NumRegs; i++) {
414       FuncInfo.RegFixups[AssignedReg + i] = Reg + i;
415       FuncInfo.RegsWithFixups.insert(Reg + i);
416     }
417 
418     AssignedReg = Reg;
419   }
420 }
421 
422 std::pair<Register, bool> FastISel::getRegForGEPIndex(const Value *Idx) {
423   Register IdxN = getRegForValue(Idx);
424   if (!IdxN)
425     // Unhandled operand. Halt "fast" selection and bail.
426     return std::pair<Register, bool>(Register(), false);
427 
428   bool IdxNIsKill = hasTrivialKill(Idx);
429 
430   // If the index is smaller or larger than intptr_t, truncate or extend it.
431   MVT PtrVT = TLI.getPointerTy(DL);
432   EVT IdxVT = EVT::getEVT(Idx->getType(), /*HandleUnknown=*/false);
433   if (IdxVT.bitsLT(PtrVT)) {
434     IdxN = fastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::SIGN_EXTEND, IdxN,
435                       IdxNIsKill);
436     IdxNIsKill = true;
437   } else if (IdxVT.bitsGT(PtrVT)) {
438     IdxN =
439         fastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::TRUNCATE, IdxN, IdxNIsKill);
440     IdxNIsKill = true;
441   }
442   return std::pair<Register, bool>(IdxN, IdxNIsKill);
443 }
444 
445 void FastISel::recomputeInsertPt() {
446   if (getLastLocalValue()) {
447     FuncInfo.InsertPt = getLastLocalValue();
448     FuncInfo.MBB = FuncInfo.InsertPt->getParent();
449     ++FuncInfo.InsertPt;
450   } else
451     FuncInfo.InsertPt = FuncInfo.MBB->getFirstNonPHI();
452 
453   // Now skip past any EH_LABELs, which must remain at the beginning.
454   while (FuncInfo.InsertPt != FuncInfo.MBB->end() &&
455          FuncInfo.InsertPt->getOpcode() == TargetOpcode::EH_LABEL)
456     ++FuncInfo.InsertPt;
457 }
458 
459 void FastISel::removeDeadCode(MachineBasicBlock::iterator I,
460                               MachineBasicBlock::iterator E) {
461   assert(I.isValid() && E.isValid() && std::distance(I, E) > 0 &&
462          "Invalid iterator!");
463   while (I != E) {
464     if (SavedInsertPt == I)
465       SavedInsertPt = E;
466     if (EmitStartPt == I)
467       EmitStartPt = E.isValid() ? &*E : nullptr;
468     if (LastLocalValue == I)
469       LastLocalValue = E.isValid() ? &*E : nullptr;
470 
471     MachineInstr *Dead = &*I;
472     ++I;
473     Dead->eraseFromParent();
474     ++NumFastIselDead;
475   }
476   recomputeInsertPt();
477 }
478 
479 FastISel::SavePoint FastISel::enterLocalValueArea() {
480   SavePoint OldInsertPt = FuncInfo.InsertPt;
481   recomputeInsertPt();
482   return OldInsertPt;
483 }
484 
485 void FastISel::leaveLocalValueArea(SavePoint OldInsertPt) {
486   if (FuncInfo.InsertPt != FuncInfo.MBB->begin())
487     LastLocalValue = &*std::prev(FuncInfo.InsertPt);
488 
489   // Restore the previous insert position.
490   FuncInfo.InsertPt = OldInsertPt;
491 }
492 
493 bool FastISel::selectBinaryOp(const User *I, unsigned ISDOpcode) {
494   EVT VT = EVT::getEVT(I->getType(), /*HandleUnknown=*/true);
495   if (VT == MVT::Other || !VT.isSimple())
496     // Unhandled type. Halt "fast" selection and bail.
497     return false;
498 
499   // We only handle legal types. For example, on x86-32 the instruction
500   // selector contains all of the 64-bit instructions from x86-64,
501   // under the assumption that i64 won't be used if the target doesn't
502   // support it.
503   if (!TLI.isTypeLegal(VT)) {
504     // MVT::i1 is special. Allow AND, OR, or XOR because they
505     // don't require additional zeroing, which makes them easy.
506     if (VT == MVT::i1 && (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR ||
507                           ISDOpcode == ISD::XOR))
508       VT = TLI.getTypeToTransformTo(I->getContext(), VT);
509     else
510       return false;
511   }
512 
513   // Check if the first operand is a constant, and handle it as "ri".  At -O0,
514   // we don't have anything that canonicalizes operand order.
515   if (const auto *CI = dyn_cast<ConstantInt>(I->getOperand(0)))
516     if (isa<Instruction>(I) && cast<Instruction>(I)->isCommutative()) {
517       Register Op1 = getRegForValue(I->getOperand(1));
518       if (!Op1)
519         return false;
520       bool Op1IsKill = hasTrivialKill(I->getOperand(1));
521 
522       Register ResultReg =
523           fastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op1, Op1IsKill,
524                        CI->getZExtValue(), VT.getSimpleVT());
525       if (!ResultReg)
526         return false;
527 
528       // We successfully emitted code for the given LLVM Instruction.
529       updateValueMap(I, ResultReg);
530       return true;
531     }
532 
533   Register Op0 = getRegForValue(I->getOperand(0));
534   if (!Op0) // Unhandled operand. Halt "fast" selection and bail.
535     return false;
536   bool Op0IsKill = hasTrivialKill(I->getOperand(0));
537 
538   // Check if the second operand is a constant and handle it appropriately.
539   if (const auto *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
540     uint64_t Imm = CI->getSExtValue();
541 
542     // Transform "sdiv exact X, 8" -> "sra X, 3".
543     if (ISDOpcode == ISD::SDIV && isa<BinaryOperator>(I) &&
544         cast<BinaryOperator>(I)->isExact() && isPowerOf2_64(Imm)) {
545       Imm = Log2_64(Imm);
546       ISDOpcode = ISD::SRA;
547     }
548 
549     // Transform "urem x, pow2" -> "and x, pow2-1".
550     if (ISDOpcode == ISD::UREM && isa<BinaryOperator>(I) &&
551         isPowerOf2_64(Imm)) {
552       --Imm;
553       ISDOpcode = ISD::AND;
554     }
555 
556     Register ResultReg = fastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op0,
557                                       Op0IsKill, Imm, VT.getSimpleVT());
558     if (!ResultReg)
559       return false;
560 
561     // We successfully emitted code for the given LLVM Instruction.
562     updateValueMap(I, ResultReg);
563     return true;
564   }
565 
566   Register Op1 = getRegForValue(I->getOperand(1));
567   if (!Op1) // Unhandled operand. Halt "fast" selection and bail.
568     return false;
569   bool Op1IsKill = hasTrivialKill(I->getOperand(1));
570 
571   // Now we have both operands in registers. Emit the instruction.
572   Register ResultReg = fastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(),
573                                    ISDOpcode, Op0, Op0IsKill, Op1, Op1IsKill);
574   if (!ResultReg)
575     // Target-specific code wasn't able to find a machine opcode for
576     // the given ISD opcode and type. Halt "fast" selection and bail.
577     return false;
578 
579   // We successfully emitted code for the given LLVM Instruction.
580   updateValueMap(I, ResultReg);
581   return true;
582 }
583 
584 bool FastISel::selectGetElementPtr(const User *I) {
585   Register N = getRegForValue(I->getOperand(0));
586   if (!N) // Unhandled operand. Halt "fast" selection and bail.
587     return false;
588 
589   // FIXME: The code below does not handle vector GEPs. Halt "fast" selection
590   // and bail.
591   if (isa<VectorType>(I->getType()))
592     return false;
593 
594   bool NIsKill = hasTrivialKill(I->getOperand(0));
595 
596   // Keep a running tab of the total offset to coalesce multiple N = N + Offset
597   // into a single N = N + TotalOffset.
598   uint64_t TotalOffs = 0;
599   // FIXME: What's a good SWAG number for MaxOffs?
600   uint64_t MaxOffs = 2048;
601   MVT VT = TLI.getPointerTy(DL);
602   for (gep_type_iterator GTI = gep_type_begin(I), E = gep_type_end(I);
603        GTI != E; ++GTI) {
604     const Value *Idx = GTI.getOperand();
605     if (StructType *StTy = GTI.getStructTypeOrNull()) {
606       uint64_t Field = cast<ConstantInt>(Idx)->getZExtValue();
607       if (Field) {
608         // N = N + Offset
609         TotalOffs += DL.getStructLayout(StTy)->getElementOffset(Field);
610         if (TotalOffs >= MaxOffs) {
611           N = fastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
612           if (!N) // Unhandled operand. Halt "fast" selection and bail.
613             return false;
614           NIsKill = true;
615           TotalOffs = 0;
616         }
617       }
618     } else {
619       Type *Ty = GTI.getIndexedType();
620 
621       // If this is a constant subscript, handle it quickly.
622       if (const auto *CI = dyn_cast<ConstantInt>(Idx)) {
623         if (CI->isZero())
624           continue;
625         // N = N + Offset
626         uint64_t IdxN = CI->getValue().sextOrTrunc(64).getSExtValue();
627         TotalOffs += DL.getTypeAllocSize(Ty) * IdxN;
628         if (TotalOffs >= MaxOffs) {
629           N = fastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
630           if (!N) // Unhandled operand. Halt "fast" selection and bail.
631             return false;
632           NIsKill = true;
633           TotalOffs = 0;
634         }
635         continue;
636       }
637       if (TotalOffs) {
638         N = fastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
639         if (!N) // Unhandled operand. Halt "fast" selection and bail.
640           return false;
641         NIsKill = true;
642         TotalOffs = 0;
643       }
644 
645       // N = N + Idx * ElementSize;
646       uint64_t ElementSize = DL.getTypeAllocSize(Ty);
647       std::pair<Register, bool> Pair = getRegForGEPIndex(Idx);
648       Register IdxN = Pair.first;
649       bool IdxNIsKill = Pair.second;
650       if (!IdxN) // Unhandled operand. Halt "fast" selection and bail.
651         return false;
652 
653       if (ElementSize != 1) {
654         IdxN = fastEmit_ri_(VT, ISD::MUL, IdxN, IdxNIsKill, ElementSize, VT);
655         if (!IdxN) // Unhandled operand. Halt "fast" selection and bail.
656           return false;
657         IdxNIsKill = true;
658       }
659       N = fastEmit_rr(VT, VT, ISD::ADD, N, NIsKill, IdxN, IdxNIsKill);
660       if (!N) // Unhandled operand. Halt "fast" selection and bail.
661         return false;
662     }
663   }
664   if (TotalOffs) {
665     N = fastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
666     if (!N) // Unhandled operand. Halt "fast" selection and bail.
667       return false;
668   }
669 
670   // We successfully emitted code for the given LLVM Instruction.
671   updateValueMap(I, N);
672   return true;
673 }
674 
675 bool FastISel::addStackMapLiveVars(SmallVectorImpl<MachineOperand> &Ops,
676                                    const CallInst *CI, unsigned StartIdx) {
677   for (unsigned i = StartIdx, e = CI->getNumArgOperands(); i != e; ++i) {
678     Value *Val = CI->getArgOperand(i);
679     // Check for constants and encode them with a StackMaps::ConstantOp prefix.
680     if (const auto *C = dyn_cast<ConstantInt>(Val)) {
681       Ops.push_back(MachineOperand::CreateImm(StackMaps::ConstantOp));
682       Ops.push_back(MachineOperand::CreateImm(C->getSExtValue()));
683     } else if (isa<ConstantPointerNull>(Val)) {
684       Ops.push_back(MachineOperand::CreateImm(StackMaps::ConstantOp));
685       Ops.push_back(MachineOperand::CreateImm(0));
686     } else if (auto *AI = dyn_cast<AllocaInst>(Val)) {
687       // Values coming from a stack location also require a special encoding,
688       // but that is added later on by the target specific frame index
689       // elimination implementation.
690       auto SI = FuncInfo.StaticAllocaMap.find(AI);
691       if (SI != FuncInfo.StaticAllocaMap.end())
692         Ops.push_back(MachineOperand::CreateFI(SI->second));
693       else
694         return false;
695     } else {
696       Register Reg = getRegForValue(Val);
697       if (!Reg)
698         return false;
699       Ops.push_back(MachineOperand::CreateReg(Reg, /*isDef=*/false));
700     }
701   }
702   return true;
703 }
704 
705 bool FastISel::selectStackmap(const CallInst *I) {
706   // void @llvm.experimental.stackmap(i64 <id>, i32 <numShadowBytes>,
707   //                                  [live variables...])
708   assert(I->getCalledFunction()->getReturnType()->isVoidTy() &&
709          "Stackmap cannot return a value.");
710 
711   // The stackmap intrinsic only records the live variables (the arguments
712   // passed to it) and emits NOPS (if requested). Unlike the patchpoint
713   // intrinsic, this won't be lowered to a function call. This means we don't
714   // have to worry about calling conventions and target-specific lowering code.
715   // Instead we perform the call lowering right here.
716   //
717   // CALLSEQ_START(0, 0...)
718   // STACKMAP(id, nbytes, ...)
719   // CALLSEQ_END(0, 0)
720   //
721   SmallVector<MachineOperand, 32> Ops;
722 
723   // Add the <id> and <numBytes> constants.
724   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::IDPos)) &&
725          "Expected a constant integer.");
726   const auto *ID = cast<ConstantInt>(I->getOperand(PatchPointOpers::IDPos));
727   Ops.push_back(MachineOperand::CreateImm(ID->getZExtValue()));
728 
729   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos)) &&
730          "Expected a constant integer.");
731   const auto *NumBytes =
732       cast<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos));
733   Ops.push_back(MachineOperand::CreateImm(NumBytes->getZExtValue()));
734 
735   // Push live variables for the stack map (skipping the first two arguments
736   // <id> and <numBytes>).
737   if (!addStackMapLiveVars(Ops, I, 2))
738     return false;
739 
740   // We are not adding any register mask info here, because the stackmap doesn't
741   // clobber anything.
742 
743   // Add scratch registers as implicit def and early clobber.
744   CallingConv::ID CC = I->getCallingConv();
745   const MCPhysReg *ScratchRegs = TLI.getScratchRegisters(CC);
746   for (unsigned i = 0; ScratchRegs[i]; ++i)
747     Ops.push_back(MachineOperand::CreateReg(
748         ScratchRegs[i], /*isDef=*/true, /*isImp=*/true, /*isKill=*/false,
749         /*isDead=*/false, /*isUndef=*/false, /*isEarlyClobber=*/true));
750 
751   // Issue CALLSEQ_START
752   unsigned AdjStackDown = TII.getCallFrameSetupOpcode();
753   auto Builder =
754       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AdjStackDown));
755   const MCInstrDesc &MCID = Builder.getInstr()->getDesc();
756   for (unsigned I = 0, E = MCID.getNumOperands(); I < E; ++I)
757     Builder.addImm(0);
758 
759   // Issue STACKMAP.
760   MachineInstrBuilder MIB = BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
761                                     TII.get(TargetOpcode::STACKMAP));
762   for (auto const &MO : Ops)
763     MIB.add(MO);
764 
765   // Issue CALLSEQ_END
766   unsigned AdjStackUp = TII.getCallFrameDestroyOpcode();
767   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AdjStackUp))
768       .addImm(0)
769       .addImm(0);
770 
771   // Inform the Frame Information that we have a stackmap in this function.
772   FuncInfo.MF->getFrameInfo().setHasStackMap();
773 
774   return true;
775 }
776 
777 /// Lower an argument list according to the target calling convention.
778 ///
779 /// This is a helper for lowering intrinsics that follow a target calling
780 /// convention or require stack pointer adjustment. Only a subset of the
781 /// intrinsic's operands need to participate in the calling convention.
782 bool FastISel::lowerCallOperands(const CallInst *CI, unsigned ArgIdx,
783                                  unsigned NumArgs, const Value *Callee,
784                                  bool ForceRetVoidTy, CallLoweringInfo &CLI) {
785   ArgListTy Args;
786   Args.reserve(NumArgs);
787 
788   // Populate the argument list.
789   for (unsigned ArgI = ArgIdx, ArgE = ArgIdx + NumArgs; ArgI != ArgE; ++ArgI) {
790     Value *V = CI->getOperand(ArgI);
791 
792     assert(!V->getType()->isEmptyTy() && "Empty type passed to intrinsic.");
793 
794     ArgListEntry Entry;
795     Entry.Val = V;
796     Entry.Ty = V->getType();
797     Entry.setAttributes(CI, ArgI);
798     Args.push_back(Entry);
799   }
800 
801   Type *RetTy = ForceRetVoidTy ? Type::getVoidTy(CI->getType()->getContext())
802                                : CI->getType();
803   CLI.setCallee(CI->getCallingConv(), RetTy, Callee, std::move(Args), NumArgs);
804 
805   return lowerCallTo(CLI);
806 }
807 
808 FastISel::CallLoweringInfo &FastISel::CallLoweringInfo::setCallee(
809     const DataLayout &DL, MCContext &Ctx, CallingConv::ID CC, Type *ResultTy,
810     StringRef Target, ArgListTy &&ArgsList, unsigned FixedArgs) {
811   SmallString<32> MangledName;
812   Mangler::getNameWithPrefix(MangledName, Target, DL);
813   MCSymbol *Sym = Ctx.getOrCreateSymbol(MangledName);
814   return setCallee(CC, ResultTy, Sym, std::move(ArgsList), FixedArgs);
815 }
816 
817 bool FastISel::selectPatchpoint(const CallInst *I) {
818   // void|i64 @llvm.experimental.patchpoint.void|i64(i64 <id>,
819   //                                                 i32 <numBytes>,
820   //                                                 i8* <target>,
821   //                                                 i32 <numArgs>,
822   //                                                 [Args...],
823   //                                                 [live variables...])
824   CallingConv::ID CC = I->getCallingConv();
825   bool IsAnyRegCC = CC == CallingConv::AnyReg;
826   bool HasDef = !I->getType()->isVoidTy();
827   Value *Callee = I->getOperand(PatchPointOpers::TargetPos)->stripPointerCasts();
828 
829   // Get the real number of arguments participating in the call <numArgs>
830   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NArgPos)) &&
831          "Expected a constant integer.");
832   const auto *NumArgsVal =
833       cast<ConstantInt>(I->getOperand(PatchPointOpers::NArgPos));
834   unsigned NumArgs = NumArgsVal->getZExtValue();
835 
836   // Skip the four meta args: <id>, <numNopBytes>, <target>, <numArgs>
837   // This includes all meta-operands up to but not including CC.
838   unsigned NumMetaOpers = PatchPointOpers::CCPos;
839   assert(I->getNumArgOperands() >= NumMetaOpers + NumArgs &&
840          "Not enough arguments provided to the patchpoint intrinsic");
841 
842   // For AnyRegCC the arguments are lowered later on manually.
843   unsigned NumCallArgs = IsAnyRegCC ? 0 : NumArgs;
844   CallLoweringInfo CLI;
845   CLI.setIsPatchPoint();
846   if (!lowerCallOperands(I, NumMetaOpers, NumCallArgs, Callee, IsAnyRegCC, CLI))
847     return false;
848 
849   assert(CLI.Call && "No call instruction specified.");
850 
851   SmallVector<MachineOperand, 32> Ops;
852 
853   // Add an explicit result reg if we use the anyreg calling convention.
854   if (IsAnyRegCC && HasDef) {
855     assert(CLI.NumResultRegs == 0 && "Unexpected result register.");
856     CLI.ResultReg = createResultReg(TLI.getRegClassFor(MVT::i64));
857     CLI.NumResultRegs = 1;
858     Ops.push_back(MachineOperand::CreateReg(CLI.ResultReg, /*isDef=*/true));
859   }
860 
861   // Add the <id> and <numBytes> constants.
862   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::IDPos)) &&
863          "Expected a constant integer.");
864   const auto *ID = cast<ConstantInt>(I->getOperand(PatchPointOpers::IDPos));
865   Ops.push_back(MachineOperand::CreateImm(ID->getZExtValue()));
866 
867   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos)) &&
868          "Expected a constant integer.");
869   const auto *NumBytes =
870       cast<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos));
871   Ops.push_back(MachineOperand::CreateImm(NumBytes->getZExtValue()));
872 
873   // Add the call target.
874   if (const auto *C = dyn_cast<IntToPtrInst>(Callee)) {
875     uint64_t CalleeConstAddr =
876       cast<ConstantInt>(C->getOperand(0))->getZExtValue();
877     Ops.push_back(MachineOperand::CreateImm(CalleeConstAddr));
878   } else if (const auto *C = dyn_cast<ConstantExpr>(Callee)) {
879     if (C->getOpcode() == Instruction::IntToPtr) {
880       uint64_t CalleeConstAddr =
881         cast<ConstantInt>(C->getOperand(0))->getZExtValue();
882       Ops.push_back(MachineOperand::CreateImm(CalleeConstAddr));
883     } else
884       llvm_unreachable("Unsupported ConstantExpr.");
885   } else if (const auto *GV = dyn_cast<GlobalValue>(Callee)) {
886     Ops.push_back(MachineOperand::CreateGA(GV, 0));
887   } else if (isa<ConstantPointerNull>(Callee))
888     Ops.push_back(MachineOperand::CreateImm(0));
889   else
890     llvm_unreachable("Unsupported callee address.");
891 
892   // Adjust <numArgs> to account for any arguments that have been passed on
893   // the stack instead.
894   unsigned NumCallRegArgs = IsAnyRegCC ? NumArgs : CLI.OutRegs.size();
895   Ops.push_back(MachineOperand::CreateImm(NumCallRegArgs));
896 
897   // Add the calling convention
898   Ops.push_back(MachineOperand::CreateImm((unsigned)CC));
899 
900   // Add the arguments we omitted previously. The register allocator should
901   // place these in any free register.
902   if (IsAnyRegCC) {
903     for (unsigned i = NumMetaOpers, e = NumMetaOpers + NumArgs; i != e; ++i) {
904       Register Reg = getRegForValue(I->getArgOperand(i));
905       if (!Reg)
906         return false;
907       Ops.push_back(MachineOperand::CreateReg(Reg, /*isDef=*/false));
908     }
909   }
910 
911   // Push the arguments from the call instruction.
912   for (auto Reg : CLI.OutRegs)
913     Ops.push_back(MachineOperand::CreateReg(Reg, /*isDef=*/false));
914 
915   // Push live variables for the stack map.
916   if (!addStackMapLiveVars(Ops, I, NumMetaOpers + NumArgs))
917     return false;
918 
919   // Push the register mask info.
920   Ops.push_back(MachineOperand::CreateRegMask(
921       TRI.getCallPreservedMask(*FuncInfo.MF, CC)));
922 
923   // Add scratch registers as implicit def and early clobber.
924   const MCPhysReg *ScratchRegs = TLI.getScratchRegisters(CC);
925   for (unsigned i = 0; ScratchRegs[i]; ++i)
926     Ops.push_back(MachineOperand::CreateReg(
927         ScratchRegs[i], /*isDef=*/true, /*isImp=*/true, /*isKill=*/false,
928         /*isDead=*/false, /*isUndef=*/false, /*isEarlyClobber=*/true));
929 
930   // Add implicit defs (return values).
931   for (auto Reg : CLI.InRegs)
932     Ops.push_back(MachineOperand::CreateReg(Reg, /*isDef=*/true,
933                                             /*isImp=*/true));
934 
935   // Insert the patchpoint instruction before the call generated by the target.
936   MachineInstrBuilder MIB = BuildMI(*FuncInfo.MBB, CLI.Call, DbgLoc,
937                                     TII.get(TargetOpcode::PATCHPOINT));
938 
939   for (auto &MO : Ops)
940     MIB.add(MO);
941 
942   MIB->setPhysRegsDeadExcept(CLI.InRegs, TRI);
943 
944   // Delete the original call instruction.
945   CLI.Call->eraseFromParent();
946 
947   // Inform the Frame Information that we have a patchpoint in this function.
948   FuncInfo.MF->getFrameInfo().setHasPatchPoint();
949 
950   if (CLI.NumResultRegs)
951     updateValueMap(I, CLI.ResultReg, CLI.NumResultRegs);
952   return true;
953 }
954 
955 bool FastISel::selectXRayCustomEvent(const CallInst *I) {
956   const auto &Triple = TM.getTargetTriple();
957   if (Triple.getArch() != Triple::x86_64 || !Triple.isOSLinux())
958     return true; // don't do anything to this instruction.
959   SmallVector<MachineOperand, 8> Ops;
960   Ops.push_back(MachineOperand::CreateReg(getRegForValue(I->getArgOperand(0)),
961                                           /*isDef=*/false));
962   Ops.push_back(MachineOperand::CreateReg(getRegForValue(I->getArgOperand(1)),
963                                           /*isDef=*/false));
964   MachineInstrBuilder MIB =
965       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
966               TII.get(TargetOpcode::PATCHABLE_EVENT_CALL));
967   for (auto &MO : Ops)
968     MIB.add(MO);
969 
970   // Insert the Patchable Event Call instruction, that gets lowered properly.
971   return true;
972 }
973 
974 bool FastISel::selectXRayTypedEvent(const CallInst *I) {
975   const auto &Triple = TM.getTargetTriple();
976   if (Triple.getArch() != Triple::x86_64 || !Triple.isOSLinux())
977     return true; // don't do anything to this instruction.
978   SmallVector<MachineOperand, 8> Ops;
979   Ops.push_back(MachineOperand::CreateReg(getRegForValue(I->getArgOperand(0)),
980                                           /*isDef=*/false));
981   Ops.push_back(MachineOperand::CreateReg(getRegForValue(I->getArgOperand(1)),
982                                           /*isDef=*/false));
983   Ops.push_back(MachineOperand::CreateReg(getRegForValue(I->getArgOperand(2)),
984                                           /*isDef=*/false));
985   MachineInstrBuilder MIB =
986       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
987               TII.get(TargetOpcode::PATCHABLE_TYPED_EVENT_CALL));
988   for (auto &MO : Ops)
989     MIB.add(MO);
990 
991   // Insert the Patchable Typed Event Call instruction, that gets lowered properly.
992   return true;
993 }
994 
995 /// Returns an AttributeList representing the attributes applied to the return
996 /// value of the given call.
997 static AttributeList getReturnAttrs(FastISel::CallLoweringInfo &CLI) {
998   SmallVector<Attribute::AttrKind, 2> Attrs;
999   if (CLI.RetSExt)
1000     Attrs.push_back(Attribute::SExt);
1001   if (CLI.RetZExt)
1002     Attrs.push_back(Attribute::ZExt);
1003   if (CLI.IsInReg)
1004     Attrs.push_back(Attribute::InReg);
1005 
1006   return AttributeList::get(CLI.RetTy->getContext(), AttributeList::ReturnIndex,
1007                             Attrs);
1008 }
1009 
1010 bool FastISel::lowerCallTo(const CallInst *CI, const char *SymName,
1011                            unsigned NumArgs) {
1012   MCContext &Ctx = MF->getContext();
1013   SmallString<32> MangledName;
1014   Mangler::getNameWithPrefix(MangledName, SymName, DL);
1015   MCSymbol *Sym = Ctx.getOrCreateSymbol(MangledName);
1016   return lowerCallTo(CI, Sym, NumArgs);
1017 }
1018 
1019 bool FastISel::lowerCallTo(const CallInst *CI, MCSymbol *Symbol,
1020                            unsigned NumArgs) {
1021   FunctionType *FTy = CI->getFunctionType();
1022   Type *RetTy = CI->getType();
1023 
1024   ArgListTy Args;
1025   Args.reserve(NumArgs);
1026 
1027   // Populate the argument list.
1028   // Attributes for args start at offset 1, after the return attribute.
1029   for (unsigned ArgI = 0; ArgI != NumArgs; ++ArgI) {
1030     Value *V = CI->getOperand(ArgI);
1031 
1032     assert(!V->getType()->isEmptyTy() && "Empty type passed to intrinsic.");
1033 
1034     ArgListEntry Entry;
1035     Entry.Val = V;
1036     Entry.Ty = V->getType();
1037     Entry.setAttributes(CI, ArgI);
1038     Args.push_back(Entry);
1039   }
1040   TLI.markLibCallAttributes(MF, CI->getCallingConv(), Args);
1041 
1042   CallLoweringInfo CLI;
1043   CLI.setCallee(RetTy, FTy, Symbol, std::move(Args), *CI, NumArgs);
1044 
1045   return lowerCallTo(CLI);
1046 }
1047 
1048 bool FastISel::lowerCallTo(CallLoweringInfo &CLI) {
1049   // Handle the incoming return values from the call.
1050   CLI.clearIns();
1051   SmallVector<EVT, 4> RetTys;
1052   ComputeValueVTs(TLI, DL, CLI.RetTy, RetTys);
1053 
1054   SmallVector<ISD::OutputArg, 4> Outs;
1055   GetReturnInfo(CLI.CallConv, CLI.RetTy, getReturnAttrs(CLI), Outs, TLI, DL);
1056 
1057   bool CanLowerReturn = TLI.CanLowerReturn(
1058       CLI.CallConv, *FuncInfo.MF, CLI.IsVarArg, Outs, CLI.RetTy->getContext());
1059 
1060   // FIXME: sret demotion isn't supported yet - bail out.
1061   if (!CanLowerReturn)
1062     return false;
1063 
1064   for (unsigned I = 0, E = RetTys.size(); I != E; ++I) {
1065     EVT VT = RetTys[I];
1066     MVT RegisterVT = TLI.getRegisterType(CLI.RetTy->getContext(), VT);
1067     unsigned NumRegs = TLI.getNumRegisters(CLI.RetTy->getContext(), VT);
1068     for (unsigned i = 0; i != NumRegs; ++i) {
1069       ISD::InputArg MyFlags;
1070       MyFlags.VT = RegisterVT;
1071       MyFlags.ArgVT = VT;
1072       MyFlags.Used = CLI.IsReturnValueUsed;
1073       if (CLI.RetSExt)
1074         MyFlags.Flags.setSExt();
1075       if (CLI.RetZExt)
1076         MyFlags.Flags.setZExt();
1077       if (CLI.IsInReg)
1078         MyFlags.Flags.setInReg();
1079       CLI.Ins.push_back(MyFlags);
1080     }
1081   }
1082 
1083   // Handle all of the outgoing arguments.
1084   CLI.clearOuts();
1085   for (auto &Arg : CLI.getArgs()) {
1086     Type *FinalType = Arg.Ty;
1087     if (Arg.IsByVal)
1088       FinalType = cast<PointerType>(Arg.Ty)->getElementType();
1089     bool NeedsRegBlock = TLI.functionArgumentNeedsConsecutiveRegisters(
1090         FinalType, CLI.CallConv, CLI.IsVarArg);
1091 
1092     ISD::ArgFlagsTy Flags;
1093     if (Arg.IsZExt)
1094       Flags.setZExt();
1095     if (Arg.IsSExt)
1096       Flags.setSExt();
1097     if (Arg.IsInReg)
1098       Flags.setInReg();
1099     if (Arg.IsSRet)
1100       Flags.setSRet();
1101     if (Arg.IsSwiftSelf)
1102       Flags.setSwiftSelf();
1103     if (Arg.IsSwiftError)
1104       Flags.setSwiftError();
1105     if (Arg.IsCFGuardTarget)
1106       Flags.setCFGuardTarget();
1107     if (Arg.IsByVal)
1108       Flags.setByVal();
1109     if (Arg.IsInAlloca) {
1110       Flags.setInAlloca();
1111       // Set the byval flag for CCAssignFn callbacks that don't know about
1112       // inalloca. This way we can know how many bytes we should've allocated
1113       // and how many bytes a callee cleanup function will pop.  If we port
1114       // inalloca to more targets, we'll have to add custom inalloca handling in
1115       // the various CC lowering callbacks.
1116       Flags.setByVal();
1117     }
1118     if (Arg.IsPreallocated) {
1119       Flags.setPreallocated();
1120       // Set the byval flag for CCAssignFn callbacks that don't know about
1121       // preallocated. This way we can know how many bytes we should've
1122       // allocated and how many bytes a callee cleanup function will pop.  If we
1123       // port preallocated to more targets, we'll have to add custom
1124       // preallocated handling in the various CC lowering callbacks.
1125       Flags.setByVal();
1126     }
1127     if (Arg.IsByVal || Arg.IsInAlloca || Arg.IsPreallocated) {
1128       PointerType *Ty = cast<PointerType>(Arg.Ty);
1129       Type *ElementTy = Ty->getElementType();
1130       unsigned FrameSize =
1131           DL.getTypeAllocSize(Arg.ByValType ? Arg.ByValType : ElementTy);
1132 
1133       // For ByVal, alignment should come from FE. BE will guess if this info
1134       // is not there, but there are cases it cannot get right.
1135       MaybeAlign FrameAlign = Arg.Alignment;
1136       if (!FrameAlign)
1137         FrameAlign = Align(TLI.getByValTypeAlignment(ElementTy, DL));
1138       Flags.setByValSize(FrameSize);
1139       Flags.setByValAlign(*FrameAlign);
1140     }
1141     if (Arg.IsNest)
1142       Flags.setNest();
1143     if (NeedsRegBlock)
1144       Flags.setInConsecutiveRegs();
1145     Flags.setOrigAlign(DL.getABITypeAlign(Arg.Ty));
1146 
1147     CLI.OutVals.push_back(Arg.Val);
1148     CLI.OutFlags.push_back(Flags);
1149   }
1150 
1151   if (!fastLowerCall(CLI))
1152     return false;
1153 
1154   // Set all unused physreg defs as dead.
1155   assert(CLI.Call && "No call instruction specified.");
1156   CLI.Call->setPhysRegsDeadExcept(CLI.InRegs, TRI);
1157 
1158   if (CLI.NumResultRegs && CLI.CB)
1159     updateValueMap(CLI.CB, CLI.ResultReg, CLI.NumResultRegs);
1160 
1161   // Set labels for heapallocsite call.
1162   if (CLI.CB)
1163     if (MDNode *MD = CLI.CB->getMetadata("heapallocsite"))
1164       CLI.Call->setHeapAllocMarker(*MF, MD);
1165 
1166   return true;
1167 }
1168 
1169 bool FastISel::lowerCall(const CallInst *CI) {
1170   FunctionType *FuncTy = CI->getFunctionType();
1171   Type *RetTy = CI->getType();
1172 
1173   ArgListTy Args;
1174   ArgListEntry Entry;
1175   Args.reserve(CI->arg_size());
1176 
1177   for (auto i = CI->arg_begin(), e = CI->arg_end(); i != e; ++i) {
1178     Value *V = *i;
1179 
1180     // Skip empty types
1181     if (V->getType()->isEmptyTy())
1182       continue;
1183 
1184     Entry.Val = V;
1185     Entry.Ty = V->getType();
1186 
1187     // Skip the first return-type Attribute to get to params.
1188     Entry.setAttributes(CI, i - CI->arg_begin());
1189     Args.push_back(Entry);
1190   }
1191 
1192   // Check if target-independent constraints permit a tail call here.
1193   // Target-dependent constraints are checked within fastLowerCall.
1194   bool IsTailCall = CI->isTailCall();
1195   if (IsTailCall && !isInTailCallPosition(*CI, TM))
1196     IsTailCall = false;
1197   if (IsTailCall && MF->getFunction()
1198                             .getFnAttribute("disable-tail-calls")
1199                             .getValueAsString() == "true")
1200     IsTailCall = false;
1201 
1202   CallLoweringInfo CLI;
1203   CLI.setCallee(RetTy, FuncTy, CI->getCalledOperand(), std::move(Args), *CI)
1204       .setTailCall(IsTailCall);
1205 
1206   return lowerCallTo(CLI);
1207 }
1208 
1209 bool FastISel::selectCall(const User *I) {
1210   const CallInst *Call = cast<CallInst>(I);
1211 
1212   // Handle simple inline asms.
1213   if (const InlineAsm *IA = dyn_cast<InlineAsm>(Call->getCalledOperand())) {
1214     // Don't attempt to handle constraints.
1215     if (!IA->getConstraintString().empty())
1216       return false;
1217 
1218     unsigned ExtraInfo = 0;
1219     if (IA->hasSideEffects())
1220       ExtraInfo |= InlineAsm::Extra_HasSideEffects;
1221     if (IA->isAlignStack())
1222       ExtraInfo |= InlineAsm::Extra_IsAlignStack;
1223     if (Call->isConvergent())
1224       ExtraInfo |= InlineAsm::Extra_IsConvergent;
1225     ExtraInfo |= IA->getDialect() * InlineAsm::Extra_AsmDialect;
1226 
1227     MachineInstrBuilder MIB = BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1228                                       TII.get(TargetOpcode::INLINEASM));
1229     MIB.addExternalSymbol(IA->getAsmString().c_str());
1230     MIB.addImm(ExtraInfo);
1231 
1232     const MDNode *SrcLoc = Call->getMetadata("srcloc");
1233     if (SrcLoc)
1234       MIB.addMetadata(SrcLoc);
1235 
1236     return true;
1237   }
1238 
1239   // Handle intrinsic function calls.
1240   if (const auto *II = dyn_cast<IntrinsicInst>(Call))
1241     return selectIntrinsicCall(II);
1242 
1243   return lowerCall(Call);
1244 }
1245 
1246 bool FastISel::selectIntrinsicCall(const IntrinsicInst *II) {
1247   switch (II->getIntrinsicID()) {
1248   default:
1249     break;
1250   // At -O0 we don't care about the lifetime intrinsics.
1251   case Intrinsic::lifetime_start:
1252   case Intrinsic::lifetime_end:
1253   // The donothing intrinsic does, well, nothing.
1254   case Intrinsic::donothing:
1255   // Neither does the sideeffect intrinsic.
1256   case Intrinsic::sideeffect:
1257   // Neither does the assume intrinsic; it's also OK not to codegen its operand.
1258   case Intrinsic::assume:
1259   // Neither does the llvm.experimental.noalias.scope.decl intrinsic
1260   case Intrinsic::experimental_noalias_scope_decl:
1261     return true;
1262   case Intrinsic::dbg_declare: {
1263     const DbgDeclareInst *DI = cast<DbgDeclareInst>(II);
1264     assert(DI->getVariable() && "Missing variable");
1265     if (!FuncInfo.MF->getMMI().hasDebugInfo()) {
1266       LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI
1267                         << " (!hasDebugInfo)\n");
1268       return true;
1269     }
1270 
1271     const Value *Address = DI->getAddress();
1272     if (!Address || isa<UndefValue>(Address)) {
1273       LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI
1274                         << " (bad/undef address)\n");
1275       return true;
1276     }
1277 
1278     // Byval arguments with frame indices were already handled after argument
1279     // lowering and before isel.
1280     const auto *Arg =
1281         dyn_cast<Argument>(Address->stripInBoundsConstantOffsets());
1282     if (Arg && FuncInfo.getArgumentFrameIndex(Arg) != INT_MAX)
1283       return true;
1284 
1285     Optional<MachineOperand> Op;
1286     if (Register Reg = lookUpRegForValue(Address))
1287       Op = MachineOperand::CreateReg(Reg, false);
1288 
1289     // If we have a VLA that has a "use" in a metadata node that's then used
1290     // here but it has no other uses, then we have a problem. E.g.,
1291     //
1292     //   int foo (const int *x) {
1293     //     char a[*x];
1294     //     return 0;
1295     //   }
1296     //
1297     // If we assign 'a' a vreg and fast isel later on has to use the selection
1298     // DAG isel, it will want to copy the value to the vreg. However, there are
1299     // no uses, which goes counter to what selection DAG isel expects.
1300     if (!Op && !Address->use_empty() && isa<Instruction>(Address) &&
1301         (!isa<AllocaInst>(Address) ||
1302          !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(Address))))
1303       Op = MachineOperand::CreateReg(FuncInfo.InitializeRegForValue(Address),
1304                                      false);
1305 
1306     if (Op) {
1307       assert(DI->getVariable()->isValidLocationForIntrinsic(DbgLoc) &&
1308              "Expected inlined-at fields to agree");
1309       // A dbg.declare describes the address of a source variable, so lower it
1310       // into an indirect DBG_VALUE.
1311       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1312               TII.get(TargetOpcode::DBG_VALUE), /*IsIndirect*/ true,
1313               *Op, DI->getVariable(), DI->getExpression());
1314     } else {
1315       // We can't yet handle anything else here because it would require
1316       // generating code, thus altering codegen because of debug info.
1317       LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI
1318                         << " (no materialized reg for address)\n");
1319     }
1320     return true;
1321   }
1322   case Intrinsic::dbg_value: {
1323     // This form of DBG_VALUE is target-independent.
1324     const DbgValueInst *DI = cast<DbgValueInst>(II);
1325     const MCInstrDesc &II = TII.get(TargetOpcode::DBG_VALUE);
1326     const Value *V = DI->getValue();
1327     assert(DI->getVariable()->isValidLocationForIntrinsic(DbgLoc) &&
1328            "Expected inlined-at fields to agree");
1329     if (!V || isa<UndefValue>(V)) {
1330       // Currently the optimizer can produce this; insert an undef to
1331       // help debugging.
1332       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, false, 0U,
1333               DI->getVariable(), DI->getExpression());
1334     } else if (const auto *CI = dyn_cast<ConstantInt>(V)) {
1335       if (CI->getBitWidth() > 64)
1336         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1337             .addCImm(CI)
1338             .addImm(0U)
1339             .addMetadata(DI->getVariable())
1340             .addMetadata(DI->getExpression());
1341       else
1342         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1343             .addImm(CI->getZExtValue())
1344             .addImm(0U)
1345             .addMetadata(DI->getVariable())
1346             .addMetadata(DI->getExpression());
1347     } else if (const auto *CF = dyn_cast<ConstantFP>(V)) {
1348       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1349           .addFPImm(CF)
1350           .addImm(0U)
1351           .addMetadata(DI->getVariable())
1352           .addMetadata(DI->getExpression());
1353     } else if (Register Reg = lookUpRegForValue(V)) {
1354       // FIXME: This does not handle register-indirect values at offset 0.
1355       bool IsIndirect = false;
1356       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, IsIndirect, Reg,
1357               DI->getVariable(), DI->getExpression());
1358     } else {
1359       // We don't know how to handle other cases, so we drop.
1360       LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
1361     }
1362     return true;
1363   }
1364   case Intrinsic::dbg_label: {
1365     const DbgLabelInst *DI = cast<DbgLabelInst>(II);
1366     assert(DI->getLabel() && "Missing label");
1367     if (!FuncInfo.MF->getMMI().hasDebugInfo()) {
1368       LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
1369       return true;
1370     }
1371 
1372     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1373             TII.get(TargetOpcode::DBG_LABEL)).addMetadata(DI->getLabel());
1374     return true;
1375   }
1376   case Intrinsic::objectsize:
1377     llvm_unreachable("llvm.objectsize.* should have been lowered already");
1378 
1379   case Intrinsic::is_constant:
1380     llvm_unreachable("llvm.is.constant.* should have been lowered already");
1381 
1382   case Intrinsic::launder_invariant_group:
1383   case Intrinsic::strip_invariant_group:
1384   case Intrinsic::expect: {
1385     Register ResultReg = getRegForValue(II->getArgOperand(0));
1386     if (!ResultReg)
1387       return false;
1388     updateValueMap(II, ResultReg);
1389     return true;
1390   }
1391   case Intrinsic::experimental_stackmap:
1392     return selectStackmap(II);
1393   case Intrinsic::experimental_patchpoint_void:
1394   case Intrinsic::experimental_patchpoint_i64:
1395     return selectPatchpoint(II);
1396 
1397   case Intrinsic::xray_customevent:
1398     return selectXRayCustomEvent(II);
1399   case Intrinsic::xray_typedevent:
1400     return selectXRayTypedEvent(II);
1401   }
1402 
1403   return fastLowerIntrinsicCall(II);
1404 }
1405 
1406 bool FastISel::selectCast(const User *I, unsigned Opcode) {
1407   EVT SrcVT = TLI.getValueType(DL, I->getOperand(0)->getType());
1408   EVT DstVT = TLI.getValueType(DL, I->getType());
1409 
1410   if (SrcVT == MVT::Other || !SrcVT.isSimple() || DstVT == MVT::Other ||
1411       !DstVT.isSimple())
1412     // Unhandled type. Halt "fast" selection and bail.
1413     return false;
1414 
1415   // Check if the destination type is legal.
1416   if (!TLI.isTypeLegal(DstVT))
1417     return false;
1418 
1419   // Check if the source operand is legal.
1420   if (!TLI.isTypeLegal(SrcVT))
1421     return false;
1422 
1423   Register InputReg = getRegForValue(I->getOperand(0));
1424   if (!InputReg)
1425     // Unhandled operand.  Halt "fast" selection and bail.
1426     return false;
1427 
1428   bool InputRegIsKill = hasTrivialKill(I->getOperand(0));
1429 
1430   Register ResultReg = fastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(),
1431                                   Opcode, InputReg, InputRegIsKill);
1432   if (!ResultReg)
1433     return false;
1434 
1435   updateValueMap(I, ResultReg);
1436   return true;
1437 }
1438 
1439 bool FastISel::selectBitCast(const User *I) {
1440   // If the bitcast doesn't change the type, just use the operand value.
1441   if (I->getType() == I->getOperand(0)->getType()) {
1442     Register Reg = getRegForValue(I->getOperand(0));
1443     if (!Reg)
1444       return false;
1445     updateValueMap(I, Reg);
1446     return true;
1447   }
1448 
1449   // Bitcasts of other values become reg-reg copies or BITCAST operators.
1450   EVT SrcEVT = TLI.getValueType(DL, I->getOperand(0)->getType());
1451   EVT DstEVT = TLI.getValueType(DL, I->getType());
1452   if (SrcEVT == MVT::Other || DstEVT == MVT::Other ||
1453       !TLI.isTypeLegal(SrcEVT) || !TLI.isTypeLegal(DstEVT))
1454     // Unhandled type. Halt "fast" selection and bail.
1455     return false;
1456 
1457   MVT SrcVT = SrcEVT.getSimpleVT();
1458   MVT DstVT = DstEVT.getSimpleVT();
1459   Register Op0 = getRegForValue(I->getOperand(0));
1460   if (!Op0) // Unhandled operand. Halt "fast" selection and bail.
1461     return false;
1462   bool Op0IsKill = hasTrivialKill(I->getOperand(0));
1463 
1464   // First, try to perform the bitcast by inserting a reg-reg copy.
1465   Register ResultReg;
1466   if (SrcVT == DstVT) {
1467     const TargetRegisterClass *SrcClass = TLI.getRegClassFor(SrcVT);
1468     const TargetRegisterClass *DstClass = TLI.getRegClassFor(DstVT);
1469     // Don't attempt a cross-class copy. It will likely fail.
1470     if (SrcClass == DstClass) {
1471       ResultReg = createResultReg(DstClass);
1472       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1473               TII.get(TargetOpcode::COPY), ResultReg).addReg(Op0);
1474     }
1475   }
1476 
1477   // If the reg-reg copy failed, select a BITCAST opcode.
1478   if (!ResultReg)
1479     ResultReg = fastEmit_r(SrcVT, DstVT, ISD::BITCAST, Op0, Op0IsKill);
1480 
1481   if (!ResultReg)
1482     return false;
1483 
1484   updateValueMap(I, ResultReg);
1485   return true;
1486 }
1487 
1488 bool FastISel::selectFreeze(const User *I) {
1489   Register Reg = getRegForValue(I->getOperand(0));
1490   if (!Reg)
1491     // Unhandled operand.
1492     return false;
1493 
1494   EVT ETy = TLI.getValueType(DL, I->getOperand(0)->getType());
1495   if (ETy == MVT::Other || !TLI.isTypeLegal(ETy))
1496     // Unhandled type, bail out.
1497     return false;
1498 
1499   MVT Ty = ETy.getSimpleVT();
1500   const TargetRegisterClass *TyRegClass = TLI.getRegClassFor(Ty);
1501   Register ResultReg = createResultReg(TyRegClass);
1502   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1503           TII.get(TargetOpcode::COPY), ResultReg).addReg(Reg);
1504 
1505   updateValueMap(I, ResultReg);
1506   return true;
1507 }
1508 
1509 // Remove local value instructions starting from the instruction after
1510 // SavedLastLocalValue to the current function insert point.
1511 void FastISel::removeDeadLocalValueCode(MachineInstr *SavedLastLocalValue)
1512 {
1513   MachineInstr *CurLastLocalValue = getLastLocalValue();
1514   if (CurLastLocalValue != SavedLastLocalValue) {
1515     // Find the first local value instruction to be deleted.
1516     // This is the instruction after SavedLastLocalValue if it is non-NULL.
1517     // Otherwise it's the first instruction in the block.
1518     MachineBasicBlock::iterator FirstDeadInst(SavedLastLocalValue);
1519     if (SavedLastLocalValue)
1520       ++FirstDeadInst;
1521     else
1522       FirstDeadInst = FuncInfo.MBB->getFirstNonPHI();
1523     setLastLocalValue(SavedLastLocalValue);
1524     removeDeadCode(FirstDeadInst, FuncInfo.InsertPt);
1525   }
1526 }
1527 
1528 bool FastISel::selectInstruction(const Instruction *I) {
1529   // Flush the local value map before starting each instruction.
1530   // This improves locality and debugging, and can reduce spills.
1531   // Reuse of values across IR instructions is relatively uncommon.
1532   flushLocalValueMap();
1533 
1534   MachineInstr *SavedLastLocalValue = getLastLocalValue();
1535   // Just before the terminator instruction, insert instructions to
1536   // feed PHI nodes in successor blocks.
1537   if (I->isTerminator()) {
1538     if (!handlePHINodesInSuccessorBlocks(I->getParent())) {
1539       // PHI node handling may have generated local value instructions,
1540       // even though it failed to handle all PHI nodes.
1541       // We remove these instructions because SelectionDAGISel will generate
1542       // them again.
1543       removeDeadLocalValueCode(SavedLastLocalValue);
1544       return false;
1545     }
1546   }
1547 
1548   // FastISel does not handle any operand bundles except OB_funclet.
1549   if (auto *Call = dyn_cast<CallBase>(I))
1550     for (unsigned i = 0, e = Call->getNumOperandBundles(); i != e; ++i)
1551       if (Call->getOperandBundleAt(i).getTagID() != LLVMContext::OB_funclet)
1552         return false;
1553 
1554   DbgLoc = I->getDebugLoc();
1555 
1556   SavedInsertPt = FuncInfo.InsertPt;
1557 
1558   if (const auto *Call = dyn_cast<CallInst>(I)) {
1559     const Function *F = Call->getCalledFunction();
1560     LibFunc Func;
1561 
1562     // As a special case, don't handle calls to builtin library functions that
1563     // may be translated directly to target instructions.
1564     if (F && !F->hasLocalLinkage() && F->hasName() &&
1565         LibInfo->getLibFunc(F->getName(), Func) &&
1566         LibInfo->hasOptimizedCodeGen(Func))
1567       return false;
1568 
1569     // Don't handle Intrinsic::trap if a trap function is specified.
1570     if (F && F->getIntrinsicID() == Intrinsic::trap &&
1571         Call->hasFnAttr("trap-func-name"))
1572       return false;
1573   }
1574 
1575   // First, try doing target-independent selection.
1576   if (!SkipTargetIndependentISel) {
1577     if (selectOperator(I, I->getOpcode())) {
1578       ++NumFastIselSuccessIndependent;
1579       DbgLoc = DebugLoc();
1580       return true;
1581     }
1582     // Remove dead code.
1583     recomputeInsertPt();
1584     if (SavedInsertPt != FuncInfo.InsertPt)
1585       removeDeadCode(FuncInfo.InsertPt, SavedInsertPt);
1586     SavedInsertPt = FuncInfo.InsertPt;
1587   }
1588   // Next, try calling the target to attempt to handle the instruction.
1589   if (fastSelectInstruction(I)) {
1590     ++NumFastIselSuccessTarget;
1591     DbgLoc = DebugLoc();
1592     return true;
1593   }
1594   // Remove dead code.
1595   recomputeInsertPt();
1596   if (SavedInsertPt != FuncInfo.InsertPt)
1597     removeDeadCode(FuncInfo.InsertPt, SavedInsertPt);
1598 
1599   DbgLoc = DebugLoc();
1600   // Undo phi node updates, because they will be added again by SelectionDAG.
1601   if (I->isTerminator()) {
1602     // PHI node handling may have generated local value instructions.
1603     // We remove them because SelectionDAGISel will generate them again.
1604     removeDeadLocalValueCode(SavedLastLocalValue);
1605     FuncInfo.PHINodesToUpdate.resize(FuncInfo.OrigNumPHINodesToUpdate);
1606   }
1607   return false;
1608 }
1609 
1610 /// Emit an unconditional branch to the given block, unless it is the immediate
1611 /// (fall-through) successor, and update the CFG.
1612 void FastISel::fastEmitBranch(MachineBasicBlock *MSucc,
1613                               const DebugLoc &DbgLoc) {
1614   if (FuncInfo.MBB->getBasicBlock()->sizeWithoutDebug() > 1 &&
1615       FuncInfo.MBB->isLayoutSuccessor(MSucc)) {
1616     // For more accurate line information if this is the only non-debug
1617     // instruction in the block then emit it, otherwise we have the
1618     // unconditional fall-through case, which needs no instructions.
1619   } else {
1620     // The unconditional branch case.
1621     TII.insertBranch(*FuncInfo.MBB, MSucc, nullptr,
1622                      SmallVector<MachineOperand, 0>(), DbgLoc);
1623   }
1624   if (FuncInfo.BPI) {
1625     auto BranchProbability = FuncInfo.BPI->getEdgeProbability(
1626         FuncInfo.MBB->getBasicBlock(), MSucc->getBasicBlock());
1627     FuncInfo.MBB->addSuccessor(MSucc, BranchProbability);
1628   } else
1629     FuncInfo.MBB->addSuccessorWithoutProb(MSucc);
1630 }
1631 
1632 void FastISel::finishCondBranch(const BasicBlock *BranchBB,
1633                                 MachineBasicBlock *TrueMBB,
1634                                 MachineBasicBlock *FalseMBB) {
1635   // Add TrueMBB as successor unless it is equal to the FalseMBB: This can
1636   // happen in degenerate IR and MachineIR forbids to have a block twice in the
1637   // successor/predecessor lists.
1638   if (TrueMBB != FalseMBB) {
1639     if (FuncInfo.BPI) {
1640       auto BranchProbability =
1641           FuncInfo.BPI->getEdgeProbability(BranchBB, TrueMBB->getBasicBlock());
1642       FuncInfo.MBB->addSuccessor(TrueMBB, BranchProbability);
1643     } else
1644       FuncInfo.MBB->addSuccessorWithoutProb(TrueMBB);
1645   }
1646 
1647   fastEmitBranch(FalseMBB, DbgLoc);
1648 }
1649 
1650 /// Emit an FNeg operation.
1651 bool FastISel::selectFNeg(const User *I, const Value *In) {
1652   Register OpReg = getRegForValue(In);
1653   if (!OpReg)
1654     return false;
1655   bool OpRegIsKill = hasTrivialKill(In);
1656 
1657   // If the target has ISD::FNEG, use it.
1658   EVT VT = TLI.getValueType(DL, I->getType());
1659   Register ResultReg = fastEmit_r(VT.getSimpleVT(), VT.getSimpleVT(), ISD::FNEG,
1660                                   OpReg, OpRegIsKill);
1661   if (ResultReg) {
1662     updateValueMap(I, ResultReg);
1663     return true;
1664   }
1665 
1666   // Bitcast the value to integer, twiddle the sign bit with xor,
1667   // and then bitcast it back to floating-point.
1668   if (VT.getSizeInBits() > 64)
1669     return false;
1670   EVT IntVT = EVT::getIntegerVT(I->getContext(), VT.getSizeInBits());
1671   if (!TLI.isTypeLegal(IntVT))
1672     return false;
1673 
1674   Register IntReg = fastEmit_r(VT.getSimpleVT(), IntVT.getSimpleVT(),
1675                                ISD::BITCAST, OpReg, OpRegIsKill);
1676   if (!IntReg)
1677     return false;
1678 
1679   Register IntResultReg = fastEmit_ri_(
1680       IntVT.getSimpleVT(), ISD::XOR, IntReg, /*Op0IsKill=*/true,
1681       UINT64_C(1) << (VT.getSizeInBits() - 1), IntVT.getSimpleVT());
1682   if (!IntResultReg)
1683     return false;
1684 
1685   ResultReg = fastEmit_r(IntVT.getSimpleVT(), VT.getSimpleVT(), ISD::BITCAST,
1686                          IntResultReg, /*Op0IsKill=*/true);
1687   if (!ResultReg)
1688     return false;
1689 
1690   updateValueMap(I, ResultReg);
1691   return true;
1692 }
1693 
1694 bool FastISel::selectExtractValue(const User *U) {
1695   const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(U);
1696   if (!EVI)
1697     return false;
1698 
1699   // Make sure we only try to handle extracts with a legal result.  But also
1700   // allow i1 because it's easy.
1701   EVT RealVT = TLI.getValueType(DL, EVI->getType(), /*AllowUnknown=*/true);
1702   if (!RealVT.isSimple())
1703     return false;
1704   MVT VT = RealVT.getSimpleVT();
1705   if (!TLI.isTypeLegal(VT) && VT != MVT::i1)
1706     return false;
1707 
1708   const Value *Op0 = EVI->getOperand(0);
1709   Type *AggTy = Op0->getType();
1710 
1711   // Get the base result register.
1712   unsigned ResultReg;
1713   DenseMap<const Value *, Register>::iterator I = FuncInfo.ValueMap.find(Op0);
1714   if (I != FuncInfo.ValueMap.end())
1715     ResultReg = I->second;
1716   else if (isa<Instruction>(Op0))
1717     ResultReg = FuncInfo.InitializeRegForValue(Op0);
1718   else
1719     return false; // fast-isel can't handle aggregate constants at the moment
1720 
1721   // Get the actual result register, which is an offset from the base register.
1722   unsigned VTIndex = ComputeLinearIndex(AggTy, EVI->getIndices());
1723 
1724   SmallVector<EVT, 4> AggValueVTs;
1725   ComputeValueVTs(TLI, DL, AggTy, AggValueVTs);
1726 
1727   for (unsigned i = 0; i < VTIndex; i++)
1728     ResultReg += TLI.getNumRegisters(FuncInfo.Fn->getContext(), AggValueVTs[i]);
1729 
1730   updateValueMap(EVI, ResultReg);
1731   return true;
1732 }
1733 
1734 bool FastISel::selectOperator(const User *I, unsigned Opcode) {
1735   switch (Opcode) {
1736   case Instruction::Add:
1737     return selectBinaryOp(I, ISD::ADD);
1738   case Instruction::FAdd:
1739     return selectBinaryOp(I, ISD::FADD);
1740   case Instruction::Sub:
1741     return selectBinaryOp(I, ISD::SUB);
1742   case Instruction::FSub:
1743     return selectBinaryOp(I, ISD::FSUB);
1744   case Instruction::Mul:
1745     return selectBinaryOp(I, ISD::MUL);
1746   case Instruction::FMul:
1747     return selectBinaryOp(I, ISD::FMUL);
1748   case Instruction::SDiv:
1749     return selectBinaryOp(I, ISD::SDIV);
1750   case Instruction::UDiv:
1751     return selectBinaryOp(I, ISD::UDIV);
1752   case Instruction::FDiv:
1753     return selectBinaryOp(I, ISD::FDIV);
1754   case Instruction::SRem:
1755     return selectBinaryOp(I, ISD::SREM);
1756   case Instruction::URem:
1757     return selectBinaryOp(I, ISD::UREM);
1758   case Instruction::FRem:
1759     return selectBinaryOp(I, ISD::FREM);
1760   case Instruction::Shl:
1761     return selectBinaryOp(I, ISD::SHL);
1762   case Instruction::LShr:
1763     return selectBinaryOp(I, ISD::SRL);
1764   case Instruction::AShr:
1765     return selectBinaryOp(I, ISD::SRA);
1766   case Instruction::And:
1767     return selectBinaryOp(I, ISD::AND);
1768   case Instruction::Or:
1769     return selectBinaryOp(I, ISD::OR);
1770   case Instruction::Xor:
1771     return selectBinaryOp(I, ISD::XOR);
1772 
1773   case Instruction::FNeg:
1774     return selectFNeg(I, I->getOperand(0));
1775 
1776   case Instruction::GetElementPtr:
1777     return selectGetElementPtr(I);
1778 
1779   case Instruction::Br: {
1780     const BranchInst *BI = cast<BranchInst>(I);
1781 
1782     if (BI->isUnconditional()) {
1783       const BasicBlock *LLVMSucc = BI->getSuccessor(0);
1784       MachineBasicBlock *MSucc = FuncInfo.MBBMap[LLVMSucc];
1785       fastEmitBranch(MSucc, BI->getDebugLoc());
1786       return true;
1787     }
1788 
1789     // Conditional branches are not handed yet.
1790     // Halt "fast" selection and bail.
1791     return false;
1792   }
1793 
1794   case Instruction::Unreachable:
1795     if (TM.Options.TrapUnreachable)
1796       return fastEmit_(MVT::Other, MVT::Other, ISD::TRAP) != 0;
1797     else
1798       return true;
1799 
1800   case Instruction::Alloca:
1801     // FunctionLowering has the static-sized case covered.
1802     if (FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(I)))
1803       return true;
1804 
1805     // Dynamic-sized alloca is not handled yet.
1806     return false;
1807 
1808   case Instruction::Call:
1809     // On AIX, call lowering uses the DAG-ISEL path currently so that the
1810     // callee of the direct function call instruction will be mapped to the
1811     // symbol for the function's entry point, which is distinct from the
1812     // function descriptor symbol. The latter is the symbol whose XCOFF symbol
1813     // name is the C-linkage name of the source level function.
1814     if (TM.getTargetTriple().isOSAIX())
1815       return false;
1816     return selectCall(I);
1817 
1818   case Instruction::BitCast:
1819     return selectBitCast(I);
1820 
1821   case Instruction::FPToSI:
1822     return selectCast(I, ISD::FP_TO_SINT);
1823   case Instruction::ZExt:
1824     return selectCast(I, ISD::ZERO_EXTEND);
1825   case Instruction::SExt:
1826     return selectCast(I, ISD::SIGN_EXTEND);
1827   case Instruction::Trunc:
1828     return selectCast(I, ISD::TRUNCATE);
1829   case Instruction::SIToFP:
1830     return selectCast(I, ISD::SINT_TO_FP);
1831 
1832   case Instruction::IntToPtr: // Deliberate fall-through.
1833   case Instruction::PtrToInt: {
1834     EVT SrcVT = TLI.getValueType(DL, I->getOperand(0)->getType());
1835     EVT DstVT = TLI.getValueType(DL, I->getType());
1836     if (DstVT.bitsGT(SrcVT))
1837       return selectCast(I, ISD::ZERO_EXTEND);
1838     if (DstVT.bitsLT(SrcVT))
1839       return selectCast(I, ISD::TRUNCATE);
1840     Register Reg = getRegForValue(I->getOperand(0));
1841     if (!Reg)
1842       return false;
1843     updateValueMap(I, Reg);
1844     return true;
1845   }
1846 
1847   case Instruction::ExtractValue:
1848     return selectExtractValue(I);
1849 
1850   case Instruction::Freeze:
1851     return selectFreeze(I);
1852 
1853   case Instruction::PHI:
1854     llvm_unreachable("FastISel shouldn't visit PHI nodes!");
1855 
1856   default:
1857     // Unhandled instruction. Halt "fast" selection and bail.
1858     return false;
1859   }
1860 }
1861 
1862 FastISel::FastISel(FunctionLoweringInfo &FuncInfo,
1863                    const TargetLibraryInfo *LibInfo,
1864                    bool SkipTargetIndependentISel)
1865     : FuncInfo(FuncInfo), MF(FuncInfo.MF), MRI(FuncInfo.MF->getRegInfo()),
1866       MFI(FuncInfo.MF->getFrameInfo()), MCP(*FuncInfo.MF->getConstantPool()),
1867       TM(FuncInfo.MF->getTarget()), DL(MF->getDataLayout()),
1868       TII(*MF->getSubtarget().getInstrInfo()),
1869       TLI(*MF->getSubtarget().getTargetLowering()),
1870       TRI(*MF->getSubtarget().getRegisterInfo()), LibInfo(LibInfo),
1871       SkipTargetIndependentISel(SkipTargetIndependentISel),
1872       LastLocalValue(nullptr), EmitStartPt(nullptr) {}
1873 
1874 FastISel::~FastISel() = default;
1875 
1876 bool FastISel::fastLowerArguments() { return false; }
1877 
1878 bool FastISel::fastLowerCall(CallLoweringInfo & /*CLI*/) { return false; }
1879 
1880 bool FastISel::fastLowerIntrinsicCall(const IntrinsicInst * /*II*/) {
1881   return false;
1882 }
1883 
1884 unsigned FastISel::fastEmit_(MVT, MVT, unsigned) { return 0; }
1885 
1886 unsigned FastISel::fastEmit_r(MVT, MVT, unsigned, unsigned /*Op0*/,
1887                               bool /*Op0IsKill*/) {
1888   return 0;
1889 }
1890 
1891 unsigned FastISel::fastEmit_rr(MVT, MVT, unsigned, unsigned /*Op0*/,
1892                                bool /*Op0IsKill*/, unsigned /*Op1*/,
1893                                bool /*Op1IsKill*/) {
1894   return 0;
1895 }
1896 
1897 unsigned FastISel::fastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) {
1898   return 0;
1899 }
1900 
1901 unsigned FastISel::fastEmit_f(MVT, MVT, unsigned,
1902                               const ConstantFP * /*FPImm*/) {
1903   return 0;
1904 }
1905 
1906 unsigned FastISel::fastEmit_ri(MVT, MVT, unsigned, unsigned /*Op0*/,
1907                                bool /*Op0IsKill*/, uint64_t /*Imm*/) {
1908   return 0;
1909 }
1910 
1911 /// This method is a wrapper of fastEmit_ri. It first tries to emit an
1912 /// instruction with an immediate operand using fastEmit_ri.
1913 /// If that fails, it materializes the immediate into a register and try
1914 /// fastEmit_rr instead.
1915 Register FastISel::fastEmit_ri_(MVT VT, unsigned Opcode, unsigned Op0,
1916                                 bool Op0IsKill, uint64_t Imm, MVT ImmType) {
1917   // If this is a multiply by a power of two, emit this as a shift left.
1918   if (Opcode == ISD::MUL && isPowerOf2_64(Imm)) {
1919     Opcode = ISD::SHL;
1920     Imm = Log2_64(Imm);
1921   } else if (Opcode == ISD::UDIV && isPowerOf2_64(Imm)) {
1922     // div x, 8 -> srl x, 3
1923     Opcode = ISD::SRL;
1924     Imm = Log2_64(Imm);
1925   }
1926 
1927   // Horrible hack (to be removed), check to make sure shift amounts are
1928   // in-range.
1929   if ((Opcode == ISD::SHL || Opcode == ISD::SRA || Opcode == ISD::SRL) &&
1930       Imm >= VT.getSizeInBits())
1931     return 0;
1932 
1933   // First check if immediate type is legal. If not, we can't use the ri form.
1934   Register ResultReg = fastEmit_ri(VT, VT, Opcode, Op0, Op0IsKill, Imm);
1935   if (ResultReg)
1936     return ResultReg;
1937   Register MaterialReg = fastEmit_i(ImmType, ImmType, ISD::Constant, Imm);
1938   bool IsImmKill = true;
1939   if (!MaterialReg) {
1940     // This is a bit ugly/slow, but failing here means falling out of
1941     // fast-isel, which would be very slow.
1942     IntegerType *ITy =
1943         IntegerType::get(FuncInfo.Fn->getContext(), VT.getSizeInBits());
1944     MaterialReg = getRegForValue(ConstantInt::get(ITy, Imm));
1945     if (!MaterialReg)
1946       return 0;
1947     // FIXME: If the materialized register here has no uses yet then this
1948     // will be the first use and we should be able to mark it as killed.
1949     // However, the local value area for materialising constant expressions
1950     // grows down, not up, which means that any constant expressions we generate
1951     // later which also use 'Imm' could be after this instruction and therefore
1952     // after this kill.
1953     IsImmKill = false;
1954   }
1955   return fastEmit_rr(VT, VT, Opcode, Op0, Op0IsKill, MaterialReg, IsImmKill);
1956 }
1957 
1958 Register FastISel::createResultReg(const TargetRegisterClass *RC) {
1959   return MRI.createVirtualRegister(RC);
1960 }
1961 
1962 Register FastISel::constrainOperandRegClass(const MCInstrDesc &II, Register Op,
1963                                             unsigned OpNum) {
1964   if (Op.isVirtual()) {
1965     const TargetRegisterClass *RegClass =
1966         TII.getRegClass(II, OpNum, &TRI, *FuncInfo.MF);
1967     if (!MRI.constrainRegClass(Op, RegClass)) {
1968       // If it's not legal to COPY between the register classes, something
1969       // has gone very wrong before we got here.
1970       Register NewOp = createResultReg(RegClass);
1971       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1972               TII.get(TargetOpcode::COPY), NewOp).addReg(Op);
1973       return NewOp;
1974     }
1975   }
1976   return Op;
1977 }
1978 
1979 Register FastISel::fastEmitInst_(unsigned MachineInstOpcode,
1980                                  const TargetRegisterClass *RC) {
1981   Register ResultReg = createResultReg(RC);
1982   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1983 
1984   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg);
1985   return ResultReg;
1986 }
1987 
1988 Register FastISel::fastEmitInst_r(unsigned MachineInstOpcode,
1989                                   const TargetRegisterClass *RC, unsigned Op0,
1990                                   bool Op0IsKill) {
1991   const MCInstrDesc &II = TII.get(MachineInstOpcode);
1992 
1993   Register ResultReg = createResultReg(RC);
1994   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
1995 
1996   if (II.getNumDefs() >= 1)
1997     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
1998         .addReg(Op0, getKillRegState(Op0IsKill));
1999   else {
2000     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
2001         .addReg(Op0, getKillRegState(Op0IsKill));
2002     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2003             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2004   }
2005 
2006   return ResultReg;
2007 }
2008 
2009 Register FastISel::fastEmitInst_rr(unsigned MachineInstOpcode,
2010                                    const TargetRegisterClass *RC, unsigned Op0,
2011                                    bool Op0IsKill, unsigned Op1,
2012                                    bool Op1IsKill) {
2013   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2014 
2015   Register ResultReg = createResultReg(RC);
2016   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
2017   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
2018 
2019   if (II.getNumDefs() >= 1)
2020     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
2021         .addReg(Op0, getKillRegState(Op0IsKill))
2022         .addReg(Op1, getKillRegState(Op1IsKill));
2023   else {
2024     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
2025         .addReg(Op0, getKillRegState(Op0IsKill))
2026         .addReg(Op1, getKillRegState(Op1IsKill));
2027     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2028             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2029   }
2030   return ResultReg;
2031 }
2032 
2033 Register FastISel::fastEmitInst_rrr(unsigned MachineInstOpcode,
2034                                     const TargetRegisterClass *RC, unsigned Op0,
2035                                     bool Op0IsKill, unsigned Op1,
2036                                     bool Op1IsKill, unsigned Op2,
2037                                     bool Op2IsKill) {
2038   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2039 
2040   Register ResultReg = createResultReg(RC);
2041   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
2042   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
2043   Op2 = constrainOperandRegClass(II, Op2, II.getNumDefs() + 2);
2044 
2045   if (II.getNumDefs() >= 1)
2046     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
2047         .addReg(Op0, getKillRegState(Op0IsKill))
2048         .addReg(Op1, getKillRegState(Op1IsKill))
2049         .addReg(Op2, getKillRegState(Op2IsKill));
2050   else {
2051     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
2052         .addReg(Op0, getKillRegState(Op0IsKill))
2053         .addReg(Op1, getKillRegState(Op1IsKill))
2054         .addReg(Op2, getKillRegState(Op2IsKill));
2055     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2056             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2057   }
2058   return ResultReg;
2059 }
2060 
2061 Register FastISel::fastEmitInst_ri(unsigned MachineInstOpcode,
2062                                    const TargetRegisterClass *RC, unsigned Op0,
2063                                    bool Op0IsKill, uint64_t Imm) {
2064   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2065 
2066   Register ResultReg = createResultReg(RC);
2067   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
2068 
2069   if (II.getNumDefs() >= 1)
2070     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
2071         .addReg(Op0, getKillRegState(Op0IsKill))
2072         .addImm(Imm);
2073   else {
2074     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
2075         .addReg(Op0, getKillRegState(Op0IsKill))
2076         .addImm(Imm);
2077     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2078             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2079   }
2080   return ResultReg;
2081 }
2082 
2083 Register FastISel::fastEmitInst_rii(unsigned MachineInstOpcode,
2084                                     const TargetRegisterClass *RC, unsigned Op0,
2085                                     bool Op0IsKill, uint64_t Imm1,
2086                                     uint64_t Imm2) {
2087   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2088 
2089   Register ResultReg = createResultReg(RC);
2090   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
2091 
2092   if (II.getNumDefs() >= 1)
2093     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
2094         .addReg(Op0, getKillRegState(Op0IsKill))
2095         .addImm(Imm1)
2096         .addImm(Imm2);
2097   else {
2098     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
2099         .addReg(Op0, getKillRegState(Op0IsKill))
2100         .addImm(Imm1)
2101         .addImm(Imm2);
2102     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2103             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2104   }
2105   return ResultReg;
2106 }
2107 
2108 Register FastISel::fastEmitInst_f(unsigned MachineInstOpcode,
2109                                   const TargetRegisterClass *RC,
2110                                   const ConstantFP *FPImm) {
2111   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2112 
2113   Register ResultReg = createResultReg(RC);
2114 
2115   if (II.getNumDefs() >= 1)
2116     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
2117         .addFPImm(FPImm);
2118   else {
2119     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
2120         .addFPImm(FPImm);
2121     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2122             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2123   }
2124   return ResultReg;
2125 }
2126 
2127 Register FastISel::fastEmitInst_rri(unsigned MachineInstOpcode,
2128                                     const TargetRegisterClass *RC, unsigned Op0,
2129                                     bool Op0IsKill, unsigned Op1,
2130                                     bool Op1IsKill, uint64_t Imm) {
2131   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2132 
2133   Register ResultReg = createResultReg(RC);
2134   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
2135   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
2136 
2137   if (II.getNumDefs() >= 1)
2138     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
2139         .addReg(Op0, getKillRegState(Op0IsKill))
2140         .addReg(Op1, getKillRegState(Op1IsKill))
2141         .addImm(Imm);
2142   else {
2143     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
2144         .addReg(Op0, getKillRegState(Op0IsKill))
2145         .addReg(Op1, getKillRegState(Op1IsKill))
2146         .addImm(Imm);
2147     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2148             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2149   }
2150   return ResultReg;
2151 }
2152 
2153 Register FastISel::fastEmitInst_i(unsigned MachineInstOpcode,
2154                                   const TargetRegisterClass *RC, uint64_t Imm) {
2155   Register ResultReg = createResultReg(RC);
2156   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2157 
2158   if (II.getNumDefs() >= 1)
2159     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
2160         .addImm(Imm);
2161   else {
2162     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II).addImm(Imm);
2163     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2164             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2165   }
2166   return ResultReg;
2167 }
2168 
2169 Register FastISel::fastEmitInst_extractsubreg(MVT RetVT, unsigned Op0,
2170                                               bool Op0IsKill, uint32_t Idx) {
2171   Register ResultReg = createResultReg(TLI.getRegClassFor(RetVT));
2172   assert(Register::isVirtualRegister(Op0) &&
2173          "Cannot yet extract from physregs");
2174   const TargetRegisterClass *RC = MRI.getRegClass(Op0);
2175   MRI.constrainRegClass(Op0, TRI.getSubClassWithSubReg(RC, Idx));
2176   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(TargetOpcode::COPY),
2177           ResultReg).addReg(Op0, getKillRegState(Op0IsKill), Idx);
2178   return ResultReg;
2179 }
2180 
2181 /// Emit MachineInstrs to compute the value of Op with all but the least
2182 /// significant bit set to zero.
2183 Register FastISel::fastEmitZExtFromI1(MVT VT, unsigned Op0, bool Op0IsKill) {
2184   return fastEmit_ri(VT, VT, ISD::AND, Op0, Op0IsKill, 1);
2185 }
2186 
2187 /// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks.
2188 /// Emit code to ensure constants are copied into registers when needed.
2189 /// Remember the virtual registers that need to be added to the Machine PHI
2190 /// nodes as input.  We cannot just directly add them, because expansion
2191 /// might result in multiple MBB's for one BB.  As such, the start of the
2192 /// BB might correspond to a different MBB than the end.
2193 bool FastISel::handlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) {
2194   const Instruction *TI = LLVMBB->getTerminator();
2195 
2196   SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled;
2197   FuncInfo.OrigNumPHINodesToUpdate = FuncInfo.PHINodesToUpdate.size();
2198 
2199   // Check successor nodes' PHI nodes that expect a constant to be available
2200   // from this block.
2201   for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
2202     const BasicBlock *SuccBB = TI->getSuccessor(succ);
2203     if (!isa<PHINode>(SuccBB->begin()))
2204       continue;
2205     MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB];
2206 
2207     // If this terminator has multiple identical successors (common for
2208     // switches), only handle each succ once.
2209     if (!SuccsHandled.insert(SuccMBB).second)
2210       continue;
2211 
2212     MachineBasicBlock::iterator MBBI = SuccMBB->begin();
2213 
2214     // At this point we know that there is a 1-1 correspondence between LLVM PHI
2215     // nodes and Machine PHI nodes, but the incoming operands have not been
2216     // emitted yet.
2217     for (const PHINode &PN : SuccBB->phis()) {
2218       // Ignore dead phi's.
2219       if (PN.use_empty())
2220         continue;
2221 
2222       // Only handle legal types. Two interesting things to note here. First,
2223       // by bailing out early, we may leave behind some dead instructions,
2224       // since SelectionDAG's HandlePHINodesInSuccessorBlocks will insert its
2225       // own moves. Second, this check is necessary because FastISel doesn't
2226       // use CreateRegs to create registers, so it always creates
2227       // exactly one register for each non-void instruction.
2228       EVT VT = TLI.getValueType(DL, PN.getType(), /*AllowUnknown=*/true);
2229       if (VT == MVT::Other || !TLI.isTypeLegal(VT)) {
2230         // Handle integer promotions, though, because they're common and easy.
2231         if (!(VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16)) {
2232           FuncInfo.PHINodesToUpdate.resize(FuncInfo.OrigNumPHINodesToUpdate);
2233           return false;
2234         }
2235       }
2236 
2237       const Value *PHIOp = PN.getIncomingValueForBlock(LLVMBB);
2238 
2239       // Set the DebugLoc for the copy. Use the location of the operand if
2240       // there is one; otherwise no location, flushLocalValueMap will fix it.
2241       DbgLoc = DebugLoc();
2242       if (const auto *Inst = dyn_cast<Instruction>(PHIOp))
2243         DbgLoc = Inst->getDebugLoc();
2244 
2245       Register Reg = getRegForValue(PHIOp);
2246       if (!Reg) {
2247         FuncInfo.PHINodesToUpdate.resize(FuncInfo.OrigNumPHINodesToUpdate);
2248         return false;
2249       }
2250       FuncInfo.PHINodesToUpdate.push_back(std::make_pair(&*MBBI++, Reg));
2251       DbgLoc = DebugLoc();
2252     }
2253   }
2254 
2255   return true;
2256 }
2257 
2258 bool FastISel::tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst) {
2259   assert(LI->hasOneUse() &&
2260          "tryToFoldLoad expected a LoadInst with a single use");
2261   // We know that the load has a single use, but don't know what it is.  If it
2262   // isn't one of the folded instructions, then we can't succeed here.  Handle
2263   // this by scanning the single-use users of the load until we get to FoldInst.
2264   unsigned MaxUsers = 6; // Don't scan down huge single-use chains of instrs.
2265 
2266   const Instruction *TheUser = LI->user_back();
2267   while (TheUser != FoldInst && // Scan up until we find FoldInst.
2268          // Stay in the right block.
2269          TheUser->getParent() == FoldInst->getParent() &&
2270          --MaxUsers) { // Don't scan too far.
2271     // If there are multiple or no uses of this instruction, then bail out.
2272     if (!TheUser->hasOneUse())
2273       return false;
2274 
2275     TheUser = TheUser->user_back();
2276   }
2277 
2278   // If we didn't find the fold instruction, then we failed to collapse the
2279   // sequence.
2280   if (TheUser != FoldInst)
2281     return false;
2282 
2283   // Don't try to fold volatile loads.  Target has to deal with alignment
2284   // constraints.
2285   if (LI->isVolatile())
2286     return false;
2287 
2288   // Figure out which vreg this is going into.  If there is no assigned vreg yet
2289   // then there actually was no reference to it.  Perhaps the load is referenced
2290   // by a dead instruction.
2291   Register LoadReg = getRegForValue(LI);
2292   if (!LoadReg)
2293     return false;
2294 
2295   // We can't fold if this vreg has no uses or more than one use.  Multiple uses
2296   // may mean that the instruction got lowered to multiple MIs, or the use of
2297   // the loaded value ended up being multiple operands of the result.
2298   if (!MRI.hasOneUse(LoadReg))
2299     return false;
2300 
2301   MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LoadReg);
2302   MachineInstr *User = RI->getParent();
2303 
2304   // Set the insertion point properly.  Folding the load can cause generation of
2305   // other random instructions (like sign extends) for addressing modes; make
2306   // sure they get inserted in a logical place before the new instruction.
2307   FuncInfo.InsertPt = User;
2308   FuncInfo.MBB = User->getParent();
2309 
2310   // Ask the target to try folding the load.
2311   return tryToFoldLoadIntoMI(User, RI.getOperandNo(), LI);
2312 }
2313 
2314 bool FastISel::canFoldAddIntoGEP(const User *GEP, const Value *Add) {
2315   // Must be an add.
2316   if (!isa<AddOperator>(Add))
2317     return false;
2318   // Type size needs to match.
2319   if (DL.getTypeSizeInBits(GEP->getType()) !=
2320       DL.getTypeSizeInBits(Add->getType()))
2321     return false;
2322   // Must be in the same basic block.
2323   if (isa<Instruction>(Add) &&
2324       FuncInfo.MBBMap[cast<Instruction>(Add)->getParent()] != FuncInfo.MBB)
2325     return false;
2326   // Must have a constant operand.
2327   return isa<ConstantInt>(cast<AddOperator>(Add)->getOperand(1));
2328 }
2329 
2330 MachineMemOperand *
2331 FastISel::createMachineMemOperandFor(const Instruction *I) const {
2332   const Value *Ptr;
2333   Type *ValTy;
2334   MaybeAlign Alignment;
2335   MachineMemOperand::Flags Flags;
2336   bool IsVolatile;
2337 
2338   if (const auto *LI = dyn_cast<LoadInst>(I)) {
2339     Alignment = LI->getAlign();
2340     IsVolatile = LI->isVolatile();
2341     Flags = MachineMemOperand::MOLoad;
2342     Ptr = LI->getPointerOperand();
2343     ValTy = LI->getType();
2344   } else if (const auto *SI = dyn_cast<StoreInst>(I)) {
2345     Alignment = SI->getAlign();
2346     IsVolatile = SI->isVolatile();
2347     Flags = MachineMemOperand::MOStore;
2348     Ptr = SI->getPointerOperand();
2349     ValTy = SI->getValueOperand()->getType();
2350   } else
2351     return nullptr;
2352 
2353   bool IsNonTemporal = I->hasMetadata(LLVMContext::MD_nontemporal);
2354   bool IsInvariant = I->hasMetadata(LLVMContext::MD_invariant_load);
2355   bool IsDereferenceable = I->hasMetadata(LLVMContext::MD_dereferenceable);
2356   const MDNode *Ranges = I->getMetadata(LLVMContext::MD_range);
2357 
2358   AAMDNodes AAInfo;
2359   I->getAAMetadata(AAInfo);
2360 
2361   if (!Alignment) // Ensure that codegen never sees alignment 0.
2362     Alignment = DL.getABITypeAlign(ValTy);
2363 
2364   unsigned Size = DL.getTypeStoreSize(ValTy);
2365 
2366   if (IsVolatile)
2367     Flags |= MachineMemOperand::MOVolatile;
2368   if (IsNonTemporal)
2369     Flags |= MachineMemOperand::MONonTemporal;
2370   if (IsDereferenceable)
2371     Flags |= MachineMemOperand::MODereferenceable;
2372   if (IsInvariant)
2373     Flags |= MachineMemOperand::MOInvariant;
2374 
2375   return FuncInfo.MF->getMachineMemOperand(MachinePointerInfo(Ptr), Flags, Size,
2376                                            *Alignment, AAInfo, Ranges);
2377 }
2378 
2379 CmpInst::Predicate FastISel::optimizeCmpPredicate(const CmpInst *CI) const {
2380   // If both operands are the same, then try to optimize or fold the cmp.
2381   CmpInst::Predicate Predicate = CI->getPredicate();
2382   if (CI->getOperand(0) != CI->getOperand(1))
2383     return Predicate;
2384 
2385   switch (Predicate) {
2386   default: llvm_unreachable("Invalid predicate!");
2387   case CmpInst::FCMP_FALSE: Predicate = CmpInst::FCMP_FALSE; break;
2388   case CmpInst::FCMP_OEQ:   Predicate = CmpInst::FCMP_ORD;   break;
2389   case CmpInst::FCMP_OGT:   Predicate = CmpInst::FCMP_FALSE; break;
2390   case CmpInst::FCMP_OGE:   Predicate = CmpInst::FCMP_ORD;   break;
2391   case CmpInst::FCMP_OLT:   Predicate = CmpInst::FCMP_FALSE; break;
2392   case CmpInst::FCMP_OLE:   Predicate = CmpInst::FCMP_ORD;   break;
2393   case CmpInst::FCMP_ONE:   Predicate = CmpInst::FCMP_FALSE; break;
2394   case CmpInst::FCMP_ORD:   Predicate = CmpInst::FCMP_ORD;   break;
2395   case CmpInst::FCMP_UNO:   Predicate = CmpInst::FCMP_UNO;   break;
2396   case CmpInst::FCMP_UEQ:   Predicate = CmpInst::FCMP_TRUE;  break;
2397   case CmpInst::FCMP_UGT:   Predicate = CmpInst::FCMP_UNO;   break;
2398   case CmpInst::FCMP_UGE:   Predicate = CmpInst::FCMP_TRUE;  break;
2399   case CmpInst::FCMP_ULT:   Predicate = CmpInst::FCMP_UNO;   break;
2400   case CmpInst::FCMP_ULE:   Predicate = CmpInst::FCMP_TRUE;  break;
2401   case CmpInst::FCMP_UNE:   Predicate = CmpInst::FCMP_UNO;   break;
2402   case CmpInst::FCMP_TRUE:  Predicate = CmpInst::FCMP_TRUE;  break;
2403 
2404   case CmpInst::ICMP_EQ:    Predicate = CmpInst::FCMP_TRUE;  break;
2405   case CmpInst::ICMP_NE:    Predicate = CmpInst::FCMP_FALSE; break;
2406   case CmpInst::ICMP_UGT:   Predicate = CmpInst::FCMP_FALSE; break;
2407   case CmpInst::ICMP_UGE:   Predicate = CmpInst::FCMP_TRUE;  break;
2408   case CmpInst::ICMP_ULT:   Predicate = CmpInst::FCMP_FALSE; break;
2409   case CmpInst::ICMP_ULE:   Predicate = CmpInst::FCMP_TRUE;  break;
2410   case CmpInst::ICMP_SGT:   Predicate = CmpInst::FCMP_FALSE; break;
2411   case CmpInst::ICMP_SGE:   Predicate = CmpInst::FCMP_TRUE;  break;
2412   case CmpInst::ICMP_SLT:   Predicate = CmpInst::FCMP_FALSE; break;
2413   case CmpInst::ICMP_SLE:   Predicate = CmpInst::FCMP_TRUE;  break;
2414   }
2415 
2416   return Predicate;
2417 }
2418