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 using namespace llvm;
00069 
00070 #define DEBUG_TYPE "isel"
00071 
00072 STATISTIC(NumFastIselSuccessIndependent, "Number of insts selected by "
00073           "target-independent selector");
00074 STATISTIC(NumFastIselSuccessTarget, "Number of insts selected by "
00075           "target-specific selector");
00076 STATISTIC(NumFastIselDead, "Number of dead insts removed on failure");
00077 
00078 /// \brief Set CallLoweringInfo attribute flags based on a call instruction
00079 /// and called function attributes.
00080 void FastISel::ArgListEntry::setAttributes(ImmutableCallSite *CS,
00081                                            unsigned AttrIdx) {
00082   isSExt     = CS->paramHasAttr(AttrIdx, Attribute::SExt);
00083   isZExt     = CS->paramHasAttr(AttrIdx, Attribute::ZExt);
00084   isInReg    = CS->paramHasAttr(AttrIdx, Attribute::InReg);
00085   isSRet     = CS->paramHasAttr(AttrIdx, Attribute::StructRet);
00086   isNest     = CS->paramHasAttr(AttrIdx, Attribute::Nest);
00087   isByVal    = CS->paramHasAttr(AttrIdx, Attribute::ByVal);
00088   isInAlloca = CS->paramHasAttr(AttrIdx, Attribute::InAlloca);
00089   isReturned = CS->paramHasAttr(AttrIdx, Attribute::Returned);
00090   Alignment  = CS->getParamAlignment(AttrIdx);
00091 }
00092 
00093 /// startNewBlock - Set the current block to which generated machine
00094 /// instructions will be appended, and clear the local CSE map.
00095 ///
00096 void FastISel::startNewBlock() {
00097   LocalValueMap.clear();
00098 
00099   // Instructions are appended to FuncInfo.MBB. If the basic block already
00100   // contains labels or copies, use the last instruction as the last local
00101   // value.
00102   EmitStartPt = nullptr;
00103   if (!FuncInfo.MBB->empty())
00104     EmitStartPt = &FuncInfo.MBB->back();
00105   LastLocalValue = EmitStartPt;
00106 }
00107 
00108 bool FastISel::LowerArguments() {
00109   if (!FuncInfo.CanLowerReturn)
00110     // Fallback to SDISel argument lowering code to deal with sret pointer
00111     // parameter.
00112     return false;
00113 
00114   if (!FastLowerArguments())
00115     return false;
00116 
00117   // Enter arguments into ValueMap for uses in non-entry BBs.
00118   for (Function::const_arg_iterator I = FuncInfo.Fn->arg_begin(),
00119          E = FuncInfo.Fn->arg_end(); I != E; ++I) {
00120     DenseMap<const Value *, unsigned>::iterator VI = LocalValueMap.find(I);
00121     assert(VI != LocalValueMap.end() && "Missed an argument?");
00122     FuncInfo.ValueMap[I] = VI->second;
00123   }
00124   return true;
00125 }
00126 
00127 void FastISel::flushLocalValueMap() {
00128   LocalValueMap.clear();
00129   LastLocalValue = EmitStartPt;
00130   recomputeInsertPt();
00131 }
00132 
00133 bool FastISel::hasTrivialKill(const Value *V) const {
00134   // Don't consider constants or arguments to have trivial kills.
00135   const Instruction *I = dyn_cast<Instruction>(V);
00136   if (!I)
00137     return false;
00138 
00139   // No-op casts are trivially coalesced by fast-isel.
00140   if (const CastInst *Cast = dyn_cast<CastInst>(I))
00141     if (Cast->isNoopCast(DL.getIntPtrType(Cast->getContext())) &&
00142         !hasTrivialKill(Cast->getOperand(0)))
00143       return false;
00144 
00145   // GEPs with all zero indices are trivially coalesced by fast-isel.
00146   if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I))
00147     if (GEP->hasAllZeroIndices() && !hasTrivialKill(GEP->getOperand(0)))
00148       return false;
00149 
00150   // Only instructions with a single use in the same basic block are considered
00151   // to have trivial kills.
00152   return I->hasOneUse() &&
00153          !(I->getOpcode() == Instruction::BitCast ||
00154            I->getOpcode() == Instruction::PtrToInt ||
00155            I->getOpcode() == Instruction::IntToPtr) &&
00156          cast<Instruction>(*I->user_begin())->getParent() == I->getParent();
00157 }
00158 
00159 unsigned FastISel::getRegForValue(const Value *V) {
00160   EVT RealVT = TLI.getValueType(V->getType(), /*AllowUnknown=*/true);
00161   // Don't handle non-simple values in FastISel.
00162   if (!RealVT.isSimple())
00163     return 0;
00164 
00165   // Ignore illegal types. We must do this before looking up the value
00166   // in ValueMap because Arguments are given virtual registers regardless
00167   // of whether FastISel can handle them.
00168   MVT VT = RealVT.getSimpleVT();
00169   if (!TLI.isTypeLegal(VT)) {
00170     // Handle integer promotions, though, because they're common and easy.
00171     if (VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16)
00172       VT = TLI.getTypeToTransformTo(V->getContext(), VT).getSimpleVT();
00173     else
00174       return 0;
00175   }
00176 
00177   // Look up the value to see if we already have a register for it.
00178   unsigned Reg = lookUpRegForValue(V);
00179   if (Reg != 0)
00180     return Reg;
00181 
00182   // In bottom-up mode, just create the virtual register which will be used
00183   // to hold the value. It will be materialized later.
00184   if (isa<Instruction>(V) &&
00185       (!isa<AllocaInst>(V) ||
00186        !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(V))))
00187     return FuncInfo.InitializeRegForValue(V);
00188 
00189   SavePoint SaveInsertPt = enterLocalValueArea();
00190 
00191   // Materialize the value in a register. Emit any instructions in the
00192   // local value area.
00193   Reg = materializeRegForValue(V, VT);
00194 
00195   leaveLocalValueArea(SaveInsertPt);
00196 
00197   return Reg;
00198 }
00199 
00200 /// materializeRegForValue - Helper for getRegForValue. This function is
00201 /// called when the value isn't already available in a register and must
00202 /// be materialized with new instructions.
00203 unsigned FastISel::materializeRegForValue(const Value *V, MVT VT) {
00204   unsigned Reg = 0;
00205 
00206   if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
00207     if (CI->getValue().getActiveBits() <= 64)
00208       Reg = FastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue());
00209   } else if (isa<AllocaInst>(V)) {
00210     Reg = TargetMaterializeAlloca(cast<AllocaInst>(V));
00211   } else if (isa<ConstantPointerNull>(V)) {
00212     // Translate this as an integer zero so that it can be
00213     // local-CSE'd with actual integer zeros.
00214     Reg =
00215       getRegForValue(Constant::getNullValue(DL.getIntPtrType(V->getContext())));
00216   } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
00217     if (CF->isNullValue()) {
00218       Reg = TargetMaterializeFloatZero(CF);
00219     } else {
00220       // Try to emit the constant directly.
00221       Reg = FastEmit_f(VT, VT, ISD::ConstantFP, CF);
00222     }
00223 
00224     if (!Reg) {
00225       // Try to emit the constant by using an integer constant with a cast.
00226       const APFloat &Flt = CF->getValueAPF();
00227       EVT IntVT = TLI.getPointerTy();
00228 
00229       uint64_t x[2];
00230       uint32_t IntBitWidth = IntVT.getSizeInBits();
00231       bool isExact;
00232       (void) Flt.convertToInteger(x, IntBitWidth, /*isSigned=*/true,
00233                                   APFloat::rmTowardZero, &isExact);
00234       if (isExact) {
00235         APInt IntVal(IntBitWidth, x);
00236 
00237         unsigned IntegerReg =
00238           getRegForValue(ConstantInt::get(V->getContext(), IntVal));
00239         if (IntegerReg != 0)
00240           Reg = FastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP,
00241                            IntegerReg, /*Kill=*/false);
00242       }
00243     }
00244   } else if (const Operator *Op = dyn_cast<Operator>(V)) {
00245     if (!SelectOperator(Op, Op->getOpcode()))
00246       if (!isa<Instruction>(Op) ||
00247           !TargetSelectInstruction(cast<Instruction>(Op)))
00248         return 0;
00249     Reg = lookUpRegForValue(Op);
00250   } else if (isa<UndefValue>(V)) {
00251     Reg = createResultReg(TLI.getRegClassFor(VT));
00252     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
00253             TII.get(TargetOpcode::IMPLICIT_DEF), Reg);
00254   }
00255 
00256   // If target-independent code couldn't handle the value, give target-specific
00257   // code a try.
00258   if (!Reg && isa<Constant>(V))
00259     Reg = TargetMaterializeConstant(cast<Constant>(V));
00260 
00261   // Don't cache constant materializations in the general ValueMap.
00262   // To do so would require tracking what uses they dominate.
00263   if (Reg != 0) {
00264     LocalValueMap[V] = Reg;
00265     LastLocalValue = MRI.getVRegDef(Reg);
00266   }
00267   return Reg;
00268 }
00269 
00270 unsigned FastISel::lookUpRegForValue(const Value *V) {
00271   // Look up the value to see if we already have a register for it. We
00272   // cache values defined by Instructions across blocks, and other values
00273   // only locally. This is because Instructions already have the SSA
00274   // def-dominates-use requirement enforced.
00275   DenseMap<const Value *, unsigned>::iterator I = FuncInfo.ValueMap.find(V);
00276   if (I != FuncInfo.ValueMap.end())
00277     return I->second;
00278   return LocalValueMap[V];
00279 }
00280 
00281 /// UpdateValueMap - Update the value map to include the new mapping for this
00282 /// instruction, or insert an extra copy to get the result in a previous
00283 /// determined register.
00284 /// NOTE: This is only necessary because we might select a block that uses
00285 /// a value before we select the block that defines the value.  It might be
00286 /// possible to fix this by selecting blocks in reverse postorder.
00287 void FastISel::UpdateValueMap(const Value *I, unsigned Reg, unsigned NumRegs) {
00288   if (!isa<Instruction>(I)) {
00289     LocalValueMap[I] = Reg;
00290     return;
00291   }
00292 
00293   unsigned &AssignedReg = FuncInfo.ValueMap[I];
00294   if (AssignedReg == 0)
00295     // Use the new register.
00296     AssignedReg = Reg;
00297   else if (Reg != AssignedReg) {
00298     // Arrange for uses of AssignedReg to be replaced by uses of Reg.
00299     for (unsigned i = 0; i < NumRegs; i++)
00300       FuncInfo.RegFixups[AssignedReg+i] = Reg+i;
00301 
00302     AssignedReg = Reg;
00303   }
00304 }
00305 
00306 std::pair<unsigned, bool> FastISel::getRegForGEPIndex(const Value *Idx) {
00307   unsigned IdxN = getRegForValue(Idx);
00308   if (IdxN == 0)
00309     // Unhandled operand. Halt "fast" selection and bail.
00310     return std::pair<unsigned, bool>(0, false);
00311 
00312   bool IdxNIsKill = hasTrivialKill(Idx);
00313 
00314   // If the index is smaller or larger than intptr_t, truncate or extend it.
00315   MVT PtrVT = TLI.getPointerTy();
00316   EVT IdxVT = EVT::getEVT(Idx->getType(), /*HandleUnknown=*/false);
00317   if (IdxVT.bitsLT(PtrVT)) {
00318     IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::SIGN_EXTEND,
00319                       IdxN, IdxNIsKill);
00320     IdxNIsKill = true;
00321   }
00322   else if (IdxVT.bitsGT(PtrVT)) {
00323     IdxN = FastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::TRUNCATE,
00324                       IdxN, IdxNIsKill);
00325     IdxNIsKill = true;
00326   }
00327   return std::pair<unsigned, bool>(IdxN, IdxNIsKill);
00328 }
00329 
00330 void FastISel::recomputeInsertPt() {
00331   if (getLastLocalValue()) {
00332     FuncInfo.InsertPt = getLastLocalValue();
00333     FuncInfo.MBB = FuncInfo.InsertPt->getParent();
00334     ++FuncInfo.InsertPt;
00335   } else
00336     FuncInfo.InsertPt = FuncInfo.MBB->getFirstNonPHI();
00337 
00338   // Now skip past any EH_LABELs, which must remain at the beginning.
00339   while (FuncInfo.InsertPt != FuncInfo.MBB->end() &&
00340          FuncInfo.InsertPt->getOpcode() == TargetOpcode::EH_LABEL)
00341     ++FuncInfo.InsertPt;
00342 }
00343 
00344 void FastISel::removeDeadCode(MachineBasicBlock::iterator I,
00345                               MachineBasicBlock::iterator E) {
00346   assert (I && E && std::distance(I, E) > 0 && "Invalid iterator!");
00347   while (I != E) {
00348     MachineInstr *Dead = &*I;
00349     ++I;
00350     Dead->eraseFromParent();
00351     ++NumFastIselDead;
00352   }
00353   recomputeInsertPt();
00354 }
00355 
00356 FastISel::SavePoint FastISel::enterLocalValueArea() {
00357   MachineBasicBlock::iterator OldInsertPt = FuncInfo.InsertPt;
00358   DebugLoc OldDL = DbgLoc;
00359   recomputeInsertPt();
00360   DbgLoc = DebugLoc();
00361   SavePoint SP = { OldInsertPt, OldDL };
00362   return SP;
00363 }
00364 
00365 void FastISel::leaveLocalValueArea(SavePoint OldInsertPt) {
00366   if (FuncInfo.InsertPt != FuncInfo.MBB->begin())
00367     LastLocalValue = std::prev(FuncInfo.InsertPt);
00368 
00369   // Restore the previous insert position.
00370   FuncInfo.InsertPt = OldInsertPt.InsertPt;
00371   DbgLoc = OldInsertPt.DL;
00372 }
00373 
00374 /// SelectBinaryOp - Select and emit code for a binary operator instruction,
00375 /// which has an opcode which directly corresponds to the given ISD opcode.
00376 ///
00377 bool FastISel::SelectBinaryOp(const User *I, unsigned ISDOpcode) {
00378   EVT VT = EVT::getEVT(I->getType(), /*HandleUnknown=*/true);
00379   if (VT == MVT::Other || !VT.isSimple())
00380     // Unhandled type. Halt "fast" selection and bail.
00381     return false;
00382 
00383   // We only handle legal types. For example, on x86-32 the instruction
00384   // selector contains all of the 64-bit instructions from x86-64,
00385   // under the assumption that i64 won't be used if the target doesn't
00386   // support it.
00387   if (!TLI.isTypeLegal(VT)) {
00388     // MVT::i1 is special. Allow AND, OR, or XOR because they
00389     // don't require additional zeroing, which makes them easy.
00390     if (VT == MVT::i1 &&
00391         (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR ||
00392          ISDOpcode == ISD::XOR))
00393       VT = TLI.getTypeToTransformTo(I->getContext(), VT);
00394     else
00395       return false;
00396   }
00397 
00398   // Check if the first operand is a constant, and handle it as "ri".  At -O0,
00399   // we don't have anything that canonicalizes operand order.
00400   if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(0)))
00401     if (isa<Instruction>(I) && cast<Instruction>(I)->isCommutative()) {
00402       unsigned Op1 = getRegForValue(I->getOperand(1));
00403       if (Op1 == 0) return false;
00404 
00405       bool Op1IsKill = hasTrivialKill(I->getOperand(1));
00406 
00407       unsigned ResultReg = FastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op1,
00408                                         Op1IsKill, CI->getZExtValue(),
00409                                         VT.getSimpleVT());
00410       if (ResultReg == 0) return false;
00411 
00412       // We successfully emitted code for the given LLVM Instruction.
00413       UpdateValueMap(I, ResultReg);
00414       return true;
00415     }
00416 
00417 
00418   unsigned Op0 = getRegForValue(I->getOperand(0));
00419   if (Op0 == 0)   // Unhandled operand. Halt "fast" selection and bail.
00420     return false;
00421 
00422   bool Op0IsKill = hasTrivialKill(I->getOperand(0));
00423 
00424   // Check if the second operand is a constant and handle it appropriately.
00425   if (ConstantInt *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
00426     uint64_t Imm = CI->getZExtValue();
00427 
00428     // Transform "sdiv exact X, 8" -> "sra X, 3".
00429     if (ISDOpcode == ISD::SDIV && isa<BinaryOperator>(I) &&
00430         cast<BinaryOperator>(I)->isExact() &&
00431         isPowerOf2_64(Imm)) {
00432       Imm = Log2_64(Imm);
00433       ISDOpcode = ISD::SRA;
00434     }
00435 
00436     // Transform "urem x, pow2" -> "and x, pow2-1".
00437     if (ISDOpcode == ISD::UREM && isa<BinaryOperator>(I) &&
00438         isPowerOf2_64(Imm)) {
00439       --Imm;
00440       ISDOpcode = ISD::AND;
00441     }
00442 
00443     unsigned ResultReg = FastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op0,
00444                                       Op0IsKill, Imm, VT.getSimpleVT());
00445     if (ResultReg == 0) return false;
00446 
00447     // We successfully emitted code for the given LLVM Instruction.
00448     UpdateValueMap(I, ResultReg);
00449     return true;
00450   }
00451 
00452   // Check if the second operand is a constant float.
00453   if (ConstantFP *CF = dyn_cast<ConstantFP>(I->getOperand(1))) {
00454     unsigned ResultReg = FastEmit_rf(VT.getSimpleVT(), VT.getSimpleVT(),
00455                                      ISDOpcode, Op0, Op0IsKill, CF);
00456     if (ResultReg != 0) {
00457       // We successfully emitted code for the given LLVM Instruction.
00458       UpdateValueMap(I, ResultReg);
00459       return true;
00460     }
00461   }
00462 
00463   unsigned Op1 = getRegForValue(I->getOperand(1));
00464   if (Op1 == 0)
00465     // Unhandled operand. Halt "fast" selection and bail.
00466     return false;
00467 
00468   bool Op1IsKill = hasTrivialKill(I->getOperand(1));
00469 
00470   // Now we have both operands in registers. Emit the instruction.
00471   unsigned ResultReg = FastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(),
00472                                    ISDOpcode,
00473                                    Op0, Op0IsKill,
00474                                    Op1, Op1IsKill);
00475   if (ResultReg == 0)
00476     // Target-specific code wasn't able to find a machine opcode for
00477     // the given ISD opcode and type. Halt "fast" selection and bail.
00478     return false;
00479 
00480   // We successfully emitted code for the given LLVM Instruction.
00481   UpdateValueMap(I, ResultReg);
00482   return true;
00483 }
00484 
00485 bool FastISel::SelectGetElementPtr(const User *I) {
00486   unsigned N = getRegForValue(I->getOperand(0));
00487   if (N == 0)
00488     // Unhandled operand. Halt "fast" selection and bail.
00489     return false;
00490 
00491   bool NIsKill = hasTrivialKill(I->getOperand(0));
00492 
00493   // Keep a running tab of the total offset to coalesce multiple N = N + Offset
00494   // into a single N = N + TotalOffset.
00495   uint64_t TotalOffs = 0;
00496   // FIXME: What's a good SWAG number for MaxOffs?
00497   uint64_t MaxOffs = 2048;
00498   Type *Ty = I->getOperand(0)->getType();
00499   MVT VT = TLI.getPointerTy();
00500   for (GetElementPtrInst::const_op_iterator OI = I->op_begin()+1,
00501        E = I->op_end(); OI != E; ++OI) {
00502     const Value *Idx = *OI;
00503     if (StructType *StTy = dyn_cast<StructType>(Ty)) {
00504       unsigned Field = cast<ConstantInt>(Idx)->getZExtValue();
00505       if (Field) {
00506         // N = N + Offset
00507         TotalOffs += DL.getStructLayout(StTy)->getElementOffset(Field);
00508         if (TotalOffs >= MaxOffs) {
00509           N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
00510           if (N == 0)
00511             // Unhandled operand. Halt "fast" selection and bail.
00512             return false;
00513           NIsKill = true;
00514           TotalOffs = 0;
00515         }
00516       }
00517       Ty = StTy->getElementType(Field);
00518     } else {
00519       Ty = cast<SequentialType>(Ty)->getElementType();
00520 
00521       // If this is a constant subscript, handle it quickly.
00522       if (const ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) {
00523         if (CI->isZero()) continue;
00524         // N = N + Offset
00525         TotalOffs +=
00526           DL.getTypeAllocSize(Ty)*cast<ConstantInt>(CI)->getSExtValue();
00527         if (TotalOffs >= MaxOffs) {
00528           N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
00529           if (N == 0)
00530             // Unhandled operand. Halt "fast" selection and bail.
00531             return false;
00532           NIsKill = true;
00533           TotalOffs = 0;
00534         }
00535         continue;
00536       }
00537       if (TotalOffs) {
00538         N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
00539         if (N == 0)
00540           // Unhandled operand. Halt "fast" selection and bail.
00541           return false;
00542         NIsKill = true;
00543         TotalOffs = 0;
00544       }
00545 
00546       // N = N + Idx * ElementSize;
00547       uint64_t ElementSize = DL.getTypeAllocSize(Ty);
00548       std::pair<unsigned, bool> Pair = getRegForGEPIndex(Idx);
00549       unsigned IdxN = Pair.first;
00550       bool IdxNIsKill = Pair.second;
00551       if (IdxN == 0)
00552         // Unhandled operand. Halt "fast" selection and bail.
00553         return false;
00554 
00555       if (ElementSize != 1) {
00556         IdxN = FastEmit_ri_(VT, ISD::MUL, IdxN, IdxNIsKill, ElementSize, VT);
00557         if (IdxN == 0)
00558           // Unhandled operand. Halt "fast" selection and bail.
00559           return false;
00560         IdxNIsKill = true;
00561       }
00562       N = FastEmit_rr(VT, VT, ISD::ADD, N, NIsKill, IdxN, IdxNIsKill);
00563       if (N == 0)
00564         // Unhandled operand. Halt "fast" selection and bail.
00565         return false;
00566     }
00567   }
00568   if (TotalOffs) {
00569     N = FastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
00570     if (N == 0)
00571       // Unhandled operand. Halt "fast" selection and bail.
00572       return false;
00573   }
00574 
00575   // We successfully emitted code for the given LLVM Instruction.
00576   UpdateValueMap(I, N);
00577   return true;
00578 }
00579 
00580 /// \brief Add a stackmap or patchpoint intrinsic call's live variable operands
00581 /// to a stackmap or patchpoint machine instruction.
00582 bool FastISel::addStackMapLiveVars(SmallVectorImpl<MachineOperand> &Ops,
00583                                    const CallInst *CI, unsigned StartIdx) {
00584   for (unsigned i = StartIdx, e = CI->getNumArgOperands(); i != e; ++i) {
00585     Value *Val = CI->getArgOperand(i);
00586     // Check for constants and encode them with a StackMaps::ConstantOp prefix.
00587     if (auto *C = dyn_cast<ConstantInt>(Val)) {
00588       Ops.push_back(MachineOperand::CreateImm(StackMaps::ConstantOp));
00589       Ops.push_back(MachineOperand::CreateImm(C->getSExtValue()));
00590     } else if (isa<ConstantPointerNull>(Val)) {
00591       Ops.push_back(MachineOperand::CreateImm(StackMaps::ConstantOp));
00592       Ops.push_back(MachineOperand::CreateImm(0));
00593     } else if (auto *AI = dyn_cast<AllocaInst>(Val)) {
00594       // Values coming from a stack location also require a sepcial encoding,
00595       // but that is added later on by the target specific frame index
00596       // elimination implementation.
00597       auto SI = FuncInfo.StaticAllocaMap.find(AI);
00598       if (SI != FuncInfo.StaticAllocaMap.end())
00599         Ops.push_back(MachineOperand::CreateFI(SI->second));
00600       else
00601         return false;
00602     } else {
00603       unsigned Reg = getRegForValue(Val);
00604       if (Reg == 0)
00605         return false;
00606       Ops.push_back(MachineOperand::CreateReg(Reg, /*IsDef=*/false));
00607     }
00608   }
00609 
00610   return true;
00611 }
00612 
00613 bool FastISel::SelectStackmap(const CallInst *I) {
00614   // void @llvm.experimental.stackmap(i64 <id>, i32 <numShadowBytes>,
00615   //                                  [live variables...])
00616   assert(I->getCalledFunction()->getReturnType()->isVoidTy() &&
00617          "Stackmap cannot return a value.");
00618 
00619   // The stackmap intrinsic only records the live variables (the arguments
00620   // passed to it) and emits NOPS (if requested). Unlike the patchpoint
00621   // intrinsic, this won't be lowered to a function call. This means we don't
00622   // have to worry about calling conventions and target-specific lowering code.
00623   // Instead we perform the call lowering right here.
00624   //
00625   // CALLSEQ_START(0)
00626   // STACKMAP(id, nbytes, ...)
00627   // CALLSEQ_END(0, 0)
00628   //
00629   SmallVector<MachineOperand, 32> Ops;
00630 
00631   // Add the <id> and <numBytes> constants.
00632   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::IDPos)) &&
00633          "Expected a constant integer.");
00634   const auto *ID = cast<ConstantInt>(I->getOperand(PatchPointOpers::IDPos));
00635   Ops.push_back(MachineOperand::CreateImm(ID->getZExtValue()));
00636 
00637   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos)) &&
00638          "Expected a constant integer.");
00639   const auto *NumBytes =
00640     cast<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos));
00641   Ops.push_back(MachineOperand::CreateImm(NumBytes->getZExtValue()));
00642 
00643   // Push live variables for the stack map (skipping the first two arguments
00644   // <id> and <numBytes>).
00645   if (!addStackMapLiveVars(Ops, I, 2))
00646     return false;
00647 
00648   // We are not adding any register mask info here, because the stackmap doesn't
00649   // clobber anything.
00650 
00651   // Add scratch registers as implicit def and early clobber.
00652   CallingConv::ID CC = I->getCallingConv();
00653   const MCPhysReg *ScratchRegs = TLI.getScratchRegisters(CC);
00654   for (unsigned i = 0; ScratchRegs[i]; ++i)
00655     Ops.push_back(MachineOperand::CreateReg(
00656       ScratchRegs[i], /*IsDef=*/true, /*IsImp=*/true, /*IsKill=*/false,
00657       /*IsDead=*/false, /*IsUndef=*/false, /*IsEarlyClobber=*/true));
00658 
00659   // Issue CALLSEQ_START
00660   unsigned AdjStackDown = TII.getCallFrameSetupOpcode();
00661   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AdjStackDown))
00662     .addImm(0);
00663 
00664   // Issue STACKMAP.
00665   MachineInstrBuilder MIB = BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
00666                                     TII.get(TargetOpcode::STACKMAP));
00667   for (auto const &MO : Ops)
00668     MIB.addOperand(MO);
00669 
00670   // Issue CALLSEQ_END
00671   unsigned AdjStackUp = TII.getCallFrameDestroyOpcode();
00672   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AdjStackUp))
00673     .addImm(0).addImm(0);
00674 
00675   // Inform the Frame Information that we have a stackmap in this function.
00676   FuncInfo.MF->getFrameInfo()->setHasStackMap();
00677 
00678   return true;
00679 }
00680 
00681 /// \brief Lower an argument list according to the target calling convention.
00682 ///
00683 /// This is a helper for lowering intrinsics that follow a target calling
00684 /// convention or require stack pointer adjustment. Only a subset of the
00685 /// intrinsic's operands need to participate in the calling convention.
00686 bool FastISel::lowerCallOperands(const CallInst *CI, unsigned ArgIdx,
00687                                  unsigned NumArgs, const Value *Callee,
00688                                  bool ForceRetVoidTy, CallLoweringInfo &CLI) {
00689   ArgListTy Args;
00690   Args.reserve(NumArgs);
00691 
00692   // Populate the argument list.
00693   // Attributes for args start at offset 1, after the return attribute.
00694   ImmutableCallSite CS(CI);
00695   for (unsigned ArgI = ArgIdx, ArgE = ArgIdx + NumArgs, AttrI = ArgIdx + 1;
00696        ArgI != ArgE; ++ArgI) {
00697     Value *V = CI->getOperand(ArgI);
00698 
00699     assert(!V->getType()->isEmptyTy() && "Empty type passed to intrinsic.");
00700 
00701     ArgListEntry Entry;
00702     Entry.Val = V;
00703     Entry.Ty = V->getType();
00704     Entry.setAttributes(&CS, AttrI);
00705     Args.push_back(Entry);
00706   }
00707 
00708   Type *RetTy = ForceRetVoidTy ? Type::getVoidTy(CI->getType()->getContext())
00709                                : CI->getType();
00710   CLI.setCallee(CI->getCallingConv(), RetTy, Callee, std::move(Args), NumArgs);
00711 
00712   return LowerCallTo(CLI);
00713 }
00714 
00715 bool FastISel::SelectPatchpoint(const CallInst *I) {
00716   // void|i64 @llvm.experimental.patchpoint.void|i64(i64 <id>,
00717   //                                                 i32 <numBytes>,
00718   //                                                 i8* <target>,
00719   //                                                 i32 <numArgs>,
00720   //                                                 [Args...],
00721   //                                                 [live variables...])
00722   CallingConv::ID CC = I->getCallingConv();
00723   bool IsAnyRegCC = CC == CallingConv::AnyReg;
00724   bool HasDef = !I->getType()->isVoidTy();
00725   Value *Callee = I->getOperand(PatchPointOpers::TargetPos);
00726 
00727   // Get the real number of arguments participating in the call <numArgs>
00728   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NArgPos)) &&
00729          "Expected a constant integer.");
00730   const auto *NumArgsVal =
00731     cast<ConstantInt>(I->getOperand(PatchPointOpers::NArgPos));
00732   unsigned NumArgs = NumArgsVal->getZExtValue();
00733 
00734   // Skip the four meta args: <id>, <numNopBytes>, <target>, <numArgs>
00735   // This includes all meta-operands up to but not including CC.
00736   unsigned NumMetaOpers = PatchPointOpers::CCPos;
00737   assert(I->getNumArgOperands() >= NumMetaOpers + NumArgs &&
00738          "Not enough arguments provided to the patchpoint intrinsic");
00739 
00740   // For AnyRegCC the arguments are lowered later on manually.
00741   unsigned NumCallArgs = IsAnyRegCC ? 0 : NumArgs;
00742   CallLoweringInfo CLI;
00743   if (!lowerCallOperands(I, NumMetaOpers, NumCallArgs, Callee, IsAnyRegCC, CLI))
00744     return false;
00745 
00746   assert(CLI.Call && "No call instruction specified.");
00747 
00748   SmallVector<MachineOperand, 32> Ops;
00749 
00750   // Add an explicit result reg if we use the anyreg calling convention.
00751   if (IsAnyRegCC && HasDef) {
00752     assert(CLI.NumResultRegs == 0 && "Unexpected result register.");
00753     CLI.ResultReg = createResultReg(TLI.getRegClassFor(MVT::i64));
00754     CLI.NumResultRegs = 1;
00755     Ops.push_back(MachineOperand::CreateReg(CLI.ResultReg, /*IsDef=*/true));
00756   }
00757 
00758   // Add the <id> and <numBytes> constants.
00759   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::IDPos)) &&
00760          "Expected a constant integer.");
00761   const auto *ID = cast<ConstantInt>(I->getOperand(PatchPointOpers::IDPos));
00762   Ops.push_back(MachineOperand::CreateImm(ID->getZExtValue()));
00763 
00764   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos)) &&
00765          "Expected a constant integer.");
00766   const auto *NumBytes =
00767     cast<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos));
00768   Ops.push_back(MachineOperand::CreateImm(NumBytes->getZExtValue()));
00769 
00770   // Assume that the callee is a constant address or null pointer.
00771   // FIXME: handle function symbols in the future.
00772   uint64_t CalleeAddr;
00773   if (const auto *C = dyn_cast<IntToPtrInst>(Callee))
00774     CalleeAddr = cast<ConstantInt>(C->getOperand(0))->getZExtValue();
00775   else if (const auto *C = dyn_cast<ConstantExpr>(Callee)) {
00776     if (C->getOpcode() == Instruction::IntToPtr)
00777       CalleeAddr = cast<ConstantInt>(C->getOperand(0))->getZExtValue();
00778     else
00779       llvm_unreachable("Unsupported ConstantExpr.");
00780   } else if (isa<ConstantPointerNull>(Callee))
00781     CalleeAddr = 0;
00782   else
00783     llvm_unreachable("Unsupported callee address.");
00784 
00785   Ops.push_back(MachineOperand::CreateImm(CalleeAddr));
00786 
00787   // Adjust <numArgs> to account for any arguments that have been passed on
00788   // the stack instead.
00789   unsigned NumCallRegArgs = IsAnyRegCC ? NumArgs : CLI.OutRegs.size();
00790   Ops.push_back(MachineOperand::CreateImm(NumCallRegArgs));
00791 
00792   // Add the calling convention
00793   Ops.push_back(MachineOperand::CreateImm((unsigned)CC));
00794 
00795   // Add the arguments we omitted previously. The register allocator should
00796   // place these in any free register.
00797   if (IsAnyRegCC) {
00798     for (unsigned i = NumMetaOpers, e = NumMetaOpers + NumArgs; i != e; ++i) {
00799       unsigned Reg = getRegForValue(I->getArgOperand(i));
00800       if (!Reg)
00801         return false;
00802       Ops.push_back(MachineOperand::CreateReg(Reg, /*IsDef=*/false));
00803     }
00804   }
00805 
00806   // Push the arguments from the call instruction.
00807   for (auto Reg : CLI.OutRegs)
00808     Ops.push_back(MachineOperand::CreateReg(Reg, /*IsDef=*/false));
00809 
00810   // Push live variables for the stack map.
00811   if (!addStackMapLiveVars(Ops, I, NumMetaOpers + NumArgs))
00812     return false;
00813 
00814   // Push the register mask info.
00815   Ops.push_back(MachineOperand::CreateRegMask(TRI.getCallPreservedMask(CC)));
00816 
00817   // Add scratch registers as implicit def and early clobber.
00818   const MCPhysReg *ScratchRegs = TLI.getScratchRegisters(CC);
00819   for (unsigned i = 0; ScratchRegs[i]; ++i)
00820     Ops.push_back(MachineOperand::CreateReg(
00821       ScratchRegs[i], /*IsDef=*/true, /*IsImp=*/true, /*IsKill=*/false,
00822       /*IsDead=*/false, /*IsUndef=*/false, /*IsEarlyClobber=*/true));
00823 
00824   // Add implicit defs (return values).
00825   for (auto Reg : CLI.InRegs)
00826     Ops.push_back(MachineOperand::CreateReg(Reg, /*IsDef=*/true,
00827                                             /*IsImpl=*/true));
00828 
00829   // Insert the patchpoint instruction before the call generated by the target.
00830   MachineInstrBuilder MIB = BuildMI(*FuncInfo.MBB, CLI.Call, DbgLoc,
00831                                     TII.get(TargetOpcode::PATCHPOINT));
00832 
00833   for (auto &MO : Ops)
00834     MIB.addOperand(MO);
00835 
00836   MIB->setPhysRegsDeadExcept(CLI.InRegs, TRI);
00837 
00838   // Delete the original call instruction.
00839   CLI.Call->eraseFromParent();
00840 
00841   // Inform the Frame Information that we have a patchpoint in this function.
00842   FuncInfo.MF->getFrameInfo()->setHasPatchPoint();
00843 
00844   if (CLI.NumResultRegs)
00845     UpdateValueMap(I, CLI.ResultReg, CLI.NumResultRegs);
00846   return true;
00847 }
00848 
00849 /// Returns an AttributeSet representing the attributes applied to the return
00850 /// value of the given call.
00851 static AttributeSet getReturnAttrs(FastISel::CallLoweringInfo &CLI) {
00852   SmallVector<Attribute::AttrKind, 2> Attrs;
00853   if (CLI.RetSExt)
00854     Attrs.push_back(Attribute::SExt);
00855   if (CLI.RetZExt)
00856     Attrs.push_back(Attribute::ZExt);
00857   if (CLI.IsInReg)
00858     Attrs.push_back(Attribute::InReg);
00859 
00860   return AttributeSet::get(CLI.RetTy->getContext(), AttributeSet::ReturnIndex,
00861                            Attrs);
00862 }
00863 
00864 bool FastISel::LowerCallTo(const CallInst *CI, const char *SymName,
00865                            unsigned NumArgs) {
00866   ImmutableCallSite CS(CI);
00867 
00868   PointerType *PT = cast<PointerType>(CS.getCalledValue()->getType());
00869   FunctionType *FTy = cast<FunctionType>(PT->getElementType());
00870   Type *RetTy = FTy->getReturnType();
00871 
00872   ArgListTy Args;
00873   Args.reserve(NumArgs);
00874 
00875   // Populate the argument list.
00876   // Attributes for args start at offset 1, after the return attribute.
00877   for (unsigned ArgI = 0; ArgI != NumArgs; ++ArgI) {
00878     Value *V = CI->getOperand(ArgI);
00879 
00880     assert(!V->getType()->isEmptyTy() && "Empty type passed to intrinsic.");
00881 
00882     ArgListEntry Entry;
00883     Entry.Val = V;
00884     Entry.Ty = V->getType();
00885     Entry.setAttributes(&CS, ArgI + 1);
00886     Args.push_back(Entry);
00887   }
00888 
00889   CallLoweringInfo CLI;
00890   CLI.setCallee(RetTy, FTy, SymName, std::move(Args), CS, NumArgs);
00891 
00892   return LowerCallTo(CLI);
00893 }
00894 
00895 bool FastISel::LowerCallTo(CallLoweringInfo &CLI) {
00896   // Handle the incoming return values from the call.
00897   CLI.clearIns();
00898   SmallVector<EVT, 4> RetTys;
00899   ComputeValueVTs(TLI, CLI.RetTy, RetTys);
00900 
00901   SmallVector<ISD::OutputArg, 4> Outs;
00902   GetReturnInfo(CLI.RetTy, getReturnAttrs(CLI), Outs, TLI);
00903 
00904   bool CanLowerReturn = TLI.CanLowerReturn(CLI.CallConv, *FuncInfo.MF,
00905                                            CLI.IsVarArg, Outs,
00906                                            CLI.RetTy->getContext());
00907 
00908   // FIXME: sret demotion isn't supported yet - bail out.
00909   if (!CanLowerReturn)
00910     return false;
00911 
00912   for (unsigned I = 0, E = RetTys.size(); I != E; ++I) {
00913     EVT VT = RetTys[I];
00914     MVT RegisterVT = TLI.getRegisterType(CLI.RetTy->getContext(), VT);
00915     unsigned NumRegs = TLI.getNumRegisters(CLI.RetTy->getContext(), VT);
00916     for (unsigned i = 0; i != NumRegs; ++i) {
00917       ISD::InputArg MyFlags;
00918       MyFlags.VT = RegisterVT;
00919       MyFlags.ArgVT = VT;
00920       MyFlags.Used = CLI.IsReturnValueUsed;
00921       if (CLI.RetSExt)
00922         MyFlags.Flags.setSExt();
00923       if (CLI.RetZExt)
00924         MyFlags.Flags.setZExt();
00925       if (CLI.IsInReg)
00926         MyFlags.Flags.setInReg();
00927       CLI.Ins.push_back(MyFlags);
00928     }
00929   }
00930 
00931   // Handle all of the outgoing arguments.
00932   CLI.clearOuts();
00933   for (auto &Arg : CLI.getArgs()) {
00934     Type *FinalType = Arg.Ty;
00935     if (Arg.isByVal)
00936       FinalType = cast<PointerType>(Arg.Ty)->getElementType();
00937     bool NeedsRegBlock = TLI.functionArgumentNeedsConsecutiveRegisters(
00938       FinalType, CLI.CallConv, CLI.IsVarArg);
00939 
00940     ISD::ArgFlagsTy Flags;
00941     if (Arg.isZExt)
00942       Flags.setZExt();
00943     if (Arg.isSExt)
00944       Flags.setSExt();
00945     if (Arg.isInReg)
00946       Flags.setInReg();
00947     if (Arg.isSRet)
00948       Flags.setSRet();
00949     if (Arg.isByVal)
00950       Flags.setByVal();
00951     if (Arg.isInAlloca) {
00952       Flags.setInAlloca();
00953       // Set the byval flag for CCAssignFn callbacks that don't know about
00954       // inalloca. This way we can know how many bytes we should've allocated
00955       // and how many bytes a callee cleanup function will pop.  If we port
00956       // inalloca to more targets, we'll have to add custom inalloca handling in
00957       // the various CC lowering callbacks.
00958       Flags.setByVal();
00959     }
00960     if (Arg.isByVal || Arg.isInAlloca) {
00961       PointerType *Ty = cast<PointerType>(Arg.Ty);
00962       Type *ElementTy = Ty->getElementType();
00963       unsigned FrameSize = DL.getTypeAllocSize(ElementTy);
00964       // For ByVal, alignment should come from FE. BE will guess if this info is
00965       // not there, but there are cases it cannot get right.
00966       unsigned FrameAlign = Arg.Alignment;
00967       if (!FrameAlign)
00968         FrameAlign = TLI.getByValTypeAlignment(ElementTy);
00969       Flags.setByValSize(FrameSize);
00970       Flags.setByValAlign(FrameAlign);
00971     }
00972     if (Arg.isNest)
00973       Flags.setNest();
00974     if (NeedsRegBlock)
00975       Flags.setInConsecutiveRegs();
00976     unsigned OriginalAlignment = DL.getABITypeAlignment(Arg.Ty);
00977     Flags.setOrigAlign(OriginalAlignment);
00978 
00979     CLI.OutVals.push_back(Arg.Val);
00980     CLI.OutFlags.push_back(Flags);
00981   }
00982 
00983   if (!FastLowerCall(CLI))
00984     return false;
00985 
00986   // Set all unused physreg defs as dead.
00987   assert(CLI.Call && "No call instruction specified.");
00988   CLI.Call->setPhysRegsDeadExcept(CLI.InRegs, TRI);
00989 
00990   if (CLI.NumResultRegs && CLI.CS)
00991     UpdateValueMap(CLI.CS->getInstruction(), CLI.ResultReg, CLI.NumResultRegs);
00992 
00993   return true;
00994 }
00995 
00996 bool FastISel::LowerCall(const CallInst *CI) {
00997   ImmutableCallSite CS(CI);
00998 
00999   PointerType *PT = cast<PointerType>(CS.getCalledValue()->getType());
01000   FunctionType *FuncTy = cast<FunctionType>(PT->getElementType());
01001   Type *RetTy = FuncTy->getReturnType();
01002 
01003   ArgListTy Args;
01004   ArgListEntry Entry;
01005   Args.reserve(CS.arg_size());
01006 
01007   for (ImmutableCallSite::arg_iterator i = CS.arg_begin(), e = CS.arg_end();
01008        i != e; ++i) {
01009     Value *V = *i;
01010 
01011     // Skip empty types
01012     if (V->getType()->isEmptyTy())
01013       continue;
01014 
01015     Entry.Val = V;
01016     Entry.Ty = V->getType();
01017 
01018     // Skip the first return-type Attribute to get to params.
01019     Entry.setAttributes(&CS, i - CS.arg_begin() + 1);
01020     Args.push_back(Entry);
01021   }
01022 
01023   // Check if target-independent constraints permit a tail call here.
01024   // Target-dependent constraints are checked within FastLowerCall.
01025   bool IsTailCall = CI->isTailCall();
01026   if (IsTailCall && !isInTailCallPosition(CS, TM))
01027     IsTailCall = false;
01028 
01029   CallLoweringInfo CLI;
01030   CLI.setCallee(RetTy, FuncTy, CI->getCalledValue(), std::move(Args), CS)
01031     .setTailCall(IsTailCall);
01032 
01033   return LowerCallTo(CLI);
01034 }
01035 
01036 bool FastISel::SelectCall(const User *I) {
01037   const CallInst *Call = cast<CallInst>(I);
01038 
01039   // Handle simple inline asms.
01040   if (const InlineAsm *IA = dyn_cast<InlineAsm>(Call->getCalledValue())) {
01041     // If the inline asm has side effects, then make sure that no local value
01042     // lives across by flushing the local value map.
01043     if (IA->hasSideEffects())
01044       flushLocalValueMap();
01045 
01046     // Don't attempt to handle constraints.
01047     if (!IA->getConstraintString().empty())
01048       return false;
01049 
01050     unsigned ExtraInfo = 0;
01051     if (IA->hasSideEffects())
01052       ExtraInfo |= InlineAsm::Extra_HasSideEffects;
01053     if (IA->isAlignStack())
01054       ExtraInfo |= InlineAsm::Extra_IsAlignStack;
01055 
01056     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01057             TII.get(TargetOpcode::INLINEASM))
01058       .addExternalSymbol(IA->getAsmString().c_str())
01059       .addImm(ExtraInfo);
01060     return true;
01061   }
01062 
01063   MachineModuleInfo &MMI = FuncInfo.MF->getMMI();
01064   ComputeUsesVAFloatArgument(*Call, &MMI);
01065 
01066   // Handle intrinsic function calls.
01067   if (const auto *II = dyn_cast<IntrinsicInst>(Call))
01068     return SelectIntrinsicCall(II);
01069 
01070   // Usually, it does not make sense to initialize a value,
01071   // make an unrelated function call and use the value, because
01072   // it tends to be spilled on the stack. So, we move the pointer
01073   // to the last local value to the beginning of the block, so that
01074   // all the values which have already been materialized,
01075   // appear after the call. It also makes sense to skip intrinsics
01076   // since they tend to be inlined.
01077   flushLocalValueMap();
01078 
01079   return LowerCall(Call);
01080 }
01081 
01082 bool FastISel::SelectIntrinsicCall(const IntrinsicInst *II) {
01083   switch (II->getIntrinsicID()) {
01084   default: break;
01085   // At -O0 we don't care about the lifetime intrinsics.
01086   case Intrinsic::lifetime_start:
01087   case Intrinsic::lifetime_end:
01088   // The donothing intrinsic does, well, nothing.
01089   case Intrinsic::donothing:
01090     return true;
01091   case Intrinsic::dbg_declare: {
01092     const DbgDeclareInst *DI = cast<DbgDeclareInst>(II);
01093     DIVariable DIVar(DI->getVariable());
01094     assert((!DIVar || DIVar.isVariable()) &&
01095            "Variable in DbgDeclareInst should be either null or a DIVariable.");
01096     if (!DIVar || !FuncInfo.MF->getMMI().hasDebugInfo()) {
01097       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
01098       return true;
01099     }
01100 
01101     const Value *Address = DI->getAddress();
01102     if (!Address || isa<UndefValue>(Address)) {
01103       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
01104       return true;
01105     }
01106 
01107     unsigned Offset = 0;
01108     Optional<MachineOperand> Op;
01109     if (const Argument *Arg = dyn_cast<Argument>(Address))
01110       // Some arguments' frame index is recorded during argument lowering.
01111       Offset = FuncInfo.getArgumentFrameIndex(Arg);
01112     if (Offset)
01113       Op = MachineOperand::CreateFI(Offset);
01114     if (!Op)
01115       if (unsigned Reg = lookUpRegForValue(Address))
01116         Op = MachineOperand::CreateReg(Reg, false);
01117 
01118     // If we have a VLA that has a "use" in a metadata node that's then used
01119     // here but it has no other uses, then we have a problem. E.g.,
01120     //
01121     //   int foo (const int *x) {
01122     //     char a[*x];
01123     //     return 0;
01124     //   }
01125     //
01126     // If we assign 'a' a vreg and fast isel later on has to use the selection
01127     // DAG isel, it will want to copy the value to the vreg. However, there are
01128     // no uses, which goes counter to what selection DAG isel expects.
01129     if (!Op && !Address->use_empty() && isa<Instruction>(Address) &&
01130         (!isa<AllocaInst>(Address) ||
01131          !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(Address))))
01132       Op = MachineOperand::CreateReg(FuncInfo.InitializeRegForValue(Address),
01133                                      false);
01134 
01135     if (Op) {
01136       if (Op->isReg()) {
01137         Op->setIsDebug(true);
01138         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01139                 TII.get(TargetOpcode::DBG_VALUE), false, Op->getReg(), 0,
01140                 DI->getVariable());
01141       } else
01142         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01143                 TII.get(TargetOpcode::DBG_VALUE))
01144           .addOperand(*Op)
01145           .addImm(0)
01146           .addMetadata(DI->getVariable());
01147     } else {
01148       // We can't yet handle anything else here because it would require
01149       // generating code, thus altering codegen because of debug info.
01150       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
01151     }
01152     return true;
01153   }
01154   case Intrinsic::dbg_value: {
01155     // This form of DBG_VALUE is target-independent.
01156     const DbgValueInst *DI = cast<DbgValueInst>(II);
01157     const MCInstrDesc &II = TII.get(TargetOpcode::DBG_VALUE);
01158     const Value *V = DI->getValue();
01159     if (!V) {
01160       // Currently the optimizer can produce this; insert an undef to
01161       // help debugging.  Probably the optimizer should not do this.
01162       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
01163         .addReg(0U).addImm(DI->getOffset())
01164         .addMetadata(DI->getVariable());
01165     } else if (const ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
01166       if (CI->getBitWidth() > 64)
01167         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
01168           .addCImm(CI).addImm(DI->getOffset())
01169           .addMetadata(DI->getVariable());
01170       else
01171         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
01172           .addImm(CI->getZExtValue()).addImm(DI->getOffset())
01173           .addMetadata(DI->getVariable());
01174     } else if (const ConstantFP *CF = dyn_cast<ConstantFP>(V)) {
01175       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
01176         .addFPImm(CF).addImm(DI->getOffset())
01177         .addMetadata(DI->getVariable());
01178     } else if (unsigned Reg = lookUpRegForValue(V)) {
01179       // FIXME: This does not handle register-indirect values at offset 0.
01180       bool IsIndirect = DI->getOffset() != 0;
01181       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, IsIndirect,
01182               Reg, DI->getOffset(), DI->getVariable());
01183     } else {
01184       // We can't yet handle anything else here because it would require
01185       // generating code, thus altering codegen because of debug info.
01186       DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
01187     }
01188     return true;
01189   }
01190   case Intrinsic::objectsize: {
01191     ConstantInt *CI = cast<ConstantInt>(II->getArgOperand(1));
01192     unsigned long long Res = CI->isZero() ? -1ULL : 0;
01193     Constant *ResCI = ConstantInt::get(II->getType(), Res);
01194     unsigned ResultReg = getRegForValue(ResCI);
01195     if (ResultReg == 0)
01196       return false;
01197     UpdateValueMap(II, ResultReg);
01198     return true;
01199   }
01200   case Intrinsic::expect: {
01201     unsigned ResultReg = getRegForValue(II->getArgOperand(0));
01202     if (ResultReg == 0)
01203       return false;
01204     UpdateValueMap(II, ResultReg);
01205     return true;
01206   }
01207   case Intrinsic::experimental_stackmap:
01208     return SelectStackmap(II);
01209   case Intrinsic::experimental_patchpoint_void:
01210   case Intrinsic::experimental_patchpoint_i64:
01211     return SelectPatchpoint(II);
01212   }
01213 
01214   return FastLowerIntrinsicCall(II);
01215 }
01216 
01217 bool FastISel::SelectCast(const User *I, unsigned Opcode) {
01218   EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
01219   EVT DstVT = TLI.getValueType(I->getType());
01220 
01221   if (SrcVT == MVT::Other || !SrcVT.isSimple() ||
01222       DstVT == MVT::Other || !DstVT.isSimple())
01223     // Unhandled type. Halt "fast" selection and bail.
01224     return false;
01225 
01226   // Check if the destination type is legal.
01227   if (!TLI.isTypeLegal(DstVT))
01228     return false;
01229 
01230   // Check if the source operand is legal.
01231   if (!TLI.isTypeLegal(SrcVT))
01232     return false;
01233 
01234   unsigned InputReg = getRegForValue(I->getOperand(0));
01235   if (!InputReg)
01236     // Unhandled operand.  Halt "fast" selection and bail.
01237     return false;
01238 
01239   bool InputRegIsKill = hasTrivialKill(I->getOperand(0));
01240 
01241   unsigned ResultReg = FastEmit_r(SrcVT.getSimpleVT(),
01242                                   DstVT.getSimpleVT(),
01243                                   Opcode,
01244                                   InputReg, InputRegIsKill);
01245   if (!ResultReg)
01246     return false;
01247 
01248   UpdateValueMap(I, ResultReg);
01249   return true;
01250 }
01251 
01252 bool FastISel::SelectBitCast(const User *I) {
01253   // If the bitcast doesn't change the type, just use the operand value.
01254   if (I->getType() == I->getOperand(0)->getType()) {
01255     unsigned Reg = getRegForValue(I->getOperand(0));
01256     if (Reg == 0)
01257       return false;
01258     UpdateValueMap(I, Reg);
01259     return true;
01260   }
01261 
01262   // Bitcasts of other values become reg-reg copies or BITCAST operators.
01263   EVT SrcEVT = TLI.getValueType(I->getOperand(0)->getType());
01264   EVT DstEVT = TLI.getValueType(I->getType());
01265   if (SrcEVT == MVT::Other || DstEVT == MVT::Other ||
01266       !TLI.isTypeLegal(SrcEVT) || !TLI.isTypeLegal(DstEVT))
01267     // Unhandled type. Halt "fast" selection and bail.
01268     return false;
01269 
01270   MVT SrcVT = SrcEVT.getSimpleVT();
01271   MVT DstVT = DstEVT.getSimpleVT();
01272   unsigned Op0 = getRegForValue(I->getOperand(0));
01273   if (Op0 == 0)
01274     // Unhandled operand. Halt "fast" selection and bail.
01275     return false;
01276 
01277   bool Op0IsKill = hasTrivialKill(I->getOperand(0));
01278 
01279   // First, try to perform the bitcast by inserting a reg-reg copy.
01280   unsigned ResultReg = 0;
01281   if (SrcVT == DstVT) {
01282     const TargetRegisterClass* SrcClass = TLI.getRegClassFor(SrcVT);
01283     const TargetRegisterClass* DstClass = TLI.getRegClassFor(DstVT);
01284     // Don't attempt a cross-class copy. It will likely fail.
01285     if (SrcClass == DstClass) {
01286       ResultReg = createResultReg(DstClass);
01287       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
01288               TII.get(TargetOpcode::COPY), ResultReg).addReg(Op0);
01289     }
01290   }
01291 
01292   // If the reg-reg copy failed, select a BITCAST opcode.
01293   if (!ResultReg)
01294     ResultReg = FastEmit_r(SrcVT, DstVT, ISD::BITCAST, Op0, Op0IsKill);
01295 
01296   if (!ResultReg)
01297     return false;
01298 
01299   UpdateValueMap(I, ResultReg);
01300   return true;
01301 }
01302 
01303 bool
01304 FastISel::SelectInstruction(const Instruction *I) {
01305   // Just before the terminator instruction, insert instructions to
01306   // feed PHI nodes in successor blocks.
01307   if (isa<TerminatorInst>(I))
01308     if (!HandlePHINodesInSuccessorBlocks(I->getParent()))
01309       return false;
01310 
01311   DbgLoc = I->getDebugLoc();
01312 
01313   MachineBasicBlock::iterator SavedInsertPt = FuncInfo.InsertPt;
01314 
01315   if (const CallInst *Call = dyn_cast<CallInst>(I)) {
01316     const Function *F = Call->getCalledFunction();
01317     LibFunc::Func Func;
01318 
01319     // As a special case, don't handle calls to builtin library functions that
01320     // may be translated directly to target instructions.
01321     if (F && !F->hasLocalLinkage() && F->hasName() &&
01322         LibInfo->getLibFunc(F->getName(), Func) &&
01323         LibInfo->hasOptimizedCodeGen(Func))
01324       return false;
01325 
01326     // Don't handle Intrinsic::trap if a trap funciton is specified.
01327     if (F && F->getIntrinsicID() == Intrinsic::trap &&
01328         !TM.Options.getTrapFunctionName().empty())
01329       return false;
01330   }
01331 
01332   // First, try doing target-independent selection.
01333   if (SelectOperator(I, I->getOpcode())) {
01334     ++NumFastIselSuccessIndependent;
01335     DbgLoc = DebugLoc();
01336     return true;
01337   }
01338   // Remove dead code.  However, ignore call instructions since we've flushed
01339   // the local value map and recomputed the insert point.
01340   if (!isa<CallInst>(I)) {
01341     recomputeInsertPt();
01342     if (SavedInsertPt != FuncInfo.InsertPt)
01343       removeDeadCode(FuncInfo.InsertPt, SavedInsertPt);
01344   }
01345 
01346   // Next, try calling the target to attempt to handle the instruction.
01347   SavedInsertPt = FuncInfo.InsertPt;
01348   if (TargetSelectInstruction(I)) {
01349     ++NumFastIselSuccessTarget;
01350     DbgLoc = DebugLoc();
01351     return true;
01352   }
01353   // Check for dead code and remove as necessary.
01354   recomputeInsertPt();
01355   if (SavedInsertPt != FuncInfo.InsertPt)
01356     removeDeadCode(FuncInfo.InsertPt, SavedInsertPt);
01357 
01358   DbgLoc = DebugLoc();
01359   return false;
01360 }
01361 
01362 /// FastEmitBranch - Emit an unconditional branch to the given block,
01363 /// unless it is the immediate (fall-through) successor, and update
01364 /// the CFG.
01365 void
01366 FastISel::FastEmitBranch(MachineBasicBlock *MSucc, DebugLoc DbgLoc) {
01367   if (FuncInfo.MBB->getBasicBlock()->size() > 1 &&
01368       FuncInfo.MBB->isLayoutSuccessor(MSucc)) {
01369     // For more accurate line information if this is the only instruction
01370     // in the block then emit it, otherwise we have the unconditional
01371     // fall-through case, which needs no instructions.
01372   } else {
01373     // The unconditional branch case.
01374     TII.InsertBranch(*FuncInfo.MBB, MSucc, nullptr,
01375                      SmallVector<MachineOperand, 0>(), DbgLoc);
01376   }
01377   uint32_t BranchWeight = 0;
01378   if (FuncInfo.BPI)
01379     BranchWeight = FuncInfo.BPI->getEdgeWeight(FuncInfo.MBB->getBasicBlock(),
01380                                                MSucc->getBasicBlock());
01381   FuncInfo.MBB->addSuccessor(MSucc, BranchWeight);
01382 }
01383 
01384 /// SelectFNeg - Emit an FNeg operation.
01385 ///
01386 bool
01387 FastISel::SelectFNeg(const User *I) {
01388   unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I));
01389   if (OpReg == 0) return false;
01390 
01391   bool OpRegIsKill = hasTrivialKill(I);
01392 
01393   // If the target has ISD::FNEG, use it.
01394   EVT VT = TLI.getValueType(I->getType());
01395   unsigned ResultReg = FastEmit_r(VT.getSimpleVT(), VT.getSimpleVT(),
01396                                   ISD::FNEG, OpReg, OpRegIsKill);
01397   if (ResultReg != 0) {
01398     UpdateValueMap(I, ResultReg);
01399     return true;
01400   }
01401 
01402   // Bitcast the value to integer, twiddle the sign bit with xor,
01403   // and then bitcast it back to floating-point.
01404   if (VT.getSizeInBits() > 64) return false;
01405   EVT IntVT = EVT::getIntegerVT(I->getContext(), VT.getSizeInBits());
01406   if (!TLI.isTypeLegal(IntVT))
01407     return false;
01408 
01409   unsigned IntReg = FastEmit_r(VT.getSimpleVT(), IntVT.getSimpleVT(),
01410                                ISD::BITCAST, OpReg, OpRegIsKill);
01411   if (IntReg == 0)
01412     return false;
01413 
01414   unsigned IntResultReg = FastEmit_ri_(IntVT.getSimpleVT(), ISD::XOR,
01415                                        IntReg, /*Kill=*/true,
01416                                        UINT64_C(1) << (VT.getSizeInBits()-1),
01417                                        IntVT.getSimpleVT());
01418   if (IntResultReg == 0)
01419     return false;
01420 
01421   ResultReg = FastEmit_r(IntVT.getSimpleVT(), VT.getSimpleVT(),
01422                          ISD::BITCAST, IntResultReg, /*Kill=*/true);
01423   if (ResultReg == 0)
01424     return false;
01425 
01426   UpdateValueMap(I, ResultReg);
01427   return true;
01428 }
01429 
01430 bool
01431 FastISel::SelectExtractValue(const User *U) {
01432   const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(U);
01433   if (!EVI)
01434     return false;
01435 
01436   // Make sure we only try to handle extracts with a legal result.  But also
01437   // allow i1 because it's easy.
01438   EVT RealVT = TLI.getValueType(EVI->getType(), /*AllowUnknown=*/true);
01439   if (!RealVT.isSimple())
01440     return false;
01441   MVT VT = RealVT.getSimpleVT();
01442   if (!TLI.isTypeLegal(VT) && VT != MVT::i1)
01443     return false;
01444 
01445   const Value *Op0 = EVI->getOperand(0);
01446   Type *AggTy = Op0->getType();
01447 
01448   // Get the base result register.
01449   unsigned ResultReg;
01450   DenseMap<const Value *, unsigned>::iterator I = FuncInfo.ValueMap.find(Op0);
01451   if (I != FuncInfo.ValueMap.end())
01452     ResultReg = I->second;
01453   else if (isa<Instruction>(Op0))
01454     ResultReg = FuncInfo.InitializeRegForValue(Op0);
01455   else
01456     return false; // fast-isel can't handle aggregate constants at the moment
01457 
01458   // Get the actual result register, which is an offset from the base register.
01459   unsigned VTIndex = ComputeLinearIndex(AggTy, EVI->getIndices());
01460 
01461   SmallVector<EVT, 4> AggValueVTs;
01462   ComputeValueVTs(TLI, AggTy, AggValueVTs);
01463 
01464   for (unsigned i = 0; i < VTIndex; i++)
01465     ResultReg += TLI.getNumRegisters(FuncInfo.Fn->getContext(), AggValueVTs[i]);
01466 
01467   UpdateValueMap(EVI, ResultReg);
01468   return true;
01469 }
01470 
01471 bool
01472 FastISel::SelectOperator(const User *I, unsigned Opcode) {
01473   switch (Opcode) {
01474   case Instruction::Add:
01475     return SelectBinaryOp(I, ISD::ADD);
01476   case Instruction::FAdd:
01477     return SelectBinaryOp(I, ISD::FADD);
01478   case Instruction::Sub:
01479     return SelectBinaryOp(I, ISD::SUB);
01480   case Instruction::FSub:
01481     // FNeg is currently represented in LLVM IR as a special case of FSub.
01482     if (BinaryOperator::isFNeg(I))
01483       return SelectFNeg(I);
01484     return SelectBinaryOp(I, ISD::FSUB);
01485   case Instruction::Mul:
01486     return SelectBinaryOp(I, ISD::MUL);
01487   case Instruction::FMul:
01488     return SelectBinaryOp(I, ISD::FMUL);
01489   case Instruction::SDiv:
01490     return SelectBinaryOp(I, ISD::SDIV);
01491   case Instruction::UDiv:
01492     return SelectBinaryOp(I, ISD::UDIV);
01493   case Instruction::FDiv:
01494     return SelectBinaryOp(I, ISD::FDIV);
01495   case Instruction::SRem:
01496     return SelectBinaryOp(I, ISD::SREM);
01497   case Instruction::URem:
01498     return SelectBinaryOp(I, ISD::UREM);
01499   case Instruction::FRem:
01500     return SelectBinaryOp(I, ISD::FREM);
01501   case Instruction::Shl:
01502     return SelectBinaryOp(I, ISD::SHL);
01503   case Instruction::LShr:
01504     return SelectBinaryOp(I, ISD::SRL);
01505   case Instruction::AShr:
01506     return SelectBinaryOp(I, ISD::SRA);
01507   case Instruction::And:
01508     return SelectBinaryOp(I, ISD::AND);
01509   case Instruction::Or:
01510     return SelectBinaryOp(I, ISD::OR);
01511   case Instruction::Xor:
01512     return SelectBinaryOp(I, ISD::XOR);
01513 
01514   case Instruction::GetElementPtr:
01515     return SelectGetElementPtr(I);
01516 
01517   case Instruction::Br: {
01518     const BranchInst *BI = cast<BranchInst>(I);
01519 
01520     if (BI->isUnconditional()) {
01521       const BasicBlock *LLVMSucc = BI->getSuccessor(0);
01522       MachineBasicBlock *MSucc = FuncInfo.MBBMap[LLVMSucc];
01523       FastEmitBranch(MSucc, BI->getDebugLoc());
01524       return true;
01525     }
01526 
01527     // Conditional branches are not handed yet.
01528     // Halt "fast" selection and bail.
01529     return false;
01530   }
01531 
01532   case Instruction::Unreachable:
01533     if (TM.Options.TrapUnreachable)
01534       return FastEmit_(MVT::Other, MVT::Other, ISD::TRAP) != 0;
01535     else
01536       return true;
01537 
01538   case Instruction::Alloca:
01539     // FunctionLowering has the static-sized case covered.
01540     if (FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(I)))
01541       return true;
01542 
01543     // Dynamic-sized alloca is not handled yet.
01544     return false;
01545 
01546   case Instruction::Call:
01547     return SelectCall(I);
01548 
01549   case Instruction::BitCast:
01550     return SelectBitCast(I);
01551 
01552   case Instruction::FPToSI:
01553     return SelectCast(I, ISD::FP_TO_SINT);
01554   case Instruction::ZExt:
01555     return SelectCast(I, ISD::ZERO_EXTEND);
01556   case Instruction::SExt:
01557     return SelectCast(I, ISD::SIGN_EXTEND);
01558   case Instruction::Trunc:
01559     return SelectCast(I, ISD::TRUNCATE);
01560   case Instruction::SIToFP:
01561     return SelectCast(I, ISD::SINT_TO_FP);
01562 
01563   case Instruction::IntToPtr: // Deliberate fall-through.
01564   case Instruction::PtrToInt: {
01565     EVT SrcVT = TLI.getValueType(I->getOperand(0)->getType());
01566     EVT DstVT = TLI.getValueType(I->getType());
01567     if (DstVT.bitsGT(SrcVT))
01568       return SelectCast(I, ISD::ZERO_EXTEND);
01569     if (DstVT.bitsLT(SrcVT))
01570       return SelectCast(I, ISD::TRUNCATE);
01571     unsigned Reg = getRegForValue(I->getOperand(0));
01572     if (Reg == 0) return false;
01573     UpdateValueMap(I, Reg);
01574     return true;
01575   }
01576 
01577   case Instruction::ExtractValue:
01578     return SelectExtractValue(I);
01579 
01580   case Instruction::PHI:
01581     llvm_unreachable("FastISel shouldn't visit PHI nodes!");
01582 
01583   default:
01584     // Unhandled instruction. Halt "fast" selection and bail.
01585     return false;
01586   }
01587 }
01588 
01589 FastISel::FastISel(FunctionLoweringInfo &funcInfo,
01590                    const TargetLibraryInfo *libInfo)
01591   : FuncInfo(funcInfo),
01592     MF(funcInfo.MF),
01593     MRI(FuncInfo.MF->getRegInfo()),
01594     MFI(*FuncInfo.MF->getFrameInfo()),
01595     MCP(*FuncInfo.MF->getConstantPool()),
01596     TM(FuncInfo.MF->getTarget()),
01597     DL(*TM.getDataLayout()),
01598     TII(*TM.getInstrInfo()),
01599     TLI(*TM.getTargetLowering()),
01600     TRI(*TM.getRegisterInfo()),
01601     LibInfo(libInfo) {
01602 }
01603 
01604 FastISel::~FastISel() {}
01605 
01606 bool FastISel::FastLowerArguments() {
01607   return false;
01608 }
01609 
01610 bool FastISel::FastLowerCall(CallLoweringInfo &/*CLI*/) {
01611   return false;
01612 }
01613 
01614 bool FastISel::FastLowerIntrinsicCall(const IntrinsicInst * /*II*/) {
01615   return false;
01616 }
01617 
01618 unsigned FastISel::FastEmit_(MVT, MVT,
01619                              unsigned) {
01620   return 0;
01621 }
01622 
01623 unsigned FastISel::FastEmit_r(MVT, MVT,
01624                               unsigned,
01625                               unsigned /*Op0*/, bool /*Op0IsKill*/) {
01626   return 0;
01627 }
01628 
01629 unsigned FastISel::FastEmit_rr(MVT, MVT,
01630                                unsigned,
01631                                unsigned /*Op0*/, bool /*Op0IsKill*/,
01632                                unsigned /*Op1*/, bool /*Op1IsKill*/) {
01633   return 0;
01634 }
01635 
01636 unsigned FastISel::FastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) {
01637   return 0;
01638 }
01639 
01640 unsigned FastISel::FastEmit_f(MVT, MVT,
01641                               unsigned, const ConstantFP * /*FPImm*/) {
01642   return 0;
01643 }
01644 
01645 unsigned FastISel::FastEmit_ri(MVT, MVT,
01646                                unsigned,
01647                                unsigned /*Op0*/, bool /*Op0IsKill*/,
01648                                uint64_t /*Imm*/) {
01649   return 0;
01650 }
01651 
01652 unsigned FastISel::FastEmit_rf(MVT, MVT,
01653                                unsigned,
01654                                unsigned /*Op0*/, bool /*Op0IsKill*/,
01655                                const ConstantFP * /*FPImm*/) {
01656   return 0;
01657 }
01658 
01659 unsigned FastISel::FastEmit_rri(MVT, MVT,
01660                                 unsigned,
01661                                 unsigned /*Op0*/, bool /*Op0IsKill*/,
01662                                 unsigned /*Op1*/, bool /*Op1IsKill*/,
01663                                 uint64_t /*Imm*/) {
01664   return 0;
01665 }
01666 
01667 /// FastEmit_ri_ - This method is a wrapper of FastEmit_ri. It first tries
01668 /// to emit an instruction with an immediate operand using FastEmit_ri.
01669 /// If that fails, it materializes the immediate into a register and try
01670 /// FastEmit_rr instead.
01671 unsigned FastISel::FastEmit_ri_(MVT VT, unsigned Opcode,
01672                                 unsigned Op0, bool Op0IsKill,
01673                                 uint64_t Imm, MVT ImmType) {
01674   // If this is a multiply by a power of two, emit this as a shift left.
01675   if (Opcode == ISD::MUL && isPowerOf2_64(Imm)) {
01676     Opcode = ISD::SHL;
01677     Imm = Log2_64(Imm);
01678   } else if (Opcode == ISD::UDIV && isPowerOf2_64(Imm)) {
01679     // div x, 8 -> srl x, 3
01680     Opcode = ISD::SRL;
01681     Imm = Log2_64(Imm);
01682   }
01683 
01684   // Horrible hack (to be removed), check to make sure shift amounts are
01685   // in-range.
01686   if ((Opcode == ISD::SHL || Opcode == ISD::SRA || Opcode == ISD::SRL) &&
01687       Imm >= VT.getSizeInBits())
01688     return 0;
01689 
01690   // First check if immediate type is legal. If not, we can't use the ri form.
01691   unsigned ResultReg = FastEmit_ri(VT, VT, Opcode, Op0, Op0IsKill, Imm);
01692   if (ResultReg != 0)
01693     return ResultReg;
01694   unsigned MaterialReg = FastEmit_i(ImmType, ImmType, ISD::Constant, Imm);
01695   if (MaterialReg == 0) {
01696     // This is a bit ugly/slow, but failing here means falling out of
01697     // fast-isel, which would be very slow.
01698     IntegerType *ITy = IntegerType::get(FuncInfo.Fn->getContext(),
01699                                               VT.getSizeInBits());
01700     MaterialReg = getRegForValue(ConstantInt::get(ITy, Imm));
01701     assert (MaterialReg != 0 && "Unable to materialize 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 = TM.getDataLayout()->getTypeStoreSize(ValTy);
02170 
02171   if (IsVolatile)
02172     Flags |= MachineMemOperand::MOVolatile;
02173   if (IsNonTemporal)
02174     Flags |= MachineMemOperand::MONonTemporal;
02175   if (IsInvariant)
02176     Flags |= MachineMemOperand::MOInvariant;
02177 
02178   return FuncInfo.MF->getMachineMemOperand(MachinePointerInfo(Ptr), Flags, Size,
02179                                            Alignment, AAInfo, Ranges);
02180 }