Bug Summary

File:build/gcc/tree-vect-slp-patterns.c
Warning:line 820, column 12
Although the value stored to 'kind' is used in the enclosing expression, the value is never actually read from 'kind'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name tree-vect-slp-patterns.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model static -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/gcc -resource-dir /usr/lib64/clang/13.0.0 -D IN_GCC -D HAVE_CONFIG_H -I . -I . -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/. -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../include -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libcpp/include -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libcody -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libdecnumber -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libdecnumber/bid -I ../libdecnumber -I /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/../libbacktrace -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/11/../../../../include/c++/11 -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/11/../../../../include/c++/11/x86_64-suse-linux -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/11/../../../../include/c++/11/backward -internal-isystem /usr/lib64/clang/13.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/bin/../lib64/gcc/x86_64-suse-linux/11/../../../../x86_64-suse-linux/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-narrowing -Wwrite-strings -Wno-error=format-diag -Wno-long-long -Wno-variadic-macros -Wno-overlength-strings -fdeprecated-macro -fdebug-compilation-dir=/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/gcc -ferror-limit 19 -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=plist-html -analyzer-config silence-checkers=core.NullDereference -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/objdir/clang-static-analyzer/2021-11-20-133755-20252-1/report-f88kxB.plist -x c++ /home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-vect-slp-patterns.c
1/* SLP - Pattern matcher on SLP trees
2 Copyright (C) 2020-2021 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along 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
74static bool
75vect_pattern_validate_optab (internal_fn ifn, slp_tree node)
76{
77 tree vectype = SLP_TREE_VECTYPE (node)(node)->vectype;
78 if (ifn == IFN_LAST || !vectype)
79 return false;
80
81 if (dump_enabled_p ())
82 dump_printf_loc (MSG_NOTE, vect_location,
83 "Found %s pattern in SLP tree\n",
84 internal_fn_name (ifn));
85
86 if (direct_internal_fn_supported_p (ifn, vectype, OPTIMIZE_FOR_SPEED))
87 {
88 if (dump_enabled_p ())
89 dump_printf_loc (MSG_NOTE, vect_location,
90 "Target supports %s vectorization with mode %T\n",
91 internal_fn_name (ifn), vectype);
92 }
93 else
94 {
95 if (dump_enabled_p ())
96 {
97 if (!vectype)
98 dump_printf_loc (MSG_NOTE, vect_location,
99 "Target does not support vector type for %T\n",
100 SLP_TREE_DEF_TYPE (node)(node)->def_type);
101 else
102 dump_printf_loc (MSG_NOTE, vect_location,
103 "Target does not support %s for vector type "
104 "%T\n", internal_fn_name (ifn), vectype);
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
119typedef 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
135static inline complex_perm_kinds_t
136is_linear_load_p (load_permutation_t loads)
137{
138 if (loads.length() == 0)
139 return PERM_UNKNOWN;
140
141 unsigned load, i;
142 complex_perm_kinds_t candidates[4]
143 = { PERM_ODDODD
144 , PERM_EVENEVEN
145 , PERM_EVENODD
146 , PERM_ODDEVEN
147 };
148
149 int valid_patterns = 4;
150 FOR_EACH_VEC_ELT (loads, i, load)for (i = 0; (loads).iterate ((i), &(load)); ++(i))
151 {
152 if (candidates[0] != PERM_UNKNOWN && load != 1)
153 {
154 candidates[0] = PERM_UNKNOWN;
155 valid_patterns--;
156 }
157 if (candidates[1] != PERM_UNKNOWN && load != 0)
158 {
159 candidates[1] = PERM_UNKNOWN;
160 valid_patterns--;
161 }
162 if (candidates[2] != PERM_UNKNOWN && load != i)
163 {
164 candidates[2] = PERM_UNKNOWN;
165 valid_patterns--;
166 }
167 if (candidates[3] != PERM_UNKNOWN
168 && load != (i % 2 == 0 ? i + 1 : i - 1))
169 {
170 candidates[3] = PERM_UNKNOWN;
171 valid_patterns--;
172 }
173
174 if (valid_patterns == 0)
175 return PERM_UNKNOWN;
176 }
177
178 for (i = 0; i < sizeof(candidates); i++)
179 if (candidates[i] != PERM_UNKNOWN)
180 return candidates[i];
181
182 return PERM_UNKNOWN;
183}
184
185/* Combine complex_perm_kinds A and B into a new permute kind that describes the
186 resulting operation. */
187
188static inline complex_perm_kinds_t
189vect_merge_perms (complex_perm_kinds_t a, complex_perm_kinds_t b)
190{
191 if (a == b)
192 return a;
193
194 if (a == PERM_TOP)
195 return b;
196
197 if (b == PERM_TOP)
198 return a;
199
200 return PERM_UNKNOWN;
201}
202
203/* Check to see if all loads rooted in ROOT are linear. Linearity is
204 defined as having no gaps between values loaded. */
205
206static complex_perm_kinds_t
207linear_loads_p (slp_tree_to_load_perm_map_t *perm_cache, slp_tree root)
208{
209 if (!root)
210 return PERM_UNKNOWN;
211
212 unsigned i;
213 complex_perm_kinds_t *tmp;
214
215 if ((tmp = perm_cache->get (root)) != NULLnullptr)
216 return *tmp;
217
218 complex_perm_kinds_t retval = PERM_UNKNOWN;
219 perm_cache->put (root, retval);
220
221 /* If it's a load node, then just read the load permute. */
222 if (SLP_TREE_LOAD_PERMUTATION (root)(root)->load_permutation.exists ())
223 {
224 retval = is_linear_load_p (SLP_TREE_LOAD_PERMUTATION (root)(root)->load_permutation);
225 perm_cache->put (root, retval);
226 return retval;
227 }
228 else if (SLP_TREE_DEF_TYPE (root)(root)->def_type != vect_internal_def)
229 {
230 retval = PERM_TOP;
231 perm_cache->put (root, retval);
232 return retval;
233 }
234
235 complex_perm_kinds_t kind = PERM_TOP;
236
237 slp_tree child;
238 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (root), i, child)for (i = 0; ((root)->children).iterate ((i), &(child))
; ++(i))
239 {
240 complex_perm_kinds_t res = linear_loads_p (perm_cache, child);
241 kind = vect_merge_perms (kind, res);
242 /* Unknown and Top are not valid on blends as they produce no permute. */
243 retval = kind;
244 if (kind == PERM_UNKNOWN || kind == PERM_TOP)
245 return retval;
246 }
247
248 retval = kind;
249
250 perm_cache->put (root, retval);
251 return retval;
252}
253
254
255/* This function attempts to make a node rooted in NODE is linear. If the node
256 if already linear than the node itself is returned in RESULT.
257
258 If the node is not linear then a new VEC_PERM_EXPR node is created with a
259 lane permute that when applied will make the node linear. If such a
260 permute cannot be created then FALSE is returned from the function.
261
262 Here linearity is defined as having a sequential, monotically increasing
263 load position inside the load permute generated by the loads reachable from
264 NODE. */
265
266static slp_tree
267vect_build_swap_evenodd_node (slp_tree node)
268{
269 /* Attempt to linearise the permute. */
270 vec<std::pair<unsigned, unsigned> > zipped;
271 zipped.create (SLP_TREE_LANES (node)(node)->lanes);
272
273 for (unsigned x = 0; x < SLP_TREE_LANES (node)(node)->lanes; x+=2)
274 {
275 zipped.quick_push (std::make_pair (0, x+1));
276 zipped.quick_push (std::make_pair (0, x));
277 }
278
279 /* Create the new permute node and store it instead. */
280 slp_tree vnode = vect_create_new_slp_node (1, VEC_PERM_EXPR);
281 SLP_TREE_LANE_PERMUTATION (vnode)(vnode)->lane_permutation = zipped;
282 SLP_TREE_VECTYPE (vnode)(vnode)->vectype = SLP_TREE_VECTYPE (node)(node)->vectype;
283 SLP_TREE_CHILDREN (vnode)(vnode)->children.quick_push (node);
284 SLP_TREE_REF_COUNT (vnode)(vnode)->refcnt = 1;
285 SLP_TREE_LANES (vnode)(vnode)->lanes = SLP_TREE_LANES (node)(node)->lanes;
286 SLP_TREE_REPRESENTATIVE (vnode)(vnode)->representative = SLP_TREE_REPRESENTATIVE (node)(node)->representative;
287 SLP_TREE_REF_COUNT (node)(node)->refcnt++;
288 return vnode;
289}
290
291/* Checks to see of the expression represented by NODE is a gimple assign with
292 code CODE. */
293
294static inline bool
295vect_match_expression_p (slp_tree node, tree_code code)
296{
297 if (!node
298 || !SLP_TREE_REPRESENTATIVE (node)(node)->representative)
299 return false;
300
301 gimple* expr = STMT_VINFO_STMT (SLP_TREE_REPRESENTATIVE (node))((node)->representative)->stmt;
302 if (!is_gimple_assign (expr)
303 || gimple_assign_rhs_code (expr) != code)
304 return false;
305
306 return true;
307}
308
309/* Check if the given lane permute in PERMUTES matches an alternating sequence
310 of {even odd even odd ...}. This to account for unrolled loops. Further
311 mode there resulting permute must be linear. */
312
313static inline bool
314vect_check_evenodd_blend (lane_permutation_t &permutes,
315 unsigned even, unsigned odd)
316{
317 if (permutes.length () == 0
318 || permutes.length () % 2 != 0)
319 return false;
320
321 unsigned val[2] = {even, odd};
322 unsigned seed = 0;
323 for (unsigned i = 0; i < permutes.length (); i++)
324 if (permutes[i].first != val[i % 2]
325 || permutes[i].second != seed++)
326 return false;
327
328 return true;
329}
330
331/* This function will match the two gimple expressions representing NODE1 and
332 NODE2 in parallel and returns the pair operation that represents the two
333 expressions in the two statements.
334
335 If match is successful then the corresponding complex_operation is
336 returned and the arguments to the two matched operations are returned in OPS.
337
338 If TWO_OPERANDS it is expected that the LANES of the parent VEC_PERM select
339 from the two nodes alternatingly.
340
341 If unsuccessful then CMPLX_NONE is returned and OPS is untouched.
342
343 e.g. the following gimple statements
344
345 stmt 0 _39 = _37 + _12;
346 stmt 1 _6 = _38 - _36;
347
348 will return PLUS_MINUS along with OPS containing {_37, _12, _38, _36}.
349*/
350
351static complex_operation_t
352vect_detect_pair_op (slp_tree node1, slp_tree node2, lane_permutation_t &lanes,
353 bool two_operands = true, vec<slp_tree> *ops = NULLnullptr)
354{
355 complex_operation_t result = CMPLX_NONE;
356
357 if (vect_match_expression_p (node1, MINUS_EXPR)
358 && vect_match_expression_p (node2, PLUS_EXPR)
359 && (!two_operands || vect_check_evenodd_blend (lanes, 0, 1)))
360 result = MINUS_PLUS;
361 else if (vect_match_expression_p (node1, PLUS_EXPR)
362 && vect_match_expression_p (node2, MINUS_EXPR)
363 && (!two_operands || vect_check_evenodd_blend (lanes, 0, 1)))
364 result = PLUS_MINUS;
365 else if (vect_match_expression_p (node1, PLUS_EXPR)
366 && vect_match_expression_p (node2, PLUS_EXPR))
367 result = PLUS_PLUS;
368 else if (vect_match_expression_p (node1, MULT_EXPR)
369 && vect_match_expression_p (node2, MULT_EXPR))
370 result = MULT_MULT;
371
372 if (result != CMPLX_NONE && ops != NULLnullptr)
373 {
374 if (two_operands)
375 {
376 auto l0node = SLP_TREE_CHILDREN (node1)(node1)->children;
377 auto l1node = SLP_TREE_CHILDREN (node2)(node2)->children;
378
379 /* Check if the tree is connected as we expect it. */
380 if (!((l0node[0] == l1node[0] && l0node[1] == l1node[1])
381 || (l0node[0] == l1node[1] && l0node[1] == l1node[0])))
382 return CMPLX_NONE;
383 }
384 ops->safe_push (node1);
385 ops->safe_push (node2);
386 }
387 return result;
388}
389
390/* Overload of vect_detect_pair_op that matches against the representative
391 statements in the children of NODE. It is expected that NODE has exactly
392 two children and when TWO_OPERANDS then NODE must be a VEC_PERM. */
393
394static complex_operation_t
395vect_detect_pair_op (slp_tree node, bool two_operands = true,
396 vec<slp_tree> *ops = NULLnullptr)
397{
398 if (!two_operands && SLP_TREE_CODE (node)(node)->code == VEC_PERM_EXPR)
399 return CMPLX_NONE;
400
401 if (SLP_TREE_CHILDREN (node)(node)->children.length () != 2)
402 return CMPLX_NONE;
403
404 vec<slp_tree> children = SLP_TREE_CHILDREN (node)(node)->children;
405 lane_permutation_t &lanes = SLP_TREE_LANE_PERMUTATION (node)(node)->lane_permutation;
406
407 return vect_detect_pair_op (children[0], children[1], lanes, two_operands,
408 ops);
409}
410
411/*******************************************************************************
412 * complex_pattern class
413 ******************************************************************************/
414
415/* SLP Complex Numbers pattern matching.
416
417 As an example, the following simple loop:
418
419 double a[restrict N]; double b[restrict N]; double c[restrict N];
420
421 for (int i=0; i < N; i+=2)
422 {
423 c[i] = a[i] - b[i+1];
424 c[i+1] = a[i+1] + b[i];
425 }
426
427 which represents a complex addition on with a rotation of 90* around the
428 argand plane. i.e. if `a` and `b` were complex numbers then this would be the
429 same as `a + (b * I)`.
430
431 Here the expressions for `c[i]` and `c[i+1]` are independent but have to be
432 both recognized in order for the pattern to work. As an SLP tree this is
433 represented as
434
435 +--------------------------------+
436 | stmt 0 *_9 = _10; |
437 | stmt 1 *_15 = _16; |
438 +--------------------------------+
439 |
440 |
441 v
442 +--------------------------------+
443 | stmt 0 _10 = _4 - _8; |
444 | stmt 1 _16 = _12 + _14; |
445 | lane permutation { 0[0] 1[1] } |
446 +--------------------------------+
447 | |
448 | |
449 | |
450 +-----+ | | +-----+
451 | | | | | |
452 +-----| { } |<-----+ +----->| { } --------+
453 | | | +------------------| | |
454 | +-----+ | +-----+ |
455 | | | |
456 | | | |
457 | +------|------------------+ |
458 | | | |
459 v v v v
460 +--------------------------+ +--------------------------------+
461 | stmt 0 _8 = *_7; | | stmt 0 _4 = *_3; |
462 | stmt 1 _14 = *_13; | | stmt 1 _12 = *_11; |
463 | load permutation { 1 0 } | | load permutation { 0 1 } |
464 +--------------------------+ +--------------------------------+
465
466 The pattern matcher allows you to replace both statements 0 and 1 or none at
467 all. Because this operation is a two operands operation the actual nodes
468 being replaced are those in the { } nodes. The actual scalar statements
469 themselves are not replaced or used during the matching but instead the
470 SLP_TREE_REPRESENTATIVE statements are inspected. You are also allowed to
471 replace and match on any number of nodes.
472
473 Because the pattern matcher matches on the representative statement for the
474 SLP node the case of two_operators it allows you to match the children of the
475 node. This is done using the method `recognize ()`.
476
477*/
478
479/* The complex_pattern class contains common code for pattern matchers that work
480 on complex numbers. These provide functionality to allow de-construction and
481 validation of sequences depicting/transforming REAL and IMAG pairs. */
482
483class complex_pattern : public vect_pattern
484{
485 protected:
486 auto_vec<slp_tree> m_workset;
487 complex_pattern (slp_tree *node, vec<slp_tree> *m_ops, internal_fn ifn)
488 : vect_pattern (node, m_ops, ifn)
489 {
490 this->m_workset.safe_push (*node);
491 }
492
493 public:
494 void build (vec_info *);
495
496 static internal_fn
497 matches (complex_operation_t op, slp_tree_to_load_perm_map_t *, slp_tree *,
498 vec<slp_tree> *);
499};
500
501/* Create a replacement pattern statement for each node in m_node and inserts
502 the new statement into m_node as the new representative statement. The old
503 statement is marked as being in a pattern defined by the new statement. The
504 statement is created as call to internal function IFN with m_num_args
505 arguments.
506
507 Futhermore the new pattern is also added to the vectorization information
508 structure VINFO and the old statement STMT_INFO is marked as unused while
509 the new statement is marked as used and the number of SLP uses of the new
510 statement is incremented.
511
512 The newly created SLP nodes are marked as SLP only and will be dissolved
513 if SLP is aborted.
514
515 The newly created gimple call is returned and the BB remains unchanged.
516
517 This default method is designed to only match against simple operands where
518 all the input and output types are the same.
519*/
520
521void
522complex_pattern::build (vec_info *vinfo)
523{
524 stmt_vec_info stmt_info;
525
526 auto_vec<tree> args;
527 args.create (this->m_num_args);
528 args.quick_grow_cleared (this->m_num_args);
529 slp_tree node;
530 unsigned ix;
531 stmt_vec_info call_stmt_info;
532 gcall *call_stmt = NULLnullptr;
533
534 /* Now modify the nodes themselves. */
535 FOR_EACH_VEC_ELT (this->m_workset, ix, node)for (ix = 0; (this->m_workset).iterate ((ix), &(node))
; ++(ix))
536 {
537 /* Calculate the location of the statement in NODE to replace. */
538 stmt_info = SLP_TREE_REPRESENTATIVE (node)(node)->representative;
539 stmt_vec_info reduc_def
540 = STMT_VINFO_REDUC_DEF (vect_orig_stmt (stmt_info))(vect_orig_stmt (stmt_info))->reduc_def;
541 gimple* old_stmt = STMT_VINFO_STMT (stmt_info)(stmt_info)->stmt;
542 tree lhs_old_stmt = gimple_get_lhs (old_stmt);
543 tree type = TREE_TYPE (lhs_old_stmt)((contains_struct_check ((lhs_old_stmt), (TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-vect-slp-patterns.c"
, 543, __FUNCTION__))->typed.type)
;
544
545 /* Create the argument set for use by gimple_build_call_internal_vec. */
546 for (unsigned i = 0; i < this->m_num_args; i++)
547 args[i] = lhs_old_stmt;
548
549 /* Create the new pattern statements. */
550 call_stmt = gimple_build_call_internal_vec (this->m_ifn, args);
551 tree var = make_temp_ssa_name (type, call_stmt, "slp_patt");
552 gimple_call_set_lhs (call_stmt, var);
553 gimple_set_location (call_stmt, gimple_location (old_stmt));
554 gimple_call_set_nothrow (call_stmt, true);
555
556 /* Adjust the book-keeping for the new and old statements for use during
557 SLP. This is required to get the right VF and statement during SLP
558 analysis. These changes are created after relevancy has been set for
559 the nodes as such we need to manually update them. Any changes will be
560 undone if SLP is cancelled. */
561 call_stmt_info
562 = vinfo->add_pattern_stmt (call_stmt, stmt_info);
563
564 /* Make sure to mark the representative statement pure_slp and
565 relevant and transfer reduction info. */
566 STMT_VINFO_RELEVANT (call_stmt_info)(call_stmt_info)->relevant = vect_used_in_scope;
567 STMT_SLP_TYPE (call_stmt_info)(call_stmt_info)->slp_type = pure_slp;
568 STMT_VINFO_REDUC_DEF (call_stmt_info)(call_stmt_info)->reduc_def = reduc_def;
569
570 gimple_set_bb (call_stmt, gimple_bb (stmt_info->stmt));
571 STMT_VINFO_VECTYPE (call_stmt_info)(call_stmt_info)->vectype = SLP_TREE_VECTYPE (node)(node)->vectype;
572 STMT_VINFO_SLP_VECT_ONLY_PATTERN (call_stmt_info)(call_stmt_info)->slp_vect_pattern_only_p = true;
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 SLP_TREE_REPRESENTATIVE (node)(node)->representative = call_stmt_info;
578 SLP_TREE_LANE_PERMUTATION (node)(node)->lane_permutation.release ();
579 SLP_TREE_CODE (node)(node)->code = CALL_EXPR;
580 }
581}
582
583/*******************************************************************************
584 * complex_add_pattern class
585 ******************************************************************************/
586
587class complex_add_pattern : public complex_pattern
588{
589 protected:
590 complex_add_pattern (slp_tree *node, vec<slp_tree> *m_ops, internal_fn ifn)
591 : complex_pattern (node, m_ops, ifn)
592 {
593 this->m_num_args = 2;
594 }
595
596 public:
597 void build (vec_info *);
598 static internal_fn
599 matches (complex_operation_t op, slp_tree_to_load_perm_map_t *, slp_tree *,
600 vec<slp_tree> *);
601
602 static vect_pattern*
603 recognize (slp_tree_to_load_perm_map_t *, slp_tree *);
604
605 static vect_pattern*
606 mkInstance (slp_tree *node, vec<slp_tree> *m_ops, internal_fn ifn)
607 {
608 return new complex_add_pattern (node, m_ops, ifn);
609 }
610};
611
612/* Perform a replacement of the detected complex add pattern with the new
613 instruction sequences. */
614
615void
616complex_add_pattern::build (vec_info *vinfo)
617{
618 SLP_TREE_CHILDREN (*this->m_node)(*this->m_node)->children.reserve_exact (2);
619
620 slp_tree node = this->m_ops[0];
621 vec<slp_tree> children = SLP_TREE_CHILDREN (node)(node)->children;
622
623 /* First re-arrange the children. */
624 SLP_TREE_CHILDREN (*this->m_node)(*this->m_node)->children[0] = children[0];
625 SLP_TREE_CHILDREN (*this->m_node)(*this->m_node)->children[1] =
626 vect_build_swap_evenodd_node (children[1]);
627
628 SLP_TREE_REF_COUNT (SLP_TREE_CHILDREN (*this->m_node)[0])((*this->m_node)->children[0])->refcnt++;
629 SLP_TREE_REF_COUNT (SLP_TREE_CHILDREN (*this->m_node)[1])((*this->m_node)->children[1])->refcnt++;
630 vect_free_slp_tree (this->m_ops[0]);
631 vect_free_slp_tree (this->m_ops[1]);
632
633 complex_pattern::build (vinfo);
634}
635
636/* Pattern matcher for trying to match complex addition pattern in SLP tree.
637
638 If no match is found then IFN is set to IFN_LAST.
639 This function matches the patterns shaped as:
640
641 c[i] = a[i] - b[i+1];
642 c[i+1] = a[i+1] + b[i];
643
644 If a match occurred then TRUE is returned, else FALSE. The initial match is
645 expected to be in OP1 and the initial match operands in args0. */
646
647internal_fn
648complex_add_pattern::matches (complex_operation_t op,
649 slp_tree_to_load_perm_map_t *perm_cache,
650 slp_tree *node, vec<slp_tree> *ops)
651{
652 internal_fn ifn = IFN_LAST;
653
654 /* Find the two components. Rotation in the complex plane will modify
655 the operations:
656
657 * Rotation 0: + +
658 * Rotation 90: - +
659 * Rotation 180: - -
660 * Rotation 270: + -
661
662 Rotation 0 and 180 can be handled by normal SIMD code, so we don't need
663 to care about them here. */
664 if (op == MINUS_PLUS)
665 ifn = IFN_COMPLEX_ADD_ROT90;
666 else if (op == PLUS_MINUS)
667 ifn = IFN_COMPLEX_ADD_ROT270;
668 else
669 return ifn;
670
671 /* verify that there is a permute, otherwise this isn't a pattern we
672 we support. */
673 gcc_assert (ops->length () == 2)((void)(!(ops->length () == 2) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-vect-slp-patterns.c"
, 673, __FUNCTION__), 0 : 0))
;
674
675 vec<slp_tree> children = SLP_TREE_CHILDREN ((*ops)[0])((*ops)[0])->children;
676
677 /* First node must be unpermuted. */
678 if (linear_loads_p (perm_cache, children[0]) != PERM_EVENODD)
679 return IFN_LAST;
680
681 /* Second node must be permuted. */
682 if (linear_loads_p (perm_cache, children[1]) != PERM_ODDEVEN)
683 return IFN_LAST;
684
685 if (!vect_pattern_validate_optab (ifn, *node))
686 return IFN_LAST;
687
688 return ifn;
689}
690
691/* Attempt to recognize a complex add pattern. */
692
693vect_pattern*
694complex_add_pattern::recognize (slp_tree_to_load_perm_map_t *perm_cache,
695 slp_tree *node)
696{
697 auto_vec<slp_tree> ops;
698 complex_operation_t op
699 = vect_detect_pair_op (*node, true, &ops);
700 internal_fn ifn
701 = complex_add_pattern::matches (op, perm_cache, node, &ops);
702 if (ifn == IFN_LAST)
703 return NULLnullptr;
704
705 return new complex_add_pattern (node, &ops, ifn);
706}
707
708/*******************************************************************************
709 * complex_mul_pattern
710 ******************************************************************************/
711
712/* Check to see if either of the trees in ARGS are a NEGATE_EXPR. If the first
713 child (args[0]) is a NEGATE_EXPR then NEG_FIRST_P is set to TRUE.
714
715 If a negate is found then the values in ARGS are reordered such that the
716 negate node is always the second one and the entry is replaced by the child
717 of the negate node. */
718
719static inline bool
720vect_normalize_conj_loc (vec<slp_tree> &args, bool *neg_first_p = NULLnullptr)
721{
722 gcc_assert (args.length () == 2)((void)(!(args.length () == 2) ? fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-vect-slp-patterns.c"
, 722, __FUNCTION__), 0 : 0))
;
723 bool neg_found = false;
724
725 if (vect_match_expression_p (args[0], NEGATE_EXPR))
726 {
727 std::swap (args[0], args[1]);
728 neg_found = true;
729 if (neg_first_p)
730 *neg_first_p = true;
731 }
732 else if (vect_match_expression_p (args[1], NEGATE_EXPR))
733 {
734 neg_found = true;
735 if (neg_first_p)
736 *neg_first_p = false;
737 }
738
739 if (neg_found)
740 args[1] = SLP_TREE_CHILDREN (args[1])(args[1])->children[0];
741
742 return neg_found;
743}
744
745/* Helper function to check if PERM is KIND or PERM_TOP. */
746
747static inline bool
748is_eq_or_top (complex_perm_kinds_t perm, complex_perm_kinds_t kind)
749{
750 return perm == kind || perm == PERM_TOP;
751}
752
753/* Helper function that checks to see if LEFT_OP and RIGHT_OP are both MULT_EXPR
754 nodes but also that they represent an operation that is either a complex
755 multiplication or a complex multiplication by conjugated value.
756
757 Of the negation is expected to be in the first half of the tree (As required
758 by an FMS pattern) then NEG_FIRST is true. If the operation is a conjugate
759 operation then CONJ_FIRST_OPERAND is set to indicate whether the first or
760 second operand contains the conjugate operation. */
761
762static inline bool
763vect_validate_multiplication (slp_tree_to_load_perm_map_t *perm_cache,
764 const vec<slp_tree> &left_op,
765 const vec<slp_tree> &right_op,
766 bool neg_first, bool *conj_first_operand,
767 bool fms)
768{
769 /* The presence of a negation indicates that we have either a conjugate or a
770 rotation. We need to distinguish which one. */
771 *conj_first_operand = false;
772 complex_perm_kinds_t kind;
773
774 /* Complex conjugates have the negation on the imaginary part of the
775 number where rotations affect the real component. So check if the
776 negation is on a dup of lane 1. */
777 if (fms)
778 {
779 /* Canonicalization for fms is not consistent. So have to test both
780 variants to be sure. This needs to be fixed in the mid-end so
781 this part can be simpler. */
782 kind = linear_loads_p (perm_cache, right_op[0]);
783 if (!((is_eq_or_top (linear_loads_p (perm_cache, right_op[0]), PERM_ODDODD)
784 && is_eq_or_top (linear_loads_p (perm_cache, right_op[1]),
785 PERM_ODDEVEN))
786 || (kind == PERM_ODDEVEN
787 && is_eq_or_top (linear_loads_p (perm_cache, right_op[1]),
788 PERM_ODDODD))))
789 return false;
790 }
791 else
792 {
793 if (linear_loads_p (perm_cache, right_op[1]) != PERM_ODDODD
794 && !is_eq_or_top (linear_loads_p (perm_cache, right_op[0]),
795 PERM_ODDEVEN))
796 return false;
797 }
798
799 /* Deal with differences in indexes. */
800 int index1 = fms ? 1 : 0;
801 int index2 = fms ? 0 : 1;
802
803 /* Check if the conjugate is on the second first or second operand. The
804 order of the node with the conjugate value determines this, and the dup
805 node must be one of lane 0 of the same DR as the neg node. */
806 kind = linear_loads_p (perm_cache, left_op[index1]);
807 if (kind == PERM_TOP)
808 {
809 if (linear_loads_p (perm_cache, left_op[index2]) == PERM_EVENODD)
810 return true;
811 }
812 else if (kind == PERM_EVENODD && !neg_first)
813 {
814 if ((kind = linear_loads_p (perm_cache, left_op[index2])) != PERM_EVENEVEN)
815 return false;
816 return true;
817 }
818 else if (kind == PERM_EVENEVEN && neg_first)
819 {
820 if ((kind = linear_loads_p (perm_cache, left_op[index2])) != PERM_EVENODD)
Although the value stored to 'kind' is used in the enclosing expression, the value is never actually read from 'kind'
821 return false;
822
823 *conj_first_operand = true;
824 return true;
825 }
826 else
827 return false;
828
829 if (kind != PERM_EVENEVEN)
830 return false;
831
832 return true;
833}
834
835/* Helper function to help distinguish between a conjugate and a rotation in a
836 complex multiplication. The operations have similar shapes but the order of
837 the load permutes are different. This function returns TRUE when the order
838 is consistent with a multiplication or multiplication by conjugated
839 operand but returns FALSE if it's a multiplication by rotated operand. */
840
841static inline bool
842vect_validate_multiplication (slp_tree_to_load_perm_map_t *perm_cache,
843 const vec<slp_tree> &op,
844 complex_perm_kinds_t permKind)
845{
846 /* The left node is the more common case, test it first. */
847 if (!is_eq_or_top (linear_loads_p (perm_cache, op[0]), permKind))
848 {
849 if (!is_eq_or_top (linear_loads_p (perm_cache, op[1]), permKind))
850 return false;
851 }
852 return true;
853}
854
855/* This function combines two nodes containing only even and only odd lanes
856 together into a single node which contains the nodes in even/odd order
857 by using a lane permute.
858
859 The lanes in EVEN and ODD are duplicated 2 times inside the vectors.
860 So for a lanes = 4 EVEN contains {EVEN1, EVEN1, EVEN2, EVEN2}.
861
862 The tree REPRESENTATION is taken from the supplied REP along with the
863 vectype which must be the same between all three nodes.
864*/
865
866static slp_tree
867vect_build_combine_node (slp_tree even, slp_tree odd, slp_tree rep)
868{
869 vec<std::pair<unsigned, unsigned> > perm;
870 perm.create (SLP_TREE_LANES (rep)(rep)->lanes);
871
872 for (unsigned x = 0; x < SLP_TREE_LANES (rep)(rep)->lanes; x+=2)
873 {
874 perm.quick_push (std::make_pair (0, x));
875 perm.quick_push (std::make_pair (1, x+1));
876 }
877
878 slp_tree vnode = vect_create_new_slp_node (2, SLP_TREE_CODE (even)(even)->code);
879 SLP_TREE_CODE (vnode)(vnode)->code = VEC_PERM_EXPR;
880 SLP_TREE_LANE_PERMUTATION (vnode)(vnode)->lane_permutation = perm;
881
882 SLP_TREE_CHILDREN (vnode)(vnode)->children.create (2);
883 SLP_TREE_CHILDREN (vnode)(vnode)->children.quick_push (even);
884 SLP_TREE_CHILDREN (vnode)(vnode)->children.quick_push (odd);
885 SLP_TREE_REF_COUNT (even)(even)->refcnt++;
886 SLP_TREE_REF_COUNT (odd)(odd)->refcnt++;
887 SLP_TREE_REF_COUNT (vnode)(vnode)->refcnt = 1;
888
889 SLP_TREE_LANES (vnode)(vnode)->lanes = SLP_TREE_LANES (rep)(rep)->lanes;
890 gcc_assert (perm.length () == SLP_TREE_LANES (vnode))((void)(!(perm.length () == (vnode)->lanes) ? fancy_abort (
"/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-vect-slp-patterns.c"
, 890, __FUNCTION__), 0 : 0))
;
891 /* Representation is set to that of the current node as the vectorizer
892 can't deal with VEC_PERMs with no representation, as would be the
893 case with invariants. */
894 SLP_TREE_REPRESENTATIVE (vnode)(vnode)->representative = SLP_TREE_REPRESENTATIVE (rep)(rep)->representative;
895 SLP_TREE_VECTYPE (vnode)(vnode)->vectype = SLP_TREE_VECTYPE (rep)(rep)->vectype;
896 return vnode;
897}
898
899class complex_mul_pattern : public complex_pattern
900{
901 protected:
902 complex_mul_pattern (slp_tree *node, vec<slp_tree> *m_ops, internal_fn ifn)
903 : complex_pattern (node, m_ops, ifn)
904 {
905 this->m_num_args = 2;
906 }
907
908 public:
909 void build (vec_info *);
910 static internal_fn
911 matches (complex_operation_t op, slp_tree_to_load_perm_map_t *, slp_tree *,
912 vec<slp_tree> *);
913
914 static vect_pattern*
915 recognize (slp_tree_to_load_perm_map_t *, slp_tree *);
916
917 static vect_pattern*
918 mkInstance (slp_tree *node, vec<slp_tree> *m_ops, internal_fn ifn)
919 {
920 return new complex_mul_pattern (node, m_ops, ifn);
921 }
922
923};
924
925/* Pattern matcher for trying to match complex multiply and complex multiply
926 and accumulate pattern in SLP tree. If the operation matches then IFN
927 is set to the operation it matched and the arguments to the two
928 replacement statements are put in m_ops.
929
930 If no match is found then IFN is set to IFN_LAST and m_ops is unchanged.
931
932 This function matches the patterns shaped as:
933
934 double ax = (b[i+1] * a[i]);
935 double bx = (a[i+1] * b[i]);
936
937 c[i] = c[i] - ax;
938 c[i+1] = c[i+1] + bx;
939
940 If a match occurred then TRUE is returned, else FALSE. The initial match is
941 expected to be in OP1 and the initial match operands in args0. */
942
943internal_fn
944complex_mul_pattern::matches (complex_operation_t op,
945 slp_tree_to_load_perm_map_t *perm_cache,
946 slp_tree *node, vec<slp_tree> *ops)
947{
948 internal_fn ifn = IFN_LAST;
949
950 if (op != MINUS_PLUS)
951 return IFN_LAST;
952
953 auto childs = *ops;
954 auto l0node = SLP_TREE_CHILDREN (childs[0])(childs[0])->children;
955
956 bool mul0 = vect_match_expression_p (l0node[0], MULT_EXPR);
957 bool mul1 = vect_match_expression_p (l0node[1], MULT_EXPR);
958 if (!mul0 && !mul1)
959 return IFN_LAST;
960
961 /* Now operand2+4 may lead to another expression. */
962 auto_vec<slp_tree> left_op, right_op;
963 slp_tree add0 = NULLnullptr;
964
965 /* Check if we may be a multiply add. */
966 if (!mul0
967 && vect_match_expression_p (l0node[0], PLUS_EXPR))
968 {
969 auto vals = SLP_TREE_CHILDREN (l0node[0])(l0node[0])->children;
970 /* Check if it's a multiply, otherwise no idea what this is. */
971 if (!(mul0 = vect_match_expression_p (vals[1], MULT_EXPR)))
972 return IFN_LAST;
973
974 /* Check if the ADD is linear, otherwise it's not valid complex FMA. */
975 if (linear_loads_p (perm_cache, vals[0]) != PERM_EVENODD)
976 return IFN_LAST;
977
978 left_op.safe_splice (SLP_TREE_CHILDREN (vals[1])(vals[1])->children);
979 add0 = vals[0];
980 }
981 else
982 left_op.safe_splice (SLP_TREE_CHILDREN (l0node[0])(l0node[0])->children);
983
984 right_op.safe_splice (SLP_TREE_CHILDREN (l0node[1])(l0node[1])->children);
985
986 if (left_op.length () != 2
987 || right_op.length () != 2
988 || !mul0
989 || !mul1
990 || linear_loads_p (perm_cache, left_op[1]) == PERM_ODDEVEN)
991 return IFN_LAST;
992
993 bool neg_first = false;
994 bool conj_first_operand = false;
995 bool is_neg = vect_normalize_conj_loc (right_op, &neg_first);
996
997 if (!is_neg)
998 {
999 /* A multiplication needs to multiply agains the real pair, otherwise
1000 the pattern matches that of FMS. */
1001 if (!vect_validate_multiplication (perm_cache, left_op, PERM_EVENEVEN)
1002 || vect_normalize_conj_loc (left_op))
1003 return IFN_LAST;
1004 if (add0)
1005 ifn = IFN_COMPLEX_FMA;
1006 else
1007 ifn = IFN_COMPLEX_MUL;
1008 }
1009 else
1010 {
1011 if (!vect_validate_multiplication (perm_cache, left_op, right_op,
1012 neg_first, &conj_first_operand,
1013 false))
1014 return IFN_LAST;
1015
1016 if(add0)
1017 ifn = IFN_COMPLEX_FMA_CONJ;
1018 else
1019 ifn = IFN_COMPLEX_MUL_CONJ;
1020 }
1021
1022 if (!vect_pattern_validate_optab (ifn, *node))
1023 return IFN_LAST;
1024
1025 ops->truncate (0);
1026 ops->create (add0 ? 4 : 3);
1027
1028 if (add0)
1029 ops->quick_push (add0);
1030
1031 complex_perm_kinds_t kind = linear_loads_p (perm_cache, left_op[0]);
1032 if (kind == PERM_EVENODD)
1033 {
1034 ops->quick_push (left_op[1]);
1035 ops->quick_push (right_op[1]);
1036 ops->quick_push (left_op[0]);
1037 }
1038 else if (kind == PERM_TOP)
1039 {
1040 ops->quick_push (left_op[1]);
1041 ops->quick_push (right_op[1]);
1042 ops->quick_push (left_op[0]);
1043 }
1044 else if (kind == PERM_EVENEVEN && !conj_first_operand)
1045 {
1046 ops->quick_push (left_op[0]);
1047 ops->quick_push (right_op[0]);
1048 ops->quick_push (left_op[1]);
1049 }
1050 else
1051 {
1052 ops->quick_push (left_op[0]);
1053 ops->quick_push (right_op[1]);
1054 ops->quick_push (left_op[1]);
1055 }
1056
1057 return ifn;
1058}
1059
1060/* Attempt to recognize a complex mul pattern. */
1061
1062vect_pattern*
1063complex_mul_pattern::recognize (slp_tree_to_load_perm_map_t *perm_cache,
1064 slp_tree *node)
1065{
1066 auto_vec<slp_tree> ops;
1067 complex_operation_t op
1068 = vect_detect_pair_op (*node, true, &ops);
1069 internal_fn ifn
1070 = complex_mul_pattern::matches (op, perm_cache, node, &ops);
1071 if (ifn == IFN_LAST)
1072 return NULLnullptr;
1073
1074 return new complex_mul_pattern (node, &ops, ifn);
1075}
1076
1077/* Perform a replacement of the detected complex mul pattern with the new
1078 instruction sequences. */
1079
1080void
1081complex_mul_pattern::build (vec_info *vinfo)
1082{
1083 slp_tree node;
1084 unsigned i;
1085 switch (this->m_ifn)
1086 {
1087 case IFN_COMPLEX_MUL:
1088 case IFN_COMPLEX_MUL_CONJ:
1089 {
1090 slp_tree newnode
1091 = vect_build_combine_node (this->m_ops[0], this->m_ops[1],
1092 *this->m_node);
1093 SLP_TREE_REF_COUNT (this->m_ops[2])(this->m_ops[2])->refcnt++;
1094
1095 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (*this->m_node), i, node)for (i = 0; ((*this->m_node)->children).iterate ((i), &
(node)); ++(i))
1096 vect_free_slp_tree (node);
1097
1098 /* First re-arrange the children. */
1099 SLP_TREE_CHILDREN (*this->m_node)(*this->m_node)->children.reserve_exact (2);
1100 SLP_TREE_CHILDREN (*this->m_node)(*this->m_node)->children[0] = this->m_ops[2];
1101 SLP_TREE_CHILDREN (*this->m_node)(*this->m_node)->children[1] = newnode;
1102 break;
1103 }
1104 case IFN_COMPLEX_FMA:
1105 case IFN_COMPLEX_FMA_CONJ:
1106 {
1107 SLP_TREE_REF_COUNT (this->m_ops[0])(this->m_ops[0])->refcnt++;
1108 slp_tree newnode
1109 = vect_build_combine_node (this->m_ops[1], this->m_ops[2],
1110 *this->m_node);
1111 SLP_TREE_REF_COUNT (this->m_ops[3])(this->m_ops[3])->refcnt++;
1112
1113 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (*this->m_node), i, node)for (i = 0; ((*this->m_node)->children).iterate ((i), &
(node)); ++(i))
1114 vect_free_slp_tree (node);
1115
1116 /* First re-arrange the children. */
1117 SLP_TREE_CHILDREN (*this->m_node)(*this->m_node)->children.safe_grow (3);
1118 SLP_TREE_CHILDREN (*this->m_node)(*this->m_node)->children[0] = this->m_ops[0];
1119 SLP_TREE_CHILDREN (*this->m_node)(*this->m_node)->children[1] = this->m_ops[3];
1120 SLP_TREE_CHILDREN (*this->m_node)(*this->m_node)->children[2] = newnode;
1121
1122 /* Tell the builder to expect an extra argument. */
1123 this->m_num_args++;
1124 break;
1125 }
1126 default:
1127 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-vect-slp-patterns.c"
, 1127, __FUNCTION__))
;
1128 }
1129
1130 /* And then rewrite the node itself. */
1131 complex_pattern::build (vinfo);
1132}
1133
1134/*******************************************************************************
1135 * complex_fms_pattern class
1136 ******************************************************************************/
1137
1138class complex_fms_pattern : public complex_pattern
1139{
1140 protected:
1141 complex_fms_pattern (slp_tree *node, vec<slp_tree> *m_ops, internal_fn ifn)
1142 : complex_pattern (node, m_ops, ifn)
1143 {
1144 this->m_num_args = 3;
1145 }
1146
1147 public:
1148 void build (vec_info *);
1149 static internal_fn
1150 matches (complex_operation_t op, slp_tree_to_load_perm_map_t *, slp_tree *,
1151 vec<slp_tree> *);
1152
1153 static vect_pattern*
1154 recognize (slp_tree_to_load_perm_map_t *, slp_tree *);
1155
1156 static vect_pattern*
1157 mkInstance (slp_tree *node, vec<slp_tree> *m_ops, internal_fn ifn)
1158 {
1159 return new complex_fms_pattern (node, m_ops, ifn);
1160 }
1161};
1162
1163
1164/* Pattern matcher for trying to match complex multiply and subtract pattern
1165 in SLP tree. If the operation matches then IFN is set to the operation
1166 it matched and the arguments to the two replacement statements are put in
1167 m_ops.
1168
1169 If no match is found then IFN is set to IFN_LAST and m_ops is unchanged.
1170
1171 This function matches the patterns shaped as:
1172
1173 double ax = (b[i+1] * a[i]) + (b[i] * a[i]);
1174 double bx = (a[i+1] * b[i]) - (a[i+1] * b[i+1]);
1175
1176 c[i] = c[i] - ax;
1177 c[i+1] = c[i+1] + bx;
1178
1179 If a match occurred then TRUE is returned, else FALSE. The initial match is
1180 expected to be in OP1 and the initial match operands in args0. */
1181
1182internal_fn
1183complex_fms_pattern::matches (complex_operation_t op,
1184 slp_tree_to_load_perm_map_t *perm_cache,
1185 slp_tree * ref_node, vec<slp_tree> *ops)
1186{
1187 internal_fn ifn = IFN_LAST;
1188
1189 /* We need to ignore the two_operands nodes that may also match,
1190 for that we can check if they have any scalar statements and also
1191 check that it's not a permute node as we're looking for a normal
1192 MINUS_EXPR operation. */
1193 if (op != CMPLX_NONE)
1194 return IFN_LAST;
1195
1196 slp_tree root = *ref_node;
1197 if (!vect_match_expression_p (root, MINUS_EXPR))
1198 return IFN_LAST;
1199
1200 auto nodes = SLP_TREE_CHILDREN (root)(root)->children;
1201 if (!vect_match_expression_p (nodes[1], MULT_EXPR)
1202 || vect_detect_pair_op (nodes[0]) != PLUS_MINUS)
1203 return IFN_LAST;
1204
1205 auto childs = SLP_TREE_CHILDREN (nodes[0])(nodes[0])->children;
1206 auto l0node = SLP_TREE_CHILDREN (childs[0])(childs[0])->children;
1207
1208 /* Now operand2+4 may lead to another expression. */
1209 auto_vec<slp_tree> left_op, right_op;
1210 left_op.safe_splice (SLP_TREE_CHILDREN (l0node[1])(l0node[1])->children);
1211 right_op.safe_splice (SLP_TREE_CHILDREN (nodes[1])(nodes[1])->children);
1212
1213 /* If these nodes don't have any children then they're
1214 not ones we're interested in. */
1215 if (left_op.length () != 2
1216 || right_op.length () != 2
1217 || !vect_match_expression_p (l0node[1], MULT_EXPR))
1218 return IFN_LAST;
1219
1220 bool is_neg = vect_normalize_conj_loc (left_op);
1221
1222 bool conj_first_operand = false;
1223 if (!vect_validate_multiplication (perm_cache, right_op, left_op, false,
1224 &conj_first_operand, true))
1225 return IFN_LAST;
1226
1227 if (!is_neg)
1228 ifn = IFN_COMPLEX_FMS;
1229 else if (is_neg)
1230 ifn = IFN_COMPLEX_FMS_CONJ;
1231
1232 if (!vect_pattern_validate_optab (ifn, *ref_node))
1233 return IFN_LAST;
1234
1235 ops->truncate (0);
1236 ops->create (4);
1237
1238 complex_perm_kinds_t kind = linear_loads_p (perm_cache, right_op[0]);
1239 if (kind == PERM_EVENODD)
1240 {
1241 ops->quick_push (l0node[0]);
1242 ops->quick_push (right_op[0]);
1243 ops->quick_push (right_op[1]);
1244 ops->quick_push (left_op[1]);
1245 }
1246 else if (kind == PERM_TOP)
1247 {
1248 ops->quick_push (l0node[0]);
1249 ops->quick_push (right_op[1]);
1250 ops->quick_push (right_op[0]);
1251 ops->quick_push (left_op[0]);
1252 }
1253 else if (kind == PERM_EVENEVEN && !is_neg)
1254 {
1255 ops->quick_push (l0node[0]);
1256 ops->quick_push (right_op[1]);
1257 ops->quick_push (right_op[0]);
1258 ops->quick_push (left_op[0]);
1259 }
1260 else
1261 {
1262 ops->quick_push (l0node[0]);
1263 ops->quick_push (right_op[1]);
1264 ops->quick_push (right_op[0]);
1265 ops->quick_push (left_op[1]);
1266 }
1267
1268 return ifn;
1269}
1270
1271/* Attempt to recognize a complex mul pattern. */
1272
1273vect_pattern*
1274complex_fms_pattern::recognize (slp_tree_to_load_perm_map_t *perm_cache,
1275 slp_tree *node)
1276{
1277 auto_vec<slp_tree> ops;
1278 complex_operation_t op
1279 = vect_detect_pair_op (*node, true, &ops);
1280 internal_fn ifn
1281 = complex_fms_pattern::matches (op, perm_cache, node, &ops);
1282 if (ifn == IFN_LAST)
1283 return NULLnullptr;
1284
1285 return new complex_fms_pattern (node, &ops, ifn);
1286}
1287
1288/* Perform a replacement of the detected complex mul pattern with the new
1289 instruction sequences. */
1290
1291void
1292complex_fms_pattern::build (vec_info *vinfo)
1293{
1294 slp_tree node;
1295 unsigned i;
1296 slp_tree newnode =
1297 vect_build_combine_node (this->m_ops[2], this->m_ops[3], *this->m_node);
1298 SLP_TREE_REF_COUNT (this->m_ops[0])(this->m_ops[0])->refcnt++;
1299 SLP_TREE_REF_COUNT (this->m_ops[1])(this->m_ops[1])->refcnt++;
1300
1301 FOR_EACH_VEC_ELT (SLP_TREE_CHILDREN (*this->m_node), i, node)for (i = 0; ((*this->m_node)->children).iterate ((i), &
(node)); ++(i))
1302 vect_free_slp_tree (node);
1303
1304 SLP_TREE_CHILDREN (*this->m_node)(*this->m_node)->children.release ();
1305 SLP_TREE_CHILDREN (*this->m_node)(*this->m_node)->children.create (3);
1306
1307 /* First re-arrange the children. */
1308 SLP_TREE_CHILDREN (*this->m_node)(*this->m_node)->children.quick_push (this->m_ops[0]);
1309 SLP_TREE_CHILDREN (*this->m_node)(*this->m_node)->children.quick_push (this->m_ops[1]);
1310 SLP_TREE_CHILDREN (*this->m_node)(*this->m_node)->children.quick_push (newnode);
1311
1312 /* And then rewrite the node itself. */
1313 complex_pattern::build (vinfo);
1314}
1315
1316/*******************************************************************************
1317 * complex_operations_pattern class
1318 ******************************************************************************/
1319
1320/* This function combines all the existing pattern matchers above into one class
1321 that shares the functionality between them. The initial match is shared
1322 between all complex operations. */
1323
1324class complex_operations_pattern : public complex_pattern
1325{
1326 protected:
1327 complex_operations_pattern (slp_tree *node, vec<slp_tree> *m_ops,
1328 internal_fn ifn)
1329 : complex_pattern (node, m_ops, ifn)
1330 {
1331 this->m_num_args = 0;
1332 }
1333
1334 public:
1335 void build (vec_info *);
1336 static internal_fn
1337 matches (complex_operation_t op, slp_tree_to_load_perm_map_t *, slp_tree *,
1338 vec<slp_tree> *);
1339
1340 static vect_pattern*
1341 recognize (slp_tree_to_load_perm_map_t *, slp_tree *);
1342};
1343
1344/* Dummy matches implementation for proxy object. */
1345
1346internal_fn
1347complex_operations_pattern::
1348matches (complex_operation_t /* op */,
1349 slp_tree_to_load_perm_map_t * /* perm_cache */,
1350 slp_tree * /* ref_node */, vec<slp_tree> * /* ops */)
1351{
1352 return IFN_LAST;
1353}
1354
1355/* Attempt to recognize a complex mul pattern. */
1356
1357vect_pattern*
1358complex_operations_pattern::recognize (slp_tree_to_load_perm_map_t *perm_cache,
1359 slp_tree *node)
1360{
1361 auto_vec<slp_tree> ops;
1362 complex_operation_t op
1363 = vect_detect_pair_op (*node, true, &ops);
1364 internal_fn ifn = IFN_LAST;
1365
1366 ifn = complex_fms_pattern::matches (op, perm_cache, node, &ops);
1367 if (ifn != IFN_LAST)
1368 return complex_fms_pattern::mkInstance (node, &ops, ifn);
1369
1370 ifn = complex_mul_pattern::matches (op, perm_cache, node, &ops);
1371 if (ifn != IFN_LAST)
1372 return complex_mul_pattern::mkInstance (node, &ops, ifn);
1373
1374 ifn = complex_add_pattern::matches (op, perm_cache, node, &ops);
1375 if (ifn != IFN_LAST)
1376 return complex_add_pattern::mkInstance (node, &ops, ifn);
1377
1378 return NULLnullptr;
1379}
1380
1381/* Dummy implementation of build. */
1382
1383void
1384complex_operations_pattern::build (vec_info * /* vinfo */)
1385{
1386 gcc_unreachable ()(fancy_abort ("/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-vect-slp-patterns.c"
, 1386, __FUNCTION__))
;
1387}
1388
1389
1390/* The addsub_pattern. */
1391
1392class addsub_pattern : public vect_pattern
1393{
1394 public:
1395 addsub_pattern (slp_tree *node, internal_fn ifn)
1396 : vect_pattern (node, NULLnullptr, ifn) {};
1397
1398 void build (vec_info *);
1399
1400 static vect_pattern*
1401 recognize (slp_tree_to_load_perm_map_t *, slp_tree *);
1402};
1403
1404vect_pattern *
1405addsub_pattern::recognize (slp_tree_to_load_perm_map_t *, slp_tree *node_)
1406{
1407 slp_tree node = *node_;
1408 if (SLP_TREE_CODE (node)(node)->code != VEC_PERM_EXPR
1409 || SLP_TREE_CHILDREN (node)(node)->children.length () != 2
1410 || SLP_TREE_LANE_PERMUTATION (node)(node)->lane_permutation.length () % 2)
1411 return NULLnullptr;
1412
1413 /* Match a blend of a plus and a minus op with the same number of plus and
1414 minus lanes on the same operands. */
1415 unsigned l0 = SLP_TREE_LANE_PERMUTATION (node)(node)->lane_permutation[0].first;
1416 unsigned l1 = SLP_TREE_LANE_PERMUTATION (node)(node)->lane_permutation[1].first;
1417 if (l0 == l1)
1418 return NULLnullptr;
1419 bool l0add_p = vect_match_expression_p (SLP_TREE_CHILDREN (node)(node)->children[l0],
1420 PLUS_EXPR);
1421 if (!l0add_p
1422 && !vect_match_expression_p (SLP_TREE_CHILDREN (node)(node)->children[l0], MINUS_EXPR))
1423 return NULLnullptr;
1424 bool l1add_p = vect_match_expression_p (SLP_TREE_CHILDREN (node)(node)->children[l1],
1425 PLUS_EXPR);
1426 if (!l1add_p
1427 && !vect_match_expression_p (SLP_TREE_CHILDREN (node)(node)->children[l1], MINUS_EXPR))
1428 return NULLnullptr;
1429
1430 slp_tree l0node = SLP_TREE_CHILDREN (node)(node)->children[l0];
1431 slp_tree l1node = SLP_TREE_CHILDREN (node)(node)->children[l1];
1432 if (!((SLP_TREE_CHILDREN (l0node)(l0node)->children[0] == SLP_TREE_CHILDREN (l1node)(l1node)->children[0]
1433 && SLP_TREE_CHILDREN (l0node)(l0node)->children[1] == SLP_TREE_CHILDREN (l1node)(l1node)->children[1])
1434 || (SLP_TREE_CHILDREN (l0node)(l0node)->children[0] == SLP_TREE_CHILDREN (l1node)(l1node)->children[1]
1435 && SLP_TREE_CHILDREN (l0node)(l0node)->children[1] == SLP_TREE_CHILDREN (l1node)(l1node)->children[0])))
1436 return NULLnullptr;
1437
1438 for (unsigned i = 0; i < SLP_TREE_LANE_PERMUTATION (node)(node)->lane_permutation.length (); ++i)
1439 {
1440 std::pair<unsigned, unsigned> perm = SLP_TREE_LANE_PERMUTATION (node)(node)->lane_permutation[i];
1441 /* It has to be alternating -, +, -,
1442 While we could permute the .ADDSUB inputs and the .ADDSUB output
1443 that's only profitable over the add + sub + blend if at least
1444 one of the permute is optimized which we can't determine here. */
1445 if (perm.first != ((i & 1) ? l1 : l0)
1446 || perm.second != i)
1447 return NULLnullptr;
1448 }
1449
1450 /* Now we have either { -, +, -, + ... } (!l0add_p) or { +, -, +, - ... }
1451 (l0add_p), see whether we have FMA variants. */
1452 if (!l0add_p
1453 && vect_match_expression_p (SLP_TREE_CHILDREN (l0node)(l0node)->children[0], MULT_EXPR))
1454 {
1455 /* (c * d) -+ a */
1456 if (vect_pattern_validate_optab (IFN_VEC_FMADDSUB, node))
1457 return new addsub_pattern (node_, IFN_VEC_FMADDSUB);
1458 }
1459 else if (l0add_p
1460 && vect_match_expression_p (SLP_TREE_CHILDREN (l1node)(l1node)->children[0], MULT_EXPR))
1461 {
1462 /* (c * d) +- a */
1463 if (vect_pattern_validate_optab (IFN_VEC_FMSUBADD, node))
1464 return new addsub_pattern (node_, IFN_VEC_FMSUBADD);
1465 }
1466
1467 if (!l0add_p && vect_pattern_validate_optab (IFN_VEC_ADDSUB, node))
1468 return new addsub_pattern (node_, IFN_VEC_ADDSUB);
1469
1470 return NULLnullptr;
1471}
1472
1473void
1474addsub_pattern::build (vec_info *vinfo)
1475{
1476 slp_tree node = *m_node;
1477
1478 unsigned l0 = SLP_TREE_LANE_PERMUTATION (node)(node)->lane_permutation[0].first;
1479 unsigned l1 = SLP_TREE_LANE_PERMUTATION (node)(node)->lane_permutation[1].first;
1480
1481 switch (m_ifn)
1482 {
1483 case IFN_VEC_ADDSUB:
1484 {
1485 slp_tree sub = SLP_TREE_CHILDREN (node)(node)->children[l0];
1486 slp_tree add = SLP_TREE_CHILDREN (node)(node)->children[l1];
1487
1488 /* Modify the blend node in-place. */
1489 SLP_TREE_CHILDREN (node)(node)->children[0] = SLP_TREE_CHILDREN (sub)(sub)->children[0];
1490 SLP_TREE_CHILDREN (node)(node)->children[1] = SLP_TREE_CHILDREN (sub)(sub)->children[1];
1491 SLP_TREE_REF_COUNT (SLP_TREE_CHILDREN (node)[0])((node)->children[0])->refcnt++;
1492 SLP_TREE_REF_COUNT (SLP_TREE_CHILDREN (node)[1])((node)->children[1])->refcnt++;
1493
1494 /* Build IFN_VEC_ADDSUB from the sub representative operands. */
1495 stmt_vec_info rep = SLP_TREE_REPRESENTATIVE (sub)(sub)->representative;
1496 gcall *call = gimple_build_call_internal (IFN_VEC_ADDSUB, 2,
1497 gimple_assign_rhs1 (rep->stmt),
1498 gimple_assign_rhs2 (rep->stmt));
1499 gimple_call_set_lhs (call, make_ssa_name
1500 (TREE_TYPE (gimple_assign_lhs (rep->stmt))((contains_struct_check ((gimple_assign_lhs (rep->stmt)), (
TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-vect-slp-patterns.c"
, 1500, __FUNCTION__))->typed.type)
));
1501 gimple_call_set_nothrow (call, true);
1502 gimple_set_bb (call, gimple_bb (rep->stmt));
1503 stmt_vec_info new_rep = vinfo->add_pattern_stmt (call, rep);
1504 SLP_TREE_REPRESENTATIVE (node)(node)->representative = new_rep;
1505 STMT_VINFO_RELEVANT (new_rep)(new_rep)->relevant = vect_used_in_scope;
1506 STMT_SLP_TYPE (new_rep)(new_rep)->slp_type = pure_slp;
1507 STMT_VINFO_VECTYPE (new_rep)(new_rep)->vectype = SLP_TREE_VECTYPE (node)(node)->vectype;
1508 STMT_VINFO_SLP_VECT_ONLY_PATTERN (new_rep)(new_rep)->slp_vect_pattern_only_p = true;
1509 STMT_VINFO_REDUC_DEF (new_rep)(new_rep)->reduc_def = STMT_VINFO_REDUC_DEF (vect_orig_stmt (rep))(vect_orig_stmt (rep))->reduc_def;
1510 SLP_TREE_CODE (node)(node)->code = ERROR_MARK;
1511 SLP_TREE_LANE_PERMUTATION (node)(node)->lane_permutation.release ();
1512
1513 vect_free_slp_tree (sub);
1514 vect_free_slp_tree (add);
1515 break;
1516 }
1517 case IFN_VEC_FMADDSUB:
1518 case IFN_VEC_FMSUBADD:
1519 {
1520 slp_tree sub, add;
1521 if (m_ifn == IFN_VEC_FMADDSUB)
1522 {
1523 sub = SLP_TREE_CHILDREN (node)(node)->children[l0];
1524 add = SLP_TREE_CHILDREN (node)(node)->children[l1];
1525 }
1526 else /* m_ifn == IFN_VEC_FMSUBADD */
1527 {
1528 sub = SLP_TREE_CHILDREN (node)(node)->children[l1];
1529 add = SLP_TREE_CHILDREN (node)(node)->children[l0];
1530 }
1531 slp_tree mul = SLP_TREE_CHILDREN (sub)(sub)->children[0];
1532 /* Modify the blend node in-place. */
1533 SLP_TREE_CHILDREN (node)(node)->children.safe_grow (3, true);
1534 SLP_TREE_CHILDREN (node)(node)->children[0] = SLP_TREE_CHILDREN (mul)(mul)->children[0];
1535 SLP_TREE_CHILDREN (node)(node)->children[1] = SLP_TREE_CHILDREN (mul)(mul)->children[1];
1536 SLP_TREE_CHILDREN (node)(node)->children[2] = SLP_TREE_CHILDREN (sub)(sub)->children[1];
1537 SLP_TREE_REF_COUNT (SLP_TREE_CHILDREN (node)[0])((node)->children[0])->refcnt++;
1538 SLP_TREE_REF_COUNT (SLP_TREE_CHILDREN (node)[1])((node)->children[1])->refcnt++;
1539 SLP_TREE_REF_COUNT (SLP_TREE_CHILDREN (node)[2])((node)->children[2])->refcnt++;
1540
1541 /* Build IFN_VEC_FMADDSUB from the mul/sub representative operands. */
1542 stmt_vec_info srep = SLP_TREE_REPRESENTATIVE (sub)(sub)->representative;
1543 stmt_vec_info mrep = SLP_TREE_REPRESENTATIVE (mul)(mul)->representative;
1544 gcall *call = gimple_build_call_internal (m_ifn, 3,
1545 gimple_assign_rhs1 (mrep->stmt),
1546 gimple_assign_rhs2 (mrep->stmt),
1547 gimple_assign_rhs2 (srep->stmt));
1548 gimple_call_set_lhs (call, make_ssa_name
1549 (TREE_TYPE (gimple_assign_lhs (srep->stmt))((contains_struct_check ((gimple_assign_lhs (srep->stmt)),
(TS_TYPED), "/home/marxin/BIG/buildbot/buildworker/marxinbox-gcc-clang-static-analyzer/build/gcc/tree-vect-slp-patterns.c"
, 1549, __FUNCTION__))->typed.type)
));
1550 gimple_call_set_nothrow (call, true);
1551 gimple_set_bb (call, gimple_bb (srep->stmt));
1552 stmt_vec_info new_rep = vinfo->add_pattern_stmt (call, srep);
1553 SLP_TREE_REPRESENTATIVE (node)(node)->representative = new_rep;
1554 STMT_VINFO_RELEVANT (new_rep)(new_rep)->relevant = vect_used_in_scope;
1555 STMT_SLP_TYPE (new_rep)(new_rep)->slp_type = pure_slp;
1556 STMT_VINFO_VECTYPE (new_rep)(new_rep)->vectype = SLP_TREE_VECTYPE (node)(node)->vectype;
1557 STMT_VINFO_SLP_VECT_ONLY_PATTERN (new_rep)(new_rep)->slp_vect_pattern_only_p = true;
1558 STMT_VINFO_REDUC_DEF (new_rep)(new_rep)->reduc_def = STMT_VINFO_REDUC_DEF (vect_orig_stmt (srep))(vect_orig_stmt (srep))->reduc_def;
1559 SLP_TREE_CODE (node)(node)->code = ERROR_MARK;
1560 SLP_TREE_LANE_PERMUTATION (node)(node)->lane_permutation.release ();
1561
1562 vect_free_slp_tree (sub);
1563 vect_free_slp_tree (add);
1564 break;
1565 }
1566 default:;
1567 }
1568}
1569
1570/*******************************************************************************
1571 * Pattern matching definitions
1572 ******************************************************************************/
1573
1574#define SLP_PATTERN(x) &x::recognize
1575vect_pattern_decl_t slp_patterns[]
1576{
1577 /* For least amount of back-tracking and more efficient matching
1578 order patterns from the largest to the smallest. Especially if they
1579 overlap in what they can detect. */
1580
1581 SLP_PATTERN (complex_operations_pattern),
1582 SLP_PATTERN (addsub_pattern)
1583};
1584#undef SLP_PATTERN
1585
1586/* Set the number of SLP pattern matchers available. */
1587size_t num__slp_patterns = sizeof(slp_patterns)/sizeof(vect_pattern_decl_t);