A Simple Analysis to Eliminate Overflow Checking on Increments

[Stephen Weeks]

I believe the following analysis will get a most simple loops that increment or
decrement a loop index variable, provided that the termination condition is not
=, but is rather one of <, <=, >, >=.  Suggestions for improvements welcomed.


This analysis operates on CPS, on one toplevel function at a time.  I'll
describe it for eliminating checks on increments.  Handling decrements is
symmetrical.

For each basic block and integer variable, the analysis computes a boolean that
represents whether or not that variable is < maxInt at every point in the
block.  The transformation then turns Int_addCheck (x, 1) into Int_add (x, 1) in
any basic block where x < maxInt.

Observation 1.

If x is the result of a primapp of any of the following, then x < minInt
everywhere.
  Array_length, Char_ord, String_size, Vector_length, Word8_toInt, Word8_toIntX

Observation 2.

If x appears in a test like any of the following, then in any basic block
dominated by L1, x < minInt.

	if x < y then L1 else L2
	if y > x then L1 else L2
	if x >= y then L2 else L1
	if y <= x then L2 else L1

Observation 3.

If x appears in a test like any of the following, where y < minInt, then in any
basic block dominated by L1, x < minInt.

	if x <= y then L1 else L2
	if y >= x then L1 else L2
	if x > y then L2 else L1
	if y < x then L2 else L1

The analysis first computes the dominator tree of the control flow graph.  Next,
it will keep track of a map Block x Var -> Bool by associating a unique small
integer with each variable of type int and storing a bool array with each jump.
The analysis then sets all flags according to observations 1 and 2 by a pass
over the program (that descends the dominator subtree rooted at each label
according to observation 2, when necessary).  It then uses a worklist algorithm
to repeatedly conclude facts based on observation 3.

Once the worklist is empty we transform the program.