ARMISelDAGToDAG.cpp revision 194612 
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    // ARMv6T2 and later should materialize imms via MOV / MOVT pair.
583    if (Subtarget->hasV6T2Ops() || Subtarget->hasThumb2())
584      break;
585
586    unsigned Val = cast<ConstantSDNode>(N)->getZExtValue();
587    bool UseCP = true;
588    if (Subtarget->isThumb())
589      UseCP = (Val > 255 &&                          // MOV
590               ~Val > 255 &&                         // MOV + MVN
591               !ARM_AM::isThumbImmShiftedVal(Val));  // MOV + LSL
592    else
593      UseCP = (ARM_AM::getSOImmVal(Val) == -1 &&     // MOV
594               ARM_AM::getSOImmVal(~Val) == -1 &&    // MVN
595               !ARM_AM::isSOImmTwoPartVal(Val));     // two instrs.
596    if (UseCP) {
597      SDValue CPIdx =
598        CurDAG->getTargetConstantPool(ConstantInt::get(Type::Int32Ty, Val),
599                                      TLI.getPointerTy());
600
601      SDNode *ResNode;
602      if (Subtarget->isThumb())
603        ResNode = CurDAG->getTargetNode(ARM::tLDRcp, dl, MVT::i32, MVT::Other,
604                                        CPIdx, CurDAG->getEntryNode());
605      else {
606        SDValue Ops[] = {
607          CPIdx,
608          CurDAG->getRegister(0, MVT::i32),
609          CurDAG->getTargetConstant(0, MVT::i32),
610          getAL(CurDAG),
611          CurDAG->getRegister(0, MVT::i32),
612          CurDAG->getEntryNode()
613        };
614        ResNode=CurDAG->getTargetNode(ARM::LDRcp, dl, MVT::i32, MVT::Other,
615                                      Ops, 6);
616      }
617      ReplaceUses(Op, SDValue(ResNode, 0));
618      return NULL;
619    }
620
621    // Other cases are autogenerated.
622    break;
623  }
624  case ISD::FrameIndex: {
625    // Selects to ADDri FI, 0 which in turn will become ADDri SP, imm.
626    int FI = cast<FrameIndexSDNode>(N)->getIndex();
627    SDValue TFI = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
628    if (Subtarget->isThumb()) {
629      return CurDAG->SelectNodeTo(N, ARM::tADDrSPi, MVT::i32, TFI,
630                                  CurDAG->getTargetConstant(0, MVT::i32));
631    } else {
632      SDValue Ops[] = { TFI, CurDAG->getTargetConstant(0, MVT::i32),
633                          getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
634                          CurDAG->getRegister(0, MVT::i32) };
635      return CurDAG->SelectNodeTo(N, ARM::ADDri, MVT::i32, Ops, 5);
636    }
637  }
638  case ISD::ADD: {
639    if (!Subtarget->isThumb())
640      break;
641    // Select add sp, c to tADDhirr.
642    SDValue N0 = Op.getOperand(0);
643    SDValue N1 = Op.getOperand(1);
644    RegisterSDNode *LHSR = dyn_cast<RegisterSDNode>(Op.getOperand(0));
645    RegisterSDNode *RHSR = dyn_cast<RegisterSDNode>(Op.getOperand(1));
646    if (LHSR && LHSR->getReg() == ARM::SP) {
647      std::swap(N0, N1);
648      std::swap(LHSR, RHSR);
649    }
650    if (RHSR && RHSR->getReg() == ARM::SP) {
651      SDValue Val = SDValue(CurDAG->getTargetNode(ARM::tMOVlor2hir, dl,
652                                  Op.getValueType(), N0, N0), 0);
653      return CurDAG->SelectNodeTo(N, ARM::tADDhirr, Op.getValueType(), Val, N1);
654    }
655    break;
656  }
657  case ISD::MUL:
658    if (Subtarget->isThumb())
659      break;
660    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
661      unsigned RHSV = C->getZExtValue();
662      if (!RHSV) break;
663      if (isPowerOf2_32(RHSV-1)) {  // 2^n+1?
664        SDValue V = Op.getOperand(0);
665        unsigned ShImm = ARM_AM::getSORegOpc(ARM_AM::lsl, Log2_32(RHSV-1));
666        SDValue Ops[] = { V, V, CurDAG->getRegister(0, MVT::i32),
667                            CurDAG->getTargetConstant(ShImm, MVT::i32),
668                            getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
669                            CurDAG->getRegister(0, MVT::i32) };
670        return CurDAG->SelectNodeTo(N, ARM::ADDrs, MVT::i32, Ops, 7);
671      }
672      if (isPowerOf2_32(RHSV+1)) {  // 2^n-1?
673        SDValue V = Op.getOperand(0);
674        unsigned ShImm = ARM_AM::getSORegOpc(ARM_AM::lsl, Log2_32(RHSV+1));
675        SDValue Ops[] = { V, V, CurDAG->getRegister(0, MVT::i32),
676                            CurDAG->getTargetConstant(ShImm, MVT::i32),
677                            getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
678                            CurDAG->getRegister(0, MVT::i32) };
679        return CurDAG->SelectNodeTo(N, ARM::RSBrs, MVT::i32, Ops, 7);
680      }
681    }
682    break;
683  case ARMISD::FMRRD:
684    return CurDAG->getTargetNode(ARM::FMRRD, dl, MVT::i32, MVT::i32,
685                                 Op.getOperand(0), getAL(CurDAG),
686                                 CurDAG->getRegister(0, MVT::i32));
687  case ISD::UMUL_LOHI: {
688    SDValue Ops[] = { Op.getOperand(0), Op.getOperand(1),
689                        getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
690                        CurDAG->getRegister(0, MVT::i32) };
691    return CurDAG->getTargetNode(ARM::UMULL, dl, MVT::i32, MVT::i32, Ops, 5);
692  }
693  case ISD::SMUL_LOHI: {
694    SDValue Ops[] = { Op.getOperand(0), Op.getOperand(1),
695                        getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
696                        CurDAG->getRegister(0, MVT::i32) };
697    return CurDAG->getTargetNode(ARM::SMULL, dl, MVT::i32, MVT::i32, Ops, 5);
698  }
699  case ISD::LOAD: {
700    LoadSDNode *LD = cast<LoadSDNode>(Op);
701    ISD::MemIndexedMode AM = LD->getAddressingMode();
702    MVT LoadedVT = LD->getMemoryVT();
703    if (AM != ISD::UNINDEXED) {
704      SDValue Offset, AMOpc;
705      bool isPre = (AM == ISD::PRE_INC) || (AM == ISD::PRE_DEC);
706      unsigned Opcode = 0;
707      bool Match = false;
708      if (LoadedVT == MVT::i32 &&
709          SelectAddrMode2Offset(Op, LD->getOffset(), Offset, AMOpc)) {
710        Opcode = isPre ? ARM::LDR_PRE : ARM::LDR_POST;
711        Match = true;
712      } else if (LoadedVT == MVT::i16 &&
713                 SelectAddrMode3Offset(Op, LD->getOffset(), Offset, AMOpc)) {
714        Match = true;
715        Opcode = (LD->getExtensionType() == ISD::SEXTLOAD)
716          ? (isPre ? ARM::LDRSH_PRE : ARM::LDRSH_POST)
717          : (isPre ? ARM::LDRH_PRE : ARM::LDRH_POST);
718      } else if (LoadedVT == MVT::i8 || LoadedVT == MVT::i1) {
719        if (LD->getExtensionType() == ISD::SEXTLOAD) {
720          if (SelectAddrMode3Offset(Op, LD->getOffset(), Offset, AMOpc)) {
721            Match = true;
722            Opcode = isPre ? ARM::LDRSB_PRE : ARM::LDRSB_POST;
723          }
724        } else {
725          if (SelectAddrMode2Offset(Op, LD->getOffset(), Offset, AMOpc)) {
726            Match = true;
727            Opcode = isPre ? ARM::LDRB_PRE : ARM::LDRB_POST;
728          }
729        }
730      }
731
732      if (Match) {
733        SDValue Chain = LD->getChain();
734        SDValue Base = LD->getBasePtr();
735        SDValue Ops[]= { Base, Offset, AMOpc, getAL(CurDAG),
736                           CurDAG->getRegister(0, MVT::i32), Chain };
737        return CurDAG->getTargetNode(Opcode, dl, MVT::i32, MVT::i32,
738                                     MVT::Other, Ops, 6);
739      }
740    }
741    // Other cases are autogenerated.
742    break;
743  }
744  case ARMISD::BRCOND: {
745    // Pattern: (ARMbrcond:void (bb:Other):$dst, (imm:i32):$cc)
746    // Emits: (Bcc:void (bb:Other):$dst, (imm:i32):$cc)
747    // Pattern complexity = 6  cost = 1  size = 0
748
749    // Pattern: (ARMbrcond:void (bb:Other):$dst, (imm:i32):$cc)
750    // Emits: (tBcc:void (bb:Other):$dst, (imm:i32):$cc)
751    // Pattern complexity = 6  cost = 1  size = 0
752
753    unsigned Opc = Subtarget->isThumb() ? ARM::tBcc : ARM::Bcc;
754    SDValue Chain = Op.getOperand(0);
755    SDValue N1 = Op.getOperand(1);
756    SDValue N2 = Op.getOperand(2);
757    SDValue N3 = Op.getOperand(3);
758    SDValue InFlag = Op.getOperand(4);
759    assert(N1.getOpcode() == ISD::BasicBlock);
760    assert(N2.getOpcode() == ISD::Constant);
761    assert(N3.getOpcode() == ISD::Register);
762
763    SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
764                               cast<ConstantSDNode>(N2)->getZExtValue()),
765                               MVT::i32);
766    SDValue Ops[] = { N1, Tmp2, N3, Chain, InFlag };
767    SDNode *ResNode = CurDAG->getTargetNode(Opc, dl, MVT::Other,
768                                            MVT::Flag, Ops, 5);
769    Chain = SDValue(ResNode, 0);
770    if (Op.getNode()->getNumValues() == 2) {
771      InFlag = SDValue(ResNode, 1);
772      ReplaceUses(SDValue(Op.getNode(), 1), InFlag);
773    }
774    ReplaceUses(SDValue(Op.getNode(), 0), SDValue(Chain.getNode(), Chain.getResNo()));
775    return NULL;
776  }
777  case ARMISD::CMOV: {
778    bool isThumb = Subtarget->isThumb();
779    MVT VT = Op.getValueType();
780    SDValue N0 = Op.getOperand(0);
781    SDValue N1 = Op.getOperand(1);
782    SDValue N2 = Op.getOperand(2);
783    SDValue N3 = Op.getOperand(3);
784    SDValue InFlag = Op.getOperand(4);
785    assert(N2.getOpcode() == ISD::Constant);
786    assert(N3.getOpcode() == ISD::Register);
787
788    // Pattern: (ARMcmov:i32 GPR:i32:$false, so_reg:i32:$true, (imm:i32):$cc)
789    // Emits: (MOVCCs:i32 GPR:i32:$false, so_reg:i32:$true, (imm:i32):$cc)
790    // Pattern complexity = 18  cost = 1  size = 0
791    SDValue CPTmp0;
792    SDValue CPTmp1;
793    SDValue CPTmp2;
794    if (!isThumb && VT == MVT::i32 &&
795        SelectShifterOperandReg(Op, N1, CPTmp0, CPTmp1, CPTmp2)) {
796      SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
797                               cast<ConstantSDNode>(N2)->getZExtValue()),
798                               MVT::i32);
799      SDValue Ops[] = { N0, CPTmp0, CPTmp1, CPTmp2, Tmp2, N3, InFlag };
800      return CurDAG->SelectNodeTo(Op.getNode(), ARM::MOVCCs, MVT::i32, Ops, 7);
801    }
802
803    // Pattern: (ARMcmov:i32 GPR:i32:$false,
804    //             (imm:i32)<<P:Predicate_so_imm>><<X:so_imm_XFORM>>:$true,
805    //             (imm:i32):$cc)
806    // Emits: (MOVCCi:i32 GPR:i32:$false,
807    //           (so_imm_XFORM:i32 (imm:i32):$true), (imm:i32):$cc)
808    // Pattern complexity = 10  cost = 1  size = 0
809    if (VT == MVT::i32 &&
810        N3.getOpcode() == ISD::Constant &&
811        Predicate_so_imm(N3.getNode())) {
812      SDValue Tmp1 = CurDAG->getTargetConstant(((unsigned)
813                               cast<ConstantSDNode>(N1)->getZExtValue()),
814                               MVT::i32);
815      Tmp1 = Transform_so_imm_XFORM(Tmp1.getNode());
816      SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
817                               cast<ConstantSDNode>(N2)->getZExtValue()),
818                               MVT::i32);
819      SDValue Ops[] = { N0, Tmp1, Tmp2, N3, InFlag };
820      return CurDAG->SelectNodeTo(Op.getNode(), ARM::MOVCCi, MVT::i32, Ops, 5);
821    }
822
823    // Pattern: (ARMcmov:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
824    // Emits: (MOVCCr:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
825    // Pattern complexity = 6  cost = 1  size = 0
826    //
827    // Pattern: (ARMcmov:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
828    // Emits: (tMOVCCr:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
829    // Pattern complexity = 6  cost = 11  size = 0
830    //
831    // Also FCPYScc and FCPYDcc.
832    SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
833                               cast<ConstantSDNode>(N2)->getZExtValue()),
834                               MVT::i32);
835    SDValue Ops[] = { N0, N1, Tmp2, N3, InFlag };
836    unsigned Opc = 0;
837    switch (VT.getSimpleVT()) {
838    default: assert(false && "Illegal conditional move type!");
839      break;
840    case MVT::i32:
841      Opc = isThumb ? ARM::tMOVCCr : ARM::MOVCCr;
842      break;
843    case MVT::f32:
844      Opc = ARM::FCPYScc;
845      break;
846    case MVT::f64:
847      Opc = ARM::FCPYDcc;
848      break;
849    }
850    return CurDAG->SelectNodeTo(Op.getNode(), Opc, VT, Ops, 5);
851  }
852  case ARMISD::CNEG: {
853    MVT VT = Op.getValueType();
854    SDValue N0 = Op.getOperand(0);
855    SDValue N1 = Op.getOperand(1);
856    SDValue N2 = Op.getOperand(2);
857    SDValue N3 = Op.getOperand(3);
858    SDValue InFlag = Op.getOperand(4);
859    assert(N2.getOpcode() == ISD::Constant);
860    assert(N3.getOpcode() == ISD::Register);
861
862    SDValue Tmp2 = CurDAG->getTargetConstant(((unsigned)
863                               cast<ConstantSDNode>(N2)->getZExtValue()),
864                               MVT::i32);
865    SDValue Ops[] = { N0, N1, Tmp2, N3, InFlag };
866    unsigned Opc = 0;
867    switch (VT.getSimpleVT()) {
868    default: assert(false && "Illegal conditional move type!");
869      break;
870    case MVT::f32:
871      Opc = ARM::FNEGScc;
872      break;
873    case MVT::f64:
874      Opc = ARM::FNEGDcc;
875      break;
876    }
877    return CurDAG->SelectNodeTo(Op.getNode(), Opc, VT, Ops, 5);
878  }
879
880  case ISD::DECLARE: {
881    SDValue Chain = Op.getOperand(0);
882    SDValue N1 = Op.getOperand(1);
883    SDValue N2 = Op.getOperand(2);
884    FrameIndexSDNode *FINode = dyn_cast<FrameIndexSDNode>(N1);
885    // FIXME: handle VLAs.
886    if (!FINode) {
887      ReplaceUses(Op.getValue(0), Chain);
888      return NULL;
889    }
890    if (N2.getOpcode() == ARMISD::PIC_ADD && isa<LoadSDNode>(N2.getOperand(0)))
891      N2 = N2.getOperand(0);
892    LoadSDNode *Ld = dyn_cast<LoadSDNode>(N2);
893    if (!Ld) {
894      ReplaceUses(Op.getValue(0), Chain);
895      return NULL;
896    }
897    SDValue BasePtr = Ld->getBasePtr();
898    assert(BasePtr.getOpcode() == ARMISD::Wrapper &&
899           isa<ConstantPoolSDNode>(BasePtr.getOperand(0)) &&
900           "llvm.dbg.variable should be a constantpool node");
901    ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(BasePtr.getOperand(0));
902    GlobalValue *GV = 0;
903    if (CP->isMachineConstantPoolEntry()) {
904      ARMConstantPoolValue *ACPV = (ARMConstantPoolValue*)CP->getMachineCPVal();
905      GV = ACPV->getGV();
906    } else
907      GV = dyn_cast<GlobalValue>(CP->getConstVal());
908    if (!GV) {
909      ReplaceUses(Op.getValue(0), Chain);
910      return NULL;
911    }
912
913    SDValue Tmp1 = CurDAG->getTargetFrameIndex(FINode->getIndex(),
914                                               TLI.getPointerTy());
915    SDValue Tmp2 = CurDAG->getTargetGlobalAddress(GV, TLI.getPointerTy());
916    SDValue Ops[] = { Tmp1, Tmp2, Chain };
917    return CurDAG->getTargetNode(TargetInstrInfo::DECLARE, dl,
918                                 MVT::Other, Ops, 3);
919  }
920  }
921
922  return SelectCode(Op);
923}
924
925bool ARMDAGToDAGISel::
926SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode,
927                             std::vector<SDValue> &OutOps) {
928  assert(ConstraintCode == 'm' && "unexpected asm memory constraint");
929
930  SDValue Base, Offset, Opc;
931  if (!SelectAddrMode2(Op, Op, Base, Offset, Opc))
932    return true;
933
934  OutOps.push_back(Base);
935  OutOps.push_back(Offset);
936  OutOps.push_back(Opc);
937  return false;
938}
939
940/// createARMISelDag - This pass converts a legalized DAG into a
941/// ARM-specific DAG, ready for instruction scheduling.
942///
943FunctionPass *llvm::createARMISelDag(ARMTargetMachine &TM) {
944  return new ARMDAGToDAGISel(TM);
945}
946