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