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