Skip to content

Keep more type information in Lambda#2156

Merged
alainfrisch merged 21 commits intoocaml:trunkfrom
alainfrisch:chambart-function_parameter_type
Nov 23, 2018
Merged

Keep more type information in Lambda#2156
alainfrisch merged 21 commits intoocaml:trunkfrom
alainfrisch:chambart-function_parameter_type

Conversation

@alainfrisch
Copy link
Copy Markdown
Contributor

@alainfrisch alainfrisch commented Nov 20, 2018 •
edited
Loading

This PR adds more propagation of "value kinds" (used to drive float unboxing, in particular) through the compiler:

The first point is somehow independent from the other ones, but (1) it goes in the same direction as the second point; and (2) all together they will allow to make sure that functions compiled "statically" as in #2143 will not require boxing when jumping to a shared continuation.

Variants of #1322 (unboxed calling conventions) and other optimizations could also benefit from keeping more value kinds in lambda/clambda.

The text below does not apply any more to this PR

In its current state, this PR already avoids boxing b in;

let f z x y =
  let a, b =
    if z then (x * 2, y *. 3.)
    else (x, y)
  in
  float a -. b

The tuple binding is compiled to a staticcatch, and this optimization now makes sure to annotate the parameters of the staticcatch with value kinds derived from the pattern type. (This only works without flambda. Extra work will be needed to propagate -- and hopefully enrich -- the value kind annotations through flambda.)

Similarly, the PR avoids some boxing with or-pattern, such as for x in:

type t =
  {
    x: float;
    y: float;
  }

let f = function
  | Some {x; y = 0.} | Some {x = 0.; y = x} -> x +. x
  | _ -> 0.

The unboxing decision for staticcatch parameters (in Cmmgen) is currently only based on value kind annotations (inherit from Lambda). One bad case is when all staticraise sites naturally produce a boxed version (e.g. by calling a float-returning function, or reading from a boxed data structure), and the statichandler can use this boxed version directly. With the new heuristics, those floats will be unboxed and then reboxed when accessed in the handler. This is similar to what happens for float mutable variables, which are always unboxed (independently of the bound expression), and I think one can live with that.~~

chambart and others added 10 commits February 3, 2017 17:26
@alainfrisch alainfrisch changed the title [WIP] Keep more type information in Lambda Keep more type information in Lambda Nov 20, 2018
@alainfrisch
Copy link
Copy Markdown
Contributor Author

alainfrisch commented Nov 20, 2018

I've edited the description and removed the [WIP] marker. This is ready for review.

@alainfrisch alainfrisch changed the title Keep more type information in Lambda Keep more type information in Lambda, unbox float across statichandlers Nov 20, 2018
@alainfrisch alainfrisch mentioned this pull request Nov 20, 2018
Merged
@alainfrisch
Copy link
Copy Markdown
Contributor Author

alainfrisch commented Nov 20, 2018

(Note: CI reported on #1029 a problem while compiling Camlp4, because of "empty pattern matching", not allowed by the normal syntax. I've added a commit which should fix this problem. AppVeyor/Travis don't compile Camlp4 anymore.)

@alainfrisch
Copy link
Copy Markdown
Contributor Author

alainfrisch commented Nov 21, 2018

Commit 998d831 avoids boxing of x in:

type t =
  {
    x: float;
    y: float;
  }

let f = function
  | Some {x; y = 0.} | Some {x = 0.; y = x} -> x +. x
  | _ -> 0.

@alainfrisch
Copy link
Copy Markdown
Contributor Author

alainfrisch commented Nov 21, 2018

Would someone be able to review this PR (perhaps @chambart , @lpw25 or @mshinwell)?

chambart
chambart reviewed Nov 22, 2018
View reviewed changes
chambart
chambart reviewed Nov 22, 2018
View reviewed changes
bytecomp/lambda.ml
| _ -> Llet(str, kind, var, exp, body)

let bind str var exp body =
bind_with_value_kind str (var, Pgenval) exp body
Copy link
Copy Markdown
Contributor

@chambart chambart Nov 22, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I've looked at the use points for this function. They are all in Matching. Most of them do have kind information. I think it would probably be better to update the uses rather than the definition.

Copy link
Copy Markdown
Contributor Author

@alainfrisch alainfrisch Nov 22, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I've switched two call sites to compute the value_kind, but all others in Matching, there does not seem to be a trivial way to compute the value_kind without more refactoring.

chambart
chambart reviewed Nov 22, 2018
View reviewed changes
chambart
chambart reviewed Nov 22, 2018
View reviewed changes
chambart
chambart reviewed Nov 22, 2018
View reviewed changes
chambart
chambart reviewed Nov 22, 2018
View reviewed changes
@chambart
Copy link
Copy Markdown
Contributor

chambart commented Nov 22, 2018

I would have separated the propagation/unboxing in 2 PR, but it doesn't really matter.
I had a few remarks, but otherwise I have no objection to the propagation part and the code is ok.
The unboxing part, I think, could have been handled exactly like the non-mutable lets.

@mshinwell
Copy link
Copy Markdown
Contributor

mshinwell commented Nov 23, 2018

Could we please separate the unboxing part from the propagation of kinds in this patch? They seem like distinct features.

@alainfrisch
Copy link
Copy Markdown
Contributor Author

alainfrisch commented Nov 23, 2018

Ok, let's try to get the (tedious but mechanical) propagation stuff first. I've reverted the commit about the actual unboxing and will submit another PR later.

@alainfrisch alainfrisch changed the title Keep more type information in Lambda, unbox float across statichandlers Keep more type information in Lambda Nov 23, 2018
@alainfrisch
Copy link
Copy Markdown
Contributor Author

alainfrisch commented Nov 23, 2018

All comments addressed. I've reviewed the part originally written by @chambart , and @chambart looked at the part I added. @chambart : if you are happy with the current state, can you add a formal review?

chambart
chambart reviewed Nov 23, 2018
View reviewed changes
bytecomp/translcore.ml
let lvars = List.map (fun id -> Lvar id) val_ids in
static_catch (transl_list argl) val_ids
(Matching.for_multiple_match e.exp_loc lvars val_cases partial)
let val_ids =
Copy link
Copy Markdown
Contributor

@chambart chambart Nov 23, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why did you change the indentation depth here ? I know that 4 is the default, but the rest of the code is 2 here

Copy link
Copy Markdown
Contributor Author

@alainfrisch alainfrisch Nov 23, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I didn't; emacs+ocp-indent did, and I'm a bit too lazy to find how to disable this behavior. You can ask GitHub to hide whitespace changes if this helps reviewing.

chambart
chambart reviewed Nov 23, 2018
View reviewed changes
asmcomp/flambda_to_clambda.ml Outdated
arity = Flambda_utils.function_arity function_decl;
params = List.map (fun var -> VP.create var) (params @ [env_var]);
params =
List.map (fun var -> VP.create var, Lambda.Pgenval) (params @ [env_var]);
Copy link
Copy Markdown
Contributor

@chambart chambart Nov 23, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

check_typo is complaining about this line (81 characters)

@chambart
Copy link
Copy Markdown
Contributor

chambart commented Nov 23, 2018

I think it's good to go when the CI is happy (the only failure is check_typo).

@alainfrisch alainfrisch merged commit 7a746de into ocaml:trunk Nov 23, 2018
@shindere
Copy link
Copy Markdown
Contributor

shindere commented Nov 23, 2018

This breaks the tests/translprim/array_spec.ml test when the
compiler is configured with -no-flat-float-array.

More precisely: there is a difference between the expected and the obtained
output:

  •  (array.length[addr] addr_a) (function a (array.length[addr] a))

  •  (array.length[addr] addr_a) (function a : int (array.length[addr] a))

Shall I just go ahead and update the reference file or is there something
deeper to do here?

@alainfrisch
Copy link
Copy Markdown
Contributor Author

alainfrisch commented Nov 23, 2018

No, nothing deep, this simply needs to be updated!

@shindere
Copy link
Copy Markdown
Contributor

shindere commented Nov 23, 2018 via email

@alainfrisch
Copy link
Copy Markdown
Contributor Author

alainfrisch commented Nov 23, 2018

Thanks! @shindere!

@shindere
Copy link
Copy Markdown
Contributor

shindere commented Nov 23, 2018 via email

@alainfrisch alainfrisch mentioned this pull request Nov 23, 2018
Closed
@mshinwell mshinwell mentioned this pull request Jun 28, 2019
Closed
@trefis trefis mentioned this pull request Sep 25, 2019
Merged
@buergerling
Copy link
Copy Markdown

buergerling commented Nov 27, 2019 •
edited
Loading

I'd like to use the -dtypedtree flag and a modified printtyped.ml to transpile from ocaml into another language without such advanced pattern matching capabilities.

Is there a pattern match compiler keeping all type information?

@gasche
Copy link
Copy Markdown
Member

gasche commented Nov 27, 2019

@buergerling I would recommend instead that you link to compilerlibs and implement your own driver program; driver/compile_common.mli shows you how to parse and type-check a module, and then you can use your own code to turn the typedtree into an AST for your output language -- or print it directly. (The Compierlibs API is not stable, so this couples you to a specific compiler version, but then so does forking the compiler as you have in mind.)

The compilation of pattern-matching is done during the Typedtree->(untyped)Lambda translation, so it does not preserve type information. This means that you would probably have to rewrite your own pattern-matching compiler yourself. You could also fork OCaml's pattern-matching compiler to emit a typed representation, and I think it would be doable, but it's a complex piece of the codebase.

@gasche gasche mentioned this pull request Apr 26, 2021
Closed
@lthls lthls mentioned this pull request Apr 25, 2024
Open
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@mshinwell mshinwell mshinwell left review comments

@chambart chambart chambart left review comments

Assignees

No one assigned

Labels

approved

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

6 participants

@alainfrisch @chambart @mshinwell @shindere @buergerling @gasche