Detect if a basicblock is part of a loop

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

Detect if a basicblock is part of a loop

Rinaldini Julien
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 :(

Any advice?
Thx

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Detect if a basicblock is part of a loop

Hal Finkel
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

On Thu, 26 Apr 2012 14:02:04 +0000
Rinaldini Julien <[hidden email]> wrote:

> 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 :(
>
> Any advice?
> Thx
>
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev



--
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Detect if a basicblock is part of a loop

Cristianno Martins
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

On Thursday, 26 de April de 2012 at 11:57, Hal Finkel wrote:

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

On Thu, 26 Apr 2012 14:02:04 +0000
Rinaldini Julien <[hidden email]> wrote:

Hi,

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

I tried the llvm::LoopInfo like that

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:
it didn't work too :(

Any advice?
Thx

_______________________________________________
LLVM Developers mailing list



--
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory
_______________________________________________
LLVM Developers mailing list


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Detect if a basicblock is part of a loop

Arnaud A. de Grandmaison
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

________________________________________
From: [hidden email] [[hidden email]] On Behalf Of Cristianno Martins [[hidden email]]
Sent: Thursday, April 26, 2012 5:52 PM
To: Hal Finkel
Cc: [hidden email]
Subject: Re: [LLVMdev] Detect if a basicblock is part of a loop

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
[hidden email]


On Thursday, 26 de April de 2012 at 11:57, Hal Finkel wrote:

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

On Thu, 26 Apr 2012 14:02:04 +0000
Rinaldini Julien <[hidden email]<mailto:[hidden email]>> wrote:

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 :(

Any advice?
Thx

_______________________________________________
LLVM Developers mailing list
[hidden email]..edu http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev



--
Hal Finkel
Postdoctoral Appointee
Leadership Computing Facility
Argonne National Laboratory
_______________________________________________
LLVM Developers mailing list
[hidden email] http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

RE : Detect if a basicblock is part of a loop

Rinaldini Julien
Thx all for the quick answers...

> De : [hidden email] [[hidden email]] de la part de Arnaud ALLARD DE GRANDMAISON [[hidden email]]
>
> 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: [hidden email] [[hidden email]] On Behalf Of Cristianno Martins [[hidden email]]

> 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
> [hidden email]

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

> On Thursday, 26 de April de 2012 at 11:57, Hal Finkel wrote:
>
> 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

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

No others optimization applied...


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RE : Detect if a basicblock is part of a loop

陳韋任 (Wei-Ren Chen)
> 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

--
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667
Homepage: http://people.cs.nctu.edu.tw/~chenwj

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

RE : RE : Detect if a basicblock is part of a loop

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

Cheers
________________________________________
De : 陳韋任 [[hidden email]]
Date d'envoi : vendredi 27 avril 2012 14:14
À : Rinaldini Julien
Cc: [hidden email]
Objet : Re: [LLVMdev] RE :  Detect if a basicblock is part of a loop

> 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

--
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667
Homepage: http://people.cs.nctu.edu.tw/~chenwj

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RE : Detect if a basicblock is part of a loop

陳韋任 (Wei-Ren Chen)
In reply to this post by Rinaldini Julien
> 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

--
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667
Homepage: http://people.cs.nctu.edu.tw/~chenwj

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

RE : RE : Detect if a basicblock is part of a loop

Rinaldini Julien
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 :(

________________________________________
De : 陳韋任 [[hidden email]]
Date d'envoi : vendredi 27 avril 2012 14:45
À : Rinaldini Julien
Cc: [hidden email]
Objet : Re: [LLVMdev] RE :  Detect if a basicblock is part of a loop

> 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

--
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667
Homepage: http://people.cs.nctu.edu.tw/~chenwj

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: RE : RE : Detect if a basicblock is part of a loop

陳韋任 (Wei-Ren Chen)
> 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

--
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667
Homepage: http://people.cs.nctu.edu.tw/~chenwj

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

RE : RE : RE : Detect if a basicblock is part of a loop

Rinaldini Julien
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
________________________________________
De : 陳韋任 [[hidden email]]
Date d'envoi : vendredi 27 avril 2012 15:05
À : Rinaldini Julien
Cc: [hidden email]
Objet : Re: [LLVMdev] RE :  RE :  Detect if a basicblock is part of a loop

> 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

--
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667
Homepage: http://people.cs.nctu.edu.tw/~chenwj

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

RE : RE : RE : RE : Detect if a basicblock is part of a loop

Rinaldini Julien
Hi there,

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

Thx all for answers
Cheers
________________________________________
De : [hidden email] [[hidden email]] de la part de Rinaldini Julien [[hidden email]]
Date d'envoi : vendredi 27 avril 2012 15:24
À : [hidden email]
Objet : [LLVMdev] RE : RE : RE : Detect if a basicblock is part of a loop

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
________________________________________
De : 陳韋任 [[hidden email]]
Date d'envoi : vendredi 27 avril 2012 15:05
À : Rinaldini Julien
Cc: [hidden email]
Objet : Re: [LLVMdev] RE :  RE :  Detect if a basicblock is part of a loop

> 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

--
Wei-Ren Chen (陳韋任)
Computer Systems Lab, Institute of Information Science,
Academia Sinica, Taiwan (R.O.C.)
Tel:886-2-2788-3799 #1667
Homepage: http://people.cs.nctu.edu.tw/~chenwj

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev