Re: Include language bindings? Re: Draft Standard Text, V02.1 - recognizing the same interval
The examples show some of the challenges compilers face. Skip this note if you're not interested in compiler innards.
Everything in this note describes how IBM's C, C++ and Fortran compilers work. Others may be similar or totally different.
Each constant, variable and _expression_ is treated as if copied into a temporary register. You can think of it as a compiler-generated variable representing the "canonical definition" or "formal identity" of the value. In a simpler case
pp = xx + yy - xx;
is internally translated into something equivalent to
__xx = xx;
__yy = yy;
_xx_plus_yy = __xx + __yy;
__xx = xx; // redundant so will be discarded
__xx_plus_yy_minus_xx = __xx + __yy - __xx;
pp = __xx_plus_yy_minus_xx;
Note both the "xx"s will be copied into the same temporary I called __xx. In this representation it's easy to see that each __xx is identical, and Common _expression_ elimination will eliminate all but the first "__xx = xx;". If you allowed reassociation and simplification you could easily transform it into
pp = yy;
That's both good and bad. The good is that it recognizes that multiple uses of "xx" are really the same value.
If you replace "xx" with the interval constant "[1,10]", then the same internal transformations will turn
pp = [1,10] + yy - [1,10];
into
__1_10 = [1,10];
__yy = yy;
_1_10_plus_yy = __1_10 + __yy;
__1_10xx = [1,10]; // redundant so will be discarded
__1_10_plus_yy_minus_1_10 = __1_10 + __yy - __1_10;
pp = __1_10_plus_yy_minus_1_10;
And now we have the bad. The two [1,10]s look the same to the compiler, but as I learned from this group last year they are separate intervals.
pp = [1,10] + yy - [1,10];
does NOT mean the same as
ss = [1,10];
pp = ss + yy - ss;
so can NOT be transformed into
pp = yy;
So to separate the good from the bad, the compiler has to treat variables and constants differently.
Similarly, if an interval was created by the function Interval, as in
pp = Interval(1,10) + yy - Interval(1,10);
then the compiler would have to treat function results differently from variables. It already distinguishes pure from impure functions, and this Interval would have to be treated as impure.
The second example
tt0 = c0;
tt1 = tt0*xx + c1;
tt2 = tt1*xx + c2;
tt3 = tt2*xx + c3;
tt4 = tt3*xx + c4;
pp = tt4*xx + c5;
introduces a new issue and problem - the handling would be different when optimizing from when not.
When not optimizing, there would be no recognition that the xx s are the same value. When optimizing, they likely would be, depending on whether the optimizer knows that tt1, tt2, tt3 and tt4 could or could not possibly be the same memory as xx. If they could be the same, then each assignment might change xx and the xx s are not necessarily identical. If tt1, tt2, tt3 and tt4 could not be xx, then the xx s are identical. If that's not clear, replace each tt# with a dereference of a pointer that might or might not point at xx.
The third example
tt[0] = c0;
for (i = 1; i < n; i++) tt[i] = tt[i-1]*xx + c[i];
pp = tt[n-1];
has two interesting aspects. The first is that when optimizing, the xx would usually be moved out of the loop, and all iterations would be using the same value. It would depend on whether it looked like something else in the loop might be able to change the value of xx. Without optimization xx would be left in the loop, and the values would not be considered the same.
Many but not all compilers have an optimization that recognizes a "recurrence" between tt[i] this iteration and tt[i-1] next iteration, and reuses the value. So depending on the optimization level and the code details, values like them might be recognized as being the same, or might not.
The other question is when this matters. I don't think it does in any of the 3 original examples, but it would in
pp = xx + yy - xx;
and
pp = [1,10] + yy - [1,10];
Other compilers may differ.
- Ian McIntosh IBM Canada Lab Compiler Back End Support and Development
Dan Zuras Intervals ---03/16/2010 12:55:17 PM---> From: "Nate Hayes" <nh@xxxxxxxxxxxxxxxxx> > To: "P1788" <stds-1788@xxxxxxxxxxxxxxxxx>
From: |
Dan Zuras Intervals <intervals08@xxxxxxxxxxxxxx> |
To: |
Ian McIntosh/Toronto/IBM@IBMCA |
Date: |
03/16/2010 12:55 PM |
Subject: |
Re: Include language bindings? Re: Draft Standard Text, V02.1 |
> From: "Nate Hayes" <nh@xxxxxxxxxxxxxxxxx>
> To: "P1788" <stds-1788@xxxxxxxxxxxxxxxxx>
> Subject: Re: Include language bindings? Re: Draft Standard Text, V02.1
> Date: Tue, 16 Mar 2010 10:04:24 -0500
>
> I think to study the algebraic properties of intervals and make sure these
> semantics are clearly delineated in the standard will be helpful along this
> direction. For example, if an implementation violates the algebraic
> properties, then it would be clear the implementation is non-conforming.
>
> Also, if some sorts of _expression_ rearrangement are allowed, this will
> particularly ensure various compiler optimizations by different vendors will
> be more consistent accross implementations.
>
> Nate
>
When Nate speaks of the algebraic properties of intervals
he is including issues peculiar to interval expressions
which have no analogy among real or floating-point
expressions.
Let me illustrate with 3 different ways of evaluating some
polynomial pp(xx):
pp = ((((c0*xx + c1)*xx + c2)*xx + c3)*xx + c4)*xx + c5;
tt0 = c0;
tt1 = tt0*xx + c1;
tt2 = tt1*xx + c2;
tt3 = tt2*xx + c3;
tt4 = tt3*xx + c4;
pp = tt4*xx + c5;
tt[0] = c0;
for (i = 1; i < n; i++) tt[i] = tt[i-1]*xx + c[i];
pp = tt[n-1];
All are exactly the same. If implemented in floating-point,
all would be implemented with exactly the same sequence of
floating-point operations. (Let's pass on the FMA issue for
now.) In a very real sense, all have the same 'meaning'.
However, as we discussed at length in the stds-1788-er
subgroup, the resulting interval would be unnecessarily wide
unless one recognises that each instance of the interval
variable 'xx' are the SAME variable. That is, all of the
instances co-vary rather than vary independently of one
another.
Nate calls this an 'algebraic' property of the _expression_.
And while this observation may be arrived at algebraically,
I believe it is a mistake to think of it in this way.
Co-variance is not an algebraic property. And the way we
must account for it is peculiar to interval expressions
apart from their algebraic properties.
(There are mathematical objects that deal with the issue of
co-variance in different ways. Probablity is one. The
mathematics of motion on continuous curved surfaces is
another. Intervals is different from both.)
Now, part of what Nate is trying to preserve here is the
very clever work he & others have done in looking at
expressions & algebraically reformulating them in a way
which minimizes the width of the resulting interval to
something more closely resembling the 'actual' variance
available in the _expression_. While this reformulation
is itself a reinterpretation of the _expression_ beyond that
which is written in the source, it is often essential to
obtain adequately narrow intervals.
Nate is right. We must have these optimizations available
if we are to present meaningful results.
But look at the difficulty the compiler faces in implementing
these things.
In the first _expression_, all that is needed is to recognise
that each instance of 'xx' is the same interval variable.
In the second _expression_, this observation must be extended
beyond each assignment. And in the third, it must be extended
in time through each iteration of the loop.
Further, if we are to have a standard which is reproducible
across all implementations, any modification of an _expression_
beyond that which is written in the source must ITSELF be
standard in a way that the programmer can predict. These
modifications (which often involve separating the positive
coefficients from the negative ones) must be either discoverable
at compile time or possibly reformulated on the fly.
At the time we had this discussion in the stds-1788-er subgroup,
I took a hard line & said that the default must be to use no
reinterpretation of the _expression_ beyond that which is written.
I may have erred in that position.
Still, I believe that the programmer must be able to predict
exactly how the expressions written into the source are to
be evaluated. So if we are to make 'algebraic' optimizations
they must be THEMSELVES standard & clearly spelled out in both
the 1788 document & the specification of the language itself.
I have insufficient compiler experience to know how much this
is asking of our target compilers. Others will have to fill
in with their expertise.
It may still be true that no reformulation of any kind is the
correct default. But Nate & others have convinced me that
these sorts of optimizations must be clearly spelled out in
our standard & offered to the programmer in some way.
Have you got your toes wet yet, folks?
You're still in the shallow end.
Wait until you have to dive into the matrix _expression_ pool.
That one can be intractably deep.
Exponentially so. :-)
Enjoy,
Dan