1/* Vectorizer
2 Copyright (C) 2003-2017 Free Software Foundation, Inc.
3 Contributed by Dorit Naishlos <dorit@il.ibm.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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.c - loop specific parts such as reductions, etc. These are
31 used by drivers (1) and (2).
32 - tree-vect-loop-manip.c - vectorizer's loop control-flow utilities, used by
33 drivers (1) and (2).
34 - tree-vect-slp.c - BB vectorization specific analysis and transformation,
35 used by drivers (2) and (3).
36 - tree-vect-stmts.c - statements analysis and transformation (used by all).
37 - tree-vect-data-refs.c - vectorizer specific data-refs analysis and
38 manipulations (used by all).
39 - tree-vect-patterns.c - vectorizable code patterns detector (used by all)
40
41 Here's a poor attempt at illustrating that:
42
43 tree-vectorizer.c:
44 loop_vect() loop_aware_slp() slp_vect()
45 | / \ /
46 | / \ /
47 tree-vect-loop.c tree-vect-slp.c
48 | \ \ / / |
49 | \ \/ / |
50 | \ /\ / |
51 | \ / \ / |
52 tree-vect-stmts.c tree-vect-data-refs.c
53 \ /
54 tree-vect-patterns.c
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
82
83/* Loop or bb location. */
84source_location vect_location;
85
86/* Vector mapping GIMPLE stmt to stmt_vec_info. */
87vec<stmt_vec_info> stmt_vec_info_vec;
88
89/* For mapping simduid to vectorization factor. */
90
91struct simduid_to_vf : free_ptr_hash<simduid_to_vf>
92{
93 unsigned int simduid;
94 int vf;
95
96 /* hash_table support. */
97 static inline hashval_t hash (const simduid_to_vf *);
98 static inline int equal (const simduid_to_vf *, const simduid_to_vf *);
99};
100
101inline hashval_t
102simduid_to_vf::hash (const simduid_to_vf *p)
103{
104 return p->simduid;
105}
106
107inline int
108simduid_to_vf::equal (const simduid_to_vf *p1, const simduid_to_vf *p2)
109{
110 return p1->simduid == p2->simduid;
111}
112
113/* This hash maps the OMP simd array to the corresponding simduid used
114 to index into it. Like thus,
115
116 _7 = GOMP_SIMD_LANE (simduid.0)
117 ...
118 ...
119 D.1737[_7] = stuff;
120
121
122 This hash maps from the OMP simd array (D.1737[]) to DECL_UID of
123 simduid.0. */
124
125struct simd_array_to_simduid : free_ptr_hash<simd_array_to_simduid>
126{
127 tree decl;
128 unsigned int simduid;
129
130 /* hash_table support. */
131 static inline hashval_t hash (const simd_array_to_simduid *);
132 static inline int equal (const simd_array_to_simduid *,
133 const simd_array_to_simduid *);
134};
135
136inline hashval_t
137simd_array_to_simduid::hash (const simd_array_to_simduid *p)
138{
139 return DECL_UID (p->decl);
140}
141
142inline int
143simd_array_to_simduid::equal (const simd_array_to_simduid *p1,
144 const simd_array_to_simduid *p2)
145{
146 return p1->decl == p2->decl;
147}
148
149/* Fold IFN_GOMP_SIMD_LANE, IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LAST_LANE,
150 into their corresponding constants and remove
151 IFN_GOMP_SIMD_ORDERED_{START,END}. */
152
153static void
154adjust_simduid_builtins (hash_table<simduid_to_vf> *htab)
155{
156 basic_block bb;
157
158 FOR_EACH_BB_FN (bb, cfun)
159 {
160 gimple_stmt_iterator i;
161
162 for (i = gsi_start_bb (bb); !gsi_end_p (i); )
163 {
164 unsigned int vf = 1;
165 enum internal_fn ifn;
166 gimple *stmt = gsi_stmt (i);
167 tree t;
168 if (!is_gimple_call (stmt)
169 || !gimple_call_internal_p (stmt))
170 {
171 gsi_next (&i);
172 continue;
173 }
174 ifn = gimple_call_internal_fn (stmt);
175 switch (ifn)
176 {
177 case IFN_GOMP_SIMD_LANE:
178 case IFN_GOMP_SIMD_VF:
179 case IFN_GOMP_SIMD_LAST_LANE:
180 break;
181 case IFN_GOMP_SIMD_ORDERED_START:
182 case IFN_GOMP_SIMD_ORDERED_END:
183 if (integer_onep (gimple_call_arg (stmt, 0)))
184 {
185 enum built_in_function bcode
186 = (ifn == IFN_GOMP_SIMD_ORDERED_START
187 ? BUILT_IN_GOMP_ORDERED_START
188 : BUILT_IN_GOMP_ORDERED_END);
189 gimple *g
190 = gimple_build_call (builtin_decl_explicit (bcode), 0);
191 tree vdef = gimple_vdef (stmt);
192 gimple_set_vdef (g, vdef);
193 SSA_NAME_DEF_STMT (vdef) = g;
194 gimple_set_vuse (g, gimple_vuse (stmt));
195 gsi_replace (&i, g, true);
196 continue;
197 }
198 gsi_remove (&i, true);
199 unlink_stmt_vdef (stmt);
200 continue;
201 default:
202 gsi_next (&i);
203 continue;
204 }
205 tree arg = gimple_call_arg (stmt, 0);
206 gcc_assert (arg != NULL_TREE);
207 gcc_assert (TREE_CODE (arg) == SSA_NAME);
208 simduid_to_vf *p = NULL, data;
209 data.simduid = DECL_UID (SSA_NAME_VAR (arg));
210 /* Need to nullify loop safelen field since it's value is not
211 valid after transformation. */
212 if (bb->loop_father && bb->loop_father->safelen > 0)
213 bb->loop_father->safelen = 0;
214 if (htab)
215 {
216 p = htab->find (&data);
217 if (p)
218 vf = p->vf;
219 }
220 switch (ifn)
221 {
222 case IFN_GOMP_SIMD_VF:
223 t = build_int_cst (unsigned_type_node, vf);
224 break;
225 case IFN_GOMP_SIMD_LANE:
226 t = build_int_cst (unsigned_type_node, 0);
227 break;
228 case IFN_GOMP_SIMD_LAST_LANE:
229 t = gimple_call_arg (stmt, 1);
230 break;
231 default:
232 gcc_unreachable ();
233 }
234 tree lhs = gimple_call_lhs (stmt);
235 if (lhs)
236 replace_uses_by (lhs, t);
237 release_defs (stmt);
238 gsi_remove (&i, true);
239 }
240 }
241}
242
243/* Helper structure for note_simd_array_uses. */
244
245struct note_simd_array_uses_struct
246{
247 hash_table<simd_array_to_simduid> **htab;
248 unsigned int simduid;
249};
250
251/* Callback for note_simd_array_uses, called through walk_gimple_op. */
252
253static tree
254note_simd_array_uses_cb (tree *tp, int *walk_subtrees, void *data)
255{
256 struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
257 struct note_simd_array_uses_struct *ns
258 = (struct note_simd_array_uses_struct *) wi->info;
259
260 if (TYPE_P (*tp))
261 *walk_subtrees = 0;
262 else if (VAR_P (*tp)
263 && lookup_attribute ("omp simd array", DECL_ATTRIBUTES (*tp))
264 && DECL_CONTEXT (*tp) == current_function_decl)
265 {
266 simd_array_to_simduid data;
267 if (!*ns->htab)
268 *ns->htab = new hash_table<simd_array_to_simduid> (15);
269 data.decl = *tp;
270 data.simduid = ns->simduid;
271 simd_array_to_simduid **slot = (*ns->htab)->find_slot (&data, INSERT);
272 if (*slot == NULL)
273 {
274 simd_array_to_simduid *p = XNEW (simd_array_to_simduid);
275 *p = data;
276 *slot = p;
277 }
278 else if ((*slot)->simduid != ns->simduid)
279 (*slot)->simduid = -1U;
280 *walk_subtrees = 0;
281 }
282 return NULL_TREE;
283}
284
285/* Find "omp simd array" temporaries and map them to corresponding
286 simduid. */
287
288static void
289note_simd_array_uses (hash_table<simd_array_to_simduid> **htab)
290{
291 basic_block bb;
292 gimple_stmt_iterator gsi;
293 struct walk_stmt_info wi;
294 struct note_simd_array_uses_struct ns;
295
296 memset (&wi, 0, sizeof (wi));
297 wi.info = &ns;
298 ns.htab = htab;
299
300 FOR_EACH_BB_FN (bb, cfun)
301 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
302 {
303 gimple *stmt = gsi_stmt (gsi);
304 if (!is_gimple_call (stmt) || !gimple_call_internal_p (stmt))
305 continue;
306 switch (gimple_call_internal_fn (stmt))
307 {
308 case IFN_GOMP_SIMD_LANE:
309 case IFN_GOMP_SIMD_VF:
310 case IFN_GOMP_SIMD_LAST_LANE:
311 break;
312 default:
313 continue;
314 }
315 tree lhs = gimple_call_lhs (stmt);
316 if (lhs == NULL_TREE)
317 continue;
318 imm_use_iterator use_iter;
319 gimple *use_stmt;
320 ns.simduid = DECL_UID (SSA_NAME_VAR (gimple_call_arg (stmt, 0)));
321 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, lhs)
322 if (!is_gimple_debug (use_stmt))
323 walk_gimple_op (use_stmt, note_simd_array_uses_cb, &wi);
324 }
325}
326
327/* Shrink arrays with "omp simd array" attribute to the corresponding
328 vectorization factor. */
329
330static void
331shrink_simd_arrays
332 (hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab,
333 hash_table<simduid_to_vf> *simduid_to_vf_htab)
334{
335 for (hash_table<simd_array_to_simduid>::iterator iter
336 = simd_array_to_simduid_htab->begin ();
337 iter != simd_array_to_simduid_htab->end (); ++iter)
338 if ((*iter)->simduid != -1U)
339 {
340 tree decl = (*iter)->decl;
341 int vf = 1;
342 if (simduid_to_vf_htab)
343 {
344 simduid_to_vf *p = NULL, data;
345 data.simduid = (*iter)->simduid;
346 p = simduid_to_vf_htab->find (&data);
347 if (p)
348 vf = p->vf;
349 }
350 tree atype
351 = build_array_type_nelts (TREE_TYPE (TREE_TYPE (decl)), vf);
352 TREE_TYPE (decl) = atype;
353 relayout_decl (decl);
354 }
355
356 delete simd_array_to_simduid_htab;
357}
358
359/* Initialize the vec_info with kind KIND_IN and target cost data
360 TARGET_COST_DATA_IN. */
361
362vec_info::vec_info (vec_info::vec_kind kind_in, void *target_cost_data_in)
363 : kind (kind_in),
364 datarefs (vNULL),
365 ddrs (vNULL),
366 target_cost_data (target_cost_data_in)
367{
368}
369
370vec_info::~vec_info ()
371{
372 slp_instance instance;
373 struct data_reference *dr;
374 unsigned int i;
375
376 FOR_EACH_VEC_ELT (datarefs, i, dr)
377 if (dr->aux)
378 {
379 free (dr->aux);
380 dr->aux = NULL;
381 }
382
383 FOR_EACH_VEC_ELT (slp_instances, i, instance)
384 vect_free_slp_instance (instance);
385
386 free_data_refs (datarefs);
387 free_dependence_relations (ddrs);
388 destroy_cost_data (target_cost_data);
389}
390
391/* A helper function to free scev and LOOP niter information, as well as
392 clear loop constraint LOOP_C_FINITE. */
393
394void
395vect_free_loop_info_assumptions (struct loop *loop)
396{
397 scev_reset_htab ();
398 /* We need to explicitly reset upper bound information since they are
399 used even after free_numbers_of_iterations_estimates. */
400 loop->any_upper_bound = false;
401 loop->any_likely_upper_bound = false;
402 free_numbers_of_iterations_estimates (loop);
403 loop_constraint_clear (loop, LOOP_C_FINITE);
404}
405
406/* Return whether STMT is inside the region we try to vectorize. */
407
408bool
409vect_stmt_in_region_p (vec_info *vinfo, gimple *stmt)
410{
411 if (!gimple_bb (stmt))
412 return false;
413
414 if (loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo))
415 {
416 struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
417 if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt)))
418 return false;
419 }
420 else
421 {
422 bb_vec_info bb_vinfo = as_a <bb_vec_info> (vinfo);
423 if (gimple_bb (stmt) != BB_VINFO_BB (bb_vinfo)
424 || gimple_uid (stmt) == -1U
425 || gimple_code (stmt) == GIMPLE_PHI)
426 return false;
427 }
428
429 return true;
430}
431
432
433/* If LOOP has been versioned during ifcvt, return the internal call
434 guarding it. */
435
436static gimple *
437vect_loop_vectorized_call (struct loop *loop)
438{
439 basic_block bb = loop_preheader_edge (loop)->src;
440 gimple *g;
441 do
442 {
443 g = last_stmt (bb);
444 if (g)
445 break;
446 if (!single_pred_p (bb))
447 break;
448 bb = single_pred (bb);
449 }
450 while (1);
451 if (g && gimple_code (g) == GIMPLE_COND)
452 {
453 gimple_stmt_iterator gsi = gsi_for_stmt (g);
454 gsi_prev (&gsi);
455 if (!gsi_end_p (gsi))
456 {
457 g = gsi_stmt (gsi);
458 if (gimple_call_internal_p (g, IFN_LOOP_VECTORIZED)
459 && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->num
460 || tree_to_shwi (gimple_call_arg (g, 1)) == loop->num))
461 return g;
462 }
463 }
464 return NULL;
465}
466
467/* If LOOP has been versioned during loop distribution, return the gurading
468 internal call. */
469
470static gimple *
471vect_loop_dist_alias_call (struct loop *loop)
472{
473 basic_block bb;
474 basic_block entry;
475 struct loop *outer, *orig;
476 gimple_stmt_iterator gsi;
477 gimple *g;
478
479 if (loop->orig_loop_num == 0)
480 return NULL;
481
482 orig = get_loop (cfun, loop->orig_loop_num);
483 if (orig == NULL)
484 {
485 /* The original loop is somehow destroyed. Clear the information. */
486 loop->orig_loop_num = 0;
487 return NULL;
488 }
489
490 if (loop != orig)
491 bb = nearest_common_dominator (CDI_DOMINATORS, loop->header, orig->header);
492 else
493 bb = loop_preheader_edge (loop)->src;
494
495 outer = bb->loop_father;
496 entry = ENTRY_BLOCK_PTR_FOR_FN (cfun);
497
498 /* Look upward in dominance tree. */
499 for (; bb != entry && flow_bb_inside_loop_p (outer, bb);
500 bb = get_immediate_dominator (CDI_DOMINATORS, bb))
501 {
502 g = last_stmt (bb);
503 if (g == NULL || gimple_code (g) != GIMPLE_COND)
504 continue;
505
506 gsi = gsi_for_stmt (g);
507 gsi_prev (&gsi);
508 if (gsi_end_p (gsi))
509 continue;
510
511 g = gsi_stmt (gsi);
512 /* The guarding internal function call must have the same distribution
513 alias id. */
514 if (gimple_call_internal_p (g, IFN_LOOP_DIST_ALIAS)
515 && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->orig_loop_num))
516 return g;
517 }
518 return NULL;
519}
520
521/* Set the uids of all the statements in basic blocks inside loop
522 represented by LOOP_VINFO. LOOP_VECTORIZED_CALL is the internal
523 call guarding the loop which has been if converted. */
524static void
525set_uid_loop_bbs (loop_vec_info loop_vinfo, gimple *loop_vectorized_call)
526{
527 tree arg = gimple_call_arg (loop_vectorized_call, 1);
528 basic_block *bbs;
529 unsigned int i;
530 struct loop *scalar_loop = get_loop (cfun, tree_to_shwi (arg));
531
532 LOOP_VINFO_SCALAR_LOOP (loop_vinfo) = scalar_loop;
533 gcc_checking_assert (vect_loop_vectorized_call (scalar_loop)
534 == loop_vectorized_call);
535 /* If we are going to vectorize outer loop, prevent vectorization
536 of the inner loop in the scalar loop - either the scalar loop is
537 thrown away, so it is a wasted work, or is used only for
538 a few iterations. */
539 if (scalar_loop->inner)
540 {
541 gimple *g = vect_loop_vectorized_call (scalar_loop->inner);
542 if (g)
543 {
544 arg = gimple_call_arg (g, 0);
545 get_loop (cfun, tree_to_shwi (arg))->dont_vectorize = true;
546 fold_loop_internal_call (g, boolean_false_node);
547 }
548 }
549 bbs = get_loop_body (scalar_loop);
550 for (i = 0; i < scalar_loop->num_nodes; i++)
551 {
552 basic_block bb = bbs[i];
553 gimple_stmt_iterator gsi;
554 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
555 {
556 gimple *phi = gsi_stmt (gsi);
557 gimple_set_uid (phi, 0);
558 }
559 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
560 {
561 gimple *stmt = gsi_stmt (gsi);
562 gimple_set_uid (stmt, 0);
563 }
564 }
565 free (bbs);
566}
567
568/* Function vectorize_loops.
569
570 Entry point to loop vectorization phase. */
571
572unsigned
573vectorize_loops (void)
574{
575 unsigned int i;
576 unsigned int num_vectorized_loops = 0;
577 unsigned int vect_loops_num;
578 struct loop *loop;
579 hash_table<simduid_to_vf> *simduid_to_vf_htab = NULL;
580 hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab = NULL;
581 bool any_ifcvt_loops = false;
582 unsigned ret = 0;
583 struct loop *new_loop;
584
585 vect_loops_num = number_of_loops (cfun);
586
587 /* Bail out if there are no loops. */
588 if (vect_loops_num <= 1)
589 return 0;
590
591 if (cfun->has_simduid_loops)
592 note_simd_array_uses (&simd_array_to_simduid_htab);
593
594 init_stmt_vec_info_vec ();
595
596 /* ----------- Analyze loops. ----------- */
597
598 /* If some loop was duplicated, it gets bigger number
599 than all previously defined loops. This fact allows us to run
600 only over initial loops skipping newly generated ones. */
601 FOR_EACH_LOOP (loop, 0)
602 if (loop->dont_vectorize)
603 {
604 any_ifcvt_loops = true;
605 /* If-conversion sometimes versions both the outer loop
606 (for the case when outer loop vectorization might be
607 desirable) as well as the inner loop in the scalar version
608 of the loop. So we have:
609 if (LOOP_VECTORIZED (1, 3))
610 {
611 loop1
612 loop2
613 }
614 else
615 loop3 (copy of loop1)
616 if (LOOP_VECTORIZED (4, 5))
617 loop4 (copy of loop2)
618 else
619 loop5 (copy of loop4)
620 If FOR_EACH_LOOP gives us loop3 first (which has
621 dont_vectorize set), make sure to process loop1 before loop4;
622 so that we can prevent vectorization of loop4 if loop1
623 is successfully vectorized. */
624 if (loop->inner)
625 {
626 gimple *loop_vectorized_call
627 = vect_loop_vectorized_call (loop);
628 if (loop_vectorized_call
629 && vect_loop_vectorized_call (loop->inner))
630 {
631 tree arg = gimple_call_arg (loop_vectorized_call, 0);
632 struct loop *vector_loop
633 = get_loop (cfun, tree_to_shwi (arg));
634 if (vector_loop && vector_loop != loop)
635 {
636 loop = vector_loop;
637 /* Make sure we don't vectorize it twice. */
638 loop->dont_vectorize = true;
639 goto try_vectorize;
640 }
641 }
642 }
643 }
644 else
645 {
646 loop_vec_info loop_vinfo, orig_loop_vinfo;
647 gimple *loop_vectorized_call, *loop_dist_alias_call;
648 try_vectorize:
649 if (!((flag_tree_loop_vectorize
650 && optimize_loop_nest_for_speed_p (loop))
651 || loop->force_vectorize))
652 continue;
653 orig_loop_vinfo = NULL;
654 loop_vectorized_call = vect_loop_vectorized_call (loop);
655 loop_dist_alias_call = vect_loop_dist_alias_call (loop);
656 vectorize_epilogue:
657 vect_location = find_loop_location (loop);
658 if (LOCATION_LOCUS (vect_location) != UNKNOWN_LOCATION
659 && dump_enabled_p ())
660 dump_printf (MSG_NOTE, "\nAnalyzing loop at %s:%d\n",
661 LOCATION_FILE (vect_location),
662 LOCATION_LINE (vect_location));
663
664 loop_vinfo = vect_analyze_loop (loop, orig_loop_vinfo);
665 loop->aux = loop_vinfo;
666
667 if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo))
668 {
669 /* Free existing information if loop is analyzed with some
670 assumptions. */
671 if (loop_constraint_set_p (loop, LOOP_C_FINITE))
672 vect_free_loop_info_assumptions (loop);
673
674 /* If we applied if-conversion then try to vectorize the
675 BB of innermost loops.
676 ??? Ideally BB vectorization would learn to vectorize
677 control flow by applying if-conversion on-the-fly, the
678 following retains the if-converted loop body even when
679 only non-if-converted parts took part in BB vectorization. */
680 if (flag_tree_slp_vectorize != 0
681 && loop_vectorized_call
682 && ! loop->inner)
683 {
684 basic_block bb = loop->header;
685 bool has_mask_load_store = false;
686 for (gimple_stmt_iterator gsi = gsi_start_bb (bb);
687 !gsi_end_p (gsi); gsi_next (&gsi))
688 {
689 gimple *stmt = gsi_stmt (gsi);
690 if (is_gimple_call (stmt)
691 && gimple_call_internal_p (stmt)
692 && (gimple_call_internal_fn (stmt) == IFN_MASK_LOAD
693 || gimple_call_internal_fn (stmt) == IFN_MASK_STORE))
694 {
695 has_mask_load_store = true;
696 break;
697 }
698 gimple_set_uid (stmt, -1);
699 gimple_set_visited (stmt, false);
700 }
701 if (! has_mask_load_store && vect_slp_bb (bb))
702 {
703 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location,
704 "basic block vectorized\n");
705 fold_loop_internal_call (loop_vectorized_call,
706 boolean_true_node);
707 loop_vectorized_call = NULL;
708 ret |= TODO_cleanup_cfg;
709 }
710 }
711 /* If outer loop vectorization fails for LOOP_VECTORIZED guarded
712 loop, don't vectorize its inner loop; we'll attempt to
713 vectorize LOOP_VECTORIZED guarded inner loop of the scalar
714 loop version. */
715 if (loop_vectorized_call && loop->inner)
716 loop->inner->dont_vectorize = true;
717 continue;
718 }
719
720 if (!dbg_cnt (vect_loop))
721 {
722 /* We may miss some if-converted loops due to
723 debug counter. Set any_ifcvt_loops to visit
724 them at finalization. */
725 any_ifcvt_loops = true;
726 /* Free existing information if loop is analyzed with some
727 assumptions. */
728 if (loop_constraint_set_p (loop, LOOP_C_FINITE))
729 vect_free_loop_info_assumptions (loop);
730
731 break;
732 }
733
734 if (loop_vectorized_call)
735 set_uid_loop_bbs (loop_vinfo, loop_vectorized_call);
736 if (LOCATION_LOCUS (vect_location) != UNKNOWN_LOCATION
737 && dump_enabled_p ())
738 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location,
739 "loop vectorized\n");
740 new_loop = vect_transform_loop (loop_vinfo);
741 num_vectorized_loops++;
742 /* Now that the loop has been vectorized, allow it to be unrolled
743 etc. */
744 loop->force_vectorize = false;
745
746 if (loop->simduid)
747 {
748 simduid_to_vf *simduid_to_vf_data = XNEW (simduid_to_vf);
749 if (!simduid_to_vf_htab)
750 simduid_to_vf_htab = new hash_table<simduid_to_vf> (15);
751 simduid_to_vf_data->simduid = DECL_UID (loop->simduid);
752 simduid_to_vf_data->vf = loop_vinfo->vectorization_factor;
753 *simduid_to_vf_htab->find_slot (simduid_to_vf_data, INSERT)
754 = simduid_to_vf_data;
755 }
756
757 if (loop_vectorized_call)
758 {
759 fold_loop_internal_call (loop_vectorized_call, boolean_true_node);
760 loop_vectorized_call = NULL;
761 ret |= TODO_cleanup_cfg;
762 }
763 if (loop_dist_alias_call)
764 {
765 tree value = gimple_call_arg (loop_dist_alias_call, 1);
766 fold_loop_internal_call (loop_dist_alias_call, value);
767 loop_dist_alias_call = NULL;
768 ret |= TODO_cleanup_cfg;
769 }
770
771 if (new_loop)
772 {
773 /* Epilogue of vectorized loop must be vectorized too. */
774 vect_loops_num = number_of_loops (cfun);
775 loop = new_loop;
776 orig_loop_vinfo = loop_vinfo; /* To pass vect_analyze_loop. */
777 goto vectorize_epilogue;
778 }
779 }
780
781 vect_location = UNKNOWN_LOCATION;
782
783 statistics_counter_event (cfun, "Vectorized loops", num_vectorized_loops);
784 if (dump_enabled_p ()
785 || (num_vectorized_loops > 0 && dump_enabled_p ()))
786 dump_printf_loc (MSG_NOTE, vect_location,
787 "vectorized %u loops in function.\n",
788 num_vectorized_loops);
789
790 /* ----------- Finalize. ----------- */
791
792 if (any_ifcvt_loops)
793 for (i = 1; i < vect_loops_num; i++)
794 {
795 loop = get_loop (cfun, i);
796 if (loop && loop->dont_vectorize)
797 {
798 gimple *g = vect_loop_vectorized_call (loop);
799 if (g)
800 {
801 fold_loop_internal_call (g, boolean_false_node);
802 ret |= TODO_cleanup_cfg;
803 g = NULL;
804 }
805 else
806 g = vect_loop_dist_alias_call (loop);
807
808 if (g)
809 {
810 fold_loop_internal_call (g, boolean_false_node);
811 ret |= TODO_cleanup_cfg;
812 }
813 }
814 }
815
816 for (i = 1; i < vect_loops_num; i++)
817 {
818 loop_vec_info loop_vinfo;
819 bool has_mask_store;
820
821 loop = get_loop (cfun, i);
822 if (!loop)
823 continue;
824 loop_vinfo = (loop_vec_info) loop->aux;
825 has_mask_store = false;
826 if (loop_vinfo)
827 has_mask_store = LOOP_VINFO_HAS_MASK_STORE (loop_vinfo);
828 delete loop_vinfo;
829 if (has_mask_store)
830 optimize_mask_stores (loop);
831 loop->aux = NULL;
832 }
833
834 free_stmt_vec_info_vec ();
835
836 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */
837 if (cfun->has_simduid_loops)
838 adjust_simduid_builtins (simduid_to_vf_htab);
839
840 /* Shrink any "omp array simd" temporary arrays to the
841 actual vectorization factors. */
842 if (simd_array_to_simduid_htab)
843 shrink_simd_arrays (simd_array_to_simduid_htab, simduid_to_vf_htab);
844 delete simduid_to_vf_htab;
845 cfun->has_simduid_loops = false;
846
847 if (num_vectorized_loops > 0)
848 {
849 /* If we vectorized any loop only virtual SSA form needs to be updated.
850 ??? Also while we try hard to update loop-closed SSA form we fail
851 to properly do this in some corner-cases (see PR56286). */
852 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_only_virtuals);
853 return TODO_cleanup_cfg;
854 }
855
856 return ret;
857}
858
859
860/* Entry point to the simduid cleanup pass. */
861
862namespace {
863
864const pass_data pass_data_simduid_cleanup =
865{
866 GIMPLE_PASS, /* type */
867 "simduid", /* name */
868 OPTGROUP_NONE, /* optinfo_flags */
869 TV_NONE, /* tv_id */
870 ( PROP_ssa | PROP_cfg ), /* properties_required */
871 0, /* properties_provided */
872 0, /* properties_destroyed */
873 0, /* todo_flags_start */
874 0, /* todo_flags_finish */
875};
876
877class pass_simduid_cleanup : public gimple_opt_pass
878{
879public:
880 pass_simduid_cleanup (gcc::context *ctxt)
881 : gimple_opt_pass (pass_data_simduid_cleanup, ctxt)
882 {}
883
884 /* opt_pass methods: */
885 opt_pass * clone () { return new pass_simduid_cleanup (m_ctxt); }
886 virtual bool gate (function *fun) { return fun->has_simduid_loops; }
887 virtual unsigned int execute (function *);
888
889}; // class pass_simduid_cleanup
890
891unsigned int
892pass_simduid_cleanup::execute (function *fun)
893{
894 hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab = NULL;
895
896 note_simd_array_uses (&simd_array_to_simduid_htab);
897
898 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */
899 adjust_simduid_builtins (NULL);
900
901 /* Shrink any "omp array simd" temporary arrays to the
902 actual vectorization factors. */
903 if (simd_array_to_simduid_htab)
904 shrink_simd_arrays (simd_array_to_simduid_htab, NULL);
905 fun->has_simduid_loops = false;
906 return 0;
907}
908
909} // anon namespace
910
911gimple_opt_pass *
912make_pass_simduid_cleanup (gcc::context *ctxt)
913{
914 return new pass_simduid_cleanup (ctxt);
915}
916
917
918/* Entry point to basic block SLP phase. */
919
920namespace {
921
922const pass_data pass_data_slp_vectorize =
923{
924 GIMPLE_PASS, /* type */
925 "slp", /* name */
926 OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
927 TV_TREE_SLP_VECTORIZATION, /* tv_id */
928 ( PROP_ssa | PROP_cfg ), /* properties_required */
929 0, /* properties_provided */
930 0, /* properties_destroyed */
931 0, /* todo_flags_start */
932 TODO_update_ssa, /* todo_flags_finish */
933};
934
935class pass_slp_vectorize : public gimple_opt_pass
936{
937public:
938 pass_slp_vectorize (gcc::context *ctxt)
939 : gimple_opt_pass (pass_data_slp_vectorize, ctxt)
940 {}
941
942 /* opt_pass methods: */
943 opt_pass * clone () { return new pass_slp_vectorize (m_ctxt); }
944 virtual bool gate (function *) { return flag_tree_slp_vectorize != 0; }
945 virtual unsigned int execute (function *);
946
947}; // class pass_slp_vectorize
948
949unsigned int
950pass_slp_vectorize::execute (function *fun)
951{
952 basic_block bb;
953
954 bool in_loop_pipeline = scev_initialized_p ();
955 if (!in_loop_pipeline)
956 {
957 loop_optimizer_init (LOOPS_NORMAL);
958 scev_initialize ();
959 }
960
961 /* Mark all stmts as not belonging to the current region and unvisited. */
962 FOR_EACH_BB_FN (bb, fun)
963 {
964 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
965 gsi_next (&gsi))
966 {
967 gimple *stmt = gsi_stmt (gsi);
968 gimple_set_uid (stmt, -1);
969 gimple_set_visited (stmt, false);
970 }
971 }
972
973 init_stmt_vec_info_vec ();
974
975 FOR_EACH_BB_FN (bb, fun)
976 {
977 if (vect_slp_bb (bb))
978 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location,
979 "basic block vectorized\n");
980 }
981
982 free_stmt_vec_info_vec ();
983
984 if (!in_loop_pipeline)
985 {
986 scev_finalize ();
987 loop_optimizer_finalize ();
988 }
989
990 return 0;
991}
992
993} // anon namespace
994
995gimple_opt_pass *
996make_pass_slp_vectorize (gcc::context *ctxt)
997{
998 return new pass_slp_vectorize (ctxt);
999}
1000
1001
1002/* Increase alignment of global arrays to improve vectorization potential.
1003 TODO:
1004 - Consider also structs that have an array field.
1005 - Use ipa analysis to prune arrays that can't be vectorized?
1006 This should involve global alignment analysis and in the future also
1007 array padding. */
1008
1009static unsigned get_vec_alignment_for_type (tree);
1010static hash_map<tree, unsigned> *type_align_map;
1011
1012/* Return alignment of array's vector type corresponding to scalar type.
1013 0 if no vector type exists. */
1014static unsigned
1015get_vec_alignment_for_array_type (tree type)
1016{
1017 gcc_assert (TREE_CODE (type) == ARRAY_TYPE);
1018
1019 tree vectype = get_vectype_for_scalar_type (strip_array_types (type));
1020 if (!vectype
1021 || !TYPE_SIZE (type)
1022 || TREE_CODE (TYPE_SIZE (type)) != INTEGER_CST
1023 || tree_int_cst_lt (TYPE_SIZE (type), TYPE_SIZE (vectype)))
1024 return 0;
1025
1026 return TYPE_ALIGN (vectype);
1027}
1028
1029/* Return alignment of field having maximum alignment of vector type
1030 corresponding to it's scalar type. For now, we only consider fields whose
1031 offset is a multiple of it's vector alignment.
1032 0 if no suitable field is found. */
1033static unsigned
1034get_vec_alignment_for_record_type (tree type)
1035{
1036 gcc_assert (TREE_CODE (type) == RECORD_TYPE);
1037
1038 unsigned max_align = 0, alignment;
1039 HOST_WIDE_INT offset;
1040 tree offset_tree;
1041
1042 if (TYPE_PACKED (type))
1043 return 0;
1044
1045 unsigned *slot = type_align_map->get (type);
1046 if (slot)
1047 return *slot;
1048
1049 for (tree field = first_field (type);
1050 field != NULL_TREE;
1051 field = DECL_CHAIN (field))
1052 {
1053 /* Skip if not FIELD_DECL or if alignment is set by user. */
1054 if (TREE_CODE (field) != FIELD_DECL
1055 || DECL_USER_ALIGN (field)
1056 || DECL_ARTIFICIAL (field))
1057 continue;
1058
1059 /* We don't need to process the type further if offset is variable,
1060 since the offsets of remaining members will also be variable. */
1061 if (TREE_CODE (DECL_FIELD_OFFSET (field)) != INTEGER_CST
1062 || TREE_CODE (DECL_FIELD_BIT_OFFSET (field)) != INTEGER_CST)
1063 break;
1064
1065 /* Similarly stop processing the type if offset_tree
1066 does not fit in unsigned HOST_WIDE_INT. */
1067 offset_tree = bit_position (field);
1068 if (!tree_fits_uhwi_p (offset_tree))
1069 break;
1070
1071 offset = tree_to_uhwi (offset_tree);
1072 alignment = get_vec_alignment_for_type (TREE_TYPE (field));
1073
1074 /* Get maximum alignment of vectorized field/array among those members
1075 whose offset is multiple of the vector alignment. */
1076 if (alignment
1077 && (offset % alignment == 0)
1078 && (alignment > max_align))
1079 max_align = alignment;
1080 }
1081
1082 type_align_map->put (type, max_align);
1083 return max_align;
1084}
1085
1086/* Return alignment of vector type corresponding to decl's scalar type
1087 or 0 if it doesn't exist or the vector alignment is lesser than
1088 decl's alignment. */
1089static unsigned
1090get_vec_alignment_for_type (tree type)
1091{
1092 if (type == NULL_TREE)
1093 return 0;
1094
1095 gcc_assert (TYPE_P (type));
1096
1097 static unsigned alignment = 0;
1098 switch (TREE_CODE (type))
1099 {
1100 case ARRAY_TYPE:
1101 alignment = get_vec_alignment_for_array_type (type);
1102 break;
1103 case RECORD_TYPE:
1104 alignment = get_vec_alignment_for_record_type (type);
1105 break;
1106 default:
1107 alignment = 0;
1108 break;
1109 }
1110
1111 return (alignment > TYPE_ALIGN (type)) ? alignment : 0;
1112}
1113
1114/* Entry point to increase_alignment pass. */
1115static unsigned int
1116increase_alignment (void)
1117{
1118 varpool_node *vnode;
1119
1120 vect_location = UNKNOWN_LOCATION;
1121 type_align_map = new hash_map<tree, unsigned>;
1122
1123 /* Increase the alignment of all global arrays for vectorization. */
1124 FOR_EACH_DEFINED_VARIABLE (vnode)
1125 {
1126 tree decl = vnode->decl;
1127 unsigned int alignment;
1128
1129 if ((decl_in_symtab_p (decl)
1130 && !symtab_node::get (decl)->can_increase_alignment_p ())
1131 || DECL_USER_ALIGN (decl) || DECL_ARTIFICIAL (decl))
1132 continue;
1133
1134 alignment = get_vec_alignment_for_type (TREE_TYPE (decl));
1135 if (alignment && vect_can_force_dr_alignment_p (decl, alignment))
1136 {
1137 vnode->increase_alignment (alignment);
1138 dump_printf (MSG_NOTE, "Increasing alignment of decl: ");
1139 dump_generic_expr (MSG_NOTE, TDF_SLIM, decl);
1140 dump_printf (MSG_NOTE, "\n");
1141 }
1142 }
1143
1144 delete type_align_map;
1145 return 0;
1146}
1147
1148
1149namespace {
1150
1151const pass_data pass_data_ipa_increase_alignment =
1152{
1153 SIMPLE_IPA_PASS, /* type */
1154 "increase_alignment", /* name */
1155 OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */
1156 TV_IPA_OPT, /* tv_id */
1157 0, /* properties_required */
1158 0, /* properties_provided */
1159 0, /* properties_destroyed */
1160 0, /* todo_flags_start */
1161 0, /* todo_flags_finish */
1162};
1163
1164class pass_ipa_increase_alignment : public simple_ipa_opt_pass
1165{
1166public:
1167 pass_ipa_increase_alignment (gcc::context *ctxt)
1168 : simple_ipa_opt_pass (pass_data_ipa_increase_alignment, ctxt)
1169 {}
1170
1171 /* opt_pass methods: */
1172 virtual bool gate (function *)
1173 {
1174 return flag_section_anchors && flag_tree_loop_vectorize;
1175 }
1176
1177 virtual unsigned int execute (function *) { return increase_alignment (); }
1178
1179}; // class pass_ipa_increase_alignment
1180
1181} // anon namespace
1182
1183simple_ipa_opt_pass *
1184make_pass_ipa_increase_alignment (gcc::context *ctxt)
1185{
1186 return new pass_ipa_increase_alignment (ctxt);
1187}
1188