Eliminate dead `ICatch` handlers by gretay-js · Pull Request #2321 · ocaml/ocaml

gretay-js · 2019-03-13T11:31:47Z

This is an improvement of deadcode pass.
This PR detects dead handlers by propagating information about Iexit instructions that appear inside an instruction i and refer to handlers outside of i, using correct scoping rules depending on whether Icatch is recursive or not. The function deadcode was refactored to return a record instead of a pair.

Here is a common and simple example that resulted in dead code before this PR:

type t = A | B

let bar t (x:float) (y:float) = match t with
  | A -> x < y
  | B -> x > y

let foo t x y = not (bar t x y)

Generated assembly (amd64, compiled with flambda) with dead code in blocks L107 and L106:

camlTest1__foo_22:
        .cfi_startproc
.L113:
        cmpq    $1, %rax
        je      .L110
        movsd   (%rdi), %xmm0
        movsd   (%rbx), %xmm1
        comisd  %xmm0, %xmm1
        ja      .L112
        movq    $1, %rax
        jmp     .L111
        .align  4
.L112:
        xorq    %rax, %rax
.L111:
        leaq    1(%rax,%rax), %rax
        ret
        .align  4
.L110:
        movsd   (%rdi), %xmm0
        movsd   (%rbx), %xmm1
        comisd  %xmm1, %xmm0
        ja      .L109
        movq    $1, %rax
        jmp     .L108
        .align  4
.L109:
        xorq    %rax, %rax
.L108:
        leaq    1(%rax,%rax), %rax
        ret
        .align  4
.L107:
        movq    $3, %rax
        ret
        .align  4
.L106:
        movq    $1, %rax
        ret

mshinwell · 2019-06-26T13:29:43Z

I've asked @chambart and @lthls if one of them can review this.

I've been doing some experiments to determine how often dead code, that this patch removes, occurs.
On the following set of OPAM packages I measured 54 occurrences in total:

ocamlfind
num
coq
ocamlbuild
menhir
why3

On some packages there are no occurrences (e.g. in the compiler itself). So the situation doesn't happen "very often", but it definitely happens a fair amount, probably mostly when match ... with ... exception is being used.

It's good to delete these pieces of dead code not only for code size reasons but also so analysis tools that spot dead code don't complain. On one particular Jane Street executable there were nearly 4,000 dead basic blocks that such a tool spotted and were subsequently removed by this patch.

The parts of the patch that change a tupled return type to a record could potentially be committed as a separate no-op commit.

chambart · 2019-06-28T12:36:02Z

This is not eliminating some unreachable handler in recursive cases, for instance:

catch exit 1
with 1 -> ()
 and 2 -> exit 3
 and 3 -> ()

I made a pull request on the original branch.

gretay-js · 2019-06-28T13:02:37Z

Thank you for the review and the improvements - I saw the PR! Let me try to construct a cmm test from your example. @mshinwell says we can't currently generate that example in the compiler. It only generates a single exist for recursive catch, but with flambda2 it will be possible.

gretay-js · 2019-07-03T08:28:45Z

Here is an improved version (@chambart thanks!), rebased. I added a test and added a comment explaining the invariant it relies on.

@chambart : I hope you don't mind that I changed variable name "exit" to "nfail" as in other places, as "exit" confuses my syntax highlighting.

It wasn't hard to construct a cmm test for the example above of recursive catch with dead handlers. The problem was to convince ocamltest to do the intended checks. I had to make a small addition to ocamltest. @shindere, I couldn't find a way around adding "flags" and "output" to codegen actions in ocamltest. Does the change in 5d79f82 look right?

I implemented a separate function to check the variants we rely on for elimination of dead handlers: the indexes of handlers are unique across the entire function and Iexit instructions refer to the correctly scoped handlers.

I ran it on all the code in the compiler and a few other tests. The only place where invariants didn't hold is in the "asmgen" testsuite. I fixed it as part of adding the new test in commit. The fix involves a change in parsecmm of while loops and exits 5d79f82. @lthls can you please have a look? It apppears to have been slighly broken for a while.

I wonder if it is worth including the invariant checks in the compiler, perhaps under a separate flag. It is similar to linear_invariants check that @lthls has in another PR. These test can be useful especially with flambda2 changes coming up.

shindere · 2019-07-03T08:35:51Z

Greta Yorsh (2019/07/03 01:28 -0700):

The problem was to convince ocamltest to do the intended checks. I had to make a small addition to ocamltest. @shindere, I couldn't find a way around adding "flags" and "output" to codegen actions in ocamltest. Does the change in 5d79f82 look right?

Yes absolutely, thanks. It'd just be nice to make the indentation similar to the rest of the file, if you don't mind.

I implemented a separate function to check the variants we rely on for elimination of dead handlers: the indexes of handlers are unique across the entire function and Iexit instructions refer to the correctly scoped handlers. I ran it on all the code in the compiler and a few other tests. The only place where invariants didn't hold is in the "asmgen" testsuite. I fixed it as part of adding the new test in commit. The fix involves a change in parsecmm of while loops and exits 5d79f82. @lthls can you please have a look? It apppears to have been slighly broken for a while. I wonder if it is worth including the invariant checks in the compiler, perhaps under a separate flag. It is similar to linear_invariants check that @lthls has in another PR. These test can be useful especially with flambda2 changes coming up.

I think @xavierleroy may want to comment, here.

gretay-js · 2019-07-03T08:59:12Z

Yes absolutely, thanks. It'd just be nice to make the indentation similar to the rest of the file, if you don't mind.

@shindere I hope this version is better: 5929437

shindere · 2019-07-03T09:00:22Z

Greta Yorsh (2019/07/03 01:59 -0700):

> Yes absolutely, thanks. It'd just be nice to make the indentation similar to the rest of the file, if you don't mind. @shindere I hope this version is better: 5929437

Sure! Thanks!

lthls

The handling of while in parsecmm.mly seems indeed to have been broken for a very long time, and I have to admit that I'm partly guilty in that I didn't notice it was wrong when I last patched it. Thanks for fixing it.

About the uniqueness of nfail identifiers, I think it's a good thing to have, but I'm wary of relying on it without enforcing it explicitly. I have an open PR (#1400) that can help with enforcement, or you could commit your own check if you prefer. As noted in an inline comment, if nfail numbers are not unique within a function declaration then reachable handlers could be dropped, leading to strange errors later in the backend.

I've also had a look at your initial version for Icatch, and while @chambart 's one allows for more aggressive deadcode elimination (in theory, at least), the original implementation had the nice property that the live_exits set corresponded to free continuations only. You could probably restore this property with a small patch, but I'm not sure if it is important enough.

I'd like to see the issue of uniqueness settled before approving, but otherwise this PR looks good to me.

lthls · 2019-07-03T10:01:51Z

asmcomp/deadcode.ml


-(* [deadcode i] returns a pair of an optimized instruction [i']
-   and a set of registers live "before" instruction [i]. *)
+module Int = Identifiable.Make (Numbers.Int)


Numbers.Int's signature already includes Identifiable.S, so the call to Identifiable.Make seems redundant (@chambart tells me it's probably an oversight on his part)

lthls · 2019-07-03T12:58:19Z

asmcomp/deadcode.ml

+    let handlers' = Int.Map.map deadcode (Int.Map.of_list handlers) in
+    (* Previous passes guarantee that indexes of handlers are unique
+       across the entire function and Iexit instructions refer
+       to the correctly scoped handlers. *)


My thoughts about this algorithm (no action needed, though you can use this to add comments if you want):

live_exits records all the nfail numbers that have been passed to Cexit in reachable code from the current expression. This includes both free and bound continuations. Because of this, with duplicate nfail numbers in a nested context, the outer handler could be considered reachable even though it is not.

handlers are added to used_handlers (thus considered reachable) only when they are found for the first time in the live_exits of either the body or a handler that has just been found reachable. But since the initial value of live_exits in the fixpoint contains the ones from the next instruction (after the catch), reuse of nfail numbers could lead to a reachable handler that gets dropped because an exit to a different handler with the same number occurs in the next instruction.

nonrecursive handlers are handled the same way as recursive ones, which is fine in this context, but again if duplicate numbers were allowed this could make a handler wrongly considered reachable.

lthls · 2019-07-03T13:01:35Z

asmcomp/deadcode.ml

+    in
+    let live_exits, used_handlers =
+      Int.Set.fold add_live body'.exits (s.exits, [])
+    in


I would make a special case for when used_handlers is empty, to avoid creating a catch handler with no handlers

gretay-js · 2019-07-03T14:09:18Z

I'd like to see the issue of uniqueness settled

Uniqueness can be checked with a small change to the current version. Actually, I have already had a version of just that, but I removed it after convincing myself that the indexes are unique. I can resurrect it.

The invariant check are on a separate branch at the moment: 8cea3a6. They are subsumed by your PR #1400, except that mine version is on Mach instead of Cmm and checks for dead handlers. The problem in asmgen tests is probably the same one you noticed in #1400, as it had duplicated handlers.

Thank you for your other suggestions, I'll address them at the same time, but I won't be able to do it until Monday, sorry.

gretay-js · 2019-07-08T18:06:37Z

An updated version in 5be5511

does not rely on uniqueness of indexes
still collects dead handlers in recursive catch construct, as in the above example
live exits refer to correctly scoped handlers only, as in the original version
catch with no handlers is simplified

gretay-js · 2019-07-08T18:12:39Z

Forgot to say that catch without used handlers occurs 11 times in the build of the compiler itself.

shindere · 2019-07-08T18:15:56Z

Greta Yorsh (2019/07/08 11:12 -0700):

Forgot to say that catch without used handlers occurs 11 times in the build of the compiler itself.

Sorry, not sure what this means / how to interprete this information? Is that something that should be fixed somehow?

gretay-js · 2019-07-09T08:05:41Z

Greta Yorsh (2019/07/08 11:12 -0700):
Forgot to say that catch without used handlers occurs 11 times in the build of the compiler itself.
Sorry, not sure what this means / how to interprete this information? Is that something that should be
fixed somehow?

No, on the contrary. This was just to say that the optimization is useful: the simplification is indeed triggered.

shindere · 2019-07-09T09:16:15Z

Greta Yorsh (2019/07/09 01:05 -0700):

No, on the contrary. This was just to say that the optimization is useful: the simplification is indeed triggered.

Okay it makes sense now, many thanks for having taken the time to clarify!

lthls · 2019-07-09T14:17:03Z

So, removing empty handlers turns out to be not as easy as I expected (this is the cause of the CI failures). I'm sending a small pull request with a fix, which I hope is correct, but the safe solution may be to simply forget about this simplification and generate catches with no handlers anyway.

@shindere catch without used handlers are uncommon, but can happen in the following case:

(false || not (* some non-trivial expression *))

This gets compiled (in Cmmgen) to:

catch
  4 - (* expression *)
with(n)
  3

(4 - x is the translation of not x, and 3 is true)

This is not optimal, but not a huge problem.

gretay-js · 2019-07-09T15:21:15Z

Thank you for your fix, I've just merged it in on the PR branch.

lthls · 2019-07-10T13:42:21Z

asmcomp/deadcode.ml

+    let i =
+      match used_handlers with
+      | [] -> (* Simplify catch without handlers *)
+        patch_next body'.i s.i


I just noticed that my patch doesn't work if the body of the catch is Iend. I hope it never happens, and a quick test on the compiler sources and testsuite doesn't trigger anything, but adding assert (body'.i.desc <> Iend); or a small if to handle this case would be nice.

Thanks! I added some code to handle this case.

lthls · 2019-07-10T13:42:26Z

asmcomp/deadcode.ml

+        { i with desc = Icatch(rec_flag, handlers, body'.i); next = s.i }
+    in
+    { i;
+      regs = i.live;


I think this needs to be regs = Reg.add_set_array i.live arg since i could now be an instruction with arguments.

Yes, but I think we can just use regs = body'.regs in this case.

lthls · 2019-07-10T13:49:17Z

Apart from my last comments, I'm convinced about the correctness of this patch.
You need a Changes entry, and then assuming that CI is green we can merge.

shindere · 2019-07-11T08:45:02Z

Before this gets merged, it may be a good idea to cleanup the history.

gretay-js · 2019-07-11T09:04:54Z

All green on the CI.

gretay-js · 2019-07-12T11:04:45Z

Can this be merged please?

lthls

I'm satisfied with the code. I'm slightly biased though, so I won't merge myself (unless it gets stalled for too long).

mshinwell · 2019-07-16T09:20:23Z

We're going to do a final check on the Jane Street tree of this one, although we believe it to be correct.

damiendoligez

Good to go when the JS check is green (and the conflict is fixed).

gretay-js · 2019-07-17T10:19:49Z

Thank you for the reviews. Testing on Jane code finished with no regressions. I've just updated Changes to fix the conflict.

gretay-js · 2019-08-05T11:49:34Z

Can this be merged please, it's ready.

gretay-js mentioned this pull request Mar 13, 2019

Add pseudo-instruction Ladjust_trap_depth #2322

Merged

chambart self-assigned this Jun 27, 2019

gretay-js force-pushed the deadcode-catch-handler branch from 064dc79 to 5d79f82 Compare July 3, 2019 08:15

lthls reviewed Jul 3, 2019

View reviewed changes

gretay-js force-pushed the deadcode-catch-handler branch from 5be5511 to f2d05a7 Compare July 8, 2019 18:13

lthls reviewed Jul 10, 2019

View reviewed changes

lthls approved these changes Jul 12, 2019

View reviewed changes

damiendoligez approved these changes Jul 16, 2019

View reviewed changes

Eliminate dead ICatch handlers

a224744

chambart and others added 8 commits July 17, 2019 11:09

Compute live_exits with a fixpoint

8f02a4b

Add a comment about the assumptions

a2e1afa

Add asmgen test for recursive catch with dead handlers

f317e9f

Fix formatting in ocamltest

057d8b5

Do not rely on uniquness of indexes

668a707

Fix empty handler case

732412f

Fix hanlding of catch without handlers

5dccc97

Changes entry

a657aa3

gretay-js force-pushed the deadcode-catch-handler branch from 61d2a28 to a657aa3 Compare July 17, 2019 10:11

mshinwell merged commit e08a968 into ocaml:trunk Aug 6, 2019

gretay-js added a commit to gretay-js/ocaml that referenced this pull request Aug 26, 2019

Eliminate dead ICatch handlers (ocaml#2321)

3d8051e

gretay-js mentioned this pull request Nov 6, 2019

Do not emit references to dead labels (spacetime) #9097

Merged

gretay-js added a commit to gretay-js/ocaml that referenced this pull request Nov 21, 2019

Eliminate dead ICatch handlers (ocaml#2321)

9d822b7

Conversation

gretay-js commented Mar 13, 2019

Uh oh!

mshinwell commented Jun 26, 2019

Uh oh!

chambart commented Jun 28, 2019

Uh oh!

gretay-js commented Jun 28, 2019

Uh oh!

gretay-js commented Jul 3, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

shindere commented Jul 3, 2019 via email

Uh oh!

gretay-js commented Jul 3, 2019

Uh oh!

shindere commented Jul 3, 2019 via email

Uh oh!

lthls left a comment

Choose a reason for hiding this comment

Uh oh!

lthls Jul 3, 2019

Choose a reason for hiding this comment

Uh oh!

lthls Jul 3, 2019

Choose a reason for hiding this comment

Uh oh!

lthls Jul 3, 2019

Choose a reason for hiding this comment

Uh oh!

gretay-js commented Jul 3, 2019

Uh oh!

gretay-js commented Jul 8, 2019

Uh oh!

gretay-js commented Jul 8, 2019

Uh oh!

shindere commented Jul 8, 2019 via email

Uh oh!

gretay-js commented Jul 9, 2019

Uh oh!

shindere commented Jul 9, 2019 via email

Uh oh!

lthls commented Jul 9, 2019

Uh oh!

gretay-js commented Jul 9, 2019

Uh oh!

lthls Jul 10, 2019

Choose a reason for hiding this comment

Uh oh!

gretay-js Jul 11, 2019

Choose a reason for hiding this comment

Uh oh!

lthls Jul 10, 2019

Choose a reason for hiding this comment

Uh oh!

gretay-js Jul 11, 2019

Choose a reason for hiding this comment

Uh oh!

lthls commented Jul 10, 2019

Uh oh!

shindere commented Jul 11, 2019 via email

Uh oh!

gretay-js commented Jul 11, 2019

Uh oh!

gretay-js commented Jul 12, 2019

Uh oh!

lthls left a comment

Choose a reason for hiding this comment

Uh oh!

mshinwell commented Jul 16, 2019

Uh oh!

damiendoligez left a comment

Choose a reason for hiding this comment

Uh oh!

gretay-js commented Jul 17, 2019

Uh oh!

gretay-js commented Aug 5, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Reviewers

gretay-js commented Jul 3, 2019 •

edited

Loading

gretay-js commented Aug 5, 2019 •

edited

Loading