From fae545fb033970348210c52597a246445efe4160 Mon Sep 17 00:00:00 2001 From: Richard Biener Date: Wed, 25 Mar 2020 14:41:51 +0100 Subject: [PATCH] rewrite hybrid SLP detection This rewrites hybrid SLP detection to be simpler and cope with group size changes in the SLP graph. In particular detection works starting from non-SLP stmts following use->def chains rather than walking the SLP graph and following def->use chains. It's all temporary of course since non-SLP and thus hybrid SLP will go away. 2020-05-05 Richard Biener * tree-vect-slp.c (struct vdhs_data): New. (vect_detect_hybrid_slp): New walker. (vect_detect_hybrid_slp): Rewrite. --- gcc/ChangeLog | 6 ++ gcc/tree-vect-slp.c | 187 +++++++++++++------------------------------- 2 files changed, 62 insertions(+), 131 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 9178e9d14c8..e39ede9077f 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,9 @@ +2020-05-05 Richard Biener + + * tree-vect-slp.c (struct vdhs_data): New. + (vect_detect_hybrid_slp): New walker. + (vect_detect_hybrid_slp): Rewrite. + 2020-05-05 Richard Biener PR ipa/94947 diff --git a/gcc/tree-vect-slp.c b/gcc/tree-vect-slp.c index 45cf491ddd9..f83b568dcc1 100644 --- a/gcc/tree-vect-slp.c +++ b/gcc/tree-vect-slp.c @@ -2566,140 +2566,62 @@ vect_make_slp_decision (loop_vec_info loop_vinfo) return (decided_to_slp > 0); } - -/* Find stmts that must be both vectorized and SLPed (since they feed stmts that - can't be SLPed) in the tree rooted at NODE. Mark such stmts as HYBRID. */ - -static void -vect_detect_hybrid_slp_stmts (loop_vec_info loop_vinfo, slp_tree node, - unsigned i, slp_vect_type stype, - hash_map &visited) +/* Private data for vect_detect_hybrid_slp. */ +struct vdhs_data { - stmt_vec_info stmt_vinfo = SLP_TREE_SCALAR_STMTS (node)[i]; - imm_use_iterator imm_iter; - gimple *use_stmt; - stmt_vec_info use_vinfo; - slp_tree child; - int j; - - /* We need to union stype over the incoming graph edges but we still - want to limit recursion to stay O(N+E). */ - unsigned visited_cnt = ++visited.get_or_insert (node); - gcc_assert (visited_cnt <= node->refcnt); - bool only_edge = (visited_cnt != node->refcnt); - - /* Propagate hybrid down the SLP tree. */ - if (stype == hybrid) - ; - else if (HYBRID_SLP_STMT (stmt_vinfo)) - stype = hybrid; - else if (!only_edge) - { - /* Check if a pure SLP stmt has uses in non-SLP stmts. */ - gcc_checking_assert (PURE_SLP_STMT (stmt_vinfo)); - /* If we get a pattern stmt here we have to use the LHS of the - original stmt for immediate uses. */ - gimple *stmt = vect_orig_stmt (stmt_vinfo)->stmt; - tree def; - if (gimple_code (stmt) == GIMPLE_PHI) - def = gimple_phi_result (stmt); - else - def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF); - if (def) - FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, def) - { - use_vinfo = loop_vinfo->lookup_stmt (use_stmt); - if (!use_vinfo) - continue; - use_vinfo = vect_stmt_to_vectorize (use_vinfo); - if (!STMT_SLP_TYPE (use_vinfo) - && (STMT_VINFO_RELEVANT (use_vinfo) - || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (use_vinfo))) - && !(gimple_code (use_stmt) == GIMPLE_PHI - && STMT_VINFO_DEF_TYPE (use_vinfo) == vect_reduction_def)) - { - if (dump_enabled_p ()) - dump_printf_loc (MSG_NOTE, vect_location, "use of SLP " - "def in non-SLP stmt: %G", use_stmt); - stype = hybrid; - } - } - } - - if (stype == hybrid - && !HYBRID_SLP_STMT (stmt_vinfo)) - { - if (dump_enabled_p ()) - dump_printf_loc (MSG_NOTE, vect_location, "marking hybrid: %G", - stmt_vinfo->stmt); - STMT_SLP_TYPE (stmt_vinfo) = hybrid; - } - - if (!only_edge) - FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (node), j, child) - if (SLP_TREE_DEF_TYPE (child) != vect_external_def - && SLP_TREE_DEF_TYPE (child) != vect_constant_def) - vect_detect_hybrid_slp_stmts (loop_vinfo, child, i, stype, visited); -} + loop_vec_info loop_vinfo; + vec *worklist; +}; -/* Helpers for vect_detect_hybrid_slp walking pattern stmt uses. */ +/* Walker for walk_gimple_op. */ static tree -vect_detect_hybrid_slp_1 (tree *tp, int *, void *data) +vect_detect_hybrid_slp (tree *tp, int *, void *data) { walk_stmt_info *wi = (walk_stmt_info *)data; - loop_vec_info loop_vinfo = (loop_vec_info) wi->info; + vdhs_data *dat = (vdhs_data *)wi->info; if (wi->is_lhs) return NULL_TREE; - stmt_vec_info def_stmt_info = loop_vinfo->lookup_def (*tp); - if (def_stmt_info && PURE_SLP_STMT (def_stmt_info)) + stmt_vec_info def_stmt_info = dat->loop_vinfo->lookup_def (*tp); + if (!def_stmt_info) + return NULL_TREE; + def_stmt_info = vect_stmt_to_vectorize (def_stmt_info); + if (PURE_SLP_STMT (def_stmt_info)) { if (dump_enabled_p ()) dump_printf_loc (MSG_NOTE, vect_location, "marking hybrid: %G", def_stmt_info->stmt); STMT_SLP_TYPE (def_stmt_info) = hybrid; + dat->worklist->safe_push (def_stmt_info); } return NULL_TREE; } -static tree -vect_detect_hybrid_slp_2 (gimple_stmt_iterator *gsi, bool *handled, - walk_stmt_info *wi) -{ - loop_vec_info loop_vinfo = (loop_vec_info) wi->info; - stmt_vec_info use_vinfo = loop_vinfo->lookup_stmt (gsi_stmt (*gsi)); - /* If the stmt is in a SLP instance then this isn't a reason - to mark use definitions in other SLP instances as hybrid. */ - if (! STMT_SLP_TYPE (use_vinfo) - && (STMT_VINFO_RELEVANT (use_vinfo) - || VECTORIZABLE_CYCLE_DEF (STMT_VINFO_DEF_TYPE (use_vinfo))) - && ! (gimple_code (gsi_stmt (*gsi)) == GIMPLE_PHI - && STMT_VINFO_DEF_TYPE (use_vinfo) == vect_reduction_def)) - ; - else - *handled = true; - return NULL_TREE; -} - /* Find stmts that must be both vectorized and SLPed. */ void vect_detect_hybrid_slp (loop_vec_info loop_vinfo) { - unsigned int i; - vec slp_instances = LOOP_VINFO_SLP_INSTANCES (loop_vinfo); - slp_instance instance; - DUMP_VECT_SCOPE ("vect_detect_hybrid_slp"); - /* First walk all pattern stmt in the loop and mark defs of uses as - hybrid because immediate uses in them are not recorded. */ - for (i = 0; i < LOOP_VINFO_LOOP (loop_vinfo)->num_nodes; ++i) + /* All stmts participating in SLP are marked pure_slp, all other + stmts are loop_vect. + First collect all loop_vect stmts into a worklist. */ + auto_vec worklist; + for (unsigned i = 0; i < LOOP_VINFO_LOOP (loop_vinfo)->num_nodes; ++i) { basic_block bb = LOOP_VINFO_BBS (loop_vinfo)[i]; + for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); + gsi_next (&gsi)) + { + gphi *phi = gsi.phi (); + stmt_vec_info stmt_info = loop_vinfo->lookup_stmt (phi); + if (!STMT_SLP_TYPE (stmt_info) && STMT_VINFO_RELEVANT (stmt_info)) + worklist.safe_push (stmt_info); + } for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { @@ -2707,37 +2629,40 @@ vect_detect_hybrid_slp (loop_vec_info loop_vinfo) stmt_vec_info stmt_info = loop_vinfo->lookup_stmt (stmt); if (STMT_VINFO_IN_PATTERN_P (stmt_info)) { - walk_stmt_info wi; - memset (&wi, 0, sizeof (wi)); - wi.info = loop_vinfo; - gimple_stmt_iterator gsi2 - = gsi_for_stmt (STMT_VINFO_RELATED_STMT (stmt_info)->stmt); - walk_gimple_stmt (&gsi2, vect_detect_hybrid_slp_2, - vect_detect_hybrid_slp_1, &wi); - walk_gimple_seq (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info), - vect_detect_hybrid_slp_2, - vect_detect_hybrid_slp_1, &wi); + for (gimple_stmt_iterator gsi2 + = gsi_start (STMT_VINFO_PATTERN_DEF_SEQ (stmt_info)); + !gsi_end_p (gsi2); gsi_next (&gsi2)) + { + stmt_vec_info patt_info + = loop_vinfo->lookup_stmt (gsi_stmt (gsi2)); + if (!STMT_SLP_TYPE (patt_info) + && STMT_VINFO_RELEVANT (patt_info)) + worklist.safe_push (patt_info); + } + stmt_info = STMT_VINFO_RELATED_STMT (stmt_info); } + if (!STMT_SLP_TYPE (stmt_info) && STMT_VINFO_RELEVANT (stmt_info)) + worklist.safe_push (stmt_info); } } - /* Then walk the SLP instance trees marking stmts with uses in - non-SLP stmts as hybrid, also propagating hybrid down the - SLP tree, collecting the above info on-the-fly. */ - for (unsigned j = 0;; ++j) + /* Now we have a worklist of non-SLP stmts, follow use->def chains and + mark any SLP vectorized stmt as hybrid. + ??? We're visiting def stmts N times (once for each non-SLP and + once for each hybrid-SLP use). */ + walk_stmt_info wi; + vdhs_data dat; + dat.worklist = &worklist; + dat.loop_vinfo = loop_vinfo; + memset (&wi, 0, sizeof (wi)); + wi.info = (void *)&dat; + while (!worklist.is_empty ()) { - hash_map visited; - bool any = false; - FOR_EACH_VEC_ELT (slp_instances, i, instance) - if (j < SLP_INSTANCE_GROUP_SIZE (instance)) - { - any = true; - vect_detect_hybrid_slp_stmts (loop_vinfo, - SLP_INSTANCE_TREE (instance), - j, pure_slp, visited); - } - if (!any) - break; + stmt_vec_info stmt_info = worklist.pop (); + /* Since SSA operands are not set up for pattern stmts we need + to use walk_gimple_op. */ + wi.is_lhs = 0; + walk_gimple_op (stmt_info->stmt, vect_detect_hybrid_slp, &wi); } } -- 2.30.2