Reimplement the static analysis that supports poll point insertion by xavierleroy · Pull Request #6 · damiendoligez/ocaml

xavierleroy · 2021-05-05T13:39:28Z

Following the dataflow approach discussed with @damiendoligez.

I'm not using a generic dataflow engine yet, because it might be less efficient, so for the moment I have two specialized analyses.

@damiendoligez

Following the dataflow approach discussed with @damiendoligez.

damiendoligez

Nice code, except that there's a bug, and then it inserts too many polls: one for every handler that's in a nonallocating loop, even if polling in one of them would be enough. For example, in

let f x =
  while true do
    while true do () done
  done

you will insert poll calls in both loops, even though one poll in the inner loop is enough.

It would probably be better to mix the analysis with the poll insertions (or the decisions to insert, at least) so that, when you insert a poll in a loop, you can continue the analysis with the knowledge that this loop will poll. Of course correctness will be harder to establish...

damiendoligez · 2021-05-05T13:55:15Z

asmcomp/polling.ml

+    | Iop (Icall_ind | Icall_imm _) ->  (* TODO: make sure we can ignore exn *)
+        before i.next end_ exn


Isn't it obvious that this should be treated like an operation that can raise, like the very next case?

Or it could be treated like an Ialloc, on the assumption that the called function polls "enough". I'm confused.

damiendoligez · 2021-05-05T14:47:49Z

asmcomp/polling.ml

+    ignore (before funbody true true);
+    get_handler


Suggested change

ignore (before funbody true true);

get_handler

ignore (before funbody true true);

get_handler

damiendoligez · 2021-05-06T09:52:38Z

asmcomp/polling.ml

+    if handler_ok n then
      i
+    else
+      Mach.instr_cons (Iop (Ipoll { return_label = None })) [||] [||] i


As soon as a handler is "not-OK", you're going to insert a poll before every jump to this handler (even from the body of the catch, which cannot be part of the loop). It would be better to simply insert the poll once at the top of the handler itself.

damiendoligez · 2021-05-06T11:59:55Z

asmcomp/polling.ml

+        List.iter
+          (fun (n, h) -> set_handler n (before h end_ exn))
+          handlers;
+        before body end_ exn


There's a bug here: you can't just ignore i.next, it might contain a non-allocating loop.

Suggested change

List.iter

(fun (n, h) -> set_handler n (before h end_ exn))

handlers;

before body end_ exn

let join = before i.next end_ exn in

List.iter

(fun (n, h) -> set_handler n (before h join exn))

handlers;

before body join exn

Agreed, sorry for the bug.

damiendoligez · 2021-05-06T12:00:48Z

asmcomp/polling.ml

+        let update changed (n, h) =
+          let b0 = get_handler n in
+          let b1 = before h end_ exn in
+          if b1 = b0 then changed else (set_handler n b1; true) in
+        while List.fold_left update false handlers do () done;
+        before body end_ exn


Suggested change

let update changed (n, h) =

let b0 = get_handler n in

let b1 = before h end_ exn in

if b1 = b0 then changed else (set_handler n b1; true) in

while List.fold_left update false handlers do () done;

before body end_ exn

let join = before i.next end_ exn in

let update changed (n, h) =

let b0 = get_handler n in

let b1 = before h join exn in

if b1 = b0 then changed else (set_handler n b1; true) in

while List.fold_left update false handlers do () done;

before body join exn

damiendoligez · 2021-05-06T12:01:57Z

asmcomp/polling.ml

+    | Iexit n ->
+        get_handler n
+    | Itrywith(body, handler) ->
+        before body end_ (before handler end_ exn)


Suggested change

before body end_ (before handler end_ exn)

let join = before i.next end_ exn in

before body join (before handler join exn)

damiendoligez · 2021-05-06T12:02:53Z

asmcomp/polling.ml

+        let join = before i.next end_ exn in
+        Array.exists (fun i -> before i join exn) branches
+    | Icatch (Cmm.Nonrecursive, handlers, body) ->
+        List.iter


Same bug as in polled_loops_analysis.

damiendoligez · 2021-05-06T12:07:01Z

asmcomp/polling.ml

      next = instr i.next;
    }
-  | Icatch (Nonrecursive, hdl, body) ->
+  | Icatch (rc, hdl, body) ->


Because you ignore the rec_flag, you will insert too many polls. For example, in nonrecursive catch handlers that are followed by a nonallocating loop:

let f x y z t = begin match x with | 0 when y -> z | _ -> t end; while true do () done

Here the catch handler of the match gets an unnecessary poll (after fixing the bug).

You're right, the rec_flag should be taken into account, and polls should only go on "true" back-edges, not all jumps to handlers.

damiendoligez · 2021-05-06T12:38:51Z

@xavierleroy Don't fix your code just yet, I'm implementing my own suggestions now.

xavierleroy · 2021-05-06T13:58:41Z

Why don't you merge the parts you like in your previous proposal? It will be easier to work on a consolidated version.

…l#13294) The toplevel printer detects cycles by keeping a hashtable of values that it has already traversed. However, some OCaml runtime types (at least bigarrays) may be partially uninitialized, and hashing them at arbitrary program points may read uninitialized memory. In particular, the OCaml testsuite fails when running with a memory-sanitizer enabled, as bigarray printing results in reads to uninitialized memory: ``` ==133712==WARNING: MemorySanitizer: use-of-uninitialized-value #0 0x4e6d11 in caml_ba_hash /var/home/edwin/git/ocaml/runtime/bigarray.c:486:45 #1 0x52474a in caml_hash /var/home/edwin/git/ocaml/runtime/hash.c:251:35 #2 0x599ebf in caml_interprete /var/home/edwin/git/ocaml/runtime/interp.c:1065:14 #3 0x5a909a in caml_main /var/home/edwin/git/ocaml/runtime/startup_byt.c:575:9 #4 0x540ccb in main /var/home/edwin/git/ocaml/runtime/main.c:37:3 #5 0x7f0910abb087 in __libc_start_call_main (/lib64/libc.so.6+0x2a087) (BuildId: 8f53abaad945a669f2bdcd25f471d80e077568ef) #6 0x7f0910abb14a in __libc_start_main@GLIBC_2.2.5 (/lib64/libc.so.6+0x2a14a) (BuildId: 8f53abaad945a669f2bdcd25f471d80e077568ef) #7 0x441804 in _start (/var/home/edwin/git/ocaml/runtime/ocamlrun+0x441804) (BuildId: 7a60eef57e1c2baf770bc38d10d6c227e60ead37) Uninitialized value was created by a heap allocation #0 0x47d306 in malloc (/var/home/edwin/git/ocaml/runtime/ocamlrun+0x47d306) (BuildId: 7a60eef57e1c2baf770bc38d10d6c227e60ead37) #1 0x4e7960 in caml_ba_alloc /var/home/edwin/git/ocaml/runtime/bigarray.c:246:12 #2 0x4e801f in caml_ba_create /var/home/edwin/git/ocaml/runtime/bigarray.c:673:10 #3 0x59b8fc in caml_interprete /var/home/edwin/git/ocaml/runtime/interp.c:1058:14 #4 0x5a909a in caml_main /var/home/edwin/git/ocaml/runtime/startup_byt.c:575:9 #5 0x540ccb in main /var/home/edwin/git/ocaml/runtime/main.c:37:3 #6 0x7f0910abb087 in __libc_start_call_main (/lib64/libc.so.6+0x2a087) (BuildId: 8f53abaad945a669f2bdcd25f471d80e077568ef) #7 0x7f0910abb14a in __libc_start_main@GLIBC_2.2.5 (/lib64/libc.so.6+0x2a14a) (BuildId: 8f53abaad945a669f2bdcd25f471d80e077568ef) ocaml#8 0x441804 in _start (/var/home/edwin/git/ocaml/runtime/ocamlrun+0x441804) (BuildId: 7a60eef57e1c2baf770bc38d10d6c227e60ead37) SUMMARY: MemorySanitizer: use-of-uninitialized-value /var/home/edwin/git/ocaml/runtime/bigarray.c:486:45 in caml_ba_hash ``` The only use of hashing in genprintval is to avoid cycles, that is, it is only useful for OCaml values that contain other OCaml values (including possibly themselves). Bigarrays cannot introduce cycles, and they are always printed as "<abstr>" anyway. The present commit proposes to be more conservative in which values are hashed by the cycle detector to avoid this issue: we skip hashing any value with tag above No_scan_tag -- which may not contain any OCaml values. Suggested-by: Gabriel Scherer <gabriel.scherer@gmail.com> Signed-off-by: Edwin Török <edwin.torok@cloud.com> Co-authored-by: Edwin Török <edwin.torok@cloud.com>

damiendoligez and others added 6 commits April 23, 2021 17:07

better version of path_polls and requires_prologue_polls

2a61e96

better version of instrument_body_with_polls

2d938ea

do not insert a poll before raise

205fcf7

make seq_approx tail-recursive

29bdea1

add memoization for the approx function

5e15aca

Reimplement the static analysis that supports poll point insertion

58676bd

Following the dataflow approach discussed with @damiendoligez.

xavierleroy mentioned this pull request May 5, 2021

Safepoints sadiqj/ocaml#3

Closed

damiendoligez reviewed May 6, 2021

View reviewed changes

damiendoligez force-pushed the safepoints branch from 5e15aca to d848d09 Compare May 6, 2021 14:36

xavierleroy closed this May 6, 2021

xavierleroy deleted the safepoints branch July 18, 2021 16:29

		\| Iop (Icall_ind \| Icall_imm _) -> (* TODO: make sure we can ignore exn *)
		before i.next end_ exn

	before body end_ (before handler end_ exn)
	let join = before i.next end_ exn in
	before body join (before handler join exn)

Conversation

xavierleroy commented May 5, 2021

Uh oh!

damiendoligez left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

damiendoligez commented May 6, 2021

Uh oh!

xavierleroy commented May 6, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

xavierleroy commented May 6, 2021 •

edited

Loading