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   bool isVarArg      = cast<ConstantSDNode>(Op.getOperand(2))->getValue() != 0;
 314   bool isTailCall    = cast<ConstantSDNode>(Op.getOperand(3))->getValue() != 0;
 315   SDOperand Callee   = Op.getOperand(4);
 316   unsigned NumOps    = (Op.getNumOperands() - 5) / 2;
 317   SDOperand StackPtr = DAG.getRegister(ARM::R13, MVT::i32);
 318   static const unsigned regs[] = {
 319     ARM::R0, ARM::R1, ARM::R2, ARM::R3
 320   };
 321
 322   std::vector<MVT::ValueType> Types;
 323   for (unsigned i = 0; i < NumOps; ++i) {
 324     MVT::ValueType VT = Op.getOperand(5+2*i).getValueType();
 325     Types.push_back(VT);
 326   }
 327   ArgumentLayout Layout(Types);
 328
 329   unsigned NumBytes = Layout.getStackSize();
 330
 331   Chain = DAG.getCALLSEQ_START(Chain,
 332                                DAG.getConstant(NumBytes, MVT::i32));
 333
 334   //Build a sequence of stores
 335   std::vector<SDOperand> MemOpChains;
 336   for (unsigned i = Layout.lastRegArg() + 1; i < NumOps; ++i) {
 337     SDOperand      Arg = Op.getOperand(5+2*i);
 338     unsigned ArgOffset = Layout.getOffset(i);
 339     SDOperand   PtrOff = DAG.getConstant(ArgOffset, StackPtr.getValueType());
 340     PtrOff             = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff);
 341     MemOpChains.push_back(DAG.getStore(Chain, Arg, PtrOff, NULL, 0));
 342   }
 343   if (!MemOpChains.empty())
 344     Chain = DAG.getNode(ISD::TokenFactor, MVT::Other,
 345                         &MemOpChains[0], MemOpChains.size());
 346
 347   // If the callee is a GlobalAddress node (quite common, every direct call is)
 348   // turn it into a TargetGlobalAddress node so that legalize doesn't hack it.
 349   // Likewise ExternalSymbol -> TargetExternalSymbol.
 350   assert(Callee.getValueType() == MVT::i32);
 351   if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(Callee))
 352     Callee = DAG.getTargetGlobalAddress(G->getGlobal(), MVT::i32);
 353   else if (ExternalSymbolSDNode *E = dyn_cast<ExternalSymbolSDNode>(Callee))
 354     Callee = DAG.getTargetExternalSymbol(E->getSymbol(), MVT::i32);
 355
 356   // If this is a direct call, pass the chain and the callee.
 357   assert (Callee.Val);
 358   std::vector<SDOperand> Ops;
 359   Ops.push_back(Chain);
 360   Ops.push_back(Callee);
 361
 362   // Build a sequence of copy-to-reg nodes chained together with token chain
 363   // and flag operands which copy the outgoing args into the appropriate regs.
 364   SDOperand InFlag;
 365   for (int i = 0, e = Layout.lastRegArg(); i <= e; ++i) {
 366     SDOperand     Arg = Op.getOperand(5+2*i);
 367     unsigned   RegNum = Layout.getRegisterNum(i);
 368     unsigned     Reg1 = regs[RegNum];
 369     MVT::ValueType VT = Layout.getType(i);
 370     assert(VT == Arg.getValueType());
 371     assert(VT == MVT::i32 || VT == MVT::f32 || VT == MVT::f64);
 372
 373     // Add argument register to the end of the list so that it is known live
 374     // into the call.
 375     Ops.push_back(DAG.getRegister(Reg1, MVT::i32));
 376     if (VT == MVT::f64) {
 377       unsigned    Reg2 = regs[RegNum + 1];
 378       SDOperand SDReg1 = DAG.getRegister(Reg1, MVT::i32);
 379       SDOperand SDReg2 = DAG.getRegister(Reg2, MVT::i32);
 380
 381       Ops.push_back(DAG.getRegister(Reg2, MVT::i32));
 382       SDVTList    VTs = DAG.getVTList(MVT::Other, MVT::Flag);
 383       SDOperand Ops[] = {Chain, SDReg1, SDReg2, Arg, InFlag};
 384       Chain = DAG.getNode(ARMISD::FMRRD, VTs, Ops, InFlag.Val ? 5 : 4);
 385     } else {
 386       if (VT == MVT::f32)
 387         Arg = DAG.getNode(ISD::BIT_CONVERT, MVT::i32, Arg);
 388       Chain = DAG.getCopyToReg(Chain, Reg1, Arg, InFlag);
 389     }
 390     InFlag = Chain.getValue(1);
 391   }
 392
 393   std::vector<MVT::ValueType> NodeTys;
 394   NodeTys.push_back(MVT::Other);   // Returns a chain
 395   NodeTys.push_back(MVT::Flag);    // Returns a flag for retval copy to use.
 396
 397   unsigned CallOpc = ARMISD::CALL;
 398   if (InFlag.Val)
 399     Ops.push_back(InFlag);
 400   Chain = DAG.getNode(CallOpc, NodeTys, &Ops[0], Ops.size());
 401   InFlag = Chain.getValue(1);
 402
 403   std::vector<SDOperand> ResultVals;
 404   NodeTys.clear();
 405
 406   // If the call has results, copy the values out of the ret val registers.
 407   MVT::ValueType VT = Op.Val->getValueType(0);
 408   if (VT != MVT::Other) {
 409     assert(VT == MVT::i32 || VT == MVT::f32 || VT == MVT::f64);
 410
 411     SDOperand Value1 = DAG.getCopyFromReg(Chain, ARM::R0, MVT::i32, InFlag);
 412     Chain            = Value1.getValue(1);
 413     InFlag           = Value1.getValue(2);
 414     NodeTys.push_back(VT);
 415     if (VT == MVT::i32) {
 416       ResultVals.push_back(Value1);
 417       if (Op.Val->getValueType(1) == MVT::i32) {
 418         SDOperand Value2 = DAG.getCopyFromReg(Chain, ARM::R1, MVT::i32, InFlag);
 419         Chain            = Value2.getValue(1);
 420         ResultVals.push_back(Value2);
 421         NodeTys.push_back(VT);
 422       }
 423     }
 424     if (VT == MVT::f32) {
 425       SDOperand Value = DAG.getNode(ISD::BIT_CONVERT, MVT::f32, Value1);
 426       ResultVals.push_back(Value);
 427     }
 428     if (VT == MVT::f64) {
 429       SDOperand Value2 = DAG.getCopyFromReg(Chain, ARM::R1, MVT::i32, InFlag);
 430       Chain            = Value2.getValue(1);
 431       SDOperand Value  = DAG.getNode(ARMISD::FMDRR, MVT::f64, Value1, Value2);
 432       ResultVals.push_back(Value);
 433     }
 434   }
 435
 436   Chain = DAG.getNode(ISD::CALLSEQ_END, MVT::Other, Chain,
 437                       DAG.getConstant(NumBytes, MVT::i32));
 438   NodeTys.push_back(MVT::Other);
 439
 440   if (ResultVals.empty())
 441     return Chain;
 442
 443   ResultVals.push_back(Chain);
 444   SDOperand Res = DAG.getNode(ISD::MERGE_VALUES, NodeTys, &ResultVals[0],
 445                               ResultVals.size());
 446   return Res.getValue(Op.ResNo);
 447 }
 448
 449 static SDOperand LowerRET(SDOperand Op, SelectionDAG &DAG) {
 450   SDOperand Copy;
 451   SDOperand Chain = Op.getOperand(0);
 452   SDOperand    R0 = DAG.getRegister(ARM::R0, MVT::i32);
 453   SDOperand    R1 = DAG.getRegister(ARM::R1, MVT::i32);
 454
 455   switch(Op.getNumOperands()) {
 456   default:
 457     assert(0 && "Do not know how to return this many arguments!");
 458     abort();
 459   case 1: {
 460     SDOperand LR = DAG.getRegister(ARM::R14, MVT::i32);
 461     return DAG.getNode(ARMISD::RET_FLAG, MVT::Other, Chain);
 462   }
 463   case 3: {
 464     SDOperand Val = Op.getOperand(1);
 465     assert(Val.getValueType() == MVT::i32 ||
 466            Val.getValueType() == MVT::f32 ||
 467            Val.getValueType() == MVT::f64);
 468
 469     if (Val.getValueType() == MVT::f64) {
 470       SDVTList    VTs = DAG.getVTList(MVT::Other, MVT::Flag);
 471       SDOperand Ops[] = {Chain, R0, R1, Val};
 472       Copy  = DAG.getNode(ARMISD::FMRRD, VTs, Ops, 4);
 473     } else {
 474       if (Val.getValueType() == MVT::f32)
 475         Val = DAG.getNode(ISD::BIT_CONVERT, MVT::i32, Val);
 476       Copy = DAG.getCopyToReg(Chain, R0, Val, SDOperand());
 477     }
 478
 479     if (DAG.getMachineFunction().liveout_empty()) {
 480       DAG.getMachineFunction().addLiveOut(ARM::R0);
 481       if (Val.getValueType() == MVT::f64)
 482         DAG.getMachineFunction().addLiveOut(ARM::R1);
 483     }
 484     break;
 485   }
 486   case 5:
 487     Copy = DAG.getCopyToReg(Chain, ARM::R1, Op.getOperand(3), SDOperand());
 488     Copy = DAG.getCopyToReg(Copy, ARM::R0, Op.getOperand(1), Copy.getValue(1));
 489     // If we haven't noted the R0+R1 are live out, do so now.
 490     if (DAG.getMachineFunction().liveout_empty()) {
 491       DAG.getMachineFunction().addLiveOut(ARM::R0);
 492       DAG.getMachineFunction().addLiveOut(ARM::R1);
 493     }
 494     break;
 495   }
 496
 497   //We must use RET_FLAG instead of BRIND because BRIND doesn't have a flag
 498   return DAG.getNode(ARMISD::RET_FLAG, MVT::Other, Copy, Copy.getValue(1));
 499 }
 500
 501 static SDOperand LowerConstantPool(SDOperand Op, SelectionDAG &DAG) {
 502   MVT::ValueType PtrVT = Op.getValueType();
 503   ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(Op);
 504   Constant *C = CP->getConstVal();
 505   SDOperand CPI = DAG.getTargetConstantPool(C, PtrVT, CP->getAlignment());
 506
 507   return CPI;
 508 }
 509
 510 static SDOperand LowerGlobalAddress(SDOperand Op,
 511                                     SelectionDAG &DAG) {
 512   GlobalValue  *GV = cast<GlobalAddressSDNode>(Op)->getGlobal();
 513   int alignment = 2;
 514   SDOperand CPAddr = DAG.getConstantPool(GV, MVT::i32, alignment);
 515   return DAG.getLoad(MVT::i32, DAG.getEntryNode(), CPAddr, NULL, 0);
 516 }
 517
 518 static SDOperand LowerVASTART(SDOperand Op, SelectionDAG &DAG,
 519                               unsigned VarArgsFrameIndex) {
 520   // vastart just stores the address of the VarArgsFrameIndex slot into the
 521   // memory location argument.
 522   MVT::ValueType PtrVT = DAG.getTargetLoweringInfo().getPointerTy();
 523   SDOperand FR = DAG.getFrameIndex(VarArgsFrameIndex, PtrVT);
 524   SrcValueSDNode *SV = cast<SrcValueSDNode>(Op.getOperand(2));
 525   return DAG.getStore(Op.getOperand(0), FR, Op.getOperand(1), SV->getValue(),
 526                       SV->getOffset());
 527 }
 528
 529 static SDOperand LowerFORMAL_ARGUMENTS(SDOperand Op, SelectionDAG &DAG,
 530                                        int &VarArgsFrameIndex) {
 531   MachineFunction   &MF = DAG.getMachineFunction();
 532   MachineFrameInfo *MFI = MF.getFrameInfo();
 533   SSARegMap     *RegMap = MF.getSSARegMap();
 534   unsigned      NumArgs = Op.Val->getNumValues()-1;
 535   SDOperand        Root = Op.getOperand(0);
 536   bool         isVarArg = cast<ConstantSDNode>(Op.getOperand(2))->getValue() != 0;
 537   static const unsigned REGS[] = {
 538     ARM::R0, ARM::R1, ARM::R2, ARM::R3
 539   };
 540
 541   std::vector<MVT::ValueType> Types(Op.Val->value_begin(), Op.Val->value_end() - 1);
 542   ArgumentLayout Layout(Types);
 543
 544   std::vector<SDOperand> ArgValues;
 545   for (unsigned ArgNo = 0; ArgNo < NumArgs; ++ArgNo) {
 546     MVT::ValueType VT = Types[ArgNo];
 547
 548     SDOperand Value;
 549     if (Layout.isRegister(ArgNo)) {
 550       assert(VT == MVT::i32 || VT == MVT::f32 || VT == MVT::f64);
 551       unsigned  RegNum = Layout.getRegisterNum(ArgNo);
 552       unsigned    Reg1 = REGS[RegNum];
 553       unsigned   VReg1 = RegMap->createVirtualRegister(&ARM::IntRegsRegClass);
 554       SDOperand Value1 = DAG.getCopyFromReg(Root, VReg1, MVT::i32);
 555       MF.addLiveIn(Reg1, VReg1);
 556       if (VT == MVT::f64) {
 557         unsigned    Reg2 = REGS[RegNum + 1];
 558         unsigned   VReg2 = RegMap->createVirtualRegister(&ARM::IntRegsRegClass);
 559         SDOperand Value2 = DAG.getCopyFromReg(Root, VReg2, MVT::i32);
 560         MF.addLiveIn(Reg2, VReg2);
 561         Value            = DAG.getNode(ARMISD::FMDRR, MVT::f64, Value1, Value2);
 562       } else {
 563         Value = Value1;
 564         if (VT == MVT::f32)
 565           Value = DAG.getNode(ISD::BIT_CONVERT, VT, Value);
 566       }
 567     } else {
 568       // If the argument is actually used, emit a load from the right stack
 569       // slot.
 570       if (!Op.Val->hasNUsesOfValue(0, ArgNo)) {
 571         unsigned Offset = Layout.getOffset(ArgNo);
 572         unsigned   Size = MVT::getSizeInBits(VT)/8;
 573         int          FI = MFI->CreateFixedObject(Size, Offset);
 574         SDOperand   FIN = DAG.getFrameIndex(FI, VT);
 575         Value = DAG.getLoad(VT, Root, FIN, NULL, 0);
 576       } else {
 577         Value = DAG.getNode(ISD::UNDEF, VT);
 578       }
 579     }
 580     ArgValues.push_back(Value);
 581   }
 582
 583   unsigned NextRegNum = Layout.lastRegNum() + 1;
 584
 585   if (isVarArg) {
 586     //If this function is vararg we must store the remaing
 587     //registers so that they can be acessed with va_start
 588     VarArgsFrameIndex = MFI->CreateFixedObject(MVT::getSizeInBits(MVT::i32)/8,
 589                                                -16 + NextRegNum * 4);
 590
 591     SmallVector<SDOperand, 4> MemOps;
 592     for (unsigned RegNo = NextRegNum; RegNo < 4; ++RegNo) {
 593       int RegOffset = - (4 - RegNo) * 4;
 594       int FI = MFI->CreateFixedObject(MVT::getSizeInBits(MVT::i32)/8,
 595                                       RegOffset);
 596       SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
 597
 598       unsigned VReg = RegMap->createVirtualRegister(&ARM::IntRegsRegClass);
 599       MF.addLiveIn(REGS[RegNo], VReg);
 600
 601       SDOperand Val = DAG.getCopyFromReg(Root, VReg, MVT::i32);
 602       SDOperand Store = DAG.getStore(Val.getValue(1), Val, FIN, NULL, 0);
 603       MemOps.push_back(Store);
 604     }
 605     Root = DAG.getNode(ISD::TokenFactor, MVT::Other,&MemOps[0],MemOps.size());
 606   }
 607
 608   ArgValues.push_back(Root);
 609
 610   // Return the new list of results.
 611   std::vector<MVT::ValueType> RetVT(Op.Val->value_begin(),
 612                                     Op.Val->value_end());
 613   return DAG.getNode(ISD::MERGE_VALUES, RetVT, &ArgValues[0], ArgValues.size());
 614 }
 615
 616 static SDOperand GetCMP(ISD::CondCode CC, SDOperand LHS, SDOperand RHS,
 617                         SelectionDAG &DAG) {
 618   MVT::ValueType vt = LHS.getValueType();
 619   assert(vt == MVT::i32 || vt == MVT::f32 || vt == MVT::f64);
 620
 621   SDOperand Cmp = DAG.getNode(ARMISD::CMP,  MVT::Flag, LHS, RHS);
 622
 623   if (vt != MVT::i32)
 624     Cmp = DAG.getNode(ARMISD::FMSTAT, MVT::Flag, Cmp);
 625   return Cmp;
 626 }
 627
 628 static SDOperand GetARMCC(ISD::CondCode CC, MVT::ValueType vt,
 629                           SelectionDAG &DAG) {
 630   assert(vt == MVT::i32 || vt == MVT::f32 || vt == MVT::f64);
 631   if (vt == MVT::i32)
 632     return DAG.getConstant(DAGIntCCToARMCC(CC), MVT::i32);
 633   else
 634     return DAG.getConstant(DAGFPCCToARMCC(CC), MVT::i32);
 635 }
 636
 637 static SDOperand LowerSELECT_CC(SDOperand Op, SelectionDAG &DAG) {
 638   SDOperand LHS = Op.getOperand(0);
 639   SDOperand RHS = Op.getOperand(1);
 640   ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(4))->get();
 641   SDOperand TrueVal = Op.getOperand(2);
 642   SDOperand FalseVal = Op.getOperand(3);
 643   SDOperand      Cmp = GetCMP(CC, LHS, RHS, DAG);
 644   SDOperand    ARMCC = GetARMCC(CC, LHS.getValueType(), DAG);
 645   return DAG.getNode(ARMISD::SELECT, MVT::i32, TrueVal, FalseVal, ARMCC, Cmp);
 646 }
 647
 648 static SDOperand LowerBR_CC(SDOperand Op, SelectionDAG &DAG) {
 649   SDOperand  Chain = Op.getOperand(0);
 650   ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(1))->get();
 651   SDOperand    LHS = Op.getOperand(2);
 652   SDOperand    RHS = Op.getOperand(3);
 653   SDOperand   Dest = Op.getOperand(4);
 654   SDOperand    Cmp = GetCMP(CC, LHS, RHS, DAG);
 655   SDOperand  ARMCC = GetARMCC(CC, LHS.getValueType(), DAG);
 656   return DAG.getNode(ARMISD::BR, MVT::Other, Chain, Dest, ARMCC, Cmp);
 657 }
 658
 659 static SDOperand LowerSINT_TO_FP(SDOperand Op, SelectionDAG &DAG) {
 660   SDOperand IntVal  = Op.getOperand(0);
 661   assert(IntVal.getValueType() == MVT::i32);
 662   MVT::ValueType vt = Op.getValueType();
 663   assert(vt == MVT::f32 ||
 664          vt == MVT::f64);
 665
 666   SDOperand Tmp = DAG.getNode(ISD::BIT_CONVERT, MVT::f32, IntVal);
 667   ARMISD::NodeType op = vt == MVT::f32 ? ARMISD::FSITOS : ARMISD::FSITOD;
 668   return DAG.getNode(op, vt, Tmp);
 669 }
 670
 671 static SDOperand LowerFP_TO_SINT(SDOperand Op, SelectionDAG &DAG) {
 672   assert(Op.getValueType() == MVT::i32);
 673   SDOperand FloatVal = Op.getOperand(0);
 674   MVT::ValueType  vt = FloatVal.getValueType();
 675   assert(vt == MVT::f32 || vt == MVT::f64);
 676
 677   ARMISD::NodeType op = vt == MVT::f32 ? ARMISD::FTOSIS : ARMISD::FTOSID;
 678   SDOperand Tmp = DAG.getNode(op, MVT::f32, FloatVal);
 679   return DAG.getNode(ISD::BIT_CONVERT, MVT::i32, Tmp);
 680 }
 681
 682 static SDOperand LowerUINT_TO_FP(SDOperand Op, SelectionDAG &DAG) {
 683   SDOperand IntVal  = Op.getOperand(0);
 684   assert(IntVal.getValueType() == MVT::i32);
 685   MVT::ValueType vt = Op.getValueType();
 686   assert(vt == MVT::f32 ||
 687          vt == MVT::f64);
 688
 689   SDOperand Tmp = DAG.getNode(ISD::BIT_CONVERT, MVT::f32, IntVal);
 690   ARMISD::NodeType op = vt == MVT::f32 ? ARMISD::FUITOS : ARMISD::FUITOD;
 691   return DAG.getNode(op, vt, Tmp);
 692 }
 693
 694 static SDOperand LowerFP_TO_UINT(SDOperand Op, SelectionDAG &DAG) {
 695   assert(Op.getValueType() == MVT::i32);
 696   SDOperand FloatVal = Op.getOperand(0);
 697   MVT::ValueType  vt = FloatVal.getValueType();
 698   assert(vt == MVT::f32 || vt == MVT::f64);
 699
 700   ARMISD::NodeType op = vt == MVT::f32 ? ARMISD::FTOUIS : ARMISD::FTOUID;
 701   SDOperand Tmp = DAG.getNode(op, MVT::f32, FloatVal);
 702   return DAG.getNode(ISD::BIT_CONVERT, MVT::i32, Tmp);
 703 }
 704
 705 SDOperand ARMTargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
 706   switch (Op.getOpcode()) {
 707   default:
 708     assert(0 && "Should not custom lower this!");
 709     abort();
 710   case ISD::ConstantPool:
 711     return LowerConstantPool(Op, DAG);
 712   case ISD::GlobalAddress:
 713     return LowerGlobalAddress(Op, DAG);
 714   case ISD::FP_TO_SINT:
 715     return LowerFP_TO_SINT(Op, DAG);
 716   case ISD::SINT_TO_FP:
 717     return LowerSINT_TO_FP(Op, DAG);
 718   case ISD::FP_TO_UINT:
 719     return LowerFP_TO_UINT(Op, DAG);
 720   case ISD::UINT_TO_FP:
 721     return LowerUINT_TO_FP(Op, DAG);
 722   case ISD::FORMAL_ARGUMENTS:
 723     return LowerFORMAL_ARGUMENTS(Op, DAG, VarArgsFrameIndex);
 724   case ISD::CALL:
 725     return LowerCALL(Op, DAG);
 726   case ISD::RET:
 727     return LowerRET(Op, DAG);
 728   case ISD::SELECT_CC:
 729     return LowerSELECT_CC(Op, DAG);
 730   case ISD::BR_CC:
 731     return LowerBR_CC(Op, DAG);
 732   case ISD::VASTART:
 733     return LowerVASTART(Op, DAG, VarArgsFrameIndex);
 734   }
 735 }
 736
 737 //===----------------------------------------------------------------------===//
 738 // Instruction Selector Implementation
 739 //===----------------------------------------------------------------------===//
 740
 741 //===--------------------------------------------------------------------===//
 742 /// ARMDAGToDAGISel - ARM specific code to select ARM machine
 743 /// instructions for SelectionDAG operations.
 744 ///
 745 namespace {
 746 class ARMDAGToDAGISel : public SelectionDAGISel {
 747   ARMTargetLowering Lowering;
 748
 749 public:
 750   ARMDAGToDAGISel(TargetMachine &TM)
 751     : SelectionDAGISel(Lowering), Lowering(TM) {
 752   }
 753
 754   SDNode *Select(SDOperand Op);
 755   virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
 756   bool SelectAddrRegImm(SDOperand N, SDOperand &Offset, SDOperand &Base);
 757   bool SelectAddrMode1(SDOperand N, SDOperand &Arg, SDOperand &Shift,
 758                        SDOperand &ShiftType);
 759   bool SelectAddrMode5(SDOperand N, SDOperand &Arg, 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 N,
 814                                       SDOperand &Arg,
 815                                       SDOperand &Shift,
 816                                       SDOperand &ShiftType) {
 817   switch(N.getOpcode()) {
 818   case ISD::Constant: {
 819     uint32_t val = cast<ConstantSDNode>(N)->getValue();
 820     if(!isRotInt8Immediate(val)) {
 821       Constant    *C = ConstantInt::get(Type::UIntTy, val);
 822       int  alignment = 2;
 823       SDOperand Addr = CurDAG->getTargetConstantPool(C, MVT::i32, alignment);
 824       SDOperand    Z = CurDAG->getTargetConstant(0,     MVT::i32);
 825       SDNode      *n = CurDAG->getTargetNode(ARM::ldr,  MVT::i32, Z, Addr);
 826       Arg            = SDOperand(n, 0);
 827     } else
 828       Arg            = CurDAG->getTargetConstant(val,    MVT::i32);
 829
 830     Shift     = CurDAG->getTargetConstant(0,             MVT::i32);
 831     ShiftType = CurDAG->getTargetConstant(ARMShift::LSL, MVT::i32);
 832     return true;
 833   }
 834   case ISD::SRA:
 835     Arg       = N.getOperand(0);
 836     Shift     = N.getOperand(1);
 837     ShiftType = CurDAG->getTargetConstant(ARMShift::ASR, MVT::i32);
 838     return true;
 839   case ISD::SRL:
 840     Arg       = N.getOperand(0);
 841     Shift     = N.getOperand(1);
 842     ShiftType = CurDAG->getTargetConstant(ARMShift::LSR, MVT::i32);
 843     return true;
 844   case ISD::SHL:
 845     Arg       = N.getOperand(0);
 846     Shift     = N.getOperand(1);
 847     ShiftType = CurDAG->getTargetConstant(ARMShift::LSL, MVT::i32);
 848     return true;
 849   }
 850
 851   Arg       = N;
 852   Shift     = CurDAG->getTargetConstant(0, MVT::i32);
 853   ShiftType = CurDAG->getTargetConstant(ARMShift::LSL, MVT::i32);
 854   return true;
 855 }
 856
 857 bool ARMDAGToDAGISel::SelectAddrMode5(SDOperand N, SDOperand &Arg,
 858                                       SDOperand &Offset) {
 859   //TODO: detect offset
 860   Offset = CurDAG->getTargetConstant(0, MVT::i32);
 861   Arg    = N;
 862   return true;
 863 }
 864
 865 //register plus/minus 12 bit offset
 866 bool ARMDAGToDAGISel::SelectAddrRegImm(SDOperand N, SDOperand &Offset,
 867                                     SDOperand &Base) {
 868   if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(N)) {
 869     Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i32);
 870     Offset = CurDAG->getTargetConstant(0, MVT::i32);
 871     return true;
 872   }
 873   if (N.getOpcode() == ISD::ADD) {
 874     short imm = 0;
 875     if (isInt12Immediate(N.getOperand(1), imm)) {
 876       Offset = CurDAG->getTargetConstant(imm, MVT::i32);
 877       if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N.getOperand(0))) {
 878         Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
 879       } else {
 880         Base = N.getOperand(0);
 881       }
 882       return true; // [r+i]
 883     }
 884   }
 885
 886   Offset = CurDAG->getTargetConstant(0, MVT::i32);
 887   if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N)) {
 888     Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
 889   }
 890   else
 891     Base = N;
 892   return true;      //any address fits in a register
 893 }
 894
 895 SDNode *ARMDAGToDAGISel::Select(SDOperand Op) {
 896   SDNode *N = Op.Val;
 897
 898   switch (N->getOpcode()) {
 899   default:
 900     return SelectCode(Op);
 901     break;
 902   }
 903   return NULL;
 904 }
 905
 906 }  // end anonymous namespace
 907
 908 /// createARMISelDag - This pass converts a legalized DAG into a
 909 /// ARM-specific DAG, ready for instruction scheduling.
 910 ///
 911 FunctionPass *llvm::createARMISelDag(TargetMachine &TM) {
 912   return new ARMDAGToDAGISel(TM);
 913 }