This patch implements Loop Rotation Pass:
- Canonicalize loop latch to have only one successor.
- Clone all the BBs which are exiting the loop (There is a cost function to prevent code size increase)
- Adjust phi of cloned BBs
- Add phi to the new loop header
- Update DOM
With this patch all the basic blocks which are exiting the loop can be copied during rotation. This is helpful for passes like gvn/licm which can now remove loop invariant code
because some computations (which might not dominate all the basic blocks of loop) can now be PRE'd as they are available outside of the loop (due to loop rotation).
Several test cases have been added to exercise loop rotation for different loop bodies.
Relevant test case to demonstrate loop rotation can help gvn.
This patch depends on https://reviews.llvm.org/D22558, which is used to clone SEME.
Worked in collaboration with Sebastian Pop