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     SDNode *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 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 SDNode *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()).Val;
 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 Op) {
 906   SDNode *N = Op.Val;
 907   if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
 908       N->getOpcode() < PPCISD::FIRST_NUMBER)
 909     return NULL;   // Already selected.
 910
 911   switch (N->getOpcode()) {
 912   default: break;
 913   case ISD::SETCC:
 914     return SelectSETCC(Op);
 915   case PPCISD::GlobalBaseReg:
 916     return getGlobalBaseReg();
 917
 918   case ISD::FrameIndex: {
 919     int FI = cast<FrameIndexSDNode>(N)->getIndex();
 920     SDOperand TFI = CurDAG->getTargetFrameIndex(FI, Op.getValueType());
 921     unsigned Opc = Op.getValueType() == MVT::i32 ? PPC::ADDI : PPC::ADDI8;
 922     if (N->hasOneUse())
 923       return CurDAG->SelectNodeTo(N, Opc, Op.getValueType(), TFI,
 924                                   getSmallIPtrImm(0)).Val;
 925     return CurDAG->getTargetNode(Opc, Op.getValueType(), TFI,
 926                                  getSmallIPtrImm(0));
 927   }
 928
 929   case PPCISD::MFCR: {
 930     SDOperand InFlag = N->getOperand(1);
 931     AddToISelQueue(InFlag);
 932     // Use MFOCRF if supported.
 933     if (TLI.getTargetMachine().getSubtarget<PPCSubtarget>().isGigaProcessor())
 934       return CurDAG->getTargetNode(PPC::MFOCRF, MVT::i32,
 935                                    N->getOperand(0), InFlag);
 936     else
 937       return CurDAG->getTargetNode(PPC::MFCR, MVT::i32, InFlag);
 938   }
 939
 940   case ISD::SDIV: {
 941     // FIXME: since this depends on the setting of the carry flag from the srawi
 942     //        we should really be making notes about that for the scheduler.
 943     // FIXME: It sure would be nice if we could cheaply recognize the
 944     //        srl/add/sra pattern the dag combiner will generate for this as
 945     //        sra/addze rather than having to handle sdiv ourselves.  oh well.
 946     unsigned Imm;
 947     if (isInt32Immediate(N->getOperand(1), Imm)) {
 948       SDOperand N0 = N->getOperand(0);
 949       AddToISelQueue(N0);
 950       if ((signed)Imm > 0 && isPowerOf2_32(Imm)) {
 951         SDNode *Op =
 952           CurDAG->getTargetNode(PPC::SRAWI, MVT::i32, MVT::Flag,
 953                                 N0, getI32Imm(Log2_32(Imm)));
 954         return CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
 955                                     SDOperand(Op, 0), SDOperand(Op, 1)).Val;
 956       } else if ((signed)Imm < 0 && isPowerOf2_32(-Imm)) {
 957         SDNode *Op =
 958           CurDAG->getTargetNode(PPC::SRAWI, MVT::i32, MVT::Flag,
 959                                 N0, getI32Imm(Log2_32(-Imm)));
 960         SDOperand PT =
 961           SDOperand(CurDAG->getTargetNode(PPC::ADDZE, MVT::i32,
 962                                           SDOperand(Op, 0), SDOperand(Op, 1)),
 963                     0);
 964         return CurDAG->SelectNodeTo(N, PPC::NEG, MVT::i32, PT).Val;
 965       }
 966     }
 967
 968     // Other cases are autogenerated.
 969     break;
 970   }
 971   case ISD::AND: {
 972     unsigned Imm, Imm2;
 973     // If this is an and of a value rotated between 0 and 31 bits and then and'd
 974     // with a mask, emit rlwinm
 975     if (isInt32Immediate(N->getOperand(1), Imm) &&
 976         (isShiftedMask_32(Imm) || isShiftedMask_32(~Imm))) {
 977       SDOperand Val;
 978       unsigned SH, MB, ME;
 979       if (isRotateAndMask(N->getOperand(0).Val, Imm, false, SH, MB, ME)) {
 980         Val = N->getOperand(0).getOperand(0);
 981         AddToISelQueue(Val);
 982       } else if (Imm == 0) {
 983         // AND X, 0 -> 0, not "rlwinm 32".
 984         AddToISelQueue(N->getOperand(1));
 985         ReplaceUses(SDOperand(N, 0), N->getOperand(1));
 986         return NULL;
 987       } else {
 988         Val = N->getOperand(0);
 989         AddToISelQueue(Val);
 990         isRunOfOnes(Imm, MB, ME);
 991         SH = 0;
 992       }
 993       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Val,
 994                                   getI32Imm(SH), getI32Imm(MB),
 995                                   getI32Imm(ME)).Val;
 996     }
 997     // ISD::OR doesn't get all the bitfield insertion fun.
 998     // (and (or x, c1), c2) where isRunOfOnes(~(c1^c2)) is a bitfield insert
 999     if (isInt32Immediate(N->getOperand(1), Imm) &&
1000         N->getOperand(0).getOpcode() == ISD::OR &&
1001         isInt32Immediate(N->getOperand(0).getOperand(1), Imm2)) {
1002       unsigned MB, ME;
1003       Imm = ~(Imm^Imm2);
1004       if (isRunOfOnes(Imm, MB, ME)) {
1005         AddToISelQueue(N->getOperand(0).getOperand(0));
1006         AddToISelQueue(N->getOperand(0).getOperand(1));
1007         return CurDAG->getTargetNode(PPC::RLWIMI, MVT::i32,
1008                                      N->getOperand(0).getOperand(0),
1009                                      N->getOperand(0).getOperand(1),
1010                                      getI32Imm(0), getI32Imm(MB),getI32Imm(ME));
1011       }
1012     }
1013
1014     // Other cases are autogenerated.
1015     break;
1016   }
1017   case ISD::OR:
1018     if (N->getValueType(0) == MVT::i32)
1019       if (SDNode *I = SelectBitfieldInsert(N))
1020         return I;
1021
1022     // Other cases are autogenerated.
1023     break;
1024   case ISD::SHL: {
1025     unsigned Imm, SH, MB, ME;
1026     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
1027         isRotateAndMask(N, Imm, true, SH, MB, ME)) {
1028       AddToISelQueue(N->getOperand(0).getOperand(0));
1029       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32,
1030                                   N->getOperand(0).getOperand(0),
1031                                   getI32Imm(SH), getI32Imm(MB),
1032                                   getI32Imm(ME)).Val;
1033     }
1034
1035     // Other cases are autogenerated.
1036     break;
1037   }
1038   case ISD::SRL: {
1039     unsigned Imm, SH, MB, ME;
1040     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
1041         isRotateAndMask(N, Imm, true, SH, MB, ME)) {
1042       AddToISelQueue(N->getOperand(0).getOperand(0));
1043       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32,
1044                                   N->getOperand(0).getOperand(0),
1045                                   getI32Imm(SH), getI32Imm(MB),
1046                                   getI32Imm(ME)).Val;
1047     }
1048
1049     // Other cases are autogenerated.
1050     break;
1051   }
1052   case ISD::SELECT_CC: {
1053     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(4))->get();
1054
1055     // Handle the setcc cases here.  select_cc lhs, 0, 1, 0, cc
1056     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N->getOperand(1)))
1057       if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N->getOperand(2)))
1058         if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N->getOperand(3)))
1059           if (N1C->isNullValue() && N3C->isNullValue() &&
1060               N2C->getValue() == 1ULL && CC == ISD::SETNE &&
1061               // FIXME: Implement this optzn for PPC64.
1062               N->getValueType(0) == MVT::i32) {
1063             AddToISelQueue(N->getOperand(0));
1064             SDNode *Tmp =
1065               CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
1066                                     N->getOperand(0), getI32Imm(~0U));
1067             return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32,
1068                                         SDOperand(Tmp, 0), N->getOperand(0),
1069                                         SDOperand(Tmp, 1)).Val;
1070           }
1071
1072     SDOperand CCReg = SelectCC(N->getOperand(0), N->getOperand(1), CC);
1073     unsigned BROpc = getBCCForSetCC(CC);
1074
1075     bool isFP = MVT::isFloatingPoint(N->getValueType(0));
1076     unsigned SelectCCOp;
1077     if (N->getValueType(0) == MVT::i32)
1078       SelectCCOp = PPC::SELECT_CC_I4;
1079     else if (N->getValueType(0) == MVT::i64)
1080       SelectCCOp = PPC::SELECT_CC_I8;
1081     else if (N->getValueType(0) == MVT::f32)
1082       SelectCCOp = PPC::SELECT_CC_F4;
1083     else if (N->getValueType(0) == MVT::f64)
1084       SelectCCOp = PPC::SELECT_CC_F8;
1085     else
1086       SelectCCOp = PPC::SELECT_CC_VRRC;
1087
1088     AddToISelQueue(N->getOperand(2));
1089     AddToISelQueue(N->getOperand(3));
1090     return CurDAG->SelectNodeTo(N, SelectCCOp, N->getValueType(0), CCReg,
1091                                 N->getOperand(2), N->getOperand(3),
1092                                 getI32Imm(BROpc)).Val;
1093   }
1094   case ISD::BR_CC: {
1095     AddToISelQueue(N->getOperand(0));
1096     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(1))->get();
1097     SDOperand CondCode = SelectCC(N->getOperand(2), N->getOperand(3), CC);
1098     return CurDAG->SelectNodeTo(N, PPC::COND_BRANCH, MVT::Other,
1099                                 CondCode, getI32Imm(getBCCForSetCC(CC)),
1100                                 N->getOperand(4), N->getOperand(0)).Val;
1101   }
1102   case ISD::BRIND: {
1103     // FIXME: Should custom lower this.
1104     SDOperand Chain = N->getOperand(0);
1105     SDOperand Target = N->getOperand(1);
1106     AddToISelQueue(Chain);
1107     AddToISelQueue(Target);
1108     unsigned Opc = Target.getValueType() == MVT::i32 ? PPC::MTCTR : PPC::MTCTR8;
1109     Chain = SDOperand(CurDAG->getTargetNode(Opc, MVT::Other, Target,
1110                                             Chain), 0);
1111     return CurDAG->SelectNodeTo(N, PPC::BCTR, MVT::Other, Chain).Val;
1112   }
1113   // FIXME: These are manually selected because tblgen isn't handling varargs
1114   // nodes correctly.
1115   case PPCISD::BCTRL:            return MySelect_PPCbctrl(Op);
1116   case PPCISD::CALL:             return MySelect_PPCcall(Op);
1117   }
1118
1119   return SelectCode(Op);
1120 }
1121
1122
1123 // FIXME: This is manually selected because tblgen isn't handling varargs nodes
1124 // correctly.
1125 SDNode *PPCDAGToDAGISel::MySelect_PPCbctrl(SDOperand N) {
1126   SDOperand Chain(0, 0);
1127
1128   bool hasFlag =
1129     N.getOperand(N.getNumOperands()-1).getValueType() == MVT::Flag;
1130
1131   SmallVector<SDOperand, 8> Ops;
1132   // Push varargs arguments, including optional flag.
1133   for (unsigned i = 1, e = N.getNumOperands()-hasFlag; i != e; ++i) {
1134     Chain = N.getOperand(i);
1135     AddToISelQueue(Chain);
1136     Ops.push_back(Chain);
1137   }
1138
1139   Chain = N.getOperand(0);
1140   AddToISelQueue(Chain);
1141   Ops.push_back(Chain);
1142
1143   if (hasFlag) {
1144     Chain = N.getOperand(N.getNumOperands()-1);
1145     AddToISelQueue(Chain);
1146     Ops.push_back(Chain);
1147   }
1148
1149   return CurDAG->getTargetNode(PPC::BCTRL, MVT::Other, MVT::Flag,
1150                                &Ops[0], Ops.size());
1151 }
1152
1153 // FIXME: This is manually selected because tblgen isn't handling varargs nodes
1154 // correctly.
1155 SDNode *PPCDAGToDAGISel::MySelect_PPCcall(SDOperand N) {
1156   SDOperand Chain(0, 0);
1157   SDOperand N1(0, 0);
1158   SDOperand Tmp0(0, 0);
1159   SDNode *ResNode;
1160   Chain = N.getOperand(0);
1161   N1 = N.getOperand(1);
1162
1163   // Pattern: (PPCcall:void (imm:i32):$func)
1164   // Emits: (BLA:void (imm:i32):$func)
1165   // Pattern complexity = 4  cost = 1
1166   if (N1.getOpcode() == ISD::Constant) {
1167     unsigned Tmp0C = (unsigned)cast<ConstantSDNode>(N1)->getValue();
1168
1169     SmallVector<SDOperand, 8> Ops;
1170     Ops.push_back(CurDAG->getTargetConstant(Tmp0C, MVT::i32));
1171
1172     bool hasFlag =
1173       N.getOperand(N.getNumOperands()-1).getValueType() == MVT::Flag;
1174
1175     // Push varargs arguments, not including optional flag.
1176     for (unsigned i = 2, e = N.getNumOperands()-hasFlag; i != e; ++i) {
1177       Chain = N.getOperand(i);
1178       AddToISelQueue(Chain);
1179       Ops.push_back(Chain);
1180     }
1181     Chain = N.getOperand(0);
1182     AddToISelQueue(Chain);
1183     Ops.push_back(Chain);
1184     if (hasFlag) {
1185       Chain = N.getOperand(N.getNumOperands()-1);
1186       AddToISelQueue(Chain);
1187       Ops.push_back(Chain);
1188     }
1189     return CurDAG->getTargetNode(PPC::BLA, MVT::Other, MVT::Flag,
1190                                  &Ops[0], Ops.size());
1191   }
1192
1193   // Pattern: (PPCcall:void (tglobaladdr:i32):$dst)
1194   // Emits: (BL:void (tglobaladdr:i32):$dst)
1195   // Pattern complexity = 4  cost = 1
1196   if (N1.getOpcode() == ISD::TargetGlobalAddress) {
1197     SmallVector<SDOperand, 8> Ops;
1198     Ops.push_back(N1);
1199
1200     bool hasFlag =
1201       N.getOperand(N.getNumOperands()-1).getValueType() == MVT::Flag;
1202
1203     // Push varargs arguments, not including optional flag.
1204     for (unsigned i = 2, e = N.getNumOperands()-hasFlag; i != e; ++i) {
1205       Chain = N.getOperand(i);
1206       AddToISelQueue(Chain);
1207       Ops.push_back(Chain);
1208     }
1209     Chain = N.getOperand(0);
1210     AddToISelQueue(Chain);
1211     Ops.push_back(Chain);
1212     if (hasFlag) {
1213       Chain = N.getOperand(N.getNumOperands()-1);
1214       AddToISelQueue(Chain);
1215       Ops.push_back(Chain);
1216     }
1217
1218     return CurDAG->getTargetNode(PPC::BL, MVT::Other, MVT::Flag,
1219                                  &Ops[0], Ops.size());
1220   }
1221
1222   // Pattern: (PPCcall:void (texternalsym:i32):$dst)
1223   // Emits: (BL:void (texternalsym:i32):$dst)
1224   // Pattern complexity = 4  cost = 1
1225   if (N1.getOpcode() == ISD::TargetExternalSymbol) {
1226     std::vector<SDOperand> Ops;
1227     Ops.push_back(N1);
1228
1229     bool hasFlag =
1230       N.getOperand(N.getNumOperands()-1).getValueType() == MVT::Flag;
1231
1232     // Push varargs arguments, not including optional flag.
1233     for (unsigned i = 2, e = N.getNumOperands()-hasFlag; i != e; ++i) {
1234       Chain = N.getOperand(i);
1235       AddToISelQueue(Chain);
1236       Ops.push_back(Chain);
1237     }
1238     Chain = N.getOperand(0);
1239     AddToISelQueue(Chain);
1240     Ops.push_back(Chain);
1241     if (hasFlag) {
1242       Chain = N.getOperand(N.getNumOperands()-1);
1243       AddToISelQueue(Chain);
1244       Ops.push_back(Chain);
1245     }
1246
1247     return CurDAG->getTargetNode(PPC::BL, MVT::Other, MVT::Flag,
1248                                  &Ops[0], Ops.size());
1249   }
1250   std::cerr << "Cannot yet select: ";
1251   N.Val->dump(CurDAG);
1252   std::cerr << '\n';
1253   abort();
1254
1255   return NULL;
1256 }
1257
1258
1259 /// createPPCISelDag - This pass converts a legalized DAG into a
1260 /// PowerPC-specific DAG, ready for instruction scheduling.
1261 ///
1262 FunctionPass *llvm::createPPCISelDag(PPCTargetMachine &TM) {
1263   return new PPCDAGToDAGISel(TM);
1264 }
1265