Re: [PATCH][vectorizer][2/2] Hook up mult synthesis logic into vectorisation of mult-by-constant

[Kyrill Tkachov <kyrylo dot tkachov at foss dot arm dot com>]

On 15/06/16 22:53, Marc Glisse wrote:
> On Wed, 15 Jun 2016, Kyrill Tkachov wrote:
>
> > This is a respin of https://gcc.gnu.org/ml/gcc-patches/2016-06/msg00952.html following feedback.
> > I've changed the code to cast the operand to an unsigned type before applying the multiplication algorithm
> > and cast it back to the signed type at the end.
> > Whether to perform the cast is now determined by the function cast_mult_synth_to_unsigned in which I've implemented
> > the cases that Marc mentioned in [1]. Please do let me know
> > if there are any other cases that need to be handled.
>
> Ah, I never meant those cases as an exhaustive list, I was just looking for examples showing that the transformation was unsafe, and those 2 came to mind:
>
> - x*15 -> x*16-x the second one can overflow even when the first one doesn't.
>
> - x*-2 -> -(x*2) can overflow when the result is INT_MIN (maybe that's redundant with the negate_variant check?)
>
> On the other hand, as long as we remain in the 'positive' operations, turning x*3 to x<<1+x seems perfectly safe. And even x*30 to (x*16-x)*2 cannot cause spurious overflows. But I didn't look at the algorithm closely enough to 
> characterize the safe cases. Now if you have done it, that's good :-) Otherwise, we might want to err on the side of caution.

I'll be honest, I didn't give it much thought beyond convincing myself that the two cases you listed are legitimate.
Looking at expand_mult_const in expmed.c can be helpful (where it updates val_so_far for checking purposes) to see
the different algorithm cases. I think the only steps that could cause overflow are alg_sub_t_m2, alg_sub_t2_m and alg_sub_factor or when the final step is negate_variant, which are what you listed (and covered in this patch).

richi is away on PTO for the time being though, so we have some time to convince ourselves :)

Thanks,
Kyrill