This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Teach isDeadPHICycle to look through multiple uses
Needs ReviewPublic

Authored by luke on Jan 25 2023, 8:06 AM.

Details

Reviewers
nikic
spatel
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

Diff Detail

Event Timeline

luke created this revision.Jan 25 2023, 8:06 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 25 2023, 8:06 AM
luke requested review of this revision.Jan 25 2023, 8:06 AM
Herald added a project: Restricted Project. · View Herald TranscriptJan 25 2023, 8:06 AM
luke added inline comments.Jan 25 2023, 8:10 AM
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

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

luke added a comment.Jan 25 2023, 9:01 AM

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?

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.

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 added a comment.Jan 25 2023, 9:35 AM

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 added inline comments.Jan 25 2023, 2:25 PM
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 updated this revision to Diff 492520.Jan 26 2023, 10:55 AM

Address comments

luke marked 3 inline comments as done.Jan 26 2023, 10:57 AM
luke added inline comments.
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 added a comment.Jan 26 2023, 1:36 PM

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 marked an inline comment as done.Jan 26 2023, 3:00 PM

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.