[SystemZ] Use SRST to implement strlen and strnlen

It would also make sense to use it for memchr; I'm working on that now.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@188547 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/include/llvm/Target/TargetLibraryInfo.h b/include/llvm/Target/TargetLibraryInfo.h
index 7a06415f4b68a3f83b2079e67bebbb32b3674657..50b16a355dcc577fa6c0a1a6083e5038e4363cc6 100644 (file)
--- a/include/llvm/Target/TargetLibraryInfo.h
+++ b/include/llvm/Target/TargetLibraryInfo.h
@@ -700,7 +700,7 @@ public:
     case LibFunc::log2:      case LibFunc::log2f:      case LibFunc::log2l:
     case LibFunc::exp2:      case LibFunc::exp2f:      case LibFunc::exp2l:
     case LibFunc::memcmp:    case LibFunc::strcmp:     case LibFunc::strcpy:
-    case LibFunc::stpcpy:
+    case LibFunc::stpcpy:    case LibFunc::strlen:     case LibFunc::strnlen:
       return true;
     }
     return false;

diff --git a/include/llvm/Target/TargetSelectionDAGInfo.h b/include/llvm/Target/TargetSelectionDAGInfo.h
index 5e65c304a1dfd5824bc0447589d3f2ea9e79d751..138ff481961274809053f796f72cb47093e5ec2f 100644 (file)
--- a/include/llvm/Target/TargetSelectionDAGInfo.h
+++ b/include/llvm/Target/TargetSelectionDAGInfo.h
@@ -137,6 +137,19 @@ public:
                           MachinePointerInfo Op2PtrInfo) const {
     return std::make_pair(SDValue(), SDValue());
   }
+
+  virtual std::pair<SDValue, SDValue>
+  EmitTargetCodeForStrlen(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
+                          SDValue Src, MachinePointerInfo SrcPtrInfo) const {
+    return std::make_pair(SDValue(), SDValue());
+  }
+
+  virtual std::pair<SDValue, SDValue>
+  EmitTargetCodeForStrnlen(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
+                           SDValue Src, SDValue MaxLength,
+                           MachinePointerInfo SrcPtrInfo) const {
+    return std::make_pair(SDValue(), SDValue());
+  }
 };
 
 } // end llvm namespace

diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
index 9bb78978e11149add37ba70fda574d6a5eb90e42..3b9f3581a4cdaf6cc8e22b95c14c8e615021ba88 100644 (file)
--- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp
@@ -5616,6 +5616,59 @@ bool SelectionDAGBuilder::visitStrCmpCall(const CallInst &I) {
   return false;
 }
 
+/// visitStrLenCall -- See if we can lower a strlen call into an optimized
+/// form.  If so, return true and lower it, otherwise return false and it
+/// will be lowered like a normal call.
+bool SelectionDAGBuilder::visitStrLenCall(const CallInst &I) {
+  // Verify that the prototype makes sense.  size_t strlen(char *)
+  if (I.getNumArgOperands() != 1)
+    return false;
+
+  const Value *Arg0 = I.getArgOperand(0);
+  if (!Arg0->getType()->isPointerTy() || !I.getType()->isIntegerTy())
+    return false;
+
+  const TargetSelectionDAGInfo &TSI = DAG.getSelectionDAGInfo();
+  std::pair<SDValue, SDValue> Res =
+    TSI.EmitTargetCodeForStrlen(DAG, getCurSDLoc(), DAG.getRoot(),
+                                getValue(Arg0), MachinePointerInfo(Arg0));
+  if (Res.first.getNode()) {
+    processIntegerCallValue(I, Res.first, false);
+    PendingLoads.push_back(Res.second);
+    return true;
+  }
+
+  return false;
+}
+
+/// visitStrNLenCall -- See if we can lower a strnlen call into an optimized
+/// form.  If so, return true and lower it, otherwise return false and it
+/// will be lowered like a normal call.
+bool SelectionDAGBuilder::visitStrNLenCall(const CallInst &I) {
+  // Verify that the prototype makes sense.  size_t strnlen(char *, size_t)
+  if (I.getNumArgOperands() != 2)
+    return false;
+
+  const Value *Arg0 = I.getArgOperand(0), *Arg1 = I.getArgOperand(1);
+  if (!Arg0->getType()->isPointerTy() ||
+      !Arg1->getType()->isIntegerTy() ||
+      !I.getType()->isIntegerTy())
+    return false;
+
+  const TargetSelectionDAGInfo &TSI = DAG.getSelectionDAGInfo();
+  std::pair<SDValue, SDValue> Res =
+    TSI.EmitTargetCodeForStrnlen(DAG, getCurSDLoc(), DAG.getRoot(),
+                                 getValue(Arg0), getValue(Arg1),
+                                 MachinePointerInfo(Arg0));
+  if (Res.first.getNode()) {
+    processIntegerCallValue(I, Res.first, false);
+    PendingLoads.push_back(Res.second);
+    return true;
+  }
+
+  return false;
+}
+
 /// visitUnaryFloatCall - If a call instruction is a unary floating-point
 /// operation (as expected), translate it to an SDNode with the specified opcode
 /// and return true.
@@ -5774,6 +5827,14 @@ void SelectionDAGBuilder::visitCall(const CallInst &I) {
         if (visitStrCmpCall(I))
           return;
         break;
+      case LibFunc::strlen:
+        if (visitStrLenCall(I))
+          return;
+        break;
+      case LibFunc::strnlen:
+        if (visitStrNLenCall(I))
+          return;
+        break;
       }
     }
   }

diff --git a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
index 7c6e671b73f435f1b620b340ff8eb607ea6937a5..f1cf17ffef4271e8bad81842adaa55df0cb32592 100644 (file)
--- a/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
+++ b/lib/CodeGen/SelectionDAG/SelectionDAGBuilder.h
@@ -525,6 +525,8 @@ private:
   bool visitMemCmpCall(const CallInst &I);
   bool visitStrCpyCall(const CallInst &I, bool isStpcpy);
   bool visitStrCmpCall(const CallInst &I);
+  bool visitStrLenCall(const CallInst &I);
+  bool visitStrNLenCall(const CallInst &I);
   bool visitUnaryFloatCall(const CallInst &I, unsigned Opcode);
   void visitAtomicLoad(const LoadInst &I);
   void visitAtomicStore(const StoreInst &I);

diff --git a/lib/Target/SystemZ/SystemZISelLowering.cpp b/lib/Target/SystemZ/SystemZISelLowering.cpp
index b22cc40155d77133ac833dbc2b02e04dcbdee2f8..788fc2e7058fabc8056d268bfe4188b596f60855 100644 (file)
--- a/lib/Target/SystemZ/SystemZISelLowering.cpp
+++ b/lib/Target/SystemZ/SystemZISelLowering.cpp
@@ -1704,6 +1704,7 @@ const char *SystemZTargetLowering::getTargetNodeName(unsigned Opcode) const {
     OPCODE(CLC);
     OPCODE(STRCMP);
     OPCODE(STPCPY);
+    OPCODE(SEARCH_STRING);
     OPCODE(IPM);
     OPCODE(ATOMIC_SWAPW);
     OPCODE(ATOMIC_LOADW_ADD);
@@ -2554,6 +2555,8 @@ EmitInstrWithCustomInserter(MachineInstr *MI, MachineBasicBlock *MBB) const {
     return emitStringWrapper(MI, MBB, SystemZ::CLST);
   case SystemZ::MVSTLoop:
     return emitStringWrapper(MI, MBB, SystemZ::MVST);
+  case SystemZ::SRSTLoop:
+    return emitStringWrapper(MI, MBB, SystemZ::SRST);
   default:
     llvm_unreachable("Unexpected instr type to insert");
   }

diff --git a/lib/Target/SystemZ/SystemZISelLowering.h b/lib/Target/SystemZ/SystemZISelLowering.h
index b27f1672e83fe7d347625a34c89dae2acbcbab4b..21677a0e77c5f72fef338c183fdae3dfe7e57183 100644 (file)
--- a/lib/Target/SystemZ/SystemZISelLowering.h
+++ b/lib/Target/SystemZ/SystemZISelLowering.h
@@ -91,6 +91,12 @@ namespace SystemZISD {
     // are the addresses of the strings to compare.
     STRCMP,
 
+    // Use an SRST-based sequence to search a block of memory.  The first
+    // operand is the end address, the second is the start, and the third
+    // is the character to search for.  CC is set to 1 on success and 2
+    // on failure.
+    SEARCH_STRING,
+
     // Store the CC value in bits 29 and 28 of an integer.
     IPM,
 

diff --git a/lib/Target/SystemZ/SystemZInstrInfo.td b/lib/Target/SystemZ/SystemZInstrInfo.td
index 43537aa3cc1454786cd8613de53ac618025650a5..7789d614972c99c029d286cb40d25cefe2dc6732 100644 (file)
--- a/lib/Target/SystemZ/SystemZInstrInfo.td
+++ b/lib/Target/SystemZ/SystemZInstrInfo.td
@@ -1163,6 +1163,10 @@ let usesCustomInserter = 1 in {
   def ZEXT128_64 : Pseudo<(outs GR128:$dst), (ins GR64:$src), []>;
 }
 
+// Search a block of memory for a character.
+let mayLoad = 1, Defs = [CC], Uses = [R0W] in
+  defm SRST : StringRRE<"srst", 0xb25e, z_search_string>;
+
 //===----------------------------------------------------------------------===//
 // Peepholes.
 //===----------------------------------------------------------------------===//

diff --git a/lib/Target/SystemZ/SystemZOperators.td b/lib/Target/SystemZ/SystemZOperators.td
index e0eeab109d48e320988f8fd5079773e7aac9909f..1a3d45efe997059cae313910da08b3f04307d6f3 100644 (file)
--- a/lib/Target/SystemZ/SystemZOperators.td
+++ b/lib/Target/SystemZ/SystemZOperators.td
@@ -123,6 +123,8 @@ def z_strcmp            : SDNode<"SystemZISD::STRCMP", SDT_ZString,
                                  [SDNPHasChain, SDNPOutGlue, SDNPMayLoad]>;
 def z_stpcpy            : SDNode<"SystemZISD::STPCPY", SDT_ZString,
                                  [SDNPHasChain, SDNPMayStore, SDNPMayLoad]>;
+def z_search_string     : SDNode<"SystemZISD::SEARCH_STRING", SDT_ZString,
+                                 [SDNPHasChain, SDNPOutGlue, SDNPMayLoad]>;
 def z_ipm               : SDNode<"SystemZISD::IPM", SDT_ZI32Intrinsic,
                                  [SDNPInGlue]>;
 

diff --git a/lib/Target/SystemZ/SystemZSelectionDAGInfo.cpp b/lib/Target/SystemZ/SystemZSelectionDAGInfo.cpp
index 0a2080db0b99356881d2dd7f30daa4e93fa1df71..73bd4808fe8490532a0280e542b484b8ff4d8742 100644 (file)
--- a/lib/Target/SystemZ/SystemZSelectionDAGInfo.cpp
+++ b/lib/Target/SystemZ/SystemZSelectionDAGInfo.cpp
@@ -181,3 +181,37 @@ EmitTargetCodeForStrcmp(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
   SDValue Glue = Chain.getValue(2);
   return std::make_pair(addIPMSequence(DL, Glue, DAG), Chain);
 }
+
+// Search from Src for a null character, stopping once Src reaches Limit.
+// Return a pair of values, the first being the number of nonnull characters
+// and the second being the out chain.
+//
+// This can be used for strlen by setting Limit to 0.
+static std::pair<SDValue, SDValue> getBoundedStrlen(SelectionDAG &DAG, SDLoc DL,
+                                                    SDValue Chain, SDValue Src,
+                                                    SDValue Limit) {
+  EVT PtrVT = Src.getValueType();
+  SDVTList VTs = DAG.getVTList(PtrVT, MVT::Other, MVT::Glue);
+  SDValue End = DAG.getNode(SystemZISD::SEARCH_STRING, DL, VTs, Chain,
+                            Limit, Src, DAG.getConstant(0, MVT::i32));
+  Chain = End.getValue(1);
+  SDValue Len = DAG.getNode(ISD::SUB, DL, PtrVT, End, Src);
+  return std::make_pair(Len, Chain);
+}    
+
+std::pair<SDValue, SDValue> SystemZSelectionDAGInfo::
+EmitTargetCodeForStrlen(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
+                        SDValue Src, MachinePointerInfo SrcPtrInfo) const {
+  EVT PtrVT = Src.getValueType();
+  return getBoundedStrlen(DAG, DL, Chain, Src, DAG.getConstant(0, PtrVT));
+}
+
+std::pair<SDValue, SDValue> SystemZSelectionDAGInfo::
+EmitTargetCodeForStrnlen(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
+                         SDValue Src, SDValue MaxLength,
+                         MachinePointerInfo SrcPtrInfo) const {
+  EVT PtrVT = Src.getValueType();
+  MaxLength = DAG.getZExtOrTrunc(MaxLength, DL, PtrVT);
+  SDValue Limit = DAG.getNode(ISD::ADD, DL, PtrVT, Src, MaxLength);
+  return getBoundedStrlen(DAG, DL, Chain, Src, Limit);
+}

diff --git a/lib/Target/SystemZ/SystemZSelectionDAGInfo.h b/lib/Target/SystemZ/SystemZSelectionDAGInfo.h
index 123cb63c09c6f575b74039e1ab4fe6f1f64656aa..26d648893ea2f316349c4f89b5da14f2399f4937 100644 (file)
--- a/lib/Target/SystemZ/SystemZSelectionDAGInfo.h
+++ b/lib/Target/SystemZ/SystemZSelectionDAGInfo.h
@@ -58,6 +58,16 @@ public:
                           SDValue Src1, SDValue Src2,
                           MachinePointerInfo Op1PtrInfo,
                           MachinePointerInfo Op2PtrInfo) const LLVM_OVERRIDE;
+
+  virtual std::pair<SDValue, SDValue>
+  EmitTargetCodeForStrlen(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
+                          SDValue Src, MachinePointerInfo SrcPtrInfo) const
+    LLVM_OVERRIDE;
+
+  virtual std::pair<SDValue, SDValue>
+  EmitTargetCodeForStrnlen(SelectionDAG &DAG, SDLoc DL, SDValue Chain,
+                           SDValue Src, SDValue MaxLength,
+                           MachinePointerInfo SrcPtrInfo) const LLVM_OVERRIDE;
 };
 
 }

diff --git a/test/CodeGen/SystemZ/strlen-01.ll b/test/CodeGen/SystemZ/strlen-01.ll
new file mode 100644 (file)
index 0000000..16161d4
--- /dev/null
+++ b/test/CodeGen/SystemZ/strlen-01.ll
@@ -0,0 +1,39 @@
+; Test strlen using SRST, i64 version.
+;
+; RUN: llc < %s -mtriple=s390x-linux-gnu | FileCheck %s
+
+declare i64 @strlen(i8 *%src)
+declare i64 @strnlen(i8 *%src, i64 %len)
+
+; Test strlen with its proper i64 prototype.  It would also be valid for
+; the uses of %r3 and REG after the LGR to be swapped.
+define i64 @f1(i32 %dummy, i8 *%src) {
+; CHECK-LABEL: f1:
+; CHECK-DAG: lhi %r0, 0
+; CHECK-DAG: lghi %r2, 0
+; CHECK-DAG: lgr [[REG:%r[145]]], %r3
+; CHECK: [[LABEL:\.[^:]*]]:
+; CHECK-NEXT: srst %r2, [[REG]]
+; CHECK-NEXT: jo [[LABEL]]
+; CHECK-NEXT: BB#{{[0-9]+}}
+; CHECK-NEXT: sgr %r2, %r3
+; CHECK: br %r14
+  %res = call i64 @strlen(i8 *%src)
+  ret i64 %res
+}
+
+; Test strnlen with its proper i64 prototype.
+define i64 @f2(i64 %len, i8 *%src) {
+; CHECK-LABEL: f2:
+; CHECK-DAG: agr %r2, %r3
+; CHECK-DAG: lhi %r0, 0
+; CHECK-DAG: lgr [[REG:%r[145]]], %r3
+; CHECK: [[LABEL:\.[^:]*]]:
+; CHECK-NEXT: srst %r2, [[REG]]
+; CHECK-NEXT: jo [[LABEL]]
+; CHECK-NEXT: BB#{{[0-9]+}}
+; CHECK-NEXT: sgr %r2, %r3
+; CHECK: br %r14
+  %res = call i64 @strnlen(i8 *%src, i64 %len)
+  ret i64 %res
+}

diff --git a/test/CodeGen/SystemZ/strlen-02.ll b/test/CodeGen/SystemZ/strlen-02.ll
new file mode 100644 (file)
index 0000000..e1abbff
--- /dev/null
+++ b/test/CodeGen/SystemZ/strlen-02.ll
@@ -0,0 +1,39 @@
+; Test strlen using SRST, i32 version.
+;
+; RUN: llc < %s -mtriple=s390x-linux-gnu | FileCheck %s
+
+declare i32 @strlen(i8 *%src)
+declare i32 @strnlen(i8 *%src, i32 %len)
+
+; Test strlen with an i32-based prototype.  It would also be valid for
+; the uses of %r3 and REG after the LGR to be swapped.
+define i32 @f1(i32 %dummy, i8 *%src) {
+; CHECK-LABEL: f1:
+; CHECK-DAG: lhi %r0, 0
+; CHECK-DAG: lghi %r2, 0
+; CHECK-DAG: lgr [[REG:%r[145]]], %r3
+; CHECK: [[LABEL:\.[^:]*]]:
+; CHECK-NEXT: srst %r2, [[REG]]
+; CHECK-NEXT: jo [[LABEL]]
+; CHECK-NEXT: BB#{{[0-9]+}}
+; CHECK-NEXT: sgr %r2, %r3
+; CHECK: br %r14
+  %res = call i32 @strlen(i8 *%src)
+  ret i32 %res
+}
+
+; Test strnlen with an i32-based prototype.
+define i32 @f2(i32 zeroext %len, i8 *%src) {
+; CHECK-LABEL: f2:
+; CHECK-DAG: agr %r2, %r3
+; CHECK-DAG: lhi %r0, 0
+; CHECK-DAG: lgr [[REG:%r[145]]], %r3
+; CHECK: [[LABEL:\.[^:]*]]:
+; CHECK-NEXT: srst %r2, [[REG]]
+; CHECK-NEXT: jo [[LABEL]]
+; CHECK-NEXT: BB#{{[0-9]+}}
+; CHECK-NEXT: sgr %r2, %r3
+; CHECK: br %r14
+  %res = call i32 @strnlen(i8 *%src, i32 %len)
+  ret i32 %res
+}

diff --git a/test/MC/Disassembler/SystemZ/insns.txt b/test/MC/Disassembler/SystemZ/insns.txt
index c25bb9f946132bd20a63aec7808f9700ab6577ad..328e2d63d436bed9264118be2a2eba5198e68434 100644 (file)
--- a/test/MC/Disassembler/SystemZ/insns.txt
+++ b/test/MC/Disassembler/SystemZ/insns.txt
@@ -6253,6 +6253,18 @@
 # CHECK: srk %r2, %r3, %r4
 0xb9 0xf9 0x40 0x23
 
+# CHECK: srst %r0, %r0
+0xb2 0x5e 0x00 0x00
+
+# CHECK: srst %r0, %r15
+0xb2 0x5e 0x00 0x0f
+
+# CHECK: srst %r15, %r0
+0xb2 0x5e 0x00 0xf0
+
+# CHECK: srst %r7, %r8
+0xb2 0x5e 0x00 0x78
+
 # CHECK: stc %r0, 0
 0x42 0x00 0x00 0x00
 

diff --git a/test/MC/SystemZ/insn-good.s b/test/MC/SystemZ/insn-good.s
index da2b77e4eb7d2861c279cc270a3f18016ec1f300..52dc31d9dff0a36b27f2497cf73f266d99a1b97f 100644 (file)
--- a/test/MC/SystemZ/insn-good.s
+++ b/test/MC/SystemZ/insn-good.s
@@ -6728,6 +6728,16 @@
        srlg    %r0,%r0,524287(%r1)
        srlg    %r0,%r0,524287(%r15)
 
+#CHECK: srst   %r0, %r0                # encoding: [0xb2,0x5e,0x00,0x00]
+#CHECK: srst   %r0, %r15               # encoding: [0xb2,0x5e,0x00,0x0f]
+#CHECK: srst   %r15, %r0               # encoding: [0xb2,0x5e,0x00,0xf0]
+#CHECK: srst   %r7, %r8                # encoding: [0xb2,0x5e,0x00,0x78]
+
+       srst    %r0,%r0
+       srst    %r0,%r15
+       srst    %r15,%r0
+       srst    %r7,%r8
+
 #CHECK: st     %r0, 0                  # encoding: [0x50,0x00,0x00,0x00]
 #CHECK: st     %r0, 4095               # encoding: [0x50,0x00,0x0f,0xff]
 #CHECK: st     %r0, 0(%r1)             # encoding: [0x50,0x00,0x10,0x00]