* [PATCH 0/2]: Fix address cost complexity and register pressure cost calculation. @ 2022-12-21 13:12 Dimitrije Milošević 2022-12-21 13:12 ` [PATCH 1/2] ivopts: Compute complexity for unsupported addressing modes Dimitrije Milošević 2022-12-21 13:12 ` [PATCH 2/2] ivopts: Revert register pressure cost when there are enough registers Dimitrije Milošević 0 siblings, 2 replies; 6+ messages in thread From: Dimitrije Milošević @ 2022-12-21 13:12 UTC (permalink / raw) To: gcc-patches; +Cc: djordje.todorovic, richard.guenther, jeffreyalaw Architectures like Mips are very limited when it comes to addressing modes. Therefore, the expected behavior would be that, for the BASE + OFFSET addressing mode, complexity is lower, while, for more complex addressing modes (e.g. BASE + INDEX << SCALE), which are not supported, complexity is higher. Currently, the complexity calculation algorithm bails out if BASE + INDEX addressing mode is not supported by the target architecture, resuling in 0-complexities for all candidates, which leads to non-optimal candidate selection, especially in scenarios where there are multiple nested loops. Register pressure cost model isn't optimal for the case when there are enough registers. Currently, the register pressure cost is bumped up by another n_cands, while there is no reason for the register pressure cost to be equal to n_cands + n_invs (for that case). Adding another n_cands could be used as a tie-breaker for the two cases where we do have enough registers and the sum of n_invs and n_cands is equal, however I think there are two problems with that: - How often does it happen that we have two cases where we do have enough registers, n_invs + n_cands sums are equal, and n_cands differ? I think that's pretty rare. - Bumping up the cost by another n_cands may lead to cost for the "If we do have enough registers." case to be higher than for other cases, which doesn't make sense. Dimitrije Milosevic (2): ivopts: ivopts: Compute complexity for unsupported addressing modes. ivopts: Revert register pressure cost when there are enough registers. gcc/tree-ssa-loop-ivopts.cc | 10 +++++++--- 1 file changed, 7 insertions(+), 3 deletions(-) --- 2.25.1 ^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH 1/2] ivopts: Compute complexity for unsupported addressing modes. 2022-12-21 13:12 [PATCH 0/2]: Fix address cost complexity and register pressure cost calculation Dimitrije Milošević @ 2022-12-21 13:12 ` Dimitrije Milošević 2022-12-21 13:12 ` [PATCH 2/2] ivopts: Revert register pressure cost when there are enough registers Dimitrije Milošević 1 sibling, 0 replies; 6+ messages in thread From: Dimitrije Milošević @ 2022-12-21 13:12 UTC (permalink / raw) To: gcc-patches Cc: djordje.todorovic, richard.guenther, jeffreyalaw, Dimitrije Milošević 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. There still is code that adjusts the address cost for unsupported addressing modes, however, it only adjusts the cost part (the complexity part is left at 0). gcc/ChangeLog: * tree-ssa-loop-ivopts.cc (get_address_cost): Calculate complexity for unsupported addressing modes as well. Signed-off-by: Dimitrije Milosevic <dimitrije.milosevic@syrmia.com> --- gcc/tree-ssa-loop-ivopts.cc | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc index ebd4aecce37..60c61dc9e49 100644 --- a/gcc/tree-ssa-loop-ivopts.cc +++ b/gcc/tree-ssa-loop-ivopts.cc @@ -4778,10 +4778,14 @@ get_address_cost (struct ivopts_data *data, struct iv_use *use, 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) + 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.complexity += 1; + } + if (comp_inv != NULL_TREE && parts.index == NULL_TREE) { var_cost += add_cost (speed, addr_mode); + var_cost.complexity += 1; + } if (comp_inv && inv_expr && !simple_inv) { -- 2.25.1 ^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH 2/2] ivopts: Revert register pressure cost when there are enough registers. 2022-12-21 13:12 [PATCH 0/2]: Fix address cost complexity and register pressure cost calculation Dimitrije Milošević 2022-12-21 13:12 ` [PATCH 1/2] ivopts: Compute complexity for unsupported addressing modes Dimitrije Milošević @ 2022-12-21 13:12 ` Dimitrije Milošević 2023-05-15 10:44 ` Richard Biener 1 sibling, 1 reply; 6+ messages in thread From: Dimitrije Milošević @ 2022-12-21 13:12 UTC (permalink / raw) To: gcc-patches Cc: djordje.todorovic, richard.guenther, jeffreyalaw, Dimitrije Milošević When there are enough registers, the register pressure cost is unnecessarily bumped by adding another n_cands. This behavior may result in register pressure costs for the case when there are enough registers being higher than for other cases. When there are enough registers, the register pressure cost should be equal to n_invs + n_cands. This used to be the case before c18101f. gcc/ChangeLog: * tree-ssa-loop-ivopts.cc (ivopts_estimate_reg_pressure): Adjust. Signed-off-by: Dimitrije Milosevic <dimitrije.milosevic@syrmia.com> --- gcc/tree-ssa-loop-ivopts.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc index 60c61dc9e49..3176482d0d9 100644 --- a/gcc/tree-ssa-loop-ivopts.cc +++ b/gcc/tree-ssa-loop-ivopts.cc @@ -6092,7 +6092,7 @@ ivopts_estimate_reg_pressure (struct ivopts_data *data, unsigned n_invs, /* If we have enough registers. */ if (regs_needed + target_res_regs < available_regs) - cost = n_new; + return n_new; /* If close to running out of registers, try to preserve them. */ else if (regs_needed <= available_regs) cost = target_reg_cost [speed] * regs_needed; -- 2.25.1 ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 2/2] ivopts: Revert register pressure cost when there are enough registers. 2022-12-21 13:12 ` [PATCH 2/2] ivopts: Revert register pressure cost when there are enough registers Dimitrije Milošević @ 2023-05-15 10:44 ` Richard Biener 2023-05-15 12:23 ` Richard Biener 0 siblings, 1 reply; 6+ messages in thread From: Richard Biener @ 2023-05-15 10:44 UTC (permalink / raw) To: Dimitrije Milošević; +Cc: gcc-patches, djordje.todorovic, jeffreyalaw On Wed, Dec 21, 2022 at 2:12 PM Dimitrije Milošević <dimitrije.milosevic@syrmia.com> wrote: > > When there are enough registers, the register pressure cost is > unnecessarily bumped by adding another n_cands. > > This behavior may result in register pressure costs for the case > when there are enough registers being higher than for other cases. > > When there are enough registers, the register pressure cost should be > equal to n_invs + n_cands. > > This used to be the case before c18101f. > > gcc/ChangeLog: > > * tree-ssa-loop-ivopts.cc (ivopts_estimate_reg_pressure): Adjust. > > Signed-off-by: Dimitrije Milosevic <dimitrije.milosevic@syrmia.com> > --- > gcc/tree-ssa-loop-ivopts.cc | 2 +- > 1 file changed, 1 insertion(+), 1 deletion(-) > > diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc > index 60c61dc9e49..3176482d0d9 100644 > --- a/gcc/tree-ssa-loop-ivopts.cc > +++ b/gcc/tree-ssa-loop-ivopts.cc > @@ -6092,7 +6092,7 @@ ivopts_estimate_reg_pressure (struct ivopts_data *data, unsigned n_invs, > > /* If we have enough registers. */ > if (regs_needed + target_res_regs < available_regs) > - cost = n_new; > + return n_new; This still doesn't make much sense (before nor after). We're comparing apples and oranges. I think it would make most sense to merge this case with the following and thus do the following. The distinction between the cases should be preserved and attenuated by the adding of n_cands at the end (as tie-breaker). Does this help the mips case? I'm going to throw it at x86_64-linux bootstrap/regtest. Btw, I don't think using address complexity makes much sense for a port that has only one addressing mode so I guess a better approach for 1/2 would be to make sure it is consistently the same value (I suppose it is not, otherwise you wouldn't have changed it). Oh, and we're adding the reg-pressure cost to the same bucket as well, and there we don't really know how many times we're going to spill. That said, I think ->complexity should rather go away - we are asking for address-cost already and IVOPTs uses built RTX to query the target. But yes, I agree ivopts_estimate_reg_pressure has an issue. Sorry for the very long delay, Richard. diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc index 6fbd2d59318..bc8493622de 100644 --- a/gcc/tree-ssa-loop-ivopts.cc +++ b/gcc/tree-ssa-loop-ivopts.cc @@ -6077,8 +6077,9 @@ ivopts_estimate_reg_pressure (struct ivopts_data *data, unsigned n_invs, unsigned n_cands) { unsigned cost; - unsigned n_old = data->regs_used, n_new = n_invs + n_cands; - unsigned regs_needed = n_new + n_old, available_regs = target_avail_regs; + unsigned n_old = data->regs_used; + unsigned regs_needed = n_invs + n_cands + n_old; + unsigned available_regs = target_avail_regs; bool speed = data->speed; /* If there is a call in the loop body, the call-clobbered registers @@ -6087,10 +6088,7 @@ ivopts_estimate_reg_pressure (struct ivopts_data *data, unsigned n_invs, available_regs = available_regs - target_clobbered_regs; /* If we have enough registers. */ - if (regs_needed + target_res_regs < available_regs) - cost = n_new; - /* If close to running out of registers, try to preserve them. */ - else if (regs_needed <= available_regs) + if (regs_needed <= available_regs) cost = target_reg_cost [speed] * regs_needed; /* If we run out of available registers but the number of candidates does not, we penalize extra registers using target_spill_cost. */ > /* If close to running out of registers, try to preserve them. */ > else if (regs_needed <= available_regs) > cost = target_reg_cost [speed] * regs_needed; > -- > 2.25.1 > ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 2/2] ivopts: Revert register pressure cost when there are enough registers. 2023-05-15 10:44 ` Richard Biener @ 2023-05-15 12:23 ` Richard Biener 2023-05-15 14:32 ` Jovan Dmitrovic 0 siblings, 1 reply; 6+ messages in thread From: Richard Biener @ 2023-05-15 12:23 UTC (permalink / raw) To: Dimitrije Milošević; +Cc: gcc-patches, djordje.todorovic, jeffreyalaw On Mon, May 15, 2023 at 12:44 PM Richard Biener <richard.guenther@gmail.com> wrote: > > On Wed, Dec 21, 2022 at 2:12 PM Dimitrije Milošević > <dimitrije.milosevic@syrmia.com> wrote: > > > > When there are enough registers, the register pressure cost is > > unnecessarily bumped by adding another n_cands. > > > > This behavior may result in register pressure costs for the case > > when there are enough registers being higher than for other cases. > > > > When there are enough registers, the register pressure cost should be > > equal to n_invs + n_cands. > > > > This used to be the case before c18101f. > > > > gcc/ChangeLog: > > > > * tree-ssa-loop-ivopts.cc (ivopts_estimate_reg_pressure): Adjust. > > > > Signed-off-by: Dimitrije Milosevic <dimitrije.milosevic@syrmia.com> > > --- > > gcc/tree-ssa-loop-ivopts.cc | 2 +- > > 1 file changed, 1 insertion(+), 1 deletion(-) > > > > diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc > > index 60c61dc9e49..3176482d0d9 100644 > > --- a/gcc/tree-ssa-loop-ivopts.cc > > +++ b/gcc/tree-ssa-loop-ivopts.cc > > @@ -6092,7 +6092,7 @@ ivopts_estimate_reg_pressure (struct ivopts_data *data, unsigned n_invs, > > > > /* If we have enough registers. */ > > if (regs_needed + target_res_regs < available_regs) > > - cost = n_new; > > + return n_new; > > This still doesn't make much sense (before nor after). We're > comparing apples and oranges. > > I think it would make most sense to merge this case with the following > and thus do > the following. The distinction between the cases should be preserved > and attenuated > by the adding of n_cands at the end (as tie-breaker). > > Does this help the mips case? I'm going to throw it at x86_64-linux > bootstrap/regtest. > > Btw, I don't think using address complexity makes much sense for a port that > has only one addressing mode so I guess a better approach for 1/2 would be > to make sure it is consistently the same value (I suppose it is not, otherwise > you wouldn't have changed it). Oh, and we're adding the > reg-pressure cost to the same bucket as well, and there we don't really know > how many times we're going to spill. That said, I think ->complexity should > rather go away - we are asking for address-cost already and IVOPTs uses > built RTX to query the target. > > But yes, I agree ivopts_estimate_reg_pressure has an issue. > > Sorry for the very long delay, > Richard. The patch below bootstraps and regtests ok on x86_64-unknown-linux-gnu, but I guess that doesn't mean much. Richard. > diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc > index 6fbd2d59318..bc8493622de 100644 > --- a/gcc/tree-ssa-loop-ivopts.cc > +++ b/gcc/tree-ssa-loop-ivopts.cc > @@ -6077,8 +6077,9 @@ ivopts_estimate_reg_pressure (struct ivopts_data > *data, unsigned n_invs, > unsigned n_cands) > { > unsigned cost; > - unsigned n_old = data->regs_used, n_new = n_invs + n_cands; > - unsigned regs_needed = n_new + n_old, available_regs = target_avail_regs; > + unsigned n_old = data->regs_used; > + unsigned regs_needed = n_invs + n_cands + n_old; > + unsigned available_regs = target_avail_regs; > bool speed = data->speed; > > /* If there is a call in the loop body, the call-clobbered registers > @@ -6087,10 +6088,7 @@ ivopts_estimate_reg_pressure (struct > ivopts_data *data, unsigned n_invs, > available_regs = available_regs - target_clobbered_regs; > > /* If we have enough registers. */ > - if (regs_needed + target_res_regs < available_regs) > - cost = n_new; > - /* If close to running out of registers, try to preserve them. */ > - else if (regs_needed <= available_regs) > + if (regs_needed <= available_regs) > cost = target_reg_cost [speed] * regs_needed; > /* If we run out of available registers but the number of candidates > does not, we penalize extra registers using target_spill_cost. */ > > > > /* If close to running out of registers, try to preserve them. */ > > else if (regs_needed <= available_regs) > > cost = target_reg_cost [speed] * regs_needed; > > -- > > 2.25.1 > > ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 2/2] ivopts: Revert register pressure cost when there are enough registers. 2023-05-15 12:23 ` Richard Biener @ 2023-05-15 14:32 ` Jovan Dmitrovic 0 siblings, 0 replies; 6+ messages in thread From: Jovan Dmitrovic @ 2023-05-15 14:32 UTC (permalink / raw) To: Richard Biener; +Cc: gcc-patches, Djordje Todorovic, jeffreyalaw [-- Attachment #1: Type: text/plain, Size: 5156 bytes --] Hi Richard, I had pinged the community about this problem back in March, and I will be taking Dimitrije's place, considering he isn't working on these patches anymore. Your solution for 2/2 seems reasonable, I don't exactly know why target_reg_cost hasn't been accounted for in the first case, nor do I know why that particular case was specified at all. I will get back to you when I have researched 1/2 a bit more thoroughly. Regards, Jovan ________________________________ From: Richard Biener <richard.guenther@gmail.com> Sent: Monday, May 15, 2023 2:23 PM To: Dimitrije Milošević <dimitrije.milosevic@syrmia.com> Cc: gcc-patches@gcc.gnu.org <gcc-patches@gcc.gnu.org>; Djordje Todorovic <Djordje.Todorovic@syrmia.com>; jeffreyalaw@gmail.com <jeffreyalaw@gmail.com> Subject: Re: [PATCH 2/2] ivopts: Revert register pressure cost when there are enough registers. On Mon, May 15, 2023 at 12:44 PM Richard Biener <richard.guenther@gmail.com> wrote: > > On Wed, Dec 21, 2022 at 2:12 PM Dimitrije Milošević > <dimitrije.milosevic@syrmia.com> wrote: > > > > When there are enough registers, the register pressure cost is > > unnecessarily bumped by adding another n_cands. > > > > This behavior may result in register pressure costs for the case > > when there are enough registers being higher than for other cases. > > > > When there are enough registers, the register pressure cost should be > > equal to n_invs + n_cands. > > > > This used to be the case before c18101f. > > > > gcc/ChangeLog: > > > > * tree-ssa-loop-ivopts.cc (ivopts_estimate_reg_pressure): Adjust. > > > > Signed-off-by: Dimitrije Milosevic <dimitrije.milosevic@syrmia.com> > > --- > > gcc/tree-ssa-loop-ivopts.cc | 2 +- > > 1 file changed, 1 insertion(+), 1 deletion(-) > > > > diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc > > index 60c61dc9e49..3176482d0d9 100644 > > --- a/gcc/tree-ssa-loop-ivopts.cc > > +++ b/gcc/tree-ssa-loop-ivopts.cc > > @@ -6092,7 +6092,7 @@ ivopts_estimate_reg_pressure (struct ivopts_data *data, unsigned n_invs, > > > > /* If we have enough registers. */ > > if (regs_needed + target_res_regs < available_regs) > > - cost = n_new; > > + return n_new; > > This still doesn't make much sense (before nor after). We're > comparing apples and oranges. > > I think it would make most sense to merge this case with the following > and thus do > the following. The distinction between the cases should be preserved > and attenuated > by the adding of n_cands at the end (as tie-breaker). > > Does this help the mips case? I'm going to throw it at x86_64-linux > bootstrap/regtest. > > Btw, I don't think using address complexity makes much sense for a port that > has only one addressing mode so I guess a better approach for 1/2 would be > to make sure it is consistently the same value (I suppose it is not, otherwise > you wouldn't have changed it). Oh, and we're adding the > reg-pressure cost to the same bucket as well, and there we don't really know > how many times we're going to spill. That said, I think ->complexity should > rather go away - we are asking for address-cost already and IVOPTs uses > built RTX to query the target. > > But yes, I agree ivopts_estimate_reg_pressure has an issue. > > Sorry for the very long delay, > Richard. The patch below bootstraps and regtests ok on x86_64-unknown-linux-gnu, but I guess that doesn't mean much. Richard. > diff --git a/gcc/tree-ssa-loop-ivopts.cc b/gcc/tree-ssa-loop-ivopts.cc > index 6fbd2d59318..bc8493622de 100644 > --- a/gcc/tree-ssa-loop-ivopts.cc > +++ b/gcc/tree-ssa-loop-ivopts.cc > @@ -6077,8 +6077,9 @@ ivopts_estimate_reg_pressure (struct ivopts_data > *data, unsigned n_invs, > unsigned n_cands) > { > unsigned cost; > - unsigned n_old = data->regs_used, n_new = n_invs + n_cands; > - unsigned regs_needed = n_new + n_old, available_regs = target_avail_regs; > + unsigned n_old = data->regs_used; > + unsigned regs_needed = n_invs + n_cands + n_old; > + unsigned available_regs = target_avail_regs; > bool speed = data->speed; > > /* If there is a call in the loop body, the call-clobbered registers > @@ -6087,10 +6088,7 @@ ivopts_estimate_reg_pressure (struct > ivopts_data *data, unsigned n_invs, > available_regs = available_regs - target_clobbered_regs; > > /* If we have enough registers. */ > - if (regs_needed + target_res_regs < available_regs) > - cost = n_new; > - /* If close to running out of registers, try to preserve them. */ > - else if (regs_needed <= available_regs) > + if (regs_needed <= available_regs) > cost = target_reg_cost [speed] * regs_needed; > /* If we run out of available registers but the number of candidates > does not, we penalize extra registers using target_spill_cost. */ > > > > /* If close to running out of registers, try to preserve them. */ > > else if (regs_needed <= available_regs) > > cost = target_reg_cost [speed] * regs_needed; > > -- > > 2.25.1 > > ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2023-05-15 14:32 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2022-12-21 13:12 [PATCH 0/2]: Fix address cost complexity and register pressure cost calculation Dimitrije Milošević 2022-12-21 13:12 ` [PATCH 1/2] ivopts: Compute complexity for unsupported addressing modes Dimitrije Milošević 2022-12-21 13:12 ` [PATCH 2/2] ivopts: Revert register pressure cost when there are enough registers Dimitrije Milošević 2023-05-15 10:44 ` Richard Biener 2023-05-15 12:23 ` Richard Biener 2023-05-15 14:32 ` Jovan Dmitrovic
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).