LLVM API Documentation

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