Optimize signed integer comparison

[John Rose]

On Jul 18, 2014, at 10:58 AM, Vladimir Kozlov <vladimir.kozlov at oracle.com> wrote:

> What you described is exactly why 8043284 was filed.
> 
> If we only looking for BoolNode 'eq'/'ne' checks then returning TypeInt:CC_LT or CC_GT should give correct 'ne' result. Right? See BoolTest::cc2logical().

It is risky to return an incorrect value for a node based on what other nodes we think might be testing it, since if some other node picks up the incorrect value, it might make a wrong decision with it.  A couple of scenarios where "some other node" might pop up:  1. During parsing when we haven't hooked everything together yet (because we haven't parsed every bytecode yet).  2. If a third node gets replaced by the incorrectly-valued node (because of something like value numbering).

It would be better to transform the nodes that are testing for the NE condition.  The NE condition (which we can't directly express in types) is produced by a Cmp node.  The node which could use an NE condition is a Bool node (testing eq or ne).  If we can make a transformation fold up both the Bool and the Cmp, then we can eliminate the unreached code, right?  So the optimization is a little less local than we want.

Alternatively, and more powerfully, we could add bitfield tracking to the type system.  Graal has this (based on type equations I sent them).  If we were to do both range and bitfield tracking of the {-1,0,1} range of Cmp operations, we could express the type NE using the type assertion "(cmp&-2)!=0" which can be coded as "downMask!=0".

— John

> Vladimir
> 
> On 6/24/14 4:03 AM, Tobias Hartmann wrote:
>> Hi,
>> 
>> it would be nice if someone could have a look at this. While working at
>> JDK-8043284 [1] I noticed the following problem (see attached example
>> Unreachable.java):
>> 
>> The method test(..) takes a char c, casts it to int and adds INT_MAX to
>> it. If the result is equal to CHAR_MAX the method shouldNotReachHere(..)
>> is executed. But no matter what value c has, shouldNotReachHere(...) is
>> never executed because after the addition the result is either MAX_INT
>> or overflows and has a value between INT_MIN and INT_MIN + CHAR_MAX - 1.
>> 
>> The problem is that the C2 compiler does not detect this unreachable
>> code. The C2 type system merges the two possible integer ranges
>> [INT_MIN] and [INT_MIN + CHAR_MAX -1] into the general [INT_MIN,
>> INT_MAX] range. The CmpINode is then unable to detect the inequality and
>> returns the TypeInt::CC condition code which we cannot optimize.
>> 
>> To fix this we can check in CmpINode::Value(..) if the result of the
>> AddINode overflows and if so compare the two possible ranges with the
>> target value (very similar to what Vladimir did for [2]). If both ranges
>> are unequal we would return an unequal condition code and translate it
>> to a boolean value in BoolNode::Value(..). This would lead to removal of
>> all unreachable nodes in the graph.
>> 
>> However, the problem with this solution is that we currently do not have
>> an unequal type (we only have LT, GT, EQ, LE, GE) and adding one seems
>> to be difficult because the CC integer range [-1, 1] is already used
>> (see type.cpp line 297). I wonder why we don't have an own type for the
>> condition codes but use TypeInt.
>> 
>> Because my example is quite artificial, I did some testing with Octane
>> and it looks like as if this happens quite often. I therefore think we
>> should fix it.
>> 
>> What do you think?
>> 
>> Thanks,
>> Tobias
>> 
>> [1] https://bugs.openjdk.java.net/browse/JDK-8043284
>> [2] https://bugs.openjdk.java.net/browse/JDK-8042786