lib/Target/PowerPC/PPCISelPattern.cpp

   1 //===-- PPC32ISelPattern.cpp - A pattern matching inst selector for PPC32 -===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Nate Begeman 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 // Magic number generation for integer divide from the PowerPC Compiler Writer's
  12 // Guide, section 3.2.3.5
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "PowerPC.h"
  17 #include "PowerPCInstrBuilder.h"
  18 #include "PowerPCInstrInfo.h"
  19 #include "PPC32TargetMachine.h"
  20 #include "PPC32ISelLowering.h"
  21 #include "llvm/Constants.h"
  22 #include "llvm/Function.h"
  23 #include "llvm/CodeGen/MachineConstantPool.h"
  24 #include "llvm/CodeGen/MachineFunction.h"
  25 #include "llvm/CodeGen/MachineFrameInfo.h"
  26 #include "llvm/CodeGen/SelectionDAG.h"
  27 #include "llvm/CodeGen/SelectionDAGISel.h"
  28 #include "llvm/CodeGen/SSARegMap.h"
  29 #include "llvm/Target/TargetData.h"
  30 #include "llvm/Target/TargetOptions.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/MathExtras.h"
  33 #include "llvm/ADT/Statistic.h"
  34 #include <set>
  35 #include <algorithm>
  36 using namespace llvm;
  37
  38 namespace {
  39 Statistic<> Recorded("ppc-codegen", "Number of recording ops emitted");
  40 Statistic<> FusedFP ("ppc-codegen", "Number of fused fp operations");
  41 Statistic<> FrameOff("ppc-codegen", "Number of frame idx offsets collapsed");
  42
  43 //===--------------------------------------------------------------------===//
  44 // ISel - PPC32 specific code to select PPC32 machine instructions for
  45 // SelectionDAG operations.
  46 //===--------------------------------------------------------------------===//
  47
  48 class ISel : public SelectionDAGISel {
  49   PPC32TargetLowering PPC32Lowering;
  50   SelectionDAG *ISelDAG;  // Hack to support us having a dag->dag transform
  51                           // for sdiv and udiv until it is put into the future
  52                           // dag combiner.
  53
  54   /// ExprMap - As shared expressions are codegen'd, we keep track of which
  55   /// vreg the value is produced in, so we only emit one copy of each compiled
  56   /// tree.
  57   std::map<SDOperand, unsigned> ExprMap;
  58
  59   unsigned GlobalBaseReg;
  60   bool GlobalBaseInitialized;
  61   bool RecordSuccess;
  62 public:
  63   ISel(TargetMachine &TM) : SelectionDAGISel(PPC32Lowering), PPC32Lowering(TM),
  64                             ISelDAG(0) {}
  65
  66   /// runOnFunction - Override this function in order to reset our per-function
  67   /// variables.
  68   virtual bool runOnFunction(Function &Fn) {
  69     // Make sure we re-emit a set of the global base reg if necessary
  70     GlobalBaseInitialized = false;
  71     return SelectionDAGISel::runOnFunction(Fn);
  72   }
  73
  74   /// InstructionSelectBasicBlock - This callback is invoked by
  75   /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
  76   virtual void InstructionSelectBasicBlock(SelectionDAG &DAG) {
  77     DEBUG(BB->dump());
  78     // Codegen the basic block.
  79     ISelDAG = &DAG;
  80     Select(DAG.getRoot());
  81
  82     // Clear state used for selection.
  83     ExprMap.clear();
  84     ISelDAG = 0;
  85   }
  86
  87   // convenience functions for virtual register creation
  88   inline unsigned MakeIntReg() {
  89     return RegMap->createVirtualRegister(PPC32::GPRCRegisterClass);
  90   }
  91   inline unsigned MakeFPReg() {
  92     return RegMap->createVirtualRegister(PPC32::FPRCRegisterClass);
  93   }
  94
  95   // dag -> dag expanders for integer divide by constant
  96   SDOperand BuildSDIVSequence(SDOperand N);
  97   SDOperand BuildUDIVSequence(SDOperand N);
  98
  99   unsigned getGlobalBaseReg();
 100   unsigned getConstDouble(double floatVal, unsigned Result);
 101   void MoveCRtoGPR(unsigned CCReg, ISD::CondCode CC, unsigned Result);
 102   bool SelectBitfieldInsert(SDOperand OR, unsigned Result);
 103   unsigned FoldIfWideZeroExtend(SDOperand N);
 104   unsigned SelectCC(SDOperand LHS, SDOperand RHS, ISD::CondCode CC);
 105   bool SelectIntImmediateExpr(SDOperand N, unsigned Result,
 106                               unsigned OCHi, unsigned OCLo,
 107                               bool IsArithmetic = false, bool Negate = false);
 108   unsigned SelectExpr(SDOperand N, bool Recording=false);
 109   void Select(SDOperand N);
 110
 111   unsigned SelectAddr(SDOperand N, unsigned& Reg, int& offset);
 112   void SelectBranchCC(SDOperand N);
 113
 114   virtual const char *getPassName() const {
 115     return "PowerPC Pattern Instruction Selection";
 116   }
 117 };
 118
 119 // isRunOfOnes - Returns true iff Val consists of one contiguous run of 1s with
 120 // any number of 0s on either side.  The 1s are allowed to wrap from LSB to
 121 // MSB, so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs.  0x0F0F0000 is
 122 // not, since all 1s are not contiguous.
 123 static bool isRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
 124   if (isShiftedMask_32(Val)) {
 125     // look for the first non-zero bit
 126     MB = CountLeadingZeros_32(Val);
 127     // look for the first zero bit after the run of ones
 128     ME = CountLeadingZeros_32((Val - 1) ^ Val);
 129     return true;
 130   } else if (isShiftedMask_32(Val = ~Val)) { // invert mask
 131     // effectively look for the first zero bit
 132     ME = CountLeadingZeros_32(Val) - 1;
 133     // effectively look for the first one bit after the run of zeros
 134     MB = CountLeadingZeros_32((Val - 1) ^ Val) + 1;
 135     return true;
 136   }
 137   // no run present
 138   return false;
 139 }
 140
 141 // isRotateAndMask - Returns true if Mask and Shift can be folded in to a rotate
 142 // and mask opcode and mask operation.
 143 static bool isRotateAndMask(unsigned Opcode, unsigned Shift, unsigned Mask,
 144                             bool IsShiftMask,
 145                             unsigned &SH, unsigned &MB, unsigned &ME) {
 146   if (Shift > 31) return false;
 147   unsigned Indeterminant = ~0;       // bit mask marking indeterminant results
 148
 149   if (Opcode == ISD::SHL) { // shift left
 150     // apply shift to mask if it comes first
 151     if (IsShiftMask) Mask = Mask << Shift;
 152     // determine which bits are made indeterminant by shift
 153     Indeterminant = ~(0xFFFFFFFFu << Shift);
 154   } else if (Opcode == ISD::SRA || Opcode == ISD::SRL) { // shift rights
 155     // apply shift to mask if it comes first
 156     if (IsShiftMask) Mask = Mask >> Shift;
 157     // determine which bits are made indeterminant by shift
 158     Indeterminant = ~(0xFFFFFFFFu >> Shift);
 159     // adjust for the left rotate
 160     Shift = 32 - Shift;
 161   }
 162
 163   // if the mask doesn't intersect any Indeterminant bits
 164   if (Mask && !(Mask & Indeterminant)) {
 165     SH = Shift;
 166     // make sure the mask is still a mask (wrap arounds may not be)
 167     return isRunOfOnes(Mask, MB, ME);
 168   }
 169
 170   // can't do it
 171   return false;
 172 }
 173
 174 // isIntImmediate - This method tests to see if a constant operand.
 175 // If so Imm will receive the 32 bit value.
 176 static bool isIntImmediate(SDOperand N, unsigned& Imm) {
 177   // test for constant
 178   if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N)) {
 179     // retrieve value
 180     Imm = (unsigned)CN->getValue();
 181     // passes muster
 182     return true;
 183   }
 184   // not a constant
 185   return false;
 186 }
 187
 188 // isOpcWithIntImmediate - This method tests to see if the node is a specific
 189 // opcode and that it has a immediate integer right operand.
 190 // If so Imm will receive the 32 bit value.
 191 static bool isOpcWithIntImmediate(SDOperand N, unsigned Opc, unsigned& Imm) {
 192   return N.getOpcode() == Opc && isIntImmediate(N.getOperand(1), Imm);
 193 }
 194
 195 // isOprShiftImm - Returns true if the specified operand is a shift opcode with
 196 // a immediate shift count less than 32.
 197 static bool isOprShiftImm(SDOperand N, unsigned& Opc, unsigned& SH) {
 198   Opc = N.getOpcode();
 199   return (Opc == ISD::SHL || Opc == ISD::SRL || Opc == ISD::SRA) &&
 200          isIntImmediate(N.getOperand(1), SH) && SH < 32;
 201 }
 202
 203 // isOprNot - Returns true if the specified operand is an xor with immediate -1.
 204 static bool isOprNot(SDOperand N) {
 205   unsigned Imm;
 206   return isOpcWithIntImmediate(N, ISD::XOR, Imm) && (signed)Imm == -1;
 207 }
 208
 209 // Immediate constant composers.
 210 // Lo16 - grabs the lo 16 bits from a 32 bit constant.
 211 // Hi16 - grabs the hi 16 bits from a 32 bit constant.
 212 // HA16 - computes the hi bits required if the lo bits are add/subtracted in
 213 // arithmethically.
 214 static unsigned Lo16(unsigned x)  { return x & 0x0000FFFF; }
 215 static unsigned Hi16(unsigned x)  { return Lo16(x >> 16); }
 216 static unsigned HA16(unsigned x)  { return Hi16((signed)x - (signed short)x); }
 217
 218 /// NodeHasRecordingVariant - If SelectExpr can always produce code for
 219 /// NodeOpcode that also sets CR0 as a side effect, return true.  Otherwise,
 220 /// return false.
 221 static bool NodeHasRecordingVariant(unsigned NodeOpcode) {
 222   switch(NodeOpcode) {
 223   default: return false;
 224   case ISD::AND:
 225   case ISD::OR:
 226     return true;
 227   }
 228 }
 229
 230 /// getBCCForSetCC - Returns the PowerPC condition branch mnemonic corresponding
 231 /// to Condition.
 232 static unsigned getBCCForSetCC(ISD::CondCode CC) {
 233   switch (CC) {
 234   default: assert(0 && "Unknown condition!"); abort();
 235   case ISD::SETEQ:  return PPC::BEQ;
 236   case ISD::SETNE:  return PPC::BNE;
 237   case ISD::SETULT:
 238   case ISD::SETLT:  return PPC::BLT;
 239   case ISD::SETULE:
 240   case ISD::SETLE:  return PPC::BLE;
 241   case ISD::SETUGT:
 242   case ISD::SETGT:  return PPC::BGT;
 243   case ISD::SETUGE:
 244   case ISD::SETGE:  return PPC::BGE;
 245   }
 246   return 0;
 247 }
 248
 249 /// getCRIdxForSetCC - Return the index of the condition register field
 250 /// associated with the SetCC condition, and whether or not the field is
 251 /// treated as inverted.  That is, lt = 0; ge = 0 inverted.
 252 static unsigned getCRIdxForSetCC(ISD::CondCode CC, bool& Inv) {
 253   switch (CC) {
 254   default: assert(0 && "Unknown condition!"); abort();
 255   case ISD::SETULT:
 256   case ISD::SETLT:  Inv = false;  return 0;
 257   case ISD::SETUGE:
 258   case ISD::SETGE:  Inv = true;   return 0;
 259   case ISD::SETUGT:
 260   case ISD::SETGT:  Inv = false;  return 1;
 261   case ISD::SETULE:
 262   case ISD::SETLE:  Inv = true;   return 1;
 263   case ISD::SETEQ:  Inv = false;  return 2;
 264   case ISD::SETNE:  Inv = true;   return 2;
 265   }
 266   return 0;
 267 }
 268
 269 /// IndexedOpForOp - Return the indexed variant for each of the PowerPC load
 270 /// and store immediate instructions.
 271 static unsigned IndexedOpForOp(unsigned Opcode) {
 272   switch(Opcode) {
 273   default: assert(0 && "Unknown opcode!"); abort();
 274   case PPC::LBZ: return PPC::LBZX;  case PPC::STB: return PPC::STBX;
 275   case PPC::LHZ: return PPC::LHZX;  case PPC::STH: return PPC::STHX;
 276   case PPC::LHA: return PPC::LHAX;  case PPC::STW: return PPC::STWX;
 277   case PPC::LWZ: return PPC::LWZX;  case PPC::STFS: return PPC::STFSX;
 278   case PPC::LFS: return PPC::LFSX;  case PPC::STFD: return PPC::STFDX;
 279   case PPC::LFD: return PPC::LFDX;
 280   }
 281   return 0;
 282 }
 283
 284 // Structure used to return the necessary information to codegen an SDIV as
 285 // a multiply.
 286 struct ms {
 287   int m; // magic number
 288   int s; // shift amount
 289 };
 290
 291 struct mu {
 292   unsigned int m; // magic number
 293   int a;          // add indicator
 294   int s;          // shift amount
 295 };
 296
 297 /// magic - calculate the magic numbers required to codegen an integer sdiv as
 298 /// a sequence of multiply and shifts.  Requires that the divisor not be 0, 1,
 299 /// or -1.
 300 static struct ms magic(int d) {
 301   int p;
 302   unsigned int ad, anc, delta, q1, r1, q2, r2, t;
 303   const unsigned int two31 = 0x80000000U;
 304   struct ms mag;
 305
 306   ad = abs(d);
 307   t = two31 + ((unsigned int)d >> 31);
 308   anc = t - 1 - t%ad;   // absolute value of nc
 309   p = 31;               // initialize p
 310   q1 = two31/anc;       // initialize q1 = 2p/abs(nc)
 311   r1 = two31 - q1*anc;  // initialize r1 = rem(2p,abs(nc))
 312   q2 = two31/ad;        // initialize q2 = 2p/abs(d)
 313   r2 = two31 - q2*ad;   // initialize r2 = rem(2p,abs(d))
 314   do {
 315     p = p + 1;
 316     q1 = 2*q1;        // update q1 = 2p/abs(nc)
 317     r1 = 2*r1;        // update r1 = rem(2p/abs(nc))
 318     if (r1 >= anc) {  // must be unsigned comparison
 319       q1 = q1 + 1;
 320       r1 = r1 - anc;
 321     }
 322     q2 = 2*q2;        // update q2 = 2p/abs(d)
 323     r2 = 2*r2;        // update r2 = rem(2p/abs(d))
 324     if (r2 >= ad) {   // must be unsigned comparison
 325       q2 = q2 + 1;
 326       r2 = r2 - ad;
 327     }
 328     delta = ad - r2;
 329   } while (q1 < delta || (q1 == delta && r1 == 0));
 330
 331   mag.m = q2 + 1;
 332   if (d < 0) mag.m = -mag.m; // resulting magic number
 333   mag.s = p - 32;            // resulting shift
 334   return mag;
 335 }
 336
 337 /// magicu - calculate the magic numbers required to codegen an integer udiv as
 338 /// a sequence of multiply, add and shifts.  Requires that the divisor not be 0.
 339 static struct mu magicu(unsigned d)
 340 {
 341   int p;
 342   unsigned int nc, delta, q1, r1, q2, r2;
 343   struct mu magu;
 344   magu.a = 0;               // initialize "add" indicator
 345   nc = - 1 - (-d)%d;
 346   p = 31;                   // initialize p
 347   q1 = 0x80000000/nc;       // initialize q1 = 2p/nc
 348   r1 = 0x80000000 - q1*nc;  // initialize r1 = rem(2p,nc)
 349   q2 = 0x7FFFFFFF/d;        // initialize q2 = (2p-1)/d
 350   r2 = 0x7FFFFFFF - q2*d;   // initialize r2 = rem((2p-1),d)
 351   do {
 352     p = p + 1;
 353     if (r1 >= nc - r1 ) {
 354       q1 = 2*q1 + 1;  // update q1
 355       r1 = 2*r1 - nc; // update r1
 356     }
 357     else {
 358       q1 = 2*q1; // update q1
 359       r1 = 2*r1; // update r1
 360     }
 361     if (r2 + 1 >= d - r2) {
 362       if (q2 >= 0x7FFFFFFF) magu.a = 1;
 363       q2 = 2*q2 + 1;     // update q2
 364       r2 = 2*r2 + 1 - d; // update r2
 365     }
 366     else {
 367       if (q2 >= 0x80000000) magu.a = 1;
 368       q2 = 2*q2;     // update q2
 369       r2 = 2*r2 + 1; // update r2
 370     }
 371     delta = d - 1 - r2;
 372   } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
 373   magu.m = q2 + 1; // resulting magic number
 374   magu.s = p - 32;  // resulting shift
 375   return magu;
 376 }
 377 }
 378
 379 /// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant,
 380 /// return a DAG expression to select that will generate the same value by
 381 /// multiplying by a magic number.  See:
 382 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
 383 SDOperand ISel::BuildSDIVSequence(SDOperand N) {
 384   int d = (int)cast<ConstantSDNode>(N.getOperand(1))->getSignExtended();
 385   ms magics = magic(d);
 386   // Multiply the numerator (operand 0) by the magic value
 387   SDOperand Q = ISelDAG->getNode(ISD::MULHS, MVT::i32, N.getOperand(0),
 388                                  ISelDAG->getConstant(magics.m, MVT::i32));
 389   // If d > 0 and m < 0, add the numerator
 390   if (d > 0 && magics.m < 0)
 391     Q = ISelDAG->getNode(ISD::ADD, MVT::i32, Q, N.getOperand(0));
 392   // If d < 0 and m > 0, subtract the numerator.
 393   if (d < 0 && magics.m > 0)
 394     Q = ISelDAG->getNode(ISD::SUB, MVT::i32, Q, N.getOperand(0));
 395   // Shift right algebraic if shift value is nonzero
 396   if (magics.s > 0)
 397     Q = ISelDAG->getNode(ISD::SRA, MVT::i32, Q,
 398                          ISelDAG->getConstant(magics.s, MVT::i32));
 399   // Extract the sign bit and add it to the quotient
 400   SDOperand T =
 401     ISelDAG->getNode(ISD::SRL, MVT::i32, Q, ISelDAG->getConstant(31, MVT::i32));
 402   return ISelDAG->getNode(ISD::ADD, MVT::i32, Q, T);
 403 }
 404
 405 /// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant,
 406 /// return a DAG expression to select that will generate the same value by
 407 /// multiplying by a magic number.  See:
 408 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
 409 SDOperand ISel::BuildUDIVSequence(SDOperand N) {
 410   unsigned d =
 411     (unsigned)cast<ConstantSDNode>(N.getOperand(1))->getSignExtended();
 412   mu magics = magicu(d);
 413   // Multiply the numerator (operand 0) by the magic value
 414   SDOperand Q = ISelDAG->getNode(ISD::MULHU, MVT::i32, N.getOperand(0),
 415                                  ISelDAG->getConstant(magics.m, MVT::i32));
 416   if (magics.a == 0) {
 417     Q = ISelDAG->getNode(ISD::SRL, MVT::i32, Q,
 418                          ISelDAG->getConstant(magics.s, MVT::i32));
 419   } else {
 420     SDOperand NPQ = ISelDAG->getNode(ISD::SUB, MVT::i32, N.getOperand(0), Q);
 421     NPQ = ISelDAG->getNode(ISD::SRL, MVT::i32, NPQ,
 422                            ISelDAG->getConstant(1, MVT::i32));
 423     NPQ = ISelDAG->getNode(ISD::ADD, MVT::i32, NPQ, Q);
 424     Q = ISelDAG->getNode(ISD::SRL, MVT::i32, NPQ,
 425                            ISelDAG->getConstant(magics.s-1, MVT::i32));
 426   }
 427   return Q;
 428 }
 429
 430 /// getGlobalBaseReg - Output the instructions required to put the
 431 /// base address to use for accessing globals into a register.
 432 ///
 433 unsigned ISel::getGlobalBaseReg() {
 434   if (!GlobalBaseInitialized) {
 435     // Insert the set of GlobalBaseReg into the first MBB of the function
 436     MachineBasicBlock &FirstMBB = BB->getParent()->front();
 437     MachineBasicBlock::iterator MBBI = FirstMBB.begin();
 438     GlobalBaseReg = MakeIntReg();
 439     BuildMI(FirstMBB, MBBI, PPC::MovePCtoLR, 0, PPC::LR);
 440     BuildMI(FirstMBB, MBBI, PPC::MFLR, 1, GlobalBaseReg);
 441     GlobalBaseInitialized = true;
 442   }
 443   return GlobalBaseReg;
 444 }
 445
 446 /// getConstDouble - Loads a floating point value into a register, via the
 447 /// Constant Pool.  Optionally takes a register in which to load the value.
 448 unsigned ISel::getConstDouble(double doubleVal, unsigned Result=0) {
 449   unsigned Tmp1 = MakeIntReg();
 450   if (0 == Result) Result = MakeFPReg();
 451   MachineConstantPool *CP = BB->getParent()->getConstantPool();
 452   ConstantFP *CFP = ConstantFP::get(Type::DoubleTy, doubleVal);
 453   unsigned CPI = CP->getConstantPoolIndex(CFP);
 454   if (PICEnabled)
 455     BuildMI(BB, PPC::ADDIS, 2, Tmp1).addReg(getGlobalBaseReg())
 456       .addConstantPoolIndex(CPI);
 457   else
 458     BuildMI(BB, PPC::LIS, 1, Tmp1).addConstantPoolIndex(CPI);
 459   BuildMI(BB, PPC::LFD, 2, Result).addConstantPoolIndex(CPI).addReg(Tmp1);
 460   return Result;
 461 }
 462
 463 /// MoveCRtoGPR - Move CCReg[Idx] to the least significant bit of Result.  If
 464 /// Inv is true, then invert the result.
 465 void ISel::MoveCRtoGPR(unsigned CCReg, ISD::CondCode CC, unsigned Result){
 466   bool Inv;
 467   unsigned IntCR = MakeIntReg();
 468   unsigned Idx = getCRIdxForSetCC(CC, Inv);
 469   BuildMI(BB, PPC::MCRF, 1, PPC::CR7).addReg(CCReg);
 470   bool GPOpt =
 471     TLI.getTargetMachine().getSubtarget<PPCSubtarget>().isGigaProcessor();
 472   if (GPOpt)
 473     BuildMI(BB, PPC::MFOCRF, 1, IntCR).addReg(PPC::CR7);
 474   else
 475     BuildMI(BB, PPC::MFCR, 0, IntCR);
 476   if (Inv) {
 477     unsigned Tmp1 = MakeIntReg();
 478     BuildMI(BB, PPC::RLWINM, 4, Tmp1).addReg(IntCR).addImm(32-(3-Idx))
 479       .addImm(31).addImm(31);
 480     BuildMI(BB, PPC::XORI, 2, Result).addReg(Tmp1).addImm(1);
 481   } else {
 482     BuildMI(BB, PPC::RLWINM, 4, Result).addReg(IntCR).addImm(32-(3-Idx))
 483       .addImm(31).addImm(31);
 484   }
 485 }
 486
 487 /// SelectBitfieldInsert - turn an or of two masked values into
 488 /// the rotate left word immediate then mask insert (rlwimi) instruction.
 489 /// Returns true on success, false if the caller still needs to select OR.
 490 ///
 491 /// Patterns matched:
 492 /// 1. or shl, and   5. or and, and
 493 /// 2. or and, shl   6. or shl, shr
 494 /// 3. or shr, and   7. or shr, shl
 495 /// 4. or and, shr
 496 bool ISel::SelectBitfieldInsert(SDOperand OR, unsigned Result) {
 497   bool IsRotate = false;
 498   unsigned TgtMask = 0xFFFFFFFF, InsMask = 0xFFFFFFFF, Amount = 0;
 499   unsigned Value;
 500
 501   SDOperand Op0 = OR.getOperand(0);
 502   SDOperand Op1 = OR.getOperand(1);
 503
 504   unsigned Op0Opc = Op0.getOpcode();
 505   unsigned Op1Opc = Op1.getOpcode();
 506
 507   // Verify that we have the correct opcodes
 508   if (ISD::SHL != Op0Opc && ISD::SRL != Op0Opc && ISD::AND != Op0Opc)
 509     return false;
 510   if (ISD::SHL != Op1Opc && ISD::SRL != Op1Opc && ISD::AND != Op1Opc)
 511     return false;
 512
 513   // Generate Mask value for Target
 514   if (isIntImmediate(Op0.getOperand(1), Value)) {
 515     switch(Op0Opc) {
 516     case ISD::SHL: TgtMask <<= Value; break;
 517     case ISD::SRL: TgtMask >>= Value; break;
 518     case ISD::AND: TgtMask &= Value; break;
 519     }
 520   } else {
 521     return false;
 522   }
 523
 524   // Generate Mask value for Insert
 525   if (isIntImmediate(Op1.getOperand(1), Value)) {
 526     switch(Op1Opc) {
 527     case ISD::SHL:
 528       Amount = Value;
 529       InsMask <<= Amount;
 530       if (Op0Opc == ISD::SRL) IsRotate = true;
 531       break;
 532     case ISD::SRL:
 533       Amount = Value;
 534       InsMask >>= Amount;
 535       Amount = 32-Amount;
 536       if (Op0Opc == ISD::SHL) IsRotate = true;
 537       break;
 538     case ISD::AND:
 539       InsMask &= Value;
 540       break;
 541     }
 542   } else {
 543     return false;
 544   }
 545
 546   unsigned Tmp3 = 0;
 547
 548   // If both of the inputs are ANDs and one of them has a logical shift by
 549   // constant as its input, make that the inserted value so that we can combine
 550   // the shift into the rotate part of the rlwimi instruction
 551   if (Op0Opc == ISD::AND && Op1Opc == ISD::AND) {
 552     if (Op1.getOperand(0).getOpcode() == ISD::SHL ||
 553         Op1.getOperand(0).getOpcode() == ISD::SRL) {
 554       if (isIntImmediate(Op1.getOperand(0).getOperand(1), Value)) {
 555         Amount = Op1.getOperand(0).getOpcode() == ISD::SHL ?
 556           Value : 32 - Value;
 557         Tmp3 = SelectExpr(Op1.getOperand(0).getOperand(0));
 558       }
 559     } else if (Op0.getOperand(0).getOpcode() == ISD::SHL ||
 560                Op0.getOperand(0).getOpcode() == ISD::SRL) {
 561       if (isIntImmediate(Op0.getOperand(0).getOperand(1), Value)) {
 562         std::swap(Op0, Op1);
 563         std::swap(TgtMask, InsMask);
 564         Amount = Op1.getOperand(0).getOpcode() == ISD::SHL ?
 565           Value : 32 - Value;
 566         Tmp3 = SelectExpr(Op1.getOperand(0).getOperand(0));
 567       }
 568     }
 569   }
 570
 571   // Verify that the Target mask and Insert mask together form a full word mask
 572   // and that the Insert mask is a run of set bits (which implies both are runs
 573   // of set bits).  Given that, Select the arguments and generate the rlwimi
 574   // instruction.
 575   unsigned MB, ME;
 576   if (((TgtMask & InsMask) == 0) && isRunOfOnes(InsMask, MB, ME)) {
 577     unsigned Tmp1, Tmp2;
 578     bool fullMask = (TgtMask ^ InsMask) == 0xFFFFFFFF;
 579     // Check for rotlwi / rotrwi here, a special case of bitfield insert
 580     // where both bitfield halves are sourced from the same value.
 581     if (IsRotate && fullMask &&
 582         OR.getOperand(0).getOperand(0) == OR.getOperand(1).getOperand(0)) {
 583       Tmp1 = SelectExpr(OR.getOperand(0).getOperand(0));
 584       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(Amount)
 585         .addImm(0).addImm(31);
 586       return true;
 587     }
 588     if (Op0Opc == ISD::AND && fullMask)
 589       Tmp1 = SelectExpr(Op0.getOperand(0));
 590     else
 591       Tmp1 = SelectExpr(Op0);
 592     Tmp2 = Tmp3 ? Tmp3 : SelectExpr(Op1.getOperand(0));
 593     BuildMI(BB, PPC::RLWIMI, 5, Result).addReg(Tmp1).addReg(Tmp2)
 594       .addImm(Amount).addImm(MB).addImm(ME);
 595     return true;
 596   }
 597   return false;
 598 }
 599
 600 /// FoldIfWideZeroExtend - 32 bit PowerPC implicit masks shift amounts to the
 601 /// low six bits.  If the shift amount is an ISD::AND node with a mask that is
 602 /// wider than the implicit mask, then we can get rid of the AND and let the
 603 /// shift do the mask.
 604 unsigned ISel::FoldIfWideZeroExtend(SDOperand N) {
 605   unsigned C;
 606   if (isOpcWithIntImmediate(N, ISD::AND, C) && isMask_32(C) && C > 63)
 607     return SelectExpr(N.getOperand(0));
 608   else
 609     return SelectExpr(N);
 610 }
 611
 612 unsigned ISel::SelectCC(SDOperand LHS, SDOperand RHS, ISD::CondCode CC) {
 613   unsigned Result, Tmp1, Tmp2;
 614   bool AlreadySelected = false;
 615   static const unsigned CompareOpcodes[] =
 616     { PPC::FCMPU, PPC::FCMPU, PPC::CMPW, PPC::CMPLW };
 617
 618   // Allocate a condition register for this expression
 619   Result = RegMap->createVirtualRegister(PPC32::CRRCRegisterClass);
 620
 621   // Use U to determine whether the SETCC immediate range is signed or not.
 622   bool U = ISD::isUnsignedIntSetCC(CC);
 623   if (isIntImmediate(RHS, Tmp2) &&
 624       ((U && isUInt16(Tmp2)) || (!U && isInt16(Tmp2)))) {
 625     Tmp2 = Lo16(Tmp2);
 626     // For comparisons against zero, we can implicity set CR0 if a recording
 627     // variant (e.g. 'or.' instead of 'or') of the instruction that defines
 628     // operand zero of the SetCC node is available.
 629     if (Tmp2 == 0 &&
 630         NodeHasRecordingVariant(LHS.getOpcode()) && LHS.Val->hasOneUse()) {
 631       RecordSuccess = false;
 632       Tmp1 = SelectExpr(LHS, true);
 633       if (RecordSuccess) {
 634         ++Recorded;
 635         BuildMI(BB, PPC::MCRF, 1, Result).addReg(PPC::CR0);
 636         return Result;
 637       }
 638       AlreadySelected = true;
 639     }
 640     // If we could not implicitly set CR0, then emit a compare immediate
 641     // instead.
 642     if (!AlreadySelected) Tmp1 = SelectExpr(LHS);
 643     if (U)
 644       BuildMI(BB, PPC::CMPLWI, 2, Result).addReg(Tmp1).addImm(Tmp2);
 645     else
 646       BuildMI(BB, PPC::CMPWI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
 647   } else {
 648     bool IsInteger = MVT::isInteger(LHS.getValueType());
 649     unsigned CompareOpc = CompareOpcodes[2 * IsInteger + U];
 650     Tmp1 = SelectExpr(LHS);
 651     Tmp2 = SelectExpr(RHS);
 652     BuildMI(BB, CompareOpc, 2, Result).addReg(Tmp1).addReg(Tmp2);
 653   }
 654   return Result;
 655 }
 656
 657 /// Check to see if the load is a constant offset from a base register.
 658 unsigned ISel::SelectAddr(SDOperand N, unsigned& Reg, int& offset)
 659 {
 660   unsigned imm = 0, opcode = N.getOpcode();
 661   if (N.getOpcode() == ISD::ADD) {
 662     bool isFrame = N.getOperand(0).getOpcode() == ISD::FrameIndex;
 663     if (isIntImmediate(N.getOperand(1), imm) && isInt16(imm)) {
 664       offset = Lo16(imm);
 665       if (isFrame) {
 666         ++FrameOff;
 667         Reg = cast<FrameIndexSDNode>(N.getOperand(0))->getIndex();
 668         return 1;
 669       } else {
 670         Reg = SelectExpr(N.getOperand(0));
 671         return 0;
 672       }
 673     } else {
 674       Reg = SelectExpr(N.getOperand(0));
 675       offset = SelectExpr(N.getOperand(1));
 676       return 2;
 677     }
 678   }
 679   // Now check if we're dealing with a global, and whether or not we should emit
 680   // an optimized load or store for statics.
 681   if(GlobalAddressSDNode *GN = dyn_cast<GlobalAddressSDNode>(N)) {
 682     GlobalValue *GV = GN->getGlobal();
 683     if (!GV->hasWeakLinkage() && !GV->isExternal()) {
 684       unsigned GlobalHi = MakeIntReg();
 685       if (PICEnabled)
 686         BuildMI(BB, PPC::ADDIS, 2, GlobalHi).addReg(getGlobalBaseReg())
 687           .addGlobalAddress(GV);
 688       else
 689         BuildMI(BB, PPC::LIS, 1, GlobalHi).addGlobalAddress(GV);
 690       Reg = GlobalHi;
 691       offset = 0;
 692       return 3;
 693     }
 694   }
 695   Reg = SelectExpr(N);
 696   offset = 0;
 697   return 0;
 698 }
 699
 700 void ISel::SelectBranchCC(SDOperand N)
 701 {
 702   MachineBasicBlock *Dest =
 703     cast<BasicBlockSDNode>(N.getOperand(4))->getBasicBlock();
 704
 705   Select(N.getOperand(0));  //chain
 706   ISD::CondCode CC = cast<CondCodeSDNode>(N.getOperand(1))->get();
 707   unsigned CCReg = SelectCC(N.getOperand(2), N.getOperand(3), CC);
 708   unsigned Opc = getBCCForSetCC(CC);
 709
 710   // If this is a two way branch, then grab the fallthrough basic block argument
 711   // and build a PowerPC branch pseudo-op, suitable for long branch conversion
 712   // if necessary by the branch selection pass.  Otherwise, emit a standard
 713   // conditional branch.
 714   if (N.getOpcode() == ISD::BRTWOWAY_CC) {
 715     MachineBasicBlock *Fallthrough =
 716       cast<BasicBlockSDNode>(N.getOperand(5))->getBasicBlock();
 717     BuildMI(BB, PPC::COND_BRANCH, 4).addReg(CCReg).addImm(Opc)
 718       .addMBB(Dest).addMBB(Fallthrough);
 719     BuildMI(BB, PPC::B, 1).addMBB(Fallthrough);
 720   } else {
 721     // Iterate to the next basic block
 722     ilist<MachineBasicBlock>::iterator It = BB;
 723     ++It;
 724
 725     // If the fallthrough path is off the end of the function, which would be
 726     // undefined behavior, set it to be the same as the current block because
 727     // we have nothing better to set it to, and leaving it alone will cause the
 728     // PowerPC Branch Selection pass to crash.
 729     if (It == BB->getParent()->end()) It = Dest;
 730     BuildMI(BB, PPC::COND_BRANCH, 4).addReg(CCReg).addImm(Opc)
 731       .addMBB(Dest).addMBB(It);
 732   }
 733   return;
 734 }
 735
 736 // SelectIntImmediateExpr - Choose code for opcodes with immediate value.
 737 bool ISel::SelectIntImmediateExpr(SDOperand N, unsigned Result,
 738                                   unsigned OCHi, unsigned OCLo,
 739                                   bool IsArithmetic, bool Negate) {
 740   // check constant
 741   ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1));
 742   // exit if not a constant
 743   if (!CN) return false;
 744   // extract immediate
 745   unsigned C = (unsigned)CN->getValue();
 746   // negate if required (ISD::SUB)
 747   if (Negate) C = -C;
 748   // get the hi and lo portions of constant
 749   unsigned Hi = IsArithmetic ? HA16(C) : Hi16(C);
 750   unsigned Lo = Lo16(C);
 751   // assume no intermediate result from lo instruction (same as final result)
 752   unsigned Tmp = Result;
 753   // check if two instructions are needed
 754   if (Hi && Lo) {
 755     // exit if usage indicates it would be better to load immediate into a
 756     // register
 757     if (CN->use_size() > 2) return false;
 758     // need intermediate result for two instructions
 759     Tmp = MakeIntReg();
 760   }
 761   // get first operand
 762   unsigned Opr0 = SelectExpr(N.getOperand(0));
 763   // is a lo instruction needed
 764   if (Lo) {
 765     // generate instruction for lo portion
 766     BuildMI(BB, OCLo, 2, Tmp).addReg(Opr0).addImm(Lo);
 767     // need to switch out first operand for hi instruction
 768     Opr0 = Tmp;
 769   }
 770   // is a hi instruction needed
 771   if (Hi) {
 772     // generate instruction for hi portion
 773     BuildMI(BB, OCHi, 2, Result).addReg(Opr0).addImm(Hi);
 774   }
 775   return true;
 776 }
 777
 778 unsigned ISel::SelectExpr(SDOperand N, bool Recording) {
 779   unsigned Result;
 780   unsigned Tmp1, Tmp2, Tmp3;
 781   unsigned Opc = 0;
 782   unsigned opcode = N.getOpcode();
 783
 784   SDNode *Node = N.Val;
 785   MVT::ValueType DestType = N.getValueType();
 786
 787   if (Node->getOpcode() == ISD::CopyFromReg) {
 788     unsigned Reg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
 789     // Just use the specified register as our input.
 790     if (MRegisterInfo::isVirtualRegister(Reg) || Reg == PPC::R1)
 791       return Reg;
 792   }
 793
 794   unsigned &Reg = ExprMap[N];
 795   if (Reg) return Reg;
 796
 797   switch (N.getOpcode()) {
 798   default:
 799     Reg = Result = (N.getValueType() != MVT::Other) ?
 800                             MakeReg(N.getValueType()) : 1;
 801     break;
 802   case ISD::TAILCALL:
 803   case ISD::CALL:
 804     // If this is a call instruction, make sure to prepare ALL of the result
 805     // values as well as the chain.
 806     if (Node->getNumValues() == 1)
 807       Reg = Result = 1;  // Void call, just a chain.
 808     else {
 809       Result = MakeReg(Node->getValueType(0));
 810       ExprMap[N.getValue(0)] = Result;
 811       for (unsigned i = 1, e = N.Val->getNumValues()-1; i != e; ++i)
 812         ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
 813       ExprMap[SDOperand(Node, Node->getNumValues()-1)] = 1;
 814     }
 815     break;
 816   case ISD::ADD_PARTS:
 817   case ISD::SUB_PARTS:
 818   case ISD::SHL_PARTS:
 819   case ISD::SRL_PARTS:
 820   case ISD::SRA_PARTS:
 821     Result = MakeReg(Node->getValueType(0));
 822     ExprMap[N.getValue(0)] = Result;
 823     for (unsigned i = 1, e = N.Val->getNumValues(); i != e; ++i)
 824       ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
 825     break;
 826   }
 827
 828   switch (opcode) {
 829   default:
 830     Node->dump(); std::cerr << '\n';
 831     assert(0 && "Node not handled!\n");
 832   case ISD::UNDEF:
 833     BuildMI(BB, PPC::IMPLICIT_DEF, 0, Result);
 834     return Result;
 835   case ISD::DYNAMIC_STACKALLOC:
 836     // Generate both result values.  FIXME: Need a better commment here?
 837     if (Result != 1)
 838       ExprMap[N.getValue(1)] = 1;
 839     else
 840       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 841
 842     // FIXME: We are currently ignoring the requested alignment for handling
 843     // greater than the stack alignment.  This will need to be revisited at some
 844     // point.  Align = N.getOperand(2);
 845     if (!isa<ConstantSDNode>(N.getOperand(2)) ||
 846         cast<ConstantSDNode>(N.getOperand(2))->getValue() != 0) {
 847       std::cerr << "Cannot allocate stack object with greater alignment than"
 848                 << " the stack alignment yet!";
 849       abort();
 850     }
 851     Select(N.getOperand(0));
 852     Tmp1 = SelectExpr(N.getOperand(1));
 853     // Subtract size from stack pointer, thereby allocating some space.
 854     BuildMI(BB, PPC::SUBF, 2, PPC::R1).addReg(Tmp1).addReg(PPC::R1);
 855     // Put a pointer to the space into the result register by copying the SP
 856     BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R1).addReg(PPC::R1);
 857     return Result;
 858
 859   case ISD::ConstantPool:
 860     Tmp1 = cast<ConstantPoolSDNode>(N)->getIndex();
 861     Tmp2 = MakeIntReg();
 862     if (PICEnabled)
 863       BuildMI(BB, PPC::ADDIS, 2, Tmp2).addReg(getGlobalBaseReg())
 864         .addConstantPoolIndex(Tmp1);
 865     else
 866       BuildMI(BB, PPC::LIS, 1, Tmp2).addConstantPoolIndex(Tmp1);
 867     BuildMI(BB, PPC::LA, 2, Result).addReg(Tmp2).addConstantPoolIndex(Tmp1);
 868     return Result;
 869
 870   case ISD::FrameIndex:
 871     Tmp1 = cast<FrameIndexSDNode>(N)->getIndex();
 872     addFrameReference(BuildMI(BB, PPC::ADDI, 2, Result), (int)Tmp1, 0, false);
 873     return Result;
 874
 875   case ISD::GlobalAddress: {
 876     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
 877     Tmp1 = MakeIntReg();
 878     if (PICEnabled)
 879       BuildMI(BB, PPC::ADDIS, 2, Tmp1).addReg(getGlobalBaseReg())
 880         .addGlobalAddress(GV);
 881     else
 882       BuildMI(BB, PPC::LIS, 1, Tmp1).addGlobalAddress(GV);
 883     if (GV->hasWeakLinkage() || GV->isExternal()) {
 884       BuildMI(BB, PPC::LWZ, 2, Result).addGlobalAddress(GV).addReg(Tmp1);
 885     } else {
 886       BuildMI(BB, PPC::LA, 2, Result).addReg(Tmp1).addGlobalAddress(GV);
 887     }
 888     return Result;
 889   }
 890
 891   case ISD::LOAD:
 892   case ISD::EXTLOAD:
 893   case ISD::ZEXTLOAD:
 894   case ISD::SEXTLOAD: {
 895     MVT::ValueType TypeBeingLoaded = (ISD::LOAD == opcode) ?
 896       Node->getValueType(0) : cast<VTSDNode>(Node->getOperand(3))->getVT();
 897     bool sext = (ISD::SEXTLOAD == opcode);
 898
 899     // Make sure we generate both values.
 900     if (Result != 1)
 901       ExprMap[N.getValue(1)] = 1;   // Generate the token
 902     else
 903       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 904
 905     SDOperand Chain   = N.getOperand(0);
 906     SDOperand Address = N.getOperand(1);
 907     Select(Chain);
 908
 909     switch (TypeBeingLoaded) {
 910     default: Node->dump(); assert(0 && "Cannot load this type!");
 911     case MVT::i1:  Opc = PPC::LBZ; break;
 912     case MVT::i8:  Opc = PPC::LBZ; break;
 913     case MVT::i16: Opc = sext ? PPC::LHA : PPC::LHZ; break;
 914     case MVT::i32: Opc = PPC::LWZ; break;
 915     case MVT::f32: Opc = PPC::LFS; break;
 916     case MVT::f64: Opc = PPC::LFD; break;
 917     }
 918
 919     if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Address)) {
 920       Tmp1 = MakeIntReg();
 921       int CPI = CP->getIndex();
 922       if (PICEnabled)
 923         BuildMI(BB, PPC::ADDIS, 2, Tmp1).addReg(getGlobalBaseReg())
 924           .addConstantPoolIndex(CPI);
 925       else
 926         BuildMI(BB, PPC::LIS, 1, Tmp1).addConstantPoolIndex(CPI);
 927       BuildMI(BB, Opc, 2, Result).addConstantPoolIndex(CPI).addReg(Tmp1);
 928     } else if (Address.getOpcode() == ISD::FrameIndex) {
 929       Tmp1 = cast<FrameIndexSDNode>(Address)->getIndex();
 930       addFrameReference(BuildMI(BB, Opc, 2, Result), (int)Tmp1);
 931     } else {
 932       int offset;
 933       switch(SelectAddr(Address, Tmp1, offset)) {
 934       default: assert(0 && "Unhandled return value from SelectAddr");
 935       case 0:   // imm offset, no frame, no index
 936         BuildMI(BB, Opc, 2, Result).addSImm(offset).addReg(Tmp1);
 937         break;
 938       case 1:   // imm offset + frame index
 939         addFrameReference(BuildMI(BB, Opc, 2, Result), (int)Tmp1, offset);
 940         break;
 941       case 2:   // base+index addressing
 942         Opc = IndexedOpForOp(Opc);
 943         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(offset);
 944         break;
 945       case 3: {
 946         GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(Address);
 947         GlobalValue *GV = GN->getGlobal();
 948         BuildMI(BB, Opc, 2, Result).addGlobalAddress(GV).addReg(Tmp1);
 949       }
 950       }
 951     }
 952     return Result;
 953   }
 954
 955   case ISD::TAILCALL:
 956   case ISD::CALL: {
 957     unsigned GPR_idx = 0, FPR_idx = 0;
 958     static const unsigned GPR[] = {
 959       PPC::R3, PPC::R4, PPC::R5, PPC::R6,
 960       PPC::R7, PPC::R8, PPC::R9, PPC::R10,
 961     };
 962     static const unsigned FPR[] = {
 963       PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
 964       PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
 965     };
 966
 967     // Lower the chain for this call.
 968     Select(N.getOperand(0));
 969     ExprMap[N.getValue(Node->getNumValues()-1)] = 1;
 970
 971     MachineInstr *CallMI;
 972     // Emit the correct call instruction based on the type of symbol called.
 973     if (GlobalAddressSDNode *GASD =
 974         dyn_cast<GlobalAddressSDNode>(N.getOperand(1))) {
 975       CallMI = BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(GASD->getGlobal(),
 976                                                            true);
 977     } else if (ExternalSymbolSDNode *ESSDN =
 978                dyn_cast<ExternalSymbolSDNode>(N.getOperand(1))) {
 979       CallMI = BuildMI(PPC::CALLpcrel, 1).addExternalSymbol(ESSDN->getSymbol(),
 980                                                             true);
 981     } else {
 982       Tmp1 = SelectExpr(N.getOperand(1));
 983       BuildMI(BB, PPC::OR, 2, PPC::R12).addReg(Tmp1).addReg(Tmp1);
 984       BuildMI(BB, PPC::MTCTR, 1).addReg(PPC::R12);
 985       CallMI = BuildMI(PPC::CALLindirect, 3).addImm(20).addImm(0)
 986         .addReg(PPC::R12);
 987     }
 988
 989     // Load the register args to virtual regs
 990     std::vector<unsigned> ArgVR;
 991     for(int i = 2, e = Node->getNumOperands(); i < e; ++i)
 992       ArgVR.push_back(SelectExpr(N.getOperand(i)));
 993
 994     // Copy the virtual registers into the appropriate argument register
 995     for(int i = 0, e = ArgVR.size(); i < e; ++i) {
 996       switch(N.getOperand(i+2).getValueType()) {
 997       default: Node->dump(); assert(0 && "Unknown value type for call");
 998       case MVT::i1:
 999       case MVT::i8:
1000       case MVT::i16:
1001       case MVT::i32:
1002         assert(GPR_idx < 8 && "Too many int args");
1003         if (N.getOperand(i+2).getOpcode() != ISD::UNDEF) {
1004           BuildMI(BB, PPC::OR,2,GPR[GPR_idx]).addReg(ArgVR[i]).addReg(ArgVR[i]);
1005           CallMI->addRegOperand(GPR[GPR_idx], MachineOperand::Use);
1006         }
1007         ++GPR_idx;
1008         break;
1009       case MVT::f64:
1010       case MVT::f32:
1011         assert(FPR_idx < 13 && "Too many fp args");
1012         BuildMI(BB, PPC::FMR, 1, FPR[FPR_idx]).addReg(ArgVR[i]);
1013         CallMI->addRegOperand(FPR[FPR_idx], MachineOperand::Use);
1014         ++FPR_idx;
1015         break;
1016       }
1017     }
1018
1019     // Put the call instruction in the correct place in the MachineBasicBlock
1020     BB->push_back(CallMI);
1021
1022     switch (Node->getValueType(0)) {
1023     default: assert(0 && "Unknown value type for call result!");
1024     case MVT::Other: return 1;
1025     case MVT::i1:
1026     case MVT::i8:
1027     case MVT::i16:
1028     case MVT::i32:
1029       if (Node->getValueType(1) == MVT::i32) {
1030         BuildMI(BB, PPC::OR, 2, Result+1).addReg(PPC::R3).addReg(PPC::R3);
1031         BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R4).addReg(PPC::R4);
1032       } else {
1033         BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R3).addReg(PPC::R3);
1034       }
1035       break;
1036     case MVT::f32:
1037     case MVT::f64:
1038       BuildMI(BB, PPC::FMR, 1, Result).addReg(PPC::F1);
1039       break;
1040     }
1041     return Result+N.ResNo;
1042   }
1043
1044   case ISD::SIGN_EXTEND:
1045   case ISD::SIGN_EXTEND_INREG:
1046     Tmp1 = SelectExpr(N.getOperand(0));
1047     switch(cast<VTSDNode>(Node->getOperand(1))->getVT()) {
1048     default: Node->dump(); assert(0 && "Unhandled SIGN_EXTEND type"); break;
1049     case MVT::i16:
1050       BuildMI(BB, PPC::EXTSH, 1, Result).addReg(Tmp1);
1051       break;
1052     case MVT::i8:
1053       BuildMI(BB, PPC::EXTSB, 1, Result).addReg(Tmp1);
1054       break;
1055     }
1056     return Result;
1057
1058   case ISD::CopyFromReg:
1059     DestType = N.getValue(0).getValueType();
1060     if (Result == 1)
1061       Result = ExprMap[N.getValue(0)] = MakeReg(DestType);
1062     Tmp1 = dyn_cast<RegisterSDNode>(Node->getOperand(1))->getReg();
1063     if (MVT::isInteger(DestType))
1064       BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp1).addReg(Tmp1);
1065     else
1066       BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
1067     return Result;
1068
1069   case ISD::SHL:
1070     if (isIntImmediate(N.getOperand(1), Tmp2)) {
1071       unsigned SH, MB, ME;
1072       if (isOpcWithIntImmediate(N.getOperand(0), ISD::AND, Tmp3) &&
1073           isRotateAndMask(ISD::SHL, Tmp2, Tmp3, true, SH, MB, ME)) {
1074         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1075         BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(SH)
1076           .addImm(MB).addImm(ME);
1077         return Result;
1078       }
1079       Tmp1 = SelectExpr(N.getOperand(0));
1080       Tmp2 &= 0x1F;
1081       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(Tmp2).addImm(0)
1082         .addImm(31-Tmp2);
1083     } else {
1084       Tmp1 = SelectExpr(N.getOperand(0));
1085       Tmp2 = FoldIfWideZeroExtend(N.getOperand(1));
1086       BuildMI(BB, PPC::SLW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1087     }
1088     return Result;
1089
1090   case ISD::SRL:
1091     if (isIntImmediate(N.getOperand(1), Tmp2)) {
1092       unsigned SH, MB, ME;
1093       if (isOpcWithIntImmediate(N.getOperand(0), ISD::AND, Tmp3) &&
1094           isRotateAndMask(ISD::SRL, Tmp2, Tmp3, true, SH, MB, ME)) {
1095         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1096         BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(SH)
1097           .addImm(MB).addImm(ME);
1098         return Result;
1099       }
1100       Tmp1 = SelectExpr(N.getOperand(0));
1101       Tmp2 &= 0x1F;
1102       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(32-Tmp2)
1103         .addImm(Tmp2).addImm(31);
1104     } else {
1105       Tmp1 = SelectExpr(N.getOperand(0));
1106       Tmp2 = FoldIfWideZeroExtend(N.getOperand(1));
1107       BuildMI(BB, PPC::SRW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1108     }
1109     return Result;
1110
1111   case ISD::SRA:
1112     if (isIntImmediate(N.getOperand(1), Tmp2)) {
1113       unsigned SH, MB, ME;
1114       if (isOpcWithIntImmediate(N.getOperand(0), ISD::AND, Tmp3) &&
1115           isRotateAndMask(ISD::SRA, Tmp2, Tmp3, true, SH, MB, ME)) {
1116         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1117         BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(SH)
1118           .addImm(MB).addImm(ME);
1119         return Result;
1120       }
1121       Tmp1 = SelectExpr(N.getOperand(0));
1122       Tmp2 &= 0x1F;
1123       BuildMI(BB, PPC::SRAWI, 2, Result).addReg(Tmp1).addImm(Tmp2);
1124     } else {
1125       Tmp1 = SelectExpr(N.getOperand(0));
1126       Tmp2 = FoldIfWideZeroExtend(N.getOperand(1));
1127       BuildMI(BB, PPC::SRAW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1128     }
1129     return Result;
1130
1131   case ISD::CTLZ:
1132     Tmp1 = SelectExpr(N.getOperand(0));
1133     BuildMI(BB, PPC::CNTLZW, 1, Result).addReg(Tmp1);
1134     return Result;
1135
1136   case ISD::ADD:
1137     if (!MVT::isInteger(DestType)) {
1138       if (!NoExcessFPPrecision && N.getOperand(0).getOpcode() == ISD::MUL &&
1139           N.getOperand(0).Val->hasOneUse()) {
1140         ++FusedFP; // Statistic
1141         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1142         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1143         Tmp3 = SelectExpr(N.getOperand(1));
1144         Opc = DestType == MVT::f64 ? PPC::FMADD : PPC::FMADDS;
1145         BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1146         return Result;
1147       }
1148       if (!NoExcessFPPrecision && N.getOperand(1).getOpcode() == ISD::MUL &&
1149           N.getOperand(1).Val->hasOneUse()) {
1150         ++FusedFP; // Statistic
1151         Tmp1 = SelectExpr(N.getOperand(1).getOperand(0));
1152         Tmp2 = SelectExpr(N.getOperand(1).getOperand(1));
1153         Tmp3 = SelectExpr(N.getOperand(0));
1154         Opc = DestType == MVT::f64 ? PPC::FMADD : PPC::FMADDS;
1155         BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1156         return Result;
1157       }
1158       Opc = DestType == MVT::f64 ? PPC::FADD : PPC::FADDS;
1159       Tmp1 = SelectExpr(N.getOperand(0));
1160       Tmp2 = SelectExpr(N.getOperand(1));
1161       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1162       return Result;
1163     }
1164     if (SelectIntImmediateExpr(N, Result, PPC::ADDIS, PPC::ADDI, true))
1165       return Result;
1166     Tmp1 = SelectExpr(N.getOperand(0));
1167     Tmp2 = SelectExpr(N.getOperand(1));
1168     BuildMI(BB, PPC::ADD, 2, Result).addReg(Tmp1).addReg(Tmp2);
1169     return Result;
1170
1171   case ISD::AND:
1172     if (isIntImmediate(N.getOperand(1), Tmp2)) {
1173       if (isShiftedMask_32(Tmp2) || isShiftedMask_32(~Tmp2)) {
1174         unsigned SH, MB, ME;
1175         Opc = Recording ? PPC::RLWINMo : PPC::RLWINM;
1176         unsigned OprOpc;
1177         if (isOprShiftImm(N.getOperand(0), OprOpc, Tmp3) &&
1178             isRotateAndMask(OprOpc, Tmp3, Tmp2, false, SH, MB, ME)) {
1179           Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1180         } else {
1181           Tmp1 = SelectExpr(N.getOperand(0));
1182           isRunOfOnes(Tmp2, MB, ME);
1183           SH = 0;
1184         }
1185         BuildMI(BB, Opc, 4, Result).addReg(Tmp1).addImm(SH)
1186           .addImm(MB).addImm(ME);
1187         RecordSuccess = true;
1188         return Result;
1189       } else if (isUInt16(Tmp2)) {
1190         Tmp2 = Lo16(Tmp2);
1191         Tmp1 = SelectExpr(N.getOperand(0));
1192         BuildMI(BB, PPC::ANDIo, 2, Result).addReg(Tmp1).addImm(Tmp2);
1193         RecordSuccess = true;
1194         return Result;
1195       } else if (isUInt16(Tmp2)) {
1196         Tmp2 = Hi16(Tmp2);
1197         Tmp1 = SelectExpr(N.getOperand(0));
1198         BuildMI(BB, PPC::ANDISo, 2, Result).addReg(Tmp1).addImm(Tmp2);
1199         RecordSuccess = true;
1200        return Result;
1201       }
1202     }
1203     if (isOprNot(N.getOperand(1))) {
1204       Tmp1 = SelectExpr(N.getOperand(0));
1205       Tmp2 = SelectExpr(N.getOperand(1).getOperand(0));
1206       BuildMI(BB, PPC::ANDC, 2, Result).addReg(Tmp1).addReg(Tmp2);
1207       RecordSuccess = false;
1208       return Result;
1209     }
1210     if (isOprNot(N.getOperand(0))) {
1211       Tmp1 = SelectExpr(N.getOperand(1));
1212       Tmp2 = SelectExpr(N.getOperand(0).getOperand(0));
1213       BuildMI(BB, PPC::ANDC, 2, Result).addReg(Tmp1).addReg(Tmp2);
1214       RecordSuccess = false;
1215       return Result;
1216     }
1217     // emit a regular and
1218     Tmp1 = SelectExpr(N.getOperand(0));
1219     Tmp2 = SelectExpr(N.getOperand(1));
1220     Opc = Recording ? PPC::ANDo : PPC::AND;
1221     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1222     RecordSuccess = true;
1223     return Result;
1224
1225   case ISD::OR:
1226     if (SelectBitfieldInsert(N, Result))
1227       return Result;
1228     if (SelectIntImmediateExpr(N, Result, PPC::ORIS, PPC::ORI))
1229       return Result;
1230     if (isOprNot(N.getOperand(1))) {
1231       Tmp1 = SelectExpr(N.getOperand(0));
1232       Tmp2 = SelectExpr(N.getOperand(1).getOperand(0));
1233       BuildMI(BB, PPC::ORC, 2, Result).addReg(Tmp1).addReg(Tmp2);
1234       RecordSuccess = false;
1235       return Result;
1236     }
1237     if (isOprNot(N.getOperand(0))) {
1238       Tmp1 = SelectExpr(N.getOperand(1));
1239       Tmp2 = SelectExpr(N.getOperand(0).getOperand(0));
1240       BuildMI(BB, PPC::ORC, 2, Result).addReg(Tmp1).addReg(Tmp2);
1241       RecordSuccess = false;
1242       return Result;
1243     }
1244     // emit regular or
1245     Tmp1 = SelectExpr(N.getOperand(0));
1246     Tmp2 = SelectExpr(N.getOperand(1));
1247     Opc = Recording ? PPC::ORo : PPC::OR;
1248     RecordSuccess = true;
1249     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1250     return Result;
1251
1252   case ISD::XOR: {
1253     // Check for EQV: xor, (xor a, -1), b
1254     if (isOprNot(N.getOperand(0))) {
1255       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1256       Tmp2 = SelectExpr(N.getOperand(1));
1257       BuildMI(BB, PPC::EQV, 2, Result).addReg(Tmp1).addReg(Tmp2);
1258       return Result;
1259     }
1260     // Check for NOT, NOR, EQV, and NAND: xor (copy, or, xor, and), -1
1261     if (isOprNot(N)) {
1262       switch(N.getOperand(0).getOpcode()) {
1263       case ISD::OR:
1264         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1265         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1266         BuildMI(BB, PPC::NOR, 2, Result).addReg(Tmp1).addReg(Tmp2);
1267         break;
1268       case ISD::AND:
1269         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1270         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1271         BuildMI(BB, PPC::NAND, 2, Result).addReg(Tmp1).addReg(Tmp2);
1272         break;
1273       case ISD::XOR:
1274         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1275         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1276         BuildMI(BB, PPC::EQV, 2, Result).addReg(Tmp1).addReg(Tmp2);
1277         break;
1278       default:
1279         Tmp1 = SelectExpr(N.getOperand(0));
1280         BuildMI(BB, PPC::NOR, 2, Result).addReg(Tmp1).addReg(Tmp1);
1281         break;
1282       }
1283       return Result;
1284     }
1285     if (SelectIntImmediateExpr(N, Result, PPC::XORIS, PPC::XORI))
1286       return Result;
1287     // emit regular xor
1288     Tmp1 = SelectExpr(N.getOperand(0));
1289     Tmp2 = SelectExpr(N.getOperand(1));
1290     BuildMI(BB, PPC::XOR, 2, Result).addReg(Tmp1).addReg(Tmp2);
1291     return Result;
1292   }
1293
1294    case ISD::SUB:
1295     if (!MVT::isInteger(DestType)) {
1296       if (!NoExcessFPPrecision && N.getOperand(0).getOpcode() == ISD::MUL &&
1297           N.getOperand(0).Val->hasOneUse()) {
1298         ++FusedFP; // Statistic
1299         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1300         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1301         Tmp3 = SelectExpr(N.getOperand(1));
1302         Opc = DestType == MVT::f64 ? PPC::FMSUB : PPC::FMSUBS;
1303         BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1304         return Result;
1305       }
1306       if (!NoExcessFPPrecision && N.getOperand(1).getOpcode() == ISD::MUL &&
1307           N.getOperand(1).Val->hasOneUse()) {
1308         ++FusedFP; // Statistic
1309         Tmp1 = SelectExpr(N.getOperand(1).getOperand(0));
1310         Tmp2 = SelectExpr(N.getOperand(1).getOperand(1));
1311         Tmp3 = SelectExpr(N.getOperand(0));
1312         Opc = DestType == MVT::f64 ? PPC::FNMSUB : PPC::FNMSUBS;
1313         BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1314         return Result;
1315       }
1316       Opc = DestType == MVT::f64 ? PPC::FSUB : PPC::FSUBS;
1317       Tmp1 = SelectExpr(N.getOperand(0));
1318       Tmp2 = SelectExpr(N.getOperand(1));
1319       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1320       return Result;
1321     }
1322     if (isIntImmediate(N.getOperand(0), Tmp1) && isInt16(Tmp1)) {
1323       Tmp1 = Lo16(Tmp1);
1324       Tmp2 = SelectExpr(N.getOperand(1));
1325       if (0 == Tmp1)
1326         BuildMI(BB, PPC::NEG, 1, Result).addReg(Tmp2);
1327       else
1328         BuildMI(BB, PPC::SUBFIC, 2, Result).addReg(Tmp2).addSImm(Tmp1);
1329       return Result;
1330     }
1331     if (SelectIntImmediateExpr(N, Result, PPC::ADDIS, PPC::ADDI, true, true))
1332         return Result;
1333     Tmp1 = SelectExpr(N.getOperand(0));
1334     Tmp2 = SelectExpr(N.getOperand(1));
1335     BuildMI(BB, PPC::SUBF, 2, Result).addReg(Tmp2).addReg(Tmp1);
1336     return Result;
1337
1338   case ISD::MUL:
1339     Tmp1 = SelectExpr(N.getOperand(0));
1340     if (isIntImmediate(N.getOperand(1), Tmp2) && isInt16(Tmp2)) {
1341       Tmp2 = Lo16(Tmp2);
1342       BuildMI(BB, PPC::MULLI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
1343     } else {
1344       Tmp2 = SelectExpr(N.getOperand(1));
1345       switch (DestType) {
1346       default: assert(0 && "Unknown type to ISD::MUL"); break;
1347       case MVT::i32: Opc = PPC::MULLW; break;
1348       case MVT::f32: Opc = PPC::FMULS; break;
1349       case MVT::f64: Opc = PPC::FMUL; break;
1350       }
1351       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1352     }
1353     return Result;
1354
1355   case ISD::MULHS:
1356   case ISD::MULHU:
1357     Tmp1 = SelectExpr(N.getOperand(0));
1358     Tmp2 = SelectExpr(N.getOperand(1));
1359     Opc = (ISD::MULHU == opcode) ? PPC::MULHWU : PPC::MULHW;
1360     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1361     return Result;
1362
1363   case ISD::SDIV:
1364     if (isIntImmediate(N.getOperand(1), Tmp3)) {
1365       if ((signed)Tmp3 > 0 && isPowerOf2_32(Tmp3)) {
1366         Tmp3 = Log2_32(Tmp3);
1367         Tmp1 = MakeIntReg();
1368         Tmp2 = SelectExpr(N.getOperand(0));
1369         BuildMI(BB, PPC::SRAWI, 2, Tmp1).addReg(Tmp2).addImm(Tmp3);
1370         BuildMI(BB, PPC::ADDZE, 1, Result).addReg(Tmp1);
1371         return Result;
1372       } else if ((signed)Tmp3 < 0 && isPowerOf2_32(-Tmp3)) {
1373         Tmp3 = Log2_32(-Tmp3);
1374         Tmp2 = SelectExpr(N.getOperand(0));
1375         Tmp1 = MakeIntReg();
1376         unsigned Tmp4 = MakeIntReg();
1377         BuildMI(BB, PPC::SRAWI, 2, Tmp1).addReg(Tmp2).addImm(Tmp3);
1378         BuildMI(BB, PPC::ADDZE, 1, Tmp4).addReg(Tmp1);
1379         BuildMI(BB, PPC::NEG, 1, Result).addReg(Tmp4);
1380         return Result;
1381       }
1382     }
1383     // fall thru
1384   case ISD::UDIV:
1385     // If this is a divide by constant, we can emit code using some magic
1386     // constants to implement it as a multiply instead.
1387     if (isIntImmediate(N.getOperand(1), Tmp3)) {
1388       if (opcode == ISD::SDIV) {
1389         if ((signed)Tmp3 < -1 || (signed)Tmp3 > 1) {
1390           ExprMap.erase(N);
1391           return SelectExpr(BuildSDIVSequence(N));
1392         }
1393       } else {
1394         if ((signed)Tmp3 > 1) {
1395           ExprMap.erase(N);
1396           return SelectExpr(BuildUDIVSequence(N));
1397         }
1398       }
1399     }
1400     Tmp1 = SelectExpr(N.getOperand(0));
1401     Tmp2 = SelectExpr(N.getOperand(1));
1402     switch (DestType) {
1403     default: assert(0 && "Unknown type to ISD::SDIV"); break;
1404     case MVT::i32: Opc = (ISD::UDIV == opcode) ? PPC::DIVWU : PPC::DIVW; break;
1405     case MVT::f32: Opc = PPC::FDIVS; break;
1406     case MVT::f64: Opc = PPC::FDIV; break;
1407     }
1408     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1409     return Result;
1410
1411   case ISD::ADD_PARTS:
1412   case ISD::SUB_PARTS: {
1413     assert(N.getNumOperands() == 4 && N.getValueType() == MVT::i32 &&
1414            "Not an i64 add/sub!");
1415     unsigned Tmp4 = 0;
1416     bool ME = isIntImmediate(N.getOperand(3),Tmp3) && ((signed)Tmp3 == -1);
1417     bool ZE = isIntImmediate(N.getOperand(3),Tmp3) && (Tmp3 == 0);
1418     bool IM = isIntImmediate(N.getOperand(2),Tmp3) && ((signed)Tmp3 >= -32768 ||
1419                                                        (signed)Tmp3 <   32768);
1420     Tmp1 = SelectExpr(N.getOperand(0));
1421     Tmp2 = SelectExpr(N.getOperand(1));
1422     if (!IM || N.getOpcode() == ISD::SUB_PARTS)
1423       Tmp3 = SelectExpr(N.getOperand(2));
1424     if ((!ME && !ZE) || N.getOpcode() == ISD::SUB_PARTS)
1425       Tmp4 = SelectExpr(N.getOperand(3));
1426
1427     if (N.getOpcode() == ISD::ADD_PARTS) {
1428       // Codegen the low 32 bits of the add.  Interestingly, there is no shifted
1429       // form of add immediate carrying.
1430       if (IM)
1431         BuildMI(BB, PPC::ADDIC, 2, Result).addReg(Tmp1).addSImm(Tmp3);
1432       else
1433         BuildMI(BB, PPC::ADDC, 2, Result).addReg(Tmp1).addReg(Tmp3);
1434       // Codegen the high 32 bits, adding zero, minus one, or the full value
1435       // along with the carry flag produced by addc/addic to tmp2.
1436       if (ZE)
1437         BuildMI(BB, PPC::ADDZE, 1, Result+1).addReg(Tmp2);
1438       else if (ME)
1439         BuildMI(BB, PPC::ADDME, 1, Result+1).addReg(Tmp2);
1440       else
1441         BuildMI(BB, PPC::ADDE, 2, Result+1).addReg(Tmp2).addReg(Tmp4);
1442     } else {
1443       BuildMI(BB, PPC::SUBFC, 2, Result).addReg(Tmp3).addReg(Tmp1);
1444       BuildMI(BB, PPC::SUBFE, 2, Result+1).addReg(Tmp4).addReg(Tmp2);
1445     }
1446     return Result+N.ResNo;
1447   }
1448
1449   case ISD::SHL_PARTS:
1450   case ISD::SRA_PARTS:
1451   case ISD::SRL_PARTS: {
1452     assert(N.getNumOperands() == 3 && N.getValueType() == MVT::i32 &&
1453            "Not an i64 shift!");
1454     unsigned ShiftOpLo = SelectExpr(N.getOperand(0));
1455     unsigned ShiftOpHi = SelectExpr(N.getOperand(1));
1456     unsigned SHReg = FoldIfWideZeroExtend(N.getOperand(2));
1457     Tmp1 = MakeIntReg();
1458     Tmp2 = MakeIntReg();
1459     Tmp3 = MakeIntReg();
1460     unsigned Tmp4 = MakeIntReg();
1461     unsigned Tmp5 = MakeIntReg();
1462     unsigned Tmp6 = MakeIntReg();
1463     BuildMI(BB, PPC::SUBFIC, 2, Tmp1).addReg(SHReg).addSImm(32);
1464     if (ISD::SHL_PARTS == opcode) {
1465       BuildMI(BB, PPC::SLW, 2, Tmp2).addReg(ShiftOpHi).addReg(SHReg);
1466       BuildMI(BB, PPC::SRW, 2, Tmp3).addReg(ShiftOpLo).addReg(Tmp1);
1467       BuildMI(BB, PPC::OR, 2, Tmp4).addReg(Tmp2).addReg(Tmp3);
1468       BuildMI(BB, PPC::ADDI, 2, Tmp5).addReg(SHReg).addSImm(-32);
1469       BuildMI(BB, PPC::SLW, 2, Tmp6).addReg(ShiftOpLo).addReg(Tmp5);
1470       BuildMI(BB, PPC::OR, 2, Result+1).addReg(Tmp4).addReg(Tmp6);
1471       BuildMI(BB, PPC::SLW, 2, Result).addReg(ShiftOpLo).addReg(SHReg);
1472     } else if (ISD::SRL_PARTS == opcode) {
1473       BuildMI(BB, PPC::SRW, 2, Tmp2).addReg(ShiftOpLo).addReg(SHReg);
1474       BuildMI(BB, PPC::SLW, 2, Tmp3).addReg(ShiftOpHi).addReg(Tmp1);
1475       BuildMI(BB, PPC::OR, 2, Tmp4).addReg(Tmp2).addReg(Tmp3);
1476       BuildMI(BB, PPC::ADDI, 2, Tmp5).addReg(SHReg).addSImm(-32);
1477       BuildMI(BB, PPC::SRW, 2, Tmp6).addReg(ShiftOpHi).addReg(Tmp5);
1478       BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp4).addReg(Tmp6);
1479       BuildMI(BB, PPC::SRW, 2, Result+1).addReg(ShiftOpHi).addReg(SHReg);
1480     } else {
1481       MachineBasicBlock *TmpMBB = new MachineBasicBlock(BB->getBasicBlock());
1482       MachineBasicBlock *PhiMBB = new MachineBasicBlock(BB->getBasicBlock());
1483       MachineBasicBlock *OldMBB = BB;
1484       MachineFunction *F = BB->getParent();
1485       ilist<MachineBasicBlock>::iterator It = BB; ++It;
1486       F->getBasicBlockList().insert(It, TmpMBB);
1487       F->getBasicBlockList().insert(It, PhiMBB);
1488       BB->addSuccessor(TmpMBB);
1489       BB->addSuccessor(PhiMBB);
1490       BuildMI(BB, PPC::SRW, 2, Tmp2).addReg(ShiftOpLo).addReg(SHReg);
1491       BuildMI(BB, PPC::SLW, 2, Tmp3).addReg(ShiftOpHi).addReg(Tmp1);
1492       BuildMI(BB, PPC::OR, 2, Tmp4).addReg(Tmp2).addReg(Tmp3);
1493       BuildMI(BB, PPC::ADDICo, 2, Tmp5).addReg(SHReg).addSImm(-32);
1494       BuildMI(BB, PPC::SRAW, 2, Tmp6).addReg(ShiftOpHi).addReg(Tmp5);
1495       BuildMI(BB, PPC::SRAW, 2, Result+1).addReg(ShiftOpHi).addReg(SHReg);
1496       BuildMI(BB, PPC::BLE, 2).addReg(PPC::CR0).addMBB(PhiMBB);
1497       // Select correct least significant half if the shift amount > 32
1498       BB = TmpMBB;
1499       unsigned Tmp7 = MakeIntReg();
1500       BuildMI(BB, PPC::OR, 2, Tmp7).addReg(Tmp6).addReg(Tmp6);
1501       TmpMBB->addSuccessor(PhiMBB);
1502       BB = PhiMBB;
1503       BuildMI(BB, PPC::PHI, 4, Result).addReg(Tmp4).addMBB(OldMBB)
1504         .addReg(Tmp7).addMBB(TmpMBB);
1505     }
1506     return Result+N.ResNo;
1507   }
1508
1509   case ISD::FP_TO_SINT: {
1510     Tmp1 = SelectExpr(N.getOperand(0));
1511     Tmp2 = MakeFPReg();
1512     BuildMI(BB, PPC::FCTIWZ, 1, Tmp2).addReg(Tmp1);
1513     int FrameIdx = BB->getParent()->getFrameInfo()->CreateStackObject(8, 8);
1514     addFrameReference(BuildMI(BB, PPC::STFD, 3).addReg(Tmp2), FrameIdx);
1515     addFrameReference(BuildMI(BB, PPC::LWZ, 2, Result), FrameIdx, 4);
1516     return Result;
1517   }
1518
1519   case ISD::SETCC: {
1520     ISD::CondCode CC = cast<CondCodeSDNode>(Node->getOperand(2))->get();
1521     if (isIntImmediate(Node->getOperand(1), Tmp3)) {
1522       // We can codegen setcc op, imm very efficiently compared to a brcond.
1523       // Check for those cases here.
1524       // setcc op, 0
1525       if (Tmp3 == 0) {
1526         Tmp1 = SelectExpr(Node->getOperand(0));
1527         switch (CC) {
1528         default: Node->dump(); assert(0 && "Unhandled SetCC condition"); abort();
1529         case ISD::SETEQ:
1530           Tmp2 = MakeIntReg();
1531           BuildMI(BB, PPC::CNTLZW, 1, Tmp2).addReg(Tmp1);
1532           BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp2).addImm(27)
1533             .addImm(5).addImm(31);
1534           break;
1535         case ISD::SETNE:
1536           Tmp2 = MakeIntReg();
1537           BuildMI(BB, PPC::ADDIC, 2, Tmp2).addReg(Tmp1).addSImm(-1);
1538           BuildMI(BB, PPC::SUBFE, 2, Result).addReg(Tmp2).addReg(Tmp1);
1539           break;
1540         case ISD::SETLT:
1541           BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(1)
1542             .addImm(31).addImm(31);
1543           break;
1544         case ISD::SETGT:
1545           Tmp2 = MakeIntReg();
1546           Tmp3 = MakeIntReg();
1547           BuildMI(BB, PPC::NEG, 2, Tmp2).addReg(Tmp1);
1548           BuildMI(BB, PPC::ANDC, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1549           BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp3).addImm(1)
1550             .addImm(31).addImm(31);
1551           break;
1552         }
1553         return Result;
1554       } else if (Tmp3 == ~0U) {        // setcc op, -1
1555         Tmp1 = SelectExpr(Node->getOperand(0));
1556         switch (CC) {
1557         default: assert(0 && "Unhandled SetCC condition"); abort();
1558         case ISD::SETEQ:
1559           Tmp2 = MakeIntReg();
1560           Tmp3 = MakeIntReg();
1561           BuildMI(BB, PPC::ADDIC, 2, Tmp2).addReg(Tmp1).addSImm(1);
1562           BuildMI(BB, PPC::LI, 1, Tmp3).addSImm(0);
1563           BuildMI(BB, PPC::ADDZE, 1, Result).addReg(Tmp3);
1564           break;
1565         case ISD::SETNE:
1566           Tmp2 = MakeIntReg();
1567           Tmp3 = MakeIntReg();
1568           BuildMI(BB, PPC::NOR, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
1569           BuildMI(BB, PPC::ADDIC, 2, Tmp3).addReg(Tmp2).addSImm(-1);
1570           BuildMI(BB, PPC::SUBFE, 2, Result).addReg(Tmp3).addReg(Tmp2);
1571           break;
1572         case ISD::SETLT:
1573           Tmp2 = MakeIntReg();
1574           Tmp3 = MakeIntReg();
1575           BuildMI(BB, PPC::ADDI, 2, Tmp2).addReg(Tmp1).addSImm(1);
1576           BuildMI(BB, PPC::AND, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1577           BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp3).addImm(1)
1578             .addImm(31).addImm(31);
1579           break;
1580         case ISD::SETGT:
1581           Tmp2 = MakeIntReg();
1582           BuildMI(BB, PPC::RLWINM, 4, Tmp2).addReg(Tmp1).addImm(1)
1583             .addImm(31).addImm(31);
1584           BuildMI(BB, PPC::XORI, 2, Result).addReg(Tmp2).addImm(1);
1585           break;
1586         }
1587         return Result;
1588       }
1589     }
1590
1591     unsigned CCReg = SelectCC(N.getOperand(0), N.getOperand(1), CC);
1592     MoveCRtoGPR(CCReg, CC, Result);
1593     return Result;
1594   }
1595
1596   case ISD::SELECT_CC: {
1597     ISD::CondCode CC = cast<CondCodeSDNode>(N.getOperand(4))->get();
1598     if (!MVT::isInteger(N.getOperand(0).getValueType()) &&
1599         !MVT::isInteger(N.getOperand(2).getValueType()) &&
1600         CC != ISD::SETEQ && CC != ISD::SETNE) {
1601       MVT::ValueType VT = N.getOperand(0).getValueType();
1602       unsigned TV = SelectExpr(N.getOperand(2)); // Use if TRUE
1603       unsigned FV = SelectExpr(N.getOperand(3)); // Use if FALSE
1604
1605       ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N.getOperand(1));
1606       if (CN && (CN->isExactlyValue(-0.0) || CN->isExactlyValue(0.0))) {
1607         switch(CC) {
1608         default: assert(0 && "Invalid FSEL condition"); abort();
1609         case ISD::SETULT:
1610         case ISD::SETLT:
1611           std::swap(TV, FV);  // fsel is natively setge, swap operands for setlt
1612         case ISD::SETUGE:
1613         case ISD::SETGE:
1614           Tmp1 = SelectExpr(N.getOperand(0));   // Val to compare against
1615           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp1).addReg(TV).addReg(FV);
1616           return Result;
1617         case ISD::SETUGT:
1618         case ISD::SETGT:
1619           std::swap(TV, FV);  // fsel is natively setge, swap operands for setlt
1620         case ISD::SETULE:
1621         case ISD::SETLE: {
1622           if (N.getOperand(0).getOpcode() == ISD::FNEG) {
1623             Tmp2 = SelectExpr(N.getOperand(0).getOperand(0));
1624           } else {
1625             Tmp2 = MakeReg(VT);
1626             Tmp1 = SelectExpr(N.getOperand(0));   // Val to compare against
1627             BuildMI(BB, PPC::FNEG, 1, Tmp2).addReg(Tmp1);
1628           }
1629           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp2).addReg(TV).addReg(FV);
1630           return Result;
1631         }
1632         }
1633       } else {
1634         Opc = (MVT::f64 == VT) ? PPC::FSUB : PPC::FSUBS;
1635         Tmp1 = SelectExpr(N.getOperand(0));   // Val to compare against
1636         Tmp2 = SelectExpr(N.getOperand(1));
1637         Tmp3 =  MakeReg(VT);
1638         switch(CC) {
1639         default: assert(0 && "Invalid FSEL condition"); abort();
1640         case ISD::SETULT:
1641         case ISD::SETLT:
1642           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
1643           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(FV).addReg(TV);
1644           return Result;
1645         case ISD::SETUGE:
1646         case ISD::SETGE:
1647           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
1648           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(TV).addReg(FV);
1649           return Result;
1650         case ISD::SETUGT:
1651         case ISD::SETGT:
1652           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1653           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(FV).addReg(TV);
1654           return Result;
1655         case ISD::SETULE:
1656         case ISD::SETLE:
1657           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1658           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(TV).addReg(FV);
1659           return Result;
1660         }
1661       }
1662       assert(0 && "Should never get here");
1663     }
1664
1665     // handle the setcc cases here.  select_cc lhs, 0, 1, 0, cc
1666     ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N.getOperand(1));
1667     ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N.getOperand(2));
1668     ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N.getOperand(3));
1669     if (N1C && N2C && N3C && N1C->isNullValue() && N3C->isNullValue() &&
1670         N2C->getValue() == 1ULL && CC == ISD::SETNE) {
1671       Tmp1 = SelectExpr(Node->getOperand(0));
1672       Tmp2 = MakeIntReg();
1673       BuildMI(BB, PPC::ADDIC, 2, Tmp2).addReg(Tmp1).addSImm(-1);
1674       BuildMI(BB, PPC::SUBFE, 2, Result).addReg(Tmp2).addReg(Tmp1);
1675       return Result;
1676     }
1677
1678     // If the False value only has one use, we can generate better code by
1679     // selecting it in the fallthrough basic block rather than here, which
1680     // increases register pressure.
1681     unsigned TrueValue = SelectExpr(N.getOperand(2));
1682     unsigned FalseValue;
1683
1684     // If the false value is simple enough, evaluate it inline in the false
1685     // block.
1686     if (N.getOperand(3).Val->hasOneUse() &&
1687         (isa<ConstantSDNode>(N.getOperand(3)) ||
1688          isa<ConstantFPSDNode>(N.getOperand(3)) ||
1689          isa<GlobalAddressSDNode>(N.getOperand(3))))
1690       FalseValue = 0;
1691     else
1692       FalseValue = SelectExpr(N.getOperand(3));
1693     unsigned CCReg = SelectCC(N.getOperand(0), N.getOperand(1), CC);
1694     Opc = getBCCForSetCC(CC);
1695
1696     // Create an iterator with which to insert the MBB for copying the false
1697     // value and the MBB to hold the PHI instruction for this SetCC.
1698     MachineBasicBlock *thisMBB = BB;
1699     const BasicBlock *LLVM_BB = BB->getBasicBlock();
1700     ilist<MachineBasicBlock>::iterator It = BB;
1701     ++It;
1702
1703     //  thisMBB:
1704     //  ...
1705     //   TrueVal = ...
1706     //   cmpTY ccX, r1, r2
1707     //   bCC copy1MBB
1708     //   fallthrough --> copy0MBB
1709     MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
1710     MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
1711     BuildMI(BB, Opc, 2).addReg(CCReg).addMBB(sinkMBB);
1712     MachineFunction *F = BB->getParent();
1713     F->getBasicBlockList().insert(It, copy0MBB);
1714     F->getBasicBlockList().insert(It, sinkMBB);
1715     // Update machine-CFG edges
1716     BB->addSuccessor(copy0MBB);
1717     BB->addSuccessor(sinkMBB);
1718
1719     //  copy0MBB:
1720     //   %FalseValue = ...
1721     //   # fallthrough to sinkMBB
1722     BB = copy0MBB;
1723
1724     // If the false value is simple enough, evaluate it here, to avoid it being
1725     // evaluated on the true edge.
1726     if (FalseValue == 0)
1727       FalseValue = SelectExpr(N.getOperand(3));
1728
1729     // Update machine-CFG edges
1730     BB->addSuccessor(sinkMBB);
1731
1732     //  sinkMBB:
1733     //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
1734     //  ...
1735     BB = sinkMBB;
1736     BuildMI(BB, PPC::PHI, 4, Result).addReg(FalseValue)
1737       .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
1738     return Result;
1739   }
1740
1741   case ISD::Constant: {
1742     assert(N.getValueType() == MVT::i32 &&
1743            "Only i32 constants are legal on this target!");
1744     unsigned v = (unsigned)cast<ConstantSDNode>(N)->getValue();
1745     if (isInt16(v)) {
1746       BuildMI(BB, PPC::LI, 1, Result).addSImm(Lo16(v));
1747     } else {
1748       unsigned Hi = Hi16(v);
1749       unsigned Lo = Lo16(v);
1750       if (Lo) {
1751         Tmp1 = MakeIntReg();
1752         BuildMI(BB, PPC::LIS, 1, Tmp1).addSImm(Hi);
1753         BuildMI(BB, PPC::ORI, 2, Result).addReg(Tmp1).addImm(Lo);
1754       } else {
1755         BuildMI(BB, PPC::LIS, 1, Result).addSImm(Hi);
1756       }
1757     }
1758     return Result;
1759   }
1760
1761   case ISD::ConstantFP: {
1762     ConstantFPSDNode *CN = cast<ConstantFPSDNode>(N);
1763     Result = getConstDouble(CN->getValue(), Result);
1764     return Result;
1765   }
1766
1767   case ISD::FNEG:
1768     if (!NoExcessFPPrecision &&
1769         ISD::ADD == N.getOperand(0).getOpcode() &&
1770         N.getOperand(0).Val->hasOneUse() &&
1771         ISD::MUL == N.getOperand(0).getOperand(0).getOpcode() &&
1772         N.getOperand(0).getOperand(0).Val->hasOneUse()) {
1773       ++FusedFP; // Statistic
1774       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(0));
1775       Tmp2 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(1));
1776       Tmp3 = SelectExpr(N.getOperand(0).getOperand(1));
1777       Opc = DestType == MVT::f64 ? PPC::FNMADD : PPC::FNMADDS;
1778       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1779     } else if (!NoExcessFPPrecision &&
1780         ISD::ADD == N.getOperand(0).getOpcode() &&
1781         N.getOperand(0).Val->hasOneUse() &&
1782         ISD::MUL == N.getOperand(0).getOperand(1).getOpcode() &&
1783         N.getOperand(0).getOperand(1).Val->hasOneUse()) {
1784       ++FusedFP; // Statistic
1785       Tmp1 = SelectExpr(N.getOperand(0).getOperand(1).getOperand(0));
1786       Tmp2 = SelectExpr(N.getOperand(0).getOperand(1).getOperand(1));
1787       Tmp3 = SelectExpr(N.getOperand(0).getOperand(0));
1788       Opc = DestType == MVT::f64 ? PPC::FNMADD : PPC::FNMADDS;
1789       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1790     } else if (ISD::FABS == N.getOperand(0).getOpcode()) {
1791       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1792       BuildMI(BB, PPC::FNABS, 1, Result).addReg(Tmp1);
1793     } else {
1794       Tmp1 = SelectExpr(N.getOperand(0));
1795       BuildMI(BB, PPC::FNEG, 1, Result).addReg(Tmp1);
1796     }
1797     return Result;
1798
1799   case ISD::FABS:
1800     Tmp1 = SelectExpr(N.getOperand(0));
1801     BuildMI(BB, PPC::FABS, 1, Result).addReg(Tmp1);
1802     return Result;
1803
1804   case ISD::FSQRT:
1805     Tmp1 = SelectExpr(N.getOperand(0));
1806     Opc = DestType == MVT::f64 ? PPC::FSQRT : PPC::FSQRTS;
1807     BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
1808     return Result;
1809
1810   case ISD::FP_ROUND:
1811     assert (DestType == MVT::f32 &&
1812             N.getOperand(0).getValueType() == MVT::f64 &&
1813             "only f64 to f32 conversion supported here");
1814     Tmp1 = SelectExpr(N.getOperand(0));
1815     BuildMI(BB, PPC::FRSP, 1, Result).addReg(Tmp1);
1816     return Result;
1817
1818   case ISD::FP_EXTEND:
1819     assert (DestType == MVT::f64 &&
1820             N.getOperand(0).getValueType() == MVT::f32 &&
1821             "only f32 to f64 conversion supported here");
1822     Tmp1 = SelectExpr(N.getOperand(0));
1823     BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
1824     return Result;
1825   }
1826   return 0;
1827 }
1828
1829 void ISel::Select(SDOperand N) {
1830   unsigned Tmp1, Tmp2, Tmp3, Opc;
1831   unsigned opcode = N.getOpcode();
1832
1833   if (!ExprMap.insert(std::make_pair(N, 1)).second)
1834     return;  // Already selected.
1835
1836   SDNode *Node = N.Val;
1837
1838   switch (Node->getOpcode()) {
1839   default:
1840     Node->dump(); std::cerr << "\n";
1841     assert(0 && "Node not handled yet!");
1842   case ISD::EntryToken: return;  // Noop
1843   case ISD::TokenFactor:
1844     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
1845       Select(Node->getOperand(i));
1846     return;
1847   case ISD::CALLSEQ_START:
1848   case ISD::CALLSEQ_END:
1849     Select(N.getOperand(0));
1850     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
1851     Opc = N.getOpcode() == ISD::CALLSEQ_START ? PPC::ADJCALLSTACKDOWN :
1852       PPC::ADJCALLSTACKUP;
1853     BuildMI(BB, Opc, 1).addImm(Tmp1);
1854     return;
1855   case ISD::BR: {
1856     MachineBasicBlock *Dest =
1857       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
1858     Select(N.getOperand(0));
1859     BuildMI(BB, PPC::B, 1).addMBB(Dest);
1860     return;
1861   }
1862   case ISD::BR_CC:
1863   case ISD::BRTWOWAY_CC:
1864     SelectBranchCC(N);
1865     return;
1866   case ISD::CopyToReg:
1867     Select(N.getOperand(0));
1868     Tmp1 = SelectExpr(N.getOperand(2));
1869     Tmp2 = cast<RegisterSDNode>(N.getOperand(1))->getReg();
1870
1871     if (Tmp1 != Tmp2) {
1872       if (N.getOperand(2).getValueType() == MVT::f64 ||
1873           N.getOperand(2).getValueType() == MVT::f32)
1874         BuildMI(BB, PPC::FMR, 1, Tmp2).addReg(Tmp1);
1875       else
1876         BuildMI(BB, PPC::OR, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
1877     }
1878     return;
1879   case ISD::ImplicitDef:
1880     Select(N.getOperand(0));
1881     BuildMI(BB, PPC::IMPLICIT_DEF, 0,
1882             cast<RegisterSDNode>(N.getOperand(1))->getReg());
1883     return;
1884   case ISD::RET:
1885     switch (N.getNumOperands()) {
1886     default:
1887       assert(0 && "Unknown return instruction!");
1888     case 3:
1889       assert(N.getOperand(1).getValueType() == MVT::i32 &&
1890              N.getOperand(2).getValueType() == MVT::i32 &&
1891              "Unknown two-register value!");
1892       Select(N.getOperand(0));
1893       Tmp1 = SelectExpr(N.getOperand(1));
1894       Tmp2 = SelectExpr(N.getOperand(2));
1895       BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp2).addReg(Tmp2);
1896       BuildMI(BB, PPC::OR, 2, PPC::R4).addReg(Tmp1).addReg(Tmp1);
1897       break;
1898     case 2:
1899       Select(N.getOperand(0));
1900       Tmp1 = SelectExpr(N.getOperand(1));
1901       switch (N.getOperand(1).getValueType()) {
1902         default:
1903           assert(0 && "Unknown return type!");
1904         case MVT::f64:
1905         case MVT::f32:
1906           BuildMI(BB, PPC::FMR, 1, PPC::F1).addReg(Tmp1);
1907           break;
1908         case MVT::i32:
1909           BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp1).addReg(Tmp1);
1910           break;
1911       }
1912     case 1:
1913       Select(N.getOperand(0));
1914       break;
1915     }
1916     BuildMI(BB, PPC::BLR, 0); // Just emit a 'ret' instruction
1917     return;
1918   case ISD::TRUNCSTORE:
1919   case ISD::STORE: {
1920     SDOperand Chain   = N.getOperand(0);
1921     SDOperand Value   = N.getOperand(1);
1922     SDOperand Address = N.getOperand(2);
1923     Select(Chain);
1924
1925     Tmp1 = SelectExpr(Value); //value
1926
1927     if (opcode == ISD::STORE) {
1928       switch(Value.getValueType()) {
1929       default: assert(0 && "unknown Type in store");
1930       case MVT::i32: Opc = PPC::STW; break;
1931       case MVT::f64: Opc = PPC::STFD; break;
1932       case MVT::f32: Opc = PPC::STFS; break;
1933       }
1934     } else { //ISD::TRUNCSTORE
1935       switch(cast<VTSDNode>(Node->getOperand(4))->getVT()) {
1936       default: assert(0 && "unknown Type in store");
1937       case MVT::i1:
1938       case MVT::i8: Opc  = PPC::STB; break;
1939       case MVT::i16: Opc = PPC::STH; break;
1940       }
1941     }
1942
1943     if(Address.getOpcode() == ISD::FrameIndex) {
1944       Tmp2 = cast<FrameIndexSDNode>(Address)->getIndex();
1945       addFrameReference(BuildMI(BB, Opc, 3).addReg(Tmp1), (int)Tmp2);
1946     } else {
1947       int offset;
1948       switch(SelectAddr(Address, Tmp2, offset)) {
1949       default: assert(0 && "Unhandled return value from SelectAddr");
1950       case 0:   // imm offset, no frame, no index
1951         BuildMI(BB, Opc, 3).addReg(Tmp1).addSImm(offset).addReg(Tmp2);
1952         break;
1953       case 1:   // imm offset + frame index
1954         addFrameReference(BuildMI(BB, Opc, 3).addReg(Tmp1), (int)Tmp2, offset);
1955         break;
1956       case 2:   // base+index addressing
1957         Opc = IndexedOpForOp(Opc);
1958         BuildMI(BB, Opc, 3).addReg(Tmp1).addReg(Tmp2).addReg(offset);
1959         break;
1960       case 3: {
1961         GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(Address);
1962         GlobalValue *GV = GN->getGlobal();
1963         BuildMI(BB, Opc, 3).addReg(Tmp1).addGlobalAddress(GV).addReg(Tmp2);
1964       }
1965       }
1966     }
1967     return;
1968   }
1969   case ISD::EXTLOAD:
1970   case ISD::SEXTLOAD:
1971   case ISD::ZEXTLOAD:
1972   case ISD::LOAD:
1973   case ISD::CopyFromReg:
1974   case ISD::TAILCALL:
1975   case ISD::CALL:
1976   case ISD::DYNAMIC_STACKALLOC:
1977     ExprMap.erase(N);
1978     SelectExpr(N);
1979     return;
1980   }
1981   assert(0 && "Should not be reached!");
1982 }
1983
1984
1985 /// createPPC32PatternInstructionSelector - This pass converts an LLVM function
1986 /// into a machine code representation using pattern matching and a machine
1987 /// description file.
1988 ///
1989 FunctionPass *llvm::createPPC32ISelPattern(TargetMachine &TM) {
1990   return new ISel(TM);
1991 }
1992