Line data Source code
1 : /* Loop autoparallelization.
2 : Copyright (C) 2006-2026 Free Software Foundation, Inc.
3 : Contributed by Sebastian Pop <pop@cri.ensmp.fr>
4 : Zdenek Dvorak <dvorakz@suse.cz> and Razya Ladelsky <razya@il.ibm.com>.
5 :
6 : This file is part of GCC.
7 :
8 : GCC is free software; you can redistribute it and/or modify it under
9 : the terms of the GNU General Public License as published by the Free
10 : Software Foundation; either version 3, or (at your option) any later
11 : version.
12 :
13 : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 : WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 : for more details.
17 :
18 : You should have received a copy of the GNU General Public License
19 : along with GCC; see the file COPYING3. If not see
20 : <http://www.gnu.org/licenses/>. */
21 :
22 : #include "config.h"
23 : #include "system.h"
24 : #include "coretypes.h"
25 : #include "backend.h"
26 : #include "tree.h"
27 : #include "gimple.h"
28 : #include "cfghooks.h"
29 : #include "tree-pass.h"
30 : #include "ssa.h"
31 : #include "cgraph.h"
32 : #include "gimple-pretty-print.h"
33 : #include "fold-const.h"
34 : #include "gimplify.h"
35 : #include "gimple-iterator.h"
36 : #include "gimplify-me.h"
37 : #include "gimple-walk.h"
38 : #include "stor-layout.h"
39 : #include "tree-nested.h"
40 : #include "tree-cfg.h"
41 : #include "tree-ssa-loop-ivopts.h"
42 : #include "tree-ssa-loop-manip.h"
43 : #include "tree-ssa-loop-niter.h"
44 : #include "tree-ssa-loop.h"
45 : #include "tree-into-ssa.h"
46 : #include "cfgloop.h"
47 : #include "tree-scalar-evolution.h"
48 : #include "langhooks.h"
49 : #include "tree-vectorizer.h"
50 : #include "tree-hasher.h"
51 : #include "tree-parloops.h"
52 : #include "omp-general.h"
53 : #include "omp-low.h"
54 : #include "tree-ssa.h"
55 : #include "tree-ssa-alias.h"
56 : #include "tree-eh.h"
57 : #include "gomp-constants.h"
58 : #include "tree-dfa.h"
59 : #include "stringpool.h"
60 : #include "attribs.h"
61 :
62 : /* This pass tries to distribute iterations of loops into several threads.
63 : The implementation is straightforward -- for each loop we test whether its
64 : iterations are independent, and if it is the case (and some additional
65 : conditions regarding profitability and correctness are satisfied), we
66 : add GIMPLE_OMP_PARALLEL and GIMPLE_OMP_FOR codes and let omp expansion
67 : machinery do its job.
68 :
69 : The most of the complexity is in bringing the code into shape expected
70 : by the omp expanders:
71 : -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction
72 : variable and that the exit test is at the start of the loop body
73 : -- for GIMPLE_OMP_PARALLEL, replacing the references to local addressable
74 : variables by accesses through pointers, and breaking up ssa chains
75 : by storing the values incoming to the parallelized loop to a structure
76 : passed to the new function as an argument (something similar is done
77 : in omp gimplification, unfortunately only a small part of the code
78 : can be shared).
79 :
80 : TODO:
81 : -- if there are several parallelizable loops in a function, it may be
82 : possible to generate the threads just once (using synchronization to
83 : ensure that cross-loop dependences are obeyed).
84 : -- handling of common reduction patterns for outer loops.
85 :
86 : More info can also be found at http://gcc.gnu.org/wiki/AutoParInGCC */
87 : /*
88 : Reduction handling:
89 : currently we use code inspired by vect_force_simple_reduction to detect
90 : reduction patterns.
91 : The code transformation will be introduced by an example.
92 :
93 :
94 : parloop
95 : {
96 : int sum=1;
97 :
98 : for (i = 0; i < N; i++)
99 : {
100 : x[i] = i + 3;
101 : sum+=x[i];
102 : }
103 : }
104 :
105 : gimple-like code:
106 : header_bb:
107 :
108 : # sum_29 = PHI <sum_11(5), 1(3)>
109 : # i_28 = PHI <i_12(5), 0(3)>
110 : D.1795_8 = i_28 + 3;
111 : x[i_28] = D.1795_8;
112 : sum_11 = D.1795_8 + sum_29;
113 : i_12 = i_28 + 1;
114 : if (N_6(D) > i_12)
115 : goto header_bb;
116 :
117 :
118 : exit_bb:
119 :
120 : # sum_21 = PHI <sum_11(4)>
121 : printf (&"%d"[0], sum_21);
122 :
123 :
124 : after reduction transformation (only relevant parts):
125 :
126 : parloop
127 : {
128 :
129 : ....
130 :
131 :
132 : # Storing the initial value given by the user. #
133 :
134 : .paral_data_store.32.sum.27 = 1;
135 :
136 : #pragma omp parallel num_threads(4)
137 :
138 : #pragma omp for schedule(static)
139 :
140 : # The neutral element corresponding to the particular
141 : reduction's operation, e.g. 0 for PLUS_EXPR,
142 : 1 for MULT_EXPR, etc. replaces the user's initial value. #
143 :
144 : # sum.27_29 = PHI <sum.27_11, 0>
145 :
146 : sum.27_11 = D.1827_8 + sum.27_29;
147 :
148 : GIMPLE_OMP_CONTINUE
149 :
150 : # Adding this reduction phi is done at create_phi_for_local_result() #
151 : # sum.27_56 = PHI <sum.27_11, 0>
152 : GIMPLE_OMP_RETURN
153 :
154 : # Creating the atomic operation is done at
155 : create_call_for_reduction_1() #
156 :
157 : #pragma omp atomic_load
158 : D.1839_59 = *&.paral_data_load.33_51->reduction.23;
159 : D.1840_60 = sum.27_56 + D.1839_59;
160 : #pragma omp atomic_store (D.1840_60);
161 :
162 : GIMPLE_OMP_RETURN
163 :
164 : # collecting the result after the join of the threads is done at
165 : create_loads_for_reductions().
166 : The value computed by the threads is loaded from the
167 : shared struct. #
168 :
169 :
170 : .paral_data_load.33_52 = &.paral_data_store.32;
171 : sum_37 = .paral_data_load.33_52->sum.27;
172 : sum_43 = D.1795_41 + sum_37;
173 :
174 : exit bb:
175 : # sum_21 = PHI <sum_43, sum_26>
176 : printf (&"%d"[0], sum_21);
177 :
178 : ...
179 :
180 : }
181 :
182 : */
183 :
184 : /* Error reporting helper for parloops_is_simple_reduction below. GIMPLE
185 : statement STMT is printed with a message MSG. */
186 :
187 : static void
188 69 : report_ploop_op (dump_flags_t msg_type, gimple *stmt, const char *msg)
189 : {
190 69 : dump_printf_loc (msg_type, vect_location, "%s%G", msg, stmt);
191 69 : }
192 :
193 : /* DEF_STMT_INFO occurs in a loop that contains a potential reduction
194 : operation. Return true if the results of DEF_STMT_INFO are something
195 : that can be accumulated by such a reduction. */
196 :
197 : static bool
198 84 : parloops_valid_reduction_input_p (stmt_vec_info def_stmt_info)
199 : {
200 84 : return (is_gimple_assign (def_stmt_info->stmt)
201 2 : || is_gimple_call (def_stmt_info->stmt)
202 2 : || STMT_VINFO_DEF_TYPE (def_stmt_info) == vect_induction_def
203 86 : || (gimple_code (def_stmt_info->stmt) == GIMPLE_PHI
204 2 : && STMT_VINFO_DEF_TYPE (def_stmt_info) == vect_internal_def
205 2 : && !is_loop_header_bb_p (gimple_bb (def_stmt_info->stmt))));
206 : }
207 :
208 : /* Return true if we need an in-order reduction for operation CODE
209 : on type TYPE. NEED_WRAPPING_INTEGRAL_OVERFLOW is true if integer
210 : overflow must wrap. */
211 :
212 : static bool
213 104 : parloops_needs_fold_left_reduction_p (tree type, tree_code code,
214 : bool need_wrapping_integral_overflow)
215 : {
216 : /* CHECKME: check for !flag_finite_math_only too? */
217 104 : if (SCALAR_FLOAT_TYPE_P (type))
218 17 : switch (code)
219 : {
220 : case MIN_EXPR:
221 : case MAX_EXPR:
222 : return false;
223 :
224 17 : default:
225 17 : return !flag_associative_math;
226 : }
227 :
228 87 : if (INTEGRAL_TYPE_P (type))
229 : {
230 83 : if (!operation_no_trapping_overflow (type, code))
231 : return true;
232 83 : if (need_wrapping_integral_overflow
233 83 : && !TYPE_OVERFLOW_WRAPS (type)
234 116 : && operation_can_overflow (code))
235 : return true;
236 66 : return false;
237 : }
238 :
239 4 : if (SAT_FIXED_POINT_TYPE_P (type))
240 : return true;
241 :
242 : return false;
243 : }
244 :
245 :
246 : /* Function parloops_is_simple_reduction
247 :
248 : (1) Detect a cross-iteration def-use cycle that represents a simple
249 : reduction computation. We look for the following pattern:
250 :
251 : loop_header:
252 : a1 = phi < a0, a2 >
253 : a3 = ...
254 : a2 = operation (a3, a1)
255 :
256 : or
257 :
258 : a3 = ...
259 : loop_header:
260 : a1 = phi < a0, a2 >
261 : a2 = operation (a3, a1)
262 :
263 : such that:
264 : 1. operation is commutative and associative and it is safe to
265 : change the order of the computation
266 : 2. no uses for a2 in the loop (a2 is used out of the loop)
267 : 3. no uses of a1 in the loop besides the reduction operation
268 : 4. no uses of a1 outside the loop.
269 :
270 : Conditions 1,4 are tested here.
271 : Conditions 2,3 are tested in vect_mark_stmts_to_be_vectorized.
272 :
273 : (2) Detect a cross-iteration def-use cycle in nested loops, i.e.,
274 : nested cycles.
275 :
276 : (3) Detect cycles of phi nodes in outer-loop vectorization, i.e., double
277 : reductions:
278 :
279 : a1 = phi < a0, a2 >
280 : inner loop (def of a3)
281 : a2 = phi < a3 >
282 :
283 : (4) Detect condition expressions, ie:
284 : for (int i = 0; i < N; i++)
285 : if (a[i] < val)
286 : ret_val = a[i];
287 :
288 : */
289 :
290 : static stmt_vec_info
291 136 : parloops_is_simple_reduction (loop_vec_info loop_info, stmt_vec_info phi_info,
292 : bool *double_reduc,
293 : bool need_wrapping_integral_overflow,
294 : enum vect_reduction_type *v_reduc_type,
295 : hash_set<gphi *> &double_reduc_inner_lc_phis)
296 : {
297 136 : gphi *phi = as_a <gphi *> (phi_info->stmt);
298 136 : class loop *loop = (gimple_bb (phi))->loop_father;
299 136 : class loop *vect_loop = LOOP_VINFO_LOOP (loop_info);
300 136 : bool nested_in_vect_loop = flow_loop_nested_p (vect_loop, loop);
301 136 : gimple *phi_use_stmt = NULL;
302 136 : enum tree_code orig_code, code;
303 136 : tree op1, op2, op3 = NULL_TREE, op4 = NULL_TREE;
304 136 : tree type;
305 136 : tree name;
306 136 : imm_use_iterator imm_iter;
307 136 : use_operand_p use_p;
308 136 : bool phi_def;
309 :
310 136 : *double_reduc = false;
311 136 : *v_reduc_type = TREE_CODE_REDUCTION;
312 :
313 136 : tree phi_name = PHI_RESULT (phi);
314 : /* ??? If there are no uses of the PHI result the inner loop reduction
315 : won't be detected as possibly double-reduction by vectorizable_reduction
316 : because that tries to walk the PHI arg from the preheader edge which
317 : can be constant. See PR60382. */
318 136 : if (has_zero_uses (phi_name))
319 : return NULL;
320 136 : unsigned nphi_def_loop_uses = 0;
321 418 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, phi_name)
322 : {
323 146 : gimple *use_stmt = USE_STMT (use_p);
324 146 : if (is_gimple_debug (use_stmt))
325 1 : continue;
326 :
327 145 : if (!flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
328 : {
329 0 : if (dump_enabled_p ())
330 0 : dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
331 : "intermediate value used outside loop.\n");
332 :
333 0 : return NULL;
334 : }
335 :
336 145 : nphi_def_loop_uses++;
337 145 : phi_use_stmt = use_stmt;
338 0 : }
339 :
340 136 : edge latch_e = loop_latch_edge (loop);
341 136 : tree loop_arg = PHI_ARG_DEF_FROM_EDGE (phi, latch_e);
342 136 : if (TREE_CODE (loop_arg) != SSA_NAME)
343 : {
344 0 : if (dump_enabled_p ())
345 0 : dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
346 : "reduction: not ssa_name: %T\n", loop_arg);
347 0 : return NULL;
348 : }
349 :
350 136 : stmt_vec_info def_stmt_info = loop_info->lookup_def (loop_arg);
351 136 : if (!def_stmt_info
352 136 : || !flow_bb_inside_loop_p (loop, gimple_bb (def_stmt_info->stmt)))
353 0 : return NULL;
354 :
355 136 : if (gassign *def_stmt = dyn_cast <gassign *> (def_stmt_info->stmt))
356 : {
357 117 : name = gimple_assign_lhs (def_stmt);
358 117 : phi_def = false;
359 : }
360 19 : else if (gphi *def_stmt = dyn_cast <gphi *> (def_stmt_info->stmt))
361 : {
362 19 : name = PHI_RESULT (def_stmt);
363 19 : phi_def = true;
364 : }
365 : else
366 : {
367 0 : if (dump_enabled_p ())
368 0 : dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
369 : "reduction: unhandled reduction operation: %G",
370 : def_stmt_info->stmt);
371 0 : return NULL;
372 : }
373 :
374 136 : unsigned nlatch_def_loop_uses = 0;
375 136 : auto_vec<gphi *, 3> lcphis;
376 136 : bool inner_loop_of_double_reduc = false;
377 542 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, name)
378 : {
379 270 : gimple *use_stmt = USE_STMT (use_p);
380 270 : if (is_gimple_debug (use_stmt))
381 2 : continue;
382 268 : if (flow_bb_inside_loop_p (loop, gimple_bb (use_stmt)))
383 140 : nlatch_def_loop_uses++;
384 : else
385 : {
386 : /* We can have more than one loop-closed PHI. */
387 128 : lcphis.safe_push (as_a <gphi *> (use_stmt));
388 128 : if (nested_in_vect_loop
389 128 : && double_reduc_inner_lc_phis.contains (as_a <gphi *> (use_stmt)))
390 19 : inner_loop_of_double_reduc = true;
391 : }
392 136 : }
393 :
394 : /* If this isn't a nested cycle or if the nested cycle reduction value
395 : is used ouside of the inner loop we cannot handle uses of the reduction
396 : value. */
397 136 : if ((!nested_in_vect_loop || inner_loop_of_double_reduc)
398 136 : && (nlatch_def_loop_uses > 1 || nphi_def_loop_uses > 1))
399 : {
400 11 : if (dump_enabled_p ())
401 11 : dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
402 : "reduction used in loop.\n");
403 11 : return NULL;
404 : }
405 :
406 : /* If DEF_STMT is a phi node itself, we expect it to have a single argument
407 : defined in the inner loop. */
408 125 : if (phi_def)
409 : {
410 19 : gphi *def_stmt = as_a <gphi *> (def_stmt_info->stmt);
411 19 : op1 = PHI_ARG_DEF (def_stmt, 0);
412 :
413 19 : if (gimple_phi_num_args (def_stmt) != 1
414 19 : || TREE_CODE (op1) != SSA_NAME)
415 : {
416 0 : if (dump_enabled_p ())
417 0 : dump_printf_loc (MSG_MISSED_OPTIMIZATION, vect_location,
418 : "unsupported phi node definition.\n");
419 :
420 0 : return NULL;
421 : }
422 :
423 19 : gimple *def1 = SSA_NAME_DEF_STMT (op1);
424 19 : if (gimple_bb (def1)
425 19 : && flow_bb_inside_loop_p (loop, gimple_bb (def_stmt))
426 19 : && loop->inner
427 19 : && flow_bb_inside_loop_p (loop->inner, gimple_bb (def1))
428 19 : && is_gimple_assign (def1)
429 19 : && is_a <gphi *> (phi_use_stmt)
430 38 : && flow_bb_inside_loop_p (loop->inner, gimple_bb (phi_use_stmt)))
431 : {
432 19 : if (dump_enabled_p ())
433 14 : report_ploop_op (MSG_NOTE, def_stmt,
434 : "detected double reduction: ");
435 :
436 19 : *double_reduc = true;
437 19 : return def_stmt_info;
438 : }
439 :
440 0 : return NULL;
441 : }
442 :
443 : /* If we are vectorizing an inner reduction we are executing that
444 : in the original order only in case we are not dealing with a
445 : double reduction. */
446 106 : bool check_reduction = true;
447 106 : if (flow_loop_nested_p (vect_loop, loop))
448 : {
449 : gphi *lcphi;
450 : unsigned i;
451 : check_reduction = false;
452 38 : FOR_EACH_VEC_ELT (lcphis, i, lcphi)
453 76 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, gimple_phi_result (lcphi))
454 : {
455 38 : gimple *use_stmt = USE_STMT (use_p);
456 38 : if (is_gimple_debug (use_stmt))
457 0 : continue;
458 38 : if (! flow_bb_inside_loop_p (vect_loop, gimple_bb (use_stmt)))
459 38 : check_reduction = true;
460 19 : }
461 : }
462 :
463 106 : gassign *def_stmt = as_a <gassign *> (def_stmt_info->stmt);
464 106 : code = orig_code = gimple_assign_rhs_code (def_stmt);
465 :
466 106 : if (nested_in_vect_loop && !check_reduction)
467 : {
468 : /* FIXME: Even for non-reductions code generation is funneled
469 : through vectorizable_reduction for the stmt defining the
470 : PHI latch value. So we have to artificially restrict ourselves
471 : for the supported operations. */
472 0 : switch (get_gimple_rhs_class (code))
473 : {
474 0 : case GIMPLE_BINARY_RHS:
475 0 : case GIMPLE_TERNARY_RHS:
476 0 : break;
477 0 : default:
478 : /* Not supported by vectorizable_reduction. */
479 0 : if (dump_enabled_p ())
480 0 : report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
481 : "nested cycle: not handled operation: ");
482 0 : return NULL;
483 : }
484 0 : if (dump_enabled_p ())
485 0 : report_ploop_op (MSG_NOTE, def_stmt, "detected nested cycle: ");
486 0 : return def_stmt_info;
487 : }
488 :
489 : /* We can handle "res -= x[i]", which is non-associative by
490 : simply rewriting this into "res += -x[i]". Avoid changing
491 : gimple instruction for the first simple tests and only do this
492 : if we're allowed to change code at all. */
493 121 : if (code == MINUS_EXPR && gimple_assign_rhs2 (def_stmt) != phi_name)
494 : code = PLUS_EXPR;
495 :
496 91 : if (code == COND_EXPR)
497 : {
498 0 : if (! nested_in_vect_loop)
499 0 : *v_reduc_type = COND_REDUCTION;
500 :
501 0 : op3 = gimple_assign_rhs1 (def_stmt);
502 0 : if (COMPARISON_CLASS_P (op3))
503 : {
504 0 : op4 = TREE_OPERAND (op3, 1);
505 0 : op3 = TREE_OPERAND (op3, 0);
506 : }
507 0 : if (op3 == phi_name || op4 == phi_name)
508 : {
509 0 : if (dump_enabled_p ())
510 0 : report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
511 : "reduction: condition depends on previous"
512 : " iteration: ");
513 0 : return NULL;
514 : }
515 :
516 0 : op1 = gimple_assign_rhs2 (def_stmt);
517 0 : op2 = gimple_assign_rhs3 (def_stmt);
518 : }
519 106 : else if (!commutative_tree_code (code) || !associative_tree_code (code))
520 : {
521 2 : if (dump_enabled_p ())
522 2 : report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
523 : "reduction: not commutative/associative: ");
524 2 : return NULL;
525 : }
526 104 : else if (get_gimple_rhs_class (code) == GIMPLE_BINARY_RHS)
527 : {
528 104 : op1 = gimple_assign_rhs1 (def_stmt);
529 104 : op2 = gimple_assign_rhs2 (def_stmt);
530 : }
531 : else
532 : {
533 0 : if (dump_enabled_p ())
534 0 : report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
535 : "reduction: not handled operation: ");
536 0 : return NULL;
537 : }
538 :
539 104 : if (TREE_CODE (op1) != SSA_NAME && TREE_CODE (op2) != SSA_NAME)
540 : {
541 0 : if (dump_enabled_p ())
542 0 : report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
543 : "reduction: both uses not ssa_names: ");
544 :
545 0 : return NULL;
546 : }
547 :
548 104 : type = TREE_TYPE (gimple_assign_lhs (def_stmt));
549 104 : if ((TREE_CODE (op1) == SSA_NAME
550 104 : && !types_compatible_p (type,TREE_TYPE (op1)))
551 104 : || (TREE_CODE (op2) == SSA_NAME
552 101 : && !types_compatible_p (type, TREE_TYPE (op2)))
553 104 : || (op3 && TREE_CODE (op3) == SSA_NAME
554 0 : && !types_compatible_p (type, TREE_TYPE (op3)))
555 208 : || (op4 && TREE_CODE (op4) == SSA_NAME
556 0 : && !types_compatible_p (type, TREE_TYPE (op4))))
557 : {
558 0 : if (dump_enabled_p ())
559 : {
560 0 : dump_printf_loc (MSG_NOTE, vect_location,
561 : "reduction: multiple types: operation type: "
562 : "%T, operands types: %T,%T",
563 0 : type, TREE_TYPE (op1), TREE_TYPE (op2));
564 0 : if (op3)
565 0 : dump_printf (MSG_NOTE, ",%T", TREE_TYPE (op3));
566 :
567 0 : if (op4)
568 0 : dump_printf (MSG_NOTE, ",%T", TREE_TYPE (op4));
569 0 : dump_printf (MSG_NOTE, "\n");
570 : }
571 :
572 0 : return NULL;
573 : }
574 :
575 : /* Check whether it's ok to change the order of the computation.
576 : Generally, when vectorizing a reduction we change the order of the
577 : computation. This may change the behavior of the program in some
578 : cases, so we need to check that this is ok. One exception is when
579 : vectorizing an outer-loop: the inner-loop is executed sequentially,
580 : and therefore vectorizing reductions in the inner-loop during
581 : outer-loop vectorization is safe. */
582 104 : if (check_reduction
583 104 : && *v_reduc_type == TREE_CODE_REDUCTION
584 208 : && parloops_needs_fold_left_reduction_p (type, code,
585 : need_wrapping_integral_overflow))
586 19 : *v_reduc_type = FOLD_LEFT_REDUCTION;
587 :
588 : /* Reduction is safe. We're dealing with one of the following:
589 : 1) integer arithmetic and no trapv
590 : 2) floating point arithmetic, and special flags permit this optimization
591 : 3) nested cycle (i.e., outer loop vectorization). */
592 104 : stmt_vec_info def1_info = loop_info->lookup_def (op1);
593 104 : stmt_vec_info def2_info = loop_info->lookup_def (op2);
594 104 : if (code != COND_EXPR && !def1_info && !def2_info)
595 : {
596 0 : if (dump_enabled_p ())
597 0 : report_ploop_op (MSG_NOTE, def_stmt,
598 : "reduction: no defs for operands: ");
599 0 : return NULL;
600 : }
601 :
602 : /* Check that one def is the reduction def, defined by PHI,
603 : the other def is either defined in the loop ("vect_internal_def"),
604 : or it's an induction (defined by a loop-header phi-node). */
605 :
606 104 : if (def2_info
607 101 : && def2_info->stmt == phi
608 104 : && (code == COND_EXPR
609 80 : || !def1_info
610 80 : || !flow_bb_inside_loop_p (loop, gimple_bb (def1_info->stmt))
611 80 : || parloops_valid_reduction_input_p (def1_info)))
612 : {
613 80 : if (dump_enabled_p ())
614 49 : report_ploop_op (MSG_NOTE, def_stmt, "detected reduction: ");
615 80 : return def_stmt_info;
616 : }
617 :
618 24 : if (def1_info
619 24 : && def1_info->stmt == phi
620 24 : && (code == COND_EXPR
621 7 : || !def2_info
622 4 : || !flow_bb_inside_loop_p (loop, gimple_bb (def2_info->stmt))
623 4 : || parloops_valid_reduction_input_p (def2_info)))
624 : {
625 7 : if (! nested_in_vect_loop && orig_code != MINUS_EXPR)
626 : {
627 : /* Check if we can swap operands (just for simplicity - so that
628 : the rest of the code can assume that the reduction variable
629 : is always the last (second) argument). */
630 3 : if (code == COND_EXPR)
631 : {
632 : /* Swap cond_expr by inverting the condition. */
633 0 : tree cond_expr = gimple_assign_rhs1 (def_stmt);
634 0 : enum tree_code invert_code = ERROR_MARK;
635 0 : enum tree_code cond_code = TREE_CODE (cond_expr);
636 :
637 0 : if (TREE_CODE_CLASS (cond_code) == tcc_comparison)
638 : {
639 0 : bool honor_nans = HONOR_NANS (TREE_OPERAND (cond_expr, 0));
640 0 : invert_code = invert_tree_comparison (cond_code, honor_nans);
641 : }
642 0 : if (invert_code != ERROR_MARK)
643 : {
644 0 : TREE_SET_CODE (cond_expr, invert_code);
645 0 : swap_ssa_operands (def_stmt,
646 : gimple_assign_rhs2_ptr (def_stmt),
647 : gimple_assign_rhs3_ptr (def_stmt));
648 : }
649 : else
650 : {
651 0 : if (dump_enabled_p ())
652 0 : report_ploop_op (MSG_NOTE, def_stmt,
653 : "detected reduction: cannot swap operands "
654 : "for cond_expr");
655 0 : return NULL;
656 : }
657 : }
658 : else
659 3 : swap_ssa_operands (def_stmt, gimple_assign_rhs1_ptr (def_stmt),
660 : gimple_assign_rhs2_ptr (def_stmt));
661 :
662 3 : if (dump_enabled_p ())
663 0 : report_ploop_op (MSG_NOTE, def_stmt,
664 : "detected reduction: need to swap operands: ");
665 : }
666 : else
667 : {
668 4 : if (dump_enabled_p ())
669 4 : report_ploop_op (MSG_NOTE, def_stmt, "detected reduction: ");
670 : }
671 :
672 7 : return def_stmt_info;
673 : }
674 :
675 : /* Look for the expression computing loop_arg from loop PHI result. */
676 17 : if (check_reduction_path (vect_location, loop, phi, loop_arg, code))
677 : return def_stmt_info;
678 :
679 0 : if (dump_enabled_p ())
680 : {
681 0 : report_ploop_op (MSG_MISSED_OPTIMIZATION, def_stmt,
682 : "reduction: unknown pattern: ");
683 : }
684 :
685 : return NULL;
686 136 : }
687 :
688 : /* Wrapper around vect_is_simple_reduction, which will modify code
689 : in-place if it enables detection of more reductions. Arguments
690 : as there. */
691 :
692 : stmt_vec_info
693 136 : parloops_force_simple_reduction (loop_vec_info loop_info, stmt_vec_info phi_info,
694 : bool *double_reduc,
695 : bool need_wrapping_integral_overflow,
696 : hash_set<gphi *> &double_reduc_inner_lc_phis)
697 : {
698 136 : enum vect_reduction_type v_reduc_type;
699 136 : stmt_vec_info def_info
700 136 : = parloops_is_simple_reduction (loop_info, phi_info, double_reduc,
701 : need_wrapping_integral_overflow,
702 : &v_reduc_type, double_reduc_inner_lc_phis);
703 : /* Parallelization would reassociate the operation, which isn't
704 : allowed for in-order reductions. */
705 136 : if (v_reduc_type == FOLD_LEFT_REDUCTION)
706 : return NULL;
707 117 : if (def_info && *double_reduc)
708 19 : double_reduc_inner_lc_phis.add (as_a <gphi *> (def_info->stmt));
709 : return def_info;
710 : }
711 :
712 : /* Minimal number of iterations of a loop that should be executed in each
713 : thread. */
714 : #define MIN_PER_THREAD param_parloops_min_per_thread
715 :
716 : /* Element of the hashtable, representing a
717 : reduction in the current loop. */
718 : struct reduction_info
719 : {
720 : gimple *reduc_stmt; /* reduction statement. */
721 : tree reduc_phi_name; /* The result of the phi node defining the reduction. */
722 : enum tree_code reduction_code;/* code for the reduction operation. */
723 : unsigned reduc_version; /* SSA_NAME_VERSION of original reduc_phi
724 : result. */
725 : gphi *keep_res; /* The PHI_RESULT of this phi is the resulting value
726 : of the reduction variable when existing the loop. */
727 : tree initial_value; /* The initial value of the reduction var before entering the loop. */
728 : tree field; /* the name of the field in the parloop data structure intended for reduction. */
729 : tree reduc_addr; /* The address of the reduction variable for
730 : openacc reductions. */
731 : tree init; /* reduction initialization value. */
732 : gphi *new_phi; /* (helper field) Newly created phi node whose result
733 : will be passed to the atomic operation. Represents
734 : the local result each thread computed for the reduction
735 : operation. */
736 :
737 : gphi *
738 583 : reduc_phi () const
739 : {
740 583 : return as_a<gphi *> (SSA_NAME_DEF_STMT (reduc_phi_name));
741 : }
742 : };
743 :
744 : /* Reduction info hashtable helpers. */
745 :
746 : struct reduction_hasher : free_ptr_hash <reduction_info>
747 : {
748 : static inline hashval_t hash (const reduction_info *);
749 : static inline bool equal (const reduction_info *, const reduction_info *);
750 : };
751 :
752 : /* Equality and hash functions for hashtab code. */
753 :
754 : inline bool
755 338 : reduction_hasher::equal (const reduction_info *a, const reduction_info *b)
756 : {
757 338 : return (a->reduc_phi_name == b->reduc_phi_name);
758 : }
759 :
760 : inline hashval_t
761 263 : reduction_hasher::hash (const reduction_info *a)
762 : {
763 263 : return a->reduc_version;
764 : }
765 :
766 : typedef hash_table<reduction_hasher> reduction_info_table_type;
767 :
768 :
769 : static struct reduction_info *
770 1414 : reduction_phi (reduction_info_table_type *reduction_list, gimple *phi)
771 : {
772 1414 : struct reduction_info tmpred, *red;
773 :
774 1414 : if (reduction_list->is_empty () || phi == NULL || !is_a <gphi *> (phi))
775 : return NULL;
776 :
777 405 : if (gimple_uid (phi) == (unsigned int)-1
778 405 : || gimple_uid (phi) == 0)
779 : return NULL;
780 :
781 320 : tmpred.reduc_phi_name = gimple_phi_result (phi);
782 320 : tmpred.reduc_version = gimple_uid (phi);
783 320 : red = reduction_list->find (&tmpred);
784 320 : gcc_assert (red == NULL || red->reduc_phi () == phi);
785 :
786 : return red;
787 : }
788 :
789 : /* Element of hashtable of names to copy. */
790 :
791 : struct name_to_copy_elt
792 : {
793 : unsigned version; /* The version of the name to copy. */
794 : tree new_name; /* The new name used in the copy. */
795 : tree field; /* The field of the structure used to pass the
796 : value. */
797 : };
798 :
799 : /* Name copies hashtable helpers. */
800 :
801 : struct name_to_copy_hasher : free_ptr_hash <name_to_copy_elt>
802 : {
803 : static inline hashval_t hash (const name_to_copy_elt *);
804 : static inline bool equal (const name_to_copy_elt *, const name_to_copy_elt *);
805 : };
806 :
807 : /* Equality and hash functions for hashtab code. */
808 :
809 : inline bool
810 5741 : name_to_copy_hasher::equal (const name_to_copy_elt *a, const name_to_copy_elt *b)
811 : {
812 5741 : return a->version == b->version;
813 : }
814 :
815 : inline hashval_t
816 5229 : name_to_copy_hasher::hash (const name_to_copy_elt *a)
817 : {
818 5229 : return (hashval_t) a->version;
819 : }
820 :
821 : typedef hash_table<name_to_copy_hasher> name_to_copy_table_type;
822 :
823 : /* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
824 : matrix. Rather than use floats, we simply keep a single DENOMINATOR that
825 : represents the denominator for every element in the matrix. */
826 : typedef struct lambda_trans_matrix_s
827 : {
828 : lambda_matrix matrix;
829 : int rowsize;
830 : int colsize;
831 : int denominator;
832 : } *lambda_trans_matrix;
833 : #define LTM_MATRIX(T) ((T)->matrix)
834 : #define LTM_ROWSIZE(T) ((T)->rowsize)
835 : #define LTM_COLSIZE(T) ((T)->colsize)
836 : #define LTM_DENOMINATOR(T) ((T)->denominator)
837 :
838 : /* Allocate a new transformation matrix. */
839 :
840 : static lambda_trans_matrix
841 775 : lambda_trans_matrix_new (int colsize, int rowsize,
842 : struct obstack * lambda_obstack)
843 : {
844 775 : lambda_trans_matrix ret;
845 :
846 1550 : ret = (lambda_trans_matrix)
847 775 : obstack_alloc (lambda_obstack, sizeof (struct lambda_trans_matrix_s));
848 775 : LTM_MATRIX (ret) = lambda_matrix_new (rowsize, colsize, lambda_obstack);
849 775 : LTM_ROWSIZE (ret) = rowsize;
850 775 : LTM_COLSIZE (ret) = colsize;
851 775 : LTM_DENOMINATOR (ret) = 1;
852 775 : return ret;
853 : }
854 :
855 : /* Multiply a vector VEC by a matrix MAT.
856 : MAT is an M*N matrix, and VEC is a vector with length N. The result
857 : is stored in DEST which must be a vector of length M. */
858 :
859 : static void
860 638 : lambda_matrix_vector_mult (lambda_matrix matrix, int m, int n,
861 : lambda_vector vec, lambda_vector dest)
862 : {
863 638 : int i, j;
864 :
865 638 : lambda_vector_clear (dest, m);
866 1276 : for (i = 0; i < m; i++)
867 1276 : for (j = 0; j < n; j++)
868 638 : dest[i] += matrix[i][j] * vec[j];
869 638 : }
870 :
871 : /* Return true if TRANS is a legal transformation matrix that respects
872 : the dependence vectors in DISTS and DIRS. The conservative answer
873 : is false.
874 :
875 : "Wolfe proves that a unimodular transformation represented by the
876 : matrix T is legal when applied to a loop nest with a set of
877 : lexicographically non-negative distance vectors RDG if and only if
878 : for each vector d in RDG, (T.d >= 0) is lexicographically positive.
879 : i.e.: if and only if it transforms the lexicographically positive
880 : distance vectors to lexicographically positive vectors. Note that
881 : a unimodular matrix must transform the zero vector (and only it) to
882 : the zero vector." S.Muchnick. */
883 :
884 : static bool
885 775 : lambda_transform_legal_p (lambda_trans_matrix trans,
886 : int nb_loops,
887 : vec<ddr_p> dependence_relations)
888 : {
889 775 : unsigned int i, j;
890 775 : lambda_vector distres;
891 775 : struct data_dependence_relation *ddr;
892 :
893 775 : gcc_assert (LTM_COLSIZE (trans) == nb_loops
894 : && LTM_ROWSIZE (trans) == nb_loops);
895 :
896 : /* When there are no dependences, the transformation is correct. */
897 1293 : if (dependence_relations.length () == 0)
898 : return true;
899 :
900 730 : ddr = dependence_relations[0];
901 730 : if (ddr == NULL)
902 : return true;
903 :
904 : /* When there is an unknown relation in the dependence_relations, we
905 : know that it is no worth looking at this loop nest: give up. */
906 730 : if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
907 : return false;
908 :
909 537 : distres = lambda_vector_new (nb_loops);
910 :
911 : /* For each distance vector in the dependence graph. */
912 3200 : FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
913 : {
914 : /* Don't care about relations for which we know that there is no
915 : dependence, nor about read-read (aka. output-dependences):
916 : these data accesses can happen in any order. */
917 2145 : if (DDR_ARE_DEPENDENT (ddr) == chrec_known
918 1254 : || (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr))))
919 1509 : continue;
920 :
921 : /* Conservatively answer: "this transformation is not valid". */
922 636 : if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
923 : return false;
924 :
925 : /* If the dependence could not be captured by a distance vector,
926 : conservatively answer that the transform is not valid. */
927 631 : if (DDR_NUM_DIST_VECTS (ddr) == 0)
928 : return false;
929 :
930 : /* Compute trans.dist_vect */
931 1255 : for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
932 : {
933 1276 : lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops,
934 638 : DDR_DIST_VECT (ddr, j), distres);
935 :
936 1476 : if (!lambda_vector_lexico_pos (distres, nb_loops))
937 : return false;
938 : }
939 : }
940 : return true;
941 : }
942 :
943 : /* Data dependency analysis. Returns true if the iterations of LOOP
944 : are independent on each other (that is, if we can execute them
945 : in parallel). */
946 :
947 : static bool
948 1168 : loop_parallel_p (class loop *loop, struct obstack * parloop_obstack)
949 : {
950 1168 : vec<ddr_p> dependence_relations;
951 1168 : vec<data_reference_p> datarefs;
952 1168 : lambda_trans_matrix trans;
953 1168 : bool ret = false;
954 :
955 1168 : if (dump_file && (dump_flags & TDF_DETAILS))
956 : {
957 237 : fprintf (dump_file, "Considering loop %d\n", loop->num);
958 237 : if (!loop->inner)
959 207 : fprintf (dump_file, "loop is innermost\n");
960 : else
961 30 : fprintf (dump_file, "loop NOT innermost\n");
962 : }
963 :
964 : /* Check for problems with dependences. If the loop can be reversed,
965 : the iterations are independent. */
966 1168 : auto_vec<loop_p, 3> loop_nest;
967 1168 : datarefs.create (10);
968 1168 : dependence_relations.create (100);
969 1168 : if (! compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs,
970 : &dependence_relations))
971 : {
972 393 : if (dump_file && (dump_flags & TDF_DETAILS))
973 14 : fprintf (dump_file, " FAILED: cannot analyze data dependencies\n");
974 393 : ret = false;
975 393 : goto end;
976 : }
977 775 : if (dump_file && (dump_flags & TDF_DETAILS))
978 223 : dump_data_dependence_relations (dump_file, dependence_relations);
979 :
980 775 : trans = lambda_trans_matrix_new (1, 1, parloop_obstack);
981 775 : LTM_MATRIX (trans)[0][0] = -1;
982 :
983 775 : if (lambda_transform_legal_p (trans, 1, dependence_relations))
984 : {
985 563 : ret = true;
986 563 : if (dump_file && (dump_flags & TDF_DETAILS))
987 206 : fprintf (dump_file, " SUCCESS: may be parallelized\n");
988 : }
989 212 : else if (dump_file && (dump_flags & TDF_DETAILS))
990 17 : fprintf (dump_file,
991 : " FAILED: data dependencies exist across iterations\n");
992 :
993 1168 : end:
994 1168 : free_dependence_relations (dependence_relations);
995 1168 : free_data_refs (datarefs);
996 :
997 1168 : return ret;
998 1168 : }
999 :
1000 : /* Return true when LOOP contains basic blocks marked with the
1001 : BB_IRREDUCIBLE_LOOP flag. */
1002 :
1003 : static inline bool
1004 1871 : loop_has_blocks_with_irreducible_flag (class loop *loop)
1005 : {
1006 1871 : unsigned i;
1007 1871 : basic_block *bbs = get_loop_body_in_dom_order (loop);
1008 1871 : bool res = true;
1009 :
1010 12572 : for (i = 0; i < loop->num_nodes; i++)
1011 8830 : if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
1012 0 : goto end;
1013 :
1014 : res = false;
1015 1871 : end:
1016 1871 : free (bbs);
1017 1871 : return res;
1018 : }
1019 :
1020 : /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
1021 : The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
1022 : to their addresses that can be reused. The address of OBJ is known to
1023 : be invariant in the whole function. Other needed statements are placed
1024 : right before GSI. */
1025 :
1026 : static tree
1027 239 : take_address_of (tree obj, tree type, edge entry,
1028 : int_tree_htab_type *decl_address, gimple_stmt_iterator *gsi)
1029 : {
1030 239 : int uid;
1031 239 : tree *var_p, name, addr;
1032 239 : gassign *stmt;
1033 239 : gimple_seq stmts;
1034 :
1035 : /* Since the address of OBJ is invariant, the trees may be shared.
1036 : Avoid rewriting unrelated parts of the code. */
1037 239 : obj = unshare_expr (obj);
1038 239 : for (var_p = &obj;
1039 240 : handled_component_p (*var_p);
1040 1 : var_p = &TREE_OPERAND (*var_p, 0))
1041 1 : continue;
1042 :
1043 : /* Canonicalize the access to base on a MEM_REF. */
1044 239 : if (DECL_P (*var_p))
1045 239 : *var_p = build_simple_mem_ref (build_fold_addr_expr (*var_p));
1046 :
1047 : /* Assign a canonical SSA name to the address of the base decl used
1048 : in the address and share it for all accesses and addresses based
1049 : on it. */
1050 239 : uid = DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));
1051 239 : int_tree_map elt;
1052 239 : elt.uid = uid;
1053 478 : int_tree_map *slot = decl_address->find_slot (elt,
1054 : gsi == NULL
1055 239 : ? NO_INSERT
1056 : : INSERT);
1057 239 : if (!slot || !slot->to)
1058 : {
1059 202 : if (gsi == NULL)
1060 : return NULL;
1061 202 : addr = TREE_OPERAND (*var_p, 0);
1062 202 : const char *obj_name
1063 202 : = get_name (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));
1064 202 : if (obj_name)
1065 202 : name = make_temp_ssa_name (TREE_TYPE (addr), NULL, obj_name);
1066 : else
1067 0 : name = make_ssa_name (TREE_TYPE (addr));
1068 202 : stmt = gimple_build_assign (name, addr);
1069 202 : gsi_insert_on_edge_immediate (entry, stmt);
1070 :
1071 202 : slot->uid = uid;
1072 202 : slot->to = name;
1073 202 : }
1074 : else
1075 : name = slot->to;
1076 :
1077 : /* Express the address in terms of the canonical SSA name. */
1078 239 : TREE_OPERAND (*var_p, 0) = name;
1079 239 : if (gsi == NULL)
1080 4 : return build_fold_addr_expr_with_type (obj, type);
1081 :
1082 235 : name = force_gimple_operand (build_addr (obj),
1083 : &stmts, true, NULL_TREE);
1084 235 : if (!gimple_seq_empty_p (stmts))
1085 1 : gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
1086 :
1087 235 : if (!useless_type_conversion_p (type, TREE_TYPE (name)))
1088 : {
1089 0 : name = force_gimple_operand (fold_convert (type, name), &stmts, true,
1090 : NULL_TREE);
1091 0 : if (!gimple_seq_empty_p (stmts))
1092 0 : gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
1093 : }
1094 :
1095 : return name;
1096 1 : }
1097 :
1098 : static tree
1099 230 : reduc_stmt_res (gimple *stmt)
1100 : {
1101 230 : return (gimple_code (stmt) == GIMPLE_PHI
1102 246 : ? gimple_phi_result (stmt)
1103 214 : : gimple_assign_lhs (stmt));
1104 : }
1105 :
1106 : /* Callback for htab_traverse. Create the initialization statement
1107 : for reduction described in SLOT, and place it at the preheader of
1108 : the loop described in DATA. */
1109 :
1110 : int
1111 68 : initialize_reductions (reduction_info **slot, class loop *loop)
1112 : {
1113 68 : tree init;
1114 68 : tree type, arg;
1115 68 : edge e;
1116 :
1117 68 : struct reduction_info *const reduc = *slot;
1118 :
1119 : /* Create initialization in preheader:
1120 : reduction_variable = initialization value of reduction. */
1121 :
1122 : /* In the phi node at the header, replace the argument coming
1123 : from the preheader with the reduction initialization value. */
1124 :
1125 : /* Initialize the reduction. */
1126 68 : type = TREE_TYPE (reduc->reduc_phi_name);
1127 68 : init = omp_reduction_init_op (gimple_location (reduc->reduc_stmt),
1128 : reduc->reduction_code, type);
1129 68 : reduc->init = init;
1130 :
1131 : /* Replace the argument representing the initialization value
1132 : with the initialization value for the reduction (neutral
1133 : element for the particular operation, e.g. 0 for PLUS_EXPR,
1134 : 1 for MULT_EXPR, etc).
1135 : Keep the old value in a new variable "reduction_initial",
1136 : that will be taken in consideration after the parallel
1137 : computing is done. */
1138 :
1139 68 : e = loop_preheader_edge (loop);
1140 68 : const auto phi = reduc->reduc_phi ();
1141 68 : arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
1142 : /* Create new variable to hold the initial value. */
1143 :
1144 68 : SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)), init);
1145 68 : reduc->initial_value = arg;
1146 68 : return 1;
1147 : }
1148 :
1149 : struct elv_data
1150 : {
1151 : struct walk_stmt_info info;
1152 : edge entry;
1153 : int_tree_htab_type *decl_address;
1154 : gimple_stmt_iterator *gsi;
1155 : bool changed;
1156 : bool reset;
1157 : };
1158 :
1159 : /* Eliminates references to local variables in *TP out of the single
1160 : entry single exit region starting at DTA->ENTRY.
1161 : DECL_ADDRESS contains addresses of the references that had their
1162 : address taken already. If the expression is changed, CHANGED is
1163 : set to true. Callback for walk_tree. */
1164 :
1165 : static tree
1166 5719 : eliminate_local_variables_1 (tree *tp, int *walk_subtrees, void *data)
1167 : {
1168 5719 : struct elv_data *const dta = (struct elv_data *) data;
1169 5719 : tree t = *tp, var, addr, addr_type, type, obj;
1170 :
1171 5719 : if (DECL_P (t))
1172 : {
1173 244 : *walk_subtrees = 0;
1174 :
1175 244 : if (!SSA_VAR_P (t) || DECL_EXTERNAL (t))
1176 : return NULL_TREE;
1177 :
1178 224 : type = TREE_TYPE (t);
1179 224 : addr_type = build_pointer_type (type);
1180 224 : addr = take_address_of (t, addr_type, dta->entry, dta->decl_address,
1181 : dta->gsi);
1182 224 : if (dta->gsi == NULL && addr == NULL_TREE)
1183 : {
1184 0 : dta->reset = true;
1185 0 : return NULL_TREE;
1186 : }
1187 :
1188 224 : *tp = build_simple_mem_ref (addr);
1189 :
1190 224 : dta->changed = true;
1191 224 : return NULL_TREE;
1192 : }
1193 :
1194 5475 : if (TREE_CODE (t) == ADDR_EXPR)
1195 : {
1196 : /* ADDR_EXPR may appear in two contexts:
1197 : -- as a gimple operand, when the address taken is a function invariant
1198 : -- as gimple rhs, when the resulting address in not a function
1199 : invariant
1200 : We do not need to do anything special in the latter case (the base of
1201 : the memory reference whose address is taken may be replaced in the
1202 : DECL_P case). The former case is more complicated, as we need to
1203 : ensure that the new address is still a gimple operand. Thus, it
1204 : is not sufficient to replace just the base of the memory reference --
1205 : we need to move the whole computation of the address out of the
1206 : loop. */
1207 20 : if (!is_gimple_val (t))
1208 : return NULL_TREE;
1209 :
1210 20 : *walk_subtrees = 0;
1211 20 : obj = TREE_OPERAND (t, 0);
1212 20 : var = get_base_address (obj);
1213 20 : if (!var || !SSA_VAR_P (var) || DECL_EXTERNAL (var))
1214 : return NULL_TREE;
1215 :
1216 15 : addr_type = TREE_TYPE (t);
1217 15 : addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address,
1218 : dta->gsi);
1219 15 : if (dta->gsi == NULL && addr == NULL_TREE)
1220 : {
1221 0 : dta->reset = true;
1222 0 : return NULL_TREE;
1223 : }
1224 15 : *tp = addr;
1225 :
1226 15 : dta->changed = true;
1227 15 : return NULL_TREE;
1228 : }
1229 :
1230 5455 : if (!EXPR_P (t))
1231 5023 : *walk_subtrees = 0;
1232 :
1233 : return NULL_TREE;
1234 : }
1235 :
1236 : /* Moves the references to local variables in STMT at *GSI out of the single
1237 : entry single exit region starting at ENTRY. DECL_ADDRESS contains
1238 : addresses of the references that had their address taken
1239 : already. */
1240 :
1241 : static void
1242 2012 : eliminate_local_variables_stmt (edge entry, gimple_stmt_iterator *gsi,
1243 : int_tree_htab_type *decl_address)
1244 : {
1245 2012 : struct elv_data dta;
1246 2012 : gimple *stmt = gsi_stmt (*gsi);
1247 :
1248 2012 : memset (&dta.info, '\0', sizeof (dta.info));
1249 2012 : dta.entry = entry;
1250 2012 : dta.decl_address = decl_address;
1251 2012 : dta.changed = false;
1252 2012 : dta.reset = false;
1253 :
1254 2012 : if (gimple_debug_bind_p (stmt))
1255 : {
1256 99 : dta.gsi = NULL;
1257 99 : walk_tree (gimple_debug_bind_get_value_ptr (stmt),
1258 : eliminate_local_variables_1, &dta.info, NULL);
1259 99 : if (dta.reset)
1260 : {
1261 0 : gimple_debug_bind_reset_value (stmt);
1262 0 : dta.changed = true;
1263 : }
1264 : }
1265 1913 : else if (gimple_clobber_p (stmt))
1266 : {
1267 0 : unlink_stmt_vdef (stmt);
1268 0 : stmt = gimple_build_nop ();
1269 0 : gsi_replace (gsi, stmt, false);
1270 0 : dta.changed = true;
1271 : }
1272 : else
1273 : {
1274 1913 : dta.gsi = gsi;
1275 1913 : walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
1276 : }
1277 :
1278 2012 : if (dta.changed)
1279 239 : update_stmt (stmt);
1280 2012 : }
1281 :
1282 : /* Eliminates the references to local variables from the single entry
1283 : single exit region between the ENTRY and EXIT edges.
1284 :
1285 : This includes:
1286 : 1) Taking address of a local variable -- these are moved out of the
1287 : region (and temporary variable is created to hold the address if
1288 : necessary).
1289 :
1290 : 2) Dereferencing a local variable -- these are replaced with indirect
1291 : references. */
1292 :
1293 : static void
1294 196 : eliminate_local_variables (edge entry, edge exit)
1295 : {
1296 196 : basic_block bb;
1297 196 : auto_vec<basic_block, 3> body;
1298 196 : unsigned i;
1299 196 : gimple_stmt_iterator gsi;
1300 196 : bool has_debug_stmt = false;
1301 196 : int_tree_htab_type decl_address (10);
1302 196 : basic_block entry_bb = entry->src;
1303 196 : basic_block exit_bb = exit->dest;
1304 :
1305 196 : gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
1306 :
1307 1293 : FOR_EACH_VEC_ELT (body, i, bb)
1308 901 : if (bb != entry_bb && bb != exit_bb)
1309 : {
1310 3519 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1311 2109 : if (is_gimple_debug (gsi_stmt (gsi)))
1312 : {
1313 196 : if (gimple_debug_bind_p (gsi_stmt (gsi)))
1314 2109 : has_debug_stmt = true;
1315 : }
1316 : else
1317 1913 : eliminate_local_variables_stmt (entry, &gsi, &decl_address);
1318 : }
1319 :
1320 196 : if (has_debug_stmt)
1321 101 : FOR_EACH_VEC_ELT (body, i, bb)
1322 82 : if (bb != entry_bb && bb != exit_bb)
1323 455 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1324 428 : if (gimple_debug_bind_p (gsi_stmt (gsi)))
1325 99 : eliminate_local_variables_stmt (entry, &gsi, &decl_address);
1326 196 : }
1327 :
1328 : /* Returns true if expression EXPR is not defined between ENTRY and
1329 : EXIT, i.e. if all its operands are defined outside of the region. */
1330 :
1331 : static bool
1332 3239 : expr_invariant_in_region_p (edge entry, edge exit, tree expr)
1333 : {
1334 3239 : basic_block entry_bb = entry->src;
1335 3239 : basic_block exit_bb = exit->dest;
1336 3239 : basic_block def_bb;
1337 :
1338 3239 : if (is_gimple_min_invariant (expr))
1339 : return true;
1340 :
1341 3239 : if (TREE_CODE (expr) == SSA_NAME)
1342 : {
1343 3239 : def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
1344 3239 : if (def_bb
1345 3134 : && dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)
1346 5993 : && !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))
1347 : return false;
1348 :
1349 485 : return true;
1350 : }
1351 :
1352 : return false;
1353 : }
1354 :
1355 : /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
1356 : The copies are stored to NAME_COPIES, if NAME was already duplicated,
1357 : its duplicate stored in NAME_COPIES is returned.
1358 :
1359 : Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
1360 : duplicated, storing the copies in DECL_COPIES. */
1361 :
1362 : static tree
1363 5297 : separate_decls_in_region_name (tree name, name_to_copy_table_type *name_copies,
1364 : int_tree_htab_type *decl_copies,
1365 : bool copy_name_p)
1366 : {
1367 5297 : tree copy, var, var_copy;
1368 5297 : unsigned idx, uid, nuid;
1369 5297 : struct int_tree_map ielt;
1370 5297 : struct name_to_copy_elt elt, *nelt;
1371 5297 : name_to_copy_elt **slot;
1372 5297 : int_tree_map *dslot;
1373 :
1374 5297 : if (TREE_CODE (name) != SSA_NAME)
1375 : return name;
1376 :
1377 5297 : idx = SSA_NAME_VERSION (name);
1378 5297 : elt.version = idx;
1379 10109 : slot = name_copies->find_slot_with_hash (&elt, idx,
1380 : copy_name_p ? INSERT : NO_INSERT);
1381 5297 : if (slot && *slot)
1382 60 : return (*slot)->new_name;
1383 :
1384 5237 : if (copy_name_p)
1385 : {
1386 425 : copy = duplicate_ssa_name (name, NULL);
1387 425 : nelt = XNEW (struct name_to_copy_elt);
1388 425 : nelt->version = idx;
1389 425 : nelt->new_name = copy;
1390 425 : nelt->field = NULL_TREE;
1391 425 : *slot = nelt;
1392 : }
1393 : else
1394 : {
1395 4812 : gcc_assert (!slot);
1396 : copy = name;
1397 : }
1398 :
1399 5237 : var = SSA_NAME_VAR (name);
1400 1539 : if (!var)
1401 : return copy;
1402 :
1403 1539 : uid = DECL_UID (var);
1404 1539 : ielt.uid = uid;
1405 1539 : dslot = decl_copies->find_slot_with_hash (ielt, uid, INSERT);
1406 1539 : if (!dslot->to)
1407 : {
1408 368 : var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
1409 368 : DECL_NOT_GIMPLE_REG_P (var_copy) = DECL_NOT_GIMPLE_REG_P (var);
1410 368 : dslot->uid = uid;
1411 368 : dslot->to = var_copy;
1412 :
1413 : /* Ensure that when we meet this decl next time, we won't duplicate
1414 : it again. */
1415 368 : nuid = DECL_UID (var_copy);
1416 368 : ielt.uid = nuid;
1417 368 : dslot = decl_copies->find_slot_with_hash (ielt, nuid, INSERT);
1418 368 : gcc_assert (!dslot->to);
1419 368 : dslot->uid = nuid;
1420 368 : dslot->to = var_copy;
1421 : }
1422 : else
1423 : var_copy = dslot->to;
1424 :
1425 1539 : replace_ssa_name_symbol (copy, var_copy);
1426 1539 : return copy;
1427 : }
1428 :
1429 : /* Finds the ssa names used in STMT that are defined outside the
1430 : region between ENTRY and EXIT and replaces such ssa names with
1431 : their duplicates. The duplicates are stored to NAME_COPIES. Base
1432 : decls of all ssa names used in STMT (including those defined in
1433 : LOOP) are replaced with the new temporary variables; the
1434 : replacement decls are stored in DECL_COPIES. */
1435 :
1436 : static void
1437 2749 : separate_decls_in_region_stmt (edge entry, edge exit, gimple *stmt,
1438 : name_to_copy_table_type *name_copies,
1439 : int_tree_htab_type *decl_copies)
1440 : {
1441 2749 : use_operand_p use;
1442 2749 : def_operand_p def;
1443 2749 : ssa_op_iter oi;
1444 2749 : tree name, copy;
1445 2749 : bool copy_name_p;
1446 :
1447 7556 : FOR_EACH_PHI_OR_STMT_DEF (def, stmt, oi, SSA_OP_DEF)
1448 : {
1449 2058 : name = DEF_FROM_PTR (def);
1450 2058 : gcc_assert (TREE_CODE (name) == SSA_NAME);
1451 2058 : copy = separate_decls_in_region_name (name, name_copies, decl_copies,
1452 : false);
1453 2058 : gcc_assert (copy == name);
1454 : }
1455 :
1456 9019 : FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
1457 : {
1458 3521 : name = USE_FROM_PTR (use);
1459 3521 : if (TREE_CODE (name) != SSA_NAME)
1460 282 : continue;
1461 :
1462 3239 : copy_name_p = expr_invariant_in_region_p (entry, exit, name);
1463 3239 : copy = separate_decls_in_region_name (name, name_copies, decl_copies,
1464 : copy_name_p);
1465 3239 : SET_USE (use, copy);
1466 : }
1467 2749 : }
1468 :
1469 : /* Finds the ssa names used in STMT that are defined outside the
1470 : region between ENTRY and EXIT and replaces such ssa names with
1471 : their duplicates. The duplicates are stored to NAME_COPIES. Base
1472 : decls of all ssa names used in STMT (including those defined in
1473 : LOOP) are replaced with the new temporary variables; the
1474 : replacement decls are stored in DECL_COPIES. */
1475 :
1476 : static bool
1477 196 : separate_decls_in_region_debug (gimple *stmt,
1478 : name_to_copy_table_type *name_copies,
1479 : int_tree_htab_type *decl_copies)
1480 : {
1481 196 : use_operand_p use;
1482 196 : ssa_op_iter oi;
1483 196 : tree var, name;
1484 196 : struct int_tree_map ielt;
1485 196 : struct name_to_copy_elt elt;
1486 196 : name_to_copy_elt **slot;
1487 196 : int_tree_map *dslot;
1488 :
1489 196 : if (gimple_debug_bind_p (stmt))
1490 99 : var = gimple_debug_bind_get_var (stmt);
1491 128 : else if (gimple_debug_source_bind_p (stmt))
1492 0 : var = gimple_debug_source_bind_get_var (stmt);
1493 : else
1494 : return true;
1495 99 : if (TREE_CODE (var) == DEBUG_EXPR_DECL || TREE_CODE (var) == LABEL_DECL)
1496 : return true;
1497 78 : gcc_assert (DECL_P (var) && SSA_VAR_P (var));
1498 78 : ielt.uid = DECL_UID (var);
1499 78 : dslot = decl_copies->find_slot_with_hash (ielt, ielt.uid, NO_INSERT);
1500 78 : if (!dslot)
1501 : return true;
1502 68 : if (gimple_debug_bind_p (stmt))
1503 68 : gimple_debug_bind_set_var (stmt, dslot->to);
1504 0 : else if (gimple_debug_source_bind_p (stmt))
1505 0 : gimple_debug_source_bind_set_var (stmt, dslot->to);
1506 :
1507 136 : FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
1508 : {
1509 56 : name = USE_FROM_PTR (use);
1510 56 : if (TREE_CODE (name) != SSA_NAME)
1511 0 : continue;
1512 :
1513 56 : elt.version = SSA_NAME_VERSION (name);
1514 56 : slot = name_copies->find_slot_with_hash (&elt, elt.version, NO_INSERT);
1515 56 : if (!slot)
1516 : {
1517 56 : gimple_debug_bind_reset_value (stmt);
1518 56 : update_stmt (stmt);
1519 56 : break;
1520 : }
1521 :
1522 0 : SET_USE (use, (*slot)->new_name);
1523 : }
1524 :
1525 : return false;
1526 : }
1527 :
1528 : /* Callback for htab_traverse. Adds a field corresponding to the reduction
1529 : specified in SLOT. The type is passed in DATA. */
1530 :
1531 : int
1532 54 : add_field_for_reduction (reduction_info **slot, tree type)
1533 : {
1534 :
1535 54 : struct reduction_info *const red = *slot;
1536 54 : tree var = reduc_stmt_res (red->reduc_stmt);
1537 108 : tree field = build_decl (gimple_location (red->reduc_stmt), FIELD_DECL,
1538 108 : SSA_NAME_IDENTIFIER (var), TREE_TYPE (var));
1539 :
1540 54 : insert_field_into_struct (type, field);
1541 :
1542 54 : red->field = field;
1543 :
1544 54 : return 1;
1545 : }
1546 :
1547 : /* Callback for htab_traverse. Adds a field corresponding to a ssa name
1548 : described in SLOT. The type is passed in DATA. */
1549 :
1550 : int
1551 425 : add_field_for_name (name_to_copy_elt **slot, tree type)
1552 : {
1553 425 : struct name_to_copy_elt *const elt = *slot;
1554 425 : tree name = ssa_name (elt->version);
1555 850 : tree field = build_decl (UNKNOWN_LOCATION,
1556 425 : FIELD_DECL, SSA_NAME_IDENTIFIER (name),
1557 425 : TREE_TYPE (name));
1558 :
1559 425 : insert_field_into_struct (type, field);
1560 425 : elt->field = field;
1561 :
1562 425 : return 1;
1563 : }
1564 :
1565 : /* Callback for htab_traverse. A local result is the intermediate result
1566 : computed by a single
1567 : thread, or the initial value in case no iteration was executed.
1568 : This function creates a phi node reflecting these values.
1569 : The phi's result will be stored in NEW_PHI field of the
1570 : reduction's data structure. */
1571 :
1572 : int
1573 68 : create_phi_for_local_result (reduction_info **slot, class loop *loop)
1574 : {
1575 68 : struct reduction_info *const reduc = *slot;
1576 68 : edge e;
1577 68 : gphi *new_phi;
1578 68 : basic_block store_bb, continue_bb;
1579 68 : tree local_res;
1580 68 : location_t locus;
1581 :
1582 : /* STORE_BB is the block where the phi
1583 : should be stored. It is the destination of the loop exit.
1584 : (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
1585 68 : continue_bb = single_pred (loop->latch);
1586 68 : store_bb = FALLTHRU_EDGE (continue_bb)->dest;
1587 :
1588 : /* STORE_BB has two predecessors. One coming from the loop
1589 : (the reduction's result is computed at the loop),
1590 : and another coming from a block preceding the loop,
1591 : when no iterations
1592 : are executed (the initial value should be taken). */
1593 68 : if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (continue_bb))
1594 68 : e = EDGE_PRED (store_bb, 1);
1595 : else
1596 : e = EDGE_PRED (store_bb, 0);
1597 68 : tree lhs = reduc_stmt_res (reduc->reduc_stmt);
1598 68 : local_res = copy_ssa_name (lhs);
1599 68 : locus = gimple_location (reduc->reduc_stmt);
1600 68 : new_phi = create_phi_node (local_res, store_bb);
1601 68 : add_phi_arg (new_phi, reduc->init, e, locus);
1602 68 : add_phi_arg (new_phi, lhs, FALLTHRU_EDGE (continue_bb), locus);
1603 68 : reduc->new_phi = new_phi;
1604 :
1605 68 : return 1;
1606 : }
1607 :
1608 : struct clsn_data
1609 : {
1610 : tree store;
1611 : tree load;
1612 :
1613 : basic_block store_bb;
1614 : basic_block load_bb;
1615 : };
1616 :
1617 : /* Callback for htab_traverse. Create an atomic instruction for the
1618 : reduction described in SLOT.
1619 : DATA annotates the place in memory the atomic operation relates to,
1620 : and the basic block it needs to be generated in. */
1621 :
1622 : int
1623 68 : create_call_for_reduction_1 (reduction_info **slot, struct clsn_data *clsn_data)
1624 : {
1625 68 : struct reduction_info *const reduc = *slot;
1626 68 : gimple_stmt_iterator gsi;
1627 68 : tree type = TREE_TYPE (reduc->reduc_phi_name);
1628 68 : tree load_struct;
1629 68 : basic_block bb;
1630 68 : basic_block new_bb;
1631 68 : edge e;
1632 68 : tree t, addr, ref, x;
1633 68 : tree tmp_load, name;
1634 68 : gimple *load;
1635 :
1636 68 : if (reduc->reduc_addr == NULL_TREE)
1637 : {
1638 54 : load_struct = build_simple_mem_ref (clsn_data->load);
1639 54 : t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
1640 :
1641 54 : addr = build_addr (t);
1642 : }
1643 : else
1644 : {
1645 : /* Set the address for the atomic store. */
1646 14 : addr = reduc->reduc_addr;
1647 :
1648 : /* Remove the non-atomic store '*addr = sum'. */
1649 14 : tree res = PHI_RESULT (reduc->keep_res);
1650 14 : use_operand_p use_p;
1651 14 : gimple *stmt;
1652 14 : bool single_use_p = single_imm_use (res, &use_p, &stmt);
1653 14 : gcc_assert (single_use_p);
1654 42 : replace_uses_by (gimple_vdef (stmt),
1655 : gimple_vuse (stmt));
1656 14 : gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1657 14 : gsi_remove (&gsi, true);
1658 : }
1659 :
1660 : /* Create phi node. */
1661 68 : bb = clsn_data->load_bb;
1662 :
1663 68 : gsi = gsi_last_bb (bb);
1664 68 : e = split_block (bb, gsi_stmt (gsi));
1665 68 : new_bb = e->dest;
1666 :
1667 68 : tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)));
1668 68 : tmp_load = make_ssa_name (tmp_load);
1669 68 : load = gimple_build_omp_atomic_load (tmp_load, addr,
1670 : OMP_MEMORY_ORDER_RELAXED);
1671 68 : SSA_NAME_DEF_STMT (tmp_load) = load;
1672 68 : gsi = gsi_start_bb (new_bb);
1673 68 : gsi_insert_after (&gsi, load, GSI_NEW_STMT);
1674 :
1675 68 : e = split_block (new_bb, load);
1676 68 : new_bb = e->dest;
1677 68 : gsi = gsi_start_bb (new_bb);
1678 68 : ref = tmp_load;
1679 68 : x = fold_build2 (reduc->reduction_code,
1680 : TREE_TYPE (PHI_RESULT (reduc->new_phi)), ref,
1681 : PHI_RESULT (reduc->new_phi));
1682 :
1683 68 : name = force_gimple_operand_gsi (&gsi, x, true, NULL_TREE, true,
1684 : GSI_CONTINUE_LINKING);
1685 :
1686 68 : gimple *store = gimple_build_omp_atomic_store (name,
1687 : OMP_MEMORY_ORDER_RELAXED);
1688 68 : gsi_insert_after (&gsi, store, GSI_NEW_STMT);
1689 68 : return 1;
1690 : }
1691 :
1692 : /* Create the atomic operation at the join point of the threads.
1693 : REDUCTION_LIST describes the reductions in the LOOP.
1694 : LD_ST_DATA describes the shared data structure where
1695 : shared data is stored in and loaded from. */
1696 : static void
1697 66 : create_call_for_reduction (class loop *loop,
1698 : reduction_info_table_type *reduction_list,
1699 : struct clsn_data *ld_st_data)
1700 : {
1701 134 : reduction_list->traverse <class loop *, create_phi_for_local_result> (loop);
1702 : /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
1703 66 : basic_block continue_bb = single_pred (loop->latch);
1704 66 : ld_st_data->load_bb = FALLTHRU_EDGE (continue_bb)->dest;
1705 66 : reduction_list
1706 134 : ->traverse <struct clsn_data *, create_call_for_reduction_1> (ld_st_data);
1707 66 : }
1708 :
1709 : /* Callback for htab_traverse. Loads the final reduction value at the
1710 : join point of all threads, and inserts it in the right place. */
1711 :
1712 : int
1713 54 : create_loads_for_reductions (reduction_info **slot, struct clsn_data *clsn_data)
1714 : {
1715 54 : struct reduction_info *const red = *slot;
1716 54 : gimple *stmt;
1717 54 : gimple_stmt_iterator gsi;
1718 54 : tree type = TREE_TYPE (reduc_stmt_res (red->reduc_stmt));
1719 54 : tree load_struct;
1720 54 : tree name;
1721 54 : tree x;
1722 :
1723 : /* If there's no exit phi, the result of the reduction is unused. */
1724 54 : if (red->keep_res == NULL)
1725 : return 1;
1726 :
1727 53 : gsi = gsi_after_labels (clsn_data->load_bb);
1728 53 : load_struct = build_simple_mem_ref (clsn_data->load);
1729 53 : load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
1730 : NULL_TREE);
1731 :
1732 53 : x = load_struct;
1733 53 : name = PHI_RESULT (red->keep_res);
1734 53 : stmt = gimple_build_assign (name, x);
1735 :
1736 53 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1737 :
1738 53 : for (gsi = gsi_start_phis (gimple_bb (red->keep_res));
1739 56 : !gsi_end_p (gsi); gsi_next (&gsi))
1740 56 : if (gsi_stmt (gsi) == red->keep_res)
1741 : {
1742 53 : remove_phi_node (&gsi, false);
1743 53 : return 1;
1744 : }
1745 0 : gcc_unreachable ();
1746 : }
1747 :
1748 : /* Load the reduction result that was stored in LD_ST_DATA.
1749 : REDUCTION_LIST describes the list of reductions that the
1750 : loads should be generated for. */
1751 : static void
1752 52 : create_final_loads_for_reduction (reduction_info_table_type *reduction_list,
1753 : struct clsn_data *ld_st_data)
1754 : {
1755 52 : gimple_stmt_iterator gsi;
1756 52 : tree t;
1757 52 : gimple *stmt;
1758 :
1759 52 : gsi = gsi_after_labels (ld_st_data->load_bb);
1760 52 : t = build_fold_addr_expr (ld_st_data->store);
1761 52 : stmt = gimple_build_assign (ld_st_data->load, t);
1762 :
1763 52 : gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1764 :
1765 52 : reduction_list
1766 106 : ->traverse <struct clsn_data *, create_loads_for_reductions> (ld_st_data);
1767 :
1768 52 : }
1769 :
1770 : /* Callback for htab_traverse. Store the neutral value for the
1771 : particular reduction's operation, e.g. 0 for PLUS_EXPR,
1772 : 1 for MULT_EXPR, etc. into the reduction field.
1773 : The reduction is specified in SLOT. The store information is
1774 : passed in DATA. */
1775 :
1776 : int
1777 54 : create_stores_for_reduction (reduction_info **slot, struct clsn_data *clsn_data)
1778 : {
1779 54 : struct reduction_info *const red = *slot;
1780 54 : tree t;
1781 54 : gimple *stmt;
1782 54 : gimple_stmt_iterator gsi;
1783 54 : tree type = TREE_TYPE (reduc_stmt_res (red->reduc_stmt));
1784 :
1785 54 : gsi = gsi_last_bb (clsn_data->store_bb);
1786 54 : t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE);
1787 54 : stmt = gimple_build_assign (t, red->initial_value);
1788 54 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1789 :
1790 54 : return 1;
1791 : }
1792 :
1793 : /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
1794 : store to a field of STORE in STORE_BB for the ssa name and its duplicate
1795 : specified in SLOT. */
1796 :
1797 : int
1798 425 : create_loads_and_stores_for_name (name_to_copy_elt **slot,
1799 : struct clsn_data *clsn_data)
1800 : {
1801 425 : struct name_to_copy_elt *const elt = *slot;
1802 425 : tree t;
1803 425 : gimple *stmt;
1804 425 : gimple_stmt_iterator gsi;
1805 425 : tree type = TREE_TYPE (elt->new_name);
1806 425 : tree load_struct;
1807 :
1808 425 : gsi = gsi_last_bb (clsn_data->store_bb);
1809 425 : t = build3 (COMPONENT_REF, type, clsn_data->store, elt->field, NULL_TREE);
1810 425 : stmt = gimple_build_assign (t, ssa_name (elt->version));
1811 425 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1812 :
1813 425 : gsi = gsi_last_bb (clsn_data->load_bb);
1814 425 : load_struct = build_simple_mem_ref (clsn_data->load);
1815 425 : t = build3 (COMPONENT_REF, type, load_struct, elt->field, NULL_TREE);
1816 425 : stmt = gimple_build_assign (elt->new_name, t);
1817 425 : gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1818 :
1819 425 : return 1;
1820 : }
1821 :
1822 : /* Moves all the variables used in LOOP and defined outside of it (including
1823 : the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1824 : name) to a structure created for this purpose. The code
1825 :
1826 : while (1)
1827 : {
1828 : use (a);
1829 : use (b);
1830 : }
1831 :
1832 : is transformed this way:
1833 :
1834 : bb0:
1835 : old.a = a;
1836 : old.b = b;
1837 :
1838 : bb1:
1839 : a' = new->a;
1840 : b' = new->b;
1841 : while (1)
1842 : {
1843 : use (a');
1844 : use (b');
1845 : }
1846 :
1847 : `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1848 : pointer `new' is intentionally not initialized (the loop will be split to a
1849 : separate function later, and `new' will be initialized from its arguments).
1850 : LD_ST_DATA holds information about the shared data structure used to pass
1851 : information among the threads. It is initialized here, and
1852 : gen_parallel_loop will pass it to create_call_for_reduction that
1853 : needs this information. REDUCTION_LIST describes the reductions
1854 : in LOOP. */
1855 :
1856 : static void
1857 196 : separate_decls_in_region (edge entry, edge exit,
1858 : reduction_info_table_type *reduction_list,
1859 : tree *arg_struct, tree *new_arg_struct,
1860 : struct clsn_data *ld_st_data)
1861 :
1862 : {
1863 196 : basic_block bb1 = split_edge (entry);
1864 196 : basic_block bb0 = single_pred (bb1);
1865 196 : name_to_copy_table_type name_copies (10);
1866 196 : int_tree_htab_type decl_copies (10);
1867 196 : unsigned i;
1868 196 : tree type, type_name, nvar;
1869 196 : gimple_stmt_iterator gsi;
1870 196 : struct clsn_data clsn_data;
1871 196 : auto_vec<basic_block, 3> body;
1872 196 : basic_block bb;
1873 196 : basic_block entry_bb = bb1;
1874 196 : basic_block exit_bb = exit->dest;
1875 196 : bool has_debug_stmt = false;
1876 :
1877 196 : entry = single_succ_edge (entry_bb);
1878 196 : gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
1879 :
1880 1097 : FOR_EACH_VEC_ELT (body, i, bb)
1881 : {
1882 901 : if (bb != entry_bb && bb != exit_bb)
1883 : {
1884 1540 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1885 835 : separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
1886 : &name_copies, &decl_copies);
1887 :
1888 3520 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1889 : {
1890 2110 : gimple *stmt = gsi_stmt (gsi);
1891 :
1892 2110 : if (is_gimple_debug (stmt))
1893 : has_debug_stmt = true;
1894 : else
1895 1914 : separate_decls_in_region_stmt (entry, exit, stmt,
1896 : &name_copies, &decl_copies);
1897 : }
1898 : }
1899 : }
1900 :
1901 : /* Now process debug bind stmts. We must not create decls while
1902 : processing debug stmts, so we defer their processing so as to
1903 : make sure we will have debug info for as many variables as
1904 : possible (all of those that were dealt with in the loop above),
1905 : and discard those for which we know there's nothing we can
1906 : do. */
1907 196 : if (has_debug_stmt)
1908 141 : FOR_EACH_VEC_ELT (body, i, bb)
1909 114 : if (bb != entry_bb && bb != exit_bb)
1910 : {
1911 543 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
1912 : {
1913 369 : gimple *stmt = gsi_stmt (gsi);
1914 :
1915 369 : if (is_gimple_debug (stmt))
1916 : {
1917 196 : if (separate_decls_in_region_debug (stmt, &name_copies,
1918 : &decl_copies))
1919 : {
1920 128 : gsi_remove (&gsi, true);
1921 128 : continue;
1922 : }
1923 : }
1924 :
1925 241 : gsi_next (&gsi);
1926 : }
1927 : }
1928 :
1929 196 : if (name_copies.is_empty () && reduction_list->is_empty ())
1930 : {
1931 : /* It may happen that there is nothing to copy (if there are only
1932 : loop carried and external variables in the loop). */
1933 12 : *arg_struct = NULL;
1934 12 : *new_arg_struct = NULL;
1935 : }
1936 : else
1937 : {
1938 : /* Create the type for the structure to store the ssa names to. */
1939 184 : type = lang_hooks.types.make_type (RECORD_TYPE);
1940 184 : type_name = build_decl (UNKNOWN_LOCATION,
1941 : TYPE_DECL, create_tmp_var_name (".paral_data"),
1942 : type);
1943 184 : TYPE_NAME (type) = type_name;
1944 :
1945 609 : name_copies.traverse <tree, add_field_for_name> (type);
1946 184 : if (reduction_list && !reduction_list->is_empty ())
1947 : {
1948 : /* Create the fields for reductions. */
1949 106 : reduction_list->traverse <tree, add_field_for_reduction> (type);
1950 : }
1951 184 : layout_type (type);
1952 :
1953 : /* Create the loads and stores. */
1954 184 : *arg_struct = create_tmp_var (type, ".paral_data_store");
1955 184 : nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load");
1956 184 : *new_arg_struct = make_ssa_name (nvar);
1957 :
1958 184 : ld_st_data->store = *arg_struct;
1959 184 : ld_st_data->load = *new_arg_struct;
1960 184 : ld_st_data->store_bb = bb0;
1961 184 : ld_st_data->load_bb = bb1;
1962 :
1963 184 : name_copies
1964 : .traverse <struct clsn_data *, create_loads_and_stores_for_name>
1965 609 : (ld_st_data);
1966 :
1967 : /* Load the calculation from memory (after the join of the threads). */
1968 :
1969 184 : if (reduction_list && !reduction_list->is_empty ())
1970 : {
1971 52 : reduction_list
1972 : ->traverse <struct clsn_data *, create_stores_for_reduction>
1973 106 : (ld_st_data);
1974 52 : clsn_data.load = make_ssa_name (nvar);
1975 52 : clsn_data.load_bb = exit->dest;
1976 52 : clsn_data.store = ld_st_data->store;
1977 52 : create_final_loads_for_reduction (reduction_list, &clsn_data);
1978 : }
1979 : }
1980 196 : }
1981 :
1982 : /* Returns true if FN was created to run in parallel. */
1983 :
1984 : bool
1985 1213 : parallelized_function_p (tree fndecl)
1986 : {
1987 1213 : cgraph_node *node = cgraph_node::get (fndecl);
1988 1213 : gcc_assert (node != NULL);
1989 1213 : return node->parallelized_function;
1990 : }
1991 :
1992 : /* Creates and returns an empty function that will receive the body of
1993 : a parallelized loop. */
1994 :
1995 : static tree
1996 582 : create_loop_fn (location_t loc)
1997 : {
1998 582 : char buf[100];
1999 582 : char *tname;
2000 582 : tree decl, type, name, t;
2001 582 : struct function *act_cfun = cfun;
2002 582 : static unsigned loopfn_num;
2003 :
2004 582 : loc = LOCATION_LOCUS (loc);
2005 582 : snprintf (buf, 100, "%s.$loopfn", current_function_name ());
2006 582 : ASM_FORMAT_PRIVATE_NAME (tname, buf, loopfn_num++);
2007 582 : clean_symbol_name (tname);
2008 582 : name = get_identifier (tname);
2009 582 : type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
2010 :
2011 582 : decl = build_decl (loc, FUNCTION_DECL, name, type);
2012 582 : TREE_STATIC (decl) = 1;
2013 582 : TREE_USED (decl) = 1;
2014 582 : DECL_ARTIFICIAL (decl) = 1;
2015 582 : DECL_IGNORED_P (decl) = 0;
2016 582 : TREE_PUBLIC (decl) = 0;
2017 582 : DECL_UNINLINABLE (decl) = 1;
2018 582 : DECL_EXTERNAL (decl) = 0;
2019 582 : DECL_CONTEXT (decl) = NULL_TREE;
2020 582 : DECL_INITIAL (decl) = make_node (BLOCK);
2021 582 : BLOCK_SUPERCONTEXT (DECL_INITIAL (decl)) = decl;
2022 :
2023 582 : t = build_decl (loc, RESULT_DECL, NULL_TREE, void_type_node);
2024 582 : DECL_ARTIFICIAL (t) = 1;
2025 582 : DECL_IGNORED_P (t) = 1;
2026 582 : DECL_RESULT (decl) = t;
2027 :
2028 582 : t = build_decl (loc, PARM_DECL, get_identifier (".paral_data_param"),
2029 : ptr_type_node);
2030 582 : DECL_ARTIFICIAL (t) = 1;
2031 582 : DECL_ARG_TYPE (t) = ptr_type_node;
2032 582 : DECL_CONTEXT (t) = decl;
2033 582 : TREE_USED (t) = 1;
2034 582 : DECL_ARGUMENTS (decl) = t;
2035 1164 : DECL_FUNCTION_SPECIFIC_TARGET (decl)
2036 582 : = DECL_FUNCTION_SPECIFIC_TARGET (act_cfun->decl);
2037 1164 : DECL_FUNCTION_SPECIFIC_OPTIMIZATION (decl)
2038 582 : = DECL_FUNCTION_SPECIFIC_OPTIMIZATION (act_cfun->decl);
2039 :
2040 :
2041 582 : allocate_struct_function (decl, false);
2042 :
2043 : /* The call to allocate_struct_function clobbers CFUN, so we need to restore
2044 : it. */
2045 582 : set_cfun (act_cfun);
2046 :
2047 582 : return decl;
2048 : }
2049 :
2050 : /* Replace uses of NAME by VAL in block BB. */
2051 :
2052 : static void
2053 2210 : replace_uses_in_bb_by (tree name, tree val, basic_block bb)
2054 : {
2055 2210 : gimple *use_stmt;
2056 2210 : imm_use_iterator imm_iter;
2057 :
2058 7937 : FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, name)
2059 : {
2060 3517 : if (gimple_bb (use_stmt) != bb)
2061 2414 : continue;
2062 :
2063 1103 : use_operand_p use_p;
2064 4412 : FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
2065 1103 : SET_USE (use_p, val);
2066 2210 : }
2067 2210 : }
2068 :
2069 : /* Do transformation from:
2070 :
2071 : <bb preheader>:
2072 : ...
2073 : goto <bb header>
2074 :
2075 : <bb header>:
2076 : ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
2077 : sum_a = PHI <sum_init (preheader), sum_b (latch)>
2078 : ...
2079 : use (ivtmp_a)
2080 : ...
2081 : sum_b = sum_a + sum_update
2082 : ...
2083 : if (ivtmp_a < n)
2084 : goto <bb latch>;
2085 : else
2086 : goto <bb exit>;
2087 :
2088 : <bb latch>:
2089 : ivtmp_b = ivtmp_a + 1;
2090 : goto <bb header>
2091 :
2092 : <bb exit>:
2093 : sum_z = PHI <sum_b (cond[1]), ...>
2094 :
2095 : [1] Where <bb cond> is single_pred (bb latch); In the simplest case,
2096 : that's <bb header>.
2097 :
2098 : to:
2099 :
2100 : <bb preheader>:
2101 : ...
2102 : goto <bb newheader>
2103 :
2104 : <bb header>:
2105 : ivtmp_a = PHI <ivtmp_c (latch)>
2106 : sum_a = PHI <sum_c (latch)>
2107 : ...
2108 : use (ivtmp_a)
2109 : ...
2110 : sum_b = sum_a + sum_update
2111 : ...
2112 : goto <bb latch>;
2113 :
2114 : <bb newheader>:
2115 : ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
2116 : sum_c = PHI <sum_init (preheader), sum_b (latch)>
2117 : if (ivtmp_c < n + 1)
2118 : goto <bb header>;
2119 : else
2120 : goto <bb newexit>;
2121 :
2122 : <bb latch>:
2123 : ivtmp_b = ivtmp_a + 1;
2124 : goto <bb newheader>
2125 :
2126 : <bb newexit>:
2127 : sum_y = PHI <sum_c (newheader)>
2128 :
2129 : <bb exit>:
2130 : sum_z = PHI <sum_y (newexit), ...>
2131 :
2132 :
2133 : In unified diff format:
2134 :
2135 : <bb preheader>:
2136 : ...
2137 : - goto <bb header>
2138 : + goto <bb newheader>
2139 :
2140 : <bb header>:
2141 : - ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
2142 : - sum_a = PHI <sum_init (preheader), sum_b (latch)>
2143 : + ivtmp_a = PHI <ivtmp_c (latch)>
2144 : + sum_a = PHI <sum_c (latch)>
2145 : ...
2146 : use (ivtmp_a)
2147 : ...
2148 : sum_b = sum_a + sum_update
2149 : ...
2150 : - if (ivtmp_a < n)
2151 : - goto <bb latch>;
2152 : + goto <bb latch>;
2153 : +
2154 : + <bb newheader>:
2155 : + ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
2156 : + sum_c = PHI <sum_init (preheader), sum_b (latch)>
2157 : + if (ivtmp_c < n + 1)
2158 : + goto <bb header>;
2159 : else
2160 : goto <bb exit>;
2161 :
2162 : <bb latch>:
2163 : ivtmp_b = ivtmp_a + 1;
2164 : - goto <bb header>
2165 : + goto <bb newheader>
2166 :
2167 : + <bb newexit>:
2168 : + sum_y = PHI <sum_c (newheader)>
2169 :
2170 : <bb exit>:
2171 : - sum_z = PHI <sum_b (cond[1]), ...>
2172 : + sum_z = PHI <sum_y (newexit), ...>
2173 :
2174 : Note: the example does not show any virtual phis, but these are handled more
2175 : or less as reductions.
2176 :
2177 :
2178 : Moves the exit condition of LOOP to the beginning of its header.
2179 : REDUCTION_LIST describes the reductions in LOOP. BOUND is the new loop
2180 : bound. */
2181 :
2182 : static void
2183 558 : transform_to_exit_first_loop_alt (class loop *loop,
2184 : reduction_info_table_type *reduction_list,
2185 : tree bound)
2186 : {
2187 558 : basic_block header = loop->header;
2188 558 : basic_block latch = loop->latch;
2189 558 : edge exit = single_dom_exit (loop);
2190 558 : basic_block exit_block = exit->dest;
2191 1116 : gcond *cond_stmt = as_a <gcond *> (*gsi_last_bb (exit->src));
2192 558 : tree control = gimple_cond_lhs (cond_stmt);
2193 558 : edge e;
2194 :
2195 : /* Create the new_header block. */
2196 558 : basic_block new_header = split_block_before_cond_jump (exit->src);
2197 558 : edge edge_at_split = single_pred_edge (new_header);
2198 :
2199 : /* Redirect entry edge to new_header. */
2200 558 : edge entry = loop_preheader_edge (loop);
2201 558 : e = redirect_edge_and_branch (entry, new_header);
2202 558 : gcc_assert (e == entry);
2203 :
2204 : /* Redirect post_inc_edge to new_header. */
2205 558 : edge post_inc_edge = single_succ_edge (latch);
2206 558 : e = redirect_edge_and_branch (post_inc_edge, new_header);
2207 558 : gcc_assert (e == post_inc_edge);
2208 :
2209 : /* Redirect post_cond_edge to header. */
2210 558 : edge post_cond_edge = single_pred_edge (latch);
2211 558 : e = redirect_edge_and_branch (post_cond_edge, header);
2212 558 : gcc_assert (e == post_cond_edge);
2213 :
2214 : /* Redirect edge_at_split to latch. */
2215 558 : e = redirect_edge_and_branch (edge_at_split, latch);
2216 558 : gcc_assert (e == edge_at_split);
2217 :
2218 : /* Set the new loop bound. */
2219 558 : gimple_cond_set_rhs (cond_stmt, bound);
2220 558 : update_stmt (cond_stmt);
2221 :
2222 : /* Repair the ssa. */
2223 558 : vec<edge_var_map> *v = redirect_edge_var_map_vector (post_inc_edge);
2224 558 : edge_var_map *vm;
2225 558 : gphi_iterator gsi;
2226 558 : int i;
2227 558 : for (gsi = gsi_start_phis (header), i = 0;
2228 1663 : !gsi_end_p (gsi) && v->iterate (i, &vm);
2229 1105 : gsi_next (&gsi), i++)
2230 : {
2231 1105 : gphi *phi = gsi.phi ();
2232 1105 : tree res_a = PHI_RESULT (phi);
2233 :
2234 : /* Create new phi. */
2235 1105 : tree res_c = copy_ssa_name (res_a, phi);
2236 1105 : gphi *nphi = create_phi_node (res_c, new_header);
2237 :
2238 : /* Replace ivtmp_a with ivtmp_c in condition 'if (ivtmp_a < n)'. */
2239 1105 : replace_uses_in_bb_by (res_a, res_c, new_header);
2240 :
2241 : /* Replace ivtmp/sum_b with ivtmp/sum_c in header phi. */
2242 1105 : add_phi_arg (phi, res_c, post_cond_edge, UNKNOWN_LOCATION);
2243 :
2244 : /* Replace sum_b with sum_c in exit phi. */
2245 1105 : tree res_b = redirect_edge_var_map_def (vm);
2246 1105 : replace_uses_in_bb_by (res_b, res_c, exit_block);
2247 :
2248 1105 : struct reduction_info *red = reduction_phi (reduction_list, phi);
2249 2210 : gcc_assert (virtual_operand_p (res_a)
2250 : || res_a == control
2251 : || red != NULL);
2252 :
2253 1105 : if (red)
2254 : {
2255 : /* Register the new reduction phi. */
2256 67 : red->reduc_phi_name = res_c;
2257 67 : gcc_checking_assert (red->reduc_phi () == nphi);
2258 67 : gimple_set_uid (nphi, red->reduc_version);
2259 : }
2260 : }
2261 558 : gcc_assert (gsi_end_p (gsi) && !v->iterate (i, &vm));
2262 :
2263 : /* Set the preheader argument of the new phis to ivtmp/sum_init. */
2264 558 : flush_pending_stmts (entry);
2265 :
2266 : /* Set the latch arguments of the new phis to ivtmp/sum_b. */
2267 558 : flush_pending_stmts (post_inc_edge);
2268 :
2269 :
2270 558 : basic_block new_exit_block = NULL;
2271 558 : if (!single_pred_p (exit->dest))
2272 : {
2273 : /* Create a new empty exit block, inbetween the new loop header and the
2274 : old exit block. The function separate_decls_in_region needs this block
2275 : to insert code that is active on loop exit, but not any other path. */
2276 172 : new_exit_block = split_edge (exit);
2277 : }
2278 :
2279 : /* Insert and register the reduction exit phis. */
2280 558 : for (gphi_iterator gsi = gsi_start_phis (exit_block);
2281 1103 : !gsi_end_p (gsi);
2282 545 : gsi_next (&gsi))
2283 : {
2284 545 : gphi *phi = gsi.phi ();
2285 545 : gphi *nphi = NULL;
2286 545 : tree res_z = PHI_RESULT (phi);
2287 545 : tree res_c;
2288 :
2289 545 : if (new_exit_block != NULL)
2290 : {
2291 : /* Now that we have a new exit block, duplicate the phi of the old
2292 : exit block in the new exit block to preserve loop-closed ssa. */
2293 155 : edge succ_new_exit_block = single_succ_edge (new_exit_block);
2294 155 : edge pred_new_exit_block = single_pred_edge (new_exit_block);
2295 155 : tree res_y = copy_ssa_name (res_z, phi);
2296 155 : nphi = create_phi_node (res_y, new_exit_block);
2297 155 : res_c = PHI_ARG_DEF_FROM_EDGE (phi, succ_new_exit_block);
2298 155 : add_phi_arg (nphi, res_c, pred_new_exit_block, UNKNOWN_LOCATION);
2299 155 : add_phi_arg (phi, res_y, succ_new_exit_block, UNKNOWN_LOCATION);
2300 : }
2301 : else
2302 390 : res_c = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2303 :
2304 1090 : if (virtual_operand_p (res_z))
2305 479 : continue;
2306 :
2307 66 : gimple *reduc_phi = SSA_NAME_DEF_STMT (res_c);
2308 66 : struct reduction_info *red = reduction_phi (reduction_list, reduc_phi);
2309 66 : if (red != NULL)
2310 66 : red->keep_res = (nphi != NULL
2311 66 : ? nphi
2312 : : phi);
2313 : }
2314 :
2315 : /* We're going to cancel the loop at the end of gen_parallel_loop, but until
2316 : then we're still using some fields, so only bother about fields that are
2317 : still used: header and latch.
2318 : The loop has a new header bb, so we update it. The latch bb stays the
2319 : same. */
2320 558 : loop->header = new_header;
2321 :
2322 : /* Recalculate dominance info. */
2323 558 : free_dominance_info (CDI_DOMINATORS);
2324 558 : calculate_dominance_info (CDI_DOMINATORS);
2325 558 : }
2326 :
2327 : /* Tries to moves the exit condition of LOOP to the beginning of its header
2328 : without duplication of the loop body. NIT is the number of iterations of the
2329 : loop. REDUCTION_LIST describes the reductions in LOOP. Return true if
2330 : transformation is successful. */
2331 :
2332 : static bool
2333 582 : try_transform_to_exit_first_loop_alt (class loop *loop,
2334 : reduction_info_table_type *reduction_list,
2335 : tree nit)
2336 : {
2337 : /* Check whether the latch contains a single statement. */
2338 1164 : if (!gimple_seq_nondebug_singleton_p (bb_seq (loop->latch)))
2339 : return false;
2340 :
2341 : /* Check whether the latch contains no phis. */
2342 578 : if (phi_nodes (loop->latch) != NULL)
2343 : return false;
2344 :
2345 : /* Check whether the latch contains the loop iv increment. */
2346 578 : edge back = single_succ_edge (loop->latch);
2347 578 : edge exit = single_dom_exit (loop);
2348 1156 : gcond *cond_stmt = as_a <gcond *> (*gsi_last_bb (exit->src));
2349 578 : tree control = gimple_cond_lhs (cond_stmt);
2350 578 : gphi *phi = as_a <gphi *> (SSA_NAME_DEF_STMT (control));
2351 578 : tree inc_res = gimple_phi_arg_def (phi, back->dest_idx);
2352 578 : if (gimple_bb (SSA_NAME_DEF_STMT (inc_res)) != loop->latch)
2353 : return false;
2354 :
2355 : /* Check whether there's no code between the loop condition and the latch. */
2356 582 : if (!single_pred_p (loop->latch)
2357 578 : || single_pred (loop->latch) != exit->src)
2358 : return false;
2359 :
2360 578 : tree alt_bound = NULL_TREE;
2361 578 : tree nit_type = TREE_TYPE (nit);
2362 :
2363 : /* Figure out whether nit + 1 overflows. */
2364 578 : if (poly_int_tree_p (nit))
2365 : {
2366 436 : if (!tree_int_cst_equal (nit, TYPE_MAX_VALUE (nit_type)))
2367 : {
2368 436 : alt_bound = fold_build2_loc (UNKNOWN_LOCATION, PLUS_EXPR, nit_type,
2369 : nit, build_one_cst (nit_type));
2370 :
2371 436 : gcc_assert (TREE_CODE (alt_bound) == INTEGER_CST
2372 : || TREE_CODE (alt_bound) == POLY_INT_CST);
2373 436 : transform_to_exit_first_loop_alt (loop, reduction_list, alt_bound);
2374 436 : return true;
2375 : }
2376 : else
2377 : {
2378 : /* Todo: Figure out if we can trigger this, if it's worth to handle
2379 : optimally, and if we can handle it optimally. */
2380 : return false;
2381 : }
2382 : }
2383 :
2384 142 : gcc_assert (TREE_CODE (nit) == SSA_NAME);
2385 :
2386 : /* Variable nit is the loop bound as returned by canonicalize_loop_ivs, for an
2387 : iv with base 0 and step 1 that is incremented in the latch, like this:
2388 :
2389 : <bb header>:
2390 : # iv_1 = PHI <0 (preheader), iv_2 (latch)>
2391 : ...
2392 : if (iv_1 < nit)
2393 : goto <bb latch>;
2394 : else
2395 : goto <bb exit>;
2396 :
2397 : <bb latch>:
2398 : iv_2 = iv_1 + 1;
2399 : goto <bb header>;
2400 :
2401 : The range of iv_1 is [0, nit]. The latch edge is taken for
2402 : iv_1 == [0, nit - 1] and the exit edge is taken for iv_1 == nit. So the
2403 : number of latch executions is equal to nit.
2404 :
2405 : The function max_loop_iterations gives us the maximum number of latch
2406 : executions, so it gives us the maximum value of nit. */
2407 142 : widest_int nit_max;
2408 142 : if (!max_loop_iterations (loop, &nit_max))
2409 : return false;
2410 :
2411 : /* Check if nit + 1 overflows. */
2412 142 : widest_int type_max = wi::to_widest (TYPE_MAX_VALUE (nit_type));
2413 142 : if (nit_max >= type_max)
2414 : return false;
2415 :
2416 122 : gimple *def = SSA_NAME_DEF_STMT (nit);
2417 :
2418 : /* Try to find nit + 1, in the form of n in an assignment nit = n - 1. */
2419 122 : if (def
2420 122 : && is_gimple_assign (def)
2421 243 : && gimple_assign_rhs_code (def) == PLUS_EXPR)
2422 : {
2423 23 : tree op1 = gimple_assign_rhs1 (def);
2424 23 : tree op2 = gimple_assign_rhs2 (def);
2425 23 : if (integer_minus_onep (op1))
2426 : alt_bound = op2;
2427 23 : else if (integer_minus_onep (op2))
2428 : alt_bound = op1;
2429 : }
2430 :
2431 : /* If not found, insert nit + 1. */
2432 23 : if (alt_bound == NULL_TREE)
2433 : {
2434 99 : alt_bound = fold_build2 (PLUS_EXPR, nit_type, nit,
2435 : build_int_cst_type (nit_type, 1));
2436 :
2437 99 : gimple_stmt_iterator gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
2438 :
2439 99 : alt_bound
2440 99 : = force_gimple_operand_gsi (&gsi, alt_bound, true, NULL_TREE, false,
2441 : GSI_CONTINUE_LINKING);
2442 : }
2443 :
2444 122 : transform_to_exit_first_loop_alt (loop, reduction_list, alt_bound);
2445 122 : return true;
2446 284 : }
2447 :
2448 : /* Moves the exit condition of LOOP to the beginning of its header. NIT is the
2449 : number of iterations of the loop. REDUCTION_LIST describes the reductions in
2450 : LOOP. */
2451 :
2452 : static void
2453 24 : transform_to_exit_first_loop (class loop *loop,
2454 : reduction_info_table_type *reduction_list,
2455 : tree nit)
2456 : {
2457 24 : basic_block *bbs, *nbbs, ex_bb, orig_header;
2458 24 : unsigned n;
2459 24 : bool ok;
2460 24 : edge exit = single_dom_exit (loop), hpred;
2461 24 : tree control, control_name, res, t;
2462 24 : gphi *phi, *nphi;
2463 24 : gassign *stmt;
2464 24 : gcond *cond_stmt, *cond_nit;
2465 24 : tree nit_1;
2466 :
2467 24 : split_block_after_labels (loop->header);
2468 24 : orig_header = single_succ (loop->header);
2469 24 : hpred = single_succ_edge (loop->header);
2470 :
2471 48 : cond_stmt = as_a <gcond *> (*gsi_last_bb (exit->src));
2472 24 : control = gimple_cond_lhs (cond_stmt);
2473 24 : gcc_assert (gimple_cond_rhs (cond_stmt) == nit);
2474 :
2475 : /* Make sure that we have phi nodes on exit for all loop header phis
2476 : (create_parallel_loop requires that). */
2477 24 : for (gphi_iterator gsi = gsi_start_phis (loop->header);
2478 63 : !gsi_end_p (gsi);
2479 39 : gsi_next (&gsi))
2480 : {
2481 39 : phi = gsi.phi ();
2482 39 : res = PHI_RESULT (phi);
2483 39 : t = copy_ssa_name (res, phi);
2484 39 : if (auto red = reduction_phi (reduction_list, phi))
2485 1 : red->reduc_phi_name = t;
2486 39 : SET_PHI_RESULT (phi, t);
2487 39 : nphi = create_phi_node (res, orig_header);
2488 39 : add_phi_arg (nphi, t, hpred, UNKNOWN_LOCATION);
2489 :
2490 39 : if (res == control)
2491 : {
2492 24 : gimple_cond_set_lhs (cond_stmt, t);
2493 24 : update_stmt (cond_stmt);
2494 24 : control = t;
2495 : }
2496 : }
2497 :
2498 24 : bbs = get_loop_body_in_dom_order (loop);
2499 :
2500 74 : for (n = 0; bbs[n] != exit->src; n++)
2501 26 : continue;
2502 24 : nbbs = XNEWVEC (basic_block, n);
2503 24 : ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
2504 : bbs + 1, n, nbbs);
2505 24 : gcc_assert (ok);
2506 24 : free (bbs);
2507 24 : ex_bb = nbbs[0];
2508 24 : free (nbbs);
2509 :
2510 : /* Other than reductions, the only gimple reg that should be copied
2511 : out of the loop is the control variable. */
2512 24 : exit = single_dom_exit (loop);
2513 24 : control_name = NULL_TREE;
2514 24 : for (gphi_iterator gsi = gsi_start_phis (ex_bb);
2515 63 : !gsi_end_p (gsi); )
2516 : {
2517 39 : phi = gsi.phi ();
2518 39 : res = PHI_RESULT (phi);
2519 78 : if (virtual_operand_p (res))
2520 : {
2521 14 : gsi_next (&gsi);
2522 14 : continue;
2523 : }
2524 :
2525 : /* Check if it is a part of reduction. If it is,
2526 : keep the phi at the reduction's keep_res field. The
2527 : PHI_RESULT of this phi is the resulting value of the reduction
2528 : variable when exiting the loop. */
2529 :
2530 25 : if (!reduction_list->is_empty ())
2531 : {
2532 2 : struct reduction_info *red;
2533 :
2534 2 : tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2535 2 : red = reduction_phi (reduction_list, SSA_NAME_DEF_STMT (val));
2536 2 : if (red)
2537 : {
2538 1 : red->keep_res = phi;
2539 1 : gsi_next (&gsi);
2540 1 : continue;
2541 : }
2542 : }
2543 96 : gcc_assert (control_name == NULL_TREE
2544 : && SSA_NAME_VAR (res) == SSA_NAME_VAR (control));
2545 24 : control_name = res;
2546 24 : remove_phi_node (&gsi, false);
2547 : }
2548 24 : gcc_assert (control_name != NULL_TREE);
2549 :
2550 : /* Initialize the control variable to number of iterations
2551 : according to the rhs of the exit condition. */
2552 24 : gimple_stmt_iterator gsi = gsi_after_labels (ex_bb);
2553 48 : cond_nit = as_a <gcond *> (*gsi_last_bb (exit->src));
2554 24 : nit_1 = gimple_cond_rhs (cond_nit);
2555 24 : nit_1 = force_gimple_operand_gsi (&gsi,
2556 24 : fold_convert (TREE_TYPE (control_name), nit_1),
2557 : false, NULL_TREE, false, GSI_SAME_STMT);
2558 24 : stmt = gimple_build_assign (control_name, nit_1);
2559 24 : gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2560 26 : }
2561 :
2562 : /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
2563 : LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
2564 : NEW_DATA is the variable that should be initialized from the argument
2565 : of LOOP_FN. N_THREADS is the requested number of threads, which can be 0 if
2566 : that number is to be determined later. */
2567 :
2568 : static void
2569 582 : create_parallel_loop (class loop *loop, tree loop_fn, tree data,
2570 : tree new_data, unsigned n_threads, location_t loc,
2571 : bool oacc_kernels_p)
2572 : {
2573 582 : gimple_stmt_iterator gsi;
2574 582 : basic_block for_bb, ex_bb, continue_bb;
2575 582 : tree t, param;
2576 582 : gomp_parallel *omp_par_stmt;
2577 582 : gimple *omp_return_stmt1, *omp_return_stmt2;
2578 582 : gimple *phi;
2579 582 : gcond *cond_stmt;
2580 582 : gomp_for *for_stmt;
2581 582 : gomp_continue *omp_cont_stmt;
2582 582 : tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
2583 582 : edge exit, nexit, guard, end, e;
2584 :
2585 582 : if (oacc_kernels_p)
2586 : {
2587 386 : gcc_checking_assert (lookup_attribute ("oacc kernels",
2588 : DECL_ATTRIBUTES (cfun->decl)));
2589 : /* Indicate to later processing that this is a parallelized OpenACC
2590 : kernels construct. */
2591 386 : DECL_ATTRIBUTES (cfun->decl)
2592 772 : = tree_cons (get_identifier ("oacc kernels parallelized"),
2593 386 : NULL_TREE, DECL_ATTRIBUTES (cfun->decl));
2594 : }
2595 : else
2596 : {
2597 : /* Prepare the GIMPLE_OMP_PARALLEL statement. */
2598 :
2599 196 : basic_block bb = loop_preheader_edge (loop)->src;
2600 196 : basic_block paral_bb = single_pred (bb);
2601 196 : gsi = gsi_last_bb (paral_bb);
2602 :
2603 196 : gcc_checking_assert (n_threads != 0);
2604 196 : if (n_threads == INT_MAX)
2605 : /* No hardcoded thread count, let OpenMP runtime decide. */
2606 3 : omp_par_stmt = gimple_build_omp_parallel (NULL, NULL_TREE, loop_fn,
2607 : data);
2608 : else
2609 : {
2610 : /* Build the OMP_CLAUSE_NUM_THREADS clause only if we have a fixed
2611 : thread count. */
2612 193 : t = build_omp_clause (loc, OMP_CLAUSE_NUM_THREADS);
2613 193 : OMP_CLAUSE_NUM_THREADS_EXPR (t)
2614 193 : = build_int_cst (integer_type_node, n_threads);
2615 193 : omp_par_stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
2616 : }
2617 196 : gimple_set_location (omp_par_stmt, loc);
2618 :
2619 196 : gsi_insert_after (&gsi, omp_par_stmt, GSI_NEW_STMT);
2620 :
2621 : /* Initialize NEW_DATA. */
2622 196 : if (data)
2623 : {
2624 184 : gassign *assign_stmt;
2625 :
2626 184 : gsi = gsi_after_labels (bb);
2627 :
2628 184 : param = make_ssa_name (DECL_ARGUMENTS (loop_fn));
2629 184 : assign_stmt = gimple_build_assign (param, build_fold_addr_expr (data));
2630 184 : gsi_insert_before (&gsi, assign_stmt, GSI_SAME_STMT);
2631 :
2632 184 : assign_stmt = gimple_build_assign (new_data,
2633 184 : fold_convert (TREE_TYPE (new_data), param));
2634 184 : gsi_insert_before (&gsi, assign_stmt, GSI_SAME_STMT);
2635 : }
2636 :
2637 : /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
2638 196 : bb = split_loop_exit_edge (single_dom_exit (loop));
2639 196 : gsi = gsi_last_bb (bb);
2640 196 : omp_return_stmt1 = gimple_build_omp_return (false);
2641 196 : gimple_set_location (omp_return_stmt1, loc);
2642 196 : gsi_insert_after (&gsi, omp_return_stmt1, GSI_NEW_STMT);
2643 : }
2644 :
2645 : /* Extract data for GIMPLE_OMP_FOR. */
2646 582 : gcc_assert (loop->header == single_dom_exit (loop)->src);
2647 1164 : cond_stmt = as_a <gcond *> (*gsi_last_bb (loop->header));
2648 :
2649 582 : cvar = gimple_cond_lhs (cond_stmt);
2650 582 : cvar_base = SSA_NAME_VAR (cvar);
2651 582 : phi = SSA_NAME_DEF_STMT (cvar);
2652 582 : cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2653 582 : initvar = copy_ssa_name (cvar);
2654 582 : SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
2655 : initvar);
2656 582 : cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2657 :
2658 582 : gsi = gsi_last_nondebug_bb (loop->latch);
2659 582 : gcc_assert (gsi_stmt (gsi) == SSA_NAME_DEF_STMT (cvar_next));
2660 582 : gsi_remove (&gsi, true);
2661 :
2662 : /* Prepare cfg. */
2663 582 : for_bb = split_edge (loop_preheader_edge (loop));
2664 582 : ex_bb = split_loop_exit_edge (single_dom_exit (loop));
2665 582 : extract_true_false_edges_from_block (loop->header, &nexit, &exit);
2666 582 : gcc_assert (exit == single_dom_exit (loop));
2667 :
2668 582 : guard = make_edge (for_bb, ex_bb, 0);
2669 : /* FIXME: What is the probability? */
2670 582 : guard->probability = profile_probability::guessed_never ();
2671 : /* Split the latch edge, so LOOPS_HAVE_SIMPLE_LATCHES is still valid. */
2672 582 : loop->latch = split_edge (single_succ_edge (loop->latch));
2673 582 : single_pred_edge (loop->latch)->flags = 0;
2674 582 : end = make_single_succ_edge (single_pred (loop->latch), ex_bb, EDGE_FALLTHRU);
2675 582 : rescan_loop_exit (end, true, false);
2676 :
2677 582 : for (gphi_iterator gpi = gsi_start_phis (ex_bb);
2678 1089 : !gsi_end_p (gpi); gsi_next (&gpi))
2679 : {
2680 507 : location_t locus;
2681 507 : gphi *phi = gpi.phi ();
2682 507 : tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2683 507 : gimple *def_stmt = SSA_NAME_DEF_STMT (def);
2684 :
2685 : /* If the exit phi is not connected to a header phi in the same loop, this
2686 : value is not modified in the loop, and we're done with this phi. */
2687 507 : if (!(gimple_code (def_stmt) == GIMPLE_PHI
2688 507 : && gimple_bb (def_stmt) == loop->header))
2689 : {
2690 0 : locus = gimple_phi_arg_location_from_edge (phi, exit);
2691 0 : add_phi_arg (phi, def, guard, locus);
2692 0 : add_phi_arg (phi, def, end, locus);
2693 0 : continue;
2694 : }
2695 :
2696 507 : gphi *stmt = as_a <gphi *> (def_stmt);
2697 507 : def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop));
2698 507 : locus = gimple_phi_arg_location_from_edge (stmt,
2699 : loop_preheader_edge (loop));
2700 507 : add_phi_arg (phi, def, guard, locus);
2701 :
2702 507 : def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_latch_edge (loop));
2703 507 : locus = gimple_phi_arg_location_from_edge (stmt, loop_latch_edge (loop));
2704 507 : add_phi_arg (phi, def, end, locus);
2705 : }
2706 582 : e = redirect_edge_and_branch (exit, nexit->dest);
2707 582 : PENDING_STMT (e) = NULL;
2708 :
2709 : /* Emit GIMPLE_OMP_FOR. */
2710 582 : if (oacc_kernels_p)
2711 : /* Parallelized OpenACC kernels constructs use gang parallelism. See also
2712 : omp-offload.cc:execute_oacc_loop_designation. */
2713 386 : t = build_omp_clause (loc, OMP_CLAUSE_GANG);
2714 : else
2715 : {
2716 196 : t = build_omp_clause (loc, OMP_CLAUSE_SCHEDULE);
2717 196 : int chunk_size = param_parloops_chunk_size;
2718 196 : switch (param_parloops_schedule)
2719 : {
2720 181 : case PARLOOPS_SCHEDULE_STATIC:
2721 181 : OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
2722 181 : break;
2723 7 : case PARLOOPS_SCHEDULE_DYNAMIC:
2724 7 : OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_DYNAMIC;
2725 7 : break;
2726 4 : case PARLOOPS_SCHEDULE_GUIDED:
2727 4 : OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_GUIDED;
2728 4 : break;
2729 2 : case PARLOOPS_SCHEDULE_AUTO:
2730 2 : OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_AUTO;
2731 2 : chunk_size = 0;
2732 2 : break;
2733 2 : case PARLOOPS_SCHEDULE_RUNTIME:
2734 2 : OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_RUNTIME;
2735 2 : chunk_size = 0;
2736 2 : break;
2737 0 : default:
2738 0 : gcc_unreachable ();
2739 : }
2740 196 : if (chunk_size != 0)
2741 16 : OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (t)
2742 32 : = build_int_cst (integer_type_node, chunk_size);
2743 : }
2744 :
2745 778 : for_stmt = gimple_build_omp_for (NULL,
2746 : (oacc_kernels_p
2747 : ? GF_OMP_FOR_KIND_OACC_LOOP
2748 : : GF_OMP_FOR_KIND_FOR),
2749 : t, 1, NULL);
2750 :
2751 582 : gimple_cond_set_lhs (cond_stmt, cvar_base);
2752 582 : type = TREE_TYPE (cvar);
2753 582 : gimple_set_location (for_stmt, loc);
2754 582 : gimple_omp_for_set_index (for_stmt, 0, initvar);
2755 582 : gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
2756 582 : gimple_omp_for_set_final (for_stmt, 0, gimple_cond_rhs (cond_stmt));
2757 582 : gimple_omp_for_set_cond (for_stmt, 0, gimple_cond_code (cond_stmt));
2758 582 : gimple_omp_for_set_incr (for_stmt, 0, build2 (PLUS_EXPR, type,
2759 : cvar_base,
2760 : build_int_cst (type, 1)));
2761 :
2762 582 : gsi = gsi_last_bb (for_bb);
2763 582 : gsi_insert_after (&gsi, for_stmt, GSI_NEW_STMT);
2764 582 : SSA_NAME_DEF_STMT (initvar) = for_stmt;
2765 :
2766 : /* Emit GIMPLE_OMP_CONTINUE. */
2767 582 : continue_bb = single_pred (loop->latch);
2768 582 : gsi = gsi_last_bb (continue_bb);
2769 582 : omp_cont_stmt = gimple_build_omp_continue (cvar_next, cvar);
2770 582 : gimple_set_location (omp_cont_stmt, loc);
2771 582 : gsi_insert_after (&gsi, omp_cont_stmt, GSI_NEW_STMT);
2772 582 : SSA_NAME_DEF_STMT (cvar_next) = omp_cont_stmt;
2773 :
2774 : /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
2775 582 : gsi = gsi_last_bb (ex_bb);
2776 582 : omp_return_stmt2 = gimple_build_omp_return (true);
2777 582 : gimple_set_location (omp_return_stmt2, loc);
2778 582 : gsi_insert_after (&gsi, omp_return_stmt2, GSI_NEW_STMT);
2779 :
2780 : /* After the above dom info is hosed. Re-compute it. */
2781 582 : free_dominance_info (CDI_DOMINATORS);
2782 582 : calculate_dominance_info (CDI_DOMINATORS);
2783 582 : }
2784 :
2785 : /* Return number of phis in bb. If COUNT_VIRTUAL_P is false, don't count the
2786 : virtual phi. */
2787 :
2788 : static unsigned int
2789 583 : num_phis (basic_block bb, bool count_virtual_p)
2790 : {
2791 583 : unsigned int nr_phis = 0;
2792 583 : gphi_iterator gsi;
2793 1730 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2794 : {
2795 3441 : if (!count_virtual_p && virtual_operand_p (PHI_RESULT (gsi.phi ())))
2796 494 : continue;
2797 :
2798 653 : nr_phis++;
2799 : }
2800 :
2801 583 : return nr_phis;
2802 : }
2803 :
2804 : /* Generates code to execute the iterations of LOOP in N_THREADS
2805 : threads in parallel, which can be 0 if that number is to be determined
2806 : later.
2807 :
2808 : NITER describes number of iterations of LOOP.
2809 : REDUCTION_LIST describes the reductions existent in the LOOP. */
2810 :
2811 : static void
2812 583 : gen_parallel_loop (class loop *loop,
2813 : reduction_info_table_type *reduction_list,
2814 : unsigned n_threads, class tree_niter_desc *niter,
2815 : bool oacc_kernels_p)
2816 : {
2817 583 : tree many_iterations_cond, type, nit;
2818 583 : tree arg_struct, new_arg_struct;
2819 583 : gimple_seq stmts;
2820 583 : edge entry, exit;
2821 583 : struct clsn_data clsn_data;
2822 583 : location_t loc;
2823 583 : gimple *cond_stmt;
2824 :
2825 : /* From
2826 :
2827 : ---------------------------------------------------------------------
2828 : loop
2829 : {
2830 : IV = phi (INIT, IV + STEP)
2831 : BODY1;
2832 : if (COND)
2833 : break;
2834 : BODY2;
2835 : }
2836 : ---------------------------------------------------------------------
2837 :
2838 : with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
2839 : we generate the following code:
2840 :
2841 : ---------------------------------------------------------------------
2842 :
2843 : if (MAY_BE_ZERO
2844 : || NITER < MIN_PER_THREAD * N_THREADS)
2845 : goto original;
2846 :
2847 : BODY1;
2848 : store all local loop-invariant variables used in body of the loop to DATA.
2849 : GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
2850 : load the variables from DATA.
2851 : GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
2852 : BODY2;
2853 : BODY1;
2854 : GIMPLE_OMP_CONTINUE;
2855 : GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
2856 : GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
2857 : goto end;
2858 :
2859 : original:
2860 : loop
2861 : {
2862 : IV = phi (INIT, IV + STEP)
2863 : BODY1;
2864 : if (COND)
2865 : break;
2866 : BODY2;
2867 : }
2868 :
2869 : end:
2870 :
2871 : */
2872 :
2873 : /* Create two versions of the loop -- in the old one, we know that the
2874 : number of iterations is large enough, and we will transform it into the
2875 : loop that will be split to loop_fn, the new one will be used for the
2876 : remaining iterations. */
2877 :
2878 : /* We should compute a better number-of-iterations value for outer loops.
2879 : That is, if we have
2880 :
2881 : for (i = 0; i < n; ++i)
2882 : for (j = 0; j < m; ++j)
2883 : ...
2884 :
2885 : we should compute nit = n * m, not nit = n.
2886 : Also may_be_zero handling would need to be adjusted. */
2887 :
2888 583 : type = TREE_TYPE (niter->niter);
2889 583 : nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true,
2890 : NULL_TREE);
2891 583 : if (stmts)
2892 142 : gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2893 :
2894 583 : if (!oacc_kernels_p)
2895 : {
2896 197 : gcc_checking_assert (n_threads != 0);
2897 : /* For runtime thread detection, use a conservative estimate of 2 threads
2898 : for the many iterations condition check. */
2899 197 : unsigned threads = (n_threads == INT_MAX) ? 2 : n_threads;
2900 197 : unsigned m_p_thread = loop->inner ? 2 : MIN_PER_THREAD;
2901 197 : many_iterations_cond =
2902 197 : fold_build2 (GE_EXPR, boolean_type_node,
2903 : nit, build_int_cst (type, m_p_thread * threads - 1));
2904 :
2905 197 : many_iterations_cond
2906 197 : = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
2907 : invert_truthvalue (unshare_expr (niter->may_be_zero)),
2908 : many_iterations_cond);
2909 197 : many_iterations_cond
2910 197 : = force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
2911 197 : if (stmts)
2912 7 : gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2913 197 : if (!is_gimple_condexpr_for_cond (many_iterations_cond))
2914 : {
2915 7 : many_iterations_cond
2916 7 : = force_gimple_operand (many_iterations_cond, &stmts,
2917 : true, NULL_TREE);
2918 7 : if (stmts)
2919 7 : gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop),
2920 : stmts);
2921 : }
2922 :
2923 197 : initialize_original_copy_tables ();
2924 :
2925 : /* We assume that the loop usually iterates a lot. */
2926 197 : loop_version (loop, many_iterations_cond, NULL,
2927 : profile_probability::likely (),
2928 : profile_probability::unlikely (),
2929 : profile_probability::likely (),
2930 : profile_probability::unlikely (), true);
2931 197 : update_ssa (TODO_update_ssa_no_phi);
2932 197 : free_original_copy_tables ();
2933 : }
2934 :
2935 : /* Base all the induction variables in LOOP on a single control one. */
2936 583 : canonicalize_loop_ivs (loop, &nit, true);
2937 583 : if (num_phis (loop->header, false) != reduction_list->elements () + 1)
2938 : {
2939 : /* The call to canonicalize_loop_ivs above failed to "base all the
2940 : induction variables in LOOP on a single control one". Do damage
2941 : control. */
2942 1 : basic_block preheader = loop_preheader_edge (loop)->src;
2943 1 : basic_block cond_bb = single_pred (preheader);
2944 2 : gcond *cond = as_a <gcond *> (gsi_stmt (gsi_last_bb (cond_bb)));
2945 1 : gimple_cond_make_true (cond);
2946 1 : update_stmt (cond);
2947 : /* We've gotten rid of the duplicate loop created by loop_version, but
2948 : we can't undo whatever canonicalize_loop_ivs has done.
2949 : TODO: Fix this properly by ensuring that the call to
2950 : canonicalize_loop_ivs succeeds. */
2951 1 : if (dump_file
2952 1 : && (dump_flags & TDF_DETAILS))
2953 0 : fprintf (dump_file, "canonicalize_loop_ivs failed for loop %d,"
2954 : " aborting transformation\n", loop->num);
2955 1 : return;
2956 : }
2957 :
2958 : /* Ensure that the exit condition is the first statement in the loop.
2959 : The common case is that latch of the loop is empty (apart from the
2960 : increment) and immediately follows the loop exit test. Attempt to move the
2961 : entry of the loop directly before the exit check and increase the number of
2962 : iterations of the loop by one. */
2963 582 : if (try_transform_to_exit_first_loop_alt (loop, reduction_list, nit))
2964 : {
2965 558 : if (dump_file
2966 558 : && (dump_flags & TDF_DETAILS))
2967 221 : fprintf (dump_file,
2968 : "alternative exit-first loop transform succeeded"
2969 : " for loop %d\n", loop->num);
2970 : }
2971 : else
2972 : {
2973 24 : if (oacc_kernels_p)
2974 0 : n_threads = 1;
2975 :
2976 : /* Fall back on the method that handles more cases, but duplicates the
2977 : loop body: move the exit condition of LOOP to the beginning of its
2978 : header, and duplicate the part of the last iteration that gets disabled
2979 : to the exit of the loop. */
2980 24 : transform_to_exit_first_loop (loop, reduction_list, nit);
2981 : }
2982 582 : update_ssa (TODO_update_ssa_no_phi);
2983 :
2984 : /* Generate initializations for reductions. */
2985 582 : if (!reduction_list->is_empty ())
2986 134 : reduction_list->traverse <class loop *, initialize_reductions> (loop);
2987 :
2988 : /* Eliminate the references to local variables from the loop. */
2989 582 : gcc_assert (single_exit (loop));
2990 582 : entry = loop_preheader_edge (loop);
2991 582 : exit = single_dom_exit (loop);
2992 :
2993 : /* This rewrites the body in terms of new variables. This has already
2994 : been done for oacc_kernels_p in pass_lower_omp/lower_omp (). */
2995 582 : if (!oacc_kernels_p)
2996 : {
2997 196 : eliminate_local_variables (entry, exit);
2998 : /* In the old loop, move all variables non-local to the loop to a
2999 : structure and back, and create separate decls for the variables used in
3000 : loop. */
3001 196 : separate_decls_in_region (entry, exit, reduction_list, &arg_struct,
3002 : &new_arg_struct, &clsn_data);
3003 : }
3004 : else
3005 : {
3006 386 : arg_struct = NULL_TREE;
3007 386 : new_arg_struct = NULL_TREE;
3008 386 : clsn_data.load = NULL_TREE;
3009 386 : clsn_data.load_bb = exit->dest;
3010 386 : clsn_data.store = NULL_TREE;
3011 386 : clsn_data.store_bb = NULL;
3012 : }
3013 :
3014 : /* Create the parallel constructs. */
3015 582 : loc = UNKNOWN_LOCATION;
3016 582 : cond_stmt = last_nondebug_stmt (loop->header);
3017 582 : if (cond_stmt)
3018 582 : loc = gimple_location (cond_stmt);
3019 582 : create_parallel_loop (loop, create_loop_fn (loc), arg_struct, new_arg_struct,
3020 : n_threads, loc, oacc_kernels_p);
3021 582 : if (!reduction_list->is_empty ())
3022 66 : create_call_for_reduction (loop, reduction_list, &clsn_data);
3023 :
3024 582 : scev_reset ();
3025 :
3026 : /* Free loop bound estimations that could contain references to
3027 : removed statements. */
3028 582 : free_numbers_of_iterations_estimates (cfun);
3029 : }
3030 :
3031 : /* Returns true when LOOP contains vector phi nodes. */
3032 :
3033 : static bool
3034 1871 : loop_has_vector_phi_nodes (class loop *loop ATTRIBUTE_UNUSED)
3035 : {
3036 1871 : unsigned i;
3037 1871 : basic_block *bbs = get_loop_body_in_dom_order (loop);
3038 1871 : gphi_iterator gsi;
3039 1871 : bool res = true;
3040 :
3041 12572 : for (i = 0; i < loop->num_nodes; i++)
3042 16851 : for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
3043 8021 : if (VECTOR_TYPE_P (TREE_TYPE (PHI_RESULT (gsi.phi ()))))
3044 0 : goto end;
3045 :
3046 : res = false;
3047 1871 : end:
3048 1871 : free (bbs);
3049 1871 : return res;
3050 : }
3051 :
3052 : /* Create a reduction_info struct, initialize it with REDUC_STMT
3053 : and PHI, insert it to the REDUCTION_LIST. */
3054 :
3055 : static void
3056 85 : build_new_reduction (reduction_info_table_type *reduction_list,
3057 : gimple *reduc_stmt, gphi *phi)
3058 : {
3059 85 : reduction_info **slot;
3060 85 : struct reduction_info *new_reduction;
3061 85 : enum tree_code reduction_code;
3062 :
3063 85 : gcc_assert (reduc_stmt);
3064 :
3065 85 : if (gimple_code (reduc_stmt) == GIMPLE_PHI)
3066 : {
3067 18 : tree op1 = PHI_ARG_DEF (reduc_stmt, 0);
3068 18 : gimple *def1 = SSA_NAME_DEF_STMT (op1);
3069 18 : reduction_code = gimple_assign_rhs_code (def1);
3070 : }
3071 : else
3072 67 : reduction_code = gimple_assign_rhs_code (reduc_stmt);
3073 : /* Check for OpenMP supported reduction. */
3074 85 : switch (reduction_code)
3075 : {
3076 15 : case MINUS_EXPR:
3077 15 : reduction_code = PLUS_EXPR;
3078 : /* Fallthru. */
3079 85 : case PLUS_EXPR:
3080 85 : case MULT_EXPR:
3081 85 : case MAX_EXPR:
3082 85 : case MIN_EXPR:
3083 85 : case BIT_IOR_EXPR:
3084 85 : case BIT_XOR_EXPR:
3085 85 : case BIT_AND_EXPR:
3086 85 : case TRUTH_OR_EXPR:
3087 85 : case TRUTH_XOR_EXPR:
3088 85 : case TRUTH_AND_EXPR:
3089 85 : break;
3090 0 : default:
3091 0 : return;
3092 : }
3093 :
3094 85 : if (dump_file && (dump_flags & TDF_DETAILS))
3095 : {
3096 43 : fprintf (dump_file,
3097 : "Detected reduction. reduction stmt is:\n");
3098 43 : print_gimple_stmt (dump_file, reduc_stmt, 0);
3099 43 : fprintf (dump_file, "\n");
3100 : }
3101 :
3102 85 : new_reduction = XCNEW (struct reduction_info);
3103 :
3104 85 : new_reduction->reduc_stmt = reduc_stmt;
3105 85 : const auto phi_name = gimple_phi_result (phi);
3106 85 : new_reduction->reduc_phi_name = phi_name;
3107 85 : new_reduction->reduc_version = SSA_NAME_VERSION (phi_name);
3108 85 : new_reduction->reduction_code = reduction_code;
3109 85 : slot = reduction_list->find_slot (new_reduction, INSERT);
3110 85 : *slot = new_reduction;
3111 : }
3112 :
3113 : /* Callback for htab_traverse. Sets gimple_uid of reduc_phi stmts. */
3114 :
3115 : int
3116 85 : set_reduc_phi_uids (reduction_info **slot, void *data ATTRIBUTE_UNUSED)
3117 : {
3118 85 : struct reduction_info *const red = *slot;
3119 85 : gimple_set_uid (red->reduc_phi (), red->reduc_version);
3120 85 : return 1;
3121 : }
3122 :
3123 : /* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
3124 :
3125 : static void
3126 1275 : gather_scalar_reductions (loop_p loop, reduction_info_table_type *reduction_list)
3127 : {
3128 1275 : gphi_iterator gsi;
3129 1275 : loop_vec_info simple_loop_info;
3130 1275 : auto_vec<gphi *, 4> double_reduc_phis;
3131 1275 : auto_vec<gimple *, 4> double_reduc_stmts;
3132 1275 : hash_set<gphi *> double_reduc_inner_lc_phis;
3133 :
3134 1275 : vec_info_shared shared;
3135 1275 : vect_loop_form_info info;
3136 1275 : if (!vect_analyze_loop_form (loop, NULL, &info))
3137 575 : goto gather_done;
3138 :
3139 700 : simple_loop_info = vect_create_loop_vinfo (loop, &shared, &info);
3140 2371 : for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
3141 : {
3142 1671 : gphi *phi = gsi.phi ();
3143 1671 : affine_iv iv;
3144 1671 : tree res = PHI_RESULT (phi);
3145 1671 : bool double_reduc;
3146 :
3147 3342 : if (virtual_operand_p (res))
3148 1604 : continue;
3149 :
3150 1079 : if (simple_iv (loop, loop, res, &iv, true))
3151 962 : continue;
3152 :
3153 117 : stmt_vec_info reduc_stmt_info
3154 117 : = parloops_force_simple_reduction (simple_loop_info,
3155 : simple_loop_info->lookup_stmt (phi),
3156 : &double_reduc, true,
3157 : double_reduc_inner_lc_phis);
3158 117 : if (!reduc_stmt_info)
3159 31 : continue;
3160 :
3161 86 : if (double_reduc)
3162 : {
3163 : /* vect_analyze_loop_form guarantees this. */
3164 19 : gcc_assert (loop->inner->inner == NULL);
3165 :
3166 19 : double_reduc_phis.safe_push (phi);
3167 19 : double_reduc_stmts.safe_push (reduc_stmt_info->stmt);
3168 19 : continue;
3169 : }
3170 :
3171 67 : build_new_reduction (reduction_list, reduc_stmt_info->stmt, phi);
3172 : }
3173 :
3174 700 : if (!double_reduc_phis.is_empty ())
3175 : {
3176 : gphi *phi;
3177 : unsigned int i;
3178 :
3179 38 : FOR_EACH_VEC_ELT (double_reduc_phis, i, phi)
3180 : {
3181 19 : affine_iv iv;
3182 19 : tree res = PHI_RESULT (phi);
3183 19 : bool double_reduc;
3184 :
3185 19 : use_operand_p use_p;
3186 19 : gimple *inner_stmt;
3187 19 : bool single_use_p = single_imm_use (res, &use_p, &inner_stmt);
3188 19 : gcc_assert (single_use_p);
3189 19 : if (gimple_code (inner_stmt) != GIMPLE_PHI)
3190 1 : continue;
3191 19 : gphi *inner_phi = as_a <gphi *> (inner_stmt);
3192 19 : if (simple_iv (loop->inner, loop->inner, PHI_RESULT (inner_phi),
3193 : &iv, true))
3194 0 : continue;
3195 :
3196 19 : stmt_vec_info inner_phi_info
3197 19 : = simple_loop_info->lookup_stmt (inner_phi);
3198 19 : stmt_vec_info inner_reduc_stmt_info
3199 19 : = parloops_force_simple_reduction (simple_loop_info,
3200 : inner_phi_info,
3201 : &double_reduc, true,
3202 : double_reduc_inner_lc_phis);
3203 19 : gcc_assert (!double_reduc);
3204 19 : if (!inner_reduc_stmt_info)
3205 1 : continue;
3206 :
3207 18 : build_new_reduction (reduction_list, double_reduc_stmts[i], phi);
3208 : }
3209 : }
3210 700 : delete simple_loop_info;
3211 :
3212 0 : gather_done:
3213 1275 : if (reduction_list->is_empty ())
3214 1192 : return;
3215 :
3216 : /* As gimple_uid is used by the vectorizer in between vect_analyze_loop_form
3217 : and delete simple_loop_info, we can set gimple_uid of reduc_phi stmts only
3218 : now. */
3219 83 : basic_block bb;
3220 1141 : FOR_EACH_BB_FN (bb, cfun)
3221 2106 : for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
3222 1048 : gimple_set_uid (gsi_stmt (gsi), (unsigned int)-1);
3223 168 : reduction_list->traverse <void *, set_reduc_phi_uids> (NULL);
3224 1275 : }
3225 :
3226 : /* Try to initialize NITER for code generation part. */
3227 :
3228 : static bool
3229 1762 : try_get_loop_niter (loop_p loop, class tree_niter_desc *niter)
3230 : {
3231 1762 : edge exit = single_dom_exit (loop);
3232 :
3233 1762 : gcc_assert (exit);
3234 :
3235 : /* We need to know # of iterations, and there should be no uses of values
3236 : defined inside loop outside of it, unless the values are invariants of
3237 : the loop. */
3238 1762 : if (!number_of_iterations_exit (loop, exit, niter, false))
3239 : {
3240 487 : if (dump_file && (dump_flags & TDF_DETAILS))
3241 10 : fprintf (dump_file, " FAILED: number of iterations not known\n");
3242 487 : return false;
3243 : }
3244 :
3245 : return true;
3246 : }
3247 :
3248 : /* Return the default def of the first function argument. */
3249 :
3250 : static tree
3251 404 : get_omp_data_i_param (void)
3252 : {
3253 404 : tree decl = DECL_ARGUMENTS (cfun->decl);
3254 404 : gcc_assert (DECL_CHAIN (decl) == NULL_TREE);
3255 404 : return ssa_default_def (cfun, decl);
3256 : }
3257 :
3258 : /* For PHI in loop header of LOOP, look for pattern:
3259 :
3260 : <bb preheader>
3261 : .omp_data_i = &.omp_data_arr;
3262 : addr = .omp_data_i->sum;
3263 : sum_a = *addr;
3264 :
3265 : <bb header>:
3266 : sum_b = PHI <sum_a (preheader), sum_c (latch)>
3267 :
3268 : and return addr. Otherwise, return NULL_TREE. */
3269 :
3270 : static tree
3271 14 : find_reduc_addr (class loop *loop, gphi *phi)
3272 : {
3273 14 : edge e = loop_preheader_edge (loop);
3274 14 : tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
3275 14 : gimple *stmt = SSA_NAME_DEF_STMT (arg);
3276 14 : if (!gimple_assign_single_p (stmt))
3277 : return NULL_TREE;
3278 14 : tree memref = gimple_assign_rhs1 (stmt);
3279 14 : if (TREE_CODE (memref) != MEM_REF)
3280 : return NULL_TREE;
3281 14 : tree addr = TREE_OPERAND (memref, 0);
3282 :
3283 14 : gimple *stmt2 = SSA_NAME_DEF_STMT (addr);
3284 14 : if (!gimple_assign_single_p (stmt2))
3285 : return NULL_TREE;
3286 14 : tree compref = gimple_assign_rhs1 (stmt2);
3287 14 : if (TREE_CODE (compref) != COMPONENT_REF)
3288 : return NULL_TREE;
3289 14 : tree addr2 = TREE_OPERAND (compref, 0);
3290 14 : if (TREE_CODE (addr2) != MEM_REF)
3291 : return NULL_TREE;
3292 14 : addr2 = TREE_OPERAND (addr2, 0);
3293 14 : if (TREE_CODE (addr2) != SSA_NAME
3294 14 : || addr2 != get_omp_data_i_param ())
3295 0 : return NULL_TREE;
3296 :
3297 : return addr;
3298 : }
3299 :
3300 : /* Try to initialize REDUCTION_LIST for code generation part.
3301 : REDUCTION_LIST describes the reductions. */
3302 :
3303 : static bool
3304 1275 : try_create_reduction_list (loop_p loop,
3305 : reduction_info_table_type *reduction_list,
3306 : bool oacc_kernels_p)
3307 : {
3308 1275 : edge exit = single_dom_exit (loop);
3309 1275 : gphi_iterator gsi;
3310 :
3311 1275 : gcc_assert (exit);
3312 :
3313 : /* Try to get rid of exit phis. */
3314 1275 : final_value_replacement_loop (loop);
3315 :
3316 1275 : gather_scalar_reductions (loop, reduction_list);
3317 :
3318 :
3319 2431 : for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
3320 : {
3321 1227 : gphi *phi = gsi.phi ();
3322 1227 : struct reduction_info *red;
3323 1227 : imm_use_iterator imm_iter;
3324 1227 : use_operand_p use_p;
3325 1227 : gimple *reduc_phi;
3326 1227 : tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3327 :
3328 2454 : if (!virtual_operand_p (val))
3329 : {
3330 155 : if (TREE_CODE (val) != SSA_NAME)
3331 : {
3332 0 : if (dump_file && (dump_flags & TDF_DETAILS))
3333 0 : fprintf (dump_file,
3334 : " FAILED: exit PHI argument invariant.\n");
3335 71 : return false;
3336 : }
3337 :
3338 155 : if (dump_file && (dump_flags & TDF_DETAILS))
3339 : {
3340 56 : fprintf (dump_file, "phi is ");
3341 56 : print_gimple_stmt (dump_file, phi, 0);
3342 56 : fprintf (dump_file, "arg of phi to exit: value ");
3343 56 : print_generic_expr (dump_file, val);
3344 56 : fprintf (dump_file, " used outside loop\n");
3345 56 : fprintf (dump_file,
3346 : " checking if it is part of reduction pattern:\n");
3347 : }
3348 155 : if (reduction_list->is_empty ())
3349 : {
3350 66 : if (dump_file && (dump_flags & TDF_DETAILS))
3351 13 : fprintf (dump_file,
3352 : " FAILED: it is not a part of reduction.\n");
3353 66 : return false;
3354 : }
3355 89 : reduc_phi = NULL;
3356 247 : FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
3357 : {
3358 158 : if (!gimple_debug_bind_p (USE_STMT (use_p))
3359 158 : && flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
3360 : {
3361 89 : reduc_phi = USE_STMT (use_p);
3362 89 : break;
3363 : }
3364 89 : }
3365 89 : red = reduction_phi (reduction_list, reduc_phi);
3366 89 : if (red == NULL)
3367 : {
3368 5 : if (dump_file && (dump_flags & TDF_DETAILS))
3369 0 : fprintf (dump_file,
3370 : " FAILED: it is not a part of reduction.\n");
3371 5 : return false;
3372 : }
3373 84 : if (red->keep_res != NULL)
3374 : {
3375 0 : if (dump_file && (dump_flags & TDF_DETAILS))
3376 0 : fprintf (dump_file,
3377 : " FAILED: reduction has multiple exit phis.\n");
3378 0 : return false;
3379 : }
3380 84 : red->keep_res = phi;
3381 84 : if (dump_file && (dump_flags & TDF_DETAILS))
3382 : {
3383 43 : fprintf (dump_file, "reduction phi is ");
3384 43 : print_gimple_stmt (dump_file, red->reduc_phi (), 0);
3385 43 : fprintf (dump_file, "reduction stmt is ");
3386 43 : print_gimple_stmt (dump_file, red->reduc_stmt, 0);
3387 : }
3388 : }
3389 : }
3390 :
3391 : /* The iterations of the loop may communicate only through bivs whose
3392 : iteration space can be distributed efficiently. */
3393 3740 : for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
3394 : {
3395 2548 : gphi *phi = gsi.phi ();
3396 2548 : tree def = PHI_RESULT (phi);
3397 2548 : affine_iv iv;
3398 :
3399 5096 : if (!virtual_operand_p (def) && !simple_iv (loop, loop, def, &iv, true))
3400 : {
3401 85 : struct reduction_info *red;
3402 :
3403 85 : red = reduction_phi (reduction_list, phi);
3404 85 : if (red == NULL)
3405 : {
3406 12 : if (dump_file && (dump_flags & TDF_DETAILS))
3407 0 : fprintf (dump_file,
3408 : " FAILED: scalar dependency between iterations\n");
3409 12 : return false;
3410 : }
3411 : }
3412 : }
3413 :
3414 1192 : if (oacc_kernels_p)
3415 : {
3416 2691 : for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi);
3417 1813 : gsi_next (&gsi))
3418 : {
3419 1813 : gphi *phi = gsi.phi ();
3420 1813 : tree def = PHI_RESULT (phi);
3421 1813 : affine_iv iv;
3422 :
3423 1813 : if (!virtual_operand_p (def)
3424 1813 : && !simple_iv (loop, loop, def, &iv, true))
3425 : {
3426 14 : tree addr = find_reduc_addr (loop, phi);
3427 14 : if (addr == NULL_TREE)
3428 0 : return false;
3429 14 : struct reduction_info *red = reduction_phi (reduction_list, phi);
3430 14 : red->reduc_addr = addr;
3431 : }
3432 : }
3433 : }
3434 :
3435 : return true;
3436 : }
3437 :
3438 : /* Return true if LOOP contains phis with ADDR_EXPR in args. */
3439 :
3440 : static bool
3441 1192 : loop_has_phi_with_address_arg (class loop *loop)
3442 : {
3443 1192 : basic_block *bbs = get_loop_body (loop);
3444 1192 : bool res = false;
3445 :
3446 1192 : unsigned i, j;
3447 1192 : gphi_iterator gsi;
3448 6531 : for (i = 0; i < loop->num_nodes; i++)
3449 9811 : for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
3450 : {
3451 4472 : gphi *phi = gsi.phi ();
3452 13208 : for (j = 0; j < gimple_phi_num_args (phi); j++)
3453 : {
3454 8736 : tree arg = gimple_phi_arg_def (phi, j);
3455 8736 : if (TREE_CODE (arg) == ADDR_EXPR)
3456 : {
3457 : /* This should be handled by eliminate_local_variables, but that
3458 : function currently ignores phis. */
3459 0 : res = true;
3460 0 : goto end;
3461 : }
3462 : }
3463 : }
3464 1192 : end:
3465 1192 : free (bbs);
3466 :
3467 1192 : return res;
3468 : }
3469 :
3470 : /* Return true if memory ref REF (corresponding to the stmt at GSI in
3471 : REGIONS_BB[I]) conflicts with the statements in REGIONS_BB[I] after gsi,
3472 : or the statements in REGIONS_BB[I + n]. REF_IS_STORE indicates if REF is a
3473 : store. Ignore conflicts with SKIP_STMT. */
3474 :
3475 : static bool
3476 566 : ref_conflicts_with_region (gimple_stmt_iterator gsi, ao_ref *ref,
3477 : bool ref_is_store, vec<basic_block> region_bbs,
3478 : unsigned int i, gimple *skip_stmt)
3479 : {
3480 566 : basic_block bb = region_bbs[i];
3481 566 : gsi_next (&gsi);
3482 :
3483 1538 : while (true)
3484 : {
3485 7283 : for (; !gsi_end_p (gsi);
3486 5179 : gsi_next (&gsi))
3487 : {
3488 5183 : gimple *stmt = gsi_stmt (gsi);
3489 5183 : if (stmt == skip_stmt)
3490 : {
3491 14 : if (dump_file)
3492 : {
3493 12 : fprintf (dump_file, "skipping reduction store: ");
3494 12 : print_gimple_stmt (dump_file, stmt, 0);
3495 : }
3496 14 : continue;
3497 : }
3498 :
3499 8992 : if (!gimple_vdef (stmt)
3500 8434 : && !gimple_vuse (stmt))
3501 2747 : continue;
3502 :
3503 2422 : if (gimple_code (stmt) == GIMPLE_RETURN)
3504 546 : continue;
3505 :
3506 1876 : if (ref_is_store)
3507 : {
3508 780 : if (ref_maybe_used_by_stmt_p (stmt, ref))
3509 : {
3510 0 : if (dump_file)
3511 : {
3512 0 : fprintf (dump_file, "Stmt ");
3513 0 : print_gimple_stmt (dump_file, stmt, 0);
3514 : }
3515 0 : return true;
3516 : }
3517 : }
3518 : else
3519 : {
3520 1096 : if (stmt_may_clobber_ref_p_1 (stmt, ref))
3521 : {
3522 4 : if (dump_file)
3523 : {
3524 1 : fprintf (dump_file, "Stmt ");
3525 1 : print_gimple_stmt (dump_file, stmt, 0);
3526 : }
3527 4 : return true;
3528 : }
3529 : }
3530 : }
3531 2100 : i++;
3532 2100 : if (i == region_bbs.length ())
3533 : break;
3534 1538 : bb = region_bbs[i];
3535 1538 : gsi = gsi_start_bb (bb);
3536 1538 : }
3537 :
3538 : return false;
3539 : }
3540 :
3541 : /* Return true if the bbs in REGION_BBS but not in in_loop_bbs can be executed
3542 : in parallel with REGION_BBS containing the loop. Return the stores of
3543 : reduction results in REDUCTION_STORES. */
3544 :
3545 : static bool
3546 390 : oacc_entry_exit_ok_1 (bitmap in_loop_bbs, const vec<basic_block> ®ion_bbs,
3547 : reduction_info_table_type *reduction_list,
3548 : bitmap reduction_stores)
3549 : {
3550 390 : tree omp_data_i = get_omp_data_i_param ();
3551 :
3552 390 : unsigned i;
3553 390 : basic_block bb;
3554 2634 : FOR_EACH_VEC_ELT (region_bbs, i, bb)
3555 : {
3556 2248 : if (bitmap_bit_p (in_loop_bbs, bb->index))
3557 970 : continue;
3558 :
3559 1278 : gimple_stmt_iterator gsi;
3560 4738 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
3561 2182 : gsi_next (&gsi))
3562 : {
3563 2186 : gimple *stmt = gsi_stmt (gsi);
3564 2186 : gimple *skip_stmt = NULL;
3565 :
3566 2186 : if (is_gimple_debug (stmt)
3567 2186 : || gimple_code (stmt) == GIMPLE_COND)
3568 1620 : continue;
3569 :
3570 2094 : ao_ref ref;
3571 2094 : bool ref_is_store = false;
3572 2094 : if (gimple_assign_load_p (stmt))
3573 : {
3574 1200 : tree rhs = gimple_assign_rhs1 (stmt);
3575 1200 : tree base = get_base_address (rhs);
3576 2140 : if (TREE_CODE (base) == MEM_REF
3577 1200 : && operand_equal_p (TREE_OPERAND (base, 0), omp_data_i, 0))
3578 940 : continue;
3579 :
3580 260 : tree lhs = gimple_assign_lhs (stmt);
3581 260 : if (TREE_CODE (lhs) == SSA_NAME
3582 260 : && has_single_use (lhs))
3583 : {
3584 152 : use_operand_p use_p;
3585 152 : gimple *use_stmt;
3586 152 : struct reduction_info *red;
3587 152 : single_imm_use (lhs, &use_p, &use_stmt);
3588 152 : if (gimple_code (use_stmt) == GIMPLE_PHI
3589 152 : && (red = reduction_phi (reduction_list, use_stmt)))
3590 : {
3591 14 : tree val = PHI_RESULT (red->keep_res);
3592 14 : if (has_single_use (val))
3593 : {
3594 14 : single_imm_use (val, &use_p, &use_stmt);
3595 14 : if (gimple_store_p (use_stmt))
3596 : {
3597 14 : unsigned int id
3598 28 : = SSA_NAME_VERSION (gimple_vdef (use_stmt));
3599 14 : bitmap_set_bit (reduction_stores, id);
3600 14 : skip_stmt = use_stmt;
3601 14 : if (dump_file)
3602 : {
3603 12 : fprintf (dump_file, "found reduction load: ");
3604 12 : print_gimple_stmt (dump_file, stmt, 0);
3605 : }
3606 : }
3607 : }
3608 : }
3609 : }
3610 :
3611 260 : ao_ref_init (&ref, rhs);
3612 : }
3613 894 : else if (gimple_store_p (stmt))
3614 : {
3615 306 : ao_ref_init (&ref, gimple_assign_lhs (stmt));
3616 306 : ref_is_store = true;
3617 : }
3618 588 : else if (gimple_code (stmt) == GIMPLE_OMP_RETURN)
3619 0 : continue;
3620 588 : else if (!gimple_has_side_effects (stmt)
3621 588 : && !gimple_could_trap_p (stmt)
3622 588 : && !stmt_could_throw_p (cfun, stmt)
3623 588 : && !gimple_vdef (stmt)
3624 1176 : && !gimple_vuse (stmt))
3625 202 : continue;
3626 386 : else if (gimple_call_internal_p (stmt, IFN_GOACC_DIM_POS))
3627 0 : continue;
3628 386 : else if (gimple_code (stmt) == GIMPLE_RETURN)
3629 386 : continue;
3630 : else
3631 : {
3632 0 : if (dump_file)
3633 : {
3634 0 : fprintf (dump_file, "Unhandled stmt in entry/exit: ");
3635 0 : print_gimple_stmt (dump_file, stmt, 0);
3636 : }
3637 4 : return false;
3638 : }
3639 :
3640 566 : if (ref_conflicts_with_region (gsi, &ref, ref_is_store, region_bbs,
3641 : i, skip_stmt))
3642 : {
3643 4 : if (dump_file)
3644 : {
3645 1 : fprintf (dump_file, "conflicts with entry/exit stmt: ");
3646 1 : print_gimple_stmt (dump_file, stmt, 0);
3647 : }
3648 4 : return false;
3649 : }
3650 : }
3651 : }
3652 :
3653 : return true;
3654 : }
3655 :
3656 : /* Find stores inside REGION_BBS and outside IN_LOOP_BBS, and guard them with
3657 : gang_pos == 0, except when the stores are REDUCTION_STORES. Return true
3658 : if any changes were made. */
3659 :
3660 : static bool
3661 386 : oacc_entry_exit_single_gang (bitmap in_loop_bbs,
3662 : const vec<basic_block> ®ion_bbs,
3663 : bitmap reduction_stores)
3664 : {
3665 386 : tree gang_pos = NULL_TREE;
3666 386 : bool changed = false;
3667 :
3668 386 : unsigned i;
3669 386 : basic_block bb;
3670 2626 : FOR_EACH_VEC_ELT (region_bbs, i, bb)
3671 : {
3672 2240 : if (bitmap_bit_p (in_loop_bbs, bb->index))
3673 970 : continue;
3674 :
3675 1270 : gimple_stmt_iterator gsi;
3676 4714 : for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
3677 : {
3678 2174 : gimple *stmt = gsi_stmt (gsi);
3679 :
3680 2174 : if (!gimple_store_p (stmt))
3681 : {
3682 : /* Update gsi to point to next stmt. */
3683 1868 : gsi_next (&gsi);
3684 1868 : continue;
3685 : }
3686 :
3687 612 : if (bitmap_bit_p (reduction_stores,
3688 306 : SSA_NAME_VERSION (gimple_vdef (stmt))))
3689 : {
3690 14 : if (dump_file)
3691 : {
3692 12 : fprintf (dump_file,
3693 : "skipped reduction store for single-gang"
3694 : " neutering: ");
3695 12 : print_gimple_stmt (dump_file, stmt, 0);
3696 : }
3697 :
3698 : /* Update gsi to point to next stmt. */
3699 14 : gsi_next (&gsi);
3700 14 : continue;
3701 : }
3702 :
3703 292 : changed = true;
3704 :
3705 292 : if (gang_pos == NULL_TREE)
3706 : {
3707 142 : tree arg = build_int_cst (integer_type_node, GOMP_DIM_GANG);
3708 142 : gcall *gang_single
3709 142 : = gimple_build_call_internal (IFN_GOACC_DIM_POS, 1, arg);
3710 142 : gang_pos = make_ssa_name (integer_type_node);
3711 142 : gimple_call_set_lhs (gang_single, gang_pos);
3712 142 : gimple_stmt_iterator start
3713 142 : = gsi_start_bb (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
3714 142 : tree vuse = ssa_default_def (cfun, gimple_vop (cfun));
3715 142 : gimple_set_vuse (gang_single, vuse);
3716 142 : gsi_insert_before (&start, gang_single, GSI_SAME_STMT);
3717 : }
3718 :
3719 292 : if (dump_file)
3720 : {
3721 112 : fprintf (dump_file,
3722 : "found store that needs single-gang neutering: ");
3723 112 : print_gimple_stmt (dump_file, stmt, 0);
3724 : }
3725 :
3726 292 : {
3727 : /* Split block before store. */
3728 292 : gimple_stmt_iterator gsi2 = gsi;
3729 292 : gsi_prev (&gsi2);
3730 292 : edge e;
3731 292 : if (gsi_end_p (gsi2))
3732 : {
3733 8 : e = split_block_after_labels (bb);
3734 16 : gsi2 = gsi_last_bb (bb);
3735 : }
3736 : else
3737 284 : e = split_block (bb, gsi_stmt (gsi2));
3738 292 : basic_block bb2 = e->dest;
3739 :
3740 : /* Split block after store. */
3741 292 : gimple_stmt_iterator gsi3 = gsi_start_bb (bb2);
3742 292 : edge e2 = split_block (bb2, gsi_stmt (gsi3));
3743 292 : basic_block bb3 = e2->dest;
3744 :
3745 292 : gimple *cond
3746 292 : = gimple_build_cond (EQ_EXPR, gang_pos, integer_zero_node,
3747 : NULL_TREE, NULL_TREE);
3748 292 : gsi_insert_after (&gsi2, cond, GSI_NEW_STMT);
3749 :
3750 292 : edge e3 = make_edge (bb, bb3, EDGE_FALSE_VALUE);
3751 : /* FIXME: What is the probability? */
3752 292 : e3->probability = profile_probability::guessed_never ();
3753 292 : e->flags = EDGE_TRUE_VALUE;
3754 :
3755 292 : tree vdef = gimple_vdef (stmt);
3756 292 : tree vuse = gimple_vuse (stmt);
3757 :
3758 292 : tree phi_res = copy_ssa_name (vdef);
3759 292 : gphi *new_phi = create_phi_node (phi_res, bb3);
3760 292 : replace_uses_by (vdef, phi_res);
3761 292 : add_phi_arg (new_phi, vuse, e3, UNKNOWN_LOCATION);
3762 292 : add_phi_arg (new_phi, vdef, e2, UNKNOWN_LOCATION);
3763 :
3764 : /* Update gsi to point to next stmt. */
3765 292 : bb = bb3;
3766 584 : gsi = gsi_start_bb (bb);
3767 : }
3768 : }
3769 : }
3770 :
3771 386 : return changed;
3772 : }
3773 :
3774 : /* Return true if the statements before and after the LOOP can be executed in
3775 : parallel with the function containing the loop. Resolve conflicting stores
3776 : outside LOOP by guarding them such that only a single gang executes them. */
3777 :
3778 : static bool
3779 390 : oacc_entry_exit_ok (class loop *loop,
3780 : reduction_info_table_type *reduction_list)
3781 : {
3782 390 : basic_block *loop_bbs = get_loop_body_in_dom_order (loop);
3783 390 : auto_vec<basic_block> region_bbs
3784 390 : = get_all_dominated_blocks (CDI_DOMINATORS, ENTRY_BLOCK_PTR_FOR_FN (cfun));
3785 :
3786 390 : bitmap in_loop_bbs = BITMAP_ALLOC (NULL);
3787 390 : bitmap_clear (in_loop_bbs);
3788 1368 : for (unsigned int i = 0; i < loop->num_nodes; i++)
3789 978 : bitmap_set_bit (in_loop_bbs, loop_bbs[i]->index);
3790 :
3791 390 : bitmap reduction_stores = BITMAP_ALLOC (NULL);
3792 390 : bool res = oacc_entry_exit_ok_1 (in_loop_bbs, region_bbs, reduction_list,
3793 : reduction_stores);
3794 :
3795 390 : if (res)
3796 : {
3797 386 : bool changed = oacc_entry_exit_single_gang (in_loop_bbs, region_bbs,
3798 : reduction_stores);
3799 386 : if (changed)
3800 : {
3801 142 : free_dominance_info (CDI_DOMINATORS);
3802 142 : calculate_dominance_info (CDI_DOMINATORS);
3803 : }
3804 : }
3805 :
3806 390 : free (loop_bbs);
3807 :
3808 390 : BITMAP_FREE (in_loop_bbs);
3809 390 : BITMAP_FREE (reduction_stores);
3810 :
3811 390 : return res;
3812 390 : }
3813 :
3814 : /* Detect parallel loops and generate parallel code using libgomp
3815 : primitives. Returns true if some loop was parallelized, false
3816 : otherwise. */
3817 :
3818 : static bool
3819 1643 : parallelize_loops (bool oacc_kernels_p)
3820 : {
3821 1643 : unsigned n_threads;
3822 1643 : bool changed = false;
3823 1643 : class loop *skip_loop = NULL;
3824 1643 : class tree_niter_desc niter_desc;
3825 1643 : struct obstack parloop_obstack;
3826 1643 : HOST_WIDE_INT estimated;
3827 :
3828 : /* Do not parallelize loops in the functions created by parallelization. */
3829 1643 : if (!oacc_kernels_p
3830 1643 : && parallelized_function_p (cfun->decl))
3831 : return false;
3832 :
3833 : /* Do not parallelize loops in offloaded functions. */
3834 1447 : if (!oacc_kernels_p
3835 1447 : && oacc_get_fn_attrib (cfun->decl) != NULL)
3836 : return false;
3837 :
3838 1447 : if (cfun->has_nonlocal_label)
3839 : return false;
3840 :
3841 : /* For OpenACC kernels, n_threads will be determined later; otherwise, it's
3842 : the argument to -ftree-parallelize-loops. */
3843 1447 : if (oacc_kernels_p)
3844 : n_threads = 0;
3845 : else
3846 414 : n_threads = flag_tree_parallelize_loops;
3847 :
3848 1447 : gcc_obstack_init (&parloop_obstack);
3849 1447 : reduction_info_table_type reduction_list (10);
3850 :
3851 1447 : calculate_dominance_info (CDI_DOMINATORS);
3852 :
3853 7130 : for (auto loop : loops_list (cfun, 0))
3854 : {
3855 2789 : if (loop == skip_loop)
3856 : {
3857 623 : if (!loop->in_oacc_kernels_region
3858 623 : && dump_file && (dump_flags & TDF_DETAILS))
3859 17 : fprintf (dump_file,
3860 : "Skipping loop %d as inner loop of parallelized loop\n",
3861 : loop->num);
3862 :
3863 623 : skip_loop = loop->inner;
3864 623 : continue;
3865 : }
3866 : else
3867 2166 : skip_loop = NULL;
3868 :
3869 2166 : reduction_list.empty ();
3870 :
3871 2166 : if (oacc_kernels_p)
3872 : {
3873 1033 : if (!loop->in_oacc_kernels_region)
3874 0 : continue;
3875 :
3876 : /* Don't try to parallelize inner loops in an oacc kernels region. */
3877 1033 : if (loop->inner)
3878 : skip_loop = loop->inner;
3879 :
3880 1033 : if (dump_file && (dump_flags & TDF_DETAILS))
3881 165 : fprintf (dump_file,
3882 : "Trying loop %d with header bb %d in oacc kernels"
3883 165 : " region\n", loop->num, loop->header->index);
3884 : }
3885 :
3886 2166 : if (dump_file && (dump_flags & TDF_DETAILS))
3887 : {
3888 302 : fprintf (dump_file, "Trying loop %d as candidate\n",loop->num);
3889 302 : if (loop->inner)
3890 52 : fprintf (dump_file, "loop %d is not innermost\n",loop->num);
3891 : else
3892 250 : fprintf (dump_file, "loop %d is innermost\n",loop->num);
3893 : }
3894 :
3895 2166 : if (!single_dom_exit (loop))
3896 : {
3897 :
3898 295 : if (dump_file && (dump_flags & TDF_DETAILS))
3899 22 : fprintf (dump_file, "loop is !single_dom_exit\n");
3900 :
3901 295 : continue;
3902 : }
3903 :
3904 1871 : if (/* And of course, the loop must be parallelizable. */
3905 1871 : !can_duplicate_loop_p (loop)
3906 1871 : || loop_has_blocks_with_irreducible_flag (loop)
3907 1871 : || (loop_preheader_edge (loop)->src->flags & BB_IRREDUCIBLE_LOOP)
3908 : /* FIXME: the check for vector phi nodes could be removed. */
3909 3742 : || loop_has_vector_phi_nodes (loop))
3910 0 : continue;
3911 :
3912 1871 : estimated = estimated_loop_iterations_int (loop);
3913 1871 : if (estimated == -1)
3914 1104 : estimated = get_likely_max_loop_iterations_int (loop);
3915 : /* For runtime thread detection, use an estimate of 2 threads. */
3916 1871 : unsigned threads = (n_threads == INT_MAX) ? 2 : n_threads;
3917 1871 : unsigned m_p_thread = loop->inner ? 2 : MIN_PER_THREAD;
3918 : /* FIXME: Bypass this check as graphite doesn't update the
3919 : count and frequency correctly now. */
3920 1980 : if (!flag_loop_parallelize_all
3921 1771 : && !oacc_kernels_p
3922 2609 : && ((estimated != -1
3923 393 : && (estimated < ((HOST_WIDE_INT) threads * m_p_thread - 1)))
3924 : /* Do not bother with loops in cold areas. */
3925 637 : || optimize_loop_nest_for_size_p (loop)))
3926 109 : continue;
3927 :
3928 1762 : if (!try_get_loop_niter (loop, &niter_desc))
3929 487 : continue;
3930 :
3931 1275 : if (!try_create_reduction_list (loop, &reduction_list, oacc_kernels_p))
3932 83 : continue;
3933 :
3934 1192 : if (loop_has_phi_with_address_arg (loop))
3935 0 : continue;
3936 :
3937 1797 : if (!loop->can_be_parallel
3938 1192 : && !loop_parallel_p (loop, &parloop_obstack))
3939 605 : continue;
3940 :
3941 591 : if (oacc_kernels_p
3942 587 : && !oacc_entry_exit_ok (loop, &reduction_list))
3943 : {
3944 4 : if (dump_file)
3945 1 : fprintf (dump_file, "entry/exit not ok: FAILED\n");
3946 4 : continue;
3947 : }
3948 :
3949 583 : changed = true;
3950 583 : skip_loop = loop->inner;
3951 :
3952 583 : if (dump_enabled_p ())
3953 : {
3954 229 : dump_user_location_t loop_loc = find_loop_location (loop);
3955 229 : if (loop->inner)
3956 26 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loop_loc,
3957 : "parallelizing outer loop %d\n", loop->num);
3958 : else
3959 203 : dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loop_loc,
3960 : "parallelizing inner loop %d\n", loop->num);
3961 : }
3962 :
3963 583 : gen_parallel_loop (loop, &reduction_list,
3964 : n_threads, &niter_desc, oacc_kernels_p);
3965 1447 : }
3966 :
3967 1447 : obstack_free (&parloop_obstack, NULL);
3968 :
3969 : /* Parallelization will cause new function calls to be inserted through
3970 : which local variables will escape. Reset the points-to solution
3971 : for ESCAPED. */
3972 1447 : if (changed)
3973 : {
3974 550 : pt_solution_reset (&cfun->gimple_df->escaped);
3975 550 : pt_solution_reset (&cfun->gimple_df->escaped_return);
3976 : }
3977 :
3978 1447 : return changed;
3979 1447 : }
3980 :
3981 : /* Parallelization. */
3982 :
3983 : namespace {
3984 :
3985 : const pass_data pass_data_parallelize_loops =
3986 : {
3987 : GIMPLE_PASS, /* type */
3988 : "parloops", /* name */
3989 : OPTGROUP_LOOP, /* optinfo_flags */
3990 : TV_TREE_PARALLELIZE_LOOPS, /* tv_id */
3991 : ( PROP_cfg | PROP_ssa ), /* properties_required */
3992 : 0, /* properties_provided */
3993 : 0, /* properties_destroyed */
3994 : 0, /* todo_flags_start */
3995 : 0, /* todo_flags_finish */
3996 : };
3997 :
3998 : class pass_parallelize_loops : public gimple_opt_pass
3999 : {
4000 : public:
4001 571444 : pass_parallelize_loops (gcc::context *ctxt)
4002 571444 : : gimple_opt_pass (pass_data_parallelize_loops, ctxt),
4003 1142888 : oacc_kernels_p (false)
4004 : {}
4005 :
4006 : /* opt_pass methods: */
4007 242496 : bool gate (function *) final override
4008 : {
4009 242496 : if (oacc_kernels_p)
4010 1038 : return flag_openacc;
4011 : else
4012 241458 : return flag_tree_parallelize_loops > 1;
4013 : }
4014 : unsigned int execute (function *) final override;
4015 285722 : opt_pass * clone () final override
4016 : {
4017 285722 : return new pass_parallelize_loops (m_ctxt);
4018 : }
4019 571444 : void set_pass_param (unsigned int n, bool param) final override
4020 : {
4021 571444 : gcc_assert (n == 0);
4022 571444 : oacc_kernels_p = param;
4023 571444 : }
4024 :
4025 : private:
4026 : bool oacc_kernels_p;
4027 : }; // class pass_parallelize_loops
4028 :
4029 : unsigned
4030 1643 : pass_parallelize_loops::execute (function *fun)
4031 : {
4032 1643 : tree nthreads = builtin_decl_explicit (BUILT_IN_OMP_GET_NUM_THREADS);
4033 1643 : if (nthreads == NULL_TREE)
4034 : return 0;
4035 :
4036 1643 : bool in_loop_pipeline = scev_initialized_p ();
4037 1643 : if (!in_loop_pipeline)
4038 1033 : loop_optimizer_init (LOOPS_NORMAL
4039 : | LOOPS_HAVE_RECORDED_EXITS);
4040 :
4041 3286 : if (number_of_loops (fun) <= 1)
4042 : return 0;
4043 :
4044 1643 : if (!in_loop_pipeline)
4045 : {
4046 1033 : rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
4047 1033 : scev_initialize ();
4048 : }
4049 :
4050 1643 : unsigned int todo = 0;
4051 1643 : if (parallelize_loops (oacc_kernels_p))
4052 : {
4053 550 : fun->curr_properties &= ~(PROP_gimple_eomp);
4054 :
4055 550 : checking_verify_loop_structure ();
4056 :
4057 : /* ??? Intermediate SSA updates with no PHIs might have lost
4058 : the virtual operand renaming needed by separate_decls_in_region,
4059 : make sure to rename them again. */
4060 550 : mark_virtual_operands_for_renaming (fun);
4061 550 : update_ssa (TODO_update_ssa);
4062 550 : if (in_loop_pipeline)
4063 164 : rewrite_into_loop_closed_ssa (NULL, 0);
4064 : }
4065 :
4066 1257 : if (!in_loop_pipeline)
4067 : {
4068 1033 : scev_finalize ();
4069 1033 : loop_optimizer_finalize ();
4070 : }
4071 :
4072 : return todo;
4073 : }
4074 :
4075 : } // anon namespace
4076 :
4077 : gimple_opt_pass *
4078 285722 : make_pass_parallelize_loops (gcc::context *ctxt)
4079 : {
4080 285722 : return new pass_parallelize_loops (ctxt);
4081 : }
|
