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