lib/Target/PowerPC/PPCISelDAGToDAG.cpp

   1 //===-- PPCISelDAGToDAG.cpp - PPC --pattern matching inst selector --------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Chris Lattner and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines a pattern matching instruction selector for PowerPC,
  11 // converting from a legalized dag to a PPC dag.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "PPC.h"
  16 #include "PPCTargetMachine.h"
  17 #include "PPCISelLowering.h"
  18 #include "PPCHazardRecognizers.h"
  19 #include "llvm/CodeGen/MachineInstrBuilder.h"
  20 #include "llvm/CodeGen/MachineFunction.h"
  21 #include "llvm/CodeGen/SSARegMap.h"
  22 #include "llvm/CodeGen/SelectionDAG.h"
  23 #include "llvm/CodeGen/SelectionDAGISel.h"
  24 #include "llvm/Target/TargetOptions.h"
  25 #include "llvm/ADT/Statistic.h"
  26 #include "llvm/Constants.h"
  27 #include "llvm/GlobalValue.h"
  28 #include "llvm/Intrinsics.h"
  29 #include "llvm/Support/Debug.h"
  30 #include "llvm/Support/MathExtras.h"
  31 #include "llvm/Support/Visibility.h"
  32 #include <iostream>
  33 #include <queue>
  34 #include <set>
  35 using namespace llvm;
  36
  37 namespace {
  38   Statistic<> FrameOff("ppc-codegen", "Number of frame idx offsets collapsed");
  39
  40   //===--------------------------------------------------------------------===//
  41   /// PPCDAGToDAGISel - PPC specific code to select PPC machine
  42   /// instructions for SelectionDAG operations.
  43   ///
  44   class VISIBILITY_HIDDEN PPCDAGToDAGISel : public SelectionDAGISel {
  45     PPCTargetMachine &TM;
  46     PPCTargetLowering PPCLowering;
  47     unsigned GlobalBaseReg;
  48   public:
  49     PPCDAGToDAGISel(PPCTargetMachine &tm)
  50       : SelectionDAGISel(PPCLowering), TM(tm),
  51         PPCLowering(*TM.getTargetLowering()) {}
  52
  53     virtual bool runOnFunction(Function &Fn) {
  54       // Make sure we re-emit a set of the global base reg if necessary
  55       GlobalBaseReg = 0;
  56       SelectionDAGISel::runOnFunction(Fn);
  57
  58       InsertVRSaveCode(Fn);
  59       return true;
  60     }
  61
  62     /// getI32Imm - Return a target constant with the specified value, of type
  63     /// i32.
  64     inline SDOperand getI32Imm(unsigned Imm) {
  65       return CurDAG->getTargetConstant(Imm, MVT::i32);
  66     }
  67
  68     /// getI64Imm - Return a target constant with the specified value, of type
  69     /// i64.
  70     inline SDOperand getI64Imm(uint64_t Imm) {
  71       return CurDAG->getTargetConstant(Imm, MVT::i64);
  72     }
  73
  74     /// getSmallIPtrImm - Return a target constant of pointer type.
  75     inline SDOperand getSmallIPtrImm(unsigned Imm) {
  76       return CurDAG->getTargetConstant(Imm, PPCLowering.getPointerTy());
  77     }
  78
  79
  80     /// getGlobalBaseReg - insert code into the entry mbb to materialize the PIC
  81     /// base register.  Return the virtual register that holds this value.
  82     SDOperand getGlobalBaseReg();
  83
  84     // Select - Convert the specified operand from a target-independent to a
  85     // target-specific node if it hasn't already been changed.
  86     SDNode *Select(SDOperand &Result, SDOperand Op);
  87
  88     SDNode *SelectBitfieldInsert(SDNode *N);
  89
  90     /// SelectCC - Select a comparison of the specified values with the
  91     /// specified condition code, returning the CR# of the expression.
  92     SDOperand SelectCC(SDOperand LHS, SDOperand RHS, ISD::CondCode CC);
  93
  94     /// SelectAddrImm - Returns true if the address N can be represented by
  95     /// a base register plus a signed 16-bit displacement [r+imm].
  96     bool SelectAddrImm(SDOperand N, SDOperand &Disp, SDOperand &Base);
  97
  98     /// SelectAddrIdx - Given the specified addressed, check to see if it can be
  99     /// represented as an indexed [r+r] operation.  Returns false if it can
 100     /// be represented by [r+imm], which are preferred.
 101     bool SelectAddrIdx(SDOperand N, SDOperand &Base, SDOperand &Index);
 102
 103     /// SelectAddrIdxOnly - Given the specified addressed, force it to be
 104     /// represented as an indexed [r+r] operation.
 105     bool SelectAddrIdxOnly(SDOperand N, SDOperand &Base, SDOperand &Index);
 106
 107     /// SelectAddrImmShift - Returns true if the address N can be represented by
 108     /// a base register plus a signed 14-bit displacement [r+imm*4].  Suitable
 109     /// for use by STD and friends.
 110     bool SelectAddrImmShift(SDOperand N, SDOperand &Disp, SDOperand &Base);
 111
 112     /// SelectInlineAsmMemoryOperand - Implement addressing mode selection for
 113     /// inline asm expressions.
 114     virtual bool SelectInlineAsmMemoryOperand(const SDOperand &Op,
 115                                               char ConstraintCode,
 116                                               std::vector<SDOperand> &OutOps,
 117                                               SelectionDAG &DAG) {
 118       SDOperand Op0, Op1;
 119       switch (ConstraintCode) {
 120       default: return true;
 121       case 'm':   // memory
 122         if (!SelectAddrIdx(Op, Op0, Op1))
 123           SelectAddrImm(Op, Op0, Op1);
 124         break;
 125       case 'o':   // offsetable
 126         if (!SelectAddrImm(Op, Op0, Op1)) {
 127           Op0 = Op;
 128           AddToISelQueue(Op0);     // r+0.
 129           Op1 = getSmallIPtrImm(0);
 130         }
 131         break;
 132       case 'v':   // not offsetable
 133         SelectAddrIdxOnly(Op, Op0, Op1);
 134         break;
 135       }
 136
 137       OutOps.push_back(Op0);
 138       OutOps.push_back(Op1);
 139       return false;
 140     }
 141
 142     SDOperand BuildSDIVSequence(SDNode *N);
 143     SDOperand BuildUDIVSequence(SDNode *N);
 144
 145     /// InstructionSelectBasicBlock - This callback is invoked by
 146     /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 147     virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
 148
 149     void InsertVRSaveCode(Function &Fn);
 150
 151     virtual const char *getPassName() const {
 152       return "PowerPC DAG->DAG Pattern Instruction Selection";
 153     }
 154
 155     /// CreateTargetHazardRecognizer - Return the hazard recognizer to use for
 156     /// this target when scheduling the DAG.
 157     virtual HazardRecognizer *CreateTargetHazardRecognizer() {
 158       // Should use subtarget info to pick the right hazard recognizer.  For
 159       // now, always return a PPC970 recognizer.
 160       const TargetInstrInfo *II = PPCLowering.getTargetMachine().getInstrInfo();
 161       assert(II && "No InstrInfo?");
 162       return new PPCHazardRecognizer970(*II);
 163     }
 164
 165 // Include the pieces autogenerated from the target description.
 166 #include "PPCGenDAGISel.inc"
 167
 168 private:
 169     SDNode *SelectSETCC(SDOperand Op);
 170     SDNode *MySelect_PPCbctrl(SDOperand N);
 171     SDNode *MySelect_PPCcall(SDOperand N);
 172   };
 173 }
 174
 175 /// InstructionSelectBasicBlock - This callback is invoked by
 176 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 177 void PPCDAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
 178   DEBUG(BB->dump());
 179
 180   // Select target instructions for the DAG.
 181   DAG.setRoot(SelectRoot(DAG.getRoot()));
 182   DAG.RemoveDeadNodes();
 183
 184   // Emit machine code to BB.
 185   ScheduleAndEmitDAG(DAG);
 186 }
 187
 188 /// InsertVRSaveCode - Once the entire function has been instruction selected,
 189 /// all virtual registers are created and all machine instructions are built,
 190 /// check to see if we need to save/restore VRSAVE.  If so, do it.
 191 void PPCDAGToDAGISel::InsertVRSaveCode(Function &F) {
 192   // Check to see if this function uses vector registers, which means we have to
 193   // save and restore the VRSAVE register and update it with the regs we use.
 194   //
 195   // In this case, there will be virtual registers of vector type type created
 196   // by the scheduler.  Detect them now.
 197   MachineFunction &Fn = MachineFunction::get(&F);
 198   SSARegMap *RegMap = Fn.getSSARegMap();
 199   bool HasVectorVReg = false;
 200   for (unsigned i = MRegisterInfo::FirstVirtualRegister,
 201        e = RegMap->getLastVirtReg()+1; i != e; ++i)
 202     if (RegMap->getRegClass(i) == &PPC::VRRCRegClass) {
 203       HasVectorVReg = true;
 204       break;
 205     }
 206   if (!HasVectorVReg) return;  // nothing to do.
 207
 208   // If we have a vector register, we want to emit code into the entry and exit
 209   // blocks to save and restore the VRSAVE register.  We do this here (instead
 210   // of marking all vector instructions as clobbering VRSAVE) for two reasons:
 211   //
 212   // 1. This (trivially) reduces the load on the register allocator, by not
 213   //    having to represent the live range of the VRSAVE register.
 214   // 2. This (more significantly) allows us to create a temporary virtual
 215   //    register to hold the saved VRSAVE value, allowing this temporary to be
 216   //    register allocated, instead of forcing it to be spilled to the stack.
 217
 218   // Create two vregs - one to hold the VRSAVE register that is live-in to the
 219   // function and one for the value after having bits or'd into it.
 220   unsigned InVRSAVE = RegMap->createVirtualRegister(&PPC::GPRCRegClass);
 221   unsigned UpdatedVRSAVE = RegMap->createVirtualRegister(&PPC::GPRCRegClass);
 222
 223   MachineBasicBlock &EntryBB = *Fn.begin();
 224   // Emit the following code into the entry block:
 225   // InVRSAVE = MFVRSAVE
 226   // UpdatedVRSAVE = UPDATE_VRSAVE InVRSAVE
 227   // MTVRSAVE UpdatedVRSAVE
 228   MachineBasicBlock::iterator IP = EntryBB.begin();  // Insert Point
 229   BuildMI(EntryBB, IP, PPC::MFVRSAVE, 0, InVRSAVE);
 230   BuildMI(EntryBB, IP, PPC::UPDATE_VRSAVE, 1, UpdatedVRSAVE).addReg(InVRSAVE);
 231   BuildMI(EntryBB, IP, PPC::MTVRSAVE, 1).addReg(UpdatedVRSAVE);
 232
 233   // Find all return blocks, outputting a restore in each epilog.
 234   const TargetInstrInfo &TII = *TM.getInstrInfo();
 235   for (MachineFunction::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
 236     if (!BB->empty() && TII.isReturn(BB->back().getOpcode())) {
 237       IP = BB->end(); --IP;
 238
 239       // Skip over all terminator instructions, which are part of the return
 240       // sequence.
 241       MachineBasicBlock::iterator I2 = IP;
 242       while (I2 != BB->begin() && TII.isTerminatorInstr((--I2)->getOpcode()))
 243         IP = I2;
 244
 245       // Emit: MTVRSAVE InVRSave
 246       BuildMI(*BB, IP, PPC::MTVRSAVE, 1).addReg(InVRSAVE);
 247     }
 248   }
 249 }
 250
 251
 252 /// getGlobalBaseReg - Output the instructions required to put the
 253 /// base address to use for accessing globals into a register.
 254 ///
 255 SDOperand PPCDAGToDAGISel::getGlobalBaseReg() {
 256   if (!GlobalBaseReg) {
 257     // Insert the set of GlobalBaseReg into the first MBB of the function
 258     MachineBasicBlock &FirstMBB = BB->getParent()->front();
 259     MachineBasicBlock::iterator MBBI = FirstMBB.begin();
 260     SSARegMap *RegMap = BB->getParent()->getSSARegMap();
 261
 262     if (PPCLowering.getPointerTy() == MVT::i32)
 263       GlobalBaseReg = RegMap->createVirtualRegister(PPC::GPRCRegisterClass);
 264     else
 265       GlobalBaseReg = RegMap->createVirtualRegister(PPC::G8RCRegisterClass);
 266
 267     BuildMI(FirstMBB, MBBI, PPC::MovePCtoLR, 0, PPC::LR);
 268     BuildMI(FirstMBB, MBBI, PPC::MFLR, 1, GlobalBaseReg);
 269   }
 270   return CurDAG->getRegister(GlobalBaseReg, PPCLowering.getPointerTy());
 271 }
 272
 273 /// isIntS16Immediate - This method tests to see if the node is either a 32-bit
 274 /// or 64-bit immediate, and if the value can be accurately represented as a
 275 /// sign extension from a 16-bit value.  If so, this returns true and the
 276 /// immediate.
 277 static bool isIntS16Immediate(SDNode *N, short &Imm) {
 278   if (N->getOpcode() != ISD::Constant)
 279     return false;
 280
 281   Imm = (short)cast<ConstantSDNode>(N)->getValue();
 282   if (N->getValueType(0) == MVT::i32)
 283     return Imm == (int32_t)cast<ConstantSDNode>(N)->getValue();
 284   else
 285     return Imm == (int64_t)cast<ConstantSDNode>(N)->getValue();
 286 }
 287
 288 static bool isIntS16Immediate(SDOperand Op, short &Imm) {
 289   return isIntS16Immediate(Op.Val, Imm);
 290 }
 291
 292
 293 /// isInt32Immediate - This method tests to see if the node is a 32-bit constant
 294 /// operand. If so Imm will receive the 32-bit value.
 295 static bool isInt32Immediate(SDNode *N, unsigned &Imm) {
 296   if (N->getOpcode() == ISD::Constant && N->getValueType(0) == MVT::i32) {
 297     Imm = cast<ConstantSDNode>(N)->getValue();
 298     return true;
 299   }
 300   return false;
 301 }
 302
 303 /// isInt64Immediate - This method tests to see if the node is a 64-bit constant
 304 /// operand.  If so Imm will receive the 64-bit value.
 305 static bool isInt64Immediate(SDNode *N, uint64_t &Imm) {
 306   if (N->getOpcode() == ISD::Constant && N->getValueType(0) == MVT::i32) {
 307     Imm = cast<ConstantSDNode>(N)->getValue();
 308     return true;
 309   }
 310   return false;
 311 }
 312
 313 // isInt32Immediate - This method tests to see if a constant operand.
 314 // If so Imm will receive the 32 bit value.
 315 static bool isInt32Immediate(SDOperand N, unsigned &Imm) {
 316   return isInt32Immediate(N.Val, Imm);
 317 }
 318
 319
 320 // isOpcWithIntImmediate - This method tests to see if the node is a specific
 321 // opcode and that it has a immediate integer right operand.
 322 // If so Imm will receive the 32 bit value.
 323 static bool isOpcWithIntImmediate(SDNode *N, unsigned Opc, unsigned& Imm) {
 324   return N->getOpcode() == Opc && isInt32Immediate(N->getOperand(1).Val, Imm);
 325 }
 326
 327
 328 // isRunOfOnes - Returns true iff Val consists of one contiguous run of 1s with
 329 // any number of 0s on either side.  The 1s are allowed to wrap from LSB to
 330 // MSB, so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs.  0x0F0F0000 is
 331 // not, since all 1s are not contiguous.
 332 static bool isRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
 333   if (isShiftedMask_32(Val)) {
 334     // look for the first non-zero bit
 335     MB = CountLeadingZeros_32(Val);
 336     // look for the first zero bit after the run of ones
 337     ME = CountLeadingZeros_32((Val - 1) ^ Val);
 338     return true;
 339   } else {
 340     Val = ~Val; // invert mask
 341     if (isShiftedMask_32(Val)) {
 342       // effectively look for the first zero bit
 343       ME = CountLeadingZeros_32(Val) - 1;
 344       // effectively look for the first one bit after the run of zeros
 345       MB = CountLeadingZeros_32((Val - 1) ^ Val) + 1;
 346       return true;
 347     }
 348   }
 349   // no run present
 350   return false;
 351 }
 352
 353 // isRotateAndMask - Returns true if Mask and Shift can be folded into a rotate
 354 // and mask opcode and mask operation.
 355 static bool isRotateAndMask(SDNode *N, unsigned Mask, bool IsShiftMask,
 356                             unsigned &SH, unsigned &MB, unsigned &ME) {
 357   // Don't even go down this path for i64, since different logic will be
 358   // necessary for rldicl/rldicr/rldimi.
 359   if (N->getValueType(0) != MVT::i32)
 360     return false;
 361
 362   unsigned Shift  = 32;
 363   unsigned Indeterminant = ~0;  // bit mask marking indeterminant results
 364   unsigned Opcode = N->getOpcode();
 365   if (N->getNumOperands() != 2 ||
 366       !isInt32Immediate(N->getOperand(1).Val, Shift) || (Shift > 31))
 367     return false;
 368
 369   if (Opcode == ISD::SHL) {
 370     // apply shift left to mask if it comes first
 371     if (IsShiftMask) Mask = Mask << Shift;
 372     // determine which bits are made indeterminant by shift
 373     Indeterminant = ~(0xFFFFFFFFu << Shift);
 374   } else if (Opcode == ISD::SRL) {
 375     // apply shift right to mask if it comes first
 376     if (IsShiftMask) Mask = Mask >> Shift;
 377     // determine which bits are made indeterminant by shift
 378     Indeterminant = ~(0xFFFFFFFFu >> Shift);
 379     // adjust for the left rotate
 380     Shift = 32 - Shift;
 381   } else {
 382     return false;
 383   }
 384
 385   // if the mask doesn't intersect any Indeterminant bits
 386   if (Mask && !(Mask & Indeterminant)) {
 387     SH = Shift & 31;
 388     // make sure the mask is still a mask (wrap arounds may not be)
 389     return isRunOfOnes(Mask, MB, ME);
 390   }
 391   return false;
 392 }
 393
 394 /// SelectBitfieldInsert - turn an or of two masked values into
 395 /// the rotate left word immediate then mask insert (rlwimi) instruction.
 396 SDNode *PPCDAGToDAGISel::SelectBitfieldInsert(SDNode *N) {
 397   SDOperand Op0 = N->getOperand(0);
 398   SDOperand Op1 = N->getOperand(1);
 399
 400   uint64_t LKZ, LKO, RKZ, RKO;
 401   TLI.ComputeMaskedBits(Op0, 0xFFFFFFFFULL, LKZ, LKO);
 402   TLI.ComputeMaskedBits(Op1, 0xFFFFFFFFULL, RKZ, RKO);
 403
 404   unsigned TargetMask = LKZ;
 405   unsigned InsertMask = RKZ;
 406
 407   if ((TargetMask | InsertMask) == 0xFFFFFFFF) {
 408     unsigned Op0Opc = Op0.getOpcode();
 409     unsigned Op1Opc = Op1.getOpcode();
 410     unsigned Value, SH = 0;
 411     TargetMask = ~TargetMask;
 412     InsertMask = ~InsertMask;
 413
 414     // If the LHS has a foldable shift and the RHS does not, then swap it to the
 415     // RHS so that we can fold the shift into the insert.
 416     if (Op0Opc == ISD::AND && Op1Opc == ISD::AND) {
 417       if (Op0.getOperand(0).getOpcode() == ISD::SHL ||
 418           Op0.getOperand(0).getOpcode() == ISD::SRL) {
 419         if (Op1.getOperand(0).getOpcode() != ISD::SHL &&
 420             Op1.getOperand(0).getOpcode() != ISD::SRL) {
 421           std::swap(Op0, Op1);
 422           std::swap(Op0Opc, Op1Opc);
 423           std::swap(TargetMask, InsertMask);
 424         }
 425       }
 426     } else if (Op0Opc == ISD::SHL || Op0Opc == ISD::SRL) {
 427       if (Op1Opc == ISD::AND && Op1.getOperand(0).getOpcode() != ISD::SHL &&
 428           Op1.getOperand(0).getOpcode() != ISD::SRL) {
 429         std::swap(Op0, Op1);
 430         std::swap(Op0Opc, Op1Opc);
 431         std::swap(TargetMask, InsertMask);
 432       }
 433     }
 434
 435     unsigned MB, ME;
 436     if (InsertMask && isRunOfOnes(InsertMask, MB, ME)) {
 437       SDOperand Tmp1, Tmp2, Tmp3;
 438       bool DisjointMask = (TargetMask ^ InsertMask) == 0xFFFFFFFF;
 439
 440       if ((Op1Opc == ISD::SHL || Op1Opc == ISD::SRL) &&
 441           isInt32Immediate(Op1.getOperand(1), Value)) {
 442         Op1 = Op1.getOperand(0);
 443         SH  = (Op1Opc == ISD::SHL) ? Value : 32 - Value;
 444       }
 445       if (Op1Opc == ISD::AND) {
 446         unsigned SHOpc = Op1.getOperand(0).getOpcode();
 447         if ((SHOpc == ISD::SHL || SHOpc == ISD::SRL) &&
 448             isInt32Immediate(Op1.getOperand(0).getOperand(1), Value)) {
 449           Op1 = Op1.getOperand(0).getOperand(0);
 450           SH  = (SHOpc == ISD::SHL) ? Value : 32 - Value;
 451         } else {
 452           Op1 = Op1.getOperand(0);
 453         }
 454       }
 455
 456       Tmp3 = (Op0Opc == ISD::AND && DisjointMask) ? Op0.getOperand(0) : Op0;
 457       AddToISelQueue(Tmp3);
 458       AddToISelQueue(Op1);
 459       SH &= 31;
 460       return CurDAG->getTargetNode(PPC::RLWIMI, MVT::i32, Tmp3, Op1,
 461                                    getI32Imm(SH), getI32Imm(MB), getI32Imm(ME));
 462     }
 463   }
 464   return 0;
 465 }
 466
 467 /// SelectAddrImm - Returns true if the address N can be represented by
 468 /// a base register plus a signed 16-bit displacement [r+imm].
 469 bool PPCDAGToDAGISel::SelectAddrImm(SDOperand N, SDOperand &Disp,
 470                                     SDOperand &Base) {
 471   // If this can be more profitably realized as r+r, fail.
 472   if (SelectAddrIdx(N, Disp, Base))
 473     return false;
 474
 475   if (N.getOpcode() == ISD::ADD) {
 476     short imm = 0;
 477     if (isIntS16Immediate(N.getOperand(1), imm)) {
 478       Disp = getI32Imm((int)imm & 0xFFFF);
 479       if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N.getOperand(0))) {
 480         Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
 481       } else {
 482         Base = N.getOperand(0);
 483       }
 484       return true; // [r+i]
 485     } else if (N.getOperand(1).getOpcode() == PPCISD::Lo) {
 486       // Match LOAD (ADD (X, Lo(G))).
 487       assert(!cast<ConstantSDNode>(N.getOperand(1).getOperand(1))->getValue()
 488              && "Cannot handle constant offsets yet!");
 489       Disp = N.getOperand(1).getOperand(0);  // The global address.
 490       assert(Disp.getOpcode() == ISD::TargetGlobalAddress ||
 491              Disp.getOpcode() == ISD::TargetConstantPool ||
 492              Disp.getOpcode() == ISD::TargetJumpTable);
 493       Base = N.getOperand(0);
 494       return true;  // [&g+r]
 495     }
 496   } else if (N.getOpcode() == ISD::OR) {
 497     short imm = 0;
 498     if (isIntS16Immediate(N.getOperand(1), imm)) {
 499       // If this is an or of disjoint bitfields, we can codegen this as an add
 500       // (for better address arithmetic) if the LHS and RHS of the OR are
 501       // provably disjoint.
 502       uint64_t LHSKnownZero, LHSKnownOne;
 503       PPCLowering.ComputeMaskedBits(N.getOperand(0), ~0U,
 504                                     LHSKnownZero, LHSKnownOne);
 505       if ((LHSKnownZero|~(unsigned)imm) == ~0U) {
 506         // If all of the bits are known zero on the LHS or RHS, the add won't
 507         // carry.
 508         Base = N.getOperand(0);
 509         Disp = getI32Imm((int)imm & 0xFFFF);
 510         return true;
 511       }
 512     }
 513   } else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
 514     // Loading from a constant address.
 515
 516     // If this address fits entirely in a 16-bit sext immediate field, codegen
 517     // this as "d, 0"
 518     short Imm;
 519     if (isIntS16Immediate(CN, Imm)) {
 520       Disp = CurDAG->getTargetConstant(Imm, CN->getValueType(0));
 521       Base = CurDAG->getRegister(PPC::R0, CN->getValueType(0));
 522       return true;
 523     }
 524
 525     // FIXME: Handle small sext constant offsets in PPC64 mode also!
 526     if (CN->getValueType(0) == MVT::i32) {
 527       int Addr = (int)CN->getValue();
 528
 529       // Otherwise, break this down into an LIS + disp.
 530       Disp = getI32Imm((short)Addr);
 531       Base = CurDAG->getConstant(Addr - (signed short)Addr, MVT::i32);
 532       return true;
 533     }
 534   }
 535
 536   Disp = getSmallIPtrImm(0);
 537   if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N))
 538     Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
 539   else
 540     Base = N;
 541   return true;      // [r+0]
 542 }
 543
 544 /// SelectAddrIdx - Given the specified addressed, check to see if it can be
 545 /// represented as an indexed [r+r] operation.  Returns false if it can
 546 /// be represented by [r+imm], which are preferred.
 547 bool PPCDAGToDAGISel::SelectAddrIdx(SDOperand N, SDOperand &Base,
 548                                     SDOperand &Index) {
 549   short imm = 0;
 550   if (N.getOpcode() == ISD::ADD) {
 551     if (isIntS16Immediate(N.getOperand(1), imm))
 552       return false;    // r+i
 553     if (N.getOperand(1).getOpcode() == PPCISD::Lo)
 554       return false;    // r+i
 555
 556     Base = N.getOperand(0);
 557     Index = N.getOperand(1);
 558     return true;
 559   } else if (N.getOpcode() == ISD::OR) {
 560     if (isIntS16Immediate(N.getOperand(1), imm))
 561       return false;    // r+i can fold it if we can.
 562
 563     // If this is an or of disjoint bitfields, we can codegen this as an add
 564     // (for better address arithmetic) if the LHS and RHS of the OR are provably
 565     // disjoint.
 566     uint64_t LHSKnownZero, LHSKnownOne;
 567     uint64_t RHSKnownZero, RHSKnownOne;
 568     PPCLowering.ComputeMaskedBits(N.getOperand(0), ~0U,
 569                                   LHSKnownZero, LHSKnownOne);
 570
 571     if (LHSKnownZero) {
 572       PPCLowering.ComputeMaskedBits(N.getOperand(1), ~0U,
 573                                     RHSKnownZero, RHSKnownOne);
 574       // If all of the bits are known zero on the LHS or RHS, the add won't
 575       // carry.
 576       if ((LHSKnownZero | RHSKnownZero) == ~0U) {
 577         Base = N.getOperand(0);
 578         Index = N.getOperand(1);
 579         return true;
 580       }
 581     }
 582   }
 583
 584   return false;
 585 }
 586
 587 /// SelectAddrIdxOnly - Given the specified addressed, force it to be
 588 /// represented as an indexed [r+r] operation.
 589 bool PPCDAGToDAGISel::SelectAddrIdxOnly(SDOperand N, SDOperand &Base,
 590                                         SDOperand &Index) {
 591   // Check to see if we can easily represent this as an [r+r] address.  This
 592   // will fail if it thinks that the address is more profitably represented as
 593   // reg+imm, e.g. where imm = 0.
 594   if (SelectAddrIdx(N, Base, Index))
 595     return true;
 596
 597   // If the operand is an addition, always emit this as [r+r], since this is
 598   // better (for code size, and execution, as the memop does the add for free)
 599   // than emitting an explicit add.
 600   if (N.getOpcode() == ISD::ADD) {
 601     Base = N.getOperand(0);
 602     Index = N.getOperand(1);
 603     return true;
 604   }
 605
 606   // Otherwise, do it the hard way, using R0 as the base register.
 607   Base = CurDAG->getRegister(PPC::R0, N.getValueType());
 608   Index = N;
 609   return true;
 610 }
 611
 612 /// SelectAddrImmShift - Returns true if the address N can be represented by
 613 /// a base register plus a signed 14-bit displacement [r+imm*4].  Suitable
 614 /// for use by STD and friends.
 615 bool PPCDAGToDAGISel::SelectAddrImmShift(SDOperand N, SDOperand &Disp,
 616                                          SDOperand &Base) {
 617   // If this can be more profitably realized as r+r, fail.
 618   if (SelectAddrIdx(N, Disp, Base))
 619     return false;
 620
 621   if (N.getOpcode() == ISD::ADD) {
 622     short imm = 0;
 623     if (isIntS16Immediate(N.getOperand(1), imm) && (imm & 3) == 0) {
 624       Disp = getI32Imm(((int)imm & 0xFFFF) >> 2);
 625       if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N.getOperand(0))) {
 626         Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
 627       } else {
 628         Base = N.getOperand(0);
 629       }
 630       return true; // [r+i]
 631     } else if (N.getOperand(1).getOpcode() == PPCISD::Lo) {
 632       // Match LOAD (ADD (X, Lo(G))).
 633       assert(!cast<ConstantSDNode>(N.getOperand(1).getOperand(1))->getValue()
 634              && "Cannot handle constant offsets yet!");
 635       Disp = N.getOperand(1).getOperand(0);  // The global address.
 636       assert(Disp.getOpcode() == ISD::TargetGlobalAddress ||
 637              Disp.getOpcode() == ISD::TargetConstantPool ||
 638              Disp.getOpcode() == ISD::TargetJumpTable);
 639       Base = N.getOperand(0);
 640       return true;  // [&g+r]
 641     }
 642   } else if (N.getOpcode() == ISD::OR) {
 643     short imm = 0;
 644     if (isIntS16Immediate(N.getOperand(1), imm) && (imm & 3) == 0) {
 645       // If this is an or of disjoint bitfields, we can codegen this as an add
 646       // (for better address arithmetic) if the LHS and RHS of the OR are
 647       // provably disjoint.
 648       uint64_t LHSKnownZero, LHSKnownOne;
 649       PPCLowering.ComputeMaskedBits(N.getOperand(0), ~0U,
 650                                     LHSKnownZero, LHSKnownOne);
 651       if ((LHSKnownZero|~(unsigned)imm) == ~0U) {
 652         // If all of the bits are known zero on the LHS or RHS, the add won't
 653         // carry.
 654         Base = N.getOperand(0);
 655         Disp = getI32Imm(((int)imm & 0xFFFF) >> 2);
 656         return true;
 657       }
 658     }
 659   } else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
 660     // Loading from a constant address.
 661
 662     // If this address fits entirely in a 14-bit sext immediate field, codegen
 663     // this as "d, 0"
 664     short Imm;
 665     if (isIntS16Immediate(CN, Imm)) {
 666       Disp = getSmallIPtrImm((unsigned short)Imm >> 2);
 667       Base = CurDAG->getRegister(PPC::R0, CN->getValueType(0));
 668       return true;
 669     }
 670
 671     // FIXME: Handle small sext constant offsets in PPC64 mode also!
 672     if (CN->getValueType(0) == MVT::i32) {
 673       int Addr = (int)CN->getValue();
 674
 675       // Otherwise, break this down into an LIS + disp.
 676       Disp = getI32Imm((short)Addr >> 2);
 677       Base = CurDAG->getConstant(Addr - (signed short)Addr, MVT::i32);
 678       return true;
 679     }
 680   }
 681
 682   Disp = getSmallIPtrImm(0);
 683   if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N))
 684     Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
 685   else
 686     Base = N;
 687   return true;      // [r+0]
 688 }
 689
 690
 691 /// SelectCC - Select a comparison of the specified values with the specified
 692 /// condition code, returning the CR# of the expression.
 693 SDOperand PPCDAGToDAGISel::SelectCC(SDOperand LHS, SDOperand RHS,
 694                                     ISD::CondCode CC) {
 695   // Always select the LHS.
 696   AddToISelQueue(LHS);
 697   unsigned Opc;
 698
 699   if (LHS.getValueType() == MVT::i32) {
 700     unsigned Imm;
 701     if (ISD::isUnsignedIntSetCC(CC)) {
 702       if (isInt32Immediate(RHS, Imm) && isUInt16(Imm))
 703         return SDOperand(CurDAG->getTargetNode(PPC::CMPLWI, MVT::i32, LHS,
 704                                                getI32Imm(Imm & 0xFFFF)), 0);
 705       Opc = PPC::CMPLW;
 706     } else {
 707       short SImm;
 708       if (isIntS16Immediate(RHS, SImm))
 709         return SDOperand(CurDAG->getTargetNode(PPC::CMPWI, MVT::i32, LHS,
 710                                                getI32Imm((int)SImm & 0xFFFF)),
 711                          0);
 712       Opc = PPC::CMPW;
 713     }
 714   } else if (LHS.getValueType() == MVT::i64) {
 715     uint64_t Imm;
 716     if (ISD::isUnsignedIntSetCC(CC)) {
 717       if (isInt64Immediate(RHS.Val, Imm) && isUInt16(Imm))
 718         return SDOperand(CurDAG->getTargetNode(PPC::CMPLDI, MVT::i64, LHS,
 719                                                getI64Imm(Imm & 0xFFFF)), 0);
 720       Opc = PPC::CMPLD;
 721     } else {
 722       short SImm;
 723       if (isIntS16Immediate(RHS, SImm))
 724         return SDOperand(CurDAG->getTargetNode(PPC::CMPDI, MVT::i64, LHS,
 725                                                getI64Imm((int)SImm & 0xFFFF)),
 726                          0);
 727       Opc = PPC::CMPD;
 728     }
 729   } else if (LHS.getValueType() == MVT::f32) {
 730     Opc = PPC::FCMPUS;
 731   } else {
 732     assert(LHS.getValueType() == MVT::f64 && "Unknown vt!");
 733     Opc = PPC::FCMPUD;
 734   }
 735   AddToISelQueue(RHS);
 736   return SDOperand(CurDAG->getTargetNode(Opc, MVT::i32, LHS, RHS), 0);
 737 }
 738
 739 /// getBCCForSetCC - Returns the PowerPC condition branch mnemonic corresponding
 740 /// to Condition.
 741 static unsigned getBCCForSetCC(ISD::CondCode CC) {
 742   switch (CC) {
 743   default: assert(0 && "Unknown condition!"); abort();
 744   case ISD::SETOEQ:    // FIXME: This is incorrect see PR642.
 745   case ISD::SETUEQ:
 746   case ISD::SETEQ:  return PPC::BEQ;
 747   case ISD::SETONE:    // FIXME: This is incorrect see PR642.
 748   case ISD::SETUNE:
 749   case ISD::SETNE:  return PPC::BNE;
 750   case ISD::SETOLT:    // FIXME: This is incorrect see PR642.
 751   case ISD::SETULT:
 752   case ISD::SETLT:  return PPC::BLT;
 753   case ISD::SETOLE:    // FIXME: This is incorrect see PR642.
 754   case ISD::SETULE:
 755   case ISD::SETLE:  return PPC::BLE;
 756   case ISD::SETOGT:    // FIXME: This is incorrect see PR642.
 757   case ISD::SETUGT:
 758   case ISD::SETGT:  return PPC::BGT;
 759   case ISD::SETOGE:    // FIXME: This is incorrect see PR642.
 760   case ISD::SETUGE:
 761   case ISD::SETGE:  return PPC::BGE;
 762
 763   case ISD::SETO:   return PPC::BUN;
 764   case ISD::SETUO:  return PPC::BNU;
 765   }
 766   return 0;
 767 }
 768
 769 /// getCRIdxForSetCC - Return the index of the condition register field
 770 /// associated with the SetCC condition, and whether or not the field is
 771 /// treated as inverted.  That is, lt = 0; ge = 0 inverted.
 772 static unsigned getCRIdxForSetCC(ISD::CondCode CC, bool& Inv) {
 773   switch (CC) {
 774   default: assert(0 && "Unknown condition!"); abort();
 775   case ISD::SETOLT:  // FIXME: This is incorrect see PR642.
 776   case ISD::SETULT:
 777   case ISD::SETLT:  Inv = false;  return 0;
 778   case ISD::SETOGE:  // FIXME: This is incorrect see PR642.
 779   case ISD::SETUGE:
 780   case ISD::SETGE:  Inv = true;   return 0;
 781   case ISD::SETOGT:  // FIXME: This is incorrect see PR642.
 782   case ISD::SETUGT:
 783   case ISD::SETGT:  Inv = false;  return 1;
 784   case ISD::SETOLE:  // FIXME: This is incorrect see PR642.
 785   case ISD::SETULE:
 786   case ISD::SETLE:  Inv = true;   return 1;
 787   case ISD::SETOEQ:  // FIXME: This is incorrect see PR642.
 788   case ISD::SETUEQ:
 789   case ISD::SETEQ:  Inv = false;  return 2;
 790   case ISD::SETONE:  // FIXME: This is incorrect see PR642.
 791   case ISD::SETUNE:
 792   case ISD::SETNE:  Inv = true;   return 2;
 793   case ISD::SETO:   Inv = true;   return 3;
 794   case ISD::SETUO:  Inv = false;  return 3;
 795   }
 796   return 0;
 797 }
 798
 799 SDNode *PPCDAGToDAGISel::SelectSETCC(SDOperand Op) {
 800   SDNode *N = Op.Val;
 801   unsigned Imm;
 802   ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(2))->get();
 803   if (isInt32Immediate(N->getOperand(1), Imm)) {
 804     // We can codegen setcc op, imm very efficiently compared to a brcond.
 805     // Check for those cases here.
 806     // setcc op, 0
 807     if (Imm == 0) {
 808       SDOperand Op = N->getOperand(0);
 809       AddToISelQueue(Op);
 810       switch (CC) {
 811       default: break;
 812       case ISD::SETEQ:
 813         Op = SDOperand(CurDAG->getTargetNode(PPC::CNTLZW, MVT::i32, Op), 0);
 814         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Op, getI32Imm(27),
 815                                     getI32Imm(5), getI32Imm(31)).Val;
 816       case ISD::SETNE: {
 817         SDOperand AD =
 818           SDOperand(CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
 819                                           Op, getI32Imm(~0U)), 0);
 820         return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, AD, Op,
 821                                     AD.getValue(1)).Val;
 822       }
 823       case ISD::SETLT:
 824         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Op, getI32Imm(1),
 825                                     getI32Imm(31), getI32Imm(31)).Val;
 826       case ISD::SETGT: {
 827         SDOperand T =
 828           SDOperand(CurDAG->getTargetNode(PPC::NEG, MVT::i32, Op), 0);
 829         T = SDOperand(CurDAG->getTargetNode(PPC::ANDC, MVT::i32, T, Op), 0);
 830         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, T, getI32Imm(1),
 831                                     getI32Imm(31), getI32Imm(31)).Val;
 832       }
 833       }
 834     } else if (Imm == ~0U) {        // setcc op, -1
 835       SDOperand Op = N->getOperand(0);
 836       AddToISelQueue(Op);
 837       switch (CC) {
 838       default: break;
 839       case ISD::SETEQ:
 840         Op = SDOperand(CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
 841                                              Op, getI32Imm(1)), 0);
 842         return CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
 843                               SDOperand(CurDAG->getTargetNode(PPC::LI, MVT::i32,
 844                                                               getI32Imm(0)), 0),
 845                                     Op.getValue(1)).Val;
 846       case ISD::SETNE: {
 847         Op = SDOperand(CurDAG->getTargetNode(PPC::NOR, MVT::i32, Op, Op), 0);
 848         SDNode *AD = CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
 849                                            Op, getI32Imm(~0U));
 850         return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, SDOperand(AD, 0),
 851                                     Op, SDOperand(AD, 1)).Val;
 852       }
 853       case ISD::SETLT: {
 854         SDOperand AD = SDOperand(CurDAG->getTargetNode(PPC::ADDI, MVT::i32, Op,
 855                                                        getI32Imm(1)), 0);
 856         SDOperand AN = SDOperand(CurDAG->getTargetNode(PPC::AND, MVT::i32, AD,
 857                                                        Op), 0);
 858         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, AN, getI32Imm(1),
 859                                     getI32Imm(31), getI32Imm(31)).Val;
 860       }
 861       case ISD::SETGT:
 862         Op = SDOperand(CurDAG->getTargetNode(PPC::RLWINM, MVT::i32, Op,
 863                                              getI32Imm(1), getI32Imm(31),
 864                                              getI32Imm(31)), 0);
 865         return CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Op,
 866                                     getI32Imm(1)).Val;
 867       }
 868     }
 869   }
 870
 871   bool Inv;
 872   unsigned Idx = getCRIdxForSetCC(CC, Inv);
 873   SDOperand CCReg = SelectCC(N->getOperand(0), N->getOperand(1), CC);
 874   SDOperand IntCR;
 875
 876   // Force the ccreg into CR7.
 877   SDOperand CR7Reg = CurDAG->getRegister(PPC::CR7, MVT::i32);
 878
 879   SDOperand InFlag(0, 0);  // Null incoming flag value.
 880   CCReg = CurDAG->getCopyToReg(CurDAG->getEntryNode(), CR7Reg, CCReg,
 881                                InFlag).getValue(1);
 882
 883   if (TLI.getTargetMachine().getSubtarget<PPCSubtarget>().isGigaProcessor())
 884     IntCR = SDOperand(CurDAG->getTargetNode(PPC::MFOCRF, MVT::i32, CR7Reg,
 885                                             CCReg), 0);
 886   else
 887     IntCR = SDOperand(CurDAG->getTargetNode(PPC::MFCR, MVT::i32, CCReg), 0);
 888
 889   if (!Inv) {
 890     return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, IntCR,
 891                                 getI32Imm((32-(3-Idx)) & 31),
 892                                 getI32Imm(31), getI32Imm(31)).Val;
 893   } else {
 894     SDOperand Tmp =
 895       SDOperand(CurDAG->getTargetNode(PPC::RLWINM, MVT::i32, IntCR,
 896                                       getI32Imm((32-(3-Idx)) & 31),
 897                                       getI32Imm(31),getI32Imm(31)), 0);
 898     return CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Tmp, getI32Imm(1)).Val;
 899   }
 900 }
 901
 902
 903 // Select - Convert the specified operand from a target-independent to a
 904 // target-specific node if it hasn't already been changed.
 905 SDNode *PPCDAGToDAGISel::Select(SDOperand &Result, SDOperand Op) {
 906   SDNode *N = Op.Val;
 907   if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
 908       N->getOpcode() < PPCISD::FIRST_NUMBER) {
 909     Result = Op;
 910     return NULL;   // Already selected.
 911   }
 912
 913   switch (N->getOpcode()) {
 914   default: break;
 915   case ISD::SETCC:
 916     return SelectSETCC(Op);
 917   case PPCISD::GlobalBaseReg:
 918     return getGlobalBaseReg().Val;
 919
 920   case ISD::FrameIndex: {
 921     int FI = cast<FrameIndexSDNode>(N)->getIndex();
 922     SDOperand TFI = CurDAG->getTargetFrameIndex(FI, Op.getValueType());
 923     unsigned Opc = Op.getValueType() == MVT::i32 ? PPC::ADDI : PPC::ADDI8;
 924     if (N->hasOneUse())
 925       return CurDAG->SelectNodeTo(N, Opc, Op.getValueType(), TFI,
 926                                   getSmallIPtrImm(0)).Val;
 927     return CurDAG->getTargetNode(Opc, Op.getValueType(), TFI,
 928                                  getSmallIPtrImm(0));
 929   }
 930
 931   case PPCISD::MFCR: {
 932     SDOperand InFlag = N->getOperand(1);
 933     AddToISelQueue(InFlag);
 934     // Use MFOCRF if supported.
 935     if (TLI.getTargetMachine().getSubtarget<PPCSubtarget>().isGigaProcessor())
 936       return CurDAG->getTargetNode(PPC::MFOCRF, MVT::i32,
 937                                    N->getOperand(0), InFlag);
 938     else
 939       return CurDAG->getTargetNode(PPC::MFCR, MVT::i32, InFlag);
 940   }
 941
 942   case ISD::SDIV: {
 943     // FIXME: since this depends on the setting of the carry flag from the srawi
 944     //        we should really be making notes about that for the scheduler.
 945     // FIXME: It sure would be nice if we could cheaply recognize the
 946     //        srl/add/sra pattern the dag combiner will generate for this as
 947     //        sra/addze rather than having to handle sdiv ourselves.  oh well.
 948     unsigned Imm;
 949     if (isInt32Immediate(N->getOperand(1), Imm)) {
 950       SDOperand N0 = N->getOperand(0);
 951       AddToISelQueue(N0);
 952       if ((signed)Imm > 0 && isPowerOf2_32(Imm)) {
 953         SDNode *Op =
 954           CurDAG->getTargetNode(PPC::SRAWI, MVT::i32, MVT::Flag,
 955                                 N0, getI32Imm(Log2_32(Imm)));
 956         return CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
 957                                     SDOperand(Op, 0), SDOperand(Op, 1)).Val;
 958       } else if ((signed)Imm < 0 && isPowerOf2_32(-Imm)) {
 959         SDNode *Op =
 960           CurDAG->getTargetNode(PPC::SRAWI, MVT::i32, MVT::Flag,
 961                                 N0, getI32Imm(Log2_32(-Imm)));
 962         SDOperand PT =
 963           SDOperand(CurDAG->getTargetNode(PPC::ADDZE, MVT::i32,
 964                                           SDOperand(Op, 0), SDOperand(Op, 1)),
 965                     0);
 966         return CurDAG->SelectNodeTo(N, PPC::NEG, MVT::i32, PT).Val;
 967       }
 968     }
 969
 970     // Other cases are autogenerated.
 971     break;
 972   }
 973   case ISD::AND: {
 974     unsigned Imm, Imm2;
 975     // If this is an and of a value rotated between 0 and 31 bits and then and'd
 976     // with a mask, emit rlwinm
 977     if (isInt32Immediate(N->getOperand(1), Imm) &&
 978         (isShiftedMask_32(Imm) || isShiftedMask_32(~Imm))) {
 979       SDOperand Val;
 980       unsigned SH, MB, ME;
 981       if (isRotateAndMask(N->getOperand(0).Val, Imm, false, SH, MB, ME)) {
 982         Val = N->getOperand(0).getOperand(0);
 983         AddToISelQueue(Val);
 984       } else if (Imm == 0) {
 985         // AND X, 0 -> 0, not "rlwinm 32".
 986         AddToISelQueue(N->getOperand(1));
 987         ReplaceUses(SDOperand(N, 0), N->getOperand(1));
 988         return NULL;
 989       } else {
 990         Val = N->getOperand(0);
 991         AddToISelQueue(Val);
 992         isRunOfOnes(Imm, MB, ME);
 993         SH = 0;
 994       }
 995       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Val,
 996                                   getI32Imm(SH), getI32Imm(MB),
 997                                   getI32Imm(ME)).Val;
 998     }
 999     // ISD::OR doesn't get all the bitfield insertion fun.
1000     // (and (or x, c1), c2) where isRunOfOnes(~(c1^c2)) is a bitfield insert
1001     if (isInt32Immediate(N->getOperand(1), Imm) &&
1002         N->getOperand(0).getOpcode() == ISD::OR &&
1003         isInt32Immediate(N->getOperand(0).getOperand(1), Imm2)) {
1004       unsigned MB, ME;
1005       Imm = ~(Imm^Imm2);
1006       if (isRunOfOnes(Imm, MB, ME)) {
1007         AddToISelQueue(N->getOperand(0).getOperand(0));
1008         AddToISelQueue(N->getOperand(0).getOperand(1));
1009         return CurDAG->getTargetNode(PPC::RLWIMI, MVT::i32,
1010                                      N->getOperand(0).getOperand(0),
1011                                      N->getOperand(0).getOperand(1),
1012                                      getI32Imm(0), getI32Imm(MB),getI32Imm(ME));
1013       }
1014     }
1015
1016     // Other cases are autogenerated.
1017     break;
1018   }
1019   case ISD::OR:
1020     if (N->getValueType(0) == MVT::i32)
1021       if (SDNode *I = SelectBitfieldInsert(N))
1022         return I;
1023
1024     // Other cases are autogenerated.
1025     break;
1026   case ISD::SHL: {
1027     unsigned Imm, SH, MB, ME;
1028     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
1029         isRotateAndMask(N, Imm, true, SH, MB, ME)) {
1030       AddToISelQueue(N->getOperand(0).getOperand(0));
1031       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32,
1032                                   N->getOperand(0).getOperand(0),
1033                                   getI32Imm(SH), getI32Imm(MB),
1034                                   getI32Imm(ME)).Val;
1035     }
1036
1037     // Other cases are autogenerated.
1038     break;
1039   }
1040   case ISD::SRL: {
1041     unsigned Imm, SH, MB, ME;
1042     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
1043         isRotateAndMask(N, Imm, true, SH, MB, ME)) {
1044       AddToISelQueue(N->getOperand(0).getOperand(0));
1045       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32,
1046                                   N->getOperand(0).getOperand(0),
1047                                   getI32Imm(SH), getI32Imm(MB),
1048                                   getI32Imm(ME)).Val;
1049     }
1050
1051     // Other cases are autogenerated.
1052     break;
1053   }
1054   case ISD::SELECT_CC: {
1055     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(4))->get();
1056
1057     // Handle the setcc cases here.  select_cc lhs, 0, 1, 0, cc
1058     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N->getOperand(1)))
1059       if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N->getOperand(2)))
1060         if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N->getOperand(3)))
1061           if (N1C->isNullValue() && N3C->isNullValue() &&
1062               N2C->getValue() == 1ULL && CC == ISD::SETNE &&
1063               // FIXME: Implement this optzn for PPC64.
1064               N->getValueType(0) == MVT::i32) {
1065             AddToISelQueue(N->getOperand(0));
1066             SDNode *Tmp =
1067               CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
1068                                     N->getOperand(0), getI32Imm(~0U));
1069             return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32,
1070                                         SDOperand(Tmp, 0), N->getOperand(0),
1071                                         SDOperand(Tmp, 1)).Val;
1072           }
1073
1074     SDOperand CCReg = SelectCC(N->getOperand(0), N->getOperand(1), CC);
1075     unsigned BROpc = getBCCForSetCC(CC);
1076
1077     bool isFP = MVT::isFloatingPoint(N->getValueType(0));
1078     unsigned SelectCCOp;
1079     if (N->getValueType(0) == MVT::i32)
1080       SelectCCOp = PPC::SELECT_CC_I4;
1081     else if (N->getValueType(0) == MVT::i64)
1082       SelectCCOp = PPC::SELECT_CC_I8;
1083     else if (N->getValueType(0) == MVT::f32)
1084       SelectCCOp = PPC::SELECT_CC_F4;
1085     else if (N->getValueType(0) == MVT::f64)
1086       SelectCCOp = PPC::SELECT_CC_F8;
1087     else
1088       SelectCCOp = PPC::SELECT_CC_VRRC;
1089
1090     AddToISelQueue(N->getOperand(2));
1091     AddToISelQueue(N->getOperand(3));
1092     return CurDAG->SelectNodeTo(N, SelectCCOp, N->getValueType(0), CCReg,
1093                                 N->getOperand(2), N->getOperand(3),
1094                                 getI32Imm(BROpc)).Val;
1095   }
1096   case ISD::BR_CC: {
1097     AddToISelQueue(N->getOperand(0));
1098     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(1))->get();
1099     SDOperand CondCode = SelectCC(N->getOperand(2), N->getOperand(3), CC);
1100     return CurDAG->SelectNodeTo(N, PPC::COND_BRANCH, MVT::Other,
1101                                 CondCode, getI32Imm(getBCCForSetCC(CC)),
1102                                 N->getOperand(4), N->getOperand(0)).Val;
1103   }
1104   case ISD::BRIND: {
1105     // FIXME: Should custom lower this.
1106     SDOperand Chain = N->getOperand(0);
1107     SDOperand Target = N->getOperand(1);
1108     AddToISelQueue(Chain);
1109     AddToISelQueue(Target);
1110     unsigned Opc = Target.getValueType() == MVT::i32 ? PPC::MTCTR : PPC::MTCTR8;
1111     Chain = SDOperand(CurDAG->getTargetNode(Opc, MVT::Other, Target,
1112                                             Chain), 0);
1113     return CurDAG->SelectNodeTo(N, PPC::BCTR, MVT::Other, Chain).Val;
1114   }
1115   // FIXME: These are manually selected because tblgen isn't handling varargs
1116   // nodes correctly.
1117   case PPCISD::BCTRL:            return MySelect_PPCbctrl(Op);
1118   case PPCISD::CALL:             return MySelect_PPCcall(Op);
1119   }
1120
1121   return SelectCode(Result, Op);
1122 }
1123
1124
1125 // FIXME: This is manually selected because tblgen isn't handling varargs nodes
1126 // correctly.
1127 SDNode *PPCDAGToDAGISel::MySelect_PPCbctrl(SDOperand N) {
1128   SDOperand Chain(0, 0);
1129
1130   bool hasFlag =
1131     N.getOperand(N.getNumOperands()-1).getValueType() == MVT::Flag;
1132
1133   SmallVector<SDOperand, 8> Ops;
1134   // Push varargs arguments, including optional flag.
1135   for (unsigned i = 1, e = N.getNumOperands()-hasFlag; i != e; ++i) {
1136     Chain = N.getOperand(i);
1137     AddToISelQueue(Chain);
1138     Ops.push_back(Chain);
1139   }
1140
1141   Chain = N.getOperand(0);
1142   AddToISelQueue(Chain);
1143   Ops.push_back(Chain);
1144
1145   if (hasFlag) {
1146     Chain = N.getOperand(N.getNumOperands()-1);
1147     AddToISelQueue(Chain);
1148     Ops.push_back(Chain);
1149   }
1150
1151   return CurDAG->getTargetNode(PPC::BCTRL, MVT::Other, MVT::Flag,
1152                                &Ops[0], Ops.size());
1153 }
1154
1155 // FIXME: This is manually selected because tblgen isn't handling varargs nodes
1156 // correctly.
1157 SDNode *PPCDAGToDAGISel::MySelect_PPCcall(SDOperand N) {
1158   SDOperand Chain(0, 0);
1159   SDOperand N1(0, 0);
1160   SDOperand Tmp0(0, 0);
1161   SDNode *ResNode;
1162   Chain = N.getOperand(0);
1163   N1 = N.getOperand(1);
1164
1165   // Pattern: (PPCcall:void (imm:i32):$func)
1166   // Emits: (BLA:void (imm:i32):$func)
1167   // Pattern complexity = 4  cost = 1
1168   if (N1.getOpcode() == ISD::Constant) {
1169     unsigned Tmp0C = (unsigned)cast<ConstantSDNode>(N1)->getValue();
1170
1171     SmallVector<SDOperand, 8> Ops;
1172     Ops.push_back(CurDAG->getTargetConstant(Tmp0C, MVT::i32));
1173
1174     bool hasFlag =
1175       N.getOperand(N.getNumOperands()-1).getValueType() == MVT::Flag;
1176
1177     // Push varargs arguments, not including optional flag.
1178     for (unsigned i = 2, e = N.getNumOperands()-hasFlag; i != e; ++i) {
1179       Chain = N.getOperand(i);
1180       AddToISelQueue(Chain);
1181       Ops.push_back(Chain);
1182     }
1183     Chain = N.getOperand(0);
1184     AddToISelQueue(Chain);
1185     Ops.push_back(Chain);
1186     if (hasFlag) {
1187       Chain = N.getOperand(N.getNumOperands()-1);
1188       AddToISelQueue(Chain);
1189       Ops.push_back(Chain);
1190     }
1191     return CurDAG->getTargetNode(PPC::BLA, MVT::Other, MVT::Flag,
1192                                  &Ops[0], Ops.size());
1193   }
1194
1195   // Pattern: (PPCcall:void (tglobaladdr:i32):$dst)
1196   // Emits: (BL:void (tglobaladdr:i32):$dst)
1197   // Pattern complexity = 4  cost = 1
1198   if (N1.getOpcode() == ISD::TargetGlobalAddress) {
1199     SmallVector<SDOperand, 8> Ops;
1200     Ops.push_back(N1);
1201
1202     bool hasFlag =
1203       N.getOperand(N.getNumOperands()-1).getValueType() == MVT::Flag;
1204
1205     // Push varargs arguments, not including optional flag.
1206     for (unsigned i = 2, e = N.getNumOperands()-hasFlag; i != e; ++i) {
1207       Chain = N.getOperand(i);
1208       AddToISelQueue(Chain);
1209       Ops.push_back(Chain);
1210     }
1211     Chain = N.getOperand(0);
1212     AddToISelQueue(Chain);
1213     Ops.push_back(Chain);
1214     if (hasFlag) {
1215       Chain = N.getOperand(N.getNumOperands()-1);
1216       AddToISelQueue(Chain);
1217       Ops.push_back(Chain);
1218     }
1219
1220     return CurDAG->getTargetNode(PPC::BL, MVT::Other, MVT::Flag,
1221                                  &Ops[0], Ops.size());
1222   }
1223
1224   // Pattern: (PPCcall:void (texternalsym:i32):$dst)
1225   // Emits: (BL:void (texternalsym:i32):$dst)
1226   // Pattern complexity = 4  cost = 1
1227   if (N1.getOpcode() == ISD::TargetExternalSymbol) {
1228     std::vector<SDOperand> Ops;
1229     Ops.push_back(N1);
1230
1231     bool hasFlag =
1232       N.getOperand(N.getNumOperands()-1).getValueType() == MVT::Flag;
1233
1234     // Push varargs arguments, not including optional flag.
1235     for (unsigned i = 2, e = N.getNumOperands()-hasFlag; i != e; ++i) {
1236       Chain = N.getOperand(i);
1237       AddToISelQueue(Chain);
1238       Ops.push_back(Chain);
1239     }
1240     Chain = N.getOperand(0);
1241     AddToISelQueue(Chain);
1242     Ops.push_back(Chain);
1243     if (hasFlag) {
1244       Chain = N.getOperand(N.getNumOperands()-1);
1245       AddToISelQueue(Chain);
1246       Ops.push_back(Chain);
1247     }
1248
1249     return CurDAG->getTargetNode(PPC::BL, MVT::Other, MVT::Flag,
1250                                  &Ops[0], Ops.size());
1251   }
1252   std::cerr << "Cannot yet select: ";
1253   N.Val->dump(CurDAG);
1254   std::cerr << '\n';
1255   abort();
1256
1257   return NULL;
1258 }
1259
1260
1261 /// createPPCISelDag - This pass converts a legalized DAG into a
1262 /// PowerPC-specific DAG, ready for instruction scheduling.
1263 ///
1264 FunctionPass *llvm::createPPCISelDag(PPCTargetMachine &TM) {
1265   return new PPCDAGToDAGISel(TM);
1266 }
1267