From: Andrei Nichita Tirziu <[email protected]>
The new SLP pattern identifies a MATCH pattern:
- OR-chain (for equality disjunctions): `(p0) || (p1) || ...`,
leaves are `EQ_EXPR`.
- AND-chain (for inequality conjunctions): `(q0) && (q1) && ...`,
leaves are `NE_EXPR`.
For the pattern to be recognized, the leaves (also called "predicates")
must be formed of a common variant and some invariants.
Example (using an array - the variant, and 3 invariants -
the variables `x`, `y`, `z`):
for (int i = 0; i < n; i++)
{
if (a[i] == x || a[i] == y || a[i] == z)
{
...
}
}
If such a pattern is identified, a replacement is also created for it, such
that the GIMPLE expression used by the if-statement, of the form
exp = (a[i] == x || a[i] == y || a[i] == z)
is rewritten as (the actual code is slightly different, but this exemplifies
the main idea):
exp = IFN_MATCH_EQ (a[i], x, y, z)
Using this new node, the vectorizer is able to transform the loop to use
an SVE MATCH instruction instead of the intitial comparisons.
The pattern is enabled through the subsequent commits.
gcc/ChangeLog:
* tree-vect-slp-patterns.cc: New pattern.
Change-Id: Ica57d1297720e4f763d3894af03e0003904883f8
---
gcc/tree-vect-slp-patterns.cc | 565 +++++++++++++++++++++++++++++++++-
1 file changed, 564 insertions(+), 1 deletion(-)
diff --git a/gcc/tree-vect-slp-patterns.cc b/gcc/tree-vect-slp-patterns.cc
index f30b1eb91a35..e2fc9bebd9c9 100644
--- a/gcc/tree-vect-slp-patterns.cc
+++ b/gcc/tree-vect-slp-patterns.cc
@@ -42,6 +42,7 @@ along with GCC; see the file COPYING3. If not see
#include "vec-perm-indices.h"
#include "gimple-fold.h"
#include "internal-fn.h"
+#include <vector>
/* SLP Pattern matching mechanism.
@@ -1705,6 +1706,568 @@ addsub_pattern::build (vec_info *vinfo)
}
}
+/**
+ * Recognize and replace a âmatch-any equalityâ predicate with an IFN.
+ *
+ * Detects the idiom:
+ * - Disjunction of equalities (OR-chain):
+ * `(a == c0) || (a == c1) || ... || (a == ck)`
+ * (the classic âa equals any of the set {c0..ck}â)
+ * - Conjuction of inequalities (AND-chain):
+ * `(a != c0) && (a != c1) && ... && (a != ck)`
+ *
+ * This pattern is useful for loops that contain:
+ * if (x[i] == c0 || x[i] == c1 || ...) { }
+ *
+ * Throughout the comments and code, we use:
+ * - `leaves` or `terms` to denote the structures similar to (a == c0);
+ * - `operand` to refer to `x[i]` or `{c0...ck}`;
+ * - `variant operand` for `x[i]`; this is the variant operand within a
single
+ * iteration;
+ * - `invariant operand` for `{c0...ck}`, which are invariant with respect to
+ * the loop.
+ */
+class match_pattern : public vect_pattern
+{
+private:
+ std::vector<slp_tree> all_terms {};
+
+public:
+ match_pattern (slp_tree* node, internal_fn ifn, std::vector<slp_tree>& terms)
+ : vect_pattern (node, NULL, ifn), all_terms (terms) {};
+
+ /**
+ * Build the replacement statement.
+ *
+ * @param vinfo Vectorizer context.
+ */
+ void build (vec_info *vinfo) final override;
+
+ /**
+ * Check the current SLP node if it matches the MATCH pattern
+ * (see class description for more details).
+ *
+ * @param slp_tree node The SLP node we are analyzing.
+ *
+ * @return An instance of the `match_pattern` class if the pattern
+ * was detected, or NULL otherwise.
+ */
+ static vect_pattern* recognize (slp_tree_to_load_perm_map_t*,
+ slp_compat_nodes_map_t*,
+ slp_tree* node);
+
+ /**
+ * Identify the root SLP node representing an OR/AND predicate chain
+ * and collect all its leaf predicate SLP nodes.
+ *
+ * Typical intended shapes:
+ * - OR-chain (for equality disjunctions): `(p0) || (p1) || ...`,
+ * leaves are `EQ_EXPR`.
+ * - AND-chain (for inequality conjunctions): `(q0) && (q1) && ...`,
+ * leaves are `NE_EXPR`.
+ *
+ * If we have for example this GIMPLE sequence of statements:
+ * _1 = x[i]
+ * _2 = ( _1 == a )
+ * _3 = ( _1 == b )
+ * _4 = ( _1 == c )
+ * _5 = ( _3 || _4 )
+ * _6 = ( _2 || _4 )
+ *
+ * The leaves (sometimes called the predicates) correspond
+ * to `_2`, `_3`, and `_4`.
+ * In the SLP form, this function locates those comparison nodes within the
+ * SLP graph and records their corresponding SLP nodes as the collected
terms.
+ *
+ * @param slp_node The SLP node we are analyzing.
+ * @param terms Output vector that receives all discovered predicate-leaf
+ * SLP nodes (`EQ_EXPR` or `NE_EXPR`).
+ *
+ * @return <True, is_or_chain>, if `slp_node` denotes the root of an
+ * OR/AND chain, <False, False> oterwise.
+ */
+ static std::pair<bool, bool>
+ identify_and_collect_match_terms (slp_tree* slp_node,
+ std::vector<slp_tree>& terms);
+
+ /**
+ * Perform a depth-first walk over an SLP subtree to collect the leaf
+ * SLP nodes corresponding to predicate comparisons (EQ or NE) that form
+ * an OR/AND chain.
+ *
+ * @param node Root SLP node representing the top OR/AND
expression.
+ * @param collected_terms Vector to append the predicate leaf SLP nodes to.
+ * @param is_or_chain When true, collect EQ leaves under ORs, otherwise
+ * collect NE leaves under ANDs.
+ */
+ static bool collect_match_terms (slp_tree node,
+ std::vector<slp_tree>& collected_terms,
+ bool is_or_chain);
+
+ /**
+ * Given a boolean SSA name `pred_ssa` that is produced by some statement,
+ * check whether any of its immediate uses is itself an OR/AND-producing
+ * GIMPLE_ASSIGN. If so, this `pred_ssa` has a parent in the OR/AND chain.
+ *
+ * @param pred_ssa Boolean SSA name to inspect.
+ * @param look_for_or_chain If true, look for OR parents; else
+ * look for AND parents.
+ *
+ * @return True if an OR/AND consumer exists; False otherwise.
+ */
+ static bool has_or_and_parent (tree pred_ssa, bool look_for_or_chain);
+
+private:
+ /**
+ * Determine whether an operand is invariant within the current
+ * vectorization region.
+ *
+ * @param vinfo Vectorization context.
+ * @param term Operand to classify.
+ *
+ * @return True if `term` is invariant, False otherwise.
+ */
+ bool is_term_invariant_operand_inside_for_loop (vec_info* vinfo, tree term);
+
+ /**
+ * Extract the common (variant) operand and the unique invariant candidates
+ * from a set of SLP leaf nodes.
+ *
+ * @param vinfo Vectorization context.
+ * @param terms Vector of SLP leaf nodes representing EQ/NE
+ * comparisons collected from an
+ * OR/AND predicate chain.
+ * @param variant_operand Shared non-invariant SLP operand present in
+ * all predicate leaves.
+ * @param invariant_operands List of SLP operands that are invariant within
+ * the loop and distinct across leaves.
+ *
+ * @return True, if the common variant exists and the other terms are
+ * invariant, False otherwise.
+ */
+ bool identify_match_operands_from_terms (vec_info *vinfo,
+ const std::vector<slp_tree>& terms,
+ slp_tree& variant_operand,
+ std::vector<slp_tree>&
invariant_operands);
+};
+
+void match_pattern::build (vec_info *vinfo)
+{
+ stmt_vec_info current_vec_info = SLP_TREE_REPRESENTATIVE (*m_node);
+ const gimple* current_stmt = STMT_VINFO_STMT (current_vec_info);
+
+ // Identify the unique invariant operands.
+ std::vector<slp_tree> invariant_operands {};
+
+ // The non-invariant side that must be the same across all leaves.
+ slp_tree variant_operand = nullptr;
+
+ // Collect all operands.
+ if (!identify_match_operands_from_terms (vinfo, all_terms,
+ variant_operand, invariant_operands))
+ {
+ return;
+ }
+
+ // Only at this point we know that the pattern fully matches.
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "Found SLP MATCH pattern starting from statement %G",
+ current_stmt);
+
+ /* The first element will be a boolean mask, and the second will
+ be an integer vector (we know this from all previous checks). */
+ const tree_pair ifn_types = tree_pair (SLP_TREE_VECTYPE (*m_node),
+ SLP_TREE_VECTYPE (variant_operand));
+
+ // Check if the backend supports a direct optab for this internal function.
+ if (!direct_internal_fn_supported_p (m_ifn, ifn_types, OPTIMIZE_FOR_SPEED))
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "SLP MATCH pattern: %s is not supported by an optab. "
+ "Aborting transformation\n",
+ internal_fn_name (m_ifn));
+
+ return;
+ }
+
+ // Create a new SLP node to hold all invariants as scalar operands.
+ slp_tree invariant_node = vect_create_new_slp_node (0, CONSTRUCTOR);
+ SLP_TREE_DEF_TYPE (invariant_node) = vect_external_def;
+ SLP_TREE_VECTYPE (invariant_node) = SLP_TREE_VECTYPE (variant_operand);
+ SLP_TREE_REPRESENTATIVE (invariant_node) = nullptr;
+
+ /* At this point, we know that we have a vector mode and we are
+ interested in how many elements we can pack in a segment
+ (usually 128 bits long). */
+ const unsigned int lanes_in_segment =
+ GET_MODE_NUNITS (vinfo->vector_mode).coeffs[0];
+
+ // We can't fit more invariants than the number of lanes in a segment.
+ if (lanes_in_segment < invariant_operands.size ())
+ {
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "SLP MATCH pattern: Too many invariants (got %d "
+ "invariants, maximum for the current data type was %d)."
+ "Aborting transformation\n",
+ invariant_operands.size (),
+ lanes_in_segment);
+
+ return;
+ }
+
+ const std::size_t number_invariants = invariant_operands.size ();
+
+ /* Most likely, the number of invariants won't match the number of lanes,
+ so we have to fill the lanes in a circular way.
+ The lanes can't just be left empty, since we would then match with zero,
+ which isn't necessarily among our invariants. */
+ for (unsigned int i = 0; i < lanes_in_segment; i++)
+ {
+ const tree scalar_invariant =
+ SLP_TREE_SCALAR_OPS (invariant_operands[i % number_invariants])[0];
+ SLP_TREE_SCALAR_OPS (invariant_node).safe_push (scalar_invariant);
+ }
+
+ /* We need a value here, that ensures that the
+ scalar operands end up vectorized. */
+ SLP_TREE_LANES (invariant_node) = 1;
+
+ /* Build a dummy IFN (the IFN will get its proper arguments
+ in vectorizable_call). */
+ auto_vec<tree> ifn_args {};
+ tree dummy_arg_type = TREE_TYPE (gimple_get_lhs (current_stmt));
+ tree dummy_arg = fold_convert (dummy_arg_type, integer_zero_node);
+
+ ifn_args.safe_push (dummy_arg);
+ ifn_args.safe_push (dummy_arg);
+
+ gcall *ifn_call = gimple_build_call_internal_vec (m_ifn, ifn_args);
+
+ // Create an SSA LHS of the vector mask type and attach it to the call.
+ const tree lhs = make_temp_ssa_name (SLP_TREE_VECTYPE (*m_node),
+ ifn_call,
+ "match_temp_ifn");
+ gimple_call_set_lhs (ifn_call, lhs);
+ gimple_set_location (ifn_call, gimple_location (current_stmt));
+ gimple_call_set_nothrow (ifn_call, true);
+ gimple_set_bb (ifn_call, gimple_bb (current_stmt));
+
+ // Create new vector info for the newly created IFN call.
+ stmt_vec_info new_vec_info = vinfo->add_pattern_stmt (ifn_call,
+ current_vec_info);
+ STMT_VINFO_RELEVANT (new_vec_info) = vect_used_in_scope;
+ STMT_SLP_TYPE (new_vec_info) = pure_slp;
+ STMT_VINFO_VECTYPE (new_vec_info) = SLP_TREE_VECTYPE (*m_node);
+ STMT_VINFO_SLP_VECT_ONLY_PATTERN (new_vec_info) = true;
+
+ /* We'll replace the node's children with the variant operand node
+ and the newly created invariants node. */
+ SLP_TREE_CHILDREN (*m_node).release ();
+
+ SLP_TREE_CHILDREN (*m_node).safe_push (variant_operand);
+ SLP_TREE_REF_COUNT (variant_operand)++;
+
+ SLP_TREE_CHILDREN (*m_node).safe_push (invariant_node);
+ SLP_TREE_REF_COUNT (invariant_node)++;
+
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_NOTE, vect_location,
+ "SLP MATCH pattern: Successfully built replacement for "
+ "statement %G",
+ current_stmt);
+
+ SLP_TREE_REPRESENTATIVE (*m_node) = new_vec_info;
+ SLP_TREE_CODE (*m_node) = CALL_EXPR;
+}
+
+vect_pattern*
+match_pattern::recognize (slp_tree_to_load_perm_map_t*,
slp_compat_nodes_map_t*,
+ slp_tree* node)
+{
+ /* Collect leaf predicate SSA names that are defined by EQ or NE leaves
+ across all lanes. */
+ std::vector<slp_tree> terms {};
+
+ auto [match_success, is_or_chain] =
+ identify_and_collect_match_terms (node, terms);
+ if (!match_success)
+ return nullptr;
+
+ return new match_pattern (node,
+ is_or_chain ? IFN_MATCH_EQ : IFN_MATCH_NE,
+ terms);
+}
+
+std::pair<bool, bool>
+match_pattern::identify_and_collect_match_terms (slp_tree* slp_node,
+ std::vector<slp_tree>& terms)
+{
+ // VecInfo of representative statement of the SLP node.
+ const stmt_vec_info vec_info = SLP_TREE_REPRESENTATIVE (*slp_node);
+ if (!vec_info)
+ return {false, false};
+
+ // The representative scalar statement we're inspecting.
+ const gimple *stmt = STMT_VINFO_STMT (vec_info);
+ if (!stmt)
+ return {false, false};
+
+ // If True, we have an OR chain, otherwise it is an AND chain.
+ bool is_or_chain;
+
+ // We only start from an OR / AND-producing GIMPLE_ASSIGN statement.
+ if (is_gimple_assign (stmt))
+ {
+ const tree_code stmt_code = gimple_assign_rhs_code (stmt);
+
+ // Only consider OR, AND nodes.
+ if (stmt_code == TRUTH_OR_EXPR || stmt_code == BIT_IOR_EXPR)
+ is_or_chain = true;
+ else if (stmt_code == TRUTH_AND_EXPR || stmt_code == BIT_AND_EXPR)
+ is_or_chain = false;
+ else
+ return {false, false};
+
+ // LHS is an SSA name of type bool, produced by this OR / AND node.
+ const tree lhs = gimple_get_lhs (stmt);
+
+ /* Ensure this OR / AND node is the root of the chain
+ (if this is an interior OR / AND, we will skip it). */
+ if (has_or_and_parent (lhs, is_or_chain))
+ return {false, false};
+ }
+ else
+ return {false, false};
+
+ // Ensure the statement has the expected shape, and collect its leaves.
+ if (!collect_match_terms (*slp_node, terms, is_or_chain))
+ return {false, false};
+
+ // We need at least one leaf.
+ if (terms.empty ())
+ return {false, false};
+
+ return {true, is_or_chain};
+}
+
+bool
+match_pattern::collect_match_terms (slp_tree node,
+ std::vector<slp_tree>& collected_terms,
+ bool is_or_chain)
+{
+ const stmt_vec_info vec_info = SLP_TREE_REPRESENTATIVE (node);
+ if (!vec_info)
+ return false;
+
+ const gimple *stmt = STMT_VINFO_STMT (vec_info);
+ if (!is_gimple_assign (stmt))
+ return false;
+
+ const tree lhs = gimple_get_lhs (stmt);
+ /* We only expect SSA names of boolean types here
+ (the result of an OR/AND/EQ/NE assign). */
+ if (TREE_CODE (lhs) != SSA_NAME
+ || TREE_CODE (TREE_TYPE (lhs)) != BOOLEAN_TYPE)
+ return false;
+
+ if (is_or_chain)
+ {
+ switch (gimple_assign_rhs_code (stmt))
+ {
+ case TRUTH_OR_EXPR:
+ case BIT_IOR_EXPR:
+ {
+ /* Internal OR node: recurse into both boolean children.
+ Expect exactly 2 children in the SLP tree for a binary op. */
+ const auto& children = SLP_TREE_CHILDREN (node);
+ if (children.length () != 2)
+ return false;
+
+ return collect_match_terms (children[0], collected_terms, is_or_chain)
+ && collect_match_terms (children[1], collected_terms, is_or_chain);
+ }
+ case EQ_EXPR:
+ // Leaf predicate for the OR case: equality comparison.
+ collected_terms.push_back (node);
+ return true;
+ default:
+ return false;
+ }
+ }
+ else
+ {
+ switch (gimple_assign_rhs_code (stmt))
+ {
+ case TRUTH_AND_EXPR:
+ case BIT_AND_EXPR:
+ {
+ /* Internal AND node: recurse into both boolean children.
+ Expect exactly 2 children in the SLP tree for a binary op. */
+ const auto& children = SLP_TREE_CHILDREN (node);
+ if (children.length () != 2)
+ return false;
+
+ return collect_match_terms (children[0], collected_terms, is_or_chain)
+ && collect_match_terms (children[1], collected_terms, is_or_chain);
+ }
+ case NE_EXPR:
+ // Leaf predicate for the AND case: inequality comparison.
+ collected_terms.push_back (node);
+ return true;
+ default:
+ return false;
+ }
+ }
+}
+
+bool match_pattern::has_or_and_parent (tree pred_ssa, bool look_for_or_chain)
+{
+ imm_use_iterator it;
+ use_operand_p use_p;
+
+ /* Iterate over all immediate consumers of this SSA name
+ (look at the other GIMPLE statements that use this SSA variable). */
+ FOR_EACH_IMM_USE_FAST (use_p, it, pred_ssa)
+ {
+ const gimple *u = USE_STMT (use_p);
+
+ // Only assignments can have an RHS code we care about.
+ if (is_gimple_assign (u))
+ {
+ const tree_code c = gimple_assign_rhs_code (u);
+
+ if (look_for_or_chain)
+ {
+ if (c == TRUTH_OR_EXPR || c == BIT_IOR_EXPR)
+ return true;
+ }
+ else
+ {
+ if (c == TRUTH_AND_EXPR || c == BIT_AND_EXPR)
+ return true;
+ }
+ }
+ }
+
+ return false;
+}
+
+bool
+match_pattern::is_term_invariant_operand_inside_for_loop (vec_info* vinfo,
+ tree term)
+{
+ // GIMPLE minimal invariants.
+ if (is_gimple_min_invariant (term))
+ return true;
+
+ if (TREE_CODE (term) != SSA_NAME)
+ return false;
+
+ /* Will hold how the value enters the vectorization region:
+ - vect_constant_def : compile-time constant
+ - vect_external_def : defined outside the vectorized region
+ - vect_internal_def : defined inside (variant)
+ - vect_induction_def / vect_reduction_def / etc.: also variant for us
+ */
+ enum vect_def_type dt;
+
+ /* Ask the vectorizer to classify the use/definition of `term` relative
+ to `vinfo`. */
+ if (!vect_is_simple_use (term, vinfo, &dt))
+ return false;
+
+ return dt == vect_constant_def || dt == vect_external_def;
+}
+
+bool
+match_pattern::identify_match_operands_from_terms (vec_info *vinfo,
+ const std::vector<slp_tree>&
terms,
+ slp_tree& variant_operand,
+ std::vector<slp_tree>&
invariant_operands)
+{
+ for (const slp_tree& term : terms)
+ {
+ const stmt_vec_info term_vec_info = SLP_TREE_REPRESENTATIVE (term);
+ if (!term_vec_info)
+ return false;
+
+ const gimple* term_node = STMT_VINFO_STMT (term_vec_info);
+ if (!is_gimple_assign (term_node))
+ return false;
+
+ const tree expr_lhs = gimple_assign_rhs1 (term_node);
+ const tree expr_rhs = gimple_assign_rhs2 (term_node);
+
+ // Classify invariance for each side: we require exactly one invariant
side.
+ const bool is_lhs_invariant =
+ is_term_invariant_operand_inside_for_loop (vinfo, expr_lhs);
+ const bool is_rhs_invariant =
+ is_term_invariant_operand_inside_for_loop (vinfo, expr_rhs);
+
+ if (is_lhs_invariant && is_rhs_invariant)
+ return false;
+
+ if (!is_lhs_invariant && !is_rhs_invariant)
+ return false;
+
+ auto &children = SLP_TREE_CHILDREN (term);
+ if (children.length () != 2)
+ return false;
+
+ const slp_tree lhs_node = children[0];
+ const slp_tree rhs_node = children[1];
+
+ /* The invariants is designated as "not common", the variant is
+ "maybe common". */
+ const slp_tree maybe_common_op = is_lhs_invariant ? rhs_node : lhs_node;
+ const slp_tree not_common_op = is_rhs_invariant ? rhs_node : lhs_node;
+
+ if (!variant_operand)
+ {
+ // First leaf establishes the "common" variant operand.
+ variant_operand = maybe_common_op;
+ invariant_operands.push_back (not_common_op);
+ }
+ else
+ {
+ auto is_same_slp_operand = [] (slp_tree a, slp_tree b) -> bool {
+ /* Prefer pointer equality, but fall back to scalar operand equality
+ if we have representatives. */
+ if (a == b)
+ return true;
+ if (a == nullptr || b == nullptr)
+ return false;
+ auto &a_ops = SLP_TREE_SCALAR_OPS (a);
+ auto &b_ops = SLP_TREE_SCALAR_OPS (b);
+ if (a_ops.is_empty () || b_ops.is_empty ())
+ return false;
+ return operand_equal_p (a_ops[0], b_ops[0]);
+ };
+
+ // Enforce that all leaves share the same variant "common" operand.
+ if (!is_same_slp_operand (variant_operand, maybe_common_op))
+ return false;
+
+ // Deduplicate the invariant candidate across leaves.
+ bool operand_exists = false;
+ for (const slp_tree &op : invariant_operands)
+ if (is_same_slp_operand (op, not_common_op))
+ {
+ operand_exists = true;
+ break;
+ }
+
+ if (!operand_exists)
+ invariant_operands.push_back (not_common_op);
+ }
+ }
+
+ return true;
+}
+
/*******************************************************************************
* Pattern matching definitions
******************************************************************************/
@@ -1717,7 +2280,7 @@ vect_pattern_decl_t slp_patterns[]
overlap in what they can detect. */
SLP_PATTERN (complex_operations_pattern),
- SLP_PATTERN (addsub_pattern)
+ SLP_PATTERN (match_pattern)
};
#undef SLP_PATTERN
--
2.52.0
