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).addReg(PPC::LR);
 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   BuildMI(BB, GPOpt ? PPC::MFOCRF : PPC::MFCR, 1, IntCR).addReg(PPC::CR7);
 473   if (Inv) {
 474     unsigned Tmp1 = MakeIntReg();
 475     BuildMI(BB, PPC::RLWINM, 4, Tmp1).addReg(IntCR).addImm(32-(3-Idx))
 476       .addImm(31).addImm(31);
 477     BuildMI(BB, PPC::XORI, 2, Result).addReg(Tmp1).addImm(1);
 478   } else {
 479     BuildMI(BB, PPC::RLWINM, 4, Result).addReg(IntCR).addImm(32-(3-Idx))
 480       .addImm(31).addImm(31);
 481   }
 482 }
 483
 484 /// SelectBitfieldInsert - turn an or of two masked values into
 485 /// the rotate left word immediate then mask insert (rlwimi) instruction.
 486 /// Returns true on success, false if the caller still needs to select OR.
 487 ///
 488 /// Patterns matched:
 489 /// 1. or shl, and   5. or and, and
 490 /// 2. or and, shl   6. or shl, shr
 491 /// 3. or shr, and   7. or shr, shl
 492 /// 4. or and, shr
 493 bool ISel::SelectBitfieldInsert(SDOperand OR, unsigned Result) {
 494   bool IsRotate = false;
 495   unsigned TgtMask = 0xFFFFFFFF, InsMask = 0xFFFFFFFF, Amount = 0;
 496   unsigned Value;
 497
 498   SDOperand Op0 = OR.getOperand(0);
 499   SDOperand Op1 = OR.getOperand(1);
 500
 501   unsigned Op0Opc = Op0.getOpcode();
 502   unsigned Op1Opc = Op1.getOpcode();
 503
 504   // Verify that we have the correct opcodes
 505   if (ISD::SHL != Op0Opc && ISD::SRL != Op0Opc && ISD::AND != Op0Opc)
 506     return false;
 507   if (ISD::SHL != Op1Opc && ISD::SRL != Op1Opc && ISD::AND != Op1Opc)
 508     return false;
 509
 510   // Generate Mask value for Target
 511   if (isIntImmediate(Op0.getOperand(1), Value)) {
 512     switch(Op0Opc) {
 513     case ISD::SHL: TgtMask <<= Value; break;
 514     case ISD::SRL: TgtMask >>= Value; break;
 515     case ISD::AND: TgtMask &= Value; break;
 516     }
 517   } else {
 518     return false;
 519   }
 520
 521   // Generate Mask value for Insert
 522   if (isIntImmediate(Op1.getOperand(1), Value)) {
 523     switch(Op1Opc) {
 524     case ISD::SHL:
 525       Amount = Value;
 526       InsMask <<= Amount;
 527       if (Op0Opc == ISD::SRL) IsRotate = true;
 528       break;
 529     case ISD::SRL:
 530       Amount = Value;
 531       InsMask >>= Amount;
 532       Amount = 32-Amount;
 533       if (Op0Opc == ISD::SHL) IsRotate = true;
 534       break;
 535     case ISD::AND:
 536       InsMask &= Value;
 537       break;
 538     }
 539   } else {
 540     return false;
 541   }
 542
 543   unsigned Tmp3 = 0;
 544
 545   // If both of the inputs are ANDs and one of them has a logical shift by
 546   // constant as its input, make that the inserted value so that we can combine
 547   // the shift into the rotate part of the rlwimi instruction
 548   if (Op0Opc == ISD::AND && Op1Opc == ISD::AND) {
 549     if (Op1.getOperand(0).getOpcode() == ISD::SHL ||
 550         Op1.getOperand(0).getOpcode() == ISD::SRL) {
 551       if (isIntImmediate(Op1.getOperand(0).getOperand(1), Value)) {
 552         Amount = Op1.getOperand(0).getOpcode() == ISD::SHL ?
 553           Value : 32 - Value;
 554         Tmp3 = SelectExpr(Op1.getOperand(0).getOperand(0));
 555       }
 556     } else if (Op0.getOperand(0).getOpcode() == ISD::SHL ||
 557                Op0.getOperand(0).getOpcode() == ISD::SRL) {
 558       if (isIntImmediate(Op0.getOperand(0).getOperand(1), Value)) {
 559         std::swap(Op0, Op1);
 560         std::swap(TgtMask, InsMask);
 561         Amount = Op1.getOperand(0).getOpcode() == ISD::SHL ?
 562           Value : 32 - Value;
 563         Tmp3 = SelectExpr(Op1.getOperand(0).getOperand(0));
 564       }
 565     }
 566   }
 567
 568   // Verify that the Target mask and Insert mask together form a full word mask
 569   // and that the Insert mask is a run of set bits (which implies both are runs
 570   // of set bits).  Given that, Select the arguments and generate the rlwimi
 571   // instruction.
 572   unsigned MB, ME;
 573   if (((TgtMask & InsMask) == 0) && isRunOfOnes(InsMask, MB, ME)) {
 574     unsigned Tmp1, Tmp2;
 575     bool fullMask = (TgtMask ^ InsMask) == 0xFFFFFFFF;
 576     // Check for rotlwi / rotrwi here, a special case of bitfield insert
 577     // where both bitfield halves are sourced from the same value.
 578     if (IsRotate && fullMask &&
 579         OR.getOperand(0).getOperand(0) == OR.getOperand(1).getOperand(0)) {
 580       Tmp1 = SelectExpr(OR.getOperand(0).getOperand(0));
 581       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(Amount)
 582         .addImm(0).addImm(31);
 583       return true;
 584     }
 585     if (Op0Opc == ISD::AND && fullMask)
 586       Tmp1 = SelectExpr(Op0.getOperand(0));
 587     else
 588       Tmp1 = SelectExpr(Op0);
 589     Tmp2 = Tmp3 ? Tmp3 : SelectExpr(Op1.getOperand(0));
 590     BuildMI(BB, PPC::RLWIMI, 5, Result).addReg(Tmp1).addReg(Tmp2)
 591       .addImm(Amount).addImm(MB).addImm(ME);
 592     return true;
 593   }
 594   return false;
 595 }
 596
 597 /// FoldIfWideZeroExtend - 32 bit PowerPC implicit masks shift amounts to the
 598 /// low six bits.  If the shift amount is an ISD::AND node with a mask that is
 599 /// wider than the implicit mask, then we can get rid of the AND and let the
 600 /// shift do the mask.
 601 unsigned ISel::FoldIfWideZeroExtend(SDOperand N) {
 602   unsigned C;
 603   if (isOpcWithIntImmediate(N, ISD::AND, C) && isMask_32(C) && C > 63)
 604     return SelectExpr(N.getOperand(0));
 605   else
 606     return SelectExpr(N);
 607 }
 608
 609 unsigned ISel::SelectCC(SDOperand LHS, SDOperand RHS, ISD::CondCode CC) {
 610   unsigned Result, Tmp1, Tmp2;
 611   bool AlreadySelected = false;
 612   static const unsigned CompareOpcodes[] =
 613     { PPC::FCMPU, PPC::FCMPU, PPC::CMPW, PPC::CMPLW };
 614
 615   // Allocate a condition register for this expression
 616   Result = RegMap->createVirtualRegister(PPC32::CRRCRegisterClass);
 617
 618   // Use U to determine whether the SETCC immediate range is signed or not.
 619   bool U = ISD::isUnsignedIntSetCC(CC);
 620   if (isIntImmediate(RHS, Tmp2) &&
 621       ((U && isUInt16(Tmp2)) || (!U && isInt16(Tmp2)))) {
 622     Tmp2 = Lo16(Tmp2);
 623     // For comparisons against zero, we can implicity set CR0 if a recording
 624     // variant (e.g. 'or.' instead of 'or') of the instruction that defines
 625     // operand zero of the SetCC node is available.
 626     if (Tmp2 == 0 &&
 627         NodeHasRecordingVariant(LHS.getOpcode()) && LHS.Val->hasOneUse()) {
 628       RecordSuccess = false;
 629       Tmp1 = SelectExpr(LHS, true);
 630       if (RecordSuccess) {
 631         ++Recorded;
 632         BuildMI(BB, PPC::MCRF, 1, Result).addReg(PPC::CR0);
 633         return Result;
 634       }
 635       AlreadySelected = true;
 636     }
 637     // If we could not implicitly set CR0, then emit a compare immediate
 638     // instead.
 639     if (!AlreadySelected) Tmp1 = SelectExpr(LHS);
 640     if (U)
 641       BuildMI(BB, PPC::CMPLWI, 2, Result).addReg(Tmp1).addImm(Tmp2);
 642     else
 643       BuildMI(BB, PPC::CMPWI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
 644   } else {
 645     bool IsInteger = MVT::isInteger(LHS.getValueType());
 646     unsigned CompareOpc = CompareOpcodes[2 * IsInteger + U];
 647     Tmp1 = SelectExpr(LHS);
 648     Tmp2 = SelectExpr(RHS);
 649     BuildMI(BB, CompareOpc, 2, Result).addReg(Tmp1).addReg(Tmp2);
 650   }
 651   return Result;
 652 }
 653
 654 /// Check to see if the load is a constant offset from a base register.
 655 unsigned ISel::SelectAddr(SDOperand N, unsigned& Reg, int& offset)
 656 {
 657   unsigned imm = 0, opcode = N.getOpcode();
 658   if (N.getOpcode() == ISD::ADD) {
 659     bool isFrame = N.getOperand(0).getOpcode() == ISD::FrameIndex;
 660     if (isIntImmediate(N.getOperand(1), imm) && isInt16(imm)) {
 661       offset = Lo16(imm);
 662       if (isFrame) {
 663         ++FrameOff;
 664         Reg = cast<FrameIndexSDNode>(N.getOperand(0))->getIndex();
 665         return 1;
 666       } else {
 667         Reg = SelectExpr(N.getOperand(0));
 668         return 0;
 669       }
 670     } else {
 671       Reg = SelectExpr(N.getOperand(0));
 672       offset = SelectExpr(N.getOperand(1));
 673       return 2;
 674     }
 675   }
 676   // Now check if we're dealing with a global, and whether or not we should emit
 677   // an optimized load or store for statics.
 678   if(GlobalAddressSDNode *GN = dyn_cast<GlobalAddressSDNode>(N)) {
 679     GlobalValue *GV = GN->getGlobal();
 680     if (!GV->hasWeakLinkage() && !GV->isExternal()) {
 681       unsigned GlobalHi = MakeIntReg();
 682       if (PICEnabled)
 683         BuildMI(BB, PPC::ADDIS, 2, GlobalHi).addReg(getGlobalBaseReg())
 684           .addGlobalAddress(GV);
 685       else
 686         BuildMI(BB, PPC::LIS, 1, GlobalHi).addGlobalAddress(GV);
 687       Reg = GlobalHi;
 688       offset = 0;
 689       return 3;
 690     }
 691   }
 692   Reg = SelectExpr(N);
 693   offset = 0;
 694   return 0;
 695 }
 696
 697 void ISel::SelectBranchCC(SDOperand N)
 698 {
 699   MachineBasicBlock *Dest =
 700     cast<BasicBlockSDNode>(N.getOperand(4))->getBasicBlock();
 701
 702   Select(N.getOperand(0));  //chain
 703   ISD::CondCode CC = cast<CondCodeSDNode>(N.getOperand(1))->get();
 704   unsigned CCReg = SelectCC(N.getOperand(2), N.getOperand(3), CC);
 705   unsigned Opc = getBCCForSetCC(CC);
 706
 707   // Iterate to the next basic block
 708   ilist<MachineBasicBlock>::iterator It = BB;
 709   ++It;
 710
 711   // If this is a two way branch, then grab the fallthrough basic block argument
 712   // and build a PowerPC branch pseudo-op, suitable for long branch conversion
 713   // if necessary by the branch selection pass.  Otherwise, emit a standard
 714   // conditional branch.
 715   if (N.getOpcode() == ISD::BRTWOWAY_CC) {
 716     MachineBasicBlock *Fallthrough =
 717       cast<BasicBlockSDNode>(N.getOperand(5))->getBasicBlock();
 718     if (Dest != It) {
 719       BuildMI(BB, PPC::COND_BRANCH, 4).addReg(CCReg).addImm(Opc)
 720         .addMBB(Dest).addMBB(Fallthrough);
 721       if (Fallthrough != It)
 722         BuildMI(BB, PPC::B, 1).addMBB(Fallthrough);
 723     } else {
 724       if (Fallthrough != It) {
 725         Opc = PPC32InstrInfo::invertPPCBranchOpcode(Opc);
 726         BuildMI(BB, PPC::COND_BRANCH, 4).addReg(CCReg).addImm(Opc)
 727           .addMBB(Fallthrough).addMBB(Dest);
 728       }
 729     }
 730   } else {
 731     // If the fallthrough path is off the end of the function, which would be
 732     // undefined behavior, set it to be the same as the current block because
 733     // we have nothing better to set it to, and leaving it alone will cause the
 734     // PowerPC Branch Selection pass to crash.
 735     if (It == BB->getParent()->end()) It = Dest;
 736     BuildMI(BB, PPC::COND_BRANCH, 4).addReg(CCReg).addImm(Opc)
 737       .addMBB(Dest).addMBB(It);
 738   }
 739   return;
 740 }
 741
 742 // SelectIntImmediateExpr - Choose code for opcodes with immediate value.
 743 bool ISel::SelectIntImmediateExpr(SDOperand N, unsigned Result,
 744                                   unsigned OCHi, unsigned OCLo,
 745                                   bool IsArithmetic, bool Negate) {
 746   // check constant
 747   ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1));
 748   // exit if not a constant
 749   if (!CN) return false;
 750   // extract immediate
 751   unsigned C = (unsigned)CN->getValue();
 752   // negate if required (ISD::SUB)
 753   if (Negate) C = -C;
 754   // get the hi and lo portions of constant
 755   unsigned Hi = IsArithmetic ? HA16(C) : Hi16(C);
 756   unsigned Lo = Lo16(C);
 757   // assume no intermediate result from lo instruction (same as final result)
 758   unsigned Tmp = Result;
 759   // check if two instructions are needed
 760   if (Hi && Lo) {
 761     // exit if usage indicates it would be better to load immediate into a
 762     // register
 763     if (CN->use_size() > 2) return false;
 764     // need intermediate result for two instructions
 765     Tmp = MakeIntReg();
 766   }
 767   // get first operand
 768   unsigned Opr0 = SelectExpr(N.getOperand(0));
 769   // is a lo instruction needed
 770   if (Lo) {
 771     // generate instruction for lo portion
 772     BuildMI(BB, OCLo, 2, Tmp).addReg(Opr0).addImm(Lo);
 773     // need to switch out first operand for hi instruction
 774     Opr0 = Tmp;
 775   }
 776   // is a hi instruction needed
 777   if (Hi) {
 778     // generate instruction for hi portion
 779     BuildMI(BB, OCHi, 2, Result).addReg(Opr0).addImm(Hi);
 780   }
 781   return true;
 782 }
 783
 784 unsigned ISel::SelectExpr(SDOperand N, bool Recording) {
 785   unsigned Result;
 786   unsigned Tmp1, Tmp2, Tmp3;
 787   unsigned Opc = 0;
 788   unsigned opcode = N.getOpcode();
 789
 790   SDNode *Node = N.Val;
 791   MVT::ValueType DestType = N.getValueType();
 792
 793   if (Node->getOpcode() == ISD::CopyFromReg) {
 794     unsigned Reg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
 795     // Just use the specified register as our input.
 796     if (MRegisterInfo::isVirtualRegister(Reg) || Reg == PPC::R1)
 797       return Reg;
 798   }
 799
 800   unsigned &Reg = ExprMap[N];
 801   if (Reg) return Reg;
 802
 803   switch (N.getOpcode()) {
 804   default:
 805     Reg = Result = (N.getValueType() != MVT::Other) ?
 806                             MakeReg(N.getValueType()) : 1;
 807     break;
 808   case ISD::TAILCALL:
 809   case ISD::CALL:
 810     // If this is a call instruction, make sure to prepare ALL of the result
 811     // values as well as the chain.
 812     if (Node->getNumValues() == 1)
 813       Reg = Result = 1;  // Void call, just a chain.
 814     else {
 815       Result = MakeReg(Node->getValueType(0));
 816       ExprMap[N.getValue(0)] = Result;
 817       for (unsigned i = 1, e = N.Val->getNumValues()-1; i != e; ++i)
 818         ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
 819       ExprMap[SDOperand(Node, Node->getNumValues()-1)] = 1;
 820     }
 821     break;
 822   case ISD::ADD_PARTS:
 823   case ISD::SUB_PARTS:
 824   case ISD::SHL_PARTS:
 825   case ISD::SRL_PARTS:
 826   case ISD::SRA_PARTS:
 827     Result = MakeReg(Node->getValueType(0));
 828     ExprMap[N.getValue(0)] = Result;
 829     for (unsigned i = 1, e = N.Val->getNumValues(); i != e; ++i)
 830       ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
 831     break;
 832   }
 833
 834   switch (opcode) {
 835   default:
 836     Node->dump(); std::cerr << '\n';
 837     assert(0 && "Node not handled!\n");
 838   case ISD::UNDEF:
 839     BuildMI(BB, PPC::IMPLICIT_DEF, 0, Result);
 840     return Result;
 841   case ISD::DYNAMIC_STACKALLOC:
 842     // Generate both result values.  FIXME: Need a better commment here?
 843     if (Result != 1)
 844       ExprMap[N.getValue(1)] = 1;
 845     else
 846       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 847
 848     // FIXME: We are currently ignoring the requested alignment for handling
 849     // greater than the stack alignment.  This will need to be revisited at some
 850     // point.  Align = N.getOperand(2);
 851     if (!isa<ConstantSDNode>(N.getOperand(2)) ||
 852         cast<ConstantSDNode>(N.getOperand(2))->getValue() != 0) {
 853       std::cerr << "Cannot allocate stack object with greater alignment than"
 854                 << " the stack alignment yet!";
 855       abort();
 856     }
 857     Select(N.getOperand(0));
 858     Tmp1 = SelectExpr(N.getOperand(1));
 859     // Subtract size from stack pointer, thereby allocating some space.
 860     BuildMI(BB, PPC::SUBF, 2, PPC::R1).addReg(Tmp1).addReg(PPC::R1);
 861     // Put a pointer to the space into the result register by copying the SP
 862     BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R1).addReg(PPC::R1);
 863     return Result;
 864
 865   case ISD::ConstantPool:
 866     Tmp1 = cast<ConstantPoolSDNode>(N)->getIndex();
 867     Tmp2 = MakeIntReg();
 868     if (PICEnabled)
 869       BuildMI(BB, PPC::ADDIS, 2, Tmp2).addReg(getGlobalBaseReg())
 870         .addConstantPoolIndex(Tmp1);
 871     else
 872       BuildMI(BB, PPC::LIS, 1, Tmp2).addConstantPoolIndex(Tmp1);
 873     BuildMI(BB, PPC::LA, 2, Result).addReg(Tmp2).addConstantPoolIndex(Tmp1);
 874     return Result;
 875
 876   case ISD::FrameIndex:
 877     Tmp1 = cast<FrameIndexSDNode>(N)->getIndex();
 878     addFrameReference(BuildMI(BB, PPC::ADDI, 2, Result), (int)Tmp1, 0, false);
 879     return Result;
 880
 881   case ISD::GlobalAddress: {
 882     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
 883     Tmp1 = MakeIntReg();
 884     if (PICEnabled)
 885       BuildMI(BB, PPC::ADDIS, 2, Tmp1).addReg(getGlobalBaseReg())
 886         .addGlobalAddress(GV);
 887     else
 888       BuildMI(BB, PPC::LIS, 1, Tmp1).addGlobalAddress(GV);
 889     if (GV->hasWeakLinkage() || GV->isExternal()) {
 890       BuildMI(BB, PPC::LWZ, 2, Result).addGlobalAddress(GV).addReg(Tmp1);
 891     } else {
 892       BuildMI(BB, PPC::LA, 2, Result).addReg(Tmp1).addGlobalAddress(GV);
 893     }
 894     return Result;
 895   }
 896
 897   case ISD::LOAD:
 898   case ISD::EXTLOAD:
 899   case ISD::ZEXTLOAD:
 900   case ISD::SEXTLOAD: {
 901     MVT::ValueType TypeBeingLoaded = (ISD::LOAD == opcode) ?
 902       Node->getValueType(0) : cast<VTSDNode>(Node->getOperand(3))->getVT();
 903     bool sext = (ISD::SEXTLOAD == opcode);
 904
 905     // Make sure we generate both values.
 906     if (Result != 1)
 907       ExprMap[N.getValue(1)] = 1;   // Generate the token
 908     else
 909       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 910
 911     SDOperand Chain   = N.getOperand(0);
 912     SDOperand Address = N.getOperand(1);
 913     Select(Chain);
 914
 915     switch (TypeBeingLoaded) {
 916     default: Node->dump(); assert(0 && "Cannot load this type!");
 917     case MVT::i1:  Opc = PPC::LBZ; break;
 918     case MVT::i8:  Opc = PPC::LBZ; break;
 919     case MVT::i16: Opc = sext ? PPC::LHA : PPC::LHZ; break;
 920     case MVT::i32: Opc = PPC::LWZ; break;
 921     case MVT::f32: Opc = PPC::LFS; break;
 922     case MVT::f64: Opc = PPC::LFD; break;
 923     }
 924
 925     if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Address)) {
 926       Tmp1 = MakeIntReg();
 927       int CPI = CP->getIndex();
 928       if (PICEnabled)
 929         BuildMI(BB, PPC::ADDIS, 2, Tmp1).addReg(getGlobalBaseReg())
 930           .addConstantPoolIndex(CPI);
 931       else
 932         BuildMI(BB, PPC::LIS, 1, Tmp1).addConstantPoolIndex(CPI);
 933       BuildMI(BB, Opc, 2, Result).addConstantPoolIndex(CPI).addReg(Tmp1);
 934     } else if (Address.getOpcode() == ISD::FrameIndex) {
 935       Tmp1 = cast<FrameIndexSDNode>(Address)->getIndex();
 936       addFrameReference(BuildMI(BB, Opc, 2, Result), (int)Tmp1);
 937     } else {
 938       int offset;
 939       switch(SelectAddr(Address, Tmp1, offset)) {
 940       default: assert(0 && "Unhandled return value from SelectAddr");
 941       case 0:   // imm offset, no frame, no index
 942         BuildMI(BB, Opc, 2, Result).addSImm(offset).addReg(Tmp1);
 943         break;
 944       case 1:   // imm offset + frame index
 945         addFrameReference(BuildMI(BB, Opc, 2, Result), (int)Tmp1, offset);
 946         break;
 947       case 2:   // base+index addressing
 948         Opc = IndexedOpForOp(Opc);
 949         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(offset);
 950         break;
 951       case 3: {
 952         GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(Address);
 953         GlobalValue *GV = GN->getGlobal();
 954         BuildMI(BB, Opc, 2, Result).addGlobalAddress(GV).addReg(Tmp1);
 955       }
 956       }
 957     }
 958     return Result;
 959   }
 960
 961   case ISD::TAILCALL:
 962   case ISD::CALL: {
 963     unsigned GPR_idx = 0, FPR_idx = 0;
 964     static const unsigned GPR[] = {
 965       PPC::R3, PPC::R4, PPC::R5, PPC::R6,
 966       PPC::R7, PPC::R8, PPC::R9, PPC::R10,
 967     };
 968     static const unsigned FPR[] = {
 969       PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
 970       PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
 971     };
 972
 973     // Lower the chain for this call.
 974     Select(N.getOperand(0));
 975     ExprMap[N.getValue(Node->getNumValues()-1)] = 1;
 976
 977     MachineInstr *CallMI;
 978     // Emit the correct call instruction based on the type of symbol called.
 979     if (GlobalAddressSDNode *GASD =
 980         dyn_cast<GlobalAddressSDNode>(N.getOperand(1))) {
 981       CallMI = BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(GASD->getGlobal(),
 982                                                            true);
 983     } else if (ExternalSymbolSDNode *ESSDN =
 984                dyn_cast<ExternalSymbolSDNode>(N.getOperand(1))) {
 985       CallMI = BuildMI(PPC::CALLpcrel, 1).addExternalSymbol(ESSDN->getSymbol(),
 986                                                             true);
 987     } else {
 988       Tmp1 = SelectExpr(N.getOperand(1));
 989       BuildMI(BB, PPC::OR, 2, PPC::R12).addReg(Tmp1).addReg(Tmp1);
 990       BuildMI(BB, PPC::MTCTR, 1).addReg(PPC::R12);
 991       CallMI = BuildMI(PPC::CALLindirect, 3).addImm(20).addImm(0)
 992         .addReg(PPC::R12);
 993     }
 994
 995     // Load the register args to virtual regs
 996     std::vector<unsigned> ArgVR;
 997     for(int i = 2, e = Node->getNumOperands(); i < e; ++i)
 998       ArgVR.push_back(SelectExpr(N.getOperand(i)));
 999
1000     // Copy the virtual registers into the appropriate argument register
1001     for(int i = 0, e = ArgVR.size(); i < e; ++i) {
1002       switch(N.getOperand(i+2).getValueType()) {
1003       default: Node->dump(); assert(0 && "Unknown value type for call");
1004       case MVT::i1:
1005       case MVT::i8:
1006       case MVT::i16:
1007       case MVT::i32:
1008         assert(GPR_idx < 8 && "Too many int args");
1009         if (N.getOperand(i+2).getOpcode() != ISD::UNDEF) {
1010           BuildMI(BB, PPC::OR,2,GPR[GPR_idx]).addReg(ArgVR[i]).addReg(ArgVR[i]);
1011           CallMI->addRegOperand(GPR[GPR_idx], MachineOperand::Use);
1012         }
1013         ++GPR_idx;
1014         break;
1015       case MVT::f64:
1016       case MVT::f32:
1017         assert(FPR_idx < 13 && "Too many fp args");
1018         BuildMI(BB, PPC::FMR, 1, FPR[FPR_idx]).addReg(ArgVR[i]);
1019         CallMI->addRegOperand(FPR[FPR_idx], MachineOperand::Use);
1020         ++FPR_idx;
1021         break;
1022       }
1023     }
1024
1025     // Put the call instruction in the correct place in the MachineBasicBlock
1026     BB->push_back(CallMI);
1027
1028     switch (Node->getValueType(0)) {
1029     default: assert(0 && "Unknown value type for call result!");
1030     case MVT::Other: return 1;
1031     case MVT::i1:
1032     case MVT::i8:
1033     case MVT::i16:
1034     case MVT::i32:
1035       if (Node->getValueType(1) == MVT::i32) {
1036         BuildMI(BB, PPC::OR, 2, Result+1).addReg(PPC::R3).addReg(PPC::R3);
1037         BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R4).addReg(PPC::R4);
1038       } else {
1039         BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R3).addReg(PPC::R3);
1040       }
1041       break;
1042     case MVT::f32:
1043     case MVT::f64:
1044       BuildMI(BB, PPC::FMR, 1, Result).addReg(PPC::F1);
1045       break;
1046     }
1047     return Result+N.ResNo;
1048   }
1049
1050   case ISD::SIGN_EXTEND:
1051   case ISD::SIGN_EXTEND_INREG:
1052     Tmp1 = SelectExpr(N.getOperand(0));
1053     switch(cast<VTSDNode>(Node->getOperand(1))->getVT()) {
1054     default: Node->dump(); assert(0 && "Unhandled SIGN_EXTEND type"); break;
1055     case MVT::i16:
1056       BuildMI(BB, PPC::EXTSH, 1, Result).addReg(Tmp1);
1057       break;
1058     case MVT::i8:
1059       BuildMI(BB, PPC::EXTSB, 1, Result).addReg(Tmp1);
1060       break;
1061     case MVT::i1:
1062       BuildMI(BB, PPC::SUBFIC, 2, Result).addReg(Tmp1).addSImm(0);
1063       break;
1064     }
1065     return Result;
1066
1067   case ISD::CopyFromReg:
1068     DestType = N.getValue(0).getValueType();
1069     if (Result == 1)
1070       Result = ExprMap[N.getValue(0)] = MakeReg(DestType);
1071     Tmp1 = dyn_cast<RegisterSDNode>(Node->getOperand(1))->getReg();
1072     if (MVT::isInteger(DestType))
1073       BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp1).addReg(Tmp1);
1074     else
1075       BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
1076     return Result;
1077
1078   case ISD::SHL:
1079     if (isIntImmediate(N.getOperand(1), Tmp2)) {
1080       unsigned SH, MB, ME;
1081       if (isOpcWithIntImmediate(N.getOperand(0), ISD::AND, Tmp3) &&
1082           isRotateAndMask(ISD::SHL, Tmp2, Tmp3, true, SH, MB, ME)) {
1083         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1084         BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(SH)
1085           .addImm(MB).addImm(ME);
1086         return Result;
1087       }
1088       Tmp1 = SelectExpr(N.getOperand(0));
1089       Tmp2 &= 0x1F;
1090       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(Tmp2).addImm(0)
1091         .addImm(31-Tmp2);
1092     } else {
1093       Tmp1 = SelectExpr(N.getOperand(0));
1094       Tmp2 = FoldIfWideZeroExtend(N.getOperand(1));
1095       BuildMI(BB, PPC::SLW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1096     }
1097     return Result;
1098
1099   case ISD::SRL:
1100     if (isIntImmediate(N.getOperand(1), Tmp2)) {
1101       unsigned SH, MB, ME;
1102       if (isOpcWithIntImmediate(N.getOperand(0), ISD::AND, Tmp3) &&
1103           isRotateAndMask(ISD::SRL, Tmp2, Tmp3, true, SH, MB, ME)) {
1104         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1105         BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(SH)
1106           .addImm(MB).addImm(ME);
1107         return Result;
1108       }
1109       Tmp1 = SelectExpr(N.getOperand(0));
1110       Tmp2 &= 0x1F;
1111       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(32-Tmp2)
1112         .addImm(Tmp2).addImm(31);
1113     } else {
1114       Tmp1 = SelectExpr(N.getOperand(0));
1115       Tmp2 = FoldIfWideZeroExtend(N.getOperand(1));
1116       BuildMI(BB, PPC::SRW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1117     }
1118     return Result;
1119
1120   case ISD::SRA:
1121     if (isIntImmediate(N.getOperand(1), Tmp2)) {
1122       unsigned SH, MB, ME;
1123       if (isOpcWithIntImmediate(N.getOperand(0), ISD::AND, Tmp3) &&
1124           isRotateAndMask(ISD::SRA, Tmp2, Tmp3, true, SH, MB, ME)) {
1125         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1126         BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(SH)
1127           .addImm(MB).addImm(ME);
1128         return Result;
1129       }
1130       Tmp1 = SelectExpr(N.getOperand(0));
1131       Tmp2 &= 0x1F;
1132       BuildMI(BB, PPC::SRAWI, 2, Result).addReg(Tmp1).addImm(Tmp2);
1133     } else {
1134       Tmp1 = SelectExpr(N.getOperand(0));
1135       Tmp2 = FoldIfWideZeroExtend(N.getOperand(1));
1136       BuildMI(BB, PPC::SRAW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1137     }
1138     return Result;
1139
1140   case ISD::CTLZ:
1141     Tmp1 = SelectExpr(N.getOperand(0));
1142     BuildMI(BB, PPC::CNTLZW, 1, Result).addReg(Tmp1);
1143     return Result;
1144
1145   case ISD::ADD:
1146     if (!MVT::isInteger(DestType)) {
1147       if (!NoExcessFPPrecision && N.getOperand(0).getOpcode() == ISD::MUL &&
1148           N.getOperand(0).Val->hasOneUse()) {
1149         ++FusedFP; // Statistic
1150         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1151         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1152         Tmp3 = SelectExpr(N.getOperand(1));
1153         Opc = DestType == MVT::f64 ? PPC::FMADD : PPC::FMADDS;
1154         BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1155         return Result;
1156       }
1157       if (!NoExcessFPPrecision && N.getOperand(1).getOpcode() == ISD::MUL &&
1158           N.getOperand(1).Val->hasOneUse()) {
1159         ++FusedFP; // Statistic
1160         Tmp1 = SelectExpr(N.getOperand(1).getOperand(0));
1161         Tmp2 = SelectExpr(N.getOperand(1).getOperand(1));
1162         Tmp3 = SelectExpr(N.getOperand(0));
1163         Opc = DestType == MVT::f64 ? PPC::FMADD : PPC::FMADDS;
1164         BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1165         return Result;
1166       }
1167       Opc = DestType == MVT::f64 ? PPC::FADD : PPC::FADDS;
1168       Tmp1 = SelectExpr(N.getOperand(0));
1169       Tmp2 = SelectExpr(N.getOperand(1));
1170       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1171       return Result;
1172     }
1173     if (SelectIntImmediateExpr(N, Result, PPC::ADDIS, PPC::ADDI, true))
1174       return Result;
1175     Tmp1 = SelectExpr(N.getOperand(0));
1176     Tmp2 = SelectExpr(N.getOperand(1));
1177     BuildMI(BB, PPC::ADD, 2, Result).addReg(Tmp1).addReg(Tmp2);
1178     return Result;
1179
1180   case ISD::AND:
1181     if (isIntImmediate(N.getOperand(1), Tmp2)) {
1182       if (isShiftedMask_32(Tmp2) || isShiftedMask_32(~Tmp2)) {
1183         unsigned SH, MB, ME;
1184         Opc = Recording ? PPC::RLWINMo : PPC::RLWINM;
1185         unsigned OprOpc;
1186         if (isOprShiftImm(N.getOperand(0), OprOpc, Tmp3) &&
1187             isRotateAndMask(OprOpc, Tmp3, Tmp2, false, SH, MB, ME)) {
1188           Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1189         } else {
1190           Tmp1 = SelectExpr(N.getOperand(0));
1191           isRunOfOnes(Tmp2, MB, ME);
1192           SH = 0;
1193         }
1194         BuildMI(BB, Opc, 4, Result).addReg(Tmp1).addImm(SH)
1195           .addImm(MB).addImm(ME);
1196         RecordSuccess = true;
1197         return Result;
1198       } else if (isUInt16(Tmp2)) {
1199         Tmp2 = Lo16(Tmp2);
1200         Tmp1 = SelectExpr(N.getOperand(0));
1201         BuildMI(BB, PPC::ANDIo, 2, Result).addReg(Tmp1).addImm(Tmp2);
1202         RecordSuccess = true;
1203         return Result;
1204       } else if (isUInt16(Tmp2)) {
1205         Tmp2 = Hi16(Tmp2);
1206         Tmp1 = SelectExpr(N.getOperand(0));
1207         BuildMI(BB, PPC::ANDISo, 2, Result).addReg(Tmp1).addImm(Tmp2);
1208         RecordSuccess = true;
1209        return Result;
1210       }
1211     }
1212     if (isOprNot(N.getOperand(1))) {
1213       Tmp1 = SelectExpr(N.getOperand(0));
1214       Tmp2 = SelectExpr(N.getOperand(1).getOperand(0));
1215       BuildMI(BB, PPC::ANDC, 2, Result).addReg(Tmp1).addReg(Tmp2);
1216       RecordSuccess = false;
1217       return Result;
1218     }
1219     if (isOprNot(N.getOperand(0))) {
1220       Tmp1 = SelectExpr(N.getOperand(1));
1221       Tmp2 = SelectExpr(N.getOperand(0).getOperand(0));
1222       BuildMI(BB, PPC::ANDC, 2, Result).addReg(Tmp1).addReg(Tmp2);
1223       RecordSuccess = false;
1224       return Result;
1225     }
1226     // emit a regular and
1227     Tmp1 = SelectExpr(N.getOperand(0));
1228     Tmp2 = SelectExpr(N.getOperand(1));
1229     Opc = Recording ? PPC::ANDo : PPC::AND;
1230     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1231     RecordSuccess = true;
1232     return Result;
1233
1234   case ISD::OR:
1235     if (SelectBitfieldInsert(N, Result))
1236       return Result;
1237     if (SelectIntImmediateExpr(N, Result, PPC::ORIS, PPC::ORI))
1238       return Result;
1239     if (isOprNot(N.getOperand(1))) {
1240       Tmp1 = SelectExpr(N.getOperand(0));
1241       Tmp2 = SelectExpr(N.getOperand(1).getOperand(0));
1242       BuildMI(BB, PPC::ORC, 2, Result).addReg(Tmp1).addReg(Tmp2);
1243       RecordSuccess = false;
1244       return Result;
1245     }
1246     if (isOprNot(N.getOperand(0))) {
1247       Tmp1 = SelectExpr(N.getOperand(1));
1248       Tmp2 = SelectExpr(N.getOperand(0).getOperand(0));
1249       BuildMI(BB, PPC::ORC, 2, Result).addReg(Tmp1).addReg(Tmp2);
1250       RecordSuccess = false;
1251       return Result;
1252     }
1253     // emit regular or
1254     Tmp1 = SelectExpr(N.getOperand(0));
1255     Tmp2 = SelectExpr(N.getOperand(1));
1256     Opc = Recording ? PPC::ORo : PPC::OR;
1257     RecordSuccess = true;
1258     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1259     return Result;
1260
1261   case ISD::XOR: {
1262     // Check for EQV: xor, (xor a, -1), b
1263     if (isOprNot(N.getOperand(0))) {
1264       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1265       Tmp2 = SelectExpr(N.getOperand(1));
1266       BuildMI(BB, PPC::EQV, 2, Result).addReg(Tmp1).addReg(Tmp2);
1267       return Result;
1268     }
1269     // Check for NOT, NOR, EQV, and NAND: xor (copy, or, xor, and), -1
1270     if (isOprNot(N)) {
1271       switch(N.getOperand(0).getOpcode()) {
1272       case ISD::OR:
1273         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1274         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1275         BuildMI(BB, PPC::NOR, 2, Result).addReg(Tmp1).addReg(Tmp2);
1276         break;
1277       case ISD::AND:
1278         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1279         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1280         BuildMI(BB, PPC::NAND, 2, Result).addReg(Tmp1).addReg(Tmp2);
1281         break;
1282       case ISD::XOR:
1283         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1284         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1285         BuildMI(BB, PPC::EQV, 2, Result).addReg(Tmp1).addReg(Tmp2);
1286         break;
1287       default:
1288         Tmp1 = SelectExpr(N.getOperand(0));
1289         BuildMI(BB, PPC::NOR, 2, Result).addReg(Tmp1).addReg(Tmp1);
1290         break;
1291       }
1292       return Result;
1293     }
1294     if (SelectIntImmediateExpr(N, Result, PPC::XORIS, PPC::XORI))
1295       return Result;
1296     // emit regular xor
1297     Tmp1 = SelectExpr(N.getOperand(0));
1298     Tmp2 = SelectExpr(N.getOperand(1));
1299     BuildMI(BB, PPC::XOR, 2, Result).addReg(Tmp1).addReg(Tmp2);
1300     return Result;
1301   }
1302
1303    case ISD::SUB:
1304     if (!MVT::isInteger(DestType)) {
1305       if (!NoExcessFPPrecision && N.getOperand(0).getOpcode() == ISD::MUL &&
1306           N.getOperand(0).Val->hasOneUse()) {
1307         ++FusedFP; // Statistic
1308         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1309         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1310         Tmp3 = SelectExpr(N.getOperand(1));
1311         Opc = DestType == MVT::f64 ? PPC::FMSUB : PPC::FMSUBS;
1312         BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1313         return Result;
1314       }
1315       if (!NoExcessFPPrecision && N.getOperand(1).getOpcode() == ISD::MUL &&
1316           N.getOperand(1).Val->hasOneUse()) {
1317         ++FusedFP; // Statistic
1318         Tmp1 = SelectExpr(N.getOperand(1).getOperand(0));
1319         Tmp2 = SelectExpr(N.getOperand(1).getOperand(1));
1320         Tmp3 = SelectExpr(N.getOperand(0));
1321         Opc = DestType == MVT::f64 ? PPC::FNMSUB : PPC::FNMSUBS;
1322         BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1323         return Result;
1324       }
1325       Opc = DestType == MVT::f64 ? PPC::FSUB : PPC::FSUBS;
1326       Tmp1 = SelectExpr(N.getOperand(0));
1327       Tmp2 = SelectExpr(N.getOperand(1));
1328       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1329       return Result;
1330     }
1331     if (isIntImmediate(N.getOperand(0), Tmp1) && isInt16(Tmp1)) {
1332       Tmp1 = Lo16(Tmp1);
1333       Tmp2 = SelectExpr(N.getOperand(1));
1334       BuildMI(BB, PPC::SUBFIC, 2, Result).addReg(Tmp2).addSImm(Tmp1);
1335       return Result;
1336     }
1337     if (SelectIntImmediateExpr(N, Result, PPC::ADDIS, PPC::ADDI, true, true))
1338         return Result;
1339     Tmp1 = SelectExpr(N.getOperand(0));
1340     Tmp2 = SelectExpr(N.getOperand(1));
1341     BuildMI(BB, PPC::SUBF, 2, Result).addReg(Tmp2).addReg(Tmp1);
1342     return Result;
1343
1344   case ISD::MUL:
1345     Tmp1 = SelectExpr(N.getOperand(0));
1346     if (isIntImmediate(N.getOperand(1), Tmp2) && isInt16(Tmp2)) {
1347       Tmp2 = Lo16(Tmp2);
1348       BuildMI(BB, PPC::MULLI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
1349     } else {
1350       Tmp2 = SelectExpr(N.getOperand(1));
1351       switch (DestType) {
1352       default: assert(0 && "Unknown type to ISD::MUL"); break;
1353       case MVT::i32: Opc = PPC::MULLW; break;
1354       case MVT::f32: Opc = PPC::FMULS; break;
1355       case MVT::f64: Opc = PPC::FMUL; break;
1356       }
1357       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1358     }
1359     return Result;
1360
1361   case ISD::MULHS:
1362   case ISD::MULHU:
1363     Tmp1 = SelectExpr(N.getOperand(0));
1364     Tmp2 = SelectExpr(N.getOperand(1));
1365     Opc = (ISD::MULHU == opcode) ? PPC::MULHWU : PPC::MULHW;
1366     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1367     return Result;
1368
1369   case ISD::SDIV:
1370     if (isIntImmediate(N.getOperand(1), Tmp3)) {
1371       if ((signed)Tmp3 > 0 && isPowerOf2_32(Tmp3)) {
1372         Tmp3 = Log2_32(Tmp3);
1373         Tmp1 = MakeIntReg();
1374         Tmp2 = SelectExpr(N.getOperand(0));
1375         BuildMI(BB, PPC::SRAWI, 2, Tmp1).addReg(Tmp2).addImm(Tmp3);
1376         BuildMI(BB, PPC::ADDZE, 1, Result).addReg(Tmp1);
1377         return Result;
1378       } else if ((signed)Tmp3 < 0 && isPowerOf2_32(-Tmp3)) {
1379         Tmp3 = Log2_32(-Tmp3);
1380         Tmp2 = SelectExpr(N.getOperand(0));
1381         Tmp1 = MakeIntReg();
1382         unsigned Tmp4 = MakeIntReg();
1383         BuildMI(BB, PPC::SRAWI, 2, Tmp1).addReg(Tmp2).addImm(Tmp3);
1384         BuildMI(BB, PPC::ADDZE, 1, Tmp4).addReg(Tmp1);
1385         BuildMI(BB, PPC::NEG, 1, Result).addReg(Tmp4);
1386         return Result;
1387       }
1388     }
1389     // fall thru
1390   case ISD::UDIV:
1391     // If this is a divide by constant, we can emit code using some magic
1392     // constants to implement it as a multiply instead.
1393     if (isIntImmediate(N.getOperand(1), Tmp3)) {
1394       if (opcode == ISD::SDIV) {
1395         if ((signed)Tmp3 < -1 || (signed)Tmp3 > 1) {
1396           ExprMap.erase(N);
1397           return SelectExpr(BuildSDIVSequence(N));
1398         }
1399       } else {
1400         if ((signed)Tmp3 > 1) {
1401           ExprMap.erase(N);
1402           return SelectExpr(BuildUDIVSequence(N));
1403         }
1404       }
1405     }
1406     Tmp1 = SelectExpr(N.getOperand(0));
1407     Tmp2 = SelectExpr(N.getOperand(1));
1408     switch (DestType) {
1409     default: assert(0 && "Unknown type to ISD::SDIV"); break;
1410     case MVT::i32: Opc = (ISD::UDIV == opcode) ? PPC::DIVWU : PPC::DIVW; break;
1411     case MVT::f32: Opc = PPC::FDIVS; break;
1412     case MVT::f64: Opc = PPC::FDIV; break;
1413     }
1414     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1415     return Result;
1416
1417   case ISD::ADD_PARTS:
1418   case ISD::SUB_PARTS: {
1419     assert(N.getNumOperands() == 4 && N.getValueType() == MVT::i32 &&
1420            "Not an i64 add/sub!");
1421     unsigned Tmp4 = 0;
1422     bool ME = isIntImmediate(N.getOperand(3),Tmp3) && ((signed)Tmp3 == -1);
1423     bool ZE = isIntImmediate(N.getOperand(3),Tmp3) && (Tmp3 == 0);
1424     bool IM = isIntImmediate(N.getOperand(2),Tmp3) && ((signed)Tmp3 >= -32768 ||
1425                                                        (signed)Tmp3 <   32768);
1426     Tmp1 = SelectExpr(N.getOperand(0));
1427     Tmp2 = SelectExpr(N.getOperand(1));
1428     if (!IM || N.getOpcode() == ISD::SUB_PARTS)
1429       Tmp3 = SelectExpr(N.getOperand(2));
1430     if ((!ME && !ZE) || N.getOpcode() == ISD::SUB_PARTS)
1431       Tmp4 = SelectExpr(N.getOperand(3));
1432
1433     if (N.getOpcode() == ISD::ADD_PARTS) {
1434       // Codegen the low 32 bits of the add.  Interestingly, there is no shifted
1435       // form of add immediate carrying.
1436       if (IM)
1437         BuildMI(BB, PPC::ADDIC, 2, Result).addReg(Tmp1).addSImm(Tmp3);
1438       else
1439         BuildMI(BB, PPC::ADDC, 2, Result).addReg(Tmp1).addReg(Tmp3);
1440       // Codegen the high 32 bits, adding zero, minus one, or the full value
1441       // along with the carry flag produced by addc/addic to tmp2.
1442       if (ZE)
1443         BuildMI(BB, PPC::ADDZE, 1, Result+1).addReg(Tmp2);
1444       else if (ME)
1445         BuildMI(BB, PPC::ADDME, 1, Result+1).addReg(Tmp2);
1446       else
1447         BuildMI(BB, PPC::ADDE, 2, Result+1).addReg(Tmp2).addReg(Tmp4);
1448     } else {
1449       BuildMI(BB, PPC::SUBFC, 2, Result).addReg(Tmp3).addReg(Tmp1);
1450       BuildMI(BB, PPC::SUBFE, 2, Result+1).addReg(Tmp4).addReg(Tmp2);
1451     }
1452     return Result+N.ResNo;
1453   }
1454
1455   case ISD::SHL_PARTS:
1456   case ISD::SRA_PARTS:
1457   case ISD::SRL_PARTS: {
1458     assert(N.getNumOperands() == 3 && N.getValueType() == MVT::i32 &&
1459            "Not an i64 shift!");
1460     unsigned ShiftOpLo = SelectExpr(N.getOperand(0));
1461     unsigned ShiftOpHi = SelectExpr(N.getOperand(1));
1462     unsigned SHReg = FoldIfWideZeroExtend(N.getOperand(2));
1463     Tmp1 = MakeIntReg();
1464     Tmp2 = MakeIntReg();
1465     Tmp3 = MakeIntReg();
1466     unsigned Tmp4 = MakeIntReg();
1467     unsigned Tmp5 = MakeIntReg();
1468     unsigned Tmp6 = MakeIntReg();
1469     BuildMI(BB, PPC::SUBFIC, 2, Tmp1).addReg(SHReg).addSImm(32);
1470     if (ISD::SHL_PARTS == opcode) {
1471       BuildMI(BB, PPC::SLW, 2, Tmp2).addReg(ShiftOpHi).addReg(SHReg);
1472       BuildMI(BB, PPC::SRW, 2, Tmp3).addReg(ShiftOpLo).addReg(Tmp1);
1473       BuildMI(BB, PPC::OR, 2, Tmp4).addReg(Tmp2).addReg(Tmp3);
1474       BuildMI(BB, PPC::ADDI, 2, Tmp5).addReg(SHReg).addSImm(-32);
1475       BuildMI(BB, PPC::SLW, 2, Tmp6).addReg(ShiftOpLo).addReg(Tmp5);
1476       BuildMI(BB, PPC::OR, 2, Result+1).addReg(Tmp4).addReg(Tmp6);
1477       BuildMI(BB, PPC::SLW, 2, Result).addReg(ShiftOpLo).addReg(SHReg);
1478     } else if (ISD::SRL_PARTS == opcode) {
1479       BuildMI(BB, PPC::SRW, 2, Tmp2).addReg(ShiftOpLo).addReg(SHReg);
1480       BuildMI(BB, PPC::SLW, 2, Tmp3).addReg(ShiftOpHi).addReg(Tmp1);
1481       BuildMI(BB, PPC::OR, 2, Tmp4).addReg(Tmp2).addReg(Tmp3);
1482       BuildMI(BB, PPC::ADDI, 2, Tmp5).addReg(SHReg).addSImm(-32);
1483       BuildMI(BB, PPC::SRW, 2, Tmp6).addReg(ShiftOpHi).addReg(Tmp5);
1484       BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp4).addReg(Tmp6);
1485       BuildMI(BB, PPC::SRW, 2, Result+1).addReg(ShiftOpHi).addReg(SHReg);
1486     } else {
1487       MachineBasicBlock *TmpMBB = new MachineBasicBlock(BB->getBasicBlock());
1488       MachineBasicBlock *PhiMBB = new MachineBasicBlock(BB->getBasicBlock());
1489       MachineBasicBlock *OldMBB = BB;
1490       MachineFunction *F = BB->getParent();
1491       ilist<MachineBasicBlock>::iterator It = BB; ++It;
1492       F->getBasicBlockList().insert(It, TmpMBB);
1493       F->getBasicBlockList().insert(It, PhiMBB);
1494       BB->addSuccessor(TmpMBB);
1495       BB->addSuccessor(PhiMBB);
1496       BuildMI(BB, PPC::SRW, 2, Tmp2).addReg(ShiftOpLo).addReg(SHReg);
1497       BuildMI(BB, PPC::SLW, 2, Tmp3).addReg(ShiftOpHi).addReg(Tmp1);
1498       BuildMI(BB, PPC::OR, 2, Tmp4).addReg(Tmp2).addReg(Tmp3);
1499       BuildMI(BB, PPC::ADDICo, 2, Tmp5).addReg(SHReg).addSImm(-32);
1500       BuildMI(BB, PPC::SRAW, 2, Tmp6).addReg(ShiftOpHi).addReg(Tmp5);
1501       BuildMI(BB, PPC::SRAW, 2, Result+1).addReg(ShiftOpHi).addReg(SHReg);
1502       BuildMI(BB, PPC::BLE, 2).addReg(PPC::CR0).addMBB(PhiMBB);
1503       // Select correct least significant half if the shift amount > 32
1504       BB = TmpMBB;
1505       unsigned Tmp7 = MakeIntReg();
1506       BuildMI(BB, PPC::OR, 2, Tmp7).addReg(Tmp6).addReg(Tmp6);
1507       TmpMBB->addSuccessor(PhiMBB);
1508       BB = PhiMBB;
1509       BuildMI(BB, PPC::PHI, 4, Result).addReg(Tmp4).addMBB(OldMBB)
1510         .addReg(Tmp7).addMBB(TmpMBB);
1511     }
1512     return Result+N.ResNo;
1513   }
1514
1515   case ISD::FP_TO_SINT: {
1516     Tmp1 = SelectExpr(N.getOperand(0));
1517     Tmp2 = MakeFPReg();
1518     BuildMI(BB, PPC::FCTIWZ, 1, Tmp2).addReg(Tmp1);
1519     int FrameIdx = BB->getParent()->getFrameInfo()->CreateStackObject(8, 8);
1520     addFrameReference(BuildMI(BB, PPC::STFD, 3).addReg(Tmp2), FrameIdx);
1521     addFrameReference(BuildMI(BB, PPC::LWZ, 2, Result), FrameIdx, 4);
1522     return Result;
1523   }
1524
1525   case ISD::SETCC: {
1526     ISD::CondCode CC = cast<CondCodeSDNode>(Node->getOperand(2))->get();
1527     if (isIntImmediate(Node->getOperand(1), Tmp3)) {
1528       // We can codegen setcc op, imm very efficiently compared to a brcond.
1529       // Check for those cases here.
1530       // setcc op, 0
1531       if (Tmp3 == 0) {
1532         Tmp1 = SelectExpr(Node->getOperand(0));
1533         switch (CC) {
1534         default: Node->dump(); assert(0 && "Unhandled SetCC condition"); abort();
1535         case ISD::SETEQ:
1536           Tmp2 = MakeIntReg();
1537           BuildMI(BB, PPC::CNTLZW, 1, Tmp2).addReg(Tmp1);
1538           BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp2).addImm(27)
1539             .addImm(5).addImm(31);
1540           break;
1541         case ISD::SETNE:
1542           Tmp2 = MakeIntReg();
1543           BuildMI(BB, PPC::ADDIC, 2, Tmp2).addReg(Tmp1).addSImm(-1);
1544           BuildMI(BB, PPC::SUBFE, 2, Result).addReg(Tmp2).addReg(Tmp1);
1545           break;
1546         case ISD::SETLT:
1547           BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(1)
1548             .addImm(31).addImm(31);
1549           break;
1550         case ISD::SETGT:
1551           Tmp2 = MakeIntReg();
1552           Tmp3 = MakeIntReg();
1553           BuildMI(BB, PPC::NEG, 2, Tmp2).addReg(Tmp1);
1554           BuildMI(BB, PPC::ANDC, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1555           BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp3).addImm(1)
1556             .addImm(31).addImm(31);
1557           break;
1558         }
1559         return Result;
1560       } else if (Tmp3 == ~0U) {        // setcc op, -1
1561         Tmp1 = SelectExpr(Node->getOperand(0));
1562         switch (CC) {
1563         default: assert(0 && "Unhandled SetCC condition"); abort();
1564         case ISD::SETEQ:
1565           Tmp2 = MakeIntReg();
1566           Tmp3 = MakeIntReg();
1567           BuildMI(BB, PPC::ADDIC, 2, Tmp2).addReg(Tmp1).addSImm(1);
1568           BuildMI(BB, PPC::LI, 1, Tmp3).addSImm(0);
1569           BuildMI(BB, PPC::ADDZE, 1, Result).addReg(Tmp3);
1570           break;
1571         case ISD::SETNE:
1572           Tmp2 = MakeIntReg();
1573           Tmp3 = MakeIntReg();
1574           BuildMI(BB, PPC::NOR, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
1575           BuildMI(BB, PPC::ADDIC, 2, Tmp3).addReg(Tmp2).addSImm(-1);
1576           BuildMI(BB, PPC::SUBFE, 2, Result).addReg(Tmp3).addReg(Tmp2);
1577           break;
1578         case ISD::SETLT:
1579           Tmp2 = MakeIntReg();
1580           Tmp3 = MakeIntReg();
1581           BuildMI(BB, PPC::ADDI, 2, Tmp2).addReg(Tmp1).addSImm(1);
1582           BuildMI(BB, PPC::AND, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1583           BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp3).addImm(1)
1584             .addImm(31).addImm(31);
1585           break;
1586         case ISD::SETGT:
1587           Tmp2 = MakeIntReg();
1588           BuildMI(BB, PPC::RLWINM, 4, Tmp2).addReg(Tmp1).addImm(1)
1589             .addImm(31).addImm(31);
1590           BuildMI(BB, PPC::XORI, 2, Result).addReg(Tmp2).addImm(1);
1591           break;
1592         }
1593         return Result;
1594       }
1595     }
1596
1597     unsigned CCReg = SelectCC(N.getOperand(0), N.getOperand(1), CC);
1598     MoveCRtoGPR(CCReg, CC, Result);
1599     return Result;
1600   }
1601
1602   case ISD::SELECT_CC: {
1603     ISD::CondCode CC = cast<CondCodeSDNode>(N.getOperand(4))->get();
1604     if (!MVT::isInteger(N.getOperand(0).getValueType()) &&
1605         !MVT::isInteger(N.getOperand(2).getValueType()) &&
1606         CC != ISD::SETEQ && CC != ISD::SETNE) {
1607       MVT::ValueType VT = N.getOperand(0).getValueType();
1608       unsigned TV = SelectExpr(N.getOperand(2)); // Use if TRUE
1609       unsigned FV = SelectExpr(N.getOperand(3)); // Use if FALSE
1610
1611       ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N.getOperand(1));
1612       if (CN && (CN->isExactlyValue(-0.0) || CN->isExactlyValue(0.0))) {
1613         switch(CC) {
1614         default: assert(0 && "Invalid FSEL condition"); abort();
1615         case ISD::SETULT:
1616         case ISD::SETLT:
1617           std::swap(TV, FV);  // fsel is natively setge, swap operands for setlt
1618         case ISD::SETUGE:
1619         case ISD::SETGE:
1620           Tmp1 = SelectExpr(N.getOperand(0));   // Val to compare against
1621           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp1).addReg(TV).addReg(FV);
1622           return Result;
1623         case ISD::SETUGT:
1624         case ISD::SETGT:
1625           std::swap(TV, FV);  // fsel is natively setge, swap operands for setlt
1626         case ISD::SETULE:
1627         case ISD::SETLE: {
1628           if (N.getOperand(0).getOpcode() == ISD::FNEG) {
1629             Tmp2 = SelectExpr(N.getOperand(0).getOperand(0));
1630           } else {
1631             Tmp2 = MakeReg(VT);
1632             Tmp1 = SelectExpr(N.getOperand(0));   // Val to compare against
1633             BuildMI(BB, PPC::FNEG, 1, Tmp2).addReg(Tmp1);
1634           }
1635           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp2).addReg(TV).addReg(FV);
1636           return Result;
1637         }
1638         }
1639       } else {
1640         Opc = (MVT::f64 == VT) ? PPC::FSUB : PPC::FSUBS;
1641         Tmp1 = SelectExpr(N.getOperand(0));   // Val to compare against
1642         Tmp2 = SelectExpr(N.getOperand(1));
1643         Tmp3 =  MakeReg(VT);
1644         switch(CC) {
1645         default: assert(0 && "Invalid FSEL condition"); abort();
1646         case ISD::SETULT:
1647         case ISD::SETLT:
1648           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
1649           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(FV).addReg(TV);
1650           return Result;
1651         case ISD::SETUGE:
1652         case ISD::SETGE:
1653           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
1654           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(TV).addReg(FV);
1655           return Result;
1656         case ISD::SETUGT:
1657         case ISD::SETGT:
1658           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1659           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(FV).addReg(TV);
1660           return Result;
1661         case ISD::SETULE:
1662         case ISD::SETLE:
1663           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1664           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(TV).addReg(FV);
1665           return Result;
1666         }
1667       }
1668       assert(0 && "Should never get here");
1669     }
1670
1671     // If the False value only has one use, we can generate better code by
1672     // selecting it in the fallthrough basic block rather than here, which
1673     // increases register pressure.
1674     unsigned TrueValue = SelectExpr(N.getOperand(2));
1675     unsigned FalseValue = SelectExpr(N.getOperand(3));
1676     unsigned CCReg = SelectCC(N.getOperand(0), N.getOperand(1), CC);
1677     Opc = getBCCForSetCC(CC);
1678
1679     // Create an iterator with which to insert the MBB for copying the false
1680     // value and the MBB to hold the PHI instruction for this SetCC.
1681     MachineBasicBlock *thisMBB = BB;
1682     const BasicBlock *LLVM_BB = BB->getBasicBlock();
1683     ilist<MachineBasicBlock>::iterator It = BB;
1684     ++It;
1685
1686     //  thisMBB:
1687     //  ...
1688     //   TrueVal = ...
1689     //   cmpTY ccX, r1, r2
1690     //   bCC copy1MBB
1691     //   fallthrough --> copy0MBB
1692     MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
1693     MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
1694     BuildMI(BB, Opc, 2).addReg(CCReg).addMBB(sinkMBB);
1695     MachineFunction *F = BB->getParent();
1696     F->getBasicBlockList().insert(It, copy0MBB);
1697     F->getBasicBlockList().insert(It, sinkMBB);
1698     // Update machine-CFG edges
1699     BB->addSuccessor(copy0MBB);
1700     BB->addSuccessor(sinkMBB);
1701
1702     //  copy0MBB:
1703     //   %FalseValue = ...
1704     //   # fallthrough to sinkMBB
1705     BB = copy0MBB;
1706     // Update machine-CFG edges
1707     BB->addSuccessor(sinkMBB);
1708
1709     //  sinkMBB:
1710     //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
1711     //  ...
1712     BB = sinkMBB;
1713     BuildMI(BB, PPC::PHI, 4, Result).addReg(FalseValue)
1714       .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
1715     return Result;
1716   }
1717
1718   case ISD::Constant: {
1719     assert(N.getValueType() == MVT::i32 &&
1720            "Only i32 constants are legal on this target!");
1721     unsigned v = (unsigned)cast<ConstantSDNode>(N)->getValue();
1722     unsigned Hi = HA16(v);
1723     unsigned Lo = Lo16(v);
1724     if (Hi && Lo) {
1725       Tmp1 = MakeIntReg();
1726       BuildMI(BB, PPC::LIS, 1, Tmp1).addSImm(v >> 16);
1727       BuildMI(BB, PPC::ORI, 2, Result).addReg(Tmp1).addImm(Lo);
1728     } else if (Hi) {
1729       BuildMI(BB, PPC::LIS, 1, Result).addSImm(v >> 16);
1730     } else {
1731       BuildMI(BB, PPC::LI, 1, Result).addSImm(Lo);
1732     }
1733     return Result;
1734   }
1735
1736   case ISD::ConstantFP: {
1737     ConstantFPSDNode *CN = cast<ConstantFPSDNode>(N);
1738     Result = getConstDouble(CN->getValue(), Result);
1739     return Result;
1740   }
1741
1742   case ISD::FNEG:
1743     if (!NoExcessFPPrecision &&
1744         ISD::ADD == N.getOperand(0).getOpcode() &&
1745         N.getOperand(0).Val->hasOneUse() &&
1746         ISD::MUL == N.getOperand(0).getOperand(0).getOpcode() &&
1747         N.getOperand(0).getOperand(0).Val->hasOneUse()) {
1748       ++FusedFP; // Statistic
1749       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(0));
1750       Tmp2 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(1));
1751       Tmp3 = SelectExpr(N.getOperand(0).getOperand(1));
1752       Opc = DestType == MVT::f64 ? PPC::FNMADD : PPC::FNMADDS;
1753       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1754     } else if (!NoExcessFPPrecision &&
1755         ISD::ADD == N.getOperand(0).getOpcode() &&
1756         N.getOperand(0).Val->hasOneUse() &&
1757         ISD::MUL == N.getOperand(0).getOperand(1).getOpcode() &&
1758         N.getOperand(0).getOperand(1).Val->hasOneUse()) {
1759       ++FusedFP; // Statistic
1760       Tmp1 = SelectExpr(N.getOperand(0).getOperand(1).getOperand(0));
1761       Tmp2 = SelectExpr(N.getOperand(0).getOperand(1).getOperand(1));
1762       Tmp3 = SelectExpr(N.getOperand(0).getOperand(0));
1763       Opc = DestType == MVT::f64 ? PPC::FNMADD : PPC::FNMADDS;
1764       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1765     } else if (ISD::FABS == N.getOperand(0).getOpcode()) {
1766       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1767       BuildMI(BB, PPC::FNABS, 1, Result).addReg(Tmp1);
1768     } else {
1769       Tmp1 = SelectExpr(N.getOperand(0));
1770       BuildMI(BB, PPC::FNEG, 1, Result).addReg(Tmp1);
1771     }
1772     return Result;
1773
1774   case ISD::FABS:
1775     Tmp1 = SelectExpr(N.getOperand(0));
1776     BuildMI(BB, PPC::FABS, 1, Result).addReg(Tmp1);
1777     return Result;
1778
1779   case ISD::FSQRT:
1780     Tmp1 = SelectExpr(N.getOperand(0));
1781     Opc = DestType == MVT::f64 ? PPC::FSQRT : PPC::FSQRTS;
1782     BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
1783     return Result;
1784
1785   case ISD::FP_ROUND:
1786     assert (DestType == MVT::f32 &&
1787             N.getOperand(0).getValueType() == MVT::f64 &&
1788             "only f64 to f32 conversion supported here");
1789     Tmp1 = SelectExpr(N.getOperand(0));
1790     BuildMI(BB, PPC::FRSP, 1, Result).addReg(Tmp1);
1791     return Result;
1792
1793   case ISD::FP_EXTEND:
1794     assert (DestType == MVT::f64 &&
1795             N.getOperand(0).getValueType() == MVT::f32 &&
1796             "only f32 to f64 conversion supported here");
1797     Tmp1 = SelectExpr(N.getOperand(0));
1798     BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
1799     return Result;
1800   }
1801   return 0;
1802 }
1803
1804 void ISel::Select(SDOperand N) {
1805   unsigned Tmp1, Tmp2, Tmp3, Opc;
1806   unsigned opcode = N.getOpcode();
1807
1808   if (!ExprMap.insert(std::make_pair(N, 1)).second)
1809     return;  // Already selected.
1810
1811   SDNode *Node = N.Val;
1812
1813   switch (Node->getOpcode()) {
1814   default:
1815     Node->dump(); std::cerr << "\n";
1816     assert(0 && "Node not handled yet!");
1817   case ISD::EntryToken: return;  // Noop
1818   case ISD::TokenFactor:
1819     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
1820       Select(Node->getOperand(i));
1821     return;
1822   case ISD::CALLSEQ_START:
1823   case ISD::CALLSEQ_END:
1824     Select(N.getOperand(0));
1825     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
1826     Opc = N.getOpcode() == ISD::CALLSEQ_START ? PPC::ADJCALLSTACKDOWN :
1827       PPC::ADJCALLSTACKUP;
1828     BuildMI(BB, Opc, 1).addImm(Tmp1);
1829     return;
1830   case ISD::BR: {
1831     MachineBasicBlock *Dest =
1832       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
1833     Select(N.getOperand(0));
1834     BuildMI(BB, PPC::B, 1).addMBB(Dest);
1835     return;
1836   }
1837   case ISD::BR_CC:
1838   case ISD::BRTWOWAY_CC:
1839     SelectBranchCC(N);
1840     return;
1841   case ISD::CopyToReg:
1842     Select(N.getOperand(0));
1843     Tmp1 = SelectExpr(N.getOperand(2));
1844     Tmp2 = cast<RegisterSDNode>(N.getOperand(1))->getReg();
1845
1846     if (Tmp1 != Tmp2) {
1847       if (N.getOperand(2).getValueType() == MVT::f64 ||
1848           N.getOperand(2).getValueType() == MVT::f32)
1849         BuildMI(BB, PPC::FMR, 1, Tmp2).addReg(Tmp1);
1850       else
1851         BuildMI(BB, PPC::OR, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
1852     }
1853     return;
1854   case ISD::ImplicitDef:
1855     Select(N.getOperand(0));
1856     BuildMI(BB, PPC::IMPLICIT_DEF, 0,
1857             cast<RegisterSDNode>(N.getOperand(1))->getReg());
1858     return;
1859   case ISD::RET:
1860     switch (N.getNumOperands()) {
1861     default:
1862       assert(0 && "Unknown return instruction!");
1863     case 3:
1864       assert(N.getOperand(1).getValueType() == MVT::i32 &&
1865              N.getOperand(2).getValueType() == MVT::i32 &&
1866              "Unknown two-register value!");
1867       Select(N.getOperand(0));
1868       Tmp1 = SelectExpr(N.getOperand(1));
1869       Tmp2 = SelectExpr(N.getOperand(2));
1870       BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp2).addReg(Tmp2);
1871       BuildMI(BB, PPC::OR, 2, PPC::R4).addReg(Tmp1).addReg(Tmp1);
1872       break;
1873     case 2:
1874       Select(N.getOperand(0));
1875       Tmp1 = SelectExpr(N.getOperand(1));
1876       switch (N.getOperand(1).getValueType()) {
1877         default:
1878           assert(0 && "Unknown return type!");
1879         case MVT::f64:
1880         case MVT::f32:
1881           BuildMI(BB, PPC::FMR, 1, PPC::F1).addReg(Tmp1);
1882           break;
1883         case MVT::i32:
1884           BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp1).addReg(Tmp1);
1885           break;
1886       }
1887     case 1:
1888       Select(N.getOperand(0));
1889       break;
1890     }
1891     BuildMI(BB, PPC::BLR, 0); // Just emit a 'ret' instruction
1892     return;
1893   case ISD::TRUNCSTORE:
1894   case ISD::STORE: {
1895     SDOperand Chain   = N.getOperand(0);
1896     SDOperand Value   = N.getOperand(1);
1897     SDOperand Address = N.getOperand(2);
1898     Select(Chain);
1899
1900     Tmp1 = SelectExpr(Value); //value
1901
1902     if (opcode == ISD::STORE) {
1903       switch(Value.getValueType()) {
1904       default: assert(0 && "unknown Type in store");
1905       case MVT::i32: Opc = PPC::STW; break;
1906       case MVT::f64: Opc = PPC::STFD; break;
1907       case MVT::f32: Opc = PPC::STFS; break;
1908       }
1909     } else { //ISD::TRUNCSTORE
1910       switch(cast<VTSDNode>(Node->getOperand(4))->getVT()) {
1911       default: assert(0 && "unknown Type in store");
1912       case MVT::i1:
1913       case MVT::i8: Opc  = PPC::STB; break;
1914       case MVT::i16: Opc = PPC::STH; break;
1915       }
1916     }
1917
1918     if(Address.getOpcode() == ISD::FrameIndex) {
1919       Tmp2 = cast<FrameIndexSDNode>(Address)->getIndex();
1920       addFrameReference(BuildMI(BB, Opc, 3).addReg(Tmp1), (int)Tmp2);
1921     } else {
1922       int offset;
1923       switch(SelectAddr(Address, Tmp2, offset)) {
1924       default: assert(0 && "Unhandled return value from SelectAddr");
1925       case 0:   // imm offset, no frame, no index
1926         BuildMI(BB, Opc, 3).addReg(Tmp1).addSImm(offset).addReg(Tmp2);
1927         break;
1928       case 1:   // imm offset + frame index
1929         addFrameReference(BuildMI(BB, Opc, 3).addReg(Tmp1), (int)Tmp2, offset);
1930         break;
1931       case 2:   // base+index addressing
1932         Opc = IndexedOpForOp(Opc);
1933         BuildMI(BB, Opc, 3).addReg(Tmp1).addReg(Tmp2).addReg(offset);
1934         break;
1935       case 3: {
1936         GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(Address);
1937         GlobalValue *GV = GN->getGlobal();
1938         BuildMI(BB, Opc, 3).addReg(Tmp1).addGlobalAddress(GV).addReg(Tmp2);
1939       }
1940       }
1941     }
1942     return;
1943   }
1944   case ISD::EXTLOAD:
1945   case ISD::SEXTLOAD:
1946   case ISD::ZEXTLOAD:
1947   case ISD::LOAD:
1948   case ISD::CopyFromReg:
1949   case ISD::TAILCALL:
1950   case ISD::CALL:
1951   case ISD::DYNAMIC_STACKALLOC:
1952     ExprMap.erase(N);
1953     SelectExpr(N);
1954     return;
1955   }
1956   assert(0 && "Should not be reached!");
1957 }
1958
1959
1960 /// createPPC32PatternInstructionSelector - This pass converts an LLVM function
1961 /// into a machine code representation using pattern matching and a machine
1962 /// description file.
1963 ///
1964 FunctionPass *llvm::createPPC32ISelPattern(TargetMachine &TM) {
1965   return new ISel(TM);
1966 }
1967