Remove 64 bit simple ISel, it never worked correctly

Add initial (buggy) implementation of 64 bit pattern ISel


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21096 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 1767 insertions, 0 deletions

diff --git a/lib/Target/PowerPC/PPC64ISelPattern.cpp b/lib/Target/PowerPC/PPC64ISelPattern.cpp
new file mode 100644
index 0000000000..210acf580b
--- /dev/null
+++ b/lib/Target/PowerPC/PPC64ISelPattern.cpp
@@ -0,0 +1,1767 @@
+//===-- PPC32ISelPattern.cpp - A pattern matching inst selector for PPC32 -===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file was developed by Nate Begeman and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+// 
+//===----------------------------------------------------------------------===//
+//
+// This file defines a pattern matching instruction selector for 32 bit PowerPC.
+//
+//===----------------------------------------------------------------------===//
+
+#include "PowerPC.h"
+#include "PowerPCInstrBuilder.h"
+#include "PowerPCInstrInfo.h"
+#include "PPC64RegisterInfo.h"
+#include "llvm/Constants.h"                   // FIXME: REMOVE
+#include "llvm/Function.h"
+#include "llvm/CodeGen/MachineConstantPool.h" // FIXME: REMOVE
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
+#include "llvm/CodeGen/SelectionDAG.h"
+#include "llvm/CodeGen/SelectionDAGISel.h"
+#include "llvm/CodeGen/SSARegMap.h"
+#include "llvm/Target/TargetData.h"
+#include "llvm/Target/TargetLowering.h"
+#include "llvm/Target/TargetOptions.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/MathExtras.h"
+#include "llvm/ADT/Statistic.h"
+#include <set>
+#include <algorithm>
+using namespace llvm;
+
+//===----------------------------------------------------------------------===//
+//  PPC32TargetLowering - PPC32 Implementation of the TargetLowering interface
+namespace {
+  class PPC64TargetLowering : public TargetLowering {
+    int VarArgsFrameIndex;            // FrameIndex for start of varargs area.
+    int ReturnAddrIndex;              // FrameIndex for return slot.
+  public:
+    PPC64TargetLowering(TargetMachine &TM) : TargetLowering(TM) {
+      // Set up the register classes.
+      addRegisterClass(MVT::i64, PPC64::GPRCRegisterClass);
+      addRegisterClass(MVT::f32, PPC64::FPRCRegisterClass);
+      addRegisterClass(MVT::f64, PPC64::FPRCRegisterClass);
+      
+      // PowerPC has no intrinsics for these particular operations
+      setOperationAction(ISD::MEMMOVE, MVT::Other, Expand);
+      setOperationAction(ISD::MEMSET, MVT::Other, Expand);
+      setOperationAction(ISD::MEMCPY, MVT::Other, Expand);
+
+      // PPC 64 has i16 and i32 but no i8 (or i1) SEXTLOAD
+      setOperationAction(ISD::SEXTLOAD, MVT::i1, Expand);
+      setOperationAction(ISD::SEXTLOAD, MVT::i8, Expand);
+
+      setShiftAmountFlavor(Extend);   // shl X, 32 == 0
+      addLegalFPImmediate(+0.0); // Necessary for FSEL
+      addLegalFPImmediate(-0.0); // 
+
+      computeRegisterProperties();
+    }
+
+    /// LowerArguments - This hook must be implemented to indicate how we should
+    /// lower the arguments for the specified function, into the specified DAG.
+    virtual std::vector<SDOperand>
+    LowerArguments(Function &F, SelectionDAG &DAG);
+    
+    /// LowerCallTo - This hook lowers an abstract call to a function into an
+    /// actual call.
+    virtual std::pair<SDOperand, SDOperand>
+    LowerCallTo(SDOperand Chain, const Type *RetTy, bool isVarArg,
+                SDOperand Callee, ArgListTy &Args, SelectionDAG &DAG);
+    
+    virtual std::pair<SDOperand, SDOperand>
+    LowerVAStart(SDOperand Chain, SelectionDAG &DAG);
+    
+    virtual std::pair<SDOperand,SDOperand>
+    LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
+                   const Type *ArgTy, SelectionDAG &DAG);
+
+    virtual std::pair<SDOperand, SDOperand>
+    LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain, unsigned Depth,
+                            SelectionDAG &DAG);
+  };
+}
+
+
+std::vector<SDOperand>
+PPC64TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
+  //
+  // add beautiful description of PPC stack frame format, or at least some docs
+  //
+  MachineFunction &MF = DAG.getMachineFunction();
+  MachineFrameInfo *MFI = MF.getFrameInfo();
+  MachineBasicBlock& BB = MF.front();
+  std::vector<SDOperand> ArgValues;
+  
+  // Due to the rather complicated nature of the PowerPC ABI, rather than a 
+  // fixed size array of physical args, for the sake of simplicity let the STL
+  // handle tracking them for us.
+  std::vector<unsigned> argVR, argPR, argOp;
+  unsigned ArgOffset = 24;
+  unsigned GPR_remaining = 8;
+  unsigned FPR_remaining = 13;
+  unsigned GPR_idx = 0, FPR_idx = 0;
+  static const unsigned GPR[] = { 
+    PPC::R3, PPC::R4, PPC::R5, PPC::R6,
+    PPC::R7, PPC::R8, PPC::R9, PPC::R10,
+  };
+  static const unsigned FPR[] = {
+    PPC::F1, PPC::F2, PPC::F3, PPC::F4, PPC::F5, PPC::F6, PPC::F7,
+    PPC::F8, PPC::F9, PPC::F10, PPC::F11, PPC::F12, PPC::F13
+  };
+
+  // Add DAG nodes to load the arguments...  On entry to a function on PPC,
+  // the arguments start at offset 24, although they are likely to be passed
+  // in registers.
+  for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) {
+    SDOperand newroot, argt;
+    unsigned ObjSize;
+    bool needsLoad = false;
+    MVT::ValueType ObjectVT = getValueType(I->getType());
+    
+    switch (ObjectVT) {
+    default: assert(0 && "Unhandled argument type!");
+    case MVT::i1:
+    case MVT::i8:
+    case MVT::i16:
+    case MVT::i32: 
+      ObjSize = 4;
+      if (GPR_remaining > 0) {
+        BuildMI(&BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx]);
+        argt = newroot = DAG.getCopyFromReg(GPR[GPR_idx], MVT::i32,
+                                            DAG.getRoot());
+        if (ObjectVT != MVT::i32)
+          argt = DAG.getNode(ISD::TRUNCATE, ObjectVT, newroot);
+      } else {
+        needsLoad = true;
+      }
+      break;
+      case MVT::i64: ObjSize = 8;
+      // FIXME: can split 64b load between reg/mem if it is last arg in regs
+      if (GPR_remaining > 1) {
+        BuildMI(&BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx]);
+        BuildMI(&BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx+1]);
+        // Copy the extracted halves into the virtual registers
+        SDOperand argHi = DAG.getCopyFromReg(GPR[GPR_idx], MVT::i32, 
+                                             DAG.getRoot());
+        SDOperand argLo = DAG.getCopyFromReg(GPR[GPR_idx+1], MVT::i32, argHi);
+        // Build the outgoing arg thingy
+        argt = DAG.getNode(ISD::BUILD_PAIR, MVT::i64, argLo, argHi);
+        newroot = argLo;
+      } else {
+        needsLoad = true; 
+      }
+      break;
+      case MVT::f32: ObjSize = 4;
+      case MVT::f64: ObjSize = 8;
+      if (FPR_remaining > 0) {
+        BuildMI(&BB, PPC::IMPLICIT_DEF, 0, FPR[FPR_idx]);
+        argt = newroot = DAG.getCopyFromReg(FPR[FPR_idx], ObjectVT, 
+                                            DAG.getRoot());
+        --FPR_remaining;
+        ++FPR_idx;
+      } else {
+        needsLoad = true;
+      }
+      break;
+    }
+    
+    // We need to load the argument to a virtual register if we determined above
+    // that we ran out of physical registers of the appropriate type 
+    if (needsLoad) {
+      unsigned SubregOffset = 0;
+      if (ObjectVT == MVT::i8 || ObjectVT == MVT::i1) SubregOffset = 3;
+      if (ObjectVT == MVT::i16) SubregOffset = 2;
+      int FI = MFI->CreateFixedObject(ObjSize, ArgOffset);
+      SDOperand FIN = DAG.getFrameIndex(FI, MVT::i32);
+      FIN = DAG.getNode(ISD::ADD, MVT::i32, FIN, 
+                        DAG.getConstant(SubregOffset, MVT::i32));
+      argt = newroot = DAG.getLoad(ObjectVT, DAG.getEntryNode(), FIN);
+    }
+    
+    // Every 4 bytes of argument space consumes one of the GPRs available for
+    // argument passing.
+    if (GPR_remaining > 0) {
+      unsigned delta = (GPR_remaining > 1 && ObjSize == 8) ? 2 : 1;
+      GPR_remaining -= delta;
+      GPR_idx += delta;
+    }
+    ArgOffset += ObjSize;
+    
+    DAG.setRoot(newroot.getValue(1));
+    ArgValues.push_back(argt);
+  }
+
+  // If the function takes variable number of arguments, make a frame index for
+  // the start of the first vararg value... for expansion of llvm.va_start.
+  if (F.isVarArg()) {
+    VarArgsFrameIndex = MFI->CreateFixedObject(4, ArgOffset);
+    SDOperand FIN = DAG.getFrameIndex(VarArgsFrameIndex, MVT::i32);
+    // If this function is vararg, store any remaining integer argument regs
+    // to their spots on the stack so that they may be loaded by deferencing the
+    // result of va_next.
+    std::vector<SDOperand> MemOps;
+    for (; GPR_remaining > 0; --GPR_remaining, ++GPR_idx) {
+      BuildMI(&BB, PPC::IMPLICIT_DEF, 0, GPR[GPR_idx]);
+      SDOperand Val = DAG.getCopyFromReg(GPR[GPR_idx], MVT::i32, DAG.getRoot());
+      SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, Val.getValue(1), 
+                                    Val, FIN);
+      MemOps.push_back(Store);
+      // Increment the address by four for the next argument to store
+      SDOperand PtrOff = DAG.getConstant(4, getPointerTy());
+      FIN = DAG.getNode(ISD::ADD, MVT::i32, FIN, PtrOff);
+    }
+    DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, MemOps));
+  }
+
+  return ArgValues;
+}
+
+std::pair<SDOperand, SDOperand>
+PPC64TargetLowering::LowerCallTo(SDOperand Chain,
+				 const Type *RetTy, bool isVarArg,
+         SDOperand Callee, ArgListTy &Args, SelectionDAG &DAG) {
+  // args_to_use will accumulate outgoing args for the ISD::CALL case in
+  // SelectExpr to use to put the arguments in the appropriate registers.
+  std::vector<SDOperand> args_to_use;
+
+  // Count how many bytes are to be pushed on the stack, including the linkage
+  // area, and parameter passing area.
+  unsigned NumBytes = 24;
+
+  if (Args.empty()) {
+    Chain = DAG.getNode(ISD::ADJCALLSTACKDOWN, MVT::Other, Chain,
+                        DAG.getConstant(NumBytes, getPointerTy()));
+  } else {
+    for (unsigned i = 0, e = Args.size(); i != e; ++i)
+      switch (getValueType(Args[i].second)) {
+      default: assert(0 && "Unknown value type!");
+      case MVT::i1:
+      case MVT::i8:
+      case MVT::i16:
+      case MVT::i32:
+      case MVT::f32:
+        NumBytes += 4;
+        break;
+      case MVT::i64:
+      case MVT::f64:
+        NumBytes += 8;
+        break;
+      }
+    
+    // Just to be safe, we'll always reserve the full 24 bytes of linkage area 
+    // plus 32 bytes of argument space in case any called code gets funky on us.
+    if (NumBytes < 56) NumBytes = 56;
+
+    // Adjust the stack pointer for the new arguments...
+    // These operations are automatically eliminated by the prolog/epilog pass
+    Chain = DAG.getNode(ISD::ADJCALLSTACKDOWN, MVT::Other, Chain,
+                        DAG.getConstant(NumBytes, getPointerTy()));
+
+    // Set up a copy of the stack pointer for use loading and storing any
+    // arguments that may not fit in the registers available for argument
+    // passing.
+    SDOperand StackPtr = DAG.getCopyFromReg(PPC::R1, MVT::i32,
+                                            DAG.getEntryNode());
+    
+    // Figure out which arguments are going to go in registers, and which in
+    // memory.  Also, if this is a vararg function, floating point operations
+    // must be stored to our stack, and loaded into integer regs as well, if
+    // any integer regs are available for argument passing.
+    unsigned ArgOffset = 24;
+    unsigned GPR_remaining = 8;
+    unsigned FPR_remaining = 13;
+    
+    std::vector<SDOperand> MemOps;
+    for (unsigned i = 0, e = Args.size(); i != e; ++i) {
+      // PtrOff will be used to store the current argument to the stack if a
+      // register cannot be found for it.
+      SDOperand PtrOff = DAG.getConstant(ArgOffset, getPointerTy());
+      PtrOff = DAG.getNode(ISD::ADD, MVT::i32, StackPtr, PtrOff);
+      MVT::ValueType ArgVT = getValueType(Args[i].second);
+      
+      switch (ArgVT) {
+      default: assert(0 && "Unexpected ValueType for argument!");
+      case MVT::i1:
+      case MVT::i8:
+      case MVT::i16:
+        // Promote the integer to 32 bits.  If the input type is signed use a
+        // sign extend, otherwise use a zero extend.
+        if (Args[i].second->isSigned())
+          Args[i].first =DAG.getNode(ISD::SIGN_EXTEND, MVT::i32, Args[i].first);
+        else
+          Args[i].first =DAG.getNode(ISD::ZERO_EXTEND, MVT::i32, Args[i].first);
+        // FALL THROUGH
+      case MVT::i32:
+        if (GPR_remaining > 0) {
+          args_to_use.push_back(Args[i].first);
+          --GPR_remaining;
+        } else {
+          MemOps.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
+                                          Args[i].first, PtrOff));
+        }
+        ArgOffset += 4;
+        break;
+      case MVT::i64:
+        // If we have one free GPR left, we can place the upper half of the i64
+        // in it, and store the other half to the stack.  If we have two or more
+        // free GPRs, then we can pass both halves of the i64 in registers.
+        if (GPR_remaining > 0) {
+          SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32, 
+            Args[i].first, DAG.getConstant(1, MVT::i32));
+          SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, MVT::i32, 
+            Args[i].first, DAG.getConstant(0, MVT::i32));
+          args_to_use.push_back(Hi);
+          --GPR_remaining;
+          if (GPR_remaining > 0) {
+            args_to_use.push_back(Lo);
+            --GPR_remaining;
+          } else {
+            SDOperand ConstFour = DAG.getConstant(4, getPointerTy());
+            PtrOff = DAG.getNode(ISD::ADD, MVT::i32, PtrOff, ConstFour);
+            MemOps.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
+                                            Lo, PtrOff));
+          }
+        } else {
+          MemOps.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
+                                          Args[i].first, PtrOff));
+        }
+        ArgOffset += 8;
+        break;
+      case MVT::f32:
+      case MVT::f64:
+        if (FPR_remaining > 0) {
+          args_to_use.push_back(Args[i].first);
+          --FPR_remaining;
+          if (isVarArg) {
+            SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, Chain,
+                                          Args[i].first, PtrOff);
+            MemOps.push_back(Store);
+            // Float varargs are always shadowed in available integer registers
+            if (GPR_remaining > 0) {
+              SDOperand Load = DAG.getLoad(MVT::i32, Store, PtrOff);
+              MemOps.push_back(Load);
+              args_to_use.push_back(Load);
+              --GPR_remaining;
+            }
+            if (GPR_remaining > 0 && MVT::f64 == ArgVT) {
+              SDOperand ConstFour = DAG.getConstant(4, getPointerTy());
+              PtrOff = DAG.getNode(ISD::ADD, MVT::i32, PtrOff, ConstFour);
+              SDOperand Load = DAG.getLoad(MVT::i32, Store, PtrOff);
+              MemOps.push_back(Load);
+              args_to_use.push_back(Load);
+              --GPR_remaining;
+            }
+          } else {
+            // If we have any FPRs remaining, we may also have GPRs remaining.
+            // Args passed in FPRs consume either 1 (f32) or 2 (f64) available
+            // GPRs.
+            if (GPR_remaining > 0) {
+              args_to_use.push_back(DAG.getNode(ISD::UNDEF, MVT::i32));
+              --GPR_remaining;
+            }
+            if (GPR_remaining > 0 && MVT::f64 == ArgVT) {
+              args_to_use.push_back(DAG.getNode(ISD::UNDEF, MVT::i32));
+              --GPR_remaining;
+            }
+          }
+        } else {
+          MemOps.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain,
+                                          Args[i].first, PtrOff));
+        }
+        ArgOffset += (ArgVT == MVT::f32) ? 4 : 8;
+        break;
+      }
+    }
+    if (!MemOps.empty())
+      Chain = DAG.getNode(ISD::TokenFactor, MVT::Other, MemOps);
+  }
+  
+  std::vector<MVT::ValueType> RetVals;
+  MVT::ValueType RetTyVT = getValueType(RetTy);
+  if (RetTyVT != MVT::isVoid)
+    RetVals.push_back(RetTyVT);
+  RetVals.push_back(MVT::Other);
+
+  SDOperand TheCall = SDOperand(DAG.getCall(RetVals, 
+                                            Chain, Callee, args_to_use), 0);
+  Chain = TheCall.getValue(RetTyVT != MVT::isVoid);
+  Chain = DAG.getNode(ISD::ADJCALLSTACKUP, MVT::Other, Chain,
+                      DAG.getConstant(NumBytes, getPointerTy()));
+  return std::make_pair(TheCall, Chain);
+}
+
+std::pair<SDOperand, SDOperand>
+PPC64TargetLowering::LowerVAStart(SDOperand Chain, SelectionDAG &DAG) {
+  //vastart just returns the address of the VarArgsFrameIndex slot.
+  return std::make_pair(DAG.getFrameIndex(VarArgsFrameIndex, MVT::i32), Chain);
+}
+
+std::pair<SDOperand,SDOperand> PPC64TargetLowering::
+LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
+               const Type *ArgTy, SelectionDAG &DAG) {
+  MVT::ValueType ArgVT = getValueType(ArgTy);
+  SDOperand Result;
+  if (!isVANext) {
+    Result = DAG.getLoad(ArgVT, DAG.getEntryNode(), VAList);
+  } else {
+    unsigned Amt;
+    if (ArgVT == MVT::i32 || ArgVT == MVT::f32)
+      Amt = 4;
+    else {
+      assert((ArgVT == MVT::i64 || ArgVT == MVT::f64) &&
+             "Other types should have been promoted for varargs!");
+      Amt = 8;
+    }
+    Result = DAG.getNode(ISD::ADD, VAList.getValueType(), VAList,
+                         DAG.getConstant(Amt, VAList.getValueType()));
+  }
+  return std::make_pair(Result, Chain);
+}
+               
+
+std::pair<SDOperand, SDOperand> PPC64TargetLowering::
+LowerFrameReturnAddress(bool isFrameAddress, SDOperand Chain, unsigned Depth,
+                        SelectionDAG &DAG) {
+  assert(0 && "LowerFrameReturnAddress unimplemented");
+  abort();
+}
+
+namespace {
+Statistic<>NotLogic("ppc-codegen", "Number of inverted logical ops");
+Statistic<>FusedFP("ppc-codegen", "Number of fused fp operations");
+//===--------------------------------------------------------------------===//
+/// ISel - PPC32 specific code to select PPC32 machine instructions for
+/// SelectionDAG operations.
+//===--------------------------------------------------------------------===//
+class ISel : public SelectionDAGISel {
+  
+  /// Comment Here.
+  PPC64TargetLowering PPC64Lowering;
+  
+  /// ExprMap - As shared expressions are codegen'd, we keep track of which
+  /// vreg the value is produced in, so we only emit one copy of each compiled
+  /// tree.
+  std::map<SDOperand, unsigned> ExprMap;
+
+  unsigned GlobalBaseReg;
+  bool GlobalBaseInitialized;
+  
+public:
+  ISel(TargetMachine &TM) : SelectionDAGISel(PPC64Lowering), PPC64Lowering(TM) 
+  {}
+  
+  /// runOnFunction - Override this function in order to reset our per-function
+  /// variables.
+  virtual bool runOnFunction(Function &Fn) {
+    // Make sure we re-emit a set of the global base reg if necessary
+    GlobalBaseInitialized = false;
+    return SelectionDAGISel::runOnFunction(Fn);
+  } 
+  
+  /// InstructionSelectBasicBlock - This callback is invoked by
+  /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
+  virtual void InstructionSelectBasicBlock(SelectionDAG &DAG) {
+    DEBUG(BB->dump());
+    // Codegen the basic block.
+    Select(DAG.getRoot());
+    
+    // Clear state used for selection.
+    ExprMap.clear();
+  }
+  
+  unsigned getGlobalBaseReg();
+  unsigned getConstDouble(double floatVal, unsigned Result);
+  unsigned SelectSetCR0(SDOperand CC);
+  unsigned SelectExpr(SDOperand N);
+  unsigned SelectExprFP(SDOperand N, unsigned Result);
+  void Select(SDOperand N);
+  
+  bool SelectAddr(SDOperand N, unsigned& Reg, int& offset);
+  void SelectBranchCC(SDOperand N);
+};
+
+/// ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
+/// returns zero when the input is not exactly a power of two.
+static unsigned ExactLog2(unsigned Val) {
+  if (Val == 0 || (Val & (Val-1))) return 0;
+  unsigned Count = 0;
+  while (Val != 1) {
+    Val >>= 1;
+    ++Count;
+  }
+  return Count;
+}
+
+/// getImmediateForOpcode - This method returns a value indicating whether
+/// the ConstantSDNode N can be used as an immediate to Opcode.  The return
+/// values are either 0, 1 or 2.  0 indicates that either N is not a
+/// ConstantSDNode, or is not suitable for use by that opcode.  A return value 
+/// of 1 indicates that the constant may be used in normal immediate form.  A
+/// return value of 2 indicates that the constant may be used in shifted
+/// immediate form.  A return value of 3 indicates that log base 2 of the
+/// constant may be used.
+///
+static unsigned getImmediateForOpcode(SDOperand N, unsigned Opcode,
+                                      unsigned& Imm, bool U = false) {
+  if (N.getOpcode() != ISD::Constant) return 0;
+
+  int v = (int)cast<ConstantSDNode>(N)->getSignExtended();
+  
+  switch(Opcode) {
+  default: return 0;
+  case ISD::ADD:
+    if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
+    if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
+    break;
+  case ISD::AND:
+  case ISD::XOR:
+  case ISD::OR:
+    if (v >= 0 && v <= 65535) { Imm = v & 0xFFFF; return 1; }
+    if ((v & 0x0000FFFF) == 0) { Imm = v >> 16; return 2; }
+    break;
+  case ISD::MUL:
+  case ISD::SUB:
+    if (v <= 32767 && v >= -32768) { Imm = v & 0xFFFF; return 1; }
+    break;
+  case ISD::SETCC:
+    if (U && (v >= 0 && v <= 65535)) { Imm = v & 0xFFFF; return 1; }
+    if (!U && (v <= 32767 && v >= -32768)) { Imm = v & 0xFFFF; return 1; }
+    break;
+  case ISD::SDIV:
+    if ((Imm = ExactLog2(v))) { return 3; }
+    break;
+  }
+  return 0;
+}
+
+/// getBCCForSetCC - Returns the PowerPC condition branch mnemonic corresponding
+/// to Condition.  If the Condition is unordered or unsigned, the bool argument
+/// U is set to true, otherwise it is set to false.
+static unsigned getBCCForSetCC(unsigned Condition, bool& U) {
+  U = false;
+  switch (Condition) {
+  default: assert(0 && "Unknown condition!"); abort();
+  case ISD::SETEQ:  return PPC::BEQ;
+  case ISD::SETNE:  return PPC::BNE;
+  case ISD::SETULT: U = true;
+  case ISD::SETLT:  return PPC::BLT;
+  case ISD::SETULE: U = true;
+  case ISD::SETLE:  return PPC::BLE;
+  case ISD::SETUGT: U = true;
+  case ISD::SETGT:  return PPC::BGT;
+  case ISD::SETUGE: U = true;
+  case ISD::SETGE:  return PPC::BGE;
+  }
+  return 0;
+}
+
+/// IndexedOpForOp - Return the indexed variant for each of the PowerPC load
+/// and store immediate instructions.
+static unsigned IndexedOpForOp(unsigned Opcode) {
+  switch(Opcode) {
+  default: assert(0 && "Unknown opcode!"); abort();
+  case PPC::LBZ: return PPC::LBZX;  case PPC::STB: return PPC::STBX;
+  case PPC::LHZ: return PPC::LHZX;  case PPC::STH: return PPC::STHX;
+  case PPC::LHA: return PPC::LHAX;  case PPC::STW: return PPC::STWX;
+  case PPC::LWZ: return PPC::LWZX;  case PPC::STD: return PPC::STDX;
+  case PPC::LD:  return PPC::LDX;   case PPC::STFS: return PPC::STFSX;
+  case PPC::LFS: return PPC::LFSX;  case PPC::STFD: return PPC::STFDX;
+  case PPC::LFD: return PPC::LFDX;
+  }
+  return 0;
+}
+}
+
+/// getGlobalBaseReg - Output the instructions required to put the
+/// base address to use for accessing globals into a register.
+///
+unsigned ISel::getGlobalBaseReg() {
+  if (!GlobalBaseInitialized) {
+    // Insert the set of GlobalBaseReg into the first MBB of the function
+    MachineBasicBlock &FirstMBB = BB->getParent()->front();
+    MachineBasicBlock::iterator MBBI = FirstMBB.begin();
+    GlobalBaseReg = MakeReg(MVT::i64);
+    BuildMI(FirstMBB, MBBI, PPC::MovePCtoLR, 0, PPC::LR);
+    BuildMI(FirstMBB, MBBI, PPC::MFLR, 1, GlobalBaseReg).addReg(PPC::LR);
+    GlobalBaseInitialized = true;
+  }
+  return GlobalBaseReg;
+}
+
+/// getConstDouble - Loads a floating point value into a register, via the 
+/// Constant Pool.  Optionally takes a register in which to load the value.
+unsigned ISel::getConstDouble(double doubleVal, unsigned Result=0) {
+  unsigned Tmp1 = MakeReg(MVT::i32);
+  if (0 == Result) Result = MakeReg(MVT::f64);
+  MachineConstantPool *CP = BB->getParent()->getConstantPool();
+  ConstantFP *CFP = ConstantFP::get(Type::DoubleTy, doubleVal);
+  unsigned CPI = CP->getConstantPoolIndex(CFP);
+  BuildMI(BB, PPC::LOADHiAddr, 2, Tmp1).addReg(getGlobalBaseReg())
+    .addConstantPoolIndex(CPI);
+  BuildMI(BB, PPC::LFD, 2, Result).addConstantPoolIndex(CPI).addReg(Tmp1);
+  return Result;
+}
+
+unsigned ISel::SelectSetCR0(SDOperand CC) {
+  unsigned Opc, Tmp1, Tmp2;
+  static const unsigned CompareOpcodes[] = 
+    { PPC::FCMPU, PPC::FCMPU, PPC::CMPW, PPC::CMPLW };
+  
+  // If the first operand to the select is a SETCC node, then we can fold it
+  // into the branch that selects which value to return.
+  SetCCSDNode* SetCC = dyn_cast<SetCCSDNode>(CC.Val);
+  if (SetCC && CC.getOpcode() == ISD::SETCC) {
+    bool U;
+    Opc = getBCCForSetCC(SetCC->getCondition(), U);
+    Tmp1 = SelectExpr(SetCC->getOperand(0));
+
+    // Pass the optional argument U to getImmediateForOpcode for SETCC,
+    // so that it knows whether the SETCC immediate range is signed or not.
+    if (1 == getImmediateForOpcode(SetCC->getOperand(1), ISD::SETCC, 
+                                   Tmp2, U)) {
+      if (U)
+        BuildMI(BB, PPC::CMPLWI, 2, PPC::CR0).addReg(Tmp1).addImm(Tmp2);
+      else
+        BuildMI(BB, PPC::CMPWI, 2, PPC::CR0).addReg(Tmp1).addSImm(Tmp2);
+    } else {
+      bool IsInteger = MVT::isInteger(SetCC->getOperand(0).getValueType());
+      unsigned CompareOpc = CompareOpcodes[2 * IsInteger + U];
+      Tmp2 = SelectExpr(SetCC->getOperand(1));
+      BuildMI(BB, CompareOpc, 2, PPC::CR0).addReg(Tmp1).addReg(Tmp2);
+    }
+  } else {
+    Tmp1 = SelectExpr(CC);
+    BuildMI(BB, PPC::CMPLWI, 2, PPC::CR0).addReg(Tmp1).addImm(0);
+    Opc = PPC::BNE;
+  }
+  return Opc;
+}
+
+/// Check to see if the load is a constant offset from a base register
+bool ISel::SelectAddr(SDOperand N, unsigned& Reg, int& offset)
+{
+  unsigned imm = 0, opcode = N.getOpcode();
+  if (N.getOpcode() == ISD::ADD) {
+    Reg = SelectExpr(N.getOperand(0));
+    if (1 == getImmediateForOpcode(N.getOperand(1), opcode, imm)) {
+      offset = imm;
+      return false;
+    } 
+    offset = SelectExpr(N.getOperand(1));
+    return true;
+  }
+  Reg = SelectExpr(N);
+  offset = 0;
+  return false;
+}
+
+void ISel::SelectBranchCC(SDOperand N)
+{
+  assert(N.getOpcode() == ISD::BRCOND && "Not a BranchCC???");
+  MachineBasicBlock *Dest = 
+    cast<BasicBlockSDNode>(N.getOperand(2))->getBasicBlock();
+
+  // Get the MBB we will fall through to so that we can hand it off to the
+  // branch selection pass as an argument to the PPC::COND_BRANCH pseudo op.
+  //ilist<MachineBasicBlock>::iterator It = BB;
+  //MachineBasicBlock *Fallthrough = ++It;
+  
+  Select(N.getOperand(0));  //chain
+  unsigned Opc = SelectSetCR0(N.getOperand(1));
+  // FIXME: Use this once we have something approximating two-way branches
+  // We cannot currently use this in case the ISel hands us something like
+  // BRcc MBBx
+  // BR MBBy
+  // since the fallthrough basic block for the conditional branch does not start
+  // with the unconditional branch (it is skipped over).
+  //BuildMI(BB, PPC::COND_BRANCH, 4).addReg(PPC::CR0).addImm(Opc)
+  //  .addMBB(Dest).addMBB(Fallthrough);
+  BuildMI(BB, Opc, 2).addReg(PPC::CR0).addMBB(Dest);
+  return;
+}
+
+unsigned ISel::SelectExprFP(SDOperand N, unsigned Result)
+{
+  unsigned Tmp1, Tmp2, Tmp3;
+  unsigned Opc = 0;
+  SDNode *Node = N.Val;
+  MVT::ValueType DestType = N.getValueType();
+  unsigned opcode = N.getOpcode();
+
+  switch (opcode) {
+  default:
+    Node->dump();
+    assert(0 && "Node not handled!\n");
+
+  case ISD::SELECT: {
+    // Attempt to generate FSEL.  We can do this whenever we have an FP result,
+    // and an FP comparison in the SetCC node.
+    SetCCSDNode* SetCC = dyn_cast<SetCCSDNode>(N.getOperand(0).Val);
+    if (SetCC && N.getOperand(0).getOpcode() == ISD::SETCC &&
+        !MVT::isInteger(SetCC->getOperand(0).getValueType()) &&
+        SetCC->getCondition() != ISD::SETEQ &&
+        SetCC->getCondition() != ISD::SETNE) {
+      MVT::ValueType VT = SetCC->getOperand(0).getValueType();
+      Tmp1 = SelectExpr(SetCC->getOperand(0));   // Val to compare against
+      unsigned TV = SelectExpr(N.getOperand(1)); // Use if TRUE
+      unsigned FV = SelectExpr(N.getOperand(2)); // Use if FALSE
+      
+      ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(SetCC->getOperand(1));
+      if (CN && (CN->isExactlyValue(-0.0) || CN->isExactlyValue(0.0))) {
+        switch(SetCC->getCondition()) {
+        default: assert(0 && "Invalid FSEL condition"); abort();
+        case ISD::SETULT:
+        case ISD::SETLT:
+          BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp1).addReg(FV).addReg(TV);
+          return Result;
+        case ISD::SETUGE:
+        case ISD::SETGE:
+          BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp1).addReg(TV).addReg(FV);
+          return Result;
+        case ISD::SETUGT:
+        case ISD::SETGT: {
+          Tmp2 = MakeReg(VT);
+          BuildMI(BB, PPC::FNEG, 1, Tmp2).addReg(Tmp1);
+          BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp2).addReg(FV).addReg(TV);
+          return Result;
+        }
+        case ISD::SETULE:
+        case ISD::SETLE: {
+          Tmp2 = MakeReg(VT);
+          BuildMI(BB, PPC::FNEG, 1, Tmp2).addReg(Tmp1);
+          BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp2).addReg(TV).addReg(FV);
+          return Result;
+        }
+        }
+      } else {
+        Opc = (MVT::f64 == VT) ? PPC::FSUB : PPC::FSUBS;
+        Tmp2 = SelectExpr(SetCC->getOperand(1));
+        Tmp3 =  MakeReg(VT);
+        switch(SetCC->getCondition()) {
+        default: assert(0 && "Invalid FSEL condition"); abort();
+        case ISD::SETULT:
+        case ISD::SETLT:
+          BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
+          BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(FV).addReg(TV);
+          return Result;
+        case ISD::SETUGE:
+        case ISD::SETGE:
+          BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
+          BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(TV).addReg(FV);
+          return Result;
+        case ISD::SETUGT:
+        case ISD::SETGT:
+          BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
+          BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(FV).addReg(TV);
+          return Result;
+        case ISD::SETULE:
+        case ISD::SETLE:
+          BuildMI(BB, Opc, 2, Tmp3).addReg(Tmp2).addReg(Tmp1);
+          BuildMI(BB, PPC::FSEL, 3, Result).addReg(Tmp3).addReg(TV).addReg(FV);
+          return Result;
+        }
+      }
+      assert(0 && "Should never get here");
+      return 0;
+    }
+    
+    unsigned TrueValue = SelectExpr(N.getOperand(1)); //Use if TRUE
+    unsigned FalseValue = SelectExpr(N.getOperand(2)); //Use if FALSE
+    Opc = SelectSetCR0(N.getOperand(0));
+
+    // Create an iterator with which to insert the MBB for copying the false 
+    // value and the MBB to hold the PHI instruction for this SetCC.
+    MachineBasicBlock *thisMBB = BB;
+    const BasicBlock *LLVM_BB = BB->getBasicBlock();
+    ilist<MachineBasicBlock>::iterator It = BB;
+    ++It;
+
+    //  thisMBB:
+    //  ...
+    //   TrueVal = ...
+    //   cmpTY cr0, r1, r2
+    //   bCC copy1MBB
+    //   fallthrough --> copy0MBB
+    MachineBasicBlock *copy0MBB = new MachineBasicBlock(LLVM_BB);
+    MachineBasicBlock *sinkMBB = new MachineBasicBlock(LLVM_BB);
+    BuildMI(BB, Opc, 2).addReg(PPC::CR0).addMBB(sinkMBB);
+    MachineFunction *F = BB->getParent();
+    F->getBasicBlockList().insert(It, copy0MBB);
+    F->getBasicBlockList().insert(It, sinkMBB);
+    // Update machine-CFG edges
+    BB->addSuccessor(copy0MBB);
+    BB->addSuccessor(sinkMBB);
+
+    //  copy0MBB:
+    //   %FalseValue = ...
+    //   # fallthrough to sinkMBB
+    BB = copy0MBB;
+    // Update machine-CFG edges
+    BB->addSuccessor(sinkMBB);
+
+    //  sinkMBB:
+    //   %Result = phi [ %FalseValue, copy0MBB ], [ %TrueValue, thisMBB ]
+    //  ...
+    BB = sinkMBB;
+    BuildMI(BB, PPC::PHI, 4, Result).addReg(FalseValue)
+      .addMBB(copy0MBB).addReg(TrueValue).addMBB(thisMBB);
+    return Result;
+  }
+
+  case ISD::FNEG:
+    if (!NoExcessFPPrecision && 
+        ISD::ADD == N.getOperand(0).getOpcode() &&
+        N.getOperand(0).Val->hasOneUse() &&
+        ISD::MUL == N.getOperand(0).getOperand(0).getOpcode() &&
+        N.getOperand(0).getOperand(0).Val->hasOneUse()) {
+      ++FusedFP; // Statistic
+      Tmp1 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(0));
+      Tmp2 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(1));
+      Tmp3 = SelectExpr(N.getOperand(0).getOperand(1));
+      Opc = DestType == MVT::f64 ? PPC::FNMADD : PPC::FNMADDS;
+      BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
+    } else if (!NoExcessFPPrecision && 
+        ISD::SUB == N.getOperand(0).getOpcode() &&
+        N.getOperand(0).Val->hasOneUse() &&
+        ISD::MUL == N.getOperand(0).getOperand(0).getOpcode() &&
+        N.getOperand(0).getOperand(0).Val->hasOneUse()) {
+      ++FusedFP; // Statistic
+      Tmp1 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(0));
+      Tmp2 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(1));
+      Tmp3 = SelectExpr(N.getOperand(0).getOperand(1));
+      Opc = DestType == MVT::f64 ? PPC::FNMSUB : PPC::FNMSUBS;
+      BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
+    } else if (ISD::FABS == N.getOperand(0).getOpcode()) {
+      Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
+      BuildMI(BB, PPC::FNABS, 1, Result).addReg(Tmp1);
+    } else {
+      Tmp1 = SelectExpr(N.getOperand(0));
+      BuildMI(BB, PPC::FNEG, 1, Result).addReg(Tmp1);
+    }
+    return Result;
+    
+  case ISD::FABS:
+    Tmp1 = SelectExpr(N.getOperand(0));
+    BuildMI(BB, PPC::FABS, 1, Result).addReg(Tmp1);
+    return Result;
+
+  case ISD::FP_ROUND:
+    assert (DestType == MVT::f32 && 
+            N.getOperand(0).getValueType() == MVT::f64 && 
+            "only f64 to f32 conversion supported here");
+    Tmp1 = SelectExpr(N.getOperand(0));
+    BuildMI(BB, PPC::FRSP, 1, Result).addReg(Tmp1);
+    return Result;
+
+  case ISD::FP_EXTEND:
+    assert (DestType == MVT::f64 && 
+            N.getOperand(0).getValueType() == MVT::f32 && 
+            "only f32 to f64 conversion supported here");
+    Tmp1 = SelectExpr(N.getOperand(0));
+    BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
+    return Result;
+
+  case ISD::CopyFromReg:
+    if (Result == 1)
+      Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
+    Tmp1 = dyn_cast<RegSDNode>(Node)->getReg();
+    BuildMI(BB, PPC::FMR, 1, Result).addReg(Tmp1);
+    return Result;
+    
+  case ISD::ConstantFP: {
+    ConstantFPSDNode *CN = cast<ConstantFPSDNode>(N);
+    Result = getConstDouble(CN->getValue(), Result);
+    return Result;
+  }
+    
+  case ISD::ADD:
+    if (!NoExcessFPPrecision && N.getOperand(0).getOpcode() == ISD::MUL &&
+        N.getOperand(0).Val->hasOneUse()) {
+      ++FusedFP; // Statistic
+      Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
+      Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
+      Tmp3 = SelectExpr(N.getOperand(1));
+      Opc = DestType == MVT::f64 ? PPC::FMADD : PPC::FMADDS;
+      BuildMI(BB, Opc, 3, Result).addReg(Tmp1).addReg(Tmp2).addReg(Tmp3);
+      return Result;
+    }
+    Opc = DestType == MVT::f64 ? PPC::FADD : PPC::FADDS;
+    Tmp1 = SelectExpr(N.getOperand(0));
+    Tmp2 = SelectExpr(N.getOperand(1));
+    BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
+    return Result;
+
+  case ISD::SUB:
+    if (!NoExcessFPPrecision && N.getOperand(0).getOpcode() == ISD::MUL &&
+        N.getOperand(0).Val->hasOneUse()) {
+      ++FusedFP; // Statistic
+      Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));