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 // Magic number generation for integer divide from the PowerPC Compiler Writer's
  12 // Guide, section 3.2.3.5
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "PowerPC.h"
  17 #include "PowerPCInstrBuilder.h"
  18 #include "PowerPCInstrInfo.h"
  19 #include "PPC32TargetMachine.h"
  20 #include "llvm/Constants.h"                   // FIXME: REMOVE
  21 #include "llvm/Function.h"
  22 #include "llvm/CodeGen/MachineConstantPool.h" // FIXME: REMOVE
  23 #include "llvm/CodeGen/MachineFunction.h"
  24 #include "llvm/CodeGen/MachineFrameInfo.h"
  25 #include "llvm/CodeGen/SelectionDAG.h"
  26 #include "llvm/CodeGen/SelectionDAGISel.h"
  27 #include "llvm/CodeGen/SSARegMap.h"
  28 #include "llvm/Target/TargetData.h"
  29 #include "llvm/Target/TargetLowering.h"
  30 #include "llvm/Target/TargetOptions.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/MathExtras.h"
  33 #include "llvm/ADT/Statistic.h"
  34 #include <set>
  35 #include <algorithm>
  36 using namespace llvm;
  37
  38 //===----------------------------------------------------------------------===//
  39 //  PPC32TargetLowering - PPC32 Implementation of the TargetLowering interface
  40 namespace {
  41   class PPC32TargetLowering : public TargetLowering {
  42     int VarArgsFrameIndex;            // FrameIndex for start of varargs area.
  43     int ReturnAddrIndex;              // FrameIndex for return slot.
  44   public:
  45     PPC32TargetLowering(TargetMachine &TM) : TargetLowering(TM) {
  46       // Set up the register classes.
  47       addRegisterClass(MVT::i32, PPC32::GPRCRegisterClass);
  48       addRegisterClass(MVT::f32, PPC32::FPRCRegisterClass);
  49       addRegisterClass(MVT::f64, PPC32::FPRCRegisterClass);
  50
  51       // PowerPC has no intrinsics for these particular operations
  52       setOperationAction(ISD::MEMMOVE, MVT::Other, Expand);
  53       setOperationAction(ISD::MEMSET, MVT::Other, Expand);
  54       setOperationAction(ISD::MEMCPY, MVT::Other, Expand);
  55
  56       // PowerPC has an i16 but no i8 (or i1) SEXTLOAD
  57       setOperationAction(ISD::SEXTLOAD, MVT::i1, Expand);
  58       setOperationAction(ISD::SEXTLOAD, MVT::i8, Expand);
  59
  60       // PowerPC has no SREM/UREM instructions
  61       setOperationAction(ISD::SREM, MVT::i32, Expand);
  62       setOperationAction(ISD::UREM, MVT::i32, Expand);
  63
  64       setShiftAmountFlavor(Extend);   // shl X, 32 == 0
  65       setSetCCResultContents(ZeroOrOneSetCCResult);
  66       addLegalFPImmediate(+0.0); // Necessary for FSEL
  67       addLegalFPImmediate(-0.0); //
  68
  69       computeRegisterProperties();
  70     }
  71
  72     /// LowerArguments - This hook must be implemented to indicate how we should
  73     /// lower the arguments for the specified function, into the specified DAG.
  74     virtual std::vector<SDOperand>
  75     LowerArguments(Function &F, SelectionDAG &DAG);
  76
  77     /// LowerCallTo - This hook lowers an abstract call to a function into an
  78     /// actual call.
  79     virtual std::pair<SDOperand, SDOperand>
  80     LowerCallTo(SDOperand Chain, const Type *RetTy, bool isVarArg,
  81                 SDOperand Callee, ArgListTy &Args, SelectionDAG &DAG);
  82
  83     virtual std::pair<SDOperand, SDOperand>
  84     LowerVAStart(SDOperand Chain, SelectionDAG &DAG);
  85
  86     virtual std::pair<SDOperand,SDOperand>
  87     LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
  88                    const Type *ArgTy, SelectionDAG &DAG);
  89
  90     virtual std::pair<SDOperand, SDOperand>
  91     LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain, unsigned Depth,
  92                             SelectionDAG &DAG);
  93   };
  94 }
  95
  96
  97 std::vector<SDOperand>
  98 PPC32TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
  99   //
 100   // add beautiful description of PPC stack frame format, or at least some docs
 101   //
 102   MachineFunction &MF = DAG.getMachineFunction();
 103   MachineFrameInfo *MFI = MF.getFrameInfo();
 104   MachineBasicBlock& BB = MF.front();
 105   std::vector<SDOperand> ArgValues;
 106
 107   // Due to the rather complicated nature of the PowerPC ABI, rather than a
 108   // fixed size array of physical args, for the sake of simplicity let the STL
 109   // handle tracking them for us.
 110   std::vector<unsigned> argVR, argPR, argOp;
 111   unsigned ArgOffset = 24;
 112   unsigned GPR_remaining = 8;
 113   unsigned FPR_remaining = 13;
 114   unsigned GPR_idx = 0, FPR_idx = 0;
 115   static const unsigned GPR[] = {
 116     PPC::R3, PPC::R4, PPC::R5, PPC::R6,
 117     PPC::R7, PPC::R8, PPC::R9, PPC::R10,
 118   };
 119   static const unsigned FPR[] = {
 120     PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
 121     PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
 122   };
 123
 124   // Add DAG nodes to load the arguments...  On entry to a function on PPC,
 125   // the arguments start at offset 24, although they are likely to be passed
 126   // in registers.
 127   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
 128     SDOperand newroot, argt;
 129     unsigned ObjSize;
 130     bool needsLoad = false;
 131     bool ArgLive = !I->use_empty();
 132     MVT::ValueType ObjectVT = getValueType(I->getType());
 133
 134     switch (ObjectVT) {
 135     default: assert(0 && "Unhandled argument type!");
 136     case MVT::i1:
 137     case MVT::i8:
 138     case MVT::i16:
 139     case MVT::i32:
 140       ObjSize = 4;
 141       if (!ArgLive) break;
 142       if (GPR_remaining > 0) {
 143         MF.addLiveIn(GPR[GPR_idx]);
 144         argt = newroot = DAG.getCopyFromReg(GPR[GPR_idx], MVT::i32,
 145                                             DAG.getRoot());
 146         if (ObjectVT != MVT::i32)
 147           argt = DAG.getNode(ISD::TRUNCATE, ObjectVT, newroot);
 148       } else {
 149         needsLoad = true;
 150       }
 151       break;
 152       case MVT::i64: ObjSize = 8;
 153       if (!ArgLive) break;
 154       // FIXME: can split 64b load between reg/mem if it is last arg in regs
 155       if (GPR_remaining > 1) {
 156         MF.addLiveIn(GPR[GPR_idx]);
 157         MF.addLiveIn(GPR[GPR_idx+1]);
 158         // Copy the extracted halves into the virtual registers
 159         SDOperand argHi = DAG.getCopyFromReg(GPR[GPR_idx], MVT::i32,
 160                                              DAG.getRoot());
 161         SDOperand argLo = DAG.getCopyFromReg(GPR[GPR_idx+1], MVT::i32, argHi);
 162         // Build the outgoing arg thingy
 163         argt = DAG.getNode(ISD::BUILD_PAIR, MVT::i64, argLo, argHi);
 164         newroot = argLo;
 165       } else {
 166         needsLoad = true;
 167       }
 168       break;
 169       case MVT::f32:
 170       case MVT::f64:
 171       ObjSize = (ObjectVT == MVT::f64) ? 8 : 4;
 172       if (!ArgLive) break;
 173       if (FPR_remaining > 0) {
 174         MF.addLiveIn(FPR[FPR_idx]);
 175         argt = newroot = DAG.getCopyFromReg(FPR[FPR_idx], ObjectVT,
 176                                             DAG.getRoot());
 177         --FPR_remaining;
 178         ++FPR_idx;
 179       } else {
 180         needsLoad = true;
 181       }
 182       break;
 183     }
 184
 185     // We need to load the argument to a virtual register if we determined above
 186     // that we ran out of physical registers of the appropriate type
 187     if (needsLoad) {
 188       unsigned SubregOffset = 0;
 189       if (ObjectVT == MVT::i8 || ObjectVT == MVT::i1) SubregOffset = 3;
 190       if (ObjectVT == MVT::i16) SubregOffset = 2;
 191       int FI = MFI->CreateFixedObject(ObjSize, ArgOffset);
 192       SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
 193       FIN = DAG.getNode(ISD::ADD, MVT::i32, FIN,
 194                         DAG.getConstant(SubregOffset, MVT::i32));
 195       argt = newroot = DAG.getLoad(ObjectVT, DAG.getEntryNode(), FIN);
 196     }
 197
 198     // Every 4 bytes of argument space consumes one of the GPRs available for
 199     // argument passing.
 200     if (GPR_remaining > 0) {
 201       unsigned delta = (GPR_remaining > 1 && ObjSize == 8) ? 2 : 1;
 202       GPR_remaining -= delta;
 203       GPR_idx += delta;
 204     }
 205     ArgOffset += ObjSize;
 206
 207     DAG.setRoot(newroot.getValue(1));
 208     ArgValues.push_back(argt);
 209   }
 210
 211   // If the function takes variable number of arguments, make a frame index for
 212   // the start of the first vararg value... for expansion of llvm.va_start.
 213   if (F.isVarArg()) {
 214     VarArgsFrameIndex = MFI->CreateFixedObject(4, ArgOffset);
 215     SDOperand FIN = DAG.getFrameIndex(VarArgsFrameIndex, MVT::i32);
 216     // If this function is vararg, store any remaining integer argument regs
 217     // to their spots on the stack so that they may be loaded by deferencing the
 218     // result of va_next.
 219     std::vector<SDOperand> MemOps;
 220     for (; GPR_remaining > 0; --GPR_remaining, ++GPR_idx) {
 221       MF.addLiveIn(GPR[GPR_idx]);
 222       SDOperand Val = DAG.getCopyFromReg(GPR[GPR_idx], MVT::i32, DAG.getRoot());
 223       SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, Val.getValue(1),
 224                                     Val, FIN);
 225       MemOps.push_back(Store);
 226       // Increment the address by four for the next argument to store
 227       SDOperand PtrOff = DAG.getConstant(4, getPointerTy());
 228       FIN = DAG.getNode(ISD::ADD, MVT::i32, FIN, PtrOff);
 229     }
 230     DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, MemOps));
 231   }
 232
 233   // Finally, inform the code generator which regs we return values in.
 234   switch (getValueType(F.getReturnType())) {
 235   default: assert(0 && "Unknown type!");
 236   case MVT::isVoid: break;
 237   case MVT::i1:
 238   case MVT::i8:
 239   case MVT::i16:
 240   case MVT::i32:
 241     MF.addLiveOut(PPC::R3);
 242     break;
 243   case MVT::i64:
 244     MF.addLiveOut(PPC::R3);
 245     MF.addLiveOut(PPC::R4);
 246     break;
 247   case MVT::f32:
 248   case MVT::f64:
 249     MF.addLiveOut(PPC::F1);
 250     break;
 251   }
 252
 253   return ArgValues;
 254 }
 255
 256 std::pair<SDOperand, SDOperand>
 257 PPC32TargetLowering::LowerCallTo(SDOperand Chain,
 258                                  const Type *RetTy, bool isVarArg,
 259          SDOperand Callee, ArgListTy &Args, SelectionDAG &DAG) {
 260   // args_to_use will accumulate outgoing args for the ISD::CALL case in
 261   // SelectExpr to use to put the arguments in the appropriate registers.
 262   std::vector<SDOperand> args_to_use;
 263
 264   // Count how many bytes are to be pushed on the stack, including the linkage
 265   // area, and parameter passing area.
 266   unsigned NumBytes = 24;
 267
 268   if (Args.empty()) {
 269     Chain = DAG.getNode(ISD::ADJCALLSTACKDOWN, MVT::Other, Chain,
 270                         DAG.getConstant(NumBytes, getPointerTy()));
 271   } else {
 272     for (unsigned i = 0, e = Args.size(); i != e; ++i)
 273       switch (getValueType(Args[i].second)) {
 274       default: assert(0 && "Unknown value type!");
 275       case MVT::i1:
 276       case MVT::i8:
 277       case MVT::i16:
 278       case MVT::i32:
 279       case MVT::f32:
 280         NumBytes += 4;
 281         break;
 282       case MVT::i64:
 283       case MVT::f64:
 284         NumBytes += 8;
 285         break;
 286       }
 287
 288     // Just to be safe, we'll always reserve the full 24 bytes of linkage area
 289     // plus 32 bytes of argument space in case any called code gets funky on us.
 290     if (NumBytes < 56) NumBytes = 56;
 291
 292     // Adjust the stack pointer for the new arguments...
 293     // These operations are automatically eliminated by the prolog/epilog pass
 294     Chain = DAG.getNode(ISD::ADJCALLSTACKDOWN, MVT::Other, Chain,
 295                         DAG.getConstant(NumBytes, getPointerTy()));
 296
 297     // Set up a copy of the stack pointer for use loading and storing any
 298     // arguments that may not fit in the registers available for argument
 299     // passing.
 300     SDOperand StackPtr = DAG.getCopyFromReg(PPC::R1, MVT::i32,
 301                                             DAG.getEntryNode());
 302
 303     // Figure out which arguments are going to go in registers, and which in
 304     // memory.  Also, if this is a vararg function, floating point operations
 305     // must be stored to our stack, and loaded into integer regs as well, if
 306     // any integer regs are available for argument passing.
 307     unsigned ArgOffset = 24;
 308     unsigned GPR_remaining = 8;
 309     unsigned FPR_remaining = 13;
 310
 311     std::vector<SDOperand> MemOps;
 312     for (unsigned i = 0, e = Args.size(); i != e; ++i) {
 313       // PtrOff will be used to store the current argument to the stack if a
 314       // register cannot be found for it.
 315       SDOperand PtrOff = DAG.getConstant(ArgOffset, getPointerTy());
 316       PtrOff = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff);
 317       MVT::ValueType ArgVT = getValueType(Args[i].second);
 318
 319       switch (ArgVT) {
 320       default: assert(0 && "Unexpected ValueType for argument!");
 321       case MVT::i1:
 322       case MVT::i8:
 323       case MVT::i16:
 324         // Promote the integer to 32 bits.  If the input type is signed use a
 325         // sign extend, otherwise use a zero extend.
 326         if (Args[i].second->isSigned())
 327           Args[i].first =DAG.getNode(ISD::SIGN_EXTEND, MVT::i32, Args[i].first);
 328         else
 329           Args[i].first =DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Args[i].first);
 330         // FALL THROUGH
 331       case MVT::i32:
 332         if (GPR_remaining > 0) {
 333           args_to_use.push_back(Args[i].first);
 334           --GPR_remaining;
 335         } else {
 336           MemOps.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 337                                           Args[i].first, PtrOff));
 338         }
 339         ArgOffset += 4;
 340         break;
 341       case MVT::i64:
 342         // If we have one free GPR left, we can place the upper half of the i64
 343         // in it, and store the other half to the stack.  If we have two or more
 344         // free GPRs, then we can pass both halves of the i64 in registers.
 345         if (GPR_remaining > 0) {
 346           SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32,
 347             Args[i].first, DAG.getConstant(1, MVT::i32));
 348           SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32,
 349             Args[i].first, DAG.getConstant(0, MVT::i32));
 350           args_to_use.push_back(Hi);
 351           --GPR_remaining;
 352           if (GPR_remaining > 0) {
 353             args_to_use.push_back(Lo);
 354             --GPR_remaining;
 355           } else {
 356             SDOperand ConstFour = DAG.getConstant(4, getPointerTy());
 357             PtrOff = DAG.getNode(ISD::ADD, MVT::i32, PtrOff, ConstFour);
 358             MemOps.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 359                                             Lo, PtrOff));
 360           }
 361         } else {
 362           MemOps.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 363                                           Args[i].first, PtrOff));
 364         }
 365         ArgOffset += 8;
 366         break;
 367       case MVT::f32:
 368       case MVT::f64:
 369         if (FPR_remaining > 0) {
 370           args_to_use.push_back(Args[i].first);
 371           --FPR_remaining;
 372           if (isVarArg) {
 373             SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, Chain,
 374                                           Args[i].first, PtrOff);
 375             MemOps.push_back(Store);
 376             // Float varargs are always shadowed in available integer registers
 377             if (GPR_remaining > 0) {
 378               SDOperand Load = DAG.getLoad(MVT::i32, Store, PtrOff);
 379               MemOps.push_back(Load);
 380               args_to_use.push_back(Load);
 381               --GPR_remaining;
 382             }
 383             if (GPR_remaining > 0 && MVT::f64 == ArgVT) {
 384               SDOperand ConstFour = DAG.getConstant(4, getPointerTy());
 385               PtrOff = DAG.getNode(ISD::ADD, MVT::i32, PtrOff, ConstFour);
 386               SDOperand Load = DAG.getLoad(MVT::i32, Store, PtrOff);
 387               MemOps.push_back(Load);
 388               args_to_use.push_back(Load);
 389               --GPR_remaining;
 390             }
 391           } else {
 392             // If we have any FPRs remaining, we may also have GPRs remaining.
 393             // Args passed in FPRs consume either 1 (f32) or 2 (f64) available
 394             // GPRs.
 395             if (GPR_remaining > 0) {
 396               args_to_use.push_back(DAG.getNode(ISD::UNDEF, MVT::i32));
 397               --GPR_remaining;
 398             }
 399             if (GPR_remaining > 0 && MVT::f64 == ArgVT) {
 400               args_to_use.push_back(DAG.getNode(ISD::UNDEF, MVT::i32));
 401               --GPR_remaining;
 402             }
 403           }
 404         } else {
 405           MemOps.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
 406                                           Args[i].first, PtrOff));
 407         }
 408         ArgOffset += (ArgVT == MVT::f32) ? 4 : 8;
 409         break;
 410       }
 411     }
 412     if (!MemOps.empty())
 413       Chain = DAG.getNode(ISD::TokenFactor, MVT::Other, MemOps);
 414   }
 415
 416   std::vector<MVT::ValueType> RetVals;
 417   MVT::ValueType RetTyVT = getValueType(RetTy);
 418   if (RetTyVT != MVT::isVoid)
 419     RetVals.push_back(RetTyVT);
 420   RetVals.push_back(MVT::Other);
 421
 422   SDOperand TheCall = SDOperand(DAG.getCall(RetVals,
 423                                             Chain, Callee, args_to_use), 0);
 424   Chain = TheCall.getValue(RetTyVT != MVT::isVoid);
 425   Chain = DAG.getNode(ISD::ADJCALLSTACKUP, MVT::Other, Chain,
 426                       DAG.getConstant(NumBytes, getPointerTy()));
 427   return std::make_pair(TheCall, Chain);
 428 }
 429
 430 std::pair<SDOperand, SDOperand>
 431 PPC32TargetLowering::LowerVAStart(SDOperand Chain, SelectionDAG &DAG) {
 432   //vastart just returns the address of the VarArgsFrameIndex slot.
 433   return std::make_pair(DAG.getFrameIndex(VarArgsFrameIndex, MVT::i32), Chain);
 434 }
 435
 436 std::pair<SDOperand,SDOperand> PPC32TargetLowering::
 437 LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
 438                const Type *ArgTy, SelectionDAG &DAG) {
 439   MVT::ValueType ArgVT = getValueType(ArgTy);
 440   SDOperand Result;
 441   if (!isVANext) {
 442     Result = DAG.getLoad(ArgVT, DAG.getEntryNode(), VAList);
 443   } else {
 444     unsigned Amt;
 445     if (ArgVT == MVT::i32 || ArgVT == MVT::f32)
 446       Amt = 4;
 447     else {
 448       assert((ArgVT == MVT::i64 || ArgVT == MVT::f64) &&
 449              "Other types should have been promoted for varargs!");
 450       Amt = 8;
 451     }
 452     Result = DAG.getNode(ISD::ADD, VAList.getValueType(), VAList,
 453                          DAG.getConstant(Amt, VAList.getValueType()));
 454   }
 455   return std::make_pair(Result, Chain);
 456 }
 457
 458
 459 std::pair<SDOperand, SDOperand> PPC32TargetLowering::
 460 LowerFrameReturnAddress(bool isFrameAddress, SDOperand Chain, unsigned Depth,
 461                         SelectionDAG &DAG) {
 462   assert(0 && "LowerFrameReturnAddress unimplemented");
 463   abort();
 464 }
 465
 466 namespace {
 467 Statistic<>Rotates("ppc-codegen", "Number of rotates emitted");
 468 Statistic<>FusedFP("ppc-codegen", "Number of fused fp operations");
 469 //===--------------------------------------------------------------------===//
 470 /// ISel - PPC32 specific code to select PPC32 machine instructions for
 471 /// SelectionDAG operations.
 472 //===--------------------------------------------------------------------===//
 473 class ISel : public SelectionDAGISel {
 474   PPC32TargetLowering PPC32Lowering;
 475   SelectionDAG *ISelDAG;  // Hack to support us having a dag->dag transform
 476                           // for sdiv and udiv until it is put into the future
 477                           // dag combiner.
 478
 479   /// ExprMap - As shared expressions are codegen'd, we keep track of which
 480   /// vreg the value is produced in, so we only emit one copy of each compiled
 481   /// tree.
 482   std::map<SDOperand, unsigned> ExprMap;
 483
 484   unsigned GlobalBaseReg;
 485   bool GlobalBaseInitialized;
 486
 487 public:
 488   ISel(TargetMachine &TM) : SelectionDAGISel(PPC32Lowering), PPC32Lowering(TM),
 489                             ISelDAG(0) {}
 490
 491   /// runOnFunction - Override this function in order to reset our per-function
 492   /// variables.
 493   virtual bool runOnFunction(Function &Fn) {
 494     // Make sure we re-emit a set of the global base reg if necessary
 495     GlobalBaseInitialized = false;
 496     return SelectionDAGISel::runOnFunction(Fn);
 497   }
 498
 499   /// InstructionSelectBasicBlock - This callback is invoked by
 500   /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 501   virtual void InstructionSelectBasicBlock(SelectionDAG &DAG) {
 502     DEBUG(BB->dump());
 503     // Codegen the basic block.
 504     ISelDAG = &DAG;
 505     Select(DAG.getRoot());
 506
 507     // Clear state used for selection.
 508     ExprMap.clear();
 509     ISelDAG = 0;
 510   }
 511
 512   // dag -> dag expanders for integer divide by constant
 513   SDOperand BuildSDIVSequence(SDOperand N);
 514   SDOperand BuildUDIVSequence(SDOperand N);
 515
 516   unsigned getGlobalBaseReg();
 517   unsigned getConstDouble(double floatVal, unsigned Result);
 518   bool SelectBitfieldInsert(SDOperand OR, unsigned Result);
 519   unsigned SelectSetCR0(SDOperand CC);
 520   unsigned SelectExpr(SDOperand N);
 521   unsigned SelectExprFP(SDOperand N, unsigned Result);
 522   void Select(SDOperand N);
 523
 524   bool SelectAddr(SDOperand N, unsigned& Reg, int& offset);
 525   void SelectBranchCC(SDOperand N);
 526 };
 527
 528 /// ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
 529 /// returns zero when the input is not exactly a power of two.
 530 static unsigned ExactLog2(unsigned Val) {
 531   if (Val == 0 || (Val & (Val-1))) return 0;
 532   unsigned Count = 0;
 533   while (Val != 1) {
 534     Val >>= 1;
 535     ++Count;
 536   }
 537   return Count;
 538 }
 539
 540 // IsRunOfOnes - returns true if Val consists of one contiguous run of 1's with
 541 // any number of 0's on either side.  the 1's are allowed to wrap from LSB to
 542 // MSB.  so 0x000FFF0, 0x0000FFFF, and 0xFF0000FF are all runs.  0x0F0F0000 is
 543 // not, since all 1's are not contiguous.
 544 static bool IsRunOfOnes(unsigned Val, unsigned &MB, unsigned &ME) {
 545   bool isRun = true;
 546   MB = 0;
 547   ME = 0;
 548
 549   // look for first set bit
 550   int i = 0;
 551   for (; i < 32; i++) {
 552     if ((Val & (1 << (31 - i))) != 0) {
 553       MB = i;
 554       ME = i;
 555       break;
 556     }
 557   }
 558
 559   // look for last set bit
 560   for (; i < 32; i++) {
 561     if ((Val & (1 << (31 - i))) == 0)
 562       break;
 563     ME = i;
 564   }
 565
 566   // look for next set bit
 567   for (; i < 32; i++) {
 568     if ((Val & (1 << (31 - i))) != 0)
 569       break;
 570   }
 571
 572   // if we exhausted all the bits, we found a match at this point for 0*1*0*
 573   if (i == 32)
 574     return true;
 575
 576   // since we just encountered more 1's, if it doesn't wrap around to the
 577   // most significant bit of the word, then we did not find a match to 1*0*1* so
 578   // exit.
 579   if (MB != 0)
 580     return false;
 581
 582   // look for last set bit
 583   for (MB = i; i < 32; i++) {
 584     if ((Val & (1 << (31 - i))) == 0)
 585       break;
 586   }
 587
 588   // if we exhausted all the bits, then we found a match for 1*0*1*, otherwise,
 589   // the value is not a run of ones.
 590   if (i == 32)
 591     return true;
 592   return false;
 593 }
 594
 595 /// getImmediateForOpcode - This method returns a value indicating whether
 596 /// the ConstantSDNode N can be used as an immediate to Opcode.  The return
 597 /// values are either 0, 1 or 2.  0 indicates that either N is not a
 598 /// ConstantSDNode, or is not suitable for use by that opcode.  A return value
 599 /// of 1 indicates that the constant may be used in normal immediate form.  A
 600 /// return value of 2 indicates that the constant may be used in shifted
 601 /// immediate form.  A return value of 3 indicates that log base 2 of the
 602 /// constant may be used.  A return value of 4 indicates that the constant is
 603 /// suitable for conversion into a magic number for integer division.
 604 ///
 605 static unsigned getImmediateForOpcode(SDOperand N, unsigned Opcode,
 606                                       unsigned& Imm, bool U = false) {
 607   if (N.getOpcode() != ISD::Constant) return 0;
 608
 609   int v = (int)cast<ConstantSDNode>(N)->getSignExtended();
 610
 611   switch(Opcode) {
 612   default: return 0;
 613   case ISD::ADD:
 614     if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
 615     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
 616     break;
 617   case ISD::AND:
 618   case ISD::XOR:
 619   case ISD::OR:
 620     if (v >= 0 && v <= 65535) { Imm = v & 0xFFFF; return 1; }
 621     if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
 622     break;
 623   case ISD::MUL:
 624   case ISD::SUB:
 625     if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
 626     break;
 627   case ISD::SETCC:
 628     if (U && (v >= 0 && v <= 65535)) { Imm = v & 0xFFFF; return 1; }
 629     if (!U && (v <= 32767 && v >= -32768)) { Imm = v & 0xFFFF; return 1; }
 630     break;
 631   case ISD::SDIV:
 632     if ((Imm = ExactLog2(v))) { return 3; }
 633     if (v <= -2 || v >= 2) { return 4; }
 634     break;
 635   case ISD::UDIV:
 636     if (v > 1) { return 4; }
 637     break;
 638   }
 639   return 0;
 640 }
 641
 642 /// getBCCForSetCC - Returns the PowerPC condition branch mnemonic corresponding
 643 /// to Condition.  If the Condition is unordered or unsigned, the bool argument
 644 /// U is set to true, otherwise it is set to false.
 645 static unsigned getBCCForSetCC(unsigned Condition, bool& U) {
 646   U = false;
 647   switch (Condition) {
 648   default: assert(0 && "Unknown condition!"); abort();
 649   case ISD::SETEQ:  return PPC::BEQ;
 650   case ISD::SETNE:  return PPC::BNE;
 651   case ISD::SETULT: U = true;
 652   case ISD::SETLT:  return PPC::BLT;
 653   case ISD::SETULE: U = true;
 654   case ISD::SETLE:  return PPC::BLE;
 655   case ISD::SETUGT: U = true;
 656   case ISD::SETGT:  return PPC::BGT;
 657   case ISD::SETUGE: U = true;
 658   case ISD::SETGE:  return PPC::BGE;
 659   }
 660   return 0;
 661 }
 662
 663 /// IndexedOpForOp - Return the indexed variant for each of the PowerPC load
 664 /// and store immediate instructions.
 665 static unsigned IndexedOpForOp(unsigned Opcode) {
 666   switch(Opcode) {
 667   default: assert(0 && "Unknown opcode!"); abort();
 668   case PPC::LBZ: return PPC::LBZX;  case PPC::STB: return PPC::STBX;
 669   case PPC::LHZ: return PPC::LHZX;  case PPC::STH: return PPC::STHX;
 670   case PPC::LHA: return PPC::LHAX;  case PPC::STW: return PPC::STWX;
 671   case PPC::LWZ: return PPC::LWZX;  case PPC::STFS: return PPC::STFSX;
 672   case PPC::LFS: return PPC::LFSX;  case PPC::STFD: return PPC::STFDX;
 673   case PPC::LFD: return PPC::LFDX;
 674   }
 675   return 0;
 676 }
 677
 678 // Structure used to return the necessary information to codegen an SDIV as
 679 // a multiply.
 680 struct ms {
 681   int m; // magic number
 682   int s; // shift amount
 683 };
 684
 685 struct mu {
 686   unsigned int m; // magic number
 687   int a;          // add indicator
 688   int s;          // shift amount
 689 };
 690
 691 /// magic - calculate the magic numbers required to codegen an integer sdiv as
 692 /// a sequence of multiply and shifts.  Requires that the divisor not be 0, 1,
 693 /// or -1.
 694 static struct ms magic(int d) {
 695   int p;
 696   unsigned int ad, anc, delta, q1, r1, q2, r2, t;
 697   const unsigned int two31 = 2147483648U; // 2^31
 698   struct ms mag;
 699
 700   ad = abs(d);
 701   t = two31 + ((unsigned int)d >> 31);
 702   anc = t - 1 - t%ad;   // absolute value of nc
 703   p = 31;               // initialize p
 704   q1 = two31/anc;       // initialize q1 = 2p/abs(nc)
 705   r1 = two31 - q1*anc;  // initialize r1 = rem(2p,abs(nc))
 706   q2 = two31/ad;        // initialize q2 = 2p/abs(d)
 707   r2 = two31 - q2*ad;   // initialize r2 = rem(2p,abs(d))
 708   do {
 709     p = p + 1;
 710     q1 = 2*q1;        // update q1 = 2p/abs(nc)
 711     r1 = 2*r1;        // update r1 = rem(2p/abs(nc))
 712     if (r1 >= anc) {  // must be unsigned comparison
 713       q1 = q1 + 1;
 714       r1 = r1 - anc;
 715     }
 716     q2 = 2*q2;        // update q2 = 2p/abs(d)
 717     r2 = 2*r2;        // update r2 = rem(2p/abs(d))
 718     if (r2 >= ad) {   // must be unsigned comparison
 719       q2 = q2 + 1;
 720       r2 = r2 - ad;
 721     }
 722     delta = ad - r2;
 723   } while (q1 < delta || (q1 == delta && r1 == 0));
 724
 725   mag.m = q2 + 1;
 726   if (d < 0) mag.m = -mag.m; // resulting magic number
 727   mag.s = p - 32;            // resulting shift
 728   return mag;
 729 }
 730
 731 /// magicu - calculate the magic numbers required to codegen an integer udiv as
 732 /// a sequence of multiply, add and shifts.  Requires that the divisor not be 0.
 733 static struct mu magicu(unsigned d)
 734 {
 735   int p;
 736   unsigned int nc, delta, q1, r1, q2, r2;
 737   struct mu magu;
 738   magu.a = 0;               // initialize "add" indicator
 739   nc = - 1 - (-d)%d;
 740   p = 31;                   // initialize p
 741   q1 = 0x80000000/nc;       // initialize q1 = 2p/nc
 742   r1 = 0x80000000 - q1*nc;  // initialize r1 = rem(2p,nc)
 743   q2 = 0x7FFFFFFF/d;        // initialize q2 = (2p-1)/d
 744   r2 = 0x7FFFFFFF - q2*d;   // initialize r2 = rem((2p-1),d)
 745   do {
 746     p = p + 1;
 747     if (r1 >= nc - r1 ) {
 748       q1 = 2*q1 + 1;  // update q1
 749       r1 = 2*r1 - nc; // update r1
 750     }
 751     else {
 752       q1 = 2*q1; // update q1
 753       r1 = 2*r1; // update r1
 754     }
 755     if (r2 + 1 >= d - r2) {
 756       if (q2 >= 0x7FFFFFFF) magu.a = 1;
 757       q2 = 2*q2 + 1;     // update q2
 758       r2 = 2*r2 + 1 - d; // update r2
 759     }
 760     else {
 761       if (q2 >= 0x80000000) magu.a = 1;
 762       q2 = 2*q2;     // update q2
 763       r2 = 2*r2 + 1; // update r2
 764     }
 765     delta = d - 1 - r2;
 766   } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
 767   magu.m = q2 + 1; // resulting magic number
 768   magu.s = p - 32;  // resulting shift
 769   return magu;
 770 }
 771 }
 772
 773 /// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant,
 774 /// return a DAG expression to select that will generate the same value by
 775 /// multiplying by a magic number.  See:
 776 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
 777 SDOperand ISel::BuildSDIVSequence(SDOperand N) {
 778   int d = (int)cast<ConstantSDNode>(N.getOperand(1))->getSignExtended();
 779   ms magics = magic(d);
 780   // Multiply the numerator (operand 0) by the magic value
 781   SDOperand Q = ISelDAG->getNode(ISD::MULHS, MVT::i32, N.getOperand(0),
 782                                  ISelDAG->getConstant(magics.m, MVT::i32));
 783   // If d > 0 and m < 0, add the numerator
 784   if (d > 0 && magics.m < 0)
 785     Q = ISelDAG->getNode(ISD::ADD, MVT::i32, Q, N.getOperand(0));
 786   // If d < 0 and m > 0, subtract the numerator.
 787   if (d < 0 && magics.m > 0)
 788     Q = ISelDAG->getNode(ISD::SUB, MVT::i32, Q, N.getOperand(0));
 789   // Shift right algebraic if shift value is nonzero
 790   if (magics.s > 0)
 791     Q = ISelDAG->getNode(ISD::SRA, MVT::i32, Q,
 792                          ISelDAG->getConstant(magics.s, MVT::i32));
 793   // Extract the sign bit and add it to the quotient
 794   SDOperand T =
 795     ISelDAG->getNode(ISD::SRL, MVT::i32, Q, ISelDAG->getConstant(31, MVT::i32));
 796   return ISelDAG->getNode(ISD::ADD, MVT::i32, Q, T);
 797 }
 798
 799 /// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant,
 800 /// return a DAG expression to select that will generate the same value by
 801 /// multiplying by a magic number.  See:
 802 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
 803 SDOperand ISel::BuildUDIVSequence(SDOperand N) {
 804   unsigned d =
 805     (unsigned)cast<ConstantSDNode>(N.getOperand(1))->getSignExtended();
 806   mu magics = magicu(d);
 807   // Multiply the numerator (operand 0) by the magic value
 808   SDOperand Q = ISelDAG->getNode(ISD::MULHU, MVT::i32, N.getOperand(0),
 809                                  ISelDAG->getConstant(magics.m, MVT::i32));
 810   if (magics.a == 0) {
 811     Q = ISelDAG->getNode(ISD::SRL, MVT::i32, Q,
 812                          ISelDAG->getConstant(magics.s, MVT::i32));
 813   } else {
 814     SDOperand NPQ = ISelDAG->getNode(ISD::SUB, MVT::i32, N.getOperand(0), Q);
 815     NPQ = ISelDAG->getNode(ISD::SRL, MVT::i32, NPQ,
 816                            ISelDAG->getConstant(1, MVT::i32));
 817     NPQ = ISelDAG->getNode(ISD::ADD, MVT::i32, NPQ, Q);
 818     Q = ISelDAG->getNode(ISD::SRL, MVT::i32, NPQ,
 819                            ISelDAG->getConstant(magics.s-1, MVT::i32));
 820   }
 821   return Q;
 822 }
 823
 824 /// getGlobalBaseReg - Output the instructions required to put the
 825 /// base address to use for accessing globals into a register.
 826 ///
 827 unsigned ISel::getGlobalBaseReg() {
 828   if (!GlobalBaseInitialized) {
 829     // Insert the set of GlobalBaseReg into the first MBB of the function
 830     MachineBasicBlock &FirstMBB = BB->getParent()->front();
 831     MachineBasicBlock::iterator MBBI = FirstMBB.begin();
 832     GlobalBaseReg = MakeReg(MVT::i32);
 833     BuildMI(FirstMBB, MBBI, PPC::MovePCtoLR, 0, PPC::LR);
 834     BuildMI(FirstMBB, MBBI, PPC::MFLR, 1, GlobalBaseReg).addReg(PPC::LR);
 835     GlobalBaseInitialized = true;
 836   }
 837   return GlobalBaseReg;
 838 }
 839
 840 /// getConstDouble - Loads a floating point value into a register, via the
 841 /// Constant Pool.  Optionally takes a register in which to load the value.
 842 unsigned ISel::getConstDouble(double doubleVal, unsigned Result=0) {
 843   unsigned Tmp1 = MakeReg(MVT::i32);
 844   if (0 == Result) Result = MakeReg(MVT::f64);
 845   MachineConstantPool *CP = BB->getParent()->getConstantPool();
 846   ConstantFP *CFP = ConstantFP::get(Type::DoubleTy, doubleVal);
 847   unsigned CPI = CP->getConstantPoolIndex(CFP);
 848   BuildMI(BB, PPC::LOADHiAddr, 2, Tmp1).addReg(getGlobalBaseReg())
 849     .addConstantPoolIndex(CPI);
 850   BuildMI(BB, PPC::LFD, 2, Result).addConstantPoolIndex(CPI).addReg(Tmp1);
 851   return Result;
 852 }
 853
 854 /// SelectBitfieldInsert - turn an or of two masked values into
 855 /// the rotate left word immediate then mask insert (rlwimi) instruction.
 856 /// Returns true on success, false if the caller still needs to select OR.
 857 ///
 858 /// Patterns matched:
 859 /// 1. or shl, and   5. or and, and
 860 /// 2. or and, shl   6. or shl, shr
 861 /// 3. or shr, and   7. or shr, shl
 862 /// 4. or and, shr
 863 bool ISel::SelectBitfieldInsert(SDOperand OR, unsigned Result) {
 864   bool IsRotate = false;
 865   unsigned TgtMask = 0xFFFFFFFF, InsMask = 0xFFFFFFFF, Amount = 0;
 866   unsigned Op0Opc = OR.getOperand(0).getOpcode();
 867   unsigned Op1Opc = OR.getOperand(1).getOpcode();
 868
 869   // Verify that we have the correct opcodes
 870   if (ISD::SHL != Op0Opc && ISD::SRL != Op0Opc && ISD::AND != Op0Opc)
 871     return false;
 872   if (ISD::SHL != Op1Opc && ISD::SRL != Op1Opc && ISD::AND != Op1Opc)
 873     return false;
 874
 875   // Generate Mask value for Target
 876   if (ConstantSDNode *CN =
 877       dyn_cast<ConstantSDNode>(OR.getOperand(0).getOperand(1).Val)) {
 878     switch(Op0Opc) {
 879     case ISD::SHL: TgtMask <<= (unsigned)CN->getValue(); break;
 880     case ISD::SRL: TgtMask >>= (unsigned)CN->getValue(); break;
 881     case ISD::AND: TgtMask &= (unsigned)CN->getValue(); break;
 882     }
 883   } else {
 884     return false;
 885   }
 886
 887   // Generate Mask value for Insert
 888   if (ConstantSDNode *CN =
 889       dyn_cast<ConstantSDNode>(OR.getOperand(1).getOperand(1).Val)) {
 890     switch(Op1Opc) {
 891     case ISD::SHL:
 892       Amount = CN->getValue();
 893       InsMask <<= Amount;
 894       if (Op0Opc == ISD::SRL) IsRotate = true;
 895       break;
 896     case ISD::SRL:
 897       Amount = CN->getValue();
 898       InsMask >>= Amount;
 899       Amount = 32-Amount;
 900       if (Op0Opc == ISD::SHL) IsRotate = true;
 901       break;
 902     case ISD::AND:
 903       InsMask &= (unsigned)CN->getValue();
 904       break;
 905     }
 906   } else {
 907     return false;
 908   }
 909
 910   // Verify that the Target mask and Insert mask together form a full word mask
 911   // and that the Insert mask is a run of set bits (which implies both are runs
 912   // of set bits).  Given that, Select the arguments and generate the rlwimi
 913   // instruction.
 914   unsigned MB, ME;
 915   if (((TgtMask ^ InsMask) == 0xFFFFFFFF) && IsRunOfOnes(InsMask, MB, ME)) {
 916     unsigned Tmp1, Tmp2;
 917     // Check for rotlwi / rotrwi here, a special case of bitfield insert
 918     // where both bitfield halves are sourced from the same value.
 919     if (IsRotate &&
 920         OR.getOperand(0).getOperand(0) == OR.getOperand(1).getOperand(0)) {
 921       ++Rotates;  // Statistic
 922       Tmp1 = SelectExpr(OR.getOperand(0).getOperand(0));
 923       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(Amount)
 924         .addImm(0).addImm(31);
 925       return true;
 926     }
 927     if (Op0Opc == ISD::AND)
 928       Tmp1 = SelectExpr(OR.getOperand(0).getOperand(0));
 929     else
 930       Tmp1 = SelectExpr(OR.getOperand(0));
 931     Tmp2 = SelectExpr(OR.getOperand(1).getOperand(0));
 932     BuildMI(BB, PPC::RLWIMI, 5, Result).addReg(Tmp1).addReg(Tmp2)
 933       .addImm(Amount).addImm(MB).addImm(ME);
 934     return true;
 935   }
 936   return false;
 937 }
 938
 939 unsigned ISel::SelectSetCR0(SDOperand CC) {
 940   unsigned Opc, Tmp1, Tmp2;
 941   static const unsigned CompareOpcodes[] =
 942     { PPC::FCMPU, PPC::FCMPU, PPC::CMPW, PPC::CMPLW };
 943
 944   // If the first operand to the select is a SETCC node, then we can fold it
 945   // into the branch that selects which value to return.
 946   SetCCSDNode* SetCC = dyn_cast<SetCCSDNode>(CC.Val);
 947   if (SetCC && CC.getOpcode() == ISD::SETCC) {
 948     bool U;
 949     Opc = getBCCForSetCC(SetCC->getCondition(), U);
 950     Tmp1 = SelectExpr(SetCC->getOperand(0));
 951
 952     // Pass the optional argument U to getImmediateForOpcode for SETCC,
 953     // so that it knows whether the SETCC immediate range is signed or not.
 954     if (1 == getImmediateForOpcode(SetCC->getOperand(1), ISD::SETCC,
 955                                    Tmp2, U)) {
 956       if (U)
 957         BuildMI(BB, PPC::CMPLWI, 2, PPC::CR0).addReg(Tmp1).addImm(Tmp2);
 958       else
 959         BuildMI(BB, PPC::CMPWI, 2, PPC::CR0).addReg(Tmp1).addSImm(Tmp2);
 960     } else {
 961       bool IsInteger = MVT::isInteger(SetCC->getOperand(0).getValueType());
 962       unsigned CompareOpc = CompareOpcodes[2 * IsInteger + U];
 963       Tmp2 = SelectExpr(SetCC->getOperand(1));
 964       BuildMI(BB, CompareOpc, 2, PPC::CR0).addReg(Tmp1).addReg(Tmp2);
 965     }
 966   } else {
 967     Tmp1 = SelectExpr(CC);
 968     BuildMI(BB, PPC::CMPLWI, 2, PPC::CR0).addReg(Tmp1).addImm(0);
 969     Opc = PPC::BNE;
 970   }
 971   return Opc;
 972 }
 973
 974 /// Check to see if the load is a constant offset from a base register
 975 bool ISel::SelectAddr(SDOperand N, unsigned& Reg, int& offset)
 976 {
 977   unsigned imm = 0, opcode = N.getOpcode();
 978   if (N.getOpcode() == ISD::ADD) {
 979     Reg = SelectExpr(N.getOperand(0));
 980     if (1 == getImmediateForOpcode(N.getOperand(1), opcode, imm)) {
 981       offset = imm;
 982       return false;
 983     }
 984     offset = SelectExpr(N.getOperand(1));
 985     return true;
 986   }
 987   Reg = SelectExpr(N);
 988   offset = 0;
 989   return false;
 990 }
 991
 992 void ISel::SelectBranchCC(SDOperand N)
 993 {
 994   MachineBasicBlock *Dest =
 995     cast<BasicBlockSDNode>(N.getOperand(2))->getBasicBlock();
 996
 997   Select(N.getOperand(0));  //chain
 998   unsigned Opc = SelectSetCR0(N.getOperand(1));
 999
1000   // Iterate to the next basic block, unless we're already at the end of the
1001   ilist<MachineBasicBlock>::iterator It = BB, E = BB->getParent()->end();
1002   if (It != E) ++It;
1003
1004   // If this is a two way branch, then grab the fallthrough basic block argument
1005   // and build a PowerPC branch pseudo-op, suitable for long branch conversion
1006   // if necessary by the branch selection pass.  Otherwise, emit a standard
1007   // conditional branch.
1008   if (N.getOpcode() == ISD::BRCONDTWOWAY) {
1009     MachineBasicBlock *Fallthrough =
1010       cast<BasicBlockSDNode>(N.getOperand(3))->getBasicBlock();
1011     if (Dest != It) {
1012       BuildMI(BB, PPC::COND_BRANCH, 4).addReg(PPC::CR0).addImm(Opc)
1013         .addMBB(Dest).addMBB(Fallthrough);
1014       if (Fallthrough != It)
1015         BuildMI(BB, PPC::B, 1).addMBB(Fallthrough);
1016     } else {
1017       if (Fallthrough != It) {
1018         Opc = PPC32InstrInfo::invertPPCBranchOpcode(Opc);
1019         BuildMI(BB, PPC::COND_BRANCH, 4).addReg(PPC::CR0).addImm(Opc)
1020           .addMBB(Fallthrough).addMBB(Dest);
1021       }
1022     }
1023   } else {
1024     BuildMI(BB, Opc, 2).addReg(PPC::CR0).addMBB(Dest);
1025   }
1026   return;
1027 }
1028
1029 unsigned ISel::SelectExprFP(SDOperand N, unsigned Result)
1030 {
1031   unsigned Tmp1, Tmp2, Tmp3;
1032   unsigned Opc = 0;
1033   SDNode *Node = N.Val;
1034   MVT::ValueType DestType = N.getValueType();
1035   unsigned opcode = N.getOpcode();
1036
1037   switch (opcode) {
1038   default:
1039     Node->dump();
1040     assert(0 && "Node not handled!\n");
1041
1042   case ISD::SELECT: {
1043     // Attempt to generate FSEL.  We can do this whenever we have an FP result,
1044     // and an FP comparison in the SetCC node.
1045     SetCCSDNode* SetCC = dyn_cast<SetCCSDNode>(N.getOperand(0).Val);
1046     if (SetCC && N.getOperand(0).getOpcode() == ISD::SETCC &&
1047         !MVT::isInteger(SetCC->getOperand(0).getValueType()) &&
1048         SetCC->getCondition() != ISD::SETEQ &&
1049         SetCC->getCondition() != ISD::SETNE) {
1050       MVT::ValueType VT = SetCC->getOperand(0).getValueType();
1051       unsigned TV = SelectExpr(N.getOperand(1)); // Use if TRUE
1052       unsigned FV = SelectExpr(N.getOperand(2)); // Use if FALSE
1053
1054       ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(SetCC->getOperand(1));
1055       if (CN && (CN->isExactlyValue(-0.0) || CN->isExactlyValue(0.0))) {
1056         switch(SetCC->getCondition()) {
1057         default: assert(0 && "Invalid FSEL condition"); abort();
1058         case ISD::SETULT:
1059         case ISD::SETLT:
1060           std::swap(TV, FV);  // fsel is natively setge, swap operands for setlt
1061         case ISD::SETUGE:
1062         case ISD::SETGE:
1063           Tmp1 = SelectExpr(SetCC->getOperand(0));   // Val to compare against
1064           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp1).addReg(TV).addReg(FV);
1065           return Result;
1066         case ISD::SETUGT:
1067         case ISD::SETGT:
1068           std::swap(TV, FV);  // fsel is natively setge, swap operands for setlt
1069         case ISD::SETULE:
1070         case ISD::SETLE: {
1071           if (SetCC->getOperand(0).getOpcode() == ISD::FNEG) {
1072             Tmp2 = SelectExpr(SetCC->getOperand(0).getOperand(0));
1073           } else {
1074             Tmp2 = MakeReg(VT);
1075             Tmp1 = SelectExpr(SetCC->getOperand(0));   // Val to compare against
1076             BuildMI(BB, PPC::FNEG, 1, Tmp2).addReg(Tmp1);
1077           }
1078           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp2).addReg(TV).addReg(FV);
1079           return Result;
1080         }
1081         }
1082       } else {
1083         Opc = (MVT::f64 == VT) ? PPC::FSUB : PPC::FSUBS;
1084         Tmp1 = SelectExpr(SetCC->getOperand(0));   // Val to compare against
1085         Tmp2 = SelectExpr(SetCC->getOperand(1));
1086         Tmp3 =  MakeReg(VT);
1087         switch(SetCC->getCondition()) {
1088         default: assert(0 && "Invalid FSEL condition"); abort();
1089         case ISD::SETULT:
1090         case ISD::SETLT:
1091           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
1092           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(FV).addReg(TV);
1093           return Result;
1094         case ISD::SETUGE:
1095         case ISD::SETGE:
1096           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
1097           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(TV).addReg(FV);
1098           return Result;
1099         case ISD::SETUGT:
1100         case ISD::SETGT:
1101           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1102           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(FV).addReg(TV);
1103           return Result;
1104         case ISD::SETULE:
1105         case ISD::SETLE:
1106           BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
1107           BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(TV).addReg(FV);
1108           return Result;
1109         }
1110       }
1111       assert(0 && "Should never get here");
1112       return 0;
1113     }
1114
1115     unsigned TrueValue = SelectExpr(N.getOperand(1)); //Use if TRUE
1116     unsigned FalseValue = SelectExpr(N.getOperand(2)); //Use if FALSE
1117     Opc = SelectSetCR0(N.getOperand(0));
1118
1119     // Create an iterator with which to insert the MBB for copying the false
1120     // value and the MBB to hold the PHI instruction for this SetCC.
1121     MachineBasicBlock *thisMBB = BB;
1122     const BasicBlock *LLVM_BB = BB->getBasicBlock();
1123     ilist<MachineBasicBlock>::iterator It = BB;
1124     ++It;
1125
1126     //  thisMBB:
1127     //  ...
1128     //   TrueVal = ...
1129     //   cmpTY cr0, r1, r2
1130     //   bCC copy1MBB
1131     //   fallthrough --> copy0MBB
1132     MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
1133     MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
1134     BuildMI(BB, Opc, 2).addReg(PPC::CR0).addMBB(sinkMBB);
1135     MachineFunction *F = BB->getParent();
1136     F->getBasicBlockList().insert(It, copy0MBB);
1137     F->getBasicBlockList().insert(It, sinkMBB);
1138     // Update machine-CFG edges
1139     BB->addSuccessor(copy0MBB);
1140     BB->addSuccessor(sinkMBB);
1141
1142     //  copy0MBB:
1143     //   %FalseValue = ...
1144     //   # fallthrough to sinkMBB
1145     BB = copy0MBB;
1146     // Update machine-CFG edges
1147     BB->addSuccessor(sinkMBB);
1148
1149     //  sinkMBB:
1150     //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
1151     //  ...
1152     BB = sinkMBB;
1153     BuildMI(BB, PPC::PHI, 4, Result).addReg(FalseValue)
1154       .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
1155     return Result;
1156   }
1157
1158   case ISD::FNEG:
1159     if (!NoExcessFPPrecision &&
1160         ISD::ADD == N.getOperand(0).getOpcode() &&
1161         N.getOperand(0).Val->hasOneUse() &&
1162         ISD::MUL == N.getOperand(0).getOperand(0).getOpcode() &&
1163         N.getOperand(0).getOperand(0).Val->hasOneUse()) {
1164       ++FusedFP; // Statistic
1165       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(0));
1166       Tmp2 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(1));
1167       Tmp3 = SelectExpr(N.getOperand(0).getOperand(1));
1168       Opc = DestType == MVT::f64 ? PPC::FNMADD : PPC::FNMADDS;
1169       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1170     } else if (!NoExcessFPPrecision &&
1171         ISD::ADD == N.getOperand(0).getOpcode() &&
1172         N.getOperand(0).Val->hasOneUse() &&
1173         ISD::MUL == N.getOperand(0).getOperand(1).getOpcode() &&
1174         N.getOperand(0).getOperand(1).Val->hasOneUse()) {
1175       ++FusedFP; // Statistic
1176       Tmp1 = SelectExpr(N.getOperand(0).getOperand(1).getOperand(0));
1177       Tmp2 = SelectExpr(N.getOperand(0).getOperand(1).getOperand(1));
1178       Tmp3 = SelectExpr(N.getOperand(0).getOperand(0));
1179       Opc = DestType == MVT::f64 ? PPC::FNMADD : PPC::FNMADDS;
1180       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1181     } else if (ISD::FABS == N.getOperand(0).getOpcode()) {
1182       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1183       BuildMI(BB, PPC::FNABS, 1, Result).addReg(Tmp1);
1184     } else {
1185       Tmp1 = SelectExpr(N.getOperand(0));
1186       BuildMI(BB, PPC::FNEG, 1, Result).addReg(Tmp1);
1187     }
1188     return Result;
1189
1190   case ISD::FABS:
1191     Tmp1 = SelectExpr(N.getOperand(0));
1192     BuildMI(BB, PPC::FABS, 1, Result).addReg(Tmp1);
1193     return Result;
1194
1195   case ISD::FP_ROUND:
1196     assert (DestType == MVT::f32 &&
1197             N.getOperand(0).getValueType() == MVT::f64 &&
1198             "only f64 to f32 conversion supported here");
1199     Tmp1 = SelectExpr(N.getOperand(0));
1200     BuildMI(BB, PPC::FRSP, 1, Result).addReg(Tmp1);
1201     return Result;
1202
1203   case ISD::FP_EXTEND:
1204     assert (DestType == MVT::f64 &&
1205             N.getOperand(0).getValueType() == MVT::f32 &&
1206             "only f32 to f64 conversion supported here");
1207     Tmp1 = SelectExpr(N.getOperand(0));
1208     BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
1209     return Result;
1210
1211   case ISD::CopyFromReg:
1212     if (Result == 1)
1213       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1214     Tmp1 = dyn_cast<RegSDNode>(Node)->getReg();
1215     BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
1216     return Result;
1217
1218   case ISD::ConstantFP: {
1219     ConstantFPSDNode *CN = cast<ConstantFPSDNode>(N);
1220     Result = getConstDouble(CN->getValue(), Result);
1221     return Result;
1222   }
1223
1224   case ISD::ADD:
1225     if (!NoExcessFPPrecision && N.getOperand(0).getOpcode() == ISD::MUL &&
1226         N.getOperand(0).Val->hasOneUse()) {
1227       ++FusedFP; // Statistic
1228       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1229       Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1230       Tmp3 = SelectExpr(N.getOperand(1));
1231       Opc = DestType == MVT::f64 ? PPC::FMADD : PPC::FMADDS;
1232       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1233       return Result;
1234     }
1235     if (!NoExcessFPPrecision && N.getOperand(1).getOpcode() == ISD::MUL &&
1236         N.getOperand(1).Val->hasOneUse()) {
1237       ++FusedFP; // Statistic
1238       Tmp1 = SelectExpr(N.getOperand(1).getOperand(0));
1239       Tmp2 = SelectExpr(N.getOperand(1).getOperand(1));
1240       Tmp3 = SelectExpr(N.getOperand(0));
1241       Opc = DestType == MVT::f64 ? PPC::FMADD : PPC::FMADDS;
1242       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1243       return Result;
1244     }
1245     Opc = DestType == MVT::f64 ? PPC::FADD : PPC::FADDS;
1246     Tmp1 = SelectExpr(N.getOperand(0));
1247     Tmp2 = SelectExpr(N.getOperand(1));
1248     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1249     return Result;
1250
1251   case ISD::SUB:
1252     if (!NoExcessFPPrecision && N.getOperand(0).getOpcode() == ISD::MUL &&
1253         N.getOperand(0).Val->hasOneUse()) {
1254       ++FusedFP; // Statistic
1255       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1256       Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1257       Tmp3 = SelectExpr(N.getOperand(1));
1258       Opc = DestType == MVT::f64 ? PPC::FMSUB : PPC::FMSUBS;
1259       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1260       return Result;
1261     }
1262     if (!NoExcessFPPrecision && N.getOperand(1).getOpcode() == ISD::MUL &&
1263         N.getOperand(1).Val->hasOneUse()) {
1264       ++FusedFP; // Statistic
1265       Tmp1 = SelectExpr(N.getOperand(1).getOperand(0));
1266       Tmp2 = SelectExpr(N.getOperand(1).getOperand(1));
1267       Tmp3 = SelectExpr(N.getOperand(0));
1268       Opc = DestType == MVT::f64 ? PPC::FNMSUB : PPC::FNMSUBS;
1269       BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
1270       return Result;
1271     }
1272     Opc = DestType == MVT::f64 ? PPC::FSUB : PPC::FSUBS;
1273     Tmp1 = SelectExpr(N.getOperand(0));
1274     Tmp2 = SelectExpr(N.getOperand(1));
1275     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1276     return Result;
1277
1278   case ISD::MUL:
1279   case ISD::SDIV:
1280     switch( opcode ) {
1281     case ISD::MUL:  Opc = DestType == MVT::f64 ? PPC::FMUL : PPC::FMULS; break;
1282     case ISD::SDIV: Opc = DestType == MVT::f64 ? PPC::FDIV : PPC::FDIVS; break;
1283     };
1284     Tmp1 = SelectExpr(N.getOperand(0));
1285     Tmp2 = SelectExpr(N.getOperand(1));
1286     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1287     return Result;
1288
1289   case ISD::UINT_TO_FP:
1290   case ISD::SINT_TO_FP: {
1291     assert (N.getOperand(0).getValueType() == MVT::i32
1292             && "int to float must operate on i32");
1293     bool IsUnsigned = (ISD::UINT_TO_FP == opcode);
1294     Tmp1 = SelectExpr(N.getOperand(0));  // Get the operand register
1295     Tmp2 = MakeReg(MVT::f64); // temp reg to load the integer value into
1296     Tmp3 = MakeReg(MVT::i32); // temp reg to hold the conversion constant
1297     unsigned ConstF = MakeReg(MVT::f64); // temp reg to hold the fp constant
1298
1299     int FrameIdx = BB->getParent()->getFrameInfo()->CreateStackObject(8, 8);
1300     MachineConstantPool *CP = BB->getParent()->getConstantPool();
1301
1302     // FIXME: pull this FP constant generation stuff out into something like
1303     // the simple ISel's getReg.
1304     if (IsUnsigned) {
1305       ConstantFP *CFP = ConstantFP::get(Type::DoubleTy, 0x1.000000p52);
1306       unsigned CPI = CP->getConstantPoolIndex(CFP);
1307       // Load constant fp value
1308       unsigned Tmp4 = MakeReg(MVT::i32);
1309       BuildMI(BB, PPC::LOADHiAddr, 2, Tmp4).addReg(getGlobalBaseReg())
1310         .addConstantPoolIndex(CPI);
1311       BuildMI(BB, PPC::LFD, 2, ConstF).addConstantPoolIndex(CPI).addReg(Tmp4);
1312       // Store the hi & low halves of the fp value, currently in int regs
1313       BuildMI(BB, PPC::LIS, 1, Tmp3).addSImm(0x4330);
1314       addFrameReference(BuildMI(BB, PPC::STW, 3).addReg(Tmp3), FrameIdx);
1315       addFrameReference(BuildMI(BB, PPC::STW, 3).addReg(Tmp1), FrameIdx, 4);
1316       addFrameReference(BuildMI(BB, PPC::LFD, 2, Tmp2), FrameIdx);
1317       // Generate the return value with a subtract
1318       BuildMI(BB, PPC::FSUB, 2, Result).addReg(Tmp2).addReg(ConstF);
1319     } else {
1320       ConstantFP *CFP = ConstantFP::get(Type::DoubleTy, 0x1.000008p52);
1321       unsigned CPI = CP->getConstantPoolIndex(CFP);
1322       // Load constant fp value
1323       unsigned Tmp4 = MakeReg(MVT::i32);
1324       unsigned TmpL = MakeReg(MVT::i32);
1325       BuildMI(BB, PPC::LOADHiAddr, 2, Tmp4).addReg(getGlobalBaseReg())
1326         .addConstantPoolIndex(CPI);
1327       BuildMI(BB, PPC::LFD, 2, ConstF).addConstantPoolIndex(CPI).addReg(Tmp4);
1328       // Store the hi & low halves of the fp value, currently in int regs
1329       BuildMI(BB, PPC::LIS, 1, Tmp3).addSImm(0x4330);
1330       addFrameReference(BuildMI(BB, PPC::STW, 3).addReg(Tmp3), FrameIdx);
1331       BuildMI(BB, PPC::XORIS, 2, TmpL).addReg(Tmp1).addImm(0x8000);
1332       addFrameReference(BuildMI(BB, PPC::STW, 3).addReg(TmpL), FrameIdx, 4);
1333       addFrameReference(BuildMI(BB, PPC::LFD, 2, Tmp2), FrameIdx);
1334       // Generate the return value with a subtract
1335       BuildMI(BB, PPC::FSUB, 2, Result).addReg(Tmp2).addReg(ConstF);
1336     }
1337     return Result;
1338   }
1339   }
1340   assert(0 && "Should never get here");
1341   return 0;
1342 }
1343
1344 unsigned ISel::SelectExpr(SDOperand N) {
1345   unsigned Result;
1346   unsigned Tmp1, Tmp2, Tmp3;
1347   unsigned Opc = 0;
1348   unsigned opcode = N.getOpcode();
1349
1350   SDNode *Node = N.Val;
1351   MVT::ValueType DestType = N.getValueType();
1352
1353   unsigned &Reg = ExprMap[N];
1354   if (Reg) return Reg;
1355
1356   switch (N.getOpcode()) {
1357   default:
1358     Reg = Result = (N.getValueType() != MVT::Other) ?
1359                             MakeReg(N.getValueType()) : 1;
1360     break;
1361   case ISD::CALL:
1362     // If this is a call instruction, make sure to prepare ALL of the result
1363     // values as well as the chain.
1364     if (Node->getNumValues() == 1)
1365       Reg = Result = 1;  // Void call, just a chain.
1366     else {
1367       Result = MakeReg(Node->getValueType(0));
1368       ExprMap[N.getValue(0)] = Result;
1369       for (unsigned i = 1, e = N.Val->getNumValues()-1; i != e; ++i)
1370         ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
1371       ExprMap[SDOperand(Node, Node->getNumValues()-1)] = 1;
1372     }
1373     break;
1374   case ISD::ADD_PARTS:
1375   case ISD::SUB_PARTS:
1376   case ISD::SHL_PARTS:
1377   case ISD::SRL_PARTS:
1378   case ISD::SRA_PARTS:
1379     Result = MakeReg(Node->getValueType(0));
1380     ExprMap[N.getValue(0)] = Result;
1381     for (unsigned i = 1, e = N.Val->getNumValues(); i != e; ++i)
1382       ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
1383     break;
1384   }
1385
1386   if (ISD::CopyFromReg == opcode)
1387     DestType = N.getValue(0).getValueType();
1388
1389   if (DestType == MVT::f64 || DestType == MVT::f32)
1390     if (ISD::LOAD != opcode && ISD::EXTLOAD != opcode && ISD::UNDEF != opcode)
1391       return SelectExprFP(N, Result);
1392
1393   switch (opcode) {
1394   default:
1395     Node->dump();
1396     assert(0 && "Node not handled!\n");
1397   case ISD::UNDEF:
1398     BuildMI(BB, PPC::IMPLICIT_DEF, 0, Result);
1399     return Result;
1400   case ISD::DYNAMIC_STACKALLOC:
1401     // Generate both result values.  FIXME: Need a better commment here?
1402     if (Result != 1)
1403       ExprMap[N.getValue(1)] = 1;
1404     else
1405       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1406
1407     // FIXME: We are currently ignoring the requested alignment for handling
1408     // greater than the stack alignment.  This will need to be revisited at some
1409     // point.  Align = N.getOperand(2);
1410     if (!isa<ConstantSDNode>(N.getOperand(2)) ||
1411         cast<ConstantSDNode>(N.getOperand(2))->getValue() != 0) {
1412       std::cerr << "Cannot allocate stack object with greater alignment than"
1413                 << " the stack alignment yet!";
1414       abort();
1415     }
1416     Select(N.getOperand(0));
1417     Tmp1 = SelectExpr(N.getOperand(1));
1418     // Subtract size from stack pointer, thereby allocating some space.
1419     BuildMI(BB, PPC::SUBF, 2, PPC::R1).addReg(Tmp1).addReg(PPC::R1);
1420     // Put a pointer to the space into the result register by copying the SP
1421     BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R1).addReg(PPC::R1);
1422     return Result;
1423
1424   case ISD::ConstantPool:
1425     Tmp1 = cast<ConstantPoolSDNode>(N)->getIndex();
1426     Tmp2 = MakeReg(MVT::i32);
1427     BuildMI(BB, PPC::LOADHiAddr, 2, Tmp2).addReg(getGlobalBaseReg())
1428       .addConstantPoolIndex(Tmp1);
1429     BuildMI(BB, PPC::LA, 2, Result).addReg(Tmp2).addConstantPoolIndex(Tmp1);
1430     return Result;
1431
1432   case ISD::FrameIndex:
1433     Tmp1 = cast<FrameIndexSDNode>(N)->getIndex();
1434     addFrameReference(BuildMI(BB, PPC::ADDI, 2, Result), (int)Tmp1, 0, false);
1435     return Result;
1436
1437   case ISD::GlobalAddress: {
1438     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
1439     Tmp1 = MakeReg(MVT::i32);
1440     BuildMI(BB, PPC::LOADHiAddr, 2, Tmp1).addReg(getGlobalBaseReg())
1441       .addGlobalAddress(GV);
1442     if (GV->hasWeakLinkage() || GV->isExternal()) {
1443       BuildMI(BB, PPC::LWZ, 2, Result).addGlobalAddress(GV).addReg(Tmp1);
1444     } else {
1445       BuildMI(BB, PPC::LA, 2, Result).addReg(Tmp1).addGlobalAddress(GV);
1446     }
1447     return Result;
1448   }
1449
1450   case ISD::LOAD:
1451   case ISD::EXTLOAD:
1452   case ISD::ZEXTLOAD:
1453   case ISD::SEXTLOAD: {
1454     MVT::ValueType TypeBeingLoaded = (ISD::LOAD == opcode) ?
1455       Node->getValueType(0) : cast<MVTSDNode>(Node)->getExtraValueType();
1456     bool sext = (ISD::SEXTLOAD == opcode);
1457
1458     // Make sure we generate both values.
1459     if (Result != 1)
1460       ExprMap[N.getValue(1)] = 1;   // Generate the token
1461     else
1462       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1463
1464     SDOperand Chain   = N.getOperand(0);
1465     SDOperand Address = N.getOperand(1);
1466     Select(Chain);
1467
1468     switch (TypeBeingLoaded) {
1469     default: Node->dump(); assert(0 && "Cannot load this type!");
1470     case MVT::i1:  Opc = PPC::LBZ; break;
1471     case MVT::i8:  Opc = PPC::LBZ; break;
1472     case MVT::i16: Opc = sext ? PPC::LHA : PPC::LHZ; break;
1473     case MVT::i32: Opc = PPC::LWZ; break;
1474     case MVT::f32: Opc = PPC::LFS; break;
1475     case MVT::f64: Opc = PPC::LFD; break;
1476     }
1477
1478     if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Address)) {
1479       Tmp1 = MakeReg(MVT::i32);
1480       int CPI = CP->getIndex();
1481       BuildMI(BB, PPC::LOADHiAddr, 2, Tmp1).addReg(getGlobalBaseReg())
1482         .addConstantPoolIndex(CPI);
1483       BuildMI(BB, Opc, 2, Result).addConstantPoolIndex(CPI).addReg(Tmp1);
1484     }
1485     else if(Address.getOpcode() == ISD::FrameIndex) {
1486       Tmp1 = cast<FrameIndexSDNode>(Address)->getIndex();
1487       addFrameReference(BuildMI(BB, Opc, 2, Result), (int)Tmp1);
1488     } else {
1489       int offset;
1490       bool idx = SelectAddr(Address, Tmp1, offset);
1491       if (idx) {
1492         Opc = IndexedOpForOp(Opc);
1493         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(offset);
1494       } else {
1495         BuildMI(BB, Opc, 2, Result).addSImm(offset).addReg(Tmp1);
1496       }
1497     }
1498     return Result;
1499   }
1500
1501   case ISD::CALL: {
1502     unsigned GPR_idx = 0, FPR_idx = 0;
1503     static const unsigned GPR[] = {
1504       PPC::R3, PPC::R4, PPC::R5, PPC::R6,
1505       PPC::R7, PPC::R8, PPC::R9, PPC::R10,
1506     };
1507     static const unsigned FPR[] = {
1508       PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
1509       PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
1510     };
1511
1512     // Lower the chain for this call.
1513     Select(N.getOperand(0));
1514     ExprMap[N.getValue(Node->getNumValues()-1)] = 1;
1515
1516     MachineInstr *CallMI;
1517     // Emit the correct call instruction based on the type of symbol called.
1518     if (GlobalAddressSDNode *GASD =
1519         dyn_cast<GlobalAddressSDNode>(N.getOperand(1))) {
1520       CallMI = BuildMI(PPC::CALLpcrel, 1).addGlobalAddress(GASD->getGlobal(),
1521                                                            true);
1522     } else if (ExternalSymbolSDNode *ESSDN =
1523                dyn_cast<ExternalSymbolSDNode>(N.getOperand(1))) {
1524       CallMI = BuildMI(PPC::CALLpcrel, 1).addExternalSymbol(ESSDN->getSymbol(),
1525                                                             true);
1526     } else {
1527       Tmp1 = SelectExpr(N.getOperand(1));
1528       BuildMI(BB, PPC::OR, 2, PPC::R12).addReg(Tmp1).addReg(Tmp1);
1529       BuildMI(BB, PPC::MTCTR, 1).addReg(PPC::R12);
1530       CallMI = BuildMI(PPC::CALLindirect, 3).addImm(20).addImm(0)
1531         .addReg(PPC::R12);
1532     }
1533
1534     // Load the register args to virtual regs
1535     std::vector<unsigned> ArgVR;
1536     for(int i = 2, e = Node->getNumOperands(); i < e; ++i)
1537       ArgVR.push_back(SelectExpr(N.getOperand(i)));
1538
1539     // Copy the virtual registers into the appropriate argument register
1540     for(int i = 0, e = ArgVR.size(); i < e; ++i) {
1541       switch(N.getOperand(i+2).getValueType()) {
1542       default: Node->dump(); assert(0 && "Unknown value type for call");
1543       case MVT::i1:
1544       case MVT::i8:
1545       case MVT::i16:
1546       case MVT::i32:
1547         assert(GPR_idx < 8 && "Too many int args");
1548         if (N.getOperand(i+2).getOpcode() != ISD::UNDEF) {
1549           BuildMI(BB, PPC::OR,2,GPR[GPR_idx]).addReg(ArgVR[i]).addReg(ArgVR[i]);
1550           CallMI->addRegOperand(GPR[GPR_idx], MachineOperand::Use);
1551         }
1552         ++GPR_idx;
1553         break;
1554       case MVT::f64:
1555       case MVT::f32:
1556         assert(FPR_idx < 13 && "Too many fp args");
1557         BuildMI(BB, PPC::FMR, 1, FPR[FPR_idx]).addReg(ArgVR[i]);
1558         CallMI->addRegOperand(FPR[FPR_idx], MachineOperand::Use);
1559         ++FPR_idx;
1560         break;
1561       }
1562     }
1563
1564     // Put the call instruction in the correct place in the MachineBasicBlock
1565     BB->push_back(CallMI);
1566
1567     switch (Node->getValueType(0)) {
1568     default: assert(0 && "Unknown value type for call result!");
1569     case MVT::Other: return 1;
1570     case MVT::i1:
1571     case MVT::i8:
1572     case MVT::i16:
1573     case MVT::i32:
1574       if (Node->getValueType(1) == MVT::i32) {
1575         BuildMI(BB, PPC::OR, 2, Result+1).addReg(PPC::R3).addReg(PPC::R3);
1576         BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R4).addReg(PPC::R4);
1577       } else {
1578         BuildMI(BB, PPC::OR, 2, Result).addReg(PPC::R3).addReg(PPC::R3);
1579       }
1580       break;
1581     case MVT::f32:
1582     case MVT::f64:
1583       BuildMI(BB, PPC::FMR, 1, Result).addReg(PPC::F1);
1584       break;
1585     }
1586     return Result+N.ResNo;
1587   }
1588
1589   case ISD::SIGN_EXTEND:
1590   case ISD::SIGN_EXTEND_INREG:
1591     Tmp1 = SelectExpr(N.getOperand(0));
1592     switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
1593     default: Node->dump(); assert(0 && "Unhandled SIGN_EXTEND type"); break;
1594     case MVT::i16:
1595       BuildMI(BB, PPC::EXTSH, 1, Result).addReg(Tmp1);
1596       break;
1597     case MVT::i8:
1598       BuildMI(BB, PPC::EXTSB, 1, Result).addReg(Tmp1);
1599       break;
1600     case MVT::i1:
1601       BuildMI(BB, PPC::SUBFIC, 2, Result).addReg(Tmp1).addSImm(0);
1602       break;
1603     }
1604     return Result;
1605
1606   case ISD::ZERO_EXTEND_INREG:
1607     Tmp1 = SelectExpr(N.getOperand(0));
1608     switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
1609     default: Node->dump(); assert(0 && "Unhandled ZERO_EXTEND type"); break;
1610     case MVT::i16:  Tmp2 = 16; break;
1611     case MVT::i8:   Tmp2 = 24; break;
1612     case MVT::i1:   Tmp2 = 31; break;
1613     }
1614     BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(0).addImm(Tmp2)
1615       .addImm(31);
1616     return Result;
1617
1618   case ISD::CopyFromReg:
1619     if (Result == 1)
1620       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1621     Tmp1 = dyn_cast<RegSDNode>(Node)->getReg();
1622     BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp1).addReg(Tmp1);
1623     return Result;
1624
1625   case ISD::SHL:
1626     Tmp1 = SelectExpr(N.getOperand(0));
1627     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1628       Tmp2 = CN->getValue() & 0x1F;
1629       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(Tmp2).addImm(0)
1630         .addImm(31-Tmp2);
1631     } else {
1632       Tmp2 = SelectExpr(N.getOperand(1));
1633       BuildMI(BB, PPC::SLW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1634     }
1635     return Result;
1636
1637   case ISD::SRL:
1638     Tmp1 = SelectExpr(N.getOperand(0));
1639     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1640       Tmp2 = CN->getValue() & 0x1F;
1641       BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(32-Tmp2)
1642         .addImm(Tmp2).addImm(31);
1643     } else {
1644       Tmp2 = SelectExpr(N.getOperand(1));
1645       BuildMI(BB, PPC::SRW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1646     }
1647     return Result;
1648
1649   case ISD::SRA:
1650     Tmp1 = SelectExpr(N.getOperand(0));
1651     if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
1652       Tmp2 = CN->getValue() & 0x1F;
1653       BuildMI(BB, PPC::SRAWI, 2, Result).addReg(Tmp1).addImm(Tmp2);
1654     } else {
1655       Tmp2 = SelectExpr(N.getOperand(1));
1656       BuildMI(BB, PPC::SRAW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1657     }
1658     return Result;
1659
1660   case ISD::ADD:
1661     assert (DestType == MVT::i32 && "Only do arithmetic on i32s!");
1662     Tmp1 = SelectExpr(N.getOperand(0));
1663     switch(getImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
1664       default: assert(0 && "unhandled result code");
1665       case 0: // No immediate
1666         Tmp2 = SelectExpr(N.getOperand(1));
1667         BuildMI(BB, PPC::ADD, 2, Result).addReg(Tmp1).addReg(Tmp2);
1668         break;
1669       case 1: // Low immediate
1670         BuildMI(BB, PPC::ADDI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
1671         break;
1672       case 2: // Shifted immediate
1673         BuildMI(BB, PPC::ADDIS, 2, Result).addReg(Tmp1).addSImm(Tmp2);
1674         break;
1675     }
1676     return Result;
1677
1678   case ISD::AND:
1679     Tmp1 = SelectExpr(N.getOperand(0));
1680     // FIXME: should add check in getImmediateForOpcode to return a value
1681     // indicating the immediate is a run of set bits so we can emit a bitfield
1682     // clear with RLWINM instead.
1683     switch(getImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
1684       default: assert(0 && "unhandled result code");
1685       case 0: // No immediate
1686         Tmp2 = SelectExpr(N.getOperand(1));
1687         BuildMI(BB, PPC::AND, 2, Result).addReg(Tmp1).addReg(Tmp2);
1688         break;
1689       case 1: // Low immediate
1690         BuildMI(BB, PPC::ANDIo, 2, Result).addReg(Tmp1).addImm(Tmp2);
1691         break;
1692       case 2: // Shifted immediate
1693         BuildMI(BB, PPC::ANDISo, 2, Result).addReg(Tmp1).addImm(Tmp2);
1694         break;
1695     }
1696     return Result;
1697
1698   case ISD::OR:
1699     if (SelectBitfieldInsert(N, Result))
1700       return Result;
1701     Tmp1 = SelectExpr(N.getOperand(0));
1702     switch(getImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
1703       default: assert(0 && "unhandled result code");
1704       case 0: // No immediate
1705         Tmp2 = SelectExpr(N.getOperand(1));
1706         BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp1).addReg(Tmp2);
1707         break;
1708       case 1: // Low immediate
1709         BuildMI(BB, PPC::ORI, 2, Result).addReg(Tmp1).addImm(Tmp2);
1710         break;
1711       case 2: // Shifted immediate
1712         BuildMI(BB, PPC::ORIS, 2, Result).addReg(Tmp1).addImm(Tmp2);
1713         break;
1714     }
1715     return Result;
1716
1717   case ISD::XOR: {
1718     // Check for EQV: xor, (xor a, -1), b
1719     if (N.getOperand(0).getOpcode() == ISD::XOR &&
1720         N.getOperand(0).getOperand(1).getOpcode() == ISD::Constant &&
1721         cast<ConstantSDNode>(N.getOperand(0).getOperand(1))->isAllOnesValue()) {
1722       Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1723       Tmp2 = SelectExpr(N.getOperand(1));
1724       BuildMI(BB, PPC::EQV, 2, Result).addReg(Tmp1).addReg(Tmp2);
1725       return Result;
1726     }
1727     // Check for NOT, NOR, and NAND: xor (copy, or, and), -1
1728     if (N.getOperand(1).getOpcode() == ISD::Constant &&
1729         cast<ConstantSDNode>(N.getOperand(1))->isAllOnesValue()) {
1730       switch(N.getOperand(0).getOpcode()) {
1731       case ISD::OR:
1732         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1733         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1734         BuildMI(BB, PPC::NOR, 2, Result).addReg(Tmp1).addReg(Tmp2);
1735         break;
1736       case ISD::AND:
1737         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1738         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1739         BuildMI(BB, PPC::NAND, 2, Result).addReg(Tmp1).addReg(Tmp2);
1740         break;
1741       default:
1742         Tmp1 = SelectExpr(N.getOperand(0));
1743         BuildMI(BB, PPC::NOR, 2, Result).addReg(Tmp1).addReg(Tmp1);
1744         break;
1745       }
1746       return Result;
1747     }
1748     Tmp1 = SelectExpr(N.getOperand(0));
1749     switch(getImmediateForOpcode(N.getOperand(1), opcode, Tmp2)) {
1750       default: assert(0 && "unhandled result code");
1751       case 0: // No immediate
1752         Tmp2 = SelectExpr(N.getOperand(1));
1753         BuildMI(BB, PPC::XOR, 2, Result).addReg(Tmp1).addReg(Tmp2);
1754         break;
1755       case 1: // Low immediate
1756         BuildMI(BB, PPC::XORI, 2, Result).addReg(Tmp1).addImm(Tmp2);
1757         break;
1758       case 2: // Shifted immediate
1759         BuildMI(BB, PPC::XORIS, 2, Result).addReg(Tmp1).addImm(Tmp2);
1760         break;
1761     }
1762     return Result;
1763   }
1764
1765   case ISD::SUB:
1766     Tmp2 = SelectExpr(N.getOperand(1));
1767     if (1 == getImmediateForOpcode(N.getOperand(0), opcode, Tmp1))
1768       BuildMI(BB, PPC::SUBFIC, 2, Result).addReg(Tmp2).addSImm(Tmp1);
1769     else {
1770       Tmp1 = SelectExpr(N.getOperand(0));
1771       BuildMI(BB, PPC::SUBF, 2, Result).addReg(Tmp2).addReg(Tmp1);
1772     }
1773     return Result;
1774
1775   case ISD::MUL:
1776     Tmp1 = SelectExpr(N.getOperand(0));
1777     if (1 == getImmediateForOpcode(N.getOperand(1), opcode, Tmp2))
1778       BuildMI(BB, PPC::MULLI, 2, Result).addReg(Tmp1).addSImm(Tmp2);
1779     else {
1780       Tmp2 = SelectExpr(N.getOperand(1));
1781       BuildMI(BB, PPC::MULLW, 2, Result).addReg(Tmp1).addReg(Tmp2);
1782     }
1783     return Result;
1784
1785   case ISD::MULHS:
1786   case ISD::MULHU:
1787     Tmp1 = SelectExpr(N.getOperand(0));
1788     Tmp2 = SelectExpr(N.getOperand(1));
1789     Opc = (ISD::MULHU == opcode) ? PPC::MULHWU : PPC::MULHW;
1790     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1791     return Result;
1792
1793   case ISD::SDIV:
1794   case ISD::UDIV:
1795     switch (getImmediateForOpcode(N.getOperand(1), opcode, Tmp3)) {
1796     default: break;
1797     // If this is an sdiv by a power of two, we can use an srawi/addze pair.
1798     case 3:
1799       Tmp1 = MakeReg(MVT::i32);
1800       Tmp2 = SelectExpr(N.getOperand(0));
1801       BuildMI(BB, PPC::SRAWI, 2, Tmp1).addReg(Tmp2).addImm(Tmp3);
1802       BuildMI(BB, PPC::ADDZE, 1, Result).addReg(Tmp1);
1803       return Result;
1804     // If this is a divide by constant, we can emit code using some magic
1805     // constants to implement it as a multiply instead.
1806     case 4:
1807       ExprMap.erase(N);
1808       if (opcode == ISD::SDIV)
1809         return SelectExpr(BuildSDIVSequence(N));
1810       else
1811         return SelectExpr(BuildUDIVSequence(N));
1812     }
1813     Tmp1 = SelectExpr(N.getOperand(0));
1814     Tmp2 = SelectExpr(N.getOperand(1));
1815     Opc = (ISD::UDIV == opcode) ? PPC::DIVWU : PPC::DIVW;
1816     BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1817     return Result;
1818
1819   case ISD::ADD_PARTS:
1820   case ISD::SUB_PARTS: {
1821     assert(N.getNumOperands() == 4 && N.getValueType() == MVT::i32 &&
1822            "Not an i64 add/sub!");
1823     // Emit all of the operands.
1824     std::vector<unsigned> InVals;
1825     for (unsigned i = 0, e = N.getNumOperands(); i != e; ++i)
1826       InVals.push_back(SelectExpr(N.getOperand(i)));
1827     if (N.getOpcode() == ISD::ADD_PARTS) {
1828       BuildMI(BB, PPC::ADDC, 2, Result).addReg(InVals[0]).addReg(InVals[2]);
1829       BuildMI(BB, PPC::ADDE, 2, Result+1).addReg(InVals[1]).addReg(InVals[3]);
1830     } else {
1831       BuildMI(BB, PPC::SUBFC, 2, Result).addReg(InVals[2]).addReg(InVals[0]);
1832       BuildMI(BB, PPC::SUBFE, 2, Result+1).addReg(InVals[3]).addReg(InVals[1]);
1833     }
1834     return Result+N.ResNo;
1835   }
1836
1837   case ISD::SHL_PARTS:
1838   case ISD::SRA_PARTS:
1839   case ISD::SRL_PARTS: {
1840     assert(N.getNumOperands() == 3 && N.getValueType() == MVT::i32 &&
1841            "Not an i64 shift!");
1842     unsigned ShiftOpLo = SelectExpr(N.getOperand(0));
1843     unsigned ShiftOpHi = SelectExpr(N.getOperand(1));
1844     unsigned SHReg = SelectExpr(N.getOperand(2));
1845     Tmp1 = MakeReg(MVT::i32);
1846     Tmp2 = MakeReg(MVT::i32);
1847     Tmp3 = MakeReg(MVT::i32);
1848     unsigned Tmp4 = MakeReg(MVT::i32);
1849     unsigned Tmp5 = MakeReg(MVT::i32);
1850     unsigned Tmp6 = MakeReg(MVT::i32);
1851     BuildMI(BB, PPC::SUBFIC, 2, Tmp1).addReg(SHReg).addSImm(32);
1852     if (ISD::SHL_PARTS == opcode) {
1853       BuildMI(BB, PPC::SLW, 2, Tmp2).addReg(ShiftOpHi).addReg(SHReg);
1854       BuildMI(BB, PPC::SRW, 2, Tmp3).addReg(ShiftOpLo).addReg(Tmp1);
1855       BuildMI(BB, PPC::OR, 2, Tmp4).addReg(Tmp2).addReg(Tmp3);
1856       BuildMI(BB, PPC::ADDI, 2, Tmp5).addReg(SHReg).addSImm(-32);
1857       BuildMI(BB, PPC::SLW, 2, Tmp6).addReg(ShiftOpLo).addReg(Tmp5);
1858       BuildMI(BB, PPC::OR, 2, Result+1).addReg(Tmp4).addReg(Tmp6);
1859       BuildMI(BB, PPC::SLW, 2, Result).addReg(ShiftOpLo).addReg(SHReg);
1860     } else if (ISD::SRL_PARTS == opcode) {
1861       BuildMI(BB, PPC::SRW, 2, Tmp2).addReg(ShiftOpLo).addReg(SHReg);
1862       BuildMI(BB, PPC::SLW, 2, Tmp3).addReg(ShiftOpHi).addReg(Tmp1);
1863       BuildMI(BB, PPC::OR, 2, Tmp4).addReg(Tmp2).addReg(Tmp3);
1864       BuildMI(BB, PPC::ADDI, 2, Tmp5).addReg(SHReg).addSImm(-32);
1865       BuildMI(BB, PPC::SRW, 2, Tmp6).addReg(ShiftOpHi).addReg(Tmp5);
1866       BuildMI(BB, PPC::OR, 2, Result).addReg(Tmp4).addReg(Tmp6);
1867       BuildMI(BB, PPC::SRW, 2, Result+1).addReg(ShiftOpHi).addReg(SHReg);
1868     } else {
1869       MachineBasicBlock *TmpMBB = new MachineBasicBlock(BB->getBasicBlock());
1870       MachineBasicBlock *PhiMBB = new MachineBasicBlock(BB->getBasicBlock());
1871       MachineBasicBlock *OldMBB = BB;
1872       MachineFunction *F = BB->getParent();
1873       ilist<MachineBasicBlock>::iterator It = BB; ++It;
1874       F->getBasicBlockList().insert(It, TmpMBB);
1875       F->getBasicBlockList().insert(It, PhiMBB);
1876       BB->addSuccessor(TmpMBB);
1877       BB->addSuccessor(PhiMBB);
1878       BuildMI(BB, PPC::SRW, 2, Tmp2).addReg(ShiftOpLo).addReg(SHReg);
1879       BuildMI(BB, PPC::SLW, 2, Tmp3).addReg(ShiftOpHi).addReg(Tmp1);
1880       BuildMI(BB, PPC::OR, 2, Tmp4).addReg(Tmp2).addReg(Tmp3);
1881       BuildMI(BB, PPC::ADDICo, 2, Tmp5).addReg(SHReg).addSImm(-32);
1882       BuildMI(BB, PPC::SRAW, 2, Tmp6).addReg(ShiftOpHi).addReg(Tmp5);
1883       BuildMI(BB, PPC::SRAW, 2, Result+1).addReg(ShiftOpHi).addReg(SHReg);
1884       BuildMI(BB, PPC::BLE, 2).addReg(PPC::CR0).addMBB(PhiMBB);
1885       // Select correct least significant half if the shift amount > 32
1886       BB = TmpMBB;
1887       unsigned Tmp7 = MakeReg(MVT::i32);
1888       BuildMI(BB, PPC::OR, 2, Tmp7).addReg(Tmp6).addReg(Tmp6);
1889       TmpMBB->addSuccessor(PhiMBB);
1890       BB = PhiMBB;
1891       BuildMI(BB, PPC::PHI, 4, Result).addReg(Tmp4).addMBB(OldMBB)
1892         .addReg(Tmp7).addMBB(TmpMBB);
1893     }
1894     return Result+N.ResNo;
1895   }
1896
1897   case ISD::FP_TO_UINT:
1898   case ISD::FP_TO_SINT: {
1899     bool U = (ISD::FP_TO_UINT == opcode);
1900     Tmp1 = SelectExpr(N.getOperand(0));
1901     if (!U) {
1902       Tmp2 = MakeReg(MVT::f64);
1903       BuildMI(BB, PPC::FCTIWZ, 1, Tmp2).addReg(Tmp1);
1904       int FrameIdx = BB->getParent()->getFrameInfo()->CreateStackObject(8, 8);
1905       addFrameReference(BuildMI(BB, PPC::STFD, 3).addReg(Tmp2), FrameIdx);
1906       addFrameReference(BuildMI(BB, PPC::LWZ, 2, Result), FrameIdx, 4);
1907       return Result;
1908     } else {
1909       unsigned Zero = getConstDouble(0.0);
1910       unsigned MaxInt = getConstDouble((1LL << 32) - 1);
1911       unsigned Border = getConstDouble(1LL << 31);
1912       unsigned UseZero = MakeReg(MVT::f64);
1913       unsigned UseMaxInt = MakeReg(MVT::f64);
1914       unsigned UseChoice = MakeReg(MVT::f64);
1915       unsigned TmpReg = MakeReg(MVT::f64);
1916       unsigned TmpReg2 = MakeReg(MVT::f64);
1917       unsigned ConvReg = MakeReg(MVT::f64);
1918       unsigned IntTmp = MakeReg(MVT::i32);
1919       unsigned XorReg = MakeReg(MVT::i32);
1920       MachineFunction *F = BB->getParent();
1921       int FrameIdx = F->getFrameInfo()->CreateStackObject(8, 8);
1922       // Update machine-CFG edges
1923       MachineBasicBlock *XorMBB = new MachineBasicBlock(BB->getBasicBlock());
1924       MachineBasicBlock *PhiMBB = new MachineBasicBlock(BB->getBasicBlock());
1925       MachineBasicBlock *OldMBB = BB;
1926       ilist<MachineBasicBlock>::iterator It = BB; ++It;
1927       F->getBasicBlockList().insert(It, XorMBB);
1928       F->getBasicBlockList().insert(It, PhiMBB);
1929       BB->addSuccessor(XorMBB);
1930       BB->addSuccessor(PhiMBB);
1931       // Convert from floating point to unsigned 32-bit value
1932       // Use 0 if incoming value is < 0.0
1933       BuildMI(BB, PPC::FSEL, 3, UseZero).addReg(Tmp1).addReg(Tmp1).addReg(Zero);
1934       // Use 2**32 - 1 if incoming value is >= 2**32
1935       BuildMI(BB, PPC::FSUB, 2, UseMaxInt).addReg(MaxInt).addReg(Tmp1);
1936       BuildMI(BB, PPC::FSEL, 3, UseChoice).addReg(UseMaxInt).addReg(UseZero)
1937         .addReg(MaxInt);
1938       // Subtract 2**31
1939       BuildMI(BB, PPC::FSUB, 2, TmpReg).addReg(UseChoice).addReg(Border);
1940       // Use difference if >= 2**31
1941       BuildMI(BB, PPC::FCMPU, 2, PPC::CR0).addReg(UseChoice).addReg(Border);
1942       BuildMI(BB, PPC::FSEL, 3, TmpReg2).addReg(TmpReg).addReg(TmpReg)
1943         .addReg(UseChoice);
1944       // Convert to integer
1945       BuildMI(BB, PPC::FCTIWZ, 1, ConvReg).addReg(TmpReg2);
1946       addFrameReference(BuildMI(BB, PPC::STFD, 3).addReg(ConvReg), FrameIdx);
1947       addFrameReference(BuildMI(BB, PPC::LWZ, 2, IntTmp), FrameIdx, 4);
1948       BuildMI(BB, PPC::BLT, 2).addReg(PPC::CR0).addMBB(PhiMBB);
1949       BuildMI(BB, PPC::B, 1).addMBB(XorMBB);
1950
1951       // XorMBB:
1952       //   add 2**31 if input was >= 2**31
1953       BB = XorMBB;
1954       BuildMI(BB, PPC::XORIS, 2, XorReg).addReg(IntTmp).addImm(0x8000);
1955       XorMBB->addSuccessor(PhiMBB);
1956
1957       // PhiMBB:
1958       //   DestReg = phi [ IntTmp, OldMBB ], [ XorReg, XorMBB ]
1959       BB = PhiMBB;
1960       BuildMI(BB, PPC::PHI, 4, Result).addReg(IntTmp).addMBB(OldMBB)
1961         .addReg(XorReg).addMBB(XorMBB);
1962       return Result;
1963     }
1964     assert(0 && "Should never get here");
1965     return 0;
1966   }
1967
1968   case ISD::SETCC:
1969     if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(Node)) {
1970       // We can codegen setcc op, 0 very efficiently compared to a conditional
1971       // branch.  Check for that here.
1972       if (ConstantSDNode *CN =
1973           dyn_cast<ConstantSDNode>(SetCC->getOperand(1).Val)) {
1974         if (CN->getValue() == 0) {
1975           Tmp1 = SelectExpr(SetCC->getOperand(0));
1976           switch (SetCC->getCondition()) {
1977           default: assert(0 && "Unhandled SetCC condition"); abort();
1978           case ISD::SETEQ:
1979           case ISD::SETULE:
1980             Tmp2 = MakeReg(MVT::i32);
1981             BuildMI(BB, PPC::CNTLZW, 1, Tmp2).addReg(Tmp1);
1982             BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp2).addImm(27)
1983               .addImm(5).addImm(31);
1984             break;
1985           case ISD::SETNE:
1986           case ISD::SETUGT:
1987             Tmp2 = MakeReg(MVT::i32);
1988             BuildMI(BB, PPC::ADDIC, 2, Tmp2).addReg(Tmp1).addSImm(-1);
1989             BuildMI(BB, PPC::SUBFE, 2, Result).addReg(Tmp2).addReg(Tmp1);
1990             break;
1991           case ISD::SETULT:
1992             BuildMI(BB, PPC::LI, 1, Result).addSImm(0);
1993             break;
1994           case ISD::SETLT:
1995             BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp1).addImm(1)
1996               .addImm(31).addImm(31);
1997             break;
1998           case ISD::SETLE:
1999             Tmp2 = MakeReg(MVT::i32);
2000             Tmp3 = MakeReg(MVT::i32);
2001             BuildMI(BB, PPC::NEG, 2, Tmp2).addReg(Tmp1);
2002             BuildMI(BB, PPC::ORC, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
2003             BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp3).addImm(1)
2004               .addImm(31).addImm(31);
2005             break;
2006           case ISD::SETGT:
2007             Tmp2 = MakeReg(MVT::i32);
2008             Tmp3 = MakeReg(MVT::i32);
2009             BuildMI(BB, PPC::NEG, 2, Tmp2).addReg(Tmp1);
2010             BuildMI(BB, PPC::ANDC, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
2011             BuildMI(BB, PPC::RLWINM, 4, Result).addReg(Tmp3).addImm(1)
2012               .addImm(31).addImm(31);
2013             break;
2014           case ISD::SETUGE:
2015             BuildMI(BB, PPC::LI, 1, Result).addSImm(1);
2016             break;
2017           case ISD::SETGE:
2018             BuildMI(BB, PPC::RLWINM, 4, Tmp2).addReg(Tmp1).addImm(1)
2019               .addImm(31).addImm(31);
2020             BuildMI(BB, PPC::XORI, 2, Result).addReg(Tmp2).addImm(1);
2021             break;
2022           }
2023           return Result;
2024         }
2025       }
2026
2027       Opc = SelectSetCR0(N);
2028       unsigned TrueValue = MakeReg(MVT::i32);
2029       BuildMI(BB, PPC::LI, 1, TrueValue).addSImm(1);
2030       unsigned FalseValue = MakeReg(MVT::i32);
2031       BuildMI(BB, PPC::LI, 1, FalseValue).addSImm(0);
2032
2033       // Create an iterator with which to insert the MBB for copying the false
2034       // value and the MBB to hold the PHI instruction for this SetCC.
2035       MachineBasicBlock *thisMBB = BB;
2036       const BasicBlock *LLVM_BB = BB->getBasicBlock();
2037       ilist<MachineBasicBlock>::iterator It = BB;
2038       ++It;
2039
2040       //  thisMBB:
2041       //  ...
2042       //   cmpTY cr0, r1, r2
2043       //   %TrueValue = li 1
2044       //   bCC sinkMBB
2045       MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
2046       MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
2047       BuildMI(BB, Opc, 2).addReg(PPC::CR0).addMBB(sinkMBB);
2048       MachineFunction *F = BB->getParent();
2049       F->getBasicBlockList().insert(It, copy0MBB);
2050       F->getBasicBlockList().insert(It, sinkMBB);
2051       // Update machine-CFG edges
2052       BB->addSuccessor(copy0MBB);
2053       BB->addSuccessor(sinkMBB);
2054
2055       //  copy0MBB:
2056       //   %FalseValue = li 0
2057       //   fallthrough
2058       BB = copy0MBB;
2059       // Update machine-CFG edges
2060       BB->addSuccessor(sinkMBB);
2061
2062       //  sinkMBB:
2063       //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
2064       //  ...
2065       BB = sinkMBB;
2066       BuildMI(BB, PPC::PHI, 4, Result).addReg(FalseValue)
2067         .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
2068       return Result;
2069     }
2070     assert(0 && "Is this legal?");
2071     return 0;
2072
2073   case ISD::SELECT: {
2074     // We can codegen select (a < 0) ? b : 0 very efficiently compared to a
2075     // conditional branch.  Check for that here.
2076     if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(N.getOperand(0).Val)) {
2077       if (ConstantSDNode *CN =
2078           dyn_cast<ConstantSDNode>(SetCC->getOperand(1).Val)) {
2079         if (ConstantSDNode *CNF =
2080             dyn_cast<ConstantSDNode>(N.getOperand(2).Val)) {
2081           if (CN->getValue() == 0 && CNF->getValue() == 0 &&
2082               SetCC->getCondition() == ISD::SETLT) {
2083             Tmp1 = SelectExpr(N.getOperand(1)); // TRUE value
2084             Tmp2 = SelectExpr(SetCC->getOperand(0));
2085             Tmp3 = MakeReg(MVT::i32);
2086             BuildMI(BB, PPC::SRAWI, 2, Tmp3).addReg(Tmp2).addImm(31);
2087             BuildMI(BB, PPC::AND, 2, Result).addReg(Tmp1).addReg(Tmp3);
2088             return Result;
2089           }
2090         }
2091       }
2092     }
2093     unsigned TrueValue = SelectExpr(N.getOperand(1)); //Use if TRUE
2094     unsigned FalseValue = SelectExpr(N.getOperand(2)); //Use if FALSE
2095     Opc = SelectSetCR0(N.getOperand(0));
2096
2097     // Create an iterator with which to insert the MBB for copying the false
2098     // value and the MBB to hold the PHI instruction for this SetCC.
2099     MachineBasicBlock *thisMBB = BB;
2100     const BasicBlock *LLVM_BB = BB->getBasicBlock();
2101     ilist<MachineBasicBlock>::iterator It = BB;
2102     ++It;
2103
2104     //  thisMBB:
2105     //  ...
2106     //   TrueVal = ...
2107     //   cmpTY cr0, r1, r2
2108     //   bCC copy1MBB
2109     //   fallthrough --> copy0MBB
2110     MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
2111     MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
2112     BuildMI(BB, Opc, 2).addReg(PPC::CR0).addMBB(sinkMBB);
2113     MachineFunction *F = BB->getParent();
2114     F->getBasicBlockList().insert(It, copy0MBB);
2115     F->getBasicBlockList().insert(It, sinkMBB);
2116     // Update machine-CFG edges
2117     BB->addSuccessor(copy0MBB);
2118     BB->addSuccessor(sinkMBB);
2119
2120     //  copy0MBB:
2121     //   %FalseValue = ...
2122     //   # fallthrough to sinkMBB
2123     BB = copy0MBB;
2124     // Update machine-CFG edges
2125     BB->addSuccessor(sinkMBB);
2126
2127     //  sinkMBB:
2128     //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
2129     //  ...
2130     BB = sinkMBB;
2131     BuildMI(BB, PPC::PHI, 4, Result).addReg(FalseValue)
2132       .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
2133     return Result;
2134   }
2135
2136   case ISD::Constant:
2137     switch (N.getValueType()) {
2138     default: assert(0 && "Cannot use constants of this type!");
2139     case MVT::i1:
2140       BuildMI(BB, PPC::LI, 1, Result)
2141         .addSImm(!cast<ConstantSDNode>(N)->isNullValue());
2142       break;
2143     case MVT::i32:
2144       {
2145         int v = (int)cast<ConstantSDNode>(N)->getSignExtended();
2146         if (v < 32768 && v >= -32768) {
2147           BuildMI(BB, PPC::LI, 1, Result).addSImm(v);
2148         } else {
2149           Tmp1 = MakeReg(MVT::i32);
2150           BuildMI(BB, PPC::LIS, 1, Tmp1).addSImm(v >> 16);
2151           BuildMI(BB, PPC::ORI, 2, Result).addReg(Tmp1).addImm(v & 0xFFFF);
2152         }
2153       }
2154     }
2155     return Result;
2156   }
2157
2158   return 0;
2159 }
2160
2161 void ISel::Select(SDOperand N) {
2162   unsigned Tmp1, Tmp2, Opc;
2163   unsigned opcode = N.getOpcode();
2164
2165   if (!ExprMap.insert(std::make_pair(N, 1)).second)
2166     return;  // Already selected.
2167
2168   SDNode *Node = N.Val;
2169
2170   switch (Node->getOpcode()) {
2171   default:
2172     Node->dump(); std::cerr << "\n";
2173     assert(0 && "Node not handled yet!");
2174   case ISD::EntryToken: return;  // Noop
2175   case ISD::TokenFactor:
2176     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
2177       Select(Node->getOperand(i));
2178     return;
2179   case ISD::ADJCALLSTACKDOWN:
2180   case ISD::ADJCALLSTACKUP:
2181     Select(N.getOperand(0));
2182     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
2183     Opc = N.getOpcode() == ISD::ADJCALLSTACKDOWN ? PPC::ADJCALLSTACKDOWN :
2184       PPC::ADJCALLSTACKUP;
2185     BuildMI(BB, Opc, 1).addImm(Tmp1);
2186     return;
2187   case ISD::BR: {
2188     MachineBasicBlock *Dest =
2189       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
2190     Select(N.getOperand(0));
2191     BuildMI(BB, PPC::B, 1).addMBB(Dest);
2192     return;
2193   }
2194   case ISD::BRCOND:
2195   case ISD::BRCONDTWOWAY:
2196     SelectBranchCC(N);
2197     return;
2198   case ISD::CopyToReg:
2199     Select(N.getOperand(0));
2200     Tmp1 = SelectExpr(N.getOperand(1));
2201     Tmp2 = cast<RegSDNode>(N)->getReg();
2202
2203     if (Tmp1 != Tmp2) {
2204       if (N.getOperand(1).getValueType() == MVT::f64 ||
2205           N.getOperand(1).getValueType() == MVT::f32)
2206         BuildMI(BB, PPC::FMR, 1, Tmp2).addReg(Tmp1);
2207       else
2208         BuildMI(BB, PPC::OR, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
2209     }
2210     return;
2211   case ISD::ImplicitDef:
2212     Select(N.getOperand(0));
2213     BuildMI(BB, PPC::IMPLICIT_DEF, 0, cast<RegSDNode>(N)->getReg());
2214     return;
2215   case ISD::RET:
2216     switch (N.getNumOperands()) {
2217     default:
2218       assert(0 && "Unknown return instruction!");
2219     case 3:
2220       assert(N.getOperand(1).getValueType() == MVT::i32 &&
2221              N.getOperand(2).getValueType() == MVT::i32 &&
2222                    "Unknown two-register value!");
2223       Select(N.getOperand(0));
2224       Tmp1 = SelectExpr(N.getOperand(1));
2225       Tmp2 = SelectExpr(N.getOperand(2));
2226       BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp2).addReg(Tmp2);
2227       BuildMI(BB, PPC::OR, 2, PPC::R4).addReg(Tmp1).addReg(Tmp1);
2228       break;
2229     case 2:
2230       Select(N.getOperand(0));
2231       Tmp1 = SelectExpr(N.getOperand(1));
2232       switch (N.getOperand(1).getValueType()) {
2233         default:
2234           assert(0 && "Unknown return type!");
2235         case MVT::f64:
2236         case MVT::f32:
2237           BuildMI(BB, PPC::FMR, 1, PPC::F1).addReg(Tmp1);
2238           break;
2239         case MVT::i32:
2240           BuildMI(BB, PPC::OR, 2, PPC::R3).addReg(Tmp1).addReg(Tmp1);
2241           break;
2242       }
2243     case 1:
2244       Select(N.getOperand(0));
2245       break;
2246     }
2247     BuildMI(BB, PPC::BLR, 0); // Just emit a 'ret' instruction
2248     return;
2249   case ISD::TRUNCSTORE:
2250   case ISD::STORE:
2251     {
2252       SDOperand Chain   = N.getOperand(0);
2253       SDOperand Value   = N.getOperand(1);
2254       SDOperand Address = N.getOperand(2);
2255       Select(Chain);
2256
2257       Tmp1 = SelectExpr(Value); //value
2258
2259       if (opcode == ISD::STORE) {
2260         switch(Value.getValueType()) {
2261         default: assert(0 && "unknown Type in store");
2262         case MVT::i32: Opc = PPC::STW; break;
2263         case MVT::f64: Opc = PPC::STFD; break;
2264         case MVT::f32: Opc = PPC::STFS; break;
2265         }
2266       } else { //ISD::TRUNCSTORE
2267         switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
2268         default: assert(0 && "unknown Type in store");
2269         case MVT::i1:
2270         case MVT::i8: Opc  = PPC::STB; break;
2271         case MVT::i16: Opc = PPC::STH; break;
2272         }
2273       }
2274
2275       if(Address.getOpcode() == ISD::FrameIndex)
2276       {
2277         Tmp2 = cast<FrameIndexSDNode>(Address)->getIndex();
2278         addFrameReference(BuildMI(BB, Opc, 3).addReg(Tmp1), (int)Tmp2);
2279       }
2280       else
2281       {
2282         int offset;
2283         bool idx = SelectAddr(Address, Tmp2, offset);
2284         if (idx) {
2285           Opc = IndexedOpForOp(Opc);
2286           BuildMI(BB, Opc, 3).addReg(Tmp1).addReg(Tmp2).addReg(offset);
2287         } else {
2288           BuildMI(BB, Opc, 3).addReg(Tmp1).addImm(offset).addReg(Tmp2);
2289         }
2290       }
2291       return;
2292     }
2293   case ISD::EXTLOAD:
2294   case ISD::SEXTLOAD:
2295   case ISD::ZEXTLOAD:
2296   case ISD::LOAD:
2297   case ISD::CopyFromReg:
2298   case ISD::CALL:
2299   case ISD::DYNAMIC_STACKALLOC:
2300     ExprMap.erase(N);
2301     SelectExpr(N);
2302     return;
2303   }
2304   assert(0 && "Should not be reached!");
2305 }
2306
2307
2308 /// createPPC32PatternInstructionSelector - This pass converts an LLVM function
2309 /// into a machine code representation using pattern matching and a machine
2310 /// description file.
2311 ///
2312 FunctionPass *llvm::createPPC32ISelPattern(TargetMachine &TM) {
2313   return new ISel(TM);
2314 }
2315