lib/Target/Alpha/AlphaISelDAGToDAG.cpp

   1 //===-- AlphaISelDAGToDAG.cpp - Alpha pattern matching inst selector ------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Andrew Lenharth 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 // converting from a legalized dag to a Alpha dag.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "Alpha.h"
  16 #include "AlphaTargetMachine.h"
  17 #include "AlphaISelLowering.h"
  18 #include "llvm/CodeGen/MachineInstrBuilder.h"
  19 #include "llvm/CodeGen/MachineFrameInfo.h"
  20 #include "llvm/CodeGen/MachineFunction.h"
  21 #include "llvm/CodeGen/SSARegMap.h"
  22 #include "llvm/CodeGen/SelectionDAG.h"
  23 #include "llvm/CodeGen/SelectionDAGISel.h"
  24 #include "llvm/Target/TargetOptions.h"
  25 #include "llvm/ADT/Statistic.h"
  26 #include "llvm/Constants.h"
  27 #include "llvm/GlobalValue.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/Support/MathExtras.h"
  30 #include <algorithm>
  31 using namespace llvm;
  32
  33 namespace {
  34
  35   //===--------------------------------------------------------------------===//
  36   /// AlphaDAGToDAGISel - Alpha specific code to select Alpha machine
  37   /// instructions for SelectionDAG operations.
  38   class AlphaDAGToDAGISel : public SelectionDAGISel {
  39     AlphaTargetLowering AlphaLowering;
  40
  41     static const int IMM_LOW  = -32768;
  42     static const int IMM_HIGH = 32767;
  43     static const int IMM_MULT = 65536;
  44
  45   public:
  46     AlphaDAGToDAGISel(TargetMachine &TM)
  47       : SelectionDAGISel(AlphaLowering), AlphaLowering(TM) {}
  48
  49     /// getI64Imm - Return a target constant with the specified value, of type
  50     /// i64.
  51     inline SDOperand getI64Imm(int64_t Imm) {
  52       return CurDAG->getTargetConstant(Imm, MVT::i64);
  53     }
  54
  55     // Select - Convert the specified operand from a target-independent to a
  56     // target-specific node if it hasn't already been changed.
  57     SDOperand Select(SDOperand Op);
  58
  59     /// InstructionSelectBasicBlock - This callback is invoked by
  60     /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
  61     virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
  62
  63     virtual const char *getPassName() const {
  64       return "Alpha DAG->DAG Pattern Instruction Selection";
  65     }
  66
  67 // Include the pieces autogenerated from the target description.
  68 #include "AlphaGenDAGISel.inc"
  69
  70 private:
  71     SDOperand getGlobalBaseReg();
  72     SDOperand getRASaveReg();
  73     SDOperand SelectCALL(SDOperand Op);
  74
  75   };
  76 }
  77
  78 /// getGlobalBaseReg - Output the instructions required to put the
  79 /// GOT address into a register.
  80 ///
  81 SDOperand AlphaDAGToDAGISel::getGlobalBaseReg() {
  82   return CurDAG->getCopyFromReg(CurDAG->getEntryNode(),
  83                                 AlphaLowering.getVRegGP(),
  84                                 MVT::i64);
  85 }
  86
  87 /// getRASaveReg - Grab the return address
  88 ///
  89 SDOperand AlphaDAGToDAGISel::getRASaveReg() {
  90   return CurDAG->getCopyFromReg(CurDAG->getEntryNode(),
  91                                 AlphaLowering.getVRegRA(),
  92                                 MVT::i64);
  93 }
  94
  95 /// InstructionSelectBasicBlock - This callback is invoked by
  96 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
  97 void AlphaDAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
  98   DEBUG(BB->dump());
  99
 100   // Select target instructions for the DAG.
 101   DAG.setRoot(Select(DAG.getRoot()));
 102   CodeGenMap.clear();
 103   DAG.RemoveDeadNodes();
 104
 105   // Emit machine code to BB.
 106   ScheduleAndEmitDAG(DAG);
 107 }
 108
 109 // Select - Convert the specified operand from a target-independent to a
 110 // target-specific node if it hasn't already been changed.
 111 SDOperand AlphaDAGToDAGISel::Select(SDOperand Op) {
 112   SDNode *N = Op.Val;
 113   if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
 114       N->getOpcode() < AlphaISD::FIRST_NUMBER)
 115     return Op;   // Already selected.
 116
 117   // If this has already been converted, use it.
 118   std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(Op);
 119   if (CGMI != CodeGenMap.end()) return CGMI->second;
 120
 121   switch (N->getOpcode()) {
 122   default: break;
 123   case ISD::TAILCALL:
 124   case ISD::CALL: return SelectCALL(Op);
 125
 126   case ISD::DYNAMIC_STACKALLOC: {
 127     if (!isa<ConstantSDNode>(N->getOperand(2)) ||
 128         cast<ConstantSDNode>(N->getOperand(2))->getValue() != 0) {
 129       std::cerr << "Cannot allocate stack object with greater alignment than"
 130                 << " the stack alignment yet!";
 131       abort();
 132     }
 133
 134     SDOperand Chain = Select(N->getOperand(0));
 135     SDOperand Amt   = Select(N->getOperand(1));
 136     SDOperand Reg = CurDAG->getRegister(Alpha::R30, MVT::i64);
 137     SDOperand Val = CurDAG->getCopyFromReg(Chain, Alpha::R30, MVT::i64);
 138     Chain = Val.getValue(1);
 139
 140     // Subtract the amount (guaranteed to be a multiple of the stack alignment)
 141     // from the stack pointer, giving us the result pointer.
 142     SDOperand Result = CurDAG->getTargetNode(Alpha::SUBQ, MVT::i64, Val, Amt);
 143
 144     // Copy this result back into R30.
 145     Chain = CurDAG->getNode(ISD::CopyToReg, MVT::Other, Chain, Reg, Result);
 146
 147     // Copy this result back out of R30 to make sure we're not using the stack
 148     // space without decrementing the stack pointer.
 149     Result = CurDAG->getCopyFromReg(Chain, Alpha::R30, MVT::i64);
 150
 151     // Finally, replace the DYNAMIC_STACKALLOC with the copyfromreg.
 152     CodeGenMap[Op.getValue(0)] = Result;
 153     CodeGenMap[Op.getValue(1)] = Result.getValue(1);
 154     return SDOperand(Result.Val, Op.ResNo);
 155   }
 156   case ISD::BRCOND: {
 157     if (N->getOperand(1).getOpcode() == ISD::SETCC &&
 158         MVT::isFloatingPoint(N->getOperand(1).getOperand(0).getValueType())) {
 159       SDOperand Chain = Select(N->getOperand(0));
 160       SDOperand CC1 = Select(N->getOperand(1).getOperand(0));
 161       SDOperand CC2 = Select(N->getOperand(1).getOperand(1));
 162       ISD::CondCode cCode= cast<CondCodeSDNode>(N->getOperand(1).getOperand(2))->get();
 163
 164       bool rev = false;
 165       bool isNE = false;
 166       unsigned Opc = Alpha::WTF;
 167       switch(cCode) {
 168       default: N->dump(); assert(0 && "Unknown FP comparison!");
 169       case ISD::SETEQ: Opc = Alpha::CMPTEQ; break;
 170       case ISD::SETLT: Opc = Alpha::CMPTLT; break;
 171       case ISD::SETLE: Opc = Alpha::CMPTLE; break;
 172       case ISD::SETGT: Opc = Alpha::CMPTLT; rev = true; break;
 173       case ISD::SETGE: Opc = Alpha::CMPTLE; rev = true; break;
 174       case ISD::SETNE: Opc = Alpha::CMPTEQ; isNE = true; break;
 175       };
 176       SDOperand cmp = CurDAG->getTargetNode(Opc, MVT::f64,
 177                                             rev?CC2:CC1,
 178                                             rev?CC1:CC2);
 179
 180       MachineBasicBlock *Dest =
 181         cast<BasicBlockSDNode>(N->getOperand(2))->getBasicBlock();
 182       if(isNE)
 183         return CurDAG->SelectNodeTo(N, Alpha::FBEQ, MVT::Other, cmp,
 184                                     CurDAG->getBasicBlock(Dest), Chain);
 185       else
 186         return CurDAG->SelectNodeTo(N, Alpha::FBNE, MVT::Other, cmp,
 187                                     CurDAG->getBasicBlock(Dest), Chain);
 188     }
 189     SDOperand Chain = Select(N->getOperand(0));
 190     SDOperand CC = Select(N->getOperand(1));
 191     MachineBasicBlock *Dest =
 192       cast<BasicBlockSDNode>(N->getOperand(2))->getBasicBlock();
 193     return CurDAG->SelectNodeTo(N, Alpha::BNE, MVT::Other, CC,
 194                                 CurDAG->getBasicBlock(Dest), Chain);
 195   }
 196
 197   case ISD::BR:
 198     return CurDAG->SelectNodeTo(N, Alpha::BR_DAG, MVT::Other, N->getOperand(1),
 199                                 Select(N->getOperand(0)));
 200   case ISD::FrameIndex: {
 201     int FI = cast<FrameIndexSDNode>(N)->getIndex();
 202     return CurDAG->SelectNodeTo(N, Alpha::LDA, MVT::i64,
 203                                 CurDAG->getTargetFrameIndex(FI, MVT::i32),
 204                                 getI64Imm(0));
 205   }
 206   case AlphaISD::GlobalBaseReg:
 207     return getGlobalBaseReg();
 208
 209   case ISD::TargetConstantPool: {
 210     Constant *C = cast<ConstantPoolSDNode>(N)->get();
 211     SDOperand Tmp, CPI = CurDAG->getTargetConstantPool(C, MVT::i64);
 212     Tmp = CurDAG->getTargetNode(Alpha::LDAHr, MVT::i64, CPI, getGlobalBaseReg());
 213     return CurDAG->SelectNodeTo(N, Alpha::LDAr, MVT::i64, CPI, Tmp);
 214   }
 215   case ISD::ExternalSymbol:
 216     return CurDAG->SelectNodeTo(N, Alpha::LDQl, MVT::i64,
 217                                 CurDAG->getTargetExternalSymbol(cast<ExternalSymbolSDNode>(N)->getSymbol(), MVT::i64),
 218                                 getGlobalBaseReg());
 219
 220   case ISD::RET: {
 221     SDOperand Chain = Select(N->getOperand(0));     // Token chain.
 222     SDOperand InFlag;
 223
 224     if (N->getNumOperands() == 2) {
 225       SDOperand Val = Select(N->getOperand(1));
 226       if (N->getOperand(1).getValueType() == MVT::i64) {
 227         Chain = CurDAG->getCopyToReg(Chain, Alpha::R0, Val, InFlag);
 228         InFlag = Chain.getValue(1);
 229       } else if (N->getOperand(1).getValueType() == MVT::f64 ||
 230                  N->getOperand(1).getValueType() == MVT::f32) {
 231         Chain = CurDAG->getCopyToReg(Chain, Alpha::F0, Val, InFlag);
 232         InFlag = Chain.getValue(1);
 233       }
 234     }
 235     Chain = CurDAG->getCopyToReg(Chain, Alpha::R26, getRASaveReg(), InFlag);
 236     InFlag = Chain.getValue(1);
 237
 238     // Finally, select this to a ret instruction.
 239     return CurDAG->SelectNodeTo(N, Alpha::RETDAG, MVT::Other, Chain, InFlag);
 240   }
 241   case ISD::Constant: {
 242     int64_t val = (int64_t)cast<ConstantSDNode>(N)->getValue();
 243     if (val > (int64_t)IMM_HIGH +(int64_t)IMM_HIGH* (int64_t)IMM_MULT ||
 244         val < (int64_t)IMM_LOW + (int64_t)IMM_LOW * (int64_t)IMM_MULT) {
 245       MachineConstantPool *CP = BB->getParent()->getConstantPool();
 246       ConstantUInt *C =
 247         ConstantUInt::get(Type::getPrimitiveType(Type::ULongTyID) , val);
 248       SDOperand Tmp, CPI = CurDAG->getTargetConstantPool(C, MVT::i64);
 249       Tmp = CurDAG->getTargetNode(Alpha::LDAHr, MVT::i64, CPI, getGlobalBaseReg());
 250       return CurDAG->SelectNodeTo(N, Alpha::LDQr, MVT::i64, CPI, Tmp);
 251     }
 252     break;
 253   }
 254   case ISD::ConstantFP:
 255     if (ConstantFPSDNode *CN = dyn_cast<ConstantFPSDNode>(N)) {
 256       bool isDouble = N->getValueType(0) == MVT::f64;
 257       MVT::ValueType T = isDouble ? MVT::f64 : MVT::f32;
 258       if (CN->isExactlyValue(+0.0)) {
 259         return CurDAG->SelectNodeTo(N, isDouble ? Alpha::CPYST : Alpha::CPYSS,
 260                                     T, CurDAG->getRegister(Alpha::F31, T),
 261                                     CurDAG->getRegister(Alpha::F31, T));
 262       } else if ( CN->isExactlyValue(-0.0)) {
 263         return CurDAG->SelectNodeTo(N, isDouble ? Alpha::CPYSNT : Alpha::CPYSNS,
 264                                     T, CurDAG->getRegister(Alpha::F31, T),
 265                                     CurDAG->getRegister(Alpha::F31, T));
 266       } else {
 267         abort();
 268       }
 269       break;
 270     }
 271   case ISD::SDIV:
 272   case ISD::UDIV:
 273   case ISD::UREM:
 274   case ISD::SREM:
 275     if (MVT::isInteger(N->getValueType(0))) {
 276       const char* opstr = 0;
 277       switch(N->getOpcode()) {
 278       case ISD::UREM: opstr = "__remqu"; break;
 279       case ISD::SREM: opstr = "__remq";  break;
 280       case ISD::UDIV: opstr = "__divqu"; break;
 281       case ISD::SDIV: opstr = "__divq";  break;
 282       }
 283       SDOperand Tmp1 = Select(N->getOperand(0)),
 284         Tmp2 = Select(N->getOperand(1)),
 285         Addr = Select(CurDAG->getExternalSymbol(opstr,
 286                                                 AlphaLowering.getPointerTy()));
 287       SDOperand Chain;
 288       Chain = CurDAG->getCopyToReg(CurDAG->getEntryNode(), Alpha::R24, Tmp1,
 289                                    SDOperand(0,0));
 290       Chain = CurDAG->getCopyToReg(Chain, Alpha::R25, Tmp2, Chain.getValue(1));
 291       Chain = CurDAG->getCopyToReg(Chain, Alpha::R27, Addr, Chain.getValue(1));
 292       Chain = CurDAG->getTargetNode(Alpha::JSRsDAG, MVT::Other, MVT::Flag,
 293                                     Chain, Chain.getValue(1));
 294       return CurDAG->getCopyFromReg(Chain, Alpha::R27, MVT::i64,
 295                                     Chain.getValue(1));
 296     }
 297     break;
 298
 299   case ISD::SETCC:
 300     if (MVT::isFloatingPoint(N->getOperand(0).Val->getValueType(0))) {
 301       unsigned Opc = Alpha::WTF;
 302       ISD::CondCode CC = cast<CondCodeSDNode>(N->getOperand(2))->get();
 303       bool rev = false;
 304       bool isNE = false;
 305       switch(CC) {
 306       default: N->dump(); assert(0 && "Unknown FP comparison!");
 307       case ISD::SETEQ: Opc = Alpha::CMPTEQ; break;
 308       case ISD::SETLT: Opc = Alpha::CMPTLT; break;
 309       case ISD::SETLE: Opc = Alpha::CMPTLE; break;
 310       case ISD::SETGT: Opc = Alpha::CMPTLT; rev = true; break;
 311       case ISD::SETGE: Opc = Alpha::CMPTLE; rev = true; break;
 312       case ISD::SETNE: Opc = Alpha::CMPTEQ; isNE = true; break;
 313       };
 314       SDOperand tmp1 = Select(N->getOperand(0)),
 315         tmp2 = Select(N->getOperand(1));
 316       SDOperand cmp = CurDAG->getTargetNode(Opc, MVT::f64,
 317                                             rev?tmp2:tmp1,
 318                                             rev?tmp1:tmp2);
 319       if (isNE)
 320         cmp = CurDAG->getTargetNode(Alpha::CMPTEQ, MVT::f64, cmp,
 321                                     CurDAG->getRegister(Alpha::F31, MVT::f64));
 322
 323       SDOperand LD;
 324       if (AlphaLowering.hasITOF()) {
 325         LD = CurDAG->getNode(AlphaISD::FTOIT_, MVT::i64, cmp);
 326       } else {
 327         int FrameIdx =
 328           CurDAG->getMachineFunction().getFrameInfo()->CreateStackObject(8, 8);
 329         SDOperand FI = CurDAG->getFrameIndex(FrameIdx, MVT::i64);
 330         SDOperand ST = CurDAG->getTargetNode(Alpha::STT, MVT::Other,
 331                                              cmp, FI, CurDAG->getRegister(Alpha::R31, MVT::i64));
 332         LD = CurDAG->getTargetNode(Alpha::LDQ, MVT::i64, FI,
 333                                    CurDAG->getRegister(Alpha::R31, MVT::i64),
 334                                    ST);
 335       }
 336       SDOperand FP = CurDAG->getTargetNode(Alpha::CMPULT, MVT::i64,
 337                                            CurDAG->getRegister(Alpha::R31, MVT::i64),
 338                                            LD);
 339       return FP;
 340     }
 341     break;
 342
 343   case ISD::SELECT:
 344     if (MVT::isFloatingPoint(N->getValueType(0)) &&
 345         (N->getOperand(0).getOpcode() != ISD::SETCC ||
 346          !MVT::isFloatingPoint(N->getOperand(0).getOperand(1).getValueType()))) {
 347       //This should be the condition not covered by the Patterns
 348       //FIXME: Don't have SelectCode die, but rather return something testable
 349       // so that things like this can be caught in fall though code
 350       //move int to fp
 351       bool isDouble = N->getValueType(0) == MVT::f64;
 352       SDOperand LD,
 353         cond = Select(N->getOperand(0)),
 354         TV = Select(N->getOperand(1)),
 355         FV = Select(N->getOperand(2));
 356
 357       if (AlphaLowering.hasITOF()) {
 358         LD = CurDAG->getNode(AlphaISD::ITOFT_, MVT::f64, cond);
 359       } else {
 360         int FrameIdx =
 361           CurDAG->getMachineFunction().getFrameInfo()->CreateStackObject(8, 8);
 362         SDOperand FI = CurDAG->getFrameIndex(FrameIdx, MVT::i64);
 363         SDOperand ST = CurDAG->getTargetNode(Alpha::STQ, MVT::Other,
 364                                              cond, FI, CurDAG->getRegister(Alpha::R31, MVT::i64));
 365         LD = CurDAG->getTargetNode(Alpha::LDT, MVT::f64, FI,
 366                                    CurDAG->getRegister(Alpha::R31, MVT::i64),
 367                                    ST);
 368       }
 369       SDOperand FP = CurDAG->getTargetNode(isDouble?Alpha::FCMOVNET:Alpha::FCMOVNES,
 370                                            MVT::f64, FV, TV, LD);
 371       return FP;
 372     }
 373     break;
 374
 375   }
 376
 377   return SelectCode(Op);
 378 }
 379
 380 SDOperand AlphaDAGToDAGISel::SelectCALL(SDOperand Op) {
 381   //TODO: add flag stuff to prevent nondeturministic breakage!
 382
 383   SDNode *N = Op.Val;
 384   SDOperand Chain = Select(N->getOperand(0));
 385   SDOperand Addr = Select(N->getOperand(1));
 386   SDOperand InFlag;  // Null incoming flag value.
 387
 388    std::vector<SDOperand> CallOperands;
 389    std::vector<MVT::ValueType> TypeOperands;
 390
 391    //grab the arguments
 392    for(int i = 2, e = N->getNumOperands(); i < e; ++i) {
 393      TypeOperands.push_back(N->getOperand(i).getValueType());
 394      CallOperands.push_back(Select(N->getOperand(i)));
 395    }
 396    int count = N->getNumOperands() - 2;
 397
 398    static const unsigned args_int[] = {Alpha::R16, Alpha::R17, Alpha::R18,
 399                                        Alpha::R19, Alpha::R20, Alpha::R21};
 400    static const unsigned args_float[] = {Alpha::F16, Alpha::F17, Alpha::F18,
 401                                          Alpha::F19, Alpha::F20, Alpha::F21};
 402
 403    for (int i = 6; i < count; ++i) {
 404      unsigned Opc = Alpha::WTF;
 405      if (MVT::isInteger(TypeOperands[i])) {
 406        Opc = Alpha::STQ;
 407      } else if (TypeOperands[i] == MVT::f32) {
 408        Opc = Alpha::STS;
 409      } else if (TypeOperands[i] == MVT::f64) {
 410        Opc = Alpha::STT;
 411      } else
 412        assert(0 && "Unknown operand");
 413      Chain = CurDAG->getTargetNode(Opc, MVT::Other, CallOperands[i],
 414                                    getI64Imm((i - 6) * 8),
 415                                    CurDAG->getCopyFromReg(Chain, Alpha::R30, MVT::i64),
 416                                    Chain);
 417    }
 418    for (int i = 0; i < std::min(6, count); ++i) {
 419      if (MVT::isInteger(TypeOperands[i])) {
 420        Chain = CurDAG->getCopyToReg(Chain, args_int[i], CallOperands[i], InFlag);
 421        InFlag = Chain.getValue(1);
 422      } else if (TypeOperands[i] == MVT::f32 || TypeOperands[i] == MVT::f64) {
 423        Chain = CurDAG->getCopyToReg(Chain, args_float[i], CallOperands[i], InFlag);
 424        InFlag = Chain.getValue(1);
 425      } else
 426        assert(0 && "Unknown operand");
 427    }
 428
 429
 430    Chain = CurDAG->getCopyToReg(Chain, Alpha::R27, Addr, InFlag);
 431    InFlag = Chain.getValue(1);
 432    // Finally, once everything is in registers to pass to the call, emit the
 433    // call itself.
 434    Chain = CurDAG->getTargetNode(Alpha::JSRDAG, MVT::Other, MVT::Flag,
 435                                  Chain, InFlag );
 436    InFlag = Chain.getValue(1);
 437
 438    std::vector<SDOperand> CallResults;
 439
 440    switch (N->getValueType(0)) {
 441    default: assert(0 && "Unexpected ret value!");
 442      case MVT::Other: break;
 443    case MVT::i64:
 444      Chain = CurDAG->getCopyFromReg(Chain, Alpha::R0, MVT::i64, InFlag).getValue(1);
 445      CallResults.push_back(Chain.getValue(0));
 446      break;
 447    case MVT::f32:
 448      Chain = CurDAG->getCopyFromReg(Chain, Alpha::F0, MVT::f32, InFlag).getValue(1);
 449      CallResults.push_back(Chain.getValue(0));
 450      break;
 451    case MVT::f64:
 452      Chain = CurDAG->getCopyFromReg(Chain, Alpha::F0, MVT::f64, InFlag).getValue(1);
 453      CallResults.push_back(Chain.getValue(0));
 454      break;
 455    }
 456
 457    CallResults.push_back(Chain);
 458    for (unsigned i = 0, e = CallResults.size(); i != e; ++i)
 459      CodeGenMap[Op.getValue(i)] = CallResults[i];
 460    return CallResults[Op.ResNo];
 461 }
 462
 463
 464 /// createAlphaISelDag - This pass converts a legalized DAG into a
 465 /// Alpha-specific DAG, ready for instruction scheduling.
 466 ///
 467 FunctionPass *llvm::createAlphaISelDag(TargetMachine &TM) {
 468   return new AlphaDAGToDAGISel(TM);
 469 }