United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-6467870 Fixes to monotonically narrow or widen types during igvn
JDK-6467870 : Fixes to monotonically narrow or widen types during igvn

Details
Type:
Bug
Submit Date:
2006-09-06
Status:
Resolved
Updated Date:
2010-04-02
Project Name:
JDK
Resolved Date:
2006-11-14
Component:
hotspot
OS:
solaris_9
Sub-Component:
compiler
CPU:
sparc
Priority:
P3
Resolution:
Fixed
Affected Versions:
5.0
Fixed Versions:
hs10 (b03)

Related Reports
Backport:
Backport:
Relates:

Sub Tasks

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
EVALUATION

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

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



Hardware and Software, Engineered to Work Together