[LLVMdev] Re: Loops

[Chris Lattner]

On Tue, 28 Feb 2006, Domagoj Babic wrote:
> Hi Chris,

Hi, for future reference, it's better to email the llvmdev list than it is 
to email me directly (even if I'm the one that ends up responding), so 
that others can see responses.

> If you remember, I mentioned on the channel that I'm planning to write a
> pass (or modify the existing code) to convert multiple-entry multiple-exit
> loops into single-entry single-exit loops. According to some results, the
> code blowup should be negligible (5% on average). The pass should be of
> linear complexity.

Ok.

> If I understood you correctly, multiple entry loops are already converted to
> single entry loops and the loop headers are separated. (Please correct me
> if I'm wrong.)

The -loopsimplify pass currently takes single-entry natural loops and 
simplifies them in various ways.  In particular, it guarantees that:

1. There is a preheader for the loop, a block that has one successor that
    branches to the header of the loop.
2. There is exactly one backedge for the loop.  Multiple backedges have an
    extra merge block inserted.  This guarantees the header has exactly two
    predecessors.
3. Exit blocks (blocks not in the loop that are reachable from the
    loop) are all dominated by the loop header, again by splitting edges
    as necessary.

If you have multiple entry (irreducible) loops, you will want to have a 
pass that converts those to single-entry loops first, then run the 
loopsimplify pass if the properties above are useful.  Following that, 
merging all of the exit blocks into a single exit block with a switch (for 
example) in it would be reasonable.

> Since the elimination of multiple exits might be useful to the LLVM
> community, I'd like to contribute the code (If deemed worthy :-) ).

Cool.

> Would you be willing to advise me on which approach should I take (a
> separate pass or modify the code), and which files should I look into?

I'd suggest writing this as multiple passes.  The first part (converting 
irreducible loops to reducible ones) would be generally quite useful by 
itself (even being on the open projects list :) ), but the "single exit" 
property is more specialized.  It would be nice to be able to pick and 
choose the properties desired.

> In the near future (by autumn) I'm also planning to write a new very
> precise alias analysis (unlikely that this would be of general interest)

Sounds fun :)

> and add GSA gamma function computation. Let me know if GSA is of any
> interest to LLVM project. Gamma functions can be computed in nearly
> linear time (linear * inv_ackerman_fun).

It would be interesting to have GSA form (I assume you mean Gated Single 
Assignment) for some purposes.  When you have it working, please let us 
know.

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/