Detect if a basicblock is part of a loop

Hi,

I'm trying to detect if a basicblock is part of a loop or not.

I tried the llvm::LoopInfo like that (http://llvm.org/docs/doxygen/html/classllvm_1_1LoopInfo.html#a4abca289c73cd09487e05d11d9f7d877):

LoopInfo *loop = new LoopInfo();
bool isLoop = loop->getLoopFor(myBB); // getLoopFor - Return the inner most loop that BB lives in. If a basic block is in no loop (for example the entry node), null is returned. See doxygen

But getLoopFor() always return me NULL even if my basicblock is inside a for loop...
I tried this: http://comments.gmane.org/gmane.comp.compilers.llvm.devel/38490 but it didn't work too :frowning:

Any advice?
Thx

Rinaldini,

What exactly did you run? Specifically, you may be missing some
analysis passes that are necessary for LoopInfo to have the loop
information you desire.

-Hal

Hi Rinaldini,

In order to find information about loops inside a given function you should use something like “LoopInfo *LI = P->getAnalysis()”, remembering to add “AU.addRequired();” to your getAnalysisUsage method.

If the function you are interested to is not located in the module being compiled (if you created it as an auxiliary function, for example), you could create this information by simply creating a DominatorTreeBase of your function and using it to calculate the LoopInfo, as below:

DominatorTreeBase *DTB;
DTB = new DominatorTreeBase(false);
DTB->recalculate(*AuxFunction);

LoopInfoBase<BasicBlock, Loop> LIB;

LIB.Calculate(*DTB);

Cheers,

Hi,

Depending on what have run before your pass, the loop may have been unrolled or simplified if the computation inside the loop is too simple.

Cheers,

Thx all for the quick answers...

De : llvmdev-bounces@cs.uiuc.edu [llvmdev-bounces@cs.uiuc.edu] de la part de Arnaud ALLARD DE GRANDMAISON [arnaud.allarddegrandmaison@parrot.com]

Hi,

Depending on what have run before your pass, the loop may have been unrolled or simplified if the computation inside the loop is too simple.

Cheers,
--
Arnaud de Grandmaison

Just as I said to Hal, nothing else than:
$ clang -emit-llvm -S -o main.ll main.c
$ ../build/Release/bin/opt -load ../build/Release/lib/LLVMobfuscationTest.so -flattening -S main.ll -o main.opt.ll

From: llvmdev-bounces@cs.uiuc.edu [llvmdev-bounces@cs.uiuc.edu] On Behalf Of Cristianno Martins [cristiannomartins@gmail.com]

Hi Rinaldini,

In order to find information about loops inside a given function you should use something like "LoopInfo *LI = P->getAnalysis<LoopInfo>()", remembering to add "AU.addRequired<LoopInfo>();" to your getAnalysisUsage method.

If the function you are interested to is not located in the module being compiled (if you created it as an auxiliary function, for example), you could create this information by simply creating a DominatorTreeBase of your function and using it to calculate the LoopInfo, as below:
    DominatorTreeBase<BasicBlock> *DTB;
    DTB = new DominatorTreeBase<BasicBlock>(false);
    DTB->recalculate(*AuxFunction);

    LoopInfoBase<BasicBlock, Loop> LIB;
    LIB.Calculate(*DTB);

Cheers,

--
Cristianno Martins
PhD Student of Computer Science
University of Campinas
cmartins@ic.unicamp.br

Thx, I'll try that... I guess I missed the Dominator step last time

I'm running opt with my lib on a ir code emmitted by clang: $ clang -emit-llvm -S -o main.ll main.c
and opt: $ ../build/Release/bin/opt -load ../build/Release/lib/LLVMobfuscationTest.so -flattening -S main.ll -o main.opt.ll

  What's the clang default opt level? Maybe you should use "-O0" explicitly.

Regards,
chenwj

I got the same code with or without -O0 opt level
It seems that clang default opt level is 0...

Cheers

Just as I said to Hal, nothing else than:
$ clang -emit-llvm -S -o main.ll main.c
$ ../build/Release/bin/opt -load ../build/Release/lib/LLVMobfuscationTest.so -flattening -S main.ll -o main.opt.ll

  Then you might need to past your main.c. Besides, is LLVMobfuscationTest.so
your own pass? What does it do?

Regards,
chenwj

This is my main.c (just a crappy test file):

#include <stdlib.h>

void foo() {
        foo();
}

int main(int argc,char** argv) {
        int a = 1;
        int b = 3;
        int c = a+b;

        int k;
        for(k=0;k<10;++k) { // The loop I'm trying to detect
                int sdf = 123123;
                c++;
        }

        if(c - atoi(argv[1]) < 4)
                c = 0;
        else
                c = 1;

        return c;
}

The ir code corresponding to the loop:

; <label>:7 ; preds = %13, %0
  %8 = load i32* %k, align 4
  %9 = icmp slt i32 %8, 10
  br i1 %9, label %10, label %16

; <label>:10 ; preds = %7
  store i32 123123, i32* %sdf, align 4
  %11 = load i32* %c, align 4
  %12 = add nsw i32 %11, 1
  store i32 %12, i32* %c, align 4
  br label %13

; <label>:13 ; preds = %10
  %14 = load i32* %k, align 4
  %15 = add nsw i32 %14, 1
  store i32 %15, i32* %k, align 4
  br label %7

is LLVMobfuscationTest.so your own pass? What does it do?

Yes it's my own lib... It contains some obfuscation's passes. The one I'm trying to make now is making code flattening!

Cheers

ps: I tried Cristianno Martins solution, but it didn't work too :frowning:

Yes it's my own lib... It contains some obfuscation's passes. The one I'm trying to make now is making code flattening!

                                                                                                  ^^^^^^^^^^^^^^^^^^^^^^
  What's the flattening effect? Maybe try NOT to flat it first?

Regards,
chenwj

It try to put all basicblock in a switch in a loop, like that for example:

int main() {
    if(something)
         somethingelse:
    else
          another;
}

become:

int main() {
    while(true) {
        switch(var) {
            case 0:
                 if(something)
                    var+=1;
                 else:
                     var+=2;
                  break;
              case1:
                    somethingelse;
                    var = MAX;
                    break;
               case2:
                     another;
                      var = MAX;
               case MAX:
                      exit();
           }
      }
}

But I'm trying that before any attempt of code flattening, just to see if I can detect loop...

Cheers

Hi there,

I just tried Cristianno Martins solution again and it's working... I don't know what was wrong last time :frowning:

Thx all for answers
Cheers