similar to: [LLVMdev] mem2reg optimization

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 some extra profiling lately and the RewriteSingleStoreAlloca function alone is taking a whopping 63% of execution time. Thanks! Nicolas -----Original Message----- From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu]

On Monday 11 August 2008 09:58, Nicolas Capens wrote: > Hi all, > > > > While profiling LLVM I noticed that a significant amount of time is spent > in the RewriteSingleStoreAlloca function. Especially for fairly long basic > blocks, linearly searching for uses before a store isn't fast. So I was > wondering if there isn't a faster way to locate these uses? YES! I

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

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 some extra > profiling lately and the RewriteSingleStoreAlloca function alone is taking > a whopping 63% of execution time. I will commit it today along with

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. >

On Oct 26, 2008, at 11:09 PM, Chris Lattner wrote: >> Fundamentally, we need a map from BasicBlock to a list of ordered >> loads and >> stores in that block. > > Are you seeing cases where lots of time is spent in > RewriteSingleStoreAlloca[s]? If so, please provide a testcase and I > can apply the obvious fix. Okay, I decided to just go ahead and make the change,

On Oct 21, 2008, at 10:16 AM, David Greene wrote: > On Monday 20 October 2008 16:14, Chris Lattner wrote: > >> Ok, if you need this direction, just use an >> std::vector<pair<unsigned,Instruction*>> as a forward map? You can >> do >> fast binary searches in it. > > I don't see how that helps. I need a map from BasicBlock to a list > of

On May 20, 2008, at 8:57 AM, David Greene wrote: > On Tuesday 20 May 2008 07:03, Nicolas Capens wrote: > >> 1) Does ScalarReplAggregates totally superscede >> PromoteMemoryToRegister? I > > Nope, they are different. Mem2Reg is really important if you want > register > allocation. Actually SROA does fully subsume Mem2Reg. It iterates between breaking up

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

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

On Tue, May 20, 2008 at 2:28 PM, Chris Lattner <clattner at apple.com> wrote: > > On May 20, 2008, at 8:57 AM, David Greene wrote: > >> On Tuesday 20 May 2008 07:03, Nicolas Capens wrote: >> >>> 1) Does ScalarReplAggregates totally superscede >>> PromoteMemoryToRegister? I >> >> Nope, they are different. Mem2Reg is really important if you

Hi all, I'm getting more impressed by LLVM day by day, but what's a bit unclear to me now is the order of optimization passes, and their performance. I think I have a pretty solid understanding of what each pass does at a high level, but I couldn't find any documentation about how they interact at a lower level. I'd like to use LLVM for generating high-performance stream

On Monday 06 October 2008 11:47, David Greene wrote: > > 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.

On Monday 20 October 2008 16:14, Chris Lattner wrote: > Ok, if you need this direction, just use an > std::vector<pair<unsigned,Instruction*>> as a forward map? You can do > fast binary searches in it. I don't see how that helps. I need a map from BasicBlock to a list of loads and stores. > > I suppose we could resctrict the map to containing only load and

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 >

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

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 just Actually, 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.

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

On Saturday 04 October 2008 17:05, Chris Lattner wrote: > 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 Correct. > case. I could imagine that if you saw lots of single store allocas in > the middle of a large BB that

On Tuesday 07 October 2008 12:37, Dan Gohman wrote: > On Tue, October 7, 2008 9:02 am, David Greene wrote: > > 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 just > > > > Actually, no it can't. See