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 char *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     Callee = DAG.getTargetGlobalAddress(G->getGlobal(), CLI.DL, PtrVT,
 311                                         G->getOffset(), 0);
 312   else if (ExternalSymbolSDNode *E = dyn_cast<ExternalSymbolSDNode>(Callee))
 313     Callee = DAG.getTargetExternalSymbol(E->getSymbol(), PtrVT, 0);
 314
 315   // Returns a chain & a flag for retval copy to use.
 316   SDVTList NodeTys = DAG.getVTList(MVT::Other, MVT::Glue);
 317   SmallVector<SDValue, 8> Ops;
 318   Ops.push_back(Chain);
 319   Ops.push_back(Callee);
 320
 321   // Add argument registers to the end of the list so that they are
 322   // known live into the call.
 323   for (auto &Reg : RegsToPass)
 324     Ops.push_back(DAG.getRegister(Reg.first, Reg.second.getValueType()));
 325
 326   if (InFlag.getNode())
 327     Ops.push_back(InFlag);
 328
 329   Chain = DAG.getNode(BPFISD::CALL, CLI.DL, NodeTys, Ops);
 330   InFlag = Chain.getValue(1);
 331
 332   // Create the CALLSEQ_END node.
 333   Chain = DAG.getCALLSEQ_END(
 334       Chain, DAG.getConstant(NumBytes, CLI.DL, PtrVT, true),
 335       DAG.getConstant(0, CLI.DL, PtrVT, true), InFlag, CLI.DL);
 336   InFlag = Chain.getValue(1);
 337
 338   // Handle result values, copying them out of physregs into vregs that we
 339   // return.
 340   return LowerCallResult(Chain, InFlag, CallConv, IsVarArg, Ins, CLI.DL, DAG,
 341                          InVals);
 342 }
 343
 344 SDValue
 345 BPFTargetLowering::LowerReturn(SDValue Chain, CallingConv::ID CallConv,
 346                                bool IsVarArg,
 347                                const SmallVectorImpl<ISD::OutputArg> &Outs,
 348                                const SmallVectorImpl<SDValue> &OutVals,
 349                                const SDLoc &DL, SelectionDAG &DAG) const {
 350   unsigned Opc = BPFISD::RET_FLAG;
 351
 352   // CCValAssign - represent the assignment of the return value to a location
 353   SmallVector<CCValAssign, 16> RVLocs;
 354   MachineFunction &MF = DAG.getMachineFunction();
 355
 356   // CCState - Info about the registers and stack slot.
 357   CCState CCInfo(CallConv, IsVarArg, MF, RVLocs, *DAG.getContext());
 358
 359   if (MF.getFunction()->getReturnType()->isAggregateType()) {
 360     fail(DL, DAG, "only integer returns supported");
 361     return DAG.getNode(Opc, DL, MVT::Other, Chain);
 362   }
 363
 364   // Analize return values.
 365   CCInfo.AnalyzeReturn(Outs, RetCC_BPF64);
 366
 367   SDValue Flag;
 368   SmallVector<SDValue, 4> RetOps(1, Chain);
 369
 370   // Copy the result values into the output registers.
 371   for (unsigned i = 0; i != RVLocs.size(); ++i) {
 372     CCValAssign &VA = RVLocs[i];
 373     assert(VA.isRegLoc() && "Can only return in registers!");
 374
 375     Chain = DAG.getCopyToReg(Chain, DL, VA.getLocReg(), OutVals[i], Flag);
 376
 377     // Guarantee that all emitted copies are stuck together,
 378     // avoiding something bad.
 379     Flag = Chain.getValue(1);
 380     RetOps.push_back(DAG.getRegister(VA.getLocReg(), VA.getLocVT()));
 381   }
 382
 383   RetOps[0] = Chain; // Update chain.
 384
 385   // Add the flag if we have it.
 386   if (Flag.getNode())
 387     RetOps.push_back(Flag);
 388
 389   return DAG.getNode(Opc, DL, MVT::Other, RetOps);
 390 }
 391
 392 SDValue BPFTargetLowering::LowerCallResult(
 393     SDValue Chain, SDValue InFlag, CallingConv::ID CallConv, bool IsVarArg,
 394     const SmallVectorImpl<ISD::InputArg> &Ins, const SDLoc &DL,
 395     SelectionDAG &DAG, SmallVectorImpl<SDValue> &InVals) const {
 396
 397   MachineFunction &MF = DAG.getMachineFunction();
 398   // Assign locations to each value returned by this call.
 399   SmallVector<CCValAssign, 16> RVLocs;
 400   CCState CCInfo(CallConv, IsVarArg, MF, RVLocs, *DAG.getContext());
 401
 402   if (Ins.size() >= 2) {
 403     fail(DL, DAG, "only small returns supported");
 404     for (unsigned i = 0, e = Ins.size(); i != e; ++i)
 405       InVals.push_back(DAG.getConstant(0, DL, Ins[i].VT));
 406     return DAG.getCopyFromReg(Chain, DL, 1, Ins[0].VT, InFlag).getValue(1);
 407   }
 408
 409   CCInfo.AnalyzeCallResult(Ins, RetCC_BPF64);
 410
 411   // Copy all of the result registers out of their specified physreg.
 412   for (auto &Val : RVLocs) {
 413     Chain = DAG.getCopyFromReg(Chain, DL, Val.getLocReg(),
 414                                Val.getValVT(), InFlag).getValue(1);
 415     InFlag = Chain.getValue(2);
 416     InVals.push_back(Chain.getValue(0));
 417   }
 418
 419   return Chain;
 420 }
 421
 422 static void NegateCC(SDValue &LHS, SDValue &RHS, ISD::CondCode &CC) {
 423   switch (CC) {
 424   default:
 425     break;
 426   case ISD::SETULT:
 427   case ISD::SETULE:
 428   case ISD::SETLT:
 429   case ISD::SETLE:
 430     CC = ISD::getSetCCSwappedOperands(CC);
 431     std::swap(LHS, RHS);
 432     break;
 433   }
 434 }
 435
 436 SDValue BPFTargetLowering::LowerBR_CC(SDValue Op, SelectionDAG &DAG) const {
 437   SDValue Chain = Op.getOperand(0);
 438   ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(1))->get();
 439   SDValue LHS = Op.getOperand(2);
 440   SDValue RHS = Op.getOperand(3);
 441   SDValue Dest = Op.getOperand(4);
 442   SDLoc DL(Op);
 443
 444   NegateCC(LHS, RHS, CC);
 445
 446   return DAG.getNode(BPFISD::BR_CC, DL, Op.getValueType(), Chain, LHS, RHS,
 447                      DAG.getConstant(CC, DL, MVT::i64), Dest);
 448 }
 449
 450 SDValue BPFTargetLowering::LowerSELECT_CC(SDValue Op, SelectionDAG &DAG) const {
 451   SDValue LHS = Op.getOperand(0);
 452   SDValue RHS = Op.getOperand(1);
 453   SDValue TrueV = Op.getOperand(2);
 454   SDValue FalseV = Op.getOperand(3);
 455   ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(4))->get();
 456   SDLoc DL(Op);
 457
 458   NegateCC(LHS, RHS, CC);
 459
 460   SDValue TargetCC = DAG.getConstant(CC, DL, MVT::i64);
 461
 462   SDVTList VTs = DAG.getVTList(Op.getValueType(), MVT::Glue);
 463   SDValue Ops[] = {LHS, RHS, TargetCC, TrueV, FalseV};
 464
 465   return DAG.getNode(BPFISD::SELECT_CC, DL, VTs, Ops);
 466 }
 467
 468 const char *BPFTargetLowering::getTargetNodeName(unsigned Opcode) const {
 469   switch ((BPFISD::NodeType)Opcode) {
 470   case BPFISD::FIRST_NUMBER:
 471     break;
 472   case BPFISD::RET_FLAG:
 473     return "BPFISD::RET_FLAG";
 474   case BPFISD::CALL:
 475     return "BPFISD::CALL";
 476   case BPFISD::SELECT_CC:
 477     return "BPFISD::SELECT_CC";
 478   case BPFISD::BR_CC:
 479     return "BPFISD::BR_CC";
 480   case BPFISD::Wrapper:
 481     return "BPFISD::Wrapper";
 482   }
 483   return nullptr;
 484 }
 485
 486 SDValue BPFTargetLowering::LowerGlobalAddress(SDValue Op,
 487                                               SelectionDAG &DAG) const {
 488   SDLoc DL(Op);
 489   const GlobalValue *GV = cast<GlobalAddressSDNode>(Op)->getGlobal();
 490   SDValue GA = DAG.getTargetGlobalAddress(GV, DL, MVT::i64);
 491
 492   return DAG.getNode(BPFISD::Wrapper, DL, MVT::i64, GA);
 493 }
 494
 495 MachineBasicBlock *
 496 BPFTargetLowering::EmitInstrWithCustomInserter(MachineInstr &MI,
 497                                                MachineBasicBlock *BB) const {
 498   const TargetInstrInfo &TII = *BB->getParent()->getSubtarget().getInstrInfo();
 499   DebugLoc DL = MI.getDebugLoc();
 500
 501   assert(MI.getOpcode() == BPF::Select && "Unexpected instr type to insert");
 502
 503   // To "insert" a SELECT instruction, we actually have to insert the diamond
 504   // control-flow pattern.  The incoming instruction knows the destination vreg
 505   // to set, the condition code register to branch on, the true/false values to
 506   // select between, and a branch opcode to use.
 507   const BasicBlock *LLVM_BB = BB->getBasicBlock();
 508   MachineFunction::iterator I = ++BB->getIterator();
 509
 510   // ThisMBB:
 511   // ...
 512   //  TrueVal = ...
 513   //  jmp_XX r1, r2 goto Copy1MBB
 514   //  fallthrough --> Copy0MBB
 515   MachineBasicBlock *ThisMBB = BB;
 516   MachineFunction *F = BB->getParent();
 517   MachineBasicBlock *Copy0MBB = F->CreateMachineBasicBlock(LLVM_BB);
 518   MachineBasicBlock *Copy1MBB = F->CreateMachineBasicBlock(LLVM_BB);
 519
 520   F->insert(I, Copy0MBB);
 521   F->insert(I, Copy1MBB);
 522   // Update machine-CFG edges by transferring all successors of the current
 523   // block to the new block which will contain the Phi node for the select.
 524   Copy1MBB->splice(Copy1MBB->begin(), BB,
 525                    std::next(MachineBasicBlock::iterator(MI)), BB->end());
 526   Copy1MBB->transferSuccessorsAndUpdatePHIs(BB);
 527   // Next, add the true and fallthrough blocks as its successors.
 528   BB->addSuccessor(Copy0MBB);
 529   BB->addSuccessor(Copy1MBB);
 530
 531   // Insert Branch if Flag
 532   unsigned LHS = MI.getOperand(1).getReg();
 533   unsigned RHS = MI.getOperand(2).getReg();
 534   int CC = MI.getOperand(3).getImm();
 535   switch (CC) {
 536   case ISD::SETGT:
 537     BuildMI(BB, DL, TII.get(BPF::JSGT_rr))
 538         .addReg(LHS)
 539         .addReg(RHS)
 540         .addMBB(Copy1MBB);
 541     break;
 542   case ISD::SETUGT:
 543     BuildMI(BB, DL, TII.get(BPF::JUGT_rr))
 544         .addReg(LHS)
 545         .addReg(RHS)
 546         .addMBB(Copy1MBB);
 547     break;
 548   case ISD::SETGE:
 549     BuildMI(BB, DL, TII.get(BPF::JSGE_rr))
 550         .addReg(LHS)
 551         .addReg(RHS)
 552         .addMBB(Copy1MBB);
 553     break;
 554   case ISD::SETUGE:
 555     BuildMI(BB, DL, TII.get(BPF::JUGE_rr))
 556         .addReg(LHS)
 557         .addReg(RHS)
 558         .addMBB(Copy1MBB);
 559     break;
 560   case ISD::SETEQ:
 561     BuildMI(BB, DL, TII.get(BPF::JEQ_rr))
 562         .addReg(LHS)
 563         .addReg(RHS)
 564         .addMBB(Copy1MBB);
 565     break;
 566   case ISD::SETNE:
 567     BuildMI(BB, DL, TII.get(BPF::JNE_rr))
 568         .addReg(LHS)
 569         .addReg(RHS)
 570         .addMBB(Copy1MBB);
 571     break;
 572   default:
 573     report_fatal_error("unimplemented select CondCode " + Twine(CC));
 574   }
 575
 576   // Copy0MBB:
 577   //  %FalseValue = ...
 578   //  # fallthrough to Copy1MBB
 579   BB = Copy0MBB;
 580
 581   // Update machine-CFG edges
 582   BB->addSuccessor(Copy1MBB);
 583
 584   // Copy1MBB:
 585   //  %Result = phi [ %FalseValue, Copy0MBB ], [ %TrueValue, ThisMBB ]
 586   // ...
 587   BB = Copy1MBB;
 588   BuildMI(*BB, BB->begin(), DL, TII.get(BPF::PHI), MI.getOperand(0).getReg())
 589       .addReg(MI.getOperand(5).getReg())
 590       .addMBB(Copy0MBB)
 591       .addReg(MI.getOperand(4).getReg())
 592       .addMBB(ThisMBB);
 593
 594   MI.eraseFromParent(); // The pseudo instruction is gone now.
 595   return BB;
 596 }