From b86c14c18c906dbafff9e373a031a4c55e7cfd0e Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Wed, 6 May 2020 12:16:17 +0200 Subject: experiment with alias --- gcc/Makefile.in | 1 + gcc/common.opt | 4 ++ gcc/ipa-hello-world.c | 126 ++++++++++++++++++++++++++++++++++++++++++++++++++ gcc/passes.def | 1 + gcc/tree-pass.h | 1 + 5 files changed, 133 insertions(+) create mode 100644 gcc/ipa-hello-world.c diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 9ba21f735f6..a27a91b5387 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1403,6 +1403,7 @@ OBJS = \ incpath.o \ init-regs.o \ internal-fn.o \ + ipa-hello-world.o \ ipa-cp.o \ ipa-sra.o \ ipa-devirt.o \ diff --git a/gcc/common.opt b/gcc/common.opt index 4464049fc1f..850a914be1a 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -3413,4 +3413,8 @@ fipa-ra Common Report Var(flag_ipa_ra) Optimization Use caller save register across calls if possible. +fipa-hello-world +Common Report Var(flag_ipa_hello_world) Optimization +TBD + ; This comment is to ensure we retain the blank line above. diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c new file mode 100644 index 00000000000..00e276a4bd7 --- /dev/null +++ b/gcc/ipa-hello-world.c @@ -0,0 +1,126 @@ +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple-expr.h" +#include "predict.h" +#include "alloc-pool.h" +#include "tree-pass.h" +#include "cgraph.h" +#include "diagnostic.h" +#include "fold-const.h" +#include "gimple-fold.h" +#include "symbol-summary.h" +#include "tree-vrp.h" +#include "ipa-prop.h" +#include "tree-pretty-print.h" +#include "tree-inline.h" +#include "ipa-fnsummary.h" +#include "ipa-utils.h" +#include "tree-ssa-ccp.h" +#include "stringpool.h" +#include "attribs.h" +#include "tree-ssa-alias.h" +#include "tree-ssanames.h" +#include "gimple.h" +#include "cfg.h" +#include "gimple-iterator.h" +#include "gimple-ssa.h" + +void inline +log(const char* const fmt, ...) +{ + if (!dump_file) return; + + va_list args; + va_start(args, fmt); + vfprintf(dump_file, fmt, args); + va_end(args); +} + +static void +alias_experiment_gimple_body(const cgraph_node *cnode) +{ + gcc_assert(cnode); + + function *func = DECL_STRUCT_FUNCTION(cnode->decl); + + // We are looking first into SSA becaues of + // this documentation... + // Points-to and escape analysis. + // Points-to analysis builds a set of constraints from the GIMPLE SSA IL + // representing all pointer operations and facts we do or do not know + // about pointers. Solving this set of constraints yields a conservatively + // correct solution for each pointer variable in the program (though we are + // only interested in SSA name pointers) as to what it may possibly point to. + // https://gcc.gnu.org/onlinedocs/gccint/Alias-analysis.html + + size_t j = 0; + tree var_decl = NULL; + FOR_EACH_LOCAL_DECL(func, j, var_decl) + { + const_tree identifier_node = DECL_NAME(var_decl); + if (!identifier_node) continue; + const char* const identifier_pointer = IDENTIFIER_POINTER(identifier_node); + log("var_decl = %s\n", identifier_pointer); + if (POINTER_TYPE_P(TREE_TYPE(var_decl))) break; + } + + size_t i = 0; + tree ssa_name = NULL; + push_cfun(func); + FOR_EACH_SSA_NAME(i, ssa_name, cfun) + { + struct ptr_info_def *pi = SSA_NAME_PTR_INFO(ssa_name); + if (!pi) continue; + log("i have a pi"); + pt_solution_includes(&pi->pt, var_decl); + } + pop_cfun(); + + +} + +static unsigned int +iphw_execute() +{ + cgraph_node *node = NULL; + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(node) + { + alias_experiment_gimple_body (node); + } + return 0; +} + +namespace { +const pass_data pass_data_ipa_hello_world = +{ + SIMPLE_IPA_PASS, + "hello-world", + OPTGROUP_NONE, + TV_NONE, + (PROP_cfg | PROP_ssa), + 0, + 0, + TODO_rebuild_alias, + 0, +}; + +class pass_ipa_hello_world : public simple_ipa_opt_pass +{ +public: + pass_ipa_hello_world (gcc::context *ctx) + : simple_ipa_opt_pass(pass_data_ipa_hello_world, ctx) + {} + + virtual bool gate(function*) { return flag_ipa_hello_world; } + virtual unsigned execute (function*) { return iphw_execute(); } +}; +} // anon namespace + +simple_ipa_opt_pass* +make_pass_ipa_hello_world (gcc::context *ctx) +{ + return new pass_ipa_hello_world (ctx); +} diff --git a/gcc/passes.def b/gcc/passes.def index 2bf2cb78fc5..66f333f81dc 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -149,6 +149,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_ipa_profile); NEXT_PASS (pass_ipa_icf); NEXT_PASS (pass_ipa_devirt); + NEXT_PASS (pass_ipa_hello_world); NEXT_PASS (pass_ipa_cp); NEXT_PASS (pass_ipa_sra); NEXT_PASS (pass_ipa_cdtor_merge); diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index a1207a20a3c..377dda689cc 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -501,6 +501,7 @@ extern ipa_opt_pass_d *make_pass_ipa_fn_summary (gcc::context *ctxt); extern ipa_opt_pass_d *make_pass_ipa_inline (gcc::context *ctxt); extern simple_ipa_opt_pass *make_pass_ipa_free_lang_data (gcc::context *ctxt); extern simple_ipa_opt_pass *make_pass_ipa_free_fn_summary (gcc::context *ctxt); +extern simple_ipa_opt_pass *make_pass_ipa_hello_world (gcc::context *ctxt); extern ipa_opt_pass_d *make_pass_ipa_cp (gcc::context *ctxt); extern ipa_opt_pass_d *make_pass_ipa_sra (gcc::context *ctxt); extern ipa_opt_pass_d *make_pass_ipa_icf (gcc::context *ctxt); -- cgit v1.2.3 From 2cd40f49f0ca4a8c8c98f57194e76d41f8810dfb Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Thu, 7 May 2020 14:49:29 +0200 Subject: Adds compare types --- gcc/compare-types.c | 273 ++++++++++++++++++++++++++++++++++++++++++++++++++++ gcc/compare-types.h | 12 +++ 2 files changed, 285 insertions(+) create mode 100644 gcc/compare-types.c create mode 100644 gcc/compare-types.h diff --git a/gcc/compare-types.c b/gcc/compare-types.c new file mode 100644 index 00000000000..61a43d8c408 --- /dev/null +++ b/gcc/compare-types.c @@ -0,0 +1,273 @@ +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple-expr.h" +#include "predict.h" +#include "alloc-pool.h" +#include "tree-pass.h" +#include "cgraph.h" +#include "diagnostic.h" +#include "fold-const.h" +#include "gimple-fold.h" +#include "symbol-summary.h" +#include "tree-vrp.h" +#include "ipa-prop.h" +#include "tree-pretty-print.h" +#include "tree-inline.h" +#include "ipa-fnsummary.h" +#include "ipa-utils.h" +#include "tree-ssa-ccp.h" +#include "stringpool.h" +#include "attribs.h" +#include "tree-ssa-alias.h" +#include "tree-ssanames.h" +#include "gimple.h" +#include "cfg.h" +#include "gimple-iterator.h" +#include "gimple-ssa.h" + +#include "compare-types.h" + +static bool +eq_main_variant(const_tree a, const_tree b) +{ + gcc_assert(a && b); + const_tree main_variant_a = TYPE_MAIN_VARIANT(a); + const_tree main_variant_b = TYPE_MAIN_VARIANT(b); + gcc_assert(main_variant_a && main_variant_b); + const bool are_equal = main_variant_a == main_variant_b; + return are_equal; +} + +static bool +eq_canonical_internal(const_tree a, const_tree b) +{ + gcc_assert(a && b); + const_tree canonical_a = TYPE_CANONICAL(a); + const_tree canonical_b = TYPE_CANONICAL(b); + gcc_assert(canonical_a && canonical_b); + const bool are_equal = canonical_a == canonical_b; + return are_equal; +} + +static bool +eq_record_or_union_types(const_tree a, const_tree b, const bool force_structural) +{ + gcc_assert(a && b); + + tree field_a = TYPE_FIELDS(a); + tree field_b = TYPE_FIELDS(b); + while (field_a || field_b) + { + const bool different_lengths = (bool)field_a != (bool)field_b; + if (different_lengths) return false; + + const_tree field_type_a = TREE_TYPE(field_a); + const_tree field_type_b = TREE_TYPE(field_b); + gcc_assert(field_type_a && field_type_b); + const bool same_field_types = eq_types(field_type_a, field_type_b, force_structural); + if (!same_field_types) return false; + + field_a = DECL_CHAIN(field_a); + field_b = DECL_CHAIN(field_b); + } + + return true; +} + +static bool +eq_record_types(const_tree a, const_tree b, const bool force_structural) +{ + gcc_assert(a && b); + assert_is_type(a, RECORD_TYPE); + assert_is_type(b, RECORD_TYPE); + return eq_record_or_union_types(a, b, force_structural); +} + +static bool +eq_union_types(const_tree a, const_tree b, const bool force_structural) +{ + gcc_assert(a && b); + assert_is_type(a, UNION_TYPE); + assert_is_type(b, UNION_TYPE); + return eq_record_or_union_types(a, b, force_structural); +} + +static bool +eq_wrapper_types(const_tree a, const_tree b, const bool force_structural) +{ + gcc_assert(a && b); + const_tree inner_type_a = TREE_TYPE(a); + const_tree inner_type_b = TREE_TYPE(b); + gcc_assert(inner_type_a && inner_type_b); + return eq_types(inner_type_a, inner_type_b, force_structural); +} + +static bool +eq_pointer_types(const_tree a, const_tree b, const bool force_structural) +{ + gcc_assert(a && b); + assert_is_type(a, POINTER_TYPE); + assert_is_type(b, POINTER_TYPE); + return eq_wrapper_types(a, b, force_structural); +} + +static bool +eq_reference_types(const_tree a, const_tree b, const bool force_structural) +{ + gcc_assert(a && b); + assert_is_type(a, REFERENCE_TYPE); + assert_is_type(b, REFERENCE_TYPE); + return eq_wrapper_types(a, b, force_structural); +} + +static bool +eq_array_types(const_tree a, const_tree b, const bool force_structural) +{ + gcc_assert(a && b); + assert_is_type(a, ARRAY_TYPE); + assert_is_type(b, ARRAY_TYPE); + return eq_wrapper_types(a, b, force_structural); +} + +static bool +eq_function_or_method_types(const_tree a, const_tree b, const bool force_structural) +{ + gcc_assert(a && b); + const_tree return_type_a = TREE_TYPE(a); + const_tree return_type_b = TREE_TYPE(b); + const bool is_return_equal = eq_types(return_type_a, return_type_b, force_structural); + if (!is_return_equal) return false; + + tree parm_a = TYPE_ARG_TYPES(a); + tree parm_b = TYPE_ARG_TYPES(b); + + while (parm_a || parm_b) + { + const bool different_lengths = (bool)parm_a != (bool)parm_b; + if (different_lengths) return false; + + const_tree parm_type_a = TREE_TYPE(parm_a); + const_tree parm_type_b = TREE_TYPE(parm_b); + gcc_assert(parm_type_a && parm_type_b); + const bool same_field_types = eq_types(parm_type_a, parm_type_b, force_structural); + if (!same_field_types) return false; + + parm_a = TREE_CHAIN(parm_a); + parm_b = TREE_CHAIN(parm_b); + } + + return true; +} + +static bool +eq_function_types(const_tree a, const_tree b, const bool force_structural) +{ + gcc_assert(a && b); + assert_is_type(a, FUNCTION_TYPE); + assert_is_type(b, FUNCTION_TYPE); + return eq_function_or_method_types(a, b, force_structural); +} + +static bool +eq_method_types(const_tree a, const_tree b, const bool force_structural) +{ + gcc_assert(a && b); + assert_is_type(a, METHOD_TYPE); + assert_is_type(b, METHOD_TYPE); + + const_tree base_type_a = TYPE_METHOD_BASETYPE(a); + const_tree base_type_b = TYPE_METHOD_BASETYPE(b); + const bool eq_base_types = eq_types(base_type_a, base_type_b, force_structural); + return eq_base_types && eq_function_or_method_types(a, b, force_structural); +} + +static bool eq_structural(const_tree a, const_tree b, const bool force_structural = false); + +static bool +eq_structural(const_tree a, const_tree b, const bool force_structural) +{ + gcc_assert(a && b); + const enum tree_code code_a = TREE_CODE(a); + const enum tree_code code_b = TREE_CODE(b); + const bool equal_code = code_a == code_b; + if (!equal_code) return false; + + const enum tree_code code = code_a; + switch (code) + { + case VOID_TYPE: + case INTEGER_TYPE: + case REAL_TYPE: + case FIXED_POINT_TYPE: + case COMPLEX_TYPE: + case ENUMERAL_TYPE: + case BOOLEAN_TYPE: + case OFFSET_TYPE: + return true; + break; + default: + break; + } + + switch (code) + { + case RECORD_TYPE: + return eq_record_types(a, b, force_structural); + break; + case POINTER_TYPE: + return eq_pointer_types(a, b, force_structural); + break; + case REFERENCE_TYPE: + return eq_reference_types(a, b, force_structural); + break; + case ARRAY_TYPE: + return eq_array_types(a, b, force_structural); + break; + case UNION_TYPE: + return eq_union_types(a, b, force_structural); + break; + case FUNCTION_TYPE: + return eq_function_types(a, b, force_structural); + break; + case METHOD_TYPE: + return eq_method_types(a, b, force_structural); + break; + case QUAL_UNION_TYPE: + case LANG_TYPE: + default: + // Unimplemented + gcc_unreachable(); + break; + } + + gcc_unreachable(); + return false; +} + +static bool +eq_canonical(const_tree a, const_tree b) +{ + gcc_assert(a && b); + const bool struct_eq_a = TYPE_STRUCTURAL_EQUALITY_P(a); + const bool struct_eq_b = TYPE_STRUCTURAL_EQUALITY_P(b); + const bool use_structural_equality = struct_eq_a || struct_eq_b; + const bool are_equal = use_structural_equality ? eq_structural(a, b) : eq_canonical_internal(a, b); + return are_equal; +} + +bool +eq_types(const_tree a, const_tree b, const bool force_structural) +{ + gcc_assert(a && b); + if (force_structural) return eq_structural(a, b, force_structural); + + if (eq_main_variant(a, b)) return true; + if (!eq_canonical(a, b)) return false; + + // optimistic... + gcc_unreachable(); + return false; +} diff --git a/gcc/compare-types.h b/gcc/compare-types.h new file mode 100644 index 00000000000..ca7251109a6 --- /dev/null +++ b/gcc/compare-types.h @@ -0,0 +1,12 @@ +#pragma once + +inline +void assert_is_type(const_tree a, const enum tree_code expected_code) +{ + gcc_assert(a); + const enum tree_code observed_code = TREE_CODE(a); + const bool eq_codes = observed_code == expected_code; + gcc_assert(eq_codes); +} + +extern bool eq_types(const_tree a, const_tree b, const bool force_structural = false); -- cgit v1.2.3 From cb14559b9aa05c91facd512877abb074b7dbbfa3 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Thu, 7 May 2020 14:49:41 +0200 Subject: wip --- build.sh | 15 +++ gcc/Makefile.in | 1 + gcc/ipa-hello-world.c | 334 ++++++++++++++++++++++++++++++++++++++++++++------ 3 files changed, 314 insertions(+), 36 deletions(-) create mode 100755 build.sh diff --git a/build.sh b/build.sh new file mode 100755 index 00000000000..b87c079a48c --- /dev/null +++ b/build.sh @@ -0,0 +1,15 @@ +#!/usr/bin/env bash + +set -e +set -u + +installdir=${1:-"gcc-inst2"} +mkdir -p $HOME/code/gcc-build/ +mkdir -p $HOME/code/${installdir}/ +pushd $HOME/code/gcc-build/ +$OLDPWD/configure --disable-bootstrap --disable-libsanitizer --enable-__cxa_atexit --enable-shared --disable-libsanitizer --enable-languages=c,c++,fortran --enable-lto --enable-gold --enable-linker-build-id --with-cpu-emag --prefix="$HOME/code/${installdir}/" +make -j `nproc` +make install -j `nproc` +make check-gcc RUNTESTFLAGS="ipa.exp" +popd + diff --git a/gcc/Makefile.in b/gcc/Makefile.in index a27a91b5387..84031e0e5a4 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1404,6 +1404,7 @@ OBJS = \ init-regs.o \ internal-fn.o \ ipa-hello-world.o \ + compare-types.o \ ipa-cp.o \ ipa-sra.o \ ipa-devirt.o \ diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c index 00e276a4bd7..d9af11cfb41 100644 --- a/gcc/ipa-hello-world.c +++ b/gcc/ipa-hello-world.c @@ -28,6 +28,9 @@ #include "gimple-iterator.h" #include "gimple-ssa.h" +#include "compare-types.h" +#include + void inline log(const char* const fmt, ...) { @@ -39,57 +42,316 @@ log(const char* const fmt, ...) va_end(args); } +typedef std::set typeset; + +static const bool contains_record_types(const_tree type); + +static const bool +inner_type_contains_record_types(const_tree type) +{ + gcc_assert(type); + const_tree inner = TREE_TYPE(type); + return contains_record_types(inner); +} + +static const bool +pointer_contains_record_types(const_tree type) +{ + assert_is_type(type, POINTER_TYPE); + return inner_type_contains_record_types(type); +} + +static const bool +reference_contains_record_types(const_tree type) +{ + assert_is_type(type, REFERENCE_TYPE); + return inner_type_contains_record_types(type); +} + +static const bool +array_contains_record_types(const_tree type) +{ + assert_is_type(type, ARRAY_TYPE); + return inner_type_contains_record_types(type); +} + +static const bool +union_contains_record_types(const_tree type) +{ + assert_is_type(type, UNION_TYPE); + tree field = TYPE_FIELDS(type); + while (field) + { + const_tree field_type = TREE_TYPE(field); + gcc_assert(field_type); + const bool contains_record = contains_record_types(field_type); + if (contains_record) return true; + + field = DECL_CHAIN(field); + } + + return false; +} + +static const bool +function_or_method_contains_record_types(const_tree type) +{ + gcc_assert(type); + const_tree ret_type = TREE_TYPE(type); + const bool return_type_contains_record = contains_record_types(ret_type); + if (return_type_contains_record) return true; + + tree parm = TYPE_ARG_TYPES(type); + + while (parm) + { + const_tree parm_type = TREE_TYPE(parm); + const bool parm_type_contains_record = contains_record_types(parm_type); + if (parm_type) return true; + + parm = TREE_CHAIN(parm); + } + + return false; +} + +static const bool +function_contains_record_types(const_tree type) +{ + assert_is_type(type, FUNCTION_TYPE); + return function_or_method_contains_record_types(type); +} + +static const bool +method_contains_record_types(const_tree type) +{ + assert_is_type(type, FUNCTION_TYPE); + const_tree base_type = TYPE_METHOD_BASETYPE(type); + const bool base_type_contains_record_types = contains_record_types(base_type); + return base_type_contains_record_types && function_or_method_contains_record_types(type); +} + +static const bool +contains_record_types(const_tree type) +{ + gcc_assert(type); + const enum tree_code code = TREE_CODE(type); + if (code == RECORD_TYPE) return true; + + switch (code) + { + case VOID_TYPE: + case INTEGER_TYPE: + case REAL_TYPE: + case FIXED_POINT_TYPE: + case ENUMERAL_TYPE: + case BOOLEAN_TYPE: + case OFFSET_TYPE: + return false; + break; + default: + break; + } + + switch (code) + { + case POINTER_TYPE: + return pointer_contains_record_types(type); + break; + case REFERENCE_TYPE: + return reference_contains_record_types(type); + break; + case ARRAY_TYPE: + return array_contains_record_types(type); + break; + case UNION_TYPE: + return union_contains_record_types(type); + break; + case FUNCTION_TYPE: + return function_contains_record_types(type); + break; + case METHOD_TYPE: + return method_contains_record_types(type); + break; + case QUAL_UNION_TYPE: + case LANG_TYPE: + default: + gcc_unreachable(); + break; + } + + gcc_unreachable(); + return false; +} + static void -alias_experiment_gimple_body(const cgraph_node *cnode) +get_non_escaping_locals(const cgraph_node *cnode, typeset &escaping_types, typeset &non_escaping_types) { gcc_assert(cnode); - - function *func = DECL_STRUCT_FUNCTION(cnode->decl); - - // We are looking first into SSA becaues of - // this documentation... - // Points-to and escape analysis. - // Points-to analysis builds a set of constraints from the GIMPLE SSA IL - // representing all pointer operations and facts we do or do not know - // about pointers. Solving this set of constraints yields a conservatively - // correct solution for each pointer variable in the program (though we are - // only interested in SSA name pointers) as to what it may possibly point to. - // https://gcc.gnu.org/onlinedocs/gccint/Alias-analysis.html - - size_t j = 0; + function *func = DECL_STRUCT_FUNCTION (cnode->decl); + int i = 0; tree var_decl = NULL; - FOR_EACH_LOCAL_DECL(func, j, var_decl) + FOR_EACH_LOCAL_DECL(func, i, var_decl) { - const_tree identifier_node = DECL_NAME(var_decl); - if (!identifier_node) continue; - const char* const identifier_pointer = IDENTIFIER_POINTER(identifier_node); - log("var_decl = %s\n", identifier_pointer); - if (POINTER_TYPE_P(TREE_TYPE(var_decl))) break; + } +} + +static void +get_non_escaping_types(const cgraph_node *cnode, typeset &escaping_types, typeset &non_escaping_types) +{ + gcc_assert(cnode); + get_non_escaping_locals(cnode, escaping_types, non_escaping_types); +} - size_t i = 0; - tree ssa_name = NULL; - push_cfun(func); - FOR_EACH_SSA_NAME(i, ssa_name, cfun) +// So, have a set with TYPE_MAIN_VARIANTS... +typeset +get_non_escaping_types() +{ + cgraph_node *cnode = NULL; + typeset non_escaping_types; + typeset escaping_types; + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(cnode) { - struct ptr_info_def *pi = SSA_NAME_PTR_INFO(ssa_name); - if (!pi) continue; - log("i have a pi"); - pt_solution_includes(&pi->pt, var_decl); + cnode->get_untransformed_body(); + get_non_escaping_types(cnode, escaping_types, non_escaping_types); } - pop_cfun(); + return non_escaping_types; +} + +namespace test_type_equality { + +static void +test_main_variant() +{ + tree void_a = make_node(VOID_TYPE); + tree void_b = build_variant_type_copy(void_a); + const bool expected = true; + const bool observed = eq_types(void_a, void_b); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_pointer_types_eq() +{ + tree pointer_a = make_node(POINTER_TYPE); + tree inner_type = make_node(INTEGER_TYPE); + TREE_TYPE(pointer_a) = inner_type; + tree pointer_b = build_variant_type_copy(pointer_a); + const bool expected = true; + const bool observed = eq_types(pointer_a, pointer_b); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_pointer_types_ne() +{ + tree pointer_a = make_node(POINTER_TYPE); + tree inner_type_a = make_node(INTEGER_TYPE); + TREE_TYPE(pointer_a) = inner_type_a; + tree pointer_b = make_node(POINTER_TYPE); + tree inner_type_b = make_node(VOID_TYPE); + TREE_TYPE(pointer_b) = inner_type_b; + const bool expected = false; + const bool observed = eq_types(pointer_a, pointer_b, true); + const bool success = expected == observed; + gcc_assert(success); +} +static void +test_pointer_types_eq_structurally() +{ + tree pointer_a = make_node(POINTER_TYPE); + tree inner_type_a = make_node(INTEGER_TYPE); + TREE_TYPE(pointer_a) = inner_type_a; + tree pointer_b = make_node(POINTER_TYPE); + tree inner_type_b = make_node(INTEGER_TYPE); + TREE_TYPE(pointer_b) = inner_type_b; + const bool expected = true; + const bool observed = eq_types(pointer_a, pointer_b, true); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_void_eq() +{ + tree void_a = make_node(VOID_TYPE); + tree void_b = build_variant_type_copy(void_a); + const bool expected = true; + const bool observed = eq_types(void_a, void_b, true); + const bool success = expected == observed; + gcc_assert(success); +} +static void +test_structural_equality_different_types() +{ + tree type_a = make_node(VOID_TYPE); + tree type_b = make_node(RECORD_TYPE); + const bool expected = false; + const bool observed = eq_types(type_a, type_b, true); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_different_record_types() +{ + tree type_a = make_node(RECORD_TYPE); + tree type_b = make_node(RECORD_TYPE); + tree field_a = make_node(FIELD_DECL); + tree field_b = make_node(FIELD_DECL); + tree type_field_a = make_node(VOID_TYPE); + tree type_field_b = make_node(RECORD_TYPE); + TREE_TYPE(field_a) = type_field_a; + TREE_TYPE(field_b) = type_field_b; + TYPE_FIELDS(type_a) = field_a; + TYPE_FIELDS(type_b) = field_b; + const bool expected = false; + const bool observed = eq_types(type_a, type_b, true); + const bool success = expected == observed; + gcc_assert(success); } +static void +test_same_record_types() +{ + tree type_a = make_node(RECORD_TYPE); + tree field_a = make_node(FIELD_DECL); + tree type_field_a = make_node(VOID_TYPE); + TREE_TYPE(field_a) = type_field_a; + TYPE_FIELDS(type_a) = field_a; + tree type_b = build_variant_type_copy(type_a); + const bool expected = true; + const bool observed = eq_types(type_a, type_b, true); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +run_tests() +{ + log("running tests...\n"); + test_main_variant(); + test_void_eq(); + test_structural_equality_different_types(); + test_different_record_types(); + test_same_record_types(); + test_pointer_types_eq_structurally(); + test_pointer_types_ne(); + test_pointer_types_eq(); + +} +} // test_type_equality + static unsigned int iphw_execute() { - cgraph_node *node = NULL; - FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(node) - { - alias_experiment_gimple_body (node); - } + //test_type_equality::run_tests(); + typeset non_escaping = get_non_escaping_types(); return 0; } @@ -114,7 +376,7 @@ public: : simple_ipa_opt_pass(pass_data_ipa_hello_world, ctx) {} - virtual bool gate(function*) { return flag_ipa_hello_world; } + virtual bool gate(function*) { return false; } virtual unsigned execute (function*) { return iphw_execute(); } }; } // anon namespace -- cgit v1.2.3 From 05be5426007e015726c9dc76cabd708ddd4d6be0 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Fri, 8 May 2020 13:30:28 +0200 Subject: wip --- gcc/Makefile.in | 1 + gcc/collect-types.c | 192 +++++++++++++++++++++++++++++ gcc/collect-types.h | 7 ++ gcc/compare-types.c | 128 +++++++++++++++++++ gcc/compare-types.h | 10 +- gcc/ipa-hello-world.c | 336 +++++++------------------------------------------- gcc/types-inlines.h | 21 ++++ 7 files changed, 394 insertions(+), 301 deletions(-) create mode 100644 gcc/collect-types.c create mode 100644 gcc/collect-types.h create mode 100644 gcc/types-inlines.h diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 84031e0e5a4..8af80cfd9e1 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1405,6 +1405,7 @@ OBJS = \ internal-fn.o \ ipa-hello-world.o \ compare-types.o \ + collect-types.o \ ipa-cp.o \ ipa-sra.o \ ipa-devirt.o \ diff --git a/gcc/collect-types.c b/gcc/collect-types.c new file mode 100644 index 00000000000..18c4ab3ca92 --- /dev/null +++ b/gcc/collect-types.c @@ -0,0 +1,192 @@ +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple-expr.h" +#include "predict.h" +#include "alloc-pool.h" +#include "tree-pass.h" +#include "cgraph.h" +#include "diagnostic.h" +#include "fold-const.h" +#include "gimple-fold.h" +#include "symbol-summary.h" +#include "tree-vrp.h" +#include "ipa-prop.h" +#include "tree-pretty-print.h" +#include "tree-inline.h" +#include "ipa-fnsummary.h" +#include "ipa-utils.h" +#include "tree-ssa-ccp.h" +#include "stringpool.h" +#include "attribs.h" +#include "tree-ssa-alias.h" +#include "tree-ssanames.h" +#include "gimple.h" +#include "cfg.h" +#include "gimple-iterator.h" +#include "gimple-ssa.h" + +#include "compare-types.h" +#include "types-inlines.h" +#include + +#include "collect-types.h" + +static void +collect_types_from_record_or_union_type(const_tree type, typeset &types) +{ + gcc_assert(type); + const enum tree_code code = TREE_CODE(type); + const bool is_union = UNION_TYPE == code; + const bool is_record = RECORD_TYPE == code; + const bool is_valid_input = is_union || is_record; + gcc_assert(is_valid_input); + + for (tree field = TYPE_FIELDS(type) ; field ; field = DECL_CHAIN(field)) + { + const_tree field_type = TREE_TYPE(field); + collect_types(field, types); + } +} + +static void +collect_types_from_record_type(const_tree type, typeset &types) +{ + assert_is_type(type, RECORD_TYPE); + collect_types_from_record_or_union_type(type, types); +} + +static void +collect_types_from_union_type(const_tree type, typeset &types) +{ + assert_is_type(type, UNION_TYPE); + collect_types_from_record_or_union_type(type, types); +} + +static void +collect_types_from_wrapper_type(const_tree type, typeset &types) +{ + gcc_assert(type); + const_tree inner_type = TREE_TYPE(type); + gcc_assert(inner_type); + collect_types(inner_type, types); +} + +static void +collect_types_from_pointer_type(const_tree type, typeset &types) +{ + assert_is_type(type, POINTER_TYPE); + collect_types_from_wrapper_type(type, types); +} + +static void +collect_types_from_reference_type(const_tree type, typeset &types) +{ + assert_is_type(type, REFERENCE_TYPE); + collect_types_from_wrapper_type(type, types); +} + +static void +collect_types_from_array_type(const_tree type, typeset &types) +{ + assert_is_type(type, ARRAY_TYPE); + collect_types_from_wrapper_type(type, types); +} + +static void +collect_types_from_function_or_method_type(const_tree type, typeset &types) +{ + gcc_assert(type); + const enum tree_code code = TREE_CODE(type); + const bool is_function = FUNCTION_TYPE == code; + const bool is_method = METHOD_TYPE == code; + const bool is_valid_input = is_function || is_method; + gcc_assert(is_valid_input); + + const_tree ret_type = TREE_TYPE(type); + gcc_assert(ret_type); + collect_types(ret_type, types); + + for (tree param = TYPE_ARG_TYPES(type); param; param = TREE_CHAIN(param)) + { + const_tree param_type = TREE_TYPE(param); + gcc_assert(param_type); + collect_types(param_type, types); + } +} + +static void +collect_types_from_function_type(const_tree type, typeset &types) +{ + assert_is_type(type, FUNCTION_TYPE); + collect_types_from_function_or_method_type(type, types); +} + +static void +collect_types_from_method_type(const_tree type, typeset &types) +{ + assert_is_type(type, METHOD_TYPE); + collect_types_from_function_or_method_type(type, types); +} + +void +collect_types(const_tree type, typeset &types) +{ + if (!type) return; + + const bool in_set = types.find(type) != types.end(); + // memoized. + if (in_set) return; + + const enum tree_code code = TREE_CODE(type); + switch (code) + { + case VOID_TYPE: + case INTEGER_TYPE: + case REAL_TYPE: + case FIXED_POINT_TYPE: + case COMPLEX_TYPE: + case ENUMERAL_TYPE: + case BOOLEAN_TYPE: + case OFFSET_TYPE: + types.insert(type); + return; + break; + default: + break; + } + + switch (code) + { + case RECORD_TYPE: + collect_types_from_record_type(type, types); + break; + case POINTER_TYPE: + collect_types_from_pointer_type(type, types); + break; + case REFERENCE_TYPE: + collect_types_from_reference_type(type, types); + break; + case ARRAY_TYPE: + collect_types_from_array_type(type, types); + break; + case UNION_TYPE: + collect_types_from_union_type(type, types); + break; + case FUNCTION_TYPE: + collect_types_from_function_type(type, types); + break; + case METHOD_TYPE: + collect_types_from_method_type(type, types); + break; + case QUAL_UNION_TYPE: + case LANG_TYPE: + default: + gcc_unreachable(); + break; + } + + types.insert(type); +} diff --git a/gcc/collect-types.h b/gcc/collect-types.h new file mode 100644 index 00000000000..315c19abfd7 --- /dev/null +++ b/gcc/collect-types.h @@ -0,0 +1,7 @@ +#pragma once + +#include "tree.h" +#include + +typedef std::set typeset; +extern void collect_types(const_tree type, typeset &types); diff --git a/gcc/compare-types.c b/gcc/compare-types.c index 61a43d8c408..641cc1fca90 100644 --- a/gcc/compare-types.c +++ b/gcc/compare-types.c @@ -29,6 +29,7 @@ #include "gimple-ssa.h" #include "compare-types.h" +#include "types-inlines.h" static bool eq_main_variant(const_tree a, const_tree b) @@ -271,3 +272,130 @@ eq_types(const_tree a, const_tree b, const bool force_structural) gcc_unreachable(); return false; } + +namespace test_type_equality { + +static void +test_main_variant() +{ + tree void_a = make_node(VOID_TYPE); + tree void_b = build_variant_type_copy(void_a); + const bool expected = true; + const bool observed = eq_types(void_a, void_b); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_pointer_types_eq() +{ + tree pointer_a = make_node(POINTER_TYPE); + tree inner_type = make_node(INTEGER_TYPE); + TREE_TYPE(pointer_a) = inner_type; + tree pointer_b = build_variant_type_copy(pointer_a); + const bool expected = true; + const bool observed = eq_types(pointer_a, pointer_b); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_pointer_types_ne() +{ + tree pointer_a = make_node(POINTER_TYPE); + tree inner_type_a = make_node(INTEGER_TYPE); + TREE_TYPE(pointer_a) = inner_type_a; + tree pointer_b = make_node(POINTER_TYPE); + tree inner_type_b = make_node(VOID_TYPE); + TREE_TYPE(pointer_b) = inner_type_b; + const bool expected = false; + const bool observed = eq_types(pointer_a, pointer_b, true); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_pointer_types_eq_structurally() +{ + tree pointer_a = make_node(POINTER_TYPE); + tree inner_type_a = make_node(INTEGER_TYPE); + TREE_TYPE(pointer_a) = inner_type_a; + tree pointer_b = make_node(POINTER_TYPE); + tree inner_type_b = make_node(INTEGER_TYPE); + TREE_TYPE(pointer_b) = inner_type_b; + const bool expected = true; + const bool observed = eq_types(pointer_a, pointer_b, true); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_void_eq() +{ + tree void_a = make_node(VOID_TYPE); + tree void_b = build_variant_type_copy(void_a); + const bool expected = true; + const bool observed = eq_types(void_a, void_b, true); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_structural_equality_different_types() +{ + tree type_a = make_node(VOID_TYPE); + tree type_b = make_node(RECORD_TYPE); + const bool expected = false; + const bool observed = eq_types(type_a, type_b, true); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_different_record_types() +{ + tree type_a = make_node(RECORD_TYPE); + tree type_b = make_node(RECORD_TYPE); + tree field_a = make_node(FIELD_DECL); + tree field_b = make_node(FIELD_DECL); + tree type_field_a = make_node(VOID_TYPE); + tree type_field_b = make_node(RECORD_TYPE); + TREE_TYPE(field_a) = type_field_a; + TREE_TYPE(field_b) = type_field_b; + TYPE_FIELDS(type_a) = field_a; + TYPE_FIELDS(type_b) = field_b; + const bool expected = false; + const bool observed = eq_types(type_a, type_b, true); + const bool success = expected == observed; + gcc_assert(success); +} + +static void +test_same_record_types() +{ + tree type_a = make_node(RECORD_TYPE); + tree field_a = make_node(FIELD_DECL); + tree type_field_a = make_node(VOID_TYPE); + TREE_TYPE(field_a) = type_field_a; + TYPE_FIELDS(type_a) = field_a; + tree type_b = build_variant_type_copy(type_a); + const bool expected = true; + const bool observed = eq_types(type_a, type_b, true); + const bool success = expected == observed; + gcc_assert(success); +} + +void +run_tests() +{ + test_main_variant(); + test_void_eq(); + test_structural_equality_different_types(); + test_different_record_types(); + test_same_record_types(); + test_pointer_types_eq_structurally(); + test_pointer_types_ne(); + test_pointer_types_eq(); + +} +} // test_type_equality diff --git a/gcc/compare-types.h b/gcc/compare-types.h index ca7251109a6..63474713807 100644 --- a/gcc/compare-types.h +++ b/gcc/compare-types.h @@ -1,12 +1,4 @@ #pragma once -inline -void assert_is_type(const_tree a, const enum tree_code expected_code) -{ - gcc_assert(a); - const enum tree_code observed_code = TREE_CODE(a); - const bool eq_codes = observed_code == expected_code; - gcc_assert(eq_codes); -} - +namespace test_type_equality { void run_tests(); }; extern bool eq_types(const_tree a, const_tree b, const bool force_structural = false); diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c index d9af11cfb41..09cf4526780 100644 --- a/gcc/ipa-hello-world.c +++ b/gcc/ipa-hello-world.c @@ -29,329 +29,81 @@ #include "gimple-ssa.h" #include "compare-types.h" +#include "types-inlines.h" #include -void inline -log(const char* const fmt, ...) -{ - if (!dump_file) return; - - va_list args; - va_start(args, fmt); - vfprintf(dump_file, fmt, args); - va_end(args); -} - -typedef std::set typeset; - -static const bool contains_record_types(const_tree type); - -static const bool -inner_type_contains_record_types(const_tree type) -{ - gcc_assert(type); - const_tree inner = TREE_TYPE(type); - return contains_record_types(inner); -} - -static const bool -pointer_contains_record_types(const_tree type) -{ - assert_is_type(type, POINTER_TYPE); - return inner_type_contains_record_types(type); -} - -static const bool -reference_contains_record_types(const_tree type) -{ - assert_is_type(type, REFERENCE_TYPE); - return inner_type_contains_record_types(type); -} - -static const bool -array_contains_record_types(const_tree type) -{ - assert_is_type(type, ARRAY_TYPE); - return inner_type_contains_record_types(type); -} +#include "collect-types.h" -static const bool -union_contains_record_types(const_tree type) -{ - assert_is_type(type, UNION_TYPE); - tree field = TYPE_FIELDS(type); - while (field) - { - const_tree field_type = TREE_TYPE(field); - gcc_assert(field_type); - const bool contains_record = contains_record_types(field_type); - if (contains_record) return true; - - field = DECL_CHAIN(field); - } - - return false; -} -static const bool -function_or_method_contains_record_types(const_tree type) -{ - gcc_assert(type); - const_tree ret_type = TREE_TYPE(type); - const bool return_type_contains_record = contains_record_types(ret_type); - if (return_type_contains_record) return true; - - tree parm = TYPE_ARG_TYPES(type); - - while (parm) - { - const_tree parm_type = TREE_TYPE(parm); - const bool parm_type_contains_record = contains_record_types(parm_type); - if (parm_type) return true; - - parm = TREE_CHAIN(parm); - } - - return false; -} - -static const bool -function_contains_record_types(const_tree type) -{ - assert_is_type(type, FUNCTION_TYPE); - return function_or_method_contains_record_types(type); -} - -static const bool -method_contains_record_types(const_tree type) -{ - assert_is_type(type, FUNCTION_TYPE); - const_tree base_type = TYPE_METHOD_BASETYPE(type); - const bool base_type_contains_record_types = contains_record_types(base_type); - return base_type_contains_record_types && function_or_method_contains_record_types(type); -} - -static const bool -contains_record_types(const_tree type) +static void +collect_types_from_cnode_decl(cgraph_node *cnode, typeset &types) { - gcc_assert(type); - const enum tree_code code = TREE_CODE(type); - if (code == RECORD_TYPE) return true; - - switch (code) - { - case VOID_TYPE: - case INTEGER_TYPE: - case REAL_TYPE: - case FIXED_POINT_TYPE: - case ENUMERAL_TYPE: - case BOOLEAN_TYPE: - case OFFSET_TYPE: - return false; - break; - default: - break; - } - - switch (code) - { - case POINTER_TYPE: - return pointer_contains_record_types(type); - break; - case REFERENCE_TYPE: - return reference_contains_record_types(type); - break; - case ARRAY_TYPE: - return array_contains_record_types(type); - break; - case UNION_TYPE: - return union_contains_record_types(type); - break; - case FUNCTION_TYPE: - return function_contains_record_types(type); - break; - case METHOD_TYPE: - return method_contains_record_types(type); - break; - case QUAL_UNION_TYPE: - case LANG_TYPE: - default: - gcc_unreachable(); - break; - } - - gcc_unreachable(); - return false; + gcc_assert(cnode); + const_tree decl = cnode->decl; + gcc_assert(decl); + const_tree decl_type = TREE_TYPE(decl); + gcc_assert(decl_type); + // This will collect return, arguments and decl_type itself + collect_types(decl_type, types); } static void -get_non_escaping_locals(const cgraph_node *cnode, typeset &escaping_types, typeset &non_escaping_types) +collect_types_from_cnode_locals(cgraph_node *cnode, typeset &types) { gcc_assert(cnode); - function *func = DECL_STRUCT_FUNCTION (cnode->decl); + const_tree decl = cnode->decl; + gcc_assert(decl); + function *func = DECL_STRUCT_FUNCTION (decl); + gcc_assert(func); int i = 0; tree var_decl = NULL; FOR_EACH_LOCAL_DECL(func, i, var_decl) { - + gcc_assert(var_decl); + const_tree var_decl_type = TREE_TYPE(var_decl); + collect_types(var_decl_type, types); } } static void -get_non_escaping_types(const cgraph_node *cnode, typeset &escaping_types, typeset &non_escaping_types) +collect_types_from_cnode_ssa_names(cgraph_node *cnode, typeset &types) { gcc_assert(cnode); - get_non_escaping_locals(cnode, escaping_types, non_escaping_types); -} - -// So, have a set with TYPE_MAIN_VARIANTS... -typeset -get_non_escaping_types() -{ - cgraph_node *cnode = NULL; - typeset non_escaping_types; - typeset escaping_types; - FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(cnode) + const_tree decl = cnode->decl; + gcc_assert(decl); + function *func = DECL_STRUCT_FUNCTION (decl); + push_cfun(func); + size_t i = 0; + tree ssa_name = NULL; + FOR_EACH_SSA_NAME(i, ssa_name, cfun) { - cnode->get_untransformed_body(); - get_non_escaping_types(cnode, escaping_types, non_escaping_types); + gcc_assert(ssa_name); + const_tree ssa_name_type = TREE_TYPE(ssa_name); + collect_types(ssa_name, types); } - return non_escaping_types; -} - -namespace test_type_equality { - -static void -test_main_variant() -{ - tree void_a = make_node(VOID_TYPE); - tree void_b = build_variant_type_copy(void_a); - const bool expected = true; - const bool observed = eq_types(void_a, void_b); - const bool success = expected == observed; - gcc_assert(success); -} - -static void -test_pointer_types_eq() -{ - tree pointer_a = make_node(POINTER_TYPE); - tree inner_type = make_node(INTEGER_TYPE); - TREE_TYPE(pointer_a) = inner_type; - tree pointer_b = build_variant_type_copy(pointer_a); - const bool expected = true; - const bool observed = eq_types(pointer_a, pointer_b); - const bool success = expected == observed; - gcc_assert(success); -} - -static void -test_pointer_types_ne() -{ - tree pointer_a = make_node(POINTER_TYPE); - tree inner_type_a = make_node(INTEGER_TYPE); - TREE_TYPE(pointer_a) = inner_type_a; - tree pointer_b = make_node(POINTER_TYPE); - tree inner_type_b = make_node(VOID_TYPE); - TREE_TYPE(pointer_b) = inner_type_b; - const bool expected = false; - const bool observed = eq_types(pointer_a, pointer_b, true); - const bool success = expected == observed; - gcc_assert(success); -} - -static void -test_pointer_types_eq_structurally() -{ - tree pointer_a = make_node(POINTER_TYPE); - tree inner_type_a = make_node(INTEGER_TYPE); - TREE_TYPE(pointer_a) = inner_type_a; - tree pointer_b = make_node(POINTER_TYPE); - tree inner_type_b = make_node(INTEGER_TYPE); - TREE_TYPE(pointer_b) = inner_type_b; - const bool expected = true; - const bool observed = eq_types(pointer_a, pointer_b, true); - const bool success = expected == observed; - gcc_assert(success); + pop_cfun(); } static void -test_void_eq() -{ - tree void_a = make_node(VOID_TYPE); - tree void_b = build_variant_type_copy(void_a); - const bool expected = true; - const bool observed = eq_types(void_a, void_b, true); - const bool success = expected == observed; - gcc_assert(success); -} - -static void -test_structural_equality_different_types() +collect_types_from_functions_with_gimple_body(cgraph_node *cnode, typeset &types) { - tree type_a = make_node(VOID_TYPE); - tree type_b = make_node(RECORD_TYPE); - const bool expected = false; - const bool observed = eq_types(type_a, type_b, true); - const bool success = expected == observed; - gcc_assert(success); -} - -static void -test_different_record_types() -{ - tree type_a = make_node(RECORD_TYPE); - tree type_b = make_node(RECORD_TYPE); - tree field_a = make_node(FIELD_DECL); - tree field_b = make_node(FIELD_DECL); - tree type_field_a = make_node(VOID_TYPE); - tree type_field_b = make_node(RECORD_TYPE); - TREE_TYPE(field_a) = type_field_a; - TREE_TYPE(field_b) = type_field_b; - TYPE_FIELDS(type_a) = field_a; - TYPE_FIELDS(type_b) = field_b; - const bool expected = false; - const bool observed = eq_types(type_a, type_b, true); - const bool success = expected == observed; - gcc_assert(success); -} - -static void -test_same_record_types() -{ - tree type_a = make_node(RECORD_TYPE); - tree field_a = make_node(FIELD_DECL); - tree type_field_a = make_node(VOID_TYPE); - TREE_TYPE(field_a) = type_field_a; - TYPE_FIELDS(type_a) = field_a; - tree type_b = build_variant_type_copy(type_a); - const bool expected = true; - const bool observed = eq_types(type_a, type_b, true); - const bool success = expected == observed; - gcc_assert(success); -} - -static void -run_tests() -{ - log("running tests...\n"); - test_main_variant(); - test_void_eq(); - test_structural_equality_different_types(); - test_different_record_types(); - test_same_record_types(); - test_pointer_types_eq_structurally(); - test_pointer_types_ne(); - test_pointer_types_eq(); - + gcc_assert(cnode); + collect_types_from_cnode_decl(cnode, types); + collect_types_from_cnode_locals(cnode, types); + collect_types_from_cnode_ssa_names(cnode, types); } -} // test_type_equality static unsigned int iphw_execute() { - //test_type_equality::run_tests(); - typeset non_escaping = get_non_escaping_types(); + test_type_equality::run_tests(); + cgraph_node *node = NULL; + typeset types; + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(node) + { + node->get_untransformed_body(); + collect_types_from_functions_with_gimple_body(node, types); + } return 0; } diff --git a/gcc/types-inlines.h b/gcc/types-inlines.h new file mode 100644 index 00000000000..9d91bc050d2 --- /dev/null +++ b/gcc/types-inlines.h @@ -0,0 +1,21 @@ +#pragma once + +inline void +assert_is_type(const_tree a, const enum tree_code expected_code) +{ + gcc_assert(a); + const enum tree_code observed_code = TREE_CODE(a); + const bool eq_codes = observed_code == expected_code; + gcc_assert(eq_codes); +} + +inline void +log(const char* const fmt, ...) +{ + if (!dump_file) return; + + va_list args; + va_start(args, fmt); + vfprintf(dump_file, fmt, args); + va_end(args); +} -- cgit v1.2.3 From fd18ddec9304a852070c894397ee34f811db14c7 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Mon, 11 May 2020 13:28:35 +0200 Subject: Adds passes to print type names --- gcc/Makefile.in | 1 + gcc/collect-types.c | 10 +- gcc/ipa-hello-world.c | 40 +++++- gcc/name-types.c | 388 ++++++++++++++++++++++++++++++++++++++++++++++++++ gcc/name-types.h | 10 ++ gcc/passes.def | 2 +- gcc/types-inlines.h | 10 -- 7 files changed, 442 insertions(+), 19 deletions(-) create mode 100644 gcc/name-types.c create mode 100644 gcc/name-types.h diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 8af80cfd9e1..e8e22d88706 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1406,6 +1406,7 @@ OBJS = \ ipa-hello-world.o \ compare-types.o \ collect-types.o \ + name-types.o \ ipa-cp.o \ ipa-sra.o \ ipa-devirt.o \ diff --git a/gcc/collect-types.c b/gcc/collect-types.c index 18c4ab3ca92..20a5ad4eeba 100644 --- a/gcc/collect-types.c +++ b/gcc/collect-types.c @@ -109,11 +109,12 @@ collect_types_from_function_or_method_type(const_tree type, typeset &types) gcc_assert(ret_type); collect_types(ret_type, types); - for (tree param = TYPE_ARG_TYPES(type); param; param = TREE_CHAIN(param)) + tree arg_node = TYPE_ARG_TYPES(type); + while (NULL_TREE != arg_node) { - const_tree param_type = TREE_TYPE(param); - gcc_assert(param_type); - collect_types(param_type, types); + tree arg_node_type = TREE_VALUE(arg_node); + collect_types(arg_node_type, types); + arg_node = TREE_CHAIN(arg_node); } } @@ -184,6 +185,7 @@ collect_types(const_tree type, typeset &types) case QUAL_UNION_TYPE: case LANG_TYPE: default: + //log("%s\n", get_tree_code_name(code)); gcc_unreachable(); break; } diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c index 09cf4526780..72294961af6 100644 --- a/gcc/ipa-hello-world.c +++ b/gcc/ipa-hello-world.c @@ -31,10 +31,23 @@ #include "compare-types.h" #include "types-inlines.h" #include +#include #include "collect-types.h" +#include "name-types.h" +inline void +log(const char* const fmt, ...) +{ + if (!dump_file) return; + + va_list args; + va_start(args, fmt); + vfprintf(dump_file, fmt, args); + va_end(args); +} + static void collect_types_from_cnode_decl(cgraph_node *cnode, typeset &types) { @@ -43,8 +56,12 @@ collect_types_from_cnode_decl(cgraph_node *cnode, typeset &types) gcc_assert(decl); const_tree decl_type = TREE_TYPE(decl); gcc_assert(decl_type); + function *func = DECL_STRUCT_FUNCTION (decl); + gcc_assert(func); + push_cfun(func); // This will collect return, arguments and decl_type itself collect_types(decl_type, types); + pop_cfun(); } static void @@ -72,9 +89,10 @@ collect_types_from_cnode_ssa_names(cgraph_node *cnode, typeset &types) const_tree decl = cnode->decl; gcc_assert(decl); function *func = DECL_STRUCT_FUNCTION (decl); - push_cfun(func); + gcc_assert(func); size_t i = 0; tree ssa_name = NULL; + push_cfun(func); FOR_EACH_SSA_NAME(i, ssa_name, cfun) { gcc_assert(ssa_name); @@ -90,13 +108,25 @@ collect_types_from_functions_with_gimple_body(cgraph_node *cnode, typeset &types gcc_assert(cnode); collect_types_from_cnode_decl(cnode, types); collect_types_from_cnode_locals(cnode, types); - collect_types_from_cnode_ssa_names(cnode, types); + //collect_types_from_cnode_ssa_names(cnode, types); +} + +static void +print_types_in_set(typeset &types) +{ + for (auto it = types.cbegin(); it != types.cend(); ++it) + { + const_tree type = *it; + std::string name = type_to_string(type); + log("name: %s\n", name.c_str()); + } } static unsigned int iphw_execute() { - test_type_equality::run_tests(); + //test_type_equality::run_tests(); + //test_naming_types::run_tests(); cgraph_node *node = NULL; typeset types; FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(node) @@ -104,6 +134,8 @@ iphw_execute() node->get_untransformed_body(); collect_types_from_functions_with_gimple_body(node, types); } + + print_types_in_set(types); return 0; } @@ -128,7 +160,7 @@ public: : simple_ipa_opt_pass(pass_data_ipa_hello_world, ctx) {} - virtual bool gate(function*) { return false; } + virtual bool gate(function*) { return flag_ipa_hello_world; } virtual unsigned execute (function*) { return iphw_execute(); } }; } // anon namespace diff --git a/gcc/name-types.c b/gcc/name-types.c new file mode 100644 index 00000000000..fb490d0c8f4 --- /dev/null +++ b/gcc/name-types.c @@ -0,0 +1,388 @@ +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple-expr.h" +#include "predict.h" +#include "alloc-pool.h" +#include "tree-pass.h" +#include "cgraph.h" +#include "diagnostic.h" +#include "fold-const.h" +#include "gimple-fold.h" +#include "symbol-summary.h" +#include "tree-vrp.h" +#include "ipa-prop.h" +#include "tree-pretty-print.h" +#include "tree-inline.h" +#include "ipa-fnsummary.h" +#include "ipa-utils.h" +#include "tree-ssa-ccp.h" +#include "stringpool.h" +#include "attribs.h" +#include "tree-ssa-alias.h" +#include "tree-ssanames.h" +#include "gimple.h" +#include "cfg.h" +#include "gimple-iterator.h" +#include "gimple-ssa.h" + +#include "types-inlines.h" +#include +#include + +#include "name-types.h" + +// Using std::string because it will manage memory for us +// And we don't know whether the user will free the memory. +// Also that's why we are returning a value rather than a +// pointer... + +static const std::string +type_to_string_simple(const_tree type) +{ + gcc_assert(type); + const enum tree_code code = TREE_CODE(type); + bool valid_input = false; + switch (code) + { + case VOID_TYPE: + case INTEGER_TYPE: + case REAL_TYPE: + case FIXED_POINT_TYPE: + case COMPLEX_TYPE: + case ENUMERAL_TYPE: + case BOOLEAN_TYPE: + case OFFSET_TYPE: + valid_input = true; + break; + default: + valid_input = false; + break; + } + gcc_assert(valid_input); + + + return std::string(get_tree_code_name(code)); +} + +static const std::string +type_to_string_get_field_name(const_tree field) +{ + assert_is_type(field, FIELD_DECL); + const_tree decl_name = DECL_NAME(field); + if (!decl_name) return std::string(""); + + const char* identifier = IDENTIFIER_POINTER(field); + return std::string(identifier); +} + +static const unsigned +type_to_string_get_field_offset(const_tree field) +{ + assert_is_type(field, FIELD_DECL); + tree cst = byte_position(field); + gcc_assert(cst); + unsigned offset = tree_to_uhwi (cst); + return offset; +} + +static const unsigned +type_to_string_get_type_size(const_tree type) +{ + gcc_assert(type); + const_tree type_size = TYPE_SIZE(type); + const bool is_incomplete = NULL_TREE == type_size; + if (is_incomplete) return 0; + + const bool fits_uhwi = tree_fits_uhwi_p(type_size); + if (fits_uhwi) return tree_to_uhwi (type_size); + + const bool fits_shwi = tree_fits_shwi_p(type_size); + if (fits_shwi) return tree_to_shwi (type_size); + + return 0; + +} + +static const std::string +type_to_string_get_record_name(const_tree type) +{ + assert_is_type(type, RECORD_TYPE); + tree name = TYPE_NAME(type); + // The TYPE_NAME will be NULL_TREE for a type + // that is not a built-in type, the result of a typedef + // or a named class type. + const bool no_name = NULL_TREE == name; + if (no_name) return std::string(""); + + const enum tree_code name_code = TREE_CODE(name); + const bool is_name_type_decl = TYPE_DECL == name_code; + name = is_name_type_decl ? DECL_NAME(name) : name; + const char* identifier_ptr = IDENTIFIER_POINTER(name); + gcc_assert(identifier_ptr); + return std::string(identifier_ptr); +} + +static const std::string +type_to_string_get_record_or_union_name(const_tree type) +{ + //TODO: FIXME + //I think it should also work for UNIONS, but I should then rewrite the function + //to avoid the assertion + return type_to_string_get_record_name(type); +} + +/* + * The idea behind this function is to receive either + * a record or a union type and return a string that + * represents this type. + * The output should look something like this: + * 0: astruct { + * 0: int a + * 8: int b + * 16: bstruct* + * 24: cstruct { + * 0: int a + * } + * 32: { + * } + * } + * The question I have now... is... should we follos bstruct* + * to see what it points to? Because, maybe there's two bstruct*s + * defined in different TU? + * So maybe more like this: + * 0: astruct { + * 0: int a + * 8: int b + * 16: bstruct { + * 0: int a + * }* + * 24: cstruct { + * 0: int a + * } + * 32: { + * } + */ +static const std::string +type_to_string_record_or_union(const_tree type) +{ + gcc_assert(type); + const enum tree_code code = TREE_CODE(type); + const bool is_record = RECORD_TYPE == code; + const bool is_union = UNION_TYPE == code; + const bool is_valid_input = is_record || is_union; + gcc_assert(is_valid_input); + + std::string name = type_to_string_get_record_or_union_name(type); + std::string aggregate = name + std::string(" {"); + + for (tree field = TYPE_FIELDS(type); field; field = DECL_CHAIN(field)) + { + std::string field_name = type_to_string_get_field_name(field); + const_tree field_type = TREE_TYPE(field); + const unsigned field_offset = type_to_string_get_field_offset(field); + std::string field_type_name = type_to_string(field_type, field_offset); + aggregate += field_type_name + std::string(";"); + } + + aggregate += "}"; + return aggregate; +} + +static const std::string +type_to_string_record(const_tree type) +{ + assert_is_type(type, RECORD_TYPE); + return type_to_string_record_or_union(type); +} + +static const std::string +type_to_string_union(const_tree type) +{ + assert_is_type(type, UNION_TYPE); + return type_to_string_record_or_union(type); +} + +static const std::string +type_to_string_wrapper(const_tree type) +{ + gcc_assert(type); + const enum tree_code code = TREE_CODE(type); + bool is_valid_input = false; + switch (code) + { + case POINTER_TYPE: + case ARRAY_TYPE: + case REFERENCE_TYPE: + is_valid_input = true; + break; + default: + is_valid_input = false; + break; + } + gcc_assert(is_valid_input); + + const_tree inner_type = TREE_TYPE(type); + return type_to_string(inner_type, 0, false); +} + +static const std::string +type_to_string_pointer(const_tree type) +{ + assert_is_type(type, POINTER_TYPE); + return type_to_string_wrapper(type) + std::string("*"); +} + +static const std::string +type_to_string_array(const_tree type) +{ + assert_is_type(type, ARRAY_TYPE); + return type_to_string_wrapper(type) + std::string("[]"); +} + +static const std::string +type_to_string_reference(const_tree type) +{ + assert_is_type(type, REFERENCE_TYPE); + return type_to_string_wrapper(type) + std::string("&"); +} + +static const std::string +type_to_string_function_or_method(const_tree type) +{ + gcc_assert(type); + const enum tree_code code = TREE_CODE(type); + const bool is_function = FUNCTION_TYPE == code; + const bool is_method = METHOD_TYPE == code; + const bool is_valid = is_function || is_method; + gcc_assert(is_valid); + + const_tree return_type = TREE_TYPE(type); + gcc_assert(return_type); + + const std::string return_type_name = type_to_string(return_type, 0, false); + + std::string aggregate(""); + + for(tree param = TYPE_ARG_TYPES(type); param; param = TREE_CHAIN(param)) + { + const_tree param_type = TREE_VALUE(param); + //TODO: Why no param type? + //gcc_assert(param_type); + const bool has_more_params = TREE_CHAIN(param); + aggregate += type_to_string(param_type); + if (!has_more_params) break; + + aggregate += std::string(", "); + } + + //TODO: Add base_type for method types + std::string retval = return_type_name + std::string("(") + aggregate + std::string(")"); + return retval; +} + +static const std::string +type_to_string_function(const_tree type) +{ + assert_is_type(type, FUNCTION_TYPE); + return type_to_string_function_or_method(type); +} + +static const std::string +type_to_string_method(const_tree type) +{ + assert_is_type(type, METHOD_TYPE); + return type_to_string_function_or_method(type); +} + + +const std::string +type_to_string(const_tree type, const unsigned field_offset, const bool add_prelude) +{ + if (!type) return std::string("why"); + gcc_assert(type); + const enum tree_code code = TREE_CODE(type); + const unsigned size = type_to_string_get_type_size(type); + std::string prelude = add_prelude ? std::to_string(field_offset) + std::string(",") + std::to_string(field_offset + size) + std::string(":") : std::string(""); + + switch (code) + { + case VOID_TYPE: + case INTEGER_TYPE: + case REAL_TYPE: + case FIXED_POINT_TYPE: + case COMPLEX_TYPE: + case ENUMERAL_TYPE: + case BOOLEAN_TYPE: + case OFFSET_TYPE: + return prelude + type_to_string_simple(type); + break; + default: + break; + } + + switch (code) + { + case RECORD_TYPE: + return prelude + type_to_string_record(type); + break; + case UNION_TYPE: + return prelude + type_to_string_union(type); + break; + case POINTER_TYPE: + return prelude + type_to_string_pointer(type); + break; + case REFERENCE_TYPE: + return prelude + type_to_string_reference(type); + break; + case ARRAY_TYPE: + return prelude + type_to_string_array(type); + break; + case FUNCTION_TYPE: + return prelude + type_to_string_function(type); + break; + case METHOD_TYPE: + return prelude + type_to_string_method(type); + break; + case QUAL_UNION_TYPE: + case LANG_TYPE: + default: + // unimplemented + gcc_unreachable(); + break; + } + + gcc_unreachable(); + return std::string("you shouldn't ever see this"); +} + +namespace test_naming_types { + +void test_generic_to_string(const enum tree_code code, const char * expected_char_array) +{ + std::string expected_value(expected_char_array); + tree type = make_node(code); + std::string observed_value = type_to_string(type); + const bool success = expected_value.compare(observed_value) == 0; + gcc_assert(success); + +} +void test_simple_to_string() +{ + test_generic_to_string(VOID_TYPE, "0:void_type"); + test_generic_to_string(INTEGER_TYPE, "0:integer_type"); + test_generic_to_string(REAL_TYPE, "0:real_type"); + test_generic_to_string(FIXED_POINT_TYPE, "0:fixed_point_type"); + test_generic_to_string(COMPLEX_TYPE, "0:complex_type"); + test_generic_to_string(ENUMERAL_TYPE, "0:enumeral_type"); + test_generic_to_string(BOOLEAN_TYPE, "0:boolean_type"); + test_generic_to_string(OFFSET_TYPE, "0:offset_type"); +} + +void run_tests() +{ + test_simple_to_string(); +} +}; diff --git a/gcc/name-types.h b/gcc/name-types.h new file mode 100644 index 00000000000..a56b459b87f --- /dev/null +++ b/gcc/name-types.h @@ -0,0 +1,10 @@ +#pragma once + +#include "tree.h" +#include + +const std::string type_to_string(const_tree type, const unsigned field_offset=0, const bool add_prelude=true); + +namespace test_naming_types { +void run_tests(); +}; diff --git a/gcc/passes.def b/gcc/passes.def index 66f333f81dc..22e5cf21e35 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -149,7 +149,6 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_ipa_profile); NEXT_PASS (pass_ipa_icf); NEXT_PASS (pass_ipa_devirt); - NEXT_PASS (pass_ipa_hello_world); NEXT_PASS (pass_ipa_cp); NEXT_PASS (pass_ipa_sra); NEXT_PASS (pass_ipa_cdtor_merge); @@ -172,6 +171,7 @@ along with GCC; see the file COPYING3. If not see compiled unit. */ INSERT_PASSES_AFTER (all_late_ipa_passes) NEXT_PASS (pass_materialize_all_clones); + NEXT_PASS (pass_ipa_hello_world); NEXT_PASS (pass_ipa_pta); NEXT_PASS (pass_omp_simd_clone); TERMINATE_PASS_LIST (all_late_ipa_passes) diff --git a/gcc/types-inlines.h b/gcc/types-inlines.h index 9d91bc050d2..24bd23dddc9 100644 --- a/gcc/types-inlines.h +++ b/gcc/types-inlines.h @@ -9,13 +9,3 @@ assert_is_type(const_tree a, const enum tree_code expected_code) gcc_assert(eq_codes); } -inline void -log(const char* const fmt, ...) -{ - if (!dump_file) return; - - va_list args; - va_start(args, fmt); - vfprintf(dump_file, fmt, args); - va_end(args); -} -- cgit v1.2.3 From 65c6dbee729fa280ff6ab741c78a8ab197940512 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Mon, 11 May 2020 15:21:45 +0200 Subject: Type playground performs comparisons --- gcc/compare-types.c | 21 +++++++++++++++++---- gcc/compare-types.h | 4 ++++ gcc/ipa-hello-world.c | 33 ++++++++++++++++++++++++++++++++- gcc/name-types.c | 1 - 4 files changed, 53 insertions(+), 6 deletions(-) diff --git a/gcc/compare-types.c b/gcc/compare-types.c index 641cc1fca90..860a0de076a 100644 --- a/gcc/compare-types.c +++ b/gcc/compare-types.c @@ -31,7 +31,7 @@ #include "compare-types.h" #include "types-inlines.h" -static bool +bool eq_main_variant(const_tree a, const_tree b) { gcc_assert(a && b); @@ -150,8 +150,8 @@ eq_function_or_method_types(const_tree a, const_tree b, const bool force_structu const bool different_lengths = (bool)parm_a != (bool)parm_b; if (different_lengths) return false; - const_tree parm_type_a = TREE_TYPE(parm_a); - const_tree parm_type_b = TREE_TYPE(parm_b); + const_tree parm_type_a = TREE_VALUE(parm_a); + const_tree parm_type_b = TREE_VALUE(parm_b); gcc_assert(parm_type_a && parm_type_b); const bool same_field_types = eq_types(parm_type_a, parm_type_b, force_structural); if (!same_field_types) return false; @@ -248,7 +248,7 @@ eq_structural(const_tree a, const_tree b, const bool force_structural) return false; } -static bool +bool eq_canonical(const_tree a, const_tree b) { gcc_assert(a && b); @@ -259,6 +259,19 @@ eq_canonical(const_tree a, const_tree b) return are_equal; } + +bool +eq_type_compare(const_tree a, const_tree b) +{ + return eq_types(a, b); +} + +bool +eq_type_structural(const_tree a, const_tree b) +{ + return eq_types(a, b, true); +} + bool eq_types(const_tree a, const_tree b, const bool force_structural) { diff --git a/gcc/compare-types.h b/gcc/compare-types.h index 63474713807..68a79ce4c0a 100644 --- a/gcc/compare-types.h +++ b/gcc/compare-types.h @@ -1,4 +1,8 @@ #pragma once namespace test_type_equality { void run_tests(); }; +extern bool eq_main_variant(const_tree a, const_tree b); +extern bool eq_canonical(const_tree a, const_tree b); +extern bool eq_type_compare(const_tree a, const_tree b); +extern bool eq_type_structural(const_tree a, const_tree b); extern bool eq_types(const_tree a, const_tree b, const bool force_structural = false); diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c index 72294961af6..a6b6aa5a36c 100644 --- a/gcc/ipa-hello-world.c +++ b/gcc/ipa-hello-world.c @@ -36,6 +36,16 @@ #include "collect-types.h" #include "name-types.h" +namespace type_playground { +static unsigned const type_comparisons = 4; +typedef bool (*type_comparison_func_t)(const_tree, const_tree); +static type_comparison_func_t comparisons[type_comparisons] = { + eq_main_variant, + eq_canonical, + eq_type_structural, + eq_type_compare +}; +} inline void log(const char* const fmt, ...) @@ -122,6 +132,27 @@ print_types_in_set(typeset &types) } } +static void +compare_types_in_set(typeset &types) +{ + for (auto i = types.cbegin(); i != types.cend(); ++i) + { + for (auto j = types.cbegin(); j != types.cend(); ++j) + { + const_tree a = *i; + const_tree b = *j; + log("%s x %s = ", type_to_string(a).c_str(), type_to_string(b).c_str()); + for (unsigned k = 0; k < type_playground::type_comparisons; k++) + { + type_playground::type_comparison_func_t comparison = type_playground::comparisons[k]; + const bool result = comparison(a, b); + log("%s, ", result ? "t" : "f"); + } + log("\n"); + } + } +} + static unsigned int iphw_execute() { @@ -135,7 +166,7 @@ iphw_execute() collect_types_from_functions_with_gimple_body(node, types); } - print_types_in_set(types); + compare_types_in_set(types); return 0; } diff --git a/gcc/name-types.c b/gcc/name-types.c index fb490d0c8f4..693ebf28400 100644 --- a/gcc/name-types.c +++ b/gcc/name-types.c @@ -103,7 +103,6 @@ type_to_string_get_type_size(const_tree type) if (fits_shwi) return tree_to_shwi (type_size); return 0; - } static const std::string -- cgit v1.2.3 From cd8aacf48f9e958a9eb3e055ae3754a40d4ec876 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Mon, 11 May 2020 16:16:50 +0200 Subject: Fixes --- gcc/collect-types.c | 46 ++++++++++++++++++++++++++++++++++++++++++++++ gcc/compare-types.c | 6 ++++++ gcc/ipa-hello-world.c | 4 ++-- 3 files changed, 54 insertions(+), 2 deletions(-) diff --git a/gcc/collect-types.c b/gcc/collect-types.c index 20a5ad4eeba..0d05c7bdb4d 100644 --- a/gcc/collect-types.c +++ b/gcc/collect-types.c @@ -34,6 +34,40 @@ #include "collect-types.h" +static bool +filter_out_simple_types(const_tree type) +{ + gcc_assert(type); + const enum tree_code code = TREE_CODE(type); + + switch (code) + { + case VOID_TYPE: + case INTEGER_TYPE: + case REAL_TYPE: + case FIXED_POINT_TYPE: + case COMPLEX_TYPE: + case ENUMERAL_TYPE: + case BOOLEAN_TYPE: + case OFFSET_TYPE: + return true; + break; + default: + return false; + break; + } + + gcc_unreachable(); + return false; +} + +static const unsigned filter_buffer_size = 1; +typedef bool (*filter_t)(const_tree); +const extern filter_t filter[filter_buffer_size] = +{ + filter_out_simple_types, +}; + static void collect_types_from_record_or_union_type(const_tree type, typeset &types) { @@ -141,6 +175,18 @@ collect_types(const_tree type, typeset &types) // memoized. if (in_set) return; + // we should have filters here + // such that if we are processing a type + // which we know somehow that it is not a type we are interested + // then we just return immediately. + // maybe even add it to a set of blacklisted types so that we + // memoize and do things faster... + for (unsigned i = 0; i < filter_buffer_size; i++) + { + const bool filter_out = filter[i](type); + if (filter_out) return; + } + const enum tree_code code = TREE_CODE(type); switch (code) { diff --git a/gcc/compare-types.c b/gcc/compare-types.c index 860a0de076a..752f4cfbd0d 100644 --- a/gcc/compare-types.c +++ b/gcc/compare-types.c @@ -199,6 +199,11 @@ eq_structural(const_tree a, const_tree b, const bool force_structural) const enum tree_code code = code_a; switch (code) { + //FIXME: Just because two codes are the same + //doesn't mean they are the same type + //E.g. short != int + // float != double + // enum a != enum b case VOID_TYPE: case INTEGER_TYPE: case REAL_TYPE: @@ -282,6 +287,7 @@ eq_types(const_tree a, const_tree b, const bool force_structural) if (!eq_canonical(a, b)) return false; // optimistic... + // maybe we should have a MAYBE? gcc_unreachable(); return false; } diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c index a6b6aa5a36c..e7cd5400282 100644 --- a/gcc/ipa-hello-world.c +++ b/gcc/ipa-hello-world.c @@ -107,7 +107,7 @@ collect_types_from_cnode_ssa_names(cgraph_node *cnode, typeset &types) { gcc_assert(ssa_name); const_tree ssa_name_type = TREE_TYPE(ssa_name); - collect_types(ssa_name, types); + collect_types(ssa_name_type, types); } pop_cfun(); } @@ -118,7 +118,7 @@ collect_types_from_functions_with_gimple_body(cgraph_node *cnode, typeset &types gcc_assert(cnode); collect_types_from_cnode_decl(cnode, types); collect_types_from_cnode_locals(cnode, types); - //collect_types_from_cnode_ssa_names(cnode, types); + collect_types_from_cnode_ssa_names(cnode, types); } static void -- cgit v1.2.3 From 44ac8e749cb905fda22bfb26b4d210e822666249 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Tue, 12 May 2020 14:31:03 +0200 Subject: Adds ability to use only specified comparison functions --- build.sh | 2 +- gcc/collect-types.c | 2 +- gcc/common.opt | 6 +++++ gcc/compare-types.c | 15 +++++++++++ gcc/compare-types.h | 2 ++ gcc/ipa-hello-world.c | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++- gcc/name-types.c | 18 +++++++++++++ gcc/name-types.h | 1 + 8 files changed, 116 insertions(+), 3 deletions(-) diff --git a/build.sh b/build.sh index b87c079a48c..711b8c4bd56 100755 --- a/build.sh +++ b/build.sh @@ -3,7 +3,7 @@ set -e set -u -installdir=${1:-"gcc-inst2"} +installdir=${1:-"gcc-inst"} mkdir -p $HOME/code/gcc-build/ mkdir -p $HOME/code/${installdir}/ pushd $HOME/code/gcc-build/ diff --git a/gcc/collect-types.c b/gcc/collect-types.c index 0d05c7bdb4d..3f04e0f8d45 100644 --- a/gcc/collect-types.c +++ b/gcc/collect-types.c @@ -50,7 +50,7 @@ filter_out_simple_types(const_tree type) case ENUMERAL_TYPE: case BOOLEAN_TYPE: case OFFSET_TYPE: - return true; + return false; break; default: return false; diff --git a/gcc/common.opt b/gcc/common.opt index 850a914be1a..4c97d6dda5f 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -3417,4 +3417,10 @@ fipa-hello-world Common Report Var(flag_ipa_hello_world) Optimization TBD +ftp-types-compared= +Common Joined Report Var(flag_tp_types_compared) Init(0) + +ftp-comparison-functions= +Common Joined Report Var(flag_tp_comparison_functions) Init(0) + ; This comment is to ensure we retain the blank line above. diff --git a/gcc/compare-types.c b/gcc/compare-types.c index 752f4cfbd0d..33021d5feb0 100644 --- a/gcc/compare-types.c +++ b/gcc/compare-types.c @@ -30,6 +30,7 @@ #include "compare-types.h" #include "types-inlines.h" +#include "name-types.h" bool eq_main_variant(const_tree a, const_tree b) @@ -187,6 +188,20 @@ eq_method_types(const_tree a, const_tree b, const bool force_structural) static bool eq_structural(const_tree a, const_tree b, const bool force_structural = false); +bool +eq_pointer(const_tree a, const_tree b) +{ + return a == b; +} + +bool +eq_identifier(const_tree a, const_tree b) +{ + std::string name_a = get_type_identifier(a); + std::string name_b = get_type_identifier(b); + return name_a.compare(name_b) == 0; +} + static bool eq_structural(const_tree a, const_tree b, const bool force_structural) { diff --git a/gcc/compare-types.h b/gcc/compare-types.h index 68a79ce4c0a..7f33684e927 100644 --- a/gcc/compare-types.h +++ b/gcc/compare-types.h @@ -1,6 +1,8 @@ #pragma once namespace test_type_equality { void run_tests(); }; +extern bool eq_identifier(const_tree a, const_tree b); +extern bool eq_pointer(const_tree a, const_tree b); extern bool eq_main_variant(const_tree a, const_tree b); extern bool eq_canonical(const_tree a, const_tree b); extern bool eq_type_compare(const_tree a, const_tree b); diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c index e7cd5400282..b3f85d2e85c 100644 --- a/gcc/ipa-hello-world.c +++ b/gcc/ipa-hello-world.c @@ -37,9 +37,28 @@ #include "name-types.h" namespace type_playground { -static unsigned const type_comparisons = 4; +enum type_comparison_func_enum { + EQ_POINTER = 0, + EQ_IDENTIFIER, + EQ_MAIN_VARIANT, + EQ_CANONICAL, + EQ_STRUCTURAL, + EQ_COMPARE, + EQ_END +}; +static unsigned const type_comparisons = EQ_END; +static const char* names[type_comparisons] = { + "EQ_POINTER", + "EQ_IDENTIFIER", + "EQ_MAIN_VARIANT", + "EQ_CANONICAL", + "EQ_STRUCTURAL", + "EQ_COMPARE" +}; typedef bool (*type_comparison_func_t)(const_tree, const_tree); static type_comparison_func_t comparisons[type_comparisons] = { + eq_pointer, + eq_identifier, eq_main_variant, eq_canonical, eq_type_structural, @@ -132,6 +151,55 @@ print_types_in_set(typeset &types) } } +static const bool +filter_comparisons_functions_char(const char* function_name) +{ + // Everything should run + if (!flag_tp_comparison_functions) return true; + + const size_t buffer_size = 1024; + const size_t cli_length = strlen(flag_tp_comparison_functions); + gcc_assert(buffer_size > cli_length); + char whitelist[buffer_size]; + strcpy(whitelist, flag_tp_comparison_functions); + + + char* saveptr = whitelist; + char* token = NULL; + while (token = strtok_r(saveptr, ",", &saveptr)) + { + const bool name_allowed = strcmp(token, function_name) == 0; + if (name_allowed) return true; + } + + return false; +} + +static const bool +filter_comparisons_functions_int(unsigned function_id) +{ + if (!flag_tp_comparison_functions) return true; + + const char* function_name = type_playground::names[function_id]; + return filter_comparisons_functions_char(function_name); +} + +static const bool +filter_comparisons_functions(type_playground::type_comparison_func_t func) +{ + if (!flag_tp_comparison_functions) return true; + + for (unsigned i = 0; i < type_playground::type_comparisons; i++) + { + if (func != type_playground::comparisons[i]) continue; + + return filter_comparisons_functions_int(i); + } + + return false; +} + + static void compare_types_in_set(typeset &types) { @@ -145,6 +213,9 @@ compare_types_in_set(typeset &types) for (unsigned k = 0; k < type_playground::type_comparisons; k++) { type_playground::type_comparison_func_t comparison = type_playground::comparisons[k]; + const bool allowed_to_run = filter_comparisons_functions(comparison); + if (!allowed_to_run) continue; + const bool result = comparison(a, b); log("%s, ", result ? "t" : "f"); } diff --git a/gcc/name-types.c b/gcc/name-types.c index 693ebf28400..44ff4021153 100644 --- a/gcc/name-types.c +++ b/gcc/name-types.c @@ -105,6 +105,24 @@ type_to_string_get_type_size(const_tree type) return 0; } +const std::string +get_type_identifier(const_tree type) +{ + tree name = TYPE_NAME(type); + // The TYPE_NAME will be NULL_TREE for a type + // that is not a built-in type, the result of a typedef + // or a named class type. + const bool no_name = NULL_TREE == name; + if (no_name) return std::string(""); + + const enum tree_code name_code = TREE_CODE(name); + const bool is_name_type_decl = TYPE_DECL == name_code; + name = is_name_type_decl ? DECL_NAME(name) : name; + const char* identifier_ptr = IDENTIFIER_POINTER(name); + gcc_assert(identifier_ptr); + return std::string(identifier_ptr); +} + static const std::string type_to_string_get_record_name(const_tree type) { diff --git a/gcc/name-types.h b/gcc/name-types.h index a56b459b87f..538956fdd5d 100644 --- a/gcc/name-types.h +++ b/gcc/name-types.h @@ -4,6 +4,7 @@ #include const std::string type_to_string(const_tree type, const unsigned field_offset=0, const bool add_prelude=true); +const std::string get_type_identifier(const_tree type); namespace test_naming_types { void run_tests(); -- cgit v1.2.3 From fad38b1253bcc4e47e25a3a795b32798d521972b Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Tue, 12 May 2020 15:06:10 +0200 Subject: Filtering out types based on cli --- gcc/ipa-hello-world.c | 30 ++++++++++++++++++++++++++++++ 1 file changed, 30 insertions(+) diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c index b3f85d2e85c..e3ea729bbb9 100644 --- a/gcc/ipa-hello-world.c +++ b/gcc/ipa-hello-world.c @@ -224,6 +224,35 @@ compare_types_in_set(typeset &types) } } +static void +filter_out_types_in_set(typeset &types) +{ + // compare everything + if (!flag_tp_types_compared) return; + + const size_t buffer_size = 1024; + const size_t cli_length = strlen(flag_tp_comparison_functions); + gcc_assert(buffer_size > cli_length); + char whitelist[buffer_size]; + strcpy(whitelist, flag_tp_types_compared); + + bool name_allowed = false; + for (auto it = types.cbegin(); it != types.cend(); name_allowed ? ++it : it = types.erase(it)) + { + const_tree type = *it; + std::string observed_name = get_type_identifier(type); + char* saveptr = whitelist; + char* expected_name = NULL; + name_allowed = false; + + while (expected_name = strtok_r(saveptr, ",", &saveptr)) + { + name_allowed |= strcmp(expected_name, observed_name.c_str()) == 0; + } + } + +} + static unsigned int iphw_execute() { @@ -237,6 +266,7 @@ iphw_execute() collect_types_from_functions_with_gimple_body(node, types); } + filter_out_types_in_set(types); compare_types_in_set(types); return 0; } -- cgit v1.2.3 From 811d3f835a293778ba61054191a217c4bdd8d961 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Tue, 12 May 2020 15:17:49 +0200 Subject: Add test case 00 --- gcc/testsuite/gcc.dg/ipa/type-playground-00.c | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) create mode 100644 gcc/testsuite/gcc.dg/ipa/type-playground-00.c diff --git a/gcc/testsuite/gcc.dg/ipa/type-playground-00.c b/gcc/testsuite/gcc.dg/ipa/type-playground-00.c new file mode 100644 index 00000000000..21180e53a4a --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/type-playground-00.c @@ -0,0 +1,21 @@ +/* { dg-do run } */ +/* { dg-options "-fipa-hello-world -fdump-ipa-hello-world -ftp-comparison-functions=EQ_POINTER -ftp-types-compared=int " } */ + +int +main () +{ + int a = 0; + const int b = 0; + return 0; +} + +// This is proof that comparing trees using only +// pointer equality yields different trees +// when types have different attributes. +// i.e. +// TREE_TYPE(a) == TREE_TYPE(b) +// evaluates to false + + +/* { dg-final { scan-ipa-dump "0,32:integer_type x 0,32:integer_type = f," "hello-world" } } */ + -- cgit v1.2.3 From f801efe2ec0080ce1e1677294326f0836455d413 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Wed, 13 May 2020 10:02:40 +0200 Subject: Proof for incomplete type structural inequality --- build.sh | 2 +- gcc/collect-types.c | 20 ++++++++++++-------- gcc/ipa-hello-world.c | 12 +----------- gcc/name-types.c | 2 +- gcc/passes.def | 2 +- gcc/testsuite/gcc.dg/ipa/type-playground-00.c | 6 +++--- gcc/testsuite/gcc.dg/ipa/type-playground-01.c | 19 +++++++++++++++++++ gcc/types-inlines.h | 26 ++++++++++++++++++++++++++ test.sh | 3 +++ 9 files changed, 67 insertions(+), 25 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/ipa/type-playground-01.c create mode 100755 test.sh diff --git a/build.sh b/build.sh index 711b8c4bd56..ab3ed67cc9c 100755 --- a/build.sh +++ b/build.sh @@ -10,6 +10,6 @@ pushd $HOME/code/gcc-build/ $OLDPWD/configure --disable-bootstrap --disable-libsanitizer --enable-__cxa_atexit --enable-shared --disable-libsanitizer --enable-languages=c,c++,fortran --enable-lto --enable-gold --enable-linker-build-id --with-cpu-emag --prefix="$HOME/code/${installdir}/" make -j `nproc` make install -j `nproc` -make check-gcc RUNTESTFLAGS="ipa.exp" +${OLDPWD}/test.sh popd diff --git a/gcc/collect-types.c b/gcc/collect-types.c index 3f04e0f8d45..01c019a2be8 100644 --- a/gcc/collect-types.c +++ b/gcc/collect-types.c @@ -77,25 +77,26 @@ collect_types_from_record_or_union_type(const_tree type, typeset &types) const bool is_record = RECORD_TYPE == code; const bool is_valid_input = is_union || is_record; gcc_assert(is_valid_input); + assert_is_complete(type); for (tree field = TYPE_FIELDS(type) ; field ; field = DECL_CHAIN(field)) { const_tree field_type = TREE_TYPE(field); - collect_types(field, types); + collect_types(field_type, types); } } static void collect_types_from_record_type(const_tree type, typeset &types) { - assert_is_type(type, RECORD_TYPE); + assert_is_complete_type(type, RECORD_TYPE); collect_types_from_record_or_union_type(type, types); } static void collect_types_from_union_type(const_tree type, typeset &types) { - assert_is_type(type, UNION_TYPE); + assert_is_complete_type(type, UNION_TYPE); collect_types_from_record_or_union_type(type, types); } @@ -103,6 +104,7 @@ static void collect_types_from_wrapper_type(const_tree type, typeset &types) { gcc_assert(type); + assert_is_complete(type); const_tree inner_type = TREE_TYPE(type); gcc_assert(inner_type); collect_types(inner_type, types); @@ -112,20 +114,21 @@ static void collect_types_from_pointer_type(const_tree type, typeset &types) { assert_is_type(type, POINTER_TYPE); + assert_is_complete(type); collect_types_from_wrapper_type(type, types); } static void collect_types_from_reference_type(const_tree type, typeset &types) { - assert_is_type(type, REFERENCE_TYPE); + assert_is_complete_type(type, REFERENCE_TYPE); collect_types_from_wrapper_type(type, types); } static void collect_types_from_array_type(const_tree type, typeset &types) { - assert_is_type(type, ARRAY_TYPE); + assert_is_complete_type(type, ARRAY_TYPE); collect_types_from_wrapper_type(type, types); } @@ -133,6 +136,7 @@ static void collect_types_from_function_or_method_type(const_tree type, typeset &types) { gcc_assert(type); + assert_is_complete(type); const enum tree_code code = TREE_CODE(type); const bool is_function = FUNCTION_TYPE == code; const bool is_method = METHOD_TYPE == code; @@ -155,14 +159,14 @@ collect_types_from_function_or_method_type(const_tree type, typeset &types) static void collect_types_from_function_type(const_tree type, typeset &types) { - assert_is_type(type, FUNCTION_TYPE); + assert_is_complete_type(type, FUNCTION_TYPE); collect_types_from_function_or_method_type(type, types); } static void collect_types_from_method_type(const_tree type, typeset &types) { - assert_is_type(type, METHOD_TYPE); + assert_is_complete_type(type, METHOD_TYPE); collect_types_from_function_or_method_type(type, types); } @@ -231,7 +235,7 @@ collect_types(const_tree type, typeset &types) case QUAL_UNION_TYPE: case LANG_TYPE: default: - //log("%s\n", get_tree_code_name(code)); + log("%s\n", get_tree_code_name(code)); gcc_unreachable(); break; } diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c index e3ea729bbb9..4f2622cec5f 100644 --- a/gcc/ipa-hello-world.c +++ b/gcc/ipa-hello-world.c @@ -66,16 +66,6 @@ static type_comparison_func_t comparisons[type_comparisons] = { }; } -inline void -log(const char* const fmt, ...) -{ - if (!dump_file) return; - - va_list args; - va_start(args, fmt); - vfprintf(dump_file, fmt, args); - va_end(args); -} static void collect_types_from_cnode_decl(cgraph_node *cnode, typeset &types) @@ -137,7 +127,7 @@ collect_types_from_functions_with_gimple_body(cgraph_node *cnode, typeset &types gcc_assert(cnode); collect_types_from_cnode_decl(cnode, types); collect_types_from_cnode_locals(cnode, types); - collect_types_from_cnode_ssa_names(cnode, types); + //collect_types_from_cnode_ssa_names(cnode, types); } static void diff --git a/gcc/name-types.c b/gcc/name-types.c index 44ff4021153..5629cc40a7f 100644 --- a/gcc/name-types.c +++ b/gcc/name-types.c @@ -74,7 +74,7 @@ type_to_string_get_field_name(const_tree field) const_tree decl_name = DECL_NAME(field); if (!decl_name) return std::string(""); - const char* identifier = IDENTIFIER_POINTER(field); + const char* identifier = IDENTIFIER_POINTER(decl_name); return std::string(identifier); } diff --git a/gcc/passes.def b/gcc/passes.def index 22e5cf21e35..66f333f81dc 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -149,6 +149,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_ipa_profile); NEXT_PASS (pass_ipa_icf); NEXT_PASS (pass_ipa_devirt); + NEXT_PASS (pass_ipa_hello_world); NEXT_PASS (pass_ipa_cp); NEXT_PASS (pass_ipa_sra); NEXT_PASS (pass_ipa_cdtor_merge); @@ -171,7 +172,6 @@ along with GCC; see the file COPYING3. If not see compiled unit. */ INSERT_PASSES_AFTER (all_late_ipa_passes) NEXT_PASS (pass_materialize_all_clones); - NEXT_PASS (pass_ipa_hello_world); NEXT_PASS (pass_ipa_pta); NEXT_PASS (pass_omp_simd_clone); TERMINATE_PASS_LIST (all_late_ipa_passes) diff --git a/gcc/testsuite/gcc.dg/ipa/type-playground-00.c b/gcc/testsuite/gcc.dg/ipa/type-playground-00.c index 21180e53a4a..708b4d9d785 100644 --- a/gcc/testsuite/gcc.dg/ipa/type-playground-00.c +++ b/gcc/testsuite/gcc.dg/ipa/type-playground-00.c @@ -1,5 +1,5 @@ -/* { dg-do run } */ -/* { dg-options "-fipa-hello-world -fdump-ipa-hello-world -ftp-comparison-functions=EQ_POINTER -ftp-types-compared=int " } */ +/* { dg-do link } */ +/* { dg-options "-flto -fipa-hello-world -fdump-ipa-hello-world -ftp-comparison-functions=EQ_POINTER -ftp-types-compared=int " } */ int main () @@ -17,5 +17,5 @@ main () // evaluates to false -/* { dg-final { scan-ipa-dump "0,32:integer_type x 0,32:integer_type = f," "hello-world" } } */ +/* { dg-final { scan-wpa-ipa-dump "0,32:integer_type x 0,32:integer_type = t," "hello-world" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/type-playground-01.c b/gcc/testsuite/gcc.dg/ipa/type-playground-01.c new file mode 100644 index 00000000000..4abd3aa6161 --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/type-playground-01.c @@ -0,0 +1,19 @@ +/* { dg-do run } */ +/* { dg-options "-flto -fipa-hello-world -fdump-ipa-hello-world -ftp-comparison-functions=EQ_STRUCTURAL -ftp-types-compared=astruct_s" } */ + +struct astruct_s { + struct astruct_s* a; +}; + +int +main(int argc, char* argv) +{ + struct astruct_s a; +} + +// This is proof that an incomplete type cannot be compared +// via structural equality. + +// 0,64:astruct_s {0,64:astruct_s {}*;} x 0,0:astruct_s {} = f, +// I am not an expert on regex +/* { dg-final { scan-wpa-ipa-dump "0,64:astruct_s .0,64:astruct_s ..... x 0,0:astruct_s .. = f," "hello-world" } } */ diff --git a/gcc/types-inlines.h b/gcc/types-inlines.h index 24bd23dddc9..1532ef198e8 100644 --- a/gcc/types-inlines.h +++ b/gcc/types-inlines.h @@ -1,5 +1,25 @@ #pragma once + +inline void +log(const char* const fmt, ...) +{ + if (!dump_file) return; + + va_list args; + va_start(args, fmt); + vfprintf(dump_file, fmt, args); + va_end(args); +} + +inline void +assert_is_complete(const_tree a) +{ + //gcc_assert(a); + //const_tree type_size = TYPE_SIZE(a); + //gcc_assert(NULL_TREE != type_size); +} + inline void assert_is_type(const_tree a, const enum tree_code expected_code) { @@ -9,3 +29,9 @@ assert_is_type(const_tree a, const enum tree_code expected_code) gcc_assert(eq_codes); } +inline void +assert_is_complete_type(const_tree a, const enum tree_code expected_code) +{ + //assert_is_complete(a); + assert_is_type(a, expected_code); +} diff --git a/test.sh b/test.sh new file mode 100755 index 00000000000..d649022ea72 --- /dev/null +++ b/test.sh @@ -0,0 +1,3 @@ +pushd ${HOME}/code/gcc-build +make check-gcc RUNTESTFLAGS="ipa.exp" +popd -- cgit v1.2.3 From bee50c9b1551d178c1248be3a582ee3d198ef6e8 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Wed, 13 May 2020 11:49:17 +0200 Subject: Successfully understand how incomplete types are compared --- gcc/compare-types.c | 25 ++++++++++++++++++++++++- gcc/compare-types.h | 1 + gcc/ipa-hello-world.c | 3 +++ gcc/testsuite/gcc.dg/ipa/type-playground-02.c | 19 +++++++++++++++++++ gcc/testsuite/gcc.dg/ipa/type-playground-03.c | 25 +++++++++++++++++++++++++ gcc/testsuite/gcc.dg/ipa/type-playground-04.c | 25 +++++++++++++++++++++++++ 6 files changed, 97 insertions(+), 1 deletion(-) create mode 100644 gcc/testsuite/gcc.dg/ipa/type-playground-02.c create mode 100644 gcc/testsuite/gcc.dg/ipa/type-playground-03.c create mode 100644 gcc/testsuite/gcc.dg/ipa/type-playground-04.c diff --git a/gcc/compare-types.c b/gcc/compare-types.c index 33021d5feb0..e8a2611eca0 100644 --- a/gcc/compare-types.c +++ b/gcc/compare-types.c @@ -32,6 +32,14 @@ #include "types-inlines.h" #include "name-types.h" +static bool +is_incomplete_type(const_tree a) +{ + gcc_assert(a); + const_tree type_size = TYPE_SIZE(a); + return NULL_TREE == type_size; +} + bool eq_main_variant(const_tree a, const_tree b) { @@ -43,7 +51,7 @@ eq_main_variant(const_tree a, const_tree b) return are_equal; } -static bool +bool eq_canonical_internal(const_tree a, const_tree b) { gcc_assert(a && b); @@ -296,9 +304,24 @@ bool eq_types(const_tree a, const_tree b, const bool force_structural) { gcc_assert(a && b); + // This should be before comparing incomplete types. + // This is not enabled by default, and it is used for + // testing structural equality limitations. if (force_structural) return eq_structural(a, b, force_structural); + // eq_structural (a-incomplete, a-complete) = false + // eq_main_variant(a-incomplete, a-complete) = false + // eq_canonical (a-incomplete, a-complete) = false + // Fallback to eq_identifier only here. + // This should be the only static call to eq_identifier! + const bool is_a_incomplete = is_incomplete_type(a); + const bool is_b_incomplete = is_incomplete_type(b); + const bool compare_incomplete_types = is_a_incomplete || is_b_incomplete; + if (compare_incomplete_types) return eq_identifier(a, b); + + if (eq_main_variant(a, b)) return true; + if (!eq_canonical(a, b)) return false; // optimistic... diff --git a/gcc/compare-types.h b/gcc/compare-types.h index 7f33684e927..2c690fc3081 100644 --- a/gcc/compare-types.h +++ b/gcc/compare-types.h @@ -5,6 +5,7 @@ extern bool eq_identifier(const_tree a, const_tree b); extern bool eq_pointer(const_tree a, const_tree b); extern bool eq_main_variant(const_tree a, const_tree b); extern bool eq_canonical(const_tree a, const_tree b); +extern bool eq_canonical_internal(const_tree a, const_tree b); extern bool eq_type_compare(const_tree a, const_tree b); extern bool eq_type_structural(const_tree a, const_tree b); extern bool eq_types(const_tree a, const_tree b, const bool force_structural = false); diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c index 4f2622cec5f..8aa305f8812 100644 --- a/gcc/ipa-hello-world.c +++ b/gcc/ipa-hello-world.c @@ -43,6 +43,7 @@ enum type_comparison_func_enum { EQ_MAIN_VARIANT, EQ_CANONICAL, EQ_STRUCTURAL, + EQ_CANONICAL_STRICT, EQ_COMPARE, EQ_END }; @@ -52,6 +53,7 @@ static const char* names[type_comparisons] = { "EQ_IDENTIFIER", "EQ_MAIN_VARIANT", "EQ_CANONICAL", + "EQ_CANONICAL_STRICT", "EQ_STRUCTURAL", "EQ_COMPARE" }; @@ -61,6 +63,7 @@ static type_comparison_func_t comparisons[type_comparisons] = { eq_identifier, eq_main_variant, eq_canonical, + eq_canonical_internal, eq_type_structural, eq_type_compare }; diff --git a/gcc/testsuite/gcc.dg/ipa/type-playground-02.c b/gcc/testsuite/gcc.dg/ipa/type-playground-02.c new file mode 100644 index 00000000000..e45f0ae7038 --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/type-playground-02.c @@ -0,0 +1,19 @@ +/* { dg-do run } */ +/* { dg-options "-flto -fipa-hello-world -fdump-ipa-hello-world -ftp-comparison-functions=EQ_MAIN_VARIANT -ftp-types-compared=astruct_s" } */ + +struct astruct_s { + struct astruct_s* a; +}; + +int +main(int argc, char* argv) +{ + struct astruct_s a; +} + +// This is proof that an incomplete type cannot be compared +// via main variant equality. + +// 0,64:astruct_s {0,64:astruct_s {}*;} x 0,0:astruct_s {} = f, +// I am not an expert on regex +/* { dg-final { scan-wpa-ipa-dump "0,64:astruct_s .0,64:astruct_s ..... x 0,0:astruct_s .. = f," "hello-world" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/type-playground-03.c b/gcc/testsuite/gcc.dg/ipa/type-playground-03.c new file mode 100644 index 00000000000..515215aefae --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/type-playground-03.c @@ -0,0 +1,25 @@ +/* { dg-do run } */ +/* { dg-options "-flto -fipa-hello-world -fdump-ipa-hello-world -ftp-comparison-functions=EQ_IDENTIFIER -ftp-types-compared=astruct_s" } */ + +struct astruct_s { + struct astruct_s* a; +}; + +int +main(int argc, char* argv) +{ + struct astruct_s a; +} + +// This is proof that an incomplete type **CAN** be compared +// via identifier identity. +// Intuitevely, identifier identity may give false positives (and maybe false negatives too?) +// So, it must be the last resort comparisons. +// +// If we say that an identifier comparison may give false positives and false negatives +// then maybe it would be useful to documents attempts to explicitly produce false positives +// and false negatives to better understand what causes them. + +// 0,64:astruct_s {0,64:astruct_s {}*;} x 0,0:astruct_s {} = t, +// I am not an expert on regex +/* { dg-final { scan-wpa-ipa-dump "0,64:astruct_s .0,64:astruct_s ..... x 0,0:astruct_s .. = t," "hello-world" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/type-playground-04.c b/gcc/testsuite/gcc.dg/ipa/type-playground-04.c new file mode 100644 index 00000000000..ba1f7361c92 --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/type-playground-04.c @@ -0,0 +1,25 @@ +/* { dg-do run } */ +/* { dg-options "-flto -fipa-hello-world -fdump-ipa-hello-world -ftp-comparison-functions=EQ_CANONICAL -ftp-types-compared=astruct_s" } */ + +struct astruct_s { + struct astruct_s* a; +}; + +int +main(int argc, char* argv) +{ + struct astruct_s a; +} + +// This is proof that an incomplete type **CAN** be compared +// via identifier identity. +// Intuitevely, identifier identity may give false positives (and maybe false negatives too?) +// So, it must be the last resort comparisons. +// +// If we say that an identifier comparison may give false positives and false negatives +// then maybe it would be useful to documents attempts to explicitly produce false positives +// and false negatives to better understand what causes them. + +// 0,64:astruct_s {0,64:astruct_s {}*;} x 0,0:astruct_s {} = f, +// I am not an expert on regex +/* { dg-final { scan-wpa-ipa-dump "0,64:astruct_s .0,64:astruct_s ..... x 0,0:astruct_s .. = f," "hello-world" } } */ -- cgit v1.2.3 From 8b5eb52b20038577bc91974ad96f12d029912b67 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Wed, 13 May 2020 14:28:08 +0200 Subject: Fix inlines --- gcc/collect-types.c | 16 ++++++---------- gcc/types-inlines.h | 6 +++--- 2 files changed, 9 insertions(+), 13 deletions(-) diff --git a/gcc/collect-types.c b/gcc/collect-types.c index 01c019a2be8..fd25ff81be3 100644 --- a/gcc/collect-types.c +++ b/gcc/collect-types.c @@ -77,7 +77,6 @@ collect_types_from_record_or_union_type(const_tree type, typeset &types) const bool is_record = RECORD_TYPE == code; const bool is_valid_input = is_union || is_record; gcc_assert(is_valid_input); - assert_is_complete(type); for (tree field = TYPE_FIELDS(type) ; field ; field = DECL_CHAIN(field)) { @@ -89,14 +88,14 @@ collect_types_from_record_or_union_type(const_tree type, typeset &types) static void collect_types_from_record_type(const_tree type, typeset &types) { - assert_is_complete_type(type, RECORD_TYPE); + assert_is_type(type, RECORD_TYPE); collect_types_from_record_or_union_type(type, types); } static void collect_types_from_union_type(const_tree type, typeset &types) { - assert_is_complete_type(type, UNION_TYPE); + assert_is_type(type, UNION_TYPE); collect_types_from_record_or_union_type(type, types); } @@ -104,7 +103,6 @@ static void collect_types_from_wrapper_type(const_tree type, typeset &types) { gcc_assert(type); - assert_is_complete(type); const_tree inner_type = TREE_TYPE(type); gcc_assert(inner_type); collect_types(inner_type, types); @@ -114,21 +112,20 @@ static void collect_types_from_pointer_type(const_tree type, typeset &types) { assert_is_type(type, POINTER_TYPE); - assert_is_complete(type); collect_types_from_wrapper_type(type, types); } static void collect_types_from_reference_type(const_tree type, typeset &types) { - assert_is_complete_type(type, REFERENCE_TYPE); + assert_is_type(type, REFERENCE_TYPE); collect_types_from_wrapper_type(type, types); } static void collect_types_from_array_type(const_tree type, typeset &types) { - assert_is_complete_type(type, ARRAY_TYPE); + assert_is_type(type, ARRAY_TYPE); collect_types_from_wrapper_type(type, types); } @@ -136,7 +133,6 @@ static void collect_types_from_function_or_method_type(const_tree type, typeset &types) { gcc_assert(type); - assert_is_complete(type); const enum tree_code code = TREE_CODE(type); const bool is_function = FUNCTION_TYPE == code; const bool is_method = METHOD_TYPE == code; @@ -159,14 +155,14 @@ collect_types_from_function_or_method_type(const_tree type, typeset &types) static void collect_types_from_function_type(const_tree type, typeset &types) { - assert_is_complete_type(type, FUNCTION_TYPE); + assert_is_type(type, FUNCTION_TYPE); collect_types_from_function_or_method_type(type, types); } static void collect_types_from_method_type(const_tree type, typeset &types) { - assert_is_complete_type(type, METHOD_TYPE); + assert_is_type(type, METHOD_TYPE); collect_types_from_function_or_method_type(type, types); } diff --git a/gcc/types-inlines.h b/gcc/types-inlines.h index 1532ef198e8..340108fcf8f 100644 --- a/gcc/types-inlines.h +++ b/gcc/types-inlines.h @@ -15,9 +15,9 @@ log(const char* const fmt, ...) inline void assert_is_complete(const_tree a) { - //gcc_assert(a); - //const_tree type_size = TYPE_SIZE(a); - //gcc_assert(NULL_TREE != type_size); + gcc_assert(a); + const_tree type_size = TYPE_SIZE(a); + gcc_assert(NULL_TREE != type_size); } inline void -- cgit v1.2.3 From aaffff87dc28c6cb3f08569d3164245fb92498c1 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Wed, 13 May 2020 15:11:33 +0200 Subject: renames hello-world pass to escape-analysis --- build.sh | 12 ++++++------ gcc/common.opt | 4 ++-- gcc/ipa-hello-world.c | 16 ++++++++-------- gcc/passes.def | 2 +- gcc/testsuite/gcc.dg/ipa/type-playground-00.c | 4 ++-- gcc/testsuite/gcc.dg/ipa/type-playground-01.c | 4 ++-- gcc/testsuite/gcc.dg/ipa/type-playground-02.c | 4 ++-- gcc/testsuite/gcc.dg/ipa/type-playground-03.c | 4 ++-- gcc/testsuite/gcc.dg/ipa/type-playground-04.c | 4 ++-- gcc/tree-pass.h | 2 +- test.sh | 3 --- 11 files changed, 28 insertions(+), 31 deletions(-) delete mode 100755 test.sh diff --git a/build.sh b/build.sh index ab3ed67cc9c..f1ebba3e23c 100755 --- a/build.sh +++ b/build.sh @@ -3,13 +3,13 @@ set -e set -u -installdir=${1:-"gcc-inst"} -mkdir -p $HOME/code/gcc-build/ -mkdir -p $HOME/code/${installdir}/ -pushd $HOME/code/gcc-build/ -$OLDPWD/configure --disable-bootstrap --disable-libsanitizer --enable-__cxa_atexit --enable-shared --disable-libsanitizer --enable-languages=c,c++,fortran --enable-lto --enable-gold --enable-linker-build-id --with-cpu-emag --prefix="$HOME/code/${installdir}/" +suffix=${1:-""} +mkdir -p $HOME/code/gcc-build${suffix}/ +mkdir -p $HOME/code/gcc-inst${suffix}/ +pushd $HOME/code/gcc-build${suffix}/ +$OLDPWD/configure --disable-bootstrap --disable-libsanitizer --enable-__cxa_atexit --enable-shared --disable-libsanitizer --enable-languages=c,c++,fortran --enable-lto --enable-gold --enable-linker-build-id --with-cpu-emag --prefix="$HOME/code/gcc-inst${suffix}/" make -j `nproc` make install -j `nproc` -${OLDPWD}/test.sh +make check-gcc RUNTESTFLAGS="ipa.exp" popd diff --git a/gcc/common.opt b/gcc/common.opt index 4c97d6dda5f..5c626286a16 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -3413,8 +3413,8 @@ fipa-ra Common Report Var(flag_ipa_ra) Optimization Use caller save register across calls if possible. -fipa-hello-world -Common Report Var(flag_ipa_hello_world) Optimization +fipa-escape-analysis +Common Report Var(flag_ipa_escape_analysis) Optimization TBD ftp-types-compared= diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c index 8aa305f8812..678faed9f1f 100644 --- a/gcc/ipa-hello-world.c +++ b/gcc/ipa-hello-world.c @@ -265,10 +265,10 @@ iphw_execute() } namespace { -const pass_data pass_data_ipa_hello_world = +const pass_data pass_data_ipa_escape_analysis = { SIMPLE_IPA_PASS, - "hello-world", + "escape-analysis", OPTGROUP_NONE, TV_NONE, (PROP_cfg | PROP_ssa), @@ -278,20 +278,20 @@ const pass_data pass_data_ipa_hello_world = 0, }; -class pass_ipa_hello_world : public simple_ipa_opt_pass +class pass_ipa_escape_analysis : public simple_ipa_opt_pass { public: - pass_ipa_hello_world (gcc::context *ctx) - : simple_ipa_opt_pass(pass_data_ipa_hello_world, ctx) + pass_ipa_escape_analysis (gcc::context *ctx) + : simple_ipa_opt_pass(pass_data_ipa_escape_analysis, ctx) {} - virtual bool gate(function*) { return flag_ipa_hello_world; } + virtual bool gate(function*) { return flag_ipa_escape_analysis; } virtual unsigned execute (function*) { return iphw_execute(); } }; } // anon namespace simple_ipa_opt_pass* -make_pass_ipa_hello_world (gcc::context *ctx) +make_pass_ipa_escape_analysis (gcc::context *ctx) { - return new pass_ipa_hello_world (ctx); + return new pass_ipa_escape_analysis (ctx); } diff --git a/gcc/passes.def b/gcc/passes.def index 66f333f81dc..853e512e227 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -149,7 +149,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_ipa_profile); NEXT_PASS (pass_ipa_icf); NEXT_PASS (pass_ipa_devirt); - NEXT_PASS (pass_ipa_hello_world); + NEXT_PASS (pass_ipa_escape_analysis); NEXT_PASS (pass_ipa_cp); NEXT_PASS (pass_ipa_sra); NEXT_PASS (pass_ipa_cdtor_merge); diff --git a/gcc/testsuite/gcc.dg/ipa/type-playground-00.c b/gcc/testsuite/gcc.dg/ipa/type-playground-00.c index 708b4d9d785..6bddfac9939 100644 --- a/gcc/testsuite/gcc.dg/ipa/type-playground-00.c +++ b/gcc/testsuite/gcc.dg/ipa/type-playground-00.c @@ -1,5 +1,5 @@ /* { dg-do link } */ -/* { dg-options "-flto -fipa-hello-world -fdump-ipa-hello-world -ftp-comparison-functions=EQ_POINTER -ftp-types-compared=int " } */ +/* { dg-options "-flto -fipa-escape-analysis -fdump-ipa-escape-analysis -ftp-comparison-functions=EQ_POINTER -ftp-types-compared=int " } */ int main () @@ -17,5 +17,5 @@ main () // evaluates to false -/* { dg-final { scan-wpa-ipa-dump "0,32:integer_type x 0,32:integer_type = t," "hello-world" } } */ +/* { dg-final { scan-wpa-ipa-dump "0,32:integer_type x 0,32:integer_type = t," "escape-analysis" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/type-playground-01.c b/gcc/testsuite/gcc.dg/ipa/type-playground-01.c index 4abd3aa6161..f85ecc13ef1 100644 --- a/gcc/testsuite/gcc.dg/ipa/type-playground-01.c +++ b/gcc/testsuite/gcc.dg/ipa/type-playground-01.c @@ -1,5 +1,5 @@ /* { dg-do run } */ -/* { dg-options "-flto -fipa-hello-world -fdump-ipa-hello-world -ftp-comparison-functions=EQ_STRUCTURAL -ftp-types-compared=astruct_s" } */ +/* { dg-options "-flto -fipa-escape-analysis -fdump-ipa-escape-analysis -ftp-comparison-functions=EQ_STRUCTURAL -ftp-types-compared=astruct_s" } */ struct astruct_s { struct astruct_s* a; @@ -16,4 +16,4 @@ main(int argc, char* argv) // 0,64:astruct_s {0,64:astruct_s {}*;} x 0,0:astruct_s {} = f, // I am not an expert on regex -/* { dg-final { scan-wpa-ipa-dump "0,64:astruct_s .0,64:astruct_s ..... x 0,0:astruct_s .. = f," "hello-world" } } */ +/* { dg-final { scan-wpa-ipa-dump "0,64:astruct_s .0,64:astruct_s ..... x 0,0:astruct_s .. = f," "escape-analysis" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/type-playground-02.c b/gcc/testsuite/gcc.dg/ipa/type-playground-02.c index e45f0ae7038..128dc8f3b82 100644 --- a/gcc/testsuite/gcc.dg/ipa/type-playground-02.c +++ b/gcc/testsuite/gcc.dg/ipa/type-playground-02.c @@ -1,5 +1,5 @@ /* { dg-do run } */ -/* { dg-options "-flto -fipa-hello-world -fdump-ipa-hello-world -ftp-comparison-functions=EQ_MAIN_VARIANT -ftp-types-compared=astruct_s" } */ +/* { dg-options "-flto -fipa-escape-analysis -fdump-ipa-escape-analysis -ftp-comparison-functions=EQ_MAIN_VARIANT -ftp-types-compared=astruct_s" } */ struct astruct_s { struct astruct_s* a; @@ -16,4 +16,4 @@ main(int argc, char* argv) // 0,64:astruct_s {0,64:astruct_s {}*;} x 0,0:astruct_s {} = f, // I am not an expert on regex -/* { dg-final { scan-wpa-ipa-dump "0,64:astruct_s .0,64:astruct_s ..... x 0,0:astruct_s .. = f," "hello-world" } } */ +/* { dg-final { scan-wpa-ipa-dump "0,64:astruct_s .0,64:astruct_s ..... x 0,0:astruct_s .. = f," "escape-analysis" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/type-playground-03.c b/gcc/testsuite/gcc.dg/ipa/type-playground-03.c index 515215aefae..4ffe949f826 100644 --- a/gcc/testsuite/gcc.dg/ipa/type-playground-03.c +++ b/gcc/testsuite/gcc.dg/ipa/type-playground-03.c @@ -1,5 +1,5 @@ /* { dg-do run } */ -/* { dg-options "-flto -fipa-hello-world -fdump-ipa-hello-world -ftp-comparison-functions=EQ_IDENTIFIER -ftp-types-compared=astruct_s" } */ +/* { dg-options "-flto -fipa-escape-analysis -fdump-ipa-escape-analysis -ftp-comparison-functions=EQ_IDENTIFIER -ftp-types-compared=astruct_s" } */ struct astruct_s { struct astruct_s* a; @@ -22,4 +22,4 @@ main(int argc, char* argv) // 0,64:astruct_s {0,64:astruct_s {}*;} x 0,0:astruct_s {} = t, // I am not an expert on regex -/* { dg-final { scan-wpa-ipa-dump "0,64:astruct_s .0,64:astruct_s ..... x 0,0:astruct_s .. = t," "hello-world" } } */ +/* { dg-final { scan-wpa-ipa-dump "0,64:astruct_s .0,64:astruct_s ..... x 0,0:astruct_s .. = t," "escape-analysis" } } */ diff --git a/gcc/testsuite/gcc.dg/ipa/type-playground-04.c b/gcc/testsuite/gcc.dg/ipa/type-playground-04.c index ba1f7361c92..7b490f6eca3 100644 --- a/gcc/testsuite/gcc.dg/ipa/type-playground-04.c +++ b/gcc/testsuite/gcc.dg/ipa/type-playground-04.c @@ -1,5 +1,5 @@ /* { dg-do run } */ -/* { dg-options "-flto -fipa-hello-world -fdump-ipa-hello-world -ftp-comparison-functions=EQ_CANONICAL -ftp-types-compared=astruct_s" } */ +/* { dg-options "-flto -fipa-escape-analysis -fdump-ipa-escape-analysis -ftp-comparison-functions=EQ_CANONICAL -ftp-types-compared=astruct_s" } */ struct astruct_s { struct astruct_s* a; @@ -22,4 +22,4 @@ main(int argc, char* argv) // 0,64:astruct_s {0,64:astruct_s {}*;} x 0,0:astruct_s {} = f, // I am not an expert on regex -/* { dg-final { scan-wpa-ipa-dump "0,64:astruct_s .0,64:astruct_s ..... x 0,0:astruct_s .. = f," "hello-world" } } */ +/* { dg-final { scan-wpa-ipa-dump "0,64:astruct_s .0,64:astruct_s ..... x 0,0:astruct_s .. = f," "escape-analysis" } } */ diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 377dda689cc..a35ac21d324 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -501,7 +501,7 @@ extern ipa_opt_pass_d *make_pass_ipa_fn_summary (gcc::context *ctxt); extern ipa_opt_pass_d *make_pass_ipa_inline (gcc::context *ctxt); extern simple_ipa_opt_pass *make_pass_ipa_free_lang_data (gcc::context *ctxt); extern simple_ipa_opt_pass *make_pass_ipa_free_fn_summary (gcc::context *ctxt); -extern simple_ipa_opt_pass *make_pass_ipa_hello_world (gcc::context *ctxt); +extern simple_ipa_opt_pass *make_pass_ipa_escape_analysis (gcc::context *ctxt); extern ipa_opt_pass_d *make_pass_ipa_cp (gcc::context *ctxt); extern ipa_opt_pass_d *make_pass_ipa_sra (gcc::context *ctxt); extern ipa_opt_pass_d *make_pass_ipa_icf (gcc::context *ctxt); diff --git a/test.sh b/test.sh deleted file mode 100755 index d649022ea72..00000000000 --- a/test.sh +++ /dev/null @@ -1,3 +0,0 @@ -pushd ${HOME}/code/gcc-build -make check-gcc RUNTESTFLAGS="ipa.exp" -popd -- cgit v1.2.3 From 34883e842c8f5cec4c93fd383d712f879240b7dc Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Wed, 13 May 2020 20:57:30 +0200 Subject: working on escape analysis --- gcc/Makefile.in | 2 +- gcc/compare-types.c | 1 - gcc/ipa-escape-analysis.c | 531 ++++++++++++++++++++++++++++++++++++++++++++++ gcc/ipa-hello-world.c | 297 -------------------------- 4 files changed, 532 insertions(+), 299 deletions(-) create mode 100644 gcc/ipa-escape-analysis.c delete mode 100644 gcc/ipa-hello-world.c diff --git a/gcc/Makefile.in b/gcc/Makefile.in index e8e22d88706..523e3045fe8 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1403,7 +1403,7 @@ OBJS = \ incpath.o \ init-regs.o \ internal-fn.o \ - ipa-hello-world.o \ + ipa-escape-analysis.o \ compare-types.o \ collect-types.o \ name-types.o \ diff --git a/gcc/compare-types.c b/gcc/compare-types.c index e8a2611eca0..cc81577fc9b 100644 --- a/gcc/compare-types.c +++ b/gcc/compare-types.c @@ -57,7 +57,6 @@ eq_canonical_internal(const_tree a, const_tree b) gcc_assert(a && b); const_tree canonical_a = TYPE_CANONICAL(a); const_tree canonical_b = TYPE_CANONICAL(b); - gcc_assert(canonical_a && canonical_b); const bool are_equal = canonical_a == canonical_b; return are_equal; } diff --git a/gcc/ipa-escape-analysis.c b/gcc/ipa-escape-analysis.c new file mode 100644 index 00000000000..b9119009042 --- /dev/null +++ b/gcc/ipa-escape-analysis.c @@ -0,0 +1,531 @@ +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "gimple-expr.h" +#include "predict.h" +#include "alloc-pool.h" +#include "tree-pass.h" +#include "cgraph.h" +#include "diagnostic.h" +#include "fold-const.h" +#include "gimple-fold.h" +#include "symbol-summary.h" +#include "tree-vrp.h" +#include "ipa-prop.h" +#include "tree-pretty-print.h" +#include "tree-inline.h" +#include "ipa-fnsummary.h" +#include "ipa-utils.h" +#include "tree-ssa-ccp.h" +#include "stringpool.h" +#include "attribs.h" +#include "tree-ssa-alias.h" +#include "tree-ssanames.h" +#include "gimple.h" +#include "cfg.h" +#include "gimple-iterator.h" +#include "gimple-ssa.h" + +#include "compare-types.h" +#include "types-inlines.h" +#include +#include + +#include "collect-types.h" +#include "name-types.h" + +namespace type_playground { +enum type_comparison_func_enum { + EQ_POINTER = 0, + EQ_IDENTIFIER, + EQ_MAIN_VARIANT, + EQ_CANONICAL, + EQ_STRUCTURAL, + EQ_CANONICAL_STRICT, + EQ_COMPARE, + EQ_END +}; +static unsigned const type_comparisons = EQ_END; +static const char* names[type_comparisons] = { + "EQ_POINTER", + "EQ_IDENTIFIER", + "EQ_MAIN_VARIANT", + "EQ_CANONICAL", + "EQ_CANONICAL_STRICT", + "EQ_STRUCTURAL", + "EQ_COMPARE" +}; +typedef bool (*type_comparison_func_t)(const_tree, const_tree); +static type_comparison_func_t comparisons[type_comparisons] = { + eq_pointer, + eq_identifier, + eq_main_variant, + eq_canonical, + eq_canonical_internal, + eq_type_structural, + eq_type_compare +}; +} +static void collect_types_from_expr(const_tree expr, typeset &types); + +inline void +is_gimple_code(gimple *stmt, const enum gimple_code ex_code) +{ + gcc_assert(stmt); + const enum gimple_code ob_code = gimple_code(stmt); + const bool succeeds = ex_code == ob_code; + gcc_assert(succeeds); +} + +inline void +is_gimple_rhs_class(gimple *stmt, const enum gimple_rhs_class ex_class) +{ + gcc_assert(stmt); + is_gimple_code(stmt, GIMPLE_ASSIGN); + const enum gimple_rhs_class ob_class = gimple_assign_rhs_class(stmt); + const bool succeeds = ex_class == ob_class; + gcc_assert(succeeds); +} + +static void +collect_types_from_ssa_name(const_tree expr, typeset &types) +{ + assert_is_type(expr, SSA_NAME); + const_tree type = TREE_TYPE(expr); + gcc_assert(type); + collect_types(type, types); +} + +static void +collect_types_from_component_ref(const_tree expr, typeset &types) +{ + assert_is_type(expr, COMPONENT_REF); + const_tree _struct = TREE_OPERAND(expr, 0); + collect_types_from_expr(_struct, types); + gcc_assert(_struct); + const_tree _field = TREE_OPERAND(expr, 1); + gcc_assert(_field); + collect_types_from_expr(_field, types); +} + +static void +collect_types_from_var_decl(const_tree expr, typeset &types) +{ + assert_is_type(expr, VAR_DECL); + const_tree type = TREE_TYPE(expr); + gcc_assert(type); + collect_types(type, types); +} + +static void +collect_types_from_field_decl(const_tree expr, typeset &types) +{ +} + +static void +collect_types_from_expr(const_tree expr, typeset &types) +{ + // We are interested in collecting all types which + // point to a RECORD_TYPE. + // Therefore, it is not necessary to consider unfeasible paths. + gcc_assert(expr); + const enum tree_code code = TREE_CODE(expr); + switch (code) + { + case COMPONENT_REF: + collect_types_from_component_ref(expr, types); + break; + case SSA_NAME: + collect_types_from_ssa_name(expr, types); + break; + case VAR_DECL: + collect_types_from_var_decl(expr, types); + break; + case FIELD_DECL: + collect_types_from_field_decl(expr, types); + break; + break; + default: + log("tree_code: %s\n", get_tree_code_name(code)); + break; + } +} + +static void +collect_types_from_stmt_assign_lhs(gimple *stmt, typeset &types) +{ + is_gimple_code(stmt, GIMPLE_ASSIGN); + const_tree lhs = gimple_assign_lhs(stmt); + gcc_assert(lhs); + collect_types_from_expr(lhs, types); +} + +static void +collect_types_from_stmt_assign_rhs3(gimple *stmt, typeset &types) +{ + is_gimple_rhs_class(stmt, GIMPLE_TERNARY_RHS); + const_tree rhs = gimple_assign_rhs3(stmt); + gcc_assert(rhs); + collect_types_from_expr(rhs, types); +} + +static void +collect_types_from_stmt_assign_rhs2(gimple *stmt, typeset &types) +{ + is_gimple_code(stmt, GIMPLE_ASSIGN); + const enum gimple_rhs_class gclass = gimple_assign_rhs_class(stmt); + const bool is_ternary = GIMPLE_TERNARY_RHS == gclass; + const bool is_binary = GIMPLE_BINARY_RHS == gclass; + const bool is_valid_input = is_ternary || is_binary; + gcc_assert(is_valid_input); + const_tree rhs = gimple_assign_rhs2(stmt); + gcc_assert(rhs); + collect_types_from_expr(rhs, types); +} + +static void +collect_types_from_stmt_assign_rhs1(gimple *stmt, typeset &types) +{ + is_gimple_code(stmt, GIMPLE_ASSIGN); + const enum gimple_rhs_class gclass = gimple_assign_rhs_class(stmt); + const bool is_ternary = GIMPLE_TERNARY_RHS == gclass; + const bool is_binary = GIMPLE_BINARY_RHS == gclass; + const bool is_unary = GIMPLE_UNARY_RHS == gclass; + const bool is_single = GIMPLE_SINGLE_RHS == gclass; + const bool is_valid_input = is_ternary || is_binary || is_unary || is_single; + gcc_assert(is_valid_input); + const_tree rhs = gimple_assign_rhs1(stmt); + gcc_assert(rhs); + collect_types_from_expr(rhs, types); +} + +static void +collect_types_from_stmt_assign_rhs(gimple *stmt, typeset &types) +{ + is_gimple_code(stmt, GIMPLE_ASSIGN); + const enum gimple_rhs_class gclass = gimple_assign_rhs_class(stmt); + switch (gclass) + { + case GIMPLE_TERNARY_RHS: + collect_types_from_stmt_assign_rhs3(stmt, types); + /* fall-through */ + case GIMPLE_BINARY_RHS: + collect_types_from_stmt_assign_rhs2(stmt, types); + /* fall-through */ + case GIMPLE_UNARY_RHS: + case GIMPLE_SINGLE_RHS: + collect_types_from_stmt_assign_rhs1(stmt, types); + break; + default: + gcc_unreachable(); + break; + } +} + +static void +collect_types_from_stmt_assign(gimple *stmt, typeset &types) +{ + is_gimple_code(stmt, GIMPLE_ASSIGN); + collect_types_from_stmt_assign_lhs(stmt, types); + collect_types_from_stmt_assign_rhs(stmt, types); +} + +static void +collect_types_from_stmt_call(gimple *stmt, typeset &types) +{ + is_gimple_code(stmt, GIMPLE_CALL); + //TODO: +} + +static void +collect_types_from_stmt_cond(gimple *stmt, typeset &types) +{ + is_gimple_code(stmt, GIMPLE_COND); + //TODO: +} + +static void +collect_types_from_stmt(gimple *stmt, typeset &types) +{ + gcc_assert(stmt); + const enum gimple_code code = gimple_code(stmt); + switch (code) + { + case GIMPLE_ASSIGN: + collect_types_from_stmt_assign(stmt, types); + break; + case GIMPLE_CALL: + collect_types_from_stmt_call(stmt, types); + break; + case GIMPLE_COND: + collect_types_from_stmt_cond(stmt, types); + break; + default: + //TODO: + break; + } +} + +static void +collect_types_from_cnode_decl(cgraph_node *cnode, typeset &types) +{ + gcc_assert(cnode); + const_tree decl = cnode->decl; + gcc_assert(decl); + const_tree decl_type = TREE_TYPE(decl); + gcc_assert(decl_type); + function *func = DECL_STRUCT_FUNCTION (decl); + gcc_assert(func); + push_cfun(func); + // This will collect return, arguments and decl_type itself + collect_types(decl_type, types); + pop_cfun(); +} + +static void +collect_types_from_cnode_locals(cgraph_node *cnode, typeset &types) +{ + gcc_assert(cnode); + const_tree decl = cnode->decl; + gcc_assert(decl); + function *func = DECL_STRUCT_FUNCTION (decl); + gcc_assert(func); + int i = 0; + tree var_decl = NULL; + FOR_EACH_LOCAL_DECL(func, i, var_decl) + { + gcc_assert(var_decl); + const_tree var_decl_type = TREE_TYPE(var_decl); + collect_types(var_decl_type, types); + } +} + +static void +collect_types_from_cnode_ssa_names(cgraph_node *cnode, typeset &types) +{ + gcc_assert(cnode); + const_tree decl = cnode->decl; + gcc_assert(decl); + function *func = DECL_STRUCT_FUNCTION (decl); + gcc_assert(func); + size_t i = 0; + tree ssa_name = NULL; + push_cfun(func); + FOR_EACH_SSA_NAME(i, ssa_name, cfun) + { + gcc_assert(ssa_name); + const_tree ssa_name_type = TREE_TYPE(ssa_name); + collect_types(ssa_name_type, types); + } + pop_cfun(); +} + +static void +collect_types_from_bb(basic_block bb, typeset &types) +{ + gcc_assert(bb); + for (auto gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) + { + gimple *stmt = gsi_stmt(gsi); + gcc_assert(stmt); + collect_types_from_stmt(stmt, types); + } +} + +static void +collect_types_from_cnode_bb(cgraph_node *cnode, typeset &types) +{ + gcc_assert(cnode); + cnode->get_untransformed_body(); + tree decl = cnode->decl; + gcc_assert(decl); + function *func = DECL_STRUCT_FUNCTION(decl); + gcc_assert(func); + basic_block bb = NULL; + push_cfun(func); + FOR_EACH_BB_FN(bb, func) + { + gcc_assert(bb); + collect_types_from_bb(bb, types); + } + pop_cfun(); +} + +static void +collect_types_from_functions_with_gimple_body(cgraph_node *cnode, typeset &types) +{ + gcc_assert(cnode); + collect_types_from_cnode_decl(cnode, types); + collect_types_from_cnode_locals(cnode, types); + collect_types_from_cnode_ssa_names(cnode, types); + collect_types_from_cnode_bb(cnode, types); +} + +static void +print_types_in_set(typeset &types) +{ + for (auto it = types.cbegin(); it != types.cend(); ++it) + { + const_tree type = *it; + std::string name = type_to_string(type); + log("name: %s\n", name.c_str()); + } +} + +static const bool +filter_comparisons_functions_char(const char* function_name) +{ + // Everything should run + if (!flag_tp_comparison_functions) return true; + + const size_t buffer_size = 1024; + const size_t cli_length = strlen(flag_tp_comparison_functions); + gcc_assert(buffer_size > cli_length); + char whitelist[buffer_size]; + strcpy(whitelist, flag_tp_comparison_functions); + + + char* saveptr = whitelist; + char* token = NULL; + while (token = strtok_r(saveptr, ",", &saveptr)) + { + const bool name_allowed = strcmp(token, function_name) == 0; + if (name_allowed) return true; + } + + return false; +} + +static const bool +filter_comparisons_functions_int(unsigned function_id) +{ + if (!flag_tp_comparison_functions) return true; + + const char* function_name = type_playground::names[function_id]; + return filter_comparisons_functions_char(function_name); +} + +static const bool +filter_comparisons_functions(type_playground::type_comparison_func_t func) +{ + if (!flag_tp_comparison_functions) return true; + + for (unsigned i = 0; i < type_playground::type_comparisons; i++) + { + if (func != type_playground::comparisons[i]) continue; + + return filter_comparisons_functions_int(i); + } + + return false; +} + + +static void +compare_types_in_set(typeset &types) +{ + for (auto i = types.cbegin(); i != types.cend(); ++i) + { + for (auto j = types.cbegin(); j != types.cend(); ++j) + { + const_tree a = *i; + const_tree b = *j; + log("%s x %s = ", type_to_string(a).c_str(), type_to_string(b).c_str()); + for (unsigned k = 0; k < type_playground::type_comparisons; k++) + { + type_playground::type_comparison_func_t comparison = type_playground::comparisons[k]; + const bool allowed_to_run = filter_comparisons_functions(comparison); + if (!allowed_to_run) continue; + + const bool result = comparison(a, b); + log("%s, ", result ? "t" : "f"); + } + log("\n"); + } + } +} + +static void +filter_out_types_in_set(typeset &types) +{ + // compare everything + if (!flag_tp_types_compared) return; + + const size_t buffer_size = 1024; + const size_t cli_length = strlen(flag_tp_comparison_functions); + gcc_assert(buffer_size > cli_length); + char whitelist[buffer_size]; + strcpy(whitelist, flag_tp_types_compared); + + bool name_allowed = false; + for (auto it = types.cbegin(); it != types.cend(); name_allowed ? ++it : it = types.erase(it)) + { + const_tree type = *it; + std::string observed_name = get_type_identifier(type); + char* saveptr = whitelist; + char* expected_name = NULL; + name_allowed = false; + + while (expected_name = strtok_r(saveptr, ",", &saveptr)) + { + name_allowed |= strcmp(expected_name, observed_name.c_str()) == 0; + } + } + +} + +static unsigned int +iphw_execute() +{ + //test_type_equality::run_tests(); + //test_naming_types::run_tests(); + cgraph_node *node = NULL; + typeset types; + + FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(node) + { + node->get_untransformed_body(); + collect_types_from_functions_with_gimple_body(node, types); + } + + // We still need to collect types from + // the function signatures of functions without gimple bodies... + + filter_out_types_in_set(types); + compare_types_in_set(types); + return 0; +} + +namespace { +const pass_data pass_data_ipa_escape_analysis = +{ + SIMPLE_IPA_PASS, + "escape-analysis", + OPTGROUP_NONE, + TV_NONE, + (PROP_cfg | PROP_ssa), + 0, + 0, + TODO_rebuild_alias, + 0, +}; + +class pass_ipa_escape_analysis : public simple_ipa_opt_pass +{ +public: + pass_ipa_escape_analysis (gcc::context *ctx) + : simple_ipa_opt_pass(pass_data_ipa_escape_analysis, ctx) + {} + + virtual bool gate(function*) { return flag_ipa_escape_analysis; } + virtual unsigned execute (function*) { return iphw_execute(); } +}; +} // anon namespace + +simple_ipa_opt_pass* +make_pass_ipa_escape_analysis (gcc::context *ctx) +{ + return new pass_ipa_escape_analysis (ctx); +} diff --git a/gcc/ipa-hello-world.c b/gcc/ipa-hello-world.c deleted file mode 100644 index 678faed9f1f..00000000000 --- a/gcc/ipa-hello-world.c +++ /dev/null @@ -1,297 +0,0 @@ -#include "config.h" -#include "system.h" -#include "coretypes.h" -#include "backend.h" -#include "tree.h" -#include "gimple-expr.h" -#include "predict.h" -#include "alloc-pool.h" -#include "tree-pass.h" -#include "cgraph.h" -#include "diagnostic.h" -#include "fold-const.h" -#include "gimple-fold.h" -#include "symbol-summary.h" -#include "tree-vrp.h" -#include "ipa-prop.h" -#include "tree-pretty-print.h" -#include "tree-inline.h" -#include "ipa-fnsummary.h" -#include "ipa-utils.h" -#include "tree-ssa-ccp.h" -#include "stringpool.h" -#include "attribs.h" -#include "tree-ssa-alias.h" -#include "tree-ssanames.h" -#include "gimple.h" -#include "cfg.h" -#include "gimple-iterator.h" -#include "gimple-ssa.h" - -#include "compare-types.h" -#include "types-inlines.h" -#include -#include - -#include "collect-types.h" -#include "name-types.h" - -namespace type_playground { -enum type_comparison_func_enum { - EQ_POINTER = 0, - EQ_IDENTIFIER, - EQ_MAIN_VARIANT, - EQ_CANONICAL, - EQ_STRUCTURAL, - EQ_CANONICAL_STRICT, - EQ_COMPARE, - EQ_END -}; -static unsigned const type_comparisons = EQ_END; -static const char* names[type_comparisons] = { - "EQ_POINTER", - "EQ_IDENTIFIER", - "EQ_MAIN_VARIANT", - "EQ_CANONICAL", - "EQ_CANONICAL_STRICT", - "EQ_STRUCTURAL", - "EQ_COMPARE" -}; -typedef bool (*type_comparison_func_t)(const_tree, const_tree); -static type_comparison_func_t comparisons[type_comparisons] = { - eq_pointer, - eq_identifier, - eq_main_variant, - eq_canonical, - eq_canonical_internal, - eq_type_structural, - eq_type_compare -}; -} - - -static void -collect_types_from_cnode_decl(cgraph_node *cnode, typeset &types) -{ - gcc_assert(cnode); - const_tree decl = cnode->decl; - gcc_assert(decl); - const_tree decl_type = TREE_TYPE(decl); - gcc_assert(decl_type); - function *func = DECL_STRUCT_FUNCTION (decl); - gcc_assert(func); - push_cfun(func); - // This will collect return, arguments and decl_type itself - collect_types(decl_type, types); - pop_cfun(); -} - -static void -collect_types_from_cnode_locals(cgraph_node *cnode, typeset &types) -{ - gcc_assert(cnode); - const_tree decl = cnode->decl; - gcc_assert(decl); - function *func = DECL_STRUCT_FUNCTION (decl); - gcc_assert(func); - int i = 0; - tree var_decl = NULL; - FOR_EACH_LOCAL_DECL(func, i, var_decl) - { - gcc_assert(var_decl); - const_tree var_decl_type = TREE_TYPE(var_decl); - collect_types(var_decl_type, types); - } -} - -static void -collect_types_from_cnode_ssa_names(cgraph_node *cnode, typeset &types) -{ - gcc_assert(cnode); - const_tree decl = cnode->decl; - gcc_assert(decl); - function *func = DECL_STRUCT_FUNCTION (decl); - gcc_assert(func); - size_t i = 0; - tree ssa_name = NULL; - push_cfun(func); - FOR_EACH_SSA_NAME(i, ssa_name, cfun) - { - gcc_assert(ssa_name); - const_tree ssa_name_type = TREE_TYPE(ssa_name); - collect_types(ssa_name_type, types); - } - pop_cfun(); -} - -static void -collect_types_from_functions_with_gimple_body(cgraph_node *cnode, typeset &types) -{ - gcc_assert(cnode); - collect_types_from_cnode_decl(cnode, types); - collect_types_from_cnode_locals(cnode, types); - //collect_types_from_cnode_ssa_names(cnode, types); -} - -static void -print_types_in_set(typeset &types) -{ - for (auto it = types.cbegin(); it != types.cend(); ++it) - { - const_tree type = *it; - std::string name = type_to_string(type); - log("name: %s\n", name.c_str()); - } -} - -static const bool -filter_comparisons_functions_char(const char* function_name) -{ - // Everything should run - if (!flag_tp_comparison_functions) return true; - - const size_t buffer_size = 1024; - const size_t cli_length = strlen(flag_tp_comparison_functions); - gcc_assert(buffer_size > cli_length); - char whitelist[buffer_size]; - strcpy(whitelist, flag_tp_comparison_functions); - - - char* saveptr = whitelist; - char* token = NULL; - while (token = strtok_r(saveptr, ",", &saveptr)) - { - const bool name_allowed = strcmp(token, function_name) == 0; - if (name_allowed) return true; - } - - return false; -} - -static const bool -filter_comparisons_functions_int(unsigned function_id) -{ - if (!flag_tp_comparison_functions) return true; - - const char* function_name = type_playground::names[function_id]; - return filter_comparisons_functions_char(function_name); -} - -static const bool -filter_comparisons_functions(type_playground::type_comparison_func_t func) -{ - if (!flag_tp_comparison_functions) return true; - - for (unsigned i = 0; i < type_playground::type_comparisons; i++) - { - if (func != type_playground::comparisons[i]) continue; - - return filter_comparisons_functions_int(i); - } - - return false; -} - - -static void -compare_types_in_set(typeset &types) -{ - for (auto i = types.cbegin(); i != types.cend(); ++i) - { - for (auto j = types.cbegin(); j != types.cend(); ++j) - { - const_tree a = *i; - const_tree b = *j; - log("%s x %s = ", type_to_string(a).c_str(), type_to_string(b).c_str()); - for (unsigned k = 0; k < type_playground::type_comparisons; k++) - { - type_playground::type_comparison_func_t comparison = type_playground::comparisons[k]; - const bool allowed_to_run = filter_comparisons_functions(comparison); - if (!allowed_to_run) continue; - - const bool result = comparison(a, b); - log("%s, ", result ? "t" : "f"); - } - log("\n"); - } - } -} - -static void -filter_out_types_in_set(typeset &types) -{ - // compare everything - if (!flag_tp_types_compared) return; - - const size_t buffer_size = 1024; - const size_t cli_length = strlen(flag_tp_comparison_functions); - gcc_assert(buffer_size > cli_length); - char whitelist[buffer_size]; - strcpy(whitelist, flag_tp_types_compared); - - bool name_allowed = false; - for (auto it = types.cbegin(); it != types.cend(); name_allowed ? ++it : it = types.erase(it)) - { - const_tree type = *it; - std::string observed_name = get_type_identifier(type); - char* saveptr = whitelist; - char* expected_name = NULL; - name_allowed = false; - - while (expected_name = strtok_r(saveptr, ",", &saveptr)) - { - name_allowed |= strcmp(expected_name, observed_name.c_str()) == 0; - } - } - -} - -static unsigned int -iphw_execute() -{ - //test_type_equality::run_tests(); - //test_naming_types::run_tests(); - cgraph_node *node = NULL; - typeset types; - FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(node) - { - node->get_untransformed_body(); - collect_types_from_functions_with_gimple_body(node, types); - } - - filter_out_types_in_set(types); - compare_types_in_set(types); - return 0; -} - -namespace { -const pass_data pass_data_ipa_escape_analysis = -{ - SIMPLE_IPA_PASS, - "escape-analysis", - OPTGROUP_NONE, - TV_NONE, - (PROP_cfg | PROP_ssa), - 0, - 0, - TODO_rebuild_alias, - 0, -}; - -class pass_ipa_escape_analysis : public simple_ipa_opt_pass -{ -public: - pass_ipa_escape_analysis (gcc::context *ctx) - : simple_ipa_opt_pass(pass_data_ipa_escape_analysis, ctx) - {} - - virtual bool gate(function*) { return flag_ipa_escape_analysis; } - virtual unsigned execute (function*) { return iphw_execute(); } -}; -} // anon namespace - -simple_ipa_opt_pass* -make_pass_ipa_escape_analysis (gcc::context *ctx) -{ - return new pass_ipa_escape_analysis (ctx); -} -- cgit v1.2.3 From 50002c5ed291c8cc5b2c59692f94a8c7a19b8575 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Thu, 14 May 2020 10:18:01 +0200 Subject: fuzzing type collector --- gcc/compare-types.c | 2 +- gcc/ipa-escape-analysis.c | 272 ++++++++++++++++++++++++++++++++++++++++++---- gcc/name-types.c | 23 +++- 3 files changed, 271 insertions(+), 26 deletions(-) diff --git a/gcc/compare-types.c b/gcc/compare-types.c index cc81577fc9b..4be9d28151d 100644 --- a/gcc/compare-types.c +++ b/gcc/compare-types.c @@ -325,7 +325,7 @@ eq_types(const_tree a, const_tree b, const bool force_structural) // optimistic... // maybe we should have a MAYBE? - gcc_unreachable(); + //gcc_unreachable(); return false; } diff --git a/gcc/ipa-escape-analysis.c b/gcc/ipa-escape-analysis.c index b9119009042..a3d6a2cb191 100644 --- a/gcc/ipa-escape-analysis.c +++ b/gcc/ipa-escape-analysis.c @@ -90,50 +90,211 @@ is_gimple_rhs_class(gimple *stmt, const enum gimple_rhs_class ex_class) } static void -collect_types_from_ssa_name(const_tree expr, typeset &types) +collect_types_from_op(const_tree expr, typeset &types, unsigned n) { - assert_is_type(expr, SSA_NAME); + gcc_assert(expr); + const_tree op_n = TREE_OPERAND(expr, n); + gcc_assert(op_n); + collect_types_from_expr(op_n, types); +} + +static void +collect_types_from_op0(const_tree expr, typeset &types, const enum tree_code ex_code) +{ + assert_is_type(expr, ex_code); + collect_types_from_op(expr, types, 0); +} + +static void +collect_types_from_op1(const_tree expr, typeset &types, const enum tree_code ex_code) +{ + assert_is_type(expr, ex_code); + collect_types_from_op(expr, types, 0); + collect_types_from_op(expr, types, 1); +} + +static void +collect_types_from_addr_expr(const_tree expr, typeset &types) +{ + collect_types_from_op0(expr, types, ADDR_EXPR); +} + +static void +collect_types_from_component_ref(const_tree expr, typeset &types) +{ + collect_types_from_op1(expr, types, COMPONENT_REF); +} + +static void +collect_types_from_mem_ref(const_tree expr, typeset &types) +{ + collect_types_from_op1(expr, types, MEM_REF); +} + +static void +collect_types_from_array_ref(const_tree expr, typeset &types) +{ + collect_types_from_op1(expr, types, ARRAY_REF); +} + +static void +collect_types_from_leaf_expr(const_tree expr, typeset &types, const enum tree_code ex_code) +{ + assert_is_type(expr, ex_code); const_tree type = TREE_TYPE(expr); gcc_assert(type); collect_types(type, types); } static void -collect_types_from_component_ref(const_tree expr, typeset &types) +collect_types_from_ssa_name(const_tree expr, typeset &types) { - assert_is_type(expr, COMPONENT_REF); - const_tree _struct = TREE_OPERAND(expr, 0); - collect_types_from_expr(_struct, types); - gcc_assert(_struct); - const_tree _field = TREE_OPERAND(expr, 1); - gcc_assert(_field); - collect_types_from_expr(_field, types); + collect_types_from_leaf_expr(expr, types, SSA_NAME); } static void collect_types_from_var_decl(const_tree expr, typeset &types) { - assert_is_type(expr, VAR_DECL); + collect_types_from_leaf_expr(expr, types, VAR_DECL); +} + +static void +collect_types_from_field_decl(const_tree expr, typeset &types) +{ + collect_types_from_leaf_expr(expr, types, FIELD_DECL); +} + +static void +collect_types_from_integer_cst(const_tree expr, typeset &types) +{ + collect_types_from_leaf_expr(expr, types, INTEGER_CST); +} + +static void +collect_types_from_constructor_array(const_tree expr, typeset &types) +{ + assert_is_type(expr, CONSTRUCTOR); + const_tree type = TREE_TYPE(expr); + assert_is_type(type, ARRAY_TYPE); + //TODO: Collect types from here +} + +static void +collect_types_from_constructor_record_or_union(const_tree expr, typeset &types) +{ + assert_is_type(expr, CONSTRUCTOR); + const_tree type = TREE_TYPE(expr); + const enum tree_code code = TREE_CODE(type); + const bool is_record = RECORD_TYPE == code; + const bool is_union = UNION_TYPE == code; + const bool is_qual_union = QUAL_UNION_TYPE == code; + const bool is_valid_input = is_record || is_union || is_qual_union; + gcc_assert(is_valid_input); + //TODO: Collect types from here +} + +static void +collect_types_from_constructor(const_tree expr, typeset &types) +{ + // https://gcc.gnu.org/onlinedocs/gccint/Unary-and-Binary-Expressions.html#Unary-and-Binary-Expressions + // These nodes represent the brace-enclosed initializers for a structure or an array. + // They contain a sequence of component values made out of a vector of constructor_elt, which is a (INDEX, VALUE) pair. + // If the TREE_TYPE of the CONSTRUCTOR is a RECORD_TYPE, UNION_TYPE or QUAL_UNION_TYPE then + // the INDEX of each node in the sequence will be a FIELD_DECL and the VALUE will be the expression used to initialize that field. + // If the TREE_TYPE of the CONSTRUCTOR is an ARRAY_TYPE, then the INDEX of + // each node in the sequence will be an INTEGER_CST or a RANGE_EXPR of + // two INTEGER_CSTs. A single INTEGER_CST indicates which element of + // the array is being assigned to. A RANGE_EXPR indicates an inclusive range + // of elements to initialize. In both cases the VALUE is the + // corresponding initializer. It is re-evaluated for each element of + // a RANGE_EXPR. If the INDEX is NULL_TREE, then the initializer + // is for the next available array element. + assert_is_type(expr, CONSTRUCTOR); const_tree type = TREE_TYPE(expr); gcc_assert(type); - collect_types(type, types); + const enum tree_code code = TREE_CODE(type); + switch (code) + { + case RECORD_TYPE: + case UNION_TYPE: + case QUAL_UNION_TYPE: + case ARRAY_TYPE: + break; + default: + // TODO: I should fuzz this, I got a constructor of an integer type? + return; + break; + } + + const bool is_array = ARRAY_TYPE == code; + is_array ? collect_types_from_constructor_array(expr, types) : collect_types_from_constructor_record_or_union(expr, types); } static void -collect_types_from_field_decl(const_tree expr, typeset &types) +collect_types_from_parm_decl(const_tree expr, typeset &types) { + collect_types_from_leaf_expr(expr, types, PARM_DECL); +} + +static void +collect_types_from_real_cst(const_tree expr, typeset &types) +{ + collect_types_from_leaf_expr(expr, types, REAL_CST); +} + +static void +collect_types_from_string_cst(const_tree expr, typeset &types) +{ + collect_types_from_leaf_expr(expr, types, STRING_CST); +} + +static void +collect_types_from_bit_field_ref(const_tree expr, typeset &types) +{ + // TODO: How to collect types from bit_field_ref? +} + +static void +collect_types_from_view_convert_expr(const_tree expr, typeset &types) +{ + // VIEW_CONVERT_EXPR is used to interpret the bit representation + // of a register as a register of a different type. + // It is unspecified if this is allowed to change the + // register size. If disallowed this case needs to go + // through an integer mode and an intermediate BIT_FIELD_REF. + // https://gcc.gnu.org/wiki/MemRef + //TODO: How to collect types from VIEW_CONVERT_EXPR? +} + +static void +collect_types_from_result_decl(const_tree expr, typeset &types) +{ + collect_types_from_leaf_expr(expr, types, RESULT_DECL); } static void collect_types_from_expr(const_tree expr, typeset &types) { - // We are interested in collecting all types which - // point to a RECORD_TYPE. - // Therefore, it is not necessary to consider unfeasible paths. + // These are the codes I saw using csmith to fuzz. gcc_assert(expr); + const_tree type = TREE_TYPE(expr); + gcc_assert(type); + collect_types(type, types); const enum tree_code code = TREE_CODE(expr); switch (code) { + case ADDR_EXPR: + collect_types_from_addr_expr(expr, types); + break; + case BIT_FIELD_REF: + collect_types_from_bit_field_ref(expr, types); + break; + case ARRAY_REF: + collect_types_from_array_ref(expr, types); + break; + case MEM_REF: + collect_types_from_mem_ref(expr, types); + break; case COMPONENT_REF: collect_types_from_component_ref(expr, types); break; @@ -146,9 +307,30 @@ collect_types_from_expr(const_tree expr, typeset &types) case FIELD_DECL: collect_types_from_field_decl(expr, types); break; + case VIEW_CONVERT_EXPR: + collect_types_from_view_convert_expr(expr, types); + break; + case INTEGER_CST: + collect_types_from_integer_cst(expr, types); + break; + case CONSTRUCTOR: + collect_types_from_constructor(expr, types); + break; + case RESULT_DECL: + collect_types_from_result_decl(expr, types); + break; + case PARM_DECL: + collect_types_from_parm_decl(expr, types); + break; + case REAL_CST: + collect_types_from_real_cst(expr, types); + break; + case STRING_CST: + collect_types_from_string_cst(expr, types); break; default: log("tree_code: %s\n", get_tree_code_name(code)); + gcc_unreachable(); break; } } @@ -232,18 +414,59 @@ collect_types_from_stmt_assign(gimple *stmt, typeset &types) collect_types_from_stmt_assign_rhs(stmt, types); } +static void +collect_types_from_stmt_call_lhs(gimple *stmt, typeset &types) +{ + is_gimple_code(stmt, GIMPLE_CALL); + const_tree lhs = gimple_call_lhs(stmt); + if (!lhs) return; + collect_types_from_expr(lhs, types); +} + +static void +collect_types_from_stmt_call_rhs(gimple *stmt, typeset &types) +{ + is_gimple_code(stmt, GIMPLE_CALL); + unsigned num_args = gimple_call_num_args(stmt); + for (unsigned i = 0; i < num_args; i++) + { + const_tree arg_i = gimple_call_arg(stmt, i); + collect_types_from_expr(arg_i, types); + } +} + static void collect_types_from_stmt_call(gimple *stmt, typeset &types) { is_gimple_code(stmt, GIMPLE_CALL); - //TODO: + collect_types_from_stmt_call_lhs(stmt, types); + collect_types_from_stmt_call_rhs(stmt, types); +} + +static void +collect_types_from_stmt_cond_lhs(gimple *stmt, typeset &types) +{ + is_gimple_code(stmt, GIMPLE_COND); + const_tree lhs = gimple_cond_lhs(stmt); + gcc_assert(lhs); + collect_types_from_expr(lhs, types); +} + +static void +collect_types_from_stmt_cond_rhs(gimple *stmt, typeset &types) +{ + is_gimple_code(stmt, GIMPLE_COND); + const_tree rhs = gimple_cond_rhs(stmt); + gcc_assert(rhs); + collect_types_from_expr(rhs, types); } static void collect_types_from_stmt_cond(gimple *stmt, typeset &types) { is_gimple_code(stmt, GIMPLE_COND); - //TODO: + collect_types_from_stmt_cond_lhs(stmt, types); + collect_types_from_stmt_cond_rhs(stmt, types); } static void @@ -251,8 +474,7 @@ collect_types_from_stmt(gimple *stmt, typeset &types) { gcc_assert(stmt); const enum gimple_code code = gimple_code(stmt); - switch (code) - { + switch (code) { case GIMPLE_ASSIGN: collect_types_from_stmt_assign(stmt, types); break; @@ -262,8 +484,16 @@ collect_types_from_stmt(gimple *stmt, typeset &types) case GIMPLE_COND: collect_types_from_stmt_cond(stmt, types); break; + case GIMPLE_LABEL: + case GIMPLE_RETURN: + case GIMPLE_PREDICT: + break; default: - //TODO: + { + const char* name = gimple_code_name[code]; + log("gimple code name %s\n", name); + gcc_unreachable(); + } break; } } diff --git a/gcc/name-types.c b/gcc/name-types.c index 5629cc40a7f..800ba6cb1d2 100644 --- a/gcc/name-types.c +++ b/gcc/name-types.c @@ -145,10 +145,25 @@ type_to_string_get_record_name(const_tree type) static const std::string type_to_string_get_record_or_union_name(const_tree type) { - //TODO: FIXME - //I think it should also work for UNIONS, but I should then rewrite the function - //to avoid the assertion - return type_to_string_get_record_name(type); + const enum tree_code code = TREE_CODE(type); + const bool is_record = RECORD_TYPE == code; + const bool is_union = UNION_TYPE == code; + const bool is_valid_input = is_record || is_union; + gcc_assert(is_valid_input); + tree name = TYPE_NAME(type); + + // The TYPE_NAME will be NULL_TREE for a type + // that is not a built-in type, the result of a typedef + // or a named class type. + const bool no_name = NULL_TREE == name; + if (no_name) return std::string(""); + + const enum tree_code name_code = TREE_CODE(name); + const bool is_name_type_decl = TYPE_DECL == name_code; + name = is_name_type_decl ? DECL_NAME(name) : name; + const char* identifier_ptr = IDENTIFIER_POINTER(name); + gcc_assert(identifier_ptr); + return std::string(identifier_ptr); } /* -- cgit v1.2.3 From ac7e59f92eabb7c200e84e5a6947ac139810d8c0 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Thu, 14 May 2020 10:58:54 +0200 Subject: add collecting types for GIMPLE_RETURN --- gcc/gimple.h | 28 ++++++++++++++++++++++------ gcc/ipa-escape-analysis.c | 13 ++++++++++++- 2 files changed, 34 insertions(+), 7 deletions(-) diff --git a/gcc/gimple.h b/gcc/gimple.h index ca7fec6247e..e5b594a5b01 100644 --- a/gcc/gimple.h +++ b/gcc/gimple.h @@ -6494,6 +6494,23 @@ gimple_transaction_set_subcode (gtransaction *transaction_stmt, transaction_stmt->subcode = subcode; } + +/* Return the return value for GIMPLE_RETURN GS. */ + +static inline tree +gimple_return_retval (const greturn *gs) +{ + return gs->op[0]; +} + +static inline tree +gimple_return_retval(const gimple *gs) +{ + GIMPLE_CHECK(gs, GIMPLE_RETURN); + const greturn *gr = dyn_cast (gs); + return gimple_return_retval (gr); +} + /* Return a pointer to the return value for GIMPLE_RETURN GS. */ static inline tree * @@ -6502,15 +6519,14 @@ gimple_return_retval_ptr (greturn *gs) return &gs->op[0]; } -/* Return the return value for GIMPLE_RETURN GS. */ - -static inline tree -gimple_return_retval (const greturn *gs) +static inline tree * +gimple_return_retval_ptr (gimple *gs) { - return gs->op[0]; + GIMPLE_CHECK(gs, GIMPLE_RETURN); + greturn *gr = dyn_cast (gs); + return gimple_return_retval_ptr (gr); } - /* Set RETVAL to be the return value for GIMPLE_RETURN GS. */ static inline void diff --git a/gcc/ipa-escape-analysis.c b/gcc/ipa-escape-analysis.c index a3d6a2cb191..5b0e878fb2c 100644 --- a/gcc/ipa-escape-analysis.c +++ b/gcc/ipa-escape-analysis.c @@ -469,6 +469,15 @@ collect_types_from_stmt_cond(gimple *stmt, typeset &types) collect_types_from_stmt_cond_rhs(stmt, types); } +static void +collect_types_from_stmt_return(gimple *stmt, typeset &types) +{ + is_gimple_code(stmt, GIMPLE_RETURN); + const_tree retval = gimple_return_retval(stmt); + gcc_assert(retval); + collect_types_from_expr(retval); +} + static void collect_types_from_stmt(gimple *stmt, typeset &types) { @@ -484,8 +493,10 @@ collect_types_from_stmt(gimple *stmt, typeset &types) case GIMPLE_COND: collect_types_from_stmt_cond(stmt, types); break; - case GIMPLE_LABEL: case GIMPLE_RETURN: + collect_types_from_stmt_return(stmt, types); + break; + case GIMPLE_LABEL: case GIMPLE_PREDICT: break; default: -- cgit v1.2.3 From 2b7d6678eed25ade1351c12fe5919dd7120f37b2 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Thu, 14 May 2020 11:04:43 +0200 Subject: Adds fuzz mode --- gcc/ipa-escape-analysis.c | 23 +++++++++++++++++++++-- 1 file changed, 21 insertions(+), 2 deletions(-) diff --git a/gcc/ipa-escape-analysis.c b/gcc/ipa-escape-analysis.c index 5b0e878fb2c..ba0ae26c88e 100644 --- a/gcc/ipa-escape-analysis.c +++ b/gcc/ipa-escape-analysis.c @@ -36,6 +36,8 @@ #include "collect-types.h" #include "name-types.h" +#define FUZZ_MODE 0 + namespace type_playground { enum type_comparison_func_enum { EQ_POINTER = 0, @@ -177,6 +179,9 @@ collect_types_from_constructor_array(const_tree expr, typeset &types) const_tree type = TREE_TYPE(expr); assert_is_type(type, ARRAY_TYPE); //TODO: Collect types from here +#ifdef FUZZ_MODE + gcc_unreachable(); +#endif } static void @@ -191,6 +196,9 @@ collect_types_from_constructor_record_or_union(const_tree expr, typeset &types) const bool is_valid_input = is_record || is_union || is_qual_union; gcc_assert(is_valid_input); //TODO: Collect types from here +#ifdef FUZZ_MODE + gcc_unreachable(); +#endif } static void @@ -222,6 +230,9 @@ collect_types_from_constructor(const_tree expr, typeset &types) break; default: // TODO: I should fuzz this, I got a constructor of an integer type? +#ifdef FUZZ_MODE + gcc_unreachable(); +#endif return; break; } @@ -252,6 +263,9 @@ static void collect_types_from_bit_field_ref(const_tree expr, typeset &types) { // TODO: How to collect types from bit_field_ref? +#ifdef FUZZ_MODE + gcc_unreachable(); +#endif } static void @@ -264,6 +278,9 @@ collect_types_from_view_convert_expr(const_tree expr, typeset &types) // through an integer mode and an intermediate BIT_FIELD_REF. // https://gcc.gnu.org/wiki/MemRef //TODO: How to collect types from VIEW_CONVERT_EXPR? +#ifdef FUZZ_MODE + gcc_unreachable(); +#endif } static void @@ -475,7 +492,7 @@ collect_types_from_stmt_return(gimple *stmt, typeset &types) is_gimple_code(stmt, GIMPLE_RETURN); const_tree retval = gimple_return_retval(stmt); gcc_assert(retval); - collect_types_from_expr(retval); + collect_types_from_expr(retval, types); } static void @@ -498,6 +515,9 @@ collect_types_from_stmt(gimple *stmt, typeset &types) break; case GIMPLE_LABEL: case GIMPLE_PREDICT: +#ifdef FUZZ_MODE + gcc_unreachable(); +#endif break; default: { @@ -733,7 +753,6 @@ iphw_execute() // We still need to collect types from // the function signatures of functions without gimple bodies... - filter_out_types_in_set(types); compare_types_in_set(types); return 0; -- cgit v1.2.3 From a22362346872039fa01a22fc8dc2c26de16d24a0 Mon Sep 17 00:00:00 2001 From: Erick Ochoa Date: Thu, 14 May 2020 14:39:09 +0200 Subject: Adds globals --- gcc/collect-types.c | 258 +++++++++++++++++++++++++++++++++++++++------- gcc/collect-types.h | 14 ++- gcc/ipa-escape-analysis.c | 148 +++++++++++++++----------- 3 files changed, 322 insertions(+), 98 deletions(-) diff --git a/gcc/collect-types.c b/gcc/collect-types.c index fd25ff81be3..0ce6cccb025 100644 --- a/gcc/collect-types.c +++ b/gcc/collect-types.c @@ -30,46 +30,193 @@ #include "compare-types.h" #include "types-inlines.h" +#include "name-types.h" #include #include "collect-types.h" +static bool filter_boring_types(const_tree type, ptrset_t &); + static bool -filter_out_simple_types(const_tree type) +filter_boring_types_wrapper(const_tree type, ptrset_t &types) { gcc_assert(type); + const_tree inner_type = TREE_TYPE(type); + gcc_assert(inner_type); + return filter_boring_types(inner_type, types); +} + +static bool +filter_boring_types_array(const_tree type, ptrset_t &types) +{ + assert_is_type(type, ARRAY_TYPE); + return filter_boring_types_wrapper(type, types); +} + +static bool +filter_boring_types_reference(const_tree type, ptrset_t &types) +{ + assert_is_type(type, REFERENCE_TYPE); + return filter_boring_types_wrapper(type, types); +} + +static bool +filter_boring_types_pointer(const_tree type, ptrset_t &types) +{ + assert_is_type(type, POINTER_TYPE); + return filter_boring_types_wrapper(type, types); +} + +static bool +filter_boring_types_record(const_tree type, ptrset_t &types) +{ + assert_is_type(type, RECORD_TYPE); + return false; +} + +static bool +filter_boring_types_unions(const_tree type, ptrset_t &types) +{ + const enum tree_code code = TREE_CODE(type); + const bool is_union = UNION_TYPE == code; + const bool is_qual_union = QUAL_UNION_TYPE == code; + const bool is_valid_input = is_union || is_qual_union; + gcc_assert(is_valid_input); + + for (tree field = TYPE_FIELDS(type) ; field ; field = DECL_CHAIN(field)) + { + const_tree field_type = TREE_TYPE(field); + gcc_assert(field_type); + const bool is_boring = filter_boring_types(field_type, types); + if (!is_boring) return is_boring; + } + + return true; +} + +static bool +filter_boring_types_union(const_tree type, ptrset_t &types) +{ + assert_is_type(type, UNION_TYPE); + return filter_boring_types_unions(type, types); +} + +static bool +filter_boring_types_qual_union(const_tree type, ptrset_t &types) +{ + assert_is_type(type, QUAL_UNION_TYPE); + return filter_boring_types_unions(type, types); +} + +static bool +filter_boring_types_function_or_method(const_tree type, ptrset_t &types) +{ const enum tree_code code = TREE_CODE(type); + const bool is_function = FUNCTION_TYPE == code; + const bool is_method = METHOD_TYPE == code; + const bool is_valid_input = is_function || is_method; + gcc_assert(is_valid_input); + + const_tree ret_type = TREE_TYPE(type); + gcc_assert(ret_type); + const bool retval_is_boring = filter_boring_types(ret_type, types); + if (!retval_is_boring) return retval_is_boring; + + tree arg_node = TYPE_ARG_TYPES(type); + while (NULL_TREE != arg_node) + { + tree arg_node_type = TREE_VALUE(arg_node); + gcc_assert(arg_node_type); + const bool arg_is_boring = filter_boring_types(arg_node_type, types); + arg_node = TREE_CHAIN(arg_node); + if (!arg_is_boring) return arg_is_boring; + } + + return true; +} +static bool +filter_boring_types_function(const_tree type, ptrset_t &types) +{ + assert_is_type(type, FUNCTION_TYPE); + return filter_boring_types_function_or_method(type, types); +} + +static bool +filter_boring_types_method(const_tree type, ptrset_t &types) +{ + assert_is_type(type, METHOD_TYPE); + return filter_boring_types_function_or_method(type, types); +} + +static bool +filter_boring_types(const_tree type, ptrset_t &types) +{ + // boring types are those that do not point to + // a struct + gcc_assert(type); + + // Optimization to speed up the filter. + // Memoization + const bool seen_before = types.in_universe(type); + if (seen_before) + { + const bool in_points_to_record = types.in_points_to_record(type); + const bool in_complement = types.in_complement(type); + const bool _xor = in_points_to_record != in_complement; + gcc_assert(_xor); + return in_complement; + } + + + bool is_boring = true; + enum tree_code code = TREE_CODE(type); switch (code) { - case VOID_TYPE: - case INTEGER_TYPE: - case REAL_TYPE: - case FIXED_POINT_TYPE: - case COMPLEX_TYPE: - case ENUMERAL_TYPE: - case BOOLEAN_TYPE: - case OFFSET_TYPE: - return false; + case ARRAY_TYPE: + is_boring = filter_boring_types_array(type, types); + break; + case RECORD_TYPE: + is_boring = filter_boring_types_record(type, types); + break; + case UNION_TYPE: + is_boring = filter_boring_types_union(type, types); + break; + case QUAL_UNION_TYPE: + is_boring = filter_boring_types_qual_union(type, types); + break; + case REFERENCE_TYPE: + is_boring = filter_boring_types_reference(type, types); + break; + case POINTER_TYPE: + is_boring = filter_boring_types_pointer(type, types); + break; + case FUNCTION_TYPE: + is_boring = filter_boring_types_function(type, types); + break; + case METHOD_TYPE: + is_boring = filter_boring_types_method(type, types); break; default: - return false; + // I will probably need to fuzz. break; } - gcc_unreachable(); - return false; + // This should be one the two only times we call insert! + types.insert(type, !is_boring); + + return is_boring; } static const unsigned filter_buffer_size = 1; -typedef bool (*filter_t)(const_tree); +typedef bool (*filter_t)(const_tree, ptrset_t&); const extern filter_t filter[filter_buffer_size] = { - filter_out_simple_types, + filter_boring_types, }; static void -collect_types_from_record_or_union_type(const_tree type, typeset &types) +collect_types_from_record_or_union_type(const_tree type, ptrset_t &types) { gcc_assert(type); const enum tree_code code = TREE_CODE(type); @@ -81,26 +228,27 @@ collect_types_from_record_or_union_type(const_tree type, typeset &types) for (tree field = TYPE_FIELDS(type) ; field ; field = DECL_CHAIN(field)) { const_tree field_type = TREE_TYPE(field); + gcc_assert(field_type); collect_types(field_type, types); } } static void -collect_types_from_record_type(const_tree type, typeset &types) +collect_types_from_record_type(const_tree type, ptrset_t &types) { assert_is_type(type, RECORD_TYPE); collect_types_from_record_or_union_type(type, types); } static void -collect_types_from_union_type(const_tree type, typeset &types) +collect_types_from_union_type(const_tree type, ptrset_t &types) { assert_is_type(type, UNION_TYPE); collect_types_from_record_or_union_type(type, types); } static void -collect_types_from_wrapper_type(const_tree type, typeset &types) +collect_types_from_wrapper_type(const_tree type, ptrset_t &types) { gcc_assert(type); const_tree inner_type = TREE_TYPE(type); @@ -109,28 +257,28 @@ collect_types_from_wrapper_type(const_tree type, typeset &types) } static void -collect_types_from_pointer_type(const_tree type, typeset &types) +collect_types_from_pointer_type(const_tree type, ptrset_t &types) { assert_is_type(type, POINTER_TYPE); collect_types_from_wrapper_type(type, types); } static void -collect_types_from_reference_type(const_tree type, typeset &types) +collect_types_from_reference_type(const_tree type, ptrset_t &types) { assert_is_type(type, REFERENCE_TYPE); collect_types_from_wrapper_type(type, types); } static void -collect_types_from_array_type(const_tree type, typeset &types) +collect_types_from_array_type(const_tree type, ptrset_t &types) { assert_is_type(type, ARRAY_TYPE); collect_types_from_wrapper_type(type, types); } static void -collect_types_from_function_or_method_type(const_tree type, typeset &types) +collect_types_from_function_or_method_type(const_tree type, ptrset_t &types) { gcc_assert(type); const enum tree_code code = TREE_CODE(type); @@ -147,31 +295,71 @@ collect_types_from_function_or_method_type(const_tree type, typeset &types) while (NULL_TREE != arg_node) { tree arg_node_type = TREE_VALUE(arg_node); + gcc_assert(arg_node_type); collect_types(arg_node_type, types); arg_node = TREE_CHAIN(arg_node); } } static void -collect_types_from_function_type(const_tree type, typeset &types) +collect_types_from_function_type(const_tree type, ptrset_t &types) { assert_is_type(type, FUNCTION_TYPE); collect_types_from_function_or_method_type(type, types); } static void -collect_types_from_method_type(const_tree type, typeset &types) +collect_types_from_method_type(const_tree type, ptrset_t &types) { assert_is_type(type, METHOD_TYPE); collect_types_from_function_or_method_type(type, types); } void -collect_types(const_tree type, typeset &types) +points_to_record_sets_s::insert(const_tree type, bool in_points_to_record) +{ + gcc_assert(type); + this->universe.insert(type); + in_points_to_record ? this->points_to_record.insert(type) : this->complement.insert(type); + // let's just double check... + const bool in_points_to_set = this->in_points_to_record(type); + const bool in_complement = this->in_complement(type); + const bool _xor = in_points_to_set != in_complement; + gcc_assert(_xor); +} + +bool +points_to_record_sets_s::in_universe(const_tree type) const +{ + gcc_assert(type); + const bool seen_before = this->universe.find(type) != this->universe.end(); + return seen_before; +} + +bool +points_to_record_sets_s::in_points_to_record(const_tree type) const +{ + gcc_assert(type); + const bool seen_before = this->points_to_record.find(type) != this->points_to_record.end(); + return seen_before; +} + +bool +points_to_record_sets_s::in_complement(const_tree type) const +{ + gcc_assert(type); + const bool seen_before = this->complement.find(type) != this->complement.end(); + return seen_before; +} + +void +collect_types(const_tree type, ptrset_t &types) { if (!type) return; - const bool in_set = types.find(type) != types.end(); + // This should be the only case we call to find if + // we have seen the type before! + const bool in_set = types.in_universe(type); // memoized. if (in_set) return; @@ -181,10 +369,10 @@ collect_types(const_tree type, typeset &types) // then we just return immediately. // maybe even add it to a set of blacklisted types so that we // memoize and do things faster... + bool is_boring = false; for (unsigned i = 0; i < filter_buffer_size; i++) { - const bool filter_out = filter[i](type); - if (filter_out) return; + is_boring |= filter[i](type, types); } const enum tree_code code = TREE_CODE(type); @@ -198,15 +386,8 @@ collect_types(const_tree type, typeset &types) case ENUMERAL_TYPE: case BOOLEAN_TYPE: case OFFSET_TYPE: - types.insert(type); - return; - break; - default: + // simple cases and we want to allow them break; - } - - switch (code) - { case RECORD_TYPE: collect_types_from_record_type(type, types); break; @@ -236,5 +417,6 @@ collect_types(const_tree type, typeset &types) break; } - types.insert(type); + // This should be one the two only times we call insert! + types.insert(type, !is_boring); } diff --git a/gcc/collect-types.h b/gcc/collect-types.h index 315c19abfd7..883c08d36dc 100644 --- a/gcc/collect-types.h +++ b/gcc/collect-types.h @@ -4,4 +4,16 @@ #include typedef std::set typeset; -extern void collect_types(const_tree type, typeset &types); +struct points_to_record_sets_s { + typeset universe; + typeset points_to_record; + typeset complement; + bool in_universe(const_tree) const; + bool in_points_to_record(const_tree) const; + bool in_complement(const_tree) const; + void insert(const_tree, bool); +}; + +typedef struct points_to_record_sets_s ptrset_t; + +extern void collect_types(const_tree type, ptrset_t &ptrset_t); diff --git a/gcc/ipa-escape-analysis.c b/gcc/ipa-escape-analysis.c index ba0ae26c88e..04023a406a5 100644 --- a/gcc/ipa-escape-analysis.c +++ b/gcc/ipa-escape-analysis.c @@ -36,7 +36,7 @@ #include "collect-types.h" #include "name-types.h" -#define FUZZ_MODE 0 +//#define FUZZ_MODE 1 namespace type_playground { enum type_comparison_func_enum { @@ -70,7 +70,7 @@ static type_comparison_func_t comparisons[type_comparisons] = { eq_type_compare }; } -static void collect_types_from_expr(const_tree expr, typeset &types); +static void collect_types_from_expr(const_tree expr, ptrset_t &types); inline void is_gimple_code(gimple *stmt, const enum gimple_code ex_code) @@ -92,7 +92,7 @@ is_gimple_rhs_class(gimple *stmt, const enum gimple_rhs_class ex_class) } static void -collect_types_from_op(const_tree expr, typeset &types, unsigned n) +collect_types_from_op(const_tree expr, ptrset_t &types, unsigned n) { gcc_assert(expr); const_tree op_n = TREE_OPERAND(expr, n); @@ -101,14 +101,14 @@ collect_types_from_op(const_tree expr, typeset &types, unsigned n) } static void -collect_types_from_op0(const_tree expr, typeset &types, const enum tree_code ex_code) +collect_types_from_op0(const_tree expr, ptrset_t &types, const enum tree_code ex_code) { assert_is_type(expr, ex_code); collect_types_from_op(expr, types, 0); } static void -collect_types_from_op1(const_tree expr, typeset &types, const enum tree_code ex_code) +collect_types_from_op1(const_tree expr, ptrset_t &types, const enum tree_code ex_code) { assert_is_type(expr, ex_code); collect_types_from_op(expr, types, 0); @@ -116,31 +116,31 @@ collect_types_from_op1(const_tree expr, typeset &types, const enum tree_code ex_ } static void -collect_types_from_addr_expr(const_tree expr, typeset &types) +collect_types_from_addr_expr(const_tree expr, ptrset_t &types) { collect_types_from_op0(expr, types, ADDR_EXPR); } static void -collect_types_from_component_ref(const_tree expr, typeset &types) +collect_types_from_component_ref(const_tree expr, ptrset_t &types) { collect_types_from_op1(expr, types, COMPONENT_REF); } static void -collect_types_from_mem_ref(const_tree expr, typeset &types) +collect_types_from_mem_ref(const_tree expr, ptrset_t &types) { collect_types_from_op1(expr, types, MEM_REF); } static void -collect_types_from_array_ref(const_tree expr, typeset &types) +collect_types_from_array_ref(const_tree expr, ptrset_t &types) { collect_types_from_op1(expr, types, ARRAY_REF); } static void -collect_types_from_leaf_expr(const_tree expr, typeset &types, const enum tree_code ex_code) +collect_types_from_leaf_expr(const_tree expr, ptrset_t &types, const enum tree_code ex_code) { assert_is_type(expr, ex_code); const_tree type = TREE_TYPE(expr); @@ -149,31 +149,31 @@ collect_types_from_leaf_expr(const_tree expr, typeset &types, const enum tree_co } static void -collect_types_from_ssa_name(const_tree expr, typeset &types) +collect_types_from_ssa_name(const_tree expr, ptrset_t &types) { collect_types_from_leaf_expr(expr, types, SSA_NAME); } static void -collect_types_from_var_decl(const_tree expr, typeset &types) +collect_types_from_var_decl(const_tree expr, ptrset_t &types) { collect_types_from_leaf_expr(expr, types, VAR_DECL); } static void -collect_types_from_field_decl(const_tree expr, typeset &types) +collect_types_from_field_decl(const_tree expr, ptrset_t &types) { collect_types_from_leaf_expr(expr, types, FIELD_DECL); } static void -collect_types_from_integer_cst(const_tree expr, typeset &types) +collect_types_from_integer_cst(const_tree expr, ptrset_t &types) { collect_types_from_leaf_expr(expr, types, INTEGER_CST); } static void -collect_types_from_constructor_array(const_tree expr, typeset &types) +collect_types_from_constructor_array(const_tree expr, ptrset_t &types) { assert_is_type(expr, CONSTRUCTOR); const_tree type = TREE_TYPE(expr); @@ -185,7 +185,7 @@ collect_types_from_constructor_array(const_tree expr, typeset &types) } static void -collect_types_from_constructor_record_or_union(const_tree expr, typeset &types) +collect_types_from_constructor_record_or_union(const_tree expr, ptrset_t &types) { assert_is_type(expr, CONSTRUCTOR); const_tree type = TREE_TYPE(expr); @@ -202,7 +202,7 @@ collect_types_from_constructor_record_or_union(const_tree expr, typeset &types) } static void -collect_types_from_constructor(const_tree expr, typeset &types) +collect_types_from_constructor(const_tree expr, ptrset_t &types) { // https://gcc.gnu.org/onlinedocs/gccint/Unary-and-Binary-Expressions.html#Unary-and-Binary-Expressions // These nodes represent the brace-enclosed initializers for a structure or an array. @@ -242,25 +242,25 @@ collect_types_from_constructor(const_tree expr, typeset &types) } static void -collect_types_from_parm_decl(const_tree expr, typeset &types) +collect_types_from_parm_decl(const_tree expr, ptrset_t &types) { collect_types_from_leaf_expr(expr, types, PARM_DECL); } static void -collect_types_from_real_cst(const_tree expr, typeset &types) +collect_types_from_real_cst(const_tree expr, ptrset_t &types) { collect_types_from_leaf_expr(expr, types, REAL_CST); } static void -collect_types_from_string_cst(const_tree expr, typeset &types) +collect_types_from_string_cst(const_tree expr, ptrset_t &types) { collect_types_from_leaf_expr(expr, types, STRING_CST); } static void -collect_types_from_bit_field_ref(const_tree expr, typeset &types) +collect_types_from_bit_field_ref(const_tree expr, ptrset_t &types) { // TODO: How to collect types from bit_field_ref? #ifdef FUZZ_MODE @@ -269,7 +269,7 @@ collect_types_from_bit_field_ref(const_tree expr, typeset &types) } static void -collect_types_from_view_convert_expr(const_tree expr, typeset &types) +collect_types_from_view_convert_expr(const_tree expr, ptrset_t &types) { // VIEW_CONVERT_EXPR is used to interpret the bit representation // of a register as a register of a different type. @@ -284,13 +284,13 @@ collect_types_from_view_convert_expr(const_tree expr, typeset &types) } static void -collect_types_from_result_decl(const_tree expr, typeset &types) +collect_types_from_result_decl(const_tree expr, ptrset_t &types) { collect_types_from_leaf_expr(expr, types, RESULT_DECL); } static void -collect_types_from_expr(const_tree expr, typeset &types) +collect_types_from_expr(const_tree expr, ptrset_t &types) { // These are the codes I saw using csmith to fuzz. gcc_assert(expr); @@ -353,7 +353,7 @@ collect_types_from_expr(const_tree expr, typeset &types) } static void -collect_types_from_stmt_assign_lhs(gimple *stmt, typeset &types) +collect_types_from_stmt_assign_lhs(gimple *stmt, ptrset_t &types) { is_gimple_code(stmt, GIMPLE_ASSIGN); const_tree lhs = gimple_assign_lhs(stmt); @@ -362,7 +362,7 @@ collect_types_from_stmt_assign_lhs(gimple *stmt, typeset &types) } static void -collect_types_from_stmt_assign_rhs3(gimple *stmt, typeset &types) +collect_types_from_stmt_assign_rhs3(gimple *stmt, ptrset_t &types) { is_gimple_rhs_class(stmt, GIMPLE_TERNARY_RHS); const_tree rhs = gimple_assign_rhs3(stmt); @@ -371,7 +371,7 @@ collect_types_from_stmt_assign_rhs3(gimple *stmt, typeset &types) } static void -collect_types_from_stmt_assign_rhs2(gimple *stmt, typeset &types) +collect_types_from_stmt_assign_rhs2(gimple *stmt, ptrset_t &types) { is_gimple_code(stmt, GIMPLE_ASSIGN); const enum gimple_rhs_class gclass = gimple_assign_rhs_class(stmt); @@ -385,7 +385,7 @@ collect_types_from_stmt_assign_rhs2(gimple *stmt, typeset &types) } static void -collect_types_from_stmt_assign_rhs1(gimple *stmt, typeset &types) +collect_types_from_stmt_assign_rhs1(gimple *stmt, ptrset_t &types) { is_gimple_code(stmt, GIMPLE_ASSIGN); const enum gimple_rhs_class gclass = gimple_assign_rhs_class(stmt); @@ -401,7 +401,7 @@ collect_types_from_stmt_assign_rhs1(gimple *stmt, typeset &types) } static void -collect_types_from_stmt_assign_rhs(gimple *stmt, typeset &types) +collect_types_from_stmt_assign_rhs(gimple *stmt, ptrset_t &types) { is_gimple_code(stmt, GIMPLE_ASSIGN); const enum gimple_rhs_class gclass = gimple_assign_rhs_class(stmt); @@ -424,7 +424,7 @@ collect_types_from_stmt_assign_rhs(gimple *stmt, typeset &types) } static void -collect_types_from_stmt_assign(gimple *stmt, typeset &types) +collect_types_from_stmt_assign(gimple *stmt, ptrset_t &types) { is_gimple_code(stmt, GIMPLE_ASSIGN); collect_types_from_stmt_assign_lhs(stmt, types); @@ -432,7 +432,7 @@ collect_types_from_stmt_assign(gimple *stmt, typeset &types) } static void -collect_types_from_stmt_call_lhs(gimple *stmt, typeset &types) +collect_types_from_stmt_call_lhs(gimple *stmt, ptrset_t &types) { is_gimple_code(stmt, GIMPLE_CALL); const_tree lhs = gimple_call_lhs(stmt); @@ -441,7 +441,7 @@ collect_types_from_stmt_call_lhs(gimple *stmt, typeset &types) } static void -collect_types_from_stmt_call_rhs(gimple *stmt, typeset &types) +collect_types_from_stmt_call_rhs(gimple *stmt, ptrset_t &types) { is_gimple_code(stmt, GIMPLE_CALL); unsigned num_args = gimple_call_num_args(stmt); @@ -453,7 +453,7 @@ collect_types_from_stmt_call_rhs(gimple *stmt, typeset &types) } static void -collect_types_from_stmt_call(gimple *stmt, typeset &types) +collect_types_from_stmt_call(gimple *stmt, ptrset_t &types) { is_gimple_code(stmt, GIMPLE_CALL); collect_types_from_stmt_call_lhs(stmt, types); @@ -461,7 +461,7 @@ collect_types_from_stmt_call(gimple *stmt, typeset &types) } static void -collect_types_from_stmt_cond_lhs(gimple *stmt, typeset &types) +collect_types_from_stmt_cond_lhs(gimple *stmt, ptrset_t &types) { is_gimple_code(stmt, GIMPLE_COND); const_tree lhs = gimple_cond_lhs(stmt); @@ -470,7 +470,7 @@ collect_types_from_stmt_cond_lhs(gimple *stmt, typeset &types) } static void -collect_types_from_stmt_cond_rhs(gimple *stmt, typeset &types) +collect_types_from_stmt_cond_rhs(gimple *stmt, ptrset_t &types) { is_gimple_code(stmt, GIMPLE_COND); const_tree rhs = gimple_cond_rhs(stmt); @@ -479,7 +479,7 @@ collect_types_from_stmt_cond_rhs(gimple *stmt, typeset &types) } static void -collect_types_from_stmt_cond(gimple *stmt, typeset &types) +collect_types_from_stmt_cond(gimple *stmt, ptrset_t &types) { is_gimple_code(stmt, GIMPLE_COND); collect_types_from_stmt_cond_lhs(stmt, types); @@ -487,7 +487,7 @@ collect_types_from_stmt_cond(gimple *stmt, typeset &types) } static void -collect_types_from_stmt_return(gimple *stmt, typeset &types) +collect_types_from_stmt_return(gimple *stmt, ptrset_t &types) { is_gimple_code(stmt, GIMPLE_RETURN); const_tree retval = gimple_return_retval(stmt); @@ -496,7 +496,7 @@ collect_types_from_stmt_return(gimple *stmt, typeset &types) } static void -collect_types_from_stmt(gimple *stmt, typeset &types) +collect_types_from_stmt(gimple *stmt, ptrset_t &types) { gcc_assert(stmt); const enum gimple_code code = gimple_code(stmt); @@ -530,7 +530,7 @@ collect_types_from_stmt(gimple *stmt, typeset &types) } static void -collect_types_from_cnode_decl(cgraph_node *cnode, typeset &types) +collect_types_from_cnode_decl(cgraph_node *cnode, ptrset_t &types) { gcc_assert(cnode); const_tree decl = cnode->decl; @@ -546,7 +546,7 @@ collect_types_from_cnode_decl(cgraph_node *cnode, typeset &types) } static void -collect_types_from_cnode_locals(cgraph_node *cnode, typeset &types) +collect_types_from_cnode_locals(cgraph_node *cnode, ptrset_t &types) { gcc_assert(cnode); const_tree decl = cnode->decl; @@ -564,7 +564,7 @@ collect_types_from_cnode_locals(cgraph_node *cnode, typeset &types) } static void -collect_types_from_cnode_ssa_names(cgraph_node *cnode, typeset &types) +collect_types_from_cnode_ssa_names(cgraph_node *cnode, ptrset_t &types) { gcc_assert(cnode); const_tree decl = cnode->decl; @@ -584,7 +584,7 @@ collect_types_from_cnode_ssa_names(cgraph_node *cnode, typeset &types) } static void -collect_types_from_bb(basic_block bb, typeset &types) +collect_types_from_bb(basic_block bb, ptrset_t &types) { gcc_assert(bb); for (auto gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) @@ -596,7 +596,7 @@ collect_types_from_bb(basic_block bb, typeset &types) } static void -collect_types_from_cnode_bb(cgraph_node *cnode, typeset &types) +collect_types_from_cnode_bb(cgraph_node *cnode, ptrset_t &types) { gcc_assert(cnode); cnode->get_untransformed_body(); @@ -615,7 +615,30 @@ collect_types_from_cnode_bb(cgraph_node *cnode, typeset &types) } static void -collect_types_from_functions_with_gimple_body(cgraph_node *cnode, typeset &types) +collect_types_from_global(varpool_node *vnode, ptrset_t &types) +{ + gcc_assert(vnode); + struct ipa_ref *ref = NULL; + for (unsigned i = 0; vnode->iterate_referring(i, ref); i++) + { + tree decl = vnode->decl; + gcc_assert(decl); + collect_types_from_var_decl(decl, types); + } +} + +static void +collect_types_from_globals(ptrset_t &types) +{ + varpool_node *vnode = NULL; + FOR_EACH_VARIABLE (vnode) + { + collect_types_from_global(vnode, types); + } +} + +static void +collect_types_from_functions_with_gimple_body(cgraph_node *cnode, ptrset_t &types) { gcc_assert(cnode); collect_types_from_cnode_decl(cnode, types); @@ -625,9 +648,9 @@ collect_types_from_functions_with_gimple_body(cgraph_node *cnode, typeset &types } static void -print_types_in_set(typeset &types) +print_types_in_set(ptrset_t &types) { - for (auto it = types.cbegin(); it != types.cend(); ++it) + for (auto it = types.points_to_record.cbegin(); it != types.points_to_record.cend(); ++it) { const_tree type = *it; std::string name = type_to_string(type); @@ -685,11 +708,11 @@ filter_comparisons_functions(type_playground::type_comparison_func_t func) static void -compare_types_in_set(typeset &types) +compare_types_in_set(ptrset_t &types) { - for (auto i = types.cbegin(); i != types.cend(); ++i) + for (auto i = types.points_to_record.cbegin(); i != types.points_to_record.cend(); ++i) { - for (auto j = types.cbegin(); j != types.cend(); ++j) + for (auto j = types.points_to_record.cbegin(); j != types.points_to_record.cend(); ++j) { const_tree a = *i; const_tree b = *j; @@ -709,7 +732,7 @@ compare_types_in_set(typeset &types) } static void -filter_out_types_in_set(typeset &types) +filter_out_types_in_set(ptrset_t &types) { // compare everything if (!flag_tp_types_compared) return; @@ -721,7 +744,7 @@ filter_out_types_in_set(typeset &types) strcpy(whitelist, flag_tp_types_compared); bool name_allowed = false; - for (auto it = types.cbegin(); it != types.cend(); name_allowed ? ++it : it = types.erase(it)) + for (auto it = types.points_to_record.cbegin(); it != types.points_to_record.cend(); name_allowed ? ++it : it = types.points_to_record.erase(it)) { const_tree type = *it; std::string observed_name = get_type_identifier(type); @@ -737,22 +760,29 @@ filter_out_types_in_set(typeset &types) } -static unsigned int -iphw_execute() +static void +collect_types(ptrset_t &types) { - //test_type_equality::run_tests(); - //test_naming_types::run_tests(); - cgraph_node *node = NULL; - typeset types; + collect_types_from_globals(types); + cgraph_node *node = NULL; FOR_EACH_FUNCTION_WITH_GIMPLE_BODY(node) { node->get_untransformed_body(); collect_types_from_functions_with_gimple_body(node, types); + // We still need to collect types from + // the function signatures of functions without gimple bodies... } +} + +static unsigned int +iphw_execute() +{ + //test_type_equality::run_tests(); + //test_naming_types::run_tests(); + ptrset_t types; - // We still need to collect types from - // the function signatures of functions without gimple bodies... + collect_types(types); filter_out_types_in_set(types); compare_types_in_set(types); return 0; -- cgit v1.2.3