Extended static exceptions: preparation for local functions by chambart · Pull Request #98 · ocaml/ocaml

chambart · 2014-09-04T15:49:51Z

The Cmm and Mach intermediate representations can't express a lot of control flow without going through functions or exceptions. This patch series propose to extend the static exception mechanism.

The proposed features are:

allowing (mutually-)recursive static exceptions:
( this is pseudo code, the patch contains no change before the cmm passes )

let fact x =
  static_try
    exit 0 (x, 1)
  with 0 (x, acc) ->
    if x = 0
    then acc
    else exit 0 (x-1, acc * x)

indirect exit construction and static exception variables

let fact x =
  static_try
    exit 0 (x, 1) 0
  with 0 (x, acc) k ->
    if x = 0
    then acc
    else indirect_exit k (x-1, acc * x) k

This will allow to provide a cheap encoding of local functions: non-escaping tail-called functions.

Notes: the original loop constructions are removed from cmm and mach, and there is a cleaner implementation for allowing static exception to jump out of try/with. A few examples are provided in testsuite/tests/asmcomp/

The patch has been tested on amd64 and i386 on linux and lightly tested on arm(v7) and arm64 in qemu linux.

… in Exit_ind

…oadgen, linearize

chambart · 2014-09-23T09:39:09Z

This batch removes indirect jumps, abstract the label type and fix a problem introduced in simplif

chambart · 2014-10-03T14:45:27Z

@xavierleroy, @alainfrisch, is there still anything blocking ?

gasche · 2014-10-08T07:07:59Z

I tried to have a look at the patchset, and here are some more comments about how we could get either of those two to actual do a code review.

First and foremost, I'm not sure there is a clear specification of the whole change somewhere. Your last update gives a detailed spec of a part of the proposal (good!), but I haven't found a coherent description of the whole change. My understanding is that Xavier would like to read something like that, and make sure he agrees with it, before going into any code details.

In particular, a question I asked myself when looking at the patches is the following: which ones of the intermediate representations have been converted to the label/jump vocabulary, and which still use the metaphor of static exceptions? Don't we want to convert all representations to label/jump (or to something even more descriptive of second-class local functions?). (Or would that maybe require a change in the bytecode format?)

If you had to describe, from scratch, the new IR constructs to a newcomer (eg. me), what would you write?

gasche · 2014-10-08T07:37:41Z

Separately, here are some comments about the patches themselves. I feel the change is already too large to review the complete diff in one go. The natural other solution is to review patch by patch, but your patch series is not clean enough to conveniently review -- there is a lot of back-and-forth and things in the first few patches get invalidated in later patches.

I think a nice patch order would be roughly as follows:

"metaphor changes": simple renamings (and type abstractions) to the intermediate language(s)
"new language features": extending the expressivity of the language by allowing new mode of uses, with the corresponding representation-correctness-related code
"use of new features": the optimizations and simplifications enabled by the new features

(Are the changes to emit.mlp still needed? In the discussion I understood there weren't anymore, but in the patch they are still present in a way that looks like the previous patches by Alain and you on jumping across try .. with. If this part is still necessary, maybe it could go first would be merge-able in isolation?)

chambart · 2014-10-17T15:11:43Z

The current semantics of 'labels/jumps' is:

(jump X arg) term => (jump X arg)
value (jump X arg) => (jump X arg)
(label (X param term) (value)) => value
(label (X param term) (jump X arg)) => (term [param := arg])

The extended semantics is the same, except

(label (X param term) (jump X arg)) => (label (X param term) (term [param := arg]))

and it allows multiply recursive labels:

(label [(X param term); (Y param' term') .. ] (jump X arg)) =>
   (label [(X param term); (Y param' term') .. ] (term [param := arg]))

The changes proposed for inclusion in this patch are the ones concerning
cmm, mach and linear. The changes to lambda and clambda are some kind of
overgrowth demonstration and are not necessary proposed in this state.
Without the modifications to lambda and simplify, the generated code is
identical to the current state of the compiler (except some dead Lpushtrap
removed in linearize). This part is considered to be a demonstration because
I am not convinced that this is the right place to do this optimisation
(this cannot be represented in bytecode and could benefit from inlining).
Yet if the core team thinks that this is valuable there I will bring that
to an acceptable state. This is already efficient and tested, but the
catch/exit => label/jump renaming has not been propagated.

The different things changed by this patch and proposed for inclusion:

The label type is abstracted.
Supress the 'loop' construction in the cmm and mach representations.
The loop construction is replaced by a label/jump in cmmgen (function cloop)
Cleaning spurious dead Lpoptrap:
Since the introduction of the 'match with exception' construction
Lbranch constructions can be followed by a dead Lpushtrap.
The Lbranch construction of the linear representation is changed to have
a new argument telling the difference in stack depth between the branch
and the next instruction. This results in the insertion of cfi directives
and applying the offset to 'stack_offset' in */emit.mlp. This is the only
changes to */emit.mlp and the major change to linearize. This change
removes the state in linearize so eliminate the need for Linearize.reset
(that was never called by the way...).
Those change were needed for the indirect versions, but are not strictly
needed now.
Handle a few more cases of Lbranch lbl followed by Llabel lbl in linearize
to always generate the same code as the original one for loops.
Rename catch/exit to label/jump: this affects the cmm, and mach representations.
The label construction takes a list of expressions as arguments instead of
only one.
The environments of Selectgen is extended to also contain the
'label to register' map.
This removes the catch_reg reference.
Liveness and spilling/reloading must do a fixpoint for the lbranch case.
There is a special case to avoid doing more than one round with the non
recursive use of labels. This avoid exponential blowup with the existing
code (unless it is a deeply nested for/while)

let-def · 2015-11-15T14:05:03Z

@chambart is this patch still relevant or is it obsoleted by the flambda branch?

gasche · 2016-11-12T03:22:35Z

Closing, as #524 was merged.

* Add multi-round CSE join, to allow sharing of complex expressions. The maximum number of rounds is controlled by the -flambda-cse-depth flag. * Fix for too eager propagation of Is_int/Get_tag

)

@inline

23a7f73 flambda-backend: Fix some Debuginfo.t scopes in the frontend (ocaml#248) 33a04a6 flambda-backend: Attempt to shrink the heap before calling the assembler (ocaml#429) 8a36a16 flambda-backend: Fix to allow stage 2 builds in Flambda 2 -Oclassic mode (ocaml#442) d828db6 flambda-backend: Rename -no-extensions flag to -disable-all-extensions (ocaml#425) 68c39d5 flambda-backend: Fix mistake with extension records (ocaml#423) 423f312 flambda-backend: Refactor -extension and -standard flags (ocaml#398) 585e023 flambda-backend: Improved simplification of array operations (ocaml#384) faec6b1 flambda-backend: Typos (ocaml#407) 8914940 flambda-backend: Ensure allocations are initialised, even dead ones (ocaml#405) 6b58001 flambda-backend: Move compiler flag -dcfg out of ocaml/ subdirectory (ocaml#400) 4fd57cf flambda-backend: Use ghost loc for extension to avoid expressions with overlapping locations (ocaml#399) 8d993c5 flambda-backend: Let's fix instead of reverting flambda_backend_args (ocaml#396) d29b133 flambda-backend: Revert "Move flambda-backend specific flags out of ocaml/ subdirectory (ocaml#382)" (ocaml#395) d0cda93 flambda-backend: Revert ocaml#373 (ocaml#393) 1c6eee1 flambda-backend: Fix "make check_all_arches" in ocaml/ subdirectory (ocaml#388) a7960dd flambda-backend: Move flambda-backend specific flags out of ocaml/ subdirectory (ocaml#382) bf7b1a8 flambda-backend: List and Array Comprehensions (ocaml#147) f2547de flambda-backend: Compile more stdlib files with -O3 (ocaml#380) 3620c58 flambda-backend: Four small inliner fixes (ocaml#379) 2d165d2 flambda-backend: Regenerate ocaml/configure 3838b56 flambda-backend: Bump Menhir to version 20210419 (ocaml#362) 43c14d6 flambda-backend: Re-enable -flambda2-join-points (ocaml#374) 5cd2520 flambda-backend: Disable inlining of recursive functions by default (ocaml#372) e98b277 flambda-backend: Import ocaml#10736 (stack limit increases) (ocaml#373) 82c8086 flambda-backend: Use hooks for type tree and parse tree (ocaml#363) 33bbc93 flambda-backend: Fix parsecmm.mly in ocaml subdirectory (ocaml#357) 9650034 flambda-backend: Right-to-left evaluation of arguments of String.get and friends (ocaml#354) f7d3775 flambda-backend: Revert "Magic numbers" (ocaml#360) 0bd2fa6 flambda-backend: Add [@inline ready] attribute and remove [@inline hint] (not [@inlined hint]) (ocaml#351) cee74af flambda-backend: Ensure that functions are evaluated after their arguments (ocaml#353) 954be59 flambda-backend: Bootstrap dd5c299 flambda-backend: Change prefix of all magic numbers to avoid clashes with upstream. c2b1355 flambda-backend: Fix wrong shift generation in Cmm_helpers (ocaml#347) 739243b flambda-backend: Add flambda_oclassic attribute (ocaml#348) dc9b7fd flambda-backend: Only speculate during inlining if argument types have useful information (ocaml#343) aa190ec flambda-backend: Backport fix from PR#10719 (ocaml#342) c53a574 flambda-backend: Reduce max inlining depths at -O2 and -O3 (ocaml#334) a2493dc flambda-backend: Tweak error messages in Compenv. 1c7b580 flambda-backend: Change Name_abstraction to use a parameterized type (ocaml#326) 07e0918 flambda-backend: Save cfg to file (ocaml#257) 9427a8d flambda-backend: Make inlining parameters more aggressive (ocaml#332) fe0610f flambda-backend: Do not cache young_limit in a processor register (upstream PR 9876) (ocaml#315) 56f28b8 flambda-backend: Fix an overflow bug in major GC work computation (ocaml#310) 8e43a49 flambda-backend: Cmm invariants (port upstream PR 1400) (ocaml#258) e901f16 flambda-backend: Add attributes effects and coeffects (#18) aaa1cdb flambda-backend: Expose Flambda 2 flags via OCAMLPARAM (ocaml#304) 62db54f flambda-backend: Fix freshening substitutions 57231d2 flambda-backend: Evaluate signature substitutions lazily (upstream PR 10599) (ocaml#280) a1a07de flambda-backend: Keep Sys.opaque_identity in Cmm and Mach (port upstream PR 9412) (ocaml#238) faaf149 flambda-backend: Rename Un_cps -> To_cmm (ocaml#261) ecb0201 flambda-backend: Add "-dcfg" flag to ocamlopt (ocaml#254) 32ec58a flambda-backend: Bypass Simplify (ocaml#162) bd4ce4a flambda-backend: Revert "Semaphore without probes: dummy notes (ocaml#142)" (ocaml#242) c98530f flambda-backend: Semaphore without probes: dummy notes (ocaml#142) c9b6a04 flambda-backend: Remove hack for .depend from runtime/dune (ocaml#170) 6e5d4cf flambda-backend: Build and install Semaphore (ocaml#183) 924eb60 flambda-backend: Special constructor for %sys_argv primitive (ocaml#166) 2ac6334 flambda-backend: Build ocamldoc (ocaml#157) c6f7267 flambda-backend: Add -mbranches-within-32B to major_gc.c compilation (where supported) a99fdee flambda-backend: Merge pull request ocaml#10195 from stedolan/mark-prefetching bd72dcb flambda-backend: Prefetching optimisations for sweeping (ocaml#9934) 27fed7e flambda-backend: Add missing index param for Obj.field (ocaml#145) cd48b2f flambda-backend: Fix camlinternalOO at -O3 with Flambda 2 (ocaml#132) 9d85430 flambda-backend: Fix testsuite execution (ocaml#125) ac964ca flambda-backend: Comment out `[@inlined]` annotation. (ocaml#136) ad4afce flambda-backend: Fix magic numbers (test suite) (ocaml#135) 9b033c7 flambda-backend: Disable the comparison of bytecode programs (`ocamltest`) (ocaml#128) e650abd flambda-backend: Import flambda2 changes (`Asmpackager`) (ocaml#127) 14dcc38 flambda-backend: Fix error with Record_unboxed (bug in block kind patch) (ocaml#119) 2d35761 flambda-backend: Resurrect [@inline never] annotations in camlinternalMod (ocaml#121) f5985ad flambda-backend: Magic numbers for cmx and cmxa files (ocaml#118) 0e8b9f0 flambda-backend: Extend conditions to include flambda2 (ocaml#115) 99870c8 flambda-backend: Fix Translobj assertions for Flambda 2 (ocaml#112) 5106317 flambda-backend: Minor fix for "lazy" compilation in Matching with Flambda 2 (ocaml#110) dba922b flambda-backend: Oclassic/O2/O3 etc (ocaml#104) f88af3e flambda-backend: Wire in the remaining Flambda 2 flags (ocaml#103) 678d647 flambda-backend: Wire in the Flambda 2 inlining flags (ocaml#100) 1a8febb flambda-backend: Formatting of help text for some Flambda 2 options (ocaml#101) 9ae1c7a flambda-backend: First set of command-line flags for Flambda 2 (ocaml#98) bc0bc5e flambda-backend: Add config variables flambda_backend, flambda2 and probes (ocaml#99) efb8304 flambda-backend: Build our own ocamlobjinfo from tools/objinfo/ at the root (ocaml#95) d2cfaca flambda-backend: Add mutability annotations to Pfield etc. (ocaml#88) 5532555 flambda-backend: Lambda block kinds (ocaml#86) 0c597ba flambda-backend: Revert VERSION, etc. back to 4.12.0 (mostly reverts 822d0a0 from upstream 4.12) (ocaml#93) 037c3d0 flambda-backend: Float blocks 7a9d190 flambda-backend: Allow --enable-middle-end=flambda2 etc (ocaml#89) 9057474 flambda-backend: Root scanning fixes for Flambda 2 (ocaml#87) 08e02a3 flambda-backend: Ensure that Lifthenelse has a boolean-valued condition (ocaml#63) 77214b7 flambda-backend: Obj changes for Flambda 2 (ocaml#71) ecfdd72 flambda-backend: Cherry-pick 9432cfdadb043a191b414a2caece3e4f9bbc68b7 (ocaml#84) d1a4396 flambda-backend: Add a `returns` field to `Cmm.Cextcall` (ocaml#74) 575dff5 flambda-backend: CMM traps (ocaml#72) 8a87272 flambda-backend: Remove Obj.set_tag and Obj.truncate (ocaml#73) d9017ae flambda-backend: Merge pull request ocaml#80 from mshinwell/fb-backport-pr10205 3a4824e flambda-backend: Backport PR#10205 from upstream: Avoid overwriting closures while initialising recursive modules f31890e flambda-backend: Install missing headers of ocaml/runtime/caml (ocaml#77) 83516f8 flambda-backend: Apply node created for probe should not be annotated as tailcall (ocaml#76) bc430cb flambda-backend: Add Clflags.is_flambda2 (ocaml#62) ed87247 flambda-backend: Preallocation of blocks in Translmod for value let rec w/ flambda2 (ocaml#59) a4b04d5 flambda-backend: inline never on Gc.create_alarm (ocaml#56) cef0bb6 flambda-backend: Config.flambda2 (ocaml#58) ff0e4f7 flambda-backend: Pun labelled arguments with type constraint in function applications (ocaml#53) d72c5fb flambda-backend: Remove Cmm.memory_chunk.Double_u (ocaml#42) 9d34d99 flambda-backend: Install missing artifacts 10146f2 flambda-backend: Add ocamlcfg (ocaml#34) 819d38a flambda-backend: Use OC_CFLAGS, OC_CPPFLAGS, and SHAREDLIB_CFLAGS for foreign libs (#30) f98b564 flambda-backend: Pass -function-sections iff supported. (#29) e0eef5e flambda-backend: Bootstrap (#11 part 2) 17374b4 flambda-backend: Add [@@Builtin] attribute to Primitives (#11 part 1) 85127ad flambda-backend: Add builtin, effects and coeffects fields to Cextcall (#12) b670bcf flambda-backend: Replace tuple with record in Cextcall (#10) db451b5 flambda-backend: Speedups in Asmlink (#8) 2fe489d flambda-backend: Cherry-pick upstream PR#10184 from upstream, dynlink invariant removal (rev 3dc3cd7 upstream) d364bfa flambda-backend: Local patch against upstream: enable function sections in the Dune build 886b800 flambda-backend: Local patch against upstream: remove Raw_spacetime_lib (does not build with -m32) 1a7db7c flambda-backend: Local patch against upstream: make dune ignore ocamldoc/ directory e411dd3 flambda-backend: Local patch against upstream: remove ocaml/testsuite/tests/tool-caml-tex/ 1016d03 flambda-backend: Local patch against upstream: remove ocaml/dune-project and ocaml/ocaml-variants.opam 93785e3 flambda-backend: To upstream: export-dynamic for otherlibs/dynlink/ via the natdynlinkops files (still needs .gitignore + way of generating these files) 63db8c1 flambda-backend: To upstream: stop using -O3 in otherlibs/Makefile.otherlibs.common eb2f1ed flambda-backend: To upstream: stop using -O3 for dynlink/ 6682f8d flambda-backend: To upstream: use flambda_o3 attribute instead of -O3 in the Makefile for systhreads/ de197df flambda-backend: To upstream: renamed ocamltest_unix.xxx files for dune bf3773d flambda-backend: To upstream: dune build fixes (depends on previous to-upstream patches) 6fbc80e flambda-backend: To upstream: refactor otherlibs/dynlink/, removing byte/ and native/ 71a03ef flambda-backend: To upstream: fix to Ocaml_modifiers in ocamltest 686d6e3 flambda-backend: To upstream: fix dependency problem with Instruct c311155 flambda-backend: To upstream: remove threadUnix 52e6e78 flambda-backend: To upstream: stabilise filenames used in backtraces: stdlib/, otherlibs/systhreads/, toplevel/toploop.ml 7d08e0e flambda-backend: To upstream: use flambda_o3 attribute in stdlib 403b82e flambda-backend: To upstream: flambda_o3 attribute support (includes bootstrap) 65032b1 flambda-backend: To upstream: use nolabels attribute instead of -nolabels for otherlibs/unix/ f533fad flambda-backend: To upstream: remove Compflags, add attributes, etc. 49fc1b5 flambda-backend: To upstream: Add attributes and bootstrap compiler a4b9e0d flambda-backend: Already upstreamed: stdlib capitalisation patch 4c1c259 flambda-backend: ocaml#9748 from xclerc/share-ev_defname (cherry-pick 3e937fc) 00027c4 flambda-backend: permanent/default-to-best-fit (cherry-pick 64240fd) 2561dd9 flambda-backend: permanent/reraise-by-default (cherry-pick 50e9490) c0aa4f4 flambda-backend: permanent/gc-tuning (cherry-pick e9d6d2f) git-subtree-dir: ocaml git-subtree-split: 23a7f73

chambart added 30 commits September 3, 2014 16:46

Allow jumping out of try/with

f3b05ad

Allow recursive static exceptions (like continuations)

56c77c6

Fix liveness static catch fixpoint initialisation

f2547cf

Fix liveness static catch fixpoint again.

8dfec08

Port linearize to 4.02

059a953

First step for allowing static exception variables

1efc5da

Propagate and use information about possibly reached static exception…

a478b9b

… in Exit_ind

replace Cloop construct by Ccatch

ed1f61b

Change cmm type for Ccatch handler list

df61009

Selection for multiply recursive ccatch

d07336d

Update cmm parser of the testsuite

e14d6a6

Add simple test for multiply recursive static catch

967b373

Change Mach type definition for multiply recursive Icatch

89e67a3

Start addapting for change in Mach (not complete).

a2826af

Update liveness.ml

5a46dee

Addapt Spill.reload, Spill.spill, Split.rename, Deadcode, Interf, Rel…

7b6596c

…oadgen, linearize

Fix linearize

1298f58

Missing case in Cmmgen.subst_boxed_number

9494794

Remove Cloop and Iloop constructions

084dac9

Fix testsuite cmm parser (no more Cloop)

15f740f

Update i386 emit.mlp

b8cb741

load_label don't go through the GOT on amd64

76b3bbc

Update arm emit.mlp

89a329a

update arm64 emit.mlp

6ed93df

refix arm64 emit

6d8dc48

Update powerpc emit.mlp

b6c4f35

Update sparc emit.mlp

5d87ca7

Iconst_sexn_addr result can go to the stack on amd64

154309f

Update Windows versions

26c4833

Comment Iconst_sexn_addr argument

94ca128

chambart added 9 commits September 22, 2014 14:45

Remove static exception variables from Lambda

6e7aac6

Abstract the static exception type in lambda and clambda

326e0e3

Abstract label in cmm

33c8de6

Abstract mach label

5955787

Update bytegen

866baba

Update printclambda

4fff75b

Error message in selectgen

742845e

Topological ordering of handlers for substitution

bf59abf

Update tests/asmcomp

0ed9540

damiendoligez added this to the 4.04-or-later milestone Jan 27, 2016

chambart mentioned this pull request Mar 25, 2016

Extended static exceptions for 4.05 #524

Merged

damiendoligez removed this from the 4.04 milestone Aug 3, 2016

gasche closed this Nov 12, 2016

This was referenced Mar 14, 2019

Unix et ThreadUnix (suite) #2437

Closed

OCaml SIGSEGV in invert_pointer_at() (OCaml Garbage Collector / Compaction) #7431

Closed

chambart pushed a commit to chambart/ocaml-1 that referenced this pull request Aug 4, 2021

First set of command-line flags for Flambda 2 (ocaml#98)

a3a87bc

stedolan pushed a commit to stedolan/ocaml that referenced this pull request Oct 5, 2021

First set of command-line flags for Flambda 2 (ocaml#98)

4363d4e

stedolan pushed a commit to stedolan/ocaml that referenced this pull request Dec 13, 2021

flambda-backend: First set of command-line flags for Flambda 2 (ocaml#98

9ae1c7a

)

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Extended static exceptions: preparation for local functions#98

Extended static exceptions: preparation for local functions#98
chambart wants to merge 72 commits intoocaml:trunkfrom
chambart:extended_static_exceptions

chambart commented Sep 4, 2014

Uh oh!

chambart commented Sep 23, 2014

Uh oh!

chambart commented Oct 3, 2014

Uh oh!

gasche commented Oct 8, 2014

Uh oh!

gasche commented Oct 8, 2014

Uh oh!

chambart commented Oct 17, 2014

Uh oh!

let-def commented Nov 15, 2015

Uh oh!

gasche commented Nov 12, 2016

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

Conversation

chambart commented Sep 4, 2014

Uh oh!

chambart commented Sep 23, 2014

Uh oh!

chambart commented Oct 3, 2014

Uh oh!

gasche commented Oct 8, 2014

Uh oh!

gasche commented Oct 8, 2014

Uh oh!

chambart commented Oct 17, 2014

Uh oh!

let-def commented Nov 15, 2015

Uh oh!

gasche commented Nov 12, 2016

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants