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 liveness pass calculates the minimal ranges over which registers must be live;
• The availability pass calculates the maximal ranges over which registers happen to be available.

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 variableFoo.bar is to be found in registerrax between labelsL1234 andL5678". 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 operationIname_for_debugger which 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 existingReg module). 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 namefoo to (other) registers (since the value offoo has now changed, and those registers might contain copies of its old value). Only in theCassign case will theis_assignment member insideIname_for_debugger betrue.

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 ofprovenance will 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).