[SCEV] Make exact taken count calculation more optimistic
authorMax Kazantsev <max.kazantsev@azul.com>
Tue, 27 Mar 2018 07:30:38 +0000 (07:30 +0000)
committerMax Kazantsev <max.kazantsev@azul.com>
Tue, 27 Mar 2018 07:30:38 +0000 (07:30 +0000)
commit7094c8deb2b2bc0a5a4b79f5a5cc195bf4e1d5ca
tree70c5cdcf3057d66d3a4425049b150a98ad16a87b
parent3ddeb33e0017209792e72b33dee1a0ba69b316f1
[SCEV] Make exact taken count calculation more optimistic

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;
    . . .
  }

Differential Revision: https://reviews.llvm.org/D44676
Reviewed By: fhahn

llvm-svn: 328611
llvm/include/llvm/Analysis/ScalarEvolution.h
llvm/lib/Analysis/ScalarEvolution.cpp
llvm/test/Analysis/ScalarEvolution/exact_iter_count.ll [new file with mode: 0644]
llvm/test/Analysis/ScalarEvolution/max-trip-count.ll
llvm/test/Analysis/ScalarEvolution/trip-count14.ll
llvm/test/Transforms/IndVarSimplify/loop_evaluate10.ll
llvm/test/Transforms/LoopSimplify/preserve-scev.ll