Skip to content

Optimize away some physical equality#850

Merged
mshinwell merged 8 commits intoocaml:trunkfrom
chambart:physequal_difference
Aug 1, 2017
Merged

Optimize away some physical equality#850
mshinwell merged 8 commits intoocaml:trunkfrom
chambart:physequal_difference

Conversation

@chambart
Copy link
Contributor

@chambart chambart commented Oct 11, 2016

Physical equality on structurally different values is always false. This patch allows to handle some cases. The need arise when evaluating some functions that use it to avoid some computation. For instance in Set.add test if the added value is already present to avoid rebuilding the same set.

    let rec add x = function
        Empty -> Node(Empty, x, Empty, 1)
      | Node(l, v, r, _) as t ->
          let c = Ord.compare x v in
          if c = 0 then t else
          if c < 0 then
            let ll = add x l in
            if l == ll then t else bal ll v r
          else
            let rr = add x r in
            if r == rr then t else bal l v rr

This change allows some of those uses to be eliminated.

@mshinwell mshinwell requested review from lpw25 and mshinwell December 9, 2016 15:50
mshinwell
mshinwell requested changes Dec 27, 2016
View reviewed changes
middle_end/simplify_primitives.ml Outdated
let is_known_to_be_some_kind_of_int (arg:A.descr) =
match arg with
| Value_int _ | Value_char _ | Value_constptr _ -> true
| _ -> false
Copy link
Contributor

@mshinwell mshinwell Dec 27, 2016

Choose a reason for hiding this comment

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

Please make both of these matches exhaustive.

middle_end/simplify_primitives.ml Outdated
let rec structurally_different (arg1:A.t) (arg2:A.t) =
match arg1.descr, arg2.descr with
| Value_block (tag1, fields1), Value_block (tag2, fields2) ->
not (Tag.equal tag1 tag2) ||
Copy link
Contributor

@mshinwell mshinwell Dec 27, 2016

Choose a reason for hiding this comment

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

Indentation needs fixing for these two stanzas (also on line 69 too).
I would also recommend following the GNU convention of putting the || at the start of each line of a multi-line conditional; I think it's easier to follow.

@mshinwell
Copy link
Contributor

mshinwell commented Mar 7, 2017

@chambart Ping

@chambart chambart force-pushed the physequal_difference branch from 65197a3 to 99f242a Compare March 15, 2017 22:55
mshinwell
mshinwell reviewed Mar 16, 2017
View reviewed changes
testsuite/tests/asmcomp/is_static_flambda.ml
(* eq is supposed to be considered always true since v is a
constant, hence aliased to a symbol.
It is not yet optimized away if it is not constant *)
let eq = v == v in
Copy link
Contributor

@mshinwell mshinwell Mar 16, 2017

Choose a reason for hiding this comment

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

These tests might as well check that eq is as expected, no?

Copy link
Contributor

@mshinwell mshinwell Jul 31, 2017

Choose a reason for hiding this comment

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

Actually I think this is fine as-is.

@mshinwell
Copy link
Contributor

mshinwell commented Mar 16, 2017

I made one comment, but OK otherwise. We need to wait for @lpw25 to review too.

@mshinwell
Copy link
Contributor

mshinwell commented Mar 16, 2017

Ah, this should have a Changes entry too, I think.

@lpw25 lpw25 added the approved label Mar 16, 2017
@mshinwell
Copy link
Contributor

mshinwell commented May 4, 2017

@chambart Please add a Changes entry and merge to trunk, thanks.

@alainfrisch
Copy link
Contributor

alainfrisch commented Jul 20, 2017

Ping @chambart

@mshinwell
Copy link
Contributor

mshinwell commented Jul 31, 2017

I've added the Changes entry and merged with current trunk. I will merge into trunk assuming CI passes.

@mshinwell mshinwell merged commit 177713e into ocaml:trunk Aug 1, 2017
stedolan added a commit to stedolan/ocaml that referenced this pull request Oct 25, 2022
@stedolan
Fix soundness bug by using currying information from typing (ocaml#850)
08424cc 
Previously, transl_curried_function in Translcore redetected function
currying, which is difficult with locals as modes may make it invalid
to merge two lambdas into a single n-ary function.

The mode logic here was wrong, leading to a soundness bug. Rather than
fix it (which would continue the duplication of mode-checking between
typing and transl), the fix here is to add the relevant information to
Typedtree, so that Translcore follows the decisions made by typing
instead of redetecting currying on its own.
sadiqj pushed a commit to sadiqj/ocaml that referenced this pull request Feb 21, 2023
@stedolan
flambda-backend: Fix soundness bug by using currying information from…
c102688 
… typing (ocaml#850)

Previously, transl_curried_function in Translcore redetected function
currying, which is difficult with locals as modes may make it invalid
to merge two lambdas into a single n-ary function.

The mode logic here was wrong, leading to a soundness bug. Rather than
fix it (which would continue the duplication of mode-checking between
typing and transl), the fix here is to add the relevant information to
Typedtree, so that Translcore follows the decisions made by typing
instead of redetecting currying on its own.
stedolan pushed a commit to stedolan/ocaml that referenced this pull request Mar 21, 2023
@mshinwell
Squashed 'ocaml/' changes from 2118848..25188da
db559ae 
25188da flambda-backend: Missed comment from PR802 (ocaml#887)
9469765 flambda-backend: Improve the semantics of asynchronous exceptions (new simpler version) (ocaml#802)
d9e4dd0 flambda-backend: Fix `make runtest` on NixOS (ocaml#874)
4bbde7a flambda-backend: Simpler symbols (ocaml#753)
ef37262 flambda-backend: Add opaqueness to Obj.magic under Flambda 2 (ocaml#862)
a9616e9 flambda-backend: Add build system hooks for ocaml-jst (ocaml#869)
045ef67 flambda-backend: Allow the compiler to build with stock Dune (ocaml#868)
3cac5be flambda-backend: Simplify Makefile logic for natdynlinkops (ocaml#866)
c5b12bf flambda-backend: Remove unnecessary install lines (ocaml#860)
ff12bbe flambda-backend: Fix unused variable warning in st_stubs.c (ocaml#861)
c84976c flambda-backend: Static check for noalloc: attributes (ocaml#825)
ca56052 flambda-backend: Build system refactoring for ocaml-jst (ocaml#857)
39eb7f9 flambda-backend: Remove integer comparison involving nonconstant polymorphic variants (ocaml#854)
c102688 flambda-backend: Fix soundness bug by using currying information from typing (ocaml#850)
6a96b61 flambda-backend: Add a primitive to enable/disable the tick thread (ocaml#852)
f64370b flambda-backend: Make Obj.dup use a new primitive, %obj_dup (ocaml#843)
9b78eb2 flambda-backend: Add test for ocaml#820 (include functor soundness bug) (ocaml#841)
8f24346 flambda-backend: Add `-dtimings-precision` flag (ocaml#833)
65c2f22 flambda-backend: Add test for ocaml#829 (ocaml#831)
7b27a49 flambda-backend: Follow-up PR#829 (comballoc fixes for locals) (ocaml#830)
ad7ec10 flambda-backend: Use a custom condition variable implementation (ocaml#787)
3ee650c flambda-backend: Fix soundness bug in include functor (ocaml#820)
2f57378 flambda-backend: Static check noalloc (ocaml#778)
aaad625 flambda-backend: Emit begin/end region only when stack allocation is enabled (ocaml#812)
17c7173 flambda-backend: Fix .cmt for included signatures (ocaml#803)
e119669 flambda-backend: Increase delays in tests/lib-threads/beat.ml (ocaml#800)
ccc356d flambda-backend: Prevent dynamic loading of the same .cmxs twice in private mode, etc. (ocaml#784)
14eb572 flambda-backend: Make local extension point equivalent to local_ expression (ocaml#790)
487d11b flambda-backend: Fix tast_iterator and tast_mapper for include functor. (ocaml#795)
a50a818 flambda-backend: Reduce closure allocation in List (ocaml#792)
96c9c60 flambda-backend: Merge ocaml-jst
a775b88 flambda-backend: Fix ocaml/otherlibs/unix 32-bit build (ocaml#767)
f7c2679 flambda-backend: Create object files internally to avoid invoking GAS (ocaml#757)
c7a46bb flambda-backend: Bugfix for Cmmgen.expr_size with locals (ocaml#756)
b337cb6 flambda-backend: Fix build_upstream for PR749 (ocaml#750)
8e7e81c flambda-backend: Differentiate is_int primitive between generic and variant-only versions (ocaml#749)

git-subtree-dir: ocaml
git-subtree-split: 25188da
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@mshinwell mshinwell mshinwell approved these changes

@lpw25 lpw25 Awaiting requested review from lpw25

Assignees

No one assigned

Labels

approved

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

@chambart @mshinwell @alainfrisch @lpw25