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 is distributed under the University of Illinois Open Source
   6 // 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 "ARMISelLowering.h"
  16 #include "ARMTargetMachine.h"
  17 #include "ARMAddressingModes.h"
  18 #include "llvm/CallingConv.h"
  19 #include "llvm/Constants.h"
  20 #include "llvm/DerivedTypes.h"
  21 #include "llvm/Function.h"
  22 #include "llvm/Intrinsics.h"
  23 #include "llvm/CodeGen/MachineFrameInfo.h"
  24 #include "llvm/CodeGen/MachineFunction.h"
  25 #include "llvm/CodeGen/MachineInstrBuilder.h"
  26 #include "llvm/CodeGen/MachineModuleInfo.h"
  27 #include "llvm/CodeGen/SelectionDAG.h"
  28 #include "llvm/CodeGen/SelectionDAGISel.h"
  29 #include "llvm/Target/TargetLowering.h"
  30 #include "llvm/Target/TargetOptions.h"
  31 #include "llvm/Support/Compiler.h"
  32 #include "llvm/Support/Debug.h"
  33 using namespace llvm;
  34
  35 //===--------------------------------------------------------------------===//
  36 /// ARMDAGToDAGISel - ARM specific code to select ARM machine
  37 /// instructions for SelectionDAG operations.
  38 ///
  39 namespace {
  40 class ARMDAGToDAGISel : public SelectionDAGISel {
  41   ARMTargetLowering Lowering;
  42
  43   /// Subtarget - Keep a pointer to the ARMSubtarget around so that we can
  44   /// make the right decision when generating code for different targets.
  45   const ARMSubtarget *Subtarget;
  46
  47 public:
  48   ARMDAGToDAGISel(ARMTargetMachine &TM)
  49     : SelectionDAGISel(Lowering), Lowering(TM),
  50     Subtarget(&TM.getSubtarget<ARMSubtarget>()) {
  51   }
  52
  53   virtual const char *getPassName() const {
  54     return "ARM Instruction Selection";
  55   }
  56
  57   SDNode *Select(SDOperand Op);
  58   virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
  59   bool SelectAddrMode2(SDOperand Op, SDOperand N, SDOperand &Base,
  60                        SDOperand &Offset, SDOperand &Opc);
  61   bool SelectAddrMode2Offset(SDOperand Op, SDOperand N,
  62                              SDOperand &Offset, SDOperand &Opc);
  63   bool SelectAddrMode3(SDOperand Op, SDOperand N, SDOperand &Base,
  64                        SDOperand &Offset, SDOperand &Opc);
  65   bool SelectAddrMode3Offset(SDOperand Op, SDOperand N,
  66                              SDOperand &Offset, SDOperand &Opc);
  67   bool SelectAddrMode5(SDOperand Op, SDOperand N, SDOperand &Base,
  68                        SDOperand &Offset);
  69
  70   bool SelectAddrModePC(SDOperand Op, SDOperand N, SDOperand &Offset,
  71                          SDOperand &Label);
  72
  73   bool SelectThumbAddrModeRR(SDOperand Op, SDOperand N, SDOperand &Base,
  74                              SDOperand &Offset);
  75   bool SelectThumbAddrModeRI5(SDOperand Op, SDOperand N, unsigned Scale,
  76                               SDOperand &Base, SDOperand &OffImm,
  77                               SDOperand &Offset);
  78   bool SelectThumbAddrModeS1(SDOperand Op, SDOperand N, SDOperand &Base,
  79                              SDOperand &OffImm, SDOperand &Offset);
  80   bool SelectThumbAddrModeS2(SDOperand Op, SDOperand N, SDOperand &Base,
  81                              SDOperand &OffImm, SDOperand &Offset);
  82   bool SelectThumbAddrModeS4(SDOperand Op, SDOperand N, SDOperand &Base,
  83                              SDOperand &OffImm, SDOperand &Offset);
  84   bool SelectThumbAddrModeSP(SDOperand Op, SDOperand N, SDOperand &Base,
  85                              SDOperand &OffImm);
  86
  87   bool SelectShifterOperandReg(SDOperand Op, SDOperand N, SDOperand &A,
  88                                SDOperand &B, SDOperand &C);
  89
  90   // Include the pieces autogenerated from the target description.
  91 #include "ARMGenDAGISel.inc"
  92 };
  93 }
  94
  95 void ARMDAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
  96   DEBUG(BB->dump());
  97
  98   DAG.setRoot(SelectRoot(DAG.getRoot()));
  99   DAG.RemoveDeadNodes();
 100
 101   ScheduleAndEmitDAG(DAG);
 102 }
 103
 104 bool ARMDAGToDAGISel::SelectAddrMode2(SDOperand Op, SDOperand N,
 105                                       SDOperand &Base, SDOperand &Offset,
 106                                       SDOperand &Opc) {
 107   if (N.getOpcode() == ISD::MUL) {
 108     if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 109       // X * [3,5,9] -> X + X * [2,4,8] etc.
 110       int RHSC = (int)RHS->getValue();
 111       if (RHSC & 1) {
 112         RHSC = RHSC & ~1;
 113         ARM_AM::AddrOpc AddSub = ARM_AM::add;
 114         if (RHSC < 0) {
 115           AddSub = ARM_AM::sub;
 116           RHSC = - RHSC;
 117         }
 118         if (isPowerOf2_32(RHSC)) {
 119           unsigned ShAmt = Log2_32(RHSC);
 120           Base = Offset = N.getOperand(0);
 121           Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, ShAmt,
 122                                                             ARM_AM::lsl),
 123                                           MVT::i32);
 124           return true;
 125         }
 126       }
 127     }
 128   }
 129
 130   if (N.getOpcode() != ISD::ADD && N.getOpcode() != ISD::SUB) {
 131     Base = N;
 132     if (N.getOpcode() == ISD::FrameIndex) {
 133       int FI = cast<FrameIndexSDNode>(N)->getIndex();
 134       Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
 135     } else if (N.getOpcode() == ARMISD::Wrapper) {
 136       Base = N.getOperand(0);
 137     }
 138     Offset = CurDAG->getRegister(0, MVT::i32);
 139     Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(ARM_AM::add, 0,
 140                                                       ARM_AM::no_shift),
 141                                     MVT::i32);
 142     return true;
 143   }
 144
 145   // Match simple R +/- imm12 operands.
 146   if (N.getOpcode() == ISD::ADD)
 147     if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 148       int RHSC = (int)RHS->getValue();
 149       if ((RHSC >= 0 && RHSC < 0x1000) ||
 150           (RHSC < 0 && RHSC > -0x1000)) { // 12 bits.
 151         Base = N.getOperand(0);
 152         if (Base.getOpcode() == ISD::FrameIndex) {
 153           int FI = cast<FrameIndexSDNode>(Base)->getIndex();
 154           Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
 155         }
 156         Offset = CurDAG->getRegister(0, MVT::i32);
 157
 158         ARM_AM::AddrOpc AddSub = ARM_AM::add;
 159         if (RHSC < 0) {
 160           AddSub = ARM_AM::sub;
 161           RHSC = - RHSC;
 162         }
 163         Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, RHSC,
 164                                                           ARM_AM::no_shift),
 165                                         MVT::i32);
 166         return true;
 167       }
 168     }
 169
 170   // Otherwise this is R +/- [possibly shifted] R
 171   ARM_AM::AddrOpc AddSub = N.getOpcode() == ISD::ADD ? ARM_AM::add:ARM_AM::sub;
 172   ARM_AM::ShiftOpc ShOpcVal = ARM_AM::getShiftOpcForNode(N.getOperand(1));
 173   unsigned ShAmt = 0;
 174
 175   Base   = N.getOperand(0);
 176   Offset = N.getOperand(1);
 177
 178   if (ShOpcVal != ARM_AM::no_shift) {
 179     // Check to see if the RHS of the shift is a constant, if not, we can't fold
 180     // it.
 181     if (ConstantSDNode *Sh =
 182            dyn_cast<ConstantSDNode>(N.getOperand(1).getOperand(1))) {
 183       ShAmt = Sh->getValue();
 184       Offset = N.getOperand(1).getOperand(0);
 185     } else {
 186       ShOpcVal = ARM_AM::no_shift;
 187     }
 188   }
 189
 190   // Try matching (R shl C) + (R).
 191   if (N.getOpcode() == ISD::ADD && ShOpcVal == ARM_AM::no_shift) {
 192     ShOpcVal = ARM_AM::getShiftOpcForNode(N.getOperand(0));
 193     if (ShOpcVal != ARM_AM::no_shift) {
 194       // Check to see if the RHS of the shift is a constant, if not, we can't
 195       // fold it.
 196       if (ConstantSDNode *Sh =
 197           dyn_cast<ConstantSDNode>(N.getOperand(0).getOperand(1))) {
 198         ShAmt = Sh->getValue();
 199         Offset = N.getOperand(0).getOperand(0);
 200         Base = N.getOperand(1);
 201       } else {
 202         ShOpcVal = ARM_AM::no_shift;
 203       }
 204     }
 205   }
 206
 207   Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, ShAmt, ShOpcVal),
 208                                   MVT::i32);
 209   return true;
 210 }
 211
 212 bool ARMDAGToDAGISel::SelectAddrMode2Offset(SDOperand Op, SDOperand N,
 213                                             SDOperand &Offset, SDOperand &Opc) {
 214   unsigned Opcode = Op.getOpcode();
 215   ISD::MemIndexedMode AM = (Opcode == ISD::LOAD)
 216     ? cast<LoadSDNode>(Op)->getAddressingMode()
 217     : cast<StoreSDNode>(Op)->getAddressingMode();
 218   ARM_AM::AddrOpc AddSub = (AM == ISD::PRE_INC || AM == ISD::POST_INC)
 219     ? ARM_AM::add : ARM_AM::sub;
 220   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N)) {
 221     int Val = (int)C->getValue();
 222     if (Val >= 0 && Val < 0x1000) { // 12 bits.
 223       Offset = CurDAG->getRegister(0, MVT::i32);
 224       Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, Val,
 225                                                         ARM_AM::no_shift),
 226                                       MVT::i32);
 227       return true;
 228     }
 229   }
 230
 231   Offset = N;
 232   ARM_AM::ShiftOpc ShOpcVal = ARM_AM::getShiftOpcForNode(N);
 233   unsigned ShAmt = 0;
 234   if (ShOpcVal != ARM_AM::no_shift) {
 235     // Check to see if the RHS of the shift is a constant, if not, we can't fold
 236     // it.
 237     if (ConstantSDNode *Sh = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 238       ShAmt = Sh->getValue();
 239       Offset = N.getOperand(0);
 240     } else {
 241       ShOpcVal = ARM_AM::no_shift;
 242     }
 243   }
 244
 245   Opc = CurDAG->getTargetConstant(ARM_AM::getAM2Opc(AddSub, ShAmt, ShOpcVal),
 246                                   MVT::i32);
 247   return true;
 248 }
 249
 250
 251 bool ARMDAGToDAGISel::SelectAddrMode3(SDOperand Op, SDOperand N,
 252                                       SDOperand &Base, SDOperand &Offset,
 253                                       SDOperand &Opc) {
 254   if (N.getOpcode() == ISD::SUB) {
 255     // X - C  is canonicalize to X + -C, no need to handle it here.
 256     Base = N.getOperand(0);
 257     Offset = N.getOperand(1);
 258     Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(ARM_AM::sub, 0),MVT::i32);
 259     return true;
 260   }
 261
 262   if (N.getOpcode() != ISD::ADD) {
 263     Base = N;
 264     if (N.getOpcode() == ISD::FrameIndex) {
 265       int FI = cast<FrameIndexSDNode>(N)->getIndex();
 266       Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
 267     }
 268     Offset = CurDAG->getRegister(0, MVT::i32);
 269     Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(ARM_AM::add, 0),MVT::i32);
 270     return true;
 271   }
 272
 273   // If the RHS is +/- imm8, fold into addr mode.
 274   if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 275     int RHSC = (int)RHS->getValue();
 276     if ((RHSC >= 0 && RHSC < 256) ||
 277         (RHSC < 0 && RHSC > -256)) { // note -256 itself isn't allowed.
 278       Base = N.getOperand(0);
 279       if (Base.getOpcode() == ISD::FrameIndex) {
 280         int FI = cast<FrameIndexSDNode>(Base)->getIndex();
 281         Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
 282       }
 283       Offset = CurDAG->getRegister(0, MVT::i32);
 284
 285       ARM_AM::AddrOpc AddSub = ARM_AM::add;
 286       if (RHSC < 0) {
 287         AddSub = ARM_AM::sub;
 288         RHSC = - RHSC;
 289       }
 290       Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(AddSub, RHSC),MVT::i32);
 291       return true;
 292     }
 293   }
 294
 295   Base = N.getOperand(0);
 296   Offset = N.getOperand(1);
 297   Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(ARM_AM::add, 0), MVT::i32);
 298   return true;
 299 }
 300
 301 bool ARMDAGToDAGISel::SelectAddrMode3Offset(SDOperand Op, SDOperand N,
 302                                             SDOperand &Offset, SDOperand &Opc) {
 303   unsigned Opcode = Op.getOpcode();
 304   ISD::MemIndexedMode AM = (Opcode == ISD::LOAD)
 305     ? cast<LoadSDNode>(Op)->getAddressingMode()
 306     : cast<StoreSDNode>(Op)->getAddressingMode();
 307   ARM_AM::AddrOpc AddSub = (AM == ISD::PRE_INC || AM == ISD::POST_INC)
 308     ? ARM_AM::add : ARM_AM::sub;
 309   if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(N)) {
 310     int Val = (int)C->getValue();
 311     if (Val >= 0 && Val < 256) {
 312       Offset = CurDAG->getRegister(0, MVT::i32);
 313       Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(AddSub, Val), MVT::i32);
 314       return true;
 315     }
 316   }
 317
 318   Offset = N;
 319   Opc = CurDAG->getTargetConstant(ARM_AM::getAM3Opc(AddSub, 0), MVT::i32);
 320   return true;
 321 }
 322
 323
 324 bool ARMDAGToDAGISel::SelectAddrMode5(SDOperand Op, SDOperand N,
 325                                       SDOperand &Base, SDOperand &Offset) {
 326   if (N.getOpcode() != ISD::ADD) {
 327     Base = N;
 328     if (N.getOpcode() == ISD::FrameIndex) {
 329       int FI = cast<FrameIndexSDNode>(N)->getIndex();
 330       Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
 331     } else if (N.getOpcode() == ARMISD::Wrapper) {
 332       Base = N.getOperand(0);
 333     }
 334     Offset = CurDAG->getTargetConstant(ARM_AM::getAM5Opc(ARM_AM::add, 0),
 335                                        MVT::i32);
 336     return true;
 337   }
 338
 339   // If the RHS is +/- imm8, fold into addr mode.
 340   if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 341     int RHSC = (int)RHS->getValue();
 342     if ((RHSC & 3) == 0) {  // The constant is implicitly multiplied by 4.
 343       RHSC >>= 2;
 344       if ((RHSC >= 0 && RHSC < 256) ||
 345           (RHSC < 0 && RHSC > -256)) { // note -256 itself isn't allowed.
 346         Base = N.getOperand(0);
 347         if (Base.getOpcode() == ISD::FrameIndex) {
 348           int FI = cast<FrameIndexSDNode>(Base)->getIndex();
 349           Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
 350         }
 351
 352         ARM_AM::AddrOpc AddSub = ARM_AM::add;
 353         if (RHSC < 0) {
 354           AddSub = ARM_AM::sub;
 355           RHSC = - RHSC;
 356         }
 357         Offset = CurDAG->getTargetConstant(ARM_AM::getAM5Opc(AddSub, RHSC),
 358                                            MVT::i32);
 359         return true;
 360       }
 361     }
 362   }
 363
 364   Base = N;
 365   Offset = CurDAG->getTargetConstant(ARM_AM::getAM5Opc(ARM_AM::add, 0),
 366                                      MVT::i32);
 367   return true;
 368 }
 369
 370 bool ARMDAGToDAGISel::SelectAddrModePC(SDOperand Op, SDOperand N,
 371                                         SDOperand &Offset, SDOperand &Label) {
 372   if (N.getOpcode() == ARMISD::PIC_ADD && N.hasOneUse()) {
 373     Offset = N.getOperand(0);
 374     SDOperand N1 = N.getOperand(1);
 375     Label  = CurDAG->getTargetConstant(cast<ConstantSDNode>(N1)->getValue(),
 376                                        MVT::i32);
 377     return true;
 378   }
 379   return false;
 380 }
 381
 382 bool ARMDAGToDAGISel::SelectThumbAddrModeRR(SDOperand Op, SDOperand N,
 383                                             SDOperand &Base, SDOperand &Offset){
 384   if (N.getOpcode() != ISD::ADD) {
 385     Base = N;
 386     // We must materialize a zero in a reg! Returning an constant here won't
 387     // work since its node is -1 so it won't get added to the selection queue.
 388     // Explicitly issue a tMOVri8 node!
 389     Offset = SDOperand(CurDAG->getTargetNode(ARM::tMOVi8, MVT::i32,
 390                                     CurDAG->getTargetConstant(0, MVT::i32)), 0);
 391     return true;
 392   }
 393
 394   Base = N.getOperand(0);
 395   Offset = N.getOperand(1);
 396   return true;
 397 }
 398
 399 bool
 400 ARMDAGToDAGISel::SelectThumbAddrModeRI5(SDOperand Op, SDOperand N,
 401                                         unsigned Scale, SDOperand &Base,
 402                                         SDOperand &OffImm, SDOperand &Offset) {
 403   if (Scale == 4) {
 404     SDOperand TmpBase, TmpOffImm;
 405     if (SelectThumbAddrModeSP(Op, N, TmpBase, TmpOffImm))
 406       return false;  // We want to select tLDRspi / tSTRspi instead.
 407     if (N.getOpcode() == ARMISD::Wrapper &&
 408         N.getOperand(0).getOpcode() == ISD::TargetConstantPool)
 409       return false;  // We want to select tLDRpci instead.
 410   }
 411
 412   if (N.getOpcode() != ISD::ADD) {
 413     Base = (N.getOpcode() == ARMISD::Wrapper) ? N.getOperand(0) : N;
 414     Offset = CurDAG->getRegister(0, MVT::i32);
 415     OffImm = CurDAG->getTargetConstant(0, MVT::i32);
 416     return true;
 417   }
 418
 419   // Thumb does not have [sp, r] address mode.
 420   RegisterSDNode *LHSR = dyn_cast<RegisterSDNode>(N.getOperand(0));
 421   RegisterSDNode *RHSR = dyn_cast<RegisterSDNode>(N.getOperand(1));
 422   if ((LHSR && LHSR->getReg() == ARM::SP) ||
 423       (RHSR && RHSR->getReg() == ARM::SP)) {
 424     Base = N;
 425     Offset = CurDAG->getRegister(0, MVT::i32);
 426     OffImm = CurDAG->getTargetConstant(0, MVT::i32);
 427     return true;
 428   }
 429
 430   // If the RHS is + imm5 * scale, fold into addr mode.
 431   if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 432     int RHSC = (int)RHS->getValue();
 433     if ((RHSC & (Scale-1)) == 0) {  // The constant is implicitly multiplied.
 434       RHSC /= Scale;
 435       if (RHSC >= 0 && RHSC < 32) {
 436         Base = N.getOperand(0);
 437         Offset = CurDAG->getRegister(0, MVT::i32);
 438         OffImm = CurDAG->getTargetConstant(RHSC, MVT::i32);
 439         return true;
 440       }
 441     }
 442   }
 443
 444   Base = N.getOperand(0);
 445   Offset = N.getOperand(1);
 446   OffImm = CurDAG->getTargetConstant(0, MVT::i32);
 447   return true;
 448 }
 449
 450 bool ARMDAGToDAGISel::SelectThumbAddrModeS1(SDOperand Op, SDOperand N,
 451                                             SDOperand &Base, SDOperand &OffImm,
 452                                             SDOperand &Offset) {
 453   return SelectThumbAddrModeRI5(Op, N, 1, Base, OffImm, Offset);
 454 }
 455
 456 bool ARMDAGToDAGISel::SelectThumbAddrModeS2(SDOperand Op, SDOperand N,
 457                                             SDOperand &Base, SDOperand &OffImm,
 458                                             SDOperand &Offset) {
 459   return SelectThumbAddrModeRI5(Op, N, 2, Base, OffImm, Offset);
 460 }
 461
 462 bool ARMDAGToDAGISel::SelectThumbAddrModeS4(SDOperand Op, SDOperand N,
 463                                             SDOperand &Base, SDOperand &OffImm,
 464                                             SDOperand &Offset) {
 465   return SelectThumbAddrModeRI5(Op, N, 4, Base, OffImm, Offset);
 466 }
 467
 468 bool ARMDAGToDAGISel::SelectThumbAddrModeSP(SDOperand Op, SDOperand N,
 469                                            SDOperand &Base, SDOperand &OffImm) {
 470   if (N.getOpcode() == ISD::FrameIndex) {
 471     int FI = cast<FrameIndexSDNode>(N)->getIndex();
 472     Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
 473     OffImm = CurDAG->getTargetConstant(0, MVT::i32);
 474     return true;
 475   }
 476
 477   if (N.getOpcode() != ISD::ADD)
 478     return false;
 479
 480   RegisterSDNode *LHSR = dyn_cast<RegisterSDNode>(N.getOperand(0));
 481   if (N.getOperand(0).getOpcode() == ISD::FrameIndex ||
 482       (LHSR && LHSR->getReg() == ARM::SP)) {
 483     // If the RHS is + imm8 * scale, fold into addr mode.
 484     if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 485       int RHSC = (int)RHS->getValue();
 486       if ((RHSC & 3) == 0) {  // The constant is implicitly multiplied.
 487         RHSC >>= 2;
 488         if (RHSC >= 0 && RHSC < 256) {
 489           Base = N.getOperand(0);
 490           if (Base.getOpcode() == ISD::FrameIndex) {
 491             int FI = cast<FrameIndexSDNode>(Base)->getIndex();
 492             Base = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
 493           }
 494           OffImm = CurDAG->getTargetConstant(RHSC, MVT::i32);
 495           return true;
 496         }
 497       }
 498     }
 499   }
 500
 501   return false;
 502 }
 503
 504 bool ARMDAGToDAGISel::SelectShifterOperandReg(SDOperand Op,
 505                                               SDOperand N,
 506                                               SDOperand &BaseReg,
 507                                               SDOperand &ShReg,
 508                                               SDOperand &Opc) {
 509   ARM_AM::ShiftOpc ShOpcVal = ARM_AM::getShiftOpcForNode(N);
 510
 511   // Don't match base register only case. That is matched to a separate
 512   // lower complexity pattern with explicit register operand.
 513   if (ShOpcVal == ARM_AM::no_shift) return false;
 514
 515   BaseReg = N.getOperand(0);
 516   unsigned ShImmVal = 0;
 517   if (ConstantSDNode *RHS = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
 518     ShReg = CurDAG->getRegister(0, MVT::i32);
 519     ShImmVal = RHS->getValue() & 31;
 520   } else {
 521     ShReg = N.getOperand(1);
 522   }
 523   Opc = CurDAG->getTargetConstant(ARM_AM::getSORegOpc(ShOpcVal, ShImmVal),
 524                                   MVT::i32);
 525   return true;
 526 }
 527
 528 /// getAL - Returns a ARMCC::AL immediate node.
 529 static inline SDOperand getAL(SelectionDAG *CurDAG) {
 530   return CurDAG->getTargetConstant((uint64_t)ARMCC::AL, MVT::i32);
 531 }
 532
 533
 534 SDNode *ARMDAGToDAGISel::Select(SDOperand Op) {
 535   SDNode *N = Op.Val;
 536   unsigned Opcode = N->getOpcode();
 537
 538   if (Opcode >= ISD::BUILTIN_OP_END && Opcode < ARMISD::FIRST_NUMBER)
 539     return NULL;   // Already selected.
 540
 541   switch (N->getOpcode()) {
 542   default: break;
 543   case ISD::Constant: {
 544     unsigned Val = cast<ConstantSDNode>(N)->getValue();
 545     bool UseCP = true;
 546     if (Subtarget->isThumb())
 547       UseCP = (Val > 255 &&                          // MOV
 548                ~Val > 255 &&                         // MOV + MVN
 549                !ARM_AM::isThumbImmShiftedVal(Val));  // MOV + LSL
 550     else
 551       UseCP = (ARM_AM::getSOImmVal(Val) == -1 &&     // MOV
 552                ARM_AM::getSOImmVal(~Val) == -1 &&    // MVN
 553                !ARM_AM::isSOImmTwoPartVal(Val));     // two instrs.
 554     if (UseCP) {
 555       SDOperand CPIdx =
 556         CurDAG->getTargetConstantPool(ConstantInt::get(Type::Int32Ty, Val),
 557                                       TLI.getPointerTy());
 558
 559       SDNode *ResNode;
 560       if (Subtarget->isThumb())
 561         ResNode = CurDAG->getTargetNode(ARM::tLDRcp, MVT::i32, MVT::Other,
 562                                         CPIdx, CurDAG->getEntryNode());
 563       else {
 564         SDOperand Ops[] = {
 565           CPIdx,
 566           CurDAG->getRegister(0, MVT::i32),
 567           CurDAG->getTargetConstant(0, MVT::i32),
 568           getAL(CurDAG),
 569           CurDAG->getRegister(0, MVT::i32),
 570           CurDAG->getEntryNode()
 571         };
 572         ResNode=CurDAG->getTargetNode(ARM::LDRcp, MVT::i32, MVT::Other, Ops, 6);
 573       }
 574       ReplaceUses(Op, SDOperand(ResNode, 0));
 575       return NULL;
 576     }
 577
 578     // Other cases are autogenerated.
 579     break;
 580   }
 581   case ISD::FrameIndex: {
 582     // Selects to ADDri FI, 0 which in turn will become ADDri SP, imm.
 583     int FI = cast<FrameIndexSDNode>(N)->getIndex();
 584     SDOperand TFI = CurDAG->getTargetFrameIndex(FI, TLI.getPointerTy());
 585     if (Subtarget->isThumb())
 586       return CurDAG->SelectNodeTo(N, ARM::tADDrSPi, MVT::i32, TFI,
 587                                   CurDAG->getTargetConstant(0, MVT::i32));
 588     else {
 589       SDOperand Ops[] = { TFI, CurDAG->getTargetConstant(0, MVT::i32),
 590                           getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
 591                           CurDAG->getRegister(0, MVT::i32) };
 592       return CurDAG->SelectNodeTo(N, ARM::ADDri, MVT::i32, Ops, 5);
 593     }
 594   }
 595   case ISD::ADD: {
 596     // Select add sp, c to tADDhirr.
 597     SDOperand N0 = Op.getOperand(0);
 598     SDOperand N1 = Op.getOperand(1);
 599     RegisterSDNode *LHSR = dyn_cast<RegisterSDNode>(Op.getOperand(0));
 600     RegisterSDNode *RHSR = dyn_cast<RegisterSDNode>(Op.getOperand(1));
 601     if (LHSR && LHSR->getReg() == ARM::SP) {
 602       std::swap(N0, N1);
 603       std::swap(LHSR, RHSR);
 604     }
 605     if (RHSR && RHSR->getReg() == ARM::SP) {
 606       AddToISelQueue(N0);
 607       AddToISelQueue(N1);
 608       return CurDAG->SelectNodeTo(N, ARM::tADDhirr, Op.getValueType(), N0, N1);
 609     }
 610     break;
 611   }
 612   case ISD::MUL:
 613     if (Subtarget->isThumb())
 614       break;
 615     if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op.getOperand(1))) {
 616       unsigned RHSV = C->getValue();
 617       if (!RHSV) break;
 618       if (isPowerOf2_32(RHSV-1)) {  // 2^n+1?
 619         SDOperand V = Op.getOperand(0);
 620         AddToISelQueue(V);
 621         unsigned ShImm = ARM_AM::getSORegOpc(ARM_AM::lsl, Log2_32(RHSV-1));
 622         SDOperand Ops[] = { V, V, CurDAG->getRegister(0, MVT::i32),
 623                             CurDAG->getTargetConstant(ShImm, MVT::i32),
 624                             getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
 625                             CurDAG->getRegister(0, MVT::i32) };
 626         return CurDAG->SelectNodeTo(N, ARM::ADDrs, MVT::i32, Ops, 7);
 627       }
 628       if (isPowerOf2_32(RHSV+1)) {  // 2^n-1?
 629         SDOperand V = Op.getOperand(0);
 630         AddToISelQueue(V);
 631         unsigned ShImm = ARM_AM::getSORegOpc(ARM_AM::lsl, Log2_32(RHSV+1));
 632         SDOperand Ops[] = { V, V, CurDAG->getRegister(0, MVT::i32),
 633                             CurDAG->getTargetConstant(ShImm, MVT::i32),
 634                             getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
 635                             CurDAG->getRegister(0, MVT::i32) };
 636         return CurDAG->SelectNodeTo(N, ARM::RSBrs, MVT::i32, Ops, 7);
 637       }
 638     }
 639     break;
 640   case ARMISD::FMRRD:
 641     AddToISelQueue(Op.getOperand(0));
 642     return CurDAG->getTargetNode(ARM::FMRRD, MVT::i32, MVT::i32,
 643                                  Op.getOperand(0), getAL(CurDAG),
 644                                  CurDAG->getRegister(0, MVT::i32));
 645   case ISD::UMUL_LOHI: {
 646     AddToISelQueue(Op.getOperand(0));
 647     AddToISelQueue(Op.getOperand(1));
 648     SDOperand Ops[] = { Op.getOperand(0), Op.getOperand(1),
 649                         getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
 650                         CurDAG->getRegister(0, MVT::i32) };
 651     return CurDAG->getTargetNode(ARM::UMULL, MVT::i32, MVT::i32, Ops, 5);
 652   }
 653   case ISD::SMUL_LOHI: {
 654     AddToISelQueue(Op.getOperand(0));
 655     AddToISelQueue(Op.getOperand(1));
 656     SDOperand Ops[] = { Op.getOperand(0), Op.getOperand(1),
 657                         getAL(CurDAG), CurDAG->getRegister(0, MVT::i32),
 658                         CurDAG->getRegister(0, MVT::i32) };
 659     return CurDAG->getTargetNode(ARM::SMULL, MVT::i32, MVT::i32, Ops, 5);
 660   }
 661   case ISD::LOAD: {
 662     LoadSDNode *LD = cast<LoadSDNode>(Op);
 663     ISD::MemIndexedMode AM = LD->getAddressingMode();
 664     MVT::ValueType LoadedVT = LD->getMemoryVT();
 665     if (AM != ISD::UNINDEXED) {
 666       SDOperand Offset, AMOpc;
 667       bool isPre = (AM == ISD::PRE_INC) || (AM == ISD::PRE_DEC);
 668       unsigned Opcode = 0;
 669       bool Match = false;
 670       if (LoadedVT == MVT::i32 &&
 671           SelectAddrMode2Offset(Op, LD->getOffset(), Offset, AMOpc)) {
 672         Opcode = isPre ? ARM::LDR_PRE : ARM::LDR_POST;
 673         Match = true;
 674       } else if (LoadedVT == MVT::i16 &&
 675                  SelectAddrMode3Offset(Op, LD->getOffset(), Offset, AMOpc)) {
 676         Match = true;
 677         Opcode = (LD->getExtensionType() == ISD::SEXTLOAD)
 678           ? (isPre ? ARM::LDRSH_PRE : ARM::LDRSH_POST)
 679           : (isPre ? ARM::LDRH_PRE : ARM::LDRH_POST);
 680       } else if (LoadedVT == MVT::i8 || LoadedVT == MVT::i1) {
 681         if (LD->getExtensionType() == ISD::SEXTLOAD) {
 682           if (SelectAddrMode3Offset(Op, LD->getOffset(), Offset, AMOpc)) {
 683             Match = true;
 684             Opcode = isPre ? ARM::LDRSB_PRE : ARM::LDRSB_POST;
 685           }
 686         } else {
 687           if (SelectAddrMode2Offset(Op, LD->getOffset(), Offset, AMOpc)) {
 688             Match = true;
 689             Opcode = isPre ? ARM::LDRB_PRE : ARM::LDRB_POST;
 690           }
 691         }
 692       }
 693
 694       if (Match) {
 695         SDOperand Chain = LD->getChain();
 696         SDOperand Base = LD->getBasePtr();
 697         AddToISelQueue(Chain);
 698         AddToISelQueue(Base);
 699         AddToISelQueue(Offset);
 700         SDOperand Ops[]= { Base, Offset, AMOpc, getAL(CurDAG),
 701                            CurDAG->getRegister(0, MVT::i32), Chain };
 702         return CurDAG->getTargetNode(Opcode, MVT::i32, MVT::i32,
 703                                      MVT::Other, Ops, 6);
 704       }
 705     }
 706     // Other cases are autogenerated.
 707     break;
 708   }
 709   case ARMISD::BRCOND: {
 710     // Pattern: (ARMbrcond:void (bb:Other):$dst, (imm:i32):$cc)
 711     // Emits: (Bcc:void (bb:Other):$dst, (imm:i32):$cc)
 712     // Pattern complexity = 6  cost = 1  size = 0
 713
 714     // Pattern: (ARMbrcond:void (bb:Other):$dst, (imm:i32):$cc)
 715     // Emits: (tBcc:void (bb:Other):$dst, (imm:i32):$cc)
 716     // Pattern complexity = 6  cost = 1  size = 0
 717
 718     unsigned Opc = Subtarget->isThumb() ? ARM::tBcc : ARM::Bcc;
 719     SDOperand Chain = Op.getOperand(0);
 720     SDOperand N1 = Op.getOperand(1);
 721     SDOperand N2 = Op.getOperand(2);
 722     SDOperand N3 = Op.getOperand(3);
 723     SDOperand InFlag = Op.getOperand(4);
 724     assert(N1.getOpcode() == ISD::BasicBlock);
 725     assert(N2.getOpcode() == ISD::Constant);
 726     assert(N3.getOpcode() == ISD::Register);
 727
 728     AddToISelQueue(Chain);
 729     AddToISelQueue(N1);
 730     AddToISelQueue(InFlag);
 731     SDOperand Tmp2 = CurDAG->getTargetConstant(((unsigned)
 732                                cast<ConstantSDNode>(N2)->getValue()), MVT::i32);
 733     SDOperand Ops[] = { N1, Tmp2, N3, Chain, InFlag };
 734     SDNode *ResNode = CurDAG->getTargetNode(Opc, MVT::Other, MVT::Flag, Ops, 5);
 735     Chain = SDOperand(ResNode, 0);
 736     if (Op.Val->getNumValues() == 2) {
 737       InFlag = SDOperand(ResNode, 1);
 738       ReplaceUses(SDOperand(Op.Val, 1), InFlag);
 739     }
 740     ReplaceUses(SDOperand(Op.Val, 0), SDOperand(Chain.Val, Chain.ResNo));
 741     return NULL;
 742   }
 743   case ARMISD::CMOV: {
 744     bool isThumb = Subtarget->isThumb();
 745     MVT::ValueType VT = Op.getValueType();
 746     SDOperand N0 = Op.getOperand(0);
 747     SDOperand N1 = Op.getOperand(1);
 748     SDOperand N2 = Op.getOperand(2);
 749     SDOperand N3 = Op.getOperand(3);
 750     SDOperand InFlag = Op.getOperand(4);
 751     assert(N2.getOpcode() == ISD::Constant);
 752     assert(N3.getOpcode() == ISD::Register);
 753
 754     // Pattern: (ARMcmov:i32 GPR:i32:$false, so_reg:i32:$true, (imm:i32):$cc)
 755     // Emits: (MOVCCs:i32 GPR:i32:$false, so_reg:i32:$true, (imm:i32):$cc)
 756     // Pattern complexity = 18  cost = 1  size = 0
 757     SDOperand CPTmp0;
 758     SDOperand CPTmp1;
 759     SDOperand CPTmp2;
 760     if (!isThumb && VT == MVT::i32 &&
 761         SelectShifterOperandReg(Op, N1, CPTmp0, CPTmp1, CPTmp2)) {
 762       AddToISelQueue(N0);
 763       AddToISelQueue(CPTmp0);
 764       AddToISelQueue(CPTmp1);
 765       AddToISelQueue(CPTmp2);
 766       AddToISelQueue(InFlag);
 767       SDOperand Tmp2 = CurDAG->getTargetConstant(((unsigned)
 768                                cast<ConstantSDNode>(N2)->getValue()), MVT::i32);
 769       SDOperand Ops[] = { N0, CPTmp0, CPTmp1, CPTmp2, Tmp2, N3, InFlag };
 770       return CurDAG->SelectNodeTo(Op.Val, ARM::MOVCCs, MVT::i32, Ops, 7);
 771     }
 772
 773     // Pattern: (ARMcmov:i32 GPR:i32:$false,
 774     //             (imm:i32)<<P:Predicate_so_imm>><<X:so_imm_XFORM>>:$true,
 775     //             (imm:i32):$cc)
 776     // Emits: (MOVCCi:i32 GPR:i32:$false,
 777     //           (so_imm_XFORM:i32 (imm:i32):$true), (imm:i32):$cc)
 778     // Pattern complexity = 10  cost = 1  size = 0
 779     if (VT == MVT::i32 &&
 780         N3.getOpcode() == ISD::Constant &&
 781         Predicate_so_imm(N3.Val)) {
 782       AddToISelQueue(N0);
 783       AddToISelQueue(InFlag);
 784       SDOperand Tmp1 = CurDAG->getTargetConstant(((unsigned)
 785                                cast<ConstantSDNode>(N1)->getValue()), MVT::i32);
 786       Tmp1 = Transform_so_imm_XFORM(Tmp1.Val);
 787       SDOperand Tmp2 = CurDAG->getTargetConstant(((unsigned)
 788                                cast<ConstantSDNode>(N2)->getValue()), MVT::i32);
 789       SDOperand Ops[] = { N0, Tmp1, Tmp2, N3, InFlag };
 790       return CurDAG->SelectNodeTo(Op.Val, ARM::MOVCCi, MVT::i32, Ops, 5);
 791     }
 792
 793     // Pattern: (ARMcmov:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
 794     // Emits: (MOVCCr:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
 795     // Pattern complexity = 6  cost = 1  size = 0
 796     //
 797     // Pattern: (ARMcmov:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
 798     // Emits: (tMOVCCr:i32 GPR:i32:$false, GPR:i32:$true, (imm:i32):$cc)
 799     // Pattern complexity = 6  cost = 11  size = 0
 800     //
 801     // Also FCPYScc and FCPYDcc.
 802     AddToISelQueue(N0);
 803     AddToISelQueue(N1);
 804     AddToISelQueue(InFlag);
 805     SDOperand Tmp2 = CurDAG->getTargetConstant(((unsigned)
 806                                cast<ConstantSDNode>(N2)->getValue()), MVT::i32);
 807     SDOperand Ops[] = { N0, N1, Tmp2, N3, InFlag };
 808     unsigned Opc = 0;
 809     switch (VT) {
 810     default: assert(false && "Illegal conditional move type!");
 811       break;
 812     case MVT::i32:
 813       Opc = isThumb ? ARM::tMOVCCr : ARM::MOVCCr;
 814       break;
 815     case MVT::f32:
 816       Opc = ARM::FCPYScc;
 817       break;
 818     case MVT::f64:
 819       Opc = ARM::FCPYDcc;
 820       break;
 821     }
 822     return CurDAG->SelectNodeTo(Op.Val, Opc, VT, Ops, 5);
 823   }
 824   case ARMISD::CNEG: {
 825     MVT::ValueType VT = Op.getValueType();
 826     SDOperand N0 = Op.getOperand(0);
 827     SDOperand N1 = Op.getOperand(1);
 828     SDOperand N2 = Op.getOperand(2);
 829     SDOperand N3 = Op.getOperand(3);
 830     SDOperand InFlag = Op.getOperand(4);
 831     assert(N2.getOpcode() == ISD::Constant);
 832     assert(N3.getOpcode() == ISD::Register);
 833
 834     AddToISelQueue(N0);
 835     AddToISelQueue(N1);
 836     AddToISelQueue(InFlag);
 837     SDOperand Tmp2 = CurDAG->getTargetConstant(((unsigned)
 838                                cast<ConstantSDNode>(N2)->getValue()), MVT::i32);
 839     SDOperand Ops[] = { N0, N1, Tmp2, N3, InFlag };
 840     unsigned Opc = 0;
 841     switch (VT) {
 842     default: assert(false && "Illegal conditional move type!");
 843       break;
 844     case MVT::f32:
 845       Opc = ARM::FNEGScc;
 846       break;
 847     case MVT::f64:
 848       Opc = ARM::FNEGDcc;
 849       break;
 850     }
 851     return CurDAG->SelectNodeTo(Op.Val, Opc, VT, Ops, 5);
 852   }
 853   }
 854   return SelectCode(Op);
 855 }
 856
 857 /// createARMISelDag - This pass converts a legalized DAG into a
 858 /// ARM-specific DAG, ready for instruction scheduling.
 859 ///
 860 FunctionPass *llvm::createARMISelDag(ARMTargetMachine &TM) {
 861   return new ARMDAGToDAGISel(TM);
 862 }