MSP430ISelDAGToDAG.cpp revision 198090 
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
35using namespace llvm;
36
37STATISTIC(NumLoadMoved, "Number of loads moved below TokenFactor");
38
39/// MSP430DAGToDAGISel - MSP430 specific code to select MSP430 machine
40/// instructions for SelectionDAG operations.
41///
42namespace {
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///
80FunctionPass *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.
86bool 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
134bool MSP430DAGToDAGISel::
135SelectInlineAsmMemoryOperand(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.
155static 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?
187static 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.
214void 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.
270void 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
287SDNode *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}
334