[InstCombine] Teach isDeadPHICycle to look through multiple uses

[luke]

Summary

Instead of only detecting trivial cycles which must be a PHI with a single use that's a PHI, which in turn has a single use of the first PHI, generalize it to catch more complex cycles. This means making it look through all of its uses, as well as looking through arbitrary side-effect free instructions.

The motivation behind this is to enable InstCombiner to remove larger dead PHI cycles in one iteration, to prevent cascading iterations in some pathological cases with lots of dead PHI cycles.

Supersedes D142293
Fixes https://github.com/llvm/llvm-project/issues/50564

[luke]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

1443

This is now covered by isDeadPHICycle

llvm/test/Transforms/InstCombine/fmul.ll

396–400

Looks like a dead cycle to me. I presume it's now detected because it isDeadPHICycle can look through arbitrary instructions now

llvm/test/Transforms/InstCombine/pr27703.ll

16

Otherwise a dead phi cycle is detected here and the phi is removed

[luismarques]

It might be a good idea to see the compile-time impact of this with https://llvm-compile-time-tracker.com?

[luke]

In D142551#4080233, @luismarques wrote:

It might be a good idea to see the compile-time impact of this with https://llvm-compile-time-tracker.com?

Good idea, I don't have access to a remote on it though. Would someone be able to post a branch with this patch on it?

[luismarques]

In D142551#4080298, @luke wrote:

Good idea, I don't have access to a remote on it though. Would someone be able to post a branch with this patch on it?

I think I can do it.

[luismarques]

In D142551#4080298, @luke wrote:

Good idea, I don't have access to a remote on it though. Would someone be able to post a branch with this patch on it?

https://llvm-compile-time-tracker.com/compare.php?from=f84d3dd0fd4ec3be52488e4c29baebb0077b04d4&to=b79315a7071612621ac543cd7595cb487c437a64&stat=instructions:u

[luke]

In D142551#4080424, @luismarques wrote:

In D142551#4080298, @luke wrote:

Good idea, I don't have access to a remote on it though. Would someone be able to post a branch with this patch on it?

https://llvm-compile-time-tracker.com/compare.php?from=f84d3dd0fd4ec3be52488e4c29baebb0077b04d4&to=b79315a7071612621ac543cd7595cb487c437a64&stat=instructions:u

Thanks. That seems like a non-negligible increase. Would it be worthwhile then limiting the search depth for non-phi node instructions to maybe 1 or 2 at a time?

[nikic]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

975–976

This code should also run for non-phis, with PotentiallyDeadPHIs -> PotentiallyDeadInsts. We want to count non-phi instructions towards the limit as well. I expect this is why you're seeing such a large compile time impact, because as written we only limit the number of visited phis, not the number of visited instructions.

1016

Can cast<> here, all users of instructions are instructions.

1016

Returning false for I->use_empty() doesn't really make sense. I suspect that what you're trying to work around here is the something like br doesn't have side effects, but also can't just be removed. The correct predicate to check here is wouldInstructionBeTriviallyDead.

[luke]

Address comments

[luke]

llvm/lib/Transforms/InstCombine/InstCombinePHI.cpp

1016

That makes much more sense, thanks.
I've updated the diff but now isDeadPHICycle is really just isDeadCycle, which makes me wonder if there's another, more generic place for this.

[nikic]

Huh, this made compile-time impact even worse: https://llvm-compile-time-tracker.com/compare.php?from=051bcd4f310bbf97781b9ccc95ae2754224a75b2&to=bd36ced96eabd9b4e028778d058dcb56bb6d86ba&stat=instructions

Apparently wouldInstructionBeTriviallyDead is that expensive. Using !isa<PHINode>(I) && !isa<BinaryOperator>(I) && !isa<GetElementPtrInst>(I)) in keeping with the existing code brings it down to this: http://llvm-compile-time-tracker.com/compare.php?from=051bcd4f310bbf97781b9ccc95ae2754224a75b2&to=abae5ca4dc70078006e4e26095215a732be1f330&stat=instructions%3Au

This is still not as free as I had hoped :/

[luke]

In D142551#4083916, @nikic wrote:

Huh, this made compile-time impact even worse: https://llvm-compile-time-tracker.com/compare.php?from=051bcd4f310bbf97781b9ccc95ae2754224a75b2&to=bd36ced96eabd9b4e028778d058dcb56bb6d86ba&stat=instructions

Apparently wouldInstructionBeTriviallyDead is that expensive. Using !isa<PHINode>(I) && !isa<BinaryOperator>(I) && !isa<GetElementPtrInst>(I)) in keeping with the existing code brings it down to this: http://llvm-compile-time-tracker.com/compare.php?from=051bcd4f310bbf97781b9ccc95ae2754224a75b2&to=abae5ca4dc70078006e4e26095215a732be1f330&stat=instructions%3Au

This is still not as free as I had hoped :/

We could also try limiting it to phi nodes with one use. There’s a test case in there for a phi node with 2 uses, but the actual bug that this aims to fix only has single use phi nodes.