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

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