[External] : Re: RFC : Approach to handle Allocation Merges in C2 Scalar Replacement
Vladimir Kozlov
vladimir.kozlov at oracle.com
Wed Mar 30 21:32:28 UTC 2022
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