Unsigned integer comparison optimizations

#93 Open

Bitbucket cannot automatically merge this request.

The commits that make up this pull request have been removed.

Bitbucket cannot automatically merge this request due to conflicts.

Review the conflicts on the Overview tab. You can then either decline the request or merge it manually on your local system using the following commands:

hg update ad79cc0ce9a8
hg pull -r default https://bitbucket.org/mpavone/pypy
# Note: This will create a new head!
hg merge 9fd1c9e7f3fc
hg commit -m 'Merged in mpavone/pypy (pull request #93)'
  1. Michael Pavone

Unsigned integer comparisons now update/propagate integer bounds and can be optimized away based on integer bounds information.

Comments (2)

  1. Armin Rigo

    Hum, your code is fine, but I fear that it's pointing towards another issue: we have only "int_add" as the operation to add integers, and so far we assumed throughout intbounds.py that it's a non-overflowing addition of signed integers (and the same with "int_mul", "int_sub", etc). The problem is that for unsigned integers it carries on bogus intbounds, and now adding your code might actually expose that latent bug... Example:

    assume that the intbounds say that 1 <= i0 <= sys.maxint-1

    i1 = int_mul(i0, 4)

    now the intbounds will say 4 <= i1 (with no upper bound)

    i2 = uint_lt(i1, 4)

    So the optimizer will deduce that i2 == 0, which is probably not correct: if the int_mul was really an unsigned multiplication by 4 (i.e. a shift left by 2), and if i0 was ULONG_MAX / 4, then i1 == 0.

    The complete fix is probably to add uint_add, uint_mul, etc. as ResOperations.

  2. Hakan Ardo

    The behaviour of overflowing signed arithmetic is undefined in C, presumable to allow this kind of optimizations?

    A quick fix would be to check that both the flags has_lower and has_upper of v1.intbound and v2.intbound are True in the optimize_UINT_* methods. Similar to how we handle the shift operations. That'll of course render the optimization less useful though...