SystemZISelDAGToDAG.cpp revision 745ca1eed7dc0a056b066f16aea750ce6fa8a530
1//===-- SystemZISelDAGToDAG.cpp - A dag to dag inst selector for SystemZ --===// 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 SystemZ target. 11// 12//===----------------------------------------------------------------------===// 13 14#include "SystemZTargetMachine.h" 15#include "llvm/Analysis/AliasAnalysis.h" 16#include "llvm/CodeGen/SelectionDAGISel.h" 17#include "llvm/Support/Debug.h" 18#include "llvm/Support/raw_ostream.h" 19 20using namespace llvm; 21 22namespace { 23// Used to build addressing modes. 24struct SystemZAddressingMode { 25 // The shape of the address. 26 enum AddrForm { 27 // base+displacement 28 FormBD, 29 30 // base+displacement+index for load and store operands 31 FormBDXNormal, 32 33 // base+displacement+index for load address operands 34 FormBDXLA, 35 36 // base+displacement+index+ADJDYNALLOC 37 FormBDXDynAlloc 38 }; 39 AddrForm Form; 40 41 // The type of displacement. The enum names here correspond directly 42 // to the definitions in SystemZOperand.td. We could split them into 43 // flags -- single/pair, 128-bit, etc. -- but it hardly seems worth it. 44 enum DispRange { 45 Disp12Only, 46 Disp12Pair, 47 Disp20Only, 48 Disp20Only128, 49 Disp20Pair 50 }; 51 DispRange DR; 52 53 // The parts of the address. The address is equivalent to: 54 // 55 // Base + Disp + Index + (IncludesDynAlloc ? ADJDYNALLOC : 0) 56 SDValue Base; 57 int64_t Disp; 58 SDValue Index; 59 bool IncludesDynAlloc; 60 61 SystemZAddressingMode(AddrForm form, DispRange dr) 62 : Form(form), DR(dr), Base(), Disp(0), Index(), 63 IncludesDynAlloc(false) {} 64 65 // True if the address can have an index register. 66 bool hasIndexField() { return Form != FormBD; } 67 68 // True if the address can (and must) include ADJDYNALLOC. 69 bool isDynAlloc() { return Form == FormBDXDynAlloc; } 70 71 void dump() { 72 errs() << "SystemZAddressingMode " << this << '\n'; 73 74 errs() << " Base "; 75 if (Base.getNode() != 0) 76 Base.getNode()->dump(); 77 else 78 errs() << "null\n"; 79 80 if (hasIndexField()) { 81 errs() << " Index "; 82 if (Index.getNode() != 0) 83 Index.getNode()->dump(); 84 else 85 errs() << "null\n"; 86 } 87 88 errs() << " Disp " << Disp; 89 if (IncludesDynAlloc) 90 errs() << " + ADJDYNALLOC"; 91 errs() << '\n'; 92 } 93}; 94 95// Return a mask with Count low bits set. 96static uint64_t allOnes(unsigned int Count) { 97 return Count == 0 ? 0 : (uint64_t(1) << (Count - 1) << 1) - 1; 98} 99 100// Represents operands 2 to 5 of the ROTATE AND ... SELECTED BITS operation 101// given by Opcode. The operands are: Input (R2), Start (I3), End (I4) and 102// Rotate (I5). The combined operand value is effectively: 103// 104// (or (rotl Input, Rotate), ~Mask) 105// 106// for RNSBG and: 107// 108// (and (rotl Input, Rotate), Mask) 109// 110// otherwise. The value has BitSize bits. 111struct RxSBGOperands { 112 RxSBGOperands(unsigned Op, SDValue N) 113 : Opcode(Op), BitSize(N.getValueType().getSizeInBits()), 114 Mask(allOnes(BitSize)), Input(N), Start(64 - BitSize), End(63), 115 Rotate(0) {} 116 117 unsigned Opcode; 118 unsigned BitSize; 119 uint64_t Mask; 120 SDValue Input; 121 unsigned Start; 122 unsigned End; 123 unsigned Rotate; 124}; 125 126class SystemZDAGToDAGISel : public SelectionDAGISel { 127 const SystemZTargetLowering &Lowering; 128 const SystemZSubtarget &Subtarget; 129 130 // Used by SystemZOperands.td to create integer constants. 131 inline SDValue getImm(const SDNode *Node, uint64_t Imm) const { 132 return CurDAG->getTargetConstant(Imm, Node->getValueType(0)); 133 } 134 135 const SystemZTargetMachine &getTargetMachine() const { 136 return static_cast<const SystemZTargetMachine &>(TM); 137 } 138 139 const SystemZInstrInfo *getInstrInfo() const { 140 return getTargetMachine().getInstrInfo(); 141 } 142 143 // Try to fold more of the base or index of AM into AM, where IsBase 144 // selects between the base and index. 145 bool expandAddress(SystemZAddressingMode &AM, bool IsBase) const; 146 147 // Try to describe N in AM, returning true on success. 148 bool selectAddress(SDValue N, SystemZAddressingMode &AM) const; 149 150 // Extract individual target operands from matched address AM. 151 void getAddressOperands(const SystemZAddressingMode &AM, EVT VT, 152 SDValue &Base, SDValue &Disp) const; 153 void getAddressOperands(const SystemZAddressingMode &AM, EVT VT, 154 SDValue &Base, SDValue &Disp, SDValue &Index) const; 155 156 // Try to match Addr as a FormBD address with displacement type DR. 157 // Return true on success, storing the base and displacement in 158 // Base and Disp respectively. 159 bool selectBDAddr(SystemZAddressingMode::DispRange DR, SDValue Addr, 160 SDValue &Base, SDValue &Disp) const; 161 162 // Try to match Addr as a FormBDX address with displacement type DR. 163 // Return true on success and if the result had no index. Store the 164 // base and displacement in Base and Disp respectively. 165 bool selectMVIAddr(SystemZAddressingMode::DispRange DR, SDValue Addr, 166 SDValue &Base, SDValue &Disp) const; 167 168 // Try to match Addr as a FormBDX* address of form Form with 169 // displacement type DR. Return true on success, storing the base, 170 // displacement and index in Base, Disp and Index respectively. 171 bool selectBDXAddr(SystemZAddressingMode::AddrForm Form, 172 SystemZAddressingMode::DispRange DR, SDValue Addr, 173 SDValue &Base, SDValue &Disp, SDValue &Index) const; 174 175 // PC-relative address matching routines used by SystemZOperands.td. 176 bool selectPCRelAddress(SDValue Addr, SDValue &Target) const { 177 if (SystemZISD::isPCREL(Addr.getOpcode())) { 178 Target = Addr.getOperand(0); 179 return true; 180 } 181 return false; 182 } 183 184 // BD matching routines used by SystemZOperands.td. 185 bool selectBDAddr12Only(SDValue Addr, SDValue &Base, SDValue &Disp) const { 186 return selectBDAddr(SystemZAddressingMode::Disp12Only, Addr, Base, Disp); 187 } 188 bool selectBDAddr12Pair(SDValue Addr, SDValue &Base, SDValue &Disp) const { 189 return selectBDAddr(SystemZAddressingMode::Disp12Pair, Addr, Base, Disp); 190 } 191 bool selectBDAddr20Only(SDValue Addr, SDValue &Base, SDValue &Disp) const { 192 return selectBDAddr(SystemZAddressingMode::Disp20Only, Addr, Base, Disp); 193 } 194 bool selectBDAddr20Pair(SDValue Addr, SDValue &Base, SDValue &Disp) const { 195 return selectBDAddr(SystemZAddressingMode::Disp20Pair, Addr, Base, Disp); 196 } 197 198 // MVI matching routines used by SystemZOperands.td. 199 bool selectMVIAddr12Pair(SDValue Addr, SDValue &Base, SDValue &Disp) const { 200 return selectMVIAddr(SystemZAddressingMode::Disp12Pair, Addr, Base, Disp); 201 } 202 bool selectMVIAddr20Pair(SDValue Addr, SDValue &Base, SDValue &Disp) const { 203 return selectMVIAddr(SystemZAddressingMode::Disp20Pair, Addr, Base, Disp); 204 } 205 206 // BDX matching routines used by SystemZOperands.td. 207 bool selectBDXAddr12Only(SDValue Addr, SDValue &Base, SDValue &Disp, 208 SDValue &Index) const { 209 return selectBDXAddr(SystemZAddressingMode::FormBDXNormal, 210 SystemZAddressingMode::Disp12Only, 211 Addr, Base, Disp, Index); 212 } 213 bool selectBDXAddr12Pair(SDValue Addr, SDValue &Base, SDValue &Disp, 214 SDValue &Index) const { 215 return selectBDXAddr(SystemZAddressingMode::FormBDXNormal, 216 SystemZAddressingMode::Disp12Pair, 217 Addr, Base, Disp, Index); 218 } 219 bool selectDynAlloc12Only(SDValue Addr, SDValue &Base, SDValue &Disp, 220 SDValue &Index) const { 221 return selectBDXAddr(SystemZAddressingMode::FormBDXDynAlloc, 222 SystemZAddressingMode::Disp12Only, 223 Addr, Base, Disp, Index); 224 } 225 bool selectBDXAddr20Only(SDValue Addr, SDValue &Base, SDValue &Disp, 226 SDValue &Index) const { 227 return selectBDXAddr(SystemZAddressingMode::FormBDXNormal, 228 SystemZAddressingMode::Disp20Only, 229 Addr, Base, Disp, Index); 230 } 231 bool selectBDXAddr20Only128(SDValue Addr, SDValue &Base, SDValue &Disp, 232 SDValue &Index) const { 233 return selectBDXAddr(SystemZAddressingMode::FormBDXNormal, 234 SystemZAddressingMode::Disp20Only128, 235 Addr, Base, Disp, Index); 236 } 237 bool selectBDXAddr20Pair(SDValue Addr, SDValue &Base, SDValue &Disp, 238 SDValue &Index) const { 239 return selectBDXAddr(SystemZAddressingMode::FormBDXNormal, 240 SystemZAddressingMode::Disp20Pair, 241 Addr, Base, Disp, Index); 242 } 243 bool selectLAAddr12Pair(SDValue Addr, SDValue &Base, SDValue &Disp, 244 SDValue &Index) const { 245 return selectBDXAddr(SystemZAddressingMode::FormBDXLA, 246 SystemZAddressingMode::Disp12Pair, 247 Addr, Base, Disp, Index); 248 } 249 bool selectLAAddr20Pair(SDValue Addr, SDValue &Base, SDValue &Disp, 250 SDValue &Index) const { 251 return selectBDXAddr(SystemZAddressingMode::FormBDXLA, 252 SystemZAddressingMode::Disp20Pair, 253 Addr, Base, Disp, Index); 254 } 255 256 // Check whether (or Op (and X InsertMask)) is effectively an insertion 257 // of X into bits InsertMask of some Y != Op. Return true if so and 258 // set Op to that Y. 259 bool detectOrAndInsertion(SDValue &Op, uint64_t InsertMask) const; 260 261 // Try to update RxSBG so that only the bits of RxSBG.Input in Mask are used. 262 // Return true on success. 263 bool refineRxSBGMask(RxSBGOperands &RxSBG, uint64_t Mask) const; 264 265 // Try to fold some of RxSBG.Input into other fields of RxSBG. 266 // Return true on success. 267 bool expandRxSBG(RxSBGOperands &RxSBG) const; 268 269 // Return an undefined i64 value. 270 SDValue getUNDEF64(SDLoc DL) const; 271 272 // Convert N to VT, if it isn't already. 273 SDValue convertTo(SDLoc DL, EVT VT, SDValue N) const; 274 275 // Try to implement AND or shift node N using RISBG with the zero flag set. 276 // Return the selected node on success, otherwise return null. 277 SDNode *tryRISBGZero(SDNode *N); 278 279 // Try to use RISBG or Opcode to implement OR or XOR node N. 280 // Return the selected node on success, otherwise return null. 281 SDNode *tryRxSBG(SDNode *N, unsigned Opcode); 282 283 // If Op0 is null, then Node is a constant that can be loaded using: 284 // 285 // (Opcode UpperVal LowerVal) 286 // 287 // If Op0 is nonnull, then Node can be implemented using: 288 // 289 // (Opcode (Opcode Op0 UpperVal) LowerVal) 290 SDNode *splitLargeImmediate(unsigned Opcode, SDNode *Node, SDValue Op0, 291 uint64_t UpperVal, uint64_t LowerVal); 292 293 // Return true if Load and Store are loads and stores of the same size 294 // and are guaranteed not to overlap. Such operations can be implemented 295 // using block (SS-format) instructions. 296 // 297 // Partial overlap would lead to incorrect code, since the block operations 298 // are logically bytewise, even though they have a fast path for the 299 // non-overlapping case. We also need to avoid full overlap (i.e. two 300 // addresses that might be equal at run time) because although that case 301 // would be handled correctly, it might be implemented by millicode. 302 bool canUseBlockOperation(StoreSDNode *Store, LoadSDNode *Load) const; 303 304 // N is a (store (load Y), X) pattern. Return true if it can use an MVC 305 // from Y to X. 306 bool storeLoadCanUseMVC(SDNode *N) const; 307 308 // N is a (store (op (load A[0]), (load A[1])), X) pattern. Return true 309 // if A[1 - I] == X and if N can use a block operation like NC from A[I] 310 // to X. 311 bool storeLoadCanUseBlockBinary(SDNode *N, unsigned I) const; 312 313public: 314 SystemZDAGToDAGISel(SystemZTargetMachine &TM, CodeGenOpt::Level OptLevel) 315 : SelectionDAGISel(TM, OptLevel), 316 Lowering(*TM.getTargetLowering()), 317 Subtarget(*TM.getSubtargetImpl()) { } 318 319 // Override MachineFunctionPass. 320 virtual const char *getPassName() const LLVM_OVERRIDE { 321 return "SystemZ DAG->DAG Pattern Instruction Selection"; 322 } 323 324 // Override SelectionDAGISel. 325 virtual SDNode *Select(SDNode *Node) LLVM_OVERRIDE; 326 virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op, 327 char ConstraintCode, 328 std::vector<SDValue> &OutOps) 329 LLVM_OVERRIDE; 330 331 // Include the pieces autogenerated from the target description. 332 #include "SystemZGenDAGISel.inc" 333}; 334} // end anonymous namespace 335 336FunctionPass *llvm::createSystemZISelDag(SystemZTargetMachine &TM, 337 CodeGenOpt::Level OptLevel) { 338 return new SystemZDAGToDAGISel(TM, OptLevel); 339} 340 341// Return true if Val should be selected as a displacement for an address 342// with range DR. Here we're interested in the range of both the instruction 343// described by DR and of any pairing instruction. 344static bool selectDisp(SystemZAddressingMode::DispRange DR, int64_t Val) { 345 switch (DR) { 346 case SystemZAddressingMode::Disp12Only: 347 return isUInt<12>(Val); 348 349 case SystemZAddressingMode::Disp12Pair: 350 case SystemZAddressingMode::Disp20Only: 351 case SystemZAddressingMode::Disp20Pair: 352 return isInt<20>(Val); 353 354 case SystemZAddressingMode::Disp20Only128: 355 return isInt<20>(Val) && isInt<20>(Val + 8); 356 } 357 llvm_unreachable("Unhandled displacement range"); 358} 359 360// Change the base or index in AM to Value, where IsBase selects 361// between the base and index. 362static void changeComponent(SystemZAddressingMode &AM, bool IsBase, 363 SDValue Value) { 364 if (IsBase) 365 AM.Base = Value; 366 else 367 AM.Index = Value; 368} 369 370// The base or index of AM is equivalent to Value + ADJDYNALLOC, 371// where IsBase selects between the base and index. Try to fold the 372// ADJDYNALLOC into AM. 373static bool expandAdjDynAlloc(SystemZAddressingMode &AM, bool IsBase, 374 SDValue Value) { 375 if (AM.isDynAlloc() && !AM.IncludesDynAlloc) { 376 changeComponent(AM, IsBase, Value); 377 AM.IncludesDynAlloc = true; 378 return true; 379 } 380 return false; 381} 382 383// The base of AM is equivalent to Base + Index. Try to use Index as 384// the index register. 385static bool expandIndex(SystemZAddressingMode &AM, SDValue Base, 386 SDValue Index) { 387 if (AM.hasIndexField() && !AM.Index.getNode()) { 388 AM.Base = Base; 389 AM.Index = Index; 390 return true; 391 } 392 return false; 393} 394 395// The base or index of AM is equivalent to Op0 + Op1, where IsBase selects 396// between the base and index. Try to fold Op1 into AM's displacement. 397static bool expandDisp(SystemZAddressingMode &AM, bool IsBase, 398 SDValue Op0, uint64_t Op1) { 399 // First try adjusting the displacement. 400 int64_t TestDisp = AM.Disp + Op1; 401 if (selectDisp(AM.DR, TestDisp)) { 402 changeComponent(AM, IsBase, Op0); 403 AM.Disp = TestDisp; 404 return true; 405 } 406 407 // We could consider forcing the displacement into a register and 408 // using it as an index, but it would need to be carefully tuned. 409 return false; 410} 411 412bool SystemZDAGToDAGISel::expandAddress(SystemZAddressingMode &AM, 413 bool IsBase) const { 414 SDValue N = IsBase ? AM.Base : AM.Index; 415 unsigned Opcode = N.getOpcode(); 416 if (Opcode == ISD::TRUNCATE) { 417 N = N.getOperand(0); 418 Opcode = N.getOpcode(); 419 } 420 if (Opcode == ISD::ADD || CurDAG->isBaseWithConstantOffset(N)) { 421 SDValue Op0 = N.getOperand(0); 422 SDValue Op1 = N.getOperand(1); 423 424 unsigned Op0Code = Op0->getOpcode(); 425 unsigned Op1Code = Op1->getOpcode(); 426 427 if (Op0Code == SystemZISD::ADJDYNALLOC) 428 return expandAdjDynAlloc(AM, IsBase, Op1); 429 if (Op1Code == SystemZISD::ADJDYNALLOC) 430 return expandAdjDynAlloc(AM, IsBase, Op0); 431 432 if (Op0Code == ISD::Constant) 433 return expandDisp(AM, IsBase, Op1, 434 cast<ConstantSDNode>(Op0)->getSExtValue()); 435 if (Op1Code == ISD::Constant) 436 return expandDisp(AM, IsBase, Op0, 437 cast<ConstantSDNode>(Op1)->getSExtValue()); 438 439 if (IsBase && expandIndex(AM, Op0, Op1)) 440 return true; 441 } 442 if (Opcode == SystemZISD::PCREL_OFFSET) { 443 SDValue Full = N.getOperand(0); 444 SDValue Base = N.getOperand(1); 445 SDValue Anchor = Base.getOperand(0); 446 uint64_t Offset = (cast<GlobalAddressSDNode>(Full)->getOffset() - 447 cast<GlobalAddressSDNode>(Anchor)->getOffset()); 448 return expandDisp(AM, IsBase, Base, Offset); 449 } 450 return false; 451} 452 453// Return true if an instruction with displacement range DR should be 454// used for displacement value Val. selectDisp(DR, Val) must already hold. 455static bool isValidDisp(SystemZAddressingMode::DispRange DR, int64_t Val) { 456 assert(selectDisp(DR, Val) && "Invalid displacement"); 457 switch (DR) { 458 case SystemZAddressingMode::Disp12Only: 459 case SystemZAddressingMode::Disp20Only: 460 case SystemZAddressingMode::Disp20Only128: 461 return true; 462 463 case SystemZAddressingMode::Disp12Pair: 464 // Use the other instruction if the displacement is too large. 465 return isUInt<12>(Val); 466 467 case SystemZAddressingMode::Disp20Pair: 468 // Use the other instruction if the displacement is small enough. 469 return !isUInt<12>(Val); 470 } 471 llvm_unreachable("Unhandled displacement range"); 472} 473 474// Return true if Base + Disp + Index should be performed by LA(Y). 475static bool shouldUseLA(SDNode *Base, int64_t Disp, SDNode *Index) { 476 // Don't use LA(Y) for constants. 477 if (!Base) 478 return false; 479 480 // Always use LA(Y) for frame addresses, since we know that the destination 481 // register is almost always (perhaps always) going to be different from 482 // the frame register. 483 if (Base->getOpcode() == ISD::FrameIndex) 484 return true; 485 486 if (Disp) { 487 // Always use LA(Y) if there is a base, displacement and index. 488 if (Index) 489 return true; 490 491 // Always use LA if the displacement is small enough. It should always 492 // be no worse than AGHI (and better if it avoids a move). 493 if (isUInt<12>(Disp)) 494 return true; 495 496 // For similar reasons, always use LAY if the constant is too big for AGHI. 497 // LAY should be no worse than AGFI. 498 if (!isInt<16>(Disp)) 499 return true; 500 } else { 501 // Don't use LA for plain registers. 502 if (!Index) 503 return false; 504 505 // Don't use LA for plain addition if the index operand is only used 506 // once. It should be a natural two-operand addition in that case. 507 if (Index->hasOneUse()) 508 return false; 509 510 // Prefer addition if the second operation is sign-extended, in the 511 // hope of using AGF. 512 unsigned IndexOpcode = Index->getOpcode(); 513 if (IndexOpcode == ISD::SIGN_EXTEND || 514 IndexOpcode == ISD::SIGN_EXTEND_INREG) 515 return false; 516 } 517 518 // Don't use LA for two-operand addition if either operand is only 519 // used once. The addition instructions are better in that case. 520 if (Base->hasOneUse()) 521 return false; 522 523 return true; 524} 525 526// Return true if Addr is suitable for AM, updating AM if so. 527bool SystemZDAGToDAGISel::selectAddress(SDValue Addr, 528 SystemZAddressingMode &AM) const { 529 // Start out assuming that the address will need to be loaded separately, 530 // then try to extend it as much as we can. 531 AM.Base = Addr; 532 533 // First try treating the address as a constant. 534 if (Addr.getOpcode() == ISD::Constant && 535 expandDisp(AM, true, SDValue(), 536 cast<ConstantSDNode>(Addr)->getSExtValue())) 537 ; 538 else 539 // Otherwise try expanding each component. 540 while (expandAddress(AM, true) || 541 (AM.Index.getNode() && expandAddress(AM, false))) 542 continue; 543 544 // Reject cases where it isn't profitable to use LA(Y). 545 if (AM.Form == SystemZAddressingMode::FormBDXLA && 546 !shouldUseLA(AM.Base.getNode(), AM.Disp, AM.Index.getNode())) 547 return false; 548 549 // Reject cases where the other instruction in a pair should be used. 550 if (!isValidDisp(AM.DR, AM.Disp)) 551 return false; 552 553 // Make sure that ADJDYNALLOC is included where necessary. 554 if (AM.isDynAlloc() && !AM.IncludesDynAlloc) 555 return false; 556 557 DEBUG(AM.dump()); 558 return true; 559} 560 561// Insert a node into the DAG at least before Pos. This will reposition 562// the node as needed, and will assign it a node ID that is <= Pos's ID. 563// Note that this does *not* preserve the uniqueness of node IDs! 564// The selection DAG must no longer depend on their uniqueness when this 565// function is used. 566static void insertDAGNode(SelectionDAG *DAG, SDNode *Pos, SDValue N) { 567 if (N.getNode()->getNodeId() == -1 || 568 N.getNode()->getNodeId() > Pos->getNodeId()) { 569 DAG->RepositionNode(Pos, N.getNode()); 570 N.getNode()->setNodeId(Pos->getNodeId()); 571 } 572} 573 574void SystemZDAGToDAGISel::getAddressOperands(const SystemZAddressingMode &AM, 575 EVT VT, SDValue &Base, 576 SDValue &Disp) const { 577 Base = AM.Base; 578 if (!Base.getNode()) 579 // Register 0 means "no base". This is mostly useful for shifts. 580 Base = CurDAG->getRegister(0, VT); 581 else if (Base.getOpcode() == ISD::FrameIndex) { 582 // Lower a FrameIndex to a TargetFrameIndex. 583 int64_t FrameIndex = cast<FrameIndexSDNode>(Base)->getIndex(); 584 Base = CurDAG->getTargetFrameIndex(FrameIndex, VT); 585 } else if (Base.getValueType() != VT) { 586 // Truncate values from i64 to i32, for shifts. 587 assert(VT == MVT::i32 && Base.getValueType() == MVT::i64 && 588 "Unexpected truncation"); 589 SDLoc DL(Base); 590 SDValue Trunc = CurDAG->getNode(ISD::TRUNCATE, DL, VT, Base); 591 insertDAGNode(CurDAG, Base.getNode(), Trunc); 592 Base = Trunc; 593 } 594 595 // Lower the displacement to a TargetConstant. 596 Disp = CurDAG->getTargetConstant(AM.Disp, VT); 597} 598 599void SystemZDAGToDAGISel::getAddressOperands(const SystemZAddressingMode &AM, 600 EVT VT, SDValue &Base, 601 SDValue &Disp, 602 SDValue &Index) const { 603 getAddressOperands(AM, VT, Base, Disp); 604 605 Index = AM.Index; 606 if (!Index.getNode()) 607 // Register 0 means "no index". 608 Index = CurDAG->getRegister(0, VT); 609} 610 611bool SystemZDAGToDAGISel::selectBDAddr(SystemZAddressingMode::DispRange DR, 612 SDValue Addr, SDValue &Base, 613 SDValue &Disp) const { 614 SystemZAddressingMode AM(SystemZAddressingMode::FormBD, DR); 615 if (!selectAddress(Addr, AM)) 616 return false; 617 618 getAddressOperands(AM, Addr.getValueType(), Base, Disp); 619 return true; 620} 621 622bool SystemZDAGToDAGISel::selectMVIAddr(SystemZAddressingMode::DispRange DR, 623 SDValue Addr, SDValue &Base, 624 SDValue &Disp) const { 625 SystemZAddressingMode AM(SystemZAddressingMode::FormBDXNormal, DR); 626 if (!selectAddress(Addr, AM) || AM.Index.getNode()) 627 return false; 628 629 getAddressOperands(AM, Addr.getValueType(), Base, Disp); 630 return true; 631} 632 633bool SystemZDAGToDAGISel::selectBDXAddr(SystemZAddressingMode::AddrForm Form, 634 SystemZAddressingMode::DispRange DR, 635 SDValue Addr, SDValue &Base, 636 SDValue &Disp, SDValue &Index) const { 637 SystemZAddressingMode AM(Form, DR); 638 if (!selectAddress(Addr, AM)) 639 return false; 640 641 getAddressOperands(AM, Addr.getValueType(), Base, Disp, Index); 642 return true; 643} 644 645bool SystemZDAGToDAGISel::detectOrAndInsertion(SDValue &Op, 646 uint64_t InsertMask) const { 647 // We're only interested in cases where the insertion is into some operand 648 // of Op, rather than into Op itself. The only useful case is an AND. 649 if (Op.getOpcode() != ISD::AND) 650 return false; 651 652 // We need a constant mask. 653 ConstantSDNode *MaskNode = 654 dyn_cast<ConstantSDNode>(Op.getOperand(1).getNode()); 655 if (!MaskNode) 656 return false; 657 658 // It's not an insertion of Op.getOperand(0) if the two masks overlap. 659 uint64_t AndMask = MaskNode->getZExtValue(); 660 if (InsertMask & AndMask) 661 return false; 662 663 // It's only an insertion if all bits are covered or are known to be zero. 664 // The inner check covers all cases but is more expensive. 665 uint64_t Used = allOnes(Op.getValueType().getSizeInBits()); 666 if (Used != (AndMask | InsertMask)) { 667 APInt KnownZero, KnownOne; 668 CurDAG->ComputeMaskedBits(Op.getOperand(0), KnownZero, KnownOne); 669 if (Used != (AndMask | InsertMask | KnownZero.getZExtValue())) 670 return false; 671 } 672 673 Op = Op.getOperand(0); 674 return true; 675} 676 677bool SystemZDAGToDAGISel::refineRxSBGMask(RxSBGOperands &RxSBG, 678 uint64_t Mask) const { 679 const SystemZInstrInfo *TII = getInstrInfo(); 680 if (RxSBG.Rotate != 0) 681 Mask = (Mask << RxSBG.Rotate) | (Mask >> (64 - RxSBG.Rotate)); 682 Mask &= RxSBG.Mask; 683 if (TII->isRxSBGMask(Mask, RxSBG.BitSize, RxSBG.Start, RxSBG.End)) { 684 RxSBG.Mask = Mask; 685 return true; 686 } 687 return false; 688} 689 690// RxSBG.Input is a shift of Count bits in the direction given by IsLeft. 691// Return true if the result depends on the signs or zeros that are 692// shifted in. 693static bool shiftedInBitsMatter(RxSBGOperands &RxSBG, uint64_t Count, 694 bool IsLeft) { 695 // Work out which bits of the shift result are zeros or sign copies. 696 uint64_t ShiftedIn = allOnes(Count); 697 if (!IsLeft) 698 ShiftedIn <<= RxSBG.BitSize - Count; 699 700 // Rotate that mask in the same way as RxSBG.Input is rotated. 701 if (RxSBG.Rotate != 0) 702 ShiftedIn = ((ShiftedIn << RxSBG.Rotate) | 703 (ShiftedIn >> (64 - RxSBG.Rotate))); 704 705 // Fail if any of the zero or sign bits are used. 706 return (ShiftedIn & RxSBG.Mask) != 0; 707} 708 709bool SystemZDAGToDAGISel::expandRxSBG(RxSBGOperands &RxSBG) const { 710 SDValue N = RxSBG.Input; 711 unsigned Opcode = N.getOpcode(); 712 switch (Opcode) { 713 case ISD::AND: { 714 if (RxSBG.Opcode == SystemZ::RNSBG) 715 return false; 716 717 ConstantSDNode *MaskNode = 718 dyn_cast<ConstantSDNode>(N.getOperand(1).getNode()); 719 if (!MaskNode) 720 return false; 721 722 SDValue Input = N.getOperand(0); 723 uint64_t Mask = MaskNode->getZExtValue(); 724 if (!refineRxSBGMask(RxSBG, Mask)) { 725 // If some bits of Input are already known zeros, those bits will have 726 // been removed from the mask. See if adding them back in makes the 727 // mask suitable. 728 APInt KnownZero, KnownOne; 729 CurDAG->ComputeMaskedBits(Input, KnownZero, KnownOne); 730 Mask |= KnownZero.getZExtValue(); 731 if (!refineRxSBGMask(RxSBG, Mask)) 732 return false; 733 } 734 RxSBG.Input = Input; 735 return true; 736 } 737 738 case ISD::OR: { 739 if (RxSBG.Opcode != SystemZ::RNSBG) 740 return false; 741 742 ConstantSDNode *MaskNode = 743 dyn_cast<ConstantSDNode>(N.getOperand(1).getNode()); 744 if (!MaskNode) 745 return false; 746 747 SDValue Input = N.getOperand(0); 748 uint64_t Mask = ~MaskNode->getZExtValue(); 749 if (!refineRxSBGMask(RxSBG, Mask)) { 750 // If some bits of Input are already known ones, those bits will have 751 // been removed from the mask. See if adding them back in makes the 752 // mask suitable. 753 APInt KnownZero, KnownOne; 754 CurDAG->ComputeMaskedBits(Input, KnownZero, KnownOne); 755 Mask &= ~KnownOne.getZExtValue(); 756 if (!refineRxSBGMask(RxSBG, Mask)) 757 return false; 758 } 759 RxSBG.Input = Input; 760 return true; 761 } 762 763 case ISD::ROTL: { 764 // Any 64-bit rotate left can be merged into the RxSBG. 765 if (RxSBG.BitSize != 64) 766 return false; 767 ConstantSDNode *CountNode 768 = dyn_cast<ConstantSDNode>(N.getOperand(1).getNode()); 769 if (!CountNode) 770 return false; 771 772 RxSBG.Rotate = (RxSBG.Rotate + CountNode->getZExtValue()) & 63; 773 RxSBG.Input = N.getOperand(0); 774 return true; 775 } 776 777 case ISD::SHL: { 778 ConstantSDNode *CountNode = 779 dyn_cast<ConstantSDNode>(N.getOperand(1).getNode()); 780 if (!CountNode) 781 return false; 782 783 uint64_t Count = CountNode->getZExtValue(); 784 if (Count < 1 || Count >= RxSBG.BitSize) 785 return false; 786 787 if (RxSBG.Opcode == SystemZ::RNSBG) { 788 // Treat (shl X, count) as (rotl X, size-count) as long as the bottom 789 // count bits from RxSBG.Input are ignored. 790 if (shiftedInBitsMatter(RxSBG, Count, true)) 791 return false; 792 } else { 793 // Treat (shl X, count) as (and (rotl X, count), ~0<<count). 794 if (!refineRxSBGMask(RxSBG, allOnes(RxSBG.BitSize - Count) << Count)) 795 return false; 796 } 797 798 RxSBG.Rotate = (RxSBG.Rotate + Count) & 63; 799 RxSBG.Input = N.getOperand(0); 800 return true; 801 } 802 803 case ISD::SRL: 804 case ISD::SRA: { 805 ConstantSDNode *CountNode = 806 dyn_cast<ConstantSDNode>(N.getOperand(1).getNode()); 807 if (!CountNode) 808 return false; 809 810 uint64_t Count = CountNode->getZExtValue(); 811 if (Count < 1 || Count >= RxSBG.BitSize) 812 return false; 813 814 if (RxSBG.Opcode == SystemZ::RNSBG || Opcode == ISD::SRA) { 815 // Treat (srl|sra X, count) as (rotl X, size-count) as long as the top 816 // count bits from RxSBG.Input are ignored. 817 if (shiftedInBitsMatter(RxSBG, Count, false)) 818 return false; 819 } else { 820 // Treat (srl X, count), mask) as (and (rotl X, size-count), ~0>>count), 821 // which is similar to SLL above. 822 if (!refineRxSBGMask(RxSBG, allOnes(RxSBG.BitSize - Count))) 823 return false; 824 } 825 826 RxSBG.Rotate = (RxSBG.Rotate - Count) & 63; 827 RxSBG.Input = N.getOperand(0); 828 return true; 829 } 830 default: 831 return false; 832 } 833} 834 835SDValue SystemZDAGToDAGISel::getUNDEF64(SDLoc DL) const { 836 SDNode *N = CurDAG->getMachineNode(TargetOpcode::IMPLICIT_DEF, DL, MVT::i64); 837 return SDValue(N, 0); 838} 839 840SDValue SystemZDAGToDAGISel::convertTo(SDLoc DL, EVT VT, SDValue N) const { 841 if (N.getValueType() == MVT::i32 && VT == MVT::i64) 842 return CurDAG->getTargetInsertSubreg(SystemZ::subreg_l32, 843 DL, VT, getUNDEF64(DL), N); 844 if (N.getValueType() == MVT::i64 && VT == MVT::i32) 845 return CurDAG->getTargetExtractSubreg(SystemZ::subreg_l32, DL, VT, N); 846 assert(N.getValueType() == VT && "Unexpected value types"); 847 return N; 848} 849 850SDNode *SystemZDAGToDAGISel::tryRISBGZero(SDNode *N) { 851 EVT VT = N->getValueType(0); 852 RxSBGOperands RISBG(SystemZ::RISBG, SDValue(N, 0)); 853 unsigned Count = 0; 854 while (expandRxSBG(RISBG)) 855 Count += 1; 856 if (Count == 0) 857 return 0; 858 if (Count == 1) { 859 // Prefer to use normal shift instructions over RISBG, since they can handle 860 // all cases and are sometimes shorter. 861 if (N->getOpcode() != ISD::AND) 862 return 0; 863 864 // Prefer register extensions like LLC over RISBG. Also prefer to start 865 // out with normal ANDs if one instruction would be enough. We can convert 866 // these ANDs into an RISBG later if a three-address instruction is useful. 867 if (VT == MVT::i32 || 868 RISBG.Mask == 0xff || 869 RISBG.Mask == 0xffff || 870 SystemZ::isImmLF(~RISBG.Mask) || 871 SystemZ::isImmHF(~RISBG.Mask)) { 872 // Force the new mask into the DAG, since it may include known-one bits. 873 ConstantSDNode *MaskN = cast<ConstantSDNode>(N->getOperand(1).getNode()); 874 if (MaskN->getZExtValue() != RISBG.Mask) { 875 SDValue NewMask = CurDAG->getConstant(RISBG.Mask, VT); 876 N = CurDAG->UpdateNodeOperands(N, N->getOperand(0), NewMask); 877 return SelectCode(N); 878 } 879 return 0; 880 } 881 } 882 883 SDValue Ops[5] = { 884 getUNDEF64(SDLoc(N)), 885 convertTo(SDLoc(N), MVT::i64, RISBG.Input), 886 CurDAG->getTargetConstant(RISBG.Start, MVT::i32), 887 CurDAG->getTargetConstant(RISBG.End | 128, MVT::i32), 888 CurDAG->getTargetConstant(RISBG.Rotate, MVT::i32) 889 }; 890 N = CurDAG->getMachineNode(SystemZ::RISBG, SDLoc(N), MVT::i64, Ops); 891 return convertTo(SDLoc(N), VT, SDValue(N, 0)).getNode(); 892} 893 894SDNode *SystemZDAGToDAGISel::tryRxSBG(SDNode *N, unsigned Opcode) { 895 // Try treating each operand of N as the second operand of the RxSBG 896 // and see which goes deepest. 897 RxSBGOperands RxSBG[] = { 898 RxSBGOperands(Opcode, N->getOperand(0)), 899 RxSBGOperands(Opcode, N->getOperand(1)) 900 }; 901 unsigned Count[] = { 0, 0 }; 902 for (unsigned I = 0; I < 2; ++I) 903 while (expandRxSBG(RxSBG[I])) 904 Count[I] += 1; 905 906 // Do nothing if neither operand is suitable. 907 if (Count[0] == 0 && Count[1] == 0) 908 return 0; 909 910 // Pick the deepest second operand. 911 unsigned I = Count[0] > Count[1] ? 0 : 1; 912 SDValue Op0 = N->getOperand(I ^ 1); 913 914 // Prefer IC for character insertions from memory. 915 if (Opcode == SystemZ::ROSBG && (RxSBG[I].Mask & 0xff) == 0) 916 if (LoadSDNode *Load = dyn_cast<LoadSDNode>(Op0.getNode())) 917 if (Load->getMemoryVT() == MVT::i8) 918 return 0; 919 920 // See whether we can avoid an AND in the first operand by converting 921 // ROSBG to RISBG. 922 if (Opcode == SystemZ::ROSBG && detectOrAndInsertion(Op0, RxSBG[I].Mask)) 923 Opcode = SystemZ::RISBG; 924 925 EVT VT = N->getValueType(0); 926 SDValue Ops[5] = { 927 convertTo(SDLoc(N), MVT::i64, Op0), 928 convertTo(SDLoc(N), MVT::i64, RxSBG[I].Input), 929 CurDAG->getTargetConstant(RxSBG[I].Start, MVT::i32), 930 CurDAG->getTargetConstant(RxSBG[I].End, MVT::i32), 931 CurDAG->getTargetConstant(RxSBG[I].Rotate, MVT::i32) 932 }; 933 N = CurDAG->getMachineNode(Opcode, SDLoc(N), MVT::i64, Ops); 934 return convertTo(SDLoc(N), VT, SDValue(N, 0)).getNode(); 935} 936 937SDNode *SystemZDAGToDAGISel::splitLargeImmediate(unsigned Opcode, SDNode *Node, 938 SDValue Op0, uint64_t UpperVal, 939 uint64_t LowerVal) { 940 EVT VT = Node->getValueType(0); 941 SDLoc DL(Node); 942 SDValue Upper = CurDAG->getConstant(UpperVal, VT); 943 if (Op0.getNode()) 944 Upper = CurDAG->getNode(Opcode, DL, VT, Op0, Upper); 945 Upper = SDValue(Select(Upper.getNode()), 0); 946 947 SDValue Lower = CurDAG->getConstant(LowerVal, VT); 948 SDValue Or = CurDAG->getNode(Opcode, DL, VT, Upper, Lower); 949 return Or.getNode(); 950} 951 952bool SystemZDAGToDAGISel::canUseBlockOperation(StoreSDNode *Store, 953 LoadSDNode *Load) const { 954 // Check that the two memory operands have the same size. 955 if (Load->getMemoryVT() != Store->getMemoryVT()) 956 return false; 957 958 // Volatility stops an access from being decomposed. 959 if (Load->isVolatile() || Store->isVolatile()) 960 return false; 961 962 // There's no chance of overlap if the load is invariant. 963 if (Load->isInvariant()) 964 return true; 965 966 // Otherwise we need to check whether there's an alias. 967 const Value *V1 = Load->getSrcValue(); 968 const Value *V2 = Store->getSrcValue(); 969 if (!V1 || !V2) 970 return false; 971 972 // Reject equality. 973 uint64_t Size = Load->getMemoryVT().getStoreSize(); 974 int64_t End1 = Load->getSrcValueOffset() + Size; 975 int64_t End2 = Store->getSrcValueOffset() + Size; 976 if (V1 == V2 && End1 == End2) 977 return false; 978 979 return !AA->alias(AliasAnalysis::Location(V1, End1, Load->getTBAAInfo()), 980 AliasAnalysis::Location(V2, End2, Store->getTBAAInfo())); 981} 982 983bool SystemZDAGToDAGISel::storeLoadCanUseMVC(SDNode *N) const { 984 StoreSDNode *Store = cast<StoreSDNode>(N); 985 LoadSDNode *Load = cast<LoadSDNode>(Store->getValue()); 986 987 // Prefer not to use MVC if either address can use ... RELATIVE LONG 988 // instructions. 989 uint64_t Size = Load->getMemoryVT().getStoreSize(); 990 if (Size > 1 && Size <= 8) { 991 // Prefer LHRL, LRL and LGRL. 992 if (SystemZISD::isPCREL(Load->getBasePtr().getOpcode())) 993 return false; 994 // Prefer STHRL, STRL and STGRL. 995 if (SystemZISD::isPCREL(Store->getBasePtr().getOpcode())) 996 return false; 997 } 998 999 return canUseBlockOperation(Store, Load); 1000} 1001 1002bool SystemZDAGToDAGISel::storeLoadCanUseBlockBinary(SDNode *N, 1003 unsigned I) const { 1004 StoreSDNode *StoreA = cast<StoreSDNode>(N); 1005 LoadSDNode *LoadA = cast<LoadSDNode>(StoreA->getValue().getOperand(1 - I)); 1006 LoadSDNode *LoadB = cast<LoadSDNode>(StoreA->getValue().getOperand(I)); 1007 return !LoadA->isVolatile() && canUseBlockOperation(StoreA, LoadB); 1008} 1009 1010SDNode *SystemZDAGToDAGISel::Select(SDNode *Node) { 1011 // Dump information about the Node being selected 1012 DEBUG(errs() << "Selecting: "; Node->dump(CurDAG); errs() << "\n"); 1013 1014 // If we have a custom node, we already have selected! 1015 if (Node->isMachineOpcode()) { 1016 DEBUG(errs() << "== "; Node->dump(CurDAG); errs() << "\n"); 1017 Node->setNodeId(-1); 1018 return 0; 1019 } 1020 1021 unsigned Opcode = Node->getOpcode(); 1022 SDNode *ResNode = 0; 1023 switch (Opcode) { 1024 case ISD::OR: 1025 if (Node->getOperand(1).getOpcode() != ISD::Constant) 1026 ResNode = tryRxSBG(Node, SystemZ::ROSBG); 1027 goto or_xor; 1028 1029 case ISD::XOR: 1030 if (Node->getOperand(1).getOpcode() != ISD::Constant) 1031 ResNode = tryRxSBG(Node, SystemZ::RXSBG); 1032 // Fall through. 1033 or_xor: 1034 // If this is a 64-bit operation in which both 32-bit halves are nonzero, 1035 // split the operation into two. 1036 if (!ResNode && Node->getValueType(0) == MVT::i64) 1037 if (ConstantSDNode *Op1 = dyn_cast<ConstantSDNode>(Node->getOperand(1))) { 1038 uint64_t Val = Op1->getZExtValue(); 1039 if (!SystemZ::isImmLF(Val) && !SystemZ::isImmHF(Val)) 1040 Node = splitLargeImmediate(Opcode, Node, Node->getOperand(0), 1041 Val - uint32_t(Val), uint32_t(Val)); 1042 } 1043 break; 1044 1045 case ISD::AND: 1046 if (Node->getOperand(1).getOpcode() != ISD::Constant) 1047 ResNode = tryRxSBG(Node, SystemZ::RNSBG); 1048 // Fall through. 1049 case ISD::ROTL: 1050 case ISD::SHL: 1051 case ISD::SRL: 1052 if (!ResNode) 1053 ResNode = tryRISBGZero(Node); 1054 break; 1055 1056 case ISD::Constant: 1057 // If this is a 64-bit constant that is out of the range of LLILF, 1058 // LLIHF and LGFI, split it into two 32-bit pieces. 1059 if (Node->getValueType(0) == MVT::i64) { 1060 uint64_t Val = cast<ConstantSDNode>(Node)->getZExtValue(); 1061 if (!SystemZ::isImmLF(Val) && !SystemZ::isImmHF(Val) && !isInt<32>(Val)) 1062 Node = splitLargeImmediate(ISD::OR, Node, SDValue(), 1063 Val - uint32_t(Val), uint32_t(Val)); 1064 } 1065 break; 1066 1067 case ISD::ATOMIC_LOAD_SUB: 1068 // Try to convert subtractions of constants to additions. 1069 if (ConstantSDNode *Op2 = dyn_cast<ConstantSDNode>(Node->getOperand(2))) { 1070 uint64_t Value = -Op2->getZExtValue(); 1071 EVT VT = Node->getValueType(0); 1072 if (VT == MVT::i32 || isInt<32>(Value)) { 1073 SDValue Ops[] = { Node->getOperand(0), Node->getOperand(1), 1074 CurDAG->getConstant(int32_t(Value), VT) }; 1075 Node = CurDAG->MorphNodeTo(Node, ISD::ATOMIC_LOAD_ADD, 1076 Node->getVTList(), Ops, array_lengthof(Ops)); 1077 } 1078 } 1079 break; 1080 1081 case SystemZISD::SELECT_CCMASK: { 1082 SDValue Op0 = Node->getOperand(0); 1083 SDValue Op1 = Node->getOperand(1); 1084 // Prefer to put any load first, so that it can be matched as a 1085 // conditional load. 1086 if (Op1.getOpcode() == ISD::LOAD && Op0.getOpcode() != ISD::LOAD) { 1087 SDValue CCValid = Node->getOperand(2); 1088 SDValue CCMask = Node->getOperand(3); 1089 uint64_t ConstCCValid = 1090 cast<ConstantSDNode>(CCValid.getNode())->getZExtValue(); 1091 uint64_t ConstCCMask = 1092 cast<ConstantSDNode>(CCMask.getNode())->getZExtValue(); 1093 // Invert the condition. 1094 CCMask = CurDAG->getConstant(ConstCCValid ^ ConstCCMask, 1095 CCMask.getValueType()); 1096 SDValue Op4 = Node->getOperand(4); 1097 Node = CurDAG->UpdateNodeOperands(Node, Op1, Op0, CCValid, CCMask, Op4); 1098 } 1099 break; 1100 } 1101 } 1102 1103 // Select the default instruction 1104 if (!ResNode) 1105 ResNode = SelectCode(Node); 1106 1107 DEBUG(errs() << "=> "; 1108 if (ResNode == NULL || ResNode == Node) 1109 Node->dump(CurDAG); 1110 else 1111 ResNode->dump(CurDAG); 1112 errs() << "\n"; 1113 ); 1114 return ResNode; 1115} 1116 1117bool SystemZDAGToDAGISel:: 1118SelectInlineAsmMemoryOperand(const SDValue &Op, 1119 char ConstraintCode, 1120 std::vector<SDValue> &OutOps) { 1121 assert(ConstraintCode == 'm' && "Unexpected constraint code"); 1122 // Accept addresses with short displacements, which are compatible 1123 // with Q, R, S and T. But keep the index operand for future expansion. 1124 SDValue Base, Disp, Index; 1125 if (!selectBDXAddr(SystemZAddressingMode::FormBD, 1126 SystemZAddressingMode::Disp12Only, 1127 Op, Base, Disp, Index)) 1128 return true; 1129 OutOps.push_back(Base); 1130 OutOps.push_back(Disp); 1131 OutOps.push_back(Index); 1132 return false; 1133} 1134