ARMISelDAGToDAG.cpp revision ee568cf7948230b78303b86c92722c177d3a5673 
1//===-- ARMISelDAGToDAG.cpp - A dag to dag inst selector for ARM ----------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file was developed by Chris Lattner and is distributed under
6// the University of Illinois Open Source 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 "ARMISelLowering.h"
16#include "ARMTargetMachine.h"
17#include "ARMAddressingModes.h"
18#include "llvm/CallingConv.h"
19#include "llvm/Constants.h"
20#include "llvm/DerivedTypes.h"
21#include "llvm/Function.h"
22#include "llvm/Intrinsics.h"
23#include "llvm/CodeGen/MachineFrameInfo.h"
24#include "llvm/CodeGen/MachineFunction.h"
25#include "llvm/CodeGen/MachineInstrBuilder.h"
26#include "llvm/CodeGen/SelectionDAG.h"
27#include "llvm/CodeGen/SelectionDAGISel.h"
28#include "llvm/CodeGen/SSARegMap.h"
29#include "llvm/Target/TargetLowering.h"
30#include "llvm/Target/TargetOptions.h"
31#include "llvm/Support/Debug.h"
32using namespace llvm;
33
34//===--------------------------------------------------------------------===//
35/// ARMDAGToDAGISel - ARM specific code to select ARM machine
36/// instructions for SelectionDAG operations.
37///
38namespace {
39class ARMDAGToDAGISel : public SelectionDAGISel {
40  ARMTargetLowering Lowering;
41
42  /// Subtarget - Keep a pointer to the ARMSubtarget around so that we can
43  /// make the right decision when generating code for different targets.
44  const ARMSubtarget *Subtarget;
45
46public:
47  ARMDAGToDAGISel(ARMTargetMachine &TM)
48    : SelectionDAGISel(Lowering), Lowering(TM),
49    Subtarget(&TM.getSubtarget<ARMSubtarget>()) {
50  }
51
52  virtual const char *getPassName() const {
53    return "ARM Instruction Selection";
54  }
55
56  SDNode *Select(SDOperand Op);
57  virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
58  bool SelectAddrMode2(SDOperand Op, SDOperand N, SDOperand &Base,
59                       SDOperand &Offset, SDOperand &Opc);
60  bool SelectAddrMode2Offset(SDOperand Op, SDOperand N,
61                             SDOperand &Offset, SDOperand &Opc);
62  bool SelectAddrMode3(SDOperand Op, SDOperand N, SDOperand &Base,
63                       SDOperand &Offset, SDOperand &Opc);
64  bool SelectAddrMode3Offset(SDOperand Op, SDOperand N,
65                             SDOperand &Offset, SDOperand &Opc);
66  bool SelectAddrMode5(SDOperand Op, SDOperand N, SDOperand &Base,
67                       SDOperand &Offset);
68
69  bool SelectAddrModePC(SDOperand Op, SDOperand N, SDOperand &Offset,
70                         SDOperand &Label);
71
72  bool SelectThumbAddrModeRR(SDOperand Op, SDOperand N, SDOperand &Base,
73                             SDOperand &Offset);
74  bool SelectThumbAddrModeRI5(SDOperand Op, SDOperand N, unsigned Scale,
75                              SDOperand &Base, SDOperand &OffImm,
76                              SDOperand &Offset);
77  bool SelectThumbAddrModeS1(SDOperand Op, SDOperand N, SDOperand &Base,
78                             SDOperand &OffImm, SDOperand &Offset);
79  bool SelectThumbAddrModeS2(SDOperand Op, SDOperand N, SDOperand &Base,
80                             SDOperand &OffImm, SDOperand &Offset);
81  bool SelectThumbAddrModeS4(SDOperand Op, SDOperand N, SDOperand &Base,
82                             SDOperand &OffImm, SDOperand &Offset);
83  bool SelectThumbAddrModeSP(SDOperand Op, SDOperand N, SDOperand &Base,
84                             SDOperand &OffImm);
85
86  bool SelectShifterOperandReg(SDOperand Op, SDOperand N, SDOperand &A,
87                               SDOperand &B, SDOperand &C);
88
89  // Include the pieces autogenerated from the target description.
90#include "ARMGenDAGISel.inc"
91};
92}
93
94void ARMDAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
95  DEBUG(BB->dump());
96
97  DAG.setRoot(SelectRoot(DAG.getRoot()));
98  DAG.RemoveDeadNodes();
99
100  ScheduleAndEmitDAG(DAG);
101}
102
103bool ARMDAGToDAGISel::SelectAddrMode2(SDOperand Op, SDOperand N,
104                                      SDOperand &Base, SDOperand &Offset,
105                                      SDOperand &Opc) {
106  if (N.getOpcode() == ISD::MUL) {
107    if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
108      // X * [3,5,9] -> X + X * [2,4,8] etc.
109      int RHSC = (int)RHS->getValue();
110      if (RHSC & 1) {
111        RHSC = RHSC & ~1;
112        ARM_AM::AddrOpc AddSub = ARM_AM::add;
113        if (RHSC < 0) {
114          AddSub = ARM_AM::sub;
115          RHSC = - RHSC;
116        }
117        if (isPowerOf2_32(RHSC)) {
118          unsigned ShAmt = Log2_32(RHSC);
119          Base = Offset = N.getOperand(0);
120          Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, ShAmt,
121                                                            ARM_AM::lsl),
122                                          MVT::i32);
123          return true;
124        }
125      }
126    }
127  }
128
129  if (N.getOpcode() != ISD::ADD && N.getOpcode() != ISD::SUB) {
130    Base = N;
131    if (N.getOpcode() == ISD::FrameIndex) {
132      int FI = cast<FrameIndexSDNode>(N)->getIndex();
133      Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
134    } else if (N.getOpcode() == ARMISD::Wrapper) {
135      Base = N.getOperand(0);
136    }
137    Offset = CurDAG->getRegister(0, MVT::i32);
138    Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(ARM_AM::add, 0,
139                                                      ARM_AM::no_shift),
140                                    MVT::i32);
141    return true;
142  }
143
144  // Match simple R +/- imm12 operands.
145  if (N.getOpcode() == ISD::ADD)
146    if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
147      int RHSC = (int)RHS->getValue();
148      if ((RHSC >= 0 && RHSC < 0x1000) ||
149          (RHSC < 0 && RHSC > -0x1000)) { // 12 bits.
150        Base = N.getOperand(0);
151        if (Base.getOpcode() == ISD::FrameIndex) {
152          int FI = cast<FrameIndexSDNode>(Base)->getIndex();
153          Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
154        }
155        Offset = CurDAG->getRegister(0, MVT::i32);
156
157        ARM_AM::AddrOpc AddSub = ARM_AM::add;
158        if (RHSC < 0) {
159          AddSub = ARM_AM::sub;
160          RHSC = - RHSC;
161        }
162        Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, RHSC,
163                                                          ARM_AM::no_shift),
164                                        MVT::i32);
165        return true;
166      }
167    }
168
169  // Otherwise this is R +/- [possibly shifted] R
170  ARM_AM::AddrOpc AddSub = N.getOpcode() == ISD::ADD ? ARM_AM::add:ARM_AM::sub;
171  ARM_AM::ShiftOpc ShOpcVal = ARM_AM::getShiftOpcForNode(N.getOperand(1));
172  unsigned ShAmt = 0;
173
174  Base   = N.getOperand(0);
175  Offset = N.getOperand(1);
176
177  if (ShOpcVal != ARM_AM::no_shift) {
178    // Check to see if the RHS of the shift is a constant, if not, we can't fold
179    // it.
180    if (ConstantSDNode *Sh =
181           dyn_cast<ConstantSDNode>(N.getOperand(1).getOperand(1))) {
182      ShAmt = Sh->getValue();
183      Offset = N.getOperand(1).getOperand(0);
184    } else {
185      ShOpcVal = ARM_AM::no_shift;
186    }
187  }
188
189  // Try matching (R shl C) + (R).
190  if (N.getOpcode() == ISD::ADD && ShOpcVal == ARM_AM::no_shift) {
191    ShOpcVal = ARM_AM::getShiftOpcForNode(N.getOperand(0));
192    if (ShOpcVal != ARM_AM::no_shift) {
193      // Check to see if the RHS of the shift is a constant, if not, we can't
194      // fold it.
195      if (ConstantSDNode *Sh =
196          dyn_cast<ConstantSDNode>(N.getOperand(0).getOperand(1))) {
197        ShAmt = Sh->getValue();
198        Offset = N.getOperand(0).getOperand(0);
199        Base = N.getOperand(1);
200      } else {
201        ShOpcVal = ARM_AM::no_shift;
202      }
203    }
204  }
205
206  Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, ShAmt, ShOpcVal),
207                                  MVT::i32);
208  return true;
209}
210
211bool ARMDAGToDAGISel::SelectAddrMode2Offset(SDOperand Op, SDOperand N,
212                                            SDOperand &Offset, SDOperand &Opc) {
213  unsigned Opcode = Op.getOpcode();
214  ISD::MemIndexedMode AM = (Opcode == ISD::LOAD)
215    ? cast<LoadSDNode>(Op)->getAddressingMode()
216    : cast<StoreSDNode>(Op)->getAddressingMode();
217  ARM_AM::AddrOpc AddSub = (AM == ISD::PRE_INC || AM == ISD::POST_INC)
218    ? ARM_AM::add : ARM_AM::sub;
219  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N)) {
220    int Val = (int)C->getValue();
221    if (Val >= 0 && Val < 0x1000) { // 12 bits.
222      Offset = CurDAG->getRegister(0, MVT::i32);
223      Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, Val,
224                                                        ARM_AM::no_shift),
225                                      MVT::i32);
226      return true;
227    }
228  }
229
230  Offset = N;
231  ARM_AM::ShiftOpc ShOpcVal = ARM_AM::getShiftOpcForNode(N);
232  unsigned ShAmt = 0;
233  if (ShOpcVal != ARM_AM::no_shift) {
234    // Check to see if the RHS of the shift is a constant, if not, we can't fold
235    // it.
236    if (ConstantSDNode *Sh = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
237      ShAmt = Sh->getValue();
238      Offset = N.getOperand(0);
239    } else {
240      ShOpcVal = ARM_AM::no_shift;
241    }
242  }
243
244  Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, ShAmt, ShOpcVal),
245                                  MVT::i32);
246  return true;
247}
248
249
250bool ARMDAGToDAGISel::SelectAddrMode3(SDOperand Op, SDOperand N,
251                                      SDOperand &Base, SDOperand &Offset,
252                                      SDOperand &Opc) {
253  if (N.getOpcode() == ISD::SUB) {
254    // X - C  is canonicalize to X + -C, no need to handle it here.
255    Base = N.getOperand(0);
256    Offset = N.getOperand(1);
257    Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(ARM_AM::sub, 0),MVT::i32);
258    return true;
259  }
260
261  if (N.getOpcode() != ISD::ADD) {
262    Base = N;
263    if (N.getOpcode() == ISD::FrameIndex) {
264      int FI = cast<FrameIndexSDNode>(N)->getIndex();
265      Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
266    }
267    Offset = CurDAG->getRegister(0, MVT::i32);
268    Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(ARM_AM::add, 0),MVT::i32);
269    return true;
270  }
271
272  // If the RHS is +/- imm8, fold into addr mode.
273  if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
274    int RHSC = (int)RHS->getValue();
275    if ((RHSC >= 0 && RHSC < 256) ||
276        (RHSC < 0 && RHSC > -256)) { // note -256 itself isn't allowed.
277      Base = N.getOperand(0);
278      if (Base.getOpcode() == ISD::FrameIndex) {
279        int FI = cast<FrameIndexSDNode>(Base)->getIndex();
280        Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
281      }
282      Offset = CurDAG->getRegister(0, MVT::i32);
283
284      ARM_AM::AddrOpc AddSub = ARM_AM::add;
285      if (RHSC < 0) {
286        AddSub = ARM_AM::sub;
287        RHSC = - RHSC;
288      }
289      Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(AddSub, RHSC),MVT::i32);
290      return true;
291    }
292  }
293
294  Base = N.getOperand(0);
295  Offset = N.getOperand(1);
296  Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(ARM_AM::add, 0), MVT::i32);
297  return true;
298}
299
300bool ARMDAGToDAGISel::SelectAddrMode3Offset(SDOperand Op, SDOperand N,
301                                            SDOperand &Offset, SDOperand &Opc) {
302  unsigned Opcode = Op.getOpcode();
303  ISD::MemIndexedMode AM = (Opcode == ISD::LOAD)
304    ? cast<LoadSDNode>(Op)->getAddressingMode()
305    : cast<StoreSDNode>(Op)->getAddressingMode();
306  ARM_AM::AddrOpc AddSub = (AM == ISD::PRE_INC || AM == ISD::POST_INC)
307    ? ARM_AM::add : ARM_AM::sub;
308  if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N)) {
309    int Val = (int)C->getValue();
310    if (Val >= 0 && Val < 256) {
311      Offset = CurDAG->getRegister(0, MVT::i32);
312      Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(AddSub, Val), MVT::i32);
313      return true;
314    }
315  }
316
317  Offset = N;
318  Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(AddSub, 0), MVT::i32);
319  return true;
320}
321
322
323bool ARMDAGToDAGISel::SelectAddrMode5(SDOperand Op, SDOperand N,
324                                      SDOperand &Base, SDOperand &Offset) {
325  if (N.getOpcode() != ISD::ADD) {
326    Base = N;
327    if (N.getOpcode() == ISD::FrameIndex) {
328      int FI = cast<FrameIndexSDNode>(N)->getIndex();
329      Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
330    } else if (N.getOpcode() == ARMISD::Wrapper) {
331      Base = N.getOperand(0);
332    }
333    Offset = CurDAG->getTargetConstant(ARM_AM::getAM5Opc(ARM_AM::add, 0),
334                                       MVT::i32);
335    return true;
336  }
337
338  // If the RHS is +/- imm8, fold into addr mode.
339  if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
340    int RHSC = (int)RHS->getValue();
341    if ((RHSC & 3) == 0) {  // The constant is implicitly multiplied by 4.
342      RHSC >>= 2;
343      if ((RHSC >= 0 && RHSC < 256) ||
344          (RHSC < 0 && RHSC > -256)) { // note -256 itself isn't allowed.
345        Base = N.getOperand(0);
346        if (Base.getOpcode() == ISD::FrameIndex) {
347          int FI = cast<FrameIndexSDNode>(Base)->getIndex();
348          Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
349        }
350
351        ARM_AM::AddrOpc AddSub = ARM_AM::add;
352        if (RHSC < 0) {
353          AddSub = ARM_AM::sub;
354          RHSC = - RHSC;
355        }
356        Offset = CurDAG->getTargetConstant(ARM_AM::getAM5Opc(AddSub, RHSC),
357                                           MVT::i32);
358        return true;
359      }
360    }
361  }
362
363  Base = N;
364  Offset = CurDAG->getTargetConstant(ARM_AM::getAM5Opc(ARM_AM::add, 0),
365                                     MVT::i32);
366  return true;
367}
368
369bool ARMDAGToDAGISel::SelectAddrModePC(SDOperand Op, SDOperand N,
370                                        SDOperand &Offset, SDOperand &Label) {
371  if (N.getOpcode() == ARMISD::PIC_ADD && N.hasOneUse()) {
372    Offset = N.getOperand(0);
373    SDOperand N1 = N.getOperand(1);
374    Label  = CurDAG->getTargetConstant(cast<ConstantSDNode>(N1)->getValue(),
375                                       MVT::i32);
376    return true;
377  }
378  return false;
379}
380
381bool ARMDAGToDAGISel::SelectThumbAddrModeRR(SDOperand Op, SDOperand N,
382                                            SDOperand &Base, SDOperand &Offset){
383  if (N.getOpcode() != ISD::ADD) {
384    Base = N;
385    // We must materialize a zero in a reg! Returning an constant here won't
386    // work since its node is -1 so it won't get added to the selection queue.
387    // Explicitly issue a tMOVri8 node!
388    Offset = SDOperand(CurDAG->getTargetNode(ARM::tMOVi8, MVT::i32,
389                                    CurDAG->getTargetConstant(0, MVT::i32)), 0);
390    return true;
391  }
392
393  Base = N.getOperand(0);
394  Offset = N.getOperand(1);
395  return true;
396}
397
398bool
399ARMDAGToDAGISel::SelectThumbAddrModeRI5(SDOperand Op, SDOperand N,
400                                        unsigned Scale, SDOperand &Base,
401                                        SDOperand &OffImm, SDOperand &Offset) {
402  if (Scale == 4) {
403    SDOperand TmpBase, TmpOffImm;
404    if (SelectThumbAddrModeSP(Op, N, TmpBase, TmpOffImm))
405      return false;  // We want to select tLDRspi / tSTRspi instead.
406    if (N.getOpcode() == ARMISD::Wrapper &&
407        N.getOperand(0).getOpcode() == ISD::TargetConstantPool)
408      return false;  // We want to select tLDRpci instead.
409  }
410
411  if (N.getOpcode() != ISD::ADD) {
412    Base = (N.getOpcode() == ARMISD::Wrapper) ? N.getOperand(0) : N;
413    Offset = CurDAG->getRegister(0, MVT::i32);
414    OffImm = CurDAG->getTargetConstant(0, MVT::i32);
415    return true;
416  }
417
418  // Thumb does not have [sp, r] address mode.
419  RegisterSDNode *LHSR = dyn_cast<RegisterSDNode>(N.getOperand(0));
420  RegisterSDNode *RHSR = dyn_cast<RegisterSDNode>(N.getOperand(1));
421  if ((LHSR && LHSR->getReg() == ARM::SP) ||
422      (RHSR && RHSR->getReg() == ARM::SP)) {
423    Base = N;
424    Offset = CurDAG->getRegister(0, MVT::i32);
425    OffImm = CurDAG->getTargetConstant(0, MVT::i32);
426    return true;
427  }
428
429  // If the RHS is + imm5 * scale, fold into addr mode.
430  if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
431    int RHSC = (int)RHS->getValue();
432    if ((RHSC & (Scale-1)) == 0) {  // The constant is implicitly multiplied.
433      RHSC /= Scale;
434      if (RHSC >= 0 && RHSC < 32) {
435        Base = N.getOperand(0);
436        Offset = CurDAG->getRegister(0, MVT::i32);
437        OffImm = CurDAG->getTargetConstant(RHSC, MVT::i32);
438        return true;
439      }
440    }
441  }
442
443  Base = N.getOperand(0);
444  Offset = N.getOperand(1);
445  OffImm = CurDAG->getTargetConstant(0, MVT::i32);
446  return true;
447}
448
449bool ARMDAGToDAGISel::SelectThumbAddrModeS1(SDOperand Op, SDOperand N,
450                                            SDOperand &Base, SDOperand &OffImm,
451                                            SDOperand &Offset) {
452  return SelectThumbAddrModeRI5(Op, N, 1, Base, OffImm, Offset);
453}
454
455bool ARMDAGToDAGISel::SelectThumbAddrModeS2(SDOperand Op, SDOperand N,
456                                            SDOperand &Base, SDOperand &OffImm,
457                                            SDOperand &Offset) {
458  return SelectThumbAddrModeRI5(Op, N, 2, Base, OffImm, Offset);
459}
460
461bool ARMDAGToDAGISel::SelectThumbAddrModeS4(SDOperand Op, SDOperand N,
462                                            SDOperand &Base, SDOperand &OffImm,
463                                            SDOperand &Offset) {
464  return SelectThumbAddrModeRI5(Op, N, 4, Base, OffImm, Offset);
465}
466
467bool ARMDAGToDAGISel::SelectThumbAddrModeSP(SDOperand Op, SDOperand N,
468                                           SDOperand &Base, SDOperand &OffImm) {
469  if (N.getOpcode() == ISD::FrameIndex) {
470    int FI = cast<FrameIndexSDNode>(N)->getIndex();
471    Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
472    OffImm = CurDAG->getTargetConstant(0, MVT::i32);
473    return true;
474  }
475
476  if (N.getOpcode() != ISD::ADD)
477    return false;
478
479  RegisterSDNode *LHSR = dyn_cast<RegisterSDNode>(N.getOperand(0));
480  if (N.getOperand(0).getOpcode() == ISD::FrameIndex ||
481      (LHSR && LHSR->getReg() == ARM::SP)) {
482    // If the RHS is + imm8 * scale, fold into addr mode.
483    if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
484      int RHSC = (int)RHS->getValue();
485      if ((RHSC & 3) == 0) {  // The constant is implicitly multiplied.
486        RHSC >>= 2;
487        if (RHSC >= 0 && RHSC < 256) {
488          Base = N.getOperand(0);
489          if (Base.getOpcode() == ISD::FrameIndex) {
490            int FI = cast<FrameIndexSDNode>(Base)->getIndex();
491            Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
492          }
493          OffImm = CurDAG->getTargetConstant(RHSC, MVT::i32);
494          return true;
495        }
496      }
497    }
498  }
499
500  return false;
501}
502
503bool ARMDAGToDAGISel::SelectShifterOperandReg(SDOperand Op,
504                                              SDOperand N,
505                                              SDOperand &BaseReg,
506                                              SDOperand &ShReg,
507                                              SDOperand &Opc) {
508  ARM_AM::ShiftOpc ShOpcVal = ARM_AM::getShiftOpcForNode(N);
509
510  // Don't match base register only case. That is matched to a separate
511  // lower complexity pattern with explicit register operand.
512  if (ShOpcVal == ARM_AM::no_shift) return false;
513
514  BaseReg = N.getOperand(0);
515  unsigned ShImmVal = 0;
516  if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
517    ShReg = CurDAG->getRegister(0, MVT::i32);
518    ShImmVal = RHS->getValue() & 31;
519  } else {
520    ShReg = N.getOperand(1);
521  }
522  Opc = CurDAG->getTargetConstant(ARM_AM::getSORegOpc(ShOpcVal, ShImmVal),
523                                  MVT::i32);
524  return true;
525}
526
527/// getAL - Returns a ARMCC::AL immediate node.
528static inline SDOperand getAL(SelectionDAG *CurDAG) {
529  return CurDAG->getTargetConstant((uint64_t)ARMCC::AL, MVT::i32);
530}
531
532
533SDNode *ARMDAGToDAGISel::Select(SDOperand Op) {
534  SDNode *N = Op.Val;
535  unsigned Opcode = N->getOpcode();
536
537  if (Opcode >= ISD::BUILTIN_OP_END && Opcode < ARMISD::FIRST_NUMBER)
538    return NULL;   // Already selected.
539
540  switch (N->getOpcode()) {
541  default: break;
542  case ISD::Constant: {
543    unsigned Val = cast<ConstantSDNode>(N)->getValue();
544    bool UseCP = true;
545    if (Subtarget->isThumb())
546      UseCP = (Val > 255 &&                          // MOV
547               ~Val > 255 &&                         // MOV + MVN
548               !ARM_AM::isThumbImmShiftedVal(Val));  // MOV + LSL
549    else
550      UseCP = (ARM_AM::getSOImmVal(Val) == -1 &&     // MOV
551               ARM_AM::getSOImmVal(~Val) == -1 &&    // MVN
552               !ARM_AM::isSOImmTwoPartVal(Val));     // two instrs.
553    if (UseCP) {
554      SDOperand CPIdx =
555        CurDAG->getTargetConstantPool(ConstantInt::get(Type::Int32Ty, Val),
556                                      TLI.getPointerTy());
557
558      SDNode *ResNode;
559      if (Subtarget->isThumb())
560        ResNode = CurDAG->getTargetNode(ARM::tLDRcp, MVT::i32, MVT::Other,
561                                        CPIdx, CurDAG->getEntryNode());
562      else {
563        SDOperand Ops[] = {
564          CPIdx,
565          CurDAG->getRegister(0, MVT::i32),
566          CurDAG->getTargetConstant(0, MVT::i32),
567          getAL(CurDAG),
568          CurDAG->getRegister(0, MVT::i32),
569          CurDAG->getEntryNode()
570        };
571        ResNode=CurDAG->getTargetNode(ARM::LDRcp, MVT::i32, MVT::Other, Ops, 6);
572      }
573      ReplaceUses(Op, SDOperand(ResNode, 0));
574      return NULL;
575    }
576
577    // Other cases are autogenerated.
578    break;
579  }
580  case ISD::FrameIndex: {
581    // Selects to ADDri FI, 0 which in turn will become ADDri SP, imm.
582    int FI = cast<FrameIndexSDNode>(N)->getIndex();
583    SDOperand TFI = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
584    if (Subtarget->isThumb())
585      return CurDAG->SelectNodeTo(N, ARM::tADDrSPi, MVT::i32, TFI,
586                                  CurDAG->getTargetConstant(0, MVT::i32));
587    else {
588      SDOperand Ops[] = { TFI, CurDAG->getTargetConstant(0, MVT::i32),
589                          getAL(CurDAG), CurDAG->getRegister(0, MVT::i32) };
590      return CurDAG->SelectNodeTo(N, ARM::ADDri, MVT::i32, Ops, 4);
591    }
592  }
593  case ISD::ADD: {
594    // Select add sp, c to tADDhirr.
595    SDOperand N0 = Op.getOperand(0);
596    SDOperand N1 = Op.getOperand(1);
597    RegisterSDNode *LHSR = dyn_cast<RegisterSDNode>(Op.getOperand(0));
598    RegisterSDNode *RHSR = dyn_cast<RegisterSDNode>(Op.getOperand(1));
599    if (LHSR && LHSR->getReg() == ARM::SP) {
600      std::swap(N0, N1);
601      std::swap(LHSR, RHSR);
602    }
603    if (RHSR && RHSR->getReg() == ARM::SP) {
604      AddToISelQueue(N0);
605      AddToISelQueue(N1);
606      return CurDAG->SelectNodeTo(N, ARM::tADDhirr, Op.getValueType(), N0, N1);
607    }
608    break;
609  }
610  case ISD::MUL:
611    if (Subtarget->isThumb())
612      break;
613    if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
614      unsigned RHSV = C->getValue();
615      if (!RHSV) break;
616      if (isPowerOf2_32(RHSV-1)) {  // 2^n+1?
617        SDOperand V = Op.getOperand(0);
618        AddToISelQueue(V);
619        unsigned ShImm = ARM_AM::getSORegOpc(ARM_AM::lsl, Log2_32(RHSV-1));
620        SDOperand Ops[] = { V, V, CurDAG->getRegister(0, MVT::i32),
621                            CurDAG->getTargetConstant(ShImm, MVT::i32),
622                            getAL(CurDAG), CurDAG->getRegister(0, MVT::i32)
623
624        };
625        return CurDAG->SelectNodeTo(N, ARM::ADDrs, MVT::i32, Ops, 6);
626      }
627      if (isPowerOf2_32(RHSV+1)) {  // 2^n-1?
628        SDOperand V = Op.getOperand(0);
629        AddToISelQueue(V);
630        unsigned ShImm = ARM_AM::getSORegOpc(ARM_AM::lsl, Log2_32(RHSV+1));
631        SDOperand Ops[] = { V, V, CurDAG->getRegister(0, MVT::i32),
632                            CurDAG->getTargetConstant(ShImm, MVT::i32),
633                            getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
634        };
635        return CurDAG->SelectNodeTo(N, ARM::RSBrs, MVT::i32, Ops, 6);
636      }
637    }
638    break;
639  case ARMISD::FMRRD:
640    AddToISelQueue(Op.getOperand(0));
641    return CurDAG->getTargetNode(ARM::FMRRD, MVT::i32, MVT::i32,
642                                 Op.getOperand(0), getAL(CurDAG),
643                                 CurDAG->getRegister(0, MVT::i32));
644  case ARMISD::MULHILOU: {
645    AddToISelQueue(Op.getOperand(0));
646    AddToISelQueue(Op.getOperand(1));
647    SDOperand Ops[] = { Op.getOperand(0), Op.getOperand(1),
648                        getAL(CurDAG), CurDAG->getRegister(0, MVT::i32) };
649    return CurDAG->getTargetNode(ARM::UMULL, MVT::i32, MVT::i32, Ops, 4);
650  }
651  case ARMISD::MULHILOS: {
652    AddToISelQueue(Op.getOperand(0));
653    AddToISelQueue(Op.getOperand(1));
654    SDOperand Ops[] = { Op.getOperand(0), Op.getOperand(1),
655                        getAL(CurDAG), CurDAG->getRegister(0, MVT::i32) };
656    return CurDAG->getTargetNode(ARM::SMULL, MVT::i32, MVT::i32, Ops, 4);
657  }
658  case ISD::LOAD: {
659    LoadSDNode *LD = cast<LoadSDNode>(Op);
660    ISD::MemIndexedMode AM = LD->getAddressingMode();
661    MVT::ValueType LoadedVT = LD->getLoadedVT();
662    if (AM != ISD::UNINDEXED) {
663      SDOperand Offset, AMOpc;
664      bool isPre = (AM == ISD::PRE_INC) || (AM == ISD::PRE_DEC);
665      unsigned Opcode = 0;
666      bool Match = false;
667      if (LoadedVT == MVT::i32 &&
668          SelectAddrMode2Offset(Op, LD->getOffset(), Offset, AMOpc)) {
669        Opcode = isPre ? ARM::LDR_PRE : ARM::LDR_POST;
670        Match = true;
671      } else if (LoadedVT == MVT::i16 &&
672                 SelectAddrMode3Offset(Op, LD->getOffset(), Offset, AMOpc)) {
673        Match = true;
674        Opcode = (LD->getExtensionType() == ISD::SEXTLOAD)
675          ? (isPre ? ARM::LDRSH_PRE : ARM::LDRSH_POST)
676          : (isPre ? ARM::LDRH_PRE : ARM::LDRH_POST);
677      } else if (LoadedVT == MVT::i8 || LoadedVT == MVT::i1) {
678        if (LD->getExtensionType() == ISD::SEXTLOAD) {
679          if (SelectAddrMode3Offset(Op, LD->getOffset(), Offset, AMOpc)) {
680            Match = true;
681            Opcode = isPre ? ARM::LDRSB_PRE : ARM::LDRSB_POST;
682          }
683        } else {
684          if (SelectAddrMode2Offset(Op, LD->getOffset(), Offset, AMOpc)) {
685            Match = true;
686            Opcode = isPre ? ARM::LDRB_PRE : ARM::LDRB_POST;
687          }
688        }
689      }
690
691      if (Match) {
692        SDOperand Chain = LD->getChain();
693        SDOperand Base = LD->getBasePtr();
694        AddToISelQueue(Chain);
695        AddToISelQueue(Base);
696        AddToISelQueue(Offset);
697        SDOperand Ops[]= { Base, Offset, AMOpc, getAL(CurDAG),
698                           CurDAG->getRegister(0, MVT::i32), Chain };
699        return CurDAG->getTargetNode(Opcode, MVT::i32, MVT::i32,
700                                     MVT::Other, Ops, 6);
701      }
702    }
703    // Other cases are autogenerated.
704    break;
705  }
706  case ARMISD::BRCOND: {
707    // Pattern: (ARMbrcond:void (bb:Other):$dst, (imm:i32):$cc)
708    // Emits: (Bcc:void (bb:Other):$dst, (imm:i32):$cc)
709    // Pattern complexity = 6  cost = 1  size = 0
710
711    // Pattern: (ARMbrcond:void (bb:Other):$dst, (imm:i32):$cc)
712    // Emits: (tBcc:void (bb:Other):$dst, (imm:i32):$cc)
713    // Pattern complexity = 6  cost = 1  size = 0
714
715    unsigned Opc = Subtarget->isThumb() ? ARM::tBcc : ARM::Bcc;
716    SDOperand Chain = Op.getOperand(0);
717    SDOperand N1 = Op.getOperand(1);
718    SDOperand N2 = Op.getOperand(2);
719    SDOperand N3 = Op.getOperand(3);
720    SDOperand InFlag = Op.getOperand(4);
721    assert(N1.getOpcode() == ISD::BasicBlock);
722    assert(N2.getOpcode() == ISD::Constant);
723    assert(N3.getOpcode() == ISD::Register);
724
725    AddToISelQueue(Chain);
726    AddToISelQueue(N1);
727    AddToISelQueue(InFlag);
728    SDOperand Tmp2 = CurDAG->getTargetConstant(((unsigned)
729                               cast<ConstantSDNode>(N2)->getValue()), MVT::i32);
730    SDOperand Ops[] = { N1, Tmp2, N3, Chain, InFlag };
731    SDNode *ResNode = CurDAG->getTargetNode(Opc, MVT::Other, MVT::Flag, Ops, 5);
732    Chain = SDOperand(ResNode, 0);
733    InFlag = SDOperand(ResNode, 1);
734    ReplaceUses(SDOperand(Op.Val, 1), InFlag);
735    ReplaceUses(SDOperand(Op.Val, 0), SDOperand(Chain.Val, Chain.ResNo));
736    return NULL;
737  }
738  case ARMISD::CMOV: {
739    bool isThumb = Subtarget->isThumb();
740    MVT::ValueType VT = Op.getValueType();
741    SDOperand N0 = Op.getOperand(0);
742    SDOperand N1 = Op.getOperand(1);
743    SDOperand N2 = Op.getOperand(2);
744    SDOperand N3 = Op.getOperand(3);
745    SDOperand InFlag = Op.getOperand(4);
746    assert(N2.getOpcode() == ISD::Constant);
747    assert(N3.getOpcode() == ISD::Register);
748
749    // Pattern: (ARMcmov:i32 GPR:i32:$false, so_reg:i32:$true, (imm:i32):$cc)
750    // Emits: (MOVCCs:i32 GPR:i32:$false, so_reg:i32:$true, (imm:i32):$cc)
751    // Pattern complexity = 18  cost = 1  size = 0
752    SDOperand CPTmp0;
753    SDOperand CPTmp1;
754    SDOperand CPTmp2;
755    if (!isThumb && VT == MVT::i32 &&
756        SelectShifterOperandReg(Op, N1, CPTmp0, CPTmp1, CPTmp2)) {
757      AddToISelQueue(N0);
758      AddToISelQueue(CPTmp0);
759      AddToISelQueue(CPTmp1);
760      AddToISelQueue(CPTmp2);
761      AddToISelQueue(InFlag);
762      SDOperand Tmp2 = CurDAG->getTargetConstant(((unsigned)
763                               cast<ConstantSDNode>(N2)->getValue()), MVT::i32);
764      SDOperand Ops[] = { N0, CPTmp0, CPTmp1, CPTmp2, Tmp2, N3, InFlag };
765      return CurDAG->SelectNodeTo(Op.Val, ARM::MOVCCs, MVT::i32, Ops, 7);
766    }
767
768    // Pattern: (ARMcmov:i32 GPR:i32:$false,
769    //             (imm:i32)<<P:Predicate_so_imm>><<X:so_imm_XFORM>>:$true,
770    //             (imm:i32):$cc)
771    // Emits: (MOVCCi:i32 GPR:i32:$false,
772    //           (so_imm_XFORM:i32 (imm:i32):$true), (imm:i32):$cc)
773    // Pattern complexity = 10  cost = 1  size = 0
774    if (VT == MVT::i32 &&
775        N3.getOpcode() == ISD::Constant &&
776        Predicate_so_imm(N3.Val)) {
777      AddToISelQueue(N0);
778      AddToISelQueue(InFlag);
779      SDOperand Tmp1 = CurDAG->getTargetConstant(((unsigned)
780                               cast<ConstantSDNode>(N1)->getValue()), MVT::i32);
781      Tmp1 = Transform_so_imm_XFORM(Tmp1.Val);
782      SDOperand Tmp2 = CurDAG->getTargetConstant(((unsigned)
783                               cast<ConstantSDNode>(N2)->getValue()), MVT::i32);
784      SDOperand Ops[] = { N0, Tmp1, Tmp2, N3, InFlag };
785      return CurDAG->SelectNodeTo(Op.Val, ARM::MOVCCi, MVT::i32, Ops, 5);
786    }
787
788    // Pattern: (ARMcmov:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
789    // Emits: (MOVCCr:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
790    // Pattern complexity = 6  cost = 1  size = 0
791    //
792    // Pattern: (ARMcmov:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
793    // Emits: (tMOVCCr:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
794    // Pattern complexity = 6  cost = 11  size = 0
795    //
796    // Also FCPYScc and FCPYDcc.
797    AddToISelQueue(N0);
798    AddToISelQueue(N1);
799    AddToISelQueue(InFlag);
800    SDOperand Tmp2 = CurDAG->getTargetConstant(((unsigned)
801                               cast<ConstantSDNode>(N2)->getValue()), MVT::i32);
802    SDOperand Ops[] = { N0, N1, Tmp2, N3, InFlag };
803    unsigned Opc = 0;
804    switch (VT) {
805    default: assert(false && "Illegal conditional move type!");
806      break;
807    case MVT::i32:
808      Opc = isThumb ? ARM::tMOVCCr : ARM::MOVCCr;
809      break;
810    case MVT::f32:
811      Opc = ARM::FCPYScc;
812      break;
813    case MVT::f64:
814      Opc = ARM::FCPYDcc;
815      break;
816    }
817    return CurDAG->SelectNodeTo(Op.Val, Opc, VT, Ops, 5);
818  }
819  case ARMISD::CNEG: {
820    MVT::ValueType VT = Op.getValueType();
821    SDOperand N0 = Op.getOperand(0);
822    SDOperand N1 = Op.getOperand(1);
823    SDOperand N2 = Op.getOperand(2);
824    SDOperand N3 = Op.getOperand(3);
825    SDOperand InFlag = Op.getOperand(4);
826    assert(N2.getOpcode() == ISD::Constant);
827    assert(N3.getOpcode() == ISD::Register);
828
829    AddToISelQueue(N0);
830    AddToISelQueue(N1);
831    AddToISelQueue(InFlag);
832    SDOperand Tmp2 = CurDAG->getTargetConstant(((unsigned)
833                               cast<ConstantSDNode>(N2)->getValue()), MVT::i32);
834    SDOperand Ops[] = { N0, N1, Tmp2, N3, InFlag };
835    unsigned Opc = 0;
836    switch (VT) {
837    default: assert(false && "Illegal conditional move type!");
838      break;
839    case MVT::f32:
840      Opc = ARM::FNEGScc;
841      break;
842    case MVT::f64:
843      Opc = ARM::FNEGDcc;
844      break;
845    }
846    return CurDAG->SelectNodeTo(Op.Val, Opc, VT, Ops, 5);
847  }
848  }
849  return SelectCode(Op);
850}
851
852/// createARMISelDag - This pass converts a legalized DAG into a
853/// ARM-specific DAG, ready for instruction scheduling.
854///
855FunctionPass *llvm::createARMISelDag(ARMTargetMachine &TM) {
856  return new ARMDAGToDAGISel(TM);
857}
858