similar to: [LLVMdev] mem2reg Question

On Fri, Sep 19, 2008 at 11:08 AM, David Greene <dag at cray.com> wrote: > \Why is this only prevented when NOT storing > to global values? It's not a question of storing *to* a global value, but storing a global value into the alloca. If there's only a single store to an alloca, there are only two possible values that can be extracted from the alloca: the value stored, and

On Friday 19 September 2008 17:17, Eli Friedman wrote: > On Fri, Sep 19, 2008 at 11:08 AM, David Greene <dag at cray.com> wrote: > > \Why is this only prevented when NOT storing > > to global values? > > It's not a question of storing *to* a global value, but storing a > global value into the alloca. If there's only a single store to an Ah, ok. > alloca,

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.

Hello, I noticed a strage behavior of mem2reg pass when the code has an uninitialized local variable dereference. Running the pass over the following bytecode: %buf = alloca i32 %val = load i32* %buf store i32 10, i32* %buf ret %val produces the following result: ret i32 10 I would expect mem2reg to produce undef result instead: ret i32 undef As behavior of the original code is

On Oct 20, 2008, at 10:04 AM, David Greene wrote: > 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

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

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

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

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

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

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

Like I said, i'm nearly positive there is a much faster way, as the sets are mostly shared except in the cyclic case, and in all reducible cyclic cases, removal of back-arcs does not affect dominance (because in any reducible flowgraph, v dominates u whenever u,v is a back-arc) On Tue, Apr 25, 2017 at 7:38 PM, Hongbin Zheng <etherzhhb at gmail.com> wrote: > Hi Daniel, > >

Hi Daniel, Thanks a lot for all these explanation, I will try it out. Hongbin On Tue, Apr 25, 2017 at 7:04 PM, Daniel Berlin <dberlin at dberlin.org> wrote: > > > On Tue, Apr 25, 2017 at 6:42 PM, Hongbin Zheng <etherzhhb at gmail.com> > wrote: > >> >> >> On Tue, Apr 25, 2017 at 6:32 PM, Daniel Berlin <dberlin at dberlin.org> >> wrote:

Hi Daniel, I mean "*As a set*, B + C dominate D". On Tue, Apr 25, 2017 at 5:42 PM, Daniel Berlin <dberlin at dberlin.org> wrote: > When you say collectively, you mean "would dominate it if considered a > single block together? > > IE > > A > / \ > B C > \ / > D > > As a set, B + C dominate D. > > The set you are