[llvm-dev] RFC: speedups with instruction side-data (ADCE, perhaps others?)

[Chris Lattner via llvm-dev]

> On Sep 14, 2015, at 4:28 PM, Sean Silva via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
> What is the contract between passes for the marker bit? I.e. do passes need to "clean up" the marker bit to a predetermined value after they run? (or they need to assume that it might be dirty? (like I think you do below))

This is the key question for this sort of thing (which has come up many times before).

For the record, I’m not opposed to something like this, so long as:

- It only applies to instructions and basic blocks, not constants, Function, GlobalVariable, etc.  We don’t want to make parallelization harder than it already is.
- The contract (enforced by the verifier) is that these bits are always zero between passes.
- Adding bits doesn’t increase the size of the IR over what it is today.

Beyond that, I think that it is really important to design the right data-structure around this to provide these invariants.  Here’s a sketch of something that I think could work well, over-simplified to be just a single bit on Instruction to illustrate the point:


class Instruction {
  bool TheBit = 0  // squished into something that already exists.
...
public:
  bool isBitSet() const { return TheBit; }
  void setBit(BitTracker &BT, bool Value = true) {
     if (TheBit) return;

     BT.addToSet(this);
     TheBIt = Value;
  }
}

Where BitTracker is basically just an std::vector<Instruction*> that keeps track of all the instructions which (might) have a bit set, and offers a method to go zero all the bits.

An API like this would make it very straight-forward for function passes to preserve the invariant.

-Chris