Track Integer bounds in AbstractInterpretation

[oscardssmith]

Right now, Julia is in an awkward place with @inbounds. Effect analysis really doesn't like @inbounds because indexing OOB is inconsistent, but AbstractInterpretation doesn't propagate Integer bounds at all.

I think the best solution to this would be to add an IntegerRange{T<:BitInteger} type to Core.Compiler that tracks ranges of integers through abstract interpretation. Specifically, it would need to support:

• comparison (<,<=,>,>=,==,!=) with Const
• basic arithmatic (+,-,*,div) both with Const and optionally between 2 IntegerRanges All arithmetic operations would use checked operations and on overflow would widen to T
• basic bit operations & with Const clamps the upper bit of the range to the largest number with the highest bit set in the const, xor(x,x)=Const(0)

All other operations would just widen to T

With these rules, we would be able to remove most un-necessary boundchecks in code that doesn't have loops. Getting this analysis to work well in the presence of loops is harder, and I'm not sure what would need to be done to prove convergence of bounds. Anyone have ideas?

[vchuravy]

LLVM uses a technique called scalar evolution (SCEV) based on the algebra of chaines of recurrences. Some references here https://github.com/JuliaLang/llvm-project/blob/046f90173567535397c97b2d00406c93ee4bc890/llvm/lib/Analysis/ScalarEvolution.cpp#L39-L56

There is a lot of previous work on using abstract interpretation for array bounds as an example see https://hal.univ-reunion.fr/hal-01921666/document.