lib/Target/MSP430/MSP430ISelDAGToDAG.cpp

   1 //===-- MSP430ISelDAGToDAG.cpp - A dag to dag inst selector for MSP430 ----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines an instruction selector for the MSP430 target.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "MSP430.h"
  15 #include "MSP430ISelLowering.h"
  16 #include "MSP430TargetMachine.h"
  17 #include "llvm/DerivedTypes.h"
  18 #include "llvm/Function.h"
  19 #include "llvm/Intrinsics.h"
  20 #include "llvm/CallingConv.h"
  21 #include "llvm/Constants.h"
  22 #include "llvm/CodeGen/MachineFrameInfo.h"
  23 #include "llvm/CodeGen/MachineFunction.h"
  24 #include "llvm/CodeGen/MachineInstrBuilder.h"
  25 #include "llvm/CodeGen/MachineRegisterInfo.h"
  26 #include "llvm/CodeGen/SelectionDAG.h"
  27 #include "llvm/CodeGen/SelectionDAGISel.h"
  28 #include "llvm/Target/TargetLowering.h"
  29 #include "llvm/Support/Compiler.h"
  30 #include "llvm/Support/Debug.h"
  31 #include "llvm/Support/ErrorHandling.h"
  32 #include "llvm/Support/raw_ostream.h"
  33 #include "llvm/ADT/Statistic.h"
  34
  35 using namespace llvm;
  36
  37 STATISTIC(NumLoadMoved, "Number of loads moved below TokenFactor");
  38
  39 /// MSP430DAGToDAGISel - MSP430 specific code to select MSP430 machine
  40 /// instructions for SelectionDAG operations.
  41 ///
  42 namespace {
  43   class MSP430DAGToDAGISel : public SelectionDAGISel {
  44     MSP430TargetLowering &Lowering;
  45     const MSP430Subtarget &Subtarget;
  46
  47   public:
  48     MSP430DAGToDAGISel(MSP430TargetMachine &TM, CodeGenOpt::Level OptLevel)
  49       : SelectionDAGISel(TM, OptLevel),
  50         Lowering(*TM.getTargetLowering()),
  51         Subtarget(*TM.getSubtargetImpl()) { }
  52
  53     virtual void InstructionSelect();
  54
  55     virtual const char *getPassName() const {
  56       return "MSP430 DAG->DAG Pattern Instruction Selection";
  57     }
  58
  59     virtual bool
  60     SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode,
  61                                  std::vector<SDValue> &OutOps);
  62
  63     // Include the pieces autogenerated from the target description.
  64   #include "MSP430GenDAGISel.inc"
  65
  66   private:
  67     void PreprocessForRMW();
  68     SDNode *Select(SDValue Op);
  69     bool SelectAddr(SDValue Op, SDValue Addr, SDValue &Base, SDValue &Disp);
  70
  71   #ifndef NDEBUG
  72     unsigned Indent;
  73   #endif
  74   };
  75 }  // end anonymous namespace
  76
  77 /// createMSP430ISelDag - This pass converts a legalized DAG into a
  78 /// MSP430-specific DAG, ready for instruction scheduling.
  79 ///
  80 FunctionPass *llvm::createMSP430ISelDag(MSP430TargetMachine &TM,
  81                                         CodeGenOpt::Level OptLevel) {
  82   return new MSP430DAGToDAGISel(TM, OptLevel);
  83 }
  84
  85 // FIXME: This is pretty dummy routine and needs to be rewritten in the future.
  86 bool MSP430DAGToDAGISel::SelectAddr(SDValue Op, SDValue Addr,
  87                                     SDValue &Base, SDValue &Disp) {
  88   // Try to match frame address first.
  89   if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr)) {
  90     Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i16);
  91     Disp = CurDAG->getTargetConstant(0, MVT::i16);
  92     return true;
  93   }
  94
  95   switch (Addr.getOpcode()) {
  96   case ISD::ADD:
  97    // Operand is a result from ADD with constant operand which fits into i16.
  98    if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1))) {
  99       uint64_t CVal = CN->getZExtValue();
 100       // Offset should fit into 16 bits.
 101       if (((CVal << 48) >> 48) == CVal) {
 102         SDValue N0 = Addr.getOperand(0);
 103         if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(N0))
 104           Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i16);
 105         else
 106           Base = N0;
 107
 108         Disp = CurDAG->getTargetConstant(CVal, MVT::i16);
 109         return true;
 110       }
 111     }
 112     break;
 113   case MSP430ISD::Wrapper:
 114     SDValue N0 = Addr.getOperand(0);
 115     if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) {
 116       Base = CurDAG->getTargetGlobalAddress(G->getGlobal(),
 117                                             MVT::i16, G->getOffset());
 118       Disp = CurDAG->getTargetConstant(0, MVT::i16);
 119       return true;
 120     } else if (ExternalSymbolSDNode *E = dyn_cast<ExternalSymbolSDNode>(N0)) {
 121       Base = CurDAG->getTargetExternalSymbol(E->getSymbol(), MVT::i16);
 122       Disp = CurDAG->getTargetConstant(0, MVT::i16);
 123     }
 124     break;
 125   };
 126
 127   Base = Addr;
 128   Disp = CurDAG->getTargetConstant(0, MVT::i16);
 129
 130   return true;
 131 }
 132
 133
 134 bool MSP430DAGToDAGISel::
 135 SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode,
 136                              std::vector<SDValue> &OutOps) {
 137   SDValue Op0, Op1;
 138   switch (ConstraintCode) {
 139   default: return true;
 140   case 'm':   // memory
 141     if (!SelectAddr(Op, Op, Op0, Op1))
 142       return true;
 143     break;
 144   }
 145
 146   OutOps.push_back(Op0);
 147   OutOps.push_back(Op1);
 148   return false;
 149 }
 150
 151 /// MoveBelowTokenFactor - Replace TokenFactor operand with load's chain operand
 152 /// and move load below the TokenFactor. Replace store's chain operand with
 153 /// load's chain result.
 154 /// Shamelessly stolen from X86.
 155 static void MoveBelowTokenFactor(SelectionDAG *CurDAG, SDValue Load,
 156                                  SDValue Store, SDValue TF) {
 157   SmallVector<SDValue, 4> Ops;
 158   bool isRMW = false;
 159   SDValue TF0, TF1, NewTF;
 160   for (unsigned i = 0, e = TF.getNode()->getNumOperands(); i != e; ++i)
 161     if (Load.getNode() == TF.getOperand(i).getNode()) {
 162       TF0 = Load.getOperand(0);
 163       Ops.push_back(TF0);
 164     } else {
 165       TF1 = TF.getOperand(i);
 166       Ops.push_back(TF1);
 167       if (LoadSDNode* LD = dyn_cast<LoadSDNode>(TF1))
 168         isRMW = !LD->isVolatile();
 169     }
 170
 171   if (isRMW && TF1.getOperand(0).getNode() == TF0.getNode())
 172     NewTF = TF0;
 173   else
 174     NewTF = CurDAG->UpdateNodeOperands(TF, &Ops[0], Ops.size());
 175
 176   SDValue NewLoad = CurDAG->UpdateNodeOperands(Load, NewTF,
 177                                                Load.getOperand(1),
 178                                                Load.getOperand(2));
 179   CurDAG->UpdateNodeOperands(Store, NewLoad.getValue(1), Store.getOperand(1),
 180                              Store.getOperand(2), Store.getOperand(3));
 181 }
 182
 183 /// isRMWLoad - Return true if N is a load that's part of RMW sub-DAG. The chain
 184 /// produced by the load must only be used by the store's chain operand,
 185 /// otherwise this may produce a cycle in the DAG.
 186 /// Shamelessly stolen from X86. FIXME: Should we make this function common?
 187 static bool isRMWLoad(SDValue N, SDValue Chain, SDValue Address,
 188                       SDValue &Load) {
 189   if (N.getOpcode() == ISD::BIT_CONVERT)
 190     N = N.getOperand(0);
 191
 192   LoadSDNode *LD = dyn_cast<LoadSDNode>(N);
 193   if (!LD || LD->isVolatile())
 194     return false;
 195   if (LD->getAddressingMode() != ISD::UNINDEXED)
 196     return false;
 197
 198   ISD::LoadExtType ExtType = LD->getExtensionType();
 199   if (ExtType != ISD::NON_EXTLOAD && ExtType != ISD::EXTLOAD)
 200     return false;
 201
 202   if (N.hasOneUse() &&
 203       LD->hasNUsesOfValue(1, 1) &&
 204       N.getOperand(1) == Address &&
 205       LD->isOperandOf(Chain.getNode())) {
 206     Load = N;
 207     return true;
 208   }
 209   return false;
 210 }
 211
 212 /// PreprocessForRMW - Preprocess the DAG to make instruction selection better.
 213 /// Shamelessly stolen from X86.
 214 void MSP430DAGToDAGISel::PreprocessForRMW() {
 215   for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
 216          E = CurDAG->allnodes_end(); I != E; ++I) {
 217     if (!ISD::isNON_TRUNCStore(I))
 218       continue;
 219
 220     SDValue Chain = I->getOperand(0);
 221     if (Chain.getNode()->getOpcode() != ISD::TokenFactor)
 222       continue;
 223
 224     SDValue N1 = I->getOperand(1); // Value to store
 225     SDValue N2 = I->getOperand(2); // Address of store
 226
 227     if (!N1.hasOneUse())
 228       continue;
 229
 230     bool RModW = false;
 231     SDValue Load;
 232     unsigned Opcode = N1.getNode()->getOpcode();
 233     switch (Opcode) {
 234       case ISD::ADD:
 235       case ISD::AND:
 236       case ISD::OR:
 237       case ISD::XOR:
 238       case ISD::ADDC:
 239       case ISD::ADDE: {
 240         SDValue N10 = N1.getOperand(0);
 241         SDValue N11 = N1.getOperand(1);
 242         RModW = isRMWLoad(N10, Chain, N2, Load);
 243
 244         if (!RModW && isRMWLoad(N11, Chain, N2, Load)) {
 245           // Swap the operands, making the RMW load the first operand seems
 246           // to help selection and prevent token chain loops.
 247           N1 = CurDAG->UpdateNodeOperands(N1, N11, N10);
 248           RModW = true;
 249         }
 250        break;
 251       }
 252       case ISD::SUB:
 253       case ISD::SUBC:
 254       case ISD::SUBE: {
 255         SDValue N10 = N1.getOperand(0);
 256         RModW = isRMWLoad(N10, Chain, N2, Load);
 257         break;
 258       }
 259     }
 260
 261     if (RModW) {
 262       MoveBelowTokenFactor(CurDAG, Load, SDValue(I, 0), Chain);
 263       ++NumLoadMoved;
 264     }
 265   }
 266 }
 267
 268 /// InstructionSelect - This callback is invoked by
 269 /// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
 270 void MSP430DAGToDAGISel::InstructionSelect() {
 271   PreprocessForRMW();
 272
 273   DEBUG(errs() << "Selection DAG after RMW preprocessing:\n");
 274   DEBUG(CurDAG->dump());
 275
 276   DEBUG(BB->dump());
 277
 278   // Codegen the basic block.
 279   DEBUG(errs() << "===== Instruction selection begins:\n");
 280   DEBUG(Indent = 0);
 281   SelectRoot(*CurDAG);
 282   DEBUG(errs() << "===== Instruction selection ends:\n");
 283
 284   CurDAG->RemoveDeadNodes();
 285 }
 286
 287 SDNode *MSP430DAGToDAGISel::Select(SDValue Op) {
 288   SDNode *Node = Op.getNode();
 289   DebugLoc dl = Op.getDebugLoc();
 290
 291   // Dump information about the Node being selected
 292   DEBUG(errs().indent(Indent) << "Selecting: ");
 293   DEBUG(Node->dump(CurDAG));
 294   DEBUG(errs() << "\n");
 295   DEBUG(Indent += 2);
 296
 297   // If we have a custom node, we already have selected!
 298   if (Node->isMachineOpcode()) {
 299     DEBUG(errs().indent(Indent-2) << "== ";
 300           Node->dump(CurDAG);
 301           errs() << "\n");
 302     DEBUG(Indent -= 2);
 303     return NULL;
 304   }
 305
 306   // Few custom selection stuff.
 307   switch (Node->getOpcode()) {
 308   default: break;
 309   case ISD::FrameIndex: {
 310     assert(Op.getValueType() == MVT::i16);
 311     int FI = cast<FrameIndexSDNode>(Node)->getIndex();
 312     SDValue TFI = CurDAG->getTargetFrameIndex(FI, MVT::i16);
 313     if (Node->hasOneUse())
 314       return CurDAG->SelectNodeTo(Node, MSP430::ADD16ri, MVT::i16,
 315                                   TFI, CurDAG->getTargetConstant(0, MVT::i16));
 316     return CurDAG->getMachineNode(MSP430::ADD16ri, dl, MVT::i16,
 317                                   TFI, CurDAG->getTargetConstant(0, MVT::i16));
 318   }
 319   }
 320
 321   // Select the default instruction
 322   SDNode *ResNode = SelectCode(Op);
 323
 324   DEBUG(errs() << std::string(Indent-2, ' ') << "=> ");
 325   if (ResNode == NULL || ResNode == Op.getNode())
 326     DEBUG(Op.getNode()->dump(CurDAG));
 327   else
 328     DEBUG(ResNode->dump(CurDAG));
 329   DEBUG(errs() << "\n");
 330   DEBUG(Indent -= 2);
 331
 332   return ResNode;
 333 }