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