LoopInterchange Pass

Project Infrastructure LLVM Dev List Archives
1


Hi,

I developed a Loop Interchange pass. Please take a look.
I have not incorporate data dependence analysis check. I can insert it when the LoopDependenceAnalysis is available.

Thank you
Satya
|

sum.c (1.69 KB)

t.c (1.75 KB)

README.txt (1.24 KB)

LoopInterchange.cpp (19.2 KB)

2

Owen, comments?

Evan

3

Hi Satya,


Hi,

I developed a Loop Interchange pass. Please take a look.
I have not incorporate data dependence analysis check. I can insert it when the LoopDependenceAnalysis is available.
|

  • |

Have you tried using include/llvm/Analysis/LoopDependenceAnalysis.h ?

Please include all the changes listed in README.txt in the patch along with a test case that is in .ll form. It makes easier to review such complete patch.

Few general comments and initial thoughts.

  • Stay within 80 columns
  • Add comment before each function def.
  • Use at least one vertical space between function def.
  • There is cut-n-paste error in runOnLoop() where the code checks LCSSA form.

std::vector<std::pair<Loop*,Loop*> > interchangedLoops;

This may not be the most reliable way to keep track of interchangedLoops. This vector must be recomputed if loop info is recreated. It must be updated if a loop is replaced or deleted by another pass.

void LoopInterchange::updateDominators …

However the pass does not preserve dominators info.

void LoopInterchange::removeChildLoop

It is a good idea to use another name for this method to avoid any confusion with Loop::removeChildLoop.

What is the difference between updateSSA() and updateSSAAgain() ?

4

Hi Devang,

Thanks for the feed back.
I took care of function naming and limiting comments to 80 columns.
I am looking into implementing Loop Dependence Analysis. As of release 2.7 no data dependence analysis is being done.

Satya

5

Hello Satya,

Besides dependence analysis, the other main thing that appears
to be missing before this code is generally usable is code to
decide when interchange is likely to be profitable. A simple
heuristic which just aims to put loops that drive
stride-one memory accesses on the inside would probably go a
long way, given that LLVM isn't doing many other loop
restructuring optimizations at this time.

Dan