1 //===-- ARMISelDAGToDAG.cpp - A dag to dag inst selector for ARM ----------===//
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 an instruction selector for the ARM target.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "ARM.h"
15 #include "ARMAddressingModes.h"
16 #include "ARMConstantPoolValue.h"
17 #include "ARMISelLowering.h"
18 #include "ARMTargetMachine.h"
19 #include "llvm/CallingConv.h"
20 #include "llvm/Constants.h"
21 #include "llvm/DerivedTypes.h"
22 #include "llvm/Function.h"
23 #include "llvm/Intrinsics.h"
24 #include "llvm/CodeGen/MachineFrameInfo.h"
25 #include "llvm/CodeGen/MachineFunction.h"
26 #include "llvm/CodeGen/MachineInstrBuilder.h"
27 #include "llvm/CodeGen/SelectionDAG.h"
28 #include "llvm/CodeGen/SelectionDAGISel.h"
29 #include "llvm/Target/TargetLowering.h"
30 #include "llvm/Target/TargetOptions.h"
31 #include "llvm/Support/Compiler.h"
32 #include "llvm/Support/Debug.h"
33 #include "llvm/Support/ErrorHandling.h"
34 #include "llvm/Support/raw_ostream.h"
35 
36 using namespace llvm;
37 
38 static const unsigned arm_dsubreg_0 = 5;
39 static const unsigned arm_dsubreg_1 = 6;
40 
41 //===--------------------------------------------------------------------===//
42 /// ARMDAGToDAGISel - ARM specific code to select ARM machine
43 /// instructions for SelectionDAG operations.
44 ///
45 namespace {
46 class ARMDAGToDAGISel : public SelectionDAGISel {
47   ARMBaseTargetMachine &TM;
48 
49   /// Subtarget - Keep a pointer to the ARMSubtarget around so that we can
50   /// make the right decision when generating code for different targets.
51   const ARMSubtarget *Subtarget;
52 
53 public:
54   explicit ARMDAGToDAGISel(ARMBaseTargetMachine &tm)
55     : SelectionDAGISel(tm), TM(tm),
56     Subtarget(&TM.getSubtarget<ARMSubtarget>()) {
57   }
58 
59   virtual const char *getPassName() const {
60     return "ARM Instruction Selection";
61   }
62 
63  /// getI32Imm - Return a target constant with the specified value, of type i32.
64   inline SDValue getI32Imm(unsigned Imm) {
65     return CurDAG->getTargetConstant(Imm, MVT::i32);
66   }
67 
68   SDNode *Select(SDValue Op);
69   virtual void InstructionSelect();
70   bool SelectShifterOperandReg(SDValue Op, SDValue N, SDValue &A,
71                                SDValue &B, SDValue &C);
72   bool SelectAddrMode2(SDValue Op, SDValue N, SDValue &Base,
73                        SDValue &Offset, SDValue &Opc);
74   bool SelectAddrMode2Offset(SDValue Op, SDValue N,
75                              SDValue &Offset, SDValue &Opc);
76   bool SelectAddrMode3(SDValue Op, SDValue N, SDValue &Base,
77                        SDValue &Offset, SDValue &Opc);
78   bool SelectAddrMode3Offset(SDValue Op, SDValue N,
79                              SDValue &Offset, SDValue &Opc);
80   bool SelectAddrMode5(SDValue Op, SDValue N, SDValue &Base,
81                        SDValue &Offset);
82   bool SelectAddrMode6(SDValue Op, SDValue N, SDValue &Addr, SDValue &Update,
83                        SDValue &Opc);
84 
85   bool SelectAddrModePC(SDValue Op, SDValue N, SDValue &Offset,
86                         SDValue &Label);
87 
88   bool SelectThumbAddrModeRR(SDValue Op, SDValue N, SDValue &Base,
89                              SDValue &Offset);
90   bool SelectThumbAddrModeRI5(SDValue Op, SDValue N, unsigned Scale,
91                               SDValue &Base, SDValue &OffImm,
92                               SDValue &Offset);
93   bool SelectThumbAddrModeS1(SDValue Op, SDValue N, SDValue &Base,
94                              SDValue &OffImm, SDValue &Offset);
95   bool SelectThumbAddrModeS2(SDValue Op, SDValue N, SDValue &Base,
96                              SDValue &OffImm, SDValue &Offset);
97   bool SelectThumbAddrModeS4(SDValue Op, SDValue N, SDValue &Base,
98                              SDValue &OffImm, SDValue &Offset);
99   bool SelectThumbAddrModeSP(SDValue Op, SDValue N, SDValue &Base,
100                              SDValue &OffImm);
101 
102   bool SelectT2ShifterOperandReg(SDValue Op, SDValue N,
103                                  SDValue &BaseReg, SDValue &Opc);
104   bool SelectT2AddrModeImm12(SDValue Op, SDValue N, SDValue &Base,
105                              SDValue &OffImm);
106   bool SelectT2AddrModeImm8(SDValue Op, SDValue N, SDValue &Base,
107                             SDValue &OffImm);
108   bool SelectT2AddrModeImm8Offset(SDValue Op, SDValue N,
109                                  SDValue &OffImm);
110   bool SelectT2AddrModeImm8s4(SDValue Op, SDValue N, SDValue &Base,
111                               SDValue &OffImm);
112   bool SelectT2AddrModeSoReg(SDValue Op, SDValue N, SDValue &Base,
113                              SDValue &OffReg, SDValue &ShImm);
114 
115   // Include the pieces autogenerated from the target description.
116 #include "ARMGenDAGISel.inc"
117 
118 private:
119   /// SelectARMIndexedLoad - Indexed (pre/post inc/dec) load matching code for
120   /// ARM.
121   SDNode *SelectARMIndexedLoad(SDValue Op);
122   SDNode *SelectT2IndexedLoad(SDValue Op);
123 
124 
125   /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
126   /// inline asm expressions.
127   virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op,
128                                             char ConstraintCode,
129                                             std::vector<SDValue> &OutOps);
130 };
131 }
132 
133 void ARMDAGToDAGISel::InstructionSelect() {
134   DEBUG(BB->dump());
135 
136   SelectRoot(*CurDAG);
137   CurDAG->RemoveDeadNodes();
138 }
139 
140 bool ARMDAGToDAGISel::SelectShifterOperandReg(SDValue Op,
141                                               SDValue N,
142                                               SDValue &BaseReg,
143                                               SDValue &ShReg,
144                                               SDValue &Opc) {
145   ARM_AM::ShiftOpc ShOpcVal = ARM_AM::getShiftOpcForNode(N);
146 
147   // Don't match base register only case. That is matched to a separate
148   // lower complexity pattern with explicit register operand.
149   if (ShOpcVal == ARM_AM::no_shift) return false;
150 
151   BaseReg = N.getOperand(0);
152   unsigned ShImmVal = 0;
153   if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
154     ShReg = CurDAG->getRegister(0, MVT::i32);
155     ShImmVal = RHS->getZExtValue() & 31;
156   } else {
157     ShReg = N.getOperand(1);
158   }
159   Opc = CurDAG->getTargetConstant(ARM_AM::getSORegOpc(ShOpcVal, ShImmVal),
160                                   MVT::i32);
161   return true;
162 }
163 
164 bool ARMDAGToDAGISel::SelectAddrMode2(SDValue Op, SDValue N,
165                                       SDValue &Base, SDValue &Offset,
166                                       SDValue &Opc) {
167   if (N.getOpcode() == ISD::MUL) {
168     if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
169       // X * [3,5,9] -> X + X * [2,4,8] etc.
170       int RHSC = (int)RHS->getZExtValue();
171       if (RHSC & 1) {
172         RHSC = RHSC & ~1;
173         ARM_AM::AddrOpc AddSub = ARM_AM::add;
174         if (RHSC < 0) {
175           AddSub = ARM_AM::sub;
176           RHSC = - RHSC;
177         }
178         if (isPowerOf2_32(RHSC)) {
179           unsigned ShAmt = Log2_32(RHSC);
180           Base = Offset = N.getOperand(0);
181           Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, ShAmt,
182                                                             ARM_AM::lsl),
183                                           MVT::i32);
184           return true;
185         }
186       }
187     }
188   }
189 
190   if (N.getOpcode() != ISD::ADD && N.getOpcode() != ISD::SUB) {
191     Base = N;
192     if (N.getOpcode() == ISD::FrameIndex) {
193       int FI = cast<FrameIndexSDNode>(N)->getIndex();
194       Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
195     } else if (N.getOpcode() == ARMISD::Wrapper) {
196       Base = N.getOperand(0);
197     }
198     Offset = CurDAG->getRegister(0, MVT::i32);
199     Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(ARM_AM::add, 0,
200                                                       ARM_AM::no_shift),
201                                     MVT::i32);
202     return true;
203   }
204 
205   // Match simple R +/- imm12 operands.
206   if (N.getOpcode() == ISD::ADD)
207     if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
208       int RHSC = (int)RHS->getZExtValue();
209       if ((RHSC >= 0 && RHSC < 0x1000) ||
210           (RHSC < 0 && RHSC > -0x1000)) { // 12 bits.
211         Base = N.getOperand(0);
212         if (Base.getOpcode() == ISD::FrameIndex) {
213           int FI = cast<FrameIndexSDNode>(Base)->getIndex();
214           Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
215         }
216         Offset = CurDAG->getRegister(0, MVT::i32);
217 
218         ARM_AM::AddrOpc AddSub = ARM_AM::add;
219         if (RHSC < 0) {
220           AddSub = ARM_AM::sub;
221           RHSC = - RHSC;
222         }
223         Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, RHSC,
224                                                           ARM_AM::no_shift),
225                                         MVT::i32);
226         return true;
227       }
228     }
229 
230   // Otherwise this is R +/- [possibly shifted] R
231   ARM_AM::AddrOpc AddSub = N.getOpcode() == ISD::ADD ? ARM_AM::add:ARM_AM::sub;
232   ARM_AM::ShiftOpc ShOpcVal = ARM_AM::getShiftOpcForNode(N.getOperand(1));
233   unsigned ShAmt = 0;
234 
235   Base   = N.getOperand(0);
236   Offset = N.getOperand(1);
237 
238   if (ShOpcVal != ARM_AM::no_shift) {
239     // Check to see if the RHS of the shift is a constant, if not, we can't fold
240     // it.
241     if (ConstantSDNode *Sh =
242            dyn_cast<ConstantSDNode>(N.getOperand(1).getOperand(1))) {
243       ShAmt = Sh->getZExtValue();
244       Offset = N.getOperand(1).getOperand(0);
245     } else {
246       ShOpcVal = ARM_AM::no_shift;
247     }
248   }
249 
250   // Try matching (R shl C) + (R).
251   if (N.getOpcode() == ISD::ADD && ShOpcVal == ARM_AM::no_shift) {
252     ShOpcVal = ARM_AM::getShiftOpcForNode(N.getOperand(0));
253     if (ShOpcVal != ARM_AM::no_shift) {
254       // Check to see if the RHS of the shift is a constant, if not, we can't
255       // fold it.
256       if (ConstantSDNode *Sh =
257           dyn_cast<ConstantSDNode>(N.getOperand(0).getOperand(1))) {
258         ShAmt = Sh->getZExtValue();
259         Offset = N.getOperand(0).getOperand(0);
260         Base = N.getOperand(1);
261       } else {
262         ShOpcVal = ARM_AM::no_shift;
263       }
264     }
265   }
266 
267   Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, ShAmt, ShOpcVal),
268                                   MVT::i32);
269   return true;
270 }
271 
272 bool ARMDAGToDAGISel::SelectAddrMode2Offset(SDValue Op, SDValue N,
273                                             SDValue &Offset, SDValue &Opc) {
274   unsigned Opcode = Op.getOpcode();
275   ISD::MemIndexedMode AM = (Opcode == ISD::LOAD)
276     ? cast<LoadSDNode>(Op)->getAddressingMode()
277     : cast<StoreSDNode>(Op)->getAddressingMode();
278   ARM_AM::AddrOpc AddSub = (AM == ISD::PRE_INC || AM == ISD::POST_INC)
279     ? ARM_AM::add : ARM_AM::sub;
280   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N)) {
281     int Val = (int)C->getZExtValue();
282     if (Val >= 0 && Val < 0x1000) { // 12 bits.
283       Offset = CurDAG->getRegister(0, MVT::i32);
284       Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, Val,
285                                                         ARM_AM::no_shift),
286                                       MVT::i32);
287       return true;
288     }
289   }
290 
291   Offset = N;
292   ARM_AM::ShiftOpc ShOpcVal = ARM_AM::getShiftOpcForNode(N);
293   unsigned ShAmt = 0;
294   if (ShOpcVal != ARM_AM::no_shift) {
295     // Check to see if the RHS of the shift is a constant, if not, we can't fold
296     // it.
297     if (ConstantSDNode *Sh = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
298       ShAmt = Sh->getZExtValue();
299       Offset = N.getOperand(0);
300     } else {
301       ShOpcVal = ARM_AM::no_shift;
302     }
303   }
304 
305   Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, ShAmt, ShOpcVal),
306                                   MVT::i32);
307   return true;
308 }
309 
310 
311 bool ARMDAGToDAGISel::SelectAddrMode3(SDValue Op, SDValue N,
312                                       SDValue &Base, SDValue &Offset,
313                                       SDValue &Opc) {
314   if (N.getOpcode() == ISD::SUB) {
315     // X - C  is canonicalize to X + -C, no need to handle it here.
316     Base = N.getOperand(0);
317     Offset = N.getOperand(1);
318     Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(ARM_AM::sub, 0),MVT::i32);
319     return true;
320   }
321 
322   if (N.getOpcode() != ISD::ADD) {
323     Base = N;
324     if (N.getOpcode() == ISD::FrameIndex) {
325       int FI = cast<FrameIndexSDNode>(N)->getIndex();
326       Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
327     }
328     Offset = CurDAG->getRegister(0, MVT::i32);
329     Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(ARM_AM::add, 0),MVT::i32);
330     return true;
331   }
332 
333   // If the RHS is +/- imm8, fold into addr mode.
334   if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
335     int RHSC = (int)RHS->getZExtValue();
336     if ((RHSC >= 0 && RHSC < 256) ||
337         (RHSC < 0 && RHSC > -256)) { // note -256 itself isn't allowed.
338       Base = N.getOperand(0);
339       if (Base.getOpcode() == ISD::FrameIndex) {
340         int FI = cast<FrameIndexSDNode>(Base)->getIndex();
341         Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
342       }
343       Offset = CurDAG->getRegister(0, MVT::i32);
344 
345       ARM_AM::AddrOpc AddSub = ARM_AM::add;
346       if (RHSC < 0) {
347         AddSub = ARM_AM::sub;
348         RHSC = - RHSC;
349       }
350       Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(AddSub, RHSC),MVT::i32);
351       return true;
352     }
353   }
354 
355   Base = N.getOperand(0);
356   Offset = N.getOperand(1);
357   Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(ARM_AM::add, 0), MVT::i32);
358   return true;
359 }
360 
361 bool ARMDAGToDAGISel::SelectAddrMode3Offset(SDValue Op, SDValue N,
362                                             SDValue &Offset, SDValue &Opc) {
363   unsigned Opcode = Op.getOpcode();
364   ISD::MemIndexedMode AM = (Opcode == ISD::LOAD)
365     ? cast<LoadSDNode>(Op)->getAddressingMode()
366     : cast<StoreSDNode>(Op)->getAddressingMode();
367   ARM_AM::AddrOpc AddSub = (AM == ISD::PRE_INC || AM == ISD::POST_INC)
368     ? ARM_AM::add : ARM_AM::sub;
369   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N)) {
370     int Val = (int)C->getZExtValue();
371     if (Val >= 0 && Val < 256) {
372       Offset = CurDAG->getRegister(0, MVT::i32);
373       Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(AddSub, Val), MVT::i32);
374       return true;
375     }
376   }
377 
378   Offset = N;
379   Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(AddSub, 0), MVT::i32);
380   return true;
381 }
382 
383 
384 bool ARMDAGToDAGISel::SelectAddrMode5(SDValue Op, SDValue N,
385                                       SDValue &Base, SDValue &Offset) {
386   if (N.getOpcode() != ISD::ADD) {
387     Base = N;
388     if (N.getOpcode() == ISD::FrameIndex) {
389       int FI = cast<FrameIndexSDNode>(N)->getIndex();
390       Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
391     } else if (N.getOpcode() == ARMISD::Wrapper) {
392       Base = N.getOperand(0);
393     }
394     Offset = CurDAG->getTargetConstant(ARM_AM::getAM5Opc(ARM_AM::add, 0),
395                                        MVT::i32);
396     return true;
397   }
398 
399   // If the RHS is +/- imm8, fold into addr mode.
400   if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
401     int RHSC = (int)RHS->getZExtValue();
402     if ((RHSC & 3) == 0) {  // The constant is implicitly multiplied by 4.
403       RHSC >>= 2;
404       if ((RHSC >= 0 && RHSC < 256) ||
405           (RHSC < 0 && RHSC > -256)) { // note -256 itself isn't allowed.
406         Base = N.getOperand(0);
407         if (Base.getOpcode() == ISD::FrameIndex) {
408           int FI = cast<FrameIndexSDNode>(Base)->getIndex();
409           Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
410         }
411 
412         ARM_AM::AddrOpc AddSub = ARM_AM::add;
413         if (RHSC < 0) {
414           AddSub = ARM_AM::sub;
415           RHSC = - RHSC;
416         }
417         Offset = CurDAG->getTargetConstant(ARM_AM::getAM5Opc(AddSub, RHSC),
418                                            MVT::i32);
419         return true;
420       }
421     }
422   }
423 
424   Base = N;
425   Offset = CurDAG->getTargetConstant(ARM_AM::getAM5Opc(ARM_AM::add, 0),
426                                      MVT::i32);
427   return true;
428 }
429 
430 bool ARMDAGToDAGISel::SelectAddrMode6(SDValue Op, SDValue N,
431                                       SDValue &Addr, SDValue &Update,
432                                       SDValue &Opc) {
433   Addr = N;
434   // The optional writeback is handled in ARMLoadStoreOpt.
435   Update = CurDAG->getRegister(0, MVT::i32);
436   Opc = CurDAG->getTargetConstant(ARM_AM::getAM6Opc(false), MVT::i32);
437   return true;
438 }
439 
440 bool ARMDAGToDAGISel::SelectAddrModePC(SDValue Op, SDValue N,
441                                         SDValue &Offset, SDValue &Label) {
442   if (N.getOpcode() == ARMISD::PIC_ADD && N.hasOneUse()) {
443     Offset = N.getOperand(0);
444     SDValue N1 = N.getOperand(1);
445     Label  = CurDAG->getTargetConstant(cast<ConstantSDNode>(N1)->getZExtValue(),
446                                        MVT::i32);
447     return true;
448   }
449   return false;
450 }
451 
452 bool ARMDAGToDAGISel::SelectThumbAddrModeRR(SDValue Op, SDValue N,
453                                             SDValue &Base, SDValue &Offset){
454   // FIXME dl should come from the parent load or store, not the address
455   DebugLoc dl = Op.getDebugLoc();
456   if (N.getOpcode() != ISD::ADD) {
457     Base = N;
458     // We must materialize a zero in a reg! Returning a constant here
459     // wouldn't work without additional code to position the node within
460     // ISel's topological ordering in a place where ISel will process it
461     // normally.  Instead, just explicitly issue a tMOVri8 node!
462     Offset = SDValue(CurDAG->getTargetNode(ARM::tMOVi8, dl, MVT::i32,
463                                     CurDAG->getTargetConstant(0, MVT::i32)), 0);
464     return true;
465   }
466 
467   Base = N.getOperand(0);
468   Offset = N.getOperand(1);
469   return true;
470 }
471 
472 bool
473 ARMDAGToDAGISel::SelectThumbAddrModeRI5(SDValue Op, SDValue N,
474                                         unsigned Scale, SDValue &Base,
475                                         SDValue &OffImm, SDValue &Offset) {
476   if (Scale == 4) {
477     SDValue TmpBase, TmpOffImm;
478     if (SelectThumbAddrModeSP(Op, N, TmpBase, TmpOffImm))
479       return false;  // We want to select tLDRspi / tSTRspi instead.
480     if (N.getOpcode() == ARMISD::Wrapper &&
481         N.getOperand(0).getOpcode() == ISD::TargetConstantPool)
482       return false;  // We want to select tLDRpci instead.
483   }
484 
485   if (N.getOpcode() != ISD::ADD) {
486     Base = (N.getOpcode() == ARMISD::Wrapper) ? N.getOperand(0) : N;
487     Offset = CurDAG->getRegister(0, MVT::i32);
488     OffImm = CurDAG->getTargetConstant(0, MVT::i32);
489     return true;
490   }
491 
492   // Thumb does not have [sp, r] address mode.
493   RegisterSDNode *LHSR = dyn_cast<RegisterSDNode>(N.getOperand(0));
494   RegisterSDNode *RHSR = dyn_cast<RegisterSDNode>(N.getOperand(1));
495   if ((LHSR && LHSR->getReg() == ARM::SP) ||
496       (RHSR && RHSR->getReg() == ARM::SP)) {
497     Base = N;
498     Offset = CurDAG->getRegister(0, MVT::i32);
499     OffImm = CurDAG->getTargetConstant(0, MVT::i32);
500     return true;
501   }
502 
503   // If the RHS is + imm5 * scale, fold into addr mode.
504   if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
505     int RHSC = (int)RHS->getZExtValue();
506     if ((RHSC & (Scale-1)) == 0) {  // The constant is implicitly multiplied.
507       RHSC /= Scale;
508       if (RHSC >= 0 && RHSC < 32) {
509         Base = N.getOperand(0);
510         Offset = CurDAG->getRegister(0, MVT::i32);
511         OffImm = CurDAG->getTargetConstant(RHSC, MVT::i32);
512         return true;
513       }
514     }
515   }
516 
517   Base = N.getOperand(0);
518   Offset = N.getOperand(1);
519   OffImm = CurDAG->getTargetConstant(0, MVT::i32);
520   return true;
521 }
522 
523 bool ARMDAGToDAGISel::SelectThumbAddrModeS1(SDValue Op, SDValue N,
524                                             SDValue &Base, SDValue &OffImm,
525                                             SDValue &Offset) {
526   return SelectThumbAddrModeRI5(Op, N, 1, Base, OffImm, Offset);
527 }
528 
529 bool ARMDAGToDAGISel::SelectThumbAddrModeS2(SDValue Op, SDValue N,
530                                             SDValue &Base, SDValue &OffImm,
531                                             SDValue &Offset) {
532   return SelectThumbAddrModeRI5(Op, N, 2, Base, OffImm, Offset);
533 }
534 
535 bool ARMDAGToDAGISel::SelectThumbAddrModeS4(SDValue Op, SDValue N,
536                                             SDValue &Base, SDValue &OffImm,
537                                             SDValue &Offset) {
538   return SelectThumbAddrModeRI5(Op, N, 4, Base, OffImm, Offset);
539 }
540 
541 bool ARMDAGToDAGISel::SelectThumbAddrModeSP(SDValue Op, SDValue N,
542                                            SDValue &Base, SDValue &OffImm) {
543   if (N.getOpcode() == ISD::FrameIndex) {
544     int FI = cast<FrameIndexSDNode>(N)->getIndex();
545     Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
546     OffImm = CurDAG->getTargetConstant(0, MVT::i32);
547     return true;
548   }
549 
550   if (N.getOpcode() != ISD::ADD)
551     return false;
552 
553   RegisterSDNode *LHSR = dyn_cast<RegisterSDNode>(N.getOperand(0));
554   if (N.getOperand(0).getOpcode() == ISD::FrameIndex ||
555       (LHSR && LHSR->getReg() == ARM::SP)) {
556     // If the RHS is + imm8 * scale, fold into addr mode.
557     if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
558       int RHSC = (int)RHS->getZExtValue();
559       if ((RHSC & 3) == 0) {  // The constant is implicitly multiplied.
560         RHSC >>= 2;
561         if (RHSC >= 0 && RHSC < 256) {
562           Base = N.getOperand(0);
563           if (Base.getOpcode() == ISD::FrameIndex) {
564             int FI = cast<FrameIndexSDNode>(Base)->getIndex();
565             Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
566           }
567           OffImm = CurDAG->getTargetConstant(RHSC, MVT::i32);
568           return true;
569         }
570       }
571     }
572   }
573 
574   return false;
575 }
576 
577 bool ARMDAGToDAGISel::SelectT2ShifterOperandReg(SDValue Op, SDValue N,
578                                                 SDValue &BaseReg,
579                                                 SDValue &Opc) {
580   ARM_AM::ShiftOpc ShOpcVal = ARM_AM::getShiftOpcForNode(N);
581 
582   // Don't match base register only case. That is matched to a separate
583   // lower complexity pattern with explicit register operand.
584   if (ShOpcVal == ARM_AM::no_shift) return false;
585 
586   BaseReg = N.getOperand(0);
587   unsigned ShImmVal = 0;
588   if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
589     ShImmVal = RHS->getZExtValue() & 31;
590     Opc = getI32Imm(ARM_AM::getSORegOpc(ShOpcVal, ShImmVal));
591     return true;
592   }
593 
594   return false;
595 }
596 
597 bool ARMDAGToDAGISel::SelectT2AddrModeImm12(SDValue Op, SDValue N,
598                                             SDValue &Base, SDValue &OffImm) {
599   // Match simple R + imm12 operands.
600   if (N.getOpcode() != ISD::ADD)
601     return false;
602 
603   if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
604     int RHSC = (int)RHS->getZExtValue();
605     if (RHSC >= 0 && RHSC < 0x1000) { // 12 bits.
606       Base   = N.getOperand(0);
607       OffImm = CurDAG->getTargetConstant(RHSC, MVT::i32);
608       return true;
609     }
610   }
611 
612   return false;
613 }
614 
615 bool ARMDAGToDAGISel::SelectT2AddrModeImm8(SDValue Op, SDValue N,
616                                            SDValue &Base, SDValue &OffImm) {
617   if (N.getOpcode() == ISD::ADD) {
618     if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
619       int RHSC = (int)RHS->getZExtValue();
620       if (RHSC < 0 && RHSC > -0x100) { // 8 bits.
621         Base   = N.getOperand(0);
622         OffImm = CurDAG->getTargetConstant(RHSC, MVT::i32);
623         return true;
624       }
625     }
626   } else if (N.getOpcode() == ISD::SUB) {
627     if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
628       int RHSC = (int)RHS->getZExtValue();
629       if (RHSC >= 0 && RHSC < 0x100) { // 8 bits.
630         Base   = N.getOperand(0);
631         OffImm = CurDAG->getTargetConstant(-RHSC, MVT::i32);
632         return true;
633       }
634     }
635   }
636 
637   return false;
638 }
639 
640 bool ARMDAGToDAGISel::SelectT2AddrModeImm8Offset(SDValue Op, SDValue N,
641                                                  SDValue &OffImm){
642   unsigned Opcode = Op.getOpcode();
643   ISD::MemIndexedMode AM = (Opcode == ISD::LOAD)
644     ? cast<LoadSDNode>(Op)->getAddressingMode()
645     : cast<StoreSDNode>(Op)->getAddressingMode();
646   if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N)) {
647     int RHSC = (int)RHS->getZExtValue();
648     if (RHSC >= 0 && RHSC < 0x100) { // 8 bits.
649       OffImm = (AM == ISD::PRE_INC)
650         ? CurDAG->getTargetConstant(RHSC, MVT::i32)
651         : CurDAG->getTargetConstant(-RHSC, MVT::i32);
652       return true;
653     }
654   }
655 
656   return false;
657 }
658 
659 bool ARMDAGToDAGISel::SelectT2AddrModeImm8s4(SDValue Op, SDValue N,
660                                              SDValue &Base, SDValue &OffImm) {
661   if (N.getOpcode() == ISD::ADD) {
662     if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
663       int RHSC = (int)RHS->getZExtValue();
664       if (((RHSC & 0x3) == 0) && (RHSC < 0 && RHSC > -0x400)) { // 8 bits.
665         Base   = N.getOperand(0);
666         OffImm = CurDAG->getTargetConstant(RHSC, MVT::i32);
667         return true;
668       }
669     }
670   } else if (N.getOpcode() == ISD::SUB) {
671     if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
672       int RHSC = (int)RHS->getZExtValue();
673       if (((RHSC & 0x3) == 0) && (RHSC >= 0 && RHSC < 0x400)) { // 8 bits.
674         Base   = N.getOperand(0);
675         OffImm = CurDAG->getTargetConstant(-RHSC, MVT::i32);
676         return true;
677       }
678     }
679   }
680 
681   return false;
682 }
683 
684 bool ARMDAGToDAGISel::SelectT2AddrModeSoReg(SDValue Op, SDValue N,
685                                             SDValue &Base,
686                                             SDValue &OffReg, SDValue &ShImm) {
687   // Base only.
688   if (N.getOpcode() != ISD::ADD && N.getOpcode() != ISD::SUB) {
689     Base = N;
690     if (N.getOpcode() == ISD::FrameIndex) {
691       int FI = cast<FrameIndexSDNode>(N)->getIndex();
692       Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
693     } else if (N.getOpcode() == ARMISD::Wrapper) {
694       Base = N.getOperand(0);
695       if (Base.getOpcode() == ISD::TargetConstantPool)
696         return false;  // We want to select t2LDRpci instead.
697     }
698     OffReg = CurDAG->getRegister(0, MVT::i32);
699     ShImm  = CurDAG->getTargetConstant(0, MVT::i32);
700     return true;
701   }
702 
703   // Look for (R + R) or (R + (R << [1,2,3])).
704   unsigned ShAmt = 0;
705   Base   = N.getOperand(0);
706   OffReg = N.getOperand(1);
707 
708   // Swap if it is ((R << c) + R).
709   ARM_AM::ShiftOpc ShOpcVal = ARM_AM::getShiftOpcForNode(OffReg);
710   if (ShOpcVal != ARM_AM::lsl) {
711     ShOpcVal = ARM_AM::getShiftOpcForNode(Base);
712     if (ShOpcVal == ARM_AM::lsl)
713       std::swap(Base, OffReg);
714   }
715 
716   if (ShOpcVal == ARM_AM::lsl) {
717     // Check to see if the RHS of the shift is a constant, if not, we can't fold
718     // it.
719     if (ConstantSDNode *Sh = dyn_cast<ConstantSDNode>(OffReg.getOperand(1))) {
720       ShAmt = Sh->getZExtValue();
721       if (ShAmt >= 4) {
722         ShAmt = 0;
723         ShOpcVal = ARM_AM::no_shift;
724       } else
725         OffReg = OffReg.getOperand(0);
726     } else {
727       ShOpcVal = ARM_AM::no_shift;
728     }
729   } else if (SelectT2AddrModeImm12(Op, N, Base, ShImm) ||
730              SelectT2AddrModeImm8 (Op, N, Base, ShImm))
731     // Don't match if it's possible to match to one of the r +/- imm cases.
732     return false;
733 
734   ShImm = CurDAG->getTargetConstant(ShAmt, MVT::i32);
735 
736   return true;
737 }
738 
739 //===--------------------------------------------------------------------===//
740 
741 /// getAL - Returns a ARMCC::AL immediate node.
742 static inline SDValue getAL(SelectionDAG *CurDAG) {
743   return CurDAG->getTargetConstant((uint64_t)ARMCC::AL, MVT::i32);
744 }
745 
746 SDNode *ARMDAGToDAGISel::SelectARMIndexedLoad(SDValue Op) {
747   LoadSDNode *LD = cast<LoadSDNode>(Op);
748   ISD::MemIndexedMode AM = LD->getAddressingMode();
749   if (AM == ISD::UNINDEXED)
750     return NULL;
751 
752   MVT LoadedVT = LD->getMemoryVT();
753   SDValue Offset, AMOpc;
754   bool isPre = (AM == ISD::PRE_INC) || (AM == ISD::PRE_DEC);
755   unsigned Opcode = 0;
756   bool Match = false;
757   if (LoadedVT == MVT::i32 &&
758       SelectAddrMode2Offset(Op, LD->getOffset(), Offset, AMOpc)) {
759     Opcode = isPre ? ARM::LDR_PRE : ARM::LDR_POST;
760     Match = true;
761   } else if (LoadedVT == MVT::i16 &&
762              SelectAddrMode3Offset(Op, LD->getOffset(), Offset, AMOpc)) {
763     Match = true;
764     Opcode = (LD->getExtensionType() == ISD::SEXTLOAD)
765       ? (isPre ? ARM::LDRSH_PRE : ARM::LDRSH_POST)
766       : (isPre ? ARM::LDRH_PRE : ARM::LDRH_POST);
767   } else if (LoadedVT == MVT::i8 || LoadedVT == MVT::i1) {
768     if (LD->getExtensionType() == ISD::SEXTLOAD) {
769       if (SelectAddrMode3Offset(Op, LD->getOffset(), Offset, AMOpc)) {
770         Match = true;
771         Opcode = isPre ? ARM::LDRSB_PRE : ARM::LDRSB_POST;
772       }
773     } else {
774       if (SelectAddrMode2Offset(Op, LD->getOffset(), Offset, AMOpc)) {
775         Match = true;
776         Opcode = isPre ? ARM::LDRB_PRE : ARM::LDRB_POST;
777       }
778     }
779   }
780 
781   if (Match) {
782     SDValue Chain = LD->getChain();
783     SDValue Base = LD->getBasePtr();
784     SDValue Ops[]= { Base, Offset, AMOpc, getAL(CurDAG),
785                      CurDAG->getRegister(0, MVT::i32), Chain };
786     return CurDAG->getTargetNode(Opcode, Op.getDebugLoc(), MVT::i32, MVT::i32,
787                                  MVT::Other, Ops, 6);
788   }
789 
790   return NULL;
791 }
792 
793 SDNode *ARMDAGToDAGISel::SelectT2IndexedLoad(SDValue Op) {
794   LoadSDNode *LD = cast<LoadSDNode>(Op);
795   ISD::MemIndexedMode AM = LD->getAddressingMode();
796   if (AM == ISD::UNINDEXED)
797     return NULL;
798 
799   MVT LoadedVT = LD->getMemoryVT();
800   bool isSExtLd = LD->getExtensionType() == ISD::SEXTLOAD;
801   SDValue Offset;
802   bool isPre = (AM == ISD::PRE_INC) || (AM == ISD::PRE_DEC);
803   unsigned Opcode = 0;
804   bool Match = false;
805   if (SelectT2AddrModeImm8Offset(Op, LD->getOffset(), Offset)) {
806     switch (LoadedVT.getSimpleVT()) {
807     case MVT::i32:
808       Opcode = isPre ? ARM::t2LDR_PRE : ARM::t2LDR_POST;
809       break;
810     case MVT::i16:
811       if (isSExtLd)
812         Opcode = isPre ? ARM::t2LDRSH_PRE : ARM::t2LDRSH_POST;
813       else
814         Opcode = isPre ? ARM::t2LDRH_PRE : ARM::t2LDRH_POST;
815       break;
816     case MVT::i8:
817     case MVT::i1:
818       if (isSExtLd)
819         Opcode = isPre ? ARM::t2LDRSB_PRE : ARM::t2LDRSB_POST;
820       else
821         Opcode = isPre ? ARM::t2LDRB_PRE : ARM::t2LDRB_POST;
822       break;
823     default:
824       return NULL;
825     }
826     Match = true;
827   }
828 
829   if (Match) {
830     SDValue Chain = LD->getChain();
831     SDValue Base = LD->getBasePtr();
832     SDValue Ops[]= { Base, Offset, getAL(CurDAG),
833                      CurDAG->getRegister(0, MVT::i32), Chain };
834     return CurDAG->getTargetNode(Opcode, Op.getDebugLoc(), MVT::i32, MVT::i32,
835                                  MVT::Other, Ops, 5);
836   }
837 
838   return NULL;
839 }
840 
841 
842 SDNode *ARMDAGToDAGISel::Select(SDValue Op) {
843   SDNode *N = Op.getNode();
844   DebugLoc dl = N->getDebugLoc();
845 
846   if (N->isMachineOpcode())
847     return NULL;   // Already selected.
848 
849   switch (N->getOpcode()) {
850   default: break;
851   case ISD::Constant: {
852     unsigned Val = cast<ConstantSDNode>(N)->getZExtValue();
853     bool UseCP = true;
854     if (Subtarget->isThumb()) {
855       if (Subtarget->hasThumb2())
856         // Thumb2 has the MOVT instruction, so all immediates can
857         // be done with MOV + MOVT, at worst.
858         UseCP = 0;
859       else
860         UseCP = (Val > 255 &&                          // MOV
861                  ~Val > 255 &&                         // MOV + MVN
862                  !ARM_AM::isThumbImmShiftedVal(Val));  // MOV + LSL
863     } else
864       UseCP = (ARM_AM::getSOImmVal(Val) == -1 &&     // MOV
865                ARM_AM::getSOImmVal(~Val) == -1 &&    // MVN
866                !ARM_AM::isSOImmTwoPartVal(Val));     // two instrs.
867     if (UseCP) {
868       SDValue CPIdx =
869         CurDAG->getTargetConstantPool(ConstantInt::get(Type::Int32Ty, Val),
870                                       TLI.getPointerTy());
871 
872       SDNode *ResNode;
873       if (Subtarget->isThumb1Only())
874         ResNode = CurDAG->getTargetNode(ARM::tLDRcp, dl, MVT::i32, MVT::Other,
875                                         CPIdx, CurDAG->getEntryNode());
876       else {
877         SDValue Ops[] = {
878           CPIdx,
879           CurDAG->getRegister(0, MVT::i32),
880           CurDAG->getTargetConstant(0, MVT::i32),
881           getAL(CurDAG),
882           CurDAG->getRegister(0, MVT::i32),
883           CurDAG->getEntryNode()
884         };
885         ResNode=CurDAG->getTargetNode(ARM::LDRcp, dl, MVT::i32, MVT::Other,
886                                       Ops, 6);
887       }
888       ReplaceUses(Op, SDValue(ResNode, 0));
889       return NULL;
890     }
891 
892     // Other cases are autogenerated.
893     break;
894   }
895   case ISD::FrameIndex: {
896     // Selects to ADDri FI, 0 which in turn will become ADDri SP, imm.
897     int FI = cast<FrameIndexSDNode>(N)->getIndex();
898     SDValue TFI = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
899     if (Subtarget->isThumb1Only()) {
900       return CurDAG->SelectNodeTo(N, ARM::tADDrSPi, MVT::i32, TFI,
901                                   CurDAG->getTargetConstant(0, MVT::i32));
902     } else {
903       SDValue Ops[] = { TFI, CurDAG->getTargetConstant(0, MVT::i32),
904                           getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
905                           CurDAG->getRegister(0, MVT::i32) };
906       return CurDAG->SelectNodeTo(N, (Subtarget->hasThumb2()) ? ARM::t2ADDri : ARM::ADDri,
907                                   MVT::i32, Ops, 5);
908     }
909   }
910   case ISD::ADD: {
911     if (!Subtarget->isThumb1Only())
912       break;
913     // Select add sp, c to tADDhirr.
914     SDValue N0 = Op.getOperand(0);
915     SDValue N1 = Op.getOperand(1);
916     RegisterSDNode *LHSR = dyn_cast<RegisterSDNode>(Op.getOperand(0));
917     RegisterSDNode *RHSR = dyn_cast<RegisterSDNode>(Op.getOperand(1));
918     if (LHSR && LHSR->getReg() == ARM::SP) {
919       std::swap(N0, N1);
920       std::swap(LHSR, RHSR);
921     }
922     if (RHSR && RHSR->getReg() == ARM::SP) {
923       SDValue Val = SDValue(CurDAG->getTargetNode(ARM::tMOVlor2hir, dl,
924                                   Op.getValueType(), N0, N0), 0);
925       return CurDAG->SelectNodeTo(N, ARM::tADDhirr, Op.getValueType(), Val, N1);
926     }
927     break;
928   }
929   case ISD::MUL:
930     if (Subtarget->isThumb1Only())
931       break;
932     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
933       unsigned RHSV = C->getZExtValue();
934       if (!RHSV) break;
935       if (isPowerOf2_32(RHSV-1)) {  // 2^n+1?
936         SDValue V = Op.getOperand(0);
937         unsigned ShImm = ARM_AM::getSORegOpc(ARM_AM::lsl, Log2_32(RHSV-1));
938         SDValue Ops[] = { V, V, CurDAG->getRegister(0, MVT::i32),
939                             CurDAG->getTargetConstant(ShImm, MVT::i32),
940                             getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
941                             CurDAG->getRegister(0, MVT::i32) };
942         return CurDAG->SelectNodeTo(N, (Subtarget->hasThumb2()) ?
943                                     ARM::t2ADDrs : ARM::ADDrs, MVT::i32, Ops, 7);
944       }
945       if (isPowerOf2_32(RHSV+1)) {  // 2^n-1?
946         SDValue V = Op.getOperand(0);
947         unsigned ShImm = ARM_AM::getSORegOpc(ARM_AM::lsl, Log2_32(RHSV+1));
948         SDValue Ops[] = { V, V, CurDAG->getRegister(0, MVT::i32),
949                             CurDAG->getTargetConstant(ShImm, MVT::i32),
950                             getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
951                             CurDAG->getRegister(0, MVT::i32) };
952         return CurDAG->SelectNodeTo(N, (Subtarget->hasThumb2()) ?
953                                     ARM::t2RSBrs : ARM::RSBrs, MVT::i32, Ops, 7);
954       }
955     }
956     break;
957   case ARMISD::FMRRD:
958     return CurDAG->getTargetNode(ARM::FMRRD, dl, MVT::i32, MVT::i32,
959                                  Op.getOperand(0), getAL(CurDAG),
960                                  CurDAG->getRegister(0, MVT::i32));
961   case ISD::UMUL_LOHI: {
962     if (Subtarget->isThumb1Only())
963       break;
964     if (Subtarget->isThumb()) {
965       SDValue Ops[] = { Op.getOperand(0), Op.getOperand(1),
966                         getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
967                         CurDAG->getRegister(0, MVT::i32) };
968       return CurDAG->getTargetNode(ARM::t2UMULL, dl, MVT::i32, MVT::i32, Ops,4);
969     } else {
970       SDValue Ops[] = { Op.getOperand(0), Op.getOperand(1),
971                         getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
972                         CurDAG->getRegister(0, MVT::i32) };
973       return CurDAG->getTargetNode(ARM::UMULL, dl, MVT::i32, MVT::i32, Ops, 5);
974     }
975   }
976   case ISD::SMUL_LOHI: {
977     if (Subtarget->isThumb1Only())
978       break;
979     if (Subtarget->isThumb()) {
980       SDValue Ops[] = { Op.getOperand(0), Op.getOperand(1),
981                         getAL(CurDAG), CurDAG->getRegister(0, MVT::i32) };
982       return CurDAG->getTargetNode(ARM::t2SMULL, dl, MVT::i32, MVT::i32, Ops,4);
983     } else {
984       SDValue Ops[] = { Op.getOperand(0), Op.getOperand(1),
985                         getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
986                         CurDAG->getRegister(0, MVT::i32) };
987       return CurDAG->getTargetNode(ARM::SMULL, dl, MVT::i32, MVT::i32, Ops, 5);
988     }
989   }
990   case ISD::LOAD: {
991     SDNode *ResNode = 0;
992     if (Subtarget->isThumb() && Subtarget->hasThumb2())
993       ResNode = SelectT2IndexedLoad(Op);
994     else
995       ResNode = SelectARMIndexedLoad(Op);
996     if (ResNode)
997       return ResNode;
998     // Other cases are autogenerated.
999     break;
1000   }
1001   case ARMISD::BRCOND: {
1002     // Pattern: (ARMbrcond:void (bb:Other):$dst, (imm:i32):$cc)
1003     // Emits: (Bcc:void (bb:Other):$dst, (imm:i32):$cc)
1004     // Pattern complexity = 6  cost = 1  size = 0
1005 
1006     // Pattern: (ARMbrcond:void (bb:Other):$dst, (imm:i32):$cc)
1007     // Emits: (tBcc:void (bb:Other):$dst, (imm:i32):$cc)
1008     // Pattern complexity = 6  cost = 1  size = 0
1009 
1010     // Pattern: (ARMbrcond:void (bb:Other):$dst, (imm:i32):$cc)
1011     // Emits: (t2Bcc:void (bb:Other):$dst, (imm:i32):$cc)
1012     // Pattern complexity = 6  cost = 1  size = 0
1013 
1014     unsigned Opc = Subtarget->isThumb() ?
1015       ((Subtarget->hasThumb2()) ? ARM::t2Bcc : ARM::tBcc) : ARM::Bcc;
1016     SDValue Chain = Op.getOperand(0);
1017     SDValue N1 = Op.getOperand(1);
1018     SDValue N2 = Op.getOperand(2);
1019     SDValue N3 = Op.getOperand(3);
1020     SDValue InFlag = Op.getOperand(4);
1021     assert(N1.getOpcode() == ISD::BasicBlock);
1022     assert(N2.getOpcode() == ISD::Constant);
1023     assert(N3.getOpcode() == ISD::Register);
1024 
1025     SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
1026                                cast<ConstantSDNode>(N2)->getZExtValue()),
1027                                MVT::i32);
1028     SDValue Ops[] = { N1, Tmp2, N3, Chain, InFlag };
1029     SDNode *ResNode = CurDAG->getTargetNode(Opc, dl, MVT::Other,
1030                                             MVT::Flag, Ops, 5);
1031     Chain = SDValue(ResNode, 0);
1032     if (Op.getNode()->getNumValues() == 2) {
1033       InFlag = SDValue(ResNode, 1);
1034       ReplaceUses(SDValue(Op.getNode(), 1), InFlag);
1035     }
1036     ReplaceUses(SDValue(Op.getNode(), 0), SDValue(Chain.getNode(), Chain.getResNo()));
1037     return NULL;
1038   }
1039   case ARMISD::CMOV: {
1040     MVT VT = Op.getValueType();
1041     SDValue N0 = Op.getOperand(0);
1042     SDValue N1 = Op.getOperand(1);
1043     SDValue N2 = Op.getOperand(2);
1044     SDValue N3 = Op.getOperand(3);
1045     SDValue InFlag = Op.getOperand(4);
1046     assert(N2.getOpcode() == ISD::Constant);
1047     assert(N3.getOpcode() == ISD::Register);
1048 
1049     if (!Subtarget->isThumb1Only() && VT == MVT::i32) {
1050       // Pattern: (ARMcmov:i32 GPR:i32:$false, so_reg:i32:$true, (imm:i32):$cc)
1051       // Emits: (MOVCCs:i32 GPR:i32:$false, so_reg:i32:$true, (imm:i32):$cc)
1052       // Pattern complexity = 18  cost = 1  size = 0
1053       SDValue CPTmp0;
1054       SDValue CPTmp1;
1055       SDValue CPTmp2;
1056       if (Subtarget->isThumb()) {
1057         if (SelectT2ShifterOperandReg(Op, N1, CPTmp0, CPTmp1)) {
1058           SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
1059                                    cast<ConstantSDNode>(N2)->getZExtValue()),
1060                                    MVT::i32);
1061           SDValue Ops[] = { N0, CPTmp0, CPTmp1, Tmp2, N3, InFlag };
1062           return CurDAG->SelectNodeTo(Op.getNode(),
1063                                       ARM::t2MOVCCs, MVT::i32,Ops, 6);
1064         }
1065       } else {
1066         if (SelectShifterOperandReg(Op, N1, CPTmp0, CPTmp1, CPTmp2)) {
1067           SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
1068                                    cast<ConstantSDNode>(N2)->getZExtValue()),
1069                                    MVT::i32);
1070           SDValue Ops[] = { N0, CPTmp0, CPTmp1, CPTmp2, Tmp2, N3, InFlag };
1071           return CurDAG->SelectNodeTo(Op.getNode(),
1072                                       ARM::MOVCCs, MVT::i32, Ops, 7);
1073         }
1074       }
1075 
1076       // Pattern: (ARMcmov:i32 GPR:i32:$false,
1077       //             (imm:i32)<<P:Predicate_so_imm>>:$true,
1078       //             (imm:i32):$cc)
1079       // Emits: (MOVCCi:i32 GPR:i32:$false,
1080       //           (so_imm:i32 (imm:i32):$true), (imm:i32):$cc)
1081       // Pattern complexity = 10  cost = 1  size = 0
1082       if (N3.getOpcode() == ISD::Constant) {
1083         if (Subtarget->isThumb()) {
1084           if (Predicate_t2_so_imm(N3.getNode())) {
1085             SDValue Tmp1 = CurDAG->getTargetConstant(((unsigned)
1086                                      cast<ConstantSDNode>(N1)->getZExtValue()),
1087                                      MVT::i32);
1088             SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
1089                                      cast<ConstantSDNode>(N2)->getZExtValue()),
1090                                      MVT::i32);
1091             SDValue Ops[] = { N0, Tmp1, Tmp2, N3, InFlag };
1092             return CurDAG->SelectNodeTo(Op.getNode(),
1093                                         ARM::t2MOVCCi, MVT::i32, Ops, 5);
1094           }
1095         } else {
1096           if (Predicate_so_imm(N3.getNode())) {
1097             SDValue Tmp1 = CurDAG->getTargetConstant(((unsigned)
1098                                      cast<ConstantSDNode>(N1)->getZExtValue()),
1099                                      MVT::i32);
1100             SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
1101                                      cast<ConstantSDNode>(N2)->getZExtValue()),
1102                                      MVT::i32);
1103             SDValue Ops[] = { N0, Tmp1, Tmp2, N3, InFlag };
1104             return CurDAG->SelectNodeTo(Op.getNode(),
1105                                         ARM::MOVCCi, MVT::i32, Ops, 5);
1106           }
1107         }
1108       }
1109     }
1110 
1111     // Pattern: (ARMcmov:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
1112     // Emits: (MOVCCr:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
1113     // Pattern complexity = 6  cost = 1  size = 0
1114     //
1115     // Pattern: (ARMcmov:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
1116     // Emits: (tMOVCCr:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
1117     // Pattern complexity = 6  cost = 11  size = 0
1118     //
1119     // Also FCPYScc and FCPYDcc.
1120     SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
1121                                cast<ConstantSDNode>(N2)->getZExtValue()),
1122                                MVT::i32);
1123     SDValue Ops[] = { N0, N1, Tmp2, N3, InFlag };
1124     unsigned Opc = 0;
1125     switch (VT.getSimpleVT()) {
1126     default: assert(false && "Illegal conditional move type!");
1127       break;
1128     case MVT::i32:
1129       Opc = Subtarget->isThumb()
1130         ? (Subtarget->hasThumb2() ? ARM::t2MOVCCr : ARM::tMOVCCr)
1131         : ARM::MOVCCr;
1132       break;
1133     case MVT::f32:
1134       Opc = ARM::FCPYScc;
1135       break;
1136     case MVT::f64:
1137       Opc = ARM::FCPYDcc;
1138       break;
1139     }
1140     return CurDAG->SelectNodeTo(Op.getNode(), Opc, VT, Ops, 5);
1141   }
1142   case ARMISD::CNEG: {
1143     MVT VT = Op.getValueType();
1144     SDValue N0 = Op.getOperand(0);
1145     SDValue N1 = Op.getOperand(1);
1146     SDValue N2 = Op.getOperand(2);
1147     SDValue N3 = Op.getOperand(3);
1148     SDValue InFlag = Op.getOperand(4);
1149     assert(N2.getOpcode() == ISD::Constant);
1150     assert(N3.getOpcode() == ISD::Register);
1151 
1152     SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
1153                                cast<ConstantSDNode>(N2)->getZExtValue()),
1154                                MVT::i32);
1155     SDValue Ops[] = { N0, N1, Tmp2, N3, InFlag };
1156     unsigned Opc = 0;
1157     switch (VT.getSimpleVT()) {
1158     default: assert(false && "Illegal conditional move type!");
1159       break;
1160     case MVT::f32:
1161       Opc = ARM::FNEGScc;
1162       break;
1163     case MVT::f64:
1164       Opc = ARM::FNEGDcc;
1165       break;
1166     }
1167     return CurDAG->SelectNodeTo(Op.getNode(), Opc, VT, Ops, 5);
1168   }
1169 
1170   case ISD::DECLARE: {
1171     SDValue Chain = Op.getOperand(0);
1172     SDValue N1 = Op.getOperand(1);
1173     SDValue N2 = Op.getOperand(2);
1174     FrameIndexSDNode *FINode = dyn_cast<FrameIndexSDNode>(N1);
1175     // FIXME: handle VLAs.
1176     if (!FINode) {
1177       ReplaceUses(Op.getValue(0), Chain);
1178       return NULL;
1179     }
1180     if (N2.getOpcode() == ARMISD::PIC_ADD && isa<LoadSDNode>(N2.getOperand(0)))
1181       N2 = N2.getOperand(0);
1182     LoadSDNode *Ld = dyn_cast<LoadSDNode>(N2);
1183     if (!Ld) {
1184       ReplaceUses(Op.getValue(0), Chain);
1185       return NULL;
1186     }
1187     SDValue BasePtr = Ld->getBasePtr();
1188     assert(BasePtr.getOpcode() == ARMISD::Wrapper &&
1189            isa<ConstantPoolSDNode>(BasePtr.getOperand(0)) &&
1190            "llvm.dbg.variable should be a constantpool node");
1191     ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(BasePtr.getOperand(0));
1192     GlobalValue *GV = 0;
1193     if (CP->isMachineConstantPoolEntry()) {
1194       ARMConstantPoolValue *ACPV = (ARMConstantPoolValue*)CP->getMachineCPVal();
1195       GV = ACPV->getGV();
1196     } else
1197       GV = dyn_cast<GlobalValue>(CP->getConstVal());
1198     if (!GV) {
1199       ReplaceUses(Op.getValue(0), Chain);
1200       return NULL;
1201     }
1202 
1203     SDValue Tmp1 = CurDAG->getTargetFrameIndex(FINode->getIndex(),
1204                                                TLI.getPointerTy());
1205     SDValue Tmp2 = CurDAG->getTargetGlobalAddress(GV, TLI.getPointerTy());
1206     SDValue Ops[] = { Tmp1, Tmp2, Chain };
1207     return CurDAG->getTargetNode(TargetInstrInfo::DECLARE, dl,
1208                                  MVT::Other, Ops, 3);
1209   }
1210 
1211   case ISD::CONCAT_VECTORS: {
1212     MVT VT = Op.getValueType();
1213     assert(VT.is128BitVector() && Op.getNumOperands() == 2 &&
1214            "unexpected CONCAT_VECTORS");
1215     SDValue N0 = Op.getOperand(0);
1216     SDValue N1 = Op.getOperand(1);
1217     SDNode *Result =
1218       CurDAG->getTargetNode(TargetInstrInfo::IMPLICIT_DEF, dl, VT);
1219     if (N0.getOpcode() != ISD::UNDEF)
1220       Result = CurDAG->getTargetNode(TargetInstrInfo::INSERT_SUBREG, dl, VT,
1221                                      SDValue(Result, 0), N0,
1222                                      CurDAG->getTargetConstant(arm_dsubreg_0,
1223                                                                MVT::i32));
1224     if (N1.getOpcode() != ISD::UNDEF)
1225       Result = CurDAG->getTargetNode(TargetInstrInfo::INSERT_SUBREG, dl, VT,
1226                                      SDValue(Result, 0), N1,
1227                                      CurDAG->getTargetConstant(arm_dsubreg_1,
1228                                                                MVT::i32));
1229     return Result;
1230   }
1231 
1232   case ISD::VECTOR_SHUFFLE: {
1233     MVT VT = Op.getValueType();
1234 
1235     // Match 128-bit splat to VDUPLANEQ.  (This could be done with a Pat in
1236     // ARMInstrNEON.td but it is awkward because the shuffle mask needs to be
1237     // transformed first into a lane number and then to both a subregister
1238     // index and an adjusted lane number.)  If the source operand is a
1239     // SCALAR_TO_VECTOR, leave it so it will be matched later as a VDUP.
1240     ShuffleVectorSDNode *SVOp = cast<ShuffleVectorSDNode>(N);
1241     if (VT.is128BitVector() && SVOp->isSplat() &&
1242         Op.getOperand(0).getOpcode() != ISD::SCALAR_TO_VECTOR &&
1243         Op.getOperand(1).getOpcode() == ISD::UNDEF) {
1244       unsigned LaneVal = SVOp->getSplatIndex();
1245 
1246       MVT HalfVT;
1247       unsigned Opc = 0;
1248       switch (VT.getVectorElementType().getSimpleVT()) {
1249       default: assert(false && "unhandled VDUP splat type");
1250       case MVT::i8:  Opc = ARM::VDUPLN8q;  HalfVT = MVT::v8i8; break;
1251       case MVT::i16: Opc = ARM::VDUPLN16q; HalfVT = MVT::v4i16; break;
1252       case MVT::i32: Opc = ARM::VDUPLN32q; HalfVT = MVT::v2i32; break;
1253       case MVT::f32: Opc = ARM::VDUPLNfq;  HalfVT = MVT::v2f32; break;
1254       }
1255 
1256       // The source operand needs to be changed to a subreg of the original
1257       // 128-bit operand, and the lane number needs to be adjusted accordingly.
1258       unsigned NumElts = VT.getVectorNumElements() / 2;
1259       unsigned SRVal = (LaneVal < NumElts ? arm_dsubreg_0 : arm_dsubreg_1);
1260       SDValue SR = CurDAG->getTargetConstant(SRVal, MVT::i32);
1261       SDValue NewLane = CurDAG->getTargetConstant(LaneVal % NumElts, MVT::i32);
1262       SDNode *SubReg = CurDAG->getTargetNode(TargetInstrInfo::EXTRACT_SUBREG,
1263                                              dl, HalfVT, N->getOperand(0), SR);
1264       return CurDAG->SelectNodeTo(N, Opc, VT, SDValue(SubReg, 0), NewLane);
1265     }
1266 
1267     break;
1268   }
1269   }
1270 
1271   return SelectCode(Op);
1272 }
1273 
1274 bool ARMDAGToDAGISel::
1275 SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode,
1276                              std::vector<SDValue> &OutOps) {
1277   assert(ConstraintCode == 'm' && "unexpected asm memory constraint");
1278 
1279   SDValue Base, Offset, Opc;
1280   if (!SelectAddrMode2(Op, Op, Base, Offset, Opc))
1281     return true;
1282 
1283   OutOps.push_back(Base);
1284   OutOps.push_back(Offset);
1285   OutOps.push_back(Opc);
1286   return false;
1287 }
1288 
1289 /// createARMISelDag - This pass converts a legalized DAG into a
1290 /// ARM-specific DAG, ready for instruction scheduling.
1291 ///
1292 FunctionPass *llvm::createARMISelDag(ARMBaseTargetMachine &TM) {
1293   return new ARMDAGToDAGISel(TM);
1294 }
1295