This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Handle zero stride correctly in howManyLessThans
ClosedPublic

Authored by reames on Jul 13 2021, 11:19 AM.

Details

Summary

This is split from D105216, but the code is hoisted much earlier into the path where we can actually get a zero stride flowing through. Some fairly simple proofs handle the cases which show up in practice. The only test changes are the cases where we really do need a non-zero divider to produce the right result.

Diff Detail

Event Timeline

reames created this revision.Jul 13 2021, 11:19 AM
reames requested review of this revision.Jul 13 2021, 11:19 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 13 2021, 11:19 AM
efriedma added inline comments.Jul 13 2021, 12:02 PM
llvm/lib/Analysis/ScalarEvolution.cpp
11675

We make exactly the same isLoopEntryGuardedByCond() call later; can we avoid calling it twice?

reames added inline comments.Jul 13 2021, 12:21 PM
llvm/lib/Analysis/ScalarEvolution.cpp
11675

I assume you're concerned about compile time? If so, I'd prefer to land the simple change (this one), and then revisit if needed. I would not be surprised if the later one changed form anyways.

efriedma accepted this revision.Jul 13 2021, 12:24 PM

LGTM

llvm/lib/Analysis/ScalarEvolution.cpp
11675

As a practical matter, I'm not really concerned about compile-time here, I guess; we should be hitting wouldZeroStrideBeUB() very rarely in real code. Just feels a little weird. I'm okay landing this as-is for now, and we can consider refactoring once we're confident we're actually performing all the checks we need.

This revision is now accepted and ready to land.Jul 13 2021, 12:24 PM
This revision was landed with ongoing or failed builds.Jul 13 2021, 1:31 PM
This revision was automatically updated to reflect the committed changes.

I've bisected a crash to this change

$ opt -passes='default<O3>' reduced.ll
opt: ../../llvm/lib/Analysis/ScalarEvolution.cpp:10521: bool llvm::ScalarEvolution::isLoopEntryGuardedByCond(const llvm::Loop *, ICmpInst::Predica
te, const llvm::SCEV *, const llvm::SCEV *): Assertion `isAvailableAtLoopEntry(RHS, L) && "RHS is not available at Loop Entry"' failed.

Maybe we should look at threading the actual branch through to howManyLessThans, so we can use isKnownPredicateAt() or something like that. In the meantime, I'll recommit with an appropriate isLoopInvariant() check.

Artur, Eli, thanks to each of you!