[EarlyCSE] detect equivalence of selects with inverse conditions and commuted operands (PR41101)

This is 1 of the problems discussed in the post-commit thread for:
rL355741 / http://lists.llvm.org/p

[EarlyCSE] detect equivalence of selects with inverse conditions and commuted operands (PR41101)

This is 1 of the problems discussed in the post-commit thread for:
rL355741 / http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20190311/635516.html
and filed as:
https://bugs.llvm.org/show_bug.cgi?id=41101

Instcombine tries to canonicalize some of these cases (and there's room for improvement
there independently of this patch), but it can't always do that because of extra uses.
So we need to recognize these commuted operand patterns here in EarlyCSE. This is similar
to how we detect commuted compares and commuted min/max/abs.

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

llvm-svn: 358523

show more ...

Very minor typo. NFC

Typo `we we're` => `we were` in the pass EarlyCSE

Patch by liangdzou (Liang ZOU)

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

llvm-svn: 355895

[EarlyCSE] Cleanup deadcode. [NFCI]

Summary: Cleanup nop assignments.

Reviewers: george.burgess.iv, davide

Subscribers: sanjoy, jlebar, llvm-commits

Tags: #llvm

Differential Revision: https://re

[EarlyCSE] Cleanup deadcode. [NFCI]

Summary: Cleanup nop assignments.

Reviewers: george.burgess.iv, davide

Subscribers: sanjoy, jlebar, llvm-commits

Tags: #llvm

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

llvm-svn: 354612

show more ...

[EarlyCSE & MSSA] Cap the clobbering calls in EarlyCSE.

Summary:
Unlimitted number of calls to getClobberingAccess can lead to high
compile times in pathological cases.
Limitting getClobberingAccess

[EarlyCSE & MSSA] Cap the clobbering calls in EarlyCSE.

Summary:
Unlimitted number of calls to getClobberingAccess can lead to high
compile times in pathological cases.
Limitting getClobberingAccess to a fairly high number. Can be adjusted
based on users/need.
Note: this is the only user of MemorySSA currently enabled by default.
The same handling exists in LICM (disabled atm). As MemorySSA gains more
users, this logic of capping will need to move inside MemorySSA.

Reviewers: george.burgess.iv

Subscribers: llvm-commits

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

llvm-svn: 354182

show more ...

[EarlyCSE & MSSA] Cleanup special handling for removing MemoryAccesses.

Summary: Moving special handling to MemorySSAUpdater in D57199.

Reviewers: gberry, george.burgess.iv

Subscribers: sanjoy, jl

[EarlyCSE & MSSA] Cleanup special handling for removing MemoryAccesses.

Summary: Moving special handling to MemorySSAUpdater in D57199.

Reviewers: gberry, george.burgess.iv

Subscribers: sanjoy, jlebar, Prazek, llvm-commits

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

llvm-svn: 352794

show more ...

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...

[EarlyCSE] If DI can't be salvaged, mark it as unavailable.

Fixes PR39874.

llvm-svn: 349323

[EarlyCSEwMemorySSA] Add MSSA verification and tests to make EarlyCSE failures easier to track.

Summary:
EarlyCSE can make IR changes that will leave MemorySSA with accesses claiming to be optimized

[EarlyCSEwMemorySSA] Add MSSA verification and tests to make EarlyCSE failures easier to track.

Summary:
EarlyCSE can make IR changes that will leave MemorySSA with accesses claiming to be optimized, but for which a subsequent MemorySSA run will yield a different optimized result.
Due to relying on AA queries, we can't fix this in general, unless we recompute MemorySSA.
Adding some tests to track this and a basic verify for future potential failures.

Reviewers: george.burgess.iv, gberry

Subscribers: sanjoy, jlebar, Prazek, llvm-commits

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

llvm-svn: 342422

show more ...

Re-enable "[NFC] Unify guards detection"

rL340921 has been reverted by rL340923 due to linkage dependency
from Transform/Utils to Analysis which is not allowed. In this patch
this has been fixed, a

Re-enable "[NFC] Unify guards detection"

rL340921 has been reverted by rL340923 due to linkage dependency
from Transform/Utils to Analysis which is not allowed. In this patch
this has been fixed, a new utility function moved to Analysis.

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

llvm-svn: 341014

show more ...

Revert r340921 "[NFC] Unify guards detection"

This broke the build, see e.g.

http://lab.llvm.org:8011/builders/clang-cmake-armv8-lnt/builds/4626/
http://lab.llvm.org:8011/builders/clang-ppc64be-lin

Revert r340921 "[NFC] Unify guards detection"

This broke the build, see e.g.

http://lab.llvm.org:8011/builders/clang-cmake-armv8-lnt/builds/4626/
http://lab.llvm.org:8011/builders/clang-ppc64be-linux-lnt/builds/18647/
http://lab.llvm.org:8011/builders/clang-cmake-x86_64-avx2-linux/builds/5856/
http://lab.llvm.org:8011/builders/lld-x86_64-freebsd/builds/22800/

> We have multiple places in code where we try to identify whether or not
> some instruction is a guard. This patch factors out this logic into a separate
> utility function which works uniformly in all places.
>
> Differential Revision: https://reviews.llvm.org/D51152
> Reviewed By: fedor.sergeev

llvm-svn: 340923

show more ...

[NFC] Unify guards detection

We have multiple places in code where we try to identify whether or not
some instruction is a guard. This patch factors out this logic into a separate
utility function w

[NFC] Unify guards detection

We have multiple places in code where we try to identify whether or not
some instruction is a guard. This patch factors out this logic into a separate
utility function which works uniformly in all places.

Differential Revision: https://reviews.llvm.org/D51152
Reviewed By: fedor.sergeev

llvm-svn: 340921

show more ...

Remove trailing space

sed -Ei 's/[[:space:]]+$//' include/**/*.{def,h,td} lib/**/*.{cpp,h}

llvm-svn: 338293

[EarlyCSE] Fix MSVC build. NFCI.

MSVC doesn't let you assign different lambdas through a ternary operator.

llvm-svn: 334715

[EarlyCSE] Propagate conditions of AND and OR instructions

This patches teaches EarlyCSE to figure out that if `and i1 %x, %y` is true then both
`%x` and `%y` are true in the taken branch, and if `o

[EarlyCSE] Propagate conditions of AND and OR instructions

This patches teaches EarlyCSE to figure out that if `and i1 %x, %y` is true then both
`%x` and `%y` are true in the taken branch, and if `or i1 %x, %y` is false then both
`%x` and `%y` are false in non-taken branch. Fix for PR37635.

Differential Revision: https://reviews.llvm.org/D47574
Reviewed By: reames

llvm-svn: 334707

show more ...

[NFC] fix trivial typos in comments

llvm-svn: 334687

Move Analysis/Utils/Local.h back to Transforms

Review feedback from r328165. Split out just the one function from the
file that's used by Analysis. (As chandlerc pointed out, the original
change onl

Move Analysis/Utils/Local.h back to Transforms

Review feedback from r328165. Split out just the one function from the
file that's used by Analysis. (As chandlerc pointed out, the original
change only moved the header and not the implementation anyway - which
was fine for the one function that was used (since it's a
template/inlined in the header) but not in general)

llvm-svn: 333954

show more ...

[NFC] Factor out a method for further extension

llvm-svn: 333633

[EarlyCSE] Improve EarlyCSE of some absolute value cases.

Change matchSelectPattern to return X and -X for ABS/NABS in a well defined order. Adjust EarlyCSE to account for this. Ensure the SPF resul

[EarlyCSE] Improve EarlyCSE of some absolute value cases.

Change matchSelectPattern to return X and -X for ABS/NABS in a well defined order. Adjust EarlyCSE to account for this. Ensure the SPF result is some kind of min/max and not abs/nabs in one place in InstCombine that made me nervous.

Prevously we returned the two operands of the compare part of the abs pattern. The RHS is always going to be a 0i, 1 or -1 constant. This isn't a very meaningful thing to return for any one. There's also some freedom in the abs pattern as to what happens when the value is equal to 0. This freedom led to early cse failing to match when different constants were used in otherwise equivalent operations. By returning the input and its negation in a defined order we can ensure an exact match. This also makes sure both patterns use the exact same subtract instruction for the negation. I believe CSE should evebntually make this happen and properly merge the nsw/nuw flags. But I'm not familiar with CSE and what order it does things in so it seemed like it might be good to really enforce that they were the same.

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

llvm-svn: 332865

show more ...

Rename DEBUG macro to LLVM_DEBUG.

The DEBUG() macro is very generic so it might clash with other projects.
The renaming was done as follows:
- git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/

Rename DEBUG macro to LLVM_DEBUG.

The DEBUG() macro is very generic so it might clash with other projects.
The renaming was done as follows:
- git grep -l 'DEBUG' | xargs sed -i 's/\bDEBUG\s\?(/LLVM_DEBUG(/g'
- git diff -U0 master | ../clang/tools/clang-format/clang-format-diff.py -i -p1 -style LLVM
- Manual change to APInt
- Manually chage DOCS as regex doesn't match it.

In the transition period the DEBUG() macro is still present and aliased
to the LLVM_DEBUG() one.

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

llvm-svn: 332240

show more ...

Remove \brief commands from doxygen comments.

We've been running doxygen with the autobrief option for a couple of
years now. This makes the \brief markers into our comments
redundant. Since they ar

Remove \brief commands from doxygen comments.

We've been running doxygen with the autobrief option for a couple of
years now. This makes the \brief markers into our comments
redundant. Since they are a visual distraction and we don't want to
encourage more \brief markers in new code either, this patch removes
them all.

Patch produced by

for i in $(git grep -l '\\brief'); do perl -pi -e 's/\\brief //g' $i & done

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

llvm-svn: 331272

show more ...

[EarlyCSE] Add debug counter for debugging mis-optimizations. NFC.

Reviewers: reames, spatel, davide, dberlin

Subscribers: mcrosier, llvm-commits

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

[EarlyCSE] Add debug counter for debugging mis-optimizations. NFC.

Reviewers: reames, spatel, davide, dberlin

Subscribers: mcrosier, llvm-commits

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

llvm-svn: 329443

show more ...

Fix a couple of layering violations in Transforms

Remove #include of Transforms/Scalar.h from Transform/Utils to fix layering.

Transforms depends on Transforms/Utils, not the other way around. So
r

Fix a couple of layering violations in Transforms

Remove #include of Transforms/Scalar.h from Transform/Utils to fix layering.

Transforms depends on Transforms/Utils, not the other way around. So
remove the header and the "createStripGCRelocatesPass" function
declaration (& definition) that is unused and motivated this dependency.

Move Transforms/Utils/Local.h into Analysis because it's used by
Analysis/MemoryBuiltins.cpp.

llvm-svn: 328165

show more ...

[EarlyCSE] Don't hide earler invariant.scopes

If we've already established an invariant scope with an earlier generation, we don't want to hide it in the scoped hash table with one with a later gene

[EarlyCSE] Don't hide earler invariant.scopes

If we've already established an invariant scope with an earlier generation, we don't want to hide it in the scoped hash table with one with a later generation. I noticed this when working on the invariant-load handling, but it also applies to the invariant.start case as well.

Without this change, my previous patch for invariant-load regresses some cases, so I'm pushing this without waiting for review. This is why you don't make last minute tweaks to patches to catch "obvious cases" after it's already been reviewed. Bad Philip!

llvm-svn: 327655

show more ...

[EarlyCSE] Reuse invariant scopes for invariant load

This is a follow up to https://reviews.llvm.org/D43716 which rewrites the invariant load handling using the new infrastructure. It's slightly mor

[EarlyCSE] Reuse invariant scopes for invariant load

This is a follow up to https://reviews.llvm.org/D43716 which rewrites the invariant load handling using the new infrastructure. It's slightly more powerful, but only in somewhat minor ways for the moment. It's not clear that DSE of stores to invariant locations is actually interesting since why would your IR have such a construct to start with?

Note: The submitted version is slightly different than the reviewed one. I realized the scope could start for an invariant load which was proven redundant and removed. Added a test case to illustrate that as well.

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

llvm-svn: 327646

show more ...

[EarlyCSE] Exploit open ended invariant.start scopes

If we have an invariant.start with no corresponding invariant.end, then the memory location becomes invariant indefinitely after the invariant.st

[EarlyCSE] Exploit open ended invariant.start scopes

If we have an invariant.start with no corresponding invariant.end, then the memory location becomes invariant indefinitely after the invariant.start. As a result, anything dominated by the start is guaranteed to see the value the memory location had when the invariant.start executed.

This patch adds an AvailableInvariants table which tracks the generation a particular memory location became invariant and then uses that information to allow value forwarding that would otherwise be disallowed by potentially aliasing stores. (Reminder: In EarlyCSE everything clobbers everything by default.)

This should be compatible with the MemorySSA variant, but design is generational. We can and should add first class support for invariant.start within MemorySSA at a later time. I took a quick look at doing so, but probably need some input from a MemorySSA expert.

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

llvm-svn: 327577

show more ...