| Age | Commit message (Collapse) | Author |
|---|
|
Having a finite Depth (or recursion limit) for computeKnownBits is very
limiting, but is currently a load-bearing necessity, as all KnownBits
are recomputed on each call and there is no caching. As a prerequisite
for an effort to remove the recursion limit altogether, either using a
clever caching technique, or writing a easily-invalidable KnownBits
analysis, make the Depth argument in APIs in ValueTracking uniformly the
last argument with a default value. This would aid in removing the
argument when the time comes, as many callers that currently pass 0
explicitly are now updated to omit the argument altogether.
|
|
Reapply "IR: Remove uselist for constantdata (#137313)"
This reverts commit 5936c02c8b9c6d1476f7830517781ce8b6e26e75.
Fix checking uselists of constants in assume bundle queries
|
|
Possibly breaks the build: https://lab.llvm.org/buildbot/#/builders/24/builds/8119
This reverts commit 87f312aad6ede636cd2de5d18f3058bf2caf5651.
|
|
This is a resurrected version of the patch attached to this RFC:
https://discourse.llvm.org/t/rfc-constantdata-should-not-have-use-lists/42606
In this adaptation, there are a few differences. In the original patch, the Use's
use list was replaced with an unsigned* to the reference count in the value. This
version leaves them as null and leaves the ref counting only in Value.
Remove use-lists from instances of ConstantData (which are shared
across modules and have no operands).
To continue supporting most of the use-list API, store a ref-count in
place of the use-list; this is for API like Value::use_empty and
Value::hasNUses. Operations that actually need the use-list -- like
Value::use_begin -- will assert.
This change has three benefits:
1. The compiler output cannot in any way depend on the use-list order
of instances of ConstantData.
2. There's no use-list traffic when adding and removing simple
constants from operand lists (although there is ref-count traffic;
YMMV).
3. It's cheaper to serialize use-lists (since we're no longer
serializing the use-list order of things like i32 0).
The downside is that you can't look at all the users of ConstantData,
but traversals of users of i32 0 are already ill-advised.
Possible follow-ups:
- Track if an instance of a ConstantVector/ConstantArray/etc. is known
to have all ConstantData arguments, and drop the use-lists to
ref-counts in those cases. Callers need to check Value::hasUseList
before iterating through the use-list.
- Remove even the ref-counts. I'm not sure they have any benefit
besides minimizing the scope of this commit, and maintaining the
counts is not free.
Fixes #58629
Co-authored-by: Duncan P. N. Exon Smith <dexonsmith@apple.com>
|
|
(#137287)
Alive2: https://alive2.llvm.org/ce/z/uiUzEf
Closes https://github.com/llvm/llvm-project/issues/137196.
Note: To avoid regression in
`ret_nofpclass_nopositives_copysign_nnan_flag`, the second commit takes
FMF into account.
|
|
bits (#124429)
When simplifying operands based on demanded bits, the return value range
of llvm.fshl might change. Keeping the Range attribute might cause
llvm.fshl to generate a poison and lead to miscompile. Drop the Range
attribute similar to `dropPosonGeneratingFlags` elsewhere.
Fix #124387
|
|
demanded (#111151)
Alive2: https://alive2.llvm.org/ce/z/Z7QgjH
|
|
Closes https://github.com/llvm/llvm-project/issues/116775.
|
|
Allows customizing the depth of the recursive search on vectors that
InstCombine does when looking for unused elements.
We find it helpful to be able to customize this for compile time
reasons.
|
|
Rename the function to reflect its correct behavior and to be consistent
with `Module::getOrInsertFunction`. This is also in preparation of
adding a new `Intrinsic::getDeclaration` that will have behavior similar
to `Module::getFunction` (i.e, just lookup, no creation).
|
|
(#111128)
The disables folding for FP aggregates that are not poison/posZero
types, which is currently not supported. Note: To fully handle this
aggregates would also likely require teaching `computeKnownFPClass()` to
handle array and struct constants (which does not seem implemented
outside of zero init).
|
|
(#110635)
Alive2: https://alive2.llvm.org/ce/z/NJgBPL
The motivating case of this patch is to emit `andn` on RISC-V with zbb
for expressions like `(sub 63, X) & 63`.
|
|
There was a discrepancy between how SimplifyDemandedBits and
computeKnownBits handled the Argument case. computeKnownBits()
would use information from range attributes even once the
recursion limit has been reached.
Fixes https://github.com/llvm/llvm-project/issues/110631.
|
|
The srem case of SimplifyDemandedUseBits partially duplicates
KnownBits::srem. It is guarded by a statement that takes the absolute
value of the RHS and checks whether it is a power of 2, but the abs()
call here useless, since an srem with a negative RHS is flipped into one
with a positive RHS, adjusting LHS appropriately. Stripping the abs call
allows us to call KnownBits::srem instead of partially duplicating it.
|
|
When dividing by -1 we were breaking out of the code entirely,
while we should fall through to computeKnownBits().
This fixes an instcombine-verify-known-bits discrepancy.
Fixes https://github.com/llvm/llvm-project/issues/109957.
|
|
|
|
(#102244)
This PR fixes https://github.com/llvm/llvm-project/issues/98435.
`SimplifyDemandedVectorElts` mishandles the undef by assuming that
!isNullValue() means the condition is true.
By preventing any value that we're not certain equals 1 or 0, it avoids
having to make any particular choice by not demanding bits from a
particular branch with potentially picking a wrong value.
Proof: https://alive2.llvm.org/ce/z/r8CmEu
|
|
Compile-time improvement:
http://llvm-compile-time-tracker.com/compare.php?from=13996378d81c8fa9a364aeaafd7382abbc1db83a&to=861ffa4ec5f7bde5a194a7715593a1b5359eb581&stat=instructions:u
baseline: 803eaf29267c6aae9162d1a83a4a2ae508b440d3
```
Top 5 improvements:
stockfish/movegen.ll 2541620819 2538599412 -0.12%
minetest/profiler.cpp.ll 431724935 431246500 -0.11%
abc/luckySwap.c.ll 581173720 580581935 -0.10%
abc/kitTruth.c.ll 2521936288 2519445570 -0.10%
abc/extraUtilTruth.c.ll 1216674614 1215495502 -0.10%
Top 5 regressions:
openssl/libcrypto-shlib-sm4.ll 1155054721 1155943201 +0.08%
openssl/libcrypto-lib-sm4.ll 1155054838 1155943063 +0.08%
spike/vsm4r_vv.ll 1296430080 1297039258 +0.05%
spike/vsm4r_vs.ll 1312496906 1313093460 +0.05%
nuttx/lib_rand48.c.ll 126201233 126246692 +0.04%
Overall: -0.02112308%
```
|
|
The functional change here is to undo "llvm-svn: 311773", aka D36936,
aka commit 22178dd33b3460207b8. That patch avoided to convert AShr
into LShr in SimplifyDemandedUseBits based on known sign bits
analysis. Even if it would be legal to turn the shift into a
logical shift (given by the fact that the shifted in bits wasn't
demanded), that patch prevented converting the shift into LShr when
any of the original sign bits were demanded.
One side effect of the reverted functionalty was that the better we
were at computing number of sign bits, the less likely it was that
we would replace AShr by LShr during SimplifyDemandedUseBits. This
was seen in https://github.com/llvm/llvm-project/pull/97693/ when
an improvement of ComputeNumSignBits resulted in regressions due
to no longer rewriting AShr to LShr.
The test case from D36936 still passes after this commit. So it seems
like at least the compiler has been taught how to optimize that
scenario even if we do the AShr->LShr transform more aggressively.
|
|
Fixes https://github.com/llvm/llvm-project/issues/98139.
|
|
When calling SimplifyDemandedBits (as opposed to
SimplifyDemandedInstructionBits), and there are multiple uses,
always use SimplifyMultipleUseDemandedBits and drop the special
case for root values.
This fixes the ephemeral value detection, as seen by the restored
assumes in tests. It may result in more or less simplification,
depending on whether we get more out of having demanded bits or
the ability to perform non-multi-use transforms. The change in
the phi-known-bits.ll test is because the icmp operand now gets
simplified based on demanded bits, which then prevents a different
known bits simplification later.
This also makes the code safe against future changes like
https://github.com/llvm/llvm-project/pull/97289, which add more
context that would have to be discarded for the multi-use case.
|
|
Repplied with a clang test fix.
-----
When simplifying a multi-use root value, the demanded bits were
reset to full, but we also need to reset the context instruction.
To make this convenient (without requiring by-value passing of
SimplifyQuery), move the logic that handles constants and
dispatches to SimplifyDemandedUseBits/SimplifyMultipleUseDemandedBits
into SimplifyDemandedBits. The SimplifyDemandedInstructionBits
caller starts with full demanded bits and an appropriate context
anyway.
The different context instruction does mean that the ephemeral
value protection no longer triggers in some cases, as the changes
to assume tests show.
An alternative, which I will explore in a followup, is to always
use SimplifyMultipleUseDemandedBits() -- the previous root special
case is only really intended for SimplifyDemandedInstructionBits(),
which now no longer shares this code path.
Fixes https://github.com/llvm/llvm-project/issues/97330.
|
|
This reverts commit b558ac0eef57a3737b1e27844115fa91e0b32582.
This breaks a clang test, reverting for now.
|
|
When simplifying a multi-use root value, the demanded bits were
reset to full, but we also need to reset the context extract. To
make this convenient (without requiring by-value passing of
SimplifyQuery), move the logic that that handles constants and
dispatches to SimplifyDemandedUseBits/SimplifyMultipleUseDemandedBits
into SimplifyDemandedBits. The SimplifyDemandedInstructionBits
caller starts with full demanded bits and an appropriate context
anyway.
The different context instruction does mean that the ephemeral
value protection no longer triggers in some cases, as the changes
to assume tests show.
An alternative, which I will explore in a followup, is to always
use SimplifyMultipleUseDemandedBits() -- the previous root special
case is only really intended for SimplifyDemandedInstructionBits(),
which now no longer shares this code path.
Fixes https://github.com/llvm/llvm-project/issues/97330.
|
|
Extract an adjustKnownBitsForSelectArm() helper for the
ValueTracking logic and make use of it in SimplifyDemandedBits().
This fixes a consistency violation under instcombine-verify-known-bits.
|
|
This fixes a consistency violation under -instcombine-verify-known-bits.
|
|
This will enable calling SimplifyDemandedBits() with a SimplifyQuery
that has CondContext set in the future.
Additionally this also marginally strengthens the analysis by
retaining the original context instruction for one-use chains.
|
|
--> sext (X | Y) to iN (#90509)
Since these remove instructions as long as at least one of X or Y is
one-use, we don't need to check one-use for both.
|
|
We shouldn't simply return here -- we still need to compute the
known bits and fall through to generic handling.
This fixes a -instcombine-verify-known-bits violation in funnel.ll.
|
|
This does the recursive simplification with all bits demanded,
which is not useful. Fall through to the fallback case instead.
|
|
Allow KnownBits to represent "always poison" values via conflict.
close: #94436
|
|
(#79014)
This patch resolve TODO written in commit:
https://github.com/llvm/llvm-project/commit/5909c678831f3a5c1669f6906f777d4ec4532fa1
Proof: https://alive2.llvm.org/ce/z/C3VNoR
|
|
Targets the dynamic realignment pattern of `(Ptr + Align - 1) & -Align;`
as implemented by gep then ptrmask.
Specifically, when the pointer already has alignment information,
dynamically realigning it to less than is already known should be a
no-op. Discovered while writing test cases for another patch.
For the zero low bits of a known aligned pointer, adding the gep index
then removing it with a mask is a no-op. Folding the ptrmask effect
entirely into the gep is the ideal result as that unblocks other
optimisations that are not aware of ptrmask.
In some other cases the gep is known to be dead and is removed without
changing the ptrmask.
In the least effective case, this transform creates a new gep with a
rounded-down index and still leaves the ptrmask unchanged. That
simplified gep is still a minor improvement, geps are cheap and ptrmask
occurs in address calculation contexts so I don't think it's worth
special casing to avoid the extra instruction.
|
|
|
|
A miscompilation issue has been addressed with refined checking.
Shuffle masks operand may be turned into `poison` if this does
not lead to observable changes. This however may not guarantee
binop to binop-of-shuffle replacement to be sound anymore.
Fixes: https://github.com/llvm/llvm-project/issues/82052.
|
|
fshl/fshr having first two arguments as same gets lowered to target
specific rotate. But based on the uses, one of the arguments can get
simplified resulting in different arguments performing equivalent
operation.
This patch prevents the simplification of the arguments of lshr/shl if
they are part of fshl pattern.
Closes https://github.com/llvm/llvm-project/pull/73441.
|
|
This reverts commit ef388334ee5a3584255b9ef5b3fefdb244fa3fd7.
The referenced issue violates the spec for finite-only math only by
using a return value for a constant infinity. If the interpretation
is results and arguments cannot violate nofpclass, then any
std::numeric_limits<T>::infinity() result is invalid under
-ffinite-math-only. Without this interpretation the utility of
nofpclass is slashed.
|
|
The assertion in #80597 failed when we were trying to compute known bits
of a value in an unreachable BB.
https://github.com/llvm/llvm-project/blob/859b09da08c2a47026ba0a7d2f21b7dca705864d/llvm/lib/Transforms/InstCombine/InstCombineSimplifyDemanded.cpp#L749-L810
In this case, `SignBits` is 30 (deduced from instr info), but `Known` is
`10000101010111010011110101000?0?00000000000000000000000000000000`
(deduced from dom cond). Setting high bits of `lshr Known, 1` will lead
to conflict.
This patch masks out high bits of `Known.Zero` to address this problem.
Fixes #80597.
|
|
|
|
We can only set PoisonElts if the element is poison, not if it is
undef.
|
|
This reverts commit 318d5bff0b65aa7d52fc7004d49587416f0fb564.
Has incomplete test updates.
|
|
A miscompilation issue has been addressed with refined checking.
|
|
If an operand (esp to shufflevector or insertelement) is not
demanded, canonicalize it from undef to poison.
|
|
If the splat shuffle is represented using an undef RHS, replace it
with poison.
|
|
In line with updated shufflevector semantics, this represents the
poison elements rather than undef elements now. This commit is a
pure rename, without any logic changes.
|
|
Do not poison `undef` demanded elements in `SimplifyDemandedVectorElts`.
A miscompilation issue has been addressed with refined checking.
Proofs: https://alive2.llvm.org/ce/z/WA5oD5.
|
|
|
|
Change (add x, c) to (xor x, c) iff c is constant and c equals the top bit of the demanded bits.
Alive2: https://alive2.llvm.org/ce/z/DKmkwF
---------
Signed-off-by: Peter Han <fujun.han@iluvatar.com>
Co-authored-by: Peter Han <fujun.han@iluvatar.com>
|
|
|
|
SimplifyDemandedUseBits.
We were previously retaining the name with a numeric suffix.
|
