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 gimple keep_res
; /* The PHI_RESULT of this phi is the resulting value
172 of the reduction variable when existing the loop. */
173 tree initial_value
; /* The initial value of the reduction var before entering the loop. */
174 tree field
; /* the name of the field in the parloop data structure intended for reduction. */
175 tree init
; /* reduction initialization value. */
176 gimple new_phi
; /* (helper field) Newly created phi node whose result
177 will be passed to the atomic operation. Represents
178 the local result each thread computed for the reduction
182 /* Equality and hash functions for hashtab code. */
185 reduction_info_eq (const void *aa
, const void *bb
)
187 const struct reduction_info
*a
= (const struct reduction_info
*) aa
;
188 const struct reduction_info
*b
= (const struct reduction_info
*) bb
;
190 return (a
->reduc_phi
== b
->reduc_phi
);
194 reduction_info_hash (const void *aa
)
196 const struct reduction_info
*a
= (const struct reduction_info
*) aa
;
198 return htab_hash_pointer (a
->reduc_phi
);
201 static struct reduction_info
*
202 reduction_phi (htab_t reduction_list
, gimple phi
)
204 struct reduction_info tmpred
, *red
;
206 if (htab_elements (reduction_list
) == 0)
209 tmpred
.reduc_phi
= phi
;
210 red
= (struct reduction_info
*) htab_find (reduction_list
, &tmpred
);
215 /* Element of hashtable of names to copy. */
217 struct name_to_copy_elt
219 unsigned version
; /* The version of the name to copy. */
220 tree new_name
; /* The new name used in the copy. */
221 tree field
; /* The field of the structure used to pass the
225 /* Equality and hash functions for hashtab code. */
228 name_to_copy_elt_eq (const void *aa
, const void *bb
)
230 const struct name_to_copy_elt
*a
= (const struct name_to_copy_elt
*) aa
;
231 const struct name_to_copy_elt
*b
= (const struct name_to_copy_elt
*) bb
;
233 return a
->version
== b
->version
;
237 name_to_copy_elt_hash (const void *aa
)
239 const struct name_to_copy_elt
*a
= (const struct name_to_copy_elt
*) aa
;
241 return (hashval_t
) a
->version
;
245 /* Data dependency analysis. Returns true if the iterations of LOOP
246 are independent on each other (that is, if we can execute them
250 loop_parallel_p (struct loop
*loop
, struct obstack
* parloop_obstack
)
252 VEC (ddr_p
, heap
) * dependence_relations
;
253 VEC (data_reference_p
, heap
) *datarefs
;
254 lambda_trans_matrix trans
;
257 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
259 fprintf (dump_file
, "Considering loop %d\n", loop
->num
);
261 fprintf (dump_file
, "loop is innermost\n");
263 fprintf (dump_file
, "loop NOT innermost\n");
266 /* Check for problems with dependences. If the loop can be reversed,
267 the iterations are independent. */
268 datarefs
= VEC_alloc (data_reference_p
, heap
, 10);
269 dependence_relations
= VEC_alloc (ddr_p
, heap
, 10 * 10);
270 compute_data_dependences_for_loop (loop
, true, &datarefs
,
271 &dependence_relations
);
272 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
273 dump_data_dependence_relations (dump_file
, dependence_relations
);
275 trans
= lambda_trans_matrix_new (1, 1, parloop_obstack
);
276 LTM_MATRIX (trans
)[0][0] = -1;
278 if (lambda_transform_legal_p (trans
, 1, dependence_relations
))
281 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
282 fprintf (dump_file
, " SUCCESS: may be parallelized\n");
284 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
286 " FAILED: data dependencies exist across iterations\n");
288 free_dependence_relations (dependence_relations
);
289 free_data_refs (datarefs
);
294 /* Return true when LOOP contains basic blocks marked with the
295 BB_IRREDUCIBLE_LOOP flag. */
298 loop_has_blocks_with_irreducible_flag (struct loop
*loop
)
301 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
304 for (i
= 0; i
< loop
->num_nodes
; i
++)
305 if (bbs
[i
]->flags
& BB_IRREDUCIBLE_LOOP
)
314 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
315 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
316 to their addresses that can be reused. The address of OBJ is known to
317 be invariant in the whole function. */
320 take_address_of (tree obj
, tree type
, edge entry
, htab_t decl_address
)
324 struct int_tree_map ielt
, *nielt
;
325 tree
*var_p
, name
, bvar
, addr
;
329 /* Since the address of OBJ is invariant, the trees may be shared.
330 Avoid rewriting unrelated parts of the code. */
331 obj
= unshare_expr (obj
);
333 handled_component_p (*var_p
);
334 var_p
= &TREE_OPERAND (*var_p
, 0))
336 uid
= DECL_UID (*var_p
);
339 dslot
= htab_find_slot_with_hash (decl_address
, &ielt
, uid
, INSERT
);
342 addr
= build_addr (*var_p
, current_function_decl
);
343 bvar
= create_tmp_var (TREE_TYPE (addr
), get_name (*var_p
));
344 add_referenced_var (bvar
);
345 stmt
= gimple_build_assign (bvar
, addr
);
346 name
= make_ssa_name (bvar
, stmt
);
347 gimple_assign_set_lhs (stmt
, name
);
348 gsi_insert_on_edge_immediate (entry
, stmt
);
350 nielt
= XNEW (struct int_tree_map
);
356 name
= ((struct int_tree_map
*) *dslot
)->to
;
360 *var_p
= build_simple_mem_ref (name
);
361 name
= force_gimple_operand (build_addr (obj
, current_function_decl
),
362 &stmts
, true, NULL_TREE
);
363 if (!gimple_seq_empty_p (stmts
))
364 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
367 if (TREE_TYPE (name
) != type
)
369 name
= force_gimple_operand (fold_convert (type
, name
), &stmts
, true,
371 if (!gimple_seq_empty_p (stmts
))
372 gsi_insert_seq_on_edge_immediate (entry
, stmts
);
378 /* Callback for htab_traverse. Create the initialization statement
379 for reduction described in SLOT, and place it at the preheader of
380 the loop described in DATA. */
383 initialize_reductions (void **slot
, void *data
)
386 tree bvar
, type
, arg
;
389 struct reduction_info
*const reduc
= (struct reduction_info
*) *slot
;
390 struct loop
*loop
= (struct loop
*) data
;
392 /* Create initialization in preheader:
393 reduction_variable = initialization value of reduction. */
395 /* In the phi node at the header, replace the argument coming
396 from the preheader with the reduction initialization value. */
398 /* Create a new variable to initialize the reduction. */
399 type
= TREE_TYPE (PHI_RESULT (reduc
->reduc_phi
));
400 bvar
= create_tmp_var (type
, "reduction");
401 add_referenced_var (bvar
);
403 c
= build_omp_clause (gimple_location (reduc
->reduc_stmt
),
404 OMP_CLAUSE_REDUCTION
);
405 OMP_CLAUSE_REDUCTION_CODE (c
) = reduc
->reduction_code
;
406 OMP_CLAUSE_DECL (c
) = SSA_NAME_VAR (gimple_assign_lhs (reduc
->reduc_stmt
));
408 init
= omp_reduction_init (c
, TREE_TYPE (bvar
));
411 /* Replace the argument representing the initialization value
412 with the initialization value for the reduction (neutral
413 element for the particular operation, e.g. 0 for PLUS_EXPR,
414 1 for MULT_EXPR, etc).
415 Keep the old value in a new variable "reduction_initial",
416 that will be taken in consideration after the parallel
417 computing is done. */
419 e
= loop_preheader_edge (loop
);
420 arg
= PHI_ARG_DEF_FROM_EDGE (reduc
->reduc_phi
, e
);
421 /* Create new variable to hold the initial value. */
423 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
424 (reduc
->reduc_phi
, loop_preheader_edge (loop
)), init
);
425 reduc
->initial_value
= arg
;
431 struct walk_stmt_info info
;
437 /* Eliminates references to local variables in *TP out of the single
438 entry single exit region starting at DTA->ENTRY.
439 DECL_ADDRESS contains addresses of the references that had their
440 address taken already. If the expression is changed, CHANGED is
441 set to true. Callback for walk_tree. */
444 eliminate_local_variables_1 (tree
*tp
, int *walk_subtrees
, void *data
)
446 struct elv_data
*const dta
= (struct elv_data
*) data
;
447 tree t
= *tp
, var
, addr
, addr_type
, type
, obj
;
453 if (!SSA_VAR_P (t
) || DECL_EXTERNAL (t
))
456 type
= TREE_TYPE (t
);
457 addr_type
= build_pointer_type (type
);
458 addr
= take_address_of (t
, addr_type
, dta
->entry
, dta
->decl_address
);
459 *tp
= build_simple_mem_ref (addr
);
465 if (TREE_CODE (t
) == ADDR_EXPR
)
467 /* ADDR_EXPR may appear in two contexts:
468 -- as a gimple operand, when the address taken is a function invariant
469 -- as gimple rhs, when the resulting address in not a function
471 We do not need to do anything special in the latter case (the base of
472 the memory reference whose address is taken may be replaced in the
473 DECL_P case). The former case is more complicated, as we need to
474 ensure that the new address is still a gimple operand. Thus, it
475 is not sufficient to replace just the base of the memory reference --
476 we need to move the whole computation of the address out of the
478 if (!is_gimple_val (t
))
482 obj
= TREE_OPERAND (t
, 0);
483 var
= get_base_address (obj
);
484 if (!var
|| !SSA_VAR_P (var
) || DECL_EXTERNAL (var
))
487 addr_type
= TREE_TYPE (t
);
488 addr
= take_address_of (obj
, addr_type
, dta
->entry
, dta
->decl_address
);
501 /* Moves the references to local variables in STMT out of the single
502 entry single exit region starting at ENTRY. DECL_ADDRESS contains
503 addresses of the references that had their address taken
507 eliminate_local_variables_stmt (edge entry
, gimple stmt
,
512 memset (&dta
.info
, '\0', sizeof (dta
.info
));
514 dta
.decl_address
= decl_address
;
517 if (gimple_debug_bind_p (stmt
))
518 walk_tree (gimple_debug_bind_get_value_ptr (stmt
),
519 eliminate_local_variables_1
, &dta
.info
, NULL
);
521 walk_gimple_op (stmt
, eliminate_local_variables_1
, &dta
.info
);
527 /* Eliminates the references to local variables from the single entry
528 single exit region between the ENTRY and EXIT edges.
531 1) Taking address of a local variable -- these are moved out of the
532 region (and temporary variable is created to hold the address if
535 2) Dereferencing a local variable -- these are replaced with indirect
539 eliminate_local_variables (edge entry
, edge exit
)
542 VEC (basic_block
, heap
) *body
= VEC_alloc (basic_block
, heap
, 3);
544 gimple_stmt_iterator gsi
;
545 htab_t decl_address
= htab_create (10, int_tree_map_hash
, int_tree_map_eq
,
547 basic_block entry_bb
= entry
->src
;
548 basic_block exit_bb
= exit
->dest
;
550 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
552 for (i
= 0; VEC_iterate (basic_block
, body
, i
, bb
); i
++)
553 if (bb
!= entry_bb
&& bb
!= exit_bb
)
554 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
555 eliminate_local_variables_stmt (entry
, gsi_stmt (gsi
),
558 htab_delete (decl_address
);
559 VEC_free (basic_block
, heap
, body
);
562 /* Returns true if expression EXPR is not defined between ENTRY and
563 EXIT, i.e. if all its operands are defined outside of the region. */
566 expr_invariant_in_region_p (edge entry
, edge exit
, tree expr
)
568 basic_block entry_bb
= entry
->src
;
569 basic_block exit_bb
= exit
->dest
;
572 if (is_gimple_min_invariant (expr
))
575 if (TREE_CODE (expr
) == SSA_NAME
)
577 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
579 && dominated_by_p (CDI_DOMINATORS
, def_bb
, entry_bb
)
580 && !dominated_by_p (CDI_DOMINATORS
, def_bb
, exit_bb
))
589 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
590 The copies are stored to NAME_COPIES, if NAME was already duplicated,
591 its duplicate stored in NAME_COPIES is returned.
593 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
594 duplicated, storing the copies in DECL_COPIES. */
597 separate_decls_in_region_name (tree name
,
598 htab_t name_copies
, htab_t decl_copies
,
601 tree copy
, var
, var_copy
;
602 unsigned idx
, uid
, nuid
;
603 struct int_tree_map ielt
, *nielt
;
604 struct name_to_copy_elt elt
, *nelt
;
605 void **slot
, **dslot
;
607 if (TREE_CODE (name
) != SSA_NAME
)
610 idx
= SSA_NAME_VERSION (name
);
612 slot
= htab_find_slot_with_hash (name_copies
, &elt
, idx
,
613 copy_name_p
? INSERT
: NO_INSERT
);
615 return ((struct name_to_copy_elt
*) *slot
)->new_name
;
617 var
= SSA_NAME_VAR (name
);
618 uid
= DECL_UID (var
);
620 dslot
= htab_find_slot_with_hash (decl_copies
, &ielt
, uid
, INSERT
);
623 var_copy
= create_tmp_var (TREE_TYPE (var
), get_name (var
));
624 DECL_GIMPLE_REG_P (var_copy
) = DECL_GIMPLE_REG_P (var
);
625 add_referenced_var (var_copy
);
626 nielt
= XNEW (struct int_tree_map
);
628 nielt
->to
= var_copy
;
631 /* Ensure that when we meet this decl next time, we won't duplicate
633 nuid
= DECL_UID (var_copy
);
635 dslot
= htab_find_slot_with_hash (decl_copies
, &ielt
, nuid
, INSERT
);
636 gcc_assert (!*dslot
);
637 nielt
= XNEW (struct int_tree_map
);
639 nielt
->to
= var_copy
;
643 var_copy
= ((struct int_tree_map
*) *dslot
)->to
;
647 copy
= duplicate_ssa_name (name
, NULL
);
648 nelt
= XNEW (struct name_to_copy_elt
);
650 nelt
->new_name
= copy
;
651 nelt
->field
= NULL_TREE
;
660 SSA_NAME_VAR (copy
) = var_copy
;
664 /* Finds the ssa names used in STMT that are defined outside the
665 region between ENTRY and EXIT and replaces such ssa names with
666 their duplicates. The duplicates are stored to NAME_COPIES. Base
667 decls of all ssa names used in STMT (including those defined in
668 LOOP) are replaced with the new temporary variables; the
669 replacement decls are stored in DECL_COPIES. */
672 separate_decls_in_region_stmt (edge entry
, edge exit
, gimple stmt
,
673 htab_t name_copies
, htab_t decl_copies
)
681 mark_virtual_ops_for_renaming (stmt
);
683 FOR_EACH_PHI_OR_STMT_DEF (def
, stmt
, oi
, SSA_OP_DEF
)
685 name
= DEF_FROM_PTR (def
);
686 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
687 copy
= separate_decls_in_region_name (name
, name_copies
, decl_copies
,
689 gcc_assert (copy
== name
);
692 FOR_EACH_PHI_OR_STMT_USE (use
, stmt
, oi
, SSA_OP_USE
)
694 name
= USE_FROM_PTR (use
);
695 if (TREE_CODE (name
) != SSA_NAME
)
698 copy_name_p
= expr_invariant_in_region_p (entry
, exit
, name
);
699 copy
= separate_decls_in_region_name (name
, name_copies
, decl_copies
,
705 /* Finds the ssa names used in STMT that are defined outside the
706 region between ENTRY and EXIT and replaces such ssa names with
707 their duplicates. The duplicates are stored to NAME_COPIES. Base
708 decls of all ssa names used in STMT (including those defined in
709 LOOP) are replaced with the new temporary variables; the
710 replacement decls are stored in DECL_COPIES. */
713 separate_decls_in_region_debug_bind (gimple stmt
,
714 htab_t name_copies
, htab_t decl_copies
)
719 struct int_tree_map ielt
;
720 struct name_to_copy_elt elt
;
721 void **slot
, **dslot
;
723 var
= gimple_debug_bind_get_var (stmt
);
724 if (TREE_CODE (var
) == DEBUG_EXPR_DECL
)
726 gcc_assert (DECL_P (var
) && SSA_VAR_P (var
));
727 ielt
.uid
= DECL_UID (var
);
728 dslot
= htab_find_slot_with_hash (decl_copies
, &ielt
, ielt
.uid
, NO_INSERT
);
731 gimple_debug_bind_set_var (stmt
, ((struct int_tree_map
*) *dslot
)->to
);
733 FOR_EACH_PHI_OR_STMT_USE (use
, stmt
, oi
, SSA_OP_USE
)
735 name
= USE_FROM_PTR (use
);
736 if (TREE_CODE (name
) != SSA_NAME
)
739 elt
.version
= SSA_NAME_VERSION (name
);
740 slot
= htab_find_slot_with_hash (name_copies
, &elt
, elt
.version
, NO_INSERT
);
743 gimple_debug_bind_reset_value (stmt
);
748 SET_USE (use
, ((struct name_to_copy_elt
*) *slot
)->new_name
);
754 /* Callback for htab_traverse. Adds a field corresponding to the reduction
755 specified in SLOT. The type is passed in DATA. */
758 add_field_for_reduction (void **slot
, void *data
)
761 struct reduction_info
*const red
= (struct reduction_info
*) *slot
;
762 tree
const type
= (tree
) data
;
763 tree var
= SSA_NAME_VAR (gimple_assign_lhs (red
->reduc_stmt
));
764 tree field
= build_decl (gimple_location (red
->reduc_stmt
),
765 FIELD_DECL
, DECL_NAME (var
), TREE_TYPE (var
));
767 insert_field_into_struct (type
, field
);
774 /* Callback for htab_traverse. Adds a field corresponding to a ssa name
775 described in SLOT. The type is passed in DATA. */
778 add_field_for_name (void **slot
, void *data
)
780 struct name_to_copy_elt
*const elt
= (struct name_to_copy_elt
*) *slot
;
781 tree type
= (tree
) data
;
782 tree name
= ssa_name (elt
->version
);
783 tree var
= SSA_NAME_VAR (name
);
784 tree field
= build_decl (DECL_SOURCE_LOCATION (var
),
785 FIELD_DECL
, DECL_NAME (var
), TREE_TYPE (var
));
787 insert_field_into_struct (type
, field
);
793 /* Callback for htab_traverse. A local result is the intermediate result
795 thread, or the initial value in case no iteration was executed.
796 This function creates a phi node reflecting these values.
797 The phi's result will be stored in NEW_PHI field of the
798 reduction's data structure. */
801 create_phi_for_local_result (void **slot
, void *data
)
803 struct reduction_info
*const reduc
= (struct reduction_info
*) *slot
;
804 const struct loop
*const loop
= (const struct loop
*) data
;
807 basic_block store_bb
;
809 source_location locus
;
811 /* STORE_BB is the block where the phi
812 should be stored. It is the destination of the loop exit.
813 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
814 store_bb
= FALLTHRU_EDGE (loop
->latch
)->dest
;
816 /* STORE_BB has two predecessors. One coming from the loop
817 (the reduction's result is computed at the loop),
818 and another coming from a block preceding the loop,
820 are executed (the initial value should be taken). */
821 if (EDGE_PRED (store_bb
, 0) == FALLTHRU_EDGE (loop
->latch
))
822 e
= EDGE_PRED (store_bb
, 1);
824 e
= EDGE_PRED (store_bb
, 0);
826 = make_ssa_name (SSA_NAME_VAR (gimple_assign_lhs (reduc
->reduc_stmt
)),
828 locus
= gimple_location (reduc
->reduc_stmt
);
829 new_phi
= create_phi_node (local_res
, store_bb
);
830 SSA_NAME_DEF_STMT (local_res
) = new_phi
;
831 add_phi_arg (new_phi
, reduc
->init
, e
, locus
);
832 add_phi_arg (new_phi
, gimple_assign_lhs (reduc
->reduc_stmt
),
833 FALLTHRU_EDGE (loop
->latch
), locus
);
834 reduc
->new_phi
= new_phi
;
844 basic_block store_bb
;
848 /* Callback for htab_traverse. Create an atomic instruction for the
849 reduction described in SLOT.
850 DATA annotates the place in memory the atomic operation relates to,
851 and the basic block it needs to be generated in. */
854 create_call_for_reduction_1 (void **slot
, void *data
)
856 struct reduction_info
*const reduc
= (struct reduction_info
*) *slot
;
857 struct clsn_data
*const clsn_data
= (struct clsn_data
*) data
;
858 gimple_stmt_iterator gsi
;
859 tree type
= TREE_TYPE (PHI_RESULT (reduc
->reduc_phi
));
864 tree t
, addr
, ref
, x
;
868 load_struct
= build_simple_mem_ref (clsn_data
->load
);
869 t
= build3 (COMPONENT_REF
, type
, load_struct
, reduc
->field
, NULL_TREE
);
871 addr
= build_addr (t
, current_function_decl
);
873 /* Create phi node. */
874 bb
= clsn_data
->load_bb
;
876 e
= split_block (bb
, t
);
879 tmp_load
= create_tmp_var (TREE_TYPE (TREE_TYPE (addr
)), NULL
);
880 add_referenced_var (tmp_load
);
881 tmp_load
= make_ssa_name (tmp_load
, NULL
);
882 load
= gimple_build_omp_atomic_load (tmp_load
, addr
);
883 SSA_NAME_DEF_STMT (tmp_load
) = load
;
884 gsi
= gsi_start_bb (new_bb
);
885 gsi_insert_after (&gsi
, load
, GSI_NEW_STMT
);
887 e
= split_block (new_bb
, load
);
889 gsi
= gsi_start_bb (new_bb
);
891 x
= fold_build2 (reduc
->reduction_code
,
892 TREE_TYPE (PHI_RESULT (reduc
->new_phi
)), ref
,
893 PHI_RESULT (reduc
->new_phi
));
895 name
= force_gimple_operand_gsi (&gsi
, x
, true, NULL_TREE
, true,
896 GSI_CONTINUE_LINKING
);
898 gsi_insert_after (&gsi
, gimple_build_omp_atomic_store (name
), GSI_NEW_STMT
);
902 /* Create the atomic operation at the join point of the threads.
903 REDUCTION_LIST describes the reductions in the LOOP.
904 LD_ST_DATA describes the shared data structure where
905 shared data is stored in and loaded from. */
907 create_call_for_reduction (struct loop
*loop
, htab_t reduction_list
,
908 struct clsn_data
*ld_st_data
)
910 htab_traverse (reduction_list
, create_phi_for_local_result
, loop
);
911 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
912 ld_st_data
->load_bb
= FALLTHRU_EDGE (loop
->latch
)->dest
;
913 htab_traverse (reduction_list
, create_call_for_reduction_1
, ld_st_data
);
916 /* Callback for htab_traverse. Loads the final reduction value at the
917 join point of all threads, and inserts it in the right place. */
920 create_loads_for_reductions (void **slot
, void *data
)
922 struct reduction_info
*const red
= (struct reduction_info
*) *slot
;
923 struct clsn_data
*const clsn_data
= (struct clsn_data
*) data
;
925 gimple_stmt_iterator gsi
;
926 tree type
= TREE_TYPE (gimple_assign_lhs (red
->reduc_stmt
));
931 gsi
= gsi_after_labels (clsn_data
->load_bb
);
932 load_struct
= build_simple_mem_ref (clsn_data
->load
);
933 load_struct
= build3 (COMPONENT_REF
, type
, load_struct
, red
->field
,
937 name
= PHI_RESULT (red
->keep_res
);
938 stmt
= gimple_build_assign (name
, x
);
939 SSA_NAME_DEF_STMT (name
) = stmt
;
941 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
943 for (gsi
= gsi_start_phis (gimple_bb (red
->keep_res
));
944 !gsi_end_p (gsi
); gsi_next (&gsi
))
945 if (gsi_stmt (gsi
) == red
->keep_res
)
947 remove_phi_node (&gsi
, false);
953 /* Load the reduction result that was stored in LD_ST_DATA.
954 REDUCTION_LIST describes the list of reductions that the
955 loads should be generated for. */
957 create_final_loads_for_reduction (htab_t reduction_list
,
958 struct clsn_data
*ld_st_data
)
960 gimple_stmt_iterator gsi
;
964 gsi
= gsi_after_labels (ld_st_data
->load_bb
);
965 t
= build_fold_addr_expr (ld_st_data
->store
);
966 stmt
= gimple_build_assign (ld_st_data
->load
, t
);
968 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
969 SSA_NAME_DEF_STMT (ld_st_data
->load
) = stmt
;
971 htab_traverse (reduction_list
, create_loads_for_reductions
, ld_st_data
);
975 /* Callback for htab_traverse. Store the neutral value for the
976 particular reduction's operation, e.g. 0 for PLUS_EXPR,
977 1 for MULT_EXPR, etc. into the reduction field.
978 The reduction is specified in SLOT. The store information is
982 create_stores_for_reduction (void **slot
, void *data
)
984 struct reduction_info
*const red
= (struct reduction_info
*) *slot
;
985 struct clsn_data
*const clsn_data
= (struct clsn_data
*) data
;
988 gimple_stmt_iterator gsi
;
989 tree type
= TREE_TYPE (gimple_assign_lhs (red
->reduc_stmt
));
991 gsi
= gsi_last_bb (clsn_data
->store_bb
);
992 t
= build3 (COMPONENT_REF
, type
, clsn_data
->store
, red
->field
, NULL_TREE
);
993 stmt
= gimple_build_assign (t
, red
->initial_value
);
994 mark_virtual_ops_for_renaming (stmt
);
995 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1000 /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
1001 store to a field of STORE in STORE_BB for the ssa name and its duplicate
1002 specified in SLOT. */
1005 create_loads_and_stores_for_name (void **slot
, void *data
)
1007 struct name_to_copy_elt
*const elt
= (struct name_to_copy_elt
*) *slot
;
1008 struct clsn_data
*const clsn_data
= (struct clsn_data
*) data
;
1011 gimple_stmt_iterator gsi
;
1012 tree type
= TREE_TYPE (elt
->new_name
);
1015 gsi
= gsi_last_bb (clsn_data
->store_bb
);
1016 t
= build3 (COMPONENT_REF
, type
, clsn_data
->store
, elt
->field
, NULL_TREE
);
1017 stmt
= gimple_build_assign (t
, ssa_name (elt
->version
));
1018 mark_virtual_ops_for_renaming (stmt
);
1019 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1021 gsi
= gsi_last_bb (clsn_data
->load_bb
);
1022 load_struct
= build_simple_mem_ref (clsn_data
->load
);
1023 t
= build3 (COMPONENT_REF
, type
, load_struct
, elt
->field
, NULL_TREE
);
1024 stmt
= gimple_build_assign (elt
->new_name
, t
);
1025 SSA_NAME_DEF_STMT (elt
->new_name
) = stmt
;
1026 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1031 /* Moves all the variables used in LOOP and defined outside of it (including
1032 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1033 name) to a structure created for this purpose. The code
1041 is transformed this way:
1056 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1057 pointer `new' is intentionally not initialized (the loop will be split to a
1058 separate function later, and `new' will be initialized from its arguments).
1059 LD_ST_DATA holds information about the shared data structure used to pass
1060 information among the threads. It is initialized here, and
1061 gen_parallel_loop will pass it to create_call_for_reduction that
1062 needs this information. REDUCTION_LIST describes the reductions
1066 separate_decls_in_region (edge entry
, edge exit
, htab_t reduction_list
,
1067 tree
*arg_struct
, tree
*new_arg_struct
,
1068 struct clsn_data
*ld_st_data
)
1071 basic_block bb1
= split_edge (entry
);
1072 basic_block bb0
= single_pred (bb1
);
1073 htab_t name_copies
= htab_create (10, name_to_copy_elt_hash
,
1074 name_to_copy_elt_eq
, free
);
1075 htab_t decl_copies
= htab_create (10, int_tree_map_hash
, int_tree_map_eq
,
1078 tree type
, type_name
, nvar
;
1079 gimple_stmt_iterator gsi
;
1080 struct clsn_data clsn_data
;
1081 VEC (basic_block
, heap
) *body
= VEC_alloc (basic_block
, heap
, 3);
1083 basic_block entry_bb
= bb1
;
1084 basic_block exit_bb
= exit
->dest
;
1085 bool has_debug_stmt
= false;
1087 entry
= single_succ_edge (entry_bb
);
1088 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
1090 for (i
= 0; VEC_iterate (basic_block
, body
, i
, bb
); i
++)
1092 if (bb
!= entry_bb
&& bb
!= exit_bb
)
1094 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1095 separate_decls_in_region_stmt (entry
, exit
, gsi_stmt (gsi
),
1096 name_copies
, decl_copies
);
1098 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1100 gimple stmt
= gsi_stmt (gsi
);
1102 if (is_gimple_debug (stmt
))
1103 has_debug_stmt
= true;
1105 separate_decls_in_region_stmt (entry
, exit
, stmt
,
1106 name_copies
, decl_copies
);
1111 /* Now process debug bind stmts. We must not create decls while
1112 processing debug stmts, so we defer their processing so as to
1113 make sure we will have debug info for as many variables as
1114 possible (all of those that were dealt with in the loop above),
1115 and discard those for which we know there's nothing we can
1118 for (i
= 0; VEC_iterate (basic_block
, body
, i
, bb
); i
++)
1119 if (bb
!= entry_bb
&& bb
!= exit_bb
)
1121 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
1123 gimple stmt
= gsi_stmt (gsi
);
1125 if (gimple_debug_bind_p (stmt
))
1127 if (separate_decls_in_region_debug_bind (stmt
,
1131 gsi_remove (&gsi
, true);
1140 VEC_free (basic_block
, heap
, body
);
1142 if (htab_elements (name_copies
) == 0 && htab_elements (reduction_list
) == 0)
1144 /* It may happen that there is nothing to copy (if there are only
1145 loop carried and external variables in the loop). */
1147 *new_arg_struct
= NULL
;
1151 /* Create the type for the structure to store the ssa names to. */
1152 type
= lang_hooks
.types
.make_type (RECORD_TYPE
);
1153 type_name
= build_decl (BUILTINS_LOCATION
,
1154 TYPE_DECL
, create_tmp_var_name (".paral_data"),
1156 TYPE_NAME (type
) = type_name
;
1158 htab_traverse (name_copies
, add_field_for_name
, type
);
1159 if (reduction_list
&& htab_elements (reduction_list
) > 0)
1161 /* Create the fields for reductions. */
1162 htab_traverse (reduction_list
, add_field_for_reduction
,
1167 /* Create the loads and stores. */
1168 *arg_struct
= create_tmp_var (type
, ".paral_data_store");
1169 add_referenced_var (*arg_struct
);
1170 nvar
= create_tmp_var (build_pointer_type (type
), ".paral_data_load");
1171 add_referenced_var (nvar
);
1172 *new_arg_struct
= make_ssa_name (nvar
, NULL
);
1174 ld_st_data
->store
= *arg_struct
;
1175 ld_st_data
->load
= *new_arg_struct
;
1176 ld_st_data
->store_bb
= bb0
;
1177 ld_st_data
->load_bb
= bb1
;
1179 htab_traverse (name_copies
, create_loads_and_stores_for_name
,
1182 /* Load the calculation from memory (after the join of the threads). */
1184 if (reduction_list
&& htab_elements (reduction_list
) > 0)
1186 htab_traverse (reduction_list
, create_stores_for_reduction
,
1188 clsn_data
.load
= make_ssa_name (nvar
, NULL
);
1189 clsn_data
.load_bb
= exit
->dest
;
1190 clsn_data
.store
= ld_st_data
->store
;
1191 create_final_loads_for_reduction (reduction_list
, &clsn_data
);
1195 htab_delete (decl_copies
);
1196 htab_delete (name_copies
);
1199 /* Bitmap containing uids of functions created by parallelization. We cannot
1200 allocate it from the default obstack, as it must live across compilation
1201 of several functions; we make it gc allocated instead. */
1203 static GTY(()) bitmap parallelized_functions
;
1205 /* Returns true if FN was created by create_loop_fn. */
1208 parallelized_function_p (tree fn
)
1210 if (!parallelized_functions
|| !DECL_ARTIFICIAL (fn
))
1213 return bitmap_bit_p (parallelized_functions
, DECL_UID (fn
));
1216 /* Creates and returns an empty function that will receive the body of
1217 a parallelized loop. */
1220 create_loop_fn (void)
1224 tree decl
, type
, name
, t
;
1225 struct function
*act_cfun
= cfun
;
1226 static unsigned loopfn_num
;
1228 snprintf (buf
, 100, "%s.$loopfn", current_function_name ());
1229 ASM_FORMAT_PRIVATE_NAME (tname
, buf
, loopfn_num
++);
1230 clean_symbol_name (tname
);
1231 name
= get_identifier (tname
);
1232 type
= build_function_type_list (void_type_node
, ptr_type_node
, NULL_TREE
);
1234 decl
= build_decl (BUILTINS_LOCATION
,
1235 FUNCTION_DECL
, name
, type
);
1236 if (!parallelized_functions
)
1237 parallelized_functions
= BITMAP_GGC_ALLOC ();
1238 bitmap_set_bit (parallelized_functions
, DECL_UID (decl
));
1240 TREE_STATIC (decl
) = 1;
1241 TREE_USED (decl
) = 1;
1242 DECL_ARTIFICIAL (decl
) = 1;
1243 DECL_IGNORED_P (decl
) = 0;
1244 TREE_PUBLIC (decl
) = 0;
1245 DECL_UNINLINABLE (decl
) = 1;
1246 DECL_EXTERNAL (decl
) = 0;
1247 DECL_CONTEXT (decl
) = NULL_TREE
;
1248 DECL_INITIAL (decl
) = make_node (BLOCK
);
1250 t
= build_decl (BUILTINS_LOCATION
,
1251 RESULT_DECL
, NULL_TREE
, void_type_node
);
1252 DECL_ARTIFICIAL (t
) = 1;
1253 DECL_IGNORED_P (t
) = 1;
1254 DECL_RESULT (decl
) = t
;
1256 t
= build_decl (BUILTINS_LOCATION
,
1257 PARM_DECL
, get_identifier (".paral_data_param"),
1259 DECL_ARTIFICIAL (t
) = 1;
1260 DECL_ARG_TYPE (t
) = ptr_type_node
;
1261 DECL_CONTEXT (t
) = decl
;
1263 DECL_ARGUMENTS (decl
) = t
;
1265 allocate_struct_function (decl
, false);
1267 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1269 set_cfun (act_cfun
);
1274 /* Moves the exit condition of LOOP to the beginning of its header, and
1275 duplicates the part of the last iteration that gets disabled to the
1276 exit of the loop. NIT is the number of iterations of the loop
1277 (used to initialize the variables in the duplicated part).
1279 TODO: the common case is that latch of the loop is empty and immediately
1280 follows the loop exit. In this case, it would be better not to copy the
1281 body of the loop, but only move the entry of the loop directly before the
1282 exit check and increase the number of iterations of the loop by one.
1283 This may need some additional preconditioning in case NIT = ~0.
1284 REDUCTION_LIST describes the reductions in LOOP. */
1287 transform_to_exit_first_loop (struct loop
*loop
, htab_t reduction_list
, tree nit
)
1289 basic_block
*bbs
, *nbbs
, ex_bb
, orig_header
;
1292 edge exit
= single_dom_exit (loop
), hpred
;
1293 tree control
, control_name
, res
, t
;
1294 gimple phi
, nphi
, cond_stmt
, stmt
, cond_nit
;
1295 gimple_stmt_iterator gsi
;
1298 split_block_after_labels (loop
->header
);
1299 orig_header
= single_succ (loop
->header
);
1300 hpred
= single_succ_edge (loop
->header
);
1302 cond_stmt
= last_stmt (exit
->src
);
1303 control
= gimple_cond_lhs (cond_stmt
);
1304 gcc_assert (gimple_cond_rhs (cond_stmt
) == nit
);
1306 /* Make sure that we have phi nodes on exit for all loop header phis
1307 (create_parallel_loop requires that). */
1308 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1310 phi
= gsi_stmt (gsi
);
1311 res
= PHI_RESULT (phi
);
1312 t
= make_ssa_name (SSA_NAME_VAR (res
), phi
);
1313 SET_PHI_RESULT (phi
, t
);
1314 nphi
= create_phi_node (res
, orig_header
);
1315 SSA_NAME_DEF_STMT (res
) = nphi
;
1316 add_phi_arg (nphi
, t
, hpred
, UNKNOWN_LOCATION
);
1320 gimple_cond_set_lhs (cond_stmt
, t
);
1321 update_stmt (cond_stmt
);
1325 bbs
= get_loop_body_in_dom_order (loop
);
1327 for (n
= 0; bbs
[n
] != loop
->latch
; n
++)
1329 nbbs
= XNEWVEC (basic_block
, n
);
1330 ok
= gimple_duplicate_sese_tail (single_succ_edge (loop
->header
), exit
,
1337 /* Other than reductions, the only gimple reg that should be copied
1338 out of the loop is the control variable. */
1340 control_name
= NULL_TREE
;
1341 for (gsi
= gsi_start_phis (ex_bb
); !gsi_end_p (gsi
); )
1343 phi
= gsi_stmt (gsi
);
1344 res
= PHI_RESULT (phi
);
1345 if (!is_gimple_reg (res
))
1351 /* Check if it is a part of reduction. If it is,
1352 keep the phi at the reduction's keep_res field. The
1353 PHI_RESULT of this phi is the resulting value of the reduction
1354 variable when exiting the loop. */
1356 exit
= single_dom_exit (loop
);
1358 if (htab_elements (reduction_list
) > 0)
1360 struct reduction_info
*red
;
1362 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1363 red
= reduction_phi (reduction_list
, SSA_NAME_DEF_STMT (val
));
1366 red
->keep_res
= phi
;
1371 gcc_assert (control_name
== NULL_TREE
1372 && SSA_NAME_VAR (res
) == SSA_NAME_VAR (control
));
1374 remove_phi_node (&gsi
, false);
1376 gcc_assert (control_name
!= NULL_TREE
);
1378 /* Initialize the control variable to number of iterations
1379 according to the rhs of the exit condition. */
1380 gsi
= gsi_after_labels (ex_bb
);
1381 cond_nit
= last_stmt (exit
->src
);
1382 nit_1
= gimple_cond_rhs (cond_nit
);
1383 nit_1
= force_gimple_operand_gsi (&gsi
,
1384 fold_convert (TREE_TYPE (control_name
), nit_1
),
1385 false, NULL_TREE
, false, GSI_SAME_STMT
);
1386 stmt
= gimple_build_assign (control_name
, nit_1
);
1387 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1388 SSA_NAME_DEF_STMT (control_name
) = stmt
;
1391 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
1392 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
1393 NEW_DATA is the variable that should be initialized from the argument
1394 of LOOP_FN. N_THREADS is the requested number of threads. Returns the
1395 basic block containing GIMPLE_OMP_PARALLEL tree. */
1398 create_parallel_loop (struct loop
*loop
, tree loop_fn
, tree data
,
1399 tree new_data
, unsigned n_threads
)
1401 gimple_stmt_iterator gsi
;
1402 basic_block bb
, paral_bb
, for_bb
, ex_bb
;
1404 gimple stmt
, for_stmt
, phi
, cond_stmt
;
1405 tree cvar
, cvar_init
, initvar
, cvar_next
, cvar_base
, type
;
1406 edge exit
, nexit
, guard
, end
, e
;
1408 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
1409 bb
= loop_preheader_edge (loop
)->src
;
1410 paral_bb
= single_pred (bb
);
1411 gsi
= gsi_last_bb (paral_bb
);
1413 t
= build_omp_clause (BUILTINS_LOCATION
, OMP_CLAUSE_NUM_THREADS
);
1414 OMP_CLAUSE_NUM_THREADS_EXPR (t
)
1415 = build_int_cst (integer_type_node
, n_threads
);
1416 stmt
= gimple_build_omp_parallel (NULL
, t
, loop_fn
, data
);
1418 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1420 /* Initialize NEW_DATA. */
1423 gsi
= gsi_after_labels (bb
);
1425 param
= make_ssa_name (DECL_ARGUMENTS (loop_fn
), NULL
);
1426 stmt
= gimple_build_assign (param
, build_fold_addr_expr (data
));
1427 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1428 SSA_NAME_DEF_STMT (param
) = stmt
;
1430 stmt
= gimple_build_assign (new_data
,
1431 fold_convert (TREE_TYPE (new_data
), param
));
1432 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1433 SSA_NAME_DEF_STMT (new_data
) = stmt
;
1436 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
1437 bb
= split_loop_exit_edge (single_dom_exit (loop
));
1438 gsi
= gsi_last_bb (bb
);
1439 gsi_insert_after (&gsi
, gimple_build_omp_return (false), GSI_NEW_STMT
);
1441 /* Extract data for GIMPLE_OMP_FOR. */
1442 gcc_assert (loop
->header
== single_dom_exit (loop
)->src
);
1443 cond_stmt
= last_stmt (loop
->header
);
1445 cvar
= gimple_cond_lhs (cond_stmt
);
1446 cvar_base
= SSA_NAME_VAR (cvar
);
1447 phi
= SSA_NAME_DEF_STMT (cvar
);
1448 cvar_init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1449 initvar
= make_ssa_name (cvar_base
, NULL
);
1450 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, loop_preheader_edge (loop
)),
1452 cvar_next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
1454 gsi
= gsi_last_bb (loop
->latch
);
1455 gcc_assert (gsi_stmt (gsi
) == SSA_NAME_DEF_STMT (cvar_next
));
1456 gsi_remove (&gsi
, true);
1459 for_bb
= split_edge (loop_preheader_edge (loop
));
1460 ex_bb
= split_loop_exit_edge (single_dom_exit (loop
));
1461 extract_true_false_edges_from_block (loop
->header
, &nexit
, &exit
);
1462 gcc_assert (exit
== single_dom_exit (loop
));
1464 guard
= make_edge (for_bb
, ex_bb
, 0);
1465 single_succ_edge (loop
->latch
)->flags
= 0;
1466 end
= make_edge (loop
->latch
, ex_bb
, EDGE_FALLTHRU
);
1467 for (gsi
= gsi_start_phis (ex_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1469 source_location locus
;
1471 phi
= gsi_stmt (gsi
);
1472 stmt
= SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi
, exit
));
1474 def
= PHI_ARG_DEF_FROM_EDGE (stmt
, loop_preheader_edge (loop
));
1475 locus
= gimple_phi_arg_location_from_edge (stmt
,
1476 loop_preheader_edge (loop
));
1477 add_phi_arg (phi
, def
, guard
, locus
);
1479 def
= PHI_ARG_DEF_FROM_EDGE (stmt
, loop_latch_edge (loop
));
1480 locus
= gimple_phi_arg_location_from_edge (stmt
, loop_latch_edge (loop
));
1481 add_phi_arg (phi
, def
, end
, locus
);
1483 e
= redirect_edge_and_branch (exit
, nexit
->dest
);
1484 PENDING_STMT (e
) = NULL
;
1486 /* Emit GIMPLE_OMP_FOR. */
1487 gimple_cond_set_lhs (cond_stmt
, cvar_base
);
1488 type
= TREE_TYPE (cvar
);
1489 t
= build_omp_clause (BUILTINS_LOCATION
, OMP_CLAUSE_SCHEDULE
);
1490 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_STATIC
;
1492 for_stmt
= gimple_build_omp_for (NULL
, t
, 1, NULL
);
1493 gimple_omp_for_set_index (for_stmt
, 0, initvar
);
1494 gimple_omp_for_set_initial (for_stmt
, 0, cvar_init
);
1495 gimple_omp_for_set_final (for_stmt
, 0, gimple_cond_rhs (cond_stmt
));
1496 gimple_omp_for_set_cond (for_stmt
, 0, gimple_cond_code (cond_stmt
));
1497 gimple_omp_for_set_incr (for_stmt
, 0, build2 (PLUS_EXPR
, type
,
1499 build_int_cst (type
, 1)));
1501 gsi
= gsi_last_bb (for_bb
);
1502 gsi_insert_after (&gsi
, for_stmt
, GSI_NEW_STMT
);
1503 SSA_NAME_DEF_STMT (initvar
) = for_stmt
;
1505 /* Emit GIMPLE_OMP_CONTINUE. */
1506 gsi
= gsi_last_bb (loop
->latch
);
1507 stmt
= gimple_build_omp_continue (cvar_next
, cvar
);
1508 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1509 SSA_NAME_DEF_STMT (cvar_next
) = stmt
;
1511 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
1512 gsi
= gsi_last_bb (ex_bb
);
1513 gsi_insert_after (&gsi
, gimple_build_omp_return (true), GSI_NEW_STMT
);
1518 /* Generates code to execute the iterations of LOOP in N_THREADS
1519 threads in parallel.
1521 NITER describes number of iterations of LOOP.
1522 REDUCTION_LIST describes the reductions existent in the LOOP. */
1525 gen_parallel_loop (struct loop
*loop
, htab_t reduction_list
,
1526 unsigned n_threads
, struct tree_niter_desc
*niter
)
1529 tree many_iterations_cond
, type
, nit
;
1530 tree arg_struct
, new_arg_struct
;
1532 basic_block parallel_head
;
1534 struct clsn_data clsn_data
;
1539 ---------------------------------------------------------------------
1542 IV = phi (INIT, IV + STEP)
1548 ---------------------------------------------------------------------
1550 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
1551 we generate the following code:
1553 ---------------------------------------------------------------------
1556 || NITER < MIN_PER_THREAD * N_THREADS)
1560 store all local loop-invariant variables used in body of the loop to DATA.
1561 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
1562 load the variables from DATA.
1563 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
1566 GIMPLE_OMP_CONTINUE;
1567 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
1568 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
1574 IV = phi (INIT, IV + STEP)
1585 /* Create two versions of the loop -- in the old one, we know that the
1586 number of iterations is large enough, and we will transform it into the
1587 loop that will be split to loop_fn, the new one will be used for the
1588 remaining iterations. */
1590 type
= TREE_TYPE (niter
->niter
);
1591 nit
= force_gimple_operand (unshare_expr (niter
->niter
), &stmts
, true,
1594 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1596 many_iterations_cond
=
1597 fold_build2 (GE_EXPR
, boolean_type_node
,
1598 nit
, build_int_cst (type
, MIN_PER_THREAD
* n_threads
));
1599 many_iterations_cond
1600 = fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1601 invert_truthvalue (unshare_expr (niter
->may_be_zero
)),
1602 many_iterations_cond
);
1603 many_iterations_cond
1604 = force_gimple_operand (many_iterations_cond
, &stmts
, false, NULL_TREE
);
1606 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1607 if (!is_gimple_condexpr (many_iterations_cond
))
1609 many_iterations_cond
1610 = force_gimple_operand (many_iterations_cond
, &stmts
,
1613 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1616 initialize_original_copy_tables ();
1618 /* We assume that the loop usually iterates a lot. */
1619 prob
= 4 * REG_BR_PROB_BASE
/ 5;
1620 loop_version (loop
, many_iterations_cond
, NULL
,
1621 prob
, prob
, REG_BR_PROB_BASE
- prob
, true);
1622 update_ssa (TODO_update_ssa
);
1623 free_original_copy_tables ();
1625 /* Base all the induction variables in LOOP on a single control one. */
1626 canonicalize_loop_ivs (loop
, &nit
, true);
1628 /* Ensure that the exit condition is the first statement in the loop. */
1629 transform_to_exit_first_loop (loop
, reduction_list
, nit
);
1631 /* Generate initializations for reductions. */
1632 if (htab_elements (reduction_list
) > 0)
1633 htab_traverse (reduction_list
, initialize_reductions
, loop
);
1635 /* Eliminate the references to local variables from the loop. */
1636 gcc_assert (single_exit (loop
));
1637 entry
= loop_preheader_edge (loop
);
1638 exit
= single_dom_exit (loop
);
1640 eliminate_local_variables (entry
, exit
);
1641 /* In the old loop, move all variables non-local to the loop to a structure
1642 and back, and create separate decls for the variables used in loop. */
1643 separate_decls_in_region (entry
, exit
, reduction_list
, &arg_struct
,
1644 &new_arg_struct
, &clsn_data
);
1646 /* Create the parallel constructs. */
1647 parallel_head
= create_parallel_loop (loop
, create_loop_fn (), arg_struct
,
1648 new_arg_struct
, n_threads
);
1649 if (htab_elements (reduction_list
) > 0)
1650 create_call_for_reduction (loop
, reduction_list
, &clsn_data
);
1654 /* Cancel the loop (it is simpler to do it here rather than to teach the
1655 expander to do it). */
1656 cancel_loop_tree (loop
);
1658 /* Free loop bound estimations that could contain references to
1659 removed statements. */
1660 FOR_EACH_LOOP (li
, loop
, 0)
1661 free_numbers_of_iterations_estimates_loop (loop
);
1663 /* Expand the parallel constructs. We do it directly here instead of running
1664 a separate expand_omp pass, since it is more efficient, and less likely to
1665 cause troubles with further analyses not being able to deal with the
1668 omp_expand_local (parallel_head
);
1671 /* Returns true when LOOP contains vector phi nodes. */
1674 loop_has_vector_phi_nodes (struct loop
*loop ATTRIBUTE_UNUSED
)
1677 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
1678 gimple_stmt_iterator gsi
;
1681 for (i
= 0; i
< loop
->num_nodes
; i
++)
1682 for (gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
1683 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi_stmt (gsi
)))) == VECTOR_TYPE
)
1692 /* Create a reduction_info struct, initialize it with REDUC_STMT
1693 and PHI, insert it to the REDUCTION_LIST. */
1696 build_new_reduction (htab_t reduction_list
, gimple reduc_stmt
, gimple phi
)
1699 struct reduction_info
*new_reduction
;
1701 gcc_assert (reduc_stmt
);
1703 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1706 "Detected reduction. reduction stmt is: \n");
1707 print_gimple_stmt (dump_file
, reduc_stmt
, 0, 0);
1708 fprintf (dump_file
, "\n");
1711 new_reduction
= XCNEW (struct reduction_info
);
1713 new_reduction
->reduc_stmt
= reduc_stmt
;
1714 new_reduction
->reduc_phi
= phi
;
1715 new_reduction
->reduction_code
= gimple_assign_rhs_code (reduc_stmt
);
1716 slot
= htab_find_slot (reduction_list
, new_reduction
, INSERT
);
1717 *slot
= new_reduction
;
1720 /* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
1723 gather_scalar_reductions (loop_p loop
, htab_t reduction_list
)
1725 gimple_stmt_iterator gsi
;
1726 loop_vec_info simple_loop_info
;
1729 simple_loop_info
= vect_analyze_loop_form (loop
);
1731 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1733 gimple phi
= gsi_stmt (gsi
);
1735 tree res
= PHI_RESULT (phi
);
1738 if (!is_gimple_reg (res
))
1741 if (!simple_iv (loop
, loop
, res
, &iv
, true)
1742 && simple_loop_info
)
1744 gimple reduc_stmt
= vect_force_simple_reduction (simple_loop_info
,
1747 if (reduc_stmt
&& !double_reduc
)
1748 build_new_reduction (reduction_list
, reduc_stmt
, phi
);
1751 destroy_loop_vec_info (simple_loop_info
, true);
1754 /* Try to initialize NITER for code generation part. */
1757 try_get_loop_niter (loop_p loop
, struct tree_niter_desc
*niter
)
1759 edge exit
= single_dom_exit (loop
);
1763 /* We need to know # of iterations, and there should be no uses of values
1764 defined inside loop outside of it, unless the values are invariants of
1766 if (!number_of_iterations_exit (loop
, exit
, niter
, false))
1768 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1769 fprintf (dump_file
, " FAILED: number of iterations not known\n");
1776 /* Try to initialize REDUCTION_LIST for code generation part.
1777 REDUCTION_LIST describes the reductions. */
1780 try_create_reduction_list (loop_p loop
, htab_t reduction_list
)
1782 edge exit
= single_dom_exit (loop
);
1783 gimple_stmt_iterator gsi
;
1787 gather_scalar_reductions (loop
, reduction_list
);
1790 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1792 gimple phi
= gsi_stmt (gsi
);
1793 struct reduction_info
*red
;
1794 imm_use_iterator imm_iter
;
1795 use_operand_p use_p
;
1797 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1799 if (is_gimple_reg (val
))
1801 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1803 fprintf (dump_file
, "phi is ");
1804 print_gimple_stmt (dump_file
, phi
, 0, 0);
1805 fprintf (dump_file
, "arg of phi to exit: value ");
1806 print_generic_expr (dump_file
, val
, 0);
1807 fprintf (dump_file
, " used outside loop\n");
1809 " checking if it a part of reduction pattern: \n");
1811 if (htab_elements (reduction_list
) == 0)
1813 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1815 " FAILED: it is not a part of reduction.\n");
1819 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, val
)
1821 if (flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
1823 reduc_phi
= USE_STMT (use_p
);
1827 red
= reduction_phi (reduction_list
, reduc_phi
);
1830 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1832 " FAILED: it is not a part of reduction.\n");
1835 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1837 fprintf (dump_file
, "reduction phi is ");
1838 print_gimple_stmt (dump_file
, red
->reduc_phi
, 0, 0);
1839 fprintf (dump_file
, "reduction stmt is ");
1840 print_gimple_stmt (dump_file
, red
->reduc_stmt
, 0, 0);
1845 /* The iterations of the loop may communicate only through bivs whose
1846 iteration space can be distributed efficiently. */
1847 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1849 gimple phi
= gsi_stmt (gsi
);
1850 tree def
= PHI_RESULT (phi
);
1853 if (is_gimple_reg (def
) && !simple_iv (loop
, loop
, def
, &iv
, true))
1855 struct reduction_info
*red
;
1857 red
= reduction_phi (reduction_list
, phi
);
1860 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1862 " FAILED: scalar dependency between iterations\n");
1872 /* Detect parallel loops and generate parallel code using libgomp
1873 primitives. Returns true if some loop was parallelized, false
1877 parallelize_loops (void)
1879 unsigned n_threads
= flag_tree_parallelize_loops
;
1880 bool changed
= false;
1882 struct tree_niter_desc niter_desc
;
1884 htab_t reduction_list
;
1885 struct obstack parloop_obstack
;
1886 HOST_WIDE_INT estimated
;
1889 /* Do not parallelize loops in the functions created by parallelization. */
1890 if (parallelized_function_p (cfun
->decl
))
1892 if (cfun
->has_nonlocal_label
)
1895 gcc_obstack_init (&parloop_obstack
);
1896 reduction_list
= htab_create (10, reduction_info_hash
,
1897 reduction_info_eq
, free
);
1898 init_stmt_vec_info_vec ();
1900 FOR_EACH_LOOP (li
, loop
, 0)
1902 htab_empty (reduction_list
);
1903 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1905 fprintf (dump_file
, "Trying loop %d as candidate\n",loop
->num
);
1907 fprintf (dump_file
, "loop %d is not innermost\n",loop
->num
);
1909 fprintf (dump_file
, "loop %d is innermost\n",loop
->num
);
1912 /* If we use autopar in graphite pass, we use its marked dependency
1913 checking results. */
1914 if (flag_loop_parallelize_all
&& !loop
->can_be_parallel
)
1916 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1917 fprintf (dump_file
, "loop is not parallel according to graphite\n");
1921 if (!single_dom_exit (loop
))
1924 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1925 fprintf (dump_file
, "loop is !single_dom_exit\n");
1930 if (/* And of course, the loop must be parallelizable. */
1931 !can_duplicate_loop_p (loop
)
1932 || loop_has_blocks_with_irreducible_flag (loop
)
1933 || (loop_preheader_edge (loop
)->src
->flags
& BB_IRREDUCIBLE_LOOP
)
1934 /* FIXME: the check for vector phi nodes could be removed. */
1935 || loop_has_vector_phi_nodes (loop
))
1937 estimated
= estimated_loop_iterations_int (loop
, false);
1938 /* FIXME: Bypass this check as graphite doesn't update the
1939 count and frequency correctly now. */
1940 if (!flag_loop_parallelize_all
1942 && estimated
<= (HOST_WIDE_INT
) n_threads
* MIN_PER_THREAD
)
1943 /* Do not bother with loops in cold areas. */
1944 || optimize_loop_nest_for_size_p (loop
)))
1947 if (!try_get_loop_niter (loop
, &niter_desc
))
1950 if (!try_create_reduction_list (loop
, reduction_list
))
1953 if (!flag_loop_parallelize_all
1954 && !loop_parallel_p (loop
, &parloop_obstack
))
1958 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1961 fprintf (dump_file
, "parallelizing outer loop %d\n",loop
->header
->index
);
1963 fprintf (dump_file
, "parallelizing inner loop %d\n",loop
->header
->index
);
1964 loop_loc
= find_loop_location (loop
);
1965 if (loop_loc
!= UNKNOWN_LOC
)
1966 fprintf (dump_file
, "\nloop at %s:%d: ",
1967 LOC_FILE (loop_loc
), LOC_LINE (loop_loc
));
1969 gen_parallel_loop (loop
, reduction_list
,
1970 n_threads
, &niter_desc
);
1971 verify_flow_info ();
1972 verify_dominators (CDI_DOMINATORS
);
1973 verify_loop_structure ();
1974 verify_loop_closed_ssa (true);
1977 free_stmt_vec_info_vec ();
1978 htab_delete (reduction_list
);
1979 obstack_free (&parloop_obstack
, NULL
);
1981 /* Parallelization will cause new function calls to be inserted through
1982 which local variables will escape. Reset the points-to solution
1985 pt_solution_reset (&cfun
->gimple_df
->escaped
);
1990 #include "gt-tree-parloops.h"