lib/Target/PowerPC/PPCISelPattern.cpp

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