Strlen loop idiom recognition

[musman]

Summary

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;
}

[efriedma]

I don't like the way the pattern-matching is written here; analyzing the exact instruction patterns is complicated, error-prone, and likely to miss cases.

I think I'd structure the analysis like this:

1. Is the latch condition of the form "%loadedval = load i8, i8* %p; icmp eq i8 %loadedval, 0"
2. Query SCEV to check %p is an AddRec with step 1.
3. Query SCEV to check all the LCSSA PHI nodes are AddRecs.
4. Check that the loop doesn't contain any operations with side-effects.

Then to apply the transform, you take the SCEV for the LCSSA PHI node, transform the AddRec to an Add (for example, {n,+,1} to n + strlen(p)), then use SCEVExpander to expand it.

Leveraging SCEV like this will make the transform a lot more flexible and easier to read.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1605

"BasicBlock::size()" should never be used as a threshold; it's sensitive to debug info.

[musman]

@efriedma Thanks for the review, I didn't think to use SCEV for this. I will modify the code as you suggested.

[shawnl]

This comment was removed by shawnl.

[musman]

Hi @efriedma, I am having some trouble understanding how to transform the AddRec to Add ({n,+,1} to n + strlen(p)). Should this be done with ScalarEvolution::getAddExpr, and then expanded? Thanks.

[efriedma]

I was thinking of something like that, yes. But thinking a bit more, maybe simpler to just use SCEVExpander on the base (e.g. "n") and emit the add directly in IR.

[xbolva00]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

108–109

Can you add similar statistic for strlen?

[musman]

Change to use SCEV instead of pattern match for strlen recognition.

[efriedma]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1609

I don't understand this bit about the precondition block; why are we not inserting the strlen call in the preheader?

1627

You probably want to check that the load is in address-space zero.

1641

for (auto *I : *LoopBody) {

1648

This checks there's at least one PHI, but not exactly one PHI.

1657

I don't understand what you're doing here.

Probably the simplest thing to do here would be to directly expand LCSSAPHI based on the result of strlen, instead of trying to dig into the exit block and find a subtraction operation.

[musman]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1657

I was thinking the subtraction operation was needed in order to do replaceAllUsesWith on it, is there a way to do that without needing the subtract?
Also, to expand the LCSSAPHI would you take the incoming value and check if it's an AddRec, then expand that?
Thanks again.

[efriedma]

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

1657

The actual output of the loop reflects the true count; you shouldn't need to dig through instructions outside it. (We can simplify the subtraction, if there is one, as a separate transform. I assume instcombine already handles this.)

To expand the LCSSAPHI, yes, you'd check if it's an appropriate addrec, then replace it with the sum of the addrec's base and the result of the strlen call.

llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp

 #include <utility>
 #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");
 
 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 &&
     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;
+  auto *EntryBI = dyn_cast<BranchInst>(PH->getTerminator());
+  if (!EntryBI || EntryBI->isConditional())
+    return false;
+
+  // It should have a precondition block where the generated strlen
+  // function call can be inserted.
+  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)
+    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 (BasicBlock::iterator I = LoopBody->begin(), E = LoopBody->end();
+       I != E;) {
+    Instruction *Inst = &*I++;
+    if (Inst->mayHaveSideEffects())
+      return false;
+  }
+
+  // Check that the loop exit block is valid:
+  // It needs to have one LCSSA Phi
+  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;
+
+  // Find the 'sub' instruction that computes the strlen. First we need
+  // the base pointer to check the operands of the 'sub'.
+  auto *BasePtrSCEV = dyn_cast<SCEVUnknown>(SE->getPointerBase(LoadEv));
+  Value *BasePtr = BasePtrSCEV->getValue();
+  auto *SubLHS = dyn_cast<PtrToIntInst>(LoopExitBB->getFirstNonPHIOrDbg());
+  if (!SubLHS || !SubLHS->hasOneUse())
+    return false;
+  auto *ResInst = dyn_cast<BinaryOperator>(SubLHS->user_back());
+  if (!ResInst || ResInst->getOpcode() != Instruction::Sub)
+    return false;
+  auto *SubRHS = dyn_cast<PtrToIntInst>(ResInst->getOperand(1));
+  if (!SubRHS || SubRHS->getPointerOperand() != BasePtr)
+    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());
+
+  const SCEV *StrBaseSCEV = LoadEv->getStart();
+  Value *Expanded = Expander.expandCodeFor(
+      StrBaseSCEV, Builder.getInt8PtrTy(LoopLoad->getPointerAddressSpace()),
+      PH->getTerminator());
+  EVC.add(Expanded);
+  EVC.commit();
+
+  Value *FuncCall = emitStrLen(Expanded, Builder, *DL, TLI);
+  Value *Strlen = Builder.CreateZExtOrTrunc(FuncCall, 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;
+  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;
 

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