1 /* Loop autoparallelization.
2 Copyright (C) 2006-2013 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
4 Zdenek Dvorak <dvorakz@suse.cz> and Razya Ladelsky <razya@il.ibm.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
28 #include "gimple-iterator.h"
29 #include "gimplify-me.h"
30 #include "gimple-walk.h"
31 #include "gimple-ssa.h"
33 #include "tree-phinodes.h"
34 #include "ssa-iterators.h"
35 #include "tree-ssanames.h"
36 #include "tree-ssa-loop-ivopts.h"
37 #include "tree-ssa-loop-manip.h"
38 #include "tree-ssa-loop-niter.h"
39 #include "tree-ssa-loop.h"
40 #include "tree-into-ssa.h"
42 #include "tree-data-ref.h"
43 #include "tree-scalar-evolution.h"
44 #include "gimple-pretty-print.h"
45 #include "tree-pass.h"
46 #include "langhooks.h"
47 #include "tree-vectorizer.h"
48 #include "tree-hasher.h"
49 #include "tree-parloops.h"
52 /* This pass tries to distribute iterations of loops into several threads.
53 The implementation is straightforward -- for each loop we test whether its
54 iterations are independent, and if it is the case (and some additional
55 conditions regarding profitability and correctness are satisfied), we
56 add GIMPLE_OMP_PARALLEL and GIMPLE_OMP_FOR codes and let omp expansion
59 The most of the complexity is in bringing the code into shape expected
61 -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction
62 variable and that the exit test is at the start of the loop body
63 -- for GIMPLE_OMP_PARALLEL, replacing the references to local addressable
64 variables by accesses through pointers, and breaking up ssa chains
65 by storing the values incoming to the parallelized loop to a structure
66 passed to the new function as an argument (something similar is done
67 in omp gimplification, unfortunately only a small part of the code
71 -- if there are several parallelizable loops in a function, it may be
72 possible to generate the threads just once (using synchronization to
73 ensure that cross-loop dependences are obeyed).
74 -- handling of common reduction patterns for outer loops.
76 More info can also be found at http://gcc.gnu.org/wiki/AutoParInGCC */
79 currently we use vect_force_simple_reduction() to detect reduction patterns.
80 The code transformation will be introduced by an example.
87 for (i = 0; i < N; i++)
97 # sum_29 = PHI <sum_11(5), 1(3)>
98 # i_28 = PHI <i_12(5), 0(3)>
101 sum_11 = D.1795_8 + sum_29;
109 # sum_21 = PHI <sum_11(4)>
110 printf (&"%d"[0], sum_21);
113 after reduction transformation (only relevant parts):
121 # Storing the initial value given by the user. #
123 .paral_data_store.32.sum.27 = 1;
125 #pragma omp parallel num_threads(4)
127 #pragma omp for schedule(static)
129 # The neutral element corresponding to the particular
130 reduction's operation, e.g. 0 for PLUS_EXPR,
131 1 for MULT_EXPR, etc. replaces the user's initial value. #
133 # sum.27_29 = PHI <sum.27_11, 0>
135 sum.27_11 = D.1827_8 + sum.27_29;
139 # Adding this reduction phi is done at create_phi_for_local_result() #
140 # sum.27_56 = PHI <sum.27_11, 0>
143 # Creating the atomic operation is done at
144 create_call_for_reduction_1() #
146 #pragma omp atomic_load
147 D.1839_59 = *&.paral_data_load.33_51->reduction.23;
148 D.1840_60 = sum.27_56 + D.1839_59;
149 #pragma omp atomic_store (D.1840_60);
153 # collecting the result after the join of the threads is done at
154 create_loads_for_reductions().
155 The value computed by the threads is loaded from the
159 .paral_data_load.33_52 = &.paral_data_store.32;
160 sum_37 = .paral_data_load.33_52->sum.27;
161 sum_43 = D.1795_41 + sum_37;
164 # sum_21 = PHI <sum_43, sum_26>
165 printf (&"%d"[0], sum_21);
173 /* Minimal number of iterations of a loop that should be executed in each
175 #define MIN_PER_THREAD 100
177 /* Element of the hashtable, representing a
178 reduction in the current loop. */
179 struct reduction_info
181 gimple reduc_stmt
; /* reduction statement. */
182 gimple reduc_phi
; /* The phi node defining the reduction. */
183 enum tree_code reduction_code
;/* code for the reduction operation. */
184 unsigned reduc_version
; /* SSA_NAME_VERSION of original reduc_phi
186 gimple keep_res
; /* The PHI_RESULT of this phi is the resulting value
187 of the reduction variable when existing the loop. */
188 tree initial_value
; /* The initial value of the reduction var before entering the loop. */
189 tree field
; /* the name of the field in the parloop data structure intended for reduction. */
190 tree init
; /* reduction initialization value. */
191 gimple new_phi
; /* (helper field) Newly created phi node whose result
192 will be passed to the atomic operation. Represents
193 the local result each thread computed for the reduction
197 /* Reduction info hashtable helpers. */
199 struct reduction_hasher
: typed_free_remove
<reduction_info
>
201 typedef reduction_info value_type
;
202 typedef reduction_info compare_type
;
203 static inline hashval_t
hash (const value_type
*);
204 static inline bool equal (const value_type
*, const compare_type
*);
207 /* Equality and hash functions for hashtab code. */
210 reduction_hasher::equal (const value_type
*a
, const compare_type
*b
)
212 return (a
->reduc_phi
== b
->reduc_phi
);
216 reduction_hasher::hash (const value_type
*a
)
218 return a
->reduc_version
;
221 typedef hash_table
<reduction_hasher
> reduction_info_table_type
;
224 static struct reduction_info
*
225 reduction_phi (reduction_info_table_type reduction_list
, gimple phi
)
227 struct reduction_info tmpred
, *red
;
229 if (reduction_list
.elements () == 0 || phi
== NULL
)
232 tmpred
.reduc_phi
= phi
;
233 tmpred
.reduc_version
= gimple_uid (phi
);
234 red
= reduction_list
.find (&tmpred
);
239 /* Element of hashtable of names to copy. */
241 struct name_to_copy_elt
243 unsigned version
; /* The version of the name to copy. */
244 tree new_name
; /* The new name used in the copy. */
245 tree field
; /* The field of the structure used to pass the
249 /* Name copies hashtable helpers. */
251 struct name_to_copy_hasher
: typed_free_remove
<name_to_copy_elt
>
253 typedef name_to_copy_elt value_type
;
254 typedef name_to_copy_elt compare_type
;
255 static inline hashval_t
hash (const value_type
*);
256 static inline bool equal (const value_type
*, const compare_type
*);
259 /* Equality and hash functions for hashtab code. */
262 name_to_copy_hasher::equal (const value_type
*a
, const compare_type
*b
)
264 return a
->version
== b
->version
;
268 name_to_copy_hasher::hash (const value_type
*a
)
270 return (hashval_t
) a
->version
;
273 typedef hash_table
<name_to_copy_hasher
> name_to_copy_table_type
;
275 /* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
276 matrix. Rather than use floats, we simply keep a single DENOMINATOR that
277 represents the denominator for every element in the matrix. */
278 typedef struct lambda_trans_matrix_s
280 lambda_matrix matrix
;
284 } *lambda_trans_matrix
;
285 #define LTM_MATRIX(T) ((T)->matrix)
286 #define LTM_ROWSIZE(T) ((T)->rowsize)
287 #define LTM_COLSIZE(T) ((T)->colsize)
288 #define LTM_DENOMINATOR(T) ((T)->denominator)
290 /* Allocate a new transformation matrix. */
292 static lambda_trans_matrix
293 lambda_trans_matrix_new (int colsize
, int rowsize
,
294 struct obstack
* lambda_obstack
)
296 lambda_trans_matrix ret
;
298 ret
= (lambda_trans_matrix
)
299 obstack_alloc (lambda_obstack
, sizeof (struct lambda_trans_matrix_s
));
300 LTM_MATRIX (ret
) = lambda_matrix_new (rowsize
, colsize
, lambda_obstack
);
301 LTM_ROWSIZE (ret
) = rowsize
;
302 LTM_COLSIZE (ret
) = colsize
;
303 LTM_DENOMINATOR (ret
) = 1;
307 /* Multiply a vector VEC by a matrix MAT.
308 MAT is an M*N matrix, and VEC is a vector with length N. The result
309 is stored in DEST which must be a vector of length M. */
312 lambda_matrix_vector_mult (lambda_matrix matrix
, int m
, int n
,
313 lambda_vector vec
, lambda_vector dest
)
317 lambda_vector_clear (dest
, m
);
318 for (i
= 0; i
< m
; i
++)
319 for (j
= 0; j
< n
; j
++)
320 dest
[i
] += matrix
[i
][j
] * vec
[j
];
323 /* Return true if TRANS is a legal transformation matrix that respects
324 the dependence vectors in DISTS and DIRS. The conservative answer
327 "Wolfe proves that a unimodular transformation represented by the
328 matrix T is legal when applied to a loop nest with a set of
329 lexicographically non-negative distance vectors RDG if and only if
330 for each vector d in RDG, (T.d >= 0) is lexicographically positive.
331 i.e.: if and only if it transforms the lexicographically positive
332 distance vectors to lexicographically positive vectors. Note that
333 a unimodular matrix must transform the zero vector (and only it) to
334 the zero vector." S.Muchnick. */
337 lambda_transform_legal_p (lambda_trans_matrix trans
,
339 vec
<ddr_p
> dependence_relations
)
342 lambda_vector distres
;
343 struct data_dependence_relation
*ddr
;
345 gcc_assert (LTM_COLSIZE (trans
) == nb_loops
346 && LTM_ROWSIZE (trans
) == nb_loops
);
348 /* When there are no dependences, the transformation is correct. */
349 if (dependence_relations
.length () == 0)
352 ddr
= dependence_relations
[0];
356 /* When there is an unknown relation in the dependence_relations, we
357 know that it is no worth looking at this loop nest: give up. */
358 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
361 distres
= lambda_vector_new (nb_loops
);
363 /* For each distance vector in the dependence graph. */
364 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
366 /* Don't care about relations for which we know that there is no
367 dependence, nor about read-read (aka. output-dependences):
368 these data accesses can happen in any order. */
369 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
370 || (DR_IS_READ (DDR_A (ddr
)) && DR_IS_READ (DDR_B (ddr
))))
373 /* Conservatively answer: "this transformation is not valid". */
374 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
377 /* If the dependence could not be captured by a distance vector,
378 conservatively answer that the transform is not valid. */
379 if (DDR_NUM_DIST_VECTS (ddr
) == 0)
382 /* Compute trans.dist_vect */
383 for (j
= 0; j
< DDR_NUM_DIST_VECTS (ddr
); j
++)
385 lambda_matrix_vector_mult (LTM_MATRIX (trans
), nb_loops
, nb_loops
,
386 DDR_DIST_VECT (ddr
, j
), distres
);
388 if (!lambda_vector_lexico_pos (distres
, nb_loops
))
395 /* Data dependency analysis. Returns true if the iterations of LOOP
396 are independent on each other (that is, if we can execute them
400 loop_parallel_p (struct loop
*loop
, struct obstack
* parloop_obstack
)
402 vec
<ddr_p
> dependence_relations
;
403 vec
<data_reference_p
> datarefs
;
404 lambda_trans_matrix trans
;
407 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
409 fprintf (dump_file
, "Considering loop %d\n", loop
->num
);
411 fprintf (dump_file
, "loop is innermost\n");
413 fprintf (dump_file
, "loop NOT innermost\n");
416 /* Check for problems with dependences. If the loop can be reversed,
417 the iterations are independent. */
418 stack_vec
<loop_p
, 3> loop_nest
;
419 datarefs
.create (10);
420 dependence_relations
.create (100);
421 if (! compute_data_dependences_for_loop (loop
, true, &loop_nest
, &datarefs
,
422 &dependence_relations
))
424 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
425 fprintf (dump_file
, " FAILED: cannot analyze data dependencies\n");
429 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
430 dump_data_dependence_relations (dump_file
, dependence_relations
);
432 trans
= lambda_trans_matrix_new (1, 1, parloop_obstack
);
433 LTM_MATRIX (trans
)[0][0] = -1;
435 if (lambda_transform_legal_p (trans
, 1, dependence_relations
))
438 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
439 fprintf (dump_file
, " SUCCESS: may be parallelized\n");
441 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
443 " FAILED: data dependencies exist across iterations\n");
446 free_dependence_relations (dependence_relations
);
447 free_data_refs (datarefs
);
452 /* Return true when LOOP contains basic blocks marked with the
453 BB_IRREDUCIBLE_LOOP flag. */
456 loop_has_blocks_with_irreducible_flag (struct loop
*loop
)
459 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
462 for (i
= 0; i
< loop
->num_nodes
; i
++)
463 if (bbs
[i
]->flags
& BB_IRREDUCIBLE_LOOP
)
472 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
473 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
474 to their addresses that can be reused. The address of OBJ is known to
475 be invariant in the whole function. Other needed statements are placed
479 take_address_of (tree obj
, tree type
, edge entry
,
480 int_tree_htab_type decl_address
, gimple_stmt_iterator
*gsi
)
483 int_tree_map
**dslot
;
484 struct int_tree_map ielt
, *nielt
;
485 tree
*var_p
, name
, addr
;
489 /* Since the address of OBJ is invariant, the trees may be shared.
490 Avoid rewriting unrelated parts of the code. */
491 obj
= unshare_expr (obj
);
493 handled_component_p (*var_p
);
494 var_p
= &TREE_OPERAND (*var_p
, 0))
497 /* Canonicalize the access to base on a MEM_REF. */
499 *var_p
= build_simple_mem_ref (build_fold_addr_expr (*var_p
));
501 /* Assign a canonical SSA name to the address of the base decl used
502 in the address and share it for all accesses and addresses based
504 uid
= DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p
, 0), 0));
506 dslot
= decl_address
.find_slot_with_hash (&ielt
, uid
, INSERT
);
511 addr
= TREE_OPERAND (*var_p
, 0);
513 = get_name (TREE_OPERAND (TREE_OPERAND (*var_p
, 0), 0));
515 name
= make_temp_ssa_name (TREE_TYPE (addr
), NULL
, obj_name
);
517 name
= make_ssa_name (TREE_TYPE (addr
), NULL
);
518 stmt
= gimple_build_assign (name
, addr
);
519 gsi_insert_on_edge_immediate (entry
, stmt
);
521 nielt
= XNEW (struct int_tree_map
);
529 /* Express the address in terms of the canonical SSA name. */
530 TREE_OPERAND (*var_p
, 0) = name
;
532 return build_fold_addr_expr_with_type (obj
, type
);
534 name
= force_gimple_operand (build_addr (obj
, current_function_decl
),
535 &stmts
, true, NULL_TREE
);
536 if (!gimple_seq_empty_p (stmts
))
537 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
539 if (!useless_type_conversion_p (type
, TREE_TYPE (name
)))
541 name
= force_gimple_operand (fold_convert (type
, name
), &stmts
, true,
543 if (!gimple_seq_empty_p (stmts
))
544 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
550 /* Callback for htab_traverse. Create the initialization statement
551 for reduction described in SLOT, and place it at the preheader of
552 the loop described in DATA. */
555 initialize_reductions (reduction_info
**slot
, struct loop
*loop
)
558 tree bvar
, type
, arg
;
561 struct reduction_info
*const reduc
= *slot
;
563 /* Create initialization in preheader:
564 reduction_variable = initialization value of reduction. */
566 /* In the phi node at the header, replace the argument coming
567 from the preheader with the reduction initialization value. */
569 /* Create a new variable to initialize the reduction. */
570 type
= TREE_TYPE (PHI_RESULT (reduc
->reduc_phi
));
571 bvar
= create_tmp_var (type
, "reduction");
573 c
= build_omp_clause (gimple_location (reduc
->reduc_stmt
),
574 OMP_CLAUSE_REDUCTION
);
575 OMP_CLAUSE_REDUCTION_CODE (c
) = reduc
->reduction_code
;
576 OMP_CLAUSE_DECL (c
) = SSA_NAME_VAR (gimple_assign_lhs (reduc
->reduc_stmt
));
578 init
= omp_reduction_init (c
, TREE_TYPE (bvar
));
581 /* Replace the argument representing the initialization value
582 with the initialization value for the reduction (neutral
583 element for the particular operation, e.g. 0 for PLUS_EXPR,
584 1 for MULT_EXPR, etc).
585 Keep the old value in a new variable "reduction_initial",
586 that will be taken in consideration after the parallel
587 computing is done. */
589 e
= loop_preheader_edge (loop
);
590 arg
= PHI_ARG_DEF_FROM_EDGE (reduc
->reduc_phi
, e
);
591 /* Create new variable to hold the initial value. */
593 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
594 (reduc
->reduc_phi
, loop_preheader_edge (loop
)), init
);
595 reduc
->initial_value
= arg
;
601 struct walk_stmt_info info
;
603 int_tree_htab_type decl_address
;
604 gimple_stmt_iterator
*gsi
;
609 /* Eliminates references to local variables in *TP out of the single
610 entry single exit region starting at DTA->ENTRY.
611 DECL_ADDRESS contains addresses of the references that had their
612 address taken already. If the expression is changed, CHANGED is
613 set to true. Callback for walk_tree. */
616 eliminate_local_variables_1 (tree
*tp
, int *walk_subtrees
, void *data
)
618 struct elv_data
*const dta
= (struct elv_data
*) data
;
619 tree t
= *tp
, var
, addr
, addr_type
, type
, obj
;
625 if (!SSA_VAR_P (t
) || DECL_EXTERNAL (t
))
628 type
= TREE_TYPE (t
);
629 addr_type
= build_pointer_type (type
);
630 addr
= take_address_of (t
, addr_type
, dta
->entry
, dta
->decl_address
,
632 if (dta
->gsi
== NULL
&& addr
== NULL_TREE
)
638 *tp
= build_simple_mem_ref (addr
);
644 if (TREE_CODE (t
) == ADDR_EXPR
)
646 /* ADDR_EXPR may appear in two contexts:
647 -- as a gimple operand, when the address taken is a function invariant
648 -- as gimple rhs, when the resulting address in not a function
650 We do not need to do anything special in the latter case (the base of
651 the memory reference whose address is taken may be replaced in the
652 DECL_P case). The former case is more complicated, as we need to
653 ensure that the new address is still a gimple operand. Thus, it
654 is not sufficient to replace just the base of the memory reference --
655 we need to move the whole computation of the address out of the
657 if (!is_gimple_val (t
))
661 obj
= TREE_OPERAND (t
, 0);
662 var
= get_base_address (obj
);
663 if (!var
|| !SSA_VAR_P (var
) || DECL_EXTERNAL (var
))
666 addr_type
= TREE_TYPE (t
);
667 addr
= take_address_of (obj
, addr_type
, dta
->entry
, dta
->decl_address
,
669 if (dta
->gsi
== NULL
&& addr
== NULL_TREE
)
686 /* Moves the references to local variables in STMT at *GSI out of the single
687 entry single exit region starting at ENTRY. DECL_ADDRESS contains
688 addresses of the references that had their address taken
692 eliminate_local_variables_stmt (edge entry
, gimple_stmt_iterator
*gsi
,
693 int_tree_htab_type decl_address
)
696 gimple stmt
= gsi_stmt (*gsi
);
698 memset (&dta
.info
, '\0', sizeof (dta
.info
));
700 dta
.decl_address
= decl_address
;
704 if (gimple_debug_bind_p (stmt
))
707 walk_tree (gimple_debug_bind_get_value_ptr (stmt
),
708 eliminate_local_variables_1
, &dta
.info
, NULL
);
711 gimple_debug_bind_reset_value (stmt
);
715 else if (gimple_clobber_p (stmt
))
717 stmt
= gimple_build_nop ();
718 gsi_replace (gsi
, stmt
, false);
724 walk_gimple_op (stmt
, eliminate_local_variables_1
, &dta
.info
);
731 /* Eliminates the references to local variables from the single entry
732 single exit region between the ENTRY and EXIT edges.
735 1) Taking address of a local variable -- these are moved out of the
736 region (and temporary variable is created to hold the address if
739 2) Dereferencing a local variable -- these are replaced with indirect
743 eliminate_local_variables (edge entry
, edge exit
)
746 stack_vec
<basic_block
, 3> body
;
748 gimple_stmt_iterator gsi
;
749 bool has_debug_stmt
= false;
750 int_tree_htab_type decl_address
;
751 decl_address
.create (10);
752 basic_block entry_bb
= entry
->src
;
753 basic_block exit_bb
= exit
->dest
;
755 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
757 FOR_EACH_VEC_ELT (body
, i
, bb
)
758 if (bb
!= entry_bb
&& bb
!= exit_bb
)
759 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
760 if (is_gimple_debug (gsi_stmt (gsi
)))
762 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
763 has_debug_stmt
= true;
766 eliminate_local_variables_stmt (entry
, &gsi
, decl_address
);
769 FOR_EACH_VEC_ELT (body
, i
, bb
)
770 if (bb
!= entry_bb
&& bb
!= exit_bb
)
771 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
772 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
773 eliminate_local_variables_stmt (entry
, &gsi
, decl_address
);
775 decl_address
.dispose ();
778 /* Returns true if expression EXPR is not defined between ENTRY and
779 EXIT, i.e. if all its operands are defined outside of the region. */
782 expr_invariant_in_region_p (edge entry
, edge exit
, tree expr
)
784 basic_block entry_bb
= entry
->src
;
785 basic_block exit_bb
= exit
->dest
;
788 if (is_gimple_min_invariant (expr
))
791 if (TREE_CODE (expr
) == SSA_NAME
)
793 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
795 && dominated_by_p (CDI_DOMINATORS
, def_bb
, entry_bb
)
796 && !dominated_by_p (CDI_DOMINATORS
, def_bb
, exit_bb
))
805 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
806 The copies are stored to NAME_COPIES, if NAME was already duplicated,
807 its duplicate stored in NAME_COPIES is returned.
809 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
810 duplicated, storing the copies in DECL_COPIES. */
813 separate_decls_in_region_name (tree name
, name_to_copy_table_type name_copies
,
814 int_tree_htab_type decl_copies
, bool copy_name_p
)
816 tree copy
, var
, var_copy
;
817 unsigned idx
, uid
, nuid
;
818 struct int_tree_map ielt
, *nielt
;
819 struct name_to_copy_elt elt
, *nelt
;
820 name_to_copy_elt
**slot
;
821 int_tree_map
**dslot
;
823 if (TREE_CODE (name
) != SSA_NAME
)
826 idx
= SSA_NAME_VERSION (name
);
828 slot
= name_copies
.find_slot_with_hash (&elt
, idx
,
829 copy_name_p
? INSERT
: NO_INSERT
);
831 return (*slot
)->new_name
;
835 copy
= duplicate_ssa_name (name
, NULL
);
836 nelt
= XNEW (struct name_to_copy_elt
);
838 nelt
->new_name
= copy
;
839 nelt
->field
= NULL_TREE
;
848 var
= SSA_NAME_VAR (name
);
852 uid
= DECL_UID (var
);
854 dslot
= decl_copies
.find_slot_with_hash (&ielt
, uid
, INSERT
);
857 var_copy
= create_tmp_var (TREE_TYPE (var
), get_name (var
));
858 DECL_GIMPLE_REG_P (var_copy
) = DECL_GIMPLE_REG_P (var
);
859 nielt
= XNEW (struct int_tree_map
);
861 nielt
->to
= var_copy
;
864 /* Ensure that when we meet this decl next time, we won't duplicate
866 nuid
= DECL_UID (var_copy
);
868 dslot
= decl_copies
.find_slot_with_hash (&ielt
, nuid
, INSERT
);
869 gcc_assert (!*dslot
);
870 nielt
= XNEW (struct int_tree_map
);
872 nielt
->to
= var_copy
;
876 var_copy
= ((struct int_tree_map
*) *dslot
)->to
;
878 replace_ssa_name_symbol (copy
, var_copy
);
882 /* Finds the ssa names used in STMT that are defined outside the
883 region between ENTRY and EXIT and replaces such ssa names with
884 their duplicates. The duplicates are stored to NAME_COPIES. Base
885 decls of all ssa names used in STMT (including those defined in
886 LOOP) are replaced with the new temporary variables; the
887 replacement decls are stored in DECL_COPIES. */
890 separate_decls_in_region_stmt (edge entry
, edge exit
, gimple stmt
,
891 name_to_copy_table_type name_copies
,
892 int_tree_htab_type decl_copies
)
900 FOR_EACH_PHI_OR_STMT_DEF (def
, stmt
, oi
, SSA_OP_DEF
)
902 name
= DEF_FROM_PTR (def
);
903 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
904 copy
= separate_decls_in_region_name (name
, name_copies
, decl_copies
,
906 gcc_assert (copy
== name
);
909 FOR_EACH_PHI_OR_STMT_USE (use
, stmt
, oi
, SSA_OP_USE
)
911 name
= USE_FROM_PTR (use
);
912 if (TREE_CODE (name
) != SSA_NAME
)
915 copy_name_p
= expr_invariant_in_region_p (entry
, exit
, name
);
916 copy
= separate_decls_in_region_name (name
, name_copies
, decl_copies
,
922 /* Finds the ssa names used in STMT that are defined outside the
923 region between ENTRY and EXIT and replaces such ssa names with
924 their duplicates. The duplicates are stored to NAME_COPIES. Base
925 decls of all ssa names used in STMT (including those defined in
926 LOOP) are replaced with the new temporary variables; the
927 replacement decls are stored in DECL_COPIES. */
930 separate_decls_in_region_debug (gimple stmt
,
931 name_to_copy_table_type name_copies
,
932 int_tree_htab_type decl_copies
)
937 struct int_tree_map ielt
;
938 struct name_to_copy_elt elt
;
939 name_to_copy_elt
**slot
;
940 int_tree_map
**dslot
;
942 if (gimple_debug_bind_p (stmt
))
943 var
= gimple_debug_bind_get_var (stmt
);
944 else if (gimple_debug_source_bind_p (stmt
))
945 var
= gimple_debug_source_bind_get_var (stmt
);
948 if (TREE_CODE (var
) == DEBUG_EXPR_DECL
|| TREE_CODE (var
) == LABEL_DECL
)
950 gcc_assert (DECL_P (var
) && SSA_VAR_P (var
));
951 ielt
.uid
= DECL_UID (var
);
952 dslot
= decl_copies
.find_slot_with_hash (&ielt
, ielt
.uid
, NO_INSERT
);
955 if (gimple_debug_bind_p (stmt
))
956 gimple_debug_bind_set_var (stmt
, ((struct int_tree_map
*) *dslot
)->to
);
957 else if (gimple_debug_source_bind_p (stmt
))
958 gimple_debug_source_bind_set_var (stmt
, ((struct int_tree_map
*) *dslot
)->to
);
960 FOR_EACH_PHI_OR_STMT_USE (use
, stmt
, oi
, SSA_OP_USE
)
962 name
= USE_FROM_PTR (use
);
963 if (TREE_CODE (name
) != SSA_NAME
)
966 elt
.version
= SSA_NAME_VERSION (name
);
967 slot
= name_copies
.find_slot_with_hash (&elt
, elt
.version
, NO_INSERT
);
970 gimple_debug_bind_reset_value (stmt
);
975 SET_USE (use
, (*slot
)->new_name
);
981 /* Callback for htab_traverse. Adds a field corresponding to the reduction
982 specified in SLOT. The type is passed in DATA. */
985 add_field_for_reduction (reduction_info
**slot
, tree type
)
988 struct reduction_info
*const red
= *slot
;
989 tree var
= gimple_assign_lhs (red
->reduc_stmt
);
990 tree field
= build_decl (gimple_location (red
->reduc_stmt
), FIELD_DECL
,
991 SSA_NAME_IDENTIFIER (var
), TREE_TYPE (var
));
993 insert_field_into_struct (type
, field
);
1000 /* Callback for htab_traverse. Adds a field corresponding to a ssa name
1001 described in SLOT. The type is passed in DATA. */
1004 add_field_for_name (name_to_copy_elt
**slot
, tree type
)
1006 struct name_to_copy_elt
*const elt
= *slot
;
1007 tree name
= ssa_name (elt
->version
);
1008 tree field
= build_decl (UNKNOWN_LOCATION
,
1009 FIELD_DECL
, SSA_NAME_IDENTIFIER (name
),
1012 insert_field_into_struct (type
, field
);
1018 /* Callback for htab_traverse. A local result is the intermediate result
1019 computed by a single
1020 thread, or the initial value in case no iteration was executed.
1021 This function creates a phi node reflecting these values.
1022 The phi's result will be stored in NEW_PHI field of the
1023 reduction's data structure. */
1026 create_phi_for_local_result (reduction_info
**slot
, struct loop
*loop
)
1028 struct reduction_info
*const reduc
= *slot
;
1031 basic_block store_bb
;
1033 source_location locus
;
1035 /* STORE_BB is the block where the phi
1036 should be stored. It is the destination of the loop exit.
1037 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
1038 store_bb
= FALLTHRU_EDGE (loop
->latch
)->dest
;
1040 /* STORE_BB has two predecessors. One coming from the loop
1041 (the reduction's result is computed at the loop),
1042 and another coming from a block preceding the loop,
1044 are executed (the initial value should be taken). */
1045 if (EDGE_PRED (store_bb
, 0) == FALLTHRU_EDGE (loop
->latch
))
1046 e
= EDGE_PRED (store_bb
, 1);
1048 e
= EDGE_PRED (store_bb
, 0);
1049 local_res
= copy_ssa_name (gimple_assign_lhs (reduc
->reduc_stmt
), NULL
);
1050 locus
= gimple_location (reduc
->reduc_stmt
);
1051 new_phi
= create_phi_node (local_res
, store_bb
);
1052 add_phi_arg (new_phi
, reduc
->init
, e
, locus
);
1053 add_phi_arg (new_phi
, gimple_assign_lhs (reduc
->reduc_stmt
),
1054 FALLTHRU_EDGE (loop
->latch
), locus
);
1055 reduc
->new_phi
= new_phi
;
1065 basic_block store_bb
;
1066 basic_block load_bb
;
1069 /* Callback for htab_traverse. Create an atomic instruction for the
1070 reduction described in SLOT.
1071 DATA annotates the place in memory the atomic operation relates to,
1072 and the basic block it needs to be generated in. */
1075 create_call_for_reduction_1 (reduction_info
**slot
, struct clsn_data
*clsn_data
)
1077 struct reduction_info
*const reduc
= *slot
;
1078 gimple_stmt_iterator gsi
;
1079 tree type
= TREE_TYPE (PHI_RESULT (reduc
->reduc_phi
));
1084 tree t
, addr
, ref
, x
;
1085 tree tmp_load
, name
;
1088 load_struct
= build_simple_mem_ref (clsn_data
->load
);
1089 t
= build3 (COMPONENT_REF
, type
, load_struct
, reduc
->field
, NULL_TREE
);
1091 addr
= build_addr (t
, current_function_decl
);
1093 /* Create phi node. */
1094 bb
= clsn_data
->load_bb
;
1096 e
= split_block (bb
, t
);
1099 tmp_load
= create_tmp_var (TREE_TYPE (TREE_TYPE (addr
)), NULL
);
1100 tmp_load
= make_ssa_name (tmp_load
, NULL
);
1101 load
= gimple_build_omp_atomic_load (tmp_load
, addr
);
1102 SSA_NAME_DEF_STMT (tmp_load
) = load
;
1103 gsi
= gsi_start_bb (new_bb
);
1104 gsi_insert_after (&gsi
, load
, GSI_NEW_STMT
);
1106 e
= split_block (new_bb
, load
);
1108 gsi
= gsi_start_bb (new_bb
);
1110 x
= fold_build2 (reduc
->reduction_code
,
1111 TREE_TYPE (PHI_RESULT (reduc
->new_phi
)), ref
,
1112 PHI_RESULT (reduc
->new_phi
));
1114 name
= force_gimple_operand_gsi (&gsi
, x
, true, NULL_TREE
, true,
1115 GSI_CONTINUE_LINKING
);
1117 gsi_insert_after (&gsi
, gimple_build_omp_atomic_store (name
), GSI_NEW_STMT
);
1121 /* Create the atomic operation at the join point of the threads.
1122 REDUCTION_LIST describes the reductions in the LOOP.
1123 LD_ST_DATA describes the shared data structure where
1124 shared data is stored in and loaded from. */
1126 create_call_for_reduction (struct loop
*loop
,
1127 reduction_info_table_type reduction_list
,
1128 struct clsn_data
*ld_st_data
)
1130 reduction_list
.traverse
<struct loop
*, create_phi_for_local_result
> (loop
);
1131 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
1132 ld_st_data
->load_bb
= FALLTHRU_EDGE (loop
->latch
)->dest
;
1134 .traverse
<struct clsn_data
*, create_call_for_reduction_1
> (ld_st_data
);
1137 /* Callback for htab_traverse. Loads the final reduction value at the
1138 join point of all threads, and inserts it in the right place. */
1141 create_loads_for_reductions (reduction_info
**slot
, struct clsn_data
*clsn_data
)
1143 struct reduction_info
*const red
= *slot
;
1145 gimple_stmt_iterator gsi
;
1146 tree type
= TREE_TYPE (gimple_assign_lhs (red
->reduc_stmt
));
1151 gsi
= gsi_after_labels (clsn_data
->load_bb
);
1152 load_struct
= build_simple_mem_ref (clsn_data
->load
);
1153 load_struct
= build3 (COMPONENT_REF
, type
, load_struct
, red
->field
,
1157 name
= PHI_RESULT (red
->keep_res
);
1158 stmt
= gimple_build_assign (name
, x
);
1160 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1162 for (gsi
= gsi_start_phis (gimple_bb (red
->keep_res
));
1163 !gsi_end_p (gsi
); gsi_next (&gsi
))
1164 if (gsi_stmt (gsi
) == red
->keep_res
)
1166 remove_phi_node (&gsi
, false);
1172 /* Load the reduction result that was stored in LD_ST_DATA.
1173 REDUCTION_LIST describes the list of reductions that the
1174 loads should be generated for. */
1176 create_final_loads_for_reduction (reduction_info_table_type reduction_list
,
1177 struct clsn_data
*ld_st_data
)
1179 gimple_stmt_iterator gsi
;
1183 gsi
= gsi_after_labels (ld_st_data
->load_bb
);
1184 t
= build_fold_addr_expr (ld_st_data
->store
);
1185 stmt
= gimple_build_assign (ld_st_data
->load
, t
);
1187 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1190 .traverse
<struct clsn_data
*, create_loads_for_reductions
> (ld_st_data
);
1194 /* Callback for htab_traverse. Store the neutral value for the
1195 particular reduction's operation, e.g. 0 for PLUS_EXPR,
1196 1 for MULT_EXPR, etc. into the reduction field.
1197 The reduction is specified in SLOT. The store information is
1201 create_stores_for_reduction (reduction_info
**slot
, struct clsn_data
*clsn_data
)
1203 struct reduction_info
*const red
= *slot
;
1206 gimple_stmt_iterator gsi
;
1207 tree type
= TREE_TYPE (gimple_assign_lhs (red
->reduc_stmt
));
1209 gsi
= gsi_last_bb (clsn_data
->store_bb
);
1210 t
= build3 (COMPONENT_REF
, type
, clsn_data
->store
, red
->field
, NULL_TREE
);
1211 stmt
= gimple_build_assign (t
, red
->initial_value
);
1212 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1217 /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
1218 store to a field of STORE in STORE_BB for the ssa name and its duplicate
1219 specified in SLOT. */
1222 create_loads_and_stores_for_name (name_to_copy_elt
**slot
,
1223 struct clsn_data
*clsn_data
)
1225 struct name_to_copy_elt
*const elt
= *slot
;
1228 gimple_stmt_iterator gsi
;
1229 tree type
= TREE_TYPE (elt
->new_name
);
1232 gsi
= gsi_last_bb (clsn_data
->store_bb
);
1233 t
= build3 (COMPONENT_REF
, type
, clsn_data
->store
, elt
->field
, NULL_TREE
);
1234 stmt
= gimple_build_assign (t
, ssa_name (elt
->version
));
1235 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1237 gsi
= gsi_last_bb (clsn_data
->load_bb
);
1238 load_struct
= build_simple_mem_ref (clsn_data
->load
);
1239 t
= build3 (COMPONENT_REF
, type
, load_struct
, elt
->field
, NULL_TREE
);
1240 stmt
= gimple_build_assign (elt
->new_name
, t
);
1241 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1246 /* Moves all the variables used in LOOP and defined outside of it (including
1247 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1248 name) to a structure created for this purpose. The code
1256 is transformed this way:
1271 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1272 pointer `new' is intentionally not initialized (the loop will be split to a
1273 separate function later, and `new' will be initialized from its arguments).
1274 LD_ST_DATA holds information about the shared data structure used to pass
1275 information among the threads. It is initialized here, and
1276 gen_parallel_loop will pass it to create_call_for_reduction that
1277 needs this information. REDUCTION_LIST describes the reductions
1281 separate_decls_in_region (edge entry
, edge exit
,
1282 reduction_info_table_type reduction_list
,
1283 tree
*arg_struct
, tree
*new_arg_struct
,
1284 struct clsn_data
*ld_st_data
)
1287 basic_block bb1
= split_edge (entry
);
1288 basic_block bb0
= single_pred (bb1
);
1289 name_to_copy_table_type name_copies
;
1290 name_copies
.create (10);
1291 int_tree_htab_type decl_copies
;
1292 decl_copies
.create (10);
1294 tree type
, type_name
, nvar
;
1295 gimple_stmt_iterator gsi
;
1296 struct clsn_data clsn_data
;
1297 stack_vec
<basic_block
, 3> body
;
1299 basic_block entry_bb
= bb1
;
1300 basic_block exit_bb
= exit
->dest
;
1301 bool has_debug_stmt
= false;
1303 entry
= single_succ_edge (entry_bb
);
1304 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
1306 FOR_EACH_VEC_ELT (body
, i
, bb
)
1308 if (bb
!= entry_bb
&& bb
!= exit_bb
)
1310 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1311 separate_decls_in_region_stmt (entry
, exit
, gsi_stmt (gsi
),
1312 name_copies
, decl_copies
);
1314 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1316 gimple stmt
= gsi_stmt (gsi
);
1318 if (is_gimple_debug (stmt
))
1319 has_debug_stmt
= true;
1321 separate_decls_in_region_stmt (entry
, exit
, stmt
,
1322 name_copies
, decl_copies
);
1327 /* Now process debug bind stmts. We must not create decls while
1328 processing debug stmts, so we defer their processing so as to
1329 make sure we will have debug info for as many variables as
1330 possible (all of those that were dealt with in the loop above),
1331 and discard those for which we know there's nothing we can
1334 FOR_EACH_VEC_ELT (body
, i
, bb
)
1335 if (bb
!= entry_bb
&& bb
!= exit_bb
)
1337 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
1339 gimple stmt
= gsi_stmt (gsi
);
1341 if (is_gimple_debug (stmt
))
1343 if (separate_decls_in_region_debug (stmt
, name_copies
,
1346 gsi_remove (&gsi
, true);
1355 if (name_copies
.elements () == 0 && reduction_list
.elements () == 0)
1357 /* It may happen that there is nothing to copy (if there are only
1358 loop carried and external variables in the loop). */
1360 *new_arg_struct
= NULL
;
1364 /* Create the type for the structure to store the ssa names to. */
1365 type
= lang_hooks
.types
.make_type (RECORD_TYPE
);
1366 type_name
= build_decl (UNKNOWN_LOCATION
,
1367 TYPE_DECL
, create_tmp_var_name (".paral_data"),
1369 TYPE_NAME (type
) = type_name
;
1371 name_copies
.traverse
<tree
, add_field_for_name
> (type
);
1372 if (reduction_list
.is_created () && reduction_list
.elements () > 0)
1374 /* Create the fields for reductions. */
1375 reduction_list
.traverse
<tree
, add_field_for_reduction
> (type
);
1379 /* Create the loads and stores. */
1380 *arg_struct
= create_tmp_var (type
, ".paral_data_store");
1381 nvar
= create_tmp_var (build_pointer_type (type
), ".paral_data_load");
1382 *new_arg_struct
= make_ssa_name (nvar
, NULL
);
1384 ld_st_data
->store
= *arg_struct
;
1385 ld_st_data
->load
= *new_arg_struct
;
1386 ld_st_data
->store_bb
= bb0
;
1387 ld_st_data
->load_bb
= bb1
;
1390 .traverse
<struct clsn_data
*, create_loads_and_stores_for_name
>
1393 /* Load the calculation from memory (after the join of the threads). */
1395 if (reduction_list
.is_created () && reduction_list
.elements () > 0)
1398 .traverse
<struct clsn_data
*, create_stores_for_reduction
>
1400 clsn_data
.load
= make_ssa_name (nvar
, NULL
);
1401 clsn_data
.load_bb
= exit
->dest
;
1402 clsn_data
.store
= ld_st_data
->store
;
1403 create_final_loads_for_reduction (reduction_list
, &clsn_data
);
1407 decl_copies
.dispose ();
1408 name_copies
.dispose ();
1411 /* Bitmap containing uids of functions created by parallelization. We cannot
1412 allocate it from the default obstack, as it must live across compilation
1413 of several functions; we make it gc allocated instead. */
1415 static GTY(()) bitmap parallelized_functions
;
1417 /* Returns true if FN was created by create_loop_fn. */
1420 parallelized_function_p (tree fn
)
1422 if (!parallelized_functions
|| !DECL_ARTIFICIAL (fn
))
1425 return bitmap_bit_p (parallelized_functions
, DECL_UID (fn
));
1428 /* Creates and returns an empty function that will receive the body of
1429 a parallelized loop. */
1432 create_loop_fn (location_t loc
)
1436 tree decl
, type
, name
, t
;
1437 struct function
*act_cfun
= cfun
;
1438 static unsigned loopfn_num
;
1440 loc
= LOCATION_LOCUS (loc
);
1441 snprintf (buf
, 100, "%s.$loopfn", current_function_name ());
1442 ASM_FORMAT_PRIVATE_NAME (tname
, buf
, loopfn_num
++);
1443 clean_symbol_name (tname
);
1444 name
= get_identifier (tname
);
1445 type
= build_function_type_list (void_type_node
, ptr_type_node
, NULL_TREE
);
1447 decl
= build_decl (loc
, FUNCTION_DECL
, name
, type
);
1448 if (!parallelized_functions
)
1449 parallelized_functions
= BITMAP_GGC_ALLOC ();
1450 bitmap_set_bit (parallelized_functions
, DECL_UID (decl
));
1452 TREE_STATIC (decl
) = 1;
1453 TREE_USED (decl
) = 1;
1454 DECL_ARTIFICIAL (decl
) = 1;
1455 DECL_IGNORED_P (decl
) = 0;
1456 TREE_PUBLIC (decl
) = 0;
1457 DECL_UNINLINABLE (decl
) = 1;
1458 DECL_EXTERNAL (decl
) = 0;
1459 DECL_CONTEXT (decl
) = NULL_TREE
;
1460 DECL_INITIAL (decl
) = make_node (BLOCK
);
1462 t
= build_decl (loc
, RESULT_DECL
, NULL_TREE
, void_type_node
);
1463 DECL_ARTIFICIAL (t
) = 1;
1464 DECL_IGNORED_P (t
) = 1;
1465 DECL_RESULT (decl
) = t
;
1467 t
= build_decl (loc
, PARM_DECL
, get_identifier (".paral_data_param"),
1469 DECL_ARTIFICIAL (t
) = 1;
1470 DECL_ARG_TYPE (t
) = ptr_type_node
;
1471 DECL_CONTEXT (t
) = decl
;
1473 DECL_ARGUMENTS (decl
) = t
;
1475 allocate_struct_function (decl
, false);
1477 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1479 set_cfun (act_cfun
);
1484 /* Moves the exit condition of LOOP to the beginning of its header, and
1485 duplicates the part of the last iteration that gets disabled to the
1486 exit of the loop. NIT is the number of iterations of the loop
1487 (used to initialize the variables in the duplicated part).
1489 TODO: the common case is that latch of the loop is empty and immediately
1490 follows the loop exit. In this case, it would be better not to copy the
1491 body of the loop, but only move the entry of the loop directly before the
1492 exit check and increase the number of iterations of the loop by one.
1493 This may need some additional preconditioning in case NIT = ~0.
1494 REDUCTION_LIST describes the reductions in LOOP. */
1497 transform_to_exit_first_loop (struct loop
*loop
,
1498 reduction_info_table_type reduction_list
,
1501 basic_block
*bbs
, *nbbs
, ex_bb
, orig_header
;
1504 edge exit
= single_dom_exit (loop
), hpred
;
1505 tree control
, control_name
, res
, t
;
1506 gimple phi
, nphi
, cond_stmt
, stmt
, cond_nit
;
1507 gimple_stmt_iterator gsi
;
1510 split_block_after_labels (loop
->header
);
1511 orig_header
= single_succ (loop
->header
);
1512 hpred
= single_succ_edge (loop
->header
);
1514 cond_stmt
= last_stmt (exit
->src
);
1515 control
= gimple_cond_lhs (cond_stmt
);
1516 gcc_assert (gimple_cond_rhs (cond_stmt
) == nit
);
1518 /* Make sure that we have phi nodes on exit for all loop header phis
1519 (create_parallel_loop requires that). */
1520 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1522 phi
= gsi_stmt (gsi
);
1523 res
= PHI_RESULT (phi
);
1524 t
= copy_ssa_name (res
, phi
);
1525 SET_PHI_RESULT (phi
, t
);
1526 nphi
= create_phi_node (res
, orig_header
);
1527 add_phi_arg (nphi
, t
, hpred
, UNKNOWN_LOCATION
);
1531 gimple_cond_set_lhs (cond_stmt
, t
);
1532 update_stmt (cond_stmt
);
1537 bbs
= get_loop_body_in_dom_order (loop
);
1539 for (n
= 0; bbs
[n
] != exit
->src
; n
++)
1541 nbbs
= XNEWVEC (basic_block
, n
);
1542 ok
= gimple_duplicate_sese_tail (single_succ_edge (loop
->header
), exit
,
1549 /* Other than reductions, the only gimple reg that should be copied
1550 out of the loop is the control variable. */
1551 exit
= single_dom_exit (loop
);
1552 control_name
= NULL_TREE
;
1553 for (gsi
= gsi_start_phis (ex_bb
); !gsi_end_p (gsi
); )
1555 phi
= gsi_stmt (gsi
);
1556 res
= PHI_RESULT (phi
);
1557 if (virtual_operand_p (res
))
1563 /* Check if it is a part of reduction. If it is,
1564 keep the phi at the reduction's keep_res field. The
1565 PHI_RESULT of this phi is the resulting value of the reduction
1566 variable when exiting the loop. */
1568 if (reduction_list
.elements () > 0)
1570 struct reduction_info
*red
;
1572 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1573 red
= reduction_phi (reduction_list
, SSA_NAME_DEF_STMT (val
));
1576 red
->keep_res
= phi
;
1581 gcc_assert (control_name
== NULL_TREE
1582 && SSA_NAME_VAR (res
) == SSA_NAME_VAR (control
));
1584 remove_phi_node (&gsi
, false);
1586 gcc_assert (control_name
!= NULL_TREE
);
1588 /* Initialize the control variable to number of iterations
1589 according to the rhs of the exit condition. */
1590 gsi
= gsi_after_labels (ex_bb
);
1591 cond_nit
= last_stmt (exit
->src
);
1592 nit_1
= gimple_cond_rhs (cond_nit
);
1593 nit_1
= force_gimple_operand_gsi (&gsi
,
1594 fold_convert (TREE_TYPE (control_name
), nit_1
),
1595 false, NULL_TREE
, false, GSI_SAME_STMT
);
1596 stmt
= gimple_build_assign (control_name
, nit_1
);
1597 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1600 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
1601 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
1602 NEW_DATA is the variable that should be initialized from the argument
1603 of LOOP_FN. N_THREADS is the requested number of threads. Returns the
1604 basic block containing GIMPLE_OMP_PARALLEL tree. */
1607 create_parallel_loop (struct loop
*loop
, tree loop_fn
, tree data
,
1608 tree new_data
, unsigned n_threads
, location_t loc
)
1610 gimple_stmt_iterator gsi
;
1611 basic_block bb
, paral_bb
, for_bb
, ex_bb
;
1613 gimple stmt
, for_stmt
, phi
, cond_stmt
;
1614 tree cvar
, cvar_init
, initvar
, cvar_next
, cvar_base
, type
;
1615 edge exit
, nexit
, guard
, end
, e
;
1617 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
1618 bb
= loop_preheader_edge (loop
)->src
;
1619 paral_bb
= single_pred (bb
);
1620 gsi
= gsi_last_bb (paral_bb
);
1622 t
= build_omp_clause (loc
, OMP_CLAUSE_NUM_THREADS
);
1623 OMP_CLAUSE_NUM_THREADS_EXPR (t
)
1624 = build_int_cst (integer_type_node
, n_threads
);
1625 stmt
= gimple_build_omp_parallel (NULL
, t
, loop_fn
, data
);
1626 gimple_set_location (stmt
, loc
);
1628 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1630 /* Initialize NEW_DATA. */
1633 gsi
= gsi_after_labels (bb
);
1635 param
= make_ssa_name (DECL_ARGUMENTS (loop_fn
), NULL
);
1636 stmt
= gimple_build_assign (param
, build_fold_addr_expr (data
));
1637 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1639 stmt
= gimple_build_assign (new_data
,
1640 fold_convert (TREE_TYPE (new_data
), param
));
1641 gsi_insert_before (&gsi
, stmt
, GSI_SAME_STMT
);
1644 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
1645 bb
= split_loop_exit_edge (single_dom_exit (loop
));
1646 gsi
= gsi_last_bb (bb
);
1647 stmt
= gimple_build_omp_return (false);
1648 gimple_set_location (stmt
, loc
);
1649 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1651 /* Extract data for GIMPLE_OMP_FOR. */
1652 gcc_assert (loop
->header
== single_dom_exit (loop
)->src
);
1653 cond_stmt
= last_stmt (loop
->header
);
1655 cvar
= gimple_cond_lhs (cond_stmt
);
1656 cvar_base
= SSA_NAME_VAR (cvar
);
1657 phi
= SSA_NAME_DEF_STMT (cvar
);
1658 cvar_init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1659 initvar
= copy_ssa_name (cvar
, NULL
);
1660 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, loop_preheader_edge (loop
)),
1662 cvar_next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
1664 gsi
= gsi_last_nondebug_bb (loop
->latch
);
1665 gcc_assert (gsi_stmt (gsi
) == SSA_NAME_DEF_STMT (cvar_next
));
1666 gsi_remove (&gsi
, true);
1669 for_bb
= split_edge (loop_preheader_edge (loop
));
1670 ex_bb
= split_loop_exit_edge (single_dom_exit (loop
));
1671 extract_true_false_edges_from_block (loop
->header
, &nexit
, &exit
);
1672 gcc_assert (exit
== single_dom_exit (loop
));
1674 guard
= make_edge (for_bb
, ex_bb
, 0);
1675 single_succ_edge (loop
->latch
)->flags
= 0;
1676 end
= make_edge (loop
->latch
, ex_bb
, EDGE_FALLTHRU
);
1677 for (gsi
= gsi_start_phis (ex_bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1679 source_location locus
;
1681 phi
= gsi_stmt (gsi
);
1682 stmt
= SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi
, exit
));
1684 def
= PHI_ARG_DEF_FROM_EDGE (stmt
, loop_preheader_edge (loop
));
1685 locus
= gimple_phi_arg_location_from_edge (stmt
,
1686 loop_preheader_edge (loop
));
1687 add_phi_arg (phi
, def
, guard
, locus
);
1689 def
= PHI_ARG_DEF_FROM_EDGE (stmt
, loop_latch_edge (loop
));
1690 locus
= gimple_phi_arg_location_from_edge (stmt
, loop_latch_edge (loop
));
1691 add_phi_arg (phi
, def
, end
, locus
);
1693 e
= redirect_edge_and_branch (exit
, nexit
->dest
);
1694 PENDING_STMT (e
) = NULL
;
1696 /* Emit GIMPLE_OMP_FOR. */
1697 gimple_cond_set_lhs (cond_stmt
, cvar_base
);
1698 type
= TREE_TYPE (cvar
);
1699 t
= build_omp_clause (loc
, OMP_CLAUSE_SCHEDULE
);
1700 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_STATIC
;
1702 for_stmt
= gimple_build_omp_for (NULL
, GF_OMP_FOR_KIND_FOR
, t
, 1, NULL
);
1703 gimple_set_location (for_stmt
, loc
);
1704 gimple_omp_for_set_index (for_stmt
, 0, initvar
);
1705 gimple_omp_for_set_initial (for_stmt
, 0, cvar_init
);
1706 gimple_omp_for_set_final (for_stmt
, 0, gimple_cond_rhs (cond_stmt
));
1707 gimple_omp_for_set_cond (for_stmt
, 0, gimple_cond_code (cond_stmt
));
1708 gimple_omp_for_set_incr (for_stmt
, 0, build2 (PLUS_EXPR
, type
,
1710 build_int_cst (type
, 1)));
1712 gsi
= gsi_last_bb (for_bb
);
1713 gsi_insert_after (&gsi
, for_stmt
, GSI_NEW_STMT
);
1714 SSA_NAME_DEF_STMT (initvar
) = for_stmt
;
1716 /* Emit GIMPLE_OMP_CONTINUE. */
1717 gsi
= gsi_last_bb (loop
->latch
);
1718 stmt
= gimple_build_omp_continue (cvar_next
, cvar
);
1719 gimple_set_location (stmt
, loc
);
1720 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1721 SSA_NAME_DEF_STMT (cvar_next
) = stmt
;
1723 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
1724 gsi
= gsi_last_bb (ex_bb
);
1725 stmt
= gimple_build_omp_return (true);
1726 gimple_set_location (stmt
, loc
);
1727 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1729 /* After the above dom info is hosed. Re-compute it. */
1730 free_dominance_info (CDI_DOMINATORS
);
1731 calculate_dominance_info (CDI_DOMINATORS
);
1736 /* Generates code to execute the iterations of LOOP in N_THREADS
1737 threads in parallel.
1739 NITER describes number of iterations of LOOP.
1740 REDUCTION_LIST describes the reductions existent in the LOOP. */
1743 gen_parallel_loop (struct loop
*loop
, reduction_info_table_type reduction_list
,
1744 unsigned n_threads
, struct tree_niter_desc
*niter
)
1747 tree many_iterations_cond
, type
, nit
;
1748 tree arg_struct
, new_arg_struct
;
1750 basic_block parallel_head
;
1752 struct clsn_data clsn_data
;
1756 unsigned int m_p_thread
=2;
1760 ---------------------------------------------------------------------
1763 IV = phi (INIT, IV + STEP)
1769 ---------------------------------------------------------------------
1771 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
1772 we generate the following code:
1774 ---------------------------------------------------------------------
1777 || NITER < MIN_PER_THREAD * N_THREADS)
1781 store all local loop-invariant variables used in body of the loop to DATA.
1782 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
1783 load the variables from DATA.
1784 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
1787 GIMPLE_OMP_CONTINUE;
1788 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
1789 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
1795 IV = phi (INIT, IV + STEP)
1806 /* Create two versions of the loop -- in the old one, we know that the
1807 number of iterations is large enough, and we will transform it into the
1808 loop that will be split to loop_fn, the new one will be used for the
1809 remaining iterations. */
1811 /* We should compute a better number-of-iterations value for outer loops.
1814 for (i = 0; i < n; ++i)
1815 for (j = 0; j < m; ++j)
1818 we should compute nit = n * m, not nit = n.
1819 Also may_be_zero handling would need to be adjusted. */
1821 type
= TREE_TYPE (niter
->niter
);
1822 nit
= force_gimple_operand (unshare_expr (niter
->niter
), &stmts
, true,
1825 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1830 m_p_thread
=MIN_PER_THREAD
;
1832 many_iterations_cond
=
1833 fold_build2 (GE_EXPR
, boolean_type_node
,
1834 nit
, build_int_cst (type
, m_p_thread
* n_threads
));
1836 many_iterations_cond
1837 = fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1838 invert_truthvalue (unshare_expr (niter
->may_be_zero
)),
1839 many_iterations_cond
);
1840 many_iterations_cond
1841 = force_gimple_operand (many_iterations_cond
, &stmts
, false, NULL_TREE
);
1843 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1844 if (!is_gimple_condexpr (many_iterations_cond
))
1846 many_iterations_cond
1847 = force_gimple_operand (many_iterations_cond
, &stmts
,
1850 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1853 initialize_original_copy_tables ();
1855 /* We assume that the loop usually iterates a lot. */
1856 prob
= 4 * REG_BR_PROB_BASE
/ 5;
1857 loop_version (loop
, many_iterations_cond
, NULL
,
1858 prob
, prob
, REG_BR_PROB_BASE
- prob
, true);
1859 update_ssa (TODO_update_ssa
);
1860 free_original_copy_tables ();
1862 /* Base all the induction variables in LOOP on a single control one. */
1863 canonicalize_loop_ivs (loop
, &nit
, true);
1865 /* Ensure that the exit condition is the first statement in the loop. */
1866 transform_to_exit_first_loop (loop
, reduction_list
, nit
);
1868 /* Generate initializations for reductions. */
1869 if (reduction_list
.elements () > 0)
1870 reduction_list
.traverse
<struct loop
*, initialize_reductions
> (loop
);
1872 /* Eliminate the references to local variables from the loop. */
1873 gcc_assert (single_exit (loop
));
1874 entry
= loop_preheader_edge (loop
);
1875 exit
= single_dom_exit (loop
);
1877 eliminate_local_variables (entry
, exit
);
1878 /* In the old loop, move all variables non-local to the loop to a structure
1879 and back, and create separate decls for the variables used in loop. */
1880 separate_decls_in_region (entry
, exit
, reduction_list
, &arg_struct
,
1881 &new_arg_struct
, &clsn_data
);
1883 /* Create the parallel constructs. */
1884 loc
= UNKNOWN_LOCATION
;
1885 cond_stmt
= last_stmt (loop
->header
);
1887 loc
= gimple_location (cond_stmt
);
1888 parallel_head
= create_parallel_loop (loop
, create_loop_fn (loc
), arg_struct
,
1889 new_arg_struct
, n_threads
, loc
);
1890 if (reduction_list
.elements () > 0)
1891 create_call_for_reduction (loop
, reduction_list
, &clsn_data
);
1895 /* Cancel the loop (it is simpler to do it here rather than to teach the
1896 expander to do it). */
1897 cancel_loop_tree (loop
);
1899 /* Free loop bound estimations that could contain references to
1900 removed statements. */
1901 FOR_EACH_LOOP (li
, loop
, 0)
1902 free_numbers_of_iterations_estimates_loop (loop
);
1904 /* Expand the parallel constructs. We do it directly here instead of running
1905 a separate expand_omp pass, since it is more efficient, and less likely to
1906 cause troubles with further analyses not being able to deal with the
1909 omp_expand_local (parallel_head
);
1912 /* Returns true when LOOP contains vector phi nodes. */
1915 loop_has_vector_phi_nodes (struct loop
*loop ATTRIBUTE_UNUSED
)
1918 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
1919 gimple_stmt_iterator gsi
;
1922 for (i
= 0; i
< loop
->num_nodes
; i
++)
1923 for (gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
1924 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi_stmt (gsi
)))) == VECTOR_TYPE
)
1933 /* Create a reduction_info struct, initialize it with REDUC_STMT
1934 and PHI, insert it to the REDUCTION_LIST. */
1937 build_new_reduction (reduction_info_table_type reduction_list
,
1938 gimple reduc_stmt
, gimple phi
)
1940 reduction_info
**slot
;
1941 struct reduction_info
*new_reduction
;
1943 gcc_assert (reduc_stmt
);
1945 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1948 "Detected reduction. reduction stmt is: \n");
1949 print_gimple_stmt (dump_file
, reduc_stmt
, 0, 0);
1950 fprintf (dump_file
, "\n");
1953 new_reduction
= XCNEW (struct reduction_info
);
1955 new_reduction
->reduc_stmt
= reduc_stmt
;
1956 new_reduction
->reduc_phi
= phi
;
1957 new_reduction
->reduc_version
= SSA_NAME_VERSION (gimple_phi_result (phi
));
1958 new_reduction
->reduction_code
= gimple_assign_rhs_code (reduc_stmt
);
1959 slot
= reduction_list
.find_slot (new_reduction
, INSERT
);
1960 *slot
= new_reduction
;
1963 /* Callback for htab_traverse. Sets gimple_uid of reduc_phi stmts. */
1966 set_reduc_phi_uids (reduction_info
**slot
, void *data ATTRIBUTE_UNUSED
)
1968 struct reduction_info
*const red
= *slot
;
1969 gimple_set_uid (red
->reduc_phi
, red
->reduc_version
);
1973 /* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
1976 gather_scalar_reductions (loop_p loop
, reduction_info_table_type reduction_list
)
1978 gimple_stmt_iterator gsi
;
1979 loop_vec_info simple_loop_info
;
1981 simple_loop_info
= vect_analyze_loop_form (loop
);
1983 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1985 gimple phi
= gsi_stmt (gsi
);
1987 tree res
= PHI_RESULT (phi
);
1990 if (virtual_operand_p (res
))
1993 if (!simple_iv (loop
, loop
, res
, &iv
, true)
1994 && simple_loop_info
)
1996 gimple reduc_stmt
= vect_force_simple_reduction (simple_loop_info
,
1999 if (reduc_stmt
&& !double_reduc
)
2000 build_new_reduction (reduction_list
, reduc_stmt
, phi
);
2003 destroy_loop_vec_info (simple_loop_info
, true);
2005 /* As gimple_uid is used by the vectorizer in between vect_analyze_loop_form
2006 and destroy_loop_vec_info, we can set gimple_uid of reduc_phi stmts
2008 reduction_list
.traverse
<void *, set_reduc_phi_uids
> (NULL
);
2011 /* Try to initialize NITER for code generation part. */
2014 try_get_loop_niter (loop_p loop
, struct tree_niter_desc
*niter
)
2016 edge exit
= single_dom_exit (loop
);
2020 /* We need to know # of iterations, and there should be no uses of values
2021 defined inside loop outside of it, unless the values are invariants of
2023 if (!number_of_iterations_exit (loop
, exit
, niter
, false))
2025 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2026 fprintf (dump_file
, " FAILED: number of iterations not known\n");
2033 /* Try to initialize REDUCTION_LIST for code generation part.
2034 REDUCTION_LIST describes the reductions. */
2037 try_create_reduction_list (loop_p loop
,
2038 reduction_info_table_type reduction_list
)
2040 edge exit
= single_dom_exit (loop
);
2041 gimple_stmt_iterator gsi
;
2045 gather_scalar_reductions (loop
, reduction_list
);
2048 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2050 gimple phi
= gsi_stmt (gsi
);
2051 struct reduction_info
*red
;
2052 imm_use_iterator imm_iter
;
2053 use_operand_p use_p
;
2055 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2057 if (!virtual_operand_p (val
))
2059 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2061 fprintf (dump_file
, "phi is ");
2062 print_gimple_stmt (dump_file
, phi
, 0, 0);
2063 fprintf (dump_file
, "arg of phi to exit: value ");
2064 print_generic_expr (dump_file
, val
, 0);
2065 fprintf (dump_file
, " used outside loop\n");
2067 " checking if it a part of reduction pattern: \n");
2069 if (reduction_list
.elements () == 0)
2071 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2073 " FAILED: it is not a part of reduction.\n");
2077 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, val
)
2079 if (!gimple_debug_bind_p (USE_STMT (use_p
))
2080 && flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
2082 reduc_phi
= USE_STMT (use_p
);
2086 red
= reduction_phi (reduction_list
, reduc_phi
);
2089 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2091 " FAILED: it is not a part of reduction.\n");
2094 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2096 fprintf (dump_file
, "reduction phi is ");
2097 print_gimple_stmt (dump_file
, red
->reduc_phi
, 0, 0);
2098 fprintf (dump_file
, "reduction stmt is ");
2099 print_gimple_stmt (dump_file
, red
->reduc_stmt
, 0, 0);
2104 /* The iterations of the loop may communicate only through bivs whose
2105 iteration space can be distributed efficiently. */
2106 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2108 gimple phi
= gsi_stmt (gsi
);
2109 tree def
= PHI_RESULT (phi
);
2112 if (!virtual_operand_p (def
) && !simple_iv (loop
, loop
, def
, &iv
, true))
2114 struct reduction_info
*red
;
2116 red
= reduction_phi (reduction_list
, phi
);
2119 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2121 " FAILED: scalar dependency between iterations\n");
2131 /* Detect parallel loops and generate parallel code using libgomp
2132 primitives. Returns true if some loop was parallelized, false
2136 parallelize_loops (void)
2138 unsigned n_threads
= flag_tree_parallelize_loops
;
2139 bool changed
= false;
2141 struct tree_niter_desc niter_desc
;
2143 reduction_info_table_type reduction_list
;
2144 struct obstack parloop_obstack
;
2145 HOST_WIDE_INT estimated
;
2148 /* Do not parallelize loops in the functions created by parallelization. */
2149 if (parallelized_function_p (cfun
->decl
))
2151 if (cfun
->has_nonlocal_label
)
2154 gcc_obstack_init (&parloop_obstack
);
2155 reduction_list
.create (10);
2156 init_stmt_vec_info_vec ();
2158 FOR_EACH_LOOP (li
, loop
, 0)
2160 reduction_list
.empty ();
2161 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2163 fprintf (dump_file
, "Trying loop %d as candidate\n",loop
->num
);
2165 fprintf (dump_file
, "loop %d is not innermost\n",loop
->num
);
2167 fprintf (dump_file
, "loop %d is innermost\n",loop
->num
);
2170 /* If we use autopar in graphite pass, we use its marked dependency
2171 checking results. */
2172 if (flag_loop_parallelize_all
&& !loop
->can_be_parallel
)
2174 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2175 fprintf (dump_file
, "loop is not parallel according to graphite\n");
2179 if (!single_dom_exit (loop
))
2182 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2183 fprintf (dump_file
, "loop is !single_dom_exit\n");
2188 if (/* And of course, the loop must be parallelizable. */
2189 !can_duplicate_loop_p (loop
)
2190 || loop_has_blocks_with_irreducible_flag (loop
)
2191 || (loop_preheader_edge (loop
)->src
->flags
& BB_IRREDUCIBLE_LOOP
)
2192 /* FIXME: the check for vector phi nodes could be removed. */
2193 || loop_has_vector_phi_nodes (loop
))
2196 estimated
= estimated_stmt_executions_int (loop
);
2197 if (estimated
== -1)
2198 estimated
= max_stmt_executions_int (loop
);
2199 /* FIXME: Bypass this check as graphite doesn't update the
2200 count and frequency correctly now. */
2201 if (!flag_loop_parallelize_all
2202 && ((estimated
!= -1
2203 && estimated
<= (HOST_WIDE_INT
) n_threads
* MIN_PER_THREAD
)
2204 /* Do not bother with loops in cold areas. */
2205 || optimize_loop_nest_for_size_p (loop
)))
2208 if (!try_get_loop_niter (loop
, &niter_desc
))
2211 if (!try_create_reduction_list (loop
, reduction_list
))
2214 if (!flag_loop_parallelize_all
2215 && !loop_parallel_p (loop
, &parloop_obstack
))
2219 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2222 fprintf (dump_file
, "parallelizing outer loop %d\n",loop
->header
->index
);
2224 fprintf (dump_file
, "parallelizing inner loop %d\n",loop
->header
->index
);
2225 loop_loc
= find_loop_location (loop
);
2226 if (loop_loc
!= UNKNOWN_LOC
)
2227 fprintf (dump_file
, "\nloop at %s:%d: ",
2228 LOC_FILE (loop_loc
), LOC_LINE (loop_loc
));
2230 gen_parallel_loop (loop
, reduction_list
,
2231 n_threads
, &niter_desc
);
2234 free_stmt_vec_info_vec ();
2235 reduction_list
.dispose ();
2236 obstack_free (&parloop_obstack
, NULL
);
2238 /* Parallelization will cause new function calls to be inserted through
2239 which local variables will escape. Reset the points-to solution
2242 pt_solution_reset (&cfun
->gimple_df
->escaped
);
2247 /* Parallelization. */
2250 gate_tree_parallelize_loops (void)
2252 return flag_tree_parallelize_loops
> 1;
2256 tree_parallelize_loops (void)
2258 if (number_of_loops (cfun
) <= 1)
2261 if (parallelize_loops ())
2262 return TODO_cleanup_cfg
| TODO_rebuild_alias
;
2268 const pass_data pass_data_parallelize_loops
=
2270 GIMPLE_PASS
, /* type */
2271 "parloops", /* name */
2272 OPTGROUP_LOOP
, /* optinfo_flags */
2273 true, /* has_gate */
2274 true, /* has_execute */
2275 TV_TREE_PARALLELIZE_LOOPS
, /* tv_id */
2276 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2277 0, /* properties_provided */
2278 0, /* properties_destroyed */
2279 0, /* todo_flags_start */
2280 TODO_verify_flow
, /* todo_flags_finish */
2283 class pass_parallelize_loops
: public gimple_opt_pass
2286 pass_parallelize_loops (gcc::context
*ctxt
)
2287 : gimple_opt_pass (pass_data_parallelize_loops
, ctxt
)
2290 /* opt_pass methods: */
2291 bool gate () { return gate_tree_parallelize_loops (); }
2292 unsigned int execute () { return tree_parallelize_loops (); }
2294 }; // class pass_parallelize_loops
2299 make_pass_parallelize_loops (gcc::context
*ctxt
)
2301 return new pass_parallelize_loops (ctxt
);
2305 #include "gt-tree-parloops.h"