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