MSP430ISelDAGToDAG.cpp revision 198396
1//===-- MSP430ISelDAGToDAG.cpp - A dag to dag inst selector for MSP430 ----===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines an instruction selector for the MSP430 target. 11// 12//===----------------------------------------------------------------------===// 13 14#include "MSP430.h" 15#include "MSP430ISelLowering.h" 16#include "MSP430TargetMachine.h" 17#include "llvm/DerivedTypes.h" 18#include "llvm/Function.h" 19#include "llvm/Intrinsics.h" 20#include "llvm/CallingConv.h" 21#include "llvm/Constants.h" 22#include "llvm/CodeGen/MachineFrameInfo.h" 23#include "llvm/CodeGen/MachineFunction.h" 24#include "llvm/CodeGen/MachineInstrBuilder.h" 25#include "llvm/CodeGen/MachineRegisterInfo.h" 26#include "llvm/CodeGen/SelectionDAG.h" 27#include "llvm/CodeGen/SelectionDAGISel.h" 28#include "llvm/Target/TargetLowering.h" 29#include "llvm/Support/CommandLine.h" 30#include "llvm/Support/Compiler.h" 31#include "llvm/Support/Debug.h" 32#include "llvm/Support/ErrorHandling.h" 33#include "llvm/Support/raw_ostream.h" 34#include "llvm/ADT/Statistic.h" 35 36using namespace llvm; 37 38#ifndef NDEBUG 39static cl::opt<bool> 40ViewRMWDAGs("view-msp430-rmw-dags", cl::Hidden, 41 cl::desc("Pop up a window to show isel dags after RMW preprocess")); 42#else 43static const bool ViewRMWDAGs = false; 44#endif 45 46STATISTIC(NumLoadMoved, "Number of loads moved below TokenFactor"); 47 48/// MSP430DAGToDAGISel - MSP430 specific code to select MSP430 machine 49/// instructions for SelectionDAG operations. 50/// 51namespace { 52 class MSP430DAGToDAGISel : public SelectionDAGISel { 53 MSP430TargetLowering &Lowering; 54 const MSP430Subtarget &Subtarget; 55 56 public: 57 MSP430DAGToDAGISel(MSP430TargetMachine &TM, CodeGenOpt::Level OptLevel) 58 : SelectionDAGISel(TM, OptLevel), 59 Lowering(*TM.getTargetLowering()), 60 Subtarget(*TM.getSubtargetImpl()) { } 61 62 virtual void InstructionSelect(); 63 64 virtual const char *getPassName() const { 65 return "MSP430 DAG->DAG Pattern Instruction Selection"; 66 } 67 68 bool IsLegalAndProfitableToFold(SDNode *N, SDNode *U, 69 SDNode *Root) const; 70 71 virtual bool 72 SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode, 73 std::vector<SDValue> &OutOps); 74 75 // Include the pieces autogenerated from the target description. 76 #include "MSP430GenDAGISel.inc" 77 78 private: 79 DenseMap<SDNode*, SDNode*> RMWStores; 80 void PreprocessForRMW(); 81 SDNode *Select(SDValue Op); 82 bool SelectAddr(SDValue Op, SDValue Addr, SDValue &Base, SDValue &Disp); 83 84 #ifndef NDEBUG 85 unsigned Indent; 86 #endif 87 }; 88} // end anonymous namespace 89 90/// createMSP430ISelDag - This pass converts a legalized DAG into a 91/// MSP430-specific DAG, ready for instruction scheduling. 92/// 93FunctionPass *llvm::createMSP430ISelDag(MSP430TargetMachine &TM, 94 CodeGenOpt::Level OptLevel) { 95 return new MSP430DAGToDAGISel(TM, OptLevel); 96} 97 98// FIXME: This is pretty dummy routine and needs to be rewritten in the future. 99bool MSP430DAGToDAGISel::SelectAddr(SDValue Op, SDValue Addr, 100 SDValue &Base, SDValue &Disp) { 101 // Try to match frame address first. 102 if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(Addr)) { 103 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i16); 104 Disp = CurDAG->getTargetConstant(0, MVT::i16); 105 return true; 106 } 107 108 switch (Addr.getOpcode()) { 109 case ISD::ADD: 110 // Operand is a result from ADD with constant operand which fits into i16. 111 if (ConstantSDNode *CN = dyn_cast<ConstantSDNode>(Addr.getOperand(1))) { 112 uint64_t CVal = CN->getZExtValue(); 113 // Offset should fit into 16 bits. 114 if (((CVal << 48) >> 48) == CVal) { 115 SDValue N0 = Addr.getOperand(0); 116 if (FrameIndexSDNode *FIN = dyn_cast<FrameIndexSDNode>(N0)) 117 Base = CurDAG->getTargetFrameIndex(FIN->getIndex(), MVT::i16); 118 else 119 Base = N0; 120 121 Disp = CurDAG->getTargetConstant(CVal, MVT::i16); 122 return true; 123 } 124 } 125 break; 126 case MSP430ISD::Wrapper: 127 SDValue N0 = Addr.getOperand(0); 128 if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(N0)) { 129 Base = CurDAG->getTargetGlobalAddress(G->getGlobal(), 130 MVT::i16, G->getOffset()); 131 Disp = CurDAG->getTargetConstant(0, MVT::i16); 132 return true; 133 } else if (ExternalSymbolSDNode *E = dyn_cast<ExternalSymbolSDNode>(N0)) { 134 Base = CurDAG->getTargetExternalSymbol(E->getSymbol(), MVT::i16); 135 Disp = CurDAG->getTargetConstant(0, MVT::i16); 136 } 137 break; 138 }; 139 140 Base = Addr; 141 Disp = CurDAG->getTargetConstant(0, MVT::i16); 142 143 return true; 144} 145 146bool MSP430DAGToDAGISel:: 147SelectInlineAsmMemoryOperand(const SDValue &Op, char ConstraintCode, 148 std::vector<SDValue> &OutOps) { 149 SDValue Op0, Op1; 150 switch (ConstraintCode) { 151 default: return true; 152 case 'm': // memory 153 if (!SelectAddr(Op, Op, Op0, Op1)) 154 return true; 155 break; 156 } 157 158 OutOps.push_back(Op0); 159 OutOps.push_back(Op1); 160 return false; 161} 162 163bool MSP430DAGToDAGISel::IsLegalAndProfitableToFold(SDNode *N, SDNode *U, 164 SDNode *Root) const { 165 if (OptLevel == CodeGenOpt::None) return false; 166 167 /// RMW preprocessing creates the following code: 168 /// [Load1] 169 /// ^ ^ 170 /// / | 171 /// / | 172 /// [Load2] | 173 /// ^ ^ | 174 /// | | | 175 /// | \-| 176 /// | | 177 /// | [Op] 178 /// | ^ 179 /// | | 180 /// \ / 181 /// \ / 182 /// [Store] 183 /// 184 /// The path Store => Load2 => Load1 is via chain. Note that in general it is 185 /// not allowed to fold Load1 into Op (and Store) since it will creates a 186 /// cycle. However, this is perfectly legal for the loads moved below the 187 /// TokenFactor by PreprocessForRMW. Query the map Store => Load1 (created 188 /// during preprocessing) to determine whether it's legal to introduce such 189 /// "cycle" for a moment. 190 DenseMap<SDNode*, SDNode*>::iterator I = RMWStores.find(Root); 191 if (I != RMWStores.end() && I->second == N) 192 return true; 193 194 // Proceed to 'generic' cycle finder code 195 return SelectionDAGISel::IsLegalAndProfitableToFold(N, U, Root); 196} 197 198 199/// MoveBelowTokenFactor - Replace TokenFactor operand with load's chain operand 200/// and move load below the TokenFactor. Replace store's chain operand with 201/// load's chain result. 202static void MoveBelowTokenFactor(SelectionDAG *CurDAG, SDValue Load, 203 SDValue Store, SDValue TF) { 204 SmallVector<SDValue, 4> Ops; 205 for (unsigned i = 0, e = TF.getNode()->getNumOperands(); i != e; ++i) 206 if (Load.getNode() == TF.getOperand(i).getNode()) 207 Ops.push_back(Load.getOperand(0)); 208 else 209 Ops.push_back(TF.getOperand(i)); 210 SDValue NewTF = CurDAG->UpdateNodeOperands(TF, &Ops[0], Ops.size()); 211 SDValue NewLoad = CurDAG->UpdateNodeOperands(Load, NewTF, 212 Load.getOperand(1), 213 Load.getOperand(2)); 214 CurDAG->UpdateNodeOperands(Store, NewLoad.getValue(1), Store.getOperand(1), 215 Store.getOperand(2), Store.getOperand(3)); 216} 217 218/// MoveBelowTokenFactor2 - Replace TokenFactor operand with load's chain operand 219/// and move load below the TokenFactor. Replace store's chain operand with 220/// load's chain result. This a version which sinks two loads below token factor. 221/// Look into PreprocessForRMW comments for explanation of transform. 222static void MoveBelowTokenFactor2(SelectionDAG *CurDAG, 223 SDValue Load1, SDValue Load2, 224 SDValue Store, SDValue TF) { 225 SmallVector<SDValue, 4> Ops; 226 for (unsigned i = 0, e = TF.getNode()->getNumOperands(); i != e; ++i) { 227 SDNode* N = TF.getOperand(i).getNode(); 228 if (Load2.getNode() == N) 229 Ops.push_back(Load2.getOperand(0)); 230 else if (Load1.getNode() != N) 231 Ops.push_back(TF.getOperand(i)); 232 } 233 234 SDValue NewTF = SDValue(CurDAG->MorphNodeTo(TF.getNode(), 235 TF.getOpcode(), 236 TF.getNode()->getVTList(), 237 &Ops[0], Ops.size()), TF.getResNo()); 238 SDValue NewLoad2 = CurDAG->UpdateNodeOperands(Load2, NewTF, 239 Load2.getOperand(1), 240 Load2.getOperand(2)); 241 242 SDValue NewLoad1 = CurDAG->UpdateNodeOperands(Load1, NewLoad2.getValue(1), 243 Load1.getOperand(1), 244 Load1.getOperand(2)); 245 246 CurDAG->UpdateNodeOperands(Store, 247 NewLoad1.getValue(1), 248 Store.getOperand(1), 249 Store.getOperand(2), Store.getOperand(3)); 250} 251 252/// isAllowedToSink - return true if N a load which can be moved below token 253/// factor. Basically, the load should be non-volatile and has single use. 254static bool isLoadAllowedToSink(SDValue N, SDValue Chain) { 255 if (N.getOpcode() == ISD::BIT_CONVERT) 256 N = N.getOperand(0); 257 258 LoadSDNode *LD = dyn_cast<LoadSDNode>(N); 259 if (!LD || LD->isVolatile()) 260 return false; 261 if (LD->getAddressingMode() != ISD::UNINDEXED) 262 return false; 263 264 ISD::LoadExtType ExtType = LD->getExtensionType(); 265 if (ExtType != ISD::NON_EXTLOAD && ExtType != ISD::EXTLOAD) 266 return false; 267 268 return (N.hasOneUse() && 269 LD->hasNUsesOfValue(1, 1) && 270 LD->isOperandOf(Chain.getNode())); 271} 272 273 274/// isRMWLoad - Return true if N is a load that's part of RMW sub-DAG. 275/// The chain produced by the load must only be used by the store's chain 276/// operand, otherwise this may produce a cycle in the DAG. 277static bool isRMWLoad(SDValue N, SDValue Chain, SDValue Address, 278 SDValue &Load) { 279 if (isLoadAllowedToSink(N, Chain) && 280 N.getOperand(1) == Address) { 281 Load = N; 282 return true; 283 } 284 return false; 285} 286 287/// PreprocessForRMW - Preprocess the DAG to make instruction selection better. 288/// This is only run if not in -O0 mode. 289/// This allows the instruction selector to pick more read-modify-write 290/// instructions. This is a common case: 291/// 292/// [Load chain] 293/// ^ 294/// | 295/// [Load] 296/// ^ ^ 297/// | | 298/// / \- 299/// / | 300/// [TokenFactor] [Op] 301/// ^ ^ 302/// | | 303/// \ / 304/// \ / 305/// [Store] 306/// 307/// The fact the store's chain operand != load's chain will prevent the 308/// (store (op (load))) instruction from being selected. We can transform it to: 309/// 310/// [Load chain] 311/// ^ 312/// | 313/// [TokenFactor] 314/// ^ 315/// | 316/// [Load] 317/// ^ ^ 318/// | | 319/// | \- 320/// | | 321/// | [Op] 322/// | ^ 323/// | | 324/// \ / 325/// \ / 326/// [Store] 327/// 328/// We also recognize the case where second operand of Op is load as well and 329/// move it below token factor as well creating DAG as follows: 330/// 331/// [Load chain] 332/// ^ 333/// | 334/// [TokenFactor] 335/// ^ 336/// | 337/// [Load1] 338/// ^ ^ 339/// / | 340/// / | 341/// [Load2] | 342/// ^ ^ | 343/// | | | 344/// | \-| 345/// | | 346/// | [Op] 347/// | ^ 348/// | | 349/// \ / 350/// \ / 351/// [Store] 352/// 353/// This allows selection of mem-mem instructions. Yay! 354 355void MSP430DAGToDAGISel::PreprocessForRMW() { 356 for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(), 357 E = CurDAG->allnodes_end(); I != E; ++I) { 358 if (!ISD::isNON_TRUNCStore(I)) 359 continue; 360 SDValue Chain = I->getOperand(0); 361 362 if (Chain.getNode()->getOpcode() != ISD::TokenFactor) 363 continue; 364 365 SDValue N1 = I->getOperand(1); 366 SDValue N2 = I->getOperand(2); 367 if ((N1.getValueType().isFloatingPoint() && 368 !N1.getValueType().isVector()) || 369 !N1.hasOneUse()) 370 continue; 371 372 unsigned RModW = 0; 373 SDValue Load1, Load2; 374 unsigned Opcode = N1.getNode()->getOpcode(); 375 switch (Opcode) { 376 case ISD::ADD: 377 case ISD::AND: 378 case ISD::OR: 379 case ISD::XOR: 380 case ISD::ADDC: 381 case ISD::ADDE: { 382 SDValue N10 = N1.getOperand(0); 383 SDValue N11 = N1.getOperand(1); 384 if (isRMWLoad(N10, Chain, N2, Load1)) { 385 if (isLoadAllowedToSink(N11, Chain)) { 386 Load2 = N11; 387 RModW = 2; 388 } else 389 RModW = 1; 390 } else if (isRMWLoad(N11, Chain, N2, Load1)) { 391 if (isLoadAllowedToSink(N10, Chain)) { 392 Load2 = N10; 393 RModW = 2; 394 } else 395 RModW = 1; 396 } 397 break; 398 } 399 case ISD::SUB: 400 case ISD::SUBC: 401 case ISD::SUBE: { 402 SDValue N10 = N1.getOperand(0); 403 SDValue N11 = N1.getOperand(1); 404 if (isRMWLoad(N10, Chain, N2, Load1)) { 405 if (isLoadAllowedToSink(N11, Chain)) { 406 Load2 = N11; 407 RModW = 2; 408 } else 409 RModW = 1; 410 } 411 break; 412 } 413 } 414 415 NumLoadMoved += RModW; 416 if (RModW == 1) 417 MoveBelowTokenFactor(CurDAG, Load1, SDValue(I, 0), Chain); 418 else if (RModW == 2) { 419 MoveBelowTokenFactor2(CurDAG, Load1, Load2, SDValue(I, 0), Chain); 420 SDNode* Store = I; 421 RMWStores[Store] = Load2.getNode(); 422 } 423 } 424} 425 426/// InstructionSelect - This callback is invoked by 427/// SelectionDAGISel when it has created a SelectionDAG for us to codegen. 428void MSP430DAGToDAGISel::InstructionSelect() { 429 std::string BlockName; 430 if (ViewRMWDAGs) 431 BlockName = MF->getFunction()->getNameStr() + ":" + 432 BB->getBasicBlock()->getNameStr(); 433 434 PreprocessForRMW(); 435 436 if (ViewRMWDAGs) CurDAG->viewGraph("RMW preprocessed:" + BlockName); 437 438 DEBUG(errs() << "Selection DAG after RMW preprocessing:\n"); 439 DEBUG(CurDAG->dump()); 440 441 DEBUG(BB->dump()); 442 443 // Codegen the basic block. 444 DEBUG(errs() << "===== Instruction selection begins:\n"); 445 DEBUG(Indent = 0); 446 SelectRoot(*CurDAG); 447 DEBUG(errs() << "===== Instruction selection ends:\n"); 448 449 CurDAG->RemoveDeadNodes(); 450 RMWStores.clear(); 451} 452 453SDNode *MSP430DAGToDAGISel::Select(SDValue Op) { 454 SDNode *Node = Op.getNode(); 455 DebugLoc dl = Op.getDebugLoc(); 456 457 // Dump information about the Node being selected 458 DEBUG(errs().indent(Indent) << "Selecting: "); 459 DEBUG(Node->dump(CurDAG)); 460 DEBUG(errs() << "\n"); 461 DEBUG(Indent += 2); 462 463 // If we have a custom node, we already have selected! 464 if (Node->isMachineOpcode()) { 465 DEBUG(errs().indent(Indent-2) << "== "; 466 Node->dump(CurDAG); 467 errs() << "\n"); 468 DEBUG(Indent -= 2); 469 return NULL; 470 } 471 472 // Few custom selection stuff. 473 switch (Node->getOpcode()) { 474 default: break; 475 case ISD::FrameIndex: { 476 assert(Op.getValueType() == MVT::i16); 477 int FI = cast<FrameIndexSDNode>(Node)->getIndex(); 478 SDValue TFI = CurDAG->getTargetFrameIndex(FI, MVT::i16); 479 if (Node->hasOneUse()) 480 return CurDAG->SelectNodeTo(Node, MSP430::ADD16ri, MVT::i16, 481 TFI, CurDAG->getTargetConstant(0, MVT::i16)); 482 return CurDAG->getMachineNode(MSP430::ADD16ri, dl, MVT::i16, 483 TFI, CurDAG->getTargetConstant(0, MVT::i16)); 484 } 485 } 486 487 // Select the default instruction 488 SDNode *ResNode = SelectCode(Op); 489 490 DEBUG(errs() << std::string(Indent-2, ' ') << "=> "); 491 if (ResNode == NULL || ResNode == Op.getNode()) 492 DEBUG(Op.getNode()->dump(CurDAG)); 493 else 494 DEBUG(ResNode->dump(CurDAG)); 495 DEBUG(errs() << "\n"); 496 DEBUG(Indent -= 2); 497 498 return ResNode; 499} 500