llvm dev - Jul 2016 - RFC: Strong GC References in LLVM

On Fri, Jul 15, 2016 at 4:00 PM, Andrew Trick <atrick at apple.com> wrote:
>
> On Jul 15, 2016, at 3:38 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
> wrote:
>
> > Note that this is also necessary to makes post-dominance correct (but
we
> > already do it in most cases, but i think there are still bugs open
about
> > correctness)
>
> Yeah, right now in LLVM we cannot rely on post-dominance to conclude
> "guaranteed to execute" which isn't ideal.  There's at
least one place
> I know where a more precise post-dominance could be used. :)
>
>
> I completely understand the philosophical criticism, but
>
> - LLVM clearly made the decision/tradeoff to allow implicit early exits,
> and I’m pretty certain that will never change.
>
> Nobody is looking to change that necessarily, or at least i'm not, only
to
make the impact not "correctness requires N^2 algorithms or other things
that *already* are slowing down the compiler"

> - LLVM made the decision/tradeoff not to maintain a postdom tree
> throughout most of the pass pipeline
>
> Well, actually, this one is likely to change. The only issue here is
keeping it updated, and i have a solution for that.


> - Fundamentally, you don’t really lose anything.
>
This i'm going to disagree with :)
This is basically an argument that postdom is not needed, and i think we've
actually proven precisely the opposite.  We approximate it in so many
places, and then go looking for harder and harder ways to optimize those
cases using dominance, and make ever  more complicated "if the cfg kinda
looks like that, well then, sure go for it" instead of using postdom.  We
never get all the cases, and we're well past the point where it would be
easier to use postdom in most of these places.

> It’s an easy analysis to find the exit points and mark blocks.
>
I'm going to simply point out that may throw was fixed using N^2 methods in
at least 3 passes, with no intention to change it.  I haven't looked at the
rest, but i also suspect there are more bugs hiding here that nobody has
noticed yet.

So you are right that it may be algorithmically easy, it's apparently not
so easy that people did it.
I will also point out that the design decision lead to simple trivial test
cases that exercised this design decision being broken for years in the
compiler in on-by-default optimization passes.

Does that make it the wrong design?
No, of course not, but it is empirical evidence that maybe things were
missing from "making it easy to get it right", etc.


> Doing a CFG walk instead of a PostDom walk is typically not such a big
> deal.
>
Using post-dom to approximate classical control dependence, as we do in
several places, has led to a mess nobody quite understands in those places.

But, like i said, i have a plan to fix this by making post-dom updates
automatic. There are now incremental dominance update algorithms that are
very fast in the common case (IE 100x faster than computing from scratch)
and even in the very pathological cases, 2x faster than computing from
scratch.  This comes out to "fast enough" to maintain postdom without
anyone having to think about anything other than saying "i added an
edge"
or "i deleted an edge".

I often overload the term “control dependence” here. When I say a load
is
> control dependent on a branch, I don’t mean that the load’s block is
> classically control dependent on the branch, I mean that the load is
> illegal to speculate above the branch. Yes they are two different things,
> but I don’t have a better term to use for that dependence information.
>
> -Andy
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160715/4d3d2252/attachment.html>

> On Jul 15, 2016, at 4:21 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> 
> Doing a CFG walk instead of a PostDom walk is typically not such a big
deal.
> 
> Using post-dom to approximate classical control dependence, as we do in
several places, has led to a mess nobody quite understands in those places.
>  
> But, like i said, i have a plan to fix this by making post-dom updates
automatic. There are now incremental dominance update algorithms that are very
fast in the common case (IE 100x faster than computing from scratch) and even in
the very pathological cases, 2x faster than computing from scratch.  This comes
out to "fast enough" to maintain postdom without anyone having to
think about anything other than saying "i added an edge" or "i
deleted an edge”.
Ok, I do love incremental domtree update. It’s just that for postdom you have to
be aware of addition/removal of maythrow sort of calls.
> I often overload the term “control dependence” here. When I say a load is
control dependent on a branch, I don’t mean that the load’s block is classically
control dependent on the branch, I mean that the load is illegal to speculate
above the branch. Yes they are two different things, but I don’t have a better
term to use for that dependence information.
I still don’t know how to talk about a load’s dependencies without calling it
“control dependence”

-Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160715/92f58179/attachment.html>

On Fri, Jul 15, 2016 at 4:21 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
>
>
> On Fri, Jul 15, 2016 at 4:00 PM, Andrew Trick <atrick at apple.com>
wrote:
>
>>
>> On Jul 15, 2016, at 3:38 PM, Sanjoy Das <sanjoy at
playingwithpointers.com>
>> wrote:
>>
>> > Note that this is also necessary to makes post-dominance correct
(but we
>> > already do it in most cases, but i think there are still bugs open
about
>> > correctness)
>>
>> Yeah, right now in LLVM we cannot rely on post-dominance to conclude
>> "guaranteed to execute" which isn't ideal.  There's
at least one place
>> I know where a more precise post-dominance could be used. :)
>>
>>
>> I completely understand the philosophical criticism, but
>>
>> - LLVM clearly made the decision/tradeoff to allow implicit early
exits,
>> and I’m pretty certain that will never change.
>>
>> Nobody is looking to change that necessarily, or at least i'm not,
only
> to make the impact not "correctness requires N^2 algorithms or other
things
> that *already* are slowing down the compiler"
>

Though, just as an aside, i will admit i find the design decision strange.

GCC's design decision is one where nothing has to explicitly care about
implicit early exits to get correct answers about sinking/hoisting (they
won't hoist because the predecessor will have multiple successors, they
won't sink because the current block will have multiple successors. Even
PRE and PDE will get this right by default).

LLVM's design decision is one where everything has to explicitly care about
implicit early exits to get correct answers (and not to harp too much, but
"not everything does", years later).  If they don't, they will get
wrong
answers.

Most of LLVM's design tradeoffs are in the other direction.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160715/aabfd358/attachment.html>

On Fri, Jul 15, 2016 at 4:27 PM, Andrew Trick <atrick at apple.com> wrote:
>
> On Jul 15, 2016, at 4:21 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
>
> Doing a CFG walk instead of a PostDom walk is typically not such a big
>> deal.
>>
>
> Using post-dom to approximate classical control dependence, as we do in
> several places, has led to a mess nobody quite understands in those places.
>
> But, like i said, i have a plan to fix this by making post-dom updates
> automatic. There are now incremental dominance update algorithms that are
> very fast in the common case (IE 100x faster than computing from scratch)
> and even in the very pathological cases, 2x faster than computing from
> scratch.  This comes out to "fast enough" to maintain postdom
without
> anyone having to think about anything other than saying "i added an
edge"
> or "i deleted an edge”.
>
>
> Ok, I do love incremental domtree update. It’s just that for postdom you
> have to be aware of addition/removal of maythrow sort of calls.
>
These create block edges in the post-dom tree, even now (or at least, they
have to for correctness).  They still will be then.  So it'll just be an
edge add/removal  in the actual tree ;)
>From an API standpoint, the only thing an API would actually care about for
this is the block they were added/removed from, and the count of such calls
before add/removal (If there are any, you need an edge, if there are none,
you don't).

So as long as things changing these types of calls (or erasing/duplicating
them) notify postdom, it'll still work just fine.

That seems doable.


> I often overload the term “control dependence” here. When I say a load is
>> control dependent on a branch, I don’t mean that the load’s block is
>> classically control dependent on the branch, I mean that the load is
>> illegal to speculate above the branch. Yes they are two different
things,
>> but I don’t have a better term to use for that dependence information.
>>
>
> I still don’t know how to talk about a load’s dependencies without calling
> it “control dependence”
>
Yeah, i'm working on it :)

>
> -Andy
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160715/9ae0e4d0/attachment.html>

>
>
> LLVM's design decision is one where everything has to explicitly care
> about implicit early exits to get correct answers (and not to harp too
> much, but "not everything does", years later).  If they
don't, they will
> get wrong answers.
>
>
So, ironically, while looking at this, i noticed it turns out LLVM's PRE in
GVN is another place that does not do this correctly either.

It will insert and hoist loads past may-throw calls depending on whether it
thinks the call aliases the pointer or not (IE depending on what memdep
tells it, and memdep only cares about aliasing here when coming up with
deps), regardless of whether the call is nounwind or not.  This is rare but
can happen.

This is because memdep does this:
       // If the call has no effect on the queried pointer, just ignore it.
So it does not give a dep, and PRE then never does anything else to check
whether there is a may-throw call in the way of the hoist.

Testcase and patch coming.

Even more ironically, in gcc land, the non-local case would have been
prevented by this code GVN tries to use:

     // If any of these blocks has more than one successor (i.e. if the
edge we
     // just traversed was critical), then there are other paths through
this
     // block along which the load may not be anticipated.  Hoisting the
load
     // above this block would be adding the load to execution paths along
     // which it was not previously executed.
     if (TmpBB->getTerminator()->getNumSuccessors() != 1)
       return false;

Since it would have had edges to the exit block in any predecessor with a
may-throw call, it would have gotten the right answer.

Anyway, since i still don't plan on proposing changes here, i'm going to
stop harping on this for a while.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160715/e8cca797/attachment.html>