[SCEV] Use a SmallPtrSet as a temporary union predicate; NFC

Summary:
Instead of creating and destroying SCEVUnionPredicate instances (which
internally creates and destroys a DenseMap), use temporar

[SCEV] Use a SmallPtrSet as a temporary union predicate; NFC

Summary:
Instead of creating and destroying SCEVUnionPredicate instances (which
internally creates and destroys a DenseMap), use temporary SmallPtrSet
instances of remember the set of predicates that will get reified into a
SCEVUnionPredicate.

Reviewers: silviu.baranga, sbaranga

Subscribers: sanjoy, mcrosier, llvm-commits, mzolotukhin

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

llvm-svn: 282606

show more ...

[SCEV] Replace a struct with a function; NFC

We can do this now thanks to C++11 lambdas.

llvm-svn: 282515

[SCEV] Use find instead of find_as; NFC

We don't need the extra generality here.

llvm-svn: 282514

[SCEV] Reduce the scope of a struct; NFC

llvm-svn: 282513

[SCEV] Remove custom RAII wrapper; NFC

Instead use the pre-existing `scope_exit` class.

llvm-svn: 282512

[SCEV] Make PendingLoopPredicates more frugal; NFCI

I don't expect `PendingLoopPredicates` to have very many
elements (e.g. when -O3'ing the sqlite3 amalgamation,
`PendingLoopPredicates` has at most

[SCEV] Make PendingLoopPredicates more frugal; NFCI

I don't expect `PendingLoopPredicates` to have very many
elements (e.g. when -O3'ing the sqlite3 amalgamation,
`PendingLoopPredicates` has at most 3 elements). So now we use a
`SmallPtrSet` for it instead of the more heavyweight `DenseSet`.

llvm-svn: 282511

show more ...

[SCEV] Fix the order of members in the initializer list.

Noticed due to the warning on this line. Sanjoy is on
a less-than-awesome internet connection, so committing on his behalf.

llvm-svn: 282380

[SCEV] Assign LoopPropertiesCache in the move constructor

In a previous change I collapsed two different caches into one. When
doing that I noticed that ScalarEvolution's move constructor was not
m

[SCEV] Assign LoopPropertiesCache in the move constructor

In a previous change I collapsed two different caches into one. When
doing that I noticed that ScalarEvolution's move constructor was not
moving those caches.

To keep the previous change simple, I've moved that bugfix into this
separate change.

llvm-svn: 282376

show more ...

[SCEV] Combine two predicates into one; NFC

Both `loopHasNoSideEffects` and `loopHasNoAbnormalExits` involve walking
the loop and maintaining similar sorts of caches. This commit changes
SCEV to co

[SCEV] Combine two predicates into one; NFC

Both `loopHasNoSideEffects` and `loopHasNoAbnormalExits` involve walking
the loop and maintaining similar sorts of caches. This commit changes
SCEV to compute both the predicates via a single walk, and maintain a
single cache instead of two.

llvm-svn: 282375

show more ...

[SCEV] Make it obvious BackedgeTakenInfo's constructor steals storage

Specifically, it moves SCEVUnionPredicates from its input into its own
storage. Make this obvious at the type level.

llvm-svn:

[SCEV] Make it obvious BackedgeTakenInfo's constructor steals storage

Specifically, it moves SCEVUnionPredicates from its input into its own
storage. Make this obvious at the type level.

llvm-svn: 282374

show more ...

[SCEV] Further isolate incidental data structure; NFC

llvm-svn: 282373

[SCEV] Simplify BackedgeTakenInfo::getMax; NFC

llvm-svn: 282372

[SCEV] Reserve space in SmallVector; NFC

llvm-svn: 282368

[SCEV] Have ExitNotTakenInfo keep a pointer to its predicate; NFC

SCEVUnionPredicate is a "heavyweight" structure, so it is beneficial to
store the (optional) data out of line.

llvm-svn: 282366

[SCEV] Simplify tracking ExitNotTakenInfo instances; NFC

This change simplifies a data structure optimization in the
`BackedgeTakenInfo` class for loops with exactly one computable exit.

I've sanit

[SCEV] Simplify tracking ExitNotTakenInfo instances; NFC

This change simplifies a data structure optimization in the
`BackedgeTakenInfo` class for loops with exactly one computable exit.

I've sanity checked that this does not regress compile time performance,
using sqlite3's amalgamated build.

llvm-svn: 282365

show more ...

[SCEV] Rename a couple of fields; NFC

llvm-svn: 282364

[SCEV] Remove incidental data structure; NFC

llvm-svn: 282363

Reapplying r278731 after fixing the problem that caused it to be reverted.

Enhance SCEV to compute the trip count for some loops with unknown stride.

Patch by Pankaj Chawla

Differential Revision:

Reapplying r278731 after fixing the problem that caused it to be reverted.

Enhance SCEV to compute the trip count for some loops with unknown stride.

Patch by Pankaj Chawla

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

llvm-svn: 281732

show more ...

SCEV: Don't assert about non-SCEV-able value in isSCEVExprNeverPoison() (PR28932)

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

llvm-svn: 278999

Replace a few more "fall through" comments with LLVM_FALLTHROUGH

Follow up to r278902. I had missed "fall through", with a space.

llvm-svn: 278970

Revert "Enhance SCEV to compute the trip count for some loops with unknown stride."

This reverts commit r278731. It caused http://crbug.com/638314

llvm-svn: 278853

Enhance SCEV to compute the trip count for some loops with unknown stride.

Patch by Pankaj Chawla

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

llvm-svn: 278731

Use the range variant of remove_if instead of unpacking begin/end

No functionality change is intended.

llvm-svn: 278475

Recommit "Use ValueOffsetPair to enhance value reuse during SCEV expansion".

The fix for PR28705 will be committed consecutively.

In D12090, the ExprValueMap was added to reuse existing value durin

Recommit "Use ValueOffsetPair to enhance value reuse during SCEV expansion".

The fix for PR28705 will be committed consecutively.

In D12090, the ExprValueMap was added to reuse existing value during SCEV expansion.
However, const folding and sext/zext distribution can make the reuse still difficult.

A simplified case is: suppose we know S1 expands to V1 in ExprValueMap, and
S1 = S2 + C_a
S3 = S2 + C_b
where C_a and C_b are different SCEVConstants. Then we'd like to expand S3 as
V1 - C_a + C_b instead of expanding S2 literally. It is helpful when S2 is a
complex SCEV expr and S2 has no entry in ExprValueMap, which is usually caused
by the fact that S3 is generated from S1 after const folding.

In order to do that, we represent ExprValueMap as a mapping from SCEV to
ValueOffsetPair. We will save both S1->{V1, 0} and S2->{V1, C_a} into the
ExprValueMap when we create SCEV for V1. When S3 is expanded, it will first
expand S2 to V1 - C_a because of S2->{V1, C_a} in the map, then expand S3 to
V1 - C_a + C_b.

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

llvm-svn: 278160

show more ...

Consistently use FunctionAnalysisManager

Besides a general consistently benefit, the extra layer of indirection
allows the mechanical part of https://reviews.llvm.org/D23256 that
requires touching e

Consistently use FunctionAnalysisManager

Besides a general consistently benefit, the extra layer of indirection
allows the mechanical part of https://reviews.llvm.org/D23256 that
requires touching every transformation and analysis to be factored out
cleanly.

Thanks to David for the suggestion.

llvm-svn: 278077

show more ...