On Thu, Apr 21, 2016 at 7:26 PM, Bin Cheng <bin.ch...@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.ch...@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.ch...@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.
