Page MenuHomePhabricator

[SCEV] Correct handling of recurrences matched in partially unreachable code (try 2)
AbandonedPublic

Authored by reames on Tue, Apr 6, 7:27 PM.

Details

Summary

(This is, I think, entirely functionally equivalent to https://reviews.llvm.org/D99929. I just preferred this way of framing the fix. The key difference here is focusing on the connection between the loop trip count and the recurrence. I do think we have a recurrence, it's just a trivially one where only the first iteration runs.)

As shown by PR49856 and the reopened test case on PR49768, my first attempt at accounting for unreachable blocks wasn't quite complete. The new approach simply takes what was previously the assert, turns it into a bail out, and adds a comment explaining why it can happen.

Diff Detail

Event Timeline

reames created this revision.Tue, Apr 6, 7:27 PM
reames requested review of this revision.Tue, Apr 6, 7:27 PM
Herald added a project: Restricted Project. · View Herald TranscriptTue, Apr 6, 7:27 PM
mkazantsev added inline comments.Tue, Apr 6, 9:25 PM
llvm/lib/Analysis/ScalarEvolution.cpp
5675

Do we have a guarantee of having no loops in unreachable code?

uabelho added a subscriber: uabelho.Tue, Apr 6, 9:42 PM
reames added a comment.Wed, Apr 7, 8:51 PM

JFYI, planning on pursuing this as a style cleanup over Max's landed change, but distracted due to other events. Will likely be a couple days before I get back to this.

llvm/lib/Analysis/ScalarEvolution.cpp
5675

See LoopInfoBase<>::analyze specififically the line:
DomTree.isReachableFromEntry(Backedge))

Note that the verify routine also checks against a newly constructed LI, so any failure to update should be caught in a expensive asserts run.

mkazantsev added inline comments.Sun, Apr 11, 9:40 PM
llvm/lib/Analysis/ScalarEvolution.cpp
5675

But expensive verification runs between the passes. It is still possible that some pass makes a loop unreachable in the middle of the transform and does not immediately destroy the loop while continuing to use SCEV.

I am still strongly leaning towards not relying on such things, even if they might be correct. It's far from obvious and far from simple.

reames added inline comments.Tue, Apr 13, 3:03 PM
llvm/lib/Analysis/ScalarEvolution.cpp
5675

Passes that rely on running with partially corrupt analyzes are buggy. We should find and fix them.

mkazantsev added inline comments.Mon, Apr 19, 8:35 AM
llvm/lib/Analysis/ScalarEvolution.cpp
5675

It is not a corrupt analysis. It is clearly stated that LI for unreachable blocks is undefined. It may have loops anywhere.

reames abandoned this revision.Tue, Apr 20, 10:44 AM

I prototyped a couple of alternatives to this, and the resulting interface in matchSimpleRecurrence is ugly and error prone. Based on a survey of the existing users, SCEV is the only place which cares about the mismatch between LoopInfo and reachability.

I'm strongly of the opinion that the loop info approach sketched here is the right one, but given this seems to have stumbled into a much larger issue (with, IMO, incorrect docs and missing asserts) I'm going to set this aside. I already have several major changes in flight and don't have the bandwidth for any more.

llvm/lib/Analysis/ScalarEvolution.cpp
5675

IMO, this is a case where the docs are simply wrong.

The (lack of an) invariant your arguing for here would make it hard to implement any useful analysis based on loops. If we redefined dominance in unreachable code, maybe we could make this work, but with our current domtree semantics not having loopinfo match that is a serious problem.