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