C2: Generalize loop predication

XMLWordPrintable

    • Type: Enhancement
    • Resolution: Unresolved
    • Priority: P4
    • tbd
    • Affects Version/s: None
    • Component/s: hotspot

      Currently, loop predication only works when the exit condition is unsigned greater than, and the right hand side is a non-negative value. We can generalize it as follow:

      For signed comparisons:
      1. (iv * scale + offset) s</<= range
        can be infered from:
        + ConvI2L(min_iv) * ConvI2L(scale) + ConvI2L(offset) s>= min_jint
        + ConvI2L(max_iv) * ConvI2L(scale) + ConvI2L(offset) s>= min_jint
        + ConvI2L(min_iv) * ConvI2L(scale) + ConvI2L(offset) s</<= ConvI2L(range)
        + ConvI2L(max_iv) * ConvI2L(scale) + ConvI2L(offset) s</<= ConvI2L(range)
        Proof:
        The 4 equalities imply that:
        + ConvI2L(iv) * ConvI2L(scale) + ConvI2L(offset) s>= min_jint
        + ConvI2L(iv) * ConvI2L(scale) + ConvI2L(offset) s</<= ConvI2L(range) s<= max_jint
        For all jlong x such that min_jint s<= x s<= max_jint, we have x == ConvI2L(ConvL2I(x)), with
        x = ConvI2L(iv) * ConvI2L(scale) + ConvI2L(offset), we have:
        + ConvI2L(ConvL2I(ConvI2L(iv) * ConvI2L(scale) + ConvI2L(offset))) s</<= ConvI2L(range)
        Since ConvL2I(x * y) == ConvL2I(x) * ConvL2I(y) and ConvL2I(x + y) == ConvL2I(x) + ConvL2I(y),
        and ConvL2I(ConvI2L(t)) == t, we have:
        + ConvI2L(iv * scale + offset) s</<= ConvI2L(range)
        which means:
        + (iv * scale + offset) s</<= range (Q.E.D)

      2. (iv * scale + offset) s>/>= range
        similarly, can be inferred from:
        + ConvI2L(min_iv) * ConvI2L(scale) + ConvI2L(offset) s<= max_jint
        + ConvI2L(max_iv) * ConvI2L(scale) + ConvI2L(offset) s<= max_jint
        + ConvI2L(min_iv) * ConvI2L(scale) + ConvI2L(offset) s>/>= ConvI2L(range)
        + ConvI2L(max_iv) * ConvI2L(scale) + ConvI2L(offset) s>/>= ConvI2L(range)

      For unsigned comparisons:
      1. (iv * scale + offset) u</<= range
        can be inferred from (ConvUI2L(x) is just AndL(ConvI2L(x), max_juint)):
        + ConvI2L(min_iv) * ConvI2L(scale) + ConvI2L(offset) s>= 0
        + ConvI2L(max_iv) * ConvI2L(scale) + ConvI2L(offset) s>= 0
        + ConvI2L(min_iv) * ConvI2L(scale) + ConvI2L(offset) s</<= ConvUI2L(range)
        + ConvI2L(max_iv) * ConvI2L(scale) + ConvI2L(offset) s</<= ConvUI2L(range)
        Proof:
        The 4 inequalities imply that:
        + ConvI2L(iv) * ConvI2L(scale) + ConvI2L(offset) s>= 0
        + ConvI2L(iv) * ConvI2L(scale) + ConvI2L(offset) s</<= ConvUI2L(range) s<= max_juint
        For all jlong x such that 0 s<= x s<= max_juint, we have x == ConvUI2L(ConvL2I(x)), with
        x = ConvI2L(iv) * ConvI2L(scale) + ConvI2L(offset), we have:
        + ConvUI2L(ConvL2I(ConvI2L(iv) * ConvI2L(scale) + ConvI2L(offset))) s>= 0
        + ConvUI2L(ConvL2I(ConvI2L(iv) * ConvI2L(scale) + ConvI2L(offset))) s</<= ConvUI2L(range)
        Since ConvL2I(x * y) == ConvL2I(x) * ConvL2I(y) and ConvL2I(x + y) == ConvL2I(x) + ConvL2I(y),
        and ConvL2I(ConvI2L(t)) == t, we have:
        + ConvUI2L(iv * scale + offset) s>= 0
        + ConvUI2L(iv * scale + offset) s</<= ConvUI2L(range)
        which means:
        + ConvUI2L(iv * scale + offset) u</<= ConvUI2L(range)
        or:
        + (iv * scale + offset) u</<= range (Q.E.D)

      2. (iv * scale + offset) u>/>= range
        similarly, can be inferred from:
        + ConvI2L(min_iv) * ConvI2L(scale) + ConvI2L(offset) s<= max_juint
        + ConvI2L(max_iv) * ConvI2L(scale) + ConvI2L(offset) s<= max_juint
        + ConvI2L(min_iv) * ConvI2L(scale) + ConvI2L(offset) s>/>= ConvUI2L(range)
        + ConvI2L(max_iv) * ConvI2L(scale) + ConvI2L(offset) s>/>= ConvUI2L(range)

      Furthermore, since scale and loop direction are known, it is adequate to perform 2 comparisons.
      For example, when the check we want to removed is (iv * scale + offset) s> range, and scale > 0,
      we know that:
      + ConvI2L(min_iv) * ConvI2L(scale) + ConvI2L(offset) s< ConvI2L(max_iv) * ConvI2L(scale) + ConvI2L(offset)
      This means that we only need to perform 2 comparisons:
      + ConvI2L(min_iv) * ConvI2L(scale) + ConvI2L(offset) s> ConvI2L(range)
      + ConvI2L(max_iv) * ConvI2L(scale) + ConvI2L(offset) s<= max_juint

            Assignee:
            Quan Anh Mai
            Reporter:
            Quan Anh Mai
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

              Created:
              Updated: