Induction Variable Analysis and Array Bounds Check Elimination

I added an Induction Variable Analysis (IVA) pass to the compiler. It runs after the arithmetic optimizer which converts all instructions that substract a constant value from a value into additions with a negative constant. The IVA pass then searches for PHI instructions in tails of the tree that point update a context variable with an addition that draws its value directly from the same context variable. To deal with stacked additions, i.e. an a[i++] followed by a b[i++], the arithmetic optimizer accumulates chains of additions and substractions into a single addition. A context slot is only considered an induction variable if its increased (or decreased) by a constant amount along every trace in the tree. However, the value by which the variable changes does not have to be constant. Variables that are increasing along every trace (or remain unchanged which corresponds to an increase by zero) are flagged monotonic non-decreasing. Variables that always decrease (or stay the same) along every trace are flagged monotonic non-increasing.

The result of the IVA is used by the guard elimination pass to hoist guards out of the loop that check whether an induction variable is always smaller than a constant (i.e. a not less than zero index check for arrays). Since we know for induction variables that they are either monotonic non-increasing or monotonic non-decreasing, we can hoist such guards out of the loop and merly check them once in the prolog. This eliminates 50% of the guards associated with reading from or writing to arrays. The other bounds check (in case of an increasing index the upper bounds check) will be eliminated using guard condition coalescing.