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
  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::i64) {
 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       SDOperand Ops[] = { Tmp3, Op1, getI32Imm(SH), getI32Imm(MB),
 461                           getI32Imm(ME) };
 462       return CurDAG->getTargetNode(PPC::RLWIMI, MVT::i32, Ops, 5);
 463     }
 464   }
 465   return 0;
 466 }
 467
 468 /// SelectAddrImm - Returns true if the address N can be represented by
 469 /// a base register plus a signed 16-bit displacement [r+imm].
 470 bool PPCDAGToDAGISel::SelectAddrImm(SDOperand N, SDOperand &Disp,
 471                                     SDOperand &Base) {
 472   // If this can be more profitably realized as r+r, fail.
 473   if (SelectAddrIdx(N, Disp, Base))
 474     return false;
 475
 476   if (N.getOpcode() == ISD::ADD) {
 477     short imm = 0;
 478     if (isIntS16Immediate(N.getOperand(1), imm)) {
 479       Disp = getI32Imm((int)imm & 0xFFFF);
 480       if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N.getOperand(0))) {
 481         Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
 482       } else {
 483         Base = N.getOperand(0);
 484       }
 485       return true; // [r+i]
 486     } else if (N.getOperand(1).getOpcode() == PPCISD::Lo) {
 487       // Match LOAD (ADD (X, Lo(G))).
 488       assert(!cast<ConstantSDNode>(N.getOperand(1).getOperand(1))->getValue()
 489              && "Cannot handle constant offsets yet!");
 490       Disp = N.getOperand(1).getOperand(0);  // The global address.
 491       assert(Disp.getOpcode() == ISD::TargetGlobalAddress ||
 492              Disp.getOpcode() == ISD::TargetConstantPool ||
 493              Disp.getOpcode() == ISD::TargetJumpTable);
 494       Base = N.getOperand(0);
 495       return true;  // [&g+r]
 496     }
 497   } else if (N.getOpcode() == ISD::OR) {
 498     short imm = 0;
 499     if (isIntS16Immediate(N.getOperand(1), imm)) {
 500       // If this is an or of disjoint bitfields, we can codegen this as an add
 501       // (for better address arithmetic) if the LHS and RHS of the OR are
 502       // provably disjoint.
 503       uint64_t LHSKnownZero, LHSKnownOne;
 504       PPCLowering.ComputeMaskedBits(N.getOperand(0), ~0U,
 505                                     LHSKnownZero, LHSKnownOne);
 506       if ((LHSKnownZero|~(unsigned)imm) == ~0U) {
 507         // If all of the bits are known zero on the LHS or RHS, the add won't
 508         // carry.
 509         Base = N.getOperand(0);
 510         Disp = getI32Imm((int)imm & 0xFFFF);
 511         return true;
 512       }
 513     }
 514   } else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
 515     // Loading from a constant address.
 516
 517     // If this address fits entirely in a 16-bit sext immediate field, codegen
 518     // this as "d, 0"
 519     short Imm;
 520     if (isIntS16Immediate(CN, Imm)) {
 521       Disp = CurDAG->getTargetConstant(Imm, CN->getValueType(0));
 522       Base = CurDAG->getRegister(PPC::R0, CN->getValueType(0));
 523       return true;
 524     }
 525
 526     // FIXME: Handle small sext constant offsets in PPC64 mode also!
 527     if (CN->getValueType(0) == MVT::i32) {
 528       int Addr = (int)CN->getValue();
 529
 530       // Otherwise, break this down into an LIS + disp.
 531       Disp = getI32Imm((short)Addr);
 532       Base = CurDAG->getConstant(Addr - (signed short)Addr, MVT::i32);
 533       return true;
 534     }
 535   }
 536
 537   Disp = getSmallIPtrImm(0);
 538   if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N))
 539     Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
 540   else
 541     Base = N;
 542   return true;      // [r+0]
 543 }
 544
 545 /// SelectAddrIdx - Given the specified addressed, check to see if it can be
 546 /// represented as an indexed [r+r] operation.  Returns false if it can
 547 /// be represented by [r+imm], which are preferred.
 548 bool PPCDAGToDAGISel::SelectAddrIdx(SDOperand N, SDOperand &Base,
 549                                     SDOperand &Index) {
 550   short imm = 0;
 551   if (N.getOpcode() == ISD::ADD) {
 552     if (isIntS16Immediate(N.getOperand(1), imm))
 553       return false;    // r+i
 554     if (N.getOperand(1).getOpcode() == PPCISD::Lo)
 555       return false;    // r+i
 556
 557     Base = N.getOperand(0);
 558     Index = N.getOperand(1);
 559     return true;
 560   } else if (N.getOpcode() == ISD::OR) {
 561     if (isIntS16Immediate(N.getOperand(1), imm))
 562       return false;    // r+i can fold it if we can.
 563
 564     // If this is an or of disjoint bitfields, we can codegen this as an add
 565     // (for better address arithmetic) if the LHS and RHS of the OR are provably
 566     // disjoint.
 567     uint64_t LHSKnownZero, LHSKnownOne;
 568     uint64_t RHSKnownZero, RHSKnownOne;
 569     PPCLowering.ComputeMaskedBits(N.getOperand(0), ~0U,
 570                                   LHSKnownZero, LHSKnownOne);
 571
 572     if (LHSKnownZero) {
 573       PPCLowering.ComputeMaskedBits(N.getOperand(1), ~0U,
 574                                     RHSKnownZero, RHSKnownOne);
 575       // If all of the bits are known zero on the LHS or RHS, the add won't
 576       // carry.
 577       if ((LHSKnownZero | RHSKnownZero) == ~0U) {
 578         Base = N.getOperand(0);
 579         Index = N.getOperand(1);
 580         return true;
 581       }
 582     }
 583   }
 584
 585   return false;
 586 }
 587
 588 /// SelectAddrIdxOnly - Given the specified addressed, force it to be
 589 /// represented as an indexed [r+r] operation.
 590 bool PPCDAGToDAGISel::SelectAddrIdxOnly(SDOperand N, SDOperand &Base,
 591                                         SDOperand &Index) {
 592   // Check to see if we can easily represent this as an [r+r] address.  This
 593   // will fail if it thinks that the address is more profitably represented as
 594   // reg+imm, e.g. where imm = 0.
 595   if (SelectAddrIdx(N, Base, Index))
 596     return true;
 597
 598   // If the operand is an addition, always emit this as [r+r], since this is
 599   // better (for code size, and execution, as the memop does the add for free)
 600   // than emitting an explicit add.
 601   if (N.getOpcode() == ISD::ADD) {
 602     Base = N.getOperand(0);
 603     Index = N.getOperand(1);
 604     return true;
 605   }
 606
 607   // Otherwise, do it the hard way, using R0 as the base register.
 608   Base = CurDAG->getRegister(PPC::R0, N.getValueType());
 609   Index = N;
 610   return true;
 611 }
 612
 613 /// SelectAddrImmShift - Returns true if the address N can be represented by
 614 /// a base register plus a signed 14-bit displacement [r+imm*4].  Suitable
 615 /// for use by STD and friends.
 616 bool PPCDAGToDAGISel::SelectAddrImmShift(SDOperand N, SDOperand &Disp,
 617                                          SDOperand &Base) {
 618   // If this can be more profitably realized as r+r, fail.
 619   if (SelectAddrIdx(N, Disp, Base))
 620     return false;
 621
 622   if (N.getOpcode() == ISD::ADD) {
 623     short imm = 0;
 624     if (isIntS16Immediate(N.getOperand(1), imm) && (imm & 3) == 0) {
 625       Disp = getI32Imm(((int)imm & 0xFFFF) >> 2);
 626       if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N.getOperand(0))) {
 627         Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
 628       } else {
 629         Base = N.getOperand(0);
 630       }
 631       return true; // [r+i]
 632     } else if (N.getOperand(1).getOpcode() == PPCISD::Lo) {
 633       // Match LOAD (ADD (X, Lo(G))).
 634       assert(!cast<ConstantSDNode>(N.getOperand(1).getOperand(1))->getValue()
 635              && "Cannot handle constant offsets yet!");
 636       Disp = N.getOperand(1).getOperand(0);  // The global address.
 637       assert(Disp.getOpcode() == ISD::TargetGlobalAddress ||
 638              Disp.getOpcode() == ISD::TargetConstantPool ||
 639              Disp.getOpcode() == ISD::TargetJumpTable);
 640       Base = N.getOperand(0);
 641       return true;  // [&g+r]
 642     }
 643   } else if (N.getOpcode() == ISD::OR) {
 644     short imm = 0;
 645     if (isIntS16Immediate(N.getOperand(1), imm) && (imm & 3) == 0) {
 646       // If this is an or of disjoint bitfields, we can codegen this as an add
 647       // (for better address arithmetic) if the LHS and RHS of the OR are
 648       // provably disjoint.
 649       uint64_t LHSKnownZero, LHSKnownOne;
 650       PPCLowering.ComputeMaskedBits(N.getOperand(0), ~0U,
 651                                     LHSKnownZero, LHSKnownOne);
 652       if ((LHSKnownZero|~(unsigned)imm) == ~0U) {
 653         // If all of the bits are known zero on the LHS or RHS, the add won't
 654         // carry.
 655         Base = N.getOperand(0);
 656         Disp = getI32Imm(((int)imm & 0xFFFF) >> 2);
 657         return true;
 658       }
 659     }
 660   } else if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
 661     // Loading from a constant address.
 662
 663     // If this address fits entirely in a 14-bit sext immediate field, codegen
 664     // this as "d, 0"
 665     short Imm;
 666     if (isIntS16Immediate(CN, Imm)) {
 667       Disp = getSmallIPtrImm((unsigned short)Imm >> 2);
 668       Base = CurDAG->getRegister(PPC::R0, CN->getValueType(0));
 669       return true;
 670     }
 671
 672     // FIXME: Handle small sext constant offsets in PPC64 mode also!
 673     if (CN->getValueType(0) == MVT::i32) {
 674       int Addr = (int)CN->getValue();
 675
 676       // Otherwise, break this down into an LIS + disp.
 677       Disp = getI32Imm((short)Addr >> 2);
 678       Base = CurDAG->getConstant(Addr - (signed short)Addr, MVT::i32);
 679       return true;
 680     }
 681   }
 682
 683   Disp = getSmallIPtrImm(0);
 684   if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(N))
 685     Base = CurDAG->getTargetFrameIndex(FI->getIndex(), N.getValueType());
 686   else
 687     Base = N;
 688   return true;      // [r+0]
 689 }
 690
 691
 692 /// SelectCC - Select a comparison of the specified values with the specified
 693 /// condition code, returning the CR# of the expression.
 694 SDOperand PPCDAGToDAGISel::SelectCC(SDOperand LHS, SDOperand RHS,
 695                                     ISD::CondCode CC) {
 696   // Always select the LHS.
 697   AddToISelQueue(LHS);
 698   unsigned Opc;
 699
 700   if (LHS.getValueType() == MVT::i32) {
 701     unsigned Imm;
 702     if (CC == ISD::SETEQ || CC == ISD::SETNE) {
 703       if (isInt32Immediate(RHS, Imm)) {
 704         // SETEQ/SETNE comparison with 16-bit immediate, fold it.
 705         if (isUInt16(Imm))
 706           return SDOperand(CurDAG->getTargetNode(PPC::CMPLWI, MVT::i32, LHS,
 707                                                  getI32Imm(Imm & 0xFFFF)), 0);
 708         // If this is a 16-bit signed immediate, fold it.
 709         if (isInt16(Imm))
 710           return SDOperand(CurDAG->getTargetNode(PPC::CMPWI, MVT::i32, LHS,
 711                                                  getI32Imm(Imm & 0xFFFF)), 0);
 712
 713         // For non-equality comparisons, the default code would materialize the
 714         // constant, then compare against it, like this:
 715         //   lis r2, 4660
 716         //   ori r2, r2, 22136
 717         //   cmpw cr0, r3, r2
 718         // Since we are just comparing for equality, we can emit this instead:
 719         //   xoris r0,r3,0x1234
 720         //   cmplwi cr0,r0,0x5678
 721         //   beq cr0,L6
 722         SDOperand Xor(CurDAG->getTargetNode(PPC::XORIS, MVT::i32, LHS,
 723                                             getI32Imm(Imm >> 16)), 0);
 724         return SDOperand(CurDAG->getTargetNode(PPC::CMPLWI, MVT::i32, Xor,
 725                                                getI32Imm(Imm & 0xFFFF)), 0);
 726       }
 727       Opc = PPC::CMPLW;
 728     } else if (ISD::isUnsignedIntSetCC(CC)) {
 729       if (isInt32Immediate(RHS, Imm) && isUInt16(Imm))
 730         return SDOperand(CurDAG->getTargetNode(PPC::CMPLWI, MVT::i32, LHS,
 731                                                getI32Imm(Imm & 0xFFFF)), 0);
 732       Opc = PPC::CMPLW;
 733     } else {
 734       short SImm;
 735       if (isIntS16Immediate(RHS, SImm))
 736         return SDOperand(CurDAG->getTargetNode(PPC::CMPWI, MVT::i32, LHS,
 737                                                getI32Imm((int)SImm & 0xFFFF)),
 738                          0);
 739       Opc = PPC::CMPW;
 740     }
 741   } else if (LHS.getValueType() == MVT::i64) {
 742     uint64_t Imm;
 743     if (CC == ISD::SETEQ || CC == ISD::SETNE) {
 744       if (isInt64Immediate(RHS.Val, Imm)) {
 745         // SETEQ/SETNE comparison with 16-bit immediate, fold it.
 746         if (isUInt16(Imm))
 747           return SDOperand(CurDAG->getTargetNode(PPC::CMPLDI, MVT::i64, LHS,
 748                                                  getI32Imm(Imm & 0xFFFF)), 0);
 749         // If this is a 16-bit signed immediate, fold it.
 750         if (isInt16(Imm))
 751           return SDOperand(CurDAG->getTargetNode(PPC::CMPDI, MVT::i64, LHS,
 752                                                  getI32Imm(Imm & 0xFFFF)), 0);
 753
 754         // For non-equality comparisons, the default code would materialize the
 755         // constant, then compare against it, like this:
 756         //   lis r2, 4660
 757         //   ori r2, r2, 22136
 758         //   cmpd cr0, r3, r2
 759         // Since we are just comparing for equality, we can emit this instead:
 760         //   xoris r0,r3,0x1234
 761         //   cmpldi cr0,r0,0x5678
 762         //   beq cr0,L6
 763         if (isUInt32(Imm)) {
 764           SDOperand Xor(CurDAG->getTargetNode(PPC::XORIS8, MVT::i64, LHS,
 765                                               getI64Imm(Imm >> 16)), 0);
 766           return SDOperand(CurDAG->getTargetNode(PPC::CMPLDI, MVT::i64, Xor,
 767                                                  getI64Imm(Imm & 0xFFFF)), 0);
 768         }
 769       }
 770       Opc = PPC::CMPLD;
 771     } else if (ISD::isUnsignedIntSetCC(CC)) {
 772       if (isInt64Immediate(RHS.Val, Imm) && isUInt16(Imm))
 773         return SDOperand(CurDAG->getTargetNode(PPC::CMPLDI, MVT::i64, LHS,
 774                                                getI64Imm(Imm & 0xFFFF)), 0);
 775       Opc = PPC::CMPLD;
 776     } else {
 777       short SImm;
 778       if (isIntS16Immediate(RHS, SImm))
 779         return SDOperand(CurDAG->getTargetNode(PPC::CMPDI, MVT::i64, LHS,
 780                                                getI64Imm(SImm & 0xFFFF)),
 781                          0);
 782       Opc = PPC::CMPD;
 783     }
 784   } else if (LHS.getValueType() == MVT::f32) {
 785     Opc = PPC::FCMPUS;
 786   } else {
 787     assert(LHS.getValueType() == MVT::f64 && "Unknown vt!");
 788     Opc = PPC::FCMPUD;
 789   }
 790   AddToISelQueue(RHS);
 791   return SDOperand(CurDAG->getTargetNode(Opc, MVT::i32, LHS, RHS), 0);
 792 }
 793
 794 /// getBCCForSetCC - Returns the PowerPC condition branch mnemonic corresponding
 795 /// to Condition.
 796 static unsigned getBCCForSetCC(ISD::CondCode CC) {
 797   switch (CC) {
 798   default: assert(0 && "Unknown condition!"); abort();
 799   case ISD::SETOEQ:    // FIXME: This is incorrect see PR642.
 800   case ISD::SETUEQ:
 801   case ISD::SETEQ:  return PPC::BEQ;
 802   case ISD::SETONE:    // FIXME: This is incorrect see PR642.
 803   case ISD::SETUNE:
 804   case ISD::SETNE:  return PPC::BNE;
 805   case ISD::SETOLT:    // FIXME: This is incorrect see PR642.
 806   case ISD::SETULT:
 807   case ISD::SETLT:  return PPC::BLT;
 808   case ISD::SETOLE:    // FIXME: This is incorrect see PR642.
 809   case ISD::SETULE:
 810   case ISD::SETLE:  return PPC::BLE;
 811   case ISD::SETOGT:    // FIXME: This is incorrect see PR642.
 812   case ISD::SETUGT:
 813   case ISD::SETGT:  return PPC::BGT;
 814   case ISD::SETOGE:    // FIXME: This is incorrect see PR642.
 815   case ISD::SETUGE:
 816   case ISD::SETGE:  return PPC::BGE;
 817
 818   case ISD::SETO:   return PPC::BUN;
 819   case ISD::SETUO:  return PPC::BNU;
 820   }
 821   return 0;
 822 }
 823
 824 /// getCRIdxForSetCC - Return the index of the condition register field
 825 /// associated with the SetCC condition, and whether or not the field is
 826 /// treated as inverted.  That is, lt = 0; ge = 0 inverted.
 827 static unsigned getCRIdxForSetCC(ISD::CondCode CC, bool& Inv) {
 828   switch (CC) {
 829   default: assert(0 && "Unknown condition!"); abort();
 830   case ISD::SETOLT:  // FIXME: This is incorrect see PR642.
 831   case ISD::SETULT:
 832   case ISD::SETLT:  Inv = false;  return 0;
 833   case ISD::SETOGE:  // FIXME: This is incorrect see PR642.
 834   case ISD::SETUGE:
 835   case ISD::SETGE:  Inv = true;   return 0;
 836   case ISD::SETOGT:  // FIXME: This is incorrect see PR642.
 837   case ISD::SETUGT:
 838   case ISD::SETGT:  Inv = false;  return 1;
 839   case ISD::SETOLE:  // FIXME: This is incorrect see PR642.
 840   case ISD::SETULE:
 841   case ISD::SETLE:  Inv = true;   return 1;
 842   case ISD::SETOEQ:  // FIXME: This is incorrect see PR642.
 843   case ISD::SETUEQ:
 844   case ISD::SETEQ:  Inv = false;  return 2;
 845   case ISD::SETONE:  // FIXME: This is incorrect see PR642.
 846   case ISD::SETUNE:
 847   case ISD::SETNE:  Inv = true;   return 2;
 848   case ISD::SETO:   Inv = true;   return 3;
 849   case ISD::SETUO:  Inv = false;  return 3;
 850   }
 851   return 0;
 852 }
 853
 854 SDNode *PPCDAGToDAGISel::SelectSETCC(SDOperand Op) {
 855   SDNode *N = Op.Val;
 856   unsigned Imm;
 857   ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(2))->get();
 858   if (isInt32Immediate(N->getOperand(1), Imm)) {
 859     // We can codegen setcc op, imm very efficiently compared to a brcond.
 860     // Check for those cases here.
 861     // setcc op, 0
 862     if (Imm == 0) {
 863       SDOperand Op = N->getOperand(0);
 864       AddToISelQueue(Op);
 865       switch (CC) {
 866       default: break;
 867       case ISD::SETEQ: {
 868         Op = SDOperand(CurDAG->getTargetNode(PPC::CNTLZW, MVT::i32, Op), 0);
 869         SDOperand Ops[] = { Op, getI32Imm(27), getI32Imm(5), getI32Imm(31) };
 870         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
 871       }
 872       case ISD::SETNE: {
 873         SDOperand AD =
 874           SDOperand(CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
 875                                           Op, getI32Imm(~0U)), 0);
 876         return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, AD, Op,
 877                                     AD.getValue(1));
 878       }
 879       case ISD::SETLT: {
 880         SDOperand Ops[] = { Op, getI32Imm(1), getI32Imm(31), getI32Imm(31) };
 881         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
 882       }
 883       case ISD::SETGT: {
 884         SDOperand T =
 885           SDOperand(CurDAG->getTargetNode(PPC::NEG, MVT::i32, Op), 0);
 886         T = SDOperand(CurDAG->getTargetNode(PPC::ANDC, MVT::i32, T, Op), 0);
 887         SDOperand Ops[] = { T, getI32Imm(1), getI32Imm(31), getI32Imm(31) };
 888         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
 889       }
 890       }
 891     } else if (Imm == ~0U) {        // setcc op, -1
 892       SDOperand Op = N->getOperand(0);
 893       AddToISelQueue(Op);
 894       switch (CC) {
 895       default: break;
 896       case ISD::SETEQ:
 897         Op = SDOperand(CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
 898                                              Op, getI32Imm(1)), 0);
 899         return CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
 900                               SDOperand(CurDAG->getTargetNode(PPC::LI, MVT::i32,
 901                                                               getI32Imm(0)), 0),
 902                                     Op.getValue(1));
 903       case ISD::SETNE: {
 904         Op = SDOperand(CurDAG->getTargetNode(PPC::NOR, MVT::i32, Op, Op), 0);
 905         SDNode *AD = CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
 906                                            Op, getI32Imm(~0U));
 907         return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, SDOperand(AD, 0),
 908                                     Op, SDOperand(AD, 1));
 909       }
 910       case ISD::SETLT: {
 911         SDOperand AD = SDOperand(CurDAG->getTargetNode(PPC::ADDI, MVT::i32, Op,
 912                                                        getI32Imm(1)), 0);
 913         SDOperand AN = SDOperand(CurDAG->getTargetNode(PPC::AND, MVT::i32, AD,
 914                                                        Op), 0);
 915         SDOperand Ops[] = { AN, getI32Imm(1), getI32Imm(31), getI32Imm(31) };
 916         return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
 917       }
 918       case ISD::SETGT: {
 919         SDOperand Ops[] = { Op, getI32Imm(1), getI32Imm(31), getI32Imm(31) };
 920         Op = SDOperand(CurDAG->getTargetNode(PPC::RLWINM, MVT::i32, Ops, 4), 0);
 921         return CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Op,
 922                                     getI32Imm(1));
 923       }
 924       }
 925     }
 926   }
 927
 928   bool Inv;
 929   unsigned Idx = getCRIdxForSetCC(CC, Inv);
 930   SDOperand CCReg = SelectCC(N->getOperand(0), N->getOperand(1), CC);
 931   SDOperand IntCR;
 932
 933   // Force the ccreg into CR7.
 934   SDOperand CR7Reg = CurDAG->getRegister(PPC::CR7, MVT::i32);
 935
 936   SDOperand InFlag(0, 0);  // Null incoming flag value.
 937   CCReg = CurDAG->getCopyToReg(CurDAG->getEntryNode(), CR7Reg, CCReg,
 938                                InFlag).getValue(1);
 939
 940   if (TLI.getTargetMachine().getSubtarget<PPCSubtarget>().isGigaProcessor())
 941     IntCR = SDOperand(CurDAG->getTargetNode(PPC::MFOCRF, MVT::i32, CR7Reg,
 942                                             CCReg), 0);
 943   else
 944     IntCR = SDOperand(CurDAG->getTargetNode(PPC::MFCR, MVT::i32, CCReg), 0);
 945
 946   SDOperand Ops[] = { IntCR, getI32Imm((32-(3-Idx)) & 31),
 947                       getI32Imm(31), getI32Imm(31) };
 948   if (!Inv) {
 949     return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
 950   } else {
 951     SDOperand Tmp =
 952       SDOperand(CurDAG->getTargetNode(PPC::RLWINM, MVT::i32, Ops, 4), 0);
 953     return CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Tmp, getI32Imm(1));
 954   }
 955 }
 956
 957
 958 // Select - Convert the specified operand from a target-independent to a
 959 // target-specific node if it hasn't already been changed.
 960 SDNode *PPCDAGToDAGISel::Select(SDOperand Op) {
 961   SDNode *N = Op.Val;
 962   if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
 963       N->getOpcode() < PPCISD::FIRST_NUMBER)
 964     return NULL;   // Already selected.
 965
 966   switch (N->getOpcode()) {
 967   default: break;
 968   case ISD::SETCC:
 969     return SelectSETCC(Op);
 970   case PPCISD::GlobalBaseReg:
 971     return getGlobalBaseReg();
 972
 973   case ISD::FrameIndex: {
 974     int FI = cast<FrameIndexSDNode>(N)->getIndex();
 975     SDOperand TFI = CurDAG->getTargetFrameIndex(FI, Op.getValueType());
 976     unsigned Opc = Op.getValueType() == MVT::i32 ? PPC::ADDI : PPC::ADDI8;
 977     if (N->hasOneUse())
 978       return CurDAG->SelectNodeTo(N, Opc, Op.getValueType(), TFI,
 979                                   getSmallIPtrImm(0));
 980     return CurDAG->getTargetNode(Opc, Op.getValueType(), TFI,
 981                                  getSmallIPtrImm(0));
 982   }
 983
 984   case PPCISD::MFCR: {
 985     SDOperand InFlag = N->getOperand(1);
 986     AddToISelQueue(InFlag);
 987     // Use MFOCRF if supported.
 988     if (TLI.getTargetMachine().getSubtarget<PPCSubtarget>().isGigaProcessor())
 989       return CurDAG->getTargetNode(PPC::MFOCRF, MVT::i32,
 990                                    N->getOperand(0), InFlag);
 991     else
 992       return CurDAG->getTargetNode(PPC::MFCR, MVT::i32, InFlag);
 993   }
 994
 995   case ISD::SDIV: {
 996     // FIXME: since this depends on the setting of the carry flag from the srawi
 997     //        we should really be making notes about that for the scheduler.
 998     // FIXME: It sure would be nice if we could cheaply recognize the
 999     //        srl/add/sra pattern the dag combiner will generate for this as
1000     //        sra/addze rather than having to handle sdiv ourselves.  oh well.
1001     unsigned Imm;
1002     if (isInt32Immediate(N->getOperand(1), Imm)) {
1003       SDOperand N0 = N->getOperand(0);
1004       AddToISelQueue(N0);
1005       if ((signed)Imm > 0 && isPowerOf2_32(Imm)) {
1006         SDNode *Op =
1007           CurDAG->getTargetNode(PPC::SRAWI, MVT::i32, MVT::Flag,
1008                                 N0, getI32Imm(Log2_32(Imm)));
1009         return CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
1010                                     SDOperand(Op, 0), SDOperand(Op, 1));
1011       } else if ((signed)Imm < 0 && isPowerOf2_32(-Imm)) {
1012         SDNode *Op =
1013           CurDAG->getTargetNode(PPC::SRAWI, MVT::i32, MVT::Flag,
1014                                 N0, getI32Imm(Log2_32(-Imm)));
1015         SDOperand PT =
1016           SDOperand(CurDAG->getTargetNode(PPC::ADDZE, MVT::i32,
1017                                           SDOperand(Op, 0), SDOperand(Op, 1)),
1018                     0);
1019         return CurDAG->SelectNodeTo(N, PPC::NEG, MVT::i32, PT);
1020       }
1021     }
1022
1023     // Other cases are autogenerated.
1024     break;
1025   }
1026   case ISD::AND: {
1027     unsigned Imm, Imm2;
1028     // If this is an and of a value rotated between 0 and 31 bits and then and'd
1029     // with a mask, emit rlwinm
1030     if (isInt32Immediate(N->getOperand(1), Imm) &&
1031         (isShiftedMask_32(Imm) || isShiftedMask_32(~Imm))) {
1032       SDOperand Val;
1033       unsigned SH, MB, ME;
1034       if (isRotateAndMask(N->getOperand(0).Val, Imm, false, SH, MB, ME)) {
1035         Val = N->getOperand(0).getOperand(0);
1036         AddToISelQueue(Val);
1037       } else if (Imm == 0) {
1038         // AND X, 0 -> 0, not "rlwinm 32".
1039         AddToISelQueue(N->getOperand(1));
1040         ReplaceUses(SDOperand(N, 0), N->getOperand(1));
1041         return NULL;
1042       } else {
1043         Val = N->getOperand(0);
1044         AddToISelQueue(Val);
1045         isRunOfOnes(Imm, MB, ME);
1046         SH = 0;
1047       }
1048       SDOperand Ops[] = { Val, getI32Imm(SH), getI32Imm(MB), getI32Imm(ME) };
1049       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
1050     }
1051     // ISD::OR doesn't get all the bitfield insertion fun.
1052     // (and (or x, c1), c2) where isRunOfOnes(~(c1^c2)) is a bitfield insert
1053     if (isInt32Immediate(N->getOperand(1), Imm) &&
1054         N->getOperand(0).getOpcode() == ISD::OR &&
1055         isInt32Immediate(N->getOperand(0).getOperand(1), Imm2)) {
1056       unsigned MB, ME;
1057       Imm = ~(Imm^Imm2);
1058       if (isRunOfOnes(Imm, MB, ME)) {
1059         AddToISelQueue(N->getOperand(0).getOperand(0));
1060         AddToISelQueue(N->getOperand(0).getOperand(1));
1061         SDOperand Ops[] = { N->getOperand(0).getOperand(0),
1062                             N->getOperand(0).getOperand(1),
1063                             getI32Imm(0), getI32Imm(MB),getI32Imm(ME) };
1064         return CurDAG->getTargetNode(PPC::RLWIMI, MVT::i32, Ops, 5);
1065       }
1066     }
1067
1068     // Other cases are autogenerated.
1069     break;
1070   }
1071   case ISD::OR:
1072     if (N->getValueType(0) == MVT::i32)
1073       if (SDNode *I = SelectBitfieldInsert(N))
1074         return I;
1075
1076     // Other cases are autogenerated.
1077     break;
1078   case ISD::SHL: {
1079     unsigned Imm, SH, MB, ME;
1080     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
1081         isRotateAndMask(N, Imm, true, SH, MB, ME)) {
1082       AddToISelQueue(N->getOperand(0).getOperand(0));
1083       SDOperand Ops[] = { N->getOperand(0).getOperand(0),
1084                           getI32Imm(SH), getI32Imm(MB), getI32Imm(ME) };
1085       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
1086     }
1087
1088     // Other cases are autogenerated.
1089     break;
1090   }
1091   case ISD::SRL: {
1092     unsigned Imm, SH, MB, ME;
1093     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
1094         isRotateAndMask(N, Imm, true, SH, MB, ME)) {
1095       AddToISelQueue(N->getOperand(0).getOperand(0));
1096       SDOperand Ops[] = { N->getOperand(0).getOperand(0),
1097                           getI32Imm(SH), getI32Imm(MB), getI32Imm(ME) };
1098       return CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops, 4);
1099     }
1100
1101     // Other cases are autogenerated.
1102     break;
1103   }
1104   case ISD::SELECT_CC: {
1105     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(4))->get();
1106
1107     // Handle the setcc cases here.  select_cc lhs, 0, 1, 0, cc
1108     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N->getOperand(1)))
1109       if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N->getOperand(2)))
1110         if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N->getOperand(3)))
1111           if (N1C->isNullValue() && N3C->isNullValue() &&
1112               N2C->getValue() == 1ULL && CC == ISD::SETNE &&
1113               // FIXME: Implement this optzn for PPC64.
1114               N->getValueType(0) == MVT::i32) {
1115             AddToISelQueue(N->getOperand(0));
1116             SDNode *Tmp =
1117               CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
1118                                     N->getOperand(0), getI32Imm(~0U));
1119             return CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32,
1120                                         SDOperand(Tmp, 0), N->getOperand(0),
1121                                         SDOperand(Tmp, 1));
1122           }
1123
1124     SDOperand CCReg = SelectCC(N->getOperand(0), N->getOperand(1), CC);
1125     unsigned BROpc = getBCCForSetCC(CC);
1126
1127     bool isFP = MVT::isFloatingPoint(N->getValueType(0));
1128     unsigned SelectCCOp;
1129     if (N->getValueType(0) == MVT::i32)
1130       SelectCCOp = PPC::SELECT_CC_I4;
1131     else if (N->getValueType(0) == MVT::i64)
1132       SelectCCOp = PPC::SELECT_CC_I8;
1133     else if (N->getValueType(0) == MVT::f32)
1134       SelectCCOp = PPC::SELECT_CC_F4;
1135     else if (N->getValueType(0) == MVT::f64)
1136       SelectCCOp = PPC::SELECT_CC_F8;
1137     else
1138       SelectCCOp = PPC::SELECT_CC_VRRC;
1139
1140     AddToISelQueue(N->getOperand(2));
1141     AddToISelQueue(N->getOperand(3));
1142     SDOperand Ops[] = { CCReg, N->getOperand(2), N->getOperand(3),
1143                         getI32Imm(BROpc) };
1144     return CurDAG->SelectNodeTo(N, SelectCCOp, N->getValueType(0), Ops, 4);
1145   }
1146   case ISD::BR_CC: {
1147     AddToISelQueue(N->getOperand(0));
1148     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(1))->get();
1149     SDOperand CondCode = SelectCC(N->getOperand(2), N->getOperand(3), CC);
1150     SDOperand Ops[] = { CondCode, getI32Imm(getBCCForSetCC(CC)),
1151                         N->getOperand(4), N->getOperand(0) };
1152     return CurDAG->SelectNodeTo(N, PPC::COND_BRANCH, MVT::Other, Ops, 4);
1153   }
1154   case ISD::BRIND: {
1155     // FIXME: Should custom lower this.
1156     SDOperand Chain = N->getOperand(0);
1157     SDOperand Target = N->getOperand(1);
1158     AddToISelQueue(Chain);
1159     AddToISelQueue(Target);
1160     unsigned Opc = Target.getValueType() == MVT::i32 ? PPC::MTCTR : PPC::MTCTR8;
1161     Chain = SDOperand(CurDAG->getTargetNode(Opc, MVT::Other, Target,
1162                                             Chain), 0);
1163     return CurDAG->SelectNodeTo(N, PPC::BCTR, MVT::Other, Chain);
1164   }
1165   // FIXME: These are manually selected because tblgen isn't handling varargs
1166   // nodes correctly.
1167   case PPCISD::BCTRL:            return MySelect_PPCbctrl(Op);
1168   case PPCISD::CALL:             return MySelect_PPCcall(Op);
1169   }
1170
1171   return SelectCode(Op);
1172 }
1173
1174
1175 // FIXME: This is manually selected because tblgen isn't handling varargs nodes
1176 // correctly.
1177 SDNode *PPCDAGToDAGISel::MySelect_PPCbctrl(SDOperand N) {
1178   SDOperand Chain(0, 0);
1179
1180   bool hasFlag =
1181     N.getOperand(N.getNumOperands()-1).getValueType() == MVT::Flag;
1182
1183   SmallVector<SDOperand, 8> Ops;
1184   // Push varargs arguments, including optional flag.
1185   for (unsigned i = 1, e = N.getNumOperands()-hasFlag; i != e; ++i) {
1186     Chain = N.getOperand(i);
1187     AddToISelQueue(Chain);
1188     Ops.push_back(Chain);
1189   }
1190
1191   Chain = N.getOperand(0);
1192   AddToISelQueue(Chain);
1193   Ops.push_back(Chain);
1194
1195   if (hasFlag) {
1196     Chain = N.getOperand(N.getNumOperands()-1);
1197     AddToISelQueue(Chain);
1198     Ops.push_back(Chain);
1199   }
1200
1201   return CurDAG->getTargetNode(PPC::BCTRL, MVT::Other, MVT::Flag,
1202                                &Ops[0], Ops.size());
1203 }
1204
1205 // FIXME: This is manually selected because tblgen isn't handling varargs nodes
1206 // correctly.
1207 SDNode *PPCDAGToDAGISel::MySelect_PPCcall(SDOperand N) {
1208   SDOperand Chain(0, 0);
1209   SDOperand N1(0, 0);
1210   SDOperand Tmp0(0, 0);
1211   SDNode *ResNode;
1212   Chain = N.getOperand(0);
1213   N1 = N.getOperand(1);
1214
1215   // Pattern: (PPCcall:void (imm:i32):$func)
1216   // Emits: (BLA:void (imm:i32):$func)
1217   // Pattern complexity = 4  cost = 1
1218   if (N1.getOpcode() == ISD::Constant) {
1219     unsigned Tmp0C = (unsigned)cast<ConstantSDNode>(N1)->getValue();
1220
1221     SmallVector<SDOperand, 8> Ops;
1222     Ops.push_back(CurDAG->getTargetConstant(Tmp0C, MVT::i32));
1223
1224     bool hasFlag =
1225       N.getOperand(N.getNumOperands()-1).getValueType() == MVT::Flag;
1226
1227     // Push varargs arguments, not including optional flag.
1228     for (unsigned i = 2, e = N.getNumOperands()-hasFlag; i != e; ++i) {
1229       Chain = N.getOperand(i);
1230       AddToISelQueue(Chain);
1231       Ops.push_back(Chain);
1232     }
1233     Chain = N.getOperand(0);
1234     AddToISelQueue(Chain);
1235     Ops.push_back(Chain);
1236     if (hasFlag) {
1237       Chain = N.getOperand(N.getNumOperands()-1);
1238       AddToISelQueue(Chain);
1239       Ops.push_back(Chain);
1240     }
1241     return CurDAG->getTargetNode(PPC::BLA, MVT::Other, MVT::Flag,
1242                                  &Ops[0], Ops.size());
1243   }
1244
1245   // Pattern: (PPCcall:void (tglobaladdr:i32):$dst)
1246   // Emits: (BL:void (tglobaladdr:i32):$dst)
1247   // Pattern complexity = 4  cost = 1
1248   if (N1.getOpcode() == ISD::TargetGlobalAddress) {
1249     SmallVector<SDOperand, 8> Ops;
1250     Ops.push_back(N1);
1251
1252     bool hasFlag =
1253       N.getOperand(N.getNumOperands()-1).getValueType() == MVT::Flag;
1254
1255     // Push varargs arguments, not including optional flag.
1256     for (unsigned i = 2, e = N.getNumOperands()-hasFlag; i != e; ++i) {
1257       Chain = N.getOperand(i);
1258       AddToISelQueue(Chain);
1259       Ops.push_back(Chain);
1260     }
1261     Chain = N.getOperand(0);
1262     AddToISelQueue(Chain);
1263     Ops.push_back(Chain);
1264     if (hasFlag) {
1265       Chain = N.getOperand(N.getNumOperands()-1);
1266       AddToISelQueue(Chain);
1267       Ops.push_back(Chain);
1268     }
1269
1270     return CurDAG->getTargetNode(PPC::BL, MVT::Other, MVT::Flag,
1271                                  &Ops[0], Ops.size());
1272   }
1273
1274   // Pattern: (PPCcall:void (texternalsym:i32):$dst)
1275   // Emits: (BL:void (texternalsym:i32):$dst)
1276   // Pattern complexity = 4  cost = 1
1277   if (N1.getOpcode() == ISD::TargetExternalSymbol) {
1278     std::vector<SDOperand> Ops;
1279     Ops.push_back(N1);
1280
1281     bool hasFlag =
1282       N.getOperand(N.getNumOperands()-1).getValueType() == MVT::Flag;
1283
1284     // Push varargs arguments, not including optional flag.
1285     for (unsigned i = 2, e = N.getNumOperands()-hasFlag; i != e; ++i) {
1286       Chain = N.getOperand(i);
1287       AddToISelQueue(Chain);
1288       Ops.push_back(Chain);
1289     }
1290     Chain = N.getOperand(0);
1291     AddToISelQueue(Chain);
1292     Ops.push_back(Chain);
1293     if (hasFlag) {
1294       Chain = N.getOperand(N.getNumOperands()-1);
1295       AddToISelQueue(Chain);
1296       Ops.push_back(Chain);
1297     }
1298
1299     return CurDAG->getTargetNode(PPC::BL, MVT::Other, MVT::Flag,
1300                                  &Ops[0], Ops.size());
1301   }
1302   std::cerr << "Cannot yet select: ";
1303   N.Val->dump(CurDAG);
1304   std::cerr << '\n';
1305   abort();
1306
1307   return NULL;
1308 }
1309
1310
1311 /// createPPCISelDag - This pass converts a legalized DAG into a
1312 /// PowerPC-specific DAG, ready for instruction scheduling.
1313 ///
1314 FunctionPass *llvm::createPPCISelDag(PPCTargetMachine &TM) {
1315   return new PPCDAGToDAGISel(TM);
1316 }
1317