2 Copyright (C) 2003-2013 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
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
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
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.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
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)
41 Here's a poor attempt at illustrating that:
44 loop_vect() loop_aware_slp() slp_vect()
47 tree-vect-loop.c tree-vect-slp.c
52 tree-vect-stmts.c tree-vect-data-refs.c
59 #include "coretypes.h"
64 #include "tree-pretty-print.h"
65 #include "tree-flow.h"
67 #include "tree-vectorizer.h"
68 #include "tree-pass.h"
69 #include "hash-table.h"
70 #include "tree-ssa-propagate.h"
72 /* Loop or bb location. */
75 /* Vector mapping GIMPLE stmt to stmt_vec_info. */
76 vec
<vec_void_p
> stmt_vec_info_vec
;
78 /* For mapping simduid to vectorization factor. */
80 struct simduid_to_vf
: typed_free_remove
<simduid_to_vf
>
85 /* hash_table support. */
86 typedef simduid_to_vf value_type
;
87 typedef simduid_to_vf compare_type
;
88 static inline hashval_t
hash (const value_type
*);
89 static inline int equal (const value_type
*, const compare_type
*);
93 simduid_to_vf::hash (const value_type
*p
)
99 simduid_to_vf::equal (const value_type
*p1
, const value_type
*p2
)
101 return p1
->simduid
== p2
->simduid
;
104 /* This hash maps the OMP simd array to the corresponding simduid used
105 to index into it. Like thus,
107 _7 = GOMP_SIMD_LANE (simduid.0)
113 This hash maps from the simduid.0 to OMP simd array (D.1737[]). */
115 struct simd_array_to_simduid
: typed_free_remove
<simd_array_to_simduid
>
118 unsigned int simduid
;
120 /* hash_table support. */
121 typedef simd_array_to_simduid value_type
;
122 typedef simd_array_to_simduid compare_type
;
123 static inline hashval_t
hash (const value_type
*);
124 static inline int equal (const value_type
*, const compare_type
*);
128 simd_array_to_simduid::hash (const value_type
*p
)
130 return DECL_UID (p
->decl
);
134 simd_array_to_simduid::equal (const value_type
*p1
, const value_type
*p2
)
136 return p1
->decl
== p2
->decl
;
139 /* Fold IFN_GOMP_SIMD_LANE, IFN_GOMP_SIMD_VF and IFN_GOMP_SIMD_LAST_LANE
140 into their corresponding constants. */
143 adjust_simduid_builtins (hash_table
<simduid_to_vf
> &htab
)
149 gimple_stmt_iterator i
;
151 for (i
= gsi_start_bb (bb
); !gsi_end_p (i
); gsi_next (&i
))
154 enum internal_fn ifn
;
155 gimple stmt
= gsi_stmt (i
);
157 if (!is_gimple_call (stmt
)
158 || !gimple_call_internal_p (stmt
))
160 ifn
= gimple_call_internal_fn (stmt
);
163 case IFN_GOMP_SIMD_LANE
:
164 case IFN_GOMP_SIMD_VF
:
165 case IFN_GOMP_SIMD_LAST_LANE
:
170 tree arg
= gimple_call_arg (stmt
, 0);
171 gcc_assert (arg
!= NULL_TREE
);
172 gcc_assert (TREE_CODE (arg
) == SSA_NAME
);
173 simduid_to_vf
*p
= NULL
, data
;
174 data
.simduid
= DECL_UID (SSA_NAME_VAR (arg
));
175 if (htab
.is_created ())
176 p
= htab
.find (&data
);
181 case IFN_GOMP_SIMD_VF
:
182 t
= build_int_cst (unsigned_type_node
, vf
);
184 case IFN_GOMP_SIMD_LANE
:
185 t
= build_int_cst (unsigned_type_node
, 0);
187 case IFN_GOMP_SIMD_LAST_LANE
:
188 t
= gimple_call_arg (stmt
, 1);
193 update_call_from_tree (&i
, t
);
198 /* Helper structure for note_simd_array_uses. */
200 struct note_simd_array_uses_struct
202 hash_table
<simd_array_to_simduid
> *htab
;
203 unsigned int simduid
;
206 /* Callback for note_simd_array_uses, called through walk_gimple_op. */
209 note_simd_array_uses_cb (tree
*tp
, int *walk_subtrees
, void *data
)
211 struct walk_stmt_info
*wi
= (struct walk_stmt_info
*) data
;
212 struct note_simd_array_uses_struct
*ns
213 = (struct note_simd_array_uses_struct
*) wi
->info
;
218 && lookup_attribute ("omp simd array", DECL_ATTRIBUTES (*tp
))
219 && DECL_CONTEXT (*tp
) == current_function_decl
)
221 simd_array_to_simduid data
;
222 if (!ns
->htab
->is_created ())
223 ns
->htab
->create (15);
225 data
.simduid
= ns
->simduid
;
226 simd_array_to_simduid
**slot
= ns
->htab
->find_slot (&data
, INSERT
);
229 simd_array_to_simduid
*p
= XNEW (simd_array_to_simduid
);
233 else if ((*slot
)->simduid
!= ns
->simduid
)
234 (*slot
)->simduid
= -1U;
240 /* Find "omp simd array" temporaries and map them to corresponding
244 note_simd_array_uses (hash_table
<simd_array_to_simduid
> *htab
)
247 gimple_stmt_iterator gsi
;
248 struct walk_stmt_info wi
;
249 struct note_simd_array_uses_struct ns
;
251 memset (&wi
, 0, sizeof (wi
));
256 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
258 gimple stmt
= gsi_stmt (gsi
);
259 if (!is_gimple_call (stmt
) || !gimple_call_internal_p (stmt
))
261 switch (gimple_call_internal_fn (stmt
))
263 case IFN_GOMP_SIMD_LANE
:
264 case IFN_GOMP_SIMD_VF
:
265 case IFN_GOMP_SIMD_LAST_LANE
:
270 tree lhs
= gimple_call_lhs (stmt
);
271 if (lhs
== NULL_TREE
)
273 imm_use_iterator use_iter
;
275 ns
.simduid
= DECL_UID (SSA_NAME_VAR (gimple_call_arg (stmt
, 0)));
276 FOR_EACH_IMM_USE_STMT (use_stmt
, use_iter
, lhs
)
277 if (!is_gimple_debug (use_stmt
))
278 walk_gimple_op (use_stmt
, note_simd_array_uses_cb
, &wi
);
282 /* Function vectorize_loops.
284 Entry point to loop vectorization phase. */
287 vectorize_loops (void)
290 unsigned int num_vectorized_loops
= 0;
291 unsigned int vect_loops_num
;
294 hash_table
<simduid_to_vf
> simduid_to_vf_htab
;
295 hash_table
<simd_array_to_simduid
> simd_array_to_simduid_htab
;
297 vect_loops_num
= number_of_loops (cfun
);
299 /* Bail out if there are no loops. */
300 if (vect_loops_num
<= 1)
302 if (cfun
->has_simduid_loops
)
303 adjust_simduid_builtins (simduid_to_vf_htab
);
307 if (cfun
->has_simduid_loops
)
308 note_simd_array_uses (&simd_array_to_simduid_htab
);
310 init_stmt_vec_info_vec ();
312 /* ----------- Analyze loops. ----------- */
314 /* If some loop was duplicated, it gets bigger number
315 than all previously defined loops. This fact allows us to run
316 only over initial loops skipping newly generated ones. */
317 FOR_EACH_LOOP (li
, loop
, 0)
318 if ((flag_tree_vectorize
&& optimize_loop_nest_for_speed_p (loop
))
321 loop_vec_info loop_vinfo
;
322 vect_location
= find_loop_location (loop
);
323 if (LOCATION_LOCUS (vect_location
) != UNKNOWN_LOC
324 && dump_enabled_p ())
325 dump_printf (MSG_NOTE
, "\nAnalyzing loop at %s:%d\n",
326 LOC_FILE (vect_location
), LOC_LINE (vect_location
));
328 loop_vinfo
= vect_analyze_loop (loop
);
329 loop
->aux
= loop_vinfo
;
331 if (!loop_vinfo
|| !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo
))
334 if (LOCATION_LOCUS (vect_location
) != UNKNOWN_LOC
335 && dump_enabled_p ())
336 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
337 "loop vectorized\n");
338 vect_transform_loop (loop_vinfo
);
339 num_vectorized_loops
++;
340 /* Now that the loop has been vectorized, allow it to be unrolled
342 loop
->force_vect
= false;
346 simduid_to_vf
*simduid_to_vf_data
= XNEW (simduid_to_vf
);
347 if (!simduid_to_vf_htab
.is_created ())
348 simduid_to_vf_htab
.create (15);
349 simduid_to_vf_data
->simduid
= DECL_UID (loop
->simduid
);
350 simduid_to_vf_data
->vf
= loop_vinfo
->vectorization_factor
;
351 *simduid_to_vf_htab
.find_slot (simduid_to_vf_data
, INSERT
)
352 = simduid_to_vf_data
;
356 vect_location
= UNKNOWN_LOC
;
358 statistics_counter_event (cfun
, "Vectorized loops", num_vectorized_loops
);
359 if (dump_enabled_p ()
360 || (num_vectorized_loops
> 0 && dump_enabled_p ()))
361 dump_printf_loc (MSG_NOTE
, vect_location
,
362 "vectorized %u loops in function.\n",
363 num_vectorized_loops
);
365 /* ----------- Finalize. ----------- */
367 for (i
= 1; i
< vect_loops_num
; i
++)
369 loop_vec_info loop_vinfo
;
371 loop
= get_loop (cfun
, i
);
374 loop_vinfo
= (loop_vec_info
) loop
->aux
;
375 destroy_loop_vec_info (loop_vinfo
, true);
379 free_stmt_vec_info_vec ();
381 /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE} builtins. */
382 if (cfun
->has_simduid_loops
)
383 adjust_simduid_builtins (simduid_to_vf_htab
);
385 /* Shrink any "omp array simd" temporary arrays to the
386 actual vectorization factors. */
387 if (simd_array_to_simduid_htab
.is_created ())
389 for (hash_table
<simd_array_to_simduid
>::iterator iter
390 = simd_array_to_simduid_htab
.begin ();
391 iter
!= simd_array_to_simduid_htab
.end (); ++iter
)
392 if ((*iter
).simduid
!= -1U)
394 tree decl
= (*iter
).decl
;
396 if (simduid_to_vf_htab
.is_created ())
398 simduid_to_vf
*p
= NULL
, data
;
399 data
.simduid
= (*iter
).simduid
;
400 p
= simduid_to_vf_htab
.find (&data
);
405 = build_array_type_nelts (TREE_TYPE (TREE_TYPE (decl
)), vf
);
406 TREE_TYPE (decl
) = atype
;
407 relayout_decl (decl
);
410 simd_array_to_simduid_htab
.dispose ();
412 if (simduid_to_vf_htab
.is_created ())
413 simduid_to_vf_htab
.dispose ();
415 if (num_vectorized_loops
> 0)
417 /* If we vectorized any loop only virtual SSA form needs to be updated.
418 ??? Also while we try hard to update loop-closed SSA form we fail
419 to properly do this in some corner-cases (see PR56286). */
420 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa_only_virtuals
);
421 return TODO_cleanup_cfg
;
428 /* Entry point to basic block SLP phase. */
431 execute_vect_slp (void)
435 init_stmt_vec_info_vec ();
439 vect_location
= find_bb_location (bb
);
441 if (vect_slp_analyze_bb (bb
))
443 vect_slp_transform_bb (bb
);
444 if (dump_enabled_p ())
445 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
, vect_location
,
446 "basic block vectorized\n");
450 free_stmt_vec_info_vec ();
457 /* Apply SLP either if the vectorizer is on and the user didn't specify
458 whether to run SLP or not, or if the SLP flag was set by the user. */
459 return ((flag_tree_vectorize
!= 0 && flag_tree_slp_vectorize
!= 0)
460 || flag_tree_slp_vectorize
== 1);
465 const pass_data pass_data_slp_vectorize
=
467 GIMPLE_PASS
, /* type */
469 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
471 true, /* has_execute */
472 TV_TREE_SLP_VECTORIZATION
, /* tv_id */
473 ( PROP_ssa
| PROP_cfg
), /* properties_required */
474 0, /* properties_provided */
475 0, /* properties_destroyed */
476 0, /* todo_flags_start */
477 ( TODO_verify_ssa
| TODO_update_ssa
478 | TODO_verify_stmts
), /* todo_flags_finish */
481 class pass_slp_vectorize
: public gimple_opt_pass
484 pass_slp_vectorize(gcc::context
*ctxt
)
485 : gimple_opt_pass(pass_data_slp_vectorize
, ctxt
)
488 /* opt_pass methods: */
489 bool gate () { return gate_vect_slp (); }
490 unsigned int execute () { return execute_vect_slp (); }
492 }; // class pass_slp_vectorize
497 make_pass_slp_vectorize (gcc::context
*ctxt
)
499 return new pass_slp_vectorize (ctxt
);
503 /* Increase alignment of global arrays to improve vectorization potential.
505 - Consider also structs that have an array field.
506 - Use ipa analysis to prune arrays that can't be vectorized?
507 This should involve global alignment analysis and in the future also
511 increase_alignment (void)
513 struct varpool_node
*vnode
;
515 vect_location
= UNKNOWN_LOC
;
517 /* Increase the alignment of all global arrays for vectorization. */
518 FOR_EACH_DEFINED_VARIABLE (vnode
)
520 tree vectype
, decl
= vnode
->symbol
.decl
;
522 unsigned int alignment
;
525 if (TREE_CODE (t
) != ARRAY_TYPE
)
527 vectype
= get_vectype_for_scalar_type (strip_array_types (t
));
530 alignment
= TYPE_ALIGN (vectype
);
531 if (DECL_ALIGN (decl
) >= alignment
)
534 if (vect_can_force_dr_alignment_p (decl
, alignment
))
536 DECL_ALIGN (decl
) = TYPE_ALIGN (vectype
);
537 DECL_USER_ALIGN (decl
) = 1;
538 dump_printf (MSG_NOTE
, "Increasing alignment of decl: ");
539 dump_generic_expr (MSG_NOTE
, TDF_SLIM
, decl
);
540 dump_printf (MSG_NOTE
, "\n");
548 gate_increase_alignment (void)
550 return flag_section_anchors
&& flag_tree_vectorize
;
556 const pass_data pass_data_ipa_increase_alignment
=
558 SIMPLE_IPA_PASS
, /* type */
559 "increase_alignment", /* name */
560 OPTGROUP_LOOP
| OPTGROUP_VEC
, /* optinfo_flags */
562 true, /* has_execute */
563 TV_IPA_OPT
, /* tv_id */
564 0, /* properties_required */
565 0, /* properties_provided */
566 0, /* properties_destroyed */
567 0, /* todo_flags_start */
568 0, /* todo_flags_finish */
571 class pass_ipa_increase_alignment
: public simple_ipa_opt_pass
574 pass_ipa_increase_alignment(gcc::context
*ctxt
)
575 : simple_ipa_opt_pass(pass_data_ipa_increase_alignment
, ctxt
)
578 /* opt_pass methods: */
579 bool gate () { return gate_increase_alignment (); }
580 unsigned int execute () { return increase_alignment (); }
582 }; // class pass_ipa_increase_alignment
586 simple_ipa_opt_pass
*
587 make_pass_ipa_increase_alignment (gcc::context
*ctxt
)
589 return new pass_ipa_increase_alignment (ctxt
);