[Transforms] Convert tests to opaque pointers (NFC)

[LoopFlatten] Use loop versioning when overflow can't be disproven (#78576)

Implement the TODO in loop flattening to version the loop when we can't
prove that the trip count calculation won't overf

[LoopFlatten] Use loop versioning when overflow can't be disproven (#78576)

Implement the TODO in loop flattening to version the loop when we can't
prove that the trip count calculation won't overflow.

show more ...

[Transforms] Convert some tests to opaque pointers (NFC)

These are all tests where conversion worked automatically, and
required no manual fixup.

[NFC] Port all LoopFlatten tests to `-passes=` syntax

[LoopFlatten] Fix assertion failure

There is an assertion failure in computeOverflowForUnsignedMul
(used in checkOverflow) due to the inner and outer trip counts
having different types. This occurs

[LoopFlatten] Fix assertion failure

There is an assertion failure in computeOverflowForUnsignedMul
(used in checkOverflow) due to the inner and outer trip counts
having different types. This occurs when the IV has been widened,
but the loop components are not successfully rediscovered.
This is fixed by some refactoring of the code in findLoopComponents
which identifies the trip count of the loop.

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

show more ...

[LoopFlatten] Fix missed LoopFlatten opportunity

When the limit of the inner loop is a known integer, the InstCombine
pass now causes the transformation e.g. imcp ult i32 %inc, tripcount ->
icmp ult

[LoopFlatten] Fix missed LoopFlatten opportunity

When the limit of the inner loop is a known integer, the InstCombine
pass now causes the transformation e.g. imcp ult i32 %inc, tripcount ->
icmp ult %j, tripcount-step (where %j is the inner loop induction
variable and %inc is add %j, step), which is now accounted for when
identifying the trip count of the loop. This is also an acceptable use
of %j (provided the step is 1) so is ignored as long as the compare
that it's used in is also the condition of the inner branch.

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

show more ...

Revert "[LoopFlatten] Fix missed LoopFlatten opportunity"

This reverts commit 2df8bf9339e43de63d8d28e07182e1d6d7ffb843.

Reverting because it causes an assertion failure.

[LoopFlatten] Fix missed LoopFlatten opportunity

When the trip count of the inner loop is a constant, the InstCombine
pass now causes the transformation e.g. imcp ult i32 %inc, tripcount ->
icmp ult

[LoopFlatten] Fix missed LoopFlatten opportunity

When the trip count of the inner loop is a constant, the InstCombine
pass now causes the transformation e.g. imcp ult i32 %inc, tripcount ->
icmp ult %j, tripcount-step (where %j is the inner loop induction
variable and %inc is add %j, step), which is now accounted for when
identifying the trip count of the loop. This is also an acceptable use
of %j (provided the step is 1) so is ignored as long as the compare
that it's used in is also the condition of the inner branch.

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

show more ...

[LoopFlatten] Fix bug where SCEVCouldNotCompute object is used

The SCEV method getBackedgeTakenCount() returns a SCEVCouldNotCompute
object if the backedge-taken count is unpredictable. This fix ens

[LoopFlatten] Fix bug where SCEVCouldNotCompute object is used

The SCEV method getBackedgeTakenCount() returns a SCEVCouldNotCompute
object if the backedge-taken count is unpredictable. This fix ensures
there is no longer an attempt to use such an object to find the trip
count.

Patch by: Rosie Sumpter.

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

show more ...

[LoopFlatten] Use SCEV and Loop APIs to identify increment and trip count

Replace pattern-matching with existing SCEV and Loop APIs as a more
robust way of identifying the loop increment and trip co

[LoopFlatten] Use SCEV and Loop APIs to identify increment and trip count

Replace pattern-matching with existing SCEV and Loop APIs as a more
robust way of identifying the loop increment and trip count. Also
rename 'Limit' as 'TripCount' to be consistent with terminology.

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

show more ...

[LoopFlatten] Widen the IV

Widen the IV to the widest available and legal integer type, which makes this
transformations always safe so that we can skip overflow checks.

Motivation is to let this p

[LoopFlatten] Widen the IV

Widen the IV to the widest available and legal integer type, which makes this
transformations always safe so that we can skip overflow checks.

Motivation is to let this pass trigger on 64-bit targets too, and this is the
last patch in a serie to achieve this: D90402 moves pass LoopFlatten to just
before IndVarSimplify so that IVs are not already widened, D90421 factors out
widening from IndVarSimplify into Utils/SimplifyIndVar so that we can also use
it in LoopFlatten.

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

show more ...

[LoopFlatten] Make it a FunctionPass

This converts LoopFlatten from a LoopPass to a FunctionPass so that we don't
run into problems of a loop pass deleting a (inner)loop.

Differential Revision: htt

[LoopFlatten] Make it a FunctionPass

This converts LoopFlatten from a LoopPass to a FunctionPass so that we don't
run into problems of a loop pass deleting a (inner)loop.

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

show more ...

[LoopFlatten] Add a loop-flattening pass

This is a simple pass that flattens nested loops. The intention is to optimise
loop nests like this, which together access an array linearly:

for (int i

[LoopFlatten] Add a loop-flattening pass

This is a simple pass that flattens nested loops. The intention is to optimise
loop nests like this, which together access an array linearly:

for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
f(A[i*M+j]);

into one loop:

for (int i = 0; i < (N*M); ++i)
f(A[i]);

It can also flatten loops where the induction variables are not used in the
loop. This can help with codesize and runtime, especially on simple cpus
without advanced branch prediction.

This is only worth flattening if the induction variables are only used in an
expression like i*M+j. If they had any other uses, we would have to insert a
div/mod to reconstruct the original values, so this wouldn't be profitable.

This partially fixes PR40581 as this pass triggers on one of the two cases. I
will follow up on this to learn LoopFlatten a few more (small) tricks. Please
note that LoopFlatten is not yet enabled by default.

Patch by Oliver Stannard, with minor tweaks from Dave Green and myself.

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

show more ...