Hello, Quick question to see if I haven't missed anything: I would like convert counting down loops, i.e. loops with a constant -1 step value, to counting up loops, because the vectoriser is able to better deal with these loops (see e.g. D76838 that I was discussing today with Ayal). It looks like LoopSimplifyCFG and IndVarSimplify don't do this. So was just curious if I haven't missed anything here or in another pass I haven't yet considered. I was perhaps also expecting this to be the canonical form of loops, but couldn't find any evidence of that in [1] or in source-code. The obvious follow-up question is if there would be any objections to adding this to e.g. LoopSimplifyCFG, and adding LoopSimplifyCFG to the optimisation pipeline just before the vectoriser. Cheers, Sjoerd. [1] https://llvm.org/docs/LoopTerminology.html -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200326/ecc075e6/attachment.html>
LLVM used to rewrite the induction variable in indvars, but we stopped doing it a long time ago. If I recall correctly, it made the generated code worse in some cases, without any clear benefit. -Eli From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Sjoerd Meijer via llvm-dev Sent: Thursday, March 26, 2020 1:56 PM To: llvm-dev at lists.llvm.org Subject: [EXT] [llvm-dev] canonical form loops Hello, Quick question to see if I haven't missed anything: I would like convert counting down loops, i.e. loops with a constant -1 step value, to counting up loops, because the vectoriser is able to better deal with these loops (see e.g. D76838 that I was discussing today with Ayal). It looks like LoopSimplifyCFG and IndVarSimplify don't do this. So was just curious if I haven't missed anything here or in another pass I haven't yet considered. I was perhaps also expecting this to be the canonical form of loops, but couldn't find any evidence of that in [1] or in source-code. The obvious follow-up question is if there would be any objections to adding this to e.g. LoopSimplifyCFG, and adding LoopSimplifyCFG to the optimisation pipeline just before the vectoriser. Cheers, Sjoerd. [1] https://llvm.org/docs/LoopTerminology.html -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200326/ee6b2f22/attachment.html>
Hi Eli, Thanks for commenting. From your reply I understand it would probably be better not to add more logic to indvars. I see that this has the advantage of this pass not making any changes where this is possibly undesired. For the same reason, LoopSimplify, possibly another candidate for this, would not be a good idea. Thus a more focused approach is a new pass run just before the vectoriser, or very similar a helper added to LoopUtils invoked from the vectoriser, to bring loops in a canonical form. Cheers. ________________________________ From: Eli Friedman <efriedma at quicinc.com> Sent: 26 March 2020 22:07 To: Sjoerd Meijer <Sjoerd.Meijer at arm.com>; llvm-dev <llvm-dev at lists.llvm.org> Subject: RE: [llvm-dev] canonical form loops LLVM used to rewrite the induction variable in indvars, but we stopped doing it a long time ago. If I recall correctly, it made the generated code worse in some cases, without any clear benefit. -Eli From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Sjoerd Meijer via llvm-dev Sent: Thursday, March 26, 2020 1:56 PM To: llvm-dev at lists.llvm.org Subject: [EXT] [llvm-dev] canonical form loops Hello, Quick question to see if I haven't missed anything: I would like convert counting down loops, i.e. loops with a constant -1 step value, to counting up loops, because the vectoriser is able to better deal with these loops (see e.g. D76838 that I was discussing today with Ayal). It looks like LoopSimplifyCFG and IndVarSimplify don't do this. So was just curious if I haven't missed anything here or in another pass I haven't yet considered. I was perhaps also expecting this to be the canonical form of loops, but couldn't find any evidence of that in [1] or in source-code. The obvious follow-up question is if there would be any objections to adding this to e.g. LoopSimplifyCFG, and adding LoopSimplifyCFG to the optimisation pipeline just before the vectoriser. Cheers, Sjoerd. [1] https://llvm.org/docs/LoopTerminology.html -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200327/dffb75c4/attachment.html>
The topic came up before, e.g. https://reviews.llvm.org/D60565#1484984> Some canonicalization passes are designed for this. In particular, IndVarSimplify used to make canonical loops (i.e. start at zero, increment by one). r133502 introduced -disable-iv-rewrite to rely more on ScalarEvolution instead of "opcode/pattern matching" (cite from the commit message). -enable-iv-rewrite=false was made the default in r139579 after finding that it slows down many benchmarks. It was completely removed in r153260.The general approach in LLVM is to rely on SCEV for analyzing loops instead of custom handling. As a consequence, any loop structure that is recognized by SCEV will (/should) not profit from rewriting. Michael Am Do., 26. März 2020 um 15:56 Uhr schrieb Sjoerd Meijer via llvm-dev <llvm-dev at lists.llvm.org>:> > Hello, > > Quick question to see if I haven't missed anything: I would like convert counting down loops, i.e. loops with a constant -1 step value, to counting up loops, because the vectoriser is able to better deal with these loops (see e.g. D76838 that I was discussing today with Ayal). It looks like LoopSimplifyCFG and IndVarSimplify don't do this. So was just curious if I haven't missed anything here or in another pass I haven't yet considered. I was perhaps also expecting this to be the canonical form of loops, but couldn't find any evidence of that in [1] or in source-code. > The obvious follow-up question is if there would be any objections to adding this to e.g. LoopSimplifyCFG, and adding LoopSimplifyCFG to the optimisation pipeline just before the vectoriser. > > Cheers, > Sjoerd. > > [1] https://llvm.org/docs/LoopTerminology.html > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Thanks for the info and the pointer Michael, that's very useful! Cheers. ________________________________ From: Michael Kruse <llvmdev at meinersbur.de> Sent: 28 March 2020 09:32 To: Sjoerd Meijer <Sjoerd.Meijer at arm.com> Cc: llvm-dev at lists.llvm.org <llvm-dev at lists.llvm.org> Subject: Re: [llvm-dev] canonical form loops The topic came up before, e.g. https://reviews.llvm.org/D60565#1484984> Some canonicalization passes are designed for this. In particular, IndVarSimplify used to make canonical loops (i.e. start at zero, increment by one). r133502 introduced -disable-iv-rewrite to rely more on ScalarEvolution instead of "opcode/pattern matching" (cite from the commit message). -enable-iv-rewrite=false was made the default in r139579 after finding that it slows down many benchmarks. It was completely removed in r153260.The general approach in LLVM is to rely on SCEV for analyzing loops instead of custom handling. As a consequence, any loop structure that is recognized by SCEV will (/should) not profit from rewriting. Michael Am Do., 26. März 2020 um 15:56 Uhr schrieb Sjoerd Meijer via llvm-dev <llvm-dev at lists.llvm.org>:> > Hello, > > Quick question to see if I haven't missed anything: I would like convert counting down loops, i.e. loops with a constant -1 step value, to counting up loops, because the vectoriser is able to better deal with these loops (see e.g. D76838 that I was discussing today with Ayal). It looks like LoopSimplifyCFG and IndVarSimplify don't do this. So was just curious if I haven't missed anything here or in another pass I haven't yet considered. I was perhaps also expecting this to be the canonical form of loops, but couldn't find any evidence of that in [1] or in source-code. > The obvious follow-up question is if there would be any objections to adding this to e.g. LoopSimplifyCFG, and adding LoopSimplifyCFG to the optimisation pipeline just before the vectoriser. > > Cheers, > Sjoerd. > > [1] https://llvm.org/docs/LoopTerminology.html > > > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200328/ea4753b2/attachment.html>
Interesting, thanks for digging this up!> As a consequence, any loop structure that is recognized > by SCEV will (/should) not profit from rewriting.As discussed in https://reviews.llvm.org/D68577#1742745 and PR40816 showed, there is still merit and profit in further simplifying loop induction variables, or at-least the primary one; somewhat independent of continuing to rely on SCEV for analyzing loops.> enable-iv-rewrite=false was made the default in r139579 after finding that it > slows down many benchmarks.This was 8.5 years ago. Time to revisit and try to re-enable some of these iv-rewrites, with a better understanding why current downstream passes pessimize canonical iv's, if they still do?> -----Original Message----- > From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Michael > Kruse via llvm-dev > Sent: Saturday, March 28, 2020 12:33 > To: Sjoerd Meijer <Sjoerd.Meijer at arm.com> > Cc: llvm-dev at lists.llvm.org > Subject: Re: [llvm-dev] canonical form loops > > The topic came up before, e.g. https://reviews.llvm.org/D60565#1484984 > > > Some canonicalization passes are designed for this. In particular, > IndVarSimplify used to make canonical loops (i.e. start at zero, increment by > one). r133502 introduced -disable-iv-rewrite to rely more on ScalarEvolution > instead of "opcode/pattern matching" (cite from the commit message). - > enable-iv-rewrite=false was made the default in r139579 after finding that it > slows down many benchmarks. It was completely removed in r153260. > > The general approach in LLVM is to rely on SCEV for analyzing loops instead > of custom handling. As a consequence, any loop structure that is recognized > by SCEV will (/should) not profit from rewriting. > > Michael > > > > > Am Do., 26. März 2020 um 15:56 Uhr schrieb Sjoerd Meijer via llvm-dev > <llvm-dev at lists.llvm.org>: > > > > Hello, > > > > Quick question to see if I haven't missed anything: I would like convert > counting down loops, i.e. loops with a constant -1 step value, to counting up > loops, because the vectoriser is able to better deal with these loops (see e.g. > D76838 that I was discussing today with Ayal). It looks like LoopSimplifyCFG > and IndVarSimplify don't do this. So was just curious if I haven't missed > anything here or in another pass I haven't yet considered. I was perhaps also > expecting this to be the canonical form of loops, but couldn't find any > evidence of that in [1] or in source-code. > > The obvious follow-up question is if there would be any objections to > adding this to e.g. LoopSimplifyCFG, and adding LoopSimplifyCFG to the > optimisation pipeline just before the vectoriser. > > > > Cheers, > > Sjoerd. > > > > [1] https://llvm.org/docs/LoopTerminology.html > > > > > > _______________________________________________ > > LLVM Developers mailing list > > llvm-dev at lists.llvm.org > > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev--------------------------------------------------------------------- Intel Israel (74) Limited This e-mail and any attachments may contain confidential material for the sole use of the intended recipient(s). Any review or distribution by others is strictly prohibited. If you are not the intended recipient, please contact the sender and delete all copies.