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