Re: [PATCH GCC]Refactor IVOPT.

[Bin.Cheng]

On Fri, Apr 22, 2016 at 8:20 AM, Richard Biener
 wrote:
> On Thu, Apr 21, 2016 at 7:26 PM, Bin Cheng  wrote:
>> Hi,
>> This patch refactors IVOPT in three major aspects:
>> Firstly it rewrites iv_use groups.  Use group is originally introduced only 
>> for address type uses, this patch makes it general to all (generic, compare, 
>> address) types.  Currently generic/compare groups contain only one iv_use, 
>> and compare groups can be extended to contain multiple uses.  As far as 
>> generic use is concerned, it won't contain multiple uses because IVOPT 
>> reuses one iv_use structure for generic uses at different places already.  
>> This change also cleanups algorithms as well as data structures.
>> Secondly it implements group data structure in vector rather than in list as 
>> originally.  List was used because it's easy to split.  Of course list is 
>> hard to sort (For example, we use quadratic insertion sort now).  This 
>> problem will become more critical since I plan to introduce fine-control 
>> over splitting small address groups by checking if target supports 
>> load/store pair instructions or not.  In this case address group needs to be 
>> sorted more than once and against complex conditions, for example, memory 
>> loads in one basic block should be sorted together in offset ascending 
>> order.  With vector group, sorting can be done very efficiently with quick 
>> sort.
>> Thirdly this patch cleanups/reformats IVOPT's dump information.  I think the 
>> information is easier to read/test now.  Since change of dump information is 
>> entangled with group data-structure change, it's hard to make it a 
>> standalone patch.  Given this part patch is quite straightforward, I hope it 
>> won't be confusing.
>>
>> Bootstrap and test on x86_64 and AArch64, no regressions.  I also checked 
>> generated assembly for spec2k and spec2k6 on both platforms, turns out 
>> output assembly is almost not changed except for several files.  After 
>> further investigation, I can confirm the difference is cause by small change 
>> when sorting groups. Given the original sorting condition as below:
>> -  /* Sub use list is maintained in offset ascending order.  */
>> -  if (addr_offset <= group->addr_offset)
>> -{
>> -  use->related_cands = group->related_cands;
>> -  group->related_cands = NULL;
>> -  use->next = group;
>> -  data->iv_uses[id_group] = use;
>> -}
>> iv_uses with same addr_offset are sorted in reverse control flow order.  
>> This might be a typo since I don't remember any specific reason for it.  If 
>> this patch sorts groups in the same way, there will be no difference in 
>> generated assembly at all.  So this patch is a pure refactoring work which 
>> doesn't have any functional change.
>>
>> Any comments?
>
> Looks good to me.

Hi
Attachment is what I applied as r235513., picking up two new tests
that need to be revised.  Also applied Martin's patch on top of it as
r2355134.

Thanks,
bin

2016-04-27  Martin Liska  

* tree-ssa-loop-ivopts.c (iv_ca_dump): Fix level of indentation.
(free_loop_data): Release vuses of groups.

>
> Richard.
>
>> Thanks,
>> bin
>>
>> 2016-04-19  Bin Cheng  
>>
>> * tree-ssa-loop-ivopts.c (struct iv): Use pointer to struct iv_use
>> instead of redundant use_id and boolean have_use_for.
>> (struct iv_use): Change sub_id into group_id.  Remove field next.
>> Move fields: related_cands, n_map_members, cost_map and selected
>> to ...
>> (struct iv_group): ... here.  New structure.
>> (struct iv_common_cand): Use structure declaration directly.
>> (struct ivopts_data, iv_ca, iv_ca_delta): Rename fields.
>> (MAX_CONSIDERED_USES): Rename macro to ...
>> (MAX_CONSIDERED_GROUPS): ... here.
>> (n_iv_uses, iv_use, n_iv_cands, iv_cand): Delete.
>> (dump_iv, dump_use, dump_cand): Refactor format of dump information.
>> (dump_uses): Rename to ...
>> (dump_groups): ... here.  Update all uses.
>> (tree_ssa_iv_optimize_init, alloc_iv): Update all uses.
>> (find_induction_variables): Refactor format of dump information.
>> (record_sub_use): Delete.
>> (record_use): Update all uses.
>> (record_group): New function.
>> (record_group_use, find_interesting_uses_op): Call above functions.
>> Update all uses.
>> (find_interesting_uses_cond): Ditto.
>> (group_compare_offset): New function.
>> (split_all_small_groups): Rename to ...
>> (split_small_address_groups_p): ... here.  Update all uses.
>> (split_address_groups):  Update all uses.
>> (find_interesting_uses): Refactor format of dump information.
>> (add_candidate_1): Update all uses.  Remove redundant check on iv,
>> base and step.
>> (add_candidate, record_common_cand): Remove 

Re: [PATCH GCC]Refactor IVOPT.

[Bin.Cheng]

On Mon, Apr 25, 2016 at 3:49 PM, Martin Liška  wrote:
> Hello.
>
> Please consider application of the following patch, it fixes
> a coding style issue and a memory leak.
Hi Martin,
Will do, thanks very much for the help.

Thanks,
bin
>
> Thanks,
> Martin

Re: [PATCH GCC]Refactor IVOPT.

[Martin Liška]

Hello.

Please consider application of the following patch, it fixes
a coding style issue and a memory leak.

Thanks,
Martin
>From 6afc975de0b6de76aa51b8c2ef741cd72c76dc75 Mon Sep 17 00:00:00 2001
From: marxin 
Date: Mon, 25 Apr 2016 13:50:41 +0200
Subject: [PATCH 1/4] Fix coding style and a memory leak in IVOPTS

gcc/ChangeLog:

2016-04-25  Martin Liska  

	* tree-ssa-loop-ivopts.c (iv_ca_dump): Fix level of indentation.
	(free_loop_data): Release vuses of groups.
---
 gcc/tree-ssa-loop-ivopts.c | 9 +
 1 file changed, 5 insertions(+), 4 deletions(-)

diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index 18c1773..9314363 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -6311,15 +6311,15 @@ iv_ca_dump (struct ivopts_data *data, FILE *file, struct iv_ca *ivs)
ivs->cand_cost, ivs->cand_use_cost.cost, ivs->cand_use_cost.complexity);
   bitmap_print (file, ivs->cands, "  candidates: ","\n");
 
-   for (i = 0; i < ivs->upto; i++)
+  for (i = 0; i < ivs->upto; i++)
 {
   struct iv_group *group = data->vgroups[i];
   struct cost_pair *cp = iv_ca_cand_for_group (ivs, group);
   if (cp)
-fprintf (file, "   group:%d --> iv_cand:%d, cost=(%d,%d)\n",
- group->id, cp->cand->id, cp->cost.cost, cp->cost.complexity);
+	fprintf (file, "   group:%d --> iv_cand:%d, cost=(%d,%d)\n",
+		 group->id, cp->cand->id, cp->cost.cost, cp->cost.complexity);
   else
-fprintf (file, "   group:%d --> ??\n", group->id);
+	fprintf (file, "   group:%d --> ??\n", group->id);
 }
 
   for (i = 1; i <= data->max_inv_id; i++)
@@ -7503,6 +7503,7 @@ free_loop_data (struct ivopts_data *data)
 
   for (j = 0; j < group->vuses.length (); j++)
 	free (group->vuses[j]);
+  group->vuses.release ();
 
   BITMAP_FREE (group->related_cands);
   for (j = 0; j < group->n_map_members; j++)
-- 
2.8.1

Re: [PATCH GCC]Refactor IVOPT.

[Richard Biener]

On Thu, Apr 21, 2016 at 7:26 PM, Bin Cheng  wrote:
> Hi,
> This patch refactors IVOPT in three major aspects:
> Firstly it rewrites iv_use groups.  Use group is originally introduced only 
> for address type uses, this patch makes it general to all (generic, compare, 
> address) types.  Currently generic/compare groups contain only one iv_use, 
> and compare groups can be extended to contain multiple uses.  As far as 
> generic use is concerned, it won't contain multiple uses because IVOPT reuses 
> one iv_use structure for generic uses at different places already.  This 
> change also cleanups algorithms as well as data structures.
> Secondly it implements group data structure in vector rather than in list as 
> originally.  List was used because it's easy to split.  Of course list is 
> hard to sort (For example, we use quadratic insertion sort now).  This 
> problem will become more critical since I plan to introduce fine-control over 
> splitting small address groups by checking if target supports load/store pair 
> instructions or not.  In this case address group needs to be sorted more than 
> once and against complex conditions, for example, memory loads in one basic 
> block should be sorted together in offset ascending order.  With vector 
> group, sorting can be done very efficiently with quick sort.
> Thirdly this patch cleanups/reformats IVOPT's dump information.  I think the 
> information is easier to read/test now.  Since change of dump information is 
> entangled with group data-structure change, it's hard to make it a standalone 
> patch.  Given this part patch is quite straightforward, I hope it won't be 
> confusing.
>
> Bootstrap and test on x86_64 and AArch64, no regressions.  I also checked 
> generated assembly for spec2k and spec2k6 on both platforms, turns out output 
> assembly is almost not changed except for several files.  After further 
> investigation, I can confirm the difference is cause by small change when 
> sorting groups. Given the original sorting condition as below:
> -  /* Sub use list is maintained in offset ascending order.  */
> -  if (addr_offset <= group->addr_offset)
> -{
> -  use->related_cands = group->related_cands;
> -  group->related_cands = NULL;
> -  use->next = group;
> -  data->iv_uses[id_group] = use;
> -}
> iv_uses with same addr_offset are sorted in reverse control flow order.  This 
> might be a typo since I don't remember any specific reason for it.  If this 
> patch sorts groups in the same way, there will be no difference in generated 
> assembly at all.  So this patch is a pure refactoring work which doesn't have 
> any functional change.
>
> Any comments?

Looks good to me.

Richard.

> Thanks,
> bin
>
> 2016-04-19  Bin Cheng  
>
> * tree-ssa-loop-ivopts.c (struct iv): Use pointer to struct iv_use
> instead of redundant use_id and boolean have_use_for.
> (struct iv_use): Change sub_id into group_id.  Remove field next.
> Move fields: related_cands, n_map_members, cost_map and selected
> to ...
> (struct iv_group): ... here.  New structure.
> (struct iv_common_cand): Use structure declaration directly.
> (struct ivopts_data, iv_ca, iv_ca_delta): Rename fields.
> (MAX_CONSIDERED_USES): Rename macro to ...
> (MAX_CONSIDERED_GROUPS): ... here.
> (n_iv_uses, iv_use, n_iv_cands, iv_cand): Delete.
> (dump_iv, dump_use, dump_cand): Refactor format of dump information.
> (dump_uses): Rename to ...
> (dump_groups): ... here.  Update all uses.
> (tree_ssa_iv_optimize_init, alloc_iv): Update all uses.
> (find_induction_variables): Refactor format of dump information.
> (record_sub_use): Delete.
> (record_use): Update all uses.
> (record_group): New function.
> (record_group_use, find_interesting_uses_op): Call above functions.
> Update all uses.
> (find_interesting_uses_cond): Ditto.
> (group_compare_offset): New function.
> (split_all_small_groups): Rename to ...
> (split_small_address_groups_p): ... here.  Update all uses.
> (split_address_groups):  Update all uses.
> (find_interesting_uses): Refactor format of dump information.
> (add_candidate_1): Update all uses.  Remove redundant check on iv,
> base and step.
> (add_candidate, record_common_cand): Remove redundant assert.
> (add_iv_candidate_for_biv): Update use.
> (add_iv_candidate_derived_from_uses): Update all uses.
> (add_iv_candidate_for_groups, record_important_candidates): Ditto.
> (alloc_use_cost_map): Ditto.
> (set_use_iv_cost, get_use_iv_cost): Rename to ...
> (set_group_iv_cost, get_group_iv_cost): ... here.  Update all uses.
> (determine_use_iv_cost_generic): Ditto.
> (determine_group_iv_cost_generic): Ditto.
> 

[PATCH GCC]Refactor IVOPT.

[Bin Cheng]

Hi,
This patch refactors IVOPT in three major aspects:
Firstly it rewrites iv_use groups.  Use group is originally introduced only for 
address type uses, this patch makes it general to all (generic, compare, 
address) types.  Currently generic/compare groups contain only one iv_use, and 
compare groups can be extended to contain multiple uses.  As far as generic use 
is concerned, it won't contain multiple uses because IVOPT reuses one iv_use 
structure for generic uses at different places already.  This change also 
cleanups algorithms as well as data structures.
Secondly it implements group data structure in vector rather than in list as 
originally.  List was used because it's easy to split.  Of course list is hard 
to sort (For example, we use quadratic insertion sort now).  This problem will 
become more critical since I plan to introduce fine-control over splitting 
small address groups by checking if target supports load/store pair 
instructions or not.  In this case address group needs to be sorted more than 
once and against complex conditions, for example, memory loads in one basic 
block should be sorted together in offset ascending order.  With vector group, 
sorting can be done very efficiently with quick sort.
Thirdly this patch cleanups/reformats IVOPT's dump information.  I think the 
information is easier to read/test now.  Since change of dump information is 
entangled with group data-structure change, it's hard to make it a standalone 
patch.  Given this part patch is quite straightforward, I hope it won't be 
confusing.

Bootstrap and test on x86_64 and AArch64, no regressions.  I also checked 
generated assembly for spec2k and spec2k6 on both platforms, turns out output 
assembly is almost not changed except for several files.  After further 
investigation, I can confirm the difference is cause by small change when 
sorting groups. Given the original sorting condition as below:
-  /* Sub use list is maintained in offset ascending order.  */
-  if (addr_offset <= group->addr_offset)
-{
-  use->related_cands = group->related_cands;
-  group->related_cands = NULL;
-  use->next = group;
-  data->iv_uses[id_group] = use;
-}
iv_uses with same addr_offset are sorted in reverse control flow order.  This 
might be a typo since I don't remember any specific reason for it.  If this 
patch sorts groups in the same way, there will be no difference in generated 
assembly at all.  So this patch is a pure refactoring work which doesn't have 
any functional change.

Any comments?

Thanks,
bin

2016-04-19  Bin Cheng  

* tree-ssa-loop-ivopts.c (struct iv): Use pointer to struct iv_use
instead of redundant use_id and boolean have_use_for.
(struct iv_use): Change sub_id into group_id.  Remove field next.
Move fields: related_cands, n_map_members, cost_map and selected
to ...
(struct iv_group): ... here.  New structure.
(struct iv_common_cand): Use structure declaration directly.
(struct ivopts_data, iv_ca, iv_ca_delta): Rename fields.
(MAX_CONSIDERED_USES): Rename macro to ...
(MAX_CONSIDERED_GROUPS): ... here.
(n_iv_uses, iv_use, n_iv_cands, iv_cand): Delete.
(dump_iv, dump_use, dump_cand): Refactor format of dump information.
(dump_uses): Rename to ...
(dump_groups): ... here.  Update all uses.
(tree_ssa_iv_optimize_init, alloc_iv): Update all uses.
(find_induction_variables): Refactor format of dump information.
(record_sub_use): Delete.
(record_use): Update all uses.
(record_group): New function.
(record_group_use, find_interesting_uses_op): Call above functions.
Update all uses.
(find_interesting_uses_cond): Ditto.
(group_compare_offset): New function.
(split_all_small_groups): Rename to ...
(split_small_address_groups_p): ... here.  Update all uses.
(split_address_groups):  Update all uses.
(find_interesting_uses): Refactor format of dump information.
(add_candidate_1): Update all uses.  Remove redundant check on iv,
base and step.
(add_candidate, record_common_cand): Remove redundant assert.
(add_iv_candidate_for_biv): Update use.
(add_iv_candidate_derived_from_uses): Update all uses.
(add_iv_candidate_for_groups, record_important_candidates): Ditto.
(alloc_use_cost_map): Ditto.
(set_use_iv_cost, get_use_iv_cost): Rename to ...
(set_group_iv_cost, get_group_iv_cost): ... here.  Update all uses.
(determine_use_iv_cost_generic): Ditto.
(determine_group_iv_cost_generic): Ditto.
(determine_use_iv_cost_address): Ditto.
(determine_group_iv_cost_address): Ditto.
(determine_use_iv_cost_condition): Ditto.
(determine_group_iv_cost_cond): Ditto.
(determine_use_iv_cost): Ditto.
(determine_group_iv_cost): Ditto.