Re: Anyone used Graphite of Gentoo recently?

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

On Mon, Mar 31, 2014 at 8:23 AM, Tobias Grosser <tobias@grosser.es> wrote:
> On 03/31/2014 06:25 AM, Vladimir Kargov wrote:
>>
>> On 27 March 2014 18:39, Mircea Namolaru <mircea.namolaru@gmail.com> wrote:
>>>
>>> The domain is computed on basis of the information provided by
>>> number_of_latch_execution that returns the tree expression
>>>
>>> (unsigned int) maxLen_6(D) - (unsigned int) minLen_4(D)
>>>
>>> For signed integers (without the cast to unsigned int) this seems to be
>>> the
>>> correct value. As an unsigned int expression it leads to incorrect
>>> domain.
>>
>>
>> I've got a couple of questions with regards to wrapping. Pasting the
>> relevant code from graphite-sese-to-poly.c:
>>
>> static isl_pw_aff *
>> extract_affine (scop_p s, tree e, __isl_take isl_space *space)
>> {
>> ...
>>    // e comes from number_of_latch_executions()
>>    type = TREE_TYPE (e);
>>    if (TYPE_UNSIGNED (type))
>>      res = wrap (res, TYPE_PRECISION (type));
>>
>> 1) Any idea why wrapping occurs only for unsigned expressions?
>
>
> In the C standard, unsinged operations have defined overflow semantics in
> form of wrapping. Signed operations instead have undefined behavior, which
> means we can assume that no wrapping occurs and consequently do not need to
> model it.
>
>> 2) What exactly is wrapping needed for? I can't find it in the old PPL
>> implementation (though it could have been called differently).
>
>
> it is necessary to model the defined overflow behavior of unsigned integers.
>
>> Also, no matter what the logic behind wrapping is, it does seem
>> suspicious that this code checks the signedness of the result of
>> number_of_latch_execution() (which may be arbitrary, as far as I
>> understood), and not of the loop induction variable, for example.
>
>
> It is very suspicious. It is a rather difficult topic and I doubt it is
> implemented correctly. Also, I do not think that implementing wrapping this
> way is the right approach. Instead, we should just model it to
> extract a run-time check that verifiers that no wrapping occurs and then go
> one without wrapping.
>
> Regarding this bug there are two directions to go:
>
> 1) It is necessary to understand if we need to do wrapping on the result of
> number_of_latch_executions. Meaning, we should understand the semantics of
> this function and the expression it returns.
>
> 2) There is something else happening?? From my observations it seems
> that the generated code at least for this test case should behave correctly
> and the relevant loop should be executed exactly twice. Surprisingly this is
> not the case. It would be interesting to understand what exactly prevents
> this loop from being executed. (From the clast, this is not obvious to me).

Note that there are always two sides of the "undefined overflow" thing

 1. in the input IL whether an operation may overflow or not (check
TYPE_OVERFLOW_UNDEFINED, _not_ !TYPE_UNSIGNED)
 2. in the GIMPLE IL generated from clast - all operations that satisfy
TYPE_OVERFLOW_UNDEFINED may not have different overflow behavior
than in the original untransformed program (no intermediate overflows
unless they were already present).  Usually that's not very easy to guarantee,
thus re-writing everything into unsigned arithmetic may be easiest.

Richard.

> Tobi