[ValueTracking] Interpret GEPs as a series of adds multiplied by the related scaling factor

Prior to this patch, computeKnownBits would only try to deduce trailing zeros
bits for getelementptrs. Thi

[ValueTracking] Interpret GEPs as a series of adds multiplied by the related scaling factor

Prior to this patch, computeKnownBits would only try to deduce trailing zeros
bits for getelementptrs. This patch adds the logic to treat geps as a series
of add * scaling factor.

Thanks to this patch, using a gep or performing an address computation
directly "by hand" (ptrtoint followed by adds and mul followed by inttoptr)
offers the same computeKnownBits information.

Previously, the "by hand" approach would have given more information.

This is related to https://llvm.org/PR47241.

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

show more ...

[ValueTracking] Use assume's noundef operand bundle

This patch updates `isGuaranteedNotToBeUndefOrPoison` to use `llvm.assume`'s `noundef` operand bundle.

Reviewed By: jdoerfert

Differential Revis

[ValueTracking] Use assume's noundef operand bundle

This patch updates `isGuaranteedNotToBeUndefOrPoison` to use `llvm.assume`'s `noundef` operand bundle.

Reviewed By: jdoerfert

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

show more ...

[unittests] Add a few tests for computeKnownBits with ranges

These tests make sure that the range information is properly
understood during computeKnownBits analysis.

NFC

Differential Revision: ht

[unittests] Add a few tests for computeKnownBits with ranges

These tests make sure that the range information is properly
understood during computeKnownBits analysis.

NFC

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

show more ...

[ValueTracking] Fix analyses to update CxtI to be phi's incoming edges' terminators

It was mentioned that D88276 that when a phi node is visited, terminators at their incoming edges should be used f

[ValueTracking] Fix analyses to update CxtI to be phi's incoming edges' terminators

It was mentioned that D88276 that when a phi node is visited, terminators at their incoming edges should be used for CtxI.
This is a patch that makes two functions (ComputeNumSignBitsImpl, isGuaranteedNotToBeUndefOrPoison) to do so.

Reviewed By: nikic

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

show more ...

[ValueTracking] Check uses of Argument if it is given to isGuaranteedNotToBeUndefOrPoison

This is a patch that allows isGuaranteedNotToBeUndefOrPoison to return more precise result
when an argument

[ValueTracking] Check uses of Argument if it is given to isGuaranteedNotToBeUndefOrPoison

This is a patch that allows isGuaranteedNotToBeUndefOrPoison to return more precise result
when an argument is given, by looking through its uses at the entry block (and following blocks as well, if it is checking poison only).

This is useful when there is a function call with noundef arguments at the entry block.

Reviewed By: nikic

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

show more ...

[ValueTracking] isKnownNonZero, computeKnownBits for freeze

This implements support for isKnownNonZero, computeKnownBits when freeze is involved.

```
br (x != 0), BB1, BB2
BB1:
y = freeze x
```

[ValueTracking] isKnownNonZero, computeKnownBits for freeze

This implements support for isKnownNonZero, computeKnownBits when freeze is involved.

```
br (x != 0), BB1, BB2
BB1:
y = freeze x
```

In the above program, we can say that y is non-zero. The reason is as follows:

(1) If x was poison, `br (x != 0)` raised UB
(2) If x was fully undef, the branch again raised UB
(3) If x was non-zero partially undef, say `undef | 1`, `freeze x` will return a nondeterministic value which is also non-zero.
(4) If x was just a concrete value, it is trivial

Reviewed By: nikic

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

show more ...

[ValueTracking] Add UndefOrPoison/Poison-only version of relevant functions

This patch adds isGuaranteedNotToBePoison and programUndefinedIfUndefOrPoison.

isGuaranteedNotToBePoison will be used at

[ValueTracking] Add UndefOrPoison/Poison-only version of relevant functions

This patch adds isGuaranteedNotToBePoison and programUndefinedIfUndefOrPoison.

isGuaranteedNotToBePoison will be used at D75808. The latter function is used at isGuaranteedNotToBePoison.

Reviewed By: nikic

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

show more ...

[ValueTracking] Replace recursion with Worklist

Now findAllocaForValue can handle nontrivial phi cycles.

[NFC][ValueTracking] Add OffsetZero into findAllocaForValue

For StackLifetime after finding alloca we need to check that
values ponting to the begining of alloca.

Reviewed By: eugenis

Differential

[NFC][ValueTracking] Add OffsetZero into findAllocaForValue

For StackLifetime after finding alloca we need to check that
values ponting to the begining of alloca.

Reviewed By: eugenis

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

show more ...

[NFC][ValueTracking] Cleanup a test

[NFC][ValueTracking] Fix typo in test

[ValueTracking] Support select in findAllocaForValue

[NFC] Add unittests for findAllocaForValue

Fix ValueTrackingTest.cpp to use pair instead of tuple

[ValueTracking] Add canCreateUndefOrPoison & let canCreatePoison use Operator

This patch
- adds `canCreateUndefOrPoison`
- refactors `canCreatePoison` so it can deal with constantexprs

`canCreateUn

[ValueTracking] Add canCreateUndefOrPoison & let canCreatePoison use Operator

This patch
- adds `canCreateUndefOrPoison`
- refactors `canCreatePoison` so it can deal with constantexprs

`canCreateUndefOrPoison` will be used at D83926.

Reviewed By: nikic, jdoerfert

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

show more ...

[ValueTracking] Use assumptions in computeConstantRange.

This patch updates computeConstantRange to optionally take an assumption
cache as argument and use the available assumptions to limit the ran

[ValueTracking] Use assumptions in computeConstantRange.

This patch updates computeConstantRange to optionally take an assumption
cache as argument and use the available assumptions to limit the range
of the result.

Currently this is limited to assumptions that are comparisons.

Reviewers: reames, nikic, spatel, jdoerfert, lebedev.ri

Reviewed By: nikic

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

show more ...

[ValueTracking] Fix computeKnownBits() with bitwidth-changing ptrtoint

computeKnownBitsFromAssume() currently asserts if m_V matches a
ptrtoint that changes the bitwidth. Because InstCombine
canonic

[ValueTracking] Fix computeKnownBits() with bitwidth-changing ptrtoint

computeKnownBitsFromAssume() currently asserts if m_V matches a
ptrtoint that changes the bitwidth. Because InstCombine
canonicalizes ptrtoint instructions to use explicit zext/trunc,
we never ran into the issue in practice. I'm adding unit tests,
as I don't know if this can be triggered via IR anywhere.

Fix this by calling anyextOrTrunc(BitWidth) on the computed
KnownBits. Note that we are going from the KnownBits of the
ptrtoint result to the KnownBits of the ptrtoint operand,
so we need to truncate if the ptrtoint zexted and anyext if
the ptrtoint truncated.

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

show more ...

[ValueTracking] Let propagatesPoison support binops/unaryops/cast/etc.

Summary:
This patch makes propagatesPoison be more accurate by returning true on
more bin ops/unary ops/casts/etc.

The changed

[ValueTracking] Let propagatesPoison support binops/unaryops/cast/etc.

Summary:
This patch makes propagatesPoison be more accurate by returning true on
more bin ops/unary ops/casts/etc.

The changed test in ScalarEvolution/nsw.ll was introduced by
https://github.com/llvm/llvm-project/commit/a19edc4d15b0dae0210b90615775edd76f021008 .
IIUC, the goal of the tests is to show that iv.inc's SCEV expression still has
no-overflow flags even if the loop isn't in the wanted form.
It becomes more accurate with this patch, so think this is okay.

Reviewers: spatel, lebedev.ri, jdoerfert, reames, nikic, sanjoy

Reviewed By: spatel, nikic

Subscribers: regehr, nlopes, efriedma, fhahn, javed.absar, llvm-commits, hiraditya

Tags: #llvm

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

show more ...

[ValueTracking] Convert test to unit test (NFC)

Test this directly, rather than going through InstSimplify.

[CallSite removal][ValueTracking] Use CallBase instead of ImmutableCallSite for getIntrinsicForCallSite. NFC

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

[ValueTracking] Implement canCreatePoison

Summary:
This PR adds `canCreatePoison(Instruction *I)` which returns true if `I` can generate poison from non-poison
operands.

Reviewers: spatel, nikic, l

[ValueTracking] Implement canCreatePoison

Summary:
This PR adds `canCreatePoison(Instruction *I)` which returns true if `I` can generate poison from non-poison
operands.

Reviewers: spatel, nikic, lebedev.ri

Reviewed By: spatel

Subscribers: hiraditya, llvm-commits, regehr, nlopes

Tags: #llvm

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

show more ...

[ValueTracking] enhance matching of umin/umax with 'not' operands

The cmyk test is based on the known regression that resulted from:
rGf2fbdf76d8d0

This improves on the equivalent signed min/max ch

[ValueTracking] enhance matching of umin/umax with 'not' operands

The cmyk test is based on the known regression that resulted from:
rGf2fbdf76d8d0

This improves on the equivalent signed min/max change:
rG867f0c3c4d8c

The underlying icmp equivalence is:
~X pred ~Y --> Y pred X

For an icmp with constant, canonicalization results in a swapped pred:
~X < C --> X > ~C

show more ...

[ValueTracking] add/adjust tests for min/max; NFC

[ValueTracking] enhance matching of smin/smax with 'not' operands

The cmyk tests are based on the known regression that resulted from:
rGf2fbdf76d8d0

So this improvement in analysis might be enough

[ValueTracking] enhance matching of smin/smax with 'not' operands

The cmyk tests are based on the known regression that resulted from:
rGf2fbdf76d8d0

So this improvement in analysis might be enough to restore that commit.

show more ...

[ValueTracking] add tests for smin/smax; NFC