Wed, 5 Jan 1994 20:54:39 GMT

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

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

Return to the
comp.compilers page.

Search the
comp.compilers archives again.