[ConstantFolding] Infer getelementptr nuw flag (#119214)

Infer nuw from nusw and nneg. This is the constant expression variant of
https://github.com/llvm/llvm-project/pull/111144.

Proof: https:/

[ConstantFolding] Infer getelementptr nuw flag (#119214)

Infer nuw from nusw and nneg. This is the constant expression variant of
https://github.com/llvm/llvm-project/pull/111144.

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

show more ...

[ConstantFolding] Canonicalize constexpr GEPs to i8 (#89872)

This patch canonicalizes constant expression GEPs to use i8 source
element type, aka ptradd. This is the ConstantFolding equivalent of t

[ConstantFolding] Canonicalize constexpr GEPs to i8 (#89872)

This patch canonicalizes constant expression GEPs to use i8 source
element type, aka ptradd. This is the ConstantFolding equivalent of the
InstCombine canonicalization introduced in #68882.

I believe all our optimizations working on constant expression GEPs
(like GlobalOpt etc) have already been switched to work on offsets, so I
don't expect any significant fallout from this change.

This is part of:
https://discourse.llvm.org/t/rfc-replacing-getelementptr-with-ptradd/68699

show more ...

[SCCP] Do not attempt to create constexpr for a scalable vector GEP

Scalable vector GEPs are not constants and trying to create one for
these GEPs causes an assertion failure.

Reviewed By: nikic, p

[SCCP] Do not attempt to create constexpr for a scalable vector GEP

Scalable vector GEPs are not constants and trying to create one for
these GEPs causes an assertion failure.

Reviewed By: nikic, paulwalker-arm

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

show more ...

[SCCP] Convert tests to opaque pointers (NFC)

Conversion was performed using
https://gist.github.com/nikic/98357b71fd67756b0f064c9517b62a34
plus manual (but uninteresting) fixup.

[ConstantFold] Remove unnecessary bounded index restriction

The fold for merging a GEP of GEP into a single GEP currently bails
if doing so would result in notional overindexing. The justification
g

[ConstantFold] Remove unnecessary bounded index restriction

The fold for merging a GEP of GEP into a single GEP currently bails
if doing so would result in notional overindexing. The justification
given in the comment above this check is dangerously incorrect: GEPs
with notional overindexing are perfectly fine, and if some code
treats them incorrectly, then that code is broken, not the GEP.
Such a GEP might legally appear in source IR, so only preventing
its creation cannot be sufficient. (The constant folder also ends
up canonicalizing the GEP to remove the notional overindexing, but
that's neither here nor there.)

This check dates back to
https://github.com/llvm/llvm-project/commit/bd4fef4a8939db18f39b108e19097b25e2c7c47a,
and as far as I can tell the original issue this was trying to
patch around has since been resolved.

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

show more ...

[test] Use -passes syntax when specifying pipeline in some more tests

The legacy PM is deprecated, so update a bunch of lit tests running
opt to use the new PM syntax when specifying the pipeline.
I

[test] Use -passes syntax when specifying pipeline in some more tests

The legacy PM is deprecated, so update a bunch of lit tests running
opt to use the new PM syntax when specifying the pipeline.
In this patch focus has been put on test cases for ConstantMerge,
ConstraintElimination, CorrelatedValuePropagation, GlobalDCE,
GlobalOpt, SCCP, TailCallElim and PredicateInfo.

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

show more ...

[ConstantFold] ConstantFoldGetElementPtr - use APInt::isNegative() instead of getSExtValue() to support big ints

Fixes fuzz test: https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=39197

[SCCP] Regenerate bigint test checks

Revert "Recommit "[SCCP] Do not replace deref'able ptr with un-deref'able one.""

Looks like there is still another remaining issue:

http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstra

Revert "Recommit "[SCCP] Do not replace deref'able ptr with un-deref'able one.""

Looks like there is still another remaining issue:

http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap-msan/builds/22273/steps/build%20libcxx%2Fmsan/logs/stdio

This reverts commit 86a20d9e34f5a9989da72097f23f3b0a44157e73.

show more ...

Recommit "[SCCP] Do not replace deref'able ptr with un-deref'able one."

This version includes an small fix allowing function pointers to be
unconditionally replaced for now.

This reverts commit 4c5

Recommit "[SCCP] Do not replace deref'able ptr with un-deref'able one."

This version includes an small fix allowing function pointers to be
unconditionally replaced for now.

This reverts commit 4c5e4aa89b11ec3253258b8df5125833773d1b1e.

show more ...

Revert "[SCCP] Do not replace deref'able ptr with un-deref'able one."

This reverts commit 3542feeb2077f267bff1ab98fb4bf20099f44bb8.

This seems to be causing issues with a sanitizer build
http://lab

Revert "[SCCP] Do not replace deref'able ptr with un-deref'able one."

This reverts commit 3542feeb2077f267bff1ab98fb4bf20099f44bb8.

This seems to be causing issues with a sanitizer build
http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-bootstrap-msan/builds/21677

show more ...

[SCCP] Do not replace deref'able ptr with un-deref'able one.

Currently IPSCCP (and others like CVP/GVN) blindly propagate pointer
equalities. In certain cases, that leads to dereferenceable pointers

[SCCP] Do not replace deref'able ptr with un-deref'able one.

Currently IPSCCP (and others like CVP/GVN) blindly propagate pointer
equalities. In certain cases, that leads to dereferenceable pointers
being replaced, as in the example test case.

I think this is not allowed, as it introduces an access of an
un-dereferenceable pointer. Note that the pointer is inbounds, but one
past the last element, so it is valid, but not dereferenceable.

This patch is mostly to highlight the issue and start a discussion.
Currently it only checks for specifically looking
one-past-the-last-element pointers with array typed bases.

This causes the mis-compile outlined in
https://stackoverflow.com/questions/55754313/is-this-gcc-clang-past-one-pointer-comparison-behavior-conforming-or-non-standar

In the test case, if we replace %p with the GEP for the store, we
subsequently determine that the store and the load cannot alias, because
they are to different underlying objects.

Note that Alive2 seems to think that the replacement is valid:
https://alive2.llvm.org/ce/z/2rorhk

Reviewed By: efriedma

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

show more ...

[SCCP] Do not mark unknown loads as overdefined.

For tracked globals that are unknown after solving, we expect all
non-store uses to be replaced.

This is a follow-up to f8045b250d80, which removed

[SCCP] Do not mark unknown loads as overdefined.

For tracked globals that are unknown after solving, we expect all
non-store uses to be replaced.

This is a follow-up to f8045b250d80, which removed forcedconstant.

We should not mark unknown loads as overdefined, as they either load
from an unknown pointer or an undef global. Restore the original logic
for loads.

show more ...

Recommit "[SCCP] Remove forcedconstant, go to overdefined instead"

This includes a fix for cases where things get marked as overdefined in
ResolvedUndefsIn, but we later discover a constant. To avoi

Recommit "[SCCP] Remove forcedconstant, go to overdefined instead"

This includes a fix for cases where things get marked as overdefined in
ResolvedUndefsIn, but we later discover a constant. To avoid crashing,
we consistently bail out on overdefined values in the visitors. This is
similar to the previous behavior with forcedconstant.

This reverts the revert commit 02b72f564c8be0b4f4337d5c4a3fcf7e8018a818.

show more ...

Revert "Recommit "[SCCP] Remove forcedconstant, go to overdefined instead""

This reverts commit bb310b3f73dde5551bc2a0d564e88f7c831dfdb3. This
breaks the stage2 ASan build, see:

https://bugs.llvm.o

Revert "Recommit "[SCCP] Remove forcedconstant, go to overdefined instead""

This reverts commit bb310b3f73dde5551bc2a0d564e88f7c831dfdb3. This
breaks the stage2 ASan build, see:

https://bugs.llvm.org/show_bug.cgi?id=44898

rdar://59431448

show more ...

Recommit "[SCCP] Remove forcedconstant, go to overdefined instead"

This version includes a fix for a set of crashes caused by marking
values depending on a yet unknown & tracked call as overdefined.

Recommit "[SCCP] Remove forcedconstant, go to overdefined instead"

This version includes a fix for a set of crashes caused by marking
values depending on a yet unknown & tracked call as overdefined.

In some cases, we would later discover that the call has a constant
result and try to mark a user of it as constant, although it was already
marked as overdefined. Most instruction handlers bail out early if the
instruction is already overdefined. But that is not necessary for
CastInsts for example. By skipping values that depend on skipped
calls, we resolve the crashes and also improve the precision in some
cases (see resolvedundefsin-tracked-fn.ll).

Note that we may not skip PHI nodes that may depend on a skipped call,
but they can be safely marked as overdefined, as we bail out early if
the PHI node is overdefined.

This reverts the revert commit
a74b31a3e9cd844c7ce2087978568e3f5ec8519.

show more ...

Revert "[SCCP] Remove forcedconstant, go to overdefined instead"

This causes a crash for the reproducer below

enum { a };
enum b { c, d };
e;
static _Bool g(struct f *h, enum b i) {
i &&j();

Revert "[SCCP] Remove forcedconstant, go to overdefined instead"

This causes a crash for the reproducer below

enum { a };
enum b { c, d };
e;
static _Bool g(struct f *h, enum b i) {
i &&j();
return a;
}
static k(char h, enum b i) {
_Bool l = g(e, i);
l;
}
m(h) {
k(h, c);
g(h, d);
}

This reverts commit aadb635e04854220064b77cc10d0e6772f5492fd.

show more ...

[SCCP] Remove forcedconstant, go to overdefined instead

This patch removes forcedconstant to simplify things for the
move to ValueLattice, which includes constant ranges, but no
forced constants.

T

[SCCP] Remove forcedconstant, go to overdefined instead

This patch removes forcedconstant to simplify things for the
move to ValueLattice, which includes constant ranges, but no
forced constants.

This patch removes forcedconstant and changes ResolvedUndefsIn
to mark instructions with unknown operands as overdefined. This
means we do not do simplifications based on undef directly in SCCP
any longer, but this seems to hardly come up in practice (see stats
below), presumably because InstCombine & others take care
of most of the relevant folds already.

It is still beneficial to keep ResolvedUndefIn, as it allows us delaying
going to overdefined until we propagated all known information.

I also built MultiSource, SPEC2000 and SPEC2006 and compared
sccp.IPNumInstRemoved and sccp.NumInstRemoved. It looks like the impact
is quite low:

Tests: 244
Same hash: 238 (filtered out)
Remaining: 6
Metric: sccp.IPNumInstRemoved

Program base patch diff
test-suite...arks/VersaBench/dbms/dbms.test 4.00 3.00 -25.0%
test-suite...TimberWolfMC/timberwolfmc.test 38.00 34.00 -10.5%
test-suite...006/453.povray/453.povray.test 158.00 155.00 -1.9%
test-suite.../CINT2000/176.gcc/176.gcc.test 668.00 668.00 0.0%
test-suite.../CINT2006/403.gcc/403.gcc.test 1209.00 1209.00 0.0%
test-suite...arks/mafft/pairlocalalign.test 76.00 76.00 0.0%

Tests: 244
Same hash: 238 (filtered out)
Remaining: 6
Metric: sccp.NumInstRemoved

Program base patch diff
test-suite...arks/mafft/pairlocalalign.test 185.00 175.00 -5.4%
test-suite.../CINT2006/403.gcc/403.gcc.test 2059.00 2056.00 -0.1%
test-suite.../CINT2000/176.gcc/176.gcc.test 2358.00 2357.00 -0.0%
test-suite...006/453.povray/453.povray.test 317.00 317.00 0.0%
test-suite...TimberWolfMC/timberwolfmc.test 12.00 12.00 0.0%

Reviewers: davide, efriedma, mssimpso

Reviewed By: efriedma

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

show more ...

Revert "Temporarily Revert "Add basic loop fusion pass.""

The reversion apparently deleted the test/Transforms directory.

Will be re-reverting again.

llvm-svn: 358552

[ConstantFold] Use getMinSignedBits for APInt in isIndexInRangeOfArrayType.

Indices for getelementptr can be signed so we should use
getMinSignedBits instead of getActiveBits here. The function late

[ConstantFold] Use getMinSignedBits for APInt in isIndexInRangeOfArrayType.

Indices for getelementptr can be signed so we should use
getMinSignedBits instead of getActiveBits here. The function later calls
getSExtValue to get the int64_t value, which also checks
getMinSignedBits.

This fixes https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=11647.

Reviewers: mssimpso, efriedma, davide

Reviewed By: efriedma

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

llvm-svn: 348957

show more ...

[ConstantInt] Check active bits before calling getZExtValue.

Without this check, we hit an assertion in getZExtValue, if the constant
value does not fit into an uint64_t.

As getZExtValue returns an

[ConstantInt] Check active bits before calling getZExtValue.

Without this check, we hit an assertion in getZExtValue, if the constant
value does not fit into an uint64_t.

As getZExtValue returns an uint64_t, should we update
getAggregateElement to take an uin64_t as well?

This fixes https://bugs.chromium.org/p/oss-fuzz/issues/detail?id=6109.

Reviewers: efriedma, craig.topper, spatel

Reviewed By: efriedma

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

llvm-svn: 348906

show more ...

[opaque pointer type] Add textual IR support for explicit type parameter to load instruction

Essentially the same as the GEP change in r230786.

A similar migration script can be used to update test

[opaque pointer type] Add textual IR support for explicit type parameter to load instruction

Essentially the same as the GEP change in r230786.

A similar migration script can be used to update test cases, though a few more
test case improvements/changes were required this time around: (r229269-r229278)

import fileinput
import sys
import re

pat = re.compile(r"((?:=|:|^)\s*load (?:atomic )?(?:volatile )?(.*?))(| addrspace\(\d+\) *)\*($| *(?:%|@|null|undef|blockaddress|getelementptr|addrspacecast|bitcast|inttoptr|\[\[[a-zA-Z]|\{\{).*$)")

for line in sys.stdin:
sys.stdout.write(re.sub(pat, r"\1, \2\3*\4", line))

Reviewers: rafael, dexonsmith, grosser

Differential Revision: http://reviews.llvm.org/D7649

llvm-svn: 230794

show more ...

[opaque pointer type] Add textual IR support for explicit type parameter to getelementptr instruction

One of several parallel first steps to remove the target type of pointers,
replacing them with a

[opaque pointer type] Add textual IR support for explicit type parameter to getelementptr instruction

One of several parallel first steps to remove the target type of pointers,
replacing them with a single opaque pointer type.

This adds an explicit type parameter to the gep instruction so that when the
first parameter becomes an opaque pointer type, the type to gep through is
still available to the instructions.

* This doesn't modify gep operators, only instructions (operators will be
handled separately)

* Textual IR changes only. Bitcode (including upgrade) and changing the
in-memory representation will be in separate changes.

* geps of vectors are transformed as:
getelementptr <4 x float*> %x, ...
->getelementptr float, <4 x float*> %x, ...
Then, once the opaque pointer type is introduced, this will ultimately look
like:
getelementptr float, <4 x ptr> %x
with the unambiguous interpretation that it is a vector of pointers to float.

* address spaces remain on the pointer, not the type:
getelementptr float addrspace(1)* %x
->getelementptr float, float addrspace(1)* %x
Then, eventually:
getelementptr float, ptr addrspace(1) %x

Importantly, the massive amount of test case churn has been automated by
same crappy python code. I had to manually update a few test cases that
wouldn't fit the script's model (r228970,r229196,r229197,r229198). The
python script just massages stdin and writes the result to stdout, I
then wrapped that in a shell script to handle replacing files, then
using the usual find+xargs to migrate all the files.

update.py:
import fileinput
import sys
import re

ibrep = re.compile(r"(^.*?[^%\w]getelementptr inbounds )(((?:<\d* x )?)(.*?)(| addrspace\(\d\)) *\*(|>)(?:$| *(?:%|@|null|undef|blockaddress|getelementptr|addrspacecast|bitcast|inttoptr|\[\[[a-zA-Z]|\{\{).*$))")
normrep = re.compile( r"(^.*?[^%\w]getelementptr )(((?:<\d* x )?)(.*?)(| addrspace\(\d\)) *\*(|>)(?:$| *(?:%|@|null|undef|blockaddress|getelementptr|addrspacecast|bitcast|inttoptr|\[\[[a-zA-Z]|\{\{).*$))")

def conv(match, line):
if not match:
return line
line = match.groups()[0]
if len(match.groups()[5]) == 0:
line += match.groups()[2]
line += match.groups()[3]
line += ", "
line += match.groups()[1]
line += "\n"
return line

for line in sys.stdin:
if line.find("getelementptr ") == line.find("getelementptr inbounds"):
if line.find("getelementptr inbounds") != line.find("getelementptr inbounds ("):
line = conv(re.match(ibrep, line), line)
elif line.find("getelementptr ") != line.find("getelementptr ("):
line = conv(re.match(normrep, line), line)
sys.stdout.write(line)

apply.sh:
for name in "$@"
do
python3 `dirname "$0"`/update.py < "$name" > "$name.tmp" && mv "$name.tmp" "$name"
rm -f "$name.tmp"
done

The actual commands:
From llvm/src:
find test/ -name *.ll | xargs ./apply.sh
From llvm/src/tools/clang:
find test/ -name *.mm -o -name *.m -o -name *.cpp -o -name *.c | xargs -I '{}' ../../apply.sh "{}"
From llvm/src/tools/polly:
find test/ -name *.ll | xargs ./apply.sh

After that, check-all (with llvm, clang, clang-tools-extra, lld,
compiler-rt, and polly all checked out).

The extra 'rm' in the apply.sh script is due to a few files in clang's test
suite using interesting unicode stuff that my python script was throwing
exceptions on. None of those files needed to be migrated, so it seemed
sufficient to ignore those cases.

Reviewers: rafael, dexonsmith, grosser

Differential Revision: http://reviews.llvm.org/D7636

llvm-svn: 230786

show more ...

Eliminate more redundant llvm-as calls.

llvm-svn: 81540

Use opt -S instead of piping bitcode output through llvm-dis.

llvm-svn: 81257