Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Unboxing should be done earlier, avoiding a second pass #7022

Closed
vicuna opened this issue Oct 16, 2015 · 2 comments

Comments

Projects
None yet
2 participants
@vicuna
Copy link

commented Oct 16, 2015

Original bug ID: 7022
Reporter: @alainfrisch
Assigned to: @alainfrisch
Status: closed (set by @xavierleroy on 2017-02-16T14:14:35Z)
Resolution: fixed
Priority: normal
Severity: minor
Fixed in version: 4.03.0+dev / +beta1
Category: back end (clambda to assembly)
Monitored by: @diml @hcarty

Bug description

The unboxing strategy (for floats and boxed integers) in Cmmgen is now as follow:

When translating an expression "let x = e1 in e2", one translate first e2 (assuming x is a general value), then one decides if e1 will produce a boxed value, and if so, one rewrites the translated e2 to replace references on the boxed x to references to the unboxed x.

This is not very good, both for compile-time complexity and for the strength of unboxing:

  • It's easy to see that this can yield quadratic compile time for expressions such as:
    let x = x +. 1. in
    let x = x +. 1. in
    ...
    let x = x +. 1. in
  • This misses some simple unboxing opportunities. Consider:
    let f b x0 =
      let x = x0 +. 1. in
      let y =
          if b then x
          else x +. 1.
      in
      y *. 2.

When "let y = ... in ..." is translated, one doesn't know yet that x will be unboxed. So the bound expression (if b then ...) cannot be certain to produce a boxed value (then branch returns x), and so y won't be unboxed:

(function camlFoo__f_1203 (b/1204: val x0/1205: val)
 (let
   (x/1210 (+f (load float64u x0/1205) 1.)
    y/1207 (if (!= b/1204 1) (alloc 2301 x/1210) (alloc 2301 (+f x/1210 1.))))
   (alloc 2301 (*f (load float64u y/1207) 2.))))

These two issues can be addressed by compiling the body e2 of "let x = e1 in e2" under the knowledge that x is unboxed (since this can now be decided looking only at e1). This would also be more direct than the current "reverse engineering" of the unboxing construction in Cmmgen.subst_boxed_number.

@vicuna

This comment has been minimized.

Copy link
Author

commented Oct 16, 2015

Comment author: @alainfrisch

I'm working on this new strategy here:

https://github.com/alainfrisch/ocaml/tree/unbox_earlier

@vicuna

This comment has been minimized.

Copy link
Author

commented Nov 12, 2015

Comment author: @alainfrisch

#259

Committed to trunk, rev 16527.

@vicuna vicuna closed this Feb 16, 2017

@vicuna vicuna added the back-end label Mar 14, 2019

@vicuna vicuna added the bug label Mar 20, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.