invariants

wclodius@aol.com (Wclodius) writes:
>[...] compiler writers should recognize that the
>presence of relational operators in the language implies that the
>language permits reasoning about invariants in the code and should
>preserve the pertinent invariants. I want to know that if the
>arithmetic is guaranteed to be finite then I can do the following
>
> IF (X > Y) THEN
> do something with X > Y
> ELSE
> do something with X <= Y
> ENDIF
>
>[...]
>
>I will not expect magic from compiler writers, i.e., the recognition
>of an expression in all contexts where it can be made to appear
>through the mathematically proper invocation of commutativity,
>associativity, and distributivity, but I do want simple invocations of
>invariants between variables to be recognized.


I can recognize such things, in floating point or integer, and take
advantage of them, but it can be quite expensive in compile time,
depending on how much I want to do with them.


Typically, compilers that do dependence analysis (for vectorization,
parallization, cache management, etc) have to do this sort of thing,
but in a fairly limited way. For more extensive forms of this
analysis, see, for instance, the various papers by Pugh and his
students, along with their bibliographies.


    title="Eliminating False Data Dependences using the {Omega} Test",
    author="William Pugh and David Wonnacott",
    pages="140--151",
    journal=sigplan,
    year=1992,
    month=jul,
    volume=27,
    number=7,
    note=pldi92


    author="William Pugh and David Wonnacott",
    title="Static Analysis of Upper and Lower Bounds on Dependences
and Parallelism",
    pages="1248--1278",
    journal=toplas,
    year=1994,
    month=july,
    volume=16,
    number=4


    author="William Pugh",
    title="Counting Solutions to Presburger Formulas: How and Why",
    pages="121--134",
    journal=sigplan,
    year=1994,
    month=jun,
    volume=29,
    number=6,
    note=pldi94


Preston Briggs
[I think he was referring to invariants he can use in hand analyses of
numerical properties, rather than invariants that an optimizer might
use. For the former, the compiler doesn't have to understand them, it
just has to avoid gratuitously breaking them. -John]

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