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