contrib/llvm/lib/CodeGen/SelectionDAG/FastISel.cpp

   1 //===- FastISel.cpp - Implementation of the FastISel class ----------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file contains the implementation of the FastISel class.
  11 //
  12 // "Fast" instruction selection is designed to emit very poor code quickly.
  13 // Also, it is not designed to be able to do much lowering, so most illegal
  14 // types (e.g. i64 on 32-bit targets) and operations are not supported.  It is
  15 // also not intended to be able to do much optimization, except in a few cases
  16 // where doing optimizations reduces overall compile time.  For example, folding
  17 // constants into immediate fields is often done, because it's cheap and it
  18 // reduces the number of instructions later phases have to examine.
  19 //
  20 // "Fast" instruction selection is able to fail gracefully and transfer
  21 // control to the SelectionDAG selector for operations that it doesn't
  22 // support.  In many cases, this allows us to avoid duplicating a lot of
  23 // the complicated lowering logic that SelectionDAG currently has.
  24 //
  25 // The intended use for "fast" instruction selection is "-O0" mode
  26 // compilation, where the quality of the generated code is irrelevant when
  27 // weighed against the speed at which the code can be generated.  Also,
  28 // at -O0, the LLVM optimizers are not running, and this makes the
  29 // compile time of codegen a much higher portion of the overall compile
  30 // time.  Despite its limitations, "fast" instruction selection is able to
  31 // handle enough code on its own to provide noticeable overall speedups
  32 // in -O0 compiles.
  33 //
  34 // Basic operations are supported in a target-independent way, by reading
  35 // the same instruction descriptions that the SelectionDAG selector reads,
  36 // and identifying simple arithmetic operations that can be directly selected
  37 // from simple operators.  More complicated operations currently require
  38 // target-specific code.
  39 //
  40 //===----------------------------------------------------------------------===//
  41
  42 #include "llvm/CodeGen/FastISel.h"
  43 #include "llvm/ADT/APFloat.h"
  44 #include "llvm/ADT/APSInt.h"
  45 #include "llvm/ADT/DenseMap.h"
  46 #include "llvm/ADT/Optional.h"
  47 #include "llvm/ADT/SmallPtrSet.h"
  48 #include "llvm/ADT/SmallString.h"
  49 #include "llvm/ADT/SmallVector.h"
  50 #include "llvm/ADT/Statistic.h"
  51 #include "llvm/Analysis/BranchProbabilityInfo.h"
  52 #include "llvm/Analysis/TargetLibraryInfo.h"
  53 #include "llvm/CodeGen/Analysis.h"
  54 #include "llvm/CodeGen/FunctionLoweringInfo.h"
  55 #include "llvm/CodeGen/ISDOpcodes.h"
  56 #include "llvm/CodeGen/MachineBasicBlock.h"
  57 #include "llvm/CodeGen/MachineFrameInfo.h"
  58 #include "llvm/CodeGen/MachineInstr.h"
  59 #include "llvm/CodeGen/MachineInstrBuilder.h"
  60 #include "llvm/CodeGen/MachineMemOperand.h"
  61 #include "llvm/CodeGen/MachineModuleInfo.h"
  62 #include "llvm/CodeGen/MachineOperand.h"
  63 #include "llvm/CodeGen/MachineRegisterInfo.h"
  64 #include "llvm/CodeGen/StackMaps.h"
  65 #include "llvm/CodeGen/TargetInstrInfo.h"
  66 #include "llvm/CodeGen/TargetLowering.h"
  67 #include "llvm/CodeGen/TargetSubtargetInfo.h"
  68 #include "llvm/CodeGen/ValueTypes.h"
  69 #include "llvm/IR/Argument.h"
  70 #include "llvm/IR/Attributes.h"
  71 #include "llvm/IR/BasicBlock.h"
  72 #include "llvm/IR/CallSite.h"
  73 #include "llvm/IR/CallingConv.h"
  74 #include "llvm/IR/Constant.h"
  75 #include "llvm/IR/Constants.h"
  76 #include "llvm/IR/DataLayout.h"
  77 #include "llvm/IR/DebugInfo.h"
  78 #include "llvm/IR/DebugLoc.h"
  79 #include "llvm/IR/DerivedTypes.h"
  80 #include "llvm/IR/Function.h"
  81 #include "llvm/IR/GetElementPtrTypeIterator.h"
  82 #include "llvm/IR/GlobalValue.h"
  83 #include "llvm/IR/InlineAsm.h"
  84 #include "llvm/IR/InstrTypes.h"
  85 #include "llvm/IR/Instruction.h"
  86 #include "llvm/IR/Instructions.h"
  87 #include "llvm/IR/IntrinsicInst.h"
  88 #include "llvm/IR/LLVMContext.h"
  89 #include "llvm/IR/Mangler.h"
  90 #include "llvm/IR/Metadata.h"
  91 #include "llvm/IR/Operator.h"
  92 #include "llvm/IR/Type.h"
  93 #include "llvm/IR/User.h"
  94 #include "llvm/IR/Value.h"
  95 #include "llvm/MC/MCContext.h"
  96 #include "llvm/MC/MCInstrDesc.h"
  97 #include "llvm/MC/MCRegisterInfo.h"
  98 #include "llvm/Support/Casting.h"
  99 #include "llvm/Support/Debug.h"
 100 #include "llvm/Support/ErrorHandling.h"
 101 #include "llvm/Support/MachineValueType.h"
 102 #include "llvm/Support/MathExtras.h"
 103 #include "llvm/Support/raw_ostream.h"
 104 #include "llvm/Target/TargetMachine.h"
 105 #include "llvm/Target/TargetOptions.h"
 106 #include <algorithm>
 107 #include <cassert>
 108 #include <cstdint>
 109 #include <iterator>
 110 #include <utility>
 111
 112 using namespace llvm;
 113
 114 #define DEBUG_TYPE "isel"
 115
 116 // FIXME: Remove this after the feature has proven reliable.
 117 static cl::opt<bool> SinkLocalValues("fast-isel-sink-local-values",
 118                                      cl::init(true), cl::Hidden,
 119                                      cl::desc("Sink local values in FastISel"));
 120
 121 STATISTIC(NumFastIselSuccessIndependent, "Number of insts selected by "
 122                                          "target-independent selector");
 123 STATISTIC(NumFastIselSuccessTarget, "Number of insts selected by "
 124                                     "target-specific selector");
 125 STATISTIC(NumFastIselDead, "Number of dead insts removed on failure");
 126
 127 /// Set the current block to which generated machine instructions will be
 128 /// appended.
 129 void FastISel::startNewBlock() {
 130   assert(LocalValueMap.empty() &&
 131          "local values should be cleared after finishing a BB");
 132
 133   // Instructions are appended to FuncInfo.MBB. If the basic block already
 134   // contains labels or copies, use the last instruction as the last local
 135   // value.
 136   EmitStartPt = nullptr;
 137   if (!FuncInfo.MBB->empty())
 138     EmitStartPt = &FuncInfo.MBB->back();
 139   LastLocalValue = EmitStartPt;
 140 }
 141
 142 /// Flush the local CSE map and sink anything we can.
 143 void FastISel::finishBasicBlock() { flushLocalValueMap(); }
 144
 145 bool FastISel::lowerArguments() {
 146   if (!FuncInfo.CanLowerReturn)
 147     // Fallback to SDISel argument lowering code to deal with sret pointer
 148     // parameter.
 149     return false;
 150
 151   if (!fastLowerArguments())
 152     return false;
 153
 154   // Enter arguments into ValueMap for uses in non-entry BBs.
 155   for (Function::const_arg_iterator I = FuncInfo.Fn->arg_begin(),
 156                                     E = FuncInfo.Fn->arg_end();
 157        I != E; ++I) {
 158     DenseMap<const Value *, unsigned>::iterator VI = LocalValueMap.find(&*I);
 159     assert(VI != LocalValueMap.end() && "Missed an argument?");
 160     FuncInfo.ValueMap[&*I] = VI->second;
 161   }
 162   return true;
 163 }
 164
 165 /// Return the defined register if this instruction defines exactly one
 166 /// virtual register and uses no other virtual registers. Otherwise return 0.
 167 static unsigned findSinkableLocalRegDef(MachineInstr &MI) {
 168   unsigned RegDef = 0;
 169   for (const MachineOperand &MO : MI.operands()) {
 170     if (!MO.isReg())
 171       continue;
 172     if (MO.isDef()) {
 173       if (RegDef)
 174         return 0;
 175       RegDef = MO.getReg();
 176     } else if (TargetRegisterInfo::isVirtualRegister(MO.getReg())) {
 177       // This is another use of a vreg. Don't try to sink it.
 178       return 0;
 179     }
 180   }
 181   return RegDef;
 182 }
 183
 184 void FastISel::flushLocalValueMap() {
 185   // Try to sink local values down to their first use so that we can give them a
 186   // better debug location. This has the side effect of shrinking local value
 187   // live ranges, which helps out fast regalloc.
 188   if (SinkLocalValues && LastLocalValue != EmitStartPt) {
 189     // Sink local value materialization instructions between EmitStartPt and
 190     // LastLocalValue. Visit them bottom-up, starting from LastLocalValue, to
 191     // avoid inserting into the range that we're iterating over.
 192     MachineBasicBlock::reverse_iterator RE =
 193         EmitStartPt ? MachineBasicBlock::reverse_iterator(EmitStartPt)
 194                     : FuncInfo.MBB->rend();
 195     MachineBasicBlock::reverse_iterator RI(LastLocalValue);
 196
 197     InstOrderMap OrderMap;
 198     for (; RI != RE;) {
 199       MachineInstr &LocalMI = *RI;
 200       ++RI;
 201       bool Store = true;
 202       if (!LocalMI.isSafeToMove(nullptr, Store))
 203         continue;
 204       unsigned DefReg = findSinkableLocalRegDef(LocalMI);
 205       if (DefReg == 0)
 206         continue;
 207
 208       sinkLocalValueMaterialization(LocalMI, DefReg, OrderMap);
 209     }
 210   }
 211
 212   LocalValueMap.clear();
 213   LastLocalValue = EmitStartPt;
 214   recomputeInsertPt();
 215   SavedInsertPt = FuncInfo.InsertPt;
 216   LastFlushPoint = FuncInfo.InsertPt;
 217 }
 218
 219 static bool isRegUsedByPhiNodes(unsigned DefReg,
 220                                 FunctionLoweringInfo &FuncInfo) {
 221   for (auto &P : FuncInfo.PHINodesToUpdate)
 222     if (P.second == DefReg)
 223       return true;
 224   return false;
 225 }
 226
 227 /// Build a map of instruction orders. Return the first terminator and its
 228 /// order. Consider EH_LABEL instructions to be terminators as well, since local
 229 /// values for phis after invokes must be materialized before the call.
 230 void FastISel::InstOrderMap::initialize(
 231     MachineBasicBlock *MBB, MachineBasicBlock::iterator LastFlushPoint) {
 232   unsigned Order = 0;
 233   for (MachineInstr &I : *MBB) {
 234     if (!FirstTerminator &&
 235         (I.isTerminator() || (I.isEHLabel() && &I != &MBB->front()))) {
 236       FirstTerminator = &I;
 237       FirstTerminatorOrder = Order;
 238     }
 239     Orders[&I] = Order++;
 240
 241     // We don't need to order instructions past the last flush point.
 242     if (I.getIterator() == LastFlushPoint)
 243       break;
 244   }
 245 }
 246
 247 void FastISel::sinkLocalValueMaterialization(MachineInstr &LocalMI,
 248                                              unsigned DefReg,
 249                                              InstOrderMap &OrderMap) {
 250   // If this register is used by a register fixup, MRI will not contain all
 251   // the uses until after register fixups, so don't attempt to sink or DCE
 252   // this instruction. Register fixups typically come from no-op cast
 253   // instructions, which replace the cast instruction vreg with the local
 254   // value vreg.
 255   if (FuncInfo.RegsWithFixups.count(DefReg))
 256     return;
 257
 258   // We can DCE this instruction if there are no uses and it wasn't a
 259   // materialized for a successor PHI node.
 260   bool UsedByPHI = isRegUsedByPhiNodes(DefReg, FuncInfo);
 261   if (!UsedByPHI && MRI.use_nodbg_empty(DefReg)) {
 262     if (EmitStartPt == &LocalMI)
 263       EmitStartPt = EmitStartPt->getPrevNode();
 264     LLVM_DEBUG(dbgs() << "removing dead local value materialization "
 265                       << LocalMI);
 266     OrderMap.Orders.erase(&LocalMI);
 267     LocalMI.eraseFromParent();
 268     return;
 269   }
 270
 271   // Number the instructions if we haven't yet so we can efficiently find the
 272   // earliest use.
 273   if (OrderMap.Orders.empty())
 274     OrderMap.initialize(FuncInfo.MBB, LastFlushPoint);
 275
 276   // Find the first user in the BB.
 277   MachineInstr *FirstUser = nullptr;
 278   unsigned FirstOrder = std::numeric_limits<unsigned>::max();
 279   for (MachineInstr &UseInst : MRI.use_nodbg_instructions(DefReg)) {
 280     auto I = OrderMap.Orders.find(&UseInst);
 281     assert(I != OrderMap.Orders.end() &&
 282            "local value used by instruction outside local region");
 283     unsigned UseOrder = I->second;
 284     if (UseOrder < FirstOrder) {
 285       FirstOrder = UseOrder;
 286       FirstUser = &UseInst;
 287     }
 288   }
 289
 290   // The insertion point will be the first terminator or the first user,
 291   // whichever came first. If there was no terminator, this must be a
 292   // fallthrough block and the insertion point is the end of the block.
 293   MachineBasicBlock::instr_iterator SinkPos;
 294   if (UsedByPHI && OrderMap.FirstTerminatorOrder < FirstOrder) {
 295     FirstOrder = OrderMap.FirstTerminatorOrder;
 296     SinkPos = OrderMap.FirstTerminator->getIterator();
 297   } else if (FirstUser) {
 298     SinkPos = FirstUser->getIterator();
 299   } else {
 300     assert(UsedByPHI && "must be users if not used by a phi");
 301     SinkPos = FuncInfo.MBB->instr_end();
 302   }
 303
 304   // Collect all DBG_VALUEs before the new insertion position so that we can
 305   // sink them.
 306   SmallVector<MachineInstr *, 1> DbgValues;
 307   for (MachineInstr &DbgVal : MRI.use_instructions(DefReg)) {
 308     if (!DbgVal.isDebugValue())
 309       continue;
 310     unsigned UseOrder = OrderMap.Orders[&DbgVal];
 311     if (UseOrder < FirstOrder)
 312       DbgValues.push_back(&DbgVal);
 313   }
 314
 315   // Sink LocalMI before SinkPos and assign it the same DebugLoc.
 316   LLVM_DEBUG(dbgs() << "sinking local value to first use " << LocalMI);
 317   FuncInfo.MBB->remove(&LocalMI);
 318   FuncInfo.MBB->insert(SinkPos, &LocalMI);
 319   if (SinkPos != FuncInfo.MBB->end())
 320     LocalMI.setDebugLoc(SinkPos->getDebugLoc());
 321
 322   // Sink any debug values that we've collected.
 323   for (MachineInstr *DI : DbgValues) {
 324     FuncInfo.MBB->remove(DI);
 325     FuncInfo.MBB->insert(SinkPos, DI);
 326   }
 327 }
 328
 329 bool FastISel::hasTrivialKill(const Value *V) {
 330   // Don't consider constants or arguments to have trivial kills.
 331   const Instruction *I = dyn_cast<Instruction>(V);
 332   if (!I)
 333     return false;
 334
 335   // No-op casts are trivially coalesced by fast-isel.
 336   if (const auto *Cast = dyn_cast<CastInst>(I))
 337     if (Cast->isNoopCast(DL) && !hasTrivialKill(Cast->getOperand(0)))
 338       return false;
 339
 340   // Even the value might have only one use in the LLVM IR, it is possible that
 341   // FastISel might fold the use into another instruction and now there is more
 342   // than one use at the Machine Instruction level.
 343   unsigned Reg = lookUpRegForValue(V);
 344   if (Reg && !MRI.use_empty(Reg))
 345     return false;
 346
 347   // GEPs with all zero indices are trivially coalesced by fast-isel.
 348   if (const auto *GEP = dyn_cast<GetElementPtrInst>(I))
 349     if (GEP->hasAllZeroIndices() && !hasTrivialKill(GEP->getOperand(0)))
 350       return false;
 351
 352   // Only instructions with a single use in the same basic block are considered
 353   // to have trivial kills.
 354   return I->hasOneUse() &&
 355          !(I->getOpcode() == Instruction::BitCast ||
 356            I->getOpcode() == Instruction::PtrToInt ||
 357            I->getOpcode() == Instruction::IntToPtr) &&
 358          cast<Instruction>(*I->user_begin())->getParent() == I->getParent();
 359 }
 360
 361 unsigned FastISel::getRegForValue(const Value *V) {
 362   EVT RealVT = TLI.getValueType(DL, V->getType(), /*AllowUnknown=*/true);
 363   // Don't handle non-simple values in FastISel.
 364   if (!RealVT.isSimple())
 365     return 0;
 366
 367   // Ignore illegal types. We must do this before looking up the value
 368   // in ValueMap because Arguments are given virtual registers regardless
 369   // of whether FastISel can handle them.
 370   MVT VT = RealVT.getSimpleVT();
 371   if (!TLI.isTypeLegal(VT)) {
 372     // Handle integer promotions, though, because they're common and easy.
 373     if (VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16)
 374       VT = TLI.getTypeToTransformTo(V->getContext(), VT).getSimpleVT();
 375     else
 376       return 0;
 377   }
 378
 379   // Look up the value to see if we already have a register for it.
 380   unsigned Reg = lookUpRegForValue(V);
 381   if (Reg)
 382     return Reg;
 383
 384   // In bottom-up mode, just create the virtual register which will be used
 385   // to hold the value. It will be materialized later.
 386   if (isa<Instruction>(V) &&
 387       (!isa<AllocaInst>(V) ||
 388        !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(V))))
 389     return FuncInfo.InitializeRegForValue(V);
 390
 391   SavePoint SaveInsertPt = enterLocalValueArea();
 392
 393   // Materialize the value in a register. Emit any instructions in the
 394   // local value area.
 395   Reg = materializeRegForValue(V, VT);
 396
 397   leaveLocalValueArea(SaveInsertPt);
 398
 399   return Reg;
 400 }
 401
 402 unsigned FastISel::materializeConstant(const Value *V, MVT VT) {
 403   unsigned Reg = 0;
 404   if (const auto *CI = dyn_cast<ConstantInt>(V)) {
 405     if (CI->getValue().getActiveBits() <= 64)
 406       Reg = fastEmit_i(VT, VT, ISD::Constant, CI->getZExtValue());
 407   } else if (isa<AllocaInst>(V))
 408     Reg = fastMaterializeAlloca(cast<AllocaInst>(V));
 409   else if (isa<ConstantPointerNull>(V))
 410     // Translate this as an integer zero so that it can be
 411     // local-CSE'd with actual integer zeros.
 412     Reg = getRegForValue(
 413         Constant::getNullValue(DL.getIntPtrType(V->getContext())));
 414   else if (const auto *CF = dyn_cast<ConstantFP>(V)) {
 415     if (CF->isNullValue())
 416       Reg = fastMaterializeFloatZero(CF);
 417     else
 418       // Try to emit the constant directly.
 419       Reg = fastEmit_f(VT, VT, ISD::ConstantFP, CF);
 420
 421     if (!Reg) {
 422       // Try to emit the constant by using an integer constant with a cast.
 423       const APFloat &Flt = CF->getValueAPF();
 424       EVT IntVT = TLI.getPointerTy(DL);
 425       uint32_t IntBitWidth = IntVT.getSizeInBits();
 426       APSInt SIntVal(IntBitWidth, /*isUnsigned=*/false);
 427       bool isExact;
 428       (void)Flt.convertToInteger(SIntVal, APFloat::rmTowardZero, &isExact);
 429       if (isExact) {
 430         unsigned IntegerReg =
 431             getRegForValue(ConstantInt::get(V->getContext(), SIntVal));
 432         if (IntegerReg != 0)
 433           Reg = fastEmit_r(IntVT.getSimpleVT(), VT, ISD::SINT_TO_FP, IntegerReg,
 434                            /*Kill=*/false);
 435       }
 436     }
 437   } else if (const auto *Op = dyn_cast<Operator>(V)) {
 438     if (!selectOperator(Op, Op->getOpcode()))
 439       if (!isa<Instruction>(Op) ||
 440           !fastSelectInstruction(cast<Instruction>(Op)))
 441         return 0;
 442     Reg = lookUpRegForValue(Op);
 443   } else if (isa<UndefValue>(V)) {
 444     Reg = createResultReg(TLI.getRegClassFor(VT));
 445     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
 446             TII.get(TargetOpcode::IMPLICIT_DEF), Reg);
 447   }
 448   return Reg;
 449 }
 450
 451 /// Helper for getRegForValue. This function is called when the value isn't
 452 /// already available in a register and must be materialized with new
 453 /// instructions.
 454 unsigned FastISel::materializeRegForValue(const Value *V, MVT VT) {
 455   unsigned Reg = 0;
 456   // Give the target-specific code a try first.
 457   if (isa<Constant>(V))
 458     Reg = fastMaterializeConstant(cast<Constant>(V));
 459
 460   // If target-specific code couldn't or didn't want to handle the value, then
 461   // give target-independent code a try.
 462   if (!Reg)
 463     Reg = materializeConstant(V, VT);
 464
 465   // Don't cache constant materializations in the general ValueMap.
 466   // To do so would require tracking what uses they dominate.
 467   if (Reg) {
 468     LocalValueMap[V] = Reg;
 469     LastLocalValue = MRI.getVRegDef(Reg);
 470   }
 471   return Reg;
 472 }
 473
 474 unsigned FastISel::lookUpRegForValue(const Value *V) {
 475   // Look up the value to see if we already have a register for it. We
 476   // cache values defined by Instructions across blocks, and other values
 477   // only locally. This is because Instructions already have the SSA
 478   // def-dominates-use requirement enforced.
 479   DenseMap<const Value *, unsigned>::iterator I = FuncInfo.ValueMap.find(V);
 480   if (I != FuncInfo.ValueMap.end())
 481     return I->second;
 482   return LocalValueMap[V];
 483 }
 484
 485 void FastISel::updateValueMap(const Value *I, unsigned Reg, unsigned NumRegs) {
 486   if (!isa<Instruction>(I)) {
 487     LocalValueMap[I] = Reg;
 488     return;
 489   }
 490
 491   unsigned &AssignedReg = FuncInfo.ValueMap[I];
 492   if (AssignedReg == 0)
 493     // Use the new register.
 494     AssignedReg = Reg;
 495   else if (Reg != AssignedReg) {
 496     // Arrange for uses of AssignedReg to be replaced by uses of Reg.
 497     for (unsigned i = 0; i < NumRegs; i++) {
 498       FuncInfo.RegFixups[AssignedReg + i] = Reg + i;
 499       FuncInfo.RegsWithFixups.insert(Reg + i);
 500     }
 501
 502     AssignedReg = Reg;
 503   }
 504 }
 505
 506 std::pair<unsigned, bool> FastISel::getRegForGEPIndex(const Value *Idx) {
 507   unsigned IdxN = getRegForValue(Idx);
 508   if (IdxN == 0)
 509     // Unhandled operand. Halt "fast" selection and bail.
 510     return std::pair<unsigned, bool>(0, false);
 511
 512   bool IdxNIsKill = hasTrivialKill(Idx);
 513
 514   // If the index is smaller or larger than intptr_t, truncate or extend it.
 515   MVT PtrVT = TLI.getPointerTy(DL);
 516   EVT IdxVT = EVT::getEVT(Idx->getType(), /*HandleUnknown=*/false);
 517   if (IdxVT.bitsLT(PtrVT)) {
 518     IdxN = fastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::SIGN_EXTEND, IdxN,
 519                       IdxNIsKill);
 520     IdxNIsKill = true;
 521   } else if (IdxVT.bitsGT(PtrVT)) {
 522     IdxN =
 523         fastEmit_r(IdxVT.getSimpleVT(), PtrVT, ISD::TRUNCATE, IdxN, IdxNIsKill);
 524     IdxNIsKill = true;
 525   }
 526   return std::pair<unsigned, bool>(IdxN, IdxNIsKill);
 527 }
 528
 529 void FastISel::recomputeInsertPt() {
 530   if (getLastLocalValue()) {
 531     FuncInfo.InsertPt = getLastLocalValue();
 532     FuncInfo.MBB = FuncInfo.InsertPt->getParent();
 533     ++FuncInfo.InsertPt;
 534   } else
 535     FuncInfo.InsertPt = FuncInfo.MBB->getFirstNonPHI();
 536
 537   // Now skip past any EH_LABELs, which must remain at the beginning.
 538   while (FuncInfo.InsertPt != FuncInfo.MBB->end() &&
 539          FuncInfo.InsertPt->getOpcode() == TargetOpcode::EH_LABEL)
 540     ++FuncInfo.InsertPt;
 541 }
 542
 543 void FastISel::removeDeadCode(MachineBasicBlock::iterator I,
 544                               MachineBasicBlock::iterator E) {
 545   assert(I.isValid() && E.isValid() && std::distance(I, E) > 0 &&
 546          "Invalid iterator!");
 547   while (I != E) {
 548     MachineInstr *Dead = &*I;
 549     ++I;
 550     Dead->eraseFromParent();
 551     ++NumFastIselDead;
 552   }
 553   recomputeInsertPt();
 554 }
 555
 556 FastISel::SavePoint FastISel::enterLocalValueArea() {
 557   MachineBasicBlock::iterator OldInsertPt = FuncInfo.InsertPt;
 558   DebugLoc OldDL = DbgLoc;
 559   recomputeInsertPt();
 560   DbgLoc = DebugLoc();
 561   SavePoint SP = {OldInsertPt, OldDL};
 562   return SP;
 563 }
 564
 565 void FastISel::leaveLocalValueArea(SavePoint OldInsertPt) {
 566   if (FuncInfo.InsertPt != FuncInfo.MBB->begin())
 567     LastLocalValue = &*std::prev(FuncInfo.InsertPt);
 568
 569   // Restore the previous insert position.
 570   FuncInfo.InsertPt = OldInsertPt.InsertPt;
 571   DbgLoc = OldInsertPt.DL;
 572 }
 573
 574 bool FastISel::selectBinaryOp(const User *I, unsigned ISDOpcode) {
 575   EVT VT = EVT::getEVT(I->getType(), /*HandleUnknown=*/true);
 576   if (VT == MVT::Other || !VT.isSimple())
 577     // Unhandled type. Halt "fast" selection and bail.
 578     return false;
 579
 580   // We only handle legal types. For example, on x86-32 the instruction
 581   // selector contains all of the 64-bit instructions from x86-64,
 582   // under the assumption that i64 won't be used if the target doesn't
 583   // support it.
 584   if (!TLI.isTypeLegal(VT)) {
 585     // MVT::i1 is special. Allow AND, OR, or XOR because they
 586     // don't require additional zeroing, which makes them easy.
 587     if (VT == MVT::i1 && (ISDOpcode == ISD::AND || ISDOpcode == ISD::OR ||
 588                           ISDOpcode == ISD::XOR))
 589       VT = TLI.getTypeToTransformTo(I->getContext(), VT);
 590     else
 591       return false;
 592   }
 593
 594   // Check if the first operand is a constant, and handle it as "ri".  At -O0,
 595   // we don't have anything that canonicalizes operand order.
 596   if (const auto *CI = dyn_cast<ConstantInt>(I->getOperand(0)))
 597     if (isa<Instruction>(I) && cast<Instruction>(I)->isCommutative()) {
 598       unsigned Op1 = getRegForValue(I->getOperand(1));
 599       if (!Op1)
 600         return false;
 601       bool Op1IsKill = hasTrivialKill(I->getOperand(1));
 602
 603       unsigned ResultReg =
 604           fastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op1, Op1IsKill,
 605                        CI->getZExtValue(), VT.getSimpleVT());
 606       if (!ResultReg)
 607         return false;
 608
 609       // We successfully emitted code for the given LLVM Instruction.
 610       updateValueMap(I, ResultReg);
 611       return true;
 612     }
 613
 614   unsigned Op0 = getRegForValue(I->getOperand(0));
 615   if (!Op0) // Unhandled operand. Halt "fast" selection and bail.
 616     return false;
 617   bool Op0IsKill = hasTrivialKill(I->getOperand(0));
 618
 619   // Check if the second operand is a constant and handle it appropriately.
 620   if (const auto *CI = dyn_cast<ConstantInt>(I->getOperand(1))) {
 621     uint64_t Imm = CI->getSExtValue();
 622
 623     // Transform "sdiv exact X, 8" -> "sra X, 3".
 624     if (ISDOpcode == ISD::SDIV && isa<BinaryOperator>(I) &&
 625         cast<BinaryOperator>(I)->isExact() && isPowerOf2_64(Imm)) {
 626       Imm = Log2_64(Imm);
 627       ISDOpcode = ISD::SRA;
 628     }
 629
 630     // Transform "urem x, pow2" -> "and x, pow2-1".
 631     if (ISDOpcode == ISD::UREM && isa<BinaryOperator>(I) &&
 632         isPowerOf2_64(Imm)) {
 633       --Imm;
 634       ISDOpcode = ISD::AND;
 635     }
 636
 637     unsigned ResultReg = fastEmit_ri_(VT.getSimpleVT(), ISDOpcode, Op0,
 638                                       Op0IsKill, Imm, VT.getSimpleVT());
 639     if (!ResultReg)
 640       return false;
 641
 642     // We successfully emitted code for the given LLVM Instruction.
 643     updateValueMap(I, ResultReg);
 644     return true;
 645   }
 646
 647   unsigned Op1 = getRegForValue(I->getOperand(1));
 648   if (!Op1) // Unhandled operand. Halt "fast" selection and bail.
 649     return false;
 650   bool Op1IsKill = hasTrivialKill(I->getOperand(1));
 651
 652   // Now we have both operands in registers. Emit the instruction.
 653   unsigned ResultReg = fastEmit_rr(VT.getSimpleVT(), VT.getSimpleVT(),
 654                                    ISDOpcode, Op0, Op0IsKill, Op1, Op1IsKill);
 655   if (!ResultReg)
 656     // Target-specific code wasn't able to find a machine opcode for
 657     // the given ISD opcode and type. Halt "fast" selection and bail.
 658     return false;
 659
 660   // We successfully emitted code for the given LLVM Instruction.
 661   updateValueMap(I, ResultReg);
 662   return true;
 663 }
 664
 665 bool FastISel::selectGetElementPtr(const User *I) {
 666   unsigned N = getRegForValue(I->getOperand(0));
 667   if (!N) // Unhandled operand. Halt "fast" selection and bail.
 668     return false;
 669   bool NIsKill = hasTrivialKill(I->getOperand(0));
 670
 671   // Keep a running tab of the total offset to coalesce multiple N = N + Offset
 672   // into a single N = N + TotalOffset.
 673   uint64_t TotalOffs = 0;
 674   // FIXME: What's a good SWAG number for MaxOffs?
 675   uint64_t MaxOffs = 2048;
 676   MVT VT = TLI.getPointerTy(DL);
 677   for (gep_type_iterator GTI = gep_type_begin(I), E = gep_type_end(I);
 678        GTI != E; ++GTI) {
 679     const Value *Idx = GTI.getOperand();
 680     if (StructType *StTy = GTI.getStructTypeOrNull()) {
 681       uint64_t Field = cast<ConstantInt>(Idx)->getZExtValue();
 682       if (Field) {
 683         // N = N + Offset
 684         TotalOffs += DL.getStructLayout(StTy)->getElementOffset(Field);
 685         if (TotalOffs >= MaxOffs) {
 686           N = fastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
 687           if (!N) // Unhandled operand. Halt "fast" selection and bail.
 688             return false;
 689           NIsKill = true;
 690           TotalOffs = 0;
 691         }
 692       }
 693     } else {
 694       Type *Ty = GTI.getIndexedType();
 695
 696       // If this is a constant subscript, handle it quickly.
 697       if (const auto *CI = dyn_cast<ConstantInt>(Idx)) {
 698         if (CI->isZero())
 699           continue;
 700         // N = N + Offset
 701         uint64_t IdxN = CI->getValue().sextOrTrunc(64).getSExtValue();
 702         TotalOffs += DL.getTypeAllocSize(Ty) * IdxN;
 703         if (TotalOffs >= MaxOffs) {
 704           N = fastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
 705           if (!N) // Unhandled operand. Halt "fast" selection and bail.
 706             return false;
 707           NIsKill = true;
 708           TotalOffs = 0;
 709         }
 710         continue;
 711       }
 712       if (TotalOffs) {
 713         N = fastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
 714         if (!N) // Unhandled operand. Halt "fast" selection and bail.
 715           return false;
 716         NIsKill = true;
 717         TotalOffs = 0;
 718       }
 719
 720       // N = N + Idx * ElementSize;
 721       uint64_t ElementSize = DL.getTypeAllocSize(Ty);
 722       std::pair<unsigned, bool> Pair = getRegForGEPIndex(Idx);
 723       unsigned IdxN = Pair.first;
 724       bool IdxNIsKill = Pair.second;
 725       if (!IdxN) // Unhandled operand. Halt "fast" selection and bail.
 726         return false;
 727
 728       if (ElementSize != 1) {
 729         IdxN = fastEmit_ri_(VT, ISD::MUL, IdxN, IdxNIsKill, ElementSize, VT);
 730         if (!IdxN) // Unhandled operand. Halt "fast" selection and bail.
 731           return false;
 732         IdxNIsKill = true;
 733       }
 734       N = fastEmit_rr(VT, VT, ISD::ADD, N, NIsKill, IdxN, IdxNIsKill);
 735       if (!N) // Unhandled operand. Halt "fast" selection and bail.
 736         return false;
 737     }
 738   }
 739   if (TotalOffs) {
 740     N = fastEmit_ri_(VT, ISD::ADD, N, NIsKill, TotalOffs, VT);
 741     if (!N) // Unhandled operand. Halt "fast" selection and bail.
 742       return false;
 743   }
 744
 745   // We successfully emitted code for the given LLVM Instruction.
 746   updateValueMap(I, N);
 747   return true;
 748 }
 749
 750 bool FastISel::addStackMapLiveVars(SmallVectorImpl<MachineOperand> &Ops,
 751                                    const CallInst *CI, unsigned StartIdx) {
 752   for (unsigned i = StartIdx, e = CI->getNumArgOperands(); i != e; ++i) {
 753     Value *Val = CI->getArgOperand(i);
 754     // Check for constants and encode them with a StackMaps::ConstantOp prefix.
 755     if (const auto *C = dyn_cast<ConstantInt>(Val)) {
 756       Ops.push_back(MachineOperand::CreateImm(StackMaps::ConstantOp));
 757       Ops.push_back(MachineOperand::CreateImm(C->getSExtValue()));
 758     } else if (isa<ConstantPointerNull>(Val)) {
 759       Ops.push_back(MachineOperand::CreateImm(StackMaps::ConstantOp));
 760       Ops.push_back(MachineOperand::CreateImm(0));
 761     } else if (auto *AI = dyn_cast<AllocaInst>(Val)) {
 762       // Values coming from a stack location also require a special encoding,
 763       // but that is added later on by the target specific frame index
 764       // elimination implementation.
 765       auto SI = FuncInfo.StaticAllocaMap.find(AI);
 766       if (SI != FuncInfo.StaticAllocaMap.end())
 767         Ops.push_back(MachineOperand::CreateFI(SI->second));
 768       else
 769         return false;
 770     } else {
 771       unsigned Reg = getRegForValue(Val);
 772       if (!Reg)
 773         return false;
 774       Ops.push_back(MachineOperand::CreateReg(Reg, /*IsDef=*/false));
 775     }
 776   }
 777   return true;
 778 }
 779
 780 bool FastISel::selectStackmap(const CallInst *I) {
 781   // void @llvm.experimental.stackmap(i64 <id>, i32 <numShadowBytes>,
 782   //                                  [live variables...])
 783   assert(I->getCalledFunction()->getReturnType()->isVoidTy() &&
 784          "Stackmap cannot return a value.");
 785
 786   // The stackmap intrinsic only records the live variables (the arguments
 787   // passed to it) and emits NOPS (if requested). Unlike the patchpoint
 788   // intrinsic, this won't be lowered to a function call. This means we don't
 789   // have to worry about calling conventions and target-specific lowering code.
 790   // Instead we perform the call lowering right here.
 791   //
 792   // CALLSEQ_START(0, 0...)
 793   // STACKMAP(id, nbytes, ...)
 794   // CALLSEQ_END(0, 0)
 795   //
 796   SmallVector<MachineOperand, 32> Ops;
 797
 798   // Add the <id> and <numBytes> constants.
 799   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::IDPos)) &&
 800          "Expected a constant integer.");
 801   const auto *ID = cast<ConstantInt>(I->getOperand(PatchPointOpers::IDPos));
 802   Ops.push_back(MachineOperand::CreateImm(ID->getZExtValue()));
 803
 804   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos)) &&
 805          "Expected a constant integer.");
 806   const auto *NumBytes =
 807       cast<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos));
 808   Ops.push_back(MachineOperand::CreateImm(NumBytes->getZExtValue()));
 809
 810   // Push live variables for the stack map (skipping the first two arguments
 811   // <id> and <numBytes>).
 812   if (!addStackMapLiveVars(Ops, I, 2))
 813     return false;
 814
 815   // We are not adding any register mask info here, because the stackmap doesn't
 816   // clobber anything.
 817
 818   // Add scratch registers as implicit def and early clobber.
 819   CallingConv::ID CC = I->getCallingConv();
 820   const MCPhysReg *ScratchRegs = TLI.getScratchRegisters(CC);
 821   for (unsigned i = 0; ScratchRegs[i]; ++i)
 822     Ops.push_back(MachineOperand::CreateReg(
 823         ScratchRegs[i], /*IsDef=*/true, /*IsImp=*/true, /*IsKill=*/false,
 824         /*IsDead=*/false, /*IsUndef=*/false, /*IsEarlyClobber=*/true));
 825
 826   // Issue CALLSEQ_START
 827   unsigned AdjStackDown = TII.getCallFrameSetupOpcode();
 828   auto Builder =
 829       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AdjStackDown));
 830   const MCInstrDesc &MCID = Builder.getInstr()->getDesc();
 831   for (unsigned I = 0, E = MCID.getNumOperands(); I < E; ++I)
 832     Builder.addImm(0);
 833
 834   // Issue STACKMAP.
 835   MachineInstrBuilder MIB = BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
 836                                     TII.get(TargetOpcode::STACKMAP));
 837   for (auto const &MO : Ops)
 838     MIB.add(MO);
 839
 840   // Issue CALLSEQ_END
 841   unsigned AdjStackUp = TII.getCallFrameDestroyOpcode();
 842   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(AdjStackUp))
 843       .addImm(0)
 844       .addImm(0);
 845
 846   // Inform the Frame Information that we have a stackmap in this function.
 847   FuncInfo.MF->getFrameInfo().setHasStackMap();
 848
 849   return true;
 850 }
 851
 852 /// Lower an argument list according to the target calling convention.
 853 ///
 854 /// This is a helper for lowering intrinsics that follow a target calling
 855 /// convention or require stack pointer adjustment. Only a subset of the
 856 /// intrinsic's operands need to participate in the calling convention.
 857 bool FastISel::lowerCallOperands(const CallInst *CI, unsigned ArgIdx,
 858                                  unsigned NumArgs, const Value *Callee,
 859                                  bool ForceRetVoidTy, CallLoweringInfo &CLI) {
 860   ArgListTy Args;
 861   Args.reserve(NumArgs);
 862
 863   // Populate the argument list.
 864   ImmutableCallSite CS(CI);
 865   for (unsigned ArgI = ArgIdx, ArgE = ArgIdx + NumArgs; ArgI != ArgE; ++ArgI) {
 866     Value *V = CI->getOperand(ArgI);
 867
 868     assert(!V->getType()->isEmptyTy() && "Empty type passed to intrinsic.");
 869
 870     ArgListEntry Entry;
 871     Entry.Val = V;
 872     Entry.Ty = V->getType();
 873     Entry.setAttributes(&CS, ArgI);
 874     Args.push_back(Entry);
 875   }
 876
 877   Type *RetTy = ForceRetVoidTy ? Type::getVoidTy(CI->getType()->getContext())
 878                                : CI->getType();
 879   CLI.setCallee(CI->getCallingConv(), RetTy, Callee, std::move(Args), NumArgs);
 880
 881   return lowerCallTo(CLI);
 882 }
 883
 884 FastISel::CallLoweringInfo &FastISel::CallLoweringInfo::setCallee(
 885     const DataLayout &DL, MCContext &Ctx, CallingConv::ID CC, Type *ResultTy,
 886     StringRef Target, ArgListTy &&ArgsList, unsigned FixedArgs) {
 887   SmallString<32> MangledName;
 888   Mangler::getNameWithPrefix(MangledName, Target, DL);
 889   MCSymbol *Sym = Ctx.getOrCreateSymbol(MangledName);
 890   return setCallee(CC, ResultTy, Sym, std::move(ArgsList), FixedArgs);
 891 }
 892
 893 bool FastISel::selectPatchpoint(const CallInst *I) {
 894   // void|i64 @llvm.experimental.patchpoint.void|i64(i64 <id>,
 895   //                                                 i32 <numBytes>,
 896   //                                                 i8* <target>,
 897   //                                                 i32 <numArgs>,
 898   //                                                 [Args...],
 899   //                                                 [live variables...])
 900   CallingConv::ID CC = I->getCallingConv();
 901   bool IsAnyRegCC = CC == CallingConv::AnyReg;
 902   bool HasDef = !I->getType()->isVoidTy();
 903   Value *Callee = I->getOperand(PatchPointOpers::TargetPos)->stripPointerCasts();
 904
 905   // Get the real number of arguments participating in the call <numArgs>
 906   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NArgPos)) &&
 907          "Expected a constant integer.");
 908   const auto *NumArgsVal =
 909       cast<ConstantInt>(I->getOperand(PatchPointOpers::NArgPos));
 910   unsigned NumArgs = NumArgsVal->getZExtValue();
 911
 912   // Skip the four meta args: <id>, <numNopBytes>, <target>, <numArgs>
 913   // This includes all meta-operands up to but not including CC.
 914   unsigned NumMetaOpers = PatchPointOpers::CCPos;
 915   assert(I->getNumArgOperands() >= NumMetaOpers + NumArgs &&
 916          "Not enough arguments provided to the patchpoint intrinsic");
 917
 918   // For AnyRegCC the arguments are lowered later on manually.
 919   unsigned NumCallArgs = IsAnyRegCC ? 0 : NumArgs;
 920   CallLoweringInfo CLI;
 921   CLI.setIsPatchPoint();
 922   if (!lowerCallOperands(I, NumMetaOpers, NumCallArgs, Callee, IsAnyRegCC, CLI))
 923     return false;
 924
 925   assert(CLI.Call && "No call instruction specified.");
 926
 927   SmallVector<MachineOperand, 32> Ops;
 928
 929   // Add an explicit result reg if we use the anyreg calling convention.
 930   if (IsAnyRegCC && HasDef) {
 931     assert(CLI.NumResultRegs == 0 && "Unexpected result register.");
 932     CLI.ResultReg = createResultReg(TLI.getRegClassFor(MVT::i64));
 933     CLI.NumResultRegs = 1;
 934     Ops.push_back(MachineOperand::CreateReg(CLI.ResultReg, /*IsDef=*/true));
 935   }
 936
 937   // Add the <id> and <numBytes> constants.
 938   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::IDPos)) &&
 939          "Expected a constant integer.");
 940   const auto *ID = cast<ConstantInt>(I->getOperand(PatchPointOpers::IDPos));
 941   Ops.push_back(MachineOperand::CreateImm(ID->getZExtValue()));
 942
 943   assert(isa<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos)) &&
 944          "Expected a constant integer.");
 945   const auto *NumBytes =
 946       cast<ConstantInt>(I->getOperand(PatchPointOpers::NBytesPos));
 947   Ops.push_back(MachineOperand::CreateImm(NumBytes->getZExtValue()));
 948
 949   // Add the call target.
 950   if (const auto *C = dyn_cast<IntToPtrInst>(Callee)) {
 951     uint64_t CalleeConstAddr =
 952       cast<ConstantInt>(C->getOperand(0))->getZExtValue();
 953     Ops.push_back(MachineOperand::CreateImm(CalleeConstAddr));
 954   } else if (const auto *C = dyn_cast<ConstantExpr>(Callee)) {
 955     if (C->getOpcode() == Instruction::IntToPtr) {
 956       uint64_t CalleeConstAddr =
 957         cast<ConstantInt>(C->getOperand(0))->getZExtValue();
 958       Ops.push_back(MachineOperand::CreateImm(CalleeConstAddr));
 959     } else
 960       llvm_unreachable("Unsupported ConstantExpr.");
 961   } else if (const auto *GV = dyn_cast<GlobalValue>(Callee)) {
 962     Ops.push_back(MachineOperand::CreateGA(GV, 0));
 963   } else if (isa<ConstantPointerNull>(Callee))
 964     Ops.push_back(MachineOperand::CreateImm(0));
 965   else
 966     llvm_unreachable("Unsupported callee address.");
 967
 968   // Adjust <numArgs> to account for any arguments that have been passed on
 969   // the stack instead.
 970   unsigned NumCallRegArgs = IsAnyRegCC ? NumArgs : CLI.OutRegs.size();
 971   Ops.push_back(MachineOperand::CreateImm(NumCallRegArgs));
 972
 973   // Add the calling convention
 974   Ops.push_back(MachineOperand::CreateImm((unsigned)CC));
 975
 976   // Add the arguments we omitted previously. The register allocator should
 977   // place these in any free register.
 978   if (IsAnyRegCC) {
 979     for (unsigned i = NumMetaOpers, e = NumMetaOpers + NumArgs; i != e; ++i) {
 980       unsigned Reg = getRegForValue(I->getArgOperand(i));
 981       if (!Reg)
 982         return false;
 983       Ops.push_back(MachineOperand::CreateReg(Reg, /*IsDef=*/false));
 984     }
 985   }
 986
 987   // Push the arguments from the call instruction.
 988   for (auto Reg : CLI.OutRegs)
 989     Ops.push_back(MachineOperand::CreateReg(Reg, /*IsDef=*/false));
 990
 991   // Push live variables for the stack map.
 992   if (!addStackMapLiveVars(Ops, I, NumMetaOpers + NumArgs))
 993     return false;
 994
 995   // Push the register mask info.
 996   Ops.push_back(MachineOperand::CreateRegMask(
 997       TRI.getCallPreservedMask(*FuncInfo.MF, CC)));
 998
 999   // Add scratch registers as implicit def and early clobber.
1000   const MCPhysReg *ScratchRegs = TLI.getScratchRegisters(CC);
1001   for (unsigned i = 0; ScratchRegs[i]; ++i)
1002     Ops.push_back(MachineOperand::CreateReg(
1003         ScratchRegs[i], /*IsDef=*/true, /*IsImp=*/true, /*IsKill=*/false,
1004         /*IsDead=*/false, /*IsUndef=*/false, /*IsEarlyClobber=*/true));
1005
1006   // Add implicit defs (return values).
1007   for (auto Reg : CLI.InRegs)
1008     Ops.push_back(MachineOperand::CreateReg(Reg, /*IsDef=*/true,
1009                                             /*IsImpl=*/true));
1010
1011   // Insert the patchpoint instruction before the call generated by the target.
1012   MachineInstrBuilder MIB = BuildMI(*FuncInfo.MBB, CLI.Call, DbgLoc,
1013                                     TII.get(TargetOpcode::PATCHPOINT));
1014
1015   for (auto &MO : Ops)
1016     MIB.add(MO);
1017
1018   MIB->setPhysRegsDeadExcept(CLI.InRegs, TRI);
1019
1020   // Delete the original call instruction.
1021   CLI.Call->eraseFromParent();
1022
1023   // Inform the Frame Information that we have a patchpoint in this function.
1024   FuncInfo.MF->getFrameInfo().setHasPatchPoint();
1025
1026   if (CLI.NumResultRegs)
1027     updateValueMap(I, CLI.ResultReg, CLI.NumResultRegs);
1028   return true;
1029 }
1030
1031 bool FastISel::selectXRayCustomEvent(const CallInst *I) {
1032   const auto &Triple = TM.getTargetTriple();
1033   if (Triple.getArch() != Triple::x86_64 || !Triple.isOSLinux())
1034     return true; // don't do anything to this instruction.
1035   SmallVector<MachineOperand, 8> Ops;
1036   Ops.push_back(MachineOperand::CreateReg(getRegForValue(I->getArgOperand(0)),
1037                                           /*IsDef=*/false));
1038   Ops.push_back(MachineOperand::CreateReg(getRegForValue(I->getArgOperand(1)),
1039                                           /*IsDef=*/false));
1040   MachineInstrBuilder MIB =
1041       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1042               TII.get(TargetOpcode::PATCHABLE_EVENT_CALL));
1043   for (auto &MO : Ops)
1044     MIB.add(MO);
1045
1046   // Insert the Patchable Event Call instruction, that gets lowered properly.
1047   return true;
1048 }
1049
1050 bool FastISel::selectXRayTypedEvent(const CallInst *I) {
1051   const auto &Triple = TM.getTargetTriple();
1052   if (Triple.getArch() != Triple::x86_64 || !Triple.isOSLinux())
1053     return true; // don't do anything to this instruction.
1054   SmallVector<MachineOperand, 8> Ops;
1055   Ops.push_back(MachineOperand::CreateReg(getRegForValue(I->getArgOperand(0)),
1056                                           /*IsDef=*/false));
1057   Ops.push_back(MachineOperand::CreateReg(getRegForValue(I->getArgOperand(1)),
1058                                           /*IsDef=*/false));
1059   Ops.push_back(MachineOperand::CreateReg(getRegForValue(I->getArgOperand(2)),
1060                                           /*IsDef=*/false));
1061   MachineInstrBuilder MIB =
1062       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1063               TII.get(TargetOpcode::PATCHABLE_TYPED_EVENT_CALL));
1064   for (auto &MO : Ops)
1065     MIB.add(MO);
1066
1067   // Insert the Patchable Typed Event Call instruction, that gets lowered properly.
1068   return true;
1069 }
1070
1071 /// Returns an AttributeList representing the attributes applied to the return
1072 /// value of the given call.
1073 static AttributeList getReturnAttrs(FastISel::CallLoweringInfo &CLI) {
1074   SmallVector<Attribute::AttrKind, 2> Attrs;
1075   if (CLI.RetSExt)
1076     Attrs.push_back(Attribute::SExt);
1077   if (CLI.RetZExt)
1078     Attrs.push_back(Attribute::ZExt);
1079   if (CLI.IsInReg)
1080     Attrs.push_back(Attribute::InReg);
1081
1082   return AttributeList::get(CLI.RetTy->getContext(), AttributeList::ReturnIndex,
1083                             Attrs);
1084 }
1085
1086 bool FastISel::lowerCallTo(const CallInst *CI, const char *SymName,
1087                            unsigned NumArgs) {
1088   MCContext &Ctx = MF->getContext();
1089   SmallString<32> MangledName;
1090   Mangler::getNameWithPrefix(MangledName, SymName, DL);
1091   MCSymbol *Sym = Ctx.getOrCreateSymbol(MangledName);
1092   return lowerCallTo(CI, Sym, NumArgs);
1093 }
1094
1095 bool FastISel::lowerCallTo(const CallInst *CI, MCSymbol *Symbol,
1096                            unsigned NumArgs) {
1097   ImmutableCallSite CS(CI);
1098
1099   FunctionType *FTy = CS.getFunctionType();
1100   Type *RetTy = CS.getType();
1101
1102   ArgListTy Args;
1103   Args.reserve(NumArgs);
1104
1105   // Populate the argument list.
1106   // Attributes for args start at offset 1, after the return attribute.
1107   for (unsigned ArgI = 0; ArgI != NumArgs; ++ArgI) {
1108     Value *V = CI->getOperand(ArgI);
1109
1110     assert(!V->getType()->isEmptyTy() && "Empty type passed to intrinsic.");
1111
1112     ArgListEntry Entry;
1113     Entry.Val = V;
1114     Entry.Ty = V->getType();
1115     Entry.setAttributes(&CS, ArgI);
1116     Args.push_back(Entry);
1117   }
1118   TLI.markLibCallAttributes(MF, CS.getCallingConv(), Args);
1119
1120   CallLoweringInfo CLI;
1121   CLI.setCallee(RetTy, FTy, Symbol, std::move(Args), CS, NumArgs);
1122
1123   return lowerCallTo(CLI);
1124 }
1125
1126 bool FastISel::lowerCallTo(CallLoweringInfo &CLI) {
1127   // Handle the incoming return values from the call.
1128   CLI.clearIns();
1129   SmallVector<EVT, 4> RetTys;
1130   ComputeValueVTs(TLI, DL, CLI.RetTy, RetTys);
1131
1132   SmallVector<ISD::OutputArg, 4> Outs;
1133   GetReturnInfo(CLI.CallConv, CLI.RetTy, getReturnAttrs(CLI), Outs, TLI, DL);
1134
1135   bool CanLowerReturn = TLI.CanLowerReturn(
1136       CLI.CallConv, *FuncInfo.MF, CLI.IsVarArg, Outs, CLI.RetTy->getContext());
1137
1138   // FIXME: sret demotion isn't supported yet - bail out.
1139   if (!CanLowerReturn)
1140     return false;
1141
1142   for (unsigned I = 0, E = RetTys.size(); I != E; ++I) {
1143     EVT VT = RetTys[I];
1144     MVT RegisterVT = TLI.getRegisterType(CLI.RetTy->getContext(), VT);
1145     unsigned NumRegs = TLI.getNumRegisters(CLI.RetTy->getContext(), VT);
1146     for (unsigned i = 0; i != NumRegs; ++i) {
1147       ISD::InputArg MyFlags;
1148       MyFlags.VT = RegisterVT;
1149       MyFlags.ArgVT = VT;
1150       MyFlags.Used = CLI.IsReturnValueUsed;
1151       if (CLI.RetSExt)
1152         MyFlags.Flags.setSExt();
1153       if (CLI.RetZExt)
1154         MyFlags.Flags.setZExt();
1155       if (CLI.IsInReg)
1156         MyFlags.Flags.setInReg();
1157       CLI.Ins.push_back(MyFlags);
1158     }
1159   }
1160
1161   // Handle all of the outgoing arguments.
1162   CLI.clearOuts();
1163   for (auto &Arg : CLI.getArgs()) {
1164     Type *FinalType = Arg.Ty;
1165     if (Arg.IsByVal)
1166       FinalType = cast<PointerType>(Arg.Ty)->getElementType();
1167     bool NeedsRegBlock = TLI.functionArgumentNeedsConsecutiveRegisters(
1168         FinalType, CLI.CallConv, CLI.IsVarArg);
1169
1170     ISD::ArgFlagsTy Flags;
1171     if (Arg.IsZExt)
1172       Flags.setZExt();
1173     if (Arg.IsSExt)
1174       Flags.setSExt();
1175     if (Arg.IsInReg)
1176       Flags.setInReg();
1177     if (Arg.IsSRet)
1178       Flags.setSRet();
1179     if (Arg.IsSwiftSelf)
1180       Flags.setSwiftSelf();
1181     if (Arg.IsSwiftError)
1182       Flags.setSwiftError();
1183     if (Arg.IsByVal)
1184       Flags.setByVal();
1185     if (Arg.IsInAlloca) {
1186       Flags.setInAlloca();
1187       // Set the byval flag for CCAssignFn callbacks that don't know about
1188       // inalloca. This way we can know how many bytes we should've allocated
1189       // and how many bytes a callee cleanup function will pop.  If we port
1190       // inalloca to more targets, we'll have to add custom inalloca handling in
1191       // the various CC lowering callbacks.
1192       Flags.setByVal();
1193     }
1194     if (Arg.IsByVal || Arg.IsInAlloca) {
1195       PointerType *Ty = cast<PointerType>(Arg.Ty);
1196       Type *ElementTy = Ty->getElementType();
1197       unsigned FrameSize = DL.getTypeAllocSize(ElementTy);
1198       // For ByVal, alignment should come from FE. BE will guess if this info is
1199       // not there, but there are cases it cannot get right.
1200       unsigned FrameAlign = Arg.Alignment;
1201       if (!FrameAlign)
1202         FrameAlign = TLI.getByValTypeAlignment(ElementTy, DL);
1203       Flags.setByValSize(FrameSize);
1204       Flags.setByValAlign(FrameAlign);
1205     }
1206     if (Arg.IsNest)
1207       Flags.setNest();
1208     if (NeedsRegBlock)
1209       Flags.setInConsecutiveRegs();
1210     unsigned OriginalAlignment = DL.getABITypeAlignment(Arg.Ty);
1211     Flags.setOrigAlign(OriginalAlignment);
1212
1213     CLI.OutVals.push_back(Arg.Val);
1214     CLI.OutFlags.push_back(Flags);
1215   }
1216
1217   if (!fastLowerCall(CLI))
1218     return false;
1219
1220   // Set all unused physreg defs as dead.
1221   assert(CLI.Call && "No call instruction specified.");
1222   CLI.Call->setPhysRegsDeadExcept(CLI.InRegs, TRI);
1223
1224   if (CLI.NumResultRegs && CLI.CS)
1225     updateValueMap(CLI.CS->getInstruction(), CLI.ResultReg, CLI.NumResultRegs);
1226
1227   return true;
1228 }
1229
1230 bool FastISel::lowerCall(const CallInst *CI) {
1231   ImmutableCallSite CS(CI);
1232
1233   FunctionType *FuncTy = CS.getFunctionType();
1234   Type *RetTy = CS.getType();
1235
1236   ArgListTy Args;
1237   ArgListEntry Entry;
1238   Args.reserve(CS.arg_size());
1239
1240   for (ImmutableCallSite::arg_iterator i = CS.arg_begin(), e = CS.arg_end();
1241        i != e; ++i) {
1242     Value *V = *i;
1243
1244     // Skip empty types
1245     if (V->getType()->isEmptyTy())
1246       continue;
1247
1248     Entry.Val = V;
1249     Entry.Ty = V->getType();
1250
1251     // Skip the first return-type Attribute to get to params.
1252     Entry.setAttributes(&CS, i - CS.arg_begin());
1253     Args.push_back(Entry);
1254   }
1255
1256   // Check if target-independent constraints permit a tail call here.
1257   // Target-dependent constraints are checked within fastLowerCall.
1258   bool IsTailCall = CI->isTailCall();
1259   if (IsTailCall && !isInTailCallPosition(CS, TM))
1260     IsTailCall = false;
1261
1262   CallLoweringInfo CLI;
1263   CLI.setCallee(RetTy, FuncTy, CI->getCalledValue(), std::move(Args), CS)
1264       .setTailCall(IsTailCall);
1265
1266   return lowerCallTo(CLI);
1267 }
1268
1269 bool FastISel::selectCall(const User *I) {
1270   const CallInst *Call = cast<CallInst>(I);
1271
1272   // Handle simple inline asms.
1273   if (const InlineAsm *IA = dyn_cast<InlineAsm>(Call->getCalledValue())) {
1274     // If the inline asm has side effects, then make sure that no local value
1275     // lives across by flushing the local value map.
1276     if (IA->hasSideEffects())
1277       flushLocalValueMap();
1278
1279     // Don't attempt to handle constraints.
1280     if (!IA->getConstraintString().empty())
1281       return false;
1282
1283     unsigned ExtraInfo = 0;
1284     if (IA->hasSideEffects())
1285       ExtraInfo |= InlineAsm::Extra_HasSideEffects;
1286     if (IA->isAlignStack())
1287       ExtraInfo |= InlineAsm::Extra_IsAlignStack;
1288
1289     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1290             TII.get(TargetOpcode::INLINEASM))
1291         .addExternalSymbol(IA->getAsmString().c_str())
1292         .addImm(ExtraInfo);
1293     return true;
1294   }
1295
1296   MachineModuleInfo &MMI = FuncInfo.MF->getMMI();
1297   computeUsesVAFloatArgument(*Call, MMI);
1298
1299   // Handle intrinsic function calls.
1300   if (const auto *II = dyn_cast<IntrinsicInst>(Call))
1301     return selectIntrinsicCall(II);
1302
1303   // Usually, it does not make sense to initialize a value,
1304   // make an unrelated function call and use the value, because
1305   // it tends to be spilled on the stack. So, we move the pointer
1306   // to the last local value to the beginning of the block, so that
1307   // all the values which have already been materialized,
1308   // appear after the call. It also makes sense to skip intrinsics
1309   // since they tend to be inlined.
1310   flushLocalValueMap();
1311
1312   return lowerCall(Call);
1313 }
1314
1315 bool FastISel::selectIntrinsicCall(const IntrinsicInst *II) {
1316   switch (II->getIntrinsicID()) {
1317   default:
1318     break;
1319   // At -O0 we don't care about the lifetime intrinsics.
1320   case Intrinsic::lifetime_start:
1321   case Intrinsic::lifetime_end:
1322   // The donothing intrinsic does, well, nothing.
1323   case Intrinsic::donothing:
1324   // Neither does the sideeffect intrinsic.
1325   case Intrinsic::sideeffect:
1326   // Neither does the assume intrinsic; it's also OK not to codegen its operand.
1327   case Intrinsic::assume:
1328     return true;
1329   case Intrinsic::dbg_declare: {
1330     const DbgDeclareInst *DI = cast<DbgDeclareInst>(II);
1331     assert(DI->getVariable() && "Missing variable");
1332     if (!FuncInfo.MF->getMMI().hasDebugInfo()) {
1333       LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
1334       return true;
1335     }
1336
1337     const Value *Address = DI->getAddress();
1338     if (!Address || isa<UndefValue>(Address)) {
1339       LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
1340       return true;
1341     }
1342
1343     // Byval arguments with frame indices were already handled after argument
1344     // lowering and before isel.
1345     const auto *Arg =
1346         dyn_cast<Argument>(Address->stripInBoundsConstantOffsets());
1347     if (Arg && FuncInfo.getArgumentFrameIndex(Arg) != INT_MAX)
1348       return true;
1349
1350     Optional<MachineOperand> Op;
1351     if (unsigned Reg = lookUpRegForValue(Address))
1352       Op = MachineOperand::CreateReg(Reg, false);
1353
1354     // If we have a VLA that has a "use" in a metadata node that's then used
1355     // here but it has no other uses, then we have a problem. E.g.,
1356     //
1357     //   int foo (const int *x) {
1358     //     char a[*x];
1359     //     return 0;
1360     //   }
1361     //
1362     // If we assign 'a' a vreg and fast isel later on has to use the selection
1363     // DAG isel, it will want to copy the value to the vreg. However, there are
1364     // no uses, which goes counter to what selection DAG isel expects.
1365     if (!Op && !Address->use_empty() && isa<Instruction>(Address) &&
1366         (!isa<AllocaInst>(Address) ||
1367          !FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(Address))))
1368       Op = MachineOperand::CreateReg(FuncInfo.InitializeRegForValue(Address),
1369                                      false);
1370
1371     if (Op) {
1372       assert(DI->getVariable()->isValidLocationForIntrinsic(DbgLoc) &&
1373              "Expected inlined-at fields to agree");
1374       // A dbg.declare describes the address of a source variable, so lower it
1375       // into an indirect DBG_VALUE.
1376       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1377               TII.get(TargetOpcode::DBG_VALUE), /*IsIndirect*/ true,
1378               *Op, DI->getVariable(), DI->getExpression());
1379     } else {
1380       // We can't yet handle anything else here because it would require
1381       // generating code, thus altering codegen because of debug info.
1382       LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
1383     }
1384     return true;
1385   }
1386   case Intrinsic::dbg_value: {
1387     // This form of DBG_VALUE is target-independent.
1388     const DbgValueInst *DI = cast<DbgValueInst>(II);
1389     const MCInstrDesc &II = TII.get(TargetOpcode::DBG_VALUE);
1390     const Value *V = DI->getValue();
1391     assert(DI->getVariable()->isValidLocationForIntrinsic(DbgLoc) &&
1392            "Expected inlined-at fields to agree");
1393     if (!V) {
1394       // Currently the optimizer can produce this; insert an undef to
1395       // help debugging.  Probably the optimizer should not do this.
1396       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, false, 0U,
1397               DI->getVariable(), DI->getExpression());
1398     } else if (const auto *CI = dyn_cast<ConstantInt>(V)) {
1399       if (CI->getBitWidth() > 64)
1400         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1401             .addCImm(CI)
1402             .addImm(0U)
1403             .addMetadata(DI->getVariable())
1404             .addMetadata(DI->getExpression());
1405       else
1406         BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1407             .addImm(CI->getZExtValue())
1408             .addImm(0U)
1409             .addMetadata(DI->getVariable())
1410             .addMetadata(DI->getExpression());
1411     } else if (const auto *CF = dyn_cast<ConstantFP>(V)) {
1412       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
1413           .addFPImm(CF)
1414           .addImm(0U)
1415           .addMetadata(DI->getVariable())
1416           .addMetadata(DI->getExpression());
1417     } else if (unsigned Reg = lookUpRegForValue(V)) {
1418       // FIXME: This does not handle register-indirect values at offset 0.
1419       bool IsIndirect = false;
1420       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, IsIndirect, Reg,
1421               DI->getVariable(), DI->getExpression());
1422     } else {
1423       // We can't yet handle anything else here because it would require
1424       // generating code, thus altering codegen because of debug info.
1425       LLVM_DEBUG(dbgs() << "Dropping debug info for " << *DI << "\n");
1426     }
1427     return true;
1428   }
1429   case Intrinsic::objectsize: {
1430     ConstantInt *CI = cast<ConstantInt>(II->getArgOperand(1));
1431     unsigned long long Res = CI->isZero() ? -1ULL : 0;
1432     Constant *ResCI = ConstantInt::get(II->getType(), Res);
1433     unsigned ResultReg = getRegForValue(ResCI);
1434     if (!ResultReg)
1435       return false;
1436     updateValueMap(II, ResultReg);
1437     return true;
1438   }
1439   case Intrinsic::launder_invariant_group:
1440   case Intrinsic::strip_invariant_group:
1441   case Intrinsic::expect: {
1442     unsigned ResultReg = getRegForValue(II->getArgOperand(0));
1443     if (!ResultReg)
1444       return false;
1445     updateValueMap(II, ResultReg);
1446     return true;
1447   }
1448   case Intrinsic::experimental_stackmap:
1449     return selectStackmap(II);
1450   case Intrinsic::experimental_patchpoint_void:
1451   case Intrinsic::experimental_patchpoint_i64:
1452     return selectPatchpoint(II);
1453
1454   case Intrinsic::xray_customevent:
1455     return selectXRayCustomEvent(II);
1456   case Intrinsic::xray_typedevent:
1457     return selectXRayTypedEvent(II);
1458   }
1459
1460   return fastLowerIntrinsicCall(II);
1461 }
1462
1463 bool FastISel::selectCast(const User *I, unsigned Opcode) {
1464   EVT SrcVT = TLI.getValueType(DL, I->getOperand(0)->getType());
1465   EVT DstVT = TLI.getValueType(DL, I->getType());
1466
1467   if (SrcVT == MVT::Other || !SrcVT.isSimple() || DstVT == MVT::Other ||
1468       !DstVT.isSimple())
1469     // Unhandled type. Halt "fast" selection and bail.
1470     return false;
1471
1472   // Check if the destination type is legal.
1473   if (!TLI.isTypeLegal(DstVT))
1474     return false;
1475
1476   // Check if the source operand is legal.
1477   if (!TLI.isTypeLegal(SrcVT))
1478     return false;
1479
1480   unsigned InputReg = getRegForValue(I->getOperand(0));
1481   if (!InputReg)
1482     // Unhandled operand.  Halt "fast" selection and bail.
1483     return false;
1484
1485   bool InputRegIsKill = hasTrivialKill(I->getOperand(0));
1486
1487   unsigned ResultReg = fastEmit_r(SrcVT.getSimpleVT(), DstVT.getSimpleVT(),
1488                                   Opcode, InputReg, InputRegIsKill);
1489   if (!ResultReg)
1490     return false;
1491
1492   updateValueMap(I, ResultReg);
1493   return true;
1494 }
1495
1496 bool FastISel::selectBitCast(const User *I) {
1497   // If the bitcast doesn't change the type, just use the operand value.
1498   if (I->getType() == I->getOperand(0)->getType()) {
1499     unsigned Reg = getRegForValue(I->getOperand(0));
1500     if (!Reg)
1501       return false;
1502     updateValueMap(I, Reg);
1503     return true;
1504   }
1505
1506   // Bitcasts of other values become reg-reg copies or BITCAST operators.
1507   EVT SrcEVT = TLI.getValueType(DL, I->getOperand(0)->getType());
1508   EVT DstEVT = TLI.getValueType(DL, I->getType());
1509   if (SrcEVT == MVT::Other || DstEVT == MVT::Other ||
1510       !TLI.isTypeLegal(SrcEVT) || !TLI.isTypeLegal(DstEVT))
1511     // Unhandled type. Halt "fast" selection and bail.
1512     return false;
1513
1514   MVT SrcVT = SrcEVT.getSimpleVT();
1515   MVT DstVT = DstEVT.getSimpleVT();
1516   unsigned Op0 = getRegForValue(I->getOperand(0));
1517   if (!Op0) // Unhandled operand. Halt "fast" selection and bail.
1518     return false;
1519   bool Op0IsKill = hasTrivialKill(I->getOperand(0));
1520
1521   // First, try to perform the bitcast by inserting a reg-reg copy.
1522   unsigned ResultReg = 0;
1523   if (SrcVT == DstVT) {
1524     const TargetRegisterClass *SrcClass = TLI.getRegClassFor(SrcVT);
1525     const TargetRegisterClass *DstClass = TLI.getRegClassFor(DstVT);
1526     // Don't attempt a cross-class copy. It will likely fail.
1527     if (SrcClass == DstClass) {
1528       ResultReg = createResultReg(DstClass);
1529       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1530               TII.get(TargetOpcode::COPY), ResultReg).addReg(Op0);
1531     }
1532   }
1533
1534   // If the reg-reg copy failed, select a BITCAST opcode.
1535   if (!ResultReg)
1536     ResultReg = fastEmit_r(SrcVT, DstVT, ISD::BITCAST, Op0, Op0IsKill);
1537
1538   if (!ResultReg)
1539     return false;
1540
1541   updateValueMap(I, ResultReg);
1542   return true;
1543 }
1544
1545 // Remove local value instructions starting from the instruction after
1546 // SavedLastLocalValue to the current function insert point.
1547 void FastISel::removeDeadLocalValueCode(MachineInstr *SavedLastLocalValue)
1548 {
1549   MachineInstr *CurLastLocalValue = getLastLocalValue();
1550   if (CurLastLocalValue != SavedLastLocalValue) {
1551     // Find the first local value instruction to be deleted.
1552     // This is the instruction after SavedLastLocalValue if it is non-NULL.
1553     // Otherwise it's the first instruction in the block.
1554     MachineBasicBlock::iterator FirstDeadInst(SavedLastLocalValue);
1555     if (SavedLastLocalValue)
1556       ++FirstDeadInst;
1557     else
1558       FirstDeadInst = FuncInfo.MBB->getFirstNonPHI();
1559     setLastLocalValue(SavedLastLocalValue);
1560     removeDeadCode(FirstDeadInst, FuncInfo.InsertPt);
1561   }
1562 }
1563
1564 bool FastISel::selectInstruction(const Instruction *I) {
1565   MachineInstr *SavedLastLocalValue = getLastLocalValue();
1566   // Just before the terminator instruction, insert instructions to
1567   // feed PHI nodes in successor blocks.
1568   if (isa<TerminatorInst>(I)) {
1569     if (!handlePHINodesInSuccessorBlocks(I->getParent())) {
1570       // PHI node handling may have generated local value instructions,
1571       // even though it failed to handle all PHI nodes.
1572       // We remove these instructions because SelectionDAGISel will generate
1573       // them again.
1574       removeDeadLocalValueCode(SavedLastLocalValue);
1575       return false;
1576     }
1577   }
1578
1579   // FastISel does not handle any operand bundles except OB_funclet.
1580   if (ImmutableCallSite CS = ImmutableCallSite(I))
1581     for (unsigned i = 0, e = CS.getNumOperandBundles(); i != e; ++i)
1582       if (CS.getOperandBundleAt(i).getTagID() != LLVMContext::OB_funclet)
1583         return false;
1584
1585   DbgLoc = I->getDebugLoc();
1586
1587   SavedInsertPt = FuncInfo.InsertPt;
1588
1589   if (const auto *Call = dyn_cast<CallInst>(I)) {
1590     const Function *F = Call->getCalledFunction();
1591     LibFunc Func;
1592
1593     // As a special case, don't handle calls to builtin library functions that
1594     // may be translated directly to target instructions.
1595     if (F && !F->hasLocalLinkage() && F->hasName() &&
1596         LibInfo->getLibFunc(F->getName(), Func) &&
1597         LibInfo->hasOptimizedCodeGen(Func))
1598       return false;
1599
1600     // Don't handle Intrinsic::trap if a trap function is specified.
1601     if (F && F->getIntrinsicID() == Intrinsic::trap &&
1602         Call->hasFnAttr("trap-func-name"))
1603       return false;
1604   }
1605
1606   // First, try doing target-independent selection.
1607   if (!SkipTargetIndependentISel) {
1608     if (selectOperator(I, I->getOpcode())) {
1609       ++NumFastIselSuccessIndependent;
1610       DbgLoc = DebugLoc();
1611       return true;
1612     }
1613     // Remove dead code.
1614     recomputeInsertPt();
1615     if (SavedInsertPt != FuncInfo.InsertPt)
1616       removeDeadCode(FuncInfo.InsertPt, SavedInsertPt);
1617     SavedInsertPt = FuncInfo.InsertPt;
1618   }
1619   // Next, try calling the target to attempt to handle the instruction.
1620   if (fastSelectInstruction(I)) {
1621     ++NumFastIselSuccessTarget;
1622     DbgLoc = DebugLoc();
1623     return true;
1624   }
1625   // Remove dead code.
1626   recomputeInsertPt();
1627   if (SavedInsertPt != FuncInfo.InsertPt)
1628     removeDeadCode(FuncInfo.InsertPt, SavedInsertPt);
1629
1630   DbgLoc = DebugLoc();
1631   // Undo phi node updates, because they will be added again by SelectionDAG.
1632   if (isa<TerminatorInst>(I)) {
1633     // PHI node handling may have generated local value instructions.
1634     // We remove them because SelectionDAGISel will generate them again.
1635     removeDeadLocalValueCode(SavedLastLocalValue);
1636     FuncInfo.PHINodesToUpdate.resize(FuncInfo.OrigNumPHINodesToUpdate);
1637   }
1638   return false;
1639 }
1640
1641 /// Emit an unconditional branch to the given block, unless it is the immediate
1642 /// (fall-through) successor, and update the CFG.
1643 void FastISel::fastEmitBranch(MachineBasicBlock *MSucc,
1644                               const DebugLoc &DbgLoc) {
1645   if (FuncInfo.MBB->getBasicBlock()->size() > 1 &&
1646       FuncInfo.MBB->isLayoutSuccessor(MSucc)) {
1647     // For more accurate line information if this is the only instruction
1648     // in the block then emit it, otherwise we have the unconditional
1649     // fall-through case, which needs no instructions.
1650   } else {
1651     // The unconditional branch case.
1652     TII.insertBranch(*FuncInfo.MBB, MSucc, nullptr,
1653                      SmallVector<MachineOperand, 0>(), DbgLoc);
1654   }
1655   if (FuncInfo.BPI) {
1656     auto BranchProbability = FuncInfo.BPI->getEdgeProbability(
1657         FuncInfo.MBB->getBasicBlock(), MSucc->getBasicBlock());
1658     FuncInfo.MBB->addSuccessor(MSucc, BranchProbability);
1659   } else
1660     FuncInfo.MBB->addSuccessorWithoutProb(MSucc);
1661 }
1662
1663 void FastISel::finishCondBranch(const BasicBlock *BranchBB,
1664                                 MachineBasicBlock *TrueMBB,
1665                                 MachineBasicBlock *FalseMBB) {
1666   // Add TrueMBB as successor unless it is equal to the FalseMBB: This can
1667   // happen in degenerate IR and MachineIR forbids to have a block twice in the
1668   // successor/predecessor lists.
1669   if (TrueMBB != FalseMBB) {
1670     if (FuncInfo.BPI) {
1671       auto BranchProbability =
1672           FuncInfo.BPI->getEdgeProbability(BranchBB, TrueMBB->getBasicBlock());
1673       FuncInfo.MBB->addSuccessor(TrueMBB, BranchProbability);
1674     } else
1675       FuncInfo.MBB->addSuccessorWithoutProb(TrueMBB);
1676   }
1677
1678   fastEmitBranch(FalseMBB, DbgLoc);
1679 }
1680
1681 /// Emit an FNeg operation.
1682 bool FastISel::selectFNeg(const User *I) {
1683   unsigned OpReg = getRegForValue(BinaryOperator::getFNegArgument(I));
1684   if (!OpReg)
1685     return false;
1686   bool OpRegIsKill = hasTrivialKill(I);
1687
1688   // If the target has ISD::FNEG, use it.
1689   EVT VT = TLI.getValueType(DL, I->getType());
1690   unsigned ResultReg = fastEmit_r(VT.getSimpleVT(), VT.getSimpleVT(), ISD::FNEG,
1691                                   OpReg, OpRegIsKill);
1692   if (ResultReg) {
1693     updateValueMap(I, ResultReg);
1694     return true;
1695   }
1696
1697   // Bitcast the value to integer, twiddle the sign bit with xor,
1698   // and then bitcast it back to floating-point.
1699   if (VT.getSizeInBits() > 64)
1700     return false;
1701   EVT IntVT = EVT::getIntegerVT(I->getContext(), VT.getSizeInBits());
1702   if (!TLI.isTypeLegal(IntVT))
1703     return false;
1704
1705   unsigned IntReg = fastEmit_r(VT.getSimpleVT(), IntVT.getSimpleVT(),
1706                                ISD::BITCAST, OpReg, OpRegIsKill);
1707   if (!IntReg)
1708     return false;
1709
1710   unsigned IntResultReg = fastEmit_ri_(
1711       IntVT.getSimpleVT(), ISD::XOR, IntReg, /*IsKill=*/true,
1712       UINT64_C(1) << (VT.getSizeInBits() - 1), IntVT.getSimpleVT());
1713   if (!IntResultReg)
1714     return false;
1715
1716   ResultReg = fastEmit_r(IntVT.getSimpleVT(), VT.getSimpleVT(), ISD::BITCAST,
1717                          IntResultReg, /*IsKill=*/true);
1718   if (!ResultReg)
1719     return false;
1720
1721   updateValueMap(I, ResultReg);
1722   return true;
1723 }
1724
1725 bool FastISel::selectExtractValue(const User *U) {
1726   const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(U);
1727   if (!EVI)
1728     return false;
1729
1730   // Make sure we only try to handle extracts with a legal result.  But also
1731   // allow i1 because it's easy.
1732   EVT RealVT = TLI.getValueType(DL, EVI->getType(), /*AllowUnknown=*/true);
1733   if (!RealVT.isSimple())
1734     return false;
1735   MVT VT = RealVT.getSimpleVT();
1736   if (!TLI.isTypeLegal(VT) && VT != MVT::i1)
1737     return false;
1738
1739   const Value *Op0 = EVI->getOperand(0);
1740   Type *AggTy = Op0->getType();
1741
1742   // Get the base result register.
1743   unsigned ResultReg;
1744   DenseMap<const Value *, unsigned>::iterator I = FuncInfo.ValueMap.find(Op0);
1745   if (I != FuncInfo.ValueMap.end())
1746     ResultReg = I->second;
1747   else if (isa<Instruction>(Op0))
1748     ResultReg = FuncInfo.InitializeRegForValue(Op0);
1749   else
1750     return false; // fast-isel can't handle aggregate constants at the moment
1751
1752   // Get the actual result register, which is an offset from the base register.
1753   unsigned VTIndex = ComputeLinearIndex(AggTy, EVI->getIndices());
1754
1755   SmallVector<EVT, 4> AggValueVTs;
1756   ComputeValueVTs(TLI, DL, AggTy, AggValueVTs);
1757
1758   for (unsigned i = 0; i < VTIndex; i++)
1759     ResultReg += TLI.getNumRegisters(FuncInfo.Fn->getContext(), AggValueVTs[i]);
1760
1761   updateValueMap(EVI, ResultReg);
1762   return true;
1763 }
1764
1765 bool FastISel::selectOperator(const User *I, unsigned Opcode) {
1766   switch (Opcode) {
1767   case Instruction::Add:
1768     return selectBinaryOp(I, ISD::ADD);
1769   case Instruction::FAdd:
1770     return selectBinaryOp(I, ISD::FADD);
1771   case Instruction::Sub:
1772     return selectBinaryOp(I, ISD::SUB);
1773   case Instruction::FSub:
1774     // FNeg is currently represented in LLVM IR as a special case of FSub.
1775     if (BinaryOperator::isFNeg(I))
1776       return selectFNeg(I);
1777     return selectBinaryOp(I, ISD::FSUB);
1778   case Instruction::Mul:
1779     return selectBinaryOp(I, ISD::MUL);
1780   case Instruction::FMul:
1781     return selectBinaryOp(I, ISD::FMUL);
1782   case Instruction::SDiv:
1783     return selectBinaryOp(I, ISD::SDIV);
1784   case Instruction::UDiv:
1785     return selectBinaryOp(I, ISD::UDIV);
1786   case Instruction::FDiv:
1787     return selectBinaryOp(I, ISD::FDIV);
1788   case Instruction::SRem:
1789     return selectBinaryOp(I, ISD::SREM);
1790   case Instruction::URem:
1791     return selectBinaryOp(I, ISD::UREM);
1792   case Instruction::FRem:
1793     return selectBinaryOp(I, ISD::FREM);
1794   case Instruction::Shl:
1795     return selectBinaryOp(I, ISD::SHL);
1796   case Instruction::LShr:
1797     return selectBinaryOp(I, ISD::SRL);
1798   case Instruction::AShr:
1799     return selectBinaryOp(I, ISD::SRA);
1800   case Instruction::And:
1801     return selectBinaryOp(I, ISD::AND);
1802   case Instruction::Or:
1803     return selectBinaryOp(I, ISD::OR);
1804   case Instruction::Xor:
1805     return selectBinaryOp(I, ISD::XOR);
1806
1807   case Instruction::GetElementPtr:
1808     return selectGetElementPtr(I);
1809
1810   case Instruction::Br: {
1811     const BranchInst *BI = cast<BranchInst>(I);
1812
1813     if (BI->isUnconditional()) {
1814       const BasicBlock *LLVMSucc = BI->getSuccessor(0);
1815       MachineBasicBlock *MSucc = FuncInfo.MBBMap[LLVMSucc];
1816       fastEmitBranch(MSucc, BI->getDebugLoc());
1817       return true;
1818     }
1819
1820     // Conditional branches are not handed yet.
1821     // Halt "fast" selection and bail.
1822     return false;
1823   }
1824
1825   case Instruction::Unreachable:
1826     if (TM.Options.TrapUnreachable)
1827       return fastEmit_(MVT::Other, MVT::Other, ISD::TRAP) != 0;
1828     else
1829       return true;
1830
1831   case Instruction::Alloca:
1832     // FunctionLowering has the static-sized case covered.
1833     if (FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(I)))
1834       return true;
1835
1836     // Dynamic-sized alloca is not handled yet.
1837     return false;
1838
1839   case Instruction::Call:
1840     return selectCall(I);
1841
1842   case Instruction::BitCast:
1843     return selectBitCast(I);
1844
1845   case Instruction::FPToSI:
1846     return selectCast(I, ISD::FP_TO_SINT);
1847   case Instruction::ZExt:
1848     return selectCast(I, ISD::ZERO_EXTEND);
1849   case Instruction::SExt:
1850     return selectCast(I, ISD::SIGN_EXTEND);
1851   case Instruction::Trunc:
1852     return selectCast(I, ISD::TRUNCATE);
1853   case Instruction::SIToFP:
1854     return selectCast(I, ISD::SINT_TO_FP);
1855
1856   case Instruction::IntToPtr: // Deliberate fall-through.
1857   case Instruction::PtrToInt: {
1858     EVT SrcVT = TLI.getValueType(DL, I->getOperand(0)->getType());
1859     EVT DstVT = TLI.getValueType(DL, I->getType());
1860     if (DstVT.bitsGT(SrcVT))
1861       return selectCast(I, ISD::ZERO_EXTEND);
1862     if (DstVT.bitsLT(SrcVT))
1863       return selectCast(I, ISD::TRUNCATE);
1864     unsigned Reg = getRegForValue(I->getOperand(0));
1865     if (!Reg)
1866       return false;
1867     updateValueMap(I, Reg);
1868     return true;
1869   }
1870
1871   case Instruction::ExtractValue:
1872     return selectExtractValue(I);
1873
1874   case Instruction::PHI:
1875     llvm_unreachable("FastISel shouldn't visit PHI nodes!");
1876
1877   default:
1878     // Unhandled instruction. Halt "fast" selection and bail.
1879     return false;
1880   }
1881 }
1882
1883 FastISel::FastISel(FunctionLoweringInfo &FuncInfo,
1884                    const TargetLibraryInfo *LibInfo,
1885                    bool SkipTargetIndependentISel)
1886     : FuncInfo(FuncInfo), MF(FuncInfo.MF), MRI(FuncInfo.MF->getRegInfo()),
1887       MFI(FuncInfo.MF->getFrameInfo()), MCP(*FuncInfo.MF->getConstantPool()),
1888       TM(FuncInfo.MF->getTarget()), DL(MF->getDataLayout()),
1889       TII(*MF->getSubtarget().getInstrInfo()),
1890       TLI(*MF->getSubtarget().getTargetLowering()),
1891       TRI(*MF->getSubtarget().getRegisterInfo()), LibInfo(LibInfo),
1892       SkipTargetIndependentISel(SkipTargetIndependentISel) {}
1893
1894 FastISel::~FastISel() = default;
1895
1896 bool FastISel::fastLowerArguments() { return false; }
1897
1898 bool FastISel::fastLowerCall(CallLoweringInfo & /*CLI*/) { return false; }
1899
1900 bool FastISel::fastLowerIntrinsicCall(const IntrinsicInst * /*II*/) {
1901   return false;
1902 }
1903
1904 unsigned FastISel::fastEmit_(MVT, MVT, unsigned) { return 0; }
1905
1906 unsigned FastISel::fastEmit_r(MVT, MVT, unsigned, unsigned /*Op0*/,
1907                               bool /*Op0IsKill*/) {
1908   return 0;
1909 }
1910
1911 unsigned FastISel::fastEmit_rr(MVT, MVT, unsigned, unsigned /*Op0*/,
1912                                bool /*Op0IsKill*/, unsigned /*Op1*/,
1913                                bool /*Op1IsKill*/) {
1914   return 0;
1915 }
1916
1917 unsigned FastISel::fastEmit_i(MVT, MVT, unsigned, uint64_t /*Imm*/) {
1918   return 0;
1919 }
1920
1921 unsigned FastISel::fastEmit_f(MVT, MVT, unsigned,
1922                               const ConstantFP * /*FPImm*/) {
1923   return 0;
1924 }
1925
1926 unsigned FastISel::fastEmit_ri(MVT, MVT, unsigned, unsigned /*Op0*/,
1927                                bool /*Op0IsKill*/, uint64_t /*Imm*/) {
1928   return 0;
1929 }
1930
1931 /// This method is a wrapper of fastEmit_ri. It first tries to emit an
1932 /// instruction with an immediate operand using fastEmit_ri.
1933 /// If that fails, it materializes the immediate into a register and try
1934 /// fastEmit_rr instead.
1935 unsigned FastISel::fastEmit_ri_(MVT VT, unsigned Opcode, unsigned Op0,
1936                                 bool Op0IsKill, uint64_t Imm, MVT ImmType) {
1937   // If this is a multiply by a power of two, emit this as a shift left.
1938   if (Opcode == ISD::MUL && isPowerOf2_64(Imm)) {
1939     Opcode = ISD::SHL;
1940     Imm = Log2_64(Imm);
1941   } else if (Opcode == ISD::UDIV && isPowerOf2_64(Imm)) {
1942     // div x, 8 -> srl x, 3
1943     Opcode = ISD::SRL;
1944     Imm = Log2_64(Imm);
1945   }
1946
1947   // Horrible hack (to be removed), check to make sure shift amounts are
1948   // in-range.
1949   if ((Opcode == ISD::SHL || Opcode == ISD::SRA || Opcode == ISD::SRL) &&
1950       Imm >= VT.getSizeInBits())
1951     return 0;
1952
1953   // First check if immediate type is legal. If not, we can't use the ri form.
1954   unsigned ResultReg = fastEmit_ri(VT, VT, Opcode, Op0, Op0IsKill, Imm);
1955   if (ResultReg)
1956     return ResultReg;
1957   unsigned MaterialReg = fastEmit_i(ImmType, ImmType, ISD::Constant, Imm);
1958   bool IsImmKill = true;
1959   if (!MaterialReg) {
1960     // This is a bit ugly/slow, but failing here means falling out of
1961     // fast-isel, which would be very slow.
1962     IntegerType *ITy =
1963         IntegerType::get(FuncInfo.Fn->getContext(), VT.getSizeInBits());
1964     MaterialReg = getRegForValue(ConstantInt::get(ITy, Imm));
1965     if (!MaterialReg)
1966       return 0;
1967     // FIXME: If the materialized register here has no uses yet then this
1968     // will be the first use and we should be able to mark it as killed.
1969     // However, the local value area for materialising constant expressions
1970     // grows down, not up, which means that any constant expressions we generate
1971     // later which also use 'Imm' could be after this instruction and therefore
1972     // after this kill.
1973     IsImmKill = false;
1974   }
1975   return fastEmit_rr(VT, VT, Opcode, Op0, Op0IsKill, MaterialReg, IsImmKill);
1976 }
1977
1978 unsigned FastISel::createResultReg(const TargetRegisterClass *RC) {
1979   return MRI.createVirtualRegister(RC);
1980 }
1981
1982 unsigned FastISel::constrainOperandRegClass(const MCInstrDesc &II, unsigned Op,
1983                                             unsigned OpNum) {
1984   if (TargetRegisterInfo::isVirtualRegister(Op)) {
1985     const TargetRegisterClass *RegClass =
1986         TII.getRegClass(II, OpNum, &TRI, *FuncInfo.MF);
1987     if (!MRI.constrainRegClass(Op, RegClass)) {
1988       // If it's not legal to COPY between the register classes, something
1989       // has gone very wrong before we got here.
1990       unsigned NewOp = createResultReg(RegClass);
1991       BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
1992               TII.get(TargetOpcode::COPY), NewOp).addReg(Op);
1993       return NewOp;
1994     }
1995   }
1996   return Op;
1997 }
1998
1999 unsigned FastISel::fastEmitInst_(unsigned MachineInstOpcode,
2000                                  const TargetRegisterClass *RC) {
2001   unsigned ResultReg = createResultReg(RC);
2002   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2003
2004   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg);
2005   return ResultReg;
2006 }
2007
2008 unsigned FastISel::fastEmitInst_r(unsigned MachineInstOpcode,
2009                                   const TargetRegisterClass *RC, unsigned Op0,
2010                                   bool Op0IsKill) {
2011   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2012
2013   unsigned ResultReg = createResultReg(RC);
2014   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
2015
2016   if (II.getNumDefs() >= 1)
2017     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
2018         .addReg(Op0, getKillRegState(Op0IsKill));
2019   else {
2020     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
2021         .addReg(Op0, getKillRegState(Op0IsKill));
2022     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2023             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2024   }
2025
2026   return ResultReg;
2027 }
2028
2029 unsigned FastISel::fastEmitInst_rr(unsigned MachineInstOpcode,
2030                                    const TargetRegisterClass *RC, unsigned Op0,
2031                                    bool Op0IsKill, unsigned Op1,
2032                                    bool Op1IsKill) {
2033   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2034
2035   unsigned ResultReg = createResultReg(RC);
2036   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
2037   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
2038
2039   if (II.getNumDefs() >= 1)
2040     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
2041         .addReg(Op0, getKillRegState(Op0IsKill))
2042         .addReg(Op1, getKillRegState(Op1IsKill));
2043   else {
2044     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
2045         .addReg(Op0, getKillRegState(Op0IsKill))
2046         .addReg(Op1, getKillRegState(Op1IsKill));
2047     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2048             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2049   }
2050   return ResultReg;
2051 }
2052
2053 unsigned FastISel::fastEmitInst_rrr(unsigned MachineInstOpcode,
2054                                     const TargetRegisterClass *RC, unsigned Op0,
2055                                     bool Op0IsKill, unsigned Op1,
2056                                     bool Op1IsKill, unsigned Op2,
2057                                     bool Op2IsKill) {
2058   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2059
2060   unsigned ResultReg = createResultReg(RC);
2061   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
2062   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
2063   Op2 = constrainOperandRegClass(II, Op2, II.getNumDefs() + 2);
2064
2065   if (II.getNumDefs() >= 1)
2066     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
2067         .addReg(Op0, getKillRegState(Op0IsKill))
2068         .addReg(Op1, getKillRegState(Op1IsKill))
2069         .addReg(Op2, getKillRegState(Op2IsKill));
2070   else {
2071     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
2072         .addReg(Op0, getKillRegState(Op0IsKill))
2073         .addReg(Op1, getKillRegState(Op1IsKill))
2074         .addReg(Op2, getKillRegState(Op2IsKill));
2075     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2076             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2077   }
2078   return ResultReg;
2079 }
2080
2081 unsigned FastISel::fastEmitInst_ri(unsigned MachineInstOpcode,
2082                                    const TargetRegisterClass *RC, unsigned Op0,
2083                                    bool Op0IsKill, uint64_t Imm) {
2084   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2085
2086   unsigned ResultReg = createResultReg(RC);
2087   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
2088
2089   if (II.getNumDefs() >= 1)
2090     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
2091         .addReg(Op0, getKillRegState(Op0IsKill))
2092         .addImm(Imm);
2093   else {
2094     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
2095         .addReg(Op0, getKillRegState(Op0IsKill))
2096         .addImm(Imm);
2097     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2098             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2099   }
2100   return ResultReg;
2101 }
2102
2103 unsigned FastISel::fastEmitInst_rii(unsigned MachineInstOpcode,
2104                                     const TargetRegisterClass *RC, unsigned Op0,
2105                                     bool Op0IsKill, uint64_t Imm1,
2106                                     uint64_t Imm2) {
2107   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2108
2109   unsigned ResultReg = createResultReg(RC);
2110   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
2111
2112   if (II.getNumDefs() >= 1)
2113     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
2114         .addReg(Op0, getKillRegState(Op0IsKill))
2115         .addImm(Imm1)
2116         .addImm(Imm2);
2117   else {
2118     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
2119         .addReg(Op0, getKillRegState(Op0IsKill))
2120         .addImm(Imm1)
2121         .addImm(Imm2);
2122     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2123             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2124   }
2125   return ResultReg;
2126 }
2127
2128 unsigned FastISel::fastEmitInst_f(unsigned MachineInstOpcode,
2129                                   const TargetRegisterClass *RC,
2130                                   const ConstantFP *FPImm) {
2131   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2132
2133   unsigned ResultReg = createResultReg(RC);
2134
2135   if (II.getNumDefs() >= 1)
2136     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
2137         .addFPImm(FPImm);
2138   else {
2139     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
2140         .addFPImm(FPImm);
2141     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2142             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2143   }
2144   return ResultReg;
2145 }
2146
2147 unsigned FastISel::fastEmitInst_rri(unsigned MachineInstOpcode,
2148                                     const TargetRegisterClass *RC, unsigned Op0,
2149                                     bool Op0IsKill, unsigned Op1,
2150                                     bool Op1IsKill, uint64_t Imm) {
2151   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2152
2153   unsigned ResultReg = createResultReg(RC);
2154   Op0 = constrainOperandRegClass(II, Op0, II.getNumDefs());
2155   Op1 = constrainOperandRegClass(II, Op1, II.getNumDefs() + 1);
2156
2157   if (II.getNumDefs() >= 1)
2158     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
2159         .addReg(Op0, getKillRegState(Op0IsKill))
2160         .addReg(Op1, getKillRegState(Op1IsKill))
2161         .addImm(Imm);
2162   else {
2163     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II)
2164         .addReg(Op0, getKillRegState(Op0IsKill))
2165         .addReg(Op1, getKillRegState(Op1IsKill))
2166         .addImm(Imm);
2167     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2168             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2169   }
2170   return ResultReg;
2171 }
2172
2173 unsigned FastISel::fastEmitInst_i(unsigned MachineInstOpcode,
2174                                   const TargetRegisterClass *RC, uint64_t Imm) {
2175   unsigned ResultReg = createResultReg(RC);
2176   const MCInstrDesc &II = TII.get(MachineInstOpcode);
2177
2178   if (II.getNumDefs() >= 1)
2179     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II, ResultReg)
2180         .addImm(Imm);
2181   else {
2182     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, II).addImm(Imm);
2183     BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc,
2184             TII.get(TargetOpcode::COPY), ResultReg).addReg(II.ImplicitDefs[0]);
2185   }
2186   return ResultReg;
2187 }
2188
2189 unsigned FastISel::fastEmitInst_extractsubreg(MVT RetVT, unsigned Op0,
2190                                               bool Op0IsKill, uint32_t Idx) {
2191   unsigned ResultReg = createResultReg(TLI.getRegClassFor(RetVT));
2192   assert(TargetRegisterInfo::isVirtualRegister(Op0) &&
2193          "Cannot yet extract from physregs");
2194   const TargetRegisterClass *RC = MRI.getRegClass(Op0);
2195   MRI.constrainRegClass(Op0, TRI.getSubClassWithSubReg(RC, Idx));
2196   BuildMI(*FuncInfo.MBB, FuncInfo.InsertPt, DbgLoc, TII.get(TargetOpcode::COPY),
2197           ResultReg).addReg(Op0, getKillRegState(Op0IsKill), Idx);
2198   return ResultReg;
2199 }
2200
2201 /// Emit MachineInstrs to compute the value of Op with all but the least
2202 /// significant bit set to zero.
2203 unsigned FastISel::fastEmitZExtFromI1(MVT VT, unsigned Op0, bool Op0IsKill) {
2204   return fastEmit_ri(VT, VT, ISD::AND, Op0, Op0IsKill, 1);
2205 }
2206
2207 /// HandlePHINodesInSuccessorBlocks - Handle PHI nodes in successor blocks.
2208 /// Emit code to ensure constants are copied into registers when needed.
2209 /// Remember the virtual registers that need to be added to the Machine PHI
2210 /// nodes as input.  We cannot just directly add them, because expansion
2211 /// might result in multiple MBB's for one BB.  As such, the start of the
2212 /// BB might correspond to a different MBB than the end.
2213 bool FastISel::handlePHINodesInSuccessorBlocks(const BasicBlock *LLVMBB) {
2214   const TerminatorInst *TI = LLVMBB->getTerminator();
2215
2216   SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled;
2217   FuncInfo.OrigNumPHINodesToUpdate = FuncInfo.PHINodesToUpdate.size();
2218
2219   // Check successor nodes' PHI nodes that expect a constant to be available
2220   // from this block.
2221   for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) {
2222     const BasicBlock *SuccBB = TI->getSuccessor(succ);
2223     if (!isa<PHINode>(SuccBB->begin()))
2224       continue;
2225     MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB];
2226
2227     // If this terminator has multiple identical successors (common for
2228     // switches), only handle each succ once.
2229     if (!SuccsHandled.insert(SuccMBB).second)
2230       continue;
2231
2232     MachineBasicBlock::iterator MBBI = SuccMBB->begin();
2233
2234     // At this point we know that there is a 1-1 correspondence between LLVM PHI
2235     // nodes and Machine PHI nodes, but the incoming operands have not been
2236     // emitted yet.
2237     for (const PHINode &PN : SuccBB->phis()) {
2238       // Ignore dead phi's.
2239       if (PN.use_empty())
2240         continue;
2241
2242       // Only handle legal types. Two interesting things to note here. First,
2243       // by bailing out early, we may leave behind some dead instructions,
2244       // since SelectionDAG's HandlePHINodesInSuccessorBlocks will insert its
2245       // own moves. Second, this check is necessary because FastISel doesn't
2246       // use CreateRegs to create registers, so it always creates
2247       // exactly one register for each non-void instruction.
2248       EVT VT = TLI.getValueType(DL, PN.getType(), /*AllowUnknown=*/true);
2249       if (VT == MVT::Other || !TLI.isTypeLegal(VT)) {
2250         // Handle integer promotions, though, because they're common and easy.
2251         if (!(VT == MVT::i1 || VT == MVT::i8 || VT == MVT::i16)) {
2252           FuncInfo.PHINodesToUpdate.resize(FuncInfo.OrigNumPHINodesToUpdate);
2253           return false;
2254         }
2255       }
2256
2257       const Value *PHIOp = PN.getIncomingValueForBlock(LLVMBB);
2258
2259       // Set the DebugLoc for the copy. Prefer the location of the operand
2260       // if there is one; use the location of the PHI otherwise.
2261       DbgLoc = PN.getDebugLoc();
2262       if (const auto *Inst = dyn_cast<Instruction>(PHIOp))
2263         DbgLoc = Inst->getDebugLoc();
2264
2265       unsigned Reg = getRegForValue(PHIOp);
2266       if (!Reg) {
2267         FuncInfo.PHINodesToUpdate.resize(FuncInfo.OrigNumPHINodesToUpdate);
2268         return false;
2269       }
2270       FuncInfo.PHINodesToUpdate.push_back(std::make_pair(&*MBBI++, Reg));
2271       DbgLoc = DebugLoc();
2272     }
2273   }
2274
2275   return true;
2276 }
2277
2278 bool FastISel::tryToFoldLoad(const LoadInst *LI, const Instruction *FoldInst) {
2279   assert(LI->hasOneUse() &&
2280          "tryToFoldLoad expected a LoadInst with a single use");
2281   // We know that the load has a single use, but don't know what it is.  If it
2282   // isn't one of the folded instructions, then we can't succeed here.  Handle
2283   // this by scanning the single-use users of the load until we get to FoldInst.
2284   unsigned MaxUsers = 6; // Don't scan down huge single-use chains of instrs.
2285
2286   const Instruction *TheUser = LI->user_back();
2287   while (TheUser != FoldInst && // Scan up until we find FoldInst.
2288          // Stay in the right block.
2289          TheUser->getParent() == FoldInst->getParent() &&
2290          --MaxUsers) { // Don't scan too far.
2291     // If there are multiple or no uses of this instruction, then bail out.
2292     if (!TheUser->hasOneUse())
2293       return false;
2294
2295     TheUser = TheUser->user_back();
2296   }
2297
2298   // If we didn't find the fold instruction, then we failed to collapse the
2299   // sequence.
2300   if (TheUser != FoldInst)
2301     return false;
2302
2303   // Don't try to fold volatile loads.  Target has to deal with alignment
2304   // constraints.
2305   if (LI->isVolatile())
2306     return false;
2307
2308   // Figure out which vreg this is going into.  If there is no assigned vreg yet
2309   // then there actually was no reference to it.  Perhaps the load is referenced
2310   // by a dead instruction.
2311   unsigned LoadReg = getRegForValue(LI);
2312   if (!LoadReg)
2313     return false;
2314
2315   // We can't fold if this vreg has no uses or more than one use.  Multiple uses
2316   // may mean that the instruction got lowered to multiple MIs, or the use of
2317   // the loaded value ended up being multiple operands of the result.
2318   if (!MRI.hasOneUse(LoadReg))
2319     return false;
2320
2321   MachineRegisterInfo::reg_iterator RI = MRI.reg_begin(LoadReg);
2322   MachineInstr *User = RI->getParent();
2323
2324   // Set the insertion point properly.  Folding the load can cause generation of
2325   // other random instructions (like sign extends) for addressing modes; make
2326   // sure they get inserted in a logical place before the new instruction.
2327   FuncInfo.InsertPt = User;
2328   FuncInfo.MBB = User->getParent();
2329
2330   // Ask the target to try folding the load.
2331   return tryToFoldLoadIntoMI(User, RI.getOperandNo(), LI);
2332 }
2333
2334 bool FastISel::canFoldAddIntoGEP(const User *GEP, const Value *Add) {
2335   // Must be an add.
2336   if (!isa<AddOperator>(Add))
2337     return false;
2338   // Type size needs to match.
2339   if (DL.getTypeSizeInBits(GEP->getType()) !=
2340       DL.getTypeSizeInBits(Add->getType()))
2341     return false;
2342   // Must be in the same basic block.
2343   if (isa<Instruction>(Add) &&
2344       FuncInfo.MBBMap[cast<Instruction>(Add)->getParent()] != FuncInfo.MBB)
2345     return false;
2346   // Must have a constant operand.
2347   return isa<ConstantInt>(cast<AddOperator>(Add)->getOperand(1));
2348 }
2349
2350 MachineMemOperand *
2351 FastISel::createMachineMemOperandFor(const Instruction *I) const {
2352   const Value *Ptr;
2353   Type *ValTy;
2354   unsigned Alignment;
2355   MachineMemOperand::Flags Flags;
2356   bool IsVolatile;
2357
2358   if (const auto *LI = dyn_cast<LoadInst>(I)) {
2359     Alignment = LI->getAlignment();
2360     IsVolatile = LI->isVolatile();
2361     Flags = MachineMemOperand::MOLoad;
2362     Ptr = LI->getPointerOperand();
2363     ValTy = LI->getType();
2364   } else if (const auto *SI = dyn_cast<StoreInst>(I)) {
2365     Alignment = SI->getAlignment();
2366     IsVolatile = SI->isVolatile();
2367     Flags = MachineMemOperand::MOStore;
2368     Ptr = SI->getPointerOperand();
2369     ValTy = SI->getValueOperand()->getType();
2370   } else
2371     return nullptr;
2372
2373   bool IsNonTemporal = I->getMetadata(LLVMContext::MD_nontemporal) != nullptr;
2374   bool IsInvariant = I->getMetadata(LLVMContext::MD_invariant_load) != nullptr;
2375   bool IsDereferenceable =
2376       I->getMetadata(LLVMContext::MD_dereferenceable) != nullptr;
2377   const MDNode *Ranges = I->getMetadata(LLVMContext::MD_range);
2378
2379   AAMDNodes AAInfo;
2380   I->getAAMetadata(AAInfo);
2381
2382   if (Alignment == 0) // Ensure that codegen never sees alignment 0.
2383     Alignment = DL.getABITypeAlignment(ValTy);
2384
2385   unsigned Size = DL.getTypeStoreSize(ValTy);
2386
2387   if (IsVolatile)
2388     Flags |= MachineMemOperand::MOVolatile;
2389   if (IsNonTemporal)
2390     Flags |= MachineMemOperand::MONonTemporal;
2391   if (IsDereferenceable)
2392     Flags |= MachineMemOperand::MODereferenceable;
2393   if (IsInvariant)
2394     Flags |= MachineMemOperand::MOInvariant;
2395
2396   return FuncInfo.MF->getMachineMemOperand(MachinePointerInfo(Ptr), Flags, Size,
2397                                            Alignment, AAInfo, Ranges);
2398 }
2399
2400 CmpInst::Predicate FastISel::optimizeCmpPredicate(const CmpInst *CI) const {
2401   // If both operands are the same, then try to optimize or fold the cmp.
2402   CmpInst::Predicate Predicate = CI->getPredicate();
2403   if (CI->getOperand(0) != CI->getOperand(1))
2404     return Predicate;
2405
2406   switch (Predicate) {
2407   default: llvm_unreachable("Invalid predicate!");
2408   case CmpInst::FCMP_FALSE: Predicate = CmpInst::FCMP_FALSE; break;
2409   case CmpInst::FCMP_OEQ:   Predicate = CmpInst::FCMP_ORD;   break;
2410   case CmpInst::FCMP_OGT:   Predicate = CmpInst::FCMP_FALSE; break;
2411   case CmpInst::FCMP_OGE:   Predicate = CmpInst::FCMP_ORD;   break;
2412   case CmpInst::FCMP_OLT:   Predicate = CmpInst::FCMP_FALSE; break;
2413   case CmpInst::FCMP_OLE:   Predicate = CmpInst::FCMP_ORD;   break;
2414   case CmpInst::FCMP_ONE:   Predicate = CmpInst::FCMP_FALSE; break;
2415   case CmpInst::FCMP_ORD:   Predicate = CmpInst::FCMP_ORD;   break;
2416   case CmpInst::FCMP_UNO:   Predicate = CmpInst::FCMP_UNO;   break;
2417   case CmpInst::FCMP_UEQ:   Predicate = CmpInst::FCMP_TRUE;  break;
2418   case CmpInst::FCMP_UGT:   Predicate = CmpInst::FCMP_UNO;   break;
2419   case CmpInst::FCMP_UGE:   Predicate = CmpInst::FCMP_TRUE;  break;
2420   case CmpInst::FCMP_ULT:   Predicate = CmpInst::FCMP_UNO;   break;
2421   case CmpInst::FCMP_ULE:   Predicate = CmpInst::FCMP_TRUE;  break;
2422   case CmpInst::FCMP_UNE:   Predicate = CmpInst::FCMP_UNO;   break;
2423   case CmpInst::FCMP_TRUE:  Predicate = CmpInst::FCMP_TRUE;  break;
2424
2425   case CmpInst::ICMP_EQ:    Predicate = CmpInst::FCMP_TRUE;  break;
2426   case CmpInst::ICMP_NE:    Predicate = CmpInst::FCMP_FALSE; break;
2427   case CmpInst::ICMP_UGT:   Predicate = CmpInst::FCMP_FALSE; break;
2428   case CmpInst::ICMP_UGE:   Predicate = CmpInst::FCMP_TRUE;  break;
2429   case CmpInst::ICMP_ULT:   Predicate = CmpInst::FCMP_FALSE; break;
2430   case CmpInst::ICMP_ULE:   Predicate = CmpInst::FCMP_TRUE;  break;
2431   case CmpInst::ICMP_SGT:   Predicate = CmpInst::FCMP_FALSE; break;
2432   case CmpInst::ICMP_SGE:   Predicate = CmpInst::FCMP_TRUE;  break;
2433   case CmpInst::ICMP_SLT:   Predicate = CmpInst::FCMP_FALSE; break;
2434   case CmpInst::ICMP_SLE:   Predicate = CmpInst::FCMP_TRUE;  break;
2435   }
2436
2437   return Predicate;
2438 }