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

[Daniel Berlin via llvm-dev]

On Thu, Jul 14, 2016 at 4:48 PM, Sanjoy Das <sanjoy at playingwithpointers.com>
wrote:

> Hi all,
>
> It looks like the key controversial point is the bit about the extra
> control dependence on loads and stores[0].  Generally the consensus is
> that (please chime if you think otherwise) it is not reasonable to
> make the safety (or semantics) of a load instruction depend on the
> type it is loading.  Introducing such a thing would involve changing
> the IR semantics in a fundamental way, and therefore has a high bar
> for acceptance.
>
> Here is a summary of the alternative solutions that were proposed here
> and on IRC (thanks Chandler, Andy, Eli!):
>
>  1. Model loads and stores of GC references as intrinsic calls: add
>     llvm.gc_load, llvm.gc_store intrinsics, and optimize them as loads
>     and stores whenever appropriate and legal.
>
>  2. Introduce a flag on load and stores that either
>       a. Denotes a "gc_safety" control dependence.
>       b. Denotes a "blackbox_safety" control dependence.  In this case
>          we will probably have some optional metadata on loads and
>          stores to indicate that the control dependence is actually on
>          GC safety.
>
>     As a starting point, LLVM will conservatively not speculate such
>     loads and stores; and will leave open the potential to upstream
>     logic that will have a more precise sense of when these loads and
>     stores are safe to speculate.
>

I think you need to define what you mean by control dependence here.  If
you mean speculation, you should say speculation :)
As you describe below, it is not enough to simply not speculate them. You
also are saying you don't want to change the conditions on which they
execute.
That is very different from speculation.


>  3. Introduce a general way to denote control dependence on loads and
>     stores.  This can be helpful to LLVM in general, and will let us
>     basically implement a more precise version of (2).
>


>
>
> [0]: I may have (incorrectly) mentioned otherwise on IRC, but we need
> to model safety properties of stores as well, to avoid transforms
> like:
>
>   %x = malloc()  ;; known thread local
>   if (cond_0) {
>     store GCREF %val to %x
>   }
>   if (cond_1) {
>     store i64 %val to %x
>   }
>
> to
>
>   %x = malloc()  ;; known thread local
>   if (cond_0 || cond_1) {
>     store GCREF %val to %x  ;; This "speculative" store is bad
>     if (cond_1) {
>       store i64 %val to %x
>     }
>   }
>


FWIW: This raises one of the same issues we have now with may-throw, which
is that, if all you have is a flag on the instruction, now you have to look
at every instruction in every block to know whether a *CFG* transform is
correct.

That means any pass that wants to just touch the CFG can't do so without
also looking at the instruction stream.  It will also make a bunch of
things currently O(N), O(N^2) (see the sets of patches fixing may-throw
places, and extrapolate to more places).

This is theoretically fixable in each pass by taking a single pass over the
instruction stream and marking which blocks have these instructions, etc,
and then using that info.

But we shouldn't have to do that in each pass,  especially if they just
want to make CFG manipulations.

The TL;DR  I would really like to see this also made a BB level flag that
says whether the block contains instructions with unknown control
dependences (or really, 1 bb level flag for each attribute you introduce) .
 I don't think this is terribly difficult, and at the very least, will keep
us from having to look at every instruction in the block in the common case
that there is nothing in the block to worry about ;)

Also note that these CFG transforms will also now need post-dominance info
in a bunch of cases to sanely determine if they are changing the control
dependence structure.



Let me ask another question:

Given

  %x = malloc()  ;; known thread local
  if (cond_0) {
    store GCREF %val to %x
  }
  if (cond_1) {
    store i64 %val to %x
  }
Assume i can prove cond0 and cond1 the same.


I change this to:
  %x = malloc()  ;; known thread local
  if (cond_0) {
    store i64 %val to %x
    store GCREF %val to %x
  }

Is this okay to happen?
Note that i did not actually change the control dependence of it by the
normal definition of control dependence.

But you can end up "hoisting" or "sinking" instructions by moving every
other instruction :)

Is that okay, or are they really barriers as well (like may throw), in
which case, they probably need some real representation in control flow if
you want to make most algorithms O(N) (you can get away with the bb level
flags if you are willing to make some algorithms N^2 in cases where these
things exist).
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160715/dfc1973b/attachment.html>