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