[LLVM][IR] Use splat syntax when printing Constant[Data]Vector. (#112548)

[InstCombine] Remove some of the complexity-based canonicalization (#91185)

The idea behind this canonicalization is that it allows us to handle less
patterns, because we know that some will be can

[InstCombine] Remove some of the complexity-based canonicalization (#91185)

The idea behind this canonicalization is that it allows us to handle less
patterns, because we know that some will be canonicalized away. This is
indeed very useful to e.g. know that constants are always on the right.

However, this is only useful if the canonicalization is actually
reliable. This is the case for constants, but not for arguments: Moving
these to the right makes it look like the "more complex" expression is
guaranteed to be on the left, but this is not actually the case in
practice. It fails as soon as you replace the argument with another
instruction.

The end result is that it looks like things correctly work in tests,
while they actually don't. We use the "thwart complexity-based
canonicalization" trick to handle this in tests, but it's often a
challenge for new contributors to get this right, and based on the
regressions this PR originally exposed, we clearly don't get this right
in many cases.

For this reason, I think that it's better to remove this complexity
canonicalization. It will make it much easier to write tests for
commuted cases and make sure that they are handled.

show more ...

[InstCombine] Simplify and/or by replacing operands with constants (#77231)

This patch tries to simplify `X | Y` by replacing occurrences of `Y` in
`X` with 0. Similarly, it tries to simplify `X &

[InstCombine] Simplify and/or by replacing operands with constants (#77231)

This patch tries to simplify `X | Y` by replacing occurrences of `Y` in
`X` with 0. Similarly, it tries to simplify `X & Y` by replacing
occurrences of `Y` in `X` with -1.

Alive2: https://alive2.llvm.org/ce/z/cNjDTR
Note: As the current implementation is too conservative in the one-use
checks, I cannot remove other existing hard-coded simplifications if
they involves more than two instructions (e.g, `A & ~(A ^ B) --> A &
B`).

Compile-time impact:
http://llvm-compile-time-tracker.com/compare.php?from=a085402ef54379758e6c996dbaedfcb92ad222b5&to=9d655c6685865ffce0ad336fed81228f3071bd03&stat=instructions%3Au

|stage1-O3|stage1-ReleaseThinLTO|stage1-ReleaseLTO-g|stage1-O0-g|stage2-O3|stage2-O0-g|stage2-clang|
|--|--|--|--|--|--|--|
|+0.01%|-0.00%|+0.00%|-0.02%|+0.01%|+0.02%|-0.01%|

Fixes #76554.

show more ...

[InstCombine] Check isGuaranteedNotToBeUndef in haveNoCommonBitsSetSpecialCases. (#74390)

It's not safe for InstCombine to add disjoint metadata when converting
Add to Or otherwise.

I've added n

[InstCombine] Check isGuaranteedNotToBeUndef in haveNoCommonBitsSetSpecialCases. (#74390)

It's not safe for InstCombine to add disjoint metadata when converting
Add to Or otherwise.

I've added noundef attribute to preserve existing test behavior.

show more ...

[InstCombine] Infer disjoint flag on Or instructions. (#72912)

The disjoint flag was recently added to IR in #72583

We already set it when we turn an add into an or. This patch sets it on Ors tha

[InstCombine] Infer disjoint flag on Or instructions. (#72912)

The disjoint flag was recently added to IR in #72583

We already set it when we turn an add into an or. This patch sets it on Ors that weren't converted from an Add.

show more ...

[InstCombine] remove stale test comment; NFC

[InstCombine] add support for multi-use Y of (X op Y) op Z --> (Y op Z) op X

For (X op Y) op Z --> (Y op Z) op X
we can still do transform when Y is multi-use. In D131356 limit it to one-use,
this p

[InstCombine] add support for multi-use Y of (X op Y) op Z --> (Y op Z) op X

For (X op Y) op Z --> (Y op Z) op X
we can still do transform when Y is multi-use. In D131356 limit it to one-use,
this patch remove this limit.

This is still not a complete solution, I add a todo test to show it.
In this case, X and Y are both multi use, we can't differentiate how to convert based on this.
But at least we don't make the code worse，and it can solve half the scenarios.

show more ...

[InstCombine] reassociate bitwise logic chains based on uses

(X op Y) op Z --> (Y op Z) op X

This isn't a complete solution (see TODO tests for possible refinements),
but it shows some nice wins an

[InstCombine] reassociate bitwise logic chains based on uses

(X op Y) op Z --> (Y op Z) op X

This isn't a complete solution (see TODO tests for possible refinements),
but it shows some nice wins and doesn't seem to cause any harm. I think
the most potential danger is from conflicting with other folds and causing
an infinite loop - that's the reason for avoiding patterns with constant
operands.

Alternatively, we could try this in the reassociate pass, but we would not
immediately see all of the logic folds that instcombine provides. I also
looked at improving ValueTracking's isImpliedCondition() (and we should
still add some enhancements there), but that would not work in general for
bitwise logic reduction.

The tests that reduce completely to 0/-1 are motivated by issue #56653.

Differential Revision: https://reviews.llvm.org/D131356

show more ...

[InstCombine] add tests for bitwise logic; NFC

[test] Use -passes=instcombine instead of -instcombine in lots of tests. NFC

Another step moving away from the deprecated syntax of specifying
pass pipeline in opt.

Differential Revision: https://r

[test] Use -passes=instcombine instead of -instcombine in lots of tests. NFC

Another step moving away from the deprecated syntax of specifying
pass pipeline in opt.

Differential Revision: https://reviews.llvm.org/D119081

show more ...

Revert "Temporarily Revert "Add basic loop fusion pass.""

The reversion apparently deleted the test/Transforms directory.

Will be re-reverting again.

llvm-svn: 358552

Revert rL333106 / D46814: [InstCombine] Fold unfolded masked merge pattern with variable mask!

In post-commit review, Eric Christopher notes that many
new MSan warnings are being observed with this

Revert rL333106 / D46814: [InstCombine] Fold unfolded masked merge pattern with variable mask!

In post-commit review, Eric Christopher notes that many
new MSan warnings are being observed with this patch.

The probable reason is: if 'y' is undef here and we could
evaluate it twice and get different results.
We can't increase the number of uses of a value.

llvm-svn: 333631

show more ...

[InstCombine] Fold unfolded masked merge pattern with variable mask!

Summary:
Finally fixes [[ https://bugs.llvm.org/show_bug.cgi?id=6773 | PR6773 ]].

Now that the backend is all done, we can final

[InstCombine] Fold unfolded masked merge pattern with variable mask!

Summary:
Finally fixes [[ https://bugs.llvm.org/show_bug.cgi?id=6773 | PR6773 ]].

Now that the backend is all done, we can finally fold it!

The canonical unfolded masked merge pattern is
```(x & m) | (y & ~m)```
There is a second, equivalent variant:
```(x | ~m) & (y | m)```
Only one of them (the or-of-and's i think) is canonical.
And if the mask is not a constant, we should fold it to:
```((x ^ y) & M) ^ y```

https://rise4fun.com/Alive/ndQw

Reviewers: spatel, craig.topper

Reviewed By: spatel

Subscribers: nicholas, RKSimon, llvm-commits

Differential Revision: https://reviews.llvm.org/D46814

llvm-svn: 333106

show more ...

[PatternMatch] Stabilize the matching order of commutative matchers

Summary:
Currently, we
1. match `LHS` matcher to the `first` operand of binary operator,
2. and then match `RHS` matcher to the `s

[PatternMatch] Stabilize the matching order of commutative matchers

Summary:
Currently, we
1. match `LHS` matcher to the `first` operand of binary operator,
2. and then match `RHS` matcher to the `second` operand of binary operator.
If that does not match, we swap the `LHS` and `RHS` matchers:
1. match `RHS` matcher to the `first` operand of binary operator,
2. and then match `LHS` matcher to the `second` operand of binary operator.

This works ok.
But it complicates writing of commutative matchers, where one would like to match
(`m_Value()`) the value on one side, and use (`m_Specific()`) it on the other side.

This is additionally complicated by the fact that `m_Specific()` stores the `Value *`,
not `Value **`, so it won't work at all out of the box.

The last problem is trivially solved by adding a new `m_c_Specific()` that stores the
`Value **`, not `Value *`. I'm choosing to add a new matcher, not change the existing
one because i guess all the current users are ok with existing behavior,
and this additional pointer indirection may have performance drawbacks.
Also, i'm storing pointer, not reference, because for some mysterious-to-me reason
it did not work with the reference.

The first one appears trivial, too.
Currently, we
1. match `LHS` matcher to the `first` operand of binary operator,
2. and then match `RHS` matcher to the `second` operand of binary operator.
If that does not match, we swap the ~~`LHS` and `RHS` matchers~~ **operands**:
1. match ~~`RHS`~~ **`LHS`** matcher to the ~~`first`~~ **`second`** operand of binary operator,
2. and then match ~~`LHS`~~ **`RHS`** matcher to the ~~`second`~ **`first`** operand of binary operator.

Surprisingly, `$ ninja check-llvm` still passes with this.
But i expect the bots will disagree..

The motivational unittest is included.
I'd like to use this in D45664.

Reviewers: spatel, craig.topper, arsenm, RKSimon

Reviewed By: craig.topper

Subscribers: xbolva00, wdng, llvm-commits

Differential Revision: https://reviews.llvm.org/D45828

llvm-svn: 331085

show more ...

[InstCombine][NFC] Regenerate checks in and-or-not.ll

llvm-svn: 330994

[InstCombine] Fold (a | b) ^ (~a | ~b) --> ~(a ^ b) and (a & b) ^ (~a & ~b) --> ~(a ^ b)

Summary:
I came across this while thinking about what would happen if one of the operands in this xor pattern

[InstCombine] Fold (a | b) ^ (~a | ~b) --> ~(a ^ b) and (a & b) ^ (~a & ~b) --> ~(a ^ b)

Summary:
I came across this while thinking about what would happen if one of the operands in this xor pattern was itself a inverted (A & ~B) ^ (~A & B)-> (A^B).

The patterns here assume that the (~a | ~b) will be demorganed to ~(a & b) first. Though I wonder if there's a multiple use case that would prevent the demorgan.

Reviewers: spatel

Reviewed By: spatel

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D34870

llvm-svn: 306967

show more ...

fix trivial typos, NFC

llvm-svn: 306808

[InstCombine] Add test cases to demonstrate failure to fold (a | b) ^ (~a | ~b) --> ~(a ^ b) and its commuted variants.

llvm-svn: 306801

[InstCombine] In foldXorToXor, move the commutable matcher from the LHS match to the RHS match. No meaningful change intended.

There are two conditions ORed here with similar checks and each contain

[InstCombine] In foldXorToXor, move the commutable matcher from the LHS match to the RHS match. No meaningful change intended.

There are two conditions ORed here with similar checks and each contain two matches that must be true for the if to succeed. With the commutable match on the first half of the OR then both ifs basically have the same first part and only the second part distinguishs. With this change we move the commutable match to second half and make the first half unique.

This caused some tests to change because we now produce a commuted result, but this shouldn't matter in practice.

llvm-svn: 306800

show more ...

[InstCombine] Add one use checks to or/and->xnor folding

If the components of the and/or had multiple uses, this transform created an additional instruction.

This patch makes sure we remove one of

[InstCombine] Add one use checks to or/and->xnor folding

If the components of the and/or had multiple uses, this transform created an additional instruction.

This patch makes sure we remove one of the components.

Differential Revision: https://reviews.llvm.org/D34498

llvm-svn: 306027

show more ...

[InstCombine] Add test cases to demonstrate that and->xnor and or->xnor folding can create more instructions than it removed when there are multiple uses. NFC

llvm-svn: 305985

[InstCombine] consolidate tests for DeMorgan folds; NFC

I'm proposing to add tests and change behavior in D32665.

llvm-svn: 301774

[InstCombine] fix matcher to bind to specific operand (PR32830)

Matching any random value would be very wrong:
https://bugs.llvm.org/show_bug.cgi?id=32830

llvm-svn: 301594

[InstCombine] add/move folds for [not]-xor

We handled all of the commuted variants for plain xor already,
although they were scattered around and sometimes folded less
efficiently using distributive

[InstCombine] add/move folds for [not]-xor

We handled all of the commuted variants for plain xor already,
although they were scattered around and sometimes folded less
efficiently using distributive laws. We had no folds for not-xor.

Handling all of these patterns consistently is part of trying to
reinstate:
https://reviews.llvm.org/rL300977

llvm-svn: 301144

show more ...

[InstCombine] add tests for not-xor and remove redundant tests; NFC

llvm-svn: 301140