[UnJ] Add debug messages for why loops are not unrolled. NFC

Adds some cleaned up debug messages from back when I was writing this.
Hopefully useful to others (and myself) as to why unroll and jam i

[UnJ] Add debug messages for why loops are not unrolled. NFC

Adds some cleaned up debug messages from back when I was writing this.
Hopefully useful to others (and myself) as to why unroll and jam is not
transforming as expected.

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

llvm-svn: 338676

show more ...

[UnJ] Common some code. NFC

Create a processHeaderPhiOperands for analysing the instructions
in the aft blocks that must be moved before the loop.

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

[UnJ] Common some code. NFC

Create a processHeaderPhiOperands for analysing the instructions
in the aft blocks that must be moved before the loop.

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

llvm-svn: 338033

show more ...

[UnJ] Use SmallPtrSets for block collections. NFC

We no longer care about the order of blocks in these collections,
so can change to SmallPtrSets, making contains checks quicker.

Differential revis

[UnJ] Use SmallPtrSets for block collections. NFC

We no longer care about the order of blocks in these collections,
so can change to SmallPtrSets, making contains checks quicker.

Differential revision: https://reviews.llvm.org/D49060

llvm-svn: 336897

show more ...

[UnrollAndJam] New Unroll and Jam pass

This is a simple implementation of the unroll-and-jam classical loop
optimisation.

The basic idea is that we take an outer loop of the form:

for i..
Fo

[UnrollAndJam] New Unroll and Jam pass

This is a simple implementation of the unroll-and-jam classical loop
optimisation.

The basic idea is that we take an outer loop of the form:

for i..
ForeBlocks(i)
for j..
SubLoopBlocks(i, j)
AftBlocks(i)

Instead of doing normal inner or outer unrolling, we unroll as follows:

for i... i+=2
ForeBlocks(i)
ForeBlocks(i+1)
for j..
SubLoopBlocks(i, j)
SubLoopBlocks(i+1, j)
AftBlocks(i)
AftBlocks(i+1)
Remainder Loop

So we have unrolled the outer loop, then jammed the two inner loops into
one. This can lead to a simpler inner loop if memory accesses can be shared
between the now jammed loops.

To do this we have to prove that this is all safe, both for the memory
accesses (using dependence analysis) and that ForeBlocks(i+1) can move before
AftBlocks(i) and SubLoopBlocks(i, j).

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

llvm-svn: 336062

show more ...

[UnrollAndJam] Add a new Unroll and Jam pass

This is a simple implementation of the unroll-and-jam classical loop
optimisation.

The basic idea is that we take an outer loop of the form:

for i..

[UnrollAndJam] Add a new Unroll and Jam pass

This is a simple implementation of the unroll-and-jam classical loop
optimisation.

The basic idea is that we take an outer loop of the form:

for i..
ForeBlocks(i)
for j..
SubLoopBlocks(i, j)
AftBlocks(i)

Instead of doing normal inner or outer unrolling, we unroll as follows:

for i... i+=2
ForeBlocks(i)
ForeBlocks(i+1)
for j..
SubLoopBlocks(i, j)
SubLoopBlocks(i+1, j)
AftBlocks(i)
AftBlocks(i+1)
Remainder

So we have unrolled the outer loop, then jammed the two inner loops into
one. This can lead to a simpler inner loop if memory accesses can be shared
between the now-jammed loops.

To do this we have to prove that this is all safe, both for the memory
accesses (using dependence analysis) and that ForeBlocks(i+1) can move before
AftBlocks(i) and SubLoopBlocks(i, j).

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

llvm-svn: 333358

show more ...