Re: A Level 2 query - X-X

[Ian McIntosh <ianm@xxxxxxxxxx>]

Skip this unless you care about whether SUB = X - X can be optimized.


For existing numeric data types, IBM's C, C++, Fortran and other compilers already optimize X-X into 0 in some cases:
 - For X being an integer, X-X is replaced with 0.
 - For X being floating point, if a compiler option is used saying the user doesn't care about NaNs and Infinities or that they're impossible, X-X is replaced with 0.; but otherwise it is left alone.
 - For X being complex, early in optimization while X-X is still represented as a Complex Subtract X-X can easily be replaced with (0.,0.) if the user doesn't care about NaNs and Infinities.

In most ways intervals are much like complex, so could easily be done IF the compiler front end describes them to the back end as a new "interval" type and the user guarantees that the endpoints can't be infinite.  The former isn't very likely and the latter is very unlikely.

There's also another problem for intervals, related to their semantics.  For floating point
X = 5.;
Y = 5.;
Z = X - Y;
after value propagation the optimizer sees
X = 5;
Y = 5;
Z = 5. - 5.;
and the last line can be optimized to
Z = 0.;

For intervals it would be OK to do the same for
SUB = X - X;
(except for infinite bounds) because X is identical to X, and for
X = [5., 10.];
Y = X;
Z = X - Y;
because the value Y represents is identical to X and none of the bounds is infinite, and for
U = [5., 10.];
X = U;
Y = U;
Z = X - Y;
because X and Y are always identical, but it would be wrong to do it for the similar looking
X = [5., 10.];
Y = [5., 10.];
Z = X - Y;
because even though X and Y are the same range neither is derived from the other or a common variable, and they might represent different values in their ranges that happen tpo have the same bounds.

Optimizers must be taught not to propagate values in the last case for intervals even if they would for other types.

If the optimizer doesn't have enough information to distinguish the last case from the earlier cases, then it can't optimize the early ones because it can't optimize the last.  If intervals are a native type the information might be available.  If the key question is whether the source is a literal or a variable and the transformation is done before any value propagation then it should be safe.  Generally though, if intervals are implemented as a C++/Java class or Fortran derived type or by a library instead of built into the compiler, then it's very unlikely the optimizer can always know when Z = 0. would be safe.

- Ian McIntosh          IBM Canada Lab         Compiler Back End Support and Development


Ned Nedialkov ---06/25/2013 05:35:13 PM--->  > I assume that these kinds of things exist in other interval

From:	Ned Nedialkov <nedialk@xxxxxxxxxxx>
To:	Ian McIntosh/Toronto/IBM@IBMCA
Date:	06/25/2013 05:35 PM
Subject:	Re: A Level 2 query

---

> 
> I assume that these kinds of things exist in other interval
> library designs where people have made some effort to
> extract single-use expressions, are willing to consider
> differentiation / max / min extraction, etc.  From the
> perspective of the language/compiler-for-intervals
> design,  I think the routine
> 
> SUB(X)
> SUB=X-X
> RETURN
> 
> should return [0,0] for finite intervals. I'm unsure about
> what is best if X is not-an-interval. (etc)
> 
> Anyway, my question is still -- if the compiler works hard to come
> up with a tighter enclosure (by doing SUE simplification, polynomial
> root finding, etc) is that going to violate the standard, or is it
> irrelevant to the standard being supra-library,  and nothing to
> worry about :)

My feeling is that it will be a long time before compilers would do this,
so I would not consider what they could do. 

As a side question/comment. 
During my PhD in the late 90s, I was looking for a subroutine that, given 
polynomial coefficients that are intervals, produces tight interval containing
the range of this polynomial over some interval. I could not find such, 
although there were articles on the topic. I am wondering if such an implementation
exists now. 

Ned
> 
> RJF
> 
> 
> 
>> 
>> If so, then the standard should make it very clear that interval
>> arguments of functions are to be evaluated differently from regular
>> interval variables.
>> 
>> Cheers,
>> 
>> Bill
>> 
>> On 6/20/13 7:27 AM, Richard Fateman wrote:
>>> I am unclear as to whether you are excluding from consideration as
>>> standard-conforming the following compiler
>>> "optimization":
>>> 
>>> let  y :=   ...some explicit polynomial P in the interval variable x.
>>> 
>>> 
>>> The compiler recognizes P as a polynomial, computes (at compile time)
>>> locations and values at
>>> its relative maxima and minima, and at run-time uses this information
>>> to
>>> compute inf(y)  and sup(y) on the interval x  entirely without
>>> dependency slop.
>>> And perhaps with great speed compared to evaluating P.
>>> 
>>> RJF
>>> 
>>> 
>>> On 6/20/2013 6:05 AM, John Pryce wrote:
>>>> Ian, Jürgen, P1788
>>>> 
>>>> What I get from these replies is that the T -> T operation *should*
>>>> be mandatory. Ian's comments are important but they apply to
>>>> expressions. Those are a language issue and we IMO
>>>> (a) *should not* make requirements about _expression_-evaluation
>>>> (beyond containment);
>>>> (b) *should* make recommendations on the lines Ian proposes.
>>>> Actually, thinking about it, I'm less sure about (a).
>>>> 
>>>> 
>>> <snip>
>>> 
>> 
>>