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