[ValueTracking] Handle nonnull attributes at callsite (#124908)

Alive2: https://alive2.llvm.org/ce/z/yJfskv
Closes https://github.com/llvm/llvm-project/issues/124540.

[ValueTracking] Fix bug of using wrong condition for deducing KnownBits (#124481)

- **[ValueTracking] Add test for issue 124275**
- **[ValueTracking] Fix bug of using wrong condition for deducing

[ValueTracking] Fix bug of using wrong condition for deducing KnownBits (#124481)

- **[ValueTracking] Add test for issue 124275**
- **[ValueTracking] Fix bug of using wrong condition for deducing
KnownBits**

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

Bug was introduced by https://github.com/llvm/llvm-project/pull/114689

Now that computeKnownBits supports breaking out of recursive Phi
nodes, `IncValue` can be an operand of a different Phi than `P`. This
breaks the previous assumptions we had when using the possibly
condition at `CxtI` to constrain `IncValue`.

show more ...

[ValueTracking] Pass changed predicate `SignedLPred` to `isImpliedByMatchingCmp` (#124271)

Fixes #124267.

Since we are using the new predicate, we should also update the
parameters of `isImplied

[ValueTracking] Pass changed predicate `SignedLPred` to `isImpliedByMatchingCmp` (#124271)

Fixes #124267.

Since we are using the new predicate, we should also update the
parameters of `isImpliedByMatchingCmp`.

show more ...

[NFC][DebugInfo] Use iterator-flavour getFirstNonPHI at many call-sites (#123737)

As part of the "RemoveDIs" project, BasicBlock::iterator now carries a
debug-info bit that's needed when getFirstNo

[NFC][DebugInfo] Use iterator-flavour getFirstNonPHI at many call-sites (#123737)

As part of the "RemoveDIs" project, BasicBlock::iterator now carries a
debug-info bit that's needed when getFirstNonPHI and similar feed into
instruction insertion positions. Call-sites where that's necessary were
updated a year ago; but to ensure some type safety however, we'd like to
have all calls to getFirstNonPHI use the iterator-returning version.

This patch changes a bunch of call-sites calling getFirstNonPHI to use
getFirstNonPHIIt, which returns an iterator. All these call sites are
where it's obviously safe to fetch the iterator then dereference it. A
follow-up patch will contain less-obviously-safe changes.

We'll eventually deprecate and remove the instruction-pointer
getFirstNonPHI, but not before adding concise documentation of what
considerations are needed (very few).

---------

Co-authored-by: Stephen Tozer <Melamoto@gmail.com>

show more ...

[ValueTracking] Handle recursive select/PHI in ComputeKnownBits (#114689)


Finish porting #114008 to `KnownBits` (Follow up to #113707).

[ValueTracking] Return `poison` for zero-sized types (#122647)

Return `poison` for zero-sized types in `isBitwiseValue`.

[ValueTracking] Provide getUnderlyingObjectAggressive fallback (#123019)

This callsite assumes `getUnderlyingObjectAggressive` returns a non-null
pointer:

https://github.com/llvm/llvm-project/bl

[ValueTracking] Provide getUnderlyingObjectAggressive fallback (#123019)

This callsite assumes `getUnderlyingObjectAggressive` returns a non-null
pointer:

https://github.com/llvm/llvm-project/blob/273a94b3d5a78cd9122c7b3bbb5d5a87147735d2/llvm/lib/Transforms/IPO/FunctionAttrs.cpp#L124

But it can return null when there are cycles in the value chain so there
is no more `Worklist` item anymore to explore, in which case it just
returns `Object` at the end of the function without ever setting it:
https://github.com/llvm/llvm-project/blob/9b5857a68381652dbea2a0c9efa734b6c4cf38c9/llvm/lib/Analysis/ValueTracking.cpp#L6866-L6867
https://github.com/llvm/llvm-project/blob/9b5857a68381652dbea2a0c9efa734b6c4cf38c9/llvm/lib/Analysis/ValueTracking.cpp#L6889

`getUnderlyingObject` does not seem to return null either judging by
looking at its code and its callsites, so I think it is not likely to be
the author's intention that `getUnderlyingObjectAggressive` returns
null.

So this checks whether `Object` is null at the end, and if so, falls
back to the original first value.

---

The test case here was reduced by bugpoint and further reduced manually,
but I find it hard to reduce it further.

To trigger this bug, the memory operation should not be reachable from
the entry BB, because the `phi`s should form a cycle without introducing
another value from the entry. I tried a minimal `phi` cycle with three
BBs (entry BB + two BBs in a cycle), but it was skipped here:
https://github.com/llvm/llvm-project/blob/273a94b3d5a78cd9122c7b3bbb5d5a87147735d2/llvm/lib/Transforms/IPO/FunctionAttrs.cpp#L121-L122
To get the result that's not `ModRefInfo::NoModRef`, the length of `phi`
chain needed to be greater than the `MaxLookup` value set in this
function:

https://github.com/llvm/llvm-project/blob/02403f4e450b86d93197dd34045ff40a34b21494/llvm/lib/Analysis/BasicAliasAnalysis.cpp#L744

But just lengthening the `phi` chain to 8 didn't trigger the same error
in `getUnderlyingObjectAggressive` because `getUnderlyingObject` here
passes through a single-chain `phi`s so not all `phi`s end up in
`Visited`:

https://github.com/llvm/llvm-project/blob/9b5857a68381652dbea2a0c9efa734b6c4cf38c9/llvm/lib/Analysis/ValueTracking.cpp#L6863

So I just submit here the smallest test case I managed to create.

---

Fixes #117308 and fixes #122166.

show more ...

[ValueTracking] Squash compile-time regression from 66badf2 (#122700)

66badf2 (VT: teach a special-case optz about samesign) introduced a
compile-time regression due to the use of CmpPredicate::get

[ValueTracking] Squash compile-time regression from 66badf2 (#122700)

66badf2 (VT: teach a special-case optz about samesign) introduced a
compile-time regression due to the use of CmpPredicate::getMatching,
which is unnecessarily inefficient. Introduce
CmpPredicate::getPreferredSignedPredicate, which alleviates the
inefficiency problem and squashes the compile-time regression.

show more ...

IR: introduce ICmpInst::isImpliedByMatchingCmp (#122597)

Create an abstraction over isImplied{True,False}ByMatchingCmp to
faithfully communicate the result of both functions, cleaning up code in
c

IR: introduce ICmpInst::isImpliedByMatchingCmp (#122597)

Create an abstraction over isImplied{True,False}ByMatchingCmp to
faithfully communicate the result of both functions, cleaning up code in
callsites. While at it, fix a bug in the implied-false version of the
function, which was inadvertedenly dropping samesign information.

show more ...

VT: teach a special-case optz about samesign (#122590)

There is a narrow special-case in isImpliedCondICmps that can benefit
from being taught about samesign. Since it costs us nothing to implement

VT: teach a special-case optz about samesign (#122590)

There is a narrow special-case in isImpliedCondICmps that can benefit
from being taught about samesign. Since it costs us nothing to implement
it, teach it about samesign, for completeness. This patch marks the
completion of the effort to teach ValueTracking about samesign.

show more ...

[ValueTracking] Take into account whether zero is poison when computing CR for `ct{t,l}z` (#122548)

VT: teach isImpliedCondMatchingOperands about samesign (#122474)

Move isImplied{True,False}ByMatchingCmp from CmpInst to ICmpInst, so
that it can operate on CmpPredicate instead of CmpInst::Predica

VT: teach isImpliedCondMatchingOperands about samesign (#122474)

Move isImplied{True,False}ByMatchingCmp from CmpInst to ICmpInst, so
that it can operate on CmpPredicate instead of CmpInst::Predicate, and
teach it about samesign. There are two callers of this function, and we
choose to migrate the one in ValueTracking, namely
isImpliedCondMatchingOperands to CmpPredicate, hence teaching it about
samesign, with visible test impact.

show more ...

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

VT: teach implied-cond-cr about samesign (#122447)

Teach isImpliedCondCommonOperandWithCR about samesign, noting that the
only case we need to handle is when exactly one of the icmps have
samesign.

VT: teach isImpliedCondOperands about samesign (#120263)

isImpliedCondICmps() and its callers in ValueTracking can greatly
benefit from being taught about samesign. As a first step, teach one
call

VT: teach isImpliedCondOperands about samesign (#120263)

isImpliedCondICmps() and its callers in ValueTracking can greatly
benefit from being taught about samesign. As a first step, teach one
caller, namely isImpliedCondOperands(). Very minimal changes are
required for this, as CmpPredicate::getMatching() does most of the work.

show more ...

[ValueTracking] Move `getFlippedStrictnessPredicateAndConstant` into ValueTracking. NFC. (#122064)

Needed by https://github.com/llvm/llvm-project/pull/121958.

[ValueTracking] Fix a bug for signed min-max clamping (#121206)

Correctly handle the case where the clamp is over the full range.
This fixes an issue introduced in #121206.

[ValueTracking] Improve KnownBits for signed min-max clamping (#120576)

A signed min-max clamp is the sequence of smin and smax intrinsics,
which constrain a signed value into the range: smin <= va

[ValueTracking] Improve KnownBits for signed min-max clamping (#120576)

A signed min-max clamp is the sequence of smin and smax intrinsics,
which constrain a signed value into the range: smin <= value <= smax.
The patch improves the calculation of KnownBits for a value subjected to
the signed clamping.

show more ...

[InstCombine] Widen Sel width after Cmp to generate Max/Min intrinsics. (#118932)

When Sel(Cmp) are in different integer type,

From: (K and N mean width, K < N; a and b are src operands.)
bN =

[InstCombine] Widen Sel width after Cmp to generate Max/Min intrinsics. (#118932)

When Sel(Cmp) are in different integer type,

From: (K and N mean width, K < N; a and b are src operands.)
bN = Ext(bK)
cond = Cmp(aN, bN)
aK = Trunc aN
retK = Sel(cond, aK, bK)
To:
bN = Ext(bK)
cond = Cmp(aN, bN)
retN = Sel(cond, aN, bN)
retK = Trunc retN

Though Sel's operands width becomes larger, the benefit
of making type width in Sel the same as Cmp, is for combing
to max/min intrinsics, and also better performance for SIMD
instructions.
References of correctness: https://alive2.llvm.org/ce/z/Y4Kegm
https://alive2.llvm.org/ce/z/qFtjtR
Reference of generated code comparision:
https://gcc.godbolt.org/z/o97svGvYM
https://gcc.godbolt.org/z/59Ynj91ov

show more ...

PatternMatch: migrate to CmpPredicate (#118534)

With the introduction of CmpPredicate in 51a895a (IR: introduce struct
with CmpInst::Predicate and samesign), PatternMatch is one of the first
key p

PatternMatch: migrate to CmpPredicate (#118534)

With the introduction of CmpPredicate in 51a895a (IR: introduce struct
with CmpInst::Predicate and samesign), PatternMatch is one of the first
key pieces of infrastructure that must be updated to match a CmpInst
respecting samesign information. Implement this change to Cmp-matchers.

This is a preparatory step in migrating the codebase over to
CmpPredicate. Since we no functional changes are desired at this stage,
we have chosen not to migrate CmpPredicate::operator==(CmpPredicate)
calls to use CmpPredicate::getMatching(), as that would have visible
impact on tests that are not yet written: instead, we call
CmpPredicate::operator==(Predicate), preserving the old behavior, while
also inserting a few FIXME comments for follow-ups.

show more ...

[ValueTracking] Add missing operand checks in `computeKnownFPClassFromCond` (#119579)

After https://github.com/llvm/llvm-project/pull/118257, we may call
`computeKnownFPClassFromCond` with unrelate

[ValueTracking] Add missing operand checks in `computeKnownFPClassFromCond` (#119579)

After https://github.com/llvm/llvm-project/pull/118257, we may call
`computeKnownFPClassFromCond` with unrelated conditions. Then
miscompilations may occur due to a lack of operand checks.

This bug was introduced by
https://github.com/llvm/llvm-project/commit/d2404ea6ced5fce9442260bde08a02d607fdd50d
and https://github.com/llvm/llvm-project/pull/80740. However, the
miscompilation couldn't have happened before
https://github.com/llvm/llvm-project/pull/118257, because we only added
related conditions to `DomConditionCache/AssumptionCache`.

Fix the miscompilation reported in
https://github.com/llvm/llvm-project/pull/118257#issuecomment-2536182166.

show more ...

IR: introduce struct with CmpInst::Predicate and samesign (#116867)

Introduce llvm::CmpPredicate, an abstraction over a floating-point
predicate, and a pack of an integer predicate with samesign in

IR: introduce struct with CmpInst::Predicate and samesign (#116867)

Introduce llvm::CmpPredicate, an abstraction over a floating-point
predicate, and a pack of an integer predicate with samesign information,
in order to ease extending large portions of the codebase that take a
CmpInst::Predicate to respect the samesign flag.

We have chosen to demonstrate the utility of this new abstraction by
migrating parts of ValueTracking, InstructionSimplify, and InstCombine
from CmpInst::Predicate to llvm::CmpPredicate. There should be no
functional changes, as we don't perform any extra optimizations with
samesign in this patch, or use CmpPredicate::getMatching.

The design approach taken by this patch allows for unaudited callers of
APIs that take a llvm::CmpPredicate to silently drop the samesign
information; it does not pose a correctness issue, and allows us to
migrate the codebase piece-wise.

show more ...

[ValueTracking] Handle and/or of conditions in `computeKnownFPClassFromContext` (#118257)

Fix a typo introduced by
https://github.com/llvm/llvm-project/pull/83161.
This patch also supports decompo

[ValueTracking] Handle and/or of conditions in `computeKnownFPClassFromContext` (#118257)

Fix a typo introduced by
https://github.com/llvm/llvm-project/pull/83161.
This patch also supports decomposition of and/or expressions in
`computeKnownFPClassFromContext`.
Compile-time improvement:
http://llvm-compile-time-tracker.com/compare.php?from=688bb432c4b618de69a1d0e7807077a22f15762a&to=07493fc354b686f0aca79d6f817091a757bd7cd5&stat=instructions:u

show more ...

[InstCombine] Fold `X Pred C2 ? X BOp C1 : C2 BOp C1` to `min/max(X, C2) BOp C1` (#116888)

Fixes #82414.

General Proof: https://alive2.llvm.org/ce/z/ERjNs4
Proof for Tests: https://alive2.llvm.

[InstCombine] Fold `X Pred C2 ? X BOp C1 : C2 BOp C1` to `min/max(X, C2) BOp C1` (#116888)

Fixes #82414.

General Proof: https://alive2.llvm.org/ce/z/ERjNs4
Proof for Tests: https://alive2.llvm.org/ce/z/K-934G

This PR transforms `select` instructions of the form `select (Cmp X C1)
(BOp X C2) C3` to `BOp (min/max X C1) C2` iff `C3 == BOp C1 C2`.

This helps in eliminating a noop loop in
https://github.com/rust-lang/rust/issues/123845 but does not improve
optimizations.

show more ...

[Analysis] atan2: isTriviallyVectorizable; add to massv and accelerate veclibs (#113637)

This change is part of this proposal:
https://discourse.llvm.org/t/rfc-all-the-math-intrinsics/78294

- Re

[Analysis] atan2: isTriviallyVectorizable; add to massv and accelerate veclibs (#113637)

This change is part of this proposal:
https://discourse.llvm.org/t/rfc-all-the-math-intrinsics/78294

- Return true for atan2 from isTriviallyVectorizable
- Add atan2 to VecFuncs.def for massv and accelerate libraries.
- Add atan2 to hasOptimizedCodeGen
- Add atan2 support in llvm/lib/Analysis/ValueTracking.cpp
llvm::getIntrinsicForCallSite and update vectorization tests
- Add atan2 name check to isLoweredToCall in
llvm/include/llvm/Analysis/TargetTransformInfoImpl.h
- Note: there's no test coverage for these names in isLoweredToCall, except that Transforms/TailCallElim/inf-recursion.ll is impacted by the "fabs" case

Thanks to @jroelofs for the atan2 accelerate veclib and associated test
additions, plus the hasOptimizedCodeGen addition.

Part of: Implement the atan2 HLSL Function #70096.

show more ...