fix typo
[oota-llvm.git] / 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