search for: rewritesinglestorealloca

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? Are there any other known opportunities for optimization? I noticed that register allocation takes a big bite ou...

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 Behalf Of David Greene Sent: Monday, 11 August, 2008 23:05 To: llvmdev at cs.uiuc.edu Subject: Re: [LLVMdev] mem2...

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 just finished a patch 2 hours ago to fix this. I'll get it in ASAP. mem2reg totally droppe...

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

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

...der? 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 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, with the justification that it is a significant code cleanup to mem2reg. Here's the patch: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20081027...

...that block. I don't see why. Please take a look at my patch, does it seem reasonable? This is a very simple approach and seems like it works just fine: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20081027/068967.html 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. -Chris

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

...in a > > large block, it would compute the indices of all loads and stores > > within the block. > > This is a simpler approach and should have the same effect. I'll code it > up. Urk. After looking at doing this today, I realized it won't work. The problem is that RewriteSingleStoreAlloca has this loop: for (; &*I != OnlyStore; ++I) { // scan block for store. if (isa<LoadInst>(I) && I->getOperand(0) == AI) break; It's looking for a load that matches the address of the single store. This is the loop that's taking all the time....

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

...ble for LLVM-based verifiers (such as KLEE) to find an uninitialized local variable bug in such examples. By the way, if 10 is replaced by a non-constant, mem2reg pass will produce "ret i32 undef" as a result, which is much closer to the original code. The problem lies in PromoteMem2Reg::RewriteSingleStoreAlloca function: it explicitly avoids checking whether a load is dominated by a store if an argument to the store is a constant. The comment in the code ("Non-instructions are always dominated") is incorrect as subsequent code checks whether the load is dominated by the store instruction, not by...

I have a question about PromoteMem2Reg::RewriteSingleStoreAlloca. Specifically, this bit of code: // If the store dominates the block and if we haven't processed it yet, // do so now. We can't handle the case where the store doesn't dominate a // block because there may be a path between the store and the use, but we // may need to...

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

...he indices of all loads and stores >>> within the block. >> >> This is a simpler approach and should have the same effect. I'll >> code it >> up. > > Urk. After looking at doing this today, I realized it won't work. > The > problem is that RewriteSingleStoreAlloca has this loop: > > for (; &*I != OnlyStore; ++I) { // scan block for store. > if (isa<LoadInst>(I) && I->getOperand(0) == AI) > break; > > It's looking for a load that matches the address of the single > store. This > is the...

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