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