MSP430ISelDAGToDAG.cpp revision cdcad11c94bc66d8b9f28cf06f6a60e0943990ba 
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/CommandLine.h"
30#include "llvm/Support/Compiler.h"
31#include "llvm/Support/Debug.h"
32#include "llvm/Support/ErrorHandling.h"
33#include "llvm/Support/raw_ostream.h"
34#include "llvm/ADT/Statistic.h"
35
36using namespace llvm;
37
38#ifndef NDEBUG
39static cl::opt<bool>
40ViewRMWDAGs("view-msp430-rmw-dags", cl::Hidden,
41          cl::desc("Pop up a window to show isel dags after RMW preprocess"));
42#else
43static const bool ViewRMWDAGs = false;
44#endif
45
46STATISTIC(NumLoadMoved, "Number of loads moved below TokenFactor");
47
48
49namespace {
50  struct MSP430ISelAddressMode {
51    enum {
52      RegBase,
53      FrameIndexBase
54    } BaseType;
55
56    struct {            // This is really a union, discriminated by BaseType!
57      SDValue Reg;
58      int FrameIndex;
59    } Base;
60
61    int16_t Disp;
62    GlobalValue *GV;
63    Constant *CP;
64    BlockAddress *BlockAddr;
65    const char *ES;
66    int JT;
67    unsigned Align;    // CP alignment.
68
69    MSP430ISelAddressMode()
70      : BaseType(RegBase), Disp(0), GV(0), CP(0), BlockAddr(0),
71        ES(0), JT(-1), Align(0) {
72    }
73
74    bool hasSymbolicDisplacement() const {
75      return GV != 0 || CP != 0 || ES != 0 || JT != -1;
76    }
77
78    bool hasBaseReg() const {
79      return Base.Reg.getNode() != 0;
80    }
81
82    void setBaseReg(SDValue Reg) {
83      BaseType = RegBase;
84      Base.Reg = Reg;
85    }
86
87    void dump() {
88      errs() << "MSP430ISelAddressMode " << this << '\n';
89      if (BaseType == RegBase && Base.Reg.getNode() != 0) {
90        errs() << "Base.Reg ";
91        Base.Reg.getNode()->dump();
92      } else if (BaseType == FrameIndexBase) {
93        errs() << " Base.FrameIndex " << Base.FrameIndex << '\n';
94      }
95      errs() << " Disp " << Disp << '\n';
96      if (GV) {
97        errs() << "GV ";
98        GV->dump();
99      } else if (CP) {
100        errs() << " CP ";
101        CP->dump();
102        errs() << " Align" << Align << '\n';
103      } else if (ES) {
104        errs() << "ES ";
105        errs() << ES << '\n';
106      } else if (JT != -1)
107        errs() << " JT" << JT << " Align" << Align << '\n';
108    }
109  };
110}
111
112/// MSP430DAGToDAGISel - MSP430 specific code to select MSP430 machine
113/// instructions for SelectionDAG operations.
114///
115namespace {
116  class MSP430DAGToDAGISel : public SelectionDAGISel {
117    MSP430TargetLowering &Lowering;
118    const MSP430Subtarget &Subtarget;
119
120  public:
121    MSP430DAGToDAGISel(MSP430TargetMachine &TM, CodeGenOpt::Level OptLevel)
122      : SelectionDAGISel(TM, OptLevel),
123        Lowering(*TM.getTargetLowering()),
124        Subtarget(*TM.getSubtargetImpl()) { }
125
126    virtual void InstructionSelect();
127
128    virtual const char *getPassName() const {
129      return "MSP430 DAG->DAG Pattern Instruction Selection";
130    }
131
132    bool MatchAddress(SDValue N, MSP430ISelAddressMode &AM);
133    bool MatchWrapper(SDValue N, MSP430ISelAddressMode &AM);
134    bool MatchAddressBase(SDValue N, MSP430ISelAddressMode &AM);
135
136    bool IsLegalAndProfitableToFold(SDNode *N, SDNode *U,
137                                    SDNode *Root) const;
138
139    virtual bool
140    SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode,
141                                 std::vector<SDValue> &OutOps);
142
143    // Include the pieces autogenerated from the target description.
144  #include "MSP430GenDAGISel.inc"
145
146  private:
147    DenseMap<SDNode*, SDNode*> RMWStores;
148    void PreprocessForRMW();
149    SDNode *Select(SDValue Op);
150    SDNode *SelectIndexedLoad(SDValue Op);
151    SDNode *SelectIndexedBinOp(SDValue Op, SDValue N1, SDValue N2,
152                               unsigned Opc8, unsigned Opc16);
153
154    bool SelectAddr(SDValue Op, SDValue Addr, SDValue &Base, SDValue &Disp);
155
156  #ifndef NDEBUG
157    unsigned Indent;
158  #endif
159  };
160}  // end anonymous namespace
161
162/// createMSP430ISelDag - This pass converts a legalized DAG into a
163/// MSP430-specific DAG, ready for instruction scheduling.
164///
165FunctionPass *llvm::createMSP430ISelDag(MSP430TargetMachine &TM,
166                                        CodeGenOpt::Level OptLevel) {
167  return new MSP430DAGToDAGISel(TM, OptLevel);
168}
169
170
171/// MatchWrapper - Try to match MSP430ISD::Wrapper node into an addressing mode.
172/// These wrap things that will resolve down into a symbol reference.  If no
173/// match is possible, this returns true, otherwise it returns false.
174bool MSP430DAGToDAGISel::MatchWrapper(SDValue N, MSP430ISelAddressMode &AM) {
175  // If the addressing mode already has a symbol as the displacement, we can
176  // never match another symbol.
177  if (AM.hasSymbolicDisplacement())
178    return true;
179
180  SDValue N0 = N.getOperand(0);
181
182  if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) {
183    AM.GV = G->getGlobal();
184    AM.Disp += G->getOffset();
185    //AM.SymbolFlags = G->getTargetFlags();
186  } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N0)) {
187    AM.CP = CP->getConstVal();
188    AM.Align = CP->getAlignment();
189    AM.Disp += CP->getOffset();
190    //AM.SymbolFlags = CP->getTargetFlags();
191  } else if (ExternalSymbolSDNode *S = dyn_cast<ExternalSymbolSDNode>(N0)) {
192    AM.ES = S->getSymbol();
193    //AM.SymbolFlags = S->getTargetFlags();
194  } else if (JumpTableSDNode *J = dyn_cast<JumpTableSDNode>(N0)) {
195    AM.JT = J->getIndex();
196    //AM.SymbolFlags = J->getTargetFlags();
197  } else {
198    AM.BlockAddr = cast<BlockAddressSDNode>(N0)->getBlockAddress();
199    //AM.SymbolFlags = cast<BlockAddressSDNode>(N0)->getTargetFlags();
200  }
201  return false;
202}
203
204/// MatchAddressBase - Helper for MatchAddress. Add the specified node to the
205/// specified addressing mode without any further recursion.
206bool MSP430DAGToDAGISel::MatchAddressBase(SDValue N, MSP430ISelAddressMode &AM) {
207  // Is the base register already occupied?
208  if (AM.BaseType != MSP430ISelAddressMode::RegBase || AM.Base.Reg.getNode()) {
209    // If so, we cannot select it.
210    return true;
211  }
212
213  // Default, generate it as a register.
214  AM.BaseType = MSP430ISelAddressMode::RegBase;
215  AM.Base.Reg = N;
216  return false;
217}
218
219bool MSP430DAGToDAGISel::MatchAddress(SDValue N, MSP430ISelAddressMode &AM) {
220  DebugLoc dl = N.getDebugLoc();
221  DEBUG({
222      errs() << "MatchAddress: ";
223      AM.dump();
224    });
225
226  switch (N.getOpcode()) {
227  default: break;
228  case ISD::Constant: {
229    uint64_t Val = cast<ConstantSDNode>(N)->getSExtValue();
230    AM.Disp += Val;
231    return false;
232  }
233
234  case MSP430ISD::Wrapper:
235    if (!MatchWrapper(N, AM))
236      return false;
237    break;
238
239  case ISD::FrameIndex:
240    if (AM.BaseType == MSP430ISelAddressMode::RegBase
241        && AM.Base.Reg.getNode() == 0) {
242      AM.BaseType = MSP430ISelAddressMode::FrameIndexBase;
243      AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex();
244      return false;
245    }
246    break;
247
248  case ISD::ADD: {
249    MSP430ISelAddressMode Backup = AM;
250    if (!MatchAddress(N.getNode()->getOperand(0), AM) &&
251        !MatchAddress(N.getNode()->getOperand(1), AM))
252      return false;
253    AM = Backup;
254    if (!MatchAddress(N.getNode()->getOperand(1), AM) &&
255        !MatchAddress(N.getNode()->getOperand(0), AM))
256      return false;
257    AM = Backup;
258
259    break;
260  }
261
262  case ISD::OR:
263    // Handle "X | C" as "X + C" iff X is known to have C bits clear.
264    if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) {
265      MSP430ISelAddressMode Backup = AM;
266      uint64_t Offset = CN->getSExtValue();
267      // Start with the LHS as an addr mode.
268      if (!MatchAddress(N.getOperand(0), AM) &&
269          // Address could not have picked a GV address for the displacement.
270          AM.GV == NULL &&
271          // Check to see if the LHS & C is zero.
272          CurDAG->MaskedValueIsZero(N.getOperand(0), CN->getAPIntValue())) {
273        AM.Disp += Offset;
274        return false;
275      }
276      AM = Backup;
277    }
278    break;
279  }
280
281  return MatchAddressBase(N, AM);
282}
283
284/// SelectAddr - returns true if it is able pattern match an addressing mode.
285/// It returns the operands which make up the maximal addressing mode it can
286/// match by reference.
287bool MSP430DAGToDAGISel::SelectAddr(SDValue Op, SDValue N,
288                                    SDValue &Base, SDValue &Disp) {
289  MSP430ISelAddressMode AM;
290
291  if (MatchAddress(N, AM))
292    return false;
293
294  EVT VT = N.getValueType();
295  if (AM.BaseType == MSP430ISelAddressMode::RegBase) {
296    if (!AM.Base.Reg.getNode())
297      AM.Base.Reg = CurDAG->getRegister(0, VT);
298  }
299
300  Base  = (AM.BaseType == MSP430ISelAddressMode::FrameIndexBase) ?
301    CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, TLI.getPointerTy()) :
302    AM.Base.Reg;
303
304  if (AM.GV)
305    Disp = CurDAG->getTargetGlobalAddress(AM.GV, MVT::i16, AM.Disp,
306                                          0/*AM.SymbolFlags*/);
307  else if (AM.CP)
308    Disp = CurDAG->getTargetConstantPool(AM.CP, MVT::i16,
309                                         AM.Align, AM.Disp, 0/*AM.SymbolFlags*/);
310  else if (AM.ES)
311    Disp = CurDAG->getTargetExternalSymbol(AM.ES, MVT::i16, 0/*AM.SymbolFlags*/);
312  else if (AM.JT != -1)
313    Disp = CurDAG->getTargetJumpTable(AM.JT, MVT::i16, 0/*AM.SymbolFlags*/);
314  else if (AM.BlockAddr)
315    Disp = CurDAG->getBlockAddress(AM.BlockAddr, MVT::i32,
316                                   true, 0/*AM.SymbolFlags*/);
317  else
318    Disp = CurDAG->getTargetConstant(AM.Disp, MVT::i16);
319
320  return true;
321}
322
323bool MSP430DAGToDAGISel::
324SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode,
325                             std::vector<SDValue> &OutOps) {
326  SDValue Op0, Op1;
327  switch (ConstraintCode) {
328  default: return true;
329  case 'm':   // memory
330    if (!SelectAddr(Op, Op, Op0, Op1))
331      return true;
332    break;
333  }
334
335  OutOps.push_back(Op0);
336  OutOps.push_back(Op1);
337  return false;
338}
339
340bool MSP430DAGToDAGISel::IsLegalAndProfitableToFold(SDNode *N, SDNode *U,
341                                                    SDNode *Root) const {
342  if (OptLevel == CodeGenOpt::None) return false;
343
344  /// RMW preprocessing creates the following code:
345  ///         [Load1]
346  ///         ^     ^
347  ///        /      |
348  ///       /       |
349  ///       [Load2] |
350  ///       ^    ^  |
351  ///       |    |  |
352  ///       |     \-|
353  ///       |       |
354  ///       |     [Op]
355  ///       |       ^
356  ///       |       |
357  ///       \      /
358  ///        \    /
359  ///       [Store]
360  ///
361  /// The path Store => Load2 => Load1 is via chain. Note that in general it is
362  /// not allowed to fold Load1 into Op (and Store) since it will creates a
363  /// cycle. However, this is perfectly legal for the loads moved below the
364  /// TokenFactor by PreprocessForRMW. Query the map Store => Load1 (created
365  /// during preprocessing) to determine whether it's legal to introduce such
366  /// "cycle" for a moment.
367  DenseMap<SDNode*, SDNode*>::const_iterator I = RMWStores.find(Root);
368  if (I != RMWStores.end() && I->second == N)
369    return true;
370
371  // Proceed to 'generic' cycle finder code
372  return SelectionDAGISel::IsLegalAndProfitableToFold(N, U, Root);
373}
374
375
376/// MoveBelowTokenFactor - Replace TokenFactor operand with load's chain operand
377/// and move load below the TokenFactor. Replace store's chain operand with
378/// load's chain result.
379static void MoveBelowTokenFactor(SelectionDAG *CurDAG, SDValue Load,
380                                 SDValue Store, SDValue TF) {
381  SmallVector<SDValue, 4> Ops;
382  for (unsigned i = 0, e = TF.getNode()->getNumOperands(); i != e; ++i)
383    if (Load.getNode() == TF.getOperand(i).getNode())
384      Ops.push_back(Load.getOperand(0));
385    else
386      Ops.push_back(TF.getOperand(i));
387  SDValue NewTF = CurDAG->UpdateNodeOperands(TF, &Ops[0], Ops.size());
388  SDValue NewLoad = CurDAG->UpdateNodeOperands(Load, NewTF,
389                                               Load.getOperand(1),
390                                               Load.getOperand(2));
391  CurDAG->UpdateNodeOperands(Store, NewLoad.getValue(1), Store.getOperand(1),
392                             Store.getOperand(2), Store.getOperand(3));
393}
394
395/// MoveBelowTokenFactor2 - Replace TokenFactor operand with load's chain operand
396/// and move load below the TokenFactor. Replace store's chain operand with
397/// load's chain result. This a version which sinks two loads below token factor.
398/// Look into PreprocessForRMW comments for explanation of transform.
399static void MoveBelowTokenFactor2(SelectionDAG *CurDAG,
400                                  SDValue Load1, SDValue Load2,
401                                  SDValue Store, SDValue TF) {
402  SmallVector<SDValue, 4> Ops;
403  for (unsigned i = 0, e = TF.getNode()->getNumOperands(); i != e; ++i) {
404    SDNode* N = TF.getOperand(i).getNode();
405    if (Load2.getNode() == N)
406      Ops.push_back(Load2.getOperand(0));
407    else if (Load1.getNode() != N)
408      Ops.push_back(TF.getOperand(i));
409  }
410
411  SDValue NewTF = SDValue(CurDAG->MorphNodeTo(TF.getNode(),
412                                  TF.getOpcode(),
413                                  TF.getNode()->getVTList(),
414                                  &Ops[0], Ops.size()), TF.getResNo());
415  SDValue NewLoad2 = CurDAG->UpdateNodeOperands(Load2, NewTF,
416                                                Load2.getOperand(1),
417                                                Load2.getOperand(2));
418
419  SDValue NewLoad1 = CurDAG->UpdateNodeOperands(Load1, NewLoad2.getValue(1),
420                                                Load1.getOperand(1),
421                                                Load1.getOperand(2));
422
423  CurDAG->UpdateNodeOperands(Store,
424                             NewLoad1.getValue(1),
425                             Store.getOperand(1),
426                             Store.getOperand(2), Store.getOperand(3));
427}
428
429/// isAllowedToSink - return true if N a load which can be moved below token
430/// factor. Basically, the load should be non-volatile and has single use.
431static bool isLoadAllowedToSink(SDValue N, SDValue Chain) {
432  if (N.getOpcode() == ISD::BIT_CONVERT)
433    N = N.getOperand(0);
434
435  LoadSDNode *LD = dyn_cast<LoadSDNode>(N);
436  if (!LD || LD->isVolatile())
437    return false;
438  if (LD->getAddressingMode() != ISD::UNINDEXED)
439    return false;
440
441  ISD::LoadExtType ExtType = LD->getExtensionType();
442  if (ExtType != ISD::NON_EXTLOAD && ExtType != ISD::EXTLOAD)
443    return false;
444
445  return (N.hasOneUse() &&
446          LD->hasNUsesOfValue(1, 1) &&
447          LD->isOperandOf(Chain.getNode()));
448}
449
450
451/// isRMWLoad - Return true if N is a load that's part of RMW sub-DAG.
452/// The chain produced by the load must only be used by the store's chain
453/// operand, otherwise this may produce a cycle in the DAG.
454static bool isRMWLoad(SDValue N, SDValue Chain, SDValue Address,
455                      SDValue &Load) {
456  if (isLoadAllowedToSink(N, Chain) &&
457      N.getOperand(1) == Address) {
458    Load = N;
459    return true;
460  }
461  return false;
462}
463
464/// PreprocessForRMW - Preprocess the DAG to make instruction selection better.
465/// This is only run if not in -O0 mode.
466/// This allows the instruction selector to pick more read-modify-write
467/// instructions. This is a common case:
468///
469///     [Load chain]
470///         ^
471///         |
472///       [Load]
473///       ^    ^
474///       |    |
475///      /      \-
476///     /         |
477/// [TokenFactor] [Op]
478///     ^          ^
479///     |          |
480///      \        /
481///       \      /
482///       [Store]
483///
484/// The fact the store's chain operand != load's chain will prevent the
485/// (store (op (load))) instruction from being selected. We can transform it to:
486///
487///     [Load chain]
488///         ^
489///         |
490///    [TokenFactor]
491///         ^
492///         |
493///       [Load]
494///       ^    ^
495///       |    |
496///       |     \-
497///       |       |
498///       |     [Op]
499///       |       ^
500///       |       |
501///       \      /
502///        \    /
503///       [Store]
504///
505/// We also recognize the case where second operand of Op is load as well and
506/// move it below token factor as well creating DAG as follows:
507///
508///       [Load chain]
509///            ^
510///            |
511///      [TokenFactor]
512///            ^
513///            |
514///         [Load1]
515///         ^     ^
516///        /      |
517///       /       |
518///       [Load2] |
519///       ^    ^  |
520///       |    |  |
521///       |     \-|
522///       |       |
523///       |     [Op]
524///       |       ^
525///       |       |
526///       \      /
527///        \    /
528///       [Store]
529///
530/// This allows selection of mem-mem instructions. Yay!
531
532void MSP430DAGToDAGISel::PreprocessForRMW() {
533  for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
534         E = CurDAG->allnodes_end(); I != E; ++I) {
535    if (!ISD::isNON_TRUNCStore(I))
536      continue;
537    SDValue Chain = I->getOperand(0);
538
539    if (Chain.getNode()->getOpcode() != ISD::TokenFactor)
540      continue;
541
542    SDValue N1 = I->getOperand(1);
543    SDValue N2 = I->getOperand(2);
544    if ((N1.getValueType().isFloatingPoint() &&
545         !N1.getValueType().isVector()) ||
546        !N1.hasOneUse())
547      continue;
548
549    unsigned RModW = 0;
550    SDValue Load1, Load2;
551    unsigned Opcode = N1.getNode()->getOpcode();
552    switch (Opcode) {
553    case ISD::ADD:
554    case ISD::AND:
555    case ISD::OR:
556    case ISD::XOR:
557    case ISD::ADDC:
558    case ISD::ADDE: {
559      SDValue N10 = N1.getOperand(0);
560      SDValue N11 = N1.getOperand(1);
561      if (isRMWLoad(N10, Chain, N2, Load1)) {
562        if (isLoadAllowedToSink(N11, Chain)) {
563          Load2 = N11;
564          RModW = 2;
565        } else
566          RModW = 1;
567      } else if (isRMWLoad(N11, Chain, N2, Load1)) {
568        if (isLoadAllowedToSink(N10, Chain)) {
569          Load2 = N10;
570          RModW = 2;
571        } else
572          RModW = 1;
573      }
574      break;
575    }
576    case ISD::SUB:
577    case ISD::SUBC:
578    case ISD::SUBE: {
579      SDValue N10 = N1.getOperand(0);
580      SDValue N11 = N1.getOperand(1);
581      if (isRMWLoad(N10, Chain, N2, Load1)) {
582        if (isLoadAllowedToSink(N11, Chain)) {
583          Load2 = N11;
584          RModW = 2;
585        } else
586          RModW = 1;
587      }
588      break;
589    }
590    }
591
592    NumLoadMoved += RModW;
593    if (RModW == 1)
594      MoveBelowTokenFactor(CurDAG, Load1, SDValue(I, 0), Chain);
595    else if (RModW == 2) {
596      MoveBelowTokenFactor2(CurDAG, Load1, Load2, SDValue(I, 0), Chain);
597      SDNode* Store = I;
598      RMWStores[Store] = Load2.getNode();
599    }
600  }
601}
602
603
604static bool isValidIndexedLoad(const LoadSDNode *LD) {
605  ISD::MemIndexedMode AM = LD->getAddressingMode();
606  if (AM != ISD::POST_INC || LD->getExtensionType() != ISD::NON_EXTLOAD)
607    return false;
608
609  EVT VT = LD->getMemoryVT();
610
611  switch (VT.getSimpleVT().SimpleTy) {
612  case MVT::i8:
613    // Sanity check
614    if (cast<ConstantSDNode>(LD->getOffset())->getZExtValue() != 1)
615      return false;
616
617    break;
618  case MVT::i16:
619    // Sanity check
620    if (cast<ConstantSDNode>(LD->getOffset())->getZExtValue() != 2)
621      return false;
622
623    break;
624  default:
625    return false;
626  }
627
628  return true;
629}
630
631SDNode *MSP430DAGToDAGISel::SelectIndexedLoad(SDValue Op) {
632  LoadSDNode *LD = cast<LoadSDNode>(Op);
633  if (!isValidIndexedLoad(LD))
634    return NULL;
635
636  MVT VT = LD->getMemoryVT().getSimpleVT();
637
638  unsigned Opcode = 0;
639  switch (VT.SimpleTy) {
640  case MVT::i8:
641    Opcode = MSP430::MOV8rm_POST;
642    break;
643  case MVT::i16:
644    Opcode = MSP430::MOV16rm_POST;
645    break;
646  default:
647    return NULL;
648  }
649
650   return CurDAG->getMachineNode(Opcode, Op.getDebugLoc(),
651                                 VT, MVT::i16, MVT::Other,
652                                 LD->getBasePtr(), LD->getChain());
653}
654
655SDNode *MSP430DAGToDAGISel::SelectIndexedBinOp(SDValue Op,
656                                               SDValue N1, SDValue N2,
657                                               unsigned Opc8, unsigned Opc16) {
658  if (N1.getOpcode() == ISD::LOAD &&
659      N1.hasOneUse() &&
660      IsLegalAndProfitableToFold(N1.getNode(), Op.getNode(), Op.getNode())) {
661    LoadSDNode *LD = cast<LoadSDNode>(N1);
662    if (!isValidIndexedLoad(LD))
663      return NULL;
664
665    MVT VT = LD->getMemoryVT().getSimpleVT();
666    unsigned Opc = (VT == MVT::i16 ? Opc16 : Opc8);
667    MachineSDNode::mmo_iterator MemRefs0 = MF->allocateMemRefsArray(1);
668    MemRefs0[0] = cast<MemSDNode>(N1)->getMemOperand();
669    SDValue Ops0[] = { N2, LD->getBasePtr(), LD->getChain() };
670    SDNode *ResNode =
671      CurDAG->SelectNodeTo(Op.getNode(), Opc,
672                           VT, MVT::i16, MVT::Other,
673                           Ops0, 3);
674    cast<MachineSDNode>(ResNode)->setMemRefs(MemRefs0, MemRefs0 + 1);
675    // Transfer chain.
676    ReplaceUses(SDValue(N1.getNode(), 2), SDValue(ResNode, 2));
677    // Transfer writeback.
678    ReplaceUses(SDValue(N1.getNode(), 1), SDValue(ResNode, 1));
679    return ResNode;
680  }
681
682  return NULL;
683}
684
685
686/// InstructionSelect - This callback is invoked by
687/// SelectionDAGISel when it has created a SelectionDAG for us to codegen.
688void MSP430DAGToDAGISel::InstructionSelect() {
689  std::string BlockName;
690  if (ViewRMWDAGs)
691    BlockName = MF->getFunction()->getNameStr() + ":" +
692                BB->getBasicBlock()->getNameStr();
693
694  PreprocessForRMW();
695
696  if (ViewRMWDAGs) CurDAG->viewGraph("RMW preprocessed:" + BlockName);
697
698  DEBUG(errs() << "Selection DAG after RMW preprocessing:\n");
699  DEBUG(CurDAG->dump());
700
701  // Codegen the basic block.
702  DEBUG(errs() << "===== Instruction selection begins:\n");
703  DEBUG(Indent = 0);
704  SelectRoot(*CurDAG);
705  DEBUG(errs() << "===== Instruction selection ends:\n");
706
707  CurDAG->RemoveDeadNodes();
708  RMWStores.clear();
709}
710
711SDNode *MSP430DAGToDAGISel::Select(SDValue Op) {
712  SDNode *Node = Op.getNode();
713  DebugLoc dl = Op.getDebugLoc();
714
715  // Dump information about the Node being selected
716  DEBUG(errs().indent(Indent) << "Selecting: ");
717  DEBUG(Node->dump(CurDAG));
718  DEBUG(errs() << "\n");
719  DEBUG(Indent += 2);
720
721  // If we have a custom node, we already have selected!
722  if (Node->isMachineOpcode()) {
723    DEBUG(errs().indent(Indent-2) << "== ";
724          Node->dump(CurDAG);
725          errs() << "\n");
726    DEBUG(Indent -= 2);
727    return NULL;
728  }
729
730  // Few custom selection stuff.
731  switch (Node->getOpcode()) {
732  default: break;
733  case ISD::FrameIndex: {
734    assert(Op.getValueType() == MVT::i16);
735    int FI = cast<FrameIndexSDNode>(Node)->getIndex();
736    SDValue TFI = CurDAG->getTargetFrameIndex(FI, MVT::i16);
737    if (Node->hasOneUse())
738      return CurDAG->SelectNodeTo(Node, MSP430::ADD16ri, MVT::i16,
739                                  TFI, CurDAG->getTargetConstant(0, MVT::i16));
740    return CurDAG->getMachineNode(MSP430::ADD16ri, dl, MVT::i16,
741                                  TFI, CurDAG->getTargetConstant(0, MVT::i16));
742  }
743  case ISD::LOAD:
744    if (SDNode *ResNode = SelectIndexedLoad(Op))
745      return ResNode;
746    // Other cases are autogenerated.
747    break;
748  case ISD::ADD:
749    if (SDNode *ResNode =
750        SelectIndexedBinOp(Op,
751                           Op.getOperand(0), Op.getOperand(1),
752                           MSP430::ADD8rm_POST, MSP430::ADD16rm_POST))
753      return ResNode;
754    else if (SDNode *ResNode =
755             SelectIndexedBinOp(Op, Op.getOperand(1), Op.getOperand(0),
756                                MSP430::ADD8rm_POST, MSP430::ADD16rm_POST))
757      return ResNode;
758
759    // Other cases are autogenerated.
760    break;
761  case ISD::SUB:
762    if (SDNode *ResNode =
763        SelectIndexedBinOp(Op,
764                           Op.getOperand(0), Op.getOperand(1),
765                           MSP430::SUB8rm_POST, MSP430::SUB16rm_POST))
766      return ResNode;
767
768    // Other cases are autogenerated.
769    break;
770  case ISD::AND:
771    if (SDNode *ResNode =
772        SelectIndexedBinOp(Op,
773                           Op.getOperand(0), Op.getOperand(1),
774                           MSP430::AND8rm_POST, MSP430::AND16rm_POST))
775      return ResNode;
776    else if (SDNode *ResNode =
777             SelectIndexedBinOp(Op, Op.getOperand(1), Op.getOperand(0),
778                                MSP430::AND8rm_POST, MSP430::AND16rm_POST))
779      return ResNode;
780
781    // Other cases are autogenerated.
782    break;
783  case ISD::OR:
784    if (SDNode *ResNode =
785        SelectIndexedBinOp(Op,
786                           Op.getOperand(0), Op.getOperand(1),
787                           MSP430::OR8rm_POST, MSP430::OR16rm_POST))
788      return ResNode;
789    else if (SDNode *ResNode =
790             SelectIndexedBinOp(Op, Op.getOperand(1), Op.getOperand(0),
791                                MSP430::OR8rm_POST, MSP430::OR16rm_POST))
792      return ResNode;
793
794    // Other cases are autogenerated.
795    break;
796  case ISD::XOR:
797    if (SDNode *ResNode =
798        SelectIndexedBinOp(Op,
799                           Op.getOperand(0), Op.getOperand(1),
800                           MSP430::XOR8rm_POST, MSP430::XOR16rm_POST))
801      return ResNode;
802    else if (SDNode *ResNode =
803             SelectIndexedBinOp(Op, Op.getOperand(1), Op.getOperand(0),
804                                MSP430::XOR8rm_POST, MSP430::XOR16rm_POST))
805      return ResNode;
806
807    // Other cases are autogenerated.
808    break;
809  }
810
811  // Select the default instruction
812  SDNode *ResNode = SelectCode(Op);
813
814  DEBUG(errs() << std::string(Indent-2, ' ') << "=> ");
815  if (ResNode == NULL || ResNode == Op.getNode())
816    DEBUG(Op.getNode()->dump(CurDAG));
817  else
818    DEBUG(ResNode->dump(CurDAG));
819  DEBUG(errs() << "\n");
820  DEBUG(Indent -= 2);
821
822  return ResNode;
823}
824