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 :  
Description
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.

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

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