[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][LoopInfo] Use Loop to identify latch compare instruction

Make getLatchCmpInst non-static and use it in LoopFlatten as a more
robust way of identifying the compare.

Differential Revisi

[LoopFlatten][LoopInfo] Use Loop to identify latch compare instruction

Make getLatchCmpInst non-static and use it in LoopFlatten as a more
robust way of identifying the compare.

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

show more ...

[LoopFlatten] Use Loop to identify loop induction phi. NFC

Replace code which identifies induction phi with helper function
getInductionVariable to improve robustness.

Differential Revision: https:

[LoopFlatten] Use Loop to identify loop induction phi. NFC

Replace code which identifies induction phi with helper function
getInductionVariable to improve robustness.

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

show more ...

[LoopNest][LoopFlatten] Change LoopFlattenPass to LoopNest pass

This patch changes LoopFlattenPass from FunctionPass to LoopNestPass.

Utilize LoopNest and let function 'Flatten' generate informatio

[LoopNest][LoopFlatten] Change LoopFlattenPass to LoopNest pass

This patch changes LoopFlattenPass from FunctionPass to LoopNestPass.

Utilize LoopNest and let function 'Flatten' generate information from it.

Reviewed By: Whitney

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

show more ...

Revert "[LoopNest][LoopFlatten] Change LoopFlattenPass to LoopNest pass"

This reverts commit 7952ddb21fb7e086d5a6f97767f235d2f6ae2176.

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

Revert "[LoopNest][LoopFlatten] Change LoopFlattenPass to LoopNest pass"

This reverts commit ffc4d3e06855550a8bd2a691f6d05828d5bf4ddf.

[LoopNest][LoopFlatten] Change LoopFlattenPass to LoopNest pass

This patch changes LoopFlattenPass from FunctionPass to LoopNestPass.

Utilize LoopNest and let function 'Flatten' generate informatio

[LoopNest][LoopFlatten] Change LoopFlattenPass to LoopNest pass

This patch changes LoopFlattenPass from FunctionPass to LoopNestPass.

Utilize LoopNest and let function 'Flatten' generate information from it.

Reviewed By: Whitney

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

show more ...

[LoopNest][LoopFlatten] Change LoopFlattenPass to LoopNest pass

This patch changes LoopFlattenPass from FunctionPass to LoopNestPass.

Utilize LoopNest and let function 'Flatten' generate informatio

[LoopNest][LoopFlatten] Change LoopFlattenPass to LoopNest pass

This patch changes LoopFlattenPass from FunctionPass to LoopNestPass.

Utilize LoopNest and let function 'Flatten' generate information from it.

Reviewed By: Whitney

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

show more ...

[LoopFlatten] Simplify loops so that the pass can operate on unsimplified loops.

The loop flattening pass requires loops to be in simplified form. If the
loops are not in simplified form, the pass c

[LoopFlatten] Simplify loops so that the pass can operate on unsimplified loops.

The loop flattening pass requires loops to be in simplified form. If the
loops are not in simplified form, the pass cannot operate. This patch
simplifies all loops before flattening. As a result, all loops will be
simplified regardless of whether anything ends up being flattened.

This change was inspired by observing a certain loop that was not flatten
because the loops were not in simplified form. This loop is added as a
test to verify that it is now flattened.

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

Change-Id: I45bcabe70fb99b0d89f0effafc82eb9e0585ec30

show more ...

LoopFlatten - CanWidenIV - Fix uninitialized variable warnings and use for-range loop. NFCI.

Fix static analysis uninitialized variable warnings, and use for-range loop iteration across WideIVs arra

LoopFlatten - CanWidenIV - Fix uninitialized variable warnings and use for-range loop. NFCI.

Fix static analysis uninitialized variable warnings, and use for-range loop iteration across WideIVs array.

show more ...

[LoopFlatten] Do not report CFG analyses as up-to-date

Removes CFGAnalyses from the preserved analyses set
returned by LoopFlattenPass::run().

Reviewed By: Dave Green, Ta-Wei Tu

Differential Revis

[LoopFlatten] Do not report CFG analyses as up-to-date

Removes CFGAnalyses from the preserved analyses set
returned by LoopFlattenPass::run().

Reviewed By: Dave Green, Ta-Wei Tu

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

show more ...

[NFC] Improve debug message and test description in 4c1f74a

[LoopFlatten] Fix invalid assertion (PR49571)

The `InductionPHI` is not necessarily the increment instruction, as
demonstrated in pr49571.ll.
This patch removes the assertion and instead bails out f

[LoopFlatten] Fix invalid assertion (PR49571)

The `InductionPHI` is not necessarily the increment instruction, as
demonstrated in pr49571.ll.
This patch removes the assertion and instead bails out from the
`LoopFlatten` pass if that happens.

This fixes https://bugs.llvm.org/show_bug.cgi?id=49571

Reviewed By: SjoerdMeijer

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

show more ...

[NFC] Remove redundant `struct` prefix

Reviewed By: SjoerdMeijer, fhahn

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

NFC: Migrate LoopFlatten to work on InstructionCost.

This patch migrates cost values and arithmetic to work on InstructionCost.
When the interfaces to TargetTransformInfo are changed, any Instructio

NFC: Migrate LoopFlatten to work on InstructionCost.

This patch migrates cost values and arithmetic to work on InstructionCost.
When the interfaces to TargetTransformInfo are changed, any InstructionCost
state will propagate naturally.

See this patch for the introduction of the type: https://reviews.llvm.org/D91174
See this thread for context: http://lists.llvm.org/pipermail/llvm-dev/2020-November/146408.html

Reviewed By: david-arm

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

show more ...

[LoopFlatten] Widen IV, support ZExt.

I disabled the widening in fa5cb4b because it run in an assert, which was
related to replacing values with different types. I forgot that an extend could
also b

[LoopFlatten] Widen IV, support ZExt.

I disabled the widening in fa5cb4b because it run in an assert, which was
related to replacing values with different types. I forgot that an extend could
also be a zero-extend, which I have added now. This means that the approach now
is to create and insert a trunc value of the outerloop for each user, and use
that to replace IV values.

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

show more ...

[LoopFlatten] Disable IV widening

Disable widening of the IV in LoopFlatten while I investigate an assertion
failures. Please note that the pass is also not yet enabled by default.

[LoopFlatten] Fold variable into assert. NFC.

[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] FlattenInfo bookkeeping. NFC.

Introduce struct FlattenInfo to group some of the bookkeeping. Besides this
being a bit of a clean-up, it is a prep step for next additions (D90640). I
co

[LoopFlatten] FlattenInfo bookkeeping. NFC.

Introduce struct FlattenInfo to group some of the bookkeeping. Besides this
being a bit of a clean-up, it is a prep step for next additions (D90640). I
could take things a bit further, but thought this was a good first step also
not to make this change too large.

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

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