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