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