Fw: [PATCH] ipa aliasing analysis

[Olga Golovanevsky <OLGA at il dot ibm dot com>]

This patch is an initial version of interprocedural
alias analysis (ipaa) for tree-profilinf branch. It is
based on the paper by Cooper and Kennedy:

http://www.cs.wisc.edu/~cs701-1/PAPERS/CooperKennedyPOPL89.pdf

The flag is "-fipa-alias".

The analysis calculates aliasing for pairs of formals. The
possible analysis results are: non_alias, must_alias,
may_alias and do_not_know. They can be seen in dump file
<file_name>.c.i02.alias, when trying the relevant testcases
(attached below).

The algorithm is initialized at callsites where aliasing info
is calculated based on interprocedural analysis, which is
very primitive right now: only combinations of local
arrays and formals are considered.

Although the alias info is calculated, it is in not yet
preserved for further optimization passes (any ideas
how it can be done correctly without loss of info?)

The patch also contains 'renaming' changes to clarify
partitioning between ipcp, ipaa and
ipa (common for both) functionalities.

Bootstraped on powerpc-apple-darwin7.6.0.

olga

ChangeLog:

      * common.opt (flag_ipa_alias): New flag.
      * ipa_prop.c (ipa_method): Renamed from ipcp_method.
      (ipa_callsite): Renamed form ipcp_callsite.
      (ipa_methodlist): Renamed from ipcp_methodlist.
      (ipa_methodlist_p): Renamed from ipcp_methodlist_p.
      (ipa_create_methodlist_node): Renamed from
      ipcp_create_methodlist_node.
      (ipa_methodlist_not_empty): Renamed from
      ipcp_methodlist_not_empty.
      (ipa_methodlist_method): Renamed from
      ipcp_methodlist_method.
      (ipa_methodlist_method_set): Renamed from
      ipcp_methodlist_method_set.
      (ipa_methodlist_next_method): Renamed from
      ipcp_methodlist_next_method.
      (ipa_methodlist_next_method_set): Renamed from
      ipcp_methodlist_next_method_set.
      (ipa_add_method): Renamed from ipcp_add_method.
      (ipa_remove_method): Renamed from ipcp_remove_method.
      (ipa_methodlist_init): Renamed from ipcp_methodlist_init.
      (ipa_callsite_param_count): Renamed from
      ipcp_callsite_param_count.
      (ipa_callsite_param_count_set): Renamed from
      ipcp_callsite_param_count_set.
      (ipa_callsite_param): Renamed from ipcp_callsite_param.
      (ipa_callsite_callee): Renamed from ipcp_callsite_callee.
      (ipa_callsite_param_set_type): Renamed from
      ipcp_callsite_param_set_type.
      (ipa_callsite_param_set_info_type_formal): Renamed from
      ipcp_callsite_param_set_info_type_formal.
      (ipa_callsite_param_set_info_type_int): Renamed from
      ipcp_callsite_param_set_info_type_int.
      (ipa_callsite_param_map_create): Renamed from
      ipcp_callsite_param_map_create.
      (ipa_callsite_tree): Renamed from ipcp_callsite_tree.
      (ipa_callsite_caller): Renamed from ipcp_callsite_caller.
      (ipa_callsite_compute_param): Renamed from
      ipcp_callsite_compute_param.
      (ipa_callsite_compute_count): Renamed from
      ipcp_callsite_compute_count.
      (ipa_method_formal_count): Renamed from
      ipcp_method_formal_count.
      (ipa_method_formal_count_set): Renamed from
      ipcp_method_formal_count_set.
      (ipa_method_is_modified): Renamed from
      ipcp_method_is_modified.
      (ipa_method_get_tree): Renamed from ipcp_method_get_tree.
      (ipa_method_tree_map_create): Renamed from
      ipcp_method_tree_map_create.
      (ipa_method_modify_create): Renamed from
      ipcp_method_modify_create.
      (ipa_method_modify_set): Renamed from ipcp_method_modify_set.
      (ipa_method_tree_map): Renamed from ipcp_method_tree_map.
      (ipa_method_compute_tree_map): Renamed from
      ipcp_method_compute_tree_map.
      (ipa_method_formal_compute_count): Renamed from
      ipcp_method_formal_compute_count.
      (ipa_method_formal_compute_count): Renamed from
      ipcp_method_formal_compute_count.
      (ipa_modify_walk_tree): Renamed from ipcp_modify_walk_tree.
      (ipa_modify_walk_tree_1): Renamed from
      ipcp_modify_walk_tree_1.
      (ipa_method_modify_init): Renamed from
      ipcp_method_modify_init.
      (ipa_method_compute_modify): Renamed from
      ipcp_method_compute_modify.
      (ipa_jf_get_info_type): Renamed from ipcp_jf_get_info_type.
      (ipa_driver): Renamed from ipcp_driver; new parameter.
      (ipa_init_stage): Renamed from ipcp_init_stage; new parameter.
      (ipa_free): Renamed from ipcp_free.
      (ipa_method_tree_print): Renamed from
      ipcp_method_tree_print.
      (ipa_method_modify_print): Renamed from
      ipcp_method_modify_print.
      (ipaa_structures_print, ipaa_callsite_param_trees_print,
      ipaa_callsite_addr_local_array_print,
      ipaa_method_alias_info_print,ipaa_callsite_alias_info_print,
      ipaa_method_create_alias_info, ipaa_method_alias_init,
      ipaa_method_set_num_pairs_args,
      ipaa_method_get_num_pairs_args, ipaa_method_compute_num_pairs,
      ipaa_method_set_pair_alias_info,
      ipaa_method_get_pair_alias_info,ipaa_method_set_alias_info,
      ipaa_method_get_alias_info): New functions.
      (ipaa_callsite_create_alias_info, ipaa_callsite_alias_init,
      ipaa_callsite_compute_num_pairs,
      ipaa_callsite_set_num_pairs_args,
      ipaa_callsite_get_num_pairs_args,
      ipaa_callsite_compute_param,
      ipaa_callsite_set_pair_alias_info,
      ipaa_callsite_get_pair_alias_info,
      ipaa_callsite_set_alias_info, ipaa_alias_info
      ipaa_callsite_get_alias_info): New functions.
      (ipaa_varslist): New structure.
      (ipaa_varslist_p): New typedef.
      (ipaa_create_varslist_node, ipaa_varslist_not_empty,
      ipaa_varslist_var, ipaa_varslist_var_set,
      ipaa_varslist_modified, ipaa_varslist_modified_set,
      ipaa_varslist_p ipaa_varslist_next_var,
      ipaa_varslist_next_var_set, ipaa_add_var,
      ipaa_destroy_varslist, ipaa_varslist_init,
      ipaa_varslist_is_modified, ipaa_varslist_call_expr,
      ipaa_varslist_call_expr_set, ipaa_print_varslist):
      New functions.
      (walk_tree_data): New structure.
      (walk_tree_data_p): New typedef.
      (ipaa_is_address_of_local_array,
      ipaa_callsites_init_aliasing,
      ipaa_varslist_find_var, ipaa_is_non_modified_formal,
      ipaa_callsites_init_aliasing,
      ipaa_method_compute_modify, ipaa_modify_walk_tree_1,
      ipaa_modify_walk_tree, ipaa_meet_alias_info,
      ipaa_propagate_stage, ipaa_insert_stage):
      New functions.
      (ipcp_driver, ipaa_driver): New functions.
      (pass_ipa_alias): New structure.
      * ipa_prop.h (ipa_jump_func): Renamed from ipcp_jump_func.
      (ipa_tree_map): Renamed from ipcp_tree_map.
      (ipa_modify): Renamed from ipcp_modified.
      (ipa_arg_num): Renamed from ipcp_arg_num in ipa_node.
      (ipa_param_tree): Renamed from ipcp_param_tree in ipa_node.
      (ipa_mod): Renamed from ipcp_mod in ipa_node.
      (ipaa_aliasing): New field in ipa_node structure.
      (ipaa_num_pairs_args): New field in ipa_node structure.
      (ipa_param_num): Renamed from ipcp_param_num.
      (ipa_param_map): Renamed from ipcp_param_map.
      (ipaa_num_pairs_arg): New field in ipa_edge structure.
      (ipaa_aliasing): New field in ipa_edge structure.
      (ipa_analysis_type, alias_info): New enums.
      (ipaa_driver): New declaration.
      * timervar.def (TV_IPA_ALIAS_ANALYSIS): New time var.
      * tree-optimize.c (pass_ipa_alias) : New ipa pass.
      * tree-pass.h (pass_ipa_alias): New ipa pass structure.

(See attached file: ipa-alias.txt) (See attached file: three_functions.c)
(See attached file: four_arrays.c)(See attached file: one_array.c)(See
attached file: array_formal.c)

Attachment: ipa-alias.txt
Description: Text document

Attachment: three_functions.c
Description: Binary data

Attachment: four_arrays.c
Description: Binary data

Attachment: one_array.c
Description: Binary data

Attachment: array_formal.c
Description: Binary data