[PATCH GCC]Refactor IVOPT.

Richard Biener richard.guenther@gmail.com
Fri Apr 22 07:20:00 GMT 2016


On Thu, Apr 21, 2016 at 7:26 PM, Bin Cheng <Bin.Cheng@arm.com> 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  <bin.cheng@arm.com>
>
>         * 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.
>         (set_autoinc_for_original_candidates): Update all uses.
>         (find_iv_candidates): Update all uses.  Refactor dump information.
>         (determine_use_iv_costs): Ditto.
>         (determine_iv_costs): Ditto.
>         (iv_ca_cand_for_use): Rename to ...
>         (iv_ca_cand_for_group): ... here.  Update all uses.
>         (iv_ca_add_use, iv_ca_add_group): Ditto.
>         (iv_ca_set_cp, iv_ca_cost, iv_ca_delta_add): Update all uses.
>         (iv_ca_delta_join, iv_ca_delta_reverse, iv_ca_delta_free): Ditto.
>         (iv_ca_new, iv_ca_dump, iv_ca_extend, iv_ca_narrow): Ditto.
>         (iv_ca_prune, cheaper_cost_with_cand, iv_ca_replace): Ditto.
>         (try_add_cand_for, try_improve_iv_set, find_optimal_iv_set): Ditto.
>         (create_new_iv, adjust_iv_update_pos): Ditto.
>         (rewrite_use_address): Delete.
>         (rewrite_use_address_1): Rename to ...
>         (rewrite_use_address): ... here.
>         (rewrite_use_compare): Update all uses.
>         (rewrite_use): Delete.
>         (rewrite_uses): Rename to ...
>         (rewrite_groups): ... here.  Update all uses.
>         (remove_unused_ivs, free_loop_data): Update all uses.
>         (tree_ssa_iv_optimize_finalize, tree_ssa_iv_optimize_loop): Ditto.
>
> gcc/testsuite/ChangeLog
> 2016-04-19  Bin Cheng  <bin.cheng@arm.com>
>
>         * gcc.dg/tree-ssa/pr64705.c: Revise check string.
>         * gcc.dg/tree-ssa/scev-9.c: Ditto.
>         * gcc.dg/tree-ssa/scev-10.c: Ditto.



More information about the Gcc-patches mailing list