IRC & LS followup

[gretay-js]

A few items of followup after merging https://github.com/ocaml-flambda/flambda-backend/pull/678

• https://github.com/ocaml-flambda/flambda-backend/pull/678#discussion_r913746264
• https://github.com/ocaml-flambda/flambda-backend/pull/678#discussion_r914515699
• https://github.com/ocaml-flambda/flambda-backend/pull/678#discussion_r914568978
• https://github.com/ocaml-flambda/flambda-backend/pull/678#discussion_r914676538
• https://github.com/ocaml-flambda/flambda-backend/pull/678#discussion_r914879519
• https://github.com/ocaml-flambda/flambda-backend/pull/678#discussion_r914883125
• Create a separate directory for regalloc (either under cfg or next to it, not sure) See https://github.com/ocaml-flambda/flambda-backend/pull/1306
• if we have mutable fields in Cfg.instruction we should make live mutable too again and see if it helps with performance.
• remove_prologue_if_not_required : why does it need to be added on always, instead of adding it on after regalloc and only if required? (there was something about it being after debug related instructions).
• Cfg_regalloc_utils Instruction: something is wrong in our Cfg interface if we need this.
• Is there a check that there is no edge between two Reg.t that are precolored in different colors?
• Assert the item is in the expected worklist before removing it (e.g., remove_spill_work_list).
• refactoring of the parameters of rewrite: spilled_nodes as in https://github.com/ocaml-flambda/flambda-backend/pull/774#pullrequestreview-1097776074 , and possiby removing reset by somehow making State.make and State.reset more uniform.

[xclerc]

Also, from the PR TODO list:

• check whether storing the liveness in the instructions would make a material difference -- not the same thing but https://github.com/ocaml-flambda/flambda-backend/pull/782 may help avoiding unnecessary recomputations;
• implement the equivalent of Reload -- See https://github.com/ocaml-flambda/flambda-backend/pull/771;
• experiment with other representations (state, CFG) -- See e.g. https://github.com/ocaml-flambda/flambda-backend/pull/775, https://github.com/ocaml-flambda/flambda-backend/pull/793, https://github.com/ocaml-flambda/flambda-backend/pull/897;
• "hierarchical" heuristics for spilling -- See https://github.com/ocaml-flambda/flambda-backend/pull/1080;
• better spilling/splitting See https://github.com/ocaml-flambda/flambda-backend/pull/1442.

[xclerc]

~~Not strictly IRC-related, but the spilling costs should not include any use by a probe.~~ See https://github.com/ocaml-flambda/flambda-backend/pull/945

[xclerc]

Stack operands: revisit https://github.com/ocaml-flambda/flambda-backend/pull/771#discussion_r967049882

[xclerc]

~~Not IRC-specific, but part of the pipeline: consider moving to dynamic arrays or doubly linked list for the layout.~~ See https://github.com/ocaml-flambda/flambda-backend/pull/1124

[xclerc]

Move could probably accept a stack operand here.

[gretay-js]

In cfg_stack_operands.ml allow stack operands for Valueofint and Intofvalue and maybe Opaque. See comment in https://github.com/ocaml-flambda/flambda-backend/pull/855

[xclerc]

There are likely missed opportunities for stack operands in IRC because of aliasing. Indeed, the functions rewriting arg/res to use stack operands do get a map of spilled registers, but that map does not include aliases.

[xclerc]

Other missed opportunities for stack operands are related to float operations - See upstream's version.

[xclerc]

Port upstream's improvement to LS heuristics. note: https://github.com/ocaml-flambda/flambda-backend/pull/1464 is possibly equivalent while applying to all CFG-based allocators

[xclerc]

There are no compilers hooks on the IRC pipeline. While we do not have spill/split there (yet), we could have a hook for liveness. The compiler hook for CFG is also not called on the IRC pipeline.

[xclerc]

The IRC pipeline does not have an equivalent of Available_regs. See https://github.com/ocaml-flambda/flambda-backend/pull/1748

[xclerc]

Remove the calls to Profile.record introduced by https://github.com/ocaml-flambda/flambda-backend/pull/1095 and https://github.com/ocaml-flambda/flambda-backend/pull/1123. See https://github.com/ocaml-flambda/flambda-backend/pull/1290

[xclerc]

~~Revisit the CR introduced by https://github.com/ocaml-flambda/flambda-backend/pull/1292, that is: ensure optimality of stack frame sizes.~~ See https://github.com/ocaml-flambda/flambda-backend/pull/1464

[xclerc]

Split/rename preprocessing phase (i.e. https://github.com/ocaml-flambda/flambda-backend/pull/1442 and follow-ups):

• add support for closure, flambda1, flambda2/classic;
• remove useless Profile.record calls after build-time optimization;
• more "code motion" / optimizations by e.g. implementing https://github.com/ocaml-flambda/flambda-backend/pull/1443 on straightline sequences - See https://github.com/ocaml-flambda/flambda-backend/pull/1741;
• in https://github.com/ocaml-flambda/flambda-backend/pull/1443, remove the bindings with an empty set;
• investigate the threshold applied in "rewrite" to determine whether to call the split/reload phase (maybe another criterion could be used, e.g. the fact that CSE is off).

[xclerc]

~~In rewrite_gen (Regalloc_rewrite module), the calls to Array.map are not necessary since the arrays are no longer shared. (It means that the condition might also not be necessary.)~~ See https://github.com/ocaml-flambda/flambda-backend/pull/1544

[xclerc]

~Get rid of the STACK_SLOTS_OPTIM parameter introduced by https://github.com/ocaml-flambda/flambda-backend/pull/1464.~ See https://github.com/ocaml-flambda/flambda-backend/pull/1545

[xclerc]

After https://github.com/ocaml-flambda/flambda-backend/pull/1441, Regalloc_utils.insert_block accepts to insert an empty block. Double check whether it is actually necessary, or we can avoid ever inserting empty blocks.

[xclerc]

In https://github.com/ocaml-flambda/flambda-backend/pull/1442, consider more destruction points, as mentioned in the CR-soons in proc.ml.

[xclerc]

Get rid of Instruction.dummy (and others) once we have nullable types.

[xclerc]

In RemoveDominatedSpillsForConstants, consider whether it would be better to compute num_sets through a forward dataflow analysis. Also reconsider the status of a missing key in this table:

• should it enable the optimization?
• should it be regarded as breaking an invariant?

[xclerc]

As noted in https://github.com/ocaml-flambda/flambda-backend/pull/1741, the various optimizations can result in empty sets in the map. Double check whether the corresponding mappings can be safely be removed.

[xclerc]

Not urgent since we currently only support amd64, but IRC current ignores the Proc.rotate_registers variable (unlike Coloring).

[gretay-js]

amd64/reload.ml has important comments about instruction set constraints on locations and sharing of registers. We should preserve this information when moving to the CFG pipeline, perhaps as part of the next version of stack operands.