Re: new sign/zero extension elimination pass

[Paolo Bonzini <bonzini at gnu dot org>]

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).

In addition, I wonder if this pass wouldn't introduce new undefined 
overflows, which would be a correctness problem.  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.

Paolo