lib/Target/Alpha/AlphaISelPattern.cpp

   1 //===- AlphaISelPattern.cpp - A pattern matching inst selector for Alpha --===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group 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 Alpha.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "Alpha.h"
  15 #include "AlphaRegisterInfo.h"
  16 #include "llvm/Constants.h"                   // FIXME: REMOVE
  17 #include "llvm/Function.h"
  18 #include "llvm/CodeGen/MachineInstrBuilder.h"
  19 #include "llvm/CodeGen/MachineConstantPool.h" // FIXME: REMOVE
  20 #include "llvm/CodeGen/MachineFunction.h"
  21 #include "llvm/CodeGen/MachineFrameInfo.h"
  22 #include "llvm/CodeGen/SelectionDAG.h"
  23 #include "llvm/CodeGen/SelectionDAGISel.h"
  24 #include "llvm/CodeGen/SSARegMap.h"
  25 #include "llvm/Target/TargetData.h"
  26 #include "llvm/Target/TargetLowering.h"
  27 #include "llvm/Support/MathExtras.h"
  28 #include "llvm/ADT/Statistic.h"
  29 #include "llvm/Support/Debug.h"
  30 #include "llvm/Support/CommandLine.h"
  31 #include <set>
  32 #include <algorithm>
  33 using namespace llvm;
  34
  35 namespace llvm {
  36   cl::opt<bool> EnableAlphaIDIV("enable-alpha-intfpdiv",
  37                              cl::desc("Use the FP div instruction for integer div when possible"),
  38                              cl::Hidden);
  39   cl::opt<bool> EnableAlphaFTOI("enable-alpha-ftoi",
  40                              cl::desc("Enable use of ftoi* and itof* instructions (ev6 and higher)"),
  41                              cl::Hidden);
  42   cl::opt<bool> EnableAlphaCount("enable-alpha-count",
  43                              cl::desc("Print estimates on live ins and outs"),
  44                              cl::Hidden);
  45 }
  46
  47 //===----------------------------------------------------------------------===//
  48 //  AlphaTargetLowering - Alpha Implementation of the TargetLowering interface
  49 namespace {
  50   class AlphaTargetLowering : public TargetLowering {
  51     int VarArgsFrameIndex;            // FrameIndex for start of varargs area.
  52     unsigned GP; //GOT vreg
  53   public:
  54     AlphaTargetLowering(TargetMachine &TM) : TargetLowering(TM) {
  55       // Set up the TargetLowering object.
  56       //I am having problems with shr n ubyte 1
  57       setShiftAmountType(MVT::i64);
  58       setSetCCResultType(MVT::i64);
  59       setSetCCResultContents(ZeroOrOneSetCCResult);
  60
  61       addRegisterClass(MVT::i64, Alpha::GPRCRegisterClass);
  62       addRegisterClass(MVT::f64, Alpha::FPRCRegisterClass);
  63       addRegisterClass(MVT::f32, Alpha::FPRCRegisterClass);
  64
  65       setOperationAction(ISD::BRCONDTWOWAY, MVT::Other, Expand);
  66       setOperationAction(ISD::EXTLOAD  , MVT::i1   , Promote);
  67       setOperationAction(ISD::EXTLOAD  , MVT::f32  , Promote);
  68
  69       setOperationAction(ISD::ZEXTLOAD , MVT::i1   , Expand);
  70       setOperationAction(ISD::ZEXTLOAD , MVT::i32  , Expand);
  71
  72       setOperationAction(ISD::SEXTLOAD , MVT::i1   , Expand);
  73       setOperationAction(ISD::SEXTLOAD , MVT::i8   , Expand);
  74       setOperationAction(ISD::SEXTLOAD , MVT::i16  , Expand);
  75
  76       setOperationAction(ISD::SREM     , MVT::f32  , Expand);
  77       setOperationAction(ISD::SREM     , MVT::f64  , Expand);
  78
  79       //      setOperationAction(ISD::CTPOP    , MVT::i64  , Expand);
  80       //      setOperationAction(ISD::CTTZ     , MVT::i64  , Expand);
  81       //      setOperationAction(ISD::CTTZ     , MVT::i64  , Expand);
  82
  83       //If this didn't legalize into a div....
  84       //      setOperationAction(ISD::SREM     , MVT::i64, Expand);
  85       //      setOperationAction(ISD::UREM     , MVT::i64, Expand);
  86
  87       setOperationAction(ISD::MEMMOVE  , MVT::Other, Expand);
  88       setOperationAction(ISD::MEMSET   , MVT::Other, Expand);
  89       setOperationAction(ISD::MEMCPY   , MVT::Other, Expand);
  90
  91       // We don't support sin/cos/sqrt
  92       setOperationAction(ISD::FSIN , MVT::f64, Expand);
  93       setOperationAction(ISD::FCOS , MVT::f64, Expand);
  94       setOperationAction(ISD::FSQRT, MVT::f64, Expand);
  95       setOperationAction(ISD::FSIN , MVT::f32, Expand);
  96       setOperationAction(ISD::FCOS , MVT::f32, Expand);
  97       setOperationAction(ISD::FSQRT, MVT::f32, Expand);
  98
  99       //Doesn't work yet
 100       setOperationAction(ISD::SETCC, MVT::f32,   Promote);
 101
 102       computeRegisterProperties();
 103
 104       addLegalFPImmediate(+0.0); //F31
 105       addLegalFPImmediate(-0.0); //-F31
 106     }
 107
 108     /// LowerArguments - This hook must be implemented to indicate how we should
 109     /// lower the arguments for the specified function, into the specified DAG.
 110     virtual std::vector<SDOperand>
 111     LowerArguments(Function &F, SelectionDAG &DAG);
 112
 113     /// LowerCallTo - This hook lowers an abstract call to a function into an
 114     /// actual call.
 115     virtual std::pair<SDOperand, SDOperand>
 116     LowerCallTo(SDOperand Chain, const Type *RetTy, bool isVarArg,
 117                 SDOperand Callee, ArgListTy &Args, SelectionDAG &DAG);
 118
 119     virtual std::pair<SDOperand, SDOperand>
 120     LowerVAStart(SDOperand Chain, SelectionDAG &DAG);
 121
 122     virtual std::pair<SDOperand,SDOperand>
 123     LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
 124                    const Type *ArgTy, SelectionDAG &DAG);
 125
 126     virtual std::pair<SDOperand, SDOperand>
 127     LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain, unsigned Depth,
 128                             SelectionDAG &DAG);
 129
 130     void restoreGP(MachineBasicBlock* BB)
 131     {
 132       BuildMI(BB, Alpha::BIS, 2, Alpha::R29).addReg(GP).addReg(GP);
 133     }
 134   };
 135 }
 136
 137 //http://www.cs.arizona.edu/computer.help/policy/DIGITAL_unix/AA-PY8AC-TET1_html/callCH3.html#BLOCK21
 138
 139 //For now, just use variable size stack frame format
 140
 141 //In a standard call, the first six items are passed in registers $16
 142 //- $21 and/or registers $f16 - $f21. (See Section 4.1.2 for details
 143 //of argument-to-register correspondence.) The remaining items are
 144 //collected in a memory argument list that is a naturally aligned
 145 //array of quadwords. In a standard call, this list, if present, must
 146 //be passed at 0(SP).
 147 //7 ... n         0(SP) ... (n-7)*8(SP)
 148
 149 // //#define FP    $15
 150 // //#define RA    $26
 151 // //#define PV    $27
 152 // //#define GP    $29
 153 // //#define SP    $30
 154
 155 std::vector<SDOperand>
 156 AlphaTargetLowering::LowerArguments(Function &F, SelectionDAG &DAG)
 157 {
 158   std::vector<SDOperand> ArgValues;
 159   std::vector<SDOperand> LS;
 160   SDOperand Chain = DAG.getRoot();
 161
 162   //  assert(0 && "TODO");
 163   MachineFunction &MF = DAG.getMachineFunction();
 164   MachineFrameInfo*MFI = MF.getFrameInfo();
 165
 166   GP = MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i64));
 167   MachineBasicBlock& BB = MF.front();
 168
 169   //Handle the return address
 170   //BuildMI(&BB, Alpha::IDEF, 0, Alpha::R26);
 171
 172   unsigned args_int[] = {Alpha::R16, Alpha::R17, Alpha::R18,
 173                          Alpha::R19, Alpha::R20, Alpha::R21};
 174   unsigned args_float[] = {Alpha::F16, Alpha::F17, Alpha::F18,
 175                            Alpha::F19, Alpha::F20, Alpha::F21};
 176   int count = 0;
 177
 178   //Def incoming registers
 179   {
 180     Function::arg_iterator I = F.arg_begin();
 181     Function::arg_iterator E = F.arg_end();
 182     for (int i = 0; i < 6; ++i)
 183     {
 184       if (F.isVarArg()) {
 185         MF.addLiveIn(args_int[i]);
 186         MF.addLiveIn(args_float[i]);
 187 //        BuildMI(&BB, Alpha::IDEF, 0, args_int[i]);
 188 //        BuildMI(&BB, Alpha::IDEF, 0, args_float[i]);
 189       } else if (I != E)
 190       {
 191         if(MVT::isInteger(getValueType(I->getType())))
 192           MF.addLiveIn(args_int[i]);
 193 //          BuildMI(&BB, Alpha::IDEF, 0, args_int[i]);
 194         else
 195           MF.addLiveIn(args_float[i]);
 196 //          BuildMI(&BB, Alpha::IDEF, 0, args_float[i]);
 197         ++I;
 198       }
 199     }
 200   }
 201
 202   MF.addLiveIn(Alpha::R29);
 203 //  BuildMI(&BB, Alpha::IDEF, 0, Alpha::R29);
 204   BuildMI(&BB, Alpha::BIS, 2, GP).addReg(Alpha::R29).addReg(Alpha::R29);
 205
 206   for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I)
 207   {
 208     SDOperand newroot, argt;
 209     if (count  < 6) {
 210       unsigned Vreg;
 211       MVT::ValueType VT = getValueType(I->getType());
 212       switch (getValueType(I->getType())) {
 213       default:
 214         std::cerr << "Unknown Type " << VT << "\n";
 215         abort();
 216       case MVT::f64:
 217       case MVT::f32:
 218         Vreg = MF.getSSARegMap()->createVirtualRegister(getRegClassFor(VT));
 219         BuildMI(&BB, Alpha::CPYS, 2, Vreg).addReg(args_float[count]).addReg(args_float[count]);
 220         argt = newroot = DAG.getCopyFromReg(Vreg,
 221                                             getValueType(I->getType()),
 222                                             Chain);
 223         break;
 224       case MVT::i1:
 225       case MVT::i8:
 226       case MVT::i16:
 227       case MVT::i32:
 228       case MVT::i64:
 229         Vreg = MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i64));
 230         BuildMI(&BB, Alpha::BIS, 2, Vreg).addReg(args_int[count]).addReg(args_int[count]);
 231         argt = newroot = DAG.getCopyFromReg(Vreg, MVT::i64, Chain);
 232         if (getValueType(I->getType()) != MVT::i64)
 233           argt = DAG.getNode(ISD::TRUNCATE, getValueType(I->getType()), newroot);
 234         break;
 235       }
 236     } else { //more args
 237       // Create the frame index object for this incoming parameter...
 238       int FI = MFI->CreateFixedObject(8, 8 * (count - 6));
 239
 240       // Create the SelectionDAG nodes corresponding to a load
 241       //from this parameter
 242       SDOperand FIN = DAG.getFrameIndex(FI, MVT::i64);
 243       argt = newroot = DAG.getLoad(getValueType(I->getType()),
 244                                    DAG.getEntryNode(), FIN, DAG.getSrcValue(NULL));
 245     }
 246     ++count;
 247     LS.push_back(newroot.getValue(1));
 248     ArgValues.push_back(argt);
 249   }
 250
 251   // If the functions takes variable number of arguments, copy all regs to stack
 252   if (F.isVarArg())
 253     for (int i = 0; i < 6; ++i)
 254     {
 255       unsigned Vreg = MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::i64));
 256       BuildMI(&BB, Alpha::BIS, 2, Vreg).addReg(args_int[i]).addReg(args_int[i]);
 257       SDOperand argt = DAG.getCopyFromReg(Vreg, MVT::i64, Chain);
 258       int FI = MFI->CreateFixedObject(8, -8 * (6 - i));
 259       SDOperand SDFI = DAG.getFrameIndex(FI, MVT::i64);
 260       LS.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain, argt, SDFI, DAG.getSrcValue(NULL)));
 261
 262       Vreg = MF.getSSARegMap()->createVirtualRegister(getRegClassFor(MVT::f64));
 263       BuildMI(&BB, Alpha::CPYS, 2, Vreg).addReg(args_float[i]).addReg(args_float[i]);
 264       argt = DAG.getCopyFromReg(Vreg, MVT::f64, Chain);
 265       FI = MFI->CreateFixedObject(8, - 8 * (12 - i));
 266       SDFI = DAG.getFrameIndex(FI, MVT::i64);
 267       LS.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain, argt, SDFI, DAG.getSrcValue(NULL)));
 268     }
 269
 270   // If the function takes variable number of arguments, make a frame index for
 271   // the start of the first arg value... for expansion of llvm.va_start.
 272   //   if (F.isVarArg())
 273   //     VarArgsFrameIndex = MFI->CreateFixedObject(4, ArgOffset);
 274
 275   //Set up a token factor with all the stack traffic
 276   DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, LS));
 277
 278   // Finally, inform the code generator which regs we return values in.
 279   switch (getValueType(F.getReturnType())) {
 280   default: assert(0 && "Unknown type!");
 281   case MVT::isVoid: break;
 282   case MVT::i1:
 283   case MVT::i8:
 284   case MVT::i16:
 285   case MVT::i32:
 286   case MVT::i64:
 287     MF.addLiveOut(Alpha::R0);
 288     break;
 289   case MVT::f32:
 290   case MVT::f64:
 291     MF.addLiveOut(Alpha::F0);
 292     break;
 293   }
 294
 295   //return the arguments
 296   return ArgValues;
 297 }
 298
 299 std::pair<SDOperand, SDOperand>
 300 AlphaTargetLowering::LowerCallTo(SDOperand Chain,
 301                                  const Type *RetTy, bool isVarArg,
 302                                  SDOperand Callee, ArgListTy &Args,
 303                                  SelectionDAG &DAG) {
 304   int NumBytes = 0;
 305   if (Args.size() > 6)
 306     NumBytes = (Args.size() - 6) * 8;
 307
 308   Chain = DAG.getNode(ISD::ADJCALLSTACKDOWN, MVT::Other, Chain,
 309                       DAG.getConstant(NumBytes, getPointerTy()));
 310   std::vector<SDOperand> args_to_use;
 311   for (unsigned i = 0, e = Args.size(); i != e; ++i)
 312   {
 313     switch (getValueType(Args[i].second)) {
 314     default: assert(0 && "Unexpected ValueType for argument!");
 315     case MVT::i1:
 316     case MVT::i8:
 317     case MVT::i16:
 318     case MVT::i32:
 319       // Promote the integer to 64 bits.  If the input type is signed use a
 320       // sign extend, otherwise use a zero extend.
 321       if (Args[i].second->isSigned())
 322         Args[i].first = DAG.getNode(ISD::SIGN_EXTEND, MVT::i64, Args[i].first);
 323       else
 324         Args[i].first = DAG.getNode(ISD::ZERO_EXTEND, MVT::i64, Args[i].first);
 325       break;
 326     case MVT::i64:
 327     case MVT::f64:
 328     case MVT::f32:
 329       break;
 330     }
 331     args_to_use.push_back(Args[i].first);
 332   }
 333
 334   std::vector<MVT::ValueType> RetVals;
 335   MVT::ValueType RetTyVT = getValueType(RetTy);
 336   if (RetTyVT != MVT::isVoid)
 337     RetVals.push_back(RetTyVT);
 338   RetVals.push_back(MVT::Other);
 339
 340   SDOperand TheCall = SDOperand(DAG.getCall(RetVals,
 341                                             Chain, Callee, args_to_use), 0);
 342   Chain = TheCall.getValue(RetTyVT != MVT::isVoid);
 343   Chain = DAG.getNode(ISD::ADJCALLSTACKUP, MVT::Other, Chain,
 344                       DAG.getConstant(NumBytes, getPointerTy()));
 345   return std::make_pair(TheCall, Chain);
 346 }
 347
 348 std::pair<SDOperand, SDOperand>
 349 AlphaTargetLowering::LowerVAStart(SDOperand Chain, SelectionDAG &DAG) {
 350   //vastart just returns the address of the VarArgsFrameIndex slot.
 351   return std::make_pair(DAG.getFrameIndex(VarArgsFrameIndex, MVT::i64), Chain);
 352 }
 353
 354 std::pair<SDOperand,SDOperand> AlphaTargetLowering::
 355 LowerVAArgNext(bool isVANext, SDOperand Chain, SDOperand VAList,
 356                const Type *ArgTy, SelectionDAG &DAG) {
 357   abort();
 358 }
 359
 360
 361 std::pair<SDOperand, SDOperand> AlphaTargetLowering::
 362 LowerFrameReturnAddress(bool isFrameAddress, SDOperand Chain, unsigned Depth,
 363                         SelectionDAG &DAG) {
 364   abort();
 365 }
 366
 367
 368
 369
 370
 371 namespace {
 372
 373 //===--------------------------------------------------------------------===//
 374 /// ISel - Alpha specific code to select Alpha machine instructions for
 375 /// SelectionDAG operations.
 376 //===--------------------------------------------------------------------===//
 377 class ISel : public SelectionDAGISel {
 378
 379   /// AlphaLowering - This object fully describes how to lower LLVM code to an
 380   /// Alpha-specific SelectionDAG.
 381   AlphaTargetLowering AlphaLowering;
 382
 383   SelectionDAG *ISelDAG;  // Hack to support us having a dag->dag transform
 384                           // for sdiv and udiv until it is put into the future
 385                           // dag combiner.
 386
 387   /// ExprMap - As shared expressions are codegen'd, we keep track of which
 388   /// vreg the value is produced in, so we only emit one copy of each compiled
 389   /// tree.
 390   static const unsigned notIn = (unsigned)(-1);
 391   std::map<SDOperand, unsigned> ExprMap;
 392
 393   //CCInvMap sometimes (SetNE) we have the inverse CC code for free
 394   std::map<SDOperand, unsigned> CCInvMap;
 395
 396   int count_ins;
 397   int count_outs;
 398   bool has_sym;
 399   int max_depth;
 400
 401 public:
 402   ISel(TargetMachine &TM) : SelectionDAGISel(AlphaLowering), AlphaLowering(TM)
 403   {}
 404
 405   /// InstructionSelectBasicBlock - This callback is invoked by
 406   /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 407   virtual void InstructionSelectBasicBlock(SelectionDAG &DAG) {
 408     DEBUG(BB->dump());
 409     count_ins = 0;
 410     count_outs = 0;
 411     max_depth = 0;
 412     has_sym = false;
 413
 414     // Codegen the basic block.
 415     ISelDAG = &DAG;
 416     max_depth = DAG.getRoot().getNodeDepth();
 417     Select(DAG.getRoot());
 418
 419     if(has_sym)
 420       ++count_ins;
 421     if(EnableAlphaCount)
 422       std::cerr << "COUNT: " << BB->getParent()->getFunction ()->getName() << " "
 423                 << BB->getNumber() << " "
 424                 << max_depth << " "
 425                 << count_ins << " "
 426                 << count_outs << "\n";
 427
 428     // Clear state used for selection.
 429     ExprMap.clear();
 430     CCInvMap.clear();
 431   }
 432
 433   unsigned SelectExpr(SDOperand N);
 434   unsigned SelectExprFP(SDOperand N, unsigned Result);
 435   void Select(SDOperand N);
 436
 437   void SelectAddr(SDOperand N, unsigned& Reg, long& offset);
 438   void SelectBranchCC(SDOperand N);
 439   void MoveFP2Int(unsigned src, unsigned dst, bool isDouble);
 440   void MoveInt2FP(unsigned src, unsigned dst, bool isDouble);
 441   //returns whether the sense of the comparison was inverted
 442   bool SelectFPSetCC(SDOperand N, unsigned dst);
 443
 444   // dag -> dag expanders for integer divide by constant
 445   SDOperand BuildSDIVSequence(SDOperand N);
 446   SDOperand BuildUDIVSequence(SDOperand N);
 447
 448 };
 449 }
 450
 451 //Factorize a number using the list of constants
 452 static bool factorize(int v[], int res[], int size, uint64_t c)
 453 {
 454   bool cont = true;
 455   while (c != 1 && cont)
 456   {
 457     cont = false;
 458     for(int i = 0; i < size; ++i)
 459     {
 460       if (c % v[i] == 0)
 461       {
 462         c /= v[i];
 463         ++res[i];
 464         cont=true;
 465       }
 466     }
 467   }
 468   return c == 1;
 469 }
 470
 471
 472 //Shamelessly adapted from PPC32
 473 // Structure used to return the necessary information to codegen an SDIV as
 474 // a multiply.
 475 struct ms {
 476   int64_t m; // magic number
 477   int64_t s; // shift amount
 478 };
 479
 480 struct mu {
 481   uint64_t m; // magic number
 482   int64_t a;          // add indicator
 483   int64_t s;          // shift amount
 484 };
 485
 486 /// magic - calculate the magic numbers required to codegen an integer sdiv as
 487 /// a sequence of multiply and shifts.  Requires that the divisor not be 0, 1,
 488 /// or -1.
 489 static struct ms magic(int64_t d) {
 490   int64_t p;
 491   uint64_t ad, anc, delta, q1, r1, q2, r2, t;
 492   const uint64_t two63 = 9223372036854775808ULL; // 2^63
 493   struct ms mag;
 494
 495   ad = abs(d);
 496   t = two63 + ((uint64_t)d >> 63);
 497   anc = t - 1 - t%ad;   // absolute value of nc
 498   p = 63;               // initialize p
 499   q1 = two63/anc;       // initialize q1 = 2p/abs(nc)
 500   r1 = two63 - q1*anc;  // initialize r1 = rem(2p,abs(nc))
 501   q2 = two63/ad;        // initialize q2 = 2p/abs(d)
 502   r2 = two63 - q2*ad;   // initialize r2 = rem(2p,abs(d))
 503   do {
 504     p = p + 1;
 505     q1 = 2*q1;        // update q1 = 2p/abs(nc)
 506     r1 = 2*r1;        // update r1 = rem(2p/abs(nc))
 507     if (r1 >= anc) {  // must be unsigned comparison
 508       q1 = q1 + 1;
 509       r1 = r1 - anc;
 510     }
 511     q2 = 2*q2;        // update q2 = 2p/abs(d)
 512     r2 = 2*r2;        // update r2 = rem(2p/abs(d))
 513     if (r2 >= ad) {   // must be unsigned comparison
 514       q2 = q2 + 1;
 515       r2 = r2 - ad;
 516     }
 517     delta = ad - r2;
 518   } while (q1 < delta || (q1 == delta && r1 == 0));
 519
 520   mag.m = q2 + 1;
 521   if (d < 0) mag.m = -mag.m; // resulting magic number
 522   mag.s = p - 64;            // resulting shift
 523   return mag;
 524 }
 525
 526 /// magicu - calculate the magic numbers required to codegen an integer udiv as
 527 /// a sequence of multiply, add and shifts.  Requires that the divisor not be 0.
 528 static struct mu magicu(uint64_t d)
 529 {
 530   int64_t p;
 531   uint64_t nc, delta, q1, r1, q2, r2;
 532   struct mu magu;
 533   magu.a = 0;               // initialize "add" indicator
 534   nc = - 1 - (-d)%d;
 535   p = 63;                   // initialize p
 536   q1 = 0x8000000000000000ull/nc;       // initialize q1 = 2p/nc
 537   r1 = 0x8000000000000000ull - q1*nc;  // initialize r1 = rem(2p,nc)
 538   q2 = 0x7FFFFFFFFFFFFFFFull/d;        // initialize q2 = (2p-1)/d
 539   r2 = 0x7FFFFFFFFFFFFFFFull - q2*d;   // initialize r2 = rem((2p-1),d)
 540   do {
 541     p = p + 1;
 542     if (r1 >= nc - r1 ) {
 543       q1 = 2*q1 + 1;  // update q1
 544       r1 = 2*r1 - nc; // update r1
 545     }
 546     else {
 547       q1 = 2*q1; // update q1
 548       r1 = 2*r1; // update r1
 549     }
 550     if (r2 + 1 >= d - r2) {
 551       if (q2 >= 0x7FFFFFFFFFFFFFFFull) magu.a = 1;
 552       q2 = 2*q2 + 1;     // update q2
 553       r2 = 2*r2 + 1 - d; // update r2
 554     }
 555     else {
 556       if (q2 >= 0x8000000000000000ull) magu.a = 1;
 557       q2 = 2*q2;     // update q2
 558       r2 = 2*r2 + 1; // update r2
 559     }
 560     delta = d - 1 - r2;
 561   } while (p < 64 && (q1 < delta || (q1 == delta && r1 == 0)));
 562   magu.m = q2 + 1; // resulting magic number
 563   magu.s = p - 64;  // resulting shift
 564   return magu;
 565 }
 566
 567 /// BuildSDIVSequence - Given an ISD::SDIV node expressing a divide by constant,
 568 /// return a DAG expression to select that will generate the same value by
 569 /// multiplying by a magic number.  See:
 570 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
 571 SDOperand ISel::BuildSDIVSequence(SDOperand N) {
 572   int64_t d = (int64_t)cast<ConstantSDNode>(N.getOperand(1))->getSignExtended();
 573   ms magics = magic(d);
 574   // Multiply the numerator (operand 0) by the magic value
 575   SDOperand Q = ISelDAG->getNode(ISD::MULHS, MVT::i64, N.getOperand(0),
 576                                  ISelDAG->getConstant(magics.m, MVT::i64));
 577   // If d > 0 and m < 0, add the numerator
 578   if (d > 0 && magics.m < 0)
 579     Q = ISelDAG->getNode(ISD::ADD, MVT::i64, Q, N.getOperand(0));
 580   // If d < 0 and m > 0, subtract the numerator.
 581   if (d < 0 && magics.m > 0)
 582     Q = ISelDAG->getNode(ISD::SUB, MVT::i64, Q, N.getOperand(0));
 583   // Shift right algebraic if shift value is nonzero
 584   if (magics.s > 0)
 585     Q = ISelDAG->getNode(ISD::SRA, MVT::i64, Q,
 586                          ISelDAG->getConstant(magics.s, MVT::i64));
 587   // Extract the sign bit and add it to the quotient
 588   SDOperand T =
 589     ISelDAG->getNode(ISD::SRL, MVT::i64, Q, ISelDAG->getConstant(63, MVT::i64));
 590   return ISelDAG->getNode(ISD::ADD, MVT::i64, Q, T);
 591 }
 592
 593 /// BuildUDIVSequence - Given an ISD::UDIV node expressing a divide by constant,
 594 /// return a DAG expression to select that will generate the same value by
 595 /// multiplying by a magic number.  See:
 596 /// <http://the.wall.riscom.net/books/proc/ppc/cwg/code2.html>
 597 SDOperand ISel::BuildUDIVSequence(SDOperand N) {
 598   unsigned d =
 599     (unsigned)cast<ConstantSDNode>(N.getOperand(1))->getSignExtended();
 600   mu magics = magicu(d);
 601   // Multiply the numerator (operand 0) by the magic value
 602   SDOperand Q = ISelDAG->getNode(ISD::MULHU, MVT::i64, N.getOperand(0),
 603                                  ISelDAG->getConstant(magics.m, MVT::i64));
 604   if (magics.a == 0) {
 605     Q = ISelDAG->getNode(ISD::SRL, MVT::i64, Q,
 606                          ISelDAG->getConstant(magics.s, MVT::i64));
 607   } else {
 608     SDOperand NPQ = ISelDAG->getNode(ISD::SUB, MVT::i64, N.getOperand(0), Q);
 609     NPQ = ISelDAG->getNode(ISD::SRL, MVT::i64, NPQ,
 610                            ISelDAG->getConstant(1, MVT::i64));
 611     NPQ = ISelDAG->getNode(ISD::ADD, MVT::i64, NPQ, Q);
 612     Q = ISelDAG->getNode(ISD::SRL, MVT::i64, NPQ,
 613                            ISelDAG->getConstant(magics.s-1, MVT::i64));
 614   }
 615   return Q;
 616 }
 617
 618 //From PPC32
 619 /// ExactLog2 - This function solves for (Val == 1 << (N-1)) and returns N.  It
 620 /// returns zero when the input is not exactly a power of two.
 621 static unsigned ExactLog2(uint64_t Val) {
 622   if (Val == 0 || (Val & (Val-1))) return 0;
 623   unsigned Count = 0;
 624   while (Val != 1) {
 625     Val >>= 1;
 626     ++Count;
 627   }
 628   return Count;
 629 }
 630
 631
 632 //These describe LDAx
 633 static const int IMM_LOW  = -32768;
 634 static const int IMM_HIGH = 32767;
 635 static const int IMM_MULT = 65536;
 636
 637 static long getUpper16(long l)
 638 {
 639   long y = l / IMM_MULT;
 640   if (l % IMM_MULT > IMM_HIGH)
 641     ++y;
 642   return y;
 643 }
 644
 645 static long getLower16(long l)
 646 {
 647   long h = getUpper16(l);
 648   return l - h * IMM_MULT;
 649 }
 650
 651 static unsigned GetSymVersion(unsigned opcode)
 652 {
 653   switch (opcode) {
 654   default: assert(0 && "unknown load or store"); return 0;
 655   case Alpha::LDQ: return Alpha::LDQ_SYM;
 656   case Alpha::LDS: return Alpha::LDS_SYM;
 657   case Alpha::LDT: return Alpha::LDT_SYM;
 658   case Alpha::LDL: return Alpha::LDL_SYM;
 659   case Alpha::LDBU: return Alpha::LDBU_SYM;
 660   case Alpha::LDWU: return Alpha::LDWU_SYM;
 661   case Alpha::LDW: return Alpha::LDW_SYM;
 662   case Alpha::LDB: return Alpha::LDB_SYM;
 663   case Alpha::STQ: return Alpha::STQ_SYM;
 664   case Alpha::STS: return Alpha::STS_SYM;
 665   case Alpha::STT: return Alpha::STT_SYM;
 666   case Alpha::STL: return Alpha::STL_SYM;
 667   case Alpha::STW: return Alpha::STW_SYM;
 668   case Alpha::STB: return Alpha::STB_SYM;
 669   }
 670 }
 671
 672 void ISel::MoveFP2Int(unsigned src, unsigned dst, bool isDouble)
 673 {
 674   unsigned Opc;
 675   if (EnableAlphaFTOI) {
 676     Opc = isDouble ? Alpha::FTOIT : Alpha::FTOIS;
 677     BuildMI(BB, Opc, 1, dst).addReg(src);
 678   } else {
 679     //The hard way:
 680     // Spill the integer to memory and reload it from there.
 681     unsigned Size = MVT::getSizeInBits(MVT::f64)/8;
 682     MachineFunction *F = BB->getParent();
 683     int FrameIdx = F->getFrameInfo()->CreateStackObject(Size, 8);
 684
 685     Opc = isDouble ? Alpha::STT : Alpha::STS;
 686     BuildMI(BB, Opc, 3).addReg(src).addFrameIndex(FrameIdx).addReg(Alpha::F31);
 687     Opc = isDouble ? Alpha::LDQ : Alpha::LDL;
 688     BuildMI(BB, Alpha::LDQ, 2, dst).addFrameIndex(FrameIdx).addReg(Alpha::F31);
 689   }
 690 }
 691
 692 void ISel::MoveInt2FP(unsigned src, unsigned dst, bool isDouble)
 693 {
 694   unsigned Opc;
 695   if (EnableAlphaFTOI) {
 696     Opc = isDouble?Alpha::ITOFT:Alpha::ITOFS;
 697     BuildMI(BB, Opc, 1, dst).addReg(src);
 698   } else {
 699     //The hard way:
 700     // Spill the integer to memory and reload it from there.
 701     unsigned Size = MVT::getSizeInBits(MVT::f64)/8;
 702     MachineFunction *F = BB->getParent();
 703     int FrameIdx = F->getFrameInfo()->CreateStackObject(Size, 8);
 704
 705     Opc = isDouble ? Alpha::STQ : Alpha::STL;
 706     BuildMI(BB, Opc, 3).addReg(src).addFrameIndex(FrameIdx).addReg(Alpha::F31);
 707     Opc = isDouble ? Alpha::LDT : Alpha::LDS;
 708     BuildMI(BB, Opc, 2, dst).addFrameIndex(FrameIdx).addReg(Alpha::F31);
 709   }
 710 }
 711
 712 bool ISel::SelectFPSetCC(SDOperand N, unsigned dst)
 713 {
 714   SDNode *Node = N.Val;
 715   unsigned Opc, Tmp1, Tmp2, Tmp3;
 716   SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(Node);
 717
 718   //assert(SetCC->getOperand(0).getValueType() != MVT::f32 && "SetCC f32 should have been promoted");
 719   bool rev = false;
 720   bool inv = false;
 721
 722   switch (SetCC->getCondition()) {
 723   default: Node->dump(); assert(0 && "Unknown FP comparison!");
 724   case ISD::SETEQ: Opc = Alpha::CMPTEQ; break;
 725   case ISD::SETLT: Opc = Alpha::CMPTLT; break;
 726   case ISD::SETLE: Opc = Alpha::CMPTLE; break;
 727   case ISD::SETGT: Opc = Alpha::CMPTLT; rev = true; break;
 728   case ISD::SETGE: Opc = Alpha::CMPTLE; rev = true; break;
 729   case ISD::SETNE: Opc = Alpha::CMPTEQ; inv = true; break;
 730   }
 731
 732   //FIXME: check for constant 0.0
 733   ConstantFPSDNode *CN;
 734   if ((CN = dyn_cast<ConstantFPSDNode>(SetCC->getOperand(0)))
 735       && (CN->isExactlyValue(+0.0) || CN->isExactlyValue(-0.0)))
 736     Tmp1 = Alpha::F31;
 737   else
 738     Tmp1 = SelectExpr(N.getOperand(0));
 739
 740   if ((CN = dyn_cast<ConstantFPSDNode>(SetCC->getOperand(1)))
 741       && (CN->isExactlyValue(+0.0) || CN->isExactlyValue(-0.0)))
 742     Tmp2 = Alpha::F31;
 743   else
 744     Tmp2 = SelectExpr(N.getOperand(1));
 745
 746   //Can only compare doubles, and dag won't promote for me
 747   if (SetCC->getOperand(0).getValueType() == MVT::f32)
 748     {
 749       //assert(0 && "Setcc On float?\n");
 750       std::cerr << "Setcc on float!\n";
 751       Tmp3 = MakeReg(MVT::f64);
 752       BuildMI(BB, Alpha::CVTST, 1, Tmp3).addReg(Tmp1);
 753       Tmp1 = Tmp3;
 754     }
 755   if (SetCC->getOperand(1).getValueType() == MVT::f32)
 756     {
 757       //assert (0 && "Setcc On float?\n");
 758       std::cerr << "Setcc on float!\n";
 759       Tmp3 = MakeReg(MVT::f64);
 760       BuildMI(BB, Alpha::CVTST, 1, Tmp3).addReg(Tmp2);
 761       Tmp2 = Tmp3;
 762     }
 763
 764   if (rev) std::swap(Tmp1, Tmp2);
 765   //do the comparison
 766   BuildMI(BB, Opc, 2, dst).addReg(Tmp1).addReg(Tmp2);
 767   return inv;
 768 }
 769
 770 //Check to see if the load is a constant offset from a base register
 771 void ISel::SelectAddr(SDOperand N, unsigned& Reg, long& offset)
 772 {
 773   unsigned opcode = N.getOpcode();
 774   if (opcode == ISD::ADD) {
 775     if(N.getOperand(1).getOpcode() == ISD::Constant &&
 776        cast<ConstantSDNode>(N.getOperand(1))->getValue() <= 32767)
 777     { //Normal imm add
 778       Reg = SelectExpr(N.getOperand(0));
 779       offset = cast<ConstantSDNode>(N.getOperand(1))->getValue();
 780       return;
 781     }
 782     else if(N.getOperand(0).getOpcode() == ISD::Constant &&
 783             cast<ConstantSDNode>(N.getOperand(0))->getValue() <= 32767)
 784     {
 785       Reg = SelectExpr(N.getOperand(1));
 786       offset = cast<ConstantSDNode>(N.getOperand(0))->getValue();
 787       return;
 788     }
 789   }
 790   Reg = SelectExpr(N);
 791   offset = 0;
 792   return;
 793 }
 794
 795 void ISel::SelectBranchCC(SDOperand N)
 796 {
 797   assert(N.getOpcode() == ISD::BRCOND && "Not a BranchCC???");
 798   MachineBasicBlock *Dest =
 799     cast<BasicBlockSDNode>(N.getOperand(2))->getBasicBlock();
 800   unsigned Opc = Alpha::WTF;
 801
 802   Select(N.getOperand(0));  //chain
 803   SDOperand CC = N.getOperand(1);
 804
 805   if (CC.getOpcode() == ISD::SETCC)
 806   {
 807     SetCCSDNode* SetCC = dyn_cast<SetCCSDNode>(CC.Val);
 808     if (MVT::isInteger(SetCC->getOperand(0).getValueType())) {
 809       //Dropping the CC is only useful if we are comparing to 0
 810       bool LeftZero = SetCC->getOperand(0).getOpcode() == ISD::Constant &&
 811         cast<ConstantSDNode>(SetCC->getOperand(0))->getValue() == 0;
 812       bool RightZero = SetCC->getOperand(0).getOpcode() == ISD::Constant &&
 813         cast<ConstantSDNode>(SetCC->getOperand(0))->getValue() == 0;
 814       bool isNE = false;
 815
 816       //Fix up CC
 817       ISD::CondCode cCode= SetCC->getCondition();
 818       if (LeftZero && !RightZero) //Swap Operands
 819         cCode = ISD::getSetCCSwappedOperands(cCode);
 820
 821       if(cCode == ISD::SETNE)
 822         isNE = true;
 823
 824       if (LeftZero || RightZero) {
 825         switch (SetCC->getCondition()) {
 826         default: CC.Val->dump(); assert(0 && "Unknown integer comparison!");
 827         case ISD::SETEQ:  Opc = Alpha::BEQ; break;
 828         case ISD::SETLT:  Opc = Alpha::BLT; break;
 829         case ISD::SETLE:  Opc = Alpha::BLE; break;
 830         case ISD::SETGT:  Opc = Alpha::BGT; break;
 831         case ISD::SETGE:  Opc = Alpha::BGE; break;
 832         case ISD::SETULT: assert(0 && "x (unsigned) < 0 is never true"); break;
 833         case ISD::SETUGT: Opc = Alpha::BNE; break;
 834         case ISD::SETULE: Opc = Alpha::BEQ; break; //Technically you could have this CC
 835         case ISD::SETUGE: assert(0 && "x (unsgined >= 0 is always true"); break;
 836         case ISD::SETNE:  Opc = Alpha::BNE; break;
 837         }
 838         unsigned Tmp1;
 839         if(LeftZero && !RightZero) //swap Operands
 840           Tmp1 = SelectExpr(SetCC->getOperand(1)); //Cond
 841         else
 842           Tmp1 = SelectExpr(SetCC->getOperand(0)); //Cond
 843         BuildMI(BB, Opc, 2).addReg(Tmp1).addMBB(Dest);
 844         return;
 845       } else {
 846         unsigned Tmp1 = SelectExpr(CC);
 847         if (isNE)
 848           BuildMI(BB, Alpha::BEQ, 2).addReg(CCInvMap[CC]).addMBB(Dest);
 849         else
 850           BuildMI(BB, Alpha::BNE, 2).addReg(Tmp1).addMBB(Dest);
 851         return;
 852       }
 853     } else { //FP
 854       //Any comparison between 2 values should be codegened as an folded branch, as moving
 855       //CC to the integer register is very expensive
 856       //for a cmp b: c = a - b;
 857       //a = b: c = 0
 858       //a < b: c < 0
 859       //a > b: c > 0
 860
 861       bool invTest = false;
 862       unsigned Tmp3;
 863
 864       ConstantFPSDNode *CN;
 865       if ((CN = dyn_cast<ConstantFPSDNode>(SetCC->getOperand(1)))
 866           && (CN->isExactlyValue(+0.0) || CN->isExactlyValue(-0.0)))
 867         Tmp3 = SelectExpr(SetCC->getOperand(0));
 868       else if ((CN = dyn_cast<ConstantFPSDNode>(SetCC->getOperand(0)))
 869           && (CN->isExactlyValue(+0.0) || CN->isExactlyValue(-0.0)))
 870       {
 871         Tmp3 = SelectExpr(SetCC->getOperand(1));
 872         invTest = true;
 873       }
 874       else
 875       {
 876         unsigned Tmp1 = SelectExpr(SetCC->getOperand(0));
 877         unsigned Tmp2 = SelectExpr(SetCC->getOperand(1));
 878         bool isD = SetCC->getOperand(0).getValueType() == MVT::f64;
 879         Tmp3 = MakeReg(isD ? MVT::f64 : MVT::f32);
 880         BuildMI(BB, isD ? Alpha::SUBT : Alpha::SUBS, 2, Tmp3)
 881           .addReg(Tmp1).addReg(Tmp2);
 882       }
 883
 884       switch (SetCC->getCondition()) {
 885       default: CC.Val->dump(); assert(0 && "Unknown FP comparison!");
 886       case ISD::SETEQ: Opc = invTest ? Alpha::FBNE : Alpha::FBEQ; break;
 887       case ISD::SETLT: Opc = invTest ? Alpha::FBGT : Alpha::FBLT; break;
 888       case ISD::SETLE: Opc = invTest ? Alpha::FBGE : Alpha::FBLE; break;
 889       case ISD::SETGT: Opc = invTest ? Alpha::FBLT : Alpha::FBGT; break;
 890       case ISD::SETGE: Opc = invTest ? Alpha::FBLE : Alpha::FBGE; break;
 891       case ISD::SETNE: Opc = invTest ? Alpha::FBEQ : Alpha::FBNE; break;
 892       }
 893       BuildMI(BB, Opc, 2).addReg(Tmp3).addMBB(Dest);
 894       return;
 895     }
 896     abort(); //Should never be reached
 897   } else {
 898     //Giveup and do the stupid thing
 899     unsigned Tmp1 = SelectExpr(CC);
 900     BuildMI(BB, Alpha::BNE, 2).addReg(Tmp1).addMBB(Dest);
 901     return;
 902   }
 903   abort(); //Should never be reached
 904 }
 905
 906 unsigned ISel::SelectExprFP(SDOperand N, unsigned Result)
 907 {
 908   unsigned Tmp1, Tmp2, Tmp3;
 909   unsigned Opc = 0;
 910   SDNode *Node = N.Val;
 911   MVT::ValueType DestType = N.getValueType();
 912   unsigned opcode = N.getOpcode();
 913
 914   switch (opcode) {
 915   default:
 916     Node->dump();
 917     assert(0 && "Node not handled!\n");
 918
 919   case ISD::UNDEF: {
 920     BuildMI(BB, Alpha::IDEF, 0, Result);
 921     return Result;
 922   }
 923
 924   case ISD::FNEG:
 925     if(ISD::FABS == N.getOperand(0).getOpcode())
 926       {
 927         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
 928         BuildMI(BB, Alpha::CPYSN, 2, Result).addReg(Alpha::F31).addReg(Tmp1);
 929       } else {
 930         Tmp1 = SelectExpr(N.getOperand(0));
 931         BuildMI(BB, Alpha::CPYSN, 2, Result).addReg(Tmp1).addReg(Tmp1);
 932       }
 933     return Result;
 934
 935   case ISD::FABS:
 936     Tmp1 = SelectExpr(N.getOperand(0));
 937     BuildMI(BB, Alpha::CPYS, 2, Result).addReg(Alpha::F31).addReg(Tmp1);
 938     return Result;
 939
 940   case ISD::SELECT:
 941     {
 942       //Tmp1 = SelectExpr(N.getOperand(0)); //Cond
 943       unsigned TV = SelectExpr(N.getOperand(1)); //Use if TRUE
 944       unsigned FV = SelectExpr(N.getOperand(2)); //Use if FALSE
 945
 946       SDOperand CC = N.getOperand(0);
 947       SetCCSDNode* SetCC = dyn_cast<SetCCSDNode>(CC.Val);
 948
 949       if (CC.getOpcode() == ISD::SETCC &&
 950           !MVT::isInteger(SetCC->getOperand(0).getValueType()))
 951       { //FP Setcc -> Select yay!
 952
 953
 954         //for a cmp b: c = a - b;
 955         //a = b: c = 0
 956         //a < b: c < 0
 957         //a > b: c > 0
 958
 959         bool invTest = false;
 960         unsigned Tmp3;
 961
 962         ConstantFPSDNode *CN;
 963         if ((CN = dyn_cast<ConstantFPSDNode>(SetCC->getOperand(1)))
 964             && (CN->isExactlyValue(+0.0) || CN->isExactlyValue(-0.0)))
 965           Tmp3 = SelectExpr(SetCC->getOperand(0));
 966         else if ((CN = dyn_cast<ConstantFPSDNode>(SetCC->getOperand(0)))
 967                  && (CN->isExactlyValue(+0.0) || CN->isExactlyValue(-0.0)))
 968         {
 969           Tmp3 = SelectExpr(SetCC->getOperand(1));
 970           invTest = true;
 971         }
 972         else
 973         {
 974           unsigned Tmp1 = SelectExpr(SetCC->getOperand(0));
 975           unsigned Tmp2 = SelectExpr(SetCC->getOperand(1));
 976           bool isD = SetCC->getOperand(0).getValueType() == MVT::f64;
 977           Tmp3 = MakeReg(isD ? MVT::f64 : MVT::f32);
 978           BuildMI(BB, isD ? Alpha::SUBT : Alpha::SUBS, 2, Tmp3)
 979             .addReg(Tmp1).addReg(Tmp2);
 980         }
 981
 982         switch (SetCC->getCondition()) {
 983         default: CC.Val->dump(); assert(0 && "Unknown FP comparison!");
 984         case ISD::SETEQ: Opc = invTest ? Alpha::FCMOVNE : Alpha::FCMOVEQ; break;
 985         case ISD::SETLT: Opc = invTest ? Alpha::FCMOVGT : Alpha::FCMOVLT; break;
 986         case ISD::SETLE: Opc = invTest ? Alpha::FCMOVGE : Alpha::FCMOVLE; break;
 987         case ISD::SETGT: Opc = invTest ? Alpha::FCMOVLT : Alpha::FCMOVGT; break;
 988         case ISD::SETGE: Opc = invTest ? Alpha::FCMOVLE : Alpha::FCMOVGE; break;
 989         case ISD::SETNE: Opc = invTest ? Alpha::FCMOVEQ : Alpha::FCMOVNE; break;
 990         }
 991         BuildMI(BB, Opc, 3, Result).addReg(FV).addReg(TV).addReg(Tmp3);
 992         return Result;
 993       }
 994       else
 995       {
 996         Tmp1 = SelectExpr(N.getOperand(0)); //Cond
 997         BuildMI(BB, Alpha::FCMOVEQ_INT, 3, Result).addReg(TV).addReg(FV).addReg(Tmp1);
 998 //         // Spill the cond to memory and reload it from there.
 999 //         unsigned Tmp4 = MakeReg(MVT::f64);
1000 //         MoveIntFP(Tmp1, Tmp4, true);
1001 //         //now ideally, we don't have to do anything to the flag...
1002 //         // Get the condition into the zero flag.
1003 //         BuildMI(BB, Alpha::FCMOVEQ, 3, Result).addReg(TV).addReg(FV).addReg(Tmp4);
1004         return Result;
1005       }
1006     }
1007
1008   case ISD::FP_ROUND:
1009     assert (DestType == MVT::f32 &&
1010             N.getOperand(0).getValueType() == MVT::f64 &&
1011             "only f64 to f32 conversion supported here");
1012     Tmp1 = SelectExpr(N.getOperand(0));
1013     BuildMI(BB, Alpha::CVTTS, 1, Result).addReg(Tmp1);
1014     return Result;
1015
1016   case ISD::FP_EXTEND:
1017     assert (DestType == MVT::f64 &&
1018             N.getOperand(0).getValueType() == MVT::f32 &&
1019             "only f32 to f64 conversion supported here");
1020     Tmp1 = SelectExpr(N.getOperand(0));
1021     BuildMI(BB, Alpha::CVTST, 1, Result).addReg(Tmp1);
1022     return Result;
1023
1024   case ISD::CopyFromReg:
1025     {
1026       // Make sure we generate both values.
1027       if (Result != notIn)
1028         ExprMap[N.getValue(1)] = notIn;   // Generate the token
1029       else
1030         Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1031
1032       SDOperand Chain   = N.getOperand(0);
1033
1034       Select(Chain);
1035       unsigned r = dyn_cast<RegSDNode>(Node)->getReg();
1036       //std::cerr << "CopyFromReg " << Result << " = " << r << "\n";
1037       BuildMI(BB, Alpha::CPYS, 2, Result).addReg(r).addReg(r);
1038       return Result;
1039     }
1040
1041   case ISD::LOAD:
1042     {
1043       // Make sure we generate both values.
1044       if (Result != notIn)
1045         ExprMap[N.getValue(1)] = notIn;   // Generate the token
1046       else
1047         Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1048
1049       DestType = N.getValue(0).getValueType();
1050
1051       SDOperand Chain   = N.getOperand(0);
1052       SDOperand Address = N.getOperand(1);
1053       Select(Chain);
1054       Opc = DestType == MVT::f64 ? Alpha::LDT : Alpha::LDS;
1055
1056       if (Address.getOpcode() == ISD::GlobalAddress) {
1057         AlphaLowering.restoreGP(BB);
1058         Opc = GetSymVersion(Opc);
1059         has_sym = true;
1060         BuildMI(BB, Opc, 1, Result).addGlobalAddress(cast<GlobalAddressSDNode>(Address)->getGlobal());
1061       }
1062       else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Address)) {
1063         AlphaLowering.restoreGP(BB);
1064         Opc = GetSymVersion(Opc);
1065         has_sym = true;
1066         BuildMI(BB, Opc, 1, Result).addConstantPoolIndex(CP->getIndex());
1067       }
1068       else if(Address.getOpcode() == ISD::FrameIndex) {
1069         BuildMI(BB, Opc, 2, Result)
1070           .addFrameIndex(cast<FrameIndexSDNode>(Address)->getIndex())
1071           .addReg(Alpha::F31);
1072       } else {
1073         long offset;
1074         SelectAddr(Address, Tmp1, offset);
1075         BuildMI(BB, Opc, 2, Result).addImm(offset).addReg(Tmp1);
1076       }
1077       return Result;
1078     }
1079   case ISD::ConstantFP:
1080     if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N)) {
1081       if (CN->isExactlyValue(+0.0)) {
1082         BuildMI(BB, Alpha::CPYS, 2, Result).addReg(Alpha::F31).addReg(Alpha::F31);
1083       } else if ( CN->isExactlyValue(-0.0)) {
1084         BuildMI(BB, Alpha::CPYSN, 2, Result).addReg(Alpha::F31).addReg(Alpha::F31);
1085       } else {
1086         abort();
1087       }
1088     }
1089     return Result;
1090
1091   case ISD::SDIV:
1092   case ISD::MUL:
1093   case ISD::ADD:
1094   case ISD::SUB:
1095     switch( opcode ) {
1096     case ISD::MUL: Opc = DestType == MVT::f64 ? Alpha::MULT : Alpha::MULS; break;
1097     case ISD::ADD: Opc = DestType == MVT::f64 ? Alpha::ADDT : Alpha::ADDS; break;
1098     case ISD::SUB: Opc = DestType == MVT::f64 ? Alpha::SUBT : Alpha::SUBS; break;
1099     case ISD::SDIV: Opc = DestType == MVT::f64 ? Alpha::DIVT : Alpha::DIVS; break;
1100     };
1101
1102     ConstantFPSDNode *CN;
1103     if (opcode == ISD::SUB
1104         && (CN = dyn_cast<ConstantFPSDNode>(N.getOperand(0)))
1105         && (CN->isExactlyValue(+0.0) || CN->isExactlyValue(-0.0)))
1106     {
1107       Tmp2 = SelectExpr(N.getOperand(1));
1108       BuildMI(BB, Alpha::CPYSN, 2, Result).addReg(Tmp2).addReg(Tmp2);
1109     } else {
1110       Tmp1 = SelectExpr(N.getOperand(0));
1111       Tmp2 = SelectExpr(N.getOperand(1));
1112       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1113     }
1114     return Result;
1115
1116   case ISD::EXTLOAD:
1117     {
1118       //include a conversion sequence for float loads to double
1119       if (Result != notIn)
1120         ExprMap[N.getValue(1)] = notIn;   // Generate the token
1121       else
1122         Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1123
1124       Tmp1 = MakeReg(MVT::f32);
1125
1126       assert(cast<MVTSDNode>(Node)->getExtraValueType() == MVT::f32 &&
1127              "EXTLOAD not from f32");
1128       assert(Node->getValueType(0) == MVT::f64 && "EXTLOAD not to f64");
1129
1130       SDOperand Chain   = N.getOperand(0);
1131       SDOperand Address = N.getOperand(1);
1132       Select(Chain);
1133
1134       if (Address.getOpcode() == ISD::GlobalAddress) {
1135         AlphaLowering.restoreGP(BB);
1136         has_sym = true;
1137         BuildMI(BB, Alpha::LDS_SYM, 1, Tmp1).addGlobalAddress(cast<GlobalAddressSDNode>(Address)->getGlobal());
1138       }
1139       else if (ConstantPoolSDNode *CP =
1140                dyn_cast<ConstantPoolSDNode>(N.getOperand(1)))
1141       {
1142         AlphaLowering.restoreGP(BB);
1143         has_sym = true;
1144         BuildMI(BB, Alpha::LDS_SYM, 1, Tmp1).addConstantPoolIndex(CP->getIndex());
1145       }
1146       else if(Address.getOpcode() == ISD::FrameIndex) {
1147         Tmp2 = cast<FrameIndexSDNode>(Address)->getIndex();
1148         BuildMI(BB, Alpha::LDS, 2, Tmp1)
1149           .addFrameIndex(cast<FrameIndexSDNode>(Address)->getIndex())
1150           .addReg(Alpha::F31);
1151       } else {
1152         long offset;
1153         SelectAddr(Address, Tmp2, offset);
1154         BuildMI(BB, Alpha::LDS, 1, Tmp1).addImm(offset).addReg(Tmp2);
1155       }
1156       BuildMI(BB, Alpha::CVTST, 1, Result).addReg(Tmp1);
1157       return Result;
1158     }
1159
1160   case ISD::UINT_TO_FP:
1161   case ISD::SINT_TO_FP:
1162     {
1163       assert (N.getOperand(0).getValueType() == MVT::i64
1164               && "only quads can be loaded from");
1165       Tmp1 = SelectExpr(N.getOperand(0));  // Get the operand register
1166       Tmp2 = MakeReg(MVT::f64);
1167       MoveInt2FP(Tmp1, Tmp2, true);
1168       Opc = DestType == MVT::f64 ? Alpha::CVTQT : Alpha::CVTQS;
1169       BuildMI(BB, Opc, 1, Result).addReg(Tmp2);
1170       return Result;
1171     }
1172   }
1173   assert(0 && "should not get here");
1174   return 0;
1175 }
1176
1177 unsigned ISel::SelectExpr(SDOperand N) {
1178   unsigned Result;
1179   unsigned Tmp1, Tmp2 = 0, Tmp3;
1180   unsigned Opc = 0;
1181   unsigned opcode = N.getOpcode();
1182
1183   SDNode *Node = N.Val;
1184   MVT::ValueType DestType = N.getValueType();
1185
1186   unsigned &Reg = ExprMap[N];
1187   if (Reg) return Reg;
1188
1189   if (N.getOpcode() != ISD::CALL)
1190     Reg = Result = (N.getValueType() != MVT::Other) ?
1191       MakeReg(N.getValueType()) : notIn;
1192   else {
1193     // If this is a call instruction, make sure to prepare ALL of the result
1194     // values as well as the chain.
1195     if (Node->getNumValues() == 1)
1196       Reg = Result = notIn;  // Void call, just a chain.
1197     else {
1198       Result = MakeReg(Node->getValueType(0));
1199       ExprMap[N.getValue(0)] = Result;
1200       for (unsigned i = 1, e = N.Val->getNumValues()-1; i != e; ++i)
1201         ExprMap[N.getValue(i)] = MakeReg(Node->getValueType(i));
1202       ExprMap[SDOperand(Node, Node->getNumValues()-1)] = notIn;
1203     }
1204   }
1205
1206   if ((DestType == MVT::f64 || DestType == MVT::f32 ||
1207        (
1208         (opcode == ISD::LOAD || opcode == ISD::CopyFromReg ||
1209          opcode == ISD::EXTLOAD) &&
1210         (N.getValue(0).getValueType() == MVT::f32 ||
1211          N.getValue(0).getValueType() == MVT::f64)
1212        ))
1213        && opcode != ISD::CALL
1214       )
1215     return SelectExprFP(N, Result);
1216
1217   switch (opcode) {
1218   default:
1219     Node->dump();
1220     assert(0 && "Node not handled!\n");
1221
1222   case ISD::CTPOP:
1223   case ISD::CTTZ:
1224   case ISD::CTLZ:
1225     Opc = opcode == ISD::CTPOP ? Alpha::CTPOP :
1226     (opcode == ISD::CTTZ ? Alpha::CTTZ : Alpha::CTLZ);
1227     Tmp1 = SelectExpr(N.getOperand(0));
1228     BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
1229     return Result;
1230
1231   case ISD::MULHU:
1232     Tmp1 = SelectExpr(N.getOperand(0));
1233     Tmp2 = SelectExpr(N.getOperand(1));
1234     BuildMI(BB, Alpha::UMULH, 2, Result).addReg(Tmp1).addReg(Tmp2);
1235     return Result;
1236   case ISD::MULHS:
1237     {
1238       //MULHU - Ra<63>*Rb - Rb<63>*Ra
1239       Tmp1 = SelectExpr(N.getOperand(0));
1240       Tmp2 = SelectExpr(N.getOperand(1));
1241       Tmp3 = MakeReg(MVT::i64);
1242       BuildMI(BB, Alpha::UMULH, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
1243       unsigned V1 = MakeReg(MVT::i64);
1244       unsigned V2 = MakeReg(MVT::i64);
1245       BuildMI(BB, Alpha::CMOVGE, 3, V1).addReg(Tmp2).addReg(Alpha::R31).addReg(Tmp1);
1246       BuildMI(BB, Alpha::CMOVGE, 3, V2).addReg(Tmp1).addReg(Alpha::R31).addReg(Tmp2);
1247       unsigned IRes = MakeReg(MVT::i64);
1248       BuildMI(BB, Alpha::SUBQ, 2, IRes).addReg(Tmp3).addReg(V1);
1249       BuildMI(BB, Alpha::SUBQ, 2, Result).addReg(IRes).addReg(V2);
1250       return Result;
1251     }
1252   case ISD::UNDEF: {
1253     BuildMI(BB, Alpha::IDEF, 0, Result);
1254     return Result;
1255   }
1256
1257   case ISD::DYNAMIC_STACKALLOC:
1258     // Generate both result values.
1259     if (Result != notIn)
1260       ExprMap[N.getValue(1)] = notIn;   // Generate the token
1261     else
1262       Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1263
1264     // FIXME: We are currently ignoring the requested alignment for handling
1265     // greater than the stack alignment.  This will need to be revisited at some
1266     // point.  Align = N.getOperand(2);
1267
1268     if (!isa<ConstantSDNode>(N.getOperand(2)) ||
1269         cast<ConstantSDNode>(N.getOperand(2))->getValue() != 0) {
1270       std::cerr << "Cannot allocate stack object with greater alignment than"
1271                 << " the stack alignment yet!";
1272       abort();
1273     }
1274
1275     Select(N.getOperand(0));
1276     if (ConstantSDNode* CN = dyn_cast<ConstantSDNode>(N.getOperand(1)))
1277     {
1278       if (CN->getValue() < 32000)
1279       {
1280         BuildMI(BB, Alpha::LDA, 2, Alpha::R30)
1281           .addImm(-CN->getValue()).addReg(Alpha::R30);
1282       } else {
1283         Tmp1 = SelectExpr(N.getOperand(1));
1284         // Subtract size from stack pointer, thereby allocating some space.
1285         BuildMI(BB, Alpha::SUBQ, 2, Alpha::R30).addReg(Alpha::R30).addReg(Tmp1);
1286       }
1287     } else {
1288       Tmp1 = SelectExpr(N.getOperand(1));
1289       // Subtract size from stack pointer, thereby allocating some space.
1290       BuildMI(BB, Alpha::SUBQ, 2, Alpha::R30).addReg(Alpha::R30).addReg(Tmp1);
1291     }
1292
1293     // Put a pointer to the space into the result register, by copying the stack
1294     // pointer.
1295     BuildMI(BB, Alpha::BIS, 2, Result).addReg(Alpha::R30).addReg(Alpha::R30);
1296     return Result;
1297
1298 //   case ISD::ConstantPool:
1299 //     Tmp1 = cast<ConstantPoolSDNode>(N)->getIndex();
1300 //     AlphaLowering.restoreGP(BB);
1301 //     BuildMI(BB, Alpha::LDQ_SYM, 1, Result).addConstantPoolIndex(Tmp1);
1302 //     return Result;
1303
1304   case ISD::FrameIndex:
1305     BuildMI(BB, Alpha::LDA, 2, Result)
1306       .addFrameIndex(cast<FrameIndexSDNode>(N)->getIndex())
1307       .addReg(Alpha::F31);
1308     return Result;
1309
1310   case ISD::EXTLOAD:
1311   case ISD::ZEXTLOAD:
1312   case ISD::SEXTLOAD:
1313   case ISD::LOAD:
1314     {
1315       // Make sure we generate both values.
1316       if (Result != notIn)
1317         ExprMap[N.getValue(1)] = notIn;   // Generate the token
1318       else
1319         Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1320
1321       SDOperand Chain   = N.getOperand(0);
1322       SDOperand Address = N.getOperand(1);
1323       Select(Chain);
1324
1325       assert(Node->getValueType(0) == MVT::i64 &&
1326              "Unknown type to sign extend to.");
1327       if (opcode == ISD::LOAD)
1328         Opc = Alpha::LDQ;
1329       else
1330         switch (cast<MVTSDNode>(Node)->getExtraValueType()) {
1331         default: Node->dump(); assert(0 && "Bad sign extend!");
1332         case MVT::i32: Opc = Alpha::LDL;
1333           assert(opcode != ISD::ZEXTLOAD && "Not sext"); break;
1334         case MVT::i16: Opc = Alpha::LDWU;
1335           assert(opcode != ISD::SEXTLOAD && "Not zext"); break;
1336         case MVT::i1: //FIXME: Treat i1 as i8 since there are problems otherwise
1337         case MVT::i8: Opc = Alpha::LDBU;
1338           assert(opcode != ISD::SEXTLOAD && "Not zext"); break;
1339         }
1340
1341       if (Address.getOpcode() == ISD::GlobalAddress) {
1342         AlphaLowering.restoreGP(BB);
1343         Opc = GetSymVersion(Opc);
1344         has_sym = true;
1345         BuildMI(BB, Opc, 1, Result).addGlobalAddress(cast<GlobalAddressSDNode>(Address)->getGlobal());
1346       }
1347       else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(Address)) {
1348         AlphaLowering.restoreGP(BB);
1349         Opc = GetSymVersion(Opc);
1350         has_sym = true;
1351         BuildMI(BB, Opc, 1, Result).addConstantPoolIndex(CP->getIndex());
1352       }
1353       else if(Address.getOpcode() == ISD::FrameIndex) {
1354         BuildMI(BB, Opc, 2, Result)
1355           .addFrameIndex(cast<FrameIndexSDNode>(Address)->getIndex())
1356           .addReg(Alpha::F31);
1357       } else {
1358         long offset;
1359         SelectAddr(Address, Tmp1, offset);
1360         BuildMI(BB, Opc, 2, Result).addImm(offset).addReg(Tmp1);
1361       }
1362       return Result;
1363     }
1364
1365   case ISD::GlobalAddress:
1366     AlphaLowering.restoreGP(BB);
1367     has_sym = true;
1368     BuildMI(BB, Alpha::LOAD_ADDR, 1, Result)
1369       .addGlobalAddress(cast<GlobalAddressSDNode>(N)->getGlobal());
1370     return Result;
1371
1372   case ISD::CALL:
1373     {
1374       Select(N.getOperand(0));
1375
1376       // The chain for this call is now lowered.
1377       ExprMap.insert(std::make_pair(N.getValue(Node->getNumValues()-1), notIn));
1378
1379       //grab the arguments
1380       std::vector<unsigned> argvregs;
1381       //assert(Node->getNumOperands() < 8 && "Only 6 args supported");
1382       for(int i = 2, e = Node->getNumOperands(); i < e; ++i)
1383         argvregs.push_back(SelectExpr(N.getOperand(i)));
1384
1385       //in reg args
1386       for(int i = 0, e = std::min(6, (int)argvregs.size()); i < e; ++i)
1387       {
1388         unsigned args_int[] = {Alpha::R16, Alpha::R17, Alpha::R18,
1389                                Alpha::R19, Alpha::R20, Alpha::R21};
1390         unsigned args_float[] = {Alpha::F16, Alpha::F17, Alpha::F18,
1391                                  Alpha::F19, Alpha::F20, Alpha::F21};
1392         switch(N.getOperand(i+2).getValueType()) {
1393         default:
1394           Node->dump();
1395           N.getOperand(i).Val->dump();
1396           std::cerr << "Type for " << i << " is: " <<
1397             N.getOperand(i+2).getValueType() << "\n";
1398           assert(0 && "Unknown value type for call");
1399         case MVT::i1:
1400         case MVT::i8:
1401         case MVT::i16:
1402         case MVT::i32:
1403         case MVT::i64:
1404           BuildMI(BB, Alpha::BIS, 2, args_int[i]).addReg(argvregs[i]).addReg(argvregs[i]);
1405           break;
1406         case MVT::f32:
1407         case MVT::f64:
1408           BuildMI(BB, Alpha::CPYS, 2, args_float[i]).addReg(argvregs[i]).addReg(argvregs[i]);
1409           break;
1410         }
1411       }
1412       //in mem args
1413       for (int i = 6, e = argvregs.size(); i < e; ++i)
1414       {
1415         switch(N.getOperand(i+2).getValueType()) {
1416         default:
1417           Node->dump();
1418           N.getOperand(i).Val->dump();
1419           std::cerr << "Type for " << i << " is: " <<
1420             N.getOperand(i+2).getValueType() << "\n";
1421           assert(0 && "Unknown value type for call");
1422         case MVT::i1:
1423         case MVT::i8:
1424         case MVT::i16:
1425         case MVT::i32:
1426         case MVT::i64:
1427           BuildMI(BB, Alpha::STQ, 3).addReg(argvregs[i]).addImm((i - 6) * 8).addReg(Alpha::R30);
1428           break;
1429         case MVT::f32:
1430           BuildMI(BB, Alpha::STS, 3).addReg(argvregs[i]).addImm((i - 6) * 8).addReg(Alpha::R30);
1431           break;
1432         case MVT::f64:
1433           BuildMI(BB, Alpha::STT, 3).addReg(argvregs[i]).addImm((i - 6) * 8).addReg(Alpha::R30);
1434           break;
1435         }
1436       }
1437       //build the right kind of call
1438       if (GlobalAddressSDNode *GASD =
1439           dyn_cast<GlobalAddressSDNode>(N.getOperand(1)))
1440       {
1441         if (GASD->getGlobal()->isExternal()) {
1442           //use safe calling convention
1443           AlphaLowering.restoreGP(BB);
1444           has_sym = true;
1445           BuildMI(BB, Alpha::CALL, 1).addGlobalAddress(GASD->getGlobal());
1446         } else {
1447           //use PC relative branch call
1448           AlphaLowering.restoreGP(BB);
1449           BuildMI(BB, Alpha::BSR, 1, Alpha::R26).addGlobalAddress(GASD->getGlobal(),true);
1450         }
1451       }
1452       else if (ExternalSymbolSDNode *ESSDN =
1453                dyn_cast<ExternalSymbolSDNode>(N.getOperand(1)))
1454       {
1455         AlphaLowering.restoreGP(BB);
1456         has_sym = true;
1457         BuildMI(BB, Alpha::CALL, 1).addExternalSymbol(ESSDN->getSymbol(), true);
1458       } else {
1459         //no need to restore GP as we are doing an indirect call
1460         Tmp1 = SelectExpr(N.getOperand(1));
1461         BuildMI(BB, Alpha::BIS, 2, Alpha::R27).addReg(Tmp1).addReg(Tmp1);
1462         BuildMI(BB, Alpha::JSR, 2, Alpha::R26).addReg(Alpha::R27).addImm(0);
1463       }
1464
1465       //push the result into a virtual register
1466
1467       switch (Node->getValueType(0)) {
1468       default: Node->dump(); assert(0 && "Unknown value type for call result!");
1469       case MVT::Other: return notIn;
1470       case MVT::i1:
1471       case MVT::i8:
1472       case MVT::i16:
1473       case MVT::i32:
1474       case MVT::i64:
1475         BuildMI(BB, Alpha::BIS, 2, Result).addReg(Alpha::R0).addReg(Alpha::R0);
1476         break;
1477       case MVT::f32:
1478       case MVT::f64:
1479         BuildMI(BB, Alpha::CPYS, 2, Result).addReg(Alpha::F0).addReg(Alpha::F0);
1480         break;
1481       }
1482       return Result+N.ResNo;
1483     }
1484
1485   case ISD::SIGN_EXTEND_INREG:
1486     {
1487       //do SDIV opt for all levels of ints if not dividing by a constant
1488       if (EnableAlphaIDIV && N.getOperand(0).getOpcode() == ISD::SDIV
1489           && N.getOperand(0).getOperand(1).getOpcode() != ISD::Constant)
1490       {
1491         unsigned Tmp4 = MakeReg(MVT::f64);
1492         unsigned Tmp5 = MakeReg(MVT::f64);
1493         unsigned Tmp6 = MakeReg(MVT::f64);
1494         unsigned Tmp7 = MakeReg(MVT::f64);
1495         unsigned Tmp8 = MakeReg(MVT::f64);
1496         unsigned Tmp9 = MakeReg(MVT::f64);
1497
1498         Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1499         Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1500         MoveInt2FP(Tmp1, Tmp4, true);
1501         MoveInt2FP(Tmp2, Tmp5, true);
1502         BuildMI(BB, Alpha::CVTQT, 1, Tmp6).addReg(Tmp4);
1503         BuildMI(BB, Alpha::CVTQT, 1, Tmp7).addReg(Tmp5);
1504         BuildMI(BB, Alpha::DIVT, 2, Tmp8).addReg(Tmp6).addReg(Tmp7);
1505         BuildMI(BB, Alpha::CVTTQ, 1, Tmp9).addReg(Tmp8);
1506         MoveFP2Int(Tmp9, Result, true);
1507         return Result;
1508       }
1509
1510       //Alpha has instructions for a bunch of signed 32 bit stuff
1511       if( dyn_cast<MVTSDNode>(Node)->getExtraValueType() == MVT::i32)
1512       {
1513         switch (N.getOperand(0).getOpcode()) {
1514         case ISD::ADD:
1515         case ISD::SUB:
1516         case ISD::MUL:
1517           {
1518             bool isAdd = N.getOperand(0).getOpcode() == ISD::ADD;
1519             bool isMul = N.getOperand(0).getOpcode() == ISD::MUL;
1520             //FIXME: first check for Scaled Adds and Subs!
1521             ConstantSDNode* CSD = NULL;
1522             if(!isMul && N.getOperand(0).getOperand(0).getOpcode() == ISD::SHL &&
1523                (CSD = dyn_cast<ConstantSDNode>(N.getOperand(0).getOperand(0).getOperand(1))) &&
1524                (CSD->getValue() == 2 || CSD->getValue() == 3))
1525             {
1526               bool use4 = CSD->getValue() == 2;
1527               Tmp1 = SelectExpr(N.getOperand(0).getOperand(0).getOperand(0));
1528               Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1529               BuildMI(BB, isAdd?(use4?Alpha::S4ADDL:Alpha::S8ADDL):(use4?Alpha::S4SUBL:Alpha::S8SUBL),
1530                       2,Result).addReg(Tmp1).addReg(Tmp2);
1531             }
1532             else if(isAdd && N.getOperand(0).getOperand(1).getOpcode() == ISD::SHL &&
1533                     (CSD = dyn_cast<ConstantSDNode>(N.getOperand(0).getOperand(1).getOperand(1))) &&
1534                     (CSD->getValue() == 2 || CSD->getValue() == 3))
1535             {
1536               bool use4 = CSD->getValue() == 2;
1537               Tmp1 = SelectExpr(N.getOperand(0).getOperand(1).getOperand(0));
1538               Tmp2 = SelectExpr(N.getOperand(0).getOperand(0));
1539               BuildMI(BB, use4?Alpha::S4ADDL:Alpha::S8ADDL, 2,Result).addReg(Tmp1).addReg(Tmp2);
1540             }
1541             else if(N.getOperand(0).getOperand(1).getOpcode() == ISD::Constant &&
1542                cast<ConstantSDNode>(N.getOperand(0).getOperand(1))->getValue() <= 255)
1543             { //Normal imm add/sub
1544               Opc = isAdd ? Alpha::ADDLi : (isMul ? Alpha::MULLi : Alpha::SUBLi);
1545               Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1546               Tmp2 = cast<ConstantSDNode>(N.getOperand(0).getOperand(1))->getValue();
1547               BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(Tmp2);
1548             }
1549             else
1550             { //Normal add/sub
1551               Opc = isAdd ? Alpha::ADDL : (isMul ? Alpha::MULL : Alpha::SUBL);
1552               Tmp1 = SelectExpr(N.getOperand(0).getOperand(0));
1553               Tmp2 = SelectExpr(N.getOperand(0).getOperand(1));
1554               BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1555             }
1556             return Result;
1557           }
1558         default: break; //Fall Though;
1559         }
1560       } //Every thing else fall though too, including unhandled opcodes above
1561       Tmp1 = SelectExpr(N.getOperand(0));
1562       MVTSDNode* MVN = dyn_cast<MVTSDNode>(Node);
1563       //std::cerr << "SrcT: " << MVN->getExtraValueType() << "\n";
1564       switch(MVN->getExtraValueType())
1565       {
1566       default:
1567         Node->dump();
1568         assert(0 && "Sign Extend InReg not there yet");
1569         break;
1570       case MVT::i32:
1571         {
1572           BuildMI(BB, Alpha::ADDLi, 2, Result).addReg(Tmp1).addImm(0);
1573           break;
1574         }
1575       case MVT::i16:
1576         BuildMI(BB, Alpha::SEXTW, 1, Result).addReg(Tmp1);
1577         break;
1578       case MVT::i8:
1579         BuildMI(BB, Alpha::SEXTB, 1, Result).addReg(Tmp1);
1580         break;
1581       case MVT::i1:
1582         Tmp2 = MakeReg(MVT::i64);
1583         BuildMI(BB, Alpha::ANDi, 2, Tmp2).addReg(Tmp1).addImm(1);
1584         BuildMI(BB, Alpha::SUBQ, 2, Result).addReg(Alpha::R31).addReg(Tmp2);
1585         break;
1586       }
1587       return Result;
1588     }
1589
1590   case ISD::SETCC:
1591     {
1592       if (SetCCSDNode *SetCC = dyn_cast<SetCCSDNode>(Node)) {
1593         if (MVT::isInteger(SetCC->getOperand(0).getValueType())) {
1594           bool isConst1 = false;
1595           bool isConst2 = false;
1596           int dir;
1597
1598           //Tmp1 = SelectExpr(N.getOperand(0));
1599           if(N.getOperand(0).getOpcode() == ISD::Constant &&
1600              cast<ConstantSDNode>(N.getOperand(0))->getValue() <= 255)
1601             isConst1 = true;
1602           if(N.getOperand(1).getOpcode() == ISD::Constant &&
1603              cast<ConstantSDNode>(N.getOperand(1))->getValue() <= 255)
1604             isConst2 = true;
1605
1606           switch (SetCC->getCondition()) {
1607           default: Node->dump(); assert(0 && "Unknown integer comparison!");
1608           case ISD::SETEQ: Opc = Alpha::CMPEQ; dir=0; break;
1609           case ISD::SETLT:
1610             Opc = isConst2 ? Alpha::CMPLTi : Alpha::CMPLT; dir = 1; break;
1611           case ISD::SETLE:
1612             Opc = isConst2 ? Alpha::CMPLEi : Alpha::CMPLE; dir = 1; break;
1613           case ISD::SETGT:
1614             Opc = isConst1 ? Alpha::CMPLTi : Alpha::CMPLT; dir = 2; break;
1615           case ISD::SETGE:
1616             Opc = isConst1 ? Alpha::CMPLEi : Alpha::CMPLE; dir = 2; break;
1617           case ISD::SETULT:
1618             Opc = isConst2 ? Alpha::CMPULTi : Alpha::CMPULT; dir = 1; break;
1619           case ISD::SETUGT:
1620             Opc = isConst1 ? Alpha::CMPULTi : Alpha::CMPULT; dir = 2; break;
1621           case ISD::SETULE:
1622             Opc = isConst2 ? Alpha::CMPULEi : Alpha::CMPULE; dir = 1; break;
1623           case ISD::SETUGE:
1624             Opc = isConst1 ? Alpha::CMPULEi : Alpha::CMPULE; dir = 2; break;
1625           case ISD::SETNE: {//Handle this one special
1626             //std::cerr << "Alpha does not have a setne.\n";
1627             //abort();
1628             Tmp1 = SelectExpr(N.getOperand(0));
1629             Tmp2 = SelectExpr(N.getOperand(1));
1630             Tmp3 = MakeReg(MVT::i64);
1631             BuildMI(BB, Alpha::CMPEQ, 2, Tmp3).addReg(Tmp1).addReg(Tmp2);
1632             //Remeber we have the Inv for this CC
1633             CCInvMap[N] = Tmp3;
1634             //and invert
1635             BuildMI(BB, Alpha::CMPEQ, 2, Result).addReg(Alpha::R31).addReg(Tmp3);
1636             return Result;
1637           }
1638           }
1639           if (dir == 1) {
1640             Tmp1 = SelectExpr(N.getOperand(0));
1641             if (isConst2) {
1642               Tmp2 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
1643               BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(Tmp2);
1644             } else {
1645               Tmp2 = SelectExpr(N.getOperand(1));
1646               BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1647             }
1648           } else if (dir == 2) {
1649             Tmp1 = SelectExpr(N.getOperand(1));
1650             if (isConst1) {
1651               Tmp2 = cast<ConstantSDNode>(N.getOperand(0))->getValue();
1652               BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(Tmp2);
1653             } else {
1654               Tmp2 = SelectExpr(N.getOperand(0));
1655               BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1656             }
1657           } else { //dir == 0
1658             if (isConst1) {
1659               Tmp1 = cast<ConstantSDNode>(N.getOperand(0))->getValue();
1660               Tmp2 = SelectExpr(N.getOperand(1));
1661               BuildMI(BB, Alpha::CMPEQi, 2, Result).addReg(Tmp2).addImm(Tmp1);
1662             } else if (isConst2) {
1663               Tmp1 = SelectExpr(N.getOperand(0));
1664               Tmp2 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
1665               BuildMI(BB, Alpha::CMPEQi, 2, Result).addReg(Tmp1).addImm(Tmp2);
1666             } else {
1667               Tmp1 = SelectExpr(N.getOperand(0));
1668               Tmp2 = SelectExpr(N.getOperand(1));
1669               BuildMI(BB, Alpha::CMPEQ, 2, Result).addReg(Tmp1).addReg(Tmp2);
1670             }
1671           }
1672         } else {
1673           //do the comparison
1674           Tmp1 = MakeReg(MVT::f64);
1675           bool inv = SelectFPSetCC(N, Tmp1);
1676
1677           //now arrange for Result (int) to have a 1 or 0
1678           Tmp2 = MakeReg(MVT::i64);
1679           BuildMI(BB, Alpha::ADDQi, 2, Tmp2).addReg(Alpha::R31).addImm(1);
1680           Opc = inv?Alpha::CMOVNEi_FP:Alpha::CMOVEQi_FP;
1681           BuildMI(BB, Opc, 3, Result).addReg(Tmp2).addImm(0).addReg(Tmp1);
1682         }
1683       }
1684       return Result;
1685     }
1686
1687   case ISD::CopyFromReg:
1688     {
1689       ++count_ins;
1690
1691       // Make sure we generate both values.
1692       if (Result != notIn)
1693         ExprMap[N.getValue(1)] = notIn;   // Generate the token
1694       else
1695         Result = ExprMap[N.getValue(0)] = MakeReg(N.getValue(0).getValueType());
1696
1697       SDOperand Chain   = N.getOperand(0);
1698
1699       Select(Chain);
1700       unsigned r = dyn_cast<RegSDNode>(Node)->getReg();
1701       //std::cerr << "CopyFromReg " << Result << " = " << r << "\n";
1702       BuildMI(BB, Alpha::BIS, 2, Result).addReg(r).addReg(r);
1703       return Result;
1704     }
1705
1706     //Most of the plain arithmetic and logic share the same form, and the same
1707     //constant immediate test
1708   case ISD::XOR:
1709     //Match Not
1710     if (N.getOperand(1).getOpcode() == ISD::Constant &&
1711         cast<ConstantSDNode>(N.getOperand(1))->getSignExtended() == -1)
1712       {
1713         Tmp1 = SelectExpr(N.getOperand(0));
1714         BuildMI(BB, Alpha::ORNOT, 2, Result).addReg(Alpha::R31).addReg(Tmp1);
1715         return Result;
1716       }
1717     //Fall through
1718   case ISD::AND:
1719     //handle zap
1720     if (opcode == ISD::AND && N.getOperand(1).getOpcode() == ISD::Constant)
1721     {
1722       uint64_t k = cast<ConstantSDNode>(N.getOperand(1))->getValue();
1723       unsigned int build = 0;
1724       for(int i = 0; i < 8; ++i)
1725       {
1726         if ((k & 0x00FF) == 0x00FF)
1727           build |= 1 << i;
1728         else if ((k & 0x00FF) != 0)
1729         { build = 0; break; }
1730         k >>= 8;
1731       }
1732       if (build)
1733       {
1734         Tmp1 = SelectExpr(N.getOperand(0));
1735         BuildMI(BB, Alpha::ZAPNOTi, 2, Result).addReg(Tmp1).addImm(build);
1736         return Result;
1737       }
1738     }
1739   case ISD::OR:
1740     //Check operand(0) == Not
1741     if (N.getOperand(0).getOpcode() == ISD::XOR &&
1742         N.getOperand(0).getOperand(1).getOpcode() == ISD::Constant &&
1743         cast<ConstantSDNode>(N.getOperand(0).getOperand(1))->getSignExtended() == -1)
1744       {
1745         switch(opcode) {
1746         case ISD::AND: Opc = Alpha::BIC; break;
1747         case ISD::OR:  Opc = Alpha::ORNOT; break;
1748         case ISD::XOR: Opc = Alpha::EQV; break;
1749         }
1750         Tmp1 = SelectExpr(N.getOperand(1));
1751         Tmp2 = SelectExpr(N.getOperand(0).getOperand(0));
1752         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1753         return Result;
1754       }
1755     //Check operand(1) == Not
1756     if (N.getOperand(1).getOpcode() == ISD::XOR &&
1757         N.getOperand(1).getOperand(1).getOpcode() == ISD::Constant &&
1758         cast<ConstantSDNode>(N.getOperand(1).getOperand(1))->getSignExtended() == -1)
1759       {
1760         switch(opcode) {
1761         case ISD::AND: Opc = Alpha::BIC; break;
1762         case ISD::OR:  Opc = Alpha::ORNOT; break;
1763         case ISD::XOR: Opc = Alpha::EQV; break;
1764         }
1765         Tmp1 = SelectExpr(N.getOperand(0));
1766         Tmp2 = SelectExpr(N.getOperand(1).getOperand(0));
1767         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1768         return Result;
1769       }
1770     //Fall through
1771   case ISD::SHL:
1772   case ISD::SRL:
1773   case ISD::SRA:
1774   case ISD::MUL:
1775     assert (DestType == MVT::i64 && "Only do arithmetic on i64s!");
1776     if(N.getOperand(1).getOpcode() == ISD::Constant &&
1777        cast<ConstantSDNode>(N.getOperand(1))->getValue() <= 255)
1778     {
1779       switch(opcode) {
1780       case ISD::AND: Opc = Alpha::ANDi; break;
1781       case ISD::OR:  Opc = Alpha::BISi; break;
1782       case ISD::XOR: Opc = Alpha::XORi; break;
1783       case ISD::SHL: Opc = Alpha::SLi; break;
1784       case ISD::SRL: Opc = Alpha::SRLi; break;
1785       case ISD::SRA: Opc = Alpha::SRAi; break;
1786       case ISD::MUL: Opc = Alpha::MULQi; break;
1787       };
1788       Tmp1 = SelectExpr(N.getOperand(0));
1789       Tmp2 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
1790       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(Tmp2);
1791     } else {
1792       switch(opcode) {
1793       case ISD::AND: Opc = Alpha::AND; break;
1794       case ISD::OR:  Opc = Alpha::BIS; break;
1795       case ISD::XOR: Opc = Alpha::XOR; break;
1796       case ISD::SHL: Opc = Alpha::SL; break;
1797       case ISD::SRL: Opc = Alpha::SRL; break;
1798       case ISD::SRA: Opc = Alpha::SRA; break;
1799       case ISD::MUL: Opc = Alpha::MULQ; break;
1800       };
1801       Tmp1 = SelectExpr(N.getOperand(0));
1802       Tmp2 = SelectExpr(N.getOperand(1));
1803       BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1804     }
1805     return Result;
1806
1807   case ISD::ADD:
1808   case ISD::SUB:
1809     {
1810       bool isAdd = opcode == ISD::ADD;
1811
1812       //first check for Scaled Adds and Subs!
1813       //Valid for add and sub
1814       ConstantSDNode* CSD = NULL;
1815       if(N.getOperand(0).getOpcode() == ISD::SHL &&
1816          (CSD = dyn_cast<ConstantSDNode>(N.getOperand(0).getOperand(1))) &&
1817          (CSD->getValue() == 2 || CSD->getValue() == 3))
1818       {
1819         bool use4 = CSD->getValue() == 2;
1820         Tmp2 = SelectExpr(N.getOperand(0).getOperand(0));
1821         if ((CSD = dyn_cast<ConstantSDNode>(N.getOperand(1))) && CSD->getValue() <= 255)
1822           BuildMI(BB, isAdd?(use4?Alpha::S4ADDQi:Alpha::S8ADDQi):(use4?Alpha::S4SUBQi:Alpha::S8SUBQi),
1823                   2, Result).addReg(Tmp2).addImm(CSD->getValue());
1824         else {
1825           Tmp1 = SelectExpr(N.getOperand(1));
1826           BuildMI(BB, isAdd?(use4?Alpha::S4ADDQi:Alpha::S8ADDQi):(use4?Alpha::S4SUBQi:Alpha::S8SUBQi),
1827                   2, Result).addReg(Tmp2).addReg(Tmp1);
1828         }
1829       }
1830       //Position prevents subs
1831       else if(N.getOperand(1).getOpcode() == ISD::SHL && isAdd &&
1832               (CSD = dyn_cast<ConstantSDNode>(N.getOperand(1).getOperand(1))) &&
1833               (CSD->getValue() == 2 || CSD->getValue() == 3))
1834       {
1835         bool use4 = CSD->getValue() == 2;
1836         Tmp2 = SelectExpr(N.getOperand(1).getOperand(0));
1837         if ((CSD = dyn_cast<ConstantSDNode>(N.getOperand(0))) && CSD->getValue() <= 255)
1838           BuildMI(BB, use4?Alpha::S4ADDQi:Alpha::S8ADDQi, 2, Result).addReg(Tmp2)
1839             .addImm(CSD->getValue());
1840         else {
1841           Tmp1 = SelectExpr(N.getOperand(0));
1842           BuildMI(BB, use4?Alpha::S4ADDQ:Alpha::S8ADDQ, 2, Result).addReg(Tmp2).addReg(Tmp1);
1843         }
1844       }
1845       //small addi
1846       else if((CSD = dyn_cast<ConstantSDNode>(N.getOperand(1))) &&
1847               CSD->getValue() <= 255)
1848       { //Normal imm add/sub
1849         Opc = isAdd ? Alpha::ADDQi : Alpha::SUBQi;
1850         Tmp1 = SelectExpr(N.getOperand(0));
1851         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addImm(CSD->getValue());
1852       }
1853       //larger addi
1854       else if((CSD = dyn_cast<ConstantSDNode>(N.getOperand(1))) &&
1855               CSD->getSignExtended() <= 32767 &&
1856               CSD->getSignExtended() >= -32767)
1857       { //LDA
1858         Tmp1 = SelectExpr(N.getOperand(0));
1859         Tmp2 = (long)CSD->getSignExtended();
1860         if (!isAdd)
1861           Tmp2 = -Tmp2;
1862         BuildMI(BB, Alpha::LDA, 2, Result).addImm(Tmp2).addReg(Tmp1);
1863       }
1864       //give up and do the operation
1865       else {
1866         //Normal add/sub
1867         Opc = isAdd ? Alpha::ADDQ : Alpha::SUBQ;
1868         Tmp1 = SelectExpr(N.getOperand(0));
1869         Tmp2 = SelectExpr(N.getOperand(1));
1870         BuildMI(BB, Opc, 2, Result).addReg(Tmp1).addReg(Tmp2);
1871       }
1872       return Result;
1873     }
1874
1875   case ISD::SDIV:
1876     {
1877       ConstantSDNode* CSD;
1878       //check if we can convert into a shift!
1879       if ((CSD = dyn_cast<ConstantSDNode>(N.getOperand(1).Val)) &&
1880           (int64_t)CSD->getSignExtended() != 0 &&
1881           ExactLog2(abs((int64_t)CSD->getSignExtended())) != 0)
1882       {
1883         unsigned k = ExactLog2(abs(CSD->getSignExtended()));
1884         Tmp1 = SelectExpr(N.getOperand(0));
1885         if (k == 1)
1886           Tmp2 = Tmp1;
1887         else
1888         {
1889           Tmp2 = MakeReg(MVT::i64);
1890           BuildMI(BB, Alpha::SRAi, 2, Tmp2).addReg(Tmp1).addImm(k - 1);
1891         }
1892         Tmp3 = MakeReg(MVT::i64);
1893         BuildMI(BB, Alpha::SRLi, 2, Tmp3).addReg(Tmp2).addImm(64-k);
1894         unsigned Tmp4 = MakeReg(MVT::i64);
1895         BuildMI(BB, Alpha::ADDQ, 2, Tmp4).addReg(Tmp3).addReg(Tmp1);
1896         if ((int64_t)CSD->getSignExtended() > 0)
1897           BuildMI(BB, Alpha::SRAi, 2, Result).addReg(Tmp4).addImm(k);
1898         else
1899         {
1900           unsigned Tmp5 = MakeReg(MVT::i64);
1901           BuildMI(BB, Alpha::SRAi, 2, Tmp5).addReg(Tmp4).addImm(k);
1902           BuildMI(BB, Alpha::SUBQ, 2, Result).addReg(Alpha::R31).addReg(Tmp5);
1903         }
1904         return Result;
1905       }
1906     }
1907     //Else fall through
1908
1909   case ISD::UDIV:
1910     {
1911       ConstantSDNode* CSD;
1912       if ((CSD = dyn_cast<ConstantSDNode>(N.getOperand(1).Val)) &&
1913           ((int64_t)CSD->getSignExtended() >= 2 ||
1914            (int64_t)CSD->getSignExtended() <= -2))
1915       {
1916         // If this is a divide by constant, we can emit code using some magic
1917         // constants to implement it as a multiply instead.
1918         ExprMap.erase(N);
1919         if (opcode == ISD::SDIV)
1920           return SelectExpr(BuildSDIVSequence(N));
1921         else
1922           return SelectExpr(BuildUDIVSequence(N));
1923       }
1924     }
1925     //else fall though
1926   case ISD::UREM:
1927   case ISD::SREM:
1928     //FIXME: alpha really doesn't support any of these operations,
1929     // the ops are expanded into special library calls with
1930     // special calling conventions
1931     //Restore GP because it is a call after all...
1932     switch(opcode) {
1933     case ISD::UREM: Opc = Alpha::REMQU; break;
1934     case ISD::SREM: Opc = Alpha::REMQ; break;
1935     case ISD::UDIV: Opc = Alpha::DIVQU; break;
1936     case ISD::SDIV: Opc = Alpha::DIVQ; break;
1937     }
1938     Tmp1 = SelectExpr(N.getOperand(0));
1939     Tmp2 = SelectExpr(N.getOperand(1));
1940     //set up regs explicitly (helps Reg alloc)
1941     BuildMI(BB, Alpha::BIS, 2, Alpha::R24).addReg(Tmp1).addReg(Tmp1);
1942     BuildMI(BB, Alpha::BIS, 2, Alpha::R25).addReg(Tmp2).addReg(Tmp2);
1943     AlphaLowering.restoreGP(BB);
1944     BuildMI(BB, Opc, 2).addReg(Alpha::R24).addReg(Alpha::R25);
1945     BuildMI(BB, Alpha::BIS, 2, Result).addReg(Alpha::R27).addReg(Alpha::R27);
1946     return Result;
1947
1948   case ISD::FP_TO_UINT:
1949   case ISD::FP_TO_SINT:
1950     {
1951       assert (DestType == MVT::i64 && "only quads can be loaded to");
1952       MVT::ValueType SrcType = N.getOperand(0).getValueType();
1953       assert (SrcType == MVT::f32 || SrcType == MVT::f64);
1954       Tmp1 = SelectExpr(N.getOperand(0));  // Get the operand register
1955       if (SrcType == MVT::f32)
1956         {
1957           Tmp2 = MakeReg(MVT::f64);
1958           BuildMI(BB, Alpha::CVTST, 1, Tmp2).addReg(Tmp1);
1959           Tmp1 = Tmp2;
1960         }
1961       Tmp2 = MakeReg(MVT::f64);
1962       BuildMI(BB, Alpha::CVTTQ, 1, Tmp2).addReg(Tmp1);
1963       MoveFP2Int(Tmp2, Result, true);
1964
1965       return Result;
1966     }
1967
1968   case ISD::SELECT:
1969     {
1970       //FIXME: look at parent to decide if intCC can be folded, or if setCC(FP) and can save stack use
1971       //Tmp1 = SelectExpr(N.getOperand(0)); //Cond
1972       //Tmp2 = SelectExpr(N.getOperand(1)); //Use if TRUE
1973       //Tmp3 = SelectExpr(N.getOperand(2)); //Use if FALSE
1974       // Get the condition into the zero flag.
1975       //BuildMI(BB, Alpha::CMOVEQ, 2, Result).addReg(Tmp2).addReg(Tmp3).addReg(Tmp1);
1976
1977       SDOperand CC = N.getOperand(0);
1978       SetCCSDNode* SetCC = dyn_cast<SetCCSDNode>(CC.Val);
1979
1980       if (CC.getOpcode() == ISD::SETCC &&
1981           !MVT::isInteger(SetCC->getOperand(0).getValueType()))
1982       { //FP Setcc -> Int Select
1983         Tmp1 = MakeReg(MVT::f64);
1984         Tmp2 = SelectExpr(N.getOperand(1)); //Use if TRUE
1985         Tmp3 = SelectExpr(N.getOperand(2)); //Use if FALSE
1986         bool inv = SelectFPSetCC(CC, Tmp1);
1987         BuildMI(BB, inv?Alpha::CMOVNE_FP:Alpha::CMOVEQ_FP, 2, Result)
1988           .addReg(Tmp2).addReg(Tmp3).addReg(Tmp1);
1989         return Result;
1990       }
1991       if (CC.getOpcode() == ISD::SETCC) {
1992         //Int SetCC -> Select
1993         //Dropping the CC is only useful if we are comparing to 0
1994         if((SetCC->getOperand(1).getOpcode() == ISD::Constant &&
1995            cast<ConstantSDNode>(SetCC->getOperand(1))->getValue() == 0) ||
1996            (SetCC->getOperand(0).getOpcode() == ISD::Constant &&
1997             cast<ConstantSDNode>(SetCC->getOperand(0))->getValue() == 0))
1998         {
1999           //figure out a few things
2000           bool LeftZero = SetCC->getOperand(0).getOpcode() == ISD::Constant &&
2001             cast<ConstantSDNode>(SetCC->getOperand(0))->getValue() == 0;
2002           bool RightZero = SetCC->getOperand(0).getOpcode() == ISD::Constant &&
2003             cast<ConstantSDNode>(SetCC->getOperand(0))->getValue() == 0;
2004           bool LeftConst = N.getOperand(1).getOpcode() == ISD::Constant &&
2005             cast<ConstantSDNode>(N.getOperand(1))->getValue() <= 255;
2006           bool RightConst = N.getOperand(2).getOpcode() == ISD::Constant &&
2007             cast<ConstantSDNode>(N.getOperand(2))->getValue() <= 255;
2008           bool useImm = LeftConst || RightConst;
2009
2010           //Fix up CC
2011           ISD::CondCode cCode= SetCC->getCondition();
2012           if (RightConst && !LeftConst) //Invert sense to get Imm field right
2013             cCode = ISD::getSetCCInverse(cCode, true);
2014           if (LeftZero && !RightZero) //Swap Operands
2015             cCode = ISD::getSetCCSwappedOperands(cCode);
2016
2017           //Choose the CMOV
2018           switch (cCode) {
2019           default: CC.Val->dump(); assert(0 && "Unknown integer comparison!");
2020           case ISD::SETEQ:  Opc = useImm?Alpha::CMOVEQi:Alpha::CMOVEQ;      break;
2021           case ISD::SETLT:  Opc = useImm?Alpha::CMOVLTi:Alpha::CMOVLT;      break;
2022           case ISD::SETLE:  Opc = useImm?Alpha::CMOVLEi:Alpha::CMOVLE;      break;
2023           case ISD::SETGT:  Opc = useImm?Alpha::CMOVGTi:Alpha::CMOVGT;      break;
2024           case ISD::SETGE:  Opc = useImm?Alpha::CMOVGEi:Alpha::CMOVGE;      break;
2025           case ISD::SETULT: assert(0 && "x (unsigned) < 0 is never true");  break;
2026           case ISD::SETUGT: Opc = useImm?Alpha::CMOVNEi:Alpha::CMOVNE;      break;
2027           case ISD::SETULE: Opc = useImm?Alpha::CMOVEQi:Alpha::CMOVEQ;      break; //Technically you could have this CC
2028           case ISD::SETUGE: assert(0 && "x (unsgined >= 0 is always true"); break;
2029           case ISD::SETNE:  Opc = useImm?Alpha::CMOVNEi:Alpha::CMOVNE;      break;
2030           }
2031           if(LeftZero && !RightZero) //swap Operands
2032             Tmp1 = SelectExpr(SetCC->getOperand(1)); //Cond
2033           else
2034             Tmp1 = SelectExpr(SetCC->getOperand(0)); //Cond
2035
2036           if (LeftConst) {
2037             Tmp3 = SelectExpr(N.getOperand(2)); //Use if FALSE
2038             BuildMI(BB, Opc, 2, Result).addReg(Tmp3)
2039                 .addImm(cast<ConstantSDNode>(N.getOperand(1))->getValue())
2040                 .addReg(Tmp1);
2041           } else if (RightConst) {
2042             Tmp3 = SelectExpr(N.getOperand(1)); //Use if FALSE
2043             BuildMI(BB, Opc, 2, Result).addReg(Tmp3)
2044                 .addImm(cast<ConstantSDNode>(N.getOperand(2))->getValue())
2045                 .addReg(Tmp1);
2046           } else {
2047             Tmp2 = SelectExpr(N.getOperand(1)); //Use if TRUE
2048             Tmp3 = SelectExpr(N.getOperand(2)); //Use if FALSE
2049             BuildMI(BB, Opc, 2, Result).addReg(Tmp3).addReg(Tmp2).addReg(Tmp1);
2050           }
2051           return Result;
2052         }
2053         //Otherwise, fall though
2054       }
2055       Tmp1 = SelectExpr(N.getOperand(0)); //Cond
2056       Tmp2 = SelectExpr(N.getOperand(1)); //Use if TRUE
2057       Tmp3 = SelectExpr(N.getOperand(2)); //Use if FALSE
2058       BuildMI(BB, Alpha::CMOVEQ, 2, Result).addReg(Tmp2).addReg(Tmp3).addReg(Tmp1);
2059
2060       return Result;
2061     }
2062
2063   case ISD::Constant:
2064     {
2065       int64_t val = (int64_t)cast<ConstantSDNode>(N)->getValue();
2066       if (val <= IMM_HIGH && val >= IMM_LOW) {
2067         BuildMI(BB, Alpha::LDA, 2, Result).addImm(val).addReg(Alpha::R31);
2068       }
2069       else if (val <= (int64_t)IMM_HIGH +(int64_t)IMM_HIGH* (int64_t)IMM_MULT &&
2070                val >= (int64_t)IMM_LOW + (int64_t)IMM_LOW * (int64_t)IMM_MULT) {
2071         Tmp1 = MakeReg(MVT::i64);
2072         BuildMI(BB, Alpha::LDAH, 2, Tmp1).addImm(getUpper16(val)).addReg(Alpha::R31);
2073         BuildMI(BB, Alpha::LDA, 2, Result).addImm(getLower16(val)).addReg(Tmp1);
2074       }
2075       else {
2076         MachineConstantPool *CP = BB->getParent()->getConstantPool();
2077         ConstantUInt *C = ConstantUInt::get(Type::getPrimitiveType(Type::ULongTyID) , val);
2078         unsigned CPI = CP->getConstantPoolIndex(C);
2079         AlphaLowering.restoreGP(BB);
2080         BuildMI(BB, Alpha::LDQ_SYM, 1, Result).addConstantPoolIndex(CPI);
2081       }
2082       return Result;
2083     }
2084   }
2085
2086   return 0;
2087 }
2088
2089 void ISel::Select(SDOperand N) {
2090   unsigned Tmp1, Tmp2, Opc;
2091   unsigned opcode = N.getOpcode();
2092
2093   if (!ExprMap.insert(std::make_pair(N, notIn)).second)
2094     return;  // Already selected.
2095
2096   SDNode *Node = N.Val;
2097
2098   switch (opcode) {
2099
2100   default:
2101     Node->dump(); std::cerr << "\n";
2102     assert(0 && "Node not handled yet!");
2103
2104   case ISD::BRCOND: {
2105     SelectBranchCC(N);
2106     return;
2107   }
2108
2109   case ISD::BR: {
2110     MachineBasicBlock *Dest =
2111       cast<BasicBlockSDNode>(N.getOperand(1))->getBasicBlock();
2112
2113     Select(N.getOperand(0));
2114     BuildMI(BB, Alpha::BR, 1, Alpha::R31).addMBB(Dest);
2115     return;
2116   }
2117
2118   case ISD::ImplicitDef:
2119     ++count_ins;
2120     Select(N.getOperand(0));
2121     BuildMI(BB, Alpha::IDEF, 0, cast<RegSDNode>(N)->getReg());
2122     return;
2123
2124   case ISD::EntryToken: return;  // Noop
2125
2126   case ISD::TokenFactor:
2127     for (unsigned i = 0, e = Node->getNumOperands(); i != e; ++i)
2128       Select(Node->getOperand(i));
2129
2130     //N.Val->dump(); std::cerr << "\n";
2131     //assert(0 && "Node not handled yet!");
2132
2133     return;
2134
2135   case ISD::CopyToReg:
2136     ++count_outs;
2137     Select(N.getOperand(0));
2138     Tmp1 = SelectExpr(N.getOperand(1));
2139     Tmp2 = cast<RegSDNode>(N)->getReg();
2140
2141     if (Tmp1 != Tmp2) {
2142       if (N.getOperand(1).getValueType() == MVT::f64 ||
2143           N.getOperand(1).getValueType() == MVT::f32)
2144         BuildMI(BB, Alpha::CPYS, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
2145       else
2146         BuildMI(BB, Alpha::BIS, 2, Tmp2).addReg(Tmp1).addReg(Tmp1);
2147     }
2148     return;
2149
2150   case ISD::RET:
2151     ++count_outs;
2152     switch (N.getNumOperands()) {
2153     default:
2154       std::cerr << N.getNumOperands() << "\n";
2155       for (unsigned i = 0; i < N.getNumOperands(); ++i)
2156         std::cerr << N.getOperand(i).getValueType() << "\n";
2157       Node->dump();
2158       assert(0 && "Unknown return instruction!");
2159     case 2:
2160       Select(N.getOperand(0));
2161       Tmp1 = SelectExpr(N.getOperand(1));
2162       switch (N.getOperand(1).getValueType()) {
2163       default: Node->dump();
2164         assert(0 && "All other types should have been promoted!!");
2165       case MVT::f64:
2166       case MVT::f32:
2167         BuildMI(BB, Alpha::CPYS, 2, Alpha::F0).addReg(Tmp1).addReg(Tmp1);
2168         break;
2169       case MVT::i32:
2170       case MVT::i64:
2171         BuildMI(BB, Alpha::BIS, 2, Alpha::R0).addReg(Tmp1).addReg(Tmp1);
2172         break;
2173       }
2174       break;
2175     case 1:
2176       Select(N.getOperand(0));
2177       break;
2178     }
2179     //Tmp2 = AlphaLowering.getRetAddr();
2180     //BuildMI(BB, Alpha::BIS, 2, Alpha::R26).addReg(Tmp2).addReg(Tmp2);
2181     BuildMI(BB, Alpha::RETURN, 0); // Just emit a 'ret' instruction
2182     return;
2183
2184   case ISD::TRUNCSTORE:
2185   case ISD::STORE:
2186     {
2187       SDOperand Chain   = N.getOperand(0);
2188       SDOperand Value = N.getOperand(1);
2189       SDOperand Address = N.getOperand(2);
2190       Select(Chain);
2191
2192       Tmp1 = SelectExpr(Value); //value
2193
2194       if (opcode == ISD::STORE) {
2195         switch(Value.getValueType()) {
2196         default: assert(0 && "unknown Type in store");
2197         case MVT::i64: Opc = Alpha::STQ; break;
2198         case MVT::f64: Opc = Alpha::STT; break;
2199         case MVT::f32: Opc = Alpha::STS; break;
2200         }
2201       } else { //ISD::TRUNCSTORE
2202         switch(cast<MVTSDNode>(Node)->getExtraValueType()) {
2203         default: assert(0 && "unknown Type in store");
2204         case MVT::i1: //FIXME: DAG does not promote this load
2205         case MVT::i8: Opc = Alpha::STB; break;
2206         case MVT::i16: Opc = Alpha::STW; break;
2207         case MVT::i32: Opc = Alpha::STL; break;
2208         }
2209       }
2210
2211       if (Address.getOpcode() == ISD::GlobalAddress)
2212       {
2213         AlphaLowering.restoreGP(BB);
2214         Opc = GetSymVersion(Opc);
2215         has_sym = true;
2216         BuildMI(BB, Opc, 2).addReg(Tmp1).addGlobalAddress(cast<GlobalAddressSDNode>(Address)->getGlobal());
2217       }
2218       else if(Address.getOpcode() == ISD::FrameIndex)
2219       {
2220         BuildMI(BB, Opc, 3).addReg(Tmp1)
2221           .addFrameIndex(cast<FrameIndexSDNode>(Address)->getIndex())
2222           .addReg(Alpha::F31);
2223       }
2224       else
2225       {
2226         long offset;
2227         SelectAddr(Address, Tmp2, offset);
2228         BuildMI(BB, Opc, 3).addReg(Tmp1).addImm(offset).addReg(Tmp2);
2229       }
2230       return;
2231     }
2232
2233   case ISD::EXTLOAD:
2234   case ISD::SEXTLOAD:
2235   case ISD::ZEXTLOAD:
2236   case ISD::LOAD:
2237   case ISD::CopyFromReg:
2238   case ISD::CALL:
2239   case ISD::DYNAMIC_STACKALLOC:
2240     ExprMap.erase(N);
2241     SelectExpr(N);
2242     return;
2243
2244   case ISD::ADJCALLSTACKDOWN:
2245   case ISD::ADJCALLSTACKUP:
2246     Select(N.getOperand(0));
2247     Tmp1 = cast<ConstantSDNode>(N.getOperand(1))->getValue();
2248
2249     Opc = N.getOpcode() == ISD::ADJCALLSTACKDOWN ? Alpha::ADJUSTSTACKDOWN :
2250       Alpha::ADJUSTSTACKUP;
2251     BuildMI(BB, Opc, 1).addImm(Tmp1);
2252     return;
2253
2254   case ISD::PCMARKER:
2255     Select(N.getOperand(0)); //Chain
2256     BuildMI(BB, Alpha::PCLABEL, 2).addImm( cast<ConstantSDNode>(N.getOperand(1))->getValue());
2257     return;
2258   }
2259   assert(0 && "Should not be reached!");
2260 }
2261
2262
2263 /// createAlphaPatternInstructionSelector - This pass converts an LLVM function
2264 /// into a machine code representation using pattern matching and a machine
2265 /// description file.
2266 ///
2267 FunctionPass *llvm::createAlphaPatternInstructionSelector(TargetMachine &TM) {
2268   return new ISel(TM);
2269 }
2270