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     if (Node->getValueType(0) == MVT::i32)
 834       BuildMI(BB, PPC::IMPLICIT_DEF_GPR, 0, Result);
 835     else
 836       BuildMI(BB, PPC::IMPLICIT_DEF_FP, 0, Result);
 837     return Result;
 838   case ISD::DYNAMIC_STACKALLOC:
 839     // Generate both result values.  FIXME: Need a better commment here?
 840     if (Result != 1)
 841       ExprMap[N.getValue(1)] = 1;
 842     else
 843       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 844
 845     // FIXME: We are currently ignoring the requested alignment for handling
 846     // greater than the stack alignment.  This will need to be revisited at some
 847     // point.  Align = N.getOperand(2);
 848     if (!isa<ConstantSDNode>(N.getOperand(2)) ||
 849         cast<ConstantSDNode>(N.getOperand(2))->getValue() != 0) {
 850       std::cerr << "Cannot allocate stack object with greater alignment than"
 851                 << " the stack alignment yet!";
 852       abort();
 853     }
 854     Select(N.getOperand(0));
 855     Tmp1 = SelectExpr(N.getOperand(1));
 856     // Subtract size from stack pointer, thereby allocating some space.
 857     BuildMI(BB, PPC::SUBF, 2, PPC::R1).addReg(Tmp1).addReg(PPC::R1);
 858     // Put a pointer to the space into the result register by copying the SP
 859     BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R1).addReg(PPC::R1);
 860     return Result;
 861
 862   case ISD::ConstantPool:
 863     Tmp1 = cast<ConstantPoolSDNode>(N)->getIndex();
 864     Tmp2 = MakeIntReg();
 865     if (PICEnabled)
 866       BuildMI(BB, PPC::ADDIS, 2, Tmp2).addReg(getGlobalBaseReg())
 867         .addConstantPoolIndex(Tmp1);
 868     else
 869       BuildMI(BB, PPC::LIS, 1, Tmp2).addConstantPoolIndex(Tmp1);
 870     BuildMI(BB, PPC::LA, 2, Result).addReg(Tmp2).addConstantPoolIndex(Tmp1);
 871     return Result;
 872
 873   case ISD::FrameIndex:
 874     Tmp1 = cast<FrameIndexSDNode>(N)->getIndex();
 875     addFrameReference(BuildMI(BB, PPC::ADDI, 2, Result), (int)Tmp1, 0, false);
 876     return Result;
 877
 878   case ISD::GlobalAddress: {
 879     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
 880     Tmp1 = MakeIntReg();
 881     if (PICEnabled)
 882       BuildMI(BB, PPC::ADDIS, 2, Tmp1).addReg(getGlobalBaseReg())
 883         .addGlobalAddress(GV);
 884     else
 885       BuildMI(BB, PPC::LIS, 1, Tmp1).addGlobalAddress(GV);
 886     if (GV->hasWeakLinkage() || GV->isExternal()) {
 887       BuildMI(BB, PPC::LWZ, 2, Result).addGlobalAddress(GV).addReg(Tmp1);
 888     } else {
 889       BuildMI(BB, PPC::LA, 2, Result).addReg(Tmp1).addGlobalAddress(GV);
 890     }
 891     return Result;
 892   }
 893
 894   case ISD::LOAD:
 895   case ISD::EXTLOAD:
 896   case ISD::ZEXTLOAD:
 897   case ISD::SEXTLOAD: {
 898     MVT::ValueType TypeBeingLoaded = (ISD::LOAD == opcode) ?
 899       Node->getValueType(0) : cast<VTSDNode>(Node->getOperand(3))->getVT();
 900     bool sext = (ISD::SEXTLOAD == opcode);
 901
 902     // Make sure we generate both values.
 903     if (Result != 1)
 904       ExprMap[N.getValue(1)] = 1;   // Generate the token
 905     else
 906       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 907
 908     SDOperand Chain   = N.getOperand(0);
 909     SDOperand Address = N.getOperand(1);
 910     Select(Chain);
 911
 912     switch (TypeBeingLoaded) {
 913     default: Node->dump(); assert(0 && "Cannot load this type!");
 914     case MVT::i1:  Opc = PPC::LBZ; break;
 915     case MVT::i8:  Opc = PPC::LBZ; break;
 916     case MVT::i16: Opc = sext ? PPC::LHA : PPC::LHZ; break;
 917     case MVT::i32: Opc = PPC::LWZ; break;
 918     case MVT::f32: Opc = PPC::LFS; break;
 919     case MVT::f64: Opc = PPC::LFD; break;
 920     }
 921
 922     if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Address)) {
 923       Tmp1 = MakeIntReg();
 924       int CPI = CP->getIndex();
 925       if (PICEnabled)
 926         BuildMI(BB, PPC::ADDIS, 2, Tmp1).addReg(getGlobalBaseReg())
 927           .addConstantPoolIndex(CPI);
 928       else
 929         BuildMI(BB, PPC::LIS, 1, Tmp1).addConstantPoolIndex(CPI);
 930       BuildMI(BB, Opc, 2, Result).addConstantPoolIndex(CPI).addReg(Tmp1);
 931     } else if (Address.getOpcode() == ISD::FrameIndex) {
 932       Tmp1 = cast<FrameIndexSDNode>(Address)->getIndex();
 933       addFrameReference(BuildMI(BB, Opc, 2, Result), (int)Tmp1);
 934     } else {
 935       int offset;
 936       switch(SelectAddr(Address, Tmp1, offset)) {
 937       default: assert(0 && "Unhandled return value from SelectAddr");
 938       case 0:   // imm offset, no frame, no index
 939         BuildMI(BB, Opc, 2, Result).addSImm(offset).addReg(Tmp1);
 940         break;
 941       case 1:   // imm offset + frame index
 942         addFrameReference(BuildMI(BB, Opc, 2, Result), (int)Tmp1, offset);
 943         break;
 944       case 2:   // base+index addressing
 945         Opc = IndexedOpForOp(Opc);
 946         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(offset);
 947         break;
 948       case 3: {
 949         GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(Address);
 950         GlobalValue *GV = GN->getGlobal();
 951         BuildMI(BB, Opc, 2, Result).addGlobalAddress(GV).addReg(Tmp1);
 952       }
 953       }
 954     }
 955     return Result;
 956   }
 957
 958   case ISD::TAILCALL:
 959   case ISD::CALL: {
 960     unsigned GPR_idx = 0, FPR_idx = 0;
 961     static const unsigned GPR[] = {
 962       PPC::R3, PPC::R4, PPC::R5, PPC::R6,
 963       PPC::R7, PPC::R8, PPC::R9, PPC::R10,
 964     };
 965     static const unsigned FPR[] = {
 966       PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
 967       PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
 968     };
 969
 970     // Lower the chain for this call.
 971     Select(N.getOperand(0));
 972     ExprMap[N.getValue(Node->getNumValues()-1)] = 1;
 973
 974     MachineInstr *CallMI;
 975     // Emit the correct call instruction based on the type of symbol called.
 976     if (GlobalAddressSDNode *GASD =
 977         dyn_cast<GlobalAddressSDNode>(N.getOperand(1))) {
 978       CallMI = BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(GASD->getGlobal(),
 979                                                            true);
 980     } else if (ExternalSymbolSDNode *ESSDN =
 981                dyn_cast<ExternalSymbolSDNode>(N.getOperand(1))) {
 982       CallMI = BuildMI(PPC::CALLpcrel, 1).addExternalSymbol(ESSDN->getSymbol(),
 983                                                             true);
 984     } else {
 985       Tmp1 = SelectExpr(N.getOperand(1));
 986       BuildMI(BB, PPC::MTCTR, 1).addReg(Tmp1);
 987       BuildMI(BB, PPC::OR, 2, PPC::R12).addReg(Tmp1).addReg(Tmp1);
 988       CallMI = BuildMI(PPC::CALLindirect, 3).addImm(20).addImm(0)
 989         .addReg(PPC::R12);
 990     }
 991
 992     // Load the register args to virtual regs
 993     std::vector<unsigned> ArgVR;
 994     for(int i = 2, e = Node->getNumOperands(); i < e; ++i)
 995       ArgVR.push_back(SelectExpr(N.getOperand(i)));
 996
 997     // Copy the virtual registers into the appropriate argument register
 998     for(int i = 0, e = ArgVR.size(); i < e; ++i) {
 999       switch(N.getOperand(i+2).getValueType()) {
1000       default: Node->dump(); assert(0 && "Unknown value type for call");
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::i32:
1026       if (Node->getValueType(1) == MVT::i32) {
1027         BuildMI(BB, PPC::OR, 2, Result+1).addReg(PPC::R3).addReg(PPC::R3);
1028         BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R4).addReg(PPC::R4);
1029       } else {
1030         BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R3).addReg(PPC::R3);
1031       }
1032       break;
1033     case MVT::f32:
1034     case MVT::f64:
1035       BuildMI(BB, PPC::FMR, 1, Result).addReg(PPC::F1);
1036       break;
1037     }
1038     return Result+N.ResNo;
1039   }
1040
1041   case ISD::SIGN_EXTEND:
1042   case ISD::SIGN_EXTEND_INREG:
1043     Tmp1 = SelectExpr(N.getOperand(0));
1044     switch(cast<VTSDNode>(Node->getOperand(1))->getVT()) {
1045     default: Node->dump(); assert(0 && "Unhandled SIGN_EXTEND type"); break;
1046     case MVT::i16:
1047       BuildMI(BB, PPC::EXTSH, 1, Result).addReg(Tmp1);
1048       break;
1049     case MVT::i8:
1050       BuildMI(BB, PPC::EXTSB, 1, Result).addReg(Tmp1);
1051       break;
1052     }
1053     return Result;
1054
1055   case ISD::CopyFromReg:
1056     DestType = N.getValue(0).getValueType();
1057     if (Result == 1)
1058       Result = ExprMap[N.getValue(0)] = MakeReg(DestType);
1059     Tmp1 = dyn_cast<RegisterSDNode>(Node->getOperand(1))->getReg();
1060     if (MVT::isInteger(DestType))
1061       BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp1).addReg(Tmp1);
1062     else
1063       BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
1064     return Result;
1065
1066   case ISD::SHL:
1067     if (isIntImmediate(N.getOperand(1), Tmp2)) {
1068       unsigned SH, MB, ME;
1069       if (isOpcWithIntImmediate(N.getOperand(0), ISD::AND, Tmp3) &&
1070           isRotateAndMask(ISD::SHL, Tmp2, Tmp3, true, SH, MB, ME)) {
1071         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1072         BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(SH)
1073           .addImm(MB).addImm(ME);
1074         return Result;
1075       }
1076       Tmp1 = SelectExpr(N.getOperand(0));
1077       Tmp2 &= 0x1F;
1078       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(Tmp2).addImm(0)
1079         .addImm(31-Tmp2);
1080     } else {
1081       Tmp1 = SelectExpr(N.getOperand(0));
1082       Tmp2 = FoldIfWideZeroExtend(N.getOperand(1));
1083       BuildMI(BB, PPC::SLW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1084     }
1085     return Result;
1086
1087   case ISD::SRL:
1088     if (isIntImmediate(N.getOperand(1), Tmp2)) {
1089       unsigned SH, MB, ME;
1090       if (isOpcWithIntImmediate(N.getOperand(0), ISD::AND, Tmp3) &&
1091           isRotateAndMask(ISD::SRL, Tmp2, Tmp3, true, SH, MB, ME)) {
1092         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1093         BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(SH)
1094           .addImm(MB).addImm(ME);
1095         return Result;
1096       }
1097       Tmp1 = SelectExpr(N.getOperand(0));
1098       Tmp2 &= 0x1F;
1099       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(32-Tmp2)
1100         .addImm(Tmp2).addImm(31);
1101     } else {
1102       Tmp1 = SelectExpr(N.getOperand(0));
1103       Tmp2 = FoldIfWideZeroExtend(N.getOperand(1));
1104       BuildMI(BB, PPC::SRW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1105     }
1106     return Result;
1107
1108   case ISD::SRA:
1109     if (isIntImmediate(N.getOperand(1), Tmp2)) {
1110       unsigned SH, MB, ME;
1111       if (isOpcWithIntImmediate(N.getOperand(0), ISD::AND, Tmp3) &&
1112           isRotateAndMask(ISD::SRA, Tmp2, Tmp3, true, SH, MB, ME)) {
1113         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1114         BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(SH)
1115           .addImm(MB).addImm(ME);
1116         return Result;
1117       }
1118       Tmp1 = SelectExpr(N.getOperand(0));
1119       Tmp2 &= 0x1F;
1120       BuildMI(BB, PPC::SRAWI, 2, Result).addReg(Tmp1).addImm(Tmp2);
1121     } else {
1122       Tmp1 = SelectExpr(N.getOperand(0));
1123       Tmp2 = FoldIfWideZeroExtend(N.getOperand(1));
1124       BuildMI(BB, PPC::SRAW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1125     }
1126     return Result;
1127
1128   case ISD::CTLZ:
1129     Tmp1 = SelectExpr(N.getOperand(0));
1130     BuildMI(BB, PPC::CNTLZW, 1, Result).addReg(Tmp1);
1131     return Result;
1132
1133   case ISD::ADD:
1134     if (!MVT::isInteger(DestType)) {
1135       if (!NoExcessFPPrecision && N.getOperand(0).getOpcode() == ISD::MUL &&
1136           N.getOperand(0).Val->hasOneUse()) {
1137         ++FusedFP; // Statistic
1138         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1139         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1140         Tmp3 = SelectExpr(N.getOperand(1));
1141         Opc = DestType == MVT::f64 ? PPC::FMADD : PPC::FMADDS;
1142         BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1143         return Result;
1144       }
1145       if (!NoExcessFPPrecision && N.getOperand(1).getOpcode() == ISD::MUL &&
1146           N.getOperand(1).Val->hasOneUse()) {
1147         ++FusedFP; // Statistic
1148         Tmp1 = SelectExpr(N.getOperand(1).getOperand(0));
1149         Tmp2 = SelectExpr(N.getOperand(1).getOperand(1));
1150         Tmp3 = SelectExpr(N.getOperand(0));
1151         Opc = DestType == MVT::f64 ? PPC::FMADD : PPC::FMADDS;
1152         BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1153         return Result;
1154       }
1155       Opc = DestType == MVT::f64 ? PPC::FADD : PPC::FADDS;
1156       Tmp1 = SelectExpr(N.getOperand(0));
1157       Tmp2 = SelectExpr(N.getOperand(1));
1158       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1159       return Result;
1160     }
1161     if (SelectIntImmediateExpr(N, Result, PPC::ADDIS, PPC::ADDI, true))
1162       return Result;
1163     Tmp1 = SelectExpr(N.getOperand(0));
1164     Tmp2 = SelectExpr(N.getOperand(1));
1165     BuildMI(BB, PPC::ADD, 2, Result).addReg(Tmp1).addReg(Tmp2);
1166     return Result;
1167
1168   case ISD::AND:
1169     if (isIntImmediate(N.getOperand(1), Tmp2)) {
1170       if (isShiftedMask_32(Tmp2) || isShiftedMask_32(~Tmp2)) {
1171         unsigned SH, MB, ME;
1172         Opc = Recording ? PPC::RLWINMo : PPC::RLWINM;
1173         unsigned OprOpc;
1174         if (isOprShiftImm(N.getOperand(0), OprOpc, Tmp3) &&
1175             isRotateAndMask(OprOpc, Tmp3, Tmp2, false, SH, MB, ME)) {
1176           Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1177         } else {
1178           Tmp1 = SelectExpr(N.getOperand(0));
1179           isRunOfOnes(Tmp2, MB, ME);
1180           SH = 0;
1181         }
1182         BuildMI(BB, Opc, 4, Result).addReg(Tmp1).addImm(SH)
1183           .addImm(MB).addImm(ME);
1184         RecordSuccess = true;
1185         return Result;
1186       } else if (isUInt16(Tmp2)) {
1187         Tmp2 = Lo16(Tmp2);
1188         Tmp1 = SelectExpr(N.getOperand(0));
1189         BuildMI(BB, PPC::ANDIo, 2, Result).addReg(Tmp1).addImm(Tmp2);
1190         RecordSuccess = true;
1191         return Result;
1192       } else if (isUInt16(Tmp2)) {
1193         Tmp2 = Hi16(Tmp2);
1194         Tmp1 = SelectExpr(N.getOperand(0));
1195         BuildMI(BB, PPC::ANDISo, 2, Result).addReg(Tmp1).addImm(Tmp2);
1196         RecordSuccess = true;
1197        return Result;
1198       }
1199     }
1200     if (isOprNot(N.getOperand(1))) {
1201       Tmp1 = SelectExpr(N.getOperand(0));
1202       Tmp2 = SelectExpr(N.getOperand(1).getOperand(0));
1203       BuildMI(BB, PPC::ANDC, 2, Result).addReg(Tmp1).addReg(Tmp2);
1204       RecordSuccess = false;
1205       return Result;
1206     }
1207     if (isOprNot(N.getOperand(0))) {
1208       Tmp1 = SelectExpr(N.getOperand(1));
1209       Tmp2 = SelectExpr(N.getOperand(0).getOperand(0));
1210       BuildMI(BB, PPC::ANDC, 2, Result).addReg(Tmp1).addReg(Tmp2);
1211       RecordSuccess = false;
1212       return Result;
1213     }
1214     // emit a regular and
1215     Tmp1 = SelectExpr(N.getOperand(0));
1216     Tmp2 = SelectExpr(N.getOperand(1));
1217     Opc = Recording ? PPC::ANDo : PPC::AND;
1218     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1219     RecordSuccess = true;
1220     return Result;
1221
1222   case ISD::OR:
1223     if (SelectBitfieldInsert(N, Result))
1224       return Result;
1225     if (SelectIntImmediateExpr(N, Result, PPC::ORIS, PPC::ORI))
1226       return Result;
1227     if (isOprNot(N.getOperand(1))) {
1228       Tmp1 = SelectExpr(N.getOperand(0));
1229       Tmp2 = SelectExpr(N.getOperand(1).getOperand(0));
1230       BuildMI(BB, PPC::ORC, 2, Result).addReg(Tmp1).addReg(Tmp2);
1231       RecordSuccess = false;
1232       return Result;
1233     }
1234     if (isOprNot(N.getOperand(0))) {
1235       Tmp1 = SelectExpr(N.getOperand(1));
1236       Tmp2 = SelectExpr(N.getOperand(0).getOperand(0));
1237       BuildMI(BB, PPC::ORC, 2, Result).addReg(Tmp1).addReg(Tmp2);
1238       RecordSuccess = false;
1239       return Result;
1240     }
1241     // emit regular or
1242     Tmp1 = SelectExpr(N.getOperand(0));
1243     Tmp2 = SelectExpr(N.getOperand(1));
1244     Opc = Recording ? PPC::ORo : PPC::OR;
1245     RecordSuccess = true;
1246     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1247     return Result;
1248
1249   case ISD::XOR: {
1250     // Check for EQV: xor, (xor a, -1), b
1251     if (isOprNot(N.getOperand(0))) {
1252       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1253       Tmp2 = SelectExpr(N.getOperand(1));
1254       BuildMI(BB, PPC::EQV, 2, Result).addReg(Tmp1).addReg(Tmp2);
1255       return Result;
1256     }
1257     // Check for NOT, NOR, EQV, and NAND: xor (copy, or, xor, and), -1
1258     if (isOprNot(N)) {
1259       switch(N.getOperand(0).getOpcode()) {
1260       case ISD::OR:
1261         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1262         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1263         BuildMI(BB, PPC::NOR, 2, Result).addReg(Tmp1).addReg(Tmp2);
1264         break;
1265       case ISD::AND:
1266         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1267         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1268         BuildMI(BB, PPC::NAND, 2, Result).addReg(Tmp1).addReg(Tmp2);
1269         break;
1270       case ISD::XOR:
1271         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1272         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1273         BuildMI(BB, PPC::EQV, 2, Result).addReg(Tmp1).addReg(Tmp2);
1274         break;
1275       default:
1276         Tmp1 = SelectExpr(N.getOperand(0));
1277         BuildMI(BB, PPC::NOR, 2, Result).addReg(Tmp1).addReg(Tmp1);
1278         break;
1279       }
1280       return Result;
1281     }
1282     if (SelectIntImmediateExpr(N, Result, PPC::XORIS, PPC::XORI))
1283       return Result;
1284     // emit regular xor
1285     Tmp1 = SelectExpr(N.getOperand(0));
1286     Tmp2 = SelectExpr(N.getOperand(1));
1287     BuildMI(BB, PPC::XOR, 2, Result).addReg(Tmp1).addReg(Tmp2);
1288     return Result;
1289   }
1290
1291    case ISD::SUB:
1292     if (!MVT::isInteger(DestType)) {
1293       if (!NoExcessFPPrecision && N.getOperand(0).getOpcode() == ISD::MUL &&
1294           N.getOperand(0).Val->hasOneUse()) {
1295         ++FusedFP; // Statistic
1296         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1297         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1298         Tmp3 = SelectExpr(N.getOperand(1));
1299         Opc = DestType == MVT::f64 ? PPC::FMSUB : PPC::FMSUBS;
1300         BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1301         return Result;
1302       }
1303       if (!NoExcessFPPrecision && N.getOperand(1).getOpcode() == ISD::MUL &&
1304           N.getOperand(1).Val->hasOneUse()) {
1305         ++FusedFP; // Statistic
1306         Tmp1 = SelectExpr(N.getOperand(1).getOperand(0));
1307         Tmp2 = SelectExpr(N.getOperand(1).getOperand(1));
1308         Tmp3 = SelectExpr(N.getOperand(0));
1309         Opc = DestType == MVT::f64 ? PPC::FNMSUB : PPC::FNMSUBS;
1310         BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1311         return Result;
1312       }
1313       Opc = DestType == MVT::f64 ? PPC::FSUB : PPC::FSUBS;
1314       Tmp1 = SelectExpr(N.getOperand(0));
1315       Tmp2 = SelectExpr(N.getOperand(1));
1316       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1317       return Result;
1318     }
1319     if (isIntImmediate(N.getOperand(0), Tmp1) && isInt16(Tmp1)) {
1320       Tmp1 = Lo16(Tmp1);
1321       Tmp2 = SelectExpr(N.getOperand(1));
1322       if (0 == Tmp1)
1323         BuildMI(BB, PPC::NEG, 1, Result).addReg(Tmp2);
1324       else
1325         BuildMI(BB, PPC::SUBFIC, 2, Result).addReg(Tmp2).addSImm(Tmp1);
1326       return Result;
1327     }
1328     if (SelectIntImmediateExpr(N, Result, PPC::ADDIS, PPC::ADDI, true, true))
1329         return Result;
1330     Tmp1 = SelectExpr(N.getOperand(0));
1331     Tmp2 = SelectExpr(N.getOperand(1));
1332     BuildMI(BB, PPC::SUBF, 2, Result).addReg(Tmp2).addReg(Tmp1);
1333     return Result;
1334
1335   case ISD::MUL:
1336     Tmp1 = SelectExpr(N.getOperand(0));
1337     if (isIntImmediate(N.getOperand(1), Tmp2) && isInt16(Tmp2)) {
1338       Tmp2 = Lo16(Tmp2);
1339       BuildMI(BB, PPC::MULLI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
1340     } else {
1341       Tmp2 = SelectExpr(N.getOperand(1));
1342       switch (DestType) {
1343       default: assert(0 && "Unknown type to ISD::MUL"); break;
1344       case MVT::i32: Opc = PPC::MULLW; break;
1345       case MVT::f32: Opc = PPC::FMULS; break;
1346       case MVT::f64: Opc = PPC::FMUL; break;
1347       }
1348       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1349     }
1350     return Result;
1351
1352   case ISD::MULHS:
1353   case ISD::MULHU:
1354     Tmp1 = SelectExpr(N.getOperand(0));
1355     Tmp2 = SelectExpr(N.getOperand(1));
1356     Opc = (ISD::MULHU == opcode) ? PPC::MULHWU : PPC::MULHW;
1357     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1358     return Result;
1359
1360   case ISD::SDIV:
1361     if (isIntImmediate(N.getOperand(1), Tmp3)) {
1362       if ((signed)Tmp3 > 0 && isPowerOf2_32(Tmp3)) {
1363         Tmp3 = Log2_32(Tmp3);
1364         Tmp1 = MakeIntReg();
1365         Tmp2 = SelectExpr(N.getOperand(0));
1366         BuildMI(BB, PPC::SRAWI, 2, Tmp1).addReg(Tmp2).addImm(Tmp3);
1367         BuildMI(BB, PPC::ADDZE, 1, Result).addReg(Tmp1);
1368         return Result;
1369       } else if ((signed)Tmp3 < 0 && isPowerOf2_32(-Tmp3)) {
1370         Tmp3 = Log2_32(-Tmp3);
1371         Tmp2 = SelectExpr(N.getOperand(0));
1372         Tmp1 = MakeIntReg();
1373         unsigned Tmp4 = MakeIntReg();
1374         BuildMI(BB, PPC::SRAWI, 2, Tmp1).addReg(Tmp2).addImm(Tmp3);
1375         BuildMI(BB, PPC::ADDZE, 1, Tmp4).addReg(Tmp1);
1376         BuildMI(BB, PPC::NEG, 1, Result).addReg(Tmp4);
1377         return Result;
1378       } else if (Tmp3) {
1379         ExprMap.erase(N);
1380         return SelectExpr(BuildSDIVSequence(N));
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) && Tmp3) {
1388       ExprMap.erase(N);
1389       return SelectExpr(BuildUDIVSequence(N));
1390     }
1391     Tmp1 = SelectExpr(N.getOperand(0));
1392     Tmp2 = SelectExpr(N.getOperand(1));
1393     switch (DestType) {
1394     default: assert(0 && "Unknown type to ISD::DIV"); break;
1395     case MVT::i32: Opc = (ISD::UDIV == opcode) ? PPC::DIVWU : PPC::DIVW; break;
1396     case MVT::f32: Opc = PPC::FDIVS; break;
1397     case MVT::f64: Opc = PPC::FDIV; break;
1398     }
1399     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1400     return Result;
1401
1402   case ISD::ADD_PARTS:
1403   case ISD::SUB_PARTS: {
1404     assert(N.getNumOperands() == 4 && N.getValueType() == MVT::i32 &&
1405            "Not an i64 add/sub!");
1406     unsigned Tmp4 = 0;
1407     Tmp1 = SelectExpr(N.getOperand(0));
1408     Tmp2 = SelectExpr(N.getOperand(1));
1409
1410     if (N.getOpcode() == ISD::ADD_PARTS) {
1411       bool ME, ZE;
1412       if (isIntImmediate(N.getOperand(3), Tmp3)) {
1413         ME = (signed)Tmp3 == -1;
1414         ZE = Tmp3 == 0;
1415       }
1416
1417       if (!ZE && !ME)
1418         Tmp4 = SelectExpr(N.getOperand(3));
1419
1420       if (isIntImmediate(N.getOperand(2), Tmp3) &&
1421           ((signed)Tmp3 >= -32768 || (signed)Tmp3 < 32768)) {
1422         // Codegen the low 32 bits of the add.  Interestingly, there is no
1423         // shifted form of add immediate carrying.
1424         BuildMI(BB, PPC::ADDIC, 2, Result).addReg(Tmp1).addSImm(Tmp3);
1425       } else {
1426         Tmp3 = SelectExpr(N.getOperand(2));
1427         BuildMI(BB, PPC::ADDC, 2, Result).addReg(Tmp1).addReg(Tmp3);
1428       }
1429
1430       // Codegen the high 32 bits, adding zero, minus one, or the full value
1431       // along with the carry flag produced by addc/addic to tmp2.
1432       if (ZE) {
1433         BuildMI(BB, PPC::ADDZE, 1, Result+1).addReg(Tmp2);
1434       } else if (ME) {
1435         BuildMI(BB, PPC::ADDME, 1, Result+1).addReg(Tmp2);
1436       } else {
1437         BuildMI(BB, PPC::ADDE, 2, Result+1).addReg(Tmp2).addReg(Tmp4);
1438       }
1439     } else {
1440       Tmp3 = SelectExpr(N.getOperand(2));
1441       Tmp4 = SelectExpr(N.getOperand(3));
1442       BuildMI(BB, PPC::SUBFC, 2, Result).addReg(Tmp3).addReg(Tmp1);
1443       BuildMI(BB, PPC::SUBFE, 2, Result+1).addReg(Tmp4).addReg(Tmp2);
1444     }
1445     return Result+N.ResNo;
1446   }
1447
1448   case ISD::SHL_PARTS:
1449   case ISD::SRA_PARTS:
1450   case ISD::SRL_PARTS: {
1451     assert(N.getNumOperands() == 3 && N.getValueType() == MVT::i32 &&
1452            "Not an i64 shift!");
1453     unsigned ShiftOpLo = SelectExpr(N.getOperand(0));
1454     unsigned ShiftOpHi = SelectExpr(N.getOperand(1));
1455     unsigned SHReg = FoldIfWideZeroExtend(N.getOperand(2));
1456     Tmp1 = MakeIntReg();
1457     Tmp2 = MakeIntReg();
1458     Tmp3 = MakeIntReg();
1459     unsigned Tmp4 = MakeIntReg();
1460     unsigned Tmp5 = MakeIntReg();
1461     unsigned Tmp6 = MakeIntReg();
1462     BuildMI(BB, PPC::SUBFIC, 2, Tmp1).addReg(SHReg).addSImm(32);
1463     if (ISD::SHL_PARTS == opcode) {
1464       BuildMI(BB, PPC::SLW, 2, Tmp2).addReg(ShiftOpHi).addReg(SHReg);
1465       BuildMI(BB, PPC::SRW, 2, Tmp3).addReg(ShiftOpLo).addReg(Tmp1);
1466       BuildMI(BB, PPC::OR, 2, Tmp4).addReg(Tmp2).addReg(Tmp3);
1467       BuildMI(BB, PPC::ADDI, 2, Tmp5).addReg(SHReg).addSImm(-32);
1468       BuildMI(BB, PPC::SLW, 2, Tmp6).addReg(ShiftOpLo).addReg(Tmp5);
1469       BuildMI(BB, PPC::OR, 2, Result+1).addReg(Tmp4).addReg(Tmp6);
1470       BuildMI(BB, PPC::SLW, 2, Result).addReg(ShiftOpLo).addReg(SHReg);
1471     } else if (ISD::SRL_PARTS == opcode) {
1472       BuildMI(BB, PPC::SRW, 2, Tmp2).addReg(ShiftOpLo).addReg(SHReg);
1473       BuildMI(BB, PPC::SLW, 2, Tmp3).addReg(ShiftOpHi).addReg(Tmp1);
1474       BuildMI(BB, PPC::OR, 2, Tmp4).addReg(Tmp2).addReg(Tmp3);
1475       BuildMI(BB, PPC::ADDI, 2, Tmp5).addReg(SHReg).addSImm(-32);
1476       BuildMI(BB, PPC::SRW, 2, Tmp6).addReg(ShiftOpHi).addReg(Tmp5);
1477       BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp4).addReg(Tmp6);
1478       BuildMI(BB, PPC::SRW, 2, Result+1).addReg(ShiftOpHi).addReg(SHReg);
1479     } else {
1480       MachineBasicBlock *TmpMBB = new MachineBasicBlock(BB->getBasicBlock());
1481       MachineBasicBlock *PhiMBB = new MachineBasicBlock(BB->getBasicBlock());
1482       MachineBasicBlock *OldMBB = BB;
1483       MachineFunction *F = BB->getParent();
1484       ilist<MachineBasicBlock>::iterator It = BB; ++It;
1485       F->getBasicBlockList().insert(It, TmpMBB);
1486       F->getBasicBlockList().insert(It, PhiMBB);
1487       BB->addSuccessor(TmpMBB);
1488       BB->addSuccessor(PhiMBB);
1489       BuildMI(BB, PPC::SRW, 2, Tmp2).addReg(ShiftOpLo).addReg(SHReg);
1490       BuildMI(BB, PPC::SLW, 2, Tmp3).addReg(ShiftOpHi).addReg(Tmp1);
1491       BuildMI(BB, PPC::OR, 2, Tmp4).addReg(Tmp2).addReg(Tmp3);
1492       BuildMI(BB, PPC::ADDICo, 2, Tmp5).addReg(SHReg).addSImm(-32);
1493       BuildMI(BB, PPC::SRAW, 2, Tmp6).addReg(ShiftOpHi).addReg(Tmp5);
1494       BuildMI(BB, PPC::SRAW, 2, Result+1).addReg(ShiftOpHi).addReg(SHReg);
1495       BuildMI(BB, PPC::BLE, 2).addReg(PPC::CR0).addMBB(PhiMBB);
1496       // Select correct least significant half if the shift amount > 32
1497       BB = TmpMBB;
1498       unsigned Tmp7 = MakeIntReg();
1499       BuildMI(BB, PPC::OR, 2, Tmp7).addReg(Tmp6).addReg(Tmp6);
1500       TmpMBB->addSuccessor(PhiMBB);
1501       BB = PhiMBB;
1502       BuildMI(BB, PPC::PHI, 4, Result).addReg(Tmp4).addMBB(OldMBB)
1503         .addReg(Tmp7).addMBB(TmpMBB);
1504     }
1505     return Result+N.ResNo;
1506   }
1507
1508   case ISD::FP_TO_SINT: {
1509     Tmp1 = SelectExpr(N.getOperand(0));
1510     Tmp2 = MakeFPReg();
1511     BuildMI(BB, PPC::FCTIWZ, 1, Tmp2).addReg(Tmp1);
1512     int FrameIdx = BB->getParent()->getFrameInfo()->CreateStackObject(8, 8);
1513     addFrameReference(BuildMI(BB, PPC::STFD, 3).addReg(Tmp2), FrameIdx);
1514     addFrameReference(BuildMI(BB, PPC::LWZ, 2, Result), FrameIdx, 4);
1515     return Result;
1516   }
1517
1518   case ISD::SETCC: {
1519     ISD::CondCode CC = cast<CondCodeSDNode>(Node->getOperand(2))->get();
1520     if (isIntImmediate(Node->getOperand(1), Tmp3)) {
1521       // We can codegen setcc op, imm very efficiently compared to a brcond.
1522       // Check for those cases here.
1523       // setcc op, 0
1524       if (Tmp3 == 0) {
1525         Tmp1 = SelectExpr(Node->getOperand(0));
1526         switch (CC) {
1527         default: Node->dump(); assert(0 && "Unhandled SetCC condition");abort();
1528         case ISD::SETEQ:
1529           Tmp2 = MakeIntReg();
1530           BuildMI(BB, PPC::CNTLZW, 1, Tmp2).addReg(Tmp1);
1531           BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp2).addImm(27)
1532             .addImm(5).addImm(31);
1533           break;
1534         case ISD::SETNE:
1535           Tmp2 = MakeIntReg();
1536           BuildMI(BB, PPC::ADDIC, 2, Tmp2).addReg(Tmp1).addSImm(-1);
1537           BuildMI(BB, PPC::SUBFE, 2, Result).addReg(Tmp2).addReg(Tmp1);
1538           break;
1539         case ISD::SETLT:
1540           BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(1)
1541             .addImm(31).addImm(31);
1542           break;
1543         case ISD::SETGT:
1544           Tmp2 = MakeIntReg();
1545           Tmp3 = MakeIntReg();
1546           BuildMI(BB, PPC::NEG, 2, Tmp2).addReg(Tmp1);
1547           BuildMI(BB, PPC::ANDC, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1548           BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp3).addImm(1)
1549             .addImm(31).addImm(31);
1550           break;
1551         }
1552         return Result;
1553       } else if (Tmp3 == ~0U) {        // setcc op, -1
1554         Tmp1 = SelectExpr(Node->getOperand(0));
1555         switch (CC) {
1556         default: assert(0 && "Unhandled SetCC condition"); abort();
1557         case ISD::SETEQ:
1558           Tmp2 = MakeIntReg();
1559           Tmp3 = MakeIntReg();
1560           BuildMI(BB, PPC::ADDIC, 2, Tmp2).addReg(Tmp1).addSImm(1);
1561           BuildMI(BB, PPC::LI, 1, Tmp3).addSImm(0);
1562           BuildMI(BB, PPC::ADDZE, 1, Result).addReg(Tmp3);
1563           break;
1564         case ISD::SETNE:
1565           Tmp2 = MakeIntReg();
1566           Tmp3 = MakeIntReg();
1567           BuildMI(BB, PPC::NOR, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
1568           BuildMI(BB, PPC::ADDIC, 2, Tmp3).addReg(Tmp2).addSImm(-1);
1569           BuildMI(BB, PPC::SUBFE, 2, Result).addReg(Tmp3).addReg(Tmp2);
1570           break;
1571         case ISD::SETLT:
1572           Tmp2 = MakeIntReg();
1573           Tmp3 = MakeIntReg();
1574           BuildMI(BB, PPC::ADDI, 2, Tmp2).addReg(Tmp1).addSImm(1);
1575           BuildMI(BB, PPC::AND, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1576           BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp3).addImm(1)
1577             .addImm(31).addImm(31);
1578           break;
1579         case ISD::SETGT:
1580           Tmp2 = MakeIntReg();
1581           BuildMI(BB, PPC::RLWINM, 4, Tmp2).addReg(Tmp1).addImm(1)
1582             .addImm(31).addImm(31);
1583           BuildMI(BB, PPC::XORI, 2, Result).addReg(Tmp2).addImm(1);
1584           break;
1585         }
1586         return Result;
1587       }
1588     }
1589
1590     unsigned CCReg = SelectCC(N.getOperand(0), N.getOperand(1), CC);
1591     MoveCRtoGPR(CCReg, CC, Result);
1592     return Result;
1593   }
1594
1595   case ISD::SELECT_CC: {
1596     ISD::CondCode CC = cast<CondCodeSDNode>(N.getOperand(4))->get();
1597     if (!MVT::isInteger(N.getOperand(0).getValueType()) &&
1598         !MVT::isInteger(N.getOperand(2).getValueType()) &&
1599         CC != ISD::SETEQ && CC != ISD::SETNE) {
1600       MVT::ValueType VT = N.getOperand(0).getValueType();
1601       unsigned TV = SelectExpr(N.getOperand(2)); // Use if TRUE
1602       unsigned FV = SelectExpr(N.getOperand(3)); // Use if FALSE
1603
1604       ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N.getOperand(1));
1605       if (CN && (CN->isExactlyValue(-0.0) || CN->isExactlyValue(0.0))) {
1606         switch(CC) {
1607         default: assert(0 && "Invalid FSEL condition"); abort();
1608         case ISD::SETULT:
1609         case ISD::SETLT:
1610           std::swap(TV, FV);  // fsel is natively setge, swap operands for setlt
1611         case ISD::SETUGE:
1612         case ISD::SETGE:
1613           Tmp1 = SelectExpr(N.getOperand(0));   // Val to compare against
1614           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp1).addReg(TV).addReg(FV);
1615           return Result;
1616         case ISD::SETUGT:
1617         case ISD::SETGT:
1618           std::swap(TV, FV);  // fsel is natively setge, swap operands for setlt
1619         case ISD::SETULE:
1620         case ISD::SETLE: {
1621           if (N.getOperand(0).getOpcode() == ISD::FNEG) {
1622             Tmp2 = SelectExpr(N.getOperand(0).getOperand(0));
1623           } else {
1624             Tmp2 = MakeReg(VT);
1625             Tmp1 = SelectExpr(N.getOperand(0));   // Val to compare against
1626             BuildMI(BB, PPC::FNEG, 1, Tmp2).addReg(Tmp1);
1627           }
1628           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp2).addReg(TV).addReg(FV);
1629           return Result;
1630         }
1631         }
1632       } else {
1633         Opc = (MVT::f64 == VT) ? PPC::FSUB : PPC::FSUBS;
1634         Tmp1 = SelectExpr(N.getOperand(0));   // Val to compare against
1635         Tmp2 = SelectExpr(N.getOperand(1));
1636         Tmp3 =  MakeReg(VT);
1637         switch(CC) {
1638         default: assert(0 && "Invalid FSEL condition"); abort();
1639         case ISD::SETULT:
1640         case ISD::SETLT:
1641           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
1642           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(FV).addReg(TV);
1643           return Result;
1644         case ISD::SETUGE:
1645         case ISD::SETGE:
1646           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
1647           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(TV).addReg(FV);
1648           return Result;
1649         case ISD::SETUGT:
1650         case ISD::SETGT:
1651           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1652           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(FV).addReg(TV);
1653           return Result;
1654         case ISD::SETULE:
1655         case ISD::SETLE:
1656           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1657           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(TV).addReg(FV);
1658           return Result;
1659         }
1660       }
1661       assert(0 && "Should never get here");
1662     }
1663
1664     // handle the setcc cases here.  select_cc lhs, 0, 1, 0, cc
1665     ConstantSDNode *N1C = dyn_cast<ConstantSDNode>(N.getOperand(1));
1666     ConstantSDNode *N2C = dyn_cast<ConstantSDNode>(N.getOperand(2));
1667     ConstantSDNode *N3C = dyn_cast<ConstantSDNode>(N.getOperand(3));
1668     if (N1C && N2C && N3C && N1C->isNullValue() && N3C->isNullValue() &&
1669         N2C->getValue() == 1ULL && CC == ISD::SETNE) {
1670       Tmp1 = SelectExpr(Node->getOperand(0));
1671       Tmp2 = MakeIntReg();
1672       BuildMI(BB, PPC::ADDIC, 2, Tmp2).addReg(Tmp1).addSImm(-1);
1673       BuildMI(BB, PPC::SUBFE, 2, Result).addReg(Tmp2).addReg(Tmp1);
1674       return Result;
1675     }
1676
1677     // If the False value only has one use, we can generate better code by
1678     // selecting it in the fallthrough basic block rather than here, which
1679     // increases register pressure.
1680     unsigned TrueValue = SelectExpr(N.getOperand(2));
1681     unsigned FalseValue;
1682
1683     // If the false value is simple enough, evaluate it inline in the false
1684     // block.
1685     if (N.getOperand(3).Val->hasOneUse() &&
1686         (isa<ConstantSDNode>(N.getOperand(3)) ||
1687          isa<ConstantFPSDNode>(N.getOperand(3)) ||
1688          isa<GlobalAddressSDNode>(N.getOperand(3))))
1689       FalseValue = 0;
1690     else
1691       FalseValue = SelectExpr(N.getOperand(3));
1692     unsigned CCReg = SelectCC(N.getOperand(0), N.getOperand(1), CC);
1693     Opc = getBCCForSetCC(CC);
1694
1695     // Create an iterator with which to insert the MBB for copying the false
1696     // value and the MBB to hold the PHI instruction for this SetCC.
1697     MachineBasicBlock *thisMBB = BB;
1698     const BasicBlock *LLVM_BB = BB->getBasicBlock();
1699     ilist<MachineBasicBlock>::iterator It = BB;
1700     ++It;
1701
1702     //  thisMBB:
1703     //  ...
1704     //   TrueVal = ...
1705     //   cmpTY ccX, r1, r2
1706     //   bCC copy1MBB
1707     //   fallthrough --> copy0MBB
1708     MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
1709     MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
1710     BuildMI(BB, Opc, 2).addReg(CCReg).addMBB(sinkMBB);
1711     MachineFunction *F = BB->getParent();
1712     F->getBasicBlockList().insert(It, copy0MBB);
1713     F->getBasicBlockList().insert(It, sinkMBB);
1714     // Update machine-CFG edges
1715     BB->addSuccessor(copy0MBB);
1716     BB->addSuccessor(sinkMBB);
1717
1718     //  copy0MBB:
1719     //   %FalseValue = ...
1720     //   # fallthrough to sinkMBB
1721     BB = copy0MBB;
1722
1723     // If the false value is simple enough, evaluate it here, to avoid it being
1724     // evaluated on the true edge.
1725     if (FalseValue == 0)
1726       FalseValue = SelectExpr(N.getOperand(3));
1727
1728     // Update machine-CFG edges
1729     BB->addSuccessor(sinkMBB);
1730
1731     //  sinkMBB:
1732     //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
1733     //  ...
1734     BB = sinkMBB;
1735     BuildMI(BB, PPC::PHI, 4, Result).addReg(FalseValue)
1736       .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
1737     return Result;
1738   }
1739
1740   case ISD::Constant: {
1741     assert(N.getValueType() == MVT::i32 &&
1742            "Only i32 constants are legal on this target!");
1743     unsigned v = (unsigned)cast<ConstantSDNode>(N)->getValue();
1744     if (isInt16(v)) {
1745       BuildMI(BB, PPC::LI, 1, Result).addSImm(Lo16(v));
1746     } else {
1747       unsigned Hi = Hi16(v);
1748       unsigned Lo = Lo16(v);
1749       if (Lo) {
1750         Tmp1 = MakeIntReg();
1751         BuildMI(BB, PPC::LIS, 1, Tmp1).addSImm(Hi);
1752         BuildMI(BB, PPC::ORI, 2, Result).addReg(Tmp1).addImm(Lo);
1753       } else {
1754         BuildMI(BB, PPC::LIS, 1, Result).addSImm(Hi);
1755       }
1756     }
1757     return Result;
1758   }
1759
1760   case ISD::ConstantFP: {
1761     ConstantFPSDNode *CN = cast<ConstantFPSDNode>(N);
1762     Result = getConstDouble(CN->getValue(), Result);
1763     return Result;
1764   }
1765
1766   case ISD::FNEG:
1767     if (!NoExcessFPPrecision &&
1768         ISD::ADD == N.getOperand(0).getOpcode() &&
1769         N.getOperand(0).Val->hasOneUse() &&
1770         ISD::MUL == N.getOperand(0).getOperand(0).getOpcode() &&
1771         N.getOperand(0).getOperand(0).Val->hasOneUse()) {
1772       ++FusedFP; // Statistic
1773       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(0));
1774       Tmp2 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(1));
1775       Tmp3 = SelectExpr(N.getOperand(0).getOperand(1));
1776       Opc = DestType == MVT::f64 ? PPC::FNMADD : PPC::FNMADDS;
1777       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1778     } else if (!NoExcessFPPrecision &&
1779         ISD::ADD == N.getOperand(0).getOpcode() &&
1780         N.getOperand(0).Val->hasOneUse() &&
1781         ISD::MUL == N.getOperand(0).getOperand(1).getOpcode() &&
1782         N.getOperand(0).getOperand(1).Val->hasOneUse()) {
1783       ++FusedFP; // Statistic
1784       Tmp1 = SelectExpr(N.getOperand(0).getOperand(1).getOperand(0));
1785       Tmp2 = SelectExpr(N.getOperand(0).getOperand(1).getOperand(1));
1786       Tmp3 = SelectExpr(N.getOperand(0).getOperand(0));
1787       Opc = DestType == MVT::f64 ? PPC::FNMADD : PPC::FNMADDS;
1788       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1789     } else if (ISD::FABS == N.getOperand(0).getOpcode()) {
1790       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1791       BuildMI(BB, PPC::FNABS, 1, Result).addReg(Tmp1);
1792     } else {
1793       Tmp1 = SelectExpr(N.getOperand(0));
1794       BuildMI(BB, PPC::FNEG, 1, Result).addReg(Tmp1);
1795     }
1796     return Result;
1797
1798   case ISD::FABS:
1799     Tmp1 = SelectExpr(N.getOperand(0));
1800     BuildMI(BB, PPC::FABS, 1, Result).addReg(Tmp1);
1801     return Result;
1802
1803   case ISD::FSQRT:
1804     Tmp1 = SelectExpr(N.getOperand(0));
1805     Opc = DestType == MVT::f64 ? PPC::FSQRT : PPC::FSQRTS;
1806     BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
1807     return Result;
1808
1809   case ISD::FP_ROUND:
1810     assert (DestType == MVT::f32 &&
1811             N.getOperand(0).getValueType() == MVT::f64 &&
1812             "only f64 to f32 conversion supported here");
1813     Tmp1 = SelectExpr(N.getOperand(0));
1814     BuildMI(BB, PPC::FRSP, 1, Result).addReg(Tmp1);
1815     return Result;
1816
1817   case ISD::FP_EXTEND:
1818     assert (DestType == MVT::f64 &&
1819             N.getOperand(0).getValueType() == MVT::f32 &&
1820             "only f32 to f64 conversion supported here");
1821     Tmp1 = SelectExpr(N.getOperand(0));
1822     BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
1823     return Result;
1824   }
1825   return 0;
1826 }
1827
1828 void ISel::Select(SDOperand N) {
1829   unsigned Tmp1, Tmp2, Tmp3, Opc;
1830   unsigned opcode = N.getOpcode();
1831
1832   if (!ExprMap.insert(std::make_pair(N, 1)).second)
1833     return;  // Already selected.
1834
1835   SDNode *Node = N.Val;
1836
1837   switch (Node->getOpcode()) {
1838   default:
1839     Node->dump(); std::cerr << "\n";
1840     assert(0 && "Node not handled yet!");
1841   case ISD::EntryToken: return;  // Noop
1842   case ISD::TokenFactor:
1843     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
1844       Select(Node->getOperand(i));
1845     return;
1846   case ISD::CALLSEQ_START:
1847   case ISD::CALLSEQ_END:
1848     Select(N.getOperand(0));
1849     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
1850     Opc = N.getOpcode() == ISD::CALLSEQ_START ? PPC::ADJCALLSTACKDOWN :
1851       PPC::ADJCALLSTACKUP;
1852     BuildMI(BB, Opc, 1).addImm(Tmp1);
1853     return;
1854   case ISD::BR: {
1855     MachineBasicBlock *Dest =
1856       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
1857     Select(N.getOperand(0));
1858     BuildMI(BB, PPC::B, 1).addMBB(Dest);
1859     return;
1860   }
1861   case ISD::BR_CC:
1862   case ISD::BRTWOWAY_CC:
1863     SelectBranchCC(N);
1864     return;
1865   case ISD::CopyToReg:
1866     Select(N.getOperand(0));
1867     Tmp1 = SelectExpr(N.getOperand(2));
1868     Tmp2 = cast<RegisterSDNode>(N.getOperand(1))->getReg();
1869
1870     if (Tmp1 != Tmp2) {
1871       if (N.getOperand(2).getValueType() == MVT::f64 ||
1872           N.getOperand(2).getValueType() == MVT::f32)
1873         BuildMI(BB, PPC::FMR, 1, Tmp2).addReg(Tmp1);
1874       else
1875         BuildMI(BB, PPC::OR, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
1876     }
1877     return;
1878   case ISD::ImplicitDef:
1879     Select(N.getOperand(0));
1880     Tmp1 = cast<RegisterSDNode>(N.getOperand(1))->getReg();
1881     if (N.getOperand(1).getValueType() == MVT::i32)
1882       BuildMI(BB, PPC::IMPLICIT_DEF_GPR, 0, Tmp1);
1883     else
1884       BuildMI(BB, PPC::IMPLICIT_DEF_FP, 0, Tmp1);
1885     return;
1886   case ISD::RET:
1887     switch (N.getNumOperands()) {
1888     default:
1889       assert(0 && "Unknown return instruction!");
1890     case 3:
1891       assert(N.getOperand(1).getValueType() == MVT::i32 &&
1892              N.getOperand(2).getValueType() == MVT::i32 &&
1893              "Unknown two-register value!");
1894       Select(N.getOperand(0));
1895       Tmp1 = SelectExpr(N.getOperand(1));
1896       Tmp2 = SelectExpr(N.getOperand(2));
1897       BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp2).addReg(Tmp2);
1898       BuildMI(BB, PPC::OR, 2, PPC::R4).addReg(Tmp1).addReg(Tmp1);
1899       break;
1900     case 2:
1901       Select(N.getOperand(0));
1902       Tmp1 = SelectExpr(N.getOperand(1));
1903       switch (N.getOperand(1).getValueType()) {
1904         default:
1905           assert(0 && "Unknown return type!");
1906         case MVT::f64:
1907         case MVT::f32:
1908           BuildMI(BB, PPC::FMR, 1, PPC::F1).addReg(Tmp1);
1909           break;
1910         case MVT::i32:
1911           BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp1).addReg(Tmp1);
1912           break;
1913       }
1914     case 1:
1915       Select(N.getOperand(0));
1916       break;
1917     }
1918     BuildMI(BB, PPC::BLR, 0); // Just emit a 'ret' instruction
1919     return;
1920   case ISD::TRUNCSTORE:
1921   case ISD::STORE: {
1922     SDOperand Chain   = N.getOperand(0);
1923     SDOperand Value   = N.getOperand(1);
1924     SDOperand Address = N.getOperand(2);
1925     Select(Chain);
1926
1927     Tmp1 = SelectExpr(Value); //value
1928
1929     if (opcode == ISD::STORE) {
1930       switch(Value.getValueType()) {
1931       default: assert(0 && "unknown Type in store");
1932       case MVT::i32: Opc = PPC::STW; break;
1933       case MVT::f64: Opc = PPC::STFD; break;
1934       case MVT::f32: Opc = PPC::STFS; break;
1935       }
1936     } else { //ISD::TRUNCSTORE
1937       switch(cast<VTSDNode>(Node->getOperand(4))->getVT()) {
1938       default: assert(0 && "unknown Type in store");
1939       case MVT::i1:
1940       case MVT::i8: Opc  = PPC::STB; break;
1941       case MVT::i16: Opc = PPC::STH; break;
1942       }
1943     }
1944
1945     if(Address.getOpcode() == ISD::FrameIndex) {
1946       Tmp2 = cast<FrameIndexSDNode>(Address)->getIndex();
1947       addFrameReference(BuildMI(BB, Opc, 3).addReg(Tmp1), (int)Tmp2);
1948     } else {
1949       int offset;
1950       switch(SelectAddr(Address, Tmp2, offset)) {
1951       default: assert(0 && "Unhandled return value from SelectAddr");
1952       case 0:   // imm offset, no frame, no index
1953         BuildMI(BB, Opc, 3).addReg(Tmp1).addSImm(offset).addReg(Tmp2);
1954         break;
1955       case 1:   // imm offset + frame index
1956         addFrameReference(BuildMI(BB, Opc, 3).addReg(Tmp1), (int)Tmp2, offset);
1957         break;
1958       case 2:   // base+index addressing
1959         Opc = IndexedOpForOp(Opc);
1960         BuildMI(BB, Opc, 3).addReg(Tmp1).addReg(Tmp2).addReg(offset);
1961         break;
1962       case 3: {
1963         GlobalAddressSDNode *GN = cast<GlobalAddressSDNode>(Address);
1964         GlobalValue *GV = GN->getGlobal();
1965         BuildMI(BB, Opc, 3).addReg(Tmp1).addGlobalAddress(GV).addReg(Tmp2);
1966       }
1967       }
1968     }
1969     return;
1970   }
1971   case ISD::EXTLOAD:
1972   case ISD::SEXTLOAD:
1973   case ISD::ZEXTLOAD:
1974   case ISD::LOAD:
1975   case ISD::CopyFromReg:
1976   case ISD::TAILCALL:
1977   case ISD::CALL:
1978   case ISD::DYNAMIC_STACKALLOC:
1979     ExprMap.erase(N);
1980     SelectExpr(N);
1981     return;
1982   }
1983   assert(0 && "Should not be reached!");
1984 }
1985
1986
1987 /// createPPC32PatternInstructionSelector - This pass converts an LLVM function
1988 /// into a machine code representation using pattern matching and a machine
1989 /// description file.
1990 ///
1991 FunctionPass *llvm::createPPC32ISelPattern(TargetMachine &TM) {
1992   return new ISel(TM);
1993 }
1994