Re: [PATCH GCC][V2]A simple implementation of loop interchange

[Richard Biener <richard.guenther@gmail.com>]

On November 30, 2017 7:20:18 PM GMT+01:00, "Bin.Cheng" <amker.cheng@gmail.com> wrote:
>On Thu, Nov 30, 2017 at 3:51 PM, Richard Biener
><richard.guenther@gmail.com> wrote:
>> On Thu, Nov 30, 2017 at 4:09 PM, Richard Biener
>> <richard.guenther@gmail.com> wrote:
>>> On Thu, Nov 30, 2017 at 3:13 PM, Bin.Cheng <amker.cheng@gmail.com>
>wrote:
>>>> On Thu, Nov 30, 2017 at 1:01 PM, Richard Biener
>>>> <richard.guenther@gmail.com> wrote:
>>>
>>> Ok, I'd like to "dumb" the pass down to the level we can solve the
>>> bwave case (which I realize is already one of the more complicated
>ones).
>>>
>>> Just because it's already late for GCC 8.
>>
>> For reference I'll commit the following tomorrow, will play with
>adding
>> a testcase for bwaves and doing the multiple_of_p thing we talked
>about.
>Given instantiated scev in parameterized case like:
>{{{p_19(D), +, 8}_1, +, (long unsigned int) n_16(D) * 8}_2, +, (long
>unsigned int) (n_16(D) * n_16(D)) * 8}_3
>it's ideal if we can relate the variable part in stride with loop
>niters.  Unfortunately that's impractical because niter
>computation and address computation may expand variables differently.
> As in case of bwaves.
>This leaves us the method to check multiple relation for stride itself:
>(long unsigned int) (n_16(D) * n_16(D)) * 8  ;;stride X
> vs.
>(long unsigned int) n_16(D) * 8                     ;;stride Y
> vs.
>8                                                                   
>;;stride Z
From inner loop to outer, we check if Y is multiple of Z and if X is
>multiple of Y, so strides computed are like:
>8 * AVG_LOOP_NITERS * AVG_LOOP_NITERS
> vs.
>8 * AVG_LOOP_NITERS
> vs.
>8
>
>To make it general, we also need to check if X is multiple of previous
>stride (Z, in this case) if check on Y failed.
>
>The multiple check on tree expr is weak, so one question is how to do
>if failed.  Giving up or using a placeholder const stride?

The question is whether we are interested in just whether strideA is bigger than strideB or in the actual difference. If the former then substituting a constant of course works.  For multiplications that's even reasonable but for other ops the relation gets too weak IMHO. Maybe we can extract sth like factors we can more easily relate.  I guess only experiments will tell. At least we should separate step extraction and this 'analysis' given if all steps are constant we can employ more precise cost models. 

Richard. 

>Thanks,
>bin
>>
>> Richard.