Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8325151

Eliminate range checks using induction variable range data

XMLWordPrintable

    • Icon: Enhancement Enhancement
    • Resolution: Unresolved
    • Icon: P4 P4
    • tbd
    • 23
    • hotspot
    • generic
    • generic

      For a simple case:

      ```
      for (int i = 0; i < arr.length; ++i) {
         blackhole(arr[i]);
      }
      ```

      C2 generates code that looks like

      ```
      if (arr == null) { trap() }
      if (arr.length <= 0) { return }
      if (arr.length - 1 >= arr.length) { trap() }
      if (arr.length <= 0) { trap() }
      for (int i = 0; i < arr.length; ++i) {
        blackhole(arr[i]);
      }
      ```

      The last two if-checks are generated by Loop Predication. It should be unnecessary. We know that 0 <= i < arr.length. We should not need any bounds checks at all.

      In general, when we have a counted loop L and induction variable V, V is in [L->init_trip(), L->exact_limit()) when stride is positive, or in (L->exact_limit(), L->init_trip] when stride is negative. We can narrow the integer range of the induction variable and see if GVN can optimize the bounds check before loop predication.

      Alternatively, we can let loop predication hoist the checks and add optimizations to fold them. `arr.length - 1 >= arr.length` can be folded because we know `arr.length >= 0`. `arr.length <= 0` can be folded base on an equivalent dominating if-check (I'm surprised this does not get optimized already).

            jcao Joshua Cao
            jcao Joshua Cao
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

              Created:
              Updated: