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