RFR: 8315066: Add unsigned bounds and known bits to TypeInt/Long [v4]

[Jasmine Karthikeyan]

On Mon, 22 Jan 2024 19:58:50 GMT, Quan Anh Mai <qamai at openjdk.org> wrote:

>> Hi,
>> 
>> This patch adds unsigned bounds and known bits constraints to TypeInt and TypeLong. This opens more transformation opportunities in an elegant manner as well as helps avoid some ad-hoc rules in Hotspot.
>> 
>> In general, a TypeInt/Long represents a set of values x that satisfies: x s>= lo && x s<= hi && x u>= ulo && x u<= uhi && (x & zeros) == 0 && (~x & ones) == 0. These constraints are not independent, e.g. an int that lies in [0, 3] in signed domain must also lie in [0, 3] in unsigned domain and have all bits but the last 2 being unset. As a result, we must normalize the constraints (tighten the constraints so that they are optimal) before constructing a TypeInt/Long instance.
>> 
>> This is extracted from #15440 , node value transformations are left for later PRs. I have also added unit tests to verify the soundness of constraint normalization.
>> 
>> Please kindly review, thanks a lot.
>> 
>> Testing
>> 
>> - [x] GHA
>> - [x] Linux x64, tier 1-4
>
> Quan Anh Mai has updated the pull request incrementally with one additional commit since the last revision:
> 
>   fix release build

I took a quick look through the patch, this is really impressive :)

Early last year I had [an attempt at the same idea](https://github.com/openjdk/jdk/compare/master...jaskarth:jdk:bit-tracking) (extremely rough patch, sorry), where I went with the approach of using a 2-bit value for each bit position to represent `0`, `1`, `BOTTOM`, and `TOP`. My general idea was to create a boolean lattice so that the meet() and dual() operations were easier to implement, before I realized how difficult reasoning about multiple constraints in the meet and dual operations was. I think your idea of marking the dual makes more sense and is cleaner, especially with how the constraints interact.

src/hotspot/share/opto/type.cpp line 1642:

> 1640: 
> 1641: const Type* TypeInt::widen(const Type* old, const Type* limit) const {
> 1642:   assert(!_dual, "");

I think it'd be helpful for these `!_dual` asserts to have a message, even if it's something simple like `dual not expected here`

src/hotspot/share/opto/type.hpp line 617:

> 615:   bool is_con(jint i) const { return is_con() && _lo == i; }
> 616:   jint get_con() const { assert(is_con(), "");  return _lo; }
> 617:   bool contains(jint i) const;

I think the `contains` and `properly_contains` functions could use some documentation as well to explain under what conditions they return true or false. For `contains(TypeInt* t)`, would it return the same as `t->higher_equal(this)`? If so, that might simplify the implementation of it.

-------------

PR Review: https://git.openjdk.org/jdk/pull/17508#pullrequestreview-1839638653
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1463870704
PR Review Comment: https://git.openjdk.org/jdk/pull/17508#discussion_r1463814326