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

Linear Scan Register Allocator for ocamlopt and ocamlnat #5324

Closed
vicuna opened this issue Aug 1, 2011 · 11 comments
Closed

Linear Scan Register Allocator for ocamlopt and ocamlnat #5324

vicuna opened this issue Aug 1, 2011 · 11 comments
Milestone

Comments

@vicuna
Copy link

vicuna commented Aug 1, 2011

Original bug ID: 5324
Reporter: meurer
Status: resolved (set by @xavierleroy on 2012-01-31T08:03:10Z)
Resolution: fixed
Priority: normal
Severity: feature
Version: 3.12.0
Target version: 4.06.0 +dev/beta1/beta2/rc1
Category: ~DO NOT USE (was: OCaml general)
Monitored by: meyer @gasche abdallah bitbckt meurer mehdi @ygrek @glondu @hcarty @Chris00 @alainfrisch

Bug description

As announced on the mailinglist, here is the first version of the linear scan algorithm for ocamlopt and ocamlnat.

File attachments

@vicuna
Copy link
Author

vicuna commented Aug 2, 2011

Comment author: @alainfrisch

This patch is very interesting.

Could you post here some timings (compilation speed and performance of compiled code)?

Minor question about the patch: wouldn't it be cleaner to have a single function Asmgen.regalloc with a conditional on use_linscan, rather than having two functions called in sequence that do their job or nothing according to the situation?

Also, is it really necessary to redefine sys_time? (As opposed to using Sys.time which is in the stdlib.)

@vicuna
Copy link
Author

vicuna commented Aug 3, 2011

Comment author: meurer

I forwarded your questions. As said, it's the very first working patch, and there are no timing results yet.

@vicuna
Copy link
Author

vicuna commented Aug 18, 2011

Comment author: meurer

I've imported the most recent patch from Marcell with some cleanups, merged the latest changes from the 3.12 branch and uploaded the project to GitHub at https://github.com/bmeurer/ocaml-experimental/tree/linear-scan-register-allocator in the linear-scan-register-allocator branch (for reference).

Marcell did some benchmarking and will publish the results soon.

@vicuna
Copy link
Author

vicuna commented Aug 19, 2011

Comment author: marcell

I've added timings for the runtime performance for amd64 and i386. Both showing the runtime for code compiled with the graph-coloring and the linear-scan algorithm and the ratio of the two measurements.

Although meurer already merged the latest changed into the GitHub-Repository I also added the latest diff.

I will add timings for the compilation time soon.

@vicuna
Copy link
Author

vicuna commented Aug 24, 2011

Comment author: marcell

Added timing results for the compilation time and also added the runtime results again as a more readable diagram.

@vicuna
Copy link
Author

vicuna commented Sep 3, 2011

Comment author: meurer

I've updated the patch with several cleanups and uploaded a new diff.

@vicuna
Copy link
Author

vicuna commented Sep 29, 2011

Comment author: meurer

Updated patch, with several cleanups and fixes for the ARM port.

@vicuna
Copy link
Author

vicuna commented Jan 31, 2012

Comment author: @xavierleroy

Here is my analysis of this proposal. The "big" users of OCaml, esp. the members of the Caml consortium, push strongly towards improving the performance of ocamlopt-generated code, but don't really care about compilation times. Linear scan register allocation goes in a different direction: fast compilation times at the cost of slightly lower quality of the generated code. I would rather invest time and effort on replacing ocamlopt's Briggs-style graph coloring by George and Appel's IRC graph coloring: this should result in slightly faster generated code and slightly lower compilation times at the same time. For the time being, let me just put this PR in the "suspended" state.

@vicuna vicuna closed this as completed Jan 31, 2012
@vicuna
Copy link
Author

vicuna commented Jan 31, 2012

Comment author: meurer

Ok, makes sense.

@vicuna
Copy link
Author

vicuna commented Jan 19, 2016

Comment author: @alainfrisch

The discussion has resumed here: #375

@vicuna
Copy link
Author

vicuna commented Feb 22, 2017

Comment author: @alainfrisch

Merged in trunk. Will be part of 4.06. Thanks to Benedikt, Marcell and Nicolas!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant