Hi, this is cleaned up version of the patch. I removed unfinished bits, fixed propagation, cleaned it up and fixed fallout.
At present modref does bare minimum of what it can do and only collects base/ref alias sets of accesses to disambiguate uding them. I have followup patches adding more features. Like pure-const pass, modref is both local and IPA pass (so early optimizations benefits from it). It works with both LTO and non-LTO. LTO tracking is bit harder since instead of alias sets one needs to track types alias sets are derived from (because alias sets change from compile to link time). For that reason I had to exprt reference_alias_ptr_type_1 so I can lookup same type as get_alias_set does. There is an assert checking that both functions are in sync. Building cc1plus with LTO I get: Alias oracle query stats: refs_may_alias_p: 59342803 disambiguations, 69597406 queries ref_maybe_used_by_call_p: 139290 disambiguations, 60227579 queries call_may_clobber_ref_p: 17604 disambiguations, 23290 queries nonoverlapping_component_refs_p: 0 disambiguations, 37088 queries nonoverlapping_refs_since_match_p: 19439 disambiguations, 55079 must overlaps, 76966 queries aliasing_component_refs_p: 54891 disambiguations, 756375 queries TBAA oracle: 22475946 disambiguations 51373119 queries 15188806 are in alias set 0 8345975 queries asked about the same object 124 queries asked about the same alias set 0 access volatile 3811042 are dependent in the DAG 1551226 are aritificially in conflict with void * Modref stats: modref use: 6315 disambiguations, 60861 queries modref clobber: 1788334 disambiguations, 2706342 queries 1223123 tbaa querries (0.451947 per modref querry) PTA query stats: pt_solution_includes: 922059 disambiguations, 13392569 queries pt_solutions_intersect: 1018189 disambiguations, 11428599 queries This ignores the disambiguations enabled by the local modref done during early optimization. On cc1plus it seems that modref querries are cheap (usually converging after checking 0.45 alias sets :) and quite effective for stores with similar number of disambiguations as the PTA oracle (that is surprisingly high). Load disambiguations are quite low. Parlty this is becuase we only track lods that binds locally, since otherwise we risk that there is optimized out load that will be still present in prevailing version of the function and may lead to memory trap. Incrementally it may be worth to start tracking info about ealry optimized out loads, but that needs more work. Other problem I noticed while looking to dumps is that gimple, tree and rtl datastrutures are unions and we drop all accesses to them to alias set 0 that makes the anaysis not very effetive on GCC itself. This analysis of all those uninlined tree/rtl/gimple predicates quite ineffective that is bit sad. For tramp3d I get: Alias oracle query stats: refs_may_alias_p: 2261286 disambiguations, 2525487 queries ref_maybe_used_by_call_p: 7402 disambiguations, 2298244 queries call_may_clobber_ref_p: 232 disambiguations, 232 queries nonoverlapping_component_refs_p: 0 disambiguations, 4145 queries nonoverlapping_refs_since_match_p: 329 disambiguations, 10232 must overlaps, 10648 queries aliasing_component_refs_p: 858 disambiguations, 34731 queries TBAA oracle: 972943 disambiguations 1808294 queries 130565 are in alias set 0 497083 queries asked about the same object 0 queries asked about the same alias set 0 access volatile 207388 are dependent in the DAG 315 are aritificially in conflict with void * Modref stats: modref use: 950 disambiguations, 5474 queries modref clobber: 30035 disambiguations, 81948 queries 41671 tbaa querries (0.508505 per modref querry) PTA query stats: pt_solution_includes: 383095 disambiguations, 593201 queries pt_solutions_intersect: 147774 disambiguations, 434255 queries So again the loads are disambiguated less. There is a new testsuite failure: ./testsuite/gfortran/gfortran.sum:FAIL: gfortran.dg/assumed_type_9.f90 -O2 execution test ./testsuite/gfortran/gfortran.sum:FAIL: gfortran.dg/assumed_type_9.f90 -Os execution test This is an pre-existing issue where fortran frontend builds array descriptors in type that contains pointer to actual data while mixes them up with data type describing array of unknown type. The two structures are not TBAA compatible without LTO and thus leads to misoptimization. Same wrong code can be triggered by forcing inlining to happen and disabling ccp pass (that otherwise hides the problem), so I think we could handle this incrementally as independent bug - I would like to get basic code in so we can test additional patches in foreseeable future. While there are several areas for improvements but I think it is not in shape for mainline and rest can be dealt with incrementally. Bootstrapped/regtested x86_64-linux including ada, d and go. I plan to commit it after bit more testing tomorrow. 2020-09-19 David Cepelik <d...@dcepelik.cz> Jan Hubicka <hubi...@ucw.cz> * Makefile.in: Add ipa-modref.c and ipa-modref-tree.c. * alias.c: (reference_alias_ptr_type_1): Export. * alias.h (reference_alias_ptr_type_1): Declare. * common.opt (fipa-modref): New. * gengtype.c (open_base_files): Add ipa-modref-tree.h and ipa-modref.h * ipa-modref-tree.c: New file. * ipa-modref-tree.h: New file. * ipa-modref.c: New file. * ipa-modref.h: New file. * lto-section-in.c (lto_section_name): Add ipa_modref. * lto-streamer.h (enum lto_section_type): Add LTO_section_ipa_modref. * opts.c (default_options_table): Enable ipa-modref at -O1+. * params.opt (-param=modref-max-bases, -param=modref-max-refs, -param=modref-max-tests): New params. * passes.def: Schedule pass_modref and pass_ipa_modref. * timevar.def (TV_IPA_MODREF): New timevar. (TV_TREE_MODREF): New timevar. * tree-pass.h (make_pass_modref): Declare. (make_pass_ipa_modref): Declare. * tree-ssa-alias.c (dump_alias_stats): Include ipa-modref-tree.h and ipa-modref.h (alias_stats): Add modref_use_may_alias, modref_use_no_alias, modref_clobber_may_alias, modref_clobber_no_alias, modref_tests. (dump_alias_stats): Dump new stats. (nonoverlapping_array_refs_p): Fix formating. (modref_may_conflict): New function. (ref_maybe_used_by_call_p_1): Use it. (call_may_clobber_ref_p_1): Use it. (call_may_clobber_ref_p): Update. (stmt_may_clobber_ref_p_1): Update. * tree-ssa-alias.h (call_may_clobber_ref_p_1): Update. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 79e854aa938..c710bad27b1 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1419,6 +1419,8 @@ OBJS = \ ipa-visibility.o \ ipa-inline-analysis.o \ ipa-inline-transform.o \ + ipa-modref.o \ + ipa-modref-tree.o \ ipa-predicate.o \ ipa-profile.o \ ipa-prop.o \ @@ -2587,6 +2589,8 @@ GTFILES = $(CPPLIB_H) $(srcdir)/input.h $(srcdir)/coretypes.h \ $(srcdir)/alias.c $(srcdir)/bitmap.c $(srcdir)/cselib.c $(srcdir)/cgraph.c \ $(srcdir)/ipa-prop.c $(srcdir)/ipa-cp.c $(srcdir)/ipa-utils.h \ $(srcdir)/ipa-param-manipulation.h $(srcdir)/ipa-sra.c $(srcdir)/dbxout.c \ + $(srcdir)/ipa-modref.h $(srcdir)/ipa-modref.c \ + $(srcdir)/ipa-modref-tree.h \ $(srcdir)/signop.h \ $(srcdir)/dwarf2out.h \ $(srcdir)/dwarf2asm.c \ diff --git a/gcc/alias.c b/gcc/alias.c index df85f07ee9a..1cb702be2ce 100644 --- a/gcc/alias.c +++ b/gcc/alias.c @@ -737,7 +737,7 @@ get_deref_alias_set (tree t) adjusted to point to the outermost component reference that can be used for assigning an alias set. */ -static tree +tree reference_alias_ptr_type_1 (tree *t) { tree inner; diff --git a/gcc/alias.h b/gcc/alias.h index 4453d9723ce..807af957f02 100644 --- a/gcc/alias.h +++ b/gcc/alias.h @@ -36,6 +36,7 @@ extern int objects_must_conflict_p (tree, tree); extern int nonoverlapping_memrefs_p (const_rtx, const_rtx, bool); extern void dump_alias_stats_in_alias_c (FILE *s); tree reference_alias_ptr_type (tree); +tree reference_alias_ptr_type_1 (tree *); bool alias_ptr_types_compatible_p (tree, tree); int compare_base_decls (tree, tree); bool refs_same_for_tbaa_p (tree, tree); diff --git a/gcc/common.opt b/gcc/common.opt index dd68c61ae1d..b833b98dfb8 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -1825,6 +1825,10 @@ fipa-bit-cp Common Report Var(flag_ipa_bit_cp) Optimization Perform interprocedural bitwise constant propagation. +fipa-modref +Common Report Var(flag_ipa_modref) Optimization +Perform interprocedural modref analysis + fipa-profile Common Report Var(flag_ipa_profile) Init(0) Optimization Perform interprocedural profile propagation. diff --git a/gcc/gengtype.c b/gcc/gengtype.c index 981577481af..a59a8823f82 100644 --- a/gcc/gengtype.c +++ b/gcc/gengtype.c @@ -1726,7 +1726,7 @@ open_base_files (void) "except.h", "output.h", "cfgloop.h", "target.h", "lto-streamer.h", "target-globals.h", "ipa-ref.h", "cgraph.h", "symbol-summary.h", "ipa-prop.h", "ipa-fnsummary.h", "dwarf2out.h", "omp-general.h", - "omp-offload.h", NULL + "omp-offload.h", "ipa-modref-tree.h", "ipa-modref.h", NULL }; const char *const *ifp; outf_p gtype_desc_c; diff --git a/gcc/ipa-modref.c b/gcc/ipa-modref.c new file mode 100644 index 00000000000..f982ce94a75 --- /dev/null +++ b/gcc/ipa-modref.c @@ -0,0 +1,1376 @@ +/* Search for references that a functions loads or stores. + Copyright (C) 2020 Free Software Foundation, Inc. + Contributed by David Cepelik and Jan Hubicka + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +/* Mod/ref pass records summary about loads and stores performed by the + function. This is later used by alias analysis to disambiguate memory + accesses across function calls. The summary has a form of decision tree and + contains: + + - base alias set + and for each: + - ref alias set + + In future more information will be tracked. + + This file contains a tree pass and an IPA pass. Both performs the same + analys however tree pass is executed during early and late optimization + passes to propagate info downwards in the compilation order. IPA pass + propagates across the callgraph and is able to handle recursion and works on + whole program during link-time analysis. + + LTO mode differs from the local mode by not recroding alias sets but types + that are translated to alias sets later. This is necessary in order stream + the information becaue the alias sets are rebuild at stream-in time and may + not correspond to ones seen during analsis. For this reason part of analysis + is duplicated. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple.h" +#include "alloc-pool.h" +#include "tree-pass.h" +#include "gimple-iterator.h" +#include "tree-dfa.h" +#include "cgraph.h" +#include "ipa-utils.h" +#include "symbol-summary.h" +#include "gimple-pretty-print.h" +#include "gimple-walk.h" +#include "print-tree.h" +#include "tree-streamer.h" +#include "alias.h" +#include "calls.h" +#include "ipa-modref-tree.h" +#include "ipa-modref.h" + +/* Class (from which there is one global instance) that holds modref summaries + for all analyzed functions. */ +class GTY((user)) modref_summaries + : public fast_function_summary <modref_summary *, va_gc> +{ +public: + modref_summaries (symbol_table *symtab) + : fast_function_summary <modref_summary *, va_gc> (symtab) {} + virtual void insert (cgraph_node *, modref_summary *state); + virtual void duplicate (cgraph_node *src_node, + cgraph_node *dst_node, + modref_summary *src_data, + modref_summary *dst_data); + /* This flag controls whether newly inserted functions should be analyzed + in IPA or normal mode. Functions inserted betweehn IPA analysis and + ipa-modref pass execution needs to be analyzed in IPA mode while all + other insertions leads to normal analysis. */ + bool ipa; +}; + +/* Global variable holding all modref summaries. */ +static GTY(()) fast_function_summary <modref_summary *, va_gc> *summaries; + +/* Summary for a single function which this pass produces. */ + +modref_summary::modref_summary () + : loads (NULL), stores (NULL), loads_lto (NULL), + stores_lto (NULL), finished (0) +{ +} + +modref_summary::~modref_summary () +{ + if (loads) + ggc_delete (loads); + if (stores) + ggc_delete (stores); + if (loads_lto) + ggc_delete (loads_lto); + if (stores_lto) + ggc_delete (stores_lto); +} + +/* Dump records TT to OUT. */ + +static void +dump_records (modref_records *tt, FILE *out) +{ + fprintf (out, " Limits: %i bases, %i refs\n", + (int)tt->max_bases, (int)tt->max_refs); + if (tt->every_base) + { + fprintf (out, " Every base\n"); + return; + } + size_t i; + modref_base_node <alias_set_type> *n; + FOR_EACH_VEC_SAFE_ELT (tt->bases, i, n) + { + fprintf (out, " Base %i: alias set %i\n", (int)i, n->base); + if (n->every_ref) + { + fprintf (out, " Every ref\n"); + continue; + } + size_t j; + modref_ref_node <alias_set_type> *r; + FOR_EACH_VEC_SAFE_ELT (n->refs, j, r) + { + fprintf (out, " Ref %i: alias set %i\n", (int)j, r->ref); + } + } +} + +/* Dump records TT to OUT. */ + +static void +dump_lto_records (modref_records_lto *tt, FILE *out) +{ + fprintf (out, " Limits: %i bases, %i refs\n", + (int)tt->max_bases, (int)tt->max_refs); + if (tt->every_base) + { + fprintf (out, " Every base\n"); + return; + } + size_t i; + modref_base_node <tree> *n; + FOR_EACH_VEC_SAFE_ELT (tt->bases, i, n) + { + fprintf (out, " Base %i:", (int)i); + print_generic_expr (dump_file, n->base); + fprintf (out, " (alias set %i)\n", + get_alias_set (n->base)); + if (n->every_ref) + { + fprintf (out, " Every ref\n"); + continue; + } + size_t j; + modref_ref_node <tree> *r; + FOR_EACH_VEC_SAFE_ELT (n->refs, j, r) + { + fprintf (out, " Ref %i:", (int)j); + print_generic_expr (dump_file, r->ref); + fprintf (out, " (alias set %i)\n", + get_alias_set (r->ref)); + } + } +} + +/* Dump summary. */ + +void +modref_summary::dump (FILE *out) +{ + if (loads) + { + fprintf (out, " loads:\n"); + dump_records (loads, out); + } + if (stores) + { + fprintf (out, " stores:\n"); + dump_records (stores, out); + } + if (loads_lto) + { + fprintf (out, " LTO loads:\n"); + dump_lto_records (loads_lto, out); + } + if (stores_lto) + { + fprintf (out, " LTO stores:\n"); + dump_lto_records (stores_lto, out); + } +} + + +/* Get function summary for FUNC if it exists, return NULL otherwise. */ + +modref_summary * +get_modref_function_summary (cgraph_node *func) +{ + /* Avoid creation of the summary too early (e.g. when front-end calls us). */ + if (!summaries) + return NULL; + + /* A single function body may be represented by multiple symbols with + different visibility. For example, if FUNC is an interposable alias, + we don't want to return anything, even if we have summary for the target + function. */ + enum availability avail; + func = func->function_or_virtual_thunk_symbol + (&avail, cgraph_node::get (current_function_decl)); + if (avail <= AVAIL_INTERPOSABLE) + return NULL; + + /* Attempt to get summary for FUNC. If analysis of FUNC hasn't finished yet, + don't return anything. */ + modref_summary *r = summaries->get (func); + if (r && r->finished) + return r; + + return NULL; +} + +/* Record access into the modref_records data structure. */ + +static void +record_access (modref_records *tt, ao_ref *ref) +{ + alias_set_type base_set = !flag_strict_aliasing ? 0 + : ao_ref_base_alias_set (ref); + alias_set_type ref_set = !flag_strict_aliasing ? 0 + : (ao_ref_alias_set (ref)); + if (dump_file) + { + fprintf (dump_file, " - Recording base_set=%i ref_set=%i\n", + base_set, ref_set); + } + tt->insert (base_set, ref_set); +} + +/* IPA version of record_access_tree. */ + +static void +record_access_lto (modref_records_lto *tt, ao_ref *ref) +{ + /* get_alias_set sometimes use different type to compute the alias set + than TREE_TYPE (base). Do same adjustments. */ + tree base_type = NULL_TREE, ref_type = NULL_TREE; + if (flag_strict_aliasing) + { + tree base; + + base = ref->ref; + while (handled_component_p (base)) + base = TREE_OPERAND (base, 0); + + base_type = reference_alias_ptr_type_1 (&base); + + if (!base_type) + base_type = TREE_TYPE (base); + else + base_type = TYPE_REF_CAN_ALIAS_ALL (base_type) + ? NULL_TREE : TREE_TYPE (base_type); + + tree ref_expr = ref->ref; + ref_type = reference_alias_ptr_type_1 (&ref_expr); + + if (!ref_type) + ref_type = TREE_TYPE (ref_expr); + else + ref_type = TYPE_REF_CAN_ALIAS_ALL (ref_type) + ? NULL_TREE : TREE_TYPE (ref_type); + + /* Sanity check that we are in sync with what get_alias_set does. */ + gcc_checking_assert ((!base_type && !ao_ref_base_alias_set (ref)) + || get_alias_set (base_type) + == ao_ref_base_alias_set (ref)); + gcc_checking_assert ((!ref_type && !ao_ref_alias_set (ref)) + || get_alias_set (ref_type) + == ao_ref_alias_set (ref)); + + /* Do not bother to record types that have no meaningful alias set. + Also skip variably modified types since these go to local streams. */ + if (base_type && (!get_alias_set (base_type) + || variably_modified_type_p (base_type, NULL_TREE))) + base_type = NULL_TREE; + if (ref_type && (!get_alias_set (ref_type) + || variably_modified_type_p (ref_type, NULL_TREE))) + ref_type = NULL_TREE; + } + if (dump_file) + { + fprintf (dump_file, " - Recording base type:"); + print_generic_expr (dump_file, base_type); + fprintf (dump_file, " (alias set %i) ref type:", + base_type ? get_alias_set (base_type) : 0); + print_generic_expr (dump_file, ref_type); + fprintf (dump_file, " (alias set %i)\n", + ref_type ? get_alias_set (ref_type) : 0); + } + + tt->insert (base_type, ref_type); +} + +/* Returns true if and only if we should store the access to EXPR. + Some accesses, e.g. loads from automatic variables, are not interesting. */ + +static bool +record_access_p (tree expr) +{ + /* Non-escaping memory is fine */ + tree t = get_base_address (expr); + if (t && (INDIRECT_REF_P (t) + || TREE_CODE (t) == MEM_REF + || TREE_CODE (t) == TARGET_MEM_REF) + && TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME + && !ptr_deref_may_alias_global_p (TREE_OPERAND (t, 0))) + { + if (dump_file) + fprintf (dump_file, " - Non-escaping memory, ignoring.\n"); + return false; + } + + /* Automatic variables are fine. */ + if (DECL_P (t) + && auto_var_in_fn_p (t, current_function_decl)) + { + if (dump_file) + fprintf (dump_file, " - Automatic variable, ignoring.\n"); + return false; + } + + /* Read-only variables are fine. */ + if (DECL_P (t) && TREE_READONLY (t)) + { + if (dump_file) + fprintf (dump_file, " - Read-only variable, ignoring.\n"); + return false; + } + + return true; +} + +/* Return true if ECF flags says that stores can be ignored. */ + +static bool +ignore_stores_p (tree caller, int flags) +{ + if (flags & ECF_PURE) + return true; + if ((flags & (ECF_NORETURN | ECF_NOTHROW)) == (ECF_NORETURN | ECF_NOTHROW) + || (!opt_for_fn (caller, flag_exceptions) && (flags & ECF_NORETURN))) + return true; + return false; +} + +/* Analyze function call STMT in function F. */ + +static bool +analyze_call (modref_summary *cur_summary, + gimple *stmt) +{ + /* Check flags on the function call. In certain cases, analysis can be + simplified. */ + int flags = gimple_call_flags (stmt); + if (flags & (ECF_CONST | ECF_NOVOPS)) + { + if (dump_file) + fprintf (dump_file, + " - ECF_CONST | ECF_NOVOPS, ignoring all stores and all loads " + "except for args.\n"); + return true; + } + + /* Pure functions do not affect global memory. Stores by functions which are + noreturn and do not throw can safely be ignored. */ + bool ignore_stores = ignore_stores_p (current_function_decl, flags); + + /* Next, we try to get the callee's function declaration. The goal is to + merge their summary with ours. */ + tree callee = gimple_call_fndecl (stmt); + + /* Check if this is an indirect call. */ + if (!callee) + { + /* If the indirect call does not write memory, our store summary is + unaffected, but we have to discard our loads summary (we don't know + anything about the loads that the called function performs). */ + if (ignore_stores) + { + if (dump_file) + fprintf (dump_file, " - Indirect call which does not write memory, " + "discarding loads.\n"); + if (cur_summary->loads) + cur_summary->loads->collapse (); + if (cur_summary->loads_lto) + cur_summary->loads_lto->collapse (); + return true; + } + if (dump_file) + fprintf (dump_file, " - Indirect call.\n"); + return false; + } + + struct cgraph_node *callee_node = cgraph_node::get_create (callee); + + /* We can not safely optimize based on summary of calle if it does + not always bind to current def: it is possible that memory load + was optimized out earlier which may not happen in the interposed + variant. */ + if (!callee_node->binds_to_current_def_p ()) + { + if (dump_file) + fprintf (dump_file, " - May be interposed: collapsing loads.\n"); + if (cur_summary->loads) + cur_summary->loads->collapse (); + if (cur_summary->loads_lto) + cur_summary->loads_lto->collapse (); + } + + /* If this is a recursive call, the target summary is the same as ours, so + there's nothing to do. */ + if (recursive_call_p (current_function_decl, callee)) + { + if (dump_file) + fprintf (dump_file, " - Skipping recursive call.\n"); + return true; + } + + gcc_assert (callee_node != NULL); + + /* Get the function symbol and its availability. */ + enum availability avail; + callee_node = callee_node->function_symbol (&avail); + if (avail <= AVAIL_INTERPOSABLE) + { + /* Keep stores summary, but discard all loads for interposable function + symbols. */ + if (ignore_stores) + { + if (cur_summary->loads) + cur_summary->loads->collapse (); + if (cur_summary->loads_lto) + cur_summary->loads_lto->collapse (); + return true; + } + if (dump_file) + fprintf (dump_file, " - Function availability <= AVAIL_INTERPOSABLE.\n"); + return false; + } + + /* Get callee's modref summary. As above, if there's no summary, we either + have to give up or, if stores are ignored, we can just purge loads. */ + modref_summary *callee_summary = summaries->get (callee_node); + if (!callee_summary) + { + if (ignore_stores) + { + if (cur_summary->loads) + cur_summary->loads->collapse (); + if (cur_summary->loads_lto) + cur_summary->loads_lto->collapse (); + return true; + } + if (dump_file) + fprintf (dump_file, " - No modref summary available for callee.\n"); + return false; + } + + /* Merge with callee's summary. */ + if (cur_summary->loads) + cur_summary->loads->merge (callee_summary->loads); + if (cur_summary->loads_lto) + cur_summary->loads_lto->merge (callee_summary->loads_lto); + if (!ignore_stores) + { + if (cur_summary->stores) + cur_summary->stores->merge (callee_summary->stores); + if (cur_summary->stores_lto) + cur_summary->stores_lto->merge (callee_summary->stores_lto); + } + + return true; +} + +/* Helper for analyze_stmt. */ + +static bool +analyze_load (gimple *, tree, tree op, void *data) +{ + modref_summary *summary = (modref_summary *)data; + + if (dump_file) + { + fprintf (dump_file, " - Analyzing load: "); + print_generic_expr (dump_file, op); + fprintf (dump_file, "\n"); + } + + if (!record_access_p (op)) + return false; + + ao_ref r; + ao_ref_init (&r, op); + + if (summary->loads) + record_access (summary->loads, &r); + if (summary->loads_lto) + record_access_lto (summary->loads_lto, &r); + return false; +} + +/* Helper for analyze_stmt. */ + +static bool +analyze_store (gimple *, tree, tree op, void *data) +{ + modref_summary *summary = (modref_summary *)data; + + if (dump_file) + { + fprintf (dump_file, " - Analyzing store: "); + print_generic_expr (dump_file, op); + fprintf (dump_file, "\n"); + } + + if (!record_access_p (op)) + return false; + + ao_ref r; + ao_ref_init (&r, op); + + if (summary->stores) + record_access (((modref_summary *)data)->stores, &r); + if (summary->stores_lto) + record_access_lto (((modref_summary *)data)->stores_lto, &r); + return false; +} + +/* Analyze statement STMT of function F. + If IPA is true do not merge in side effects of calls. */ + +static bool +analyze_stmt (modref_summary *summary, gimple *stmt, bool ipa) +{ + /* Analyze all loads and stores in STMT. */ + walk_stmt_load_store_ops (stmt, summary, + analyze_load, analyze_store); + /* or call analyze_load_ipa, analyze_store_ipa */ + + switch (gimple_code (stmt)) + { + case GIMPLE_ASM: + /* If the ASM statement does not read nor write memory, there's nothing + to do. Otherwise just give up. */ + if (!gimple_asm_clobbers_memory_p (as_a <gasm *> (stmt))) + return true; + if (dump_file) + fprintf (dump_file, " - Function contains GIMPLE_ASM statement " + "which clobbers memory.\n"); + return false; + case GIMPLE_CALL: + if (!ipa) + return analyze_call (summary, stmt); + return true; + default: + /* Nothing to do for other types of statements. */ + return true; + } +} + +/* Analyze function F. IPA indicates whether we're running in tree mode (false) + or the IPA mode (true). */ + +static void +analyze_function (function *f, bool ipa) +{ + if (dump_file) + fprintf (dump_file, "modref analyzing '%s' (ipa=%i)...\n", + function_name (f), ipa); + + /* Don't analyze this function if it's compiled with -fno-strict-aliasing. */ + if (!flag_ipa_modref) + return; + + /* Initialize the summary. */ + if (!summaries) + summaries = new (ggc_alloc <modref_summaries> ()) + modref_summaries (symtab); + else /* Remove existing summary if we are re-running the pass. */ + summaries->remove (cgraph_node::get (f->decl)); + + ((modref_summaries *)summaries)->ipa = ipa; + + modref_summary *summary = summaries->get_create (cgraph_node::get (f->decl)); + + /* Compute no-LTO summaries when local optimization is going to happen. */ + bool nolto = (!ipa || ((!flag_lto || flag_fat_lto_objects) && !in_lto_p) + || (in_lto_p && !flag_wpa + && flag_incremental_link != INCREMENTAL_LINK_LTO)); + + /* Compute LTO when LTO streaming is going to happen. */ + bool lto = ipa && ((flag_lto && !in_lto_p) + || flag_wpa + || flag_incremental_link == INCREMENTAL_LINK_LTO); + + /* Create and initialize summary for F. + Note that summaries may be already allocated from previous + run of the pass. */ + if (nolto) + { + gcc_assert (!summary->loads); + summary->loads + = new (ggc_alloc <modref_tree<alias_set_type> > ()) + modref_records (param_modref_max_bases, + param_modref_max_refs); + gcc_assert (!summary->stores); + summary->stores + = new (ggc_alloc <modref_tree<alias_set_type> > ()) + modref_records (param_modref_max_bases, + param_modref_max_refs); + } + if (lto) + { + gcc_assert (!summary->loads_lto); + summary->loads_lto + = new (ggc_alloc <modref_tree<tree> > ()) + modref_records_lto (param_modref_max_bases, + param_modref_max_refs); + gcc_assert (!summary->stores_lto); + summary->stores_lto + = new (ggc_alloc <modref_tree<tree> > ()) + modref_records_lto (param_modref_max_bases, + param_modref_max_refs); + } + summary->finished = false; + + /* Analyze each statement in each basic block of the function. If the + statement cannot be analyzed (for any reason), the entire function cannot + be analyzed by modref. */ + basic_block bb; + FOR_EACH_BB_FN (bb, f) + { + gimple_stmt_iterator si; + for (si = gsi_after_labels (bb); !gsi_end_p (si); gsi_next (&si)) + { + if (!analyze_stmt (summary, gsi_stmt (si), ipa)) + { + cgraph_node *fnode = cgraph_node::get (current_function_decl); + summaries->remove (fnode); + if (dump_file) + fprintf (dump_file, + " - modref done with result: not tracked.\n"); + return; + } + } + } + + if (!ipa) + summary->finished = true; + + if (dump_file) + { + fprintf (dump_file, " - modref done with result: tracked.\n"); + summary->dump (dump_file); + } +} + +/* Callback for generate_summary. */ + +static void +modref_generate (void) +{ + struct cgraph_node *node; + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY (node) + { + function *f = DECL_STRUCT_FUNCTION (node->decl); + if (!f) + continue; + push_cfun (f); + analyze_function (f, true); + pop_cfun (); + } +} + +/* Called when a new function is inserted to callgraph late. */ + +void +modref_summaries::insert (struct cgraph_node *node, modref_summary *) +{ + if (!DECL_STRUCT_FUNCTION (node->decl)) + return; + push_cfun (DECL_STRUCT_FUNCTION (node->decl)); + analyze_function (DECL_STRUCT_FUNCTION (node->decl), ipa); + pop_cfun (); +} + +/* Called when new clone is inserted to callgraph late. */ + +void +modref_summaries::duplicate (cgraph_node *, cgraph_node *, + modref_summary *src_data, + modref_summary *dst_data) +{ + dst_data->finished = src_data->finished; + if (src_data->stores) + { + dst_data->stores = new (ggc_alloc <modref_tree<alias_set_type> > ()) + modref_records + (src_data->stores->max_bases, + src_data->stores->max_refs); + dst_data->stores->merge (src_data->stores); + } + if (src_data->loads) + { + dst_data->loads = new (ggc_alloc <modref_tree<alias_set_type> > ()) + modref_records + (src_data->loads->max_bases, + src_data->loads->max_refs); + dst_data->loads->merge (src_data->loads); + } + if (src_data->stores_lto) + { + dst_data->stores_lto = new (ggc_alloc <modref_tree<tree> > ()) + modref_records_lto + (src_data->stores_lto->max_bases, + src_data->stores_lto->max_refs); + dst_data->stores_lto->merge (src_data->stores_lto); + } + if (src_data->loads_lto) + { + dst_data->loads_lto = new (ggc_alloc <modref_tree<tree> > ()) + modref_records_lto + (src_data->stores_lto->max_bases, + src_data->stores_lto->max_refs); + dst_data->loads_lto->merge (src_data->loads_lto); + } +} + +namespace +{ +/* Definition of the modref pass on GIMPLE. */ +const pass_data pass_data_modref = { + GIMPLE_PASS, + "modref", + OPTGROUP_IPA, + TV_TREE_MODREF, + (PROP_cfg | PROP_ssa), + 0, + 0, + 0, + 0, +}; + +class pass_modref : public gimple_opt_pass +{ + public: + pass_modref (gcc::context *ctxt) + : gimple_opt_pass (pass_data_modref, ctxt) {} + + ~pass_modref () + { + ggc_delete (summaries); + summaries = NULL; + } + + /* opt_pass methods: */ + opt_pass *clone () + { + return new pass_modref (m_ctxt); + } + virtual bool gate (function *) + { + return flag_ipa_modref; + } + virtual unsigned int execute (function *); +}; + +/* Encode TT to the output block OB using the summary streaming API. */ + +static void +write_modref_records (modref_records_lto *tt, struct output_block *ob) +{ + streamer_write_uhwi (ob, tt->max_bases); + streamer_write_uhwi (ob, tt->max_refs); + + streamer_write_uhwi (ob, tt->every_base); + streamer_write_uhwi (ob, vec_safe_length (tt->bases)); + size_t i; + modref_base_node <tree> *base_node; + FOR_EACH_VEC_SAFE_ELT (tt->bases, i, base_node) + { + stream_write_tree (ob, base_node->base, true); + + streamer_write_uhwi (ob, base_node->every_ref); + streamer_write_uhwi (ob, vec_safe_length (base_node->refs)); + size_t j; + modref_ref_node <tree> *ref_node; + FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node) + { + stream_write_tree (ob, ref_node->ref, true); + } + } +} + +/* Read a modref_tree from the input block IB using the data from DATA_IN. + This assumes that the tree was encoded using write_modref_tree. + Either nolto_ret or lto_ret is initialized by the tree depending whether + LTO streaming is expcted or not. */ + +void +read_modref_records (lto_input_block *ib, struct data_in *data_in, + modref_records **nolto_ret, + modref_records_lto **lto_ret) +{ + size_t max_bases = streamer_read_uhwi (ib); + size_t max_refs = streamer_read_uhwi (ib); + + /* Decide whether we want to turn LTO data types to non-LTO (i.e. when + LTO re-streaming is not going to happen). */ + if (flag_wpa || flag_incremental_link == INCREMENTAL_LINK_LTO) + *lto_ret = new (ggc_alloc <modref_records_lto> ()) modref_records_lto + (max_bases, max_refs); + else + *nolto_ret = new (ggc_alloc <modref_records> ()) modref_records + (max_bases, max_refs); + + size_t every_base = streamer_read_uhwi (ib); + size_t nbase = streamer_read_uhwi (ib); + + gcc_assert (!every_base || nbase == 0); + if (every_base) + { + if (*nolto_ret) + (*nolto_ret)->collapse (); + if (*lto_ret) + (*lto_ret)->collapse (); + } + for (size_t i = 0; i < nbase; i++) + { + tree base_tree = stream_read_tree (ib, data_in); + modref_base_node <alias_set_type> *nolto_base_node = NULL; + modref_base_node <tree> *lto_base_node = NULL; + + /* At stream in time we have LTO alias info. Check if we streamed in + something obviously unnecessary. Do not glob types by alias sets; + it is not 100% clear that ltrans types will get merged same way. + Types may get refined based on ODR type conflicts. */ + if (base_tree && !get_alias_set (base_tree)) + { + if (dump_file) + { + fprintf (dump_file, "Streamed in alias set 0 type "); + print_generic_expr (dump_file, base_tree); + fprintf (dump_file, "\n"); + } + base_tree = NULL; + } + + if (*nolto_ret) + nolto_base_node = (*nolto_ret)->insert_base (base_tree + ? get_alias_set (base_tree) + : 0); + if (*lto_ret) + lto_base_node = (*lto_ret)->insert_base (base_tree); + size_t every_ref = streamer_read_uhwi (ib); + size_t nref = streamer_read_uhwi (ib); + + gcc_assert (!every_ref || nref == 0); + if (every_ref) + { + if (nolto_base_node) + nolto_base_node->collapse (); + if (lto_base_node) + lto_base_node->collapse (); + } + for (size_t j = 0; j < nref; j++) + { + tree ref_tree = stream_read_tree (ib, data_in); + + if (ref_tree && !get_alias_set (ref_tree)) + { + if (dump_file) + { + fprintf (dump_file, "Streamed in alias set 0 type "); + print_generic_expr (dump_file, ref_tree); + fprintf (dump_file, "\n"); + } + base_tree = NULL; + } + + if (nolto_base_node) + nolto_base_node->insert_ref (ref_tree ? get_alias_set (ref_tree) + : 0, max_refs); + if (lto_base_node) + lto_base_node->insert_ref (ref_tree, max_refs); + } + } +} + +/* Callback for write_summary. */ + +static void +modref_write () +{ + struct output_block *ob = create_output_block (LTO_section_ipa_modref); + lto_symtab_encoder_t encoder = ob->decl_state->symtab_node_encoder; + unsigned int count = 0; + int i; + + if (!summaries) + { + streamer_write_uhwi (ob, 0); + streamer_write_char_stream (ob->main_stream, 0); + produce_asm (ob, NULL); + destroy_output_block (ob); + return; + } + + for (i = 0; i < lto_symtab_encoder_size (encoder); i++) + { + symtab_node *snode = lto_symtab_encoder_deref (encoder, i); + cgraph_node *cnode = dyn_cast <cgraph_node *> (snode); + + if (cnode && cnode->definition && !cnode->alias + && summaries->get (cnode)) + count++; + } + streamer_write_uhwi (ob, count); + + for (i = 0; i < lto_symtab_encoder_size (encoder); i++) + { + symtab_node *snode = lto_symtab_encoder_deref (encoder, i); + cgraph_node *cnode = dyn_cast <cgraph_node *> (snode); + + if (cnode && cnode->definition && !cnode->alias) + { + + modref_summary *r = summaries->get (cnode); + + if (!r) + continue; + + streamer_write_uhwi (ob, lto_symtab_encoder_encode (encoder, cnode)); + + streamer_write_uhwi (ob, r->loads_lto ? 1 : 0); + streamer_write_uhwi (ob, r->stores_lto ? 1 : 0); + if (r->loads_lto) + write_modref_records (r->loads_lto, ob); + if (r->stores_lto) + write_modref_records (r->stores_lto, ob); + } + } + streamer_write_char_stream (ob->main_stream, 0); + produce_asm (ob, NULL); + destroy_output_block (ob); +} + +static void +read_section (struct lto_file_decl_data *file_data, const char *data, + size_t len) +{ + const struct lto_function_header *header + = (const struct lto_function_header *) data; + const int cfg_offset = sizeof (struct lto_function_header); + const int main_offset = cfg_offset + header->cfg_size; + const int string_offset = main_offset + header->main_size; + struct data_in *data_in; + unsigned int i; + unsigned int f_count; + + lto_input_block ib ((const char *) data + main_offset, header->main_size, + file_data->mode_table); + + data_in + = lto_data_in_create (file_data, (const char *) data + string_offset, + header->string_size, vNULL); + f_count = streamer_read_uhwi (&ib); + for (i = 0; i < f_count; i++) + { + struct cgraph_node *node; + lto_symtab_encoder_t encoder; + + unsigned int index = streamer_read_uhwi (&ib); + encoder = file_data->symtab_node_encoder; + node = dyn_cast <cgraph_node *> (lto_symtab_encoder_deref (encoder, + index)); + + modref_summary *modref_sum = summaries->get_create (node); + modref_sum->finished = false; + int have_loads = streamer_read_uhwi (&ib); + int have_stores = streamer_read_uhwi (&ib); + gcc_assert (!modref_sum->loads_lto + && !modref_sum->stores_lto + && !modref_sum->loads + && !modref_sum->stores); + if (have_loads) + read_modref_records (&ib, data_in, + &modref_sum->loads, + &modref_sum->loads_lto); + if (have_stores) + read_modref_records (&ib, data_in, + &modref_sum->stores, + &modref_sum->stores_lto); + if (dump_file) + { + fprintf (dump_file, "Read modref for %s\n", + node->dump_name ()); + modref_sum->dump (dump_file); + } + if (flag_ltrans) + modref_sum->finished = true; + } + + lto_free_section_data (file_data, LTO_section_ipa_modref, NULL, data, + len); + lto_data_in_delete (data_in); +} + +/* Callback for read_summary. */ + +static void +modref_read (void) +{ + struct lto_file_decl_data **file_data_vec = lto_get_file_decl_data (); + struct lto_file_decl_data *file_data; + unsigned int j = 0; + + if (!summaries) + summaries = new (ggc_alloc <modref_summaries> ()) + modref_summaries (symtab); + ((modref_summaries *)summaries)->ipa = true; + + while ((file_data = file_data_vec[j++])) + { + size_t len; + const char *data = lto_get_summary_section_data (file_data, + LTO_section_ipa_modref, + &len); + if (data) + read_section (file_data, data, len); + else + /* Fatal error here. We do not want to support compiling ltrans units + with different version of compiler or different flags than the WPA + unit, so this should never happen. */ + fatal_error (input_location, + "IPA modref summary is missing in input file"); + } +} + +/* Definition of the modref IPA pass. */ +const pass_data pass_data_ipa_modref = +{ + IPA_PASS, /* type */ + "modref", /* name */ + OPTGROUP_IPA, /* optinfo_flags */ + TV_IPA_MODREF, /* tv_id */ + 0, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + ( TODO_dump_symtab ), /* todo_flags_finish */ +}; + +class pass_ipa_modref : public ipa_opt_pass_d +{ +public: + pass_ipa_modref (gcc::context *ctxt) + : ipa_opt_pass_d (pass_data_ipa_modref, ctxt, + modref_generate, /* generate_summary */ + modref_write, /* write_summary */ + modref_read, /* read_summary */ + modref_write, /* write_optimization_summary */ + modref_read, /* read_optimization_summary */ + NULL, /* stmt_fixup */ + 0, /* function_transform_todo_flags_start */ + NULL, /* function_transform */ + NULL) /* variable_transform */ + {} + + /* opt_pass methods: */ + opt_pass *clone () { return new pass_ipa_modref (m_ctxt); } + virtual bool gate (function *) + { + return true; + } + virtual unsigned int execute (function *); + +}; + +} + +unsigned int pass_modref::execute (function *f) +{ + /* If new function is being added during IPA, we can skip analysis. */ + if (summaries && ((modref_summaries *)summaries)->ipa) + return 0; + analyze_function (f, false); + return 0; +} + +gimple_opt_pass * +make_pass_modref (gcc::context *ctxt) +{ + return new pass_modref (ctxt); +} + +ipa_opt_pass_d * +make_pass_ipa_modref (gcc::context *ctxt) +{ + return new pass_ipa_modref (ctxt); +} + +/* Skip edges from and to nodes without ipa_pure_const enabled. + Ignore not available symbols. */ + +static bool +ignore_edge (struct cgraph_edge *e) +{ + enum availability avail; + cgraph_node *callee = e->callee->function_or_virtual_thunk_symbol + (&avail, e->caller); + + return (avail <= AVAIL_INTERPOSABLE + || !summaries->get (callee) + || flags_from_decl_or_type (e->callee->decl) + & (ECF_CONST | ECF_NOVOPS)); +} + +/* Run the IPA pass. This will take a function's summaries and calls and + construct new summaries which represent a transitive closure. So that + summary of an analyzed function contains information about the loads and + stores that the function or any function that it calls does. */ + +unsigned int pass_ipa_modref::execute (function *) +{ + if (!summaries) + return 0; + + struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, + symtab->cgraph_count); + int order_pos; + order_pos = ipa_reduced_postorder (order, true, ignore_edge); + int i; + + /* Iterate over all strongly connected components in post-order. */ + for (i = 0; i < order_pos; i++) + { + bool its_hopeless = false; + modref_records *loads = NULL; + modref_records *stores = NULL; + modref_records_lto *loads_lto = NULL; + modref_records_lto *stores_lto = NULL; + + /* Get the component's representative. That's just any node in the + component from which we can traverse the entire component. */ + struct cgraph_node *component_node = order[i]; + cgraph_node *first = NULL; + + if (dump_file) + fprintf (dump_file, "Start of SCC component\n"); + + /* Walk the component. CUR is the current node of the component that's + being processed. */ + for (struct cgraph_node *cur = component_node; cur && !its_hopeless; + cur = ((struct ipa_dfs_info *) cur->aux)->next_cycle) + { + /* Merge in summaries from CUR. */ + modref_summary *cur_summary = summaries->get (cur); + + if (dump_file) + fprintf (dump_file, " Processing %s\n", + cur->dump_name ()); + + /* We don't know anything about CUR, hence we cannot tell anything + about the entire component. */ + if (!cur_summary) + { + if (dump_file) + fprintf (dump_file, " No summary\n"); + its_hopeless = true; + break; + } + + /* Summaries are all going to be same, pick first ones and merge + everything in. */ + if (!first) + { + first = cur; + loads = cur_summary->loads; + stores = cur_summary->stores; + loads_lto = cur_summary->loads_lto; + stores_lto = cur_summary->stores_lto; + } + for (cgraph_edge *e = cur->indirect_calls; e; e = e->next_callee) + { + if (e->indirect_info->ecf_flags & (ECF_CONST | ECF_NOVOPS)) + continue; + if (ignore_stores_p (cur->decl, e->indirect_info->ecf_flags)) + { + if (dump_file) + fprintf (dump_file, " Indirect call: " + "collapsing loads\n"); + if (loads) + loads->collapse (); + if (loads_lto) + loads_lto->collapse (); + } + else + { + if (dump_file) + fprintf (dump_file, " Indirect call: giving up\n"); + its_hopeless = true; + } + } + + /* Walk every function that CUR calls and merge its summary. */ + for (cgraph_edge *callee_edge = cur->callees; callee_edge; + callee_edge = callee_edge->next_callee) + { + int flags = flags_from_decl_or_type (callee_edge->callee->decl); + modref_summary *callee_summary; + struct cgraph_node *callee; + + if (flags & (ECF_CONST | ECF_NOVOPS)) + continue; + + if (dump_file) + fprintf (dump_file, " Call to %s\n", + cur->dump_name ()); + + /* We can not safely optimize based on summary of calle if it + does not always bind to current def: it is possible that + memory load was optimized out earlier which may not happen in + the interposed variant. */ + if (!callee_edge->binds_to_current_def_p ()) + { + if (loads) + loads->collapse (); + if (loads_lto) + loads_lto->collapse (); + if (dump_file) + fprintf (dump_file, " May not bind local;" + " collapsing loads\n"); + } + + /* Get the callee and its summary. */ + enum availability avail; + callee = callee_edge->callee->function_or_virtual_thunk_symbol + (&avail, cur); + + /* See if we can derive something from ECF flags. Be careful on + not skipping calls within the SCC component: we must merge + all their summaries. + If we switch to iterative dataflow that may be necessary + for future improvements this may go away. */ + if (callee->aux + && ((struct ipa_dfs_info *)cur->aux)->scc_no + == ((struct ipa_dfs_info *)callee->aux)->scc_no) + flags = 0; + + bool ignore_stores = ignore_stores_p (cur->decl, flags); + + /* We don't know anything about CALLEE, hence we cannot tell + anything about the entire component. */ + + if (avail <= AVAIL_INTERPOSABLE + || !(callee_summary = summaries->get (callee))) + { + if (!ignore_stores) + { + its_hopeless = true; + if (dump_file && avail <= AVAIL_INTERPOSABLE) + fprintf (dump_file, " Call target interposable" + "or not available\n"); + else if (dump_file) + fprintf (dump_file, " No call target summary\n"); + break; + } + else + { + if (loads) + loads->collapse (); + if (loads_lto) + loads_lto->collapse (); + if (dump_file && avail <= AVAIL_INTERPOSABLE) + fprintf (dump_file, " Call target interposable" + "or not available; collapsing loads\n"); + else if (dump_file) + fprintf (dump_file, " No call target summary;" + " collapsing loads\n"); + continue; + } + } + + /* Merge in callee's information. */ + if (callee_summary->loads + && callee_summary->loads != loads) + loads->merge (callee_summary->loads); + if (callee_summary->stores + && callee_summary->stores != stores) + stores->merge (callee_summary->stores); + if (callee_summary->loads_lto + && callee_summary->loads_lto != loads_lto) + loads_lto->merge (callee_summary->loads_lto); + if (callee_summary->stores_lto + && callee_summary->stores_lto != stores_lto) + stores_lto->merge (callee_summary->stores_lto); + } + } + + /* At this time, ipa_loads and ipa_stores contain information + about all loads and stores done by any of the component's nodes and + all functions that any of the nodes calls. We will now propagate + this information to all nodes in the component. Therefore, we will + walk the component one more time to do it. */ + for (struct cgraph_node *cur = component_node; cur; + cur = ((struct ipa_dfs_info *) cur->aux)->next_cycle) + { + modref_summary *cur_summary = summaries->get (cur); + if (!cur_summary) + { + /* The function doesn't have a summary. We must have noticed + that during the first pass and the hopeless flag must + therefore be set. Skip the function. */ + gcc_assert (its_hopeless); + } + else if (its_hopeless) + { + if (dump_file) + fprintf (dump_file, "Cleared modref info for %s\n", + cur->dump_name ()); + summaries->remove (cur); + } + else + { + if (cur == first) + ; + else + { + if (loads) + cur_summary->loads->merge (loads); + if (stores) + cur_summary->stores->merge (stores); + if (loads_lto) + cur_summary->loads_lto->merge (loads_lto); + if (stores_lto) + cur_summary->stores_lto->merge (stores_lto); + } + cur_summary->finished = true; + if (dump_file) + { + fprintf (dump_file, "Propagated modref for %s%s%s\n", + cur->dump_name (), + TREE_READONLY (cur->decl) ? " (const)" : "", + DECL_PURE_P (cur->decl) ? " (pure)" : ""); + cur_summary->dump (dump_file); + } + } + } + } + ((modref_summaries *)summaries)->ipa = false; + ipa_free_postorder_info (); + return 0; +} + +#include "gt-ipa-modref.h" diff --git a/gcc/ipa-modref.h b/gcc/ipa-modref.h new file mode 100644 index 00000000000..6f979200cc2 --- /dev/null +++ b/gcc/ipa-modref.h @@ -0,0 +1,48 @@ +/* Search for references that a functions loads or stores. + Copyright (C) 2019 Free Software Foundation, Inc. + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#ifndef IPA_MODREF_H +#define IPA_MODREF_H + +typedef modref_tree <alias_set_type> modref_records; +typedef modref_tree <tree> modref_records_lto; + +/* Single function summary. */ + +struct GTY(()) modref_summary +{ + /* Load and stores in function (transitively closed to all callees) */ + modref_records *loads; + modref_records *stores; + + /* The same but using tree types rather than alias sets. This is necessary + to make the information streamable for LTO but is also more verbose + and thus more likely to hit the limits. */ + modref_records_lto *loads_lto; + modref_records_lto *stores_lto; + bool finished; + + modref_summary (); + ~modref_summary (); + void dump (FILE *); +}; + +modref_summary *get_modref_function_summary (cgraph_node *func); + +#endif diff --git a/gcc/ipa-modref-tree.c b/gcc/ipa-modref-tree.c new file mode 100644 index 00000000000..e37dee67fa3 --- /dev/null +++ b/gcc/ipa-modref-tree.c @@ -0,0 +1,236 @@ +/* Data structure for the modref pass. + Copyright (C) 2020 Free Software Foundation, Inc. + Contributed by David Cepelik and Jan Hubicka + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "ipa-modref-tree.h" +#include "selftest.h" + +#if CHECKING_P + + +static void +test_insert_search_collapse () +{ + modref_base_node<alias_set_type> *base_node; + modref_ref_node<alias_set_type> *ref_node; + + modref_tree<alias_set_type> *t = new modref_tree<alias_set_type>(1, 2); + ASSERT_FALSE (t->every_base); + + /* Insert into an empty tree. */ + t->insert (1, 2); + ASSERT_NE (t->bases, NULL); + ASSERT_EQ (t->bases->length (), 1); + ASSERT_FALSE (t->every_base); + ASSERT_EQ (t->search (2), NULL); + + base_node = t->search (1); + ASSERT_NE (base_node, NULL); + ASSERT_EQ (base_node->base, 1); + ASSERT_NE (base_node->refs, NULL); + ASSERT_EQ (base_node->refs->length (), 1); + ASSERT_EQ (base_node->search (1), NULL); + + ref_node = base_node->search (2); + ASSERT_NE (ref_node, NULL); + ASSERT_EQ (ref_node->ref, 2); + + /* Insert when base exists but ref does not. */ + t->insert (1, 3); + ASSERT_NE (t->bases, NULL); + ASSERT_EQ (t->bases->length (), 1); + ASSERT_EQ (t->search (1), base_node); + ASSERT_EQ (t->search (2), NULL); + ASSERT_NE (base_node->refs, NULL); + ASSERT_EQ (base_node->refs->length (), 2); + + ref_node = base_node->search (3); + ASSERT_NE (ref_node, NULL); + + /* Insert when base and ref exist, but access is not dominated by nor + dominates other accesses. */ + t->insert (1, 2); + ASSERT_EQ (t->bases->length (), 1); + ASSERT_EQ (t->search (1), base_node); + + ref_node = base_node->search (2); + ASSERT_NE (ref_node, NULL); + + /* Insert when base and ref exist and access is dominated. */ + t->insert (1, 2); + ASSERT_EQ (t->search (1), base_node); + ASSERT_EQ (base_node->search (2), ref_node); + + /* Insert ref to trigger ref list collapse for base 1. */ + t->insert (1, 4); + ASSERT_EQ (t->search (1), base_node); + ASSERT_EQ (base_node->refs, NULL); + ASSERT_EQ (base_node->search (2), NULL); + ASSERT_EQ (base_node->search (3), NULL); + ASSERT_TRUE (base_node->every_ref); + + /* Further inserts to collapsed ref list are ignored. */ + t->insert (1, 5); + ASSERT_EQ (t->search (1), base_node); + ASSERT_EQ (base_node->refs, NULL); + ASSERT_EQ (base_node->search (2), NULL); + ASSERT_EQ (base_node->search (3), NULL); + ASSERT_TRUE (base_node->every_ref); + + /* Insert base to trigger base list collapse. */ + t->insert (5, 6); + ASSERT_TRUE (t->every_base); + ASSERT_EQ (t->bases, NULL); + ASSERT_EQ (t->search (1), NULL); + + /* Further inserts to collapsed base list are ignored. */ + t->insert (7, 8); + ASSERT_TRUE (t->every_base); + ASSERT_EQ (t->bases, NULL); + ASSERT_EQ (t->search (1), NULL); +} + +static void +test_merge () +{ + modref_tree<alias_set_type> *t1, *t2; + modref_base_node<alias_set_type> *base_node; + + t1 = new modref_tree<alias_set_type>(3, 4); + t1->insert (1, 1); + t1->insert (1, 2); + t1->insert (1, 3); + t1->insert (2, 1); + t1->insert (3, 1); + + t2 = new modref_tree<alias_set_type>(10, 10); + t2->insert (1, 2); + t2->insert (1, 3); + t2->insert (1, 4); + t2->insert (3, 2); + t2->insert (3, 3); + t2->insert (3, 4); + t2->insert (3, 5); + + t1->merge (t2); + + ASSERT_FALSE (t1->every_base); + ASSERT_NE (t1->bases, NULL); + ASSERT_EQ (t1->bases->length (), 3); + + base_node = t1->search (1); + ASSERT_NE (base_node->refs, NULL); + ASSERT_FALSE (base_node->every_ref); + ASSERT_EQ (base_node->refs->length (), 4); + + base_node = t1->search (2); + ASSERT_NE (base_node->refs, NULL); + ASSERT_FALSE (base_node->every_ref); + ASSERT_EQ (base_node->refs->length (), 1); + + base_node = t1->search (3); + ASSERT_EQ (base_node->refs, NULL); + ASSERT_TRUE (base_node->every_ref); +} + + +void +modref_tree_c_tests () +{ + test_insert_search_collapse (); + test_merge (); +} + +#endif + +void +gt_ggc_mx (modref_tree < int >*const &tt) +{ + if (tt->bases) + { + ggc_test_and_set_mark (tt->bases); + gt_ggc_mx (tt->bases); + } +} + +void +gt_ggc_mx (modref_tree < tree_node * >*const &tt) +{ + if (tt->bases) + { + ggc_test_and_set_mark (tt->bases); + gt_ggc_mx (tt->bases); + } +} + +void gt_pch_nx (modref_tree<int>* const&) {} +void gt_pch_nx (modref_tree<tree_node*>* const&) {} +void gt_pch_nx (modref_tree<int>* const&, gt_pointer_operator, void *) {} +void gt_pch_nx (modref_tree<tree_node*>* const&, gt_pointer_operator, void *) {} + +void gt_ggc_mx (modref_base_node<int>* &b) +{ + ggc_test_and_set_mark (b); + if (b->refs) + { + ggc_test_and_set_mark (b->refs); + gt_ggc_mx (b->refs); + } +} + +void gt_ggc_mx (modref_base_node<tree_node*>* &b) +{ + ggc_test_and_set_mark (b); + if (b->refs) + { + ggc_test_and_set_mark (b->refs); + gt_ggc_mx (b->refs); + } + if (b->base) + gt_ggc_mx (b->base); +} + +void gt_pch_nx (modref_base_node<int>*) {} +void gt_pch_nx (modref_base_node<tree_node*>*) {} +void gt_pch_nx (modref_base_node<int>*, gt_pointer_operator, void *) {} +void gt_pch_nx (modref_base_node<tree_node*>*, gt_pointer_operator, void *) {} + +void gt_ggc_mx (modref_ref_node<int>* &r) +{ + ggc_test_and_set_mark (r); +} + +void gt_ggc_mx (modref_ref_node<tree_node*>* &r) +{ + ggc_test_and_set_mark (r); + if (r->ref) + gt_ggc_mx (r->ref); +} + +void gt_pch_nx (modref_ref_node<int>* ) {} +void gt_pch_nx (modref_ref_node<tree_node*>*) {} +void gt_pch_nx (modref_ref_node<int>*, gt_pointer_operator, void *) {} +void gt_pch_nx (modref_ref_node<tree_node*>*, gt_pointer_operator, void *) {} + + diff --git a/gcc/ipa-modref-tree.h b/gcc/ipa-modref-tree.h new file mode 100644 index 00000000000..3bdd3058aa1 --- /dev/null +++ b/gcc/ipa-modref-tree.h @@ -0,0 +1,253 @@ +/* Data structure for the modref pass. + Copyright (C) 2020 Free Software Foundation, Inc. + Contributed by David Cepelik and Jan Hubicka + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +#ifndef GCC_MODREF_TREE_H +#define GCC_MODREF_TREE_H + +struct ipa_modref_summary; + + +template <typename T> +struct GTY((user)) modref_ref_node +{ + T ref; + + modref_ref_node (T ref): + ref (ref) + {} +}; + +/* Base of an access. */ +template <typename T> +struct GTY((user)) modref_base_node +{ + T base; + vec <modref_ref_node <T> *, va_gc> *refs; + bool every_ref; + + modref_base_node (T base): + base (base), + refs (NULL), + every_ref (false) {} + + /* Search REF; return NULL if failed. */ + modref_ref_node <T> *search (T ref) + { + size_t i; + modref_ref_node <T> *n; + FOR_EACH_VEC_SAFE_ELT (refs, i, n) + if (n->ref == ref) + return n; + return NULL; + } + + /* Insert REF; collapse tree if there are more than MAX_REFS. */ + modref_ref_node <T> *insert_ref (T ref, size_t max_refs) + { + modref_ref_node <T> *ref_node; + + /* If the node is collapsed, don't do anything. */ + if (every_ref) + return NULL; + + if (!ref) + { + collapse (); + return NULL; + } + + /* Otherwise, insert a node for the ref of the access under the base. */ + ref_node = search (ref); + if (ref_node) + return ref_node; + + /* Collapse the node if too full already. */ + if (refs && refs->length () >= max_refs) + { + if (dump_file) + fprintf (dump_file, "--param param=modref-max-refs limit reached\n"); + collapse (); + return NULL; + } + + ref_node = new (ggc_alloc <modref_ref_node <T> > ())modref_ref_node <T> + (ref); + vec_safe_push (refs, ref_node); + return ref_node; + } + + void collapse () + { + vec_free (refs); + refs = NULL; + every_ref = true; + } +}; + +/* Access tree for a single function. */ +template <typename T> +struct GTY((user)) modref_tree +{ + vec <modref_base_node <T> *, va_gc> *bases; + size_t max_bases; + size_t max_refs; + bool every_base; + + modref_tree (size_t max_bases, size_t max_refs): + bases (NULL), + max_bases (max_bases), + max_refs (max_refs), + every_base (false) {} + + modref_base_node <T> *insert_base (T base) + { + modref_base_node <T> *base_node; + + /* If the node is collapsed, don't do anything. */ + if (every_base) + return NULL; + + /* Otherwise, insert a node for the base of the access into the tree. */ + base_node = search (base); + if (base_node) + return base_node; + + /* Collapse the node if too full already. */ + if (bases && bases->length () >= max_bases) + { + if (dump_file) + fprintf (dump_file, "--param param=modref-max-bases limit reached\n"); + collapse (); + return NULL; + } + + base_node = new (ggc_alloc <modref_base_node <T> > ()) + modref_base_node <T> (base); + vec_safe_push (bases, base_node); + return base_node; + } + + /* Insert memory access to the tree. */ + void insert (T base, T ref) + { + modref_base_node <T> *base_node; + + base_node = insert_base (base); + + if (!base && !ref) + { + collapse (); + return; + } + if (!base_node) + return; + gcc_assert (search (base) != NULL); + + base_node->insert_ref (ref, max_refs); + if (!base && base_node->every_ref) + { + collapse (); + return; + } + } + + /* Merge OTHER into the tree. */ + void merge (modref_tree <T> *other) + { + if (!other) + return; + if (other->every_base) + { + collapse (); + return; + } + + size_t i, j; + modref_base_node <T> *base_node, *my_base_node; + modref_ref_node <T> *ref_node, *my_ref_node; + FOR_EACH_VEC_SAFE_ELT (other->bases, i, base_node) + { + my_base_node = insert_base (base_node->base); + if (!my_base_node) + continue; + + if (base_node->every_ref) + { + my_base_node->collapse (); + continue; + } + + FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node) + { + my_ref_node = my_base_node->insert_ref (ref_node->ref, max_refs); + if (!my_ref_node) + continue; + } + } + } + + /* Search BASE in tree; return NULL if failed. */ + modref_base_node <T> *search (T base) + { + size_t i; + modref_base_node <T> *n; + FOR_EACH_VEC_SAFE_ELT (bases, i, n) + if (n->base == base) + return n; + return NULL; + } + + void collapse () + { + vec_free (bases); + bases = NULL; + every_base = true; + } +}; + +void modref_c_tests (); + +void gt_ggc_mx (modref_tree <int>* const&); +void gt_ggc_mx (modref_tree <tree_node*>* const&); +void gt_pch_nx (modref_tree <int>* const&); +void gt_pch_nx (modref_tree <tree_node*>* const&); +void gt_pch_nx (modref_tree <int>* const&, gt_pointer_operator op, void *cookie); +void gt_pch_nx (modref_tree <tree_node*>* const&, gt_pointer_operator op, + void *cookie); + +void gt_ggc_mx (modref_base_node <int>*); +void gt_ggc_mx (modref_base_node <tree_node*>* &); +void gt_pch_nx (modref_base_node <int>* const&); +void gt_pch_nx (modref_base_node <tree_node*>* const&); +void gt_pch_nx (modref_base_node <int>* const&, gt_pointer_operator op, + void *cookie); +void gt_pch_nx (modref_base_node <tree_node*>* const&, gt_pointer_operator op, + void *cookie); + +void gt_ggc_mx (modref_ref_node <int>*); +void gt_ggc_mx (modref_ref_node <tree_node*>* &); +void gt_pch_nx (modref_ref_node <int>* const&); +void gt_pch_nx (modref_ref_node <tree_node*>* const&); +void gt_pch_nx (modref_ref_node <int>* const&, gt_pointer_operator op, + void *cookie); +void gt_pch_nx (modref_ref_node <tree_node*>* const&, gt_pointer_operator op, + void *cookie); + +#endif diff --git a/gcc/lto-section-in.c b/gcc/lto-section-in.c index 8a38fa27d7c..c12bc8a74b3 100644 --- a/gcc/lto-section-in.c +++ b/gcc/lto-section-in.c @@ -56,6 +56,7 @@ const char *lto_section_name[LTO_N_SECTION_TYPES] = "lto", "ipa_sra", "odr_types", + "ipa_modref", }; /* Hooks so that the ipa passes can call into the lto front end to get diff --git a/gcc/lto-streamer.h b/gcc/lto-streamer.h index 8c98c96e368..b465a5e9c18 100644 --- a/gcc/lto-streamer.h +++ b/gcc/lto-streamer.h @@ -227,6 +227,7 @@ enum lto_section_type LTO_section_lto, LTO_section_ipa_sra, LTO_section_odr_types, + LTO_section_ipa_modref, LTO_N_SECTION_TYPES /* Must be last. */ }; diff --git a/gcc/opts.c b/gcc/opts.c index c5c60581f70..3c4a0b540b4 100644 --- a/gcc/opts.c +++ b/gcc/opts.c @@ -466,6 +466,7 @@ static const struct default_options default_options_table[] = { OPT_LEVELS_1_PLUS_NOT_DEBUG, OPT_finline_functions_called_once, NULL, 1 }, { OPT_LEVELS_1_PLUS_NOT_DEBUG, OPT_fmove_loop_invariants, NULL, 1 }, { OPT_LEVELS_1_PLUS_NOT_DEBUG, OPT_fssa_phiopt, NULL, 1 }, + { OPT_LEVELS_1_PLUS_NOT_DEBUG, OPT_fipa_modref, NULL, 1 }, { OPT_LEVELS_1_PLUS_NOT_DEBUG, OPT_ftree_bit_ccp, NULL, 1 }, { OPT_LEVELS_1_PLUS_NOT_DEBUG, OPT_ftree_dse, NULL, 1 }, { OPT_LEVELS_1_PLUS_NOT_DEBUG, OPT_ftree_pta, NULL, 1 }, diff --git a/gcc/params.opt b/gcc/params.opt index f39e5d1a012..1d864047ad2 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -872,6 +872,18 @@ Maximum size of a single store merging region in bytes. Common Joined UInteger Var(param_switch_conversion_branch_ratio) Init(8) IntegerRange(1, 65536) Param Optimization The maximum ratio between array size and switch branches for a switch conversion to take place. +-param=modref-max-bases= +Common Joined UInteger Var(param_modref_max_bases) Init(32) +Maximum number of bases stored in each modref tree. + +-param=modref-max-refs= +Common Joined UInteger Var(param_modref_max_refs) Init(16) +Maximum number of refs stored in each modref tree. + +-param=modref-max-tests= +Common Joined UInteger Var(param_modref_max_tests) Init(64) +Maximum number of tests perofmed by modref query + -param=tm-max-aggregate-size= Common Joined UInteger Var(param_tm_max_aggregate_size) Init(9) Param Optimization Size in bytes after which thread-local aggregates should be instrumented with the logging functions instead of save/restore pairs. diff --git a/gcc/passes.def b/gcc/passes.def index c0098d755bf..f865bdc19ac 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -91,6 +91,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_dse); NEXT_PASS (pass_cd_dce); NEXT_PASS (pass_phiopt, true /* early_p */); + NEXT_PASS (pass_modref); NEXT_PASS (pass_tail_recursion); NEXT_PASS (pass_convert_switch); NEXT_PASS (pass_cleanup_eh); @@ -156,6 +157,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_ipa_fn_summary); NEXT_PASS (pass_ipa_inline); NEXT_PASS (pass_ipa_pure_const); + NEXT_PASS (pass_ipa_modref); NEXT_PASS (pass_ipa_free_fn_summary, false /* small_p */); NEXT_PASS (pass_ipa_reference); /* This pass needs to be scheduled after any IP code duplication. */ @@ -346,6 +348,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_late_warn_uninitialized); NEXT_PASS (pass_uncprop); NEXT_PASS (pass_local_pure_const); + NEXT_PASS (pass_modref); POP_INSERT_PASSES () NEXT_PASS (pass_all_optimizations_g); PUSH_INSERT_PASSES_WITHIN (pass_all_optimizations_g) @@ -378,6 +381,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_late_warn_uninitialized); NEXT_PASS (pass_uncprop); NEXT_PASS (pass_local_pure_const); + NEXT_PASS (pass_modref); POP_INSERT_PASSES () NEXT_PASS (pass_tm_init); PUSH_INSERT_PASSES_WITHIN (pass_tm_init) diff --git a/gcc/timevar.def b/gcc/timevar.def index 7dd1e2685a4..08c21c04009 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -107,6 +107,7 @@ DEFTIMEVAR (TV_IPA_PTA , "ipa points-to") DEFTIMEVAR (TV_IPA_SRA , "ipa SRA") DEFTIMEVAR (TV_IPA_FREE_LANG_DATA , "ipa free lang data") DEFTIMEVAR (TV_IPA_FREE_INLINE_SUMMARY, "ipa free inline summary") +DEFTIMEVAR (TV_IPA_MODREF , "ipa modref") /* Time spent by constructing CFG. */ DEFTIMEVAR (TV_CFG , "cfg construction") /* Time spent by cleaning up CFG. */ @@ -218,6 +219,7 @@ DEFTIMEVAR (TV_TREE_SINCOS , "gimple CSE sin/cos") DEFTIMEVAR (TV_TREE_WIDEN_MUL , "gimple widening/fma detection") DEFTIMEVAR (TV_TRANS_MEM , "transactional memory") DEFTIMEVAR (TV_TREE_STRLEN , "tree strlen optimization") +DEFTIMEVAR (TV_TREE_MODREF , "tree modref") DEFTIMEVAR (TV_CGRAPH_VERIFY , "callgraph verifier") DEFTIMEVAR (TV_DOM_FRONTIERS , "dominance frontiers") DEFTIMEVAR (TV_DOMINANCE , "dominance computation") diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index f01e811917d..62e5b696cab 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -477,6 +477,7 @@ extern simple_ipa_opt_pass *make_pass_ipa_oacc_kernels (gcc::context *ctxt); extern gimple_opt_pass *make_pass_warn_nonnull_compare (gcc::context *ctxt); extern gimple_opt_pass *make_pass_sprintf_length (gcc::context *ctxt); extern gimple_opt_pass *make_pass_walloca (gcc::context *ctxt); +extern gimple_opt_pass *make_pass_modref (gcc::context *ctxt); extern gimple_opt_pass *make_pass_coroutine_lower_builtins (gcc::context *ctxt); extern gimple_opt_pass *make_pass_coroutine_early_expand_ifns (gcc::context *ctxt); extern gimple_opt_pass *make_pass_adjust_alignment (gcc::context *ctxt); @@ -517,6 +518,7 @@ extern ipa_opt_pass_d *make_pass_ipa_profile (gcc::context *ctxt); extern ipa_opt_pass_d *make_pass_ipa_cdtor_merge (gcc::context *ctxt); extern ipa_opt_pass_d *make_pass_ipa_single_use (gcc::context *ctxt); extern ipa_opt_pass_d *make_pass_ipa_comdats (gcc::context *ctxt); +extern ipa_opt_pass_d *make_pass_ipa_modref (gcc::context *ctxt); extern simple_ipa_opt_pass *make_pass_materialize_all_clones (gcc::context * ctxt); diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c index ede4f198342..2bd26cff478 100644 --- a/gcc/tree-ssa-alias.c +++ b/gcc/tree-ssa-alias.c @@ -38,6 +38,8 @@ along with GCC; see the file COPYING3. If not see #include "tree-dfa.h" #include "ipa-reference.h" #include "varasm.h" +#include "ipa-modref-tree.h" +#include "ipa-modref.h" /* Broad overview of how alias analysis on gimple works: @@ -107,6 +109,11 @@ static struct { unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_may_alias; unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_must_overlap; unsigned HOST_WIDE_INT nonoverlapping_refs_since_match_p_no_alias; + unsigned HOST_WIDE_INT modref_use_may_alias; + unsigned HOST_WIDE_INT modref_use_no_alias; + unsigned HOST_WIDE_INT modref_clobber_may_alias; + unsigned HOST_WIDE_INT modref_clobber_no_alias; + unsigned HOST_WIDE_INT modref_tests; } alias_stats; void @@ -153,6 +160,24 @@ dump_alias_stats (FILE *s) alias_stats.aliasing_component_refs_p_no_alias + alias_stats.aliasing_component_refs_p_may_alias); dump_alias_stats_in_alias_c (s); + fprintf (s, "\nModref stats:\n"); + fprintf (s, " modref use: " + HOST_WIDE_INT_PRINT_DEC" disambiguations, " + HOST_WIDE_INT_PRINT_DEC" queries\n", + alias_stats.modref_use_no_alias, + alias_stats.modref_use_no_alias + + alias_stats.modref_use_may_alias); + fprintf (s, " modref clobber: " + HOST_WIDE_INT_PRINT_DEC" disambiguations, " + HOST_WIDE_INT_PRINT_DEC" queries\n " + HOST_WIDE_INT_PRINT_DEC" tbaa querries (%f per modref querry)\n", + alias_stats.modref_clobber_no_alias, + alias_stats.modref_clobber_no_alias + + alias_stats.modref_clobber_may_alias, + alias_stats.modref_tests, + ((double)alias_stats.modref_tests) + / (alias_stats.modref_clobber_no_alias + + alias_stats.modref_clobber_may_alias)); } @@ -1341,8 +1366,8 @@ nonoverlapping_array_refs_p (tree ref1, tree ref2) { tree index1 = TREE_OPERAND (ref1, 1); tree index2 = TREE_OPERAND (ref2, 1); - tree low_bound1 = cheap_array_ref_low_bound(ref1); - tree low_bound2 = cheap_array_ref_low_bound(ref2); + tree low_bound1 = cheap_array_ref_low_bound (ref1); + tree low_bound2 = cheap_array_ref_low_bound (ref2); /* Handle zero offsets first: we do not need to match type size in this case. */ @@ -2394,6 +2419,66 @@ refs_output_dependent_p (tree store1, tree store2) return refs_may_alias_p_1 (&r1, &r2, false); } +/* Returns true if and only if REF may alias any access stored in TT. + IF TBAA_P is true, use TBAA oracle. */ + +static bool +modref_may_conflict (modref_tree <alias_set_type> *tt, ao_ref *ref, bool tbaa_p) +{ + alias_set_type base_set, ref_set; + modref_base_node <alias_set_type> *base_node; + modref_ref_node <alias_set_type> *ref_node; + size_t i, j; + + if (!flag_strict_aliasing) + return true; + + if (tt->every_base) + return true; + + base_set = ao_ref_base_alias_set (ref); + if (!base_set) + return true; + + ref_set = ao_ref_alias_set (ref); + + int num_tests = 0, max_tests = param_modref_max_tests; + FOR_EACH_VEC_SAFE_ELT (tt->bases, i, base_node) + { + if (base_node->every_ref) + return true; + + if (!base_node->base) + return true; + + if (tbaa_p) + { + if (!alias_sets_conflict_p (base_set, base_node->base)) + continue; + alias_stats.modref_tests++; + num_tests++; + } + else + return true; + if (num_tests >= max_tests) + return true; + + FOR_EACH_VEC_SAFE_ELT (base_node->refs, j, ref_node) + { + /* Do not repeat same test as before. */ + if (ref_set == base_set && base_node->base == ref_node->ref) + return true; + if (alias_sets_conflict_p (ref_set, ref_node->ref)) + return true; + alias_stats.modref_tests++; + num_tests++; + if (num_tests >= max_tests) + return true; + } + } + return false; +} + /* If the call CALL may use the memory reference REF return true, otherwise return false. */ @@ -2409,15 +2494,51 @@ ref_maybe_used_by_call_p_1 (gcall *call, ao_ref *ref, bool tbaa_p) && (flags & (ECF_CONST|ECF_NOVOPS))) goto process_args; - base = ao_ref_base (ref); - if (!base) - return true; - /* A call that is not without side-effects might involve volatile accesses and thus conflicts with all other volatile accesses. */ if (ref->volatile_p) return true; + callee = gimple_call_fndecl (call); + + if (!gimple_call_chain (call) && callee != NULL_TREE) + { + struct cgraph_node *node = cgraph_node::get (callee); + /* We can not safely optimize based on summary of calle if it does + not always bind to current def: it is possible that memory load + was optimized out earlier and the interposed variant may not be + optimized this way. */ + if (node && node->binds_to_current_def_p ()) + { + modref_summary *summary = get_modref_function_summary (node); + if (summary) + { + if (!modref_may_conflict (summary->loads, ref, tbaa_p)) + { + alias_stats.modref_use_no_alias++; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "ipa-modref: in %s," + " call to %s does not use ", + cgraph_node::get + (current_function_decl)->dump_name (), + node->dump_name ()); + print_generic_expr (dump_file, ref->ref); + fprintf (dump_file, " %i->%i\n", + ao_ref_base_alias_set (ref), + ao_ref_alias_set (ref)); + } + goto process_args; + } + alias_stats.modref_use_may_alias++; + } + } + } + + base = ao_ref_base (ref); + if (!base) + return true; + /* If the reference is based on a decl that is not aliased the call cannot possibly use it. */ if (DECL_P (base) @@ -2426,8 +2547,6 @@ ref_maybe_used_by_call_p_1 (gcall *call, ao_ref *ref, bool tbaa_p) && !is_global_var (base)) goto process_args; - callee = gimple_call_fndecl (call); - /* Handle those builtin functions explicitly that do not act as escape points. See tree-ssa-structalias.c:find_func_aliases for the list of builtins we might need to handle here. */ @@ -2781,7 +2900,7 @@ ref_maybe_used_by_stmt_p (gimple *stmt, tree ref, bool tbaa_p) return true, otherwise return false. */ bool -call_may_clobber_ref_p_1 (gcall *call, ao_ref *ref) +call_may_clobber_ref_p_1 (gcall *call, ao_ref *ref, bool tbaa_p) { tree base; tree callee; @@ -2808,6 +2927,39 @@ call_may_clobber_ref_p_1 (gcall *call, ao_ref *ref) break; } + callee = gimple_call_fndecl (call); + + if (callee != NULL_TREE && !ref->volatile_p) + { + struct cgraph_node *node = cgraph_node::get (callee); + if (node) + { + modref_summary *summary = get_modref_function_summary (node); + if (summary) + { + if (!modref_may_conflict (summary->stores, ref, tbaa_p)) + { + alias_stats.modref_clobber_no_alias++; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, + "ipa-modref: in %s, " + "call to %s does not clobber ", + cgraph_node::get + (current_function_decl)->dump_name (), + node->dump_name ()); + print_generic_expr (dump_file, ref->ref); + fprintf (dump_file, " %i->%i\n", + ao_ref_base_alias_set (ref), + ao_ref_alias_set (ref)); + } + return false; + } + alias_stats.modref_clobber_may_alias++; + } + } + } + base = ao_ref_base (ref); if (!base) return true; @@ -2840,8 +2992,6 @@ call_may_clobber_ref_p_1 (gcall *call, ao_ref *ref) && SSA_NAME_POINTS_TO_READONLY_MEMORY (TREE_OPERAND (base, 0))) return false; - callee = gimple_call_fndecl (call); - /* Handle those builtin functions explicitly that do not act as escape points. See tree-ssa-structalias.c:find_func_aliases for the list of builtins we might need to handle here. */ @@ -3083,7 +3233,7 @@ call_may_clobber_ref_p (gcall *call, tree ref) bool res; ao_ref r; ao_ref_init (&r, ref); - res = call_may_clobber_ref_p_1 (call, &r); + res = call_may_clobber_ref_p_1 (call, &r, true); if (res) ++alias_stats.call_may_clobber_ref_p_may_alias; else @@ -3110,7 +3260,7 @@ stmt_may_clobber_ref_p_1 (gimple *stmt, ao_ref *ref, bool tbaa_p) return true; } - return call_may_clobber_ref_p_1 (as_a <gcall *> (stmt), ref); + return call_may_clobber_ref_p_1 (as_a <gcall *> (stmt), ref, tbaa_p); } else if (gimple_assign_single_p (stmt)) { diff --git a/gcc/tree-ssa-alias.h b/gcc/tree-ssa-alias.h index d6e92d8dc12..1dd02c0ea62 100644 --- a/gcc/tree-ssa-alias.h +++ b/gcc/tree-ssa-alias.h @@ -129,7 +129,7 @@ extern bool stmt_may_clobber_global_p (gimple *); extern bool stmt_may_clobber_ref_p (gimple *, tree, bool = true); extern bool stmt_may_clobber_ref_p_1 (gimple *, ao_ref *, bool = true); extern bool call_may_clobber_ref_p (gcall *, tree); -extern bool call_may_clobber_ref_p_1 (gcall *, ao_ref *); +extern bool call_may_clobber_ref_p_1 (gcall *, ao_ref *, bool = true); extern bool stmt_kills_ref_p (gimple *, tree); extern bool stmt_kills_ref_p (gimple *, ao_ref *); enum translate_flags