This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] fold double reverses
Needs ReviewPublic

Authored by liuz on Apr 1 2023, 3:17 AM.

Details

Summary

LLVM's auto-vectorizer sometimes generates silly reverse loops, where a value is reversed by a shuffle, followed by some arithmetic, and then get reversed back.

For example, LLVM compiles this code sequence:

do {
  if (*--p == '.') *p = '_';
} while (p != name);

into

%1 = shufflevector <32 x i8> %0, poison, <31, 30, 29, 28, 27, ... 4, 3, 2, 1, 0>
%2 = icmp eq <32 x i8> %1, <46, 46, 46, 46, 46, ... 46, 46, 46, 46, 46>
%3 = shufflevector <32 x i1> %2, poison, <31, 30, 29, 28, 27, ... 4, 3, 2, 1, 0>

Obviously reverse shuffle %1 and %3 are redundant, and the sequence can be optimized into

%1 = icmp eq <32 x i8> %0, <46, 46, 46, 46, 46, ... 46, 46, 46, 46, 46>

This sequence is found in gzip's make_simple_name function.

This patch implements this rule in VectorCombine. Currently it works when %2 is a cmp instruction comparing with an splat constant. I will add other cases if this patch is approved.

The test cases in this patch are validated with Alive2.

This rewrite pattern is found by the Minotaur superoptimizer (https://github.com/minotaur-toolkit/minotaur).

Diff Detail

Event Timeline

liuz created this revision.Apr 1 2023, 3:17 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 1 2023, 3:17 AM
liuz requested review of this revision.Apr 1 2023, 3:17 AM
liuz edited the summary of this revision. (Show Details)Apr 1 2023, 3:24 AM
liuz updated this revision to Diff 510205.Apr 1 2023, 3:39 AM
liuz updated this revision to Diff 510206.Apr 1 2023, 3:42 AM
xbolva00 added inline comments.
llvm/lib/Transforms/Vectorize/VectorCombine.cpp
361 ↗(On Diff #510206)

dyn_cast without isa check?

Why is the test file called reverse-loop.ll when it doesn't involve loops?

llvm/lib/Transforms/Vectorize/VectorCombine.cpp
357 ↗(On Diff #510206)

Why does this need to be a splat? If its constant we can just constant fold with the outer shuffle

llvm/test/Transforms/VectorCombine/reverse-loop.ll
141 ↗(On Diff #510206)

Add negative test coverage that checks for length changing shuffles?

nikic added a subscriber: nikic.Apr 1 2023, 6:12 AM

As this is not a cost-model driven transform, it should be part of InstCombine, not VectorCombine.

liuz updated this revision to Diff 510255.Apr 1 2023, 11:30 AM
liuz retitled this revision from [VectorCombine] fold vector reverse loops to [InstCombine] fold double reverses.

Updated the patch according to comments

liuz added a comment.EditedApr 1 2023, 11:32 AM

As this is not a cost-model driven transform, it should be part of InstCombine, not VectorCombine.

Hi @nikic, thanks for the comment, I moved the code to InstCombine.

llvm/lib/Transforms/Vectorize/VectorCombine.cpp
357 ↗(On Diff #510206)

Thanks Simon for the comment, yes this does not need to be a splat, let me update this code to handle any constants.

liuz marked 2 inline comments as done.Apr 1 2023, 11:39 AM
liuz added inline comments.
llvm/lib/Transforms/Vectorize/VectorCombine.cpp
357 ↗(On Diff #510206)

Updated the patch to support general form (reverse (cmp (reverse x), y)) -> (cmp x, (reverse y)) and (reverse (cmp y, (reverse x))) -> (cmp (reverse y), x). This is exactly what Simon is suggesting in https://github.com/llvm/llvm-project/issues/48960#issuecomment-981040032 , except that this one takes cmpinst instead of binops, see the updated test cases. I'll add binops and other cases once this patch is approved.

361 ↗(On Diff #510206)

fixed. thanks.

llvm/test/Transforms/VectorCombine/reverse-loop.ll
141 ↗(On Diff #510206)

added.

liuz marked an inline comment as done.Apr 1 2023, 11:42 AM

Why is the test file called reverse-loop.ll when it doesn't involve loops?

Changed the test-cases's name to "vector-double-reverse.ll".

liuz added a comment.Apr 1 2023, 11:43 AM

All the new test cases are validated by Alive2.

liuz updated this revision to Diff 510277.Apr 1 2023, 4:18 PM

fixed the failing test case.

liuz updated this revision to Diff 510279.Apr 1 2023, 5:24 PM
junaire added a subscriber: junaire.Apr 1 2023, 7:02 PM
junaire added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp
2739

FWIW, we have m_ICmp

liuz added inline comments.Apr 1 2023, 7:06 PM
llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp
2739

I avoided m_ICmp because this code will support other type of instructions (Unary, Binary, Intrinsic, etc...) in the future.

craig.topper added inline comments.Apr 5 2023, 3:45 PM
llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp
2746

Can we inline this into the call to CmpInst::Create like we did with CI->getOpcode()?

2751

You can do

if ((RevX = dyn_cast<ShuffleVectorInst>(LHS)) &&
    RevX->hasOneUse() && RevX->isReverse())
2766

Why do we need to check for Constant here? Builder will constant fold.

2769

There's a version of CreateShuffleVector that only takes one Value and creates the Poison vector.

Though I wonder if we should just call Builder.CreateVectorReverse instead of copying the mask.

liuz updated this revision to Diff 523212.May 17 2023, 4:12 PM

rebase + solve comments

liuz marked 4 inline comments as done.May 17 2023, 4:15 PM

hey @craig.topper thanks for the comments. I've updated my patch, please kindly have a look again if you have time :) thanks.

liuz updated this revision to Diff 545330.Jul 28 2023, 9:37 PM

rebased

goldstein.w.n added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp
2770

Is there any different logic you need for binop that doesn't apply for cmp?

I was recently wondering if it would make sense for canEvaluateShuffled to detect cases where there's an input shuffle that cancels the starting shuffle.