Add a new pass "inductive range check elimination"
authorSanjoy Das <sanjoy@playingwithpointers.com>
Fri, 16 Jan 2015 01:03:22 +0000 (01:03 +0000)
committerSanjoy Das <sanjoy@playingwithpointers.com>
Fri, 16 Jan 2015 01:03:22 +0000 (01:03 +0000)
commita1837a342d183b8e796c3f5a52cf0477d7b479fd
treea6ef78435a05af4c658773dcced6a840d5a330a8
parentdb56013cd13442bb194a62cdd6c57ef69c9708bc
Add a new pass "inductive range check elimination"

IRCE eliminates range checks of the form

  0 <= A * I + B < Length

by splitting a loop's iteration space into three segments in a way
that the check is completely redundant in the middle segment.  As an
example, IRCE will convert

  len = < known positive >
  for (i = 0; i < n; i++) {
    if (0 <= i && i < len) {
      do_something();
    } else {
      throw_out_of_bounds();
    }
  }

to

  len = < known positive >
  limit = smin(n, len)
  // no first segment
  for (i = 0; i < limit; i++) {
    if (0 <= i && i < len) { // this check is fully redundant
      do_something();
    } else {
      throw_out_of_bounds();
    }
  }
  for (i = limit; i < n; i++) {
    if (0 <= i && i < len) {
      do_something();
    } else {
      throw_out_of_bounds();
    }
  }

IRCE can deal with multiple range checks in the same loop (it takes
the intersection of the ranges that will make each of them redundant
individually).

Currently IRCE does not do any profitability analysis.  That is a
TODO.

Please note that the status of this pass is *experimental*, and it is
not part of any default pass pipeline.  Having said that, I will love
to get feedback and general input from people interested in trying
this out.

This pass was originally r226201.  It was reverted because it used C++
features not supported by MSVC 2012.

Differential Revision: http://reviews.llvm.org/D6693

llvm-svn: 226238
llvm/include/llvm/InitializePasses.h
llvm/include/llvm/LinkAllPasses.h
llvm/include/llvm/Transforms/Scalar.h
llvm/lib/Transforms/Scalar/CMakeLists.txt
llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp [new file with mode: 0644]
llvm/lib/Transforms/Scalar/Scalar.cpp
llvm/test/Transforms/IRCE/multiple-access-no-preloop.ll [new file with mode: 0644]
llvm/test/Transforms/IRCE/single-access-no-preloop.ll [new file with mode: 0644]
llvm/test/Transforms/IRCE/single-access-with-preloop.ll [new file with mode: 0644]
llvm/test/Transforms/IRCE/unhandled.ll [new file with mode: 0644]
llvm/test/Transforms/IRCE/with-parent-loops.ll [new file with mode: 0644]