llvm dev - Dec 2011 - [LLVMdev] compounding loop exit conditions

Hi all,

I got a question on loop exit condition identification based on LLVM. I 
made an assumption first that loop exit conditions are located in 
exiting basic blocks. Then I use loop->getExitingBlocks() to get all 
BBs. However, this policy seemed not work for combinational exit 
conditions, e.g. compounding conditions consists of conditions with 
logical predicates. *The problem is that LLVM discompose these 
compounding conditions and only returns the last conditions*. Obviously, 
it is not I wanted. I give a sample loop code segments here and attached 
please find my BB flow chart drawn according to the disassemble files 
(*.ll). The conditions are just for test, so pls do not take it seriously.

volatile int a;
int b,e ;
....

void *f1 (void *notused)
{
     int *c;
     int d;

     while (1) {
         c = &a;
         if (*c != 0 ) d = 1;
         if ( d != 1 && e != 0 && e != d ) break;
         if ( *c == e) break;
     }
     b = 1;
}

In the BB flow chart, B15 and B20 is the exiting block recognized by 
LLVM. But One of the loop exit conditions is a combination of the 
compounded branches located in B15, B12 and B9.

Can any suggestion be shared with me to solve this problem?

Best,
Hanfeng
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20111227/16adf138/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 2011-12-27.pdf
Type: application/pdf
Size: 21917 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20111227/16adf138/attachment.pdf>

On Dec 27, 2011, at 6:16 AM, Hanfeng Qin wrote:
> volatile int a;
> int b,e ;
> ....
> 
> void *f1 (void *notused)
> {
>     int *c;
>     int d;
> 
>     while (1) {
>         c = &a;
>         if (*c != 0 ) d = 1;
>         if ( d != 1 && e != 0 && e != d ) break;
>         if ( *c == e) break;
>     }
>     b = 1;
> }
> 
> In the BB flow chart, B15 and B20 is the exiting block recognized by LLVM.
But One of the loop exit conditions is a combination of the compounded branches
located in B15, B12 and B9.
> 
> Can any suggestion be shared with me to solve this problem?
I didn't see a response to this, but clearly you're asking for control
dependence information within the loop. You'll have to look for CFG
predecessors of the exiting block that are not deeper in the postdominator tree.
For a fully qualified loop exiting condition, you have to do this iteratively as
you walk down the postdominator tree. Eventually you'll hit a leaf in the
tree or the loop header. I'm sure you can find a paper on control
dependence.

-Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120111/a42674f5/attachment.html>