Re: Compile-time arithmetics needed

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
--

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