Loops

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 :slight_smile: ).

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 :slight_smile: ), 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 :slight_smile:

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