JDK-6467870 : Fixes to monotonically narrow or widen types during igvn
  • Type: Bug
  • Component: hotspot
  • Sub-Component: compiler
  • Affected Version: 5.0
  • Priority: P3
  • Status: Resolved
  • Resolution: Fixed
  • OS: solaris_9
  • CPU: sparc
  • Submitted: 2006-09-06
  • Updated: 2010-04-02
  • Resolved: 2006-11-14
The Version table provides details related to the release that this issue/RFE will be addressed.

Unresolved : Release in which this issue/RFE will be addressed.
Resolved: Release in which this issue/RFE has been resolved.
Fixed : Release in which this issue/RFE has been fixed. The release containing this fix may be available for download as an Early Access Release or a General Availability Release.

To download the current JDK release, click here.
JDK 6 JDK 7 Other
6u4Fixed 7Fixed hs10Fixed
Related Reports
Relates :  
For pessimistic passes (eg. global value numbering), the types
must monotonically narrow. For optimistic  passes (eg. conditionally
constant propagation), the types must monotonically widen.

It is possible to get into a "death march" in either type of pass,
where the types are continually moving but it will take 2**31 or
more steps to converge.  This doesn't happen on most normal loops.

Here is an example of a deadly loop for an optimistic pass, along
with a partial trace of inferred types:
   x = phi(0,x'); L: x' = x+1; if (x' >= 0) goto L;
   0                 1                join([0..max], 1)
   [0..1]            [1..2]           join([0..max], [1..2])
   [0..2]            [1..3]           join([0..max], [1..3])
     ... ... ...
   [0..max]          [min]u[1..max]   join([0..max], [min..max])
   [0..max] ==> fixpoint
We would have proven, the hard way, that the iteration space is all
non-negative ints, with the loop terminating due to 32-bit overflow.

Here is the corresponding example for a pessimistic pass:
   x = phi(0,x'); L: x' = x-1; if (x' >= 0) goto L;
   int               int              join([0..max], int)
   [0..max]          [-1..max-1]      join([0..max], [-1..max-1])
   [0..max-1]        [-1..max-2]      join([0..max], [-1..max-2])
     ... ... ...
   [0..1]            [-1..0]          join([0..max], [-1..0])
   0                 -1               join([0..max], -1)
   0 == fixpoint
We would have proven, the hard way, that the iteration space is {0}.
(Usually, other optimizations will make the "if (x >= 0)" fold up
before we get into trouble.  But not always.)

Replace uses of Type::join in Node::Value methods because any join has
the potential to kill widen bits.

SUGGESTED FIX /net/prt-archiver.sfbay/data/archived_workspaces/main/c2_baseline/2006/20060918134617.nips.igvnfixpt/

EVALUATION Ensure widen value is correctly set, and allow narrowing if significant progress is being made refining the type.