1 /* Loop autoparallelization.
2 Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr> and
4 Zdenek Dvorak <dvorakz@suse.cz>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
25 #include "coretypes.h"
29 #include "tree-flow.h"
32 #include "tree-data-ref.h"
33 #include "diagnostic.h"
34 #include "tree-pass.h"
35 #include "tree-scalar-evolution.h"
37 #include "langhooks.h"
38 #include "tree-vectorizer.h"
40 /* This pass tries to distribute iterations of loops into several threads.
41 The implementation is straightforward -- for each loop we test whether its
42 iterations are independent, and if it is the case (and some additional
43 conditions regarding profitability and correctness are satisfied), we
44 add GIMPLE_OMP_PARALLEL and GIMPLE_OMP_FOR codes and let omp expansion
47 The most of the complexity is in bringing the code into shape expected
49 -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction
50 variable and that the exit test is at the start of the loop body
51 -- for GIMPLE_OMP_PARALLEL, replacing the references to local addressable
52 variables by accesses through pointers, and breaking up ssa chains
53 by storing the values incoming to the parallelized loop to a structure
54 passed to the new function as an argument (something similar is done
55 in omp gimplification, unfortunately only a small part of the code
59 -- if there are several parallelizable loops in a function, it may be
60 possible to generate the threads just once (using synchronization to
61 ensure that cross-loop dependences are obeyed).
62 -- handling of common scalar dependence patterns (accumulation, ...)
63 -- handling of non-innermost loops */
67 currently we use vect_is_simple_reduction() to detect reduction patterns.
68 The code transformation will be introduced by an example.
75 for (i = 0; i < N; i++)
85 # sum_29 = PHI <sum_11(5), 1(3)>
86 # i_28 = PHI <i_12(5), 0(3)>
89 sum_11 = D.1795_8 + sum_29;
97 # sum_21 = PHI <sum_11(4)>
98 printf (&"%d"[0], sum_21);
101 after reduction transformation (only relevant parts):
109 # Storing the initial value given by the user. #
111 .paral_data_store.32.sum.27 = 1;
113 #pragma omp parallel num_threads(4)
115 #pragma omp for schedule(static)
117 # The neutral element corresponding to the particular
118 reduction's operation, e.g. 0 for PLUS_EXPR,
119 1 for MULT_EXPR, etc. replaces the user's initial value. #
121 # sum.27_29 = PHI <sum.27_11, 0>
123 sum.27_11 = D.1827_8 + sum.27_29;
127 # Adding this reduction phi is done at create_phi_for_local_result() #
128 # sum.27_56 = PHI <sum.27_11, 0>
131 # Creating the atomic operation is done at
132 create_call_for_reduction_1() #
134 #pragma omp atomic_load
135 D.1839_59 = *&.paral_data_load.33_51->reduction.23;
136 D.1840_60 = sum.27_56 + D.1839_59;
137 #pragma omp atomic_store (D.1840_60);
141 # collecting the result after the join of the threads is done at
142 create_loads_for_reductions().
143 The value computed by the threads is loaded from the
147 .paral_data_load.33_52 = &.paral_data_store.32;
148 sum_37 = .paral_data_load.33_52->sum.27;
149 sum_43 = D.1795_41 + sum_37;
152 # sum_21 = PHI <sum_43, sum_26>
153 printf (&"%d"[0], sum_21);
161 /* Minimal number of iterations of a loop that should be executed in each
163 #define MIN_PER_THREAD 100
165 /* Element of the hashtable, representing a
166 reduction in the current loop. */
167 struct reduction_info
169 gimple reduc_stmt
; /* reduction statement. */
170 gimple reduc_phi
; /* The phi node defining the reduction. */
171 enum tree_code reduction_code
;/* code for the reduction operation. */
172 gimple keep_res
; /* The PHI_RESULT of this phi is the resulting value
173 of the reduction variable when existing the loop. */
174 tree initial_value
; /* The initial value of the reduction var before entering the loop. */
175 tree field
; /* the name of the field in the parloop data structure intended for reduction. */
176 tree init
; /* reduction initialization value. */
177 gimple new_phi
; /* (helper field) Newly created phi node whose result
178 will be passed to the atomic operation. Represents
179 the local result each thread computed for the reduction
183 /* Equality and hash functions for hashtab code. */
186 reduction_info_eq (const void *aa
, const void *bb
)
188 const struct reduction_info
*a
= (const struct reduction_info
*) aa
;
189 const struct reduction_info
*b
= (const struct reduction_info
*) bb
;
191 return (a
->reduc_phi
== b
->reduc_phi
);
195 reduction_info_hash (const void *aa
)
197 const struct reduction_info
*a
= (const struct reduction_info
*) aa
;
199 return htab_hash_pointer (a
->reduc_phi
);
202 static struct reduction_info
*
203 reduction_phi (htab_t reduction_list
, gimple phi
)
205 struct reduction_info tmpred
, *red
;
207 if (htab_elements (reduction_list
) == 0)
210 tmpred
.reduc_phi
= phi
;
211 red
= (struct reduction_info
*) htab_find (reduction_list
, &tmpred
);
216 /* Element of hashtable of names to copy. */
218 struct name_to_copy_elt
220 unsigned version
; /* The version of the name to copy. */
221 tree new_name
; /* The new name used in the copy. */
222 tree field
; /* The field of the structure used to pass the
226 /* Equality and hash functions for hashtab code. */
229 name_to_copy_elt_eq (const void *aa
, const void *bb
)
231 const struct name_to_copy_elt
*a
= (const struct name_to_copy_elt
*) aa
;
232 const struct name_to_copy_elt
*b
= (const struct name_to_copy_elt
*) bb
;
234 return a
->version
== b
->version
;
238 name_to_copy_elt_hash (const void *aa
)
240 const struct name_to_copy_elt
*a
= (const struct name_to_copy_elt
*) aa
;
242 return (hashval_t
) a
->version
;
245 /* Returns true if the iterations of LOOP are independent on each other (that
246 is, if we can execute them in parallel), and if LOOP satisfies other
247 conditions that we need to be able to parallelize it. Description of number
248 of iterations is stored to NITER. Reduction analysis is done, if
249 reductions are found, they are inserted to the REDUCTION_LIST. */
252 loop_parallel_p (struct loop
*loop
, htab_t reduction_list
,
253 struct tree_niter_desc
*niter
)
255 edge exit
= single_dom_exit (loop
);
256 VEC (ddr_p
, heap
) * dependence_relations
;
257 VEC (data_reference_p
, heap
) *datarefs
;
258 lambda_trans_matrix trans
;
260 gimple_stmt_iterator gsi
;
261 loop_vec_info simple_loop_info
;
263 /* Only consider innermost loops with just one exit. The innermost-loop
264 restriction is not necessary, but it makes things simpler. */
265 if (loop
->inner
|| !exit
)
268 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
269 fprintf (dump_file
, "\nConsidering loop %d\n", loop
->num
);
271 /* We need to know # of iterations, and there should be no uses of values
272 defined inside loop outside of it, unless the values are invariants of
274 if (!number_of_iterations_exit (loop
, exit
, niter
, false))
276 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
277 fprintf (dump_file
, " FAILED: number of iterations not known\n");
282 simple_loop_info
= vect_analyze_loop_form (loop
);
284 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
286 gimple phi
= gsi_stmt (gsi
);
287 gimple reduc_stmt
= NULL
;
289 /* ??? TODO: Change this into a generic function that
290 recognizes reductions. */
291 if (!is_gimple_reg (PHI_RESULT (phi
)))
293 if (simple_loop_info
)
294 reduc_stmt
= vect_is_simple_reduction (simple_loop_info
, phi
);
296 /* Create a reduction_info struct, initialize it and insert it to
297 the reduction list. */
302 struct reduction_info
*new_reduction
;
304 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
307 "Detected reduction. reduction stmt is: \n");
308 print_gimple_stmt (dump_file
, reduc_stmt
, 0, 0);
309 fprintf (dump_file
, "\n");
312 new_reduction
= XCNEW (struct reduction_info
);
314 new_reduction
->reduc_stmt
= reduc_stmt
;
315 new_reduction
->reduc_phi
= phi
;
316 new_reduction
->reduction_code
= gimple_assign_rhs_code (reduc_stmt
);
317 slot
= htab_find_slot (reduction_list
, new_reduction
, INSERT
);
318 *slot
= new_reduction
;
322 /* Get rid of the information created by the vectorizer functions. */
323 destroy_loop_vec_info (simple_loop_info
, true);
325 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
327 gimple phi
= gsi_stmt (gsi
);
328 struct reduction_info
*red
;
329 imm_use_iterator imm_iter
;
332 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
334 if (is_gimple_reg (val
))
336 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
338 fprintf (dump_file
, "phi is ");
339 print_gimple_stmt (dump_file
, phi
, 0, 0);
340 fprintf (dump_file
, "arg of phi to exit: value ");
341 print_generic_expr (dump_file
, val
, 0);
342 fprintf (dump_file
, " used outside loop\n");
344 " checking if it a part of reduction pattern: \n");
346 if (htab_elements (reduction_list
) == 0)
348 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
350 " FAILED: it is not a part of reduction.\n");
354 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, val
)
356 if (flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
358 reduc_phi
= USE_STMT (use_p
);
362 red
= reduction_phi (reduction_list
, reduc_phi
);
365 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
367 " FAILED: it is not a part of reduction.\n");
370 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
372 fprintf (dump_file
, "reduction phi is ");
373 print_gimple_stmt (dump_file
, red
->reduc_phi
, 0, 0);
374 fprintf (dump_file
, "reduction stmt is ");
375 print_gimple_stmt (dump_file
, red
->reduc_stmt
, 0, 0);
381 /* The iterations of the loop may communicate only through bivs whose
382 iteration space can be distributed efficiently. */
383 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
385 gimple phi
= gsi_stmt (gsi
);
386 tree def
= PHI_RESULT (phi
);
389 if (is_gimple_reg (def
) && !simple_iv (loop
, phi
, def
, &iv
, true))
391 struct reduction_info
*red
;
393 red
= reduction_phi (reduction_list
, phi
);
396 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
398 " FAILED: scalar dependency between iterations\n");
404 /* We need to version the loop to verify assumptions in runtime. */
405 if (!can_duplicate_loop_p (loop
))
407 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
408 fprintf (dump_file
, " FAILED: cannot be duplicated\n");
412 /* Check for problems with dependences. If the loop can be reversed,
413 the iterations are independent. */
414 datarefs
= VEC_alloc (data_reference_p
, heap
, 10);
415 dependence_relations
= VEC_alloc (ddr_p
, heap
, 10 * 10);
416 compute_data_dependences_for_loop (loop
, true, &datarefs
,
417 &dependence_relations
);
418 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
419 dump_data_dependence_relations (dump_file
, dependence_relations
);
421 trans
= lambda_trans_matrix_new (1, 1);
422 LTM_MATRIX (trans
)[0][0] = -1;
424 if (lambda_transform_legal_p (trans
, 1, dependence_relations
))
427 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
428 fprintf (dump_file
, " SUCCESS: may be parallelized\n");
430 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
432 " FAILED: data dependencies exist across iterations\n");
434 free_dependence_relations (dependence_relations
);
435 free_data_refs (datarefs
);
440 /* Return true when LOOP contains basic blocks marked with the
441 BB_IRREDUCIBLE_LOOP flag. */
444 loop_has_blocks_with_irreducible_flag (struct loop
*loop
)
447 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
450 for (i
= 0; i
< loop
->num_nodes
; i
++)
451 if (bbs
[i
]->flags
& BB_IRREDUCIBLE_LOOP
)
460 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
461 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
462 to their addresses that can be reused. The address of OBJ is known to
463 be invariant in the whole function. */
466 take_address_of (tree obj
, tree type
, edge entry
, htab_t decl_address
)
470 struct int_tree_map ielt
, *nielt
;
471 tree
*var_p
, name
, bvar
, addr
;
475 /* Since the address of OBJ is invariant, the trees may be shared.
476 Avoid rewriting unrelated parts of the code. */
477 obj
= unshare_expr (obj
);
479 handled_component_p (*var_p
);
480 var_p
= &TREE_OPERAND (*var_p
, 0))
482 uid
= DECL_UID (*var_p
);
485 dslot
= htab_find_slot_with_hash (decl_address
, &ielt
, uid
, INSERT
);
488 addr
= build_addr (*var_p
, current_function_decl
);
489 bvar
= create_tmp_var (TREE_TYPE (addr
), get_name (*var_p
));
490 add_referenced_var (bvar
);
491 stmt
= gimple_build_assign (bvar
, addr
);
492 name
= make_ssa_name (bvar
, stmt
);
493 gimple_assign_set_lhs (stmt
, name
);
494 gsi_insert_on_edge_immediate (entry
, stmt
);
496 nielt
= XNEW (struct int_tree_map
);
502 name
= ((struct int_tree_map
*) *dslot
)->to
;
506 *var_p
= build1 (INDIRECT_REF
, TREE_TYPE (*var_p
), name
);
507 name
= force_gimple_operand (build_addr (obj
, current_function_decl
),
508 &stmts
, true, NULL_TREE
);
509 if (!gimple_seq_empty_p (stmts
))
510 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
513 if (TREE_TYPE (name
) != type
)
515 name
= force_gimple_operand (fold_convert (type
, name
), &stmts
, true,
517 if (!gimple_seq_empty_p (stmts
))
518 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
524 /* Callback for htab_traverse. Create the initialization statement
525 for reduction described in SLOT, and place it at the preheader of
526 the loop described in DATA. */
529 initialize_reductions (void **slot
, void *data
)
532 tree bvar
, type
, arg
;
535 struct reduction_info
*const reduc
= (struct reduction_info
*) *slot
;
536 struct loop
*loop
= (struct loop
*) data
;
538 /* Create initialization in preheader:
539 reduction_variable = initialization value of reduction. */
541 /* In the phi node at the header, replace the argument coming
542 from the preheader with the reduction initialization value. */
544 /* Create a new variable to initialize the reduction. */
545 type
= TREE_TYPE (PHI_RESULT (reduc
->reduc_phi
));
546 bvar
= create_tmp_var (type
, "reduction");
547 add_referenced_var (bvar
);
549 c
= build_omp_clause (OMP_CLAUSE_REDUCTION
);
550 OMP_CLAUSE_REDUCTION_CODE (c
) = reduc
->reduction_code
;
551 OMP_CLAUSE_DECL (c
) = SSA_NAME_VAR (gimple_assign_lhs (reduc
->reduc_stmt
));
553 init
= omp_reduction_init (c
, TREE_TYPE (bvar
));
556 /* Replace the argument representing the initialization value
557 with the initialization value for the reduction (neutral
558 element for the particular operation, e.g. 0 for PLUS_EXPR,
559 1 for MULT_EXPR, etc).
560 Keep the old value in a new variable "reduction_initial",
561 that will be taken in consideration after the parallel
562 computing is done. */
564 e
= loop_preheader_edge (loop
);
565 arg
= PHI_ARG_DEF_FROM_EDGE (reduc
->reduc_phi
, e
);
566 /* Create new variable to hold the initial value. */
568 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
569 (reduc
->reduc_phi
, loop_preheader_edge (loop
)), init
);
570 reduc
->initial_value
= arg
;
576 struct walk_stmt_info info
;
582 /* Eliminates references to local variables in *TP out of the single
583 entry single exit region starting at DTA->ENTRY.
584 DECL_ADDRESS contains addresses of the references that had their
585 address taken already. If the expression is changed, CHANGED is
586 set to true. Callback for walk_tree. */
589 eliminate_local_variables_1 (tree
*tp
, int *walk_subtrees
, void *data
)
591 struct elv_data
*const dta
= (struct elv_data
*) data
;
592 tree t
= *tp
, var
, addr
, addr_type
, type
, obj
;
598 if (!SSA_VAR_P (t
) || DECL_EXTERNAL (t
))
601 type
= TREE_TYPE (t
);
602 addr_type
= build_pointer_type (type
);
603 addr
= take_address_of (t
, addr_type
, dta
->entry
, dta
->decl_address
);
604 *tp
= build1 (INDIRECT_REF
, TREE_TYPE (*tp
), addr
);
610 if (TREE_CODE (t
) == ADDR_EXPR
)
612 /* ADDR_EXPR may appear in two contexts:
613 -- as a gimple operand, when the address taken is a function invariant
614 -- as gimple rhs, when the resulting address in not a function
616 We do not need to do anything special in the latter case (the base of
617 the memory reference whose address is taken may be replaced in the
618 DECL_P case). The former case is more complicated, as we need to
619 ensure that the new address is still a gimple operand. Thus, it
620 is not sufficient to replace just the base of the memory reference --
621 we need to move the whole computation of the address out of the
623 if (!is_gimple_val (t
))
627 obj
= TREE_OPERAND (t
, 0);
628 var
= get_base_address (obj
);
629 if (!var
|| !SSA_VAR_P (var
) || DECL_EXTERNAL (var
))
632 addr_type
= TREE_TYPE (t
);
633 addr
= take_address_of (obj
, addr_type
, dta
->entry
, dta
->decl_address
);
646 /* Moves the references to local variables in STMT out of the single
647 entry single exit region starting at ENTRY. DECL_ADDRESS contains
648 addresses of the references that had their address taken
652 eliminate_local_variables_stmt (edge entry
, gimple stmt
,
657 memset (&dta
.info
, '\0', sizeof (dta
.info
));
659 dta
.decl_address
= decl_address
;
662 walk_gimple_op (stmt
, eliminate_local_variables_1
, &dta
.info
);
668 /* Eliminates the references to local variables from the single entry
669 single exit region between the ENTRY and EXIT edges.
672 1) Taking address of a local variable -- these are moved out of the
673 region (and temporary variable is created to hold the address if
676 2) Dereferencing a local variable -- these are replaced with indirect
680 eliminate_local_variables (edge entry
, edge exit
)
683 VEC (basic_block
, heap
) *body
= VEC_alloc (basic_block
, heap
, 3);
685 gimple_stmt_iterator gsi
;
686 htab_t decl_address
= htab_create (10, int_tree_map_hash
, int_tree_map_eq
,
688 basic_block entry_bb
= entry
->src
;
689 basic_block exit_bb
= exit
->dest
;
691 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
693 for (i
= 0; VEC_iterate (basic_block
, body
, i
, bb
); i
++)
694 if (bb
!= entry_bb
&& bb
!= exit_bb
)
695 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
696 eliminate_local_variables_stmt (entry
, gsi_stmt (gsi
),
699 htab_delete (decl_address
);
700 VEC_free (basic_block
, heap
, body
);
703 /* Returns true if expression EXPR is not defined between ENTRY and
704 EXIT, i.e. if all its operands are defined outside of the region. */
707 expr_invariant_in_region_p (edge entry
, edge exit
, tree expr
)
709 basic_block entry_bb
= entry
->src
;
710 basic_block exit_bb
= exit
->dest
;
713 if (is_gimple_min_invariant (expr
))
716 if (TREE_CODE (expr
) == SSA_NAME
)
718 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
720 && dominated_by_p (CDI_DOMINATORS
, def_bb
, entry_bb
)
721 && !dominated_by_p (CDI_DOMINATORS
, def_bb
, exit_bb
))
730 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
731 The copies are stored to NAME_COPIES, if NAME was already duplicated,
732 its duplicate stored in NAME_COPIES is returned.
734 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
735 duplicated, storing the copies in DECL_COPIES. */
738 separate_decls_in_region_name (tree name
,
739 htab_t name_copies
, htab_t decl_copies
,
742 tree copy
, var
, var_copy
;
743 unsigned idx
, uid
, nuid
;
744 struct int_tree_map ielt
, *nielt
;
745 struct name_to_copy_elt elt
, *nelt
;
746 void **slot
, **dslot
;
748 if (TREE_CODE (name
) != SSA_NAME
)
751 idx
= SSA_NAME_VERSION (name
);
753 slot
= htab_find_slot_with_hash (name_copies
, &elt
, idx
,
754 copy_name_p
? INSERT
: NO_INSERT
);
756 return ((struct name_to_copy_elt
*) *slot
)->new_name
;
758 var
= SSA_NAME_VAR (name
);
759 uid
= DECL_UID (var
);
761 dslot
= htab_find_slot_with_hash (decl_copies
, &ielt
, uid
, INSERT
);
764 var_copy
= create_tmp_var (TREE_TYPE (var
), get_name (var
));
765 DECL_GIMPLE_REG_P (var_copy
) = DECL_GIMPLE_REG_P (var
);
766 add_referenced_var (var_copy
);
767 nielt
= XNEW (struct int_tree_map
);
769 nielt
->to
= var_copy
;
772 /* Ensure that when we meet this decl next time, we won't duplicate
774 nuid
= DECL_UID (var_copy
);
776 dslot
= htab_find_slot_with_hash (decl_copies
, &ielt
, nuid
, INSERT
);
777 gcc_assert (!*dslot
);
778 nielt
= XNEW (struct int_tree_map
);
780 nielt
->to
= var_copy
;
784 var_copy
= ((struct int_tree_map
*) *dslot
)->to
;
788 copy
= duplicate_ssa_name (name
, NULL
);
789 nelt
= XNEW (struct name_to_copy_elt
);
791 nelt
->new_name
= copy
;
792 nelt
->field
= NULL_TREE
;
801 SSA_NAME_VAR (copy
) = var_copy
;
805 /* Finds the ssa names used in STMT that are defined outside the
806 region between ENTRY and EXIT and replaces such ssa names with
807 their duplicates. The duplicates are stored to NAME_COPIES. Base
808 decls of all ssa names used in STMT (including those defined in
809 LOOP) are replaced with the new temporary variables; the
810 replacement decls are stored in DECL_COPIES. */
813 separate_decls_in_region_stmt (edge entry
, edge exit
, gimple stmt
,
814 htab_t name_copies
, htab_t decl_copies
)
822 mark_virtual_ops_for_renaming (stmt
);
824 FOR_EACH_PHI_OR_STMT_DEF (def
, stmt
, oi
, SSA_OP_DEF
)
826 name
= DEF_FROM_PTR (def
);
827 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
828 copy
= separate_decls_in_region_name (name
, name_copies
, decl_copies
,
830 gcc_assert (copy
== name
);
833 FOR_EACH_PHI_OR_STMT_USE (use
, stmt
, oi
, SSA_OP_USE
)
835 name
= USE_FROM_PTR (use
);
836 if (TREE_CODE (name
) != SSA_NAME
)
839 copy_name_p
= expr_invariant_in_region_p (entry
, exit
, name
);
840 copy
= separate_decls_in_region_name (name
, name_copies
, decl_copies
,
846 /* Callback for htab_traverse. Adds a field corresponding to the reduction
847 specified in SLOT. The type is passed in DATA. */
850 add_field_for_reduction (void **slot
, void *data
)
853 struct reduction_info
*const red
= (struct reduction_info
*) *slot
;
854 tree
const type
= (tree
) data
;
855 tree var
= SSA_NAME_VAR (gimple_assign_lhs (red
->reduc_stmt
));
856 tree field
= build_decl (FIELD_DECL
, DECL_NAME (var
), TREE_TYPE (var
));
858 insert_field_into_struct (type
, field
);
865 /* Callback for htab_traverse. Adds a field corresponding to a ssa name
866 described in SLOT. The type is passed in DATA. */
869 add_field_for_name (void **slot
, void *data
)
871 struct name_to_copy_elt
*const elt
= (struct name_to_copy_elt
*) *slot
;
872 tree type
= (tree
) data
;
873 tree name
= ssa_name (elt
->version
);
874 tree var
= SSA_NAME_VAR (name
);
875 tree field
= build_decl (FIELD_DECL
, DECL_NAME (var
), TREE_TYPE (var
));
877 insert_field_into_struct (type
, field
);
883 /* Callback for htab_traverse. A local result is the intermediate result
885 thread, or the initial value in case no iteration was executed.
886 This function creates a phi node reflecting these values.
887 The phi's result will be stored in NEW_PHI field of the
888 reduction's data structure. */
891 create_phi_for_local_result (void **slot
, void *data
)
893 struct reduction_info
*const reduc
= (struct reduction_info
*) *slot
;
894 const struct loop
*const loop
= (const struct loop
*) data
;
897 basic_block store_bb
;
900 /* STORE_BB is the block where the phi
901 should be stored. It is the destination of the loop exit.
902 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
903 store_bb
= FALLTHRU_EDGE (loop
->latch
)->dest
;
905 /* STORE_BB has two predecessors. One coming from the loop
906 (the reduction's result is computed at the loop),
907 and another coming from a block preceding the loop,
909 are executed (the initial value should be taken). */
910 if (EDGE_PRED (store_bb
, 0) == FALLTHRU_EDGE (loop
->latch
))
911 e
= EDGE_PRED (store_bb
, 1);
913 e
= EDGE_PRED (store_bb
, 0);
915 = make_ssa_name (SSA_NAME_VAR (gimple_assign_lhs (reduc
->reduc_stmt
)),
917 new_phi
= create_phi_node (local_res
, store_bb
);
918 SSA_NAME_DEF_STMT (local_res
) = new_phi
;
919 add_phi_arg (new_phi
, reduc
->init
, e
);
920 add_phi_arg (new_phi
, gimple_assign_lhs (reduc
->reduc_stmt
),
921 FALLTHRU_EDGE (loop
->latch
));
922 reduc
->new_phi
= new_phi
;
932 basic_block store_bb
;
936 /* Callback for htab_traverse. Create an atomic instruction for the
937 reduction described in SLOT.
938 DATA annotates the place in memory the atomic operation relates to,
939 and the basic block it needs to be generated in. */
942 create_call_for_reduction_1 (void **slot
, void *data
)
944 struct reduction_info
*const reduc
= (struct reduction_info
*) *slot
;
945 struct clsn_data
*const clsn_data
= (struct clsn_data
*) data
;
946 gimple_stmt_iterator gsi
;
947 tree type
= TREE_TYPE (PHI_RESULT (reduc
->reduc_phi
));
948 tree struct_type
= TREE_TYPE (TREE_TYPE (clsn_data
->load
));
953 tree t
, addr
, addr_type
, ref
, x
;
957 load_struct
= fold_build1 (INDIRECT_REF
, struct_type
, clsn_data
->load
);
958 t
= build3 (COMPONENT_REF
, type
, load_struct
, reduc
->field
, NULL_TREE
);
959 addr_type
= build_pointer_type (type
);
961 addr
= build_addr (t
, current_function_decl
);
963 /* Create phi node. */
964 bb
= clsn_data
->load_bb
;
966 e
= split_block (bb
, t
);
969 tmp_load
= create_tmp_var (TREE_TYPE (TREE_TYPE (addr
)), NULL
);
970 add_referenced_var (tmp_load
);
971 tmp_load
= make_ssa_name (tmp_load
, NULL
);
972 load
= gimple_build_omp_atomic_load (tmp_load
, addr
);
973 SSA_NAME_DEF_STMT (tmp_load
) = load
;
974 gsi
= gsi_start_bb (new_bb
);
975 gsi_insert_after (&gsi
, load
, GSI_NEW_STMT
);
977 e
= split_block (new_bb
, load
);
979 gsi
= gsi_start_bb (new_bb
);
981 x
= fold_build2 (reduc
->reduction_code
,
982 TREE_TYPE (PHI_RESULT (reduc
->new_phi
)), ref
,
983 PHI_RESULT (reduc
->new_phi
));
985 name
= force_gimple_operand_gsi (&gsi
, x
, true, NULL_TREE
, true,
986 GSI_CONTINUE_LINKING
);
988 gsi_insert_after (&gsi
, gimple_build_omp_atomic_store (name
), GSI_NEW_STMT
);
992 /* Create the atomic operation at the join point of the threads.
993 REDUCTION_LIST describes the reductions in the LOOP.
994 LD_ST_DATA describes the shared data structure where
995 shared data is stored in and loaded from. */
997 create_call_for_reduction (struct loop
*loop
, htab_t reduction_list
,
998 struct clsn_data
*ld_st_data
)
1000 htab_traverse (reduction_list
, create_phi_for_local_result
, loop
);
1001 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
1002 ld_st_data
->load_bb
= FALLTHRU_EDGE (loop
->latch
)->dest
;
1003 htab_traverse (reduction_list
, create_call_for_reduction_1
, ld_st_data
);
1006 /* Callback for htab_traverse. Loads the final reduction value at the
1007 join point of all threads, and inserts it in the right place. */
1010 create_loads_for_reductions (void **slot
, void *data
)
1012 struct reduction_info
*const red
= (struct reduction_info
*) *slot
;
1013 struct clsn_data
*const clsn_data
= (struct clsn_data
*) data
;
1015 gimple_stmt_iterator gsi
;
1016 tree type
= TREE_TYPE (gimple_assign_lhs (red
->reduc_stmt
));
1017 tree struct_type
= TREE_TYPE (TREE_TYPE (clsn_data
->load
));
1022 gsi
= gsi_after_labels (clsn_data
->load_bb
);
1023 load_struct
= fold_build1 (INDIRECT_REF
, struct_type
, clsn_data
->load
);
1024 load_struct
= build3 (COMPONENT_REF
, type
, load_struct
, red
->field
,
1028 name
= PHI_RESULT (red
->keep_res
);
1029 stmt
= gimple_build_assign (name
, x
);
1030 SSA_NAME_DEF_STMT (name
) = stmt
;
1032 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1034 for (gsi
= gsi_start_phis (gimple_bb (red
->keep_res
));
1035 !gsi_end_p (gsi
); gsi_next (&gsi
))
1036 if (gsi_stmt (gsi
) == red
->keep_res
)
1038 remove_phi_node (&gsi
, false);
1044 /* Load the reduction result that was stored in LD_ST_DATA.
1045 REDUCTION_LIST describes the list of reductions that the
1046 loads should be generated for. */
1048 create_final_loads_for_reduction (htab_t reduction_list
,
1049 struct clsn_data
*ld_st_data
)
1051 gimple_stmt_iterator gsi
;
1055 gsi
= gsi_after_labels (ld_st_data
->load_bb
);
1056 t
= build_fold_addr_expr (ld_st_data
->store
);
1057 stmt
= gimple_build_assign (ld_st_data
->load
, t
);
1059 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1060 SSA_NAME_DEF_STMT (ld_st_data
->load
) = stmt
;
1062 htab_traverse (reduction_list
, create_loads_for_reductions
, ld_st_data
);
1066 /* Callback for htab_traverse. Store the neutral value for the
1067 particular reduction's operation, e.g. 0 for PLUS_EXPR,
1068 1 for MULT_EXPR, etc. into the reduction field.
1069 The reduction is specified in SLOT. The store information is
1073 create_stores_for_reduction (void **slot
, void *data
)
1075 struct reduction_info
*const red
= (struct reduction_info
*) *slot
;
1076 struct clsn_data
*const clsn_data
= (struct clsn_data
*) data
;
1079 gimple_stmt_iterator gsi
;
1080 tree type
= TREE_TYPE (gimple_assign_lhs (red
->reduc_stmt
));
1082 gsi
= gsi_last_bb (clsn_data
->store_bb
);
1083 t
= build3 (COMPONENT_REF
, type
, clsn_data
->store
, red
->field
, NULL_TREE
);
1084 stmt
= gimple_build_assign (t
, red
->initial_value
);
1085 mark_virtual_ops_for_renaming (stmt
);
1086 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1091 /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
1092 store to a field of STORE in STORE_BB for the ssa name and its duplicate
1093 specified in SLOT. */
1096 create_loads_and_stores_for_name (void **slot
, void *data
)
1098 struct name_to_copy_elt
*const elt
= (struct name_to_copy_elt
*) *slot
;
1099 struct clsn_data
*const clsn_data
= (struct clsn_data
*) data
;
1102 gimple_stmt_iterator gsi
;
1103 tree type
= TREE_TYPE (elt
->new_name
);
1104 tree struct_type
= TREE_TYPE (TREE_TYPE (clsn_data
->load
));
1107 gsi
= gsi_last_bb (clsn_data
->store_bb
);
1108 t
= build3 (COMPONENT_REF
, type
, clsn_data
->store
, elt
->field
, NULL_TREE
);
1109 stmt
= gimple_build_assign (t
, ssa_name (elt
->version
));
1110 mark_virtual_ops_for_renaming (stmt
);
1111 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1113 gsi
= gsi_last_bb (clsn_data
->load_bb
);
1114 load_struct
= fold_build1 (INDIRECT_REF
, struct_type
, clsn_data
->load
);
1115 t
= build3 (COMPONENT_REF
, type
, load_struct
, elt
->field
, NULL_TREE
);
1116 stmt
= gimple_build_assign (elt
->new_name
, t
);
1117 SSA_NAME_DEF_STMT (elt
->new_name
) = stmt
;
1118 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1123 /* Moves all the variables used in LOOP and defined outside of it (including
1124 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1125 name) to a structure created for this purpose. The code
1133 is transformed this way:
1148 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1149 pointer `new' is intentionally not initialized (the loop will be split to a
1150 separate function later, and `new' will be initialized from its arguments).
1151 LD_ST_DATA holds information about the shared data structure used to pass
1152 information among the threads. It is initialized here, and
1153 gen_parallel_loop will pass it to create_call_for_reduction that
1154 needs this information. REDUCTION_LIST describes the reductions
1158 separate_decls_in_region (edge entry
, edge exit
, htab_t reduction_list
,
1159 tree
*arg_struct
, tree
*new_arg_struct
,
1160 struct clsn_data
*ld_st_data
)
1163 basic_block bb1
= split_edge (entry
);
1164 basic_block bb0
= single_pred (bb1
);
1165 htab_t name_copies
= htab_create (10, name_to_copy_elt_hash
,
1166 name_to_copy_elt_eq
, free
);
1167 htab_t decl_copies
= htab_create (10, int_tree_map_hash
, int_tree_map_eq
,
1170 tree type
, type_name
, nvar
;
1171 gimple_stmt_iterator gsi
;
1172 struct clsn_data clsn_data
;
1173 VEC (basic_block
, heap
) *body
= VEC_alloc (basic_block
, heap
, 3);
1175 basic_block entry_bb
= bb1
;
1176 basic_block exit_bb
= exit
->dest
;
1178 entry
= single_succ_edge (entry_bb
);
1179 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
1181 for (i
= 0; VEC_iterate (basic_block
, body
, i
, bb
); i
++)
1183 if (bb
!= entry_bb
&& bb
!= exit_bb
)
1185 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1186 separate_decls_in_region_stmt (entry
, exit
, gsi_stmt (gsi
),
1187 name_copies
, decl_copies
);
1189 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1190 separate_decls_in_region_stmt (entry
, exit
, gsi_stmt (gsi
),
1191 name_copies
, decl_copies
);
1195 VEC_free (basic_block
, heap
, body
);
1197 if (htab_elements (name_copies
) == 0 && 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 (TYPE_DECL
, create_tmp_var_name (".paral_data"),
1210 TYPE_NAME (type
) = type_name
;
1212 htab_traverse (name_copies
, add_field_for_name
, type
);
1213 if (reduction_list
&& htab_elements (reduction_list
) > 0)
1215 /* Create the fields for reductions. */
1216 htab_traverse (reduction_list
, add_field_for_reduction
,
1221 /* Create the loads and stores. */
1222 *arg_struct
= create_tmp_var (type
, ".paral_data_store");
1223 add_referenced_var (*arg_struct
);
1224 nvar
= create_tmp_var (build_pointer_type (type
), ".paral_data_load");
1225 add_referenced_var (nvar
);
1226 *new_arg_struct
= make_ssa_name (nvar
, NULL
);
1228 ld_st_data
->store
= *arg_struct
;
1229 ld_st_data
->load
= *new_arg_struct
;
1230 ld_st_data
->store_bb
= bb0
;
1231 ld_st_data
->load_bb
= bb1
;
1233 htab_traverse (name_copies
, create_loads_and_stores_for_name
,
1236 /* Load the calculation from memory (after the join of the threads). */
1238 if (reduction_list
&& htab_elements (reduction_list
) > 0)
1240 htab_traverse (reduction_list
, create_stores_for_reduction
,
1242 clsn_data
.load
= make_ssa_name (nvar
, NULL
);
1243 clsn_data
.load_bb
= exit
->dest
;
1244 clsn_data
.store
= ld_st_data
->store
;
1245 create_final_loads_for_reduction (reduction_list
, &clsn_data
);
1249 htab_delete (decl_copies
);
1250 htab_delete (name_copies
);
1253 /* Bitmap containing uids of functions created by parallelization. We cannot
1254 allocate it from the default obstack, as it must live across compilation
1255 of several functions; we make it gc allocated instead. */
1257 static GTY(()) bitmap parallelized_functions
;
1259 /* Returns true if FN was created by create_loop_fn. */
1262 parallelized_function_p (tree fn
)
1264 if (!parallelized_functions
|| !DECL_ARTIFICIAL (fn
))
1267 return bitmap_bit_p (parallelized_functions
, DECL_UID (fn
));
1270 /* Creates and returns an empty function that will receive the body of
1271 a parallelized loop. */
1274 create_loop_fn (void)
1278 tree decl
, type
, name
, t
;
1279 struct function
*act_cfun
= cfun
;
1280 static unsigned loopfn_num
;
1282 snprintf (buf
, 100, "%s.$loopfn", current_function_name ());
1283 ASM_FORMAT_PRIVATE_NAME (tname
, buf
, loopfn_num
++);
1284 clean_symbol_name (tname
);
1285 name
= get_identifier (tname
);
1286 type
= build_function_type_list (void_type_node
, ptr_type_node
, NULL_TREE
);
1288 decl
= build_decl (FUNCTION_DECL
, name
, type
);
1289 if (!parallelized_functions
)
1290 parallelized_functions
= BITMAP_GGC_ALLOC ();
1291 bitmap_set_bit (parallelized_functions
, DECL_UID (decl
));
1293 TREE_STATIC (decl
) = 1;
1294 TREE_USED (decl
) = 1;
1295 DECL_ARTIFICIAL (decl
) = 1;
1296 DECL_IGNORED_P (decl
) = 0;
1297 TREE_PUBLIC (decl
) = 0;
1298 DECL_UNINLINABLE (decl
) = 1;
1299 DECL_EXTERNAL (decl
) = 0;
1300 DECL_CONTEXT (decl
) = NULL_TREE
;
1301 DECL_INITIAL (decl
) = make_node (BLOCK
);
1303 t
= build_decl (RESULT_DECL
, NULL_TREE
, void_type_node
);
1304 DECL_ARTIFICIAL (t
) = 1;
1305 DECL_IGNORED_P (t
) = 1;
1306 DECL_RESULT (decl
) = t
;
1308 t
= build_decl (PARM_DECL
, get_identifier (".paral_data_param"),
1310 DECL_ARTIFICIAL (t
) = 1;
1311 DECL_ARG_TYPE (t
) = ptr_type_node
;
1312 DECL_CONTEXT (t
) = decl
;
1314 DECL_ARGUMENTS (decl
) = t
;
1316 allocate_struct_function (decl
, false);
1318 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1320 set_cfun (act_cfun
);
1325 /* Bases all the induction variables in LOOP on a single induction variable
1326 (unsigned with base 0 and step 1), whose final value is compared with
1327 NIT. The induction variable is incremented in the loop latch.
1328 REDUCTION_LIST describes the reductions in LOOP. */
1331 canonicalize_loop_ivs (struct loop
*loop
, htab_t reduction_list
, tree nit
)
1333 unsigned precision
= TYPE_PRECISION (TREE_TYPE (nit
));
1334 tree res
, type
, var_before
, val
, atype
, mtype
;
1335 gimple_stmt_iterator gsi
, psi
;
1339 edge exit
= single_dom_exit (loop
);
1340 struct reduction_info
*red
;
1342 for (psi
= gsi_start_phis (loop
->header
);
1343 !gsi_end_p (psi
); gsi_next (&psi
))
1345 phi
= gsi_stmt (psi
);
1346 res
= PHI_RESULT (phi
);
1348 if (is_gimple_reg (res
) && TYPE_PRECISION (TREE_TYPE (res
)) > precision
)
1349 precision
= TYPE_PRECISION (TREE_TYPE (res
));
1352 type
= lang_hooks
.types
.type_for_size (precision
, 1);
1354 gsi
= gsi_last_bb (loop
->latch
);
1355 create_iv (build_int_cst_type (type
, 0), build_int_cst (type
, 1), NULL_TREE
,
1356 loop
, &gsi
, true, &var_before
, NULL
);
1358 gsi
= gsi_after_labels (loop
->header
);
1359 for (psi
= gsi_start_phis (loop
->header
); !gsi_end_p (psi
); )
1361 phi
= gsi_stmt (psi
);
1362 res
= PHI_RESULT (phi
);
1364 if (!is_gimple_reg (res
) || res
== var_before
)
1370 ok
= simple_iv (loop
, phi
, res
, &iv
, true);
1371 red
= reduction_phi (reduction_list
, phi
);
1372 /* We preserve the reduction phi nodes. */
1380 remove_phi_node (&psi
, false);
1382 atype
= TREE_TYPE (res
);
1383 mtype
= POINTER_TYPE_P (atype
) ? sizetype
: atype
;
1384 val
= fold_build2 (MULT_EXPR
, mtype
, unshare_expr (iv
.step
),
1385 fold_convert (mtype
, var_before
));
1386 val
= fold_build2 (POINTER_TYPE_P (atype
)
1387 ? POINTER_PLUS_EXPR
: PLUS_EXPR
,
1388 atype
, unshare_expr (iv
.base
), val
);
1389 val
= force_gimple_operand_gsi (&gsi
, val
, false, NULL_TREE
, true,
1391 stmt
= gimple_build_assign (res
, val
);
1392 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1393 SSA_NAME_DEF_STMT (res
) = stmt
;
1396 stmt
= last_stmt (exit
->src
);
1397 /* Make the loop exit if the control condition is not satisfied. */
1398 if (exit
->flags
& EDGE_TRUE_VALUE
)
1402 extract_true_false_edges_from_block (exit
->src
, &te
, &fe
);
1403 te
->flags
= EDGE_FALSE_VALUE
;
1404 fe
->flags
= EDGE_TRUE_VALUE
;
1406 gimple_cond_set_code (stmt
, LT_EXPR
);
1407 gimple_cond_set_lhs (stmt
, var_before
);
1408 gimple_cond_set_rhs (stmt
, nit
);
1411 /* Moves the exit condition of LOOP to the beginning of its header, and
1412 duplicates the part of the last iteration that gets disabled to the
1413 exit of the loop. NIT is the number of iterations of the loop
1414 (used to initialize the variables in the duplicated part).
1416 TODO: the common case is that latch of the loop is empty and immediately
1417 follows the loop exit. In this case, it would be better not to copy the
1418 body of the loop, but only move the entry of the loop directly before the
1419 exit check and increase the number of iterations of the loop by one.
1420 This may need some additional preconditioning in case NIT = ~0.
1421 REDUCTION_LIST describes the reductions in LOOP. */
1424 transform_to_exit_first_loop (struct loop
*loop
, htab_t reduction_list
, tree nit
)
1426 basic_block
*bbs
, *nbbs
, ex_bb
, orig_header
;
1429 edge exit
= single_dom_exit (loop
), hpred
;
1430 tree control
, control_name
, res
, t
;
1431 gimple phi
, nphi
, cond_stmt
, stmt
;
1432 gimple_stmt_iterator gsi
;
1434 split_block_after_labels (loop
->header
);
1435 orig_header
= single_succ (loop
->header
);
1436 hpred
= single_succ_edge (loop
->header
);
1438 cond_stmt
= last_stmt (exit
->src
);
1439 control
= gimple_cond_lhs (cond_stmt
);
1440 gcc_assert (gimple_cond_rhs (cond_stmt
) == nit
);
1442 /* Make sure that we have phi nodes on exit for all loop header phis
1443 (create_parallel_loop requires that). */
1444 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1446 phi
= gsi_stmt (gsi
);
1447 res
= PHI_RESULT (phi
);
1448 t
= make_ssa_name (SSA_NAME_VAR (res
), phi
);
1449 SET_PHI_RESULT (phi
, t
);
1451 nphi
= create_phi_node (res
, orig_header
);
1452 SSA_NAME_DEF_STMT (res
) = nphi
;
1453 add_phi_arg (nphi
, t
, hpred
);
1457 gimple_cond_set_lhs (cond_stmt
, t
);
1458 update_stmt (cond_stmt
);
1463 bbs
= get_loop_body_in_dom_order (loop
);
1464 for (n
= 0; bbs
[n
] != exit
->src
; n
++)
1466 nbbs
= XNEWVEC (basic_block
, n
);
1467 ok
= gimple_duplicate_sese_tail (single_succ_edge (loop
->header
), exit
,
1474 /* Other than reductions, the only gimple reg that should be copied
1475 out of the loop is the control variable. */
1477 control_name
= NULL_TREE
;
1478 for (gsi
= gsi_start_phis (ex_bb
); !gsi_end_p (gsi
); )
1480 phi
= gsi_stmt (gsi
);
1481 res
= PHI_RESULT (phi
);
1482 if (!is_gimple_reg (res
))
1488 /* Check if it is a part of reduction. If it is,
1489 keep the phi at the reduction's keep_res field. The
1490 PHI_RESULT of this phi is the resulting value of the reduction
1491 variable when exiting the loop. */
1493 exit
= single_dom_exit (loop
);
1495 if (htab_elements (reduction_list
) > 0)
1497 struct reduction_info
*red
;
1499 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1501 red
= reduction_phi (reduction_list
, SSA_NAME_DEF_STMT (val
));
1504 red
->keep_res
= phi
;
1509 gcc_assert (control_name
== NULL_TREE
1510 && SSA_NAME_VAR (res
) == SSA_NAME_VAR (control
));
1512 remove_phi_node (&gsi
, false);
1514 gcc_assert (control_name
!= NULL_TREE
);
1516 /* Initialize the control variable to NIT. */
1517 gsi
= gsi_after_labels (ex_bb
);
1518 nit
= force_gimple_operand_gsi (&gsi
,
1519 fold_convert (TREE_TYPE (control_name
), nit
),
1520 false, NULL_TREE
, false, GSI_SAME_STMT
);
1521 stmt
= gimple_build_assign (control_name
, nit
);
1522 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1523 SSA_NAME_DEF_STMT (control_name
) = stmt
;
1526 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
1527 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
1528 NEW_DATA is the variable that should be initialized from the argument
1529 of LOOP_FN. N_THREADS is the requested number of threads. Returns the
1530 basic block containing GIMPLE_OMP_PARALLEL tree. */
1533 create_parallel_loop (struct loop
*loop
, tree loop_fn
, tree data
,
1534 tree new_data
, unsigned n_threads
)
1536 gimple_stmt_iterator gsi
;
1537 basic_block bb
, paral_bb
, for_bb
, ex_bb
;
1539 gimple stmt
, for_stmt
, phi
, cond_stmt
;
1540 tree cvar
, cvar_init
, initvar
, cvar_next
, cvar_base
, type
;
1541 edge exit
, nexit
, guard
, end
, e
;
1543 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
1544 bb
= loop_preheader_edge (loop
)->src
;
1545 paral_bb
= single_pred (bb
);
1546 gsi
= gsi_last_bb (paral_bb
);
1548 t
= build_omp_clause (OMP_CLAUSE_NUM_THREADS
);
1549 OMP_CLAUSE_NUM_THREADS_EXPR (t
)
1550 = build_int_cst (integer_type_node
, n_threads
);
1551 stmt
= gimple_build_omp_parallel (NULL
, t
, loop_fn
, data
);
1553 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1555 /* Initialize NEW_DATA. */
1558 gsi
= gsi_after_labels (bb
);
1560 param
= make_ssa_name (DECL_ARGUMENTS (loop_fn
), NULL
);
1561 stmt
= gimple_build_assign (param
, build_fold_addr_expr (data
));
1562 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1563 SSA_NAME_DEF_STMT (param
) = stmt
;
1565 stmt
= gimple_build_assign (new_data
,
1566 fold_convert (TREE_TYPE (new_data
), param
));
1567 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1568 SSA_NAME_DEF_STMT (new_data
) = stmt
;
1571 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
1572 bb
= split_loop_exit_edge (single_dom_exit (loop
));
1573 gsi
= gsi_last_bb (bb
);
1574 gsi_insert_after (&gsi
, gimple_build_omp_return (false), GSI_NEW_STMT
);
1576 /* Extract data for GIMPLE_OMP_FOR. */
1577 gcc_assert (loop
->header
== single_dom_exit (loop
)->src
);
1578 cond_stmt
= last_stmt (loop
->header
);
1580 cvar
= gimple_cond_lhs (cond_stmt
);
1581 cvar_base
= SSA_NAME_VAR (cvar
);
1582 phi
= SSA_NAME_DEF_STMT (cvar
);
1583 cvar_init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1584 initvar
= make_ssa_name (cvar_base
, NULL
);
1585 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, loop_preheader_edge (loop
)),
1587 cvar_next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
1589 gsi
= gsi_last_bb (loop
->latch
);
1590 gcc_assert (gsi_stmt (gsi
) == SSA_NAME_DEF_STMT (cvar_next
));
1591 gsi_remove (&gsi
, true);
1594 for_bb
= split_edge (loop_preheader_edge (loop
));
1595 ex_bb
= split_loop_exit_edge (single_dom_exit (loop
));
1596 extract_true_false_edges_from_block (loop
->header
, &nexit
, &exit
);
1597 gcc_assert (exit
== single_dom_exit (loop
));
1599 guard
= make_edge (for_bb
, ex_bb
, 0);
1600 single_succ_edge (loop
->latch
)->flags
= 0;
1601 end
= make_edge (loop
->latch
, ex_bb
, EDGE_FALLTHRU
);
1602 for (gsi
= gsi_start_phis (ex_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1604 phi
= gsi_stmt (gsi
);
1605 res
= PHI_RESULT (phi
);
1606 stmt
= SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi
, exit
));
1608 PHI_ARG_DEF_FROM_EDGE (stmt
, loop_preheader_edge (loop
)),
1610 add_phi_arg (phi
, PHI_ARG_DEF_FROM_EDGE (stmt
, loop_latch_edge (loop
)),
1613 e
= redirect_edge_and_branch (exit
, nexit
->dest
);
1614 PENDING_STMT (e
) = NULL
;
1616 /* Emit GIMPLE_OMP_FOR. */
1617 gimple_cond_set_lhs (cond_stmt
, cvar_base
);
1618 type
= TREE_TYPE (cvar
);
1619 t
= build_omp_clause (OMP_CLAUSE_SCHEDULE
);
1620 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_STATIC
;
1622 for_stmt
= gimple_build_omp_for (NULL
, t
, 1, NULL
);
1623 gimple_omp_for_set_index (for_stmt
, 0, initvar
);
1624 gimple_omp_for_set_initial (for_stmt
, 0, cvar_init
);
1625 gimple_omp_for_set_final (for_stmt
, 0, gimple_cond_rhs (cond_stmt
));
1626 gimple_omp_for_set_cond (for_stmt
, 0, gimple_cond_code (cond_stmt
));
1627 gimple_omp_for_set_incr (for_stmt
, 0, build2 (PLUS_EXPR
, type
,
1629 build_int_cst (type
, 1)));
1631 gsi
= gsi_last_bb (for_bb
);
1632 gsi_insert_after (&gsi
, for_stmt
, GSI_NEW_STMT
);
1633 SSA_NAME_DEF_STMT (initvar
) = for_stmt
;
1635 /* Emit GIMPLE_OMP_CONTINUE. */
1636 gsi
= gsi_last_bb (loop
->latch
);
1637 stmt
= gimple_build_omp_continue (cvar_next
, cvar
);
1638 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1639 SSA_NAME_DEF_STMT (cvar_next
) = stmt
;
1641 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
1642 gsi
= gsi_last_bb (ex_bb
);
1643 gsi_insert_after (&gsi
, gimple_build_omp_return (true), GSI_NEW_STMT
);
1648 /* Generates code to execute the iterations of LOOP in N_THREADS threads in
1649 parallel. NITER describes number of iterations of LOOP.
1650 REDUCTION_LIST describes the reductions existent in the LOOP. */
1653 gen_parallel_loop (struct loop
*loop
, htab_t reduction_list
,
1654 unsigned n_threads
, struct tree_niter_desc
*niter
)
1658 tree many_iterations_cond
, type
, nit
;
1659 tree arg_struct
, new_arg_struct
;
1661 basic_block parallel_head
;
1663 struct clsn_data clsn_data
;
1668 ---------------------------------------------------------------------
1671 IV = phi (INIT, IV + STEP)
1677 ---------------------------------------------------------------------
1679 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
1680 we generate the following code:
1682 ---------------------------------------------------------------------
1685 || NITER < MIN_PER_THREAD * N_THREADS)
1689 store all local loop-invariant variables used in body of the loop to DATA.
1690 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
1691 load the variables from DATA.
1692 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
1695 GIMPLE_OMP_CONTINUE;
1696 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
1697 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
1703 IV = phi (INIT, IV + STEP)
1714 /* Create two versions of the loop -- in the old one, we know that the
1715 number of iterations is large enough, and we will transform it into the
1716 loop that will be split to loop_fn, the new one will be used for the
1717 remaining iterations. */
1719 type
= TREE_TYPE (niter
->niter
);
1720 nit
= force_gimple_operand (unshare_expr (niter
->niter
), &stmts
, true,
1723 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1725 many_iterations_cond
=
1726 fold_build2 (GE_EXPR
, boolean_type_node
,
1727 nit
, build_int_cst (type
, MIN_PER_THREAD
* n_threads
));
1728 many_iterations_cond
1729 = fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1730 invert_truthvalue (unshare_expr (niter
->may_be_zero
)),
1731 many_iterations_cond
);
1732 many_iterations_cond
1733 = force_gimple_operand (many_iterations_cond
, &stmts
, false, NULL_TREE
);
1735 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1736 if (!is_gimple_condexpr (many_iterations_cond
))
1738 many_iterations_cond
1739 = force_gimple_operand (many_iterations_cond
, &stmts
,
1742 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1745 initialize_original_copy_tables ();
1747 /* We assume that the loop usually iterates a lot. */
1748 prob
= 4 * REG_BR_PROB_BASE
/ 5;
1749 nloop
= loop_version (loop
, many_iterations_cond
, NULL
,
1750 prob
, prob
, REG_BR_PROB_BASE
- prob
, true);
1751 update_ssa (TODO_update_ssa
);
1752 free_original_copy_tables ();
1754 /* Base all the induction variables in LOOP on a single control one. */
1755 canonicalize_loop_ivs (loop
, reduction_list
, nit
);
1757 /* Ensure that the exit condition is the first statement in the loop. */
1758 transform_to_exit_first_loop (loop
, reduction_list
, nit
);
1760 /* Generate initializations for reductions. */
1761 if (htab_elements (reduction_list
) > 0)
1762 htab_traverse (reduction_list
, initialize_reductions
, loop
);
1764 /* Eliminate the references to local variables from the loop. */
1765 gcc_assert (single_exit (loop
));
1766 entry
= loop_preheader_edge (loop
);
1767 exit
= single_dom_exit (loop
);
1769 eliminate_local_variables (entry
, exit
);
1770 /* In the old loop, move all variables non-local to the loop to a structure
1771 and back, and create separate decls for the variables used in loop. */
1772 separate_decls_in_region (entry
, exit
, reduction_list
, &arg_struct
,
1773 &new_arg_struct
, &clsn_data
);
1775 /* Create the parallel constructs. */
1776 parallel_head
= create_parallel_loop (loop
, create_loop_fn (), arg_struct
,
1777 new_arg_struct
, n_threads
);
1778 if (htab_elements (reduction_list
) > 0)
1779 create_call_for_reduction (loop
, reduction_list
, &clsn_data
);
1783 /* Cancel the loop (it is simpler to do it here rather than to teach the
1784 expander to do it). */
1785 cancel_loop_tree (loop
);
1787 /* Free loop bound estimations that could contain references to
1788 removed statements. */
1789 FOR_EACH_LOOP (li
, loop
, 0)
1790 free_numbers_of_iterations_estimates_loop (loop
);
1792 /* Expand the parallel constructs. We do it directly here instead of running
1793 a separate expand_omp pass, since it is more efficient, and less likely to
1794 cause troubles with further analyses not being able to deal with the
1797 omp_expand_local (parallel_head
);
1800 /* Returns true when LOOP contains vector phi nodes. */
1803 loop_has_vector_phi_nodes (struct loop
*loop ATTRIBUTE_UNUSED
)
1806 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
1807 gimple_stmt_iterator gsi
;
1810 for (i
= 0; i
< loop
->num_nodes
; i
++)
1811 for (gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
1812 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi_stmt (gsi
)))) == VECTOR_TYPE
)
1821 /* Detect parallel loops and generate parallel code using libgomp
1822 primitives. Returns true if some loop was parallelized, false
1826 parallelize_loops (void)
1828 unsigned n_threads
= flag_tree_parallelize_loops
;
1829 bool changed
= false;
1831 struct tree_niter_desc niter_desc
;
1833 htab_t reduction_list
;
1835 /* Do not parallelize loops in the functions created by parallelization. */
1836 if (parallelized_function_p (cfun
->decl
))
1839 reduction_list
= htab_create (10, reduction_info_hash
,
1840 reduction_info_eq
, free
);
1841 init_stmt_vec_info_vec ();
1843 FOR_EACH_LOOP (li
, loop
, 0)
1845 htab_empty (reduction_list
);
1846 if (/* Do not bother with loops in cold areas. */
1847 optimize_loop_nest_for_size_p (loop
)
1848 /* Or loops that roll too little. */
1849 || expected_loop_iterations (loop
) <= n_threads
1850 /* And of course, the loop must be parallelizable. */
1851 || !can_duplicate_loop_p (loop
)
1852 || loop_has_blocks_with_irreducible_flag (loop
)
1853 /* FIXME: the check for vector phi nodes could be removed. */
1854 || loop_has_vector_phi_nodes (loop
)
1855 || !loop_parallel_p (loop
, reduction_list
, &niter_desc
))
1859 gen_parallel_loop (loop
, reduction_list
, n_threads
, &niter_desc
);
1860 verify_flow_info ();
1861 verify_dominators (CDI_DOMINATORS
);
1862 verify_loop_structure ();
1863 verify_loop_closed_ssa ();
1866 free_stmt_vec_info_vec ();
1867 htab_delete (reduction_list
);
1871 #include "gt-tree-parloops.h"