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