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;
289 /* ??? TODO: Change this into a generic function that
290 recognizes reductions. */
291 if (!is_gimple_reg (PHI_RESULT (phi)))
293 if (simple_loop_info)
294 reduc_stmt = vect_is_simple_reduction (simple_loop_info, phi, true,
297 /* Create a reduction_info struct, initialize it and insert it to
298 the reduction list. */
303 struct reduction_info *new_reduction;
305 if (dump_file && (dump_flags & TDF_DETAILS))
308 "Detected reduction. reduction stmt is: \n");
309 print_gimple_stmt (dump_file, reduc_stmt, 0, 0);
310 fprintf (dump_file, "\n");
313 new_reduction = XCNEW (struct reduction_info);
315 new_reduction->reduc_stmt = reduc_stmt;
316 new_reduction->reduc_phi = phi;
317 new_reduction->reduction_code = gimple_assign_rhs_code (reduc_stmt);
318 slot = htab_find_slot (reduction_list, new_reduction, INSERT);
319 *slot = new_reduction;
323 /* Get rid of the information created by the vectorizer functions. */
324 destroy_loop_vec_info (simple_loop_info, true);
326 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
328 gimple phi = gsi_stmt (gsi);
329 struct reduction_info *red;
330 imm_use_iterator imm_iter;
333 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
335 if (is_gimple_reg (val))
337 if (dump_file && (dump_flags & TDF_DETAILS))
339 fprintf (dump_file, "phi is ");
340 print_gimple_stmt (dump_file, phi, 0, 0);
341 fprintf (dump_file, "arg of phi to exit: value ");
342 print_generic_expr (dump_file, val, 0);
343 fprintf (dump_file, " used outside loop\n");
345 " checking if it a part of reduction pattern: \n");
347 if (htab_elements (reduction_list) == 0)
349 if (dump_file && (dump_flags & TDF_DETAILS))
351 " FAILED: it is not a part of reduction.\n");
355 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
357 if (flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
359 reduc_phi = USE_STMT (use_p);
363 red = reduction_phi (reduction_list, reduc_phi);
366 if (dump_file && (dump_flags & TDF_DETAILS))
368 " FAILED: it is not a part of reduction.\n");
371 if (dump_file && (dump_flags & TDF_DETAILS))
373 fprintf (dump_file, "reduction phi is ");
374 print_gimple_stmt (dump_file, red->reduc_phi, 0, 0);
375 fprintf (dump_file, "reduction stmt is ");
376 print_gimple_stmt (dump_file, red->reduc_stmt, 0, 0);
382 /* The iterations of the loop may communicate only through bivs whose
383 iteration space can be distributed efficiently. */
384 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
386 gimple phi = gsi_stmt (gsi);
387 tree def = PHI_RESULT (phi);
390 if (is_gimple_reg (def) && !simple_iv (loop, loop, def, &iv, true))
392 struct reduction_info *red;
394 red = reduction_phi (reduction_list, phi);
397 if (dump_file && (dump_flags & TDF_DETAILS))
399 " FAILED: scalar dependency between iterations\n");
405 /* We need to version the loop to verify assumptions in runtime. */
406 if (!can_duplicate_loop_p (loop))
408 if (dump_file && (dump_flags & TDF_DETAILS))
409 fprintf (dump_file, " FAILED: cannot be duplicated\n");
413 /* Check for problems with dependences. If the loop can be reversed,
414 the iterations are independent. */
415 datarefs = VEC_alloc (data_reference_p, heap, 10);
416 dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
417 compute_data_dependences_for_loop (loop, true, &datarefs,
418 &dependence_relations);
419 if (dump_file && (dump_flags & TDF_DETAILS))
420 dump_data_dependence_relations (dump_file, dependence_relations);
422 trans = lambda_trans_matrix_new (1, 1);
423 LTM_MATRIX (trans)[0][0] = -1;
425 if (lambda_transform_legal_p (trans, 1, dependence_relations))
428 if (dump_file && (dump_flags & TDF_DETAILS))
429 fprintf (dump_file, " SUCCESS: may be parallelized\n");
431 else if (dump_file && (dump_flags & TDF_DETAILS))
433 " FAILED: data dependencies exist across iterations\n");
435 free_dependence_relations (dependence_relations);
436 free_data_refs (datarefs);
441 /* Return true when LOOP contains basic blocks marked with the
442 BB_IRREDUCIBLE_LOOP flag. */
445 loop_has_blocks_with_irreducible_flag (struct loop *loop)
448 basic_block *bbs = get_loop_body_in_dom_order (loop);
451 for (i = 0; i < loop->num_nodes; i++)
452 if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
461 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
462 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
463 to their addresses that can be reused. The address of OBJ is known to
464 be invariant in the whole function. */
467 take_address_of (tree obj, tree type, edge entry, htab_t decl_address)
471 struct int_tree_map ielt, *nielt;
472 tree *var_p, name, bvar, addr;
476 /* Since the address of OBJ is invariant, the trees may be shared.
477 Avoid rewriting unrelated parts of the code. */
478 obj = unshare_expr (obj);
480 handled_component_p (*var_p);
481 var_p = &TREE_OPERAND (*var_p, 0))
483 uid = DECL_UID (*var_p);
486 dslot = htab_find_slot_with_hash (decl_address, &ielt, uid, INSERT);
489 addr = build_addr (*var_p, current_function_decl);
490 bvar = create_tmp_var (TREE_TYPE (addr), get_name (*var_p));
491 add_referenced_var (bvar);
492 stmt = gimple_build_assign (bvar, addr);
493 name = make_ssa_name (bvar, stmt);
494 gimple_assign_set_lhs (stmt, name);
495 gsi_insert_on_edge_immediate (entry, stmt);
497 nielt = XNEW (struct int_tree_map);
503 name = ((struct int_tree_map *) *dslot)->to;
507 *var_p = build1 (INDIRECT_REF, TREE_TYPE (*var_p), name);
508 name = force_gimple_operand (build_addr (obj, current_function_decl),
509 &stmts, true, NULL_TREE);
510 if (!gimple_seq_empty_p (stmts))
511 gsi_insert_seq_on_edge_immediate (entry, stmts);
514 if (TREE_TYPE (name) != type)
516 name = force_gimple_operand (fold_convert (type, name), &stmts, true,
518 if (!gimple_seq_empty_p (stmts))
519 gsi_insert_seq_on_edge_immediate (entry, stmts);
525 /* Callback for htab_traverse. Create the initialization statement
526 for reduction described in SLOT, and place it at the preheader of
527 the loop described in DATA. */
530 initialize_reductions (void **slot, void *data)
533 tree bvar, type, arg;
536 struct reduction_info *const reduc = (struct reduction_info *) *slot;
537 struct loop *loop = (struct loop *) data;
539 /* Create initialization in preheader:
540 reduction_variable = initialization value of reduction. */
542 /* In the phi node at the header, replace the argument coming
543 from the preheader with the reduction initialization value. */
545 /* Create a new variable to initialize the reduction. */
546 type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
547 bvar = create_tmp_var (type, "reduction");
548 add_referenced_var (bvar);
550 c = build_omp_clause (gimple_location (reduc->reduc_stmt),
551 OMP_CLAUSE_REDUCTION);
552 OMP_CLAUSE_REDUCTION_CODE (c) = reduc->reduction_code;
553 OMP_CLAUSE_DECL (c) = SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt));
555 init = omp_reduction_init (c, TREE_TYPE (bvar));
558 /* Replace the argument representing the initialization value
559 with the initialization value for the reduction (neutral
560 element for the particular operation, e.g. 0 for PLUS_EXPR,
561 1 for MULT_EXPR, etc).
562 Keep the old value in a new variable "reduction_initial",
563 that will be taken in consideration after the parallel
564 computing is done. */
566 e = loop_preheader_edge (loop);
567 arg = PHI_ARG_DEF_FROM_EDGE (reduc->reduc_phi, e);
568 /* Create new variable to hold the initial value. */
570 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
571 (reduc->reduc_phi, loop_preheader_edge (loop)), init);
572 reduc->initial_value = arg;
578 struct walk_stmt_info info;
584 /* Eliminates references to local variables in *TP out of the single
585 entry single exit region starting at DTA->ENTRY.
586 DECL_ADDRESS contains addresses of the references that had their
587 address taken already. If the expression is changed, CHANGED is
588 set to true. Callback for walk_tree. */
591 eliminate_local_variables_1 (tree *tp, int *walk_subtrees, void *data)
593 struct elv_data *const dta = (struct elv_data *) data;
594 tree t = *tp, var, addr, addr_type, type, obj;
600 if (!SSA_VAR_P (t) || DECL_EXTERNAL (t))
603 type = TREE_TYPE (t);
604 addr_type = build_pointer_type (type);
605 addr = take_address_of (t, addr_type, dta->entry, dta->decl_address);
606 *tp = build1 (INDIRECT_REF, TREE_TYPE (*tp), addr);
612 if (TREE_CODE (t) == ADDR_EXPR)
614 /* ADDR_EXPR may appear in two contexts:
615 -- as a gimple operand, when the address taken is a function invariant
616 -- as gimple rhs, when the resulting address in not a function
618 We do not need to do anything special in the latter case (the base of
619 the memory reference whose address is taken may be replaced in the
620 DECL_P case). The former case is more complicated, as we need to
621 ensure that the new address is still a gimple operand. Thus, it
622 is not sufficient to replace just the base of the memory reference --
623 we need to move the whole computation of the address out of the
625 if (!is_gimple_val (t))
629 obj = TREE_OPERAND (t, 0);
630 var = get_base_address (obj);
631 if (!var || !SSA_VAR_P (var) || DECL_EXTERNAL (var))
634 addr_type = TREE_TYPE (t);
635 addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address);
648 /* Moves the references to local variables in STMT out of the single
649 entry single exit region starting at ENTRY. DECL_ADDRESS contains
650 addresses of the references that had their address taken
654 eliminate_local_variables_stmt (edge entry, gimple stmt,
659 memset (&dta.info, '\0', sizeof (dta.info));
661 dta.decl_address = decl_address;
664 walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
670 /* Eliminates the references to local variables from the single entry
671 single exit region between the ENTRY and EXIT edges.
674 1) Taking address of a local variable -- these are moved out of the
675 region (and temporary variable is created to hold the address if
678 2) Dereferencing a local variable -- these are replaced with indirect
682 eliminate_local_variables (edge entry, edge exit)
685 VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
687 gimple_stmt_iterator gsi;
688 htab_t decl_address = htab_create (10, int_tree_map_hash, int_tree_map_eq,
690 basic_block entry_bb = entry->src;
691 basic_block exit_bb = exit->dest;
693 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
695 for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
696 if (bb != entry_bb && bb != exit_bb)
697 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
698 eliminate_local_variables_stmt (entry, gsi_stmt (gsi),
701 htab_delete (decl_address);
702 VEC_free (basic_block, heap, body);
705 /* Returns true if expression EXPR is not defined between ENTRY and
706 EXIT, i.e. if all its operands are defined outside of the region. */
709 expr_invariant_in_region_p (edge entry, edge exit, tree expr)
711 basic_block entry_bb = entry->src;
712 basic_block exit_bb = exit->dest;
715 if (is_gimple_min_invariant (expr))
718 if (TREE_CODE (expr) == SSA_NAME)
720 def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
722 && dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)
723 && !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))
732 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
733 The copies are stored to NAME_COPIES, if NAME was already duplicated,
734 its duplicate stored in NAME_COPIES is returned.
736 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
737 duplicated, storing the copies in DECL_COPIES. */
740 separate_decls_in_region_name (tree name,
741 htab_t name_copies, htab_t decl_copies,
744 tree copy, var, var_copy;
745 unsigned idx, uid, nuid;
746 struct int_tree_map ielt, *nielt;
747 struct name_to_copy_elt elt, *nelt;
748 void **slot, **dslot;
750 if (TREE_CODE (name) != SSA_NAME)
753 idx = SSA_NAME_VERSION (name);
755 slot = htab_find_slot_with_hash (name_copies, &elt, idx,
756 copy_name_p ? INSERT : NO_INSERT);
758 return ((struct name_to_copy_elt *) *slot)->new_name;
760 var = SSA_NAME_VAR (name);
761 uid = DECL_UID (var);
763 dslot = htab_find_slot_with_hash (decl_copies, &ielt, uid, INSERT);
766 var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
767 DECL_GIMPLE_REG_P (var_copy) = DECL_GIMPLE_REG_P (var);
768 add_referenced_var (var_copy);
769 nielt = XNEW (struct int_tree_map);
771 nielt->to = var_copy;
774 /* Ensure that when we meet this decl next time, we won't duplicate
776 nuid = DECL_UID (var_copy);
778 dslot = htab_find_slot_with_hash (decl_copies, &ielt, nuid, INSERT);
779 gcc_assert (!*dslot);
780 nielt = XNEW (struct int_tree_map);
782 nielt->to = var_copy;
786 var_copy = ((struct int_tree_map *) *dslot)->to;
790 copy = duplicate_ssa_name (name, NULL);
791 nelt = XNEW (struct name_to_copy_elt);
793 nelt->new_name = copy;
794 nelt->field = NULL_TREE;
803 SSA_NAME_VAR (copy) = var_copy;
807 /* Finds the ssa names used in STMT that are defined outside the
808 region between ENTRY and EXIT and replaces such ssa names with
809 their duplicates. The duplicates are stored to NAME_COPIES. Base
810 decls of all ssa names used in STMT (including those defined in
811 LOOP) are replaced with the new temporary variables; the
812 replacement decls are stored in DECL_COPIES. */
815 separate_decls_in_region_stmt (edge entry, edge exit, gimple stmt,
816 htab_t name_copies, htab_t decl_copies)
824 mark_virtual_ops_for_renaming (stmt);
826 FOR_EACH_PHI_OR_STMT_DEF (def, stmt, oi, SSA_OP_DEF)
828 name = DEF_FROM_PTR (def);
829 gcc_assert (TREE_CODE (name) == SSA_NAME);
830 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
832 gcc_assert (copy == name);
835 FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
837 name = USE_FROM_PTR (use);
838 if (TREE_CODE (name) != SSA_NAME)
841 copy_name_p = expr_invariant_in_region_p (entry, exit, name);
842 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
848 /* Callback for htab_traverse. Adds a field corresponding to the reduction
849 specified in SLOT. The type is passed in DATA. */
852 add_field_for_reduction (void **slot, void *data)
855 struct reduction_info *const red = (struct reduction_info *) *slot;
856 tree const type = (tree) data;
857 tree var = SSA_NAME_VAR (gimple_assign_lhs (red->reduc_stmt));
858 tree field = build_decl (gimple_location (red->reduc_stmt),
859 FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
861 insert_field_into_struct (type, field);
868 /* Callback for htab_traverse. Adds a field corresponding to a ssa name
869 described in SLOT. The type is passed in DATA. */
872 add_field_for_name (void **slot, void *data)
874 struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
875 tree type = (tree) data;
876 tree name = ssa_name (elt->version);
877 tree var = SSA_NAME_VAR (name);
878 tree field = build_decl (DECL_SOURCE_LOCATION (var),
879 FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
881 insert_field_into_struct (type, field);
887 /* Callback for htab_traverse. A local result is the intermediate result
889 thread, or the initial value in case no iteration was executed.
890 This function creates a phi node reflecting these values.
891 The phi's result will be stored in NEW_PHI field of the
892 reduction's data structure. */
895 create_phi_for_local_result (void **slot, void *data)
897 struct reduction_info *const reduc = (struct reduction_info *) *slot;
898 const struct loop *const loop = (const struct loop *) data;
901 basic_block store_bb;
904 /* STORE_BB is the block where the phi
905 should be stored. It is the destination of the loop exit.
906 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
907 store_bb = FALLTHRU_EDGE (loop->latch)->dest;
909 /* STORE_BB has two predecessors. One coming from the loop
910 (the reduction's result is computed at the loop),
911 and another coming from a block preceding the loop,
913 are executed (the initial value should be taken). */
914 if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (loop->latch))
915 e = EDGE_PRED (store_bb, 1);
917 e = EDGE_PRED (store_bb, 0);
919 = make_ssa_name (SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt)),
921 new_phi = create_phi_node (local_res, store_bb);
922 SSA_NAME_DEF_STMT (local_res) = new_phi;
923 add_phi_arg (new_phi, reduc->init, e);
924 add_phi_arg (new_phi, gimple_assign_lhs (reduc->reduc_stmt),
925 FALLTHRU_EDGE (loop->latch));
926 reduc->new_phi = new_phi;
936 basic_block store_bb;
940 /* Callback for htab_traverse. Create an atomic instruction for the
941 reduction described in SLOT.
942 DATA annotates the place in memory the atomic operation relates to,
943 and the basic block it needs to be generated in. */
946 create_call_for_reduction_1 (void **slot, void *data)
948 struct reduction_info *const reduc = (struct reduction_info *) *slot;
949 struct clsn_data *const clsn_data = (struct clsn_data *) data;
950 gimple_stmt_iterator gsi;
951 tree type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
952 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
957 tree t, addr, addr_type, ref, x;
961 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
962 t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
963 addr_type = build_pointer_type (type);
965 addr = build_addr (t, current_function_decl);
967 /* Create phi node. */
968 bb = clsn_data->load_bb;
970 e = split_block (bb, t);
973 tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)), NULL);
974 add_referenced_var (tmp_load);
975 tmp_load = make_ssa_name (tmp_load, NULL);
976 load = gimple_build_omp_atomic_load (tmp_load, addr);
977 SSA_NAME_DEF_STMT (tmp_load) = load;
978 gsi = gsi_start_bb (new_bb);
979 gsi_insert_after (&gsi, load, GSI_NEW_STMT);
981 e = split_block (new_bb, load);
983 gsi = gsi_start_bb (new_bb);
985 x = fold_build2 (reduc->reduction_code,
986 TREE_TYPE (PHI_RESULT (reduc->new_phi)), ref,
987 PHI_RESULT (reduc->new_phi));
989 name = force_gimple_operand_gsi (&gsi, x, true, NULL_TREE, true,
990 GSI_CONTINUE_LINKING);
992 gsi_insert_after (&gsi, gimple_build_omp_atomic_store (name), GSI_NEW_STMT);
996 /* Create the atomic operation at the join point of the threads.
997 REDUCTION_LIST describes the reductions in the LOOP.
998 LD_ST_DATA describes the shared data structure where
999 shared data is stored in and loaded from. */
1001 create_call_for_reduction (struct loop *loop, htab_t reduction_list,
1002 struct clsn_data *ld_st_data)
1004 htab_traverse (reduction_list, create_phi_for_local_result, loop);
1005 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
1006 ld_st_data->load_bb = FALLTHRU_EDGE (loop->latch)->dest;
1007 htab_traverse (reduction_list, create_call_for_reduction_1, ld_st_data);
1010 /* Callback for htab_traverse. Loads the final reduction value at the
1011 join point of all threads, and inserts it in the right place. */
1014 create_loads_for_reductions (void **slot, void *data)
1016 struct reduction_info *const red = (struct reduction_info *) *slot;
1017 struct clsn_data *const clsn_data = (struct clsn_data *) data;
1019 gimple_stmt_iterator gsi;
1020 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
1021 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
1026 gsi = gsi_after_labels (clsn_data->load_bb);
1027 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
1028 load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
1032 name = PHI_RESULT (red->keep_res);
1033 stmt = gimple_build_assign (name, x);
1034 SSA_NAME_DEF_STMT (name) = stmt;
1036 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1038 for (gsi = gsi_start_phis (gimple_bb (red->keep_res));
1039 !gsi_end_p (gsi); gsi_next (&gsi))
1040 if (gsi_stmt (gsi) == red->keep_res)
1042 remove_phi_node (&gsi, false);
1048 /* Load the reduction result that was stored in LD_ST_DATA.
1049 REDUCTION_LIST describes the list of reductions that the
1050 loads should be generated for. */
1052 create_final_loads_for_reduction (htab_t reduction_list,
1053 struct clsn_data *ld_st_data)
1055 gimple_stmt_iterator gsi;
1059 gsi = gsi_after_labels (ld_st_data->load_bb);
1060 t = build_fold_addr_expr (ld_st_data->store);
1061 stmt = gimple_build_assign (ld_st_data->load, t);
1063 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1064 SSA_NAME_DEF_STMT (ld_st_data->load) = stmt;
1066 htab_traverse (reduction_list, create_loads_for_reductions, ld_st_data);
1070 /* Callback for htab_traverse. Store the neutral value for the
1071 particular reduction's operation, e.g. 0 for PLUS_EXPR,
1072 1 for MULT_EXPR, etc. into the reduction field.
1073 The reduction is specified in SLOT. The store information is
1077 create_stores_for_reduction (void **slot, void *data)
1079 struct reduction_info *const red = (struct reduction_info *) *slot;
1080 struct clsn_data *const clsn_data = (struct clsn_data *) data;
1083 gimple_stmt_iterator gsi;
1084 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
1086 gsi = gsi_last_bb (clsn_data->store_bb);
1087 t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE);
1088 stmt = gimple_build_assign (t, red->initial_value);
1089 mark_virtual_ops_for_renaming (stmt);
1090 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1095 /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
1096 store to a field of STORE in STORE_BB for the ssa name and its duplicate
1097 specified in SLOT. */
1100 create_loads_and_stores_for_name (void **slot, void *data)
1102 struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
1103 struct clsn_data *const clsn_data = (struct clsn_data *) data;
1106 gimple_stmt_iterator gsi;
1107 tree type = TREE_TYPE (elt->new_name);
1108 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
1111 gsi = gsi_last_bb (clsn_data->store_bb);
1112 t = build3 (COMPONENT_REF, type, clsn_data->store, elt->field, NULL_TREE);
1113 stmt = gimple_build_assign (t, ssa_name (elt->version));
1114 mark_virtual_ops_for_renaming (stmt);
1115 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1117 gsi = gsi_last_bb (clsn_data->load_bb);
1118 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
1119 t = build3 (COMPONENT_REF, type, load_struct, elt->field, NULL_TREE);
1120 stmt = gimple_build_assign (elt->new_name, t);
1121 SSA_NAME_DEF_STMT (elt->new_name) = stmt;
1122 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1127 /* Moves all the variables used in LOOP and defined outside of it (including
1128 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1129 name) to a structure created for this purpose. The code
1137 is transformed this way:
1152 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1153 pointer `new' is intentionally not initialized (the loop will be split to a
1154 separate function later, and `new' will be initialized from its arguments).
1155 LD_ST_DATA holds information about the shared data structure used to pass
1156 information among the threads. It is initialized here, and
1157 gen_parallel_loop will pass it to create_call_for_reduction that
1158 needs this information. REDUCTION_LIST describes the reductions
1162 separate_decls_in_region (edge entry, edge exit, htab_t reduction_list,
1163 tree *arg_struct, tree *new_arg_struct,
1164 struct clsn_data *ld_st_data)
1167 basic_block bb1 = split_edge (entry);
1168 basic_block bb0 = single_pred (bb1);
1169 htab_t name_copies = htab_create (10, name_to_copy_elt_hash,
1170 name_to_copy_elt_eq, free);
1171 htab_t decl_copies = htab_create (10, int_tree_map_hash, int_tree_map_eq,
1174 tree type, type_name, nvar;
1175 gimple_stmt_iterator gsi;
1176 struct clsn_data clsn_data;
1177 VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
1179 basic_block entry_bb = bb1;
1180 basic_block exit_bb = exit->dest;
1182 entry = single_succ_edge (entry_bb);
1183 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
1185 for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
1187 if (bb != entry_bb && bb != exit_bb)
1189 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1190 separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
1191 name_copies, decl_copies);
1193 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1194 separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
1195 name_copies, decl_copies);
1199 VEC_free (basic_block, heap, body);
1201 if (htab_elements (name_copies) == 0 && reduction_list == 0)
1203 /* It may happen that there is nothing to copy (if there are only
1204 loop carried and external variables in the loop). */
1206 *new_arg_struct = NULL;
1210 /* Create the type for the structure to store the ssa names to. */
1211 type = lang_hooks.types.make_type (RECORD_TYPE);
1212 type_name = build_decl (BUILTINS_LOCATION,
1213 TYPE_DECL, create_tmp_var_name (".paral_data"),
1215 TYPE_NAME (type) = type_name;
1217 htab_traverse (name_copies, add_field_for_name, type);
1218 if (reduction_list && htab_elements (reduction_list) > 0)
1220 /* Create the fields for reductions. */
1221 htab_traverse (reduction_list, add_field_for_reduction,
1226 /* Create the loads and stores. */
1227 *arg_struct = create_tmp_var (type, ".paral_data_store");
1228 add_referenced_var (*arg_struct);
1229 nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load");
1230 add_referenced_var (nvar);
1231 *new_arg_struct = make_ssa_name (nvar, NULL);
1233 ld_st_data->store = *arg_struct;
1234 ld_st_data->load = *new_arg_struct;
1235 ld_st_data->store_bb = bb0;
1236 ld_st_data->load_bb = bb1;
1238 htab_traverse (name_copies, create_loads_and_stores_for_name,
1241 /* Load the calculation from memory (after the join of the threads). */
1243 if (reduction_list && htab_elements (reduction_list) > 0)
1245 htab_traverse (reduction_list, create_stores_for_reduction,
1247 clsn_data.load = make_ssa_name (nvar, NULL);
1248 clsn_data.load_bb = exit->dest;
1249 clsn_data.store = ld_st_data->store;
1250 create_final_loads_for_reduction (reduction_list, &clsn_data);
1254 htab_delete (decl_copies);
1255 htab_delete (name_copies);
1258 /* Bitmap containing uids of functions created by parallelization. We cannot
1259 allocate it from the default obstack, as it must live across compilation
1260 of several functions; we make it gc allocated instead. */
1262 static GTY(()) bitmap parallelized_functions;
1264 /* Returns true if FN was created by create_loop_fn. */
1267 parallelized_function_p (tree fn)
1269 if (!parallelized_functions || !DECL_ARTIFICIAL (fn))
1272 return bitmap_bit_p (parallelized_functions, DECL_UID (fn));
1275 /* Creates and returns an empty function that will receive the body of
1276 a parallelized loop. */
1279 create_loop_fn (void)
1283 tree decl, type, name, t;
1284 struct function *act_cfun = cfun;
1285 static unsigned loopfn_num;
1287 snprintf (buf, 100, "%s.$loopfn", current_function_name ());
1288 ASM_FORMAT_PRIVATE_NAME (tname, buf, loopfn_num++);
1289 clean_symbol_name (tname);
1290 name = get_identifier (tname);
1291 type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
1293 decl = build_decl (BUILTINS_LOCATION,
1294 FUNCTION_DECL, name, type);
1295 if (!parallelized_functions)
1296 parallelized_functions = BITMAP_GGC_ALLOC ();
1297 bitmap_set_bit (parallelized_functions, DECL_UID (decl));
1299 TREE_STATIC (decl) = 1;
1300 TREE_USED (decl) = 1;
1301 DECL_ARTIFICIAL (decl) = 1;
1302 DECL_IGNORED_P (decl) = 0;
1303 TREE_PUBLIC (decl) = 0;
1304 DECL_UNINLINABLE (decl) = 1;
1305 DECL_EXTERNAL (decl) = 0;
1306 DECL_CONTEXT (decl) = NULL_TREE;
1307 DECL_INITIAL (decl) = make_node (BLOCK);
1309 t = build_decl (BUILTINS_LOCATION,
1310 RESULT_DECL, NULL_TREE, void_type_node);
1311 DECL_ARTIFICIAL (t) = 1;
1312 DECL_IGNORED_P (t) = 1;
1313 DECL_RESULT (decl) = t;
1315 t = build_decl (BUILTINS_LOCATION,
1316 PARM_DECL, get_identifier (".paral_data_param"),
1318 DECL_ARTIFICIAL (t) = 1;
1319 DECL_ARG_TYPE (t) = ptr_type_node;
1320 DECL_CONTEXT (t) = decl;
1322 DECL_ARGUMENTS (decl) = t;
1324 allocate_struct_function (decl, false);
1326 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1328 set_cfun (act_cfun);
1333 /* Bases all the induction variables in LOOP on a single induction
1334 variable (unsigned with base 0 and step 1), whose final value is
1335 compared with *NIT. When the IV type precision has to be larger
1336 than *NIT type precision, *NIT is converted to the larger type, the
1337 conversion code is inserted before the loop, and *NIT is updated to
1338 the new definition. The induction variable is incremented in the
1339 loop latch. REDUCTION_LIST describes the reductions in LOOP.
1340 Return the induction variable that was created. */
1343 canonicalize_loop_ivs (struct loop *loop, htab_t reduction_list, tree *nit)
1345 unsigned precision = TYPE_PRECISION (TREE_TYPE (*nit));
1346 unsigned original_precision = precision;
1347 tree res, type, var_before, val, atype, mtype;
1348 gimple_stmt_iterator gsi, psi;
1352 edge exit = single_dom_exit (loop);
1353 struct reduction_info *red;
1356 for (psi = gsi_start_phis (loop->header);
1357 !gsi_end_p (psi); gsi_next (&psi))
1359 phi = gsi_stmt (psi);
1360 res = PHI_RESULT (phi);
1362 if (is_gimple_reg (res) && TYPE_PRECISION (TREE_TYPE (res)) > precision)
1363 precision = TYPE_PRECISION (TREE_TYPE (res));
1366 type = lang_hooks.types.type_for_size (precision, 1);
1368 if (original_precision != precision)
1370 *nit = fold_convert (type, *nit);
1371 *nit = force_gimple_operand (*nit, &stmts, true, NULL_TREE);
1373 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1376 gsi = gsi_last_bb (loop->latch);
1377 create_iv (build_int_cst_type (type, 0), build_int_cst (type, 1), NULL_TREE,
1378 loop, &gsi, true, &var_before, NULL);
1380 gsi = gsi_after_labels (loop->header);
1381 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); )
1383 phi = gsi_stmt (psi);
1384 res = PHI_RESULT (phi);
1386 if (!is_gimple_reg (res) || res == var_before)
1392 ok = simple_iv (loop, loop, res, &iv, true);
1395 red = reduction_phi (reduction_list, phi);
1399 /* We preserve the reduction phi nodes. */
1407 remove_phi_node (&psi, false);
1409 atype = TREE_TYPE (res);
1410 mtype = POINTER_TYPE_P (atype) ? sizetype : atype;
1411 val = fold_build2 (MULT_EXPR, mtype, unshare_expr (iv.step),
1412 fold_convert (mtype, var_before));
1413 val = fold_build2 (POINTER_TYPE_P (atype)
1414 ? POINTER_PLUS_EXPR : PLUS_EXPR,
1415 atype, unshare_expr (iv.base), val);
1416 val = force_gimple_operand_gsi (&gsi, val, false, NULL_TREE, true,
1418 stmt = gimple_build_assign (res, val);
1419 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1420 SSA_NAME_DEF_STMT (res) = stmt;
1423 stmt = last_stmt (exit->src);
1424 /* Make the loop exit if the control condition is not satisfied. */
1425 if (exit->flags & EDGE_TRUE_VALUE)
1429 extract_true_false_edges_from_block (exit->src, &te, &fe);
1430 te->flags = EDGE_FALSE_VALUE;
1431 fe->flags = EDGE_TRUE_VALUE;
1433 gimple_cond_set_code (stmt, LT_EXPR);
1434 gimple_cond_set_lhs (stmt, var_before);
1435 gimple_cond_set_rhs (stmt, *nit);
1441 /* Moves the exit condition of LOOP to the beginning of its header, and
1442 duplicates the part of the last iteration that gets disabled to the
1443 exit of the loop. NIT is the number of iterations of the loop
1444 (used to initialize the variables in the duplicated part).
1446 TODO: the common case is that latch of the loop is empty and immediately
1447 follows the loop exit. In this case, it would be better not to copy the
1448 body of the loop, but only move the entry of the loop directly before the
1449 exit check and increase the number of iterations of the loop by one.
1450 This may need some additional preconditioning in case NIT = ~0.
1451 REDUCTION_LIST describes the reductions in LOOP. */
1454 transform_to_exit_first_loop (struct loop *loop, htab_t reduction_list, tree nit)
1456 basic_block *bbs, *nbbs, ex_bb, orig_header;
1459 edge exit = single_dom_exit (loop), hpred;
1460 tree control, control_name, res, t;
1461 gimple phi, nphi, cond_stmt, stmt;
1462 gimple_stmt_iterator gsi;
1464 split_block_after_labels (loop->header);
1465 orig_header = single_succ (loop->header);
1466 hpred = single_succ_edge (loop->header);
1468 cond_stmt = last_stmt (exit->src);
1469 control = gimple_cond_lhs (cond_stmt);
1470 gcc_assert (gimple_cond_rhs (cond_stmt) == nit);
1472 /* Make sure that we have phi nodes on exit for all loop header phis
1473 (create_parallel_loop requires that). */
1474 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1476 phi = gsi_stmt (gsi);
1477 res = PHI_RESULT (phi);
1478 t = make_ssa_name (SSA_NAME_VAR (res), phi);
1479 SET_PHI_RESULT (phi, t);
1481 nphi = create_phi_node (res, orig_header);
1482 SSA_NAME_DEF_STMT (res) = nphi;
1483 add_phi_arg (nphi, t, hpred);
1487 gimple_cond_set_lhs (cond_stmt, t);
1488 update_stmt (cond_stmt);
1493 bbs = get_loop_body_in_dom_order (loop);
1494 for (n = 0; bbs[n] != exit->src; n++)
1496 nbbs = XNEWVEC (basic_block, n);
1497 ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
1504 /* Other than reductions, the only gimple reg that should be copied
1505 out of the loop is the control variable. */
1507 control_name = NULL_TREE;
1508 for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); )
1510 phi = gsi_stmt (gsi);
1511 res = PHI_RESULT (phi);
1512 if (!is_gimple_reg (res))
1518 /* Check if it is a part of reduction. If it is,
1519 keep the phi at the reduction's keep_res field. The
1520 PHI_RESULT of this phi is the resulting value of the reduction
1521 variable when exiting the loop. */
1523 exit = single_dom_exit (loop);
1525 if (htab_elements (reduction_list) > 0)
1527 struct reduction_info *red;
1529 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1531 red = reduction_phi (reduction_list, SSA_NAME_DEF_STMT (val));
1534 red->keep_res = phi;
1539 gcc_assert (control_name == NULL_TREE
1540 && SSA_NAME_VAR (res) == SSA_NAME_VAR (control));
1542 remove_phi_node (&gsi, false);
1544 gcc_assert (control_name != NULL_TREE);
1546 /* Initialize the control variable to NIT. */
1547 gsi = gsi_after_labels (ex_bb);
1548 nit = force_gimple_operand_gsi (&gsi,
1549 fold_convert (TREE_TYPE (control_name), nit),
1550 false, NULL_TREE, false, GSI_SAME_STMT);
1551 stmt = gimple_build_assign (control_name, nit);
1552 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1553 SSA_NAME_DEF_STMT (control_name) = stmt;
1556 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
1557 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
1558 NEW_DATA is the variable that should be initialized from the argument
1559 of LOOP_FN. N_THREADS is the requested number of threads. Returns the
1560 basic block containing GIMPLE_OMP_PARALLEL tree. */
1563 create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
1564 tree new_data, unsigned n_threads)
1566 gimple_stmt_iterator gsi;
1567 basic_block bb, paral_bb, for_bb, ex_bb;
1569 gimple stmt, for_stmt, phi, cond_stmt;
1570 tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
1571 edge exit, nexit, guard, end, e;
1573 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
1574 bb = loop_preheader_edge (loop)->src;
1575 paral_bb = single_pred (bb);
1576 gsi = gsi_last_bb (paral_bb);
1578 t = build_omp_clause (BUILTINS_LOCATION, OMP_CLAUSE_NUM_THREADS);
1579 OMP_CLAUSE_NUM_THREADS_EXPR (t)
1580 = build_int_cst (integer_type_node, n_threads);
1581 stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
1583 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1585 /* Initialize NEW_DATA. */
1588 gsi = gsi_after_labels (bb);
1590 param = make_ssa_name (DECL_ARGUMENTS (loop_fn), NULL);
1591 stmt = gimple_build_assign (param, build_fold_addr_expr (data));
1592 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1593 SSA_NAME_DEF_STMT (param) = stmt;
1595 stmt = gimple_build_assign (new_data,
1596 fold_convert (TREE_TYPE (new_data), param));
1597 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1598 SSA_NAME_DEF_STMT (new_data) = stmt;
1601 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
1602 bb = split_loop_exit_edge (single_dom_exit (loop));
1603 gsi = gsi_last_bb (bb);
1604 gsi_insert_after (&gsi, gimple_build_omp_return (false), GSI_NEW_STMT);
1606 /* Extract data for GIMPLE_OMP_FOR. */
1607 gcc_assert (loop->header == single_dom_exit (loop)->src);
1608 cond_stmt = last_stmt (loop->header);
1610 cvar = gimple_cond_lhs (cond_stmt);
1611 cvar_base = SSA_NAME_VAR (cvar);
1612 phi = SSA_NAME_DEF_STMT (cvar);
1613 cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1614 initvar = make_ssa_name (cvar_base, NULL);
1615 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
1617 cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1619 gsi = gsi_last_bb (loop->latch);
1620 gcc_assert (gsi_stmt (gsi) == SSA_NAME_DEF_STMT (cvar_next));
1621 gsi_remove (&gsi, true);
1624 for_bb = split_edge (loop_preheader_edge (loop));
1625 ex_bb = split_loop_exit_edge (single_dom_exit (loop));
1626 extract_true_false_edges_from_block (loop->header, &nexit, &exit);
1627 gcc_assert (exit == single_dom_exit (loop));
1629 guard = make_edge (for_bb, ex_bb, 0);
1630 single_succ_edge (loop->latch)->flags = 0;
1631 end = make_edge (loop->latch, ex_bb, EDGE_FALLTHRU);
1632 for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); gsi_next (&gsi))
1634 phi = gsi_stmt (gsi);
1635 res = PHI_RESULT (phi);
1636 stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi, exit));
1638 PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop)),
1640 add_phi_arg (phi, PHI_ARG_DEF_FROM_EDGE (stmt, loop_latch_edge (loop)),
1643 e = redirect_edge_and_branch (exit, nexit->dest);
1644 PENDING_STMT (e) = NULL;
1646 /* Emit GIMPLE_OMP_FOR. */
1647 gimple_cond_set_lhs (cond_stmt, cvar_base);
1648 type = TREE_TYPE (cvar);
1649 t = build_omp_clause (BUILTINS_LOCATION, OMP_CLAUSE_SCHEDULE);
1650 OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
1652 for_stmt = gimple_build_omp_for (NULL, t, 1, NULL);
1653 gimple_omp_for_set_index (for_stmt, 0, initvar);
1654 gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
1655 gimple_omp_for_set_final (for_stmt, 0, gimple_cond_rhs (cond_stmt));
1656 gimple_omp_for_set_cond (for_stmt, 0, gimple_cond_code (cond_stmt));
1657 gimple_omp_for_set_incr (for_stmt, 0, build2 (PLUS_EXPR, type,
1659 build_int_cst (type, 1)));
1661 gsi = gsi_last_bb (for_bb);
1662 gsi_insert_after (&gsi, for_stmt, GSI_NEW_STMT);
1663 SSA_NAME_DEF_STMT (initvar) = for_stmt;
1665 /* Emit GIMPLE_OMP_CONTINUE. */
1666 gsi = gsi_last_bb (loop->latch);
1667 stmt = gimple_build_omp_continue (cvar_next, cvar);
1668 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1669 SSA_NAME_DEF_STMT (cvar_next) = stmt;
1671 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
1672 gsi = gsi_last_bb (ex_bb);
1673 gsi_insert_after (&gsi, gimple_build_omp_return (true), GSI_NEW_STMT);
1678 /* Generates code to execute the iterations of LOOP in N_THREADS threads in
1679 parallel. NITER describes number of iterations of LOOP.
1680 REDUCTION_LIST describes the reductions existent in the LOOP. */
1683 gen_parallel_loop (struct loop *loop, htab_t reduction_list,
1684 unsigned n_threads, struct tree_niter_desc *niter)
1688 tree many_iterations_cond, type, nit;
1689 tree arg_struct, new_arg_struct;
1691 basic_block parallel_head;
1693 struct clsn_data clsn_data;
1698 ---------------------------------------------------------------------
1701 IV = phi (INIT, IV + STEP)
1707 ---------------------------------------------------------------------
1709 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
1710 we generate the following code:
1712 ---------------------------------------------------------------------
1715 || NITER < MIN_PER_THREAD * N_THREADS)
1719 store all local loop-invariant variables used in body of the loop to DATA.
1720 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
1721 load the variables from DATA.
1722 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
1725 GIMPLE_OMP_CONTINUE;
1726 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
1727 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
1733 IV = phi (INIT, IV + STEP)
1744 /* Create two versions of the loop -- in the old one, we know that the
1745 number of iterations is large enough, and we will transform it into the
1746 loop that will be split to loop_fn, the new one will be used for the
1747 remaining iterations. */
1749 type = TREE_TYPE (niter->niter);
1750 nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true,
1753 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1755 many_iterations_cond =
1756 fold_build2 (GE_EXPR, boolean_type_node,
1757 nit, build_int_cst (type, MIN_PER_THREAD * n_threads));
1758 many_iterations_cond
1759 = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1760 invert_truthvalue (unshare_expr (niter->may_be_zero)),
1761 many_iterations_cond);
1762 many_iterations_cond
1763 = force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
1765 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1766 if (!is_gimple_condexpr (many_iterations_cond))
1768 many_iterations_cond
1769 = force_gimple_operand (many_iterations_cond, &stmts,
1772 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1775 initialize_original_copy_tables ();
1777 /* We assume that the loop usually iterates a lot. */
1778 prob = 4 * REG_BR_PROB_BASE / 5;
1779 nloop = loop_version (loop, many_iterations_cond, NULL,
1780 prob, prob, REG_BR_PROB_BASE - prob, true);
1781 update_ssa (TODO_update_ssa);
1782 free_original_copy_tables ();
1784 /* Base all the induction variables in LOOP on a single control one. */
1785 canonicalize_loop_ivs (loop, reduction_list, &nit);
1787 /* Ensure that the exit condition is the first statement in the loop. */
1788 transform_to_exit_first_loop (loop, reduction_list, nit);
1790 /* Generate initializations for reductions. */
1791 if (htab_elements (reduction_list) > 0)
1792 htab_traverse (reduction_list, initialize_reductions, loop);
1794 /* Eliminate the references to local variables from the loop. */
1795 gcc_assert (single_exit (loop));
1796 entry = loop_preheader_edge (loop);
1797 exit = single_dom_exit (loop);
1799 eliminate_local_variables (entry, exit);
1800 /* In the old loop, move all variables non-local to the loop to a structure
1801 and back, and create separate decls for the variables used in loop. */
1802 separate_decls_in_region (entry, exit, reduction_list, &arg_struct,
1803 &new_arg_struct, &clsn_data);
1805 /* Create the parallel constructs. */
1806 parallel_head = create_parallel_loop (loop, create_loop_fn (), arg_struct,
1807 new_arg_struct, n_threads);
1808 if (htab_elements (reduction_list) > 0)
1809 create_call_for_reduction (loop, reduction_list, &clsn_data);
1813 /* Cancel the loop (it is simpler to do it here rather than to teach the
1814 expander to do it). */
1815 cancel_loop_tree (loop);
1817 /* Free loop bound estimations that could contain references to
1818 removed statements. */
1819 FOR_EACH_LOOP (li, loop, 0)
1820 free_numbers_of_iterations_estimates_loop (loop);
1822 /* Expand the parallel constructs. We do it directly here instead of running
1823 a separate expand_omp pass, since it is more efficient, and less likely to
1824 cause troubles with further analyses not being able to deal with the
1827 omp_expand_local (parallel_head);
1830 /* Returns true when LOOP contains vector phi nodes. */
1833 loop_has_vector_phi_nodes (struct loop *loop ATTRIBUTE_UNUSED)
1836 basic_block *bbs = get_loop_body_in_dom_order (loop);
1837 gimple_stmt_iterator gsi;
1840 for (i = 0; i < loop->num_nodes; i++)
1841 for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
1842 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi_stmt (gsi)))) == VECTOR_TYPE)
1851 /* Detect parallel loops and generate parallel code using libgomp
1852 primitives. Returns true if some loop was parallelized, false
1856 parallelize_loops (void)
1858 unsigned n_threads = flag_tree_parallelize_loops;
1859 bool changed = false;
1861 struct tree_niter_desc niter_desc;
1863 htab_t reduction_list;
1865 /* Do not parallelize loops in the functions created by parallelization. */
1866 if (parallelized_function_p (cfun->decl))
1869 reduction_list = htab_create (10, reduction_info_hash,
1870 reduction_info_eq, free);
1871 init_stmt_vec_info_vec ();
1873 FOR_EACH_LOOP (li, loop, 0)
1875 htab_empty (reduction_list);
1876 if (/* Do not bother with loops in cold areas. */
1877 optimize_loop_nest_for_size_p (loop)
1878 /* Or loops that roll too little. */
1879 || expected_loop_iterations (loop) <= n_threads
1880 /* And of course, the loop must be parallelizable. */
1881 || !can_duplicate_loop_p (loop)
1882 || loop_has_blocks_with_irreducible_flag (loop)
1883 /* FIXME: the check for vector phi nodes could be removed. */
1884 || loop_has_vector_phi_nodes (loop)
1885 || !loop_parallel_p (loop, reduction_list, &niter_desc))
1889 gen_parallel_loop (loop, reduction_list, n_threads, &niter_desc);
1890 verify_flow_info ();
1891 verify_dominators (CDI_DOMINATORS);
1892 verify_loop_structure ();
1893 verify_loop_closed_ssa ();
1896 free_stmt_vec_info_vec ();
1897 htab_delete (reduction_list);
1899 /* Parallelization will cause new function calls to be inserted through
1900 which local variables will escape. Reset the points-to solutions
1901 for ESCAPED and CALLUSED. */
1904 pt_solution_reset (&cfun->gimple_df->escaped);
1905 pt_solution_reset (&cfun->gimple_df->callused);
1911 #include "gt-tree-parloops.h"