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/MachineFunction.h"
  20 #include "llvm/CodeGen/SSARegMap.h"
  21 #include "llvm/CodeGen/SelectionDAG.h"
  22 #include "llvm/CodeGen/SelectionDAGISel.h"
  23 #include "llvm/Target/TargetOptions.h"
  24 #include "llvm/ADT/Statistic.h"
  25 #include "llvm/Constants.h"
  26 #include "llvm/GlobalValue.h"
  27 #include "llvm/Support/Debug.h"
  28 #include "llvm/Support/MathExtras.h"
  29 using namespace llvm;
  30
  31 namespace {
  32
  33   //===--------------------------------------------------------------------===//
  34   /// AlphaDAGToDAGISel - Alpha specific code to select Alpha machine
  35   /// instructions for SelectionDAG operations.
  36   ///
  37   class AlphaDAGToDAGISel : public SelectionDAGISel {
  38     AlphaTargetLowering AlphaLowering;
  39
  40   public:
  41     AlphaDAGToDAGISel(TargetMachine &TM)
  42       : SelectionDAGISel(AlphaLowering), AlphaLowering(TM) {}
  43
  44     /// getI64Imm - Return a target constant with the specified value, of type
  45     /// i64.
  46     inline SDOperand getI64Imm(unsigned Imm) {
  47       return CurDAG->getTargetConstant(Imm, MVT::i64);
  48     }
  49
  50     virtual bool runOnFunction(Function &Fn) {
  51       return SelectionDAGISel::runOnFunction(Fn);
  52     }
  53
  54     // Select - Convert the specified operand from a target-independent to a
  55     // target-specific node if it hasn't already been changed.
  56     SDOperand Select(SDOperand Op);
  57
  58     /// InstructionSelectBasicBlock - This callback is invoked by
  59     /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
  60     virtual void InstructionSelectBasicBlock(SelectionDAG &DAG);
  61
  62     virtual const char *getPassName() const {
  63       return "Alpha DAG->DAG Pattern Instruction Selection";
  64     }
  65
  66 // Include the pieces autogenerated from the target description.
  67 #include "AlphaGenDAGISel.inc"
  68
  69 private:
  70   };
  71 }
  72
  73 /// InstructionSelectBasicBlock - This callback is invoked by
  74 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
  75 void AlphaDAGToDAGISel::InstructionSelectBasicBlock(SelectionDAG &DAG) {
  76   DEBUG(BB->dump());
  77
  78   // The selection process is inherently a bottom-up recursive process (users
  79   // select their uses before themselves).  Given infinite stack space, we
  80   // could just start selecting on the root and traverse the whole graph.  In
  81   // practice however, this causes us to run out of stack space on large basic
  82   // blocks.  To avoid this problem, select the entry node, then all its uses,
  83   // iteratively instead of recursively.
  84   std::vector<SDOperand> Worklist;
  85   Worklist.push_back(DAG.getEntryNode());
  86
  87   // Note that we can do this in the Alpha target (scanning forward across token
  88   // chain edges) because no nodes ever get folded across these edges.  On a
  89   // target like X86 which supports load/modify/store operations, this would
  90   // have to be more careful.
  91   while (!Worklist.empty()) {
  92     SDOperand Node = Worklist.back();
  93     Worklist.pop_back();
  94
  95     // Chose from the least deep of the top two nodes.
  96     if (!Worklist.empty() &&
  97         Worklist.back().Val->getNodeDepth() < Node.Val->getNodeDepth())
  98       std::swap(Worklist.back(), Node);
  99
 100     if ((Node.Val->getOpcode() >= ISD::BUILTIN_OP_END &&
 101          Node.Val->getOpcode() < AlphaISD::FIRST_NUMBER) ||
 102         CodeGenMap.count(Node)) continue;
 103
 104     for (SDNode::use_iterator UI = Node.Val->use_begin(),
 105          E = Node.Val->use_end(); UI != E; ++UI) {
 106       // Scan the values.  If this use has a value that is a token chain, add it
 107       // to the worklist.
 108       SDNode *User = *UI;
 109       for (unsigned i = 0, e = User->getNumValues(); i != e; ++i)
 110         if (User->getValueType(i) == MVT::Other) {
 111           Worklist.push_back(SDOperand(User, i));
 112           break;
 113         }
 114     }
 115
 116     // Finally, legalize this node.
 117     Select(Node);
 118   }
 119
 120   // Select target instructions for the DAG.
 121   DAG.setRoot(Select(DAG.getRoot()));
 122   CodeGenMap.clear();
 123   DAG.RemoveDeadNodes();
 124
 125   // Emit machine code to BB.
 126   ScheduleAndEmitDAG(DAG);
 127 }
 128
 129 // Select - Convert the specified operand from a target-independent to a
 130 // target-specific node if it hasn't already been changed.
 131 SDOperand AlphaDAGToDAGISel::Select(SDOperand Op) {
 132   SDNode *N = Op.Val;
 133   if (N->getOpcode() >= ISD::BUILTIN_OP_END &&
 134       N->getOpcode() < AlphaISD::FIRST_NUMBER)
 135     return Op;   // Already selected.
 136
 137   // If this has already been converted, use it.
 138   std::map<SDOperand, SDOperand>::iterator CGMI = CodeGenMap.find(Op);
 139   if (CGMI != CodeGenMap.end()) return CGMI->second;
 140
 141   switch (N->getOpcode()) {
 142   default: break;
 143   case ISD::DYNAMIC_STACKALLOC:
 144   case ISD::ADD_PARTS:
 145   case ISD::SUB_PARTS:
 146   case ISD::SETCC:
 147   case ISD::CALL:
 148   case ISD::TAILCALL:
 149     assert(0 && "You want these too?");
 150
 151   case ISD::TokenFactor: {
 152     SDOperand New;
 153     if (N->getNumOperands() == 2) {
 154       SDOperand Op0 = Select(N->getOperand(0));
 155       SDOperand Op1 = Select(N->getOperand(1));
 156       New = CurDAG->getNode(ISD::TokenFactor, MVT::Other, Op0, Op1);
 157     } else {
 158       std::vector<SDOperand> Ops;
 159       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
 160         Ops.push_back(Select(N->getOperand(i)));
 161       New = CurDAG->getNode(ISD::TokenFactor, MVT::Other, Ops);
 162     }
 163
 164     CodeGenMap[Op] = New;
 165     return New;
 166   }
 167   case ISD::CopyFromReg: {
 168     SDOperand Chain = Select(N->getOperand(0));
 169     if (Chain == N->getOperand(0)) return Op; // No change
 170     SDOperand New = CurDAG->getCopyFromReg(Chain,
 171          cast<RegisterSDNode>(N->getOperand(1))->getReg(), N->getValueType(0));
 172     return New.getValue(Op.ResNo);
 173   }
 174   case ISD::CopyToReg: {
 175     SDOperand Chain = Select(N->getOperand(0));
 176     SDOperand Reg = N->getOperand(1);
 177     SDOperand Val = Select(N->getOperand(2));
 178     SDOperand New = CurDAG->getNode(ISD::CopyToReg, MVT::Other,
 179                                     Chain, Reg, Val);
 180     CodeGenMap[Op] = New;
 181     return New;
 182   }
 183   case ISD::UNDEF:
 184     if (N->getValueType(0) == MVT::i64)
 185       CurDAG->SelectNodeTo(N, Alpha::IDEF, MVT::i64);
 186 //     else if (N->getValueType(0) == MVT::f32)
 187 //       CurDAG->SelectNodeTo(N, PPC::IMPLICIT_DEF_F4, MVT::f32);
 188 //     else
 189 //       CurDAG->SelectNodeTo(N, PPC::IMPLICIT_DEF_F8, MVT::f64);
 190     return SDOperand(N, 0);
 191   case ISD::FrameIndex: {
 192 //     int FI = cast<FrameIndexSDNode>(N)->getIndex();
 193 //     CurDAG->SelectNodeTo(N, Alpha::LDA, MVT::i64,
 194 //                          CurDAG->getTargetFrameIndex(FI, MVT::i32),
 195 //                          getI32Imm(0));
 196 //     return SDOperand(N, 0);
 197     assert(0 && "Frame?, you are suppose to look through the window, not at the frame!");
 198   }
 199   case ISD::ConstantPool: {
 200 //     Constant *C = cast<ConstantPoolSDNode>(N)->get();
 201 //     SDOperand Tmp, CPI = CurDAG->getTargetConstantPool(C, MVT::i32);
 202 //     if (PICEnabled)
 203 //       Tmp = CurDAG->getTargetNode(PPC::ADDIS, MVT::i32, getGlobalBaseReg(),CPI);
 204 //     else
 205 //       Tmp = CurDAG->getTargetNode(PPC::LIS, MVT::i32, CPI);
 206 //     CurDAG->SelectNodeTo(N, PPC::LA, MVT::i32, Tmp, CPI);
 207 //     return SDOperand(N, 0);
 208     assert(0 && "Constants are overrated");
 209   }
 210   case ISD::GlobalAddress: {
 211 //     GlobalValue *GV = cast<GlobalAddressSDNode>(N)->getGlobal();
 212 //     SDOperand Tmp;
 213 //     SDOperand GA = CurDAG->getTargetGlobalAddress(GV, MVT::i32);
 214 //     if (PICEnabled)
 215 //       Tmp = CurDAG->getTargetNode(PPC::ADDIS, MVT::i32, getGlobalBaseReg(), GA);
 216 //     else
 217 //       Tmp = CurDAG->getTargetNode(PPC::LIS, MVT::i32, GA);
 218
 219 //     if (GV->hasWeakLinkage() || GV->isExternal())
 220 //       CurDAG->SelectNodeTo(N, PPC::LWZ, MVT::i32, GA, Tmp);
 221 //     else
 222 //       CurDAG->SelectNodeTo(N, PPC::LA, MVT::i32, Tmp, GA);
 223 //     return SDOperand(N, 0);
 224     assert(0 && "GlobalAddresses are for wimps");
 225   }
 226
 227   case ISD::CALLSEQ_START:
 228   case ISD::CALLSEQ_END: {
 229     unsigned Amt = cast<ConstantSDNode>(N->getOperand(1))->getValue();
 230     unsigned Opc = N->getOpcode() == ISD::CALLSEQ_START ?
 231                        Alpha::ADJUSTSTACKDOWN : Alpha::ADJUSTSTACKUP;
 232     CurDAG->SelectNodeTo(N, Opc, MVT::Other,
 233                          getI64Imm(Amt), Select(N->getOperand(0)));
 234     return SDOperand(N, 0);
 235   }
 236   case ISD::RET: {
 237     SDOperand Chain = Select(N->getOperand(0));     // Token chain.
 238
 239     if (N->getNumOperands() == 2) {
 240       SDOperand Val = Select(N->getOperand(1));
 241       if (N->getOperand(1).getValueType() == MVT::i64) {
 242         Chain = CurDAG->getCopyToReg(Chain, Alpha::R0, Val);
 243       }
 244     }
 245     //BuildMI(BB, Alpha::RET, 2, Alpha::R31).addReg(Alpha::R26).addImm(1);
 246
 247     // FIXME: add restoring of the RA to R26 to the chain
 248     // Finally, select this to a ret instruction.
 249     CurDAG->SelectNodeTo(N, Alpha::RETDAG, MVT::Other, Chain);
 250     return SDOperand(N, 0);
 251   }
 252
 253
 254
 255   }
 256
 257   return SelectCode(Op);
 258 }
 259
 260 /// createAlphaISelDag - This pass converts a legalized DAG into a
 261 /// Alpha-specific DAG, ready for instruction scheduling.
 262 ///
 263 FunctionPass *llvm::createAlphaISelDag(TargetMachine &TM) {
 264   return new AlphaDAGToDAGISel(TM);
 265 }