MSP430ISelDAGToDAG.cpp revision 201360
1264790Sbapt//===-- MSP430ISelDAGToDAG.cpp - A dag to dag inst selector for MSP430 ----===// 2264790Sbapt// 3264790Sbapt// The LLVM Compiler Infrastructure 4264790Sbapt// 5264790Sbapt// This file is distributed under the University of Illinois Open Source 6264790Sbapt// License. See LICENSE.TXT for details. 7264790Sbapt// 8264790Sbapt//===----------------------------------------------------------------------===// 9264790Sbapt// 10264790Sbapt// This file defines an instruction selector for the MSP430 target. 11264790Sbapt// 12264790Sbapt//===----------------------------------------------------------------------===// 13264790Sbapt 14264790Sbapt#include "MSP430.h" 15264790Sbapt#include "MSP430ISelLowering.h" 16264790Sbapt#include "MSP430TargetMachine.h" 17264790Sbapt#include "llvm/DerivedTypes.h" 18264790Sbapt#include "llvm/Function.h" 19264790Sbapt#include "llvm/Intrinsics.h" 20264790Sbapt#include "llvm/CallingConv.h" 21264790Sbapt#include "llvm/Constants.h" 22264790Sbapt#include "llvm/CodeGen/MachineFrameInfo.h" 23264790Sbapt#include "llvm/CodeGen/MachineFunction.h" 24264790Sbapt#include "llvm/CodeGen/MachineInstrBuilder.h" 25264790Sbapt#include "llvm/CodeGen/MachineRegisterInfo.h" 26264790Sbapt#include "llvm/CodeGen/SelectionDAG.h" 27264790Sbapt#include "llvm/CodeGen/SelectionDAGISel.h" 28264790Sbapt#include "llvm/Target/TargetLowering.h" 29264790Sbapt#include "llvm/Support/CommandLine.h" 30264790Sbapt#include "llvm/Support/Compiler.h" 31264790Sbapt#include "llvm/Support/Debug.h" 32264790Sbapt#include "llvm/Support/ErrorHandling.h" 33264790Sbapt#include "llvm/Support/raw_ostream.h" 34264790Sbapt#include "llvm/ADT/Statistic.h" 35264790Sbapt 36264790Sbaptusing namespace llvm; 37264790Sbapt 38264790Sbapt#ifndef NDEBUG 39264790Sbaptstatic cl::opt<bool> 40264790SbaptViewRMWDAGs("view-msp430-rmw-dags", cl::Hidden, 41264790Sbapt cl::desc("Pop up a window to show isel dags after RMW preprocess")); 42264790Sbapt#else 43264790Sbaptstatic const bool ViewRMWDAGs = false; 44264790Sbapt#endif 45264790Sbapt 46264790SbaptSTATISTIC(NumLoadMoved, "Number of loads moved below TokenFactor"); 47264790Sbapt 48264790Sbapt 49264790Sbaptnamespace { 50264790Sbapt struct MSP430ISelAddressMode { 51264790Sbapt enum { 52264790Sbapt RegBase, 53264790Sbapt FrameIndexBase 54264790Sbapt } BaseType; 55264790Sbapt 56264790Sbapt struct { // This is really a union, discriminated by BaseType! 57264790Sbapt SDValue Reg; 58264790Sbapt int FrameIndex; 59264790Sbapt } Base; 60264790Sbapt 61264790Sbapt int16_t Disp; 62264790Sbapt GlobalValue *GV; 63264790Sbapt Constant *CP; 64264790Sbapt BlockAddress *BlockAddr; 65264790Sbapt const char *ES; 66264790Sbapt int JT; 67264790Sbapt unsigned Align; // CP alignment. 68264790Sbapt 69264790Sbapt MSP430ISelAddressMode() 70264790Sbapt : BaseType(RegBase), Disp(0), GV(0), CP(0), BlockAddr(0), 71264790Sbapt ES(0), JT(-1), Align(0) { 72264790Sbapt } 73264790Sbapt 74264790Sbapt bool hasSymbolicDisplacement() const { 75264790Sbapt return GV != 0 || CP != 0 || ES != 0 || JT != -1; 76264790Sbapt } 77264790Sbapt 78264790Sbapt bool hasBaseReg() const { 79264790Sbapt return Base.Reg.getNode() != 0; 80264790Sbapt } 81264790Sbapt 82264790Sbapt void setBaseReg(SDValue Reg) { 83264790Sbapt BaseType = RegBase; 84264790Sbapt Base.Reg = Reg; 85264790Sbapt } 86264790Sbapt 87264790Sbapt void dump() { 88264790Sbapt errs() << "MSP430ISelAddressMode " << this << '\n'; 89264790Sbapt if (BaseType == RegBase && Base.Reg.getNode() != 0) { 90264790Sbapt errs() << "Base.Reg "; 91264790Sbapt Base.Reg.getNode()->dump(); 92264790Sbapt } else if (BaseType == FrameIndexBase) { 93264790Sbapt errs() << " Base.FrameIndex " << Base.FrameIndex << '\n'; 94264790Sbapt } 95264790Sbapt errs() << " Disp " << Disp << '\n'; 96264790Sbapt if (GV) { 97264790Sbapt errs() << "GV "; 98264790Sbapt GV->dump(); 99264790Sbapt } else if (CP) { 100264790Sbapt errs() << " CP "; 101264790Sbapt CP->dump(); 102264790Sbapt errs() << " Align" << Align << '\n'; 103264790Sbapt } else if (ES) { 104264790Sbapt errs() << "ES "; 105264790Sbapt errs() << ES << '\n'; 106264790Sbapt } else if (JT != -1) 107264790Sbapt errs() << " JT" << JT << " Align" << Align << '\n'; 108264790Sbapt } 109264790Sbapt }; 110264790Sbapt} 111264790Sbapt 112264790Sbapt/// MSP430DAGToDAGISel - MSP430 specific code to select MSP430 machine 113264790Sbapt/// instructions for SelectionDAG operations. 114264790Sbapt/// 115264790Sbaptnamespace { 116264790Sbapt class MSP430DAGToDAGISel : public SelectionDAGISel { 117264790Sbapt MSP430TargetLowering &Lowering; 118264790Sbapt const MSP430Subtarget &Subtarget; 119264790Sbapt 120264790Sbapt public: 121264790Sbapt MSP430DAGToDAGISel(MSP430TargetMachine &TM, CodeGenOpt::Level OptLevel) 122264790Sbapt : SelectionDAGISel(TM, OptLevel), 123264790Sbapt Lowering(*TM.getTargetLowering()), 124264790Sbapt Subtarget(*TM.getSubtargetImpl()) { } 125264790Sbapt 126264790Sbapt virtual void InstructionSelect(); 127264790Sbapt 128264790Sbapt virtual const char *getPassName() const { 129264790Sbapt return "MSP430 DAG->DAG Pattern Instruction Selection"; 130264790Sbapt } 131264790Sbapt 132264790Sbapt bool MatchAddress(SDValue N, MSP430ISelAddressMode &AM); 133264790Sbapt bool MatchWrapper(SDValue N, MSP430ISelAddressMode &AM); 134264790Sbapt bool MatchAddressBase(SDValue N, MSP430ISelAddressMode &AM); 135264790Sbapt 136264790Sbapt bool IsLegalAndProfitableToFold(SDNode *N, SDNode *U, 137264790Sbapt SDNode *Root) const; 138264790Sbapt 139264790Sbapt virtual bool 140264790Sbapt SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode, 141264790Sbapt std::vector<SDValue> &OutOps); 142264790Sbapt 143264790Sbapt // Include the pieces autogenerated from the target description. 144264790Sbapt #include "MSP430GenDAGISel.inc" 145264790Sbapt 146264790Sbapt private: 147264790Sbapt DenseMap<SDNode*, SDNode*> RMWStores; 148264790Sbapt void PreprocessForRMW(); 149264790Sbapt SDNode *Select(SDValue Op); 150264790Sbapt SDNode *SelectIndexedLoad(SDValue Op); 151264790Sbapt SDNode *SelectIndexedBinOp(SDValue Op, SDValue N1, SDValue N2, 152264790Sbapt unsigned Opc8, unsigned Opc16); 153264790Sbapt 154264790Sbapt bool SelectAddr(SDValue Op, SDValue Addr, SDValue &Base, SDValue &Disp); 155264790Sbapt 156264790Sbapt #ifndef NDEBUG 157264790Sbapt unsigned Indent; 158264790Sbapt #endif 159264790Sbapt }; 160264790Sbapt} // end anonymous namespace 161264790Sbapt 162264790Sbapt/// createMSP430ISelDag - This pass converts a legalized DAG into a 163264790Sbapt/// MSP430-specific DAG, ready for instruction scheduling. 164264790Sbapt/// 165264790SbaptFunctionPass *llvm::createMSP430ISelDag(MSP430TargetMachine &TM, 166264790Sbapt CodeGenOpt::Level OptLevel) { 167264790Sbapt return new MSP430DAGToDAGISel(TM, OptLevel); 168264790Sbapt} 169264790Sbapt 170264790Sbapt 171264790Sbapt/// MatchWrapper - Try to match MSP430ISD::Wrapper node into an addressing mode. 172264790Sbapt/// These wrap things that will resolve down into a symbol reference. If no 173264790Sbapt/// match is possible, this returns true, otherwise it returns false. 174264790Sbaptbool MSP430DAGToDAGISel::MatchWrapper(SDValue N, MSP430ISelAddressMode &AM) { 175264790Sbapt // If the addressing mode already has a symbol as the displacement, we can 176264790Sbapt // never match another symbol. 177264790Sbapt if (AM.hasSymbolicDisplacement()) 178264790Sbapt return true; 179264790Sbapt 180264790Sbapt SDValue N0 = N.getOperand(0); 181264790Sbapt 182264790Sbapt if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) { 183264790Sbapt AM.GV = G->getGlobal(); 184264790Sbapt AM.Disp += G->getOffset(); 185264790Sbapt //AM.SymbolFlags = G->getTargetFlags(); 186264790Sbapt } else if (ConstantPoolSDNode *CP = dyn_cast<ConstantPoolSDNode>(N0)) { 187264790Sbapt AM.CP = CP->getConstVal(); 188264790Sbapt AM.Align = CP->getAlignment(); 189264790Sbapt AM.Disp += CP->getOffset(); 190264790Sbapt //AM.SymbolFlags = CP->getTargetFlags(); 191264790Sbapt } else if (ExternalSymbolSDNode *S = dyn_cast<ExternalSymbolSDNode>(N0)) { 192264790Sbapt AM.ES = S->getSymbol(); 193264790Sbapt //AM.SymbolFlags = S->getTargetFlags(); 194264790Sbapt } else if (JumpTableSDNode *J = dyn_cast<JumpTableSDNode>(N0)) { 195264790Sbapt AM.JT = J->getIndex(); 196264790Sbapt //AM.SymbolFlags = J->getTargetFlags(); 197264790Sbapt } else { 198264790Sbapt AM.BlockAddr = cast<BlockAddressSDNode>(N0)->getBlockAddress(); 199264790Sbapt //AM.SymbolFlags = cast<BlockAddressSDNode>(N0)->getTargetFlags(); 200264790Sbapt } 201264790Sbapt return false; 202264790Sbapt} 203264790Sbapt 204264790Sbapt/// MatchAddressBase - Helper for MatchAddress. Add the specified node to the 205264790Sbapt/// specified addressing mode without any further recursion. 206264790Sbaptbool MSP430DAGToDAGISel::MatchAddressBase(SDValue N, MSP430ISelAddressMode &AM) { 207264790Sbapt // Is the base register already occupied? 208264790Sbapt if (AM.BaseType != MSP430ISelAddressMode::RegBase || AM.Base.Reg.getNode()) { 209264790Sbapt // If so, we cannot select it. 210264790Sbapt return true; 211264790Sbapt } 212264790Sbapt 213264790Sbapt // Default, generate it as a register. 214264790Sbapt AM.BaseType = MSP430ISelAddressMode::RegBase; 215264790Sbapt AM.Base.Reg = N; 216264790Sbapt return false; 217264790Sbapt} 218264790Sbapt 219264790Sbaptbool MSP430DAGToDAGISel::MatchAddress(SDValue N, MSP430ISelAddressMode &AM) { 220264790Sbapt DEBUG({ 221264790Sbapt errs() << "MatchAddress: "; 222264790Sbapt AM.dump(); 223264790Sbapt }); 224264790Sbapt 225264790Sbapt switch (N.getOpcode()) { 226264790Sbapt default: break; 227264790Sbapt case ISD::Constant: { 228264790Sbapt uint64_t Val = cast<ConstantSDNode>(N)->getSExtValue(); 229264790Sbapt AM.Disp += Val; 230264790Sbapt return false; 231264790Sbapt } 232264790Sbapt 233264790Sbapt case MSP430ISD::Wrapper: 234264790Sbapt if (!MatchWrapper(N, AM)) 235264790Sbapt return false; 236264790Sbapt break; 237264790Sbapt 238264790Sbapt case ISD::FrameIndex: 239264790Sbapt if (AM.BaseType == MSP430ISelAddressMode::RegBase 240264790Sbapt && AM.Base.Reg.getNode() == 0) { 241264790Sbapt AM.BaseType = MSP430ISelAddressMode::FrameIndexBase; 242264790Sbapt AM.Base.FrameIndex = cast<FrameIndexSDNode>(N)->getIndex(); 243264790Sbapt return false; 244264790Sbapt } 245264790Sbapt break; 246264790Sbapt 247264790Sbapt case ISD::ADD: { 248264790Sbapt MSP430ISelAddressMode Backup = AM; 249264790Sbapt if (!MatchAddress(N.getNode()->getOperand(0), AM) && 250264790Sbapt !MatchAddress(N.getNode()->getOperand(1), AM)) 251264790Sbapt return false; 252264790Sbapt AM = Backup; 253264790Sbapt if (!MatchAddress(N.getNode()->getOperand(1), AM) && 254264790Sbapt !MatchAddress(N.getNode()->getOperand(0), AM)) 255264790Sbapt return false; 256264790Sbapt AM = Backup; 257264790Sbapt 258264790Sbapt break; 259264790Sbapt } 260264790Sbapt 261264790Sbapt case ISD::OR: 262264790Sbapt // Handle "X | C" as "X + C" iff X is known to have C bits clear. 263264790Sbapt if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(N.getOperand(1))) { 264264790Sbapt MSP430ISelAddressMode Backup = AM; 265264790Sbapt uint64_t Offset = CN->getSExtValue(); 266264790Sbapt // Start with the LHS as an addr mode. 267264790Sbapt if (!MatchAddress(N.getOperand(0), AM) && 268264790Sbapt // Address could not have picked a GV address for the displacement. 269264790Sbapt AM.GV == NULL && 270264790Sbapt // Check to see if the LHS & C is zero. 271264790Sbapt CurDAG->MaskedValueIsZero(N.getOperand(0), CN->getAPIntValue())) { 272264790Sbapt AM.Disp += Offset; 273264790Sbapt return false; 274264790Sbapt } 275264790Sbapt AM = Backup; 276264790Sbapt } 277264790Sbapt break; 278264790Sbapt } 279264790Sbapt 280264790Sbapt return MatchAddressBase(N, AM); 281264790Sbapt} 282264790Sbapt 283264790Sbapt/// SelectAddr - returns true if it is able pattern match an addressing mode. 284264790Sbapt/// It returns the operands which make up the maximal addressing mode it can 285264790Sbapt/// match by reference. 286264790Sbaptbool MSP430DAGToDAGISel::SelectAddr(SDValue Op, SDValue N, 287264790Sbapt SDValue &Base, SDValue &Disp) { 288264790Sbapt MSP430ISelAddressMode AM; 289264790Sbapt 290264790Sbapt if (MatchAddress(N, AM)) 291264790Sbapt return false; 292264790Sbapt 293264790Sbapt EVT VT = N.getValueType(); 294264790Sbapt if (AM.BaseType == MSP430ISelAddressMode::RegBase) { 295264790Sbapt if (!AM.Base.Reg.getNode()) 296264790Sbapt AM.Base.Reg = CurDAG->getRegister(0, VT); 297264790Sbapt } 298264790Sbapt 299264790Sbapt Base = (AM.BaseType == MSP430ISelAddressMode::FrameIndexBase) ? 300264790Sbapt CurDAG->getTargetFrameIndex(AM.Base.FrameIndex, TLI.getPointerTy()) : 301264790Sbapt AM.Base.Reg; 302264790Sbapt 303264790Sbapt if (AM.GV) 304264790Sbapt Disp = CurDAG->getTargetGlobalAddress(AM.GV, MVT::i16, AM.Disp, 305264790Sbapt 0/*AM.SymbolFlags*/); 306264790Sbapt else if (AM.CP) 307264790Sbapt Disp = CurDAG->getTargetConstantPool(AM.CP, MVT::i16, 308264790Sbapt AM.Align, AM.Disp, 0/*AM.SymbolFlags*/); 309264790Sbapt else if (AM.ES) 310264790Sbapt Disp = CurDAG->getTargetExternalSymbol(AM.ES, MVT::i16, 0/*AM.SymbolFlags*/); 311264790Sbapt else if (AM.JT != -1) 312264790Sbapt Disp = CurDAG->getTargetJumpTable(AM.JT, MVT::i16, 0/*AM.SymbolFlags*/); 313264790Sbapt else if (AM.BlockAddr) 314264790Sbapt Disp = CurDAG->getBlockAddress(AM.BlockAddr, MVT::i32, 315264790Sbapt true, 0/*AM.SymbolFlags*/); 316264790Sbapt else 317264790Sbapt Disp = CurDAG->getTargetConstant(AM.Disp, MVT::i16); 318264790Sbapt 319264790Sbapt return true; 320264790Sbapt} 321264790Sbapt 322264790Sbaptbool MSP430DAGToDAGISel:: 323264790SbaptSelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode, 324264790Sbapt std::vector<SDValue> &OutOps) { 325264790Sbapt SDValue Op0, Op1; 326264790Sbapt switch (ConstraintCode) { 327264790Sbapt default: return true; 328264790Sbapt case 'm': // memory 329264790Sbapt if (!SelectAddr(Op, Op, Op0, Op1)) 330264790Sbapt return true; 331264790Sbapt break; 332264790Sbapt } 333264790Sbapt 334264790Sbapt OutOps.push_back(Op0); 335264790Sbapt OutOps.push_back(Op1); 336264790Sbapt return false; 337264790Sbapt} 338264790Sbapt 339264790Sbaptbool MSP430DAGToDAGISel::IsLegalAndProfitableToFold(SDNode *N, SDNode *U, 340264790Sbapt SDNode *Root) const { 341264790Sbapt if (OptLevel == CodeGenOpt::None) return false; 342264790Sbapt 343264790Sbapt /// RMW preprocessing creates the following code: 344264790Sbapt /// [Load1] 345264790Sbapt /// ^ ^ 346264790Sbapt /// / | 347264790Sbapt /// / | 348264790Sbapt /// [Load2] | 349264790Sbapt /// ^ ^ | 350264790Sbapt /// | | | 351264790Sbapt /// | \-| 352264790Sbapt /// | | 353264790Sbapt /// | [Op] 354264790Sbapt /// | ^ 355264790Sbapt /// | | 356264790Sbapt /// \ / 357264790Sbapt /// \ / 358264790Sbapt /// [Store] 359264790Sbapt /// 360264790Sbapt /// The path Store => Load2 => Load1 is via chain. Note that in general it is 361264790Sbapt /// not allowed to fold Load1 into Op (and Store) since it will creates a 362264790Sbapt /// cycle. However, this is perfectly legal for the loads moved below the 363264790Sbapt /// TokenFactor by PreprocessForRMW. Query the map Store => Load1 (created 364264790Sbapt /// during preprocessing) to determine whether it's legal to introduce such 365264790Sbapt /// "cycle" for a moment. 366264790Sbapt DenseMap<SDNode*, SDNode*>::const_iterator I = RMWStores.find(Root); 367264790Sbapt if (I != RMWStores.end() && I->second == N) 368264790Sbapt return true; 369264790Sbapt 370264790Sbapt // Proceed to 'generic' cycle finder code 371264790Sbapt return SelectionDAGISel::IsLegalAndProfitableToFold(N, U, Root); 372264790Sbapt} 373264790Sbapt 374264790Sbapt 375264790Sbapt/// MoveBelowTokenFactor - Replace TokenFactor operand with load's chain operand 376264790Sbapt/// and move load below the TokenFactor. Replace store's chain operand with 377264790Sbapt/// load's chain result. 378264790Sbaptstatic void MoveBelowTokenFactor(SelectionDAG *CurDAG, SDValue Load, 379264790Sbapt SDValue Store, SDValue TF) { 380264790Sbapt SmallVector<SDValue, 4> Ops; 381264790Sbapt for (unsigned i = 0, e = TF.getNode()->getNumOperands(); i != e; ++i) 382264790Sbapt if (Load.getNode() == TF.getOperand(i).getNode()) 383264790Sbapt Ops.push_back(Load.getOperand(0)); 384264790Sbapt else 385264790Sbapt Ops.push_back(TF.getOperand(i)); 386264790Sbapt SDValue NewTF = CurDAG->UpdateNodeOperands(TF, &Ops[0], Ops.size()); 387264790Sbapt SDValue NewLoad = CurDAG->UpdateNodeOperands(Load, NewTF, 388264790Sbapt Load.getOperand(1), 389264790Sbapt Load.getOperand(2)); 390264790Sbapt CurDAG->UpdateNodeOperands(Store, NewLoad.getValue(1), Store.getOperand(1), 391264790Sbapt Store.getOperand(2), Store.getOperand(3)); 392264790Sbapt} 393264790Sbapt 394264790Sbapt/// MoveBelowTokenFactor2 - Replace TokenFactor operand with load's chain operand 395264790Sbapt/// and move load below the TokenFactor. Replace store's chain operand with 396264790Sbapt/// load's chain result. This a version which sinks two loads below token factor. 397264790Sbapt/// Look into PreprocessForRMW comments for explanation of transform. 398264790Sbaptstatic void MoveBelowTokenFactor2(SelectionDAG *CurDAG, 399264790Sbapt SDValue Load1, SDValue Load2, 400264790Sbapt SDValue Store, SDValue TF) { 401264790Sbapt SmallVector<SDValue, 4> Ops; 402264790Sbapt for (unsigned i = 0, e = TF.getNode()->getNumOperands(); i != e; ++i) { 403264790Sbapt SDNode* N = TF.getOperand(i).getNode(); 404264790Sbapt if (Load2.getNode() == N) 405264790Sbapt Ops.push_back(Load2.getOperand(0)); 406264790Sbapt else if (Load1.getNode() != N) 407264790Sbapt Ops.push_back(TF.getOperand(i)); 408264790Sbapt } 409264790Sbapt 410264790Sbapt SDValue NewTF = SDValue(CurDAG->MorphNodeTo(TF.getNode(), 411264790Sbapt TF.getOpcode(), 412264790Sbapt TF.getNode()->getVTList(), 413264790Sbapt &Ops[0], Ops.size()), TF.getResNo()); 414264790Sbapt SDValue NewLoad2 = CurDAG->UpdateNodeOperands(Load2, NewTF, 415264790Sbapt Load2.getOperand(1), 416264790Sbapt Load2.getOperand(2)); 417264790Sbapt 418264790Sbapt SDValue NewLoad1 = CurDAG->UpdateNodeOperands(Load1, NewLoad2.getValue(1), 419264790Sbapt Load1.getOperand(1), 420264790Sbapt Load1.getOperand(2)); 421264790Sbapt 422264790Sbapt CurDAG->UpdateNodeOperands(Store, 423264790Sbapt NewLoad1.getValue(1), 424264790Sbapt Store.getOperand(1), 425264790Sbapt Store.getOperand(2), Store.getOperand(3)); 426264790Sbapt} 427264790Sbapt 428264790Sbapt/// isAllowedToSink - return true if N a load which can be moved below token 429264790Sbapt/// factor. Basically, the load should be non-volatile and has single use. 430264790Sbaptstatic bool isLoadAllowedToSink(SDValue N, SDValue Chain) { 431264790Sbapt if (N.getOpcode() == ISD::BIT_CONVERT) 432264790Sbapt N = N.getOperand(0); 433264790Sbapt 434264790Sbapt LoadSDNode *LD = dyn_cast<LoadSDNode>(N); 435264790Sbapt if (!LD || LD->isVolatile()) 436264790Sbapt return false; 437264790Sbapt if (LD->getAddressingMode() != ISD::UNINDEXED) 438264790Sbapt return false; 439264790Sbapt 440264790Sbapt ISD::LoadExtType ExtType = LD->getExtensionType(); 441264790Sbapt if (ExtType != ISD::NON_EXTLOAD && ExtType != ISD::EXTLOAD) 442264790Sbapt return false; 443264790Sbapt 444264790Sbapt return (N.hasOneUse() && 445264790Sbapt LD->hasNUsesOfValue(1, 1) && 446264790Sbapt LD->isOperandOf(Chain.getNode())); 447264790Sbapt} 448264790Sbapt 449264790Sbapt 450264790Sbapt/// isRMWLoad - Return true if N is a load that's part of RMW sub-DAG. 451264790Sbapt/// The chain produced by the load must only be used by the store's chain 452264790Sbapt/// operand, otherwise this may produce a cycle in the DAG. 453264790Sbaptstatic bool isRMWLoad(SDValue N, SDValue Chain, SDValue Address, 454264790Sbapt SDValue &Load) { 455264790Sbapt if (isLoadAllowedToSink(N, Chain) && 456264790Sbapt N.getOperand(1) == Address) { 457264790Sbapt Load = N; 458264790Sbapt return true; 459264790Sbapt } 460264790Sbapt return false; 461264790Sbapt} 462264790Sbapt 463264790Sbapt/// PreprocessForRMW - Preprocess the DAG to make instruction selection better. 464264790Sbapt/// This is only run if not in -O0 mode. 465264790Sbapt/// This allows the instruction selector to pick more read-modify-write 466264790Sbapt/// instructions. This is a common case: 467264790Sbapt/// 468264790Sbapt/// [Load chain] 469264790Sbapt/// ^ 470264790Sbapt/// | 471264790Sbapt/// [Load] 472264790Sbapt/// ^ ^ 473264790Sbapt/// | | 474264790Sbapt/// / \- 475264790Sbapt/// / | 476264790Sbapt/// [TokenFactor] [Op] 477264790Sbapt/// ^ ^ 478264790Sbapt/// | | 479264790Sbapt/// \ / 480264790Sbapt/// \ / 481264790Sbapt/// [Store] 482264790Sbapt/// 483264790Sbapt/// The fact the store's chain operand != load's chain will prevent the 484264790Sbapt/// (store (op (load))) instruction from being selected. We can transform it to: 485264790Sbapt/// 486264790Sbapt/// [Load chain] 487264790Sbapt/// ^ 488264790Sbapt/// | 489264790Sbapt/// [TokenFactor] 490264790Sbapt/// ^ 491264790Sbapt/// | 492264790Sbapt/// [Load] 493264790Sbapt/// ^ ^ 494264790Sbapt/// | | 495264790Sbapt/// | \- 496264790Sbapt/// | | 497264790Sbapt/// | [Op] 498264790Sbapt/// | ^ 499264790Sbapt/// | | 500264790Sbapt/// \ / 501264790Sbapt/// \ / 502264790Sbapt/// [Store] 503264790Sbapt/// 504264790Sbapt/// We also recognize the case where second operand of Op is load as well and 505264790Sbapt/// move it below token factor as well creating DAG as follows: 506264790Sbapt/// 507264790Sbapt/// [Load chain] 508264790Sbapt/// ^ 509264790Sbapt/// | 510264790Sbapt/// [TokenFactor] 511264790Sbapt/// ^ 512264790Sbapt/// | 513264790Sbapt/// [Load1] 514264790Sbapt/// ^ ^ 515264790Sbapt/// / | 516264790Sbapt/// / | 517264790Sbapt/// [Load2] | 518264790Sbapt/// ^ ^ | 519264790Sbapt/// | | | 520264790Sbapt/// | \-| 521264790Sbapt/// | | 522264790Sbapt/// | [Op] 523264790Sbapt/// | ^ 524264790Sbapt/// | | 525264790Sbapt/// \ / 526264790Sbapt/// \ / 527264790Sbapt/// [Store] 528264790Sbapt/// 529264790Sbapt/// This allows selection of mem-mem instructions. Yay! 530264790Sbapt 531264790Sbaptvoid MSP430DAGToDAGISel::PreprocessForRMW() { 532264790Sbapt for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(), 533264790Sbapt E = CurDAG->allnodes_end(); I != E; ++I) { 534264790Sbapt if (!ISD::isNON_TRUNCStore(I)) 535264790Sbapt continue; 536264790Sbapt SDValue Chain = I->getOperand(0); 537264790Sbapt 538264790Sbapt if (Chain.getNode()->getOpcode() != ISD::TokenFactor) 539264790Sbapt continue; 540264790Sbapt 541264790Sbapt SDValue N1 = I->getOperand(1); 542264790Sbapt SDValue N2 = I->getOperand(2); 543264790Sbapt if ((N1.getValueType().isFloatingPoint() && 544264790Sbapt !N1.getValueType().isVector()) || 545264790Sbapt !N1.hasOneUse()) 546264790Sbapt continue; 547264790Sbapt 548264790Sbapt unsigned RModW = 0; 549264790Sbapt SDValue Load1, Load2; 550264790Sbapt unsigned Opcode = N1.getNode()->getOpcode(); 551264790Sbapt switch (Opcode) { 552264790Sbapt case ISD::ADD: 553264790Sbapt case ISD::AND: 554264790Sbapt case ISD::OR: 555264790Sbapt case ISD::XOR: 556264790Sbapt case ISD::ADDC: 557264790Sbapt case ISD::ADDE: { 558264790Sbapt SDValue N10 = N1.getOperand(0); 559264790Sbapt SDValue N11 = N1.getOperand(1); 560264790Sbapt if (isRMWLoad(N10, Chain, N2, Load1)) { 561264790Sbapt if (isLoadAllowedToSink(N11, Chain)) { 562264790Sbapt Load2 = N11; 563264790Sbapt RModW = 2; 564264790Sbapt } else 565264790Sbapt RModW = 1; 566264790Sbapt } else if (isRMWLoad(N11, Chain, N2, Load1)) { 567264790Sbapt if (isLoadAllowedToSink(N10, Chain)) { 568264790Sbapt Load2 = N10; 569264790Sbapt RModW = 2; 570264790Sbapt } else 571264790Sbapt RModW = 1; 572264790Sbapt } 573264790Sbapt break; 574264790Sbapt } 575264790Sbapt case ISD::SUB: 576264790Sbapt case ISD::SUBC: 577264790Sbapt case ISD::SUBE: { 578264790Sbapt SDValue N10 = N1.getOperand(0); 579264790Sbapt SDValue N11 = N1.getOperand(1); 580264790Sbapt if (isRMWLoad(N10, Chain, N2, Load1)) { 581264790Sbapt if (isLoadAllowedToSink(N11, Chain)) { 582264790Sbapt Load2 = N11; 583264790Sbapt RModW = 2; 584264790Sbapt } else 585264790Sbapt RModW = 1; 586264790Sbapt } 587264790Sbapt break; 588264790Sbapt } 589264790Sbapt } 590264790Sbapt 591264790Sbapt NumLoadMoved += RModW; 592264790Sbapt if (RModW == 1) 593264790Sbapt MoveBelowTokenFactor(CurDAG, Load1, SDValue(I, 0), Chain); 594264790Sbapt else if (RModW == 2) { 595264790Sbapt MoveBelowTokenFactor2(CurDAG, Load1, Load2, SDValue(I, 0), Chain); 596264790Sbapt SDNode* Store = I; 597264790Sbapt RMWStores[Store] = Load2.getNode(); 598264790Sbapt } 599264790Sbapt } 600264790Sbapt} 601264790Sbapt 602264790Sbapt 603264790Sbaptstatic bool isValidIndexedLoad(const LoadSDNode *LD) { 604264790Sbapt ISD::MemIndexedMode AM = LD->getAddressingMode(); 605264790Sbapt if (AM != ISD::POST_INC || LD->getExtensionType() != ISD::NON_EXTLOAD) 606264790Sbapt return false; 607264790Sbapt 608264790Sbapt EVT VT = LD->getMemoryVT(); 609264790Sbapt 610264790Sbapt switch (VT.getSimpleVT().SimpleTy) { 611264790Sbapt case MVT::i8: 612264790Sbapt // Sanity check 613264790Sbapt if (cast<ConstantSDNode>(LD->getOffset())->getZExtValue() != 1) 614264790Sbapt return false; 615264790Sbapt 616264790Sbapt break; 617264790Sbapt case MVT::i16: 618264790Sbapt // Sanity check 619264790Sbapt if (cast<ConstantSDNode>(LD->getOffset())->getZExtValue() != 2) 620264790Sbapt return false; 621264790Sbapt 622264790Sbapt break; 623264790Sbapt default: 624264790Sbapt return false; 625264790Sbapt } 626264790Sbapt 627264790Sbapt return true; 628264790Sbapt} 629264790Sbapt 630264790SbaptSDNode *MSP430DAGToDAGISel::SelectIndexedLoad(SDValue Op) { 631264790Sbapt LoadSDNode *LD = cast<LoadSDNode>(Op); 632264790Sbapt if (!isValidIndexedLoad(LD)) 633264790Sbapt return NULL; 634264790Sbapt 635264790Sbapt MVT VT = LD->getMemoryVT().getSimpleVT(); 636264790Sbapt 637264790Sbapt unsigned Opcode = 0; 638264790Sbapt switch (VT.SimpleTy) { 639264790Sbapt case MVT::i8: 640264790Sbapt Opcode = MSP430::MOV8rm_POST; 641264790Sbapt break; 642264790Sbapt case MVT::i16: 643264790Sbapt Opcode = MSP430::MOV16rm_POST; 644264790Sbapt break; 645264790Sbapt default: 646264790Sbapt return NULL; 647264790Sbapt } 648264790Sbapt 649264790Sbapt return CurDAG->getMachineNode(Opcode, Op.getDebugLoc(), 650264790Sbapt VT, MVT::i16, MVT::Other, 651264790Sbapt LD->getBasePtr(), LD->getChain()); 652264790Sbapt} 653264790Sbapt 654264790SbaptSDNode *MSP430DAGToDAGISel::SelectIndexedBinOp(SDValue Op, 655264790Sbapt SDValue N1, SDValue N2, 656264790Sbapt unsigned Opc8, unsigned Opc16) { 657264790Sbapt if (N1.getOpcode() == ISD::LOAD && 658264790Sbapt N1.hasOneUse() && 659264790Sbapt IsLegalAndProfitableToFold(N1.getNode(), Op.getNode(), Op.getNode())) { 660264790Sbapt LoadSDNode *LD = cast<LoadSDNode>(N1); 661264790Sbapt if (!isValidIndexedLoad(LD)) 662264790Sbapt return NULL; 663264790Sbapt 664264790Sbapt MVT VT = LD->getMemoryVT().getSimpleVT(); 665264790Sbapt unsigned Opc = (VT == MVT::i16 ? Opc16 : Opc8); 666264790Sbapt MachineSDNode::mmo_iterator MemRefs0 = MF->allocateMemRefsArray(1); 667264790Sbapt MemRefs0[0] = cast<MemSDNode>(N1)->getMemOperand(); 668264790Sbapt SDValue Ops0[] = { N2, LD->getBasePtr(), LD->getChain() }; 669264790Sbapt SDNode *ResNode = 670264790Sbapt CurDAG->SelectNodeTo(Op.getNode(), Opc, 671264790Sbapt VT, MVT::i16, MVT::Other, 672264790Sbapt Ops0, 3); 673264790Sbapt cast<MachineSDNode>(ResNode)->setMemRefs(MemRefs0, MemRefs0 + 1); 674264790Sbapt // Transfer chain. 675264790Sbapt ReplaceUses(SDValue(N1.getNode(), 2), SDValue(ResNode, 2)); 676264790Sbapt // Transfer writeback. 677264790Sbapt ReplaceUses(SDValue(N1.getNode(), 1), SDValue(ResNode, 1)); 678264790Sbapt return ResNode; 679264790Sbapt } 680264790Sbapt 681264790Sbapt return NULL; 682264790Sbapt} 683264790Sbapt 684264790Sbapt 685264790Sbapt/// InstructionSelect - This callback is invoked by 686264790Sbapt/// SelectionDAGISel when it has created a SelectionDAG for us to codegen. 687264790Sbaptvoid MSP430DAGToDAGISel::InstructionSelect() { 688264790Sbapt std::string BlockName; 689264790Sbapt if (ViewRMWDAGs) 690264790Sbapt BlockName = MF->getFunction()->getNameStr() + ":" + 691264790Sbapt BB->getBasicBlock()->getNameStr(); 692264790Sbapt 693264790Sbapt PreprocessForRMW(); 694264790Sbapt 695264790Sbapt if (ViewRMWDAGs) CurDAG->viewGraph("RMW preprocessed:" + BlockName); 696264790Sbapt 697264790Sbapt DEBUG(errs() << "Selection DAG after RMW preprocessing:\n"); 698264790Sbapt DEBUG(CurDAG->dump()); 699264790Sbapt 700264790Sbapt // Codegen the basic block. 701264790Sbapt DEBUG(errs() << "===== Instruction selection begins:\n"); 702264790Sbapt DEBUG(Indent = 0); 703264790Sbapt SelectRoot(*CurDAG); 704264790Sbapt DEBUG(errs() << "===== Instruction selection ends:\n"); 705264790Sbapt 706264790Sbapt CurDAG->RemoveDeadNodes(); 707264790Sbapt RMWStores.clear(); 708264790Sbapt} 709264790Sbapt 710264790SbaptSDNode *MSP430DAGToDAGISel::Select(SDValue Op) { 711264790Sbapt SDNode *Node = Op.getNode(); 712264790Sbapt DebugLoc dl = Op.getDebugLoc(); 713264790Sbapt 714264790Sbapt // Dump information about the Node being selected 715264790Sbapt DEBUG(errs().indent(Indent) << "Selecting: "); 716264790Sbapt DEBUG(Node->dump(CurDAG)); 717264790Sbapt DEBUG(errs() << "\n"); 718264790Sbapt DEBUG(Indent += 2); 719264790Sbapt 720264790Sbapt // If we have a custom node, we already have selected! 721264790Sbapt if (Node->isMachineOpcode()) { 722264790Sbapt DEBUG(errs().indent(Indent-2) << "== "; 723264790Sbapt Node->dump(CurDAG); 724264790Sbapt errs() << "\n"); 725264790Sbapt DEBUG(Indent -= 2); 726264790Sbapt return NULL; 727264790Sbapt } 728264790Sbapt 729264790Sbapt // Few custom selection stuff. 730264790Sbapt switch (Node->getOpcode()) { 731264790Sbapt default: break; 732264790Sbapt case ISD::FrameIndex: { 733264790Sbapt assert(Op.getValueType() == MVT::i16); 734264790Sbapt int FI = cast<FrameIndexSDNode>(Node)->getIndex(); 735264790Sbapt SDValue TFI = CurDAG->getTargetFrameIndex(FI, MVT::i16); 736264790Sbapt if (Node->hasOneUse()) 737264790Sbapt return CurDAG->SelectNodeTo(Node, MSP430::ADD16ri, MVT::i16, 738264790Sbapt TFI, CurDAG->getTargetConstant(0, MVT::i16)); 739264790Sbapt return CurDAG->getMachineNode(MSP430::ADD16ri, dl, MVT::i16, 740264790Sbapt TFI, CurDAG->getTargetConstant(0, MVT::i16)); 741264790Sbapt } 742264790Sbapt case ISD::LOAD: 743264790Sbapt if (SDNode *ResNode = SelectIndexedLoad(Op)) 744264790Sbapt return ResNode; 745264790Sbapt // Other cases are autogenerated. 746264790Sbapt break; 747264790Sbapt case ISD::ADD: 748264790Sbapt if (SDNode *ResNode = 749264790Sbapt SelectIndexedBinOp(Op, 750264790Sbapt Op.getOperand(0), Op.getOperand(1), 751264790Sbapt MSP430::ADD8rm_POST, MSP430::ADD16rm_POST)) 752264790Sbapt return ResNode; 753264790Sbapt else if (SDNode *ResNode = 754264790Sbapt SelectIndexedBinOp(Op, Op.getOperand(1), Op.getOperand(0), 755264790Sbapt MSP430::ADD8rm_POST, MSP430::ADD16rm_POST)) 756264790Sbapt return ResNode; 757264790Sbapt 758264790Sbapt // Other cases are autogenerated. 759264790Sbapt break; 760264790Sbapt case ISD::SUB: 761264790Sbapt if (SDNode *ResNode = 762264790Sbapt SelectIndexedBinOp(Op, 763264790Sbapt Op.getOperand(0), Op.getOperand(1), 764264790Sbapt MSP430::SUB8rm_POST, MSP430::SUB16rm_POST)) 765264790Sbapt return ResNode; 766264790Sbapt 767264790Sbapt // Other cases are autogenerated. 768264790Sbapt break; 769264790Sbapt case ISD::AND: 770264790Sbapt if (SDNode *ResNode = 771264790Sbapt SelectIndexedBinOp(Op, 772264790Sbapt Op.getOperand(0), Op.getOperand(1), 773264790Sbapt MSP430::AND8rm_POST, MSP430::AND16rm_POST)) 774264790Sbapt return ResNode; 775264790Sbapt else if (SDNode *ResNode = 776264790Sbapt SelectIndexedBinOp(Op, Op.getOperand(1), Op.getOperand(0), 777264790Sbapt MSP430::AND8rm_POST, MSP430::AND16rm_POST)) 778264790Sbapt return ResNode; 779264790Sbapt 780264790Sbapt // Other cases are autogenerated. 781264790Sbapt break; 782264790Sbapt case ISD::OR: 783264790Sbapt if (SDNode *ResNode = 784264790Sbapt SelectIndexedBinOp(Op, 785264790Sbapt Op.getOperand(0), Op.getOperand(1), 786264790Sbapt MSP430::OR8rm_POST, MSP430::OR16rm_POST)) 787264790Sbapt return ResNode; 788264790Sbapt else if (SDNode *ResNode = 789264790Sbapt SelectIndexedBinOp(Op, Op.getOperand(1), Op.getOperand(0), 790264790Sbapt MSP430::OR8rm_POST, MSP430::OR16rm_POST)) 791264790Sbapt return ResNode; 792264790Sbapt 793264790Sbapt // Other cases are autogenerated. 794264790Sbapt break; 795264790Sbapt case ISD::XOR: 796264790Sbapt if (SDNode *ResNode = 797264790Sbapt SelectIndexedBinOp(Op, 798264790Sbapt Op.getOperand(0), Op.getOperand(1), 799264790Sbapt MSP430::XOR8rm_POST, MSP430::XOR16rm_POST)) 800264790Sbapt return ResNode; 801264790Sbapt else if (SDNode *ResNode = 802264790Sbapt SelectIndexedBinOp(Op, Op.getOperand(1), Op.getOperand(0), 803264790Sbapt MSP430::XOR8rm_POST, MSP430::XOR16rm_POST)) 804264790Sbapt return ResNode; 805264790Sbapt 806264790Sbapt // Other cases are autogenerated. 807264790Sbapt break; 808264790Sbapt } 809264790Sbapt 810264790Sbapt // Select the default instruction 811264790Sbapt SDNode *ResNode = SelectCode(Op); 812264790Sbapt 813264790Sbapt DEBUG(errs() << std::string(Indent-2, ' ') << "=> "); 814264790Sbapt if (ResNode == NULL || ResNode == Op.getNode()) 815264790Sbapt DEBUG(Op.getNode()->dump(CurDAG)); 816264790Sbapt else 817264790Sbapt DEBUG(ResNode->dump(CurDAG)); 818264790Sbapt DEBUG(errs() << "\n"); 819264790Sbapt DEBUG(Indent -= 2); 820264790Sbapt 821264790Sbapt return ResNode; 822264790Sbapt} 823264790Sbapt