Hi Andrew, I can't see any reason not to run mem2reg as the first pass (except maybe run a CFG simplify first, which doesn't alter the use list as far as I know). Also, I doubt that any pass can actually make a valid change in the order of loads and stores. And finally, why would any pass want to change the order of the use list in the first place? Only passes that create new stores and/or loads and don't insert them into the use list in the same reverse order could cause problems. But as far as I know that's only during codegen (e.g. specific instructions that need an operand to be in memory, and spills and loads added during register allocation). Anyway, my experience with LLVM is quite limited so I might be overlooking something important. So if Dave's solution works in all cases and has comparable performance then that's obviously better. I'll try to compare performance early next week and keep you posted. Kind regards, Nicolas On 26 Sep 2008, at 17:56, "Andrew Lenharth" <andrewl at lenharth.org> wrote:> On Fri, Sep 26, 2008 at 10:41 AM, David Greene <dag at cray.com> wrote: >> On Thursday 25 September 2008 13:15, David Greene wrote: >>> I like your approach of using the use lists but I'm not sure the >>> ordering >>> is guaranteed. If it is, your approach is superior. >> >> I got my patch updated to work with TOT. Here it is. Comments >> welcome. >> I still prefer Nicolas' solution if his use list ordering >> assumption is valid. > > Isn't the ordering an artifact of the creation of the users? If you > run mem2reg after other optimizations, why would you still have any > ordering guarantees? > > Andrew > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Hi all, I haven't had a chance yet to do some accurate profiling, but does anyone have some more insight in the use list order? *bump* It seems very valuable to me (from a performance standpoint) to keep the use list in (reverse) order. But if this can't be guaranteed it might still be interesting to have some fast variants of passes that do make some assumptions (like my patch for mem2reg). I believe I can optimize more passes by making such assumption about the order of the use lists, so any and all information about that is welcome. Thanks a lot, Nicolas -----Original Message----- From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of Nicolas Capens Sent: Saturday, 27 September, 2008 00:48 To: LLVM Developers Mailing List Cc: LLVM Developers Mailing List Subject: Re: [LLVMdev] mem2reg optimization Hi Andrew, I can't see any reason not to run mem2reg as the first pass (except maybe run a CFG simplify first, which doesn't alter the use list as far as I know). Also, I doubt that any pass can actually make a valid change in the order of loads and stores. And finally, why would any pass want to change the order of the use list in the first place? Only passes that create new stores and/or loads and don't insert them into the use list in the same reverse order could cause problems. But as far as I know that's only during codegen (e.g. specific instructions that need an operand to be in memory, and spills and loads added during register allocation). Anyway, my experience with LLVM is quite limited so I might be overlooking something important. So if Dave's solution works in all cases and has comparable performance then that's obviously better. I'll try to compare performance early next week and keep you posted. Kind regards, Nicolas On 26 Sep 2008, at 17:56, "Andrew Lenharth" <andrewl at lenharth.org> wrote:> On Fri, Sep 26, 2008 at 10:41 AM, David Greene <dag at cray.com> wrote: >> On Thursday 25 September 2008 13:15, David Greene wrote: >>> I like your approach of using the use lists but I'm not sure the >>> ordering >>> is guaranteed. If it is, your approach is superior. >> >> I got my patch updated to work with TOT. Here it is. Comments >> welcome. >> I still prefer Nicolas' solution if his use list ordering >> assumption is valid. > > Isn't the ordering an artifact of the creation of the users? If you > run mem2reg after other optimizations, why would you still have any > ordering guarantees? > > Andrew > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev_______________________________________________ LLVM Developers mailing list LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On Thu, October 2, 2008 10:17 am, Nicolas Capens wrote:> Hi all, > > I haven't had a chance yet to do some accurate profiling, but does anyone > have some more insight in the use list order? *bump*I thought this was answered; use lists are not currently in any intentional order.> > It seems very valuable to me (from a performance standpoint) to keep the > use > list in (reverse) order. But if this can't be guaranteed it might still be > interesting to have some fast variants of passes that do make some > assumptions (like my patch for mem2reg). I believe I can optimize more > passes by making such assumption about the order of the use lists, so any > and all information about that is welcome.Keeping use lists sorted, in general, seems expensive. Take a pass like LICM; when an Instruction is hoisted from a loop, its position in any use lists it's on may need to change if they are to remain sorted. Determining the new position would require determining where the other instructions in the list are. The property of being able to arbitrarily reorder LLVM passes is an important design goal. I don't think we want to have variants that make assumptions about use list ordering unless there are very significant advantages. That said, it's an interesting idea. Would you be able to perform the same optimizations using an analysis pass that provides a topological ordering for all Instructions? Dan