Re: new sign/zero extension elimination pass

[Tom de Vries <tom@codesourcery.com>]

Paolo Bonzini wrote:
> On 10/28/2010 08:46 PM, Tom de Vries wrote:
>> The best version I can think now of is an iterative solution using
>> DU/UD-chains,
>> like this:
>> - Calculate and store the size of each use.
>> - Calculate and store the biggest use of each def (using DU-chains).
>> - Push the progating defs where the biggest use size is smaller than
>> word size
>>    on a stack.
>> - Pop a def.
>> - For the def, check if the propagated biggest use is bigger than the
>> current
>>    biggest use.
>>    If not, back to pop a def.
>>    If so, store current biggest use as propagated biggest use.
>> - For the def, propagate the biggest use of the def to the operands.
>> - For each operand, if the use size was reduced, find the reaching
>> definitions
>>    (using UD-chains).
>> - For each propagating definition, recompute the biggest use. If that
>> one was
>>    reduced below the propagated biggest use, push the def on the stack.
>> - back to pop a def.
>>
> 
> DU and UD-chains are quadratic, and the reaching definitions problem has
> very big solutions too, so they are rarely the right solution
> (unfortunately).
> 

thanks, I overlooked that completely.

> In addition, I wonder if this pass wouldn't introduce new undefined
> overflows, which would be a correctness problem.

The pass assumes wraparound overflow for plus and minus. The documentation of
the rtl operator 'plus' states that 'plus wraps round modulo the width of m'
(similar for 'minus'). I interpreted this independently from -fwrapv and
-fstrict-overflow, am I wrong there?

>  If you're going for a
> rewrite, I'd do it on tree-SSA so that:
> 
> 1) you can use unsigned math to avoid undefined overflow;
> 
> 2) SSA will provide you with cheap DU/UD.
> 
> Hopefully, only simple redundancies will remain after expand, and fwprop
> can take care of these using Andrew's patch.
> 

I see your point about the cheap DU/UD. I think the answer whether to do it in
tree-SSA or RTL depends on the answer to my previous question. If going to
tree-SSA allows us to catch more cases, we should do that.

- Tom