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.
Posted Date : 2006-09-06 17:56:47.0

N/A

Ensure widen value is correctly set, and allow narrowing if significant
progress is being made refining the type.
Posted Date : 2006-09-06 17:59:48.0