lib/Target/SystemZ/SystemZISelDAGToDAG.cpp

   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
  20 using namespace llvm;
  21
  22 namespace {
  23 // Used to build addressing modes.
  24 struct 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 class SystemZDAGToDAGISel : public SelectionDAGISel {
  96   const SystemZTargetLowering &Lowering;
  97   const SystemZSubtarget &Subtarget;
  98
  99   // Used by SystemZOperands.td to create integer constants.
 100   inline SDValue getImm(const SDNode *Node, uint64_t Imm) {
 101     return CurDAG->getTargetConstant(Imm, Node->getValueType(0));
 102   }
 103
 104   // Try to fold more of the base or index of AM into AM, where IsBase
 105   // selects between the base and index.
 106   bool expandAddress(SystemZAddressingMode &AM, bool IsBase);
 107
 108   // Try to describe N in AM, returning true on success.
 109   bool selectAddress(SDValue N, SystemZAddressingMode &AM);
 110
 111   // Extract individual target operands from matched address AM.
 112   void getAddressOperands(const SystemZAddressingMode &AM, EVT VT,
 113                           SDValue &Base, SDValue &Disp);
 114   void getAddressOperands(const SystemZAddressingMode &AM, EVT VT,
 115                           SDValue &Base, SDValue &Disp, SDValue &Index);
 116
 117   // Try to match Addr as a FormBD address with displacement type DR.
 118   // Return true on success, storing the base and displacement in
 119   // Base and Disp respectively.
 120   bool selectBDAddr(SystemZAddressingMode::DispRange DR, SDValue Addr,
 121                     SDValue &Base, SDValue &Disp);
 122
 123   // Try to match Addr as a FormBDX* address of form Form with
 124   // displacement type DR.  Return true on success, storing the base,
 125   // displacement and index in Base, Disp and Index respectively.
 126   bool selectBDXAddr(SystemZAddressingMode::AddrForm Form,
 127                      SystemZAddressingMode::DispRange DR, SDValue Addr,
 128                      SDValue &Base, SDValue &Disp, SDValue &Index);
 129
 130   // PC-relative address matching routines used by SystemZOperands.td.
 131   bool selectPCRelAddress(SDValue Addr, SDValue &Target) {
 132     if (Addr.getOpcode() == SystemZISD::PCREL_WRAPPER) {
 133       Target = Addr.getOperand(0);
 134       return true;
 135     }
 136     return false;
 137   }
 138
 139   // BD matching routines used by SystemZOperands.td.
 140   bool selectBDAddr12Only(SDValue Addr, SDValue &Base, SDValue &Disp) {
 141     return selectBDAddr(SystemZAddressingMode::Disp12Only, Addr, Base, Disp);
 142   }
 143   bool selectBDAddr12Pair(SDValue Addr, SDValue &Base, SDValue &Disp) {
 144     return selectBDAddr(SystemZAddressingMode::Disp12Pair, Addr, Base, Disp);
 145   }
 146   bool selectBDAddr20Only(SDValue Addr, SDValue &Base, SDValue &Disp) {
 147     return selectBDAddr(SystemZAddressingMode::Disp20Only, Addr, Base, Disp);
 148   }
 149   bool selectBDAddr20Pair(SDValue Addr, SDValue &Base, SDValue &Disp) {
 150     return selectBDAddr(SystemZAddressingMode::Disp20Pair, Addr, Base, Disp);
 151   }
 152
 153   // BDX matching routines used by SystemZOperands.td.
 154   bool selectBDXAddr12Only(SDValue Addr, SDValue &Base, SDValue &Disp,
 155                            SDValue &Index) {
 156     return selectBDXAddr(SystemZAddressingMode::FormBDXNormal,
 157                          SystemZAddressingMode::Disp12Only,
 158                          Addr, Base, Disp, Index);
 159   }
 160   bool selectBDXAddr12Pair(SDValue Addr, SDValue &Base, SDValue &Disp,
 161                            SDValue &Index) {
 162     return selectBDXAddr(SystemZAddressingMode::FormBDXNormal,
 163                          SystemZAddressingMode::Disp12Pair,
 164                          Addr, Base, Disp, Index);
 165   }
 166   bool selectDynAlloc12Only(SDValue Addr, SDValue &Base, SDValue &Disp,
 167                             SDValue &Index) {
 168     return selectBDXAddr(SystemZAddressingMode::FormBDXDynAlloc,
 169                          SystemZAddressingMode::Disp12Only,
 170                          Addr, Base, Disp, Index);
 171   }
 172   bool selectBDXAddr20Only(SDValue Addr, SDValue &Base, SDValue &Disp,
 173                            SDValue &Index) {
 174     return selectBDXAddr(SystemZAddressingMode::FormBDXNormal,
 175                          SystemZAddressingMode::Disp20Only,
 176                          Addr, Base, Disp, Index);
 177   }
 178   bool selectBDXAddr20Only128(SDValue Addr, SDValue &Base, SDValue &Disp,
 179                               SDValue &Index) {
 180     return selectBDXAddr(SystemZAddressingMode::FormBDXNormal,
 181                          SystemZAddressingMode::Disp20Only128,
 182                          Addr, Base, Disp, Index);
 183   }
 184   bool selectBDXAddr20Pair(SDValue Addr, SDValue &Base, SDValue &Disp,
 185                            SDValue &Index) {
 186     return selectBDXAddr(SystemZAddressingMode::FormBDXNormal,
 187                          SystemZAddressingMode::Disp20Pair,
 188                          Addr, Base, Disp, Index);
 189   }
 190   bool selectLAAddr12Pair(SDValue Addr, SDValue &Base, SDValue &Disp,
 191                           SDValue &Index) {
 192     return selectBDXAddr(SystemZAddressingMode::FormBDXLA,
 193                          SystemZAddressingMode::Disp12Pair,
 194                          Addr, Base, Disp, Index);
 195   }
 196   bool selectLAAddr20Pair(SDValue Addr, SDValue &Base, SDValue &Disp,
 197                           SDValue &Index) {
 198     return selectBDXAddr(SystemZAddressingMode::FormBDXLA,
 199                          SystemZAddressingMode::Disp20Pair,
 200                          Addr, Base, Disp, Index);
 201   }
 202
 203   // Return an undefined i64 value.
 204   SDValue getUNDEF64(SDLoc DL);
 205
 206   // Convert N to VT, if it isn't already.
 207   SDValue convertTo(SDLoc DL, EVT VT, SDValue N);
 208
 209   // Try to use RISBG to implement ISD::AND node N.  Return the selected
 210   // node on success, otherwise return null.
 211   SDNode *tryRISBGForAND(SDNode *N);
 212
 213   // If Op0 is null, then Node is a constant that can be loaded using:
 214   //
 215   //   (Opcode UpperVal LowerVal)
 216   //
 217   // If Op0 is nonnull, then Node can be implemented using:
 218   //
 219   //   (Opcode (Opcode Op0 UpperVal) LowerVal)
 220   SDNode *splitLargeImmediate(unsigned Opcode, SDNode *Node, SDValue Op0,
 221                               uint64_t UpperVal, uint64_t LowerVal);
 222
 223   bool storeLoadCanUseMVC(SDNode *N) const;
 224
 225 public:
 226   SystemZDAGToDAGISel(SystemZTargetMachine &TM, CodeGenOpt::Level OptLevel)
 227     : SelectionDAGISel(TM, OptLevel),
 228       Lowering(*TM.getTargetLowering()),
 229       Subtarget(*TM.getSubtargetImpl()) { }
 230
 231   // Override MachineFunctionPass.
 232   virtual const char *getPassName() const LLVM_OVERRIDE {
 233     return "SystemZ DAG->DAG Pattern Instruction Selection";
 234   }
 235
 236   // Override SelectionDAGISel.
 237   virtual SDNode *Select(SDNode *Node) LLVM_OVERRIDE;
 238   virtual bool SelectInlineAsmMemoryOperand(const SDValue &Op,
 239                                             char ConstraintCode,
 240                                             std::vector<SDValue> &OutOps)
 241     LLVM_OVERRIDE;
 242
 243   // Include the pieces autogenerated from the target description.
 244   #include "SystemZGenDAGISel.inc"
 245 };
 246 } // end anonymous namespace
 247
 248 FunctionPass *llvm::createSystemZISelDag(SystemZTargetMachine &TM,
 249                                          CodeGenOpt::Level OptLevel) {
 250   return new SystemZDAGToDAGISel(TM, OptLevel);
 251 }
 252
 253 // Return true if Val should be selected as a displacement for an address
 254 // with range DR.  Here we're interested in the range of both the instruction
 255 // described by DR and of any pairing instruction.
 256 static bool selectDisp(SystemZAddressingMode::DispRange DR, int64_t Val) {
 257   switch (DR) {
 258   case SystemZAddressingMode::Disp12Only:
 259     return isUInt<12>(Val);
 260
 261   case SystemZAddressingMode::Disp12Pair:
 262   case SystemZAddressingMode::Disp20Only:
 263   case SystemZAddressingMode::Disp20Pair:
 264     return isInt<20>(Val);
 265
 266   case SystemZAddressingMode::Disp20Only128:
 267     return isInt<20>(Val) && isInt<20>(Val + 8);
 268   }
 269   llvm_unreachable("Unhandled displacement range");
 270 }
 271
 272 // Change the base or index in AM to Value, where IsBase selects
 273 // between the base and index.
 274 static void changeComponent(SystemZAddressingMode &AM, bool IsBase,
 275                             SDValue Value) {
 276   if (IsBase)
 277     AM.Base = Value;
 278   else
 279     AM.Index = Value;
 280 }
 281
 282 // The base or index of AM is equivalent to Value + ADJDYNALLOC,
 283 // where IsBase selects between the base and index.  Try to fold the
 284 // ADJDYNALLOC into AM.
 285 static bool expandAdjDynAlloc(SystemZAddressingMode &AM, bool IsBase,
 286                               SDValue Value) {
 287   if (AM.isDynAlloc() && !AM.IncludesDynAlloc) {
 288     changeComponent(AM, IsBase, Value);
 289     AM.IncludesDynAlloc = true;
 290     return true;
 291   }
 292   return false;
 293 }
 294
 295 // The base of AM is equivalent to Base + Index.  Try to use Index as
 296 // the index register.
 297 static bool expandIndex(SystemZAddressingMode &AM, SDValue Base,
 298                         SDValue Index) {
 299   if (AM.hasIndexField() && !AM.Index.getNode()) {
 300     AM.Base = Base;
 301     AM.Index = Index;
 302     return true;
 303   }
 304   return false;
 305 }
 306
 307 // The base or index of AM is equivalent to Op0 + Op1, where IsBase selects
 308 // between the base and index.  Try to fold Op1 into AM's displacement.
 309 static bool expandDisp(SystemZAddressingMode &AM, bool IsBase,
 310                        SDValue Op0, ConstantSDNode *Op1) {
 311   // First try adjusting the displacement.
 312   int64_t TestDisp = AM.Disp + Op1->getSExtValue();
 313   if (selectDisp(AM.DR, TestDisp)) {
 314     changeComponent(AM, IsBase, Op0);
 315     AM.Disp = TestDisp;
 316     return true;
 317   }
 318
 319   // We could consider forcing the displacement into a register and
 320   // using it as an index, but it would need to be carefully tuned.
 321   return false;
 322 }
 323
 324 bool SystemZDAGToDAGISel::expandAddress(SystemZAddressingMode &AM,
 325                                         bool IsBase) {
 326   SDValue N = IsBase ? AM.Base : AM.Index;
 327   unsigned Opcode = N.getOpcode();
 328   if (Opcode == ISD::TRUNCATE) {
 329     N = N.getOperand(0);
 330     Opcode = N.getOpcode();
 331   }
 332   if (Opcode == ISD::ADD || CurDAG->isBaseWithConstantOffset(N)) {
 333     SDValue Op0 = N.getOperand(0);
 334     SDValue Op1 = N.getOperand(1);
 335
 336     unsigned Op0Code = Op0->getOpcode();
 337     unsigned Op1Code = Op1->getOpcode();
 338
 339     if (Op0Code == SystemZISD::ADJDYNALLOC)
 340       return expandAdjDynAlloc(AM, IsBase, Op1);
 341     if (Op1Code == SystemZISD::ADJDYNALLOC)
 342       return expandAdjDynAlloc(AM, IsBase, Op0);
 343
 344     if (Op0Code == ISD::Constant)
 345       return expandDisp(AM, IsBase, Op1, cast<ConstantSDNode>(Op0));
 346     if (Op1Code == ISD::Constant)
 347       return expandDisp(AM, IsBase, Op0, cast<ConstantSDNode>(Op1));
 348
 349     if (IsBase && expandIndex(AM, Op0, Op1))
 350       return true;
 351   }
 352   return false;
 353 }
 354
 355 // Return true if an instruction with displacement range DR should be
 356 // used for displacement value Val.  selectDisp(DR, Val) must already hold.
 357 static bool isValidDisp(SystemZAddressingMode::DispRange DR, int64_t Val) {
 358   assert(selectDisp(DR, Val) && "Invalid displacement");
 359   switch (DR) {
 360   case SystemZAddressingMode::Disp12Only:
 361   case SystemZAddressingMode::Disp20Only:
 362   case SystemZAddressingMode::Disp20Only128:
 363     return true;
 364
 365   case SystemZAddressingMode::Disp12Pair:
 366     // Use the other instruction if the displacement is too large.
 367     return isUInt<12>(Val);
 368
 369   case SystemZAddressingMode::Disp20Pair:
 370     // Use the other instruction if the displacement is small enough.
 371     return !isUInt<12>(Val);
 372   }
 373   llvm_unreachable("Unhandled displacement range");
 374 }
 375
 376 // Return true if Base + Disp + Index should be performed by LA(Y).
 377 static bool shouldUseLA(SDNode *Base, int64_t Disp, SDNode *Index) {
 378   // Don't use LA(Y) for constants.
 379   if (!Base)
 380     return false;
 381
 382   // Always use LA(Y) for frame addresses, since we know that the destination
 383   // register is almost always (perhaps always) going to be different from
 384   // the frame register.
 385   if (Base->getOpcode() == ISD::FrameIndex)
 386     return true;
 387
 388   if (Disp) {
 389     // Always use LA(Y) if there is a base, displacement and index.
 390     if (Index)
 391       return true;
 392
 393     // Always use LA if the displacement is small enough.  It should always
 394     // be no worse than AGHI (and better if it avoids a move).
 395     if (isUInt<12>(Disp))
 396       return true;
 397
 398     // For similar reasons, always use LAY if the constant is too big for AGHI.
 399     // LAY should be no worse than AGFI.
 400     if (!isInt<16>(Disp))
 401       return true;
 402   } else {
 403     // Don't use LA for plain registers.
 404     if (!Index)
 405       return false;
 406
 407     // Don't use LA for plain addition if the index operand is only used
 408     // once.  It should be a natural two-operand addition in that case.
 409     if (Index->hasOneUse())
 410       return false;
 411
 412     // Prefer addition if the second operation is sign-extended, in the
 413     // hope of using AGF.
 414     unsigned IndexOpcode = Index->getOpcode();
 415     if (IndexOpcode == ISD::SIGN_EXTEND ||
 416         IndexOpcode == ISD::SIGN_EXTEND_INREG)
 417       return false;
 418   }
 419
 420   // Don't use LA for two-operand addition if either operand is only
 421   // used once.  The addition instructions are better in that case.
 422   if (Base->hasOneUse())
 423     return false;
 424
 425   return true;
 426 }
 427
 428 // Return true if Addr is suitable for AM, updating AM if so.
 429 bool SystemZDAGToDAGISel::selectAddress(SDValue Addr,
 430                                         SystemZAddressingMode &AM) {
 431   // Start out assuming that the address will need to be loaded separately,
 432   // then try to extend it as much as we can.
 433   AM.Base = Addr;
 434
 435   // First try treating the address as a constant.
 436   if (Addr.getOpcode() == ISD::Constant &&
 437       expandDisp(AM, true, SDValue(), cast<ConstantSDNode>(Addr)))
 438     ;
 439   else
 440     // Otherwise try expanding each component.
 441     while (expandAddress(AM, true) ||
 442            (AM.Index.getNode() && expandAddress(AM, false)))
 443       continue;
 444
 445   // Reject cases where it isn't profitable to use LA(Y).
 446   if (AM.Form == SystemZAddressingMode::FormBDXLA &&
 447       !shouldUseLA(AM.Base.getNode(), AM.Disp, AM.Index.getNode()))
 448     return false;
 449
 450   // Reject cases where the other instruction in a pair should be used.
 451   if (!isValidDisp(AM.DR, AM.Disp))
 452     return false;
 453
 454   // Make sure that ADJDYNALLOC is included where necessary.
 455   if (AM.isDynAlloc() && !AM.IncludesDynAlloc)
 456     return false;
 457
 458   DEBUG(AM.dump());
 459   return true;
 460 }
 461
 462 // Insert a node into the DAG at least before Pos.  This will reposition
 463 // the node as needed, and will assign it a node ID that is <= Pos's ID.
 464 // Note that this does *not* preserve the uniqueness of node IDs!
 465 // The selection DAG must no longer depend on their uniqueness when this
 466 // function is used.
 467 static void insertDAGNode(SelectionDAG *DAG, SDNode *Pos, SDValue N) {
 468   if (N.getNode()->getNodeId() == -1 ||
 469       N.getNode()->getNodeId() > Pos->getNodeId()) {
 470     DAG->RepositionNode(Pos, N.getNode());
 471     N.getNode()->setNodeId(Pos->getNodeId());
 472   }
 473 }
 474
 475 void SystemZDAGToDAGISel::getAddressOperands(const SystemZAddressingMode &AM,
 476                                              EVT VT, SDValue &Base,
 477                                              SDValue &Disp) {
 478   Base = AM.Base;
 479   if (!Base.getNode())
 480     // Register 0 means "no base".  This is mostly useful for shifts.
 481     Base = CurDAG->getRegister(0, VT);
 482   else if (Base.getOpcode() == ISD::FrameIndex) {
 483     // Lower a FrameIndex to a TargetFrameIndex.
 484     int64_t FrameIndex = cast<FrameIndexSDNode>(Base)->getIndex();
 485     Base = CurDAG->getTargetFrameIndex(FrameIndex, VT);
 486   } else if (Base.getValueType() != VT) {
 487     // Truncate values from i64 to i32, for shifts.
 488     assert(VT == MVT::i32 && Base.getValueType() == MVT::i64 &&
 489            "Unexpected truncation");
 490     SDLoc DL(Base);
 491     SDValue Trunc = CurDAG->getNode(ISD::TRUNCATE, DL, VT, Base);
 492     insertDAGNode(CurDAG, Base.getNode(), Trunc);
 493     Base = Trunc;
 494   }
 495
 496   // Lower the displacement to a TargetConstant.
 497   Disp = CurDAG->getTargetConstant(AM.Disp, VT);
 498 }
 499
 500 void SystemZDAGToDAGISel::getAddressOperands(const SystemZAddressingMode &AM,
 501                                              EVT VT, SDValue &Base,
 502                                              SDValue &Disp, SDValue &Index) {
 503   getAddressOperands(AM, VT, Base, Disp);
 504
 505   Index = AM.Index;
 506   if (!Index.getNode())
 507     // Register 0 means "no index".
 508     Index = CurDAG->getRegister(0, VT);
 509 }
 510
 511 bool SystemZDAGToDAGISel::selectBDAddr(SystemZAddressingMode::DispRange DR,
 512                                        SDValue Addr, SDValue &Base,
 513                                        SDValue &Disp) {
 514   SystemZAddressingMode AM(SystemZAddressingMode::FormBD, DR);
 515   if (!selectAddress(Addr, AM))
 516     return false;
 517
 518   getAddressOperands(AM, Addr.getValueType(), Base, Disp);
 519   return true;
 520 }
 521
 522 bool SystemZDAGToDAGISel::selectBDXAddr(SystemZAddressingMode::AddrForm Form,
 523                                         SystemZAddressingMode::DispRange DR,
 524                                         SDValue Addr, SDValue &Base,
 525                                         SDValue &Disp, SDValue &Index) {
 526   SystemZAddressingMode AM(Form, DR);
 527   if (!selectAddress(Addr, AM))
 528     return false;
 529
 530   getAddressOperands(AM, Addr.getValueType(), Base, Disp, Index);
 531   return true;
 532 }
 533
 534 // Return true if Mask matches the regexp 0*1+0*, given that zero masks
 535 // have already been filtered out.  Store the first set bit in LSB and
 536 // the number of set bits in Length if so.
 537 static bool isStringOfOnes(uint64_t Mask, unsigned &LSB, unsigned &Length) {
 538   unsigned First = findFirstSet(Mask);
 539   uint64_t Top = (Mask >> First) + 1;
 540   if ((Top & -Top) == Top)
 541     {
 542       LSB = First;
 543       Length = findFirstSet(Top);
 544       return true;
 545     }
 546   return false;
 547 }
 548
 549 // Return a mask with Count low bits set.
 550 static uint64_t allOnes(unsigned int Count) {
 551   return Count == 0 ? 0 : (uint64_t(1) << (Count - 1) << 1) - 1;
 552 }
 553
 554 // Return true if RISBG can be used to extract the bits in Mask from
 555 // a value that has BitSize bits.  Store the start and end operands
 556 // (I3 and I4) in Start and End if so.
 557 static bool isRISBGMask(uint64_t Mask, unsigned BitSize, unsigned &Start,
 558                         unsigned &End) {
 559   // Reject trivial all-zero and all-one masks.
 560   uint64_t Used = allOnes(BitSize);
 561   if (Mask == 0 || Mask == Used)
 562     return false;
 563
 564   // Handle the 1+0+ or 0+1+0* cases.  Start then specifies the index of
 565   // the msb and End specifies the index of the lsb.
 566   unsigned LSB, Length;
 567   if (isStringOfOnes(Mask, LSB, Length))
 568     {
 569       Start = 63 - (LSB + Length - 1);
 570       End = 63 - LSB;
 571       return true;
 572     }
 573
 574   // Handle the wrap-around 1+0+1+ cases.  Start then specifies the msb
 575   // of the low 1s and End specifies the lsb of the high 1s.
 576   if (isStringOfOnes(Mask ^ Used, LSB, Length))
 577     {
 578       assert(LSB > 0 && "Bottom bit must be set");
 579       assert(LSB + Length < BitSize && "Top bit must be set");
 580       Start = 63 - (LSB - 1);
 581       End = 63 - (LSB + Length);
 582       return true;
 583     }
 584
 585   return false;
 586 }
 587
 588 SDValue SystemZDAGToDAGISel::getUNDEF64(SDLoc DL) {
 589   SDNode *N = CurDAG->getMachineNode(TargetOpcode::IMPLICIT_DEF, DL, MVT::i64);
 590   return SDValue(N, 0);
 591 }
 592
 593 SDValue SystemZDAGToDAGISel::convertTo(SDLoc DL, EVT VT, SDValue N) {
 594   if (N.getValueType() == MVT::i32 && VT == MVT::i64) {
 595     SDValue Index = CurDAG->getTargetConstant(SystemZ::subreg_32bit, MVT::i64);
 596     SDNode *Insert = CurDAG->getMachineNode(TargetOpcode::INSERT_SUBREG,
 597                                             DL, VT, getUNDEF64(DL), N, Index);
 598     return SDValue(Insert, 0);
 599   }
 600   if (N.getValueType() == MVT::i64 && VT == MVT::i32) {
 601     SDValue Index = CurDAG->getTargetConstant(SystemZ::subreg_32bit, MVT::i64);
 602     SDNode *Extract = CurDAG->getMachineNode(TargetOpcode::EXTRACT_SUBREG,
 603                                              DL, VT, N, Index);
 604     return SDValue(Extract, 0);
 605   }
 606   assert(N.getValueType() == VT && "Unexpected value types");
 607   return N;
 608 }
 609
 610 SDNode *SystemZDAGToDAGISel::tryRISBGForAND(SDNode *N) {
 611   EVT VT = N->getValueType(0);
 612   unsigned BitSize = VT.getSizeInBits();
 613   unsigned Start, End;
 614   ConstantSDNode *MaskNode =
 615     dyn_cast<ConstantSDNode>(N->getOperand(1).getNode());
 616   if (!MaskNode)
 617     return 0;
 618
 619   SDValue Input = N->getOperand(0);
 620   uint64_t Mask = MaskNode->getZExtValue();
 621   if (!isRISBGMask(Mask, BitSize, Start, End)) {
 622     APInt KnownZero, KnownOne;
 623     CurDAG->ComputeMaskedBits(Input, KnownZero, KnownOne);
 624     Mask |= KnownZero.getZExtValue();
 625     if (!isRISBGMask(Mask, BitSize, Start, End))
 626       return 0;
 627   }
 628
 629   unsigned Rotate = 0;
 630   if (Input->getOpcode() == ISD::ROTL && BitSize == 64) {
 631     // Any 64-bit rotate left can be merged into the RISBG.
 632     if (ConstantSDNode *CountNode =
 633         dyn_cast<ConstantSDNode>(Input.getOperand(1).getNode())) {
 634       Rotate = CountNode->getZExtValue() & (BitSize - 1);
 635       Input = Input->getOperand(0);
 636     }
 637   } else if (Input->getOpcode() == ISD::SHL) {
 638     // Try to convert (and (shl X, count), mask) into
 639     // (and (rotl X, count), mask&(~0<<count)), where the new mask
 640     // removes bits from the original mask that are zeroed by the shl
 641     // but that are not necessarily zero in X.
 642     if (ConstantSDNode *CountNode =
 643         dyn_cast<ConstantSDNode>(Input.getOperand(1).getNode())) {
 644       uint64_t Count = CountNode->getZExtValue();
 645       if (Count > 0 &&
 646           Count < BitSize &&
 647           isRISBGMask(Mask & (allOnes(BitSize - Count) << Count),
 648                       BitSize, Start, End)) {
 649         Rotate = Count;
 650         Input = Input->getOperand(0);
 651       }
 652     }
 653   } else if (Input->getOpcode() == ISD::SRL) {
 654     // Try to convert (and (srl X, count), mask) into
 655     // (and (rotl X, size-count), mask&(~0>>count)), which is similar
 656     // to SLL above.
 657     if (ConstantSDNode *CountNode =
 658         dyn_cast<ConstantSDNode>(Input.getOperand(1).getNode())) {
 659       uint64_t Count = CountNode->getZExtValue();
 660       if (Count > 0 &&
 661           Count < BitSize &&
 662           isRISBGMask(Mask & allOnes(BitSize - Count), BitSize, Start, End)) {
 663         Rotate = 64 - Count;
 664         Input = Input->getOperand(0);
 665       }
 666     }
 667   } else if (Start <= End && Input->getOpcode() == ISD::SRA) {
 668     // Try to convert (and (sra X, count), mask) into
 669     // (and (rotl X, size-count), mask).  The mask must not include
 670     // any sign bits.
 671     if (ConstantSDNode *CountNode =
 672         dyn_cast<ConstantSDNode>(Input.getOperand(1).getNode())) {
 673       uint64_t Count = CountNode->getZExtValue();
 674       if (Count > 0 && Count < BitSize && Start >= 64 - (BitSize - Count)) {
 675         Rotate = 64 - Count;
 676         Input = Input->getOperand(0);
 677       }
 678     }
 679   }
 680
 681   // Prefer register extensions like LLC over RSIBG.
 682   if (Rotate == 0 && (Start == 32 || Start == 48 || Start == 56) && End == 63)
 683     return 0;
 684
 685   SDValue Ops[5] = {
 686     getUNDEF64(SDLoc(N)),
 687     convertTo(SDLoc(N), MVT::i64, Input),
 688     CurDAG->getTargetConstant(Start, MVT::i32),
 689     CurDAG->getTargetConstant(End | 128, MVT::i32),
 690     CurDAG->getTargetConstant(Rotate, MVT::i32)
 691   };
 692   N = CurDAG->getMachineNode(SystemZ::RISBG, SDLoc(N), MVT::i64, Ops);
 693   return convertTo(SDLoc(N), VT, SDValue(N, 0)).getNode();
 694 }
 695
 696 SDNode *SystemZDAGToDAGISel::splitLargeImmediate(unsigned Opcode, SDNode *Node,
 697                                                  SDValue Op0, uint64_t UpperVal,
 698                                                  uint64_t LowerVal) {
 699   EVT VT = Node->getValueType(0);
 700   SDLoc DL(Node);
 701   SDValue Upper = CurDAG->getConstant(UpperVal, VT);
 702   if (Op0.getNode())
 703     Upper = CurDAG->getNode(Opcode, DL, VT, Op0, Upper);
 704   Upper = SDValue(Select(Upper.getNode()), 0);
 705
 706   SDValue Lower = CurDAG->getConstant(LowerVal, VT);
 707   SDValue Or = CurDAG->getNode(Opcode, DL, VT, Upper, Lower);
 708   return Or.getNode();
 709 }
 710
 711 // N is a (store (load ...), ...) pattern.  Return true if it can use MVC.
 712 bool SystemZDAGToDAGISel::storeLoadCanUseMVC(SDNode *N) const {
 713   StoreSDNode *Store = cast<StoreSDNode>(N);
 714   LoadSDNode *Load = cast<LoadSDNode>(Store->getValue().getNode());
 715
 716   // MVC is logically a bytewise copy, so can't be used for volatile accesses.
 717   if (Load->isVolatile() || Store->isVolatile())
 718     return false;
 719
 720   // Prefer not to use MVC if either address can use ... RELATIVE LONG
 721   // instructions.
 722   assert(Load->getMemoryVT() == Store->getMemoryVT() &&
 723          "Should already have checked that the types match");
 724   uint64_t Size = Load->getMemoryVT().getStoreSize();
 725   if (Size > 1 && Size <= 8) {
 726     // Prefer LHRL, LRL and LGRL.
 727     if (Load->getBasePtr().getOpcode() == SystemZISD::PCREL_WRAPPER)
 728       return false;
 729     // Prefer STHRL, STRL and STGRL.
 730     if (Store->getBasePtr().getOpcode() == SystemZISD::PCREL_WRAPPER)
 731       return false;
 732   }
 733
 734   // There's no chance of overlap if the load is invariant.
 735   if (Load->isInvariant())
 736     return true;
 737
 738   // If both operands are aligned, they must be equal or not overlap.
 739   if (Load->getAlignment() >= Size && Store->getAlignment() >= Size)
 740     return true;
 741
 742   // Otherwise we need to check whether there's an alias.
 743   const Value *V1 = Load->getSrcValue();
 744   const Value *V2 = Store->getSrcValue();
 745   if (!V1 || !V2)
 746     return false;
 747
 748   int64_t End1 = Load->getSrcValueOffset() + Size;
 749   int64_t End2 = Store->getSrcValueOffset() + Size;
 750   return !AA->alias(AliasAnalysis::Location(V1, End1, Load->getTBAAInfo()),
 751                     AliasAnalysis::Location(V2, End2, Store->getTBAAInfo()));
 752 }
 753
 754 SDNode *SystemZDAGToDAGISel::Select(SDNode *Node) {
 755   // Dump information about the Node being selected
 756   DEBUG(errs() << "Selecting: "; Node->dump(CurDAG); errs() << "\n");
 757
 758   // If we have a custom node, we already have selected!
 759   if (Node->isMachineOpcode()) {
 760     DEBUG(errs() << "== "; Node->dump(CurDAG); errs() << "\n");
 761     return 0;
 762   }
 763
 764   unsigned Opcode = Node->getOpcode();
 765   SDNode *ResNode = 0;
 766   switch (Opcode) {
 767   case ISD::OR:
 768   case ISD::XOR:
 769     // If this is a 64-bit operation in which both 32-bit halves are nonzero,
 770     // split the operation into two.
 771     if (Node->getValueType(0) == MVT::i64)
 772       if (ConstantSDNode *Op1 = dyn_cast<ConstantSDNode>(Node->getOperand(1))) {
 773         uint64_t Val = Op1->getZExtValue();
 774         if (!SystemZ::isImmLF(Val) && !SystemZ::isImmHF(Val))
 775           Node = splitLargeImmediate(Opcode, Node, Node->getOperand(0),
 776                                      Val - uint32_t(Val), uint32_t(Val));
 777       }
 778     break;
 779
 780   case ISD::AND:
 781     ResNode = tryRISBGForAND(Node);
 782     break;
 783
 784   case ISD::Constant:
 785     // If this is a 64-bit constant that is out of the range of LLILF,
 786     // LLIHF and LGFI, split it into two 32-bit pieces.
 787     if (Node->getValueType(0) == MVT::i64) {
 788       uint64_t Val = cast<ConstantSDNode>(Node)->getZExtValue();
 789       if (!SystemZ::isImmLF(Val) && !SystemZ::isImmHF(Val) && !isInt<32>(Val))
 790         Node = splitLargeImmediate(ISD::OR, Node, SDValue(),
 791                                    Val - uint32_t(Val), uint32_t(Val));
 792     }
 793     break;
 794
 795   case ISD::ATOMIC_LOAD_SUB:
 796     // Try to convert subtractions of constants to additions.
 797     if (ConstantSDNode *Op2 = dyn_cast<ConstantSDNode>(Node->getOperand(2))) {
 798       uint64_t Value = -Op2->getZExtValue();
 799       EVT VT = Node->getValueType(0);
 800       if (VT == MVT::i32 || isInt<32>(Value)) {
 801         SDValue Ops[] = { Node->getOperand(0), Node->getOperand(1),
 802                           CurDAG->getConstant(int32_t(Value), VT) };
 803         Node = CurDAG->MorphNodeTo(Node, ISD::ATOMIC_LOAD_ADD,
 804                                    Node->getVTList(), Ops, array_lengthof(Ops));
 805       }
 806     }
 807     break;
 808   }
 809
 810   // Select the default instruction
 811   if (!ResNode)
 812     ResNode = SelectCode(Node);
 813
 814   DEBUG(errs() << "=> ";
 815         if (ResNode == NULL || ResNode == Node)
 816           Node->dump(CurDAG);
 817         else
 818           ResNode->dump(CurDAG);
 819         errs() << "\n";
 820         );
 821   return ResNode;
 822 }
 823
 824 bool SystemZDAGToDAGISel::
 825 SelectInlineAsmMemoryOperand(const SDValue &Op,
 826                              char ConstraintCode,
 827                              std::vector<SDValue> &OutOps) {
 828   assert(ConstraintCode == 'm' && "Unexpected constraint code");
 829   // Accept addresses with short displacements, which are compatible
 830   // with Q, R, S and T.  But keep the index operand for future expansion.
 831   SDValue Base, Disp, Index;
 832   if (!selectBDXAddr(SystemZAddressingMode::FormBD,
 833                      SystemZAddressingMode::Disp12Only,
 834                      Op, Base, Disp, Index))
 835     return true;
 836   OutOps.push_back(Base);
 837   OutOps.push_back(Disp);
 838   OutOps.push_back(Index);
 839   return false;
 840 }