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.