Line data Source code
1 : /* SLP - Pattern matcher on SLP trees
2 : Copyright (C) 2020-2026 Free Software Foundation, Inc.
3 :
4 : This file is part of GCC.
5 :
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
9 : version.
10 :
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
14 : for more details.
15 :
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/>. */
19 :
20 : #include "config.h"
21 : #include "system.h"
22 : #include "coretypes.h"
23 : #include "backend.h"
24 : #include "target.h"
25 : #include "rtl.h"
26 : #include "tree.h"
27 : #include "gimple.h"
28 : #include "tree-pass.h"
29 : #include "ssa.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"
36 : #include "cfgloop.h"
37 : #include "tree-vectorizer.h"
38 : #include "langhooks.h"
39 : #include "gimple-walk.h"
40 : #include "dbgcnt.h"
41 : #include "tree-vector-builder.h"
42 : #include "vec-perm-indices.h"
43 : #include "gimple-fold.h"
44 : #include "internal-fn.h"
45 :
46 : /* SLP Pattern matching mechanism.
47 :
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.
52 :
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.
55 :
56 : The pattern matcher currently only allows you to perform replacements to
57 : internal functions.
58 :
59 : Once the patterns are matched it is one way, these cannot be undone. It is
60 : currently not supported to match patterns recursively.
61 :
62 : To add a new pattern, implement the vect_pattern class and add the type to
63 : slp_patterns.
64 :
65 : */
66 :
67 : /*******************************************************************************
68 : * vect_pattern class
69 : ******************************************************************************/
70 :
71 : /* Default implementation of recognize that performs matching, validation and
72 : replacement of nodes but that can be overridden if required. */
73 :
74 : static bool
75 5933 : vect_pattern_validate_optab (internal_fn ifn, slp_tree node)
76 : {
77 5933 : tree vectype = SLP_TREE_VECTYPE (node);
78 5933 : if (ifn == IFN_LAST || !vectype)
79 : return false;
80 :
81 5933 : if (dump_enabled_p ())
82 722 : dump_printf_loc (MSG_NOTE, vect_location,
83 : "Found %s pattern in SLP tree\n",
84 : internal_fn_name (ifn));
85 :
86 5933 : if (direct_internal_fn_supported_p (ifn, vectype, OPTIMIZE_FOR_SPEED))
87 : {
88 1114 : if (dump_enabled_p ())
89 24 : dump_printf_loc (MSG_NOTE, vect_location,
90 : "Target supports %s vectorization with mode %T\n",
91 : internal_fn_name (ifn), vectype);
92 : }
93 : else
94 : {
95 4819 : if (dump_enabled_p ())
96 : {
97 698 : if (!vectype)
98 : dump_printf_loc (MSG_NOTE, vect_location,
99 : "Target does not support vector type for %G\n",
100 : STMT_VINFO_STMT (SLP_TREE_REPRESENTATIVE (node)));
101 : else
102 698 : dump_printf_loc (MSG_NOTE, vect_location,
103 : "Target does not support %s for vector type "
104 : "%T\n", internal_fn_name (ifn), vectype);
105 : }
106 : return false;
107 : }
108 : return true;
109 : }
110 :
111 : /*******************************************************************************
112 : * General helper types
113 : ******************************************************************************/
114 :
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. */
118 :
119 : typedef enum _complex_operation : unsigned {
120 : PLUS_PLUS,
121 : MINUS_PLUS,
122 : PLUS_MINUS,
123 : MULT_MULT,
124 : CMPLX_NONE
125 : } complex_operation_t;
126 :
127 : /*******************************************************************************
128 : * General helper functions
129 : ******************************************************************************/
130 :
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.
133 : */
134 :
135 : static inline complex_perm_kinds_t
136 2414 : is_linear_load_p (load_permutation_t loads)
137 : {
138 2414 : if (loads.length() == 0)
139 : return PERM_UNKNOWN;
140 :
141 2414 : if (loads.length () == 1)
142 0 : return loads[0] == 0 ? PERM_EVENEVEN : PERM_ODDODD;
143 :
144 2414 : vec_perm_builder builder;
145 2414 : builder.new_vector (loads.length (), loads.length (), 1);
146 8677 : for (unsigned load : loads)
147 : {
148 6366 : if (load >= loads.length ())
149 2414 : return PERM_UNKNOWN;
150 6263 : builder.quick_push (load);
151 : }
152 :
153 2311 : vec_perm_indices indices (builder, 1, loads.length ());
154 :
155 2311 : if (indices.series_p (0, 2, 1, 2)
156 2311 : && indices.series_p (1, 2, 1, 2))
157 359 : return PERM_ODDODD;
158 :
159 1952 : if (indices.series_p (0, 2, 0, 2)
160 1952 : && indices.series_p (1, 2, 0, 2))
161 1028 : return PERM_EVENEVEN;
162 :
163 924 : if (indices.series_p (0, 1, 0, 1))
164 : return PERM_EVENODD;
165 :
166 877 : if (indices.series_p (0, 2, 1, 2)
167 877 : && indices.series_p (1, 2, 0, 2))
168 852 : return PERM_ODDEVEN;
169 :
170 : return PERM_UNKNOWN;
171 4725 : }
172 :
173 : /* Combine complex_perm_kinds A and B into a new permute kind that describes the
174 : resulting operation. */
175 :
176 : static inline complex_perm_kinds_t
177 19553 : vect_merge_perms (complex_perm_kinds_t a, complex_perm_kinds_t b)
178 : {
179 19553 : if (a == b)
180 : return a;
181 :
182 16995 : if (a == PERM_TOP)
183 : return b;
184 :
185 2066 : if (b == PERM_TOP)
186 : return a;
187 :
188 : return PERM_UNKNOWN;
189 : }
190 :
191 : /* Check to see if all loads rooted in ROOT are linear. Linearity is
192 : defined as having no gaps between values loaded. */
193 :
194 : static complex_perm_kinds_t
195 40257 : linear_loads_p (slp_tree_to_load_perm_map_t *perm_cache, slp_tree root)
196 : {
197 40257 : if (!root)
198 : return PERM_UNKNOWN;
199 :
200 40252 : unsigned i;
201 40252 : complex_perm_kinds_t *tmp;
202 :
203 40252 : if ((tmp = perm_cache->get (root)) != NULL)
204 15717 : return *tmp;
205 :
206 24535 : complex_perm_kinds_t retval = PERM_UNKNOWN;
207 24535 : perm_cache->put (root, retval);
208 :
209 : /* If it's a load node, then just read the load permute. */
210 24535 : if (SLP_TREE_DEF_TYPE (root) == vect_internal_def
211 21195 : && !SLP_TREE_PERMUTE_P (root)
212 18175 : && STMT_VINFO_DATA_REF (SLP_TREE_REPRESENTATIVE (root))
213 3784 : && DR_IS_READ (STMT_VINFO_DATA_REF (SLP_TREE_REPRESENTATIVE (root))))
214 : {
215 3784 : if (SLP_TREE_LOAD_PERMUTATION (root).exists ())
216 2414 : retval = is_linear_load_p (SLP_TREE_LOAD_PERMUTATION (root));
217 : else
218 : retval = PERM_EVENODD;
219 3784 : perm_cache->put (root, retval);
220 3784 : return retval;
221 : }
222 20751 : else if (SLP_TREE_DEF_TYPE (root) != vect_internal_def)
223 : {
224 3340 : retval = PERM_TOP;
225 3340 : perm_cache->put (root, retval);
226 3340 : return retval;
227 : }
228 :
229 : complex_perm_kinds_t kind = PERM_TOP;
230 :
231 : slp_tree child;
232 20058 : FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (root), i, child)
233 : {
234 19553 : complex_perm_kinds_t res = linear_loads_p (perm_cache, child);
235 19553 : kind = vect_merge_perms (kind, res);
236 : /* Unknown and Top are not valid on blends as they produce no permute. */
237 19553 : retval = kind;
238 19553 : if (kind == PERM_UNKNOWN || kind == PERM_TOP)
239 : return retval;
240 : }
241 :
242 505 : retval = kind;
243 :
244 505 : perm_cache->put (root, retval);
245 505 : return retval;
246 : }
247 :
248 :
249 : /* This function attempts to make a node rooted in NODE is linear. If the node
250 : if already linear than the node itself is returned in RESULT.
251 :
252 : If the node is not linear then a new VEC_PERM_EXPR node is created with a
253 : lane permute that when applied will make the node linear. If such a
254 : permute cannot be created then FALSE is returned from the function.
255 :
256 : Here linearity is defined as having a sequential, monotically increasing
257 : load position inside the load permute generated by the loads reachable from
258 : NODE. */
259 :
260 : static slp_tree
261 0 : vect_build_swap_evenodd_node (slp_tree node)
262 : {
263 : /* Attempt to linearise the permute. */
264 0 : lane_permutation_t zipped;
265 0 : zipped.create (SLP_TREE_LANES (node));
266 :
267 0 : for (unsigned x = 0; x < SLP_TREE_LANES (node); x+=2)
268 : {
269 0 : zipped.quick_push (std::make_pair (0, x+1));
270 0 : zipped.quick_push (std::make_pair (0, x));
271 : }
272 :
273 : /* Create the new permute node and store it instead. */
274 0 : slp_tree vnode = vect_create_new_slp_node (1, VEC_PERM_EXPR);
275 0 : SLP_TREE_LANE_PERMUTATION (vnode) = zipped;
276 0 : SLP_TREE_VECTYPE (vnode) = SLP_TREE_VECTYPE (node);
277 0 : SLP_TREE_CHILDREN (vnode).quick_push (node);
278 0 : SLP_TREE_REF_COUNT (vnode) = 1;
279 0 : SLP_TREE_LANES (vnode) = SLP_TREE_LANES (node);
280 0 : SLP_TREE_REF_COUNT (node)++;
281 0 : return vnode;
282 : }
283 :
284 : /* Checks to see of the expression represented by NODE is a gimple assign with
285 : code CODE. */
286 :
287 : static inline bool
288 11076763 : vect_match_expression_p (slp_tree node, code_helper code)
289 : {
290 11076763 : if (!node
291 10128173 : || SLP_TREE_PERMUTE_P (node)
292 10064601 : || !SLP_TREE_REPRESENTATIVE (node))
293 : return false;
294 :
295 9081288 : gimple* expr = STMT_VINFO_STMT (SLP_TREE_REPRESENTATIVE (node));
296 9081288 : if (is_gimple_assign (expr)
297 7755797 : && code.is_tree_code ()
298 16827501 : && gimple_assign_rhs_code (expr) == (tree_code) code)
299 : return true;
300 8529064 : if (is_a <gcall *> (expr)
301 94314 : && !code.is_tree_code ()
302 8529112 : && gimple_call_combined_fn (expr) == (combined_fn) code)
303 6 : return true;
304 :
305 : return false;
306 : }
307 :
308 : /* Check if the given lane permute in PERMUTES matches an alternating sequence
309 : of {even odd even odd ...}. This to account for unrolled loops. Further
310 : mode there resulting permute must be linear. */
311 :
312 : static inline bool
313 8154 : vect_check_evenodd_blend (lane_permutation_t &permutes,
314 : unsigned even, unsigned odd)
315 : {
316 8154 : if (permutes.length () == 0
317 7896 : || permutes.length () % 2 != 0)
318 : return false;
319 :
320 7872 : unsigned val[2] = {even, odd};
321 7872 : unsigned seed = 0;
322 26678 : for (unsigned i = 0; i < permutes.length (); i++)
323 19128 : if (permutes[i].first != val[i % 2]
324 19128 : || permutes[i].second != seed++)
325 : return false;
326 :
327 : return true;
328 : }
329 :
330 : /* This function will match the two gimple expressions representing NODE1 and
331 : NODE2 in parallel and returns the pair operation that represents the two
332 : expressions in the two statements.
333 :
334 : If match is successful then the corresponding complex_operation is
335 : returned and the arguments to the two matched operations are returned in OPS.
336 :
337 : If TWO_OPERANDS it is expected that the LANES of the parent VEC_PERM select
338 : from the two nodes alternatingly.
339 :
340 : If unsuccessful then CMPLX_NONE is returned and OPS is untouched.
341 :
342 : e.g. the following gimple statements
343 :
344 : stmt 0 _39 = _37 + _12;
345 : stmt 1 _6 = _38 - _36;
346 :
347 : will return PLUS_MINUS along with OPS containing {_37, _12, _38, _36}.
348 : */
349 :
350 : static complex_operation_t
351 1656082 : vect_detect_pair_op (slp_tree node1, slp_tree node2, lane_permutation_t &lanes,
352 : bool two_operands = true, vec<slp_tree> *ops = NULL)
353 : {
354 1656082 : complex_operation_t result = CMPLX_NONE;
355 :
356 1656082 : if (vect_match_expression_p (node1, MINUS_EXPR)
357 48717 : && vect_match_expression_p (node2, PLUS_EXPR)
358 1659874 : && (!two_operands || vect_check_evenodd_blend (lanes, 0, 1)))
359 : result = MINUS_PLUS;
360 1652634 : else if (vect_match_expression_p (node1, PLUS_EXPR)
361 164974 : && vect_match_expression_p (node2, MINUS_EXPR)
362 1656996 : && (!two_operands || vect_check_evenodd_blend (lanes, 0, 1)))
363 : result = PLUS_MINUS;
364 1648532 : else if (vect_match_expression_p (node1, PLUS_EXPR)
365 1648532 : && vect_match_expression_p (node2, PLUS_EXPR))
366 : result = PLUS_PLUS;
367 1645485 : else if (vect_match_expression_p (node1, MULT_EXPR)
368 1645485 : && vect_match_expression_p (node2, MULT_EXPR))
369 5307 : result = MULT_MULT;
370 :
371 1656082 : if (result != CMPLX_NONE && ops != NULL)
372 : {
373 15863 : if (two_operands)
374 : {
375 15863 : auto l0node = SLP_TREE_CHILDREN (node1);
376 15863 : auto l1node = SLP_TREE_CHILDREN (node2);
377 :
378 : /* Check if the tree is connected as we expect it. */
379 23877 : if (!((l0node[0] == l1node[0] && l0node[1] == l1node[1])
380 8073 : || (l0node[0] == l1node[1] && l0node[1] == l1node[0])))
381 1656082 : return CMPLX_NONE;
382 : }
383 7850 : ops->safe_push (node1);
384 7850 : ops->safe_push (node2);
385 : }
386 : return result;
387 : }
388 :
389 : /* Overload of vect_detect_pair_op that matches against the representative
390 : statements in the children of NODE. It is expected that NODE has exactly
391 : two children and when TWO_OPERANDS then NODE must be a VEC_PERM. */
392 :
393 : static complex_operation_t
394 5575409 : vect_detect_pair_op (slp_tree node, bool two_operands = true,
395 : vec<slp_tree> *ops = NULL)
396 : {
397 5575409 : if (!two_operands && SLP_TREE_PERMUTE_P (node))
398 : return CMPLX_NONE;
399 :
400 5575409 : if (SLP_TREE_CHILDREN (node).length () != 2)
401 : return CMPLX_NONE;
402 :
403 1656082 : vec<slp_tree> children = SLP_TREE_CHILDREN (node);
404 1656082 : lane_permutation_t &lanes = SLP_TREE_LANE_PERMUTATION (node);
405 :
406 1656082 : return vect_detect_pair_op (children[0], children[1], lanes, two_operands,
407 1656082 : ops);
408 : }
409 :
410 : /*******************************************************************************
411 : * complex_pattern class
412 : ******************************************************************************/
413 :
414 : /* SLP Complex Numbers pattern matching.
415 :
416 : As an example, the following simple loop:
417 :
418 : double a[restrict N]; double b[restrict N]; double c[restrict N];
419 :
420 : for (int i=0; i < N; i+=2)
421 : {
422 : c[i] = a[i] - b[i+1];
423 : c[i+1] = a[i+1] + b[i];
424 : }
425 :
426 : which represents a complex addition on with a rotation of 90* around the
427 : argand plane. i.e. if `a` and `b` were complex numbers then this would be the
428 : same as `a + (b * I)`.
429 :
430 : Here the expressions for `c[i]` and `c[i+1]` are independent but have to be
431 : both recognized in order for the pattern to work. As an SLP tree this is
432 : represented as
433 :
434 : +--------------------------------+
435 : | stmt 0 *_9 = _10; |
436 : | stmt 1 *_15 = _16; |
437 : +--------------------------------+
438 : |
439 : |
440 : v
441 : +--------------------------------+
442 : | stmt 0 _10 = _4 - _8; |
443 : | stmt 1 _16 = _12 + _14; |
444 : | lane permutation { 0[0] 1[1] } |
445 : +--------------------------------+
446 : | |
447 : | |
448 : | |
449 : +-----+ | | +-----+
450 : | | | | | |
451 : +-----| { } |<-----+ +----->| { } --------+
452 : | | | +------------------| | |
453 : | +-----+ | +-----+ |
454 : | | | |
455 : | | | |
456 : | +------|------------------+ |
457 : | | | |
458 : v v v v
459 : +--------------------------+ +--------------------------------+
460 : | stmt 0 _8 = *_7; | | stmt 0 _4 = *_3; |
461 : | stmt 1 _14 = *_13; | | stmt 1 _12 = *_11; |
462 : | load permutation { 1 0 } | | load permutation { 0 1 } |
463 : +--------------------------+ +--------------------------------+
464 :
465 : The pattern matcher allows you to replace both statements 0 and 1 or none at
466 : all. Because this operation is a two operands operation the actual nodes
467 : being replaced are those in the { } nodes. The actual scalar statements
468 : themselves are not replaced or used during the matching but instead the
469 : SLP_TREE_REPRESENTATIVE statements are inspected. You are also allowed to
470 : replace and match on any number of nodes.
471 :
472 : Because the pattern matcher matches on the representative statement for the
473 : SLP node the case of two_operators it allows you to match the children of the
474 : node. This is done using the method `recognize ()`.
475 :
476 : */
477 :
478 : /* The complex_pattern class contains common code for pattern matchers that work
479 : on complex numbers. These provide functionality to allow de-construction and
480 : validation of sequences depicting/transforming REAL and IMAG pairs. */
481 :
482 : class complex_pattern : public vect_pattern
483 : {
484 : protected:
485 : auto_vec<slp_tree> m_workset;
486 : stmt_vec_info m_rep;
487 :
488 32 : complex_pattern (slp_tree *node, vec<slp_tree> *m_ops, internal_fn ifn)
489 64 : : vect_pattern (node, m_ops, ifn)
490 : {
491 : /* ??? We should not have to guess here, analysis should have
492 : it and pass it as CTOR argument. */
493 32 : if (SLP_TREE_PERMUTE_P (*node))
494 32 : m_rep = SLP_TREE_REPRESENTATIVE (SLP_TREE_CHILDREN (*node)[0]);
495 : else
496 0 : m_rep = SLP_TREE_REPRESENTATIVE (*node);
497 32 : this->m_workset.safe_push (*node);
498 32 : }
499 :
500 : void build_common (vec_info *);
501 :
502 : public:
503 : static internal_fn
504 : matches (complex_operation_t op, slp_tree_to_load_perm_map_t *, slp_tree *,
505 : vec<slp_tree> *);
506 : };
507 :
508 : /* Create a replacement pattern statement for each node in m_node and inserts
509 : the new statement into m_node as the new representative statement. The old
510 : statement is marked as being in a pattern defined by the new statement. The
511 : statement is created as call to internal function IFN with m_num_args
512 : arguments.
513 :
514 : Furthermore the new pattern is also added to the vectorization information
515 : structure VINFO and the old statement STMT_INFO is marked as unused while
516 : the new statement is marked as used and the number of SLP uses of the new
517 : statement is incremented.
518 :
519 : The newly created SLP nodes are marked as SLP only and will be dissolved
520 : if SLP is aborted.
521 :
522 : The newly created gimple call is returned and the BB remains unchanged.
523 :
524 : This default method is designed to only match against simple operands where
525 : all the input and output types are the same.
526 : */
527 :
528 : void
529 32 : complex_pattern::build_common (vec_info *vinfo)
530 : {
531 32 : auto_vec<tree> args;
532 32 : args.create (this->m_num_args);
533 32 : args.quick_grow_cleared (this->m_num_args);
534 32 : slp_tree node;
535 32 : unsigned ix;
536 32 : stmt_vec_info call_stmt_info;
537 32 : gcall *call_stmt = NULL;
538 :
539 : /* Now modify the nodes themselves. */
540 128 : FOR_EACH_VEC_ELT (this->m_workset, ix, node)
541 : {
542 : /* Calculate the location of the statement in NODE to replace. */
543 32 : gimple* old_stmt = STMT_VINFO_STMT (m_rep);
544 32 : tree lhs_old_stmt = gimple_get_lhs (old_stmt);
545 32 : tree type = TREE_TYPE (lhs_old_stmt);
546 :
547 : /* Create the argument set for use by gimple_build_call_internal_vec. */
548 112 : for (unsigned i = 0; i < this->m_num_args; i++)
549 80 : args[i] = lhs_old_stmt;
550 :
551 : /* Create the new pattern statements. */
552 32 : call_stmt = gimple_build_call_internal_vec (this->m_ifn, args);
553 32 : tree var = make_temp_ssa_name (type, call_stmt, "slp_patt");
554 32 : gimple_call_set_lhs (call_stmt, var);
555 32 : gimple_set_location (call_stmt, gimple_location (old_stmt));
556 32 : gimple_call_set_nothrow (call_stmt, true);
557 :
558 : /* Adjust the book-keeping for the new and old statements for use during
559 : SLP. This is required to get the right VF and statement during SLP
560 : analysis. These changes are created after relevancy has been set for
561 : the nodes as such we need to manually update them. Any changes will be
562 : undone if SLP is cancelled. */
563 32 : call_stmt_info
564 32 : = vinfo->add_pattern_stmt (call_stmt, vect_orig_stmt (m_rep));
565 :
566 : /* Make sure to mark the representative statement pure_slp and
567 : relevant and transfer reduction info. */
568 32 : STMT_VINFO_RELEVANT (call_stmt_info) = vect_used_in_scope;
569 32 : STMT_SLP_TYPE (call_stmt_info) = pure_slp;
570 :
571 32 : gimple_set_bb (call_stmt, gimple_bb (m_rep->stmt));
572 32 : STMT_VINFO_VECTYPE (call_stmt_info) = SLP_TREE_VECTYPE (node);
573 :
574 : /* Since we are replacing all the statements in the group with the same
575 : thing it doesn't really matter. So just set it every time a new stmt
576 : is created. */
577 32 : SLP_TREE_REPRESENTATIVE (node) = call_stmt_info;
578 32 : SLP_TREE_LANE_PERMUTATION (node).release ();
579 32 : SLP_TREE_CODE (node) = ERROR_MARK;
580 : }
581 32 : }
582 :
583 : /*******************************************************************************
584 : * complex_add_pattern class
585 : ******************************************************************************/
586 :
587 : class complex_add_pattern : public complex_pattern
588 : {
589 : protected:
590 0 : complex_add_pattern (slp_tree *node, vec<slp_tree> *m_ops, internal_fn ifn)
591 0 : : complex_pattern (node, m_ops, ifn)
592 : {
593 0 : this->m_num_args = 2;
594 : }
595 :
596 : public:
597 : void build (vec_info *) final override;
598 : static internal_fn
599 : matches (complex_operation_t op, slp_tree_to_load_perm_map_t *,
600 : slp_compat_nodes_map_t *, slp_tree *, vec<slp_tree> *);
601 :
602 : static vect_pattern*
603 : recognize (slp_tree_to_load_perm_map_t *, slp_compat_nodes_map_t *,
604 : slp_tree *);
605 :
606 : static vect_pattern*
607 0 : mkInstance (slp_tree *node, vec<slp_tree> *m_ops, internal_fn ifn)
608 : {
609 0 : return new complex_add_pattern (node, m_ops, ifn);
610 : }
611 : };
612 :
613 : /* Perform a replacement of the detected complex add pattern with the new
614 : instruction sequences. */
615 :
616 : void
617 0 : complex_add_pattern::build (vec_info *vinfo)
618 : {
619 0 : SLP_TREE_CHILDREN (*this->m_node).reserve_exact (2);
620 :
621 0 : slp_tree node = this->m_ops[0];
622 0 : vec<slp_tree> children = SLP_TREE_CHILDREN (node);
623 :
624 : /* First re-arrange the children. */
625 0 : SLP_TREE_CHILDREN (*this->m_node)[0] = children[0];
626 0 : SLP_TREE_CHILDREN (*this->m_node)[1] =
627 0 : vect_build_swap_evenodd_node (children[1]);
628 :
629 0 : SLP_TREE_REF_COUNT (SLP_TREE_CHILDREN (*this->m_node)[0])++;
630 0 : SLP_TREE_REF_COUNT (SLP_TREE_CHILDREN (*this->m_node)[1])++;
631 0 : vect_free_slp_tree (this->m_ops[0]);
632 0 : vect_free_slp_tree (this->m_ops[1]);
633 :
634 0 : build_common (vinfo);
635 0 : }
636 :
637 : /* Pattern matcher for trying to match complex addition pattern in SLP tree.
638 :
639 : If no match is found then IFN is set to IFN_LAST.
640 : This function matches the patterns shaped as:
641 :
642 : c[i] = a[i] - b[i+1];
643 : c[i+1] = a[i+1] + b[i];
644 :
645 : If a match occurred then TRUE is returned, else FALSE. The initial match is
646 : expected to be in OP1 and the initial match operands in args0. */
647 :
648 : internal_fn
649 5560194 : complex_add_pattern::matches (complex_operation_t op,
650 : slp_tree_to_load_perm_map_t *perm_cache,
651 : slp_compat_nodes_map_t * /* compat_cache */,
652 : slp_tree *node, vec<slp_tree> *ops)
653 : {
654 5560194 : internal_fn ifn = IFN_LAST;
655 :
656 : /* Find the two components. Rotation in the complex plane will modify
657 : the operations:
658 :
659 : * Rotation 0: + +
660 : * Rotation 90: - +
661 : * Rotation 180: - -
662 : * Rotation 270: + -
663 :
664 : Rotation 0 and 180 can be handled by normal SIMD code, so we don't need
665 : to care about them here. */
666 5560194 : if (op == MINUS_PLUS)
667 : ifn = IFN_COMPLEX_ADD_ROT90;
668 5556783 : else if (op == PLUS_MINUS)
669 : ifn = IFN_COMPLEX_ADD_ROT270;
670 : else
671 : return ifn;
672 :
673 : /* verify that there is a permute, otherwise this isn't a pattern we
674 : we support. */
675 7489 : gcc_assert (ops->length () == 2);
676 :
677 7489 : vec<slp_tree> children = SLP_TREE_CHILDREN ((*ops)[0]);
678 :
679 : /* First node must be unpermuted. */
680 7489 : if (linear_loads_p (perm_cache, children[0]) != PERM_EVENODD)
681 : return IFN_LAST;
682 :
683 : /* Second node must be permuted. */
684 541 : if (linear_loads_p (perm_cache, children[1]) != PERM_ODDEVEN)
685 : return IFN_LAST;
686 :
687 354 : if (!vect_pattern_validate_optab (ifn, *node))
688 354 : return IFN_LAST;
689 :
690 : return ifn;
691 : }
692 :
693 : /* Attempt to recognize a complex add pattern. */
694 :
695 : vect_pattern*
696 0 : complex_add_pattern::recognize (slp_tree_to_load_perm_map_t *perm_cache,
697 : slp_compat_nodes_map_t *compat_cache,
698 : slp_tree *node)
699 : {
700 0 : auto_vec<slp_tree> ops;
701 0 : complex_operation_t op
702 0 : = vect_detect_pair_op (*node, true, &ops);
703 0 : internal_fn ifn
704 0 : = complex_add_pattern::matches (op, perm_cache, compat_cache, node, &ops);
705 0 : if (ifn == IFN_LAST)
706 : return NULL;
707 :
708 0 : return new complex_add_pattern (node, &ops, ifn);
709 0 : }
710 :
711 : /*******************************************************************************
712 : * complex_mul_pattern
713 : ******************************************************************************/
714 :
715 : /* Helper function to check if PERM is KIND or PERM_TOP. */
716 :
717 : static inline bool
718 677 : is_eq_or_top (slp_tree_to_load_perm_map_t *perm_cache,
719 : slp_tree op1, complex_perm_kinds_t kind1,
720 : slp_tree op2, complex_perm_kinds_t kind2)
721 : {
722 677 : complex_perm_kinds_t perm1 = linear_loads_p (perm_cache, op1);
723 677 : if (perm1 != kind1 && perm1 != PERM_TOP)
724 : return false;
725 :
726 258 : complex_perm_kinds_t perm2 = linear_loads_p (perm_cache, op2);
727 258 : if (perm2 != kind2 && perm2 != PERM_TOP)
728 0 : return false;
729 :
730 : return true;
731 : }
732 :
733 : enum _conj_status { CONJ_NONE, CONJ_FST, CONJ_SND };
734 :
735 : static inline bool
736 512 : compatible_complex_nodes_p (slp_compat_nodes_map_t *compat_cache,
737 : slp_tree a, int *pa, slp_tree b, int *pb)
738 : {
739 512 : bool *tmp;
740 512 : std::pair<slp_tree, slp_tree> key = std::make_pair(a, b);
741 512 : if ((tmp = compat_cache->get (key)) != NULL)
742 34 : return *tmp;
743 :
744 478 : compat_cache->put (key, false);
745 :
746 534 : if (SLP_TREE_CHILDREN (a).length () != SLP_TREE_CHILDREN (b).length ())
747 : return false;
748 :
749 474 : if (SLP_TREE_DEF_TYPE (a) != SLP_TREE_DEF_TYPE (b))
750 : return false;
751 :
752 : /* Only internal nodes can be loads, as such we can't check further if they
753 : are externals. */
754 474 : if (SLP_TREE_DEF_TYPE (a) != vect_internal_def)
755 : {
756 94 : unsigned group_size = SLP_TREE_LANES (a);
757 282 : gcc_assert (SLP_TREE_SCALAR_OPS (a).length () == group_size
758 : && SLP_TREE_SCALAR_OPS (b).length () == group_size);
759 286 : for (unsigned i = 0; i < group_size; i++)
760 : {
761 194 : tree op1 = SLP_TREE_SCALAR_OPS (a)[pa[i % 2]];
762 194 : tree op2 = SLP_TREE_SCALAR_OPS (b)[pb[i % 2]];
763 194 : if (!operand_equal_p (op1, op2, 0))
764 : return false;
765 : }
766 :
767 92 : compat_cache->put (key, true);
768 92 : return true;
769 : }
770 :
771 380 : if (SLP_TREE_PERMUTE_P (a) != SLP_TREE_PERMUTE_P (b))
772 : return false;
773 380 : else if (SLP_TREE_PERMUTE_P (a))
774 : ;
775 : else
776 : {
777 380 : auto a_stmt = STMT_VINFO_STMT (SLP_TREE_REPRESENTATIVE (a));
778 380 : auto b_stmt = STMT_VINFO_STMT (SLP_TREE_REPRESENTATIVE (b));
779 :
780 380 : if (gimple_code (a_stmt) != gimple_code (b_stmt))
781 : return false;
782 :
783 : /* code, children, type, externals, loads, constants */
784 380 : if (gimple_num_args (a_stmt) != gimple_num_args (b_stmt))
785 : return false;
786 :
787 : /* At this point, a and b are known to be the same gimple operations. */
788 380 : if (is_gimple_call (a_stmt))
789 : {
790 0 : if (!compatible_calls_p (dyn_cast <gcall *> (a_stmt),
791 : dyn_cast <gcall *> (b_stmt), false))
792 : return false;
793 : }
794 380 : else if (!is_gimple_assign (a_stmt))
795 : return false;
796 : else
797 : {
798 380 : tree_code acode = gimple_assign_rhs_code (a_stmt);
799 380 : tree_code bcode = gimple_assign_rhs_code (b_stmt);
800 380 : if ((acode == REALPART_EXPR || acode == IMAGPART_EXPR)
801 270 : && (bcode == REALPART_EXPR || bcode == IMAGPART_EXPR)
802 650 : && operand_equal_p (TREE_OPERAND (gimple_assign_rhs1 (a_stmt), 0),
803 270 : TREE_OPERAND (gimple_assign_rhs1 (b_stmt), 0)))
804 : return true;
805 :
806 110 : if (acode != bcode)
807 : return false;
808 : }
809 :
810 110 : if (!STMT_VINFO_DATA_REF (SLP_TREE_REPRESENTATIVE (a))
811 84 : || !STMT_VINFO_DATA_REF (SLP_TREE_REPRESENTATIVE (b)))
812 : {
813 78 : for (unsigned i = 0; i < gimple_num_args (a_stmt); i++)
814 : {
815 52 : tree t1 = gimple_arg (a_stmt, i);
816 52 : tree t2 = gimple_arg (b_stmt, i);
817 52 : if (TREE_CODE (t1) != TREE_CODE (t2))
818 : return false;
819 :
820 : /* If SSA name then we will need to inspect the children
821 : so we can punt here. */
822 52 : if (TREE_CODE (t1) == SSA_NAME)
823 38 : continue;
824 :
825 14 : if (!operand_equal_p (t1, t2, 0))
826 : return false;
827 : }
828 : }
829 : else
830 : {
831 84 : auto dr1 = STMT_VINFO_DATA_REF (SLP_TREE_REPRESENTATIVE (a));
832 84 : auto dr2 = STMT_VINFO_DATA_REF (SLP_TREE_REPRESENTATIVE (b));
833 : /* Don't check the last dimension as that's checked by the lineary
834 : checks. This check is also much stricter than what we need
835 : because it doesn't consider loading from adjacent elements
836 : in the same struct as loading from the same base object.
837 : But for now, I'll play it safe. */
838 84 : if (!same_data_refs (dr1, dr2, 1))
839 : return false;
840 : }
841 : }
842 :
843 134 : for (unsigned i = 0; i < SLP_TREE_CHILDREN (a).length (); i++)
844 : {
845 52 : if (!compatible_complex_nodes_p (compat_cache,
846 52 : SLP_TREE_CHILDREN (a)[i], pa,
847 52 : SLP_TREE_CHILDREN (b)[i], pb))
848 : return false;
849 : }
850 :
851 82 : compat_cache->put (key, true);
852 82 : return true;
853 : }
854 :
855 :
856 : /* Check to see if the operands to two multiplies, 2 each in ALL_OPS, match
857 : a complex multiplication or complex multiply-and-accumulate or complex
858 : multiply-and-subtract pattern. Do this using the permute cache PERM_CACHE
859 : and the combination compatibility list COMPAT_CACHE. If the operation is
860 : successful the matching operands are returned in OPS and _STATUS indicates
861 : if the operation matched includes a conjugate of one of the operands. If
862 : the operation succeeds True is returned, otherwise False and the values in
863 : ops are meaningless. */
864 : static inline bool
865 4535 : vect_validate_multiplication (slp_tree_to_load_perm_map_t *perm_cache,
866 : slp_compat_nodes_map_t *compat_cache,
867 : const slp_tree *all_ops,
868 : const unsigned *op_index, bool subtract,
869 : unsigned perm, vec<slp_tree> &ops,
870 : enum _conj_status *_status)
871 : {
872 4535 : enum _conj_status stats = CONJ_NONE;
873 4535 : gcc_assert (perm < 2);
874 :
875 : /* The complex operations can occur in two layouts and two permute sequences
876 : so declare them and re-use them. */
877 4535 : int styles[][4] = { { 0, 2, 1, 3} /* {L1, R1} + {L2, R2}. */
878 : , { 0, 3, 1, 2} /* {L1, R2} + {L2, R1}. */
879 : };
880 :
881 : /* Now for the corresponding permutes that go with these values. */
882 4535 : complex_perm_kinds_t perms[][4]
883 : = { { PERM_EVENEVEN, PERM_ODDODD, PERM_EVENODD, PERM_ODDEVEN }
884 : , { PERM_EVENODD, PERM_ODDEVEN, PERM_EVENEVEN, PERM_ODDODD }
885 : };
886 :
887 : /* These permutes are used during comparisons of externals on which
888 : we require strict equality. */
889 4535 : int cq[][4][2]
890 : = { { { 0, 0 }, { 1, 1 }, { 0, 1 }, { 1, 0 } }
891 : , { { 0, 1 }, { 1, 0 }, { 0, 0 }, { 1, 1 } }
892 : };
893 :
894 : /* Default to style 0, most operations use this one. */
895 4535 : int style = 0;
896 :
897 : /* Create the combined inputs after remapping. */
898 4535 : ops.create (4);
899 27210 : for (unsigned i = 0; i < 4; ++i)
900 18140 : ops.quick_push (all_ops[op_index[i]]);
901 :
902 : /* Check if we have a negate operation, if so absorb the node and continue
903 : looking. */
904 4535 : bool neg0 = vect_match_expression_p (ops[2], NEGATE_EXPR);
905 4535 : bool neg1 = vect_match_expression_p (ops[3], NEGATE_EXPR);
906 :
907 : /* Determine which style we're looking at. We only have different ones
908 : whenever a conjugate is involved. */
909 4535 : if (neg0 && neg1)
910 : ;
911 4535 : else if (neg0)
912 : {
913 1 : ops[2] = SLP_TREE_CHILDREN (ops[2])[0];
914 1 : stats = CONJ_FST;
915 1 : if (subtract)
916 0 : perm = 0;
917 : }
918 4534 : else if (neg1)
919 : {
920 21 : ops[3] = SLP_TREE_CHILDREN (ops[3])[0];
921 21 : stats = CONJ_SND;
922 21 : perm = 1;
923 : }
924 :
925 4535 : *_status = stats;
926 :
927 : /* Extract out the elements to check. */
928 4535 : slp_tree op0 = ops[styles[style][0]];
929 4535 : slp_tree op1 = ops[styles[style][1]];
930 4535 : slp_tree op2 = ops[styles[style][2]];
931 4535 : slp_tree op3 = ops[styles[style][3]];
932 :
933 : /* Do cheapest test first. If failed no need to analyze further. */
934 4535 : if (linear_loads_p (perm_cache, op0) != perms[perm][0]
935 1252 : || linear_loads_p (perm_cache, op1) != perms[perm][1]
936 5212 : || !is_eq_or_top (perm_cache, op2, perms[perm][2], op3, perms[perm][3]))
937 : return false;
938 :
939 258 : return compatible_complex_nodes_p (compat_cache, op0, cq[perm][0], op1,
940 258 : cq[perm][1])
941 460 : && compatible_complex_nodes_p (compat_cache, op2, cq[perm][2], op3,
942 202 : cq[perm][3]);
943 : }
944 :
945 : /* Try to validate LEFT_OP and RIGHT_OP as the operands of a complex
946 : multiplication. Since MULT_EXPR is commutative, try all combinations of
947 : swapping the operands of each multiplication. If a match is found, set OPS
948 : and STATUS for the matching order. */
949 :
950 : static inline bool
951 1215 : vect_validate_multiplication_commutative (slp_tree_to_load_perm_map_t *perm_cache,
952 : slp_compat_nodes_map_t *compat_cache,
953 : vec<slp_tree> &left_op,
954 : vec<slp_tree> &right_op,
955 : bool subtract, vec<slp_tree> &ops,
956 : enum _conj_status *status)
957 : {
958 1215 : unsigned perm = subtract ? 1 : 0;
959 1215 : static const unsigned op_indices[][4] = {
960 : { 0, 1, 2, 3 }, /* (L0 * L1), (R0 * R1). */
961 : { 0, 1, 3, 2 }, /* (L0 * L1), (R1 * R0). */
962 : { 1, 0, 2, 3 }, /* (L1 * L0), (R0 * R1). */
963 : { 1, 0, 3, 2 }, /* (L1 * L0), (R1 * R0). */
964 : };
965 :
966 : /* Only try permutations that swap operands within each MULT_EXPR. Swapping
967 : the two product terms is not valid because the real lane is ordered by a
968 : subtraction. */
969 1215 : slp_tree all_ops[4] = { left_op[0], left_op[1], right_op[0], right_op[1] };
970 5554 : for (unsigned i = 0; i < ARRAY_SIZE (op_indices); ++i)
971 : {
972 4535 : auto_vec<slp_tree> trial_ops;
973 4535 : if (vect_validate_multiplication (perm_cache, compat_cache, all_ops,
974 4535 : op_indices[i], subtract, perm,
975 : trial_ops, status))
976 : {
977 196 : ops.safe_splice (trial_ops);
978 196 : return true;
979 : }
980 4535 : }
981 :
982 : return false;
983 : }
984 :
985 : /* This function combines two nodes containing only even and only odd lanes
986 : together into a single node which contains the nodes in even/odd order
987 : by using a lane permute.
988 :
989 : The lanes in EVEN and ODD are duplicated 2 times inside the vectors.
990 : So for a lanes = 4 EVEN contains {EVEN1, EVEN1, EVEN2, EVEN2}.
991 :
992 : The tree REPRESENTATION is taken from the supplied REP along with the
993 : vectype which must be the same between all three nodes.
994 : */
995 :
996 : static slp_tree
997 32 : vect_build_combine_node (slp_tree even, slp_tree odd, slp_tree rep)
998 : {
999 32 : lane_permutation_t perm;
1000 32 : perm.create (SLP_TREE_LANES (rep));
1001 :
1002 96 : for (unsigned x = 0; x < SLP_TREE_LANES (rep); x+=2)
1003 : {
1004 32 : perm.quick_push (std::make_pair (0, x));
1005 32 : perm.quick_push (std::make_pair (1, x+1));
1006 : }
1007 :
1008 32 : slp_tree vnode = vect_create_new_slp_node (2, VEC_PERM_EXPR);
1009 32 : SLP_TREE_LANE_PERMUTATION (vnode) = perm;
1010 :
1011 32 : SLP_TREE_CHILDREN (vnode).create (2);
1012 32 : SLP_TREE_CHILDREN (vnode).quick_push (even);
1013 32 : SLP_TREE_CHILDREN (vnode).quick_push (odd);
1014 32 : SLP_TREE_REF_COUNT (even)++;
1015 32 : SLP_TREE_REF_COUNT (odd)++;
1016 32 : SLP_TREE_REF_COUNT (vnode) = 1;
1017 :
1018 32 : SLP_TREE_LANES (vnode) = SLP_TREE_LANES (rep);
1019 64 : gcc_assert (perm.length () == SLP_TREE_LANES (vnode));
1020 32 : SLP_TREE_VECTYPE (vnode) = SLP_TREE_VECTYPE (rep);
1021 32 : return vnode;
1022 : }
1023 :
1024 : class complex_mul_pattern : public complex_pattern
1025 : {
1026 : protected:
1027 32 : complex_mul_pattern (slp_tree *node, vec<slp_tree> *m_ops, internal_fn ifn)
1028 64 : : complex_pattern (node, m_ops, ifn)
1029 : {
1030 32 : this->m_num_args = 2;
1031 : }
1032 :
1033 : public:
1034 : void build (vec_info *) final override;
1035 : static internal_fn
1036 : matches (complex_operation_t op, slp_tree_to_load_perm_map_t *,
1037 : slp_compat_nodes_map_t *, slp_tree *, vec<slp_tree> *);
1038 :
1039 : static vect_pattern*
1040 : recognize (slp_tree_to_load_perm_map_t *, slp_compat_nodes_map_t *,
1041 : slp_tree *);
1042 :
1043 : static vect_pattern*
1044 32 : mkInstance (slp_tree *node, vec<slp_tree> *m_ops, internal_fn ifn)
1045 : {
1046 32 : return new complex_mul_pattern (node, m_ops, ifn);
1047 : }
1048 :
1049 : };
1050 :
1051 : /* Pattern matcher for trying to match complex multiply and complex multiply
1052 : and accumulate pattern in SLP tree. If the operation matches then IFN
1053 : is set to the operation it matched and the arguments to the two
1054 : replacement statements are put in m_ops.
1055 :
1056 : If no match is found then IFN is set to IFN_LAST and m_ops is unchanged.
1057 :
1058 : This function matches the patterns shaped as:
1059 :
1060 : double ax = (b[i+1] * a[i]);
1061 : double bx = (a[i+1] * b[i]);
1062 :
1063 : c[i] = c[i] - ax;
1064 : c[i+1] = c[i+1] + bx;
1065 :
1066 : If a match occurred then TRUE is returned, else FALSE. The initial match is
1067 : expected to be in OP1 and the initial match operands in args0. */
1068 :
1069 : internal_fn
1070 5560226 : complex_mul_pattern::matches (complex_operation_t op,
1071 : slp_tree_to_load_perm_map_t *perm_cache,
1072 : slp_compat_nodes_map_t *compat_cache,
1073 : slp_tree *node, vec<slp_tree> *ops)
1074 : {
1075 5560226 : internal_fn ifn = IFN_LAST;
1076 :
1077 5560226 : if (op != MINUS_PLUS)
1078 : return IFN_LAST;
1079 :
1080 : /* It's only valid to form FMAs and MUL with -ffp-contract=fast. */
1081 3443 : if (flag_fp_contract_mode != FP_CONTRACT_FAST
1082 3443 : && FLOAT_TYPE_P (SLP_TREE_VECTYPE (*node)))
1083 : return IFN_LAST;
1084 :
1085 3408 : auto childs = *ops;
1086 3408 : auto l0node = SLP_TREE_CHILDREN (childs[0]);
1087 :
1088 3408 : bool mul0 = vect_match_expression_p (l0node[0], MULT_EXPR);
1089 3408 : bool mul1 = vect_match_expression_p (l0node[1], MULT_EXPR);
1090 3408 : if (!mul0 && !mul1)
1091 : return IFN_LAST;
1092 :
1093 : /* Now operand2+4 may lead to another expression. */
1094 2443 : auto_vec<slp_tree> left_op, right_op;
1095 2443 : slp_tree add0 = NULL;
1096 :
1097 : /* Check if we may be a multiply add. */
1098 2443 : if (!mul0
1099 2443 : && vect_match_expression_p (l0node[0], PLUS_EXPR))
1100 : {
1101 1084 : auto vals = SLP_TREE_CHILDREN (l0node[0]);
1102 : /* Check if it's a multiply, otherwise no idea what this is. */
1103 1084 : if (!(mul0 = vect_match_expression_p (vals[1], MULT_EXPR)))
1104 2443 : return IFN_LAST;
1105 :
1106 : /* Check if the ADD is linear, otherwise it's not valid complex FMA. */
1107 647 : if (linear_loads_p (perm_cache, vals[0]) != PERM_EVENODD)
1108 : return IFN_LAST;
1109 :
1110 30 : left_op.safe_splice (SLP_TREE_CHILDREN (vals[1]));
1111 30 : add0 = vals[0];
1112 : }
1113 : else
1114 1359 : left_op.safe_splice (SLP_TREE_CHILDREN (l0node[0]));
1115 :
1116 1389 : right_op.safe_splice (SLP_TREE_CHILDREN (l0node[1]));
1117 :
1118 1389 : if (left_op.length () != 2
1119 3714 : || right_op.length () != 2
1120 : || !mul0
1121 1271 : || !mul1
1122 2542 : || linear_loads_p (perm_cache, left_op[1]) == PERM_ODDEVEN)
1123 : return IFN_LAST;
1124 :
1125 1197 : enum _conj_status status;
1126 1197 : auto_vec<slp_tree> res_ops;
1127 1197 : if (!vect_validate_multiplication_commutative (perm_cache, compat_cache,
1128 : left_op, right_op, false,
1129 : res_ops, &status))
1130 : return IFN_LAST;
1131 :
1132 196 : if (status == CONJ_NONE)
1133 : {
1134 175 : if (add0)
1135 : ifn = IFN_COMPLEX_FMA;
1136 : else
1137 165 : ifn = IFN_COMPLEX_MUL;
1138 : }
1139 : else
1140 : {
1141 21 : if(add0)
1142 : ifn = IFN_COMPLEX_FMA_CONJ;
1143 : else
1144 11 : ifn = IFN_COMPLEX_MUL_CONJ;
1145 : }
1146 :
1147 196 : if (!vect_pattern_validate_optab (ifn, *node))
1148 : return IFN_LAST;
1149 :
1150 32 : ops->truncate (0);
1151 48 : ops->create (add0 ? 4 : 3);
1152 :
1153 32 : if (add0)
1154 16 : ops->quick_push (add0);
1155 :
1156 32 : complex_perm_kinds_t kind = linear_loads_p (perm_cache, res_ops[0]);
1157 32 : if (kind == PERM_EVENODD || kind == PERM_TOP)
1158 : {
1159 16 : ops->quick_push (res_ops[1]);
1160 16 : ops->quick_push (res_ops[3]);
1161 16 : ops->quick_push (res_ops[0]);
1162 : }
1163 16 : else if (kind == PERM_EVENEVEN && status != CONJ_SND)
1164 : {
1165 16 : ops->quick_push (res_ops[0]);
1166 16 : ops->quick_push (res_ops[2]);
1167 16 : ops->quick_push (res_ops[1]);
1168 : }
1169 : else
1170 : {
1171 0 : ops->quick_push (res_ops[0]);
1172 0 : ops->quick_push (res_ops[3]);
1173 0 : ops->quick_push (res_ops[1]);
1174 : }
1175 :
1176 : return ifn;
1177 3640 : }
1178 :
1179 : /* Attempt to recognize a complex mul pattern. */
1180 :
1181 : vect_pattern*
1182 0 : complex_mul_pattern::recognize (slp_tree_to_load_perm_map_t *perm_cache,
1183 : slp_compat_nodes_map_t *compat_cache,
1184 : slp_tree *node)
1185 : {
1186 0 : auto_vec<slp_tree> ops;
1187 0 : complex_operation_t op
1188 0 : = vect_detect_pair_op (*node, true, &ops);
1189 0 : internal_fn ifn
1190 0 : = complex_mul_pattern::matches (op, perm_cache, compat_cache, node, &ops);
1191 0 : if (ifn == IFN_LAST)
1192 : return NULL;
1193 :
1194 0 : return new complex_mul_pattern (node, &ops, ifn);
1195 0 : }
1196 :
1197 : /* Perform a replacement of the detected complex mul pattern with the new
1198 : instruction sequences. */
1199 :
1200 : void
1201 32 : complex_mul_pattern::build (vec_info *vinfo)
1202 : {
1203 32 : slp_tree node;
1204 32 : unsigned i;
1205 32 : switch (this->m_ifn)
1206 : {
1207 16 : case IFN_COMPLEX_MUL:
1208 16 : case IFN_COMPLEX_MUL_CONJ:
1209 16 : {
1210 16 : slp_tree newnode
1211 16 : = vect_build_combine_node (this->m_ops[0], this->m_ops[1],
1212 16 : *this->m_node);
1213 16 : SLP_TREE_REF_COUNT (this->m_ops[2])++;
1214 :
1215 48 : FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (*this->m_node), i, node)
1216 32 : vect_free_slp_tree (node);
1217 :
1218 : /* First re-arrange the children. */
1219 16 : SLP_TREE_CHILDREN (*this->m_node).reserve_exact (2);
1220 16 : SLP_TREE_CHILDREN (*this->m_node)[0] = this->m_ops[2];
1221 16 : SLP_TREE_CHILDREN (*this->m_node)[1] = newnode;
1222 16 : break;
1223 : }
1224 16 : case IFN_COMPLEX_FMA:
1225 16 : case IFN_COMPLEX_FMA_CONJ:
1226 16 : {
1227 16 : SLP_TREE_REF_COUNT (this->m_ops[0])++;
1228 16 : slp_tree newnode
1229 16 : = vect_build_combine_node (this->m_ops[1], this->m_ops[2],
1230 16 : *this->m_node);
1231 16 : SLP_TREE_REF_COUNT (this->m_ops[3])++;
1232 :
1233 48 : FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (*this->m_node), i, node)
1234 32 : vect_free_slp_tree (node);
1235 :
1236 : /* First re-arrange the children. */
1237 16 : SLP_TREE_CHILDREN (*this->m_node).safe_grow (3);
1238 16 : SLP_TREE_CHILDREN (*this->m_node)[0] = this->m_ops[3];
1239 16 : SLP_TREE_CHILDREN (*this->m_node)[1] = newnode;
1240 16 : SLP_TREE_CHILDREN (*this->m_node)[2] = this->m_ops[0];
1241 :
1242 : /* Tell the builder to expect an extra argument. */
1243 16 : this->m_num_args++;
1244 16 : break;
1245 : }
1246 0 : default:
1247 0 : gcc_unreachable ();
1248 : }
1249 :
1250 : /* And then rewrite the node itself. */
1251 32 : build_common (vinfo);
1252 32 : }
1253 :
1254 : /*******************************************************************************
1255 : * complex_fms_pattern class
1256 : ******************************************************************************/
1257 :
1258 : class complex_fms_pattern : public complex_pattern
1259 : {
1260 : protected:
1261 0 : complex_fms_pattern (slp_tree *node, vec<slp_tree> *m_ops, internal_fn ifn)
1262 0 : : complex_pattern (node, m_ops, ifn)
1263 : {
1264 0 : this->m_num_args = 3;
1265 : }
1266 :
1267 : public:
1268 : void build (vec_info *) final override;
1269 : static internal_fn
1270 : matches (complex_operation_t op, slp_tree_to_load_perm_map_t *,
1271 : slp_compat_nodes_map_t *, slp_tree *, vec<slp_tree> *);
1272 :
1273 : static vect_pattern*
1274 : recognize (slp_tree_to_load_perm_map_t *, slp_compat_nodes_map_t *,
1275 : slp_tree *);
1276 :
1277 : static vect_pattern*
1278 0 : mkInstance (slp_tree *node, vec<slp_tree> *m_ops, internal_fn ifn)
1279 : {
1280 0 : return new complex_fms_pattern (node, m_ops, ifn);
1281 : }
1282 : };
1283 :
1284 :
1285 : /* Pattern matcher for trying to match complex multiply and subtract pattern
1286 : in SLP tree. If the operation matches then IFN is set to the operation
1287 : it matched and the arguments to the two replacement statements are put in
1288 : m_ops.
1289 :
1290 : If no match is found then IFN is set to IFN_LAST and m_ops is unchanged.
1291 :
1292 : This function matches the patterns shaped as:
1293 :
1294 : double ax = (b[i+1] * a[i]) + (b[i] * a[i]);
1295 : double bx = (a[i+1] * b[i]) - (a[i+1] * b[i+1]);
1296 :
1297 : c[i] = c[i] - ax;
1298 : c[i+1] = c[i+1] + bx;
1299 :
1300 : If a match occurred then TRUE is returned, else FALSE. The initial match is
1301 : expected to be in OP1 and the initial match operands in args0. */
1302 :
1303 : internal_fn
1304 5560226 : complex_fms_pattern::matches (complex_operation_t op,
1305 : slp_tree_to_load_perm_map_t *perm_cache,
1306 : slp_compat_nodes_map_t *compat_cache,
1307 : slp_tree * ref_node, vec<slp_tree> *ops)
1308 : {
1309 : /* It's only valid to form FMSs with -ffp-contract=fast. */
1310 5560226 : if (!SLP_TREE_VECTYPE (*ref_node)
1311 5560226 : || (flag_fp_contract_mode != FP_CONTRACT_FAST
1312 35637 : && FLOAT_TYPE_P (SLP_TREE_VECTYPE (*ref_node))))
1313 : return IFN_LAST;
1314 :
1315 : /* Match c - a * b when SLP has built the result as:
1316 :
1317 : c.real + (a.imag * b.imag - a.real * b.real)
1318 : c.imag - (a.real * b.imag + a.imag * b.real)
1319 :
1320 : This represents the same operation as the existing FMS matcher below,
1321 : but with the accumulator outside the complex product node. */
1322 3906683 : if (op == PLUS_MINUS)
1323 : {
1324 4076 : auto plus_ops = SLP_TREE_CHILDREN ((*ops)[0]);
1325 4076 : auto minus_ops = SLP_TREE_CHILDREN ((*ops)[1]);
1326 12228 : if (plus_ops.length () != 2 || minus_ops.length () != 2)
1327 : return IFN_LAST;
1328 :
1329 4076 : slp_tree acc = minus_ops[0];
1330 4076 : slp_tree prod = minus_ops[1];
1331 8152 : if (!((plus_ops[0] == acc && plus_ops[1] == prod)
1332 0 : || (plus_ops[1] == acc && plus_ops[0] == prod)))
1333 : return IFN_LAST;
1334 4076 : if (linear_loads_p (perm_cache, acc) != PERM_EVENODD)
1335 : return IFN_LAST;
1336 :
1337 172 : auto_vec<slp_tree> prod_ops;
1338 172 : if (vect_detect_pair_op (prod, true, &prod_ops) != MINUS_PLUS)
1339 : return IFN_LAST;
1340 172 : if (prod_ops.length () != 2)
1341 : return IFN_LAST;
1342 :
1343 0 : auto prod_left = SLP_TREE_CHILDREN (prod_ops[0]);
1344 0 : auto prod_right = SLP_TREE_CHILDREN (prod_ops[1]);
1345 0 : if (prod_left.length () != 2
1346 0 : || prod_right.length () != 2
1347 0 : || !vect_match_expression_p (prod_left[0], MULT_EXPR)
1348 0 : || !vect_match_expression_p (prod_left[1], MULT_EXPR)
1349 0 : || !vect_match_expression_p (prod_right[0], MULT_EXPR)
1350 0 : || !vect_match_expression_p (prod_right[1], MULT_EXPR))
1351 : return IFN_LAST;
1352 :
1353 0 : auto_vec<slp_tree> left_op, right_op;
1354 0 : left_op.safe_splice (SLP_TREE_CHILDREN (prod_left[0]));
1355 0 : right_op.safe_splice (SLP_TREE_CHILDREN (prod_left[1]));
1356 :
1357 0 : enum _conj_status status;
1358 0 : auto_vec<slp_tree> res_ops;
1359 0 : if (!vect_validate_multiplication_commutative (perm_cache, compat_cache,
1360 : right_op, left_op, true,
1361 : res_ops, &status))
1362 : return IFN_LAST;
1363 :
1364 0 : internal_fn ifn = status == CONJ_NONE ? IFN_COMPLEX_FMS
1365 : : IFN_COMPLEX_FMS_CONJ;
1366 0 : if (!vect_pattern_validate_optab (ifn, *ref_node))
1367 : return IFN_LAST;
1368 :
1369 0 : ops->truncate (0);
1370 0 : ops->create (4);
1371 :
1372 0 : complex_perm_kinds_t kind = linear_loads_p (perm_cache, res_ops[0]);
1373 0 : if (kind == PERM_EVENODD || kind == PERM_TOP)
1374 : {
1375 0 : ops->quick_push (acc);
1376 0 : ops->quick_push (res_ops[0]);
1377 0 : ops->quick_push (res_ops[1]);
1378 0 : ops->quick_push (res_ops[3]);
1379 : }
1380 0 : else if (kind == PERM_EVENEVEN && status != CONJ_SND)
1381 : {
1382 0 : ops->quick_push (acc);
1383 0 : ops->quick_push (res_ops[1]);
1384 0 : ops->quick_push (res_ops[0]);
1385 0 : ops->quick_push (res_ops[2]);
1386 : }
1387 : else
1388 : {
1389 0 : ops->quick_push (acc);
1390 0 : ops->quick_push (res_ops[1]);
1391 0 : ops->quick_push (res_ops[0]);
1392 0 : ops->quick_push (res_ops[3]);
1393 : }
1394 :
1395 : return ifn;
1396 172 : }
1397 :
1398 : /* We need to ignore the two_operands nodes that may also match,
1399 : for that we can check if they have any scalar statements and also
1400 : check that it's not a permute node as we're looking for a normal
1401 : MINUS_EXPR operation. */
1402 3902607 : if (op != CMPLX_NONE)
1403 : return IFN_LAST;
1404 :
1405 3898870 : slp_tree root = *ref_node;
1406 3898870 : if (!vect_match_expression_p (root, MINUS_EXPR))
1407 : return IFN_LAST;
1408 :
1409 : /* TODO: Support invariants here, with the new layout CADD now
1410 : can match before we get a chance to try CFMS. */
1411 71113 : auto nodes = SLP_TREE_CHILDREN (root);
1412 142202 : if (!vect_match_expression_p (nodes[1], MULT_EXPR)
1413 86124 : || vect_detect_pair_op (nodes[0]) != PLUS_MINUS)
1414 : return IFN_LAST;
1415 :
1416 24 : auto childs = SLP_TREE_CHILDREN (nodes[0]);
1417 24 : auto l0node = SLP_TREE_CHILDREN (childs[0]);
1418 :
1419 : /* Now operand2+4 may lead to another expression. */
1420 24 : auto_vec<slp_tree> left_op, right_op;
1421 24 : left_op.safe_splice (SLP_TREE_CHILDREN (l0node[1]));
1422 24 : right_op.safe_splice (SLP_TREE_CHILDREN (nodes[1]));
1423 :
1424 : /* If these nodes don't have any children then they're
1425 : not ones we're interested in. */
1426 24 : if (left_op.length () != 2
1427 18 : || right_op.length () != 2
1428 42 : || !vect_match_expression_p (l0node[1], MULT_EXPR))
1429 : return IFN_LAST;
1430 :
1431 18 : enum _conj_status status;
1432 18 : auto_vec<slp_tree> res_ops;
1433 18 : if (!vect_validate_multiplication_commutative (perm_cache, compat_cache,
1434 : right_op, left_op, true,
1435 : res_ops, &status))
1436 : return IFN_LAST;
1437 :
1438 0 : internal_fn ifn = status == CONJ_NONE ? IFN_COMPLEX_FMS
1439 : : IFN_COMPLEX_FMS_CONJ;
1440 0 : if (!vect_pattern_validate_optab (ifn, *ref_node))
1441 : return IFN_LAST;
1442 :
1443 0 : ops->truncate (0);
1444 0 : ops->create (4);
1445 :
1446 0 : complex_perm_kinds_t kind = linear_loads_p (perm_cache, res_ops[2]);
1447 0 : if (kind == PERM_EVENODD)
1448 : {
1449 0 : ops->quick_push (l0node[0]);
1450 0 : ops->quick_push (res_ops[2]);
1451 0 : ops->quick_push (res_ops[3]);
1452 0 : ops->quick_push (res_ops[1]);
1453 : }
1454 : else
1455 : {
1456 0 : ops->quick_push (l0node[0]);
1457 0 : ops->quick_push (res_ops[3]);
1458 0 : ops->quick_push (res_ops[2]);
1459 0 : ops->quick_push (res_ops[0]);
1460 : }
1461 :
1462 : return ifn;
1463 42 : }
1464 :
1465 : /* Attempt to recognize a complex mul pattern. */
1466 :
1467 : vect_pattern*
1468 0 : complex_fms_pattern::recognize (slp_tree_to_load_perm_map_t *perm_cache,
1469 : slp_compat_nodes_map_t *compat_cache,
1470 : slp_tree *node)
1471 : {
1472 0 : auto_vec<slp_tree> ops;
1473 0 : complex_operation_t op
1474 0 : = vect_detect_pair_op (*node, true, &ops);
1475 0 : internal_fn ifn
1476 0 : = complex_fms_pattern::matches (op, perm_cache, compat_cache, node, &ops);
1477 0 : if (ifn == IFN_LAST)
1478 : return NULL;
1479 :
1480 0 : return new complex_fms_pattern (node, &ops, ifn);
1481 0 : }
1482 :
1483 : /* Perform a replacement of the detected complex mul pattern with the new
1484 : instruction sequences. */
1485 :
1486 : void
1487 0 : complex_fms_pattern::build (vec_info *vinfo)
1488 : {
1489 0 : slp_tree node;
1490 0 : unsigned i;
1491 0 : slp_tree newnode =
1492 0 : vect_build_combine_node (this->m_ops[2], this->m_ops[3], *this->m_node);
1493 0 : SLP_TREE_REF_COUNT (this->m_ops[0])++;
1494 0 : SLP_TREE_REF_COUNT (this->m_ops[1])++;
1495 :
1496 0 : FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (*this->m_node), i, node)
1497 0 : vect_free_slp_tree (node);
1498 :
1499 0 : SLP_TREE_CHILDREN (*this->m_node).release ();
1500 0 : SLP_TREE_CHILDREN (*this->m_node).create (3);
1501 :
1502 : /* First re-arrange the children. */
1503 0 : SLP_TREE_CHILDREN (*this->m_node).quick_push (this->m_ops[1]);
1504 0 : SLP_TREE_CHILDREN (*this->m_node).quick_push (newnode);
1505 0 : SLP_TREE_CHILDREN (*this->m_node).quick_push (this->m_ops[0]);
1506 :
1507 : /* And then rewrite the node itself. */
1508 0 : build_common (vinfo);
1509 0 : }
1510 :
1511 : /*******************************************************************************
1512 : * complex_operations_pattern class
1513 : ******************************************************************************/
1514 :
1515 : /* This function combines all the existing pattern matchers above into one class
1516 : that shares the functionality between them. The initial match is shared
1517 : between all complex operations. */
1518 :
1519 : class complex_operations_pattern : public complex_pattern
1520 : {
1521 : protected:
1522 : complex_operations_pattern (slp_tree *node, vec<slp_tree> *m_ops,
1523 : internal_fn ifn)
1524 : : complex_pattern (node, m_ops, ifn)
1525 : {
1526 : this->m_num_args = 0;
1527 : }
1528 :
1529 : public:
1530 : void build (vec_info *) final override;
1531 : static internal_fn
1532 : matches (complex_operation_t op, slp_tree_to_load_perm_map_t *,
1533 : slp_compat_nodes_map_t *, slp_tree *, vec<slp_tree> *);
1534 :
1535 : static vect_pattern*
1536 : recognize (slp_tree_to_load_perm_map_t *, slp_compat_nodes_map_t *,
1537 : slp_tree *);
1538 : };
1539 :
1540 : /* Dummy matches implementation for proxy object. */
1541 :
1542 : internal_fn
1543 0 : complex_operations_pattern::
1544 : matches (complex_operation_t /* op */,
1545 : slp_tree_to_load_perm_map_t * /* perm_cache */,
1546 : slp_compat_nodes_map_t * /* compat_cache */,
1547 : slp_tree * /* ref_node */, vec<slp_tree> * /* ops */)
1548 : {
1549 0 : return IFN_LAST;
1550 : }
1551 :
1552 : /* Attempt to recognize a complex mul pattern. */
1553 :
1554 : vect_pattern*
1555 5560226 : complex_operations_pattern::recognize (slp_tree_to_load_perm_map_t *perm_cache,
1556 : slp_compat_nodes_map_t *ccache,
1557 : slp_tree *node)
1558 : {
1559 5560226 : auto_vec<slp_tree> ops;
1560 5560226 : complex_operation_t op
1561 5560226 : = vect_detect_pair_op (*node, true, &ops);
1562 5560226 : internal_fn ifn = IFN_LAST;
1563 :
1564 5560226 : ifn = complex_fms_pattern::matches (op, perm_cache, ccache, node, &ops);
1565 5560226 : if (ifn != IFN_LAST)
1566 0 : return complex_fms_pattern::mkInstance (node, &ops, ifn);
1567 :
1568 5560226 : ifn = complex_mul_pattern::matches (op, perm_cache, ccache, node, &ops);
1569 5560226 : if (ifn != IFN_LAST)
1570 32 : return complex_mul_pattern::mkInstance (node, &ops, ifn);
1571 :
1572 5560194 : ifn = complex_add_pattern::matches (op, perm_cache, ccache, node, &ops);
1573 5560194 : if (ifn != IFN_LAST)
1574 0 : return complex_add_pattern::mkInstance (node, &ops, ifn);
1575 :
1576 : return NULL;
1577 5560226 : }
1578 :
1579 : /* Dummy implementation of build. */
1580 :
1581 : void
1582 0 : complex_operations_pattern::build (vec_info * /* vinfo */)
1583 : {
1584 0 : gcc_unreachable ();
1585 : }
1586 :
1587 :
1588 : /* The addsub_pattern. */
1589 :
1590 : class addsub_pattern : public vect_pattern
1591 : {
1592 : public:
1593 1082 : addsub_pattern (slp_tree *node, internal_fn ifn)
1594 1082 : : vect_pattern (node, NULL, ifn) {};
1595 :
1596 : void build (vec_info *) final override;
1597 :
1598 : static vect_pattern*
1599 : recognize (slp_tree_to_load_perm_map_t *, slp_compat_nodes_map_t *,
1600 : slp_tree *);
1601 : };
1602 :
1603 : vect_pattern *
1604 5560226 : addsub_pattern::recognize (slp_tree_to_load_perm_map_t *,
1605 : slp_compat_nodes_map_t *, slp_tree *node_)
1606 : {
1607 5560226 : slp_tree node = *node_;
1608 5560226 : if (!SLP_TREE_PERMUTE_P (node)
1609 26673 : || SLP_TREE_CHILDREN (node).length () != 2
1610 5583855 : || SLP_TREE_LANE_PERMUTATION (node).length () % 2)
1611 : return NULL;
1612 :
1613 : /* Match a blend of a plus and a minus op with the same number of plus and
1614 : minus lanes on the same operands. */
1615 18562 : unsigned l0 = SLP_TREE_LANE_PERMUTATION (node)[0].first;
1616 18562 : unsigned l1 = SLP_TREE_LANE_PERMUTATION (node)[1].first;
1617 18562 : if (l0 == l1)
1618 : return NULL;
1619 15491 : bool fma_p = false;
1620 15491 : bool l0add_p = vect_match_expression_p (SLP_TREE_CHILDREN (node)[l0],
1621 15491 : PLUS_EXPR);
1622 15491 : if (!l0add_p
1623 15491 : && !vect_match_expression_p (SLP_TREE_CHILDREN (node)[l0], MINUS_EXPR))
1624 : {
1625 6729 : l0add_p = vect_match_expression_p (SLP_TREE_CHILDREN (node)[l0], CFN_FMA);
1626 6729 : if (!l0add_p
1627 6729 : && !vect_match_expression_p (SLP_TREE_CHILDREN (node)[l0], CFN_FMS))
1628 6727 : return NULL;
1629 : fma_p = true;
1630 : }
1631 8764 : bool l1add_p = vect_match_expression_p (SLP_TREE_CHILDREN (node)[l1],
1632 8764 : PLUS_EXPR);
1633 8764 : if (l1add_p && fma_p)
1634 : return NULL;
1635 8764 : if (!l1add_p
1636 8764 : && !vect_match_expression_p (SLP_TREE_CHILDREN (node)[l1], MINUS_EXPR))
1637 : {
1638 705 : if (!fma_p)
1639 : return NULL;
1640 2 : l1add_p = vect_match_expression_p (SLP_TREE_CHILDREN (node)[l1], CFN_FMA);
1641 2 : if (!l1add_p
1642 2 : && !vect_match_expression_p (SLP_TREE_CHILDREN (node)[l1], CFN_FMS))
1643 0 : return NULL;
1644 : }
1645 8059 : else if (!l1add_p && fma_p)
1646 : return NULL;
1647 :
1648 8061 : slp_tree l0node = SLP_TREE_CHILDREN (node)[l0];
1649 8061 : slp_tree l1node = SLP_TREE_CHILDREN (node)[l1];
1650 8061 : if (!((SLP_TREE_CHILDREN (l0node)[0] == SLP_TREE_CHILDREN (l1node)[0]
1651 7655 : && SLP_TREE_CHILDREN (l0node)[1] == SLP_TREE_CHILDREN (l1node)[1])
1652 429 : || (SLP_TREE_CHILDREN (l0node)[0] == SLP_TREE_CHILDREN (l1node)[1]
1653 0 : && SLP_TREE_CHILDREN (l0node)[1] == SLP_TREE_CHILDREN (l1node)[0])))
1654 : return NULL;
1655 :
1656 26135 : for (unsigned i = 0; i < SLP_TREE_LANE_PERMUTATION (node).length (); ++i)
1657 : {
1658 18644 : std::pair<unsigned, unsigned> perm = SLP_TREE_LANE_PERMUTATION (node)[i];
1659 : /* It has to be alternating -, +, -,
1660 : While we could permute the .ADDSUB inputs and the .ADDSUB output
1661 : that's only profitable over the add + sub + blend if at least
1662 : one of the permute is optimized which we can't determine here. */
1663 28010 : if (perm.first != ((i & 1) ? l1 : l0)
1664 18552 : || perm.second != i)
1665 5560226 : return NULL;
1666 : }
1667 :
1668 : /* Now we have either { -, +, -, + ... } (!l0add_p) or { +, -, +, - ... }
1669 : (l0add_p), see whether we have FMA variants. We can only form FMAs
1670 : if allowed via -ffp-contract=fast or if they were FMA before. */
1671 7491 : if (!fma_p
1672 7489 : && flag_fp_contract_mode != FP_CONTRACT_FAST
1673 7528 : && FLOAT_TYPE_P (SLP_TREE_VECTYPE (l0node)))
1674 : ;
1675 7454 : else if (!l0add_p
1676 7454 : && (fma_p
1677 3376 : || vect_match_expression_p (SLP_TREE_CHILDREN (l0node)[0],
1678 3376 : MULT_EXPR)))
1679 : {
1680 : /* (c * d) -+ a */
1681 1278 : if (vect_pattern_validate_optab (IFN_VEC_FMADDSUB, node))
1682 37 : return new addsub_pattern (node_, IFN_VEC_FMADDSUB);
1683 : }
1684 6176 : else if (l0add_p
1685 6176 : && (fma_p
1686 6176 : || vect_match_expression_p (SLP_TREE_CHILDREN (l1node)[0],
1687 4076 : MULT_EXPR)))
1688 : {
1689 : /* (c * d) +- a */
1690 731 : if (vect_pattern_validate_optab (IFN_VEC_FMSUBADD, node))
1691 23 : return new addsub_pattern (node_, IFN_VEC_FMSUBADD);
1692 : }
1693 :
1694 7431 : if (!fma_p && !l0add_p && vect_pattern_validate_optab (IFN_VEC_ADDSUB, node))
1695 1022 : return new addsub_pattern (node_, IFN_VEC_ADDSUB);
1696 :
1697 : return NULL;
1698 : }
1699 :
1700 : void
1701 1082 : addsub_pattern::build (vec_info *vinfo)
1702 : {
1703 1082 : slp_tree node = *m_node;
1704 :
1705 1082 : unsigned l0 = SLP_TREE_LANE_PERMUTATION (node)[0].first;
1706 1082 : unsigned l1 = SLP_TREE_LANE_PERMUTATION (node)[1].first;
1707 :
1708 1082 : switch (m_ifn)
1709 : {
1710 1022 : case IFN_VEC_ADDSUB:
1711 1022 : {
1712 1022 : slp_tree sub = SLP_TREE_CHILDREN (node)[l0];
1713 1022 : slp_tree add = SLP_TREE_CHILDREN (node)[l1];
1714 :
1715 : /* Modify the blend node in-place. */
1716 1022 : SLP_TREE_CHILDREN (node)[0] = SLP_TREE_CHILDREN (sub)[0];
1717 1022 : SLP_TREE_CHILDREN (node)[1] = SLP_TREE_CHILDREN (sub)[1];
1718 1022 : SLP_TREE_REF_COUNT (SLP_TREE_CHILDREN (node)[0])++;
1719 1022 : SLP_TREE_REF_COUNT (SLP_TREE_CHILDREN (node)[1])++;
1720 :
1721 : /* Build IFN_VEC_ADDSUB from the sub representative operands. */
1722 1022 : stmt_vec_info rep = SLP_TREE_REPRESENTATIVE (sub);
1723 1022 : gcall *call = gimple_build_call_internal (IFN_VEC_ADDSUB, 2,
1724 : gimple_assign_rhs1 (rep->stmt),
1725 1022 : gimple_assign_rhs2 (rep->stmt));
1726 1022 : gimple_call_set_lhs (call, make_ssa_name
1727 1022 : (TREE_TYPE (gimple_assign_lhs (rep->stmt))));
1728 1022 : gimple_call_set_nothrow (call, true);
1729 1022 : gimple_set_bb (call, gimple_bb (rep->stmt));
1730 1022 : stmt_vec_info new_rep
1731 1022 : = vinfo->add_pattern_stmt (call, vect_orig_stmt (rep));
1732 1022 : SLP_TREE_REPRESENTATIVE (node) = new_rep;
1733 1022 : STMT_VINFO_RELEVANT (new_rep) = vect_used_in_scope;
1734 1022 : STMT_SLP_TYPE (new_rep) = pure_slp;
1735 1022 : STMT_VINFO_VECTYPE (new_rep) = SLP_TREE_VECTYPE (node);
1736 1022 : SLP_TREE_CODE (node) = ERROR_MARK;
1737 1022 : SLP_TREE_LANE_PERMUTATION (node).release ();
1738 :
1739 1022 : vect_free_slp_tree (sub);
1740 1022 : vect_free_slp_tree (add);
1741 1022 : break;
1742 : }
1743 60 : case IFN_VEC_FMADDSUB:
1744 60 : case IFN_VEC_FMSUBADD:
1745 60 : {
1746 60 : slp_tree sub, add;
1747 60 : if (m_ifn == IFN_VEC_FMADDSUB)
1748 : {
1749 37 : sub = SLP_TREE_CHILDREN (node)[l0];
1750 37 : add = SLP_TREE_CHILDREN (node)[l1];
1751 : }
1752 : else /* m_ifn == IFN_VEC_FMSUBADD */
1753 : {
1754 23 : sub = SLP_TREE_CHILDREN (node)[l1];
1755 23 : add = SLP_TREE_CHILDREN (node)[l0];
1756 : }
1757 : /* Modify the blend node in-place. */
1758 60 : SLP_TREE_CHILDREN (node).safe_grow (3, true);
1759 60 : gcall *call;
1760 60 : stmt_vec_info srep = SLP_TREE_REPRESENTATIVE (sub);
1761 60 : if (vect_match_expression_p (add, CFN_FMA))
1762 : {
1763 2 : SLP_TREE_CHILDREN (node)[0] = SLP_TREE_CHILDREN (add)[0];
1764 2 : SLP_TREE_CHILDREN (node)[1] = SLP_TREE_CHILDREN (add)[1];
1765 2 : SLP_TREE_CHILDREN (node)[2] = SLP_TREE_CHILDREN (add)[2];
1766 : /* Build IFN_VEC_FMADDSUB from the fms representative
1767 : operands. */
1768 2 : call = gimple_build_call_internal (m_ifn, 3,
1769 : gimple_call_arg (srep->stmt, 0),
1770 : gimple_call_arg (srep->stmt, 1),
1771 2 : gimple_call_arg (srep->stmt, 2));
1772 : }
1773 : else
1774 : {
1775 58 : slp_tree mul = SLP_TREE_CHILDREN (sub)[0];
1776 58 : SLP_TREE_CHILDREN (node)[0] = SLP_TREE_CHILDREN (mul)[0];
1777 58 : SLP_TREE_CHILDREN (node)[1] = SLP_TREE_CHILDREN (mul)[1];
1778 58 : SLP_TREE_CHILDREN (node)[2] = SLP_TREE_CHILDREN (sub)[1];
1779 : /* Build IFN_VEC_FMADDSUB from the mul/sub representative
1780 : operands. */
1781 58 : stmt_vec_info mrep = SLP_TREE_REPRESENTATIVE (mul);
1782 58 : call = gimple_build_call_internal (m_ifn, 3,
1783 : gimple_assign_rhs1 (mrep->stmt),
1784 58 : gimple_assign_rhs2 (mrep->stmt),
1785 58 : gimple_assign_rhs2 (srep->stmt));
1786 : }
1787 60 : SLP_TREE_REF_COUNT (SLP_TREE_CHILDREN (node)[0])++;
1788 60 : SLP_TREE_REF_COUNT (SLP_TREE_CHILDREN (node)[1])++;
1789 60 : SLP_TREE_REF_COUNT (SLP_TREE_CHILDREN (node)[2])++;
1790 :
1791 60 : gimple_call_set_lhs (call, make_ssa_name
1792 60 : (TREE_TYPE (gimple_get_lhs (srep->stmt))));
1793 60 : gimple_call_set_nothrow (call, true);
1794 60 : gimple_set_bb (call, gimple_bb (srep->stmt));
1795 60 : stmt_vec_info new_rep
1796 60 : = vinfo->add_pattern_stmt (call, vect_orig_stmt (srep));
1797 60 : SLP_TREE_REPRESENTATIVE (node) = new_rep;
1798 60 : STMT_VINFO_RELEVANT (new_rep) = vect_used_in_scope;
1799 60 : STMT_SLP_TYPE (new_rep) = pure_slp;
1800 60 : STMT_VINFO_VECTYPE (new_rep) = SLP_TREE_VECTYPE (node);
1801 60 : SLP_TREE_CODE (node) = ERROR_MARK;
1802 60 : SLP_TREE_LANE_PERMUTATION (node).release ();
1803 :
1804 60 : vect_free_slp_tree (sub);
1805 60 : vect_free_slp_tree (add);
1806 60 : break;
1807 : }
1808 1082 : default:;
1809 : }
1810 1082 : }
1811 :
1812 : /*******************************************************************************
1813 : * Pattern matching definitions
1814 : ******************************************************************************/
1815 :
1816 : #define SLP_PATTERN(x) &x::recognize
1817 : vect_pattern_decl_t slp_patterns[]
1818 : {
1819 : /* For least amount of back-tracking and more efficient matching
1820 : order patterns from the largest to the smallest. Especially if they
1821 : overlap in what they can detect. */
1822 :
1823 : SLP_PATTERN (complex_operations_pattern),
1824 : SLP_PATTERN (addsub_pattern)
1825 : };
1826 : #undef SLP_PATTERN
1827 :
1828 : /* Set the number of SLP pattern matchers available. */
1829 : size_t num__slp_patterns = ARRAY_SIZE (slp_patterns);
|
