Pull requests

#93 Open
Repository
mpavone
Branch
default
Repository
pypy
Branch
default

Unsigned integer comparison optimizations

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 default
hg pull -r default https://bitbucket.org/mpavone/pypy
hg merge 9fd1c9e7f3fc
hg commit -m 'Merged in mpavone/pypy (pull request #93)'
Author
  1. Michael Pavone
Reviewers
Description

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

  • Learn about pull requests

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