1 /* Loop autoparallelization.
2 Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr> and
4 Zdenek Dvorak <dvorakz@suse.cz>.
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
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
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/>. */
24 #include "coretypes.h"
28 #include "tree-flow.h"
31 #include "tree-data-ref.h"
32 #include "diagnostic.h"
33 #include "tree-pass.h"
34 #include "tree-scalar-evolution.h"
36 #include "langhooks.h"
37 #include "tree-vectorizer.h"
39 /* This pass tries to distribute iterations of loops into several threads.
40 The implementation is straightforward -- for each loop we test whether its
41 iterations are independent, and if it is the case (and some additional
42 conditions regarding profitability and correctness are satisfied), we
43 add GIMPLE_OMP_PARALLEL and GIMPLE_OMP_FOR codes and let omp expansion
46 The most of the complexity is in bringing the code into shape expected
48 -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction
49 variable and that the exit test is at the start of the loop body
50 -- for GIMPLE_OMP_PARALLEL, replacing the references to local addressable
51 variables by accesses through pointers, and breaking up ssa chains
52 by storing the values incoming to the parallelized loop to a structure
53 passed to the new function as an argument (something similar is done
54 in omp gimplification, unfortunately only a small part of the code
58 -- if there are several parallelizable loops in a function, it may be
59 possible to generate the threads just once (using synchronization to
60 ensure that cross-loop dependences are obeyed).
61 -- handling of common scalar dependence patterns (accumulation, ...)
62 -- handling of non-innermost loops */
66 currently we use vect_is_simple_reduction() to detect reduction patterns.
67 The code transformation will be introduced by an example.
74 for (i = 0; i < N; i++)
84 # sum_29 = PHI <sum_11(5), 1(3)>
85 # i_28 = PHI <i_12(5), 0(3)>
88 sum_11 = D.1795_8 + sum_29;
96 # sum_21 = PHI <sum_11(4)>
97 printf (&"%d"[0], sum_21);
100 after reduction transformation (only relevant parts):
108 # Storing the initial value given by the user. #
110 .paral_data_store.32.sum.27 = 1;
112 #pragma omp parallel num_threads(4)
114 #pragma omp for schedule(static)
116 # The neutral element corresponding to the particular
117 reduction's operation, e.g. 0 for PLUS_EXPR,
118 1 for MULT_EXPR, etc. replaces the user's initial value. #
120 # sum.27_29 = PHI <sum.27_11, 0>
122 sum.27_11 = D.1827_8 + sum.27_29;
126 # Adding this reduction phi is done at create_phi_for_local_result() #
127 # sum.27_56 = PHI <sum.27_11, 0>
130 # Creating the atomic operation is done at
131 create_call_for_reduction_1() #
133 #pragma omp atomic_load
134 D.1839_59 = *&.paral_data_load.33_51->reduction.23;
135 D.1840_60 = sum.27_56 + D.1839_59;
136 #pragma omp atomic_store (D.1840_60);
140 # collecting the result after the join of the threads is done at
141 create_loads_for_reductions().
142 The value computed by the threads is loaded from the
146 .paral_data_load.33_52 = &.paral_data_store.32;
147 sum_37 = .paral_data_load.33_52->sum.27;
148 sum_43 = D.1795_41 + sum_37;
151 # sum_21 = PHI <sum_43, sum_26>
152 printf (&"%d"[0], sum_21);
160 /* Minimal number of iterations of a loop that should be executed in each
162 #define MIN_PER_THREAD 100
164 /* Element of the hashtable, representing a
165 reduction in the current loop. */
166 struct reduction_info
168 gimple reduc_stmt; /* reduction statement. */
169 gimple reduc_phi; /* The phi node defining the reduction. */
170 enum tree_code reduction_code;/* code for the reduction operation. */
171 gimple keep_res; /* The PHI_RESULT of this phi is the resulting value
172 of the reduction variable when existing the loop. */
173 tree initial_value; /* The initial value of the reduction var before entering the loop. */
174 tree field; /* the name of the field in the parloop data structure intended for reduction. */
175 tree init; /* reduction initialization value. */
176 gimple new_phi; /* (helper field) Newly created phi node whose result
177 will be passed to the atomic operation. Represents
178 the local result each thread computed for the reduction
182 /* Equality and hash functions for hashtab code. */
185 reduction_info_eq (const void *aa, const void *bb)
187 const struct reduction_info *a = (const struct reduction_info *) aa;
188 const struct reduction_info *b = (const struct reduction_info *) bb;
190 return (a->reduc_phi == b->reduc_phi);
194 reduction_info_hash (const void *aa)
196 const struct reduction_info *a = (const struct reduction_info *) aa;
198 return htab_hash_pointer (a->reduc_phi);
201 static struct reduction_info *
202 reduction_phi (htab_t reduction_list, gimple phi)
204 struct reduction_info tmpred, *red;
206 if (htab_elements (reduction_list) == 0)
209 tmpred.reduc_phi = phi;
210 red = (struct reduction_info *) htab_find (reduction_list, &tmpred);
215 /* Element of hashtable of names to copy. */
217 struct name_to_copy_elt
219 unsigned version; /* The version of the name to copy. */
220 tree new_name; /* The new name used in the copy. */
221 tree field; /* The field of the structure used to pass the
225 /* Equality and hash functions for hashtab code. */
228 name_to_copy_elt_eq (const void *aa, const void *bb)
230 const struct name_to_copy_elt *a = (const struct name_to_copy_elt *) aa;
231 const struct name_to_copy_elt *b = (const struct name_to_copy_elt *) bb;
233 return a->version == b->version;
237 name_to_copy_elt_hash (const void *aa)
239 const struct name_to_copy_elt *a = (const struct name_to_copy_elt *) aa;
241 return (hashval_t) a->version;
245 /* Data dependency analysis. Returns true if the iterations of LOOP
246 are independent on each other (that is, if we can execute them
250 loop_parallel_p (struct loop *loop)
252 VEC (ddr_p, heap) * dependence_relations;
253 VEC (data_reference_p, heap) *datarefs;
254 lambda_trans_matrix trans;
257 if (dump_file && (dump_flags & TDF_DETAILS))
258 fprintf (dump_file, "\nConsidering loop %d\n", loop->num);
260 /* Check for problems with dependences. If the loop can be reversed,
261 the iterations are independent. */
262 datarefs = VEC_alloc (data_reference_p, heap, 10);
263 dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
264 compute_data_dependences_for_loop (loop, true, &datarefs,
265 &dependence_relations);
266 if (dump_file && (dump_flags & TDF_DETAILS))
267 dump_data_dependence_relations (dump_file, dependence_relations);
269 trans = lambda_trans_matrix_new (1, 1);
270 LTM_MATRIX (trans)[0][0] = -1;
272 if (lambda_transform_legal_p (trans, 1, dependence_relations))
275 if (dump_file && (dump_flags & TDF_DETAILS))
276 fprintf (dump_file, " SUCCESS: may be parallelized\n");
278 else if (dump_file && (dump_flags & TDF_DETAILS))
280 " FAILED: data dependencies exist across iterations\n");
282 free_dependence_relations (dependence_relations);
283 free_data_refs (datarefs);
288 /* Return true when LOOP contains basic blocks marked with the
289 BB_IRREDUCIBLE_LOOP flag. */
292 loop_has_blocks_with_irreducible_flag (struct loop *loop)
295 basic_block *bbs = get_loop_body_in_dom_order (loop);
298 for (i = 0; i < loop->num_nodes; i++)
299 if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
308 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
309 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
310 to their addresses that can be reused. The address of OBJ is known to
311 be invariant in the whole function. */
314 take_address_of (tree obj, tree type, edge entry, htab_t decl_address)
318 struct int_tree_map ielt, *nielt;
319 tree *var_p, name, bvar, addr;
323 /* Since the address of OBJ is invariant, the trees may be shared.
324 Avoid rewriting unrelated parts of the code. */
325 obj = unshare_expr (obj);
327 handled_component_p (*var_p);
328 var_p = &TREE_OPERAND (*var_p, 0))
330 uid = DECL_UID (*var_p);
333 dslot = htab_find_slot_with_hash (decl_address, &ielt, uid, INSERT);
336 addr = build_addr (*var_p, current_function_decl);
337 bvar = create_tmp_var (TREE_TYPE (addr), get_name (*var_p));
338 add_referenced_var (bvar);
339 stmt = gimple_build_assign (bvar, addr);
340 name = make_ssa_name (bvar, stmt);
341 gimple_assign_set_lhs (stmt, name);
342 gsi_insert_on_edge_immediate (entry, stmt);
344 nielt = XNEW (struct int_tree_map);
350 name = ((struct int_tree_map *) *dslot)->to;
354 *var_p = build1 (INDIRECT_REF, TREE_TYPE (*var_p), name);
355 name = force_gimple_operand (build_addr (obj, current_function_decl),
356 &stmts, true, NULL_TREE);
357 if (!gimple_seq_empty_p (stmts))
358 gsi_insert_seq_on_edge_immediate (entry, stmts);
361 if (TREE_TYPE (name) != type)
363 name = force_gimple_operand (fold_convert (type, name), &stmts, true,
365 if (!gimple_seq_empty_p (stmts))
366 gsi_insert_seq_on_edge_immediate (entry, stmts);
372 /* Callback for htab_traverse. Create the initialization statement
373 for reduction described in SLOT, and place it at the preheader of
374 the loop described in DATA. */
377 initialize_reductions (void **slot, void *data)
380 tree bvar, type, arg;
383 struct reduction_info *const reduc = (struct reduction_info *) *slot;
384 struct loop *loop = (struct loop *) data;
386 /* Create initialization in preheader:
387 reduction_variable = initialization value of reduction. */
389 /* In the phi node at the header, replace the argument coming
390 from the preheader with the reduction initialization value. */
392 /* Create a new variable to initialize the reduction. */
393 type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
394 bvar = create_tmp_var (type, "reduction");
395 add_referenced_var (bvar);
397 c = build_omp_clause (gimple_location (reduc->reduc_stmt),
398 OMP_CLAUSE_REDUCTION);
399 OMP_CLAUSE_REDUCTION_CODE (c) = reduc->reduction_code;
400 OMP_CLAUSE_DECL (c) = SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt));
402 init = omp_reduction_init (c, TREE_TYPE (bvar));
405 /* Replace the argument representing the initialization value
406 with the initialization value for the reduction (neutral
407 element for the particular operation, e.g. 0 for PLUS_EXPR,
408 1 for MULT_EXPR, etc).
409 Keep the old value in a new variable "reduction_initial",
410 that will be taken in consideration after the parallel
411 computing is done. */
413 e = loop_preheader_edge (loop);
414 arg = PHI_ARG_DEF_FROM_EDGE (reduc->reduc_phi, e);
415 /* Create new variable to hold the initial value. */
417 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
418 (reduc->reduc_phi, loop_preheader_edge (loop)), init);
419 reduc->initial_value = arg;
425 struct walk_stmt_info info;
431 /* Eliminates references to local variables in *TP out of the single
432 entry single exit region starting at DTA->ENTRY.
433 DECL_ADDRESS contains addresses of the references that had their
434 address taken already. If the expression is changed, CHANGED is
435 set to true. Callback for walk_tree. */
438 eliminate_local_variables_1 (tree *tp, int *walk_subtrees, void *data)
440 struct elv_data *const dta = (struct elv_data *) data;
441 tree t = *tp, var, addr, addr_type, type, obj;
447 if (!SSA_VAR_P (t) || DECL_EXTERNAL (t))
450 type = TREE_TYPE (t);
451 addr_type = build_pointer_type (type);
452 addr = take_address_of (t, addr_type, dta->entry, dta->decl_address);
453 *tp = build1 (INDIRECT_REF, TREE_TYPE (*tp), addr);
459 if (TREE_CODE (t) == ADDR_EXPR)
461 /* ADDR_EXPR may appear in two contexts:
462 -- as a gimple operand, when the address taken is a function invariant
463 -- as gimple rhs, when the resulting address in not a function
465 We do not need to do anything special in the latter case (the base of
466 the memory reference whose address is taken may be replaced in the
467 DECL_P case). The former case is more complicated, as we need to
468 ensure that the new address is still a gimple operand. Thus, it
469 is not sufficient to replace just the base of the memory reference --
470 we need to move the whole computation of the address out of the
472 if (!is_gimple_val (t))
476 obj = TREE_OPERAND (t, 0);
477 var = get_base_address (obj);
478 if (!var || !SSA_VAR_P (var) || DECL_EXTERNAL (var))
481 addr_type = TREE_TYPE (t);
482 addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address);
495 /* Moves the references to local variables in STMT out of the single
496 entry single exit region starting at ENTRY. DECL_ADDRESS contains
497 addresses of the references that had their address taken
501 eliminate_local_variables_stmt (edge entry, gimple stmt,
506 memset (&dta.info, '\0', sizeof (dta.info));
508 dta.decl_address = decl_address;
511 if (gimple_debug_bind_p (stmt))
512 walk_tree (gimple_debug_bind_get_value_ptr (stmt),
513 eliminate_local_variables_1, &dta.info, NULL);
515 walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
521 /* Eliminates the references to local variables from the single entry
522 single exit region between the ENTRY and EXIT edges.
525 1) Taking address of a local variable -- these are moved out of the
526 region (and temporary variable is created to hold the address if
529 2) Dereferencing a local variable -- these are replaced with indirect
533 eliminate_local_variables (edge entry, edge exit)
536 VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
538 gimple_stmt_iterator gsi;
539 htab_t decl_address = htab_create (10, int_tree_map_hash, int_tree_map_eq,
541 basic_block entry_bb = entry->src;
542 basic_block exit_bb = exit->dest;
544 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
546 for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
547 if (bb != entry_bb && bb != exit_bb)
548 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
549 eliminate_local_variables_stmt (entry, gsi_stmt (gsi),
552 htab_delete (decl_address);
553 VEC_free (basic_block, heap, body);
556 /* Returns true if expression EXPR is not defined between ENTRY and
557 EXIT, i.e. if all its operands are defined outside of the region. */
560 expr_invariant_in_region_p (edge entry, edge exit, tree expr)
562 basic_block entry_bb = entry->src;
563 basic_block exit_bb = exit->dest;
566 if (is_gimple_min_invariant (expr))
569 if (TREE_CODE (expr) == SSA_NAME)
571 def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
573 && dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)
574 && !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))
583 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
584 The copies are stored to NAME_COPIES, if NAME was already duplicated,
585 its duplicate stored in NAME_COPIES is returned.
587 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
588 duplicated, storing the copies in DECL_COPIES. */
591 separate_decls_in_region_name (tree name,
592 htab_t name_copies, htab_t decl_copies,
595 tree copy, var, var_copy;
596 unsigned idx, uid, nuid;
597 struct int_tree_map ielt, *nielt;
598 struct name_to_copy_elt elt, *nelt;
599 void **slot, **dslot;
601 if (TREE_CODE (name) != SSA_NAME)
604 idx = SSA_NAME_VERSION (name);
606 slot = htab_find_slot_with_hash (name_copies, &elt, idx,
607 copy_name_p ? INSERT : NO_INSERT);
609 return ((struct name_to_copy_elt *) *slot)->new_name;
611 var = SSA_NAME_VAR (name);
612 uid = DECL_UID (var);
614 dslot = htab_find_slot_with_hash (decl_copies, &ielt, uid, INSERT);
617 var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
618 DECL_GIMPLE_REG_P (var_copy) = DECL_GIMPLE_REG_P (var);
619 add_referenced_var (var_copy);
620 nielt = XNEW (struct int_tree_map);
622 nielt->to = var_copy;
625 /* Ensure that when we meet this decl next time, we won't duplicate
627 nuid = DECL_UID (var_copy);
629 dslot = htab_find_slot_with_hash (decl_copies, &ielt, nuid, INSERT);
630 gcc_assert (!*dslot);
631 nielt = XNEW (struct int_tree_map);
633 nielt->to = var_copy;
637 var_copy = ((struct int_tree_map *) *dslot)->to;
641 copy = duplicate_ssa_name (name, NULL);
642 nelt = XNEW (struct name_to_copy_elt);
644 nelt->new_name = copy;
645 nelt->field = NULL_TREE;
654 SSA_NAME_VAR (copy) = var_copy;
658 /* Finds the ssa names used in STMT that are defined outside the
659 region between ENTRY and EXIT and replaces such ssa names with
660 their duplicates. The duplicates are stored to NAME_COPIES. Base
661 decls of all ssa names used in STMT (including those defined in
662 LOOP) are replaced with the new temporary variables; the
663 replacement decls are stored in DECL_COPIES. */
666 separate_decls_in_region_stmt (edge entry, edge exit, gimple stmt,
667 htab_t name_copies, htab_t decl_copies)
675 mark_virtual_ops_for_renaming (stmt);
677 FOR_EACH_PHI_OR_STMT_DEF (def, stmt, oi, SSA_OP_DEF)
679 name = DEF_FROM_PTR (def);
680 gcc_assert (TREE_CODE (name) == SSA_NAME);
681 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
683 gcc_assert (copy == name);
686 FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
688 name = USE_FROM_PTR (use);
689 if (TREE_CODE (name) != SSA_NAME)
692 copy_name_p = expr_invariant_in_region_p (entry, exit, name);
693 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
699 /* Finds the ssa names used in STMT that are defined outside the
700 region between ENTRY and EXIT and replaces such ssa names with
701 their duplicates. The duplicates are stored to NAME_COPIES. Base
702 decls of all ssa names used in STMT (including those defined in
703 LOOP) are replaced with the new temporary variables; the
704 replacement decls are stored in DECL_COPIES. */
707 separate_decls_in_region_debug_bind (gimple stmt,
708 htab_t name_copies, htab_t decl_copies)
713 struct int_tree_map ielt;
714 struct name_to_copy_elt elt;
715 void **slot, **dslot;
717 var = gimple_debug_bind_get_var (stmt);
718 if (TREE_CODE (var) == DEBUG_EXPR_DECL)
720 gcc_assert (DECL_P (var) && SSA_VAR_P (var));
721 ielt.uid = DECL_UID (var);
722 dslot = htab_find_slot_with_hash (decl_copies, &ielt, ielt.uid, NO_INSERT);
725 gimple_debug_bind_set_var (stmt, ((struct int_tree_map *) *dslot)->to);
727 FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
729 name = USE_FROM_PTR (use);
730 if (TREE_CODE (name) != SSA_NAME)
733 elt.version = SSA_NAME_VERSION (name);
734 slot = htab_find_slot_with_hash (name_copies, &elt, elt.version, NO_INSERT);
737 gimple_debug_bind_reset_value (stmt);
742 SET_USE (use, ((struct name_to_copy_elt *) *slot)->new_name);
748 /* Callback for htab_traverse. Adds a field corresponding to the reduction
749 specified in SLOT. The type is passed in DATA. */
752 add_field_for_reduction (void **slot, void *data)
755 struct reduction_info *const red = (struct reduction_info *) *slot;
756 tree const type = (tree) data;
757 tree var = SSA_NAME_VAR (gimple_assign_lhs (red->reduc_stmt));
758 tree field = build_decl (gimple_location (red->reduc_stmt),
759 FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
761 insert_field_into_struct (type, field);
768 /* Callback for htab_traverse. Adds a field corresponding to a ssa name
769 described in SLOT. The type is passed in DATA. */
772 add_field_for_name (void **slot, void *data)
774 struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
775 tree type = (tree) data;
776 tree name = ssa_name (elt->version);
777 tree var = SSA_NAME_VAR (name);
778 tree field = build_decl (DECL_SOURCE_LOCATION (var),
779 FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
781 insert_field_into_struct (type, field);
787 /* Callback for htab_traverse. A local result is the intermediate result
789 thread, or the initial value in case no iteration was executed.
790 This function creates a phi node reflecting these values.
791 The phi's result will be stored in NEW_PHI field of the
792 reduction's data structure. */
795 create_phi_for_local_result (void **slot, void *data)
797 struct reduction_info *const reduc = (struct reduction_info *) *slot;
798 const struct loop *const loop = (const struct loop *) data;
801 basic_block store_bb;
803 source_location locus;
805 /* STORE_BB is the block where the phi
806 should be stored. It is the destination of the loop exit.
807 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
808 store_bb = FALLTHRU_EDGE (loop->latch)->dest;
810 /* STORE_BB has two predecessors. One coming from the loop
811 (the reduction's result is computed at the loop),
812 and another coming from a block preceding the loop,
814 are executed (the initial value should be taken). */
815 if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (loop->latch))
816 e = EDGE_PRED (store_bb, 1);
818 e = EDGE_PRED (store_bb, 0);
820 = make_ssa_name (SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt)),
822 locus = gimple_location (reduc->reduc_stmt);
823 new_phi = create_phi_node (local_res, store_bb);
824 SSA_NAME_DEF_STMT (local_res) = new_phi;
825 add_phi_arg (new_phi, reduc->init, e, locus);
826 add_phi_arg (new_phi, gimple_assign_lhs (reduc->reduc_stmt),
827 FALLTHRU_EDGE (loop->latch), locus);
828 reduc->new_phi = new_phi;
838 basic_block store_bb;
842 /* Callback for htab_traverse. Create an atomic instruction for the
843 reduction described in SLOT.
844 DATA annotates the place in memory the atomic operation relates to,
845 and the basic block it needs to be generated in. */
848 create_call_for_reduction_1 (void **slot, void *data)
850 struct reduction_info *const reduc = (struct reduction_info *) *slot;
851 struct clsn_data *const clsn_data = (struct clsn_data *) data;
852 gimple_stmt_iterator gsi;
853 tree type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
854 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
859 tree t, addr, addr_type, ref, x;
863 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
864 t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
865 addr_type = build_pointer_type (type);
867 addr = build_addr (t, current_function_decl);
869 /* Create phi node. */
870 bb = clsn_data->load_bb;
872 e = split_block (bb, t);
875 tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)), NULL);
876 add_referenced_var (tmp_load);
877 tmp_load = make_ssa_name (tmp_load, NULL);
878 load = gimple_build_omp_atomic_load (tmp_load, addr);
879 SSA_NAME_DEF_STMT (tmp_load) = load;
880 gsi = gsi_start_bb (new_bb);
881 gsi_insert_after (&gsi, load, GSI_NEW_STMT);
883 e = split_block (new_bb, load);
885 gsi = gsi_start_bb (new_bb);
887 x = fold_build2 (reduc->reduction_code,
888 TREE_TYPE (PHI_RESULT (reduc->new_phi)), ref,
889 PHI_RESULT (reduc->new_phi));
891 name = force_gimple_operand_gsi (&gsi, x, true, NULL_TREE, true,
892 GSI_CONTINUE_LINKING);
894 gsi_insert_after (&gsi, gimple_build_omp_atomic_store (name), GSI_NEW_STMT);
898 /* Create the atomic operation at the join point of the threads.
899 REDUCTION_LIST describes the reductions in the LOOP.
900 LD_ST_DATA describes the shared data structure where
901 shared data is stored in and loaded from. */
903 create_call_for_reduction (struct loop *loop, htab_t reduction_list,
904 struct clsn_data *ld_st_data)
906 htab_traverse (reduction_list, create_phi_for_local_result, loop);
907 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
908 ld_st_data->load_bb = FALLTHRU_EDGE (loop->latch)->dest;
909 htab_traverse (reduction_list, create_call_for_reduction_1, ld_st_data);
912 /* Callback for htab_traverse. Loads the final reduction value at the
913 join point of all threads, and inserts it in the right place. */
916 create_loads_for_reductions (void **slot, void *data)
918 struct reduction_info *const red = (struct reduction_info *) *slot;
919 struct clsn_data *const clsn_data = (struct clsn_data *) data;
921 gimple_stmt_iterator gsi;
922 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
923 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
928 gsi = gsi_after_labels (clsn_data->load_bb);
929 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
930 load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
934 name = PHI_RESULT (red->keep_res);
935 stmt = gimple_build_assign (name, x);
936 SSA_NAME_DEF_STMT (name) = stmt;
938 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
940 for (gsi = gsi_start_phis (gimple_bb (red->keep_res));
941 !gsi_end_p (gsi); gsi_next (&gsi))
942 if (gsi_stmt (gsi) == red->keep_res)
944 remove_phi_node (&gsi, false);
950 /* Load the reduction result that was stored in LD_ST_DATA.
951 REDUCTION_LIST describes the list of reductions that the
952 loads should be generated for. */
954 create_final_loads_for_reduction (htab_t reduction_list,
955 struct clsn_data *ld_st_data)
957 gimple_stmt_iterator gsi;
961 gsi = gsi_after_labels (ld_st_data->load_bb);
962 t = build_fold_addr_expr (ld_st_data->store);
963 stmt = gimple_build_assign (ld_st_data->load, t);
965 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
966 SSA_NAME_DEF_STMT (ld_st_data->load) = stmt;
968 htab_traverse (reduction_list, create_loads_for_reductions, ld_st_data);
972 /* Callback for htab_traverse. Store the neutral value for the
973 particular reduction's operation, e.g. 0 for PLUS_EXPR,
974 1 for MULT_EXPR, etc. into the reduction field.
975 The reduction is specified in SLOT. The store information is
979 create_stores_for_reduction (void **slot, void *data)
981 struct reduction_info *const red = (struct reduction_info *) *slot;
982 struct clsn_data *const clsn_data = (struct clsn_data *) data;
985 gimple_stmt_iterator gsi;
986 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
988 gsi = gsi_last_bb (clsn_data->store_bb);
989 t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE);
990 stmt = gimple_build_assign (t, red->initial_value);
991 mark_virtual_ops_for_renaming (stmt);
992 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
997 /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
998 store to a field of STORE in STORE_BB for the ssa name and its duplicate
999 specified in SLOT. */
1002 create_loads_and_stores_for_name (void **slot, void *data)
1004 struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
1005 struct clsn_data *const clsn_data = (struct clsn_data *) data;
1008 gimple_stmt_iterator gsi;
1009 tree type = TREE_TYPE (elt->new_name);
1010 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
1013 gsi = gsi_last_bb (clsn_data->store_bb);
1014 t = build3 (COMPONENT_REF, type, clsn_data->store, elt->field, NULL_TREE);
1015 stmt = gimple_build_assign (t, ssa_name (elt->version));
1016 mark_virtual_ops_for_renaming (stmt);
1017 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1019 gsi = gsi_last_bb (clsn_data->load_bb);
1020 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
1021 t = build3 (COMPONENT_REF, type, load_struct, elt->field, NULL_TREE);
1022 stmt = gimple_build_assign (elt->new_name, t);
1023 SSA_NAME_DEF_STMT (elt->new_name) = stmt;
1024 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1029 /* Moves all the variables used in LOOP and defined outside of it (including
1030 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1031 name) to a structure created for this purpose. The code
1039 is transformed this way:
1054 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1055 pointer `new' is intentionally not initialized (the loop will be split to a
1056 separate function later, and `new' will be initialized from its arguments).
1057 LD_ST_DATA holds information about the shared data structure used to pass
1058 information among the threads. It is initialized here, and
1059 gen_parallel_loop will pass it to create_call_for_reduction that
1060 needs this information. REDUCTION_LIST describes the reductions
1064 separate_decls_in_region (edge entry, edge exit, htab_t reduction_list,
1065 tree *arg_struct, tree *new_arg_struct,
1066 struct clsn_data *ld_st_data)
1069 basic_block bb1 = split_edge (entry);
1070 basic_block bb0 = single_pred (bb1);
1071 htab_t name_copies = htab_create (10, name_to_copy_elt_hash,
1072 name_to_copy_elt_eq, free);
1073 htab_t decl_copies = htab_create (10, int_tree_map_hash, int_tree_map_eq,
1076 tree type, type_name, nvar;
1077 gimple_stmt_iterator gsi;
1078 struct clsn_data clsn_data;
1079 VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
1081 basic_block entry_bb = bb1;
1082 basic_block exit_bb = exit->dest;
1083 bool has_debug_stmt = false;
1085 entry = single_succ_edge (entry_bb);
1086 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
1088 for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
1090 if (bb != entry_bb && bb != exit_bb)
1092 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1093 separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
1094 name_copies, decl_copies);
1096 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1098 gimple stmt = gsi_stmt (gsi);
1100 if (is_gimple_debug (stmt))
1101 has_debug_stmt = true;
1103 separate_decls_in_region_stmt (entry, exit, stmt,
1104 name_copies, decl_copies);
1109 /* Now process debug bind stmts. We must not create decls while
1110 processing debug stmts, so we defer their processing so as to
1111 make sure we will have debug info for as many variables as
1112 possible (all of those that were dealt with in the loop above),
1113 and discard those for which we know there's nothing we can
1116 for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
1117 if (bb != entry_bb && bb != exit_bb)
1119 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
1121 gimple stmt = gsi_stmt (gsi);
1123 if (gimple_debug_bind_p (stmt))
1125 if (separate_decls_in_region_debug_bind (stmt,
1129 gsi_remove (&gsi, true);
1138 VEC_free (basic_block, heap, body);
1140 if (htab_elements (name_copies) == 0 && htab_elements (reduction_list) == 0)
1142 /* It may happen that there is nothing to copy (if there are only
1143 loop carried and external variables in the loop). */
1145 *new_arg_struct = NULL;
1149 /* Create the type for the structure to store the ssa names to. */
1150 type = lang_hooks.types.make_type (RECORD_TYPE);
1151 type_name = build_decl (BUILTINS_LOCATION,
1152 TYPE_DECL, create_tmp_var_name (".paral_data"),
1154 TYPE_NAME (type) = type_name;
1156 htab_traverse (name_copies, add_field_for_name, type);
1157 if (reduction_list && htab_elements (reduction_list) > 0)
1159 /* Create the fields for reductions. */
1160 htab_traverse (reduction_list, add_field_for_reduction,
1165 /* Create the loads and stores. */
1166 *arg_struct = create_tmp_var (type, ".paral_data_store");
1167 add_referenced_var (*arg_struct);
1168 nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load");
1169 add_referenced_var (nvar);
1170 *new_arg_struct = make_ssa_name (nvar, NULL);
1172 ld_st_data->store = *arg_struct;
1173 ld_st_data->load = *new_arg_struct;
1174 ld_st_data->store_bb = bb0;
1175 ld_st_data->load_bb = bb1;
1177 htab_traverse (name_copies, create_loads_and_stores_for_name,
1180 /* Load the calculation from memory (after the join of the threads). */
1182 if (reduction_list && htab_elements (reduction_list) > 0)
1184 htab_traverse (reduction_list, create_stores_for_reduction,
1186 clsn_data.load = make_ssa_name (nvar, NULL);
1187 clsn_data.load_bb = exit->dest;
1188 clsn_data.store = ld_st_data->store;
1189 create_final_loads_for_reduction (reduction_list, &clsn_data);
1193 htab_delete (decl_copies);
1194 htab_delete (name_copies);
1197 /* Bitmap containing uids of functions created by parallelization. We cannot
1198 allocate it from the default obstack, as it must live across compilation
1199 of several functions; we make it gc allocated instead. */
1201 static GTY(()) bitmap parallelized_functions;
1203 /* Returns true if FN was created by create_loop_fn. */
1206 parallelized_function_p (tree fn)
1208 if (!parallelized_functions || !DECL_ARTIFICIAL (fn))
1211 return bitmap_bit_p (parallelized_functions, DECL_UID (fn));
1214 /* Creates and returns an empty function that will receive the body of
1215 a parallelized loop. */
1218 create_loop_fn (void)
1222 tree decl, type, name, t;
1223 struct function *act_cfun = cfun;
1224 static unsigned loopfn_num;
1226 snprintf (buf, 100, "%s.$loopfn", current_function_name ());
1227 ASM_FORMAT_PRIVATE_NAME (tname, buf, loopfn_num++);
1228 clean_symbol_name (tname);
1229 name = get_identifier (tname);
1230 type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
1232 decl = build_decl (BUILTINS_LOCATION,
1233 FUNCTION_DECL, name, type);
1234 if (!parallelized_functions)
1235 parallelized_functions = BITMAP_GGC_ALLOC ();
1236 bitmap_set_bit (parallelized_functions, DECL_UID (decl));
1238 TREE_STATIC (decl) = 1;
1239 TREE_USED (decl) = 1;
1240 DECL_ARTIFICIAL (decl) = 1;
1241 DECL_IGNORED_P (decl) = 0;
1242 TREE_PUBLIC (decl) = 0;
1243 DECL_UNINLINABLE (decl) = 1;
1244 DECL_EXTERNAL (decl) = 0;
1245 DECL_CONTEXT (decl) = NULL_TREE;
1246 DECL_INITIAL (decl) = make_node (BLOCK);
1248 t = build_decl (BUILTINS_LOCATION,
1249 RESULT_DECL, NULL_TREE, void_type_node);
1250 DECL_ARTIFICIAL (t) = 1;
1251 DECL_IGNORED_P (t) = 1;
1252 DECL_RESULT (decl) = t;
1254 t = build_decl (BUILTINS_LOCATION,
1255 PARM_DECL, get_identifier (".paral_data_param"),
1257 DECL_ARTIFICIAL (t) = 1;
1258 DECL_ARG_TYPE (t) = ptr_type_node;
1259 DECL_CONTEXT (t) = decl;
1261 DECL_ARGUMENTS (decl) = t;
1263 allocate_struct_function (decl, false);
1265 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1267 set_cfun (act_cfun);
1272 /* Moves the exit condition of LOOP to the beginning of its header, and
1273 duplicates the part of the last iteration that gets disabled to the
1274 exit of the loop. NIT is the number of iterations of the loop
1275 (used to initialize the variables in the duplicated part).
1277 TODO: the common case is that latch of the loop is empty and immediately
1278 follows the loop exit. In this case, it would be better not to copy the
1279 body of the loop, but only move the entry of the loop directly before the
1280 exit check and increase the number of iterations of the loop by one.
1281 This may need some additional preconditioning in case NIT = ~0.
1282 REDUCTION_LIST describes the reductions in LOOP. */
1285 transform_to_exit_first_loop (struct loop *loop, htab_t reduction_list, tree nit)
1287 basic_block *bbs, *nbbs, ex_bb, orig_header;
1290 edge exit = single_dom_exit (loop), hpred;
1291 tree control, control_name, res, t;
1292 gimple phi, nphi, cond_stmt, stmt;
1293 gimple_stmt_iterator gsi;
1295 split_block_after_labels (loop->header);
1296 orig_header = single_succ (loop->header);
1297 hpred = single_succ_edge (loop->header);
1299 cond_stmt = last_stmt (exit->src);
1300 control = gimple_cond_lhs (cond_stmt);
1301 gcc_assert (gimple_cond_rhs (cond_stmt) == nit);
1303 /* Make sure that we have phi nodes on exit for all loop header phis
1304 (create_parallel_loop requires that). */
1305 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1307 phi = gsi_stmt (gsi);
1308 res = PHI_RESULT (phi);
1309 t = make_ssa_name (SSA_NAME_VAR (res), phi);
1310 SET_PHI_RESULT (phi, t);
1312 nphi = create_phi_node (res, orig_header);
1313 SSA_NAME_DEF_STMT (res) = nphi;
1314 add_phi_arg (nphi, t, hpred, UNKNOWN_LOCATION);
1318 gimple_cond_set_lhs (cond_stmt, t);
1319 update_stmt (cond_stmt);
1324 bbs = get_loop_body_in_dom_order (loop);
1325 for (n = 0; bbs[n] != exit->src; n++)
1327 nbbs = XNEWVEC (basic_block, n);
1328 ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
1335 /* Other than reductions, the only gimple reg that should be copied
1336 out of the loop is the control variable. */
1338 control_name = NULL_TREE;
1339 for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); )
1341 phi = gsi_stmt (gsi);
1342 res = PHI_RESULT (phi);
1343 if (!is_gimple_reg (res))
1349 /* Check if it is a part of reduction. If it is,
1350 keep the phi at the reduction's keep_res field. The
1351 PHI_RESULT of this phi is the resulting value of the reduction
1352 variable when exiting the loop. */
1354 exit = single_dom_exit (loop);
1356 if (htab_elements (reduction_list) > 0)
1358 struct reduction_info *red;
1360 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1362 red = reduction_phi (reduction_list, SSA_NAME_DEF_STMT (val));
1365 red->keep_res = phi;
1370 gcc_assert (control_name == NULL_TREE
1371 && SSA_NAME_VAR (res) == SSA_NAME_VAR (control));
1373 remove_phi_node (&gsi, false);
1375 gcc_assert (control_name != NULL_TREE);
1377 /* Initialize the control variable to NIT. */
1378 gsi = gsi_after_labels (ex_bb);
1379 nit = force_gimple_operand_gsi (&gsi,
1380 fold_convert (TREE_TYPE (control_name), nit),
1381 false, NULL_TREE, false, GSI_SAME_STMT);
1382 stmt = gimple_build_assign (control_name, nit);
1383 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1384 SSA_NAME_DEF_STMT (control_name) = stmt;
1387 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
1388 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
1389 NEW_DATA is the variable that should be initialized from the argument
1390 of LOOP_FN. N_THREADS is the requested number of threads. Returns the
1391 basic block containing GIMPLE_OMP_PARALLEL tree. */
1394 create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
1395 tree new_data, unsigned n_threads)
1397 gimple_stmt_iterator gsi;
1398 basic_block bb, paral_bb, for_bb, ex_bb;
1400 gimple stmt, for_stmt, phi, cond_stmt;
1401 tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
1402 edge exit, nexit, guard, end, e;
1404 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
1405 bb = loop_preheader_edge (loop)->src;
1406 paral_bb = single_pred (bb);
1407 gsi = gsi_last_bb (paral_bb);
1409 t = build_omp_clause (BUILTINS_LOCATION, OMP_CLAUSE_NUM_THREADS);
1410 OMP_CLAUSE_NUM_THREADS_EXPR (t)
1411 = build_int_cst (integer_type_node, n_threads);
1412 stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
1414 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1416 /* Initialize NEW_DATA. */
1419 gsi = gsi_after_labels (bb);
1421 param = make_ssa_name (DECL_ARGUMENTS (loop_fn), NULL);
1422 stmt = gimple_build_assign (param, build_fold_addr_expr (data));
1423 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1424 SSA_NAME_DEF_STMT (param) = stmt;
1426 stmt = gimple_build_assign (new_data,
1427 fold_convert (TREE_TYPE (new_data), param));
1428 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1429 SSA_NAME_DEF_STMT (new_data) = stmt;
1432 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
1433 bb = split_loop_exit_edge (single_dom_exit (loop));
1434 gsi = gsi_last_bb (bb);
1435 gsi_insert_after (&gsi, gimple_build_omp_return (false), GSI_NEW_STMT);
1437 /* Extract data for GIMPLE_OMP_FOR. */
1438 gcc_assert (loop->header == single_dom_exit (loop)->src);
1439 cond_stmt = last_stmt (loop->header);
1441 cvar = gimple_cond_lhs (cond_stmt);
1442 cvar_base = SSA_NAME_VAR (cvar);
1443 phi = SSA_NAME_DEF_STMT (cvar);
1444 cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1445 initvar = make_ssa_name (cvar_base, NULL);
1446 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
1448 cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1450 gsi = gsi_last_bb (loop->latch);
1451 gcc_assert (gsi_stmt (gsi) == SSA_NAME_DEF_STMT (cvar_next));
1452 gsi_remove (&gsi, true);
1455 for_bb = split_edge (loop_preheader_edge (loop));
1456 ex_bb = split_loop_exit_edge (single_dom_exit (loop));
1457 extract_true_false_edges_from_block (loop->header, &nexit, &exit);
1458 gcc_assert (exit == single_dom_exit (loop));
1460 guard = make_edge (for_bb, ex_bb, 0);
1461 single_succ_edge (loop->latch)->flags = 0;
1462 end = make_edge (loop->latch, ex_bb, EDGE_FALLTHRU);
1463 for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); gsi_next (&gsi))
1465 source_location locus;
1467 phi = gsi_stmt (gsi);
1468 res = PHI_RESULT (phi);
1469 stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi, exit));
1471 def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop));
1472 locus = gimple_phi_arg_location_from_edge (stmt,
1473 loop_preheader_edge (loop));
1474 add_phi_arg (phi, def, guard, locus);
1476 def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_latch_edge (loop));
1477 locus = gimple_phi_arg_location_from_edge (stmt, loop_latch_edge (loop));
1478 add_phi_arg (phi, def, end, locus);
1480 e = redirect_edge_and_branch (exit, nexit->dest);
1481 PENDING_STMT (e) = NULL;
1483 /* Emit GIMPLE_OMP_FOR. */
1484 gimple_cond_set_lhs (cond_stmt, cvar_base);
1485 type = TREE_TYPE (cvar);
1486 t = build_omp_clause (BUILTINS_LOCATION, OMP_CLAUSE_SCHEDULE);
1487 OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
1489 for_stmt = gimple_build_omp_for (NULL, t, 1, NULL);
1490 gimple_omp_for_set_index (for_stmt, 0, initvar);
1491 gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
1492 gimple_omp_for_set_final (for_stmt, 0, gimple_cond_rhs (cond_stmt));
1493 gimple_omp_for_set_cond (for_stmt, 0, gimple_cond_code (cond_stmt));
1494 gimple_omp_for_set_incr (for_stmt, 0, build2 (PLUS_EXPR, type,
1496 build_int_cst (type, 1)));
1498 gsi = gsi_last_bb (for_bb);
1499 gsi_insert_after (&gsi, for_stmt, GSI_NEW_STMT);
1500 SSA_NAME_DEF_STMT (initvar) = for_stmt;
1502 /* Emit GIMPLE_OMP_CONTINUE. */
1503 gsi = gsi_last_bb (loop->latch);
1504 stmt = gimple_build_omp_continue (cvar_next, cvar);
1505 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1506 SSA_NAME_DEF_STMT (cvar_next) = stmt;
1508 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
1509 gsi = gsi_last_bb (ex_bb);
1510 gsi_insert_after (&gsi, gimple_build_omp_return (true), GSI_NEW_STMT);
1515 /* Generates code to execute the iterations of LOOP in N_THREADS
1516 threads in parallel.
1518 NITER describes number of iterations of LOOP.
1519 REDUCTION_LIST describes the reductions existent in the LOOP. */
1522 gen_parallel_loop (struct loop *loop, htab_t reduction_list,
1523 unsigned n_threads, struct tree_niter_desc *niter)
1527 tree many_iterations_cond, type, nit;
1528 tree arg_struct, new_arg_struct;
1530 basic_block parallel_head;
1532 struct clsn_data clsn_data;
1537 ---------------------------------------------------------------------
1540 IV = phi (INIT, IV + STEP)
1546 ---------------------------------------------------------------------
1548 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
1549 we generate the following code:
1551 ---------------------------------------------------------------------
1554 || NITER < MIN_PER_THREAD * N_THREADS)
1558 store all local loop-invariant variables used in body of the loop to DATA.
1559 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
1560 load the variables from DATA.
1561 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
1564 GIMPLE_OMP_CONTINUE;
1565 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
1566 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
1572 IV = phi (INIT, IV + STEP)
1583 /* Create two versions of the loop -- in the old one, we know that the
1584 number of iterations is large enough, and we will transform it into the
1585 loop that will be split to loop_fn, the new one will be used for the
1586 remaining iterations. */
1588 type = TREE_TYPE (niter->niter);
1589 nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true,
1592 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1594 many_iterations_cond =
1595 fold_build2 (GE_EXPR, boolean_type_node,
1596 nit, build_int_cst (type, MIN_PER_THREAD * n_threads));
1597 many_iterations_cond
1598 = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1599 invert_truthvalue (unshare_expr (niter->may_be_zero)),
1600 many_iterations_cond);
1601 many_iterations_cond
1602 = force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
1604 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1605 if (!is_gimple_condexpr (many_iterations_cond))
1607 many_iterations_cond
1608 = force_gimple_operand (many_iterations_cond, &stmts,
1611 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1614 initialize_original_copy_tables ();
1616 /* We assume that the loop usually iterates a lot. */
1617 prob = 4 * REG_BR_PROB_BASE / 5;
1618 nloop = loop_version (loop, many_iterations_cond, NULL,
1619 prob, prob, REG_BR_PROB_BASE - prob, true);
1620 update_ssa (TODO_update_ssa);
1621 free_original_copy_tables ();
1623 /* Base all the induction variables in LOOP on a single control one. */
1624 canonicalize_loop_ivs (loop, &nit);
1626 /* Ensure that the exit condition is the first statement in the loop. */
1627 transform_to_exit_first_loop (loop, reduction_list, nit);
1629 /* Generate initializations for reductions. */
1630 if (htab_elements (reduction_list) > 0)
1631 htab_traverse (reduction_list, initialize_reductions, loop);
1633 /* Eliminate the references to local variables from the loop. */
1634 gcc_assert (single_exit (loop));
1635 entry = loop_preheader_edge (loop);
1636 exit = single_dom_exit (loop);
1638 eliminate_local_variables (entry, exit);
1639 /* In the old loop, move all variables non-local to the loop to a structure
1640 and back, and create separate decls for the variables used in loop. */
1641 separate_decls_in_region (entry, exit, reduction_list, &arg_struct,
1642 &new_arg_struct, &clsn_data);
1644 /* Create the parallel constructs. */
1645 parallel_head = create_parallel_loop (loop, create_loop_fn (), arg_struct,
1646 new_arg_struct, n_threads);
1647 if (htab_elements (reduction_list) > 0)
1648 create_call_for_reduction (loop, reduction_list, &clsn_data);
1652 /* Cancel the loop (it is simpler to do it here rather than to teach the
1653 expander to do it). */
1654 cancel_loop_tree (loop);
1656 /* Free loop bound estimations that could contain references to
1657 removed statements. */
1658 FOR_EACH_LOOP (li, loop, 0)
1659 free_numbers_of_iterations_estimates_loop (loop);
1661 /* Expand the parallel constructs. We do it directly here instead of running
1662 a separate expand_omp pass, since it is more efficient, and less likely to
1663 cause troubles with further analyses not being able to deal with the
1666 omp_expand_local (parallel_head);
1669 /* Returns true when LOOP contains vector phi nodes. */
1672 loop_has_vector_phi_nodes (struct loop *loop ATTRIBUTE_UNUSED)
1675 basic_block *bbs = get_loop_body_in_dom_order (loop);
1676 gimple_stmt_iterator gsi;
1679 for (i = 0; i < loop->num_nodes; i++)
1680 for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
1681 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi_stmt (gsi)))) == VECTOR_TYPE)
1690 /* Create a reduction_info struct, initialize it with REDUC_STMT
1691 and PHI, insert it to the REDUCTION_LIST. */
1694 build_new_reduction (htab_t reduction_list, gimple reduc_stmt, gimple phi)
1697 struct reduction_info *new_reduction;
1699 gcc_assert (reduc_stmt);
1701 if (dump_file && (dump_flags & TDF_DETAILS))
1704 "Detected reduction. reduction stmt is: \n");
1705 print_gimple_stmt (dump_file, reduc_stmt, 0, 0);
1706 fprintf (dump_file, "\n");
1709 new_reduction = XCNEW (struct reduction_info);
1711 new_reduction->reduc_stmt = reduc_stmt;
1712 new_reduction->reduc_phi = phi;
1713 new_reduction->reduction_code = gimple_assign_rhs_code (reduc_stmt);
1714 slot = htab_find_slot (reduction_list, new_reduction, INSERT);
1715 *slot = new_reduction;
1718 /* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
1721 gather_scalar_reductions (loop_p loop, htab_t reduction_list)
1723 gimple_stmt_iterator gsi;
1724 loop_vec_info simple_loop_info;
1727 simple_loop_info = vect_analyze_loop_form (loop);
1729 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1731 gimple phi = gsi_stmt (gsi);
1733 tree res = PHI_RESULT (phi);
1736 if (!is_gimple_reg (res))
1739 if (!simple_iv (loop, loop, res, &iv, true)
1740 && simple_loop_info)
1742 gimple reduc_stmt = vect_is_simple_reduction (simple_loop_info, phi, true, &double_reduc);
1744 build_new_reduction (reduction_list, reduc_stmt, phi);
1747 destroy_loop_vec_info (simple_loop_info, true);
1750 /* Try to initialize NITER for code generation part. */
1753 try_get_loop_niter (loop_p loop, struct tree_niter_desc *niter)
1755 edge exit = single_dom_exit (loop);
1759 /* We need to know # of iterations, and there should be no uses of values
1760 defined inside loop outside of it, unless the values are invariants of
1762 if (!number_of_iterations_exit (loop, exit, niter, false))
1764 if (dump_file && (dump_flags & TDF_DETAILS))
1765 fprintf (dump_file, " FAILED: number of iterations not known\n");
1772 /* Try to initialize REDUCTION_LIST for code generation part.
1773 REDUCTION_LIST describes the reductions. */
1776 try_create_reduction_list (loop_p loop, htab_t reduction_list)
1778 edge exit = single_dom_exit (loop);
1779 gimple_stmt_iterator gsi;
1783 gather_scalar_reductions (loop, reduction_list);
1786 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
1788 gimple phi = gsi_stmt (gsi);
1789 struct reduction_info *red;
1790 imm_use_iterator imm_iter;
1791 use_operand_p use_p;
1793 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1795 if (is_gimple_reg (val))
1797 if (dump_file && (dump_flags & TDF_DETAILS))
1799 fprintf (dump_file, "phi is ");
1800 print_gimple_stmt (dump_file, phi, 0, 0);
1801 fprintf (dump_file, "arg of phi to exit: value ");
1802 print_generic_expr (dump_file, val, 0);
1803 fprintf (dump_file, " used outside loop\n");
1805 " checking if it a part of reduction pattern: \n");
1807 if (htab_elements (reduction_list) == 0)
1809 if (dump_file && (dump_flags & TDF_DETAILS))
1811 " FAILED: it is not a part of reduction.\n");
1815 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
1817 if (flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
1819 reduc_phi = USE_STMT (use_p);
1823 red = reduction_phi (reduction_list, reduc_phi);
1826 if (dump_file && (dump_flags & TDF_DETAILS))
1828 " FAILED: it is not a part of reduction.\n");
1831 if (dump_file && (dump_flags & TDF_DETAILS))
1833 fprintf (dump_file, "reduction phi is ");
1834 print_gimple_stmt (dump_file, red->reduc_phi, 0, 0);
1835 fprintf (dump_file, "reduction stmt is ");
1836 print_gimple_stmt (dump_file, red->reduc_stmt, 0, 0);
1841 /* The iterations of the loop may communicate only through bivs whose
1842 iteration space can be distributed efficiently. */
1843 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1845 gimple phi = gsi_stmt (gsi);
1846 tree def = PHI_RESULT (phi);
1849 if (is_gimple_reg (def) && !simple_iv (loop, loop, def, &iv, true))
1851 struct reduction_info *red;
1853 red = reduction_phi (reduction_list, phi);
1856 if (dump_file && (dump_flags & TDF_DETAILS))
1858 " FAILED: scalar dependency between iterations\n");
1868 /* Detect parallel loops and generate parallel code using libgomp
1869 primitives. Returns true if some loop was parallelized, false
1873 parallelize_loops (void)
1875 unsigned n_threads = flag_tree_parallelize_loops;
1876 bool changed = false;
1878 struct tree_niter_desc niter_desc;
1880 htab_t reduction_list;
1882 /* Do not parallelize loops in the functions created by parallelization. */
1883 if (parallelized_function_p (cfun->decl))
1886 reduction_list = htab_create (10, reduction_info_hash,
1887 reduction_info_eq, free);
1888 init_stmt_vec_info_vec ();
1890 FOR_EACH_LOOP (li, loop, 0)
1892 htab_empty (reduction_list);
1894 /* If we use autopar in graphite pass, we use it's marked dependency
1895 checking results. */
1896 if (flag_loop_parallelize_all && !loop->can_be_parallel)
1899 /* FIXME: Only consider innermost loops with just one exit. */
1900 if (loop->inner || !single_dom_exit (loop))
1903 if (/* And of course, the loop must be parallelizable. */
1904 !can_duplicate_loop_p (loop)
1905 || loop_has_blocks_with_irreducible_flag (loop)
1906 /* FIXME: the check for vector phi nodes could be removed. */
1907 || loop_has_vector_phi_nodes (loop))
1910 /* FIXME: Bypass this check as graphite doesn't update the
1911 count and frequency correctly now. */
1912 if (!flag_loop_parallelize_all
1913 && ((estimated_loop_iterations_int (loop, false)
1914 <= (HOST_WIDE_INT) n_threads * MIN_PER_THREAD)
1915 /* Do not bother with loops in cold areas. */
1916 || optimize_loop_nest_for_size_p (loop)))
1919 if (!try_get_loop_niter (loop, &niter_desc))
1922 if (!try_create_reduction_list (loop, reduction_list))
1925 if (!flag_loop_parallelize_all && !loop_parallel_p (loop))
1929 gen_parallel_loop (loop, reduction_list,
1930 n_threads, &niter_desc);
1931 verify_flow_info ();
1932 verify_dominators (CDI_DOMINATORS);
1933 verify_loop_structure ();
1934 verify_loop_closed_ssa ();
1937 free_stmt_vec_info_vec ();
1938 htab_delete (reduction_list);
1940 /* Parallelization will cause new function calls to be inserted through
1941 which local variables will escape. Reset the points-to solutions
1942 for ESCAPED and CALLUSED. */
1945 pt_solution_reset (&cfun->gimple_df->escaped);
1946 pt_solution_reset (&cfun->gimple_df->callused);
1952 #include "gt-tree-parloops.h"