invariants (Preston Briggs)
1 Oct 1998 00:57:38 -0400

          From comp.compilers

Related articles
Re: inlining + optimization = nuisance bugs (1998-09-29)
invariants (1998-10-01)
| List of all articles for this month |

From: (Preston Briggs)
Newsgroups: comp.compilers
Date: 1 Oct 1998 00:57:38 -0400
Organization: Compilers Central
References: 98-09-162
Keywords: arithmetic (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
> do something with X <= Y
>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",

    author="William Pugh and David Wonnacott",
    title="Static Analysis of Upper and Lower Bounds on Dependences
and Parallelism",

    author="William Pugh",
    title="Counting Solutions to Presburger Formulas: How and Why",

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]

Post a followup to this message

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