contrib/llvm/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/KnownBits.h"
  19 #include "llvm/Support/raw_ostream.h"
  20
  21 using namespace llvm;
  22
  23 #define DEBUG_TYPE "systemz-isel"
  24
  25 namespace {
  26 // Used to build addressing modes.
  27 struct SystemZAddressingMode {
  28   // The shape of the address.
  29   enum AddrForm {
  30     // base+displacement
  31     FormBD,
  32
  33     // base+displacement+index for load and store operands
  34     FormBDXNormal,
  35
  36     // base+displacement+index for load address operands
  37     FormBDXLA,
  38
  39     // base+displacement+index+ADJDYNALLOC
  40     FormBDXDynAlloc
  41   };
  42   AddrForm Form;
  43
  44   // The type of displacement.  The enum names here correspond directly
  45   // to the definitions in SystemZOperand.td.  We could split them into
  46   // flags -- single/pair, 128-bit, etc. -- but it hardly seems worth it.
  47   enum DispRange {
  48     Disp12Only,
  49     Disp12Pair,
  50     Disp20Only,
  51     Disp20Only128,
  52     Disp20Pair
  53   };
  54   DispRange DR;
  55
  56   // The parts of the address.  The address is equivalent to:
  57   //
  58   //     Base + Disp + Index + (IncludesDynAlloc ? ADJDYNALLOC : 0)
  59   SDValue Base;
  60   int64_t Disp;
  61   SDValue Index;
  62   bool IncludesDynAlloc;
  63
  64   SystemZAddressingMode(AddrForm form, DispRange dr)
  65     : Form(form), DR(dr), Base(), Disp(0), Index(),
  66       IncludesDynAlloc(false) {}
  67
  68   // True if the address can have an index register.
  69   bool hasIndexField() { return Form != FormBD; }
  70
  71   // True if the address can (and must) include ADJDYNALLOC.
  72   bool isDynAlloc() { return Form == FormBDXDynAlloc; }
  73
  74   void dump(const llvm::SelectionDAG *DAG) {
  75     errs() << "SystemZAddressingMode " << this << '\n';
  76
  77     errs() << " Base ";
  78     if (Base.getNode())
  79       Base.getNode()->dump(DAG);
  80     else
  81       errs() << "null\n";
  82
  83     if (hasIndexField()) {
  84       errs() << " Index ";
  85       if (Index.getNode())
  86         Index.getNode()->dump(DAG);
  87       else
  88         errs() << "null\n";
  89     }
  90
  91     errs() << " Disp " << Disp;
  92     if (IncludesDynAlloc)
  93       errs() << " + ADJDYNALLOC";
  94     errs() << '\n';
  95   }
  96 };
  97
  98 // Return a mask with Count low bits set.
  99 static uint64_t allOnes(unsigned int Count) {
 100   assert(Count <= 64);
 101   if (Count > 63)
 102     return UINT64_MAX;
 103   return (uint64_t(1) << Count) - 1;
 104 }
 105
 106 // Represents operands 2 to 5 of the ROTATE AND ... SELECTED BITS operation
 107 // given by Opcode.  The operands are: Input (R2), Start (I3), End (I4) and
 108 // Rotate (I5).  The combined operand value is effectively:
 109 //
 110 //   (or (rotl Input, Rotate), ~Mask)
 111 //
 112 // for RNSBG and:
 113 //
 114 //   (and (rotl Input, Rotate), Mask)
 115 //
 116 // otherwise.  The output value has BitSize bits, although Input may be
 117 // narrower (in which case the upper bits are don't care), or wider (in which
 118 // case the result will be truncated as part of the operation).
 119 struct RxSBGOperands {
 120   RxSBGOperands(unsigned Op, SDValue N)
 121     : Opcode(Op), BitSize(N.getValueSizeInBits()),
 122       Mask(allOnes(BitSize)), Input(N), Start(64 - BitSize), End(63),
 123       Rotate(0) {}
 124
 125   unsigned Opcode;
 126   unsigned BitSize;
 127   uint64_t Mask;
 128   SDValue Input;
 129   unsigned Start;
 130   unsigned End;
 131   unsigned Rotate;
 132 };
 133
 134 class SystemZDAGToDAGISel : public SelectionDAGISel {
 135   const SystemZSubtarget *Subtarget;
 136
 137   // Used by SystemZOperands.td to create integer constants.
 138   inline SDValue getImm(const SDNode *Node, uint64_t Imm) const {
 139     return CurDAG->getTargetConstant(Imm, SDLoc(Node), Node->getValueType(0));
 140   }
 141
 142   const SystemZTargetMachine &getTargetMachine() const {
 143     return static_cast<const SystemZTargetMachine &>(TM);
 144   }
 145
 146   const SystemZInstrInfo *getInstrInfo() const {
 147     return Subtarget->getInstrInfo();
 148   }
 149
 150   // Try to fold more of the base or index of AM into AM, where IsBase
 151   // selects between the base and index.
 152   bool expandAddress(SystemZAddressingMode &AM, bool IsBase) const;
 153
 154   // Try to describe N in AM, returning true on success.
 155   bool selectAddress(SDValue N, SystemZAddressingMode &AM) const;
 156
 157   // Extract individual target operands from matched address AM.
 158   void getAddressOperands(const SystemZAddressingMode &AM, EVT VT,
 159                           SDValue &Base, SDValue &Disp) const;
 160   void getAddressOperands(const SystemZAddressingMode &AM, EVT VT,
 161                           SDValue &Base, SDValue &Disp, SDValue &Index) const;
 162
 163   // Try to match Addr as a FormBD address with displacement type DR.
 164   // Return true on success, storing the base and displacement in
 165   // Base and Disp respectively.
 166   bool selectBDAddr(SystemZAddressingMode::DispRange DR, SDValue Addr,
 167                     SDValue &Base, SDValue &Disp) const;
 168
 169   // Try to match Addr as a FormBDX address with displacement type DR.
 170   // Return true on success and if the result had no index.  Store the
 171   // base and displacement in Base and Disp respectively.
 172   bool selectMVIAddr(SystemZAddressingMode::DispRange DR, SDValue Addr,
 173                      SDValue &Base, SDValue &Disp) const;
 174
 175   // Try to match Addr as a FormBDX* address of form Form with
 176   // displacement type DR.  Return true on success, storing the base,
 177   // displacement and index in Base, Disp and Index respectively.
 178   bool selectBDXAddr(SystemZAddressingMode::AddrForm Form,
 179                      SystemZAddressingMode::DispRange DR, SDValue Addr,
 180                      SDValue &Base, SDValue &Disp, SDValue &Index) const;
 181
 182   // PC-relative address matching routines used by SystemZOperands.td.
 183   bool selectPCRelAddress(SDValue Addr, SDValue &Target) const {
 184     if (SystemZISD::isPCREL(Addr.getOpcode())) {
 185       Target = Addr.getOperand(0);
 186       return true;
 187     }
 188     return false;
 189   }
 190
 191   // BD matching routines used by SystemZOperands.td.
 192   bool selectBDAddr12Only(SDValue Addr, SDValue &Base, SDValue &Disp) const {
 193     return selectBDAddr(SystemZAddressingMode::Disp12Only, Addr, Base, Disp);
 194   }
 195   bool selectBDAddr12Pair(SDValue Addr, SDValue &Base, SDValue &Disp) const {
 196     return selectBDAddr(SystemZAddressingMode::Disp12Pair, Addr, Base, Disp);
 197   }
 198   bool selectBDAddr20Only(SDValue Addr, SDValue &Base, SDValue &Disp) const {
 199     return selectBDAddr(SystemZAddressingMode::Disp20Only, Addr, Base, Disp);
 200   }
 201   bool selectBDAddr20Pair(SDValue Addr, SDValue &Base, SDValue &Disp) const {
 202     return selectBDAddr(SystemZAddressingMode::Disp20Pair, Addr, Base, Disp);
 203   }
 204
 205   // MVI matching routines used by SystemZOperands.td.
 206   bool selectMVIAddr12Pair(SDValue Addr, SDValue &Base, SDValue &Disp) const {
 207     return selectMVIAddr(SystemZAddressingMode::Disp12Pair, Addr, Base, Disp);
 208   }
 209   bool selectMVIAddr20Pair(SDValue Addr, SDValue &Base, SDValue &Disp) const {
 210     return selectMVIAddr(SystemZAddressingMode::Disp20Pair, Addr, Base, Disp);
 211   }
 212
 213   // BDX matching routines used by SystemZOperands.td.
 214   bool selectBDXAddr12Only(SDValue Addr, SDValue &Base, SDValue &Disp,
 215                            SDValue &Index) const {
 216     return selectBDXAddr(SystemZAddressingMode::FormBDXNormal,
 217                          SystemZAddressingMode::Disp12Only,
 218                          Addr, Base, Disp, Index);
 219   }
 220   bool selectBDXAddr12Pair(SDValue Addr, SDValue &Base, SDValue &Disp,
 221                            SDValue &Index) const {
 222     return selectBDXAddr(SystemZAddressingMode::FormBDXNormal,
 223                          SystemZAddressingMode::Disp12Pair,
 224                          Addr, Base, Disp, Index);
 225   }
 226   bool selectDynAlloc12Only(SDValue Addr, SDValue &Base, SDValue &Disp,
 227                             SDValue &Index) const {
 228     return selectBDXAddr(SystemZAddressingMode::FormBDXDynAlloc,
 229                          SystemZAddressingMode::Disp12Only,
 230                          Addr, Base, Disp, Index);
 231   }
 232   bool selectBDXAddr20Only(SDValue Addr, SDValue &Base, SDValue &Disp,
 233                            SDValue &Index) const {
 234     return selectBDXAddr(SystemZAddressingMode::FormBDXNormal,
 235                          SystemZAddressingMode::Disp20Only,
 236                          Addr, Base, Disp, Index);
 237   }
 238   bool selectBDXAddr20Only128(SDValue Addr, SDValue &Base, SDValue &Disp,
 239                               SDValue &Index) const {
 240     return selectBDXAddr(SystemZAddressingMode::FormBDXNormal,
 241                          SystemZAddressingMode::Disp20Only128,
 242                          Addr, Base, Disp, Index);
 243   }
 244   bool selectBDXAddr20Pair(SDValue Addr, SDValue &Base, SDValue &Disp,
 245                            SDValue &Index) const {
 246     return selectBDXAddr(SystemZAddressingMode::FormBDXNormal,
 247                          SystemZAddressingMode::Disp20Pair,
 248                          Addr, Base, Disp, Index);
 249   }
 250   bool selectLAAddr12Pair(SDValue Addr, SDValue &Base, SDValue &Disp,
 251                           SDValue &Index) const {
 252     return selectBDXAddr(SystemZAddressingMode::FormBDXLA,
 253                          SystemZAddressingMode::Disp12Pair,
 254                          Addr, Base, Disp, Index);
 255   }
 256   bool selectLAAddr20Pair(SDValue Addr, SDValue &Base, SDValue &Disp,
 257                           SDValue &Index) const {
 258     return selectBDXAddr(SystemZAddressingMode::FormBDXLA,
 259                          SystemZAddressingMode::Disp20Pair,
 260                          Addr, Base, Disp, Index);
 261   }
 262
 263   // Try to match Addr as an address with a base, 12-bit displacement
 264   // and index, where the index is element Elem of a vector.
 265   // Return true on success, storing the base, displacement and vector
 266   // in Base, Disp and Index respectively.
 267   bool selectBDVAddr12Only(SDValue Addr, SDValue Elem, SDValue &Base,
 268                            SDValue &Disp, SDValue &Index) const;
 269
 270   // Check whether (or Op (and X InsertMask)) is effectively an insertion
 271   // of X into bits InsertMask of some Y != Op.  Return true if so and
 272   // set Op to that Y.
 273   bool detectOrAndInsertion(SDValue &Op, uint64_t InsertMask) const;
 274
 275   // Try to update RxSBG so that only the bits of RxSBG.Input in Mask are used.
 276   // Return true on success.
 277   bool refineRxSBGMask(RxSBGOperands &RxSBG, uint64_t Mask) const;
 278
 279   // Try to fold some of RxSBG.Input into other fields of RxSBG.
 280   // Return true on success.
 281   bool expandRxSBG(RxSBGOperands &RxSBG) const;
 282
 283   // Return an undefined value of type VT.
 284   SDValue getUNDEF(const SDLoc &DL, EVT VT) const;
 285
 286   // Convert N to VT, if it isn't already.
 287   SDValue convertTo(const SDLoc &DL, EVT VT, SDValue N) const;
 288
 289   // Try to implement AND or shift node N using RISBG with the zero flag set.
 290   // Return the selected node on success, otherwise return null.
 291   bool tryRISBGZero(SDNode *N);
 292
 293   // Try to use RISBG or Opcode to implement OR or XOR node N.
 294   // Return the selected node on success, otherwise return null.
 295   bool tryRxSBG(SDNode *N, unsigned Opcode);
 296
 297   // If Op0 is null, then Node is a constant that can be loaded using:
 298   //
 299   //   (Opcode UpperVal LowerVal)
 300   //
 301   // If Op0 is nonnull, then Node can be implemented using:
 302   //
 303   //   (Opcode (Opcode Op0 UpperVal) LowerVal)
 304   void splitLargeImmediate(unsigned Opcode, SDNode *Node, SDValue Op0,
 305                            uint64_t UpperVal, uint64_t LowerVal);
 306
 307   // Try to use gather instruction Opcode to implement vector insertion N.
 308   bool tryGather(SDNode *N, unsigned Opcode);
 309
 310   // Try to use scatter instruction Opcode to implement store Store.
 311   bool tryScatter(StoreSDNode *Store, unsigned Opcode);
 312
 313   // Change a chain of {load; op; store} of the same value into a simple op
 314   // through memory of that value, if the uses of the modified value and its
 315   // address are suitable.
 316   bool tryFoldLoadStoreIntoMemOperand(SDNode *Node);
 317
 318   // Return true if Load and Store are loads and stores of the same size
 319   // and are guaranteed not to overlap.  Such operations can be implemented
 320   // using block (SS-format) instructions.
 321   //
 322   // Partial overlap would lead to incorrect code, since the block operations
 323   // are logically bytewise, even though they have a fast path for the
 324   // non-overlapping case.  We also need to avoid full overlap (i.e. two
 325   // addresses that might be equal at run time) because although that case
 326   // would be handled correctly, it might be implemented by millicode.
 327   bool canUseBlockOperation(StoreSDNode *Store, LoadSDNode *Load) const;
 328
 329   // N is a (store (load Y), X) pattern.  Return true if it can use an MVC
 330   // from Y to X.
 331   bool storeLoadCanUseMVC(SDNode *N) const;
 332
 333   // N is a (store (op (load A[0]), (load A[1])), X) pattern.  Return true
 334   // if A[1 - I] == X and if N can use a block operation like NC from A[I]
 335   // to X.
 336   bool storeLoadCanUseBlockBinary(SDNode *N, unsigned I) const;
 337
 338   // Try to expand a boolean SELECT_CCMASK using an IPM sequence.
 339   SDValue expandSelectBoolean(SDNode *Node);
 340
 341 public:
 342   SystemZDAGToDAGISel(SystemZTargetMachine &TM, CodeGenOpt::Level OptLevel)
 343       : SelectionDAGISel(TM, OptLevel) {}
 344
 345   bool runOnMachineFunction(MachineFunction &MF) override {
 346     Subtarget = &MF.getSubtarget<SystemZSubtarget>();
 347     return SelectionDAGISel::runOnMachineFunction(MF);
 348   }
 349
 350   // Override MachineFunctionPass.
 351   StringRef getPassName() const override {
 352     return "SystemZ DAG->DAG Pattern Instruction Selection";
 353   }
 354
 355   // Override SelectionDAGISel.
 356   void Select(SDNode *Node) override;
 357   bool SelectInlineAsmMemoryOperand(const SDValue &Op, unsigned ConstraintID,
 358                                     std::vector<SDValue> &OutOps) override;
 359   bool IsProfitableToFold(SDValue N, SDNode *U, SDNode *Root) const override;
 360   void PreprocessISelDAG() override;
 361
 362   // Include the pieces autogenerated from the target description.
 363   #include "SystemZGenDAGISel.inc"
 364 };
 365 } // end anonymous namespace
 366
 367 FunctionPass *llvm::createSystemZISelDag(SystemZTargetMachine &TM,
 368                                          CodeGenOpt::Level OptLevel) {
 369   return new SystemZDAGToDAGISel(TM, OptLevel);
 370 }
 371
 372 // Return true if Val should be selected as a displacement for an address
 373 // with range DR.  Here we're interested in the range of both the instruction
 374 // described by DR and of any pairing instruction.
 375 static bool selectDisp(SystemZAddressingMode::DispRange DR, int64_t Val) {
 376   switch (DR) {
 377   case SystemZAddressingMode::Disp12Only:
 378     return isUInt<12>(Val);
 379
 380   case SystemZAddressingMode::Disp12Pair:
 381   case SystemZAddressingMode::Disp20Only:
 382   case SystemZAddressingMode::Disp20Pair:
 383     return isInt<20>(Val);
 384
 385   case SystemZAddressingMode::Disp20Only128:
 386     return isInt<20>(Val) && isInt<20>(Val + 8);
 387   }
 388   llvm_unreachable("Unhandled displacement range");
 389 }
 390
 391 // Change the base or index in AM to Value, where IsBase selects
 392 // between the base and index.
 393 static void changeComponent(SystemZAddressingMode &AM, bool IsBase,
 394                             SDValue Value) {
 395   if (IsBase)
 396     AM.Base = Value;
 397   else
 398     AM.Index = Value;
 399 }
 400
 401 // The base or index of AM is equivalent to Value + ADJDYNALLOC,
 402 // where IsBase selects between the base and index.  Try to fold the
 403 // ADJDYNALLOC into AM.
 404 static bool expandAdjDynAlloc(SystemZAddressingMode &AM, bool IsBase,
 405                               SDValue Value) {
 406   if (AM.isDynAlloc() && !AM.IncludesDynAlloc) {
 407     changeComponent(AM, IsBase, Value);
 408     AM.IncludesDynAlloc = true;
 409     return true;
 410   }
 411   return false;
 412 }
 413
 414 // The base of AM is equivalent to Base + Index.  Try to use Index as
 415 // the index register.
 416 static bool expandIndex(SystemZAddressingMode &AM, SDValue Base,
 417                         SDValue Index) {
 418   if (AM.hasIndexField() && !AM.Index.getNode()) {
 419     AM.Base = Base;
 420     AM.Index = Index;
 421     return true;
 422   }
 423   return false;
 424 }
 425
 426 // The base or index of AM is equivalent to Op0 + Op1, where IsBase selects
 427 // between the base and index.  Try to fold Op1 into AM's displacement.
 428 static bool expandDisp(SystemZAddressingMode &AM, bool IsBase,
 429                        SDValue Op0, uint64_t Op1) {
 430   // First try adjusting the displacement.
 431   int64_t TestDisp = AM.Disp + Op1;
 432   if (selectDisp(AM.DR, TestDisp)) {
 433     changeComponent(AM, IsBase, Op0);
 434     AM.Disp = TestDisp;
 435     return true;
 436   }
 437
 438   // We could consider forcing the displacement into a register and
 439   // using it as an index, but it would need to be carefully tuned.
 440   return false;
 441 }
 442
 443 bool SystemZDAGToDAGISel::expandAddress(SystemZAddressingMode &AM,
 444                                         bool IsBase) const {
 445   SDValue N = IsBase ? AM.Base : AM.Index;
 446   unsigned Opcode = N.getOpcode();
 447   if (Opcode == ISD::TRUNCATE) {
 448     N = N.getOperand(0);
 449     Opcode = N.getOpcode();
 450   }
 451   if (Opcode == ISD::ADD || CurDAG->isBaseWithConstantOffset(N)) {
 452     SDValue Op0 = N.getOperand(0);
 453     SDValue Op1 = N.getOperand(1);
 454
 455     unsigned Op0Code = Op0->getOpcode();
 456     unsigned Op1Code = Op1->getOpcode();
 457
 458     if (Op0Code == SystemZISD::ADJDYNALLOC)
 459       return expandAdjDynAlloc(AM, IsBase, Op1);
 460     if (Op1Code == SystemZISD::ADJDYNALLOC)
 461       return expandAdjDynAlloc(AM, IsBase, Op0);
 462
 463     if (Op0Code == ISD::Constant)
 464       return expandDisp(AM, IsBase, Op1,
 465                         cast<ConstantSDNode>(Op0)->getSExtValue());
 466     if (Op1Code == ISD::Constant)
 467       return expandDisp(AM, IsBase, Op0,
 468                         cast<ConstantSDNode>(Op1)->getSExtValue());
 469
 470     if (IsBase && expandIndex(AM, Op0, Op1))
 471       return true;
 472   }
 473   if (Opcode == SystemZISD::PCREL_OFFSET) {
 474     SDValue Full = N.getOperand(0);
 475     SDValue Base = N.getOperand(1);
 476     SDValue Anchor = Base.getOperand(0);
 477     uint64_t Offset = (cast<GlobalAddressSDNode>(Full)->getOffset() -
 478                        cast<GlobalAddressSDNode>(Anchor)->getOffset());
 479     return expandDisp(AM, IsBase, Base, Offset);
 480   }
 481   return false;
 482 }
 483
 484 // Return true if an instruction with displacement range DR should be
 485 // used for displacement value Val.  selectDisp(DR, Val) must already hold.
 486 static bool isValidDisp(SystemZAddressingMode::DispRange DR, int64_t Val) {
 487   assert(selectDisp(DR, Val) && "Invalid displacement");
 488   switch (DR) {
 489   case SystemZAddressingMode::Disp12Only:
 490   case SystemZAddressingMode::Disp20Only:
 491   case SystemZAddressingMode::Disp20Only128:
 492     return true;
 493
 494   case SystemZAddressingMode::Disp12Pair:
 495     // Use the other instruction if the displacement is too large.
 496     return isUInt<12>(Val);
 497
 498   case SystemZAddressingMode::Disp20Pair:
 499     // Use the other instruction if the displacement is small enough.
 500     return !isUInt<12>(Val);
 501   }
 502   llvm_unreachable("Unhandled displacement range");
 503 }
 504
 505 // Return true if Base + Disp + Index should be performed by LA(Y).
 506 static bool shouldUseLA(SDNode *Base, int64_t Disp, SDNode *Index) {
 507   // Don't use LA(Y) for constants.
 508   if (!Base)
 509     return false;
 510
 511   // Always use LA(Y) for frame addresses, since we know that the destination
 512   // register is almost always (perhaps always) going to be different from
 513   // the frame register.
 514   if (Base->getOpcode() == ISD::FrameIndex)
 515     return true;
 516
 517   if (Disp) {
 518     // Always use LA(Y) if there is a base, displacement and index.
 519     if (Index)
 520       return true;
 521
 522     // Always use LA if the displacement is small enough.  It should always
 523     // be no worse than AGHI (and better if it avoids a move).
 524     if (isUInt<12>(Disp))
 525       return true;
 526
 527     // For similar reasons, always use LAY if the constant is too big for AGHI.
 528     // LAY should be no worse than AGFI.
 529     if (!isInt<16>(Disp))
 530       return true;
 531   } else {
 532     // Don't use LA for plain registers.
 533     if (!Index)
 534       return false;
 535
 536     // Don't use LA for plain addition if the index operand is only used
 537     // once.  It should be a natural two-operand addition in that case.
 538     if (Index->hasOneUse())
 539       return false;
 540
 541     // Prefer addition if the second operation is sign-extended, in the
 542     // hope of using AGF.
 543     unsigned IndexOpcode = Index->getOpcode();
 544     if (IndexOpcode == ISD::SIGN_EXTEND ||
 545         IndexOpcode == ISD::SIGN_EXTEND_INREG)
 546       return false;
 547   }
 548
 549   // Don't use LA for two-operand addition if either operand is only
 550   // used once.  The addition instructions are better in that case.
 551   if (Base->hasOneUse())
 552     return false;
 553
 554   return true;
 555 }
 556
 557 // Return true if Addr is suitable for AM, updating AM if so.
 558 bool SystemZDAGToDAGISel::selectAddress(SDValue Addr,
 559                                         SystemZAddressingMode &AM) const {
 560   // Start out assuming that the address will need to be loaded separately,
 561   // then try to extend it as much as we can.
 562   AM.Base = Addr;
 563
 564   // First try treating the address as a constant.
 565   if (Addr.getOpcode() == ISD::Constant &&
 566       expandDisp(AM, true, SDValue(),
 567                  cast<ConstantSDNode>(Addr)->getSExtValue()))
 568     ;
 569   // Also see if it's a bare ADJDYNALLOC.
 570   else if (Addr.getOpcode() == SystemZISD::ADJDYNALLOC &&
 571            expandAdjDynAlloc(AM, true, SDValue()))
 572     ;
 573   else
 574     // Otherwise try expanding each component.
 575     while (expandAddress(AM, true) ||
 576            (AM.Index.getNode() && expandAddress(AM, false)))
 577       continue;
 578
 579   // Reject cases where it isn't profitable to use LA(Y).
 580   if (AM.Form == SystemZAddressingMode::FormBDXLA &&
 581       !shouldUseLA(AM.Base.getNode(), AM.Disp, AM.Index.getNode()))
 582     return false;
 583
 584   // Reject cases where the other instruction in a pair should be used.
 585   if (!isValidDisp(AM.DR, AM.Disp))
 586     return false;
 587
 588   // Make sure that ADJDYNALLOC is included where necessary.
 589   if (AM.isDynAlloc() && !AM.IncludesDynAlloc)
 590     return false;
 591
 592   LLVM_DEBUG(AM.dump(CurDAG));
 593   return true;
 594 }
 595
 596 // Insert a node into the DAG at least before Pos.  This will reposition
 597 // the node as needed, and will assign it a node ID that is <= Pos's ID.
 598 // Note that this does *not* preserve the uniqueness of node IDs!
 599 // The selection DAG must no longer depend on their uniqueness when this
 600 // function is used.
 601 static void insertDAGNode(SelectionDAG *DAG, SDNode *Pos, SDValue N) {
 602   if (N->getNodeId() == -1 ||
 603       (SelectionDAGISel::getUninvalidatedNodeId(N.getNode()) >
 604        SelectionDAGISel::getUninvalidatedNodeId(Pos))) {
 605     DAG->RepositionNode(Pos->getIterator(), N.getNode());
 606     // Mark Node as invalid for pruning as after this it may be a successor to a
 607     // selected node but otherwise be in the same position of Pos.
 608     // Conservatively mark it with the same -abs(Id) to assure node id
 609     // invariant is preserved.
 610     N->setNodeId(Pos->getNodeId());
 611     SelectionDAGISel::InvalidateNodeId(N.getNode());
 612   }
 613 }
 614
 615 void SystemZDAGToDAGISel::getAddressOperands(const SystemZAddressingMode &AM,
 616                                              EVT VT, SDValue &Base,
 617                                              SDValue &Disp) const {
 618   Base = AM.Base;
 619   if (!Base.getNode())
 620     // Register 0 means "no base".  This is mostly useful for shifts.
 621     Base = CurDAG->getRegister(0, VT);
 622   else if (Base.getOpcode() == ISD::FrameIndex) {
 623     // Lower a FrameIndex to a TargetFrameIndex.
 624     int64_t FrameIndex = cast<FrameIndexSDNode>(Base)->getIndex();
 625     Base = CurDAG->getTargetFrameIndex(FrameIndex, VT);
 626   } else if (Base.getValueType() != VT) {
 627     // Truncate values from i64 to i32, for shifts.
 628     assert(VT == MVT::i32 && Base.getValueType() == MVT::i64 &&
 629            "Unexpected truncation");
 630     SDLoc DL(Base);
 631     SDValue Trunc = CurDAG->getNode(ISD::TRUNCATE, DL, VT, Base);
 632     insertDAGNode(CurDAG, Base.getNode(), Trunc);
 633     Base = Trunc;
 634   }
 635
 636   // Lower the displacement to a TargetConstant.
 637   Disp = CurDAG->getTargetConstant(AM.Disp, SDLoc(Base), VT);
 638 }
 639
 640 void SystemZDAGToDAGISel::getAddressOperands(const SystemZAddressingMode &AM,
 641                                              EVT VT, SDValue &Base,
 642                                              SDValue &Disp,
 643                                              SDValue &Index) const {
 644   getAddressOperands(AM, VT, Base, Disp);
 645
 646   Index = AM.Index;
 647   if (!Index.getNode())
 648     // Register 0 means "no index".
 649     Index = CurDAG->getRegister(0, VT);
 650 }
 651
 652 bool SystemZDAGToDAGISel::selectBDAddr(SystemZAddressingMode::DispRange DR,
 653                                        SDValue Addr, SDValue &Base,
 654                                        SDValue &Disp) const {
 655   SystemZAddressingMode AM(SystemZAddressingMode::FormBD, DR);
 656   if (!selectAddress(Addr, AM))
 657     return false;
 658
 659   getAddressOperands(AM, Addr.getValueType(), Base, Disp);
 660   return true;
 661 }
 662
 663 bool SystemZDAGToDAGISel::selectMVIAddr(SystemZAddressingMode::DispRange DR,
 664                                         SDValue Addr, SDValue &Base,
 665                                         SDValue &Disp) const {
 666   SystemZAddressingMode AM(SystemZAddressingMode::FormBDXNormal, DR);
 667   if (!selectAddress(Addr, AM) || AM.Index.getNode())
 668     return false;
 669
 670   getAddressOperands(AM, Addr.getValueType(), Base, Disp);
 671   return true;
 672 }
 673
 674 bool SystemZDAGToDAGISel::selectBDXAddr(SystemZAddressingMode::AddrForm Form,
 675                                         SystemZAddressingMode::DispRange DR,
 676                                         SDValue Addr, SDValue &Base,
 677                                         SDValue &Disp, SDValue &Index) const {
 678   SystemZAddressingMode AM(Form, DR);
 679   if (!selectAddress(Addr, AM))
 680     return false;
 681
 682   getAddressOperands(AM, Addr.getValueType(), Base, Disp, Index);
 683   return true;
 684 }
 685
 686 bool SystemZDAGToDAGISel::selectBDVAddr12Only(SDValue Addr, SDValue Elem,
 687                                               SDValue &Base,
 688                                               SDValue &Disp,
 689                                               SDValue &Index) const {
 690   SDValue Regs[2];
 691   if (selectBDXAddr12Only(Addr, Regs[0], Disp, Regs[1]) &&
 692       Regs[0].getNode() && Regs[1].getNode()) {
 693     for (unsigned int I = 0; I < 2; ++I) {
 694       Base = Regs[I];
 695       Index = Regs[1 - I];
 696       // We can't tell here whether the index vector has the right type
 697       // for the access; the caller needs to do that instead.
 698       if (Index.getOpcode() == ISD::ZERO_EXTEND)
 699         Index = Index.getOperand(0);
 700       if (Index.getOpcode() == ISD::EXTRACT_VECTOR_ELT &&
 701           Index.getOperand(1) == Elem) {
 702         Index = Index.getOperand(0);
 703         return true;
 704       }
 705     }
 706   }
 707   return false;
 708 }
 709
 710 bool SystemZDAGToDAGISel::detectOrAndInsertion(SDValue &Op,
 711                                                uint64_t InsertMask) const {
 712   // We're only interested in cases where the insertion is into some operand
 713   // of Op, rather than into Op itself.  The only useful case is an AND.
 714   if (Op.getOpcode() != ISD::AND)
 715     return false;
 716
 717   // We need a constant mask.
 718   auto *MaskNode = dyn_cast<ConstantSDNode>(Op.getOperand(1).getNode());
 719   if (!MaskNode)
 720     return false;
 721
 722   // It's not an insertion of Op.getOperand(0) if the two masks overlap.
 723   uint64_t AndMask = MaskNode->getZExtValue();
 724   if (InsertMask & AndMask)
 725     return false;
 726
 727   // It's only an insertion if all bits are covered or are known to be zero.
 728   // The inner check covers all cases but is more expensive.
 729   uint64_t Used = allOnes(Op.getValueSizeInBits());
 730   if (Used != (AndMask | InsertMask)) {
 731     KnownBits Known = CurDAG->computeKnownBits(Op.getOperand(0));
 732     if (Used != (AndMask | InsertMask | Known.Zero.getZExtValue()))
 733       return false;
 734   }
 735
 736   Op = Op.getOperand(0);
 737   return true;
 738 }
 739
 740 bool SystemZDAGToDAGISel::refineRxSBGMask(RxSBGOperands &RxSBG,
 741                                           uint64_t Mask) const {
 742   const SystemZInstrInfo *TII = getInstrInfo();
 743   if (RxSBG.Rotate != 0)
 744     Mask = (Mask << RxSBG.Rotate) | (Mask >> (64 - RxSBG.Rotate));
 745   Mask &= RxSBG.Mask;
 746   if (TII->isRxSBGMask(Mask, RxSBG.BitSize, RxSBG.Start, RxSBG.End)) {
 747     RxSBG.Mask = Mask;
 748     return true;
 749   }
 750   return false;
 751 }
 752
 753 // Return true if any bits of (RxSBG.Input & Mask) are significant.
 754 static bool maskMatters(RxSBGOperands &RxSBG, uint64_t Mask) {
 755   // Rotate the mask in the same way as RxSBG.Input is rotated.
 756   if (RxSBG.Rotate != 0)
 757     Mask = ((Mask << RxSBG.Rotate) | (Mask >> (64 - RxSBG.Rotate)));
 758   return (Mask & RxSBG.Mask) != 0;
 759 }
 760
 761 bool SystemZDAGToDAGISel::expandRxSBG(RxSBGOperands &RxSBG) const {
 762   SDValue N = RxSBG.Input;
 763   unsigned Opcode = N.getOpcode();
 764   switch (Opcode) {
 765   case ISD::TRUNCATE: {
 766     if (RxSBG.Opcode == SystemZ::RNSBG)
 767       return false;
 768     uint64_t BitSize = N.getValueSizeInBits();
 769     uint64_t Mask = allOnes(BitSize);
 770     if (!refineRxSBGMask(RxSBG, Mask))
 771       return false;
 772     RxSBG.Input = N.getOperand(0);
 773     return true;
 774   }
 775   case ISD::AND: {
 776     if (RxSBG.Opcode == SystemZ::RNSBG)
 777       return false;
 778
 779     auto *MaskNode = dyn_cast<ConstantSDNode>(N.getOperand(1).getNode());
 780     if (!MaskNode)
 781       return false;
 782
 783     SDValue Input = N.getOperand(0);
 784     uint64_t Mask = MaskNode->getZExtValue();
 785     if (!refineRxSBGMask(RxSBG, Mask)) {
 786       // If some bits of Input are already known zeros, those bits will have
 787       // been removed from the mask.  See if adding them back in makes the
 788       // mask suitable.
 789       KnownBits Known = CurDAG->computeKnownBits(Input);
 790       Mask |= Known.Zero.getZExtValue();
 791       if (!refineRxSBGMask(RxSBG, Mask))
 792         return false;
 793     }
 794     RxSBG.Input = Input;
 795     return true;
 796   }
 797
 798   case ISD::OR: {
 799     if (RxSBG.Opcode != SystemZ::RNSBG)
 800       return false;
 801
 802     auto *MaskNode = dyn_cast<ConstantSDNode>(N.getOperand(1).getNode());
 803     if (!MaskNode)
 804       return false;
 805
 806     SDValue Input = N.getOperand(0);
 807     uint64_t Mask = ~MaskNode->getZExtValue();
 808     if (!refineRxSBGMask(RxSBG, Mask)) {
 809       // If some bits of Input are already known ones, those bits will have
 810       // been removed from the mask.  See if adding them back in makes the
 811       // mask suitable.
 812       KnownBits Known = CurDAG->computeKnownBits(Input);
 813       Mask &= ~Known.One.getZExtValue();
 814       if (!refineRxSBGMask(RxSBG, Mask))
 815         return false;
 816     }
 817     RxSBG.Input = Input;
 818     return true;
 819   }
 820
 821   case ISD::ROTL: {
 822     // Any 64-bit rotate left can be merged into the RxSBG.
 823     if (RxSBG.BitSize != 64 || N.getValueType() != MVT::i64)
 824       return false;
 825     auto *CountNode = dyn_cast<ConstantSDNode>(N.getOperand(1).getNode());
 826     if (!CountNode)
 827       return false;
 828
 829     RxSBG.Rotate = (RxSBG.Rotate + CountNode->getZExtValue()) & 63;
 830     RxSBG.Input = N.getOperand(0);
 831     return true;
 832   }
 833
 834   case ISD::ANY_EXTEND:
 835     // Bits above the extended operand are don't-care.
 836     RxSBG.Input = N.getOperand(0);
 837     return true;
 838
 839   case ISD::ZERO_EXTEND:
 840     if (RxSBG.Opcode != SystemZ::RNSBG) {
 841       // Restrict the mask to the extended operand.
 842       unsigned InnerBitSize = N.getOperand(0).getValueSizeInBits();
 843       if (!refineRxSBGMask(RxSBG, allOnes(InnerBitSize)))
 844         return false;
 845
 846       RxSBG.Input = N.getOperand(0);
 847       return true;
 848     }
 849     LLVM_FALLTHROUGH;
 850
 851   case ISD::SIGN_EXTEND: {
 852     // Check that the extension bits are don't-care (i.e. are masked out
 853     // by the final mask).
 854     unsigned BitSize = N.getValueSizeInBits();
 855     unsigned InnerBitSize = N.getOperand(0).getValueSizeInBits();
 856     if (maskMatters(RxSBG, allOnes(BitSize) - allOnes(InnerBitSize))) {
 857       // In the case where only the sign bit is active, increase Rotate with
 858       // the extension width.
 859       if (RxSBG.Mask == 1 && RxSBG.Rotate == 1)
 860         RxSBG.Rotate += (BitSize - InnerBitSize);
 861       else
 862         return false;
 863     }
 864
 865     RxSBG.Input = N.getOperand(0);
 866     return true;
 867   }
 868
 869   case ISD::SHL: {
 870     auto *CountNode = dyn_cast<ConstantSDNode>(N.getOperand(1).getNode());
 871     if (!CountNode)
 872       return false;
 873
 874     uint64_t Count = CountNode->getZExtValue();
 875     unsigned BitSize = N.getValueSizeInBits();
 876     if (Count < 1 || Count >= BitSize)
 877       return false;
 878
 879     if (RxSBG.Opcode == SystemZ::RNSBG) {
 880       // Treat (shl X, count) as (rotl X, size-count) as long as the bottom
 881       // count bits from RxSBG.Input are ignored.
 882       if (maskMatters(RxSBG, allOnes(Count)))
 883         return false;
 884     } else {
 885       // Treat (shl X, count) as (and (rotl X, count), ~0<<count).
 886       if (!refineRxSBGMask(RxSBG, allOnes(BitSize - Count) << Count))
 887         return false;
 888     }
 889
 890     RxSBG.Rotate = (RxSBG.Rotate + Count) & 63;
 891     RxSBG.Input = N.getOperand(0);
 892     return true;
 893   }
 894
 895   case ISD::SRL:
 896   case ISD::SRA: {
 897     auto *CountNode = dyn_cast<ConstantSDNode>(N.getOperand(1).getNode());
 898     if (!CountNode)
 899       return false;
 900
 901     uint64_t Count = CountNode->getZExtValue();
 902     unsigned BitSize = N.getValueSizeInBits();
 903     if (Count < 1 || Count >= BitSize)
 904       return false;
 905
 906     if (RxSBG.Opcode == SystemZ::RNSBG || Opcode == ISD::SRA) {
 907       // Treat (srl|sra X, count) as (rotl X, size-count) as long as the top
 908       // count bits from RxSBG.Input are ignored.
 909       if (maskMatters(RxSBG, allOnes(Count) << (BitSize - Count)))
 910         return false;
 911     } else {
 912       // Treat (srl X, count), mask) as (and (rotl X, size-count), ~0>>count),
 913       // which is similar to SLL above.
 914       if (!refineRxSBGMask(RxSBG, allOnes(BitSize - Count)))
 915         return false;
 916     }
 917
 918     RxSBG.Rotate = (RxSBG.Rotate - Count) & 63;
 919     RxSBG.Input = N.getOperand(0);
 920     return true;
 921   }
 922   default:
 923     return false;
 924   }
 925 }
 926
 927 SDValue SystemZDAGToDAGISel::getUNDEF(const SDLoc &DL, EVT VT) const {
 928   SDNode *N = CurDAG->getMachineNode(TargetOpcode::IMPLICIT_DEF, DL, VT);
 929   return SDValue(N, 0);
 930 }
 931
 932 SDValue SystemZDAGToDAGISel::convertTo(const SDLoc &DL, EVT VT,
 933                                        SDValue N) const {
 934   if (N.getValueType() == MVT::i32 && VT == MVT::i64)
 935     return CurDAG->getTargetInsertSubreg(SystemZ::subreg_l32,
 936                                          DL, VT, getUNDEF(DL, MVT::i64), N);
 937   if (N.getValueType() == MVT::i64 && VT == MVT::i32)
 938     return CurDAG->getTargetExtractSubreg(SystemZ::subreg_l32, DL, VT, N);
 939   assert(N.getValueType() == VT && "Unexpected value types");
 940   return N;
 941 }
 942
 943 bool SystemZDAGToDAGISel::tryRISBGZero(SDNode *N) {
 944   SDLoc DL(N);
 945   EVT VT = N->getValueType(0);
 946   if (!VT.isInteger() || VT.getSizeInBits() > 64)
 947     return false;
 948   RxSBGOperands RISBG(SystemZ::RISBG, SDValue(N, 0));
 949   unsigned Count = 0;
 950   while (expandRxSBG(RISBG))
 951     // The widening or narrowing is expected to be free.
 952     // Counting widening or narrowing as a saved operation will result in
 953     // preferring an R*SBG over a simple shift/logical instruction.
 954     if (RISBG.Input.getOpcode() != ISD::ANY_EXTEND &&
 955         RISBG.Input.getOpcode() != ISD::TRUNCATE)
 956       Count += 1;
 957   if (Count == 0)
 958     return false;
 959
 960   // Prefer to use normal shift instructions over RISBG, since they can handle
 961   // all cases and are sometimes shorter.
 962   if (Count == 1 && N->getOpcode() != ISD::AND)
 963     return false;
 964
 965   // Prefer register extensions like LLC over RISBG.  Also prefer to start
 966   // out with normal ANDs if one instruction would be enough.  We can convert
 967   // these ANDs into an RISBG later if a three-address instruction is useful.
 968   if (RISBG.Rotate == 0) {
 969     bool PreferAnd = false;
 970     // Prefer AND for any 32-bit and-immediate operation.
 971     if (VT == MVT::i32)
 972       PreferAnd = true;
 973     // As well as for any 64-bit operation that can be implemented via LLC(R),
 974     // LLH(R), LLGT(R), or one of the and-immediate instructions.
 975     else if (RISBG.Mask == 0xff ||
 976              RISBG.Mask == 0xffff ||
 977              RISBG.Mask == 0x7fffffff ||
 978              SystemZ::isImmLF(~RISBG.Mask) ||
 979              SystemZ::isImmHF(~RISBG.Mask))
 980      PreferAnd = true;
 981     // And likewise for the LLZRGF instruction, which doesn't have a register
 982     // to register version.
 983     else if (auto *Load = dyn_cast<LoadSDNode>(RISBG.Input)) {
 984       if (Load->getMemoryVT() == MVT::i32 &&
 985           (Load->getExtensionType() == ISD::EXTLOAD ||
 986            Load->getExtensionType() == ISD::ZEXTLOAD) &&
 987           RISBG.Mask == 0xffffff00 &&
 988           Subtarget->hasLoadAndZeroRightmostByte())
 989       PreferAnd = true;
 990     }
 991     if (PreferAnd) {
 992       // Replace the current node with an AND.  Note that the current node
 993       // might already be that same AND, in which case it is already CSE'd
 994       // with it, and we must not call ReplaceNode.
 995       SDValue In = convertTo(DL, VT, RISBG.Input);
 996       SDValue Mask = CurDAG->getConstant(RISBG.Mask, DL, VT);
 997       SDValue New = CurDAG->getNode(ISD::AND, DL, VT, In, Mask);
 998       if (N != New.getNode()) {
 999         insertDAGNode(CurDAG, N, Mask);
1000         insertDAGNode(CurDAG, N, New);
1001         ReplaceNode(N, New.getNode());
1002         N = New.getNode();
1003       }
1004       // Now, select the machine opcode to implement this operation.
1005       if (!N->isMachineOpcode())
1006         SelectCode(N);
1007       return true;
1008     }
1009   }
1010
1011   unsigned Opcode = SystemZ::RISBG;
1012   // Prefer RISBGN if available, since it does not clobber CC.
1013   if (Subtarget->hasMiscellaneousExtensions())
1014     Opcode = SystemZ::RISBGN;
1015   EVT OpcodeVT = MVT::i64;
1016   if (VT == MVT::i32 && Subtarget->hasHighWord() &&
1017       // We can only use the 32-bit instructions if all source bits are
1018       // in the low 32 bits without wrapping, both after rotation (because
1019       // of the smaller range for Start and End) and before rotation
1020       // (because the input value is truncated).
1021       RISBG.Start >= 32 && RISBG.End >= RISBG.Start &&
1022       ((RISBG.Start + RISBG.Rotate) & 63) >= 32 &&
1023       ((RISBG.End + RISBG.Rotate) & 63) >=
1024       ((RISBG.Start + RISBG.Rotate) & 63)) {
1025     Opcode = SystemZ::RISBMux;
1026     OpcodeVT = MVT::i32;
1027     RISBG.Start &= 31;
1028     RISBG.End &= 31;
1029   }
1030   SDValue Ops[5] = {
1031     getUNDEF(DL, OpcodeVT),
1032     convertTo(DL, OpcodeVT, RISBG.Input),
1033     CurDAG->getTargetConstant(RISBG.Start, DL, MVT::i32),
1034     CurDAG->getTargetConstant(RISBG.End | 128, DL, MVT::i32),
1035     CurDAG->getTargetConstant(RISBG.Rotate, DL, MVT::i32)
1036   };
1037   SDValue New = convertTo(
1038       DL, VT, SDValue(CurDAG->getMachineNode(Opcode, DL, OpcodeVT, Ops), 0));
1039   ReplaceNode(N, New.getNode());
1040   return true;
1041 }
1042
1043 bool SystemZDAGToDAGISel::tryRxSBG(SDNode *N, unsigned Opcode) {
1044   SDLoc DL(N);
1045   EVT VT = N->getValueType(0);
1046   if (!VT.isInteger() || VT.getSizeInBits() > 64)
1047     return false;
1048   // Try treating each operand of N as the second operand of the RxSBG
1049   // and see which goes deepest.
1050   RxSBGOperands RxSBG[] = {
1051     RxSBGOperands(Opcode, N->getOperand(0)),
1052     RxSBGOperands(Opcode, N->getOperand(1))
1053   };
1054   unsigned Count[] = { 0, 0 };
1055   for (unsigned I = 0; I < 2; ++I)
1056     while (expandRxSBG(RxSBG[I]))
1057       // The widening or narrowing is expected to be free.
1058       // Counting widening or narrowing as a saved operation will result in
1059       // preferring an R*SBG over a simple shift/logical instruction.
1060       if (RxSBG[I].Input.getOpcode() != ISD::ANY_EXTEND &&
1061           RxSBG[I].Input.getOpcode() != ISD::TRUNCATE)
1062         Count[I] += 1;
1063
1064   // Do nothing if neither operand is suitable.
1065   if (Count[0] == 0 && Count[1] == 0)
1066     return false;
1067
1068   // Pick the deepest second operand.
1069   unsigned I = Count[0] > Count[1] ? 0 : 1;
1070   SDValue Op0 = N->getOperand(I ^ 1);
1071
1072   // Prefer IC for character insertions from memory.
1073   if (Opcode == SystemZ::ROSBG && (RxSBG[I].Mask & 0xff) == 0)
1074     if (auto *Load = dyn_cast<LoadSDNode>(Op0.getNode()))
1075       if (Load->getMemoryVT() == MVT::i8)
1076         return false;
1077
1078   // See whether we can avoid an AND in the first operand by converting
1079   // ROSBG to RISBG.
1080   if (Opcode == SystemZ::ROSBG && detectOrAndInsertion(Op0, RxSBG[I].Mask)) {
1081     Opcode = SystemZ::RISBG;
1082     // Prefer RISBGN if available, since it does not clobber CC.
1083     if (Subtarget->hasMiscellaneousExtensions())
1084       Opcode = SystemZ::RISBGN;
1085   }
1086
1087   SDValue Ops[5] = {
1088     convertTo(DL, MVT::i64, Op0),
1089     convertTo(DL, MVT::i64, RxSBG[I].Input),
1090     CurDAG->getTargetConstant(RxSBG[I].Start, DL, MVT::i32),
1091     CurDAG->getTargetConstant(RxSBG[I].End, DL, MVT::i32),
1092     CurDAG->getTargetConstant(RxSBG[I].Rotate, DL, MVT::i32)
1093   };
1094   SDValue New = convertTo(
1095       DL, VT, SDValue(CurDAG->getMachineNode(Opcode, DL, MVT::i64, Ops), 0));
1096   ReplaceNode(N, New.getNode());
1097   return true;
1098 }
1099
1100 void SystemZDAGToDAGISel::splitLargeImmediate(unsigned Opcode, SDNode *Node,
1101                                               SDValue Op0, uint64_t UpperVal,
1102                                               uint64_t LowerVal) {
1103   EVT VT = Node->getValueType(0);
1104   SDLoc DL(Node);
1105   SDValue Upper = CurDAG->getConstant(UpperVal, DL, VT);
1106   if (Op0.getNode())
1107     Upper = CurDAG->getNode(Opcode, DL, VT, Op0, Upper);
1108
1109   {
1110     // When we haven't passed in Op0, Upper will be a constant. In order to
1111     // prevent folding back to the large immediate in `Or = getNode(...)` we run
1112     // SelectCode first and end up with an opaque machine node. This means that
1113     // we need to use a handle to keep track of Upper in case it gets CSE'd by
1114     // SelectCode.
1115     //
1116     // Note that in the case where Op0 is passed in we could just call
1117     // SelectCode(Upper) later, along with the SelectCode(Or), and avoid needing
1118     // the handle at all, but it's fine to do it here.
1119     //
1120     // TODO: This is a pretty hacky way to do this. Can we do something that
1121     // doesn't require a two paragraph explanation?
1122     HandleSDNode Handle(Upper);
1123     SelectCode(Upper.getNode());
1124     Upper = Handle.getValue();
1125   }
1126
1127   SDValue Lower = CurDAG->getConstant(LowerVal, DL, VT);
1128   SDValue Or = CurDAG->getNode(Opcode, DL, VT, Upper, Lower);
1129
1130   ReplaceNode(Node, Or.getNode());
1131
1132   SelectCode(Or.getNode());
1133 }
1134
1135 bool SystemZDAGToDAGISel::tryGather(SDNode *N, unsigned Opcode) {
1136   SDValue ElemV = N->getOperand(2);
1137   auto *ElemN = dyn_cast<ConstantSDNode>(ElemV);
1138   if (!ElemN)
1139     return false;
1140
1141   unsigned Elem = ElemN->getZExtValue();
1142   EVT VT = N->getValueType(0);
1143   if (Elem >= VT.getVectorNumElements())
1144     return false;
1145
1146   auto *Load = dyn_cast<LoadSDNode>(N->getOperand(1));
1147   if (!Load || !Load->hasNUsesOfValue(1, 0))
1148     return false;
1149   if (Load->getMemoryVT().getSizeInBits() !=
1150       Load->getValueType(0).getSizeInBits())
1151     return false;
1152
1153   SDValue Base, Disp, Index;
1154   if (!selectBDVAddr12Only(Load->getBasePtr(), ElemV, Base, Disp, Index) ||
1155       Index.getValueType() != VT.changeVectorElementTypeToInteger())
1156     return false;
1157
1158   SDLoc DL(Load);
1159   SDValue Ops[] = {
1160     N->getOperand(0), Base, Disp, Index,
1161     CurDAG->getTargetConstant(Elem, DL, MVT::i32), Load->getChain()
1162   };
1163   SDNode *Res = CurDAG->getMachineNode(Opcode, DL, VT, MVT::Other, Ops);
1164   ReplaceUses(SDValue(Load, 1), SDValue(Res, 1));
1165   ReplaceNode(N, Res);
1166   return true;
1167 }
1168
1169 bool SystemZDAGToDAGISel::tryScatter(StoreSDNode *Store, unsigned Opcode) {
1170   SDValue Value = Store->getValue();
1171   if (Value.getOpcode() != ISD::EXTRACT_VECTOR_ELT)
1172     return false;
1173   if (Store->getMemoryVT().getSizeInBits() != Value.getValueSizeInBits())
1174     return false;
1175
1176   SDValue ElemV = Value.getOperand(1);
1177   auto *ElemN = dyn_cast<ConstantSDNode>(ElemV);
1178   if (!ElemN)
1179     return false;
1180
1181   SDValue Vec = Value.getOperand(0);
1182   EVT VT = Vec.getValueType();
1183   unsigned Elem = ElemN->getZExtValue();
1184   if (Elem >= VT.getVectorNumElements())
1185     return false;
1186
1187   SDValue Base, Disp, Index;
1188   if (!selectBDVAddr12Only(Store->getBasePtr(), ElemV, Base, Disp, Index) ||
1189       Index.getValueType() != VT.changeVectorElementTypeToInteger())
1190     return false;
1191
1192   SDLoc DL(Store);
1193   SDValue Ops[] = {
1194     Vec, Base, Disp, Index, CurDAG->getTargetConstant(Elem, DL, MVT::i32),
1195     Store->getChain()
1196   };
1197   ReplaceNode(Store, CurDAG->getMachineNode(Opcode, DL, MVT::Other, Ops));
1198   return true;
1199 }
1200
1201 // Check whether or not the chain ending in StoreNode is suitable for doing
1202 // the {load; op; store} to modify transformation.
1203 static bool isFusableLoadOpStorePattern(StoreSDNode *StoreNode,
1204                                         SDValue StoredVal, SelectionDAG *CurDAG,
1205                                         LoadSDNode *&LoadNode,
1206                                         SDValue &InputChain) {
1207   // Is the stored value result 0 of the operation?
1208   if (StoredVal.getResNo() != 0)
1209     return false;
1210
1211   // Are there other uses of the loaded value than the operation?
1212   if (!StoredVal.getNode()->hasNUsesOfValue(1, 0))
1213     return false;
1214
1215   // Is the store non-extending and non-indexed?
1216   if (!ISD::isNormalStore(StoreNode) || StoreNode->isNonTemporal())
1217     return false;
1218
1219   SDValue Load = StoredVal->getOperand(0);
1220   // Is the stored value a non-extending and non-indexed load?
1221   if (!ISD::isNormalLoad(Load.getNode()))
1222     return false;
1223
1224   // Return LoadNode by reference.
1225   LoadNode = cast<LoadSDNode>(Load);
1226
1227   // Is store the only read of the loaded value?
1228   if (!Load.hasOneUse())
1229     return false;
1230
1231   // Is the address of the store the same as the load?
1232   if (LoadNode->getBasePtr() != StoreNode->getBasePtr() ||
1233       LoadNode->getOffset() != StoreNode->getOffset())
1234     return false;
1235
1236   // Check if the chain is produced by the load or is a TokenFactor with
1237   // the load output chain as an operand. Return InputChain by reference.
1238   SDValue Chain = StoreNode->getChain();
1239
1240   bool ChainCheck = false;
1241   if (Chain == Load.getValue(1)) {
1242     ChainCheck = true;
1243     InputChain = LoadNode->getChain();
1244   } else if (Chain.getOpcode() == ISD::TokenFactor) {
1245     SmallVector<SDValue, 4> ChainOps;
1246     for (unsigned i = 0, e = Chain.getNumOperands(); i != e; ++i) {
1247       SDValue Op = Chain.getOperand(i);
1248       if (Op == Load.getValue(1)) {
1249         ChainCheck = true;
1250         // Drop Load, but keep its chain. No cycle check necessary.
1251         ChainOps.push_back(Load.getOperand(0));
1252         continue;
1253       }
1254
1255       // Make sure using Op as part of the chain would not cause a cycle here.
1256       // In theory, we could check whether the chain node is a predecessor of
1257       // the load. But that can be very expensive. Instead visit the uses and
1258       // make sure they all have smaller node id than the load.
1259       int LoadId = LoadNode->getNodeId();
1260       for (SDNode::use_iterator UI = Op.getNode()->use_begin(),
1261              UE = UI->use_end(); UI != UE; ++UI) {
1262         if (UI.getUse().getResNo() != 0)
1263           continue;
1264         if (UI->getNodeId() > LoadId)
1265           return false;
1266       }
1267
1268       ChainOps.push_back(Op);
1269     }
1270
1271     if (ChainCheck)
1272       // Make a new TokenFactor with all the other input chains except
1273       // for the load.
1274       InputChain = CurDAG->getNode(ISD::TokenFactor, SDLoc(Chain),
1275                                    MVT::Other, ChainOps);
1276   }
1277   if (!ChainCheck)
1278     return false;
1279
1280   return true;
1281 }
1282
1283 // Change a chain of {load; op; store} of the same value into a simple op
1284 // through memory of that value, if the uses of the modified value and its
1285 // address are suitable.
1286 //
1287 // The tablegen pattern memory operand pattern is currently not able to match
1288 // the case where the CC on the original operation are used.
1289 //
1290 // See the equivalent routine in X86ISelDAGToDAG for further comments.
1291 bool SystemZDAGToDAGISel::tryFoldLoadStoreIntoMemOperand(SDNode *Node) {
1292   StoreSDNode *StoreNode = cast<StoreSDNode>(Node);
1293   SDValue StoredVal = StoreNode->getOperand(1);
1294   unsigned Opc = StoredVal->getOpcode();
1295   SDLoc DL(StoreNode);
1296
1297   // Before we try to select anything, make sure this is memory operand size
1298   // and opcode we can handle. Note that this must match the code below that
1299   // actually lowers the opcodes.
1300   EVT MemVT = StoreNode->getMemoryVT();
1301   unsigned NewOpc = 0;
1302   bool NegateOperand = false;
1303   switch (Opc) {
1304   default:
1305     return false;
1306   case SystemZISD::SSUBO:
1307     NegateOperand = true;
1308     LLVM_FALLTHROUGH;
1309   case SystemZISD::SADDO:
1310     if (MemVT == MVT::i32)
1311       NewOpc = SystemZ::ASI;
1312     else if (MemVT == MVT::i64)
1313       NewOpc = SystemZ::AGSI;
1314     else
1315       return false;
1316     break;
1317   case SystemZISD::USUBO:
1318     NegateOperand = true;
1319     LLVM_FALLTHROUGH;
1320   case SystemZISD::UADDO:
1321     if (MemVT == MVT::i32)
1322       NewOpc = SystemZ::ALSI;
1323     else if (MemVT == MVT::i64)
1324       NewOpc = SystemZ::ALGSI;
1325     else
1326       return false;
1327     break;
1328   }
1329
1330   LoadSDNode *LoadNode = nullptr;
1331   SDValue InputChain;
1332   if (!isFusableLoadOpStorePattern(StoreNode, StoredVal, CurDAG, LoadNode,
1333                                    InputChain))
1334     return false;
1335
1336   SDValue Operand = StoredVal.getOperand(1);
1337   auto *OperandC = dyn_cast<ConstantSDNode>(Operand);
1338   if (!OperandC)
1339     return false;
1340   auto OperandV = OperandC->getAPIntValue();
1341   if (NegateOperand)
1342     OperandV = -OperandV;
1343   if (OperandV.getMinSignedBits() > 8)
1344     return false;
1345   Operand = CurDAG->getTargetConstant(OperandV, DL, MemVT);
1346
1347   SDValue Base, Disp;
1348   if (!selectBDAddr20Only(StoreNode->getBasePtr(), Base, Disp))
1349     return false;
1350
1351   SDValue Ops[] = { Base, Disp, Operand, InputChain };
1352   MachineSDNode *Result =
1353     CurDAG->getMachineNode(NewOpc, DL, MVT::i32, MVT::Other, Ops);
1354   CurDAG->setNodeMemRefs(
1355       Result, {StoreNode->getMemOperand(), LoadNode->getMemOperand()});
1356
1357   ReplaceUses(SDValue(StoreNode, 0), SDValue(Result, 1));
1358   ReplaceUses(SDValue(StoredVal.getNode(), 1), SDValue(Result, 0));
1359   CurDAG->RemoveDeadNode(Node);
1360   return true;
1361 }
1362
1363 bool SystemZDAGToDAGISel::canUseBlockOperation(StoreSDNode *Store,
1364                                                LoadSDNode *Load) const {
1365   // Check that the two memory operands have the same size.
1366   if (Load->getMemoryVT() != Store->getMemoryVT())
1367     return false;
1368
1369   // Volatility stops an access from being decomposed.
1370   if (Load->isVolatile() || Store->isVolatile())
1371     return false;
1372
1373   // There's no chance of overlap if the load is invariant.
1374   if (Load->isInvariant() && Load->isDereferenceable())
1375     return true;
1376
1377   // Otherwise we need to check whether there's an alias.
1378   const Value *V1 = Load->getMemOperand()->getValue();
1379   const Value *V2 = Store->getMemOperand()->getValue();
1380   if (!V1 || !V2)
1381     return false;
1382
1383   // Reject equality.
1384   uint64_t Size = Load->getMemoryVT().getStoreSize();
1385   int64_t End1 = Load->getSrcValueOffset() + Size;
1386   int64_t End2 = Store->getSrcValueOffset() + Size;
1387   if (V1 == V2 && End1 == End2)
1388     return false;
1389
1390   return !AA->alias(MemoryLocation(V1, End1, Load->getAAInfo()),
1391                     MemoryLocation(V2, End2, Store->getAAInfo()));
1392 }
1393
1394 bool SystemZDAGToDAGISel::storeLoadCanUseMVC(SDNode *N) const {
1395   auto *Store = cast<StoreSDNode>(N);
1396   auto *Load = cast<LoadSDNode>(Store->getValue());
1397
1398   // Prefer not to use MVC if either address can use ... RELATIVE LONG
1399   // instructions.
1400   uint64_t Size = Load->getMemoryVT().getStoreSize();
1401   if (Size > 1 && Size <= 8) {
1402     // Prefer LHRL, LRL and LGRL.
1403     if (SystemZISD::isPCREL(Load->getBasePtr().getOpcode()))
1404       return false;
1405     // Prefer STHRL, STRL and STGRL.
1406     if (SystemZISD::isPCREL(Store->getBasePtr().getOpcode()))
1407       return false;
1408   }
1409
1410   return canUseBlockOperation(Store, Load);
1411 }
1412
1413 bool SystemZDAGToDAGISel::storeLoadCanUseBlockBinary(SDNode *N,
1414                                                      unsigned I) const {
1415   auto *StoreA = cast<StoreSDNode>(N);
1416   auto *LoadA = cast<LoadSDNode>(StoreA->getValue().getOperand(1 - I));
1417   auto *LoadB = cast<LoadSDNode>(StoreA->getValue().getOperand(I));
1418   return !LoadA->isVolatile() && canUseBlockOperation(StoreA, LoadB);
1419 }
1420
1421 void SystemZDAGToDAGISel::Select(SDNode *Node) {
1422   // If we have a custom node, we already have selected!
1423   if (Node->isMachineOpcode()) {
1424     LLVM_DEBUG(errs() << "== "; Node->dump(CurDAG); errs() << "\n");
1425     Node->setNodeId(-1);
1426     return;
1427   }
1428
1429   unsigned Opcode = Node->getOpcode();
1430   switch (Opcode) {
1431   case ISD::OR:
1432     if (Node->getOperand(1).getOpcode() != ISD::Constant)
1433       if (tryRxSBG(Node, SystemZ::ROSBG))
1434         return;
1435     goto or_xor;
1436
1437   case ISD::XOR:
1438     if (Node->getOperand(1).getOpcode() != ISD::Constant)
1439       if (tryRxSBG(Node, SystemZ::RXSBG))
1440         return;
1441     // Fall through.
1442   or_xor:
1443     // If this is a 64-bit operation in which both 32-bit halves are nonzero,
1444     // split the operation into two.  If both operands here happen to be
1445     // constant, leave this to common code to optimize.
1446     if (Node->getValueType(0) == MVT::i64 &&
1447         Node->getOperand(0).getOpcode() != ISD::Constant)
1448       if (auto *Op1 = dyn_cast<ConstantSDNode>(Node->getOperand(1))) {
1449         uint64_t Val = Op1->getZExtValue();
1450         if (!SystemZ::isImmLF(Val) && !SystemZ::isImmHF(Val)) {
1451           splitLargeImmediate(Opcode, Node, Node->getOperand(0),
1452                               Val - uint32_t(Val), uint32_t(Val));
1453           return;
1454         }
1455       }
1456     break;
1457
1458   case ISD::AND:
1459     if (Node->getOperand(1).getOpcode() != ISD::Constant)
1460       if (tryRxSBG(Node, SystemZ::RNSBG))
1461         return;
1462     LLVM_FALLTHROUGH;
1463   case ISD::ROTL:
1464   case ISD::SHL:
1465   case ISD::SRL:
1466   case ISD::ZERO_EXTEND:
1467     if (tryRISBGZero(Node))
1468       return;
1469     break;
1470
1471   case ISD::Constant:
1472     // If this is a 64-bit constant that is out of the range of LLILF,
1473     // LLIHF and LGFI, split it into two 32-bit pieces.
1474     if (Node->getValueType(0) == MVT::i64) {
1475       uint64_t Val = cast<ConstantSDNode>(Node)->getZExtValue();
1476       if (!SystemZ::isImmLF(Val) && !SystemZ::isImmHF(Val) && !isInt<32>(Val)) {
1477         splitLargeImmediate(ISD::OR, Node, SDValue(), Val - uint32_t(Val),
1478                             uint32_t(Val));
1479         return;
1480       }
1481     }
1482     break;
1483
1484   case SystemZISD::SELECT_CCMASK: {
1485     SDValue Op0 = Node->getOperand(0);
1486     SDValue Op1 = Node->getOperand(1);
1487     // Prefer to put any load first, so that it can be matched as a
1488     // conditional load.  Likewise for constants in range for LOCHI.
1489     if ((Op1.getOpcode() == ISD::LOAD && Op0.getOpcode() != ISD::LOAD) ||
1490         (Subtarget->hasLoadStoreOnCond2() &&
1491          Node->getValueType(0).isInteger() &&
1492          Op1.getOpcode() == ISD::Constant &&
1493          isInt<16>(cast<ConstantSDNode>(Op1)->getSExtValue()) &&
1494          !(Op0.getOpcode() == ISD::Constant &&
1495            isInt<16>(cast<ConstantSDNode>(Op0)->getSExtValue())))) {
1496       SDValue CCValid = Node->getOperand(2);
1497       SDValue CCMask = Node->getOperand(3);
1498       uint64_t ConstCCValid =
1499         cast<ConstantSDNode>(CCValid.getNode())->getZExtValue();
1500       uint64_t ConstCCMask =
1501         cast<ConstantSDNode>(CCMask.getNode())->getZExtValue();
1502       // Invert the condition.
1503       CCMask = CurDAG->getConstant(ConstCCValid ^ ConstCCMask, SDLoc(Node),
1504                                    CCMask.getValueType());
1505       SDValue Op4 = Node->getOperand(4);
1506       SDNode *UpdatedNode =
1507         CurDAG->UpdateNodeOperands(Node, Op1, Op0, CCValid, CCMask, Op4);
1508       if (UpdatedNode != Node) {
1509         // In case this node already exists then replace Node with it.
1510         ReplaceNode(Node, UpdatedNode);
1511         Node = UpdatedNode;
1512       }
1513     }
1514     break;
1515   }
1516
1517   case ISD::INSERT_VECTOR_ELT: {
1518     EVT VT = Node->getValueType(0);
1519     unsigned ElemBitSize = VT.getScalarSizeInBits();
1520     if (ElemBitSize == 32) {
1521       if (tryGather(Node, SystemZ::VGEF))
1522         return;
1523     } else if (ElemBitSize == 64) {
1524       if (tryGather(Node, SystemZ::VGEG))
1525         return;
1526     }
1527     break;
1528   }
1529
1530   case ISD::STORE: {
1531     if (tryFoldLoadStoreIntoMemOperand(Node))
1532       return;
1533     auto *Store = cast<StoreSDNode>(Node);
1534     unsigned ElemBitSize = Store->getValue().getValueSizeInBits();
1535     if (ElemBitSize == 32) {
1536       if (tryScatter(Store, SystemZ::VSCEF))
1537         return;
1538     } else if (ElemBitSize == 64) {
1539       if (tryScatter(Store, SystemZ::VSCEG))
1540         return;
1541     }
1542     break;
1543   }
1544   }
1545
1546   SelectCode(Node);
1547 }
1548
1549 bool SystemZDAGToDAGISel::
1550 SelectInlineAsmMemoryOperand(const SDValue &Op,
1551                              unsigned ConstraintID,
1552                              std::vector<SDValue> &OutOps) {
1553   SystemZAddressingMode::AddrForm Form;
1554   SystemZAddressingMode::DispRange DispRange;
1555   SDValue Base, Disp, Index;
1556
1557   switch(ConstraintID) {
1558   default:
1559     llvm_unreachable("Unexpected asm memory constraint");
1560   case InlineAsm::Constraint_i:
1561   case InlineAsm::Constraint_Q:
1562     // Accept an address with a short displacement, but no index.
1563     Form = SystemZAddressingMode::FormBD;
1564     DispRange = SystemZAddressingMode::Disp12Only;
1565     break;
1566   case InlineAsm::Constraint_R:
1567     // Accept an address with a short displacement and an index.
1568     Form = SystemZAddressingMode::FormBDXNormal;
1569     DispRange = SystemZAddressingMode::Disp12Only;
1570     break;
1571   case InlineAsm::Constraint_S:
1572     // Accept an address with a long displacement, but no index.
1573     Form = SystemZAddressingMode::FormBD;
1574     DispRange = SystemZAddressingMode::Disp20Only;
1575     break;
1576   case InlineAsm::Constraint_T:
1577   case InlineAsm::Constraint_m:
1578   case InlineAsm::Constraint_o:
1579     // Accept an address with a long displacement and an index.
1580     // m works the same as T, as this is the most general case.
1581     // We don't really have any special handling of "offsettable"
1582     // memory addresses, so just treat o the same as m.
1583     Form = SystemZAddressingMode::FormBDXNormal;
1584     DispRange = SystemZAddressingMode::Disp20Only;
1585     break;
1586   }
1587
1588   if (selectBDXAddr(Form, DispRange, Op, Base, Disp, Index)) {
1589     const TargetRegisterClass *TRC =
1590       Subtarget->getRegisterInfo()->getPointerRegClass(*MF);
1591     SDLoc DL(Base);
1592     SDValue RC = CurDAG->getTargetConstant(TRC->getID(), DL, MVT::i32);
1593
1594     // Make sure that the base address doesn't go into %r0.
1595     // If it's a TargetFrameIndex or a fixed register, we shouldn't do anything.
1596     if (Base.getOpcode() != ISD::TargetFrameIndex &&
1597         Base.getOpcode() != ISD::Register) {
1598       Base =
1599         SDValue(CurDAG->getMachineNode(TargetOpcode::COPY_TO_REGCLASS,
1600                                        DL, Base.getValueType(),
1601                                        Base, RC), 0);
1602     }
1603
1604     // Make sure that the index register isn't assigned to %r0 either.
1605     if (Index.getOpcode() != ISD::Register) {
1606       Index =
1607         SDValue(CurDAG->getMachineNode(TargetOpcode::COPY_TO_REGCLASS,
1608                                        DL, Index.getValueType(),
1609                                        Index, RC), 0);
1610     }
1611
1612     OutOps.push_back(Base);
1613     OutOps.push_back(Disp);
1614     OutOps.push_back(Index);
1615     return false;
1616   }
1617
1618   return true;
1619 }
1620
1621 // IsProfitableToFold - Returns true if is profitable to fold the specific
1622 // operand node N of U during instruction selection that starts at Root.
1623 bool
1624 SystemZDAGToDAGISel::IsProfitableToFold(SDValue N, SDNode *U,
1625                                         SDNode *Root) const {
1626   // We want to avoid folding a LOAD into an ICMP node if as a result
1627   // we would be forced to spill the condition code into a GPR.
1628   if (N.getOpcode() == ISD::LOAD && U->getOpcode() == SystemZISD::ICMP) {
1629     if (!N.hasOneUse() || !U->hasOneUse())
1630       return false;
1631
1632     // The user of the CC value will usually be a CopyToReg into the
1633     // physical CC register, which in turn is glued and chained to the
1634     // actual instruction that uses the CC value.  Bail out if we have
1635     // anything else than that.
1636     SDNode *CCUser = *U->use_begin();
1637     SDNode *CCRegUser = nullptr;
1638     if (CCUser->getOpcode() == ISD::CopyToReg ||
1639         cast<RegisterSDNode>(CCUser->getOperand(1))->getReg() == SystemZ::CC) {
1640       for (auto *U : CCUser->uses()) {
1641         if (CCRegUser == nullptr)
1642           CCRegUser = U;
1643         else if (CCRegUser != U)
1644           return false;
1645       }
1646     }
1647     if (CCRegUser == nullptr)
1648       return false;
1649
1650     // If the actual instruction is a branch, the only thing that remains to be
1651     // checked is whether the CCUser chain is a predecessor of the load.
1652     if (CCRegUser->isMachineOpcode() &&
1653         CCRegUser->getMachineOpcode() == SystemZ::BRC)
1654       return !N->isPredecessorOf(CCUser->getOperand(0).getNode());
1655
1656     // Otherwise, the instruction may have multiple operands, and we need to
1657     // verify that none of them are a predecessor of the load.  This is exactly
1658     // the same check that would be done by common code if the CC setter were
1659     // glued to the CC user, so simply invoke that check here.
1660     if (!IsLegalToFold(N, U, CCRegUser, OptLevel, false))
1661       return false;
1662   }
1663
1664   return true;
1665 }
1666
1667 namespace {
1668 // Represents a sequence for extracting a 0/1 value from an IPM result:
1669 // (((X ^ XORValue) + AddValue) >> Bit)
1670 struct IPMConversion {
1671   IPMConversion(unsigned xorValue, int64_t addValue, unsigned bit)
1672     : XORValue(xorValue), AddValue(addValue), Bit(bit) {}
1673
1674   int64_t XORValue;
1675   int64_t AddValue;
1676   unsigned Bit;
1677 };
1678 } // end anonymous namespace
1679
1680 // Return a sequence for getting a 1 from an IPM result when CC has a
1681 // value in CCMask and a 0 when CC has a value in CCValid & ~CCMask.
1682 // The handling of CC values outside CCValid doesn't matter.
1683 static IPMConversion getIPMConversion(unsigned CCValid, unsigned CCMask) {
1684   // Deal with cases where the result can be taken directly from a bit
1685   // of the IPM result.
1686   if (CCMask == (CCValid & (SystemZ::CCMASK_1 | SystemZ::CCMASK_3)))
1687     return IPMConversion(0, 0, SystemZ::IPM_CC);
1688   if (CCMask == (CCValid & (SystemZ::CCMASK_2 | SystemZ::CCMASK_3)))
1689     return IPMConversion(0, 0, SystemZ::IPM_CC + 1);
1690
1691   // Deal with cases where we can add a value to force the sign bit
1692   // to contain the right value.  Putting the bit in 31 means we can
1693   // use SRL rather than RISBG(L), and also makes it easier to get a
1694   // 0/-1 value, so it has priority over the other tests below.
1695   //
1696   // These sequences rely on the fact that the upper two bits of the
1697   // IPM result are zero.
1698   uint64_t TopBit = uint64_t(1) << 31;
1699   if (CCMask == (CCValid & SystemZ::CCMASK_0))
1700     return IPMConversion(0, -(1 << SystemZ::IPM_CC), 31);
1701   if (CCMask == (CCValid & (SystemZ::CCMASK_0 | SystemZ::CCMASK_1)))
1702     return IPMConversion(0, -(2 << SystemZ::IPM_CC), 31);
1703   if (CCMask == (CCValid & (SystemZ::CCMASK_0
1704                             | SystemZ::CCMASK_1
1705                             | SystemZ::CCMASK_2)))
1706     return IPMConversion(0, -(3 << SystemZ::IPM_CC), 31);
1707   if (CCMask == (CCValid & SystemZ::CCMASK_3))
1708     return IPMConversion(0, TopBit - (3 << SystemZ::IPM_CC), 31);
1709   if (CCMask == (CCValid & (SystemZ::CCMASK_1
1710                             | SystemZ::CCMASK_2
1711                             | SystemZ::CCMASK_3)))
1712     return IPMConversion(0, TopBit - (1 << SystemZ::IPM_CC), 31);
1713
1714   // Next try inverting the value and testing a bit.  0/1 could be
1715   // handled this way too, but we dealt with that case above.
1716   if (CCMask == (CCValid & (SystemZ::CCMASK_0 | SystemZ::CCMASK_2)))
1717     return IPMConversion(-1, 0, SystemZ::IPM_CC);
1718
1719   // Handle cases where adding a value forces a non-sign bit to contain
1720   // the right value.
1721   if (CCMask == (CCValid & (SystemZ::CCMASK_1 | SystemZ::CCMASK_2)))
1722     return IPMConversion(0, 1 << SystemZ::IPM_CC, SystemZ::IPM_CC + 1);
1723   if (CCMask == (CCValid & (SystemZ::CCMASK_0 | SystemZ::CCMASK_3)))
1724     return IPMConversion(0, -(1 << SystemZ::IPM_CC), SystemZ::IPM_CC + 1);
1725
1726   // The remaining cases are 1, 2, 0/1/3 and 0/2/3.  All these are
1727   // can be done by inverting the low CC bit and applying one of the
1728   // sign-based extractions above.
1729   if (CCMask == (CCValid & SystemZ::CCMASK_1))
1730     return IPMConversion(1 << SystemZ::IPM_CC, -(1 << SystemZ::IPM_CC), 31);
1731   if (CCMask == (CCValid & SystemZ::CCMASK_2))
1732     return IPMConversion(1 << SystemZ::IPM_CC,
1733                          TopBit - (3 << SystemZ::IPM_CC), 31);
1734   if (CCMask == (CCValid & (SystemZ::CCMASK_0
1735                             | SystemZ::CCMASK_1
1736                             | SystemZ::CCMASK_3)))
1737     return IPMConversion(1 << SystemZ::IPM_CC, -(3 << SystemZ::IPM_CC), 31);
1738   if (CCMask == (CCValid & (SystemZ::CCMASK_0
1739                             | SystemZ::CCMASK_2
1740                             | SystemZ::CCMASK_3)))
1741     return IPMConversion(1 << SystemZ::IPM_CC,
1742                          TopBit - (1 << SystemZ::IPM_CC), 31);
1743
1744   llvm_unreachable("Unexpected CC combination");
1745 }
1746
1747 SDValue SystemZDAGToDAGISel::expandSelectBoolean(SDNode *Node) {
1748   auto *TrueOp = dyn_cast<ConstantSDNode>(Node->getOperand(0));
1749   auto *FalseOp = dyn_cast<ConstantSDNode>(Node->getOperand(1));
1750   if (!TrueOp || !FalseOp)
1751     return SDValue();
1752   if (FalseOp->getZExtValue() != 0)
1753     return SDValue();
1754   if (TrueOp->getSExtValue() != 1 && TrueOp->getSExtValue() != -1)
1755     return SDValue();
1756
1757   auto *CCValidOp = dyn_cast<ConstantSDNode>(Node->getOperand(2));
1758   auto *CCMaskOp = dyn_cast<ConstantSDNode>(Node->getOperand(3));
1759   if (!CCValidOp || !CCMaskOp)
1760     return SDValue();
1761   int CCValid = CCValidOp->getZExtValue();
1762   int CCMask = CCMaskOp->getZExtValue();
1763
1764   SDLoc DL(Node);
1765   SDValue CCReg = Node->getOperand(4);
1766   IPMConversion IPM = getIPMConversion(CCValid, CCMask);
1767   SDValue Result = CurDAG->getNode(SystemZISD::IPM, DL, MVT::i32, CCReg);
1768
1769   if (IPM.XORValue)
1770     Result = CurDAG->getNode(ISD::XOR, DL, MVT::i32, Result,
1771                              CurDAG->getConstant(IPM.XORValue, DL, MVT::i32));
1772
1773   if (IPM.AddValue)
1774     Result = CurDAG->getNode(ISD::ADD, DL, MVT::i32, Result,
1775                              CurDAG->getConstant(IPM.AddValue, DL, MVT::i32));
1776
1777   EVT VT = Node->getValueType(0);
1778   if (VT == MVT::i32 && IPM.Bit == 31) {
1779     unsigned ShiftOp = TrueOp->getSExtValue() == 1 ? ISD::SRL : ISD::SRA;
1780     Result = CurDAG->getNode(ShiftOp, DL, MVT::i32, Result,
1781                              CurDAG->getConstant(IPM.Bit, DL, MVT::i32));
1782   } else {
1783     if (VT != MVT::i32)
1784       Result = CurDAG->getNode(ISD::ANY_EXTEND, DL, VT, Result);
1785
1786     if (TrueOp->getSExtValue() == 1) {
1787       // The SHR/AND sequence should get optimized to an RISBG.
1788       Result = CurDAG->getNode(ISD::SRL, DL, VT, Result,
1789                                CurDAG->getConstant(IPM.Bit, DL, MVT::i32));
1790       Result = CurDAG->getNode(ISD::AND, DL, VT, Result,
1791                                CurDAG->getConstant(1, DL, VT));
1792     } else {
1793       // Sign-extend from IPM.Bit using a pair of shifts.
1794       int ShlAmt = VT.getSizeInBits() - 1 - IPM.Bit;
1795       int SraAmt = VT.getSizeInBits() - 1;
1796       Result = CurDAG->getNode(ISD::SHL, DL, VT, Result,
1797                                CurDAG->getConstant(ShlAmt, DL, MVT::i32));
1798       Result = CurDAG->getNode(ISD::SRA, DL, VT, Result,
1799                                CurDAG->getConstant(SraAmt, DL, MVT::i32));
1800     }
1801   }
1802
1803   return Result;
1804 }
1805
1806 void SystemZDAGToDAGISel::PreprocessISelDAG() {
1807   // If we have conditional immediate loads, we always prefer
1808   // using those over an IPM sequence.
1809   if (Subtarget->hasLoadStoreOnCond2())
1810     return;
1811
1812   bool MadeChange = false;
1813
1814   for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
1815                                        E = CurDAG->allnodes_end();
1816        I != E;) {
1817     SDNode *N = &*I++;
1818     if (N->use_empty())
1819       continue;
1820
1821     SDValue Res;
1822     switch (N->getOpcode()) {
1823     default: break;
1824     case SystemZISD::SELECT_CCMASK:
1825       Res = expandSelectBoolean(N);
1826       break;
1827     }
1828
1829     if (Res) {
1830       LLVM_DEBUG(dbgs() << "SystemZ DAG preprocessing replacing:\nOld:    ");
1831       LLVM_DEBUG(N->dump(CurDAG));
1832       LLVM_DEBUG(dbgs() << "\nNew: ");
1833       LLVM_DEBUG(Res.getNode()->dump(CurDAG));
1834       LLVM_DEBUG(dbgs() << "\n");
1835
1836       CurDAG->ReplaceAllUsesOfValueWith(SDValue(N, 0), Res);
1837       MadeChange = true;
1838     }
1839   }
1840
1841   if (MadeChange)
1842     CurDAG->RemoveDeadNodes();
1843 }