The EliminateDuplicatePHINodes function used in simplifycfg pass does not handle cyclic phis. This patch adds detection for such phis and can be constrained using the deduplicate-phi-max-depth option.
I like the idea here, but the implementation approach is somewhat iffy. This is only going to work in the "naive" implementation -- I don't think the hash-based implementation can be extended to support this. So it won't work if there are many phis. The implementation approach is also quite inefficient: We're performing pairwise, recursive comparisons of all phis.
It should be possible to do this more generally and efficiently (something based on equivalence classes with optimistic assumption), but that would require processing all phis in the function together, not just those in a single block.
A substantial limitation here is that this only works on pure phi graphs, and for example won't be able to deduplicate typical induction variables where there is something like an add %phi, 1 in between. But at that point we're getting into phi-aware GVN, which is ... tricky.
I'm generally open to having this simple approach, as long as it can be made essentially free in terms of compile-time impact.
Can do something like this can drop the MatchingPhis.count() calls below.
This won't work, and violates the DenseMap contract, because it will report two phis as equal that have a different hash.
Use a lit test please, in some pass that uses these utilities.
The implementation approach is also quite inefficient: We're performing pairwise, recursive comparisons of all phis.
Recursion is of course not ideal, but the comparison has an upper limit. Would you suggest trying to make this into an iterative approach?
That is a great point. I will look into a different approach.
I wanted to use a lit test, but this function is called only in the -simplifycfg pass, but that pass does way too many optimizations. Using a unit test I can easily test that exactly this feature works and also it allows me to create a smaller test, where I don't have to worry about simplifycfg removing some parts.