lib/Target/SystemZ/SystemZSelectionDAGInfo.cpp

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