[Mono-devel-list] Over/under-flow in abcrem (suggestions needed)

[Massimiliano Mantione]

Hi all,
I'm working on bug 71062, and as I am at it I wanted to make abcrem
safe against over/under-flow of integer values.

To see what I mean, look at the attached program, and execute it
with and without the -O=abcrem flag.
You'll note that the program behavior is different :-(

Please do not point that the program is lame, and that just testing
if an unsigned int is >=0 is *asking* for an exception... I know,
this is a test program, and the test fails.

Short explanation: abcrem is convinced of two facts:
- In all "signed" tests, the index *always* grows.
- In all "unsigned" tests, the index *always* decreases.
abcrem guesses this looking at the operations performed on the
index variable: in the 1st case, only an addition of a positive
constant, and in the 2nd case the opposite (well, abcrem is much
more complex than that, but you get the idea).

What really happens is that, due to over/under-flow, the actual
index value has a different behavior.

Now the abcrem code (in my tree) has knowledge of all the sizes
and "nature" (signed/unsigned) of all local variables, and I
wanted to use this knowledge to solve the problem.

>From now, I'll call "+k" a sum with a positive constant or a
difference with a negative constant, and "-k" the reverse.
The idea is that abcrem should only handle operations that are
"safe"in the sense that they do not produce over/under-flow.
By "handle" I mean "try to guess the effect, and use it when
deciding to remove a check".

I would do the following:
- For signed values, handle both +k and -k operations, but only
  if k is "small". See later for the definition of "small".
- For unsigned values, handle only +k operations (the idea is
  that a +k operation cannot harm, because we know the index is
  growing, while a -k operation can *always* reach 0 and go the
  other way round, undetected, no matter how k is small).

The problem is, what does "small" mean?

For integers of size 1 or 2 bytes, IMO small means "1".
This because abcrem removes the check if and only if there is
already a branch that checks that the index does not pass the
array length. If we go on with increments of "1", we can be
(reasonably?) sure that we will be stopped by that branch before
the index becomes negative.

If, on the other hand, the index is a proper int, it is much
harder to make it overflow (in my test program I had to use a
very large constant).
In general, the constant must be "> (MAX_INT - length)" for an
overflow to be possible.
Which value would you find reasonable to use in this case as a
"guard" (so that if k < value, the operation is handled)?
I wanted to stay with a very low one (like 4).

Comments appreciated...

Ciao,
  Massi

-------------- next part --------------
A non-text attachment was scrubbed...
Name: overflow.cs
Type: text/x-csharp
Size: 3605 bytes
Desc: not available
Url : http://lists.ximian.com/pipermail/mono-devel-list/attachments/20050112/ad6536ba/attachment.bin