Re: [PATCH] Fix forwporp pattern (T)(P + A) - (T)P -> (T)A

[Richard Biener <richard dot guenther at gmail dot com>]

On Mon, Jun 23, 2014 at 8:02 PM, Bernd Edlinger
<bernd.edlinger@hotmail.de> wrote:
> Hi,
>
> On Mon, 23 Jun 2014 19:12:47, Richard Biener wrote:
>>
>> On Mon, Jun 23, 2014 at 4:28 PM, Bernd Edlinger
>> <bernd.edlinger@hotmail.de> wrote:
>>> Hi,
>>>
>>> On Mon, 23 Jun 2014 10:40:53, Richard Biener wrote:
>>>>
>>>> On Sun, Jun 22, 2014 at 9:14 AM, Bernd Edlinger
>>>> <bernd.edlinger@hotmail.de> wrote:
>>>>> Hi,
>>>>>
>>>>> I noticed that several testcases in the GMP-4.3.2 test suite are failing now which
>>>>> did not happen with GCC 4.9.0. I debugged the first one, mpz/convert, and found
>>>>> the file mpn/generic/get_str.c was miscompiled.
>>>>>
>>>>> mpn/get_str.c.132t.dse2:
>>>>> pretmp_183 = (sizetype) chars_per_limb_80;
>>>>> pretmp_184 = -pretmp_183;
>>>>> _23 = chars_per_limb_80 + 4294967295;
>>>>> _68 = (sizetype) _23;
>>>>> _28 = _68 + pretmp_184;
>>>>>
>>>>> mpn/get_str.c.133t.forwprop4:
>>>>> _28 = 4294967295;
>>>>>
>>>>>
>>>>> That is wrong, because chars_per_limb is unsigned, and it is not zero.
>>>>> So the right result should be -1. This makes the loop termination in that
>>>>> function fail.
>>>>>
>>>>> The reason for this is in this check-in:
>>>>>
>>>>> r210807 | ebotcazou | 2014-05-22 16:32:56 +0200 (Thu, 22 May 2014) | 3 lines
>>>>>
>>>>> * tree-ssa-forwprop.c (associate_plusminus): Extend (T)(P + A) - (T)P
>>>>> -> (T)A transformation to integer types.
>>>>>
>>>>>
>>>>> Because it implicitly assumes that integer overflow is not allowed with all types,
>>>>> including unsigned int.
>>>>
>>>> Hmm? But the transform is correct if overflow wraps. And it's correct if
>>>> overflow is undefined as well, as (T)A is always well-defined (implementation
>>>> defined) if it is a truncation.
>>>>
>>>
>>> we have no problem when the cast from (P + A) to T is a truncation, except if
>>> the add operation P + A is saturating.
>>
>> Ah, we indeed look at an inner operation.
>>
>>>> So we match the above an try to transform it to (T)P + (T)A - (T)P. That's
>>>> wrong if the conversion is extending I think.
>>>>
>>>
>>> Yes, in a way. But OTOH, Eric's test case opt37.adb, fails if we simply punt here.
>>>
>>> Fortunately, with opt37.adb, P and A are signed 32-bit integers, and T is size_t (64 bit)
>>> and because the overflow of P + A causes undefined behaviour, we can assume that
>>> P + A _did_ not overflow, and therefore the transformation (T)(P + A) == (T)P + (T)A
>>> is correct (but needs a strict overflow warning), and we still can use the pattern
>>> (T)P + (T)A - (T)P -> (T)A in this case.
>>
>> Ok, though that is then the only transform that uses strict-overflow semantics.
>>
>>> But we cannot use this transformation, as the attached test case demonstrates
>>> when P + A is done in unsigned integers, because the result of the addition is
>>> different if it is done in unsigned int with allowed overflow, or in long without
>>> overflow.
>>>
>>>> Richard.
>>>>
>>>>
>>>>>
>>>>> The attached patch fixes these regressions, and because the reasoning depends
>>>>> on the TYPE_OVERFLOW_UNDEFINED attribute, a strict overflow warning has to be
>>>>> emitted here, at least for widening conversions.
>>>>>
>>>>>
>>>>> Boot-strapped and regression-tested on x86_64-linux-gnu with all languages, including Ada.
>>>>> OK for trunk?
>>>>
>>>> + if (!TYPE_SATURATING (TREE_TYPE (a))
>>>>
>>>> this is already tested at the very beginning of the function.
>>>>
>>>
>>> We have done TYPE_SATURATING (TREE_TYPE (rhs1)) that refers to T,
>>> but I am concerned about the inner addition operation here,
>>> and if it is done in a saturating way.
>>
>> Ok, a valid concern.
>>
>>>
>>>> + && !FLOAT_TYPE_P (TREE_TYPE (a))
>>>> + && !FIXED_POINT_TYPE_P (TREE_TYPE (a))
>>>>
>>>> likewise.
>>>
>>> Well, maybe this cannot happen, because if we have P + A, computed in float,
>>> and T an integer type, then probably CONVERT_EXPR_CODE_P (def_code)
>>> will not match, because def_code is FIX_TRUNC_EXPR in that case?
>>
>> Yes. It cannot be a FLOAT_TYPE_P here, similar for fixed-point which
>> would use FIXED_CONVERT_EXPR. Saturating types don't seem to have
>> a special conversion tree code.
>>
>
> then this should be an assertion, with a comment why this is supposed to be impossible.

Hum, well. If then such check belongs in the gimple verifier in tree-cfg.c, not
spread (and duplicated) in random code.

>>> OTOH it does not hut to check that, becaue A's type may be quite different
>>> than rhs1's type.
>>>
>>>>
>>>> + || (!POINTER_TYPE_P (TREE_TYPE (p))
>>>> + && INTEGRAL_TYPE_P (TREE_TYPE (a))
>>>> + && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (a)))
>>>>
>>>> INTEGRAL_TYPE_P are always !POINTER_TYPE_P.
>>>>
>>>>
>>>
>>> We come here, either because P + A is a POINTER_PLUS_EXPR or because P + A is a PLUS_EXPR.
>>
>> Ah, p vs. a - misread that code.
>>
>>> In the first case, P's type is POINTER_TYPE_P and A's type is INTEGRAL_TYPE_P
>>> so this should not check the TYPE_OVERFLOW_UNDEFINED, but instead
>>> the POINTER_TYPE_OVERFLOW_UNDEFINED.
>>>
>>> Also with undefined pointer wraparound, we can exploit that in the same way as with
>>> signed integers.
>>>
>>> But I am concerned, if (T)A is always the same thing as (T)(void*)A.
>>> I'd say, yes, if TYPE_UNSIGNED (TREE_TYPE (p)) == TYPE_UNSIGNED (TREE_TYPE (a))
>>> or if A is a constant, and it is positive.
>>
>> I don't understand this last bit. If p is pointer then a is of
>> unsigned sizetype.
>> sizetypes size doesn't have to match pointer size.
>>
>
> Yes, maybe I was only a bit too shy here.
>
> The resulting code (T)A casts directly from ptrdiff_t to T, while before the transformation
> the cast was from pointer_t to T. Is the result always the same, even for negative A?

No.  That's the point of the precision check - we don't know how to extend A
to T.  Well, in theory we know that A is supposed to be sign-extended to
typeof (P) and then we know that T has the same precision as typeof (P).
So there only exists a problem for extension for targets which have
sizetype precision != pointer precision.

> I was not sure, if A is always unsigned for all possible targets,
> and if P is always unsigned and of same bit-size than A.
> And if P may have different signedness than A what a pointer
> wraparound means exactly.
>
> If the answer is A and P are always unsigned and of same size,
> then it would simplify this part significantly.

It's quite a bit more complicated, but pointer-offsets are always to be
interpreted signed (if A and P have different precision - otherwise it doesn't
matter).  Also in GIMPLE pointers have to be casted to integers with
the same precision first to make it well-defined how they extend.

So the only possible issue is with targets that have precision A != P
where we have to cast A to signed typeof (A) first before casting that to T.

>> Can you re-work the patch to split the case that doesn't exploit the undefined
>> behavior (and thus does not need to warn) and the case that does,
>> adding comments with reasoning before the individual || tests?
>>
>
> The first part will break gnat.dg/opt37.adb,
> and the second part will fix it again, is that OK?

Yes.

>> The condition in your patch is unwiedingly large.
>>
>
> Sorry, I should have warned you, it caused myself severe headaches
> when I wrote it down :-)

Eh ...

Richard.

>> Richard.
>>
>>>
>>>
>>> Thanks
>>> Bernd.
>>>
>>>Then I dont need both conditions, but I was unsure here, because
>