[ValueTracking] Add rotate idiom to haveNoCommonBitsSet special cases (#122165)

An occasional idiom for rotation is "(A << B) + (A >> (BitWidth - B))".
Currently this is not well handled on targets

[ValueTracking] Add rotate idiom to haveNoCommonBitsSet special cases (#122165)

An occasional idiom for rotation is "(A << B) + (A >> (BitWidth - B))".
Currently this is not well handled on targets with native
funnel-shift/rotate support. Add a special case to haveNoCommonBitsSet
to ensure that the addition is converted to a disjoint or in InstCombine
so during instruction selection the idiom can be converted to an
efficient rotation implementation.

Proof: https://alive2.llvm.org/ce/z/WdCZsN

show more ...

[LLVM][IR] Teach constant integer binop folds about vector ConstantInts. (#115739)

The existing logic mostly works with the main changes being:
* Use getScalarSizeInBits instead of IntegerType::ge

[LLVM][IR] Teach constant integer binop folds about vector ConstantInts. (#115739)

The existing logic mostly works with the main changes being:
* Use getScalarSizeInBits instead of IntegerType::getBitWidth
* Use ConstantInt::get(Type* instead of ConstantInt::get(LLVMContext

show more ...

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

[IR] Remove support for shl constant expressions (#96037)

Remove support for shl constant expressions, as part of:
https://discourse.llvm.org/t/rfc-remove-most-constant-expressions/63179

[PatternMatch] Do not accept undef elements in m_AllOnes() and friends (#88217)

Change all the cstval_pred_ty based PatternMatch helpers (things like
m_AllOnes and m_Zero) to only allow poison elem

[PatternMatch] Do not accept undef elements in m_AllOnes() and friends (#88217)

Change all the cstval_pred_ty based PatternMatch helpers (things like
m_AllOnes and m_Zero) to only allow poison elements inside vector
splats, not undef elements.

Historically, we used to represent non-demanded elements in vectors
using undef. Nowadays, we use poison instead. As such, I believe that
support for undef in vector splats is no longer useful.

At the same time, while poison splat elements are pretty much always
safe to ignore, this is not generally the case for undef elements. We
have existing miscompiles in our tests due to this (see the
masked-merge-*.ll tests changed here) and it's easy to miss such cases
in the future, now that we write tests using poison instead of undef
elements.

I think overall, keeping support for undef elements no longer makes
sense, and we should drop it. Once this is done consistently, I think we
may also consider allowing poison in m_APInt by default, as doing that
change is much less risky than doing the same with undef.

This change involves a substantial amount of test changes. For most
tests, I've just replaced undef with poison, as I don't think there is
value in retaining both. For some tests (where the distinction between
undef and poison is important), I've duplicated tests.

show more ...

[InstCombine] Relax shamt assertion in fsh fold

Allow the result of the comparison to contain poison elements,
which happens if one of the elements in the input vector is
poison.

[InstCombine] Favour `CreateZExtOrTrunc` in `narrowFunnelShift` (NFC)

Use `CreateZExtOrTrunc`, reduce test and regenerate checks.

[InstCombine] Zero-extend shift amounts in narrow funnel shift ops

An issue arose when handling shift amounts while performing
narrowed funnel shifts simplification. Specifically, shift
amounts were

[InstCombine] Zero-extend shift amounts in narrow funnel shift ops

An issue arose when handling shift amounts while performing
narrowed funnel shifts simplification. Specifically, shift
amounts were incorrectly truncated when their type was
narrower than the target bit width. This has been addressed
by zero-extending `ShAmt` in such cases.

Fixes: https://github.com/llvm/llvm-project/issues/71463.

Proof: https://alive2.llvm.org/ce/z/5draKz.

show more ...

[InstCombine] Improve logic for adding flags to shift instructions.

Instead of relying on constant operands, use known bits to do the
computation.

Proofs: https://alive2.llvm.org/ce/z/M-aBnw

Diffe

[InstCombine] Improve logic for adding flags to shift instructions.

Instead of relying on constant operands, use known bits to do the
computation.

Proofs: https://alive2.llvm.org/ce/z/M-aBnw

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

show more ...

[test][InstCombine] Update some test cases to use opaque pointers

These tests cases were converted using the script at
https://gist.github.com/nikic/98357b71fd67756b0f064c9517b62a34

Differential Re

[test][InstCombine] Update some test cases to use opaque pointers

These tests cases were converted using the script at
https://gist.github.com/nikic/98357b71fd67756b0f064c9517b62a34

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

show more ...

[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 ...

[InstCombine] restrict funnel shift match to avoid miscompile

As noted in the post-commit discussion for:
https://reviews.llvm.org/rGabd7529625a73f405e40a63dcc446c41d51a219e

...that change exposed

[InstCombine] restrict funnel shift match to avoid miscompile

As noted in the post-commit discussion for:
https://reviews.llvm.org/rGabd7529625a73f405e40a63dcc446c41d51a219e

...that change exposed a logic hole that allows a miscompile
if the shift amount could exceed the narrow width:
https://alive2.llvm.org/ce/z/-i_CiM
https://alive2.llvm.org/ce/z/NaYz28

The restriction isn't necessary for a rotate (same operand for
both shifts), so we should adjust the matching for the shift
value as a follow-up enhancement:
https://alive2.llvm.org/ce/z/ahuuQb

show more ...

[InstCombine] add tests for funnel shift miscompile; NFC

[InstCombine] improve demanded bits analysis of left-shifted operand

If we don't demand high bits, then we also don't care about those
high bits of a left-shift operand regardless of shift amount.
I

[InstCombine] improve demanded bits analysis of left-shifted operand

If we don't demand high bits, then we also don't care about those
high bits of a left-shift operand regardless of shift amount.
I noticed the sext/trunc pattern in a motivating example.
It seems like there should be a low-bits with right-shift sibling,
but I haven't looked at that yet.

https://alive2.llvm.org/ce/z/JuS6jc
https://rise4fun.com/Alive/Trm (not sure how to use 'width' with Alive1)
https://alive2.llvm.org/ce/z/gRadbF

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

show more ...

[InstCombine] relax masking requirement for truncated funnel/rotate match

I was investigating a seemingly unrelated improvement in demanded
bits for shift-left, but that caused regressions on these

[InstCombine] relax masking requirement for truncated funnel/rotate match

I was investigating a seemingly unrelated improvement in demanded
bits for shift-left, but that caused regressions on these tests
because we were able to look through/eliminate the mask.

https://alive2.llvm.org/ce/z/Ztdr22

define i8 @src(i32 %x, i32 %y, i32 %shift) {
%and = and i32 %shift, 3
%conv = and i32 %x, 255
%shr = lshr i32 %conv, %and
%sub = sub i32 8, %and
%shl = shl i32 %y, %sub
%or = or i32 %shr, %shl
%conv2 = trunc i32 %or to i8
ret i8 %conv2
}

define i8 @tgt(i32 %x, i32 %y, i32 %shift) {
%x8 = trunc i32 %x to i8
%y8 = trunc i32 %y to i8
%shift8 = trunc i32 %shift to i8
%and = and i8 %shift8, 3
%conv2 = call i8 @llvm.fshr.i8(i8 %y8, i8 %x8, i8 %and)
ret i8 %conv2
}

declare i8 @llvm.fshr.i8(i8,i8,i8)

show more ...

[InstCombine] add tests for rotate/funnel; NFC

[InstCombine] Add support for zext(and(neg(amt),width-1)) rotate shift amount patterns

Alive2: https://alive2.llvm.org/ce/z/bCvvHd

[InstCombine] Add rotate tests where the shift amount is zero extended after masking

Revert rG25a97c3a43d7 - "[InstCombine] visitCallInst - retain undefs in vector funnel shift amounts"

This reverts commit 25a97c3a43d7bc469ec67dd4e901a507b9b11116.

We have other constant folds that

Revert rG25a97c3a43d7 - "[InstCombine] visitCallInst - retain undefs in vector funnel shift amounts"

This reverts commit 25a97c3a43d7bc469ec67dd4e901a507b9b11116.

We have other constant folds that fold undef funnel shift amounts to 0 - so we need to be consistent.

If we end up with regressions where we lose a splat shift amount pattern we'll have to investigate other canonicalizations, but matchFunnelShift currently protects us from that.

show more ...

[InstCombine] visitCallInst - retain undefs in vector funnel shift amounts

By always performing a modulo on the shift amount constants this was causing undef amounts being replaced with zero, meanin

[InstCombine] visitCallInst - retain undefs in vector funnel shift amounts

By always performing a modulo on the shift amount constants this was causing undef amounts being replaced with zero, meaning we were losing funnel shift by splat (with undef) patterns.

Tweaked the shift amount bounds check to support (passthrough) undefs, and use Constant::mergeUndefsWith to preserve the undefs after folding.

show more ...

[InstCombine] matchFunnelShift - add support for non-uniform vectors containing undefs.

Replace m_SpecificInt with m_APIntAllowUndef to matching splats containing undefs, then use ConstantExpr::merg

[InstCombine] matchFunnelShift - add support for non-uniform vectors containing undefs.

Replace m_SpecificInt with m_APIntAllowUndef to matching splats containing undefs, then use ConstantExpr::mergeUndefsWith to merge the undefs together in the result.

The undef funnel shift amounts are getting replaced with zero later on - I'll address this in a later patch, otherwise we lose potential shift by splat value patterns.

show more ...

[InstCombine] matchFunnelShift - fold or(shl(a,x),lshr(b,sub(bw,x))) -> fshl(a,b,x) iff x < bw (REAPPLIED)

If value tracking can confirm that a shift value is less than the type bitwidth then we can

[InstCombine] matchFunnelShift - fold or(shl(a,x),lshr(b,sub(bw,x))) -> fshl(a,b,x) iff x < bw (REAPPLIED)

If value tracking can confirm that a shift value is less than the type bitwidth then we can more confidently fold general or(shl(a,x),lshr(b,sub(bw,x))) patterns to a funnel/rotate intrinsic pattern without causing bad codegen regressions in the backend (see D89139).

Reapplied after the shift canonicalization in rG02295e6d1a15 which removed the need to flip the shift values.

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

show more ...

Revert rGb97093e520036f8 - "[InstCombine] matchFunnelShift - fold or(shl(a,x),lshr(b,sub(bw,x))) -> fshl(a,b,x) iff x < bw"

This reverts commit b97093e520036f88c5b39e572966f1c8c387661e.

Funnel shif

Revert rGb97093e520036f8 - "[InstCombine] matchFunnelShift - fold or(shl(a,x),lshr(b,sub(bw,x))) -> fshl(a,b,x) iff x < bw"

This reverts commit b97093e520036f88c5b39e572966f1c8c387661e.

Funnel shift argument commutation isn't working correctly

show more ...

[InstCombine] matchFunnelShift - fold or(shl(a,x),lshr(b,sub(bw,x))) -> fshl(a,b,x) iff x < bw

If value tracking can confirm that a shift value is less than the type bitwidth then we can more confid

[InstCombine] matchFunnelShift - fold or(shl(a,x),lshr(b,sub(bw,x))) -> fshl(a,b,x) iff x < bw

If value tracking can confirm that a shift value is less than the type bitwidth then we can more confidently fold general or(shl(a,x),lshr(b,sub(bw,x))) patterns to a funnel/rotate intrinsic pattern without causing bad codegen regressions in the backend (see D89139).

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

show more ...

[InstCombine] matchFunnelShift - support non-uniform constant vector shift amounts (PR46895)

Complete basic PR46895 fixes by refactoring D87452/D88402 to allow us to match non-uniform constant value

[InstCombine] matchFunnelShift - support non-uniform constant vector shift amounts (PR46895)

Complete basic PR46895 fixes by refactoring D87452/D88402 to allow us to match non-uniform constant values.

We still don't handle non-uniform vectors that contain undef elements, but that can wait until we have a decent generic mechanism for this.

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

show more ...