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