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

Vladimir Kozlov vladimir.kozlov at oracle.com
Wed Mar 30 23:54:23 UTC 2022


I was not able to reproduce the issue with my test and your patch.

Also try to comment out/remove next your new lines to keep orig_load_mem:

+  // Create unique input for "memory" of Load
+  Node* orig_load_mem   = original_load->in(LoadNode::Memory);
+  new_load->replace_edge(orig_load_mem, orig_load_mem->is_Phi() ? orig_load_mem->in(idx) : orig_load_mem);


Thanks,
Vladimir K

On 3/30/22 2:32 PM, Vladimir Kozlov wrote:
> On 3/30/22 2:28 PM, Vladimir Kozlov wrote:
>> Hi Cesar,
>>
>> Can you also send me your test file TestSimpleMerge.java. I need to reproduce your failure.
>>
>> Currently I see wrong memeory edge in LoadI [231] node because it points to memory [122] on path which is not fully 
>> dominating (on code branch).
> 
> The memory should be this Phi:
> 
>   182  Phi  ===  105  122  43  [[ 18 ]]  #memory  Memory: @TestSimpleMerge$Point+12 *, name=x, idx=6; !jvms: 
> TestSimpleMerge::test @ bci:22 (line 14)
> 
> May be we got some partial split through Phi transformation which is causing the issue.
> 
>>
>> Thanks,
>> Vladimir K
>>
>> [1]
>>
>>   41  Initialize  ===  33  1  44  1  1  40  90  [[ 42  43 ]]  !jvms: TestSimpleMerge::test @ bci:0 (line 9)
>>   43  Proj  ===  41  [[ 133  132  131  123  179  180  181  182  53  53  53  53  233 ]] #2  Memory: @rawptr:BotPTR, 
>> idx=Raw; !jvms: TestSimpleMerge::test @ bci:0 (line 9)
>>   101  IfFalse  ===  99  [[ 105 ]] #0 !jvms: TestSimpleMerge::test @ bci:10 (line 11)
>>
>>   120  Initialize  ===  112  1  123  1  1  119  171  [[ 121  122 ]]  !jvms: TestSimpleMerge::test @ bci:13 (line 12)
>>   122  Proj  ===  120  [[ 182  181  180  179  231 ]] #2  Memory: @rawptr:BotPTR, idx=Raw; !jvms: TestSimpleMerge::test 
>> @ bci:13 (line 12)
>>   121  Proj  ===  120  [[ 105  124 ]] #0 !jvms: TestSimpleMerge::test @ bci:13 (line 12)
>>
>>   221  ConI  ===  0  [[ 220  225 ]]  #int:0
>>   222  ConI  ===  0  [[ 220 ]]  #int:1
>>
>>   105  Region  ===  105  121  101  [[ 105  220  178  179  180  181  182  227 ]]  !jvms: TestSimpleMerge::test @ bci:22 
>> (line 14)
>>
>>   220  Phi  ===  105  221  222  [[ 225 ]]  #int
>>   225  CmpI  === _  220  221  [[ 226 ]]
>>   226  Bool  === _  225  [[ 227 ]] [eq]
>>   227  If  ===  105  226  [[ 228  229 ]] P=0.000000, C=0.000000
>>
>>   229  IfFalse  ===  227  [[ 233  223 ]] #0
>>   233  LoadI  ===  229  43  232  [[ 224 ]]  @TestSimpleMerge$Point+12 *, name=x, idx=6; #int !orig=[207] !jvms: 
>> TestSimpleMerge$Point::calc @ bci:1 (line 5) TestSimpleMerge::test @ bci:23 (line 14)
>>
>>   228  IfTrue  ===  227  [[ 231  223 ]] #1
>>   231  LoadI  ===  228  122  230  [[ 224 ]]  @TestSimpleMerge$Point+12 *, name=x, idx=6; #int !orig=[207] !jvms: 
>> TestSimpleMerge$Point::calc @ bci:1 (line 5) TestSimpleMerge::test @ bci:23 (line 14)
>>
>>   223  Region  ===  223  228  229  [[ 223  224  216 ]]
>>   224  Phi  ===  223  231  233  [[ 216 ]]  #int
>>   216  Return  ===  223  178  18  8  9 returns 224  [[ 0 ]]
>>
>> On 3/29/22 5:34 PM, Cesar Soares Lucas wrote:
>>> Hi, Vladimir.
>>>
>>> Thank you for getting back to me. What you describe is exactly what I understand and what I tried to implement. I 
>>> also noticed the issue with the nodes floating up and I even tried to prevent that.. but I think the root of the 
>>> problem is somewhere else.
>>>
>>> Please take a look at this printout: https://www.dropbox.com/s/ao30zadovwqswlp/splitted.txt?dl=0 
>>> <https://urldefense.com/v3/__https://www.dropbox.com/s/ao30zadovwqswlp/splitted.txt?dl=0__;!!ACWV5N9M2RV99hQ!ZJvmUIbT0x_YJJPA3ap6R-qkOaEsH3YOGwu47flogbZamqV6nWVO2Kfx8uUYnVTddI45Zg$> 
>>> . C2 tells me that this graph has bad dominance: “Use 228 isn’t dominated by def 231”. This error message is result 
>>> of this verification: https://github.com/openjdk/jdk/blob/master/src/hotspot/share/opto/loopnode.cpp#L5361 
>>> <https://urldefense.com/v3/__https://github.com/openjdk/jdk/blob/master/src/hotspot/share/opto/loopnode.cpp*L5361__;Iw!!ACWV5N9M2RV99hQ!ZJvmUIbT0x_YJJPA3ap6R-qkOaEsH3YOGwu47flogbZamqV6nWVO2Kfx8uUYnVSGiICGJw$> 
>>>
>>>
>>> I agree and disagree with the message. I’m not sure if it’s my limited knowledge of C2 IR or some wording problem in 
>>> the message: why would 228 need to be dominated by 231 - after all 228 doesn’t use 231? The opposite makes more sense 
>>> to me: 228 needs to dominate 231 – and that is true AFAICT. Nonetheless, I agree with the message that there is 
>>> something wrong in the graph: this graph allows for execution to reach node 231 without node 124 being executed!
>>>
>>> I created this DRAFT PR so that you can look at the code if you want: https://github.com/openjdk/jdk/pull/8023 
>>> <https://urldefense.com/v3/__https://github.com/openjdk/jdk/pull/8023__;!!ACWV5N9M2RV99hQ!ZJvmUIbT0x_YJJPA3ap6R-qkOaEsH3YOGwu47flogbZamqV6nWVO2Kfx8uUYnVQl2jEXlA$> 
>>> .
>>>
>>> Please let me know what you think. TIA!
>>>
>>> Cesar
>>>
>>> *From: *Vladimir Kozlov <vladimir.kozlov at oracle.com>
>>> *Date: *Monday, March 28, 2022 at 10:48 AM
>>> *To: *Cesar Soares Lucas <Divino.Cesar at microsoft.com>, Vladimir Ivanov <vladimir.x.ivanov at oracle.com>, hotspot 
>>> compiler <hotspot-compiler-dev at openjdk.java.net>
>>> *Cc: *Brian Stafford <Brian.Stafford at microsoft.com>, Martijn Verburg <Martijn.Verburg at microsoft.com>
>>> *Subject: *Re: [External] : Re: RFC : Approach to handle Allocation Merges in C2 Scalar Replacement
>>>
>>> Hi Cesar
>>>
>>> On 3/17/22 12:15 PM, Cesar Soares Lucas wrote:
>>>> Hi all,
>>>>
>>>> I’ve been experimenting with the idea explained by Vladimir Ivanov and I was able to implement it and have a few
>>>> non-trivial merges untangled and scalar replaced. However, I found an obstacle on the road. I was able to overcome it,
>>>> but I’d very much appreciate your opinion about the matter. Assume we start off with the piece of code below.
>>>>
>>>> if (…)     p0 = …
>>>>
>>>> else       p1 = …
>>>>
>>>> p = phi(p0, p1)
>>>>
>>>> return p.x
>>>>
>>>> The idea proposed suggests, AFAIU, that we change the code to be something like the below **where we use the bases
>>>> directly**.
>>>>
>>>> if (…)   p0 = …
>>>>
>>>> else     p1 = …
>>>>
>>>> s = # selector phi #
>>>>
>>>> if (s == id_base0)           x0 = p0.x
>>>>
>>>> elseif (s == id_base1)    x1 = p1.x
>>>>
>>>> else                                  halt()
>>>>
>>>> x = phi(x0, x1)
>>>>
>>>> return x
>>>>
>>>> The problem here is that the definition of “p0” and/or “p1” doesn’t dominate their use in the loads “x0 = p0.x” / “x1 =
>>>> p1.x”, therefore certain IR verification steps in C2 fail. I was able to work around the issue by adding Phi nodes 
>>>> where
>>>> all inputs are the same (excluding the ctrl), thus creating a “fake” definition for the value. Please see code below.
>>>
>>> You have original `p = phi(p0, p1)` which is attached to Region node which merges paths with p0 and p1. `Selector ID
>>> Phi(id_p0, id_p1)` should be attached to the same Region and guarantee that p0 and p1 are defined at that point. The
>>> only issue could be is that load nodes don't have control edges and depend on memory edges to schedule. So they could
>>> float up. I think they should be attached (control edge) to id checks (s == id_base*) to prevent them move up as new
>>> special case [1]. At least as first approach for experiment.
>>>
>>> Thanks,
>>> Vladimir K
>>>
>>> [1] 
>>> https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Fgithub.com%2Fopenjdk%2Fjdk%2Fblob%2Fmaster%2Fsrc%2Fhotspot%2Fshare%2Fopto%2Fmemnode.cpp%23L1737&data=04%7C01%7CDivino.Cesar%40microsoft.com%7Cd6152056b06744f7359e08da10e33a44%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637840865379084345%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=HaPBCqckab%2BpOcIoYEccL04u1o1pqqaUjsYMCslfP7Y%3D&reserved=0 
>>> <https://urldefense.com/v3/__https://nam06.safelinks.protection.outlook.com/?url=https*3A*2F*2Fgithub.com*2Fopenjdk*2Fjdk*2Fblob*2Fmaster*2Fsrc*2Fhotspot*2Fshare*2Fopto*2Fmemnode.cpp*23L1737&data=04*7C01*7CDivino.Cesar*40microsoft.com*7Cd6152056b06744f7359e08da10e33a44*7C72f988bf86f141af91ab2d7cd011db47*7C1*7C0*7C637840865379084345*7CUnknown*7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0*3D*7C3000&sdata=HaPBCqckab*2BpOcIoYEccL04u1o1pqqaUjsYMCslfP7Y*3D&reserved=0__;JSUlJSUlJSUlJSUlJSUlJSUlJSUlJSUlJSUl!!ACWV5N9M2RV99hQ!ZJvmUIbT0x_YJJPA3ap6R-qkOaEsH3YOGwu47flogbZamqV6nWVO2Kfx8uUYnVTydJtLxg$> 
>>>
>>>
>>>>
>>>> if (…)   p0 = …
>>>>
>>>> else     p1 = …
>>>>
>>>> phi0 = phi(p0, p0)
>>>>
>>>> phi1 = Phi(p1, p1)
>>>>
>>>> s = # selector phi #
>>>>
>>>> if (s == id_base0)           x0 = phi0.x
>>>>
>>>> elseif (s == id_base1)    x1 = phi1.x
>>>>
>>>> else                                  halt()
>>>>
>>>> x = phi(x0, x1)
>>>>
>>>> return x
>>>>
>>>> Transforming the code to look like the above silenced the verifications ( :-] ) and at the end EA+SR was able to remove
>>>> the allocations **and get rid of all the Phi’s**.
>>>>
>>>> So, my question is: is this workaround acceptable? Do you have a suggestion of a better solution?
>>>>
>>>> TIA, Cesar
>>>>
>>>> *From: *hotspot-compiler-dev <hotspot-compiler-dev-retn at openjdk.java.net> on behalf of Cesar Soares Lucas
>>>> <Divino.Cesar at microsoft.com>
>>>> *Date: *Tuesday, February 22, 2022 at 10:01 AM
>>>> *To: *Vladimir Ivanov <vladimir.x.ivanov at oracle.com>, Vladimir Kozlov <vladimir.kozlov at oracle.com>, hotspot compiler
>>>> <hotspot-compiler-dev at openjdk.java.net>
>>>> *Cc: *Brian Stafford <Brian.Stafford at microsoft.com>, Martijn Verburg <Martijn.Verburg at microsoft.com>
>>>> *Subject: *Re: [External] : Re: RFC : Approach to handle Allocation Merges in C2 Scalar Replacement
>>>>
>>>> Hi Vladimir,
>>>>
>>>> I think I've enough feedback to start working on a prototype and see how things play out. Thank you for sharing your
>>>> ideas/expertise!
>>>>
>>>>
>>>> Cheers,
>>>> Cesar
>>>>
>>>> ________________________________________
>>>> From: Vladimir Ivanov <vladimir.x.ivanov at oracle.com>
>>>> Sent: February 21, 2022 10:26 AM
>>>> To: Cesar Soares Lucas; Vladimir Kozlov; hotspot compiler
>>>> Cc: Brian Stafford; Martijn Verburg
>>>> Subject: Re: [External] : Re: RFC : Approach to handle Allocation Merges in C2 Scalar Replacement
>>>>
>>>> Hi Cesar,
>>>>
>>>>> I with the selector-based base splitting idea using some examples and I think I understand the mechanics well. It's 
>>>>> conceptually simple and quite effective, I like it! I've another question, though. From your previous message I had 
>>>>> understood that we needed the clustering because split_unique_types can't handle multiple bases at once, which 
>>>>> makes sense to me. _This time I
>>>> don't understand why we need to do the clustering before doing the selector-based transformation_. AFAIU this
>>>> transformation won't be creating any memory slices but rather just assigning IDs to different bases and then creating
>>>> specialized memory operations conditionally using the different bases.
>>>>
>>>> Yes, that's a valid simplification. It does sound like introducing
>>>> selector ID doesn't require a separate memory graph (and can be
>>>> performed before split_unique_types()), but I don't have a good
>>>> understanding how complicated simplifying selector-based IR shapes would
>>>> be compared to original (memory op-based) ones. It's definitely worth
>>>> experimenting with.
>>>>
>>>> Best regards,
>>>> Vladimir Ivanov
>>>>
>>>>> ________________________________________
>>>>> From: Vladimir Ivanov <vladimir.x.ivanov at oracle.com>
>>>>> Sent: February 17, 2022 7:37 AM
>>>>> To: Vladimir Kozlov; Cesar Soares Lucas; hotspot compiler
>>>>> Cc: Brian Stafford; Martijn Verburg
>>>>> Subject: Re: RFC : Approach to handle Allocation Merges in C2 Scalar Replacement
>>>>>
>>>>>
>>>>>> But depending on the actual shape of the base pointer (here it's
>>>>>> Phi(obj1,obj2)), it may become infeasible (from performance perspective)
>>>>>> or even impossible (e.g., for complex loop variant conditions) to
>>>>>> separate instance slices.
>>>>>
>>>>> I'd like to correct myself. After thinking more about the problem, I see
>>>>> a universal way to scalarize clusters of interfering non-escaping
>>>>> allocations even in presence of accesses with indeterminate base.
>>>>>
>>>>> The crucial property for such cluster of interacting non-escaping
>>>>> allocations is for any memory access its base is either part of the
>>>>> cluster or not (it's a static property for every access). Then, when it
>>>>> is part of the cluster, then the number of possible base values at
>>>>> runtime is finite and is a subset of the cluster.
>>>>>
>>>>> So, memory graph for the cluster can be scalarized as follows:
>>>>>
>>>>>      (1) separate memory graph for the cluster
>>>>>
>>>>>      (2) on the newly constructed graph:
>>>>>
>>>>>         (a) replace every base pointer with an ID ("selector id") and
>>>>> recreate data graph for selector IDs from base pointers graph;
>>>>>
>>>>>         (b) for accesses with indeterminate base pointer, replace them
>>>>> with a merge of states from relevant allocations selected by "selector id"
>>>>>
>>>>>         (c) after 2b, all memory accesses from the cluster memory graph
>>>>> should have fixed base pointing at a particular allocation
>>>>>
>>>>>      (3) scalarize individual allocations from the cluster one by one
>>>>> (since they are independent now)
>>>>>
>>>>>         - additional transformation (like, split-through-phi) should
>>>>> simplify the graph by reducing the number of cases at merge points to
>>>>> care about (ideally, leaving only a single one);
>>>>>
>>>>>
>>>>>
>>>>> As an illustration:
>>>>>
>>>>>      val = Load (AddP (Phi R base1 base2) offset) mem # load A.i
>>>>>
>>>>> ==(pseudo-code)==>
>>>>>
>>>>>      selector = (Phi R #base1 #base2)
>>>>>
>>>>>      if (selector == #base1) {
>>>>>        val1 = Load (base1 + offset) mem
>>>>>      } else if (selector == #base2) {
>>>>>        val2 = Load (base2 + offset) mem
>>>>>      } else {
>>>>>        halt(); // impossible
>>>>>      }
>>>>>
>>>>>      val = Phi(R1, val1, val2)
>>>>>
>>>>> ======
>>>>>
>>>>>      Store (AddP (Phi R base1 base2) offset) mem v # store A.i v
>>>>>
>>>>> ==(pseudo-code)==>
>>>>>
>>>>>      selector = (Phi R #base1 #base2)
>>>>>
>>>>>      if (selector == #base1) {
>>>>>        Store base1 mem v ==> mem1
>>>>>      } else if (selector == #base2) {
>>>>>        Store base2 mem v ==> mem2
>>>>>      } else {
>>>>>        halt(); // impossible
>>>>>      }
>>>>>
>>>>>      mem = Phi(R1, mem1, mem2);
>>>>>
>>>>>
>>>>> Best regards,
>>>>> Vladimir Ivanov
>>>>>
>>>>>>
>>>>>> So, gradual approach seems the way to go:
>>>>>>      (1) split memory graph for clusters of interacting non-escaping
>>>>>> allocations;
>>>>>>
>>>>>>      (2) perform adhoc transformation targeted at untangling aliasing
>>>>>> accesses (e.g, split-through-phi);
>>>>>>
>>>>>>      (3) extract unique instance types where possible, thus making the
>>>>>> corresponding allocation scalar replaceable
>>>>>>
>>>>>> =====================================================================
>>>>>>
>>>>>> Also, one observation: interacting allocations don't have to be of the
>>>>>> same class.
>>>>>>
>>>>>>        static int testPolluted(int r, boolean b) {
>>>>>>            A obj1 = new B1(r);
>>>>>>            A obj2 = new B2(r);
>>>>>>
>>>>>>            A obj = (b ? obj1 : obj2);
>>>>>>            for (int i = 1; i < r; i++) {
>>>>>>                obj.i++;
>>>>>>            }
>>>>>>
>>>>>>            return obj1.i + obj2.i;
>>>>>>        }
>>>>>>
>>>>>> Requiring unique instance types to perform SR (and not enhancing SR to
>>>>>> handle aliasing allocations case) helps avoid some challenges in
>>>>>> instance rematerialization logic at safepoints, because actual shape of
>>>>>> the scalarized object (its class and exact set of fields) becomes a
>>>>>> runtime property.
>>>>>>
>>>>>> Best regards,
>>>>>> Vladimir Ivanov
>>>>>>
>>>>>>>>>
>>>>>>>>> Otherwise, I believe wide memory states/merges would pose serious
>>>>>>>>> problems. E.g., when a load is split through a phi, you need to pick
>>>>>>>>> correct memory states for the new loads above the phi which quickly
>>>>>>>>> becomes quite a challenging task.
>>>>>>>>
>>>>>>>> Especially in loops. Actually I did tried such approach before and I
>>>>>>>> agree that it is hard.
>>>>>>>>
>>>>>>>> Thanks,
>>>>>>>> Vladimir K
>>>>>>>>
>>>>>>>>>
>>>>>>>>> Best regards,
>>>>>>>>> Vladimir Ivanov
>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> public int ex1(boolean cond, int first, int second) {
>>>>>>>>>>        p0 = Allocate(...);
>>>>>>>>>>        ...
>>>>>>>>>>        p0.x = first;
>>>>>>>>>>        p0.y = second;
>>>>>>>>>>
>>>>>>>>>>        if (cond) {
>>>>>>>>>>            p1 = Allocate(...);
>>>>>>>>>>            ...
>>>>>>>>>>            p1.x = second;
>>>>>>>>>>            p1.y = first;
>>>>>>>>>>        }
>>>>>>>>>>
>>>>>>>>>>        p = phi(p0, p1) // unused and will be removed
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>        return phi(p0.x,p1.x) - phi(p0.y, p1.y);
>>>>>>>>>> }
>>>>>>>>>>
>>>>>>>>>> Thanks,
>>>>>>>>>> Vladimir K
>>>>>>>>>>
>>>>>>>>>> On 2/10/22 11:29 AM, Vladimir Ivanov wrote:
>>>>>>>>>>> (BCCing hotspot-dev and moving the discussion to
>>>>>>>>>>> hotspot-compiler-dev.)
>>>>>>>>>>>
>>>>>>>>>>> Hi Cesar,
>>>>>>>>>>>
>>>>>>>>>>> Thanks for looking into enhancing EA.
>>>>>>>>>>>
>>>>>>>>>>> Overall, the proposal looks reasonable.
>>>>>>>>>>>
>>>>>>>>>>> I suggest to look more closely at split_unique_types().
>>>>>>>>>>> It introduces a dedicated class of alias categories for fields of
>>>>>>>>>>> the allocation being eliminated and clones memory graph. I don't
>>>>>>>>>>> see why it shouldn't work for multiple allocations.
>>>>>>>>>>>
>>>>>>>>>>> Moreover, split_unique_types() will break if you start optimizing
>>>>>>>>>>> multiple allocations at once. The notion of unique alias should be
>>>>>>>>>>> adjusted and cover the union of unique aliases for all interacting
>>>>>>>>>>> allocations.
>>>>>>>>>>>
>>>>>>>>>>> Seems like you need to enhance SR to work on non-intersecting
>>>>>>>>>>> clusters of allocations.
>>>>>>>>>>>
>>>>>>>>>>> One thing to take care of: scalar replacement relies on
>>>>>>>>>>> TypeOopPtr::instance_id().
>>>>>>>>>>>
>>>>>>>>>>>      // If not InstanceTop or InstanceBot, indicates that this is
>>>>>>>>>>>      // a particular instance of this type which is distinct.
>>>>>>>>>>>      // This is the node index of the allocation node creating this
>>>>>>>>>>> instance.
>>>>>>>>>>>      int           _instance_id;
>>>>>>>>>>>
>>>>>>>>>>> It'll break when multiple allocations are in play.
>>>>>>>>>>>
>>>>>>>>>>> Best regards,
>>>>>>>>>>> Vladimir Ivanov
>>>>>>>>>>>
>>>>>>>>>>> On 09.02.2022 04:45, Cesar Soares Lucas wrote:
>>>>>>>>>>>> Hi there again!
>>>>>>>>>>>>
>>>>>>>>>>>> Can you please give me feedback on the following approach to at
>>>>>>>>>>>> least partially
>>>>>>>>>>>> address [1], the scalar replacement allocation merge issue?
>>>>>>>>>>>>
>>>>>>>>>>>> The problem that I am trying to solve arises when allocations are
>>>>>>>>>>>> merged after a
>>>>>>>>>>>> control flow split. The code below shows _one example_ of such a
>>>>>>>>>>>> situation.
>>>>>>>>>>>>
>>>>>>>>>>>> public int ex1(boolean cond, int x, int y) {
>>>>>>>>>>>>        Point p = new Point(x, y);
>>>>>>>>>>>>        if (cond)
>>>>>>>>>>>>            p = new Point(y, x);
>>>>>>>>>>>>        // Allocations for p are merged here.
>>>>>>>>>>>>        return p.calc();
>>>>>>>>>>>> }
>>>>>>>>>>>>
>>>>>>>>>>>> Assuming the method calls on "p" are inlined then the allocations
>>>>>>>>>>>> will not
>>>>>>>>>>>> escape the method. The C2 IR for this method will look like this:
>>>>>>>>>>>>
>>>>>>>>>>>> public int ex1(boolean cond, int first, int second) {
>>>>>>>>>>>>        p0 = Allocate(...);
>>>>>>>>>>>>        ...
>>>>>>>>>>>>        p0.x = first;
>>>>>>>>>>>>        p0.y = second;
>>>>>>>>>>>>
>>>>>>>>>>>>        if (cond) {
>>>>>>>>>>>>            p1 = Allocate(...);
>>>>>>>>>>>>            ...
>>>>>>>>>>>>            p1.x = second;
>>>>>>>>>>>>            p1.y = first;
>>>>>>>>>>>>        }
>>>>>>>>>>>>
>>>>>>>>>>>>        p = phi(p0, p1)
>>>>>>>>>>>>
>>>>>>>>>>>>        return p.x - p.y;
>>>>>>>>>>>> }
>>>>>>>>>>>>
>>>>>>>>>>>> However, one of the constraints implemented here [2],
>>>>>>>>>>>> specifically the third
>>>>>>>>>>>> one, will prevent the objects from being scalar replaced.
>>>>>>>>>>>>
>>>>>>>>>>>> The approach that I'm considering for solving the problem is to
>>>>>>>>>>>> replace the Phi
>>>>>>>>>>>> node `p = phi(p0, p1)` with new Phi nodes for each of the fields
>>>>>>>>>>>> of the objects
>>>>>>>>>>>> in the original Phi. The IR for `ex1` would look something like
>>>>>>>>>>>> this after the
>>>>>>>>>>>> transformation:
>>>>>>>>>>>>
>>>>>>>>>>>> public int ex1(boolean cond, int first, int second) {
>>>>>>>>>>>>        p0 = Allocate(...);
>>>>>>>>>>>>        ...
>>>>>>>>>>>>        p0.x = first;
>>>>>>>>>>>>        p0.y = second;
>>>>>>>>>>>>
>>>>>>>>>>>>        if (cond) {
>>>>>>>>>>>>            p1 = Allocate(...);
>>>>>>>>>>>>            ...
>>>>>>>>>>>>            p1.x = second;
>>>>>>>>>>>>            p1.y = first;
>>>>>>>>>>>>        }
>>>>>>>>>>>>
>>>>>>>>>>>>        pX = phi(first, second)
>>>>>>>>>>>>        pY = phi(second, first)
>>>>>>>>>>>>
>>>>>>>>>>>>        return pX - pY;
>>>>>>>>>>>> }
>>>>>>>>>>>>
>>>>>>>>>>>> I understand that this transformation might not be applicable for
>>>>>>>>>>>> all cases and
>>>>>>>>>>>> that it's not as simple as illustrated above. Also, it seems to
>>>>>>>>>>>> me that much of
>>>>>>>>>>>> what I'd have to implement is already implemented in other steps
>>>>>>>>>>>> of the Scalar
>>>>>>>>>>>> Replacement pipeline (which is a good thing). To work around these
>>>>>>>>>>>> implementation details I plan to use as much of the existing code
>>>>>>>>>>>> as possible.
>>>>>>>>>>>> The algorithm for the transformation would be like this:
>>>>>>>>>>>>
>>>>>>>>>>>> split_phis(phi)
>>>>>>>>>>>>        # If output of phi escapes, or something uses its identity, etc
>>>>>>>>>>>>        # then we can't remove it. The conditions here might
>>>>>>>>>>>> possible be the
>>>>>>>>>>>>        # same as the ones implemented in
>>>>>>>>>>>> `PhaseMacroExpand::can_eliminate_allocation`
>>>>>>>>>>>>        if cant_remove_phi_output(phi)
>>>>>>>>>>>>            return ;
>>>>>>>>>>>>
>>>>>>>>>>>>        # Collect a set of tuples(F,U) containing nodes U that uses
>>>>>>>>>>>> field F
>>>>>>>>>>>>        # member of the object resulting from `phi`.
>>>>>>>>>>>>        fields_used = collect_fields_used_after_phi(phi)
>>>>>>>>>>>>
>>>>>>>>>>>>        foreach field in fields_used
>>>>>>>>>>>>            producers = {}
>>>>>>>>>>>>
>>>>>>>>>>>>            # Create a list with the last Store for each field
>>>>>>>>>>>> "field" on the
>>>>>>>>>>>>            # scope of each of the Phi input objects.
>>>>>>>>>>>>            foreach o in phi.inputs
>>>>>>>>>>>>                # The function called below might re-use a lot of
>>>>>>>>>>>> the code/logic in `PhaseMacroExpand::scalar_replacement`
>>>>>>>>>>>>                producers += last_store_to_o_field(0, field)
>>>>>>>>>>>>            # Create a new phi node whose inputs are the Store's to
>>>>>>>>>>>> 'field'
>>>>>>>>>>>>            field_phi = create_new_phi(producers)
>>>>>>>>>>>>
>>>>>>>>>>>>            update_consumers(field, field_phi)
>>>>>>>>>>>>
>>>>>>>>>>>> The implementation that I envisioned would be as a "pre-process"
>>>>>>>>>>>> [3] step just
>>>>>>>>>>>> after EA but before the constraint checks in
>>>>>>>>>>>> `adjust_scalar_replaceable_state`
>>>>>>>>>>>> [2]. If we agree that the overall Scalar Replacement
>>>>>>>>>>>> implementation goes through
>>>>>>>>>>>> the following major phases:
>>>>>>>>>>>>
>>>>>>>>>>>>        1. Identify the Escape Status of objects.
>>>>>>>>>>>>        2. Adjust object Escape and/or Scalar Replacement status
>>>>>>>>>>>> based on a set of constraints.
>>>>>>>>>>>>        3. Make call to Split_unique_types [4].
>>>>>>>>>>>>        4 Iterate over object and array allocations.
>>>>>>>>>>>>            4.1 Check if allocation can be eliminated.
>>>>>>>>>>>>            4.2 Perform scalar replacement. Replace uses of object
>>>>>>>>>>>> in Safepoints.
>>>>>>>>>>>>            4.3 Process users of CheckCastPP other than Safepoint:
>>>>>>>>>>>> AddP, ArrayCopy and CastP2X.
>>>>>>>>>>>>
>>>>>>>>>>>> The transformation that I am proposing would change the overall
>>>>>>>>>>>> flow to look
>>>>>>>>>>>> like this:
>>>>>>>>>>>>
>>>>>>>>>>>>        1. Identify the Escape Status of objects.
>>>>>>>>>>>>        2. ----> New: "Split phi functions" <----
>>>>>>>>>>>>        2. Adjust object Escape and/or Scalar Replacement status
>>>>>>>>>>>> based on a set of constraints.
>>>>>>>>>>>>        3. Make call to Split_unique_types [14].
>>>>>>>>>>>>        4 Iterate over object and array allocations.
>>>>>>>>>>>>            4.1 ----> Moved to split_phi: "Check if allocation can
>>>>>>>>>>>> be eliminated" <----
>>>>>>>>>>>>            4.2 Perform scalar replacement. Replace uses of object
>>>>>>>>>>>> in Safepoints.
>>>>>>>>>>>>            4.3 Process users of CheckCastPP other than Safepoint:
>>>>>>>>>>>> AddP, ArrayCopy and CastP2X.
>>>>>>>>>>>>
>>>>>>>>>>>> Please let me know what you think and thank you for taking the
>>>>>>>>>>>> time to review
>>>>>>>>>>>> this!
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> Regards,
>>>>>>>>>>>> Cesar
>>>>>>>>>>>>
>>>>>>>>>>>> Notes:
>>>>>>>>>>>>
>>>>>>>>>>>>        [1] I am not sure yet how this approach will play with the
>>>>>>>>>>>> case of a merge
>>>>>>>>>>>>            with NULL.
>>>>>>>>>>>>        [2]
>>>>>>>>>>>> https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Furldefense.com%2Fv3%2F__https%3A%2F%2Fnam06.safelinks.protection.outlook.com%2F%3Furl%3Dhttps*3A*2F*2Fgithub.com*2Fopenjdk*2Fjdk*2Fblob*2F2f71a6b39ed6bb869b4eb3e81bc1d87f4b3328ff*2Fsrc*2Fhotspot*2Fshare*2Fopto*2Fescape.cpp*23L1809%26amp%3Bdata%3D04*7C01*7CDivino.Cesar*40microsoft.com*7Ce13b0a3de30e43d7ac4408d9f22b75c5*7C72f988bf86f141af91ab2d7cd011db47*7C1*7C0*7C637807090747649306*7CUnknown*7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0*3D*7C3000%26amp%3Bsdata%3DWruWqIgGVIzIFIG0gD0*2FEIQm40euLx6FZMexotJVrlE*3D%26amp%3Breserved%3D0__%3BJSUlJSUlJSUlJSUlJSUlJSUlJSUlJSUlJSUl!!ACWV5N9M2RV99hQ!aWncAwAPjDG2SCD4yFD_Rj6ecIB4iHjD2gepnv2TCHRO5RJznILvC8eoFUe4wgtAURqRWDc%24&data=04%7C01%7CDivino.Cesar%40microsoft.com%7Cd6152056b06744f7359e08da10e33a44%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637840865379134331%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=2uggNczR4bPxDv15gREOFA65mta6qrilwlZxblgQcYc%3D&reserved=0 
>>>
>>>
>>> <https://urldefense.com/v3/__https://nam06.safelinks.protection.outlook.com/?url=https*3A*2F*2Furldefense.com*2Fv3*2F__https*3A*2F*2Fnam06.safelinks.protection.outlook.com*2F*3Furl*3Dhttps*3A*2F*2Fgithub.com*2Fopenjdk*2Fjdk*2Fblob*2F2f71a6b39ed6bb869b4eb3e81bc1d87f4b3328ff*2Fsrc*2Fhotspot*2Fshare*2Fopto*2Fescape.cpp*23L1809*26amp*3Bdata*3D04*7C01*7CDivino.Cesar*40microsoft.com*7Ce13b0a3de30e43d7ac4408d9f22b75c5*7C72f988bf86f141af91ab2d7cd011db47*7C1*7C0*7C637807090747649306*7CUnknown*7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0*3D*7C3000*26amp*3Bsdata*3DWruWqIgGVIzIFIG0gD0*2FEIQm40euLx6FZMexotJVrlE*3D*26amp*3Breserved*3D0__*3BJSUlJSUlJSUlJSUlJSUlJSUlJSUlJSUlJSUl!!ACWV5N9M2RV99hQ!aWncAwAPjDG2SCD4yFD_Rj6ecIB4iHjD2gepnv2TCHRO5RJznILvC8eoFUe4wgtAURqRWDc*24&data=04*7C01*7CDivino.Cesar*40microsoft.com*7Cd6152056b06744f7359e08da10e33a44*7C72f988bf86f141af91ab2d7cd011db47*7C1*7C0*7C637840865379134331*7CUnknown*7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0*3D*7C3000&sdata=2uggNczR4bPxDv15gREOFA65mta6qrilwlZxblgQcYc*3D&reserved=0__;JSUlJSUlJSUlJSUqKioqKioqKioqKioqJSUlKioqKioqKioqKioqJSUlKiolJSUlJSUlJSUlJSUlJSUlJSU!!ACWV5N9M2RV99hQ!ZJvmUIbT0x_YJJPA3ap6R-qkOaEsH3YOGwu47flogbZamqV6nWVO2Kfx8uUYnVSj83WW6w$> 
>>>
>>>> <https://nam06.safelinks.protection.outlook.com/?url=https%3A%2F%2Furldefense.com%2Fv3%2F__https%3A%2F%2Fnam06.safelinks.protection.outlook.com%2F%3Furl%3Dhttps*3A*2F*2Furldefense.com*2Fv3*2F__https*3A*2F*2Fnam06.safelinks.protection.outlook.com*2F*3Furl*3Dhttps*3A*2F*2Fgithub.com*2Fopenjdk*2Fjdk*2Fblob*2F2f71a6b39ed6bb869b4eb3e81bc1d87f4b3328ff*2Fsrc*2Fhotspot*2Fshare*2Fopto*2Fescape.cpp*23L1809*26amp*3Bdata*3D04*7C01*7CDivino.Cesar*40microsoft.com*7Ce13b0a3de30e43d7ac4408d9f22b75c5*7C72f988bf86f141af91ab2d7cd011db47*7C1*7C0*7C637807090747649306*7CUnknown*7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0*3D*7C3000*26amp*3Bsdata*3DWruWqIgGVIzIFIG0gD0*2FEIQm40euLx6FZMexotJVrlE*3D*26amp*3Breserved*3D0__*3BJSUlJSUlJSUlJSUlJSUlJSUlJSUlJSUlJSUl!!ACWV5N9M2RV99hQ!aWncAwAPjDG2SCD4yFD_Rj6ecIB4iHjD2gepnv2TCHRO5RJznILvC8eoFUe4wgtAURqRWDc*24%26amp%3Bdata%3D04*7C01*7Cdivino.cesar*40microsoft.com*7C8c1737b992e847651e8d08d9f62d649b*7C72f988bf86f141af91ab2d7cd011db47*7C1*7C0*7C637811497098895122*7CUnknown*7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0*3D*7C3000%26amp%3Bsdata%3D8hLm9BcYVRF810gFqf2*2B*2Fd28jzqU2k7htD*2FDLqR9vAM*3D%26amp%3Breserved%3D0__%3BJSUlJSUlJSUlJSUqKioqKioqKioqKioqJSUlKioqKioqKioqKioqJSUlKiolJSUlJSUlJSUlJSUlJSUlJSUlJSU!!ACWV5N9M2RV99hQ!c3mFGaPH2PWpbeiHR44WrjfJKF0Ymg6aPQ8EOEMK0t5iYjdL4XwgsEvifrlDVrer2pCrdQ%24&data=04%7C01%7CDivino.Cesar%40microsoft.com%7Cd6152056b06744f7359e08da10e33a44%7C72f988bf86f141af91ab2d7cd011db47%7C1%7C0%7C637840865379134331%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C3000&sdata=MX%2BMB2A%2FyA1sLbSbXPp0uIsckxM5OOc%2Fg%2BqPAMwSgAw%3D&reserved=0 
>>>
>>>
>>> <https://urldefense.com/v3/__https://nam06.safelinks.protection.outlook.com/?url=https*3A*2F*2Furldefense.com*2Fv3*2F__https*3A*2F*2Fnam06.safelinks.protection.outlook.com*2F*3Furl*3Dhttps*3A*2F*2Furldefense.com*2Fv3*2F__https*3A*2F*2Fnam06.safelinks.protection.outlook.com*2F*3Furl*3Dhttps*3A*2F*2Fgithub.com*2Fopenjdk*2Fjdk*2Fblob*2F2f71a6b39ed6bb869b4eb3e81bc1d87f4b3328ff*2Fsrc*2Fhotspot*2Fshare*2Fopto*2Fescape.cpp*23L1809*26amp*3Bdata*3D04*7C01*7CDivino.Cesar*40microsoft.com*7Ce13b0a3de30e43d7ac4408d9f22b75c5*7C72f988bf86f141af91ab2d7cd011db47*7C1*7C0*7C637807090747649306*7CUnknown*7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0*3D*7C3000*26amp*3Bsdata*3DWruWqIgGVIzIFIG0gD0*2FEIQm40euLx6FZMexotJVrlE*3D*26amp*3Breserved*3D0__*3BJSUlJSUlJSUlJSUlJSUlJSUlJSUlJSUlJSUl!!ACWV5N9M2RV99hQ!aWncAwAPjDG2SCD4yFD_Rj6ecIB4iHjD2gepnv2TCHRO5RJznILvC8eoFUe4wgtAURqRWDc*24*26amp*3Bdata*3D04*7C01*7Cdivino.cesar*40microsoft.com*7C8c1737b992e847651e8d08d9f62d649b*7C72f988bf86f141af91ab2d7cd011db47*7C1*7C0*7C637811497098895122*7CUnknown*7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0*3D*7C3000*26amp*3Bsdata*3D8hLm9BcYVRF810gFqf2*2B*2Fd28jzqU2k7htD*2FDLqR9vAM*3D*26amp*3Breserved*3D0__*3BJSUlJSUlJSUlJSUqKioqKioqKioqKioqJSUlKioqKioqKioqKioqJSUlKiolJSUlJSUlJSUlJSUlJSUlJSUlJSU!!ACWV5N9M2RV99hQ!c3mFGaPH2PWpbeiHR44WrjfJKF0Ymg6aPQ8EOEMK0t5iYjdL4XwgsEvifrlDVrer2pCrdQ*24&data=04*7C01*7CDivino.Cesar*40microsoft.com*7Cd6152056b06744f7359e08da10e33a44*7C72f988bf86f141af91ab2d7cd011db47*7C1*7C0*7C637840865379134331*7CUnknown*7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0*3D*7C3000&sdata=MX*2BMB2A*2FyA1sLbSbXPp0uIsckxM5OOc*2Fg*2BqPAMwSgAw*3D&reserved=0__;JSUlJSUlJSUlJSUqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqJSUlKioqKioqKioqKioqJSUlKioqKiUlJSUlJSUlJSUlJSUlJSUlJSUlJSU!!ACWV5N9M2RV99hQ!ZJvmUIbT0x_YJJPA3ap6R-qkOaEsH3YOGwu47flogbZamqV6nWVO2Kfx8uUYnVQOQ4zHVg$>> 
>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>        [3] Another option would be to "patch" the current
>>>>>>>>>>>> implementation to be able
>>>>>>>>>>>>            to handle the merges. I am not certain that the "patch"
>>>>>>>>>>>> approach would be
>>>>>>>>>>>>            better, however, the "pre-process" approach is certainly
>>>>>>>>>>>> much easier to test
>>>>>>>>>>>>            and more readable.
>>>>>>>>>>>>
>>>>>>>>>>>>        [4] I cannot say I understand 100% the effects of executing
>>>>>>>>>>>>            split_unique_types(). Would the transformation that I am
>>>>>>>>>>>> proposing need to
>>>>>>>>>>>>            be after the call to split_unique_types?
>>>>
>>>


More information about the hotspot-compiler-dev mailing list