lib/Target/PowerPC/PPC64ISelPattern.cpp

   1 //===-- PPC64ISelPattern.cpp - A pattern matching inst selector for PPC64 -===//
   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 64 bit PowerPC.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "PowerPC.h"
  15 #include "PowerPCInstrBuilder.h"
  16 #include "PowerPCInstrInfo.h"
  17 #include "PPC64RegisterInfo.h"
  18 #include "llvm/Constants.h"                   // FIXME: REMOVE
  19 #include "llvm/Function.h"
  20 #include "llvm/CodeGen/MachineConstantPool.h" // FIXME: REMOVE
  21 #include "llvm/CodeGen/MachineFunction.h"
  22 #include "llvm/CodeGen/MachineFrameInfo.h"
  23 #include "llvm/CodeGen/SelectionDAG.h"
  24 #include "llvm/CodeGen/SelectionDAGISel.h"
  25 #include "llvm/CodeGen/SSARegMap.h"
  26 #include "llvm/Target/TargetData.h"
  27 #include "llvm/Target/TargetLowering.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 //===----------------------------------------------------------------------===//
  37 //  PPC32TargetLowering - PPC32 Implementation of the TargetLowering interface
  38 namespace {
  39   class PPC64TargetLowering : public TargetLowering {
  40     int VarArgsFrameIndex;            // FrameIndex for start of varargs area.
  41     int ReturnAddrIndex;              // FrameIndex for return slot.
  42   public:
  43     PPC64TargetLowering(TargetMachine &TM) : TargetLowering(TM) {
  44       // Fold away setcc operations if possible.
  45       setSetCCIsExpensive();
  46
  47       // Set up the register classes.
  48       addRegisterClass(MVT::i64, PPC64::GPRCRegisterClass);
  49       addRegisterClass(MVT::f32, PPC64::FPRCRegisterClass);
  50       addRegisterClass(MVT::f64, PPC64::FPRCRegisterClass);
  51
  52       // PowerPC has no intrinsics for these particular operations
  53       setOperationAction(ISD::BRCONDTWOWAY, MVT::Other, Expand);
  54       setOperationAction(ISD::MEMMOVE, MVT::Other, Expand);
  55       setOperationAction(ISD::MEMSET, MVT::Other, Expand);
  56       setOperationAction(ISD::MEMCPY, MVT::Other, Expand);
  57
  58       // We don't support sin/cos/sqrt/fmod
  59       setOperationAction(ISD::FSIN , MVT::f64, Expand);
  60       setOperationAction(ISD::FCOS , MVT::f64, Expand);
  61       setOperationAction(ISD::FSQRT, MVT::f64, Expand);
  62       setOperationAction(ISD::SREM , MVT::f64, Expand);
  63       setOperationAction(ISD::FSIN , MVT::f32, Expand);
  64       setOperationAction(ISD::FCOS , MVT::f32, Expand);
  65       setOperationAction(ISD::FSQRT, MVT::f32, Expand);
  66       setOperationAction(ISD::SREM , MVT::f32, Expand);
  67
  68       // PPC 64 has i16 and i32 but no i8 (or i1) SEXTLOAD
  69       setOperationAction(ISD::SEXTLOAD, MVT::i1, Expand);
  70       setOperationAction(ISD::SEXTLOAD, MVT::i8, Expand);
  71
  72       // PowerPC has no SREM/UREM instructions
  73       setOperationAction(ISD::SREM, MVT::i64, Expand);
  74       setOperationAction(ISD::UREM, MVT::i64, Expand);
  75
  76       // PowerPC has these, but they are not implemented
  77       setOperationAction(ISD::CTPOP, MVT::i64, Expand);
  78       setOperationAction(ISD::CTTZ , MVT::i64, Expand);
  79       setOperationAction(ISD::CTLZ , MVT::i64, Expand);
  80
  81       setShiftAmountFlavor(Extend);   // shl X, 32 == 0
  82       addLegalFPImmediate(+0.0); // Necessary for FSEL
  83       addLegalFPImmediate(-0.0); //
  84
  85       computeRegisterProperties();
  86     }
  87
  88     /// LowerArguments - This hook must be implemented to indicate how we should
  89     /// lower the arguments for the specified function, into the specified DAG.
  90     virtual std::vector<SDOperand>
  91     LowerArguments(Function &F, SelectionDAG &DAG);
  92
  93     /// LowerCallTo - This hook lowers an abstract call to a function into an
  94     /// actual call.
  95     virtual std::pair<SDOperand, SDOperand>
  96     LowerCallTo(SDOperand Chain, const Type *RetTy, bool isVarArg, unsigned CC,
  97                 SDOperand Callee, ArgListTy &Args, SelectionDAG &DAG);
  98
  99     virtual std::pair<SDOperand, SDOperand>
 100     LowerVAStart(SDOperand Chain, SelectionDAG &DAG);
 101
 102     virtual std::pair<SDOperand,SDOperand>
 103     LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
 104                    const Type *ArgTy, SelectionDAG &DAG);
 105
 106     virtual std::pair<SDOperand, SDOperand>
 107     LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain, unsigned Depth,
 108                             SelectionDAG &DAG);
 109   };
 110 }
 111
 112
 113 std::vector<SDOperand>
 114 PPC64TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
 115   //
 116   // add beautiful description of PPC stack frame format, or at least some docs
 117   //
 118   MachineFunction &MF = DAG.getMachineFunction();
 119   MachineFrameInfo *MFI = MF.getFrameInfo();
 120   MachineBasicBlock& BB = MF.front();
 121   std::vector<SDOperand> ArgValues;
 122
 123   // Due to the rather complicated nature of the PowerPC ABI, rather than a
 124   // fixed size array of physical args, for the sake of simplicity let the STL
 125   // handle tracking them for us.
 126   std::vector<unsigned> argVR, argPR, argOp;
 127   unsigned ArgOffset = 48;
 128   unsigned GPR_remaining = 8;
 129   unsigned FPR_remaining = 13;
 130   unsigned GPR_idx = 0, FPR_idx = 0;
 131   static const unsigned GPR[] = {
 132     PPC::R3, PPC::R4, PPC::R5, PPC::R6,
 133     PPC::R7, PPC::R8, PPC::R9, PPC::R10,
 134   };
 135   static const unsigned FPR[] = {
 136     PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
 137     PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
 138   };
 139
 140   // Add DAG nodes to load the arguments...  On entry to a function on PPC,
 141   // the arguments start at offset 48, although they are likely to be passed
 142   // in registers.
 143   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
 144     SDOperand newroot, argt;
 145     bool needsLoad = false;
 146     MVT::ValueType ObjectVT = getValueType(I->getType());
 147
 148     switch (ObjectVT) {
 149     default: assert(0 && "Unhandled argument type!");
 150     case MVT::i1:
 151     case MVT::i8:
 152     case MVT::i16:
 153     case MVT::i32:
 154     case MVT::i64:
 155       if (GPR_remaining > 0) {
 156         BuildMI(&BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx]);
 157         argt = newroot = DAG.getCopyFromReg(GPR[GPR_idx], MVT::i32,
 158                                             DAG.getRoot());
 159         if (ObjectVT != MVT::i64)
 160           argt = DAG.getNode(ISD::TRUNCATE, ObjectVT, newroot);
 161       } else {
 162         needsLoad = true;
 163       }
 164       break;
 165     case MVT::f32:
 166     case MVT::f64:
 167       if (FPR_remaining > 0) {
 168         BuildMI(&BB, PPC::IMPLICIT_DEF, 0, FPR[FPR_idx]);
 169         argt = newroot = DAG.getCopyFromReg(FPR[FPR_idx], ObjectVT,
 170                                             DAG.getRoot());
 171         --FPR_remaining;
 172         ++FPR_idx;
 173       } else {
 174         needsLoad = true;
 175       }
 176       break;
 177     }
 178
 179     // We need to load the argument to a virtual register if we determined above
 180     // that we ran out of physical registers of the appropriate type
 181     if (needsLoad) {
 182       unsigned SubregOffset = 0;
 183       switch (ObjectVT) {
 184       default: assert(0 && "Unhandled argument type!");
 185       case MVT::i1:
 186       case MVT::i8:   SubregOffset = 7; break;
 187       case MVT::i16:  SubregOffset = 6; break;
 188       case MVT::i32:
 189       case MVT::f32:  SubregOffset = 4; break;
 190       case MVT::i64:
 191       case MVT::f64:  SubregOffset = 0; break;
 192       }
 193       int FI = MFI->CreateFixedObject(8, ArgOffset);
 194       SDOperand FIN = DAG.getFrameIndex(FI, MVT::i64);
 195       FIN = DAG.getNode(ISD::ADD, MVT::i64, FIN,
 196                         DAG.getConstant(SubregOffset, MVT::i64));
 197       argt = newroot = DAG.getLoad(ObjectVT, DAG.getEntryNode(), FIN, DAG.getSrcValue(NULL));
 198     }
 199
 200     // Every 4 bytes of argument space consumes one of the GPRs available for
 201     // argument passing.
 202     if (GPR_remaining > 0) {
 203       --GPR_remaining;
 204       ++GPR_idx;
 205     }
 206     ArgOffset += 8;
 207
 208     DAG.setRoot(newroot.getValue(1));
 209     ArgValues.push_back(argt);
 210   }
 211
 212   // If the function takes variable number of arguments, make a frame index for
 213   // the start of the first vararg value... for expansion of llvm.va_start.
 214   if (F.isVarArg()) {
 215     VarArgsFrameIndex = MFI->CreateFixedObject(8, ArgOffset);
 216     SDOperand FIN = DAG.getFrameIndex(VarArgsFrameIndex, MVT::i64);
 217     // If this function is vararg, store any remaining integer argument regs
 218     // to their spots on the stack so that they may be loaded by deferencing the
 219     // result of va_next.
 220     std::vector<SDOperand> MemOps;
 221     for (; GPR_remaining > 0; --GPR_remaining, ++GPR_idx) {
 222       BuildMI(&BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx]);
 223       SDOperand Val = DAG.getCopyFromReg(GPR[GPR_idx], MVT::i64, DAG.getRoot());
 224       SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, Val.getValue(1),
 225                                     Val, FIN, DAG.getSrcValue(NULL));
 226       MemOps.push_back(Store);
 227       // Increment the address by eight for the next argument to store
 228       SDOperand PtrOff = DAG.getConstant(8, getPointerTy());
 229       FIN = DAG.getNode(ISD::ADD, MVT::i32, FIN, PtrOff);
 230     }
 231     DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, MemOps));
 232   }
 233
 234   return ArgValues;
 235 }
 236
 237 std::pair<SDOperand, SDOperand>
 238 PPC64TargetLowering::LowerCallTo(SDOperand Chain,
 239                                  const Type *RetTy, bool isVarArg,
 240                                  unsigned CallingConv,
 241                                  SDOperand Callee, ArgListTy &Args,
 242                                  SelectionDAG &DAG) {
 243   // args_to_use will accumulate outgoing args for the ISD::CALL case in
 244   // SelectExpr to use to put the arguments in the appropriate registers.
 245   std::vector<SDOperand> args_to_use;
 246
 247   // Count how many bytes are to be pushed on the stack, including the linkage
 248   // area, and parameter passing area.
 249   unsigned NumBytes = 48;
 250
 251   if (Args.empty()) {
 252     Chain = DAG.getNode(ISD::CALLSEQ_START, MVT::Other, Chain,
 253                         DAG.getConstant(NumBytes, getPointerTy()));
 254   } else {
 255     NumBytes = 8 * Args.size(); // All arguments are rounded up to 8 bytes
 256
 257     // Just to be safe, we'll always reserve the full 48 bytes of linkage area
 258     // plus 64 bytes of argument space in case any called code gets funky on us.
 259     if (NumBytes < 112) NumBytes = 112;
 260
 261     // Adjust the stack pointer for the new arguments...
 262     // These operations are automatically eliminated by the prolog/epilog pass
 263     Chain = DAG.getNode(ISD::CALLSEQ_START, MVT::Other, Chain,
 264                         DAG.getConstant(NumBytes, getPointerTy()));
 265
 266     // Set up a copy of the stack pointer for use loading and storing any
 267     // arguments that may not fit in the registers available for argument
 268     // passing.
 269     SDOperand StackPtr = DAG.getCopyFromReg(PPC::R1, MVT::i32,
 270                                             DAG.getEntryNode());
 271
 272     // Figure out which arguments are going to go in registers, and which in
 273     // memory.  Also, if this is a vararg function, floating point operations
 274     // must be stored to our stack, and loaded into integer regs as well, if
 275     // any integer regs are available for argument passing.
 276     unsigned ArgOffset = 48;
 277     unsigned GPR_remaining = 8;
 278     unsigned FPR_remaining = 13;
 279
 280     std::vector<SDOperand> MemOps;
 281     for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 282       // PtrOff will be used to store the current argument to the stack if a
 283       // register cannot be found for it.
 284       SDOperand PtrOff = DAG.getConstant(ArgOffset, getPointerTy());
 285       PtrOff = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff);
 286       MVT::ValueType ArgVT = getValueType(Args[i].second);
 287
 288       switch (ArgVT) {
 289       default: assert(0 && "Unexpected ValueType for argument!");
 290       case MVT::i1:
 291       case MVT::i8:
 292       case MVT::i16:
 293       case MVT::i32:
 294         // Promote the integer to 64 bits.  If the input type is signed use a
 295         // sign extend, otherwise use a zero extend.
 296         if (Args[i].second->isSigned())
 297           Args[i].first =DAG.getNode(ISD::SIGN_EXTEND, MVT::i64, Args[i].first);
 298         else
 299           Args[i].first =DAG.getNode(ISD::ZERO_EXTEND, MVT::i64, Args[i].first);
 300         // FALL THROUGH
 301       case MVT::i64:
 302         if (GPR_remaining > 0) {
 303           args_to_use.push_back(Args[i].first);
 304           --GPR_remaining;
 305         } else {
 306           MemOps.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 307                                           Args[i].first, PtrOff, DAG.getSrcValue(NULL)));
 308         }
 309         ArgOffset += 8;
 310         break;
 311       case MVT::f32:
 312       case MVT::f64:
 313         if (FPR_remaining > 0) {
 314           args_to_use.push_back(Args[i].first);
 315           --FPR_remaining;
 316           if (isVarArg) {
 317             SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, Chain,
 318                                           Args[i].first, PtrOff, DAG.getSrcValue(NULL));
 319             MemOps.push_back(Store);
 320             // Float varargs are always shadowed in available integer registers
 321             if (GPR_remaining > 0) {
 322               SDOperand Load = DAG.getLoad(MVT::i64, Store, PtrOff, DAG.getSrcValue(NULL));
 323               MemOps.push_back(Load);
 324               args_to_use.push_back(Load);
 325               --GPR_remaining;
 326             }
 327           } else {
 328             // If we have any FPRs remaining, we may also have GPRs remaining.
 329             // Args passed in FPRs also consume an available GPR.
 330             if (GPR_remaining > 0) {
 331               args_to_use.push_back(DAG.getNode(ISD::UNDEF, MVT::i64));
 332               --GPR_remaining;
 333             }
 334           }
 335         } else {
 336           MemOps.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 337                                           Args[i].first, PtrOff, DAG.getSrcValue(NULL)));
 338         }
 339         ArgOffset += 8;
 340         break;
 341       }
 342     }
 343     if (!MemOps.empty())
 344       Chain = DAG.getNode(ISD::TokenFactor, MVT::Other, MemOps);
 345   }
 346
 347   std::vector<MVT::ValueType> RetVals;
 348   MVT::ValueType RetTyVT = getValueType(RetTy);
 349   if (RetTyVT != MVT::isVoid)
 350     RetVals.push_back(RetTyVT);
 351   RetVals.push_back(MVT::Other);
 352
 353   SDOperand TheCall = SDOperand(DAG.getCall(RetVals,
 354                                             Chain, Callee, args_to_use), 0);
 355   Chain = TheCall.getValue(RetTyVT != MVT::isVoid);
 356   Chain = DAG.getNode(ISD::CALLSEQ_END, MVT::Other, Chain,
 357                       DAG.getConstant(NumBytes, getPointerTy()));
 358   return std::make_pair(TheCall, Chain);
 359 }
 360
 361 std::pair<SDOperand, SDOperand>
 362 PPC64TargetLowering::LowerVAStart(SDOperand Chain, SelectionDAG &DAG) {
 363   //vastart just returns the address of the VarArgsFrameIndex slot.
 364   return std::make_pair(DAG.getFrameIndex(VarArgsFrameIndex, MVT::i64), Chain);
 365 }
 366
 367 std::pair<SDOperand,SDOperand> PPC64TargetLowering::
 368 LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
 369                const Type *ArgTy, SelectionDAG &DAG) {
 370   MVT::ValueType ArgVT = getValueType(ArgTy);
 371   SDOperand Result;
 372   if (!isVANext) {
 373     Result = DAG.getLoad(ArgVT, DAG.getEntryNode(), VAList, DAG.getSrcValue(NULL));
 374   } else {
 375     Result = DAG.getNode(ISD::ADD, VAList.getValueType(), VAList,
 376                          DAG.getConstant(8, VAList.getValueType()));
 377   }
 378   return std::make_pair(Result, Chain);
 379 }
 380
 381
 382 std::pair<SDOperand, SDOperand> PPC64TargetLowering::
 383 LowerFrameReturnAddress(bool isFrameAddress, SDOperand Chain, unsigned Depth,
 384                         SelectionDAG &DAG) {
 385   assert(0 && "LowerFrameReturnAddress unimplemented");
 386   abort();
 387 }
 388
 389 namespace {
 390 Statistic<>NotLogic("ppc-codegen", "Number of inverted logical ops");
 391 Statistic<>FusedFP("ppc-codegen", "Number of fused fp operations");
 392 //===--------------------------------------------------------------------===//
 393 /// ISel - PPC32 specific code to select PPC32 machine instructions for
 394 /// SelectionDAG operations.
 395 //===--------------------------------------------------------------------===//
 396 class ISel : public SelectionDAGISel {
 397
 398   /// Comment Here.
 399   PPC64TargetLowering PPC64Lowering;
 400
 401   /// ExprMap - As shared expressions are codegen'd, we keep track of which
 402   /// vreg the value is produced in, so we only emit one copy of each compiled
 403   /// tree.
 404   std::map<SDOperand, unsigned> ExprMap;
 405
 406   unsigned GlobalBaseReg;
 407   bool GlobalBaseInitialized;
 408
 409 public:
 410   ISel(TargetMachine &TM) : SelectionDAGISel(PPC64Lowering), PPC64Lowering(TM)
 411   {}
 412
 413   /// runOnFunction - Override this function in order to reset our per-function
 414   /// variables.
 415   virtual bool runOnFunction(Function &Fn) {
 416     // Make sure we re-emit a set of the global base reg if necessary
 417     GlobalBaseInitialized = false;
 418     return SelectionDAGISel::runOnFunction(Fn);
 419   }
 420
 421   /// InstructionSelectBasicBlock - This callback is invoked by
 422   /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 423   virtual void InstructionSelectBasicBlock(SelectionDAG &DAG) {
 424     DEBUG(BB->dump());
 425     // Codegen the basic block.
 426     Select(DAG.getRoot());
 427
 428     // Clear state used for selection.
 429     ExprMap.clear();
 430   }
 431
 432   unsigned getGlobalBaseReg();
 433   unsigned getConstDouble(double floatVal, unsigned Result);
 434   unsigned SelectSetCR0(SDOperand CC);
 435   unsigned SelectExpr(SDOperand N);
 436   unsigned SelectExprFP(SDOperand N, unsigned Result);
 437   void Select(SDOperand N);
 438
 439   bool SelectAddr(SDOperand N, unsigned& Reg, int& offset);
 440   void SelectBranchCC(SDOperand N);
 441 };
 442
 443 /// ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
 444 /// returns zero when the input is not exactly a power of two.
 445 static unsigned ExactLog2(unsigned Val) {
 446   if (Val == 0 || (Val & (Val-1))) return 0;
 447   unsigned Count = 0;
 448   while (Val != 1) {
 449     Val >>= 1;
 450     ++Count;
 451   }
 452   return Count;
 453 }
 454
 455 /// getImmediateForOpcode - This method returns a value indicating whether
 456 /// the ConstantSDNode N can be used as an immediate to Opcode.  The return
 457 /// values are either 0, 1 or 2.  0 indicates that either N is not a
 458 /// ConstantSDNode, or is not suitable for use by that opcode.  A return value
 459 /// of 1 indicates that the constant may be used in normal immediate form.  A
 460 /// return value of 2 indicates that the constant may be used in shifted
 461 /// immediate form.  A return value of 3 indicates that log base 2 of the
 462 /// constant may be used.
 463 ///
 464 static unsigned getImmediateForOpcode(SDOperand N, unsigned Opcode,
 465                                       unsigned& Imm, bool U = false) {
 466   if (N.getOpcode() != ISD::Constant) return 0;
 467
 468   int v = (int)cast<ConstantSDNode>(N)->getSignExtended();
 469
 470   switch(Opcode) {
 471   default: return 0;
 472   case ISD::ADD:
 473     if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
 474     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
 475     break;
 476   case ISD::AND:
 477   case ISD::XOR:
 478   case ISD::OR:
 479     if (v >= 0 && v <= 65535) { Imm = v & 0xFFFF; return 1; }
 480     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
 481     break;
 482   case ISD::MUL:
 483   case ISD::SUB:
 484     if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
 485     break;
 486   case ISD::SETCC:
 487     if (U && (v >= 0 && v <= 65535)) { Imm = v & 0xFFFF; return 1; }
 488     if (!U && (v <= 32767 && v >= -32768)) { Imm = v & 0xFFFF; return 1; }
 489     break;
 490   case ISD::SDIV:
 491     if ((Imm = ExactLog2(v))) { return 3; }
 492     break;
 493   }
 494   return 0;
 495 }
 496
 497 /// getBCCForSetCC - Returns the PowerPC condition branch mnemonic corresponding
 498 /// to Condition.  If the Condition is unordered or unsigned, the bool argument
 499 /// U is set to true, otherwise it is set to false.
 500 static unsigned getBCCForSetCC(unsigned Condition, bool& U) {
 501   U = false;
 502   switch (Condition) {
 503   default: assert(0 && "Unknown condition!"); abort();
 504   case ISD::SETEQ:  return PPC::BEQ;
 505   case ISD::SETNE:  return PPC::BNE;
 506   case ISD::SETULT: U = true;
 507   case ISD::SETLT:  return PPC::BLT;
 508   case ISD::SETULE: U = true;
 509   case ISD::SETLE:  return PPC::BLE;
 510   case ISD::SETUGT: U = true;
 511   case ISD::SETGT:  return PPC::BGT;
 512   case ISD::SETUGE: U = true;
 513   case ISD::SETGE:  return PPC::BGE;
 514   }
 515   return 0;
 516 }
 517
 518 /// IndexedOpForOp - Return the indexed variant for each of the PowerPC load
 519 /// and store immediate instructions.
 520 static unsigned IndexedOpForOp(unsigned Opcode) {
 521   switch(Opcode) {
 522   default: assert(0 && "Unknown opcode!"); abort();
 523   case PPC::LBZ: return PPC::LBZX;  case PPC::STB: return PPC::STBX;
 524   case PPC::LHZ: return PPC::LHZX;  case PPC::STH: return PPC::STHX;
 525   case PPC::LHA: return PPC::LHAX;  case PPC::STW: return PPC::STWX;
 526   case PPC::LWZ: return PPC::LWZX;  case PPC::STD: return PPC::STDX;
 527   case PPC::LD:  return PPC::LDX;   case PPC::STFS: return PPC::STFSX;
 528   case PPC::LFS: return PPC::LFSX;  case PPC::STFD: return PPC::STFDX;
 529   case PPC::LFD: return PPC::LFDX;
 530   }
 531   return 0;
 532 }
 533 }
 534
 535 /// getGlobalBaseReg - Output the instructions required to put the
 536 /// base address to use for accessing globals into a register.
 537 ///
 538 unsigned ISel::getGlobalBaseReg() {
 539   if (!GlobalBaseInitialized) {
 540     // Insert the set of GlobalBaseReg into the first MBB of the function
 541     MachineBasicBlock &FirstMBB = BB->getParent()->front();
 542     MachineBasicBlock::iterator MBBI = FirstMBB.begin();
 543     GlobalBaseReg = MakeReg(MVT::i64);
 544     BuildMI(FirstMBB, MBBI, PPC::MovePCtoLR, 0, PPC::LR);
 545     BuildMI(FirstMBB, MBBI, PPC::MFLR, 1, GlobalBaseReg).addReg(PPC::LR);
 546     GlobalBaseInitialized = true;
 547   }
 548   return GlobalBaseReg;
 549 }
 550
 551 /// getConstDouble - Loads a floating point value into a register, via the
 552 /// Constant Pool.  Optionally takes a register in which to load the value.
 553 unsigned ISel::getConstDouble(double doubleVal, unsigned Result=0) {
 554   unsigned Tmp1 = MakeReg(MVT::i64);
 555   if (0 == Result) Result = MakeReg(MVT::f64);
 556   MachineConstantPool *CP = BB->getParent()->getConstantPool();
 557   ConstantFP *CFP = ConstantFP::get(Type::DoubleTy, doubleVal);
 558   unsigned CPI = CP->getConstantPoolIndex(CFP);
 559   BuildMI(BB, PPC::LOADHiAddr, 2, Tmp1).addReg(getGlobalBaseReg())
 560     .addConstantPoolIndex(CPI);
 561   BuildMI(BB, PPC::LFD, 2, Result).addConstantPoolIndex(CPI).addReg(Tmp1);
 562   return Result;
 563 }
 564
 565 unsigned ISel::SelectSetCR0(SDOperand CC) {
 566   unsigned Opc, Tmp1, Tmp2;
 567   static const unsigned CompareOpcodes[] =
 568     { PPC::FCMPU, PPC::FCMPU, PPC::CMPW, PPC::CMPLW };
 569
 570   // If the first operand to the select is a SETCC node, then we can fold it
 571   // into the branch that selects which value to return.
 572   SetCCSDNode* SetCC = dyn_cast<SetCCSDNode>(CC.Val);
 573   if (SetCC && CC.getOpcode() == ISD::SETCC) {
 574     bool U;
 575     Opc = getBCCForSetCC(SetCC->getCondition(), U);
 576     Tmp1 = SelectExpr(SetCC->getOperand(0));
 577
 578     // Pass the optional argument U to getImmediateForOpcode for SETCC,
 579     // so that it knows whether the SETCC immediate range is signed or not.
 580     if (1 == getImmediateForOpcode(SetCC->getOperand(1), ISD::SETCC,
 581                                    Tmp2, U)) {
 582       if (U)
 583         BuildMI(BB, PPC::CMPLWI, 2, PPC::CR0).addReg(Tmp1).addImm(Tmp2);
 584       else
 585         BuildMI(BB, PPC::CMPWI, 2, PPC::CR0).addReg(Tmp1).addSImm(Tmp2);
 586     } else {
 587       bool IsInteger = MVT::isInteger(SetCC->getOperand(0).getValueType());
 588       unsigned CompareOpc = CompareOpcodes[2 * IsInteger + U];
 589       Tmp2 = SelectExpr(SetCC->getOperand(1));
 590       BuildMI(BB, CompareOpc, 2, PPC::CR0).addReg(Tmp1).addReg(Tmp2);
 591     }
 592   } else {
 593     Tmp1 = SelectExpr(CC);
 594     BuildMI(BB, PPC::CMPLWI, 2, PPC::CR0).addReg(Tmp1).addImm(0);
 595     Opc = PPC::BNE;
 596   }
 597   return Opc;
 598 }
 599
 600 /// Check to see if the load is a constant offset from a base register
 601 bool ISel::SelectAddr(SDOperand N, unsigned& Reg, int& offset)
 602 {
 603   unsigned imm = 0, opcode = N.getOpcode();
 604   if (N.getOpcode() == ISD::ADD) {
 605     Reg = SelectExpr(N.getOperand(0));
 606     if (1 == getImmediateForOpcode(N.getOperand(1), opcode, imm)) {
 607       offset = imm;
 608       return false;
 609     }
 610     offset = SelectExpr(N.getOperand(1));
 611     return true;
 612   }
 613   Reg = SelectExpr(N);
 614   offset = 0;
 615   return false;
 616 }
 617
 618 void ISel::SelectBranchCC(SDOperand N)
 619 {
 620   assert(N.getOpcode() == ISD::BRCOND && "Not a BranchCC???");
 621   MachineBasicBlock *Dest =
 622     cast<BasicBlockSDNode>(N.getOperand(2))->getBasicBlock();
 623
 624   // Get the MBB we will fall through to so that we can hand it off to the
 625   // branch selection pass as an argument to the PPC::COND_BRANCH pseudo op.
 626   //ilist<MachineBasicBlock>::iterator It = BB;
 627   //MachineBasicBlock *Fallthrough = ++It;
 628
 629   Select(N.getOperand(0));  //chain
 630   unsigned Opc = SelectSetCR0(N.getOperand(1));
 631   // FIXME: Use this once we have something approximating two-way branches
 632   // We cannot currently use this in case the ISel hands us something like
 633   // BRcc MBBx
 634   // BR MBBy
 635   // since the fallthrough basic block for the conditional branch does not start
 636   // with the unconditional branch (it is skipped over).
 637   //BuildMI(BB, PPC::COND_BRANCH, 4).addReg(PPC::CR0).addImm(Opc)
 638   //  .addMBB(Dest).addMBB(Fallthrough);
 639   BuildMI(BB, Opc, 2).addReg(PPC::CR0).addMBB(Dest);
 640   return;
 641 }
 642
 643 unsigned ISel::SelectExprFP(SDOperand N, unsigned Result)
 644 {
 645   unsigned Tmp1, Tmp2, Tmp3;
 646   unsigned Opc = 0;
 647   SDNode *Node = N.Val;
 648   MVT::ValueType DestType = N.getValueType();
 649   unsigned opcode = N.getOpcode();
 650
 651   switch (opcode) {
 652   default:
 653     Node->dump();
 654     assert(0 && "Node not handled!\n");
 655
 656   case ISD::SELECT: {
 657     // Attempt to generate FSEL.  We can do this whenever we have an FP result,
 658     // and an FP comparison in the SetCC node.
 659     SetCCSDNode* SetCC = dyn_cast<SetCCSDNode>(N.getOperand(0).Val);
 660     if (SetCC && N.getOperand(0).getOpcode() == ISD::SETCC &&
 661         !MVT::isInteger(SetCC->getOperand(0).getValueType()) &&
 662         SetCC->getCondition() != ISD::SETEQ &&
 663         SetCC->getCondition() != ISD::SETNE) {
 664       MVT::ValueType VT = SetCC->getOperand(0).getValueType();
 665       Tmp1 = SelectExpr(SetCC->getOperand(0));   // Val to compare against
 666       unsigned TV = SelectExpr(N.getOperand(1)); // Use if TRUE
 667       unsigned FV = SelectExpr(N.getOperand(2)); // Use if FALSE
 668
 669       ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(SetCC->getOperand(1));
 670       if (CN && (CN->isExactlyValue(-0.0) || CN->isExactlyValue(0.0))) {
 671         switch(SetCC->getCondition()) {
 672         default: assert(0 && "Invalid FSEL condition"); abort();
 673         case ISD::SETULT:
 674         case ISD::SETLT:
 675           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp1).addReg(FV).addReg(TV);
 676           return Result;
 677         case ISD::SETUGE:
 678         case ISD::SETGE:
 679           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp1).addReg(TV).addReg(FV);
 680           return Result;
 681         case ISD::SETUGT:
 682         case ISD::SETGT: {
 683           Tmp2 = MakeReg(VT);
 684           BuildMI(BB, PPC::FNEG, 1, Tmp2).addReg(Tmp1);
 685           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp2).addReg(FV).addReg(TV);
 686           return Result;
 687         }
 688         case ISD::SETULE:
 689         case ISD::SETLE: {
 690           Tmp2 = MakeReg(VT);
 691           BuildMI(BB, PPC::FNEG, 1, Tmp2).addReg(Tmp1);
 692           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp2).addReg(TV).addReg(FV);
 693           return Result;
 694         }
 695         }
 696       } else {
 697         Opc = (MVT::f64 == VT) ? PPC::FSUB : PPC::FSUBS;
 698         Tmp2 = SelectExpr(SetCC->getOperand(1));
 699         Tmp3 =  MakeReg(VT);
 700         switch(SetCC->getCondition()) {
 701         default: assert(0 && "Invalid FSEL condition"); abort();
 702         case ISD::SETULT:
 703         case ISD::SETLT:
 704           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
 705           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(FV).addReg(TV);
 706           return Result;
 707         case ISD::SETUGE:
 708         case ISD::SETGE:
 709           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
 710           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(TV).addReg(FV);
 711           return Result;
 712         case ISD::SETUGT:
 713         case ISD::SETGT:
 714           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
 715           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(FV).addReg(TV);
 716           return Result;
 717         case ISD::SETULE:
 718         case ISD::SETLE:
 719           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
 720           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(TV).addReg(FV);
 721           return Result;
 722         }
 723       }
 724       assert(0 && "Should never get here");
 725       return 0;
 726     }
 727
 728     unsigned TrueValue = SelectExpr(N.getOperand(1)); //Use if TRUE
 729     unsigned FalseValue = SelectExpr(N.getOperand(2)); //Use if FALSE
 730     Opc = SelectSetCR0(N.getOperand(0));
 731
 732     // Create an iterator with which to insert the MBB for copying the false
 733     // value and the MBB to hold the PHI instruction for this SetCC.
 734     MachineBasicBlock *thisMBB = BB;
 735     const BasicBlock *LLVM_BB = BB->getBasicBlock();
 736     ilist<MachineBasicBlock>::iterator It = BB;
 737     ++It;
 738
 739     //  thisMBB:
 740     //  ...
 741     //   TrueVal = ...
 742     //   cmpTY cr0, r1, r2
 743     //   bCC copy1MBB
 744     //   fallthrough --> copy0MBB
 745     MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
 746     MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
 747     BuildMI(BB, Opc, 2).addReg(PPC::CR0).addMBB(sinkMBB);
 748     MachineFunction *F = BB->getParent();
 749     F->getBasicBlockList().insert(It, copy0MBB);
 750     F->getBasicBlockList().insert(It, sinkMBB);
 751     // Update machine-CFG edges
 752     BB->addSuccessor(copy0MBB);
 753     BB->addSuccessor(sinkMBB);
 754
 755     //  copy0MBB:
 756     //   %FalseValue = ...
 757     //   # fallthrough to sinkMBB
 758     BB = copy0MBB;
 759     // Update machine-CFG edges
 760     BB->addSuccessor(sinkMBB);
 761
 762     //  sinkMBB:
 763     //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
 764     //  ...
 765     BB = sinkMBB;
 766     BuildMI(BB, PPC::PHI, 4, Result).addReg(FalseValue)
 767       .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
 768     return Result;
 769   }
 770
 771   case ISD::FNEG:
 772     if (!NoExcessFPPrecision &&
 773         ISD::ADD == N.getOperand(0).getOpcode() &&
 774         N.getOperand(0).Val->hasOneUse() &&
 775         ISD::MUL == N.getOperand(0).getOperand(0).getOpcode() &&
 776         N.getOperand(0).getOperand(0).Val->hasOneUse()) {
 777       ++FusedFP; // Statistic
 778       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(0));
 779       Tmp2 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(1));
 780       Tmp3 = SelectExpr(N.getOperand(0).getOperand(1));
 781       Opc = DestType == MVT::f64 ? PPC::FNMADD : PPC::FNMADDS;
 782       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
 783     } else if (!NoExcessFPPrecision &&
 784         ISD::SUB == N.getOperand(0).getOpcode() &&
 785         N.getOperand(0).Val->hasOneUse() &&
 786         ISD::MUL == N.getOperand(0).getOperand(0).getOpcode() &&
 787         N.getOperand(0).getOperand(0).Val->hasOneUse()) {
 788       ++FusedFP; // Statistic
 789       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(0));
 790       Tmp2 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(1));
 791       Tmp3 = SelectExpr(N.getOperand(0).getOperand(1));
 792       Opc = DestType == MVT::f64 ? PPC::FNMSUB : PPC::FNMSUBS;
 793       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
 794     } else if (ISD::FABS == N.getOperand(0).getOpcode()) {
 795       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
 796       BuildMI(BB, PPC::FNABS, 1, Result).addReg(Tmp1);
 797     } else {
 798       Tmp1 = SelectExpr(N.getOperand(0));
 799       BuildMI(BB, PPC::FNEG, 1, Result).addReg(Tmp1);
 800     }
 801     return Result;
 802
 803   case ISD::FABS:
 804     Tmp1 = SelectExpr(N.getOperand(0));
 805     BuildMI(BB, PPC::FABS, 1, Result).addReg(Tmp1);
 806     return Result;
 807
 808   case ISD::FP_ROUND:
 809     assert (DestType == MVT::f32 &&
 810             N.getOperand(0).getValueType() == MVT::f64 &&
 811             "only f64 to f32 conversion supported here");
 812     Tmp1 = SelectExpr(N.getOperand(0));
 813     BuildMI(BB, PPC::FRSP, 1, Result).addReg(Tmp1);
 814     return Result;
 815
 816   case ISD::FP_EXTEND:
 817     assert (DestType == MVT::f64 &&
 818             N.getOperand(0).getValueType() == MVT::f32 &&
 819             "only f32 to f64 conversion supported here");
 820     Tmp1 = SelectExpr(N.getOperand(0));
 821     BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
 822     return Result;
 823
 824   case ISD::CopyFromReg:
 825     if (Result == 1)
 826       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 827     Tmp1 = dyn_cast<RegSDNode>(Node)->getReg();
 828     BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
 829     return Result;
 830
 831   case ISD::ConstantFP: {
 832     ConstantFPSDNode *CN = cast<ConstantFPSDNode>(N);
 833     Result = getConstDouble(CN->getValue(), Result);
 834     return Result;
 835   }
 836
 837   case ISD::ADD:
 838     if (!NoExcessFPPrecision && N.getOperand(0).getOpcode() == ISD::MUL &&
 839         N.getOperand(0).Val->hasOneUse()) {
 840       ++FusedFP; // Statistic
 841       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
 842       Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
 843       Tmp3 = SelectExpr(N.getOperand(1));
 844       Opc = DestType == MVT::f64 ? PPC::FMADD : PPC::FMADDS;
 845       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
 846       return Result;
 847     }
 848     Opc = DestType == MVT::f64 ? PPC::FADD : PPC::FADDS;
 849     Tmp1 = SelectExpr(N.getOperand(0));
 850     Tmp2 = SelectExpr(N.getOperand(1));
 851     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
 852     return Result;
 853
 854   case ISD::SUB:
 855     if (!NoExcessFPPrecision && N.getOperand(0).getOpcode() == ISD::MUL &&
 856         N.getOperand(0).Val->hasOneUse()) {
 857       ++FusedFP; // Statistic
 858       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
 859       Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
 860       Tmp3 = SelectExpr(N.getOperand(1));
 861       Opc = DestType == MVT::f64 ? PPC::FMSUB : PPC::FMSUBS;
 862       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
 863       return Result;
 864     }
 865     Opc = DestType == MVT::f64 ? PPC::FSUB : PPC::FSUBS;
 866     Tmp1 = SelectExpr(N.getOperand(0));
 867     Tmp2 = SelectExpr(N.getOperand(1));
 868     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
 869     return Result;
 870
 871   case ISD::MUL:
 872   case ISD::SDIV:
 873     switch( opcode ) {
 874     case ISD::MUL:  Opc = DestType == MVT::f64 ? PPC::FMUL : PPC::FMULS; break;
 875     case ISD::SDIV: Opc = DestType == MVT::f64 ? PPC::FDIV : PPC::FDIVS; break;
 876     };
 877     Tmp1 = SelectExpr(N.getOperand(0));
 878     Tmp2 = SelectExpr(N.getOperand(1));
 879     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
 880     return Result;
 881
 882   case ISD::UINT_TO_FP:
 883   case ISD::SINT_TO_FP: {
 884     bool IsUnsigned = (ISD::UINT_TO_FP == opcode);
 885     Tmp1 = SelectExpr(N.getOperand(0));  // Get the operand register
 886     Tmp2 = MakeReg(MVT::f64); // temp reg to load the integer value into
 887     Tmp3 = MakeReg(MVT::i64); // temp reg to hold the conversion constant
 888     unsigned ConstF = MakeReg(MVT::f64); // temp reg to hold the fp constant
 889
 890     int FrameIdx = BB->getParent()->getFrameInfo()->CreateStackObject(8, 8);
 891     MachineConstantPool *CP = BB->getParent()->getConstantPool();
 892
 893     // FIXME: pull this FP constant generation stuff out into something like
 894     // the simple ISel's getReg.
 895     if (IsUnsigned) {
 896       addFrameReference(BuildMI(BB, PPC::STD, 3).addReg(Tmp1), FrameIdx);
 897       addFrameReference(BuildMI(BB, PPC::LFD, 2, Tmp2), FrameIdx);
 898       BuildMI(BB, PPC::FCFID, 1, Result).addReg(Tmp2);
 899     } else {
 900       ConstantFP *CFP = ConstantFP::get(Type::DoubleTy, 0x1.000008p52);
 901       unsigned CPI = CP->getConstantPoolIndex(CFP);
 902       // Load constant fp value
 903       unsigned Tmp4 = MakeReg(MVT::i32);
 904       unsigned TmpL = MakeReg(MVT::i32);
 905       BuildMI(BB, PPC::LOADHiAddr, 2, Tmp4).addReg(getGlobalBaseReg())
 906         .addConstantPoolIndex(CPI);
 907       BuildMI(BB, PPC::LFD, 2, ConstF).addConstantPoolIndex(CPI).addReg(Tmp4);
 908       // Store the hi & low halves of the fp value, currently in int regs
 909       BuildMI(BB, PPC::LIS, 1, Tmp3).addSImm(0x4330);
 910       addFrameReference(BuildMI(BB, PPC::STW, 3).addReg(Tmp3), FrameIdx);
 911       BuildMI(BB, PPC::XORIS, 2, TmpL).addReg(Tmp1).addImm(0x8000);
 912       addFrameReference(BuildMI(BB, PPC::STW, 3).addReg(TmpL), FrameIdx, 4);
 913       addFrameReference(BuildMI(BB, PPC::LFD, 2, Tmp2), FrameIdx);
 914       // Generate the return value with a subtract
 915       BuildMI(BB, PPC::FSUB, 2, Result).addReg(Tmp2).addReg(ConstF);
 916     }
 917     return Result;
 918   }
 919   }
 920   assert(0 && "Should never get here");
 921   return 0;
 922 }
 923
 924 unsigned ISel::SelectExpr(SDOperand N) {
 925   unsigned Result;
 926   unsigned Tmp1, Tmp2, Tmp3;
 927   unsigned Opc = 0;
 928   unsigned opcode = N.getOpcode();
 929
 930   SDNode *Node = N.Val;
 931   MVT::ValueType DestType = N.getValueType();
 932
 933   unsigned &Reg = ExprMap[N];
 934   if (Reg) return Reg;
 935
 936   switch (N.getOpcode()) {
 937   default:
 938     Reg = Result = (N.getValueType() != MVT::Other) ?
 939                             MakeReg(N.getValueType()) : 1;
 940     break;
 941   case ISD::CALL:
 942     // If this is a call instruction, make sure to prepare ALL of the result
 943     // values as well as the chain.
 944     if (Node->getNumValues() == 1)
 945       Reg = Result = 1;  // Void call, just a chain.
 946     else {
 947       Result = MakeReg(Node->getValueType(0));
 948       ExprMap[N.getValue(0)] = Result;
 949       for (unsigned i = 1, e = N.Val->getNumValues()-1; i != e; ++i)
 950         ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
 951       ExprMap[SDOperand(Node, Node->getNumValues()-1)] = 1;
 952     }
 953     break;
 954   }
 955
 956   if (ISD::CopyFromReg == opcode)
 957     DestType = N.getValue(0).getValueType();
 958
 959   if (DestType == MVT::f64 || DestType == MVT::f32)
 960     if (ISD::LOAD != opcode && ISD::EXTLOAD != opcode && ISD::UNDEF != opcode)
 961       return SelectExprFP(N, Result);
 962
 963   switch (opcode) {
 964   default:
 965     Node->dump();
 966     assert(0 && "Node not handled!\n");
 967   case ISD::UNDEF:
 968     BuildMI(BB, PPC::IMPLICIT_DEF, 0, Result);
 969     return Result;
 970   case ISD::DYNAMIC_STACKALLOC:
 971     // Generate both result values.  FIXME: Need a better commment here?
 972     if (Result != 1)
 973       ExprMap[N.getValue(1)] = 1;
 974     else
 975       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
 976
 977     // FIXME: We are currently ignoring the requested alignment for handling
 978     // greater than the stack alignment.  This will need to be revisited at some
 979     // point.  Align = N.getOperand(2);
 980     if (!isa<ConstantSDNode>(N.getOperand(2)) ||
 981         cast<ConstantSDNode>(N.getOperand(2))->getValue() != 0) {
 982       std::cerr << "Cannot allocate stack object with greater alignment than"
 983                 << " the stack alignment yet!";
 984       abort();
 985     }
 986     Select(N.getOperand(0));
 987     Tmp1 = SelectExpr(N.getOperand(1));
 988     // Subtract size from stack pointer, thereby allocating some space.
 989     BuildMI(BB, PPC::SUBF, 2, PPC::R1).addReg(Tmp1).addReg(PPC::R1);
 990     // Put a pointer to the space into the result register by copying the SP
 991     BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R1).addReg(PPC::R1);
 992     return Result;
 993
 994   case ISD::ConstantPool:
 995     Tmp1 = cast<ConstantPoolSDNode>(N)->getIndex();
 996     Tmp2 = MakeReg(MVT::i64);
 997     BuildMI(BB, PPC::LOADHiAddr, 2, Tmp2).addReg(getGlobalBaseReg())
 998       .addConstantPoolIndex(Tmp1);
 999     BuildMI(BB, PPC::LA, 2, Result).addReg(Tmp2).addConstantPoolIndex(Tmp1);
1000     return Result;
1001
1002   case ISD::FrameIndex:
1003     Tmp1 = cast<FrameIndexSDNode>(N)->getIndex();
1004     addFrameReference(BuildMI(BB, PPC::ADDI, 2, Result), (int)Tmp1, 0, false);
1005     return Result;
1006
1007   case ISD::GlobalAddress: {
1008     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
1009     Tmp1 = MakeReg(MVT::i64);
1010     BuildMI(BB, PPC::LOADHiAddr, 2, Tmp1).addReg(getGlobalBaseReg())
1011       .addGlobalAddress(GV);
1012     if (GV->hasWeakLinkage() || GV->isExternal()) {
1013       BuildMI(BB, PPC::LD, 2, Result).addGlobalAddress(GV).addReg(Tmp1);
1014     } else {
1015       BuildMI(BB, PPC::LA, 2, Result).addReg(Tmp1).addGlobalAddress(GV);
1016     }
1017     return Result;
1018   }
1019
1020   case ISD::LOAD:
1021   case ISD::EXTLOAD:
1022   case ISD::ZEXTLOAD:
1023   case ISD::SEXTLOAD: {
1024     MVT::ValueType TypeBeingLoaded = (ISD::LOAD == opcode) ?
1025       Node->getValueType(0) : cast<MVTSDNode>(Node)->getExtraValueType();
1026     bool sext = (ISD::SEXTLOAD == opcode);
1027
1028     // Make sure we generate both values.
1029     if (Result != 1)
1030       ExprMap[N.getValue(1)] = 1;   // Generate the token
1031     else
1032       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1033
1034     SDOperand Chain   = N.getOperand(0);
1035     SDOperand Address = N.getOperand(1);
1036     Select(Chain);
1037
1038     switch (TypeBeingLoaded) {
1039     default: Node->dump(); assert(0 && "Cannot load this type!");
1040     case MVT::i1:  Opc = PPC::LBZ; break;
1041     case MVT::i8:  Opc = PPC::LBZ; break;
1042     case MVT::i16: Opc = sext ? PPC::LHA : PPC::LHZ; break;
1043     case MVT::i32: Opc = sext ? PPC::LWA : PPC::LWZ; break;
1044     case MVT::i64: Opc = PPC::LD;  break;
1045     case MVT::f32: Opc = PPC::LFS; break;
1046     case MVT::f64: Opc = PPC::LFD; break;
1047     }
1048
1049     if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Address)) {
1050       Tmp1 = MakeReg(MVT::i64);
1051       int CPI = CP->getIndex();
1052       BuildMI(BB, PPC::LOADHiAddr, 2, Tmp1).addReg(getGlobalBaseReg())
1053         .addConstantPoolIndex(CPI);
1054       BuildMI(BB, Opc, 2, Result).addConstantPoolIndex(CPI).addReg(Tmp1);
1055     }
1056     else if(Address.getOpcode() == ISD::FrameIndex) {
1057       Tmp1 = cast<FrameIndexSDNode>(Address)->getIndex();
1058       addFrameReference(BuildMI(BB, Opc, 2, Result), (int)Tmp1);
1059     } else {
1060       int offset;
1061       bool idx = SelectAddr(Address, Tmp1, offset);
1062       if (idx) {
1063         Opc = IndexedOpForOp(Opc);
1064         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(offset);
1065       } else {
1066         BuildMI(BB, Opc, 2, Result).addSImm(offset).addReg(Tmp1);
1067       }
1068     }
1069     return Result;
1070   }
1071
1072   case ISD::CALL: {
1073     unsigned GPR_idx = 0, FPR_idx = 0;
1074     static const unsigned GPR[] = {
1075       PPC::R3, PPC::R4, PPC::R5, PPC::R6,
1076       PPC::R7, PPC::R8, PPC::R9, PPC::R10,
1077     };
1078     static const unsigned FPR[] = {
1079       PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
1080       PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
1081     };
1082
1083     // Lower the chain for this call.
1084     Select(N.getOperand(0));
1085     ExprMap[N.getValue(Node->getNumValues()-1)] = 1;
1086
1087     MachineInstr *CallMI;
1088     // Emit the correct call instruction based on the type of symbol called.
1089     if (GlobalAddressSDNode *GASD =
1090         dyn_cast<GlobalAddressSDNode>(N.getOperand(1))) {
1091       CallMI = BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(GASD->getGlobal(),
1092                                                            true);
1093     } else if (ExternalSymbolSDNode *ESSDN =
1094                dyn_cast<ExternalSymbolSDNode>(N.getOperand(1))) {
1095       CallMI = BuildMI(PPC::CALLpcrel, 1).addExternalSymbol(ESSDN->getSymbol(),
1096                                                             true);
1097     } else {
1098       Tmp1 = SelectExpr(N.getOperand(1));
1099       BuildMI(BB, PPC::OR, 2, PPC::R12).addReg(Tmp1).addReg(Tmp1);
1100       BuildMI(BB, PPC::MTCTR, 1).addReg(PPC::R12);
1101       CallMI = BuildMI(PPC::CALLindirect, 3).addImm(20).addImm(0)
1102         .addReg(PPC::R12);
1103     }
1104
1105     // Load the register args to virtual regs
1106     std::vector<unsigned> ArgVR;
1107     for(int i = 2, e = Node->getNumOperands(); i < e; ++i)
1108       ArgVR.push_back(SelectExpr(N.getOperand(i)));
1109
1110     // Copy the virtual registers into the appropriate argument register
1111     for(int i = 0, e = ArgVR.size(); i < e; ++i) {
1112       switch(N.getOperand(i+2).getValueType()) {
1113       default: Node->dump(); assert(0 && "Unknown value type for call");
1114       case MVT::i1:
1115       case MVT::i8:
1116       case MVT::i16:
1117       case MVT::i32:
1118       case MVT::i64:
1119         assert(GPR_idx < 8 && "Too many int args");
1120         if (N.getOperand(i+2).getOpcode() != ISD::UNDEF) {
1121           BuildMI(BB, PPC::OR,2,GPR[GPR_idx]).addReg(ArgVR[i]).addReg(ArgVR[i]);
1122           CallMI->addRegOperand(GPR[GPR_idx], MachineOperand::Use);
1123         }
1124         ++GPR_idx;
1125         break;
1126       case MVT::f64:
1127       case MVT::f32:
1128         assert(FPR_idx < 13 && "Too many fp args");
1129         BuildMI(BB, PPC::FMR, 1, FPR[FPR_idx]).addReg(ArgVR[i]);
1130         CallMI->addRegOperand(FPR[FPR_idx], MachineOperand::Use);
1131         ++FPR_idx;
1132         break;
1133       }
1134     }
1135
1136     // Put the call instruction in the correct place in the MachineBasicBlock
1137     BB->push_back(CallMI);
1138
1139     switch (Node->getValueType(0)) {
1140     default: assert(0 && "Unknown value type for call result!");
1141     case MVT::Other: return 1;
1142     case MVT::i1:
1143     case MVT::i8:
1144     case MVT::i16:
1145     case MVT::i32:
1146     case MVT::i64:
1147       BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R3).addReg(PPC::R3);
1148       break;
1149     case MVT::f32:
1150     case MVT::f64:
1151       BuildMI(BB, PPC::FMR, 1, Result).addReg(PPC::F1);
1152       break;
1153     }
1154     return Result+N.ResNo;
1155   }
1156
1157   case ISD::SIGN_EXTEND:
1158   case ISD::SIGN_EXTEND_INREG:
1159     Tmp1 = SelectExpr(N.getOperand(0));
1160     switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
1161     default: Node->dump(); assert(0 && "Unhandled SIGN_EXTEND type"); break;
1162     case MVT::i32:
1163       BuildMI(BB, PPC::EXTSW, 1, Result).addReg(Tmp1);
1164       break;
1165     case MVT::i16:
1166       BuildMI(BB, PPC::EXTSH, 1, Result).addReg(Tmp1);
1167       break;
1168     case MVT::i8:
1169       BuildMI(BB, PPC::EXTSB, 1, Result).addReg(Tmp1);
1170       break;
1171     case MVT::i1:
1172       BuildMI(BB, PPC::SUBFIC, 2, Result).addReg(Tmp1).addSImm(0);
1173       break;
1174     }
1175     return Result;
1176
1177   case ISD::CopyFromReg:
1178     if (Result == 1)
1179       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1180     Tmp1 = dyn_cast<RegSDNode>(Node)->getReg();
1181     BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp1).addReg(Tmp1);
1182     return Result;
1183
1184   case ISD::SHL:
1185     Tmp1 = SelectExpr(N.getOperand(0));
1186     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1187       Tmp2 = CN->getValue() & 0x3F;
1188       BuildMI(BB, PPC::RLDICR, 3, Result).addReg(Tmp1).addImm(Tmp2)
1189         .addImm(63-Tmp2);
1190     } else {
1191       Tmp2 = SelectExpr(N.getOperand(1));
1192       BuildMI(BB, PPC::SLD, 2, Result).addReg(Tmp1).addReg(Tmp2);
1193     }
1194     return Result;
1195
1196   case ISD::SRL:
1197     Tmp1 = SelectExpr(N.getOperand(0));
1198     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1199       Tmp2 = CN->getValue() & 0x3F;
1200       BuildMI(BB, PPC::RLDICL, 3, Result).addReg(Tmp1).addImm(64-Tmp2)
1201         .addImm(Tmp2);
1202     } else {
1203       Tmp2 = SelectExpr(N.getOperand(1));
1204       BuildMI(BB, PPC::SRD, 2, Result).addReg(Tmp1).addReg(Tmp2);
1205     }
1206     return Result;
1207
1208   case ISD::SRA:
1209     Tmp1 = SelectExpr(N.getOperand(0));
1210     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1211       Tmp2 = CN->getValue() & 0x3F;
1212       BuildMI(BB, PPC::SRADI, 2, Result).addReg(Tmp1).addImm(Tmp2);
1213     } else {
1214       Tmp2 = SelectExpr(N.getOperand(1));
1215       BuildMI(BB, PPC::SRAD, 2, Result).addReg(Tmp1).addReg(Tmp2);
1216     }
1217     return Result;
1218
1219   case ISD::ADD:
1220     Tmp1 = SelectExpr(N.getOperand(0));
1221     switch(getImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
1222       default: assert(0 && "unhandled result code");
1223       case 0: // No immediate
1224         Tmp2 = SelectExpr(N.getOperand(1));
1225         BuildMI(BB, PPC::ADD, 2, Result).addReg(Tmp1).addReg(Tmp2);
1226         break;
1227       case 1: // Low immediate
1228         BuildMI(BB, PPC::ADDI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
1229         break;
1230       case 2: // Shifted immediate
1231         BuildMI(BB, PPC::ADDIS, 2, Result).addReg(Tmp1).addSImm(Tmp2);
1232         break;
1233     }
1234     return Result;
1235
1236   case ISD::AND:
1237   case ISD::OR:
1238     Tmp1 = SelectExpr(N.getOperand(0));
1239     switch(getImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
1240       default: assert(0 && "unhandled result code");
1241       case 0: // No immediate
1242         Tmp2 = SelectExpr(N.getOperand(1));
1243         switch (opcode) {
1244         case ISD::AND: Opc = PPC::AND; break;
1245         case ISD::OR:  Opc = PPC::OR;  break;
1246         }
1247         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1248         break;
1249       case 1: // Low immediate
1250         switch (opcode) {
1251         case ISD::AND: Opc = PPC::ANDIo; break;
1252         case ISD::OR:  Opc = PPC::ORI;   break;
1253         }
1254         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(Tmp2);
1255         break;
1256       case 2: // Shifted immediate
1257         switch (opcode) {
1258         case ISD::AND: Opc = PPC::ANDISo;  break;
1259         case ISD::OR:  Opc = PPC::ORIS;    break;
1260         }
1261         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(Tmp2);
1262         break;
1263     }
1264     return Result;
1265
1266   case ISD::XOR: {
1267     // Check for EQV: xor, (xor a, -1), b
1268     if (N.getOperand(0).getOpcode() == ISD::XOR &&
1269         N.getOperand(0).getOperand(1).getOpcode() == ISD::Constant &&
1270         cast<ConstantSDNode>(N.getOperand(0).getOperand(1))->isAllOnesValue()) {
1271       ++NotLogic;
1272       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1273       Tmp2 = SelectExpr(N.getOperand(1));
1274       BuildMI(BB, PPC::EQV, 2, Result).addReg(Tmp1).addReg(Tmp2);
1275       return Result;
1276     }
1277     // Check for NOT, NOR, and NAND: xor (copy, or, and), -1
1278     if (N.getOperand(1).getOpcode() == ISD::Constant &&
1279         cast<ConstantSDNode>(N.getOperand(1))->isAllOnesValue()) {
1280       ++NotLogic;
1281       switch(N.getOperand(0).getOpcode()) {
1282       case ISD::OR:
1283         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1284         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1285         BuildMI(BB, PPC::NOR, 2, Result).addReg(Tmp1).addReg(Tmp2);
1286         break;
1287       case ISD::AND:
1288         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1289         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1290         BuildMI(BB, PPC::NAND, 2, Result).addReg(Tmp1).addReg(Tmp2);
1291         break;
1292       default:
1293         Tmp1 = SelectExpr(N.getOperand(0));
1294         BuildMI(BB, PPC::NOR, 2, Result).addReg(Tmp1).addReg(Tmp1);
1295         break;
1296       }
1297       return Result;
1298     }
1299     Tmp1 = SelectExpr(N.getOperand(0));
1300     switch(getImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
1301       default: assert(0 && "unhandled result code");
1302       case 0: // No immediate
1303         Tmp2 = SelectExpr(N.getOperand(1));
1304         BuildMI(BB, PPC::XOR, 2, Result).addReg(Tmp1).addReg(Tmp2);
1305         break;
1306       case 1: // Low immediate
1307         BuildMI(BB, PPC::XORI, 2, Result).addReg(Tmp1).addImm(Tmp2);
1308         break;
1309       case 2: // Shifted immediate
1310         BuildMI(BB, PPC::XORIS, 2, Result).addReg(Tmp1).addImm(Tmp2);
1311         break;
1312     }
1313     return Result;
1314   }
1315
1316   case ISD::SUB:
1317     Tmp2 = SelectExpr(N.getOperand(1));
1318     if (1 == getImmediateForOpcode(N.getOperand(0), opcode, Tmp1))
1319       BuildMI(BB, PPC::SUBFIC, 2, Result).addReg(Tmp2).addSImm(Tmp1);
1320     else {
1321       Tmp1 = SelectExpr(N.getOperand(0));
1322       BuildMI(BB, PPC::SUBF, 2, Result).addReg(Tmp2).addReg(Tmp1);
1323     }
1324     return Result;
1325
1326   case ISD::MUL:
1327     Tmp1 = SelectExpr(N.getOperand(0));
1328     if (1 == getImmediateForOpcode(N.getOperand(1), opcode, Tmp2))
1329       BuildMI(BB, PPC::MULLI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
1330     else {
1331       Tmp2 = SelectExpr(N.getOperand(1));
1332       BuildMI(BB, PPC::MULLD, 2, Result).addReg(Tmp1).addReg(Tmp2);
1333     }
1334     return Result;
1335
1336   case ISD::SDIV:
1337   case ISD::UDIV:
1338     if (3 == getImmediateForOpcode(N.getOperand(1), opcode, Tmp3)) {
1339       Tmp1 = MakeReg(MVT::i64);
1340       Tmp2 = SelectExpr(N.getOperand(0));
1341       BuildMI(BB, PPC::SRADI, 2, Tmp1).addReg(Tmp2).addImm(Tmp3);
1342       BuildMI(BB, PPC::ADDZE, 1, Result).addReg(Tmp1);
1343       return Result;
1344     }
1345     Tmp1 = SelectExpr(N.getOperand(0));
1346     Tmp2 = SelectExpr(N.getOperand(1));
1347     Opc = (ISD::UDIV == opcode) ? PPC::DIVWU : PPC::DIVW;
1348     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1349     return Result;
1350
1351   case ISD::FP_TO_UINT:
1352   case ISD::FP_TO_SINT: {
1353     Tmp1 = SelectExpr(N.getOperand(0));
1354     Tmp2 = MakeReg(MVT::f64);
1355     BuildMI(BB, PPC::FCTIDZ, 1, Tmp2).addReg(Tmp1);
1356     int FrameIdx = BB->getParent()->getFrameInfo()->CreateStackObject(8, 8);
1357     addFrameReference(BuildMI(BB, PPC::STFD, 3).addReg(Tmp2), FrameIdx);
1358     addFrameReference(BuildMI(BB, PPC::LD, 2, Result), FrameIdx);
1359     return Result;
1360   }
1361
1362   case ISD::SETCC:
1363     if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(Node)) {
1364       Opc = SelectSetCR0(N);
1365
1366       unsigned TrueValue = MakeReg(MVT::i32);
1367       BuildMI(BB, PPC::LI, 1, TrueValue).addSImm(1);
1368       unsigned FalseValue = MakeReg(MVT::i32);
1369       BuildMI(BB, PPC::LI, 1, FalseValue).addSImm(0);
1370
1371       // Create an iterator with which to insert the MBB for copying the false
1372       // value and the MBB to hold the PHI instruction for this SetCC.
1373       MachineBasicBlock *thisMBB = BB;
1374       const BasicBlock *LLVM_BB = BB->getBasicBlock();
1375       ilist<MachineBasicBlock>::iterator It = BB;
1376       ++It;
1377
1378       //  thisMBB:
1379       //  ...
1380       //   cmpTY cr0, r1, r2
1381       //   %TrueValue = li 1
1382       //   bCC sinkMBB
1383       MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
1384       MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
1385       BuildMI(BB, Opc, 2).addReg(PPC::CR0).addMBB(sinkMBB);
1386       MachineFunction *F = BB->getParent();
1387       F->getBasicBlockList().insert(It, copy0MBB);
1388       F->getBasicBlockList().insert(It, sinkMBB);
1389       // Update machine-CFG edges
1390       BB->addSuccessor(copy0MBB);
1391       BB->addSuccessor(sinkMBB);
1392
1393       //  copy0MBB:
1394       //   %FalseValue = li 0
1395       //   fallthrough
1396       BB = copy0MBB;
1397       // Update machine-CFG edges
1398       BB->addSuccessor(sinkMBB);
1399
1400       //  sinkMBB:
1401       //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
1402       //  ...
1403       BB = sinkMBB;
1404       BuildMI(BB, PPC::PHI, 4, Result).addReg(FalseValue)
1405         .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
1406       return Result;
1407     }
1408     assert(0 && "Is this legal?");
1409     return 0;
1410
1411   case ISD::SELECT: {
1412     unsigned TrueValue = SelectExpr(N.getOperand(1)); //Use if TRUE
1413     unsigned FalseValue = SelectExpr(N.getOperand(2)); //Use if FALSE
1414     Opc = SelectSetCR0(N.getOperand(0));
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 cr0, 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(PPC::CR0).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     // Update machine-CFG edges
1444     BB->addSuccessor(sinkMBB);
1445
1446     //  sinkMBB:
1447     //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
1448     //  ...
1449     BB = sinkMBB;
1450     BuildMI(BB, PPC::PHI, 4, Result).addReg(FalseValue)
1451       .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
1452
1453     // FIXME: Select i64?
1454     return Result;
1455   }
1456
1457   case ISD::Constant:
1458     switch (N.getValueType()) {
1459     default: assert(0 && "Cannot use constants of this type!");
1460     case MVT::i1:
1461       BuildMI(BB, PPC::LI, 1, Result)
1462         .addSImm(!cast<ConstantSDNode>(N)->isNullValue());
1463       break;
1464     case MVT::i32:
1465       {
1466         int v = (int)cast<ConstantSDNode>(N)->getSignExtended();
1467         if (v < 32768 && v >= -32768) {
1468           BuildMI(BB, PPC::LI, 1, Result).addSImm(v);
1469         } else {
1470           Tmp1 = MakeReg(MVT::i32);
1471           BuildMI(BB, PPC::LIS, 1, Tmp1).addSImm(v >> 16);
1472           BuildMI(BB, PPC::ORI, 2, Result).addReg(Tmp1).addImm(v & 0xFFFF);
1473         }
1474       }
1475     }
1476     return Result;
1477   }
1478
1479   return 0;
1480 }
1481
1482 void ISel::Select(SDOperand N) {
1483   unsigned Tmp1, Tmp2, Opc;
1484   unsigned opcode = N.getOpcode();
1485
1486   if (!ExprMap.insert(std::make_pair(N, 1)).second)
1487     return;  // Already selected.
1488
1489   SDNode *Node = N.Val;
1490
1491   switch (Node->getOpcode()) {
1492   default:
1493     Node->dump(); std::cerr << "\n";
1494     assert(0 && "Node not handled yet!");
1495   case ISD::EntryToken: return;  // Noop
1496   case ISD::TokenFactor:
1497     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
1498       Select(Node->getOperand(i));
1499     return;
1500   case ISD::CALLSEQ_START:
1501   case ISD::CALLSEQ_END:
1502     Select(N.getOperand(0));
1503     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
1504     Opc = N.getOpcode() == ISD::CALLSEQ_START ? PPC::ADJCALLSTACKDOWN :
1505       PPC::ADJCALLSTACKUP;
1506     BuildMI(BB, Opc, 1).addImm(Tmp1);
1507     return;
1508   case ISD::BR: {
1509     MachineBasicBlock *Dest =
1510       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
1511     Select(N.getOperand(0));
1512     BuildMI(BB, PPC::B, 1).addMBB(Dest);
1513     return;
1514   }
1515   case ISD::BRCOND:
1516     SelectBranchCC(N);
1517     return;
1518   case ISD::CopyToReg:
1519     Select(N.getOperand(0));
1520     Tmp1 = SelectExpr(N.getOperand(1));
1521     Tmp2 = cast<RegSDNode>(N)->getReg();
1522
1523     if (Tmp1 != Tmp2) {
1524       if (N.getOperand(1).getValueType() == MVT::f64 ||
1525           N.getOperand(1).getValueType() == MVT::f32)
1526         BuildMI(BB, PPC::FMR, 1, Tmp2).addReg(Tmp1);
1527       else
1528         BuildMI(BB, PPC::OR, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
1529     }
1530     return;
1531   case ISD::ImplicitDef:
1532     Select(N.getOperand(0));
1533     BuildMI(BB, PPC::IMPLICIT_DEF, 0, cast<RegSDNode>(N)->getReg());
1534     return;
1535   case ISD::RET:
1536     switch (N.getNumOperands()) {
1537     default:
1538       assert(0 && "Unknown return instruction!");
1539     case 3:
1540       assert(N.getOperand(1).getValueType() == MVT::i32 &&
1541              N.getOperand(2).getValueType() == MVT::i32 &&
1542              "Unknown two-register value!");
1543       Select(N.getOperand(0));
1544       Tmp1 = SelectExpr(N.getOperand(1));
1545       Tmp2 = SelectExpr(N.getOperand(2));
1546       BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp2).addReg(Tmp2);
1547       BuildMI(BB, PPC::OR, 2, PPC::R4).addReg(Tmp1).addReg(Tmp1);
1548       break;
1549     case 2:
1550       Select(N.getOperand(0));
1551       Tmp1 = SelectExpr(N.getOperand(1));
1552       switch (N.getOperand(1).getValueType()) {
1553         default:
1554           assert(0 && "Unknown return type!");
1555         case MVT::f64:
1556         case MVT::f32:
1557           BuildMI(BB, PPC::FMR, 1, PPC::F1).addReg(Tmp1);
1558           break;
1559         case MVT::i32:
1560           BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp1).addReg(Tmp1);
1561           break;
1562       }
1563     case 1:
1564       Select(N.getOperand(0));
1565       break;
1566     }
1567     BuildMI(BB, PPC::BLR, 0); // Just emit a 'ret' instruction
1568     return;
1569   case ISD::TRUNCSTORE:
1570   case ISD::STORE:
1571     {
1572       SDOperand Chain   = N.getOperand(0);
1573       SDOperand Value   = N.getOperand(1);
1574       SDOperand Address = N.getOperand(2);
1575       Select(Chain);
1576
1577       Tmp1 = SelectExpr(Value); //value
1578
1579       if (opcode == ISD::STORE) {
1580         switch(Value.getValueType()) {
1581         default: assert(0 && "unknown Type in store");
1582         case MVT::i64: Opc = PPC::STD; break;
1583         case MVT::f64: Opc = PPC::STFD; break;
1584         case MVT::f32: Opc = PPC::STFS; break;
1585         }
1586       } else { //ISD::TRUNCSTORE
1587         switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
1588         default: assert(0 && "unknown Type in store");
1589         case MVT::i1: //FIXME: DAG does not promote this load
1590         case MVT::i8:  Opc= PPC::STB; break;
1591         case MVT::i16: Opc = PPC::STH; break;
1592         case MVT::i32: Opc = PPC::STW; break;
1593         }
1594       }
1595
1596       if(Address.getOpcode() == ISD::FrameIndex)
1597       {
1598         Tmp2 = cast<FrameIndexSDNode>(Address)->getIndex();
1599         addFrameReference(BuildMI(BB, Opc, 3).addReg(Tmp1), (int)Tmp2);
1600       }
1601       else
1602       {
1603         int offset;
1604         bool idx = SelectAddr(Address, Tmp2, offset);
1605         if (idx) {
1606           Opc = IndexedOpForOp(Opc);
1607           BuildMI(BB, Opc, 3).addReg(Tmp1).addReg(Tmp2).addReg(offset);
1608         } else {
1609           BuildMI(BB, Opc, 3).addReg(Tmp1).addImm(offset).addReg(Tmp2);
1610         }
1611       }
1612       return;
1613     }
1614   case ISD::EXTLOAD:
1615   case ISD::SEXTLOAD:
1616   case ISD::ZEXTLOAD:
1617   case ISD::LOAD:
1618   case ISD::CopyFromReg:
1619   case ISD::CALL:
1620   case ISD::DYNAMIC_STACKALLOC:
1621     ExprMap.erase(N);
1622     SelectExpr(N);
1623     return;
1624   }
1625   assert(0 && "Should not be reached!");
1626 }
1627
1628
1629 /// createPPC32PatternInstructionSelector - This pass converts an LLVM function
1630 /// into a machine code representation using pattern matching and a machine
1631 /// description file.
1632 ///
1633 FunctionPass *llvm::createPPC64ISelPattern(TargetMachine &TM) {
1634   return new ISel(TM);
1635 }
1636