Make Selectgen treat region boundaries more precisely by stedolan · Pull Request #1131 · oxcaml/oxcaml

stedolan · 2023-02-20T11:36:27Z

Currently, Selectgen treats region boundaries fairly loosely when inlining is involved, allowing regions to extend beyond their specified scope. For instance, consider these functions:

let[@inline] f use g x =
  let local_ r = ref 42 in
  if x then (use r; g 42)
  else (Some 42)

let h use g x =
  let local_ r = ref 42 in
  use r;
  let z = f use g x [@nontail] in
  use r;
  z

The use function is just to prevent the refs being optimised away, and isn't otherwise relevant to the example. The function h is currently compiled to (with details removed):

h_reg := beginregion;
f_reg := beginregion;
if x then
  v := call g
else
  v := Some 42
endif;
endregion f_reg;
endregion h_reg;
return v

Note that both regions are ended after the inlined body of f. (Actually, the two endregions can be coalesced to a single instruction, but in principle they're ended here). In particular, the region of f remains on the stack when f tailcalls g.

This was a known issue in Selectgen, which resulted in a minor loss of efficiency (possibly offset by improved code size) as some values stayed on the local stack in non-tail position for longer than they should. However, it becomes a soundness issue when combined with various upcoming features and optimisations that rely on precise region boundaries.

So, this patch compiles h as follows instead:

h_reg := beginregion;
f_reg := beginregion;
if x then
  endregion f_reg;
  v := call g;
  endregion h_reg
  return v
else
  endregion f_reg;
  endregion h_reg;
  v := Some 42
  return v
endif

where in particular, the region f_reg is ended before the inlined body of f tailcalls g.

This patch also lifts the assumption in Selectgen that an expression is in tail position of at most one region, which happens to be true at the moment but won't be for long.

The main change is a change to the semantics of Selectgen.emit_expr and Selectgen.emit_expr_tail:

Before:

emit_expr: emit an expression, without closing any regions (ignoring Ctail, etc.)
emit_expr_tail: emit an expression in tail position, closing the current region (of which there can be at most one)

After:

emit_expr_aux: emit an expression, possibly closing some regions if instructed to by Ctail, etc.
emit_expr: emit an expression with emit_expr_aux, verifying that no regions were closed (e.g. for nontail expressions)
emit_expr_tail: emit an expression in tail position, closing all current regions (of which there can be many)

Send(... Alloc_local...) should cause set_region_use true

stedolan · 2023-02-20T15:18:35Z

The Flambda1 build failures turn out to be an existing bug in Flambda1's region handling, uncovered by the extra checks in this patch. The logic for detecting whether a region is used was not correctly handling Send in tail position. (The fix is trivial and I'm fairly sure the bug could not lead to miscompilations)

lpw25

Looks correct although a few places could probably be made a little clearer.

ocaml/testsuite/tests/typing-local/regions.ml

backend/selectgen.ml

stedolan · 2023-03-01T16:09:37Z

I've pushed a new version after refactoring some list manipulation, but the output should be the same.

lpw25

I like the changes, but there are a couple of points that would still be worth improving.

backend/selectgen.ml

lpw25 · 2023-03-27T16:01:15Z

Happy to merge this now, but there is a CI failure that looks relevant.

stedolan · 2023-03-27T17:12:23Z

Happy to merge this now, but there is a CI failure that looks relevant.

Yeah, I need to reflect the changes to the copy of Selectgen in ocaml/. (Was waiting until review finished on the copy in backend/ first to avoid duplicating this work).

This reverts commit dffd25c.

Revert "Make Selectgen treat region boundaries more precisely (#1131)" This reverts commit dffd25c.

* Revert "Revert "Make Selectgen treat region boundaries more precisely" (#1283)" This reverts commit abd91a9. * Fix bad interaction between Cmm unboxing and locals Local regions should not count as "tail" for Cmm unboxing purposes.

1686928 flambda-backend: Restore Cmm unboxing behaviour inside regions (oxcaml#1285) cf9be42 flambda-backend: Fix all the no-naked-pointers problems (oxcaml#1282) 8fe089e flambda-backend: Unrevert oxcaml#1131 and fix a Cmm unboxing bug (oxcaml#1284) c4143c3 flambda-backend: Revert "Make Selectgen treat region boundaries more precisely" (oxcaml#1283) 2078dce flambda-backend: Add some -dtimings output for the typechecker (oxcaml#1245) 273a7f9 flambda-backend: Make Selectgen treat region boundaries more precisely (oxcaml#1131) 47610e6 flambda-backend: Bump magic numbers for 4.14.1-6 (oxcaml#1274) fd53d38 flambda-backend: Generate *.cms files for merlin (oxcaml#1232) 853f95f flambda-backend: Add tail_mod_const to builtin_attrs (oxcaml#1265) f9ef051 flambda-backend: Fix issue caused by effects of gadt expansion in mode cross check (oxcaml#1263) e9ffcf8 flambda-backend: Fix dependencies for regenerating Flambda2 parser, tests (oxcaml#1255) 6f1cd1f flambda-backend: Restore a lost location, needed for merlin (oxcaml#1242) 009332b flambda-backend: Fix merge from ocaml-jst git-subtree-dir: ocaml git-subtree-split: 1686928

a7d005a flambda-backend: Lazy deserialization of cmi files (oxcaml#1322) aa83fa3 flambda-backend: Reinstate previous API for Env.lookup_value (oxcaml#1323) e4007a4 flambda-backend: Lazy substitution into value_declaration (oxcaml#1320) 634b607 flambda-backend: Merge Types.* and Subst.Lazy.* types (oxcaml#1312) cf82708 flambda-backend: Bump magic numbers for 4.14.1-7 (oxcaml#1317) 6470400 flambda-backend: zero_alloc attribute payload "assert all" and "ignore" (oxcaml#1296) bba5248 flambda-backend: Teach `ocamldep` about all the language extensions (oxcaml#1303) 33e97b0 flambda-backend: Change Includemod to work on lazy modtypes (oxcaml#1228) 16e5002 flambda-backend: zero_alloc new warning for unchecked functions (oxcaml#1302) 36b4626 flambda-backend: Attribute [@@@zero_alloc check] to turn the check on (oxcaml#1294) 3b524c6 flambda-backend: Cmm.value_kind cleanup (oxcaml#1091) ec99505 flambda-backend: Fix failure of `check_all_arches` on RISCV (oxcaml#1300) 450bc58 flambda-backend: Backend changes for multiple returns (oxcaml#1268) 84a7a26 flambda-backend: Static check for zero_alloc: ignore allocation that lead to exceptional return (oxcaml#1157) 1723728 flambda-backend: Re-enable parallel build of the runtime (oxcaml#1287) 26ea7f3 flambda-backend: Fix closure marshalling when not in NNP mode (oxcaml#1286) 9b91f2e flambda-backend: Reduce number of caml_apply functions taking/returning "I" and "V" (oxcaml#1272) 1686928 flambda-backend: Restore Cmm unboxing behaviour inside regions (oxcaml#1285) cf9be42 flambda-backend: Fix all the no-naked-pointers problems (oxcaml#1282) 8fe089e flambda-backend: Unrevert oxcaml#1131 and fix a Cmm unboxing bug (oxcaml#1284) c4143c3 flambda-backend: Revert "Make Selectgen treat region boundaries more precisely" (oxcaml#1283) 2078dce flambda-backend: Add some -dtimings output for the typechecker (oxcaml#1245) 273a7f9 flambda-backend: Make Selectgen treat region boundaries more precisely (oxcaml#1131) 47610e6 flambda-backend: Bump magic numbers for 4.14.1-6 (oxcaml#1274) fd53d38 flambda-backend: Generate *.cms files for merlin (oxcaml#1232) 853f95f flambda-backend: Add tail_mod_const to builtin_attrs (oxcaml#1265) f9ef051 flambda-backend: Fix issue caused by effects of gadt expansion in mode cross check (oxcaml#1263) e9ffcf8 flambda-backend: Fix dependencies for regenerating Flambda2 parser, tests (oxcaml#1255) 6f1cd1f flambda-backend: Restore a lost location, needed for merlin (oxcaml#1242) 009332b flambda-backend: Fix merge from ocaml-jst git-subtree-dir: ocaml git-subtree-split: a7d005a

Make Selectgen treat region boundaries more precisely

a06984d

stedolan requested review from gretay-js and xclerc as code owners February 20, 2023 11:36

mshinwell added the backend label Feb 20, 2023

stedolan added 2 commits February 20, 2023 13:36

Support region-crossing Cexit in Selectgen

32e5628

Fix Flambda1 region-handling bug in Send

0d2765a

Send(... Alloc_local...) should cause set_region_use true

stedolan requested a review from mshinwell as a code owner February 20, 2023 15:17

lpw25 approved these changes Feb 24, 2023

View reviewed changes

Refactoring after review

b805981

lpw25 reviewed Mar 1, 2023

View reviewed changes

backend/selectgen.ml Outdated Show resolved Hide resolved

backend/selectgen.ml Show resolved Hide resolved

riaqn mentioned this pull request Mar 8, 2023

add [%exclave] support ocaml-flambda/ocaml-jst#51

Merged

more review fixes

15558da

Reflect Selectgen changes to ocaml/asmcomp

507f2ad

lpw25 merged commit dffd25c into oxcaml:main Mar 30, 2023

mshinwell added a commit that referenced this pull request Apr 2, 2023

Revert "Make Selectgen treat region boundaries more precisely (#1131)"

c93f578

This reverts commit dffd25c.

mshinwell mentioned this pull request Apr 2, 2023

Revert "Make Selectgen treat region boundaries more precisely" #1283

Merged

mshinwell added a commit that referenced this pull request Apr 2, 2023

Revert "Make Selectgen treat region boundaries more precisely" (#1283)

abd91a9

Revert "Make Selectgen treat region boundaries more precisely (#1131)" This reverts commit dffd25c.

stedolan mentioned this pull request Apr 3, 2023

Unrevert #1131 and fix a Cmm unboxing bug #1284

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Make Selectgen treat region boundaries more precisely#1131

Make Selectgen treat region boundaries more precisely#1131
lpw25 merged 6 commits intooxcaml:mainfrom
stedolan:selectgen-locals-fix

stedolan commented Feb 20, 2023 •

edited

Loading

Uh oh!

stedolan commented Feb 20, 2023

Uh oh!

lpw25 left a comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

stedolan commented Mar 1, 2023

Uh oh!

lpw25 left a comment

Uh oh!

Uh oh!

Uh oh!

lpw25 commented Mar 27, 2023

Uh oh!

stedolan commented Mar 27, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Conversation

stedolan commented Feb 20, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

stedolan commented Feb 20, 2023

Uh oh!

lpw25 left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

stedolan commented Mar 1, 2023

Uh oh!

lpw25 left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

lpw25 commented Mar 27, 2023

Uh oh!

stedolan commented Mar 27, 2023

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

stedolan commented Feb 20, 2023 •

edited

Loading