1 /* Loop autoparallelization.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <pop@cri.ensmp.fr> and
5 Zdenek Dvorak <dvorakz@suse.cz>.
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
28 #include "tree-flow.h"
30 #include "tree-data-ref.h"
31 #include "diagnostic.h"
32 #include "tree-pass.h"
33 #include "tree-scalar-evolution.h"
35 #include "langhooks.h"
36 #include "tree-vectorizer.h"
38 /* This pass tries to distribute iterations of loops into several threads.
39 The implementation is straightforward -- for each loop we test whether its
40 iterations are independent, and if it is the case (and some additional
41 conditions regarding profitability and correctness are satisfied), we
42 add GIMPLE_OMP_PARALLEL and GIMPLE_OMP_FOR codes and let omp expansion
45 The most of the complexity is in bringing the code into shape expected
47 -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction
48 variable and that the exit test is at the start of the loop body
49 -- for GIMPLE_OMP_PARALLEL, replacing the references to local addressable
50 variables by accesses through pointers, and breaking up ssa chains
51 by storing the values incoming to the parallelized loop to a structure
52 passed to the new function as an argument (something similar is done
53 in omp gimplification, unfortunately only a small part of the code
57 -- if there are several parallelizable loops in a function, it may be
58 possible to generate the threads just once (using synchronization to
59 ensure that cross-loop dependences are obeyed).
60 -- handling of common scalar dependence patterns (accumulation, ...)
61 -- handling of non-innermost loops */
65 currently we use vect_force_simple_reduction() to detect reduction patterns.
66 The code transformation will be introduced by an example.
73 for (i = 0; i < N; i++)
83 # sum_29 = PHI <sum_11(5), 1(3)>
84 # i_28 = PHI <i_12(5), 0(3)>
87 sum_11 = D.1795_8 + sum_29;
95 # sum_21 = PHI <sum_11(4)>
96 printf (&"%d"[0], sum_21);
99 after reduction transformation (only relevant parts):
107 # Storing the initial value given by the user. #
109 .paral_data_store.32.sum.27 = 1;
111 #pragma omp parallel num_threads(4)
113 #pragma omp for schedule(static)
115 # The neutral element corresponding to the particular
116 reduction's operation, e.g. 0 for PLUS_EXPR,
117 1 for MULT_EXPR, etc. replaces the user's initial value. #
119 # sum.27_29 = PHI <sum.27_11, 0>
121 sum.27_11 = D.1827_8 + sum.27_29;
125 # Adding this reduction phi is done at create_phi_for_local_result() #
126 # sum.27_56 = PHI <sum.27_11, 0>
129 # Creating the atomic operation is done at
130 create_call_for_reduction_1() #
132 #pragma omp atomic_load
133 D.1839_59 = *&.paral_data_load.33_51->reduction.23;
134 D.1840_60 = sum.27_56 + D.1839_59;
135 #pragma omp atomic_store (D.1840_60);
139 # collecting the result after the join of the threads is done at
140 create_loads_for_reductions().
141 The value computed by the threads is loaded from the
145 .paral_data_load.33_52 = &.paral_data_store.32;
146 sum_37 = .paral_data_load.33_52->sum.27;
147 sum_43 = D.1795_41 + sum_37;
150 # sum_21 = PHI <sum_43, sum_26>
151 printf (&"%d"[0], sum_21);
159 /* Minimal number of iterations of a loop that should be executed in each
161 #define MIN_PER_THREAD 100
163 /* Element of the hashtable, representing a
164 reduction in the current loop. */
165 struct reduction_info
167 gimple reduc_stmt; /* reduction statement. */
168 gimple reduc_phi; /* The phi node defining the reduction. */
169 enum tree_code reduction_code;/* code for the reduction operation. */
170 gimple keep_res; /* The PHI_RESULT of this phi is the resulting value
171 of the reduction variable when existing the loop. */
172 tree initial_value; /* The initial value of the reduction var before entering the loop. */
173 tree field; /* the name of the field in the parloop data structure intended for reduction. */
174 tree init; /* reduction initialization value. */
175 gimple new_phi; /* (helper field) Newly created phi node whose result
176 will be passed to the atomic operation. Represents
177 the local result each thread computed for the reduction
181 /* Equality and hash functions for hashtab code. */
184 reduction_info_eq (const void *aa, const void *bb)
186 const struct reduction_info *a = (const struct reduction_info *) aa;
187 const struct reduction_info *b = (const struct reduction_info *) bb;
189 return (a->reduc_phi == b->reduc_phi);
193 reduction_info_hash (const void *aa)
195 const struct reduction_info *a = (const struct reduction_info *) aa;
197 return htab_hash_pointer (a->reduc_phi);
200 static struct reduction_info *
201 reduction_phi (htab_t reduction_list, gimple phi)
203 struct reduction_info tmpred, *red;
205 if (htab_elements (reduction_list) == 0)
208 tmpred.reduc_phi = phi;
209 red = (struct reduction_info *) htab_find (reduction_list, &tmpred);
214 /* Element of hashtable of names to copy. */
216 struct name_to_copy_elt
218 unsigned version; /* The version of the name to copy. */
219 tree new_name; /* The new name used in the copy. */
220 tree field; /* The field of the structure used to pass the
224 /* Equality and hash functions for hashtab code. */
227 name_to_copy_elt_eq (const void *aa, const void *bb)
229 const struct name_to_copy_elt *a = (const struct name_to_copy_elt *) aa;
230 const struct name_to_copy_elt *b = (const struct name_to_copy_elt *) bb;
232 return a->version == b->version;
236 name_to_copy_elt_hash (const void *aa)
238 const struct name_to_copy_elt *a = (const struct name_to_copy_elt *) aa;
240 return (hashval_t) a->version;
244 /* Data dependency analysis. Returns true if the iterations of LOOP
245 are independent on each other (that is, if we can execute them
249 loop_parallel_p (struct loop *loop, struct obstack * parloop_obstack)
251 VEC (ddr_p, heap) * dependence_relations;
252 VEC (data_reference_p, heap) *datarefs;
253 lambda_trans_matrix trans;
256 if (dump_file && (dump_flags & TDF_DETAILS))
258 fprintf (dump_file, "Considering loop %d\n", loop->num);
260 fprintf (dump_file, "loop is innermost\n");
262 fprintf (dump_file, "loop NOT innermost\n");
265 /* Check for problems with dependences. If the loop can be reversed,
266 the iterations are independent. */
267 datarefs = VEC_alloc (data_reference_p, heap, 10);
268 dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
269 compute_data_dependences_for_loop (loop, true, &datarefs,
270 &dependence_relations);
271 if (dump_file && (dump_flags & TDF_DETAILS))
272 dump_data_dependence_relations (dump_file, dependence_relations);
274 trans = lambda_trans_matrix_new (1, 1, parloop_obstack);
275 LTM_MATRIX (trans)[0][0] = -1;
277 if (lambda_transform_legal_p (trans, 1, dependence_relations))
280 if (dump_file && (dump_flags & TDF_DETAILS))
281 fprintf (dump_file, " SUCCESS: may be parallelized\n");
283 else if (dump_file && (dump_flags & TDF_DETAILS))
285 " FAILED: data dependencies exist across iterations\n");
287 free_dependence_relations (dependence_relations);
288 free_data_refs (datarefs);
293 /* Return true when LOOP contains basic blocks marked with the
294 BB_IRREDUCIBLE_LOOP flag. */
297 loop_has_blocks_with_irreducible_flag (struct loop *loop)
300 basic_block *bbs = get_loop_body_in_dom_order (loop);
303 for (i = 0; i < loop->num_nodes; i++)
304 if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
313 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
314 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
315 to their addresses that can be reused. The address of OBJ is known to
316 be invariant in the whole function. */
319 take_address_of (tree obj, tree type, edge entry, htab_t decl_address)
323 struct int_tree_map ielt, *nielt;
324 tree *var_p, name, bvar, addr;
328 /* Since the address of OBJ is invariant, the trees may be shared.
329 Avoid rewriting unrelated parts of the code. */
330 obj = unshare_expr (obj);
332 handled_component_p (*var_p);
333 var_p = &TREE_OPERAND (*var_p, 0))
335 uid = DECL_UID (*var_p);
338 dslot = htab_find_slot_with_hash (decl_address, &ielt, uid, INSERT);
341 addr = build_addr (*var_p, current_function_decl);
342 bvar = create_tmp_var (TREE_TYPE (addr), get_name (*var_p));
343 add_referenced_var (bvar);
344 stmt = gimple_build_assign (bvar, addr);
345 name = make_ssa_name (bvar, stmt);
346 gimple_assign_set_lhs (stmt, name);
347 gsi_insert_on_edge_immediate (entry, stmt);
349 nielt = XNEW (struct int_tree_map);
355 name = ((struct int_tree_map *) *dslot)->to;
359 *var_p = build1 (INDIRECT_REF, TREE_TYPE (*var_p), name);
360 name = force_gimple_operand (build_addr (obj, current_function_decl),
361 &stmts, true, NULL_TREE);
362 if (!gimple_seq_empty_p (stmts))
363 gsi_insert_seq_on_edge_immediate (entry, stmts);
366 if (TREE_TYPE (name) != type)
368 name = force_gimple_operand (fold_convert (type, name), &stmts, true,
370 if (!gimple_seq_empty_p (stmts))
371 gsi_insert_seq_on_edge_immediate (entry, stmts);
377 /* Callback for htab_traverse. Create the initialization statement
378 for reduction described in SLOT, and place it at the preheader of
379 the loop described in DATA. */
382 initialize_reductions (void **slot, void *data)
385 tree bvar, type, arg;
388 struct reduction_info *const reduc = (struct reduction_info *) *slot;
389 struct loop *loop = (struct loop *) data;
391 /* Create initialization in preheader:
392 reduction_variable = initialization value of reduction. */
394 /* In the phi node at the header, replace the argument coming
395 from the preheader with the reduction initialization value. */
397 /* Create a new variable to initialize the reduction. */
398 type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
399 bvar = create_tmp_var (type, "reduction");
400 add_referenced_var (bvar);
402 c = build_omp_clause (gimple_location (reduc->reduc_stmt),
403 OMP_CLAUSE_REDUCTION);
404 OMP_CLAUSE_REDUCTION_CODE (c) = reduc->reduction_code;
405 OMP_CLAUSE_DECL (c) = SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt));
407 init = omp_reduction_init (c, TREE_TYPE (bvar));
410 /* Replace the argument representing the initialization value
411 with the initialization value for the reduction (neutral
412 element for the particular operation, e.g. 0 for PLUS_EXPR,
413 1 for MULT_EXPR, etc).
414 Keep the old value in a new variable "reduction_initial",
415 that will be taken in consideration after the parallel
416 computing is done. */
418 e = loop_preheader_edge (loop);
419 arg = PHI_ARG_DEF_FROM_EDGE (reduc->reduc_phi, e);
420 /* Create new variable to hold the initial value. */
422 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
423 (reduc->reduc_phi, loop_preheader_edge (loop)), init);
424 reduc->initial_value = arg;
430 struct walk_stmt_info info;
436 /* Eliminates references to local variables in *TP out of the single
437 entry single exit region starting at DTA->ENTRY.
438 DECL_ADDRESS contains addresses of the references that had their
439 address taken already. If the expression is changed, CHANGED is
440 set to true. Callback for walk_tree. */
443 eliminate_local_variables_1 (tree *tp, int *walk_subtrees, void *data)
445 struct elv_data *const dta = (struct elv_data *) data;
446 tree t = *tp, var, addr, addr_type, type, obj;
452 if (!SSA_VAR_P (t) || DECL_EXTERNAL (t))
455 type = TREE_TYPE (t);
456 addr_type = build_pointer_type (type);
457 addr = take_address_of (t, addr_type, dta->entry, dta->decl_address);
458 *tp = build1 (INDIRECT_REF, TREE_TYPE (*tp), addr);
464 if (TREE_CODE (t) == ADDR_EXPR)
466 /* ADDR_EXPR may appear in two contexts:
467 -- as a gimple operand, when the address taken is a function invariant
468 -- as gimple rhs, when the resulting address in not a function
470 We do not need to do anything special in the latter case (the base of
471 the memory reference whose address is taken may be replaced in the
472 DECL_P case). The former case is more complicated, as we need to
473 ensure that the new address is still a gimple operand. Thus, it
474 is not sufficient to replace just the base of the memory reference --
475 we need to move the whole computation of the address out of the
477 if (!is_gimple_val (t))
481 obj = TREE_OPERAND (t, 0);
482 var = get_base_address (obj);
483 if (!var || !SSA_VAR_P (var) || DECL_EXTERNAL (var))
486 addr_type = TREE_TYPE (t);
487 addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address);
500 /* Moves the references to local variables in STMT out of the single
501 entry single exit region starting at ENTRY. DECL_ADDRESS contains
502 addresses of the references that had their address taken
506 eliminate_local_variables_stmt (edge entry, gimple stmt,
511 memset (&dta.info, '\0', sizeof (dta.info));
513 dta.decl_address = decl_address;
516 if (gimple_debug_bind_p (stmt))
517 walk_tree (gimple_debug_bind_get_value_ptr (stmt),
518 eliminate_local_variables_1, &dta.info, NULL);
520 walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
526 /* Eliminates the references to local variables from the single entry
527 single exit region between the ENTRY and EXIT edges.
530 1) Taking address of a local variable -- these are moved out of the
531 region (and temporary variable is created to hold the address if
534 2) Dereferencing a local variable -- these are replaced with indirect
538 eliminate_local_variables (edge entry, edge exit)
541 VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
543 gimple_stmt_iterator gsi;
544 htab_t decl_address = htab_create (10, int_tree_map_hash, int_tree_map_eq,
546 basic_block entry_bb = entry->src;
547 basic_block exit_bb = exit->dest;
549 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
551 for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
552 if (bb != entry_bb && bb != exit_bb)
553 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
554 eliminate_local_variables_stmt (entry, gsi_stmt (gsi),
557 htab_delete (decl_address);
558 VEC_free (basic_block, heap, body);
561 /* Returns true if expression EXPR is not defined between ENTRY and
562 EXIT, i.e. if all its operands are defined outside of the region. */
565 expr_invariant_in_region_p (edge entry, edge exit, tree expr)
567 basic_block entry_bb = entry->src;
568 basic_block exit_bb = exit->dest;
571 if (is_gimple_min_invariant (expr))
574 if (TREE_CODE (expr) == SSA_NAME)
576 def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
578 && dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)
579 && !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))
588 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
589 The copies are stored to NAME_COPIES, if NAME was already duplicated,
590 its duplicate stored in NAME_COPIES is returned.
592 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
593 duplicated, storing the copies in DECL_COPIES. */
596 separate_decls_in_region_name (tree name,
597 htab_t name_copies, htab_t decl_copies,
600 tree copy, var, var_copy;
601 unsigned idx, uid, nuid;
602 struct int_tree_map ielt, *nielt;
603 struct name_to_copy_elt elt, *nelt;
604 void **slot, **dslot;
606 if (TREE_CODE (name) != SSA_NAME)
609 idx = SSA_NAME_VERSION (name);
611 slot = htab_find_slot_with_hash (name_copies, &elt, idx,
612 copy_name_p ? INSERT : NO_INSERT);
614 return ((struct name_to_copy_elt *) *slot)->new_name;
616 var = SSA_NAME_VAR (name);
617 uid = DECL_UID (var);
619 dslot = htab_find_slot_with_hash (decl_copies, &ielt, uid, INSERT);
622 var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
623 DECL_GIMPLE_REG_P (var_copy) = DECL_GIMPLE_REG_P (var);
624 add_referenced_var (var_copy);
625 nielt = XNEW (struct int_tree_map);
627 nielt->to = var_copy;
630 /* Ensure that when we meet this decl next time, we won't duplicate
632 nuid = DECL_UID (var_copy);
634 dslot = htab_find_slot_with_hash (decl_copies, &ielt, nuid, INSERT);
635 gcc_assert (!*dslot);
636 nielt = XNEW (struct int_tree_map);
638 nielt->to = var_copy;
642 var_copy = ((struct int_tree_map *) *dslot)->to;
646 copy = duplicate_ssa_name (name, NULL);
647 nelt = XNEW (struct name_to_copy_elt);
649 nelt->new_name = copy;
650 nelt->field = NULL_TREE;
659 SSA_NAME_VAR (copy) = var_copy;
663 /* Finds the ssa names used in STMT that are defined outside the
664 region between ENTRY and EXIT and replaces such ssa names with
665 their duplicates. The duplicates are stored to NAME_COPIES. Base
666 decls of all ssa names used in STMT (including those defined in
667 LOOP) are replaced with the new temporary variables; the
668 replacement decls are stored in DECL_COPIES. */
671 separate_decls_in_region_stmt (edge entry, edge exit, gimple stmt,
672 htab_t name_copies, htab_t decl_copies)
680 mark_virtual_ops_for_renaming (stmt);
682 FOR_EACH_PHI_OR_STMT_DEF (def, stmt, oi, SSA_OP_DEF)
684 name = DEF_FROM_PTR (def);
685 gcc_assert (TREE_CODE (name) == SSA_NAME);
686 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
688 gcc_assert (copy == name);
691 FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
693 name = USE_FROM_PTR (use);
694 if (TREE_CODE (name) != SSA_NAME)
697 copy_name_p = expr_invariant_in_region_p (entry, exit, name);
698 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
704 /* Finds the ssa names used in STMT that are defined outside the
705 region between ENTRY and EXIT and replaces such ssa names with
706 their duplicates. The duplicates are stored to NAME_COPIES. Base
707 decls of all ssa names used in STMT (including those defined in
708 LOOP) are replaced with the new temporary variables; the
709 replacement decls are stored in DECL_COPIES. */
712 separate_decls_in_region_debug_bind (gimple stmt,
713 htab_t name_copies, htab_t decl_copies)
718 struct int_tree_map ielt;
719 struct name_to_copy_elt elt;
720 void **slot, **dslot;
722 var = gimple_debug_bind_get_var (stmt);
723 if (TREE_CODE (var) == DEBUG_EXPR_DECL)
725 gcc_assert (DECL_P (var) && SSA_VAR_P (var));
726 ielt.uid = DECL_UID (var);
727 dslot = htab_find_slot_with_hash (decl_copies, &ielt, ielt.uid, NO_INSERT);
730 gimple_debug_bind_set_var (stmt, ((struct int_tree_map *) *dslot)->to);
732 FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
734 name = USE_FROM_PTR (use);
735 if (TREE_CODE (name) != SSA_NAME)
738 elt.version = SSA_NAME_VERSION (name);
739 slot = htab_find_slot_with_hash (name_copies, &elt, elt.version, NO_INSERT);
742 gimple_debug_bind_reset_value (stmt);
747 SET_USE (use, ((struct name_to_copy_elt *) *slot)->new_name);
753 /* Callback for htab_traverse. Adds a field corresponding to the reduction
754 specified in SLOT. The type is passed in DATA. */
757 add_field_for_reduction (void **slot, void *data)
760 struct reduction_info *const red = (struct reduction_info *) *slot;
761 tree const type = (tree) data;
762 tree var = SSA_NAME_VAR (gimple_assign_lhs (red->reduc_stmt));
763 tree field = build_decl (gimple_location (red->reduc_stmt),
764 FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
766 insert_field_into_struct (type, field);
773 /* Callback for htab_traverse. Adds a field corresponding to a ssa name
774 described in SLOT. The type is passed in DATA. */
777 add_field_for_name (void **slot, void *data)
779 struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
780 tree type = (tree) data;
781 tree name = ssa_name (elt->version);
782 tree var = SSA_NAME_VAR (name);
783 tree field = build_decl (DECL_SOURCE_LOCATION (var),
784 FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
786 insert_field_into_struct (type, field);
792 /* Callback for htab_traverse. A local result is the intermediate result
794 thread, or the initial value in case no iteration was executed.
795 This function creates a phi node reflecting these values.
796 The phi's result will be stored in NEW_PHI field of the
797 reduction's data structure. */
800 create_phi_for_local_result (void **slot, void *data)
802 struct reduction_info *const reduc = (struct reduction_info *) *slot;
803 const struct loop *const loop = (const struct loop *) data;
806 basic_block store_bb;
808 source_location locus;
810 /* STORE_BB is the block where the phi
811 should be stored. It is the destination of the loop exit.
812 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
813 store_bb = FALLTHRU_EDGE (loop->latch)->dest;
815 /* STORE_BB has two predecessors. One coming from the loop
816 (the reduction's result is computed at the loop),
817 and another coming from a block preceding the loop,
819 are executed (the initial value should be taken). */
820 if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (loop->latch))
821 e = EDGE_PRED (store_bb, 1);
823 e = EDGE_PRED (store_bb, 0);
825 = make_ssa_name (SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt)),
827 locus = gimple_location (reduc->reduc_stmt);
828 new_phi = create_phi_node (local_res, store_bb);
829 SSA_NAME_DEF_STMT (local_res) = new_phi;
830 add_phi_arg (new_phi, reduc->init, e, locus);
831 add_phi_arg (new_phi, gimple_assign_lhs (reduc->reduc_stmt),
832 FALLTHRU_EDGE (loop->latch), locus);
833 reduc->new_phi = new_phi;
843 basic_block store_bb;
847 /* Callback for htab_traverse. Create an atomic instruction for the
848 reduction described in SLOT.
849 DATA annotates the place in memory the atomic operation relates to,
850 and the basic block it needs to be generated in. */
853 create_call_for_reduction_1 (void **slot, void *data)
855 struct reduction_info *const reduc = (struct reduction_info *) *slot;
856 struct clsn_data *const clsn_data = (struct clsn_data *) data;
857 gimple_stmt_iterator gsi;
858 tree type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
859 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
864 tree t, addr, ref, x;
868 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
869 t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
871 addr = build_addr (t, current_function_decl);
873 /* Create phi node. */
874 bb = clsn_data->load_bb;
876 e = split_block (bb, t);
879 tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)), NULL);
880 add_referenced_var (tmp_load);
881 tmp_load = make_ssa_name (tmp_load, NULL);
882 load = gimple_build_omp_atomic_load (tmp_load, addr);
883 SSA_NAME_DEF_STMT (tmp_load) = load;
884 gsi = gsi_start_bb (new_bb);
885 gsi_insert_after (&gsi, load, GSI_NEW_STMT);
887 e = split_block (new_bb, load);
889 gsi = gsi_start_bb (new_bb);
891 x = fold_build2 (reduc->reduction_code,
892 TREE_TYPE (PHI_RESULT (reduc->new_phi)), ref,
893 PHI_RESULT (reduc->new_phi));
895 name = force_gimple_operand_gsi (&gsi, x, true, NULL_TREE, true,
896 GSI_CONTINUE_LINKING);
898 gsi_insert_after (&gsi, gimple_build_omp_atomic_store (name), GSI_NEW_STMT);
902 /* Create the atomic operation at the join point of the threads.
903 REDUCTION_LIST describes the reductions in the LOOP.
904 LD_ST_DATA describes the shared data structure where
905 shared data is stored in and loaded from. */
907 create_call_for_reduction (struct loop *loop, htab_t reduction_list,
908 struct clsn_data *ld_st_data)
910 htab_traverse (reduction_list, create_phi_for_local_result, loop);
911 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
912 ld_st_data->load_bb = FALLTHRU_EDGE (loop->latch)->dest;
913 htab_traverse (reduction_list, create_call_for_reduction_1, ld_st_data);
916 /* Callback for htab_traverse. Loads the final reduction value at the
917 join point of all threads, and inserts it in the right place. */
920 create_loads_for_reductions (void **slot, void *data)
922 struct reduction_info *const red = (struct reduction_info *) *slot;
923 struct clsn_data *const clsn_data = (struct clsn_data *) data;
925 gimple_stmt_iterator gsi;
926 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
927 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
932 gsi = gsi_after_labels (clsn_data->load_bb);
933 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
934 load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
938 name = PHI_RESULT (red->keep_res);
939 stmt = gimple_build_assign (name, x);
940 SSA_NAME_DEF_STMT (name) = stmt;
942 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
944 for (gsi = gsi_start_phis (gimple_bb (red->keep_res));
945 !gsi_end_p (gsi); gsi_next (&gsi))
946 if (gsi_stmt (gsi) == red->keep_res)
948 remove_phi_node (&gsi, false);
954 /* Load the reduction result that was stored in LD_ST_DATA.
955 REDUCTION_LIST describes the list of reductions that the
956 loads should be generated for. */
958 create_final_loads_for_reduction (htab_t reduction_list,
959 struct clsn_data *ld_st_data)
961 gimple_stmt_iterator gsi;
965 gsi = gsi_after_labels (ld_st_data->load_bb);
966 t = build_fold_addr_expr (ld_st_data->store);
967 stmt = gimple_build_assign (ld_st_data->load, t);
969 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
970 SSA_NAME_DEF_STMT (ld_st_data->load) = stmt;
972 htab_traverse (reduction_list, create_loads_for_reductions, ld_st_data);
976 /* Callback for htab_traverse. Store the neutral value for the
977 particular reduction's operation, e.g. 0 for PLUS_EXPR,
978 1 for MULT_EXPR, etc. into the reduction field.
979 The reduction is specified in SLOT. The store information is
983 create_stores_for_reduction (void **slot, void *data)
985 struct reduction_info *const red = (struct reduction_info *) *slot;
986 struct clsn_data *const clsn_data = (struct clsn_data *) data;
989 gimple_stmt_iterator gsi;
990 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
992 gsi = gsi_last_bb (clsn_data->store_bb);
993 t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE);
994 stmt = gimple_build_assign (t, red->initial_value);
995 mark_virtual_ops_for_renaming (stmt);
996 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1001 /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
1002 store to a field of STORE in STORE_BB for the ssa name and its duplicate
1003 specified in SLOT. */
1006 create_loads_and_stores_for_name (void **slot, void *data)
1008 struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
1009 struct clsn_data *const clsn_data = (struct clsn_data *) data;
1012 gimple_stmt_iterator gsi;
1013 tree type = TREE_TYPE (elt->new_name);
1014 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
1017 gsi = gsi_last_bb (clsn_data->store_bb);
1018 t = build3 (COMPONENT_REF, type, clsn_data->store, elt->field, NULL_TREE);
1019 stmt = gimple_build_assign (t, ssa_name (elt->version));
1020 mark_virtual_ops_for_renaming (stmt);
1021 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1023 gsi = gsi_last_bb (clsn_data->load_bb);
1024 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
1025 t = build3 (COMPONENT_REF, type, load_struct, elt->field, NULL_TREE);
1026 stmt = gimple_build_assign (elt->new_name, t);
1027 SSA_NAME_DEF_STMT (elt->new_name) = stmt;
1028 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1033 /* Moves all the variables used in LOOP and defined outside of it (including
1034 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1035 name) to a structure created for this purpose. The code
1043 is transformed this way:
1058 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1059 pointer `new' is intentionally not initialized (the loop will be split to a
1060 separate function later, and `new' will be initialized from its arguments).
1061 LD_ST_DATA holds information about the shared data structure used to pass
1062 information among the threads. It is initialized here, and
1063 gen_parallel_loop will pass it to create_call_for_reduction that
1064 needs this information. REDUCTION_LIST describes the reductions
1068 separate_decls_in_region (edge entry, edge exit, htab_t reduction_list,
1069 tree *arg_struct, tree *new_arg_struct,
1070 struct clsn_data *ld_st_data)
1073 basic_block bb1 = split_edge (entry);
1074 basic_block bb0 = single_pred (bb1);
1075 htab_t name_copies = htab_create (10, name_to_copy_elt_hash,
1076 name_to_copy_elt_eq, free);
1077 htab_t decl_copies = htab_create (10, int_tree_map_hash, int_tree_map_eq,
1080 tree type, type_name, nvar;
1081 gimple_stmt_iterator gsi;
1082 struct clsn_data clsn_data;
1083 VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
1085 basic_block entry_bb = bb1;
1086 basic_block exit_bb = exit->dest;
1087 bool has_debug_stmt = false;
1089 entry = single_succ_edge (entry_bb);
1090 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
1092 for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
1094 if (bb != entry_bb && bb != exit_bb)
1096 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1097 separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
1098 name_copies, decl_copies);
1100 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1102 gimple stmt = gsi_stmt (gsi);
1104 if (is_gimple_debug (stmt))
1105 has_debug_stmt = true;
1107 separate_decls_in_region_stmt (entry, exit, stmt,
1108 name_copies, decl_copies);
1113 /* Now process debug bind stmts. We must not create decls while
1114 processing debug stmts, so we defer their processing so as to
1115 make sure we will have debug info for as many variables as
1116 possible (all of those that were dealt with in the loop above),
1117 and discard those for which we know there's nothing we can
1120 for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
1121 if (bb != entry_bb && bb != exit_bb)
1123 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
1125 gimple stmt = gsi_stmt (gsi);
1127 if (gimple_debug_bind_p (stmt))
1129 if (separate_decls_in_region_debug_bind (stmt,
1133 gsi_remove (&gsi, true);
1142 VEC_free (basic_block, heap, body);
1144 if (htab_elements (name_copies) == 0 && htab_elements (reduction_list) == 0)
1146 /* It may happen that there is nothing to copy (if there are only
1147 loop carried and external variables in the loop). */
1149 *new_arg_struct = NULL;
1153 /* Create the type for the structure to store the ssa names to. */
1154 type = lang_hooks.types.make_type (RECORD_TYPE);
1155 type_name = build_decl (BUILTINS_LOCATION,
1156 TYPE_DECL, create_tmp_var_name (".paral_data"),
1158 TYPE_NAME (type) = type_name;
1160 htab_traverse (name_copies, add_field_for_name, type);
1161 if (reduction_list && htab_elements (reduction_list) > 0)
1163 /* Create the fields for reductions. */
1164 htab_traverse (reduction_list, add_field_for_reduction,
1169 /* Create the loads and stores. */
1170 *arg_struct = create_tmp_var (type, ".paral_data_store");
1171 add_referenced_var (*arg_struct);
1172 nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load");
1173 add_referenced_var (nvar);
1174 *new_arg_struct = make_ssa_name (nvar, NULL);
1176 ld_st_data->store = *arg_struct;
1177 ld_st_data->load = *new_arg_struct;
1178 ld_st_data->store_bb = bb0;
1179 ld_st_data->load_bb = bb1;
1181 htab_traverse (name_copies, create_loads_and_stores_for_name,
1184 /* Load the calculation from memory (after the join of the threads). */
1186 if (reduction_list && htab_elements (reduction_list) > 0)
1188 htab_traverse (reduction_list, create_stores_for_reduction,
1190 clsn_data.load = make_ssa_name (nvar, NULL);
1191 clsn_data.load_bb = exit->dest;
1192 clsn_data.store = ld_st_data->store;
1193 create_final_loads_for_reduction (reduction_list, &clsn_data);
1197 htab_delete (decl_copies);
1198 htab_delete (name_copies);
1201 /* Bitmap containing uids of functions created by parallelization. We cannot
1202 allocate it from the default obstack, as it must live across compilation
1203 of several functions; we make it gc allocated instead. */
1205 static GTY(()) bitmap parallelized_functions;
1207 /* Returns true if FN was created by create_loop_fn. */
1210 parallelized_function_p (tree fn)
1212 if (!parallelized_functions || !DECL_ARTIFICIAL (fn))
1215 return bitmap_bit_p (parallelized_functions, DECL_UID (fn));
1218 /* Creates and returns an empty function that will receive the body of
1219 a parallelized loop. */
1222 create_loop_fn (void)
1226 tree decl, type, name, t;
1227 struct function *act_cfun = cfun;
1228 static unsigned loopfn_num;
1230 snprintf (buf, 100, "%s.$loopfn", current_function_name ());
1231 ASM_FORMAT_PRIVATE_NAME (tname, buf, loopfn_num++);
1232 clean_symbol_name (tname);
1233 name = get_identifier (tname);
1234 type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
1236 decl = build_decl (BUILTINS_LOCATION,
1237 FUNCTION_DECL, name, type);
1238 if (!parallelized_functions)
1239 parallelized_functions = BITMAP_GGC_ALLOC ();
1240 bitmap_set_bit (parallelized_functions, DECL_UID (decl));
1242 TREE_STATIC (decl) = 1;
1243 TREE_USED (decl) = 1;
1244 DECL_ARTIFICIAL (decl) = 1;
1245 DECL_IGNORED_P (decl) = 0;
1246 TREE_PUBLIC (decl) = 0;
1247 DECL_UNINLINABLE (decl) = 1;
1248 DECL_EXTERNAL (decl) = 0;
1249 DECL_CONTEXT (decl) = NULL_TREE;
1250 DECL_INITIAL (decl) = make_node (BLOCK);
1252 t = build_decl (BUILTINS_LOCATION,
1253 RESULT_DECL, NULL_TREE, void_type_node);
1254 DECL_ARTIFICIAL (t) = 1;
1255 DECL_IGNORED_P (t) = 1;
1256 DECL_RESULT (decl) = t;
1258 t = build_decl (BUILTINS_LOCATION,
1259 PARM_DECL, get_identifier (".paral_data_param"),
1261 DECL_ARTIFICIAL (t) = 1;
1262 DECL_ARG_TYPE (t) = ptr_type_node;
1263 DECL_CONTEXT (t) = decl;
1265 DECL_ARGUMENTS (decl) = t;
1267 allocate_struct_function (decl, false);
1269 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1271 set_cfun (act_cfun);
1276 /* Moves the exit condition of LOOP to the beginning of its header, and
1277 duplicates the part of the last iteration that gets disabled to the
1278 exit of the loop. NIT is the number of iterations of the loop
1279 (used to initialize the variables in the duplicated part).
1281 TODO: the common case is that latch of the loop is empty and immediately
1282 follows the loop exit. In this case, it would be better not to copy the
1283 body of the loop, but only move the entry of the loop directly before the
1284 exit check and increase the number of iterations of the loop by one.
1285 This may need some additional preconditioning in case NIT = ~0.
1286 REDUCTION_LIST describes the reductions in LOOP. */
1289 transform_to_exit_first_loop (struct loop *loop, htab_t reduction_list, tree nit)
1291 basic_block *bbs, *nbbs, ex_bb, orig_header;
1294 edge exit = single_dom_exit (loop), hpred;
1295 tree control, control_name, res, t;
1296 gimple phi, nphi, cond_stmt, stmt, cond_nit;
1297 gimple_stmt_iterator gsi;
1300 split_block_after_labels (loop->header);
1301 orig_header = single_succ (loop->header);
1302 hpred = single_succ_edge (loop->header);
1304 cond_stmt = last_stmt (exit->src);
1305 control = gimple_cond_lhs (cond_stmt);
1306 gcc_assert (gimple_cond_rhs (cond_stmt) == nit);
1308 /* Make sure that we have phi nodes on exit for all loop header phis
1309 (create_parallel_loop requires that). */
1310 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1312 phi = gsi_stmt (gsi);
1313 res = PHI_RESULT (phi);
1314 t = make_ssa_name (SSA_NAME_VAR (res), phi);
1315 SET_PHI_RESULT (phi, t);
1316 nphi = create_phi_node (res, orig_header);
1317 SSA_NAME_DEF_STMT (res) = nphi;
1318 add_phi_arg (nphi, t, hpred, UNKNOWN_LOCATION);
1322 gimple_cond_set_lhs (cond_stmt, t);
1323 update_stmt (cond_stmt);
1327 bbs = get_loop_body_in_dom_order (loop);
1329 for (n = 0; bbs[n] != loop->latch; n++)
1331 nbbs = XNEWVEC (basic_block, n);
1332 ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
1339 /* Other than reductions, the only gimple reg that should be copied
1340 out of the loop is the control variable. */
1342 control_name = NULL_TREE;
1343 for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); )
1345 phi = gsi_stmt (gsi);
1346 res = PHI_RESULT (phi);
1347 if (!is_gimple_reg (res))
1353 /* Check if it is a part of reduction. If it is,
1354 keep the phi at the reduction's keep_res field. The
1355 PHI_RESULT of this phi is the resulting value of the reduction
1356 variable when exiting the loop. */
1358 exit = single_dom_exit (loop);
1360 if (htab_elements (reduction_list) > 0)
1362 struct reduction_info *red;
1364 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1365 red = reduction_phi (reduction_list, SSA_NAME_DEF_STMT (val));
1368 red->keep_res = phi;
1373 gcc_assert (control_name == NULL_TREE
1374 && SSA_NAME_VAR (res) == SSA_NAME_VAR (control));
1376 remove_phi_node (&gsi, false);
1378 gcc_assert (control_name != NULL_TREE);
1380 /* Initialize the control variable to number of iterations
1381 according to the rhs of the exit condition. */
1382 gsi = gsi_after_labels (ex_bb);
1383 cond_nit = last_stmt (exit->src);
1384 nit_1 = gimple_cond_rhs (cond_nit);
1385 nit_1 = force_gimple_operand_gsi (&gsi,
1386 fold_convert (TREE_TYPE (control_name), nit_1),
1387 false, NULL_TREE, false, GSI_SAME_STMT);
1388 stmt = gimple_build_assign (control_name, nit_1);
1389 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1390 SSA_NAME_DEF_STMT (control_name) = stmt;
1393 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
1394 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
1395 NEW_DATA is the variable that should be initialized from the argument
1396 of LOOP_FN. N_THREADS is the requested number of threads. Returns the
1397 basic block containing GIMPLE_OMP_PARALLEL tree. */
1400 create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
1401 tree new_data, unsigned n_threads)
1403 gimple_stmt_iterator gsi;
1404 basic_block bb, paral_bb, for_bb, ex_bb;
1406 gimple stmt, for_stmt, phi, cond_stmt;
1407 tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
1408 edge exit, nexit, guard, end, e;
1410 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
1411 bb = loop_preheader_edge (loop)->src;
1412 paral_bb = single_pred (bb);
1413 gsi = gsi_last_bb (paral_bb);
1415 t = build_omp_clause (BUILTINS_LOCATION, OMP_CLAUSE_NUM_THREADS);
1416 OMP_CLAUSE_NUM_THREADS_EXPR (t)
1417 = build_int_cst (integer_type_node, n_threads);
1418 stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
1420 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1422 /* Initialize NEW_DATA. */
1425 gsi = gsi_after_labels (bb);
1427 param = make_ssa_name (DECL_ARGUMENTS (loop_fn), NULL);
1428 stmt = gimple_build_assign (param, build_fold_addr_expr (data));
1429 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1430 SSA_NAME_DEF_STMT (param) = stmt;
1432 stmt = gimple_build_assign (new_data,
1433 fold_convert (TREE_TYPE (new_data), param));
1434 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1435 SSA_NAME_DEF_STMT (new_data) = stmt;
1438 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
1439 bb = split_loop_exit_edge (single_dom_exit (loop));
1440 gsi = gsi_last_bb (bb);
1441 gsi_insert_after (&gsi, gimple_build_omp_return (false), GSI_NEW_STMT);
1443 /* Extract data for GIMPLE_OMP_FOR. */
1444 gcc_assert (loop->header == single_dom_exit (loop)->src);
1445 cond_stmt = last_stmt (loop->header);
1447 cvar = gimple_cond_lhs (cond_stmt);
1448 cvar_base = SSA_NAME_VAR (cvar);
1449 phi = SSA_NAME_DEF_STMT (cvar);
1450 cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1451 initvar = make_ssa_name (cvar_base, NULL);
1452 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
1454 cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1456 gsi = gsi_last_bb (loop->latch);
1457 gcc_assert (gsi_stmt (gsi) == SSA_NAME_DEF_STMT (cvar_next));
1458 gsi_remove (&gsi, true);
1461 for_bb = split_edge (loop_preheader_edge (loop));
1462 ex_bb = split_loop_exit_edge (single_dom_exit (loop));
1463 extract_true_false_edges_from_block (loop->header, &nexit, &exit);
1464 gcc_assert (exit == single_dom_exit (loop));
1466 guard = make_edge (for_bb, ex_bb, 0);
1467 single_succ_edge (loop->latch)->flags = 0;
1468 end = make_edge (loop->latch, ex_bb, EDGE_FALLTHRU);
1469 for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); gsi_next (&gsi))
1471 source_location locus;
1473 phi = gsi_stmt (gsi);
1474 stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi, exit));
1476 def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop));
1477 locus = gimple_phi_arg_location_from_edge (stmt,
1478 loop_preheader_edge (loop));
1479 add_phi_arg (phi, def, guard, locus);
1481 def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_latch_edge (loop));
1482 locus = gimple_phi_arg_location_from_edge (stmt, loop_latch_edge (loop));
1483 add_phi_arg (phi, def, end, locus);
1485 e = redirect_edge_and_branch (exit, nexit->dest);
1486 PENDING_STMT (e) = NULL;
1488 /* Emit GIMPLE_OMP_FOR. */
1489 gimple_cond_set_lhs (cond_stmt, cvar_base);
1490 type = TREE_TYPE (cvar);
1491 t = build_omp_clause (BUILTINS_LOCATION, OMP_CLAUSE_SCHEDULE);
1492 OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
1494 for_stmt = gimple_build_omp_for (NULL, t, 1, NULL);
1495 gimple_omp_for_set_index (for_stmt, 0, initvar);
1496 gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
1497 gimple_omp_for_set_final (for_stmt, 0, gimple_cond_rhs (cond_stmt));
1498 gimple_omp_for_set_cond (for_stmt, 0, gimple_cond_code (cond_stmt));
1499 gimple_omp_for_set_incr (for_stmt, 0, build2 (PLUS_EXPR, type,
1501 build_int_cst (type, 1)));
1503 gsi = gsi_last_bb (for_bb);
1504 gsi_insert_after (&gsi, for_stmt, GSI_NEW_STMT);
1505 SSA_NAME_DEF_STMT (initvar) = for_stmt;
1507 /* Emit GIMPLE_OMP_CONTINUE. */
1508 gsi = gsi_last_bb (loop->latch);
1509 stmt = gimple_build_omp_continue (cvar_next, cvar);
1510 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1511 SSA_NAME_DEF_STMT (cvar_next) = stmt;
1513 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
1514 gsi = gsi_last_bb (ex_bb);
1515 gsi_insert_after (&gsi, gimple_build_omp_return (true), GSI_NEW_STMT);
1520 /* Generates code to execute the iterations of LOOP in N_THREADS
1521 threads in parallel.
1523 NITER describes number of iterations of LOOP.
1524 REDUCTION_LIST describes the reductions existent in the LOOP. */
1527 gen_parallel_loop (struct loop *loop, htab_t reduction_list,
1528 unsigned n_threads, struct tree_niter_desc *niter)
1531 tree many_iterations_cond, type, nit;
1532 tree arg_struct, new_arg_struct;
1534 basic_block parallel_head;
1536 struct clsn_data clsn_data;
1541 ---------------------------------------------------------------------
1544 IV = phi (INIT, IV + STEP)
1550 ---------------------------------------------------------------------
1552 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
1553 we generate the following code:
1555 ---------------------------------------------------------------------
1558 || NITER < MIN_PER_THREAD * N_THREADS)
1562 store all local loop-invariant variables used in body of the loop to DATA.
1563 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
1564 load the variables from DATA.
1565 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
1568 GIMPLE_OMP_CONTINUE;
1569 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
1570 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
1576 IV = phi (INIT, IV + STEP)
1587 /* Create two versions of the loop -- in the old one, we know that the
1588 number of iterations is large enough, and we will transform it into the
1589 loop that will be split to loop_fn, the new one will be used for the
1590 remaining iterations. */
1592 type = TREE_TYPE (niter->niter);
1593 nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true,
1596 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1598 many_iterations_cond =
1599 fold_build2 (GE_EXPR, boolean_type_node,
1600 nit, build_int_cst (type, MIN_PER_THREAD * n_threads));
1601 many_iterations_cond
1602 = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1603 invert_truthvalue (unshare_expr (niter->may_be_zero)),
1604 many_iterations_cond);
1605 many_iterations_cond
1606 = force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
1608 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1609 if (!is_gimple_condexpr (many_iterations_cond))
1611 many_iterations_cond
1612 = force_gimple_operand (many_iterations_cond, &stmts,
1615 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1618 initialize_original_copy_tables ();
1620 /* We assume that the loop usually iterates a lot. */
1621 prob = 4 * REG_BR_PROB_BASE / 5;
1622 loop_version (loop, many_iterations_cond, NULL,
1623 prob, prob, REG_BR_PROB_BASE - prob, true);
1624 update_ssa (TODO_update_ssa);
1625 free_original_copy_tables ();
1627 /* Base all the induction variables in LOOP on a single control one. */
1628 canonicalize_loop_ivs (loop, &nit, true);
1630 /* Ensure that the exit condition is the first statement in the loop. */
1631 transform_to_exit_first_loop (loop, reduction_list, nit);
1633 /* Generate initializations for reductions. */
1634 if (htab_elements (reduction_list) > 0)
1635 htab_traverse (reduction_list, initialize_reductions, loop);
1637 /* Eliminate the references to local variables from the loop. */
1638 gcc_assert (single_exit (loop));
1639 entry = loop_preheader_edge (loop);
1640 exit = single_dom_exit (loop);
1642 eliminate_local_variables (entry, exit);
1643 /* In the old loop, move all variables non-local to the loop to a structure
1644 and back, and create separate decls for the variables used in loop. */
1645 separate_decls_in_region (entry, exit, reduction_list, &arg_struct,
1646 &new_arg_struct, &clsn_data);
1648 /* Create the parallel constructs. */
1649 parallel_head = create_parallel_loop (loop, create_loop_fn (), arg_struct,
1650 new_arg_struct, n_threads);
1651 if (htab_elements (reduction_list) > 0)
1652 create_call_for_reduction (loop, reduction_list, &clsn_data);
1656 /* Cancel the loop (it is simpler to do it here rather than to teach the
1657 expander to do it). */
1658 cancel_loop_tree (loop);
1660 /* Free loop bound estimations that could contain references to
1661 removed statements. */
1662 FOR_EACH_LOOP (li, loop, 0)
1663 free_numbers_of_iterations_estimates_loop (loop);
1665 /* Expand the parallel constructs. We do it directly here instead of running
1666 a separate expand_omp pass, since it is more efficient, and less likely to
1667 cause troubles with further analyses not being able to deal with the
1670 omp_expand_local (parallel_head);
1673 /* Returns true when LOOP contains vector phi nodes. */
1676 loop_has_vector_phi_nodes (struct loop *loop ATTRIBUTE_UNUSED)
1679 basic_block *bbs = get_loop_body_in_dom_order (loop);
1680 gimple_stmt_iterator gsi;
1683 for (i = 0; i < loop->num_nodes; i++)
1684 for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
1685 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi_stmt (gsi)))) == VECTOR_TYPE)
1694 /* Create a reduction_info struct, initialize it with REDUC_STMT
1695 and PHI, insert it to the REDUCTION_LIST. */
1698 build_new_reduction (htab_t reduction_list, gimple reduc_stmt, gimple phi)
1701 struct reduction_info *new_reduction;
1703 gcc_assert (reduc_stmt);
1705 if (dump_file && (dump_flags & TDF_DETAILS))
1708 "Detected reduction. reduction stmt is: \n");
1709 print_gimple_stmt (dump_file, reduc_stmt, 0, 0);
1710 fprintf (dump_file, "\n");
1713 new_reduction = XCNEW (struct reduction_info);
1715 new_reduction->reduc_stmt = reduc_stmt;
1716 new_reduction->reduc_phi = phi;
1717 new_reduction->reduction_code = gimple_assign_rhs_code (reduc_stmt);
1718 slot = htab_find_slot (reduction_list, new_reduction, INSERT);
1719 *slot = new_reduction;
1722 /* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
1725 gather_scalar_reductions (loop_p loop, htab_t reduction_list)
1727 gimple_stmt_iterator gsi;
1728 loop_vec_info simple_loop_info;
1731 simple_loop_info = vect_analyze_loop_form (loop);
1733 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1735 gimple phi = gsi_stmt (gsi);
1737 tree res = PHI_RESULT (phi);
1740 if (!is_gimple_reg (res))
1743 if (!simple_iv (loop, loop, res, &iv, true)
1744 && simple_loop_info)
1746 gimple reduc_stmt = vect_force_simple_reduction (simple_loop_info,
1749 if (reduc_stmt && !double_reduc)
1750 build_new_reduction (reduction_list, reduc_stmt, phi);
1753 destroy_loop_vec_info (simple_loop_info, true);
1756 /* Try to initialize NITER for code generation part. */
1759 try_get_loop_niter (loop_p loop, struct tree_niter_desc *niter)
1761 edge exit = single_dom_exit (loop);
1765 /* We need to know # of iterations, and there should be no uses of values
1766 defined inside loop outside of it, unless the values are invariants of
1768 if (!number_of_iterations_exit (loop, exit, niter, false))
1770 if (dump_file && (dump_flags & TDF_DETAILS))
1771 fprintf (dump_file, " FAILED: number of iterations not known\n");
1778 /* Try to initialize REDUCTION_LIST for code generation part.
1779 REDUCTION_LIST describes the reductions. */
1782 try_create_reduction_list (loop_p loop, htab_t reduction_list)
1784 edge exit = single_dom_exit (loop);
1785 gimple_stmt_iterator gsi;
1789 gather_scalar_reductions (loop, reduction_list);
1792 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
1794 gimple phi = gsi_stmt (gsi);
1795 struct reduction_info *red;
1796 imm_use_iterator imm_iter;
1797 use_operand_p use_p;
1799 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1801 if (is_gimple_reg (val))
1803 if (dump_file && (dump_flags & TDF_DETAILS))
1805 fprintf (dump_file, "phi is ");
1806 print_gimple_stmt (dump_file, phi, 0, 0);
1807 fprintf (dump_file, "arg of phi to exit: value ");
1808 print_generic_expr (dump_file, val, 0);
1809 fprintf (dump_file, " used outside loop\n");
1811 " checking if it a part of reduction pattern: \n");
1813 if (htab_elements (reduction_list) == 0)
1815 if (dump_file && (dump_flags & TDF_DETAILS))
1817 " FAILED: it is not a part of reduction.\n");
1821 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
1823 if (flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
1825 reduc_phi = USE_STMT (use_p);
1829 red = reduction_phi (reduction_list, reduc_phi);
1832 if (dump_file && (dump_flags & TDF_DETAILS))
1834 " FAILED: it is not a part of reduction.\n");
1837 if (dump_file && (dump_flags & TDF_DETAILS))
1839 fprintf (dump_file, "reduction phi is ");
1840 print_gimple_stmt (dump_file, red->reduc_phi, 0, 0);
1841 fprintf (dump_file, "reduction stmt is ");
1842 print_gimple_stmt (dump_file, red->reduc_stmt, 0, 0);
1847 /* The iterations of the loop may communicate only through bivs whose
1848 iteration space can be distributed efficiently. */
1849 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1851 gimple phi = gsi_stmt (gsi);
1852 tree def = PHI_RESULT (phi);
1855 if (is_gimple_reg (def) && !simple_iv (loop, loop, def, &iv, true))
1857 struct reduction_info *red;
1859 red = reduction_phi (reduction_list, phi);
1862 if (dump_file && (dump_flags & TDF_DETAILS))
1864 " FAILED: scalar dependency between iterations\n");
1874 /* Detect parallel loops and generate parallel code using libgomp
1875 primitives. Returns true if some loop was parallelized, false
1879 parallelize_loops (void)
1881 unsigned n_threads = flag_tree_parallelize_loops;
1882 bool changed = false;
1884 struct tree_niter_desc niter_desc;
1886 htab_t reduction_list;
1887 struct obstack parloop_obstack;
1888 HOST_WIDE_INT estimated;
1891 /* Do not parallelize loops in the functions created by parallelization. */
1892 if (parallelized_function_p (cfun->decl))
1894 if (cfun->has_nonlocal_label)
1897 gcc_obstack_init (&parloop_obstack);
1898 reduction_list = htab_create (10, reduction_info_hash,
1899 reduction_info_eq, free);
1900 init_stmt_vec_info_vec ();
1902 FOR_EACH_LOOP (li, loop, 0)
1904 htab_empty (reduction_list);
1905 if (dump_file && (dump_flags & TDF_DETAILS))
1907 fprintf (dump_file, "Trying loop %d as candidate\n",loop->num);
1909 fprintf (dump_file, "loop %d is not innermost\n",loop->num);
1911 fprintf (dump_file, "loop %d is innermost\n",loop->num);
1914 /* If we use autopar in graphite pass, we use its marked dependency
1915 checking results. */
1916 if (flag_loop_parallelize_all && !loop->can_be_parallel)
1918 if (dump_file && (dump_flags & TDF_DETAILS))
1919 fprintf (dump_file, "loop is not parallel according to graphite\n");
1923 if (!single_dom_exit (loop))
1926 if (dump_file && (dump_flags & TDF_DETAILS))
1927 fprintf (dump_file, "loop is !single_dom_exit\n");
1932 if (/* And of course, the loop must be parallelizable. */
1933 !can_duplicate_loop_p (loop)
1934 || loop_has_blocks_with_irreducible_flag (loop)
1935 || (loop_preheader_edge (loop)->src->flags & BB_IRREDUCIBLE_LOOP)
1936 /* FIXME: the check for vector phi nodes could be removed. */
1937 || loop_has_vector_phi_nodes (loop))
1939 estimated = estimated_loop_iterations_int (loop, false);
1940 /* FIXME: Bypass this check as graphite doesn't update the
1941 count and frequency correctly now. */
1942 if (!flag_loop_parallelize_all
1944 && estimated <= (HOST_WIDE_INT) n_threads * MIN_PER_THREAD)
1945 /* Do not bother with loops in cold areas. */
1946 || optimize_loop_nest_for_size_p (loop)))
1949 if (!try_get_loop_niter (loop, &niter_desc))
1952 if (!try_create_reduction_list (loop, reduction_list))
1955 if (!flag_loop_parallelize_all
1956 && !loop_parallel_p (loop, &parloop_obstack))
1960 if (dump_file && (dump_flags & TDF_DETAILS))
1963 fprintf (dump_file, "parallelizing outer loop %d\n",loop->header->index);
1965 fprintf (dump_file, "parallelizing inner loop %d\n",loop->header->index);
1966 loop_loc = find_loop_location (loop);
1967 if (loop_loc != UNKNOWN_LOC)
1968 fprintf (dump_file, "\nloop at %s:%d: ",
1969 LOC_FILE (loop_loc), LOC_LINE (loop_loc));
1971 gen_parallel_loop (loop, reduction_list,
1972 n_threads, &niter_desc);
1973 verify_flow_info ();
1974 verify_dominators (CDI_DOMINATORS);
1975 verify_loop_structure ();
1976 verify_loop_closed_ssa (true);
1979 free_stmt_vec_info_vec ();
1980 htab_delete (reduction_list);
1981 obstack_free (&parloop_obstack, NULL);
1983 /* Parallelization will cause new function calls to be inserted through
1984 which local variables will escape. Reset the points-to solution
1987 pt_solution_reset (&cfun->gimple_df->escaped);
1992 #include "gt-tree-parloops.h"