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.
What are your thoughts about either making the CFG simplification aware
of loops in its entirety, or separating the "safe" transformations in
a
quick pass, and having a more aggressive pass that does preserve loop
structure?
-Krzysztof
--
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum,
hosted by The Linux Foundation
On Wed, Oct 17, 2012 at 8:41 AM, Krzysztof Parzyszek < 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.> > What are your thoughts about either making the CFG simplification aware of > loops in its entirety, or separating the "safe" transformations in a quick > pass, and having a more aggressive pass that does preserve loop structure?It's not clear what the problem is. Dan -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121017/756e0442/attachment.html>
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 17 October 2012 16:41, Krzysztof Parzyszek <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. > > What are your thoughts about either making the CFG simplification aware of > loops in its entirety, or separating the "safe" transformations in a quick > pass, and having a more aggressive pass that does preserve loop structure? >Having two back edges does not have an adverse affect on optimisation. Do you have a specific optimisation that you cannot do if there are two back edges? I thing to keep in mind is this is CFG, and can be unstructured, or after various transformations, not representable in higher level language structures such as while loops. Kind Regards James
On 10/17/2012 2:11 PM, James Courtier-Dutton wrote:> > I thing to keep in mind is this is CFG, and can be unstructured, or > after various transformations, not representable in higher level > language structures such as while loops.Having a specific loop structure with specific requirements, such as single back edge can make loop optimizations (and loop nest optimizations in particular) a lot simpler (or even possible). I don't have the specific case right now (I worked on it a while ago), but it was a case of loop unrolling giving up after SimplifyCFG. Another thing to keep in mind is that a compiler can shoot itself in the foot really easily, by performing early optimizations that hide opportunities for later transformations. This is my main concern here. -- Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by The Linux Foundation