[LLVMdev] Separate loop condition and loop body

[Benoit Boissinot]

On Tue, May 11, 2010 at 02:01:12AM -0700, Xinfinity wrote:
> >>> To me it looks like any basic block from the loop body with a
> >>> successor not in the loop body is a BB "building the condition" (an
> >>> "exit" block).
> >>
> Consider break statements (CFG attached):
> 
>     while (j < 10 && j > 5 && j % 2 == 0) {
>        j++;
>        if (j == 9)
>           break;
>     }
> 
> In this example, block bb is in the loop body, has a successor not in  
> the loop body, but is not building the condition. This appears to be a  
> violation of your rule.

In this case, the if statement could be considered part of the condition
(the exit of the loop depends on it, you can even rewrite the while
statement to include the condition). It really depends what you want to
achieve.
> 
> Hi,
> 
> I agree that not all exiting blocks are part of the condition. 
> Maybe your suggestion of trying a workaround would be easier. What I want is
> to modify the structure of the loop by adding an extra condition before its
> execution:
> 
> |------ extra.cond <-------|
> |	     |		     |
> |	     |		     |
> |	     v		     |
> |      |-loop.cond         |
> |      |     |             |
> |      |     v	     |
> |      | CALL(body)     ___|
> |      |
> |      |---> loop.end
> |
> |____>exit
> 
> This condition has to be checked in the beginning of each iteration, that
> means, the loop body should branch to this extra condition instead of the
> loop condition. So I want to eliminate the branch from loop.body to
> loop.cond and to insert a branch from loop.body to extra.cond .  Also, I
> need to delimit the BBs building the body of the loop, in order to extract
> them in a new function.

Can't you achieve the same thing by just adding new headers with your
extra condition.

transforming the following CFG:

      |
      v
     bb1<---+
    / |     |
   /  v     |
   | bb2    |
   | /  \   |
   | |  bb3-+
   \ /
    v
 loop.exit
   
into

    extra<--+
   /  |     |
  /   v     |
 /   bb1    |
|   / |     |
|  /  v     |
|  | bb2    |
|  | /  \   |
|  | |  bb3-+
|  \ /
|   v
| loop.exit
|
exit

Defining which nodes are part of the loop body is more difficult since,
at least for C language, computation and the condition can be mixed.

Cheers,

Benoit

-- 
:wq