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