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

1639

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

1639

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.

1691

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?

1708

"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

1639

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

1691

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

1691

The patch doesn't appear to prove that anywhere.

[anjankgk]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1691

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

1691

How do you know it's a sub instruction?

[anjankgk]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1691

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

1691

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

1691

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

1691

%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

1610–1723

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.

1611

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

1682

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

if (!PN)
  break;

1744

Should we call forgetLoop before deleting the loop?

1746

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

 #include <vector>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-idiom"
 
 STATISTIC(NumMemSet, "Number of memset's formed from loop stores");
 STATISTIC(NumMemCpy, "Number of memcpy's formed from loop load+stores");
+STATISTIC(NumStrLen, "Number of strlen's formed from loop loads");
 
 bool DisableLIRP::All;
 static cl::opt<bool, true>
     DisableLIRPAll("disable-" DEBUG_TYPE "-all",
                    cl::desc("Options to disable Loop Idiom Recognize Pass."),
                    cl::location(DisableLIRP::All), cl::init(false),
                    cl::ReallyHidden);
 
DisableLIRPMemcpy("disable-" DEBUG_TYPE "-memcpy",
                       cl::ReallyHidden);
 
 static cl::opt<bool> UseLIRCodeSizeHeurs(
     "use-lir-code-size-heurs",
     cl::desc("Use loop idiom recognition code size heuristics when compiling"
              "with -Os/-Oz"),
     cl::init(true), cl::Hidden);
 
+static cl::opt<bool> DisableStrlenIdiom(
+    "disable-strlen-idiom",
+    cl::desc("Disable strlen loop idiom recognize and transform"),
+    cl::init(false), cl::Hidden);
+
 namespace {
 
 class LoopIdiomRecognize {
   Loop *CurLoop = nullptr;
   AliasAnalysis *AA;
   DominatorTree *DT;
   LoopInfo *LI;
   ScalarEvolution *SE;
private:
   void transformLoopToPopcount(BasicBlock *PreCondBB, Instruction *CntInst,
                                PHINode *CntPhi, Value *Var);
   bool recognizeAndInsertFFS();  /// Find First Set: ctlz or cttz
   void transformLoopToCountable(Intrinsic::ID IntrinID, BasicBlock *PreCondBB,
                                 Instruction *CntInst, PHINode *CntPhi,
                                 Value *Var, Instruction *DefX,
                                 const DebugLoc &DL, bool ZeroCheck,
                                 bool IsCntPhiUsedOutsideLoop);
+  bool recognizeAndInsertStrlen();
 
   /// @}
 };
 
 class LoopIdiomRecognizeLegacyPass : public LoopPass {
 public:
   static char ID;
 

 }
 
 bool LoopIdiomRecognize::runOnNoncountableLoop() {
   LLVM_DEBUG(dbgs() << DEBUG_TYPE " Scanning: F["
                     << CurLoop->getHeader()->getParent()->getName()
                     << "] Noncountable Loop %"
                     << CurLoop->getHeader()->getName() << "\n");
 
-  return recognizePopcount() || recognizeAndInsertFFS();
+  return recognizePopcount() || recognizeAndInsertFFS() ||
+         recognizeAndInsertStrlen();
 }
 
 /// Check if the given conditional branch is based on the comparison between
 /// a variable and zero, and if the variable is non-zero or zero (JmpOnZero is
 /// true), the control yields to the loop entry. If the branch matches the
 /// behavior, the variable involved in the comparison is returned. This function
 /// will be called to see if the precondition and postcondition of the loop are
 /// in desirable form.
if (HeaderSize != IdiomCanonicalSize &&
       Cost > TargetTransformInfo::TCC_Basic)
     return false;
 
   transformLoopToCountable(IntrinID, PH, CntInst, CntPhi, InitX, DefX,
                            DefX->getDebugLoc(), ZeroCheck,
                            IsCntPhiUsedOutsideLoop);
   return true;
 }
 
+/// Recognizes a strlen idiom by checking for loops that either keep
+/// a variable counter or increment a char pointer and then subtract
+/// with the base pointer.
+///
+/// If detected, transforms the relevant code to a strlen function
+/// call, and returns true; otherwise, returns false.
+bool LoopIdiomRecognize::recognizeAndInsertStrlen() {
+  if (DisableStrlenIdiom)
+    return false;
+
+  // Give up if the loop has multiple blocks or multiple backedges.
+  if (CurLoop->getNumBackEdges() != 1 || CurLoop->getNumBlocks() != 1)
+    return false;
+
+  // It should have a preheader containing nothing but an unconditional branch.
+  BasicBlock *PH = CurLoop->getLoopPreheader();
+  if (!PH || &PH->front() != PH->getTerminator())
+    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)
+    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;
+  const SCEV *StepRec = LoadEv->getStepRecurrence(*SE);
+  if (!StepRec || !StepRec->isOne())
+    return false;
+
+  // Scan every instruction in the loop to ensure there are no side effects.
+  for (auto &I : *LoopBody)
+    if (I.mayHaveSideEffects())
+      return false;
+
+  // 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)));
+  if (!LCSSAEv || !LCSSAEv->isAffine())
+    return false;
+
+  auto *CleanupBB =
+      (PreCondBI->getSuccessor(0) == PH ? PreCondBI->getSuccessor(1)
+                                        : PreCondBI->getSuccessor(0));
+  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");
+  SCEVExpanderCleaner ExpCleaner(Expander, *DT);
+  IRBuilder<> Builder(PH->getTerminator());
+
+  Value *Expanded = Expander.expandCodeFor(
+      LCSSAEv->getStart(),
+      Builder.getInt8PtrTy(LoopLoad->getPointerAddressSpace()),
+      PH->getTerminator());
+
+  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
+  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);
+
+  ++NumStrLen;
+  ExpCleaner.markResultUsed();
+  return true;
+}
+
 /// Recognizes a population count idiom in a non-countable loop.
 ///
 /// If detected, transforms the relevant code to issue the popcount intrinsic
 /// function call, and returns true; otherwise, returns false.
 bool LoopIdiomRecognize::recognizePopcount() {
   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();
   if (!PH || &PH->front() != PH->getTerminator())
     return false;
   auto *EntryBI = dyn_cast<BranchInst>(PH->getTerminator());
   if (!EntryBI || EntryBI->isConditional())
     return false;
 
   // It should have a precondition block where the generated popcount intrinsic

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

+; 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) {
+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* %scevgep)
+; 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) {
+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
+}