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