Cmm arithmetic optimisations by stedolan · Pull Request #17 · ocaml/ocaml

stedolan · 2014-02-18T22:32:08Z

Some optimisations on Cmm expressions involving tagging or constants. Here's a (best-case) example:

let int_of_digits a b c = 
  100 * (Char.code a - Char.code '0') + 
   10 * (Char.code b - Char.code '0') +
    1 * (Char.code c - Char.code '0')

Trunk compiles this to:

 (+
   (+ (+ (* 200 (>>s (+ a/1020 -96) 1)) (* 20 (>>s (+ b/1021 -96) 1)))
     (* 2 (>>s (+ c/1022 -96) 1)))
   1)

This branch compiles this to:

(+ (+ (+ ( * a/1020 100) ( * b/1021 10)) c/1022) -10766)

Floating all of the constant operations, tags, etc. out of arithmetic means they can be merged into one addition.

Constant additions and tagging operations are moved out of subexpressions when possible. Often they can be merged.

chambart · 2014-02-19T00:43:48Z

asmcomp/cmmgen.ml

From the name of the function, it is not obvious that the result is the tagged result minus one. You should probably move the 'incr_int' here.

stedolan · 2014-02-23T12:22:55Z

Thanks for the quick response, sorry it took me a while to get back. I've fixed the things you pointed out.

A couple of days ago, you said that it might have O(n^2) behaviour. I'm fairly sure it doesn't: add_int only recurses when it actually finds constants, which will only happen at the root of an expression generated by these functions.

In a test, compiling a function f x = x + x + ... + x, I did observe O(n^2) runtimes. But add_int was only called O(n) times, and the problem exists on older versions of ocamlopt.

chambart · 2014-02-23T16:52:13Z

I know, I deleted the comment for that reason... The quadratic behaviour for a long addition is probably due to register allocation (or more precisely constraints generation).

Now this patch looks ok to me.

vouillon · 2014-10-10T13:45:30Z

It would be great to optimize logical operations as well.

bobot · 2014-11-11T14:25:20Z

This PR have been discussed during the last developers' meeting, where I had the pleasure to be. To sum-up:

Style: add bar at the start of match
Overflow? seems good, no obvious mistake
Use Sys.word_size.
For the record: This optimization can break other optimization like let-introduction of shared terms but it should be a general win.
OK for integration when style and Sys.word_size will be fixed.

DemiMarie · 2014-12-17T00:07:16Z

Would it be possible for me to write & submit a fixed patch?

stedolan · 2014-12-18T14:38:01Z

@drbo no objection from me! Sorry I haven't had a chance to fix this up recently.

Add | on initial match case, and use Sys.word_size

stedolan · 2014-12-29T12:42:18Z

Finally fixed this, sorry everyone for the delay.

gasche · 2015-02-07T11:32:45Z

Merged in trunk@15820, thanks!

Constant additions and tagging operations are moved out of subexpressions when possible. Often they can be merged. From Stephen Dolan: #17 git-svn-id: http://caml.inria.fr/svn/ocaml/trunk@15820 f963ae5c-01c2-4b8c-9fe0-0dff7051ff02

Constant additions and tagging operations are moved out of subexpressions when possible. Often they can be merged. From Stephen Dolan: ocaml#17 git-svn-id: http://caml.inria.fr/svn/ocaml/trunk@15820 f963ae5c-01c2-4b8c-9fe0-0dff7051ff02

Constant additions and tagging operations are moved out of subexpressions when possible. Often they can be merged. From Stephen Dolan: #17 git-svn-id: http://caml.inria.fr/svn/ocaml/trunk@15820 f963ae5c-01c2-4b8c-9fe0-0dff7051ff02

Fixes ocaml#17. (hopefully!)

Better short paths

Added continuation cloning

…alizer_promote minor gc promote all finalizers objects

ce88833 Merge flambda-backend changes b7506bb Revert "Cherry-pick of ocaml/ocaml 1eeb0e7 (ocaml#12)" 183f688 Add config option to enable/disable stack allocation (ocaml#22) ee7c849 If both the type and mode of an ident are wrong, complain about the type. (ocaml#19) 44bade0 Allow submoding during module inclusion checks (ocaml#21) de3bec9 Add subtyping between arrows of related modes (ocaml#20) 93d8615 Enable the local keywords even when the local extension is off (ocaml#18) 81dd85e Documentation for local allocations b05519f Fix a GC bug in local stack scanning (ocaml#17) 9f879de Fix __FUNCTION__ (ocaml#15) a78975e Optimise "include struct ... end" in more cases (ocaml#11134) b819c66 Cherry-pick of ocaml/ocaml 1eeb0e7 (ocaml#12) bb363d4 Optimise the allocation of optional arguments (ocaml#11) git-subtree-dir: ocaml git-subtree-split: ce88833

The stack pointer was computed relative to the wrong local arena

Fix crash when using lifted module that contains macros

…caml#17)

* Add the preview templates * Add a tutorials index page * Add a no_trailing_slash middleware

Cmm arithmetic optimisations.

0c520e4

Constant additions and tagging operations are moved out of subexpressions when possible. Often they can be merged.

chambart reviewed Feb 19, 2014
View reviewed changes

Fixes after code review of cmm arithmetic optimisations

701db1b

Coding style fixes, finally.

432ce7a

Add | on initial match case, and use Sys.word_size

gasche closed this Feb 7, 2015

stedolan added a commit to stedolan/ocaml that referenced this pull request Aug 18, 2015

Use CAML_STATIC_ASSERT only once per line.

c2a54cc

Fixes ocaml#17. (hopefully!)

mshinwell referenced this pull request in mshinwell/ocaml Jul 1, 2016

Merge pull request #17 from janestreet/patch/better-short-paths

be3b862

Better short paths

lpw25 pushed a commit to lpw25/ocaml that referenced this pull request Aug 22, 2016

Merge pull request ocaml#17 from ocamllabs/clone

d40f41e

Added continuation cloning

stedolan deleted the linear-constant-opts branch March 10, 2017 17:05

lthls mentioned this pull request Aug 8, 2019

Left-shift of 0 yields negative number #8864

Closed

stedolan pushed a commit to stedolan/ocaml that referenced this pull request Feb 20, 2020

Merge pull request ocaml#17 from ctk21/stw_minor_gc_unconditional_fin…

8b80760

…alizer_promote minor gc promote all finalizers objects

poechsel pushed a commit to poechsel/ocaml that referenced this pull request Jul 2, 2021

Add intrinsics for clz, ctz, popcnt (ocaml#17)

4ec169e

lpw25 pushed a commit to lpw25/ocaml that referenced this pull request Jun 21, 2022

Fix a GC bug in local stack scanning (ocaml#17)

b05519f

The stack pointer was computed relative to the wrong local arena

OlivierNicole pushed a commit to OlivierNicole/ocaml that referenced this pull request Oct 22, 2022

Merge pull request ocaml#17 from OlivierNicole/fix

c1d7fc7

Fix crash when using lifted module that contains macros

andreas-schwab mentioned this pull request Nov 28, 2022

ocamlopt.opt crashes from stack overflow while building coccinelle on RISC-V #11765

Closed

EmileTrotignon pushed a commit to EmileTrotignon/ocaml that referenced this pull request Jan 12, 2024

Fix yarn version after initial install by adding to devDependencies (o…

38acfee

…caml#17)

EmileTrotignon pushed a commit to EmileTrotignon/ocaml that referenced this pull request Jan 12, 2024

Preview pages (ocaml#17)

241f6f5

* Add the preview templates * Add a tutorials index page * Add a no_trailing_slash middleware

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Cmm arithmetic optimisations#17

Cmm arithmetic optimisations#17
stedolan wants to merge 3 commits intoocaml:trunkfrom
stedolan:linear-constant-opts

stedolan commented Feb 18, 2014

Uh oh!

chambart Feb 19, 2014

Uh oh!

stedolan commented Feb 23, 2014

Uh oh!

chambart commented Feb 23, 2014

Uh oh!

vouillon commented Oct 10, 2014

Uh oh!

bobot commented Nov 11, 2014

Uh oh!

DemiMarie commented Dec 17, 2014

Uh oh!

stedolan commented Dec 18, 2014

Uh oh!

stedolan commented Dec 29, 2014

Uh oh!

gasche commented Feb 7, 2015

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

Conversation

stedolan commented Feb 18, 2014

Uh oh!

chambart Feb 19, 2014

Choose a reason for hiding this comment

Uh oh!

stedolan commented Feb 23, 2014

Uh oh!

chambart commented Feb 23, 2014

Uh oh!

vouillon commented Oct 10, 2014

Uh oh!

bobot commented Nov 11, 2014

Uh oh!

DemiMarie commented Dec 17, 2014

Uh oh!

stedolan commented Dec 18, 2014

Uh oh!

stedolan commented Dec 29, 2014

Uh oh!

gasche commented Feb 7, 2015

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants