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