]>
Commit | Line | Data |
---|---|---|
ebfd146a | 1 | /* Vectorizer |
5624e564 | 2 | Copyright (C) 2003-2015 Free Software Foundation, Inc. |
b8698a0f | 3 | Contributed by Dorit Naishlos <dorit@il.ibm.com> |
79fe1b3b DN |
4 | |
5 | This file is part of GCC. | |
6 | ||
7 | GCC is free software; you can redistribute it and/or modify it under | |
8 | the terms of the GNU General Public License as published by the Free | |
9dcd6f09 | 9 | Software Foundation; either version 3, or (at your option) any later |
79fe1b3b DN |
10 | version. |
11 | ||
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | for more details. | |
16 | ||
17 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
79fe1b3b | 20 | |
ebfd146a | 21 | /* Loop and basic block vectorizer. |
7ccf35ed | 22 | |
b8698a0f L |
23 | This file contains drivers for the three vectorizers: |
24 | (1) loop vectorizer (inter-iteration parallelism), | |
ebfd146a IR |
25 | (2) loop-aware SLP (intra-iteration parallelism) (invoked by the loop |
26 | vectorizer) | |
27 | (3) BB vectorizer (out-of-loops), aka SLP | |
b8698a0f | 28 | |
ebfd146a | 29 | The rest of the vectorizer's code is organized as follows: |
b8698a0f L |
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, | |
ebfd146a IR |
35 | used by drivers (2) and (3). |
36 | - tree-vect-stmts.c - statements analysis and transformation (used by all). | |
b8698a0f | 37 | - tree-vect-data-refs.c - vectorizer specific data-refs analysis and |
ebfd146a IR |
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 | */ | |
89d67cca | 56 | |
ebfd146a IR |
57 | #include "config.h" |
58 | #include "system.h" | |
59 | #include "coretypes.h" | |
c7131fb2 | 60 | #include "backend.h" |
ebfd146a | 61 | #include "tree.h" |
c7131fb2 | 62 | #include "gimple.h" |
957060b5 AM |
63 | #include "predict.h" |
64 | #include "tree-pass.h" | |
c7131fb2 | 65 | #include "ssa.h" |
957060b5 | 66 | #include "cgraph.h" |
40e23961 | 67 | #include "fold-const.h" |
d8a2d370 | 68 | #include "stor-layout.h" |
5be5c238 AM |
69 | #include "gimple-iterator.h" |
70 | #include "gimple-walk.h" | |
e28030cf | 71 | #include "tree-ssa-loop-manip.h" |
5ce9450f | 72 | #include "tree-cfg.h" |
ebfd146a | 73 | #include "cfgloop.h" |
ebfd146a | 74 | #include "tree-vectorizer.h" |
74bf76ed | 75 | #include "tree-ssa-propagate.h" |
c716e67f | 76 | #include "dbgcnt.h" |
e5d8bd8c RB |
77 | #include "tree-scalar-evolution.h" |
78 | ||
89d67cca | 79 | |
a70d6342 | 80 | /* Loop or bb location. */ |
b05e0233 | 81 | source_location vect_location; |
ad2dd72a | 82 | |
ebfd146a | 83 | /* Vector mapping GIMPLE stmt to stmt_vec_info. */ |
3161455c | 84 | vec<stmt_vec_info> stmt_vec_info_vec; |
74bf76ed JJ |
85 | \f |
86 | /* For mapping simduid to vectorization factor. */ | |
87 | ||
95fbe13e | 88 | struct simduid_to_vf : free_ptr_hash<simduid_to_vf> |
74bf76ed JJ |
89 | { |
90 | unsigned int simduid; | |
91 | int vf; | |
92 | ||
93 | /* hash_table support. */ | |
67f58944 TS |
94 | static inline hashval_t hash (const simduid_to_vf *); |
95 | static inline int equal (const simduid_to_vf *, const simduid_to_vf *); | |
74bf76ed JJ |
96 | }; |
97 | ||
98 | inline hashval_t | |
67f58944 | 99 | simduid_to_vf::hash (const simduid_to_vf *p) |
74bf76ed JJ |
100 | { |
101 | return p->simduid; | |
102 | } | |
103 | ||
104 | inline int | |
67f58944 | 105 | simduid_to_vf::equal (const simduid_to_vf *p1, const simduid_to_vf *p2) |
74bf76ed JJ |
106 | { |
107 | return p1->simduid == p2->simduid; | |
108 | } | |
109 | ||
110 | /* This hash maps the OMP simd array to the corresponding simduid used | |
111 | to index into it. Like thus, | |
112 | ||
113 | _7 = GOMP_SIMD_LANE (simduid.0) | |
114 | ... | |
115 | ... | |
116 | D.1737[_7] = stuff; | |
117 | ||
118 | ||
acf0174b JJ |
119 | This hash maps from the OMP simd array (D.1737[]) to DECL_UID of |
120 | simduid.0. */ | |
74bf76ed | 121 | |
95fbe13e | 122 | struct simd_array_to_simduid : free_ptr_hash<simd_array_to_simduid> |
74bf76ed JJ |
123 | { |
124 | tree decl; | |
125 | unsigned int simduid; | |
126 | ||
127 | /* hash_table support. */ | |
67f58944 TS |
128 | static inline hashval_t hash (const simd_array_to_simduid *); |
129 | static inline int equal (const simd_array_to_simduid *, | |
130 | const simd_array_to_simduid *); | |
74bf76ed JJ |
131 | }; |
132 | ||
133 | inline hashval_t | |
67f58944 | 134 | simd_array_to_simduid::hash (const simd_array_to_simduid *p) |
74bf76ed JJ |
135 | { |
136 | return DECL_UID (p->decl); | |
137 | } | |
138 | ||
139 | inline int | |
67f58944 TS |
140 | simd_array_to_simduid::equal (const simd_array_to_simduid *p1, |
141 | const simd_array_to_simduid *p2) | |
74bf76ed JJ |
142 | { |
143 | return p1->decl == p2->decl; | |
144 | } | |
145 | ||
d9a6bd32 JJ |
146 | /* Fold IFN_GOMP_SIMD_LANE, IFN_GOMP_SIMD_VF, IFN_GOMP_SIMD_LAST_LANE, |
147 | into their corresponding constants and remove | |
148 | IFN_GOMP_SIMD_ORDERED_{START,END}. */ | |
74bf76ed JJ |
149 | |
150 | static void | |
8c8b9f32 | 151 | adjust_simduid_builtins (hash_table<simduid_to_vf> *htab) |
74bf76ed JJ |
152 | { |
153 | basic_block bb; | |
154 | ||
11cd3bed | 155 | FOR_EACH_BB_FN (bb, cfun) |
74bf76ed JJ |
156 | { |
157 | gimple_stmt_iterator i; | |
158 | ||
d9a6bd32 | 159 | for (i = gsi_start_bb (bb); !gsi_end_p (i); ) |
74bf76ed JJ |
160 | { |
161 | unsigned int vf = 1; | |
162 | enum internal_fn ifn; | |
355fe088 | 163 | gimple *stmt = gsi_stmt (i); |
74bf76ed JJ |
164 | tree t; |
165 | if (!is_gimple_call (stmt) | |
166 | || !gimple_call_internal_p (stmt)) | |
d9a6bd32 JJ |
167 | { |
168 | gsi_next (&i); | |
169 | continue; | |
170 | } | |
74bf76ed JJ |
171 | ifn = gimple_call_internal_fn (stmt); |
172 | switch (ifn) | |
173 | { | |
174 | case IFN_GOMP_SIMD_LANE: | |
175 | case IFN_GOMP_SIMD_VF: | |
176 | case IFN_GOMP_SIMD_LAST_LANE: | |
177 | break; | |
d9a6bd32 JJ |
178 | case IFN_GOMP_SIMD_ORDERED_START: |
179 | case IFN_GOMP_SIMD_ORDERED_END: | |
e4606348 JJ |
180 | if (integer_onep (gimple_call_arg (stmt, 0))) |
181 | { | |
182 | enum built_in_function bcode | |
183 | = (ifn == IFN_GOMP_SIMD_ORDERED_START | |
184 | ? BUILT_IN_GOMP_ORDERED_START | |
185 | : BUILT_IN_GOMP_ORDERED_END); | |
186 | gimple *g | |
187 | = gimple_build_call (builtin_decl_explicit (bcode), 0); | |
188 | tree vdef = gimple_vdef (stmt); | |
189 | gimple_set_vdef (g, vdef); | |
190 | SSA_NAME_DEF_STMT (vdef) = g; | |
191 | gimple_set_vuse (g, gimple_vuse (stmt)); | |
192 | gsi_replace (&i, g, true); | |
193 | continue; | |
194 | } | |
d9a6bd32 JJ |
195 | gsi_remove (&i, true); |
196 | unlink_stmt_vdef (stmt); | |
197 | continue; | |
74bf76ed | 198 | default: |
d9a6bd32 | 199 | gsi_next (&i); |
74bf76ed JJ |
200 | continue; |
201 | } | |
202 | tree arg = gimple_call_arg (stmt, 0); | |
203 | gcc_assert (arg != NULL_TREE); | |
204 | gcc_assert (TREE_CODE (arg) == SSA_NAME); | |
205 | simduid_to_vf *p = NULL, data; | |
206 | data.simduid = DECL_UID (SSA_NAME_VAR (arg)); | |
8c8b9f32 JJ |
207 | if (htab) |
208 | { | |
209 | p = htab->find (&data); | |
210 | if (p) | |
211 | vf = p->vf; | |
212 | } | |
74bf76ed JJ |
213 | switch (ifn) |
214 | { | |
215 | case IFN_GOMP_SIMD_VF: | |
216 | t = build_int_cst (unsigned_type_node, vf); | |
217 | break; | |
218 | case IFN_GOMP_SIMD_LANE: | |
219 | t = build_int_cst (unsigned_type_node, 0); | |
220 | break; | |
221 | case IFN_GOMP_SIMD_LAST_LANE: | |
222 | t = gimple_call_arg (stmt, 1); | |
223 | break; | |
224 | default: | |
225 | gcc_unreachable (); | |
226 | } | |
227 | update_call_from_tree (&i, t); | |
d9a6bd32 | 228 | gsi_next (&i); |
74bf76ed JJ |
229 | } |
230 | } | |
231 | } | |
89d67cca | 232 | |
74bf76ed JJ |
233 | /* Helper structure for note_simd_array_uses. */ |
234 | ||
235 | struct note_simd_array_uses_struct | |
236 | { | |
c203e8a7 | 237 | hash_table<simd_array_to_simduid> **htab; |
74bf76ed JJ |
238 | unsigned int simduid; |
239 | }; | |
240 | ||
241 | /* Callback for note_simd_array_uses, called through walk_gimple_op. */ | |
242 | ||
243 | static tree | |
244 | note_simd_array_uses_cb (tree *tp, int *walk_subtrees, void *data) | |
245 | { | |
246 | struct walk_stmt_info *wi = (struct walk_stmt_info *) data; | |
247 | struct note_simd_array_uses_struct *ns | |
248 | = (struct note_simd_array_uses_struct *) wi->info; | |
249 | ||
250 | if (TYPE_P (*tp)) | |
251 | *walk_subtrees = 0; | |
252 | else if (VAR_P (*tp) | |
253 | && lookup_attribute ("omp simd array", DECL_ATTRIBUTES (*tp)) | |
254 | && DECL_CONTEXT (*tp) == current_function_decl) | |
255 | { | |
256 | simd_array_to_simduid data; | |
c203e8a7 TS |
257 | if (!*ns->htab) |
258 | *ns->htab = new hash_table<simd_array_to_simduid> (15); | |
74bf76ed JJ |
259 | data.decl = *tp; |
260 | data.simduid = ns->simduid; | |
c203e8a7 | 261 | simd_array_to_simduid **slot = (*ns->htab)->find_slot (&data, INSERT); |
74bf76ed JJ |
262 | if (*slot == NULL) |
263 | { | |
264 | simd_array_to_simduid *p = XNEW (simd_array_to_simduid); | |
265 | *p = data; | |
266 | *slot = p; | |
267 | } | |
268 | else if ((*slot)->simduid != ns->simduid) | |
269 | (*slot)->simduid = -1U; | |
270 | *walk_subtrees = 0; | |
271 | } | |
272 | return NULL_TREE; | |
273 | } | |
274 | ||
275 | /* Find "omp simd array" temporaries and map them to corresponding | |
276 | simduid. */ | |
277 | ||
278 | static void | |
c203e8a7 | 279 | note_simd_array_uses (hash_table<simd_array_to_simduid> **htab) |
74bf76ed JJ |
280 | { |
281 | basic_block bb; | |
282 | gimple_stmt_iterator gsi; | |
283 | struct walk_stmt_info wi; | |
284 | struct note_simd_array_uses_struct ns; | |
285 | ||
286 | memset (&wi, 0, sizeof (wi)); | |
287 | wi.info = &ns; | |
288 | ns.htab = htab; | |
289 | ||
11cd3bed | 290 | FOR_EACH_BB_FN (bb, cfun) |
74bf76ed JJ |
291 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) |
292 | { | |
355fe088 | 293 | gimple *stmt = gsi_stmt (gsi); |
74bf76ed JJ |
294 | if (!is_gimple_call (stmt) || !gimple_call_internal_p (stmt)) |
295 | continue; | |
296 | switch (gimple_call_internal_fn (stmt)) | |
297 | { | |
298 | case IFN_GOMP_SIMD_LANE: | |
299 | case IFN_GOMP_SIMD_VF: | |
300 | case IFN_GOMP_SIMD_LAST_LANE: | |
301 | break; | |
302 | default: | |
303 | continue; | |
304 | } | |
305 | tree lhs = gimple_call_lhs (stmt); | |
306 | if (lhs == NULL_TREE) | |
307 | continue; | |
308 | imm_use_iterator use_iter; | |
355fe088 | 309 | gimple *use_stmt; |
74bf76ed JJ |
310 | ns.simduid = DECL_UID (SSA_NAME_VAR (gimple_call_arg (stmt, 0))); |
311 | FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, lhs) | |
312 | if (!is_gimple_debug (use_stmt)) | |
313 | walk_gimple_op (use_stmt, note_simd_array_uses_cb, &wi); | |
314 | } | |
315 | } | |
8c8b9f32 JJ |
316 | |
317 | /* Shrink arrays with "omp simd array" attribute to the corresponding | |
318 | vectorization factor. */ | |
319 | ||
320 | static void | |
321 | shrink_simd_arrays | |
322 | (hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab, | |
323 | hash_table<simduid_to_vf> *simduid_to_vf_htab) | |
324 | { | |
325 | for (hash_table<simd_array_to_simduid>::iterator iter | |
326 | = simd_array_to_simduid_htab->begin (); | |
327 | iter != simd_array_to_simduid_htab->end (); ++iter) | |
328 | if ((*iter)->simduid != -1U) | |
329 | { | |
330 | tree decl = (*iter)->decl; | |
331 | int vf = 1; | |
332 | if (simduid_to_vf_htab) | |
333 | { | |
334 | simduid_to_vf *p = NULL, data; | |
335 | data.simduid = (*iter)->simduid; | |
336 | p = simduid_to_vf_htab->find (&data); | |
337 | if (p) | |
338 | vf = p->vf; | |
339 | } | |
340 | tree atype | |
341 | = build_array_type_nelts (TREE_TYPE (TREE_TYPE (decl)), vf); | |
342 | TREE_TYPE (decl) = atype; | |
343 | relayout_decl (decl); | |
344 | } | |
345 | ||
346 | delete simd_array_to_simduid_htab; | |
347 | } | |
ebfd146a | 348 | \f |
c716e67f XDL |
349 | /* A helper function to free data refs. */ |
350 | ||
351 | void | |
310213d4 | 352 | vect_destroy_datarefs (vec_info *vinfo) |
c716e67f | 353 | { |
c716e67f XDL |
354 | struct data_reference *dr; |
355 | unsigned int i; | |
356 | ||
310213d4 | 357 | FOR_EACH_VEC_ELT (vinfo->datarefs, i, dr) |
c716e67f XDL |
358 | if (dr->aux) |
359 | { | |
360 | free (dr->aux); | |
361 | dr->aux = NULL; | |
362 | } | |
363 | ||
310213d4 | 364 | free_data_refs (vinfo->datarefs); |
c716e67f XDL |
365 | } |
366 | ||
367 | ||
61d371eb RB |
368 | /* Return whether STMT is inside the region we try to vectorize. */ |
369 | ||
370 | bool | |
371 | vect_stmt_in_region_p (vec_info *vinfo, gimple *stmt) | |
372 | { | |
373 | if (!gimple_bb (stmt)) | |
374 | return false; | |
375 | ||
376 | if (loop_vec_info loop_vinfo = dyn_cast <loop_vec_info> (vinfo)) | |
377 | { | |
378 | struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo); | |
379 | if (!flow_bb_inside_loop_p (loop, gimple_bb (stmt))) | |
380 | return false; | |
381 | } | |
382 | else | |
383 | { | |
384 | bb_vec_info bb_vinfo = as_a <bb_vec_info> (vinfo); | |
385 | if (gimple_bb (stmt) != BB_VINFO_BB (bb_vinfo) | |
386 | || gimple_uid (stmt) == -1U | |
387 | || gimple_code (stmt) == GIMPLE_PHI) | |
388 | return false; | |
389 | } | |
390 | ||
391 | return true; | |
392 | } | |
393 | ||
394 | ||
5ce9450f JJ |
395 | /* If LOOP has been versioned during ifcvt, return the internal call |
396 | guarding it. */ | |
397 | ||
355fe088 | 398 | static gimple * |
5ce9450f JJ |
399 | vect_loop_vectorized_call (struct loop *loop) |
400 | { | |
401 | basic_block bb = loop_preheader_edge (loop)->src; | |
355fe088 | 402 | gimple *g; |
5ce9450f JJ |
403 | do |
404 | { | |
405 | g = last_stmt (bb); | |
406 | if (g) | |
407 | break; | |
408 | if (!single_pred_p (bb)) | |
409 | break; | |
410 | bb = single_pred (bb); | |
411 | } | |
412 | while (1); | |
413 | if (g && gimple_code (g) == GIMPLE_COND) | |
414 | { | |
415 | gimple_stmt_iterator gsi = gsi_for_stmt (g); | |
416 | gsi_prev (&gsi); | |
417 | if (!gsi_end_p (gsi)) | |
418 | { | |
419 | g = gsi_stmt (gsi); | |
420 | if (is_gimple_call (g) | |
421 | && gimple_call_internal_p (g) | |
422 | && gimple_call_internal_fn (g) == IFN_LOOP_VECTORIZED | |
423 | && (tree_to_shwi (gimple_call_arg (g, 0)) == loop->num | |
424 | || tree_to_shwi (gimple_call_arg (g, 1)) == loop->num)) | |
425 | return g; | |
426 | } | |
427 | } | |
428 | return NULL; | |
429 | } | |
430 | ||
431 | /* Fold LOOP_VECTORIZED internal call G to VALUE and | |
432 | update any immediate uses of it's LHS. */ | |
433 | ||
434 | static void | |
355fe088 | 435 | fold_loop_vectorized_call (gimple *g, tree value) |
5ce9450f JJ |
436 | { |
437 | tree lhs = gimple_call_lhs (g); | |
438 | use_operand_p use_p; | |
439 | imm_use_iterator iter; | |
355fe088 | 440 | gimple *use_stmt; |
5ce9450f JJ |
441 | gimple_stmt_iterator gsi = gsi_for_stmt (g); |
442 | ||
443 | update_call_from_tree (&gsi, value); | |
444 | FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs) | |
14407011 JJ |
445 | { |
446 | FOR_EACH_IMM_USE_ON_STMT (use_p, iter) | |
447 | SET_USE (use_p, value); | |
448 | update_stmt (use_stmt); | |
449 | } | |
5ce9450f | 450 | } |
2fc3c9a5 AK |
451 | /* Set the uids of all the statements in basic blocks inside loop |
452 | represented by LOOP_VINFO. LOOP_VECTORIZED_CALL is the internal | |
453 | call guarding the loop which has been if converted. */ | |
454 | static void | |
355fe088 | 455 | set_uid_loop_bbs (loop_vec_info loop_vinfo, gimple *loop_vectorized_call) |
2fc3c9a5 AK |
456 | { |
457 | tree arg = gimple_call_arg (loop_vectorized_call, 1); | |
458 | basic_block *bbs; | |
459 | unsigned int i; | |
460 | struct loop *scalar_loop = get_loop (cfun, tree_to_shwi (arg)); | |
461 | ||
462 | LOOP_VINFO_SCALAR_LOOP (loop_vinfo) = scalar_loop; | |
463 | gcc_checking_assert (vect_loop_vectorized_call | |
464 | (LOOP_VINFO_SCALAR_LOOP (loop_vinfo)) | |
465 | == loop_vectorized_call); | |
466 | bbs = get_loop_body (scalar_loop); | |
467 | for (i = 0; i < scalar_loop->num_nodes; i++) | |
468 | { | |
469 | basic_block bb = bbs[i]; | |
470 | gimple_stmt_iterator gsi; | |
471 | for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
472 | { | |
355fe088 | 473 | gimple *phi = gsi_stmt (gsi); |
2fc3c9a5 AK |
474 | gimple_set_uid (phi, 0); |
475 | } | |
476 | for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
477 | { | |
355fe088 | 478 | gimple *stmt = gsi_stmt (gsi); |
2fc3c9a5 AK |
479 | gimple_set_uid (stmt, 0); |
480 | } | |
481 | } | |
482 | free (bbs); | |
483 | } | |
5ce9450f | 484 | |
79fe1b3b | 485 | /* Function vectorize_loops. |
b8698a0f | 486 | |
8644a673 | 487 | Entry point to loop vectorization phase. */ |
79fe1b3b | 488 | |
4d2280f6 | 489 | unsigned |
d73be268 | 490 | vectorize_loops (void) |
79fe1b3b | 491 | { |
b52485c6 | 492 | unsigned int i; |
79fe1b3b | 493 | unsigned int num_vectorized_loops = 0; |
42fd6772 | 494 | unsigned int vect_loops_num; |
42fd6772 | 495 | struct loop *loop; |
c203e8a7 TS |
496 | hash_table<simduid_to_vf> *simduid_to_vf_htab = NULL; |
497 | hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab = NULL; | |
5ce9450f JJ |
498 | bool any_ifcvt_loops = false; |
499 | unsigned ret = 0; | |
79fe1b3b | 500 | |
0fc822d0 | 501 | vect_loops_num = number_of_loops (cfun); |
f9be04cd RG |
502 | |
503 | /* Bail out if there are no loops. */ | |
504 | if (vect_loops_num <= 1) | |
8c8b9f32 | 505 | return 0; |
74bf76ed JJ |
506 | |
507 | if (cfun->has_simduid_loops) | |
508 | note_simd_array_uses (&simd_array_to_simduid_htab); | |
f9be04cd | 509 | |
726a989a RB |
510 | init_stmt_vec_info_vec (); |
511 | ||
79fe1b3b DN |
512 | /* ----------- Analyze loops. ----------- */ |
513 | ||
b8698a0f | 514 | /* If some loop was duplicated, it gets bigger number |
ff802fa1 | 515 | than all previously defined loops. This fact allows us to run |
79fe1b3b | 516 | only over initial loops skipping newly generated ones. */ |
f0bd40b1 | 517 | FOR_EACH_LOOP (loop, 0) |
5ce9450f JJ |
518 | if (loop->dont_vectorize) |
519 | any_ifcvt_loops = true; | |
520 | else if ((flag_tree_loop_vectorize | |
521 | && optimize_loop_nest_for_speed_p (loop)) | |
b15b5979 | 522 | || loop->force_vectorize) |
8bcf15f6 JH |
523 | { |
524 | loop_vec_info loop_vinfo; | |
8644a673 | 525 | vect_location = find_loop_location (loop); |
b05e0233 | 526 | if (LOCATION_LOCUS (vect_location) != UNKNOWN_LOCATION |
73fbfcad | 527 | && dump_enabled_p ()) |
ccb3ad87 | 528 | dump_printf (MSG_NOTE, "\nAnalyzing loop at %s:%d\n", |
b05e0233 RB |
529 | LOCATION_FILE (vect_location), |
530 | LOCATION_LINE (vect_location)); | |
7cd3603b | 531 | |
8bcf15f6 JH |
532 | loop_vinfo = vect_analyze_loop (loop); |
533 | loop->aux = loop_vinfo; | |
79fe1b3b | 534 | |
8bcf15f6 JH |
535 | if (!loop_vinfo || !LOOP_VINFO_VECTORIZABLE_P (loop_vinfo)) |
536 | continue; | |
79fe1b3b | 537 | |
c716e67f XDL |
538 | if (!dbg_cnt (vect_loop)) |
539 | break; | |
540 | ||
355fe088 | 541 | gimple *loop_vectorized_call = vect_loop_vectorized_call (loop); |
5ce9450f | 542 | if (loop_vectorized_call) |
2fc3c9a5 | 543 | set_uid_loop_bbs (loop_vinfo, loop_vectorized_call); |
b05e0233 | 544 | if (LOCATION_LOCUS (vect_location) != UNKNOWN_LOCATION |
73fbfcad | 545 | && dump_enabled_p ()) |
5d318fd4 | 546 | dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location, |
9cc1fb4b | 547 | "loop vectorized\n"); |
8bcf15f6 JH |
548 | vect_transform_loop (loop_vinfo); |
549 | num_vectorized_loops++; | |
74bf76ed JJ |
550 | /* Now that the loop has been vectorized, allow it to be unrolled |
551 | etc. */ | |
b15b5979 | 552 | loop->force_vectorize = false; |
74bf76ed JJ |
553 | |
554 | if (loop->simduid) | |
555 | { | |
556 | simduid_to_vf *simduid_to_vf_data = XNEW (simduid_to_vf); | |
c203e8a7 TS |
557 | if (!simduid_to_vf_htab) |
558 | simduid_to_vf_htab = new hash_table<simduid_to_vf> (15); | |
74bf76ed JJ |
559 | simduid_to_vf_data->simduid = DECL_UID (loop->simduid); |
560 | simduid_to_vf_data->vf = loop_vinfo->vectorization_factor; | |
c203e8a7 | 561 | *simduid_to_vf_htab->find_slot (simduid_to_vf_data, INSERT) |
74bf76ed JJ |
562 | = simduid_to_vf_data; |
563 | } | |
5ce9450f JJ |
564 | |
565 | if (loop_vectorized_call) | |
566 | { | |
567 | fold_loop_vectorized_call (loop_vectorized_call, boolean_true_node); | |
568 | ret |= TODO_cleanup_cfg; | |
569 | } | |
8bcf15f6 | 570 | } |
8644a673 | 571 | |
b05e0233 | 572 | vect_location = UNKNOWN_LOCATION; |
79fe1b3b | 573 | |
01902653 | 574 | statistics_counter_event (cfun, "Vectorized loops", num_vectorized_loops); |
73fbfcad SS |
575 | if (dump_enabled_p () |
576 | || (num_vectorized_loops > 0 && dump_enabled_p ())) | |
ccb3ad87 | 577 | dump_printf_loc (MSG_NOTE, vect_location, |
78c60e3d SS |
578 | "vectorized %u loops in function.\n", |
579 | num_vectorized_loops); | |
79fe1b3b DN |
580 | |
581 | /* ----------- Finalize. ----------- */ | |
582 | ||
5ce9450f JJ |
583 | if (any_ifcvt_loops) |
584 | for (i = 1; i < vect_loops_num; i++) | |
585 | { | |
586 | loop = get_loop (cfun, i); | |
587 | if (loop && loop->dont_vectorize) | |
588 | { | |
355fe088 | 589 | gimple *g = vect_loop_vectorized_call (loop); |
5ce9450f JJ |
590 | if (g) |
591 | { | |
592 | fold_loop_vectorized_call (g, boolean_false_node); | |
593 | ret |= TODO_cleanup_cfg; | |
594 | } | |
595 | } | |
596 | } | |
597 | ||
b52485c6 | 598 | for (i = 1; i < vect_loops_num; i++) |
79fe1b3b | 599 | { |
6775f1f3 IR |
600 | loop_vec_info loop_vinfo; |
601 | ||
0fc822d0 | 602 | loop = get_loop (cfun, i); |
79fe1b3b | 603 | if (!loop) |
6775f1f3 | 604 | continue; |
3d9a9f94 | 605 | loop_vinfo = (loop_vec_info) loop->aux; |
d29de1bf | 606 | destroy_loop_vec_info (loop_vinfo, true); |
79fe1b3b DN |
607 | loop->aux = NULL; |
608 | } | |
4d2280f6 | 609 | |
726a989a RB |
610 | free_stmt_vec_info_vec (); |
611 | ||
d9a6bd32 | 612 | /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */ |
74bf76ed | 613 | if (cfun->has_simduid_loops) |
8c8b9f32 | 614 | adjust_simduid_builtins (simduid_to_vf_htab); |
74bf76ed JJ |
615 | |
616 | /* Shrink any "omp array simd" temporary arrays to the | |
617 | actual vectorization factors. */ | |
c203e8a7 | 618 | if (simd_array_to_simduid_htab) |
8c8b9f32 JJ |
619 | shrink_simd_arrays (simd_array_to_simduid_htab, simduid_to_vf_htab); |
620 | delete simduid_to_vf_htab; | |
621 | cfun->has_simduid_loops = false; | |
74bf76ed | 622 | |
789c34e3 RB |
623 | if (num_vectorized_loops > 0) |
624 | { | |
625 | /* If we vectorized any loop only virtual SSA form needs to be updated. | |
626 | ??? Also while we try hard to update loop-closed SSA form we fail | |
627 | to properly do this in some corner-cases (see PR56286). */ | |
628 | rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa_only_virtuals); | |
629 | return TODO_cleanup_cfg; | |
630 | } | |
631 | ||
5ce9450f | 632 | return ret; |
79fe1b3b | 633 | } |
b8698a0f | 634 | |
f4b3ca72 | 635 | |
8c8b9f32 JJ |
636 | /* Entry point to the simduid cleanup pass. */ |
637 | ||
638 | namespace { | |
639 | ||
640 | const pass_data pass_data_simduid_cleanup = | |
641 | { | |
642 | GIMPLE_PASS, /* type */ | |
643 | "simduid", /* name */ | |
644 | OPTGROUP_NONE, /* optinfo_flags */ | |
645 | TV_NONE, /* tv_id */ | |
646 | ( PROP_ssa | PROP_cfg ), /* properties_required */ | |
647 | 0, /* properties_provided */ | |
648 | 0, /* properties_destroyed */ | |
649 | 0, /* todo_flags_start */ | |
650 | 0, /* todo_flags_finish */ | |
651 | }; | |
652 | ||
653 | class pass_simduid_cleanup : public gimple_opt_pass | |
654 | { | |
655 | public: | |
656 | pass_simduid_cleanup (gcc::context *ctxt) | |
657 | : gimple_opt_pass (pass_data_simduid_cleanup, ctxt) | |
658 | {} | |
659 | ||
660 | /* opt_pass methods: */ | |
661 | opt_pass * clone () { return new pass_simduid_cleanup (m_ctxt); } | |
662 | virtual bool gate (function *fun) { return fun->has_simduid_loops; } | |
663 | virtual unsigned int execute (function *); | |
664 | ||
665 | }; // class pass_simduid_cleanup | |
666 | ||
667 | unsigned int | |
668 | pass_simduid_cleanup::execute (function *fun) | |
669 | { | |
670 | hash_table<simd_array_to_simduid> *simd_array_to_simduid_htab = NULL; | |
671 | ||
672 | note_simd_array_uses (&simd_array_to_simduid_htab); | |
673 | ||
d9a6bd32 | 674 | /* Fold IFN_GOMP_SIMD_{VF,LANE,LAST_LANE,ORDERED_{START,END}} builtins. */ |
8c8b9f32 JJ |
675 | adjust_simduid_builtins (NULL); |
676 | ||
677 | /* Shrink any "omp array simd" temporary arrays to the | |
678 | actual vectorization factors. */ | |
679 | if (simd_array_to_simduid_htab) | |
680 | shrink_simd_arrays (simd_array_to_simduid_htab, NULL); | |
681 | fun->has_simduid_loops = false; | |
682 | return 0; | |
683 | } | |
684 | ||
685 | } // anon namespace | |
686 | ||
687 | gimple_opt_pass * | |
688 | make_pass_simduid_cleanup (gcc::context *ctxt) | |
689 | { | |
690 | return new pass_simduid_cleanup (ctxt); | |
691 | } | |
692 | ||
693 | ||
a70d6342 IR |
694 | /* Entry point to basic block SLP phase. */ |
695 | ||
27a4cd48 DM |
696 | namespace { |
697 | ||
698 | const pass_data pass_data_slp_vectorize = | |
a70d6342 | 699 | { |
27a4cd48 DM |
700 | GIMPLE_PASS, /* type */ |
701 | "slp", /* name */ | |
702 | OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */ | |
27a4cd48 DM |
703 | TV_TREE_SLP_VECTORIZATION, /* tv_id */ |
704 | ( PROP_ssa | PROP_cfg ), /* properties_required */ | |
705 | 0, /* properties_provided */ | |
706 | 0, /* properties_destroyed */ | |
707 | 0, /* todo_flags_start */ | |
3bea341f | 708 | TODO_update_ssa, /* todo_flags_finish */ |
a70d6342 IR |
709 | }; |
710 | ||
27a4cd48 DM |
711 | class pass_slp_vectorize : public gimple_opt_pass |
712 | { | |
713 | public: | |
c3284718 RS |
714 | pass_slp_vectorize (gcc::context *ctxt) |
715 | : gimple_opt_pass (pass_data_slp_vectorize, ctxt) | |
27a4cd48 DM |
716 | {} |
717 | ||
718 | /* opt_pass methods: */ | |
e5d8bd8c | 719 | opt_pass * clone () { return new pass_slp_vectorize (m_ctxt); } |
1a3d085c | 720 | virtual bool gate (function *) { return flag_tree_slp_vectorize != 0; } |
be55bfe6 | 721 | virtual unsigned int execute (function *); |
27a4cd48 DM |
722 | |
723 | }; // class pass_slp_vectorize | |
724 | ||
be55bfe6 TS |
725 | unsigned int |
726 | pass_slp_vectorize::execute (function *fun) | |
727 | { | |
728 | basic_block bb; | |
729 | ||
e5d8bd8c RB |
730 | bool in_loop_pipeline = scev_initialized_p (); |
731 | if (!in_loop_pipeline) | |
732 | { | |
733 | loop_optimizer_init (LOOPS_NORMAL); | |
734 | scev_initialize (); | |
735 | } | |
736 | ||
c2a12ca0 | 737 | /* Mark all stmts as not belonging to the current region and unvisited. */ |
61d371eb RB |
738 | FOR_EACH_BB_FN (bb, fun) |
739 | { | |
740 | for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); | |
741 | gsi_next (&gsi)) | |
c2a12ca0 RB |
742 | { |
743 | gimple *stmt = gsi_stmt (gsi); | |
744 | gimple_set_uid (stmt, -1); | |
745 | gimple_set_visited (stmt, false); | |
746 | } | |
61d371eb RB |
747 | } |
748 | ||
be55bfe6 TS |
749 | init_stmt_vec_info_vec (); |
750 | ||
751 | FOR_EACH_BB_FN (bb, fun) | |
752 | { | |
428db0ba RB |
753 | if (vect_slp_bb (bb)) |
754 | dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, vect_location, | |
755 | "basic block vectorized\n"); | |
be55bfe6 TS |
756 | } |
757 | ||
758 | free_stmt_vec_info_vec (); | |
e5d8bd8c RB |
759 | |
760 | if (!in_loop_pipeline) | |
761 | { | |
762 | scev_finalize (); | |
763 | loop_optimizer_finalize (); | |
764 | } | |
765 | ||
be55bfe6 TS |
766 | return 0; |
767 | } | |
768 | ||
27a4cd48 DM |
769 | } // anon namespace |
770 | ||
771 | gimple_opt_pass * | |
772 | make_pass_slp_vectorize (gcc::context *ctxt) | |
773 | { | |
774 | return new pass_slp_vectorize (ctxt); | |
775 | } | |
776 | ||
a70d6342 | 777 | |
f4b3ca72 JH |
778 | /* Increase alignment of global arrays to improve vectorization potential. |
779 | TODO: | |
780 | - Consider also structs that have an array field. | |
781 | - Use ipa analysis to prune arrays that can't be vectorized? | |
782 | This should involve global alignment analysis and in the future also | |
783 | array padding. */ | |
784 | ||
785 | static unsigned int | |
786 | increase_alignment (void) | |
787 | { | |
2c8326a5 | 788 | varpool_node *vnode; |
f4b3ca72 | 789 | |
b05e0233 | 790 | vect_location = UNKNOWN_LOCATION; |
a3d7af04 | 791 | |
f4b3ca72 | 792 | /* Increase the alignment of all global arrays for vectorization. */ |
65c70e6b | 793 | FOR_EACH_DEFINED_VARIABLE (vnode) |
f4b3ca72 | 794 | { |
67348ccc | 795 | tree vectype, decl = vnode->decl; |
cba146eb | 796 | tree t; |
f4b3ca72 JH |
797 | unsigned int alignment; |
798 | ||
c3284718 | 799 | t = TREE_TYPE (decl); |
cba146eb | 800 | if (TREE_CODE (t) != ARRAY_TYPE) |
ebfd146a | 801 | continue; |
cba146eb | 802 | vectype = get_vectype_for_scalar_type (strip_array_types (t)); |
f4b3ca72 | 803 | if (!vectype) |
ebfd146a | 804 | continue; |
f4b3ca72 JH |
805 | alignment = TYPE_ALIGN (vectype); |
806 | if (DECL_ALIGN (decl) >= alignment) | |
ebfd146a | 807 | continue; |
f4b3ca72 JH |
808 | |
809 | if (vect_can_force_dr_alignment_p (decl, alignment)) | |
ebfd146a | 810 | { |
428f0c67 | 811 | vnode->increase_alignment (TYPE_ALIGN (vectype)); |
78c60e3d SS |
812 | dump_printf (MSG_NOTE, "Increasing alignment of decl: "); |
813 | dump_generic_expr (MSG_NOTE, TDF_SLIM, decl); | |
814 | dump_printf (MSG_NOTE, "\n"); | |
ebfd146a | 815 | } |
f4b3ca72 JH |
816 | } |
817 | return 0; | |
818 | } | |
819 | ||
ebfd146a | 820 | |
27a4cd48 DM |
821 | namespace { |
822 | ||
823 | const pass_data pass_data_ipa_increase_alignment = | |
f4b3ca72 | 824 | { |
27a4cd48 DM |
825 | SIMPLE_IPA_PASS, /* type */ |
826 | "increase_alignment", /* name */ | |
827 | OPTGROUP_LOOP | OPTGROUP_VEC, /* optinfo_flags */ | |
27a4cd48 DM |
828 | TV_IPA_OPT, /* tv_id */ |
829 | 0, /* properties_required */ | |
830 | 0, /* properties_provided */ | |
831 | 0, /* properties_destroyed */ | |
832 | 0, /* todo_flags_start */ | |
833 | 0, /* todo_flags_finish */ | |
f4b3ca72 | 834 | }; |
27a4cd48 DM |
835 | |
836 | class pass_ipa_increase_alignment : public simple_ipa_opt_pass | |
837 | { | |
838 | public: | |
c3284718 RS |
839 | pass_ipa_increase_alignment (gcc::context *ctxt) |
840 | : simple_ipa_opt_pass (pass_data_ipa_increase_alignment, ctxt) | |
27a4cd48 DM |
841 | {} |
842 | ||
843 | /* opt_pass methods: */ | |
1a3d085c TS |
844 | virtual bool gate (function *) |
845 | { | |
846 | return flag_section_anchors && flag_tree_loop_vectorize; | |
847 | } | |
848 | ||
be55bfe6 | 849 | virtual unsigned int execute (function *) { return increase_alignment (); } |
27a4cd48 DM |
850 | |
851 | }; // class pass_ipa_increase_alignment | |
852 | ||
853 | } // anon namespace | |
854 | ||
855 | simple_ipa_opt_pass * | |
856 | make_pass_ipa_increase_alignment (gcc::context *ctxt) | |
857 | { | |
858 | return new pass_ipa_increase_alignment (ctxt); | |
859 | } |