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