On Wed, 2 Sep 2026 09:15:07 GMT, Quan Anh Mai <[email protected]> wrote:
>> Hi, >> >> I was reminded of this forgotten PR when reviewing a counted loop >> transformation PR. The important point is that it is easier and more >> efficient to compute the trip count of a counted loop using unsigned >> division. Currently, for int counted loops, trip count is computed by >> extending the loop parameters to long and doing a signed long division. This >> cannot be applied to long counted loop. As a result, as a precondition for >> long counted loop predication, we need to be able to efficiently transform >> an unsigned division by constant. >> >> For more information, please refer to #9947 . >> >> Testing: >> >> - [x] tier1-4,hs-comp-stress >> >> Please take a look and leave your review, thanks a lot. >> >> --------- >> - [x] I confirm that I make this contribution in accordance with the >> [OpenJDK Interim AI Policy](https://openjdk.org/legal/ai). > > Quan Anh Mai has updated the pull request with a new target base due to a > merge or a rebase. The pull request now contains 103 commits: > > - Merge branch 'master' into unsignedDiv > - Merge branch 'master' into unsignedDiv > - Merge branch 'master' into unsignedDiv > - Fix comments, remove dead code > - Merge branch 'master' into unsignedDiv > - Various fixes > - Fix IntegerDivValueTests > - Fix merge conflicts > - Merge branch 'master' into unsignedDiv > - Merge branch 'master' into unsignedDiv > - ... and 93 more: https://git.openjdk.org/jdk/compare/6da8ba2d...c0ff6d16 Looks fine to me! It's nice to read math, but acsii math... a bit less. I have a lot of nits, tho... sorry for the spam! src/hotspot/share/opto/divconstants.cpp line 32: > 30: // division by constant into a multiply/shift series. > 31: // > 32: // (1) Theory: Nit: do you mean "Theorem"? I think it goes better in the Theorem/Proof pair, no? src/hotspot/share/opto/divconstants.cpp line 78: > 76: // This implies floor(x / d) = floor(x * c / m) for v + 1 <= x <= v + d - > 1 > 77: // > 78: // Combining all the cases gives us the conclusion. It is correct, but I think it is worth explaining why that covers the whole range. I'd rather phrase `v + 1 <= x <= v + d - 1` as simply a lower bound, making the partition clear since the upper bound plays no role in splitting the range for `x`. And inside this case, I'd argue that the upper bound. Same in the `(b)` case. src/hotspot/share/opto/divconstants.cpp line 105: > 103: // > 104: // Combining all the cases gives us the conclusion. > 105: // It's really fun, I would have not skipped or detailed the same steps at all! src/hotspot/share/opto/divconstants.cpp line 108: > 106: // (3) Discussion: > 107: // > 108: // Let x be v, v - d + 1, -v, -v + d - 1, it can be seen that these > bounds are indeed optimal Nit: I think "tight" is more idiomatic for a bound. src/hotspot/share/opto/divconstants.cpp line 131: > 129: template <class T> > 130: void magic_divide_constants(T d, T N_neg, T N_pos, juint min_s, T& c, > bool& c_ovf, juint& s) { > 131: static_assert(std::is_unsigned<T>::value, "calculations must be done > in the unsigned domain"); Suggestion: static_assert(std::is_unsigned_v<T>, "calculations must be done in the unsigned domain"); Nit, but that should work, right? src/hotspot/share/opto/divnode.cpp line 99: > 97: } > 98: > 99: // magic_divide_constants in divconstants.cpp calculates the constant c, s Maybe my english is failing, but shouldn't it be "the constants"? I don't see why it shouldn't be a plural. src/hotspot/share/opto/divnode.cpp line 102: > 100: // such that division(x / d) = floor(x * c / 2**s) + (x < 0 ? 1 : 0) for > every integer x in > 101: // the input range. The functions in this file try to derive from the > formula in real > 102: // arithmetic to arrive at a formula in int/long arithmetic. More > details can be found in When you say "real arithmetic", you mean "arithmetic on mathematical integers", not "arithmetic on real numbers" (as in \mathbb{R}), right? src/hotspot/share/opto/divnode.cpp line 120: > 118: juint max_pos = dti->_hi > 0 ? juint(dti->_hi) : 0; > 119: if (min_neg < d && max_pos < d) { > 120: return new ConINode(TypeInt::ZERO); I suggest `phase->zerocon(T_INT)` or `phase->intcon(0)`. src/hotspot/share/opto/divnode.cpp line 151: > 149: // Divide-by-power-of-2 can be made into a shift, but you have to > do > 150: // more math for the rounding. You need to add 0 for positive > 151: // numbers, and "i-1" for negative numbers. Example: i=4, so the Can we take this opportunity to fix this comment? I don't think `i` is introduced before and if it is, I can't find it, so it wouldn't hurt to repeat it. I remember I found it in the while and was already irritated by it. src/hotspot/share/opto/divnode.cpp line 199: > 197: // q = (x * c) >> s + (x < 0 ? 1 : 0) = (x * c) >> s - (x >> (W - 1)) > 198: constexpr int N = 32; > 199: Node* addend1 = phase->transform(new RShiftINode(dividend, > phase->intcon(N - 1))); It's a bit awkward the thing noted W in the comment above is called `N` as a variable. I think what you have been calling `N` before was the upper bound of the domain. I think it would be consistent if you rename this variable `W`. src/hotspot/share/opto/divnode.cpp line 216: > 214: > 215: if (max_pos < divisor) { > 216: return new ConINode(TypeInt::ZERO); Same as above. src/hotspot/share/opto/divnode.cpp line 245: > 243: > 244: // Java shifts are modular so we need this special case > 245: constexpr int N = 32; `W` again? src/hotspot/share/opto/divnode.cpp line 247: > 245: constexpr int N = 32; > 246: if (shift_const == N * 2) { > 247: return new ConINode(TypeInt::ZERO); `zerocon` src/hotspot/share/opto/divnode.cpp line 389: > 387: // Divide-by-power-of-2 can be made into a shift, but you have to > do > 388: // more math for the rounding. You need to add 0 for positive > 389: // numbers, and "i-1" for negative numbers. Example: i=4, so the Same thing about `i`. src/hotspot/share/opto/divnode.cpp line 394: > 392: // (-2+3)>>2 becomes 0, etc. > 393: > 394: constexpr int N = 64; `W`? src/hotspot/share/opto/divnode.cpp line 423: > 421: addend0 = phase->transform(new RShiftLNode(mul, > phase->intcon(shift_const))); > 422: } else { > 423: constexpr int N = 64; `W` again? src/hotspot/share/opto/divnode.cpp line 497: > 495: // Java shifts are modular so we need this special case > 496: if (shift_const == N * 2) { > 497: return new ConLNode(TypeLong::ZERO); `phase->zerocon(T_LONG)` src/hotspot/share/opto/divnode.cpp line 510: > 508: } > 509: > 510: if ((divisor & 1) == 0) { Nit: what do you think about `divisor % 2 == 0`? I think it's the more arithmetically relevant property. And I trust the C compiler to optimize it. src/hotspot/share/opto/divnode.cpp line 899: > 897: } > 898: > 899: // Otherwise we give up all hope > Lasciate ogne speranza, voi ch'intrate But doesn't that apply to about 90% of C2? (and is it on purpose you kept the comment here but not in the `I` version? Not sure it is very useful, but it doesn't hurt to remind that's just the ultimate fallback) src/hotspot/share/opto/divnode.cpp line 1372: > 1370: > //============================================================================= > 1371: > //------------------------------Idealize--------------------------------------- > 1372: Node *ModLNode::Ideal(PhaseGVN *phase, bool can_reshape) { Maybe fix the style here and just under (and remove the ruler above the prototype), since you've touched the method quite a bit. src/hotspot/share/opto/divnode.hpp line 225: > 223: virtual const Type* Value(PhaseGVN* phase) const; > 224: virtual const Type* bottom_type() const { return TypeInt::INT; } > 225: virtual uint ideal_reg() const { return Op_RegI; } Why reordering that? Not that I think it was better before... test/hotspot/gtest/opto/test_constant_division.cpp line 116: > 114: return ((l * U(c)) >> s) + (l < 0 ? U(1) : U(0)); > 115: } else { > 116: if (sizeof(U) > sizeof(UT) * 2) { Can that be a `if constexpr`? ------------- Marked as reviewed by mchevalier (Reviewer). PR Review: https://git.openjdk.org/jdk/pull/31033#pullrequestreview-5151468173 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3966054161 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3966384031 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3967757561 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3966328136 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3966664555 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3967816035 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3968068854 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3967843449 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3967874551 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3967947219 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3967953967 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3967961893 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3967961157 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3968033889 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3968049304 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3968058152 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3968103526 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3968415357 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3968567942 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3968613523 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3966699039 PR Review Comment: https://git.openjdk.org/jdk/pull/31033#discussion_r3968723780
