Line data Source code
1 : /* Vectorizer
2 : Copyright (C) 2003-2026 Free Software Foundation, Inc.
3 : Contributed by Dorit Naishlos <dorit@il.ibm.com>
4 :
5 : This file is part of GCC.
6 :
7 : GCC is free software; you can redistribute it and/or modify it under
8 : the terms of the GNU General Public License as published by the Free
9 : Software Foundation; either version 3, or (at your option) any later
10 : version.
11 :
12 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : for more details.
16 :
17 : You should have received a copy of the GNU General Public License
18 : along with GCC; see the file COPYING3. If not see
19 : <http://www.gnu.org/licenses/>. */
20 :
21 : /* Loop and basic block vectorizer.
22 :
23 : This file contains drivers for the three vectorizers:
24 : (1) loop vectorizer (inter-iteration parallelism),
25 : (2) loop-aware SLP (intra-iteration parallelism) (invoked by the loop
26 : vectorizer)
27 : (3) BB vectorizer (out-of-loops), aka SLP
28 :
29 : The rest of the vectorizer's code is organized as follows:
30 : - tree-vect-loop.cc - loop specific parts such as reductions, etc. These are
31 : used by drivers (1) and (2).
32 : - tree-vect-loop-manip.cc - vectorizer's loop control-flow utilities, used by
33 : drivers (1) and (2).
34 : - tree-vect-slp.cc - BB vectorization specific analysis and transformation,
35 : used by drivers (2) and (3).
36 : - tree-vect-stmts.cc - statements analysis and transformation (used by all).
37 : - tree-vect-data-refs.cc - vectorizer specific data-refs analysis and
38 : manipulations (used by all).
39 : - tree-vect-patterns.cc - vectorizable code patterns detector (used by all)
40 :
41 : Here's a poor attempt at illustrating that:
42 :
43 : tree-vectorizer.cc:
44 : loop_vect() loop_aware_slp() slp_vect()
45 : | / \ /
46 : | / \ /
47 : tree-vect-loop.cc tree-vect-slp.cc
48 : | \ \ / / |
49 : | \ \/ / |
50 : | \ /\ / |
51 : | \ / \ / |
52 : tree-vect-stmts.cc tree-vect-data-refs.cc
53 : \ /
54 : tree-vect-patterns.cc
55 : */
56 :
57 : #include "config.h"
58 : #include "system.h"
59 : #include "coretypes.h"
60 : #include "backend.h"
61 : #include "tree.h"
62 : #include "gimple.h"
63 : #include "predict.h"
64 : #include "tree-pass.h"
65 : #include "ssa.h"
66 : #include "cgraph.h"
67 : #include "fold-const.h"
68 : #include "stor-layout.h"
69 : #include "gimple-iterator.h"
70 : #include "gimple-walk.h"
71 : #include "tree-ssa-loop-manip.h"
72 : #include "tree-ssa-loop-niter.h"
73 : #include "tree-cfg.h"
74 : #include "cfgloop.h"
75 : #include "tree-vectorizer.h"
76 : #include "tree-ssa-propagate.h"
77 : #include "dbgcnt.h"
78 : #include "tree-scalar-evolution.h"
79 : #include "stringpool.h"
80 : #include "attribs.h"
81 : #include "gimple-pretty-print.h"
82 : #include "opt-problem.h"
83 : #include "internal-fn.h"
84 : #include "tree-ssa-sccvn.h"
85 : #include "tree-into-ssa.h"
86 : #include "gimple-range.h"
87 :
88 : /* Loop or bb location, with hotness information. */
89 : dump_user_location_t vect_location;
90 :
91 : /* auto_purge_vect_location's dtor: reset the vect_location
92 : global, to avoid stale location_t values that could reference
93 : GC-ed blocks. */
94 :
95 1408300 : auto_purge_vect_location::~auto_purge_vect_location ()
96 : {
97 1408300 : vect_location = dump_user_location_t ();
98 1408300 : }
99 :
100 : /* Dump a cost entry according to args to F. */
101 :
102 : void
103 232638 : dump_stmt_cost (FILE *f, int count, enum vect_cost_for_stmt kind,
104 : stmt_vec_info stmt_info, slp_tree node, tree,
105 : int misalign, unsigned cost,
106 : enum vect_cost_model_location where)
107 : {
108 232638 : if (stmt_info)
109 : {
110 209846 : print_gimple_expr (f, STMT_VINFO_STMT (stmt_info), 0, TDF_SLIM);
111 209846 : fprintf (f, " ");
112 : }
113 22792 : else if (node)
114 22182 : fprintf (f, "node %p ", (void *)node);
115 : else
116 610 : fprintf (f, "<unknown> ");
117 232638 : fprintf (f, "%d times ", count);
118 232638 : const char *ks = "unknown";
119 232638 : switch (kind)
120 : {
121 52558 : case scalar_stmt:
122 52558 : ks = "scalar_stmt";
123 52558 : break;
124 38710 : case scalar_load:
125 38710 : ks = "scalar_load";
126 38710 : break;
127 29168 : case scalar_store:
128 29168 : ks = "scalar_store";
129 29168 : break;
130 37626 : case vector_stmt:
131 37626 : ks = "vector_stmt";
132 37626 : break;
133 23411 : case vector_load:
134 23411 : ks = "vector_load";
135 23411 : break;
136 0 : case vector_gather_load:
137 0 : ks = "vector_gather_load";
138 0 : break;
139 8307 : case unaligned_load:
140 8307 : ks = "unaligned_load";
141 8307 : break;
142 4994 : case unaligned_store:
143 4994 : ks = "unaligned_store";
144 4994 : break;
145 9251 : case vector_store:
146 9251 : ks = "vector_store";
147 9251 : break;
148 0 : case vector_scatter_store:
149 0 : ks = "vector_scatter_store";
150 0 : break;
151 3697 : case vec_to_scalar:
152 3697 : ks = "vec_to_scalar";
153 3697 : break;
154 9795 : case scalar_to_vec:
155 9795 : ks = "scalar_to_vec";
156 9795 : break;
157 18 : case cond_branch_not_taken:
158 18 : ks = "cond_branch_not_taken";
159 18 : break;
160 560 : case cond_branch_taken:
161 560 : ks = "cond_branch_taken";
162 560 : break;
163 6609 : case vec_perm:
164 6609 : ks = "vec_perm";
165 6609 : break;
166 5558 : case vec_promote_demote:
167 5558 : ks = "vec_promote_demote";
168 5558 : break;
169 1251 : case vec_construct:
170 1251 : ks = "vec_construct";
171 1251 : break;
172 1125 : case vec_deconstruct:
173 1125 : ks = "vec_deconstruct";
174 1125 : break;
175 : }
176 232638 : fprintf (f, "%s ", ks);
177 232638 : if (kind == unaligned_load || kind == unaligned_store)
178 13301 : fprintf (f, "(misalign %d) ", misalign);
179 232638 : fprintf (f, "costs %u ", cost);
180 232638 : const char *ws = "unknown";
181 232638 : switch (where)
182 : {
183 24882 : case vect_prologue:
184 24882 : ws = "prologue";
185 24882 : break;
186 198766 : case vect_body:
187 198766 : ws = "body";
188 198766 : break;
189 8990 : case vect_epilogue:
190 8990 : ws = "epilogue";
191 8990 : break;
192 : }
193 232638 : fprintf (f, "in %s\n", ws);
194 232638 : }
195 :
196 : /* For mapping simduid to vectorization factor. */
197 :
198 : class simduid_to_vf : public free_ptr_hash<simduid_to_vf>
199 : {
200 : public:
201 : unsigned int simduid;
202 : poly_uint64 vf;
203 :
204 : /* hash_table support. */
205 : static inline hashval_t hash (const simduid_to_vf *);
206 : static inline int equal (const simduid_to_vf *, const simduid_to_vf *);
207 : };
208 :
209 : inline hashval_t
210 7499 : simduid_to_vf::hash (const simduid_to_vf *p)
211 : {
212 7499 : return p->simduid;
213 : }
214 :
215 : inline int
216 13971 : simduid_to_vf::equal (const simduid_to_vf *p1, const simduid_to_vf *p2)
217 : {
218 13971 : return p1->simduid == p2->simduid;
219 : }
220 :
221 : /* This hash maps the OMP simd array to the corresponding simduid used
222 : to index into it. Like thus,
223 :
224 : _7 = GOMP_SIMD_LANE (simduid.0)
225 : ...
226 : ...
227 : D.1737[_7] = stuff;
228 :
229 :
230 : This hash maps from the OMP simd array (D.1737[]) to DECL_UID of
231 : simduid.0. */
232 :
233 : struct simd_array_to_simduid : free_ptr_hash<simd_array_to_simduid>
234 : {
235 : tree decl;
236 : unsigned int simduid;
237 :
238 : /* hash_table support. */
239 : static inline hashval_t hash (const simd_array_to_simduid *);
240 : static inline int equal (const simd_array_to_simduid *,
241 : const simd_array_to_simduid *);
242 : };
243 :
244 : inline hashval_t
245 24455 : simd_array_to_simduid::hash (const simd_array_to_simduid *p)
246 : {
247 24455 : return DECL_UID (p->decl);
248 : }
249 :
250 : inline int
251 17126 : simd_array_to_simduid::equal (const simd_array_to_simduid *p1,
252 : const simd_array_to_simduid *p2)
253 : {
254 17126 : return p1->decl == p2->decl;
255 : }
256 :
257 : /* Fold IFN_GOMP_SIMD_LANE, IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LAST_LANE,
258 : into their corresponding constants and remove
259 : IFN_GOMP_SIMD_ORDERED_{START,END}. */
260 :
261 : static void
262 7803 : adjust_simduid_builtins (hash_table<simduid_to_vf> *htab, function *fun)
263 : {
264 7803 : basic_block bb;
265 :
266 118287 : FOR_EACH_BB_FN (bb, fun)
267 : {
268 110484 : gimple_stmt_iterator i;
269 :
270 744337 : for (i = gsi_start_bb (bb); !gsi_end_p (i); )
271 : {
272 523369 : poly_uint64 vf = 1;
273 523369 : enum internal_fn ifn;
274 523369 : gimple *stmt = gsi_stmt (i);
275 523369 : tree t;
276 523369 : if (!is_gimple_call (stmt)
277 523369 : || !gimple_call_internal_p (stmt))
278 : {
279 515889 : gsi_next (&i);
280 516763 : continue;
281 : }
282 7480 : ifn = gimple_call_internal_fn (stmt);
283 7480 : switch (ifn)
284 : {
285 6606 : case IFN_GOMP_SIMD_LANE:
286 6606 : case IFN_GOMP_SIMD_VF:
287 6606 : case IFN_GOMP_SIMD_LAST_LANE:
288 6606 : break;
289 162 : case IFN_GOMP_SIMD_ORDERED_START:
290 162 : case IFN_GOMP_SIMD_ORDERED_END:
291 162 : if (integer_onep (gimple_call_arg (stmt, 0)))
292 : {
293 6 : enum built_in_function bcode
294 : = (ifn == IFN_GOMP_SIMD_ORDERED_START
295 12 : ? BUILT_IN_GOMP_ORDERED_START
296 : : BUILT_IN_GOMP_ORDERED_END);
297 12 : gimple *g
298 12 : = gimple_build_call (builtin_decl_explicit (bcode), 0);
299 12 : gimple_move_vops (g, stmt);
300 12 : gsi_replace (&i, g, true);
301 12 : continue;
302 12 : }
303 150 : gsi_remove (&i, true);
304 150 : unlink_stmt_vdef (stmt);
305 150 : continue;
306 712 : default:
307 712 : gsi_next (&i);
308 712 : continue;
309 862 : }
310 6606 : tree arg = gimple_call_arg (stmt, 0);
311 6606 : gcc_assert (arg != NULL_TREE);
312 6606 : gcc_assert (TREE_CODE (arg) == SSA_NAME);
313 6606 : simduid_to_vf *p = NULL, data;
314 6606 : data.simduid = DECL_UID (SSA_NAME_VAR (arg));
315 : /* Need to nullify loop safelen field since it's value is not
316 : valid after transformation. */
317 6606 : if (bb->loop_father && bb->loop_father->safelen > 0)
318 2160 : bb->loop_father->safelen = 0;
319 6606 : if (htab)
320 : {
321 4705 : p = htab->find (&data);
322 4705 : if (p)
323 4670 : vf = p->vf;
324 : }
325 6606 : switch (ifn)
326 : {
327 : case IFN_GOMP_SIMD_VF:
328 976 : t = build_int_cst (unsigned_type_node, vf);
329 976 : break;
330 3443 : case IFN_GOMP_SIMD_LANE:
331 3443 : t = build_int_cst (unsigned_type_node, 0);
332 3443 : break;
333 2187 : case IFN_GOMP_SIMD_LAST_LANE:
334 2187 : t = gimple_call_arg (stmt, 1);
335 2187 : break;
336 : default:
337 : gcc_unreachable ();
338 : }
339 6606 : tree lhs = gimple_call_lhs (stmt);
340 6606 : if (lhs)
341 6554 : replace_uses_by (lhs, t);
342 6606 : release_defs (stmt);
343 6606 : gsi_remove (&i, true);
344 : }
345 : }
346 7803 : }
347 :
348 : /* Helper structure for note_simd_array_uses. */
349 :
350 : struct note_simd_array_uses_struct
351 : {
352 : hash_table<simd_array_to_simduid> **htab;
353 : unsigned int simduid;
354 : };
355 :
356 : /* Callback for note_simd_array_uses, called through walk_gimple_op. */
357 :
358 : static tree
359 64444 : note_simd_array_uses_cb (tree *tp, int *walk_subtrees, void *data)
360 : {
361 64444 : struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
362 64444 : struct note_simd_array_uses_struct *ns
363 : = (struct note_simd_array_uses_struct *) wi->info;
364 :
365 64444 : if (TYPE_P (*tp))
366 0 : *walk_subtrees = 0;
367 64444 : else if (VAR_P (*tp)
368 12207 : && lookup_attribute ("omp simd array", DECL_ATTRIBUTES (*tp))
369 76651 : && DECL_CONTEXT (*tp) == current_function_decl)
370 : {
371 12207 : simd_array_to_simduid data;
372 12207 : if (!*ns->htab)
373 2209 : *ns->htab = new hash_table<simd_array_to_simduid> (15);
374 12207 : data.decl = *tp;
375 12207 : data.simduid = ns->simduid;
376 12207 : simd_array_to_simduid **slot = (*ns->htab)->find_slot (&data, INSERT);
377 12207 : if (*slot == NULL)
378 : {
379 5489 : simd_array_to_simduid *p = XNEW (simd_array_to_simduid);
380 5489 : *p = data;
381 5489 : *slot = p;
382 : }
383 6718 : else if ((*slot)->simduid != ns->simduid)
384 0 : (*slot)->simduid = -1U;
385 12207 : *walk_subtrees = 0;
386 : }
387 64444 : return NULL_TREE;
388 : }
389 :
390 : /* Find "omp simd array" temporaries and map them to corresponding
391 : simduid. */
392 :
393 : static void
394 7803 : note_simd_array_uses (hash_table<simd_array_to_simduid> **htab, function *fun)
395 : {
396 7803 : basic_block bb;
397 7803 : gimple_stmt_iterator gsi;
398 7803 : struct walk_stmt_info wi;
399 7803 : struct note_simd_array_uses_struct ns;
400 :
401 7803 : memset (&wi, 0, sizeof (wi));
402 7803 : wi.info = &ns;
403 7803 : ns.htab = htab;
404 :
405 102255 : FOR_EACH_BB_FN (bb, fun)
406 587168 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
407 : {
408 398264 : gimple *stmt = gsi_stmt (gsi);
409 398264 : if (!is_gimple_call (stmt) || !gimple_call_internal_p (stmt))
410 391725 : continue;
411 7438 : switch (gimple_call_internal_fn (stmt))
412 : {
413 6570 : case IFN_GOMP_SIMD_LANE:
414 6570 : case IFN_GOMP_SIMD_VF:
415 6570 : case IFN_GOMP_SIMD_LAST_LANE:
416 6570 : break;
417 868 : default:
418 868 : continue;
419 : }
420 6570 : tree lhs = gimple_call_lhs (stmt);
421 6570 : if (lhs == NULL_TREE)
422 31 : continue;
423 6539 : imm_use_iterator use_iter;
424 6539 : gimple *use_stmt;
425 6539 : ns.simduid = DECL_UID (SSA_NAME_VAR (gimple_call_arg (stmt, 0)));
426 24431 : FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, lhs)
427 17892 : if (!is_gimple_debug (use_stmt))
428 24339 : walk_gimple_op (use_stmt, note_simd_array_uses_cb, &wi);
429 : }
430 7803 : }
431 :
432 : /* Shrink arrays with "omp simd array" attribute to the corresponding
433 : vectorization factor. */
434 :
435 : static void
436 2209 : shrink_simd_arrays
437 : (hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab,
438 : hash_table<simduid_to_vf> *simduid_to_vf_htab)
439 : {
440 5489 : for (hash_table<simd_array_to_simduid>::iterator iter
441 2209 : = simd_array_to_simduid_htab->begin ();
442 7698 : iter != simd_array_to_simduid_htab->end (); ++iter)
443 5489 : if ((*iter)->simduid != -1U)
444 : {
445 5489 : tree decl = (*iter)->decl;
446 5489 : poly_uint64 vf = 1;
447 5489 : if (simduid_to_vf_htab)
448 : {
449 4562 : simduid_to_vf *p = NULL, data;
450 4562 : data.simduid = (*iter)->simduid;
451 4562 : p = simduid_to_vf_htab->find (&data);
452 4562 : if (p)
453 4531 : vf = p->vf;
454 : }
455 5489 : tree atype
456 5489 : = build_array_type_nelts (TREE_TYPE (TREE_TYPE (decl)), vf);
457 5489 : TREE_TYPE (decl) = atype;
458 5489 : relayout_decl (decl);
459 : }
460 :
461 2209 : delete simd_array_to_simduid_htab;
462 2209 : }
463 :
464 : /* Initialize the vec_info with kind KIND_IN and target cost data
465 : TARGET_COST_DATA_IN. */
466 :
467 2854346 : vec_info::vec_info (vec_info::vec_kind kind_in, vec_info_shared *shared_)
468 2854346 : : kind (kind_in),
469 2854346 : shared (shared_),
470 2854346 : stmt_vec_info_ro (false),
471 2854346 : bbs (NULL),
472 2854346 : nbbs (0),
473 2854346 : inv_pattern_def_seq (NULL)
474 : {
475 2854346 : stmt_vec_infos.create (50);
476 2854346 : }
477 :
478 2854346 : vec_info::~vec_info ()
479 : {
480 5226827 : for (slp_instance &instance : slp_instances)
481 1200801 : vect_free_slp_instance (instance);
482 :
483 2854346 : free_stmt_vec_infos ();
484 2854346 : }
485 :
486 2429586 : vec_info_shared::vec_info_shared ()
487 2429586 : : datarefs (vNULL),
488 2429586 : datarefs_copy (vNULL),
489 2429586 : ddrs (vNULL)
490 : {
491 2429586 : }
492 :
493 2429586 : vec_info_shared::~vec_info_shared ()
494 : {
495 2429586 : free_data_refs (datarefs);
496 2429586 : free_dependence_relations (ddrs);
497 2429586 : datarefs_copy.release ();
498 2429586 : }
499 :
500 : void
501 2186810 : vec_info_shared::save_datarefs ()
502 : {
503 2186810 : if (!flag_checking)
504 : return;
505 3275576 : datarefs_copy.reserve_exact (datarefs.length ());
506 15422359 : for (unsigned i = 0; i < datarefs.length (); ++i)
507 11048773 : datarefs_copy.quick_push (*datarefs[i]);
508 : }
509 :
510 : void
511 1188222 : vec_info_shared::check_datarefs ()
512 : {
513 1188222 : if (!flag_checking)
514 : return;
515 3514492 : gcc_assert (datarefs.length () == datarefs_copy.length ());
516 14051350 : for (unsigned i = 0; i < datarefs.length (); ++i)
517 12863132 : if (memcmp (&datarefs_copy[i], datarefs[i],
518 : offsetof (data_reference, alt_indices)) != 0)
519 0 : gcc_unreachable ();
520 : }
521 :
522 : /* Record that STMT belongs to the vectorizable region. Create and return
523 : an associated stmt_vec_info. */
524 :
525 : stmt_vec_info
526 63787251 : vec_info::add_stmt (gimple *stmt)
527 : {
528 63787251 : stmt_vec_info res = new_stmt_vec_info (stmt);
529 63787251 : set_vinfo_for_stmt (stmt, res);
530 63787251 : return res;
531 : }
532 :
533 : /* Record that STMT belongs to the vectorizable region. Create a new
534 : stmt_vec_info and mark VECINFO as being related and return the new
535 : stmt_vec_info. */
536 :
537 : stmt_vec_info
538 1114 : vec_info::add_pattern_stmt (gimple *stmt, stmt_vec_info stmt_info)
539 : {
540 1114 : stmt_vec_info res = new_stmt_vec_info (stmt);
541 1114 : res->pattern_stmt_p = true;
542 1114 : set_vinfo_for_stmt (stmt, res, false);
543 1114 : STMT_VINFO_RELATED_STMT (res) = stmt_info;
544 1114 : return res;
545 : }
546 :
547 : /* If STMT was previously associated with a stmt_vec_info and STMT now resides
548 : at a different address than before (e.g., because STMT is a phi node that has
549 : been resized), update the stored address to match the new one. It is not
550 : possible to use lookup_stmt () to perform this task, because that function
551 : returns NULL if the stored stmt pointer does not match the one being looked
552 : up. */
553 :
554 : stmt_vec_info
555 11242 : vec_info::resync_stmt_addr (gimple *stmt)
556 : {
557 11242 : unsigned int uid = gimple_uid (stmt);
558 11242 : if (uid > 0 && uid - 1 < stmt_vec_infos.length ())
559 : {
560 11242 : stmt_vec_info res = stmt_vec_infos[uid - 1];
561 11242 : if (res && res->stmt)
562 : {
563 11242 : res->stmt = stmt;
564 11242 : return res;
565 : }
566 : }
567 : return nullptr;
568 : }
569 :
570 : /* If STMT has an associated stmt_vec_info, return that vec_info, otherwise
571 : return null. It is safe to call this function on any statement, even if
572 : it might not be part of the vectorizable region. */
573 :
574 : stmt_vec_info
575 519972209 : vec_info::lookup_stmt (gimple *stmt)
576 : {
577 519972209 : unsigned int uid = gimple_uid (stmt);
578 519972209 : if (uid > 0 && uid - 1 < stmt_vec_infos.length ())
579 : {
580 321420128 : stmt_vec_info res = stmt_vec_infos[uid - 1];
581 321420128 : if (res && res->stmt == stmt)
582 321063757 : return res;
583 : }
584 : return NULL;
585 : }
586 :
587 : /* If NAME is an SSA_NAME and its definition has an associated stmt_vec_info,
588 : return that stmt_vec_info, otherwise return null. It is safe to call
589 : this on arbitrary operands. */
590 :
591 : stmt_vec_info
592 60885817 : vec_info::lookup_def (tree name)
593 : {
594 60885817 : if (TREE_CODE (name) == SSA_NAME
595 60885817 : && !SSA_NAME_IS_DEFAULT_DEF (name))
596 55021940 : return lookup_stmt (SSA_NAME_DEF_STMT (name));
597 : return NULL;
598 : }
599 :
600 : /* See whether there is a single non-debug statement that uses LHS and
601 : whether that statement has an associated stmt_vec_info. Return the
602 : stmt_vec_info if so, otherwise return null. */
603 :
604 : stmt_vec_info
605 2004 : vec_info::lookup_single_use (tree lhs)
606 : {
607 2004 : use_operand_p dummy;
608 2004 : gimple *use_stmt;
609 2004 : if (single_imm_use (lhs, &dummy, &use_stmt))
610 1859 : return lookup_stmt (use_stmt);
611 : return NULL;
612 : }
613 :
614 : /* Return vectorization information about DR. */
615 :
616 : dr_vec_info *
617 53006790 : vec_info::lookup_dr (data_reference *dr)
618 : {
619 53006790 : stmt_vec_info stmt_info = lookup_stmt (DR_STMT (dr));
620 : /* DR_STMT should never refer to a stmt in a pattern replacement. */
621 53006790 : gcc_checking_assert (!is_pattern_stmt_p (stmt_info));
622 53006790 : return STMT_VINFO_DR_INFO (stmt_info->dr_aux.stmt);
623 : }
624 :
625 : /* Record that NEW_STMT_INFO now implements the same data reference
626 : as OLD_STMT_INFO. */
627 :
628 : void
629 6295 : vec_info::move_dr (stmt_vec_info new_stmt_info, stmt_vec_info old_stmt_info)
630 : {
631 6295 : gcc_assert (!is_pattern_stmt_p (old_stmt_info));
632 6295 : STMT_VINFO_DR_INFO (old_stmt_info)->stmt = new_stmt_info;
633 6295 : new_stmt_info->dr_aux = old_stmt_info->dr_aux;
634 6295 : STMT_VINFO_DR_WRT_VEC_LOOP (new_stmt_info)
635 6295 : = STMT_VINFO_DR_WRT_VEC_LOOP (old_stmt_info);
636 6295 : STMT_VINFO_GATHER_SCATTER_P (new_stmt_info)
637 6295 : = STMT_VINFO_GATHER_SCATTER_P (old_stmt_info);
638 6295 : STMT_VINFO_STRIDED_P (new_stmt_info)
639 6295 : = STMT_VINFO_STRIDED_P (old_stmt_info);
640 6295 : STMT_VINFO_SIMD_LANE_ACCESS_P (new_stmt_info)
641 6295 : = STMT_VINFO_SIMD_LANE_ACCESS_P (old_stmt_info);
642 6295 : }
643 :
644 : /* Permanently remove the statement described by STMT_INFO from the
645 : function. */
646 :
647 : void
648 1511027 : vec_info::remove_stmt (stmt_vec_info stmt_info)
649 : {
650 1511027 : gcc_assert (!stmt_info->pattern_stmt_p);
651 1511027 : set_vinfo_for_stmt (stmt_info->stmt, NULL);
652 1511027 : unlink_stmt_vdef (stmt_info->stmt);
653 1511027 : gimple_stmt_iterator si = gsi_for_stmt (stmt_info->stmt);
654 1511027 : gsi_remove (&si, true);
655 1511027 : release_defs (stmt_info->stmt);
656 1511027 : free_stmt_vec_info (stmt_info);
657 1511027 : }
658 :
659 : /* Replace the statement at GSI by NEW_STMT, both the vectorization
660 : information and the function itself. STMT_INFO describes the statement
661 : at GSI. */
662 :
663 : void
664 5400 : vec_info::replace_stmt (gimple_stmt_iterator *gsi, stmt_vec_info stmt_info,
665 : gimple *new_stmt)
666 : {
667 5400 : gimple *old_stmt = stmt_info->stmt;
668 5400 : gcc_assert (!stmt_info->pattern_stmt_p && old_stmt == gsi_stmt (*gsi));
669 5400 : gimple_set_uid (new_stmt, gimple_uid (old_stmt));
670 5400 : stmt_info->stmt = new_stmt;
671 5400 : gsi_replace (gsi, new_stmt, true);
672 5400 : }
673 :
674 : /* Insert stmts in SEQ on the VEC_INFO region entry. If CONTEXT is
675 : not NULL it specifies whether to use the sub-region entry
676 : determined by it, currently used for loop vectorization to insert
677 : on the inner loop entry vs. the outer loop entry. */
678 :
679 : void
680 104280 : vec_info::insert_seq_on_entry (stmt_vec_info context, gimple_seq seq)
681 : {
682 104280 : if (loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (this))
683 : {
684 19334 : class loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
685 19334 : basic_block new_bb;
686 19334 : edge pe;
687 :
688 19334 : if (context && nested_in_vect_loop_p (loop, context))
689 : loop = loop->inner;
690 :
691 19334 : pe = loop_preheader_edge (loop);
692 19334 : new_bb = gsi_insert_seq_on_edge_immediate (pe, seq);
693 19334 : gcc_assert (!new_bb);
694 : }
695 : else
696 : {
697 84946 : gimple_stmt_iterator gsi_region_begin = gsi_after_labels (bbs[0]);
698 : /* If the regions starts with a returns-twice call insert afte that. */
699 84946 : if (gcall *call = safe_dyn_cast <gcall *> (gsi_stmt (gsi_region_begin)))
700 4031 : if (gimple_call_flags (call) & ECF_RETURNS_TWICE)
701 2 : gsi_next (&gsi_region_begin);
702 84946 : gsi_insert_seq_before (&gsi_region_begin, seq, GSI_SAME_STMT);
703 : }
704 104280 : }
705 :
706 : /* Like insert_seq_on_entry but just inserts the single stmt NEW_STMT. */
707 :
708 : void
709 3280 : vec_info::insert_on_entry (stmt_vec_info context, gimple *new_stmt)
710 : {
711 3280 : gimple_seq seq = NULL;
712 3280 : gimple_stmt_iterator gsi = gsi_start (seq);
713 3280 : gsi_insert_before_without_update (&gsi, new_stmt, GSI_SAME_STMT);
714 3280 : insert_seq_on_entry (context, seq);
715 3280 : }
716 :
717 : /* Create and initialize a new stmt_vec_info struct for STMT. */
718 :
719 : stmt_vec_info
720 63788365 : vec_info::new_stmt_vec_info (gimple *stmt)
721 : {
722 63788365 : stmt_vec_info res = XCNEW (class _stmt_vec_info);
723 63788365 : res->stmt = stmt;
724 :
725 63788365 : STMT_VINFO_RELEVANT (res) = vect_unused_in_scope;
726 63788365 : STMT_VINFO_VECTORIZABLE (res) = true;
727 63788365 : STMT_VINFO_REDUC_TYPE (res) = TREE_CODE_REDUCTION;
728 63788365 : STMT_VINFO_REDUC_CODE (res) = ERROR_MARK;
729 63788365 : STMT_VINFO_REDUC_IDX (res) = -1;
730 63788365 : STMT_VINFO_REDUC_DEF (res) = NULL;
731 63788365 : STMT_VINFO_SLP_VECT_ONLY (res) = false;
732 :
733 63788365 : if (is_a <loop_vec_info> (this)
734 8179651 : && gimple_code (stmt) == GIMPLE_PHI
735 65213717 : && is_loop_header_bb_p (gimple_bb (stmt)))
736 1416623 : STMT_VINFO_DEF_TYPE (res) = vect_unknown_def_type;
737 : else
738 62371742 : STMT_VINFO_DEF_TYPE (res) = vect_internal_def;
739 :
740 63788365 : STMT_SLP_TYPE (res) = not_vect;
741 :
742 : /* This is really "uninitialized" until vect_compute_data_ref_alignment. */
743 63788365 : res->dr_aux.misalignment = DR_MISALIGNMENT_UNINITIALIZED;
744 :
745 63788365 : return res;
746 : }
747 :
748 : /* Associate STMT with INFO. */
749 :
750 : void
751 65299392 : vec_info::set_vinfo_for_stmt (gimple *stmt, stmt_vec_info info, bool check_ro)
752 : {
753 65299392 : unsigned int uid = gimple_uid (stmt);
754 65299392 : if (uid == 0)
755 : {
756 63788365 : gcc_assert (!check_ro || !stmt_vec_info_ro);
757 63788365 : gcc_checking_assert (info);
758 63788365 : uid = stmt_vec_infos.length () + 1;
759 63788365 : gimple_set_uid (stmt, uid);
760 63788365 : stmt_vec_infos.safe_push (info);
761 : }
762 : else
763 : {
764 1511027 : gcc_checking_assert (info == NULL);
765 1511027 : stmt_vec_infos[uid - 1] = info;
766 : }
767 65299392 : }
768 :
769 : /* Free the contents of stmt_vec_infos. */
770 :
771 : void
772 2854346 : vec_info::free_stmt_vec_infos (void)
773 : {
774 72351403 : for (stmt_vec_info &info : stmt_vec_infos)
775 63788365 : if (info != NULL)
776 62277338 : free_stmt_vec_info (info);
777 2854346 : stmt_vec_infos.release ();
778 2854346 : }
779 :
780 : /* Free STMT_INFO. */
781 :
782 : void
783 63788365 : vec_info::free_stmt_vec_info (stmt_vec_info stmt_info)
784 : {
785 63788365 : if (stmt_info->pattern_stmt_p)
786 : {
787 2444503 : gimple_set_bb (stmt_info->stmt, NULL);
788 2444503 : tree lhs = gimple_get_lhs (stmt_info->stmt);
789 2444503 : if (lhs && TREE_CODE (lhs) == SSA_NAME)
790 2049029 : release_ssa_name (lhs);
791 : }
792 :
793 63788365 : free (stmt_info);
794 63788365 : }
795 :
796 : /* Returns true if S1 dominates S2. */
797 :
798 : bool
799 1763861 : vect_stmt_dominates_stmt_p (gimple *s1, gimple *s2)
800 : {
801 1763861 : basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
802 :
803 : /* If bb1 is NULL, it should be a GIMPLE_NOP def stmt of an (D)
804 : SSA_NAME. Assume it lives at the beginning of function and
805 : thus dominates everything. */
806 1763861 : if (!bb1 || s1 == s2)
807 : return true;
808 :
809 : /* If bb2 is NULL, it doesn't dominate any stmt with a bb. */
810 1146562 : if (!bb2)
811 : return false;
812 :
813 1146562 : if (bb1 != bb2)
814 357829 : return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
815 :
816 : /* PHIs in the same basic block are assumed to be
817 : executed all in parallel, if only one stmt is a PHI,
818 : it dominates the other stmt in the same basic block. */
819 788733 : if (gimple_code (s1) == GIMPLE_PHI)
820 : return true;
821 :
822 665831 : if (gimple_code (s2) == GIMPLE_PHI)
823 : return false;
824 :
825 : /* Inserted vectorized stmts all have UID 0 while the original stmts
826 : in the IL have UID increasing within a BB. Walk from both sides
827 : until we find the other stmt or a stmt with UID != 0. */
828 642989 : gimple_stmt_iterator gsi1 = gsi_for_stmt (s1);
829 1220700 : while (gimple_uid (gsi_stmt (gsi1)) == 0)
830 : {
831 698536 : gsi_next (&gsi1);
832 698536 : if (gsi_end_p (gsi1))
833 : return false;
834 696892 : if (gsi_stmt (gsi1) == s2)
835 : return true;
836 : }
837 522164 : if (gimple_uid (gsi_stmt (gsi1)) == -1u)
838 : return false;
839 :
840 522164 : gimple_stmt_iterator gsi2 = gsi_for_stmt (s2);
841 1165709 : while (gimple_uid (gsi_stmt (gsi2)) == 0)
842 : {
843 657039 : gsi_prev (&gsi2);
844 657039 : if (gsi_end_p (gsi2))
845 : return false;
846 643553 : if (gsi_stmt (gsi2) == s1)
847 : return true;
848 : }
849 508670 : if (gimple_uid (gsi_stmt (gsi2)) == -1u)
850 : return false;
851 :
852 508670 : if (gimple_uid (gsi_stmt (gsi1)) <= gimple_uid (gsi_stmt (gsi2)))
853 399672 : return true;
854 : return false;
855 : }
856 :
857 : /* A helper function to free scev and LOOP niter information, as well as
858 : clear loop constraint LOOP_C_FINITE. */
859 :
860 : void
861 52778 : vect_free_loop_info_assumptions (class loop *loop)
862 : {
863 52778 : scev_reset_htab ();
864 : /* We need to explicitly reset upper bound information since they are
865 : used even after free_numbers_of_iterations_estimates. */
866 52778 : loop->any_upper_bound = false;
867 52778 : loop->any_likely_upper_bound = false;
868 52778 : free_numbers_of_iterations_estimates (loop);
869 52778 : loop_constraint_clear (loop, LOOP_C_FINITE);
870 52778 : }
871 :
872 : /* If LOOP has been versioned during ifcvt, return the internal call
873 : guarding it. */
874 :
875 : gimple *
876 531005 : vect_loop_vectorized_call (class loop *loop, gcond **cond)
877 : {
878 531005 : basic_block bb = loop_preheader_edge (loop)->src;
879 981400 : gimple *g;
880 1431795 : do
881 : {
882 981400 : g = *gsi_last_bb (bb);
883 626947 : if ((g && gimple_code (g) == GIMPLE_COND)
884 2105477 : || !single_succ_p (bb))
885 : break;
886 593072 : if (!single_pred_p (bb))
887 : break;
888 450395 : bb = single_pred (bb);
889 : }
890 : while (1);
891 531005 : if (g && gimple_code (g) == GIMPLE_COND)
892 : {
893 381307 : if (cond)
894 0 : *cond = as_a <gcond *> (g);
895 381307 : gimple_stmt_iterator gsi = gsi_for_stmt (g);
896 381307 : gsi_prev (&gsi);
897 381307 : if (!gsi_end_p (gsi))
898 : {
899 348442 : g = gsi_stmt (gsi);
900 348442 : if (gimple_call_internal_p (g, IFN_LOOP_VECTORIZED)
901 348442 : && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->num
902 26937 : || tree_to_shwi (gimple_call_arg (g, 1)) == loop->num))
903 54187 : return g;
904 : }
905 : }
906 : return NULL;
907 : }
908 :
909 : /* If LOOP has been versioned during loop distribution, return the gurading
910 : internal call. */
911 :
912 : static gimple *
913 497296 : vect_loop_dist_alias_call (class loop *loop, function *fun)
914 : {
915 497296 : basic_block bb;
916 497296 : basic_block entry;
917 497296 : class loop *outer, *orig;
918 :
919 497296 : if (loop->orig_loop_num == 0)
920 : return NULL;
921 :
922 167 : orig = get_loop (fun, loop->orig_loop_num);
923 167 : if (orig == NULL)
924 : {
925 : /* The original loop is somehow destroyed. Clear the information. */
926 0 : loop->orig_loop_num = 0;
927 0 : return NULL;
928 : }
929 :
930 167 : if (loop != orig)
931 95 : bb = nearest_common_dominator (CDI_DOMINATORS, loop->header, orig->header);
932 : else
933 72 : bb = loop_preheader_edge (loop)->src;
934 :
935 167 : outer = bb->loop_father;
936 167 : entry = ENTRY_BLOCK_PTR_FOR_FN (fun);
937 :
938 : /* Look upward in dominance tree. */
939 747 : for (; bb != entry && flow_bb_inside_loop_p (outer, bb);
940 580 : bb = get_immediate_dominator (CDI_DOMINATORS, bb))
941 : {
942 696 : gimple_stmt_iterator gsi = gsi_last_bb (bb);
943 696 : if (!safe_is_a <gcond *> (*gsi))
944 184 : continue;
945 :
946 512 : gsi_prev (&gsi);
947 512 : if (gsi_end_p (gsi))
948 7 : continue;
949 :
950 505 : gimple *g = gsi_stmt (gsi);
951 : /* The guarding internal function call must have the same distribution
952 : alias id. */
953 505 : if (gimple_call_internal_p (g, IFN_LOOP_DIST_ALIAS)
954 505 : && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->orig_loop_num))
955 497296 : return g;
956 : }
957 : return NULL;
958 : }
959 :
960 : /* Set the uids of all the statements in basic blocks inside loop
961 : represented by LOOP_VINFO. LOOP_VECTORIZED_CALL is the internal
962 : call guarding the loop which has been if converted. */
963 : static void
964 7009 : set_uid_loop_bbs (loop_vec_info loop_vinfo, gimple *loop_vectorized_call,
965 : function *fun)
966 : {
967 7009 : tree arg = gimple_call_arg (loop_vectorized_call, 1);
968 7009 : basic_block *bbs;
969 7009 : unsigned int i;
970 7009 : class loop *scalar_loop = get_loop (fun, tree_to_shwi (arg));
971 :
972 7009 : LOOP_VINFO_SCALAR_LOOP (loop_vinfo) = scalar_loop;
973 7009 : LOOP_VINFO_SCALAR_MAIN_EXIT (loop_vinfo)
974 7009 : = vec_init_loop_exit_info (scalar_loop);
975 7009 : gcc_checking_assert (vect_loop_vectorized_call (scalar_loop)
976 : == loop_vectorized_call);
977 : /* If we are going to vectorize outer loop, prevent vectorization
978 : of the inner loop in the scalar loop - either the scalar loop is
979 : thrown away, so it is a wasted work, or is used only for
980 : a few iterations. */
981 7009 : if (scalar_loop->inner)
982 : {
983 100 : gimple *g = vect_loop_vectorized_call (scalar_loop->inner);
984 100 : if (g)
985 : {
986 100 : arg = gimple_call_arg (g, 0);
987 100 : get_loop (fun, tree_to_shwi (arg))->dont_vectorize = true;
988 100 : fold_loop_internal_call (g, boolean_false_node);
989 : }
990 : }
991 7009 : bbs = get_loop_body (scalar_loop);
992 45385 : for (i = 0; i < scalar_loop->num_nodes; i++)
993 : {
994 31367 : basic_block bb = bbs[i];
995 31367 : gimple_stmt_iterator gsi;
996 61382 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
997 : {
998 30015 : gimple *phi = gsi_stmt (gsi);
999 30015 : gimple_set_uid (phi, 0);
1000 : }
1001 147990 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1002 : {
1003 85256 : gimple *stmt = gsi_stmt (gsi);
1004 85256 : gimple_set_uid (stmt, 0);
1005 : }
1006 : }
1007 7009 : free (bbs);
1008 7009 : }
1009 :
1010 : /* Generate vectorized code for LOOP and its epilogues. */
1011 :
1012 : static unsigned
1013 64392 : vect_transform_loops (hash_table<simduid_to_vf> *&simduid_to_vf_htab,
1014 : loop_p loop, gimple *loop_vectorized_call,
1015 : function *fun)
1016 : {
1017 64392 : loop_vec_info loop_vinfo = loop_vec_info_for_loop (loop);
1018 :
1019 64392 : if (loop_vectorized_call)
1020 7009 : set_uid_loop_bbs (loop_vinfo, loop_vectorized_call, fun);
1021 :
1022 64392 : unsigned HOST_WIDE_INT bytes;
1023 64392 : if (dump_enabled_p ())
1024 : {
1025 22992 : if (GET_MODE_SIZE (loop_vinfo->vector_mode).is_constant (&bytes))
1026 11496 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location,
1027 : "%sloop vectorized using %s%wu byte vectors and"
1028 : " unroll factor %u\n",
1029 11496 : LOOP_VINFO_EPILOGUE_P (loop_vinfo)
1030 : ? "epilogue " : "",
1031 11496 : LOOP_VINFO_USING_PARTIAL_VECTORS_P (loop_vinfo)
1032 : ? "masked " : "", bytes,
1033 : (unsigned int) LOOP_VINFO_VECT_FACTOR
1034 11496 : (loop_vinfo).to_constant ());
1035 : else
1036 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location,
1037 : "%sloop vectorized using variable length vectors\n",
1038 : LOOP_VINFO_EPILOGUE_P (loop_vinfo)
1039 : ? "epilogue " : "");
1040 : }
1041 :
1042 64392 : loop_p new_loop = vect_transform_loop (loop_vinfo,
1043 : loop_vectorized_call);
1044 : /* Now that the loop has been vectorized, allow it to be unrolled
1045 : etc. */
1046 64392 : loop->force_vectorize = false;
1047 :
1048 64392 : if (loop->simduid)
1049 : {
1050 1899 : simduid_to_vf *simduid_to_vf_data = XNEW (simduid_to_vf);
1051 1899 : if (!simduid_to_vf_htab)
1052 1536 : simduid_to_vf_htab = new hash_table<simduid_to_vf> (15);
1053 1899 : simduid_to_vf_data->simduid = DECL_UID (loop->simduid);
1054 1899 : simduid_to_vf_data->vf = loop_vinfo->vectorization_factor;
1055 1899 : *simduid_to_vf_htab->find_slot (simduid_to_vf_data, INSERT)
1056 1899 : = simduid_to_vf_data;
1057 : }
1058 :
1059 : /* We should not have to update virtual SSA form here but some
1060 : transforms involve creating new virtual definitions which makes
1061 : updating difficult.
1062 : We delay the actual update to the end of the pass but avoid
1063 : confusing ourselves by forcing need_ssa_update_p () to false. */
1064 64392 : unsigned todo = 0;
1065 64392 : if (need_ssa_update_p (cfun))
1066 : {
1067 126 : gcc_assert (loop_vinfo->any_known_not_updated_vssa);
1068 126 : fun->gimple_df->ssa_renaming_needed = false;
1069 126 : todo |= TODO_update_ssa_only_virtuals;
1070 : }
1071 64392 : gcc_assert (!need_ssa_update_p (cfun));
1072 :
1073 : /* Epilogue of vectorized loop must be vectorized too. */
1074 64392 : if (new_loop)
1075 6946 : todo |= vect_transform_loops (simduid_to_vf_htab, new_loop, NULL, fun);
1076 :
1077 64392 : return todo;
1078 : }
1079 :
1080 : /* Try to vectorize LOOP. */
1081 :
1082 : static unsigned
1083 481919 : try_vectorize_loop_1 (hash_table<simduid_to_vf> *&simduid_to_vf_htab,
1084 : unsigned *num_vectorized_loops, loop_p loop,
1085 : gimple *loop_vectorized_call,
1086 : gimple *loop_dist_alias_call,
1087 : function *fun)
1088 : {
1089 481919 : unsigned ret = 0;
1090 481919 : vec_info_shared shared;
1091 481919 : auto_purge_vect_location sentinel;
1092 481919 : vect_location = find_loop_location (loop);
1093 :
1094 481919 : if (LOCATION_LOCUS (vect_location.get_location_t ()) != UNKNOWN_LOCATION
1095 481919 : && dump_enabled_p ())
1096 15636 : dump_printf (MSG_NOTE | MSG_PRIORITY_INTERNALS,
1097 : "\nAnalyzing loop at %s:%d\n",
1098 15636 : LOCATION_FILE (vect_location.get_location_t ()),
1099 31272 : LOCATION_LINE (vect_location.get_location_t ()));
1100 :
1101 : /* Try to analyze the loop, retaining an opt_problem if dump_enabled_p. */
1102 481919 : opt_loop_vec_info loop_vinfo = vect_analyze_loop (loop, loop_vectorized_call,
1103 : &shared);
1104 481919 : loop->aux = loop_vinfo;
1105 :
1106 481919 : if (!loop_vinfo)
1107 424469 : if (dump_enabled_p ())
1108 6017 : if (opt_problem *problem = loop_vinfo.get_problem ())
1109 : {
1110 6017 : dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1111 : "couldn't vectorize loop\n");
1112 6017 : problem->emit_and_clear ();
1113 : }
1114 :
1115 481919 : if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo))
1116 : {
1117 : /* Free existing information if loop is analyzed with some
1118 : assumptions. */
1119 424469 : if (loop_constraint_set_p (loop, LOOP_C_FINITE))
1120 7404 : vect_free_loop_info_assumptions (loop);
1121 :
1122 : /* If we applied if-conversion then try to vectorize the
1123 : BB of innermost loops.
1124 : ??? Ideally BB vectorization would learn to vectorize
1125 : control flow by applying if-conversion on-the-fly, the
1126 : following retains the if-converted loop body even when
1127 : only non-if-converted parts took part in BB vectorization. */
1128 424469 : if (flag_tree_slp_vectorize != 0
1129 423383 : && loop_vectorized_call
1130 18538 : && ! loop->inner)
1131 : {
1132 17716 : basic_block bb = loop->header;
1133 17716 : bool require_loop_vectorize = false;
1134 35432 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
1135 700265 : !gsi_end_p (gsi); gsi_next (&gsi))
1136 : {
1137 683322 : gimple *stmt = gsi_stmt (gsi);
1138 683322 : gcall *call = dyn_cast <gcall *> (stmt);
1139 1218 : if (call && gimple_call_internal_p (call))
1140 : {
1141 1112 : internal_fn ifn = gimple_call_internal_fn (call);
1142 1112 : if (ifn == IFN_MASK_LOAD
1143 1112 : || ifn == IFN_MASK_STORE
1144 746 : || ifn == IFN_MASK_CALL
1145 : /* Don't keep the if-converted parts when the ifn with
1146 : specific type is not supported by the backend. */
1147 1839 : || (direct_internal_fn_p (ifn)
1148 388 : && !direct_internal_fn_supported_p
1149 388 : (call, OPTIMIZE_FOR_SPEED)))
1150 : {
1151 : require_loop_vectorize = true;
1152 : break;
1153 : }
1154 : }
1155 682549 : gimple_set_uid (stmt, -1);
1156 682549 : gimple_set_visited (stmt, false);
1157 : }
1158 17716 : if (!require_loop_vectorize)
1159 : {
1160 16943 : tree arg = gimple_call_arg (loop_vectorized_call, 1);
1161 16943 : class loop *scalar_loop = get_loop (fun, tree_to_shwi (arg));
1162 16943 : if (vect_slp_if_converted_bb (bb, scalar_loop))
1163 : {
1164 64 : fold_loop_internal_call (loop_vectorized_call,
1165 : boolean_true_node);
1166 64 : loop_vectorized_call = NULL;
1167 64 : ret |= TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
1168 : }
1169 : }
1170 : }
1171 : /* If outer loop vectorization fails for LOOP_VECTORIZED guarded
1172 : loop, don't vectorize its inner loop; we'll attempt to
1173 : vectorize LOOP_VECTORIZED guarded inner loop of the scalar
1174 : loop version. */
1175 19624 : if (loop_vectorized_call && loop->inner)
1176 824 : loop->inner->dont_vectorize = true;
1177 : return ret;
1178 : }
1179 :
1180 57450 : if (!dbg_cnt (vect_loop))
1181 : {
1182 : /* Free existing information if loop is analyzed with some
1183 : assumptions. */
1184 4 : if (loop_constraint_set_p (loop, LOOP_C_FINITE))
1185 0 : vect_free_loop_info_assumptions (loop);
1186 : return ret;
1187 : }
1188 :
1189 57446 : (*num_vectorized_loops)++;
1190 : /* Transform LOOP and its epilogues. */
1191 57446 : ret |= vect_transform_loops (simduid_to_vf_htab, loop,
1192 : loop_vectorized_call, fun);
1193 :
1194 57446 : if (loop_vectorized_call)
1195 : {
1196 7009 : fold_loop_internal_call (loop_vectorized_call, boolean_true_node);
1197 7009 : ret |= TODO_cleanup_cfg;
1198 : }
1199 57446 : if (loop_dist_alias_call)
1200 : {
1201 8 : tree value = gimple_call_arg (loop_dist_alias_call, 1);
1202 8 : fold_loop_internal_call (loop_dist_alias_call, value);
1203 8 : ret |= TODO_cleanup_cfg;
1204 : }
1205 :
1206 : return ret;
1207 481919 : }
1208 :
1209 : /* Try to vectorize LOOP. */
1210 :
1211 : static unsigned
1212 514881 : try_vectorize_loop (hash_table<simduid_to_vf> *&simduid_to_vf_htab,
1213 : unsigned *num_vectorized_loops, loop_p loop,
1214 : function *fun)
1215 : {
1216 514881 : if (!((flag_tree_loop_vectorize
1217 510195 : && optimize_loop_nest_for_speed_p (loop))
1218 34817 : || loop->force_vectorize))
1219 : return 0;
1220 :
1221 481919 : return try_vectorize_loop_1 (simduid_to_vf_htab, num_vectorized_loops, loop,
1222 : vect_loop_vectorized_call (loop),
1223 481919 : vect_loop_dist_alias_call (loop, fun), fun);
1224 : }
1225 :
1226 :
1227 : /* Loop autovectorization. */
1228 :
1229 : namespace {
1230 :
1231 : const pass_data pass_data_vectorize =
1232 : {
1233 : GIMPLE_PASS, /* type */
1234 : "vect", /* name */
1235 : OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
1236 : TV_TREE_VECTORIZATION, /* tv_id */
1237 : ( PROP_cfg | PROP_ssa ), /* properties_required */
1238 : 0, /* properties_provided */
1239 : 0, /* properties_destroyed */
1240 : 0, /* todo_flags_start */
1241 : 0, /* todo_flags_finish */
1242 : };
1243 :
1244 : class pass_vectorize : public gimple_opt_pass
1245 : {
1246 : public:
1247 297180 : pass_vectorize (gcc::context *ctxt)
1248 594360 : : gimple_opt_pass (pass_data_vectorize, ctxt)
1249 : {}
1250 :
1251 : /* opt_pass methods: */
1252 248475 : bool gate (function *fun) final override
1253 : {
1254 248475 : return flag_tree_loop_vectorize || fun->has_force_vectorize_loops;
1255 : }
1256 :
1257 : unsigned int execute (function *) final override;
1258 :
1259 : }; // class pass_vectorize
1260 :
1261 : /* Function vectorize_loops.
1262 :
1263 : Entry point to loop vectorization phase. */
1264 :
1265 : unsigned
1266 214143 : pass_vectorize::execute (function *fun)
1267 : {
1268 214143 : unsigned int i;
1269 214143 : unsigned int num_vectorized_loops = 0;
1270 214143 : unsigned int vect_loops_num;
1271 214143 : hash_table<simduid_to_vf> *simduid_to_vf_htab = NULL;
1272 214143 : hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab = NULL;
1273 214143 : bool any_ifcvt_loops = false;
1274 214143 : unsigned ret = 0;
1275 :
1276 214143 : vect_loops_num = number_of_loops (fun);
1277 :
1278 : /* Bail out if there are no loops. */
1279 214143 : if (vect_loops_num <= 1)
1280 : return 0;
1281 :
1282 214143 : vect_slp_init ();
1283 :
1284 214143 : if (fun->has_simduid_loops)
1285 5607 : note_simd_array_uses (&simd_array_to_simduid_htab, fun);
1286 :
1287 : /* ----------- Analyze loops. ----------- */
1288 214143 : enable_ranger (fun);
1289 :
1290 : /* If some loop was duplicated, it gets bigger number
1291 : than all previously defined loops. This fact allows us to run
1292 : only over initial loops skipping newly generated ones. */
1293 1189011 : for (auto loop : loops_list (fun, 0))
1294 546582 : if (loop->dont_vectorize)
1295 : {
1296 32625 : any_ifcvt_loops = true;
1297 : /* If-conversion sometimes versions both the outer loop
1298 : (for the case when outer loop vectorization might be
1299 : desirable) as well as the inner loop in the scalar version
1300 : of the loop. So we have:
1301 : if (LOOP_VECTORIZED (1, 3))
1302 : {
1303 : loop1
1304 : loop2
1305 : }
1306 : else
1307 : loop3 (copy of loop1)
1308 : if (LOOP_VECTORIZED (4, 5))
1309 : loop4 (copy of loop2)
1310 : else
1311 : loop5 (copy of loop4)
1312 : If loops' iteration gives us loop3 first (which has
1313 : dont_vectorize set), make sure to process loop1 before loop4;
1314 : so that we can prevent vectorization of loop4 if loop1
1315 : is successfully vectorized. */
1316 32625 : if (loop->inner)
1317 : {
1318 2176 : gimple *loop_vectorized_call
1319 2176 : = vect_loop_vectorized_call (loop);
1320 2176 : if (loop_vectorized_call
1321 2176 : && vect_loop_vectorized_call (loop->inner))
1322 : {
1323 924 : tree arg = gimple_call_arg (loop_vectorized_call, 0);
1324 924 : class loop *vector_loop
1325 924 : = get_loop (fun, tree_to_shwi (arg));
1326 924 : if (vector_loop && vector_loop != loop)
1327 : {
1328 : /* Make sure we don't vectorize it twice. */
1329 924 : vector_loop->dont_vectorize = true;
1330 924 : ret |= try_vectorize_loop (simduid_to_vf_htab,
1331 : &num_vectorized_loops,
1332 : vector_loop, fun);
1333 : }
1334 : }
1335 : }
1336 : }
1337 : else
1338 513957 : ret |= try_vectorize_loop (simduid_to_vf_htab, &num_vectorized_loops,
1339 214143 : loop, fun);
1340 :
1341 214143 : vect_location = dump_user_location_t ();
1342 :
1343 214143 : statistics_counter_event (fun, "Vectorized loops", num_vectorized_loops);
1344 214143 : if (dump_enabled_p ()
1345 214143 : || (num_vectorized_loops > 0 && dump_enabled_p ()))
1346 12196 : dump_printf_loc (MSG_NOTE, vect_location,
1347 : "vectorized %u loops in function.\n",
1348 : num_vectorized_loops);
1349 :
1350 : /* ----------- Finalize. ----------- */
1351 214143 : disable_ranger (fun);
1352 :
1353 214143 : if (any_ifcvt_loops)
1354 289154 : for (i = 1; i < number_of_loops (fun); i++)
1355 : {
1356 123871 : class loop *loop = get_loop (fun, i);
1357 123871 : if (loop && loop->dont_vectorize)
1358 : {
1359 34181 : gimple *g = vect_loop_vectorized_call (loop);
1360 34181 : if (g)
1361 : {
1362 18804 : fold_loop_internal_call (g, boolean_false_node);
1363 18804 : loop->dont_vectorize = false;
1364 18804 : ret |= TODO_cleanup_cfg;
1365 18804 : g = NULL;
1366 : }
1367 : else
1368 15377 : g = vect_loop_dist_alias_call (loop, fun);
1369 :
1370 34181 : if (g)
1371 : {
1372 30 : fold_loop_internal_call (g, boolean_false_node);
1373 30 : loop->dont_vectorize = false;
1374 30 : ret |= TODO_cleanup_cfg;
1375 : }
1376 : }
1377 : }
1378 :
1379 : /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */
1380 214143 : if (fun->has_simduid_loops)
1381 : {
1382 5607 : adjust_simduid_builtins (simduid_to_vf_htab, fun);
1383 : /* Avoid stale SCEV cache entries for the SIMD_LANE defs. */
1384 5607 : scev_reset ();
1385 : }
1386 : /* Shrink any "omp array simd" temporary arrays to the
1387 : actual vectorization factors. */
1388 214143 : if (simd_array_to_simduid_htab)
1389 2205 : shrink_simd_arrays (simd_array_to_simduid_htab, simduid_to_vf_htab);
1390 214143 : delete simduid_to_vf_htab;
1391 214143 : fun->has_simduid_loops = false;
1392 :
1393 214143 : if (num_vectorized_loops > 0)
1394 : {
1395 : /* We are collecting some corner cases where we need to update
1396 : virtual SSA form via the TODO but delete the queued update-SSA
1397 : state. Force renaming if we think that might be necessary. */
1398 38755 : if (ret & TODO_update_ssa_only_virtuals)
1399 94 : mark_virtual_operands_for_renaming (cfun);
1400 : /* If we vectorized any loop only virtual SSA form needs to be updated.
1401 : ??? Also while we try hard to update loop-closed SSA form we fail
1402 : to properly do this in some corner-cases (see PR56286). */
1403 38755 : rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_only_virtuals);
1404 38755 : ret |= TODO_cleanup_cfg;
1405 : }
1406 :
1407 1916948 : for (i = 1; i < number_of_loops (fun); i++)
1408 : {
1409 744331 : loop_vec_info loop_vinfo;
1410 744331 : bool has_mask_store;
1411 :
1412 744331 : class loop *loop = get_loop (fun, i);
1413 744331 : if (!loop || !loop->aux)
1414 679935 : continue;
1415 64396 : loop_vinfo = (loop_vec_info) loop->aux;
1416 64396 : has_mask_store = LOOP_VINFO_HAS_MASK_STORE (loop_vinfo);
1417 64396 : delete loop_vinfo;
1418 64396 : if (has_mask_store
1419 64396 : && targetm.vectorize.empty_mask_is_expensive (IFN_MASK_STORE))
1420 499 : optimize_mask_stores (loop);
1421 :
1422 64396 : auto_bitmap exit_bbs;
1423 : /* Perform local CSE, this esp. helps because we emit code for
1424 : predicates that need to be shared for optimal predicate usage.
1425 : However reassoc will re-order them and prevent CSE from working
1426 : as it should. CSE only the loop body, not the entry. */
1427 64396 : auto_vec<edge> exits = get_loop_exit_edges (loop);
1428 259196 : for (edge exit : exits)
1429 66008 : bitmap_set_bit (exit_bbs, exit->dest->index);
1430 :
1431 64396 : edge entry = EDGE_PRED (loop_preheader_edge (loop)->src, 0);
1432 64396 : do_rpo_vn (fun, entry, exit_bbs);
1433 :
1434 64396 : loop->aux = NULL;
1435 64396 : }
1436 :
1437 214143 : vect_slp_fini ();
1438 :
1439 214143 : return ret;
1440 : }
1441 :
1442 : } // anon namespace
1443 :
1444 : gimple_opt_pass *
1445 297180 : make_pass_vectorize (gcc::context *ctxt)
1446 : {
1447 297180 : return new pass_vectorize (ctxt);
1448 : }
1449 :
1450 : /* Entry point to the simduid cleanup pass. */
1451 :
1452 : namespace {
1453 :
1454 : const pass_data pass_data_simduid_cleanup =
1455 : {
1456 : GIMPLE_PASS, /* type */
1457 : "simduid", /* name */
1458 : OPTGROUP_NONE, /* optinfo_flags */
1459 : TV_NONE, /* tv_id */
1460 : ( PROP_ssa | PROP_cfg ), /* properties_required */
1461 : 0, /* properties_provided */
1462 : 0, /* properties_destroyed */
1463 : 0, /* todo_flags_start */
1464 : 0, /* todo_flags_finish */
1465 : };
1466 :
1467 : class pass_simduid_cleanup : public gimple_opt_pass
1468 : {
1469 : public:
1470 594360 : pass_simduid_cleanup (gcc::context *ctxt)
1471 1188720 : : gimple_opt_pass (pass_data_simduid_cleanup, ctxt)
1472 : {}
1473 :
1474 : /* opt_pass methods: */
1475 297180 : opt_pass * clone () final override
1476 : {
1477 297180 : return new pass_simduid_cleanup (m_ctxt);
1478 : }
1479 2580935 : bool gate (function *fun) final override { return fun->has_simduid_loops; }
1480 : unsigned int execute (function *) final override;
1481 :
1482 : }; // class pass_simduid_cleanup
1483 :
1484 : unsigned int
1485 2196 : pass_simduid_cleanup::execute (function *fun)
1486 : {
1487 2196 : hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab = NULL;
1488 :
1489 2196 : note_simd_array_uses (&simd_array_to_simduid_htab, fun);
1490 :
1491 : /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */
1492 2196 : adjust_simduid_builtins (NULL, fun);
1493 :
1494 : /* Shrink any "omp array simd" temporary arrays to the
1495 : actual vectorization factors. */
1496 2196 : if (simd_array_to_simduid_htab)
1497 4 : shrink_simd_arrays (simd_array_to_simduid_htab, NULL);
1498 2196 : fun->has_simduid_loops = false;
1499 2196 : return 0;
1500 : }
1501 :
1502 : } // anon namespace
1503 :
1504 : gimple_opt_pass *
1505 297180 : make_pass_simduid_cleanup (gcc::context *ctxt)
1506 : {
1507 297180 : return new pass_simduid_cleanup (ctxt);
1508 : }
1509 :
1510 :
1511 : /* Entry point to basic block SLP phase. */
1512 :
1513 : namespace {
1514 :
1515 : const pass_data pass_data_slp_vectorize =
1516 : {
1517 : GIMPLE_PASS, /* type */
1518 : "slp", /* name */
1519 : OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
1520 : TV_TREE_SLP_VECTORIZATION, /* tv_id */
1521 : ( PROP_ssa | PROP_cfg ), /* properties_required */
1522 : 0, /* properties_provided */
1523 : 0, /* properties_destroyed */
1524 : 0, /* todo_flags_start */
1525 : TODO_update_ssa, /* todo_flags_finish */
1526 : };
1527 :
1528 : class pass_slp_vectorize : public gimple_opt_pass
1529 : {
1530 : public:
1531 594360 : pass_slp_vectorize (gcc::context *ctxt)
1532 1188720 : : gimple_opt_pass (pass_data_slp_vectorize, ctxt)
1533 : {}
1534 :
1535 : /* opt_pass methods: */
1536 297180 : opt_pass * clone () final override { return new pass_slp_vectorize (m_ctxt); }
1537 1063023 : bool gate (function *) final override { return flag_tree_slp_vectorize != 0; }
1538 : unsigned int execute (function *) final override;
1539 :
1540 : }; // class pass_slp_vectorize
1541 :
1542 : unsigned int
1543 925882 : pass_slp_vectorize::execute (function *fun)
1544 : {
1545 925882 : auto_purge_vect_location sentinel;
1546 925882 : basic_block bb;
1547 :
1548 925882 : bool in_loop_pipeline = scev_initialized_p ();
1549 925882 : if (!in_loop_pipeline)
1550 : {
1551 713450 : loop_optimizer_init (LOOPS_NORMAL);
1552 713450 : scev_initialize ();
1553 : }
1554 :
1555 : /* Mark all stmts as not belonging to the current region and unvisited. */
1556 11860734 : FOR_EACH_BB_FN (bb, fun)
1557 : {
1558 15809394 : for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1559 4874542 : gsi_next (&gsi))
1560 : {
1561 4874542 : gphi *stmt = gsi.phi ();
1562 4874542 : gimple_set_uid (stmt, -1);
1563 4874542 : gimple_set_visited (stmt, false);
1564 : }
1565 106298953 : for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1566 84429249 : gsi_next (&gsi))
1567 : {
1568 84429249 : gimple *stmt = gsi_stmt (gsi);
1569 84429249 : gimple_set_uid (stmt, -1);
1570 84429249 : gimple_set_visited (stmt, false);
1571 : }
1572 : }
1573 :
1574 925882 : vect_slp_init ();
1575 :
1576 925882 : vect_slp_function (fun);
1577 :
1578 925882 : vect_slp_fini ();
1579 :
1580 925882 : if (!in_loop_pipeline)
1581 : {
1582 713450 : scev_finalize ();
1583 713450 : loop_optimizer_finalize ();
1584 : }
1585 :
1586 1851764 : return 0;
1587 925882 : }
1588 :
1589 : } // anon namespace
1590 :
1591 : gimple_opt_pass *
1592 297180 : make_pass_slp_vectorize (gcc::context *ctxt)
1593 : {
1594 297180 : return new pass_slp_vectorize (ctxt);
1595 : }
1596 :
1597 :
1598 : /* Increase alignment of global arrays to improve vectorization potential.
1599 : TODO:
1600 : - Consider also structs that have an array field.
1601 : - Use ipa analysis to prune arrays that can't be vectorized?
1602 : This should involve global alignment analysis and in the future also
1603 : array padding. */
1604 :
1605 : static unsigned get_vec_alignment_for_type (tree);
1606 : static hash_map<tree, unsigned> *type_align_map;
1607 :
1608 : /* Return alignment of array's vector type corresponding to scalar type.
1609 : 0 if no vector type exists. */
1610 : static unsigned
1611 0 : get_vec_alignment_for_array_type (tree type)
1612 : {
1613 0 : gcc_assert (TREE_CODE (type) == ARRAY_TYPE);
1614 0 : poly_uint64 array_size, vector_size;
1615 :
1616 0 : tree scalar_type = strip_array_types (type);
1617 0 : tree vectype = get_related_vectype_for_scalar_type (VOIDmode, scalar_type);
1618 0 : if (!vectype
1619 0 : || !poly_int_tree_p (TYPE_SIZE (type), &array_size)
1620 0 : || !poly_int_tree_p (TYPE_SIZE (vectype), &vector_size)
1621 0 : || maybe_lt (array_size, vector_size))
1622 : return 0;
1623 :
1624 0 : return TYPE_ALIGN (vectype);
1625 : }
1626 :
1627 : /* Return alignment of field having maximum alignment of vector type
1628 : corresponding to it's scalar type. For now, we only consider fields whose
1629 : offset is a multiple of it's vector alignment.
1630 : 0 if no suitable field is found. */
1631 : static unsigned
1632 0 : get_vec_alignment_for_record_type (tree type)
1633 : {
1634 0 : gcc_assert (TREE_CODE (type) == RECORD_TYPE);
1635 :
1636 0 : unsigned max_align = 0, alignment;
1637 0 : HOST_WIDE_INT offset;
1638 0 : tree offset_tree;
1639 :
1640 0 : if (TYPE_PACKED (type))
1641 : return 0;
1642 :
1643 0 : unsigned *slot = type_align_map->get (type);
1644 0 : if (slot)
1645 0 : return *slot;
1646 :
1647 0 : for (tree field = first_field (type);
1648 0 : field != NULL_TREE;
1649 0 : field = DECL_CHAIN (field))
1650 : {
1651 : /* Skip if not FIELD_DECL or if alignment is set by user. */
1652 0 : if (TREE_CODE (field) != FIELD_DECL
1653 0 : || DECL_USER_ALIGN (field)
1654 0 : || DECL_ARTIFICIAL (field))
1655 0 : continue;
1656 :
1657 : /* We don't need to process the type further if offset is variable,
1658 : since the offsets of remaining members will also be variable. */
1659 0 : if (TREE_CODE (DECL_FIELD_OFFSET (field)) != INTEGER_CST
1660 0 : || TREE_CODE (DECL_FIELD_BIT_OFFSET (field)) != INTEGER_CST)
1661 : break;
1662 :
1663 : /* Similarly stop processing the type if offset_tree
1664 : does not fit in unsigned HOST_WIDE_INT. */
1665 0 : offset_tree = bit_position (field);
1666 0 : if (!tree_fits_uhwi_p (offset_tree))
1667 : break;
1668 :
1669 0 : offset = tree_to_uhwi (offset_tree);
1670 0 : alignment = get_vec_alignment_for_type (TREE_TYPE (field));
1671 :
1672 : /* Get maximum alignment of vectorized field/array among those members
1673 : whose offset is multiple of the vector alignment. */
1674 0 : if (alignment
1675 0 : && (offset % alignment == 0)
1676 0 : && (alignment > max_align))
1677 0 : max_align = alignment;
1678 : }
1679 :
1680 0 : type_align_map->put (type, max_align);
1681 0 : return max_align;
1682 : }
1683 :
1684 : /* Return alignment of vector type corresponding to decl's scalar type
1685 : or 0 if it doesn't exist or the vector alignment is lesser than
1686 : decl's alignment. */
1687 : static unsigned
1688 0 : get_vec_alignment_for_type (tree type)
1689 : {
1690 0 : if (type == NULL_TREE)
1691 : return 0;
1692 :
1693 0 : gcc_assert (TYPE_P (type));
1694 :
1695 0 : static unsigned alignment = 0;
1696 0 : switch (TREE_CODE (type))
1697 : {
1698 0 : case ARRAY_TYPE:
1699 0 : alignment = get_vec_alignment_for_array_type (type);
1700 0 : break;
1701 0 : case RECORD_TYPE:
1702 0 : alignment = get_vec_alignment_for_record_type (type);
1703 0 : break;
1704 0 : default:
1705 0 : alignment = 0;
1706 0 : break;
1707 : }
1708 :
1709 0 : return (alignment > TYPE_ALIGN (type)) ? alignment : 0;
1710 : }
1711 :
1712 : /* Entry point to increase_alignment pass. */
1713 : static unsigned int
1714 0 : increase_alignment (void)
1715 : {
1716 0 : varpool_node *vnode;
1717 :
1718 0 : vect_location = dump_user_location_t ();
1719 0 : type_align_map = new hash_map<tree, unsigned>;
1720 :
1721 : /* Increase the alignment of all global arrays for vectorization. */
1722 0 : FOR_EACH_DEFINED_VARIABLE (vnode)
1723 : {
1724 0 : tree decl = vnode->decl;
1725 0 : unsigned int alignment;
1726 :
1727 0 : if ((decl_in_symtab_p (decl)
1728 0 : && !symtab_node::get (decl)->can_increase_alignment_p ())
1729 0 : || DECL_USER_ALIGN (decl) || DECL_ARTIFICIAL (decl))
1730 0 : continue;
1731 :
1732 0 : alignment = get_vec_alignment_for_type (TREE_TYPE (decl));
1733 0 : if (alignment && vect_can_force_dr_alignment_p (decl, alignment))
1734 : {
1735 0 : vnode->increase_alignment (alignment);
1736 0 : if (dump_enabled_p ())
1737 0 : dump_printf (MSG_NOTE, "Increasing alignment of decl: %T\n", decl);
1738 : }
1739 : }
1740 :
1741 0 : delete type_align_map;
1742 0 : return 0;
1743 : }
1744 :
1745 :
1746 : namespace {
1747 :
1748 : const pass_data pass_data_ipa_increase_alignment =
1749 : {
1750 : SIMPLE_IPA_PASS, /* type */
1751 : "increase_alignment", /* name */
1752 : OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
1753 : TV_IPA_OPT, /* tv_id */
1754 : 0, /* properties_required */
1755 : 0, /* properties_provided */
1756 : 0, /* properties_destroyed */
1757 : 0, /* todo_flags_start */
1758 : 0, /* todo_flags_finish */
1759 : };
1760 :
1761 : class pass_ipa_increase_alignment : public simple_ipa_opt_pass
1762 : {
1763 : public:
1764 297180 : pass_ipa_increase_alignment (gcc::context *ctxt)
1765 594360 : : simple_ipa_opt_pass (pass_data_ipa_increase_alignment, ctxt)
1766 : {}
1767 :
1768 : /* opt_pass methods: */
1769 239073 : bool gate (function *) final override
1770 : {
1771 239073 : return flag_section_anchors && flag_tree_loop_vectorize;
1772 : }
1773 :
1774 0 : unsigned int execute (function *) final override
1775 : {
1776 0 : return increase_alignment ();
1777 : }
1778 :
1779 : }; // class pass_ipa_increase_alignment
1780 :
1781 : } // anon namespace
1782 :
1783 : simple_ipa_opt_pass *
1784 297180 : make_pass_ipa_increase_alignment (gcc::context *ctxt)
1785 : {
1786 297180 : return new pass_ipa_increase_alignment (ctxt);
1787 : }
1788 :
1789 : /* If the condition represented by T is a comparison or the SSA name
1790 : result of a comparison, extract the comparison's operands. Represent
1791 : T as NE_EXPR <T, 0> otherwise. */
1792 :
1793 : void
1794 60843 : scalar_cond_masked_key::get_cond_ops_from_tree (tree t)
1795 : {
1796 60843 : if (TREE_CODE_CLASS (TREE_CODE (t)) == tcc_comparison)
1797 : {
1798 0 : this->code = TREE_CODE (t);
1799 0 : this->op0 = TREE_OPERAND (t, 0);
1800 0 : this->op1 = TREE_OPERAND (t, 1);
1801 0 : this->inverted_p = false;
1802 0 : return;
1803 : }
1804 :
1805 60843 : if (TREE_CODE (t) == SSA_NAME)
1806 26616 : if (gassign *stmt = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (t)))
1807 : {
1808 26616 : tree_code code = gimple_assign_rhs_code (stmt);
1809 26616 : if (TREE_CODE_CLASS (code) == tcc_comparison)
1810 : {
1811 18297 : this->code = code;
1812 18297 : this->op0 = gimple_assign_rhs1 (stmt);
1813 18297 : this->op1 = gimple_assign_rhs2 (stmt);
1814 18297 : this->inverted_p = false;
1815 18297 : return;
1816 : }
1817 8319 : else if (code == BIT_NOT_EXPR)
1818 : {
1819 3475 : tree n_op = gimple_assign_rhs1 (stmt);
1820 3475 : if ((stmt = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (n_op))))
1821 : {
1822 3475 : code = gimple_assign_rhs_code (stmt);
1823 3475 : if (TREE_CODE_CLASS (code) == tcc_comparison)
1824 : {
1825 3439 : this->code = code;
1826 3439 : this->op0 = gimple_assign_rhs1 (stmt);
1827 3439 : this->op1 = gimple_assign_rhs2 (stmt);
1828 3439 : this->inverted_p = true;
1829 3439 : return;
1830 : }
1831 : }
1832 : }
1833 : }
1834 :
1835 39107 : this->code = NE_EXPR;
1836 39107 : this->op0 = t;
1837 39107 : this->op1 = build_zero_cst (TREE_TYPE (t));
1838 39107 : this->inverted_p = false;
1839 : }
1840 :
1841 : /* See the comment above the declaration for details. */
1842 :
1843 : unsigned int
1844 0 : vector_costs::add_stmt_cost (int count, vect_cost_for_stmt kind,
1845 : stmt_vec_info stmt_info, slp_tree,
1846 : tree vectype, int misalign,
1847 : vect_cost_model_location where)
1848 : {
1849 0 : unsigned int cost
1850 0 : = builtin_vectorization_cost (kind, vectype, misalign) * count;
1851 0 : return record_stmt_cost (stmt_info, where, cost);
1852 : }
1853 :
1854 : unsigned int
1855 2835405 : vector_costs::add_slp_cost (slp_tree,
1856 : const array_slice<stmt_info_for_cost> &cost_vec)
1857 : {
1858 2835405 : unsigned int sum = 0;
1859 6401862 : for (auto item : cost_vec)
1860 3566457 : sum += ::add_stmt_cost (this, item.count, item.kind, item.stmt_info,
1861 : item.node, item.vectype, item.misalign, item.where);
1862 2835405 : return sum;
1863 : }
1864 :
1865 : /* See the comment above the declaration for details. */
1866 :
1867 : void
1868 1971290 : vector_costs::finish_cost (const vector_costs *)
1869 : {
1870 1971290 : gcc_assert (!m_finished);
1871 1971290 : m_finished = true;
1872 1971290 : }
1873 :
1874 : /* Record a base cost of COST units against WHERE. If STMT_INFO is
1875 : nonnull, use it to adjust the cost based on execution frequency
1876 : (where appropriate). */
1877 :
1878 : unsigned int
1879 0 : vector_costs::record_stmt_cost (stmt_vec_info stmt_info,
1880 : vect_cost_model_location where,
1881 : unsigned int cost)
1882 : {
1883 0 : cost = adjust_cost_for_freq (stmt_info, where, cost);
1884 0 : m_costs[where] += cost;
1885 0 : return cost;
1886 : }
1887 :
1888 : /* COST is the base cost we have calculated for an operation in location WHERE.
1889 : If STMT_INFO is nonnull, use it to adjust the cost based on execution
1890 : frequency (where appropriate). Return the adjusted cost. */
1891 :
1892 : unsigned int
1893 8120880 : vector_costs::adjust_cost_for_freq (stmt_vec_info stmt_info,
1894 : vect_cost_model_location where,
1895 : unsigned int cost)
1896 : {
1897 : /* Statements in an inner loop relative to the loop being
1898 : vectorized are weighted more heavily. The value here is
1899 : arbitrary and could potentially be improved with analysis. */
1900 8120880 : if (where == vect_body
1901 8120880 : && stmt_info
1902 8120880 : && stmt_in_inner_loop_p (m_vinfo, stmt_info))
1903 : {
1904 11352 : loop_vec_info loop_vinfo = as_a<loop_vec_info> (m_vinfo);
1905 11352 : cost *= LOOP_VINFO_INNER_LOOP_COST_FACTOR (loop_vinfo);
1906 : }
1907 8120880 : return cost;
1908 : }
1909 :
1910 : /* See the comment above the declaration for details. */
1911 :
1912 : bool
1913 34603 : vector_costs::better_main_loop_than_p (const vector_costs *other) const
1914 : {
1915 34603 : int diff = compare_inside_loop_cost (other);
1916 34603 : if (diff != 0)
1917 34388 : return diff < 0;
1918 :
1919 : /* If there's nothing to choose between the loop bodies, see whether
1920 : there's a difference in the prologue and epilogue costs. */
1921 215 : diff = compare_outside_loop_cost (other);
1922 215 : if (diff != 0)
1923 149 : return diff < 0;
1924 :
1925 : return false;
1926 : }
1927 :
1928 :
1929 : /* See the comment above the declaration for details. */
1930 :
1931 : bool
1932 1485 : vector_costs::better_epilogue_loop_than_p (const vector_costs *other,
1933 : loop_vec_info main_loop) const
1934 : {
1935 1485 : loop_vec_info this_loop_vinfo = as_a<loop_vec_info> (this->m_vinfo);
1936 1485 : loop_vec_info other_loop_vinfo = as_a<loop_vec_info> (other->m_vinfo);
1937 :
1938 1485 : poly_int64 this_vf = LOOP_VINFO_VECT_FACTOR (this_loop_vinfo);
1939 1485 : poly_int64 other_vf = LOOP_VINFO_VECT_FACTOR (other_loop_vinfo);
1940 :
1941 1485 : poly_uint64 main_poly_vf = LOOP_VINFO_VECT_FACTOR (main_loop);
1942 1485 : unsigned HOST_WIDE_INT main_vf;
1943 1485 : unsigned HOST_WIDE_INT other_factor, this_factor, other_cost, this_cost;
1944 : /* If we can determine how many iterations are left for the epilogue
1945 : loop, that is if both the main loop's vectorization factor and number
1946 : of iterations are constant, then we use them to calculate the cost of
1947 : the epilogue loop together with a 'likely value' for the epilogues
1948 : vectorization factor. Otherwise we use the main loop's vectorization
1949 : factor and the maximum poly value for the epilogue's. If the target
1950 : has not provided with a sensible upper bound poly vectorization
1951 : factors are likely to be favored over constant ones. */
1952 1485 : if (main_poly_vf.is_constant (&main_vf)
1953 1485 : && LOOP_VINFO_NITERS_KNOWN_P (main_loop))
1954 : {
1955 91 : unsigned HOST_WIDE_INT niters
1956 91 : = LOOP_VINFO_INT_NITERS (main_loop) % main_vf;
1957 91 : HOST_WIDE_INT other_likely_vf
1958 91 : = estimated_poly_value (other_vf, POLY_VALUE_LIKELY);
1959 91 : HOST_WIDE_INT this_likely_vf
1960 91 : = estimated_poly_value (this_vf, POLY_VALUE_LIKELY);
1961 :
1962 : /* If the epilogue is using partial vectors we account for the
1963 : partial iteration here too. */
1964 91 : other_factor = niters / other_likely_vf;
1965 91 : if (LOOP_VINFO_USING_PARTIAL_VECTORS_P (other_loop_vinfo)
1966 0 : && niters % other_likely_vf != 0)
1967 0 : other_factor++;
1968 :
1969 91 : this_factor = niters / this_likely_vf;
1970 91 : if (LOOP_VINFO_USING_PARTIAL_VECTORS_P (this_loop_vinfo)
1971 0 : && niters % this_likely_vf != 0)
1972 0 : this_factor++;
1973 : }
1974 : else
1975 : {
1976 : unsigned HOST_WIDE_INT main_vf_max
1977 1394 : = estimated_poly_value (main_poly_vf, POLY_VALUE_MAX);
1978 1394 : unsigned HOST_WIDE_INT other_vf_max
1979 1394 : = estimated_poly_value (other_vf, POLY_VALUE_MAX);
1980 1394 : unsigned HOST_WIDE_INT this_vf_max
1981 1394 : = estimated_poly_value (this_vf, POLY_VALUE_MAX);
1982 :
1983 1394 : other_factor = CEIL (main_vf_max, other_vf_max);
1984 1394 : this_factor = CEIL (main_vf_max, this_vf_max);
1985 :
1986 : /* If the loop is not using partial vectors then it will iterate one
1987 : time less than one that does. It is safe to subtract one here,
1988 : because the main loop's vf is always at least 2x bigger than that
1989 : of an epilogue. */
1990 1394 : if (!LOOP_VINFO_USING_PARTIAL_VECTORS_P (other_loop_vinfo))
1991 1379 : other_factor -= 1;
1992 1394 : if (!LOOP_VINFO_USING_PARTIAL_VECTORS_P (this_loop_vinfo))
1993 1393 : this_factor -= 1;
1994 : }
1995 :
1996 : /* Compute the costs by multiplying the inside costs with the factor and
1997 : add the outside costs for a more complete picture. The factor is the
1998 : amount of times we are expecting to iterate this epilogue. */
1999 1485 : other_cost = other->body_cost () * other_factor;
2000 1485 : this_cost = this->body_cost () * this_factor;
2001 1485 : other_cost += other->outside_cost ();
2002 1485 : this_cost += this->outside_cost ();
2003 1485 : return this_cost < other_cost;
2004 : }
2005 :
2006 : /* A <=>-style subroutine of better_main_loop_than_p. Check whether we can
2007 : determine the return value of better_main_loop_than_p by comparing the
2008 : inside (loop body) costs of THIS and OTHER. Return:
2009 :
2010 : * -1 if better_main_loop_than_p should return true.
2011 : * 1 if better_main_loop_than_p should return false.
2012 : * 0 if we can't decide. */
2013 :
2014 : int
2015 34603 : vector_costs::compare_inside_loop_cost (const vector_costs *other) const
2016 : {
2017 34603 : loop_vec_info this_loop_vinfo = as_a<loop_vec_info> (this->m_vinfo);
2018 34603 : loop_vec_info other_loop_vinfo = as_a<loop_vec_info> (other->m_vinfo);
2019 :
2020 34603 : struct loop *loop = LOOP_VINFO_LOOP (this_loop_vinfo);
2021 34603 : gcc_assert (LOOP_VINFO_LOOP (other_loop_vinfo) == loop);
2022 :
2023 34603 : poly_int64 this_vf = LOOP_VINFO_VECT_FACTOR (this_loop_vinfo);
2024 34603 : poly_int64 other_vf = LOOP_VINFO_VECT_FACTOR (other_loop_vinfo);
2025 :
2026 : /* Limit the VFs to what is likely to be the maximum number of iterations,
2027 : to handle cases in which at least one loop_vinfo is fully-masked. */
2028 34603 : HOST_WIDE_INT estimated_max_niter = likely_max_stmt_executions_int (loop);
2029 34603 : if (estimated_max_niter != -1)
2030 : {
2031 33523 : if (estimated_poly_value (this_vf, POLY_VALUE_MIN)
2032 : >= estimated_max_niter)
2033 : this_vf = estimated_max_niter;
2034 33523 : if (estimated_poly_value (other_vf, POLY_VALUE_MIN)
2035 : >= estimated_max_niter)
2036 : other_vf = estimated_max_niter;
2037 : }
2038 :
2039 : /* Check whether the (fractional) cost per scalar iteration is lower or
2040 : higher: this_inside_cost / this_vf vs. other_inside_cost / other_vf. */
2041 34603 : poly_int64 rel_this = this_loop_vinfo->vector_costs->body_cost () * other_vf;
2042 34603 : poly_int64 rel_other
2043 34603 : = other_loop_vinfo->vector_costs->body_cost () * this_vf;
2044 :
2045 34603 : HOST_WIDE_INT est_rel_this_min
2046 34603 : = estimated_poly_value (rel_this, POLY_VALUE_MIN);
2047 34603 : HOST_WIDE_INT est_rel_this_max
2048 34603 : = estimated_poly_value (rel_this, POLY_VALUE_MAX);
2049 :
2050 34603 : HOST_WIDE_INT est_rel_other_min
2051 34603 : = estimated_poly_value (rel_other, POLY_VALUE_MIN);
2052 34603 : HOST_WIDE_INT est_rel_other_max
2053 34603 : = estimated_poly_value (rel_other, POLY_VALUE_MAX);
2054 :
2055 : /* Check first if we can make out an unambiguous total order from the minimum
2056 : and maximum estimates. */
2057 34603 : if (est_rel_this_min < est_rel_other_min
2058 : && est_rel_this_max < est_rel_other_max)
2059 : return -1;
2060 :
2061 33472 : if (est_rel_other_min < est_rel_this_min
2062 : && est_rel_other_max < est_rel_this_max)
2063 33257 : return 1;
2064 :
2065 : /* When other_loop_vinfo uses a variable vectorization factor,
2066 : we know that it has a lower cost for at least one runtime VF.
2067 : However, we don't know how likely that VF is.
2068 :
2069 : One option would be to compare the costs for the estimated VFs.
2070 : The problem is that that can put too much pressure on the cost
2071 : model. E.g. if the estimated VF is also the lowest possible VF,
2072 : and if other_loop_vinfo is 1 unit worse than this_loop_vinfo
2073 : for the estimated VF, we'd then choose this_loop_vinfo even
2074 : though (a) this_loop_vinfo might not actually be better than
2075 : other_loop_vinfo for that VF and (b) it would be significantly
2076 : worse at larger VFs.
2077 :
2078 : Here we go for a hacky compromise: pick this_loop_vinfo if it is
2079 : no more expensive than other_loop_vinfo even after doubling the
2080 : estimated other_loop_vinfo VF. For all but trivial loops, this
2081 : ensures that we only pick this_loop_vinfo if it is significantly
2082 : better than other_loop_vinfo at the estimated VF. */
2083 : if (est_rel_other_min != est_rel_this_min
2084 : || est_rel_other_max != est_rel_this_max)
2085 : {
2086 : HOST_WIDE_INT est_rel_this_likely
2087 : = estimated_poly_value (rel_this, POLY_VALUE_LIKELY);
2088 : HOST_WIDE_INT est_rel_other_likely
2089 : = estimated_poly_value (rel_other, POLY_VALUE_LIKELY);
2090 :
2091 : return est_rel_this_likely * 2 <= est_rel_other_likely ? -1 : 1;
2092 : }
2093 :
2094 : return 0;
2095 : }
2096 :
2097 : /* A <=>-style subroutine of better_main_loop_than_p, used when there is
2098 : nothing to choose between the inside (loop body) costs of THIS and OTHER.
2099 : Check whether we can determine the return value of better_main_loop_than_p
2100 : by comparing the outside (prologue and epilogue) costs of THIS and OTHER.
2101 : Return:
2102 :
2103 : * -1 if better_main_loop_than_p should return true.
2104 : * 1 if better_main_loop_than_p should return false.
2105 : * 0 if we can't decide. */
2106 :
2107 : int
2108 215 : vector_costs::compare_outside_loop_cost (const vector_costs *other) const
2109 : {
2110 215 : auto this_outside_cost = this->outside_cost ();
2111 215 : auto other_outside_cost = other->outside_cost ();
2112 215 : if (this_outside_cost != other_outside_cost)
2113 149 : return this_outside_cost < other_outside_cost ? -1 : 1;
2114 :
2115 : return 0;
2116 : }
|