LLVM  mainline
FastISel.cpp
Go to the documentation of this file.
00001 //===-- FastISel.cpp - Implementation of the FastISel class ---------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file contains the implementation of the FastISel class.
00011 //
00012 // "Fast" instruction selection is designed to emit very poor code quickly.
00013 // Also, it is not designed to be able to do much lowering, so most illegal
00014 // types (e.g. i64 on 32-bit targets) and operations are not supported.  It is
00015 // also not intended to be able to do much optimization, except in a few cases
00016 // where doing optimizations reduces overall compile time.  For example, folding
00017 // constants into immediate fields is often done, because it's cheap and it
00018 // reduces the number of instructions later phases have to examine.
00019 //
00020 // "Fast" instruction selection is able to fail gracefully and transfer
00021 // control to the SelectionDAG selector for operations that it doesn't
00022 // support.  In many cases, this allows us to avoid duplicating a lot of
00023 // the complicated lowering logic that SelectionDAG currently has.
00024 //
00025 // The intended use for "fast" instruction selection is "-O0" mode
00026 // compilation, where the quality of the generated code is irrelevant when
00027 // weighed against the speed at which the code can be generated.  Also,
00028 // at -O0, the LLVM optimizers are not running, and this makes the
00029 // compile time of codegen a much higher portion of the overall compile
00030 // time.  Despite its limitations, "fast" instruction selection is able to
00031 // handle enough code on its own to provide noticeable overall speedups
00032 // in -O0 compiles.
00033 //
00034 // Basic operations are supported in a target-independent way, by reading
00035 // the same instruction descriptions that the SelectionDAG selector reads,
00036 // and identifying simple arithmetic operations that can be directly selected
00037 // from simple operators.  More complicated operations currently require
00038 // target-specific code.
00039 //
00040 //===----------------------------------------------------------------------===//
00041 
00042 #include "llvm/CodeGen/Analysis.h"
00043 #include "llvm/ADT/Optional.h"
00044 #include "llvm/ADT/Statistic.h"
00045 #include "llvm/Analysis/BranchProbabilityInfo.h"
00046 #include "llvm/Analysis/Loads.h"
00047 #include "llvm/Analysis/TargetLibraryInfo.h"
00048 #include "llvm/CodeGen/Analysis.h"
00049 #include "llvm/CodeGen/FastISel.h"
00050 #include "llvm/CodeGen/FunctionLoweringInfo.h"
00051 #include "llvm/CodeGen/MachineFrameInfo.h"
00052 #include "llvm/CodeGen/MachineInstrBuilder.h"
00053 #include "llvm/CodeGen/MachineModuleInfo.h"
00054 #include "llvm/CodeGen/MachineRegisterInfo.h"
00055 #include "llvm/CodeGen/StackMaps.h"
00056 #include "llvm/IR/DataLayout.h"
00057 #include "llvm/IR/DebugInfo.h"
00058 #include "llvm/IR/Function.h"
00059 #include "llvm/IR/GetElementPtrTypeIterator.h"
00060 #include "llvm/IR/GlobalVariable.h"
00061 #include "llvm/IR/Instructions.h"
00062 #include "llvm/IR/IntrinsicInst.h"
00063 #include "llvm/IR/Mangler.h"
00064 #include "llvm/IR/Operator.h"
00065 #include "llvm/Support/Debug.h"
00066 #include "llvm/Support/ErrorHandling.h"
00067 #include "llvm/Support/raw_ostream.h"
00068 #include "llvm/Target/TargetInstrInfo.h"
00069 #include "llvm/Target/TargetLowering.h"
00070 #include "llvm/Target/TargetMachine.h"
00071 #include "llvm/Target/TargetSubtargetInfo.h"
00072 using namespace llvm;
00073 
00074 #define DEBUG_TYPE "isel"
00075 
00076 STATISTIC(NumFastIselSuccessIndependent, "Number of insts selected by "
00077                                          "target-independent selector");
00078 STATISTIC(NumFastIselSuccessTarget, "Number of insts selected by "
00079                                     "target-specific selector");
00080 STATISTIC(NumFastIselDead, "Number of dead insts removed on failure");
00081 
00082 void FastISel::ArgListEntry::setAttributes(ImmutableCallSite *CS,
00083                                            unsigned AttrIdx) {
00084   IsSExt = CS->paramHasAttr(AttrIdx, Attribute::SExt);
00085   IsZExt = CS->paramHasAttr(AttrIdx, Attribute::ZExt);
00086   IsInReg = CS->paramHasAttr(AttrIdx, Attribute::InReg);
00087   IsSRet = CS->paramHasAttr(AttrIdx, Attribute::StructRet);
00088   IsNest = CS->paramHasAttr(AttrIdx, Attribute::Nest);
00089   IsByVal = CS->paramHasAttr(AttrIdx, Attribute::ByVal);
00090   IsInAlloca = CS->paramHasAttr(AttrIdx, Attribute::InAlloca);
00091   IsReturned = CS->paramHasAttr(AttrIdx, Attribute::Returned);
00092   Alignment = CS->getParamAlignment(AttrIdx);
00093 }
00094 
00095 /// Set the current block to which generated machine instructions will be
00096 /// appended, and clear the local CSE map.
00097 void FastISel::startNewBlock() {
00098   LocalValueMap.clear();
00099 
00100   // Instructions are appended to FuncInfo.MBB. If the basic block already
00101   // contains labels or copies, use the last instruction as the last local
00102   // value.
00103   EmitStartPt = nullptr;
00104   if (!FuncInfo.MBB->empty())
00105     EmitStartPt = &FuncInfo.MBB->back();
00106   LastLocalValue = EmitStartPt;
00107 }
00108 
00109 bool FastISel::lowerArguments() {
00110   if (!FuncInfo.CanLowerReturn)
00111     // Fallback to SDISel argument lowering code to deal with sret pointer
00112     // parameter.
00113     return false;
00114 
00115   if (!fastLowerArguments())
00116     return false;
00117 
00118   // Enter arguments into ValueMap for uses in non-entry BBs.
00119   for (Function::const_arg_iterator I = FuncInfo.Fn->arg_begin(),
00120                                     E = FuncInfo.Fn->arg_end();
00121        I != E; ++I) {
00122     DenseMap<const Value *, unsigned>::iterator VI = LocalValueMap.find(&*I);
00123     assert(VI != LocalValueMap.end() && "Missed an argument?");
00124     FuncInfo.ValueMap[&*I] = VI->second;
00125   }
00126   return true;
00127 }
00128 
00129 void FastISel::flushLocalValueMap() {
00130   LocalValueMap.clear();
00131   LastLocalValue = EmitStartPt;
00132   recomputeInsertPt();
00133   SavedInsertPt = FuncInfo.InsertPt;
00134 }
00135 
00136 bool FastISel::hasTrivialKill(const Value *V) {
00137   // Don't consider constants or arguments to have trivial kills.
00138   const Instruction *I = dyn_cast<Instruction>(V);
00139   if (!I)
00140     return false;
00141 
00142   // No-op casts are trivially coalesced by fast-isel.
00143   if (const auto *Cast = dyn_cast<CastInst>(I))
00144     if (Cast->isNoopCast(DL.getIntPtrType(Cast->getContext())) &&
00145         !hasTrivialKill(Cast->getOperand(0)))
00146       return false;
00147 
00148   // Even the value might have only one use in the LLVM IR, it is possible that
00149   // FastISel might fold the use into another instruction and now there is more
00150   // than one use at the Machine Instruction level.
00151   unsigned Reg = lookUpRegForValue(V);
00152   if (Reg && !MRI.use_empty(Reg))
00153     return false;
00154 
00155   // GEPs with all zero indices are trivially coalesced by fast-isel.
00156   if (const auto *GEP = dyn_cast<GetElementPtrInst>(I))
00157     if (GEP->hasAllZeroIndices() && !hasTrivialKill(GEP->getOperand(0)))
00158       return false;
00159 
00160   // Only instructions with a single use in the same basic block are considered
00161   // to have trivial kills.
00162   return I->hasOneUse() &&
00163          !(I->getOpcode() == Instruction::BitCast ||
00164            I->getOpcode() == Instruction::PtrToInt ||
00165            I->getOpcode() == Instruction::IntToPtr) &&
00166          cast<Instruction>(*I->user_begin())->getParent() == I->getParent();
00167 }
00168 
00169 unsigned FastISel::getRegForValue(const Value *V) {
00170   EVT RealVT = TLI.getValueType(DL, V->getType(), /*AllowUnknown=*/true);
00171   // Don't handle non-simple values in FastISel.
00172   if (!RealVT.isSimple())
00173     return 0;
00174 
00175   // Ignore illegal types. We must do this before looking up the value
00176   // in ValueMap because Arguments are given virtual registers regardless
00177   // of whether FastISel can handle them.
00178   MVT VT = RealVT.getSimpleVT();
00179   if (!TLI.isTypeLegal(VT)) {
00180     // Handle integer promotions, though, because they're common and easy.
00181     if (VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16)
00182       VT = TLI.getTypeToTransformTo(V->getContext(), VT).getSimpleVT();
00183     else
00184       return 0;
00185   }
00186 
00187   // Look up the value to see if we already have a register for it.
00188   unsigned Reg = lookUpRegForValue(V);
00189   if (Reg)
00190     return Reg;
00191 
00192   // In bottom-up mode, just create the virtual register which will be used
00193   // to hold the value. It will be materialized later.
00194   if (isa<Instruction>(V) &&
00195       (!isa<AllocaInst>(V) ||
00196        !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(V))))
00197     return FuncInfo.InitializeRegForValue(V);
00198 
00199   SavePoint SaveInsertPt = enterLocalValueArea();
00200 
00201   // Materialize the value in a register. Emit any instructions in the
00202   // local value area.
00203   Reg = materializeRegForValue(V, VT);
00204 
00205   leaveLocalValueArea(SaveInsertPt);
00206 
00207   return Reg;
00208 }
00209 
00210 unsigned FastISel::materializeConstant(const Value *V, MVT VT) {
00211   unsigned Reg = 0;
00212   if (const auto *CI = dyn_cast<ConstantInt>(V)) {
00213     if (CI->getValue().getActiveBits() <= 64)
00214       Reg = fastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue());
00215   } else if (isa<AllocaInst>(V))
00216     Reg = fastMaterializeAlloca(cast<AllocaInst>(V));
00217   else if (isa<ConstantPointerNull>(V))
00218     // Translate this as an integer zero so that it can be
00219     // local-CSE'd with actual integer zeros.
00220     Reg = getRegForValue(
00221         Constant::getNullValue(DL.getIntPtrType(V->getContext())));
00222   else if (const auto *CF = dyn_cast<ConstantFP>(V)) {
00223     if (CF->isNullValue())
00224       Reg = fastMaterializeFloatZero(CF);
00225     else
00226       // Try to emit the constant directly.
00227       Reg = fastEmit_f(VT, VT, ISD::ConstantFP, CF);
00228 
00229     if (!Reg) {
00230       // Try to emit the constant by using an integer constant with a cast.
00231       const APFloat &Flt = CF->getValueAPF();
00232       EVT IntVT = TLI.getPointerTy(DL);
00233 
00234       uint64_t x[2];
00235       uint32_t IntBitWidth = IntVT.getSizeInBits();
00236       bool isExact;
00237       (void)Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true,
00238                                  APFloat::rmTowardZero, &isExact);
00239       if (isExact) {
00240         APInt IntVal(IntBitWidth, x);
00241 
00242         unsigned IntegerReg =
00243             getRegForValue(ConstantInt::get(V->getContext(), IntVal));
00244         if (IntegerReg != 0)
00245           Reg = fastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP, IntegerReg,
00246                            /*Kill=*/false);
00247       }
00248     }
00249   } else if (const auto *Op = dyn_cast<Operator>(V)) {
00250     if (!selectOperator(Op, Op->getOpcode()))
00251       if (!isa<Instruction>(Op) ||
00252           !fastSelectInstruction(cast<Instruction>(Op)))
00253         return 0;
00254     Reg = lookUpRegForValue(Op);
00255   } else if (isa<UndefValue>(V)) {
00256     Reg = createResultReg(TLI.getRegClassFor(VT));
00257     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
00258             TII.get(TargetOpcode::IMPLICIT_DEF), Reg);
00259   }
00260   return Reg;
00261 }
00262 
00263 /// Helper for getRegForValue. This function is called when the value isn't
00264 /// already available in a register and must be materialized with new
00265 /// instructions.
00266 unsigned FastISel::materializeRegForValue(const Value *V, MVT VT) {
00267   unsigned Reg = 0;
00268   // Give the target-specific code a try first.
00269   if (isa<Constant>(V))
00270     Reg = fastMaterializeConstant(cast<Constant>(V));
00271 
00272   // If target-specific code couldn't or didn't want to handle the value, then
00273   // give target-independent code a try.
00274   if (!Reg)
00275     Reg = materializeConstant(V, VT);
00276 
00277   // Don't cache constant materializations in the general ValueMap.
00278   // To do so would require tracking what uses they dominate.
00279   if (Reg) {
00280     LocalValueMap[V] = Reg;
00281     LastLocalValue = MRI.getVRegDef(Reg);
00282   }
00283   return Reg;
00284 }
00285 
00286 unsigned FastISel::lookUpRegForValue(const Value *V) {
00287   // Look up the value to see if we already have a register for it. We
00288   // cache values defined by Instructions across blocks, and other values
00289   // only locally. This is because Instructions already have the SSA
00290   // def-dominates-use requirement enforced.
00291   DenseMap<const Value *, unsigned>::iterator I = FuncInfo.ValueMap.find(V);
00292   if (I != FuncInfo.ValueMap.end())
00293     return I->second;
00294   return LocalValueMap[V];
00295 }
00296 
00297 void FastISel::updateValueMap(const Value *I, unsigned Reg, unsigned NumRegs) {
00298   if (!isa<Instruction>(I)) {
00299     LocalValueMap[I] = Reg;
00300     return;
00301   }
00302 
00303   unsigned &AssignedReg = FuncInfo.ValueMap[I];
00304   if (AssignedReg == 0)
00305     // Use the new register.
00306     AssignedReg = Reg;
00307   else if (Reg != AssignedReg) {
00308     // Arrange for uses of AssignedReg to be replaced by uses of Reg.
00309     for (unsigned i = 0; i < NumRegs; i++)
00310       FuncInfo.RegFixups[AssignedReg + i] = Reg + i;
00311 
00312     AssignedReg = Reg;
00313   }
00314 }
00315 
00316 std::pair<unsigned, bool> FastISel::getRegForGEPIndex(const Value *Idx) {
00317   unsigned IdxN = getRegForValue(Idx);
00318   if (IdxN == 0)
00319     // Unhandled operand. Halt "fast" selection and bail.
00320     return std::pair<unsigned, bool>(0, false);
00321 
00322   bool IdxNIsKill = hasTrivialKill(Idx);
00323 
00324   // If the index is smaller or larger than intptr_t, truncate or extend it.
00325   MVT PtrVT = TLI.getPointerTy(DL);
00326   EVT IdxVT = EVT::getEVT(Idx->getType(), /*HandleUnknown=*/false);
00327   if (IdxVT.bitsLT(PtrVT)) {
00328     IdxN = fastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::SIGN_EXTEND, IdxN,
00329                       IdxNIsKill);
00330     IdxNIsKill = true;
00331   } else if (IdxVT.bitsGT(PtrVT)) {
00332     IdxN =
00333         fastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::TRUNCATE, IdxN, IdxNIsKill);
00334     IdxNIsKill = true;
00335   }
00336   return std::pair<unsigned, bool>(IdxN, IdxNIsKill);
00337 }
00338 
00339 void FastISel::recomputeInsertPt() {
00340   if (getLastLocalValue()) {
00341     FuncInfo.InsertPt = getLastLocalValue();
00342     FuncInfo.MBB = FuncInfo.InsertPt->getParent();
00343     ++FuncInfo.InsertPt;
00344   } else
00345     FuncInfo.InsertPt = FuncInfo.MBB->getFirstNonPHI();
00346 
00347   // Now skip past any EH_LABELs, which must remain at the beginning.
00348   while (FuncInfo.InsertPt != FuncInfo.MBB->end() &&
00349          FuncInfo.InsertPt->getOpcode() == TargetOpcode::EH_LABEL)
00350     ++FuncInfo.InsertPt;
00351 }
00352 
00353 void FastISel::removeDeadCode(MachineBasicBlock::iterator I,
00354                               MachineBasicBlock::iterator E) {
00355   assert(I && E && std::distance(I, E) > 0 && "Invalid iterator!");
00356   while (I != E) {
00357     MachineInstr *Dead = &*I;
00358     ++I;
00359     Dead->eraseFromParent();
00360     ++NumFastIselDead;
00361   }
00362   recomputeInsertPt();
00363 }
00364 
00365 FastISel::SavePoint FastISel::enterLocalValueArea() {
00366   MachineBasicBlock::iterator OldInsertPt = FuncInfo.InsertPt;
00367   DebugLoc OldDL = DbgLoc;
00368   recomputeInsertPt();
00369   DbgLoc = DebugLoc();
00370   SavePoint SP = {OldInsertPt, OldDL};
00371   return SP;
00372 }
00373 
00374 void FastISel::leaveLocalValueArea(SavePoint OldInsertPt) {
00375   if (FuncInfo.InsertPt != FuncInfo.MBB->begin())
00376     LastLocalValue = std::prev(FuncInfo.InsertPt);
00377 
00378   // Restore the previous insert position.
00379   FuncInfo.InsertPt = OldInsertPt.InsertPt;
00380   DbgLoc = OldInsertPt.DL;
00381 }
00382 
00383 bool FastISel::selectBinaryOp(const User *I, unsigned ISDOpcode) {
00384   EVT VT = EVT::getEVT(I->getType(), /*HandleUnknown=*/true);
00385   if (VT == MVT::Other || !VT.isSimple())
00386     // Unhandled type. Halt "fast" selection and bail.
00387     return false;
00388 
00389   // We only handle legal types. For example, on x86-32 the instruction
00390   // selector contains all of the 64-bit instructions from x86-64,
00391   // under the assumption that i64 won't be used if the target doesn't
00392   // support it.
00393   if (!TLI.isTypeLegal(VT)) {
00394     // MVT::i1 is special. Allow AND, OR, or XOR because they
00395     // don't require additional zeroing, which makes them easy.
00396     if (VT == MVT::i1 && (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR ||
00397                           ISDOpcode == ISD::XOR))
00398       VT = TLI.getTypeToTransformTo(I->getContext(), VT);
00399     else
00400       return false;
00401   }
00402 
00403   // Check if the first operand is a constant, and handle it as "ri".  At -O0,
00404   // we don't have anything that canonicalizes operand order.
00405   if (const auto *CI = dyn_cast<ConstantInt>(I->getOperand(0)))
00406     if (isa<Instruction>(I) && cast<Instruction>(I)->isCommutative()) {
00407       unsigned Op1 = getRegForValue(I->getOperand(1));
00408       if (!Op1)
00409         return false;
00410       bool Op1IsKill = hasTrivialKill(I->getOperand(1));
00411 
00412       unsigned ResultReg =
00413           fastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op1, Op1IsKill,
00414                        CI->getZExtValue(), VT.getSimpleVT());
00415       if (!ResultReg)
00416         return false;
00417 
00418       // We successfully emitted code for the given LLVM Instruction.
00419       updateValueMap(I, ResultReg);
00420       return true;
00421     }
00422 
00423   unsigned Op0 = getRegForValue(I->getOperand(0));
00424   if (!Op0) // Unhandled operand. Halt "fast" selection and bail.
00425     return false;
00426   bool Op0IsKill = hasTrivialKill(I->getOperand(0));
00427 
00428   // Check if the second operand is a constant and handle it appropriately.
00429   if (const auto *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
00430     uint64_t Imm = CI->getSExtValue();
00431 
00432     // Transform "sdiv exact X, 8" -> "sra X, 3".
00433     if (ISDOpcode == ISD::SDIV && isa<BinaryOperator>(I) &&
00434         cast<BinaryOperator>(I)->isExact() && isPowerOf2_64(Imm)) {
00435       Imm = Log2_64(Imm);
00436       ISDOpcode = ISD::SRA;
00437     }
00438 
00439     // Transform "urem x, pow2" -> "and x, pow2-1".
00440     if (ISDOpcode == ISD::UREM && isa<BinaryOperator>(I) &&
00441         isPowerOf2_64(Imm)) {
00442       --Imm;
00443       ISDOpcode = ISD::AND;
00444     }
00445 
00446     unsigned ResultReg = fastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op0,
00447                                       Op0IsKill, Imm, VT.getSimpleVT());
00448     if (!ResultReg)
00449       return false;
00450 
00451     // We successfully emitted code for the given LLVM Instruction.
00452     updateValueMap(I, ResultReg);
00453     return true;
00454   }
00455 
00456   // Check if the second operand is a constant float.
00457   if (const auto *CF = dyn_cast<ConstantFP>(I->getOperand(1))) {
00458     unsigned ResultReg = fastEmit_rf(VT.getSimpleVT(), VT.getSimpleVT(),
00459                                      ISDOpcode, Op0, Op0IsKill, CF);
00460     if (ResultReg) {
00461       // We successfully emitted code for the given LLVM Instruction.
00462       updateValueMap(I, ResultReg);
00463       return true;
00464     }
00465   }
00466 
00467   unsigned Op1 = getRegForValue(I->getOperand(1));
00468   if (!Op1) // Unhandled operand. Halt "fast" selection and bail.
00469     return false;
00470   bool Op1IsKill = hasTrivialKill(I->getOperand(1));
00471 
00472   // Now we have both operands in registers. Emit the instruction.
00473   unsigned ResultReg = fastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(),
00474                                    ISDOpcode, Op0, Op0IsKill, Op1, Op1IsKill);
00475   if (!ResultReg)
00476     // Target-specific code wasn't able to find a machine opcode for
00477     // the given ISD opcode and type. Halt "fast" selection and bail.
00478     return false;
00479 
00480   // We successfully emitted code for the given LLVM Instruction.
00481   updateValueMap(I, ResultReg);
00482   return true;
00483 }
00484 
00485 bool FastISel::selectGetElementPtr(const User *I) {
00486   unsigned N = getRegForValue(I->getOperand(0));
00487   if (!N) // Unhandled operand. Halt "fast" selection and bail.
00488     return false;
00489   bool NIsKill = hasTrivialKill(I->getOperand(0));
00490 
00491   // Keep a running tab of the total offset to coalesce multiple N = N + Offset
00492   // into a single N = N + TotalOffset.
00493   uint64_t TotalOffs = 0;
00494   // FIXME: What's a good SWAG number for MaxOffs?
00495   uint64_t MaxOffs = 2048;
00496   MVT VT = TLI.getPointerTy(DL);
00497   for (gep_type_iterator GTI = gep_type_begin(I), E = gep_type_end(I);
00498        GTI != E; ++GTI) {
00499     const Value *Idx = GTI.getOperand();
00500     if (auto *StTy = dyn_cast<StructType>(*GTI)) {
00501       uint64_t Field = cast<ConstantInt>(Idx)->getZExtValue();
00502       if (Field) {
00503         // N = N + Offset
00504         TotalOffs += DL.getStructLayout(StTy)->getElementOffset(Field);
00505         if (TotalOffs >= MaxOffs) {
00506           N = fastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
00507           if (!N) // Unhandled operand. Halt "fast" selection and bail.
00508             return false;
00509           NIsKill = true;
00510           TotalOffs = 0;
00511         }
00512       }
00513     } else {
00514       Type *Ty = GTI.getIndexedType();
00515 
00516       // If this is a constant subscript, handle it quickly.
00517       if (const auto *CI = dyn_cast<ConstantInt>(Idx)) {
00518         if (CI->isZero())
00519           continue;
00520         // N = N + Offset
00521         uint64_t IdxN = CI->getValue().sextOrTrunc(64).getSExtValue();
00522         TotalOffs += DL.getTypeAllocSize(Ty) * IdxN;
00523         if (TotalOffs >= MaxOffs) {
00524           N = fastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
00525           if (!N) // Unhandled operand. Halt "fast" selection and bail.
00526             return false;
00527           NIsKill = true;
00528           TotalOffs = 0;
00529         }
00530         continue;
00531       }
00532       if (TotalOffs) {
00533         N = fastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
00534         if (!N) // Unhandled operand. Halt "fast" selection and bail.
00535           return false;
00536         NIsKill = true;
00537         TotalOffs = 0;
00538       }
00539 
00540       // N = N + Idx * ElementSize;
00541       uint64_t ElementSize = DL.getTypeAllocSize(Ty);
00542       std::pair<unsigned, bool> Pair = getRegForGEPIndex(Idx);
00543       unsigned IdxN = Pair.first;
00544       bool IdxNIsKill = Pair.second;
00545       if (!IdxN) // Unhandled operand. Halt "fast" selection and bail.
00546         return false;
00547 
00548       if (ElementSize != 1) {
00549         IdxN = fastEmit_ri_(VT, ISD::MUL, IdxN, IdxNIsKill, ElementSize, VT);
00550         if (!IdxN) // Unhandled operand. Halt "fast" selection and bail.
00551           return false;
00552         IdxNIsKill = true;
00553       }
00554       N = fastEmit_rr(VT, VT, ISD::ADD, N, NIsKill, IdxN, IdxNIsKill);
00555       if (!N) // Unhandled operand. Halt "fast" selection and bail.
00556         return false;
00557     }
00558   }
00559   if (TotalOffs) {
00560     N = fastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
00561     if (!N) // Unhandled operand. Halt "fast" selection and bail.
00562       return false;
00563   }
00564 
00565   // We successfully emitted code for the given LLVM Instruction.
00566   updateValueMap(I, N);
00567   return true;
00568 }
00569 
00570 bool FastISel::addStackMapLiveVars(SmallVectorImpl<MachineOperand> &Ops,
00571                                    const CallInst *CI, unsigned StartIdx) {
00572   for (unsigned i = StartIdx, e = CI->getNumArgOperands(); i != e; ++i) {
00573     Value *Val = CI->getArgOperand(i);
00574     // Check for constants and encode them with a StackMaps::ConstantOp prefix.
00575     if (const auto *C = dyn_cast<ConstantInt>(Val)) {
00576       Ops.push_back(MachineOperand::CreateImm(StackMaps::ConstantOp));
00577       Ops.push_back(MachineOperand::CreateImm(C->getSExtValue()));
00578     } else if (isa<ConstantPointerNull>(Val)) {
00579       Ops.push_back(MachineOperand::CreateImm(StackMaps::ConstantOp));
00580       Ops.push_back(MachineOperand::CreateImm(0));
00581     } else if (auto *AI = dyn_cast<AllocaInst>(Val)) {
00582       // Values coming from a stack location also require a sepcial encoding,
00583       // but that is added later on by the target specific frame index
00584       // elimination implementation.
00585       auto SI = FuncInfo.StaticAllocaMap.find(AI);
00586       if (SI != FuncInfo.StaticAllocaMap.end())
00587         Ops.push_back(MachineOperand::CreateFI(SI->second));
00588       else
00589         return false;
00590     } else {
00591       unsigned Reg = getRegForValue(Val);
00592       if (!Reg)
00593         return false;
00594       Ops.push_back(MachineOperand::CreateReg(Reg, /*IsDef=*/false));
00595     }
00596   }
00597   return true;
00598 }
00599 
00600 bool FastISel::selectStackmap(const CallInst *I) {
00601   // void @llvm.experimental.stackmap(i64 <id>, i32 <numShadowBytes>,
00602   //                                  [live variables...])
00603   assert(I->getCalledFunction()->getReturnType()->isVoidTy() &&
00604          "Stackmap cannot return a value.");
00605 
00606   // The stackmap intrinsic only records the live variables (the arguments
00607   // passed to it) and emits NOPS (if requested). Unlike the patchpoint
00608   // intrinsic, this won't be lowered to a function call. This means we don't
00609   // have to worry about calling conventions and target-specific lowering code.
00610   // Instead we perform the call lowering right here.
00611   //
00612   // CALLSEQ_START(0...)
00613   // STACKMAP(id, nbytes, ...)
00614   // CALLSEQ_END(0, 0)
00615   //
00616   SmallVector<MachineOperand, 32> Ops;
00617 
00618   // Add the <id> and <numBytes> constants.
00619   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::IDPos)) &&
00620          "Expected a constant integer.");
00621   const auto *ID = cast<ConstantInt>(I->getOperand(PatchPointOpers::IDPos));
00622   Ops.push_back(MachineOperand::CreateImm(ID->getZExtValue()));
00623 
00624   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos)) &&
00625          "Expected a constant integer.");
00626   const auto *NumBytes =
00627       cast<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos));
00628   Ops.push_back(MachineOperand::CreateImm(NumBytes->getZExtValue()));
00629 
00630   // Push live variables for the stack map (skipping the first two arguments
00631   // <id> and <numBytes>).
00632   if (!addStackMapLiveVars(Ops, I, 2))
00633     return false;
00634 
00635   // We are not adding any register mask info here, because the stackmap doesn't
00636   // clobber anything.
00637 
00638   // Add scratch registers as implicit def and early clobber.
00639   CallingConv::ID CC = I->getCallingConv();
00640   const MCPhysReg *ScratchRegs = TLI.getScratchRegisters(CC);
00641   for (unsigned i = 0; ScratchRegs[i]; ++i)
00642     Ops.push_back(MachineOperand::CreateReg(
00643         ScratchRegs[i], /*IsDef=*/true, /*IsImp=*/true, /*IsKill=*/false,
00644         /*IsDead=*/false, /*IsUndef=*/false, /*IsEarlyClobber=*/true));
00645 
00646   // Issue CALLSEQ_START
00647   unsigned AdjStackDown = TII.getCallFrameSetupOpcode();
00648   auto Builder =
00649       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AdjStackDown));
00650   const MCInstrDesc &MCID = Builder.getInstr()->getDesc();
00651   for (unsigned I = 0, E = MCID.getNumOperands(); I < E; ++I)
00652     Builder.addImm(0);
00653 
00654   // Issue STACKMAP.
00655   MachineInstrBuilder MIB = BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
00656                                     TII.get(TargetOpcode::STACKMAP));
00657   for (auto const &MO : Ops)
00658     MIB.addOperand(MO);
00659 
00660   // Issue CALLSEQ_END
00661   unsigned AdjStackUp = TII.getCallFrameDestroyOpcode();
00662   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AdjStackUp))
00663       .addImm(0)
00664       .addImm(0);
00665 
00666   // Inform the Frame Information that we have a stackmap in this function.
00667   FuncInfo.MF->getFrameInfo()->setHasStackMap();
00668 
00669   return true;
00670 }
00671 
00672 /// \brief Lower an argument list according to the target calling convention.
00673 ///
00674 /// This is a helper for lowering intrinsics that follow a target calling
00675 /// convention or require stack pointer adjustment. Only a subset of the
00676 /// intrinsic's operands need to participate in the calling convention.
00677 bool FastISel::lowerCallOperands(const CallInst *CI, unsigned ArgIdx,
00678                                  unsigned NumArgs, const Value *Callee,
00679                                  bool ForceRetVoidTy, CallLoweringInfo &CLI) {
00680   ArgListTy Args;
00681   Args.reserve(NumArgs);
00682 
00683   // Populate the argument list.
00684   // Attributes for args start at offset 1, after the return attribute.
00685   ImmutableCallSite CS(CI);
00686   for (unsigned ArgI = ArgIdx, ArgE = ArgIdx + NumArgs, AttrI = ArgIdx + 1;
00687        ArgI != ArgE; ++ArgI) {
00688     Value *V = CI->getOperand(ArgI);
00689 
00690     assert(!V->getType()->isEmptyTy() && "Empty type passed to intrinsic.");
00691 
00692     ArgListEntry Entry;
00693     Entry.Val = V;
00694     Entry.Ty = V->getType();
00695     Entry.setAttributes(&CS, AttrI);
00696     Args.push_back(Entry);
00697   }
00698 
00699   Type *RetTy = ForceRetVoidTy ? Type::getVoidTy(CI->getType()->getContext())
00700                                : CI->getType();
00701   CLI.setCallee(CI->getCallingConv(), RetTy, Callee, std::move(Args), NumArgs);
00702 
00703   return lowerCallTo(CLI);
00704 }
00705 
00706 FastISel::CallLoweringInfo &FastISel::CallLoweringInfo::setCallee(
00707     const DataLayout &DL, MCContext &Ctx, CallingConv::ID CC, Type *ResultTy,
00708     const char *Target, ArgListTy &&ArgsList, unsigned FixedArgs) {
00709   SmallString<32> MangledName;
00710   Mangler::getNameWithPrefix(MangledName, Target, DL);
00711   MCSymbol *Sym = Ctx.getOrCreateSymbol(MangledName);
00712   return setCallee(CC, ResultTy, Sym, std::move(ArgsList), FixedArgs);
00713 }
00714 
00715 bool FastISel::selectPatchpoint(const CallInst *I) {
00716   // void|i64 @llvm.experimental.patchpoint.void|i64(i64 <id>,
00717   //                                                 i32 <numBytes>,
00718   //                                                 i8* <target>,
00719   //                                                 i32 <numArgs>,
00720   //                                                 [Args...],
00721   //                                                 [live variables...])
00722   CallingConv::ID CC = I->getCallingConv();
00723   bool IsAnyRegCC = CC == CallingConv::AnyReg;
00724   bool HasDef = !I->getType()->isVoidTy();
00725   Value *Callee = I->getOperand(PatchPointOpers::TargetPos)->stripPointerCasts();
00726 
00727   // Get the real number of arguments participating in the call <numArgs>
00728   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NArgPos)) &&
00729          "Expected a constant integer.");
00730   const auto *NumArgsVal =
00731       cast<ConstantInt>(I->getOperand(PatchPointOpers::NArgPos));
00732   unsigned NumArgs = NumArgsVal->getZExtValue();
00733 
00734   // Skip the four meta args: <id>, <numNopBytes>, <target>, <numArgs>
00735   // This includes all meta-operands up to but not including CC.
00736   unsigned NumMetaOpers = PatchPointOpers::CCPos;
00737   assert(I->getNumArgOperands() >= NumMetaOpers + NumArgs &&
00738          "Not enough arguments provided to the patchpoint intrinsic");
00739 
00740   // For AnyRegCC the arguments are lowered later on manually.
00741   unsigned NumCallArgs = IsAnyRegCC ? 0 : NumArgs;
00742   CallLoweringInfo CLI;
00743   CLI.setIsPatchPoint();
00744   if (!lowerCallOperands(I, NumMetaOpers, NumCallArgs, Callee, IsAnyRegCC, CLI))
00745     return false;
00746 
00747   assert(CLI.Call && "No call instruction specified.");
00748 
00749   SmallVector<MachineOperand, 32> Ops;
00750 
00751   // Add an explicit result reg if we use the anyreg calling convention.
00752   if (IsAnyRegCC && HasDef) {
00753     assert(CLI.NumResultRegs == 0 && "Unexpected result register.");
00754     CLI.ResultReg = createResultReg(TLI.getRegClassFor(MVT::i64));
00755     CLI.NumResultRegs = 1;
00756     Ops.push_back(MachineOperand::CreateReg(CLI.ResultReg, /*IsDef=*/true));
00757   }
00758 
00759   // Add the <id> and <numBytes> constants.
00760   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::IDPos)) &&
00761          "Expected a constant integer.");
00762   const auto *ID = cast<ConstantInt>(I->getOperand(PatchPointOpers::IDPos));
00763   Ops.push_back(MachineOperand::CreateImm(ID->getZExtValue()));
00764 
00765   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos)) &&
00766          "Expected a constant integer.");
00767   const auto *NumBytes =
00768       cast<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos));
00769   Ops.push_back(MachineOperand::CreateImm(NumBytes->getZExtValue()));
00770 
00771   // Add the call target.
00772   if (const auto *C = dyn_cast<IntToPtrInst>(Callee)) {
00773     uint64_t CalleeConstAddr =
00774       cast<ConstantInt>(C->getOperand(0))->getZExtValue();
00775     Ops.push_back(MachineOperand::CreateImm(CalleeConstAddr));
00776   } else if (const auto *C = dyn_cast<ConstantExpr>(Callee)) {
00777     if (C->getOpcode() == Instruction::IntToPtr) {
00778       uint64_t CalleeConstAddr =
00779         cast<ConstantInt>(C->getOperand(0))->getZExtValue();
00780       Ops.push_back(MachineOperand::CreateImm(CalleeConstAddr));
00781     } else
00782       llvm_unreachable("Unsupported ConstantExpr.");
00783   } else if (const auto *GV = dyn_cast<GlobalValue>(Callee)) {
00784     Ops.push_back(MachineOperand::CreateGA(GV, 0));
00785   } else if (isa<ConstantPointerNull>(Callee))
00786     Ops.push_back(MachineOperand::CreateImm(0));
00787   else
00788     llvm_unreachable("Unsupported callee address.");
00789 
00790   // Adjust <numArgs> to account for any arguments that have been passed on
00791   // the stack instead.
00792   unsigned NumCallRegArgs = IsAnyRegCC ? NumArgs : CLI.OutRegs.size();
00793   Ops.push_back(MachineOperand::CreateImm(NumCallRegArgs));
00794 
00795   // Add the calling convention
00796   Ops.push_back(MachineOperand::CreateImm((unsigned)CC));
00797 
00798   // Add the arguments we omitted previously. The register allocator should
00799   // place these in any free register.
00800   if (IsAnyRegCC) {
00801     for (unsigned i = NumMetaOpers, e = NumMetaOpers + NumArgs; i != e; ++i) {
00802       unsigned Reg = getRegForValue(I->getArgOperand(i));
00803       if (!Reg)
00804         return false;
00805       Ops.push_back(MachineOperand::CreateReg(Reg, /*IsDef=*/false));
00806     }
00807   }
00808 
00809   // Push the arguments from the call instruction.
00810   for (auto Reg : CLI.OutRegs)
00811     Ops.push_back(MachineOperand::CreateReg(Reg, /*IsDef=*/false));
00812 
00813   // Push live variables for the stack map.
00814   if (!addStackMapLiveVars(Ops, I, NumMetaOpers + NumArgs))
00815     return false;
00816 
00817   // Push the register mask info.
00818   Ops.push_back(MachineOperand::CreateRegMask(
00819       TRI.getCallPreservedMask(*FuncInfo.MF, CC)));
00820 
00821   // Add scratch registers as implicit def and early clobber.
00822   const MCPhysReg *ScratchRegs = TLI.getScratchRegisters(CC);
00823   for (unsigned i = 0; ScratchRegs[i]; ++i)
00824     Ops.push_back(MachineOperand::CreateReg(
00825         ScratchRegs[i], /*IsDef=*/true, /*IsImp=*/true, /*IsKill=*/false,
00826         /*IsDead=*/false, /*IsUndef=*/false, /*IsEarlyClobber=*/true));
00827 
00828   // Add implicit defs (return values).
00829   for (auto Reg : CLI.InRegs)
00830     Ops.push_back(MachineOperand::CreateReg(Reg, /*IsDef=*/true,
00831                                             /*IsImpl=*/true));
00832 
00833   // Insert the patchpoint instruction before the call generated by the target.
00834   MachineInstrBuilder MIB = BuildMI(*FuncInfo.MBB, CLI.Call, DbgLoc,
00835                                     TII.get(TargetOpcode::PATCHPOINT));
00836 
00837   for (auto &MO : Ops)
00838     MIB.addOperand(MO);
00839 
00840   MIB->setPhysRegsDeadExcept(CLI.InRegs, TRI);
00841 
00842   // Delete the original call instruction.
00843   CLI.Call->eraseFromParent();
00844 
00845   // Inform the Frame Information that we have a patchpoint in this function.
00846   FuncInfo.MF->getFrameInfo()->setHasPatchPoint();
00847 
00848   if (CLI.NumResultRegs)
00849     updateValueMap(I, CLI.ResultReg, CLI.NumResultRegs);
00850   return true;
00851 }
00852 
00853 /// Returns an AttributeSet representing the attributes applied to the return
00854 /// value of the given call.
00855 static AttributeSet getReturnAttrs(FastISel::CallLoweringInfo &CLI) {
00856   SmallVector<Attribute::AttrKind, 2> Attrs;
00857   if (CLI.RetSExt)
00858     Attrs.push_back(Attribute::SExt);
00859   if (CLI.RetZExt)
00860     Attrs.push_back(Attribute::ZExt);
00861   if (CLI.IsInReg)
00862     Attrs.push_back(Attribute::InReg);
00863 
00864   return AttributeSet::get(CLI.RetTy->getContext(), AttributeSet::ReturnIndex,
00865                            Attrs);
00866 }
00867 
00868 bool FastISel::lowerCallTo(const CallInst *CI, const char *SymName,
00869                            unsigned NumArgs) {
00870   MCContext &Ctx = MF->getContext();
00871   SmallString<32> MangledName;
00872   Mangler::getNameWithPrefix(MangledName, SymName, DL);
00873   MCSymbol *Sym = Ctx.getOrCreateSymbol(MangledName);
00874   return lowerCallTo(CI, Sym, NumArgs);
00875 }
00876 
00877 bool FastISel::lowerCallTo(const CallInst *CI, MCSymbol *Symbol,
00878                            unsigned NumArgs) {
00879   ImmutableCallSite CS(CI);
00880 
00881   FunctionType *FTy = CS.getFunctionType();
00882   Type *RetTy = CS.getType();
00883 
00884   ArgListTy Args;
00885   Args.reserve(NumArgs);
00886 
00887   // Populate the argument list.
00888   // Attributes for args start at offset 1, after the return attribute.
00889   for (unsigned ArgI = 0; ArgI != NumArgs; ++ArgI) {
00890     Value *V = CI->getOperand(ArgI);
00891 
00892     assert(!V->getType()->isEmptyTy() && "Empty type passed to intrinsic.");
00893 
00894     ArgListEntry Entry;
00895     Entry.Val = V;
00896     Entry.Ty = V->getType();
00897     Entry.setAttributes(&CS, ArgI + 1);
00898     Args.push_back(Entry);
00899   }
00900 
00901   CallLoweringInfo CLI;
00902   CLI.setCallee(RetTy, FTy, Symbol, std::move(Args), CS, NumArgs);
00903 
00904   return lowerCallTo(CLI);
00905 }
00906 
00907 bool FastISel::lowerCallTo(CallLoweringInfo &CLI) {
00908   // Handle the incoming return values from the call.
00909   CLI.clearIns();
00910   SmallVector<EVT, 4> RetTys;
00911   ComputeValueVTs(TLI, DL, CLI.RetTy, RetTys);
00912 
00913   SmallVector<ISD::OutputArg, 4> Outs;
00914   GetReturnInfo(CLI.RetTy, getReturnAttrs(CLI), Outs, TLI, DL);
00915 
00916   bool CanLowerReturn = TLI.CanLowerReturn(
00917       CLI.CallConv, *FuncInfo.MF, CLI.IsVarArg, Outs, CLI.RetTy->getContext());
00918 
00919   // FIXME: sret demotion isn't supported yet - bail out.
00920   if (!CanLowerReturn)
00921     return false;
00922 
00923   for (unsigned I = 0, E = RetTys.size(); I != E; ++I) {
00924     EVT VT = RetTys[I];
00925     MVT RegisterVT = TLI.getRegisterType(CLI.RetTy->getContext(), VT);
00926     unsigned NumRegs = TLI.getNumRegisters(CLI.RetTy->getContext(), VT);
00927     for (unsigned i = 0; i != NumRegs; ++i) {
00928       ISD::InputArg MyFlags;
00929       MyFlags.VT = RegisterVT;
00930       MyFlags.ArgVT = VT;
00931       MyFlags.Used = CLI.IsReturnValueUsed;
00932       if (CLI.RetSExt)
00933         MyFlags.Flags.setSExt();
00934       if (CLI.RetZExt)
00935         MyFlags.Flags.setZExt();
00936       if (CLI.IsInReg)
00937         MyFlags.Flags.setInReg();
00938       CLI.Ins.push_back(MyFlags);
00939     }
00940   }
00941 
00942   // Handle all of the outgoing arguments.
00943   CLI.clearOuts();
00944   for (auto &Arg : CLI.getArgs()) {
00945     Type *FinalType = Arg.Ty;
00946     if (Arg.IsByVal)
00947       FinalType = cast<PointerType>(Arg.Ty)->getElementType();
00948     bool NeedsRegBlock = TLI.functionArgumentNeedsConsecutiveRegisters(
00949         FinalType, CLI.CallConv, CLI.IsVarArg);
00950 
00951     ISD::ArgFlagsTy Flags;
00952     if (Arg.IsZExt)
00953       Flags.setZExt();
00954     if (Arg.IsSExt)
00955       Flags.setSExt();
00956     if (Arg.IsInReg)
00957       Flags.setInReg();
00958     if (Arg.IsSRet)
00959       Flags.setSRet();
00960     if (Arg.IsByVal)
00961       Flags.setByVal();
00962     if (Arg.IsInAlloca) {
00963       Flags.setInAlloca();
00964       // Set the byval flag for CCAssignFn callbacks that don't know about
00965       // inalloca. This way we can know how many bytes we should've allocated
00966       // and how many bytes a callee cleanup function will pop.  If we port
00967       // inalloca to more targets, we'll have to add custom inalloca handling in
00968       // the various CC lowering callbacks.
00969       Flags.setByVal();
00970     }
00971     if (Arg.IsByVal || Arg.IsInAlloca) {
00972       PointerType *Ty = cast<PointerType>(Arg.Ty);
00973       Type *ElementTy = Ty->getElementType();
00974       unsigned FrameSize = DL.getTypeAllocSize(ElementTy);
00975       // For ByVal, alignment should come from FE. BE will guess if this info is
00976       // not there, but there are cases it cannot get right.
00977       unsigned FrameAlign = Arg.Alignment;
00978       if (!FrameAlign)
00979         FrameAlign = TLI.getByValTypeAlignment(ElementTy, DL);
00980       Flags.setByValSize(FrameSize);
00981       Flags.setByValAlign(FrameAlign);
00982     }
00983     if (Arg.IsNest)
00984       Flags.setNest();
00985     if (NeedsRegBlock)
00986       Flags.setInConsecutiveRegs();
00987     unsigned OriginalAlignment = DL.getABITypeAlignment(Arg.Ty);
00988     Flags.setOrigAlign(OriginalAlignment);
00989 
00990     CLI.OutVals.push_back(Arg.Val);
00991     CLI.OutFlags.push_back(Flags);
00992   }
00993 
00994   if (!fastLowerCall(CLI))
00995     return false;
00996 
00997   // Set all unused physreg defs as dead.
00998   assert(CLI.Call && "No call instruction specified.");
00999   CLI.Call->setPhysRegsDeadExcept(CLI.InRegs, TRI);
01000 
01001   if (CLI.NumResultRegs && CLI.CS)
01002     updateValueMap(CLI.CS->getInstruction(), CLI.ResultReg, CLI.NumResultRegs);
01003 
01004   return true;
01005 }
01006 
01007 bool FastISel::lowerCall(const CallInst *CI) {
01008   ImmutableCallSite CS(CI);
01009 
01010   FunctionType *FuncTy = CS.getFunctionType();
01011   Type *RetTy = CS.getType();
01012 
01013   ArgListTy Args;
01014   ArgListEntry Entry;
01015   Args.reserve(CS.arg_size());
01016 
01017   for (ImmutableCallSite::arg_iterator i = CS.arg_begin(), e = CS.arg_end();
01018        i != e; ++i) {
01019     Value *V = *i;
01020 
01021     // Skip empty types
01022     if (V->getType()->isEmptyTy())
01023       continue;
01024 
01025     Entry.Val = V;
01026     Entry.Ty = V->getType();
01027 
01028     // Skip the first return-type Attribute to get to params.
01029     Entry.setAttributes(&CS, i - CS.arg_begin() + 1);
01030     Args.push_back(Entry);
01031   }
01032 
01033   // Check if target-independent constraints permit a tail call here.
01034   // Target-dependent constraints are checked within fastLowerCall.
01035   bool IsTailCall = CI->isTailCall();
01036   if (IsTailCall && !isInTailCallPosition(CS, TM))
01037     IsTailCall = false;
01038 
01039   CallLoweringInfo CLI;
01040   CLI.setCallee(RetTy, FuncTy, CI->getCalledValue(), std::move(Args), CS)
01041       .setTailCall(IsTailCall);
01042 
01043   return lowerCallTo(CLI);
01044 }
01045 
01046 bool FastISel::selectCall(const User *I) {
01047   const CallInst *Call = cast<CallInst>(I);
01048 
01049   // Handle simple inline asms.
01050   if (const InlineAsm *IA = dyn_cast<InlineAsm>(Call->getCalledValue())) {
01051     // If the inline asm has side effects, then make sure that no local value
01052     // lives across by flushing the local value map.
01053     if (IA->hasSideEffects())
01054       flushLocalValueMap();
01055 
01056     // Don't attempt to handle constraints.
01057     if (!IA->getConstraintString().empty())
01058       return false;
01059 
01060     unsigned ExtraInfo = 0;
01061     if (IA->hasSideEffects())
01062       ExtraInfo |= InlineAsm::Extra_HasSideEffects;
01063     if (IA->isAlignStack())
01064       ExtraInfo |= InlineAsm::Extra_IsAlignStack;
01065 
01066     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01067             TII.get(TargetOpcode::INLINEASM))
01068         .addExternalSymbol(IA->getAsmString().c_str())
01069         .addImm(ExtraInfo);
01070     return true;
01071   }
01072 
01073   MachineModuleInfo &MMI = FuncInfo.MF->getMMI();
01074   ComputeUsesVAFloatArgument(*Call, &MMI);
01075 
01076   // Handle intrinsic function calls.
01077   if (const auto *II = dyn_cast<IntrinsicInst>(Call))
01078     return selectIntrinsicCall(II);
01079 
01080   // Usually, it does not make sense to initialize a value,
01081   // make an unrelated function call and use the value, because
01082   // it tends to be spilled on the stack. So, we move the pointer
01083   // to the last local value to the beginning of the block, so that
01084   // all the values which have already been materialized,
01085   // appear after the call. It also makes sense to skip intrinsics
01086   // since they tend to be inlined.
01087   flushLocalValueMap();
01088 
01089   return lowerCall(Call);
01090 }
01091 
01092 bool FastISel::selectIntrinsicCall(const IntrinsicInst *II) {
01093   switch (II->getIntrinsicID()) {
01094   default:
01095     break;
01096   // At -O0 we don't care about the lifetime intrinsics.
01097   case Intrinsic::lifetime_start:
01098   case Intrinsic::lifetime_end:
01099   // The donothing intrinsic does, well, nothing.
01100   case Intrinsic::donothing:
01101     return true;
01102   case Intrinsic::dbg_declare: {
01103     const DbgDeclareInst *DI = cast<DbgDeclareInst>(II);
01104     assert(DI->getVariable() && "Missing variable");
01105     if (!FuncInfo.MF->getMMI().hasDebugInfo()) {
01106       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
01107       return true;
01108     }
01109 
01110     const Value *Address = DI->getAddress();
01111     if (!Address || isa<UndefValue>(Address)) {
01112       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
01113       return true;
01114     }
01115 
01116     unsigned Offset = 0;
01117     Optional<MachineOperand> Op;
01118     if (const auto *Arg = dyn_cast<Argument>(Address))
01119       // Some arguments' frame index is recorded during argument lowering.
01120       Offset = FuncInfo.getArgumentFrameIndex(Arg);
01121     if (Offset)
01122       Op = MachineOperand::CreateFI(Offset);
01123     if (!Op)
01124       if (unsigned Reg = lookUpRegForValue(Address))
01125         Op = MachineOperand::CreateReg(Reg, false);
01126 
01127     // If we have a VLA that has a "use" in a metadata node that's then used
01128     // here but it has no other uses, then we have a problem. E.g.,
01129     //
01130     //   int foo (const int *x) {
01131     //     char a[*x];
01132     //     return 0;
01133     //   }
01134     //
01135     // If we assign 'a' a vreg and fast isel later on has to use the selection
01136     // DAG isel, it will want to copy the value to the vreg. However, there are
01137     // no uses, which goes counter to what selection DAG isel expects.
01138     if (!Op && !Address->use_empty() && isa<Instruction>(Address) &&
01139         (!isa<AllocaInst>(Address) ||
01140          !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(Address))))
01141       Op = MachineOperand::CreateReg(FuncInfo.InitializeRegForValue(Address),
01142                                      false);
01143 
01144     if (Op) {
01145       assert(DI->getVariable()->isValidLocationForIntrinsic(DbgLoc) &&
01146              "Expected inlined-at fields to agree");
01147       if (Op->isReg()) {
01148         Op->setIsDebug(true);
01149         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01150                 TII.get(TargetOpcode::DBG_VALUE), false, Op->getReg(), 0,
01151                 DI->getVariable(), DI->getExpression());
01152       } else
01153         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01154                 TII.get(TargetOpcode::DBG_VALUE))
01155             .addOperand(*Op)
01156             .addImm(0)
01157             .addMetadata(DI->getVariable())
01158             .addMetadata(DI->getExpression());
01159     } else {
01160       // We can't yet handle anything else here because it would require
01161       // generating code, thus altering codegen because of debug info.
01162       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
01163     }
01164     return true;
01165   }
01166   case Intrinsic::dbg_value: {
01167     // This form of DBG_VALUE is target-independent.
01168     const DbgValueInst *DI = cast<DbgValueInst>(II);
01169     const MCInstrDesc &II = TII.get(TargetOpcode::DBG_VALUE);
01170     const Value *V = DI->getValue();
01171     assert(DI->getVariable()->isValidLocationForIntrinsic(DbgLoc) &&
01172            "Expected inlined-at fields to agree");
01173     if (!V) {
01174       // Currently the optimizer can produce this; insert an undef to
01175       // help debugging.  Probably the optimizer should not do this.
01176       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
01177           .addReg(0U)
01178           .addImm(DI->getOffset())
01179           .addMetadata(DI->getVariable())
01180           .addMetadata(DI->getExpression());
01181     } else if (const auto *CI = dyn_cast<ConstantInt>(V)) {
01182       if (CI->getBitWidth() > 64)
01183         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
01184             .addCImm(CI)
01185             .addImm(DI->getOffset())
01186             .addMetadata(DI->getVariable())
01187             .addMetadata(DI->getExpression());
01188       else
01189         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
01190             .addImm(CI->getZExtValue())
01191             .addImm(DI->getOffset())
01192             .addMetadata(DI->getVariable())
01193             .addMetadata(DI->getExpression());
01194     } else if (const auto *CF = dyn_cast<ConstantFP>(V)) {
01195       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
01196           .addFPImm(CF)
01197           .addImm(DI->getOffset())
01198           .addMetadata(DI->getVariable())
01199           .addMetadata(DI->getExpression());
01200     } else if (unsigned Reg = lookUpRegForValue(V)) {
01201       // FIXME: This does not handle register-indirect values at offset 0.
01202       bool IsIndirect = DI->getOffset() != 0;
01203       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, IsIndirect, Reg,
01204               DI->getOffset(), DI->getVariable(), DI->getExpression());
01205     } else {
01206       // We can't yet handle anything else here because it would require
01207       // generating code, thus altering codegen because of debug info.
01208       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
01209     }
01210     return true;
01211   }
01212   case Intrinsic::objectsize: {
01213     ConstantInt *CI = cast<ConstantInt>(II->getArgOperand(1));
01214     unsigned long long Res = CI->isZero() ? -1ULL : 0;
01215     Constant *ResCI = ConstantInt::get(II->getType(), Res);
01216     unsigned ResultReg = getRegForValue(ResCI);
01217     if (!ResultReg)
01218       return false;
01219     updateValueMap(II, ResultReg);
01220     return true;
01221   }
01222   case Intrinsic::expect: {
01223     unsigned ResultReg = getRegForValue(II->getArgOperand(0));
01224     if (!ResultReg)
01225       return false;
01226     updateValueMap(II, ResultReg);
01227     return true;
01228   }
01229   case Intrinsic::experimental_stackmap:
01230     return selectStackmap(II);
01231   case Intrinsic::experimental_patchpoint_void:
01232   case Intrinsic::experimental_patchpoint_i64:
01233     return selectPatchpoint(II);
01234   }
01235 
01236   return fastLowerIntrinsicCall(II);
01237 }
01238 
01239 bool FastISel::selectCast(const User *I, unsigned Opcode) {
01240   EVT SrcVT = TLI.getValueType(DL, I->getOperand(0)->getType());
01241   EVT DstVT = TLI.getValueType(DL, I->getType());
01242 
01243   if (SrcVT == MVT::Other || !SrcVT.isSimple() || DstVT == MVT::Other ||
01244       !DstVT.isSimple())
01245     // Unhandled type. Halt "fast" selection and bail.
01246     return false;
01247 
01248   // Check if the destination type is legal.
01249   if (!TLI.isTypeLegal(DstVT))
01250     return false;
01251 
01252   // Check if the source operand is legal.
01253   if (!TLI.isTypeLegal(SrcVT))
01254     return false;
01255 
01256   unsigned InputReg = getRegForValue(I->getOperand(0));
01257   if (!InputReg)
01258     // Unhandled operand.  Halt "fast" selection and bail.
01259     return false;
01260 
01261   bool InputRegIsKill = hasTrivialKill(I->getOperand(0));
01262 
01263   unsigned ResultReg = fastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(),
01264                                   Opcode, InputReg, InputRegIsKill);
01265   if (!ResultReg)
01266     return false;
01267 
01268   updateValueMap(I, ResultReg);
01269   return true;
01270 }
01271 
01272 bool FastISel::selectBitCast(const User *I) {
01273   // If the bitcast doesn't change the type, just use the operand value.
01274   if (I->getType() == I->getOperand(0)->getType()) {
01275     unsigned Reg = getRegForValue(I->getOperand(0));
01276     if (!Reg)
01277       return false;
01278     updateValueMap(I, Reg);
01279     return true;
01280   }
01281 
01282   // Bitcasts of other values become reg-reg copies or BITCAST operators.
01283   EVT SrcEVT = TLI.getValueType(DL, I->getOperand(0)->getType());
01284   EVT DstEVT = TLI.getValueType(DL, I->getType());
01285   if (SrcEVT == MVT::Other || DstEVT == MVT::Other ||
01286       !TLI.isTypeLegal(SrcEVT) || !TLI.isTypeLegal(DstEVT))
01287     // Unhandled type. Halt "fast" selection and bail.
01288     return false;
01289 
01290   MVT SrcVT = SrcEVT.getSimpleVT();
01291   MVT DstVT = DstEVT.getSimpleVT();
01292   unsigned Op0 = getRegForValue(I->getOperand(0));
01293   if (!Op0) // Unhandled operand. Halt "fast" selection and bail.
01294     return false;
01295   bool Op0IsKill = hasTrivialKill(I->getOperand(0));
01296 
01297   // First, try to perform the bitcast by inserting a reg-reg copy.
01298   unsigned ResultReg = 0;
01299   if (SrcVT == DstVT) {
01300     const TargetRegisterClass *SrcClass = TLI.getRegClassFor(SrcVT);
01301     const TargetRegisterClass *DstClass = TLI.getRegClassFor(DstVT);
01302     // Don't attempt a cross-class copy. It will likely fail.
01303     if (SrcClass == DstClass) {
01304       ResultReg = createResultReg(DstClass);
01305       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01306               TII.get(TargetOpcode::COPY), ResultReg).addReg(Op0);
01307     }
01308   }
01309 
01310   // If the reg-reg copy failed, select a BITCAST opcode.
01311   if (!ResultReg)
01312     ResultReg = fastEmit_r(SrcVT, DstVT, ISD::BITCAST, Op0, Op0IsKill);
01313 
01314   if (!ResultReg)
01315     return false;
01316 
01317   updateValueMap(I, ResultReg);
01318   return true;
01319 }
01320 
01321 // Remove local value instructions starting from the instruction after
01322 // SavedLastLocalValue to the current function insert point.
01323 void FastISel::removeDeadLocalValueCode(MachineInstr *SavedLastLocalValue)
01324 {
01325   MachineInstr *CurLastLocalValue = getLastLocalValue();
01326   if (CurLastLocalValue != SavedLastLocalValue) {
01327     // Find the first local value instruction to be deleted. 
01328     // This is the instruction after SavedLastLocalValue if it is non-NULL.
01329     // Otherwise it's the first instruction in the block.
01330     MachineBasicBlock::iterator FirstDeadInst(SavedLastLocalValue);
01331     if (SavedLastLocalValue)
01332       ++FirstDeadInst;
01333     else
01334       FirstDeadInst = FuncInfo.MBB->getFirstNonPHI();
01335     setLastLocalValue(SavedLastLocalValue);
01336     removeDeadCode(FirstDeadInst, FuncInfo.InsertPt);
01337   }
01338 }
01339 
01340 bool FastISel::selectInstruction(const Instruction *I) {
01341   MachineInstr *SavedLastLocalValue = getLastLocalValue();
01342   // Just before the terminator instruction, insert instructions to
01343   // feed PHI nodes in successor blocks.
01344   if (isa<TerminatorInst>(I))
01345     if (!handlePHINodesInSuccessorBlocks(I->getParent())) {
01346       // PHI node handling may have generated local value instructions,
01347       // even though it failed to handle all PHI nodes.
01348       // We remove these instructions because SelectionDAGISel will generate 
01349       // them again.
01350       removeDeadLocalValueCode(SavedLastLocalValue);
01351       return false;
01352     }
01353 
01354   DbgLoc = I->getDebugLoc();
01355 
01356   SavedInsertPt = FuncInfo.InsertPt;
01357 
01358   if (const auto *Call = dyn_cast<CallInst>(I)) {
01359     const Function *F = Call->getCalledFunction();
01360     LibFunc::Func Func;
01361 
01362     // As a special case, don't handle calls to builtin library functions that
01363     // may be translated directly to target instructions.
01364     if (F && !F->hasLocalLinkage() && F->hasName() &&
01365         LibInfo->getLibFunc(F->getName(), Func) &&
01366         LibInfo->hasOptimizedCodeGen(Func))
01367       return false;
01368 
01369     // Don't handle Intrinsic::trap if a trap function is specified.
01370     if (F && F->getIntrinsicID() == Intrinsic::trap &&
01371         Call->hasFnAttr("trap-func-name"))
01372       return false;
01373   }
01374 
01375   // First, try doing target-independent selection.
01376   if (!SkipTargetIndependentISel) {
01377     if (selectOperator(I, I->getOpcode())) {
01378       ++NumFastIselSuccessIndependent;
01379       DbgLoc = DebugLoc();
01380       return true;
01381     }
01382     // Remove dead code.
01383     recomputeInsertPt();
01384     if (SavedInsertPt != FuncInfo.InsertPt)
01385       removeDeadCode(FuncInfo.InsertPt, SavedInsertPt);
01386     SavedInsertPt = FuncInfo.InsertPt;
01387   }
01388   // Next, try calling the target to attempt to handle the instruction.
01389   if (fastSelectInstruction(I)) {
01390     ++NumFastIselSuccessTarget;
01391     DbgLoc = DebugLoc();
01392     return true;
01393   }
01394   // Remove dead code.
01395   recomputeInsertPt();
01396   if (SavedInsertPt != FuncInfo.InsertPt)
01397     removeDeadCode(FuncInfo.InsertPt, SavedInsertPt);
01398 
01399   DbgLoc = DebugLoc();
01400   // Undo phi node updates, because they will be added again by SelectionDAG.
01401   if (isa<TerminatorInst>(I)) {
01402     // PHI node handling may have generated local value instructions. 
01403     // We remove them because SelectionDAGISel will generate them again.
01404     removeDeadLocalValueCode(SavedLastLocalValue);
01405     FuncInfo.PHINodesToUpdate.resize(FuncInfo.OrigNumPHINodesToUpdate);
01406   }
01407   return false;
01408 }
01409 
01410 /// Emit an unconditional branch to the given block, unless it is the immediate
01411 /// (fall-through) successor, and update the CFG.
01412 void FastISel::fastEmitBranch(MachineBasicBlock *MSucc, DebugLoc DbgLoc) {
01413   if (FuncInfo.MBB->getBasicBlock()->size() > 1 &&
01414       FuncInfo.MBB->isLayoutSuccessor(MSucc)) {
01415     // For more accurate line information if this is the only instruction
01416     // in the block then emit it, otherwise we have the unconditional
01417     // fall-through case, which needs no instructions.
01418   } else {
01419     // The unconditional branch case.
01420     TII.InsertBranch(*FuncInfo.MBB, MSucc, nullptr,
01421                      SmallVector<MachineOperand, 0>(), DbgLoc);
01422   }
01423   if (FuncInfo.BPI) {
01424     auto BranchProbability = FuncInfo.BPI->getEdgeProbability(
01425         FuncInfo.MBB->getBasicBlock(), MSucc->getBasicBlock());
01426     FuncInfo.MBB->addSuccessor(MSucc, BranchProbability);
01427   } else
01428     FuncInfo.MBB->addSuccessorWithoutProb(MSucc);
01429 }
01430 
01431 void FastISel::finishCondBranch(const BasicBlock *BranchBB,
01432                                 MachineBasicBlock *TrueMBB,
01433                                 MachineBasicBlock *FalseMBB) {
01434   // Add TrueMBB as successor unless it is equal to the FalseMBB: This can
01435   // happen in degenerate IR and MachineIR forbids to have a block twice in the
01436   // successor/predecessor lists.
01437   if (TrueMBB != FalseMBB) {
01438     if (FuncInfo.BPI) {
01439       auto BranchProbability =
01440           FuncInfo.BPI->getEdgeProbability(BranchBB, TrueMBB->getBasicBlock());
01441       FuncInfo.MBB->addSuccessor(TrueMBB, BranchProbability);
01442     } else
01443       FuncInfo.MBB->addSuccessorWithoutProb(TrueMBB);
01444   }
01445 
01446   fastEmitBranch(FalseMBB, DbgLoc);
01447 }
01448 
01449 /// Emit an FNeg operation.
01450 bool FastISel::selectFNeg(const User *I) {
01451   unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I));
01452   if (!OpReg)
01453     return false;
01454   bool OpRegIsKill = hasTrivialKill(I);
01455 
01456   // If the target has ISD::FNEG, use it.
01457   EVT VT = TLI.getValueType(DL, I->getType());
01458   unsigned ResultReg = fastEmit_r(VT.getSimpleVT(), VT.getSimpleVT(), ISD::FNEG,
01459                                   OpReg, OpRegIsKill);
01460   if (ResultReg) {
01461     updateValueMap(I, ResultReg);
01462     return true;
01463   }
01464 
01465   // Bitcast the value to integer, twiddle the sign bit with xor,
01466   // and then bitcast it back to floating-point.
01467   if (VT.getSizeInBits() > 64)
01468     return false;
01469   EVT IntVT = EVT::getIntegerVT(I->getContext(), VT.getSizeInBits());
01470   if (!TLI.isTypeLegal(IntVT))
01471     return false;
01472 
01473   unsigned IntReg = fastEmit_r(VT.getSimpleVT(), IntVT.getSimpleVT(),
01474                                ISD::BITCAST, OpReg, OpRegIsKill);
01475   if (!IntReg)
01476     return false;
01477 
01478   unsigned IntResultReg = fastEmit_ri_(
01479       IntVT.getSimpleVT(), ISD::XOR, IntReg, /*IsKill=*/true,
01480       UINT64_C(1) << (VT.getSizeInBits() - 1), IntVT.getSimpleVT());
01481   if (!IntResultReg)
01482     return false;
01483 
01484   ResultReg = fastEmit_r(IntVT.getSimpleVT(), VT.getSimpleVT(), ISD::BITCAST,
01485                          IntResultReg, /*IsKill=*/true);
01486   if (!ResultReg)
01487     return false;
01488 
01489   updateValueMap(I, ResultReg);
01490   return true;
01491 }
01492 
01493 bool FastISel::selectExtractValue(const User *U) {
01494   const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(U);
01495   if (!EVI)
01496     return false;
01497 
01498   // Make sure we only try to handle extracts with a legal result.  But also
01499   // allow i1 because it's easy.
01500   EVT RealVT = TLI.getValueType(DL, EVI->getType(), /*AllowUnknown=*/true);
01501   if (!RealVT.isSimple())
01502     return false;
01503   MVT VT = RealVT.getSimpleVT();
01504   if (!TLI.isTypeLegal(VT) && VT != MVT::i1)
01505     return false;
01506 
01507   const Value *Op0 = EVI->getOperand(0);
01508   Type *AggTy = Op0->getType();
01509 
01510   // Get the base result register.
01511   unsigned ResultReg;
01512   DenseMap<const Value *, unsigned>::iterator I = FuncInfo.ValueMap.find(Op0);
01513   if (I != FuncInfo.ValueMap.end())
01514     ResultReg = I->second;
01515   else if (isa<Instruction>(Op0))
01516     ResultReg = FuncInfo.InitializeRegForValue(Op0);
01517   else
01518     return false; // fast-isel can't handle aggregate constants at the moment
01519 
01520   // Get the actual result register, which is an offset from the base register.
01521   unsigned VTIndex = ComputeLinearIndex(AggTy, EVI->getIndices());
01522 
01523   SmallVector<EVT, 4> AggValueVTs;
01524   ComputeValueVTs(TLI, DL, AggTy, AggValueVTs);
01525 
01526   for (unsigned i = 0; i < VTIndex; i++)
01527     ResultReg += TLI.getNumRegisters(FuncInfo.Fn->getContext(), AggValueVTs[i]);
01528 
01529   updateValueMap(EVI, ResultReg);
01530   return true;
01531 }
01532 
01533 bool FastISel::selectOperator(const User *I, unsigned Opcode) {
01534   switch (Opcode) {
01535   case Instruction::Add:
01536     return selectBinaryOp(I, ISD::ADD);
01537   case Instruction::FAdd:
01538     return selectBinaryOp(I, ISD::FADD);
01539   case Instruction::Sub:
01540     return selectBinaryOp(I, ISD::SUB);
01541   case Instruction::FSub:
01542     // FNeg is currently represented in LLVM IR as a special case of FSub.
01543     if (BinaryOperator::isFNeg(I))
01544       return selectFNeg(I);
01545     return selectBinaryOp(I, ISD::FSUB);
01546   case Instruction::Mul:
01547     return selectBinaryOp(I, ISD::MUL);
01548   case Instruction::FMul:
01549     return selectBinaryOp(I, ISD::FMUL);
01550   case Instruction::SDiv:
01551     return selectBinaryOp(I, ISD::SDIV);
01552   case Instruction::UDiv:
01553     return selectBinaryOp(I, ISD::UDIV);
01554   case Instruction::FDiv:
01555     return selectBinaryOp(I, ISD::FDIV);
01556   case Instruction::SRem:
01557     return selectBinaryOp(I, ISD::SREM);
01558   case Instruction::URem:
01559     return selectBinaryOp(I, ISD::UREM);
01560   case Instruction::FRem:
01561     return selectBinaryOp(I, ISD::FREM);
01562   case Instruction::Shl:
01563     return selectBinaryOp(I, ISD::SHL);
01564   case Instruction::LShr:
01565     return selectBinaryOp(I, ISD::SRL);
01566   case Instruction::AShr:
01567     return selectBinaryOp(I, ISD::SRA);
01568   case Instruction::And:
01569     return selectBinaryOp(I, ISD::AND);
01570   case Instruction::Or:
01571     return selectBinaryOp(I, ISD::OR);
01572   case Instruction::Xor:
01573     return selectBinaryOp(I, ISD::XOR);
01574 
01575   case Instruction::GetElementPtr:
01576     return selectGetElementPtr(I);
01577 
01578   case Instruction::Br: {
01579     const BranchInst *BI = cast<BranchInst>(I);
01580 
01581     if (BI->isUnconditional()) {
01582       const BasicBlock *LLVMSucc = BI->getSuccessor(0);
01583       MachineBasicBlock *MSucc = FuncInfo.MBBMap[LLVMSucc];
01584       fastEmitBranch(MSucc, BI->getDebugLoc());
01585       return true;
01586     }
01587 
01588     // Conditional branches are not handed yet.
01589     // Halt "fast" selection and bail.
01590     return false;
01591   }
01592 
01593   case Instruction::Unreachable:
01594     if (TM.Options.TrapUnreachable)
01595       return fastEmit_(MVT::Other, MVT::Other, ISD::TRAP) != 0;
01596     else
01597       return true;
01598 
01599   case Instruction::Alloca:
01600     // FunctionLowering has the static-sized case covered.
01601     if (FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(I)))
01602       return true;
01603 
01604     // Dynamic-sized alloca is not handled yet.
01605     return false;
01606 
01607   case Instruction::Call:
01608     return selectCall(I);
01609 
01610   case Instruction::BitCast:
01611     return selectBitCast(I);
01612 
01613   case Instruction::FPToSI:
01614     return selectCast(I, ISD::FP_TO_SINT);
01615   case Instruction::ZExt:
01616     return selectCast(I, ISD::ZERO_EXTEND);
01617   case Instruction::SExt:
01618     return selectCast(I, ISD::SIGN_EXTEND);
01619   case Instruction::Trunc:
01620     return selectCast(I, ISD::TRUNCATE);
01621   case Instruction::SIToFP:
01622     return selectCast(I, ISD::SINT_TO_FP);
01623 
01624   case Instruction::IntToPtr: // Deliberate fall-through.
01625   case Instruction::PtrToInt: {
01626     EVT SrcVT = TLI.getValueType(DL, I->getOperand(0)->getType());
01627     EVT DstVT = TLI.getValueType(DL, I->getType());
01628     if (DstVT.bitsGT(SrcVT))
01629       return selectCast(I, ISD::ZERO_EXTEND);
01630     if (DstVT.bitsLT(SrcVT))
01631       return selectCast(I, ISD::TRUNCATE);
01632     unsigned Reg = getRegForValue(I->getOperand(0));
01633     if (!Reg)
01634       return false;
01635     updateValueMap(I, Reg);
01636     return true;
01637   }
01638 
01639   case Instruction::ExtractValue:
01640     return selectExtractValue(I);
01641 
01642   case Instruction::PHI:
01643     llvm_unreachable("FastISel shouldn't visit PHI nodes!");
01644 
01645   default:
01646     // Unhandled instruction. Halt "fast" selection and bail.
01647     return false;
01648   }
01649 }
01650 
01651 FastISel::FastISel(FunctionLoweringInfo &FuncInfo,
01652                    const TargetLibraryInfo *LibInfo,
01653                    bool SkipTargetIndependentISel)
01654     : FuncInfo(FuncInfo), MF(FuncInfo.MF), MRI(FuncInfo.MF->getRegInfo()),
01655       MFI(*FuncInfo.MF->getFrameInfo()), MCP(*FuncInfo.MF->getConstantPool()),
01656       TM(FuncInfo.MF->getTarget()), DL(MF->getDataLayout()),
01657       TII(*MF->getSubtarget().getInstrInfo()),
01658       TLI(*MF->getSubtarget().getTargetLowering()),
01659       TRI(*MF->getSubtarget().getRegisterInfo()), LibInfo(LibInfo),
01660       SkipTargetIndependentISel(SkipTargetIndependentISel) {}
01661 
01662 FastISel::~FastISel() {}
01663 
01664 bool FastISel::fastLowerArguments() { return false; }
01665 
01666 bool FastISel::fastLowerCall(CallLoweringInfo & /*CLI*/) { return false; }
01667 
01668 bool FastISel::fastLowerIntrinsicCall(const IntrinsicInst * /*II*/) {
01669   return false;
01670 }
01671 
01672 unsigned FastISel::fastEmit_(MVT, MVT, unsigned) { return 0; }
01673 
01674 unsigned FastISel::fastEmit_r(MVT, MVT, unsigned, unsigned /*Op0*/,
01675                               bool /*Op0IsKill*/) {
01676   return 0;
01677 }
01678 
01679 unsigned FastISel::fastEmit_rr(MVT, MVT, unsigned, unsigned /*Op0*/,
01680                                bool /*Op0IsKill*/, unsigned /*Op1*/,
01681                                bool /*Op1IsKill*/) {
01682   return 0;
01683 }
01684 
01685 unsigned FastISel::fastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) {
01686   return 0;
01687 }
01688 
01689 unsigned FastISel::fastEmit_f(MVT, MVT, unsigned,
01690                               const ConstantFP * /*FPImm*/) {
01691   return 0;
01692 }
01693 
01694 unsigned FastISel::fastEmit_ri(MVT, MVT, unsigned, unsigned /*Op0*/,
01695                                bool /*Op0IsKill*/, uint64_t /*Imm*/) {
01696   return 0;
01697 }
01698 
01699 unsigned FastISel::fastEmit_rf(MVT, MVT, unsigned, unsigned /*Op0*/,
01700                                bool /*Op0IsKill*/,
01701                                const ConstantFP * /*FPImm*/) {
01702   return 0;
01703 }
01704 
01705 unsigned FastISel::fastEmit_rri(MVT, MVT, unsigned, unsigned /*Op0*/,
01706                                 bool /*Op0IsKill*/, unsigned /*Op1*/,
01707                                 bool /*Op1IsKill*/, uint64_t /*Imm*/) {
01708   return 0;
01709 }
01710 
01711 /// This method is a wrapper of fastEmit_ri. It first tries to emit an
01712 /// instruction with an immediate operand using fastEmit_ri.
01713 /// If that fails, it materializes the immediate into a register and try
01714 /// fastEmit_rr instead.
01715 unsigned FastISel::fastEmit_ri_(MVT VT, unsigned Opcode, unsigned Op0,
01716                                 bool Op0IsKill, uint64_t Imm, MVT ImmType) {
01717   // If this is a multiply by a power of two, emit this as a shift left.
01718   if (Opcode == ISD::MUL && isPowerOf2_64(Imm)) {
01719     Opcode = ISD::SHL;
01720     Imm = Log2_64(Imm);
01721   } else if (Opcode == ISD::UDIV && isPowerOf2_64(Imm)) {
01722     // div x, 8 -> srl x, 3
01723     Opcode = ISD::SRL;
01724     Imm = Log2_64(Imm);
01725   }
01726 
01727   // Horrible hack (to be removed), check to make sure shift amounts are
01728   // in-range.
01729   if ((Opcode == ISD::SHL || Opcode == ISD::SRA || Opcode == ISD::SRL) &&
01730       Imm >= VT.getSizeInBits())
01731     return 0;
01732 
01733   // First check if immediate type is legal. If not, we can't use the ri form.
01734   unsigned ResultReg = fastEmit_ri(VT, VT, Opcode, Op0, Op0IsKill, Imm);
01735   if (ResultReg)
01736     return ResultReg;
01737   unsigned MaterialReg = fastEmit_i(ImmType, ImmType, ISD::Constant, Imm);
01738   bool IsImmKill = true;
01739   if (!MaterialReg) {
01740     // This is a bit ugly/slow, but failing here means falling out of
01741     // fast-isel, which would be very slow.
01742     IntegerType *ITy =
01743         IntegerType::get(FuncInfo.Fn->getContext(), VT.getSizeInBits());
01744     MaterialReg = getRegForValue(ConstantInt::get(ITy, Imm));
01745     if (!MaterialReg)
01746       return 0;
01747     // FIXME: If the materialized register here has no uses yet then this
01748     // will be the first use and we should be able to mark it as killed.
01749     // However, the local value area for materialising constant expressions
01750     // grows down, not up, which means that any constant expressions we generate
01751     // later which also use 'Imm' could be after this instruction and therefore
01752     // after this kill.
01753     IsImmKill = false;
01754   }
01755   return fastEmit_rr(VT, VT, Opcode, Op0, Op0IsKill, MaterialReg, IsImmKill);
01756 }
01757 
01758 unsigned FastISel::createResultReg(const TargetRegisterClass *RC) {
01759   return MRI.createVirtualRegister(RC);
01760 }
01761 
01762 unsigned FastISel::constrainOperandRegClass(const MCInstrDesc &II, unsigned Op,
01763                                             unsigned OpNum) {
01764   if (TargetRegisterInfo::isVirtualRegister(Op)) {
01765     const TargetRegisterClass *RegClass =
01766         TII.getRegClass(II, OpNum, &TRI, *FuncInfo.MF);
01767     if (!MRI.constrainRegClass(Op, RegClass)) {
01768       // If it's not legal to COPY between the register classes, something
01769       // has gone very wrong before we got here.
01770       unsigned NewOp = createResultReg(RegClass);
01771       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01772               TII.get(TargetOpcode::COPY), NewOp).addReg(Op);
01773       return NewOp;
01774     }
01775   }
01776   return Op;
01777 }
01778 
01779 unsigned FastISel::fastEmitInst_(unsigned MachineInstOpcode,
01780                                  const TargetRegisterClass *RC) {
01781   unsigned ResultReg = createResultReg(RC);
01782   const MCInstrDesc &II = TII.get(MachineInstOpcode);
01783 
01784   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg);
01785   return ResultReg;
01786 }
01787 
01788 unsigned FastISel::fastEmitInst_r(unsigned MachineInstOpcode,
01789                                   const TargetRegisterClass *RC, unsigned Op0,
01790                                   bool Op0IsKill) {
01791   const MCInstrDesc &II = TII.get(MachineInstOpcode);
01792 
01793   unsigned ResultReg = createResultReg(RC);
01794   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
01795 
01796   if (II.getNumDefs() >= 1)
01797     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
01798         .addReg(Op0, getKillRegState(Op0IsKill));
01799   else {
01800     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
01801         .addReg(Op0, getKillRegState(Op0IsKill));
01802     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01803             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
01804   }
01805 
01806   return ResultReg;
01807 }
01808 
01809 unsigned FastISel::fastEmitInst_rr(unsigned MachineInstOpcode,
01810                                    const TargetRegisterClass *RC, unsigned Op0,
01811                                    bool Op0IsKill, unsigned Op1,
01812                                    bool Op1IsKill) {
01813   const MCInstrDesc &II = TII.get(MachineInstOpcode);
01814 
01815   unsigned ResultReg = createResultReg(RC);
01816   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
01817   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
01818 
01819   if (II.getNumDefs() >= 1)
01820     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
01821         .addReg(Op0, getKillRegState(Op0IsKill))
01822         .addReg(Op1, getKillRegState(Op1IsKill));
01823   else {
01824     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
01825         .addReg(Op0, getKillRegState(Op0IsKill))
01826         .addReg(Op1, getKillRegState(Op1IsKill));
01827     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01828             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
01829   }
01830   return ResultReg;
01831 }
01832 
01833 unsigned FastISel::fastEmitInst_rrr(unsigned MachineInstOpcode,
01834                                     const TargetRegisterClass *RC, unsigned Op0,
01835                                     bool Op0IsKill, unsigned Op1,
01836                                     bool Op1IsKill, unsigned Op2,
01837                                     bool Op2IsKill) {
01838   const MCInstrDesc &II = TII.get(MachineInstOpcode);
01839 
01840   unsigned ResultReg = createResultReg(RC);
01841   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
01842   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
01843   Op2 = constrainOperandRegClass(II, Op2, II.getNumDefs() + 2);
01844 
01845   if (II.getNumDefs() >= 1)
01846     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
01847         .addReg(Op0, getKillRegState(Op0IsKill))
01848         .addReg(Op1, getKillRegState(Op1IsKill))
01849         .addReg(Op2, getKillRegState(Op2IsKill));
01850   else {
01851     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
01852         .addReg(Op0, getKillRegState(Op0IsKill))
01853         .addReg(Op1, getKillRegState(Op1IsKill))
01854         .addReg(Op2, getKillRegState(Op2IsKill));
01855     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01856             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
01857   }
01858   return ResultReg;
01859 }
01860 
01861 unsigned FastISel::fastEmitInst_ri(unsigned MachineInstOpcode,
01862                                    const TargetRegisterClass *RC, unsigned Op0,
01863                                    bool Op0IsKill, uint64_t Imm) {
01864   const MCInstrDesc &II = TII.get(MachineInstOpcode);
01865 
01866   unsigned ResultReg = createResultReg(RC);
01867   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
01868 
01869   if (II.getNumDefs() >= 1)
01870     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
01871         .addReg(Op0, getKillRegState(Op0IsKill))
01872         .addImm(Imm);
01873   else {
01874     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
01875         .addReg(Op0, getKillRegState(Op0IsKill))
01876         .addImm(Imm);
01877     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01878             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
01879   }
01880   return ResultReg;
01881 }
01882 
01883 unsigned FastISel::fastEmitInst_rii(unsigned MachineInstOpcode,
01884                                     const TargetRegisterClass *RC, unsigned Op0,
01885                                     bool Op0IsKill, uint64_t Imm1,
01886                                     uint64_t Imm2) {
01887   const MCInstrDesc &II = TII.get(MachineInstOpcode);
01888 
01889   unsigned ResultReg = createResultReg(RC);
01890   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
01891 
01892   if (II.getNumDefs() >= 1)
01893     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
01894         .addReg(Op0, getKillRegState(Op0IsKill))
01895         .addImm(Imm1)
01896         .addImm(Imm2);
01897   else {
01898     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
01899         .addReg(Op0, getKillRegState(Op0IsKill))
01900         .addImm(Imm1)
01901         .addImm(Imm2);
01902     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01903             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
01904   }
01905   return ResultReg;
01906 }
01907 
01908 unsigned FastISel::fastEmitInst_f(unsigned MachineInstOpcode,
01909                                   const TargetRegisterClass *RC,
01910                                   const ConstantFP *FPImm) {
01911   const MCInstrDesc &II = TII.get(MachineInstOpcode);
01912 
01913   unsigned ResultReg = createResultReg(RC);
01914 
01915   if (II.getNumDefs() >= 1)
01916     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
01917         .addFPImm(FPImm);
01918   else {
01919     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
01920         .addFPImm(FPImm);
01921     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01922             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
01923   }
01924   return ResultReg;
01925 }
01926 
01927 unsigned FastISel::fastEmitInst_rri(unsigned MachineInstOpcode,
01928                                     const TargetRegisterClass *RC, unsigned Op0,
01929                                     bool Op0IsKill, unsigned Op1,
01930                                     bool Op1IsKill, uint64_t Imm) {
01931   const MCInstrDesc &II = TII.get(MachineInstOpcode);
01932 
01933   unsigned ResultReg = createResultReg(RC);
01934   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
01935   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
01936 
01937   if (II.getNumDefs() >= 1)
01938     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
01939         .addReg(Op0, getKillRegState(Op0IsKill))
01940         .addReg(Op1, getKillRegState(Op1IsKill))
01941         .addImm(Imm);
01942   else {
01943     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
01944         .addReg(Op0, getKillRegState(Op0IsKill))
01945         .addReg(Op1, getKillRegState(Op1IsKill))
01946         .addImm(Imm);
01947     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01948             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
01949   }
01950   return ResultReg;
01951 }
01952 
01953 unsigned FastISel::fastEmitInst_i(unsigned MachineInstOpcode,
01954                                   const TargetRegisterClass *RC, uint64_t Imm) {
01955   unsigned ResultReg = createResultReg(RC);
01956   const MCInstrDesc &II = TII.get(MachineInstOpcode);
01957 
01958   if (II.getNumDefs() >= 1)
01959     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
01960         .addImm(Imm);
01961   else {
01962     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II).addImm(Imm);
01963     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01964             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
01965   }
01966   return ResultReg;
01967 }
01968 
01969 unsigned FastISel::fastEmitInst_extractsubreg(MVT RetVT, unsigned Op0,
01970                                               bool Op0IsKill, uint32_t Idx) {
01971   unsigned ResultReg = createResultReg(TLI.getRegClassFor(RetVT));
01972   assert(TargetRegisterInfo::isVirtualRegister(Op0) &&
01973          "Cannot yet extract from physregs");
01974   const TargetRegisterClass *RC = MRI.getRegClass(Op0);
01975   MRI.constrainRegClass(Op0, TRI.getSubClassWithSubReg(RC, Idx));
01976   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(TargetOpcode::COPY),
01977           ResultReg).addReg(Op0, getKillRegState(Op0IsKill), Idx);
01978   return ResultReg;
01979 }
01980 
01981 /// Emit MachineInstrs to compute the value of Op with all but the least
01982 /// significant bit set to zero.
01983 unsigned FastISel::fastEmitZExtFromI1(MVT VT, unsigned Op0, bool Op0IsKill) {
01984   return fastEmit_ri(VT, VT, ISD::AND, Op0, Op0IsKill, 1);
01985 }
01986 
01987 /// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks.
01988 /// Emit code to ensure constants are copied into registers when needed.
01989 /// Remember the virtual registers that need to be added to the Machine PHI
01990 /// nodes as input.  We cannot just directly add them, because expansion
01991 /// might result in multiple MBB's for one BB.  As such, the start of the
01992 /// BB might correspond to a different MBB than the end.
01993 bool FastISel::handlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) {
01994   const TerminatorInst *TI = LLVMBB->getTerminator();
01995 
01996   SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled;
01997   FuncInfo.OrigNumPHINodesToUpdate = FuncInfo.PHINodesToUpdate.size();
01998 
01999   // Check successor nodes' PHI nodes that expect a constant to be available
02000   // from this block.
02001   for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
02002     const BasicBlock *SuccBB = TI->getSuccessor(succ);
02003     if (!isa<PHINode>(SuccBB->begin()))
02004       continue;
02005     MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB];
02006 
02007     // If this terminator has multiple identical successors (common for
02008     // switches), only handle each succ once.
02009     if (!SuccsHandled.insert(SuccMBB).second)
02010       continue;
02011 
02012     MachineBasicBlock::iterator MBBI = SuccMBB->begin();
02013 
02014     // At this point we know that there is a 1-1 correspondence between LLVM PHI
02015     // nodes and Machine PHI nodes, but the incoming operands have not been
02016     // emitted yet.
02017     for (BasicBlock::const_iterator I = SuccBB->begin();
02018          const auto *PN = dyn_cast<PHINode>(I); ++I) {
02019 
02020       // Ignore dead phi's.
02021       if (PN->use_empty())
02022         continue;
02023 
02024       // Only handle legal types. Two interesting things to note here. First,
02025       // by bailing out early, we may leave behind some dead instructions,
02026       // since SelectionDAG's HandlePHINodesInSuccessorBlocks will insert its
02027       // own moves. Second, this check is necessary because FastISel doesn't
02028       // use CreateRegs to create registers, so it always creates
02029       // exactly one register for each non-void instruction.
02030       EVT VT = TLI.getValueType(DL, PN->getType(), /*AllowUnknown=*/true);
02031       if (VT == MVT::Other || !TLI.isTypeLegal(VT)) {
02032         // Handle integer promotions, though, because they're common and easy.
02033         if (!(VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16)) {
02034           FuncInfo.PHINodesToUpdate.resize(FuncInfo.OrigNumPHINodesToUpdate);
02035           return false;
02036         }
02037       }
02038 
02039       const Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB);
02040 
02041       // Set the DebugLoc for the copy. Prefer the location of the operand
02042       // if there is one; use the location of the PHI otherwise.
02043       DbgLoc = PN->getDebugLoc();
02044       if (const auto *Inst = dyn_cast<Instruction>(PHIOp))
02045         DbgLoc = Inst->getDebugLoc();
02046 
02047       unsigned Reg = getRegForValue(PHIOp);
02048       if (!Reg) {
02049         FuncInfo.PHINodesToUpdate.resize(FuncInfo.OrigNumPHINodesToUpdate);
02050         return false;
02051       }
02052       FuncInfo.PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg));
02053       DbgLoc = DebugLoc();
02054     }
02055   }
02056 
02057   return true;
02058 }
02059 
02060 bool FastISel::tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst) {
02061   assert(LI->hasOneUse() &&
02062          "tryToFoldLoad expected a LoadInst with a single use");
02063   // We know that the load has a single use, but don't know what it is.  If it
02064   // isn't one of the folded instructions, then we can't succeed here.  Handle
02065   // this by scanning the single-use users of the load until we get to FoldInst.
02066   unsigned MaxUsers = 6; // Don't scan down huge single-use chains of instrs.
02067 
02068   const Instruction *TheUser = LI->user_back();
02069   while (TheUser != FoldInst && // Scan up until we find FoldInst.
02070          // Stay in the right block.
02071          TheUser->getParent() == FoldInst->getParent() &&
02072          --MaxUsers) { // Don't scan too far.
02073     // If there are multiple or no uses of this instruction, then bail out.
02074     if (!TheUser->hasOneUse())
02075       return false;
02076 
02077     TheUser = TheUser->user_back();
02078   }
02079 
02080   // If we didn't find the fold instruction, then we failed to collapse the
02081   // sequence.
02082   if (TheUser != FoldInst)
02083     return false;
02084 
02085   // Don't try to fold volatile loads.  Target has to deal with alignment
02086   // constraints.
02087   if (LI->isVolatile())
02088     return false;
02089 
02090   // Figure out which vreg this is going into.  If there is no assigned vreg yet
02091   // then there actually was no reference to it.  Perhaps the load is referenced
02092   // by a dead instruction.
02093   unsigned LoadReg = getRegForValue(LI);
02094   if (!LoadReg)
02095     return false;
02096 
02097   // We can't fold if this vreg has no uses or more than one use.  Multiple uses
02098   // may mean that the instruction got lowered to multiple MIs, or the use of
02099   // the loaded value ended up being multiple operands of the result.
02100   if (!MRI.hasOneUse(LoadReg))
02101     return false;
02102 
02103   MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LoadReg);
02104   MachineInstr *User = RI->getParent();
02105 
02106   // Set the insertion point properly.  Folding the load can cause generation of
02107   // other random instructions (like sign extends) for addressing modes; make
02108   // sure they get inserted in a logical place before the new instruction.
02109   FuncInfo.InsertPt = User;
02110   FuncInfo.MBB = User->getParent();
02111 
02112   // Ask the target to try folding the load.
02113   return tryToFoldLoadIntoMI(User, RI.getOperandNo(), LI);
02114 }
02115 
02116 bool FastISel::canFoldAddIntoGEP(const User *GEP, const Value *Add) {
02117   // Must be an add.
02118   if (!isa<AddOperator>(Add))
02119     return false;
02120   // Type size needs to match.
02121   if (DL.getTypeSizeInBits(GEP->getType()) !=
02122       DL.getTypeSizeInBits(Add->getType()))
02123     return false;
02124   // Must be in the same basic block.
02125   if (isa<Instruction>(Add) &&
02126       FuncInfo.MBBMap[cast<Instruction>(Add)->getParent()] != FuncInfo.MBB)
02127     return false;
02128   // Must have a constant operand.
02129   return isa<ConstantInt>(cast<AddOperator>(Add)->getOperand(1));
02130 }
02131 
02132 MachineMemOperand *
02133 FastISel::createMachineMemOperandFor(const Instruction *I) const {
02134   const Value *Ptr;
02135   Type *ValTy;
02136   unsigned Alignment;
02137   unsigned Flags;
02138   bool IsVolatile;
02139 
02140   if (const auto *LI = dyn_cast<LoadInst>(I)) {
02141     Alignment = LI->getAlignment();
02142     IsVolatile = LI->isVolatile();
02143     Flags = MachineMemOperand::MOLoad;
02144     Ptr = LI->getPointerOperand();
02145     ValTy = LI->getType();
02146   } else if (const auto *SI = dyn_cast<StoreInst>(I)) {
02147     Alignment = SI->getAlignment();
02148     IsVolatile = SI->isVolatile();
02149     Flags = MachineMemOperand::MOStore;
02150     Ptr = SI->getPointerOperand();
02151     ValTy = SI->getValueOperand()->getType();
02152   } else
02153     return nullptr;
02154 
02155   bool IsNonTemporal = I->getMetadata(LLVMContext::MD_nontemporal) != nullptr;
02156   bool IsInvariant = I->getMetadata(LLVMContext::MD_invariant_load) != nullptr;
02157   const MDNode *Ranges = I->getMetadata(LLVMContext::MD_range);
02158 
02159   AAMDNodes AAInfo;
02160   I->getAAMetadata(AAInfo);
02161 
02162   if (Alignment == 0) // Ensure that codegen never sees alignment 0.
02163     Alignment = DL.getABITypeAlignment(ValTy);
02164 
02165   unsigned Size = DL.getTypeStoreSize(ValTy);
02166 
02167   if (IsVolatile)
02168     Flags |= MachineMemOperand::MOVolatile;
02169   if (IsNonTemporal)
02170     Flags |= MachineMemOperand::MONonTemporal;
02171   if (IsInvariant)
02172     Flags |= MachineMemOperand::MOInvariant;
02173 
02174   return FuncInfo.MF->getMachineMemOperand(MachinePointerInfo(Ptr), Flags, Size,
02175                                            Alignment, AAInfo, Ranges);
02176 }
02177 
02178 CmpInst::Predicate FastISel::optimizeCmpPredicate(const CmpInst *CI) const {
02179   // If both operands are the same, then try to optimize or fold the cmp.
02180   CmpInst::Predicate Predicate = CI->getPredicate();
02181   if (CI->getOperand(0) != CI->getOperand(1))
02182     return Predicate;
02183 
02184   switch (Predicate) {
02185   default: llvm_unreachable("Invalid predicate!");
02186   case CmpInst::FCMP_FALSE: Predicate = CmpInst::FCMP_FALSE; break;
02187   case CmpInst::FCMP_OEQ:   Predicate = CmpInst::FCMP_ORD;   break;
02188   case CmpInst::FCMP_OGT:   Predicate = CmpInst::FCMP_FALSE; break;
02189   case CmpInst::FCMP_OGE:   Predicate = CmpInst::FCMP_ORD;   break;
02190   case CmpInst::FCMP_OLT:   Predicate = CmpInst::FCMP_FALSE; break;
02191   case CmpInst::FCMP_OLE:   Predicate = CmpInst::FCMP_ORD;   break;
02192   case CmpInst::FCMP_ONE:   Predicate = CmpInst::FCMP_FALSE; break;
02193   case CmpInst::FCMP_ORD:   Predicate = CmpInst::FCMP_ORD;   break;
02194   case CmpInst::FCMP_UNO:   Predicate = CmpInst::FCMP_UNO;   break;
02195   case CmpInst::FCMP_UEQ:   Predicate = CmpInst::FCMP_TRUE;  break;
02196   case CmpInst::FCMP_UGT:   Predicate = CmpInst::FCMP_UNO;   break;
02197   case CmpInst::FCMP_UGE:   Predicate = CmpInst::FCMP_TRUE;  break;
02198   case CmpInst::FCMP_ULT:   Predicate = CmpInst::FCMP_UNO;   break;
02199   case CmpInst::FCMP_ULE:   Predicate = CmpInst::FCMP_TRUE;  break;
02200   case CmpInst::FCMP_UNE:   Predicate = CmpInst::FCMP_UNO;   break;
02201   case CmpInst::FCMP_TRUE:  Predicate = CmpInst::FCMP_TRUE;  break;
02202 
02203   case CmpInst::ICMP_EQ:    Predicate = CmpInst::FCMP_TRUE;  break;
02204   case CmpInst::ICMP_NE:    Predicate = CmpInst::FCMP_FALSE; break;
02205   case CmpInst::ICMP_UGT:   Predicate = CmpInst::FCMP_FALSE; break;
02206   case CmpInst::ICMP_UGE:   Predicate = CmpInst::FCMP_TRUE;  break;
02207   case CmpInst::ICMP_ULT:   Predicate = CmpInst::FCMP_FALSE; break;
02208   case CmpInst::ICMP_ULE:   Predicate = CmpInst::FCMP_TRUE;  break;
02209   case CmpInst::ICMP_SGT:   Predicate = CmpInst::FCMP_FALSE; break;
02210   case CmpInst::ICMP_SGE:   Predicate = CmpInst::FCMP_TRUE;  break;
02211   case CmpInst::ICMP_SLT:   Predicate = CmpInst::FCMP_FALSE; break;
02212   case CmpInst::ICMP_SLE:   Predicate = CmpInst::FCMP_TRUE;  break;
02213   }
02214 
02215   return Predicate;
02216 }