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 <queue>
  31 #include <set>
  32 using namespace llvm;
  33
  34 namespace {
  35   class ARMTargetLowering : public TargetLowering {
  36     int VarArgsFrameIndex;            // FrameIndex for start of varargs area.
  37   public:
  38     ARMTargetLowering(TargetMachine &TM);
  39     virtual SDOperand LowerOperation(SDOperand Op, SelectionDAG &DAG);
  40     virtual const char *getTargetNodeName(unsigned Opcode) const;
  41   };
  42
  43 }
  44
  45 ARMTargetLowering::ARMTargetLowering(TargetMachine &TM)
  46   : TargetLowering(TM) {
  47   addRegisterClass(MVT::i32, ARM::IntRegsRegisterClass);
  48   addRegisterClass(MVT::f32, ARM::FPRegsRegisterClass);
  49   addRegisterClass(MVT::f64, ARM::DFPRegsRegisterClass);
  50
  51   setOperationAction(ISD::SINT_TO_FP, MVT::i32, Custom);
  52
  53   setOperationAction(ISD::RET,           MVT::Other, Custom);
  54   setOperationAction(ISD::GlobalAddress, MVT::i32,   Custom);
  55   setOperationAction(ISD::ConstantPool,  MVT::i32,   Custom);
  56
  57   setOperationAction(ISD::SETCC, MVT::i32, Expand);
  58   setOperationAction(ISD::SELECT_CC, MVT::i32, Custom);
  59   setOperationAction(ISD::BR_CC, MVT::i32, Custom);
  60
  61   setOperationAction(ISD::VASTART,       MVT::Other, Custom);
  62   setOperationAction(ISD::VAEND,         MVT::Other, Expand);
  63
  64   setOperationAction(ISD::ConstantFP, MVT::f64, Expand);
  65   setOperationAction(ISD::ConstantFP, MVT::f32, Expand);
  66
  67   setSchedulingPreference(SchedulingForRegPressure);
  68   computeRegisterProperties();
  69 }
  70
  71 namespace llvm {
  72   namespace ARMISD {
  73     enum NodeType {
  74       // Start the numbering where the builting ops and target ops leave off.
  75       FIRST_NUMBER = ISD::BUILTIN_OP_END+ARM::INSTRUCTION_LIST_END,
  76       /// CALL - A direct function call.
  77       CALL,
  78
  79       /// Return with a flag operand.
  80       RET_FLAG,
  81
  82       CMP,
  83
  84       SELECT,
  85
  86       BR,
  87
  88       FSITOS,
  89
  90       FSITOD,
  91
  92       FMRRD
  93     };
  94   }
  95 }
  96
  97 /// DAGCCToARMCC - Convert a DAG integer condition code to an ARM CC
  98 static ARMCC::CondCodes DAGCCToARMCC(ISD::CondCode CC) {
  99   switch (CC) {
 100   default:
 101     std::cerr << "CC = " << CC << "\n";
 102     assert(0 && "Unknown condition code!");
 103   case ISD::SETUGT: return ARMCC::HI;
 104   case ISD::SETULE: return ARMCC::LS;
 105   case ISD::SETLE:  return ARMCC::LE;
 106   case ISD::SETLT:  return ARMCC::LT;
 107   case ISD::SETGT:  return ARMCC::GT;
 108   case ISD::SETNE:  return ARMCC::NE;
 109   case ISD::SETEQ:  return ARMCC::EQ;
 110   case ISD::SETGE:  return ARMCC::GE;
 111   case ISD::SETUGE: return ARMCC::CS;
 112   case ISD::SETULT: return ARMCC::CC;
 113   }
 114 }
 115
 116 const char *ARMTargetLowering::getTargetNodeName(unsigned Opcode) const {
 117   switch (Opcode) {
 118   default: return 0;
 119   case ARMISD::CALL:          return "ARMISD::CALL";
 120   case ARMISD::RET_FLAG:      return "ARMISD::RET_FLAG";
 121   case ARMISD::SELECT:        return "ARMISD::SELECT";
 122   case ARMISD::CMP:           return "ARMISD::CMP";
 123   case ARMISD::BR:            return "ARMISD::BR";
 124   case ARMISD::FSITOS:        return "ARMISD::FSITOS";
 125   case ARMISD::FSITOD:        return "ARMISD::FSITOD";
 126   case ARMISD::FMRRD:         return "ARMISD::FMRRD";
 127   }
 128 }
 129
 130 // This transforms a ISD::CALL node into a
 131 // callseq_star <- ARMISD:CALL <- callseq_end
 132 // chain
 133 static SDOperand LowerCALL(SDOperand Op, SelectionDAG &DAG) {
 134   SDOperand Chain    = Op.getOperand(0);
 135   unsigned CallConv  = cast<ConstantSDNode>(Op.getOperand(1))->getValue();
 136   assert(CallConv == CallingConv::C && "unknown calling convention");
 137   bool isVarArg      = cast<ConstantSDNode>(Op.getOperand(2))->getValue() != 0;
 138   bool isTailCall    = cast<ConstantSDNode>(Op.getOperand(3))->getValue() != 0;
 139   assert(isTailCall == false && "tail call not supported");
 140   SDOperand Callee   = Op.getOperand(4);
 141   unsigned NumOps    = (Op.getNumOperands() - 5) / 2;
 142
 143   // Count how many bytes are to be pushed on the stack.
 144   unsigned NumBytes = 0;
 145
 146   // Add up all the space actually used.
 147   for (unsigned i = 4; i < NumOps; ++i)
 148     NumBytes += MVT::getSizeInBits(Op.getOperand(5+2*i).getValueType())/8;
 149
 150   // Adjust the stack pointer for the new arguments...
 151   // These operations are automatically eliminated by the prolog/epilog pass
 152   Chain = DAG.getCALLSEQ_START(Chain,
 153                                DAG.getConstant(NumBytes, MVT::i32));
 154
 155   SDOperand StackPtr = DAG.getRegister(ARM::R13, MVT::i32);
 156
 157   static const unsigned int num_regs = 4;
 158   static const unsigned regs[num_regs] = {
 159     ARM::R0, ARM::R1, ARM::R2, ARM::R3
 160   };
 161
 162   std::vector<std::pair<unsigned, SDOperand> > RegsToPass;
 163   std::vector<SDOperand> MemOpChains;
 164
 165   for (unsigned i = 0; i != NumOps; ++i) {
 166     SDOperand Arg = Op.getOperand(5+2*i);
 167     assert(Arg.getValueType() == MVT::i32);
 168     if (i < num_regs)
 169       RegsToPass.push_back(std::make_pair(regs[i], Arg));
 170     else {
 171       unsigned ArgOffset = (i - num_regs) * 4;
 172       SDOperand PtrOff = DAG.getConstant(ArgOffset, StackPtr.getValueType());
 173       PtrOff = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff);
 174       MemOpChains.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 175                                           Arg, PtrOff, DAG.getSrcValue(NULL)));
 176     }
 177   }
 178   if (!MemOpChains.empty())
 179     Chain = DAG.getNode(ISD::TokenFactor, MVT::Other,
 180                         &MemOpChains[0], MemOpChains.size());
 181
 182   // Build a sequence of copy-to-reg nodes chained together with token chain
 183   // and flag operands which copy the outgoing args into the appropriate regs.
 184   SDOperand InFlag;
 185   for (unsigned i = 0, e = RegsToPass.size(); i != e; ++i) {
 186     Chain = DAG.getCopyToReg(Chain, RegsToPass[i].first, RegsToPass[i].second,
 187                              InFlag);
 188     InFlag = Chain.getValue(1);
 189   }
 190
 191   std::vector<MVT::ValueType> NodeTys;
 192   NodeTys.push_back(MVT::Other);   // Returns a chain
 193   NodeTys.push_back(MVT::Flag);    // Returns a flag for retval copy to use.
 194
 195   // If the callee is a GlobalAddress/ExternalSymbol node (quite common, every
 196   // direct call is) turn it into a TargetGlobalAddress/TargetExternalSymbol
 197   // node so that legalize doesn't hack it.
 198   if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(Callee))
 199     Callee = DAG.getTargetGlobalAddress(G->getGlobal(), Callee.getValueType());
 200
 201   // If this is a direct call, pass the chain and the callee.
 202   assert (Callee.Val);
 203   std::vector<SDOperand> Ops;
 204   Ops.push_back(Chain);
 205   Ops.push_back(Callee);
 206
 207   // Add argument registers to the end of the list so that they are known live
 208   // into the call.
 209   for (unsigned i = 0, e = RegsToPass.size(); i != e; ++i)
 210     Ops.push_back(DAG.getRegister(RegsToPass[i].first,
 211                                   RegsToPass[i].second.getValueType()));
 212
 213   unsigned CallOpc = ARMISD::CALL;
 214   if (InFlag.Val)
 215     Ops.push_back(InFlag);
 216   Chain = DAG.getNode(CallOpc, NodeTys, &Ops[0], Ops.size());
 217   InFlag = Chain.getValue(1);
 218
 219   std::vector<SDOperand> ResultVals;
 220   NodeTys.clear();
 221
 222   // If the call has results, copy the values out of the ret val registers.
 223   switch (Op.Val->getValueType(0)) {
 224   default: assert(0 && "Unexpected ret value!");
 225   case MVT::Other:
 226     break;
 227   case MVT::i32:
 228     Chain = DAG.getCopyFromReg(Chain, ARM::R0, MVT::i32, InFlag).getValue(1);
 229     ResultVals.push_back(Chain.getValue(0));
 230     NodeTys.push_back(MVT::i32);
 231   }
 232
 233   Chain = DAG.getNode(ISD::CALLSEQ_END, MVT::Other, Chain,
 234                       DAG.getConstant(NumBytes, MVT::i32));
 235   NodeTys.push_back(MVT::Other);
 236
 237   if (ResultVals.empty())
 238     return Chain;
 239
 240   ResultVals.push_back(Chain);
 241   SDOperand Res = DAG.getNode(ISD::MERGE_VALUES, NodeTys, &ResultVals[0],
 242                               ResultVals.size());
 243   return Res.getValue(Op.ResNo);
 244 }
 245
 246 static SDOperand LowerRET(SDOperand Op, SelectionDAG &DAG) {
 247   SDOperand Copy;
 248   SDOperand Chain = Op.getOperand(0);
 249   SDOperand    R0 = DAG.getRegister(ARM::R0, MVT::i32);
 250   SDOperand    R1 = DAG.getRegister(ARM::R1, MVT::i32);
 251
 252   switch(Op.getNumOperands()) {
 253   default:
 254     assert(0 && "Do not know how to return this many arguments!");
 255     abort();
 256   case 1: {
 257     SDOperand LR = DAG.getRegister(ARM::R14, MVT::i32);
 258     return DAG.getNode(ARMISD::RET_FLAG, MVT::Other, Chain);
 259   }
 260   case 3: {
 261     SDOperand Val = Op.getOperand(1);
 262     assert(Val.getValueType() == MVT::i32 ||
 263            Val.getValueType() == MVT::f32 ||
 264            Val.getValueType() == MVT::f64);
 265
 266     if (Val.getValueType() == MVT::f64) {
 267       SDVTList    VTs = DAG.getVTList(MVT::Other, MVT::Flag);
 268       SDOperand Ops[] = {Chain, R0, R1, Val};
 269       Copy  = DAG.getNode(ARMISD::FMRRD, VTs, Ops, 4);
 270     } else {
 271       if (Val.getValueType() == MVT::f32)
 272         Val = DAG.getNode(ISD::BIT_CONVERT, MVT::i32, Val);
 273       Copy = DAG.getCopyToReg(Chain, R0, Val, SDOperand());
 274     }
 275
 276     if (DAG.getMachineFunction().liveout_empty()) {
 277       DAG.getMachineFunction().addLiveOut(ARM::R0);
 278       if (Val.getValueType() == MVT::f64)
 279         DAG.getMachineFunction().addLiveOut(ARM::R1);
 280     }
 281     break;
 282   }
 283   case 5:
 284     Copy = DAG.getCopyToReg(Chain, ARM::R1, Op.getOperand(3), SDOperand());
 285     Copy = DAG.getCopyToReg(Copy, ARM::R0, Op.getOperand(1), Copy.getValue(1));
 286     // If we haven't noted the R0+R1 are live out, do so now.
 287     if (DAG.getMachineFunction().liveout_empty()) {
 288       DAG.getMachineFunction().addLiveOut(ARM::R0);
 289       DAG.getMachineFunction().addLiveOut(ARM::R1);
 290     }
 291     break;
 292   }
 293
 294   //We must use RET_FLAG instead of BRIND because BRIND doesn't have a flag
 295   return DAG.getNode(ARMISD::RET_FLAG, MVT::Other, Copy, Copy.getValue(1));
 296 }
 297
 298 static SDOperand LowerFORMAL_ARGUMENT(SDOperand Op, SelectionDAG &DAG,
 299                                       unsigned *vRegs,
 300                                       unsigned ArgNo) {
 301   MachineFunction &MF = DAG.getMachineFunction();
 302   MVT::ValueType ObjectVT = Op.getValue(ArgNo).getValueType();
 303   assert (ObjectVT == MVT::i32);
 304   SDOperand Root = Op.getOperand(0);
 305   SSARegMap *RegMap = MF.getSSARegMap();
 306
 307   unsigned num_regs = 4;
 308   static const unsigned REGS[] = {
 309     ARM::R0, ARM::R1, ARM::R2, ARM::R3
 310   };
 311
 312   if(ArgNo < num_regs) {
 313     unsigned VReg = RegMap->createVirtualRegister(&ARM::IntRegsRegClass);
 314     MF.addLiveIn(REGS[ArgNo], VReg);
 315     vRegs[ArgNo] = VReg;
 316     return DAG.getCopyFromReg(Root, VReg, MVT::i32);
 317   } else {
 318     // If the argument is actually used, emit a load from the right stack
 319       // slot.
 320     if (!Op.Val->hasNUsesOfValue(0, ArgNo)) {
 321       unsigned ArgOffset = (ArgNo - num_regs) * 4;
 322
 323       MachineFrameInfo *MFI = MF.getFrameInfo();
 324       unsigned ObjSize = MVT::getSizeInBits(ObjectVT)/8;
 325       int FI = MFI->CreateFixedObject(ObjSize, ArgOffset);
 326       SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
 327       return DAG.getLoad(ObjectVT, Root, FIN,
 328                          DAG.getSrcValue(NULL));
 329     } else {
 330       // Don't emit a dead load.
 331       return DAG.getNode(ISD::UNDEF, ObjectVT);
 332     }
 333   }
 334 }
 335
 336 static SDOperand LowerConstantPool(SDOperand Op, SelectionDAG &DAG) {
 337   MVT::ValueType PtrVT = Op.getValueType();
 338   ConstantPoolSDNode *CP = cast<ConstantPoolSDNode>(Op);
 339   Constant *C = CP->getConstVal();
 340   SDOperand CPI = DAG.getTargetConstantPool(C, PtrVT, CP->getAlignment());
 341
 342   return CPI;
 343 }
 344
 345 static SDOperand LowerGlobalAddress(SDOperand Op,
 346                                     SelectionDAG &DAG) {
 347   GlobalValue  *GV = cast<GlobalAddressSDNode>(Op)->getGlobal();
 348   int alignment = 2;
 349   SDOperand CPAddr = DAG.getConstantPool(GV, MVT::i32, alignment);
 350   return DAG.getLoad(MVT::i32, DAG.getEntryNode(), CPAddr,
 351                      DAG.getSrcValue(NULL));
 352 }
 353
 354 static SDOperand LowerVASTART(SDOperand Op, SelectionDAG &DAG,
 355                               unsigned VarArgsFrameIndex) {
 356   // vastart just stores the address of the VarArgsFrameIndex slot into the
 357   // memory location argument.
 358   MVT::ValueType PtrVT = DAG.getTargetLoweringInfo().getPointerTy();
 359   SDOperand FR = DAG.getFrameIndex(VarArgsFrameIndex, PtrVT);
 360   return DAG.getNode(ISD::STORE, MVT::Other, Op.getOperand(0), FR,
 361                      Op.getOperand(1), Op.getOperand(2));
 362 }
 363
 364 static SDOperand LowerFORMAL_ARGUMENTS(SDOperand Op, SelectionDAG &DAG,
 365                                        int &VarArgsFrameIndex) {
 366   std::vector<SDOperand> ArgValues;
 367   SDOperand Root = Op.getOperand(0);
 368   unsigned VRegs[4];
 369
 370   unsigned NumArgs = Op.Val->getNumValues()-1;
 371   for (unsigned ArgNo = 0; ArgNo < NumArgs; ++ArgNo) {
 372     SDOperand ArgVal = LowerFORMAL_ARGUMENT(Op, DAG, VRegs, ArgNo);
 373
 374     ArgValues.push_back(ArgVal);
 375   }
 376
 377   bool isVarArg = cast<ConstantSDNode>(Op.getOperand(2))->getValue() != 0;
 378   if (isVarArg) {
 379     MachineFunction &MF = DAG.getMachineFunction();
 380     SSARegMap *RegMap = MF.getSSARegMap();
 381     MachineFrameInfo *MFI = MF.getFrameInfo();
 382     VarArgsFrameIndex = MFI->CreateFixedObject(MVT::getSizeInBits(MVT::i32)/8,
 383                                                -16 + NumArgs * 4);
 384
 385
 386     static const unsigned REGS[] = {
 387       ARM::R0, ARM::R1, ARM::R2, ARM::R3
 388     };
 389     // If this function is vararg, store r0-r3 to their spots on the stack
 390     // so that they may be loaded by deferencing the result of va_next.
 391     SmallVector<SDOperand, 4> MemOps;
 392     for (unsigned ArgNo = 0; ArgNo < 4; ++ArgNo) {
 393       int ArgOffset = - (4 - ArgNo) * 4;
 394       int FI = MFI->CreateFixedObject(MVT::getSizeInBits(MVT::i32)/8,
 395                                       ArgOffset);
 396       SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
 397
 398       unsigned VReg;
 399       if (ArgNo < NumArgs)
 400         VReg = VRegs[ArgNo];
 401       else
 402         VReg = RegMap->createVirtualRegister(&ARM::IntRegsRegClass);
 403       if (ArgNo >= NumArgs)
 404         MF.addLiveIn(REGS[ArgNo], VReg);
 405
 406       SDOperand Val = DAG.getCopyFromReg(Root, VReg, MVT::i32);
 407       SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, Val.getValue(1),
 408                                     Val, FIN, DAG.getSrcValue(NULL));
 409       MemOps.push_back(Store);
 410     }
 411     Root = DAG.getNode(ISD::TokenFactor, MVT::Other,&MemOps[0],MemOps.size());
 412   }
 413
 414   ArgValues.push_back(Root);
 415
 416   // Return the new list of results.
 417   std::vector<MVT::ValueType> RetVT(Op.Val->value_begin(),
 418                                     Op.Val->value_end());
 419   return DAG.getNode(ISD::MERGE_VALUES, RetVT, &ArgValues[0], ArgValues.size());
 420 }
 421
 422 static SDOperand LowerSELECT_CC(SDOperand Op, SelectionDAG &DAG) {
 423   SDOperand LHS = Op.getOperand(0);
 424   SDOperand RHS = Op.getOperand(1);
 425   ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(4))->get();
 426   SDOperand TrueVal = Op.getOperand(2);
 427   SDOperand FalseVal = Op.getOperand(3);
 428   SDOperand    ARMCC = DAG.getConstant(DAGCCToARMCC(CC), MVT::i32);
 429
 430   SDOperand Cmp = DAG.getNode(ARMISD::CMP, MVT::Flag, LHS, RHS);
 431   return DAG.getNode(ARMISD::SELECT, MVT::i32, TrueVal, FalseVal, ARMCC, Cmp);
 432 }
 433
 434 static SDOperand LowerBR_CC(SDOperand Op, SelectionDAG &DAG) {
 435   SDOperand  Chain = Op.getOperand(0);
 436   ISD::CondCode CC = cast<CondCodeSDNode>(Op.getOperand(1))->get();
 437   SDOperand    LHS = Op.getOperand(2);
 438   SDOperand    RHS = Op.getOperand(3);
 439   SDOperand   Dest = Op.getOperand(4);
 440   SDOperand  ARMCC = DAG.getConstant(DAGCCToARMCC(CC), MVT::i32);
 441
 442   SDOperand Cmp = DAG.getNode(ARMISD::CMP, MVT::Flag, LHS, RHS);
 443   return DAG.getNode(ARMISD::BR, MVT::Other, Chain, Dest, ARMCC, Cmp);
 444 }
 445
 446 static SDOperand LowerSINT_TO_FP(SDOperand Op, SelectionDAG &DAG) {
 447   SDOperand IntVal  = Op.getOperand(0);
 448   assert(IntVal.getValueType() == MVT::i32);
 449   MVT::ValueType vt = Op.getValueType();
 450   assert(vt == MVT::f32 ||
 451          vt == MVT::f64);
 452
 453   SDOperand Tmp = DAG.getNode(ISD::BIT_CONVERT, MVT::f32, IntVal);
 454   ARMISD::NodeType op = vt == MVT::f32 ? ARMISD::FSITOS : ARMISD::FSITOD;
 455   return DAG.getNode(op, vt, Tmp);
 456 }
 457
 458 SDOperand ARMTargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) {
 459   switch (Op.getOpcode()) {
 460   default:
 461     assert(0 && "Should not custom lower this!");
 462     abort();
 463   case ISD::ConstantPool:
 464     return LowerConstantPool(Op, DAG);
 465   case ISD::GlobalAddress:
 466     return LowerGlobalAddress(Op, DAG);
 467   case ISD::SINT_TO_FP:
 468     return LowerSINT_TO_FP(Op, DAG);
 469   case ISD::FORMAL_ARGUMENTS:
 470     return LowerFORMAL_ARGUMENTS(Op, DAG, VarArgsFrameIndex);
 471   case ISD::CALL:
 472     return LowerCALL(Op, DAG);
 473   case ISD::RET:
 474     return LowerRET(Op, DAG);
 475   case ISD::SELECT_CC:
 476     return LowerSELECT_CC(Op, DAG);
 477   case ISD::BR_CC:
 478     return LowerBR_CC(Op, DAG);
 479   case ISD::VASTART:
 480     return LowerVASTART(Op, DAG, VarArgsFrameIndex);
 481   }
 482 }
 483
 484 //===----------------------------------------------------------------------===//
 485 // Instruction Selector Implementation
 486 //===----------------------------------------------------------------------===//
 487
 488 //===--------------------------------------------------------------------===//
 489 /// ARMDAGToDAGISel - ARM specific code to select ARM machine
 490 /// instructions for SelectionDAG operations.
 491 ///
 492 namespace {
 493 class ARMDAGToDAGISel : public SelectionDAGISel {
 494   ARMTargetLowering Lowering;
 495
 496 public:
 497   ARMDAGToDAGISel(TargetMachine &TM)
 498     : SelectionDAGISel(Lowering), Lowering(TM) {
 499   }
 500
 501   SDNode *Select(SDOperand Op);
 502   virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
 503   bool SelectAddrRegImm(SDOperand N, SDOperand &Offset, SDOperand &Base);
 504   bool SelectAddrMode1(SDOperand N, SDOperand &Arg, SDOperand &Shift,
 505                        SDOperand &ShiftType);
 506
 507   // Include the pieces autogenerated from the target description.
 508 #include "ARMGenDAGISel.inc"
 509 };
 510
 511 void ARMDAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
 512   DEBUG(BB->dump());
 513
 514   DAG.setRoot(SelectRoot(DAG.getRoot()));
 515   DAG.RemoveDeadNodes();
 516
 517   ScheduleAndEmitDAG(DAG);
 518 }
 519
 520 static bool isInt12Immediate(SDNode *N, short &Imm) {
 521   if (N->getOpcode() != ISD::Constant)
 522     return false;
 523
 524   int32_t t = cast<ConstantSDNode>(N)->getValue();
 525   int max = 1<<12;
 526   int min = -max;
 527   if (t > min && t < max) {
 528     Imm = t;
 529     return true;
 530   }
 531   else
 532     return false;
 533 }
 534
 535 static bool isInt12Immediate(SDOperand Op, short &Imm) {
 536   return isInt12Immediate(Op.Val, Imm);
 537 }
 538
 539 static uint32_t rotateL(uint32_t x) {
 540   uint32_t bit31 = (x & (1 << 31)) >> 31;
 541   uint32_t     t = x << 1;
 542   return t | bit31;
 543 }
 544
 545 static bool isUInt8Immediate(uint32_t x) {
 546   return x < (1 << 8);
 547 }
 548
 549 static bool isRotInt8Immediate(uint32_t x) {
 550   int r;
 551   for (r = 0; r < 16; r++) {
 552     if (isUInt8Immediate(x))
 553       return true;
 554     x = rotateL(rotateL(x));
 555   }
 556   return false;
 557 }
 558
 559 bool ARMDAGToDAGISel::SelectAddrMode1(SDOperand N,
 560                                       SDOperand &Arg,
 561                                       SDOperand &Shift,
 562                                       SDOperand &ShiftType) {
 563   switch(N.getOpcode()) {
 564   case ISD::Constant: {
 565     uint32_t val = cast<ConstantSDNode>(N)->getValue();
 566     if(!isRotInt8Immediate(val)) {
 567       const Type  *t =  MVT::getTypeForValueType(MVT::i32);
 568       Constant    *C = ConstantUInt::get(t, val);
 569       int  alignment = 2;
 570       SDOperand Addr = CurDAG->getTargetConstantPool(C, MVT::i32, alignment);
 571       SDOperand    Z = CurDAG->getTargetConstant(0,     MVT::i32);
 572       SDNode      *n = CurDAG->getTargetNode(ARM::ldr,  MVT::i32, Z, Addr);
 573       Arg            = SDOperand(n, 0);
 574     } else
 575       Arg            = CurDAG->getTargetConstant(val,    MVT::i32);
 576
 577     Shift     = CurDAG->getTargetConstant(0,             MVT::i32);
 578     ShiftType = CurDAG->getTargetConstant(ARMShift::LSL, MVT::i32);
 579     return true;
 580   }
 581   case ISD::SRA:
 582     Arg       = N.getOperand(0);
 583     Shift     = N.getOperand(1);
 584     ShiftType = CurDAG->getTargetConstant(ARMShift::ASR, MVT::i32);
 585     return true;
 586   case ISD::SRL:
 587     Arg       = N.getOperand(0);
 588     Shift     = N.getOperand(1);
 589     ShiftType = CurDAG->getTargetConstant(ARMShift::LSR, MVT::i32);
 590     return true;
 591   case ISD::SHL:
 592     Arg       = N.getOperand(0);
 593     Shift     = N.getOperand(1);
 594     ShiftType = CurDAG->getTargetConstant(ARMShift::LSL, MVT::i32);
 595     return true;
 596   }
 597
 598   Arg       = N;
 599   Shift     = CurDAG->getTargetConstant(0, MVT::i32);
 600   ShiftType = CurDAG->getTargetConstant(ARMShift::LSL, MVT::i32);
 601   return true;
 602 }
 603
 604 //register plus/minus 12 bit offset
 605 bool ARMDAGToDAGISel::SelectAddrRegImm(SDOperand N, SDOperand &Offset,
 606                                     SDOperand &Base) {
 607   if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(N)) {
 608     Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i32);
 609     Offset = CurDAG->getTargetConstant(0, MVT::i32);
 610     return true;
 611   }
 612   if (N.getOpcode() == ISD::ADD) {
 613     short imm = 0;
 614     if (isInt12Immediate(N.getOperand(1), imm)) {
 615       Offset = CurDAG->getTargetConstant(imm, MVT::i32);
 616       if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N.getOperand(0))) {
 617         Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
 618       } else {
 619         Base = N.getOperand(0);
 620       }
 621       return true; // [r+i]
 622     }
 623   }
 624
 625   Offset = CurDAG->getTargetConstant(0, MVT::i32);
 626   if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N)) {
 627     Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
 628   }
 629   else
 630     Base = N;
 631   return true;      //any address fits in a register
 632 }
 633
 634 SDNode *ARMDAGToDAGISel::Select(SDOperand Op) {
 635   SDNode *N = Op.Val;
 636
 637   switch (N->getOpcode()) {
 638   default:
 639     return SelectCode(Op);
 640     break;
 641   }
 642   return NULL;
 643 }
 644
 645 }  // end anonymous namespace
 646
 647 /// createARMISelDag - This pass converts a legalized DAG into a
 648 /// ARM-specific DAG, ready for instruction scheduling.
 649 ///
 650 FunctionPass *llvm::createARMISelDag(TargetMachine &TM) {
 651   return new ARMDAGToDAGISel(TM);
 652 }