llvm dev - May 2011 - [LLVMdev] LoopInfo are not able to identify some natural loops?

In C code, if a loop is not a natural loop, that means its loop body should
at least have one label, right? In that case, some BB out of the loop can
jump to the loop body, so the loop has more than on entry.

Does LoopInfo guarantee to identify all natural loops? This property is very
important for my pass.

regards,
Bo

On Fri, Apr 29, 2011 at 11:50 PM, Cameron Zwarich <zwarich at apple.com>
wrote:
> A natural loop is one whose header dominates all of the nodes in the loop.
> There is probably some block outside of the loop jumping to a block in the
> loop body.
>
> Cameron
>
> On Apr 29, 2011, at 7:43 PM, Bo Wu <bwu at cs.wm.edu> wrote:
>
> Hi,
>
> I found that some loops can not be identified by LoopInfo pass. For
> example, the loop at line 3094 of rdopt.c of benchmark 464.h264ref from
spec
> cpu2006 is not a loop or a child (pr grandchild) of any loop in the loop
> list generated by LoopInfo pass. The documentation of LoopInfo says that it
> identifies natural loops, who have exactly one entry point. But the IR of
> this loops shows that it's header only has one BB in preds. Does that
mean
> LoopInfo can not identify some natural loops?
>
> Thanks,
> Bo
>
> --
> Bo Wu
>
> Ph.D. student
> CAPS group
> Computer Science Department
> The College of William & Mary
> <http://www.cs.wm.edu/~bwu>www.cs.wm.edu/~bwu
>
>
>  _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu          <http://llvm.cs.uiuc.edu>
> http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>

-- 
Bo Wu

Ph.D. student
CAPS group
Computer Science Department
The College of William & Mary
www.cs.wm.edu/~bwu
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110430/8652e7a0/attachment.html>

On 4/30/11 8:52 AM, Bo Wu wrote:
> In C code, if a loop is not a natural loop, that means its loop body 
> should at least have one label, right? In that case, some BB out of 
> the loop can jump to the loop body, so the loop has more than on entry.
Off the top of my head, I would think you are right: a C label would 
have to exist within the loop in order to have a jump from outside the 
loop to the inside of the loop.

That said, have you looked at the LLVM IR generated for the function and 
determined that the loop meets all the criteria of a natural loop?  Just 
my two cents, but I think looking at the IR directly is much more 
accurate than ensuring that your conclusion about C code and natural 
loops is correct.

-- John T.
>
> Does LoopInfo guarantee to identify all natural loops? This property 
> is very important for my pass.
>
> regards,
> Bo
>
> On Fri, Apr 29, 2011 at 11:50 PM, Cameron Zwarich <zwarich at apple.com 
> <mailto:zwarich at apple.com>> wrote:
>
>     A natural loop is one whose header dominates all of the nodes in
>     the loop. There is probably some block outside of the loop jumping
>     to a block in the loop body.
>
>     Cameron
>
>     On Apr 29, 2011, at 7:43 PM, Bo Wu <bwu at cs.wm.edu
>     <mailto:bwu at cs.wm.edu>> wrote:
>
>>     Hi,
>>
>>     I found that some loops can not be identified by LoopInfo pass.
>>     For example, the loop at line 3094 of rdopt.c of benchmark
>>     464.h264ref from spec cpu2006 is not a loop or a child (pr
>>     grandchild) of any loop in the loop list generated by LoopInfo
>>     pass. The documentation of LoopInfo says that it identifies
>>     natural loops, who have exactly one entry point. But the IR of
>>     this loops shows that it's header only has one BB in preds.
Does
>>     that mean LoopInfo can not identify some natural loops?
>>
>>     Thanks,
>>     Bo
>>
>>     -- 
>>     Bo Wu
>>
>>     Ph.D. student
>>     CAPS group
>>     Computer Science Department
>>     The College of William & Mary
>>     www.cs.wm.edu/~bwu <http://www.cs.wm.edu/%7Ebwu>
>>
>>
>>     _______________________________________________
>>     LLVM Developers mailing list
>>     LLVMdev at cs.uiuc.edu <mailto:LLVMdev at cs.uiuc.edu>
>>     http://llvm.cs.uiuc.edu
>>     http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>
>
> -- 
> Bo Wu
>
> Ph.D. student
> CAPS group
> Computer Science Department
> The College of William & Mary
> www.cs.wm.edu/~bwu <http://www.cs.wm.edu/%7Ebwu>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110501/b2f2a721/attachment.html>

Thanks for the reply. The LoopInfo pass can actually identify the loop I
mentioned. My former question is due to a bug in my pass. What I worried is
that LoopInfo can not identify all the natural loops for the benchmarks I
use, but now I haven't found any such cases.

Bo

On Sun, May 1, 2011 at 4:24 PM, John Criswell <criswell at illinois.edu>
wrote:
>  On 4/30/11 8:52 AM, Bo Wu wrote:
>
> In C code, if a loop is not a natural loop, that means its loop body should
> at least have one label, right? In that case, some BB out of the loop can
> jump to the loop body, so the loop has more than on entry.
>
>
> Off the top of my head, I would think you are right: a C label would have
> to exist within the loop in order to have a jump from outside the loop to
> the inside of the loop.
>
> That said, have you looked at the LLVM IR generated for the function and
> determined that the loop meets all the criteria of a natural loop?  Just my
> two cents, but I think looking at the IR directly is much more accurate
than
> ensuring that your conclusion about C code and natural loops is correct.
>
> -- John T.
>
>
>
>  Does LoopInfo guarantee to identify all natural loops? This property is
> very important for my pass.
>
>  regards,
> Bo
>
> On Fri, Apr 29, 2011 at 11:50 PM, Cameron Zwarich <zwarich at
apple.com>wrote:
>
>>  A natural loop is one whose header dominates all of the nodes in the
>> loop. There is probably some block outside of the loop jumping to a
block in
>> the loop body.
>>
>> Cameron
>>
>> On Apr 29, 2011, at 7:43 PM, Bo Wu <bwu at cs.wm.edu> wrote:
>>
>>  Hi,
>>
>>  I found that some loops can not be identified by LoopInfo pass. For
>> example, the loop at line 3094 of rdopt.c of benchmark 464.h264ref from
spec
>> cpu2006 is not a loop or a child (pr grandchild) of any loop in the
loop
>> list generated by LoopInfo pass. The documentation of LoopInfo says
that it
>> identifies natural loops, who have exactly one entry point. But the IR
of
>> this loops shows that it's header only has one BB in preds. Does
that mean
>> LoopInfo can not identify some natural loops?
>>
>>  Thanks,
>> Bo
>>
>> --
>> Bo Wu
>>
>> Ph.D. student
>> CAPS group
>> Computer Science Department
>> The College of William & Mary
>> www.cs.wm.edu/~bwu <http://www.cs.wm.edu/%7Ebwu>
>>
>>
>>    _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>
>>
>
>
> --
> Bo Wu
>
> Ph.D. student
> CAPS group
> Computer Science Department
> The College of William & Mary
> www.cs.wm.edu/~bwu <http://www.cs.wm.edu/%7Ebwu>
>
>
>
> _______________________________________________
> LLVM Developers mailing listLLVMdev at cs.uiuc.edu        
http://llvm.cs.uiuc.eduhttp://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>
>

-- 
Bo Wu

Ph.D. student
CAPS group
Computer Science Department
The College of William & Mary
www.cs.wm.edu/~bwu
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110501/5ed04d3c/attachment.html>

Unless there is a very subtle bug in the code, it finds all natural loops. It
looks for edges where the destination dominates the source, then finds all nodes
in the corresponding loop.

Cameron

On 2011-04-30, at 6:52 AM, Bo Wu wrote:
> Does LoopInfo guarantee to identify all natural loops? This property is
very important for my pass.
> 
> regards,
> Bo
> 
> On Fri, Apr 29, 2011 at 11:50 PM, Cameron Zwarich <zwarich at
apple.com> wrote:
> A natural loop is one whose header dominates all of the nodes in the loop.
There is probably some block outside of the loop jumping to a block in the loop
body.
> 
> Cameron
> 
> On Apr 29, 2011, at 7:43 PM, Bo Wu <bwu at cs.wm.edu> wrote:
> 
>> Hi,
>> 
>> I found that some loops can not be identified by LoopInfo pass. For
example, the loop at line 3094 of rdopt.c of benchmark 464.h264ref from spec
cpu2006 is not a loop or a child (pr grandchild) of any loop in the loop list
generated by LoopInfo pass. The documentation of LoopInfo says that it
identifies natural loops, who have exactly one entry point. But the IR of this
loops shows that it's header only has one BB in preds. Does that mean
LoopInfo can not identify some natural loops?
>> 
>> Thanks,
>> Bo 
>> 
>> -- 
>> Bo Wu
>> 
>> Ph.D. student
>> CAPS group
>> Computer Science Department
>> The College of William & Mary
>> www.cs.wm.edu/~bwu
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> 
> 
> -- 
> Bo Wu
> 
> Ph.D. student
> CAPS group
> Computer Science Department
> The College of William & Mary
> www.cs.wm.edu/~bwu
> 
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110501/1471adc6/attachment.html>