Linear Scan Register Allocator for ocamlopt and ocamlnat

[vicuna]

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

• compiletime_timings.pdf
• ocaml-linear-scan-20110801.diff
• ocaml-linear-scan-20110819.diff
• ocaml-linear-scan-20110903.diff
• ocaml-linear-scan-20111014.diff
• ocaml-linear-scan20110929.diff
• runtime_timings.pdf
• timings_runtime_amd64.txt
• timings_runtime_i386.txt

[vicuna]

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]

Comment author: meurer

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

[vicuna]

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]

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]

Comment author: marcell

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

[vicuna]

Comment author: meurer

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

[vicuna]

Comment author: meurer

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

[vicuna]

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]

Comment author: meurer

Ok, makes sense.

[vicuna]

Comment author: @alainfrisch

The discussion has resumed here: #375

[vicuna]

Comment author: @alainfrisch

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