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

Hi Daniel,

Daniel Berlin wrote:
 >     /* Add fake edges to the function exit for any non constant and non
 >          noreturn calls (or noreturn calls with EH/abnormal edges),
 >          volatile inline assembly in the bitmap of blocks specified by
 >     BLOCKS
 >          or to the whole CFG if BLOCKS is zero.
 >     ...
 >
 >          The goal is to expose cases in which entering a basic block does
 >          not imply that all subsequent instructions must be executed.  */
 >
 >
 > 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. :)

 > For dominance, the dominance relationship for exit blocks a noreturn
 > blocks reach also changes , though i don't honestly remember if
it's
 > material or not, and i'm a bit lazy to think about it.  But here's
an
 > example:
 >
 >
 > IE given
 >
 > A (may-throw)
 > |
 > v
 > B
 > |
 > v
 > C (exit)
 >
 >
 > Here, we have A dominates B dominates C
 >
 > So the dominator tree is
 > A
 > |
 > v
 > B
 > |
 > v
 > C
 >
 > Now, if you add an edge from A to C, you have:
 >
 > A dominates B
 > Neither B nor A dominate C (C's idom is somewhere above, so it's
in a
 > sibling tree somewhere).

Not sure I understand this example -- won't C's new idom be A?  The new
graph is this, right:

A -> C
A -> B
B -> C

?

 >
 >
 > IE
 >
 > A    C
 >   |
 > B
 >
 >
 > In GCC, there is a single exit block, and it is always empty (returns
 > are connected to the exit block).
 > Thus, the above will not prevent an optimization that should otherwise
 > happen, from happening.
 >
 > Because LLVM's exit blocks contain real code, it may
 >
 > You can actually get even worse (ie really wrong) situations if the
 > "exit" blocks somehow have successors, but thankfully we
don't have a
 > case where that happens that i know :)
 >
 >

On Fri, Jul 15, 2016, 3:38 PM Sanjoy Das <sanjoy at
playingwithpointers.com>
wrote:
> Hi Daniel,
>
> Daniel Berlin wrote:
>  >     /* Add fake edges to the function exit for any non constant and
non
>  >          noreturn calls (or noreturn calls with EH/abnormal edges),
>  >          volatile inline assembly in the bitmap of blocks specified
by
>  >     BLOCKS
>  >          or to the whole CFG if BLOCKS is zero.
>  >     ...
>  >
>  >          The goal is to expose cases in which entering a basic block
> does
>  >          not imply that all subsequent instructions must be executed.
> */
>  >
>  >
>  > 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. :)
>
>  > For dominance, the dominance relationship for exit blocks a noreturn
>  > blocks reach also changes , though i don't honestly remember if
it's
>  > material or not, and i'm a bit lazy to think about it.  But
here's an
>  > example:
>  >
>  >
>  > IE given
>  >
>  > A (may-throw)
>  > |
>  > v
>  > B
>  > |
>  > v
>  > C (exit)
>  >
>  >
>  > Here, we have A dominates B dominates C
>  >
>  > So the dominator tree is
>  > A
>  > |
>  > v
>  > B
>  > |
>  > v
>  > C
>  >
>  > Now, if you add an edge from A to C, you have:
>  >
>  > A dominates B
>  > Neither B nor A dominate C (C's idom is somewhere above, so
it's in a
>  > sibling tree somewhere).
>
> Not sure I understand this example -- won't C's new idom be A?  The
new
> graph is this, right:
>
> A -> C
> A -> B
> B -> C
>
> ?
>
Yes I originally constructed the graph with two blocks with may throw
calls, then simplified it and screwed up. Such is Friday 😀
I noticed right after I sent it and left for the day but not before you
caught it.
>
>  >
>  >
>  > IE
>  >
>  > A    C
>  >   |
>  > B
>  >
>  >
>  > In GCC, there is a single exit block, and it is always empty (returns
>  > are connected to the exit block).
>  > Thus, the above will not prevent an optimization that should
otherwise
>  > happen, from happening.
>  >
>  > Because LLVM's exit blocks contain real code, it may
>  >
>  > You can actually get even worse (ie really wrong) situations if the
>  > "exit" blocks somehow have successors, but thankfully we
don't have a
>  > case where that happens that i know :)
>  >
>  >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160715/d1b6a3c2/attachment.html>

> 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.

- LLVM made the decision/tradeoff not to maintain a postdom tree throughout most
of the pass pipeline

- Fundamentally, you don’t really lose anything. It’s an easy analysis to find
the exit points and mark blocks. Doing a CFG walk instead of a PostDom walk is
typically not such a big deal.

The fundamental problem relevant to Precise GCRef is that the dependence between
program conditions and loads can’t be expressed.

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/5c6d462b/attachment.html>

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>

----- Original Message -----
> From: "Andrew Trick" <atrick at apple.com>
> To: "Sanjoy Das" <sanjoy at playingwithpointers.com>
> Cc: "Daniel Berlin" <dberlin at dberlin.org>,
"llvm-dev"
> <llvm-dev at lists.llvm.org>, "Joseph Tremoulet"
> <jotrem at microsoft.com>, "Oscar Blumberg"
> <oscar.blumberg at normalesup.org>, "Chandler Carruth"
> <chandlerc at gmail.com>, "Nick Lewycky" <nlewycky at
google.com>, "Hal
> Finkel" <hfinkel at anl.gov>, "Philip Reames"
> <listmail at philipreames.com>, "Manuel Jacob" <me at
manueljacob.de>,
> "Eli Friedman" <eli.friedman at gmail.com>, "David
Majnemer"
> <david.majnemer at gmail.com>
> Sent: Friday, July 15, 2016 6:00:12 PM
> Subject: Re: RFC: Strong GC References in LLVM
> > 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.
Why? A decision was made to give pointers types, and we've decided to change
that. It is not clear to me that the decision to allow implicit early exits was,
in retrospect, optimal. I think it is completely healthy for the project to
reevaluate these kinds of decisions. We now have many years of experience, bug
reports, and we should have a good ability to evaluate the compile-time impact
of a potential change.

-Hal 
> - LLVM made the decision/tradeoff not to maintain a postdom tree
> throughout most of the pass pipeline
> - Fundamentally, you don’t really lose anything. It’s an easy
> analysis to find the exit points and mark blocks. Doing a CFG walk
> instead of a PostDom walk is typically not such a big deal.
> The fundamental problem relevant to Precise GCRef is that the
> dependence between program conditions and loads can’t be expressed.
> 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
-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160715/5692b45a/attachment-0001.html>