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