Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Phabricator shutdown timeline

[InstCombine] Make `isFreeToInvert` check recursively.
AbandonedPublic

Authored by goldstein.w.n on Mon, Aug 28, 9:28 PM.

Details

Summary

Some Instructions (select/min/max) are inverted by just inverting the
operands. So the answer of whether they are free to invert is really
just whether the operands are free to invert.

Diff Detail

Unit TestsFailed

TimeTest
70 msLinux x64 > LLVM.Transforms/LoopVectorize::reduction-inloop.ll
Script: -- : 'RUN: at line 2'; /var/lib/buildkite-agent/builds/linux-56-7f758798dd-v9p4k-1/llvm-project/phabricator-build/build/bin/opt < /var/lib/buildkite-agent/builds/linux-56-7f758798dd-v9p4k-1/llvm-project/phabricator-build/llvm/test/Transforms/LoopVectorize/reduction-inloop.ll -passes=loop-vectorize,dce,instcombine -force-vector-interleave=1 -force-vector-width=4 -prefer-inloop-reductions -S | /var/lib/buildkite-agent/builds/linux-56-7f758798dd-v9p4k-1/llvm-project/phabricator-build/build/bin/FileCheck /var/lib/buildkite-agent/builds/linux-56-7f758798dd-v9p4k-1/llvm-project/phabricator-build/llvm/test/Transforms/LoopVectorize/reduction-inloop.ll
150 msWindows x64 > LLVM.Transforms/LoopVectorize::reduction-inloop.ll
Script: -- : 'RUN: at line 2'; c:\ws\src\build\bin\opt.exe < C:\ws\src\llvm\test\Transforms\LoopVectorize\reduction-inloop.ll -passes=loop-vectorize,dce,instcombine -force-vector-interleave=1 -force-vector-width=4 -prefer-inloop-reductions -S | c:\ws\src\build\bin\filecheck.exe C:\ws\src\llvm\test\Transforms\LoopVectorize\reduction-inloop.ll

Event Timeline

goldstein.w.n created this revision.Mon, Aug 28, 9:28 PM
Herald added a project: Restricted Project. · View Herald TranscriptMon, Aug 28, 9:28 PM
Herald added a subscriber: StephenFan. · View Herald Transcript
goldstein.w.n requested review of this revision.Mon, Aug 28, 9:28 PM
Herald added a project: Restricted Project. · View Herald TranscriptMon, Aug 28, 9:28 PM
nikic added a comment.Tue, Aug 29, 3:32 AM

The change itself looks fine to me, but the test changes don't look particularly compelling...

llvm/test/Transforms/LoopVectorize/reduction-inloop.ll
1362

This looks like a regression?

goldstein.w.n added inline comments.Tue, Aug 29, 9:40 AM
llvm/test/Transforms/LoopVectorize/reduction-inloop.ll
1362

agreed. Will fix before proceeding.

goldstein.w.n added a comment.EditedTue, Aug 29, 2:01 PM

The change itself looks fine to me, but the test changes don't look particularly compelling...

Okay,

So the regression is fundementally because for i1 select we canonicalize:
select C, false, A -> select ~C, A, false
and
select C, A, true -> select ~C, true, A.
This is to put the select into logical and/or form which is necessary for
A LOT of simplifications.

I started a preliminary patch to only do the canonicalization if it wouldn't
add a new instruction and the test results look good (maybe 30-40 tests
save 1-5 instructions, no regressions). That being said, I think a large
part of the reason for this is the vast majority of our test cases are
very simple so we usually get away with a free canonicalzation, and most
of the cases we just don't canonicalize the tests are only a few instructions
long and aren't really banging and logical and/or patterns.

The easy solution here is to create the canonicalized version -> run
the simplifications -> if we simplify return that, otherwise pop canonicalized
version. But thats not really a good coding pattern.

The other approach is to go through all and/or logic and update it to
also recognize !and and !or.

Or maybe another reasonable possibility?
What do you think?

Edit: Personally feel like pushing/popping at the very least makes more
sense than creating known unnecessary instructions.

goldstein.w.n added a comment.EditedTue, Aug 29, 2:36 PM

The change itself looks fine to me, but the test changes don't look particularly compelling...

Okay,

So the regression is fundementally because for i1 select we canonicalize:
select C, false, A -> select ~C, A, false
and
select C, A, true -> select ~C, true, A.
This is to put the select into logical and/or form which is necessary for
A LOT of simplifications.

I started a preliminary patch to only do the canonicalization if it wouldn't
add a new instruction and the test results look good (maybe 30-40 tests
save 1-5 instructions, no regressions). That being said, I think a large
part of the reason for this is the vast majority of our test cases are
very simple so we usually get away with a free canonicalzation, and most
of the cases we just don't canonicalize the tests are only a few instructions
long and aren't really banging and logical and/or patterns.

The easy solution here is to create the canonicalized version -> run
the simplifications -> if we simplify return that, otherwise pop canonicalized
version. But thats not really a good coding pattern.

The other approach is to go through all and/or logic and update it to
also recognize !and and !or.

Or maybe another reasonable possibility?

Another thought it that even it

What do you think?

Edit: Personally feel like pushing/popping at the very least makes more
sense than creating known unnecessary instructions.

This actually isn't so easy.

The change itself looks fine to me, but the test changes don't look particularly compelling...

Okay,

So the regression is fundementally because for i1 select we canonicalize:
select C, false, A -> select ~C, A, false
and
select C, A, true -> select ~C, true, A.
This is to put the select into logical and/or form which is necessary for
A LOT of simplifications.

I started a preliminary patch to only do the canonicalization if it wouldn't
add a new instruction and the test results look good (maybe 30-40 tests
save 1-5 instructions, no regressions). That being said, I think a large
part of the reason for this is the vast majority of our test cases are
very simple so we usually get away with a free canonicalzation, and most
of the cases we just don't canonicalize the tests are only a few instructions
long and aren't really banging and logical and/or patterns.

The easy solution here is to create the canonicalized version -> run
the simplifications -> if we simplify return that, otherwise pop canonicalized
version. But thats not really a good coding pattern.

The other approach is to go through all and/or logic and update it to
also recognize !and and !or.

Or maybe another reasonable possibility?

Another thought is that even if it costs an extra instruction logical and/or form
is more canonical and can be cleaned up elsewhere (i.e at selectiondaglowering).

What do you think?

Edit: Personally feel like pushing/popping at the very least makes more
sense than creating known unnecessary instructions.

Went with making all the (and/or cmp0, cmp1) work on just components of comparison so we can just drop the canonicalization w.o losing the folds.

Allen added inline comments.Thu, Aug 31, 8:29 AM
llvm/include/llvm/Transforms/InstCombine/InstCombiner.h
263

does it make sense to restrict the condition of recursion call? then the case predicated_or_dominates_reduction will not be touched.

+    if (match(V,
+              m_Select(PatternMatch::m_Value(), m_Not(PatternMatch::m_Value(A)),
+                       m_Not(PatternMatch::m_Value(B)))) ||
+        match(V, m_MaxOrMin(m_Not(PatternMatch::m_Value(A)),
+                            m_Not(PatternMatch::m_Value(B)))))

Rebase (fixed regressions)

goldstein.w.n added inline comments.Thu, Aug 31, 6:39 PM
llvm/include/llvm/Transforms/InstCombine/InstCombiner.h
263

Think that somewhat defeats the purpose of the change.
Have D159327 and D159328 which hopefully should fix the regression.

goldstein.w.n abandoned this revision.Tue, Sep 19, 8:54 AM

Abandoning and resubmitting on GH.