Fix ICE in lto_symtab_merge_symbols_1 (PR lto/88004).
[official-gcc.git] / gcc / tree-parloops.c
blob81d7742e7a76b84711940df14183c9c443b79de4
1 /* Loop autoparallelization.
2 Copyright (C) 2006-2018 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>.
6 This file is part of GCC.
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.
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.
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/>. */
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 "params.h"
56 #include "params-enum.h"
57 #include "tree-ssa-alias.h"
58 #include "tree-eh.h"
59 #include "gomp-constants.h"
60 #include "tree-dfa.h"
61 #include "stringpool.h"
62 #include "attribs.h"
64 /* This pass tries to distribute iterations of loops into several threads.
65 The implementation is straightforward -- for each loop we test whether its
66 iterations are independent, and if it is the case (and some additional
67 conditions regarding profitability and correctness are satisfied), we
68 add GIMPLE_OMP_PARALLEL and GIMPLE_OMP_FOR codes and let omp expansion
69 machinery do its job.
71 The most of the complexity is in bringing the code into shape expected
72 by the omp expanders:
73 -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction
74 variable and that the exit test is at the start of the loop body
75 -- for GIMPLE_OMP_PARALLEL, replacing the references to local addressable
76 variables by accesses through pointers, and breaking up ssa chains
77 by storing the values incoming to the parallelized loop to a structure
78 passed to the new function as an argument (something similar is done
79 in omp gimplification, unfortunately only a small part of the code
80 can be shared).
82 TODO:
83 -- if there are several parallelizable loops in a function, it may be
84 possible to generate the threads just once (using synchronization to
85 ensure that cross-loop dependences are obeyed).
86 -- handling of common reduction patterns for outer loops.
88 More info can also be found at http://gcc.gnu.org/wiki/AutoParInGCC */
90 Reduction handling:
91 currently we use vect_force_simple_reduction() to detect reduction patterns.
92 The code transformation will be introduced by an example.
95 parloop
97 int sum=1;
99 for (i = 0; i < N; i++)
101 x[i] = i + 3;
102 sum+=x[i];
106 gimple-like code:
107 header_bb:
109 # sum_29 = PHI <sum_11(5), 1(3)>
110 # i_28 = PHI <i_12(5), 0(3)>
111 D.1795_8 = i_28 + 3;
112 x[i_28] = D.1795_8;
113 sum_11 = D.1795_8 + sum_29;
114 i_12 = i_28 + 1;
115 if (N_6(D) > i_12)
116 goto header_bb;
119 exit_bb:
121 # sum_21 = PHI <sum_11(4)>
122 printf (&"%d"[0], sum_21);
125 after reduction transformation (only relevant parts):
127 parloop
130 ....
133 # Storing the initial value given by the user. #
135 .paral_data_store.32.sum.27 = 1;
137 #pragma omp parallel num_threads(4)
139 #pragma omp for schedule(static)
141 # The neutral element corresponding to the particular
142 reduction's operation, e.g. 0 for PLUS_EXPR,
143 1 for MULT_EXPR, etc. replaces the user's initial value. #
145 # sum.27_29 = PHI <sum.27_11, 0>
147 sum.27_11 = D.1827_8 + sum.27_29;
149 GIMPLE_OMP_CONTINUE
151 # Adding this reduction phi is done at create_phi_for_local_result() #
152 # sum.27_56 = PHI <sum.27_11, 0>
153 GIMPLE_OMP_RETURN
155 # Creating the atomic operation is done at
156 create_call_for_reduction_1() #
158 #pragma omp atomic_load
159 D.1839_59 = *&.paral_data_load.33_51->reduction.23;
160 D.1840_60 = sum.27_56 + D.1839_59;
161 #pragma omp atomic_store (D.1840_60);
163 GIMPLE_OMP_RETURN
165 # collecting the result after the join of the threads is done at
166 create_loads_for_reductions().
167 The value computed by the threads is loaded from the
168 shared struct. #
171 .paral_data_load.33_52 = &.paral_data_store.32;
172 sum_37 = .paral_data_load.33_52->sum.27;
173 sum_43 = D.1795_41 + sum_37;
175 exit bb:
176 # sum_21 = PHI <sum_43, sum_26>
177 printf (&"%d"[0], sum_21);
185 /* Minimal number of iterations of a loop that should be executed in each
186 thread. */
187 #define MIN_PER_THREAD PARAM_VALUE (PARAM_PARLOOPS_MIN_PER_THREAD)
189 /* Element of the hashtable, representing a
190 reduction in the current loop. */
191 struct reduction_info
193 gimple *reduc_stmt; /* reduction statement. */
194 gimple *reduc_phi; /* The phi node defining the reduction. */
195 enum tree_code reduction_code;/* code for the reduction operation. */
196 unsigned reduc_version; /* SSA_NAME_VERSION of original reduc_phi
197 result. */
198 gphi *keep_res; /* The PHI_RESULT of this phi is the resulting value
199 of the reduction variable when existing the loop. */
200 tree initial_value; /* The initial value of the reduction var before entering the loop. */
201 tree field; /* the name of the field in the parloop data structure intended for reduction. */
202 tree reduc_addr; /* The address of the reduction variable for
203 openacc reductions. */
204 tree init; /* reduction initialization value. */
205 gphi *new_phi; /* (helper field) Newly created phi node whose result
206 will be passed to the atomic operation. Represents
207 the local result each thread computed for the reduction
208 operation. */
211 /* Reduction info hashtable helpers. */
213 struct reduction_hasher : free_ptr_hash <reduction_info>
215 static inline hashval_t hash (const reduction_info *);
216 static inline bool equal (const reduction_info *, const reduction_info *);
219 /* Equality and hash functions for hashtab code. */
221 inline bool
222 reduction_hasher::equal (const reduction_info *a, const reduction_info *b)
224 return (a->reduc_phi == b->reduc_phi);
227 inline hashval_t
228 reduction_hasher::hash (const reduction_info *a)
230 return a->reduc_version;
233 typedef hash_table<reduction_hasher> reduction_info_table_type;
236 static struct reduction_info *
237 reduction_phi (reduction_info_table_type *reduction_list, gimple *phi)
239 struct reduction_info tmpred, *red;
241 if (reduction_list->elements () == 0 || phi == NULL)
242 return NULL;
244 if (gimple_uid (phi) == (unsigned int)-1
245 || gimple_uid (phi) == 0)
246 return NULL;
248 tmpred.reduc_phi = phi;
249 tmpred.reduc_version = gimple_uid (phi);
250 red = reduction_list->find (&tmpred);
251 gcc_assert (red == NULL || red->reduc_phi == phi);
253 return red;
256 /* Element of hashtable of names to copy. */
258 struct name_to_copy_elt
260 unsigned version; /* The version of the name to copy. */
261 tree new_name; /* The new name used in the copy. */
262 tree field; /* The field of the structure used to pass the
263 value. */
266 /* Name copies hashtable helpers. */
268 struct name_to_copy_hasher : free_ptr_hash <name_to_copy_elt>
270 static inline hashval_t hash (const name_to_copy_elt *);
271 static inline bool equal (const name_to_copy_elt *, const name_to_copy_elt *);
274 /* Equality and hash functions for hashtab code. */
276 inline bool
277 name_to_copy_hasher::equal (const name_to_copy_elt *a, const name_to_copy_elt *b)
279 return a->version == b->version;
282 inline hashval_t
283 name_to_copy_hasher::hash (const name_to_copy_elt *a)
285 return (hashval_t) a->version;
288 typedef hash_table<name_to_copy_hasher> name_to_copy_table_type;
290 /* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
291 matrix. Rather than use floats, we simply keep a single DENOMINATOR that
292 represents the denominator for every element in the matrix. */
293 typedef struct lambda_trans_matrix_s
295 lambda_matrix matrix;
296 int rowsize;
297 int colsize;
298 int denominator;
299 } *lambda_trans_matrix;
300 #define LTM_MATRIX(T) ((T)->matrix)
301 #define LTM_ROWSIZE(T) ((T)->rowsize)
302 #define LTM_COLSIZE(T) ((T)->colsize)
303 #define LTM_DENOMINATOR(T) ((T)->denominator)
305 /* Allocate a new transformation matrix. */
307 static lambda_trans_matrix
308 lambda_trans_matrix_new (int colsize, int rowsize,
309 struct obstack * lambda_obstack)
311 lambda_trans_matrix ret;
313 ret = (lambda_trans_matrix)
314 obstack_alloc (lambda_obstack, sizeof (struct lambda_trans_matrix_s));
315 LTM_MATRIX (ret) = lambda_matrix_new (rowsize, colsize, lambda_obstack);
316 LTM_ROWSIZE (ret) = rowsize;
317 LTM_COLSIZE (ret) = colsize;
318 LTM_DENOMINATOR (ret) = 1;
319 return ret;
322 /* Multiply a vector VEC by a matrix MAT.
323 MAT is an M*N matrix, and VEC is a vector with length N. The result
324 is stored in DEST which must be a vector of length M. */
326 static void
327 lambda_matrix_vector_mult (lambda_matrix matrix, int m, int n,
328 lambda_vector vec, lambda_vector dest)
330 int i, j;
332 lambda_vector_clear (dest, m);
333 for (i = 0; i < m; i++)
334 for (j = 0; j < n; j++)
335 dest[i] += matrix[i][j] * vec[j];
338 /* Return true if TRANS is a legal transformation matrix that respects
339 the dependence vectors in DISTS and DIRS. The conservative answer
340 is false.
342 "Wolfe proves that a unimodular transformation represented by the
343 matrix T is legal when applied to a loop nest with a set of
344 lexicographically non-negative distance vectors RDG if and only if
345 for each vector d in RDG, (T.d >= 0) is lexicographically positive.
346 i.e.: if and only if it transforms the lexicographically positive
347 distance vectors to lexicographically positive vectors. Note that
348 a unimodular matrix must transform the zero vector (and only it) to
349 the zero vector." S.Muchnick. */
351 static bool
352 lambda_transform_legal_p (lambda_trans_matrix trans,
353 int nb_loops,
354 vec<ddr_p> dependence_relations)
356 unsigned int i, j;
357 lambda_vector distres;
358 struct data_dependence_relation *ddr;
360 gcc_assert (LTM_COLSIZE (trans) == nb_loops
361 && LTM_ROWSIZE (trans) == nb_loops);
363 /* When there are no dependences, the transformation is correct. */
364 if (dependence_relations.length () == 0)
365 return true;
367 ddr = dependence_relations[0];
368 if (ddr == NULL)
369 return true;
371 /* When there is an unknown relation in the dependence_relations, we
372 know that it is no worth looking at this loop nest: give up. */
373 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
374 return false;
376 distres = lambda_vector_new (nb_loops);
378 /* For each distance vector in the dependence graph. */
379 FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
381 /* Don't care about relations for which we know that there is no
382 dependence, nor about read-read (aka. output-dependences):
383 these data accesses can happen in any order. */
384 if (DDR_ARE_DEPENDENT (ddr) == chrec_known
385 || (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr))))
386 continue;
388 /* Conservatively answer: "this transformation is not valid". */
389 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
390 return false;
392 /* If the dependence could not be captured by a distance vector,
393 conservatively answer that the transform is not valid. */
394 if (DDR_NUM_DIST_VECTS (ddr) == 0)
395 return false;
397 /* Compute trans.dist_vect */
398 for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
400 lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops,
401 DDR_DIST_VECT (ddr, j), distres);
403 if (!lambda_vector_lexico_pos (distres, nb_loops))
404 return false;
407 return true;
410 /* Data dependency analysis. Returns true if the iterations of LOOP
411 are independent on each other (that is, if we can execute them
412 in parallel). */
414 static bool
415 loop_parallel_p (struct loop *loop, struct obstack * parloop_obstack)
417 vec<ddr_p> dependence_relations;
418 vec<data_reference_p> datarefs;
419 lambda_trans_matrix trans;
420 bool ret = false;
422 if (dump_file && (dump_flags & TDF_DETAILS))
424 fprintf (dump_file, "Considering loop %d\n", loop->num);
425 if (!loop->inner)
426 fprintf (dump_file, "loop is innermost\n");
427 else
428 fprintf (dump_file, "loop NOT innermost\n");
431 /* Check for problems with dependences. If the loop can be reversed,
432 the iterations are independent. */
433 auto_vec<loop_p, 3> loop_nest;
434 datarefs.create (10);
435 dependence_relations.create (100);
436 if (! compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs,
437 &dependence_relations))
439 if (dump_file && (dump_flags & TDF_DETAILS))
440 fprintf (dump_file, " FAILED: cannot analyze data dependencies\n");
441 ret = false;
442 goto end;
444 if (dump_file && (dump_flags & TDF_DETAILS))
445 dump_data_dependence_relations (dump_file, dependence_relations);
447 trans = lambda_trans_matrix_new (1, 1, parloop_obstack);
448 LTM_MATRIX (trans)[0][0] = -1;
450 if (lambda_transform_legal_p (trans, 1, dependence_relations))
452 ret = true;
453 if (dump_file && (dump_flags & TDF_DETAILS))
454 fprintf (dump_file, " SUCCESS: may be parallelized\n");
456 else if (dump_file && (dump_flags & TDF_DETAILS))
457 fprintf (dump_file,
458 " FAILED: data dependencies exist across iterations\n");
460 end:
461 free_dependence_relations (dependence_relations);
462 free_data_refs (datarefs);
464 return ret;
467 /* Return true when LOOP contains basic blocks marked with the
468 BB_IRREDUCIBLE_LOOP flag. */
470 static inline bool
471 loop_has_blocks_with_irreducible_flag (struct loop *loop)
473 unsigned i;
474 basic_block *bbs = get_loop_body_in_dom_order (loop);
475 bool res = true;
477 for (i = 0; i < loop->num_nodes; i++)
478 if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
479 goto end;
481 res = false;
482 end:
483 free (bbs);
484 return res;
487 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
488 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
489 to their addresses that can be reused. The address of OBJ is known to
490 be invariant in the whole function. Other needed statements are placed
491 right before GSI. */
493 static tree
494 take_address_of (tree obj, tree type, edge entry,
495 int_tree_htab_type *decl_address, gimple_stmt_iterator *gsi)
497 int uid;
498 tree *var_p, name, addr;
499 gassign *stmt;
500 gimple_seq stmts;
502 /* Since the address of OBJ is invariant, the trees may be shared.
503 Avoid rewriting unrelated parts of the code. */
504 obj = unshare_expr (obj);
505 for (var_p = &obj;
506 handled_component_p (*var_p);
507 var_p = &TREE_OPERAND (*var_p, 0))
508 continue;
510 /* Canonicalize the access to base on a MEM_REF. */
511 if (DECL_P (*var_p))
512 *var_p = build_simple_mem_ref (build_fold_addr_expr (*var_p));
514 /* Assign a canonical SSA name to the address of the base decl used
515 in the address and share it for all accesses and addresses based
516 on it. */
517 uid = DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));
518 int_tree_map elt;
519 elt.uid = uid;
520 int_tree_map *slot = decl_address->find_slot (elt, INSERT);
521 if (!slot->to)
523 if (gsi == NULL)
524 return NULL;
525 addr = TREE_OPERAND (*var_p, 0);
526 const char *obj_name
527 = get_name (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));
528 if (obj_name)
529 name = make_temp_ssa_name (TREE_TYPE (addr), NULL, obj_name);
530 else
531 name = make_ssa_name (TREE_TYPE (addr));
532 stmt = gimple_build_assign (name, addr);
533 gsi_insert_on_edge_immediate (entry, stmt);
535 slot->uid = uid;
536 slot->to = name;
538 else
539 name = slot->to;
541 /* Express the address in terms of the canonical SSA name. */
542 TREE_OPERAND (*var_p, 0) = name;
543 if (gsi == NULL)
544 return build_fold_addr_expr_with_type (obj, type);
546 name = force_gimple_operand (build_addr (obj),
547 &stmts, true, NULL_TREE);
548 if (!gimple_seq_empty_p (stmts))
549 gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
551 if (!useless_type_conversion_p (type, TREE_TYPE (name)))
553 name = force_gimple_operand (fold_convert (type, name), &stmts, true,
554 NULL_TREE);
555 if (!gimple_seq_empty_p (stmts))
556 gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
559 return name;
562 static tree
563 reduc_stmt_res (gimple *stmt)
565 return (gimple_code (stmt) == GIMPLE_PHI
566 ? gimple_phi_result (stmt)
567 : gimple_assign_lhs (stmt));
570 /* Callback for htab_traverse. Create the initialization statement
571 for reduction described in SLOT, and place it at the preheader of
572 the loop described in DATA. */
575 initialize_reductions (reduction_info **slot, struct loop *loop)
577 tree init;
578 tree type, arg;
579 edge e;
581 struct reduction_info *const reduc = *slot;
583 /* Create initialization in preheader:
584 reduction_variable = initialization value of reduction. */
586 /* In the phi node at the header, replace the argument coming
587 from the preheader with the reduction initialization value. */
589 /* Initialize the reduction. */
590 type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
591 init = omp_reduction_init_op (gimple_location (reduc->reduc_stmt),
592 reduc->reduction_code, type);
593 reduc->init = init;
595 /* Replace the argument representing the initialization value
596 with the initialization value for the reduction (neutral
597 element for the particular operation, e.g. 0 for PLUS_EXPR,
598 1 for MULT_EXPR, etc).
599 Keep the old value in a new variable "reduction_initial",
600 that will be taken in consideration after the parallel
601 computing is done. */
603 e = loop_preheader_edge (loop);
604 arg = PHI_ARG_DEF_FROM_EDGE (reduc->reduc_phi, e);
605 /* Create new variable to hold the initial value. */
607 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
608 (reduc->reduc_phi, loop_preheader_edge (loop)), init);
609 reduc->initial_value = arg;
610 return 1;
613 struct elv_data
615 struct walk_stmt_info info;
616 edge entry;
617 int_tree_htab_type *decl_address;
618 gimple_stmt_iterator *gsi;
619 bool changed;
620 bool reset;
623 /* Eliminates references to local variables in *TP out of the single
624 entry single exit region starting at DTA->ENTRY.
625 DECL_ADDRESS contains addresses of the references that had their
626 address taken already. If the expression is changed, CHANGED is
627 set to true. Callback for walk_tree. */
629 static tree
630 eliminate_local_variables_1 (tree *tp, int *walk_subtrees, void *data)
632 struct elv_data *const dta = (struct elv_data *) data;
633 tree t = *tp, var, addr, addr_type, type, obj;
635 if (DECL_P (t))
637 *walk_subtrees = 0;
639 if (!SSA_VAR_P (t) || DECL_EXTERNAL (t))
640 return NULL_TREE;
642 type = TREE_TYPE (t);
643 addr_type = build_pointer_type (type);
644 addr = take_address_of (t, addr_type, dta->entry, dta->decl_address,
645 dta->gsi);
646 if (dta->gsi == NULL && addr == NULL_TREE)
648 dta->reset = true;
649 return NULL_TREE;
652 *tp = build_simple_mem_ref (addr);
654 dta->changed = true;
655 return NULL_TREE;
658 if (TREE_CODE (t) == ADDR_EXPR)
660 /* ADDR_EXPR may appear in two contexts:
661 -- as a gimple operand, when the address taken is a function invariant
662 -- as gimple rhs, when the resulting address in not a function
663 invariant
664 We do not need to do anything special in the latter case (the base of
665 the memory reference whose address is taken may be replaced in the
666 DECL_P case). The former case is more complicated, as we need to
667 ensure that the new address is still a gimple operand. Thus, it
668 is not sufficient to replace just the base of the memory reference --
669 we need to move the whole computation of the address out of the
670 loop. */
671 if (!is_gimple_val (t))
672 return NULL_TREE;
674 *walk_subtrees = 0;
675 obj = TREE_OPERAND (t, 0);
676 var = get_base_address (obj);
677 if (!var || !SSA_VAR_P (var) || DECL_EXTERNAL (var))
678 return NULL_TREE;
680 addr_type = TREE_TYPE (t);
681 addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address,
682 dta->gsi);
683 if (dta->gsi == NULL && addr == NULL_TREE)
685 dta->reset = true;
686 return NULL_TREE;
688 *tp = addr;
690 dta->changed = true;
691 return NULL_TREE;
694 if (!EXPR_P (t))
695 *walk_subtrees = 0;
697 return NULL_TREE;
700 /* Moves the references to local variables in STMT at *GSI out of the single
701 entry single exit region starting at ENTRY. DECL_ADDRESS contains
702 addresses of the references that had their address taken
703 already. */
705 static void
706 eliminate_local_variables_stmt (edge entry, gimple_stmt_iterator *gsi,
707 int_tree_htab_type *decl_address)
709 struct elv_data dta;
710 gimple *stmt = gsi_stmt (*gsi);
712 memset (&dta.info, '\0', sizeof (dta.info));
713 dta.entry = entry;
714 dta.decl_address = decl_address;
715 dta.changed = false;
716 dta.reset = false;
718 if (gimple_debug_bind_p (stmt))
720 dta.gsi = NULL;
721 walk_tree (gimple_debug_bind_get_value_ptr (stmt),
722 eliminate_local_variables_1, &dta.info, NULL);
723 if (dta.reset)
725 gimple_debug_bind_reset_value (stmt);
726 dta.changed = true;
729 else if (gimple_clobber_p (stmt))
731 unlink_stmt_vdef (stmt);
732 stmt = gimple_build_nop ();
733 gsi_replace (gsi, stmt, false);
734 dta.changed = true;
736 else
738 dta.gsi = gsi;
739 walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
742 if (dta.changed)
743 update_stmt (stmt);
746 /* Eliminates the references to local variables from the single entry
747 single exit region between the ENTRY and EXIT edges.
749 This includes:
750 1) Taking address of a local variable -- these are moved out of the
751 region (and temporary variable is created to hold the address if
752 necessary).
754 2) Dereferencing a local variable -- these are replaced with indirect
755 references. */
757 static void
758 eliminate_local_variables (edge entry, edge exit)
760 basic_block bb;
761 auto_vec<basic_block, 3> body;
762 unsigned i;
763 gimple_stmt_iterator gsi;
764 bool has_debug_stmt = false;
765 int_tree_htab_type decl_address (10);
766 basic_block entry_bb = entry->src;
767 basic_block exit_bb = exit->dest;
769 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
771 FOR_EACH_VEC_ELT (body, i, bb)
772 if (bb != entry_bb && bb != exit_bb)
774 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
775 if (is_gimple_debug (gsi_stmt (gsi)))
777 if (gimple_debug_bind_p (gsi_stmt (gsi)))
778 has_debug_stmt = true;
780 else
781 eliminate_local_variables_stmt (entry, &gsi, &decl_address);
784 if (has_debug_stmt)
785 FOR_EACH_VEC_ELT (body, i, bb)
786 if (bb != entry_bb && bb != exit_bb)
787 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
788 if (gimple_debug_bind_p (gsi_stmt (gsi)))
789 eliminate_local_variables_stmt (entry, &gsi, &decl_address);
792 /* Returns true if expression EXPR is not defined between ENTRY and
793 EXIT, i.e. if all its operands are defined outside of the region. */
795 static bool
796 expr_invariant_in_region_p (edge entry, edge exit, tree expr)
798 basic_block entry_bb = entry->src;
799 basic_block exit_bb = exit->dest;
800 basic_block def_bb;
802 if (is_gimple_min_invariant (expr))
803 return true;
805 if (TREE_CODE (expr) == SSA_NAME)
807 def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
808 if (def_bb
809 && dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)
810 && !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))
811 return false;
813 return true;
816 return false;
819 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
820 The copies are stored to NAME_COPIES, if NAME was already duplicated,
821 its duplicate stored in NAME_COPIES is returned.
823 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
824 duplicated, storing the copies in DECL_COPIES. */
826 static tree
827 separate_decls_in_region_name (tree name, name_to_copy_table_type *name_copies,
828 int_tree_htab_type *decl_copies,
829 bool copy_name_p)
831 tree copy, var, var_copy;
832 unsigned idx, uid, nuid;
833 struct int_tree_map ielt;
834 struct name_to_copy_elt elt, *nelt;
835 name_to_copy_elt **slot;
836 int_tree_map *dslot;
838 if (TREE_CODE (name) != SSA_NAME)
839 return name;
841 idx = SSA_NAME_VERSION (name);
842 elt.version = idx;
843 slot = name_copies->find_slot_with_hash (&elt, idx,
844 copy_name_p ? INSERT : NO_INSERT);
845 if (slot && *slot)
846 return (*slot)->new_name;
848 if (copy_name_p)
850 copy = duplicate_ssa_name (name, NULL);
851 nelt = XNEW (struct name_to_copy_elt);
852 nelt->version = idx;
853 nelt->new_name = copy;
854 nelt->field = NULL_TREE;
855 *slot = nelt;
857 else
859 gcc_assert (!slot);
860 copy = name;
863 var = SSA_NAME_VAR (name);
864 if (!var)
865 return copy;
867 uid = DECL_UID (var);
868 ielt.uid = uid;
869 dslot = decl_copies->find_slot_with_hash (ielt, uid, INSERT);
870 if (!dslot->to)
872 var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
873 DECL_GIMPLE_REG_P (var_copy) = DECL_GIMPLE_REG_P (var);
874 dslot->uid = uid;
875 dslot->to = var_copy;
877 /* Ensure that when we meet this decl next time, we won't duplicate
878 it again. */
879 nuid = DECL_UID (var_copy);
880 ielt.uid = nuid;
881 dslot = decl_copies->find_slot_with_hash (ielt, nuid, INSERT);
882 gcc_assert (!dslot->to);
883 dslot->uid = nuid;
884 dslot->to = var_copy;
886 else
887 var_copy = dslot->to;
889 replace_ssa_name_symbol (copy, var_copy);
890 return copy;
893 /* Finds the ssa names used in STMT that are defined outside the
894 region between ENTRY and EXIT and replaces such ssa names with
895 their duplicates. The duplicates are stored to NAME_COPIES. Base
896 decls of all ssa names used in STMT (including those defined in
897 LOOP) are replaced with the new temporary variables; the
898 replacement decls are stored in DECL_COPIES. */
900 static void
901 separate_decls_in_region_stmt (edge entry, edge exit, gimple *stmt,
902 name_to_copy_table_type *name_copies,
903 int_tree_htab_type *decl_copies)
905 use_operand_p use;
906 def_operand_p def;
907 ssa_op_iter oi;
908 tree name, copy;
909 bool copy_name_p;
911 FOR_EACH_PHI_OR_STMT_DEF (def, stmt, oi, SSA_OP_DEF)
913 name = DEF_FROM_PTR (def);
914 gcc_assert (TREE_CODE (name) == SSA_NAME);
915 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
916 false);
917 gcc_assert (copy == name);
920 FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
922 name = USE_FROM_PTR (use);
923 if (TREE_CODE (name) != SSA_NAME)
924 continue;
926 copy_name_p = expr_invariant_in_region_p (entry, exit, name);
927 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
928 copy_name_p);
929 SET_USE (use, copy);
933 /* Finds the ssa names used in STMT that are defined outside the
934 region between ENTRY and EXIT and replaces such ssa names with
935 their duplicates. The duplicates are stored to NAME_COPIES. Base
936 decls of all ssa names used in STMT (including those defined in
937 LOOP) are replaced with the new temporary variables; the
938 replacement decls are stored in DECL_COPIES. */
940 static bool
941 separate_decls_in_region_debug (gimple *stmt,
942 name_to_copy_table_type *name_copies,
943 int_tree_htab_type *decl_copies)
945 use_operand_p use;
946 ssa_op_iter oi;
947 tree var, name;
948 struct int_tree_map ielt;
949 struct name_to_copy_elt elt;
950 name_to_copy_elt **slot;
951 int_tree_map *dslot;
953 if (gimple_debug_bind_p (stmt))
954 var = gimple_debug_bind_get_var (stmt);
955 else if (gimple_debug_source_bind_p (stmt))
956 var = gimple_debug_source_bind_get_var (stmt);
957 else
958 return true;
959 if (TREE_CODE (var) == DEBUG_EXPR_DECL || TREE_CODE (var) == LABEL_DECL)
960 return true;
961 gcc_assert (DECL_P (var) && SSA_VAR_P (var));
962 ielt.uid = DECL_UID (var);
963 dslot = decl_copies->find_slot_with_hash (ielt, ielt.uid, NO_INSERT);
964 if (!dslot)
965 return true;
966 if (gimple_debug_bind_p (stmt))
967 gimple_debug_bind_set_var (stmt, dslot->to);
968 else if (gimple_debug_source_bind_p (stmt))
969 gimple_debug_source_bind_set_var (stmt, dslot->to);
971 FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
973 name = USE_FROM_PTR (use);
974 if (TREE_CODE (name) != SSA_NAME)
975 continue;
977 elt.version = SSA_NAME_VERSION (name);
978 slot = name_copies->find_slot_with_hash (&elt, elt.version, NO_INSERT);
979 if (!slot)
981 gimple_debug_bind_reset_value (stmt);
982 update_stmt (stmt);
983 break;
986 SET_USE (use, (*slot)->new_name);
989 return false;
992 /* Callback for htab_traverse. Adds a field corresponding to the reduction
993 specified in SLOT. The type is passed in DATA. */
996 add_field_for_reduction (reduction_info **slot, tree type)
999 struct reduction_info *const red = *slot;
1000 tree var = reduc_stmt_res (red->reduc_stmt);
1001 tree field = build_decl (gimple_location (red->reduc_stmt), FIELD_DECL,
1002 SSA_NAME_IDENTIFIER (var), TREE_TYPE (var));
1004 insert_field_into_struct (type, field);
1006 red->field = field;
1008 return 1;
1011 /* Callback for htab_traverse. Adds a field corresponding to a ssa name
1012 described in SLOT. The type is passed in DATA. */
1015 add_field_for_name (name_to_copy_elt **slot, tree type)
1017 struct name_to_copy_elt *const elt = *slot;
1018 tree name = ssa_name (elt->version);
1019 tree field = build_decl (UNKNOWN_LOCATION,
1020 FIELD_DECL, SSA_NAME_IDENTIFIER (name),
1021 TREE_TYPE (name));
1023 insert_field_into_struct (type, field);
1024 elt->field = field;
1026 return 1;
1029 /* Callback for htab_traverse. A local result is the intermediate result
1030 computed by a single
1031 thread, or the initial value in case no iteration was executed.
1032 This function creates a phi node reflecting these values.
1033 The phi's result will be stored in NEW_PHI field of the
1034 reduction's data structure. */
1037 create_phi_for_local_result (reduction_info **slot, struct loop *loop)
1039 struct reduction_info *const reduc = *slot;
1040 edge e;
1041 gphi *new_phi;
1042 basic_block store_bb, continue_bb;
1043 tree local_res;
1044 location_t locus;
1046 /* STORE_BB is the block where the phi
1047 should be stored. It is the destination of the loop exit.
1048 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
1049 continue_bb = single_pred (loop->latch);
1050 store_bb = FALLTHRU_EDGE (continue_bb)->dest;
1052 /* STORE_BB has two predecessors. One coming from the loop
1053 (the reduction's result is computed at the loop),
1054 and another coming from a block preceding the loop,
1055 when no iterations
1056 are executed (the initial value should be taken). */
1057 if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (continue_bb))
1058 e = EDGE_PRED (store_bb, 1);
1059 else
1060 e = EDGE_PRED (store_bb, 0);
1061 tree lhs = reduc_stmt_res (reduc->reduc_stmt);
1062 local_res = copy_ssa_name (lhs);
1063 locus = gimple_location (reduc->reduc_stmt);
1064 new_phi = create_phi_node (local_res, store_bb);
1065 add_phi_arg (new_phi, reduc->init, e, locus);
1066 add_phi_arg (new_phi, lhs, FALLTHRU_EDGE (continue_bb), locus);
1067 reduc->new_phi = new_phi;
1069 return 1;
1072 struct clsn_data
1074 tree store;
1075 tree load;
1077 basic_block store_bb;
1078 basic_block load_bb;
1081 /* Callback for htab_traverse. Create an atomic instruction for the
1082 reduction described in SLOT.
1083 DATA annotates the place in memory the atomic operation relates to,
1084 and the basic block it needs to be generated in. */
1087 create_call_for_reduction_1 (reduction_info **slot, struct clsn_data *clsn_data)
1089 struct reduction_info *const reduc = *slot;
1090 gimple_stmt_iterator gsi;
1091 tree type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
1092 tree load_struct;
1093 basic_block bb;
1094 basic_block new_bb;
1095 edge e;
1096 tree t, addr, ref, x;
1097 tree tmp_load, name;
1098 gimple *load;
1100 if (reduc->reduc_addr == NULL_TREE)
1102 load_struct = build_simple_mem_ref (clsn_data->load);
1103 t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
1105 addr = build_addr (t);
1107 else
1109 /* Set the address for the atomic store. */
1110 addr = reduc->reduc_addr;
1112 /* Remove the non-atomic store '*addr = sum'. */
1113 tree res = PHI_RESULT (reduc->keep_res);
1114 use_operand_p use_p;
1115 gimple *stmt;
1116 bool single_use_p = single_imm_use (res, &use_p, &stmt);
1117 gcc_assert (single_use_p);
1118 replace_uses_by (gimple_vdef (stmt),
1119 gimple_vuse (stmt));
1120 gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
1121 gsi_remove (&gsi, true);
1124 /* Create phi node. */
1125 bb = clsn_data->load_bb;
1127 gsi = gsi_last_bb (bb);
1128 e = split_block (bb, gsi_stmt (gsi));
1129 new_bb = e->dest;
1131 tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)));
1132 tmp_load = make_ssa_name (tmp_load);
1133 load = gimple_build_omp_atomic_load (tmp_load, addr,
1134 OMP_MEMORY_ORDER_RELAXED);
1135 SSA_NAME_DEF_STMT (tmp_load) = load;
1136 gsi = gsi_start_bb (new_bb);
1137 gsi_insert_after (&gsi, load, GSI_NEW_STMT);
1139 e = split_block (new_bb, load);
1140 new_bb = e->dest;
1141 gsi = gsi_start_bb (new_bb);
1142 ref = tmp_load;
1143 x = fold_build2 (reduc->reduction_code,
1144 TREE_TYPE (PHI_RESULT (reduc->new_phi)), ref,
1145 PHI_RESULT (reduc->new_phi));
1147 name = force_gimple_operand_gsi (&gsi, x, true, NULL_TREE, true,
1148 GSI_CONTINUE_LINKING);
1150 gimple *store = gimple_build_omp_atomic_store (name,
1151 OMP_MEMORY_ORDER_RELAXED);
1152 gsi_insert_after (&gsi, store, GSI_NEW_STMT);
1153 return 1;
1156 /* Create the atomic operation at the join point of the threads.
1157 REDUCTION_LIST describes the reductions in the LOOP.
1158 LD_ST_DATA describes the shared data structure where
1159 shared data is stored in and loaded from. */
1160 static void
1161 create_call_for_reduction (struct loop *loop,
1162 reduction_info_table_type *reduction_list,
1163 struct clsn_data *ld_st_data)
1165 reduction_list->traverse <struct loop *, create_phi_for_local_result> (loop);
1166 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
1167 basic_block continue_bb = single_pred (loop->latch);
1168 ld_st_data->load_bb = FALLTHRU_EDGE (continue_bb)->dest;
1169 reduction_list
1170 ->traverse <struct clsn_data *, create_call_for_reduction_1> (ld_st_data);
1173 /* Callback for htab_traverse. Loads the final reduction value at the
1174 join point of all threads, and inserts it in the right place. */
1177 create_loads_for_reductions (reduction_info **slot, struct clsn_data *clsn_data)
1179 struct reduction_info *const red = *slot;
1180 gimple *stmt;
1181 gimple_stmt_iterator gsi;
1182 tree type = TREE_TYPE (reduc_stmt_res (red->reduc_stmt));
1183 tree load_struct;
1184 tree name;
1185 tree x;
1187 /* If there's no exit phi, the result of the reduction is unused. */
1188 if (red->keep_res == NULL)
1189 return 1;
1191 gsi = gsi_after_labels (clsn_data->load_bb);
1192 load_struct = build_simple_mem_ref (clsn_data->load);
1193 load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
1194 NULL_TREE);
1196 x = load_struct;
1197 name = PHI_RESULT (red->keep_res);
1198 stmt = gimple_build_assign (name, x);
1200 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1202 for (gsi = gsi_start_phis (gimple_bb (red->keep_res));
1203 !gsi_end_p (gsi); gsi_next (&gsi))
1204 if (gsi_stmt (gsi) == red->keep_res)
1206 remove_phi_node (&gsi, false);
1207 return 1;
1209 gcc_unreachable ();
1212 /* Load the reduction result that was stored in LD_ST_DATA.
1213 REDUCTION_LIST describes the list of reductions that the
1214 loads should be generated for. */
1215 static void
1216 create_final_loads_for_reduction (reduction_info_table_type *reduction_list,
1217 struct clsn_data *ld_st_data)
1219 gimple_stmt_iterator gsi;
1220 tree t;
1221 gimple *stmt;
1223 gsi = gsi_after_labels (ld_st_data->load_bb);
1224 t = build_fold_addr_expr (ld_st_data->store);
1225 stmt = gimple_build_assign (ld_st_data->load, t);
1227 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1229 reduction_list
1230 ->traverse <struct clsn_data *, create_loads_for_reductions> (ld_st_data);
1234 /* Callback for htab_traverse. Store the neutral value for the
1235 particular reduction's operation, e.g. 0 for PLUS_EXPR,
1236 1 for MULT_EXPR, etc. into the reduction field.
1237 The reduction is specified in SLOT. The store information is
1238 passed in DATA. */
1241 create_stores_for_reduction (reduction_info **slot, struct clsn_data *clsn_data)
1243 struct reduction_info *const red = *slot;
1244 tree t;
1245 gimple *stmt;
1246 gimple_stmt_iterator gsi;
1247 tree type = TREE_TYPE (reduc_stmt_res (red->reduc_stmt));
1249 gsi = gsi_last_bb (clsn_data->store_bb);
1250 t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE);
1251 stmt = gimple_build_assign (t, red->initial_value);
1252 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1254 return 1;
1257 /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
1258 store to a field of STORE in STORE_BB for the ssa name and its duplicate
1259 specified in SLOT. */
1262 create_loads_and_stores_for_name (name_to_copy_elt **slot,
1263 struct clsn_data *clsn_data)
1265 struct name_to_copy_elt *const elt = *slot;
1266 tree t;
1267 gimple *stmt;
1268 gimple_stmt_iterator gsi;
1269 tree type = TREE_TYPE (elt->new_name);
1270 tree load_struct;
1272 gsi = gsi_last_bb (clsn_data->store_bb);
1273 t = build3 (COMPONENT_REF, type, clsn_data->store, elt->field, NULL_TREE);
1274 stmt = gimple_build_assign (t, ssa_name (elt->version));
1275 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1277 gsi = gsi_last_bb (clsn_data->load_bb);
1278 load_struct = build_simple_mem_ref (clsn_data->load);
1279 t = build3 (COMPONENT_REF, type, load_struct, elt->field, NULL_TREE);
1280 stmt = gimple_build_assign (elt->new_name, t);
1281 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1283 return 1;
1286 /* Moves all the variables used in LOOP and defined outside of it (including
1287 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1288 name) to a structure created for this purpose. The code
1290 while (1)
1292 use (a);
1293 use (b);
1296 is transformed this way:
1298 bb0:
1299 old.a = a;
1300 old.b = b;
1302 bb1:
1303 a' = new->a;
1304 b' = new->b;
1305 while (1)
1307 use (a');
1308 use (b');
1311 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1312 pointer `new' is intentionally not initialized (the loop will be split to a
1313 separate function later, and `new' will be initialized from its arguments).
1314 LD_ST_DATA holds information about the shared data structure used to pass
1315 information among the threads. It is initialized here, and
1316 gen_parallel_loop will pass it to create_call_for_reduction that
1317 needs this information. REDUCTION_LIST describes the reductions
1318 in LOOP. */
1320 static void
1321 separate_decls_in_region (edge entry, edge exit,
1322 reduction_info_table_type *reduction_list,
1323 tree *arg_struct, tree *new_arg_struct,
1324 struct clsn_data *ld_st_data)
1327 basic_block bb1 = split_edge (entry);
1328 basic_block bb0 = single_pred (bb1);
1329 name_to_copy_table_type name_copies (10);
1330 int_tree_htab_type decl_copies (10);
1331 unsigned i;
1332 tree type, type_name, nvar;
1333 gimple_stmt_iterator gsi;
1334 struct clsn_data clsn_data;
1335 auto_vec<basic_block, 3> body;
1336 basic_block bb;
1337 basic_block entry_bb = bb1;
1338 basic_block exit_bb = exit->dest;
1339 bool has_debug_stmt = false;
1341 entry = single_succ_edge (entry_bb);
1342 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
1344 FOR_EACH_VEC_ELT (body, i, bb)
1346 if (bb != entry_bb && bb != exit_bb)
1348 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1349 separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
1350 &name_copies, &decl_copies);
1352 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1354 gimple *stmt = gsi_stmt (gsi);
1356 if (is_gimple_debug (stmt))
1357 has_debug_stmt = true;
1358 else
1359 separate_decls_in_region_stmt (entry, exit, stmt,
1360 &name_copies, &decl_copies);
1365 /* Now process debug bind stmts. We must not create decls while
1366 processing debug stmts, so we defer their processing so as to
1367 make sure we will have debug info for as many variables as
1368 possible (all of those that were dealt with in the loop above),
1369 and discard those for which we know there's nothing we can
1370 do. */
1371 if (has_debug_stmt)
1372 FOR_EACH_VEC_ELT (body, i, bb)
1373 if (bb != entry_bb && bb != exit_bb)
1375 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
1377 gimple *stmt = gsi_stmt (gsi);
1379 if (is_gimple_debug (stmt))
1381 if (separate_decls_in_region_debug (stmt, &name_copies,
1382 &decl_copies))
1384 gsi_remove (&gsi, true);
1385 continue;
1389 gsi_next (&gsi);
1393 if (name_copies.elements () == 0 && reduction_list->elements () == 0)
1395 /* It may happen that there is nothing to copy (if there are only
1396 loop carried and external variables in the loop). */
1397 *arg_struct = NULL;
1398 *new_arg_struct = NULL;
1400 else
1402 /* Create the type for the structure to store the ssa names to. */
1403 type = lang_hooks.types.make_type (RECORD_TYPE);
1404 type_name = build_decl (UNKNOWN_LOCATION,
1405 TYPE_DECL, create_tmp_var_name (".paral_data"),
1406 type);
1407 TYPE_NAME (type) = type_name;
1409 name_copies.traverse <tree, add_field_for_name> (type);
1410 if (reduction_list && reduction_list->elements () > 0)
1412 /* Create the fields for reductions. */
1413 reduction_list->traverse <tree, add_field_for_reduction> (type);
1415 layout_type (type);
1417 /* Create the loads and stores. */
1418 *arg_struct = create_tmp_var (type, ".paral_data_store");
1419 nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load");
1420 *new_arg_struct = make_ssa_name (nvar);
1422 ld_st_data->store = *arg_struct;
1423 ld_st_data->load = *new_arg_struct;
1424 ld_st_data->store_bb = bb0;
1425 ld_st_data->load_bb = bb1;
1427 name_copies
1428 .traverse <struct clsn_data *, create_loads_and_stores_for_name>
1429 (ld_st_data);
1431 /* Load the calculation from memory (after the join of the threads). */
1433 if (reduction_list && reduction_list->elements () > 0)
1435 reduction_list
1436 ->traverse <struct clsn_data *, create_stores_for_reduction>
1437 (ld_st_data);
1438 clsn_data.load = make_ssa_name (nvar);
1439 clsn_data.load_bb = exit->dest;
1440 clsn_data.store = ld_st_data->store;
1441 create_final_loads_for_reduction (reduction_list, &clsn_data);
1446 /* Returns true if FN was created to run in parallel. */
1448 bool
1449 parallelized_function_p (tree fndecl)
1451 cgraph_node *node = cgraph_node::get (fndecl);
1452 gcc_assert (node != NULL);
1453 return node->parallelized_function;
1456 /* Creates and returns an empty function that will receive the body of
1457 a parallelized loop. */
1459 static tree
1460 create_loop_fn (location_t loc)
1462 char buf[100];
1463 char *tname;
1464 tree decl, type, name, t;
1465 struct function *act_cfun = cfun;
1466 static unsigned loopfn_num;
1468 loc = LOCATION_LOCUS (loc);
1469 snprintf (buf, 100, "%s.$loopfn", current_function_name ());
1470 ASM_FORMAT_PRIVATE_NAME (tname, buf, loopfn_num++);
1471 clean_symbol_name (tname);
1472 name = get_identifier (tname);
1473 type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
1475 decl = build_decl (loc, FUNCTION_DECL, name, type);
1476 TREE_STATIC (decl) = 1;
1477 TREE_USED (decl) = 1;
1478 DECL_ARTIFICIAL (decl) = 1;
1479 DECL_IGNORED_P (decl) = 0;
1480 TREE_PUBLIC (decl) = 0;
1481 DECL_UNINLINABLE (decl) = 1;
1482 DECL_EXTERNAL (decl) = 0;
1483 DECL_CONTEXT (decl) = NULL_TREE;
1484 DECL_INITIAL (decl) = make_node (BLOCK);
1485 BLOCK_SUPERCONTEXT (DECL_INITIAL (decl)) = decl;
1487 t = build_decl (loc, RESULT_DECL, NULL_TREE, void_type_node);
1488 DECL_ARTIFICIAL (t) = 1;
1489 DECL_IGNORED_P (t) = 1;
1490 DECL_RESULT (decl) = t;
1492 t = build_decl (loc, PARM_DECL, get_identifier (".paral_data_param"),
1493 ptr_type_node);
1494 DECL_ARTIFICIAL (t) = 1;
1495 DECL_ARG_TYPE (t) = ptr_type_node;
1496 DECL_CONTEXT (t) = decl;
1497 TREE_USED (t) = 1;
1498 DECL_ARGUMENTS (decl) = t;
1500 allocate_struct_function (decl, false);
1502 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1503 it. */
1504 set_cfun (act_cfun);
1506 return decl;
1509 /* Replace uses of NAME by VAL in block BB. */
1511 static void
1512 replace_uses_in_bb_by (tree name, tree val, basic_block bb)
1514 gimple *use_stmt;
1515 imm_use_iterator imm_iter;
1517 FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, name)
1519 if (gimple_bb (use_stmt) != bb)
1520 continue;
1522 use_operand_p use_p;
1523 FOR_EACH_IMM_USE_ON_STMT (use_p, imm_iter)
1524 SET_USE (use_p, val);
1528 /* Do transformation from:
1530 <bb preheader>:
1532 goto <bb header>
1534 <bb header>:
1535 ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1536 sum_a = PHI <sum_init (preheader), sum_b (latch)>
1538 use (ivtmp_a)
1540 sum_b = sum_a + sum_update
1542 if (ivtmp_a < n)
1543 goto <bb latch>;
1544 else
1545 goto <bb exit>;
1547 <bb latch>:
1548 ivtmp_b = ivtmp_a + 1;
1549 goto <bb header>
1551 <bb exit>:
1552 sum_z = PHI <sum_b (cond[1]), ...>
1554 [1] Where <bb cond> is single_pred (bb latch); In the simplest case,
1555 that's <bb header>.
1559 <bb preheader>:
1561 goto <bb newheader>
1563 <bb header>:
1564 ivtmp_a = PHI <ivtmp_c (latch)>
1565 sum_a = PHI <sum_c (latch)>
1567 use (ivtmp_a)
1569 sum_b = sum_a + sum_update
1571 goto <bb latch>;
1573 <bb newheader>:
1574 ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1575 sum_c = PHI <sum_init (preheader), sum_b (latch)>
1576 if (ivtmp_c < n + 1)
1577 goto <bb header>;
1578 else
1579 goto <bb newexit>;
1581 <bb latch>:
1582 ivtmp_b = ivtmp_a + 1;
1583 goto <bb newheader>
1585 <bb newexit>:
1586 sum_y = PHI <sum_c (newheader)>
1588 <bb exit>:
1589 sum_z = PHI <sum_y (newexit), ...>
1592 In unified diff format:
1594 <bb preheader>:
1596 - goto <bb header>
1597 + goto <bb newheader>
1599 <bb header>:
1600 - ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1601 - sum_a = PHI <sum_init (preheader), sum_b (latch)>
1602 + ivtmp_a = PHI <ivtmp_c (latch)>
1603 + sum_a = PHI <sum_c (latch)>
1605 use (ivtmp_a)
1607 sum_b = sum_a + sum_update
1609 - if (ivtmp_a < n)
1610 - goto <bb latch>;
1611 + goto <bb latch>;
1613 + <bb newheader>:
1614 + ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1615 + sum_c = PHI <sum_init (preheader), sum_b (latch)>
1616 + if (ivtmp_c < n + 1)
1617 + goto <bb header>;
1618 else
1619 goto <bb exit>;
1621 <bb latch>:
1622 ivtmp_b = ivtmp_a + 1;
1623 - goto <bb header>
1624 + goto <bb newheader>
1626 + <bb newexit>:
1627 + sum_y = PHI <sum_c (newheader)>
1629 <bb exit>:
1630 - sum_z = PHI <sum_b (cond[1]), ...>
1631 + sum_z = PHI <sum_y (newexit), ...>
1633 Note: the example does not show any virtual phis, but these are handled more
1634 or less as reductions.
1637 Moves the exit condition of LOOP to the beginning of its header.
1638 REDUCTION_LIST describes the reductions in LOOP. BOUND is the new loop
1639 bound. */
1641 static void
1642 transform_to_exit_first_loop_alt (struct loop *loop,
1643 reduction_info_table_type *reduction_list,
1644 tree bound)
1646 basic_block header = loop->header;
1647 basic_block latch = loop->latch;
1648 edge exit = single_dom_exit (loop);
1649 basic_block exit_block = exit->dest;
1650 gcond *cond_stmt = as_a <gcond *> (last_stmt (exit->src));
1651 tree control = gimple_cond_lhs (cond_stmt);
1652 edge e;
1654 /* Rewriting virtuals into loop-closed ssa normal form makes this
1655 transformation simpler. It also ensures that the virtuals are in
1656 loop-closed ssa normal from after the transformation, which is required by
1657 create_parallel_loop. */
1658 rewrite_virtuals_into_loop_closed_ssa (loop);
1660 /* Create the new_header block. */
1661 basic_block new_header = split_block_before_cond_jump (exit->src);
1662 edge edge_at_split = single_pred_edge (new_header);
1664 /* Redirect entry edge to new_header. */
1665 edge entry = loop_preheader_edge (loop);
1666 e = redirect_edge_and_branch (entry, new_header);
1667 gcc_assert (e == entry);
1669 /* Redirect post_inc_edge to new_header. */
1670 edge post_inc_edge = single_succ_edge (latch);
1671 e = redirect_edge_and_branch (post_inc_edge, new_header);
1672 gcc_assert (e == post_inc_edge);
1674 /* Redirect post_cond_edge to header. */
1675 edge post_cond_edge = single_pred_edge (latch);
1676 e = redirect_edge_and_branch (post_cond_edge, header);
1677 gcc_assert (e == post_cond_edge);
1679 /* Redirect edge_at_split to latch. */
1680 e = redirect_edge_and_branch (edge_at_split, latch);
1681 gcc_assert (e == edge_at_split);
1683 /* Set the new loop bound. */
1684 gimple_cond_set_rhs (cond_stmt, bound);
1685 update_stmt (cond_stmt);
1687 /* Repair the ssa. */
1688 vec<edge_var_map> *v = redirect_edge_var_map_vector (post_inc_edge);
1689 edge_var_map *vm;
1690 gphi_iterator gsi;
1691 int i;
1692 for (gsi = gsi_start_phis (header), i = 0;
1693 !gsi_end_p (gsi) && v->iterate (i, &vm);
1694 gsi_next (&gsi), i++)
1696 gphi *phi = gsi.phi ();
1697 tree res_a = PHI_RESULT (phi);
1699 /* Create new phi. */
1700 tree res_c = copy_ssa_name (res_a, phi);
1701 gphi *nphi = create_phi_node (res_c, new_header);
1703 /* Replace ivtmp_a with ivtmp_c in condition 'if (ivtmp_a < n)'. */
1704 replace_uses_in_bb_by (res_a, res_c, new_header);
1706 /* Replace ivtmp/sum_b with ivtmp/sum_c in header phi. */
1707 add_phi_arg (phi, res_c, post_cond_edge, UNKNOWN_LOCATION);
1709 /* Replace sum_b with sum_c in exit phi. */
1710 tree res_b = redirect_edge_var_map_def (vm);
1711 replace_uses_in_bb_by (res_b, res_c, exit_block);
1713 struct reduction_info *red = reduction_phi (reduction_list, phi);
1714 gcc_assert (virtual_operand_p (res_a)
1715 || res_a == control
1716 || red != NULL);
1718 if (red)
1720 /* Register the new reduction phi. */
1721 red->reduc_phi = nphi;
1722 gimple_set_uid (red->reduc_phi, red->reduc_version);
1725 gcc_assert (gsi_end_p (gsi) && !v->iterate (i, &vm));
1727 /* Set the preheader argument of the new phis to ivtmp/sum_init. */
1728 flush_pending_stmts (entry);
1730 /* Set the latch arguments of the new phis to ivtmp/sum_b. */
1731 flush_pending_stmts (post_inc_edge);
1734 basic_block new_exit_block = NULL;
1735 if (!single_pred_p (exit->dest))
1737 /* Create a new empty exit block, inbetween the new loop header and the
1738 old exit block. The function separate_decls_in_region needs this block
1739 to insert code that is active on loop exit, but not any other path. */
1740 new_exit_block = split_edge (exit);
1743 /* Insert and register the reduction exit phis. */
1744 for (gphi_iterator gsi = gsi_start_phis (exit_block);
1745 !gsi_end_p (gsi);
1746 gsi_next (&gsi))
1748 gphi *phi = gsi.phi ();
1749 gphi *nphi = NULL;
1750 tree res_z = PHI_RESULT (phi);
1751 tree res_c;
1753 if (new_exit_block != NULL)
1755 /* Now that we have a new exit block, duplicate the phi of the old
1756 exit block in the new exit block to preserve loop-closed ssa. */
1757 edge succ_new_exit_block = single_succ_edge (new_exit_block);
1758 edge pred_new_exit_block = single_pred_edge (new_exit_block);
1759 tree res_y = copy_ssa_name (res_z, phi);
1760 nphi = create_phi_node (res_y, new_exit_block);
1761 res_c = PHI_ARG_DEF_FROM_EDGE (phi, succ_new_exit_block);
1762 add_phi_arg (nphi, res_c, pred_new_exit_block, UNKNOWN_LOCATION);
1763 add_phi_arg (phi, res_y, succ_new_exit_block, UNKNOWN_LOCATION);
1765 else
1766 res_c = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1768 if (virtual_operand_p (res_z))
1769 continue;
1771 gimple *reduc_phi = SSA_NAME_DEF_STMT (res_c);
1772 struct reduction_info *red = reduction_phi (reduction_list, reduc_phi);
1773 if (red != NULL)
1774 red->keep_res = (nphi != NULL
1775 ? nphi
1776 : phi);
1779 /* We're going to cancel the loop at the end of gen_parallel_loop, but until
1780 then we're still using some fields, so only bother about fields that are
1781 still used: header and latch.
1782 The loop has a new header bb, so we update it. The latch bb stays the
1783 same. */
1784 loop->header = new_header;
1786 /* Recalculate dominance info. */
1787 free_dominance_info (CDI_DOMINATORS);
1788 calculate_dominance_info (CDI_DOMINATORS);
1790 checking_verify_ssa (true, true);
1793 /* Tries to moves the exit condition of LOOP to the beginning of its header
1794 without duplication of the loop body. NIT is the number of iterations of the
1795 loop. REDUCTION_LIST describes the reductions in LOOP. Return true if
1796 transformation is successful. */
1798 static bool
1799 try_transform_to_exit_first_loop_alt (struct loop *loop,
1800 reduction_info_table_type *reduction_list,
1801 tree nit)
1803 /* Check whether the latch contains a single statement. */
1804 if (!gimple_seq_nondebug_singleton_p (bb_seq (loop->latch)))
1805 return false;
1807 /* Check whether the latch contains no phis. */
1808 if (phi_nodes (loop->latch) != NULL)
1809 return false;
1811 /* Check whether the latch contains the loop iv increment. */
1812 edge back = single_succ_edge (loop->latch);
1813 edge exit = single_dom_exit (loop);
1814 gcond *cond_stmt = as_a <gcond *> (last_stmt (exit->src));
1815 tree control = gimple_cond_lhs (cond_stmt);
1816 gphi *phi = as_a <gphi *> (SSA_NAME_DEF_STMT (control));
1817 tree inc_res = gimple_phi_arg_def (phi, back->dest_idx);
1818 if (gimple_bb (SSA_NAME_DEF_STMT (inc_res)) != loop->latch)
1819 return false;
1821 /* Check whether there's no code between the loop condition and the latch. */
1822 if (!single_pred_p (loop->latch)
1823 || single_pred (loop->latch) != exit->src)
1824 return false;
1826 tree alt_bound = NULL_TREE;
1827 tree nit_type = TREE_TYPE (nit);
1829 /* Figure out whether nit + 1 overflows. */
1830 if (TREE_CODE (nit) == INTEGER_CST)
1832 if (!tree_int_cst_equal (nit, TYPE_MAX_VALUE (nit_type)))
1834 alt_bound = fold_build2_loc (UNKNOWN_LOCATION, PLUS_EXPR, nit_type,
1835 nit, build_one_cst (nit_type));
1837 gcc_assert (TREE_CODE (alt_bound) == INTEGER_CST);
1838 transform_to_exit_first_loop_alt (loop, reduction_list, alt_bound);
1839 return true;
1841 else
1843 /* Todo: Figure out if we can trigger this, if it's worth to handle
1844 optimally, and if we can handle it optimally. */
1845 return false;
1849 gcc_assert (TREE_CODE (nit) == SSA_NAME);
1851 /* Variable nit is the loop bound as returned by canonicalize_loop_ivs, for an
1852 iv with base 0 and step 1 that is incremented in the latch, like this:
1854 <bb header>:
1855 # iv_1 = PHI <0 (preheader), iv_2 (latch)>
1857 if (iv_1 < nit)
1858 goto <bb latch>;
1859 else
1860 goto <bb exit>;
1862 <bb latch>:
1863 iv_2 = iv_1 + 1;
1864 goto <bb header>;
1866 The range of iv_1 is [0, nit]. The latch edge is taken for
1867 iv_1 == [0, nit - 1] and the exit edge is taken for iv_1 == nit. So the
1868 number of latch executions is equal to nit.
1870 The function max_loop_iterations gives us the maximum number of latch
1871 executions, so it gives us the maximum value of nit. */
1872 widest_int nit_max;
1873 if (!max_loop_iterations (loop, &nit_max))
1874 return false;
1876 /* Check if nit + 1 overflows. */
1877 widest_int type_max = wi::to_widest (TYPE_MAX_VALUE (nit_type));
1878 if (nit_max >= type_max)
1879 return false;
1881 gimple *def = SSA_NAME_DEF_STMT (nit);
1883 /* Try to find nit + 1, in the form of n in an assignment nit = n - 1. */
1884 if (def
1885 && is_gimple_assign (def)
1886 && gimple_assign_rhs_code (def) == PLUS_EXPR)
1888 tree op1 = gimple_assign_rhs1 (def);
1889 tree op2 = gimple_assign_rhs2 (def);
1890 if (integer_minus_onep (op1))
1891 alt_bound = op2;
1892 else if (integer_minus_onep (op2))
1893 alt_bound = op1;
1896 /* If not found, insert nit + 1. */
1897 if (alt_bound == NULL_TREE)
1899 alt_bound = fold_build2 (PLUS_EXPR, nit_type, nit,
1900 build_int_cst_type (nit_type, 1));
1902 gimple_stmt_iterator gsi = gsi_last_bb (loop_preheader_edge (loop)->src);
1904 alt_bound
1905 = force_gimple_operand_gsi (&gsi, alt_bound, true, NULL_TREE, false,
1906 GSI_CONTINUE_LINKING);
1909 transform_to_exit_first_loop_alt (loop, reduction_list, alt_bound);
1910 return true;
1913 /* Moves the exit condition of LOOP to the beginning of its header. NIT is the
1914 number of iterations of the loop. REDUCTION_LIST describes the reductions in
1915 LOOP. */
1917 static void
1918 transform_to_exit_first_loop (struct loop *loop,
1919 reduction_info_table_type *reduction_list,
1920 tree nit)
1922 basic_block *bbs, *nbbs, ex_bb, orig_header;
1923 unsigned n;
1924 bool ok;
1925 edge exit = single_dom_exit (loop), hpred;
1926 tree control, control_name, res, t;
1927 gphi *phi, *nphi;
1928 gassign *stmt;
1929 gcond *cond_stmt, *cond_nit;
1930 tree nit_1;
1932 split_block_after_labels (loop->header);
1933 orig_header = single_succ (loop->header);
1934 hpred = single_succ_edge (loop->header);
1936 cond_stmt = as_a <gcond *> (last_stmt (exit->src));
1937 control = gimple_cond_lhs (cond_stmt);
1938 gcc_assert (gimple_cond_rhs (cond_stmt) == nit);
1940 /* Make sure that we have phi nodes on exit for all loop header phis
1941 (create_parallel_loop requires that). */
1942 for (gphi_iterator gsi = gsi_start_phis (loop->header);
1943 !gsi_end_p (gsi);
1944 gsi_next (&gsi))
1946 phi = gsi.phi ();
1947 res = PHI_RESULT (phi);
1948 t = copy_ssa_name (res, phi);
1949 SET_PHI_RESULT (phi, t);
1950 nphi = create_phi_node (res, orig_header);
1951 add_phi_arg (nphi, t, hpred, UNKNOWN_LOCATION);
1953 if (res == control)
1955 gimple_cond_set_lhs (cond_stmt, t);
1956 update_stmt (cond_stmt);
1957 control = t;
1961 bbs = get_loop_body_in_dom_order (loop);
1963 for (n = 0; bbs[n] != exit->src; n++)
1964 continue;
1965 nbbs = XNEWVEC (basic_block, n);
1966 ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
1967 bbs + 1, n, nbbs);
1968 gcc_assert (ok);
1969 free (bbs);
1970 ex_bb = nbbs[0];
1971 free (nbbs);
1973 /* Other than reductions, the only gimple reg that should be copied
1974 out of the loop is the control variable. */
1975 exit = single_dom_exit (loop);
1976 control_name = NULL_TREE;
1977 for (gphi_iterator gsi = gsi_start_phis (ex_bb);
1978 !gsi_end_p (gsi); )
1980 phi = gsi.phi ();
1981 res = PHI_RESULT (phi);
1982 if (virtual_operand_p (res))
1984 gsi_next (&gsi);
1985 continue;
1988 /* Check if it is a part of reduction. If it is,
1989 keep the phi at the reduction's keep_res field. The
1990 PHI_RESULT of this phi is the resulting value of the reduction
1991 variable when exiting the loop. */
1993 if (reduction_list->elements () > 0)
1995 struct reduction_info *red;
1997 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1998 red = reduction_phi (reduction_list, SSA_NAME_DEF_STMT (val));
1999 if (red)
2001 red->keep_res = phi;
2002 gsi_next (&gsi);
2003 continue;
2006 gcc_assert (control_name == NULL_TREE
2007 && SSA_NAME_VAR (res) == SSA_NAME_VAR (control));
2008 control_name = res;
2009 remove_phi_node (&gsi, false);
2011 gcc_assert (control_name != NULL_TREE);
2013 /* Initialize the control variable to number of iterations
2014 according to the rhs of the exit condition. */
2015 gimple_stmt_iterator gsi = gsi_after_labels (ex_bb);
2016 cond_nit = as_a <gcond *> (last_stmt (exit->src));
2017 nit_1 = gimple_cond_rhs (cond_nit);
2018 nit_1 = force_gimple_operand_gsi (&gsi,
2019 fold_convert (TREE_TYPE (control_name), nit_1),
2020 false, NULL_TREE, false, GSI_SAME_STMT);
2021 stmt = gimple_build_assign (control_name, nit_1);
2022 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
2025 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
2026 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
2027 NEW_DATA is the variable that should be initialized from the argument
2028 of LOOP_FN. N_THREADS is the requested number of threads, which can be 0 if
2029 that number is to be determined later. */
2031 static void
2032 create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
2033 tree new_data, unsigned n_threads, location_t loc,
2034 bool oacc_kernels_p)
2036 gimple_stmt_iterator gsi;
2037 basic_block for_bb, ex_bb, continue_bb;
2038 tree t, param;
2039 gomp_parallel *omp_par_stmt;
2040 gimple *omp_return_stmt1, *omp_return_stmt2;
2041 gimple *phi;
2042 gcond *cond_stmt;
2043 gomp_for *for_stmt;
2044 gomp_continue *omp_cont_stmt;
2045 tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
2046 edge exit, nexit, guard, end, e;
2048 if (oacc_kernels_p)
2050 gcc_checking_assert (lookup_attribute ("oacc kernels",
2051 DECL_ATTRIBUTES (cfun->decl)));
2052 /* Indicate to later processing that this is a parallelized OpenACC
2053 kernels construct. */
2054 DECL_ATTRIBUTES (cfun->decl)
2055 = tree_cons (get_identifier ("oacc kernels parallelized"),
2056 NULL_TREE, DECL_ATTRIBUTES (cfun->decl));
2058 else
2060 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
2062 basic_block bb = loop_preheader_edge (loop)->src;
2063 basic_block paral_bb = single_pred (bb);
2064 gsi = gsi_last_bb (paral_bb);
2066 gcc_checking_assert (n_threads != 0);
2067 t = build_omp_clause (loc, OMP_CLAUSE_NUM_THREADS);
2068 OMP_CLAUSE_NUM_THREADS_EXPR (t)
2069 = build_int_cst (integer_type_node, n_threads);
2070 omp_par_stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
2071 gimple_set_location (omp_par_stmt, loc);
2073 gsi_insert_after (&gsi, omp_par_stmt, GSI_NEW_STMT);
2075 /* Initialize NEW_DATA. */
2076 if (data)
2078 gassign *assign_stmt;
2080 gsi = gsi_after_labels (bb);
2082 param = make_ssa_name (DECL_ARGUMENTS (loop_fn));
2083 assign_stmt = gimple_build_assign (param, build_fold_addr_expr (data));
2084 gsi_insert_before (&gsi, assign_stmt, GSI_SAME_STMT);
2086 assign_stmt = gimple_build_assign (new_data,
2087 fold_convert (TREE_TYPE (new_data), param));
2088 gsi_insert_before (&gsi, assign_stmt, GSI_SAME_STMT);
2091 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
2092 bb = split_loop_exit_edge (single_dom_exit (loop));
2093 gsi = gsi_last_bb (bb);
2094 omp_return_stmt1 = gimple_build_omp_return (false);
2095 gimple_set_location (omp_return_stmt1, loc);
2096 gsi_insert_after (&gsi, omp_return_stmt1, GSI_NEW_STMT);
2099 /* Extract data for GIMPLE_OMP_FOR. */
2100 gcc_assert (loop->header == single_dom_exit (loop)->src);
2101 cond_stmt = as_a <gcond *> (last_stmt (loop->header));
2103 cvar = gimple_cond_lhs (cond_stmt);
2104 cvar_base = SSA_NAME_VAR (cvar);
2105 phi = SSA_NAME_DEF_STMT (cvar);
2106 cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
2107 initvar = copy_ssa_name (cvar);
2108 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
2109 initvar);
2110 cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
2112 gsi = gsi_last_nondebug_bb (loop->latch);
2113 gcc_assert (gsi_stmt (gsi) == SSA_NAME_DEF_STMT (cvar_next));
2114 gsi_remove (&gsi, true);
2116 /* Prepare cfg. */
2117 for_bb = split_edge (loop_preheader_edge (loop));
2118 ex_bb = split_loop_exit_edge (single_dom_exit (loop));
2119 extract_true_false_edges_from_block (loop->header, &nexit, &exit);
2120 gcc_assert (exit == single_dom_exit (loop));
2122 guard = make_edge (for_bb, ex_bb, 0);
2123 /* FIXME: What is the probability? */
2124 guard->probability = profile_probability::guessed_never ();
2125 /* Split the latch edge, so LOOPS_HAVE_SIMPLE_LATCHES is still valid. */
2126 loop->latch = split_edge (single_succ_edge (loop->latch));
2127 single_pred_edge (loop->latch)->flags = 0;
2128 end = make_single_succ_edge (single_pred (loop->latch), ex_bb, EDGE_FALLTHRU);
2129 rescan_loop_exit (end, true, false);
2131 for (gphi_iterator gpi = gsi_start_phis (ex_bb);
2132 !gsi_end_p (gpi); gsi_next (&gpi))
2134 location_t locus;
2135 gphi *phi = gpi.phi ();
2136 tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2137 gimple *def_stmt = SSA_NAME_DEF_STMT (def);
2139 /* If the exit phi is not connected to a header phi in the same loop, this
2140 value is not modified in the loop, and we're done with this phi. */
2141 if (!(gimple_code (def_stmt) == GIMPLE_PHI
2142 && gimple_bb (def_stmt) == loop->header))
2144 locus = gimple_phi_arg_location_from_edge (phi, exit);
2145 add_phi_arg (phi, def, guard, locus);
2146 add_phi_arg (phi, def, end, locus);
2147 continue;
2150 gphi *stmt = as_a <gphi *> (def_stmt);
2151 def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop));
2152 locus = gimple_phi_arg_location_from_edge (stmt,
2153 loop_preheader_edge (loop));
2154 add_phi_arg (phi, def, guard, locus);
2156 def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_latch_edge (loop));
2157 locus = gimple_phi_arg_location_from_edge (stmt, loop_latch_edge (loop));
2158 add_phi_arg (phi, def, end, locus);
2160 e = redirect_edge_and_branch (exit, nexit->dest);
2161 PENDING_STMT (e) = NULL;
2163 /* Emit GIMPLE_OMP_FOR. */
2164 if (oacc_kernels_p)
2165 /* Parallelized OpenACC kernels constructs use gang parallelism. See also
2166 omp-offload.c:execute_oacc_device_lower. */
2167 t = build_omp_clause (loc, OMP_CLAUSE_GANG);
2168 else
2170 t = build_omp_clause (loc, OMP_CLAUSE_SCHEDULE);
2171 int chunk_size = PARAM_VALUE (PARAM_PARLOOPS_CHUNK_SIZE);
2172 enum PARAM_PARLOOPS_SCHEDULE_KIND schedule_type \
2173 = (enum PARAM_PARLOOPS_SCHEDULE_KIND) PARAM_VALUE (PARAM_PARLOOPS_SCHEDULE);
2174 switch (schedule_type)
2176 case PARAM_PARLOOPS_SCHEDULE_KIND_static:
2177 OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
2178 break;
2179 case PARAM_PARLOOPS_SCHEDULE_KIND_dynamic:
2180 OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_DYNAMIC;
2181 break;
2182 case PARAM_PARLOOPS_SCHEDULE_KIND_guided:
2183 OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_GUIDED;
2184 break;
2185 case PARAM_PARLOOPS_SCHEDULE_KIND_auto:
2186 OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_AUTO;
2187 chunk_size = 0;
2188 break;
2189 case PARAM_PARLOOPS_SCHEDULE_KIND_runtime:
2190 OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_RUNTIME;
2191 chunk_size = 0;
2192 break;
2193 default:
2194 gcc_unreachable ();
2196 if (chunk_size != 0)
2197 OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (t)
2198 = build_int_cst (integer_type_node, chunk_size);
2201 for_stmt = gimple_build_omp_for (NULL,
2202 (oacc_kernels_p
2203 ? GF_OMP_FOR_KIND_OACC_LOOP
2204 : GF_OMP_FOR_KIND_FOR),
2205 t, 1, NULL);
2207 gimple_cond_set_lhs (cond_stmt, cvar_base);
2208 type = TREE_TYPE (cvar);
2209 gimple_set_location (for_stmt, loc);
2210 gimple_omp_for_set_index (for_stmt, 0, initvar);
2211 gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
2212 gimple_omp_for_set_final (for_stmt, 0, gimple_cond_rhs (cond_stmt));
2213 gimple_omp_for_set_cond (for_stmt, 0, gimple_cond_code (cond_stmt));
2214 gimple_omp_for_set_incr (for_stmt, 0, build2 (PLUS_EXPR, type,
2215 cvar_base,
2216 build_int_cst (type, 1)));
2218 gsi = gsi_last_bb (for_bb);
2219 gsi_insert_after (&gsi, for_stmt, GSI_NEW_STMT);
2220 SSA_NAME_DEF_STMT (initvar) = for_stmt;
2222 /* Emit GIMPLE_OMP_CONTINUE. */
2223 continue_bb = single_pred (loop->latch);
2224 gsi = gsi_last_bb (continue_bb);
2225 omp_cont_stmt = gimple_build_omp_continue (cvar_next, cvar);
2226 gimple_set_location (omp_cont_stmt, loc);
2227 gsi_insert_after (&gsi, omp_cont_stmt, GSI_NEW_STMT);
2228 SSA_NAME_DEF_STMT (cvar_next) = omp_cont_stmt;
2230 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
2231 gsi = gsi_last_bb (ex_bb);
2232 omp_return_stmt2 = gimple_build_omp_return (true);
2233 gimple_set_location (omp_return_stmt2, loc);
2234 gsi_insert_after (&gsi, omp_return_stmt2, GSI_NEW_STMT);
2236 /* After the above dom info is hosed. Re-compute it. */
2237 free_dominance_info (CDI_DOMINATORS);
2238 calculate_dominance_info (CDI_DOMINATORS);
2241 /* Return number of phis in bb. If COUNT_VIRTUAL_P is false, don't count the
2242 virtual phi. */
2244 static unsigned int
2245 num_phis (basic_block bb, bool count_virtual_p)
2247 unsigned int nr_phis = 0;
2248 gphi_iterator gsi;
2249 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2251 if (!count_virtual_p && virtual_operand_p (PHI_RESULT (gsi.phi ())))
2252 continue;
2254 nr_phis++;
2257 return nr_phis;
2260 /* Generates code to execute the iterations of LOOP in N_THREADS
2261 threads in parallel, which can be 0 if that number is to be determined
2262 later.
2264 NITER describes number of iterations of LOOP.
2265 REDUCTION_LIST describes the reductions existent in the LOOP. */
2267 static void
2268 gen_parallel_loop (struct loop *loop,
2269 reduction_info_table_type *reduction_list,
2270 unsigned n_threads, struct tree_niter_desc *niter,
2271 bool oacc_kernels_p)
2273 tree many_iterations_cond, type, nit;
2274 tree arg_struct, new_arg_struct;
2275 gimple_seq stmts;
2276 edge entry, exit;
2277 struct clsn_data clsn_data;
2278 location_t loc;
2279 gimple *cond_stmt;
2280 unsigned int m_p_thread=2;
2282 /* From
2284 ---------------------------------------------------------------------
2285 loop
2287 IV = phi (INIT, IV + STEP)
2288 BODY1;
2289 if (COND)
2290 break;
2291 BODY2;
2293 ---------------------------------------------------------------------
2295 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
2296 we generate the following code:
2298 ---------------------------------------------------------------------
2300 if (MAY_BE_ZERO
2301 || NITER < MIN_PER_THREAD * N_THREADS)
2302 goto original;
2304 BODY1;
2305 store all local loop-invariant variables used in body of the loop to DATA.
2306 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
2307 load the variables from DATA.
2308 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
2309 BODY2;
2310 BODY1;
2311 GIMPLE_OMP_CONTINUE;
2312 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
2313 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
2314 goto end;
2316 original:
2317 loop
2319 IV = phi (INIT, IV + STEP)
2320 BODY1;
2321 if (COND)
2322 break;
2323 BODY2;
2326 end:
2330 /* Create two versions of the loop -- in the old one, we know that the
2331 number of iterations is large enough, and we will transform it into the
2332 loop that will be split to loop_fn, the new one will be used for the
2333 remaining iterations. */
2335 /* We should compute a better number-of-iterations value for outer loops.
2336 That is, if we have
2338 for (i = 0; i < n; ++i)
2339 for (j = 0; j < m; ++j)
2342 we should compute nit = n * m, not nit = n.
2343 Also may_be_zero handling would need to be adjusted. */
2345 type = TREE_TYPE (niter->niter);
2346 nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true,
2347 NULL_TREE);
2348 if (stmts)
2349 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2351 if (!oacc_kernels_p)
2353 if (loop->inner)
2354 m_p_thread=2;
2355 else
2356 m_p_thread=MIN_PER_THREAD;
2358 gcc_checking_assert (n_threads != 0);
2359 many_iterations_cond =
2360 fold_build2 (GE_EXPR, boolean_type_node,
2361 nit, build_int_cst (type, m_p_thread * n_threads - 1));
2363 many_iterations_cond
2364 = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
2365 invert_truthvalue (unshare_expr (niter->may_be_zero)),
2366 many_iterations_cond);
2367 many_iterations_cond
2368 = force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
2369 if (stmts)
2370 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
2371 if (!is_gimple_condexpr (many_iterations_cond))
2373 many_iterations_cond
2374 = force_gimple_operand (many_iterations_cond, &stmts,
2375 true, NULL_TREE);
2376 if (stmts)
2377 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop),
2378 stmts);
2381 initialize_original_copy_tables ();
2383 /* We assume that the loop usually iterates a lot. */
2384 loop_version (loop, many_iterations_cond, NULL,
2385 profile_probability::likely (),
2386 profile_probability::unlikely (),
2387 profile_probability::likely (),
2388 profile_probability::unlikely (), true);
2389 update_ssa (TODO_update_ssa);
2390 free_original_copy_tables ();
2393 /* Base all the induction variables in LOOP on a single control one. */
2394 canonicalize_loop_ivs (loop, &nit, true);
2395 if (num_phis (loop->header, false) != reduction_list->elements () + 1)
2397 /* The call to canonicalize_loop_ivs above failed to "base all the
2398 induction variables in LOOP on a single control one". Do damage
2399 control. */
2400 basic_block preheader = loop_preheader_edge (loop)->src;
2401 basic_block cond_bb = single_pred (preheader);
2402 gcond *cond = as_a <gcond *> (gsi_stmt (gsi_last_bb (cond_bb)));
2403 gimple_cond_make_true (cond);
2404 update_stmt (cond);
2405 /* We've gotten rid of the duplicate loop created by loop_version, but
2406 we can't undo whatever canonicalize_loop_ivs has done.
2407 TODO: Fix this properly by ensuring that the call to
2408 canonicalize_loop_ivs succeeds. */
2409 if (dump_file
2410 && (dump_flags & TDF_DETAILS))
2411 fprintf (dump_file, "canonicalize_loop_ivs failed for loop %d,"
2412 " aborting transformation\n", loop->num);
2413 return;
2416 /* Ensure that the exit condition is the first statement in the loop.
2417 The common case is that latch of the loop is empty (apart from the
2418 increment) and immediately follows the loop exit test. Attempt to move the
2419 entry of the loop directly before the exit check and increase the number of
2420 iterations of the loop by one. */
2421 if (try_transform_to_exit_first_loop_alt (loop, reduction_list, nit))
2423 if (dump_file
2424 && (dump_flags & TDF_DETAILS))
2425 fprintf (dump_file,
2426 "alternative exit-first loop transform succeeded"
2427 " for loop %d\n", loop->num);
2429 else
2431 if (oacc_kernels_p)
2432 n_threads = 1;
2434 /* Fall back on the method that handles more cases, but duplicates the
2435 loop body: move the exit condition of LOOP to the beginning of its
2436 header, and duplicate the part of the last iteration that gets disabled
2437 to the exit of the loop. */
2438 transform_to_exit_first_loop (loop, reduction_list, nit);
2441 /* Generate initializations for reductions. */
2442 if (reduction_list->elements () > 0)
2443 reduction_list->traverse <struct loop *, initialize_reductions> (loop);
2445 /* Eliminate the references to local variables from the loop. */
2446 gcc_assert (single_exit (loop));
2447 entry = loop_preheader_edge (loop);
2448 exit = single_dom_exit (loop);
2450 /* This rewrites the body in terms of new variables. This has already
2451 been done for oacc_kernels_p in pass_lower_omp/lower_omp (). */
2452 if (!oacc_kernels_p)
2454 eliminate_local_variables (entry, exit);
2455 /* In the old loop, move all variables non-local to the loop to a
2456 structure and back, and create separate decls for the variables used in
2457 loop. */
2458 separate_decls_in_region (entry, exit, reduction_list, &arg_struct,
2459 &new_arg_struct, &clsn_data);
2461 else
2463 arg_struct = NULL_TREE;
2464 new_arg_struct = NULL_TREE;
2465 clsn_data.load = NULL_TREE;
2466 clsn_data.load_bb = exit->dest;
2467 clsn_data.store = NULL_TREE;
2468 clsn_data.store_bb = NULL;
2471 /* Create the parallel constructs. */
2472 loc = UNKNOWN_LOCATION;
2473 cond_stmt = last_stmt (loop->header);
2474 if (cond_stmt)
2475 loc = gimple_location (cond_stmt);
2476 create_parallel_loop (loop, create_loop_fn (loc), arg_struct, new_arg_struct,
2477 n_threads, loc, oacc_kernels_p);
2478 if (reduction_list->elements () > 0)
2479 create_call_for_reduction (loop, reduction_list, &clsn_data);
2481 scev_reset ();
2483 /* Free loop bound estimations that could contain references to
2484 removed statements. */
2485 free_numbers_of_iterations_estimates (cfun);
2488 /* Returns true when LOOP contains vector phi nodes. */
2490 static bool
2491 loop_has_vector_phi_nodes (struct loop *loop ATTRIBUTE_UNUSED)
2493 unsigned i;
2494 basic_block *bbs = get_loop_body_in_dom_order (loop);
2495 gphi_iterator gsi;
2496 bool res = true;
2498 for (i = 0; i < loop->num_nodes; i++)
2499 for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
2500 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi.phi ()))) == VECTOR_TYPE)
2501 goto end;
2503 res = false;
2504 end:
2505 free (bbs);
2506 return res;
2509 /* Create a reduction_info struct, initialize it with REDUC_STMT
2510 and PHI, insert it to the REDUCTION_LIST. */
2512 static void
2513 build_new_reduction (reduction_info_table_type *reduction_list,
2514 gimple *reduc_stmt, gphi *phi)
2516 reduction_info **slot;
2517 struct reduction_info *new_reduction;
2518 enum tree_code reduction_code;
2520 gcc_assert (reduc_stmt);
2522 if (gimple_code (reduc_stmt) == GIMPLE_PHI)
2524 tree op1 = PHI_ARG_DEF (reduc_stmt, 0);
2525 gimple *def1 = SSA_NAME_DEF_STMT (op1);
2526 reduction_code = gimple_assign_rhs_code (def1);
2528 else
2529 reduction_code = gimple_assign_rhs_code (reduc_stmt);
2530 /* Check for OpenMP supported reduction. */
2531 switch (reduction_code)
2533 case PLUS_EXPR:
2534 case MULT_EXPR:
2535 case MAX_EXPR:
2536 case MIN_EXPR:
2537 case BIT_IOR_EXPR:
2538 case BIT_XOR_EXPR:
2539 case BIT_AND_EXPR:
2540 case TRUTH_OR_EXPR:
2541 case TRUTH_XOR_EXPR:
2542 case TRUTH_AND_EXPR:
2543 break;
2544 default:
2545 return;
2548 if (dump_file && (dump_flags & TDF_DETAILS))
2550 fprintf (dump_file,
2551 "Detected reduction. reduction stmt is:\n");
2552 print_gimple_stmt (dump_file, reduc_stmt, 0);
2553 fprintf (dump_file, "\n");
2556 new_reduction = XCNEW (struct reduction_info);
2558 new_reduction->reduc_stmt = reduc_stmt;
2559 new_reduction->reduc_phi = phi;
2560 new_reduction->reduc_version = SSA_NAME_VERSION (gimple_phi_result (phi));
2561 new_reduction->reduction_code = reduction_code;
2562 slot = reduction_list->find_slot (new_reduction, INSERT);
2563 *slot = new_reduction;
2566 /* Callback for htab_traverse. Sets gimple_uid of reduc_phi stmts. */
2569 set_reduc_phi_uids (reduction_info **slot, void *data ATTRIBUTE_UNUSED)
2571 struct reduction_info *const red = *slot;
2572 gimple_set_uid (red->reduc_phi, red->reduc_version);
2573 return 1;
2576 /* Return true if the type of reduction performed by STMT_INFO is suitable
2577 for this pass. */
2579 static bool
2580 valid_reduction_p (stmt_vec_info stmt_info)
2582 /* Parallelization would reassociate the operation, which isn't
2583 allowed for in-order reductions. */
2584 vect_reduction_type reduc_type = STMT_VINFO_REDUC_TYPE (stmt_info);
2585 return reduc_type != FOLD_LEFT_REDUCTION;
2588 /* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
2590 static void
2591 gather_scalar_reductions (loop_p loop, reduction_info_table_type *reduction_list)
2593 gphi_iterator gsi;
2594 loop_vec_info simple_loop_info;
2595 auto_vec<gphi *, 4> double_reduc_phis;
2596 auto_vec<gimple *, 4> double_reduc_stmts;
2598 vec_info_shared shared;
2599 simple_loop_info = vect_analyze_loop_form (loop, &shared);
2600 if (simple_loop_info == NULL)
2601 goto gather_done;
2603 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
2605 gphi *phi = gsi.phi ();
2606 affine_iv iv;
2607 tree res = PHI_RESULT (phi);
2608 bool double_reduc;
2610 if (virtual_operand_p (res))
2611 continue;
2613 if (simple_iv (loop, loop, res, &iv, true))
2614 continue;
2616 stmt_vec_info reduc_stmt_info
2617 = vect_force_simple_reduction (simple_loop_info,
2618 simple_loop_info->lookup_stmt (phi),
2619 &double_reduc, true);
2620 if (!reduc_stmt_info || !valid_reduction_p (reduc_stmt_info))
2621 continue;
2623 if (double_reduc)
2625 if (loop->inner->inner != NULL)
2626 continue;
2628 double_reduc_phis.safe_push (phi);
2629 double_reduc_stmts.safe_push (reduc_stmt_info->stmt);
2630 continue;
2633 build_new_reduction (reduction_list, reduc_stmt_info->stmt, phi);
2635 delete simple_loop_info;
2637 if (!double_reduc_phis.is_empty ())
2639 vec_info_shared shared;
2640 simple_loop_info = vect_analyze_loop_form (loop->inner, &shared);
2641 if (simple_loop_info)
2643 gphi *phi;
2644 unsigned int i;
2646 FOR_EACH_VEC_ELT (double_reduc_phis, i, phi)
2648 affine_iv iv;
2649 tree res = PHI_RESULT (phi);
2650 bool double_reduc;
2652 use_operand_p use_p;
2653 gimple *inner_stmt;
2654 bool single_use_p = single_imm_use (res, &use_p, &inner_stmt);
2655 gcc_assert (single_use_p);
2656 if (gimple_code (inner_stmt) != GIMPLE_PHI)
2657 continue;
2658 gphi *inner_phi = as_a <gphi *> (inner_stmt);
2659 if (simple_iv (loop->inner, loop->inner, PHI_RESULT (inner_phi),
2660 &iv, true))
2661 continue;
2663 stmt_vec_info inner_phi_info
2664 = simple_loop_info->lookup_stmt (inner_phi);
2665 stmt_vec_info inner_reduc_stmt_info
2666 = vect_force_simple_reduction (simple_loop_info,
2667 inner_phi_info,
2668 &double_reduc, true);
2669 gcc_assert (!double_reduc);
2670 if (!inner_reduc_stmt_info
2671 || !valid_reduction_p (inner_reduc_stmt_info))
2672 continue;
2674 build_new_reduction (reduction_list, double_reduc_stmts[i], phi);
2676 delete simple_loop_info;
2680 gather_done:
2681 if (reduction_list->elements () == 0)
2682 return;
2684 /* As gimple_uid is used by the vectorizer in between vect_analyze_loop_form
2685 and delete simple_loop_info, we can set gimple_uid of reduc_phi stmts only
2686 now. */
2687 basic_block bb;
2688 FOR_EACH_BB_FN (bb, cfun)
2689 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2690 gimple_set_uid (gsi_stmt (gsi), (unsigned int)-1);
2691 reduction_list->traverse <void *, set_reduc_phi_uids> (NULL);
2694 /* Try to initialize NITER for code generation part. */
2696 static bool
2697 try_get_loop_niter (loop_p loop, struct tree_niter_desc *niter)
2699 edge exit = single_dom_exit (loop);
2701 gcc_assert (exit);
2703 /* We need to know # of iterations, and there should be no uses of values
2704 defined inside loop outside of it, unless the values are invariants of
2705 the loop. */
2706 if (!number_of_iterations_exit (loop, exit, niter, false))
2708 if (dump_file && (dump_flags & TDF_DETAILS))
2709 fprintf (dump_file, " FAILED: number of iterations not known\n");
2710 return false;
2713 return true;
2716 /* Return the default def of the first function argument. */
2718 static tree
2719 get_omp_data_i_param (void)
2721 tree decl = DECL_ARGUMENTS (cfun->decl);
2722 gcc_assert (DECL_CHAIN (decl) == NULL_TREE);
2723 return ssa_default_def (cfun, decl);
2726 /* For PHI in loop header of LOOP, look for pattern:
2728 <bb preheader>
2729 .omp_data_i = &.omp_data_arr;
2730 addr = .omp_data_i->sum;
2731 sum_a = *addr;
2733 <bb header>:
2734 sum_b = PHI <sum_a (preheader), sum_c (latch)>
2736 and return addr. Otherwise, return NULL_TREE. */
2738 static tree
2739 find_reduc_addr (struct loop *loop, gphi *phi)
2741 edge e = loop_preheader_edge (loop);
2742 tree arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
2743 gimple *stmt = SSA_NAME_DEF_STMT (arg);
2744 if (!gimple_assign_single_p (stmt))
2745 return NULL_TREE;
2746 tree memref = gimple_assign_rhs1 (stmt);
2747 if (TREE_CODE (memref) != MEM_REF)
2748 return NULL_TREE;
2749 tree addr = TREE_OPERAND (memref, 0);
2751 gimple *stmt2 = SSA_NAME_DEF_STMT (addr);
2752 if (!gimple_assign_single_p (stmt2))
2753 return NULL_TREE;
2754 tree compref = gimple_assign_rhs1 (stmt2);
2755 if (TREE_CODE (compref) != COMPONENT_REF)
2756 return NULL_TREE;
2757 tree addr2 = TREE_OPERAND (compref, 0);
2758 if (TREE_CODE (addr2) != MEM_REF)
2759 return NULL_TREE;
2760 addr2 = TREE_OPERAND (addr2, 0);
2761 if (TREE_CODE (addr2) != SSA_NAME
2762 || addr2 != get_omp_data_i_param ())
2763 return NULL_TREE;
2765 return addr;
2768 /* Try to initialize REDUCTION_LIST for code generation part.
2769 REDUCTION_LIST describes the reductions. */
2771 static bool
2772 try_create_reduction_list (loop_p loop,
2773 reduction_info_table_type *reduction_list,
2774 bool oacc_kernels_p)
2776 edge exit = single_dom_exit (loop);
2777 gphi_iterator gsi;
2779 gcc_assert (exit);
2781 /* Try to get rid of exit phis. */
2782 final_value_replacement_loop (loop);
2784 gather_scalar_reductions (loop, reduction_list);
2787 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
2789 gphi *phi = gsi.phi ();
2790 struct reduction_info *red;
2791 imm_use_iterator imm_iter;
2792 use_operand_p use_p;
2793 gimple *reduc_phi;
2794 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2796 if (!virtual_operand_p (val))
2798 if (dump_file && (dump_flags & TDF_DETAILS))
2800 fprintf (dump_file, "phi is ");
2801 print_gimple_stmt (dump_file, phi, 0);
2802 fprintf (dump_file, "arg of phi to exit: value ");
2803 print_generic_expr (dump_file, val);
2804 fprintf (dump_file, " used outside loop\n");
2805 fprintf (dump_file,
2806 " checking if it is part of reduction pattern:\n");
2808 if (reduction_list->elements () == 0)
2810 if (dump_file && (dump_flags & TDF_DETAILS))
2811 fprintf (dump_file,
2812 " FAILED: it is not a part of reduction.\n");
2813 return false;
2815 reduc_phi = NULL;
2816 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
2818 if (!gimple_debug_bind_p (USE_STMT (use_p))
2819 && flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
2821 reduc_phi = USE_STMT (use_p);
2822 break;
2825 red = reduction_phi (reduction_list, reduc_phi);
2826 if (red == NULL)
2828 if (dump_file && (dump_flags & TDF_DETAILS))
2829 fprintf (dump_file,
2830 " FAILED: it is not a part of reduction.\n");
2831 return false;
2833 if (red->keep_res != NULL)
2835 if (dump_file && (dump_flags & TDF_DETAILS))
2836 fprintf (dump_file,
2837 " FAILED: reduction has multiple exit phis.\n");
2838 return false;
2840 red->keep_res = phi;
2841 if (dump_file && (dump_flags & TDF_DETAILS))
2843 fprintf (dump_file, "reduction phi is ");
2844 print_gimple_stmt (dump_file, red->reduc_phi, 0);
2845 fprintf (dump_file, "reduction stmt is ");
2846 print_gimple_stmt (dump_file, red->reduc_stmt, 0);
2851 /* The iterations of the loop may communicate only through bivs whose
2852 iteration space can be distributed efficiently. */
2853 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
2855 gphi *phi = gsi.phi ();
2856 tree def = PHI_RESULT (phi);
2857 affine_iv iv;
2859 if (!virtual_operand_p (def) && !simple_iv (loop, loop, def, &iv, true))
2861 struct reduction_info *red;
2863 red = reduction_phi (reduction_list, phi);
2864 if (red == NULL)
2866 if (dump_file && (dump_flags & TDF_DETAILS))
2867 fprintf (dump_file,
2868 " FAILED: scalar dependency between iterations\n");
2869 return false;
2874 if (oacc_kernels_p)
2876 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi);
2877 gsi_next (&gsi))
2879 gphi *phi = gsi.phi ();
2880 tree def = PHI_RESULT (phi);
2881 affine_iv iv;
2883 if (!virtual_operand_p (def)
2884 && !simple_iv (loop, loop, def, &iv, true))
2886 tree addr = find_reduc_addr (loop, phi);
2887 if (addr == NULL_TREE)
2888 return false;
2889 struct reduction_info *red = reduction_phi (reduction_list, phi);
2890 red->reduc_addr = addr;
2895 return true;
2898 /* Return true if LOOP contains phis with ADDR_EXPR in args. */
2900 static bool
2901 loop_has_phi_with_address_arg (struct loop *loop)
2903 basic_block *bbs = get_loop_body (loop);
2904 bool res = false;
2906 unsigned i, j;
2907 gphi_iterator gsi;
2908 for (i = 0; i < loop->num_nodes; i++)
2909 for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
2911 gphi *phi = gsi.phi ();
2912 for (j = 0; j < gimple_phi_num_args (phi); j++)
2914 tree arg = gimple_phi_arg_def (phi, j);
2915 if (TREE_CODE (arg) == ADDR_EXPR)
2917 /* This should be handled by eliminate_local_variables, but that
2918 function currently ignores phis. */
2919 res = true;
2920 goto end;
2924 end:
2925 free (bbs);
2927 return res;
2930 /* Return true if memory ref REF (corresponding to the stmt at GSI in
2931 REGIONS_BB[I]) conflicts with the statements in REGIONS_BB[I] after gsi,
2932 or the statements in REGIONS_BB[I + n]. REF_IS_STORE indicates if REF is a
2933 store. Ignore conflicts with SKIP_STMT. */
2935 static bool
2936 ref_conflicts_with_region (gimple_stmt_iterator gsi, ao_ref *ref,
2937 bool ref_is_store, vec<basic_block> region_bbs,
2938 unsigned int i, gimple *skip_stmt)
2940 basic_block bb = region_bbs[i];
2941 gsi_next (&gsi);
2943 while (true)
2945 for (; !gsi_end_p (gsi);
2946 gsi_next (&gsi))
2948 gimple *stmt = gsi_stmt (gsi);
2949 if (stmt == skip_stmt)
2951 if (dump_file)
2953 fprintf (dump_file, "skipping reduction store: ");
2954 print_gimple_stmt (dump_file, stmt, 0);
2956 continue;
2959 if (!gimple_vdef (stmt)
2960 && !gimple_vuse (stmt))
2961 continue;
2963 if (gimple_code (stmt) == GIMPLE_RETURN)
2964 continue;
2966 if (ref_is_store)
2968 if (ref_maybe_used_by_stmt_p (stmt, ref))
2970 if (dump_file)
2972 fprintf (dump_file, "Stmt ");
2973 print_gimple_stmt (dump_file, stmt, 0);
2975 return true;
2978 else
2980 if (stmt_may_clobber_ref_p_1 (stmt, ref))
2982 if (dump_file)
2984 fprintf (dump_file, "Stmt ");
2985 print_gimple_stmt (dump_file, stmt, 0);
2987 return true;
2991 i++;
2992 if (i == region_bbs.length ())
2993 break;
2994 bb = region_bbs[i];
2995 gsi = gsi_start_bb (bb);
2998 return false;
3001 /* Return true if the bbs in REGION_BBS but not in in_loop_bbs can be executed
3002 in parallel with REGION_BBS containing the loop. Return the stores of
3003 reduction results in REDUCTION_STORES. */
3005 static bool
3006 oacc_entry_exit_ok_1 (bitmap in_loop_bbs, vec<basic_block> region_bbs,
3007 reduction_info_table_type *reduction_list,
3008 bitmap reduction_stores)
3010 tree omp_data_i = get_omp_data_i_param ();
3012 unsigned i;
3013 basic_block bb;
3014 FOR_EACH_VEC_ELT (region_bbs, i, bb)
3016 if (bitmap_bit_p (in_loop_bbs, bb->index))
3017 continue;
3019 gimple_stmt_iterator gsi;
3020 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
3021 gsi_next (&gsi))
3023 gimple *stmt = gsi_stmt (gsi);
3024 gimple *skip_stmt = NULL;
3026 if (is_gimple_debug (stmt)
3027 || gimple_code (stmt) == GIMPLE_COND)
3028 continue;
3030 ao_ref ref;
3031 bool ref_is_store = false;
3032 if (gimple_assign_load_p (stmt))
3034 tree rhs = gimple_assign_rhs1 (stmt);
3035 tree base = get_base_address (rhs);
3036 if (TREE_CODE (base) == MEM_REF
3037 && operand_equal_p (TREE_OPERAND (base, 0), omp_data_i, 0))
3038 continue;
3040 tree lhs = gimple_assign_lhs (stmt);
3041 if (TREE_CODE (lhs) == SSA_NAME
3042 && has_single_use (lhs))
3044 use_operand_p use_p;
3045 gimple *use_stmt;
3046 single_imm_use (lhs, &use_p, &use_stmt);
3047 if (gimple_code (use_stmt) == GIMPLE_PHI)
3049 struct reduction_info *red;
3050 red = reduction_phi (reduction_list, use_stmt);
3051 tree val = PHI_RESULT (red->keep_res);
3052 if (has_single_use (val))
3054 single_imm_use (val, &use_p, &use_stmt);
3055 if (gimple_store_p (use_stmt))
3057 unsigned int id
3058 = SSA_NAME_VERSION (gimple_vdef (use_stmt));
3059 bitmap_set_bit (reduction_stores, id);
3060 skip_stmt = use_stmt;
3061 if (dump_file)
3063 fprintf (dump_file, "found reduction load: ");
3064 print_gimple_stmt (dump_file, stmt, 0);
3071 ao_ref_init (&ref, rhs);
3073 else if (gimple_store_p (stmt))
3075 ao_ref_init (&ref, gimple_assign_lhs (stmt));
3076 ref_is_store = true;
3078 else if (gimple_code (stmt) == GIMPLE_OMP_RETURN)
3079 continue;
3080 else if (!gimple_has_side_effects (stmt)
3081 && !gimple_could_trap_p (stmt)
3082 && !stmt_could_throw_p (cfun, stmt)
3083 && !gimple_vdef (stmt)
3084 && !gimple_vuse (stmt))
3085 continue;
3086 else if (gimple_call_internal_p (stmt, IFN_GOACC_DIM_POS))
3087 continue;
3088 else if (gimple_code (stmt) == GIMPLE_RETURN)
3089 continue;
3090 else
3092 if (dump_file)
3094 fprintf (dump_file, "Unhandled stmt in entry/exit: ");
3095 print_gimple_stmt (dump_file, stmt, 0);
3097 return false;
3100 if (ref_conflicts_with_region (gsi, &ref, ref_is_store, region_bbs,
3101 i, skip_stmt))
3103 if (dump_file)
3105 fprintf (dump_file, "conflicts with entry/exit stmt: ");
3106 print_gimple_stmt (dump_file, stmt, 0);
3108 return false;
3113 return true;
3116 /* Find stores inside REGION_BBS and outside IN_LOOP_BBS, and guard them with
3117 gang_pos == 0, except when the stores are REDUCTION_STORES. Return true
3118 if any changes were made. */
3120 static bool
3121 oacc_entry_exit_single_gang (bitmap in_loop_bbs, vec<basic_block> region_bbs,
3122 bitmap reduction_stores)
3124 tree gang_pos = NULL_TREE;
3125 bool changed = false;
3127 unsigned i;
3128 basic_block bb;
3129 FOR_EACH_VEC_ELT (region_bbs, i, bb)
3131 if (bitmap_bit_p (in_loop_bbs, bb->index))
3132 continue;
3134 gimple_stmt_iterator gsi;
3135 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
3137 gimple *stmt = gsi_stmt (gsi);
3139 if (!gimple_store_p (stmt))
3141 /* Update gsi to point to next stmt. */
3142 gsi_next (&gsi);
3143 continue;
3146 if (bitmap_bit_p (reduction_stores,
3147 SSA_NAME_VERSION (gimple_vdef (stmt))))
3149 if (dump_file)
3151 fprintf (dump_file,
3152 "skipped reduction store for single-gang"
3153 " neutering: ");
3154 print_gimple_stmt (dump_file, stmt, 0);
3157 /* Update gsi to point to next stmt. */
3158 gsi_next (&gsi);
3159 continue;
3162 changed = true;
3164 if (gang_pos == NULL_TREE)
3166 tree arg = build_int_cst (integer_type_node, GOMP_DIM_GANG);
3167 gcall *gang_single
3168 = gimple_build_call_internal (IFN_GOACC_DIM_POS, 1, arg);
3169 gang_pos = make_ssa_name (integer_type_node);
3170 gimple_call_set_lhs (gang_single, gang_pos);
3171 gimple_stmt_iterator start
3172 = gsi_start_bb (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
3173 tree vuse = ssa_default_def (cfun, gimple_vop (cfun));
3174 gimple_set_vuse (gang_single, vuse);
3175 gsi_insert_before (&start, gang_single, GSI_SAME_STMT);
3178 if (dump_file)
3180 fprintf (dump_file,
3181 "found store that needs single-gang neutering: ");
3182 print_gimple_stmt (dump_file, stmt, 0);
3186 /* Split block before store. */
3187 gimple_stmt_iterator gsi2 = gsi;
3188 gsi_prev (&gsi2);
3189 edge e;
3190 if (gsi_end_p (gsi2))
3192 e = split_block_after_labels (bb);
3193 gsi2 = gsi_last_bb (bb);
3195 else
3196 e = split_block (bb, gsi_stmt (gsi2));
3197 basic_block bb2 = e->dest;
3199 /* Split block after store. */
3200 gimple_stmt_iterator gsi3 = gsi_start_bb (bb2);
3201 edge e2 = split_block (bb2, gsi_stmt (gsi3));
3202 basic_block bb3 = e2->dest;
3204 gimple *cond
3205 = gimple_build_cond (EQ_EXPR, gang_pos, integer_zero_node,
3206 NULL_TREE, NULL_TREE);
3207 gsi_insert_after (&gsi2, cond, GSI_NEW_STMT);
3209 edge e3 = make_edge (bb, bb3, EDGE_FALSE_VALUE);
3210 /* FIXME: What is the probability? */
3211 e3->probability = profile_probability::guessed_never ();
3212 e->flags = EDGE_TRUE_VALUE;
3214 tree vdef = gimple_vdef (stmt);
3215 tree vuse = gimple_vuse (stmt);
3217 tree phi_res = copy_ssa_name (vdef);
3218 gphi *new_phi = create_phi_node (phi_res, bb3);
3219 replace_uses_by (vdef, phi_res);
3220 add_phi_arg (new_phi, vuse, e3, UNKNOWN_LOCATION);
3221 add_phi_arg (new_phi, vdef, e2, UNKNOWN_LOCATION);
3223 /* Update gsi to point to next stmt. */
3224 bb = bb3;
3225 gsi = gsi_start_bb (bb);
3230 return changed;
3233 /* Return true if the statements before and after the LOOP can be executed in
3234 parallel with the function containing the loop. Resolve conflicting stores
3235 outside LOOP by guarding them such that only a single gang executes them. */
3237 static bool
3238 oacc_entry_exit_ok (struct loop *loop,
3239 reduction_info_table_type *reduction_list)
3241 basic_block *loop_bbs = get_loop_body_in_dom_order (loop);
3242 vec<basic_block> region_bbs
3243 = get_all_dominated_blocks (CDI_DOMINATORS, ENTRY_BLOCK_PTR_FOR_FN (cfun));
3245 bitmap in_loop_bbs = BITMAP_ALLOC (NULL);
3246 bitmap_clear (in_loop_bbs);
3247 for (unsigned int i = 0; i < loop->num_nodes; i++)
3248 bitmap_set_bit (in_loop_bbs, loop_bbs[i]->index);
3250 bitmap reduction_stores = BITMAP_ALLOC (NULL);
3251 bool res = oacc_entry_exit_ok_1 (in_loop_bbs, region_bbs, reduction_list,
3252 reduction_stores);
3254 if (res)
3256 bool changed = oacc_entry_exit_single_gang (in_loop_bbs, region_bbs,
3257 reduction_stores);
3258 if (changed)
3260 free_dominance_info (CDI_DOMINATORS);
3261 calculate_dominance_info (CDI_DOMINATORS);
3265 region_bbs.release ();
3266 free (loop_bbs);
3268 BITMAP_FREE (in_loop_bbs);
3269 BITMAP_FREE (reduction_stores);
3271 return res;
3274 /* Detect parallel loops and generate parallel code using libgomp
3275 primitives. Returns true if some loop was parallelized, false
3276 otherwise. */
3278 static bool
3279 parallelize_loops (bool oacc_kernels_p)
3281 unsigned n_threads;
3282 bool changed = false;
3283 struct loop *loop;
3284 struct loop *skip_loop = NULL;
3285 struct tree_niter_desc niter_desc;
3286 struct obstack parloop_obstack;
3287 HOST_WIDE_INT estimated;
3289 /* Do not parallelize loops in the functions created by parallelization. */
3290 if (!oacc_kernels_p
3291 && parallelized_function_p (cfun->decl))
3292 return false;
3294 /* Do not parallelize loops in offloaded functions. */
3295 if (!oacc_kernels_p
3296 && oacc_get_fn_attrib (cfun->decl) != NULL)
3297 return false;
3299 if (cfun->has_nonlocal_label)
3300 return false;
3302 /* For OpenACC kernels, n_threads will be determined later; otherwise, it's
3303 the argument to -ftree-parallelize-loops. */
3304 if (oacc_kernels_p)
3305 n_threads = 0;
3306 else
3307 n_threads = flag_tree_parallelize_loops;
3309 gcc_obstack_init (&parloop_obstack);
3310 reduction_info_table_type reduction_list (10);
3312 calculate_dominance_info (CDI_DOMINATORS);
3314 FOR_EACH_LOOP (loop, 0)
3316 if (loop == skip_loop)
3318 if (!loop->in_oacc_kernels_region
3319 && dump_file && (dump_flags & TDF_DETAILS))
3320 fprintf (dump_file,
3321 "Skipping loop %d as inner loop of parallelized loop\n",
3322 loop->num);
3324 skip_loop = loop->inner;
3325 continue;
3327 else
3328 skip_loop = NULL;
3330 reduction_list.empty ();
3332 if (oacc_kernels_p)
3334 if (!loop->in_oacc_kernels_region)
3335 continue;
3337 /* Don't try to parallelize inner loops in an oacc kernels region. */
3338 if (loop->inner)
3339 skip_loop = loop->inner;
3341 if (dump_file && (dump_flags & TDF_DETAILS))
3342 fprintf (dump_file,
3343 "Trying loop %d with header bb %d in oacc kernels"
3344 " region\n", loop->num, loop->header->index);
3347 if (dump_file && (dump_flags & TDF_DETAILS))
3349 fprintf (dump_file, "Trying loop %d as candidate\n",loop->num);
3350 if (loop->inner)
3351 fprintf (dump_file, "loop %d is not innermost\n",loop->num);
3352 else
3353 fprintf (dump_file, "loop %d is innermost\n",loop->num);
3356 if (!single_dom_exit (loop))
3359 if (dump_file && (dump_flags & TDF_DETAILS))
3360 fprintf (dump_file, "loop is !single_dom_exit\n");
3362 continue;
3365 if (/* And of course, the loop must be parallelizable. */
3366 !can_duplicate_loop_p (loop)
3367 || loop_has_blocks_with_irreducible_flag (loop)
3368 || (loop_preheader_edge (loop)->src->flags & BB_IRREDUCIBLE_LOOP)
3369 /* FIXME: the check for vector phi nodes could be removed. */
3370 || loop_has_vector_phi_nodes (loop))
3371 continue;
3373 estimated = estimated_loop_iterations_int (loop);
3374 if (estimated == -1)
3375 estimated = get_likely_max_loop_iterations_int (loop);
3376 /* FIXME: Bypass this check as graphite doesn't update the
3377 count and frequency correctly now. */
3378 if (!flag_loop_parallelize_all
3379 && !oacc_kernels_p
3380 && ((estimated != -1
3381 && (estimated
3382 < ((HOST_WIDE_INT) n_threads
3383 * (loop->inner ? 2 : MIN_PER_THREAD) - 1)))
3384 /* Do not bother with loops in cold areas. */
3385 || optimize_loop_nest_for_size_p (loop)))
3386 continue;
3388 if (!try_get_loop_niter (loop, &niter_desc))
3389 continue;
3391 if (!try_create_reduction_list (loop, &reduction_list, oacc_kernels_p))
3392 continue;
3394 if (loop_has_phi_with_address_arg (loop))
3395 continue;
3397 if (!loop->can_be_parallel
3398 && !loop_parallel_p (loop, &parloop_obstack))
3399 continue;
3401 if (oacc_kernels_p
3402 && !oacc_entry_exit_ok (loop, &reduction_list))
3404 if (dump_file)
3405 fprintf (dump_file, "entry/exit not ok: FAILED\n");
3406 continue;
3409 changed = true;
3410 skip_loop = loop->inner;
3412 if (dump_enabled_p ())
3414 dump_user_location_t loop_loc = find_loop_location (loop);
3415 if (loop->inner)
3416 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loop_loc,
3417 "parallelizing outer loop %d\n", loop->num);
3418 else
3419 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, loop_loc,
3420 "parallelizing inner loop %d\n", loop->num);
3423 gen_parallel_loop (loop, &reduction_list,
3424 n_threads, &niter_desc, oacc_kernels_p);
3427 obstack_free (&parloop_obstack, NULL);
3429 /* Parallelization will cause new function calls to be inserted through
3430 which local variables will escape. Reset the points-to solution
3431 for ESCAPED. */
3432 if (changed)
3433 pt_solution_reset (&cfun->gimple_df->escaped);
3435 return changed;
3438 /* Parallelization. */
3440 namespace {
3442 const pass_data pass_data_parallelize_loops =
3444 GIMPLE_PASS, /* type */
3445 "parloops", /* name */
3446 OPTGROUP_LOOP, /* optinfo_flags */
3447 TV_TREE_PARALLELIZE_LOOPS, /* tv_id */
3448 ( PROP_cfg | PROP_ssa ), /* properties_required */
3449 0, /* properties_provided */
3450 0, /* properties_destroyed */
3451 0, /* todo_flags_start */
3452 0, /* todo_flags_finish */
3455 class pass_parallelize_loops : public gimple_opt_pass
3457 public:
3458 pass_parallelize_loops (gcc::context *ctxt)
3459 : gimple_opt_pass (pass_data_parallelize_loops, ctxt),
3460 oacc_kernels_p (false)
3463 /* opt_pass methods: */
3464 virtual bool gate (function *)
3466 if (oacc_kernels_p)
3467 return flag_openacc;
3468 else
3469 return flag_tree_parallelize_loops > 1;
3471 virtual unsigned int execute (function *);
3472 opt_pass * clone () { return new pass_parallelize_loops (m_ctxt); }
3473 void set_pass_param (unsigned int n, bool param)
3475 gcc_assert (n == 0);
3476 oacc_kernels_p = param;
3479 private:
3480 bool oacc_kernels_p;
3481 }; // class pass_parallelize_loops
3483 unsigned
3484 pass_parallelize_loops::execute (function *fun)
3486 tree nthreads = builtin_decl_explicit (BUILT_IN_OMP_GET_NUM_THREADS);
3487 if (nthreads == NULL_TREE)
3488 return 0;
3490 bool in_loop_pipeline = scev_initialized_p ();
3491 if (!in_loop_pipeline)
3492 loop_optimizer_init (LOOPS_NORMAL
3493 | LOOPS_HAVE_RECORDED_EXITS);
3495 if (number_of_loops (fun) <= 1)
3496 return 0;
3498 if (!in_loop_pipeline)
3500 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
3501 scev_initialize ();
3504 unsigned int todo = 0;
3505 if (parallelize_loops (oacc_kernels_p))
3507 fun->curr_properties &= ~(PROP_gimple_eomp);
3509 checking_verify_loop_structure ();
3511 todo |= TODO_update_ssa;
3514 if (!in_loop_pipeline)
3516 scev_finalize ();
3517 loop_optimizer_finalize ();
3520 return todo;
3523 } // anon namespace
3525 gimple_opt_pass *
3526 make_pass_parallelize_loops (gcc::context *ctxt)
3528 return new pass_parallelize_loops (ctxt);