Page MenuHomePhabricator

PR32632 Add a case to remove loop compare
AbandonedPublic

Authored by evstupac on Jun 12 2017, 12:40 PM.

Details

Reviewers
sanjoy
efriedma
Summary

The patch add a case to eliminate comparisons like:

for (i = 84; i > 1; i--)
 for (j = i; j < i; j++)

which exit at first loop iteration.

Build and lit tests are passed.
No significant performance changes.
spec2000 - build same all
spec2006 - build same all, but 400 and 433 (with less than 1% gain).

Diff Detail

Repository
rL LLVM

Event Timeline

evstupac created this revision.Jun 12 2017, 12:40 PM
efriedma requested changes to this revision.Jun 12 2017, 1:05 PM

Scalar evolution can already analyze the given testcase on trunk. Output of "opt -analyze -scalar-evolution":

Determining loop execution counts for: @foo
Loop %for.cond4: backedge-taken count is 6
Loop %for.cond4: max backedge-taken count is 6
Loop %for.cond4: Predicated backedge-taken count is 6
 Predicates:

Loop %for.cond4: Trip multiple is 7
Loop %for.cond1: backedge-taken count is 0
Loop %for.cond1: max backedge-taken count is 0
Loop %for.cond1: Predicated backedge-taken count is 0
 Predicates:

Loop %for.cond1: Trip multiple is 1
Loop %for.cond: backedge-taken count is 83
Loop %for.cond: max backedge-taken count is 83
Loop %for.cond: Predicated backedge-taken count is 83
 Predicates:

Loop %for.cond: Trip multiple is 84
This revision now requires changes to proceed.Jun 12 2017, 1:05 PM

Scalar evolution can already analyze the given testcase on trunk. Output of "opt -analyze -scalar-evolution":

Right. The reason I'm trying to apply this patch is that the case could be resolved earlier.
It is possible to understand that the predicate is constant here. Why not to do this at "isKnownPredicate"?
There are other cases, that could be caught by BECount - should we remove them from "isKnownPredicate"?

I'm not convinced it makes sense to invest any effort into loops with a backedge-taken count of zero. Yes, maybe we simplify the exit condition slightly earlier, but does that actually do us any good in practice?

There are other cases, that could be caught by BECount - should we remove them from "isKnownPredicate"?

I don't think there's any other code in isKnownPredicate that specifically checks for exit conditions? Not all comparisons against an AddRec are checks which exit the loop.

evstupac abandoned this revision.May 2 2018, 12:27 PM