This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Teach isLoopBackedgeGuardedByCond to exploit trip counts.
ClosedPublic

Authored by sanjoy on Sep 17 2015, 4:03 PM.

Details

Summary

If the trip count of a specific backedge is N, then we know that
backedge is effectively guarded by the condition {0,+,1} u< N. This
change teaches SCEV to use this condition to prove things in
isLoopBackedgeGuardedByCond.

Depends on D12948
Depends on D12949

Diff Detail

Repository
rL LLVM

Event Timeline

sanjoy updated this revision to Diff 35047.Sep 17 2015, 4:03 PM
sanjoy retitled this revision from to [SCEV] Teach isLoopBackedgeGuardedByCond to exploit trip counts..
sanjoy updated this object.
sanjoy added reviewers: atrick, reames, hfinkel, majnemer.
sanjoy added a subscriber: llvm-commits.
sanjoy updated this revision to Diff 35133.Sep 18 2015, 1:57 PM
  • rebase on top of changes to D12948
hfinkel added inline comments.Sep 23 2015, 1:05 AM
lib/Analysis/ScalarEvolution.cpp
7008 ↗(On Diff #35133)

already computed => already-computed

7010 ↗(On Diff #35133)

It seems like we should add a comment in ScalarEvolution.h somewhere that isLoopBackedgeGuardedByCond will potentially-return more-accurate answers if you compute the look trip count first.

This seems unfortunate, but I suppose we can't force the trip-count computation here because we might infinitely recurse?

7019 ↗(On Diff #35133)

Don't we know that SCEV::FlagNW | SCEV::FlagNUW here? Otherwise, it would not really be a trip count, would it?

sanjoy added inline comments.Sep 23 2015, 12:20 PM
lib/Analysis/ScalarEvolution.cpp
7010 ↗(On Diff #35133)

This seems unfortunate, but I suppose we can't force the trip-count
computation here because we might infinitely recurse?

My motivation was to avoid burning excessive compile time computing
loop trip counts we'll never use. But on second thought, this sounds
like a silly optimization -- even calling getSCEV will sometimes end
up causing the loop's trip count to be computed, so micro-optimizing
it away here does not make sense. I'll change this to a direct call
to getBackedgeTakenInfo.

Btw, I don't think we'll end up with infinite recursion here. If
getBackedgeTakenInfo ends up recursively calling this code, the
recursive call to getBackedgeTakenInfo should return "could not
compute" as the backedge trip for Latch, so we won't make the second
recursive call to isImpliedCond.

7019 ↗(On Diff #35133)

Yes, will fix.

sanjoy updated this revision to Diff 35577.Sep 23 2015, 5:18 PM
  • address hal's review. Making the loop counter <nw> and <nuw> changed the output of an existing test case (zext-wrap.ll) -- an induction variable is now reported as <nw> when it wasn't before. This inference is correct, so I didn't actually bother trying to verify further.
hfinkel accepted this revision.Sep 24 2015, 1:27 AM
hfinkel edited edge metadata.

LGTM.

This revision is now accepted and ready to land.Sep 24 2015, 1:27 AM
This revision was automatically updated to reflect the committed changes.