[llvm-dev] Understanding and Cleaning Up Machine Instruction Bundles

[Matthias Braun via llvm-dev]

I am using machine instruction bundles [1] before register allocation. This
appears not to be too common today and I'd really like some input on the intentions and
plans of the current system. And would like some input on clean up proposals.

[1] I am currently experimenting to use machine instruction bundles to reliably
form macroop fusion opportunities without spills, reloads, splits or further
scheduling sneaking instruction in between.

== Documentation ==
It seems the best existing description about bundles is Evans original RFC:
http://lists.llvm.org/pipermail/llvm-dev/2011-December/045851.html
Are there any subsequent discussion threads that I missed?

== BUNDLE instruction / operands ==
For many backend passes a bundle can appear as a single unit. However one important tool
here is having an iterator over all operands of this unit.

The original RFC indicates that to achieve this without changing a big number
of passes an additional bundle instruction is added in front of the bundle. A
copy of all register/regmask machine operands is added to this header
instruction. Internal reads inside the bundle are marked as such. This step is
called finalization of a bundle.

The system works because the default basic block iterator moves from bundle to
bundle skipping the instructions inside the bundle. Iterating over the operands
will only give us the operands of the BUNDLE instruction but that is fine,
because it basically has a copy of everything inside the bundle.

== When to finalize bundles; Remove the FinalizeMachineBundles pass? ==

However there is a number of remaining questions/confusion: The RFC indicates
that the finalization step is done as a separate pass at the end of the
register allocation pipeline. In fact a FinalizeMachineBundles pass exists but
is not used by anyone. There is no in-tree target doing bundling before
register allocation, the one out of tree target I am aware of finalizes bundles
immediate after constructing them and is not using the separate pass.

In fact I am not sure why you would even wait with the finalization and do it
in a separate pass rather than doing it immediately after forming the bundle.
Using the pass today does not even work as the MachineVerifier will reject the
intermediate unfinalized state (missing internal read markers). I'd suggest to get
rid of the pass and the idea of delegating finalization to an own pass, any objections?

== Too many different iterators ==

Another source of confusion even for experience register allocation developers
is that we have 3 kinds of iterators for MachineOperands:

  - There is MachineInstr::iterator which is used by the majority of passes and
    gives you the operands of a single instruction.
  - There is (Const)MIOperands which appears to be equivalent to
    MachineInstr::iterator. I think we do not need a 2nd iterator and should get
    rid of this one (the only real reason to use it today is
    analyze{Virt|Phys}Reg() but that can be changed).
  - There is (Const)MIBundleOperands which iterates all machine operands of all
    instructions inside a bundle.

The last one appears to be necessary in a world without the initial BUNDLE
instruction repeating all the operands inside the bundle. In a setting where
finalization happens as a separate pass at the end of register allocation this
would be necessary for earlier register allocation passes.

However given that delaying finalization to a pass appears broken/unused it
seems we could just as well use MachineInstr::iterator instead and remove
MIBundleOperands. Any objections?

== Moving to a scheme without repeating the operands in the bundle header ==

I've heard some comments that the long term plan was to move to a scheme where
the operands inside the bundle are not repeated in a bundle header and instead
everyone uses an iterator like MIBundleOperands. I could not find any mails
documenting this, so it would be nice if some people could chime in here if
that was indeed the plan.

Even with this long term plan in mind I would suggest to remove
MIBundleOperands. If we implement this plan we should rather change
MachineInstr::iterator later instead of being in the confusin in-between state
that we have today.

- Matthias