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

Hi Andy,

Andrew Trick wrote:
 >
 > I don’t remember why this is important. I often don't know with
 > InstCombine whether something is needed to expose IR optimization or an
 > ISEL pattern (which should really be somehow denoted and only run in a
 > later pass).

But for the purposes of this discussion, only the legality (or lack
thereof) of the above transform matters, not whether it is profitable
or not.

 >> > Converting any GCREF to an integer is BAD, period. A single
benign
 >> use could float below a safepoint. Imagine if you expanded card marks
 >> early before step #3!
 >>
 >> Here I'm trying to constrain the optimizer -- if the frontend
wants to
 >> insert ptrtoints and knows what it is doing (because it has GC
 >> specific knowledge), then that should be fine.
 >
 > Sure, if the frontend has some way to guarantee that statepoint
 > insertion can’t happen between ptrtoint and its uses. But IR passes
 > should never generate a ptrtoint from a GCRref, regardless of how it is
 > used.
 > You want very simple rules for pass writers that are also
 > verifiable.
 > If the frontend wants to use ptrtoint on a GCRef it could
 > use an instrinsic for that purpose that is exempt from the GCRef 
verifier.

Agree on all three counts.

 >> We could speculate the load of .o if this.a could be proved to be
 >> non-null.
 >>
 >> > You could solve the dominance problem by introducing some garbage
 >> value on the ‘else’ path. But then your simple invariants don’t hold.
 >>
 >> Not sure what you mean by "simple invariants don’t hold",
but in the
 >> example above "void f(A a) {", putting junk on the else path
does not
 >> help.
 >
 > For that to work, you would have to know where potential statepoints
 > might be, which is why it breaks the invariant that GCRefs are always
 > valid, and why I proposed only doing this within the safepoint insertion
 > pass.
 >
 >> > This is optimization is probably best done contained in step #3,
 >> rewriting.
 >>
 >> I don't think that's a good idea -- we'll have to
replicate LICM
 >> inside RewriteStatepointsForGC, for instance, when we really want it
 >> to run early. Without LICM of gc references we can't get rid of
range
 >> checks in simple loops like
 >>
 >> for (int i = 0; i < this.a.length; i++)
 >> this.a[i] = 0;
 >
 > LICM isn’t speculation, unless its looking at the dereferenceable
 > attribute and the loop has conditions.

Yes, that was a poor example, a better example would be one with
conditions, as you suggest:

   for (int i = 0; i < this.a.length; i++)
     if (cond)
       this.a[i] = 0;

 > I thought your proposed solution was to *never* speculate loads of
 > GCRefs, which is strictly worse than what I’m suggesting.

My proposal to never speculate loads of GCRefs is only a starting
point.  Downstream we have analyses that use Java-specific
knowledge to infer type information (on a best-effort basis, but this
works fairly well in practice), and can use that to prove e.g. that a
certain value is of type java.lang.Foo in the loop preheader, so a
GCREF-load from offset 128 (say) can be legally issued in the loop
preheader.

 >> > Alternatively, you somehow make the dereferenceable attribute
apply
 >> to individual fields. Hasn't some sort of “assume dereferenceable”
 >> intrinsic been proposed? You would still left with the problem that
 >> you want to speculate past one level of type check.
 >>
 >> That's not sufficient for the "void f(A a) {" example --
the field at
 >> offset 16 is dereferenceable for "a", but it can't be
loaded as a
 >> GCREF.
 >
 > I think there is an important design question here, because I’ve also
 > heard grumbling about LLVM’s lack of condition dependence tracking
 > outside of the GCRef context.
 >
 > +CC Daniel Berlin
 >
 > If you can come up with an IR design for tracking your GCRef load
 > depedencies (usually on specific null and type checks), then that could

That sounds orthogonal to this proposal -- as a starting point we need
a simple way to mark a GCRef load as control dependent on every
condition executed since the start of the program.  Something like
cast-to-dereferenceable can possibly be added once we start
upstreaming analyses that prove that a GCRef load is safe to
speculate, but that's for better performance not correctness.

Having said that, I'll keep the "explicit control dependence" idea
in
mind -- maybe there is way to find "a simple way to mark a GCRef load
as control dependent on every condition executed since the start of
the program" that can be generalized to remember more precise control
dependence later.

 > solve some of the other difficult problems that others are wrestling
 > with (sorry I don’t have a pointer to the discussions). This probably
 > means inserting some cast-to-dereferenceable instruction on the address
 > generation def-use chain.
 >
 > Otherwise, you have to either impose some subtle rules on IR
 > optimization passes, or make all GCRef loads intrinsics, which is also a
 > maintenance burden.


 >> The "runtime" comes in and modifies values of type GCREF to
contain
 >> different bitwise representations pointing to the same logical object.
 >> It can't do this rewriting if a GCREF value contains some random
 >> bitwise pattern, since that won't point to a valid object on the
heap.
 >
 > Ok, but you also said the derived GCRef can be any bit pattern due to
 > out-of-bounds addressing. I think there is a constraint that the offset
 > from the GC root can be determined via a straightforward analysis.

You're right -- that's missing in the specification (derived pointer
provenance), I'll add that in in the next iteration.

 >> I've explicitly not talked about safepoints at all here -- GCREF
 >> values always have to hold "valid" references, and what a
valid
 >> reference is changes at arbitrary points in time (and at this layer
 >> there are no "safepoints" denoting the only places where the
 >> definition of a valid reference can change). This means, in general,
 >> you can not for sure say that an integer contains a bitwise value that
 >> is a valid GC reference, and even if you have one at a certain point
 >> in time that it will stay valid in the next instant.
 >
 > Well, it would be much much easier to understand and verify if inttoptr
 > were simply illegal. It’s confusing because the integer is defined
 > somewhere else, yet it needs to be a valid GCRef at the point of use and
 > you don’t want to allow GCRefs to live in integer values.
 >
 > As with ptrtoint, this seems like it would be better as a separate
 > intrinsic if some hypothetical frontend needs it.

I think this is the most straightforward path forward ^.

 > If this is allowed, doesn’t the integer need to be a GCRoot so a simple
 > analysis can determine the offset?

 >> > Is this supposed to be 'inttoptr’? I don’t see how this can
work at
 >> all, since the integer’s lifetime can extend beyond a safepoint.
 >>
 >> Do you mean the initial example? That is fine if <condition> is
 >> always false at runtime.
 >
 > The title of the example says “inttoptr”…

Yes, that's just a typo in the code example; sorry.

 >> > Do you really need to support constant GCRefs? Cliff Click said
it
 >> was a bad decision.
 >>
 >> Typically we don't need inttoptr to GCREFs, but other runtimes
might.
 >> I'm happy to not support it for now.
 >
 > Again, this may be better served with a gcref_to_int intrinsic that
 > cannot be hoisted.

Yes.

 >>
 >> Above the use of l in "l + 20" has to be fine, and not UB.
 >
 > Good example.
 >
 > Of course, it could be just another instance of a “no inttoptr/ptrtoint”
 > rule.

That should work.

 >
 >> >> ## Implementation Issues& Impact to LLVM
 >> >>
 >> >> This is a proposed path forward to implementing GCREF in
LLVM. The
 >> >> caveat mentioned at the start of the email (everything is
open for
 >> >> discussion) especially applies here.
 >> >>
 >> >> ### Changes to IR to represent GCREF
 >> >>
 >> >> We change `datalayout` to denote pointers of a specific
address space
 >> >> as GCREFs. We add verifier rules forbidding `inttoptr`
conversion of
 >> >> integers into GCREFs and add an intrinsic (that can be
control
 >> >> dependent) that converts integers to GCREFs.
 >
 > This intrinsic sounds like what I’m suggesting, except that I’m
 > suggesting that the frontend can hypothetically generate the intrinsic
 > if needed, and rather than prohibiting `inttoptr/ptrtoint` conversion,
 > you outright inhibit it’s existence, which is trivial to verify.

Sounds good.

 >> > Sounds good to me. If you really need Int->GCRef conversion,
then it
 >> seems like it needs to be an intrinsic with side effects, contrary to
 >> many of your examples.
 >>
 >> Yes. The other solution is to make `inttoptr` a side effect depending
 >> on the result type, but that sounds like a bad idea.
 >
 > I think you want side effects on the Int->GCRef intrinsic (hoisting it
 > is illegal, sinking it below calls is illegal), and don’t want to use
 > inttoptr at all.

Yes.

[snip]

-- Sanjoy

> On Jul 12, 2016, at 4:42 PM, Sanjoy Das <sanjoy at
playingwithpointers.com> wrote:
> 
> Hi Andy,
> 
> Andrew Trick wrote:
> >
> > I don’t remember why this is important. I often don't know with
> > InstCombine whether something is needed to expose IR optimization or
an
> > ISEL pattern (which should really be somehow denoted and only run in a
> > later pass).
> 
> But for the purposes of this discussion, only the legality (or lack
> thereof) of the above transform matters, not whether it is profitable
> or not.
Given that you will need to disable the transform for GCRefs, it’s interesting
that if it’s only something that needs to run before ISEL then you’re not
actually losing any optimization.
> 
> > If you can come up with an IR design for tracking your GCRef load
> > depedencies (usually on specific null and type checks), then that
could
> 
> That sounds orthogonal to this proposal -- as a starting point we need
> a simple way to mark a GCRef load as control dependent on every
> condition executed since the start of the program.  Something like
> cast-to-dereferenceable can possibly be added once we start
> upstreaming analyses that prove that a GCRef load is safe to
> speculate, but that's for better performance not correctness.
I thought your frontend would know which conditions guard each field access.
> Having said that, I'll keep the "explicit control dependence"
idea in
> mind -- maybe there is way to find "a simple way to mark a GCRef load
> as control dependent on every condition executed since the start of
> the program" that can be generalized to remember more precise control
> dependence later.
I only suggested it at this point because you mentioned how much work
implementing optimizations on a gc_load intrinsic would be, and that time could
otherwise be directed to a general LLVM improvement.

If it’s reasonable to prohibit speculation on normal loads where the loaded
value happens to be a GCRef, then of course that’s easiest.

-Andy

Hi Andy,

Andrew Trick wrote:
 >> But for the purposes of this discussion, only the legality (or lack
 >> thereof) of the above transform matters, not whether it is profitable
 >> or not.
 >
 > Given that you will need to disable the transform for GCRefs, it’s 
interesting that if it’s only something that needs to run before ISEL 
then you’re not actually losing any optimization.

Ah, okay; that makes sense.

 >>> If you can come up with an IR design for tracking your GCRef load
 >>> depedencies (usually on specific null and type checks), then that
could
 >> That sounds orthogonal to this proposal -- as a starting point we need
 >> a simple way to mark a GCRef load as control dependent on every
 >> condition executed since the start of the program.  Something like
 >> cast-to-dereferenceable can possibly be added once we start
 >> upstreaming analyses that prove that a GCRef load is safe to
 >> speculate, but that's for better performance not correctness.
 >
 > I thought your frontend would know which conditions guard each field 
access.

At a theoretical level it does, but in practice that kind of control
dependence can be difficult to split apart from "normal" control
dependence.

For instance, if we have:

   interface I {
     void func();
   }

   class F {
     Object o;
     void func() {
       Object val = this.o;
     }
   }

   class G {
     public static void f(I instance) {
       instance.func();
     }
   }

then when compiling func() separately there is nothing the load of val
is control dependent on, but in G::f if we do some form of predicated
devirtualization and then inline the body of F::func then the safety
of the load is predicated on the devirtualization predicate passing
too.  If the predicated devirt. was itself conditional on some control
flow based type refinement, then the safety of the load is control
dependent on that control flow as well, and so on.

[snip]

-- Sanjoy