BOOM!

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

1 files changed, 0 insertions, 2417 deletions

diff --git a/lib/Target/IA64/IA64ISelPattern.cpp b/lib/Target/IA64/IA64ISelPattern.cpp
deleted file mode 100644
index 3a1a413caf..0000000000
--- a/lib/Target/IA64/IA64ISelPattern.cpp
+++ /dev/null
@@ -1,2417 +0,0 @@
-//===-- IA64ISelPattern.cpp - A pattern matching inst selector for IA64 ---===//
-//
-//                     The LLVM Compiler Infrastructure
-//
-// This file was developed by Duraid Madina 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 IA64.
-//
-//===----------------------------------------------------------------------===//
-
-#include "IA64.h"
-#include "IA64InstrBuilder.h"
-#include "IA64RegisterInfo.h"
-#include "IA64MachineFunctionInfo.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/Support/MathExtras.h"
-#include "llvm/ADT/Statistic.h"
-#include <set>
-#include <map>
-#include <algorithm>
-using namespace llvm;
-
-//===----------------------------------------------------------------------===//
-//  IA64TargetLowering - IA64 Implementation of the TargetLowering interface
-namespace {
-  class IA64TargetLowering : public TargetLowering {
-    int VarArgsFrameIndex;            // FrameIndex for start of varargs area.
-
-    //int ReturnAddrIndex;              // FrameIndex for return slot.
-    unsigned GP, SP, RP; // FIXME - clean this mess up
-  public:
-
-   unsigned VirtGPR; // this is public so it can be accessed in the selector
-   // for ISD::RET down below. add an accessor instead? FIXME
-
-   IA64TargetLowering(TargetMachine &TM) : TargetLowering(TM) {
-
-      // register class for general registers
-      addRegisterClass(MVT::i64, IA64::GRRegisterClass);
-
-      // register class for FP registers
-      addRegisterClass(MVT::f64, IA64::FPRegisterClass);
-
-      // register class for predicate registers
-      addRegisterClass(MVT::i1, IA64::PRRegisterClass);
-
-      setOperationAction(ISD::BRCONDTWOWAY     , MVT::Other, Expand);
-      setOperationAction(ISD::BRTWOWAY_CC      , MVT::Other, Expand);
-      setOperationAction(ISD::FP_ROUND_INREG   , MVT::f32  , Expand);
-
-      setSetCCResultType(MVT::i1);
-      setShiftAmountType(MVT::i64);
-
-      setOperationAction(ISD::EXTLOAD          , MVT::i1   , Promote);
-
-      setOperationAction(ISD::ZEXTLOAD         , MVT::i1   , Expand);
-
-      setOperationAction(ISD::SEXTLOAD         , MVT::i1   , Expand);
-      setOperationAction(ISD::SEXTLOAD         , MVT::i8   , Expand);
-      setOperationAction(ISD::SEXTLOAD         , MVT::i16  , Expand);
-      setOperationAction(ISD::SEXTLOAD         , MVT::i32  , Expand);
-
-      setOperationAction(ISD::FREM             , MVT::f32  , Expand);
-      setOperationAction(ISD::FREM             , MVT::f64  , Expand);
-
-      setOperationAction(ISD::UREM             , MVT::f32  , Expand);
-      setOperationAction(ISD::UREM             , MVT::f64  , Expand);
-
-      setOperationAction(ISD::MEMMOVE          , MVT::Other, Expand);
-      setOperationAction(ISD::MEMSET           , MVT::Other, Expand);
-      setOperationAction(ISD::MEMCPY           , MVT::Other, Expand);
-      
-      setOperationAction(ISD::SINT_TO_FP       , MVT::i1   , Promote);
-      setOperationAction(ISD::UINT_TO_FP       , MVT::i1   , Promote);
-      
-      // We don't support sin/cos/sqrt
-      setOperationAction(ISD::FSIN , MVT::f64, Expand);
-      setOperationAction(ISD::FCOS , MVT::f64, Expand);
-      setOperationAction(ISD::FSQRT, MVT::f64, Expand);
-      setOperationAction(ISD::FSIN , MVT::f32, Expand);
-      setOperationAction(ISD::FCOS , MVT::f32, Expand);
-      setOperationAction(ISD::FSQRT, MVT::f32, Expand);
-
-      //IA64 has these, but they are not implemented
-      setOperationAction(ISD::CTTZ , MVT::i64  , Expand);
-      setOperationAction(ISD::CTLZ , MVT::i64  , Expand);
-      setOperationAction(ISD::ROTL , MVT::i64  , Expand);
-      setOperationAction(ISD::ROTR , MVT::i64  , Expand);
-      setOperationAction(ISD::BSWAP, MVT::i64  , Expand);  // mux @rev
-      // FIXME: implement mulhs (xma.h) and mulhu (xma.hu)
-      setOperationAction(ISD::MULHS , MVT::i64  , Expand);
-      setOperationAction(ISD::MULHU , MVT::i64  , Expand);
-
-      // We don't have line number support yet.
-      setOperationAction(ISD::LOCATION, MVT::Other, Expand);
-      setOperationAction(ISD::DEBUG_LOC, MVT::Other, Expand);
-      setOperationAction(ISD::DEBUG_LABEL, MVT::Other, Expand);
-
-      // Not implemented yet.
-      setOperationAction(ISD::STACKSAVE, MVT::Other, Expand); 
-      setOperationAction(ISD::STACKRESTORE, MVT::Other, Expand);
-
-      computeRegisterProperties();
-
-      addLegalFPImmediate(+0.0);
-      addLegalFPImmediate(+1.0);
-      addLegalFPImmediate(-0.0);
-      addLegalFPImmediate(-1.0);
-    }
-
-    /// 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, unsigned CC,
-                bool isTailCall, SDOperand Callee, ArgListTy &Args,
-                SelectionDAG &DAG);
-
-    virtual SDOperand LowerVAStart(SDOperand Chain, SDOperand VAListP,
-                                   Value *VAListV, SelectionDAG &DAG);
-    virtual std::pair<SDOperand,SDOperand>
-      LowerVAArg(SDOperand Chain, SDOperand VAListP, Value *VAListV,
-                 const Type *ArgTy, SelectionDAG &DAG);
-
-    void restoreGP_SP_RP(MachineBasicBlock* BB)
-    {
-      BuildMI(BB, IA64::MOV, 1, IA64::r1).addReg(GP);
-      BuildMI(BB, IA64::MOV, 1, IA64::r12).addReg(SP);
-      BuildMI(BB, IA64::MOV, 1, IA64::rp).addReg(RP);
-    }
-
-    void restoreSP_RP(MachineBasicBlock* BB)
-    {
-      BuildMI(BB, IA64::MOV, 1, IA64::r12).addReg(SP);
-      BuildMI(BB, IA64::MOV, 1, IA64::rp).addReg(RP);
-    }
-
-    void restoreRP(MachineBasicBlock* BB)
-    {
-      BuildMI(BB, IA64::MOV, 1, IA64::rp).addReg(RP);
-    }
-
-    void restoreGP(MachineBasicBlock* BB)
-    {
-      BuildMI(BB, IA64::MOV, 1, IA64::r1).addReg(GP);
-    }
-
-  };
-}
-
-
-std::vector<SDOperand>
-IA64TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) {
-  std::vector<SDOperand> ArgValues;
-
-  //
-  // add beautiful description of IA64 stack frame format
-  // here (from intel 24535803.pdf most likely)
-  //
-  MachineFunction &MF = DAG.getMachineFunction();
-  MachineFrameInfo *MFI = MF.getFrameInfo();
-
-  GP = MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i64));
-  SP = MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i64));
-  RP = MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i64));
-
-  MachineBasicBlock& BB = MF.front();
-
-  unsigned args_int[] = {IA64::r32, IA64::r33, IA64::r34, IA64::r35,
-                         IA64::r36, IA64::r37, IA64::r38, IA64::r39};
-
-  unsigned args_FP[] = {IA64::F8, IA64::F9, IA64::F10, IA64::F11,
-                        IA64::F12,IA64::F13,IA64::F14, IA64::F15};
-
-  unsigned argVreg[8];
-  unsigned argPreg[8];
-  unsigned argOpc[8];
-
-  unsigned used_FPArgs = 0; // how many FP args have been used so far?
-
-  unsigned ArgOffset = 0;
-  int count = 0;
-
-  for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I)
-    {
-      SDOperand newroot, argt;
-      if(count < 8) { // need to fix this logic? maybe.
-
-        switch (getValueType(I->getType())) {
-          default:
-            std::cerr << "ERROR in LowerArgs: unknown type "
-              << getValueType(I->getType()) << "\n";
-            abort();
-          case MVT::f32:
-            // fixme? (well, will need to for weird FP structy stuff,
-            // see intel ABI docs)
-          case MVT::f64:
-//XXX            BuildMI(&BB, IA64::IDEF, 0, args_FP[used_FPArgs]);
-            MF.addLiveIn(args_FP[used_FPArgs]); // mark this reg as liveIn
-            // floating point args go into f8..f15 as-needed, the increment
-            argVreg[count] =                              // is below..:
-            MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::f64));
-            // FP args go into f8..f15 as needed: (hence the ++)
-            argPreg[count] = args_FP[used_FPArgs++];
-            argOpc[count] = IA64::FMOV;
-            argt = newroot = DAG.getCopyFromReg(DAG.getRoot(), argVreg[count],
-                                                MVT::f64);
-            if (I->getType() == Type::FloatTy)
-              argt = DAG.getNode(ISD::FP_ROUND, MVT::f32, argt);
-            break;
-          case MVT::i1: // NOTE: as far as C abi stuff goes,
-                        // bools are just boring old ints
-          case MVT::i8:
-          case MVT::i16:
-          case MVT::i32:
-          case MVT::i64:
-//XXX            BuildMI(&BB, IA64::IDEF, 0, args_int[count]);
-            MF.addLiveIn(args_int[count]); // mark this register as liveIn
-            argVreg[count] =
-            MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i64));
-            argPreg[count] = args_int[count];
-            argOpc[count] = IA64::MOV;
-            argt = newroot =
-              DAG.getCopyFromReg(DAG.getRoot(), argVreg[count], MVT::i64);
-            if ( getValueType(I->getType()) != MVT::i64)
-              argt = DAG.getNode(ISD::TRUNCATE, getValueType(I->getType()),
-                  newroot);
-            break;
-        }
-      } else { // more than 8 args go into the frame
-        // Create the frame index object for this incoming parameter...
-        ArgOffset = 16 + 8 * (count - 8);
-        int FI = MFI->CreateFixedObject(8, ArgOffset);
-
-        // Create the SelectionDAG nodes corresponding to a load
-        //from this parameter
-        SDOperand FIN = DAG.getFrameIndex(FI, MVT::i64);
-        argt = newroot = DAG.getLoad(getValueType(I->getType()),
-                                     DAG.getEntryNode(), FIN, DAG.getSrcValue(NULL));
-      }
-      ++count;
-      DAG.setRoot(newroot.getValue(1));
-      ArgValues.push_back(argt);
-    }
-
-
-  // Create a vreg to hold the output of (what will become)
-  // the "alloc" instruction
-  VirtGPR = MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i64));
-  BuildMI(&BB, IA64::PSEUDO_ALLOC, 0, VirtGPR);
-  // we create a PSEUDO_ALLOC (pseudo)instruction for now
-
-  BuildMI(&BB, IA64::IDEF, 0, IA64::r1);
-
-  // hmm:
-  BuildMI(&BB, IA64::IDEF, 0, IA64::r12);
-  BuildMI(&BB, IA64::IDEF, 0, IA64::rp);
-  // ..hmm.
-
-  BuildMI(&BB, IA64::MOV, 1, GP).addReg(IA64::r1);
-
-  // hmm:
-  BuildMI(&BB, IA64::MOV, 1, SP).addReg(IA64::r12);
-  BuildMI(&BB, IA64::MOV, 1, RP).addReg(IA64::rp);
-  // ..hmm.
-
-  unsigned tempOffset=0;
-
-  // if this is a varargs function, we simply lower llvm.va_start by
-  // pointing to the first entry
-  if(F.isVarArg()) {
-    tempOffset=0;
-    VarArgsFrameIndex = MFI->CreateFixedObject(8, tempOffset);
-  }
-
-  // here we actually do the moving of args, and store them to the stack
-  // too if this is a varargs function:
-  for (int i = 0; i < count && i < 8; ++i) {
-    BuildMI(&BB, argOpc[i], 1, argVreg[i]).addReg(argPreg[i]);
-    if(F.isVarArg()) {
-      // if this is a varargs function, we copy the input registers to the stack
-      int FI = MFI->CreateFixedObject(8, tempOffset);
-      tempOffset+=8;   //XXX: is it safe to use r22 like this?
-      BuildMI(&BB, IA64::MOV, 1, IA64::r22).addFrameIndex(FI);
-      // FIXME: we should use st8.spill here, one day
-      BuildMI(&BB, IA64::ST8, 1, IA64::r22).addReg(argPreg[i]);
-    }
-  }
-
-  // Finally, inform the code generator which regs we return values in.
-  // (see the ISD::RET: case down below)
-  switch (getValueType(F.getReturnType())) {
-  default: assert(0 && "i have no idea where to return this type!");
-  case MVT::isVoid: break;
-  case MVT::i1:
-  case MVT::i8:
-  case MVT::i16:
-  case MVT::i32:
-  case MVT::i64:
-    MF.addLiveOut(IA64::r8);
-    break;
-  case MVT::f32:
-  case MVT::f64:
-    MF.addLiveOut(IA64::F8);
-    break;
-  }
-
-  return ArgValues;
-}
-
-std::pair<SDOperand, SDOperand>
-IA64TargetLowering::LowerCallTo(SDOperand Chain,
-                                const Type *RetTy, bool isVarArg,
-                                unsigned CallingConv, bool isTailCall,
-                                SDOperand Callee, ArgListTy &Args,
-                                SelectionDAG &DAG) {
-
-  MachineFunction &MF = DAG.getMachineFunction();
-
-  unsigned NumBytes = 16;
-  unsigned outRegsUsed = 0;
-
-  if (Args.size() > 8) {
-    NumBytes += (Args.size() - 8) * 8;
-    outRegsUsed = 8;
-  } else {
-    outRegsUsed = Args.size();
-  }
-
-  // FIXME? this WILL fail if we ever try to pass around an arg that
-  // consumes more than a single output slot (a 'real' double, int128
-  // some sort of aggregate etc.), as we'll underestimate how many 'outX'
-  // registers we use. Hopefully, the assembler will notice.
-  MF.getInfo<IA64FunctionInfo>()->outRegsUsed=
-    std::max(outRegsUsed, MF.getInfo<IA64FunctionInfo>()->outRegsUsed);
-
-  Chain = DAG.getNode(ISD::CALLSEQ_START, MVT::Other, Chain,
-                        DAG.getConstant(NumBytes, getPointerTy()));
-
-  std::vector<SDOperand> args_to_use;
-  for (unsigned i = 0, e = Args.size(); i != e; ++i)
-    {
-      switch (getValueType(Args[i].second)) {
-      default: assert(0 && "unexpected argument type!");
-      case MVT::i1:
-      case MVT::i8:
-      case MVT::i16:
-      case MVT::i32:
-        //promote to 64-bits, sign/zero extending based on type
-        //of the argument
-        if(Args[i].second->isSigned())
-          Args[i].first = DAG.getNode(ISD::SIGN_EXTEND, MVT::i64,
-              Args[i].first);
-        else
-          Args[i].first = DAG.getNode(ISD::ZERO_EXTEND, MVT::i64,
-              Args[i].first);
-        break;
-      case MVT::f32:
-        //promote to 64-bits
-        Args[i].first = DAG.getNode(ISD::FP_EXTEND, MVT::f64, Args[i].first);
-      case MVT::f64:
-      case MVT::i64:
-        break;
-      }
-      args_to_use.push_back(Args[i].first);
-    }
-
-  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::CALLSEQ_END, MVT::Other, Chain,
-                      DAG.getConstant(NumBytes, getPointerTy()));
-  return std::make_pair(TheCall, Chain);
-}
-
-SDOperand
-IA64TargetLowering::LowerVAStart(SDOperand Chain, SDOperand VAListP,
-                                 Value *VAListV, SelectionDAG &DAG) {
-  // vastart just stores the address of the VarArgsFrameIndex slot.
-  SDOperand FR = DAG.getFrameIndex(VarArgsFrameIndex, MVT::i64);
-  return DAG.getNode(ISD::STORE, MVT::Other, Chain, FR,
-                     VAListP, DAG.getSrcValue(VAListV));
-}
-
-std::pair<SDOperand,SDOperand> IA64TargetLowering::
-LowerVAArg(SDOperand Chain, SDOperand VAListP, Value *VAListV,
-           const Type *ArgTy, SelectionDAG &DAG) {
-
-  MVT::ValueType ArgVT = getValueType(ArgTy);
-  SDOperand Val = DAG.getLoad(MVT::i64, Chain,
-                              VAListP, DAG.getSrcValue(VAListV));
-  SDOperand Result = DAG.getLoad(ArgVT, DAG.getEntryNode(), Val,
-                                 DAG.getSrcValue(NULL));
-  unsigned Amt;
-  if (ArgVT == MVT::i32 || ArgVT == MVT::f32)
-    Amt = 8;
-  else {
-    assert((ArgVT == MVT::i64 || ArgVT == MVT::f64) &&
-           "Other types should have been promoted for varargs!");
-    Amt = 8;
-  }
-  Val = DAG.getNode(ISD::ADD, Val.getValueType(), Val,
-                    DAG.getConstant(Amt, Val.getValueType()));
-  Chain = DAG.getNode(ISD::STORE, MVT::Other, Chain,
-                      Val, VAListP, DAG.getSrcValue(VAListV));
-  return std::make_pair(Result, Chain);
-}
-
-namespace {
-
-  //===--------------------------------------------------------------------===//
-  /// ISel - IA64 specific code to select IA64 machine instructions for
-  /// SelectionDAG operations.
-  ///
-  class ISel : public SelectionDAGISel {
-    /// IA64Lowering - This object fully describes how to lower LLVM code to an
-    /// IA64-specific SelectionDAG.
-    IA64TargetLowering IA64Lowering;
-    SelectionDAG *ISelDAG; // Hack to support us having a dag->dag transform
-                           // for sdiv and udiv until it is put into the future
-                           // dag combiner
-
-    /// 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;
-    std::set<SDOperand> LoweredTokens;
-
-  public:
-    ISel(TargetMachine &TM) : SelectionDAGISel(IA64Lowering), IA64Lowering(TM),
-                              ISelDAG(0) { }
-
-    /// InstructionSelectBasicBlock - This callback is invoked by
-    /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
-    virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
-
-    unsigned SelectExpr(SDOperand N);
-    void Select(SDOperand N);
-    // a dag->dag to transform mul-by-constant-int to shifts+adds/subs
-    SDOperand BuildConstmulSequence(SDOperand N);
-
-    const char *getPassName() const { return "IA64 Instruction Selector"; }
-  };
-}
-
-/// InstructionSelectBasicBlock - This callback is invoked by SelectionDAGISel
-/// when it has created a SelectionDAG for us to codegen.
-void ISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
-
-  // Codegen the basic block.
-  ISelDAG = &DAG;
-  Select(DAG.getRoot());
-
-  // Clear state used for selection.
-  ExprMap.clear();
-  LoweredTokens.clear();
-  ISelDAG = 0;
-}
-
-// strip leading '0' characters from a string
-void munchLeadingZeros(std::string& inString) {
-  while(inString.c_str()[0]=='0') {
-    inString.erase(0, 1);
-  }
-}
-
-// strip trailing '0' characters from a string
-void munchTrailingZeros(std::string& inString) {
-  int curPos=inString.length()-1;
-
-  while(inString.c_str()[curPos]=='0') {
-    inString.erase(curPos, 1);
-    curPos--;
-  }
-}
-
-// return how many consecutive '0' characters are at the end of a string
-unsigned int countTrailingZeros(std::string& inString) {
-  int curPos=inString.length()-1;
-  unsigned int zeroCount=0;
-  // assert goes here
-  while(inString.c_str()[curPos--]=='0') {
-    zeroCount++;
-  }
-  return zeroCount;
-}
-
-// booth encode a string of '1' and '0' characters (returns string of 'P' (+1)
-// '0' and 'N' (-1) characters)
-void boothEncode(std::string inString, std::string& boothEncodedString) {
-
-  int curpos=0;
-  int replacements=0;
-  int lim=inString.size();
-
-  while(curpos<lim) {
-    if(inString[curpos]=='1') { // if we see a '1', look for a run of them
-      int runlength=0;
-      std::string replaceString="N";
-
-      // find the run length
-      for(;inString[curpos+runlength]=='1';runlength++) ;
-
-      for(int i=0; i<runlength-1; i++)
-        replaceString+="0";
-      replaceString+="1";
-
-      if(runlength>1) {
-        inString.replace(curpos, runlength+1, replaceString);
-        curpos+=runlength-1;
-      } else
-        curpos++;
-    } else { // a zero, we just keep chugging along
-      curpos++;
-    }
-  }
-
-  // clean up (trim the string, reverse it and turn '1's into 'P's)
-  munchTrailingZeros(inString);
-  boothEncodedString="";
-
-  for(int i=inString.size()-1;i>=0;i--)
-    if(inString[i]=='1')
-      boothEncodedString+="P";
-    else
-      boothEncodedString+=inString[i];
-
-}
-
-struct shiftaddblob { // this encodes stuff like (x=) "A << B [+-] C << D"
-  unsigned firstVal;    // A
-  unsigned firstShift;  // B
-  unsigned secondVal;   // C
-  unsigned secondShift; // D
-  bool isSub;
-};
-
-/* this implements Lefevre's "pattern-based" constant multiplication,
- * see "Multiplication by an Integer Constant", INRIA report 1999-06
- *
- * TODO: implement a method to try rewriting P0N<->0PP / N0P<->0NN
- * to get better booth encodings - this does help in practice
- * TODO: weight shifts appropriately (most architectures can't
- * fuse a shift and an add for arbitrary shift amounts) */
-unsigned lefevre(const std::string inString,
-                 std::vector<struct shiftaddblob> &ops) {
-  std::string retstring;
-  std::string s = inString;
-  munchTrailingZeros(s);
-
-  int length=s.length()-1;
-
-  if(length==0) {
-    return(0);
-  }
-
-  std::vector<int> p,n;
-
-  for(int i=0; i<=length; i++) {
-    if (s.c_str()[length-i]=='P') {
-      p.push_back(i);
-    } else if (s.c_str()[length-i]=='N') {
-      n.push_back(i);
-    }
-  }
-
-  std::string t, u;
-  int c = 0;
-  bool f;
-  std::map<const int, int> w;
-
-  for(unsigned i=0; i<p.size(); i++) {
-    for(unsigned j=0; j<i; j++) {
-      w[p[i]-p[j]]++;
-    }
-  }
-
-  for(unsigned i=1; i<n.size(); i++) {
-    for(unsigned j=0; j<i; j++) {
-      w[n[i]-n[j]]++;
-    }
-  }
-
-  for(unsigned i=0; i<p.size(); i++) {
-    for(unsigned j=0; j<n.size(); j++) {
-      w[-abs(p[i]-n[j])]++;
-    }
-  }
-
-  std::map<const int, int>::const_iterator ii;
-  std::vector<int> d;
-  std::multimap<int, int> sorted_by_value;
-
-  for(ii = w.begin(); ii!=w.end(); ii++)
-    sorted_by_value.insert(std::pair<int, int>((*ii).second,(*ii).first));
-
-  for (std::multimap<int, int>::iterator it = sorted_by_value.begin();
-       it != sorted_by_value.end(); ++it) {
-    d.push_back((*it).second);
-  }
-
-  int int_W=0;
-  int int_d;
-
-  while(d.size()>0 && (w[int_d=d.back()] > int_W)) {
-    d.pop_back();
-    retstring=s; // hmmm
-    int x=0;
-    int z=abs(int_d)-1;
-
-    if(int_d>0) {
-
-      for(unsigned base=0; base<retstring.size(); base++) {
-        if( ((base+z+1) < retstring.size()) &&
-           retstring.c_str()[base]=='P' &&
-           retstring.c_str()[base+z+1]=='P')
-        {
-          // match
-          x++;
-          retstring.replace(base, 1, "0");
-          retstring.replace(base+z+1, 1, "p");
-        }
-      }
-
-      for(unsigned base=0; base<retstring.size(); base++) {
-        if( ((base+z+1) < retstring.size()) &&
-           retstring.c_str()[base]=='N' &&
-           retstring.c_str()[base+z+1]=='N')
-        {
-          // match
-          x++;
-          retstring.replace(base, 1, "0");
-          retstring.replace(base+z+1, 1, "n");
-        }
-      }
-
-    } else {
-      for(unsigned base=0; base<retstring.size(); base++) {
-        if( ((base+z+1) < retstring.size()) &&
-            ((retstring.c_str()[base]=='P' &&
-             retstring.c_str()[base+z+1]=='N') ||
-            (retstring.c_str()[base]=='N' &&
-             retstring.c_str()[base+z+1]=='P')) ) {
-          // match
-          x++;
-
-          if(retstring.c_str()[base]=='P') {
-            retstring.replace(base, 1, "0");
-            retstring.replace(base+z+1, 1, "p");
-          } else { // retstring[base]=='N'
-            retstring.replace(base, 1, "0");
-            retstring.replace(base+z+1, 1, "n");
-          }
-        }
-      }
-    }
-
-    if(x>int_W) {
-      int_W = x;
-      t = retstring;
-      c = int_d; // tofix
-    }
-
-  } d.pop_back(); // hmm
-
-  u = t;
-
-  for(unsigned i=0; i<t.length(); i++) {
-    if(t.c_str()[i]=='p' || t.c_str()[i]=='n')
-      t.replace(i, 1, "0");
-  }
-
-  for(unsigned i=0; i<u.length(); i++) {
-    if(u[i]=='P' || u[i]=='N')
-      u.replace(i, 1, "0");
-    if(u[i]=='p')
-      u.replace(i, 1, "P");
-    if(u[i]=='n')
-      u.replace(i, 1, "N");
-  }
-
-  if( c<0 ) {
-    f=true;
-    c=-c;
-  } else
-    f=false;
-
-  int pos=0;
-  while(u[pos]=='0')
-    pos++;
-
-  bool hit=(u[pos]=='N');
-
-  int g=0;
-  if(hit) {
-    g=1;
-    for(unsigned p=0; p<u.length(); p++) {
-      bool isP=(u[p]=='P');
-      bool isN=(u[p]=='N');
-
-      if(isP)
-        u.replace(p, 1, "N");
-      if(isN)
-        u.replace(p, 1, "P");
-    }
-  }
-
-  munchLeadingZeros(u);
-
-  int i = lefevre(u, ops);
-
-  shiftaddblob blob;
-
-  blob.firstVal=i; blob.firstShift=c;
-  blob.isSub=f;
-  blob.secondVal=i; blob.secondShift=0;
-
-  ops.push_back(blob);
-
-  i = ops.size();
-
-  munchLeadingZeros(t);
-
-  if(t.length()==0)
-    return i;
-
-  if(t.c_str()[0]!='P') {
-    g=2;
-    for(unsigned p=0; p<t.length(); p++) {
-      bool isP=(t.c_str()[p]=='P');
-      bool isN=(t.c_str()[p]=='N');
-
-      if(isP)
-        t.replace(p, 1, "N");
-      if(isN)
-        t.replace(p, 1, "P");
-    }
-  }
-
-  int j = lefevre(t, ops);
-
-  int trail=countTrailingZeros(u);
-  blob.secondVal=i; blob.secondShift=trail;
-
-  trail=countTrailingZeros(t);
-  blob.firstVal=j; blob.firstShift=trail;
-
-  switch(g) {
-    case 0:
-      blob.isSub=false; // first + second
-      break;
-    case 1:
-      blob.isSub=true; // first - second
-      break;
-    case 2:
-      blob.isSub=true; // second - first
-      int tmpval, tmpshift;
-      tmpval=blob.firstVal;
-      tmpshift=blob.firstShift;
-      blob.firstVal=blob.secondVal;
-      blob.firstShift=blob.secondShift;
-      blob.secondVal=tmpval;
-      blob.secondShift=tmpshift;
-      break;
-      //assert
-  }
-
-  ops.push_back(blob);
-  return ops.size();
-}
-
-SDOperand ISel::BuildConstmulSequence(SDOperand N) {
-  //FIXME: we should shortcut this stuff for multiplies by 2^n+1
-  //       in particular, *3 is nicer as *2+1, not *4-1
-  int64_t constant=cast<ConstantSDNode>(N.getOperand(1))->getValue();
-
-  bool flippedSign;
-  unsigned preliminaryShift=0;
-
-  assert(constant != 0 && "erk, you're trying to multiply by constant zero\n");
-
-  // first, we make the constant to multiply by positive
-  if(constant<0) {
-    constant=-constant;
-    flippedSign=true;
-  } else {
-    flippedSign=false;
-  }
-
-  // next, we make it odd.
-  for(; (constant%2==0); preliminaryShift++)
-    constant>>=1;
-
-  //OK, we have a positive, odd number of 64 bits or less. Convert it
-  //to a binary string, constantString[0] is the LSB
-  char constantString[65];
-  for(int i=0; i<64; i++)
-    constantString[i]='0'+((constant>>i)&0x1);
-  constantString[64]=0;
-
-  // now, Booth encode it
-  std::string boothEncodedString;
-  boothEncode(constantString, boothEncodedString);
-
-  std::vector<struct shiftaddblob> ops;
-  // do the transformation, filling out 'ops'
-  lefevre(boothEncodedString, ops);
-
-  assert(ops.size() < 80 && "constmul code has gone haywire\n");
-  SDOperand results[80]; // temporary results (of adds/subs of shifts)
-
-  // now turn 'ops' into DAG bits
-  for(unsigned i=0; i<ops.size(); i++) {
-    SDOperand amt = ISelDAG->getConstant(ops[i].firstShift, MVT::i64);
-    SDOperand val = (ops[i].firstVal == 0) ? N.getOperand(0) :
-      results[ops[i].firstVal-1];
-    SDOperand left = ISelDAG->getNode(ISD::SHL, MVT::i64, val, amt);
-    amt = ISelDAG->getConstant(ops[i].secondShift, MVT::i64);
-    val = (ops[i].secondVal == 0) ? N.getOperand(0) :
-      results[ops[i].secondVal-1];
-    SDOperand right = ISelDAG->getNode(ISD::SHL, MVT::i64, val, amt);
-    if(ops[i].isSub)
-      results[i] = ISelDAG->getNode(ISD::SUB, MVT::i64, left, right);
-    else
-      results[i] = ISelDAG->getNode(ISD::ADD, MVT::i64, left, right);
-  }
-
-  // don't forget flippedSign and preliminaryShift!
-  SDOperand shiftedresult;
-  if(preliminaryShift) {
-    SDOperand finalshift = ISelDAG->getConstant(preliminaryShift, MVT::i64);
-    shiftedresult = ISelDAG->getNode(ISD::SHL, MVT::i64,
-        results[ops.size()-1], finalshift);
-  } else { // there was no preliminary divide-by-power-of-2 required
-    shiftedresult = results[ops.size()-1];
-  }
-
-  SDOperand finalresult;
-  if(flippedSign) { // if we were multiplying by a negative constant:
-    SDOperand zero = ISelDAG->getConstant(0, MVT::i64);
-    // subtract the result from 0 to flip its sign
-    finalresult = ISelDAG->getNode(ISD::SUB, MVT::i64, zero, shiftedresult);
-  } else { // there was no preliminary multiply by -1 required
-    finalresult = shiftedresult;
-  }
-
-  return finalresult;
-}
-
-/// ponderIntegerDivisionBy - When handling integer divides, if the divide
-/// is by a constant such that we can efficiently codegen it, this
-/// function says what to do. Currently, it returns 0 if the division must
-/// become a genuine divide, and 1 if the division can be turned into a
-/// right shift.
-static unsigned ponderIntegerDivisionBy(SDOperand N, bool isSigned,
-                                      unsigned& Imm) {
-  if (N.getOpcode() != ISD::Constant) return 0; // if not a divide by
-                                                // a constant, give up.
-
-  int64_t v = (int64_t)cast<ConstantSDNode>(N)->getSignExtended();
-
-  if (isPowerOf2_64(v)) { // if a division by a power of two, say so
-    Imm = Log2_64(v);
-    return 1;
-  }
-
-  return 0; // fallthrough
-}
-
-static unsigned ponderIntegerAndWith(SDOperand N, unsigned& Imm) {
-  if (N.getOpcode() != ISD::Constant) return 0; // if not ANDing with
-                                                // a constant, give up.
-
-  int64_t v = (int64_t)cast<ConstantSDNode>(N)->getSignExtended();
-
-  if (isMask_64(v)) { // if ANDing with ((2^n)-1) for some n
-    Imm = Log2_64(v) + 1;
-    return 1; // say so
-  }
-
-  return 0; // fallthrough
-}
-
-static unsigned ponderIntegerAdditionWith(SDOperand N, unsigned& Imm) {
-  if (N.getOpcode() != ISD::Constant) return 0; // if not adding a
-                                                // constant, give up.
-  int64_t v = (int64_t)cast<ConstantSDNode>(N)->getSignExtended();
-
-  if (v <= 8191 && v >= -8192) { // if this constants fits in 14 bits, say so
-    Imm = v & 0x3FFF; // 14 bits
-    return 1;
-  }
-  return 0; // fallthrough
-}
-
-static unsigned ponderIntegerSubtractionFrom(SDOperand N, unsigned& Imm) {
-  if (N.getOpcode() != ISD::Constant) return 0; // if not subtracting a
-                                                // constant, give up.
-  int64_t v = (int64_t)cast<ConstantSDNode>(N)->getSignExtended();
-
-  if (v <= 127 && v >= -128) { // if this constants fits in 8 bits, say so
-    Imm = v & 0xFF; // 8 bits
-    return 1;
-  }
-  return 0; // fallthrough
-}
-
-unsigned ISel::SelectExpr(SDOperand N) {
-  unsigned Result;
-  unsigned Tmp1, Tmp2, Tmp3;
-  unsigned Opc = 0;
-  MVT::ValueType DestType = N.getValueType();
-
-  unsigned opcode = N.getOpcode();
-
-  SDNode *Node = N.Val;
-  SDOperand Op0, Op1;
-
-  if (Node->getOpcode() == ISD::CopyFromReg)
-    // Just use the specified register as our input.
-    return cast<RegisterSDNode>(Node->getOperand(1))->getReg();
-
-  unsigned &Reg = ExprMap[N];
-  if (Reg) return Reg;
-
-  if (N.getOpcode() != ISD::CALL && N.getOpcode() != ISD::TAILCALL)
-    Reg = Result = (N.getValueType() != MVT::Other) ?
-      MakeReg(N.getValueType()) : 1;
-  else {
-    // If this is a call instruction, make sure to prepare ALL of the result
-    // values as well as the chain.
-    if (Node->getNumValues() == 1)
-      Reg = Result = 1;  // Void call, just a chain.
-    else {
-      Result = MakeReg(Node->getValueType(0));
-      ExprMap[N.getValue(0)] = Result;
-      for (unsigned i = 1, e = N.Val->getNumValues()-1; i != e; ++i)
-        ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
-      ExprMap[SDOperand(Node, Node->getNumValues()-1)] = 1;
-    }
-  }
-
-  switch (N.getOpcode()) {
-  default:
-    Node->dump();
-    assert(0 && "Node not handled!\n");
-
-  case ISD::FrameIndex: {
-    Tmp1 = cast<FrameIndexSDNode>(N)->getIndex();
-    BuildMI(BB, IA64::MOV, 1, Result).addFrameIndex(Tmp1);
-    return Result;
-  }
-
-  case ISD::ConstantPool: {
-    Tmp1 = BB->getParent()->getConstantPool()->
-          getConstantPoolIndex(cast<ConstantPoolSDNode>(N)->get());
-    IA64Lowering.restoreGP(BB); // FIXME: do i really need this?
-    BuildMI(BB, IA64::ADD, 2, Result).addConstantPoolIndex(Tmp1)
-      .addReg(IA64::r1);
-    return Result;
-  }
-
-  case ISD::ConstantFP: {
-    Tmp1 = Result;   // Intermediate Register
-    if (cast<ConstantFPSDNode>(N)->getValue() < 0.0 ||
-        cast<ConstantFPSDNode>(N)->isExactlyValue(-0.0))
-      Tmp1 = MakeReg(MVT::f64);
-
-    if (cast<ConstantFPSDNode>(N)->isExactlyValue(+0.0) ||
-        cast<ConstantFPSDNode>(N)->isExactlyValue(-0.0))
-      BuildMI(BB, IA64::FMOV, 1, Tmp1).addReg(IA64::F0); // load 0.0
-    else if (cast<ConstantFPSDNode>(N)->isExactlyValue(+1.0) ||
-             cast<ConstantFPSDNode>(N)->isExactlyValue(-1.0))
-      BuildMI(BB, IA64::FMOV, 1, Tmp1).addReg(IA64::F1); // load 1.0
-    else
-      assert(0 && "Unexpected FP constant!");
-    if (Tmp1 != Result)
-      // we multiply by +1.0, negate (this is FNMA), and then add 0.0
-      BuildMI(BB, IA64::FNMA, 3, Result).addReg(Tmp1).addReg(IA64::F1)
-        .addReg(IA64::F0);
-    return Result;<