[LVI] Remove unused get of Range metadata (#94914)

There is no test for this code and it also do not change the result of
https://github.com/dtcxzyw/llvm-opt-benchmark when I run it locally.
I hav

[LVI] Remove unused get of Range metadata (#94914)

There is no test for this code and it also do not change the result of
https://github.com/dtcxzyw/llvm-opt-benchmark when I run it locally.
I have not been able to make a test for this and do not know how to
handle the range attribute for this so maybe it shall be removed?

show more ...

[ValueTracking] Restore isKnownNonZero parameter order. (#88873)

Prior to #85863, the required parameters of llvm::isKnownNonZero were
Value and DataLayout. After, they are Value, Depth, and Simpli

[ValueTracking] Restore isKnownNonZero parameter order. (#88873)

Prior to #85863, the required parameters of llvm::isKnownNonZero were
Value and DataLayout. After, they are Value, Depth, and SimplifyQuery,
where SimplifyQuery is implicitly constructible from DataLayout. The
change to move Depth before SimplifyQuery needed callers to be updated
unnecessarily, and as commented in #85863, we actually want Depth to be
after SimplifyQuery anyway so that it can be defaulted and the caller
does not need to specify it.

show more ...

[ValueTracking] Convert `isKnownNonZero` to use SimplifyQuery (#85863)

This patch converts `isKnownNonZero` to use SimplifyQuery. Then we can
use the context information from `DomCondCache`.

Fix

[ValueTracking] Convert `isKnownNonZero` to use SimplifyQuery (#85863)

This patch converts `isKnownNonZero` to use SimplifyQuery. Then we can
use the context information from `DomCondCache`.

Fixes https://github.com/llvm/llvm-project/issues/85823.
Alive2: https://alive2.llvm.org/ce/z/QUvHVj

show more ...

[LVI] Handle range attributes (#86413)

This adds handling of range attribute for return values of Call and
Invoke in getFromRangeMetadata and handling of argument with range
attribute in solveBloc

[LVI] Handle range attributes (#86413)

This adds handling of range attribute for return values of Call and
Invoke in getFromRangeMetadata and handling of argument with range
attribute in solveBlockValueNonLocal.
There is one additional check of the range metadata at line 1120 in
getValueFromSimpleICmpCondition that is not covered in this PR as after
https://github.com/llvm/llvm-project/pull/75311 there is no test that
cover that check any more and I have not been able to create a test that
trigger that code.

show more ...

[LVI] Use m_AddLike instead of m_Add when matching simple condition

We have more complete logic for handling `Add`, so try to use that
logic for `or disjoint` (which can definitionally be treated as

[LVI] Use m_AddLike instead of m_Add when matching simple condition

We have more complete logic for handling `Add`, so try to use that
logic for `or disjoint` (which can definitionally be treated as
`add`).

Closes #86058

show more ...

[IR] Add `getNoWrapKind` method for `OverflowingBinaryOperator` (NFC)

[LVI] Assert that only one value is pushed (NFC)

[LVI] Don't push both sides of and/or at once

Same as the change in d5db2cdb22ab302acbb6e1a066e791f25dc612de,
but for condition handling. The same issue could occur here as well.

[LVI] Don't push both binop operands at once

If one of the binop operands depends on the other, this may end
up evaluating them in the wrong order, producing sub-optimal
results.

Make sure that onl

[LVI] Don't push both binop operands at once

If one of the binop operands depends on the other, this may end
up evaluating them in the wrong order, producing sub-optimal
results.

Make sure that only one unevaluated operand gets pushed per
iteration.

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

show more ...

[LVI] Support using block values when handling conditions (#75311)

Currently, LVI will only use conditions like "X < C" to constrain the
value of X on the relevant edge. This patch extends it to ha

[LVI] Support using block values when handling conditions (#75311)

Currently, LVI will only use conditions like "X < C" to constrain the
value of X on the relevant edge. This patch extends it to handle
conditions like "X < Y" by querying the known range of Y.

This means that getValueFromCondition() and various related APIs can now
return nullopt to indicate that they have pushed to the worklist, and
need to be called again later. This behavior is currently controlled by
a UseBlockValue option, and only enabled for actual edge value handling.
All other places deriving constraints from conditions keep using the
previous logic for now.

This change was originally motivated as a fix for the regression
reported in
https://github.com/llvm/llvm-project/pull/73662#issuecomment-1849281758.
Unfortunately, it doesn't actually fix it, because we run into another
issue there (LVI currently is really bad at handling values used in
loops).

This change has some compile-time impact, but it's fairly small,
in the 0.05% range.

show more ...

[LVI] Remove unnecessary TLI dependency

Only used in ConstantFoldCompareInstOperands(), which does not
actually use TLI.

[LVI] Don't return optional from getEdgeValueLocal() (NFC)

The general convention inside LVI is that std::nullopt means that
a value has been pushed to the worklist. However, getEdgeValueLocal()
use

[LVI] Don't return optional from getEdgeValueLocal() (NFC)

The general convention inside LVI is that std::nullopt means that
a value has been pushed to the worklist. However, getEdgeValueLocal()
used it as an additional spelling for getOverdefined() instead.

show more ...

[LVI] Move bulk of getConstantRangeAtUse() implementation into Impl (NFC)

Make the layering here similar to all the other methods:
LazyValueInfoImpl implements the underlying API returning a
ValueLa

[LVI] Move bulk of getConstantRangeAtUse() implementation into Impl (NFC)

Make the layering here similar to all the other methods:
LazyValueInfoImpl implements the underlying API returning a
ValueLatticeElement, and then LazyValueInfo exposes this as a
ConstantRange publicly.

show more ...

[LVI] Reuse LatticeValue to ConstantRange conversion more

Use the helper in the getConstantRange() and
getConstantRangeAtUse() APIs as well. For that purpose move the
handling of isUnknown() into th

[LVI] Reuse LatticeValue to ConstantRange conversion more

Use the helper in the getConstantRange() and
getConstantRangeAtUse() APIs as well. For that purpose move the
handling of isUnknown() into the helper as well.

show more ...

[LVI] Don't require DataLayout in getConstantRangeOrFull() (NFC)

We're only working on integers here, so we don't need DataLayout
to determine the width.

[LVI] Drop bitcast handling (NFCI)

The code only works on integer casts, and the only bitcasts
involving integers are trivial. The code as previously written
would try to handle things like float to

[LVI] Drop bitcast handling (NFCI)

The code only works on integer casts, and the only bitcasts
involving integers are trivial. The code as previously written
would try to handle things like float to integer bitcasts by
fetching a ConstantRange of a float value, which is an ill-defined
operation.

show more ...

[LVI] Switch getValueFromCondition() to use recursion

The current implementation using a worklist and visited map adds
a significant amount of additional complexity and compile-time
overhead. All we

[LVI] Switch getValueFromCondition() to use recursion

The current implementation using a worklist and visited map adds
a significant amount of additional complexity and compile-time
overhead. All we really care about here is that we don't overflow
the stack or cause exponential complexity in degenerate cases. We
can achieve this with a simple depth limit.

show more ...

[ValueTracking] Add isGuaranteedNotToBeUndef() variant (NFC)

We have a bunch of places where we have to guard against undef
to avoid multi-use issues, but would be fine with poison. Use a
different

[ValueTracking] Add isGuaranteedNotToBeUndef() variant (NFC)

We have a bunch of places where we have to guard against undef
to avoid multi-use issues, but would be fine with poison. Use a
different function for these to make it clear, and to indicate that
this check can be removed once we no longer support undef. I've
replaced some of the obvious cases, but there's probably more.

For now, the implementation is the same as UndefOrPoison, it just
has a more precise name.

show more ...

[NewPM] Remove LazyValueInfoPrinter Pass (#73408)

This pass isn't used anywhere upstream and thus has no test coverage.
For these reasons, remove it.

[LVI] Add NewPM printer pass (#73425)

This patch adds a NewPM printer pass for the LazyValueAnalysis.

[LVI] Handle icmp of ashr. (#68010)

This handles the case where this combine:
icmp sgt (ashr X, ShAmtC), C --> icmp sgt X, ((C + 1) << ShAmtC) - 1

wasn't performed by instcombine.

Proof of th

[LVI] Handle icmp of ashr. (#68010)

This handles the case where this combine:
icmp sgt (ashr X, ShAmtC), C --> icmp sgt X, ((C + 1) << ShAmtC) - 1

wasn't performed by instcombine.

Proof of the original combine: https://alive2.llvm.org/ce/z/SfpsvX

This is a port of the review in https://reviews.llvm.org/D151911 to
GitHub.

show more ...

[LVI][CVP] Treat undef like a full range (#68190)

When converting to ConstantRange, we should treat undef like a full range.
Fixes #68381.

[Analysis] Fix gcc warnings about unused variables [NFC]

gcc warned with:
[236/4788] Building CXX object lib/Analysis/CMakeFiles/LLVMAnalysis.dir/LazyValueInfo.cpp.o
../lib/Analysis/LazyValueInfo.

[Analysis] Fix gcc warnings about unused variables [NFC]

gcc warned with:
[236/4788] Building CXX object lib/Analysis/CMakeFiles/LLVMAnalysis.dir/LazyValueInfo.cpp.o
../lib/Analysis/LazyValueInfo.cpp: In member function 'void llvm::LazyValueInfo::forgetValue(llvm::Value*)':
../lib/Analysis/LazyValueInfo.cpp:1978:13: warning: unused variable 'Impl' [-Wunused-variable]
1978 | if (auto *Impl = getImpl())
| ^~~~
../lib/Analysis/LazyValueInfo.cpp: In member function 'void llvm::LazyValueInfo::eraseBlock(llvm::BasicBlock*)':
../lib/Analysis/LazyValueInfo.cpp:1983:13: warning: unused variable 'Impl' [-Wunused-variable]
1983 | if (auto *Impl = getImpl())
| ^~~~
../lib/Analysis/LazyValueInfo.cpp: In member function 'void llvm::LazyValueInfo::clear()':
../lib/Analysis/LazyValueInfo.cpp:1988:13: warning: unused variable 'Impl' [-Wunused-variable]
1988 | if (auto *Impl = getImpl())
| ^~~~
../lib/Analysis/LazyValueInfo.cpp: In member function 'void llvm::LazyValueInfo::printLVI(llvm::Function&, llvm::DominatorTree&, llvm::raw_ostream&)':
../lib/Analysis/LazyValueInfo.cpp:1993:13: warning: unused variable 'Impl' [-Wunused-variable]
1993 | if (auto *Impl = getImpl())
| ^~~~

Use the locals instead of calling getImpl() again.

show more ...

[JumpThreading][NFC] Improved access to LazyValueInfoImpl.

[JumpThreading] Invalidate LVI after `combineMetadataForCSE`.