-
Type:
Enhancement
-
Resolution: Unresolved
-
Priority:
P4
-
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
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
- relates to
-
JDK-8379125 C2: Control of rewired data in Range Check Elimination is not updated when further splitting a main loop leading to a segfault
-
- Open
-