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 (Base.Reg.getNode() != 0) {
  90         errs() << "Base.Reg ";
  91         Base.Reg.getNode()->dump();
  92       } else {
  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(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 ///
 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   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.
 287 bool 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
 323 bool MSP430DAGToDAGISel::
 324 SelectInlineAsmMemoryOperand(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
 340 bool 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.
 379 static 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.
 399 static 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.
 431 static 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.
 454 static 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
 532 void 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
 604 static 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
 631 SDNode *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
 655 SDNode *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.
 688 void 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
 711 SDNode *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 }