ARMISelDAGToDAG.cpp revision e64e3cf9adb18c9c6711e69e975d098a513ee8f8 
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
35//===--------------------------------------------------------------------===//
36/// ARMDAGToDAGISel - ARM specific code to select ARM machine
37/// instructions for SelectionDAG operations.
38///
39namespace {
40class ARMDAGToDAGISel : public SelectionDAGISel {
41  ARMTargetMachine &TM;
42
43  /// Subtarget - Keep a pointer to the ARMSubtarget around so that we can
44  /// make the right decision when generating code for different targets.
45  const ARMSubtarget *Subtarget;
46
47public:
48  explicit ARMDAGToDAGISel(ARMTargetMachine &tm)
49    : SelectionDAGISel(tm), TM(tm),
50    Subtarget(&TM.getSubtarget<ARMSubtarget>()) {
51  }
52
53  virtual const char *getPassName() const {
54    return "ARM Instruction Selection";
55  }
56
57 /// getI32Imm - Return a target constant with the specified value, of type i32.
58  inline SDValue getI32Imm(unsigned Imm) {
59    return CurDAG->getTargetConstant(Imm, MVT::i32);
60  }
61
62  SDNode *Select(SDValue Op);
63  virtual void InstructionSelect();
64  bool SelectAddrMode2(SDValue Op, SDValue N, SDValue &Base,
65                       SDValue &Offset, SDValue &Opc);
66  bool SelectAddrMode2Offset(SDValue Op, SDValue N,
67                             SDValue &Offset, SDValue &Opc);
68  bool SelectAddrMode3(SDValue Op, SDValue N, SDValue &Base,
69                       SDValue &Offset, SDValue &Opc);
70  bool SelectAddrMode3Offset(SDValue Op, SDValue N,
71                             SDValue &Offset, SDValue &Opc);
72  bool SelectAddrMode5(SDValue Op, SDValue N, SDValue &Base,
73                       SDValue &Offset);
74
75  bool SelectAddrModePC(SDValue Op, SDValue N, SDValue &Offset,
76                         SDValue &Label);
77
78  bool SelectThumbAddrModeRR(SDValue Op, SDValue N, SDValue &Base,
79                             SDValue &Offset);
80  bool SelectThumbAddrModeRI5(SDValue Op, SDValue N, unsigned Scale,
81                              SDValue &Base, SDValue &OffImm,
82                              SDValue &Offset);
83  bool SelectThumbAddrModeS1(SDValue Op, SDValue N, SDValue &Base,
84                             SDValue &OffImm, SDValue &Offset);
85  bool SelectThumbAddrModeS2(SDValue Op, SDValue N, SDValue &Base,
86                             SDValue &OffImm, SDValue &Offset);
87  bool SelectThumbAddrModeS4(SDValue Op, SDValue N, SDValue &Base,
88                             SDValue &OffImm, SDValue &Offset);
89  bool SelectThumbAddrModeSP(SDValue Op, SDValue N, SDValue &Base,
90                             SDValue &OffImm);
91
92  bool SelectShifterOperand(SDValue Op, SDValue N,
93                            SDValue &BaseReg, SDValue &Opc);
94
95  bool SelectShifterOperandReg(SDValue Op, SDValue N, SDValue &A,
96                               SDValue &B, SDValue &C);
97
98  // Include the pieces autogenerated from the target description.
99#include "ARMGenDAGISel.inc"
100
101private:
102    /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
103    /// inline asm expressions.
104    virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op,
105                                              char ConstraintCode,
106                                              std::vector<SDValue> &OutOps);
107};
108}
109
110void ARMDAGToDAGISel::InstructionSelect() {
111  DEBUG(BB->dump());
112
113  SelectRoot(*CurDAG);
114  CurDAG->RemoveDeadNodes();
115}
116
117bool ARMDAGToDAGISel::SelectAddrMode2(SDValue Op, SDValue N,
118                                      SDValue &Base, SDValue &Offset,
119                                      SDValue &Opc) {
120  if (N.getOpcode() == ISD::MUL) {
121    if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
122      // X * [3,5,9] -> X + X * [2,4,8] etc.
123      int RHSC = (int)RHS->getZExtValue();
124      if (RHSC & 1) {
125        RHSC = RHSC & ~1;
126        ARM_AM::AddrOpc AddSub = ARM_AM::add;
127        if (RHSC < 0) {
128          AddSub = ARM_AM::sub;
129          RHSC = - RHSC;
130        }
131        if (isPowerOf2_32(RHSC)) {
132          unsigned ShAmt = Log2_32(RHSC);
133          Base = Offset = N.getOperand(0);
134          Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, ShAmt,
135                                                            ARM_AM::lsl),
136                                          MVT::i32);
137          return true;
138        }
139      }
140    }
141  }
142
143  if (N.getOpcode() != ISD::ADD && N.getOpcode() != ISD::SUB) {
144    Base = N;
145    if (N.getOpcode() == ISD::FrameIndex) {
146      int FI = cast<FrameIndexSDNode>(N)->getIndex();
147      Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
148    } else if (N.getOpcode() == ARMISD::Wrapper) {
149      Base = N.getOperand(0);
150    }
151    Offset = CurDAG->getRegister(0, MVT::i32);
152    Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(ARM_AM::add, 0,
153                                                      ARM_AM::no_shift),
154                                    MVT::i32);
155    return true;
156  }
157
158  // Match simple R +/- imm12 operands.
159  if (N.getOpcode() == ISD::ADD)
160    if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
161      int RHSC = (int)RHS->getZExtValue();
162      if ((RHSC >= 0 && RHSC < 0x1000) ||
163          (RHSC < 0 && RHSC > -0x1000)) { // 12 bits.
164        Base = N.getOperand(0);
165        if (Base.getOpcode() == ISD::FrameIndex) {
166          int FI = cast<FrameIndexSDNode>(Base)->getIndex();
167          Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
168        }
169        Offset = CurDAG->getRegister(0, MVT::i32);
170
171        ARM_AM::AddrOpc AddSub = ARM_AM::add;
172        if (RHSC < 0) {
173          AddSub = ARM_AM::sub;
174          RHSC = - RHSC;
175        }
176        Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, RHSC,
177                                                          ARM_AM::no_shift),
178                                        MVT::i32);
179        return true;
180      }
181    }
182
183  // Otherwise this is R +/- [possibly shifted] R
184  ARM_AM::AddrOpc AddSub = N.getOpcode() == ISD::ADD ? ARM_AM::add:ARM_AM::sub;
185  ARM_AM::ShiftOpc ShOpcVal = ARM_AM::getShiftOpcForNode(N.getOperand(1));
186  unsigned ShAmt = 0;
187
188  Base   = N.getOperand(0);
189  Offset = N.getOperand(1);
190
191  if (ShOpcVal != ARM_AM::no_shift) {
192    // Check to see if the RHS of the shift is a constant, if not, we can't fold
193    // it.
194    if (ConstantSDNode *Sh =
195           dyn_cast<ConstantSDNode>(N.getOperand(1).getOperand(1))) {
196      ShAmt = Sh->getZExtValue();
197      Offset = N.getOperand(1).getOperand(0);
198    } else {
199      ShOpcVal = ARM_AM::no_shift;
200    }
201  }
202
203  // Try matching (R shl C) + (R).
204  if (N.getOpcode() == ISD::ADD && ShOpcVal == ARM_AM::no_shift) {
205    ShOpcVal = ARM_AM::getShiftOpcForNode(N.getOperand(0));
206    if (ShOpcVal != ARM_AM::no_shift) {
207      // Check to see if the RHS of the shift is a constant, if not, we can't
208      // fold it.
209      if (ConstantSDNode *Sh =
210          dyn_cast<ConstantSDNode>(N.getOperand(0).getOperand(1))) {
211        ShAmt = Sh->getZExtValue();
212        Offset = N.getOperand(0).getOperand(0);
213        Base = N.getOperand(1);
214      } else {
215        ShOpcVal = ARM_AM::no_shift;
216      }
217    }
218  }
219
220  Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, ShAmt, ShOpcVal),
221                                  MVT::i32);
222  return true;
223}
224
225bool ARMDAGToDAGISel::SelectAddrMode2Offset(SDValue Op, SDValue N,
226                                            SDValue &Offset, SDValue &Opc) {
227  unsigned Opcode = Op.getOpcode();
228  ISD::MemIndexedMode AM = (Opcode == ISD::LOAD)
229    ? cast<LoadSDNode>(Op)->getAddressingMode()
230    : cast<StoreSDNode>(Op)->getAddressingMode();
231  ARM_AM::AddrOpc AddSub = (AM == ISD::PRE_INC || AM == ISD::POST_INC)
232    ? ARM_AM::add : ARM_AM::sub;
233  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N)) {
234    int Val = (int)C->getZExtValue();
235    if (Val >= 0 && Val < 0x1000) { // 12 bits.
236      Offset = CurDAG->getRegister(0, MVT::i32);
237      Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, Val,
238                                                        ARM_AM::no_shift),
239                                      MVT::i32);
240      return true;
241    }
242  }
243
244  Offset = N;
245  ARM_AM::ShiftOpc ShOpcVal = ARM_AM::getShiftOpcForNode(N);
246  unsigned ShAmt = 0;
247  if (ShOpcVal != ARM_AM::no_shift) {
248    // Check to see if the RHS of the shift is a constant, if not, we can't fold
249    // it.
250    if (ConstantSDNode *Sh = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
251      ShAmt = Sh->getZExtValue();
252      Offset = N.getOperand(0);
253    } else {
254      ShOpcVal = ARM_AM::no_shift;
255    }
256  }
257
258  Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, ShAmt, ShOpcVal),
259                                  MVT::i32);
260  return true;
261}
262
263
264bool ARMDAGToDAGISel::SelectAddrMode3(SDValue Op, SDValue N,
265                                      SDValue &Base, SDValue &Offset,
266                                      SDValue &Opc) {
267  if (N.getOpcode() == ISD::SUB) {
268    // X - C  is canonicalize to X + -C, no need to handle it here.
269    Base = N.getOperand(0);
270    Offset = N.getOperand(1);
271    Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(ARM_AM::sub, 0),MVT::i32);
272    return true;
273  }
274
275  if (N.getOpcode() != ISD::ADD) {
276    Base = N;
277    if (N.getOpcode() == ISD::FrameIndex) {
278      int FI = cast<FrameIndexSDNode>(N)->getIndex();
279      Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
280    }
281    Offset = CurDAG->getRegister(0, MVT::i32);
282    Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(ARM_AM::add, 0),MVT::i32);
283    return true;
284  }
285
286  // If the RHS is +/- imm8, fold into addr mode.
287  if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
288    int RHSC = (int)RHS->getZExtValue();
289    if ((RHSC >= 0 && RHSC < 256) ||
290        (RHSC < 0 && RHSC > -256)) { // note -256 itself isn't allowed.
291      Base = N.getOperand(0);
292      if (Base.getOpcode() == ISD::FrameIndex) {
293        int FI = cast<FrameIndexSDNode>(Base)->getIndex();
294        Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
295      }
296      Offset = CurDAG->getRegister(0, MVT::i32);
297
298      ARM_AM::AddrOpc AddSub = ARM_AM::add;
299      if (RHSC < 0) {
300        AddSub = ARM_AM::sub;
301        RHSC = - RHSC;
302      }
303      Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(AddSub, RHSC),MVT::i32);
304      return true;
305    }
306  }
307
308  Base = N.getOperand(0);
309  Offset = N.getOperand(1);
310  Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(ARM_AM::add, 0), MVT::i32);
311  return true;
312}
313
314bool ARMDAGToDAGISel::SelectAddrMode3Offset(SDValue Op, SDValue N,
315                                            SDValue &Offset, SDValue &Opc) {
316  unsigned Opcode = Op.getOpcode();
317  ISD::MemIndexedMode AM = (Opcode == ISD::LOAD)
318    ? cast<LoadSDNode>(Op)->getAddressingMode()
319    : cast<StoreSDNode>(Op)->getAddressingMode();
320  ARM_AM::AddrOpc AddSub = (AM == ISD::PRE_INC || AM == ISD::POST_INC)
321    ? ARM_AM::add : ARM_AM::sub;
322  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N)) {
323    int Val = (int)C->getZExtValue();
324    if (Val >= 0 && Val < 256) {
325      Offset = CurDAG->getRegister(0, MVT::i32);
326      Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(AddSub, Val), MVT::i32);
327      return true;
328    }
329  }
330
331  Offset = N;
332  Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(AddSub, 0), MVT::i32);
333  return true;
334}
335
336
337bool ARMDAGToDAGISel::SelectAddrMode5(SDValue Op, SDValue N,
338                                      SDValue &Base, SDValue &Offset) {
339  if (N.getOpcode() != ISD::ADD) {
340    Base = N;
341    if (N.getOpcode() == ISD::FrameIndex) {
342      int FI = cast<FrameIndexSDNode>(N)->getIndex();
343      Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
344    } else if (N.getOpcode() == ARMISD::Wrapper) {
345      Base = N.getOperand(0);
346    }
347    Offset = CurDAG->getTargetConstant(ARM_AM::getAM5Opc(ARM_AM::add, 0),
348                                       MVT::i32);
349    return true;
350  }
351
352  // If the RHS is +/- imm8, fold into addr mode.
353  if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
354    int RHSC = (int)RHS->getZExtValue();
355    if ((RHSC & 3) == 0) {  // The constant is implicitly multiplied by 4.
356      RHSC >>= 2;
357      if ((RHSC >= 0 && RHSC < 256) ||
358          (RHSC < 0 && RHSC > -256)) { // note -256 itself isn't allowed.
359        Base = N.getOperand(0);
360        if (Base.getOpcode() == ISD::FrameIndex) {
361          int FI = cast<FrameIndexSDNode>(Base)->getIndex();
362          Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
363        }
364
365        ARM_AM::AddrOpc AddSub = ARM_AM::add;
366        if (RHSC < 0) {
367          AddSub = ARM_AM::sub;
368          RHSC = - RHSC;
369        }
370        Offset = CurDAG->getTargetConstant(ARM_AM::getAM5Opc(AddSub, RHSC),
371                                           MVT::i32);
372        return true;
373      }
374    }
375  }
376
377  Base = N;
378  Offset = CurDAG->getTargetConstant(ARM_AM::getAM5Opc(ARM_AM::add, 0),
379                                     MVT::i32);
380  return true;
381}
382
383bool ARMDAGToDAGISel::SelectAddrModePC(SDValue Op, SDValue N,
384                                        SDValue &Offset, SDValue &Label) {
385  if (N.getOpcode() == ARMISD::PIC_ADD && N.hasOneUse()) {
386    Offset = N.getOperand(0);
387    SDValue N1 = N.getOperand(1);
388    Label  = CurDAG->getTargetConstant(cast<ConstantSDNode>(N1)->getZExtValue(),
389                                       MVT::i32);
390    return true;
391  }
392  return false;
393}
394
395bool ARMDAGToDAGISel::SelectThumbAddrModeRR(SDValue Op, SDValue N,
396                                            SDValue &Base, SDValue &Offset){
397  // FIXME dl should come from the parent load or store, not the address
398  DebugLoc dl = Op.getDebugLoc();
399  if (N.getOpcode() != ISD::ADD) {
400    Base = N;
401    // We must materialize a zero in a reg! Returning a constant here
402    // wouldn't work without additional code to position the node within
403    // ISel's topological ordering in a place where ISel will process it
404    // normally.  Instead, just explicitly issue a tMOVri8 node!
405    Offset = SDValue(CurDAG->getTargetNode(ARM::tMOVi8, dl, MVT::i32,
406                                    CurDAG->getTargetConstant(0, MVT::i32)), 0);
407    return true;
408  }
409
410  Base = N.getOperand(0);
411  Offset = N.getOperand(1);
412  return true;
413}
414
415bool
416ARMDAGToDAGISel::SelectThumbAddrModeRI5(SDValue Op, SDValue N,
417                                        unsigned Scale, SDValue &Base,
418                                        SDValue &OffImm, SDValue &Offset) {
419  if (Scale == 4) {
420    SDValue TmpBase, TmpOffImm;
421    if (SelectThumbAddrModeSP(Op, N, TmpBase, TmpOffImm))
422      return false;  // We want to select tLDRspi / tSTRspi instead.
423    if (N.getOpcode() == ARMISD::Wrapper &&
424        N.getOperand(0).getOpcode() == ISD::TargetConstantPool)
425      return false;  // We want to select tLDRpci instead.
426  }
427
428  if (N.getOpcode() != ISD::ADD) {
429    Base = (N.getOpcode() == ARMISD::Wrapper) ? N.getOperand(0) : N;
430    Offset = CurDAG->getRegister(0, MVT::i32);
431    OffImm = CurDAG->getTargetConstant(0, MVT::i32);
432    return true;
433  }
434
435  // Thumb does not have [sp, r] address mode.
436  RegisterSDNode *LHSR = dyn_cast<RegisterSDNode>(N.getOperand(0));
437  RegisterSDNode *RHSR = dyn_cast<RegisterSDNode>(N.getOperand(1));
438  if ((LHSR && LHSR->getReg() == ARM::SP) ||
439      (RHSR && RHSR->getReg() == ARM::SP)) {
440    Base = N;
441    Offset = CurDAG->getRegister(0, MVT::i32);
442    OffImm = CurDAG->getTargetConstant(0, MVT::i32);
443    return true;
444  }
445
446  // If the RHS is + imm5 * scale, fold into addr mode.
447  if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
448    int RHSC = (int)RHS->getZExtValue();
449    if ((RHSC & (Scale-1)) == 0) {  // The constant is implicitly multiplied.
450      RHSC /= Scale;
451      if (RHSC >= 0 && RHSC < 32) {
452        Base = N.getOperand(0);
453        Offset = CurDAG->getRegister(0, MVT::i32);
454        OffImm = CurDAG->getTargetConstant(RHSC, MVT::i32);
455        return true;
456      }
457    }
458  }
459
460  Base = N.getOperand(0);
461  Offset = N.getOperand(1);
462  OffImm = CurDAG->getTargetConstant(0, MVT::i32);
463  return true;
464}
465
466bool ARMDAGToDAGISel::SelectThumbAddrModeS1(SDValue Op, SDValue N,
467                                            SDValue &Base, SDValue &OffImm,
468                                            SDValue &Offset) {
469  return SelectThumbAddrModeRI5(Op, N, 1, Base, OffImm, Offset);
470}
471
472bool ARMDAGToDAGISel::SelectThumbAddrModeS2(SDValue Op, SDValue N,
473                                            SDValue &Base, SDValue &OffImm,
474                                            SDValue &Offset) {
475  return SelectThumbAddrModeRI5(Op, N, 2, Base, OffImm, Offset);
476}
477
478bool ARMDAGToDAGISel::SelectThumbAddrModeS4(SDValue Op, SDValue N,
479                                            SDValue &Base, SDValue &OffImm,
480                                            SDValue &Offset) {
481  return SelectThumbAddrModeRI5(Op, N, 4, Base, OffImm, Offset);
482}
483
484bool ARMDAGToDAGISel::SelectThumbAddrModeSP(SDValue Op, SDValue N,
485                                           SDValue &Base, SDValue &OffImm) {
486  if (N.getOpcode() == ISD::FrameIndex) {
487    int FI = cast<FrameIndexSDNode>(N)->getIndex();
488    Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
489    OffImm = CurDAG->getTargetConstant(0, MVT::i32);
490    return true;
491  }
492
493  if (N.getOpcode() != ISD::ADD)
494    return false;
495
496  RegisterSDNode *LHSR = dyn_cast<RegisterSDNode>(N.getOperand(0));
497  if (N.getOperand(0).getOpcode() == ISD::FrameIndex ||
498      (LHSR && LHSR->getReg() == ARM::SP)) {
499    // If the RHS is + imm8 * scale, fold into addr mode.
500    if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
501      int RHSC = (int)RHS->getZExtValue();
502      if ((RHSC & 3) == 0) {  // The constant is implicitly multiplied.
503        RHSC >>= 2;
504        if (RHSC >= 0 && RHSC < 256) {
505          Base = N.getOperand(0);
506          if (Base.getOpcode() == ISD::FrameIndex) {
507            int FI = cast<FrameIndexSDNode>(Base)->getIndex();
508            Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
509          }
510          OffImm = CurDAG->getTargetConstant(RHSC, MVT::i32);
511          return true;
512        }
513      }
514    }
515  }
516
517  return false;
518}
519
520bool ARMDAGToDAGISel::SelectShifterOperand(SDValue Op,
521                                           SDValue N,
522                                           SDValue &BaseReg,
523                                           SDValue &Opc) {
524  ARM_AM::ShiftOpc ShOpcVal = ARM_AM::getShiftOpcForNode(N);
525
526  // Don't match base register only case. That is matched to a separate
527  // lower complexity pattern with explicit register operand.
528  if (ShOpcVal == ARM_AM::no_shift) return false;
529
530  BaseReg = N.getOperand(0);
531  unsigned ShImmVal = 0;
532  if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1)))
533    ShImmVal = RHS->getZExtValue() & 31;
534  else
535    return false;
536
537  Opc = getI32Imm(ARM_AM::getSORegOpc(ShOpcVal, ShImmVal));
538
539  return true;
540}
541
542bool ARMDAGToDAGISel::SelectShifterOperandReg(SDValue Op,
543                                              SDValue N,
544                                              SDValue &BaseReg,
545                                              SDValue &ShReg,
546                                              SDValue &Opc) {
547  ARM_AM::ShiftOpc ShOpcVal = ARM_AM::getShiftOpcForNode(N);
548
549  // Don't match base register only case. That is matched to a separate
550  // lower complexity pattern with explicit register operand.
551  if (ShOpcVal == ARM_AM::no_shift) return false;
552
553  BaseReg = N.getOperand(0);
554  unsigned ShImmVal = 0;
555  if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
556    ShReg = CurDAG->getRegister(0, MVT::i32);
557    ShImmVal = RHS->getZExtValue() & 31;
558  } else {
559    ShReg = N.getOperand(1);
560  }
561  Opc = CurDAG->getTargetConstant(ARM_AM::getSORegOpc(ShOpcVal, ShImmVal),
562                                  MVT::i32);
563  return true;
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
923  return SelectCode(Op);
924}
925
926bool ARMDAGToDAGISel::
927SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode,
928                             std::vector<SDValue> &OutOps) {
929  assert(ConstraintCode == 'm' && "unexpected asm memory constraint");
930
931  SDValue Base, Offset, Opc;
932  if (!SelectAddrMode2(Op, Op, Base, Offset, Opc))
933    return true;
934
935  OutOps.push_back(Base);
936  OutOps.push_back(Offset);
937  OutOps.push_back(Opc);
938  return false;
939}
940
941/// createARMISelDag - This pass converts a legalized DAG into a
942/// ARM-specific DAG, ready for instruction scheduling.
943///
944FunctionPass *llvm::createARMISelDag(ARMTargetMachine &TM) {
945  return new ARMDAGToDAGISel(TM);
946}
947