On 10/17/2012 11:09 AM, Dan Gohman wrote:> On Wed, Oct 17, 2012 at 8:41 AM, Krzysztof Parzyszek > <kparzysz at codeaurora.org <mailto:kparzysz at codeaurora.org>> wrote: > > Hello All, > > The current implementation of the CFG simplification is > loop-agnostic. In the past I have observed that it can perform > transformations that can be detrimental to the loop structure. One > example that I recall, is converting a loop like this: > while (...) { > ... > if (cond) continue; > ... > } > into two nested loops. Specifically, the "continue" branch would go > back to the loop header making it appear as if there were two back > edges. > > > Well, there really are two backedges there.There is no reason for two back edges. This loop could look like this: header: ... ... if (cond) goto tail; else goto next; next: ... tail: if (loop-condition) goto header; This way there is one loop with some control flow nested in it, instead of something that looks like two loops. -- Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation
On Oct 17, 2012, at 9:38 AM, Krzysztof Parzyszek <kparzysz at codeaurora.org> wrote:>> The current implementation of the CFG simplification is >> loop-agnostic. In the past I have observed that it can perform >> transformations that can be detrimental to the loop structure. One >> example that I recall, is converting a loop like this: >> while (...) { >> ... >> if (cond) continue; >> ... >> } >> into two nested loops. Specifically, the "continue" branch would go >> back to the loop header making it appear as if there were two back >> edges. >> >> >> Well, there really are two backedges there. > > There is no reason for two back edges. This loop could look like this: > > header: > ... > ... > if (cond) goto tail; else goto next; > next: > ... > tail: > if (loop-condition) goto header; > > > This way there is one loop with some control flow nested in it, instead of something that looks like two loops.What problem does that solve? LLVM's concept of loop is tied to the loop header block: this both forms are a single loop, not two nested loops. -Chris
On 10/17/2012 11:55 AM, Chris Lattner wrote:> On Oct 17, 2012, at 9:38 AM, Krzysztof Parzyszek <kparzysz at codeaurora.org> wrote: >> >> There is no reason for two back edges. This loop could look like this: >> >> header: >> ... >> ... >> if (cond) goto tail; else goto next; >> next: >> ... >> tail: >> if (loop-condition) goto header; >> >> >> This way there is one loop with some control flow nested in it, instead of something that looks like two loops. > > What problem does that solve? LLVM's concept of loop is tied to the loop header block: this both forms are a single loop, not two nested loops.There are two back-edges that both go to the same header. It was a while ago, but I saw some procedure that tried to eliminate such cases by separating the two back edges into their own loops. We ended up with two loops instead of only having one. I'd have to dig up the old testcase I working on, but the code there was getting unnecessarily complicated due to the fact that SimplifyCFG was making changes that eventually hurt loop optimizations. -- Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation
I actually submitted a patch to fix this very problem quite a while back, but I don't think it was ever added to the baseline: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20110711/124136.html I have also explained why it is important to avoid the creation of new loops in an optimizer that performs analysis on the looping structure. I now need to keep this patch updated whenever we upgrade LLVM, to ensure that our optimizer (which is now in production) works correctly. Would it be possible to add this patch to the head? I have a version that works with 3.0 but have not yet updated to 3.1 or the head. Andrew On 10/17/2012 12:55 PM, Chris Lattner wrote:> On Oct 17, 2012, at 9:38 AM, Krzysztof Parzyszek<kparzysz at codeaurora.org> wrote: >>> The current implementation of the CFG simplification is >>> loop-agnostic. In the past I have observed that it can perform >>> transformations that can be detrimental to the loop structure. One >>> example that I recall, is converting a loop like this: >>> while (...) { >>> ... >>> if (cond) continue; >>> ... >>> } >>> into two nested loops. Specifically, the "continue" branch would go >>> back to the loop header making it appear as if there were two back >>> edges. >>> >>> >>> Well, there really are two backedges there. >> There is no reason for two back edges. This loop could look like this: >> >> header: >> ... >> ... >> if (cond) goto tail; else goto next; >> next: >> ... >> tail: >> if (loop-condition) goto header; >> >> >> This way there is one loop with some control flow nested in it, instead of something that looks like two loops. > What problem does that solve? LLVM's concept of loop is tied to the loop header block: this both forms are a single loop, not two nested loops. > > -Chris > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev