lib/Target/PowerPC/PPCISelDAGToDAG.cpp

   1 //===-- PPC32ISelDAGToDAG.cpp - PPC32 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 32 bit PowerPC,
  11 // converting from a legalized dag to a PPC dag.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "PowerPC.h"
  16 #include "PPC32TargetMachine.h"
  17 #include "PPC32ISelLowering.h"
  18 #include "llvm/CodeGen/MachineInstrBuilder.h"
  19 #include "llvm/CodeGen/MachineFunction.h"
  20 #include "llvm/CodeGen/MachineFrameInfo.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/Support/Debug.h"
  29 #include "llvm/Support/MathExtras.h"
  30 using namespace llvm;
  31
  32 namespace {
  33   Statistic<> FusedFP ("ppc-codegen", "Number of fused fp operations");
  34   Statistic<> FrameOff("ppc-codegen", "Number of frame idx offsets collapsed");
  35
  36   //===--------------------------------------------------------------------===//
  37   /// PPC32DAGToDAGISel - PPC32 specific code to select PPC32 machine
  38   /// instructions for SelectionDAG operations.
  39   ///
  40   class PPC32DAGToDAGISel : public SelectionDAGISel {
  41     PPC32TargetLowering PPC32Lowering;
  42     unsigned GlobalBaseReg;
  43   public:
  44     PPC32DAGToDAGISel(TargetMachine &TM)
  45       : SelectionDAGISel(PPC32Lowering), PPC32Lowering(TM) {}
  46
  47     virtual bool runOnFunction(Function &Fn) {
  48       // Make sure we re-emit a set of the global base reg if necessary
  49       GlobalBaseReg = 0;
  50       return SelectionDAGISel::runOnFunction(Fn);
  51     }
  52
  53     /// getI32Imm - Return a target constant with the specified value, of type
  54     /// i32.
  55     inline SDOperand getI32Imm(unsigned Imm) {
  56       return CurDAG->getTargetConstant(Imm, MVT::i32);
  57     }
  58
  59     /// getGlobalBaseReg - insert code into the entry mbb to materialize the PIC
  60     /// base register.  Return the virtual register that holds this value.
  61     SDOperand getGlobalBaseReg();
  62
  63     // Select - Convert the specified operand from a target-independent to a
  64     // target-specific node if it hasn't already been changed.
  65     SDOperand Select(SDOperand Op);
  66
  67     SDNode *SelectIntImmediateExpr(SDOperand LHS, SDOperand RHS,
  68                                    unsigned OCHi, unsigned OCLo,
  69                                    bool IsArithmetic = false,
  70                                    bool Negate = false);
  71     SDNode *SelectBitfieldInsert(SDNode *N);
  72
  73     /// SelectCC - Select a comparison of the specified values with the
  74     /// specified condition code, returning the CR# of the expression.
  75     SDOperand SelectCC(SDOperand LHS, SDOperand RHS, ISD::CondCode CC);
  76
  77     /// SelectAddr - Given the specified address, return the two operands for a
  78     /// load/store instruction, and return true if it should be an indexed [r+r]
  79     /// operation.
  80     bool SelectAddr(SDOperand Addr, SDOperand &Op1, SDOperand &Op2);
  81
  82     SDOperand BuildSDIVSequence(SDNode *N);
  83     SDOperand BuildUDIVSequence(SDNode *N);
  84
  85     /// InstructionSelectBasicBlock - This callback is invoked by
  86     /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
  87     virtual void InstructionSelectBasicBlock(SelectionDAG &DAG) {
  88       DEBUG(BB->dump());
  89       // Select target instructions for the DAG.
  90       Select(DAG.getRoot());
  91       DAG.RemoveDeadNodes();
  92
  93       // Emit machine code to BB.
  94       ScheduleAndEmitDAG(DAG);
  95     }
  96
  97     virtual const char *getPassName() const {
  98       return "PowerPC DAG->DAG Pattern Instruction Selection";
  99     }
 100   };
 101 }
 102
 103 /// getGlobalBaseReg - Output the instructions required to put the
 104 /// base address to use for accessing globals into a register.
 105 ///
 106 SDOperand PPC32DAGToDAGISel::getGlobalBaseReg() {
 107   if (!GlobalBaseReg) {
 108     // Insert the set of GlobalBaseReg into the first MBB of the function
 109     MachineBasicBlock &FirstMBB = BB->getParent()->front();
 110     MachineBasicBlock::iterator MBBI = FirstMBB.begin();
 111     SSARegMap *RegMap = BB->getParent()->getSSARegMap();
 112     GlobalBaseReg = RegMap->createVirtualRegister(PPC32::GPRCRegisterClass);
 113     BuildMI(FirstMBB, MBBI, PPC::MovePCtoLR, 0, PPC::LR);
 114     BuildMI(FirstMBB, MBBI, PPC::MFLR, 1, GlobalBaseReg);
 115   }
 116   return CurDAG->getRegister(GlobalBaseReg, MVT::i32);
 117 }
 118
 119
 120 // isIntImmediate - This method tests to see if a constant operand.
 121 // If so Imm will receive the 32 bit value.
 122 static bool isIntImmediate(SDNode *N, unsigned& Imm) {
 123   if (N->getOpcode() == ISD::Constant) {
 124     Imm = cast<ConstantSDNode>(N)->getValue();
 125     return true;
 126   }
 127   return false;
 128 }
 129
 130 // isOprShiftImm - Returns true if the specified operand is a shift opcode with
 131 // a immediate shift count less than 32.
 132 static bool isOprShiftImm(SDNode *N, unsigned& Opc, unsigned& SH) {
 133   Opc = N->getOpcode();
 134   return (Opc == ISD::SHL || Opc == ISD::SRL || Opc == ISD::SRA) &&
 135     isIntImmediate(N->getOperand(1).Val, SH) && SH < 32;
 136 }
 137
 138 // isRunOfOnes - Returns true iff Val consists of one contiguous run of 1s with
 139 // any number of 0s on either side.  The 1s are allowed to wrap from LSB to
 140 // MSB, so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs.  0x0F0F0000 is
 141 // not, since all 1s are not contiguous.
 142 static bool isRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
 143   if (isShiftedMask_32(Val)) {
 144     // look for the first non-zero bit
 145     MB = CountLeadingZeros_32(Val);
 146     // look for the first zero bit after the run of ones
 147     ME = CountLeadingZeros_32((Val - 1) ^ Val);
 148     return true;
 149   } else {
 150     Val = ~Val; // invert mask
 151     if (isShiftedMask_32(Val)) {
 152       // effectively look for the first zero bit
 153       ME = CountLeadingZeros_32(Val) - 1;
 154       // effectively look for the first one bit after the run of zeros
 155       MB = CountLeadingZeros_32((Val - 1) ^ Val) + 1;
 156       return true;
 157     }
 158   }
 159   // no run present
 160   return false;
 161 }
 162
 163 // isRotateAndMask - Returns true if Mask and Shift can be folded in to a rotate
 164 // and mask opcode and mask operation.
 165 static bool isRotateAndMask(SDNode *N, unsigned Mask, bool IsShiftMask,
 166                             unsigned &SH, unsigned &MB, unsigned &ME) {
 167   unsigned Shift  = 32;
 168   unsigned Indeterminant = ~0;  // bit mask marking indeterminant results
 169   unsigned Opcode = N->getOpcode();
 170   if (!isIntImmediate(N->getOperand(1).Val, Shift) || (Shift > 31))
 171     return false;
 172
 173   if (Opcode == ISD::SHL) {
 174     // apply shift left to mask if it comes first
 175     if (IsShiftMask) Mask = Mask << Shift;
 176     // determine which bits are made indeterminant by shift
 177     Indeterminant = ~(0xFFFFFFFFu << Shift);
 178   } else if (Opcode == ISD::SRA || Opcode == ISD::SRL) {
 179     // apply shift right to mask if it comes first
 180     if (IsShiftMask) Mask = Mask >> Shift;
 181     // determine which bits are made indeterminant by shift
 182     Indeterminant = ~(0xFFFFFFFFu >> Shift);
 183     // adjust for the left rotate
 184     Shift = 32 - Shift;
 185   } else {
 186     return false;
 187   }
 188
 189   // if the mask doesn't intersect any Indeterminant bits
 190   if (Mask && !(Mask & Indeterminant)) {
 191     SH = Shift;
 192     // make sure the mask is still a mask (wrap arounds may not be)
 193     return isRunOfOnes(Mask, MB, ME);
 194   }
 195   return false;
 196 }
 197
 198 // isOpcWithIntImmediate - This method tests to see if the node is a specific
 199 // opcode and that it has a immediate integer right operand.
 200 // If so Imm will receive the 32 bit value.
 201 static bool isOpcWithIntImmediate(SDNode *N, unsigned Opc, unsigned& Imm) {
 202   return N->getOpcode() == Opc && isIntImmediate(N->getOperand(1).Val, Imm);
 203 }
 204
 205 // isOprNot - Returns true if the specified operand is an xor with immediate -1.
 206 static bool isOprNot(SDNode *N) {
 207   unsigned Imm;
 208   return isOpcWithIntImmediate(N, ISD::XOR, Imm) && (signed)Imm == -1;
 209 }
 210
 211 // Immediate constant composers.
 212 // Lo16 - grabs the lo 16 bits from a 32 bit constant.
 213 // Hi16 - grabs the hi 16 bits from a 32 bit constant.
 214 // HA16 - computes the hi bits required if the lo bits are add/subtracted in
 215 // arithmethically.
 216 static unsigned Lo16(unsigned x)  { return x & 0x0000FFFF; }
 217 static unsigned Hi16(unsigned x)  { return Lo16(x >> 16); }
 218 static unsigned HA16(unsigned x)  { return Hi16((signed)x - (signed short)x); }
 219
 220 // isIntImmediate - This method tests to see if a constant operand.
 221 // If so Imm will receive the 32 bit value.
 222 static bool isIntImmediate(SDOperand N, unsigned& Imm) {
 223   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
 224     Imm = (unsigned)CN->getSignExtended();
 225     return true;
 226   }
 227   return false;
 228 }
 229
 230 /// SelectBitfieldInsert - turn an or of two masked values into
 231 /// the rotate left word immediate then mask insert (rlwimi) instruction.
 232 /// Returns true on success, false if the caller still needs to select OR.
 233 ///
 234 /// Patterns matched:
 235 /// 1. or shl, and   5. or and, and
 236 /// 2. or and, shl   6. or shl, shr
 237 /// 3. or shr, and   7. or shr, shl
 238 /// 4. or and, shr
 239 SDNode *PPC32DAGToDAGISel::SelectBitfieldInsert(SDNode *N) {
 240   bool IsRotate = false;
 241   unsigned TgtMask = 0xFFFFFFFF, InsMask = 0xFFFFFFFF, SH = 0;
 242   unsigned Value;
 243
 244   SDOperand Op0 = N->getOperand(0);
 245   SDOperand Op1 = N->getOperand(1);
 246
 247   unsigned Op0Opc = Op0.getOpcode();
 248   unsigned Op1Opc = Op1.getOpcode();
 249
 250   // Verify that we have the correct opcodes
 251   if (ISD::SHL != Op0Opc && ISD::SRL != Op0Opc && ISD::AND != Op0Opc)
 252     return false;
 253   if (ISD::SHL != Op1Opc && ISD::SRL != Op1Opc && ISD::AND != Op1Opc)
 254     return false;
 255
 256   // Generate Mask value for Target
 257   if (isIntImmediate(Op0.getOperand(1), Value)) {
 258     switch(Op0Opc) {
 259       case ISD::SHL: TgtMask <<= Value; break;
 260       case ISD::SRL: TgtMask >>= Value; break;
 261       case ISD::AND: TgtMask &= Value; break;
 262     }
 263   } else {
 264     return 0;
 265   }
 266
 267   // Generate Mask value for Insert
 268   if (isIntImmediate(Op1.getOperand(1), Value)) {
 269     switch(Op1Opc) {
 270       case ISD::SHL:
 271         SH = Value;
 272         InsMask <<= SH;
 273         if (Op0Opc == ISD::SRL) IsRotate = true;
 274           break;
 275       case ISD::SRL:
 276         SH = Value;
 277         InsMask >>= SH;
 278         SH = 32-SH;
 279         if (Op0Opc == ISD::SHL) IsRotate = true;
 280           break;
 281       case ISD::AND:
 282         InsMask &= Value;
 283         break;
 284     }
 285   } else {
 286     return 0;
 287   }
 288
 289   // If both of the inputs are ANDs and one of them has a logical shift by
 290   // constant as its input, make that AND the inserted value so that we can
 291   // combine the shift into the rotate part of the rlwimi instruction
 292   bool IsAndWithShiftOp = false;
 293   if (Op0Opc == ISD::AND && Op1Opc == ISD::AND) {
 294     if (Op1.getOperand(0).getOpcode() == ISD::SHL ||
 295         Op1.getOperand(0).getOpcode() == ISD::SRL) {
 296       if (isIntImmediate(Op1.getOperand(0).getOperand(1), Value)) {
 297         SH = Op1.getOperand(0).getOpcode() == ISD::SHL ? Value : 32 - Value;
 298         IsAndWithShiftOp = true;
 299       }
 300     } else if (Op0.getOperand(0).getOpcode() == ISD::SHL ||
 301                Op0.getOperand(0).getOpcode() == ISD::SRL) {
 302       if (isIntImmediate(Op0.getOperand(0).getOperand(1), Value)) {
 303         std::swap(Op0, Op1);
 304         std::swap(TgtMask, InsMask);
 305         SH = Op1.getOperand(0).getOpcode() == ISD::SHL ? Value : 32 - Value;
 306         IsAndWithShiftOp = true;
 307       }
 308     }
 309   }
 310
 311   // Verify that the Target mask and Insert mask together form a full word mask
 312   // and that the Insert mask is a run of set bits (which implies both are runs
 313   // of set bits).  Given that, Select the arguments and generate the rlwimi
 314   // instruction.
 315   unsigned MB, ME;
 316   if (((TgtMask & InsMask) == 0) && isRunOfOnes(InsMask, MB, ME)) {
 317     bool fullMask = (TgtMask ^ InsMask) == 0xFFFFFFFF;
 318     bool Op0IsAND = Op0Opc == ISD::AND;
 319     // Check for rotlwi / rotrwi here, a special case of bitfield insert
 320     // where both bitfield halves are sourced from the same value.
 321     if (IsRotate && fullMask &&
 322         N->getOperand(0).getOperand(0) == N->getOperand(1).getOperand(0)) {
 323       Op0 = CurDAG->getTargetNode(PPC::RLWINM, MVT::i32,
 324                                   Select(N->getOperand(0).getOperand(0)),
 325                                   getI32Imm(SH), getI32Imm(0), getI32Imm(31));
 326       return Op0.Val;
 327     }
 328     SDOperand Tmp1 = (Op0IsAND && fullMask) ? Select(Op0.getOperand(0))
 329                                             : Select(Op0);
 330     SDOperand Tmp2 = IsAndWithShiftOp ? Select(Op1.getOperand(0).getOperand(0))
 331                                       : Select(Op1.getOperand(0));
 332     Op0 = CurDAG->getTargetNode(PPC::RLWIMI, MVT::i32, Tmp1, Tmp2,
 333                                 getI32Imm(SH), getI32Imm(MB), getI32Imm(ME));
 334     return Op0.Val;
 335   }
 336   return 0;
 337 }
 338
 339 // SelectIntImmediateExpr - Choose code for integer operations with an immediate
 340 // operand.
 341 SDNode *PPC32DAGToDAGISel::SelectIntImmediateExpr(SDOperand LHS, SDOperand RHS,
 342                                                   unsigned OCHi, unsigned OCLo,
 343                                                   bool IsArithmetic,
 344                                                   bool Negate) {
 345   // Check to make sure this is a constant.
 346   ConstantSDNode *CN = dyn_cast<ConstantSDNode>(RHS);
 347   // Exit if not a constant.
 348   if (!CN) return 0;
 349   // Extract immediate.
 350   unsigned C = (unsigned)CN->getValue();
 351   // Negate if required (ISD::SUB).
 352   if (Negate) C = -C;
 353   // Get the hi and lo portions of constant.
 354   unsigned Hi = IsArithmetic ? HA16(C) : Hi16(C);
 355   unsigned Lo = Lo16(C);
 356
 357   // If two instructions are needed and usage indicates it would be better to
 358   // load immediate into a register, bail out.
 359   if (Hi && Lo && CN->use_size() > 2) return false;
 360
 361   // Select the first operand.
 362   SDOperand Opr0 = Select(LHS);
 363
 364   if (Lo)  // Add in the lo-part.
 365     Opr0 = CurDAG->getTargetNode(OCLo, MVT::i32, Opr0, getI32Imm(Lo));
 366   if (Hi)  // Add in the hi-part.
 367     Opr0 = CurDAG->getTargetNode(OCHi, MVT::i32, Opr0, getI32Imm(Hi));
 368   return Opr0.Val;
 369 }
 370
 371 /// SelectAddr - Given the specified address, return the two operands for a
 372 /// load/store instruction, and return true if it should be an indexed [r+r]
 373 /// operation.
 374 bool PPC32DAGToDAGISel::SelectAddr(SDOperand Addr, SDOperand &Op1,
 375                                    SDOperand &Op2) {
 376   unsigned imm = 0;
 377   if (Addr.getOpcode() == ISD::ADD) {
 378     if (isIntImmediate(Addr.getOperand(1), imm) && isInt16(imm)) {
 379       Op1 = getI32Imm(Lo16(imm));
 380       if (FrameIndexSDNode *FI =
 381             dyn_cast<FrameIndexSDNode>(Addr.getOperand(0))) {
 382         ++FrameOff;
 383         Op2 = CurDAG->getTargetFrameIndex(FI->getIndex(), MVT::i32);
 384       } else {
 385         Op2 = Select(Addr.getOperand(0));
 386       }
 387       return false;
 388     } else {
 389       Op1 = Select(Addr.getOperand(0));
 390       Op2 = Select(Addr.getOperand(1));
 391       return true;   // [r+r]
 392     }
 393   }
 394
 395   // Now check if we're dealing with a global, and whether or not we should emit
 396   // an optimized load or store for statics.
 397   if (GlobalAddressSDNode *GN = dyn_cast<GlobalAddressSDNode>(Addr)) {
 398     GlobalValue *GV = GN->getGlobal();
 399     if (!GV->hasWeakLinkage() && !GV->isExternal()) {
 400       Op1 = CurDAG->getTargetGlobalAddress(GV, MVT::i32);
 401       if (PICEnabled)
 402         Op2 = CurDAG->getTargetNode(PPC::ADDIS, MVT::i32, getGlobalBaseReg(),
 403                                     Op1);
 404       else
 405         Op2 = CurDAG->getTargetNode(PPC::LIS, MVT::i32, Op1);
 406       return false;
 407     }
 408   } else if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(Addr)) {
 409     Op1 = getI32Imm(0);
 410     Op2 = CurDAG->getTargetFrameIndex(FI->getIndex(), MVT::i32);
 411     return false;
 412   } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Addr)) {
 413     Op1 = Addr;
 414     if (PICEnabled)
 415       Op2 = CurDAG->getTargetNode(PPC::ADDIS, MVT::i32, getGlobalBaseReg(),Op1);
 416     else
 417       Op2 = CurDAG->getTargetNode(PPC::LIS, MVT::i32, Op1);
 418     return false;
 419   }
 420   Op1 = getI32Imm(0);
 421   Op2 = Select(Addr);
 422   return false;
 423 }
 424
 425 /// SelectCC - Select a comparison of the specified values with the specified
 426 /// condition code, returning the CR# of the expression.
 427 SDOperand PPC32DAGToDAGISel::SelectCC(SDOperand LHS, SDOperand RHS,
 428                                       ISD::CondCode CC) {
 429   // Always select the LHS.
 430   LHS = Select(LHS);
 431
 432   // Use U to determine whether the SETCC immediate range is signed or not.
 433   if (MVT::isInteger(LHS.getValueType())) {
 434     bool U = ISD::isUnsignedIntSetCC(CC);
 435     unsigned Imm;
 436     if (isIntImmediate(RHS, Imm) &&
 437         ((U && isUInt16(Imm)) || (!U && isInt16(Imm))))
 438       return CurDAG->getTargetNode(U ? PPC::CMPLWI : PPC::CMPWI, MVT::i32,
 439                                    LHS, getI32Imm(Lo16(Imm)));
 440     return CurDAG->getTargetNode(U ? PPC::CMPLW : PPC::CMPW, MVT::i32,
 441                                  LHS, Select(RHS));
 442   } else {
 443     return CurDAG->getTargetNode(PPC::FCMPU, MVT::i32, LHS, Select(RHS));
 444   }
 445 }
 446
 447 /// getBCCForSetCC - Returns the PowerPC condition branch mnemonic corresponding
 448 /// to Condition.
 449 static unsigned getBCCForSetCC(ISD::CondCode CC) {
 450   switch (CC) {
 451   default: assert(0 && "Unknown condition!"); abort();
 452   case ISD::SETEQ:  return PPC::BEQ;
 453   case ISD::SETNE:  return PPC::BNE;
 454   case ISD::SETULT:
 455   case ISD::SETLT:  return PPC::BLT;
 456   case ISD::SETULE:
 457   case ISD::SETLE:  return PPC::BLE;
 458   case ISD::SETUGT:
 459   case ISD::SETGT:  return PPC::BGT;
 460   case ISD::SETUGE:
 461   case ISD::SETGE:  return PPC::BGE;
 462   }
 463   return 0;
 464 }
 465
 466 /// getCRIdxForSetCC - Return the index of the condition register field
 467 /// associated with the SetCC condition, and whether or not the field is
 468 /// treated as inverted.  That is, lt = 0; ge = 0 inverted.
 469 static unsigned getCRIdxForSetCC(ISD::CondCode CC, bool& Inv) {
 470   switch (CC) {
 471   default: assert(0 && "Unknown condition!"); abort();
 472   case ISD::SETULT:
 473   case ISD::SETLT:  Inv = false;  return 0;
 474   case ISD::SETUGE:
 475   case ISD::SETGE:  Inv = true;   return 0;
 476   case ISD::SETUGT:
 477   case ISD::SETGT:  Inv = false;  return 1;
 478   case ISD::SETULE:
 479   case ISD::SETLE:  Inv = true;   return 1;
 480   case ISD::SETEQ:  Inv = false;  return 2;
 481   case ISD::SETNE:  Inv = true;   return 2;
 482   }
 483   return 0;
 484 }
 485
 486 // Structure used to return the necessary information to codegen an SDIV as
 487 // a multiply.
 488 struct ms {
 489   int m; // magic number
 490   int s; // shift amount
 491 };
 492
 493 struct mu {
 494   unsigned int m; // magic number
 495   int a;          // add indicator
 496   int s;          // shift amount
 497 };
 498
 499 /// magic - calculate the magic numbers required to codegen an integer sdiv as
 500 /// a sequence of multiply and shifts.  Requires that the divisor not be 0, 1,
 501 /// or -1.
 502 static struct ms magic(int d) {
 503   int p;
 504   unsigned int ad, anc, delta, q1, r1, q2, r2, t;
 505   const unsigned int two31 = 0x80000000U;
 506   struct ms mag;
 507
 508   ad = abs(d);
 509   t = two31 + ((unsigned int)d >> 31);
 510   anc = t - 1 - t%ad;   // absolute value of nc
 511   p = 31;               // initialize p
 512   q1 = two31/anc;       // initialize q1 = 2p/abs(nc)
 513   r1 = two31 - q1*anc;  // initialize r1 = rem(2p,abs(nc))
 514   q2 = two31/ad;        // initialize q2 = 2p/abs(d)
 515   r2 = two31 - q2*ad;   // initialize r2 = rem(2p,abs(d))
 516   do {
 517     p = p + 1;
 518     q1 = 2*q1;        // update q1 = 2p/abs(nc)
 519     r1 = 2*r1;        // update r1 = rem(2p/abs(nc))
 520     if (r1 >= anc) {  // must be unsigned comparison
 521       q1 = q1 + 1;
 522       r1 = r1 - anc;
 523     }
 524     q2 = 2*q2;        // update q2 = 2p/abs(d)
 525     r2 = 2*r2;        // update r2 = rem(2p/abs(d))
 526     if (r2 >= ad) {   // must be unsigned comparison
 527       q2 = q2 + 1;
 528       r2 = r2 - ad;
 529     }
 530     delta = ad - r2;
 531   } while (q1 < delta || (q1 == delta && r1 == 0));
 532
 533   mag.m = q2 + 1;
 534   if (d < 0) mag.m = -mag.m; // resulting magic number
 535   mag.s = p - 32;            // resulting shift
 536   return mag;
 537 }
 538
 539 /// magicu - calculate the magic numbers required to codegen an integer udiv as
 540 /// a sequence of multiply, add and shifts.  Requires that the divisor not be 0.
 541 static struct mu magicu(unsigned d)
 542 {
 543   int p;
 544   unsigned int nc, delta, q1, r1, q2, r2;
 545   struct mu magu;
 546   magu.a = 0;               // initialize "add" indicator
 547   nc = - 1 - (-d)%d;
 548   p = 31;                   // initialize p
 549   q1 = 0x80000000/nc;       // initialize q1 = 2p/nc
 550   r1 = 0x80000000 - q1*nc;  // initialize r1 = rem(2p,nc)
 551   q2 = 0x7FFFFFFF/d;        // initialize q2 = (2p-1)/d
 552   r2 = 0x7FFFFFFF - q2*d;   // initialize r2 = rem((2p-1),d)
 553   do {
 554     p = p + 1;
 555     if (r1 >= nc - r1 ) {
 556       q1 = 2*q1 + 1;  // update q1
 557       r1 = 2*r1 - nc; // update r1
 558     }
 559     else {
 560       q1 = 2*q1; // update q1
 561       r1 = 2*r1; // update r1
 562     }
 563     if (r2 + 1 >= d - r2) {
 564       if (q2 >= 0x7FFFFFFF) magu.a = 1;
 565       q2 = 2*q2 + 1;     // update q2
 566       r2 = 2*r2 + 1 - d; // update r2
 567     }
 568     else {
 569       if (q2 >= 0x80000000) magu.a = 1;
 570       q2 = 2*q2;     // update q2
 571       r2 = 2*r2 + 1; // update r2
 572     }
 573     delta = d - 1 - r2;
 574   } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
 575   magu.m = q2 + 1; // resulting magic number
 576   magu.s = p - 32;  // resulting shift
 577   return magu;
 578 }
 579
 580 /// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant,
 581 /// return a DAG expression to select that will generate the same value by
 582 /// multiplying by a magic number.  See:
 583 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
 584 SDOperand PPC32DAGToDAGISel::BuildSDIVSequence(SDNode *N) {
 585   int d = (int)cast<ConstantSDNode>(N->getOperand(1))->getValue();
 586   ms magics = magic(d);
 587   // Multiply the numerator (operand 0) by the magic value
 588   SDOperand Q = CurDAG->getNode(ISD::MULHS, MVT::i32, N->getOperand(0),
 589                                 CurDAG->getConstant(magics.m, MVT::i32));
 590   // If d > 0 and m < 0, add the numerator
 591   if (d > 0 && magics.m < 0)
 592     Q = CurDAG->getNode(ISD::ADD, MVT::i32, Q, N->getOperand(0));
 593   // If d < 0 and m > 0, subtract the numerator.
 594   if (d < 0 && magics.m > 0)
 595     Q = CurDAG->getNode(ISD::SUB, MVT::i32, Q, N->getOperand(0));
 596   // Shift right algebraic if shift value is nonzero
 597   if (magics.s > 0)
 598     Q = CurDAG->getNode(ISD::SRA, MVT::i32, Q,
 599                         CurDAG->getConstant(magics.s, MVT::i32));
 600   // Extract the sign bit and add it to the quotient
 601   SDOperand T =
 602     CurDAG->getNode(ISD::SRL, MVT::i32, Q, CurDAG->getConstant(31, MVT::i32));
 603   return CurDAG->getNode(ISD::ADD, MVT::i32, Q, T);
 604 }
 605
 606 /// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant,
 607 /// return a DAG expression to select that will generate the same value by
 608 /// multiplying by a magic number.  See:
 609 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
 610 SDOperand PPC32DAGToDAGISel::BuildUDIVSequence(SDNode *N) {
 611   unsigned d = (unsigned)cast<ConstantSDNode>(N->getOperand(1))->getValue();
 612   mu magics = magicu(d);
 613   // Multiply the numerator (operand 0) by the magic value
 614   SDOperand Q = CurDAG->getNode(ISD::MULHU, MVT::i32, N->getOperand(0),
 615                                 CurDAG->getConstant(magics.m, MVT::i32));
 616   if (magics.a == 0) {
 617     return CurDAG->getNode(ISD::SRL, MVT::i32, Q,
 618                            CurDAG->getConstant(magics.s, MVT::i32));
 619   } else {
 620     SDOperand NPQ = CurDAG->getNode(ISD::SUB, MVT::i32, N->getOperand(0), Q);
 621     NPQ = CurDAG->getNode(ISD::SRL, MVT::i32, NPQ,
 622                            CurDAG->getConstant(1, MVT::i32));
 623     NPQ = CurDAG->getNode(ISD::ADD, MVT::i32, NPQ, Q);
 624     return CurDAG->getNode(ISD::SRL, MVT::i32, NPQ,
 625                            CurDAG->getConstant(magics.s-1, MVT::i32));
 626   }
 627 }
 628
 629 // Select - Convert the specified operand from a target-independent to a
 630 // target-specific node if it hasn't already been changed.
 631 SDOperand PPC32DAGToDAGISel::Select(SDOperand Op) {
 632   SDNode *N = Op.Val;
 633   if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
 634       N->getOpcode() < PPCISD::FIRST_NUMBER)
 635     return Op;   // Already selected.
 636
 637   switch (N->getOpcode()) {
 638   default:
 639     std::cerr << "Cannot yet select: ";
 640     N->dump();
 641     std::cerr << "\n";
 642     abort();
 643   case ISD::EntryToken:       // These leaves remain the same.
 644     return Op;
 645   case ISD::TokenFactor: {
 646     SDOperand New;
 647     if (N->getNumOperands() == 2) {
 648       SDOperand Op0 = Select(N->getOperand(0));
 649       SDOperand Op1 = Select(N->getOperand(1));
 650       New = CurDAG->getNode(ISD::TokenFactor, MVT::Other, Op0, Op1);
 651     } else {
 652       std::vector<SDOperand> Ops;
 653       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
 654         Ops.push_back(Select(N->getOperand(i)));
 655       New = CurDAG->getNode(ISD::TokenFactor, MVT::Other, Ops);
 656     }
 657
 658     if (New.Val != N) {
 659       CurDAG->ReplaceAllUsesWith(Op, New);
 660       N = New.Val;
 661     }
 662     break;
 663   }
 664   case ISD::CopyFromReg: {
 665     SDOperand Chain = Select(N->getOperand(0));
 666     if (Chain == N->getOperand(0)) return Op; // No change
 667     SDOperand New = CurDAG->getCopyFromReg(Chain,
 668          cast<RegisterSDNode>(N->getOperand(1))->getReg(), N->getValueType(0));
 669     return New.getValue(Op.ResNo);
 670   }
 671   case ISD::CopyToReg: {
 672     SDOperand Chain = Select(N->getOperand(0));
 673     SDOperand Reg = N->getOperand(1);
 674     SDOperand Val = Select(N->getOperand(2));
 675     if (Chain != N->getOperand(0) || Val != N->getOperand(2)) {
 676       SDOperand New = CurDAG->getNode(ISD::CopyToReg, MVT::Other,
 677                                       Chain, Reg, Val);
 678       CurDAG->ReplaceAllUsesWith(Op, New);
 679       N = New.Val;
 680     }
 681     break;
 682   }
 683   case ISD::Constant: {
 684     assert(N->getValueType(0) == MVT::i32);
 685     unsigned v = (unsigned)cast<ConstantSDNode>(N)->getValue();
 686     unsigned Hi = HA16(v);
 687     unsigned Lo = Lo16(v);
 688     if (Hi && Lo) {
 689       SDOperand Top = CurDAG->getTargetNode(PPC::LIS, MVT::i32,
 690                                             getI32Imm(v >> 16));
 691       CurDAG->SelectNodeTo(N, PPC::ORI, MVT::i32, Top, getI32Imm(v & 0xFFFF));
 692     } else if (Lo) {
 693       CurDAG->SelectNodeTo(N, PPC::LI, MVT::i32, getI32Imm(v));
 694     } else {
 695       CurDAG->SelectNodeTo(N, PPC::LIS, MVT::i32, getI32Imm(v >> 16));
 696     }
 697     break;
 698   }
 699   case ISD::UNDEF:
 700     if (N->getValueType(0) == MVT::i32)
 701       CurDAG->SelectNodeTo(N, PPC::IMPLICIT_DEF_GPR, MVT::i32);
 702     else
 703       CurDAG->SelectNodeTo(N, PPC::IMPLICIT_DEF_FP, N->getValueType(0));
 704     break;
 705   case ISD::FrameIndex: {
 706     int FI = cast<FrameIndexSDNode>(N)->getIndex();
 707     CurDAG->SelectNodeTo(N, PPC::ADDI, MVT::i32,
 708                          CurDAG->getTargetFrameIndex(FI, MVT::i32),
 709                          getI32Imm(0));
 710     break;
 711   }
 712   case ISD::ConstantPool: {
 713     Constant *C = cast<ConstantPoolSDNode>(N)->get();
 714     SDOperand Tmp, CPI = CurDAG->getTargetConstantPool(C, MVT::i32);
 715     if (PICEnabled)
 716       Tmp = CurDAG->getTargetNode(PPC::ADDIS, MVT::i32, getGlobalBaseReg(),CPI);
 717     else
 718       Tmp = CurDAG->getTargetNode(PPC::LIS, MVT::i32, CPI);
 719     CurDAG->SelectNodeTo(N, PPC::LA, MVT::i32, Tmp, CPI);
 720     break;
 721   }
 722   case ISD::GlobalAddress: {
 723     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
 724     SDOperand Tmp;
 725     SDOperand GA = CurDAG->getTargetGlobalAddress(GV, MVT::i32);
 726     if (PICEnabled)
 727       Tmp = CurDAG->getTargetNode(PPC::ADDIS, MVT::i32, getGlobalBaseReg(), GA);
 728     else
 729       Tmp = CurDAG->getTargetNode(PPC::LIS, MVT::i32, GA);
 730
 731     if (GV->hasWeakLinkage() || GV->isExternal())
 732       CurDAG->SelectNodeTo(N, PPC::LWZ, MVT::i32, GA, Tmp);
 733     else
 734       CurDAG->SelectNodeTo(N, PPC::LA, MVT::i32, Tmp, GA);
 735     break;
 736   }
 737   case ISD::SIGN_EXTEND_INREG:
 738     switch(cast<VTSDNode>(N->getOperand(1))->getVT()) {
 739     default: assert(0 && "Illegal type in SIGN_EXTEND_INREG"); break;
 740     case MVT::i16:
 741       CurDAG->SelectNodeTo(N, PPC::EXTSH, MVT::i32, Select(N->getOperand(0)));
 742       break;
 743     case MVT::i8:
 744       CurDAG->SelectNodeTo(N, PPC::EXTSB, MVT::i32, Select(N->getOperand(0)));
 745       break;
 746     }
 747     break;
 748   case ISD::CTLZ:
 749     assert(N->getValueType(0) == MVT::i32);
 750     CurDAG->SelectNodeTo(N, PPC::CNTLZW, MVT::i32, Select(N->getOperand(0)));
 751     break;
 752   case PPCISD::FSEL:
 753     CurDAG->SelectNodeTo(N, PPC::FSEL, N->getValueType(0),
 754                          Select(N->getOperand(0)),
 755                          Select(N->getOperand(1)),
 756                          Select(N->getOperand(2)));
 757     break;
 758   case ISD::ADD: {
 759     MVT::ValueType Ty = N->getValueType(0);
 760     if (Ty == MVT::i32) {
 761       if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0), N->getOperand(1),
 762                                              PPC::ADDIS, PPC::ADDI, true)) {
 763         CurDAG->ReplaceAllUsesWith(Op, SDOperand(I, 0));
 764         N = I;
 765       } else {
 766         CurDAG->SelectNodeTo(N, PPC::ADD, MVT::i32, Select(N->getOperand(0)),
 767                              Select(N->getOperand(1)));
 768       }
 769       break;
 770     }
 771
 772     if (!NoExcessFPPrecision) {  // Match FMA ops
 773       if (N->getOperand(0).getOpcode() == ISD::MUL &&
 774           N->getOperand(0).Val->hasOneUse()) {
 775         ++FusedFP; // Statistic
 776         CurDAG->SelectNodeTo(N, Ty == MVT::f64 ? PPC::FMADD : PPC::FMADDS, Ty,
 777                              Select(N->getOperand(0).getOperand(0)),
 778                              Select(N->getOperand(0).getOperand(1)),
 779                              Select(N->getOperand(1)));
 780         break;
 781       } else if (N->getOperand(1).getOpcode() == ISD::MUL &&
 782                  N->getOperand(1).hasOneUse()) {
 783         ++FusedFP; // Statistic
 784         CurDAG->SelectNodeTo(N, Ty == MVT::f64 ? PPC::FMADD : PPC::FMADDS, Ty,
 785                              Select(N->getOperand(1).getOperand(0)),
 786                              Select(N->getOperand(1).getOperand(1)),
 787                              Select(N->getOperand(0)));
 788         break;
 789       }
 790     }
 791
 792     CurDAG->SelectNodeTo(N, Ty == MVT::f64 ? PPC::FADD : PPC::FADDS, Ty,
 793                          Select(N->getOperand(0)), Select(N->getOperand(1)));
 794     break;
 795   }
 796   case ISD::SUB: {
 797     MVT::ValueType Ty = N->getValueType(0);
 798     if (Ty == MVT::i32) {
 799       unsigned Imm;
 800       if (isIntImmediate(N->getOperand(0), Imm) && isInt16(Imm)) {
 801         if (0 == Imm)
 802           CurDAG->SelectNodeTo(N, PPC::NEG, Ty, Select(N->getOperand(1)));
 803         else
 804           CurDAG->SelectNodeTo(N, PPC::SUBFIC, Ty, Select(N->getOperand(1)),
 805                                getI32Imm(Lo16(Imm)));
 806         break;
 807       }
 808       if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0), N->getOperand(1),
 809                                           PPC::ADDIS, PPC::ADDI, true, true)) {
 810         CurDAG->ReplaceAllUsesWith(Op, SDOperand(I, 0));
 811         N = I;
 812       } else {
 813         CurDAG->SelectNodeTo(N, PPC::SUBF, Ty, Select(N->getOperand(1)),
 814                              Select(N->getOperand(0)));
 815       }
 816       break;
 817     }
 818
 819     if (!NoExcessFPPrecision) {  // Match FMA ops
 820       if (N->getOperand(0).getOpcode() == ISD::MUL &&
 821           N->getOperand(0).Val->hasOneUse()) {
 822         ++FusedFP; // Statistic
 823         CurDAG->SelectNodeTo(N, Ty == MVT::f64 ? PPC::FMSUB : PPC::FMSUBS, Ty,
 824                              Select(N->getOperand(0).getOperand(0)),
 825                              Select(N->getOperand(0).getOperand(1)),
 826                              Select(N->getOperand(1)));
 827         break;
 828       } else if (N->getOperand(1).getOpcode() == ISD::MUL &&
 829                  N->getOperand(1).Val->hasOneUse()) {
 830         ++FusedFP; // Statistic
 831         CurDAG->SelectNodeTo(N, Ty == MVT::f64 ? PPC::FNMSUB : PPC::FNMSUBS, Ty,
 832                              Select(N->getOperand(1).getOperand(0)),
 833                              Select(N->getOperand(1).getOperand(1)),
 834                              Select(N->getOperand(0)));
 835         break;
 836       }
 837     }
 838     CurDAG->SelectNodeTo(N, Ty == MVT::f64 ? PPC::FSUB : PPC::FSUBS, Ty,
 839                          Select(N->getOperand(0)),
 840                          Select(N->getOperand(1)));
 841     break;
 842   }
 843   case ISD::MUL: {
 844     unsigned Imm, Opc;
 845     if (isIntImmediate(N->getOperand(1), Imm) && isInt16(Imm)) {
 846       CurDAG->SelectNodeTo(N, PPC::MULLI, MVT::i32,
 847                            Select(N->getOperand(0)), getI32Imm(Lo16(Imm)));
 848       break;
 849     }
 850     switch (N->getValueType(0)) {
 851       default: assert(0 && "Unhandled multiply type!");
 852       case MVT::i32: Opc = PPC::MULLW; break;
 853       case MVT::f32: Opc = PPC::FMULS; break;
 854       case MVT::f64: Opc = PPC::FMUL;  break;
 855     }
 856     CurDAG->SelectNodeTo(N, Opc, N->getValueType(0), Select(N->getOperand(0)),
 857                          Select(N->getOperand(1)));
 858     break;
 859   }
 860   case ISD::SDIV: {
 861     unsigned Imm;
 862     if (isIntImmediate(N->getOperand(1), Imm)) {
 863       if ((signed)Imm > 0 && isPowerOf2_32(Imm)) {
 864         SDOperand Op =
 865           CurDAG->getTargetNode(PPC::SRAWI, MVT::i32, MVT::Flag,
 866                                 Select(N->getOperand(0)),
 867                                 getI32Imm(Log2_32(Imm)));
 868         CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
 869                              Op.getValue(0), Op.getValue(1));
 870         break;
 871       } else if ((signed)Imm < 0 && isPowerOf2_32(-Imm)) {
 872         SDOperand Op =
 873           CurDAG->getTargetNode(PPC::SRAWI, MVT::Flag, MVT::i32,
 874                                 Select(N->getOperand(0)),
 875                                 getI32Imm(Log2_32(-Imm)));
 876         SDOperand PT =
 877           CurDAG->getTargetNode(PPC::ADDZE, MVT::i32, Op.getValue(1),
 878                                 Op.getValue(0));
 879         CurDAG->SelectNodeTo(N, PPC::NEG, MVT::i32, PT);
 880         break;
 881       } else if (Imm) {
 882         SDOperand Result = Select(BuildSDIVSequence(N));
 883         assert(Result.ResNo == 0);
 884         CurDAG->ReplaceAllUsesWith(Op, Result);
 885         N = Result.Val;
 886         break;
 887       }
 888     }
 889
 890     unsigned Opc;
 891     switch (N->getValueType(0)) {
 892     default: assert(0 && "Unknown type to ISD::SDIV");
 893     case MVT::i32: Opc = PPC::DIVW; break;
 894     case MVT::f32: Opc = PPC::FDIVS; break;
 895     case MVT::f64: Opc = PPC::FDIV; break;
 896     }
 897     CurDAG->SelectNodeTo(N, Opc, N->getValueType(0), Select(N->getOperand(0)),
 898                          Select(N->getOperand(1)));
 899     break;
 900   }
 901   case ISD::UDIV: {
 902     // If this is a divide by constant, we can emit code using some magic
 903     // constants to implement it as a multiply instead.
 904     unsigned Imm;
 905     if (isIntImmediate(N->getOperand(1), Imm) && Imm) {
 906       SDOperand Result = Select(BuildUDIVSequence(N));
 907       assert(Result.ResNo == 0);
 908       CurDAG->ReplaceAllUsesWith(Op, Result);
 909       N = Result.Val;
 910       break;
 911     }
 912
 913     CurDAG->SelectNodeTo(N, PPC::DIVWU, MVT::i32, Select(N->getOperand(0)),
 914                          Select(N->getOperand(1)));
 915     break;
 916   }
 917   case ISD::MULHS:
 918     assert(N->getValueType(0) == MVT::i32);
 919     CurDAG->SelectNodeTo(N, PPC::MULHW, MVT::i32, Select(N->getOperand(0)),
 920                          Select(N->getOperand(1)));
 921     break;
 922   case ISD::MULHU:
 923     assert(N->getValueType(0) == MVT::i32);
 924     CurDAG->SelectNodeTo(N, PPC::MULHWU, MVT::i32, Select(N->getOperand(0)),
 925                          Select(N->getOperand(1)));
 926     break;
 927   case ISD::AND: {
 928     unsigned Imm;
 929     // If this is an and of a value rotated between 0 and 31 bits and then and'd
 930     // with a mask, emit rlwinm
 931     if (isIntImmediate(N->getOperand(1), Imm) && (isShiftedMask_32(Imm) ||
 932                                                   isShiftedMask_32(~Imm))) {
 933       SDOperand Val;
 934       unsigned SH, MB, ME;
 935       if (isRotateAndMask(N->getOperand(0).Val, Imm, false, SH, MB, ME)) {
 936         Val = Select(N->getOperand(0).getOperand(0));
 937       } else {
 938         Val = Select(N->getOperand(0));
 939         isRunOfOnes(Imm, MB, ME);
 940         SH = 0;
 941       }
 942       CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Val, getI32Imm(SH),
 943                            getI32Imm(MB), getI32Imm(ME));
 944       break;
 945     }
 946     // If this is an and with an immediate that isn't a mask, then codegen it as
 947     // high and low 16 bit immediate ands.
 948     if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0),
 949                                            N->getOperand(1),
 950                                            PPC::ANDISo, PPC::ANDIo)) {
 951       CurDAG->ReplaceAllUsesWith(Op, SDOperand(I, 0));
 952       N = I;
 953       break;
 954     }
 955     // Finally, check for the case where we are being asked to select
 956     // and (not(a), b) or and (a, not(b)) which can be selected as andc.
 957     if (isOprNot(N->getOperand(0).Val))
 958       CurDAG->SelectNodeTo(N, PPC::ANDC, MVT::i32, Select(N->getOperand(1)),
 959                            Select(N->getOperand(0).getOperand(0)));
 960     else if (isOprNot(N->getOperand(1).Val))
 961       CurDAG->SelectNodeTo(N, PPC::ANDC, MVT::i32, Select(N->getOperand(0)),
 962                            Select(N->getOperand(1).getOperand(0)));
 963     else
 964       CurDAG->SelectNodeTo(N, PPC::AND, MVT::i32, Select(N->getOperand(0)),
 965                            Select(N->getOperand(1)));
 966     break;
 967   }
 968   case ISD::OR:
 969     if (SDNode *I = SelectBitfieldInsert(N)) {
 970       CurDAG->ReplaceAllUsesWith(Op, SDOperand(I, 0));
 971       N = I;
 972       break;
 973     }
 974     if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0),
 975                                            N->getOperand(1),
 976                                            PPC::ORIS, PPC::ORI)) {
 977       CurDAG->ReplaceAllUsesWith(Op, SDOperand(I, 0));
 978       N = I;
 979       break;
 980     }
 981     // Finally, check for the case where we are being asked to select
 982     // 'or (not(a), b)' or 'or (a, not(b))' which can be selected as orc.
 983     if (isOprNot(N->getOperand(0).Val))
 984       CurDAG->SelectNodeTo(N, PPC::ORC, MVT::i32, Select(N->getOperand(1)),
 985                            Select(N->getOperand(0).getOperand(0)));
 986     else if (isOprNot(N->getOperand(1).Val))
 987       CurDAG->SelectNodeTo(N, PPC::ORC, MVT::i32, Select(N->getOperand(0)),
 988                            Select(N->getOperand(1).getOperand(0)));
 989     else
 990       CurDAG->SelectNodeTo(N, PPC::OR, MVT::i32, Select(N->getOperand(0)),
 991                            Select(N->getOperand(1)));
 992     break;
 993   case ISD::XOR:
 994     // Check whether or not this node is a logical 'not'.  This is represented
 995     // by llvm as a xor with the constant value -1 (all bits set).  If this is a
 996     // 'not', then fold 'or' into 'nor', and so forth for the supported ops.
 997     if (isOprNot(N)) {
 998       unsigned Opc;
 999       SDOperand Val = Select(N->getOperand(0));
1000       switch (Val.isTargetOpcode() ? Val.getTargetOpcode() : 0) {
1001       default:        Opc = 0;          break;
1002       case PPC::OR:   Opc = PPC::NOR;   break;
1003       case PPC::AND:  Opc = PPC::NAND;  break;
1004       case PPC::XOR:  Opc = PPC::EQV;   break;
1005       }
1006       if (Opc)
1007         CurDAG->SelectNodeTo(N, Opc, MVT::i32, Val.getOperand(0),
1008                              Val.getOperand(1));
1009       else
1010         CurDAG->SelectNodeTo(N, PPC::NOR, MVT::i32, Val, Val);
1011       break;
1012     }
1013     // If this is a xor with an immediate other than -1, then codegen it as high
1014     // and low 16 bit immediate xors.
1015     if (SDNode *I = SelectIntImmediateExpr(N->getOperand(0),
1016                                            N->getOperand(1),
1017                                            PPC::XORIS, PPC::XORI)) {
1018       CurDAG->ReplaceAllUsesWith(Op, SDOperand(I, 0));
1019       N = I;
1020       break;
1021     }
1022     // Finally, check for the case where we are being asked to select
1023     // xor (not(a), b) which is equivalent to not(xor a, b), which is eqv
1024     if (isOprNot(N->getOperand(0).Val))
1025       CurDAG->SelectNodeTo(N, PPC::EQV, MVT::i32,
1026                            Select(N->getOperand(0).getOperand(0)),
1027                            Select(N->getOperand(1)));
1028     else
1029       CurDAG->SelectNodeTo(N, PPC::XOR, MVT::i32, Select(N->getOperand(0)),
1030                            Select(N->getOperand(1)));
1031     break;
1032   case ISD::SHL: {
1033     unsigned Imm, SH, MB, ME;
1034     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
1035         isRotateAndMask(N, Imm, true, SH, MB, ME))
1036       CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32,
1037                            Select(N->getOperand(0).getOperand(0)),
1038                            getI32Imm(SH), getI32Imm(MB), getI32Imm(ME));
1039     else if (isIntImmediate(N->getOperand(1), Imm))
1040       CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Select(N->getOperand(0)),
1041                            getI32Imm(Imm), getI32Imm(0), getI32Imm(31-Imm));
1042     else
1043       CurDAG->SelectNodeTo(N, PPC::SLW, MVT::i32, Select(N->getOperand(0)),
1044                            Select(N->getOperand(1)));
1045     break;
1046   }
1047   case ISD::SRL: {
1048     unsigned Imm, SH, MB, ME;
1049     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
1050         isRotateAndMask(N, Imm, true, SH, MB, ME))
1051       CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32,
1052                            Select(N->getOperand(0).getOperand(0)),
1053                            getI32Imm(SH), getI32Imm(MB), getI32Imm(ME));
1054     else if (isIntImmediate(N->getOperand(1), Imm))
1055       CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Select(N->getOperand(0)),
1056                            getI32Imm(32-Imm), getI32Imm(Imm), getI32Imm(31));
1057     else
1058       CurDAG->SelectNodeTo(N, PPC::SRW, MVT::i32, Select(N->getOperand(0)),
1059                            Select(N->getOperand(1)));
1060     break;
1061   }
1062   case ISD::SRA: {
1063     unsigned Imm, SH, MB, ME;
1064     if (isOpcWithIntImmediate(N->getOperand(0).Val, ISD::AND, Imm) &&
1065         isRotateAndMask(N, Imm, true, SH, MB, ME))
1066       CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32,
1067                            Select(N->getOperand(0).getOperand(0)),
1068                            getI32Imm(SH), getI32Imm(MB), getI32Imm(ME));
1069     else if (isIntImmediate(N->getOperand(1), Imm))
1070       CurDAG->SelectNodeTo(N, PPC::SRAWI, MVT::i32, Select(N->getOperand(0)),
1071                            getI32Imm(Imm));
1072     else
1073       CurDAG->SelectNodeTo(N, PPC::SRAW, MVT::i32, Select(N->getOperand(0)),
1074                            Select(N->getOperand(1)));
1075     break;
1076   }
1077   case ISD::FABS:
1078     CurDAG->SelectNodeTo(N, PPC::FABS, N->getValueType(0),
1079                          Select(N->getOperand(0)));
1080     break;
1081   case ISD::FP_EXTEND: {
1082     assert(MVT::f64 == N->getValueType(0) &&
1083            MVT::f32 == N->getOperand(0).getValueType() && "Illegal FP_EXTEND");
1084     std::vector<SDOperand> Tmp;
1085     Tmp.push_back(Select(N->getOperand(0)));
1086     CurDAG->ReplaceAllUsesWith(N, Tmp);  // Just use the operand as the result.
1087     return Tmp[0];
1088   }
1089   case ISD::FP_ROUND:
1090     assert(MVT::f32 == N->getValueType(0) &&
1091            MVT::f64 == N->getOperand(0).getValueType() && "Illegal FP_ROUND");
1092     CurDAG->SelectNodeTo(N, PPC::FRSP, MVT::f32, Select(N->getOperand(0)));
1093     break;
1094   case ISD::FP_TO_SINT: {
1095     SDOperand In = Select(N->getOperand(0));
1096     In = CurDAG->getTargetNode(PPC::FCTIWZ, MVT::f64, In);
1097
1098     int FrameIdx = BB->getParent()->getFrameInfo()->CreateStackObject(8, 8);
1099     SDOperand FI = CurDAG->getTargetFrameIndex(FrameIdx, MVT::f64);
1100     SDOperand ST = CurDAG->getTargetNode(PPC::STFD, MVT::Other, In, getI32Imm(0), FI);
1101     CurDAG->SelectNodeTo(N, PPC::LWZ, MVT::i32, MVT::Other, getI32Imm(4), FI, ST);
1102     break;
1103   }
1104   case ISD::FNEG: {
1105     SDOperand Val = Select(N->getOperand(0));
1106     MVT::ValueType Ty = N->getValueType(0);
1107     if (Val.Val->hasOneUse()) {
1108       unsigned Opc;
1109       switch (Val.isTargetOpcode() ? Val.getTargetOpcode() : 0) {
1110       default:          Opc = 0;            break;
1111       case PPC::FABS:   Opc = PPC::FNABS;   break;
1112       case PPC::FMADD:  Opc = PPC::FNMADD;  break;
1113       case PPC::FMADDS: Opc = PPC::FNMADDS; break;
1114       case PPC::FMSUB:  Opc = PPC::FNMSUB;  break;
1115       case PPC::FMSUBS: Opc = PPC::FNMSUBS; break;
1116       }
1117       // If we inverted the opcode, then emit the new instruction with the
1118       // inverted opcode and the original instruction's operands.  Otherwise,
1119       // fall through and generate a fneg instruction.
1120       if (Opc) {
1121         if (PPC::FNABS == Opc)
1122           CurDAG->SelectNodeTo(N, Opc, Ty, Val.getOperand(0));
1123         else
1124           CurDAG->SelectNodeTo(N, Opc, Ty, Val.getOperand(0),
1125                                Val.getOperand(1), Val.getOperand(2));
1126         break;
1127       }
1128     }
1129     CurDAG->SelectNodeTo(N, PPC::FNEG, Ty, Val);
1130     break;
1131   }
1132   case ISD::FSQRT: {
1133     MVT::ValueType Ty = N->getValueType(0);
1134     CurDAG->SelectNodeTo(N, Ty == MVT::f64 ? PPC::FSQRT : PPC::FSQRTS, Ty,
1135                          Select(N->getOperand(0)));
1136     break;
1137   }
1138
1139   case ISD::ADD_PARTS: {
1140     SDOperand LHSL = Select(N->getOperand(0));
1141     SDOperand LHSH = Select(N->getOperand(1));
1142
1143     unsigned Imm;
1144     bool ME = false, ZE = false;
1145     if (isIntImmediate(N->getOperand(3), Imm)) {
1146       ME = (signed)Imm == -1;
1147       ZE = Imm == 0;
1148     }
1149
1150     std::vector<SDOperand> Result;
1151     SDOperand CarryFromLo;
1152     if (isIntImmediate(N->getOperand(2), Imm) &&
1153         ((signed)Imm >= -32768 || (signed)Imm < 32768)) {
1154       // Codegen the low 32 bits of the add.  Interestingly, there is no
1155       // shifted form of add immediate carrying.
1156       CarryFromLo = CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
1157                                           LHSL, getI32Imm(Imm));
1158     } else {
1159       CarryFromLo = CurDAG->getTargetNode(PPC::ADDC, MVT::i32, MVT::Flag,
1160                                           LHSL, Select(N->getOperand(2)));
1161     }
1162     CarryFromLo = CarryFromLo.getValue(1);
1163
1164     // Codegen the high 32 bits, adding zero, minus one, or the full value
1165     // along with the carry flag produced by addc/addic.
1166     SDOperand ResultHi;
1167     if (ZE)
1168       ResultHi = CurDAG->getTargetNode(PPC::ADDZE, MVT::i32, LHSH, CarryFromLo);
1169     else if (ME)
1170       ResultHi = CurDAG->getTargetNode(PPC::ADDME, MVT::i32, LHSH, CarryFromLo);
1171     else
1172       ResultHi = CurDAG->getTargetNode(PPC::ADDE, MVT::i32, LHSH,
1173                                        Select(N->getOperand(3)), CarryFromLo);
1174     Result.push_back(ResultHi);
1175     Result.push_back(CarryFromLo.getValue(0));
1176     CurDAG->ReplaceAllUsesWith(N, Result);
1177     return Result[Op.ResNo];
1178   }
1179   case ISD::SUB_PARTS: {
1180     SDOperand LHSL = Select(N->getOperand(0));
1181     SDOperand LHSH = Select(N->getOperand(1));
1182     SDOperand RHSL = Select(N->getOperand(2));
1183     SDOperand RHSH = Select(N->getOperand(3));
1184
1185     std::vector<SDOperand> Result;
1186     Result.push_back(CurDAG->getTargetNode(PPC::SUBFC, MVT::i32, MVT::Flag,
1187                                            RHSL, LHSL));
1188     Result.push_back(CurDAG->getTargetNode(PPC::SUBFE, MVT::i32, RHSH, LHSH,
1189                                            Result[0].getValue(1)));
1190     CurDAG->ReplaceAllUsesWith(N, Result);
1191     return Result[Op.ResNo];
1192   }
1193   case ISD::SHL_PARTS: {
1194     SDOperand HI = Select(N->getOperand(0));
1195     SDOperand LO = Select(N->getOperand(1));
1196     SDOperand SH = Select(N->getOperand(2));
1197     SDOperand SH_LO_R = CurDAG->getTargetNode(PPC::SUBFIC, MVT::i32, MVT::Flag,
1198                                               SH, getI32Imm(32));
1199     SDOperand SH_LO_L = CurDAG->getTargetNode(PPC::ADDI, MVT::i32, SH,
1200                                           getI32Imm((unsigned)-32));
1201     SDOperand HI_SHL = CurDAG->getTargetNode(PPC::SLW, MVT::i32, HI, SH);
1202     SDOperand HI_LOR = CurDAG->getTargetNode(PPC::SRW, MVT::i32, LO, SH_LO_R);
1203     SDOperand HI_LOL = CurDAG->getTargetNode(PPC::SLW, MVT::i32, LO, SH_LO_L);
1204     SDOperand HI_OR =  CurDAG->getTargetNode(PPC::OR, MVT::i32, HI_SHL, HI_LOR);
1205
1206     std::vector<SDOperand> Result;
1207     Result.push_back(CurDAG->getTargetNode(PPC::SLW, MVT::i32, LO, SH));
1208     Result.push_back(CurDAG->getTargetNode(PPC::OR, MVT::i32, HI_OR, HI_LOL));
1209     CurDAG->ReplaceAllUsesWith(N, Result);
1210     return Result[Op.ResNo];
1211   }
1212   case ISD::SRL_PARTS: {
1213     SDOperand HI = Select(N->getOperand(0));
1214     SDOperand LO = Select(N->getOperand(1));
1215     SDOperand SH = Select(N->getOperand(2));
1216     SDOperand SH_HI_L = CurDAG->getTargetNode(PPC::SUBFIC, MVT::i32, MVT::Flag,
1217                                               SH, getI32Imm(32));
1218     SDOperand SH_HI_R = CurDAG->getTargetNode(PPC::ADDI, MVT::i32, SH,
1219                                               getI32Imm((unsigned)-32));
1220     SDOperand LO_SHR = CurDAG->getTargetNode(PPC::SRW, MVT::i32, LO, SH);
1221     SDOperand LO_HIL = CurDAG->getTargetNode(PPC::SLW, MVT::i32, HI, SH_HI_L);
1222     SDOperand LO_HIR = CurDAG->getTargetNode(PPC::SRW, MVT::i32, HI, SH_HI_R);
1223     SDOperand LO_OR =  CurDAG->getTargetNode(PPC::OR, MVT::i32, LO_SHR, LO_HIL);
1224
1225     std::vector<SDOperand> Result;
1226     Result.push_back(CurDAG->getTargetNode(PPC::OR, MVT::i32, LO_OR, LO_HIR));
1227     Result.push_back(CurDAG->getTargetNode(PPC::SRW, MVT::i32, HI, SH));
1228     CurDAG->ReplaceAllUsesWith(N, Result);
1229     return Result[Op.ResNo];
1230   }
1231
1232   case ISD::LOAD:
1233   case ISD::EXTLOAD:
1234   case ISD::ZEXTLOAD:
1235   case ISD::SEXTLOAD: {
1236     SDOperand Op1, Op2;
1237     bool isIdx = SelectAddr(N->getOperand(1), Op1, Op2);
1238
1239     MVT::ValueType TypeBeingLoaded = (N->getOpcode() == ISD::LOAD) ?
1240       N->getValueType(0) : cast<VTSDNode>(N->getOperand(3))->getVT();
1241     unsigned Opc;
1242     switch (TypeBeingLoaded) {
1243     default: N->dump(); assert(0 && "Cannot load this type!");
1244     case MVT::i1:
1245     case MVT::i8:  Opc = isIdx ? PPC::LBZX : PPC::LBZ; break;
1246     case MVT::i16:
1247       if (N->getOpcode() == ISD::SEXTLOAD) { // SEXT load?
1248         Opc = isIdx ? PPC::LHAX : PPC::LHA;
1249       } else {
1250         Opc = isIdx ? PPC::LHZX : PPC::LHZ;
1251       }
1252       break;
1253     case MVT::i32: Opc = isIdx ? PPC::LWZX : PPC::LWZ; break;
1254     case MVT::f32: Opc = isIdx ? PPC::LFSX : PPC::LFS; break;
1255     case MVT::f64: Opc = isIdx ? PPC::LFDX : PPC::LFD; break;
1256     }
1257
1258     CurDAG->SelectNodeTo(N, Opc, N->getValueType(0), MVT::Other,
1259                          Op1, Op2, Select(N->getOperand(0)));
1260     break;
1261   }
1262
1263   case ISD::TRUNCSTORE:
1264   case ISD::STORE: {
1265     SDOperand AddrOp1, AddrOp2;
1266     bool isIdx = SelectAddr(N->getOperand(2), AddrOp1, AddrOp2);
1267
1268     unsigned Opc;
1269     if (N->getOpcode() == ISD::STORE) {
1270       switch (N->getOperand(1).getValueType()) {
1271       default: assert(0 && "unknown Type in store");
1272       case MVT::i32: Opc = isIdx ? PPC::STWX  : PPC::STW; break;
1273       case MVT::f64: Opc = isIdx ? PPC::STFDX : PPC::STFD; break;
1274       case MVT::f32: Opc = isIdx ? PPC::STFSX : PPC::STFS; break;
1275       }
1276     } else { //ISD::TRUNCSTORE
1277       switch(cast<VTSDNode>(N->getOperand(4))->getVT()) {
1278       default: assert(0 && "unknown Type in store");
1279       case MVT::i1:
1280       case MVT::i8:  Opc = isIdx ? PPC::STBX : PPC::STB; break;
1281       case MVT::i16: Opc = isIdx ? PPC::STHX : PPC::STH; break;
1282       }
1283     }
1284
1285     CurDAG->SelectNodeTo(N, Opc, MVT::Other, Select(N->getOperand(1)),
1286                          AddrOp1, AddrOp2, Select(N->getOperand(0)));
1287     break;
1288   }
1289
1290   case ISD::SETCC: {
1291     unsigned Imm;
1292     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(2))->get();
1293     if (isIntImmediate(N->getOperand(1), Imm)) {
1294       // We can codegen setcc op, imm very efficiently compared to a brcond.
1295       // Check for those cases here.
1296       // setcc op, 0
1297       if (Imm == 0) {
1298         SDOperand Op = Select(N->getOperand(0));
1299         switch (CC) {
1300         default: assert(0 && "Unhandled SetCC condition"); abort();
1301         case ISD::SETEQ:
1302           Op = CurDAG->getTargetNode(PPC::CNTLZW, MVT::i32, Op);
1303           CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Op, getI32Imm(27),
1304                                getI32Imm(5), getI32Imm(31));
1305           break;
1306         case ISD::SETNE: {
1307           SDOperand AD = CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
1308                                                Op, getI32Imm(~0U));
1309           CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, AD, Op, AD.getValue(1));
1310           break;
1311         }
1312         case ISD::SETLT:
1313           CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Op, getI32Imm(1),
1314                                getI32Imm(31), getI32Imm(31));
1315           break;
1316         case ISD::SETGT: {
1317           SDOperand T = CurDAG->getTargetNode(PPC::NEG, MVT::i32, Op);
1318           T = CurDAG->getTargetNode(PPC::ANDC, MVT::i32, T, Op);;
1319           CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, T, getI32Imm(1),
1320                                getI32Imm(31), getI32Imm(31));
1321           break;
1322         }
1323         }
1324         break;
1325       } else if (Imm == ~0U) {        // setcc op, -1
1326         SDOperand Op = Select(N->getOperand(0));
1327         switch (CC) {
1328         default: assert(0 && "Unhandled SetCC condition"); abort();
1329         case ISD::SETEQ:
1330           Op = CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
1331                                      Op, getI32Imm(1));
1332           CurDAG->SelectNodeTo(N, PPC::ADDZE, MVT::i32,
1333                                CurDAG->getTargetNode(PPC::LI, MVT::i32,
1334                                                      getI32Imm(0)),
1335                                Op.getValue(1));
1336           break;
1337         case ISD::SETNE: {
1338           Op = CurDAG->getTargetNode(PPC::NOR, MVT::i32, Op, Op);
1339           SDOperand AD = CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, Op,
1340                                                getI32Imm(~0U));
1341           CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, AD, Op, AD.getValue(1));
1342           break;
1343         }
1344         case ISD::SETLT: {
1345           SDOperand AD = CurDAG->getTargetNode(PPC::ADDI, MVT::i32, Op,
1346                                                getI32Imm(1));
1347           SDOperand AN = CurDAG->getTargetNode(PPC::AND, MVT::i32, AD, Op);
1348           CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, AN, getI32Imm(1),
1349                                getI32Imm(31), getI32Imm(31));
1350           break;
1351         }
1352         case ISD::SETGT:
1353           Op = CurDAG->getTargetNode(PPC::RLWINM, MVT::i32, Op, getI32Imm(1),
1354                                      getI32Imm(31), getI32Imm(31));
1355           CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Op, getI32Imm(1));
1356           break;
1357         }
1358         break;
1359       }
1360     }
1361
1362     bool Inv;
1363     unsigned Idx = getCRIdxForSetCC(CC, Inv);
1364     SDOperand CCReg =
1365       SelectCC(Select(N->getOperand(0)), Select(N->getOperand(1)), CC);
1366     SDOperand IntCR;
1367
1368     // Force the ccreg into CR7.
1369     SDOperand CR7Reg = CurDAG->getRegister(PPC::CR7, MVT::i32);
1370
1371     std::vector<MVT::ValueType> VTs;
1372     VTs.push_back(MVT::Other);
1373     VTs.push_back(MVT::Flag);    // NONSTANDARD CopyToReg node: defines a flag
1374     std::vector<SDOperand> Ops;
1375     Ops.push_back(CurDAG->getEntryNode());
1376     Ops.push_back(CR7Reg);
1377     Ops.push_back(CCReg);
1378     CCReg = CurDAG->getNode(ISD::CopyToReg, VTs, Ops).getValue(1);
1379
1380     if (TLI.getTargetMachine().getSubtarget<PPCSubtarget>().isGigaProcessor())
1381       IntCR = CurDAG->getTargetNode(PPC::MFOCRF, MVT::i32, CR7Reg, CCReg);
1382     else
1383       IntCR = CurDAG->getTargetNode(PPC::MFCR, MVT::i32, CCReg);
1384
1385     if (!Inv) {
1386       CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, IntCR,
1387                            getI32Imm(32-(3-Idx)), getI32Imm(31), getI32Imm(31));
1388     } else {
1389       SDOperand Tmp =
1390       CurDAG->getTargetNode(PPC::RLWINM, MVT::i32, IntCR,
1391                             getI32Imm(32-(3-Idx)), getI32Imm(31),getI32Imm(31));
1392       CurDAG->SelectNodeTo(N, PPC::XORI, MVT::i32, Tmp, getI32Imm(1));
1393     }
1394
1395     break;
1396   }
1397
1398   case ISD::SELECT_CC: {
1399     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(4))->get();
1400
1401     // handle the setcc cases here.  select_cc lhs, 0, 1, 0, cc
1402     if (ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N->getOperand(1)))
1403       if (ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N->getOperand(2)))
1404         if (ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N->getOperand(3)))
1405           if (N1C->isNullValue() && N3C->isNullValue() &&
1406               N2C->getValue() == 1ULL && CC == ISD::SETNE) {
1407             SDOperand LHS = Select(N->getOperand(0));
1408             SDOperand Tmp =
1409               CurDAG->getTargetNode(PPC::ADDIC, MVT::i32, MVT::Flag,
1410                                     LHS, getI32Imm(~0U));
1411             CurDAG->SelectNodeTo(N, PPC::SUBFE, MVT::i32, Tmp, LHS,
1412                                  Tmp.getValue(1));
1413             break;
1414           }
1415
1416     SDOperand CCReg = SelectCC(Select(N->getOperand(0)),
1417                                Select(N->getOperand(1)), CC);
1418     unsigned BROpc = getBCCForSetCC(CC);
1419
1420     bool isFP = MVT::isFloatingPoint(N->getValueType(0));
1421     unsigned SelectCCOp = isFP ? PPC::SELECT_CC_FP : PPC::SELECT_CC_Int;
1422     CurDAG->SelectNodeTo(N, SelectCCOp, N->getValueType(0), CCReg,
1423                          Select(N->getOperand(2)), Select(N->getOperand(3)),
1424                          getI32Imm(BROpc));
1425     break;
1426   }
1427
1428   case ISD::CALLSEQ_START:
1429   case ISD::CALLSEQ_END: {
1430     unsigned Amt = cast<ConstantSDNode>(N->getOperand(1))->getValue();
1431     unsigned Opc = N->getOpcode() == ISD::CALLSEQ_START ?
1432                        PPC::ADJCALLSTACKDOWN : PPC::ADJCALLSTACKUP;
1433     CurDAG->SelectNodeTo(N, Opc, MVT::Other,
1434                          getI32Imm(Amt), Select(N->getOperand(0)));
1435     break;
1436   }
1437   case ISD::CALL:
1438   case ISD::TAILCALL: {
1439     SDOperand Chain = Select(N->getOperand(0));
1440
1441     unsigned CallOpcode;
1442     std::vector<SDOperand> CallOperands;
1443
1444     if (GlobalAddressSDNode *GASD =
1445         dyn_cast<GlobalAddressSDNode>(N->getOperand(1))) {
1446       CallOpcode = PPC::CALLpcrel;
1447       CallOperands.push_back(CurDAG->getTargetGlobalAddress(GASD->getGlobal(),
1448                                                             MVT::i32));
1449     } else if (ExternalSymbolSDNode *ESSDN =
1450                dyn_cast<ExternalSymbolSDNode>(N->getOperand(1))) {
1451       CallOpcode = PPC::CALLpcrel;
1452       CallOperands.push_back(N->getOperand(1));
1453     } else {
1454       // Copy the callee address into the CTR register.
1455       SDOperand Callee = Select(N->getOperand(1));
1456       Chain = CurDAG->getTargetNode(PPC::MTCTR, MVT::Other, Callee, Chain);
1457
1458       // Copy the callee address into R12 on darwin.
1459       SDOperand R12 = CurDAG->getRegister(PPC::R12, MVT::i32);
1460       Chain = CurDAG->getNode(ISD::CopyToReg, MVT::Other, Chain, R12, Callee);
1461
1462       CallOperands.push_back(getI32Imm(20));  // Information to encode indcall
1463       CallOperands.push_back(getI32Imm(0));   // Information to encode indcall
1464       CallOperands.push_back(R12);
1465       CallOpcode = PPC::CALLindirect;
1466     }
1467
1468     unsigned GPR_idx = 0, FPR_idx = 0;
1469     static const unsigned GPR[] = {
1470       PPC::R3, PPC::R4, PPC::R5, PPC::R6,
1471       PPC::R7, PPC::R8, PPC::R9, PPC::R10,
1472     };
1473     static const unsigned FPR[] = {
1474       PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
1475       PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
1476     };
1477
1478     for (unsigned i = 2, e = N->getNumOperands(); i != e; ++i)
1479       if (N->getOperand(i).getOpcode() != ISD::UNDEF) {
1480         unsigned DestReg = 0;
1481         MVT::ValueType RegTy;
1482         if (N->getOperand(i).getValueType() == MVT::i32) {
1483           assert(GPR_idx < 8 && "Too many int args");
1484           DestReg = GPR[GPR_idx++];
1485           RegTy = MVT::i32;
1486         } else {
1487           assert(MVT::isFloatingPoint(N->getOperand(i).getValueType()) &&
1488                  "Unpromoted integer arg?");
1489           assert(FPR_idx < 13 && "Too many fp args");
1490           DestReg = FPR[FPR_idx++];
1491           RegTy = MVT::f64;   // Even if this is really f32!
1492         }
1493
1494         SDOperand Reg = CurDAG->getRegister(DestReg, RegTy);
1495         Chain = CurDAG->getNode(ISD::CopyToReg, MVT::Other, Chain, Reg,
1496                                 Select(N->getOperand(i)));
1497         CallOperands.push_back(Reg);
1498       }
1499
1500     // Finally, once everything is in registers to pass to the call, emit the
1501     // call itself.
1502     CallOperands.push_back(Chain);
1503     Chain = CurDAG->getTargetNode(CallOpcode, MVT::Other, CallOperands);
1504
1505     std::vector<SDOperand> CallResults;
1506
1507     // If the call has results, copy the values out of the ret val registers.
1508     switch (N->getValueType(0)) {
1509     default: assert(0 && "Unexpected ret value!");
1510     case MVT::Other: break;
1511     case MVT::i32:
1512       if (N->getValueType(1) == MVT::i32) {
1513         Chain = CurDAG->getCopyFromReg(Chain, PPC::R4, MVT::i32).getValue(1);
1514         CallResults.push_back(Chain.getValue(0));
1515         Chain = CurDAG->getCopyFromReg(Chain, PPC::R3, MVT::i32).getValue(1);
1516         CallResults.push_back(Chain.getValue(0));
1517       } else {
1518         Chain = CurDAG->getCopyFromReg(Chain, PPC::R3, MVT::i32).getValue(1);
1519         CallResults.push_back(Chain.getValue(0));
1520       }
1521       break;
1522     case MVT::f32:
1523     case MVT::f64:
1524       Chain = CurDAG->getCopyFromReg(Chain, PPC::F1, MVT::f64).getValue(1);
1525       CallResults.push_back(Chain.getValue(0));
1526       break;
1527     }
1528
1529     CallResults.push_back(Chain);
1530     CurDAG->ReplaceAllUsesWith(N, CallResults);
1531     return CallResults[Op.ResNo];
1532   }
1533   case ISD::RET: {
1534     SDOperand Chain = Select(N->getOperand(0));     // Token chain.
1535
1536     if (N->getNumOperands() > 1) {
1537       SDOperand Val = Select(N->getOperand(1));
1538       switch (N->getOperand(1).getValueType()) {
1539       default: assert(0 && "Unknown return type!");
1540       case MVT::f64:
1541       case MVT::f32:
1542         Chain = CurDAG->getCopyToReg(Chain, PPC::F1, Val);
1543         break;
1544       case MVT::i32:
1545         Chain = CurDAG->getCopyToReg(Chain, PPC::R3, Val);
1546         break;
1547       }
1548
1549       if (N->getNumOperands() > 2) {
1550         assert(N->getOperand(1).getValueType() == MVT::i32 &&
1551                N->getOperand(2).getValueType() == MVT::i32 &&
1552                N->getNumOperands() == 3 && "Unknown two-register ret value!");
1553         Val = Select(N->getOperand(2));
1554         Chain = CurDAG->getCopyToReg(Chain, PPC::R4, Val);
1555       }
1556     }
1557
1558     // Finally, select this to a blr (return) instruction.
1559     CurDAG->SelectNodeTo(N, PPC::BLR, MVT::Other, Chain);
1560     break;
1561   }
1562   case ISD::BR:
1563     CurDAG->SelectNodeTo(N, PPC::B, MVT::Other, N->getOperand(1),
1564                          Select(N->getOperand(0)));
1565     break;
1566   case ISD::BR_CC:
1567   case ISD::BRTWOWAY_CC: {
1568     SDOperand Chain = Select(N->getOperand(0));
1569     MachineBasicBlock *Dest =
1570       cast<BasicBlockSDNode>(N->getOperand(4))->getBasicBlock();
1571     ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(1))->get();
1572     SDOperand CondCode = SelectCC(N->getOperand(2), N->getOperand(3), CC);
1573     unsigned Opc = getBCCForSetCC(CC);
1574
1575     // If this is a two way branch, then grab the fallthrough basic block
1576     // argument and build a PowerPC branch pseudo-op, suitable for long branch
1577     // conversion if necessary by the branch selection pass.  Otherwise, emit a
1578     // standard conditional branch.
1579     if (N->getOpcode() == ISD::BRTWOWAY_CC) {
1580       MachineBasicBlock *Fallthrough =
1581         cast<BasicBlockSDNode>(N->getOperand(5))->getBasicBlock();
1582       SDOperand CB = CurDAG->getTargetNode(PPC::COND_BRANCH, MVT::Other,
1583                                            CondCode, getI32Imm(Opc),
1584                                            N->getOperand(4), N->getOperand(5),
1585                                            Chain);
1586       CurDAG->SelectNodeTo(N, PPC::B, MVT::Other, N->getOperand(5), CB);
1587     } else {
1588       // Iterate to the next basic block
1589       ilist<MachineBasicBlock>::iterator It = BB;
1590       ++It;
1591
1592       // If the fallthrough path is off the end of the function, which would be
1593       // undefined behavior, set it to be the same as the current block because
1594       // we have nothing better to set it to, and leaving it alone will cause
1595       // the PowerPC Branch Selection pass to crash.
1596       if (It == BB->getParent()->end()) It = Dest;
1597       CurDAG->SelectNodeTo(N, PPC::COND_BRANCH, MVT::Other, CondCode,
1598                            getI32Imm(Opc), N->getOperand(4),
1599                            CurDAG->getBasicBlock(It), Chain);
1600     }
1601     break;
1602   }
1603   }
1604   return SDOperand(N, Op.ResNo);
1605 }
1606
1607
1608 /// createPPC32ISelDag - This pass converts a legalized DAG into a
1609 /// PowerPC-specific DAG, ready for instruction scheduling.
1610 ///
1611 FunctionPass *llvm::createPPC32ISelDag(TargetMachine &TM) {
1612   return new PPC32DAGToDAGISel(TM);
1613 }
1614