Re: [PATCH 1/2] ivopts: Revert computation of address cost complexity.

[Dimitrije Milosevic <Dimitrije.Milosevic@Syrmia.com>]

Hi Richard,

> But something is wrong then - it shouldn't ever pick a candidate with
> an addressing
> mode that isn't supported?

Test case I presented in [0] only has non-"BASE + OFFSET" candidates. Correct me
if I'm wrong, but the candidate selection algorithm doesn't take into account
which addressing modes are supported by the target?

> So you say that the cost of expressing
> 'BASE + INDEX << SCALE + OFFSET' as 'BASE + OFFSET' is not computed
> accurately?

I just took it as an example, but yes.

> The function tries to compensate for that, maybe you can point out
> where it goes wrong?
> That is, at the end it adjusts cost and complexity based on what it
> scrapped before, maybe
> that is just a bit incomplete?

I think the cost.cost part is mostly okay, as the costs are just scaled 
(what was lesser/higher before f9f69dd is lesser/higher after f9f69dd).
As far as the adjustments go, I don't think they are complete. 
On the other hand, as complexity is a valid part of address costs, and
it can be used as a tie-breaker, I feel like it should serve a purpose, 
even for targets like Mips which are limited when it comes to 
addressing modes, rather than being equal to 0.

I guess an alternative would be to fully cover cost.cost adjustments, and
leave the complexities to be 0 for non-supported addressing modes.
Currently, they are implemented as follows:

  if (simple_inv)
    simple_inv = (aff_inv == NULL
		  || aff_combination_const_p (aff_inv)
		  || aff_combination_singleton_var_p (aff_inv));
  if (!aff_combination_zero_p (aff_inv))
    comp_inv = aff_combination_to_tree (aff_inv);
  if (comp_inv != NULL_TREE)
    cost = force_var_cost (data, comp_inv, inv_vars);
  if (ratio != 1 && parts.step == NULL_TREE)
    var_cost += mult_by_coeff_cost (ratio, addr_mode, speed);
  if (comp_inv != NULL_TREE && parts.index == NULL_TREE)
    var_cost += add_cost (speed, addr_mode);

> Note the original author of this is not available so it would help
> (maybe also yourself) to
> walk through the function with a specific candidate / use where you
> think the complexity
> (or cost) is wrong?

I'd like to refer to [0] where candidate costs didn't get adjusted to 
cover the lack of complexity calculation.

Would love to hear your thoughts.

[0] https://gcc.gnu.org/pipermail/gcc-patches/2022-October/604304.html

Regards,
Dimitrije

From: Richard Biener <richard.guenther@gmail.com>
Sent: Friday, October 28, 2022 9:00 AM
To: Dimitrije Milosevic <Dimitrije.Milosevic@Syrmia.com>
Cc: Jeff Law <jeffreyalaw@gmail.com>; gcc-patches@gcc.gnu.org <gcc-patches@gcc.gnu.org>; Djordje Todorovic <Djordje.Todorovic@syrmia.com>
Subject: Re: [PATCH 1/2] ivopts: Revert computation of address cost complexity. 
 
On Fri, Oct 28, 2022 at 8:43 AM Dimitrije Milosevic
<Dimitrije.Milosevic@syrmia.com> wrote:
>
> Hi Jeff,
>
> > THe part I don't understand is, if you only have BASE+OFF, why does
> > preventing the calculation of more complex addressing modes matter?  ie,
> > what's the point of computing the cost of something like base + off +
> > scaled index when the target can't utilize it?
>
> Well, the complexities of all addressing modes other than BASE + OFFSET are
> equal to 0. For targets like Mips, which only has BASE + OFFSET, it would still
> be more complex to use a candidate with BASE + INDEX << SCALE + OFFSET
> than a candidate with BASE + INDEX, for example, as it has to compensate
> the lack of other addressing modes somehow. If complexities for both of
> those are equal to 0, in cases where complexities decide which candidate is
> to be chosen, a more complex candidate may be picked.

But something is wrong then - it shouldn't ever pick a candidate with
an addressing
mode that isn't supported?  So you say that the cost of expressing
'BASE + INDEX << SCALE + OFFSET' as 'BASE + OFFSET' is not computed
accurately?

The function tries to compensate for that, maybe you can point out
where it goes wrong?
That is, at the end it adjusts cost and complexity based on what it
scrapped before, maybe
that is just a bit incomplete?

Note the original author of this is not available so it would help
(maybe also yourself) to
walk through the function with a specific candidate / use where you
think the complexity
(or cost) is wrong?


> Regards,
> Dimitrije
>
>
> From: Jeff Law <jeffreyalaw@gmail.com>
> Sent: Friday, October 28, 2022 1:02 AM
> To: Dimitrije Milosevic <Dimitrije.Milosevic@Syrmia.com>; gcc-patches@gcc.gnu.org <gcc-patches@gcc.gnu.org>
> Cc: Djordje Todorovic <Djordje.Todorovic@syrmia.com>
> Subject: Re: [PATCH 1/2] ivopts: Revert computation of address cost complexity.
>
>
> On 10/21/22 07:52, Dimitrije Milosevic wrote:
> > From: Dimitrije Milošević <dimitrije.milosevic@syrmia.com>
> >
> > This patch reverts the computation of address cost complexity
> > to the legacy one. After f9f69dd, complexity is calculated
> > using the valid_mem_ref_p target hook. Architectures like
> > Mips only allow BASE + OFFSET addressing modes, which in turn
> > prevents the calculation of complexity for other addressing
> > modes, resulting in non-optimal candidate selection.
> >
> > gcc/ChangeLog:
> >
> >        * tree-ssa-address.cc (multiplier_allowed_in_address_p): Change
> >        to non-static.
> >        * tree-ssa-address.h (multiplier_allowed_in_address_p): Declare.
> >        * tree-ssa-loop-ivopts.cc (compute_symbol_and_var_present): Reintroduce.
> >        (compute_min_and_max_offset): Likewise.
> >        (get_address_cost): Revert
> >        complexity calculation.
>
> THe part I don't understand is, if you only have BASE+OFF, why does
> preventing the calculation of more complex addressing modes matter?  ie,
> what's the point of computing the cost of something like base + off +
> scaled index when the target can't utilize it?
>
>
> jeff
>