[InstCombine] Infer nusw + nneg -> nuw for getelementptr (#111144)

If the gep is nusw (usually via inbounds) and the offset is
non-negative, we can infer nuw.

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

[InstCombine] Infer nusw + nneg -> nuw for getelementptr (#111144)

If the gep is nusw (usually via inbounds) and the offset is
non-negative, we can infer nuw.

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

show more ...

[InstCombine] Remove some of the complexity-based canonicalization (#91185)

The idea behind this canonicalization is that it allows us to handle less
patterns, because we know that some will be can

[InstCombine] Remove some of the complexity-based canonicalization (#91185)

The idea behind this canonicalization is that it allows us to handle less
patterns, because we know that some will be canonicalized away. This is
indeed very useful to e.g. know that constants are always on the right.

However, this is only useful if the canonicalization is actually
reliable. This is the case for constants, but not for arguments: Moving
these to the right makes it look like the "more complex" expression is
guaranteed to be on the left, but this is not actually the case in
practice. It fails as soon as you replace the argument with another
instruction.

The end result is that it looks like things correctly work in tests,
while they actually don't. We use the "thwart complexity-based
canonicalization" trick to handle this in tests, but it's often a
challenge for new contributors to get this right, and based on the
regressions this PR originally exposed, we clearly don't get this right
in many cases.

For this reason, I think that it's better to remove this complexity
canonicalization. It will make it much easier to write tests for
commuted cases and make sure that they are handled.

show more ...

[InstCombine] Remove one-use restriction on icmp of gep fold (#76730)

The fold for icmp (gep (p, i1), gep (p, i2)) to icmp (i1, i2) is
currently limited to one of the GEPs either having one use or

[InstCombine] Remove one-use restriction on icmp of gep fold (#76730)

The fold for icmp (gep (p, i1), gep (p, i2)) to icmp (i1, i2) is
currently limited to one of the GEPs either having one use or a constant
offset. I believe this is to avoid duplicating complex arithmetic both
in the GEP and the offset comparison.

This patch instead does the same thing that the indexed compare fold
does, which is to rewrite the GEP into i8 form if necessary, so that the
offset arithmetic is not repeated after the transform.

I ran into this problem in a case where there are multiple conditions on
the same pointer, which prevents them from getting folded.

show more ...

[InstCombine] Canonicalize constant GEPs to i8 source element type (#68882)

This patch canonicalizes getelementptr instructions with constant
indices to use the `i8` source element type. This makes

[InstCombine] Canonicalize constant GEPs to i8 source element type (#68882)

This patch canonicalizes getelementptr instructions with constant
indices to use the `i8` source element type. This makes it easier for
optimizations to recognize that two GEPs are identical, because they
don't need to see past many different ways to express the same offset.

This is a first step towards
https://discourse.llvm.org/t/rfc-replacing-getelementptr-with-ptradd/68699.
This is limited to constant GEPs only for now, as they have a clear
canonical form, while we're not yet sure how exactly to deal with
variable indices.

The test llvm/test/Transforms/PhaseOrdering/switch_with_geps.ll gives
two representative examples of the kind of optimization improvement we
expect from this change. In the first test SimplifyCFG can now realize
that all switch branches are actually the same. In the second test it
can convert it into simple arithmetic. These are representative of
common optimization failures we see in Rust.

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

show more ...

[InstCombine] Regenerate all test checks (NFC)

Due to an improvement to name preservation, a lot of InstCombine
tests now show spurious diffs when regenerated.

Rather than regenerating individual f

[InstCombine] Regenerate all test checks (NFC)

Due to an improvement to name preservation, a lot of InstCombine
tests now show spurious diffs when regenerated.

Rather than regenerating individual files when they get touched,
mass-regenerate all UTC-based InstCombine tests. I have then reset
a number of files showing suspicious diffs where the UTC output
has clearly been manually adjusted. I apologize if I missed
anything in the mass of changes.

show more ...

InstCombine: Convert some tests to opaque pointers

Needed manual fixes:
2008-01-06-VoidCast.ll
alias.ll @0 type lost
pr27703.ll totally confused
pr44242.ll phi and update_test_checks
pr442

InstCombine: Convert some tests to opaque pointers

Needed manual fixes:
2008-01-06-VoidCast.ll
alias.ll @0 type lost
pr27703.ll totally confused
pr44242.ll phi and update_test_checks
pr44245.ll phi and update_test_checks

Needed re-running update_test_checks:
2009-01-08-AlignAlloca.ll
2009-02-20-InstCombine-SROA.ll
addrspacecast.ll
alloca-cast-debuginfo.ll
alloca-in-non-alloca-as.ll
alloca.ll
icmp-gep.ll
icmp-custom-dl.ll
lifetime-no-null-opt.ll
non-integral-pointers.ll
pr33689_same_bitwidth.ll
pr39908.ll
scalable-cast-of-alloc.ll
select-cmp-br.ll
unpack-fca.ll

Converted to generated checks:
2012-6-7-vselect-bitcast.ll

show more ...

[test] Use -passes=instcombine instead of -instcombine in lots of tests. NFC

Another step moving away from the deprecated syntax of specifying
pass pipeline in opt.

Differential Revision: https://r

[test] Use -passes=instcombine instead of -instcombine in lots of tests. NFC

Another step moving away from the deprecated syntax of specifying
pass pipeline in opt.

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

show more ...

[InstSimplify] Remove incorrect icmp of gep fold (PR52429)

As described in https://bugs.llvm.org/show_bug.cgi?id=52429 this
fold is incorrect, because inbounds only guarantees that the
pointers don'

[InstSimplify] Remove incorrect icmp of gep fold (PR52429)

As described in https://bugs.llvm.org/show_bug.cgi?id=52429 this
fold is incorrect, because inbounds only guarantees that the
pointers don't wrap in the unsigned space: It is possible that
the sign boundary is crossed by an object.

I'm dropping the fold entirely rather than adjusting it, because
computePointerICmp() fully subsumes it (just with correct predicate
handling).

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

show more ...

[InstCombine] Duplicate tests for logical and/or (NFC)

This replicates existing and/or tests to also test variants using
select. This should help us get a more accurate view on which
optimizations w

[InstCombine] Duplicate tests for logical and/or (NFC)

This replicates existing and/or tests to also test variants using
select. This should help us get a more accurate view on which
optimizations we're missing if we disable the select -> and/or
fold.

show more ...

[InstCombine] Avoid modifying instructions in-place

As discussed on D73919, this replaces a few cases where we were
modifying multiple operands of instructions in-place with the
creation of a new in

[InstCombine] Avoid modifying instructions in-place

As discussed on D73919, this replaces a few cases where we were
modifying multiple operands of instructions in-place with the
creation of a new instruction, which we generally prefer nowadays.

This tends to be more readable and less prone to worklist management
bugs.

Test changes are only superficial (instruction naming and order).

show more ...

Reland [DataLayout] Fix occurrences that size and range of pointers are assumed to be the same.

GEP index size can be specified in the DataLayout, introduced in D42123. However, there were still pla

Reland [DataLayout] Fix occurrences that size and range of pointers are assumed to be the same.

GEP index size can be specified in the DataLayout, introduced in D42123. However, there were still places
in which getIndexSizeInBits was used interchangeably with getPointerSizeInBits. This notably caused issues
with Instcombine's visitPtrToInt; but the unit tests was incorrect, so this remained undiscovered.

This fixes the buildbot failures.

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

Patch by Joseph Faulls!

show more ...

Temporarily Revert "[DataLayout] Fix occurrences that size and range of pointers are assumed to be the same."

This reverts commit 5f6208778ff92567c57d7c1e2e740c284d7e69a5.

This caused failures in T

Temporarily Revert "[DataLayout] Fix occurrences that size and range of pointers are assumed to be the same."

This reverts commit 5f6208778ff92567c57d7c1e2e740c284d7e69a5.

This caused failures in Transforms/PhaseOrdering/scev-custom-dl.ll
const: Assertion `getBitWidth() == CR.getBitWidth() && "ConstantRange types don't agree!"' failed.

show more ...

[DataLayout] Fix occurrences that size and range of pointers are assumed to be the same.

GEP index size can be specified in the DataLayout, introduced in D42123. However, there were still places
in

[DataLayout] Fix occurrences that size and range of pointers are assumed to be the same.

GEP index size can be specified in the DataLayout, introduced in D42123. However, there were still places
in which getIndexSizeInBits was used interchangeably with getPointerSizeInBits. This notably caused issues
with Instcombine's visitPtrToInt; but the unit tests was incorrect, so this remained undiscovered.

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

Patch by Joseph Faulls!

show more ...

[Analysis] Don't assume that unsigned overflow can't happen in EmitGEPOffset (PR42699)

Summary:
Currently when computing a GEP offset using the function EmitGEPOffset
for the following instruction

[Analysis] Don't assume that unsigned overflow can't happen in EmitGEPOffset (PR42699)

Summary:
Currently when computing a GEP offset using the function EmitGEPOffset
for the following instruction

getelementptr inbounds i32, i32* %p, i64 %offs

we get

mul nuw i64 %offs, 4

Unfortunately we cannot assume that unsigned wrapping won't happen
here because %offs is allowed to be negative.

Making such assumptions can lead to miscompilations: see the new test
test24_neg_offs in InstCombine/icmp.ll. Without the patch InstCombine
would generate the following comparison:

icmp eq i64 %offs, 4611686018427387902; 0x3ffffffffffffffe

Whereas the correct value to compare with is -2.

This patch replaces the NUW flag with NSW in the multiplication
instructions generated by EmitGEPOffset and adjusts the test suite.

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

Reviewers: chandlerc, craig.topper, ostannard, lebedev.ri, spatel, efriedma, nlopes, aqjune

Reviewed By: lebedev.ri

Subscribers: reames, lebedev.ri, hiraditya, llvm-commits

Tags: #llvm

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

llvm-svn: 375089

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

Adding a width of the GEP index to the Data Layout.

Making a width of GEP Index, which is used for address calculation, to be one of the pointer properties in the Data Layout.
p[address space]:size:

Adding a width of the GEP index to the Data Layout.

Making a width of GEP Index, which is used for address calculation, to be one of the pointer properties in the Data Layout.
p[address space]:size:memory_size:alignment:pref_alignment:index_size_in_bits.
The index size parameter is optional, if not specified, it is equal to the pointer size.

Till now, the InstCombiner normalized GEPs and extended the Index operand to the pointer width.
It works fine if you can convert pointer to integer for address calculation and all registered targets do this.
But some ISAs have very restricted instruction set for the pointer calculation. During discussions were desided to retrieve information for GEP index from the Data Layout.
http://lists.llvm.org/pipermail/llvm-dev/2018-January/120416.html

I added an interface to the Data Layout and I changed the InstCombiner and some other passes to take the Index width into account.
This change does not affect any in-tree target. I added tests to cover data layouts with explicitly specified index size.

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

llvm-svn: 325102

show more ...