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
On Oct 3, 2008, at 10:34 AM, Dan Gohman wrote:>> 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.I agree with Dan here. It would be an interesting property, but it just isn't feasible to maintain any sane ordering here. -Chris
Hi Dan, I don't want to beat a dead horse here, but why would anyone want to use mem2reg after LICM or other passes that can move around loads and stores? I fully understand the design goal to arbitrarily reorder other passes but for mem2reg it actually seems vital to run it as the first pass to make all other passes useful. Anyway, this can definitely also be done with an analysis pass that provides information about ordering between loads and stores. It's just ironic that this information is already available in the use lists if you run mem2reg as the first pass... Cheers, Nicolas -----Original Message----- From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of Dan Gohman Sent: Friday, 03 October, 2008 19:34 To: LLVM Developers Mailing List Cc: 'LLVM Developers Mailing List' Subject: Re: [LLVMdev] mem2reg optimization 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 _______________________________________________ LLVM Developers mailing list LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
On Tuesday 07 October 2008 00:32, Nicolas Capens wrote:> Anyway, this can definitely also be done with an analysis pass that > provides information about ordering between loads and stores. It's justActually, no it can't. See the thread about analysis passes depending on other analysis passes and when things do and don't get updated by PassManager. -Dave