Strlen loop idiom recognition

[anjankgk]

Summary

(Original patch by musman under D83392. I am planning to commit this in his absence, with his consent.)
This patch adds strlen to LoopIdiomRecognize.cpp. It is the first part of 3 patches:

1. Strlen loop idiom recognition
2. Strlen16 recognition and creation of new strlen16 intrinsic
3. Folding of strlen/strlen16 call if they are only used for zero equality comparison (replace with load of first char)

Example that this recognizes:

unsigned strlen(char *Str) {

char *Src = Str;
if (!Src)
  return 0;
for (; *Src;)
  Src++;
return Src - Str;

}

[anjankgk]

Gentle ping..

[shawnl]

This pass should recognise the nonnull attribute, as it is analyzing against null.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1614

If the passed pointer has the "nonnull" attribute then this condition need not be present.

[shawnl]

It is possible DCE will handle the null check with "nonnull" attribute, so add the test first.

Otherwise I like how little code this took compared to earlier versions.

[efriedma]

(For future reference, Phabricator has an option "commandeer" a revision, to take control if the original author of a patch leaves a patch incomplete for whatever reason. Obviously use sparingly.)

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1614

The icmp isn't against a pointer; it's against an i8. Or, it should be; I guess the code is missing a check that it's i8, as opposed to some arbitrary integer type.

For comparison, it's undefined behavior to call strlen with a null pointer.

1666

I'm not sure how ResInst is connected to the rest of this transform; why are we transforming the operand of some random PHI node?

1683

"dead instructions", not "death instructions".

llvm/test/Transforms/LoopIdiom/recognize-strlen.ll

1

Can you generate the check lines use update_test_checks.py? It isn't obvious what the whole function looks like as a result of this transform.

[shawnl]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1614

My bad. I was really working from example code (and the tests also have a null check). This is why in my C code I always use '\x00' for NUL (the character) and not 0 or NULL.

[anjankgk]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1666

I added a comment for clarity -

// Finally, we find the phi node that corresponds to the distance between the
// pointers and replace it's uses by the call to strlen in the transformed
// code.

[anjankgk]

Check for i8 type and use update_test_checks.py for testfile.

[efriedma]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1666

The patch doesn't appear to prove that anywhere.

[anjankgk]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1666

I am getting the sub instruction saved in ResInst and replacing that in line# 1689. Is that something that you prefer to be done in a different way?

[efriedma]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1666

How do you know it's a sub instruction?

[anjankgk]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1666

I agree. The current code is actually just looking for the phi node from the predecessor (LoopExitBB) block. I think, I should add a code to ensure that is actually a sub instruction. However, I am afraid that that could again lead to a pattern-matching kind of code which was initially posted.

[efriedma]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1666

What happens if we ignore ResInst, and rewrite LCSSAPhi instead? That still eliminates the inner loop; later passes should optimize the resulting arithmetic.

[anjankgk]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1666

I tried a few things, but I am not sure how to do that.
This is the i/p BB:

for.end:                                          ; preds = %for.inc
  %incdec.ptr.lcssa = phi i8* [ %incdec.ptr, %for.inc ]
  %sub.ptr.lhs.cast = ptrtoint i8* %incdec.ptr.lcssa to i64
  %sub.ptr.rhs.cast = ptrtoint i8* %Str to i64
  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
  br label %cleanup

return type of strlen is i64 (same as ResInt which is %sub.ptr.sub), as compared to the type of lcssa instrn (%incdec.ptr.lcssa) which is a i8*. I am not clear how I can rewrite lcssa with the strlen as suggested.

[efriedma]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1666

%incdec.ptr.lcssa is going to be equivalent to something like getelementptr i8, i8* %Str, i64 %strlen. Speaking in generic terms, replace %Str with the start value of LCSSAEv. Add the two values together with SCEV, and use SCEVExpander to materialize it.

[anjankgk]

Rewrite the LCSSAPhi instruction to reflect strlen idiom recognition.

[efriedma]

Phabricator doesn't track incremental patches the way you're uploading them; please upload the full diff against master.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1680–1681

LCSSAEv->getStart() is the value of the output of the loop; the input to strlen needs to be the input to the load (LoadEv->getStart()).

More tests would be helpful to catch this sort of issue.

1690

getPointerBase() isn't right; it strips all offsets from the pointer.

I'd like to see more regression test coverage of different variations on the values produced by the loop.

[hiraditya]

It'll be nice to know if this patch worked fine with a set of regression tests.
results on LLVM testsuite, or clang bootstrap will really help.

Thanks for working on this.

[anjankgk]

Changes from previous review comments:

• Replaced LCSSAEv->getStart() by LoadEv->getStart()
• Added another test function where multiple LCSSAPhi nodes were present and therefore shouldn't have replaced with strlen function.

[anjankgk]

In D88460#2342407, @efriedma wrote:

Phabricator doesn't track incremental patches the way you're uploading them; please upload the full diff against master.

Thanks @efriedma! I made the changes suggested and added another test as well. I have uploaded the right patch this time. Pls let me know in case it's still showing up wrongly.

[anjankgk]

In D88460#2342937, @hiraditya wrote:

It'll be nice to know if this patch worked fine with a set of regression tests.
results on LLVM testsuite, or clang bootstrap will really help.

Thanks for working on this.

Thank you for the feedback @hiraditya! I have tested the latest patch at various options (O2, O3, LTO and PGO) against the SPEC benchmarks as well as run the lnt tests and bootstrap tests successfully. If you were concerned about any other specific testsuite, pls let me know.

[hiraditya]

In D88460#2458205, @anjankgk wrote:

In D88460#2342937, @hiraditya wrote:

It'll be nice to know if this patch worked fine with a set of regression tests.
results on LLVM testsuite, or clang bootstrap will really help.

Thanks for working on this.

Thank you for the feedback @hiraditya! I have tested the latest patch at various options (O2, O3, LTO and PGO) against the SPEC benchmarks as well as run the lnt tests and bootstrap tests successfully. If you were concerned about any other specific testsuite, pls let me know.

Nice, if we have performance improvements on any of the benchmarks/workloads then do share.

[anjankgk]

In D88460#2462158, @hiraditya wrote:

In D88460#2458205, @anjankgk wrote:

In D88460#2342937, @hiraditya wrote:

It'll be nice to know if this patch worked fine with a set of regression tests.
results on LLVM testsuite, or clang bootstrap will really help.

Thanks for working on this.

Thank you for the feedback @hiraditya! I have tested the latest patch at various options (O2, O3, LTO and PGO) against the SPEC benchmarks as well as run the lnt tests and bootstrap tests successfully. If you were concerned about any other specific testsuite, pls let me know.

Nice, if we have performance improvements on any of the benchmarks/workloads then do share.

I did track performance measurements on a bunch of benchmarks but there was nothing noticeable since what this patch is doing is just recognizing the idiom and replacing with the lib call. However, going forward, if we could better the implementation of these library calls (which could be target platform specific) this should give us gains.

[anjankgk]

Gentle ping...

[anjankgk]

Another gentle reminder for the review.. Thanks!

[hiraditya]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1657

break when I != PN because PNs are in the beginning of a basic block.

if (!PN)
  break;

1719

Should we call forgetLoop before deleting the loop?

1721

Shouldn't be necessary as ORE is already there.

[anjankgk]

Updates from tests and fix to identifying the correct replace instruction from exit BB.

[anjankgk]

I have updated the code based on some more test results and based on the review comments.
Thanks!

[anjankgk]

Gentle ping..

[hiraditya]

Do we have an example of real world workload where this pattern was found?

[hiraditya]

This comment was removed by hiraditya.

[joerg]

Please make sure at the very least that it doesn't get matched if a function named strlen and also test for that.

[hiraditya]

In D88460#2816028, @joerg wrote:

Please make sure at the very least that it doesn't get matched if a function named strlen and also test for that.

yeah, transforming strlen itself will be a lot of trouble ;)

[hiraditya]

Can this patch also convert this one to strlen? gcc is able to recognize this idiom: https://godbolt.org/z/7ra1ErqKK

size_t strlen2(char *Str) {
    char *Src = Str;
    int i = 0;
    while (*Src) {
        ++i;
        ++Src;
    }
    return i;
}

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

if (!EntryBI || EntryBI->isConditional())
     return false;
 
   // It should have a precondition block
   auto *PreCondBB = PH->getSinglePredecessor();
   if (!PreCondBB)
     return false;
   auto *PreCondBI = dyn_cast<BranchInst>(PreCondBB->getTerminator());
   if (!PreCondBI || PreCondBI->isUnconditional())
     return false;
 
   // The loop exit must be conditioned on an icmp with 0.
   // The icmp operand has to be a load on some SSA reg that increments
   // by 1 in the loop.
   BasicBlock *LoopBody = *(CurLoop->block_begin());
   auto *LoopTerm = dyn_cast<BranchInst>(LoopBody->getTerminator());
   auto *LoopCond = matchCondition(LoopTerm, LoopBody);
+
   if (!LoopCond)
     return false;
   auto *LoopLoad = dyn_cast<LoadInst>(LoopCond);
-  if (!LoopLoad || LoopLoad->getPointerAddressSpace() != 0)
+  if (!LoopLoad || !LoopLoad->getType()->isIntegerTy(8) ||
+      LoopLoad->getPointerAddressSpace() != 0)
     return false;
 
   // See if the pointer expression is an AddRec with step 1 ({n,+,1}) on
   // the loop, indicating strlen calculation.
   auto *IncPtr = LoopLoad->getPointerOperand();
   const SCEVAddRecExpr *LoadEv = dyn_cast<SCEVAddRecExpr>(SE->getSCEV(IncPtr));
   if (!LoadEv || LoadEv->getLoop() != CurLoop || !LoadEv->isAffine())
     return false;
bool LoopIdiomRecognize::recognizeAndInsertStrlen() {
   // Check that the loop exit block is valid:
   // It needs to have exactly one LCSSA Phi which is an AddRec.
   auto *LoopExitBB =
       (LoopTerm->getSuccessor(0) == LoopBody ? LoopTerm->getSuccessor(1)
                                              : LoopTerm->getSuccessor(0));
   PHINode *LCSSAPhi = dyn_cast<PHINode>(LoopExitBB->begin());
   if (!LCSSAPhi || LCSSAPhi->getNumIncomingValues() != 1)
     return false;
-  const SCEVAddRecExpr *LCSSAEv = dyn_cast<SCEVAddRecExpr>(
-    SE->getSCEV(LCSSAPhi->getIncomingValue(0)));
+  const SCEVAddRecExpr *LCSSAEv = 
+      dyn_cast<SCEVAddRecExpr>(SE->getSCEV(LCSSAPhi->getIncomingValue(0)));
   if (!LCSSAEv || !LCSSAEv->isAffine())
     return false;
 
   auto *CleanupBB =
       (PreCondBI->getSuccessor(0) == PH ? PreCondBI->getSuccessor(1)
                                         : PreCondBI->getSuccessor(0));
+
+  // Finally, we find the phi node that corresponds to the distance between the
+  // pointers and replace it's uses by the call to strlen in the transformed 
+  // code.
   Value *ResInst = nullptr;
   for (auto &Phi : CleanupBB->phis()) {
     if (Phi.getBasicBlockIndex(LoopExitBB) != 1) {
       ResInst = Phi.getIncomingValueForBlock(LoopExitBB);
       break;
     }
   }
   if (!ResInst)
     return false;
 
   // We can now expand the base of the str and transform the loop
   SCEVExpander Expander(*SE, *DL, "loop-idiom");
   ExpandedValuesCleaner EVC(Expander, TLI);
   IRBuilder<> Builder(PH->getTerminator());
 
   Value *Expanded = Expander.expandCodeFor(
       LCSSAEv->getStart(),
       Builder.getInt8PtrTy(LoopLoad->getPointerAddressSpace()),
       PH->getTerminator());
   EVC.add(Expanded);
   EVC.commit();
           
   Value *LibCall = emitStrLen(Expanded, Builder, *DL, TLI);
   Value *Strlen = Builder.CreateZExtOrTrunc(LibCall, ResInst->getType());
   ResInst->replaceAllUsesWith(Strlen);
 
-  // Remove the loop-exit branch and delete death instructions
+  // Remove the loop-exit branch and delete dead instructions
   RecursivelyDeleteTriviallyDeadInstructions(ResInst, TLI);
   ConstantInt *NewLoopCond = LoopTerm->getSuccessor(0) == LoopBody
                                  ? Builder.getFalse()
                                  : Builder.getTrue();
   LoopTerm->setCondition(NewLoopCond);
   deleteDeadInstruction(cast<Instruction>(LoopCond));
   deleteDeadInstruction(cast<Instruction>(IncPtr));
   SE->forgetLoop(CurLoop);
if (TTI->getPopcntSupport(32) != TargetTransformInfo::PSK_FastHardware)
     return false;
 
   // Counting population are usually conducted by few arithmetic instructions.
   // Such instructions can be easily "absorbed" by vacant slots in a
   // non-compact loop. Therefore, recognizing popcount idiom only makes sense
   // in a compact loop.
 
   // Give up if the loop has multiple blocks or multiple backedges.
   if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 1)
     return false;
 
   BasicBlock *LoopBody = *(CurLoop->block_begin());
   if (LoopBody->size() >= 20) {
     // The loop is too big, bail out.
     return false;
   }
 
   // It should have a preheader containing nothing but an unconditional branch.
   BasicBlock *PH = CurLoop->getLoopPreheader();

llvm/test/Transforms/LoopIdiom/recognize-strlen.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -loop-idiom < %s -S | FileCheck %s
 target datalayout = "e-m:e-i64:64-n32:64"
 target triple = "powerpc64le-unknown-linux-gnu"
 
 define i64 @valid_strlen1(i8* %Str) {
+; CHECK-LABEL: @valid_strlen1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8* [[STR:%.*]], null
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[CLEANUP:%.*]], label [[LOR_LHS_FALSE:%.*]]
+; CHECK:       lor.lhs.false:
+; CHECK-NEXT:    [[TMP0:%.*]] = load i8, i8* [[STR]], align 1
+; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i8 [[TMP0]], 0
+; CHECK-NEXT:    br i1 [[CMP]], label [[CLEANUP]], label [[FOR_INC_PREHEADER:%.*]]
+; CHECK:       for.inc.preheader:
+; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, i8* [[STR]], i64 1
+; CHECK-NEXT:    [[STRLEN:%.*]] = call i64 @strlen(i8* [[SCEVGEP]])
+; CHECK-NEXT:    br label [[FOR_INC:%.*]]
+; CHECK:       for.inc:
+; CHECK-NEXT:    [[SRC_09:%.*]] = phi i8* [ undef, [[FOR_INC]] ], [ [[STR]], [[FOR_INC_PREHEADER]] ]
+; CHECK-NEXT:    [[TOBOOL2:%.*]] = icmp eq i8 undef, 0
+; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[FOR_INC]]
+; CHECK:       for.end:
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       cleanup:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i64 [ [[STRLEN]], [[FOR_END]] ], [ 0, [[ENTRY:%.*]] ], [ 0, [[LOR_LHS_FALSE]] ]
+; CHECK-NEXT:    ret i64 [[RETVAL_0]]
+;
 entry:
   %tobool = icmp eq i8* %Str, null
   br i1 %tobool, label %cleanup, label %lor.lhs.false
 
 lor.lhs.false:                                    ; preds = %entry
   %0 = load i8, i8* %Str, align 1
   %cmp = icmp eq i8 %0, 0
   br i1 %cmp, label %cleanup, label %for.inc
 
-; CHECK:  call i64 @strlen(i8* %Str)
-; CHECK:  br i1 true
 for.inc:                                          ; preds = %lor.lhs.false, %for.inc
   %Src.09 = phi i8* [ %incdec.ptr, %for.inc ], [ %Str, %lor.lhs.false ]
   %incdec.ptr = getelementptr inbounds i8, i8* %Src.09, i64 1
   %.pr = load i8, i8* %incdec.ptr, align 1
   %tobool2 = icmp eq i8 %.pr, 0
   br i1 %tobool2, label %for.end, label %for.inc
 
-; CHECK-NOT:    sub
 for.end:                                          ; preds = %for.inc
   %sub.ptr.lhs.cast = ptrtoint i8* %incdec.ptr to i64
   %sub.ptr.rhs.cast = ptrtoint i8* %Str to i64
   %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
   br label %cleanup
 
 cleanup:                                          ; preds = %lor.lhs.false, %entry, %for.end
   %retval.0 = phi i64 [ %sub.ptr.sub, %for.end ], [ 0, %entry ], [ 0, %lor.lhs.false ]
   ret i64 %retval.0
 }
 
 
 define i64 @valid_strlen2(i8* %Str) {
+; CHECK-LABEL: @valid_strlen2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp eq i8* [[STR:%.*]], null
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[CLEANUP:%.*]], label [[FOR_COND_PREHEADER:%.*]]
+; CHECK:       for.cond.preheader:
+; CHECK-NEXT:    [[STRLEN:%.*]] = call i64 @strlen(i8* [[STR]])
+; CHECK-NEXT:    br label [[FOR_COND:%.*]]
+; CHECK:       for.cond:
+; CHECK-NEXT:    [[TOBOOL1:%.*]] = icmp eq i8 undef, 0
+; CHECK-NEXT:    [[INCDEC_PTR:%.*]] = getelementptr inbounds i8, i8* undef, i64 1
+; CHECK-NEXT:    br i1 true, label [[FOR_END:%.*]], label [[FOR_COND]]
+; CHECK:       for.end:
+; CHECK-NEXT:    br label [[CLEANUP]]
+; CHECK:       cleanup:
+; CHECK-NEXT:    [[RETVAL_0:%.*]] = phi i64 [ [[STRLEN]], [[FOR_END]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    ret i64 [[RETVAL_0]]
+;
 entry:
   %tobool = icmp eq i8* %Str, null
   br i1 %tobool, label %cleanup, label %for.cond
 
-; CHECK:  call i64 @strlen(i8* %Str)
-; CHECK:  br i1 true
 for.cond:                                         ; preds = %entry, %for.cond
   %Src.0 = phi i8* [ %incdec.ptr, %for.cond ], [ %Str, %entry ]
   %0 = load i8, i8* %Src.0, align 1
   %tobool1 = icmp eq i8 %0, 0
   %incdec.ptr = getelementptr inbounds i8, i8* %Src.0, i64 1
   br i1 %tobool1, label %for.end, label %for.cond
 
-; CHECK-NOT:    sub
 for.end:                                          ; preds = %for.cond
   %sub.ptr.lhs.cast = ptrtoint i8* %Src.0 to i64
   %sub.ptr.rhs.cast = ptrtoint i8* %Str to i64
   %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
   br label %cleanup
 
   cleanup:                                          ; preds = %entry, %for.end
   %retval.0 = phi i64 [ %sub.ptr.sub, %for.end ], [ 0, %entry ]
   ret i64 %retval.0
 }
-
-
-define zeroext i32 @valid_strlen3(i8* %Str) {
-entry:
-  %tobool = icmp eq i8* %Str, null
-  br i1 %tobool, label %cleanup, label %lor.lhs.false
-
-lor.lhs.false:                                    ; preds = %entry
-  %0 = load i8, i8* %Str, align 1
-  %cmp = icmp eq i8 %0, 0
-  br i1 %cmp, label %cleanup, label %for.inc
-
-; CHECK:  call i64 @strlen(i8* %Str)
-; CHECK:  br i1 true
-for.inc:                                          ; preds = %lor.lhs.false, %for.inc
-  %Src.010 = phi i8* [ %incdec.ptr, %for.inc ], [ %Str, %lor.lhs.false ]
-  %incdec.ptr = getelementptr inbounds i8, i8* %Src.010, i64 1
-  %.pr = load i8, i8* %incdec.ptr, align 1
-  %tobool2 = icmp eq i8 %.pr, 0
-  br i1 %tobool2, label %for.end, label %for.inc
-
-; CHECK:      trunc i64 %strlen to i32
-; CHECK-NOT:  sub
-for.end:                                          ; preds = %for.inc
-  %sub.ptr.lhs.cast = ptrtoint i8* %incdec.ptr to i64
-  %sub.ptr.rhs.cast = ptrtoint i8* %Str to i64
-  %sub.ptr.sub = sub i64 %sub.ptr.lhs.cast, %sub.ptr.rhs.cast
-  %conv3 = trunc i64 %sub.ptr.sub to i32
-  br label %cleanup
-
-cleanup:                                          ; preds = %lor.lhs.false, %entry, %for.end
-  %retval.0 = phi i32 [ %conv3, %for.end ], [ 0, %entry ], [ 0, %lor.lhs.false ]
-  ret i32 %retval.0
-}