1//===-- SystemZSelectionDAGInfo.cpp - SystemZ SelectionDAG Info -----------===//
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 implements the SystemZSelectionDAGInfo class.
11//
12//===----------------------------------------------------------------------===//
13
14#include "SystemZTargetMachine.h"
15#include "llvm/CodeGen/SelectionDAG.h"
16
17using namespace llvm;
18
19#define DEBUG_TYPE "systemz-selectiondag-info"
20
21SystemZSelectionDAGInfo::SystemZSelectionDAGInfo(const DataLayout &DL)
22    : TargetSelectionDAGInfo(&DL) {}
23
24SystemZSelectionDAGInfo::~SystemZSelectionDAGInfo() {
25}
26
27// Decide whether it is best to use a loop or straight-line code for
28// a block operation of Size bytes with source address Src and destination
29// address Dest.  Sequence is the opcode to use for straight-line code
30// (such as MVC) and Loop is the opcode to use for loops (such as MVC_LOOP).
31// Return the chain for the completed operation.
32static SDValue emitMemMem(SelectionDAG &DAG, SDLoc DL, unsigned Sequence,
33                          unsigned Loop, SDValue Chain, SDValue Dst,
34                          SDValue Src, uint64_t Size) {
35  EVT PtrVT = Src.getValueType();
36  // The heuristic we use is to prefer loops for anything that would
37  // require 7 or more MVCs.  With these kinds of sizes there isn't
38  // much to choose between straight-line code and looping code,
39  // since the time will be dominated by the MVCs themselves.
40  // However, the loop has 4 or 5 instructions (depending on whether
41  // the base addresses can be proved equal), so there doesn't seem
42  // much point using a loop for 5 * 256 bytes or fewer.  Anything in
43  // the range (5 * 256, 6 * 256) will need another instruction after
44  // the loop, so it doesn't seem worth using a loop then either.
45  // The next value up, 6 * 256, can be implemented in the same
46  // number of straight-line MVCs as 6 * 256 - 1.
47  if (Size > 6 * 256)
48    return DAG.getNode(Loop, DL, MVT::Other, Chain, Dst, Src,
49                       DAG.getConstant(Size, PtrVT),
50                       DAG.getConstant(Size / 256, PtrVT));
51  return DAG.getNode(Sequence, DL, MVT::Other, Chain, Dst, Src,
52                     DAG.getConstant(Size, PtrVT));
53}
54
55SDValue SystemZSelectionDAGInfo::
56EmitTargetCodeForMemcpy(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
57                        SDValue Dst, SDValue Src, SDValue Size, unsigned Align,
58                        bool IsVolatile, bool AlwaysInline,
59                        MachinePointerInfo DstPtrInfo,
60                        MachinePointerInfo SrcPtrInfo) const {
61  if (IsVolatile)
62    return SDValue();
63
64  if (auto *CSize = dyn_cast<ConstantSDNode>(Size))
65    return emitMemMem(DAG, DL, SystemZISD::MVC, SystemZISD::MVC_LOOP,
66                      Chain, Dst, Src, CSize->getZExtValue());
67  return SDValue();
68}
69
70// Handle a memset of 1, 2, 4 or 8 bytes with the operands given by
71// Chain, Dst, ByteVal and Size.  These cases are expected to use
72// MVI, MVHHI, MVHI and MVGHI respectively.
73static SDValue memsetStore(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
74                           SDValue Dst, uint64_t ByteVal, uint64_t Size,
75                           unsigned Align,
76                           MachinePointerInfo DstPtrInfo) {
77  uint64_t StoreVal = ByteVal;
78  for (unsigned I = 1; I < Size; ++I)
79    StoreVal |= ByteVal << (I * 8);
80  return DAG.getStore(Chain, DL,
81                      DAG.getConstant(StoreVal, MVT::getIntegerVT(Size * 8)),
82                      Dst, DstPtrInfo, false, false, Align);
83}
84
85SDValue SystemZSelectionDAGInfo::
86EmitTargetCodeForMemset(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
87                        SDValue Dst, SDValue Byte, SDValue Size,
88                        unsigned Align, bool IsVolatile,
89                        MachinePointerInfo DstPtrInfo) const {
90  EVT PtrVT = Dst.getValueType();
91
92  if (IsVolatile)
93    return SDValue();
94
95  if (auto *CSize = dyn_cast<ConstantSDNode>(Size)) {
96    uint64_t Bytes = CSize->getZExtValue();
97    if (Bytes == 0)
98      return SDValue();
99    if (auto *CByte = dyn_cast<ConstantSDNode>(Byte)) {
100      // Handle cases that can be done using at most two of
101      // MVI, MVHI, MVHHI and MVGHI.  The latter two can only be
102      // used if ByteVal is all zeros or all ones; in other casees,
103      // we can move at most 2 halfwords.
104      uint64_t ByteVal = CByte->getZExtValue();
105      if (ByteVal == 0 || ByteVal == 255 ?
106          Bytes <= 16 && CountPopulation_64(Bytes) <= 2 :
107          Bytes <= 4) {
108        unsigned Size1 = Bytes == 16 ? 8 : 1 << findLastSet(Bytes);
109        unsigned Size2 = Bytes - Size1;
110        SDValue Chain1 = memsetStore(DAG, DL, Chain, Dst, ByteVal, Size1,
111                                     Align, DstPtrInfo);
112        if (Size2 == 0)
113          return Chain1;
114        Dst = DAG.getNode(ISD::ADD, DL, PtrVT, Dst,
115                          DAG.getConstant(Size1, PtrVT));
116        DstPtrInfo = DstPtrInfo.getWithOffset(Size1);
117        SDValue Chain2 = memsetStore(DAG, DL, Chain, Dst, ByteVal, Size2,
118                                     std::min(Align, Size1), DstPtrInfo);
119        return DAG.getNode(ISD::TokenFactor, DL, MVT::Other, Chain1, Chain2);
120      }
121    } else {
122      // Handle one and two bytes using STC.
123      if (Bytes <= 2) {
124        SDValue Chain1 = DAG.getStore(Chain, DL, Byte, Dst, DstPtrInfo,
125                                      false, false, Align);
126        if (Bytes == 1)
127          return Chain1;
128        SDValue Dst2 = DAG.getNode(ISD::ADD, DL, PtrVT, Dst,
129                                   DAG.getConstant(1, PtrVT));
130        SDValue Chain2 = DAG.getStore(Chain, DL, Byte, Dst2,
131                                      DstPtrInfo.getWithOffset(1),
132                                      false, false, 1);
133        return DAG.getNode(ISD::TokenFactor, DL, MVT::Other, Chain1, Chain2);
134      }
135    }
136    assert(Bytes >= 2 && "Should have dealt with 0- and 1-byte cases already");
137
138    // Handle the special case of a memset of 0, which can use XC.
139    auto *CByte = dyn_cast<ConstantSDNode>(Byte);
140    if (CByte && CByte->getZExtValue() == 0)
141      return emitMemMem(DAG, DL, SystemZISD::XC, SystemZISD::XC_LOOP,
142                        Chain, Dst, Dst, Bytes);
143
144    // Copy the byte to the first location and then use MVC to copy
145    // it to the rest.
146    Chain = DAG.getStore(Chain, DL, Byte, Dst, DstPtrInfo,
147                         false, false, Align);
148    SDValue DstPlus1 = DAG.getNode(ISD::ADD, DL, PtrVT, Dst,
149                                   DAG.getConstant(1, PtrVT));
150    return emitMemMem(DAG, DL, SystemZISD::MVC, SystemZISD::MVC_LOOP,
151                      Chain, DstPlus1, Dst, Bytes - 1);
152  }
153  return SDValue();
154}
155
156// Use CLC to compare [Src1, Src1 + Size) with [Src2, Src2 + Size),
157// deciding whether to use a loop or straight-line code.
158static SDValue emitCLC(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
159                       SDValue Src1, SDValue Src2, uint64_t Size) {
160  SDVTList VTs = DAG.getVTList(MVT::Other, MVT::Glue);
161  EVT PtrVT = Src1.getValueType();
162  // A two-CLC sequence is a clear win over a loop, not least because it
163  // needs only one branch.  A three-CLC sequence needs the same number
164  // of branches as a loop (i.e. 2), but is shorter.  That brings us to
165  // lengths greater than 768 bytes.  It seems relatively likely that
166  // a difference will be found within the first 768 bytes, so we just
167  // optimize for the smallest number of branch instructions, in order
168  // to avoid polluting the prediction buffer too much.  A loop only ever
169  // needs 2 branches, whereas a straight-line sequence would need 3 or more.
170  if (Size > 3 * 256)
171    return DAG.getNode(SystemZISD::CLC_LOOP, DL, VTs, Chain, Src1, Src2,
172                       DAG.getConstant(Size, PtrVT),
173                       DAG.getConstant(Size / 256, PtrVT));
174  return DAG.getNode(SystemZISD::CLC, DL, VTs, Chain, Src1, Src2,
175                     DAG.getConstant(Size, PtrVT));
176}
177
178// Convert the current CC value into an integer that is 0 if CC == 0,
179// less than zero if CC == 1 and greater than zero if CC >= 2.
180// The sequence starts with IPM, which puts CC into bits 29 and 28
181// of an integer and clears bits 30 and 31.
182static SDValue addIPMSequence(SDLoc DL, SDValue Glue, SelectionDAG &DAG) {
183  SDValue IPM = DAG.getNode(SystemZISD::IPM, DL, MVT::i32, Glue);
184  SDValue SRL = DAG.getNode(ISD::SRL, DL, MVT::i32, IPM,
185                            DAG.getConstant(SystemZ::IPM_CC, MVT::i32));
186  SDValue ROTL = DAG.getNode(ISD::ROTL, DL, MVT::i32, SRL,
187                             DAG.getConstant(31, MVT::i32));
188  return ROTL;
189}
190
191std::pair<SDValue, SDValue> SystemZSelectionDAGInfo::
192EmitTargetCodeForMemcmp(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
193                        SDValue Src1, SDValue Src2, SDValue Size,
194                        MachinePointerInfo Op1PtrInfo,
195                        MachinePointerInfo Op2PtrInfo) const {
196  if (auto *CSize = dyn_cast<ConstantSDNode>(Size)) {
197    uint64_t Bytes = CSize->getZExtValue();
198    assert(Bytes > 0 && "Caller should have handled 0-size case");
199    Chain = emitCLC(DAG, DL, Chain, Src1, Src2, Bytes);
200    SDValue Glue = Chain.getValue(1);
201    return std::make_pair(addIPMSequence(DL, Glue, DAG), Chain);
202  }
203  return std::make_pair(SDValue(), SDValue());
204}
205
206std::pair<SDValue, SDValue> SystemZSelectionDAGInfo::
207EmitTargetCodeForMemchr(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
208                        SDValue Src, SDValue Char, SDValue Length,
209                        MachinePointerInfo SrcPtrInfo) const {
210  // Use SRST to find the character.  End is its address on success.
211  EVT PtrVT = Src.getValueType();
212  SDVTList VTs = DAG.getVTList(PtrVT, MVT::Other, MVT::Glue);
213  Length = DAG.getZExtOrTrunc(Length, DL, PtrVT);
214  Char = DAG.getZExtOrTrunc(Char, DL, MVT::i32);
215  Char = DAG.getNode(ISD::AND, DL, MVT::i32, Char,
216                     DAG.getConstant(255, MVT::i32));
217  SDValue Limit = DAG.getNode(ISD::ADD, DL, PtrVT, Src, Length);
218  SDValue End = DAG.getNode(SystemZISD::SEARCH_STRING, DL, VTs, Chain,
219                            Limit, Src, Char);
220  Chain = End.getValue(1);
221  SDValue Glue = End.getValue(2);
222
223  // Now select between End and null, depending on whether the character
224  // was found.
225  SmallVector<SDValue, 5> Ops;
226  Ops.push_back(End);
227  Ops.push_back(DAG.getConstant(0, PtrVT));
228  Ops.push_back(DAG.getConstant(SystemZ::CCMASK_SRST, MVT::i32));
229  Ops.push_back(DAG.getConstant(SystemZ::CCMASK_SRST_FOUND, MVT::i32));
230  Ops.push_back(Glue);
231  VTs = DAG.getVTList(PtrVT, MVT::Glue);
232  End = DAG.getNode(SystemZISD::SELECT_CCMASK, DL, VTs, Ops);
233  return std::make_pair(End, Chain);
234}
235
236std::pair<SDValue, SDValue> SystemZSelectionDAGInfo::
237EmitTargetCodeForStrcpy(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
238                        SDValue Dest, SDValue Src,
239                        MachinePointerInfo DestPtrInfo,
240                        MachinePointerInfo SrcPtrInfo, bool isStpcpy) const {
241  SDVTList VTs = DAG.getVTList(Dest.getValueType(), MVT::Other);
242  SDValue EndDest = DAG.getNode(SystemZISD::STPCPY, DL, VTs, Chain, Dest, Src,
243                                DAG.getConstant(0, MVT::i32));
244  return std::make_pair(isStpcpy ? EndDest : Dest, EndDest.getValue(1));
245}
246
247std::pair<SDValue, SDValue> SystemZSelectionDAGInfo::
248EmitTargetCodeForStrcmp(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
249                        SDValue Src1, SDValue Src2,
250                        MachinePointerInfo Op1PtrInfo,
251                        MachinePointerInfo Op2PtrInfo) const {
252  SDVTList VTs = DAG.getVTList(Src1.getValueType(), MVT::Other, MVT::Glue);
253  SDValue Unused = DAG.getNode(SystemZISD::STRCMP, DL, VTs, Chain, Src1, Src2,
254                               DAG.getConstant(0, MVT::i32));
255  Chain = Unused.getValue(1);
256  SDValue Glue = Chain.getValue(2);
257  return std::make_pair(addIPMSequence(DL, Glue, DAG), Chain);
258}
259
260// Search from Src for a null character, stopping once Src reaches Limit.
261// Return a pair of values, the first being the number of nonnull characters
262// and the second being the out chain.
263//
264// This can be used for strlen by setting Limit to 0.
265static std::pair<SDValue, SDValue> getBoundedStrlen(SelectionDAG &DAG, SDLoc DL,
266                                                    SDValue Chain, SDValue Src,
267                                                    SDValue Limit) {
268  EVT PtrVT = Src.getValueType();
269  SDVTList VTs = DAG.getVTList(PtrVT, MVT::Other, MVT::Glue);
270  SDValue End = DAG.getNode(SystemZISD::SEARCH_STRING, DL, VTs, Chain,
271                            Limit, Src, DAG.getConstant(0, MVT::i32));
272  Chain = End.getValue(1);
273  SDValue Len = DAG.getNode(ISD::SUB, DL, PtrVT, End, Src);
274  return std::make_pair(Len, Chain);
275}
276
277std::pair<SDValue, SDValue> SystemZSelectionDAGInfo::
278EmitTargetCodeForStrlen(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
279                        SDValue Src, MachinePointerInfo SrcPtrInfo) const {
280  EVT PtrVT = Src.getValueType();
281  return getBoundedStrlen(DAG, DL, Chain, Src, DAG.getConstant(0, PtrVT));
282}
283
284std::pair<SDValue, SDValue> SystemZSelectionDAGInfo::
285EmitTargetCodeForStrnlen(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
286                         SDValue Src, SDValue MaxLength,
287                         MachinePointerInfo SrcPtrInfo) const {
288  EVT PtrVT = Src.getValueType();
289  MaxLength = DAG.getZExtOrTrunc(MaxLength, DL, PtrVT);
290  SDValue Limit = DAG.getNode(ISD::ADD, DL, PtrVT, Src, MaxLength);
291  return getBoundedStrlen(DAG, DL, Chain, Src, Limit);
292}
293