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