Register availability analysis#856
Conversation
|
This has been updated for current trunk. @chambart please review again. |
|
It looks like a few things could be simplified and clearer if you separated the notion of 'available before' and 'available across'. Of course in general available across wouldn't be observable, but for call and instructions implemented as multiple opcodes this can matter. Also, it seems like there might be a problem with Ialloc: a register which was not clobbered might still be unavailable due to a collection moving the value. This seems to be handled correctly by functions, but there is the same problem here. If you want to represent values that are probably available, you should add another notion of 'available if not moved or collected'. Most of the time those values would still be available. I don't know if there is a good way to expose that in dwarf. Otherwise it might not matter, but just for the record, there are two potential performance problems:
I'm quite confident that except the Ialloc case everything else is fine. |
asmcomp/debug/available_regs.ml
Outdated
| in | ||
| let results = | ||
| assert (Array.length instr.arg = Array.length instr.res); | ||
| Array.mapi (fun index result_reg -> |
asmcomp/debug/available_regs.ml
Outdated
| (RD.Set.of_array results)) | ||
| | Iop op -> | ||
| if M.operation_can_raise op then begin | ||
| augment_availability_at_raise (Ok avail_before) |
There was a problem hiding this comment.
If the instruction can destroy some register, this should be available across rather than available before.
There was a problem hiding this comment.
This should be fixed
asmcomp/debug/available_regs.ml
Outdated
| Printmach.instr ({ instr with M. next = M.end_instr (); }) | ||
| end; | ||
| match instr.desc with | ||
| | Iop (Ialloc _) -> |
There was a problem hiding this comment.
Across an allocation, only live and spilled values are guaranteed to be available.
There was a problem hiding this comment.
This should be fixed now
asmcomp/debug/available_regs.ml
Outdated
| (* Second: the case of OCaml to OCaml function calls. In this case, | ||
| registers always become unavailable unless: | ||
| (a) they are "live across" the call; and/or | ||
| (b) they hold immediates and are assigned to the stack. *) |
There was a problem hiding this comment.
This comment might need to explain why this is the case: the gc can move anything else.
| assert (nfail = nfail'); | ||
| (* This [available_regs] call may cause [avail_at_exit] to be | ||
| updated. *) | ||
| available_regs handler ~avail_before:avail_at_top_of_handler |
There was a problem hiding this comment.
To avoid useless traversal (with a potential linear speedup if the handlers are in the wrong order), this could check if the argument changed. i.e. if avail_at_top_of_handler is equal to handler.available_before.
There was a problem hiding this comment.
This check could be done for every instruction to avoid too much recomputing in case of nested fixpoints. But that would require an efficient equality test.
There was a problem hiding this comment.
Hmm, except you need to get the "available_after" set somehow. I think for the moment I'm going to leave this, I have added a comment in the code referencing these suggestions.
| Array.mapi (fun index result_reg -> | ||
| let arg_reg = instr.arg.(index) in | ||
| match RD.Set.find_reg_exn avail_before arg_reg with | ||
| | exception Not_found -> |
There was a problem hiding this comment.
This case should never happen. It can be an assertion.
There was a problem hiding this comment.
I've changed this to use Array.map2.
| | Unreachable -> Format.fprintf ppf "<unreachable>" | ||
| | Ok availability -> | ||
| Format.fprintf ppf "{%a}" | ||
| (Format.pp_print_list (Reg_with_debug_info.print ~print_reg)) |
There was a problem hiding this comment.
You should add ~pp_sep:(fun ppf () -> Format.fprintf ppf ",@ ")
|
I think I've addressed everything (although deferring the performance concerns). I also fixed a small mistake: names should not be propagated from I have added two flags: |
chambart
left a comment
There was a problem hiding this comment.
Looks good for merge to me now. Thanks
The availability analysis was introduced in 2017 as part of GPR ocaml#856, as a first step towards generating DWARF debugging information. This project (generating DWARF debug info) was stopped, but the analysis is still here, even though its results are not used and it is not normally run (except when the experimental -drunavail flag is given). This is essentially dead code. This PR removes it.
The availability analysis was introduced in 2017 as part of GPR #856, as a first step towards generating DWARF debugging information. This project (generating DWARF debug info) was stopped, but the analysis is still here, even though its results are not used and it is not normally run (except when the experimental -drunavail flag is given). This is essentially dead code. This PR removes it.
Co-authored-by: Cuihtlauac ALVARADO <cuihtmlauac@tarides.com>
This pull request adds a forwards dataflow pass on Mach code to calculate which registers are available immediately prior to each instruction (that is to say, when the program counter is exactly at the start of that instruction. There is a subtlety to do with call instructions which will be explained in a later pull request---it isn't relevant for the correctness of this pass).
Another way of thinking of this is:
The output of this pass is annotations on individual Mach instructions. These are collected together into contiguous ranges spanning multiple instructions by a subsequent pass, to be presented. These ranges correspond to statements such as "the value of the variable
Foo.baris to be found in registerraxbetween labelsL1234andL5678". Ranges such as these may be transcribed into DWARF location lists that may be evaluated by the debugger at runtime against a specific value of the program counter. This then determines which variables are available to have their values inspected at that particular point in the program.This analysis should be textbook, but is full of subtleties.
The availability analysis propagates naming information using a special operation
Iname_for_debuggerwhich is analogous to the method used in CompCert (thanks to @xavierleroy for describing this, which helped to simplify the code from the previous version---we no longer have to modify the existingRegmodule). Changes toSelectgen, which are not presented here, insert these new operations when it becomes clear what the name to be associated to a particular register will be. The availability analysis then propagates that forwards. Care needs to be taken withCassign---if the value being assigned to is mutable and is associated to the variablefoo, say, then we need to forget about any other ascriptions of the namefooto (other) registers (since the value offoohas now changed, and those registers might contain copies of its old value). Only in theCassigncase will theis_assignmentmember insideIname_for_debuggerbetrue.There is an assertion in this pass that checks the relation between liveness and availability, namely that any live register must also be available. This requires GPR#852 to work properly.
The type of
provenancewill be changed in due course. Those of you following along with the Flambda pull request #855 should be starting to see how this lines up with the provenance information there.I will probably make some efficiency improvements and tidy-ups to this code, but it's pretty much in a final form now, and review should commence as it's tricky. @chambart has already looked at the core algorithm before (Pierre, your comments have been marked as XCR where they have been dealt with; please make a pull request against this one to delete them or re-open them as appropriate).