[InstCombine] Make `isFreeToInvert` check recursively.

[goldstein.w.n]

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.

[nikic]

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]

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

1362

agreed. Will fix before proceeding.

[goldstein.w.n]

In D159056#4624311, @nikic wrote:

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]

In D159056#4626378, @goldstein.w.n wrote:

In D159056#4624311, @nikic wrote:

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.

In D159056#4626378, @goldstein.w.n wrote:

In D159056#4624311, @nikic wrote:

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]

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)))))

[goldstein.w.n]

Rebase (fixed regressions)

[goldstein.w.n]

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]

Rebase

[goldstein.w.n]

Rebase

[goldstein.w.n]

Abandoning and resubmitting on GH.