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;
244 /* Returns true if the iterations of LOOP are independent on each other (that
245 is, if we can execute them in parallel), and if LOOP satisfies other
246 conditions that we need to be able to parallelize it. Description of number
247 of iterations is stored to NITER. Reduction analysis is done, if
248 reductions are found, they are inserted to the REDUCTION_LIST. */
251 loop_parallel_p (struct loop *loop, htab_t reduction_list,
252 struct tree_niter_desc *niter)
254 edge exit = single_dom_exit (loop);
255 VEC (ddr_p, heap) * dependence_relations;
256 VEC (data_reference_p, heap) *datarefs;
257 lambda_trans_matrix trans;
259 gimple_stmt_iterator gsi;
260 loop_vec_info simple_loop_info;
262 /* Only consider innermost loops with just one exit. The innermost-loop
263 restriction is not necessary, but it makes things simpler. */
264 if (loop->inner || !exit)
267 if (dump_file && (dump_flags & TDF_DETAILS))
268 fprintf (dump_file, "\nConsidering loop %d\n", loop->num);
270 /* We need to know # of iterations, and there should be no uses of values
271 defined inside loop outside of it, unless the values are invariants of
273 if (!number_of_iterations_exit (loop, exit, niter, false))
275 if (dump_file && (dump_flags & TDF_DETAILS))
276 fprintf (dump_file, " FAILED: number of iterations not known\n");
281 simple_loop_info = vect_analyze_loop_form (loop);
283 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
285 gimple phi = gsi_stmt (gsi);
286 gimple reduc_stmt = NULL;
288 /* ??? TODO: Change this into a generic function that
289 recognizes reductions. */
290 if (!is_gimple_reg (PHI_RESULT (phi)))
292 if (simple_loop_info)
293 reduc_stmt = vect_is_simple_reduction (simple_loop_info, phi);
295 /* Create a reduction_info struct, initialize it and insert it to
296 the reduction list. */
301 struct reduction_info *new_reduction;
303 if (dump_file && (dump_flags & TDF_DETAILS))
306 "Detected reduction. reduction stmt is: \n");
307 print_gimple_stmt (dump_file, reduc_stmt, 0, 0);
308 fprintf (dump_file, "\n");
311 new_reduction = XCNEW (struct reduction_info);
313 new_reduction->reduc_stmt = reduc_stmt;
314 new_reduction->reduc_phi = phi;
315 new_reduction->reduction_code = gimple_assign_rhs_code (reduc_stmt);
316 slot = htab_find_slot (reduction_list, new_reduction, INSERT);
317 *slot = new_reduction;
321 /* Get rid of the information created by the vectorizer functions. */
322 destroy_loop_vec_info (simple_loop_info, true);
324 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
326 gimple phi = gsi_stmt (gsi);
327 struct reduction_info *red;
328 imm_use_iterator imm_iter;
331 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
333 if (is_gimple_reg (val))
335 if (dump_file && (dump_flags & TDF_DETAILS))
337 fprintf (dump_file, "phi is ");
338 print_gimple_stmt (dump_file, phi, 0, 0);
339 fprintf (dump_file, "arg of phi to exit: value ");
340 print_generic_expr (dump_file, val, 0);
341 fprintf (dump_file, " used outside loop\n");
343 " checking if it a part of reduction pattern: \n");
345 if (htab_elements (reduction_list) == 0)
347 if (dump_file && (dump_flags & TDF_DETAILS))
349 " FAILED: it is not a part of reduction.\n");
353 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
355 if (flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
357 reduc_phi = USE_STMT (use_p);
361 red = reduction_phi (reduction_list, reduc_phi);
364 if (dump_file && (dump_flags & TDF_DETAILS))
366 " FAILED: it is not a part of reduction.\n");
369 if (dump_file && (dump_flags & TDF_DETAILS))
371 fprintf (dump_file, "reduction phi is ");
372 print_gimple_stmt (dump_file, red->reduc_phi, 0, 0);
373 fprintf (dump_file, "reduction stmt is ");
374 print_gimple_stmt (dump_file, red->reduc_stmt, 0, 0);
380 /* The iterations of the loop may communicate only through bivs whose
381 iteration space can be distributed efficiently. */
382 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
384 gimple phi = gsi_stmt (gsi);
385 tree def = PHI_RESULT (phi);
388 if (is_gimple_reg (def) && !simple_iv (loop, phi, def, &iv, true))
390 struct reduction_info *red;
392 red = reduction_phi (reduction_list, phi);
395 if (dump_file && (dump_flags & TDF_DETAILS))
397 " FAILED: scalar dependency between iterations\n");
403 /* We need to version the loop to verify assumptions in runtime. */
404 if (!can_duplicate_loop_p (loop))
406 if (dump_file && (dump_flags & TDF_DETAILS))
407 fprintf (dump_file, " FAILED: cannot be duplicated\n");
411 /* Check for problems with dependences. If the loop can be reversed,
412 the iterations are independent. */
413 datarefs = VEC_alloc (data_reference_p, heap, 10);
414 dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
415 compute_data_dependences_for_loop (loop, true, &datarefs,
416 &dependence_relations);
417 if (dump_file && (dump_flags & TDF_DETAILS))
418 dump_data_dependence_relations (dump_file, dependence_relations);
420 trans = lambda_trans_matrix_new (1, 1);
421 LTM_MATRIX (trans)[0][0] = -1;
423 if (lambda_transform_legal_p (trans, 1, dependence_relations))
426 if (dump_file && (dump_flags & TDF_DETAILS))
427 fprintf (dump_file, " SUCCESS: may be parallelized\n");
429 else if (dump_file && (dump_flags & TDF_DETAILS))
431 " FAILED: data dependencies exist across iterations\n");
433 free_dependence_relations (dependence_relations);
434 free_data_refs (datarefs);
439 /* Return true when LOOP contains basic blocks marked with the
440 BB_IRREDUCIBLE_LOOP flag. */
443 loop_has_blocks_with_irreducible_flag (struct loop *loop)
446 basic_block *bbs = get_loop_body_in_dom_order (loop);
449 for (i = 0; i < loop->num_nodes; i++)
450 if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
459 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
460 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
461 to their addresses that can be reused. The address of OBJ is known to
462 be invariant in the whole function. */
465 take_address_of (tree obj, tree type, edge entry, htab_t decl_address)
469 struct int_tree_map ielt, *nielt;
470 tree *var_p, name, bvar, addr;
474 /* Since the address of OBJ is invariant, the trees may be shared.
475 Avoid rewriting unrelated parts of the code. */
476 obj = unshare_expr (obj);
478 handled_component_p (*var_p);
479 var_p = &TREE_OPERAND (*var_p, 0))
481 uid = DECL_UID (*var_p);
484 dslot = htab_find_slot_with_hash (decl_address, &ielt, uid, INSERT);
487 addr = build_addr (*var_p, current_function_decl);
488 bvar = create_tmp_var (TREE_TYPE (addr), get_name (*var_p));
489 add_referenced_var (bvar);
490 stmt = gimple_build_assign (bvar, addr);
491 name = make_ssa_name (bvar, stmt);
492 gimple_assign_set_lhs (stmt, name);
493 gsi_insert_on_edge_immediate (entry, stmt);
495 nielt = XNEW (struct int_tree_map);
501 name = ((struct int_tree_map *) *dslot)->to;
505 *var_p = build1 (INDIRECT_REF, TREE_TYPE (*var_p), name);
506 name = force_gimple_operand (build_addr (obj, current_function_decl),
507 &stmts, true, NULL_TREE);
508 if (!gimple_seq_empty_p (stmts))
509 gsi_insert_seq_on_edge_immediate (entry, stmts);
512 if (TREE_TYPE (name) != type)
514 name = force_gimple_operand (fold_convert (type, name), &stmts, true,
516 if (!gimple_seq_empty_p (stmts))
517 gsi_insert_seq_on_edge_immediate (entry, stmts);
523 /* Callback for htab_traverse. Create the initialization statement
524 for reduction described in SLOT, and place it at the preheader of
525 the loop described in DATA. */
528 initialize_reductions (void **slot, void *data)
531 tree bvar, type, arg;
534 struct reduction_info *const reduc = (struct reduction_info *) *slot;
535 struct loop *loop = (struct loop *) data;
537 /* Create initialization in preheader:
538 reduction_variable = initialization value of reduction. */
540 /* In the phi node at the header, replace the argument coming
541 from the preheader with the reduction initialization value. */
543 /* Create a new variable to initialize the reduction. */
544 type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
545 bvar = create_tmp_var (type, "reduction");
546 add_referenced_var (bvar);
548 c = build_omp_clause (OMP_CLAUSE_REDUCTION);
549 OMP_CLAUSE_REDUCTION_CODE (c) = reduc->reduction_code;
550 OMP_CLAUSE_DECL (c) = SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt));
552 init = omp_reduction_init (c, TREE_TYPE (bvar));
555 /* Replace the argument representing the initialization value
556 with the initialization value for the reduction (neutral
557 element for the particular operation, e.g. 0 for PLUS_EXPR,
558 1 for MULT_EXPR, etc).
559 Keep the old value in a new variable "reduction_initial",
560 that will be taken in consideration after the parallel
561 computing is done. */
563 e = loop_preheader_edge (loop);
564 arg = PHI_ARG_DEF_FROM_EDGE (reduc->reduc_phi, e);
565 /* Create new variable to hold the initial value. */
567 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
568 (reduc->reduc_phi, loop_preheader_edge (loop)), init);
569 reduc->initial_value = arg;
575 struct walk_stmt_info info;
581 /* Eliminates references to local variables in *TP out of the single
582 entry single exit region starting at DTA->ENTRY.
583 DECL_ADDRESS contains addresses of the references that had their
584 address taken already. If the expression is changed, CHANGED is
585 set to true. Callback for walk_tree. */
588 eliminate_local_variables_1 (tree *tp, int *walk_subtrees, void *data)
590 struct elv_data *const dta = (struct elv_data *) data;
591 tree t = *tp, var, addr, addr_type, type, obj;
597 if (!SSA_VAR_P (t) || DECL_EXTERNAL (t))
600 type = TREE_TYPE (t);
601 addr_type = build_pointer_type (type);
602 addr = take_address_of (t, addr_type, dta->entry, dta->decl_address);
603 *tp = build1 (INDIRECT_REF, TREE_TYPE (*tp), addr);
609 if (TREE_CODE (t) == ADDR_EXPR)
611 /* ADDR_EXPR may appear in two contexts:
612 -- as a gimple operand, when the address taken is a function invariant
613 -- as gimple rhs, when the resulting address in not a function
615 We do not need to do anything special in the latter case (the base of
616 the memory reference whose address is taken may be replaced in the
617 DECL_P case). The former case is more complicated, as we need to
618 ensure that the new address is still a gimple operand. Thus, it
619 is not sufficient to replace just the base of the memory reference --
620 we need to move the whole computation of the address out of the
622 if (!is_gimple_val (t))
626 obj = TREE_OPERAND (t, 0);
627 var = get_base_address (obj);
628 if (!var || !SSA_VAR_P (var) || DECL_EXTERNAL (var))
631 addr_type = TREE_TYPE (t);
632 addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address);
645 /* Moves the references to local variables in STMT out of the single
646 entry single exit region starting at ENTRY. DECL_ADDRESS contains
647 addresses of the references that had their address taken
651 eliminate_local_variables_stmt (edge entry, gimple stmt,
656 memset (&dta.info, '\0', sizeof (dta.info));
658 dta.decl_address = decl_address;
661 walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
667 /* Eliminates the references to local variables from the single entry
668 single exit region between the ENTRY and EXIT edges.
671 1) Taking address of a local variable -- these are moved out of the
672 region (and temporary variable is created to hold the address if
675 2) Dereferencing a local variable -- these are replaced with indirect
679 eliminate_local_variables (edge entry, edge exit)
682 VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
684 gimple_stmt_iterator gsi;
685 htab_t decl_address = htab_create (10, int_tree_map_hash, int_tree_map_eq,
687 basic_block entry_bb = entry->src;
688 basic_block exit_bb = exit->dest;
690 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
692 for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
693 if (bb != entry_bb && bb != exit_bb)
694 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
695 eliminate_local_variables_stmt (entry, gsi_stmt (gsi),
698 htab_delete (decl_address);
699 VEC_free (basic_block, heap, body);
702 /* Returns true if expression EXPR is not defined between ENTRY and
703 EXIT, i.e. if all its operands are defined outside of the region. */
706 expr_invariant_in_region_p (edge entry, edge exit, tree expr)
708 basic_block entry_bb = entry->src;
709 basic_block exit_bb = exit->dest;
712 if (is_gimple_min_invariant (expr))
715 if (TREE_CODE (expr) == SSA_NAME)
717 def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
719 && dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)
720 && !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))
729 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
730 The copies are stored to NAME_COPIES, if NAME was already duplicated,
731 its duplicate stored in NAME_COPIES is returned.
733 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
734 duplicated, storing the copies in DECL_COPIES. */
737 separate_decls_in_region_name (tree name,
738 htab_t name_copies, htab_t decl_copies,
741 tree copy, var, var_copy;
742 unsigned idx, uid, nuid;
743 struct int_tree_map ielt, *nielt;
744 struct name_to_copy_elt elt, *nelt;
745 void **slot, **dslot;
747 if (TREE_CODE (name) != SSA_NAME)
750 idx = SSA_NAME_VERSION (name);
752 slot = htab_find_slot_with_hash (name_copies, &elt, idx,
753 copy_name_p ? INSERT : NO_INSERT);
755 return ((struct name_to_copy_elt *) *slot)->new_name;
757 var = SSA_NAME_VAR (name);
758 uid = DECL_UID (var);
760 dslot = htab_find_slot_with_hash (decl_copies, &ielt, uid, INSERT);
763 var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
764 DECL_GIMPLE_REG_P (var_copy) = DECL_GIMPLE_REG_P (var);
765 add_referenced_var (var_copy);
766 nielt = XNEW (struct int_tree_map);
768 nielt->to = var_copy;
771 /* Ensure that when we meet this decl next time, we won't duplicate
773 nuid = DECL_UID (var_copy);
775 dslot = htab_find_slot_with_hash (decl_copies, &ielt, nuid, INSERT);
776 gcc_assert (!*dslot);
777 nielt = XNEW (struct int_tree_map);
779 nielt->to = var_copy;
783 var_copy = ((struct int_tree_map *) *dslot)->to;
787 copy = duplicate_ssa_name (name, NULL);
788 nelt = XNEW (struct name_to_copy_elt);
790 nelt->new_name = copy;
791 nelt->field = NULL_TREE;
800 SSA_NAME_VAR (copy) = var_copy;
804 /* Finds the ssa names used in STMT that are defined outside the
805 region between ENTRY and EXIT and replaces such ssa names with
806 their duplicates. The duplicates are stored to NAME_COPIES. Base
807 decls of all ssa names used in STMT (including those defined in
808 LOOP) are replaced with the new temporary variables; the
809 replacement decls are stored in DECL_COPIES. */
812 separate_decls_in_region_stmt (edge entry, edge exit, gimple stmt,
813 htab_t name_copies, htab_t decl_copies)
821 mark_virtual_ops_for_renaming (stmt);
823 FOR_EACH_PHI_OR_STMT_DEF (def, stmt, oi, SSA_OP_DEF)
825 name = DEF_FROM_PTR (def);
826 gcc_assert (TREE_CODE (name) == SSA_NAME);
827 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
829 gcc_assert (copy == name);
832 FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
834 name = USE_FROM_PTR (use);
835 if (TREE_CODE (name) != SSA_NAME)
838 copy_name_p = expr_invariant_in_region_p (entry, exit, name);
839 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
845 /* Callback for htab_traverse. Adds a field corresponding to the reduction
846 specified in SLOT. The type is passed in DATA. */
849 add_field_for_reduction (void **slot, void *data)
852 struct reduction_info *const red = (struct reduction_info *) *slot;
853 tree const type = (tree) data;
854 tree var = SSA_NAME_VAR (gimple_assign_lhs (red->reduc_stmt));
855 tree field = build_decl (FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
857 insert_field_into_struct (type, field);
864 /* Callback for htab_traverse. Adds a field corresponding to a ssa name
865 described in SLOT. The type is passed in DATA. */
868 add_field_for_name (void **slot, void *data)
870 struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
871 tree type = (tree) data;
872 tree name = ssa_name (elt->version);
873 tree var = SSA_NAME_VAR (name);
874 tree field = build_decl (FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
876 insert_field_into_struct (type, field);
882 /* Callback for htab_traverse. A local result is the intermediate result
884 thread, or the initial value in case no iteration was executed.
885 This function creates a phi node reflecting these values.
886 The phi's result will be stored in NEW_PHI field of the
887 reduction's data structure. */
890 create_phi_for_local_result (void **slot, void *data)
892 struct reduction_info *const reduc = (struct reduction_info *) *slot;
893 const struct loop *const loop = (const struct loop *) data;
896 basic_block store_bb;
899 /* STORE_BB is the block where the phi
900 should be stored. It is the destination of the loop exit.
901 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
902 store_bb = FALLTHRU_EDGE (loop->latch)->dest;
904 /* STORE_BB has two predecessors. One coming from the loop
905 (the reduction's result is computed at the loop),
906 and another coming from a block preceding the loop,
908 are executed (the initial value should be taken). */
909 if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (loop->latch))
910 e = EDGE_PRED (store_bb, 1);
912 e = EDGE_PRED (store_bb, 0);
914 = make_ssa_name (SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt)),
916 new_phi = create_phi_node (local_res, store_bb);
917 SSA_NAME_DEF_STMT (local_res) = new_phi;
918 add_phi_arg (new_phi, reduc->init, e);
919 add_phi_arg (new_phi, gimple_assign_lhs (reduc->reduc_stmt),
920 FALLTHRU_EDGE (loop->latch));
921 reduc->new_phi = new_phi;
931 basic_block store_bb;
935 /* Callback for htab_traverse. Create an atomic instruction for the
936 reduction described in SLOT.
937 DATA annotates the place in memory the atomic operation relates to,
938 and the basic block it needs to be generated in. */
941 create_call_for_reduction_1 (void **slot, void *data)
943 struct reduction_info *const reduc = (struct reduction_info *) *slot;
944 struct clsn_data *const clsn_data = (struct clsn_data *) data;
945 gimple_stmt_iterator gsi;
946 tree type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
947 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
952 tree t, addr, addr_type, ref, x;
956 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
957 t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
958 addr_type = build_pointer_type (type);
960 addr = build_addr (t, current_function_decl);
962 /* Create phi node. */
963 bb = clsn_data->load_bb;
965 e = split_block (bb, t);
968 tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)), NULL);
969 add_referenced_var (tmp_load);
970 tmp_load = make_ssa_name (tmp_load, NULL);
971 load = gimple_build_omp_atomic_load (tmp_load, addr);
972 SSA_NAME_DEF_STMT (tmp_load) = load;
973 gsi = gsi_start_bb (new_bb);
974 gsi_insert_after (&gsi, load, GSI_NEW_STMT);
976 e = split_block (new_bb, load);
978 gsi = gsi_start_bb (new_bb);
980 x = fold_build2 (reduc->reduction_code,
981 TREE_TYPE (PHI_RESULT (reduc->new_phi)), ref,
982 PHI_RESULT (reduc->new_phi));
984 name = force_gimple_operand_gsi (&gsi, x, true, NULL_TREE, true,
985 GSI_CONTINUE_LINKING);
987 gsi_insert_after (&gsi, gimple_build_omp_atomic_store (name), GSI_NEW_STMT);
991 /* Create the atomic operation at the join point of the threads.
992 REDUCTION_LIST describes the reductions in the LOOP.
993 LD_ST_DATA describes the shared data structure where
994 shared data is stored in and loaded from. */
996 create_call_for_reduction (struct loop *loop, htab_t reduction_list,
997 struct clsn_data *ld_st_data)
999 htab_traverse (reduction_list, create_phi_for_local_result, loop);
1000 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
1001 ld_st_data->load_bb = FALLTHRU_EDGE (loop->latch)->dest;
1002 htab_traverse (reduction_list, create_call_for_reduction_1, ld_st_data);
1005 /* Callback for htab_traverse. Loads the final reduction value at the
1006 join point of all threads, and inserts it in the right place. */
1009 create_loads_for_reductions (void **slot, void *data)
1011 struct reduction_info *const red = (struct reduction_info *) *slot;
1012 struct clsn_data *const clsn_data = (struct clsn_data *) data;
1014 gimple_stmt_iterator gsi;
1015 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
1016 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
1021 gsi = gsi_after_labels (clsn_data->load_bb);
1022 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
1023 load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
1027 name = PHI_RESULT (red->keep_res);
1028 stmt = gimple_build_assign (name, x);
1029 SSA_NAME_DEF_STMT (name) = stmt;
1031 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1033 for (gsi = gsi_start_phis (gimple_bb (red->keep_res));
1034 !gsi_end_p (gsi); gsi_next (&gsi))
1035 if (gsi_stmt (gsi) == red->keep_res)
1037 remove_phi_node (&gsi, false);
1043 /* Load the reduction result that was stored in LD_ST_DATA.
1044 REDUCTION_LIST describes the list of reductions that the
1045 loads should be generated for. */
1047 create_final_loads_for_reduction (htab_t reduction_list,
1048 struct clsn_data *ld_st_data)
1050 gimple_stmt_iterator gsi;
1054 gsi = gsi_after_labels (ld_st_data->load_bb);
1055 t = build_fold_addr_expr (ld_st_data->store);
1056 stmt = gimple_build_assign (ld_st_data->load, t);
1058 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1059 SSA_NAME_DEF_STMT (ld_st_data->load) = stmt;
1061 htab_traverse (reduction_list, create_loads_for_reductions, ld_st_data);
1065 /* Callback for htab_traverse. Store the neutral value for the
1066 particular reduction's operation, e.g. 0 for PLUS_EXPR,
1067 1 for MULT_EXPR, etc. into the reduction field.
1068 The reduction is specified in SLOT. The store information is
1072 create_stores_for_reduction (void **slot, void *data)
1074 struct reduction_info *const red = (struct reduction_info *) *slot;
1075 struct clsn_data *const clsn_data = (struct clsn_data *) data;
1078 gimple_stmt_iterator gsi;
1079 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
1081 gsi = gsi_last_bb (clsn_data->store_bb);
1082 t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE);
1083 stmt = gimple_build_assign (t, red->initial_value);
1084 mark_virtual_ops_for_renaming (stmt);
1085 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1090 /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
1091 store to a field of STORE in STORE_BB for the ssa name and its duplicate
1092 specified in SLOT. */
1095 create_loads_and_stores_for_name (void **slot, void *data)
1097 struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
1098 struct clsn_data *const clsn_data = (struct clsn_data *) data;
1101 gimple_stmt_iterator gsi;
1102 tree type = TREE_TYPE (elt->new_name);
1103 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
1106 gsi = gsi_last_bb (clsn_data->store_bb);
1107 t = build3 (COMPONENT_REF, type, clsn_data->store, elt->field, NULL_TREE);
1108 stmt = gimple_build_assign (t, ssa_name (elt->version));
1109 mark_virtual_ops_for_renaming (stmt);
1110 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1112 gsi = gsi_last_bb (clsn_data->load_bb);
1113 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
1114 t = build3 (COMPONENT_REF, type, load_struct, elt->field, NULL_TREE);
1115 stmt = gimple_build_assign (elt->new_name, t);
1116 SSA_NAME_DEF_STMT (elt->new_name) = stmt;
1117 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1122 /* Moves all the variables used in LOOP and defined outside of it (including
1123 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1124 name) to a structure created for this purpose. The code
1132 is transformed this way:
1147 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1148 pointer `new' is intentionally not initialized (the loop will be split to a
1149 separate function later, and `new' will be initialized from its arguments).
1150 LD_ST_DATA holds information about the shared data structure used to pass
1151 information among the threads. It is initialized here, and
1152 gen_parallel_loop will pass it to create_call_for_reduction that
1153 needs this information. REDUCTION_LIST describes the reductions
1157 separate_decls_in_region (edge entry, edge exit, htab_t reduction_list,
1158 tree *arg_struct, tree *new_arg_struct,
1159 struct clsn_data *ld_st_data)
1162 basic_block bb1 = split_edge (entry);
1163 basic_block bb0 = single_pred (bb1);
1164 htab_t name_copies = htab_create (10, name_to_copy_elt_hash,
1165 name_to_copy_elt_eq, free);
1166 htab_t decl_copies = htab_create (10, int_tree_map_hash, int_tree_map_eq,
1169 tree type, type_name, nvar;
1170 gimple_stmt_iterator gsi;
1171 struct clsn_data clsn_data;
1172 VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
1174 basic_block entry_bb = bb1;
1175 basic_block exit_bb = exit->dest;
1177 entry = single_succ_edge (entry_bb);
1178 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
1180 for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
1182 if (bb != entry_bb && bb != exit_bb)
1184 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1185 separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
1186 name_copies, decl_copies);
1188 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1189 separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
1190 name_copies, decl_copies);
1194 VEC_free (basic_block, heap, body);
1196 if (htab_elements (name_copies) == 0 && reduction_list == 0)
1198 /* It may happen that there is nothing to copy (if there are only
1199 loop carried and external variables in the loop). */
1201 *new_arg_struct = NULL;
1205 /* Create the type for the structure to store the ssa names to. */
1206 type = lang_hooks.types.make_type (RECORD_TYPE);
1207 type_name = build_decl (TYPE_DECL, create_tmp_var_name (".paral_data"),
1209 TYPE_NAME (type) = type_name;
1211 htab_traverse (name_copies, add_field_for_name, type);
1212 if (reduction_list && htab_elements (reduction_list) > 0)
1214 /* Create the fields for reductions. */
1215 htab_traverse (reduction_list, add_field_for_reduction,
1220 /* Create the loads and stores. */
1221 *arg_struct = create_tmp_var (type, ".paral_data_store");
1222 add_referenced_var (*arg_struct);
1223 nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load");
1224 add_referenced_var (nvar);
1225 *new_arg_struct = make_ssa_name (nvar, NULL);
1227 ld_st_data->store = *arg_struct;
1228 ld_st_data->load = *new_arg_struct;
1229 ld_st_data->store_bb = bb0;
1230 ld_st_data->load_bb = bb1;
1232 htab_traverse (name_copies, create_loads_and_stores_for_name,
1235 /* Load the calculation from memory (after the join of the threads). */
1237 if (reduction_list && htab_elements (reduction_list) > 0)
1239 htab_traverse (reduction_list, create_stores_for_reduction,
1241 clsn_data.load = make_ssa_name (nvar, NULL);
1242 clsn_data.load_bb = exit->dest;
1243 clsn_data.store = ld_st_data->store;
1244 create_final_loads_for_reduction (reduction_list, &clsn_data);
1248 htab_delete (decl_copies);
1249 htab_delete (name_copies);
1252 /* Bitmap containing uids of functions created by parallelization. We cannot
1253 allocate it from the default obstack, as it must live across compilation
1254 of several functions; we make it gc allocated instead. */
1256 static GTY(()) bitmap parallelized_functions;
1258 /* Returns true if FN was created by create_loop_fn. */
1261 parallelized_function_p (tree fn)
1263 if (!parallelized_functions || !DECL_ARTIFICIAL (fn))
1266 return bitmap_bit_p (parallelized_functions, DECL_UID (fn));
1269 /* Creates and returns an empty function that will receive the body of
1270 a parallelized loop. */
1273 create_loop_fn (void)
1277 tree decl, type, name, t;
1278 struct function *act_cfun = cfun;
1279 static unsigned loopfn_num;
1281 snprintf (buf, 100, "%s.$loopfn", current_function_name ());
1282 ASM_FORMAT_PRIVATE_NAME (tname, buf, loopfn_num++);
1283 clean_symbol_name (tname);
1284 name = get_identifier (tname);
1285 type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
1287 decl = build_decl (FUNCTION_DECL, name, type);
1288 if (!parallelized_functions)
1289 parallelized_functions = BITMAP_GGC_ALLOC ();
1290 bitmap_set_bit (parallelized_functions, DECL_UID (decl));
1292 TREE_STATIC (decl) = 1;
1293 TREE_USED (decl) = 1;
1294 DECL_ARTIFICIAL (decl) = 1;
1295 DECL_IGNORED_P (decl) = 0;
1296 TREE_PUBLIC (decl) = 0;
1297 DECL_UNINLINABLE (decl) = 1;
1298 DECL_EXTERNAL (decl) = 0;
1299 DECL_CONTEXT (decl) = NULL_TREE;
1300 DECL_INITIAL (decl) = make_node (BLOCK);
1302 t = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
1303 DECL_ARTIFICIAL (t) = 1;
1304 DECL_IGNORED_P (t) = 1;
1305 DECL_RESULT (decl) = t;
1307 t = build_decl (PARM_DECL, get_identifier (".paral_data_param"),
1309 DECL_ARTIFICIAL (t) = 1;
1310 DECL_ARG_TYPE (t) = ptr_type_node;
1311 DECL_CONTEXT (t) = decl;
1313 DECL_ARGUMENTS (decl) = t;
1315 allocate_struct_function (decl, false);
1317 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1319 set_cfun (act_cfun);
1324 /* Bases all the induction variables in LOOP on a single induction variable
1325 (unsigned with base 0 and step 1), whose final value is compared with
1326 NIT. The induction variable is incremented in the loop latch.
1327 REDUCTION_LIST describes the reductions in LOOP. Return the induction
1328 variable that was created. */
1331 canonicalize_loop_ivs (struct loop *loop, htab_t reduction_list, tree nit)
1333 unsigned precision = TYPE_PRECISION (TREE_TYPE (nit));
1334 tree res, type, var_before, val, atype, mtype;
1335 gimple_stmt_iterator gsi, psi;
1339 edge exit = single_dom_exit (loop);
1340 struct reduction_info *red;
1342 for (psi = gsi_start_phis (loop->header);
1343 !gsi_end_p (psi); gsi_next (&psi))
1345 phi = gsi_stmt (psi);
1346 res = PHI_RESULT (phi);
1348 if (is_gimple_reg (res) && TYPE_PRECISION (TREE_TYPE (res)) > precision)
1349 precision = TYPE_PRECISION (TREE_TYPE (res));
1352 type = lang_hooks.types.type_for_size (precision, 1);
1354 gsi = gsi_last_bb (loop->latch);
1355 create_iv (build_int_cst_type (type, 0), build_int_cst (type, 1), NULL_TREE,
1356 loop, &gsi, true, &var_before, NULL);
1358 gsi = gsi_after_labels (loop->header);
1359 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); )
1361 phi = gsi_stmt (psi);
1362 res = PHI_RESULT (phi);
1364 if (!is_gimple_reg (res) || res == var_before)
1370 ok = simple_iv (loop, phi, res, &iv, true);
1373 red = reduction_phi (reduction_list, phi);
1377 /* We preserve the reduction phi nodes. */
1385 remove_phi_node (&psi, false);
1387 atype = TREE_TYPE (res);
1388 mtype = POINTER_TYPE_P (atype) ? sizetype : atype;
1389 val = fold_build2 (MULT_EXPR, mtype, unshare_expr (iv.step),
1390 fold_convert (mtype, var_before));
1391 val = fold_build2 (POINTER_TYPE_P (atype)
1392 ? POINTER_PLUS_EXPR : PLUS_EXPR,
1393 atype, unshare_expr (iv.base), val);
1394 val = force_gimple_operand_gsi (&gsi, val, false, NULL_TREE, true,
1396 stmt = gimple_build_assign (res, val);
1397 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1398 SSA_NAME_DEF_STMT (res) = stmt;
1401 stmt = last_stmt (exit->src);
1402 /* Make the loop exit if the control condition is not satisfied. */
1403 if (exit->flags & EDGE_TRUE_VALUE)
1407 extract_true_false_edges_from_block (exit->src, &te, &fe);
1408 te->flags = EDGE_FALSE_VALUE;
1409 fe->flags = EDGE_TRUE_VALUE;
1411 gimple_cond_set_code (stmt, LT_EXPR);
1412 gimple_cond_set_lhs (stmt, var_before);
1413 gimple_cond_set_rhs (stmt, nit);
1419 /* Moves the exit condition of LOOP to the beginning of its header, and
1420 duplicates the part of the last iteration that gets disabled to the
1421 exit of the loop. NIT is the number of iterations of the loop
1422 (used to initialize the variables in the duplicated part).
1424 TODO: the common case is that latch of the loop is empty and immediately
1425 follows the loop exit. In this case, it would be better not to copy the
1426 body of the loop, but only move the entry of the loop directly before the
1427 exit check and increase the number of iterations of the loop by one.
1428 This may need some additional preconditioning in case NIT = ~0.
1429 REDUCTION_LIST describes the reductions in LOOP. */
1432 transform_to_exit_first_loop (struct loop *loop, htab_t reduction_list, tree nit)
1434 basic_block *bbs, *nbbs, ex_bb, orig_header;
1437 edge exit = single_dom_exit (loop), hpred;
1438 tree control, control_name, res, t;
1439 gimple phi, nphi, cond_stmt, stmt;
1440 gimple_stmt_iterator gsi;
1442 split_block_after_labels (loop->header);
1443 orig_header = single_succ (loop->header);
1444 hpred = single_succ_edge (loop->header);
1446 cond_stmt = last_stmt (exit->src);
1447 control = gimple_cond_lhs (cond_stmt);
1448 gcc_assert (gimple_cond_rhs (cond_stmt) == nit);
1450 /* Make sure that we have phi nodes on exit for all loop header phis
1451 (create_parallel_loop requires that). */
1452 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1454 phi = gsi_stmt (gsi);
1455 res = PHI_RESULT (phi);
1456 t = make_ssa_name (SSA_NAME_VAR (res), phi);
1457 SET_PHI_RESULT (phi, t);
1459 nphi = create_phi_node (res, orig_header);
1460 SSA_NAME_DEF_STMT (res) = nphi;
1461 add_phi_arg (nphi, t, hpred);
1465 gimple_cond_set_lhs (cond_stmt, t);
1466 update_stmt (cond_stmt);
1471 bbs = get_loop_body_in_dom_order (loop);
1472 for (n = 0; bbs[n] != exit->src; n++)
1474 nbbs = XNEWVEC (basic_block, n);
1475 ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
1482 /* Other than reductions, the only gimple reg that should be copied
1483 out of the loop is the control variable. */
1485 control_name = NULL_TREE;
1486 for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); )
1488 phi = gsi_stmt (gsi);
1489 res = PHI_RESULT (phi);
1490 if (!is_gimple_reg (res))
1496 /* Check if it is a part of reduction. If it is,
1497 keep the phi at the reduction's keep_res field. The
1498 PHI_RESULT of this phi is the resulting value of the reduction
1499 variable when exiting the loop. */
1501 exit = single_dom_exit (loop);
1503 if (htab_elements (reduction_list) > 0)
1505 struct reduction_info *red;
1507 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1509 red = reduction_phi (reduction_list, SSA_NAME_DEF_STMT (val));
1512 red->keep_res = phi;
1517 gcc_assert (control_name == NULL_TREE
1518 && SSA_NAME_VAR (res) == SSA_NAME_VAR (control));
1520 remove_phi_node (&gsi, false);
1522 gcc_assert (control_name != NULL_TREE);
1524 /* Initialize the control variable to NIT. */
1525 gsi = gsi_after_labels (ex_bb);
1526 nit = force_gimple_operand_gsi (&gsi,
1527 fold_convert (TREE_TYPE (control_name), nit),
1528 false, NULL_TREE, false, GSI_SAME_STMT);
1529 stmt = gimple_build_assign (control_name, nit);
1530 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1531 SSA_NAME_DEF_STMT (control_name) = stmt;
1534 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
1535 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
1536 NEW_DATA is the variable that should be initialized from the argument
1537 of LOOP_FN. N_THREADS is the requested number of threads. Returns the
1538 basic block containing GIMPLE_OMP_PARALLEL tree. */
1541 create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
1542 tree new_data, unsigned n_threads)
1544 gimple_stmt_iterator gsi;
1545 basic_block bb, paral_bb, for_bb, ex_bb;
1547 gimple stmt, for_stmt, phi, cond_stmt;
1548 tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
1549 edge exit, nexit, guard, end, e;
1551 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
1552 bb = loop_preheader_edge (loop)->src;
1553 paral_bb = single_pred (bb);
1554 gsi = gsi_last_bb (paral_bb);
1556 t = build_omp_clause (OMP_CLAUSE_NUM_THREADS);
1557 OMP_CLAUSE_NUM_THREADS_EXPR (t)
1558 = build_int_cst (integer_type_node, n_threads);
1559 stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
1561 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1563 /* Initialize NEW_DATA. */
1566 gsi = gsi_after_labels (bb);
1568 param = make_ssa_name (DECL_ARGUMENTS (loop_fn), NULL);
1569 stmt = gimple_build_assign (param, build_fold_addr_expr (data));
1570 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1571 SSA_NAME_DEF_STMT (param) = stmt;
1573 stmt = gimple_build_assign (new_data,
1574 fold_convert (TREE_TYPE (new_data), param));
1575 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1576 SSA_NAME_DEF_STMT (new_data) = stmt;
1579 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
1580 bb = split_loop_exit_edge (single_dom_exit (loop));
1581 gsi = gsi_last_bb (bb);
1582 gsi_insert_after (&gsi, gimple_build_omp_return (false), GSI_NEW_STMT);
1584 /* Extract data for GIMPLE_OMP_FOR. */
1585 gcc_assert (loop->header == single_dom_exit (loop)->src);
1586 cond_stmt = last_stmt (loop->header);
1588 cvar = gimple_cond_lhs (cond_stmt);
1589 cvar_base = SSA_NAME_VAR (cvar);
1590 phi = SSA_NAME_DEF_STMT (cvar);
1591 cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1592 initvar = make_ssa_name (cvar_base, NULL);
1593 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
1595 cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1597 gsi = gsi_last_bb (loop->latch);
1598 gcc_assert (gsi_stmt (gsi) == SSA_NAME_DEF_STMT (cvar_next));
1599 gsi_remove (&gsi, true);
1602 for_bb = split_edge (loop_preheader_edge (loop));
1603 ex_bb = split_loop_exit_edge (single_dom_exit (loop));
1604 extract_true_false_edges_from_block (loop->header, &nexit, &exit);
1605 gcc_assert (exit == single_dom_exit (loop));
1607 guard = make_edge (for_bb, ex_bb, 0);
1608 single_succ_edge (loop->latch)->flags = 0;
1609 end = make_edge (loop->latch, ex_bb, EDGE_FALLTHRU);
1610 for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); gsi_next (&gsi))
1612 phi = gsi_stmt (gsi);
1613 res = PHI_RESULT (phi);
1614 stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi, exit));
1616 PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop)),
1618 add_phi_arg (phi, PHI_ARG_DEF_FROM_EDGE (stmt, loop_latch_edge (loop)),
1621 e = redirect_edge_and_branch (exit, nexit->dest);
1622 PENDING_STMT (e) = NULL;
1624 /* Emit GIMPLE_OMP_FOR. */
1625 gimple_cond_set_lhs (cond_stmt, cvar_base);
1626 type = TREE_TYPE (cvar);
1627 t = build_omp_clause (OMP_CLAUSE_SCHEDULE);
1628 OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
1630 for_stmt = gimple_build_omp_for (NULL, t, 1, NULL);
1631 gimple_omp_for_set_index (for_stmt, 0, initvar);
1632 gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
1633 gimple_omp_for_set_final (for_stmt, 0, gimple_cond_rhs (cond_stmt));
1634 gimple_omp_for_set_cond (for_stmt, 0, gimple_cond_code (cond_stmt));
1635 gimple_omp_for_set_incr (for_stmt, 0, build2 (PLUS_EXPR, type,
1637 build_int_cst (type, 1)));
1639 gsi = gsi_last_bb (for_bb);
1640 gsi_insert_after (&gsi, for_stmt, GSI_NEW_STMT);
1641 SSA_NAME_DEF_STMT (initvar) = for_stmt;
1643 /* Emit GIMPLE_OMP_CONTINUE. */
1644 gsi = gsi_last_bb (loop->latch);
1645 stmt = gimple_build_omp_continue (cvar_next, cvar);
1646 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1647 SSA_NAME_DEF_STMT (cvar_next) = stmt;
1649 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
1650 gsi = gsi_last_bb (ex_bb);
1651 gsi_insert_after (&gsi, gimple_build_omp_return (true), GSI_NEW_STMT);
1656 /* Generates code to execute the iterations of LOOP in N_THREADS threads in
1657 parallel. NITER describes number of iterations of LOOP.
1658 REDUCTION_LIST describes the reductions existent in the LOOP. */
1661 gen_parallel_loop (struct loop *loop, htab_t reduction_list,
1662 unsigned n_threads, struct tree_niter_desc *niter)
1666 tree many_iterations_cond, type, nit;
1667 tree arg_struct, new_arg_struct;
1669 basic_block parallel_head;
1671 struct clsn_data clsn_data;
1676 ---------------------------------------------------------------------
1679 IV = phi (INIT, IV + STEP)
1685 ---------------------------------------------------------------------
1687 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
1688 we generate the following code:
1690 ---------------------------------------------------------------------
1693 || NITER < MIN_PER_THREAD * N_THREADS)
1697 store all local loop-invariant variables used in body of the loop to DATA.
1698 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
1699 load the variables from DATA.
1700 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
1703 GIMPLE_OMP_CONTINUE;
1704 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
1705 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
1711 IV = phi (INIT, IV + STEP)
1722 /* Create two versions of the loop -- in the old one, we know that the
1723 number of iterations is large enough, and we will transform it into the
1724 loop that will be split to loop_fn, the new one will be used for the
1725 remaining iterations. */
1727 type = TREE_TYPE (niter->niter);
1728 nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true,
1731 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1733 many_iterations_cond =
1734 fold_build2 (GE_EXPR, boolean_type_node,
1735 nit, build_int_cst (type, MIN_PER_THREAD * n_threads));
1736 many_iterations_cond
1737 = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1738 invert_truthvalue (unshare_expr (niter->may_be_zero)),
1739 many_iterations_cond);
1740 many_iterations_cond
1741 = force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
1743 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1744 if (!is_gimple_condexpr (many_iterations_cond))
1746 many_iterations_cond
1747 = force_gimple_operand (many_iterations_cond, &stmts,
1750 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1753 initialize_original_copy_tables ();
1755 /* We assume that the loop usually iterates a lot. */
1756 prob = 4 * REG_BR_PROB_BASE / 5;
1757 nloop = loop_version (loop, many_iterations_cond, NULL,
1758 prob, prob, REG_BR_PROB_BASE - prob, true);
1759 update_ssa (TODO_update_ssa);
1760 free_original_copy_tables ();
1762 /* Base all the induction variables in LOOP on a single control one. */
1763 canonicalize_loop_ivs (loop, reduction_list, nit);
1765 /* Ensure that the exit condition is the first statement in the loop. */
1766 transform_to_exit_first_loop (loop, reduction_list, nit);
1768 /* Generate initializations for reductions. */
1769 if (htab_elements (reduction_list) > 0)
1770 htab_traverse (reduction_list, initialize_reductions, loop);
1772 /* Eliminate the references to local variables from the loop. */
1773 gcc_assert (single_exit (loop));
1774 entry = loop_preheader_edge (loop);
1775 exit = single_dom_exit (loop);
1777 eliminate_local_variables (entry, exit);
1778 /* In the old loop, move all variables non-local to the loop to a structure
1779 and back, and create separate decls for the variables used in loop. */
1780 separate_decls_in_region (entry, exit, reduction_list, &arg_struct,
1781 &new_arg_struct, &clsn_data);
1783 /* Create the parallel constructs. */
1784 parallel_head = create_parallel_loop (loop, create_loop_fn (), arg_struct,
1785 new_arg_struct, n_threads);
1786 if (htab_elements (reduction_list) > 0)
1787 create_call_for_reduction (loop, reduction_list, &clsn_data);
1791 /* Cancel the loop (it is simpler to do it here rather than to teach the
1792 expander to do it). */
1793 cancel_loop_tree (loop);
1795 /* Free loop bound estimations that could contain references to
1796 removed statements. */
1797 FOR_EACH_LOOP (li, loop, 0)
1798 free_numbers_of_iterations_estimates_loop (loop);
1800 /* Expand the parallel constructs. We do it directly here instead of running
1801 a separate expand_omp pass, since it is more efficient, and less likely to
1802 cause troubles with further analyses not being able to deal with the
1805 omp_expand_local (parallel_head);
1808 /* Returns true when LOOP contains vector phi nodes. */
1811 loop_has_vector_phi_nodes (struct loop *loop ATTRIBUTE_UNUSED)
1814 basic_block *bbs = get_loop_body_in_dom_order (loop);
1815 gimple_stmt_iterator gsi;
1818 for (i = 0; i < loop->num_nodes; i++)
1819 for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
1820 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi_stmt (gsi)))) == VECTOR_TYPE)
1829 /* Detect parallel loops and generate parallel code using libgomp
1830 primitives. Returns true if some loop was parallelized, false
1834 parallelize_loops (void)
1836 unsigned n_threads = flag_tree_parallelize_loops;
1837 bool changed = false;
1839 struct tree_niter_desc niter_desc;
1841 htab_t reduction_list;
1843 /* Do not parallelize loops in the functions created by parallelization. */
1844 if (parallelized_function_p (cfun->decl))
1847 reduction_list = htab_create (10, reduction_info_hash,
1848 reduction_info_eq, free);
1849 init_stmt_vec_info_vec ();
1851 FOR_EACH_LOOP (li, loop, 0)
1853 htab_empty (reduction_list);
1854 if (/* Do not bother with loops in cold areas. */
1855 optimize_loop_nest_for_size_p (loop)
1856 /* Or loops that roll too little. */
1857 || expected_loop_iterations (loop) <= n_threads
1858 /* And of course, the loop must be parallelizable. */
1859 || !can_duplicate_loop_p (loop)
1860 || loop_has_blocks_with_irreducible_flag (loop)
1861 /* FIXME: the check for vector phi nodes could be removed. */
1862 || loop_has_vector_phi_nodes (loop)
1863 || !loop_parallel_p (loop, reduction_list, &niter_desc))
1867 gen_parallel_loop (loop, reduction_list, n_threads, &niter_desc);
1868 verify_flow_info ();
1869 verify_dominators (CDI_DOMINATORS);
1870 verify_loop_structure ();
1871 verify_loop_closed_ssa ();
1874 free_stmt_vec_info_vec ();
1875 htab_delete (reduction_list);
1879 #include "gt-tree-parloops.h"