contrib/llvm-project/llvm/lib/Target/SystemZ/SystemZISelDAGToDAG.cpp

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