Handle specialisation of recursive function that does not always preserve the arguments (MPR#7291) by chambart · Pull Request #780 · ocaml/ocaml

chambart · 2016-08-25T14:02:01Z

This is a followup to #731

The other solution to fixing MPR#7291 is to drop the requirement from the parameter invariance analysis from being an over-approximation.

This is done by some rewriting of specialised functions before freshening. Every recursive calls that are not obviously preserving the arguments that will be specialised call the original function instead of a recursive call to the specialised version.

This is a bit more complex than originally expected to be able to multiply recursive functions like:

type a =
  | A of b
  | End

and b =
  | B of a

let rec iter_a f a =
  match a with
  | A b ->
    f ();
    iter_b f b
  | End ->
    ()

and iter_b f b =
  match b with
  | B a ->
    f ();
    iter_a f a


let count a =
  let r = ref 0 in
  let increm () = incr r in
  (iter_a [@specialised]) increm a;
  !r

This change is not the most efficient possible: There are 3 added rewritings of the functions.
Some could be eliminated. This is only a first proposal.

mshinwell · 2016-08-26T08:08:36Z

Hmm, I think this might be plausible for 4.04 actually. I'm going to tidy it up a bit.

lpw25 · 2016-08-26T08:37:17Z

I haven't read the patch properly yet, but doesn't this risk adding closure allocations when specializing a function. We're currently careful to only request specialisation when a set of closures has no free variables, whilst this change seems to add the original set of closures as a free variable of the new set.

mshinwell · 2016-08-26T10:36:34Z

@chambart Please see chambart#33 -- I suggest merging that and then re-reading. I haven't got time to test this before going away; could you write some tests (ideally in the testsuite) including a distillation of the original problem from #731? If that all works, I think we should merge this in 4.04 instead of my original hack. I think it would be a mistake not to fix this problem in 4.04.

mshinwell · 2016-08-26T11:23:46Z

@lpw25 Hmm, I'm not sure it will. Given the current behaviour of Invariant_params, is it not the case that the only recursive calls we are going to repoint to the non-specialised version of the function (via these new free variables) are in subfunctions? I think it is. Those subfunctions are presumably referencing the existing function in their closure in any case, so I'm not sure more allocations are added.

lpw25 · 2016-08-26T13:37:42Z

I don't think it matters if the calls are in subfunctions. In order for the old set of closures to be available when we create those subfunctions it is going to need to be a free variable of the new set of closures.

lpw25 · 2016-08-26T13:59:26Z

Actually, I think this is probably fine. The new free variables are necessarily pointing to closures which themselves have no free variables. Even though flambda doesn't express it, such closures will be statically allocated and so the free variables will disappear, and I think this means there will be no closure allocation.

This inability of flambda to understand that closures with no free variables will always be statically allocated -- even when other scoping issues prevent them from being lifted to symbols -- is quite annoying. At some point it will probably need to be addressed.

There are still some downsides to this approach. For instance, the existence of free variables will prevent the new set of closures from being further specialised.

Make Inlining_transform.inline_by_copying_function_declaration robust to Invariant_params being an overaproximation.

chambart · 2016-08-31T15:12:28Z

I tried to make a self contained test exposing the problem, but there are too many interactions to make a robust one. This clearly ask for something to help writing intricate inlining test cases. It could be done either with an inline attribute telling during which inlining phase to force the inline of a function (here specializing the call site before inlining the calls inside the body of the function). Or a concrete syntax for flambda could do (but would be awful to write with all the attributes everywhere...).

chambart · 2016-08-31T15:22:09Z

You are right @lpw25 this is certainly inelegant (at least) to not be able to consider that as closed function even if we certainly know that it will be the case. I am still unsure what would be the right approach with the less downsides on that point.

@damiendoligez This is quite an important bugfix for 4.04 do you approve in principle for something like this at that point in the release ?

mshinwell · 2016-09-19T00:13:46Z

@damiendoligez Ping

damiendoligez · 2016-09-29T16:48:28Z

Since it fixes a rather important bug and it only impacts flambda, I have no problem merging this into 4.04, but you guys need to choose between this one and #731.

damiendoligez · 2016-10-05T14:49:25Z

@mshinwell @chambart @lpw25
Have you decided between this one and #731 ? Is this reviewed and good to go?

lpw25 · 2016-10-05T15:41:46Z

I think we are waiting for @chambart to return from vacation before making a decision

mshinwell · 2016-10-06T06:23:40Z

@damiendoligez Yeah, I'm sorry, we all need to round up on this one again. I think we need to wait until next Monday.

chambart · 2016-10-06T14:51:41Z

Let's say at least tuesday, I will be too wasted on monday to give a sensible answer.

damiendoligez · 2016-10-07T11:18:35Z

No problem.

mshinwell · 2016-10-13T12:10:36Z

@chambart Leo and I discussed this again and we think merging this one is probably best, since it seems more principled and possibly safer. If you are in agreement please go ahead.

mshinwell · 2016-10-20T10:16:57Z

@chambart : Ping

chambart · 2016-10-24T22:25:40Z

This is not completely certain, but https://forge.ocamlcore.org/tracker/index.php?func=detail&aid=1674&group_id=54&atid=291 is probably an instance of this bug.

mshinwell · 2016-10-25T08:29:13Z

We've agreed this is the right way to go, and will merge now.

chambart · 2016-10-25T08:46:40Z

This branch was based on trunk, so this was manually pushed to 4.04

…ins_effects Backport of pr770

* Implement "destroyed" on the CFG representation. * rebase * ocamlformat

* Rename `.gitattribute` to `.gitattributes` * Treat .eml as .html Co-authored-by: Cuihtlauac ALVARADO <cuihtmlauac@tarides.com>

chambart added the work-in-progress label Aug 25, 2016

chambart force-pushed the pr7291_bis branch from 28d74d4 to f832428 Compare August 31, 2016 15:06

chambart and others added 3 commits August 31, 2016 17:06

Add Identifiable.Map.transpose_key_and_data_set

5a318fe

Fix PR#7291

1fdf2d9

Make Inlining_transform.inline_by_copying_function_declaration robust to Invariant_params being an overaproximation.

Refactoring etc

78f3399

chambart force-pushed the pr7291_bis branch from f832428 to 78f3399 Compare August 31, 2016 15:06

chambart added bug and removed work-in-progress labels Aug 31, 2016

chambart added this to the 4.04 milestone Aug 31, 2016

Update Changes

5125863

mshinwell mentioned this pull request Oct 20, 2016

Fix parameter invariance analysis (MPR#7291) #731

Closed

chambart changed the base branch from trunk to 4.04 October 25, 2016 08:30

chambart changed the base branch from 4.04 to trunk October 25, 2016 08:31

mshinwell added the approved label Oct 25, 2016

chambart closed this Oct 25, 2016

vicuna mentioned this pull request Mar 14, 2019

fatal error during flambda pass #7291

Closed

quartz55 pushed a commit to quartz55/ocaml that referenced this pull request Feb 1, 2022

Merge pull request ocaml#780 from ocaml-multicore/pr_770_for_412_doma…

01b49c0

…ins_effects Backport of pr770

stedolan pushed a commit to stedolan/ocaml that referenced this pull request Sep 21, 2022

IRC: re-implement "destroyed" on the CFG representation (ocaml#780)

a3ada24

* Implement "destroyed" on the CFG representation. * rebase * ocamlformat

EmileTrotignon pushed a commit to EmileTrotignon/ocaml that referenced this pull request Jan 12, 2024

Rename .gitattribute to .gitattributes (ocaml#780)

3b158ce

* Rename `.gitattribute` to `.gitattributes` * Treat .eml as .html Co-authored-by: Cuihtlauac ALVARADO <cuihtmlauac@tarides.com>

Conversation

chambart commented Aug 25, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

mshinwell commented Aug 26, 2016

Uh oh!

lpw25 commented Aug 26, 2016

Uh oh!

mshinwell commented Aug 26, 2016

Uh oh!

mshinwell commented Aug 26, 2016

Uh oh!

lpw25 commented Aug 26, 2016

Uh oh!

lpw25 commented Aug 26, 2016

Uh oh!

chambart commented Aug 31, 2016

Uh oh!

chambart commented Aug 31, 2016

Uh oh!

mshinwell commented Sep 19, 2016

Uh oh!

damiendoligez commented Sep 29, 2016

Uh oh!

damiendoligez commented Oct 5, 2016

Uh oh!

lpw25 commented Oct 5, 2016

Uh oh!

mshinwell commented Oct 6, 2016

Uh oh!

chambart commented Oct 6, 2016

Uh oh!

damiendoligez commented Oct 7, 2016

Uh oh!

mshinwell commented Oct 13, 2016

Uh oh!

mshinwell commented Oct 20, 2016

Uh oh!

chambart commented Oct 24, 2016

Uh oh!

mshinwell commented Oct 25, 2016

Uh oh!

chambart commented Oct 25, 2016

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

chambart commented Aug 25, 2016 •

edited

Loading