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 (ddr_p
, heap
) * dependence_relations
;
256 VEC (data_reference_p
, heap
) *datarefs
;
257 lambda_trans_matrix trans
;
260 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
262 fprintf (dump_file
, "Considering loop %d\n", loop
->num
);
264 fprintf (dump_file
, "loop is innermost\n");
266 fprintf (dump_file
, "loop NOT innermost\n");
269 /* Check for problems with dependences. If the loop can be reversed,
270 the iterations are independent. */
271 datarefs
= VEC_alloc (data_reference_p
, heap
, 10);
272 dependence_relations
= VEC_alloc (ddr_p
, heap
, 10 * 10);
273 compute_data_dependences_for_loop (loop
, true, &datarefs
,
274 &dependence_relations
);
275 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
276 dump_data_dependence_relations (dump_file
, dependence_relations
);
278 trans
= lambda_trans_matrix_new (1, 1, parloop_obstack
);
279 LTM_MATRIX (trans
)[0][0] = -1;
281 if (lambda_transform_legal_p (trans
, 1, dependence_relations
))
284 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
285 fprintf (dump_file
, " SUCCESS: may be parallelized\n");
287 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
289 " FAILED: data dependencies exist across iterations\n");
291 free_dependence_relations (dependence_relations
);
292 free_data_refs (datarefs
);
297 /* Return true when LOOP contains basic blocks marked with the
298 BB_IRREDUCIBLE_LOOP flag. */
301 loop_has_blocks_with_irreducible_flag (struct loop
*loop
)
304 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
307 for (i
= 0; i
< loop
->num_nodes
; i
++)
308 if (bbs
[i
]->flags
& BB_IRREDUCIBLE_LOOP
)
317 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
318 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
319 to their addresses that can be reused. The address of OBJ is known to
320 be invariant in the whole function. Other needed statements are placed
324 take_address_of (tree obj
, tree type
, edge entry
, htab_t decl_address
,
325 gimple_stmt_iterator
*gsi
)
329 struct int_tree_map ielt
, *nielt
;
330 tree
*var_p
, name
, bvar
, addr
;
334 /* Since the address of OBJ is invariant, the trees may be shared.
335 Avoid rewriting unrelated parts of the code. */
336 obj
= unshare_expr (obj
);
338 handled_component_p (*var_p
);
339 var_p
= &TREE_OPERAND (*var_p
, 0))
342 /* Canonicalize the access to base on a MEM_REF. */
344 *var_p
= build_simple_mem_ref (build_fold_addr_expr (*var_p
));
346 /* Assign a canonical SSA name to the address of the base decl used
347 in the address and share it for all accesses and addresses based
349 uid
= DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p
, 0), 0));
351 dslot
= htab_find_slot_with_hash (decl_address
, &ielt
, uid
, INSERT
);
356 addr
= TREE_OPERAND (*var_p
, 0);
357 bvar
= create_tmp_var (TREE_TYPE (addr
),
358 get_name (TREE_OPERAND
359 (TREE_OPERAND (*var_p
, 0), 0)));
360 add_referenced_var (bvar
);
361 stmt
= gimple_build_assign (bvar
, addr
);
362 name
= make_ssa_name (bvar
, stmt
);
363 gimple_assign_set_lhs (stmt
, name
);
364 gsi_insert_on_edge_immediate (entry
, stmt
);
366 nielt
= XNEW (struct int_tree_map
);
372 name
= ((struct int_tree_map
*) *dslot
)->to
;
374 /* Express the address in terms of the canonical SSA name. */
375 TREE_OPERAND (*var_p
, 0) = name
;
377 return build_fold_addr_expr_with_type (obj
, type
);
379 name
= force_gimple_operand (build_addr (obj
, current_function_decl
),
380 &stmts
, true, NULL_TREE
);
381 if (!gimple_seq_empty_p (stmts
))
382 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
384 if (!useless_type_conversion_p (type
, TREE_TYPE (name
)))
386 name
= force_gimple_operand (fold_convert (type
, name
), &stmts
, true,
388 if (!gimple_seq_empty_p (stmts
))
389 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
395 /* Callback for htab_traverse. Create the initialization statement
396 for reduction described in SLOT, and place it at the preheader of
397 the loop described in DATA. */
400 initialize_reductions (void **slot
, void *data
)
403 tree bvar
, type
, arg
;
406 struct reduction_info
*const reduc
= (struct reduction_info
*) *slot
;
407 struct loop
*loop
= (struct loop
*) data
;
409 /* Create initialization in preheader:
410 reduction_variable = initialization value of reduction. */
412 /* In the phi node at the header, replace the argument coming
413 from the preheader with the reduction initialization value. */
415 /* Create a new variable to initialize the reduction. */
416 type
= TREE_TYPE (PHI_RESULT (reduc
->reduc_phi
));
417 bvar
= create_tmp_var (type
, "reduction");
418 add_referenced_var (bvar
);
420 c
= build_omp_clause (gimple_location (reduc
->reduc_stmt
),
421 OMP_CLAUSE_REDUCTION
);
422 OMP_CLAUSE_REDUCTION_CODE (c
) = reduc
->reduction_code
;
423 OMP_CLAUSE_DECL (c
) = SSA_NAME_VAR (gimple_assign_lhs (reduc
->reduc_stmt
));
425 init
= omp_reduction_init (c
, TREE_TYPE (bvar
));
428 /* Replace the argument representing the initialization value
429 with the initialization value for the reduction (neutral
430 element for the particular operation, e.g. 0 for PLUS_EXPR,
431 1 for MULT_EXPR, etc).
432 Keep the old value in a new variable "reduction_initial",
433 that will be taken in consideration after the parallel
434 computing is done. */
436 e
= loop_preheader_edge (loop
);
437 arg
= PHI_ARG_DEF_FROM_EDGE (reduc
->reduc_phi
, e
);
438 /* Create new variable to hold the initial value. */
440 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
441 (reduc
->reduc_phi
, loop_preheader_edge (loop
)), init
);
442 reduc
->initial_value
= arg
;
448 struct walk_stmt_info info
;
451 gimple_stmt_iterator
*gsi
;
456 /* Eliminates references to local variables in *TP out of the single
457 entry single exit region starting at DTA->ENTRY.
458 DECL_ADDRESS contains addresses of the references that had their
459 address taken already. If the expression is changed, CHANGED is
460 set to true. Callback for walk_tree. */
463 eliminate_local_variables_1 (tree
*tp
, int *walk_subtrees
, void *data
)
465 struct elv_data
*const dta
= (struct elv_data
*) data
;
466 tree t
= *tp
, var
, addr
, addr_type
, type
, obj
;
472 if (!SSA_VAR_P (t
) || DECL_EXTERNAL (t
))
475 type
= TREE_TYPE (t
);
476 addr_type
= build_pointer_type (type
);
477 addr
= take_address_of (t
, addr_type
, dta
->entry
, dta
->decl_address
,
479 if (dta
->gsi
== NULL
&& addr
== NULL_TREE
)
485 *tp
= build_simple_mem_ref (addr
);
491 if (TREE_CODE (t
) == ADDR_EXPR
)
493 /* ADDR_EXPR may appear in two contexts:
494 -- as a gimple operand, when the address taken is a function invariant
495 -- as gimple rhs, when the resulting address in not a function
497 We do not need to do anything special in the latter case (the base of
498 the memory reference whose address is taken may be replaced in the
499 DECL_P case). The former case is more complicated, as we need to
500 ensure that the new address is still a gimple operand. Thus, it
501 is not sufficient to replace just the base of the memory reference --
502 we need to move the whole computation of the address out of the
504 if (!is_gimple_val (t
))
508 obj
= TREE_OPERAND (t
, 0);
509 var
= get_base_address (obj
);
510 if (!var
|| !SSA_VAR_P (var
) || DECL_EXTERNAL (var
))
513 addr_type
= TREE_TYPE (t
);
514 addr
= take_address_of (obj
, addr_type
, dta
->entry
, dta
->decl_address
,
516 if (dta
->gsi
== NULL
&& addr
== NULL_TREE
)
533 /* Moves the references to local variables in STMT at *GSI out of the single
534 entry single exit region starting at ENTRY. DECL_ADDRESS contains
535 addresses of the references that had their address taken
539 eliminate_local_variables_stmt (edge entry
, gimple_stmt_iterator
*gsi
,
543 gimple stmt
= gsi_stmt (*gsi
);
545 memset (&dta
.info
, '\0', sizeof (dta
.info
));
547 dta
.decl_address
= decl_address
;
551 if (gimple_debug_bind_p (stmt
))
554 walk_tree (gimple_debug_bind_get_value_ptr (stmt
),
555 eliminate_local_variables_1
, &dta
.info
, NULL
);
558 gimple_debug_bind_reset_value (stmt
);
565 walk_gimple_op (stmt
, eliminate_local_variables_1
, &dta
.info
);
572 /* Eliminates the references to local variables from the single entry
573 single exit region between the ENTRY and EXIT edges.
576 1) Taking address of a local variable -- these are moved out of the
577 region (and temporary variable is created to hold the address if
580 2) Dereferencing a local variable -- these are replaced with indirect
584 eliminate_local_variables (edge entry
, edge exit
)
587 VEC (basic_block
, heap
) *body
= VEC_alloc (basic_block
, heap
, 3);
589 gimple_stmt_iterator gsi
;
590 bool has_debug_stmt
= false;
591 htab_t decl_address
= htab_create (10, int_tree_map_hash
, int_tree_map_eq
,
593 basic_block entry_bb
= entry
->src
;
594 basic_block exit_bb
= exit
->dest
;
596 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
598 FOR_EACH_VEC_ELT (basic_block
, body
, i
, bb
)
599 if (bb
!= entry_bb
&& bb
!= exit_bb
)
600 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
601 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
602 has_debug_stmt
= true;
604 eliminate_local_variables_stmt (entry
, &gsi
, decl_address
);
607 FOR_EACH_VEC_ELT (basic_block
, body
, i
, bb
)
608 if (bb
!= entry_bb
&& bb
!= exit_bb
)
609 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
610 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
611 eliminate_local_variables_stmt (entry
, &gsi
, decl_address
);
613 htab_delete (decl_address
);
614 VEC_free (basic_block
, heap
, body
);
617 /* Returns true if expression EXPR is not defined between ENTRY and
618 EXIT, i.e. if all its operands are defined outside of the region. */
621 expr_invariant_in_region_p (edge entry
, edge exit
, tree expr
)
623 basic_block entry_bb
= entry
->src
;
624 basic_block exit_bb
= exit
->dest
;
627 if (is_gimple_min_invariant (expr
))
630 if (TREE_CODE (expr
) == SSA_NAME
)
632 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
634 && dominated_by_p (CDI_DOMINATORS
, def_bb
, entry_bb
)
635 && !dominated_by_p (CDI_DOMINATORS
, def_bb
, exit_bb
))
644 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
645 The copies are stored to NAME_COPIES, if NAME was already duplicated,
646 its duplicate stored in NAME_COPIES is returned.
648 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
649 duplicated, storing the copies in DECL_COPIES. */
652 separate_decls_in_region_name (tree name
,
653 htab_t name_copies
, htab_t decl_copies
,
656 tree copy
, var
, var_copy
;
657 unsigned idx
, uid
, nuid
;
658 struct int_tree_map ielt
, *nielt
;
659 struct name_to_copy_elt elt
, *nelt
;
660 void **slot
, **dslot
;
662 if (TREE_CODE (name
) != SSA_NAME
)
665 idx
= SSA_NAME_VERSION (name
);
667 slot
= htab_find_slot_with_hash (name_copies
, &elt
, idx
,
668 copy_name_p
? INSERT
: NO_INSERT
);
670 return ((struct name_to_copy_elt
*) *slot
)->new_name
;
672 var
= SSA_NAME_VAR (name
);
673 uid
= DECL_UID (var
);
675 dslot
= htab_find_slot_with_hash (decl_copies
, &ielt
, uid
, INSERT
);
678 var_copy
= create_tmp_var (TREE_TYPE (var
), get_name (var
));
679 DECL_GIMPLE_REG_P (var_copy
) = DECL_GIMPLE_REG_P (var
);
680 add_referenced_var (var_copy
);
681 nielt
= XNEW (struct int_tree_map
);
683 nielt
->to
= var_copy
;
686 /* Ensure that when we meet this decl next time, we won't duplicate
688 nuid
= DECL_UID (var_copy
);
690 dslot
= htab_find_slot_with_hash (decl_copies
, &ielt
, nuid
, INSERT
);
691 gcc_assert (!*dslot
);
692 nielt
= XNEW (struct int_tree_map
);
694 nielt
->to
= var_copy
;
698 var_copy
= ((struct int_tree_map
*) *dslot
)->to
;
702 copy
= duplicate_ssa_name (name
, NULL
);
703 nelt
= XNEW (struct name_to_copy_elt
);
705 nelt
->new_name
= copy
;
706 nelt
->field
= NULL_TREE
;
715 SSA_NAME_VAR (copy
) = var_copy
;
719 /* Finds the ssa names used in STMT that are defined outside the
720 region between ENTRY and EXIT and replaces such ssa names with
721 their duplicates. The duplicates are stored to NAME_COPIES. Base
722 decls of all ssa names used in STMT (including those defined in
723 LOOP) are replaced with the new temporary variables; the
724 replacement decls are stored in DECL_COPIES. */
727 separate_decls_in_region_stmt (edge entry
, edge exit
, gimple stmt
,
728 htab_t name_copies
, htab_t decl_copies
)
736 mark_virtual_ops_for_renaming (stmt
);
738 FOR_EACH_PHI_OR_STMT_DEF (def
, stmt
, oi
, SSA_OP_DEF
)
740 name
= DEF_FROM_PTR (def
);
741 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
742 copy
= separate_decls_in_region_name (name
, name_copies
, decl_copies
,
744 gcc_assert (copy
== name
);
747 FOR_EACH_PHI_OR_STMT_USE (use
, stmt
, oi
, SSA_OP_USE
)
749 name
= USE_FROM_PTR (use
);
750 if (TREE_CODE (name
) != SSA_NAME
)
753 copy_name_p
= expr_invariant_in_region_p (entry
, exit
, name
);
754 copy
= separate_decls_in_region_name (name
, name_copies
, decl_copies
,
760 /* Finds the ssa names used in STMT that are defined outside the
761 region between ENTRY and EXIT and replaces such ssa names with
762 their duplicates. The duplicates are stored to NAME_COPIES. Base
763 decls of all ssa names used in STMT (including those defined in
764 LOOP) are replaced with the new temporary variables; the
765 replacement decls are stored in DECL_COPIES. */
768 separate_decls_in_region_debug_bind (gimple stmt
,
769 htab_t name_copies
, htab_t decl_copies
)
774 struct int_tree_map ielt
;
775 struct name_to_copy_elt elt
;
776 void **slot
, **dslot
;
778 var
= gimple_debug_bind_get_var (stmt
);
779 if (TREE_CODE (var
) == DEBUG_EXPR_DECL
)
781 gcc_assert (DECL_P (var
) && SSA_VAR_P (var
));
782 ielt
.uid
= DECL_UID (var
);
783 dslot
= htab_find_slot_with_hash (decl_copies
, &ielt
, ielt
.uid
, NO_INSERT
);
786 gimple_debug_bind_set_var (stmt
, ((struct int_tree_map
*) *dslot
)->to
);
788 FOR_EACH_PHI_OR_STMT_USE (use
, stmt
, oi
, SSA_OP_USE
)
790 name
= USE_FROM_PTR (use
);
791 if (TREE_CODE (name
) != SSA_NAME
)
794 elt
.version
= SSA_NAME_VERSION (name
);
795 slot
= htab_find_slot_with_hash (name_copies
, &elt
, elt
.version
, NO_INSERT
);
798 gimple_debug_bind_reset_value (stmt
);
803 SET_USE (use
, ((struct name_to_copy_elt
*) *slot
)->new_name
);
809 /* Callback for htab_traverse. Adds a field corresponding to the reduction
810 specified in SLOT. The type is passed in DATA. */
813 add_field_for_reduction (void **slot
, void *data
)
816 struct reduction_info
*const red
= (struct reduction_info
*) *slot
;
817 tree
const type
= (tree
) data
;
818 tree var
= SSA_NAME_VAR (gimple_assign_lhs (red
->reduc_stmt
));
819 tree field
= build_decl (gimple_location (red
->reduc_stmt
),
820 FIELD_DECL
, DECL_NAME (var
), TREE_TYPE (var
));
822 insert_field_into_struct (type
, field
);
829 /* Callback for htab_traverse. Adds a field corresponding to a ssa name
830 described in SLOT. The type is passed in DATA. */
833 add_field_for_name (void **slot
, void *data
)
835 struct name_to_copy_elt
*const elt
= (struct name_to_copy_elt
*) *slot
;
836 tree type
= (tree
) data
;
837 tree name
= ssa_name (elt
->version
);
838 tree var
= SSA_NAME_VAR (name
);
839 tree field
= build_decl (DECL_SOURCE_LOCATION (var
),
840 FIELD_DECL
, DECL_NAME (var
), TREE_TYPE (var
));
842 insert_field_into_struct (type
, field
);
848 /* Callback for htab_traverse. A local result is the intermediate result
850 thread, or the initial value in case no iteration was executed.
851 This function creates a phi node reflecting these values.
852 The phi's result will be stored in NEW_PHI field of the
853 reduction's data structure. */
856 create_phi_for_local_result (void **slot
, void *data
)
858 struct reduction_info
*const reduc
= (struct reduction_info
*) *slot
;
859 const struct loop
*const loop
= (const struct loop
*) data
;
862 basic_block store_bb
;
864 source_location locus
;
866 /* STORE_BB is the block where the phi
867 should be stored. It is the destination of the loop exit.
868 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
869 store_bb
= FALLTHRU_EDGE (loop
->latch
)->dest
;
871 /* STORE_BB has two predecessors. One coming from the loop
872 (the reduction's result is computed at the loop),
873 and another coming from a block preceding the loop,
875 are executed (the initial value should be taken). */
876 if (EDGE_PRED (store_bb
, 0) == FALLTHRU_EDGE (loop
->latch
))
877 e
= EDGE_PRED (store_bb
, 1);
879 e
= EDGE_PRED (store_bb
, 0);
881 = make_ssa_name (SSA_NAME_VAR (gimple_assign_lhs (reduc
->reduc_stmt
)),
883 locus
= gimple_location (reduc
->reduc_stmt
);
884 new_phi
= create_phi_node (local_res
, store_bb
);
885 SSA_NAME_DEF_STMT (local_res
) = new_phi
;
886 add_phi_arg (new_phi
, reduc
->init
, e
, locus
);
887 add_phi_arg (new_phi
, gimple_assign_lhs (reduc
->reduc_stmt
),
888 FALLTHRU_EDGE (loop
->latch
), locus
);
889 reduc
->new_phi
= new_phi
;
899 basic_block store_bb
;
903 /* Callback for htab_traverse. Create an atomic instruction for the
904 reduction described in SLOT.
905 DATA annotates the place in memory the atomic operation relates to,
906 and the basic block it needs to be generated in. */
909 create_call_for_reduction_1 (void **slot
, void *data
)
911 struct reduction_info
*const reduc
= (struct reduction_info
*) *slot
;
912 struct clsn_data
*const clsn_data
= (struct clsn_data
*) data
;
913 gimple_stmt_iterator gsi
;
914 tree type
= TREE_TYPE (PHI_RESULT (reduc
->reduc_phi
));
919 tree t
, addr
, ref
, x
;
923 load_struct
= build_simple_mem_ref (clsn_data
->load
);
924 t
= build3 (COMPONENT_REF
, type
, load_struct
, reduc
->field
, NULL_TREE
);
926 addr
= build_addr (t
, current_function_decl
);
928 /* Create phi node. */
929 bb
= clsn_data
->load_bb
;
931 e
= split_block (bb
, t
);
934 tmp_load
= create_tmp_var (TREE_TYPE (TREE_TYPE (addr
)), NULL
);
935 add_referenced_var (tmp_load
);
936 tmp_load
= make_ssa_name (tmp_load
, NULL
);
937 load
= gimple_build_omp_atomic_load (tmp_load
, addr
);
938 SSA_NAME_DEF_STMT (tmp_load
) = load
;
939 gsi
= gsi_start_bb (new_bb
);
940 gsi_insert_after (&gsi
, load
, GSI_NEW_STMT
);
942 e
= split_block (new_bb
, load
);
944 gsi
= gsi_start_bb (new_bb
);
946 x
= fold_build2 (reduc
->reduction_code
,
947 TREE_TYPE (PHI_RESULT (reduc
->new_phi
)), ref
,
948 PHI_RESULT (reduc
->new_phi
));
950 name
= force_gimple_operand_gsi (&gsi
, x
, true, NULL_TREE
, true,
951 GSI_CONTINUE_LINKING
);
953 gsi_insert_after (&gsi
, gimple_build_omp_atomic_store (name
), GSI_NEW_STMT
);
957 /* Create the atomic operation at the join point of the threads.
958 REDUCTION_LIST describes the reductions in the LOOP.
959 LD_ST_DATA describes the shared data structure where
960 shared data is stored in and loaded from. */
962 create_call_for_reduction (struct loop
*loop
, htab_t reduction_list
,
963 struct clsn_data
*ld_st_data
)
965 htab_traverse (reduction_list
, create_phi_for_local_result
, loop
);
966 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
967 ld_st_data
->load_bb
= FALLTHRU_EDGE (loop
->latch
)->dest
;
968 htab_traverse (reduction_list
, create_call_for_reduction_1
, ld_st_data
);
971 /* Callback for htab_traverse. Loads the final reduction value at the
972 join point of all threads, and inserts it in the right place. */
975 create_loads_for_reductions (void **slot
, void *data
)
977 struct reduction_info
*const red
= (struct reduction_info
*) *slot
;
978 struct clsn_data
*const clsn_data
= (struct clsn_data
*) data
;
980 gimple_stmt_iterator gsi
;
981 tree type
= TREE_TYPE (gimple_assign_lhs (red
->reduc_stmt
));
986 gsi
= gsi_after_labels (clsn_data
->load_bb
);
987 load_struct
= build_simple_mem_ref (clsn_data
->load
);
988 load_struct
= build3 (COMPONENT_REF
, type
, load_struct
, red
->field
,
992 name
= PHI_RESULT (red
->keep_res
);
993 stmt
= gimple_build_assign (name
, x
);
994 SSA_NAME_DEF_STMT (name
) = stmt
;
996 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
998 for (gsi
= gsi_start_phis (gimple_bb (red
->keep_res
));
999 !gsi_end_p (gsi
); gsi_next (&gsi
))
1000 if (gsi_stmt (gsi
) == red
->keep_res
)
1002 remove_phi_node (&gsi
, false);
1008 /* Load the reduction result that was stored in LD_ST_DATA.
1009 REDUCTION_LIST describes the list of reductions that the
1010 loads should be generated for. */
1012 create_final_loads_for_reduction (htab_t reduction_list
,
1013 struct clsn_data
*ld_st_data
)
1015 gimple_stmt_iterator gsi
;
1019 gsi
= gsi_after_labels (ld_st_data
->load_bb
);
1020 t
= build_fold_addr_expr (ld_st_data
->store
);
1021 stmt
= gimple_build_assign (ld_st_data
->load
, t
);
1023 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1024 SSA_NAME_DEF_STMT (ld_st_data
->load
) = stmt
;
1026 htab_traverse (reduction_list
, create_loads_for_reductions
, ld_st_data
);
1030 /* Callback for htab_traverse. Store the neutral value for the
1031 particular reduction's operation, e.g. 0 for PLUS_EXPR,
1032 1 for MULT_EXPR, etc. into the reduction field.
1033 The reduction is specified in SLOT. The store information is
1037 create_stores_for_reduction (void **slot
, void *data
)
1039 struct reduction_info
*const red
= (struct reduction_info
*) *slot
;
1040 struct clsn_data
*const clsn_data
= (struct clsn_data
*) data
;
1043 gimple_stmt_iterator gsi
;
1044 tree type
= TREE_TYPE (gimple_assign_lhs (red
->reduc_stmt
));
1046 gsi
= gsi_last_bb (clsn_data
->store_bb
);
1047 t
= build3 (COMPONENT_REF
, type
, clsn_data
->store
, red
->field
, NULL_TREE
);
1048 stmt
= gimple_build_assign (t
, red
->initial_value
);
1049 mark_virtual_ops_for_renaming (stmt
);
1050 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1055 /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
1056 store to a field of STORE in STORE_BB for the ssa name and its duplicate
1057 specified in SLOT. */
1060 create_loads_and_stores_for_name (void **slot
, void *data
)
1062 struct name_to_copy_elt
*const elt
= (struct name_to_copy_elt
*) *slot
;
1063 struct clsn_data
*const clsn_data
= (struct clsn_data
*) data
;
1066 gimple_stmt_iterator gsi
;
1067 tree type
= TREE_TYPE (elt
->new_name
);
1070 gsi
= gsi_last_bb (clsn_data
->store_bb
);
1071 t
= build3 (COMPONENT_REF
, type
, clsn_data
->store
, elt
->field
, NULL_TREE
);
1072 stmt
= gimple_build_assign (t
, ssa_name (elt
->version
));
1073 mark_virtual_ops_for_renaming (stmt
);
1074 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1076 gsi
= gsi_last_bb (clsn_data
->load_bb
);
1077 load_struct
= build_simple_mem_ref (clsn_data
->load
);
1078 t
= build3 (COMPONENT_REF
, type
, load_struct
, elt
->field
, NULL_TREE
);
1079 stmt
= gimple_build_assign (elt
->new_name
, t
);
1080 SSA_NAME_DEF_STMT (elt
->new_name
) = stmt
;
1081 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1086 /* Moves all the variables used in LOOP and defined outside of it (including
1087 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1088 name) to a structure created for this purpose. The code
1096 is transformed this way:
1111 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1112 pointer `new' is intentionally not initialized (the loop will be split to a
1113 separate function later, and `new' will be initialized from its arguments).
1114 LD_ST_DATA holds information about the shared data structure used to pass
1115 information among the threads. It is initialized here, and
1116 gen_parallel_loop will pass it to create_call_for_reduction that
1117 needs this information. REDUCTION_LIST describes the reductions
1121 separate_decls_in_region (edge entry
, edge exit
, htab_t reduction_list
,
1122 tree
*arg_struct
, tree
*new_arg_struct
,
1123 struct clsn_data
*ld_st_data
)
1126 basic_block bb1
= split_edge (entry
);
1127 basic_block bb0
= single_pred (bb1
);
1128 htab_t name_copies
= htab_create (10, name_to_copy_elt_hash
,
1129 name_to_copy_elt_eq
, free
);
1130 htab_t decl_copies
= htab_create (10, int_tree_map_hash
, int_tree_map_eq
,
1133 tree type
, type_name
, nvar
;
1134 gimple_stmt_iterator gsi
;
1135 struct clsn_data clsn_data
;
1136 VEC (basic_block
, heap
) *body
= VEC_alloc (basic_block
, heap
, 3);
1138 basic_block entry_bb
= bb1
;
1139 basic_block exit_bb
= exit
->dest
;
1140 bool has_debug_stmt
= false;
1142 entry
= single_succ_edge (entry_bb
);
1143 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
1145 FOR_EACH_VEC_ELT (basic_block
, body
, i
, bb
)
1147 if (bb
!= entry_bb
&& bb
!= exit_bb
)
1149 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1150 separate_decls_in_region_stmt (entry
, exit
, gsi_stmt (gsi
),
1151 name_copies
, decl_copies
);
1153 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1155 gimple stmt
= gsi_stmt (gsi
);
1157 if (is_gimple_debug (stmt
))
1158 has_debug_stmt
= true;
1160 separate_decls_in_region_stmt (entry
, exit
, stmt
,
1161 name_copies
, decl_copies
);
1166 /* Now process debug bind stmts. We must not create decls while
1167 processing debug stmts, so we defer their processing so as to
1168 make sure we will have debug info for as many variables as
1169 possible (all of those that were dealt with in the loop above),
1170 and discard those for which we know there's nothing we can
1173 FOR_EACH_VEC_ELT (basic_block
, body
, i
, bb
)
1174 if (bb
!= entry_bb
&& bb
!= exit_bb
)
1176 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
1178 gimple stmt
= gsi_stmt (gsi
);
1180 if (gimple_debug_bind_p (stmt
))
1182 if (separate_decls_in_region_debug_bind (stmt
,
1186 gsi_remove (&gsi
, true);
1195 VEC_free (basic_block
, heap
, body
);
1197 if (htab_elements (name_copies
) == 0 && htab_elements (reduction_list
) == 0)
1199 /* It may happen that there is nothing to copy (if there are only
1200 loop carried and external variables in the loop). */
1202 *new_arg_struct
= NULL
;
1206 /* Create the type for the structure to store the ssa names to. */
1207 type
= lang_hooks
.types
.make_type (RECORD_TYPE
);
1208 type_name
= build_decl (UNKNOWN_LOCATION
,
1209 TYPE_DECL
, create_tmp_var_name (".paral_data"),
1211 TYPE_NAME (type
) = type_name
;
1213 htab_traverse (name_copies
, add_field_for_name
, type
);
1214 if (reduction_list
&& htab_elements (reduction_list
) > 0)
1216 /* Create the fields for reductions. */
1217 htab_traverse (reduction_list
, add_field_for_reduction
,
1222 /* Create the loads and stores. */
1223 *arg_struct
= create_tmp_var (type
, ".paral_data_store");
1224 add_referenced_var (*arg_struct
);
1225 nvar
= create_tmp_var (build_pointer_type (type
), ".paral_data_load");
1226 add_referenced_var (nvar
);
1227 *new_arg_struct
= make_ssa_name (nvar
, NULL
);
1229 ld_st_data
->store
= *arg_struct
;
1230 ld_st_data
->load
= *new_arg_struct
;
1231 ld_st_data
->store_bb
= bb0
;
1232 ld_st_data
->load_bb
= bb1
;
1234 htab_traverse (name_copies
, create_loads_and_stores_for_name
,
1237 /* Load the calculation from memory (after the join of the threads). */
1239 if (reduction_list
&& htab_elements (reduction_list
) > 0)
1241 htab_traverse (reduction_list
, create_stores_for_reduction
,
1243 clsn_data
.load
= make_ssa_name (nvar
, NULL
);
1244 clsn_data
.load_bb
= exit
->dest
;
1245 clsn_data
.store
= ld_st_data
->store
;
1246 create_final_loads_for_reduction (reduction_list
, &clsn_data
);
1250 htab_delete (decl_copies
);
1251 htab_delete (name_copies
);
1254 /* Bitmap containing uids of functions created by parallelization. We cannot
1255 allocate it from the default obstack, as it must live across compilation
1256 of several functions; we make it gc allocated instead. */
1258 static GTY(()) bitmap parallelized_functions
;
1260 /* Returns true if FN was created by create_loop_fn. */
1263 parallelized_function_p (tree fn
)
1265 if (!parallelized_functions
|| !DECL_ARTIFICIAL (fn
))
1268 return bitmap_bit_p (parallelized_functions
, DECL_UID (fn
));
1271 /* Creates and returns an empty function that will receive the body of
1272 a parallelized loop. */
1275 create_loop_fn (location_t loc
)
1279 tree decl
, type
, name
, t
;
1280 struct function
*act_cfun
= cfun
;
1281 static unsigned loopfn_num
;
1283 snprintf (buf
, 100, "%s.$loopfn", current_function_name ());
1284 ASM_FORMAT_PRIVATE_NAME (tname
, buf
, loopfn_num
++);
1285 clean_symbol_name (tname
);
1286 name
= get_identifier (tname
);
1287 type
= build_function_type_list (void_type_node
, ptr_type_node
, NULL_TREE
);
1289 decl
= build_decl (loc
, FUNCTION_DECL
, name
, type
);
1290 if (!parallelized_functions
)
1291 parallelized_functions
= BITMAP_GGC_ALLOC ();
1292 bitmap_set_bit (parallelized_functions
, DECL_UID (decl
));
1294 TREE_STATIC (decl
) = 1;
1295 TREE_USED (decl
) = 1;
1296 DECL_ARTIFICIAL (decl
) = 1;
1297 DECL_IGNORED_P (decl
) = 0;
1298 TREE_PUBLIC (decl
) = 0;
1299 DECL_UNINLINABLE (decl
) = 1;
1300 DECL_EXTERNAL (decl
) = 0;
1301 DECL_CONTEXT (decl
) = NULL_TREE
;
1302 DECL_INITIAL (decl
) = make_node (BLOCK
);
1304 t
= build_decl (loc
, RESULT_DECL
, NULL_TREE
, void_type_node
);
1305 DECL_ARTIFICIAL (t
) = 1;
1306 DECL_IGNORED_P (t
) = 1;
1307 DECL_RESULT (decl
) = t
;
1309 t
= build_decl (loc
, PARM_DECL
, get_identifier (".paral_data_param"),
1311 DECL_ARTIFICIAL (t
) = 1;
1312 DECL_ARG_TYPE (t
) = ptr_type_node
;
1313 DECL_CONTEXT (t
) = decl
;
1315 DECL_ARGUMENTS (decl
) = t
;
1317 allocate_struct_function (decl
, false);
1319 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1321 set_cfun (act_cfun
);
1326 /* Moves the exit condition of LOOP to the beginning of its header, and
1327 duplicates the part of the last iteration that gets disabled to the
1328 exit of the loop. NIT is the number of iterations of the loop
1329 (used to initialize the variables in the duplicated part).
1331 TODO: the common case is that latch of the loop is empty and immediately
1332 follows the loop exit. In this case, it would be better not to copy the
1333 body of the loop, but only move the entry of the loop directly before the
1334 exit check and increase the number of iterations of the loop by one.
1335 This may need some additional preconditioning in case NIT = ~0.
1336 REDUCTION_LIST describes the reductions in LOOP. */
1339 transform_to_exit_first_loop (struct loop
*loop
, htab_t reduction_list
, tree nit
)
1341 basic_block
*bbs
, *nbbs
, ex_bb
, orig_header
;
1344 edge exit
= single_dom_exit (loop
), hpred
;
1345 tree control
, control_name
, res
, t
;
1346 gimple phi
, nphi
, cond_stmt
, stmt
, cond_nit
;
1347 gimple_stmt_iterator gsi
;
1350 split_block_after_labels (loop
->header
);
1351 orig_header
= single_succ (loop
->header
);
1352 hpred
= single_succ_edge (loop
->header
);
1354 cond_stmt
= last_stmt (exit
->src
);
1355 control
= gimple_cond_lhs (cond_stmt
);
1356 gcc_assert (gimple_cond_rhs (cond_stmt
) == nit
);
1358 /* Make sure that we have phi nodes on exit for all loop header phis
1359 (create_parallel_loop requires that). */
1360 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1362 phi
= gsi_stmt (gsi
);
1363 res
= PHI_RESULT (phi
);
1364 t
= make_ssa_name (SSA_NAME_VAR (res
), phi
);
1365 SET_PHI_RESULT (phi
, t
);
1366 nphi
= create_phi_node (res
, orig_header
);
1367 SSA_NAME_DEF_STMT (res
) = nphi
;
1368 add_phi_arg (nphi
, t
, hpred
, UNKNOWN_LOCATION
);
1372 gimple_cond_set_lhs (cond_stmt
, t
);
1373 update_stmt (cond_stmt
);
1377 bbs
= get_loop_body_in_dom_order (loop
);
1379 for (n
= 0; bbs
[n
] != loop
->latch
; n
++)
1381 nbbs
= XNEWVEC (basic_block
, n
);
1382 ok
= gimple_duplicate_sese_tail (single_succ_edge (loop
->header
), exit
,
1389 /* Other than reductions, the only gimple reg that should be copied
1390 out of the loop is the control variable. */
1392 control_name
= NULL_TREE
;
1393 for (gsi
= gsi_start_phis (ex_bb
); !gsi_end_p (gsi
); )
1395 phi
= gsi_stmt (gsi
);
1396 res
= PHI_RESULT (phi
);
1397 if (!is_gimple_reg (res
))
1403 /* Check if it is a part of reduction. If it is,
1404 keep the phi at the reduction's keep_res field. The
1405 PHI_RESULT of this phi is the resulting value of the reduction
1406 variable when exiting the loop. */
1408 exit
= single_dom_exit (loop
);
1410 if (htab_elements (reduction_list
) > 0)
1412 struct reduction_info
*red
;
1414 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1415 red
= reduction_phi (reduction_list
, SSA_NAME_DEF_STMT (val
));
1418 red
->keep_res
= phi
;
1423 gcc_assert (control_name
== NULL_TREE
1424 && SSA_NAME_VAR (res
) == SSA_NAME_VAR (control
));
1426 remove_phi_node (&gsi
, false);
1428 gcc_assert (control_name
!= NULL_TREE
);
1430 /* Initialize the control variable to number of iterations
1431 according to the rhs of the exit condition. */
1432 gsi
= gsi_after_labels (ex_bb
);
1433 cond_nit
= last_stmt (exit
->src
);
1434 nit_1
= gimple_cond_rhs (cond_nit
);
1435 nit_1
= force_gimple_operand_gsi (&gsi
,
1436 fold_convert (TREE_TYPE (control_name
), nit_1
),
1437 false, NULL_TREE
, false, GSI_SAME_STMT
);
1438 stmt
= gimple_build_assign (control_name
, nit_1
);
1439 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1440 SSA_NAME_DEF_STMT (control_name
) = stmt
;
1443 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
1444 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
1445 NEW_DATA is the variable that should be initialized from the argument
1446 of LOOP_FN. N_THREADS is the requested number of threads. Returns the
1447 basic block containing GIMPLE_OMP_PARALLEL tree. */
1450 create_parallel_loop (struct loop
*loop
, tree loop_fn
, tree data
,
1451 tree new_data
, unsigned n_threads
, location_t loc
)
1453 gimple_stmt_iterator gsi
;
1454 basic_block bb
, paral_bb
, for_bb
, ex_bb
;
1456 gimple stmt
, for_stmt
, phi
, cond_stmt
;
1457 tree cvar
, cvar_init
, initvar
, cvar_next
, cvar_base
, type
;
1458 edge exit
, nexit
, guard
, end
, e
;
1460 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
1461 bb
= loop_preheader_edge (loop
)->src
;
1462 paral_bb
= single_pred (bb
);
1463 gsi
= gsi_last_bb (paral_bb
);
1465 t
= build_omp_clause (loc
, OMP_CLAUSE_NUM_THREADS
);
1466 OMP_CLAUSE_NUM_THREADS_EXPR (t
)
1467 = build_int_cst (integer_type_node
, n_threads
);
1468 stmt
= gimple_build_omp_parallel (NULL
, t
, loop_fn
, data
);
1469 gimple_set_location (stmt
, loc
);
1471 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1473 /* Initialize NEW_DATA. */
1476 gsi
= gsi_after_labels (bb
);
1478 param
= make_ssa_name (DECL_ARGUMENTS (loop_fn
), NULL
);
1479 stmt
= gimple_build_assign (param
, build_fold_addr_expr (data
));
1480 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1481 SSA_NAME_DEF_STMT (param
) = stmt
;
1483 stmt
= gimple_build_assign (new_data
,
1484 fold_convert (TREE_TYPE (new_data
), param
));
1485 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1486 SSA_NAME_DEF_STMT (new_data
) = stmt
;
1489 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
1490 bb
= split_loop_exit_edge (single_dom_exit (loop
));
1491 gsi
= gsi_last_bb (bb
);
1492 stmt
= gimple_build_omp_return (false);
1493 gimple_set_location (stmt
, loc
);
1494 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1496 /* Extract data for GIMPLE_OMP_FOR. */
1497 gcc_assert (loop
->header
== single_dom_exit (loop
)->src
);
1498 cond_stmt
= last_stmt (loop
->header
);
1500 cvar
= gimple_cond_lhs (cond_stmt
);
1501 cvar_base
= SSA_NAME_VAR (cvar
);
1502 phi
= SSA_NAME_DEF_STMT (cvar
);
1503 cvar_init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1504 initvar
= make_ssa_name (cvar_base
, NULL
);
1505 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, loop_preheader_edge (loop
)),
1507 cvar_next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
1509 gsi
= gsi_last_nondebug_bb (loop
->latch
);
1510 gcc_assert (gsi_stmt (gsi
) == SSA_NAME_DEF_STMT (cvar_next
));
1511 gsi_remove (&gsi
, true);
1514 for_bb
= split_edge (loop_preheader_edge (loop
));
1515 ex_bb
= split_loop_exit_edge (single_dom_exit (loop
));
1516 extract_true_false_edges_from_block (loop
->header
, &nexit
, &exit
);
1517 gcc_assert (exit
== single_dom_exit (loop
));
1519 guard
= make_edge (for_bb
, ex_bb
, 0);
1520 single_succ_edge (loop
->latch
)->flags
= 0;
1521 end
= make_edge (loop
->latch
, ex_bb
, EDGE_FALLTHRU
);
1522 for (gsi
= gsi_start_phis (ex_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1524 source_location locus
;
1526 phi
= gsi_stmt (gsi
);
1527 stmt
= SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi
, exit
));
1529 def
= PHI_ARG_DEF_FROM_EDGE (stmt
, loop_preheader_edge (loop
));
1530 locus
= gimple_phi_arg_location_from_edge (stmt
,
1531 loop_preheader_edge (loop
));
1532 add_phi_arg (phi
, def
, guard
, locus
);
1534 def
= PHI_ARG_DEF_FROM_EDGE (stmt
, loop_latch_edge (loop
));
1535 locus
= gimple_phi_arg_location_from_edge (stmt
, loop_latch_edge (loop
));
1536 add_phi_arg (phi
, def
, end
, locus
);
1538 e
= redirect_edge_and_branch (exit
, nexit
->dest
);
1539 PENDING_STMT (e
) = NULL
;
1541 /* Emit GIMPLE_OMP_FOR. */
1542 gimple_cond_set_lhs (cond_stmt
, cvar_base
);
1543 type
= TREE_TYPE (cvar
);
1544 t
= build_omp_clause (loc
, OMP_CLAUSE_SCHEDULE
);
1545 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_STATIC
;
1547 for_stmt
= gimple_build_omp_for (NULL
, t
, 1, NULL
);
1548 gimple_set_location (for_stmt
, loc
);
1549 gimple_omp_for_set_index (for_stmt
, 0, initvar
);
1550 gimple_omp_for_set_initial (for_stmt
, 0, cvar_init
);
1551 gimple_omp_for_set_final (for_stmt
, 0, gimple_cond_rhs (cond_stmt
));
1552 gimple_omp_for_set_cond (for_stmt
, 0, gimple_cond_code (cond_stmt
));
1553 gimple_omp_for_set_incr (for_stmt
, 0, build2 (PLUS_EXPR
, type
,
1555 build_int_cst (type
, 1)));
1557 gsi
= gsi_last_bb (for_bb
);
1558 gsi_insert_after (&gsi
, for_stmt
, GSI_NEW_STMT
);
1559 SSA_NAME_DEF_STMT (initvar
) = for_stmt
;
1561 /* Emit GIMPLE_OMP_CONTINUE. */
1562 gsi
= gsi_last_bb (loop
->latch
);
1563 stmt
= gimple_build_omp_continue (cvar_next
, cvar
);
1564 gimple_set_location (stmt
, loc
);
1565 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1566 SSA_NAME_DEF_STMT (cvar_next
) = stmt
;
1568 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
1569 gsi
= gsi_last_bb (ex_bb
);
1570 stmt
= gimple_build_omp_return (true);
1571 gimple_set_location (stmt
, loc
);
1572 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1577 /* Generates code to execute the iterations of LOOP in N_THREADS
1578 threads in parallel.
1580 NITER describes number of iterations of LOOP.
1581 REDUCTION_LIST describes the reductions existent in the LOOP. */
1584 gen_parallel_loop (struct loop
*loop
, htab_t reduction_list
,
1585 unsigned n_threads
, struct tree_niter_desc
*niter
)
1588 tree many_iterations_cond
, type
, nit
;
1589 tree arg_struct
, new_arg_struct
;
1591 basic_block parallel_head
;
1593 struct clsn_data clsn_data
;
1600 ---------------------------------------------------------------------
1603 IV = phi (INIT, IV + STEP)
1609 ---------------------------------------------------------------------
1611 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
1612 we generate the following code:
1614 ---------------------------------------------------------------------
1617 || NITER < MIN_PER_THREAD * N_THREADS)
1621 store all local loop-invariant variables used in body of the loop to DATA.
1622 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
1623 load the variables from DATA.
1624 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
1627 GIMPLE_OMP_CONTINUE;
1628 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
1629 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
1635 IV = phi (INIT, IV + STEP)
1646 /* Create two versions of the loop -- in the old one, we know that the
1647 number of iterations is large enough, and we will transform it into the
1648 loop that will be split to loop_fn, the new one will be used for the
1649 remaining iterations. */
1651 type
= TREE_TYPE (niter
->niter
);
1652 nit
= force_gimple_operand (unshare_expr (niter
->niter
), &stmts
, true,
1655 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1657 many_iterations_cond
=
1658 fold_build2 (GE_EXPR
, boolean_type_node
,
1659 nit
, build_int_cst (type
, MIN_PER_THREAD
* n_threads
));
1660 many_iterations_cond
1661 = fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1662 invert_truthvalue (unshare_expr (niter
->may_be_zero
)),
1663 many_iterations_cond
);
1664 many_iterations_cond
1665 = force_gimple_operand (many_iterations_cond
, &stmts
, false, NULL_TREE
);
1667 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1668 if (!is_gimple_condexpr (many_iterations_cond
))
1670 many_iterations_cond
1671 = force_gimple_operand (many_iterations_cond
, &stmts
,
1674 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1677 initialize_original_copy_tables ();
1679 /* We assume that the loop usually iterates a lot. */
1680 prob
= 4 * REG_BR_PROB_BASE
/ 5;
1681 loop_version (loop
, many_iterations_cond
, NULL
,
1682 prob
, prob
, REG_BR_PROB_BASE
- prob
, true);
1683 update_ssa (TODO_update_ssa
);
1684 free_original_copy_tables ();
1686 /* Base all the induction variables in LOOP on a single control one. */
1687 canonicalize_loop_ivs (loop
, &nit
, true);
1689 /* Ensure that the exit condition is the first statement in the loop. */
1690 transform_to_exit_first_loop (loop
, reduction_list
, nit
);
1692 /* Generate initializations for reductions. */
1693 if (htab_elements (reduction_list
) > 0)
1694 htab_traverse (reduction_list
, initialize_reductions
, loop
);
1696 /* Eliminate the references to local variables from the loop. */
1697 gcc_assert (single_exit (loop
));
1698 entry
= loop_preheader_edge (loop
);
1699 exit
= single_dom_exit (loop
);
1701 eliminate_local_variables (entry
, exit
);
1702 /* In the old loop, move all variables non-local to the loop to a structure
1703 and back, and create separate decls for the variables used in loop. */
1704 separate_decls_in_region (entry
, exit
, reduction_list
, &arg_struct
,
1705 &new_arg_struct
, &clsn_data
);
1707 /* Create the parallel constructs. */
1708 loc
= UNKNOWN_LOCATION
;
1709 cond_stmt
= last_stmt (loop
->header
);
1711 loc
= gimple_location (cond_stmt
);
1712 parallel_head
= create_parallel_loop (loop
, create_loop_fn (loc
), arg_struct
,
1713 new_arg_struct
, n_threads
, loc
);
1714 if (htab_elements (reduction_list
) > 0)
1715 create_call_for_reduction (loop
, reduction_list
, &clsn_data
);
1719 /* Cancel the loop (it is simpler to do it here rather than to teach the
1720 expander to do it). */
1721 cancel_loop_tree (loop
);
1723 /* Free loop bound estimations that could contain references to
1724 removed statements. */
1725 FOR_EACH_LOOP (li
, loop
, 0)
1726 free_numbers_of_iterations_estimates_loop (loop
);
1728 /* Expand the parallel constructs. We do it directly here instead of running
1729 a separate expand_omp pass, since it is more efficient, and less likely to
1730 cause troubles with further analyses not being able to deal with the
1733 omp_expand_local (parallel_head
);
1736 /* Returns true when LOOP contains vector phi nodes. */
1739 loop_has_vector_phi_nodes (struct loop
*loop ATTRIBUTE_UNUSED
)
1742 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
1743 gimple_stmt_iterator gsi
;
1746 for (i
= 0; i
< loop
->num_nodes
; i
++)
1747 for (gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
1748 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi_stmt (gsi
)))) == VECTOR_TYPE
)
1757 /* Create a reduction_info struct, initialize it with REDUC_STMT
1758 and PHI, insert it to the REDUCTION_LIST. */
1761 build_new_reduction (htab_t reduction_list
, gimple reduc_stmt
, gimple phi
)
1764 struct reduction_info
*new_reduction
;
1766 gcc_assert (reduc_stmt
);
1768 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1771 "Detected reduction. reduction stmt is: \n");
1772 print_gimple_stmt (dump_file
, reduc_stmt
, 0, 0);
1773 fprintf (dump_file
, "\n");
1776 new_reduction
= XCNEW (struct reduction_info
);
1778 new_reduction
->reduc_stmt
= reduc_stmt
;
1779 new_reduction
->reduc_phi
= phi
;
1780 new_reduction
->reduc_version
= SSA_NAME_VERSION (gimple_phi_result (phi
));
1781 new_reduction
->reduction_code
= gimple_assign_rhs_code (reduc_stmt
);
1782 slot
= htab_find_slot (reduction_list
, new_reduction
, INSERT
);
1783 *slot
= new_reduction
;
1786 /* Callback for htab_traverse. Sets gimple_uid of reduc_phi stmts. */
1789 set_reduc_phi_uids (void **slot
, void *data ATTRIBUTE_UNUSED
)
1791 struct reduction_info
*const red
= (struct reduction_info
*) *slot
;
1792 gimple_set_uid (red
->reduc_phi
, red
->reduc_version
);
1796 /* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
1799 gather_scalar_reductions (loop_p loop
, htab_t reduction_list
)
1801 gimple_stmt_iterator gsi
;
1802 loop_vec_info simple_loop_info
;
1805 simple_loop_info
= vect_analyze_loop_form (loop
);
1807 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1809 gimple phi
= gsi_stmt (gsi
);
1811 tree res
= PHI_RESULT (phi
);
1814 if (!is_gimple_reg (res
))
1817 if (!simple_iv (loop
, loop
, res
, &iv
, true)
1818 && simple_loop_info
)
1820 gimple reduc_stmt
= vect_force_simple_reduction (simple_loop_info
,
1823 if (reduc_stmt
&& !double_reduc
)
1824 build_new_reduction (reduction_list
, reduc_stmt
, phi
);
1827 destroy_loop_vec_info (simple_loop_info
, true);
1829 /* As gimple_uid is used by the vectorizer in between vect_analyze_loop_form
1830 and destroy_loop_vec_info, we can set gimple_uid of reduc_phi stmts
1832 htab_traverse (reduction_list
, set_reduc_phi_uids
, NULL
);
1835 /* Try to initialize NITER for code generation part. */
1838 try_get_loop_niter (loop_p loop
, struct tree_niter_desc
*niter
)
1840 edge exit
= single_dom_exit (loop
);
1844 /* We need to know # of iterations, and there should be no uses of values
1845 defined inside loop outside of it, unless the values are invariants of
1847 if (!number_of_iterations_exit (loop
, exit
, niter
, false))
1849 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1850 fprintf (dump_file
, " FAILED: number of iterations not known\n");
1857 /* Try to initialize REDUCTION_LIST for code generation part.
1858 REDUCTION_LIST describes the reductions. */
1861 try_create_reduction_list (loop_p loop
, htab_t reduction_list
)
1863 edge exit
= single_dom_exit (loop
);
1864 gimple_stmt_iterator gsi
;
1868 gather_scalar_reductions (loop
, reduction_list
);
1871 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1873 gimple phi
= gsi_stmt (gsi
);
1874 struct reduction_info
*red
;
1875 imm_use_iterator imm_iter
;
1876 use_operand_p use_p
;
1878 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1880 if (is_gimple_reg (val
))
1882 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1884 fprintf (dump_file
, "phi is ");
1885 print_gimple_stmt (dump_file
, phi
, 0, 0);
1886 fprintf (dump_file
, "arg of phi to exit: value ");
1887 print_generic_expr (dump_file
, val
, 0);
1888 fprintf (dump_file
, " used outside loop\n");
1890 " checking if it a part of reduction pattern: \n");
1892 if (htab_elements (reduction_list
) == 0)
1894 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1896 " FAILED: it is not a part of reduction.\n");
1900 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, val
)
1902 if (!gimple_debug_bind_p (USE_STMT (use_p
))
1903 && flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
1905 reduc_phi
= USE_STMT (use_p
);
1909 red
= reduction_phi (reduction_list
, reduc_phi
);
1912 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1914 " FAILED: it is not a part of reduction.\n");
1917 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1919 fprintf (dump_file
, "reduction phi is ");
1920 print_gimple_stmt (dump_file
, red
->reduc_phi
, 0, 0);
1921 fprintf (dump_file
, "reduction stmt is ");
1922 print_gimple_stmt (dump_file
, red
->reduc_stmt
, 0, 0);
1927 /* The iterations of the loop may communicate only through bivs whose
1928 iteration space can be distributed efficiently. */
1929 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1931 gimple phi
= gsi_stmt (gsi
);
1932 tree def
= PHI_RESULT (phi
);
1935 if (is_gimple_reg (def
) && !simple_iv (loop
, loop
, def
, &iv
, true))
1937 struct reduction_info
*red
;
1939 red
= reduction_phi (reduction_list
, phi
);
1942 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1944 " FAILED: scalar dependency between iterations\n");
1954 /* Detect parallel loops and generate parallel code using libgomp
1955 primitives. Returns true if some loop was parallelized, false
1959 parallelize_loops (void)
1961 unsigned n_threads
= flag_tree_parallelize_loops
;
1962 bool changed
= false;
1964 struct tree_niter_desc niter_desc
;
1966 htab_t reduction_list
;
1967 struct obstack parloop_obstack
;
1968 HOST_WIDE_INT estimated
;
1971 /* Do not parallelize loops in the functions created by parallelization. */
1972 if (parallelized_function_p (cfun
->decl
))
1974 if (cfun
->has_nonlocal_label
)
1977 gcc_obstack_init (&parloop_obstack
);
1978 reduction_list
= htab_create (10, reduction_info_hash
,
1979 reduction_info_eq
, free
);
1980 init_stmt_vec_info_vec ();
1982 FOR_EACH_LOOP (li
, loop
, 0)
1984 htab_empty (reduction_list
);
1985 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1987 fprintf (dump_file
, "Trying loop %d as candidate\n",loop
->num
);
1989 fprintf (dump_file
, "loop %d is not innermost\n",loop
->num
);
1991 fprintf (dump_file
, "loop %d is innermost\n",loop
->num
);
1994 /* If we use autopar in graphite pass, we use its marked dependency
1995 checking results. */
1996 if (flag_loop_parallelize_all
&& !loop
->can_be_parallel
)
1998 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1999 fprintf (dump_file
, "loop is not parallel according to graphite\n");
2003 if (!single_dom_exit (loop
))
2006 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2007 fprintf (dump_file
, "loop is !single_dom_exit\n");
2012 if (/* And of course, the loop must be parallelizable. */
2013 !can_duplicate_loop_p (loop
)
2014 || loop_has_blocks_with_irreducible_flag (loop
)
2015 || (loop_preheader_edge (loop
)->src
->flags
& BB_IRREDUCIBLE_LOOP
)
2016 /* FIXME: the check for vector phi nodes could be removed. */
2017 || loop_has_vector_phi_nodes (loop
))
2019 estimated
= estimated_loop_iterations_int (loop
, false);
2020 /* FIXME: Bypass this check as graphite doesn't update the
2021 count and frequency correctly now. */
2022 if (!flag_loop_parallelize_all
2024 && estimated
<= (HOST_WIDE_INT
) n_threads
* MIN_PER_THREAD
)
2025 /* Do not bother with loops in cold areas. */
2026 || optimize_loop_nest_for_size_p (loop
)))
2029 if (!try_get_loop_niter (loop
, &niter_desc
))
2032 if (!try_create_reduction_list (loop
, reduction_list
))
2035 if (!flag_loop_parallelize_all
2036 && !loop_parallel_p (loop
, &parloop_obstack
))
2040 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2043 fprintf (dump_file
, "parallelizing outer loop %d\n",loop
->header
->index
);
2045 fprintf (dump_file
, "parallelizing inner loop %d\n",loop
->header
->index
);
2046 loop_loc
= find_loop_location (loop
);
2047 if (loop_loc
!= UNKNOWN_LOC
)
2048 fprintf (dump_file
, "\nloop at %s:%d: ",
2049 LOC_FILE (loop_loc
), LOC_LINE (loop_loc
));
2051 gen_parallel_loop (loop
, reduction_list
,
2052 n_threads
, &niter_desc
);
2053 verify_flow_info ();
2054 verify_dominators (CDI_DOMINATORS
);
2055 verify_loop_structure ();
2056 verify_loop_closed_ssa (true);
2059 free_stmt_vec_info_vec ();
2060 htab_delete (reduction_list
);
2061 obstack_free (&parloop_obstack
, NULL
);
2063 /* Parallelization will cause new function calls to be inserted through
2064 which local variables will escape. Reset the points-to solution
2067 pt_solution_reset (&cfun
->gimple_df
->escaped
);
2072 #include "gt-tree-parloops.h"