[llvm-dev] Adding Extended-SSA to LLVM

Thu Feb 2 10:40:48 PST 2017

On 02/02, Daniel Berlin wrote:
> On Thu, Feb 2, 2017 at 9:08 AM, Johannes Doerfert <
> doerfert at cs.uni-saarland.de> wrote:
> 
> > Hi Daniel,
> >
> > I didn't read the discussion in the review but would like to ask one
> > question anyway. In case it was already discussed elsewhere please just
> > point me there.
> >
> 
> FWIW: It's discussed in detail in the review (i detailed the approaches
> other passes take to this problem, and one of our goals is precisely to not
> do it as slowly as they do it :P). That said, happy to answer :)
> 
> 
> > Why do you want to put this information in the IR instead of recomputing
> > or preserving it like we do with other analysis results that live only
> > in memory?
> >
> The short version is it's very slow, and you can't actually do this in a
> way that is sane in an analysis.  It's been tried 3 times :)
> 
> We also already have issues in number of analysis that try to do this, with
> a significant number of open bugs due to the performance of trying do it
> this way.
> 
> IE this approach works really really well for some analysis, but is really
> really bad for others.  This is going to be one of the latter ones :)
> One of the reasons is fairly simple:
> 
> MemorySSA, which does this, and works well, works well because there is no
> IR for memory. So there are no defs/uses it's replacing.
> 
> However, this analysis is based  regular ssa, so overlaying a completely
> different set of defs and uses does not mesh well with existing
> infrastructure.
> 
> (analysis that is not trying to give def/use style info tend to work well)
> 
> But that's precisely what we need to do in order to know what affects a
> given predicate.  Thus, what you would build would essentially be a
> duplicate copy, in memory, of the existing IR, with the names changed (you
> can throw away some info, obviously). Alone, this gets very slow because
> you'd have to walk through and duplicate sometimes thousands of uses/users
> into your in-memory structure, which you have to do at a minimum to be able
> to tell the user what uses are affected by a given piece of predicate info.
> 
> Even when you do this, it  in turn is hard to use in passes, because they
> all expect one name (really, Value *) to map to one value.  This is in
> fact, the whole underlying problem one is trying to solve.   Here, even if
> you made those fake def/uses Value *'s, it is still very tricky to not make
> a mess of things.
> Our passes that try (GVN, EarlyCSE) do a combination of various scoped hash
> tables and eager IR replacement as they go to avoid this issue, but since
> NewGVN is meant itself to be split as an analysis/eliminator, we can't do
> IR replacement as we go, and the former is very mess to make work in an
> analysis *and* still catch all the cases.
> I can point you at a branch on github where we implemented the exact
> approach GVN takes now, without modifying the IR, just tracking what the
> effects are. To say it is a complex mess is an understatement. it's also 3x
> as slow as the predicateinfo approach in the base case. Not to mention
> predicateinfo required just a small amount of code to do stuff with the
> compare info (and that really should be a utility), whereas the other
> approach was a couple thousand lines.
> 
> Additionally, unlike MemorySSA, this could pretty much never be kept up to
> date, because it needs to be updated for any modification to the IR. This
> is true regardless of *invalidation* (IE most changes don't change the
> correctness, but they still have to be applied)
> 
> Given that, it doesn't, IMHO, make sense to try to do that.
> Also, i tried it anyway, and it's ... significantly slower, memory
> intensive, and not updatable :)
> 
> That doesn't make it impossible, mind you.  It's definitely doable,  but
> it's fairly complex vs doing this, and i have trouble seeing the benefits.
> 
> Note that i'm not the only person to go through this exercise:
> 
> GCC builds a nearly identical form when doing VRP (see the part where it
> builds ASSERT_EXPR, which is identical except they directly attach
> comparisons, where we don't because it constrains our ability to place
> predicateinfo for assume, which gcc doesn't have).
> It then drops the form.
> 
> A number of other compilers do similar (Jikes, for example, did this).
> 
> Some now even go farther. For example, last i looked, Graal builds pruned
> SSI.
> 
> This is all a short way of saying "yeah, i feel like we tried all the other
> approaches first" :P

I see ;)

Thank you for this detailed summary that not only answers my question
but also all the follow-up questions I can think of right now.

Cheers,
  Johannes

-- 

Johannes Doerfert
Researcher / PhD Student

Compiler Design Lab (Prof. Hack)
Saarland Informatics Campus, Germany
Building E1.3, Room 4.31

Tel. +49 (0)681 302-57521 : doerfert at cs.uni-saarland.de
Fax. +49 (0)681 302-3065  : http://www.cdl.uni-saarland.de/people/doerfert
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 228 bytes
Desc: Digital signature
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170202/e13f145e/attachment.sig>