Find loops in LLVM bytecode

Hi,
I want to find simple loops in LLVM bytecode, and extract the basic information of the loop.

For example:
     for (i=0; i<1000; i++)
         sum += i;

I want to extract the bound [0, 1000), the loop variable "i" and the loop body (sum += i).
What should I do?

I read the LLVM API document, and find some useful classes like "Loop", "LoopInfo".
But I do not know how to use them in detail.

Could you please give me some help? A detailed usage may be more helpful.
Thanks!

Best wishes,
Jia-Ju Bai

Hi,
I want to find simple loops in LLVM bytecode, and extract the basic information of the loop.

For example:
    for (i=0; i<1000; i++)
        sum += i;

I want to extract the bound [0, 1000), the loop variable "i" and the loop body (sum += i).
What should I do?

I read the LLVM API document, and find some useful classes like "Loop", "LoopInfo".
But I do not know how to use them in detail.

Could you please give me some help? A detailed usage may be more helpful.

I think you want to look at the LoopInfoWrapperPass (see the doxygen at http://llvm.org/doxygen/classllvm_1_1LoopInfoWrapperPass.html). Your pass will use the analysis results from LoopInfoWrapperPass to get references to LoopInfo objects which can then be used to find loops (if memory serves me correctly).

Regards,

John Criswell

Hi,
I want to find simple loops in LLVM bytecode, and extract the basic information of the loop.

For example:
   for (i=0; i<1000; i++)
       sum += i;

I want to extract the bound [0, 1000), the loop variable "i" and the loop body (sum += i).
What should I do?

I read the LLVM API document, and find some useful classes like "Loop", "LoopInfo".
But I do not know how to use them in detail.

Could you please give me some help? A detailed usage may be more helpful.

I think you want to look at the LoopInfoWrapperPass (see the doxygen at http://llvm.org/doxygen/classllvm_1_1LoopInfoWrapperPass.html). Your pass will use the analysis results from LoopInfoWrapperPass to get references to LoopInfo objects which can then be used to find loops (if memory serves me correctly).

On top of that, you could be interesting in SCEV (ScalarEvolution) analysis, which will give you symbolic scalar-evolution expressions for every value in IR and for the loop trip-count.

Best regards,
Michael

Thanks, John and Michael.

But I am not used to write LLVM passes. I always write a basic transformation program to modified LLVM bytecode files.
This transformation program traverses and analyzes instructions, basicblocks and functions.
Is there a way of extracting loops used for me?

Hi,

You can take a look at the InductiveRangeCheckElimination pass - it extracts some high-level information about a loops into its own loop structure.

Hi,

another suggestion is to look at Polly (http://polly.llvm.org/) for
loop analysis. It would extract high-level information such as:

$ cat ml.c
int foo() {
    int sum = 0;
    for (int i=0; i<1000; i++)
        sum += (float)i;
    return sum;
}

$ bin\clang.exe ml.c -mllvm -polly -O3 -mllvm
-polly-detect-unprofitable -mllvm -debug -mllvm
-debug-only=polly-scops -c
    Function: foo
    Region: %for.inc---%for.end
    Max Loop Depth: 1
    Context:
    { : }
    Assumed Context:
    { : }
    Boundary Context:
    { : }
    Arrays {
        i32 MemRef_sum_04__phi[*] // Element size 4
        i32 MemRef_conv2[*] // Element size 4
    }
    Arrays (Bounds as pw_affs) {
        i32 MemRef_sum_04__phi[*] // Element size 4
        i32 MemRef_conv2[*] // Element size 4
    }
    Alias Groups (0):
        n/a
    Statements {
        Stmt_for_inc
            Domain :=
                { Stmt_for_inc[i0] : i0 <= 999 and i0 >= 0 };
            Schedule :=
                { Stmt_for_inc[i0] -> [i0] };
            MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]
                { Stmt_for_inc[i0] -> MemRef_sum_04__phi };
            ReadAccess := [Reduction Type: NONE] [Scalar: 1]
                { Stmt_for_inc[i0] -> MemRef_sum_04__phi };
            MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]
                { Stmt_for_inc[i0] -> MemRef_conv2 };
    }

(The cast to float is there because otherwise LLVM would just compute
the constant result)
The interesting information for you would be the Domain {
Stmt_for_inc[i0] : i0 <= 999 and i0 >= 0 } of the loop body
(Stmt_for_inc). The loop body content itself is not printed here.

Michael