Page MenuHomePhabricator

[SCEV] Use loop guard info when computing the max BE taken count in howFarToZero.
Changes PlannedPublic

Authored by fhahn on Sep 4 2019, 8:14 AM.

Details

Summary

For some expressions, we can use information from loop guards when
we are looking for a maximum. This patch applies information from
loop guards to the expression used to compute the maximum backedge
taken count in howFarToZero. It currently replaces an unknown
expression X with UMin(X, Y), if the loop is guarded by
X ult Y.

This patch is minimal in what conditions it applies, and there
are a few TODOs to generalize.

This partly addresses PR40961. We will also need an update to
LV to address it completely.

Event Timeline

fhahn created this revision.Sep 4 2019, 8:14 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 4 2019, 8:14 AM

Instead of writing a C++ unittest, you should be able to use "opt -analyze -scalar-evolution" to test this.

Not sure I like the approach; rewriting the SCEV to a more complicated expression seems like it's stacking complexity. But it might be the least code overall, I guess.

fhahn added a comment.Sep 4 2019, 1:22 PM

Instead of writing a C++ unittest, you should be able to use "opt -analyze -scalar-evolution" to test this.

Sure, I'll do that. The current version of the unit test only tests stuff covered by -analyze -scalar-evolution.

Not sure I like the approach; rewriting the SCEV to a more complicated expression seems like it's stacking complexity. But it might be the least code overall, I guess.

Yep, the re-writing the expression was the least invasive change. But I would be happy to change the implementation to use additional conditions differently. To cover the motivating case for the patch, it would be enough to collect the additional conditions, pass them to getRangeRef and use them there. But I think the additional conditions could be helpful in the various reasoning functions as well. Currently we can pass one additional condition to most reasoning functions, but here it would be helpful to pass multiple conditions. I am happy with either direction, please let me know what you prefer :)

In terms of general API, I don't think we want to expose "applyLoopGuards"; the SCEV transform proposed here isn't really useful outside of trying to find the minimum or maximum, as far as I can tell. Which min/max expressions we want to form depends on whether we're computing a "max" or a "min". And restricting the API so the point in the CFG we're querying has to be a loop header doesn't seem helpful; other places might care about values after a loop etc.

In terms of the implementation, this composes well, in a sense: it annotates the relevant SCEV expressions with the relevant conditions, then uses the general implementation that ignores control flow. But I'm not sure how it scales for larger SCEV expressions; keeping a map on the side seems like it would have more predictable performance.

I don't really have a general vision for what the range computation implementation should look like in the future: what sources of information are practical to use? What overall data structure do we use to integrate them?

fhahn added a comment.Sep 6 2019, 12:58 PM

In terms of general API, I don't think we want to expose "applyLoopGuards"; the SCEV transform proposed here isn't really useful outside of trying to find the minimum or maximum, as far as I can tell. Which min/max expressions we want to form depends on whether we're computing a "max" or a "min". And restricting the API so the point in the CFG we're querying has to be a loop header doesn't seem helpful; other places might care about values after a loop etc.

In terms of the implementation, this composes well, in a sense: it annotates the relevant SCEV expressions with the relevant conditions, then uses the general implementation that ignores control flow. But I'm not sure how it scales for larger SCEV expressions; keeping a map on the side seems like it would have more predictable performance.

Yeah, duplicating a whole expression just because we want to attach additional range information could lead to poor performance for large expressions. I'll look into the map approach.

I don't really have a general vision for what the range computation implementation should look like in the future: what sources of information are practical to use? What overall data structure do we use to integrate them?

Do you mean in general or in for SCEV?

Do you mean in general or in for SCEV?

Well, I guess there's a question in general, but here I'm more concerned specifically about SCEV: what other analysis can it use, what sort of data structures can we use for caching. But maybe I'm looking too many steps ahead; I don't want to get in the way of an incremental improvement.

SCEV already has support for isLoopEntryGuardedByCond which should be a super set of the added code. Have you explored why the distance expression isn't be canonicalized at construction?

(There are some circularity issues between exit counts and scev canonical forms, so that might be your issue. Or it might be something easy to fix. We can always hope.)

fhahn planned changes to this revision.Sep 25 2019, 2:18 PM

SCEV already has support for isLoopEntryGuardedByCond which should be a super set of the added code.

Agreed, I think the final version of the patch should definitely share the guard discovery logic with isLoopEntryGuardedByCond.

Have you explored why the distance expression isn't be canonicalized at construction?

Do you mean why the information from the loop guard is not included in the distance expression when we create it?
IIUC, the distance expression here is the subtraction of RHS and LHS of the exit condition. As Eli indicated, including information from the guards in the expressions for the operands of the condition might increase the complexity, without much gain, besides using it to get more precise upper bounds on ranges. Do you think there would be additional benefits for including information from the guards in the distance expression, beside better range information? AFAIK, some of the reasoning methods themselves try to rewrite/simplify expressions based on information from loop guards and we might be able to skip some of those rewrites.