Any options that enable loop inversion in LLVM?

Question

Are there any options that enable loop inversion? More specifically，can LLVM transform the while form loop into do-while form loop as the following.

Before the transformation, the code is:

void foo(unsigned a, unsigned& ret) {
  bool undone = true;
  #pragma unroll 4
  while((a > 0) && undone) {
    ++ret;
    if(ret > 2)  undone = false;
    if(undone)   --a;
  }
}

After the transformation, the code is:

void foo(unsigned a, unsigned& ret) {
  bool undone = true;
  #pragma unroll 4
  if((a > 0) && undone) {
    do {
      ++ret;
      if(ret > 2)  undone = false;
      if(undone)   --a;
    while((a > 0) && undone);
  }
}

I have use the opt pass and enable the loop-rotate option and loop-simplify option. However, the loop inversion transformation is not implemented.

Answer 1

LLVM does exactly the transformation you requested with the standard optimization pipeline used by Clang at -O2 (and most other frontends built on LLVM). So the direct answer to your question is "-O2". It isn't a single pass as you need to enable the complete pipeline of optimizations that work together to accomplish this.

To see all of this in action, let's look at compiler explorer for your example code with Clang v15 (a fixed version so the line numbers are stable): https://cpp.compiler-explorer.com/z/o73nEP6r5

On line 3 of the assembly and line 9 of the LLVM IR you'll see a conditional branch. This branch is outside of the loop, and precisely corresponds to the if((a > 0) && undone) condition in your desired result. At that point, undone is a constant (true) and so folds away and the conditional branch only checks a > 0 prior to entering the loop. Again, this condition is outside of the loop and is never revisited.

Below that, you'll see this line in the assembly output:

.LBB0_2:                                # =>This Inner Loop Header: Depth=1

This label marks a basic block of machine code, and the comment at the end comes from LLVM's loop analysis and shows that this is the "loop header"[1], the top basic block of the actual looping code, and it corresponds to where the do { starts in your desired transformation.

As Nick Lewycky pointed out in the comments, the specific LLVM pass that does the specific transform you describe is 'loop-rotate', and I agree with his comment that it is a superset of what you are describing. However, you can't enable it in isolation. To see how LLVM builds up a set of loop passes that work well, see the pipeline here and the large body of code preceding it that schedules all the other relevant transforms: https://github.com/llvm/llvm-project/blob/main/llvm/lib/Passes/PassBuilderPipelines.cpp#L531,L609