[Soot-list] Any suggestions to find the end of a loop?

[Eric Bodden]

I just double-checked on this. Soot creates the following body for
this method when producing Jimple from bytecode that was produced with
Eclipse:

    private static void foo()
    {
        int $i0, i1, $i2, $i3, $i4;

        $i0 = <Foo: int calls>;
        $i2 = $i0 + 1;
        <Foo: int calls> = $i2;
        i1 = 0;
        goto label1;

     label0:
        $i3 = <Foo: int loopcnt1>;
        $i4 = $i3 + 1;
        <Foo: int loopcnt1> = $i4;
        staticinvoke <Foo: void bar()>();
        i1 = i1 + 1;

     label1:
        if i1 < 3 goto label0;

        staticinvoke <Foo: void bar1()>();
        return;
    }

For this example, MHGPostDominatorsFinder tells me that "staticinvoke
<Foo: void bar1()>();" is the immediate post-dominator for the loop
head "if i1 < 3 goto label0;" and that all of...

return,
if i1 < 3 goto $i3 = <Foo: int loopcnt1>,
staticinvoke <Foo: void bar1()>()

... are post-dominators of this same loop head. This looks correct to
me. (Note that every statement post-dominates itself.)

Eric


2009/7/29 Kelvin Tian <kevinn.tian at gmail.com>:
> Dear Eric,
>
>     Thanks for the reply.  I can find the end of loop now except one
> scenario, which has a function call below the loop.  In the example code
> below,  I found the loop header and its successors and post-dominator as
> follows.
>
>     private static void foo() {
>         calls++;
>         for (int i = 0; i < 3; i++)
>            {
>             loopcnt1++;
>             bar();
>         }
>
>         bar1();
>     }
>
> loop header:   if i1 >= 3 goto staticinvoke <TestLoop: void bar1()>()
> loop header's post-dominator:   [return, if i1 >= 3 goto staticinvoke
> <TestLoop: void bar1()>()]
> loop header's successor:    [$i3 = <TestLoop: int loopcnt1>, staticinvoke
> <TestLoop: void bar1()>()]
>
> So I see in Soot, the loop header connects two statements together, without
> labels . The loop header's post-dominators include "return" and itself,
> while don't include the statement "bar1()" after the loop because the loop
> header already contains calling to "bar1()".  But the loop header's
> successors include the original statement "bar1()" after the loop,  so in
> this case I can't find the end of the loop.  So it seems loop header has two
> different representations when getting its post-dominator and its
> successors.  Is this conflict an original design or a possible bug? Are
> there any suggestions? Thanks again for your help!
>
>
> --
> Best regards,
> Kelvin
>
>
>
> On Mon, Jul 27, 2009 at 3:45 PM, Eric Bodden <eric.bodden at mail.mcgill.ca>
> wrote:
>>
>> Hi Kelvin.
>>
>> I wound have done it the same way - sounds reasonable to me.
>>
>> Eric
>>
>> 2009/7/27 Kelvin Tian <kevinn.tian at gmail.com>:
>> > I need to identify the end of a loop and to print out some profiling
>> > info
>> > after a loop's execution.  One way I've got to identify the end of a
>> > loop is
>> > to find the loop head, and iterate through its successors, as the
>> > statements
>> > in loop body can't be the post-dominator of the loop head, so when I
>> > meet
>> > with a statement which is a post dominator of the loop head,  then the
>> > end
>> > of a loop is found.   Is this way applicable for Soot to implement or
>> > are
>> > there any better suggestions?  Thanks for any suggestions!
>> >
>> >
>> > --
>> > Best regards,
>> > Kelvin
>> >
>> >
>> > _______________________________________________
>> > Soot-list mailing list
>> > Soot-list at sable.mcgill.ca
>> > http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>> >
>> >
>>
>>
>>
>> --
>> Eric Bodden
>> Software Technology Group
>> Technical University Darmstadt, Germany
>
>



-- 
Eric Bodden
Software Technology Group
Technical University Darmstadt, Germany