value range propagation for _bitwise_ OR

[Adam D. Ruppe]

On Sat, Apr 10, 2010 at 09:21:07PM -0500, Andrei Alexandrescu wrote:
> Yah, it's clear that we're not looking anywhere near 100%. I'm a bit sad 
> we don't have an adequate baseline, but the fact that two distinct 
> methods obtained the same result is encouraging.

My brute-force program was buggy, but I think I fixed it. Here's the main():

========
	uint min_a = 0;
	uint min_b = 0;
	for(uint max_a = min_a; max_a <= 256; max_a++)
	for(uint max_b = min_b; max_b <= 256; max_b++) {
		uint real_max = 0;
		for(uint a = min_a; a <= max_a; a++)
		for(uint b = min_b; b <= max_b; b++) {
			assert((a|b) <= max_c(max_a, max_b), format("%b | %b !<= %b (from %b %b)", a, b, max_c(max_a, max_b), max_a, max_b));
			assert((a|b) >= min_c(min_a, min_b));
			if((a | b) > real_max)
				real_max = (a|b);
		}
		assert(max_c(max_a, max_b) == real_max, format("[%b, %b]. expected: %d, got %d (min == %d)", max_a, max_b, max_c(max_a, max_b), real_max, min_c(min_a, min_b)));
	}

	writeln("success");
=======

With so many nested loops, it is slow as dirt, but what it does is try every
value in the given range and record the maximum number encountered.

If it doesn't match at any step, it throws. But, it works for me. I spent
a chunk of the day eyeballing the output too to ensure it is right (and to
figure out the pattern that led to the final function).


Now, the thing is if you change min_a or min_b, it breaks the real_max; like
I said in the other message, if min == max, for example, you get the case
where 4|4 isn't the max, since 4|3 isn't available.

I'm not sure how to fix that, but I am pretty convinced that to get the
perfect solution, the max_c function needs to know min_a and min_b too.
Still, this solution works very well in the min_a = min_b = 0 case, so
it is at least a decent bound.

> On to the next task: compute minOR and maxOR for _signed_ values. It 
> turns out minOR its also nontrivial...

Nontrivial is an understatement. I started asking if it can even be done
without assuming a size.. I do think you can, by assuming the sizes
are equal, whatever they are, but it still is not easy.

I still like the idea of just casting it. How often would it cause problems
in real code anyway?

The only starting point I have is:
Of either max_a or max_b is negative, the result of the OR is going
to be negative, since that sign bit is one, and we can't change a one to
a zero on any OR operation.

So, the max value will be positive iff both values are possibly positive.

But taking that one statement to working code is too hard for my blood.


> When we're done, we can pass the functions to Walter so he can integrate 
> them within his compiler. Right now the compiler uses a wrong algorithm.

Indeed. We're getting there, but still a ways to go.


-- 
Adam D. Ruppe
http://arsdnet.net