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