# Re: Compile-time arithmetics needed

## preston@dawn.cs.rice.edu (Preston Briggs)Wed, 5 Jan 1994 20:54:39 GMT

From comp.compilers

Related articles
Compile-time arithmetics needed sepp@cs.tu-berlin.de (1994-01-05)
Re: Compile-time arithmetics needed preston@dawn.cs.rice.edu (1994-01-05)
Re: Compile-time arithmetics needed glew@ichips.intel.com (1994-01-10)
| List of all articles for this month |

 Newsgroups: comp.compilers From: preston@dawn.cs.rice.edu (Preston Briggs) Keywords: arithmetic Organization: Rice University, Houston References: 94-01-014 Date: Wed, 5 Jan 1994 20:54:39 GMT

sepp@cs.tu-berlin.de (Maximilian Spring) writes:

>I am looking for algorithms for efficient basic arithmetics (+, -, *, /
>for real & integers and modulus for integers) for constant folding, where
>range overflows are detectable.

First off, you want to be careful about folding real arithmetic; this is
an easy way to get into precision trouble. I limit myself to cases where
I can prove that the operands (or operand) is equal to some integer. That
is, I won't fold

3.14 * 1.23

but I will fold

float y = (float) 1;
float x = y * z;

There's actually a whole class of these possiblities (at least for
Fortran) that might not ordinarily come to mind: sin(0), sign(0, x),
sqrt(0), sqrt(1), log(0), log10(1), log10(10), ..., plus the various
methods of rounding and truncating. Basically, you look for special cases
where an integer-valued input gives an integer-valued output.

For integer arithmetic, the tedious cases are addition and subtraction.
Multiplication, division, and modulus are much simpler and can be handled
by checking the result. For example, if we're trying to compute X * Y and
we know they're both constants, we can compute

temp1 = X * Y; -- assuming there's no overflow checking here!
temp2 = temp1 / X;
if (temp2 != Y)
then we've got an overflow

My approach, when an overflow is detected, is to simply leave the
operation unfolded. That way, it can be detected at runtime _if_ it
actually is executed. And if the target machine has a different integer
precision or doesn't bother to detect integer overflow, then the optimizer
won't have changed the result.

To handle addition and subtraction, you need to check the signs of the
operands and the results. For example, if you add two positive operands
and get a negative result, you've had an overflow.

I seem to recall that there's a further tricky case, but I can't get at my
code to check. So, be careful and check those boundary conditions!

Preston Briggs
--

Post a followup to this message