hppa: Fix LO_SUM DLTIND14R address support in PRINT_OPERAND_ADDRESS
[official-gcc.git] / gcc / tree-vectorizer.cc
blob9001b738bf3196ceefd20cc308feb78941595b5d
1 /* Vectorizer
2 Copyright (C) 2003-2024 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
5 This file is part of GCC.
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.
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.
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/>. */
21 /* Loop and basic block vectorizer.
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
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)
41 Here's a poor attempt at illustrating that:
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
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"
87 /* Loop or bb location, with hotness information. */
88 dump_user_location_t vect_location;
90 /* auto_purge_vect_location's dtor: reset the vect_location
91 global, to avoid stale location_t values that could reference
92 GC-ed blocks. */
94 auto_purge_vect_location::~auto_purge_vect_location ()
96 vect_location = dump_user_location_t ();
99 /* Dump a cost entry according to args to F. */
101 void
102 dump_stmt_cost (FILE *f, int count, enum vect_cost_for_stmt kind,
103 stmt_vec_info stmt_info, slp_tree node, tree,
104 int misalign, unsigned cost,
105 enum vect_cost_model_location where)
107 if (stmt_info)
109 print_gimple_expr (f, STMT_VINFO_STMT (stmt_info), 0, TDF_SLIM);
110 fprintf (f, " ");
112 else if (node)
113 fprintf (f, "node %p ", (void *)node);
114 else
115 fprintf (f, "<unknown> ");
116 fprintf (f, "%d times ", count);
117 const char *ks = "unknown";
118 switch (kind)
120 case scalar_stmt:
121 ks = "scalar_stmt";
122 break;
123 case scalar_load:
124 ks = "scalar_load";
125 break;
126 case scalar_store:
127 ks = "scalar_store";
128 break;
129 case vector_stmt:
130 ks = "vector_stmt";
131 break;
132 case vector_load:
133 ks = "vector_load";
134 break;
135 case vector_gather_load:
136 ks = "vector_gather_load";
137 break;
138 case unaligned_load:
139 ks = "unaligned_load";
140 break;
141 case unaligned_store:
142 ks = "unaligned_store";
143 break;
144 case vector_store:
145 ks = "vector_store";
146 break;
147 case vector_scatter_store:
148 ks = "vector_scatter_store";
149 break;
150 case vec_to_scalar:
151 ks = "vec_to_scalar";
152 break;
153 case scalar_to_vec:
154 ks = "scalar_to_vec";
155 break;
156 case cond_branch_not_taken:
157 ks = "cond_branch_not_taken";
158 break;
159 case cond_branch_taken:
160 ks = "cond_branch_taken";
161 break;
162 case vec_perm:
163 ks = "vec_perm";
164 break;
165 case vec_promote_demote:
166 ks = "vec_promote_demote";
167 break;
168 case vec_construct:
169 ks = "vec_construct";
170 break;
172 fprintf (f, "%s ", ks);
173 if (kind == unaligned_load || kind == unaligned_store)
174 fprintf (f, "(misalign %d) ", misalign);
175 fprintf (f, "costs %u ", cost);
176 const char *ws = "unknown";
177 switch (where)
179 case vect_prologue:
180 ws = "prologue";
181 break;
182 case vect_body:
183 ws = "body";
184 break;
185 case vect_epilogue:
186 ws = "epilogue";
187 break;
189 fprintf (f, "in %s\n", ws);
192 /* For mapping simduid to vectorization factor. */
194 class simduid_to_vf : public free_ptr_hash<simduid_to_vf>
196 public:
197 unsigned int simduid;
198 poly_uint64 vf;
200 /* hash_table support. */
201 static inline hashval_t hash (const simduid_to_vf *);
202 static inline int equal (const simduid_to_vf *, const simduid_to_vf *);
205 inline hashval_t
206 simduid_to_vf::hash (const simduid_to_vf *p)
208 return p->simduid;
211 inline int
212 simduid_to_vf::equal (const simduid_to_vf *p1, const simduid_to_vf *p2)
214 return p1->simduid == p2->simduid;
217 /* This hash maps the OMP simd array to the corresponding simduid used
218 to index into it. Like thus,
220 _7 = GOMP_SIMD_LANE (simduid.0)
223 D.1737[_7] = stuff;
226 This hash maps from the OMP simd array (D.1737[]) to DECL_UID of
227 simduid.0. */
229 struct simd_array_to_simduid : free_ptr_hash<simd_array_to_simduid>
231 tree decl;
232 unsigned int simduid;
234 /* hash_table support. */
235 static inline hashval_t hash (const simd_array_to_simduid *);
236 static inline int equal (const simd_array_to_simduid *,
237 const simd_array_to_simduid *);
240 inline hashval_t
241 simd_array_to_simduid::hash (const simd_array_to_simduid *p)
243 return DECL_UID (p->decl);
246 inline int
247 simd_array_to_simduid::equal (const simd_array_to_simduid *p1,
248 const simd_array_to_simduid *p2)
250 return p1->decl == p2->decl;
253 /* Fold IFN_GOMP_SIMD_LANE, IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LAST_LANE,
254 into their corresponding constants and remove
255 IFN_GOMP_SIMD_ORDERED_{START,END}. */
257 static void
258 adjust_simduid_builtins (hash_table<simduid_to_vf> *htab, function *fun)
260 basic_block bb;
262 FOR_EACH_BB_FN (bb, fun)
264 gimple_stmt_iterator i;
266 for (i = gsi_start_bb (bb); !gsi_end_p (i); )
268 poly_uint64 vf = 1;
269 enum internal_fn ifn;
270 gimple *stmt = gsi_stmt (i);
271 tree t;
272 if (!is_gimple_call (stmt)
273 || !gimple_call_internal_p (stmt))
275 gsi_next (&i);
276 continue;
278 ifn = gimple_call_internal_fn (stmt);
279 switch (ifn)
281 case IFN_GOMP_SIMD_LANE:
282 case IFN_GOMP_SIMD_VF:
283 case IFN_GOMP_SIMD_LAST_LANE:
284 break;
285 case IFN_GOMP_SIMD_ORDERED_START:
286 case IFN_GOMP_SIMD_ORDERED_END:
287 if (integer_onep (gimple_call_arg (stmt, 0)))
289 enum built_in_function bcode
290 = (ifn == IFN_GOMP_SIMD_ORDERED_START
291 ? BUILT_IN_GOMP_ORDERED_START
292 : BUILT_IN_GOMP_ORDERED_END);
293 gimple *g
294 = gimple_build_call (builtin_decl_explicit (bcode), 0);
295 gimple_move_vops (g, stmt);
296 gsi_replace (&i, g, true);
297 continue;
299 gsi_remove (&i, true);
300 unlink_stmt_vdef (stmt);
301 continue;
302 default:
303 gsi_next (&i);
304 continue;
306 tree arg = gimple_call_arg (stmt, 0);
307 gcc_assert (arg != NULL_TREE);
308 gcc_assert (TREE_CODE (arg) == SSA_NAME);
309 simduid_to_vf *p = NULL, data;
310 data.simduid = DECL_UID (SSA_NAME_VAR (arg));
311 /* Need to nullify loop safelen field since it's value is not
312 valid after transformation. */
313 if (bb->loop_father && bb->loop_father->safelen > 0)
314 bb->loop_father->safelen = 0;
315 if (htab)
317 p = htab->find (&data);
318 if (p)
319 vf = p->vf;
321 switch (ifn)
323 case IFN_GOMP_SIMD_VF:
324 t = build_int_cst (unsigned_type_node, vf);
325 break;
326 case IFN_GOMP_SIMD_LANE:
327 t = build_int_cst (unsigned_type_node, 0);
328 break;
329 case IFN_GOMP_SIMD_LAST_LANE:
330 t = gimple_call_arg (stmt, 1);
331 break;
332 default:
333 gcc_unreachable ();
335 tree lhs = gimple_call_lhs (stmt);
336 if (lhs)
337 replace_uses_by (lhs, t);
338 release_defs (stmt);
339 gsi_remove (&i, true);
344 /* Helper structure for note_simd_array_uses. */
346 struct note_simd_array_uses_struct
348 hash_table<simd_array_to_simduid> **htab;
349 unsigned int simduid;
352 /* Callback for note_simd_array_uses, called through walk_gimple_op. */
354 static tree
355 note_simd_array_uses_cb (tree *tp, int *walk_subtrees, void *data)
357 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
358 struct note_simd_array_uses_struct *ns
359 = (struct note_simd_array_uses_struct *) wi->info;
361 if (TYPE_P (*tp))
362 *walk_subtrees = 0;
363 else if (VAR_P (*tp)
364 && lookup_attribute ("omp simd array", DECL_ATTRIBUTES (*tp))
365 && DECL_CONTEXT (*tp) == current_function_decl)
367 simd_array_to_simduid data;
368 if (!*ns->htab)
369 *ns->htab = new hash_table<simd_array_to_simduid> (15);
370 data.decl = *tp;
371 data.simduid = ns->simduid;
372 simd_array_to_simduid **slot = (*ns->htab)->find_slot (&data, INSERT);
373 if (*slot == NULL)
375 simd_array_to_simduid *p = XNEW (simd_array_to_simduid);
376 *p = data;
377 *slot = p;
379 else if ((*slot)->simduid != ns->simduid)
380 (*slot)->simduid = -1U;
381 *walk_subtrees = 0;
383 return NULL_TREE;
386 /* Find "omp simd array" temporaries and map them to corresponding
387 simduid. */
389 static void
390 note_simd_array_uses (hash_table<simd_array_to_simduid> **htab, function *fun)
392 basic_block bb;
393 gimple_stmt_iterator gsi;
394 struct walk_stmt_info wi;
395 struct note_simd_array_uses_struct ns;
397 memset (&wi, 0, sizeof (wi));
398 wi.info = &ns;
399 ns.htab = htab;
401 FOR_EACH_BB_FN (bb, fun)
402 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
404 gimple *stmt = gsi_stmt (gsi);
405 if (!is_gimple_call (stmt) || !gimple_call_internal_p (stmt))
406 continue;
407 switch (gimple_call_internal_fn (stmt))
409 case IFN_GOMP_SIMD_LANE:
410 case IFN_GOMP_SIMD_VF:
411 case IFN_GOMP_SIMD_LAST_LANE:
412 break;
413 default:
414 continue;
416 tree lhs = gimple_call_lhs (stmt);
417 if (lhs == NULL_TREE)
418 continue;
419 imm_use_iterator use_iter;
420 gimple *use_stmt;
421 ns.simduid = DECL_UID (SSA_NAME_VAR (gimple_call_arg (stmt, 0)));
422 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, lhs)
423 if (!is_gimple_debug (use_stmt))
424 walk_gimple_op (use_stmt, note_simd_array_uses_cb, &wi);
428 /* Shrink arrays with "omp simd array" attribute to the corresponding
429 vectorization factor. */
431 static void
432 shrink_simd_arrays
433 (hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab,
434 hash_table<simduid_to_vf> *simduid_to_vf_htab)
436 for (hash_table<simd_array_to_simduid>::iterator iter
437 = simd_array_to_simduid_htab->begin ();
438 iter != simd_array_to_simduid_htab->end (); ++iter)
439 if ((*iter)->simduid != -1U)
441 tree decl = (*iter)->decl;
442 poly_uint64 vf = 1;
443 if (simduid_to_vf_htab)
445 simduid_to_vf *p = NULL, data;
446 data.simduid = (*iter)->simduid;
447 p = simduid_to_vf_htab->find (&data);
448 if (p)
449 vf = p->vf;
451 tree atype
452 = build_array_type_nelts (TREE_TYPE (TREE_TYPE (decl)), vf);
453 TREE_TYPE (decl) = atype;
454 relayout_decl (decl);
457 delete simd_array_to_simduid_htab;
460 /* Initialize the vec_info with kind KIND_IN and target cost data
461 TARGET_COST_DATA_IN. */
463 vec_info::vec_info (vec_info::vec_kind kind_in, vec_info_shared *shared_)
464 : kind (kind_in),
465 shared (shared_),
466 stmt_vec_info_ro (false)
468 stmt_vec_infos.create (50);
471 vec_info::~vec_info ()
473 for (slp_instance &instance : slp_instances)
474 vect_free_slp_instance (instance);
476 free_stmt_vec_infos ();
479 vec_info_shared::vec_info_shared ()
480 : n_stmts (0),
481 datarefs (vNULL),
482 datarefs_copy (vNULL),
483 ddrs (vNULL)
487 vec_info_shared::~vec_info_shared ()
489 free_data_refs (datarefs);
490 free_dependence_relations (ddrs);
491 datarefs_copy.release ();
494 void
495 vec_info_shared::save_datarefs ()
497 if (!flag_checking)
498 return;
499 datarefs_copy.reserve_exact (datarefs.length ());
500 for (unsigned i = 0; i < datarefs.length (); ++i)
501 datarefs_copy.quick_push (*datarefs[i]);
504 void
505 vec_info_shared::check_datarefs ()
507 if (!flag_checking)
508 return;
509 gcc_assert (datarefs.length () == datarefs_copy.length ());
510 for (unsigned i = 0; i < datarefs.length (); ++i)
511 if (memcmp (&datarefs_copy[i], datarefs[i],
512 offsetof (data_reference, alt_indices)) != 0)
513 gcc_unreachable ();
516 /* Record that STMT belongs to the vectorizable region. Create and return
517 an associated stmt_vec_info. */
519 stmt_vec_info
520 vec_info::add_stmt (gimple *stmt)
522 stmt_vec_info res = new_stmt_vec_info (stmt);
523 set_vinfo_for_stmt (stmt, res);
524 return res;
527 /* Record that STMT belongs to the vectorizable region. Create a new
528 stmt_vec_info and mark VECINFO as being related and return the new
529 stmt_vec_info. */
531 stmt_vec_info
532 vec_info::add_pattern_stmt (gimple *stmt, stmt_vec_info stmt_info)
534 stmt_vec_info res = new_stmt_vec_info (stmt);
535 set_vinfo_for_stmt (stmt, res, false);
536 STMT_VINFO_RELATED_STMT (res) = stmt_info;
537 return res;
540 /* If STMT has an associated stmt_vec_info, return that vec_info, otherwise
541 return null. It is safe to call this function on any statement, even if
542 it might not be part of the vectorizable region. */
544 stmt_vec_info
545 vec_info::lookup_stmt (gimple *stmt)
547 unsigned int uid = gimple_uid (stmt);
548 if (uid > 0 && uid - 1 < stmt_vec_infos.length ())
550 stmt_vec_info res = stmt_vec_infos[uid - 1];
551 if (res && res->stmt == stmt)
552 return res;
554 return NULL;
557 /* If NAME is an SSA_NAME and its definition has an associated stmt_vec_info,
558 return that stmt_vec_info, otherwise return null. It is safe to call
559 this on arbitrary operands. */
561 stmt_vec_info
562 vec_info::lookup_def (tree name)
564 if (TREE_CODE (name) == SSA_NAME
565 && !SSA_NAME_IS_DEFAULT_DEF (name))
566 return lookup_stmt (SSA_NAME_DEF_STMT (name));
567 return NULL;
570 /* See whether there is a single non-debug statement that uses LHS and
571 whether that statement has an associated stmt_vec_info. Return the
572 stmt_vec_info if so, otherwise return null. */
574 stmt_vec_info
575 vec_info::lookup_single_use (tree lhs)
577 use_operand_p dummy;
578 gimple *use_stmt;
579 if (single_imm_use (lhs, &dummy, &use_stmt))
580 return lookup_stmt (use_stmt);
581 return NULL;
584 /* Return vectorization information about DR. */
586 dr_vec_info *
587 vec_info::lookup_dr (data_reference *dr)
589 stmt_vec_info stmt_info = lookup_stmt (DR_STMT (dr));
590 /* DR_STMT should never refer to a stmt in a pattern replacement. */
591 gcc_checking_assert (!is_pattern_stmt_p (stmt_info));
592 return STMT_VINFO_DR_INFO (stmt_info->dr_aux.stmt);
595 /* Record that NEW_STMT_INFO now implements the same data reference
596 as OLD_STMT_INFO. */
598 void
599 vec_info::move_dr (stmt_vec_info new_stmt_info, stmt_vec_info old_stmt_info)
601 gcc_assert (!is_pattern_stmt_p (old_stmt_info));
602 STMT_VINFO_DR_INFO (old_stmt_info)->stmt = new_stmt_info;
603 new_stmt_info->dr_aux = old_stmt_info->dr_aux;
604 STMT_VINFO_DR_WRT_VEC_LOOP (new_stmt_info)
605 = STMT_VINFO_DR_WRT_VEC_LOOP (old_stmt_info);
606 STMT_VINFO_GATHER_SCATTER_P (new_stmt_info)
607 = STMT_VINFO_GATHER_SCATTER_P (old_stmt_info);
610 /* Permanently remove the statement described by STMT_INFO from the
611 function. */
613 void
614 vec_info::remove_stmt (stmt_vec_info stmt_info)
616 gcc_assert (!stmt_info->pattern_stmt_p);
617 set_vinfo_for_stmt (stmt_info->stmt, NULL);
618 unlink_stmt_vdef (stmt_info->stmt);
619 gimple_stmt_iterator si = gsi_for_stmt (stmt_info->stmt);
620 gsi_remove (&si, true);
621 release_defs (stmt_info->stmt);
622 free_stmt_vec_info (stmt_info);
625 /* Replace the statement at GSI by NEW_STMT, both the vectorization
626 information and the function itself. STMT_INFO describes the statement
627 at GSI. */
629 void
630 vec_info::replace_stmt (gimple_stmt_iterator *gsi, stmt_vec_info stmt_info,
631 gimple *new_stmt)
633 gimple *old_stmt = stmt_info->stmt;
634 gcc_assert (!stmt_info->pattern_stmt_p && old_stmt == gsi_stmt (*gsi));
635 gimple_set_uid (new_stmt, gimple_uid (old_stmt));
636 stmt_info->stmt = new_stmt;
637 gsi_replace (gsi, new_stmt, true);
640 /* Insert stmts in SEQ on the VEC_INFO region entry. If CONTEXT is
641 not NULL it specifies whether to use the sub-region entry
642 determined by it, currently used for loop vectorization to insert
643 on the inner loop entry vs. the outer loop entry. */
645 void
646 vec_info::insert_seq_on_entry (stmt_vec_info context, gimple_seq seq)
648 if (loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (this))
650 class loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
651 basic_block new_bb;
652 edge pe;
654 if (context && nested_in_vect_loop_p (loop, context))
655 loop = loop->inner;
657 pe = loop_preheader_edge (loop);
658 new_bb = gsi_insert_seq_on_edge_immediate (pe, seq);
659 gcc_assert (!new_bb);
661 else
663 bb_vec_info bb_vinfo = as_a <bb_vec_info> (this);
664 gimple_stmt_iterator gsi_region_begin
665 = gsi_after_labels (bb_vinfo->bbs[0]);
666 gsi_insert_seq_before (&gsi_region_begin, seq, GSI_SAME_STMT);
670 /* Like insert_seq_on_entry but just inserts the single stmt NEW_STMT. */
672 void
673 vec_info::insert_on_entry (stmt_vec_info context, gimple *new_stmt)
675 gimple_seq seq = NULL;
676 gimple_stmt_iterator gsi = gsi_start (seq);
677 gsi_insert_before_without_update (&gsi, new_stmt, GSI_SAME_STMT);
678 insert_seq_on_entry (context, seq);
681 /* Create and initialize a new stmt_vec_info struct for STMT. */
683 stmt_vec_info
684 vec_info::new_stmt_vec_info (gimple *stmt)
686 stmt_vec_info res = XCNEW (class _stmt_vec_info);
687 res->stmt = stmt;
689 STMT_VINFO_TYPE (res) = undef_vec_info_type;
690 STMT_VINFO_RELEVANT (res) = vect_unused_in_scope;
691 STMT_VINFO_VECTORIZABLE (res) = true;
692 STMT_VINFO_REDUC_TYPE (res) = TREE_CODE_REDUCTION;
693 STMT_VINFO_REDUC_CODE (res) = ERROR_MARK;
694 STMT_VINFO_REDUC_FN (res) = IFN_LAST;
695 STMT_VINFO_REDUC_IDX (res) = -1;
696 STMT_VINFO_SLP_VECT_ONLY (res) = false;
697 STMT_VINFO_SLP_VECT_ONLY_PATTERN (res) = false;
698 STMT_VINFO_VEC_STMTS (res) = vNULL;
699 res->reduc_initial_values = vNULL;
700 res->reduc_scalar_results = vNULL;
702 if (is_a <loop_vec_info> (this)
703 && gimple_code (stmt) == GIMPLE_PHI
704 && is_loop_header_bb_p (gimple_bb (stmt)))
705 STMT_VINFO_DEF_TYPE (res) = vect_unknown_def_type;
706 else
707 STMT_VINFO_DEF_TYPE (res) = vect_internal_def;
709 STMT_SLP_TYPE (res) = loop_vect;
711 /* This is really "uninitialized" until vect_compute_data_ref_alignment. */
712 res->dr_aux.misalignment = DR_MISALIGNMENT_UNINITIALIZED;
714 return res;
717 /* Associate STMT with INFO. */
719 void
720 vec_info::set_vinfo_for_stmt (gimple *stmt, stmt_vec_info info, bool check_ro)
722 unsigned int uid = gimple_uid (stmt);
723 if (uid == 0)
725 gcc_assert (!check_ro || !stmt_vec_info_ro);
726 gcc_checking_assert (info);
727 uid = stmt_vec_infos.length () + 1;
728 gimple_set_uid (stmt, uid);
729 stmt_vec_infos.safe_push (info);
731 else
733 gcc_checking_assert (info == NULL);
734 stmt_vec_infos[uid - 1] = info;
738 /* Free the contents of stmt_vec_infos. */
740 void
741 vec_info::free_stmt_vec_infos (void)
743 for (stmt_vec_info &info : stmt_vec_infos)
744 if (info != NULL)
745 free_stmt_vec_info (info);
746 stmt_vec_infos.release ();
749 /* Free STMT_INFO. */
751 void
752 vec_info::free_stmt_vec_info (stmt_vec_info stmt_info)
754 if (stmt_info->pattern_stmt_p)
756 gimple_set_bb (stmt_info->stmt, NULL);
757 tree lhs = gimple_get_lhs (stmt_info->stmt);
758 if (lhs && TREE_CODE (lhs) == SSA_NAME)
759 release_ssa_name (lhs);
762 stmt_info->reduc_initial_values.release ();
763 stmt_info->reduc_scalar_results.release ();
764 STMT_VINFO_SIMD_CLONE_INFO (stmt_info).release ();
765 STMT_VINFO_VEC_STMTS (stmt_info).release ();
766 free (stmt_info);
769 /* Returns true if S1 dominates S2. */
771 bool
772 vect_stmt_dominates_stmt_p (gimple *s1, gimple *s2)
774 basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
776 /* If bb1 is NULL, it should be a GIMPLE_NOP def stmt of an (D)
777 SSA_NAME. Assume it lives at the beginning of function and
778 thus dominates everything. */
779 if (!bb1 || s1 == s2)
780 return true;
782 /* If bb2 is NULL, it doesn't dominate any stmt with a bb. */
783 if (!bb2)
784 return false;
786 if (bb1 != bb2)
787 return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
789 /* PHIs in the same basic block are assumed to be
790 executed all in parallel, if only one stmt is a PHI,
791 it dominates the other stmt in the same basic block. */
792 if (gimple_code (s1) == GIMPLE_PHI)
793 return true;
795 if (gimple_code (s2) == GIMPLE_PHI)
796 return false;
798 /* Inserted vectorized stmts all have UID 0 while the original stmts
799 in the IL have UID increasing within a BB. Walk from both sides
800 until we find the other stmt or a stmt with UID != 0. */
801 gimple_stmt_iterator gsi1 = gsi_for_stmt (s1);
802 while (gimple_uid (gsi_stmt (gsi1)) == 0)
804 gsi_next (&gsi1);
805 if (gsi_end_p (gsi1))
806 return false;
807 if (gsi_stmt (gsi1) == s2)
808 return true;
810 if (gimple_uid (gsi_stmt (gsi1)) == -1u)
811 return false;
813 gimple_stmt_iterator gsi2 = gsi_for_stmt (s2);
814 while (gimple_uid (gsi_stmt (gsi2)) == 0)
816 gsi_prev (&gsi2);
817 if (gsi_end_p (gsi2))
818 return false;
819 if (gsi_stmt (gsi2) == s1)
820 return true;
822 if (gimple_uid (gsi_stmt (gsi2)) == -1u)
823 return false;
825 if (gimple_uid (gsi_stmt (gsi1)) <= gimple_uid (gsi_stmt (gsi2)))
826 return true;
827 return false;
830 /* A helper function to free scev and LOOP niter information, as well as
831 clear loop constraint LOOP_C_FINITE. */
833 void
834 vect_free_loop_info_assumptions (class loop *loop)
836 scev_reset_htab ();
837 /* We need to explicitly reset upper bound information since they are
838 used even after free_numbers_of_iterations_estimates. */
839 loop->any_upper_bound = false;
840 loop->any_likely_upper_bound = false;
841 free_numbers_of_iterations_estimates (loop);
842 loop_constraint_clear (loop, LOOP_C_FINITE);
845 /* If LOOP has been versioned during ifcvt, return the internal call
846 guarding it. */
848 gimple *
849 vect_loop_vectorized_call (class loop *loop, gcond **cond)
851 basic_block bb = loop_preheader_edge (loop)->src;
852 gimple *g;
855 g = *gsi_last_bb (bb);
856 if ((g && gimple_code (g) == GIMPLE_COND)
857 || !single_succ_p (bb))
858 break;
859 if (!single_pred_p (bb))
860 break;
861 bb = single_pred (bb);
863 while (1);
864 if (g && gimple_code (g) == GIMPLE_COND)
866 if (cond)
867 *cond = as_a <gcond *> (g);
868 gimple_stmt_iterator gsi = gsi_for_stmt (g);
869 gsi_prev (&gsi);
870 if (!gsi_end_p (gsi))
872 g = gsi_stmt (gsi);
873 if (gimple_call_internal_p (g, IFN_LOOP_VECTORIZED)
874 && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->num
875 || tree_to_shwi (gimple_call_arg (g, 1)) == loop->num))
876 return g;
879 return NULL;
882 /* If LOOP has been versioned during loop distribution, return the gurading
883 internal call. */
885 static gimple *
886 vect_loop_dist_alias_call (class loop *loop, function *fun)
888 basic_block bb;
889 basic_block entry;
890 class loop *outer, *orig;
892 if (loop->orig_loop_num == 0)
893 return NULL;
895 orig = get_loop (fun, loop->orig_loop_num);
896 if (orig == NULL)
898 /* The original loop is somehow destroyed. Clear the information. */
899 loop->orig_loop_num = 0;
900 return NULL;
903 if (loop != orig)
904 bb = nearest_common_dominator (CDI_DOMINATORS, loop->header, orig->header);
905 else
906 bb = loop_preheader_edge (loop)->src;
908 outer = bb->loop_father;
909 entry = ENTRY_BLOCK_PTR_FOR_FN (fun);
911 /* Look upward in dominance tree. */
912 for (; bb != entry && flow_bb_inside_loop_p (outer, bb);
913 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
915 gimple_stmt_iterator gsi = gsi_last_bb (bb);
916 if (!safe_is_a <gcond *> (*gsi))
917 continue;
919 gsi_prev (&gsi);
920 if (gsi_end_p (gsi))
921 continue;
923 gimple *g = gsi_stmt (gsi);
924 /* The guarding internal function call must have the same distribution
925 alias id. */
926 if (gimple_call_internal_p (g, IFN_LOOP_DIST_ALIAS)
927 && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->orig_loop_num))
928 return g;
930 return NULL;
933 /* Set the uids of all the statements in basic blocks inside loop
934 represented by LOOP_VINFO. LOOP_VECTORIZED_CALL is the internal
935 call guarding the loop which has been if converted. */
936 static void
937 set_uid_loop_bbs (loop_vec_info loop_vinfo, gimple *loop_vectorized_call,
938 function *fun)
940 tree arg = gimple_call_arg (loop_vectorized_call, 1);
941 basic_block *bbs;
942 unsigned int i;
943 class loop *scalar_loop = get_loop (fun, tree_to_shwi (arg));
945 LOOP_VINFO_SCALAR_LOOP (loop_vinfo) = scalar_loop;
946 LOOP_VINFO_SCALAR_IV_EXIT (loop_vinfo)
947 = vec_init_loop_exit_info (scalar_loop);
948 gcc_checking_assert (vect_loop_vectorized_call (scalar_loop)
949 == loop_vectorized_call);
950 /* If we are going to vectorize outer loop, prevent vectorization
951 of the inner loop in the scalar loop - either the scalar loop is
952 thrown away, so it is a wasted work, or is used only for
953 a few iterations. */
954 if (scalar_loop->inner)
956 gimple *g = vect_loop_vectorized_call (scalar_loop->inner);
957 if (g)
959 arg = gimple_call_arg (g, 0);
960 get_loop (fun, tree_to_shwi (arg))->dont_vectorize = true;
961 fold_loop_internal_call (g, boolean_false_node);
964 bbs = get_loop_body (scalar_loop);
965 for (i = 0; i < scalar_loop->num_nodes; i++)
967 basic_block bb = bbs[i];
968 gimple_stmt_iterator gsi;
969 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
971 gimple *phi = gsi_stmt (gsi);
972 gimple_set_uid (phi, 0);
974 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
976 gimple *stmt = gsi_stmt (gsi);
977 gimple_set_uid (stmt, 0);
980 free (bbs);
983 /* Generate vectorized code for LOOP and its epilogues. */
985 static unsigned
986 vect_transform_loops (hash_table<simduid_to_vf> *&simduid_to_vf_htab,
987 loop_p loop, gimple *loop_vectorized_call,
988 function *fun)
990 loop_vec_info loop_vinfo = loop_vec_info_for_loop (loop);
992 if (loop_vectorized_call)
993 set_uid_loop_bbs (loop_vinfo, loop_vectorized_call, fun);
995 unsigned HOST_WIDE_INT bytes;
996 if (dump_enabled_p ())
998 if (GET_MODE_SIZE (loop_vinfo->vector_mode).is_constant (&bytes))
999 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location,
1000 "loop vectorized using %wu byte vectors\n", bytes);
1001 else
1002 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location,
1003 "loop vectorized using variable length vectors\n");
1006 loop_p new_loop = vect_transform_loop (loop_vinfo,
1007 loop_vectorized_call);
1008 /* Now that the loop has been vectorized, allow it to be unrolled
1009 etc. */
1010 loop->force_vectorize = false;
1012 if (loop->simduid)
1014 simduid_to_vf *simduid_to_vf_data = XNEW (simduid_to_vf);
1015 if (!simduid_to_vf_htab)
1016 simduid_to_vf_htab = new hash_table<simduid_to_vf> (15);
1017 simduid_to_vf_data->simduid = DECL_UID (loop->simduid);
1018 simduid_to_vf_data->vf = loop_vinfo->vectorization_factor;
1019 *simduid_to_vf_htab->find_slot (simduid_to_vf_data, INSERT)
1020 = simduid_to_vf_data;
1023 /* We should not have to update virtual SSA form here but some
1024 transforms involve creating new virtual definitions which makes
1025 updating difficult.
1026 We delay the actual update to the end of the pass but avoid
1027 confusing ourselves by forcing need_ssa_update_p () to false. */
1028 unsigned todo = 0;
1029 if (need_ssa_update_p (cfun))
1031 gcc_assert (loop_vinfo->any_known_not_updated_vssa);
1032 fun->gimple_df->ssa_renaming_needed = false;
1033 todo |= TODO_update_ssa_only_virtuals;
1035 gcc_assert (!need_ssa_update_p (cfun));
1037 /* Epilogue of vectorized loop must be vectorized too. */
1038 if (new_loop)
1039 todo |= vect_transform_loops (simduid_to_vf_htab, new_loop, NULL, fun);
1041 return todo;
1044 /* Try to vectorize LOOP. */
1046 static unsigned
1047 try_vectorize_loop_1 (hash_table<simduid_to_vf> *&simduid_to_vf_htab,
1048 unsigned *num_vectorized_loops, loop_p loop,
1049 gimple *loop_vectorized_call,
1050 gimple *loop_dist_alias_call,
1051 function *fun)
1053 unsigned ret = 0;
1054 vec_info_shared shared;
1055 auto_purge_vect_location sentinel;
1056 vect_location = find_loop_location (loop);
1058 if (LOCATION_LOCUS (vect_location.get_location_t ()) != UNKNOWN_LOCATION
1059 && dump_enabled_p ())
1060 dump_printf (MSG_NOTE | MSG_PRIORITY_INTERNALS,
1061 "\nAnalyzing loop at %s:%d\n",
1062 LOCATION_FILE (vect_location.get_location_t ()),
1063 LOCATION_LINE (vect_location.get_location_t ()));
1065 /* Try to analyze the loop, retaining an opt_problem if dump_enabled_p. */
1066 opt_loop_vec_info loop_vinfo = vect_analyze_loop (loop, &shared);
1067 loop->aux = loop_vinfo;
1069 if (!loop_vinfo)
1070 if (dump_enabled_p ())
1071 if (opt_problem *problem = loop_vinfo.get_problem ())
1073 dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
1074 "couldn't vectorize loop\n");
1075 problem->emit_and_clear ();
1078 if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo))
1080 /* Free existing information if loop is analyzed with some
1081 assumptions. */
1082 if (loop_constraint_set_p (loop, LOOP_C_FINITE))
1083 vect_free_loop_info_assumptions (loop);
1085 /* If we applied if-conversion then try to vectorize the
1086 BB of innermost loops.
1087 ??? Ideally BB vectorization would learn to vectorize
1088 control flow by applying if-conversion on-the-fly, the
1089 following retains the if-converted loop body even when
1090 only non-if-converted parts took part in BB vectorization. */
1091 if (flag_tree_slp_vectorize != 0
1092 && loop_vectorized_call
1093 && ! loop->inner)
1095 basic_block bb = loop->header;
1096 bool require_loop_vectorize = false;
1097 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
1098 !gsi_end_p (gsi); gsi_next (&gsi))
1100 gimple *stmt = gsi_stmt (gsi);
1101 gcall *call = dyn_cast <gcall *> (stmt);
1102 if (call && gimple_call_internal_p (call))
1104 internal_fn ifn = gimple_call_internal_fn (call);
1105 if (ifn == IFN_MASK_LOAD || ifn == IFN_MASK_STORE
1106 /* Don't keep the if-converted parts when the ifn with
1107 specifc type is not supported by the backend. */
1108 || (direct_internal_fn_p (ifn)
1109 && !direct_internal_fn_supported_p
1110 (call, OPTIMIZE_FOR_SPEED)))
1112 require_loop_vectorize = true;
1113 break;
1116 gimple_set_uid (stmt, -1);
1117 gimple_set_visited (stmt, false);
1119 if (!require_loop_vectorize)
1121 tree arg = gimple_call_arg (loop_vectorized_call, 1);
1122 class loop *scalar_loop = get_loop (fun, tree_to_shwi (arg));
1123 if (vect_slp_if_converted_bb (bb, scalar_loop))
1125 fold_loop_internal_call (loop_vectorized_call,
1126 boolean_true_node);
1127 loop_vectorized_call = NULL;
1128 ret |= TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
1132 /* If outer loop vectorization fails for LOOP_VECTORIZED guarded
1133 loop, don't vectorize its inner loop; we'll attempt to
1134 vectorize LOOP_VECTORIZED guarded inner loop of the scalar
1135 loop version. */
1136 if (loop_vectorized_call && loop->inner)
1137 loop->inner->dont_vectorize = true;
1138 return ret;
1141 if (!dbg_cnt (vect_loop))
1143 /* Free existing information if loop is analyzed with some
1144 assumptions. */
1145 if (loop_constraint_set_p (loop, LOOP_C_FINITE))
1146 vect_free_loop_info_assumptions (loop);
1147 return ret;
1150 (*num_vectorized_loops)++;
1151 /* Transform LOOP and its epilogues. */
1152 ret |= vect_transform_loops (simduid_to_vf_htab, loop,
1153 loop_vectorized_call, fun);
1155 if (loop_vectorized_call)
1157 fold_loop_internal_call (loop_vectorized_call, boolean_true_node);
1158 ret |= TODO_cleanup_cfg;
1160 if (loop_dist_alias_call)
1162 tree value = gimple_call_arg (loop_dist_alias_call, 1);
1163 fold_loop_internal_call (loop_dist_alias_call, value);
1164 ret |= TODO_cleanup_cfg;
1167 return ret;
1170 /* Try to vectorize LOOP. */
1172 static unsigned
1173 try_vectorize_loop (hash_table<simduid_to_vf> *&simduid_to_vf_htab,
1174 unsigned *num_vectorized_loops, loop_p loop,
1175 function *fun)
1177 if (!((flag_tree_loop_vectorize
1178 && optimize_loop_nest_for_speed_p (loop))
1179 || loop->force_vectorize))
1180 return 0;
1182 return try_vectorize_loop_1 (simduid_to_vf_htab, num_vectorized_loops, loop,
1183 vect_loop_vectorized_call (loop),
1184 vect_loop_dist_alias_call (loop, fun), fun);
1188 /* Loop autovectorization. */
1190 namespace {
1192 const pass_data pass_data_vectorize =
1194 GIMPLE_PASS, /* type */
1195 "vect", /* name */
1196 OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
1197 TV_TREE_VECTORIZATION, /* tv_id */
1198 ( PROP_cfg | PROP_ssa ), /* properties_required */
1199 0, /* properties_provided */
1200 0, /* properties_destroyed */
1201 0, /* todo_flags_start */
1202 0, /* todo_flags_finish */
1205 class pass_vectorize : public gimple_opt_pass
1207 public:
1208 pass_vectorize (gcc::context *ctxt)
1209 : gimple_opt_pass (pass_data_vectorize, ctxt)
1212 /* opt_pass methods: */
1213 bool gate (function *fun) final override
1215 return flag_tree_loop_vectorize || fun->has_force_vectorize_loops;
1218 unsigned int execute (function *) final override;
1220 }; // class pass_vectorize
1222 /* Function vectorize_loops.
1224 Entry point to loop vectorization phase. */
1226 unsigned
1227 pass_vectorize::execute (function *fun)
1229 unsigned int i;
1230 unsigned int num_vectorized_loops = 0;
1231 unsigned int vect_loops_num;
1232 hash_table<simduid_to_vf> *simduid_to_vf_htab = NULL;
1233 hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab = NULL;
1234 bool any_ifcvt_loops = false;
1235 unsigned ret = 0;
1237 vect_loops_num = number_of_loops (fun);
1239 /* Bail out if there are no loops. */
1240 if (vect_loops_num <= 1)
1241 return 0;
1243 vect_slp_init ();
1245 if (fun->has_simduid_loops)
1246 note_simd_array_uses (&simd_array_to_simduid_htab, fun);
1248 /* ----------- Analyze loops. ----------- */
1250 /* If some loop was duplicated, it gets bigger number
1251 than all previously defined loops. This fact allows us to run
1252 only over initial loops skipping newly generated ones. */
1253 for (auto loop : loops_list (fun, 0))
1254 if (loop->dont_vectorize)
1256 any_ifcvt_loops = true;
1257 /* If-conversion sometimes versions both the outer loop
1258 (for the case when outer loop vectorization might be
1259 desirable) as well as the inner loop in the scalar version
1260 of the loop. So we have:
1261 if (LOOP_VECTORIZED (1, 3))
1263 loop1
1264 loop2
1266 else
1267 loop3 (copy of loop1)
1268 if (LOOP_VECTORIZED (4, 5))
1269 loop4 (copy of loop2)
1270 else
1271 loop5 (copy of loop4)
1272 If loops' iteration gives us loop3 first (which has
1273 dont_vectorize set), make sure to process loop1 before loop4;
1274 so that we can prevent vectorization of loop4 if loop1
1275 is successfully vectorized. */
1276 if (loop->inner)
1278 gimple *loop_vectorized_call
1279 = vect_loop_vectorized_call (loop);
1280 if (loop_vectorized_call
1281 && vect_loop_vectorized_call (loop->inner))
1283 tree arg = gimple_call_arg (loop_vectorized_call, 0);
1284 class loop *vector_loop
1285 = get_loop (fun, tree_to_shwi (arg));
1286 if (vector_loop && vector_loop != loop)
1288 /* Make sure we don't vectorize it twice. */
1289 vector_loop->dont_vectorize = true;
1290 ret |= try_vectorize_loop (simduid_to_vf_htab,
1291 &num_vectorized_loops,
1292 vector_loop, fun);
1297 else
1298 ret |= try_vectorize_loop (simduid_to_vf_htab, &num_vectorized_loops,
1299 loop, fun);
1301 vect_location = dump_user_location_t ();
1303 statistics_counter_event (fun, "Vectorized loops", num_vectorized_loops);
1304 if (dump_enabled_p ()
1305 || (num_vectorized_loops > 0 && dump_enabled_p ()))
1306 dump_printf_loc (MSG_NOTE, vect_location,
1307 "vectorized %u loops in function.\n",
1308 num_vectorized_loops);
1310 /* ----------- Finalize. ----------- */
1312 if (any_ifcvt_loops)
1313 for (i = 1; i < number_of_loops (fun); i++)
1315 class loop *loop = get_loop (fun, i);
1316 if (loop && loop->dont_vectorize)
1318 gimple *g = vect_loop_vectorized_call (loop);
1319 if (g)
1321 fold_loop_internal_call (g, boolean_false_node);
1322 ret |= TODO_cleanup_cfg;
1323 g = NULL;
1325 else
1326 g = vect_loop_dist_alias_call (loop, fun);
1328 if (g)
1330 fold_loop_internal_call (g, boolean_false_node);
1331 ret |= TODO_cleanup_cfg;
1336 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */
1337 if (fun->has_simduid_loops)
1339 adjust_simduid_builtins (simduid_to_vf_htab, fun);
1340 /* Avoid stale SCEV cache entries for the SIMD_LANE defs. */
1341 scev_reset ();
1343 /* Shrink any "omp array simd" temporary arrays to the
1344 actual vectorization factors. */
1345 if (simd_array_to_simduid_htab)
1346 shrink_simd_arrays (simd_array_to_simduid_htab, simduid_to_vf_htab);
1347 delete simduid_to_vf_htab;
1348 fun->has_simduid_loops = false;
1350 if (num_vectorized_loops > 0)
1352 /* We are collecting some corner cases where we need to update
1353 virtual SSA form via the TODO but delete the queued update-SSA
1354 state. Force renaming if we think that might be necessary. */
1355 if (ret & TODO_update_ssa_only_virtuals)
1356 mark_virtual_operands_for_renaming (cfun);
1357 /* If we vectorized any loop only virtual SSA form needs to be updated.
1358 ??? Also while we try hard to update loop-closed SSA form we fail
1359 to properly do this in some corner-cases (see PR56286). */
1360 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_only_virtuals);
1361 ret |= TODO_cleanup_cfg;
1364 for (i = 1; i < number_of_loops (fun); i++)
1366 loop_vec_info loop_vinfo;
1367 bool has_mask_store;
1369 class loop *loop = get_loop (fun, i);
1370 if (!loop || !loop->aux)
1371 continue;
1372 loop_vinfo = (loop_vec_info) loop->aux;
1373 has_mask_store = LOOP_VINFO_HAS_MASK_STORE (loop_vinfo);
1374 delete loop_vinfo;
1375 if (has_mask_store
1376 && targetm.vectorize.empty_mask_is_expensive (IFN_MASK_STORE))
1377 optimize_mask_stores (loop);
1379 auto_bitmap exit_bbs;
1380 /* Perform local CSE, this esp. helps because we emit code for
1381 predicates that need to be shared for optimal predicate usage.
1382 However reassoc will re-order them and prevent CSE from working
1383 as it should. CSE only the loop body, not the entry. */
1384 auto_vec<edge> exits = get_loop_exit_edges (loop);
1385 for (edge exit : exits)
1386 bitmap_set_bit (exit_bbs, exit->dest->index);
1388 edge entry = EDGE_PRED (loop_preheader_edge (loop)->src, 0);
1389 do_rpo_vn (fun, entry, exit_bbs);
1391 loop->aux = NULL;
1394 vect_slp_fini ();
1396 return ret;
1399 } // anon namespace
1401 gimple_opt_pass *
1402 make_pass_vectorize (gcc::context *ctxt)
1404 return new pass_vectorize (ctxt);
1407 /* Entry point to the simduid cleanup pass. */
1409 namespace {
1411 const pass_data pass_data_simduid_cleanup =
1413 GIMPLE_PASS, /* type */
1414 "simduid", /* name */
1415 OPTGROUP_NONE, /* optinfo_flags */
1416 TV_NONE, /* tv_id */
1417 ( PROP_ssa | PROP_cfg ), /* properties_required */
1418 0, /* properties_provided */
1419 0, /* properties_destroyed */
1420 0, /* todo_flags_start */
1421 0, /* todo_flags_finish */
1424 class pass_simduid_cleanup : public gimple_opt_pass
1426 public:
1427 pass_simduid_cleanup (gcc::context *ctxt)
1428 : gimple_opt_pass (pass_data_simduid_cleanup, ctxt)
1431 /* opt_pass methods: */
1432 opt_pass * clone () final override
1434 return new pass_simduid_cleanup (m_ctxt);
1436 bool gate (function *fun) final override { return fun->has_simduid_loops; }
1437 unsigned int execute (function *) final override;
1439 }; // class pass_simduid_cleanup
1441 unsigned int
1442 pass_simduid_cleanup::execute (function *fun)
1444 hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab = NULL;
1446 note_simd_array_uses (&simd_array_to_simduid_htab, fun);
1448 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */
1449 adjust_simduid_builtins (NULL, fun);
1451 /* Shrink any "omp array simd" temporary arrays to the
1452 actual vectorization factors. */
1453 if (simd_array_to_simduid_htab)
1454 shrink_simd_arrays (simd_array_to_simduid_htab, NULL);
1455 fun->has_simduid_loops = false;
1456 return 0;
1459 } // anon namespace
1461 gimple_opt_pass *
1462 make_pass_simduid_cleanup (gcc::context *ctxt)
1464 return new pass_simduid_cleanup (ctxt);
1468 /* Entry point to basic block SLP phase. */
1470 namespace {
1472 const pass_data pass_data_slp_vectorize =
1474 GIMPLE_PASS, /* type */
1475 "slp", /* name */
1476 OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
1477 TV_TREE_SLP_VECTORIZATION, /* tv_id */
1478 ( PROP_ssa | PROP_cfg ), /* properties_required */
1479 0, /* properties_provided */
1480 0, /* properties_destroyed */
1481 0, /* todo_flags_start */
1482 TODO_update_ssa, /* todo_flags_finish */
1485 class pass_slp_vectorize : public gimple_opt_pass
1487 public:
1488 pass_slp_vectorize (gcc::context *ctxt)
1489 : gimple_opt_pass (pass_data_slp_vectorize, ctxt)
1492 /* opt_pass methods: */
1493 opt_pass * clone () final override { return new pass_slp_vectorize (m_ctxt); }
1494 bool gate (function *) final override { return flag_tree_slp_vectorize != 0; }
1495 unsigned int execute (function *) final override;
1497 }; // class pass_slp_vectorize
1499 unsigned int
1500 pass_slp_vectorize::execute (function *fun)
1502 auto_purge_vect_location sentinel;
1503 basic_block bb;
1505 bool in_loop_pipeline = scev_initialized_p ();
1506 if (!in_loop_pipeline)
1508 loop_optimizer_init (LOOPS_NORMAL);
1509 scev_initialize ();
1512 /* Mark all stmts as not belonging to the current region and unvisited. */
1513 FOR_EACH_BB_FN (bb, fun)
1515 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1516 gsi_next (&gsi))
1518 gphi *stmt = gsi.phi ();
1519 gimple_set_uid (stmt, -1);
1520 gimple_set_visited (stmt, false);
1522 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1523 gsi_next (&gsi))
1525 gimple *stmt = gsi_stmt (gsi);
1526 gimple_set_uid (stmt, -1);
1527 gimple_set_visited (stmt, false);
1531 vect_slp_init ();
1533 vect_slp_function (fun);
1535 vect_slp_fini ();
1537 if (!in_loop_pipeline)
1539 scev_finalize ();
1540 loop_optimizer_finalize ();
1543 return 0;
1546 } // anon namespace
1548 gimple_opt_pass *
1549 make_pass_slp_vectorize (gcc::context *ctxt)
1551 return new pass_slp_vectorize (ctxt);
1555 /* Increase alignment of global arrays to improve vectorization potential.
1556 TODO:
1557 - Consider also structs that have an array field.
1558 - Use ipa analysis to prune arrays that can't be vectorized?
1559 This should involve global alignment analysis and in the future also
1560 array padding. */
1562 static unsigned get_vec_alignment_for_type (tree);
1563 static hash_map<tree, unsigned> *type_align_map;
1565 /* Return alignment of array's vector type corresponding to scalar type.
1566 0 if no vector type exists. */
1567 static unsigned
1568 get_vec_alignment_for_array_type (tree type)
1570 gcc_assert (TREE_CODE (type) == ARRAY_TYPE);
1571 poly_uint64 array_size, vector_size;
1573 tree scalar_type = strip_array_types (type);
1574 tree vectype = get_related_vectype_for_scalar_type (VOIDmode, scalar_type);
1575 if (!vectype
1576 || !poly_int_tree_p (TYPE_SIZE (type), &array_size)
1577 || !poly_int_tree_p (TYPE_SIZE (vectype), &vector_size)
1578 || maybe_lt (array_size, vector_size))
1579 return 0;
1581 return TYPE_ALIGN (vectype);
1584 /* Return alignment of field having maximum alignment of vector type
1585 corresponding to it's scalar type. For now, we only consider fields whose
1586 offset is a multiple of it's vector alignment.
1587 0 if no suitable field is found. */
1588 static unsigned
1589 get_vec_alignment_for_record_type (tree type)
1591 gcc_assert (TREE_CODE (type) == RECORD_TYPE);
1593 unsigned max_align = 0, alignment;
1594 HOST_WIDE_INT offset;
1595 tree offset_tree;
1597 if (TYPE_PACKED (type))
1598 return 0;
1600 unsigned *slot = type_align_map->get (type);
1601 if (slot)
1602 return *slot;
1604 for (tree field = first_field (type);
1605 field != NULL_TREE;
1606 field = DECL_CHAIN (field))
1608 /* Skip if not FIELD_DECL or if alignment is set by user. */
1609 if (TREE_CODE (field) != FIELD_DECL
1610 || DECL_USER_ALIGN (field)
1611 || DECL_ARTIFICIAL (field))
1612 continue;
1614 /* We don't need to process the type further if offset is variable,
1615 since the offsets of remaining members will also be variable. */
1616 if (TREE_CODE (DECL_FIELD_OFFSET (field)) != INTEGER_CST
1617 || TREE_CODE (DECL_FIELD_BIT_OFFSET (field)) != INTEGER_CST)
1618 break;
1620 /* Similarly stop processing the type if offset_tree
1621 does not fit in unsigned HOST_WIDE_INT. */
1622 offset_tree = bit_position (field);
1623 if (!tree_fits_uhwi_p (offset_tree))
1624 break;
1626 offset = tree_to_uhwi (offset_tree);
1627 alignment = get_vec_alignment_for_type (TREE_TYPE (field));
1629 /* Get maximum alignment of vectorized field/array among those members
1630 whose offset is multiple of the vector alignment. */
1631 if (alignment
1632 && (offset % alignment == 0)
1633 && (alignment > max_align))
1634 max_align = alignment;
1637 type_align_map->put (type, max_align);
1638 return max_align;
1641 /* Return alignment of vector type corresponding to decl's scalar type
1642 or 0 if it doesn't exist or the vector alignment is lesser than
1643 decl's alignment. */
1644 static unsigned
1645 get_vec_alignment_for_type (tree type)
1647 if (type == NULL_TREE)
1648 return 0;
1650 gcc_assert (TYPE_P (type));
1652 static unsigned alignment = 0;
1653 switch (TREE_CODE (type))
1655 case ARRAY_TYPE:
1656 alignment = get_vec_alignment_for_array_type (type);
1657 break;
1658 case RECORD_TYPE:
1659 alignment = get_vec_alignment_for_record_type (type);
1660 break;
1661 default:
1662 alignment = 0;
1663 break;
1666 return (alignment > TYPE_ALIGN (type)) ? alignment : 0;
1669 /* Entry point to increase_alignment pass. */
1670 static unsigned int
1671 increase_alignment (void)
1673 varpool_node *vnode;
1675 vect_location = dump_user_location_t ();
1676 type_align_map = new hash_map<tree, unsigned>;
1678 /* Increase the alignment of all global arrays for vectorization. */
1679 FOR_EACH_DEFINED_VARIABLE (vnode)
1681 tree decl = vnode->decl;
1682 unsigned int alignment;
1684 if ((decl_in_symtab_p (decl)
1685 && !symtab_node::get (decl)->can_increase_alignment_p ())
1686 || DECL_USER_ALIGN (decl) || DECL_ARTIFICIAL (decl))
1687 continue;
1689 alignment = get_vec_alignment_for_type (TREE_TYPE (decl));
1690 if (alignment && vect_can_force_dr_alignment_p (decl, alignment))
1692 vnode->increase_alignment (alignment);
1693 if (dump_enabled_p ())
1694 dump_printf (MSG_NOTE, "Increasing alignment of decl: %T\n", decl);
1698 delete type_align_map;
1699 return 0;
1703 namespace {
1705 const pass_data pass_data_ipa_increase_alignment =
1707 SIMPLE_IPA_PASS, /* type */
1708 "increase_alignment", /* name */
1709 OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
1710 TV_IPA_OPT, /* tv_id */
1711 0, /* properties_required */
1712 0, /* properties_provided */
1713 0, /* properties_destroyed */
1714 0, /* todo_flags_start */
1715 0, /* todo_flags_finish */
1718 class pass_ipa_increase_alignment : public simple_ipa_opt_pass
1720 public:
1721 pass_ipa_increase_alignment (gcc::context *ctxt)
1722 : simple_ipa_opt_pass (pass_data_ipa_increase_alignment, ctxt)
1725 /* opt_pass methods: */
1726 bool gate (function *) final override
1728 return flag_section_anchors && flag_tree_loop_vectorize;
1731 unsigned int execute (function *) final override
1733 return increase_alignment ();
1736 }; // class pass_ipa_increase_alignment
1738 } // anon namespace
1740 simple_ipa_opt_pass *
1741 make_pass_ipa_increase_alignment (gcc::context *ctxt)
1743 return new pass_ipa_increase_alignment (ctxt);
1746 /* If the condition represented by T is a comparison or the SSA name
1747 result of a comparison, extract the comparison's operands. Represent
1748 T as NE_EXPR <T, 0> otherwise. */
1750 void
1751 scalar_cond_masked_key::get_cond_ops_from_tree (tree t)
1753 if (TREE_CODE_CLASS (TREE_CODE (t)) == tcc_comparison)
1755 this->code = TREE_CODE (t);
1756 this->op0 = TREE_OPERAND (t, 0);
1757 this->op1 = TREE_OPERAND (t, 1);
1758 this->inverted_p = false;
1759 return;
1762 if (TREE_CODE (t) == SSA_NAME)
1763 if (gassign *stmt = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (t)))
1765 tree_code code = gimple_assign_rhs_code (stmt);
1766 if (TREE_CODE_CLASS (code) == tcc_comparison)
1768 this->code = code;
1769 this->op0 = gimple_assign_rhs1 (stmt);
1770 this->op1 = gimple_assign_rhs2 (stmt);
1771 this->inverted_p = false;
1772 return;
1774 else if (code == BIT_NOT_EXPR)
1776 tree n_op = gimple_assign_rhs1 (stmt);
1777 if ((stmt = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (n_op))))
1779 code = gimple_assign_rhs_code (stmt);
1780 if (TREE_CODE_CLASS (code) == tcc_comparison)
1782 this->code = code;
1783 this->op0 = gimple_assign_rhs1 (stmt);
1784 this->op1 = gimple_assign_rhs2 (stmt);
1785 this->inverted_p = true;
1786 return;
1792 this->code = NE_EXPR;
1793 this->op0 = t;
1794 this->op1 = build_zero_cst (TREE_TYPE (t));
1795 this->inverted_p = false;
1798 /* See the comment above the declaration for details. */
1800 unsigned int
1801 vector_costs::add_stmt_cost (int count, vect_cost_for_stmt kind,
1802 stmt_vec_info stmt_info, slp_tree,
1803 tree vectype, int misalign,
1804 vect_cost_model_location where)
1806 unsigned int cost
1807 = builtin_vectorization_cost (kind, vectype, misalign) * count;
1808 return record_stmt_cost (stmt_info, where, cost);
1811 /* See the comment above the declaration for details. */
1813 void
1814 vector_costs::finish_cost (const vector_costs *)
1816 gcc_assert (!m_finished);
1817 m_finished = true;
1820 /* Record a base cost of COST units against WHERE. If STMT_INFO is
1821 nonnull, use it to adjust the cost based on execution frequency
1822 (where appropriate). */
1824 unsigned int
1825 vector_costs::record_stmt_cost (stmt_vec_info stmt_info,
1826 vect_cost_model_location where,
1827 unsigned int cost)
1829 cost = adjust_cost_for_freq (stmt_info, where, cost);
1830 m_costs[where] += cost;
1831 return cost;
1834 /* COST is the base cost we have calculated for an operation in location WHERE.
1835 If STMT_INFO is nonnull, use it to adjust the cost based on execution
1836 frequency (where appropriate). Return the adjusted cost. */
1838 unsigned int
1839 vector_costs::adjust_cost_for_freq (stmt_vec_info stmt_info,
1840 vect_cost_model_location where,
1841 unsigned int cost)
1843 /* Statements in an inner loop relative to the loop being
1844 vectorized are weighted more heavily. The value here is
1845 arbitrary and could potentially be improved with analysis. */
1846 if (where == vect_body
1847 && stmt_info
1848 && stmt_in_inner_loop_p (m_vinfo, stmt_info))
1850 loop_vec_info loop_vinfo = as_a<loop_vec_info> (m_vinfo);
1851 cost *= LOOP_VINFO_INNER_LOOP_COST_FACTOR (loop_vinfo);
1853 return cost;
1856 /* See the comment above the declaration for details. */
1858 bool
1859 vector_costs::better_main_loop_than_p (const vector_costs *other) const
1861 int diff = compare_inside_loop_cost (other);
1862 if (diff != 0)
1863 return diff < 0;
1865 /* If there's nothing to choose between the loop bodies, see whether
1866 there's a difference in the prologue and epilogue costs. */
1867 diff = compare_outside_loop_cost (other);
1868 if (diff != 0)
1869 return diff < 0;
1871 return false;
1875 /* See the comment above the declaration for details. */
1877 bool
1878 vector_costs::better_epilogue_loop_than_p (const vector_costs *other,
1879 loop_vec_info main_loop) const
1881 loop_vec_info this_loop_vinfo = as_a<loop_vec_info> (this->m_vinfo);
1882 loop_vec_info other_loop_vinfo = as_a<loop_vec_info> (other->m_vinfo);
1884 poly_int64 this_vf = LOOP_VINFO_VECT_FACTOR (this_loop_vinfo);
1885 poly_int64 other_vf = LOOP_VINFO_VECT_FACTOR (other_loop_vinfo);
1887 poly_uint64 main_poly_vf = LOOP_VINFO_VECT_FACTOR (main_loop);
1888 unsigned HOST_WIDE_INT main_vf;
1889 unsigned HOST_WIDE_INT other_factor, this_factor, other_cost, this_cost;
1890 /* If we can determine how many iterations are left for the epilogue
1891 loop, that is if both the main loop's vectorization factor and number
1892 of iterations are constant, then we use them to calculate the cost of
1893 the epilogue loop together with a 'likely value' for the epilogues
1894 vectorization factor. Otherwise we use the main loop's vectorization
1895 factor and the maximum poly value for the epilogue's. If the target
1896 has not provided with a sensible upper bound poly vectorization
1897 factors are likely to be favored over constant ones. */
1898 if (main_poly_vf.is_constant (&main_vf)
1899 && LOOP_VINFO_NITERS_KNOWN_P (main_loop))
1901 unsigned HOST_WIDE_INT niters
1902 = LOOP_VINFO_INT_NITERS (main_loop) % main_vf;
1903 HOST_WIDE_INT other_likely_vf
1904 = estimated_poly_value (other_vf, POLY_VALUE_LIKELY);
1905 HOST_WIDE_INT this_likely_vf
1906 = estimated_poly_value (this_vf, POLY_VALUE_LIKELY);
1908 /* If the epilogue is using partial vectors we account for the
1909 partial iteration here too. */
1910 other_factor = niters / other_likely_vf;
1911 if (LOOP_VINFO_USING_PARTIAL_VECTORS_P (other_loop_vinfo)
1912 && niters % other_likely_vf != 0)
1913 other_factor++;
1915 this_factor = niters / this_likely_vf;
1916 if (LOOP_VINFO_USING_PARTIAL_VECTORS_P (this_loop_vinfo)
1917 && niters % this_likely_vf != 0)
1918 this_factor++;
1920 else
1922 unsigned HOST_WIDE_INT main_vf_max
1923 = estimated_poly_value (main_poly_vf, POLY_VALUE_MAX);
1924 unsigned HOST_WIDE_INT other_vf_max
1925 = estimated_poly_value (other_vf, POLY_VALUE_MAX);
1926 unsigned HOST_WIDE_INT this_vf_max
1927 = estimated_poly_value (this_vf, POLY_VALUE_MAX);
1929 other_factor = CEIL (main_vf_max, other_vf_max);
1930 this_factor = CEIL (main_vf_max, this_vf_max);
1932 /* If the loop is not using partial vectors then it will iterate one
1933 time less than one that does. It is safe to subtract one here,
1934 because the main loop's vf is always at least 2x bigger than that
1935 of an epilogue. */
1936 if (!LOOP_VINFO_USING_PARTIAL_VECTORS_P (other_loop_vinfo))
1937 other_factor -= 1;
1938 if (!LOOP_VINFO_USING_PARTIAL_VECTORS_P (this_loop_vinfo))
1939 this_factor -= 1;
1942 /* Compute the costs by multiplying the inside costs with the factor and
1943 add the outside costs for a more complete picture. The factor is the
1944 amount of times we are expecting to iterate this epilogue. */
1945 other_cost = other->body_cost () * other_factor;
1946 this_cost = this->body_cost () * this_factor;
1947 other_cost += other->outside_cost ();
1948 this_cost += this->outside_cost ();
1949 return this_cost < other_cost;
1952 /* A <=>-style subroutine of better_main_loop_than_p. Check whether we can
1953 determine the return value of better_main_loop_than_p by comparing the
1954 inside (loop body) costs of THIS and OTHER. Return:
1956 * -1 if better_main_loop_than_p should return true.
1957 * 1 if better_main_loop_than_p should return false.
1958 * 0 if we can't decide. */
1961 vector_costs::compare_inside_loop_cost (const vector_costs *other) const
1963 loop_vec_info this_loop_vinfo = as_a<loop_vec_info> (this->m_vinfo);
1964 loop_vec_info other_loop_vinfo = as_a<loop_vec_info> (other->m_vinfo);
1966 struct loop *loop = LOOP_VINFO_LOOP (this_loop_vinfo);
1967 gcc_assert (LOOP_VINFO_LOOP (other_loop_vinfo) == loop);
1969 poly_int64 this_vf = LOOP_VINFO_VECT_FACTOR (this_loop_vinfo);
1970 poly_int64 other_vf = LOOP_VINFO_VECT_FACTOR (other_loop_vinfo);
1972 /* Limit the VFs to what is likely to be the maximum number of iterations,
1973 to handle cases in which at least one loop_vinfo is fully-masked. */
1974 HOST_WIDE_INT estimated_max_niter = likely_max_stmt_executions_int (loop);
1975 if (estimated_max_niter != -1)
1977 if (estimated_poly_value (this_vf, POLY_VALUE_MIN)
1978 >= estimated_max_niter)
1979 this_vf = estimated_max_niter;
1980 if (estimated_poly_value (other_vf, POLY_VALUE_MIN)
1981 >= estimated_max_niter)
1982 other_vf = estimated_max_niter;
1985 /* Check whether the (fractional) cost per scalar iteration is lower or
1986 higher: this_inside_cost / this_vf vs. other_inside_cost / other_vf. */
1987 poly_int64 rel_this = this_loop_vinfo->vector_costs->body_cost () * other_vf;
1988 poly_int64 rel_other
1989 = other_loop_vinfo->vector_costs->body_cost () * this_vf;
1991 HOST_WIDE_INT est_rel_this_min
1992 = estimated_poly_value (rel_this, POLY_VALUE_MIN);
1993 HOST_WIDE_INT est_rel_this_max
1994 = estimated_poly_value (rel_this, POLY_VALUE_MAX);
1996 HOST_WIDE_INT est_rel_other_min
1997 = estimated_poly_value (rel_other, POLY_VALUE_MIN);
1998 HOST_WIDE_INT est_rel_other_max
1999 = estimated_poly_value (rel_other, POLY_VALUE_MAX);
2001 /* Check first if we can make out an unambigous total order from the minimum
2002 and maximum estimates. */
2003 if (est_rel_this_min < est_rel_other_min
2004 && est_rel_this_max < est_rel_other_max)
2005 return -1;
2007 if (est_rel_other_min < est_rel_this_min
2008 && est_rel_other_max < est_rel_this_max)
2009 return 1;
2011 /* When other_loop_vinfo uses a variable vectorization factor,
2012 we know that it has a lower cost for at least one runtime VF.
2013 However, we don't know how likely that VF is.
2015 One option would be to compare the costs for the estimated VFs.
2016 The problem is that that can put too much pressure on the cost
2017 model. E.g. if the estimated VF is also the lowest possible VF,
2018 and if other_loop_vinfo is 1 unit worse than this_loop_vinfo
2019 for the estimated VF, we'd then choose this_loop_vinfo even
2020 though (a) this_loop_vinfo might not actually be better than
2021 other_loop_vinfo for that VF and (b) it would be significantly
2022 worse at larger VFs.
2024 Here we go for a hacky compromise: pick this_loop_vinfo if it is
2025 no more expensive than other_loop_vinfo even after doubling the
2026 estimated other_loop_vinfo VF. For all but trivial loops, this
2027 ensures that we only pick this_loop_vinfo if it is significantly
2028 better than other_loop_vinfo at the estimated VF. */
2029 if (est_rel_other_min != est_rel_this_min
2030 || est_rel_other_max != est_rel_this_max)
2032 HOST_WIDE_INT est_rel_this_likely
2033 = estimated_poly_value (rel_this, POLY_VALUE_LIKELY);
2034 HOST_WIDE_INT est_rel_other_likely
2035 = estimated_poly_value (rel_other, POLY_VALUE_LIKELY);
2037 return est_rel_this_likely * 2 <= est_rel_other_likely ? -1 : 1;
2040 return 0;
2043 /* A <=>-style subroutine of better_main_loop_than_p, used when there is
2044 nothing to choose between the inside (loop body) costs of THIS and OTHER.
2045 Check whether we can determine the return value of better_main_loop_than_p
2046 by comparing the outside (prologue and epilogue) costs of THIS and OTHER.
2047 Return:
2049 * -1 if better_main_loop_than_p should return true.
2050 * 1 if better_main_loop_than_p should return false.
2051 * 0 if we can't decide. */
2054 vector_costs::compare_outside_loop_cost (const vector_costs *other) const
2056 auto this_outside_cost = this->outside_cost ();
2057 auto other_outside_cost = other->outside_cost ();
2058 if (this_outside_cost != other_outside_cost)
2059 return this_outside_cost < other_outside_cost ? -1 : 1;
2061 return 0;