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