similar to: RFC Storing BB order in llvm::Instruction for faster local dominance

On 09/21/2018 01:30 PM, Chris Lattner via llvm-dev wrote: On Sep 19, 2018, at 1:30 PM, Reid Kleckner via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote: Hi folks, I looked into some slow compiles and filed https://bugs.llvm.org/show_bug.cgi?id=38829. The gist of it is that we spend a lot of time iterating basic blocks to compute local dominance, i.e.

Did you consider using the waymarking algorithm we already use for going from Use->User to store the offset of an instruction in a basic block? We could steal the two bits needed from the bb parent pointer in the instruction. -- Sanjoy On Mon, Sep 24, 2018 at 10:20 AM Reid Kleckner via llvm-dev <llvm-dev at lists.llvm.org> wrote: > > To echo what Hal said, yes, it's a major

On Tue, Sep 25, 2018 at 12:16 PM Sanjoy Das <sanjoy at playingwithpointers.com> wrote: > Let's not assume a dichotomy between storing a int64 in > llvm::Instruction and bitwise tricks -- they're both ways of caching > position within llvm::Instruction. I think we first need to establish > that we need such a cache in llvm::Instruction/llvm::BasicBlock at > all. >

On Tue, Sep 25, 2018 at 10:45 PM Chris Lattner <clattner at nondot.org> wrote: > So this is one of the reasons I find your patch to be problematic: it > isn’t fixing N^2 behavior, it is merely changing one N^2 situation for > another. AFAICT there are one of two possible cases in these sorts of > transformations: > > 1) These transformations are iteratively removing or

On 09/27/2018 12:24 AM, Chris Lattner via llvm-dev wrote: On Sep 26, 2018, at 11:55 AM, Reid Kleckner <rnk at google.com<mailto:rnk at google.com>> wrote: As suggested in the bug, if we were to rewrite these passes to use MemorySSA, this bottleneck would go away. I rebased a patch to do that for DSE, but finishing it off and enabling it by default is probably out of scope for me.

Hello again. :) There has been renewed interest in having instructions track their own order in basic blocks to help make dominance queries fast. I have a very simple naive implementation of this here: https://reviews.llvm.org/D51664 Essentially, every instruction will carry an integer order number, and inserting new instructions invalidates the ordering. I know there are better algorithms for

On Mon, Sep 24, 2018 at 10:07 PM Chris Lattner <clattner at nondot.org> wrote: > > On Sep 24, 2018, at 9:54 PM, Chris Lattner <clattner at nondot.org> wrote: > >> I think we have consensus that we should go forward with this. Would > anyone mind formally stamping it in phab? So far everyone understandably > has said "makes sense to me, but I don't

> On Sep 24, 2018, at 10:19 AM, Reid Kleckner <rnk at google.com> wrote: > > To echo what Hal said, yes, it's a major change, but I think the improved complexity guarantees, simplicity, and elimination of certain classes of bugs is worth it. > > I think we have consensus that we should go forward with this. Would anyone mind formally stamping it in phab? So far everyone

Okay, so it sounds like it might actually be better to be even more low level, call it "ExtendedBBInfo" or something, and rename what it provides to be more clearly structural: A. Inst * FirstIsGuaranteedToTransferExecutionToSuccessor(BB) (naming bikeshed open on this one :P) B. Inst * LastIsGuaranteedToTransferExecutionToSuccessor(BB) C. Inst *FirstMayThrow(BB) D. Inst

Hi, Can anyone tell me how to erase an instruction, (specially a load/store instruction) ? If I use Instr->eraseFromParent(), I get following error. Note the instruction does not have any use. opt: /home/chayan/llvm/llvm-2.6/include/llvm/ADT/ilist.h:218: llvm::ilist_iterator<NodeTy>& llvm::ilist_iterator<NodeTy>::operator++() [with NodeTy = llvm::Instruction]: Assertion

Jon, > You want: > TaintVar->insertAfter(FirstI); This worked! Thank you. On Thu, Aug 25, 2016 at 9:38 AM, Jonathan Roelofs <jonathan at codesourcery.com> wrote: > > > On 8/25/16 7:01 AM, Shehbaz Jaffer via llvm-dev wrote: >> >> I tried an alternative way of adding instruction by first getting the >> first instruction of the basic block, and then

Hi @all, I hit a problem with Polly-generated code which llvm.org/PR32251 . The problem is how @llvm.lifetime.start is placed after Polly transformed the code. Basically Polly transformed llvm.lifetime.start(&var) [...] llvm.lifetime.end(&var) into if (c) { llvm.lifetime.start(&var) } [...] llvm.lifetime.end(&var) now the llvm.lifetime.end is

On Thu, 9 Nov 2006, Ryan M. Lefever wrote: Sorry I never responded to this: > In the literature (see below for a reference), when a dominance frontier > is computed, it is computed from a CFG that contains a dummy entry node > and dummy exit node. Further, those dummy nodes are potential members > of the (post-)dominance frontier for a given basic block. In LLVM, I > could not

Hi, I found that LLVM 3.1 says Dominance frontier is deprecated. Can anyone please tell me, if there is any replacement for Dominance frontier & Postdominance frontier in LLVM? What are the options if we need to use them? Thanks, Swarup. -------------- next part -------------- An HTML attachment was scrubbed... URL:

In the literature (see below for a reference), when a dominance frontier is computed, it is computed from a CFG that contains a dummy entry node and dummy exit node. Further, those dummy nodes are potential members of the (post-)dominance frontier for a given basic block. In LLVM, I could not figure out a way to determine if the dummy entry node is a member of the post-dominance frontier of

I just finished upgrading our LLVM to 2.4 and I immediately ran into a problem with dominance frontier calculation: llvm/lib/VMCore/PassManager.cpp:714: void llvm::PMDataManager::verifyDomInfo(llvm::Pass&, llvm::Function&): Assertion `0 && "Invalid dominator info"' failed. Strangely enough, the Pass running when the assert triggers is Dominance Frontier

There is PostDominatorTree for determining post-dominance. Even if A post-dominates B and B is executed, that doesn't guarantee that A will be executed. For example, there could be an infinite loop in-between. Strong post-dominance makes the stronger guarantee that there will be no infinite loop from B to A. Do we have anything in LLVM for determining strong post-dominance and in general for

On Feb 18, 2009, at 8:00 AM, David Greene wrote: > I just finished upgrading our LLVM to 2.4 and I immediately ran into > a problem > with dominance frontier calculation: > > llvm/lib/VMCore/PassManager.cpp:714: void > llvm::PMDataManager::verifyDomInfo(llvm::Pass&, llvm::Function&): > Assertion > `0 && "Invalid dominator info"' failed.

On Jan 6, 2012, at 5:08 PM, Chris Lattner wrote: >>> >>> It's very like SSA construction, but must make provision >>> testing anti dependences. I had planned to use dominance frontiers to >>> guide placement of phi nodes, as usual. >> >> Ok, in that case, please check out include/llvm/Transforms/Utils/SSAUpdater.h, >> which is the

Many published analyses which build on post-dominance assume a canonical single-dominator-tree form induced by unifying all exits (and often adding a virtual edge from START to END). In contrast, it seems that the current LLVM post-dominator analysis only operates in a mode in which it generates a forest of post-dominator trees, with one rooted at each exit node. The problem this can cause is