This is an archive of the discontinued LLVM Phabricator instance.

Strlen loop idiom recognition
Needs ReviewPublic

Authored by musman on Jul 8 2020, 6:35 AM.
This revision needs review, but there are no reviewers specified.

Details

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

Diff Detail

Event Timeline

musman created this revision.Jul 8 2020, 6:35 AM

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.

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

shawnl added a subscriber: shawnl.Jul 8 2020, 11:38 PM
This comment was removed by shawnl.
musman added a comment.Aug 4 2020, 9:15 AM

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.

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 added inline comments.
llvm/lib/Transforms/Scalar/LoopIdiomRecognize.cpp
108–109

Can you add similar statistic for strlen?

musman updated this revision to Diff 286374.Aug 18 2020, 12:33 PM
musman edited the summary of this revision. (Show Details)
musman removed reviewers: lebedev.ri, nemanjai, hfinkel, sanjoy.
musman removed rG LLVM Github Monorepo as the repository for this revision.

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

efriedma added inline comments.Aug 18 2020, 12:50 PM
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 marked an inline comment as done.Aug 27 2020, 7:32 AM
musman added inline comments.
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 added inline comments.Aug 27 2020, 12:44 PM
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.

etiotto added a subscriber: etiotto.Sep 9 2020, 2:42 PM