1 /* SLP - Pattern matcher on SLP trees
2 Copyright (C) 2020-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
22 #include "coretypes.h"
28 #include "tree-pass.h"
30 #include "optabs-tree.h"
31 #include "insn-config.h"
32 #include "recog.h" /* FIXME: for insn_data */
33 #include "fold-const.h"
34 #include "stor-layout.h"
35 #include "gimple-iterator.h"
37 #include "tree-vectorizer.h"
38 #include "langhooks.h"
39 #include "gimple-walk.h"
41 #include "tree-vector-builder.h"
42 #include "vec-perm-indices.h"
43 #include "gimple-fold.h"
44 #include "internal-fn.h"
46 /* SLP Pattern matching mechanism.
48 This extension to the SLP vectorizer allows one to transform the generated SLP
49 tree based on any pattern. The difference between this and the normal vect
50 pattern matcher is that unlike the former, this matcher allows you to match
51 with instructions that do not belong to the same SSA dominator graph.
53 The only requirement that this pattern matcher has is that you are only
54 only allowed to either match an entire group or none.
56 The pattern matcher currently only allows you to perform replacements to
59 Once the patterns are matched it is one way, these cannot be undone. It is
60 currently not supported to match patterns recursively.
62 To add a new pattern, implement the vect_pattern class and add the type to
67 /*******************************************************************************
69 ******************************************************************************/
71 /* Default implementation of recognize that performs matching, validation and
72 replacement of nodes but that can be overriden if required. */
75 vect_pattern_validate_optab (internal_fn ifn
, slp_tree node
)
77 tree vectype
= SLP_TREE_VECTYPE (node
);
78 if (ifn
== IFN_LAST
|| !vectype
)
81 if (dump_enabled_p ())
82 dump_printf_loc (MSG_NOTE
, vect_location
,
83 "Found %s pattern in SLP tree\n",
84 internal_fn_name (ifn
));
86 if (direct_internal_fn_supported_p (ifn
, vectype
, OPTIMIZE_FOR_SPEED
))
88 if (dump_enabled_p ())
89 dump_printf_loc (MSG_NOTE
, vect_location
,
90 "Target supports %s vectorization with mode %T\n",
91 internal_fn_name (ifn
), vectype
);
95 if (dump_enabled_p ())
98 dump_printf_loc (MSG_NOTE
, vect_location
,
99 "Target does not support vector type for %T\n",
100 SLP_TREE_DEF_TYPE (node
));
102 dump_printf_loc (MSG_NOTE
, vect_location
,
103 "Target does not support %s for vector type "
104 "%T\n", internal_fn_name (ifn
), vectype
);
111 /*******************************************************************************
112 * General helper types
113 ******************************************************************************/
115 /* The COMPLEX_OPERATION enum denotes the possible pair of operations that can
116 be matched when looking for expressions that we are interested matching for
117 complex numbers addition and mla. */
119 typedef enum _complex_operation
: unsigned {
125 } complex_operation_t
;
127 /*******************************************************************************
128 * General helper functions
129 ******************************************************************************/
131 /* Helper function of linear_loads_p that checks to see if the load permutation
132 is sequential and in monotonically increasing order of loads with no gaps.
135 static inline complex_perm_kinds_t
136 is_linear_load_p (load_permutation_t loads
)
138 if (loads
.length() == 0)
142 complex_perm_kinds_t candidates
[4]
149 int valid_patterns
= 4;
150 FOR_EACH_VEC_ELT (loads
, i
, load
)
152 if (candidates
[0] != PERM_UNKNOWN
&& load
!= 1)
154 candidates
[0] = PERM_UNKNOWN
;
157 if (candidates
[1] != PERM_UNKNOWN
&& load
!= 0)
159 candidates
[1] = PERM_UNKNOWN
;
162 if (candidates
[2] != PERM_UNKNOWN
&& load
!= i
)
164 candidates
[2] = PERM_UNKNOWN
;
167 if (candidates
[3] != PERM_UNKNOWN
168 && load
!= (i
% 2 == 0 ? i
+ 1 : i
- 1))
170 candidates
[3] = PERM_UNKNOWN
;
174 if (valid_patterns
== 0)
178 for (i
= 0; i
< sizeof(candidates
); i
++)
179 if (candidates
[i
] != PERM_UNKNOWN
)
180 return candidates
[i
];
185 /* Combine complex_perm_kinds A and B into a new permute kind that describes the
186 resulting operation. */
188 static inline complex_perm_kinds_t
189 vect_merge_perms (complex_perm_kinds_t a
, complex_perm_kinds_t b
)
203 /* Check to see if all loads rooted in ROOT are linear. Linearity is
204 defined as having no gaps between values loaded. */
206 static complex_load_perm_t
207 linear_loads_p (slp_tree_to_load_perm_map_t
*perm_cache
, slp_tree root
)
210 return std::make_pair (PERM_UNKNOWN
, vNULL
);
213 complex_load_perm_t
*tmp
;
215 if ((tmp
= perm_cache
->get (root
)) != NULL
)
218 complex_load_perm_t retval
= std::make_pair (PERM_UNKNOWN
, vNULL
);
219 perm_cache
->put (root
, retval
);
221 /* If it's a load node, then just read the load permute. */
222 if (SLP_TREE_LOAD_PERMUTATION (root
).exists ())
224 retval
.first
= is_linear_load_p (SLP_TREE_LOAD_PERMUTATION (root
));
225 retval
.second
= SLP_TREE_LOAD_PERMUTATION (root
);
226 perm_cache
->put (root
, retval
);
229 else if (SLP_TREE_DEF_TYPE (root
) != vect_internal_def
)
231 retval
.first
= PERM_TOP
;
232 perm_cache
->put (root
, retval
);
236 auto_vec
<load_permutation_t
> all_loads
;
237 complex_perm_kinds_t kind
= PERM_TOP
;
240 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (root
), i
, child
)
242 complex_load_perm_t res
= linear_loads_p (perm_cache
, child
);
243 kind
= vect_merge_perms (kind
, res
.first
);
244 /* Unknown and Top are not valid on blends as they produce no permute. */
246 if (kind
== PERM_UNKNOWN
|| kind
== PERM_TOP
)
248 all_loads
.safe_push (res
.second
);
251 if (SLP_TREE_LANE_PERMUTATION (root
).exists ())
253 lane_permutation_t perm
= SLP_TREE_LANE_PERMUTATION (root
);
254 load_permutation_t nloads
;
255 nloads
.create (SLP_TREE_LANES (root
));
256 nloads
.quick_grow (SLP_TREE_LANES (root
));
257 for (i
= 0; i
< SLP_TREE_LANES (root
); i
++)
258 nloads
[i
] = all_loads
[perm
[i
].first
][perm
[i
].second
];
261 retval
.second
= nloads
;
266 retval
.second
= all_loads
[0];
269 perm_cache
->put (root
, retval
);
274 /* This function attempts to make a node rooted in NODE is linear. If the node
275 if already linear than the node itself is returned in RESULT.
277 If the node is not linear then a new VEC_PERM_EXPR node is created with a
278 lane permute that when applied will make the node linear. If such a
279 permute cannot be created then FALSE is returned from the function.
281 Here linearity is defined as having a sequential, monotically increasing
282 load position inside the load permute generated by the loads reachable from
286 vect_build_swap_evenodd_node (slp_tree node
)
288 /* Attempt to linearise the permute. */
289 vec
<std::pair
<unsigned, unsigned> > zipped
;
290 zipped
.create (SLP_TREE_LANES (node
));
292 for (unsigned x
= 0; x
< SLP_TREE_LANES (node
); x
+=2)
294 zipped
.quick_push (std::make_pair (0, x
+1));
295 zipped
.quick_push (std::make_pair (0, x
));
298 /* Create the new permute node and store it instead. */
299 slp_tree vnode
= vect_create_new_slp_node (1, VEC_PERM_EXPR
);
300 SLP_TREE_LANE_PERMUTATION (vnode
) = zipped
;
301 SLP_TREE_VECTYPE (vnode
) = SLP_TREE_VECTYPE (node
);
302 SLP_TREE_CHILDREN (vnode
).quick_push (node
);
303 SLP_TREE_REF_COUNT (vnode
) = 1;
304 SLP_TREE_LANES (vnode
) = SLP_TREE_LANES (node
);
305 SLP_TREE_REPRESENTATIVE (vnode
) = SLP_TREE_REPRESENTATIVE (node
);
306 SLP_TREE_REF_COUNT (node
)++;
310 /* Checks to see of the expression represented by NODE is a gimple assign with
314 vect_match_expression_p (slp_tree node
, tree_code code
)
317 || !SLP_TREE_REPRESENTATIVE (node
))
320 gimple
* expr
= STMT_VINFO_STMT (SLP_TREE_REPRESENTATIVE (node
));
321 if (!is_gimple_assign (expr
)
322 || gimple_assign_rhs_code (expr
) != code
)
328 /* Check if the given lane permute in PERMUTES matches an alternating sequence
329 of {even odd even odd ...}. This to account for unrolled loops. Further
330 mode there resulting permute must be linear. */
333 vect_check_evenodd_blend (lane_permutation_t
&permutes
,
334 unsigned even
, unsigned odd
)
336 if (permutes
.length () == 0)
339 unsigned val
[2] = {even
, odd
};
341 for (unsigned i
= 0; i
< permutes
.length (); i
++)
342 if (permutes
[i
].first
!= val
[i
% 2]
343 || permutes
[i
].second
!= seed
++)
349 /* This function will match the two gimple expressions representing NODE1 and
350 NODE2 in parallel and returns the pair operation that represents the two
351 expressions in the two statements.
353 If match is successful then the corresponding complex_operation is
354 returned and the arguments to the two matched operations are returned in OPS.
356 If TWO_OPERANDS it is expected that the LANES of the parent VEC_PERM select
357 from the two nodes alternatingly.
359 If unsuccessful then CMPLX_NONE is returned and OPS is untouched.
361 e.g. the following gimple statements
363 stmt 0 _39 = _37 + _12;
364 stmt 1 _6 = _38 - _36;
366 will return PLUS_MINUS along with OPS containing {_37, _12, _38, _36}.
369 static complex_operation_t
370 vect_detect_pair_op (slp_tree node1
, slp_tree node2
, lane_permutation_t
&lanes
,
371 bool two_operands
= true, vec
<slp_tree
> *ops
= NULL
)
373 complex_operation_t result
= CMPLX_NONE
;
375 if (vect_match_expression_p (node1
, MINUS_EXPR
)
376 && vect_match_expression_p (node2
, PLUS_EXPR
)
377 && (!two_operands
|| vect_check_evenodd_blend (lanes
, 0, 1)))
379 else if (vect_match_expression_p (node1
, PLUS_EXPR
)
380 && vect_match_expression_p (node2
, MINUS_EXPR
)
381 && (!two_operands
|| vect_check_evenodd_blend (lanes
, 0, 1)))
383 else if (vect_match_expression_p (node1
, PLUS_EXPR
)
384 && vect_match_expression_p (node2
, PLUS_EXPR
))
386 else if (vect_match_expression_p (node1
, MULT_EXPR
)
387 && vect_match_expression_p (node2
, MULT_EXPR
))
390 if (result
!= CMPLX_NONE
&& ops
!= NULL
)
393 ops
->quick_push (node1
);
394 ops
->quick_push (node2
);
399 /* Overload of vect_detect_pair_op that matches against the representative
400 statements in the children of NODE. It is expected that NODE has exactly
401 two children and when TWO_OPERANDS then NODE must be a VEC_PERM. */
403 static complex_operation_t
404 vect_detect_pair_op (slp_tree node
, bool two_operands
= true,
405 vec
<slp_tree
> *ops
= NULL
)
407 if (!two_operands
&& SLP_TREE_CODE (node
) == VEC_PERM_EXPR
)
410 if (SLP_TREE_CHILDREN (node
).length () != 2)
413 vec
<slp_tree
> children
= SLP_TREE_CHILDREN (node
);
414 lane_permutation_t
&lanes
= SLP_TREE_LANE_PERMUTATION (node
);
416 return vect_detect_pair_op (children
[0], children
[1], lanes
, two_operands
,
420 /*******************************************************************************
421 * complex_pattern class
422 ******************************************************************************/
424 /* SLP Complex Numbers pattern matching.
426 As an example, the following simple loop:
428 double a[restrict N]; double b[restrict N]; double c[restrict N];
430 for (int i=0; i < N; i+=2)
432 c[i] = a[i] - b[i+1];
433 c[i+1] = a[i+1] + b[i];
436 which represents a complex addition on with a rotation of 90* around the
437 argand plane. i.e. if `a` and `b` were complex numbers then this would be the
438 same as `a + (b * I)`.
440 Here the expressions for `c[i]` and `c[i+1]` are independent but have to be
441 both recognized in order for the pattern to work. As an SLP tree this is
444 +--------------------------------+
445 | stmt 0 *_9 = _10; |
446 | stmt 1 *_15 = _16; |
447 +--------------------------------+
451 +--------------------------------+
452 | stmt 0 _10 = _4 - _8; |
453 | stmt 1 _16 = _12 + _14; |
454 | lane permutation { 0[0] 1[1] } |
455 +--------------------------------+
461 +-----| { } |<-----+ +----->| { } --------+
462 | | | +------------------| | |
463 | +-----+ | +-----+ |
466 | +------|------------------+ |
469 +--------------------------+ +--------------------------------+
470 | stmt 0 _8 = *_7; | | stmt 0 _4 = *_3; |
471 | stmt 1 _14 = *_13; | | stmt 1 _12 = *_11; |
472 | load permutation { 1 0 } | | load permutation { 0 1 } |
473 +--------------------------+ +--------------------------------+
475 The pattern matcher allows you to replace both statements 0 and 1 or none at
476 all. Because this operation is a two operands operation the actual nodes
477 being replaced are those in the { } nodes. The actual scalar statements
478 themselves are not replaced or used during the matching but instead the
479 SLP_TREE_REPRESENTATIVE statements are inspected. You are also allowed to
480 replace and match on any number of nodes.
482 Because the pattern matcher matches on the representative statement for the
483 SLP node the case of two_operators it allows you to match the children of the
484 node. This is done using the method `recognize ()`.
488 /* The complex_pattern class contains common code for pattern matchers that work
489 on complex numbers. These provide functionality to allow de-construction and
490 validation of sequences depicting/transforming REAL and IMAG pairs. */
492 class complex_pattern
: public vect_pattern
495 auto_vec
<slp_tree
> m_workset
;
496 complex_pattern (slp_tree
*node
, vec
<slp_tree
> *m_ops
, internal_fn ifn
)
497 : vect_pattern (node
, m_ops
, ifn
)
499 this->m_workset
.safe_push (*node
);
503 void build (vec_info
*);
506 matches (complex_operation_t op
, slp_tree_to_load_perm_map_t
*,
510 /* Create a replacement pattern statement for each node in m_node and inserts
511 the new statement into m_node as the new representative statement. The old
512 statement is marked as being in a pattern defined by the new statement. The
513 statement is created as call to internal function IFN with m_num_args
516 Futhermore the new pattern is also added to the vectorization information
517 structure VINFO and the old statement STMT_INFO is marked as unused while
518 the new statement is marked as used and the number of SLP uses of the new
519 statement is incremented.
521 The newly created SLP nodes are marked as SLP only and will be dissolved
524 The newly created gimple call is returned and the BB remains unchanged.
526 This default method is designed to only match against simple operands where
527 all the input and output types are the same.
531 complex_pattern::build (vec_info
*vinfo
)
533 stmt_vec_info stmt_info
;
536 args
.create (this->m_num_args
);
537 args
.quick_grow_cleared (this->m_num_args
);
540 stmt_vec_info call_stmt_info
;
541 gcall
*call_stmt
= NULL
;
543 /* Now modify the nodes themselves. */
544 FOR_EACH_VEC_ELT (this->m_workset
, ix
, node
)
546 /* Calculate the location of the statement in NODE to replace. */
547 stmt_info
= SLP_TREE_REPRESENTATIVE (node
);
548 gimple
* old_stmt
= STMT_VINFO_STMT (stmt_info
);
549 tree lhs_old_stmt
= gimple_get_lhs (old_stmt
);
550 tree type
= TREE_TYPE (lhs_old_stmt
);
552 /* Create the argument set for use by gimple_build_call_internal_vec. */
553 for (unsigned i
= 0; i
< this->m_num_args
; i
++)
554 args
[i
] = lhs_old_stmt
;
556 /* Create the new pattern statements. */
557 call_stmt
= gimple_build_call_internal_vec (this->m_ifn
, args
);
558 tree var
= make_temp_ssa_name (type
, call_stmt
, "slp_patt");
559 gimple_call_set_lhs (call_stmt
, var
);
560 gimple_set_location (call_stmt
, gimple_location (old_stmt
));
561 gimple_call_set_nothrow (call_stmt
, true);
563 /* Adjust the book-keeping for the new and old statements for use during
564 SLP. This is required to get the right VF and statement during SLP
565 analysis. These changes are created after relevancy has been set for
566 the nodes as such we need to manually update them. Any changes will be
567 undone if SLP is cancelled. */
569 = vinfo
->add_pattern_stmt (call_stmt
, stmt_info
);
571 /* Make sure to mark the representative statement pure_slp and
573 STMT_VINFO_RELEVANT (call_stmt_info
) = vect_used_in_scope
;
574 STMT_SLP_TYPE (call_stmt_info
) = pure_slp
;
576 /* add_pattern_stmt can't be done in vect_mark_pattern_stmts because
577 the non-SLP pattern matchers already have added the statement to VINFO
578 by the time it is called. Some of them need to modify the returned
579 stmt_info. vect_mark_pattern_stmts is called by recog_pattern and it
580 would increase the size of each pattern with boilerplate code to make
582 vect_mark_pattern_stmts (vinfo
, stmt_info
, call_stmt
,
583 SLP_TREE_VECTYPE (node
));
584 STMT_VINFO_SLP_VECT_ONLY (call_stmt_info
) = true;
586 /* Since we are replacing all the statements in the group with the same
587 thing it doesn't really matter. So just set it every time a new stmt
589 SLP_TREE_REPRESENTATIVE (node
) = call_stmt_info
;
590 SLP_TREE_LANE_PERMUTATION (node
).release ();
591 SLP_TREE_CODE (node
) = CALL_EXPR
;
595 /*******************************************************************************
596 * complex_add_pattern class
597 ******************************************************************************/
599 class complex_add_pattern
: public complex_pattern
602 complex_add_pattern (slp_tree
*node
, vec
<slp_tree
> *m_ops
, internal_fn ifn
)
603 : complex_pattern (node
, m_ops
, ifn
)
605 this->m_num_args
= 2;
609 void build (vec_info
*);
611 matches (complex_operation_t op
, slp_tree_to_load_perm_map_t
*,
615 recognize (slp_tree_to_load_perm_map_t
*, slp_tree
*);
618 /* Perform a replacement of the detected complex add pattern with the new
619 instruction sequences. */
622 complex_add_pattern::build (vec_info
*vinfo
)
624 auto_vec
<slp_tree
> nodes
;
625 slp_tree node
= this->m_ops
[0];
626 vec
<slp_tree
> children
= SLP_TREE_CHILDREN (node
);
628 /* First re-arrange the children. */
629 nodes
.create (children
.length ());
630 nodes
.quick_push (children
[0]);
631 nodes
.quick_push (vect_build_swap_evenodd_node (children
[1]));
633 SLP_TREE_CHILDREN (*this->m_node
).truncate (0);
634 SLP_TREE_CHILDREN (*this->m_node
).safe_splice (nodes
);
636 complex_pattern::build (vinfo
);
639 /* Pattern matcher for trying to match complex addition pattern in SLP tree.
641 If no match is found then IFN is set to IFN_LAST.
642 This function matches the patterns shaped as:
644 c[i] = a[i] - b[i+1];
645 c[i+1] = a[i+1] + b[i];
647 If a match occurred then TRUE is returned, else FALSE. The initial match is
648 expected to be in OP1 and the initial match operands in args0. */
651 complex_add_pattern::matches (complex_operation_t op
,
652 slp_tree_to_load_perm_map_t
*perm_cache
,
655 internal_fn ifn
= IFN_LAST
;
657 /* Find the two components. Rotation in the complex plane will modify
665 Rotation 0 and 180 can be handled by normal SIMD code, so we don't need
666 to care about them here. */
667 if (op
== MINUS_PLUS
)
668 ifn
= IFN_COMPLEX_ADD_ROT90
;
669 else if (op
== PLUS_MINUS
)
670 ifn
= IFN_COMPLEX_ADD_ROT270
;
674 /* verify that there is a permute, otherwise this isn't a pattern we
676 gcc_assert (ops
->length () == 2);
678 vec
<slp_tree
> children
= SLP_TREE_CHILDREN ((*ops
)[0]);
680 /* First node must be unpermuted. */
681 if (linear_loads_p (perm_cache
, children
[0]).first
!= PERM_EVENODD
)
684 /* Second node must be permuted. */
685 if (linear_loads_p (perm_cache
, children
[1]).first
!= PERM_ODDEVEN
)
691 /* Attempt to recognize a complex add pattern. */
694 complex_add_pattern::recognize (slp_tree_to_load_perm_map_t
*perm_cache
,
697 auto_vec
<slp_tree
> ops
;
698 complex_operation_t op
699 = vect_detect_pair_op (*node
, true, &ops
);
700 internal_fn ifn
= complex_add_pattern::matches (op
, perm_cache
, &ops
);
701 if (!vect_pattern_validate_optab (ifn
, *node
))
704 return new complex_add_pattern (node
, &ops
, ifn
);
707 /*******************************************************************************
708 * Pattern matching definitions
709 ******************************************************************************/
711 #define SLP_PATTERN(x) &x::recognize
712 vect_pattern_decl_t slp_patterns
[]
714 /* For least amount of back-tracking and more efficient matching
715 order patterns from the largest to the smallest. Especially if they
716 overlap in what they can detect. */
718 SLP_PATTERN (complex_add_pattern
),
722 /* Set the number of SLP pattern matchers available. */
723 size_t num__slp_patterns
= sizeof(slp_patterns
)/sizeof(vect_pattern_decl_t
);