This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: IVOPT improvement patch


On Tue, May 25, 2010 at 11:12 AM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
> Hi,
>
>> >> @@ -3811,6 +3841,9 @@ get_computation_cost_at (struct ivopts_d
>> >> ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?&offset, depends_on));
>> >> ? ? ?}
>> >>
>> >> + ?/* Loop invariant computation. ?*/
>> >> + ?cost.cost /= avg_loop_niter (data->current_loop);
>> >> +
>> >
>> > This is wrong, at least some parts of the computation here are not loop invariant.
>>
>> Which part is not loop invariant?
>
> it depends on the actual form of the use. ?But in the most general case, the
> computation whose cost is determined here is ubase + ratio * (var - cbase), and
> no part of this is loop invariant (except for the force_var_costs of ubase and cbase).

You mean the last 'else' branch?


  else
    {
      cost = force_var_cost (data, cbase, depends_on);
      cost.cost += add_cost (TYPE_MODE (ctype), data->speed);
      cost = add_costs (cost,
			difference_cost (data,
					 ubase, build_int_cst (utype, 0),
					 &symbol_present, &var_present,
					 &offset, depends_on));
    }

but I don't see how this cost estimate matches expression 'ubase +
ratio * (var - cbase)'.  Also look at function 'get_computation_aff',
it looks like the aff expression is always normalized into a sum of
product form.      Also at the end of this cost function before
'fallback:' label, there is this

if (aratio != 1)
  cost.cost += multiply_by_cost (aratio, TYPE_MODE (ctype), speed);

What is this for? Looks like it is for the last term 'ratio * var'  ?


>
>> >> @@ -4056,20 +4090,16 @@ may_eliminate_iv (struct ivopts_data *da
>> >> ? ?/* If not, and if this is the only possible exit of the loop, see whether
>> >> ? ? ? we can get a conservative estimate on the number of iterations of the
>> >> ? ? ? entire loop and compare against that instead. ?*/
>> >> - ?else if (loop_only_exit_p (loop, exit))
>> >> + ?else
>> >
>> > This change is wrong, the test is necessary. ?See
>> > http://gcc.gnu.org/ml/gcc-patches/2008-07/msg00146.html
>> > and the following discussion.
>> >
>>
>> The original fix to the problem is too conservative -- if there is
>> only one exit has the test to be replaced, it should be ok to do it,
>> right?
>
> Yes. ?But I do not see your point -- your patch removes the loop_only_exit_p
> test, which is necessary.


Right, I want to discuss more about this. Looking at the original PR
(msg00146.html) -- the fundamental problem is that why 'cand_value_at'
call for the testing to be replaced returns a bound of value &c + 12
with nitr == 0x80000001? It seems t the wrapping is caused by wrong
compiler folding -- probably wrong type is passed in (TREE_TYPE
(iv->cand) which is the pointer to c[..]).  The original fix seems
enough -- if 'nitr' is not compile time constant, the cand_value_at
would never be wrapped --- so why is testing of multiple exits needed?



>
>> >> ? ? ?{
>> >> ? ? ? ?double_int period_value, max_niter;
>> >> ? ? ? ?if (!estimated_loop_iterations (loop, true, &max_niter))
>> >> ? ? ? return false;
>> >> ? ? ? ?period_value = tree_to_double_int (period);
>> >> - ? ? ?if (double_int_ucmp (max_niter, period_value) >= 0)
>> >> + ? ? ?if (double_int_ucmp (max_niter, period_value) > 0)
>> >> ? ? ? return false;
>> >> ? ? ?}
>> >
>> > This also seems wrong (or at least inconsistent with that is done for
>> > the constant number of iterations).
>>
>> This looks correct to me.
>
> I think you are right; but, then the preceding test for tree_int_cst_lt
> should be changed as well (so that both conditions are the same).
> It would also be nice to add testcases for the boundary values to the
> testsuite, to make sure we are not making an off-by-one error.

I remember one the existing test case in the patch need this patch to
work -- I will double check.

Thanks,

David

>
> Zdenek
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]