>From 289487b58709575a90fca0cbebc6ae968aba73ab Mon Sep 17 00:00:00 2001
From: Thomas de Bock <tdeb...@drwholdings.com>
Date: Thu, 28 Aug 2025 16:10:08 +0100
Subject: [PATCH] Vectorizing default struct and std::array equality
---
Notes:
Added 2 SSA passes enabling the vectorization of default equality on
structs and std::array's of structs (C arrays also implemented). Did this in a
similar way to clang: https://reviews.llvm.org/D33987, where basic blocks
forming chains of consecutive comparisons are merged and replaced with calls to
__builtin_memcmp_eq where possible. It is also able to parse the result of a
previous execution of itself recursively i.e. if we have a struct A as a field
in a struct B, with both default equality operators defined, it will first
execute on A::operator==, which then gets inlined into B::operator==, it then
parses the outputted memcmp that is now in the B::operator==, and merges it
with the surrounding comparisons (when possible).
Added an additional pass that unrolls the std::array std::__equal::equal
functions, checks if the memory compared in the loop is consecutive, then
replaces the loop with a call to __builtin_memcmp_eq when possible. Have also
added the logic to deal with the vectorization of equality on C arrays of
structs, but this is still messy (so not included here). This has to run after
the struct equality merging pass, so it can easily decide whether unrolling and
replacing with memcmp would be valid, based on the merged comparisons of the
underlying struct.
In my original implementation, it simply applies the struct comparison
merging pass to all defaulted equality operators on structs, but I imagine that
to get this merged, some attribute indicating the optimization is allowed there
should be added.
Any comments would be greatly appreciated!
gcc/Makefile.in | 3 +
gcc/passes.def | 2 +
gcc/tree-pass.h | 2 +
gcc/tree-ssa-arr-eqmerge.cc | 596 ++++++++++++++++++++++++++++++++
gcc/tree-ssa-eqmerge.cc | 332 ++++++++++++++++++
gcc/tree-ssa-eqmerge.h | 85 +++++
gcc/tree-ssa-struct-eqmerge.cc | 598 +++++++++++++++++++++++++++++++++
7 files changed, 1618 insertions(+)
create mode 100644 gcc/tree-ssa-arr-eqmerge.cc
create mode 100644 gcc/tree-ssa-eqmerge.cc
create mode 100644 gcc/tree-ssa-eqmerge.h
create mode 100644 gcc/tree-ssa-struct-eqmerge.cc
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index d2744db843d..153e327961b 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1804,6 +1804,9 @@ OBJS = \
tree-ssa-uninit.o \
tree-ssa.o \
tree-ssanames.o \
+ tree-ssa-eqmerge.o \
+ tree-ssa-arr-eqmerge.o \
+ tree-ssa-struct-eqmerge.o \
tree-stdarg.o \
tree-streamer.o \
tree-streamer-in.o \
diff --git a/gcc/passes.def b/gcc/passes.def
index 68ce53baa0f..608ceb215c5 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -105,6 +105,8 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_profile);
NEXT_PASS (pass_local_pure_const);
NEXT_PASS (pass_modref);
+ NEXT_PASS (pass_struct_eq_merge);
+ NEXT_PASS (pass_arr_eq_merge);
/* Split functions creates parts that are not run through
early optimizations again. It is thus good idea to do this
late. */
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 1c68a69350d..a7622fa1c7b 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -509,6 +509,8 @@ extern gimple_opt_pass *make_pass_warn_nonnull_compare
(gcc::context *ctxt);
extern gimple_opt_pass *make_pass_sprintf_length (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_walloca (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_modref (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_tree_struct_eq_merge (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_tree_arr_eq_merge (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_coroutine_lower_builtins (gcc::context
*ctxt);
extern gimple_opt_pass *make_pass_coroutine_early_expand_ifns (gcc::context
*ctxt);
extern gimple_opt_pass *make_pass_adjust_alignment (gcc::context *ctxt);
diff --git a/gcc/tree-ssa-arr-eqmerge.cc b/gcc/tree-ssa-arr-eqmerge.cc
new file mode 100644
index 00000000000..b6557df2b2c
--- /dev/null
+++ b/gcc/tree-ssa-arr-eqmerge.cc
@@ -0,0 +1,596 @@
+#include "tree-ssa-eqmerge.h"
+
+const pass_data pass_data_tree_arr_eq_merge = {
+ GIMPLE_PASS,
+ "arreqmerge",
+ OPTGROUP_NONE,
+ TV_NONE,
+ (PROP_cfg | PROP_ssa),
+ 0,
+ 0,
+ 0,
+ 0,
+};
+
+namespace {
+
+class pass_tree_arr_eq_merge : public gimple_opt_pass {
+ public:
+ pass_tree_arr_eq_merge(gcc::context* ctxt)
+ : gimple_opt_pass(pass_data_tree_arr_eq_merge, ctxt) {}
+
+ opt_pass* clone() final override {
+ return new pass_tree_arr_eq_merge(m_ctxt);
+ }
+ void set_pass_param(unsigned n, bool param) final override {
+ gcc_assert(n == 0);
+ use_dr_analysis_p = param;
+ }
+
+ bool gate(function*) final override { return optimize >= 2; }
+ unsigned int execute(function*) final override;
+
+ private:
+ bool use_dr_analysis_p;
+};
+
+/* Structure storing bound checking block in std::array equality */
+struct bound_check_blk {
+ basic_block bb;
+ tree base_end_ssa;
+ tree cmp_initial_base_ssa1;
+ tree cmp_initial_base_ssa2;
+ tree cmp_base_im_ssa1; /* intermediate ssa, later assigned to base */
+ tree cmp_base_im_ssa2; /* intermediate ssa, later assigned to base */
+ tree cmp_base_ssa1;
+ tree cmp_base_ssa2;
+ edge end_edge;
+ edge no_end_edge;
+};
+/* Structure storing comparison block in std::array equality loop */
+struct compare_blk {
+ basic_block bb;
+ tree cmp_base_ssa1;
+ tree cmp_base_ssa2;
+ /* Only one cmp, since if not, previous pass did not fully merge so we cannot
+ * merge loop cmps */
+ icmp cmp;
+ edge eq_edge;
+ edge neq_edge;
+};
+/* Structure storing ptr advancement block in std::array equality loop */
+struct advance_blk {
+ basic_block bb;
+ tree cmp_base_ssa1;
+ tree cmp_base_ssa2;
+ tree cmp_base_im_ssa1; /* intermediate ssa, later assigned to base */
+ tree cmp_base_im_ssa2; /* intermediate ssa, later assigned to base */
+ widest_int advance_len;
+};
+
+/* Structure storing std::array equality loop */
+struct icmploop {
+ /* Empty entry block with fallthrough edge to bb_boundcheck */
+ basic_block bb_initial;
+
+ /* Uses the bases advanced by bb_advance to read current element */
+ compare_blk bb_compare;
+
+ /* Advances the bases used in bb_compare */
+ advance_blk bb_advance;
+
+ /* Checks whether bound of array has been reached */
+ bound_check_blk bb_bounds;
+ /* PHI node gives whether input edge meant all comparisons succeeded */
+ basic_block bb_end;
+
+ basic_block outgoing;
+};
+
+bool is_stdarr_eq_fn(tree fundecl) {
+ if (TREE_CODE(fundecl) != FUNCTION_DECL) return false;
+ tree fn_name = DECL_NAME(fundecl);
+ if (!fn_name || strcmp(IDENTIFIER_POINTER(fn_name), "equal") != 0)
+ return false;
+ tree ctxt = DECL_CONTEXT(fundecl);
+ if (!ctxt) return false;
+ if (TREE_CODE(ctxt) != NAMESPACE_DECL) {
+ tree ctxt_type = TYPE_NAME(ctxt);
+ if (!ctxt_type) return false;
+ tree ctxt_name = DECL_NAME(ctxt_type);
+ if (ctxt_name == NULL_TREE ||
+ strcmp(IDENTIFIER_POINTER(ctxt_name), "__equal") != 0)
+ return false;
+ return true;
+ }
+ if (strcmp(IDENTIFIER_POINTER(DECL_NAME(ctxt)), "std") != 0) return false;
+ return true;
+}
+
+/* Compares redundant fields in input loop blocks to verify that structure is
+ * valid std::array comparison loop */
+static bool is_valid_cmp_loop(const icmploop& loop) {
+ if (loop.bb_compare.eq_edge->dest != loop.bb_advance.bb) return false;
+ if (find_succ_ignore_empties(loop.bb_compare.neq_edge->dest) != loop.bb_end)
+ return false;
+ if (loop.bb_compare.cmp_base_ssa1 != loop.bb_advance.cmp_base_ssa1)
+ return false;
+ if (loop.bb_compare.cmp_base_ssa2 != loop.bb_advance.cmp_base_ssa2)
+ return false;
+ if (loop.bb_compare.eq_edge->dest != loop.bb_advance.bb)
+ return false;
+ if (loop.bb_compare.neq_edge->dest != loop.bb_end)
+ return false;
+
+ if (loop.bb_advance.cmp_base_im_ssa1 != loop.bb_bounds.cmp_base_im_ssa1)
+ return false;
+ if (loop.bb_advance.cmp_base_im_ssa2 != loop.bb_bounds.cmp_base_im_ssa2)
+ return false;
+ if (loop.bb_advance.cmp_base_ssa1 != loop.bb_bounds.cmp_base_ssa1)
+ return false;
+ if (loop.bb_advance.cmp_base_ssa2 != loop.bb_bounds.cmp_base_ssa2)
+ return false;
+
+ if (loop.bb_bounds.end_edge->dest != loop.bb_end)
+ return false;
+ if (loop.bb_bounds.no_end_edge->dest != loop.bb_advance.bb)
+ return false;
+ /* Initial bases should be function args */
+ if (TREE_CODE(loop.bb_bounds.cmp_initial_base_ssa1) != SSA_NAME) return
false;
+ if (TREE_CODE(loop.bb_bounds.cmp_initial_base_ssa2) != SSA_NAME) return
false;
+ if (SSA_NAME_IS_DEFAULT_DEF(loop.bb_bounds.cmp_initial_base_ssa1) ==
+ PARM_DECL)
+ return false;
+ if (SSA_NAME_IS_DEFAULT_DEF(loop.bb_bounds.cmp_initial_base_ssa2) ==
+ PARM_DECL)
+ return false;
+
+ return true;
+}
+
+/* === Core pass logic === */
+
+/* Restructures std::array equality structure into one that is more easily
+ * inlineable, matching the structure of the merged field cmps, from:
+ *
+ * <bb 2>
+ * _1 = __last1_6(D) - __first1_7(D);
+ * if (_1 != 0)
+ * goto <bb 3>;
+ * else
+ * goto <bb 4>;
+ * <bb 3>
+ * _12 = (long unsigned int) _1;
+ * _14 = __builtin_memcmp (__first1_7(D), __first2_11(D), _12);
+ * _13 = _14 == 0;
+ * <bb 4>
+ * # _4 = PHI <_13(3), 1(2)>
+ *
+ * to:
+ *
+ * <bb 2>
+ * _1 = __last1_6(D) - __first1_7(D);
+ * _12 = (long unsigned int) _1;
+ * _14 = __builtin_memcmp (__first1_7(D), __first2_11(D), _12);
+ * if (_14 == 0)
+ * goto <bb 4>;
+ * else
+ * goto <bb 3>;
+ * <bb 3>
+ * <bb 4>
+ * # _4 = PHI <0(3), 1(2)>
+ */
+
+static bool restructure_int_stdarr(basic_block bb_phi) {
+ gphi* phi_stmt = gsi_start_phis(bb_phi).phi();
+ if (gimple_phi_num_args((gimple*)phi_stmt) != 2) return false;
+ basic_block bb_len_test = NULL;
+ basic_block bb_compare = NULL;
+ for (size_t i = 0; i < 2; ++i) {
+ edge bb_incoming_e = find_decision_edge_from_arg(bb_phi, i);
+ if (bb_incoming_e == NULL) continue;
+ tree incoming = gimple_phi_arg_def(phi_stmt, i);
+ if (TREE_CODE_CLASS(TREE_CODE(incoming)) == tcc_constant)
+ bb_len_test = bb_incoming_e->src;
+ else
+ bb_compare = bb_incoming_e->src;
+ }
+ if (bb_len_test == NULL) return false;
+
+ /* Find statement computing memcmp length */
+ gassign* len_def_stmt = NULL;
+ gimple_stmt_iterator gsi = gsi_start_bb(bb_len_test);
+ if ((len_def_stmt = safe_dyn_cast<gassign*>(gsi.ptr))) {
+ if (gimple_assign_rhs_code(len_def_stmt) != POINTER_DIFF_EXPR) return
false;
+ if (TREE_CODE(gimple_assign_rhs1(len_def_stmt)) != SSA_NAME) return false;
+ if (TREE_CODE(gimple_assign_rhs2(len_def_stmt)) != SSA_NAME) return false;
+ if (!SSA_NAME_IS_DEFAULT_DEF(gimple_assign_rhs1(len_def_stmt)))
+ return false;
+ if (!SSA_NAME_IS_DEFAULT_DEF(gimple_assign_rhs2(len_def_stmt)))
+ return false;
+ } else
+ return false; /* len def should be first stmt in block */
+
+ /* Find statement calling memcmp */
+ gimple* memcmp_stmt = NULL;
+ for (gsi = gsi_start_bb(bb_compare); !gsi_end_p(gsi); gsi_next(&gsi)) {
+ if (gcall* stmt = safe_dyn_cast<gcall*>(gsi.ptr)) {
+ if (DECL_FUNCTION_CODE(gimple_call_fndecl(stmt)) != BUILT_IN_MEMCMP &&
+ DECL_FUNCTION_CODE(gimple_call_fndecl(stmt)) != BUILT_IN_MEMCMP_EQ)
+ return false;
+ memcmp_stmt = stmt;
+ }
+ }
+ if (memcmp_stmt == NULL) return false;
+ /* Create new block for new structure */
+ edge compare_to_newcompare =
+ split_block(bb_compare, gsi_last_bb(bb_compare).ptr);
+ basic_block bb_new_compare = compare_to_newcompare->dest;
+
+ /* Retrieve original statements' data to use in building copies */
+ tree len_def_end = gimple_assign_rhs1(len_def_stmt);
+ tree len_def_start = gimple_assign_rhs2(len_def_stmt);
+ tree new_len_def_ssa = make_ssa_name(long_integer_type_node, NULL);
+ tree new_len_def_cast_ssa = make_ssa_name(size_type_node, NULL);
+
+ tree memcmp_arg0 = gimple_call_arg(memcmp_stmt, 0);
+ tree memcmp_arg1 = gimple_call_arg(memcmp_stmt, 1);
+ tree new_memcmp_ssa = make_ssa_name(integer_type_node, NULL);
+
+ /* Create new structure's (copied) statements */
+ gimple* new_len_def_stmt = gimple_build_assign(
+ new_len_def_ssa, POINTER_DIFF_EXPR, len_def_end, len_def_start);
+ gimple* new_len_def_cast_stmt = gimple_build_assign(
+ new_len_def_cast_ssa, fold_convert(size_type_node, new_len_def_ssa));
+ gimple* new_memcmp_stmt =
+ gimple_build_call(builtin_decl_implicit(BUILT_IN_MEMCMP_EQ), 3,
+ memcmp_arg0, memcmp_arg1, new_len_def_cast_ssa);
+ gimple_call_set_lhs(new_memcmp_stmt, new_memcmp_ssa);
+ tree new_memcmp_res_cond = build2(EQ_EXPR, boolean_type_node, new_memcmp_ssa,
+ build_zero_cst(integer_type_node));
+ gimple* new_memcmp_res_cond_stmt =
+ gimple_build_cond_from_tree(new_memcmp_res_cond, NULL_TREE, NULL_TREE);
+
+ /* Insert new statements into new block */
+ gsi = gsi_last_bb(bb_new_compare);
+ gsi_insert_after(&gsi, new_len_def_stmt, GSI_CONTINUE_LINKING);
+ gsi_insert_after(&gsi, new_len_def_cast_stmt, GSI_CONTINUE_LINKING);
+ gsi_insert_after(&gsi, new_memcmp_stmt, GSI_CONTINUE_LINKING);
+ gsi_insert_after(&gsi, new_memcmp_res_cond_stmt, GSI_CONTINUE_LINKING);
+
+ gcc_assert(single_pred_p(bb_len_test));
+
+ /* Make function start at bb_new_compare */
+ redirect_edge_succ(find_edge(single_pred(bb_len_test), bb_len_test),
+ bb_new_compare);
+ /* Remove fallthru edge from bb_compare that is now on bb_new_compare due to
+ * split */
+ if (find_edge(bb_new_compare, bb_phi))
+ remove_edge(find_edge(bb_new_compare, bb_phi));
+
+ /* Create empty block used for edge taken on memcmp failure */
+ edge new_cmp_to_empty =
+ split_block(bb_new_compare, gsi_last_bb(bb_new_compare).ptr);
+ new_cmp_to_empty->flags &= ~EDGE_FALLTHRU;
+ new_cmp_to_empty->flags |= EDGE_FALSE_VALUE;
+ new_cmp_to_empty->probability = profile_probability::even();
+
+ basic_block bb_new_empty = new_cmp_to_empty->dest;
+ make_edge(bb_new_compare, bb_phi, EDGE_TRUE_VALUE)->probability =
+ profile_probability::even();
+ make_edge(bb_new_empty, bb_phi, EDGE_FALLTHRU)->probability =
+ profile_probability::always();
+
+ /* Update phi stmt args */
+ gphi* phi = gsi_start_phis(bb_phi).phi();
+ tree phi_arg_type = TREE_TYPE(gimple_phi_result(phi));
+ for (size_t i = 0; i < EDGE_COUNT(bb_phi->preds); ++i) {
+ edge e_bb = gimple_phi_arg_edge(phi, i);
+ if (e_bb->src == bb_new_compare)
+ SET_PHI_ARG_DEF(phi, i, build_int_cst(phi_arg_type, 1));
+ else if (e_bb->src == bb_new_empty)
+ SET_PHI_ARG_DEF(phi, i, build_int_cst(phi_arg_type, 0));
+ }
+ if (dump_file)
+ fprintf(dump_file, "Modified std::array equality for better inlining");
+ return true;
+}
+
+/* Parses std::array equality's bound checking block:
+ *
+ * # __first1_2 = PHI <__first1_7(D)(2), __first1_14(4)>
+ * # __first2_3 = PHI <__first2_8(D)(2), __first2_15(4)>
+ * if (__first1_2 != __last1_10(D))
+ * goto <bb x>;
+ * else
+ * goto <bb 7>;
+ */
+static bound_check_blk parse_bb_boundcheck(basic_block bb,
+ basic_block bb_initial) {
+ bound_check_blk bb_bounds, invalid_bb;
+ invalid_bb.bb = NULL;
+ bb_bounds.bb = bb;
+ bb_bounds.cmp_base_ssa1 = NULL_TREE;
+ bb_bounds.cmp_base_ssa2 = NULL_TREE;
+
+ gphi_iterator phi_i;
+ for (phi_i = gsi_start_phis(bb); !gsi_end_p(phi_i); gsi_next(&phi_i)) {
+ gimple* phi_stmt = phi_i.phi();
+ if (gimple_phi_num_args(phi_stmt) != 2) return invalid_bb;
+ tree cmp_initial_base_ssa;
+ tree cmp_base_im_ssa;
+ tree cmp_base_ssa;
+ edge bb_e0 = find_decision_edge_from_arg(bb, 0);
+ edge bb_e1 = find_decision_edge_from_arg(bb, 1);
+ /* dest not src since entry bb will be fallthrough too, giving us function
+ * entry bb 0 */
+ size_t initial_entry_idx =
+ bb_e0->dest == bb_initial ? 0 : (bb_e1->dest == bb_initial ? 1 : 2);
+ /* Neither edges originate from the function's initial block */
+ if (initial_entry_idx == 2) return invalid_bb;
+ /* Since initial base is from function input, now assigned to base that
+ * will advance */
+ cmp_initial_base_ssa = gimple_phi_arg_def(phi_stmt, initial_entry_idx);
+ cmp_base_im_ssa = gimple_phi_arg_def(phi_stmt, 1 - initial_entry_idx);
+ cmp_base_ssa = gimple_phi_result(phi_stmt);
+
+ if (bb_bounds.cmp_base_ssa1 == NULL_TREE) {
+ bb_bounds.cmp_base_ssa1 = cmp_base_ssa;
+ bb_bounds.cmp_base_im_ssa1 = cmp_base_im_ssa;
+ bb_bounds.cmp_initial_base_ssa1 = cmp_initial_base_ssa;
+ } else if (bb_bounds.cmp_base_ssa2 == NULL_TREE) {
+ bb_bounds.cmp_base_ssa2 = cmp_base_ssa;
+ bb_bounds.cmp_base_im_ssa2 = cmp_base_im_ssa;
+ bb_bounds.cmp_initial_base_ssa2 = cmp_initial_base_ssa;
+ } else
+ return invalid_bb;
+ }
+ gimple_stmt_iterator gsi;
+ for (gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {
+ if (is_a<gdebug*>(gsi.ptr)) continue;
+ if (gcond* cond = safe_dyn_cast<gcond*>(gsi.ptr)) {
+ /* normalization failed, condition was neither NE nor EQ */
+ if (!normalize_bb_condition(bb_bounds.bb, true)) return invalid_bb;
+ if (gimple_cond_lhs(cond) != bb_bounds.cmp_base_ssa1 &&
+ gimple_cond_rhs(cond) != bb_bounds.cmp_base_ssa1)
+ return invalid_bb;
+ if (gimple_cond_lhs(cond) != bb_bounds.cmp_base_ssa1)
+ bb_bounds.base_end_ssa = gimple_cond_lhs(cond);
+ else
+ bb_bounds.base_end_ssa = gimple_cond_rhs(cond);
+ bb_bounds.no_end_edge = GET_TRUE_EDGE(bb_bounds.bb->succs);
+ bb_bounds.end_edge = GET_FALSE_EDGE(bb_bounds.bb->succs);
+ } else
+ return invalid_bb;
+ }
+ if (bb_bounds.cmp_base_ssa1 == NULL_TREE ||
+ bb_bounds.cmp_base_ssa2 == NULL_TREE)
+ return invalid_bb;
+ return bb_bounds;
+}
+/* Parses std::array equality's comparison block:
+ *
+ * _12 = __first1_2->a;
+ * _17 = __first2_3->a;
+ * if (_12 == _17)
+ * goto <bb x>;
+ * else
+ * goto <bb y>;
+ */
+static compare_blk parse_bb_compare(basic_block bb) {
+ compare_blk bb_compare, invalid_bb;
+ invalid_bb.bb = NULL;
+ bb_compare.bb = bb;
+ if (!bb_is_comparison(bb)) return invalid_bb;
+
+ bb_compare.cmp = get_cmp_bb(bb);
+ bb_compare.cmp_base_ssa1 = bb_compare.cmp.lhs.base;
+ bb_compare.cmp_base_ssa2 = bb_compare.cmp.rhs.base;
+
+ if (!normalize_bb_condition(bb)) return invalid_bb;
+ bb_compare.eq_edge = GET_TRUE_EDGE(bb_compare.bb->succs);
+ bb_compare.neq_edge = GET_FALSE_EDGE(bb_compare.bb->succs);
+ /* To get the SSA from the MEM_REF/COMPONENT_REF */
+ bb_compare.cmp_base_ssa1 = TREE_OPERAND(bb_compare.cmp_base_ssa1, 0);
+ bb_compare.cmp_base_ssa2 = TREE_OPERAND(bb_compare.cmp_base_ssa2, 0);
+ return bb_compare;
+}
+/* Parses std::array equality's ptr advancing block:
+ *
+ * __first1_14 = __first1_2 + 4;
+ * __first2_15 = __first2_3 + 4;
+ * goto <bb x>;
+ */
+static advance_blk parse_bb_advance(basic_block bb) {
+ advance_blk bb_advance, invalid_bb;
+ invalid_bb.bb = NULL;
+ bb_advance.bb = bb;
+ bb_advance.cmp_base_ssa1 = NULL_TREE;
+ bb_advance.cmp_base_ssa2 = NULL_TREE;
+ gimple_stmt_iterator gsi;
+ for (gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {
+ if (is_a<gdebug*>(gsi.ptr)) continue;
+ if (gassign* stmt = safe_dyn_cast<gassign*>(gsi.ptr)) {
+ /* Is the LHS of the assignment, adds offset to real base used in cmps */
+ tree advance_im_base;
+ tree advance_base;
+ tree advance_len_tr;
+ widest_int advance_len;
+ advance_im_base = gimple_assign_lhs(stmt);
+ advance_base = gimple_assign_rhs1(stmt);
+ advance_len_tr = gimple_assign_rhs2(stmt);
+ if (advance_base == NULL_TREE || advance_len_tr == NULL_TREE ||
+ gimple_assign_rhs3(stmt) != NULL_TREE)
+ return invalid_bb;
+ advance_len = wi::to_widest(advance_len_tr);
+ if (gimple_assign_rhs_code(stmt) != POINTER_PLUS_EXPR) return invalid_bb;
+ if (bb_advance.cmp_base_ssa1 == NULL_TREE) {
+ bb_advance.cmp_base_ssa1 = advance_base;
+ bb_advance.cmp_base_im_ssa1 = advance_im_base;
+ bb_advance.advance_len = advance_len;
+ } else if (bb_advance.cmp_base_ssa2 == NULL_TREE) {
+ /* Pointers advancing by different amount */
+ if (bb_advance.advance_len != advance_len) return invalid_bb;
+ bb_advance.cmp_base_ssa2 = advance_base;
+ bb_advance.cmp_base_im_ssa2 = advance_im_base;
+ } else
+ return invalid_bb;
+ } else
+ return invalid_bb;
+ }
+ if (bb_advance.cmp_base_ssa1 == NULL_TREE ||
+ bb_advance.cmp_base_ssa2 == NULL_TREE)
+ return invalid_bb;
+ return bb_advance;
+}
+
+/* When analyze_cmp_loop recognizes this structure:
+ * /----------------------bb empty(s)------------\
+ * / V
+ *-> compare bb -> advance ptrs bb -> bound check bb -> bb_phi
+ * ^ /
+ * \----------------------------------
+ *
+ * If the elements are consecutive, it replaces the loop with a builtin_memcmp
+ *
+ * If it recognizes the array equality already uses a memcmp and does not loop,
+ * it modifies the structure to help with inlining using
+ * `restructure_int_stdarr`.
+ *
+ * Returns true if original loop structure was replaced.
+ */
+static bool analyze_cmp_loop(basic_block bb_phi, basic_block bb_initial) {
+ if (!single_succ_p(bb_phi)) return false;
+ icmploop loop;
+ gphi* phi_stmt = gsi_start_phis(bb_phi).phi();
+ unsigned phi_arg_n = gimple_phi_num_args((gimple*)phi_stmt);
+ hash_set<basic_block> phi_blocks;
+
+ basic_block bb_boundcheck = NULL;
+ basic_block bb_compare = NULL;
+ basic_block bb_advance = NULL;
+ for (unsigned i = 0; i < phi_arg_n; ++i) {
+ edge bb_incoming_e = find_decision_edge_from_arg(bb_phi, i);
+ if (bb_incoming_e == NULL) continue;
+ tree incoming = gimple_phi_arg_def(phi_stmt, i);
+ if (incoming == NULL_TREE) continue;
+ if (!integer_zerop(incoming))
+ bb_boundcheck = bb_incoming_e->src;
+ else
+ bb_compare = bb_incoming_e->src;
+ }
+ if (bb_boundcheck == NULL) return false;
+ /* Since integer std::array equality uses 1 CST for early
+ * break on len==0, while bb_compare gets assigned at 0 CST */
+ if (bb_compare == NULL) return restructure_int_stdarr(bb_phi);
+
+ loop.bb_initial = bb_initial;
+ loop.bb_end = bb_phi;
+ loop.outgoing = single_succ(loop.bb_end);
+
+ loop.bb_compare = parse_bb_compare(bb_compare);
+ loop.bb_bounds = parse_bb_boundcheck(bb_boundcheck, bb_initial);
+
+ if (loop.bb_compare.bb == NULL || loop.bb_bounds.bb == NULL) return false;
+
+ bb_advance = loop.bb_compare.eq_edge->dest;
+ loop.bb_advance = parse_bb_advance(bb_advance);
+
+ if (loop.bb_advance.bb == NULL) return false;
+
+ if (!is_valid_cmp_loop(loop)) return false;
+
+ /* Since we remove all phi defs, just use the initial base from the function
+ * args */
+ TREE_OPERAND(loop.bb_compare.cmp.lhs.base, 0) =
+ loop.bb_bounds.cmp_initial_base_ssa1;
+ loop.bb_compare.cmp.lhs.offset = 0;
+ loop.bb_compare.cmp.lhs.refd = false;
+ TREE_OPERAND(loop.bb_compare.cmp.rhs.base, 0) =
+ loop.bb_bounds.cmp_initial_base_ssa2;
+ loop.bb_compare.cmp.rhs.offset = 0;
+ loop.bb_compare.cmp.rhs.refd = false;
+ loop.bb_compare.cmp.is_int_cmp = true;
+
+ basic_block bb_start = loop.bb_initial;
+ while (EDGE_COUNT(bb_start->succs) > 0) remove_edge(EDGE_SUCC(bb_start, 0));
+
+ /* Create block that checks if memcmp length is 0 */
+ tree memcmp_len_ssa = make_ssa_name(long_integer_type_node, NULL);
+ gimple* memcmp_len_stmt = gimple_build_assign(
+ memcmp_len_ssa, POINTER_DIFF_EXPR, loop.bb_bounds.base_end_ssa,
+ loop.bb_bounds.cmp_initial_base_ssa1);
+ gimple_stmt_iterator gsi = gsi_last_bb(bb_start);
+ gsi_insert_after(&gsi, memcmp_len_stmt, GSI_CONTINUE_LINKING);
+
+ /* Do actual comparison */
+ basic_block bb_cmp = bb_start;
+ gimple* memcmp_len_casted =
+ gimple_build_assign(make_ssa_name(size_type_node, NULL),
+ fold_convert(size_type_node, memcmp_len_ssa));
+ gimple* memcmp_call =
+ gimple_build_call(builtin_decl_implicit(BUILT_IN_MEMCMP_EQ), 3,
+ loop.bb_bounds.cmp_initial_base_ssa1,
+ loop.bb_bounds.cmp_initial_base_ssa2,
+ gimple_assign_lhs(memcmp_len_casted));
+ tree memcmp_call_ssa = make_ssa_name(integer_type_node, NULL);
+ gimple_call_set_lhs(memcmp_call, memcmp_call_ssa);
+ gimple* memcmp_res_cond = gimple_build_cond_from_tree(
+ build2(EQ_EXPR, boolean_type_node, memcmp_call_ssa,
+ build_int_cst(integer_type_node, 0)),
+ NULL_TREE, NULL_TREE);
+
+ gsi = gsi_last_bb(bb_cmp);
+ gsi_insert_after(&gsi, memcmp_len_casted, GSI_CONTINUE_LINKING);
+ gsi_insert_after(&gsi, memcmp_call, GSI_CONTINUE_LINKING);
+ gsi_insert_after(&gsi, memcmp_res_cond, GSI_CONTINUE_LINKING);
+
+ edge bb_cmp_empty_e = split_block(bb_cmp, memcmp_res_cond);
+ basic_block bb_cmp_empty = bb_cmp_empty_e->dest;
+ remove_edge(find_edge(bb_cmp, bb_cmp_empty));
+ make_edge(bb_cmp, bb_phi, EDGE_TRUE_VALUE)->probability =
+ profile_probability::even();
+ make_edge(bb_cmp, bb_cmp_empty, EDGE_FALSE_VALUE)->probability =
+ profile_probability::even();
+ make_edge(bb_cmp_empty, bb_phi, EDGE_FALLTHRU)->probability =
+ profile_probability::always();
+
+ tree phi_arg_type = TREE_TYPE(gimple_phi_result(phi_stmt));
+ for (unsigned i = 0; i < EDGE_COUNT(bb_phi->preds); ++i) {
+ edge e_bb = gimple_phi_arg_edge(phi_stmt, i);
+ if (e_bb->src == bb_cmp)
+ SET_PHI_ARG_DEF(phi_stmt, i, build_int_cst(phi_arg_type, 1));
+ else if (e_bb->src == bb_cmp_empty)
+ SET_PHI_ARG_DEF(phi_stmt, i, build_int_cst(phi_arg_type, 0));
+ }
+ if (dump_file)
+ fprintf(dump_file, "\tUnrolled std::array equality loop to memcmp\n");
+ return true;
+}
+
+unsigned int pass_stdarr_eq(function* fun) {
+ basic_block bb_initial = fun->cfg->x_entry_block_ptr->next_bb;
+
+ basic_block bb;
+ FOR_EACH_BB_REVERSE_FN(bb, fun) {
+ if (phi_nodes(bb) == NULL) continue;
+ if (analyze_cmp_loop(bb, bb_initial)) break;
+ }
+ return TODO_cleanup_cfg | TODO_update_ssa;
+}
+
+}
+
+gimple_opt_pass* make_pass_tree_arr_eq_merge(gcc::context* ctxt) {
+ return new pass_tree_arr_eq_merge(ctxt);
+}
+
+unsigned int pass_tree_arr_eq_merge::execute(function* fun) {
+ if (!builtin_decl_implicit(BUILT_IN_MEMCMP_EQ)) return false;
+
+ /* Checks if one of the underlying std::array equality functions, used for
+ * replacing looped compares with __builtin_memcmp */
+ if (is_stdarr_eq_fn(fun->decl)) return pass_stdarr_eq(fun);
+
+ return 0;
+}
diff --git a/gcc/tree-ssa-eqmerge.cc b/gcc/tree-ssa-eqmerge.cc
new file mode 100644
index 00000000000..dac1873f722
--- /dev/null
+++ b/gcc/tree-ssa-eqmerge.cc
@@ -0,0 +1,332 @@
+#include "tree-ssa-eqmerge.h"
+
+/* === Helper functions for structure parsing == */
+
+/* Follows fallthrough edges from given bb and edge.
+ * Returns edge from first non-empty bb in direction of bb_phi,
+ * where the "decision" to flow into bb_phi is made.
+ * Or where two decision edge paths to flow into bb_phi converge. */
+edge find_decision_edge_from_arg(basic_block bb_phi, size_t arg_i) {
+ gphi* phi_stmt = gsi_start_phis(bb_phi).phi();
+ edge e_crnt = gimple_phi_arg_edge(phi_stmt, arg_i);
+ if (!empty_block_p(e_crnt->src)) return e_crnt;
+ if (!(e_crnt->flags & EDGE_FALLTHRU)) return NULL;
+ if (!single_pred_p(e_crnt->src)) return e_crnt;
+ basic_block bb_current = e_crnt->src;
+ while (bb_current != NULL) {
+ e_crnt = single_pred_edge(bb_current);
+ bb_current = e_crnt->src;
+ if (!empty_block_p(bb_current)) return e_crnt;
+ if (!single_pred_p(bb_current)) return e_crnt;
+ }
+ return NULL;
+}
+
+/* Follows fallthrough edges, used so paths of empty bbs
+ * interleaved in chain structure pose no issue */
+basic_block find_succ_ignore_empties(basic_block bb_empty) {
+ basic_block bb_crnt = bb_empty;
+ while (1) {
+ if (!empty_block_p(bb_crnt)) return bb_crnt;
+ if (!single_succ_p(bb_crnt)) return NULL;
+ bb_crnt = single_succ(bb_crnt);
+ }
+}
+
+/* Transforms conditional operator and outgoing edges so all
+ * equivalent condition blocks can be discovered more easily.
+ * Condition is assigned EQ and edge true/false is inverted if needed.
+ * Returns FALSE if condition is found using neither NE nor EQ. */
+bool normalize_bb_condition(basic_block bb, bool inverted) {
+ gimple_stmt_iterator gsi;
+ for (gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {
+ gcond* cond;
+ if (!(cond = safe_dyn_cast<gcond*>(gsi.ptr))) continue;
+ tree_code cond_op = gimple_cond_code(cond);
+ if (cond_op != EQ_EXPR && cond_op != NE_EXPR) return false;
+ if (cond_op == (inverted ? NE_EXPR : EQ_EXPR)) continue;
+
+ edge e;
+ edge_iterator it;
+ FOR_EACH_EDGE(e, it, bb->succs) {
+ if (e->flags & EDGE_TRUE_VALUE) {
+ e->flags ^= EDGE_TRUE_VALUE;
+ e->flags |= EDGE_FALSE_VALUE;
+ } else if (e->flags & EDGE_FALSE_VALUE) {
+ e->flags ^= EDGE_FALSE_VALUE;
+ e->flags |= EDGE_TRUE_VALUE;
+ }
+ }
+ gimple_cond_set_code(cond, EQ_EXPR);
+ return true;
+ }
+ return true;
+}
+
+/* Returns true if the given basic block satisfies:
+ * 1. Assigns to exactly 2 SSA's (and one optional fn call return SSA).
+ * Both of these SSA's should exactly 1 immediate use.
+ * 2. RHS's is component reference or address to one, for all assignments
+ * 3. May contain 1 __builtin_memcmp's fn call using the two SSA's as arg0 and
+ * arg1, and a constant for arg3. This way, we can parse and merge
+ * already-passed operator=='s with their calling operator==, in case of
+ * equality on struct with other struct as member. Reverse topological
+ * pass-application order guaranteed by pass manager.
+ * The memcmp result SSA should have exactly 1 immediate use.
+ * 4. Block ends in a condition with an equality check on, either memory read
by
+ * the 2 SSA's defined in this block, or on the memcmp result with zero.
+ *
+ * Allows for later stages to use relatively simple case distinction instead of
+ * continuously checking block validity.
+ */
+bool bb_is_comparison(basic_block bb) {
+ if (phi_nodes(bb) != NULL) return false;
+ vec<tree> tocmp_ssas = vNULL;
+ gcall* tocmp_memcmpcall = NULL;
+ tocmp_ssas.reserve(2);
+
+ gimple_stmt_iterator gsi;
+ for (gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {
+ if (is_a<gdebug*>(gsi.ptr))
+ continue;
+ else if (gassign* assign_stmt = safe_dyn_cast<gassign*>(gsi.ptr)) {
+ /* Condition 1 */
+ if (tocmp_ssas.length() == 2) return false;
+
+ /* Condition 2 */
+ if (gimple_assign_rhs2(assign_stmt) != NULL_TREE) return false;
+
+ tree assign_val = gimple_assign_rhs1(assign_stmt);
+
+ if (TREE_CODE(assign_val) == ADDR_EXPR)
+ assign_val = TREE_OPERAND(assign_val, 0);
+ if (TREE_CODE(assign_val) != COMPONENT_REF) return false;
+
+ tree tocmp_ssa = gimple_assign_lhs(assign_stmt);
+
+ if (num_imm_uses(tocmp_ssa) != 1) return false;
+
+ tocmp_ssas.quick_push(tocmp_ssa);
+ } else if (gcall* memcmp_stmt = safe_dyn_cast<gcall*>(gsi.ptr)) {
+ /* Condition 3 */
+ if (tocmp_memcmpcall != NULL) return false;
+ tree retval_fndecl = gimple_call_fndecl(memcmp_stmt);
+
+ if (gimple_call_num_args(memcmp_stmt) != 3 ||
+ (DECL_FUNCTION_CODE(retval_fndecl) != BUILT_IN_MEMCMP &&
+ DECL_FUNCTION_CODE(retval_fndecl) != BUILT_IN_MEMCMP_EQ))
+ return false;
+ if (num_imm_uses(gimple_call_lhs(memcmp_stmt)) != 1) return false;
+
+ tocmp_memcmpcall = memcmp_stmt;
+ } else if (gcond* cmp_cond = safe_dyn_cast<gcond*>(gsi.ptr)) {
+ /* Condition 4 */
+ if (gimple_cond_code(gsi.ptr) != EQ_EXPR &&
+ gimple_cond_code(gsi.ptr) != NE_EXPR)
+ return false;
+ /*
+ * _1 = _12(D)->e;
+ * _2 = this_13(D)->e;
+ * if (_1 !=/== _2)
+ */
+ if (tocmp_ssas.length() == 2 &&
+ tocmp_memcmpcall == NULL) /* Normal field comparison */
+ {
+ if (gimple_cond_rhs(cmp_cond) == gimple_cond_lhs(cmp_cond))
+ return false;
+ if (gimple_cond_lhs(cmp_cond) != tocmp_ssas[0] &&
+ gimple_cond_lhs(cmp_cond) != tocmp_ssas[1])
+ return false;
+ if (gimple_cond_rhs(cmp_cond) != tocmp_ssas[0] &&
+ gimple_cond_rhs(cmp_cond) != tocmp_ssas[1])
+ return false;
+ return true;
+ }
+ /*
+ * _1 = &_12(D)->e;
+ * _2 = &this_13(D)->e;
+ * _3 = __builtin_memcmp (_2, _1, x);
+ * if (_3 !=/== 0)
+ */
+ else if (tocmp_ssas.length() == 2 &&
+ tocmp_memcmpcall) /* __builtin_memcmp call */
+ {
+ tree memcmp_res_ssa = gimple_call_lhs(tocmp_memcmpcall);
+ if (((gimple_cond_lhs(cmp_cond) == memcmp_res_ssa) ^
+ (gimple_cond_rhs(cmp_cond) == memcmp_res_ssa)) == 0)
+ return false;
+
+ tree cond_lhs = gimple_cond_lhs(cmp_cond);
+ tree cond_rhs = gimple_cond_rhs(cmp_cond);
+ tree cond_constval = memcmp_res_ssa == cond_lhs ? cond_rhs : cond_lhs;
+
+ if (memcmp_res_ssa == NULL_TREE) return false;
+ if (TREE_CODE_CLASS(TREE_CODE(cond_constval)) != tcc_constant)
+ return false;
+ if (!integer_zerop(cond_constval)) return false;
+
+ /* Condition 3 */
+ tree memcmp_call_arg0 = gimple_call_arg(tocmp_memcmpcall, 0);
+ tree memcmp_call_arg1 = gimple_call_arg(tocmp_memcmpcall, 1);
+ if (memcmp_call_arg0 == memcmp_call_arg1) return false;
+ if (memcmp_call_arg0 != tocmp_ssas[0] &&
+ memcmp_call_arg1 != tocmp_ssas[0])
+ return false;
+ if (memcmp_call_arg0 != tocmp_ssas[1] &&
+ memcmp_call_arg1 != tocmp_ssas[1])
+ return false;
+ tree memcmp_call_size = gimple_call_arg(tocmp_memcmpcall, 2);
+ if (TREE_CODE_CLASS(TREE_CODE(memcmp_call_size)) != tcc_constant)
+ return false;
+ return true;
+ } else
+ return false;
+ } else
+ return false;
+ }
+ /* If block does not end on a condition, return false */
+ return false;
+}
+/* Parses condition in input bb into icmp.
+ * Can parse conditionals between COMPONENT and MEM REF's,
+ * but also conditionals on __builtin_memcmp, which originate
+ * from inlining of result of previous execution of this pass. */
+icmp get_cmp_bb(basic_block bb) {
+ gimple_stmt_iterator gsi;
+ for (gsi = gsi_start_bb(bb); !gsi_end_p(gsi); gsi_next(&gsi)) {
+ if (gcond* stmt = safe_dyn_cast<gcond*>(gsi.ptr)) {
+ tree cond_lhs = gimple_cond_lhs(stmt);
+ tree cond_rhs = gimple_cond_rhs(stmt);
+
+ if (TREE_CODE_CLASS(TREE_CODE(cond_lhs)) == tcc_constant ||
+ TREE_CODE_CLASS(TREE_CODE(cond_rhs)) ==
+ tcc_constant) /* then is __builtin_memcmp call */
+ return parse_cond_builtin_memcmp(stmt);
+ return parse_cond_cmp_stmt(stmt);
+ }
+ }
+ return {{NULL, NULL_TREE, NULL_TREE, NULL, 0},
+ {NULL, NULL_TREE, NULL_TREE, NULL, 0},
+ 0,
+ NULL,
+ NULL_TREE,
+ NULL_TREE};
+}
+
+/* Parse component ref comparison conditions into icmp */
+icmp parse_cond_cmp_stmt(gcond* stmt) {
+ tree cond_lhs = gimple_cond_lhs(stmt);
+ tree cond_rhs = gimple_cond_rhs(stmt);
+ loadinf cond_lhs_load = loadinf_from_ssa(cond_lhs);
+ loadinf cond_rhs_load = loadinf_from_ssa(cond_rhs);
+ if (!LOADINF_IS_VALID(cond_lhs_load) || !LOADINF_IS_VALID(cond_rhs_load) ||
+ wi::to_widest(cond_lhs_load.size) != wi::to_widest(cond_rhs_load.size))
+ return {{NULL, NULL_TREE, NULL_TREE, NULL, 0},
+ {NULL, NULL_TREE, NULL_TREE, NULL, 0},
+ 0,
+ NULL,
+ NULL_TREE,
+ NULL_TREE};
+
+ bool is_int_cmp = ssa_is_int_type(cond_lhs) && ssa_is_int_type(cond_rhs);
+ return {cond_lhs_load, cond_rhs_load, is_int_cmp,
+ gimple_bb(stmt), NULL_TREE, NULL_TREE};
+}
+
+/* Parses __builtin_memcmps call into icmp */
+icmp parse_cond_builtin_memcmp(gcond* stmt) {
+ tree cond_lhs = gimple_cond_lhs(stmt);
+ tree cond_rhs = gimple_cond_rhs(stmt);
+
+ tree memcmp_res_ssa = TREE_CODE_CLASS(TREE_CODE(cond_lhs)) == tcc_constant
+ ? cond_rhs
+ : cond_lhs;
+ gimple* memcmp_res_ssa_def = SSA_NAME_DEF_STMT(memcmp_res_ssa);
+
+ tree lhs_base_ssa = gimple_call_arg(memcmp_res_ssa_def, 0);
+ tree rhs_base_ssa = gimple_call_arg(memcmp_res_ssa_def, 1);
+ tree load_size = gimple_call_arg(memcmp_res_ssa_def, 2);
+
+ /* We only handle __builtin_memcmp's generated by previous
+ * cmpchain pass:
+ * _1 = &_12(D)->e;
+ * _2 = &this_13(D)->e;
+ * _3 = __builtin_memcmp (_2, _1, x);
+ */
+ loadinf lhs_load = loadinf_from_ssa(lhs_base_ssa);
+ loadinf rhs_load = loadinf_from_ssa(rhs_base_ssa);
+ lhs_load.size = load_size;
+ rhs_load.size = load_size;
+ return {lhs_load, rhs_load, true, gimple_bb(stmt), NULL_TREE, NULL_TREE};
+}
+/* Returns whether or not input ssa is of a type whose entire memory region
+ * should be read and compared to determine equality */
+bool ssa_is_int_type(tree ssa) {
+ gimple* ssa_def = SSA_NAME_DEF_STMT(ssa);
+ if (!ssa_def || !is_a<gassign*>(ssa_def)) return false;
+ tree ssa_type = TREE_TYPE(gimple_assign_rhs1(ssa_def));
+ return INTEGRAL_TYPE_P(ssa_type) && TREE_CODE(ssa_type) != BOOLEAN_TYPE;
+}
+
+/* Finds SSA definition and parses it into loadinf.
+ * Use LOADINF_IS_VALID to check result validity. */
+loadinf loadinf_from_ssa(tree ssa) {
+ loadinf invalid_load = {NULL, NULL_TREE, NULL_TREE, NULL, 0};
+ gimple* ssa_def = SSA_NAME_DEF_STMT(ssa);
+
+ if (!ssa_def || !is_a<gassign*>(ssa_def)) return invalid_load;
+
+ tree ssa_rhs = gimple_assign_rhs1(ssa_def);
+
+ tree ssa_base;
+ widest_int ssa_offset;
+ tree ssa_offset_type;
+
+ bool derefd = false;
+ /* In case previous pass has already derefd this load */
+ if (TREE_CODE(ssa_rhs) == ADDR_EXPR) {
+ ssa_rhs = TREE_OPERAND(ssa_rhs, 0);
+ derefd = true;
+ }
+ if (TREE_CODE(ssa_rhs) == COMPONENT_REF) {
+ poly_int64 ssa_poffset;
+ HOST_WIDE_INT ssa_offseti;
+ ssa_base = get_addr_base_and_unit_offset(ssa_rhs, &ssa_poffset);
+
+ if (ssa_base == NULL_TREE || !ssa_poffset.is_constant(&ssa_offseti))
+ return invalid_load;
+ ssa_offset = ssa_offseti;
+ } else if (TREE_CODE(ssa_rhs) == MEM_REF) {
+ tree base_tree = TREE_OPERAND(ssa_rhs, 0);
+ tree offset_tree = TREE_OPERAND(ssa_rhs, 1);
+
+ if (base_tree == NULL_TREE) return invalid_load;
+
+ if (offset_tree == NULL_TREE || TREE_CODE(offset_tree) != INTEGER_CST)
+ ssa_offset = wi::to_widest(build_zero_cst(integer_type_node));
+ else
+ ssa_offset = wi::to_widest(offset_tree);
+
+ tree zero = build_int_cst(TREE_TYPE(offset_tree), 0);
+ ssa_base = build2(MEM_REF, TREE_TYPE(ssa_rhs), base_tree, zero);
+ } else
+ return invalid_load;
+ ssa_offset_type = build_offset_type(TREE_TYPE(ssa_rhs), TREE_TYPE(ssa_rhs));
+
+ tree ssa_type = TREE_TYPE(ssa_rhs);
+ tree ssa_size = TYPE_SIZE_UNIT(ssa_type);
+
+ /* base tree may contain offset, in case of member struct comparison:
+ * e.g. 3 bytes in MEM[(const struct A *)this_14(D) + 3B].a,
+ * must be zero'd and added to actual offset so bases can be compared */
+ if (TREE_OPERAND_LENGTH(ssa_base) >= 2) {
+ tree base_tree_offset = TREE_OPERAND(ssa_base, 1);
+ if (base_tree_offset != NULL_TREE && !integer_zerop(base_tree_offset)) {
+ ssa_offset = wi::add(ssa_offset, tree_to_shwi(base_tree_offset));
+ TREE_OPERAND(ssa_base, 1) = build_zero_cst(TREE_TYPE(base_tree_offset));
+ }
+ }
+
+ return {ssa_base, wide_int_to_tree(ssa_offset_type, ssa_offset), ssa_size,
+ ssa_def, derefd};
+}
diff --git a/gcc/tree-ssa-eqmerge.h b/gcc/tree-ssa-eqmerge.h
new file mode 100644
index 00000000000..fdd309b508b
--- /dev/null
+++ b/gcc/tree-ssa-eqmerge.h
@@ -0,0 +1,85 @@
+#include <gcc-plugin.h>
+#include <config.h>
+#include <system.h>
+#include <coretypes.h>
+#include <backend.h>
+#include <tree-pass.h>
+#include <gimple-pretty-print.h>
+#include <tree.h>
+#include <tree-dfa.h>
+#include <cp/cp-tree.h>
+#include <tree-pass.h>
+#include <gimple.h>
+#include <ssa.h>
+#include <gimple-iterator.h>
+#include <tree-pass.h>
+#include <vec.h>
+#include <tree-into-ssa.h>
+#include <context.h>
+
+#define GET_TRUE_EDGE(EDGE_VEC) \
+ EDGE_I((EDGE_VEC), ((EDGE_I((EDGE_VEC), 0)->flags & EDGE_TRUE_VALUE) ? 0 :
1))
+#define GET_FALSE_EDGE(EDGE_VEC) \
+ EDGE_I((EDGE_VEC), \
+ ((EDGE_I((EDGE_VEC), 0)->flags & EDGE_FALSE_VALUE) ? 0 : 1))
+
+/* === Helper types and functions for pass internal representations === */
+
+struct loadinf {
+ tree base;
+ tree offset;
+ tree size;
+ gimple* ssa_var_def;
+ bool refd;
+};
+struct icmp {
+ loadinf lhs;
+ loadinf rhs;
+ /* Whether or not comparison compares all bytes from load */
+ bool is_int_cmp;
+ /* Basic block this comparison was found in */
+ basic_block orig_bb;
+
+ /* Value assigned to phi stmt if false edge taken */
+ tree phi_false_val;
+ /* Value assigned to phi stmt if true edge taken (may be NULL_TREE) */
+ tree phi_true_val;
+};
+struct icmpchain {
+ vec<icmp> cmps;
+
+ /* The block that the last block in the icmpchain goes to when its condition
+ * returns true, may be equal to bb_phi */
+ basic_block outgoing_edge_dest;
+ basic_block last_bb;
+ /* The list of edges coming into the first block in the chain */
+ vec<edge> incoming_edges;
+};
+
+#define ICMP_IS_VALID(i) ((i).lhs.base != NULL)
+#define LOADINF_IS_VALID(i) ((i).base != NULL)
+
+/* Returns TRUE if bb does nothing but compare memory and branch on result */
+bool bb_is_comparison(basic_block bb);
+
+/* Returns icmp structure for condition in bb */
+icmp get_cmp_bb(basic_block bb);
+
+/* Parses condition comparing COMPONENT or MEM REF's */
+icmp parse_cond_cmp_stmt(gcond* stmt);
+/* Parses condition comparing memcmp result to constant */
+icmp parse_cond_builtin_memcmp(gcond* stmt);
+
+/* Finds SSA definition and parses it into loadinf */
+loadinf loadinf_from_ssa(tree ssa);
+
+/* SSA is of integral type, all its memory gets compared in equality */
+bool ssa_is_int_type(tree ssa);
+
+/* Replaces NE's with EQ's and switches edges if encountered */
+bool normalize_bb_condition(basic_block bb, bool inverted = false);
+
+/* Find originating edge for given bb_phi and arg index*/
+edge find_decision_edge_from_arg(basic_block bb_phi, size_t arg_i);
+/* Find nearest successor block to bb_empty that has TRUE/FALSE edges */
+basic_block find_succ_ignore_empties(basic_block bb_empty);
diff --git a/gcc/tree-ssa-struct-eqmerge.cc b/gcc/tree-ssa-struct-eqmerge.cc
new file mode 100644
index 00000000000..2595652a18e
--- /dev/null
+++ b/gcc/tree-ssa-struct-eqmerge.cc
@@ -0,0 +1,598 @@
+#include "tree-ssa-eqmerge.h"
+
+const pass_data pass_data_tree_struct_eq_merge = {
+ GIMPLE_PASS,
+ "structeqmerge",
+ OPTGROUP_NONE,
+ TV_NONE,
+ (PROP_cfg | PROP_ssa),
+ 0,
+ 0,
+ 0,
+ 0,
+};
+
+namespace {
+
+class pass_tree_struct_eq_merge : public gimple_opt_pass {
+ public:
+ pass_tree_struct_eq_merge(gcc::context* ctxt)
+ : gimple_opt_pass(pass_data_tree_struct_eq_merge, ctxt) {}
+
+ opt_pass* clone() final override {
+ return new pass_tree_struct_eq_merge(m_ctxt);
+ }
+ void set_pass_param(unsigned n, bool param) final override {
+ gcc_assert(n == 0);
+ use_dr_analysis_p = param;
+ }
+
+ bool gate(function*) final override { return optimize >= 2; }
+ unsigned int execute(function*) final override;
+
+ private:
+ bool use_dr_analysis_p;
+};
+
+/*
+ * Takes statement like:
+ * _1 = this_17(D)->a;
+ * and uses it to create:
+ * _24 = &this_17(D)->a;
+ *
+ * Making a new ssa and assigning it to the passed load inf.
+ * It does not add the new statement to any block.
+ */
+static void make_ref_load_rhs(loadinf* load) {
+ /* Even if load is already reference, we replace ssa since loadinf stmt
+ * will be copied, otherwise resulting in SSA modification error */
+ if (load->refd) {
+ tree load_rhs = gimple_assign_rhs1(load->ssa_var_def);
+ tree load_new_ssa = make_ssa_name(TREE_TYPE(load_rhs), NULL);
+ gimple* load_new_stmt = gimple_build_assign(load_new_ssa, load_rhs);
+ load->ssa_var_def = load_new_stmt;
+ return;
+ }
+ tree load_rhs = gimple_assign_rhs1(load->ssa_var_def);
+ tree load_rhs_type = build_pointer_type(TREE_TYPE(load_rhs));
+
+ tree load_new_ssa = make_ssa_name(load_rhs_type, NULL);
+ tree load_refd_rhs = build1(ADDR_EXPR, load_rhs_type, load_rhs);
+ gimple* load_new_stmt = gimple_build_assign(load_new_ssa, load_refd_rhs);
+
+ load->ssa_var_def = load_new_stmt;
+ load->refd = true;
+}
+
+static int compare_icmp_offset(const void* p1, const void* p2) {
+ auto const& A = *static_cast<const icmp*>(p1);
+ auto const& B = *static_cast<const icmp*>(p2);
+
+ if (wi::to_widest(A.lhs.offset) < wi::to_widest(B.lhs.offset)) return -1;
+ if (wi::to_widest(A.lhs.offset) > wi::to_widest(B.lhs.offset)) return +1;
+ return 0;
+}
+
+/* === Core pass logic === */
+
+/*
+ * Groups cmps by:
+ * - Base address (tree) of the data being compared
+ * - Consecutivity, so no interleaved compares with different base, or non-int
+ * type, to preserve compare order. Does not affect merging for default
+ * operator== since cmps are given in decleration order.
+ *
+ * Before merging any two integral comparisons A and B in a cluster for which:
+ * A.base == B.base && A.offset+A.size==B.offset
+ * in the left and right-hand sides of the comparisons respectively.
+ */
+static vec<icmp> simplify_icmps(vec<icmp>& cmps) {
+ /* Apply the phi true value to all cmps, so it is easily available
+ * after merging of comparisons has reordered cmps.
+ * phi_true_val may be NULL in case outgoing edge of last cmp is not bb_phi*/
+ if (cmps.last().phi_true_val != NULL) {
+ for (size_t i = 0; i < cmps.length() - 1; ++i) {
+ gcc_assert(cmps[i].phi_true_val == NULL_TREE);
+ cmps[i].phi_true_val = cmps.last().phi_true_val;
+ }
+ }
+ vec<vec<icmp>> clusters = vNULL;
+ clusters.reserve(cmps.length());
+
+ /* Group by base tree equivalence and consecutivity */
+ for (size_t i = 0; i < cmps.length(); ++i) {
+ bool same_base = false;
+ if (clusters.length() > 0 && cmps[i].is_int_cmp &&
+ (i == 0 || cmps[i - 1].is_int_cmp)) {
+ for (long long j = clusters.length() - 1; j >= 0; --j) {
+ vec<icmp>* crnt_cluster = &clusters[j];
+ if (crnt_cluster->is_empty()) break;
+ if (operand_equal_p((*crnt_cluster)[0].lhs.base, cmps[i].lhs.base,
+ OEP_ADDRESS_OF) &&
+ operand_equal_p((*crnt_cluster)[0].rhs.base, cmps[i].rhs.base,
+ OEP_ADDRESS_OF)) {
+ crnt_cluster->safe_push(cmps[i]);
+ same_base = true;
+ break;
+ }
+ if (operand_equal_p((*crnt_cluster)[0].lhs.base, cmps[i].rhs.base,
+ OEP_ADDRESS_OF) &&
+ operand_equal_p((*crnt_cluster)[0].rhs.base, cmps[i].lhs.base,
+ OEP_ADDRESS_OF)) {
+ crnt_cluster->safe_push(cmps[i]);
+ same_base = true;
+ break;
+ }
+ }
+ }
+ if (!same_base) {
+ clusters.quick_push({});
+ clusters.last().safe_push(cmps[i]);
+ }
+ }
+
+ vec<icmp> result = vNULL;
+ result.reserve(cmps.length());
+
+ for (size_t j = 0; j < clusters.length(); ++j) {
+ vec<icmp>* crnt_cluster = &clusters[j];
+ /* Sort by cmp offsets in increasing order.
+ * Widest_int is not trivially copyable, which qsort relies on (and
+ * asserts), so we store offsets/sizes as trees. */
+ crnt_cluster->qsort(compare_icmp_offset);
+
+ icmp* current = &(*crnt_cluster)[0];
+ for (size_t i = 1; i < crnt_cluster->length(); ++i) {
+ icmp* next = &(*crnt_cluster)[i];
+
+ /* Note: This code would fail at merging overlapping compares */
+ bool contiguous_lhs = (wi::to_widest(current->lhs.offset) +
+ wi::to_widest(current->lhs.size) ==
+ wi::to_widest(next->lhs.offset));
+ bool contiguous_rhs = (wi::to_widest(current->rhs.offset) +
+ wi::to_widest(current->rhs.size) ==
+ wi::to_widest(next->rhs.offset));
+
+ /* Merge consecutive compares */
+ if (contiguous_lhs && contiguous_rhs) {
+ current->lhs.size =
+ wide_int_to_tree(TREE_TYPE(current->lhs.size),
+ wi::add(wi::to_widest(current->lhs.size),
+ wi::to_widest(next->lhs.size)));
+ current->rhs.size =
+ wide_int_to_tree(TREE_TYPE(current->rhs.size),
+ wi::add(wi::to_widest(current->rhs.size),
+ wi::to_widest(next->rhs.size)));
+ } else {
+ result.safe_push(*current);
+ current = next;
+ }
+ }
+ result.quick_push(*current);
+ }
+
+ return result.copy();
+}
+
+/* Uses input cmp to build field SSA's, memcmp, and conditional,
+ * then inserted into bb_current */
+static gimple* apply_cmp_to_bb(basic_block bb_current, icmp* cmp) {
+ gimple_seq seq = NULL;
+ gimple* cond_stmt;
+ if (!cmp->is_int_cmp) {
+ /* Get COMPONENT/MEM REF used in comparison */
+ tree lhs_ssadef_rhs = gimple_assign_rhs1(cmp->lhs.ssa_var_def);
+ tree rhs_ssadef_rhs = gimple_assign_rhs1(cmp->rhs.ssa_var_def);
+
+ /* We reconstruct and move !is_int_cmp stmts,
+ * replace SSA name to prevent SSA modification error */
+ tree new_lhs_ssa = make_ssa_name(TREE_TYPE(lhs_ssadef_rhs), NULL);
+ tree new_rhs_ssa = make_ssa_name(TREE_TYPE(rhs_ssadef_rhs), NULL);
+
+ /* Copy original statements with new SSA's */
+ cmp->lhs.ssa_var_def = gimple_build_assign(new_lhs_ssa, lhs_ssadef_rhs);
+ cmp->rhs.ssa_var_def = gimple_build_assign(new_rhs_ssa, rhs_ssadef_rhs);
+
+ /* Rebuild conditions using new SSA's */
+ tree rebuilt_cond =
+ build2(EQ_EXPR, boolean_type_node, new_lhs_ssa, new_rhs_ssa);
+ cond_stmt = gimple_build_cond_from_tree(rebuilt_cond, NULL_TREE,
NULL_TREE);
+
+ /* Add new replaced SSA statements to sequence */
+ gimple_seq_add_stmt(&seq, cmp->lhs.ssa_var_def);
+ gimple_seq_add_stmt(&seq, cmp->rhs.ssa_var_def);
+ gimple_seq_add_stmt(&seq, cond_stmt);
+ } else {
+ /* Make reference of COMPONENT/MEM REF, replacing SSA's */
+ make_ref_load_rhs(&cmp->lhs);
+ make_ref_load_rhs(&cmp->rhs);
+ gimple* memcmp_lhs_def = cmp->lhs.ssa_var_def;
+ gimple* memcmp_rhs_def = cmp->rhs.ssa_var_def;
+
+ /* Build memcmp call */
+ tree memcmp_res_ssa = make_ssa_name(integer_type_node, NULL);
+ tree memcmp_len =
+ wide_int_to_tree(size_type_node, wi::to_widest(cmp->lhs.size));
+ tree memcmp_lhs_ssa = gimple_assign_lhs(memcmp_lhs_def);
+ tree memcmp_rhs_ssa = gimple_assign_lhs(memcmp_rhs_def);
+ gimple* memcmp_call =
+ gimple_build_call(builtin_decl_implicit(BUILT_IN_MEMCMP_EQ), 3,
+ memcmp_lhs_ssa, memcmp_rhs_ssa, memcmp_len);
+ gimple_call_set_lhs(memcmp_call, memcmp_res_ssa);
+
+ /* Add condition comparing result of memcmp to 0 */
+ tree zero = build_int_cst(integer_type_node, 0);
+ tree memcmp_cond = build2(EQ_EXPR, boolean_type_node, memcmp_res_ssa,
zero);
+ cond_stmt = gimple_build_cond_from_tree(memcmp_cond, NULL_TREE, NULL_TREE);
+
+ gimple_seq_add_stmt(&seq, memcmp_lhs_def);
+ gimple_seq_add_stmt(&seq, memcmp_rhs_def);
+ gimple_seq_add_stmt(&seq, memcmp_call);
+ gimple_seq_add_stmt(&seq, cond_stmt);
+ }
+
+ gimple_stmt_iterator gsi_crnt = gsi_last_bb(bb_current);
+ gsi_insert_seq_before(&gsi_crnt, seq, GSI_CONTINUE_LINKING);
+ return cond_stmt;
+}
+
+/*
+ * Takes structure like:
+ *
+ *->cmp_bbs[0]--eq---> bb_current --+
+ * \ \
+ * ne \
+ * \ v
+ * +-------------------------> bb_phi
+ *
+ * Splits bb_current (which should contain no statements), builds
+ * a memcmp statement and condition from the passed
+ * icmp, and adds them to predecessor of the splitted block.
+ * Edges are then added to get:
+ *
+ *->cmp_bbs[0]--eq---> cmp_bbs[1]--eq---> bb_current
+ * \ \ \
+ * ne ne \
+ * \ \ v
+ * +-----------------------+-------------> bb_phi
+ *
+ *
+ * Note: when is_last_cmp is set, the eq/ne edges on the newly added comparison
+ * block are switched, so bb_phi assigns phi_true_val for the last comparison
+ * block, and phi_false_val for the last empty bb (should be bb_current if
+ *is_last_cmp is set).
+ *
+ */
+static basic_block apply_cmp_and_split(basic_block bb_phi,
+ basic_block bb_current, icmp* cmp,
+ bool is_last_cmp) {
+ /* Add reference loads, memcmp, and condition to bb_current */
+ gimple* cond_stmt = apply_cmp_to_bb(bb_current, cmp);
+ edge e_end, e_split;
+ e_split = split_block(bb_current, cond_stmt);
+ e_split->flags &= ~EDGE_FALLTHRU;
+
+ /* e_split->dest will be next block in cmp chain if !is_last_cmp, otherwise
+ * empty falthru block for false edge. */
+ e_split->flags |= is_last_cmp ? EDGE_FALSE_VALUE : EDGE_TRUE_VALUE;
+
+ /* Add flow into phi block */
+ e_end = find_edge(bb_current, bb_phi);
+ if (e_end != NULL) remove_edge(e_end);
+ e_end = make_edge(bb_current, bb_phi,
+ is_last_cmp ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE);
+
+ e_end->probability = profile_probability::even();
+ e_split->probability = e_end->probability.invert();
+
+ return e_split->dest;
+}
+
+/* Given discover_bb, find and return all predecessors and successors part
+ * of the same comparison chain */
+static vec<basic_block> discover_cmp_chain_bbs(
+ basic_block discover_bb, hash_set<basic_block>& phi_blocks,
+ basic_block bb_phi) {
+ if (!bb_is_comparison(discover_bb)) {
+ phi_blocks.remove(discover_bb);
+ return {};
+ }
+ auto get_pred_chain_bb = [&bb_phi, &phi_blocks](basic_block bb_crnt) {
+ phi_blocks.remove(bb_crnt);
+ /* Only the first element in a comparison chain may contain multiple
+ * predecessors, so if bb_crnt preds != 1 and is in chain, it is start of
+ * chain */
+ if (!single_pred_p(bb_crnt)) return (basic_block)NULL;
+ basic_block bb_pred = single_pred(bb_crnt);
+ if (!phi_blocks.contains(bb_pred)) return (basic_block)NULL;
+ if (!bb_is_comparison(bb_pred)) return (basic_block)NULL;
+ normalize_bb_condition(bb_pred);
+ /* After condition normalization, should have false edge to phi,
+ * and true edge to bb_crnt, since predecessor cannot be end of chain */
+ edge e;
+ edge_iterator it;
+ FOR_EACH_EDGE(e, it, bb_pred->succs) {
+ if (e->flags & EDGE_TRUE_VALUE) {
+ /* Generally no empty blocks in cmpchain itself, but no harm in
+ * handling the case */
+ if (find_succ_ignore_empties(e->dest) != bb_crnt)
+ return (basic_block)NULL;
+ } else if (e->flags & EDGE_FALSE_VALUE) {
+ /* On false edge, chained comparison blocks should lead to phi */
+ if (find_succ_ignore_empties(e->dest) != bb_phi)
+ return (basic_block)NULL;
+ } else
+ return (basic_block)NULL;
+ }
+ return bb_pred;
+ };
+ auto get_succ_chain_bb = [&bb_phi, &phi_blocks](basic_block bb_crnt) {
+ phi_blocks.remove(bb_crnt);
+ basic_block bb_succ = GET_TRUE_EDGE(bb_crnt->succs)->dest;
+ if (!single_pred_p(bb_succ)) return (basic_block)NULL;
+ if (!phi_blocks.contains(bb_succ)) return (basic_block)NULL;
+ if (!bb_is_comparison(bb_succ)) return (basic_block)NULL;
+ normalize_bb_condition(bb_succ);
+
+ /* Must have only TRUE/FALSE edges, and FALSE must flow into phi block */
+ edge e;
+ edge_iterator it;
+ FOR_EACH_EDGE(e, it, bb_succ->succs) {
+ if (e->flags & EDGE_FALSE_VALUE) {
+ if (find_succ_ignore_empties(e->dest) != bb_phi)
+ return (basic_block)NULL;
+ } else if (!(e->flags & EDGE_TRUE_VALUE))
+ return (basic_block)NULL;
+ }
+ return bb_succ;
+ };
+ vec<basic_block> chain_bbs = vNULL;
+ chain_bbs.reserve(phi_blocks.elements());
+ chain_bbs.quick_push(discover_bb);
+ basic_block crnt_pred = discover_bb;
+ basic_block crnt_succ = discover_bb;
+ while (1) {
+ crnt_pred = get_pred_chain_bb(crnt_pred);
+ if (crnt_pred == NULL) break;
+ /* We return the chained blocks in-order */
+ chain_bbs.quick_insert(0, crnt_pred);
+ }
+ while (1) {
+ crnt_succ = get_succ_chain_bb(crnt_succ);
+ if (crnt_succ == NULL) break;
+ chain_bbs.quick_push(crnt_succ);
+ }
+ return chain_bbs.copy();
+}
+/* For a given phi block, use its phi args to discover comparison chains
+ * that flow into bb_phi */
+static vec<icmpchain> get_icmpchains_phi(basic_block bb_phi) {
+ gphi* phi_stmt = gsi_start_phis(bb_phi).phi();
+ unsigned phi_arg_n = gimple_phi_num_args((gimple*)phi_stmt);
+ /* Set of all blocks flowing into bb_phi, used in chain discovery */
+ hash_set<basic_block> phi_blocks;
+ /* Different chains with same phi bb may have different phi args for false
+ * edge (though not for default operator==) */
+ hash_map<edge, tree> phi_args_mp;
+
+ for (size_t i = 0; i < phi_arg_n; i++) {
+ /* Find basic block current argument originates from */
+ edge bb_incoming_e = find_decision_edge_from_arg(bb_phi, i);
+ if (bb_incoming_e == NULL) continue;
+ tree incoming = gimple_phi_arg_def(phi_stmt, i);
+ if (incoming == NULL_TREE) continue;
+ /* Current implementation cannot handle variable phi args,
+ * but just continue as arg `i` may not be related to chain */
+ if (TREE_CODE_CLASS(TREE_CODE(incoming)) != tcc_constant) continue;
+ phi_args_mp.put(bb_incoming_e, incoming);
+ phi_blocks.add(bb_incoming_e->src);
+ }
+ if (phi_blocks.is_empty()) return {};
+
+ vec<icmpchain> chains = vNULL;
+ chains.reserve(phi_blocks.elements());
+ while (!phi_blocks.is_empty()) {
+ /* Discovering bbs part of same chain as *phi_blocks.begin(), removing
+ * them from phi_blocks upon discovery in discover_cmp_chain_bbs.
+ * Repeat until all chains are found. */
+ vec<basic_block> chain_bbs =
+ discover_cmp_chain_bbs(*phi_blocks.begin(), phi_blocks, bb_phi);
+ if (chain_bbs.is_empty()) continue;
+ vec<icmp> chain_cmps = vNULL;
+ chain_cmps.reserve(chain_bbs.length());
+ for (size_t i = 0; i < chain_bbs.length(); i++) {
+ icmp cmp = get_cmp_bb(chain_bbs[i]);
+ /* Failure to parse rhs of ssa */
+ if (!ICMP_IS_VALID(cmp)) continue;
+
+ tree* phi_true_val = phi_args_mp.get(GET_TRUE_EDGE(chain_bbs[i]->succs));
+ tree* phi_false_val =
+ phi_args_mp.get(GET_FALSE_EDGE(chain_bbs[i]->succs));
+ if (phi_false_val != NULL) {
+ cmp.phi_false_val = *phi_false_val;
+ if (phi_true_val != NULL) cmp.phi_true_val = *phi_true_val;
+ }
+ chain_cmps.quick_push(cmp);
+ }
+ if (chain_cmps.length() <= 1) continue;
+
+ icmpchain chain = {chain_cmps.copy(), NULL, chain_bbs.last(), vNULL};
+ /* Add new chain to result, storing its incoming and outgoing control flows
+ * to be added back later to merged structure */
+ chain.outgoing_edge_dest = GET_TRUE_EDGE(chain_bbs.last()->succs)->dest;
+
+ chain.incoming_edges.reserve(EDGE_COUNT(chain_bbs[0]->preds));
+ edge e;
+ edge_iterator it;
+ FOR_EACH_EDGE(e, it, chain_bbs[0]->preds)
+ chain.incoming_edges.quick_push(e);
+ chains.quick_push(chain);
+ }
+
+ return chains.copy();
+}
+
+/* Removes comparison chain structure flowing into bb_phi,
+ * replacing it with a newly built structure from the input chain */
+static void apply_icmpchain(icmpchain& chain, basic_block bb_phi) {
+ basic_block bb_last = chain.last_bb;
+ edge e_to_empty = split_block(bb_last, gsi_last_bb(bb_last).ptr);
+ basic_block bb_empty = e_to_empty->dest;
+ remove_edge(e_to_empty);
+
+ /* Redirect edges so new chain starts at newly split empty block */
+ for (size_t i = 0; i < chain.incoming_edges.length(); ++i)
+ redirect_edge_succ(chain.incoming_edges[i], bb_empty);
+
+ while (EDGE_COUNT(bb_empty->succs) > 0) remove_edge(EDGE_SUCC(bb_empty, 0));
+
+ /* Original chain structure detached, so now we have:
+ *
+ *-->bb_empty
+ *
+ */
+
+ /*
+ * Then build the new structure up recursively:
+ *
+ * cmp_bbs[0]--ne---> bb_empty ----> ...
+ * \
+ * eq
+ * \
+ * +-------------------------> bb_phi
+ *
+ * ...
+ *
+ * cmp_bbs[0]--eq---> ... --eq--> cmp_bbs[n] ----eq--> bb_empty ---> ...
+ * \ \ \
+ * ne ne ne
+ * \ \ \
+ * +-------------------+-----------+--------------------------> bb_phi
+ */
+ basic_block bb_last_head, bb_crnt_head;
+ bb_last_head = bb_crnt_head = bb_empty;
+ vec<basic_block> new_bbs = vNULL;
+ new_bbs.reserve(chain.cmps.length() + 1);
+ new_bbs.quick_push(bb_empty);
+ for (size_t i = 0; i < chain.cmps.length(); i++) {
+ bb_last_head = bb_crnt_head;
+ bb_crnt_head = apply_cmp_and_split(bb_phi, bb_crnt_head, &chain.cmps[i],
+ i == chain.cmps.length() - 1);
+ new_bbs.quick_push(bb_crnt_head);
+ }
+
+ /* We modify last bb to flow into empty bb on inequality,
+ * which then flows into bb_phi. Not needed but preserves
+ * structure of last cmp block found in operator== comparisons,
+ * in case this affects later optimization passes. */
+ edge e_rem = find_edge(bb_crnt_head, bb_phi);
+ if (e_rem != NULL) remove_edge(e_rem);
+ e_rem = find_edge(bb_last_head, bb_phi);
+ if (e_rem != NULL) remove_edge(e_rem);
+ edge e_reattach =
+ make_edge(bb_last_head, chain.outgoing_edge_dest, EDGE_TRUE_VALUE);
+ edge e_fallthru_phi = make_edge(bb_crnt_head, bb_phi, EDGE_FALLTHRU);
+ e_reattach->probability = profile_probability::even();
+ e_fallthru_phi->probability = profile_probability::always();
+
+ /* Adjust phi node arguments to reflect the new structure */
+ gphi* phi = gsi_start_phis(bb_phi).phi();
+ for (size_t i = 0; i < EDGE_COUNT(bb_phi->preds); ++i) {
+ basic_block e_bb = find_decision_edge_from_arg(bb_phi, i)->src;
+
+ bool in_false_phi_list = false;
+ for (basic_block bb : new_bbs) {
+ if (bb == e_bb) {
+ in_false_phi_list = true;
+ break;
+ }
+ }
+
+ /* Since final may have 2 paths to phi, but true edge will be direct */
+ if (EDGE_PRED(bb_phi, i)->src == bb_last_head)
+ SET_PHI_ARG_DEF(phi, i, chain.cmps.last().phi_true_val);
+ else if (in_false_phi_list)
+ SET_PHI_ARG_DEF(phi, i, chain.cmps.last().phi_false_val);
+ }
+}
+/*
+ * analyze_cmp_chain recognizes this structure:
+ *
+ * chain_bbs[0]--eq--> ... --eq--> chain_bbs[n] ---eq---> ...
+ * \ \ \
+ * ne ne ne
+ * \ \ \
+ * empty bb(s) ------empty bb(s)--empty bb(s)---------------------> bb_phi
+ *
+ * Where "..." can be equal bb_phi, or other blocks, this is helpful when
+ * integer comparisons are interleaved with other comparisons, still allowing
+ * for chain detection.
+ *
+ * It then parses the conditionals in the chain of comparison blocks,
+ * and merges the internal `icmp` representations of comparisons of
consecutive
+ * memory.
+ *
+ * It then detaches the original comparison chain structure from its
+ * predecessors and successors, putting a new "head" block in its place.
+ * Before adding the merged comparisons as __builtin_memcmp's,
+ * by splitting the current "head" block, adding the statements to the
+ * predecessor, and creating new edges, using apply_cmp_and_split:
+ *
+ *
+ * cmp_bbs[0]--ne---> bb_empty ----> ...
+ * \
+ * eq
+ * \
+ * +-------------------------> bb_phi
+ *
+ * Eventually resulting in:
+ *
+ * cmp_bbs[0]--eq---> ... --eq--> cmp_bbs[n] ----eq--> bb_empty ---> ...
+ * \ \ \
+ * ne ne ne
+ * \ \ \
+ * +-------------------+-----------+--------------------------> bb_phi
+ *
+ *
+ * Returns true if original comparison chain structure was replaced.
+ */
+static bool analyze_cmp_chain(basic_block bb_phi) {
+ vec<icmpchain> chains = get_icmpchains_phi(bb_phi);
+ if (chains.is_empty()) return false;
+
+ if (dump_file)
+ fprintf(dump_file, "Discovered %d chain(s)\n", chains.length());
+
+ for (size_t i = 0; i < chains.length(); i++) {
+ size_t orig_cmps_len = chains[i].cmps.length();
+ chains[i].cmps = simplify_icmps(chains[i].cmps);
+ if (chains[i].cmps.length() >= orig_cmps_len) continue;
+ if (dump_file)
+ fprintf(dump_file, "[%zu] Merged struct comparisons %zu -> %u\n", i,
+ orig_cmps_len, chains[i].cmps.length());
+ apply_icmpchain(chains[i], bb_phi);
+ }
+ return true;
+}
+unsigned int pass_default_eq(function* fun) {
+ basic_block bb;
+ FOR_EACH_BB_REVERSE_FN(bb, fun) {
+ if (phi_nodes(bb) == NULL) continue;
+ if (analyze_cmp_chain(bb)) continue;
+ }
+ return TODO_cleanup_cfg | TODO_update_ssa;
+}
+
+}
+
+gimple_opt_pass* make_pass_tree_struct_eq_merge(gcc::context* ctxt) {
+ return new pass_tree_struct_eq_merge(ctxt);
+}
+
+unsigned int pass_tree_struct_eq_merge::execute(function* fun) {
+ if (!builtin_decl_implicit(BUILT_IN_MEMCMP_EQ)) return false;
+
+ if (/* Is default equality function, and/or has some attribute */) return
pass_default_eq(fun);
+
+ return 0;
+}
--
2.34.1
This e-mail and any attachments may contain information that is confidential
and proprietary and otherwise protected from disclosure. If you are not the
intended recipient of this e-mail, do not read, duplicate or redistribute it by
any means. Please immediately delete it and any attachments and notify the
sender that you have received it by mistake. Unintended recipients are
prohibited from taking action on the basis of information in this e-mail or any
attachments. The DRW Companies make no representations that this e-mail or any
attachments are free of computer viruses or other defects.
