ARMISelDAGToDAG.cpp revision f5da13367f88f06e3b585dc2263ab6e9ca6c4bf8 
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 "ARMTargetMachine.h"
16#include "llvm/CallingConv.h"
17#include "llvm/DerivedTypes.h"
18#include "llvm/Function.h"
19#include "llvm/Constants.h"
20#include "llvm/Intrinsics.h"
21#include "llvm/ADT/VectorExtras.h"
22#include "llvm/CodeGen/MachineFrameInfo.h"
23#include "llvm/CodeGen/MachineFunction.h"
24#include "llvm/CodeGen/MachineInstrBuilder.h"
25#include "llvm/CodeGen/SelectionDAG.h"
26#include "llvm/CodeGen/SelectionDAGISel.h"
27#include "llvm/CodeGen/SSARegMap.h"
28#include "llvm/Target/TargetLowering.h"
29#include "llvm/Support/Debug.h"
30#include <vector>
31using namespace llvm;
32
33namespace {
34  class ARMTargetLowering : public TargetLowering {
35    int VarArgsFrameIndex;            // FrameIndex for start of varargs area.
36  public:
37    ARMTargetLowering(TargetMachine &TM);
38    virtual SDOperand LowerOperation(SDOperand Op, SelectionDAG &DAG);
39    virtual const char *getTargetNodeName(unsigned Opcode) const;
40    std::vector<unsigned>
41    getRegClassForInlineAsmConstraint(const std::string &Constraint,
42				      MVT::ValueType VT) const;
43  };
44
45}
46
47ARMTargetLowering::ARMTargetLowering(TargetMachine &TM)
48  : TargetLowering(TM) {
49  addRegisterClass(MVT::i32, ARM::IntRegsRegisterClass);
50  addRegisterClass(MVT::f32, ARM::FPRegsRegisterClass);
51  addRegisterClass(MVT::f64, ARM::DFPRegsRegisterClass);
52
53  setLoadXAction(ISD::EXTLOAD, MVT::f32, Expand);
54
55  setOperationAction(ISD::FP_TO_SINT, MVT::i32, Custom);
56  setOperationAction(ISD::SINT_TO_FP, MVT::i32, Custom);
57
58  setOperationAction(ISD::FP_TO_UINT, MVT::i32, Custom);
59  setOperationAction(ISD::UINT_TO_FP, MVT::i32, Custom);
60
61  setOperationAction(ISD::RET,           MVT::Other, Custom);
62  setOperationAction(ISD::GlobalAddress, MVT::i32,   Custom);
63  setOperationAction(ISD::ConstantPool,  MVT::i32,   Custom);
64
65  setOperationAction(ISD::SIGN_EXTEND_INREG, MVT::i16, Expand);
66  setOperationAction(ISD::SIGN_EXTEND_INREG, MVT::i8 , Expand);
67  setOperationAction(ISD::SIGN_EXTEND_INREG, MVT::i1 , Expand);
68
69  setOperationAction(ISD::SELECT, MVT::i32, Expand);
70
71  setOperationAction(ISD::SETCC, MVT::i32, Expand);
72  setOperationAction(ISD::SETCC, MVT::f32, Expand);
73  setOperationAction(ISD::SETCC, MVT::f64, Expand);
74
75  setOperationAction(ISD::SELECT_CC, MVT::i32, Custom);
76
77  setOperationAction(ISD::MEMMOVE, MVT::Other, Expand);
78  setOperationAction(ISD::MEMSET, MVT::Other, Expand);
79  setOperationAction(ISD::MEMCPY, MVT::Other, Expand);
80
81  setOperationAction(ISD::BR_JT, MVT::Other, Expand);
82  setOperationAction(ISD::BRIND, MVT::Other, Expand);
83  setOperationAction(ISD::BR_CC, MVT::i32, Custom);
84  setOperationAction(ISD::BR_CC, MVT::f32, Custom);
85  setOperationAction(ISD::BR_CC, MVT::f64, Custom);
86
87  setOperationAction(ISD::BRCOND,        MVT::Other, Expand);
88
89  setOperationAction(ISD::SHL_PARTS, MVT::i32, Expand);
90  setOperationAction(ISD::SRA_PARTS, MVT::i32, Expand);
91  setOperationAction(ISD::SRL_PARTS, MVT::i32, Expand);
92  setOperationAction(ISD::SDIV,      MVT::i32, Expand);
93  setOperationAction(ISD::UDIV,      MVT::i32, Expand);
94  setOperationAction(ISD::SREM,      MVT::i32, Expand);
95  setOperationAction(ISD::UREM,      MVT::i32, Expand);
96
97  setOperationAction(ISD::VASTART,       MVT::Other, Custom);
98  setOperationAction(ISD::VACOPY,            MVT::Other, Expand);
99  setOperationAction(ISD::VAEND,         MVT::Other, Expand);
100  setOperationAction(ISD::DYNAMIC_STACKALLOC, MVT::i32, Expand);
101
102  setOperationAction(ISD::ConstantFP, MVT::f64, Expand);
103  setOperationAction(ISD::ConstantFP, MVT::f32, Expand);
104
105  setStackPointerRegisterToSaveRestore(ARM::R13);
106
107  setSchedulingPreference(SchedulingForRegPressure);
108  computeRegisterProperties();
109}
110
111namespace llvm {
112  namespace ARMISD {
113    enum NodeType {
114      // Start the numbering where the builting ops and target ops leave off.
115      FIRST_NUMBER = ISD::BUILTIN_OP_END+ARM::INSTRUCTION_LIST_END,
116      /// CALL - A direct function call.
117      CALL,
118
119      /// Return with a flag operand.
120      RET_FLAG,
121
122      CMP,
123
124      SELECT,
125
126      BR,
127
128      FSITOS,
129      FTOSIS,
130
131      FSITOD,
132      FTOSID,
133
134      FUITOS,
135      FTOUIS,
136
137      FUITOD,
138      FTOUID,
139
140      FMRRD,
141
142      FMDRR,
143
144      FMSTAT
145    };
146  }
147}
148
149/// DAGFPCCToARMCC - Convert a DAG fp condition code to an ARM CC
150// Unordered = !N & !Z & C & V = V
151// Ordered   =  N | Z | !C | !V = N | Z | !V
152static ARMCC::CondCodes DAGFPCCToARMCC(ISD::CondCode CC) {
153  switch (CC) {
154  default:
155    assert(0 && "Unknown fp condition code!");
156// SETOEQ = (N | Z | !V) & Z = Z                               = EQ
157  case ISD::SETEQ:
158  case ISD::SETOEQ: return ARMCC::EQ;
159// SETOGT = (N | Z | !V) & !N & !Z = !V &!N &!Z = (N = V) & !Z = GT
160  case ISD::SETGT:
161  case ISD::SETOGT: return ARMCC::GT;
162// SETOGE = (N | Z | !V) & !N = (Z | !V) & !N = !V & !N        = GE
163  case ISD::SETGE:
164  case ISD::SETOGE: return ARMCC::GE;
165// SETOLT = (N | Z | !V) & N = N                               = MI
166  case ISD::SETLT:
167  case ISD::SETOLT: return ARMCC::MI;
168// SETOLE = (N | Z | !V) & (N | Z) = N | Z = !C | Z            = LS
169  case ISD::SETLE:
170  case ISD::SETOLE: return ARMCC::LS;
171// SETONE = (N | Z | !V) & !Z = (N | !V) & Z = !V & Z = Z      = NE
172  case ISD::SETNE:
173  case ISD::SETONE: return ARMCC::NE;
174// SETO   = N | Z | !V = Z | !V = !V                           = VC
175  case ISD::SETO:   return ARMCC::VC;
176// SETUO  = V                                                  = VS
177  case ISD::SETUO:  return ARMCC::VS;
178// SETUEQ = V | Z                                              = ??
179// SETUGT = V | (!Z & !N) = !Z & !N = !Z & C                   = HI
180  case ISD::SETUGT: return ARMCC::HI;
181// SETUGE = V | !N = !N                                        = PL
182  case ISD::SETUGE: return ARMCC::PL;
183// SETULT = V | N                                              = ??
184// SETULE = V | Z | N                                          = ??
185// SETUNE = V | !Z = !Z                                        = NE
186  case ISD::SETUNE: return ARMCC::NE;
187  }
188}
189
190/// DAGIntCCToARMCC - Convert a DAG integer condition code to an ARM CC
191static ARMCC::CondCodes DAGIntCCToARMCC(ISD::CondCode CC) {
192  switch (CC) {
193  default:
194    assert(0 && "Unknown integer condition code!");
195  case ISD::SETEQ:  return ARMCC::EQ;
196  case ISD::SETNE:  return ARMCC::NE;
197  case ISD::SETLT:  return ARMCC::LT;
198  case ISD::SETLE:  return ARMCC::LE;
199  case ISD::SETGT:  return ARMCC::GT;
200  case ISD::SETGE:  return ARMCC::GE;
201  case ISD::SETULT: return ARMCC::CC;
202  case ISD::SETULE: return ARMCC::LS;
203  case ISD::SETUGT: return ARMCC::HI;
204  case ISD::SETUGE: return ARMCC::CS;
205  }
206}
207
208std::vector<unsigned> ARMTargetLowering::
209getRegClassForInlineAsmConstraint(const std::string &Constraint,
210                                  MVT::ValueType VT) const {
211  if (Constraint.size() == 1) {
212    // FIXME: handling only r regs
213    switch (Constraint[0]) {
214    default: break;  // Unknown constraint letter
215
216    case 'r':   // GENERAL_REGS
217    case 'R':   // LEGACY_REGS
218      if (VT == MVT::i32)
219        return make_vector<unsigned>(ARM::R0,  ARM::R1,  ARM::R2,  ARM::R3,
220                                     ARM::R4,  ARM::R5,  ARM::R6,  ARM::R7,
221                                     ARM::R8,  ARM::R9,  ARM::R10, ARM::R11,
222                                     ARM::R12, ARM::R13, ARM::R14, 0);
223      break;
224
225    }
226  }
227
228  return std::vector<unsigned>();
229}
230
231const char *ARMTargetLowering::getTargetNodeName(unsigned Opcode) const {
232  switch (Opcode) {
233  default: return 0;
234  case ARMISD::CALL:          return "ARMISD::CALL";
235  case ARMISD::RET_FLAG:      return "ARMISD::RET_FLAG";
236  case ARMISD::SELECT:        return "ARMISD::SELECT";
237  case ARMISD::CMP:           return "ARMISD::CMP";
238  case ARMISD::BR:            return "ARMISD::BR";
239  case ARMISD::FSITOS:        return "ARMISD::FSITOS";
240  case ARMISD::FTOSIS:        return "ARMISD::FTOSIS";
241  case ARMISD::FSITOD:        return "ARMISD::FSITOD";
242  case ARMISD::FTOSID:        return "ARMISD::FTOSID";
243  case ARMISD::FUITOS:        return "ARMISD::FUITOS";
244  case ARMISD::FTOUIS:        return "ARMISD::FTOUIS";
245  case ARMISD::FUITOD:        return "ARMISD::FUITOD";
246  case ARMISD::FTOUID:        return "ARMISD::FTOUID";
247  case ARMISD::FMRRD:         return "ARMISD::FMRRD";
248  case ARMISD::FMDRR:         return "ARMISD::FMDRR";
249  case ARMISD::FMSTAT:        return "ARMISD::FMSTAT";
250  }
251}
252
253class ArgumentLayout {
254  std::vector<bool>           is_reg;
255  std::vector<unsigned>       pos;
256  std::vector<MVT::ValueType> types;
257public:
258  ArgumentLayout(const std::vector<MVT::ValueType> &Types) {
259    types = Types;
260
261    unsigned      RegNum = 0;
262    unsigned StackOffset = 0;
263    for(std::vector<MVT::ValueType>::const_iterator I = Types.begin();
264        I != Types.end();
265        ++I) {
266      MVT::ValueType VT = *I;
267      assert(VT == MVT::i32 || VT == MVT::f32 || VT == MVT::f64);
268      unsigned     size = MVT::getSizeInBits(VT)/32;
269
270      RegNum = ((RegNum + size - 1) / size) * size;
271      if (RegNum < 4) {
272        pos.push_back(RegNum);
273        is_reg.push_back(true);
274        RegNum += size;
275      } else {
276        unsigned bytes = size * 32/8;
277        StackOffset = ((StackOffset + bytes - 1) / bytes) * bytes;
278        pos.push_back(StackOffset);
279        is_reg.push_back(false);
280        StackOffset += bytes;
281      }
282    }
283  }
284  unsigned getRegisterNum(unsigned argNum) {
285    assert(isRegister(argNum));
286    return pos[argNum];
287  }
288  unsigned getOffset(unsigned argNum) {
289    assert(isOffset(argNum));
290    return pos[argNum];
291  }
292  unsigned isRegister(unsigned argNum) {
293    assert(argNum < is_reg.size());
294    return is_reg[argNum];
295  }
296  unsigned isOffset(unsigned argNum) {
297    return !isRegister(argNum);
298  }
299  MVT::ValueType getType(unsigned argNum) {
300    assert(argNum < types.size());
301    return types[argNum];
302  }
303  unsigned getStackSize(void) {
304    int last = is_reg.size() - 1;
305    if (last < 0)
306      return 0;
307    if (isRegister(last))
308      return 0;
309    return getOffset(last) + MVT::getSizeInBits(getType(last))/8;
310  }
311  int lastRegArg(void) {
312    int size = is_reg.size();
313    int last = 0;
314    while(last < size && isRegister(last))
315      last++;
316    last--;
317    return last;
318  }
319  int lastRegNum(void) {
320    int            l = lastRegArg();
321    if (l < 0)
322      return -1;
323    unsigned       r = getRegisterNum(l);
324    MVT::ValueType t = getType(l);
325    assert(t == MVT::i32 || t == MVT::f32 || t == MVT::f64);
326    if (t == MVT::f64)
327      return r + 1;
328    return r;
329  }
330};
331
332// This transforms a ISD::CALL node into a
333// callseq_star <- ARMISD:CALL <- callseq_end
334// chain
335static SDOperand LowerCALL(SDOperand Op, SelectionDAG &DAG) {
336  SDOperand Chain    = Op.getOperand(0);
337  unsigned CallConv  = cast<ConstantSDNode>(Op.getOperand(1))->getValue();
338  assert((CallConv == CallingConv::C ||
339          CallConv == CallingConv::Fast)
340         && "unknown calling convention");
341  SDOperand Callee   = Op.getOperand(4);
342  unsigned NumOps    = (Op.getNumOperands() - 5) / 2;
343  SDOperand StackPtr = DAG.getRegister(ARM::R13, MVT::i32);
344  static const unsigned regs[] = {
345    ARM::R0, ARM::R1, ARM::R2, ARM::R3
346  };
347
348  std::vector<MVT::ValueType> Types;
349  for (unsigned i = 0; i < NumOps; ++i) {
350    MVT::ValueType VT = Op.getOperand(5+2*i).getValueType();
351    Types.push_back(VT);
352  }
353  ArgumentLayout Layout(Types);
354
355  unsigned NumBytes = Layout.getStackSize();
356
357  Chain = DAG.getCALLSEQ_START(Chain,
358                               DAG.getConstant(NumBytes, MVT::i32));
359
360  //Build a sequence of stores
361  std::vector<SDOperand> MemOpChains;
362  for (unsigned i = Layout.lastRegArg() + 1; i < NumOps; ++i) {
363    SDOperand      Arg = Op.getOperand(5+2*i);
364    unsigned ArgOffset = Layout.getOffset(i);
365    SDOperand   PtrOff = DAG.getConstant(ArgOffset, StackPtr.getValueType());
366    PtrOff             = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff);
367    MemOpChains.push_back(DAG.getStore(Chain, Arg, PtrOff, NULL, 0));
368  }
369  if (!MemOpChains.empty())
370    Chain = DAG.getNode(ISD::TokenFactor, MVT::Other,
371                        &MemOpChains[0], MemOpChains.size());
372
373  // If the callee is a GlobalAddress node (quite common, every direct call is)
374  // turn it into a TargetGlobalAddress node so that legalize doesn't hack it.
375  // Likewise ExternalSymbol -> TargetExternalSymbol.
376  assert(Callee.getValueType() == MVT::i32);
377  if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(Callee))
378    Callee = DAG.getTargetGlobalAddress(G->getGlobal(), MVT::i32);
379  else if (ExternalSymbolSDNode *E = dyn_cast<ExternalSymbolSDNode>(Callee))
380    Callee = DAG.getTargetExternalSymbol(E->getSymbol(), MVT::i32);
381
382  // If this is a direct call, pass the chain and the callee.
383  assert (Callee.Val);
384  std::vector<SDOperand> Ops;
385  Ops.push_back(Chain);
386  Ops.push_back(Callee);
387
388  // Build a sequence of copy-to-reg nodes chained together with token chain
389  // and flag operands which copy the outgoing args into the appropriate regs.
390  SDOperand InFlag;
391  for (int i = 0, e = Layout.lastRegArg(); i <= e; ++i) {
392    SDOperand     Arg = Op.getOperand(5+2*i);
393    unsigned   RegNum = Layout.getRegisterNum(i);
394    unsigned     Reg1 = regs[RegNum];
395    MVT::ValueType VT = Layout.getType(i);
396    assert(VT == Arg.getValueType());
397    assert(VT == MVT::i32 || VT == MVT::f32 || VT == MVT::f64);
398
399    // Add argument register to the end of the list so that it is known live
400    // into the call.
401    Ops.push_back(DAG.getRegister(Reg1, MVT::i32));
402    if (VT == MVT::f64) {
403      unsigned    Reg2 = regs[RegNum + 1];
404      SDOperand SDReg1 = DAG.getRegister(Reg1, MVT::i32);
405      SDOperand SDReg2 = DAG.getRegister(Reg2, MVT::i32);
406
407      Ops.push_back(DAG.getRegister(Reg2, MVT::i32));
408      SDVTList    VTs = DAG.getVTList(MVT::Other, MVT::Flag);
409      SDOperand Ops[] = {Chain, SDReg1, SDReg2, Arg, InFlag};
410      Chain = DAG.getNode(ARMISD::FMRRD, VTs, Ops, InFlag.Val ? 5 : 4);
411    } else {
412      if (VT == MVT::f32)
413        Arg = DAG.getNode(ISD::BIT_CONVERT, MVT::i32, Arg);
414      Chain = DAG.getCopyToReg(Chain, Reg1, Arg, InFlag);
415    }
416    InFlag = Chain.getValue(1);
417  }
418
419  std::vector<MVT::ValueType> NodeTys;
420  NodeTys.push_back(MVT::Other);   // Returns a chain
421  NodeTys.push_back(MVT::Flag);    // Returns a flag for retval copy to use.
422
423  unsigned CallOpc = ARMISD::CALL;
424  if (InFlag.Val)
425    Ops.push_back(InFlag);
426  Chain = DAG.getNode(CallOpc, NodeTys, &Ops[0], Ops.size());
427  InFlag = Chain.getValue(1);
428
429  std::vector<SDOperand> ResultVals;
430  NodeTys.clear();
431
432  // If the call has results, copy the values out of the ret val registers.
433  MVT::ValueType VT = Op.Val->getValueType(0);
434  if (VT != MVT::Other) {
435    assert(VT == MVT::i32 || VT == MVT::f32 || VT == MVT::f64);
436
437    SDOperand Value1 = DAG.getCopyFromReg(Chain, ARM::R0, MVT::i32, InFlag);
438    Chain            = Value1.getValue(1);
439    InFlag           = Value1.getValue(2);
440    NodeTys.push_back(VT);
441    if (VT == MVT::i32) {
442      ResultVals.push_back(Value1);
443      if (Op.Val->getValueType(1) == MVT::i32) {
444        SDOperand Value2 = DAG.getCopyFromReg(Chain, ARM::R1, MVT::i32, InFlag);
445        Chain            = Value2.getValue(1);
446        ResultVals.push_back(Value2);
447        NodeTys.push_back(VT);
448      }
449    }
450    if (VT == MVT::f32) {
451      SDOperand Value = DAG.getNode(ISD::BIT_CONVERT, MVT::f32, Value1);
452      ResultVals.push_back(Value);
453    }
454    if (VT == MVT::f64) {
455      SDOperand Value2 = DAG.getCopyFromReg(Chain, ARM::R1, MVT::i32, InFlag);
456      Chain            = Value2.getValue(1);
457      SDOperand Value  = DAG.getNode(ARMISD::FMDRR, MVT::f64, Value1, Value2);
458      ResultVals.push_back(Value);
459    }
460  }
461
462  Chain = DAG.getNode(ISD::CALLSEQ_END, MVT::Other, Chain,
463                      DAG.getConstant(NumBytes, MVT::i32));
464  NodeTys.push_back(MVT::Other);
465
466  if (ResultVals.empty())
467    return Chain;
468
469  ResultVals.push_back(Chain);
470  SDOperand Res = DAG.getNode(ISD::MERGE_VALUES, NodeTys, &ResultVals[0],
471                              ResultVals.size());
472  return Res.getValue(Op.ResNo);
473}
474
475static SDOperand LowerRET(SDOperand Op, SelectionDAG &DAG) {
476  SDOperand Copy;
477  SDOperand Chain = Op.getOperand(0);
478  SDOperand    R0 = DAG.getRegister(ARM::R0, MVT::i32);
479  SDOperand    R1 = DAG.getRegister(ARM::R1, MVT::i32);
480
481  switch(Op.getNumOperands()) {
482  default:
483    assert(0 && "Do not know how to return this many arguments!");
484    abort();
485  case 1: {
486    SDOperand LR = DAG.getRegister(ARM::R14, MVT::i32);
487    return DAG.getNode(ARMISD::RET_FLAG, MVT::Other, Chain);
488  }
489  case 3: {
490    SDOperand Val = Op.getOperand(1);
491    assert(Val.getValueType() == MVT::i32 ||
492	   Val.getValueType() == MVT::f32 ||
493	   Val.getValueType() == MVT::f64);
494
495    if (Val.getValueType() == MVT::f64) {
496      SDVTList    VTs = DAG.getVTList(MVT::Other, MVT::Flag);
497      SDOperand Ops[] = {Chain, R0, R1, Val};
498      Copy  = DAG.getNode(ARMISD::FMRRD, VTs, Ops, 4);
499    } else {
500      if (Val.getValueType() == MVT::f32)
501	Val = DAG.getNode(ISD::BIT_CONVERT, MVT::i32, Val);
502      Copy = DAG.getCopyToReg(Chain, R0, Val, SDOperand());
503    }
504
505    if (DAG.getMachineFunction().liveout_empty()) {
506      DAG.getMachineFunction().addLiveOut(ARM::R0);
507      if (Val.getValueType() == MVT::f64)
508        DAG.getMachineFunction().addLiveOut(ARM::R1);
509    }
510    break;
511  }
512  case 5:
513    Copy = DAG.getCopyToReg(Chain, ARM::R1, Op.getOperand(3), SDOperand());
514    Copy = DAG.getCopyToReg(Copy, ARM::R0, Op.getOperand(1), Copy.getValue(1));
515    // If we haven't noted the R0+R1 are live out, do so now.
516    if (DAG.getMachineFunction().liveout_empty()) {
517      DAG.getMachineFunction().addLiveOut(ARM::R0);
518      DAG.getMachineFunction().addLiveOut(ARM::R1);
519    }
520    break;
521  }
522
523  //We must use RET_FLAG instead of BRIND because BRIND doesn't have a flag
524  return DAG.getNode(ARMISD::RET_FLAG, MVT::Other, Copy, Copy.getValue(1));
525}
526
527static SDOperand LowerConstantPool(SDOperand Op, SelectionDAG &DAG) {
528  MVT::ValueType PtrVT = Op.getValueType();
529  ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(Op);
530  Constant *C = CP->getConstVal();
531  SDOperand CPI = DAG.getTargetConstantPool(C, PtrVT, CP->getAlignment());
532
533  return CPI;
534}
535
536static SDOperand LowerGlobalAddress(SDOperand Op,
537				    SelectionDAG &DAG) {
538  GlobalValue  *GV = cast<GlobalAddressSDNode>(Op)->getGlobal();
539  int alignment = 2;
540  SDOperand CPAddr = DAG.getConstantPool(GV, MVT::i32, alignment);
541  return DAG.getLoad(MVT::i32, DAG.getEntryNode(), CPAddr, NULL, 0);
542}
543
544static SDOperand LowerVASTART(SDOperand Op, SelectionDAG &DAG,
545                              unsigned VarArgsFrameIndex) {
546  // vastart just stores the address of the VarArgsFrameIndex slot into the
547  // memory location argument.
548  MVT::ValueType PtrVT = DAG.getTargetLoweringInfo().getPointerTy();
549  SDOperand FR = DAG.getFrameIndex(VarArgsFrameIndex, PtrVT);
550  SrcValueSDNode *SV = cast<SrcValueSDNode>(Op.getOperand(2));
551  return DAG.getStore(Op.getOperand(0), FR, Op.getOperand(1), SV->getValue(),
552                      SV->getOffset());
553}
554
555static SDOperand LowerFORMAL_ARGUMENTS(SDOperand Op, SelectionDAG &DAG,
556				       int &VarArgsFrameIndex) {
557  MachineFunction   &MF = DAG.getMachineFunction();
558  MachineFrameInfo *MFI = MF.getFrameInfo();
559  SSARegMap     *RegMap = MF.getSSARegMap();
560  unsigned      NumArgs = Op.Val->getNumValues()-1;
561  SDOperand        Root = Op.getOperand(0);
562  bool         isVarArg = cast<ConstantSDNode>(Op.getOperand(2))->getValue() != 0;
563  static const unsigned REGS[] = {
564    ARM::R0, ARM::R1, ARM::R2, ARM::R3
565  };
566
567  std::vector<MVT::ValueType> Types(Op.Val->value_begin(), Op.Val->value_end() - 1);
568  ArgumentLayout Layout(Types);
569
570  std::vector<SDOperand> ArgValues;
571  for (unsigned ArgNo = 0; ArgNo < NumArgs; ++ArgNo) {
572    MVT::ValueType VT = Types[ArgNo];
573
574    SDOperand Value;
575    if (Layout.isRegister(ArgNo)) {
576      assert(VT == MVT::i32 || VT == MVT::f32 || VT == MVT::f64);
577      unsigned  RegNum = Layout.getRegisterNum(ArgNo);
578      unsigned    Reg1 = REGS[RegNum];
579      unsigned   VReg1 = RegMap->createVirtualRegister(&ARM::IntRegsRegClass);
580      SDOperand Value1 = DAG.getCopyFromReg(Root, VReg1, MVT::i32);
581      MF.addLiveIn(Reg1, VReg1);
582      if (VT == MVT::f64) {
583        unsigned    Reg2 = REGS[RegNum + 1];
584        unsigned   VReg2 = RegMap->createVirtualRegister(&ARM::IntRegsRegClass);
585        SDOperand Value2 = DAG.getCopyFromReg(Root, VReg2, MVT::i32);
586        MF.addLiveIn(Reg2, VReg2);
587        Value            = DAG.getNode(ARMISD::FMDRR, MVT::f64, Value1, Value2);
588      } else {
589        Value = Value1;
590        if (VT == MVT::f32)
591          Value = DAG.getNode(ISD::BIT_CONVERT, VT, Value);
592      }
593    } else {
594      // If the argument is actually used, emit a load from the right stack
595      // slot.
596      if (!Op.Val->hasNUsesOfValue(0, ArgNo)) {
597        unsigned Offset = Layout.getOffset(ArgNo);
598        unsigned   Size = MVT::getSizeInBits(VT)/8;
599        int          FI = MFI->CreateFixedObject(Size, Offset);
600        SDOperand   FIN = DAG.getFrameIndex(FI, VT);
601        Value = DAG.getLoad(VT, Root, FIN, NULL, 0);
602      } else {
603        Value = DAG.getNode(ISD::UNDEF, VT);
604      }
605    }
606    ArgValues.push_back(Value);
607  }
608
609  unsigned NextRegNum = Layout.lastRegNum() + 1;
610
611  if (isVarArg) {
612    //If this function is vararg we must store the remaing
613    //registers so that they can be acessed with va_start
614    VarArgsFrameIndex = MFI->CreateFixedObject(MVT::getSizeInBits(MVT::i32)/8,
615                                               -16 + NextRegNum * 4);
616
617    SmallVector<SDOperand, 4> MemOps;
618    for (unsigned RegNo = NextRegNum; RegNo < 4; ++RegNo) {
619      int RegOffset = - (4 - RegNo) * 4;
620      int FI = MFI->CreateFixedObject(MVT::getSizeInBits(MVT::i32)/8,
621				      RegOffset);
622      SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
623
624      unsigned VReg = RegMap->createVirtualRegister(&ARM::IntRegsRegClass);
625      MF.addLiveIn(REGS[RegNo], VReg);
626
627      SDOperand Val = DAG.getCopyFromReg(Root, VReg, MVT::i32);
628      SDOperand Store = DAG.getStore(Val.getValue(1), Val, FIN, NULL, 0);
629      MemOps.push_back(Store);
630    }
631    Root = DAG.getNode(ISD::TokenFactor, MVT::Other,&MemOps[0],MemOps.size());
632  }
633
634  ArgValues.push_back(Root);
635
636  // Return the new list of results.
637  std::vector<MVT::ValueType> RetVT(Op.Val->value_begin(),
638                                    Op.Val->value_end());
639  return DAG.getNode(ISD::MERGE_VALUES, RetVT, &ArgValues[0], ArgValues.size());
640}
641
642static SDOperand GetCMP(ISD::CondCode CC, SDOperand LHS, SDOperand RHS,
643                        SelectionDAG &DAG) {
644  MVT::ValueType vt = LHS.getValueType();
645  assert(vt == MVT::i32 || vt == MVT::f32 || vt == MVT::f64);
646
647  SDOperand Cmp = DAG.getNode(ARMISD::CMP,  MVT::Flag, LHS, RHS);
648
649  if (vt != MVT::i32)
650    Cmp = DAG.getNode(ARMISD::FMSTAT, MVT::Flag, Cmp);
651  return Cmp;
652}
653
654static SDOperand GetARMCC(ISD::CondCode CC, MVT::ValueType vt,
655                          SelectionDAG &DAG) {
656  assert(vt == MVT::i32 || vt == MVT::f32 || vt == MVT::f64);
657  if (vt == MVT::i32)
658    return DAG.getConstant(DAGIntCCToARMCC(CC), MVT::i32);
659  else
660    return DAG.getConstant(DAGFPCCToARMCC(CC), MVT::i32);
661}
662
663static SDOperand LowerSELECT_CC(SDOperand Op, SelectionDAG &DAG) {
664  SDOperand LHS = Op.getOperand(0);
665  SDOperand RHS = Op.getOperand(1);
666  ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(4))->get();
667  SDOperand TrueVal = Op.getOperand(2);
668  SDOperand FalseVal = Op.getOperand(3);
669  SDOperand      Cmp = GetCMP(CC, LHS, RHS, DAG);
670  SDOperand    ARMCC = GetARMCC(CC, LHS.getValueType(), DAG);
671  return DAG.getNode(ARMISD::SELECT, MVT::i32, TrueVal, FalseVal, ARMCC, Cmp);
672}
673
674static SDOperand LowerBR_CC(SDOperand Op, SelectionDAG &DAG) {
675  SDOperand  Chain = Op.getOperand(0);
676  ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(1))->get();
677  SDOperand    LHS = Op.getOperand(2);
678  SDOperand    RHS = Op.getOperand(3);
679  SDOperand   Dest = Op.getOperand(4);
680  SDOperand    Cmp = GetCMP(CC, LHS, RHS, DAG);
681  SDOperand  ARMCC = GetARMCC(CC, LHS.getValueType(), DAG);
682  return DAG.getNode(ARMISD::BR, MVT::Other, Chain, Dest, ARMCC, Cmp);
683}
684
685static SDOperand LowerSINT_TO_FP(SDOperand Op, SelectionDAG &DAG) {
686  SDOperand IntVal  = Op.getOperand(0);
687  assert(IntVal.getValueType() == MVT::i32);
688  MVT::ValueType vt = Op.getValueType();
689  assert(vt == MVT::f32 ||
690         vt == MVT::f64);
691
692  SDOperand Tmp = DAG.getNode(ISD::BIT_CONVERT, MVT::f32, IntVal);
693  ARMISD::NodeType op = vt == MVT::f32 ? ARMISD::FSITOS : ARMISD::FSITOD;
694  return DAG.getNode(op, vt, Tmp);
695}
696
697static SDOperand LowerFP_TO_SINT(SDOperand Op, SelectionDAG &DAG) {
698  assert(Op.getValueType() == MVT::i32);
699  SDOperand FloatVal = Op.getOperand(0);
700  MVT::ValueType  vt = FloatVal.getValueType();
701  assert(vt == MVT::f32 || vt == MVT::f64);
702
703  ARMISD::NodeType op = vt == MVT::f32 ? ARMISD::FTOSIS : ARMISD::FTOSID;
704  SDOperand Tmp = DAG.getNode(op, MVT::f32, FloatVal);
705  return DAG.getNode(ISD::BIT_CONVERT, MVT::i32, Tmp);
706}
707
708static SDOperand LowerUINT_TO_FP(SDOperand Op, SelectionDAG &DAG) {
709  SDOperand IntVal  = Op.getOperand(0);
710  assert(IntVal.getValueType() == MVT::i32);
711  MVT::ValueType vt = Op.getValueType();
712  assert(vt == MVT::f32 ||
713         vt == MVT::f64);
714
715  SDOperand Tmp = DAG.getNode(ISD::BIT_CONVERT, MVT::f32, IntVal);
716  ARMISD::NodeType op = vt == MVT::f32 ? ARMISD::FUITOS : ARMISD::FUITOD;
717  return DAG.getNode(op, vt, Tmp);
718}
719
720static SDOperand LowerFP_TO_UINT(SDOperand Op, SelectionDAG &DAG) {
721  assert(Op.getValueType() == MVT::i32);
722  SDOperand FloatVal = Op.getOperand(0);
723  MVT::ValueType  vt = FloatVal.getValueType();
724  assert(vt == MVT::f32 || vt == MVT::f64);
725
726  ARMISD::NodeType op = vt == MVT::f32 ? ARMISD::FTOUIS : ARMISD::FTOUID;
727  SDOperand Tmp = DAG.getNode(op, MVT::f32, FloatVal);
728  return DAG.getNode(ISD::BIT_CONVERT, MVT::i32, Tmp);
729}
730
731SDOperand ARMTargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
732  switch (Op.getOpcode()) {
733  default:
734    assert(0 && "Should not custom lower this!");
735    abort();
736  case ISD::ConstantPool:
737    return LowerConstantPool(Op, DAG);
738  case ISD::GlobalAddress:
739    return LowerGlobalAddress(Op, DAG);
740  case ISD::FP_TO_SINT:
741    return LowerFP_TO_SINT(Op, DAG);
742  case ISD::SINT_TO_FP:
743    return LowerSINT_TO_FP(Op, DAG);
744  case ISD::FP_TO_UINT:
745    return LowerFP_TO_UINT(Op, DAG);
746  case ISD::UINT_TO_FP:
747    return LowerUINT_TO_FP(Op, DAG);
748  case ISD::FORMAL_ARGUMENTS:
749    return LowerFORMAL_ARGUMENTS(Op, DAG, VarArgsFrameIndex);
750  case ISD::CALL:
751    return LowerCALL(Op, DAG);
752  case ISD::RET:
753    return LowerRET(Op, DAG);
754  case ISD::SELECT_CC:
755    return LowerSELECT_CC(Op, DAG);
756  case ISD::BR_CC:
757    return LowerBR_CC(Op, DAG);
758  case ISD::VASTART:
759    return LowerVASTART(Op, DAG, VarArgsFrameIndex);
760  }
761}
762
763//===----------------------------------------------------------------------===//
764// Instruction Selector Implementation
765//===----------------------------------------------------------------------===//
766
767//===--------------------------------------------------------------------===//
768/// ARMDAGToDAGISel - ARM specific code to select ARM machine
769/// instructions for SelectionDAG operations.
770///
771namespace {
772class ARMDAGToDAGISel : public SelectionDAGISel {
773  ARMTargetLowering Lowering;
774
775public:
776  ARMDAGToDAGISel(TargetMachine &TM)
777    : SelectionDAGISel(Lowering), Lowering(TM) {
778  }
779
780  SDNode *Select(SDOperand Op);
781  virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
782  bool SelectAddrMode1(SDOperand Op, SDOperand N, SDOperand &Arg,
783                       SDOperand &Shift, SDOperand &ShiftType);
784  bool SelectAddrMode2(SDOperand Op, SDOperand N, SDOperand &Arg,
785                       SDOperand &Offset);
786  bool SelectAddrMode5(SDOperand Op, SDOperand N, SDOperand &Arg,
787                       SDOperand &Offset);
788
789  // Include the pieces autogenerated from the target description.
790#include "ARMGenDAGISel.inc"
791};
792
793void ARMDAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
794  DEBUG(BB->dump());
795
796  DAG.setRoot(SelectRoot(DAG.getRoot()));
797  DAG.RemoveDeadNodes();
798
799  ScheduleAndEmitDAG(DAG);
800}
801
802static bool isInt12Immediate(SDNode *N, short &Imm) {
803  if (N->getOpcode() != ISD::Constant)
804    return false;
805
806  int32_t t = cast<ConstantSDNode>(N)->getValue();
807  int max = 1<<12;
808  int min = -max;
809  if (t > min && t < max) {
810    Imm = t;
811    return true;
812  }
813  else
814    return false;
815}
816
817static bool isInt12Immediate(SDOperand Op, short &Imm) {
818  return isInt12Immediate(Op.Val, Imm);
819}
820
821static uint32_t rotateL(uint32_t x) {
822  uint32_t bit31 = (x & (1 << 31)) >> 31;
823  uint32_t     t = x << 1;
824  return t | bit31;
825}
826
827static bool isUInt8Immediate(uint32_t x) {
828  return x < (1 << 8);
829}
830
831static bool isRotInt8Immediate(uint32_t x) {
832  int r;
833  for (r = 0; r < 16; r++) {
834    if (isUInt8Immediate(x))
835      return true;
836    x = rotateL(rotateL(x));
837  }
838  return false;
839}
840
841bool ARMDAGToDAGISel::SelectAddrMode1(SDOperand Op,
842                                      SDOperand N,
843				      SDOperand &Arg,
844				      SDOperand &Shift,
845				      SDOperand &ShiftType) {
846  switch(N.getOpcode()) {
847  case ISD::Constant: {
848    uint32_t val = cast<ConstantSDNode>(N)->getValue();
849    if(!isRotInt8Immediate(val)) {
850      Constant    *C = ConstantInt::get(Type::UIntTy, val);
851      int  alignment = 2;
852      SDOperand Addr = CurDAG->getTargetConstantPool(C, MVT::i32, alignment);
853      SDOperand    Z = CurDAG->getTargetConstant(0,     MVT::i32);
854      SDNode      *n = CurDAG->getTargetNode(ARM::LDR,  MVT::i32, Addr, Z);
855      Arg            = SDOperand(n, 0);
856    } else
857      Arg            = CurDAG->getTargetConstant(val,    MVT::i32);
858
859    Shift     = CurDAG->getTargetConstant(0,             MVT::i32);
860    ShiftType = CurDAG->getTargetConstant(ARMShift::LSL, MVT::i32);
861    return true;
862  }
863  case ISD::SRA:
864    Arg       = N.getOperand(0);
865    Shift     = N.getOperand(1);
866    ShiftType = CurDAG->getTargetConstant(ARMShift::ASR, MVT::i32);
867    return true;
868  case ISD::SRL:
869    Arg       = N.getOperand(0);
870    Shift     = N.getOperand(1);
871    ShiftType = CurDAG->getTargetConstant(ARMShift::LSR, MVT::i32);
872    return true;
873  case ISD::SHL:
874    Arg       = N.getOperand(0);
875    Shift     = N.getOperand(1);
876    ShiftType = CurDAG->getTargetConstant(ARMShift::LSL, MVT::i32);
877    return true;
878  }
879
880  Arg       = N;
881  Shift     = CurDAG->getTargetConstant(0, MVT::i32);
882  ShiftType = CurDAG->getTargetConstant(ARMShift::LSL, MVT::i32);
883  return true;
884}
885
886bool ARMDAGToDAGISel::SelectAddrMode2(SDOperand Op, SDOperand N,
887                                      SDOperand &Arg, SDOperand &Offset) {
888  //TODO: complete and cleanup!
889  SDOperand Zero = CurDAG->getTargetConstant(0, MVT::i32);
890  if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(N)) {
891    Arg    = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i32);
892    Offset = Zero;
893    return true;
894  }
895  if (N.getOpcode() == ISD::ADD) {
896    short imm = 0;
897    if (isInt12Immediate(N.getOperand(1), imm)) {
898      Offset = CurDAG->getTargetConstant(imm, MVT::i32);
899      if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N.getOperand(0))) {
900	Arg = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
901      } else {
902	Arg = N.getOperand(0);
903      }
904      return true; // [r+i]
905    }
906  }
907  Offset = Zero;
908  if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N))
909    Arg = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
910  else
911    Arg = N;
912  return true;
913}
914
915bool ARMDAGToDAGISel::SelectAddrMode5(SDOperand Op,
916                                      SDOperand N, SDOperand &Arg,
917                                      SDOperand &Offset) {
918  //TODO: detect offset
919  Offset = CurDAG->getTargetConstant(0, MVT::i32);
920  Arg    = N;
921  return true;
922}
923
924SDNode *ARMDAGToDAGISel::Select(SDOperand Op) {
925  SDNode *N = Op.Val;
926
927  switch (N->getOpcode()) {
928  default:
929    return SelectCode(Op);
930    break;
931  case ISD::FrameIndex: {
932    int FI = cast<FrameIndexSDNode>(N)->getIndex();
933    SDOperand Ops[] = {CurDAG->getTargetFrameIndex(FI, MVT::i32),
934                       CurDAG->getTargetConstant(0, MVT::i32),
935                       CurDAG->getTargetConstant(0, MVT::i32),
936                       CurDAG->getTargetConstant(ARMShift::LSL, MVT::i32)};
937
938    return CurDAG->SelectNodeTo(N, ARM::ADD, MVT::i32, Ops,
939                                sizeof(Ops)/sizeof(SDOperand));
940    break;
941  }
942  }
943}
944
945}  // end anonymous namespace
946
947/// createARMISelDag - This pass converts a legalized DAG into a
948/// ARM-specific DAG, ready for instruction scheduling.
949///
950FunctionPass *llvm::createARMISelDag(TargetMachine &TM) {
951  return new ARMDAGToDAGISel(TM);
952}
953