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