Value range tracing

> I'm wondering if people bother with value range tracing. That is,
> keeping track of the possible range of variables at each point in the
> program. For example:


Yes indeed. We are compiling true high-level languages like Fortran90
and Algol68 and many of their constructs require substantial low-level
code. Tracking simple algebraic assertions allows a number of
optimisations to the strategic code-generation: particularly the
removal of array bound or pointer nil checks (or raising them at
compile-time), and in many cases a lot of the scaffolding which is
necessary to ensure the language semantics (such as the properties of
integer division which both F90 and A68 unlike C, completely define -
knowing the divisor is positive can save a comparison and branch on
most architectures which provide hardware division). The same
benefits may acrue with C code obfuscated via macros.


There is a limit to how much algebraic baggage a compiler is prepared
to carry around and we restrict the size of range limit expressions
(but not to constants which would be useful with our principal
languages). Tracking more other assertions such as power of two,
odd/even, exactly divisible by n, etc., would be useful in many
special cases, but not enough IMO to merit their tracking in general.


Regards,
----------------------------------------------------------------------
Dave Lloyd Email: Dave@occl-cam.demon.co.uk
Oxford and Cambridge Compilers Ltd Phone: (44) 1223 572074
55 Brampton Rd, Cambridge CB1 3HJ, UK
--

Return to the comp.compilers page.
Search the comp.compilers archives again.