LLVM  8.0.0svn
SystemZSelectionDAGInfo.cpp
Go to the documentation of this file.
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"
16 
17 using namespace llvm;
18 
19 #define DEBUG_TYPE "systemz-selectiondag-info"
20 
21 // Decide whether it is best to use a loop or straight-line code for
22 // a block operation of Size bytes with source address Src and destination
23 // address Dest. Sequence is the opcode to use for straight-line code
24 // (such as MVC) and Loop is the opcode to use for loops (such as MVC_LOOP).
25 // Return the chain for the completed operation.
26 static SDValue emitMemMem(SelectionDAG &DAG, const SDLoc &DL, unsigned Sequence,
27  unsigned Loop, SDValue Chain, SDValue Dst,
28  SDValue Src, uint64_t Size) {
29  EVT PtrVT = Src.getValueType();
30  // The heuristic we use is to prefer loops for anything that would
31  // require 7 or more MVCs. With these kinds of sizes there isn't
32  // much to choose between straight-line code and looping code,
33  // since the time will be dominated by the MVCs themselves.
34  // However, the loop has 4 or 5 instructions (depending on whether
35  // the base addresses can be proved equal), so there doesn't seem
36  // much point using a loop for 5 * 256 bytes or fewer. Anything in
37  // the range (5 * 256, 6 * 256) will need another instruction after
38  // the loop, so it doesn't seem worth using a loop then either.
39  // The next value up, 6 * 256, can be implemented in the same
40  // number of straight-line MVCs as 6 * 256 - 1.
41  if (Size > 6 * 256)
42  return DAG.getNode(Loop, DL, MVT::Other, Chain, Dst, Src,
43  DAG.getConstant(Size, DL, PtrVT),
44  DAG.getConstant(Size / 256, DL, PtrVT));
45  return DAG.getNode(Sequence, DL, MVT::Other, Chain, Dst, Src,
46  DAG.getConstant(Size, DL, PtrVT));
47 }
48 
50  SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Dst, SDValue Src,
51  SDValue Size, unsigned Align, bool IsVolatile, bool AlwaysInline,
52  MachinePointerInfo DstPtrInfo, MachinePointerInfo SrcPtrInfo) const {
53  if (IsVolatile)
54  return SDValue();
55 
56  if (auto *CSize = dyn_cast<ConstantSDNode>(Size))
58  Chain, Dst, Src, CSize->getZExtValue());
59  return SDValue();
60 }
61 
62 // Handle a memset of 1, 2, 4 or 8 bytes with the operands given by
63 // Chain, Dst, ByteVal and Size. These cases are expected to use
64 // MVI, MVHHI, MVHI and MVGHI respectively.
65 static SDValue memsetStore(SelectionDAG &DAG, const SDLoc &DL, SDValue Chain,
66  SDValue Dst, uint64_t ByteVal, uint64_t Size,
67  unsigned Align, MachinePointerInfo DstPtrInfo) {
68  uint64_t StoreVal = ByteVal;
69  for (unsigned I = 1; I < Size; ++I)
70  StoreVal |= ByteVal << (I * 8);
71  return DAG.getStore(
72  Chain, DL, DAG.getConstant(StoreVal, DL, MVT::getIntegerVT(Size * 8)),
73  Dst, DstPtrInfo, Align);
74 }
75 
77  SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Dst,
78  SDValue Byte, SDValue Size, unsigned Align, bool IsVolatile,
79  MachinePointerInfo DstPtrInfo) const {
80  EVT PtrVT = Dst.getValueType();
81 
82  if (IsVolatile)
83  return SDValue();
84 
85  if (auto *CSize = dyn_cast<ConstantSDNode>(Size)) {
86  uint64_t Bytes = CSize->getZExtValue();
87  if (Bytes == 0)
88  return SDValue();
89  if (auto *CByte = dyn_cast<ConstantSDNode>(Byte)) {
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  Align, 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(DAG, DL, Chain, Dst, ByteVal, Size2,
108  std::min(Align, Size1), DstPtrInfo);
109  return DAG.getNode(ISD::TokenFactor, DL, MVT::Other, Chain1, Chain2);
110  }
111  } else {
112  // Handle one and two bytes using STC.
113  if (Bytes <= 2) {
114  SDValue Chain1 = DAG.getStore(Chain, DL, Byte, Dst, DstPtrInfo, Align);
115  if (Bytes == 1)
116  return Chain1;
117  SDValue Dst2 = DAG.getNode(ISD::ADD, DL, PtrVT, Dst,
118  DAG.getConstant(1, DL, PtrVT));
119  SDValue Chain2 =
120  DAG.getStore(Chain, DL, Byte, Dst2, DstPtrInfo.getWithOffset(1),
121  /* Alignment = */ 1);
122  return DAG.getNode(ISD::TokenFactor, DL, MVT::Other, Chain1, Chain2);
123  }
124  }
125  assert(Bytes >= 2 && "Should have dealt with 0- and 1-byte cases already");
126 
127  // Handle the special case of a memset of 0, which can use XC.
128  auto *CByte = dyn_cast<ConstantSDNode>(Byte);
129  if (CByte && CByte->getZExtValue() == 0)
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, Align);
136  SDValue DstPlus1 = DAG.getNode(ISD::ADD, DL, PtrVT, Dst,
137  DAG.getConstant(1, DL, PtrVT));
139  Chain, DstPlus1, Dst, Bytes - 1);
140  }
141  return SDValue();
142 }
143 
144 // Use CLC to compare [Src1, Src1 + Size) with [Src2, Src2 + Size),
145 // deciding whether to use a loop or straight-line code.
146 static SDValue emitCLC(SelectionDAG &DAG, const SDLoc &DL, SDValue Chain,
147  SDValue Src1, SDValue Src2, uint64_t Size) {
149  EVT PtrVT = Src1.getValueType();
150  // A two-CLC sequence is a clear win over a loop, not least because it
151  // needs only one branch. A three-CLC sequence needs the same number
152  // of branches as a loop (i.e. 2), but is shorter. That brings us to
153  // lengths greater than 768 bytes. It seems relatively likely that
154  // a difference will be found within the first 768 bytes, so we just
155  // optimize for the smallest number of branch instructions, in order
156  // to avoid polluting the prediction buffer too much. A loop only ever
157  // needs 2 branches, whereas a straight-line sequence would need 3 or more.
158  if (Size > 3 * 256)
159  return DAG.getNode(SystemZISD::CLC_LOOP, DL, VTs, Chain, Src1, Src2,
160  DAG.getConstant(Size, DL, PtrVT),
161  DAG.getConstant(Size / 256, DL, PtrVT));
162  return DAG.getNode(SystemZISD::CLC, DL, VTs, Chain, Src1, Src2,
163  DAG.getConstant(Size, DL, PtrVT));
164 }
165 
166 // Convert the current CC value into an integer that is 0 if CC == 0,
167 // less than zero if CC == 1 and greater than zero if CC >= 2.
168 // The sequence starts with IPM, which puts CC into bits 29 and 28
169 // of an integer and clears bits 30 and 31.
170 static SDValue addIPMSequence(const SDLoc &DL, SDValue CCReg,
171  SelectionDAG &DAG) {
172  SDValue IPM = DAG.getNode(SystemZISD::IPM, DL, MVT::i32, CCReg);
173  SDValue SRL = DAG.getNode(ISD::SRL, DL, MVT::i32, IPM,
175  SDValue ROTL = DAG.getNode(ISD::ROTL, DL, MVT::i32, SRL,
176  DAG.getConstant(31, DL, MVT::i32));
177  return ROTL;
178 }
179 
181  SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Src1,
182  SDValue Src2, SDValue Size, MachinePointerInfo Op1PtrInfo,
183  MachinePointerInfo Op2PtrInfo) const {
184  if (auto *CSize = dyn_cast<ConstantSDNode>(Size)) {
185  uint64_t Bytes = CSize->getZExtValue();
186  assert(Bytes > 0 && "Caller should have handled 0-size case");
187  SDValue CCReg = emitCLC(DAG, DL, Chain, Src1, Src2, Bytes);
188  Chain = CCReg.getValue(1);
189  return std::make_pair(addIPMSequence(DL, CCReg, DAG), Chain);
190  }
191  return std::make_pair(SDValue(), SDValue());
192 }
193 
195  SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Src,
196  SDValue Char, SDValue Length, MachinePointerInfo SrcPtrInfo) const {
197  // Use SRST to find the character. End is its address on success.
198  EVT PtrVT = Src.getValueType();
199  SDVTList VTs = DAG.getVTList(PtrVT, MVT::i32, MVT::Other);
200  Length = DAG.getZExtOrTrunc(Length, DL, PtrVT);
201  Char = DAG.getZExtOrTrunc(Char, DL, MVT::i32);
202  Char = DAG.getNode(ISD::AND, DL, MVT::i32, Char,
203  DAG.getConstant(255, DL, MVT::i32));
204  SDValue Limit = DAG.getNode(ISD::ADD, DL, PtrVT, Src, Length);
205  SDValue End = DAG.getNode(SystemZISD::SEARCH_STRING, DL, VTs, Chain,
206  Limit, Src, Char);
207  SDValue CCReg = End.getValue(1);
208  Chain = End.getValue(2);
209 
210  // Now select between End and null, depending on whether the character
211  // was found.
212  SDValue Ops[] = {End, DAG.getConstant(0, DL, PtrVT),
215  CCReg};
216  End = DAG.getNode(SystemZISD::SELECT_CCMASK, DL, PtrVT, Ops);
217  return std::make_pair(End, Chain);
218 }
219 
221  SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Dest,
222  SDValue Src, MachinePointerInfo DestPtrInfo, MachinePointerInfo SrcPtrInfo,
223  bool isStpcpy) const {
224  SDVTList VTs = DAG.getVTList(Dest.getValueType(), MVT::Other);
225  SDValue EndDest = DAG.getNode(SystemZISD::STPCPY, DL, VTs, Chain, Dest, Src,
226  DAG.getConstant(0, DL, MVT::i32));
227  return std::make_pair(isStpcpy ? EndDest : Dest, EndDest.getValue(1));
228 }
229 
231  SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Src1,
232  SDValue Src2, MachinePointerInfo Op1PtrInfo,
233  MachinePointerInfo Op2PtrInfo) const {
234  SDVTList VTs = DAG.getVTList(Src1.getValueType(), MVT::i32, MVT::Other);
235  SDValue Unused = DAG.getNode(SystemZISD::STRCMP, DL, VTs, Chain, Src1, Src2,
236  DAG.getConstant(0, DL, MVT::i32));
237  SDValue CCReg = Unused.getValue(1);
238  Chain = Unused.getValue(2);
239  return std::make_pair(addIPMSequence(DL, CCReg, DAG), Chain);
240 }
241 
242 // Search from Src for a null character, stopping once Src reaches Limit.
243 // Return a pair of values, the first being the number of nonnull characters
244 // and the second being the out chain.
245 //
246 // This can be used for strlen by setting Limit to 0.
247 static std::pair<SDValue, SDValue> getBoundedStrlen(SelectionDAG &DAG,
248  const SDLoc &DL,
249  SDValue Chain, SDValue Src,
250  SDValue Limit) {
251  EVT PtrVT = Src.getValueType();
252  SDVTList VTs = DAG.getVTList(PtrVT, MVT::i32, MVT::Other);
253  SDValue End = DAG.getNode(SystemZISD::SEARCH_STRING, DL, VTs, Chain,
254  Limit, Src, DAG.getConstant(0, DL, MVT::i32));
255  Chain = End.getValue(2);
256  SDValue Len = DAG.getNode(ISD::SUB, DL, PtrVT, End, Src);
257  return std::make_pair(Len, Chain);
258 }
259 
261  SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Src,
262  MachinePointerInfo SrcPtrInfo) const {
263  EVT PtrVT = Src.getValueType();
264  return getBoundedStrlen(DAG, DL, Chain, Src, DAG.getConstant(0, DL, PtrVT));
265 }
266 
268  SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Src,
269  SDValue MaxLength, MachinePointerInfo SrcPtrInfo) const {
270  EVT PtrVT = Src.getValueType();
271  MaxLength = DAG.getZExtOrTrunc(MaxLength, DL, PtrVT);
272  SDValue Limit = DAG.getNode(ISD::ADD, DL, PtrVT, Src, MaxLength);
273  return getBoundedStrlen(DAG, DL, Chain, Src, Limit);
274 }
SDValue getStore(SDValue Chain, const SDLoc &dl, SDValue Val, SDValue Ptr, MachinePointerInfo PtrInfo, unsigned Alignment=0, MachineMemOperand::Flags MMOFlags=MachineMemOperand::MONone, const AAMDNodes &AAInfo=AAMDNodes())
Helper function to build ISD::STORE nodes.
static MVT getIntegerVT(unsigned BitWidth)
static std::pair< SDValue, SDValue > getBoundedStrlen(SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Src, SDValue Limit)
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
EVT getValueType() const
Return the ValueType of the referenced return value.
T findLastSet(T Val, ZeroBehavior ZB=ZB_Max)
Get the index of the last set bit starting from the least significant bit.
Definition: MathExtras.h:244
This class represents lattice values for constants.
Definition: AllocatorList.h:24
constexpr char IsVolatile[]
Key for Kernel::Arg::Metadata::mIsVolatile.
static SDValue memsetStore(SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Dst, uint64_t ByteVal, uint64_t Size, unsigned Align, MachinePointerInfo DstPtrInfo)
static SDValue addIPMSequence(const SDLoc &DL, SDValue CCReg, SelectionDAG &DAG)
SDValue getNode(unsigned Opcode, const SDLoc &DL, EVT VT, ArrayRef< SDUse > Ops)
Gets or creates the specified node.
std::pair< SDValue, SDValue > EmitTargetCodeForMemchr(SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Src, SDValue Char, SDValue Length, MachinePointerInfo SrcPtrInfo) const override
Emit target-specific code that performs a memchr, in cases where that is faster than a libcall...
SDVTList getVTList(EVT VT)
Return an SDVTList that represents the list of values specified.
This represents a list of ValueType&#39;s that has been intern&#39;d by a SelectionDAG.
SDValue EmitTargetCodeForMemset(SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Dst, SDValue Byte, SDValue Size, unsigned Align, bool IsVolatile, MachinePointerInfo DstPtrInfo) const override
Emit target-specific code that performs a memset.
Simple integer binary arithmetic operators.
Definition: ISDOpcodes.h:201
static SDValue emitCLC(SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Src1, SDValue Src2, uint64_t Size)
std::pair< SDValue, SDValue > EmitTargetCodeForMemcmp(SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Src1, SDValue Src2, SDValue Size, MachinePointerInfo Op1PtrInfo, MachinePointerInfo Op2PtrInfo) const override
Emit target-specific code that performs a memcmp, in cases where that is faster than a libcall...
SDValue EmitTargetCodeForMemcpy(SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Dst, SDValue Src, SDValue Size, unsigned Align, bool IsVolatile, bool AlwaysInline, MachinePointerInfo DstPtrInfo, MachinePointerInfo SrcPtrInfo) const override
Emit target-specific code that performs a memcpy.
Extended Value Type.
Definition: ValueTypes.h:34
This class contains a discriminated union of information about pointers in memory operands...
const unsigned CCMASK_SRST_FOUND
Definition: SystemZ.h:72
TokenFactor - This node takes multiple tokens as input and produces a single token result...
Definition: ISDOpcodes.h:50
unsigned countPopulation(T Value)
Count the number of set bits in a value.
Definition: MathExtras.h:520
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Definition: SelectionDAG.h:222
SDValue getZExtOrTrunc(SDValue Op, const SDLoc &DL, EVT VT)
Convert Op, which must be of integer type, to the integer type VT, by either zero-extending or trunca...
std::pair< SDValue, SDValue > EmitTargetCodeForStrcmp(SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Src1, SDValue Src2, MachinePointerInfo Op1PtrInfo, MachinePointerInfo Op2PtrInfo) const override
Emit target-specific code that performs a strcmp, in cases where that is faster than a libcall...
Wrapper class for IR location info (IR ordering and DebugLoc) to be passed into SDNode creation funct...
MachinePointerInfo getWithOffset(int64_t O) const
const unsigned CCMASK_SRST
Definition: SystemZ.h:74
Bitwise operators - logical and, logical or, logical xor.
Definition: ISDOpcodes.h:387
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:465
#define I(x, y, z)
Definition: MD5.cpp:58
Sequence
A sequence of states that a pointer may go through in which an objc_retain and objc_release are actua...
Definition: PtrState.h:41
static SDValue emitMemMem(SelectionDAG &DAG, const SDLoc &DL, unsigned Sequence, unsigned Loop, SDValue Chain, SDValue Dst, SDValue Src, uint64_t Size)
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
uint32_t Size
Definition: Profile.cpp:47
std::pair< SDValue, SDValue > EmitTargetCodeForStrnlen(SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Src, SDValue MaxLength, MachinePointerInfo SrcPtrInfo) const override
SDValue getValue(unsigned R) const
SDValue getConstant(uint64_t Val, const SDLoc &DL, EVT VT, bool isTarget=false, bool isOpaque=false)
Create a ConstantSDNode wrapping a constant value.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::pair< SDValue, SDValue > EmitTargetCodeForStrcpy(SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Dest, SDValue Src, MachinePointerInfo DestPtrInfo, MachinePointerInfo SrcPtrInfo, bool isStpcpy) const override
Emit target-specific code that performs a strcpy or stpcpy, in cases where that is faster than a libc...
std::pair< SDValue, SDValue > EmitTargetCodeForStrlen(SelectionDAG &DAG, const SDLoc &DL, SDValue Chain, SDValue Src, MachinePointerInfo SrcPtrInfo) const override
const unsigned IPM_CC
Definition: SystemZ.h:112
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation...