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