# [InstCombine] Make `isFreeToInvert` check recursively.AbandonedPublic

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

# Details

Reviewers
 nikic RKSimon Allen
Commits
rGd01857803f35: [InstCombine] Make `isFreeToInvert` check recursively.
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

### Event Timeline

goldstein.w.n created this revision.Aug 28 2023, 9:28 PM
Herald added a project: Restricted Project. Aug 28 2023, 9:28 PM
Herald added a subscriber: StephenFan.
goldstein.w.n requested review of this revision.Aug 28 2023, 9:28 PM
Herald added a project: Restricted Project. Aug 28 2023, 9:28 PM
Herald added subscribers: llvm-commits, wangpc.
nikic added a comment.Aug 29 2023, 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.Aug 29 2023, 9:40 AM
llvm/test/Transforms/LoopVectorize/reduction-inloop.ll
1362

agreed. Will fix before proceeding.

goldstein.w.n added a comment.EditedAug 29 2023, 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.EditedAug 29 2023, 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.Aug 31 2023, 8:29 AM
llvm/include/llvm/Transforms/InstCombine/InstCombiner.h
273

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.Aug 31 2023, 6:39 PM
llvm/include/llvm/Transforms/InstCombine/InstCombiner.h
273

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.Sep 19 2023, 8:54 AM

Abandoning and resubmitting on GH.

This revision was landed with ongoing or failed builds.Mon, Nov 20, 3:59 PM