#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "target.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "tree-pass.h"
#include "ssa.h"
#include "optabs-tree.h"
#include "insn-config.h"
#include "recog.h"
#include "fold-const.h"
#include "stor-layout.h"
#include "gimple-iterator.h"
#include "cfgloop.h"
#include "tree-vectorizer.h"
#include "langhooks.h"
#include "gimple-walk.h"
#include "dbgcnt.h"
#include "tree-vector-builder.h"
#include "vec-perm-indices.h"
#include "gimple-fold.h"
#include "internal-fn.h"

Include dependency graph for tree-vect-slp-patterns.cc:

Data Structures
class	complex_pattern

class	complex_add_pattern

class	complex_mul_pattern

class	complex_fms_pattern

class	complex_operations_pattern

class	addsub_pattern

Macros
#define	SLP_PATTERN(x)

Typedefs
typedef enum _complex_operation	complex_operation_t

Enumerations
enum	_complex_operation : unsigned { PLUS_PLUS , MINUS_PLUS , PLUS_MINUS , MULT_MULT , CMPLX_NONE }

enum	_conj_status { CONJ_NONE , CONJ_FST , CONJ_SND }

Functions
static bool	vect_pattern_validate_optab (internal_fn ifn, slp_tree node)

static complex_perm_kinds_t	is_linear_load_p (load_permutation_t loads)

static complex_perm_kinds_t	vect_merge_perms (complex_perm_kinds_t a, complex_perm_kinds_t b)

static complex_perm_kinds_t	linear_loads_p (slp_tree_to_load_perm_map_t *perm_cache, slp_tree root)

static slp_tree	vect_build_swap_evenodd_node (slp_tree node)

static bool	vect_match_expression_p (slp_tree node, tree_code code)

static bool	vect_check_evenodd_blend (lane_permutation_t &permutes, unsigned even, unsigned odd)

static complex_operation_t	vect_detect_pair_op (slp_tree node1, slp_tree node2, lane_permutation_t &lanes, bool two_operands=true, vec< slp_tree > *ops=NULL)

static complex_operation_t	vect_detect_pair_op (slp_tree node, bool two_operands=true, vec< slp_tree > *ops=NULL)

static bool	is_eq_or_top (slp_tree_to_load_perm_map_t *perm_cache, slp_tree op1, complex_perm_kinds_t kind1, slp_tree op2, complex_perm_kinds_t kind2)

static bool	compatible_complex_nodes_p (slp_compat_nodes_map_t compat_cache, slp_tree a, int pa, slp_tree b, int *pb)

static bool	vect_validate_multiplication (slp_tree_to_load_perm_map_t perm_cache, slp_compat_nodes_map_t compat_cache, vec< slp_tree > &left_op, vec< slp_tree > &right_op, bool subtract, enum _conj_status *_status)

static slp_tree	vect_build_combine_node (slp_tree even, slp_tree odd, slp_tree rep)

Variables
vect_pattern_decl_t	slp_patterns []

size_t	num__slp_patterns = ARRAY_SIZE (slp_patterns)

Macro Definition Documentation

◆ SLP_PATTERN

#define SLP_PATTERN ( x )

Value:

&x::recognize

Typedef Documentation

◆ complex_operation_t

typedef enum _complex_operation complex_operation_t

The COMPLEX_OPERATION enum denotes the possible pair of operations that can
be matched when looking for expressions that we are interested matching for
complex numbers addition and mla.

Enumeration Type Documentation

◆ _complex_operation

enum _complex_operation : unsigned

The COMPLEX_OPERATION enum denotes the possible pair of operations that can
be matched when looking for expressions that we are interested matching for
complex numbers addition and mla.

Enumerator
PLUS_PLUS
MINUS_PLUS
PLUS_MINUS
MULT_MULT
CMPLX_NONE

◆ _conj_status

enum _conj_status

Enumerator
CONJ_NONE
CONJ_FST
CONJ_SND

Function Documentation

◆ compatible_complex_nodes_p()

static bool compatible_complex_nodes_p	(	slp_compat_nodes_map_t *	compat_cache,
		slp_tree	a,
		int *	pa,
		slp_tree	b,
		int *	pb )

inlinestatic

◆ is_eq_or_top()

static bool is_eq_or_top	(	slp_tree_to_load_perm_map_t *	perm_cache,
		slp_tree	op1,
		complex_perm_kinds_t	kind1,
		slp_tree	op2,
		complex_perm_kinds_t	kind2 )

inlinestatic

Helper function to check if PERM is KIND or PERM_TOP.

References linear_loads_p(), and PERM_TOP.

Referenced by vect_validate_multiplication().

◆ is_linear_load_p()

static complex_perm_kinds_t is_linear_load_p ( load_permutation_t loads )

inlinestatic

Helper function of linear_loads_p that checks to see if the load permutation
  is sequential and in monotonically increasing order of loads with no gaps.

References candidates, FOR_EACH_VEC_ELT, i, PERM_EVENEVEN, PERM_EVENODD, PERM_ODDEVEN, PERM_ODDODD, and PERM_UNKNOWN.

Referenced by linear_loads_p().

◆ linear_loads_p()

static complex_perm_kinds_t linear_loads_p	(	slp_tree_to_load_perm_map_t *	perm_cache,
		slp_tree	root )

static

Check to see if all loads rooted in ROOT are linear.  Linearity is
defined as having no gaps between values loaded.

References DR_IS_READ, FOR_EACH_VEC_ELT, hash_map< KeyId, Value, Traits >::get(), i, is_linear_load_p(), linear_loads_p(), NULL, PERM_EVENODD, PERM_TOP, PERM_UNKNOWN, hash_map< KeyId, Value, Traits >::put(), SLP_TREE_CHILDREN, SLP_TREE_CODE, SLP_TREE_DEF_TYPE, SLP_TREE_LOAD_PERMUTATION, SLP_TREE_REPRESENTATIVE, STMT_VINFO_DATA_REF, vect_internal_def, and vect_merge_perms().

Referenced by is_eq_or_top(), linear_loads_p(), complex_add_pattern::matches(), complex_fms_pattern::matches(), complex_mul_pattern::matches(), and vect_validate_multiplication().

◆ vect_build_combine_node()

static slp_tree vect_build_combine_node	(	slp_tree	even,
		slp_tree	odd,
		slp_tree	rep )

static

This function combines two nodes containing only even and only odd lanes
  together into a single node which contains the nodes in even/odd order
  by using a lane permute.

  The lanes in EVEN and ODD are duplicated 2 times inside the vectors.
  So for a lanes = 4 EVEN contains {EVEN1, EVEN1, EVEN2, EVEN2}.

  The tree REPRESENTATION is taken from the supplied REP along with the
  vectype which must be the same between all three nodes.

References gcc_assert, SLP_TREE_CHILDREN, SLP_TREE_CODE, SLP_TREE_LANE_PERMUTATION, SLP_TREE_LANES, SLP_TREE_REF_COUNT, SLP_TREE_REPRESENTATIVE, SLP_TREE_VECTYPE, and vect_create_new_slp_node().

Referenced by complex_fms_pattern::build(), and complex_mul_pattern::build().

◆ vect_build_swap_evenodd_node()

static slp_tree vect_build_swap_evenodd_node ( slp_tree node )

static

This function attempts to make a node rooted in NODE is linear.  If the node
if already linear than the node itself is returned in RESULT.

If the node is not linear then a new VEC_PERM_EXPR node is created with a
lane permute that when applied will make the node linear.   If such a
permute cannot be created then FALSE is returned from the function.

Here linearity is defined as having a sequential, monotically increasing
load position inside the load permute generated by the loads reachable from
NODE.

References SLP_TREE_CHILDREN, SLP_TREE_LANE_PERMUTATION, SLP_TREE_LANES, SLP_TREE_REF_COUNT, SLP_TREE_REPRESENTATIVE, SLP_TREE_VECTYPE, and vect_create_new_slp_node().

Referenced by complex_add_pattern::build().

◆ vect_check_evenodd_blend()

static bool vect_check_evenodd_blend	(	lane_permutation_t &	permutes,
		unsigned	even,
		unsigned	odd )

inlinestatic

Check if the given lane permute in PERMUTES matches an alternating sequence
of {even odd even odd ...}.  This to account for unrolled loops.  Further
mode there resulting permute must be linear.

References i.

Referenced by vect_detect_pair_op().

◆ vect_detect_pair_op() [1/2]

static complex_operation_t vect_detect_pair_op	(	slp_tree	node,
		bool	two_operands = true,
		vec< slp_tree > *	ops = NULL )

static

Overload of vect_detect_pair_op that matches against the representative
statements in the children of NODE.  It is expected that NODE has exactly
two children and when TWO_OPERANDS then NODE must be a VEC_PERM.

References CMPLX_NONE, NULL, SLP_TREE_CHILDREN, SLP_TREE_CODE, SLP_TREE_LANE_PERMUTATION, and vect_detect_pair_op().

◆ vect_detect_pair_op() [2/2]

static complex_operation_t vect_detect_pair_op	(	slp_tree	node1,
		slp_tree	node2,
		lane_permutation_t &	lanes,
		bool	two_operands = true,
		vec< slp_tree > *	ops = NULL )

static

This function will match the two gimple expressions representing NODE1 and
  NODE2 in parallel and returns the pair operation that represents the two
  expressions in the two statements.

  If match is successful then the corresponding complex_operation is
  returned and the arguments to the two matched operations are returned in OPS.

  If TWO_OPERANDS it is expected that the LANES of the parent VEC_PERM select
  from the two nodes alternatingly.

  If unsuccessful then CMPLX_NONE is returned and OPS is untouched.

  e.g. the following gimple statements

  stmt 0 _39 = _37 + _12;
  stmt 1 _6 = _38 - _36;

  will return PLUS_MINUS along with OPS containing {_37, _12, _38, _36}.

References CMPLX_NONE, MINUS_PLUS, MULT_MULT, NULL, PLUS_MINUS, PLUS_PLUS, SLP_TREE_CHILDREN, vect_check_evenodd_blend(), and vect_match_expression_p().

Referenced by complex_fms_pattern::matches(), complex_add_pattern::recognize(), complex_fms_pattern::recognize(), complex_mul_pattern::recognize(), complex_operations_pattern::recognize(), and vect_detect_pair_op().

◆ vect_match_expression_p()

static bool vect_match_expression_p	(	slp_tree	node,
		tree_code	code )

inlinestatic

Checks to see of the expression represented by NODE is a gimple assign with
code CODE.

References gimple_assign_rhs_code(), is_gimple_assign(), SLP_TREE_REPRESENTATIVE, and STMT_VINFO_STMT.

Referenced by complex_fms_pattern::matches(), complex_mul_pattern::matches(), addsub_pattern::recognize(), vect_detect_pair_op(), and vect_validate_multiplication().

◆ vect_merge_perms()

static complex_perm_kinds_t vect_merge_perms	(	complex_perm_kinds_t	a,
		complex_perm_kinds_t	b )

inlinestatic

Combine complex_perm_kinds A and B into a new permute kind that describes the
resulting operation.

References a, b, PERM_TOP, and PERM_UNKNOWN.

Referenced by linear_loads_p().

◆ vect_pattern_validate_optab()

static bool vect_pattern_validate_optab	(	internal_fn	ifn,
		slp_tree	node )

static

SLP - Pattern matcher on SLP trees
   Copyright (C) 2020-2025 Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.

SLP Pattern matching mechanism.

 This extension to the SLP vectorizer allows one to transform the generated SLP
 tree based on any pattern.  The difference between this and the normal vect
 pattern matcher is that unlike the former, this matcher allows you to match
 with instructions that do not belong to the same SSA dominator graph.

 The only requirement that this pattern matcher has is that you are only
 only allowed to either match an entire group or none.

 The pattern matcher currently only allows you to perform replacements to
 internal functions.

 Once the patterns are matched it is one way, these cannot be undone.  It is
 currently not supported to match patterns recursively.

 To add a new pattern, implement the vect_pattern class and add the type to
 slp_patterns.

Default implementation of recognize that performs matching, validation and
replacement of nodes but that can be overriden if required.

References direct_internal_fn_supported_p(), dump_enabled_p(), dump_printf_loc(), internal_fn_name(), MSG_NOTE, OPTIMIZE_FOR_SPEED, SLP_TREE_REPRESENTATIVE, SLP_TREE_VECTYPE, STMT_VINFO_STMT, and vect_location.

Referenced by complex_add_pattern::matches(), complex_fms_pattern::matches(), complex_mul_pattern::matches(), and addsub_pattern::recognize().

◆ vect_validate_multiplication()

static bool vect_validate_multiplication	(	slp_tree_to_load_perm_map_t *	perm_cache,
		slp_compat_nodes_map_t *	compat_cache,
		vec< slp_tree > &	left_op,
		vec< slp_tree > &	right_op,
		bool	subtract,
		enum _conj_status *	_status )

inlinestatic

References compatible_complex_nodes_p(), CONJ_FST, CONJ_NONE, CONJ_SND, is_eq_or_top(), linear_loads_p(), PERM_EVENEVEN, PERM_EVENODD, PERM_ODDEVEN, PERM_ODDODD, SLP_TREE_CHILDREN, and vect_match_expression_p().

Referenced by complex_fms_pattern::matches(), and complex_mul_pattern::matches().

Variable Documentation

◆ num__slp_patterns

size_t num__slp_patterns = ARRAY_SIZE (slp_patterns)

Set the number of SLP pattern matchers available.

Referenced by vect_match_slp_patterns_2().

◆ slp_patterns

vect_pattern_decl_t slp_patterns[]

Initial value:

{
  
  SLP_PATTERN (complex_operations_pattern),
 
}

List of supported pattern matchers.

Referenced by vect_match_slp_patterns_2().

Data Structures

Macros

Typedefs

Enumerations

Functions

Variables

Macro Definition Documentation

◆ SLP_PATTERN

Typedef Documentation

◆ complex_operation_t

Enumeration Type Documentation

◆ _complex_operation

◆ _conj_status

Function Documentation

◆ compatible_complex_nodes_p()

◆ is_eq_or_top()

◆ is_linear_load_p()

◆ linear_loads_p()

◆ vect_build_combine_node()

◆ vect_build_swap_evenodd_node()

◆ vect_check_evenodd_blend()

◆ vect_detect_pair_op() [1/2]

◆ vect_detect_pair_op() [2/2]

◆ vect_match_expression_p()

◆ vect_merge_perms()

◆ vect_pattern_validate_optab()

◆ vect_validate_multiplication()

Variable Documentation

◆ num__slp_patterns

◆ slp_patterns