search for: orderedbasicblock

...rom? Are they from a couple of key places or are they > scattered throughout the pass pipeline? > When I dug into the profile with WPA, most of the time was spent in DSE and memcpyopt, which call AAResults::callCapturesBefore, which calls llvm::PointerMayBeCapturedBefore. Neither pass in an OrderedBasicBlock, so they rebuild the OrderedBasicBlock in linear time on every query. These passes insert instructions, so it's not correct to simply create and reuse an OrderedBasicBlock at this level. As suggested in the bug, if we were to rewrite these passes to use MemorySSA, this bottleneck would go away...

...t;> 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. given two instructions in the same BB, which comes first. LLVM already has a tool, OrderedBasicBlock, which attempts to address this problem by building a lazy mapping from Instruction* to position. The problem is that cache invalidation is hard. If we don't cache orderings at a high enough level, our transformations become O(n^2). If we cache them too much and insert instructions without renu...

...inance queries are, at least for SemaChecking.cpp, not clustered around small distances. The average query is somewhere out around 11,000 instructions apart. One thing to note is that the code in question isn't using DominatorTree::dominates. That was identified as a hotspot, so it's using OrderedBasicBlock, but it's not caching it at a high enough level to avoid quadratic behavior. Raising it up isn't easy, hence this patch. Sanjoy also wanted more data and suggested that I re-run the max RSS during full LTO of llc experiment that I did when I removed the vptr from Value. I went ahead and di...

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. given two instructions in the same BB, which comes first. LLVM already has a tool, OrderedBasicBlock, which attempts to address this problem by building a lazy mapping from Instruction* to position. The problem is that cache invalidation is hard. If we don't cache orderings at a high enough level, our transformations become O(n^2). If we cache them too much and insert instructions without renu...

...>> 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. given two instructions in the same BB, which comes first. >> >> LLVM already has a tool, OrderedBasicBlock, which attempts to address this problem by building a lazy mapping from Instruction* to position. The problem is that cache invalidation is hard. If we don't cache orderings at a high enough level, our transformations become O(n^2). If we cache them too much and insert instructions without renu...

...ne :P) B. Inst * LastIsGuaranteedToTransferExecutionToSuccessor(BB) C. Inst *FirstMayThrow(BB) D. Inst *LastMayThrow(BB) Most things want to know if a given inst is before or after these. Since we have to touch the entire set of instructions for a bb anyway, we could also provide dominates (like orderedbasicblock) to give you the answer to that question for free (otherwise everything has to rewalk the entire inst list again) Rather than make it part of the API for this class, this would basically be making OrderedBasicBlock an interface, and this class happens to be able to provide a pointer to something s...

Hi, On 08/07/2015 10:30 PM, Nick Lewycky wrote: [...] > Depends. What is the exact declaration of format_long? > > > In the input .ll file it is: > > ; Function Attrs: minsize optsize > define internal i16 @format_long(i16* %res.8.par, i16 %base.9.par, > i32 %x.10.par) #3 { > > which is later changed somewhere in opt to: > > ;

On Thu, Jul 21, 2016 at 9:39 AM, Daniel Berlin <dberlin at dberlin.org> wrote: > > > On Thu, Jul 21, 2016 at 9:26 AM, Andrew Trick <atrick at apple.com> wrote: > >> >> On Jul 21, 2016, at 7:45 AM, Philip Reames <listmail at philipreames.com> >> wrote: >> >> Joining in very late, but the tangent here has been interesting (if >>

...gt; another. AFAICT there are one of two possible cases in these sorts of > transformations: > > 1) These transformations are iteratively removing or inserting > instructions, which invalidate the ordering with your approach, causing > subsequent queries to rebuild the equivalent of OrderedBasicBlock. > I would say that this code fixes the quadratic behavior in practice, and lays the foundation to fix it permanently if it becomes a problem. First, removing instructions doesn't invalidate the ordering, and these passes mostly delete instructions, so in practice, the latent quadratic beh...

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.

> 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