MSP430ISelDAGToDAG.cpp revision a3d275414331b53b0a3ed6490719417c016b3515 
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.
154static void MoveBelowTokenFactor(SelectionDAG *CurDAG, SDValue Load,
155                                 SDValue Store, SDValue TF) {
156  SmallVector<SDValue, 4> Ops;
157  for (unsigned i = 0, e = TF.getNode()->getNumOperands(); i != e; ++i)
158    if (Load.getNode() == TF.getOperand(i).getNode())
159      Ops.push_back(Load.getOperand(0));
160    else
161      Ops.push_back(TF.getOperand(i));
162  SDValue NewTF = CurDAG->UpdateNodeOperands(TF, &Ops[0], Ops.size());
163  SDValue NewLoad = CurDAG->UpdateNodeOperands(Load, NewTF,
164                                               Load.getOperand(1),
165                                               Load.getOperand(2));
166  CurDAG->UpdateNodeOperands(Store, NewLoad.getValue(1), Store.getOperand(1),
167                             Store.getOperand(2), Store.getOperand(3));
168}
169
170/// isRMWLoad - Return true if N is a load that's part of RMW sub-DAG.
171/// The chain produced by the load must only be used by the store's chain
172/// operand, otherwise this may produce a cycle in the DAG.
173static bool isRMWLoad(SDValue N, SDValue Chain, SDValue Address,
174                      SDValue &Load) {
175  if (N.getOpcode() == ISD::BIT_CONVERT)
176    N = N.getOperand(0);
177
178  LoadSDNode *LD = dyn_cast<LoadSDNode>(N);
179  if (!LD || LD->isVolatile())
180    return false;
181  if (LD->getAddressingMode() != ISD::UNINDEXED)
182    return false;
183
184  ISD::LoadExtType ExtType = LD->getExtensionType();
185  if (ExtType != ISD::NON_EXTLOAD && ExtType != ISD::EXTLOAD)
186    return false;
187
188  if (N.hasOneUse() &&
189      LD->hasNUsesOfValue(1, 1) &&
190      N.getOperand(1) == Address &&
191      LD->isOperandOf(Chain.getNode())) {
192    Load = N;
193    return true;
194  }
195  return false;
196}
197
198/// PreprocessForRMW - Preprocess the DAG to make instruction selection better.
199/// This is only run if not in -O0 mode.
200/// This allows the instruction selector to pick more read-modify-write
201/// instructions. This is a common case:
202///
203///     [Load chain]
204///         ^
205///         |
206///       [Load]
207///       ^    ^
208///       |    |
209///      /      \-
210///     /         |
211/// [TokenFactor] [Op]
212///     ^          ^
213///     |          |
214///      \        /
215///       \      /
216///       [Store]
217///
218/// The fact the store's chain operand != load's chain will prevent the
219/// (store (op (load))) instruction from being selected. We can transform it to:
220///
221///     [Load chain]
222///         ^
223///         |
224///    [TokenFactor]
225///         ^
226///         |
227///       [Load]
228///       ^    ^
229///       |    |
230///       |     \-
231///       |       |
232///       |     [Op]
233///       |       ^
234///       |       |
235///       \      /
236///        \    /
237///       [Store]
238void MSP430DAGToDAGISel::PreprocessForRMW() {
239  for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
240         E = CurDAG->allnodes_end(); I != E; ++I) {
241    if (!ISD::isNON_TRUNCStore(I))
242      continue;
243    SDValue Chain = I->getOperand(0);
244
245    if (Chain.getNode()->getOpcode() != ISD::TokenFactor)
246      continue;
247
248    SDValue N1 = I->getOperand(1);
249    SDValue N2 = I->getOperand(2);
250    if ((N1.getValueType().isFloatingPoint() &&
251         !N1.getValueType().isVector()) ||
252        !N1.hasOneUse())
253      continue;
254
255    bool RModW = false;
256    SDValue Load;
257    unsigned Opcode = N1.getNode()->getOpcode();
258    switch (Opcode) {
259    case ISD::ADD:
260    case ISD::AND:
261    case ISD::OR:
262    case ISD::XOR:
263    case ISD::ADDC:
264    case ISD::ADDE: {
265      SDValue N10 = N1.getOperand(0);
266      SDValue N11 = N1.getOperand(1);
267      RModW = isRMWLoad(N10, Chain, N2, Load);
268      if (!RModW)
269        RModW = isRMWLoad(N11, Chain, N2, Load);
270      break;
271    }
272    case ISD::SUB:
273    case ISD::SUBC:
274    case ISD::SUBE: {
275      SDValue N10 = N1.getOperand(0);
276      RModW = isRMWLoad(N10, Chain, N2, Load);
277      break;
278    }
279    }
280
281    if (RModW) {
282      MoveBelowTokenFactor(CurDAG, Load, SDValue(I, 0), Chain);
283      ++NumLoadMoved;
284    }
285  }
286}
287
288/// InstructionSelect - This callback is invoked by
289/// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
290void MSP430DAGToDAGISel::InstructionSelect() {
291  PreprocessForRMW();
292
293  DEBUG(errs() << "Selection DAG after RMW preprocessing:\n");
294  DEBUG(CurDAG->dump());
295
296  DEBUG(BB->dump());
297
298  // Codegen the basic block.
299  DEBUG(errs() << "===== Instruction selection begins:\n");
300  DEBUG(Indent = 0);
301  SelectRoot(*CurDAG);
302  DEBUG(errs() << "===== Instruction selection ends:\n");
303
304  CurDAG->RemoveDeadNodes();
305}
306
307SDNode *MSP430DAGToDAGISel::Select(SDValue Op) {
308  SDNode *Node = Op.getNode();
309  DebugLoc dl = Op.getDebugLoc();
310
311  // Dump information about the Node being selected
312  DEBUG(errs().indent(Indent) << "Selecting: ");
313  DEBUG(Node->dump(CurDAG));
314  DEBUG(errs() << "\n");
315  DEBUG(Indent += 2);
316
317  // If we have a custom node, we already have selected!
318  if (Node->isMachineOpcode()) {
319    DEBUG(errs().indent(Indent-2) << "== ";
320          Node->dump(CurDAG);
321          errs() << "\n");
322    DEBUG(Indent -= 2);
323    return NULL;
324  }
325
326  // Few custom selection stuff.
327  switch (Node->getOpcode()) {
328  default: break;
329  case ISD::FrameIndex: {
330    assert(Op.getValueType() == MVT::i16);
331    int FI = cast<FrameIndexSDNode>(Node)->getIndex();
332    SDValue TFI = CurDAG->getTargetFrameIndex(FI, MVT::i16);
333    if (Node->hasOneUse())
334      return CurDAG->SelectNodeTo(Node, MSP430::ADD16ri, MVT::i16,
335                                  TFI, CurDAG->getTargetConstant(0, MVT::i16));
336    return CurDAG->getMachineNode(MSP430::ADD16ri, dl, MVT::i16,
337                                  TFI, CurDAG->getTargetConstant(0, MVT::i16));
338  }
339  }
340
341  // Select the default instruction
342  SDNode *ResNode = SelectCode(Op);
343
344  DEBUG(errs() << std::string(Indent-2, ' ') << "=> ");
345  if (ResNode == NULL || ResNode == Op.getNode())
346    DEBUG(Op.getNode()->dump(CurDAG));
347  else
348    DEBUG(ResNode->dump(CurDAG));
349  DEBUG(errs() << "\n");
350  DEBUG(Indent -= 2);
351
352  return ResNode;
353}
354