lib/Target/PowerPC/PPCISelDAGToDAG.cpp

   1 //===-- PPCISelDAGToDAG.cpp - PPC --pattern matching inst selector --------===//
   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 a pattern matching instruction selector for PowerPC,
  11 // converting from a legalized dag to a PPC dag.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #define DEBUG_TYPE "ppc-codegen"
  16 #include "PPC.h"
  17 #include "MCTargetDesc/PPCPredicates.h"
  18 #include "PPCTargetMachine.h"
  19 #include "llvm/CodeGen/MachineFunction.h"
  20 #include "llvm/CodeGen/MachineInstrBuilder.h"
  21 #include "llvm/CodeGen/MachineRegisterInfo.h"
  22 #include "llvm/CodeGen/SelectionDAG.h"
  23 #include "llvm/CodeGen/SelectionDAGISel.h"
  24 #include "llvm/IR/Constants.h"
  25 #include "llvm/IR/Function.h"
  26 #include "llvm/IR/GlobalAlias.h"
  27 #include "llvm/IR/GlobalValue.h"
  28 #include "llvm/IR/GlobalVariable.h"
  29 #include "llvm/IR/Intrinsics.h"
  30 #include "llvm/Support/Debug.h"
  31 #include "llvm/Support/ErrorHandling.h"
  32 #include "llvm/Support/MathExtras.h"
  33 #include "llvm/Support/raw_ostream.h"
  34 #include "llvm/Target/TargetOptions.h"
  35 using namespace llvm;
  36
  37 namespace llvm {
  38   void initializePPCDAGToDAGISelPass(PassRegistry&);
  39 }
  40
  41 namespace {
  42   //===--------------------------------------------------------------------===//
  43   /// PPCDAGToDAGISel - PPC specific code to select PPC machine
  44   /// instructions for SelectionDAG operations.
  45   ///
  46   class PPCDAGToDAGISel : public SelectionDAGISel {
  47     const PPCTargetMachine &TM;
  48     const PPCTargetLowering &PPCLowering;
  49     const PPCSubtarget &PPCSubTarget;
  50     unsigned GlobalBaseReg;
  51   public:
  52     explicit PPCDAGToDAGISel(PPCTargetMachine &tm)
  53       : SelectionDAGISel(tm), TM(tm),
  54         PPCLowering(*TM.getTargetLowering()),
  55         PPCSubTarget(*TM.getSubtargetImpl()) {
  56       initializePPCDAGToDAGISelPass(*PassRegistry::getPassRegistry());
  57     }
  58
  59     virtual bool runOnMachineFunction(MachineFunction &MF) {
  60       // Make sure we re-emit a set of the global base reg if necessary
  61       GlobalBaseReg = 0;
  62       SelectionDAGISel::runOnMachineFunction(MF);
  63
  64       if (!PPCSubTarget.isSVR4ABI())
  65         InsertVRSaveCode(MF);
  66
  67       return true;
  68     }
  69
  70     /// getI32Imm - Return a target constant with the specified value, of type
  71     /// i32.
  72     inline SDValue getI32Imm(unsigned Imm) {
  73       return CurDAG->getTargetConstant(Imm, MVT::i32);
  74     }
  75
  76     /// getI64Imm - Return a target constant with the specified value, of type
  77     /// i64.
  78     inline SDValue getI64Imm(uint64_t Imm) {
  79       return CurDAG->getTargetConstant(Imm, MVT::i64);
  80     }
  81
  82     /// getSmallIPtrImm - Return a target constant of pointer type.
  83     inline SDValue getSmallIPtrImm(unsigned Imm) {
  84       return CurDAG->getTargetConstant(Imm, PPCLowering.getPointerTy());
  85     }
  86
  87     /// isRunOfOnes - Returns true iff Val consists of one contiguous run of 1s
  88     /// with any number of 0s on either side.  The 1s are allowed to wrap from
  89     /// LSB to MSB, so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs.
  90     /// 0x0F0F0000 is not, since all 1s are not contiguous.
  91     static bool isRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME);
  92
  93
  94     /// isRotateAndMask - Returns true if Mask and Shift can be folded into a
  95     /// rotate and mask opcode and mask operation.
  96     static bool isRotateAndMask(SDNode *N, unsigned Mask, bool isShiftMask,
  97                                 unsigned &SH, unsigned &MB, unsigned &ME);
  98
  99     /// getGlobalBaseReg - insert code into the entry mbb to materialize the PIC
 100     /// base register.  Return the virtual register that holds this value.
 101     SDNode *getGlobalBaseReg();
 102
 103     // Select - Convert the specified operand from a target-independent to a
 104     // target-specific node if it hasn't already been changed.
 105     SDNode *Select(SDNode *N);
 106
 107     SDNode *SelectBitfieldInsert(SDNode *N);
 108
 109     /// SelectCC - Select a comparison of the specified values with the
 110     /// specified condition code, returning the CR# of the expression.
 111     SDValue SelectCC(SDValue LHS, SDValue RHS, ISD::CondCode CC, DebugLoc dl);
 112
 113     /// SelectAddrImm - Returns true if the address N can be represented by
 114     /// a base register plus a signed 16-bit displacement [r+imm].
 115     bool SelectAddrImm(SDValue N, SDValue &Disp,
 116                        SDValue &Base) {
 117       return PPCLowering.SelectAddressRegImm(N, Disp, Base, *CurDAG);
 118     }
 119
 120     /// SelectAddrImmOffs - Return true if the operand is valid for a preinc
 121     /// immediate field.  Because preinc imms have already been validated, just
 122     /// accept it.
 123     bool SelectAddrImmOffs(SDValue N, SDValue &Out) const {
 124       if (isa<ConstantSDNode>(N) || N.getOpcode() == PPCISD::Lo ||
 125           N.getOpcode() == ISD::TargetGlobalAddress) {
 126         Out = N;
 127         return true;
 128       }
 129
 130       return false;
 131     }
 132
 133     /// SelectAddrIdxOffs - Return true if the operand is valid for a preinc
 134     /// index field.  Because preinc imms have already been validated, just
 135     /// accept it.
 136     bool SelectAddrIdxOffs(SDValue N, SDValue &Out) const {
 137       if (isa<ConstantSDNode>(N) || N.getOpcode() == PPCISD::Lo ||
 138           N.getOpcode() == ISD::TargetGlobalAddress)
 139         return false;
 140
 141       Out = N;
 142       return true;
 143     }
 144
 145     /// SelectAddrIdx - Given the specified addressed, check to see if it can be
 146     /// represented as an indexed [r+r] operation.  Returns false if it can
 147     /// be represented by [r+imm], which are preferred.
 148     bool SelectAddrIdx(SDValue N, SDValue &Base, SDValue &Index) {
 149       return PPCLowering.SelectAddressRegReg(N, Base, Index, *CurDAG);
 150     }
 151
 152     /// SelectAddrIdxOnly - Given the specified addressed, force it to be
 153     /// represented as an indexed [r+r] operation.
 154     bool SelectAddrIdxOnly(SDValue N, SDValue &Base, SDValue &Index) {
 155       return PPCLowering.SelectAddressRegRegOnly(N, Base, Index, *CurDAG);
 156     }
 157
 158     /// SelectAddrImmShift - Returns true if the address N can be represented by
 159     /// a base register plus a signed 14-bit displacement [r+imm*4].  Suitable
 160     /// for use by STD and friends.
 161     bool SelectAddrImmShift(SDValue N, SDValue &Disp, SDValue &Base) {
 162       return PPCLowering.SelectAddressRegImmShift(N, Disp, Base, *CurDAG);
 163     }
 164
 165     /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
 166     /// inline asm expressions.  It is always correct to compute the value into
 167     /// a register.  The case of adding a (possibly relocatable) constant to a
 168     /// register can be improved, but it is wrong to substitute Reg+Reg for
 169     /// Reg in an asm, because the load or store opcode would have to change.
 170    virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op,
 171                                               char ConstraintCode,
 172                                               std::vector<SDValue> &OutOps) {
 173       OutOps.push_back(Op);
 174       return false;
 175     }
 176
 177     void InsertVRSaveCode(MachineFunction &MF);
 178
 179     virtual const char *getPassName() const {
 180       return "PowerPC DAG->DAG Pattern Instruction Selection";
 181     }
 182
 183 // Include the pieces autogenerated from the target description.
 184 #include "PPCGenDAGISel.inc"
 185
 186 private:
 187     SDNode *SelectSETCC(SDNode *N);
 188   };
 189 }
 190
 191 /// InsertVRSaveCode - Once the entire function has been instruction selected,
 192 /// all virtual registers are created and all machine instructions are built,
 193 /// check to see if we need to save/restore VRSAVE.  If so, do it.
 194 void PPCDAGToDAGISel::InsertVRSaveCode(MachineFunction &Fn) {
 195   // Check to see if this function uses vector registers, which means we have to
 196   // save and restore the VRSAVE register and update it with the regs we use.
 197   //
 198   // In this case, there will be virtual registers of vector type created
 199   // by the scheduler.  Detect them now.
 200   bool HasVectorVReg = false;
 201   for (unsigned i = 0, e = RegInfo->getNumVirtRegs(); i != e; ++i) {
 202     unsigned Reg = TargetRegisterInfo::index2VirtReg(i);
 203     if (RegInfo->getRegClass(Reg) == &PPC::VRRCRegClass) {
 204       HasVectorVReg = true;
 205       break;
 206     }
 207   }
 208   if (!HasVectorVReg) return;  // nothing to do.
 209
 210   // If we have a vector register, we want to emit code into the entry and exit
 211   // blocks to save and restore the VRSAVE register.  We do this here (instead
 212   // of marking all vector instructions as clobbering VRSAVE) for two reasons:
 213   //
 214   // 1. This (trivially) reduces the load on the register allocator, by not
 215   //    having to represent the live range of the VRSAVE register.
 216   // 2. This (more significantly) allows us to create a temporary virtual
 217   //    register to hold the saved VRSAVE value, allowing this temporary to be
 218   //    register allocated, instead of forcing it to be spilled to the stack.
 219
 220   // Create two vregs - one to hold the VRSAVE register that is live-in to the
 221   // function and one for the value after having bits or'd into it.
 222   unsigned InVRSAVE = RegInfo->createVirtualRegister(&PPC::GPRCRegClass);
 223   unsigned UpdatedVRSAVE = RegInfo->createVirtualRegister(&PPC::GPRCRegClass);
 224
 225   const TargetInstrInfo &TII = *TM.getInstrInfo();
 226   MachineBasicBlock &EntryBB = *Fn.begin();
 227   DebugLoc dl;
 228   // Emit the following code into the entry block:
 229   // InVRSAVE = MFVRSAVE
 230   // UpdatedVRSAVE = UPDATE_VRSAVE InVRSAVE
 231   // MTVRSAVE UpdatedVRSAVE
 232   MachineBasicBlock::iterator IP = EntryBB.begin();  // Insert Point
 233   BuildMI(EntryBB, IP, dl, TII.get(PPC::MFVRSAVE), InVRSAVE);
 234   BuildMI(EntryBB, IP, dl, TII.get(PPC::UPDATE_VRSAVE),
 235           UpdatedVRSAVE).addReg(InVRSAVE);
 236   BuildMI(EntryBB, IP, dl, TII.get(PPC::MTVRSAVE)).addReg(UpdatedVRSAVE);
 237
 238   // Find all return blocks, outputting a restore in each epilog.
 239   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
 240     if (!BB->empty() && BB->back().isReturn()) {
 241       IP = BB->end(); --IP;
 242
 243       // Skip over all terminator instructions, which are part of the return
 244       // sequence.
 245       MachineBasicBlock::iterator I2 = IP;
 246       while (I2 != BB->begin() && (--I2)->isTerminator())
 247         IP = I2;
 248
 249       // Emit: MTVRSAVE InVRSave
 250       BuildMI(*BB, IP, dl, TII.get(PPC::MTVRSAVE)).addReg(InVRSAVE);
 251     }
 252   }
 253 }
 254
 255
 256 /// getGlobalBaseReg - Output the instructions required to put the
 257 /// base address to use for accessing globals into a register.
 258 ///
 259 SDNode *PPCDAGToDAGISel::getGlobalBaseReg() {
 260   if (!GlobalBaseReg) {
 261     const TargetInstrInfo &TII = *TM.getInstrInfo();
 262     // Insert the set of GlobalBaseReg into the first MBB of the function
 263     MachineBasicBlock &FirstMBB = MF->front();
 264     MachineBasicBlock::iterator MBBI = FirstMBB.begin();
 265     DebugLoc dl;
 266
 267     if (PPCLowering.getPointerTy() == MVT::i32) {
 268       GlobalBaseReg = RegInfo->createVirtualRegister(&PPC::GPRCRegClass);
 269       BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MovePCtoLR));
 270       BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR), GlobalBaseReg);
 271     } else {
 272       GlobalBaseReg = RegInfo->createVirtualRegister(&PPC::G8RCRegClass);
 273       BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MovePCtoLR8));
 274       BuildMI(FirstMBB, MBBI, dl, TII.get(PPC::MFLR8), GlobalBaseReg);
 275     }
 276   }
 277   return CurDAG->getRegister(GlobalBaseReg,
 278                              PPCLowering.getPointerTy()).getNode();
 279 }
 280
 281 /// isIntS16Immediate - This method tests to see if the node is either a 32-bit
 282 /// or 64-bit immediate, and if the value can be accurately represented as a
 283 /// sign extension from a 16-bit value.  If so, this returns true and the
 284 /// immediate.
 285 static bool isIntS16Immediate(SDNode *N, short &Imm) {
 286   if (N->getOpcode() != ISD::Constant)
 287     return false;
 288
 289   Imm = (short)cast<ConstantSDNode>(N)->getZExtValue();
 290   if (N->getValueType(0) == MVT::i32)
 291     return Imm == (int32_t)cast<ConstantSDNode>(N)->getZExtValue();
 292   else
 293     return Imm == (int64_t)cast<ConstantSDNode>(N)->getZExtValue();
 294 }
 295
 296 static bool isIntS16Immediate(SDValue Op, short &Imm) {
 297   return isIntS16Immediate(Op.getNode(), Imm);
 298 }
 299
 300
 301 /// isInt32Immediate - This method tests to see if the node is a 32-bit constant
 302 /// operand. If so Imm will receive the 32-bit value.
 303 static bool isInt32Immediate(SDNode *N, unsigned &Imm) {
 304   if (N->getOpcode() == ISD::Constant && N->getValueType(0) == MVT::i32) {
 305     Imm = cast<ConstantSDNode>(N)->getZExtValue();
 306     return true;
 307   }
 308   return false;
 309 }
 310
 311 /// isInt64Immediate - This method tests to see if the node is a 64-bit constant
 312 /// operand.  If so Imm will receive the 64-bit value.
 313 static bool isInt64Immediate(SDNode *N, uint64_t &Imm) {
 314   if (N->getOpcode() == ISD::Constant && N->getValueType(0) == MVT::i64) {
 315     Imm = cast<ConstantSDNode>(N)->getZExtValue();
 316     return true;
 317   }
 318   return false;
 319 }
 320
 321 // isInt32Immediate - This method tests to see if a constant operand.
 322 // If so Imm will receive the 32 bit value.
 323 static bool isInt32Immediate(SDValue N, unsigned &Imm) {
 324   return isInt32Immediate(N.getNode(), Imm);
 325 }
 326
 327
 328 // isOpcWithIntImmediate - This method tests to see if the node is a specific
 329 // opcode and that it has a immediate integer right operand.
 330 // If so Imm will receive the 32 bit value.
 331 static bool isOpcWithIntImmediate(SDNode *N, unsigned Opc, unsigned& Imm) {
 332   return N->getOpcode() == Opc
 333          && isInt32Immediate(N->getOperand(1).getNode(), Imm);
 334 }
 335
 336 bool PPCDAGToDAGISel::isRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
 337   if (isShiftedMask_32(Val)) {
 338     // look for the first non-zero bit
 339     MB = CountLeadingZeros_32(Val);
 340     // look for the first zero bit after the run of ones
 341     ME = CountLeadingZeros_32((Val - 1) ^ Val);
 342     return true;
 343   } else {
 344     Val = ~Val; // invert mask
 345     if (isShiftedMask_32(Val)) {
 346       // effectively look for the first zero bit
 347       ME = CountLeadingZeros_32(Val) - 1;
 348       // effectively look for the first one bit after the run of zeros
 349       MB = CountLeadingZeros_32((Val - 1) ^ Val) + 1;
 350       return true;
 351     }
 352   }
 353   // no run present
 354   return false;
 355 }
 356
 357 bool PPCDAGToDAGISel::isRotateAndMask(SDNode *N, unsigned Mask,
 358                                       bool isShiftMask, unsigned &SH,
 359                                       unsigned &MB, unsigned &ME) {
 360   // Don't even go down this path for i64, since different logic will be
 361   // necessary for rldicl/rldicr/rldimi.
 362   if (N->getValueType(0) != MVT::i32)
 363     return false;
 364
 365   unsigned Shift  = 32;
 366   unsigned Indeterminant = ~0;  // bit mask marking indeterminant results
 367   unsigned Opcode = N->getOpcode();
 368   if (N->getNumOperands() != 2 ||
 369       !isInt32Immediate(N->getOperand(1).getNode(), Shift) || (Shift > 31))
 370     return false;
 371
 372   if (Opcode == ISD::SHL) {
 373     // apply shift left to mask if it comes first
 374     if (isShiftMask) Mask = Mask << Shift;
 375     // determine which bits are made indeterminant by shift
 376     Indeterminant = ~(0xFFFFFFFFu << Shift);
 377   } else if (Opcode == ISD::SRL) {
 378     // apply shift right to mask if it comes first
 379     if (isShiftMask) Mask = Mask >> Shift;
 380     // determine which bits are made indeterminant by shift
 381     Indeterminant = ~(0xFFFFFFFFu >> Shift);
 382     // adjust for the left rotate
 383     Shift = 32 - Shift;
 384   } else if (Opcode == ISD::ROTL) {
 385     Indeterminant = 0;
 386   } else {
 387     return false;
 388   }
 389
 390   // if the mask doesn't intersect any Indeterminant bits
 391   if (Mask && !(Mask & Indeterminant)) {
 392     SH = Shift & 31;
 393     // make sure the mask is still a mask (wrap arounds may not be)
 394     return isRunOfOnes(Mask, MB, ME);
 395   }
 396   return false;
 397 }
 398
 399 /// SelectBitfieldInsert - turn an or of two masked values into
 400 /// the rotate left word immediate then mask insert (rlwimi) instruction.
 401 SDNode *PPCDAGToDAGISel::SelectBitfieldInsert(SDNode *N) {
 402   SDValue Op0 = N->getOperand(0);
 403   SDValue Op1 = N->getOperand(1);
 404   DebugLoc dl = N->getDebugLoc();
 405
 406   APInt LKZ, LKO, RKZ, RKO;
 407   CurDAG->ComputeMaskedBits(Op0, LKZ, LKO);
 408   CurDAG->ComputeMaskedBits(Op1, RKZ, RKO);
 409
 410   unsigned TargetMask = LKZ.getZExtValue();
 411   unsigned InsertMask = RKZ.getZExtValue();
 412
 413   if ((TargetMask | InsertMask) == 0xFFFFFFFF) {
 414     unsigned Op0Opc = Op0.getOpcode();
 415     unsigned Op1Opc = Op1.getOpcode();
 416     unsigned Value, SH = 0;
 417     TargetMask = ~TargetMask;
 418     InsertMask = ~InsertMask;
 419
 420     // If the LHS has a foldable shift and the RHS does not, then swap it to the
 421     // RHS so that we can fold the shift into the insert.
 422     if (Op0Opc == ISD::AND && Op1Opc == ISD::AND) {
 423       if (Op0.getOperand(0).getOpcode() == ISD::SHL ||
 424           Op0.getOperand(0).getOpcode() == ISD::SRL) {
 425         if (Op1.getOperand(0).getOpcode() != ISD::SHL &&
 426             Op1.getOperand(0).getOpcode() != ISD::SRL) {
 427           std::swap(Op0, Op1);
 428           std::swap(Op0Opc, Op1Opc);
 429           std::swap(TargetMask, InsertMask);
 430         }
 431       }
 432     } else if (Op0Opc == ISD::SHL || Op0Opc == ISD::SRL) {
 433       if (Op1Opc == ISD::AND && Op1.getOperand(0).getOpcode() != ISD::SHL &&
 434           Op1.getOperand(0).getOpcode() != ISD::SRL) {
 435         std::swap(Op0, Op1);
 436         std::swap(Op0Opc, Op1Opc);
 437         std::swap(TargetMask, InsertMask);
 438       }
 439     }
 440
 441     unsigned MB, ME;
 442     if (InsertMask && isRunOfOnes(InsertMask, MB, ME)) {
 443       SDValue Tmp1, Tmp2;
 444
 445       if ((Op1Opc == ISD::SHL || Op1Opc == ISD::SRL) &&
 446           isInt32Immediate(Op1.getOperand(1), Value)) {
 447         Op1 = Op1.getOperand(0);
 448         SH  = (Op1Opc == ISD::SHL) ? Value : 32 - Value;
 449       }
 450       if (Op1Opc == ISD::AND) {
 451         unsigned SHOpc = Op1.getOperand(0).getOpcode();
 452         if ((SHOpc == ISD::SHL || SHOpc == ISD::SRL) &&
 453             isInt32Immediate(Op1.getOperand(0).getOperand(1), Value)) {
 454           Op1 = Op1.getOperand(0).getOperand(0);
 455           SH  = (SHOpc == ISD::SHL) ? Value : 32 - Value;
 456         } else {
 457           Op1 = Op1.getOperand(0);
 458         }
 459       }
 460
 461       SH &= 31;
 462       SDValue Ops[] = { Op0, Op1, getI32Imm(SH), getI32Imm(MB),
 463                           getI32Imm(ME) };
 464       return CurDAG->getMachineNode(PPC::RLWIMI, dl, MVT::i32, Ops, 5);
 465     }
 466   }
 467   return 0;
 468 }
 469
 470 /// SelectCC - Select a comparison of the specified values with the specified
 471 /// condition code, returning the CR# of the expression.
 472 SDValue PPCDAGToDAGISel::SelectCC(SDValue LHS, SDValue RHS,
 473                                     ISD::CondCode CC, DebugLoc dl) {
 474   // Always select the LHS.
 475   unsigned Opc;
 476
 477   if (LHS.getValueType() == MVT::i32) {
 478     unsigned Imm;
 479     if (CC == ISD::SETEQ || CC == ISD::SETNE) {
 480       if (isInt32Immediate(RHS, Imm)) {
 481         // SETEQ/SETNE comparison with 16-bit immediate, fold it.
 482         if (isUInt<16>(Imm))
 483           return SDValue(CurDAG->getMachineNode(PPC::CMPLWI, dl, MVT::i32, LHS,
 484                                                 getI32Imm(Imm & 0xFFFF)), 0);
 485         // If this is a 16-bit signed immediate, fold it.
 486         if (isInt<16>((int)Imm))
 487           return SDValue(CurDAG->getMachineNode(PPC::CMPWI, dl, MVT::i32, LHS,
 488                                                 getI32Imm(Imm & 0xFFFF)), 0);
 489
 490         // For non-equality comparisons, the default code would materialize the
 491         // constant, then compare against it, like this:
 492         //   lis r2, 4660
 493         //   ori r2, r2, 22136
 494         //   cmpw cr0, r3, r2
 495         // Since we are just comparing for equality, we can emit this instead:
 496         //   xoris r0,r3,0x1234
 497         //   cmplwi cr0,r0,0x5678
 498         //   beq cr0,L6
 499         SDValue Xor(CurDAG->getMachineNode(PPC::XORIS, dl, MVT::i32, LHS,
 500                                            getI32Imm(Imm >> 16)), 0);
 501         return SDValue(CurDAG->getMachineNode(PPC::CMPLWI, dl, MVT::i32, Xor,
 502                                               getI32Imm(Imm & 0xFFFF)), 0);
 503       }
 504       Opc = PPC::CMPLW;
 505     } else if (ISD::isUnsignedIntSetCC(CC)) {
 506       if (isInt32Immediate(RHS, Imm) && isUInt<16>(Imm))
 507         return SDValue(CurDAG->getMachineNode(PPC::CMPLWI, dl, MVT::i32, LHS,
 508                                               getI32Imm(Imm & 0xFFFF)), 0);
 509       Opc = PPC::CMPLW;
 510     } else {
 511       short SImm;
 512       if (isIntS16Immediate(RHS, SImm))
 513         return SDValue(CurDAG->getMachineNode(PPC::CMPWI, dl, MVT::i32, LHS,
 514                                               getI32Imm((int)SImm & 0xFFFF)),
 515                          0);
 516       Opc = PPC::CMPW;
 517     }
 518   } else if (LHS.getValueType() == MVT::i64) {
 519     uint64_t Imm;
 520     if (CC == ISD::SETEQ || CC == ISD::SETNE) {
 521       if (isInt64Immediate(RHS.getNode(), Imm)) {
 522         // SETEQ/SETNE comparison with 16-bit immediate, fold it.
 523         if (isUInt<16>(Imm))
 524           return SDValue(CurDAG->getMachineNode(PPC::CMPLDI, dl, MVT::i64, LHS,
 525                                                 getI32Imm(Imm & 0xFFFF)), 0);
 526         // If this is a 16-bit signed immediate, fold it.
 527         if (isInt<16>(Imm))
 528           return SDValue(CurDAG->getMachineNode(PPC::CMPDI, dl, MVT::i64, LHS,
 529                                                 getI32Imm(Imm & 0xFFFF)), 0);
 530
 531         // For non-equality comparisons, the default code would materialize the
 532         // constant, then compare against it, like this:
 533         //   lis r2, 4660
 534         //   ori r2, r2, 22136
 535         //   cmpd cr0, r3, r2
 536         // Since we are just comparing for equality, we can emit this instead:
 537         //   xoris r0,r3,0x1234
 538         //   cmpldi cr0,r0,0x5678
 539         //   beq cr0,L6
 540         if (isUInt<32>(Imm)) {
 541           SDValue Xor(CurDAG->getMachineNode(PPC::XORIS8, dl, MVT::i64, LHS,
 542                                              getI64Imm(Imm >> 16)), 0);
 543           return SDValue(CurDAG->getMachineNode(PPC::CMPLDI, dl, MVT::i64, Xor,
 544                                                 getI64Imm(Imm & 0xFFFF)), 0);
 545         }
 546       }
 547       Opc = PPC::CMPLD;
 548     } else if (ISD::isUnsignedIntSetCC(CC)) {
 549       if (isInt64Immediate(RHS.getNode(), Imm) && isUInt<16>(Imm))
 550         return SDValue(CurDAG->getMachineNode(PPC::CMPLDI, dl, MVT::i64, LHS,
 551                                               getI64Imm(Imm & 0xFFFF)), 0);
 552       Opc = PPC::CMPLD;
 553     } else {
 554       short SImm;
 555       if (isIntS16Immediate(RHS, SImm))
 556         return SDValue(CurDAG->getMachineNode(PPC::CMPDI, dl, MVT::i64, LHS,
 557                                               getI64Imm(SImm & 0xFFFF)),
 558                          0);
 559       Opc = PPC::CMPD;
 560     }
 561   } else if (LHS.getValueType() == MVT::f32) {
 562     Opc = PPC::FCMPUS;
 563   } else {
 564     assert(LHS.getValueType() == MVT::f64 && "Unknown vt!");
 565     Opc = PPC::FCMPUD;
 566   }
 567   return SDValue(CurDAG->getMachineNode(Opc, dl, MVT::i32, LHS, RHS), 0);
 568 }
 569
 570 static PPC::Predicate getPredicateForSetCC(ISD::CondCode CC) {
 571   switch (CC) {
 572   case ISD::SETUEQ:
 573   case ISD::SETONE:
 574   case ISD::SETOLE:
 575   case ISD::SETOGE:
 576     llvm_unreachable("Should be lowered by legalize!");
 577   default: llvm_unreachable("Unknown condition!");
 578   case ISD::SETOEQ:
 579   case ISD::SETEQ:  return PPC::PRED_EQ;
 580   case ISD::SETUNE:
 581   case ISD::SETNE:  return PPC::PRED_NE;
 582   case ISD::SETOLT:
 583   case ISD::SETLT:  return PPC::PRED_LT;
 584   case ISD::SETULE:
 585   case ISD::SETLE:  return PPC::PRED_LE;
 586   case ISD::SETOGT:
 587   case ISD::SETGT:  return PPC::PRED_GT;
 588   case ISD::SETUGE:
 589   case ISD::SETGE:  return PPC::PRED_GE;
 590   case ISD::SETO:   return PPC::PRED_NU;
 591   case ISD::SETUO:  return PPC::PRED_UN;
 592     // These two are invalid for floating point.  Assume we have int.
 593   case ISD::SETULT: return PPC::PRED_LT;
 594   case ISD::SETUGT: return PPC::PRED_GT;
 595   }
 596 }
 597
 598 /// getCRIdxForSetCC - Return the index of the condition register field
 599 /// associated with the SetCC condition, and whether or not the field is
 600 /// treated as inverted.  That is, lt = 0; ge = 0 inverted.
 601 ///
 602 /// If this returns with Other != -1, then the returned comparison is an or of
 603 /// two simpler comparisons.  In this case, Invert is guaranteed to be false.
 604 static unsigned getCRIdxForSetCC(ISD::CondCode CC, bool &Invert, int &Other) {
 605   Invert = false;
 606   Other = -1;
 607   switch (CC) {
 608   default: llvm_unreachable("Unknown condition!");
 609   case ISD::SETOLT:
 610   case ISD::SETLT:  return 0;                  // Bit #0 = SETOLT
 611   case ISD::SETOGT:
 612   case ISD::SETGT:  return 1;                  // Bit #1 = SETOGT
 613   case ISD::SETOEQ:
 614   case ISD::SETEQ:  return 2;                  // Bit #2 = SETOEQ
 615   case ISD::SETUO:  return 3;                  // Bit #3 = SETUO
 616   case ISD::SETUGE:
 617   case ISD::SETGE:  Invert = true; return 0;   // !Bit #0 = SETUGE
 618   case ISD::SETULE:
 619   case ISD::SETLE:  Invert = true; return 1;   // !Bit #1 = SETULE
 620   case ISD::SETUNE:
 621   case ISD::SETNE:  Invert = true; return 2;   // !Bit #2 = SETUNE
 622   case ISD::SETO:   Invert = true; return 3;   // !Bit #3 = SETO
 623   case ISD::SETUEQ:
 624   case ISD::SETOGE:
 625   case ISD::SETOLE:
 626   case ISD::SETONE:
 627     llvm_unreachable("Invalid branch code: should be expanded by legalize");
 628   // These are invalid for floating point.  Assume integer.
 629   case ISD::SETULT: return 0;
 630   case ISD::SETUGT: return 1;
 631   }
 632 }
 633
 634 // getVCmpInst: return the vector compare instruction for the specified
 635 // vector type and condition code. Since this is for altivec specific code,
 636 // only support the altivec types (v16i8, v8i16, v4i32, and v4f32).
 637 static unsigned int getVCmpInst(MVT::SimpleValueType VecVT, ISD::CondCode CC) {
 638   switch (CC) {
 639     case ISD::SETEQ:
 640     case ISD::SETUEQ:
 641     case ISD::SETNE:
 642     case ISD::SETUNE:
 643       if (VecVT == MVT::v16i8)
 644         return PPC::VCMPEQUB;
 645       else if (VecVT == MVT::v8i16)
 646         return PPC::VCMPEQUH;
 647       else if (VecVT == MVT::v4i32)
 648         return PPC::VCMPEQUW;
 649       // v4f32 != v4f32 could be translate to unordered not equal
 650       else if (VecVT == MVT::v4f32)
 651         return PPC::VCMPEQFP;
 652       break;
 653     case ISD::SETLT:
 654     case ISD::SETGT:
 655     case ISD::SETLE:
 656     case ISD::SETGE:
 657       if (VecVT == MVT::v16i8)
 658         return PPC::VCMPGTSB;
 659       else if (VecVT == MVT::v8i16)
 660         return PPC::VCMPGTSH;
 661       else if (VecVT == MVT::v4i32)
 662         return PPC::VCMPGTSW;
 663       else if (VecVT == MVT::v4f32)
 664         return PPC::VCMPGTFP;
 665       break;
 666     case ISD::SETULT:
 667     case ISD::SETUGT:
 668     case ISD::SETUGE:
 669     case ISD::SETULE:
 670       if (VecVT == MVT::v16i8)
 671         return PPC::VCMPGTUB;
 672       else if (VecVT == MVT::v8i16)
 673         return PPC::VCMPGTUH;
 674       else if (VecVT == MVT::v4i32)
 675         return PPC::VCMPGTUW;
 676       break;
 677     case ISD::SETOEQ:
 678       if (VecVT == MVT::v4f32)
 679         return PPC::VCMPEQFP;
 680       break;
 681     case ISD::SETOLT:
 682     case ISD::SETOGT:
 683     case ISD::SETOLE:
 684       if (VecVT == MVT::v4f32)
 685         return PPC::VCMPGTFP;
 686       break;
 687     case ISD::SETOGE:
 688       if (VecVT == MVT::v4f32)
 689         return PPC::VCMPGEFP;
 690       break;
 691     default:
 692       break;
 693   }
 694   llvm_unreachable("Invalid integer vector compare condition");
 695 }
 696
 697 // getVCmpEQInst: return the equal compare instruction for the specified vector
 698 // type. Since this is for altivec specific code, only support the altivec
 699 // types (v16i8, v8i16, v4i32, and v4f32).
 700 static unsigned int getVCmpEQInst(MVT::SimpleValueType VecVT) {
 701   switch (VecVT) {
 702     case MVT::v16i8:
 703       return PPC::VCMPEQUB;
 704     case MVT::v8i16:
 705       return PPC::VCMPEQUH;
 706     case MVT::v4i32:
 707       return PPC::VCMPEQUW;
 708     case MVT::v4f32:
 709       return PPC::VCMPEQFP;
 710     default:
 711       llvm_unreachable("Invalid integer vector compare condition");
 712   }
 713 }
 714
 715
 716 SDNode *PPCDAGToDAGISel::SelectSETCC(SDNode *N) {
 717   DebugLoc dl = N->getDebugLoc();
 718   unsigned Imm;
 719   ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(2))->get();
 720   EVT PtrVT = CurDAG->getTargetLoweringInfo().getPointerTy();
 721   bool isPPC64 = (PtrVT == MVT::i64);
 722
 723   if (isInt32Immediate(N->getOperand(1), Imm)) {
 724     // We can codegen setcc op, imm very efficiently compared to a brcond.
 725     // Check for those cases here.
 726     // setcc op, 0
 727     if (Imm == 0) {
 728       SDValue Op = N->getOperand(0);
 729       switch (CC) {
 730       default: break;
 731       case ISD::SETEQ: {
 732         Op = SDValue(CurDAG->getMachineNode(PPC::CNTLZW, dl, MVT::i32, Op), 0);
 733         SDValue Ops[] = { Op, getI32Imm(27), getI32Imm(5), getI32Imm(31) };
 734         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
 735       }
 736       case ISD::SETNE: {
 737         if (isPPC64) break;
 738         SDValue AD =
 739           SDValue(CurDAG->getMachineNode(PPC::ADDIC, dl, MVT::i32, MVT::Glue,
 740                                          Op, getI32Imm(~0U)), 0);
 741         return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, AD, Op,
 742                                     AD.getValue(1));
 743       }
 744       case ISD::SETLT: {
 745         SDValue Ops[] = { Op, getI32Imm(1), getI32Imm(31), getI32Imm(31) };
 746         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
 747       }
 748       case ISD::SETGT: {
 749         SDValue T =
 750           SDValue(CurDAG->getMachineNode(PPC::NEG, dl, MVT::i32, Op), 0);
 751         T = SDValue(CurDAG->getMachineNode(PPC::ANDC, dl, MVT::i32, T, Op), 0);
 752         SDValue Ops[] = { T, getI32Imm(1), getI32Imm(31), getI32Imm(31) };
 753         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
 754       }
 755       }
 756     } else if (Imm == ~0U) {        // setcc op, -1
 757       SDValue Op = N->getOperand(0);
 758       switch (CC) {
 759       default: break;
 760       case ISD::SETEQ:
 761         if (isPPC64) break;
 762         Op = SDValue(CurDAG->getMachineNode(PPC::ADDIC, dl, MVT::i32, MVT::Glue,
 763                                             Op, getI32Imm(1)), 0);
 764         return CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
 765                               SDValue(CurDAG->getMachineNode(PPC::LI, dl,
 766                                                              MVT::i32,
 767                                                              getI32Imm(0)), 0),
 768                                       Op.getValue(1));
 769       case ISD::SETNE: {
 770         if (isPPC64) break;
 771         Op = SDValue(CurDAG->getMachineNode(PPC::NOR, dl, MVT::i32, Op, Op), 0);
 772         SDNode *AD = CurDAG->getMachineNode(PPC::ADDIC, dl, MVT::i32, MVT::Glue,
 773                                             Op, getI32Imm(~0U));
 774         return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, SDValue(AD, 0),
 775                                     Op, SDValue(AD, 1));
 776       }
 777       case ISD::SETLT: {
 778         SDValue AD = SDValue(CurDAG->getMachineNode(PPC::ADDI, dl, MVT::i32, Op,
 779                                                     getI32Imm(1)), 0);
 780         SDValue AN = SDValue(CurDAG->getMachineNode(PPC::AND, dl, MVT::i32, AD,
 781                                                     Op), 0);
 782         SDValue Ops[] = { AN, getI32Imm(1), getI32Imm(31), getI32Imm(31) };
 783         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
 784       }
 785       case ISD::SETGT: {
 786         SDValue Ops[] = { Op, getI32Imm(1), getI32Imm(31), getI32Imm(31) };
 787         Op = SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops, 4),
 788                      0);
 789         return CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Op,
 790                                     getI32Imm(1));
 791       }
 792       }
 793     }
 794   }
 795
 796   SDValue LHS = N->getOperand(0);
 797   SDValue RHS = N->getOperand(1);
 798
 799   // Altivec Vector compare instructions do not set any CR register by default and
 800   // vector compare operations return the same type as the operands.
 801   if (LHS.getValueType().isVector()) {
 802     EVT VecVT = LHS.getValueType();
 803     MVT::SimpleValueType VT = VecVT.getSimpleVT().SimpleTy;
 804     unsigned int VCmpInst = getVCmpInst(VT, CC);
 805
 806     switch (CC) {
 807       case ISD::SETEQ:
 808       case ISD::SETOEQ:
 809       case ISD::SETUEQ:
 810         return CurDAG->SelectNodeTo(N, VCmpInst, VecVT, LHS, RHS);
 811       case ISD::SETNE:
 812       case ISD::SETONE:
 813       case ISD::SETUNE: {
 814         SDValue VCmp(CurDAG->getMachineNode(VCmpInst, dl, VecVT, LHS, RHS), 0);
 815         return CurDAG->SelectNodeTo(N, PPC::VNOR, VecVT, VCmp, VCmp);
 816       }
 817       case ISD::SETLT:
 818       case ISD::SETOLT:
 819       case ISD::SETULT:
 820         return CurDAG->SelectNodeTo(N, VCmpInst, VecVT, RHS, LHS);
 821       case ISD::SETGT:
 822       case ISD::SETOGT:
 823       case ISD::SETUGT:
 824         return CurDAG->SelectNodeTo(N, VCmpInst, VecVT, LHS, RHS);
 825       case ISD::SETGE:
 826       case ISD::SETOGE:
 827       case ISD::SETUGE: {
 828         // Small optimization: Altivec provides a 'Vector Compare Greater Than
 829         // or Equal To' instruction (vcmpgefp), so in this case there is no
 830         // need for extra logic for the equal compare.
 831         if (VecVT.getSimpleVT().isFloatingPoint()) {
 832           return CurDAG->SelectNodeTo(N, VCmpInst, VecVT, LHS, RHS);
 833         } else {
 834           SDValue VCmpGT(CurDAG->getMachineNode(VCmpInst, dl, VecVT, LHS, RHS), 0);
 835           unsigned int VCmpEQInst = getVCmpEQInst(VT);
 836           SDValue VCmpEQ(CurDAG->getMachineNode(VCmpEQInst, dl, VecVT, LHS, RHS), 0);
 837           return CurDAG->SelectNodeTo(N, PPC::VOR, VecVT, VCmpGT, VCmpEQ);
 838         }
 839       }
 840       case ISD::SETLE:
 841       case ISD::SETOLE:
 842       case ISD::SETULE: {
 843         SDValue VCmpLE(CurDAG->getMachineNode(VCmpInst, dl, VecVT, RHS, LHS), 0);
 844         unsigned int VCmpEQInst = getVCmpEQInst(VT);
 845         SDValue VCmpEQ(CurDAG->getMachineNode(VCmpEQInst, dl, VecVT, LHS, RHS), 0);
 846         return CurDAG->SelectNodeTo(N, PPC::VOR, VecVT, VCmpLE, VCmpEQ);
 847       }
 848       default:
 849         llvm_unreachable("Invalid vector compare type: should be expanded by legalize");
 850     }
 851   }
 852
 853   bool Inv;
 854   int OtherCondIdx;
 855   unsigned Idx = getCRIdxForSetCC(CC, Inv, OtherCondIdx);
 856   SDValue CCReg = SelectCC(LHS, RHS, CC, dl);
 857   SDValue IntCR;
 858
 859   // Force the ccreg into CR7.
 860   SDValue CR7Reg = CurDAG->getRegister(PPC::CR7, MVT::i32);
 861
 862   SDValue InFlag(0, 0);  // Null incoming flag value.
 863   CCReg = CurDAG->getCopyToReg(CurDAG->getEntryNode(), dl, CR7Reg, CCReg,
 864                                InFlag).getValue(1);
 865
 866   if (PPCSubTarget.hasMFOCRF() && OtherCondIdx == -1)
 867     IntCR = SDValue(CurDAG->getMachineNode(PPC::MFOCRF, dl, MVT::i32, CR7Reg,
 868                                            CCReg), 0);
 869   else
 870     IntCR = SDValue(CurDAG->getMachineNode(PPC::MFCRpseud, dl, MVT::i32,
 871                                            CR7Reg, CCReg), 0);
 872
 873   SDValue Ops[] = { IntCR, getI32Imm((32-(3-Idx)) & 31),
 874                       getI32Imm(31), getI32Imm(31) };
 875   if (OtherCondIdx == -1 && !Inv)
 876     return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
 877
 878   // Get the specified bit.
 879   SDValue Tmp =
 880     SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops, 4), 0);
 881   if (Inv) {
 882     assert(OtherCondIdx == -1 && "Can't have split plus negation");
 883     return CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Tmp, getI32Imm(1));
 884   }
 885
 886   // Otherwise, we have to turn an operation like SETONE -> SETOLT | SETOGT.
 887   // We already got the bit for the first part of the comparison (e.g. SETULE).
 888
 889   // Get the other bit of the comparison.
 890   Ops[1] = getI32Imm((32-(3-OtherCondIdx)) & 31);
 891   SDValue OtherCond =
 892     SDValue(CurDAG->getMachineNode(PPC::RLWINM, dl, MVT::i32, Ops, 4), 0);
 893
 894   return CurDAG->SelectNodeTo(N, PPC::OR, MVT::i32, Tmp, OtherCond);
 895 }
 896
 897
 898 // Select - Convert the specified operand from a target-independent to a
 899 // target-specific node if it hasn't already been changed.
 900 SDNode *PPCDAGToDAGISel::Select(SDNode *N) {
 901   DebugLoc dl = N->getDebugLoc();
 902   if (N->isMachineOpcode())
 903     return NULL;   // Already selected.
 904
 905   switch (N->getOpcode()) {
 906   default: break;
 907
 908   case ISD::Constant: {
 909     if (N->getValueType(0) == MVT::i64) {
 910       // Get 64 bit value.
 911       int64_t Imm = cast<ConstantSDNode>(N)->getZExtValue();
 912       // Assume no remaining bits.
 913       unsigned Remainder = 0;
 914       // Assume no shift required.
 915       unsigned Shift = 0;
 916
 917       // If it can't be represented as a 32 bit value.
 918       if (!isInt<32>(Imm)) {
 919         Shift = CountTrailingZeros_64(Imm);
 920         int64_t ImmSh = static_cast<uint64_t>(Imm) >> Shift;
 921
 922         // If the shifted value fits 32 bits.
 923         if (isInt<32>(ImmSh)) {
 924           // Go with the shifted value.
 925           Imm = ImmSh;
 926         } else {
 927           // Still stuck with a 64 bit value.
 928           Remainder = Imm;
 929           Shift = 32;
 930           Imm >>= 32;
 931         }
 932       }
 933
 934       // Intermediate operand.
 935       SDNode *Result;
 936
 937       // Handle first 32 bits.
 938       unsigned Lo = Imm & 0xFFFF;
 939       unsigned Hi = (Imm >> 16) & 0xFFFF;
 940
 941       // Simple value.
 942       if (isInt<16>(Imm)) {
 943        // Just the Lo bits.
 944         Result = CurDAG->getMachineNode(PPC::LI8, dl, MVT::i64, getI32Imm(Lo));
 945       } else if (Lo) {
 946         // Handle the Hi bits.
 947         unsigned OpC = Hi ? PPC::LIS8 : PPC::LI8;
 948         Result = CurDAG->getMachineNode(OpC, dl, MVT::i64, getI32Imm(Hi));
 949         // And Lo bits.
 950         Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64,
 951                                         SDValue(Result, 0), getI32Imm(Lo));
 952       } else {
 953        // Just the Hi bits.
 954         Result = CurDAG->getMachineNode(PPC::LIS8, dl, MVT::i64, getI32Imm(Hi));
 955       }
 956
 957       // If no shift, we're done.
 958       if (!Shift) return Result;
 959
 960       // Shift for next step if the upper 32-bits were not zero.
 961       if (Imm) {
 962         Result = CurDAG->getMachineNode(PPC::RLDICR, dl, MVT::i64,
 963                                         SDValue(Result, 0),
 964                                         getI32Imm(Shift),
 965                                         getI32Imm(63 - Shift));
 966       }
 967
 968       // Add in the last bits as required.
 969       if ((Hi = (Remainder >> 16) & 0xFFFF)) {
 970         Result = CurDAG->getMachineNode(PPC::ORIS8, dl, MVT::i64,
 971                                         SDValue(Result, 0), getI32Imm(Hi));
 972       }
 973       if ((Lo = Remainder & 0xFFFF)) {
 974         Result = CurDAG->getMachineNode(PPC::ORI8, dl, MVT::i64,
 975                                         SDValue(Result, 0), getI32Imm(Lo));
 976       }
 977
 978       return Result;
 979     }
 980     break;
 981   }
 982
 983   case ISD::SETCC:
 984     return SelectSETCC(N);
 985   case PPCISD::GlobalBaseReg:
 986     return getGlobalBaseReg();
 987
 988   case ISD::FrameIndex: {
 989     int FI = cast<FrameIndexSDNode>(N)->getIndex();
 990     SDValue TFI = CurDAG->getTargetFrameIndex(FI, N->getValueType(0));
 991     unsigned Opc = N->getValueType(0) == MVT::i32 ? PPC::ADDI : PPC::ADDI8;
 992     if (N->hasOneUse())
 993       return CurDAG->SelectNodeTo(N, Opc, N->getValueType(0), TFI,
 994                                   getSmallIPtrImm(0));
 995     return CurDAG->getMachineNode(Opc, dl, N->getValueType(0), TFI,
 996                                   getSmallIPtrImm(0));
 997   }
 998
 999   case PPCISD::MFCR: {
1000     SDValue InFlag = N->getOperand(1);
1001     // Use MFOCRF if supported.
1002     if (PPCSubTarget.hasMFOCRF())
1003       return CurDAG->getMachineNode(PPC::MFOCRF, dl, MVT::i32,
1004                                     N->getOperand(0), InFlag);
1005     else
1006       return CurDAG->getMachineNode(PPC::MFCRpseud, dl, MVT::i32,
1007                                     N->getOperand(0), InFlag);
1008   }
1009
1010   case ISD::SDIV: {
1011     // FIXME: since this depends on the setting of the carry flag from the srawi
1012     //        we should really be making notes about that for the scheduler.
1013     // FIXME: It sure would be nice if we could cheaply recognize the
1014     //        srl/add/sra pattern the dag combiner will generate for this as
1015     //        sra/addze rather than having to handle sdiv ourselves.  oh well.
1016     unsigned Imm;
1017     if (isInt32Immediate(N->getOperand(1), Imm)) {
1018       SDValue N0 = N->getOperand(0);
1019       if ((signed)Imm > 0 && isPowerOf2_32(Imm)) {
1020         SDNode *Op =
1021           CurDAG->getMachineNode(PPC::SRAWI, dl, MVT::i32, MVT::Glue,
1022                                  N0, getI32Imm(Log2_32(Imm)));
1023         return CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
1024                                     SDValue(Op, 0), SDValue(Op, 1));
1025       } else if ((signed)Imm < 0 && isPowerOf2_32(-Imm)) {
1026         SDNode *Op =
1027           CurDAG->getMachineNode(PPC::SRAWI, dl, MVT::i32, MVT::Glue,
1028                                  N0, getI32Imm(Log2_32(-Imm)));
1029         SDValue PT =
1030           SDValue(CurDAG->getMachineNode(PPC::ADDZE, dl, MVT::i32,
1031                                          SDValue(Op, 0), SDValue(Op, 1)),
1032                     0);
1033         return CurDAG->SelectNodeTo(N, PPC::NEG, MVT::i32, PT);
1034       }
1035     }
1036
1037     // Other cases are autogenerated.
1038     break;
1039   }
1040
1041   case ISD::LOAD: {
1042     // Handle preincrement loads.
1043     LoadSDNode *LD = cast<LoadSDNode>(N);
1044     EVT LoadedVT = LD->getMemoryVT();
1045
1046     // Normal loads are handled by code generated from the .td file.
1047     if (LD->getAddressingMode() != ISD::PRE_INC)
1048       break;
1049
1050     SDValue Offset = LD->getOffset();
1051     if (isa<ConstantSDNode>(Offset) ||
1052         Offset.getOpcode() == ISD::TargetGlobalAddress) {
1053
1054       unsigned Opcode;
1055       bool isSExt = LD->getExtensionType() == ISD::SEXTLOAD;
1056       if (LD->getValueType(0) != MVT::i64) {
1057         // Handle PPC32 integer and normal FP loads.
1058         assert((!isSExt || LoadedVT == MVT::i16) && "Invalid sext update load");
1059         switch (LoadedVT.getSimpleVT().SimpleTy) {
1060           default: llvm_unreachable("Invalid PPC load type!");
1061           case MVT::f64: Opcode = PPC::LFDU; break;
1062           case MVT::f32: Opcode = PPC::LFSU; break;
1063           case MVT::i32: Opcode = PPC::LWZU; break;
1064           case MVT::i16: Opcode = isSExt ? PPC::LHAU : PPC::LHZU; break;
1065           case MVT::i1:
1066           case MVT::i8:  Opcode = PPC::LBZU; break;
1067         }
1068       } else {
1069         assert(LD->getValueType(0) == MVT::i64 && "Unknown load result type!");
1070         assert((!isSExt || LoadedVT == MVT::i16) && "Invalid sext update load");
1071         switch (LoadedVT.getSimpleVT().SimpleTy) {
1072           default: llvm_unreachable("Invalid PPC load type!");
1073           case MVT::i64: Opcode = PPC::LDU; break;
1074           case MVT::i32: Opcode = PPC::LWZU8; break;
1075           case MVT::i16: Opcode = isSExt ? PPC::LHAU8 : PPC::LHZU8; break;
1076           case MVT::i1:
1077           case MVT::i8:  Opcode = PPC::LBZU8; break;
1078         }
1079       }
1080
1081       SDValue Chain = LD->getChain();
1082       SDValue Base = LD->getBasePtr();
1083       SDValue Ops[] = { Offset, Base, Chain };
1084       return CurDAG->getMachineNode(Opcode, dl, LD->getValueType(0),
1085                                     PPCLowering.getPointerTy(),
1086                                     MVT::Other, Ops, 3);
1087     } else {
1088       unsigned Opcode;
1089       bool isSExt = LD->getExtensionType() == ISD::SEXTLOAD;
1090       if (LD->getValueType(0) != MVT::i64) {
1091         // Handle PPC32 integer and normal FP loads.
1092         assert((!isSExt || LoadedVT == MVT::i16) && "Invalid sext update load");
1093         switch (LoadedVT.getSimpleVT().SimpleTy) {
1094           default: llvm_unreachable("Invalid PPC load type!");
1095           case MVT::f64: Opcode = PPC::LFDUX; break;
1096           case MVT::f32: Opcode = PPC::LFSUX; break;
1097           case MVT::i32: Opcode = PPC::LWZUX; break;
1098           case MVT::i16: Opcode = isSExt ? PPC::LHAUX : PPC::LHZUX; break;
1099           case MVT::i1:
1100           case MVT::i8:  Opcode = PPC::LBZUX; break;
1101         }
1102       } else {
1103         assert(LD->getValueType(0) == MVT::i64 && "Unknown load result type!");
1104         assert((!isSExt || LoadedVT == MVT::i16 || LoadedVT == MVT::i32) &&
1105                "Invalid sext update load");
1106         switch (LoadedVT.getSimpleVT().SimpleTy) {
1107           default: llvm_unreachable("Invalid PPC load type!");
1108           case MVT::i64: Opcode = PPC::LDUX; break;
1109           case MVT::i32: Opcode = isSExt ? PPC::LWAUX  : PPC::LWZUX8; break;
1110           case MVT::i16: Opcode = isSExt ? PPC::LHAUX8 : PPC::LHZUX8; break;
1111           case MVT::i1:
1112           case MVT::i8:  Opcode = PPC::LBZUX8; break;
1113         }
1114       }
1115
1116       SDValue Chain = LD->getChain();
1117       SDValue Base = LD->getBasePtr();
1118       SDValue Ops[] = { Offset, Base, Chain };
1119       return CurDAG->getMachineNode(Opcode, dl, LD->getValueType(0),
1120                                     PPCLowering.getPointerTy(),
1121                                     MVT::Other, Ops, 3);
1122     }
1123   }
1124
1125   case ISD::AND: {
1126     unsigned Imm, Imm2, SH, MB, ME;
1127     uint64_t Imm64;
1128
1129     // If this is an and of a value rotated between 0 and 31 bits and then and'd
1130     // with a mask, emit rlwinm
1131     if (isInt32Immediate(N->getOperand(1), Imm) &&
1132         isRotateAndMask(N->getOperand(0).getNode(), Imm, false, SH, MB, ME)) {
1133       SDValue Val = N->getOperand(0).getOperand(0);
1134       SDValue Ops[] = { Val, getI32Imm(SH), getI32Imm(MB), getI32Imm(ME) };
1135       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
1136     }
1137     // If this is just a masked value where the input is not handled above, and
1138     // is not a rotate-left (handled by a pattern in the .td file), emit rlwinm
1139     if (isInt32Immediate(N->getOperand(1), Imm) &&
1140         isRunOfOnes(Imm, MB, ME) &&
1141         N->getOperand(0).getOpcode() != ISD::ROTL) {
1142       SDValue Val = N->getOperand(0);
1143       SDValue Ops[] = { Val, getI32Imm(0), getI32Imm(MB), getI32Imm(ME) };
1144       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
1145     }
1146     // If this is a 64-bit zero-extension mask, emit rldicl.
1147     if (isInt64Immediate(N->getOperand(1).getNode(), Imm64) &&
1148         isMask_64(Imm64)) {
1149       SDValue Val = N->getOperand(0);
1150       MB = 64 - CountTrailingOnes_64(Imm64);
1151       SDValue Ops[] = { Val, getI32Imm(0), getI32Imm(MB) };
1152       return CurDAG->SelectNodeTo(N, PPC::RLDICL, MVT::i64, Ops, 3);
1153     }
1154     // AND X, 0 -> 0, not "rlwinm 32".
1155     if (isInt32Immediate(N->getOperand(1), Imm) && (Imm == 0)) {
1156       ReplaceUses(SDValue(N, 0), N->getOperand(1));
1157       return NULL;
1158     }
1159     // ISD::OR doesn't get all the bitfield insertion fun.
1160     // (and (or x, c1), c2) where isRunOfOnes(~(c1^c2)) is a bitfield insert
1161     if (isInt32Immediate(N->getOperand(1), Imm) &&
1162         N->getOperand(0).getOpcode() == ISD::OR &&
1163         isInt32Immediate(N->getOperand(0).getOperand(1), Imm2)) {
1164       unsigned MB, ME;
1165       Imm = ~(Imm^Imm2);
1166       if (isRunOfOnes(Imm, MB, ME)) {
1167         SDValue Ops[] = { N->getOperand(0).getOperand(0),
1168                             N->getOperand(0).getOperand(1),
1169                             getI32Imm(0), getI32Imm(MB),getI32Imm(ME) };
1170         return CurDAG->getMachineNode(PPC::RLWIMI, dl, MVT::i32, Ops, 5);
1171       }
1172     }
1173
1174     // Other cases are autogenerated.
1175     break;
1176   }
1177   case ISD::OR:
1178     if (N->getValueType(0) == MVT::i32)
1179       if (SDNode *I = SelectBitfieldInsert(N))
1180         return I;
1181
1182     // Other cases are autogenerated.
1183     break;
1184   case ISD::SHL: {
1185     unsigned Imm, SH, MB, ME;
1186     if (isOpcWithIntImmediate(N->getOperand(0).getNode(), ISD::AND, Imm) &&
1187         isRotateAndMask(N, Imm, true, SH, MB, ME)) {
1188       SDValue Ops[] = { N->getOperand(0).getOperand(0),
1189                           getI32Imm(SH), getI32Imm(MB), getI32Imm(ME) };
1190       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
1191     }
1192
1193     // Other cases are autogenerated.
1194     break;
1195   }
1196   case ISD::SRL: {
1197     unsigned Imm, SH, MB, ME;
1198     if (isOpcWithIntImmediate(N->getOperand(0).getNode(), ISD::AND, Imm) &&
1199         isRotateAndMask(N, Imm, true, SH, MB, ME)) {
1200       SDValue Ops[] = { N->getOperand(0).getOperand(0),
1201                           getI32Imm(SH), getI32Imm(MB), getI32Imm(ME) };
1202       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
1203     }
1204
1205     // Other cases are autogenerated.
1206     break;
1207   }
1208   case ISD::SELECT_CC: {
1209     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(4))->get();
1210     EVT PtrVT = CurDAG->getTargetLoweringInfo().getPointerTy();
1211     bool isPPC64 = (PtrVT == MVT::i64);
1212
1213     // Handle the setcc cases here.  select_cc lhs, 0, 1, 0, cc
1214     if (!isPPC64)
1215       if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N->getOperand(1)))
1216         if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N->getOperand(2)))
1217           if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N->getOperand(3)))
1218             if (N1C->isNullValue() && N3C->isNullValue() &&
1219                 N2C->getZExtValue() == 1ULL && CC == ISD::SETNE &&
1220                 // FIXME: Implement this optzn for PPC64.
1221                 N->getValueType(0) == MVT::i32) {
1222               SDNode *Tmp =
1223                 CurDAG->getMachineNode(PPC::ADDIC, dl, MVT::i32, MVT::Glue,
1224                                        N->getOperand(0), getI32Imm(~0U));
1225               return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32,
1226                                           SDValue(Tmp, 0), N->getOperand(0),
1227                                           SDValue(Tmp, 1));
1228             }
1229
1230     SDValue CCReg = SelectCC(N->getOperand(0), N->getOperand(1), CC, dl);
1231     unsigned BROpc = getPredicateForSetCC(CC);
1232
1233     unsigned SelectCCOp;
1234     if (N->getValueType(0) == MVT::i32)
1235       SelectCCOp = PPC::SELECT_CC_I4;
1236     else if (N->getValueType(0) == MVT::i64)
1237       SelectCCOp = PPC::SELECT_CC_I8;
1238     else if (N->getValueType(0) == MVT::f32)
1239       SelectCCOp = PPC::SELECT_CC_F4;
1240     else if (N->getValueType(0) == MVT::f64)
1241       SelectCCOp = PPC::SELECT_CC_F8;
1242     else
1243       SelectCCOp = PPC::SELECT_CC_VRRC;
1244
1245     SDValue Ops[] = { CCReg, N->getOperand(2), N->getOperand(3),
1246                         getI32Imm(BROpc) };
1247     return CurDAG->SelectNodeTo(N, SelectCCOp, N->getValueType(0), Ops, 4);
1248   }
1249   case PPCISD::COND_BRANCH: {
1250     // Op #0 is the Chain.
1251     // Op #1 is the PPC::PRED_* number.
1252     // Op #2 is the CR#
1253     // Op #3 is the Dest MBB
1254     // Op #4 is the Flag.
1255     // Prevent PPC::PRED_* from being selected into LI.
1256     SDValue Pred =
1257       getI32Imm(cast<ConstantSDNode>(N->getOperand(1))->getZExtValue());
1258     SDValue Ops[] = { Pred, N->getOperand(2), N->getOperand(3),
1259       N->getOperand(0), N->getOperand(4) };
1260     return CurDAG->SelectNodeTo(N, PPC::BCC, MVT::Other, Ops, 5);
1261   }
1262   case ISD::BR_CC: {
1263     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(1))->get();
1264     SDValue CondCode = SelectCC(N->getOperand(2), N->getOperand(3), CC, dl);
1265     SDValue Ops[] = { getI32Imm(getPredicateForSetCC(CC)), CondCode,
1266                         N->getOperand(4), N->getOperand(0) };
1267     return CurDAG->SelectNodeTo(N, PPC::BCC, MVT::Other, Ops, 4);
1268   }
1269   case ISD::BRIND: {
1270     // FIXME: Should custom lower this.
1271     SDValue Chain = N->getOperand(0);
1272     SDValue Target = N->getOperand(1);
1273     unsigned Opc = Target.getValueType() == MVT::i32 ? PPC::MTCTR : PPC::MTCTR8;
1274     unsigned Reg = Target.getValueType() == MVT::i32 ? PPC::BCTR : PPC::BCTR8;
1275     Chain = SDValue(CurDAG->getMachineNode(Opc, dl, MVT::Glue, Target,
1276                                            Chain), 0);
1277     return CurDAG->SelectNodeTo(N, Reg, MVT::Other, Chain);
1278   }
1279   case PPCISD::TOC_ENTRY: {
1280     assert (PPCSubTarget.isPPC64() && "Only supported for 64-bit ABI");
1281
1282     // For medium code model, we generate two instructions as described
1283     // below.  Otherwise we allow SelectCodeCommon to handle this, selecting
1284     // one of LDtoc, LDtocJTI, and LDtocCPT.
1285     if (TM.getCodeModel() != CodeModel::Medium)
1286       break;
1287
1288     // The first source operand is a TargetGlobalAddress or a
1289     // TargetJumpTable.  If it is an externally defined symbol, a symbol
1290     // with common linkage, a function address, or a jump table address,
1291     // we generate:
1292     //   LDtocL(<ga:@sym>, ADDIStocHA(%X2, <ga:@sym>))
1293     // Otherwise we generate:
1294     //   ADDItocL(ADDIStocHA(%X2, <ga:@sym>), <ga:@sym>)
1295     SDValue GA = N->getOperand(0);
1296     SDValue TOCbase = N->getOperand(1);
1297     SDNode *Tmp = CurDAG->getMachineNode(PPC::ADDIStocHA, dl, MVT::i64,
1298                                         TOCbase, GA);
1299
1300     if (isa<JumpTableSDNode>(GA))
1301       return CurDAG->getMachineNode(PPC::LDtocL, dl, MVT::i64, GA,
1302                                     SDValue(Tmp, 0));
1303
1304     if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(GA)) {
1305       const GlobalValue *GValue = G->getGlobal();
1306       const GlobalAlias *GAlias = dyn_cast<GlobalAlias>(GValue);
1307       const GlobalValue *RealGValue = GAlias ?
1308         GAlias->resolveAliasedGlobal(false) : GValue;
1309       const GlobalVariable *GVar = dyn_cast<GlobalVariable>(RealGValue);
1310       assert((GVar || isa<Function>(RealGValue)) &&
1311              "Unexpected global value subclass!");
1312
1313       // An external variable is one without an initializer.  For these,
1314       // for variables with common linkage, and for Functions, generate
1315       // the LDtocL form.
1316       if (!GVar || !GVar->hasInitializer() || RealGValue->hasCommonLinkage() ||
1317           RealGValue->hasAvailableExternallyLinkage())
1318         return CurDAG->getMachineNode(PPC::LDtocL, dl, MVT::i64, GA,
1319                                       SDValue(Tmp, 0));
1320     }
1321
1322     return CurDAG->getMachineNode(PPC::ADDItocL, dl, MVT::i64,
1323                                   SDValue(Tmp, 0), GA);
1324   }
1325   case PPCISD::VADD_SPLAT: {
1326     // This expands into one of three sequences, depending on whether
1327     // the first operand is odd or even, positive or negative.
1328     assert(isa<ConstantSDNode>(N->getOperand(0)) &&
1329            isa<ConstantSDNode>(N->getOperand(1)) &&
1330            "Invalid operand on VADD_SPLAT!");
1331
1332     int Elt     = N->getConstantOperandVal(0);
1333     int EltSize = N->getConstantOperandVal(1);
1334     unsigned Opc1, Opc2, Opc3;
1335     EVT VT;
1336
1337     if (EltSize == 1) {
1338       Opc1 = PPC::VSPLTISB;
1339       Opc2 = PPC::VADDUBM;
1340       Opc3 = PPC::VSUBUBM;
1341       VT = MVT::v16i8;
1342     } else if (EltSize == 2) {
1343       Opc1 = PPC::VSPLTISH;
1344       Opc2 = PPC::VADDUHM;
1345       Opc3 = PPC::VSUBUHM;
1346       VT = MVT::v8i16;
1347     } else {
1348       assert(EltSize == 4 && "Invalid element size on VADD_SPLAT!");
1349       Opc1 = PPC::VSPLTISW;
1350       Opc2 = PPC::VADDUWM;
1351       Opc3 = PPC::VSUBUWM;
1352       VT = MVT::v4i32;
1353     }
1354
1355     if ((Elt & 1) == 0) {
1356       // Elt is even, in the range [-32,-18] + [16,30].
1357       //
1358       // Convert: VADD_SPLAT elt, size
1359       // Into:    tmp = VSPLTIS[BHW] elt
1360       //          VADDU[BHW]M tmp, tmp
1361       // Where:   [BHW] = B for size = 1, H for size = 2, W for size = 4
1362       SDValue EltVal = getI32Imm(Elt >> 1);
1363       SDNode *Tmp = CurDAG->getMachineNode(Opc1, dl, VT, EltVal);
1364       SDValue TmpVal = SDValue(Tmp, 0);
1365       return CurDAG->getMachineNode(Opc2, dl, VT, TmpVal, TmpVal);
1366
1367     } else if (Elt > 0) {
1368       // Elt is odd and positive, in the range [17,31].
1369       //
1370       // Convert: VADD_SPLAT elt, size
1371       // Into:    tmp1 = VSPLTIS[BHW] elt-16
1372       //          tmp2 = VSPLTIS[BHW] -16
1373       //          VSUBU[BHW]M tmp1, tmp2
1374       SDValue EltVal = getI32Imm(Elt - 16);
1375       SDNode *Tmp1 = CurDAG->getMachineNode(Opc1, dl, VT, EltVal);
1376       EltVal = getI32Imm(-16);
1377       SDNode *Tmp2 = CurDAG->getMachineNode(Opc1, dl, VT, EltVal);
1378       return CurDAG->getMachineNode(Opc3, dl, VT, SDValue(Tmp1, 0),
1379                                     SDValue(Tmp2, 0));
1380
1381     } else {
1382       // Elt is odd and negative, in the range [-31,-17].
1383       //
1384       // Convert: VADD_SPLAT elt, size
1385       // Into:    tmp1 = VSPLTIS[BHW] elt+16
1386       //          tmp2 = VSPLTIS[BHW] -16
1387       //          VADDU[BHW]M tmp1, tmp2
1388       SDValue EltVal = getI32Imm(Elt + 16);
1389       SDNode *Tmp1 = CurDAG->getMachineNode(Opc1, dl, VT, EltVal);
1390       EltVal = getI32Imm(-16);
1391       SDNode *Tmp2 = CurDAG->getMachineNode(Opc1, dl, VT, EltVal);
1392       return CurDAG->getMachineNode(Opc2, dl, VT, SDValue(Tmp1, 0),
1393                                     SDValue(Tmp2, 0));
1394     }
1395   }
1396   }
1397
1398   return SelectCode(N);
1399 }
1400
1401
1402
1403 /// createPPCISelDag - This pass converts a legalized DAG into a
1404 /// PowerPC-specific DAG, ready for instruction scheduling.
1405 ///
1406 FunctionPass *llvm::createPPCISelDag(PPCTargetMachine &TM) {
1407   return new PPCDAGToDAGISel(TM);
1408 }
1409
1410 static void initializePassOnce(PassRegistry &Registry) {
1411   const char *Name = "PowerPC DAG->DAG Pattern Instruction Selection";
1412   PassInfo *PI = new PassInfo(Name, "ppc-codegen", &SelectionDAGISel::ID, 0,
1413                               false, false);
1414   Registry.registerPass(*PI, true);
1415 }
1416
1417 void llvm::initializePPCDAGToDAGISelPass(PassRegistry &Registry) {
1418   CALL_ONCE_INITIALIZATION(initializePassOnce);
1419 }
1420