How to change a do-while form loop into a while form loop in LLVM IR

Question

How can I change a loop in do-while form into a loop in while-form in LLVM IR?

Answer 1

Here we have a little loop example. The loops are just running through a boolean array until they find the first occurrence of true. I compiled it with clang -emit-llvm to get the optimized llvm IR.

#include <stdio.h>
#include <string.h>

int foo(bool* start){
        bool* cond = start;;
        while (*cond != true)
                cond++;
        return cond - start;
}

int bar(bool* start){
        bool* cond = start;
        do {
        }while (*(++cond) != true);
        return cond - start;
}

int main(){
        bool cond[8];
        memset(&cond, 0, sizeof(bool)*8);
        cond[5] = true;
        printf("%i %i\n", foo(cond), bar(cond));
}

The IR for the foo function (using just a while loop) looks like this:

; Function Attrs: nounwind uwtable
define i32 @_Z3fooPb(i8* %start) #0 {
  %1 = alloca i8*, align 8
  %cond = alloca i8*, align 8
  store i8* %start, i8** %1, align 8
  %2 = load i8** %1, align 8
  store i8* %2, i8** %cond, align 8
  br label %3

; <label>:3                                       ; preds = %9, %0
  %4 = load i8** %cond, align 8
  %5 = load i8* %4, align 1
  %6 = trunc i8 %5 to i1
  %7 = zext i1 %6 to i32
  %8 = icmp ne i32 %7, 1
  br i1 %8, label %9, label %12

; <label>:9                                       ; preds = %3
  %10 = load i8** %cond, align 8
  %11 = getelementptr inbounds i8* %10, i32 1
  store i8* %11, i8** %cond, align 8
  br label %3

; <label>:12                                      ; preds = %3
  %13 = load i8** %cond, align 8
  %14 = load i8** %1, align 8
  %15 = ptrtoint i8* %13 to i64
  %16 = ptrtoint i8* %14 to i64
  %17 = sub i64 %15, %16
  %18 = trunc i64 %17 to i32
  ret i32 %18
}

and for bar, which is using a do while we get:

; Function Attrs: nounwind uwtable
define i32 @_Z3barPb(i8* %start) #0 {
  %1 = alloca i8*, align 8
  %cond = alloca i8*, align 8
  store i8* %start, i8** %1, align 8
  %2 = load i8** %1, align 8
  store i8* %2, i8** %cond, align 8
  br label %3

; <label>:3                                       ; preds = %4, %0
  br label %4

; <label>:4                                       ; preds = %3
  %5 = load i8** %cond, align 8
  %6 = getelementptr inbounds i8* %5, i32 1
  store i8* %6, i8** %cond, align 8
  %7 = load i8* %6, align 1
  %8 = trunc i8 %7 to i1
  %9 = zext i1 %8 to i32
  %10 = icmp ne i32 %9, 1
  br i1 %10, label %3, label %11

; <label>:11                                      ; preds = %4
  %12 = load i8** %cond, align 8
  %13 = load i8** %1, align 8
  %14 = ptrtoint i8* %12 to i64
  %15 = ptrtoint i8* %13 to i64
  %16 = sub i64 %14, %15
  %17 = trunc i64 %16 to i32
  ret i32 %17
}

The differences are very small for bar we have one additional label and an additional br because we jump strait to the body of the loop and execute it before we evaluate the condition.

So the first thing to transform a do while is to get rid of the branch and just jump to the condition. Now its a while loop where the condition is evaluated first. That is easy. Now you have two choices how you handle the condition. You can try to modify the condition what is a realy hard task because you can put almost everything inside a loops condition. The easy way is to just copy the loop body one time (everything from ;<label>:4 to ;<label>:11) prior to the first branch of the loop. so you want change the correctness of your code and your do-while loop will become a loop (with on loop-body execution) in-front of the loop.

You can copy the loop body with CloneBasicBlock from llvm/Transforms/Utils/Cloning.h:

/// CloneBasicBlock - Return a copy of the specified basic block, but without
/// embedding the block into a particular function.  The block returned is an
/// exact copy of the specified basic block, without any remapping having been
/// performed.  Because of this, this is only suitable for applications where
/// the basic block will be inserted into the same function that it was cloned
/// from (loop unrolling would use this, for example).
///
/// Also, note that this function makes a direct copy of the basic block, and
/// can thus produce illegal LLVM code.  In particular, it will copy any PHI
/// nodes from the original block, even though there are no predecessors for the
/// newly cloned block (thus, phi nodes will have to be updated).  Also, this
/// block will branch to the old successors of the original block: these
/// successors will have to have any PHI nodes updated to account for the new
/// incoming edges.
///
/// The correlation between instructions in the source and result basic blocks
/// is recorded in the VMap map.
///
/// If you have a particular suffix you'd like to use to add to any cloned
/// names, specify it as the optional third parameter.
///
/// If you would like the basic block to be auto-inserted into the end of a
/// function, you can specify it as the optional fourth parameter.
///
/// If you would like to collect additional information about the cloned
/// function, you can specify a ClonedCodeInfo object with the optional fifth
/// parameter.
///
BasicBlock *CloneBasicBlock(const BasicBlock *BB,
                            ValueToValueMapTy &VMap,
                            const Twine &NameSuffix = "", Function *F = nullptr,
                            ClonedCodeInfo *CodeInfo = nullptr);

I hope this is a little help. Have Fun!