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