global value numbering

[Roger-luo]

this is a quite standard pass we are missing right now.

[weinbe58]

How is this different from CSE? The only difference is how you could possible implement it, e.g., you could use hashing for this pass but that's not the only why to check equivalence between constant statements.

[kaihsin]

This is a bit tricky because kirin allow arbitrary python class as constant. I am thinking we only check and eliminate constant that are only hashable

[Roger-luo]

This is a bit tricky because kirin allow arbitrary python class as constant. I am thinking we only check and eliminate constant that are only hashable

That's not true, we assume "all attributes are hashable". Read the implementation of CSE, and note that GVN is not the same as CSE, a lot of redundancy is already removed today when you run CSE.

One the other hand, I'm not sure if we really should push this to far (about checking SSAValue equivalence) - the gain does not seem to worth the cost not to say one day we will still move part of the compilation into low-level infrastructure (e.g MLIR or Julia)

[kaihsin]

This is a bit tricky because kirin allow arbitrary python class as constant. I am thinking we only check and eliminate constant that are only hashable

That's not true, we assume "all attributes are hashable". Read the implementation of CSE, and note that GVN is not the same as CSE, a lot of redundancy is already removed today when you run CSE.

I know CSE assume that, but then shouldn't we guard this at the lowering already? right now we allow arbitrary capture python runtime to be constant

One the other hand, I'm not sure if we really should push this to far (about checking SSAValue equivalence) - the gain does not seem to worth the cost not to say one day we will still move part of the compilation into low-level infrastructure (e.g MLIR or Julia)

Then I guess I am confused. What is this actually want address in this issue? It seems GVN can be achieved by composition the rules we already have (unless there is any we can't?) Or this is for performance consideration?

[kaihsin]

maybe related: #270 #267