This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Make exact taken count calculation more optimistic
ClosedPublic

Authored by mkazantsev on Mar 20 2018, 3:46 AM.

Details

Summary

Currently, getExact fails if it sees two exit counts in different blocks. There is
no solid reason to do so, given that we only calculate exact non-taken count
for exiting blocks that dominate latch. Using this fact, we can simply take min
out of all exits of all blocks to get the exact taken count.

This patch makes the calculation more optimistic with enforcing our assumption
with asserts. It allows us to calculate exact backedge taken count in trivial loops
like

for (int i = 0; i < 100; i++) {
  if (i > 50) break;
  . . .
}

Diff Detail

Event Timeline

mkazantsev created this revision.Mar 20 2018, 3:46 AM
fhahn added a subscriber: fhahn.Mar 20 2018, 4:28 AM
fhahn added inline comments.
lib/Analysis/ScalarEvolution.cpp
6672

With exits you mean "exiting blocks", rather than "exit blocks", right? (http://lists.llvm.org/pipermail/llvm-dev/2017-July/115962.html)

Maybe it would be clearer to explicitly use "exiting blocks" instead of exits here (and throughout the patch) :)

mkazantsev added inline comments.Mar 20 2018, 4:38 AM
lib/Analysis/ScalarEvolution.cpp
6672

Sure, I will fix it. :)

6672

Actually I can do it as a separate NFC. This is not the only place where the term is used.

fhahn added inline comments.Mar 20 2018, 4:57 AM
lib/Analysis/ScalarEvolution.cpp
6672

Sounds good to me.

fhahn accepted this revision.Mar 22 2018, 11:07 AM
fhahn added a reviewer: fhahn.

LGTM, with clearing up the exiting/exit block thing.

Please wait a bit with committing, in case the other reviewers want to raise additional concerns

fhahn added inline comments.Mar 22 2018, 3:48 PM
lib/Analysis/ScalarEvolution.cpp
6657

Please also update the comment here, stating when multiple exits are OK.

fhahn added inline comments.Mar 22 2018, 4:27 PM
lib/Analysis/ScalarEvolution.cpp
6673

Another thing to double check. Are you sure we only compute exit counts when we have a single loop latch that dominates all exiting nodes? I had a quick look but could not find the place where we ensure that (computeBackedgeTakenCount states that the loop latch may be null). In that case we might miss a case when all exit counts are equal.

mkazantsev added inline comments.Mar 23 2018, 3:01 AM
lib/Analysis/ScalarEvolution.cpp
6657

Will do before commit.

6673

The latch should be dominated by all exiting blocks, yes. It follows from current implementation of computeBackedgeTakenCount . It currently has *very* strict limitations that in practice say that the exit should actually be the latch (its successors being the loop's header and its chain of single predecessors also leads to header), so this requirement exists but implicit. If you look at https://reviews.llvm.org/D44677, here I tried to explain that the current requirement set is actually noting but a small subset of all situations when all exits dominate the latch. And in this patch, this requirement replaces all odd logic and becomes explicit.

mkazantsev added inline comments.Mar 23 2018, 3:04 AM
lib/Analysis/ScalarEvolution.cpp
6673

Besides, single latch is a canonical form, and any multiple-latch loop can be easily converted to it (and LLVM does it).

fhahn added inline comments.Mar 23 2018, 3:11 AM
lib/Analysis/ScalarEvolution.cpp
6673

Right , thanks for making this clearer and more explicit in this patch and D44677 :)

This revision was not accepted when it landed; it landed in state Needs Review.Mar 27 2018, 12:35 AM
This revision was automatically updated to reflect the committed changes.
mkazantsev added inline comments.May 3 2018, 1:59 AM
llvm/trunk/lib/Analysis/ScalarEvolution.cpp
6675 ↗(On Diff #139893)

Actually I start thinking that this may be an over-conservative assert. Imagine the situation:

do { // Loop 1
  do { // Loop 2
     if (invariant_cond) exit
   } while (...)
} while(...)

If we unswitch Loop 2 by invariant condition, we end up with something like

do { // Loop 1
  if (invariant_cond) {
    do { // Loop 2
     } while (...)
   } else {
    do { // Loop 2 copy
     } while (...)
   }
} while(...)

Exits in copies of loop2 no longer dominate the latch of loop1. I didn't comprehend it from the very beginning, but this may be an issue.