1 /* Loop autoparallelization.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Sebastian Pop <pop@cri.ensmp.fr> and
5 Zdenek Dvorak <dvorakz@suse.cz>.
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
28 #include "tree-flow.h"
30 #include "tree-data-ref.h"
31 #include "tree-pretty-print.h"
32 #include "gimple-pretty-print.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_force_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 unsigned reduc_version; /* SSA_NAME_VERSION of original reduc_phi
173 gimple keep_res; /* The PHI_RESULT of this phi is the resulting value
174 of the reduction variable when existing the loop. */
175 tree initial_value; /* The initial value of the reduction var before entering the loop. */
176 tree field; /* the name of the field in the parloop data structure intended for reduction. */
177 tree init; /* reduction initialization value. */
178 gimple new_phi; /* (helper field) Newly created phi node whose result
179 will be passed to the atomic operation. Represents
180 the local result each thread computed for the reduction
184 /* Equality and hash functions for hashtab code. */
187 reduction_info_eq (const void *aa, const void *bb)
189 const struct reduction_info *a = (const struct reduction_info *) aa;
190 const struct reduction_info *b = (const struct reduction_info *) bb;
192 return (a->reduc_phi == b->reduc_phi);
196 reduction_info_hash (const void *aa)
198 const struct reduction_info *a = (const struct reduction_info *) aa;
200 return a->reduc_version;
203 static struct reduction_info *
204 reduction_phi (htab_t reduction_list, gimple phi)
206 struct reduction_info tmpred, *red;
208 if (htab_elements (reduction_list) == 0)
211 tmpred.reduc_phi = phi;
212 tmpred.reduc_version = gimple_uid (phi);
213 red = (struct reduction_info *) htab_find (reduction_list, &tmpred);
218 /* Element of hashtable of names to copy. */
220 struct name_to_copy_elt
222 unsigned version; /* The version of the name to copy. */
223 tree new_name; /* The new name used in the copy. */
224 tree field; /* The field of the structure used to pass the
228 /* Equality and hash functions for hashtab code. */
231 name_to_copy_elt_eq (const void *aa, const void *bb)
233 const struct name_to_copy_elt *a = (const struct name_to_copy_elt *) aa;
234 const struct name_to_copy_elt *b = (const struct name_to_copy_elt *) bb;
236 return a->version == b->version;
240 name_to_copy_elt_hash (const void *aa)
242 const struct name_to_copy_elt *a = (const struct name_to_copy_elt *) aa;
244 return (hashval_t) a->version;
248 /* Data dependency analysis. Returns true if the iterations of LOOP
249 are independent on each other (that is, if we can execute them
253 loop_parallel_p (struct loop *loop, struct obstack * parloop_obstack)
255 VEC (loop_p, heap) *loop_nest;
256 VEC (ddr_p, heap) *dependence_relations;
257 VEC (data_reference_p, heap) *datarefs;
258 lambda_trans_matrix trans;
261 if (dump_file && (dump_flags & TDF_DETAILS))
263 fprintf (dump_file, "Considering loop %d\n", loop->num);
265 fprintf (dump_file, "loop is innermost\n");
267 fprintf (dump_file, "loop NOT innermost\n");
270 /* Check for problems with dependences. If the loop can be reversed,
271 the iterations are independent. */
272 datarefs = VEC_alloc (data_reference_p, heap, 10);
273 dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
274 loop_nest = VEC_alloc (loop_p, heap, 3);
275 compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs,
276 &dependence_relations);
277 if (dump_file && (dump_flags & TDF_DETAILS))
278 dump_data_dependence_relations (dump_file, dependence_relations);
280 trans = lambda_trans_matrix_new (1, 1, parloop_obstack);
281 LTM_MATRIX (trans)[0][0] = -1;
283 if (lambda_transform_legal_p (trans, 1, dependence_relations))
286 if (dump_file && (dump_flags & TDF_DETAILS))
287 fprintf (dump_file, " SUCCESS: may be parallelized\n");
289 else if (dump_file && (dump_flags & TDF_DETAILS))
291 " FAILED: data dependencies exist across iterations\n");
293 VEC_free (loop_p, heap, loop_nest);
294 free_dependence_relations (dependence_relations);
295 free_data_refs (datarefs);
300 /* Return true when LOOP contains basic blocks marked with the
301 BB_IRREDUCIBLE_LOOP flag. */
304 loop_has_blocks_with_irreducible_flag (struct loop *loop)
307 basic_block *bbs = get_loop_body_in_dom_order (loop);
310 for (i = 0; i < loop->num_nodes; i++)
311 if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
320 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
321 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
322 to their addresses that can be reused. The address of OBJ is known to
323 be invariant in the whole function. Other needed statements are placed
327 take_address_of (tree obj, tree type, edge entry, htab_t decl_address,
328 gimple_stmt_iterator *gsi)
332 struct int_tree_map ielt, *nielt;
333 tree *var_p, name, bvar, addr;
337 /* Since the address of OBJ is invariant, the trees may be shared.
338 Avoid rewriting unrelated parts of the code. */
339 obj = unshare_expr (obj);
341 handled_component_p (*var_p);
342 var_p = &TREE_OPERAND (*var_p, 0))
345 /* Canonicalize the access to base on a MEM_REF. */
347 *var_p = build_simple_mem_ref (build_fold_addr_expr (*var_p));
349 /* Assign a canonical SSA name to the address of the base decl used
350 in the address and share it for all accesses and addresses based
352 uid = DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));
354 dslot = htab_find_slot_with_hash (decl_address, &ielt, uid, INSERT);
359 addr = TREE_OPERAND (*var_p, 0);
360 bvar = create_tmp_var (TREE_TYPE (addr),
361 get_name (TREE_OPERAND
362 (TREE_OPERAND (*var_p, 0), 0)));
363 add_referenced_var (bvar);
364 stmt = gimple_build_assign (bvar, addr);
365 name = make_ssa_name (bvar, stmt);
366 gimple_assign_set_lhs (stmt, name);
367 gsi_insert_on_edge_immediate (entry, stmt);
369 nielt = XNEW (struct int_tree_map);
375 name = ((struct int_tree_map *) *dslot)->to;
377 /* Express the address in terms of the canonical SSA name. */
378 TREE_OPERAND (*var_p, 0) = name;
380 return build_fold_addr_expr_with_type (obj, type);
382 name = force_gimple_operand (build_addr (obj, current_function_decl),
383 &stmts, true, NULL_TREE);
384 if (!gimple_seq_empty_p (stmts))
385 gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
387 if (!useless_type_conversion_p (type, TREE_TYPE (name)))
389 name = force_gimple_operand (fold_convert (type, name), &stmts, true,
391 if (!gimple_seq_empty_p (stmts))
392 gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
398 /* Callback for htab_traverse. Create the initialization statement
399 for reduction described in SLOT, and place it at the preheader of
400 the loop described in DATA. */
403 initialize_reductions (void **slot, void *data)
406 tree bvar, type, arg;
409 struct reduction_info *const reduc = (struct reduction_info *) *slot;
410 struct loop *loop = (struct loop *) data;
412 /* Create initialization in preheader:
413 reduction_variable = initialization value of reduction. */
415 /* In the phi node at the header, replace the argument coming
416 from the preheader with the reduction initialization value. */
418 /* Create a new variable to initialize the reduction. */
419 type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
420 bvar = create_tmp_var (type, "reduction");
421 add_referenced_var (bvar);
423 c = build_omp_clause (gimple_location (reduc->reduc_stmt),
424 OMP_CLAUSE_REDUCTION);
425 OMP_CLAUSE_REDUCTION_CODE (c) = reduc->reduction_code;
426 OMP_CLAUSE_DECL (c) = SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt));
428 init = omp_reduction_init (c, TREE_TYPE (bvar));
431 /* Replace the argument representing the initialization value
432 with the initialization value for the reduction (neutral
433 element for the particular operation, e.g. 0 for PLUS_EXPR,
434 1 for MULT_EXPR, etc).
435 Keep the old value in a new variable "reduction_initial",
436 that will be taken in consideration after the parallel
437 computing is done. */
439 e = loop_preheader_edge (loop);
440 arg = PHI_ARG_DEF_FROM_EDGE (reduc->reduc_phi, e);
441 /* Create new variable to hold the initial value. */
443 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
444 (reduc->reduc_phi, loop_preheader_edge (loop)), init);
445 reduc->initial_value = arg;
451 struct walk_stmt_info info;
454 gimple_stmt_iterator *gsi;
459 /* Eliminates references to local variables in *TP out of the single
460 entry single exit region starting at DTA->ENTRY.
461 DECL_ADDRESS contains addresses of the references that had their
462 address taken already. If the expression is changed, CHANGED is
463 set to true. Callback for walk_tree. */
466 eliminate_local_variables_1 (tree *tp, int *walk_subtrees, void *data)
468 struct elv_data *const dta = (struct elv_data *) data;
469 tree t = *tp, var, addr, addr_type, type, obj;
475 if (!SSA_VAR_P (t) || DECL_EXTERNAL (t))
478 type = TREE_TYPE (t);
479 addr_type = build_pointer_type (type);
480 addr = take_address_of (t, addr_type, dta->entry, dta->decl_address,
482 if (dta->gsi == NULL && addr == NULL_TREE)
488 *tp = build_simple_mem_ref (addr);
494 if (TREE_CODE (t) == ADDR_EXPR)
496 /* ADDR_EXPR may appear in two contexts:
497 -- as a gimple operand, when the address taken is a function invariant
498 -- as gimple rhs, when the resulting address in not a function
500 We do not need to do anything special in the latter case (the base of
501 the memory reference whose address is taken may be replaced in the
502 DECL_P case). The former case is more complicated, as we need to
503 ensure that the new address is still a gimple operand. Thus, it
504 is not sufficient to replace just the base of the memory reference --
505 we need to move the whole computation of the address out of the
507 if (!is_gimple_val (t))
511 obj = TREE_OPERAND (t, 0);
512 var = get_base_address (obj);
513 if (!var || !SSA_VAR_P (var) || DECL_EXTERNAL (var))
516 addr_type = TREE_TYPE (t);
517 addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address,
519 if (dta->gsi == NULL && addr == NULL_TREE)
536 /* Moves the references to local variables in STMT at *GSI out of the single
537 entry single exit region starting at ENTRY. DECL_ADDRESS contains
538 addresses of the references that had their address taken
542 eliminate_local_variables_stmt (edge entry, gimple_stmt_iterator *gsi,
546 gimple stmt = gsi_stmt (*gsi);
548 memset (&dta.info, '\0', sizeof (dta.info));
550 dta.decl_address = decl_address;
554 if (gimple_debug_bind_p (stmt))
557 walk_tree (gimple_debug_bind_get_value_ptr (stmt),
558 eliminate_local_variables_1, &dta.info, NULL);
561 gimple_debug_bind_reset_value (stmt);
568 walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
575 /* Eliminates the references to local variables from the single entry
576 single exit region between the ENTRY and EXIT edges.
579 1) Taking address of a local variable -- these are moved out of the
580 region (and temporary variable is created to hold the address if
583 2) Dereferencing a local variable -- these are replaced with indirect
587 eliminate_local_variables (edge entry, edge exit)
590 VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
592 gimple_stmt_iterator gsi;
593 bool has_debug_stmt = false;
594 htab_t decl_address = htab_create (10, int_tree_map_hash, int_tree_map_eq,
596 basic_block entry_bb = entry->src;
597 basic_block exit_bb = exit->dest;
599 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
601 FOR_EACH_VEC_ELT (basic_block, body, i, bb)
602 if (bb != entry_bb && bb != exit_bb)
603 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
604 if (gimple_debug_bind_p (gsi_stmt (gsi)))
605 has_debug_stmt = true;
607 eliminate_local_variables_stmt (entry, &gsi, decl_address);
610 FOR_EACH_VEC_ELT (basic_block, body, i, bb)
611 if (bb != entry_bb && bb != exit_bb)
612 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
613 if (gimple_debug_bind_p (gsi_stmt (gsi)))
614 eliminate_local_variables_stmt (entry, &gsi, decl_address);
616 htab_delete (decl_address);
617 VEC_free (basic_block, heap, body);
620 /* Returns true if expression EXPR is not defined between ENTRY and
621 EXIT, i.e. if all its operands are defined outside of the region. */
624 expr_invariant_in_region_p (edge entry, edge exit, tree expr)
626 basic_block entry_bb = entry->src;
627 basic_block exit_bb = exit->dest;
630 if (is_gimple_min_invariant (expr))
633 if (TREE_CODE (expr) == SSA_NAME)
635 def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
637 && dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)
638 && !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))
647 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
648 The copies are stored to NAME_COPIES, if NAME was already duplicated,
649 its duplicate stored in NAME_COPIES is returned.
651 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
652 duplicated, storing the copies in DECL_COPIES. */
655 separate_decls_in_region_name (tree name,
656 htab_t name_copies, htab_t decl_copies,
659 tree copy, var, var_copy;
660 unsigned idx, uid, nuid;
661 struct int_tree_map ielt, *nielt;
662 struct name_to_copy_elt elt, *nelt;
663 void **slot, **dslot;
665 if (TREE_CODE (name) != SSA_NAME)
668 idx = SSA_NAME_VERSION (name);
670 slot = htab_find_slot_with_hash (name_copies, &elt, idx,
671 copy_name_p ? INSERT : NO_INSERT);
673 return ((struct name_to_copy_elt *) *slot)->new_name;
675 var = SSA_NAME_VAR (name);
676 uid = DECL_UID (var);
678 dslot = htab_find_slot_with_hash (decl_copies, &ielt, uid, INSERT);
681 var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
682 DECL_GIMPLE_REG_P (var_copy) = DECL_GIMPLE_REG_P (var);
683 add_referenced_var (var_copy);
684 nielt = XNEW (struct int_tree_map);
686 nielt->to = var_copy;
689 /* Ensure that when we meet this decl next time, we won't duplicate
691 nuid = DECL_UID (var_copy);
693 dslot = htab_find_slot_with_hash (decl_copies, &ielt, nuid, INSERT);
694 gcc_assert (!*dslot);
695 nielt = XNEW (struct int_tree_map);
697 nielt->to = var_copy;
701 var_copy = ((struct int_tree_map *) *dslot)->to;
705 copy = duplicate_ssa_name (name, NULL);
706 nelt = XNEW (struct name_to_copy_elt);
708 nelt->new_name = copy;
709 nelt->field = NULL_TREE;
718 SSA_NAME_VAR (copy) = var_copy;
722 /* Finds the ssa names used in STMT that are defined outside the
723 region between ENTRY and EXIT and replaces such ssa names with
724 their duplicates. The duplicates are stored to NAME_COPIES. Base
725 decls of all ssa names used in STMT (including those defined in
726 LOOP) are replaced with the new temporary variables; the
727 replacement decls are stored in DECL_COPIES. */
730 separate_decls_in_region_stmt (edge entry, edge exit, gimple stmt,
731 htab_t name_copies, htab_t decl_copies)
739 mark_virtual_ops_for_renaming (stmt);
741 FOR_EACH_PHI_OR_STMT_DEF (def, stmt, oi, SSA_OP_DEF)
743 name = DEF_FROM_PTR (def);
744 gcc_assert (TREE_CODE (name) == SSA_NAME);
745 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
747 gcc_assert (copy == name);
750 FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
752 name = USE_FROM_PTR (use);
753 if (TREE_CODE (name) != SSA_NAME)
756 copy_name_p = expr_invariant_in_region_p (entry, exit, name);
757 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
763 /* Finds the ssa names used in STMT that are defined outside the
764 region between ENTRY and EXIT and replaces such ssa names with
765 their duplicates. The duplicates are stored to NAME_COPIES. Base
766 decls of all ssa names used in STMT (including those defined in
767 LOOP) are replaced with the new temporary variables; the
768 replacement decls are stored in DECL_COPIES. */
771 separate_decls_in_region_debug_bind (gimple stmt,
772 htab_t name_copies, htab_t decl_copies)
777 struct int_tree_map ielt;
778 struct name_to_copy_elt elt;
779 void **slot, **dslot;
781 var = gimple_debug_bind_get_var (stmt);
782 if (TREE_CODE (var) == DEBUG_EXPR_DECL)
784 gcc_assert (DECL_P (var) && SSA_VAR_P (var));
785 ielt.uid = DECL_UID (var);
786 dslot = htab_find_slot_with_hash (decl_copies, &ielt, ielt.uid, NO_INSERT);
789 gimple_debug_bind_set_var (stmt, ((struct int_tree_map *) *dslot)->to);
791 FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
793 name = USE_FROM_PTR (use);
794 if (TREE_CODE (name) != SSA_NAME)
797 elt.version = SSA_NAME_VERSION (name);
798 slot = htab_find_slot_with_hash (name_copies, &elt, elt.version, NO_INSERT);
801 gimple_debug_bind_reset_value (stmt);
806 SET_USE (use, ((struct name_to_copy_elt *) *slot)->new_name);
812 /* Callback for htab_traverse. Adds a field corresponding to the reduction
813 specified in SLOT. The type is passed in DATA. */
816 add_field_for_reduction (void **slot, void *data)
819 struct reduction_info *const red = (struct reduction_info *) *slot;
820 tree const type = (tree) data;
821 tree var = SSA_NAME_VAR (gimple_assign_lhs (red->reduc_stmt));
822 tree field = build_decl (gimple_location (red->reduc_stmt),
823 FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
825 insert_field_into_struct (type, field);
832 /* Callback for htab_traverse. Adds a field corresponding to a ssa name
833 described in SLOT. The type is passed in DATA. */
836 add_field_for_name (void **slot, void *data)
838 struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
839 tree type = (tree) data;
840 tree name = ssa_name (elt->version);
841 tree var = SSA_NAME_VAR (name);
842 tree field = build_decl (DECL_SOURCE_LOCATION (var),
843 FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
845 insert_field_into_struct (type, field);
851 /* Callback for htab_traverse. A local result is the intermediate result
853 thread, or the initial value in case no iteration was executed.
854 This function creates a phi node reflecting these values.
855 The phi's result will be stored in NEW_PHI field of the
856 reduction's data structure. */
859 create_phi_for_local_result (void **slot, void *data)
861 struct reduction_info *const reduc = (struct reduction_info *) *slot;
862 const struct loop *const loop = (const struct loop *) data;
865 basic_block store_bb;
867 source_location locus;
869 /* STORE_BB is the block where the phi
870 should be stored. It is the destination of the loop exit.
871 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
872 store_bb = FALLTHRU_EDGE (loop->latch)->dest;
874 /* STORE_BB has two predecessors. One coming from the loop
875 (the reduction's result is computed at the loop),
876 and another coming from a block preceding the loop,
878 are executed (the initial value should be taken). */
879 if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (loop->latch))
880 e = EDGE_PRED (store_bb, 1);
882 e = EDGE_PRED (store_bb, 0);
884 = make_ssa_name (SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt)),
886 locus = gimple_location (reduc->reduc_stmt);
887 new_phi = create_phi_node (local_res, store_bb);
888 SSA_NAME_DEF_STMT (local_res) = new_phi;
889 add_phi_arg (new_phi, reduc->init, e, locus);
890 add_phi_arg (new_phi, gimple_assign_lhs (reduc->reduc_stmt),
891 FALLTHRU_EDGE (loop->latch), locus);
892 reduc->new_phi = new_phi;
902 basic_block store_bb;
906 /* Callback for htab_traverse. Create an atomic instruction for the
907 reduction described in SLOT.
908 DATA annotates the place in memory the atomic operation relates to,
909 and the basic block it needs to be generated in. */
912 create_call_for_reduction_1 (void **slot, void *data)
914 struct reduction_info *const reduc = (struct reduction_info *) *slot;
915 struct clsn_data *const clsn_data = (struct clsn_data *) data;
916 gimple_stmt_iterator gsi;
917 tree type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
922 tree t, addr, ref, x;
926 load_struct = build_simple_mem_ref (clsn_data->load);
927 t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
929 addr = build_addr (t, current_function_decl);
931 /* Create phi node. */
932 bb = clsn_data->load_bb;
934 e = split_block (bb, t);
937 tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)), NULL);
938 add_referenced_var (tmp_load);
939 tmp_load = make_ssa_name (tmp_load, NULL);
940 load = gimple_build_omp_atomic_load (tmp_load, addr);
941 SSA_NAME_DEF_STMT (tmp_load) = load;
942 gsi = gsi_start_bb (new_bb);
943 gsi_insert_after (&gsi, load, GSI_NEW_STMT);
945 e = split_block (new_bb, load);
947 gsi = gsi_start_bb (new_bb);
949 x = fold_build2 (reduc->reduction_code,
950 TREE_TYPE (PHI_RESULT (reduc->new_phi)), ref,
951 PHI_RESULT (reduc->new_phi));
953 name = force_gimple_operand_gsi (&gsi, x, true, NULL_TREE, true,
954 GSI_CONTINUE_LINKING);
956 gsi_insert_after (&gsi, gimple_build_omp_atomic_store (name), GSI_NEW_STMT);
960 /* Create the atomic operation at the join point of the threads.
961 REDUCTION_LIST describes the reductions in the LOOP.
962 LD_ST_DATA describes the shared data structure where
963 shared data is stored in and loaded from. */
965 create_call_for_reduction (struct loop *loop, htab_t reduction_list,
966 struct clsn_data *ld_st_data)
968 htab_traverse (reduction_list, create_phi_for_local_result, loop);
969 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
970 ld_st_data->load_bb = FALLTHRU_EDGE (loop->latch)->dest;
971 htab_traverse (reduction_list, create_call_for_reduction_1, ld_st_data);
974 /* Callback for htab_traverse. Loads the final reduction value at the
975 join point of all threads, and inserts it in the right place. */
978 create_loads_for_reductions (void **slot, void *data)
980 struct reduction_info *const red = (struct reduction_info *) *slot;
981 struct clsn_data *const clsn_data = (struct clsn_data *) data;
983 gimple_stmt_iterator gsi;
984 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
989 gsi = gsi_after_labels (clsn_data->load_bb);
990 load_struct = build_simple_mem_ref (clsn_data->load);
991 load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
995 name = PHI_RESULT (red->keep_res);
996 stmt = gimple_build_assign (name, x);
997 SSA_NAME_DEF_STMT (name) = stmt;
999 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1001 for (gsi = gsi_start_phis (gimple_bb (red->keep_res));
1002 !gsi_end_p (gsi); gsi_next (&gsi))
1003 if (gsi_stmt (gsi) == red->keep_res)
1005 remove_phi_node (&gsi, false);
1011 /* Load the reduction result that was stored in LD_ST_DATA.
1012 REDUCTION_LIST describes the list of reductions that the
1013 loads should be generated for. */
1015 create_final_loads_for_reduction (htab_t reduction_list,
1016 struct clsn_data *ld_st_data)
1018 gimple_stmt_iterator gsi;
1022 gsi = gsi_after_labels (ld_st_data->load_bb);
1023 t = build_fold_addr_expr (ld_st_data->store);
1024 stmt = gimple_build_assign (ld_st_data->load, t);
1026 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1027 SSA_NAME_DEF_STMT (ld_st_data->load) = stmt;
1029 htab_traverse (reduction_list, create_loads_for_reductions, ld_st_data);
1033 /* Callback for htab_traverse. Store the neutral value for the
1034 particular reduction's operation, e.g. 0 for PLUS_EXPR,
1035 1 for MULT_EXPR, etc. into the reduction field.
1036 The reduction is specified in SLOT. The store information is
1040 create_stores_for_reduction (void **slot, void *data)
1042 struct reduction_info *const red = (struct reduction_info *) *slot;
1043 struct clsn_data *const clsn_data = (struct clsn_data *) data;
1046 gimple_stmt_iterator gsi;
1047 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
1049 gsi = gsi_last_bb (clsn_data->store_bb);
1050 t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE);
1051 stmt = gimple_build_assign (t, red->initial_value);
1052 mark_virtual_ops_for_renaming (stmt);
1053 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1058 /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
1059 store to a field of STORE in STORE_BB for the ssa name and its duplicate
1060 specified in SLOT. */
1063 create_loads_and_stores_for_name (void **slot, void *data)
1065 struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
1066 struct clsn_data *const clsn_data = (struct clsn_data *) data;
1069 gimple_stmt_iterator gsi;
1070 tree type = TREE_TYPE (elt->new_name);
1073 gsi = gsi_last_bb (clsn_data->store_bb);
1074 t = build3 (COMPONENT_REF, type, clsn_data->store, elt->field, NULL_TREE);
1075 stmt = gimple_build_assign (t, ssa_name (elt->version));
1076 mark_virtual_ops_for_renaming (stmt);
1077 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1079 gsi = gsi_last_bb (clsn_data->load_bb);
1080 load_struct = build_simple_mem_ref (clsn_data->load);
1081 t = build3 (COMPONENT_REF, type, load_struct, elt->field, NULL_TREE);
1082 stmt = gimple_build_assign (elt->new_name, t);
1083 SSA_NAME_DEF_STMT (elt->new_name) = stmt;
1084 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1089 /* Moves all the variables used in LOOP and defined outside of it (including
1090 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1091 name) to a structure created for this purpose. The code
1099 is transformed this way:
1114 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1115 pointer `new' is intentionally not initialized (the loop will be split to a
1116 separate function later, and `new' will be initialized from its arguments).
1117 LD_ST_DATA holds information about the shared data structure used to pass
1118 information among the threads. It is initialized here, and
1119 gen_parallel_loop will pass it to create_call_for_reduction that
1120 needs this information. REDUCTION_LIST describes the reductions
1124 separate_decls_in_region (edge entry, edge exit, htab_t reduction_list,
1125 tree *arg_struct, tree *new_arg_struct,
1126 struct clsn_data *ld_st_data)
1129 basic_block bb1 = split_edge (entry);
1130 basic_block bb0 = single_pred (bb1);
1131 htab_t name_copies = htab_create (10, name_to_copy_elt_hash,
1132 name_to_copy_elt_eq, free);
1133 htab_t decl_copies = htab_create (10, int_tree_map_hash, int_tree_map_eq,
1136 tree type, type_name, nvar;
1137 gimple_stmt_iterator gsi;
1138 struct clsn_data clsn_data;
1139 VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
1141 basic_block entry_bb = bb1;
1142 basic_block exit_bb = exit->dest;
1143 bool has_debug_stmt = false;
1145 entry = single_succ_edge (entry_bb);
1146 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
1148 FOR_EACH_VEC_ELT (basic_block, body, i, bb)
1150 if (bb != entry_bb && bb != exit_bb)
1152 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1153 separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
1154 name_copies, decl_copies);
1156 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1158 gimple stmt = gsi_stmt (gsi);
1160 if (is_gimple_debug (stmt))
1161 has_debug_stmt = true;
1163 separate_decls_in_region_stmt (entry, exit, stmt,
1164 name_copies, decl_copies);
1169 /* Now process debug bind stmts. We must not create decls while
1170 processing debug stmts, so we defer their processing so as to
1171 make sure we will have debug info for as many variables as
1172 possible (all of those that were dealt with in the loop above),
1173 and discard those for which we know there's nothing we can
1176 FOR_EACH_VEC_ELT (basic_block, body, i, bb)
1177 if (bb != entry_bb && bb != exit_bb)
1179 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
1181 gimple stmt = gsi_stmt (gsi);
1183 if (gimple_debug_bind_p (stmt))
1185 if (separate_decls_in_region_debug_bind (stmt,
1189 gsi_remove (&gsi, true);
1198 VEC_free (basic_block, heap, body);
1200 if (htab_elements (name_copies) == 0 && htab_elements (reduction_list) == 0)
1202 /* It may happen that there is nothing to copy (if there are only
1203 loop carried and external variables in the loop). */
1205 *new_arg_struct = NULL;
1209 /* Create the type for the structure to store the ssa names to. */
1210 type = lang_hooks.types.make_type (RECORD_TYPE);
1211 type_name = build_decl (UNKNOWN_LOCATION,
1212 TYPE_DECL, create_tmp_var_name (".paral_data"),
1214 TYPE_NAME (type) = type_name;
1216 htab_traverse (name_copies, add_field_for_name, type);
1217 if (reduction_list && htab_elements (reduction_list) > 0)
1219 /* Create the fields for reductions. */
1220 htab_traverse (reduction_list, add_field_for_reduction,
1225 /* Create the loads and stores. */
1226 *arg_struct = create_tmp_var (type, ".paral_data_store");
1227 add_referenced_var (*arg_struct);
1228 nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load");
1229 add_referenced_var (nvar);
1230 *new_arg_struct = make_ssa_name (nvar, NULL);
1232 ld_st_data->store = *arg_struct;
1233 ld_st_data->load = *new_arg_struct;
1234 ld_st_data->store_bb = bb0;
1235 ld_st_data->load_bb = bb1;
1237 htab_traverse (name_copies, create_loads_and_stores_for_name,
1240 /* Load the calculation from memory (after the join of the threads). */
1242 if (reduction_list && htab_elements (reduction_list) > 0)
1244 htab_traverse (reduction_list, create_stores_for_reduction,
1246 clsn_data.load = make_ssa_name (nvar, NULL);
1247 clsn_data.load_bb = exit->dest;
1248 clsn_data.store = ld_st_data->store;
1249 create_final_loads_for_reduction (reduction_list, &clsn_data);
1253 htab_delete (decl_copies);
1254 htab_delete (name_copies);
1257 /* Bitmap containing uids of functions created by parallelization. We cannot
1258 allocate it from the default obstack, as it must live across compilation
1259 of several functions; we make it gc allocated instead. */
1261 static GTY(()) bitmap parallelized_functions;
1263 /* Returns true if FN was created by create_loop_fn. */
1266 parallelized_function_p (tree fn)
1268 if (!parallelized_functions || !DECL_ARTIFICIAL (fn))
1271 return bitmap_bit_p (parallelized_functions, DECL_UID (fn));
1274 /* Creates and returns an empty function that will receive the body of
1275 a parallelized loop. */
1278 create_loop_fn (location_t loc)
1282 tree decl, type, name, t;
1283 struct function *act_cfun = cfun;
1284 static unsigned loopfn_num;
1286 snprintf (buf, 100, "%s.$loopfn", current_function_name ());
1287 ASM_FORMAT_PRIVATE_NAME (tname, buf, loopfn_num++);
1288 clean_symbol_name (tname);
1289 name = get_identifier (tname);
1290 type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
1292 decl = build_decl (loc, FUNCTION_DECL, name, type);
1293 if (!parallelized_functions)
1294 parallelized_functions = BITMAP_GGC_ALLOC ();
1295 bitmap_set_bit (parallelized_functions, DECL_UID (decl));
1297 TREE_STATIC (decl) = 1;
1298 TREE_USED (decl) = 1;
1299 DECL_ARTIFICIAL (decl) = 1;
1300 DECL_IGNORED_P (decl) = 0;
1301 TREE_PUBLIC (decl) = 0;
1302 DECL_UNINLINABLE (decl) = 1;
1303 DECL_EXTERNAL (decl) = 0;
1304 DECL_CONTEXT (decl) = NULL_TREE;
1305 DECL_INITIAL (decl) = make_node (BLOCK);
1307 t = build_decl (loc, RESULT_DECL, NULL_TREE, void_type_node);
1308 DECL_ARTIFICIAL (t) = 1;
1309 DECL_IGNORED_P (t) = 1;
1310 DECL_RESULT (decl) = t;
1312 t = build_decl (loc, PARM_DECL, get_identifier (".paral_data_param"),
1314 DECL_ARTIFICIAL (t) = 1;
1315 DECL_ARG_TYPE (t) = ptr_type_node;
1316 DECL_CONTEXT (t) = decl;
1318 DECL_ARGUMENTS (decl) = t;
1320 allocate_struct_function (decl, false);
1322 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1324 set_cfun (act_cfun);
1329 /* Moves the exit condition of LOOP to the beginning of its header, and
1330 duplicates the part of the last iteration that gets disabled to the
1331 exit of the loop. NIT is the number of iterations of the loop
1332 (used to initialize the variables in the duplicated part).
1334 TODO: the common case is that latch of the loop is empty and immediately
1335 follows the loop exit. In this case, it would be better not to copy the
1336 body of the loop, but only move the entry of the loop directly before the
1337 exit check and increase the number of iterations of the loop by one.
1338 This may need some additional preconditioning in case NIT = ~0.
1339 REDUCTION_LIST describes the reductions in LOOP. */
1342 transform_to_exit_first_loop (struct loop *loop, htab_t reduction_list, tree nit)
1344 basic_block *bbs, *nbbs, ex_bb, orig_header;
1347 edge exit = single_dom_exit (loop), hpred;
1348 tree control, control_name, res, t;
1349 gimple phi, nphi, cond_stmt, stmt, cond_nit;
1350 gimple_stmt_iterator gsi;
1353 split_block_after_labels (loop->header);
1354 orig_header = single_succ (loop->header);
1355 hpred = single_succ_edge (loop->header);
1357 cond_stmt = last_stmt (exit->src);
1358 control = gimple_cond_lhs (cond_stmt);
1359 gcc_assert (gimple_cond_rhs (cond_stmt) == nit);
1361 /* Make sure that we have phi nodes on exit for all loop header phis
1362 (create_parallel_loop requires that). */
1363 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1365 phi = gsi_stmt (gsi);
1366 res = PHI_RESULT (phi);
1367 t = make_ssa_name (SSA_NAME_VAR (res), phi);
1368 SET_PHI_RESULT (phi, t);
1369 nphi = create_phi_node (res, orig_header);
1370 SSA_NAME_DEF_STMT (res) = nphi;
1371 add_phi_arg (nphi, t, hpred, UNKNOWN_LOCATION);
1375 gimple_cond_set_lhs (cond_stmt, t);
1376 update_stmt (cond_stmt);
1380 bbs = get_loop_body_in_dom_order (loop);
1382 for (n = 0; bbs[n] != loop->latch; n++)
1384 nbbs = XNEWVEC (basic_block, n);
1385 ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
1392 /* Other than reductions, the only gimple reg that should be copied
1393 out of the loop is the control variable. */
1395 control_name = NULL_TREE;
1396 for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); )
1398 phi = gsi_stmt (gsi);
1399 res = PHI_RESULT (phi);
1400 if (!is_gimple_reg (res))
1406 /* Check if it is a part of reduction. If it is,
1407 keep the phi at the reduction's keep_res field. The
1408 PHI_RESULT of this phi is the resulting value of the reduction
1409 variable when exiting the loop. */
1411 exit = single_dom_exit (loop);
1413 if (htab_elements (reduction_list) > 0)
1415 struct reduction_info *red;
1417 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1418 red = reduction_phi (reduction_list, SSA_NAME_DEF_STMT (val));
1421 red->keep_res = phi;
1426 gcc_assert (control_name == NULL_TREE
1427 && SSA_NAME_VAR (res) == SSA_NAME_VAR (control));
1429 remove_phi_node (&gsi, false);
1431 gcc_assert (control_name != NULL_TREE);
1433 /* Initialize the control variable to number of iterations
1434 according to the rhs of the exit condition. */
1435 gsi = gsi_after_labels (ex_bb);
1436 cond_nit = last_stmt (exit->src);
1437 nit_1 = gimple_cond_rhs (cond_nit);
1438 nit_1 = force_gimple_operand_gsi (&gsi,
1439 fold_convert (TREE_TYPE (control_name), nit_1),
1440 false, NULL_TREE, false, GSI_SAME_STMT);
1441 stmt = gimple_build_assign (control_name, nit_1);
1442 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1443 SSA_NAME_DEF_STMT (control_name) = stmt;
1446 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
1447 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
1448 NEW_DATA is the variable that should be initialized from the argument
1449 of LOOP_FN. N_THREADS is the requested number of threads. Returns the
1450 basic block containing GIMPLE_OMP_PARALLEL tree. */
1453 create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
1454 tree new_data, unsigned n_threads, location_t loc)
1456 gimple_stmt_iterator gsi;
1457 basic_block bb, paral_bb, for_bb, ex_bb;
1459 gimple stmt, for_stmt, phi, cond_stmt;
1460 tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
1461 edge exit, nexit, guard, end, e;
1463 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
1464 bb = loop_preheader_edge (loop)->src;
1465 paral_bb = single_pred (bb);
1466 gsi = gsi_last_bb (paral_bb);
1468 t = build_omp_clause (loc, OMP_CLAUSE_NUM_THREADS);
1469 OMP_CLAUSE_NUM_THREADS_EXPR (t)
1470 = build_int_cst (integer_type_node, n_threads);
1471 stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
1472 gimple_set_location (stmt, loc);
1474 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1476 /* Initialize NEW_DATA. */
1479 gsi = gsi_after_labels (bb);
1481 param = make_ssa_name (DECL_ARGUMENTS (loop_fn), NULL);
1482 stmt = gimple_build_assign (param, build_fold_addr_expr (data));
1483 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1484 SSA_NAME_DEF_STMT (param) = stmt;
1486 stmt = gimple_build_assign (new_data,
1487 fold_convert (TREE_TYPE (new_data), param));
1488 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1489 SSA_NAME_DEF_STMT (new_data) = stmt;
1492 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
1493 bb = split_loop_exit_edge (single_dom_exit (loop));
1494 gsi = gsi_last_bb (bb);
1495 stmt = gimple_build_omp_return (false);
1496 gimple_set_location (stmt, loc);
1497 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1499 /* Extract data for GIMPLE_OMP_FOR. */
1500 gcc_assert (loop->header == single_dom_exit (loop)->src);
1501 cond_stmt = last_stmt (loop->header);
1503 cvar = gimple_cond_lhs (cond_stmt);
1504 cvar_base = SSA_NAME_VAR (cvar);
1505 phi = SSA_NAME_DEF_STMT (cvar);
1506 cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1507 initvar = make_ssa_name (cvar_base, NULL);
1508 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
1510 cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1512 gsi = gsi_last_nondebug_bb (loop->latch);
1513 gcc_assert (gsi_stmt (gsi) == SSA_NAME_DEF_STMT (cvar_next));
1514 gsi_remove (&gsi, true);
1517 for_bb = split_edge (loop_preheader_edge (loop));
1518 ex_bb = split_loop_exit_edge (single_dom_exit (loop));
1519 extract_true_false_edges_from_block (loop->header, &nexit, &exit);
1520 gcc_assert (exit == single_dom_exit (loop));
1522 guard = make_edge (for_bb, ex_bb, 0);
1523 single_succ_edge (loop->latch)->flags = 0;
1524 end = make_edge (loop->latch, ex_bb, EDGE_FALLTHRU);
1525 for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); gsi_next (&gsi))
1527 source_location locus;
1529 phi = gsi_stmt (gsi);
1530 stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi, exit));
1532 def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop));
1533 locus = gimple_phi_arg_location_from_edge (stmt,
1534 loop_preheader_edge (loop));
1535 add_phi_arg (phi, def, guard, locus);
1537 def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_latch_edge (loop));
1538 locus = gimple_phi_arg_location_from_edge (stmt, loop_latch_edge (loop));
1539 add_phi_arg (phi, def, end, locus);
1541 e = redirect_edge_and_branch (exit, nexit->dest);
1542 PENDING_STMT (e) = NULL;
1544 /* Emit GIMPLE_OMP_FOR. */
1545 gimple_cond_set_lhs (cond_stmt, cvar_base);
1546 type = TREE_TYPE (cvar);
1547 t = build_omp_clause (loc, OMP_CLAUSE_SCHEDULE);
1548 OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
1550 for_stmt = gimple_build_omp_for (NULL, t, 1, NULL);
1551 gimple_set_location (for_stmt, loc);
1552 gimple_omp_for_set_index (for_stmt, 0, initvar);
1553 gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
1554 gimple_omp_for_set_final (for_stmt, 0, gimple_cond_rhs (cond_stmt));
1555 gimple_omp_for_set_cond (for_stmt, 0, gimple_cond_code (cond_stmt));
1556 gimple_omp_for_set_incr (for_stmt, 0, build2 (PLUS_EXPR, type,
1558 build_int_cst (type, 1)));
1560 gsi = gsi_last_bb (for_bb);
1561 gsi_insert_after (&gsi, for_stmt, GSI_NEW_STMT);
1562 SSA_NAME_DEF_STMT (initvar) = for_stmt;
1564 /* Emit GIMPLE_OMP_CONTINUE. */
1565 gsi = gsi_last_bb (loop->latch);
1566 stmt = gimple_build_omp_continue (cvar_next, cvar);
1567 gimple_set_location (stmt, loc);
1568 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1569 SSA_NAME_DEF_STMT (cvar_next) = stmt;
1571 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
1572 gsi = gsi_last_bb (ex_bb);
1573 stmt = gimple_build_omp_return (true);
1574 gimple_set_location (stmt, loc);
1575 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1580 /* Generates code to execute the iterations of LOOP in N_THREADS
1581 threads in parallel.
1583 NITER describes number of iterations of LOOP.
1584 REDUCTION_LIST describes the reductions existent in the LOOP. */
1587 gen_parallel_loop (struct loop *loop, htab_t reduction_list,
1588 unsigned n_threads, struct tree_niter_desc *niter)
1591 tree many_iterations_cond, type, nit;
1592 tree arg_struct, new_arg_struct;
1594 basic_block parallel_head;
1596 struct clsn_data clsn_data;
1603 ---------------------------------------------------------------------
1606 IV = phi (INIT, IV + STEP)
1612 ---------------------------------------------------------------------
1614 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
1615 we generate the following code:
1617 ---------------------------------------------------------------------
1620 || NITER < MIN_PER_THREAD * N_THREADS)
1624 store all local loop-invariant variables used in body of the loop to DATA.
1625 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
1626 load the variables from DATA.
1627 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
1630 GIMPLE_OMP_CONTINUE;
1631 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
1632 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
1638 IV = phi (INIT, IV + STEP)
1649 /* Create two versions of the loop -- in the old one, we know that the
1650 number of iterations is large enough, and we will transform it into the
1651 loop that will be split to loop_fn, the new one will be used for the
1652 remaining iterations. */
1654 type = TREE_TYPE (niter->niter);
1655 nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true,
1658 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1660 many_iterations_cond =
1661 fold_build2 (GE_EXPR, boolean_type_node,
1662 nit, build_int_cst (type, MIN_PER_THREAD * n_threads));
1663 many_iterations_cond
1664 = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1665 invert_truthvalue (unshare_expr (niter->may_be_zero)),
1666 many_iterations_cond);
1667 many_iterations_cond
1668 = force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
1670 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1671 if (!is_gimple_condexpr (many_iterations_cond))
1673 many_iterations_cond
1674 = force_gimple_operand (many_iterations_cond, &stmts,
1677 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1680 initialize_original_copy_tables ();
1682 /* We assume that the loop usually iterates a lot. */
1683 prob = 4 * REG_BR_PROB_BASE / 5;
1684 loop_version (loop, many_iterations_cond, NULL,
1685 prob, prob, REG_BR_PROB_BASE - prob, true);
1686 update_ssa (TODO_update_ssa);
1687 free_original_copy_tables ();
1689 /* Base all the induction variables in LOOP on a single control one. */
1690 canonicalize_loop_ivs (loop, &nit, true);
1692 /* Ensure that the exit condition is the first statement in the loop. */
1693 transform_to_exit_first_loop (loop, reduction_list, nit);
1695 /* Generate initializations for reductions. */
1696 if (htab_elements (reduction_list) > 0)
1697 htab_traverse (reduction_list, initialize_reductions, loop);
1699 /* Eliminate the references to local variables from the loop. */
1700 gcc_assert (single_exit (loop));
1701 entry = loop_preheader_edge (loop);
1702 exit = single_dom_exit (loop);
1704 eliminate_local_variables (entry, exit);
1705 /* In the old loop, move all variables non-local to the loop to a structure
1706 and back, and create separate decls for the variables used in loop. */
1707 separate_decls_in_region (entry, exit, reduction_list, &arg_struct,
1708 &new_arg_struct, &clsn_data);
1710 /* Create the parallel constructs. */
1711 loc = UNKNOWN_LOCATION;
1712 cond_stmt = last_stmt (loop->header);
1714 loc = gimple_location (cond_stmt);
1715 parallel_head = create_parallel_loop (loop, create_loop_fn (loc), arg_struct,
1716 new_arg_struct, n_threads, loc);
1717 if (htab_elements (reduction_list) > 0)
1718 create_call_for_reduction (loop, reduction_list, &clsn_data);
1722 /* Cancel the loop (it is simpler to do it here rather than to teach the
1723 expander to do it). */
1724 cancel_loop_tree (loop);
1726 /* Free loop bound estimations that could contain references to
1727 removed statements. */
1728 FOR_EACH_LOOP (li, loop, 0)
1729 free_numbers_of_iterations_estimates_loop (loop);
1731 /* Expand the parallel constructs. We do it directly here instead of running
1732 a separate expand_omp pass, since it is more efficient, and less likely to
1733 cause troubles with further analyses not being able to deal with the
1736 omp_expand_local (parallel_head);
1739 /* Returns true when LOOP contains vector phi nodes. */
1742 loop_has_vector_phi_nodes (struct loop *loop ATTRIBUTE_UNUSED)
1745 basic_block *bbs = get_loop_body_in_dom_order (loop);
1746 gimple_stmt_iterator gsi;
1749 for (i = 0; i < loop->num_nodes; i++)
1750 for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
1751 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi_stmt (gsi)))) == VECTOR_TYPE)
1760 /* Create a reduction_info struct, initialize it with REDUC_STMT
1761 and PHI, insert it to the REDUCTION_LIST. */
1764 build_new_reduction (htab_t reduction_list, gimple reduc_stmt, gimple phi)
1767 struct reduction_info *new_reduction;
1769 gcc_assert (reduc_stmt);
1771 if (dump_file && (dump_flags & TDF_DETAILS))
1774 "Detected reduction. reduction stmt is: \n");
1775 print_gimple_stmt (dump_file, reduc_stmt, 0, 0);
1776 fprintf (dump_file, "\n");
1779 new_reduction = XCNEW (struct reduction_info);
1781 new_reduction->reduc_stmt = reduc_stmt;
1782 new_reduction->reduc_phi = phi;
1783 new_reduction->reduc_version = SSA_NAME_VERSION (gimple_phi_result (phi));
1784 new_reduction->reduction_code = gimple_assign_rhs_code (reduc_stmt);
1785 slot = htab_find_slot (reduction_list, new_reduction, INSERT);
1786 *slot = new_reduction;
1789 /* Callback for htab_traverse. Sets gimple_uid of reduc_phi stmts. */
1792 set_reduc_phi_uids (void **slot, void *data ATTRIBUTE_UNUSED)
1794 struct reduction_info *const red = (struct reduction_info *) *slot;
1795 gimple_set_uid (red->reduc_phi, red->reduc_version);
1799 /* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
1802 gather_scalar_reductions (loop_p loop, htab_t reduction_list)
1804 gimple_stmt_iterator gsi;
1805 loop_vec_info simple_loop_info;
1808 simple_loop_info = vect_analyze_loop_form (loop);
1810 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1812 gimple phi = gsi_stmt (gsi);
1814 tree res = PHI_RESULT (phi);
1817 if (!is_gimple_reg (res))
1820 if (!simple_iv (loop, loop, res, &iv, true)
1821 && simple_loop_info)
1823 gimple reduc_stmt = vect_force_simple_reduction (simple_loop_info,
1826 if (reduc_stmt && !double_reduc)
1827 build_new_reduction (reduction_list, reduc_stmt, phi);
1830 destroy_loop_vec_info (simple_loop_info, true);
1832 /* As gimple_uid is used by the vectorizer in between vect_analyze_loop_form
1833 and destroy_loop_vec_info, we can set gimple_uid of reduc_phi stmts
1835 htab_traverse (reduction_list, set_reduc_phi_uids, NULL);
1838 /* Try to initialize NITER for code generation part. */
1841 try_get_loop_niter (loop_p loop, struct tree_niter_desc *niter)
1843 edge exit = single_dom_exit (loop);
1847 /* We need to know # of iterations, and there should be no uses of values
1848 defined inside loop outside of it, unless the values are invariants of
1850 if (!number_of_iterations_exit (loop, exit, niter, false))
1852 if (dump_file && (dump_flags & TDF_DETAILS))
1853 fprintf (dump_file, " FAILED: number of iterations not known\n");
1860 /* Try to initialize REDUCTION_LIST for code generation part.
1861 REDUCTION_LIST describes the reductions. */
1864 try_create_reduction_list (loop_p loop, htab_t reduction_list)
1866 edge exit = single_dom_exit (loop);
1867 gimple_stmt_iterator gsi;
1871 gather_scalar_reductions (loop, reduction_list);
1874 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
1876 gimple phi = gsi_stmt (gsi);
1877 struct reduction_info *red;
1878 imm_use_iterator imm_iter;
1879 use_operand_p use_p;
1881 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1883 if (is_gimple_reg (val))
1885 if (dump_file && (dump_flags & TDF_DETAILS))
1887 fprintf (dump_file, "phi is ");
1888 print_gimple_stmt (dump_file, phi, 0, 0);
1889 fprintf (dump_file, "arg of phi to exit: value ");
1890 print_generic_expr (dump_file, val, 0);
1891 fprintf (dump_file, " used outside loop\n");
1893 " checking if it a part of reduction pattern: \n");
1895 if (htab_elements (reduction_list) == 0)
1897 if (dump_file && (dump_flags & TDF_DETAILS))
1899 " FAILED: it is not a part of reduction.\n");
1903 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
1905 if (!gimple_debug_bind_p (USE_STMT (use_p))
1906 && flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
1908 reduc_phi = USE_STMT (use_p);
1912 red = reduction_phi (reduction_list, reduc_phi);
1915 if (dump_file && (dump_flags & TDF_DETAILS))
1917 " FAILED: it is not a part of reduction.\n");
1920 if (dump_file && (dump_flags & TDF_DETAILS))
1922 fprintf (dump_file, "reduction phi is ");
1923 print_gimple_stmt (dump_file, red->reduc_phi, 0, 0);
1924 fprintf (dump_file, "reduction stmt is ");
1925 print_gimple_stmt (dump_file, red->reduc_stmt, 0, 0);
1930 /* The iterations of the loop may communicate only through bivs whose
1931 iteration space can be distributed efficiently. */
1932 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1934 gimple phi = gsi_stmt (gsi);
1935 tree def = PHI_RESULT (phi);
1938 if (is_gimple_reg (def) && !simple_iv (loop, loop, def, &iv, true))
1940 struct reduction_info *red;
1942 red = reduction_phi (reduction_list, phi);
1945 if (dump_file && (dump_flags & TDF_DETAILS))
1947 " FAILED: scalar dependency between iterations\n");
1957 /* Detect parallel loops and generate parallel code using libgomp
1958 primitives. Returns true if some loop was parallelized, false
1962 parallelize_loops (void)
1964 unsigned n_threads = flag_tree_parallelize_loops;
1965 bool changed = false;
1967 struct tree_niter_desc niter_desc;
1969 htab_t reduction_list;
1970 struct obstack parloop_obstack;
1971 HOST_WIDE_INT estimated;
1974 /* Do not parallelize loops in the functions created by parallelization. */
1975 if (parallelized_function_p (cfun->decl))
1977 if (cfun->has_nonlocal_label)
1980 gcc_obstack_init (&parloop_obstack);
1981 reduction_list = htab_create (10, reduction_info_hash,
1982 reduction_info_eq, free);
1983 init_stmt_vec_info_vec ();
1985 FOR_EACH_LOOP (li, loop, 0)
1987 htab_empty (reduction_list);
1988 if (dump_file && (dump_flags & TDF_DETAILS))
1990 fprintf (dump_file, "Trying loop %d as candidate\n",loop->num);
1992 fprintf (dump_file, "loop %d is not innermost\n",loop->num);
1994 fprintf (dump_file, "loop %d is innermost\n",loop->num);
1997 /* If we use autopar in graphite pass, we use its marked dependency
1998 checking results. */
1999 if (flag_loop_parallelize_all && !loop->can_be_parallel)
2001 if (dump_file && (dump_flags & TDF_DETAILS))
2002 fprintf (dump_file, "loop is not parallel according to graphite\n");
2006 if (!single_dom_exit (loop))
2009 if (dump_file && (dump_flags & TDF_DETAILS))
2010 fprintf (dump_file, "loop is !single_dom_exit\n");
2015 if (/* And of course, the loop must be parallelizable. */
2016 !can_duplicate_loop_p (loop)
2017 || loop_has_blocks_with_irreducible_flag (loop)
2018 || (loop_preheader_edge (loop)->src->flags & BB_IRREDUCIBLE_LOOP)
2019 /* FIXME: the check for vector phi nodes could be removed. */
2020 || loop_has_vector_phi_nodes (loop))
2022 estimated = estimated_loop_iterations_int (loop, false);
2023 /* FIXME: Bypass this check as graphite doesn't update the
2024 count and frequency correctly now. */
2025 if (!flag_loop_parallelize_all
2027 && estimated <= (HOST_WIDE_INT) n_threads * MIN_PER_THREAD)
2028 /* Do not bother with loops in cold areas. */
2029 || optimize_loop_nest_for_size_p (loop)))
2032 if (!try_get_loop_niter (loop, &niter_desc))
2035 if (!try_create_reduction_list (loop, reduction_list))
2038 if (!flag_loop_parallelize_all
2039 && !loop_parallel_p (loop, &parloop_obstack))
2043 if (dump_file && (dump_flags & TDF_DETAILS))
2046 fprintf (dump_file, "parallelizing outer loop %d\n",loop->header->index);
2048 fprintf (dump_file, "parallelizing inner loop %d\n",loop->header->index);
2049 loop_loc = find_loop_location (loop);
2050 if (loop_loc != UNKNOWN_LOC)
2051 fprintf (dump_file, "\nloop at %s:%d: ",
2052 LOC_FILE (loop_loc), LOC_LINE (loop_loc));
2054 gen_parallel_loop (loop, reduction_list,
2055 n_threads, &niter_desc);
2056 verify_flow_info ();
2057 verify_dominators (CDI_DOMINATORS);
2058 verify_loop_structure ();
2059 verify_loop_closed_ssa (true);
2062 free_stmt_vec_info_vec ();
2063 htab_delete (reduction_list);
2064 obstack_free (&parloop_obstack, NULL);
2066 /* Parallelization will cause new function calls to be inserted through
2067 which local variables will escape. Reset the points-to solution
2070 pt_solution_reset (&cfun->gimple_df->escaped);
2075 #include "gt-tree-parloops.h"