[llvm-dev] RFC: Strong GC References in LLVM

[Daniel Berlin via llvm-dev]

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>