[SimplifyCFG][PhaseOrdering] Defer lowering switch into an integer range comparison and branch until after at least the IPSCCP

That transformation is lossy, as discussed in
https://github.com/llvm/l

[SimplifyCFG][PhaseOrdering] Defer lowering switch into an integer range comparison and branch until after at least the IPSCCP

That transformation is lossy, as discussed in
https://github.com/llvm/llvm-project/issues/53853
and https://github.com/rust-lang/rust/issues/85133#issuecomment-904185574

This is an alternative to D119839,
which would add a limited IPSCCP into SimplifyCFG.

Unlike lowering switch to lookup, we still want this transformation
to happen relatively early, but after giving a chance for the things
like CVP to do their thing. It seems like deferring it just until
the IPSCCP is enough for the tests at hand, but perhaps we need to
be more aggressive and disable it until CVP.

Fixes https://github.com/llvm/llvm-project/issues/53853
Refs. https://github.com/rust-lang/rust/issues/85133

Reviewed By: nikic

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

show more ...

[SimplifyCFG] Fix SimplifyBranchOnICmpChain to be undef/poison safe.

This patch fixes the problem of SimplifyBranchOnICmpChain that occurs
when extra values are Undef or poison.

Suppose the %mode i

[SimplifyCFG] Fix SimplifyBranchOnICmpChain to be undef/poison safe.

This patch fixes the problem of SimplifyBranchOnICmpChain that occurs
when extra values are Undef or poison.

Suppose the %mode is 51 and the %Cond is poison, and let's look at the
case below.
```
%A = icmp ne i32 %mode, 0
%B = icmp ne i32 %mode, 51
%C = select i1 %A, i1 %B, i1 false
%D = select i1 %C, i1 %Cond, i1 false
br i1 %D, label %T, label %F
=>
br i1 %Cond, label %switch.early.test, label %F
switch.early.test:
switch i32 %mode, label %T [
i32 51, label %F
i32 0, label %F
]
```
incorrectness: https://alive2.llvm.org/ce/z/BWScX

Code before transformation will not raise UB because %C and %D is false,
and it will not use %Cond. But after transformation, %Cond is being used
immediately, and it will raise UB.

This problem can be solved by adding freeze instruction.

correctness: https://alive2.llvm.org/ce/z/x9x4oY

Reviewed By: nikic

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

show more ...

[SimplifyCFG] Tail-merging all blocks with `ret` terminator

Based ontop of D104598, which is a NFCI-ish refactoring.
Here, a restriction, that only empty blocks can be merged, is lifted.

Reviewed B

[SimplifyCFG] Tail-merging all blocks with `ret` terminator

Based ontop of D104598, which is a NFCI-ish refactoring.
Here, a restriction, that only empty blocks can be merged, is lifted.

Reviewed By: rnk

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

show more ...

[SimplifyCFG] Make test more robust (NFC)

These are supposed to test creation of a switch, so make sure
there is some actual code in the branches. Otherwise this could
be turned into a select instea

[SimplifyCFG] Make test more robust (NFC)

These are supposed to test creation of a switch, so make sure
there is some actual code in the branches. Otherwise this could
be turned into a select instead.

show more ...

[SimplifyCFG] Update SimplifyBranchOnICmpChain to recognize select form of and/or

This patch teaches SimplifyCFG::SimplifyBranchOnICmpChain to understand select form of
(x == C1 || x == C2 || ...) /

[SimplifyCFG] Update SimplifyBranchOnICmpChain to recognize select form of and/or

This patch teaches SimplifyCFG::SimplifyBranchOnICmpChain to understand select form of
(x == C1 || x == C2 || ...) / (x != C1 && x != C2 && ...) and optimize them into switch if possible.
D93065 has more context about the transition, including links to the list of optimizations being updated.

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

show more ...

[SimplifyCFG] Teach tryToSimplifyUncondBranchWithICmpInIt() to preserve DomTree

Add tests for D93943 (NFC)

[SimplifyCFG] Add tests for select form and/or for creating select from icmps

[SimplifyCFG] NFC, update Switch tests as a baseline.

Also add baseline tests to show effect of later patches.

There were a couple of regressions here that were never caught,
but my patch set that

[SimplifyCFG] NFC, update Switch tests as a baseline.

Also add baseline tests to show effect of later patches.

There were a couple of regressions here that were never caught,
but my patch set that this is a preparation to will fix them.

This is the third attempt to land this patch.

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

llvm-svn: 363319

show more ...

[SimplifyCFG] reverting preliminary Switch patches again

This reverts 363226 and 363227, both NFC intended

I swear I fixed the test case that is failing, and ran
the tests, but I will look into it

[SimplifyCFG] reverting preliminary Switch patches again

This reverts 363226 and 363227, both NFC intended

I swear I fixed the test case that is failing, and ran
the tests, but I will look into it again.

llvm-svn: 363229

show more ...

[SimplifyCFG] NFC, update Switch tests to better examine successive patches

Also add baseline tests to show effect of later patches.

There were a couple of regressions here that were never caught,

[SimplifyCFG] NFC, update Switch tests to better examine successive patches

Also add baseline tests to show effect of later patches.

There were a couple of regressions here that were never caught,
but my patch set that this is a preparation to will fix them.

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

llvm-svn: 363226

show more ...

[SimplifyCFG] revert the last commit.

I ran ALL the test suite locally, so I will look into this...

llvm-svn: 363223

[SimplifyCFG] NFC, update Switch tests to HEAD so I can

see if my changes change anything

Also add baseline tests to show effect of later patches.

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

[SimplifyCFG] NFC, update Switch tests to HEAD so I can

see if my changes change anything

Also add baseline tests to show effect of later patches.

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

llvm-svn: 363222

show more ...

[SimplifyCFG] back out all SwitchInst commits

They caused the sanitizer builds to fail.

My suspicion is the change the countLeadingZeros().

llvm-svn: 361736

[SimplifyCFG] NFC, update Switch tests to HEAD so I can see if my changes change anything

Also add baseline tests to show effect of later patches.

llvm-svn: 361725

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

The reversion apparently deleted the test/Transforms directory.

Will be re-reverting again.

llvm-svn: 358552

opt: Rename -default-data-layout flag to -data-layout and make it always override the layout.

There isn't much point in a flag that only works if the data layout is empty.

Differential Revision: ht

opt: Rename -default-data-layout flag to -data-layout and make it always override the layout.

There isn't much point in a flag that only works if the data layout is empty.

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

llvm-svn: 295468

show more ...

Teaching SimplifyCFG to recognize the Or-Mask trick that InstCombine uses to
reduce the number of comparisons.

Specifically, InstCombine can turn:
(i == 5334 || i == 5335)
into:
((i | 1) == 5335

Teaching SimplifyCFG to recognize the Or-Mask trick that InstCombine uses to
reduce the number of comparisons.

Specifically, InstCombine can turn:
(i == 5334 || i == 5335)
into:
((i | 1) == 5335)

SimplifyCFG was already able to detect the pattern:
(i == 5334 || i == 5335)
to:
((i & -2) == 5334)

This patch supersedes D21315 and resolves PR27555
(https://llvm.org/bugs/show_bug.cgi?id=27555).

Thanks to David and Chandler for the suggestions!

Author: Thomas Jablin (tjablin)
Reviewers: majnemer chandlerc halfdan cycheng

http://reviews.llvm.org/D21397

llvm-svn: 273639

show more ...

SimplifyCFG is able to detect the pattern:
(i == 5334 || i == 5335)
to:
((i & -2) == 5334)

This transformation has some incorrect side conditions. Specifically, the
transformation is only ap

SimplifyCFG is able to detect the pattern:
(i == 5334 || i == 5335)
to:
((i & -2) == 5334)

This transformation has some incorrect side conditions. Specifically, the
transformation is only applied when the right-hand side constant (5334 in
the example) is a power of two not equal and not equal to the negated mask.
These side conditions were added in r258904 to fix PR26323. The correct side
condition is that: ((Constant & Mask) == Constant)[(5334 & -2) == 5334].

It's a little bit hard to see why these transformations are correct and what
the side conditions ought to be. Here is a CVC3 program to verify them for
64-bit values:
ONE : BITVECTOR(64) = BVZEROEXTEND(0bin1, 63);
x : BITVECTOR(64);
y : BITVECTOR(64);
z : BITVECTOR(64);
mask : BITVECTOR(64) = BVSHL(ONE, z);
QUERY( (y & ~mask = y) =>
((x & ~mask = y) <=> (x = y OR x = (y | mask)))
);

Please note that each pattern must be a dual implication (<--> or iff). One
directional implication can create spurious matches. If the implication is
only one-way, an unsatisfiable condition on the left side can imply a
satisfiable condition on the right side. Dual implication ensures that
satisfiable conditions are transformed to other satisfiable conditions and
unsatisfiable conditions are transformed to other unsatisfiable conditions.

Here is a concrete example of a unsatisfiable condition on the left
implying a satisfiable condition on the right:
mask = (1 << z)
(x & ~mask) == y --> (x == y || x == (y | mask))

Substituting y = 3, z = 0 yields:
(x & -2) == 3 --> (x == 3 || x == 2)

The version of this code before r258904 had no side-conditions and
incorrectly justified itself in comments through one-directional
implication.

Thanks to Chandler for the suggestion!

Author: Thomas Jablin (tjablin)
Reviewers: chandlerc majnemer hfinkel cycheng

http://reviews.llvm.org/D21417

llvm-svn: 272873

show more ...

[LLVM] Remove unwanted --check-prefix=CHECK from unit tests. NFC.

Summary: Removed unwanted --check-prefix=CHECK from numerous unit tests.

Reviewers: t.p.northover, dblaikie, uweigand, MatzeB, tste

[LLVM] Remove unwanted --check-prefix=CHECK from unit tests. NFC.

Summary: Removed unwanted --check-prefix=CHECK from numerous unit tests.

Reviewers: t.p.northover, dblaikie, uweigand, MatzeB, tstellarAMD, mcrosier

Subscribers: mcrosier, dsanders

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

llvm-svn: 266834

show more ...

[SimplifyCFG] Don't mistake icmp of and for a tree of comparisons

SimplifyCFG tries to turn complex branch conditions into a switch.
Some of it's logic attempts to reason about bitwise arithmetic pr

[SimplifyCFG] Don't mistake icmp of and for a tree of comparisons

SimplifyCFG tries to turn complex branch conditions into a switch.
Some of it's logic attempts to reason about bitwise arithmetic produced
by InstCombine. InstCombine can turn things like (X == 2) || (X == 3)
into (X & 1) == 2 and so SimplifyCFG tries to detect when this occurs so
that it can produce a switch instruction.

However, the legality checking was not sufficient to determine whether
or not this had occured. Correctly check this case by requiring that
the right-hand side of the comparison be a power of two.

This fixes PR26323.

llvm-svn: 258904

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 ...

Resolve TODO in test now that filecheck has multiple check prefixes.

llvm-svn: 194344

Teach SimplifyCFG about address spaces

llvm-svn: 193104