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>
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
On Friday 26 September 2008 10:56, Andrew Lenharth 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 youI think so.> run mem2reg after other optimizations, why would you still have any > ordering guarantees?Yes, that's exactly what I'm worried about and why I didn't use the use lists in my solution. I'll check in my patch if folks find it acceptable. It was done pretty quickly so I may make another pass over it to clean it up a bit. -Dave
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
On Sep 26, 2008, at 8:41 AM, David Greene wrote:> 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.Hi Dave, Great. I'd like to get this in, but would really like to do a profile first. Could you please include a testcase? Even if it is something contrived with llvm-gcc, I would really like to understand what is going on.> I still prefer Nicolas' solution if his use list ordering assumption > is valid.It isn't. -Chris
On Oct 4, 2008, at 2:51 PM, Chris Lattner 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. > > Hi Dave, > > Great. I'd like to get this in, but would really like to do a profile > first. Could you please include a testcase? Even if it is something > contrived with llvm-gcc, I would really like to understand what is > going on.Looking more closely at the approach, I infer that the (logical in hindsight) issue are cases where mem2reg scans a BB to see the relative ordering of two instructions. For example, the single store case. I could imagine that if you saw lots of single store allocas in the middle of a large BB that mem2reg would be very very slow. As far as the approach goes, here's a counterproposal that is a bit less complex. I suggest adding a single DenseMap<Instruction*, unsigned> to Mem2reg. If there is an entry in this map for a load/ store instruction, it would store the instruction's index in its basic block. This means that to check dominance of two instrs in a block, you just need to compare their two indices (which is fast). Really small blocks (< 10 instructions?) would never be entered into map, to keep the size of the map low. The first time a query is made within a large block, it would compute the indices of all loads and stores within the block. The nice thing about using a single map is that it makes updating the map really trivial. Just use TheMap.erase(I) when deleting load and store instructions. The numbering can be purely local to a block and the relative ordering of memops don't get invalidated when a load or store is nuked. Does this seem like a reasonable approach? If so, please split the various parts of mem2reg out into helper methods as a prepatch. This will make review of the subsequent changes much easier. -Chris
On Saturday 04 October 2008 16:51, Chris Lattner wrote:> Great. I'd like to get this in, but would really like to do a profile > first. Could you please include a testcase? Even if it is something > contrived with llvm-gcc, I would really like to understand what is > going on.Agreed. I believe I have a testcase that shows the problem.> > I still prefer Nicolas' solution if his use list ordering assumption > > is valid. > > It isn't.Ok then, I'll file an official bug with the testcase and then check this in to resolve the bug. -Dave