On Mon, May 10, 2010 at 12:32:06PM -0700, Trevor Harmon wrote:> On May 10, 2010, at 11:35 AM, Benoit Boissinot 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). > > I assume you mean "any basic block from the loop header".No really, loop body.> > I don't think your rule will work. Consider this counterexample: > > while (j < 10 && j > 5 && j % 2 == 0) { > j++; > } > > This will give you the attached CFG. bb1 is the loop header; bb2 and > bb3 are the other loop conditionals; bb is the loop body. > > Note that bb3 is part of the condition but is not a basic block from > the loop header.At least in the CFG/graph theory I know, the loop body is the set of nodes which form the strongly connected component (it contains the headers). In this case that would be {bb1, bb2, bb3, bb}, with bb1 as header. (the header is un-ambiguous in this case since the CFG is natural/reducible there is only one possible header for the loop).>From this set, bb1, bb2 and bb3 have exit edges, those are theconditional blocks. cheers, Benoit -- :wq
On May 10, 2010, at 11:05 AM, Trevor Harmon 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). >> >> I assume you mean "any basic block from the loop header". > > No really, loop body.In that case, what does it mean for a block to be "from" the loop body? Perhaps you meant "of" or "in" the loop body, but then I'm still confused. 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. Trevor -------------- next part -------------- A non-text attachment was scrubbed... Name: cfg._Z6simplei.dot Type: application/octet-stream Size: 2180 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100510/6b17f2c6/attachment.obj> -------------- next part --------------
>>> 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. Trevor 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. I hope my explanations are not too vague. Thanks for your help. Alexandra -- View this message in context: http://old.nabble.com/Separate-loop-condition-and-loop-body-tp28512281p28521641.html Sent from the LLVM - Dev mailing list archive at Nabble.com.
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
Apparently Analagous Threads
- [LLVMdev] Separate loop condition and loop body
- [LLVMdev] Separate loop condition and loop body
- [LLVMdev] Separate loop condition and loop body
- [LLVMdev] Separate loop condition and loop body
- [LLVMdev] How to prevent an instruction to be executed more than once?