Skip to content

(low priority) Mode crossing in uniqueness analysis#2377

Draft
riaqn wants to merge 1 commit intooxcaml:mainfrom
riaqn:mode_crossing_unique_analysis
Draft

(low priority) Mode crossing in uniqueness analysis#2377
riaqn wants to merge 1 commit intooxcaml:mainfrom
riaqn:mode_crossing_unique_analysis

Conversation

@riaqn
Copy link
Copy Markdown
Contributor

@riaqn riaqn commented Mar 19, 2024

This PR tries to add mode crossing to uniqueness analysis.

(won't be working on this for a while; so create a PR as a reminder)

Consider the example:

let foo () =
  let r = {x =3; y = 5} in
  ignore (unique_id r.x);
  ignore (unique_id r)

UA would sequence the usage u0 of r.x and the usage u1 of r, which will force both to be shared, many.

  • The real sequencing will happen node-wise: on the r node, we will sequence empty with u1 = maybe_unique _, which is fine. On the r.x node, we will sequence u0 = maybe_unique _ with maybe_unique _, where the second one is inherited from u1.

Note that the unique_use in u0 would be mode-crossed and not affected by the forcing. The unique_use in u1 cannot cross-modes and will trigger error.

The solution (unfinished yet in this PR) is to attach the uniqueness/linearity upper bounds to each Borrowed/Maybe_shared/Shared/Maybe_unique usage, and when we seq or par two usages, we will take the meet of the upper bounds in those two usages, and use that to mode cross both unique_use.

  • In UsageTree.seq, the upper bounds of parent node should not propagate to child node.
  • Where to get the upper_bounds? Each typedtree node has texp_type which can be checked. Is this too expensive?

@riaqn riaqn changed the title (DRAFT) Mode crossing in uniqueness analysis (low priority) Mode crossing in uniqueness analysis Mar 19, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants