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