[LoopUnroll] Use the upper bound of the loop trip count to fullly unroll a loop
authorHaicheng Wu <haicheng@codeaurora.org>
Wed, 12 Oct 2016 20:24:32 +0000 (20:24 +0000)
committerHaicheng Wu <haicheng@codeaurora.org>
Wed, 12 Oct 2016 20:24:32 +0000 (20:24 +0000)
commit6cac34fd41e8c961811d09c21063c10f442b2ad5
treeeb84c5c2acdffa2693881c014d69b0471494a1e9
parentc6667075b3474cc9e0519e99843df8ebb92d6b30
[LoopUnroll] Use the upper bound of the loop trip count to fullly unroll a loop

This patch tries to fully unroll loops having break statement like this

for (int i = 0; i < 8; i++) {
    if (a[i] == value) {
        found = true;
        break;
    }
}

GCC can fully unroll such loops, but currently LLVM cannot because LLVM only
supports loops having exact constant trip counts.

The upper bound of the trip count can be obtained from calling
ScalarEvolution::getMaxBackedgeTakenCount(). Part of the patch is the
refactoring work in SCEV to prevent duplicating code.

The feature of using the upper bound is enabled under the same circumstance
when runtime unrolling is enabled since both are used to unroll loops without
knowing the exact constant trip count.

Differential Revision: https://reviews.llvm.org/D24790

llvm-svn: 284044
llvm/include/llvm/Analysis/ScalarEvolution.h
llvm/include/llvm/Analysis/TargetTransformInfo.h
llvm/include/llvm/CodeGen/BasicTTIImpl.h
llvm/include/llvm/Transforms/Scalar.h
llvm/include/llvm/Transforms/Scalar/LoopUnrollPass.h
llvm/include/llvm/Transforms/Utils/UnrollLoop.h
llvm/lib/Analysis/ScalarEvolution.cpp
llvm/lib/Transforms/Scalar/LoopUnrollPass.cpp
llvm/lib/Transforms/Utils/LoopUnroll.cpp
llvm/test/Transforms/LoopUnroll/AArch64/full-unroll-trip-count-upper-bound.ll [new file with mode: 0644]