|Compile-time arithmetics needed email@example.com (1994-01-05)|
|Re: Compile-time arithmetics needed firstname.lastname@example.org (1994-01-05)|
|Re: Compile-time arithmetics needed email@example.com (1994-01-10)|
|From:||firstname.lastname@example.org (Preston Briggs)|
|Organization:||Rice University, Houston|
|Date:||Wed, 5 Jan 1994 20:54:39 GMT|
email@example.com (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!
Return to the
Search the comp.compilers archives again.