contrib/llvm/lib/Target/BPF/BPFISelLowering.cpp

   1 //===-- BPFISelLowering.cpp - BPF DAG Lowering Implementation  ------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the interfaces that BPF uses to lower LLVM code into a
  11 // selection DAG.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "BPFISelLowering.h"
  16 #include "BPF.h"
  17 #include "BPFSubtarget.h"
  18 #include "BPFTargetMachine.h"
  19 #include "llvm/CodeGen/CallingConvLower.h"
  20 #include "llvm/CodeGen/MachineFrameInfo.h"
  21 #include "llvm/CodeGen/MachineFunction.h"
  22 #include "llvm/CodeGen/MachineInstrBuilder.h"
  23 #include "llvm/CodeGen/MachineRegisterInfo.h"
  24 #include "llvm/CodeGen/SelectionDAGISel.h"
  25 #include "llvm/CodeGen/TargetLoweringObjectFileImpl.h"
  26 #include "llvm/CodeGen/ValueTypes.h"
  27 #include "llvm/IR/DiagnosticInfo.h"
  28 #include "llvm/IR/DiagnosticPrinter.h"
  29 #include "llvm/Support/Debug.h"
  30 #include "llvm/Support/ErrorHandling.h"
  31 #include "llvm/Support/raw_ostream.h"
  32 using namespace llvm;
  33
  34 #define DEBUG_TYPE "bpf-lower"
  35
  36 static void fail(const SDLoc &DL, SelectionDAG &DAG, const Twine &Msg) {
  37   MachineFunction &MF = DAG.getMachineFunction();
  38   DAG.getContext()->diagnose(
  39       DiagnosticInfoUnsupported(*MF.getFunction(), Msg, DL.getDebugLoc()));
  40 }
  41
  42 static void fail(const SDLoc &DL, SelectionDAG &DAG, const char *Msg,
  43                  SDValue Val) {
  44   MachineFunction &MF = DAG.getMachineFunction();
  45   std::string Str;
  46   raw_string_ostream OS(Str);
  47   OS << Msg;
  48   Val->print(OS);
  49   OS.flush();
  50   DAG.getContext()->diagnose(
  51       DiagnosticInfoUnsupported(*MF.getFunction(), Str, DL.getDebugLoc()));
  52 }
  53
  54 BPFTargetLowering::BPFTargetLowering(const TargetMachine &TM,
  55                                      const BPFSubtarget &STI)
  56     : TargetLowering(TM) {
  57
  58   // Set up the register classes.
  59   addRegisterClass(MVT::i64, &BPF::GPRRegClass);
  60
  61   // Compute derived properties from the register classes
  62   computeRegisterProperties(STI.getRegisterInfo());
  63
  64   setStackPointerRegisterToSaveRestore(BPF::R11);
  65
  66   setOperationAction(ISD::BR_CC, MVT::i64, Custom);
  67   setOperationAction(ISD::BR_JT, MVT::Other, Expand);
  68   setOperationAction(ISD::BRIND, MVT::Other, Expand);
  69   setOperationAction(ISD::BRCOND, MVT::Other, Expand);
  70   setOperationAction(ISD::SETCC, MVT::i64, Expand);
  71   setOperationAction(ISD::SELECT, MVT::i64, Expand);
  72   setOperationAction(ISD::SELECT_CC, MVT::i64, Custom);
  73
  74   setOperationAction(ISD::GlobalAddress, MVT::i64, Custom);
  75
  76   setOperationAction(ISD::DYNAMIC_STACKALLOC, MVT::i64, Custom);
  77   setOperationAction(ISD::STACKSAVE, MVT::Other, Expand);
  78   setOperationAction(ISD::STACKRESTORE, MVT::Other, Expand);
  79
  80   setOperationAction(ISD::SDIVREM, MVT::i64, Expand);
  81   setOperationAction(ISD::UDIVREM, MVT::i64, Expand);
  82   setOperationAction(ISD::SREM, MVT::i64, Expand);
  83   setOperationAction(ISD::UREM, MVT::i64, Expand);
  84
  85   setOperationAction(ISD::MULHU, MVT::i64, Expand);
  86   setOperationAction(ISD::MULHS, MVT::i64, Expand);
  87   setOperationAction(ISD::UMUL_LOHI, MVT::i64, Expand);
  88   setOperationAction(ISD::SMUL_LOHI, MVT::i64, Expand);
  89
  90   setOperationAction(ISD::ADDC, MVT::i64, Expand);
  91   setOperationAction(ISD::ADDE, MVT::i64, Expand);
  92   setOperationAction(ISD::SUBC, MVT::i64, Expand);
  93   setOperationAction(ISD::SUBE, MVT::i64, Expand);
  94
  95   setOperationAction(ISD::ROTR, MVT::i64, Expand);
  96   setOperationAction(ISD::ROTL, MVT::i64, Expand);
  97   setOperationAction(ISD::SHL_PARTS, MVT::i64, Expand);
  98   setOperationAction(ISD::SRL_PARTS, MVT::i64, Expand);
  99   setOperationAction(ISD::SRA_PARTS, MVT::i64, Expand);
 100
 101   setOperationAction(ISD::CTTZ, MVT::i64, Custom);
 102   setOperationAction(ISD::CTLZ, MVT::i64, Custom);
 103   setOperationAction(ISD::CTTZ_ZERO_UNDEF, MVT::i64, Custom);
 104   setOperationAction(ISD::CTLZ_ZERO_UNDEF, MVT::i64, Custom);
 105   setOperationAction(ISD::CTPOP, MVT::i64, Expand);
 106
 107   setOperationAction(ISD::SIGN_EXTEND_INREG, MVT::i1, Expand);
 108   setOperationAction(ISD::SIGN_EXTEND_INREG, MVT::i8, Expand);
 109   setOperationAction(ISD::SIGN_EXTEND_INREG, MVT::i16, Expand);
 110   setOperationAction(ISD::SIGN_EXTEND_INREG, MVT::i32, Expand);
 111
 112   // Extended load operations for i1 types must be promoted
 113   for (MVT VT : MVT::integer_valuetypes()) {
 114     setLoadExtAction(ISD::EXTLOAD, VT, MVT::i1, Promote);
 115     setLoadExtAction(ISD::ZEXTLOAD, VT, MVT::i1, Promote);
 116     setLoadExtAction(ISD::SEXTLOAD, VT, MVT::i1, Promote);
 117
 118     setLoadExtAction(ISD::SEXTLOAD, VT, MVT::i8, Expand);
 119     setLoadExtAction(ISD::SEXTLOAD, VT, MVT::i16, Expand);
 120     setLoadExtAction(ISD::SEXTLOAD, VT, MVT::i32, Expand);
 121   }
 122
 123   setBooleanContents(ZeroOrOneBooleanContent);
 124
 125   // Function alignments (log2)
 126   setMinFunctionAlignment(3);
 127   setPrefFunctionAlignment(3);
 128
 129   // inline memcpy() for kernel to see explicit copy
 130   MaxStoresPerMemset = MaxStoresPerMemsetOptSize = 128;
 131   MaxStoresPerMemcpy = MaxStoresPerMemcpyOptSize = 128;
 132   MaxStoresPerMemmove = MaxStoresPerMemmoveOptSize = 128;
 133 }
 134
 135 SDValue BPFTargetLowering::LowerOperation(SDValue Op, SelectionDAG &DAG) const {
 136   switch (Op.getOpcode()) {
 137   case ISD::BR_CC:
 138     return LowerBR_CC(Op, DAG);
 139   case ISD::GlobalAddress:
 140     return LowerGlobalAddress(Op, DAG);
 141   case ISD::SELECT_CC:
 142     return LowerSELECT_CC(Op, DAG);
 143   default:
 144     llvm_unreachable("unimplemented operand");
 145   }
 146 }
 147
 148 // Calling Convention Implementation
 149 #include "BPFGenCallingConv.inc"
 150
 151 SDValue BPFTargetLowering::LowerFormalArguments(
 152     SDValue Chain, CallingConv::ID CallConv, bool IsVarArg,
 153     const SmallVectorImpl<ISD::InputArg> &Ins, const SDLoc &DL,
 154     SelectionDAG &DAG, SmallVectorImpl<SDValue> &InVals) const {
 155   switch (CallConv) {
 156   default:
 157     llvm_unreachable("Unsupported calling convention");
 158   case CallingConv::C:
 159   case CallingConv::Fast:
 160     break;
 161   }
 162
 163   MachineFunction &MF = DAG.getMachineFunction();
 164   MachineRegisterInfo &RegInfo = MF.getRegInfo();
 165
 166   // Assign locations to all of the incoming arguments.
 167   SmallVector<CCValAssign, 16> ArgLocs;
 168   CCState CCInfo(CallConv, IsVarArg, MF, ArgLocs, *DAG.getContext());
 169   CCInfo.AnalyzeFormalArguments(Ins, CC_BPF64);
 170
 171   for (auto &VA : ArgLocs) {
 172     if (VA.isRegLoc()) {
 173       // Arguments passed in registers
 174       EVT RegVT = VA.getLocVT();
 175       switch (RegVT.getSimpleVT().SimpleTy) {
 176       default: {
 177         errs() << "LowerFormalArguments Unhandled argument type: "
 178                << RegVT.getEVTString() << '\n';
 179         llvm_unreachable(0);
 180       }
 181       case MVT::i64:
 182         unsigned VReg = RegInfo.createVirtualRegister(&BPF::GPRRegClass);
 183         RegInfo.addLiveIn(VA.getLocReg(), VReg);
 184         SDValue ArgValue = DAG.getCopyFromReg(Chain, DL, VReg, RegVT);
 185
 186         // If this is an 8/16/32-bit value, it is really passed promoted to 64
 187         // bits. Insert an assert[sz]ext to capture this, then truncate to the
 188         // right size.
 189         if (VA.getLocInfo() == CCValAssign::SExt)
 190           ArgValue = DAG.getNode(ISD::AssertSext, DL, RegVT, ArgValue,
 191                                  DAG.getValueType(VA.getValVT()));
 192         else if (VA.getLocInfo() == CCValAssign::ZExt)
 193           ArgValue = DAG.getNode(ISD::AssertZext, DL, RegVT, ArgValue,
 194                                  DAG.getValueType(VA.getValVT()));
 195
 196         if (VA.getLocInfo() != CCValAssign::Full)
 197           ArgValue = DAG.getNode(ISD::TRUNCATE, DL, VA.getValVT(), ArgValue);
 198
 199         InVals.push_back(ArgValue);
 200       }
 201     } else {
 202       fail(DL, DAG, "defined with too many args");
 203       InVals.push_back(DAG.getConstant(0, DL, VA.getLocVT()));
 204     }
 205   }
 206
 207   if (IsVarArg || MF.getFunction()->hasStructRetAttr()) {
 208     fail(DL, DAG, "functions with VarArgs or StructRet are not supported");
 209   }
 210
 211   return Chain;
 212 }
 213
 214 const unsigned BPFTargetLowering::MaxArgs = 5;
 215
 216 SDValue BPFTargetLowering::LowerCall(TargetLowering::CallLoweringInfo &CLI,
 217                                      SmallVectorImpl<SDValue> &InVals) const {
 218   SelectionDAG &DAG = CLI.DAG;
 219   auto &Outs = CLI.Outs;
 220   auto &OutVals = CLI.OutVals;
 221   auto &Ins = CLI.Ins;
 222   SDValue Chain = CLI.Chain;
 223   SDValue Callee = CLI.Callee;
 224   bool &IsTailCall = CLI.IsTailCall;
 225   CallingConv::ID CallConv = CLI.CallConv;
 226   bool IsVarArg = CLI.IsVarArg;
 227   MachineFunction &MF = DAG.getMachineFunction();
 228
 229   // BPF target does not support tail call optimization.
 230   IsTailCall = false;
 231
 232   switch (CallConv) {
 233   default:
 234     report_fatal_error("Unsupported calling convention");
 235   case CallingConv::Fast:
 236   case CallingConv::C:
 237     break;
 238   }
 239
 240   // Analyze operands of the call, assigning locations to each operand.
 241   SmallVector<CCValAssign, 16> ArgLocs;
 242   CCState CCInfo(CallConv, IsVarArg, MF, ArgLocs, *DAG.getContext());
 243
 244   CCInfo.AnalyzeCallOperands(Outs, CC_BPF64);
 245
 246   unsigned NumBytes = CCInfo.getNextStackOffset();
 247
 248   if (Outs.size() > MaxArgs)
 249     fail(CLI.DL, DAG, "too many args to ", Callee);
 250
 251   for (auto &Arg : Outs) {
 252     ISD::ArgFlagsTy Flags = Arg.Flags;
 253     if (!Flags.isByVal())
 254       continue;
 255
 256     fail(CLI.DL, DAG, "pass by value not supported ", Callee);
 257   }
 258
 259   auto PtrVT = getPointerTy(MF.getDataLayout());
 260   Chain = DAG.getCALLSEQ_START(
 261       Chain, DAG.getConstant(NumBytes, CLI.DL, PtrVT, true), CLI.DL);
 262
 263   SmallVector<std::pair<unsigned, SDValue>, MaxArgs> RegsToPass;
 264
 265   // Walk arg assignments
 266   for (unsigned i = 0,
 267                 e = std::min(static_cast<unsigned>(ArgLocs.size()), MaxArgs);
 268        i != e; ++i) {
 269     CCValAssign &VA = ArgLocs[i];
 270     SDValue Arg = OutVals[i];
 271
 272     // Promote the value if needed.
 273     switch (VA.getLocInfo()) {
 274     default:
 275       llvm_unreachable("Unknown loc info");
 276     case CCValAssign::Full:
 277       break;
 278     case CCValAssign::SExt:
 279       Arg = DAG.getNode(ISD::SIGN_EXTEND, CLI.DL, VA.getLocVT(), Arg);
 280       break;
 281     case CCValAssign::ZExt:
 282       Arg = DAG.getNode(ISD::ZERO_EXTEND, CLI.DL, VA.getLocVT(), Arg);
 283       break;
 284     case CCValAssign::AExt:
 285       Arg = DAG.getNode(ISD::ANY_EXTEND, CLI.DL, VA.getLocVT(), Arg);
 286       break;
 287     }
 288
 289     // Push arguments into RegsToPass vector
 290     if (VA.isRegLoc())
 291       RegsToPass.push_back(std::make_pair(VA.getLocReg(), Arg));
 292     else
 293       llvm_unreachable("call arg pass bug");
 294   }
 295
 296   SDValue InFlag;
 297
 298   // Build a sequence of copy-to-reg nodes chained together with token chain and
 299   // flag operands which copy the outgoing args into registers.  The InFlag in
 300   // necessary since all emitted instructions must be stuck together.
 301   for (auto &Reg : RegsToPass) {
 302     Chain = DAG.getCopyToReg(Chain, CLI.DL, Reg.first, Reg.second, InFlag);
 303     InFlag = Chain.getValue(1);
 304   }
 305
 306   // If the callee is a GlobalAddress node (quite common, every direct call is)
 307   // turn it into a TargetGlobalAddress node so that legalize doesn't hack it.
 308   // Likewise ExternalSymbol -> TargetExternalSymbol.
 309   if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(Callee)) {
 310     auto GV = G->getGlobal();
 311     fail(CLI.DL, DAG,
 312          "A call to global function '" + StringRef(GV->getName())
 313          + "' is not supported. "
 314          + (GV->isDeclaration() ?
 315            "Only calls to predefined BPF helpers are allowed." :
 316            "Please use __attribute__((always_inline) to make sure"
 317            " this function is inlined."));
 318     Callee = DAG.getTargetGlobalAddress(G->getGlobal(), CLI.DL, PtrVT,
 319                                         G->getOffset(), 0);
 320   } else if (ExternalSymbolSDNode *E = dyn_cast<ExternalSymbolSDNode>(Callee)) {
 321     Callee = DAG.getTargetExternalSymbol(E->getSymbol(), PtrVT, 0);
 322     fail(CLI.DL, DAG, Twine("A call to built-in function '"
 323                             + StringRef(E->getSymbol())
 324                             + "' is not supported."));
 325   }
 326
 327   // Returns a chain & a flag for retval copy to use.
 328   SDVTList NodeTys = DAG.getVTList(MVT::Other, MVT::Glue);
 329   SmallVector<SDValue, 8> Ops;
 330   Ops.push_back(Chain);
 331   Ops.push_back(Callee);
 332
 333   // Add argument registers to the end of the list so that they are
 334   // known live into the call.
 335   for (auto &Reg : RegsToPass)
 336     Ops.push_back(DAG.getRegister(Reg.first, Reg.second.getValueType()));
 337
 338   if (InFlag.getNode())
 339     Ops.push_back(InFlag);
 340
 341   Chain = DAG.getNode(BPFISD::CALL, CLI.DL, NodeTys, Ops);
 342   InFlag = Chain.getValue(1);
 343
 344   // Create the CALLSEQ_END node.
 345   Chain = DAG.getCALLSEQ_END(
 346       Chain, DAG.getConstant(NumBytes, CLI.DL, PtrVT, true),
 347       DAG.getConstant(0, CLI.DL, PtrVT, true), InFlag, CLI.DL);
 348   InFlag = Chain.getValue(1);
 349
 350   // Handle result values, copying them out of physregs into vregs that we
 351   // return.
 352   return LowerCallResult(Chain, InFlag, CallConv, IsVarArg, Ins, CLI.DL, DAG,
 353                          InVals);
 354 }
 355
 356 SDValue
 357 BPFTargetLowering::LowerReturn(SDValue Chain, CallingConv::ID CallConv,
 358                                bool IsVarArg,
 359                                const SmallVectorImpl<ISD::OutputArg> &Outs,
 360                                const SmallVectorImpl<SDValue> &OutVals,
 361                                const SDLoc &DL, SelectionDAG &DAG) const {
 362   unsigned Opc = BPFISD::RET_FLAG;
 363
 364   // CCValAssign - represent the assignment of the return value to a location
 365   SmallVector<CCValAssign, 16> RVLocs;
 366   MachineFunction &MF = DAG.getMachineFunction();
 367
 368   // CCState - Info about the registers and stack slot.
 369   CCState CCInfo(CallConv, IsVarArg, MF, RVLocs, *DAG.getContext());
 370
 371   if (MF.getFunction()->getReturnType()->isAggregateType()) {
 372     fail(DL, DAG, "only integer returns supported");
 373     return DAG.getNode(Opc, DL, MVT::Other, Chain);
 374   }
 375
 376   // Analize return values.
 377   CCInfo.AnalyzeReturn(Outs, RetCC_BPF64);
 378
 379   SDValue Flag;
 380   SmallVector<SDValue, 4> RetOps(1, Chain);
 381
 382   // Copy the result values into the output registers.
 383   for (unsigned i = 0; i != RVLocs.size(); ++i) {
 384     CCValAssign &VA = RVLocs[i];
 385     assert(VA.isRegLoc() && "Can only return in registers!");
 386
 387     Chain = DAG.getCopyToReg(Chain, DL, VA.getLocReg(), OutVals[i], Flag);
 388
 389     // Guarantee that all emitted copies are stuck together,
 390     // avoiding something bad.
 391     Flag = Chain.getValue(1);
 392     RetOps.push_back(DAG.getRegister(VA.getLocReg(), VA.getLocVT()));
 393   }
 394
 395   RetOps[0] = Chain; // Update chain.
 396
 397   // Add the flag if we have it.
 398   if (Flag.getNode())
 399     RetOps.push_back(Flag);
 400
 401   return DAG.getNode(Opc, DL, MVT::Other, RetOps);
 402 }
 403
 404 SDValue BPFTargetLowering::LowerCallResult(
 405     SDValue Chain, SDValue InFlag, CallingConv::ID CallConv, bool IsVarArg,
 406     const SmallVectorImpl<ISD::InputArg> &Ins, const SDLoc &DL,
 407     SelectionDAG &DAG, SmallVectorImpl<SDValue> &InVals) const {
 408
 409   MachineFunction &MF = DAG.getMachineFunction();
 410   // Assign locations to each value returned by this call.
 411   SmallVector<CCValAssign, 16> RVLocs;
 412   CCState CCInfo(CallConv, IsVarArg, MF, RVLocs, *DAG.getContext());
 413
 414   if (Ins.size() >= 2) {
 415     fail(DL, DAG, "only small returns supported");
 416     for (unsigned i = 0, e = Ins.size(); i != e; ++i)
 417       InVals.push_back(DAG.getConstant(0, DL, Ins[i].VT));
 418     return DAG.getCopyFromReg(Chain, DL, 1, Ins[0].VT, InFlag).getValue(1);
 419   }
 420
 421   CCInfo.AnalyzeCallResult(Ins, RetCC_BPF64);
 422
 423   // Copy all of the result registers out of their specified physreg.
 424   for (auto &Val : RVLocs) {
 425     Chain = DAG.getCopyFromReg(Chain, DL, Val.getLocReg(),
 426                                Val.getValVT(), InFlag).getValue(1);
 427     InFlag = Chain.getValue(2);
 428     InVals.push_back(Chain.getValue(0));
 429   }
 430
 431   return Chain;
 432 }
 433
 434 static void NegateCC(SDValue &LHS, SDValue &RHS, ISD::CondCode &CC) {
 435   switch (CC) {
 436   default:
 437     break;
 438   case ISD::SETULT:
 439   case ISD::SETULE:
 440   case ISD::SETLT:
 441   case ISD::SETLE:
 442     CC = ISD::getSetCCSwappedOperands(CC);
 443     std::swap(LHS, RHS);
 444     break;
 445   }
 446 }
 447
 448 SDValue BPFTargetLowering::LowerBR_CC(SDValue Op, SelectionDAG &DAG) const {
 449   SDValue Chain = Op.getOperand(0);
 450   ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(1))->get();
 451   SDValue LHS = Op.getOperand(2);
 452   SDValue RHS = Op.getOperand(3);
 453   SDValue Dest = Op.getOperand(4);
 454   SDLoc DL(Op);
 455
 456   NegateCC(LHS, RHS, CC);
 457
 458   return DAG.getNode(BPFISD::BR_CC, DL, Op.getValueType(), Chain, LHS, RHS,
 459                      DAG.getConstant(CC, DL, MVT::i64), Dest);
 460 }
 461
 462 SDValue BPFTargetLowering::LowerSELECT_CC(SDValue Op, SelectionDAG &DAG) const {
 463   SDValue LHS = Op.getOperand(0);
 464   SDValue RHS = Op.getOperand(1);
 465   SDValue TrueV = Op.getOperand(2);
 466   SDValue FalseV = Op.getOperand(3);
 467   ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(4))->get();
 468   SDLoc DL(Op);
 469
 470   NegateCC(LHS, RHS, CC);
 471
 472   SDValue TargetCC = DAG.getConstant(CC, DL, MVT::i64);
 473
 474   SDVTList VTs = DAG.getVTList(Op.getValueType(), MVT::Glue);
 475   SDValue Ops[] = {LHS, RHS, TargetCC, TrueV, FalseV};
 476
 477   return DAG.getNode(BPFISD::SELECT_CC, DL, VTs, Ops);
 478 }
 479
 480 const char *BPFTargetLowering::getTargetNodeName(unsigned Opcode) const {
 481   switch ((BPFISD::NodeType)Opcode) {
 482   case BPFISD::FIRST_NUMBER:
 483     break;
 484   case BPFISD::RET_FLAG:
 485     return "BPFISD::RET_FLAG";
 486   case BPFISD::CALL:
 487     return "BPFISD::CALL";
 488   case BPFISD::SELECT_CC:
 489     return "BPFISD::SELECT_CC";
 490   case BPFISD::BR_CC:
 491     return "BPFISD::BR_CC";
 492   case BPFISD::Wrapper:
 493     return "BPFISD::Wrapper";
 494   }
 495   return nullptr;
 496 }
 497
 498 SDValue BPFTargetLowering::LowerGlobalAddress(SDValue Op,
 499                                               SelectionDAG &DAG) const {
 500   SDLoc DL(Op);
 501   const GlobalValue *GV = cast<GlobalAddressSDNode>(Op)->getGlobal();
 502   SDValue GA = DAG.getTargetGlobalAddress(GV, DL, MVT::i64);
 503
 504   return DAG.getNode(BPFISD::Wrapper, DL, MVT::i64, GA);
 505 }
 506
 507 MachineBasicBlock *
 508 BPFTargetLowering::EmitInstrWithCustomInserter(MachineInstr &MI,
 509                                                MachineBasicBlock *BB) const {
 510   const TargetInstrInfo &TII = *BB->getParent()->getSubtarget().getInstrInfo();
 511   DebugLoc DL = MI.getDebugLoc();
 512
 513   assert(MI.getOpcode() == BPF::Select && "Unexpected instr type to insert");
 514
 515   // To "insert" a SELECT instruction, we actually have to insert the diamond
 516   // control-flow pattern.  The incoming instruction knows the destination vreg
 517   // to set, the condition code register to branch on, the true/false values to
 518   // select between, and a branch opcode to use.
 519   const BasicBlock *LLVM_BB = BB->getBasicBlock();
 520   MachineFunction::iterator I = ++BB->getIterator();
 521
 522   // ThisMBB:
 523   // ...
 524   //  TrueVal = ...
 525   //  jmp_XX r1, r2 goto Copy1MBB
 526   //  fallthrough --> Copy0MBB
 527   MachineBasicBlock *ThisMBB = BB;
 528   MachineFunction *F = BB->getParent();
 529   MachineBasicBlock *Copy0MBB = F->CreateMachineBasicBlock(LLVM_BB);
 530   MachineBasicBlock *Copy1MBB = F->CreateMachineBasicBlock(LLVM_BB);
 531
 532   F->insert(I, Copy0MBB);
 533   F->insert(I, Copy1MBB);
 534   // Update machine-CFG edges by transferring all successors of the current
 535   // block to the new block which will contain the Phi node for the select.
 536   Copy1MBB->splice(Copy1MBB->begin(), BB,
 537                    std::next(MachineBasicBlock::iterator(MI)), BB->end());
 538   Copy1MBB->transferSuccessorsAndUpdatePHIs(BB);
 539   // Next, add the true and fallthrough blocks as its successors.
 540   BB->addSuccessor(Copy0MBB);
 541   BB->addSuccessor(Copy1MBB);
 542
 543   // Insert Branch if Flag
 544   unsigned LHS = MI.getOperand(1).getReg();
 545   unsigned RHS = MI.getOperand(2).getReg();
 546   int CC = MI.getOperand(3).getImm();
 547   switch (CC) {
 548   case ISD::SETGT:
 549     BuildMI(BB, DL, TII.get(BPF::JSGT_rr))
 550         .addReg(LHS)
 551         .addReg(RHS)
 552         .addMBB(Copy1MBB);
 553     break;
 554   case ISD::SETUGT:
 555     BuildMI(BB, DL, TII.get(BPF::JUGT_rr))
 556         .addReg(LHS)
 557         .addReg(RHS)
 558         .addMBB(Copy1MBB);
 559     break;
 560   case ISD::SETGE:
 561     BuildMI(BB, DL, TII.get(BPF::JSGE_rr))
 562         .addReg(LHS)
 563         .addReg(RHS)
 564         .addMBB(Copy1MBB);
 565     break;
 566   case ISD::SETUGE:
 567     BuildMI(BB, DL, TII.get(BPF::JUGE_rr))
 568         .addReg(LHS)
 569         .addReg(RHS)
 570         .addMBB(Copy1MBB);
 571     break;
 572   case ISD::SETEQ:
 573     BuildMI(BB, DL, TII.get(BPF::JEQ_rr))
 574         .addReg(LHS)
 575         .addReg(RHS)
 576         .addMBB(Copy1MBB);
 577     break;
 578   case ISD::SETNE:
 579     BuildMI(BB, DL, TII.get(BPF::JNE_rr))
 580         .addReg(LHS)
 581         .addReg(RHS)
 582         .addMBB(Copy1MBB);
 583     break;
 584   default:
 585     report_fatal_error("unimplemented select CondCode " + Twine(CC));
 586   }
 587
 588   // Copy0MBB:
 589   //  %FalseValue = ...
 590   //  # fallthrough to Copy1MBB
 591   BB = Copy0MBB;
 592
 593   // Update machine-CFG edges
 594   BB->addSuccessor(Copy1MBB);
 595
 596   // Copy1MBB:
 597   //  %Result = phi [ %FalseValue, Copy0MBB ], [ %TrueValue, ThisMBB ]
 598   // ...
 599   BB = Copy1MBB;
 600   BuildMI(*BB, BB->begin(), DL, TII.get(BPF::PHI), MI.getOperand(0).getReg())
 601       .addReg(MI.getOperand(5).getReg())
 602       .addMBB(Copy0MBB)
 603       .addReg(MI.getOperand(4).getReg())
 604       .addMBB(ThisMBB);
 605
 606   MI.eraseFromParent(); // The pseudo instruction is gone now.
 607   return BB;
 608 }