[External] : Re: RFC : Approach to handle Allocation Merges in C2 Scalar Replacement

[Quân Anh Mai]

Hi,

Oh sorry, I forgot the definition part and get into the properties part
immediately. In a wrapper

    struct wrapper<T> {
        int selector;
        T* ref;
        T obj;
    };

The ref field contains the reference of an object if it has been
materialised on the heap, the obj field contains the flattened states of
that object if it has not needed to be materialised, and the selector field
indicates which of the 2 others is active. When an object has not escaped
(dynamically) and has not needed to be materialised on the heap, the
selector value indicates that the obj field is active, and any read and
write at the object should be done through obj. On the other hand, if an
object has escaped to the heap, either because it is passed to a function
or we received it from other functions instead of creating it ourselves,
any access must be done through the reference. As a result, we can delay
the allocation until the object really escapes and if it does not do so
then we have successfully eliminated a redundant allocation.

This idea comes from my attempt to legalised the selector-based allocation
merges solution. If both bases escape then we can do nothing, on the
opposite, if both bases do not escape then we can just float their loads up
through phi, the remaining concern is if 1 path escapes and the other
doesn't. My first idea is that if the def does not trivially dominate the
use, then we can create dummy values on other paths, so instead of

    if (cond) {
        T p1 = new T;
        selector = 0;
    } else {
        T p2 = callSomething(); // Or some other situations that make p2
escape such as T p2 = new T; callSomething(p2);
        selector = 1;
    }
    if (selector == 0) {
        x1 = p1.x;
    }  else {
        x2 = p2.x;
    }
    x = phi(x1, x2);

We have

    if (cond) {
        T p1 = new T;
        T q2 = null;
        selector = 0;
    } else {
        T p2 = callSomething(); // Or some other situations that make p2
escape such as T p2 = new T; callSomething(p2);
        T q1 = new T; // Just the zero value of T
        selector = 1;
    }
    T a1 = phi(p1, q1);
    T a2 = phi(q2, p2);
    if (selector == 0) {
        x1 = a1.x;
    }  else {
        x2 = a2.x;
    }
    x = phi(x1, x2);

We know that q2 and q1 will not appear at x and C2 will be happy. The
situation now transformed into us splitting the load of a1.x through phi,
which is entirely possible since both p1 and q1 do not escape so we can
float their loads freely.

Then I realised that this is the other explanation of the idea to make each
object a tagged union which tells whether it has escaped or not and this
solution can solve the more general problem. So in the end we can transform
the original program directly into

    if (cond) {
        selector1 = 0;
        T q1 = null;
        x1 = 0;
        y1 = 0;
        ... access p1 here is done through x1, y1
    } else {
        selector2 = 1;
        T q2 = callSomething();
        x2 = 0;
        y2 = 0;
        ...
    }
    selector = phi(selector1, selector2);
    q = phi(q1, q2);
    x = phi(x1, x2);
    y = phi(y1, y2);

    // And an access t = p.x would be
    if (selector == 0) {
        t1 = x;
    } else {
        t2 = q.x;
    }
    t = phi(t1, t2);

Note that if the loads can float through the phi in the first place, the
second if can be merged with the first if, and after dead code elimination
we have exactly the graph of the classic split the loads through phi
initially.

Regards,
Quan Anh

On Sat, 2 Apr 2022 at 04:50, Cesar Soares Lucas <Divino.Cesar at microsoft.com>
wrote:

> Hi, Quan Ahn.
>
>
>
> I’m currently working on solving allocation merge issue but the next task
> on my list is to improve EA/SR to be “flow-sensitive” (at least in some
> case..). So, thank you for sharing your ideas.
>
>
>
> Can you please elaborate what each of the fields in the wrapper mean?
>
>
>
>
>
> Regards,
>
> Cesar
>
>
>
> *From: *hotspot-compiler-dev <hotspot-compiler-dev-retn at openjdk.java.net>
> on behalf of Quân Anh Mai <anhmdq at gmail.com>
> *Date: *Friday, April 1, 2022 at 5:39 AM
> *To: *hotspot-compiler-dev at openjdk.java.net <
> hotspot-compiler-dev at openjdk.java.net>
> *Subject: *Re: [External] : Re: RFC : Approach to handle Allocation
> Merges in C2 Scalar Replacement
>
> [You don't often get email from anhmdq at gmail.com. Learn why this is
> important at http://aka.ms/LearnAboutSenderIdentification.]
>
> Hi,
>
> I would like to present some ideas regarding this topic. To extend the idea
> of using a selector, the scalar replacement algorithm may be generalised
> for objects to dynamically decide their escape status and act accordingly.
>
> Overall, an object of type T has a wrapper W<T> of the form:
>
>     struct W<T> {
>         int selector;
>         T* ref;
>         T obj;
>     }
>
> As a result, a creation site would be transformed:
>
>     T a = new T;
>     ->
>     wa.selector = 0;
>     wa.ref = null;
>     wa.obj = 0; // The zero instance of this object has all fields being
> zeros
>
>     T a = callSomething();
>     ->
>     wa.selector = 1;
>     wa.ref = callSomething();
>     wa.obj = 0;
>
> A use site then would be:
>
>     x = a.x;
>     ->
>     if (wa.selector == 0) {
>         x1 = wa.obj.x;
>     } else {
>         x2 = wa.ref->x;
>     }
>     x = phi(x1, x2);
>
>     escape(a);
>     ->
>     if (wa.selector == 0) {
>         ref1 = materialise(wa.obj);
>     } else {
>         ref2 = wa.ref;
>     }
>     ref = phi(ref1, ref2);
>     wa.selector = 1;
>     wa.ref = ref;
>     escape(ref);
>
> This can be thought of as a more generalised version of the current escape
> analysis, since if the object is known to not escape, its corresponding
> selector value would be always 0, and constant propagation and dead code
> elimination would remove the redundant selector and ref nodes. On the other
> hand, if an object is known to escape, its selector value would be always
> 1, and there would be no additional overhead checking for the selector.
>
> Regards,
> Quan Anh
>