Hi Dave, As an exercise I tried to fix this myself, and I think I have a working patch (attached). My own tests are all working wonderfully, and at fantastic performance! I'm looking forward to your patch to see whether we used the same approach or whether things could be improved further. Anyway, I've re-profiled the code and found ComputeLiveInBlocks to be the main hotspot now. Again it uses a linear search over the instructions so there's a chance this can be optimized as well... Kind regards, Nicolas -----Original Message----- From: David Greene [mailto:dag at cray.com] Sent: Wednesday, 24 September, 2008 18:07 To: Nicolas Capens Cc: 'LLVM Developers Mailing List' Subject: Re: [LLVMdev] mem2reg optimization On Wednesday 24 September 2008 09:35, Nicolas Capens wrote:> Hi Dave, > > Did that patch of yours ever make it into trunk? I can't seem to find any > related checkin for PromoteMemoryToRegister.cpp. I've been doing someextra> profiling lately and the RewriteSingleStoreAlloca function alone is taking > a whopping 63% of execution time.I will commit it today along with some other things. I've been having a lot of trouble building llvm-gcc but I think I've struggled enouigh now and will just hope our testing on this end has been enough. Thanks for the prod. -Dave -------------- next part -------------- A non-text attachment was scrubbed... Name: PromoteMemoryToRegister.patch Type: application/octet-stream Size: 2695 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080925/6cf39542/attachment.obj>
I forgot to ask: I found that uses appear to be stored in reverse order (i.e. use_begin() gives us an iterator that starts with the last use and incrementing it brings us to the first one). Is that correct and is it something I can always rely on for analysis? Thanks. -----Original Message----- From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] On Behalf Of Nicolas Capens Sent: Thursday, 25 September, 2008 14:40 To: 'David Greene' Cc: 'LLVM Developers Mailing List' Subject: Re: [LLVMdev] mem2reg optimization Hi Dave, As an exercise I tried to fix this myself, and I think I have a working patch (attached). My own tests are all working wonderfully, and at fantastic performance! I'm looking forward to your patch to see whether we used the same approach or whether things could be improved further. Anyway, I've re-profiled the code and found ComputeLiveInBlocks to be the main hotspot now. Again it uses a linear search over the instructions so there's a chance this can be optimized as well... Kind regards, Nicolas -----Original Message----- From: David Greene [mailto:dag at cray.com] Sent: Wednesday, 24 September, 2008 18:07 To: Nicolas Capens Cc: 'LLVM Developers Mailing List' Subject: Re: [LLVMdev] mem2reg optimization On Wednesday 24 September 2008 09:35, Nicolas Capens wrote:> Hi Dave, > > Did that patch of yours ever make it into trunk? I can't seem to find > any related checkin for PromoteMemoryToRegister.cpp. I've been doing > someextra> profiling lately and the RewriteSingleStoreAlloca function alone is > taking a whopping 63% of execution time.I will commit it today along with some other things. I've been having a lot of trouble building llvm-gcc but I think I've struggled enouigh now and will just hope our testing on this end has been enough. Thanks for the prod. -Dave
On Thursday 25 September 2008 07:40, Nicolas Capens wrote:> Hi Dave, > > As an exercise I tried to fix this myself, and I think I have a working > patch (attached). My own tests are all working wonderfully, and at > fantastic performance! > > I'm looking forward to your patch to see whether we used the same approach > or whether things could be improved further. > > Anyway, I've re-profiled the code and found ComputeLiveInBlocks to be the > main hotspot now. Again it uses a linear search over the instructions so > there's a chance this can be optimized as well...I don't quite understand how the logic of your patch is the same. In the original code, we're looking for a Load that uses the alloca before it is stored. Your code loops through the use list, first looking for the use that is the store. It then keeps going and if it sees a match with a load, it prevents promotion. Are use lists guaranteed to be ordered in reverse instruction order? That is instructions that use values later appear earlier in the use list? Can we really rely on ordering of the use list? My patch builds a map from BasicBlock to lists of loads and stores in that block in an initialization phase along with ordering information about the loads and stores. RewriteSingleStoreAlloca then queries that information to determine if a load appears before the single store. 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. -Dave
On Thursday 25 September 2008 13:15, David Greene wrote:> My patch builds a map from BasicBlock to lists of loads and stores in that > block in an initialization phase along with ordering information about the > loads and stores. RewriteSingleStoreAlloca then queries that information > to determine if a load appears before the single store. > > 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. -Dave -------------- next part -------------- A non-text attachment was scrubbed... Name: mem2reg.patch Type: text/x-diff Size: 24366 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20080926/314910ae/attachment.patch>