[llvm-dev] Adding Extended-SSA to LLVM

[Daniel Berlin via llvm-dev]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170202/b223fd36/attachment.html>