Re: IVOPT improvement patch

[Xinliang David Li <davidxl at google dot com>]

On Tue, May 25, 2010 at 4:59 PM, Zdenek Dvorak <rakdver@kam.mff.cuni.cz> wrote:
> Hi,
>
>> >> 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)'.
>
> this code covers forcing cbase and ubase to registers (which is loop invariant)
> and subtracting (add_cost) cbase from var (which is not).

Ok, will hoist the adjustment into branches.

>
>> ?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' ??
>
> Yes.
>
>> >> 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
>
> No. ?We want to express the exit condition for 2147483647 iterations using
> the variable with evolution [&c + some constant, +, 4], whose period is smaller
> (1073741823 iterations). ?This is obviously not possible. ?That is, after 2147483647
> iterations (and two overflows), this induction variable will have value &c + 12, as
> the folding correctly determines. ?However, this value is also achieved
> after only three iterations, which causes the loop to exit prematurely. ?The
> fact that NITR is a compile-time constant has nothing to do with
> the problem, which would reproduce even if NITR was a variable with the same value.
>
> The cause of the problem is that the bound on the number of iterations (that we
> use to ensure that the computation does not overflow in this way) comes from a
> different exit. ?So, we need to be sure that the bound corresponds to the
> currently considered exit. ?Which surely is the case if either NITR (which is
> an expression giving the number of iterations before the current exit is taken)
> is a compile-time constant, or if there are no other exits from the loop.
>

Yes yes yes -- that is precise.

Thanks,

David



> Zdenek
>