InstCombine, graph rewriting, Equality saturation

There’s the explicit sinking code in the main worklist processing loop around TryToSinkInstruction. I don’t believe that can move code into a loop since it can only move into a successor block with no predecessors. So I don’t believe that’s what happened in the addressspace cast case.

Then there’s accidental sinking that occurs when InstCombine looks at two or more instructions with some in another basic block and combines them to two or more instructions. In that case all of the combined instructions will be created in the block that contains the instruction that started the combine since that’s going to be the insert location for the IRBuilder. I think that’s what happened in the addressspace cast case. I don’t know how to fix this without qualifying every transform that produces mutliple instructions with a check that all the original instructions started in the same basic block.

Hello all,

I’ve been working on a prototype implementation of equality saturation on a personal branch:

https://github.com/bollu/llvm/tree/1ab19bdb5eba00d1d508535758d700c1d60a3815

For those who have read the paper, I now create A-PEG nodes. I need to create PEG nodes from these.

There are four more “steps” before this is a minimal, conservatively correct implementation:

  • Fill in the BasicBlock nodes with information from llvm::BasicBlock.
  • Implement the PEG → CFG back-conversion (what the paper calls reversion).
  • Figure out how to handle things like switch and more complex terminators which are not directly handled by the original paper (as far as I have seen. Please correct me if am wrong).

This brings me to the question, how is this going to be upstreamed? Will I have to write an RFC that details what changes are proposed by this?

I’m new to adding a large “chunk” of changes, so any help is very appreciated!

Thanks,
~Siddharth

I’m sorry, there are a couple of inaccuracies in the above e-mail:

  1. This will be a minimal working example, not a conservatively correct implementation.
  2. I also need to perform the following steps:
  • Convert stub “condition” nodes to actual nodes with information.
  • Perform equality saturation till fixpoint / timeout.
  • Use some kind of profitability heuristic to pick final optimisations.

Once this is done, I can have it bail out on code it does not understand. Then, this is a “minimal working example” on which stuff can be built.

Thanks, and sorry for the rushed e-mail
~Siddharth

This brings me to the question, how is this going to be upstreamed? Will
I have to write an RFC that details what changes are proposed by this?

Before you get to the stage of proposing changes, you should help us understand what the costs (compile time) and benefits (size/speed of generated code) are. LNT or SPEC CPU or LLVM itself are all good targets.

John

I've been working on a prototype implementation of equality saturation
on a personal branch:

https://github.com/bollu/llvm/tree/1ab19bdb5eba00d1d508535758d700c1d60a3815

Usually when you fork a github repo, a "compare" button will appear that makes it easy for people to see the diffs with respect to the upstream version. But I'm not seeing that here -- did you do something non-standard when you forked LLVM?

John

My bad, I didn’t actually fork it from the llvm mirror. I had a local copy which I pushed. You can compare against “master”, however. Be warned, the code is fugly :slight_smile:

Thanks,
~Siddharth

Hi,