If the types of the arguments of LOG{AND,IOR,XOR} are known to be ranges

of non-negative integers the compiler currently derives the range of the

result using straightforward implementations of algorithms from

"Hacker's Delight". These take quadratical time in the number of bits of

the inputs in the worst case, potentially leading to unacceptably long

compilation times. (The algorithms are based on loops over the bits of

the inputs, doing calculations during each iteration that are themselves

linear in the number of bits of their operands.)

Instead implement bit-parallel algorithms I have found that take linear

time in all cases. While their runtime therefore is limited to much

smaller values for large inputs, it is comparable to that of the current

algorithms for small inputs, too; the new deriver for LOGXOR is in fact

faster than the old one by a factor of two to ten already in the latter

case.

The (existing) test for these derivers compares their results with those

from a brute-force algorithm for all O(N^4) many pairs of input ranges

with endpoints from the set of N-bit unsigned integers. The brute-force

algorithm needs to consider O(N^2) input pairs for each pair of ranges,

making the total runtime O(N^6). Therefore the test normally runs with

N = 5. I have tested all three new derivers successfully with N = 7.

Replace LOG{AND,IOR,XOR}-DERIVE-UNSIGNED-{LOW,HIGH}-BOUND with

LOG{AND,IOR,XOR}-DERIVE-UNSIGNED-BOUNDS to make it possible to evaluate

expressions only once that the calculations for the low and the high

bound have in common. The callers always need both bounds anyway.

Adapt the test to this change. (It runs twice as fast now due to the

brute force loop calculating both bounds in one go.)

Add a test for the scaling behaviour. This needs a function to measure

runtimes over potentially large ranges; add this to test-util.lisp.

Fixes lp#1096444.