[Zlib-devel] [PATCH] deflate.c: identify slide_Pos() for later optimization

[Jan Seiffert]

John Reiser schrieb:
> On 07/24/2012 Jan Seiffert wrote:
> 
>> I was talking about C compiler. They can't get this because of C type promotion
>> rules in this construct (or they have to cut through a lot of red tape).
> 
> My view is that ordinary range analysis can infer the saturating subtract,
> even in C.  I was careful to use 'Pos' everywhere, particularly for the
> 'slide' parameter, and not use 'unsigned' for any of the data declarations
> ['n' is a "control" variable here]:
> 
> +    Pos *const ptr; unsigned const n; Pos const slide;
> 
> +        Pos const m = ptr[j];
> +        ptr[j] = (Pos)(m >= slide ? m-slide : NIL);
> 
> Type promotion [extend with high-order bits which are zero] from 'Pos'
> [unsigned short] to 'unsigned', for either inputs or outputs of any
> _operation_ above, does not change the value of any result.  Thus
> performing all operations in 16-bit arithmetic does conform to the
> rules for evaluation of C expressions, and so saturating subtract
> of unsigned 16-bit quantities may be inferred.
> 

If my memory and understanding of C serves me right, the compiler:
- promotes everything that is smaller then an int to int
- if further promotion is needed (for example if int is to small)
uses the smallest type which is large enough, including the signed
types (so promoting from unsigned int to long (if long is for example
64 bit) is fine)

If int is > 16bit, it can hold an unsigned short value just fine,
only now the compiler is stuck with an signed type, which has
undefined overflow semantic.

He trapped himself...

The compiler could infer from the limited value range that this
is just saturating, but needs to poke through his own type extension
(if this happens to early in the FE...).
Or he could have a special pattern matcher for such constructs.

But this does not happen most of the time because such saturating
ops are not that common.
Most of the time those ops only come with SIMD.
So the Compiler _also_ has to vectorize the loop to begin with.

All in all it's not impossible, but happens seldom.

Greetings
	Jan

-- 
const int TEN=11; /* Mine goes to eleven */