lib/Target/ARM/ARMISelDAGToDAG.cpp

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