Value Preservation and Polysemy
braddr at bellevue.puremagic.com
Mon Dec 1 14:04:01 PST 2008
On Mon, 1 Dec 2008, Andrei Alexandrescu wrote:
> My enthusiasm about polysemy got quite a bit lower when I realized that the
> promises of polysemy for integral operations can be provided (and actually
> outdone) by range analysis, a well-known method.
> The way it's done: for each integral expression in the program assign two
> numbers: the smallest possible value, and the largest possible value. Literals
> will therefore have a salami-slice-thin range associated with them. Whenever
> code asks for a lossy implicit cast, check the range and if it fits within the
> target type, let the code go through.
> Each operation computes its ranges from the range of its operands. The
> computation is operation-specific. For example, the range of a & b is
> max(a.range.min, b.range.min) to min(a.range.max, b.range.max). Sign
> considerations complicate this a bit, but not quite much.
> The precision of range analysis can be quite impressive, for example:
> uint b = ...;
> ubyte a = ((b & 2) << 6) | (b >> 24);
> typechecks no problem because it can prove no loss of information for all
> values of b.
The term I see associated with this technique, indeed well known, is Value
Range Propagation. Combine this sort of accumulated knowledge with loop
and if condition analysis as well as inlining, and often a signivicant
amount of dead code elimination can occur.
More information about the Digitalmars-d