1 /* Loop autoparallelization.
2 Copyright (C) 2006-2014 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"
26 #include "basic-block.h"
27 #include "tree-ssa-alias.h"
28 #include "internal-fn.h"
29 #include "gimple-expr.h"
33 #include "gimple-iterator.h"
34 #include "gimplify-me.h"
35 #include "gimple-walk.h"
36 #include "stor-layout.h"
37 #include "tree-nested.h"
38 #include "gimple-ssa.h"
40 #include "tree-phinodes.h"
41 #include "ssa-iterators.h"
42 #include "stringpool.h"
43 #include "tree-ssanames.h"
44 #include "tree-ssa-loop-ivopts.h"
45 #include "tree-ssa-loop-manip.h"
46 #include "tree-ssa-loop-niter.h"
47 #include "tree-ssa-loop.h"
48 #include "tree-into-ssa.h"
50 #include "tree-data-ref.h"
51 #include "tree-scalar-evolution.h"
52 #include "gimple-pretty-print.h"
53 #include "tree-pass.h"
54 #include "langhooks.h"
55 #include "tree-vectorizer.h"
56 #include "tree-hasher.h"
57 #include "tree-parloops.h"
59 #include "tree-nested.h"
61 /* This pass tries to distribute iterations of loops into several threads.
62 The implementation is straightforward -- for each loop we test whether its
63 iterations are independent, and if it is the case (and some additional
64 conditions regarding profitability and correctness are satisfied), we
65 add GIMPLE_OMP_PARALLEL and GIMPLE_OMP_FOR codes and let omp expansion
68 The most of the complexity is in bringing the code into shape expected
70 -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction
71 variable and that the exit test is at the start of the loop body
72 -- for GIMPLE_OMP_PARALLEL, replacing the references to local addressable
73 variables by accesses through pointers, and breaking up ssa chains
74 by storing the values incoming to the parallelized loop to a structure
75 passed to the new function as an argument (something similar is done
76 in omp gimplification, unfortunately only a small part of the code
80 -- if there are several parallelizable loops in a function, it may be
81 possible to generate the threads just once (using synchronization to
82 ensure that cross-loop dependences are obeyed).
83 -- handling of common reduction patterns for outer loops.
85 More info can also be found at http://gcc.gnu.org/wiki/AutoParInGCC */
88 currently we use vect_force_simple_reduction() to detect reduction patterns.
89 The code transformation will be introduced by an example.
96 for (i = 0; i < N; i++)
106 # sum_29 = PHI <sum_11(5), 1(3)>
107 # i_28 = PHI <i_12(5), 0(3)>
110 sum_11 = D.1795_8 + sum_29;
118 # sum_21 = PHI <sum_11(4)>
119 printf (&"%d"[0], sum_21);
122 after reduction transformation (only relevant parts):
130 # Storing the initial value given by the user. #
132 .paral_data_store.32.sum.27 = 1;
134 #pragma omp parallel num_threads(4)
136 #pragma omp for schedule(static)
138 # The neutral element corresponding to the particular
139 reduction's operation, e.g. 0 for PLUS_EXPR,
140 1 for MULT_EXPR, etc. replaces the user's initial value. #
142 # sum.27_29 = PHI <sum.27_11, 0>
144 sum.27_11 = D.1827_8 + sum.27_29;
148 # Adding this reduction phi is done at create_phi_for_local_result() #
149 # sum.27_56 = PHI <sum.27_11, 0>
152 # Creating the atomic operation is done at
153 create_call_for_reduction_1() #
155 #pragma omp atomic_load
156 D.1839_59 = *&.paral_data_load.33_51->reduction.23;
157 D.1840_60 = sum.27_56 + D.1839_59;
158 #pragma omp atomic_store (D.1840_60);
162 # collecting the result after the join of the threads is done at
163 create_loads_for_reductions().
164 The value computed by the threads is loaded from the
168 .paral_data_load.33_52 = &.paral_data_store.32;
169 sum_37 = .paral_data_load.33_52->sum.27;
170 sum_43 = D.1795_41 + sum_37;
173 # sum_21 = PHI <sum_43, sum_26>
174 printf (&"%d"[0], sum_21);
182 /* Minimal number of iterations of a loop that should be executed in each
184 #define MIN_PER_THREAD 100
186 /* Element of the hashtable, representing a
187 reduction in the current loop. */
188 struct reduction_info
190 gimple reduc_stmt
; /* reduction statement. */
191 gimple reduc_phi
; /* The phi node defining the reduction. */
192 enum tree_code reduction_code
;/* code for the reduction operation. */
193 unsigned reduc_version
; /* SSA_NAME_VERSION of original reduc_phi
195 gimple_phi keep_res
; /* The PHI_RESULT of this phi is the resulting value
196 of the reduction variable when existing the loop. */
197 tree initial_value
; /* The initial value of the reduction var before entering the loop. */
198 tree field
; /* the name of the field in the parloop data structure intended for reduction. */
199 tree init
; /* reduction initialization value. */
200 gimple_phi new_phi
; /* (helper field) Newly created phi node whose result
201 will be passed to the atomic operation. Represents
202 the local result each thread computed for the reduction
206 /* Reduction info hashtable helpers. */
208 struct reduction_hasher
: typed_free_remove
<reduction_info
>
210 typedef reduction_info value_type
;
211 typedef reduction_info compare_type
;
212 static inline hashval_t
hash (const value_type
*);
213 static inline bool equal (const value_type
*, const compare_type
*);
216 /* Equality and hash functions for hashtab code. */
219 reduction_hasher::equal (const value_type
*a
, const compare_type
*b
)
221 return (a
->reduc_phi
== b
->reduc_phi
);
225 reduction_hasher::hash (const value_type
*a
)
227 return a
->reduc_version
;
230 typedef hash_table
<reduction_hasher
> reduction_info_table_type
;
233 static struct reduction_info
*
234 reduction_phi (reduction_info_table_type
*reduction_list
, gimple phi
)
236 struct reduction_info tmpred
, *red
;
238 if (reduction_list
->elements () == 0 || phi
== NULL
)
241 tmpred
.reduc_phi
= phi
;
242 tmpred
.reduc_version
= gimple_uid (phi
);
243 red
= reduction_list
->find (&tmpred
);
248 /* Element of hashtable of names to copy. */
250 struct name_to_copy_elt
252 unsigned version
; /* The version of the name to copy. */
253 tree new_name
; /* The new name used in the copy. */
254 tree field
; /* The field of the structure used to pass the
258 /* Name copies hashtable helpers. */
260 struct name_to_copy_hasher
: typed_free_remove
<name_to_copy_elt
>
262 typedef name_to_copy_elt value_type
;
263 typedef name_to_copy_elt compare_type
;
264 static inline hashval_t
hash (const value_type
*);
265 static inline bool equal (const value_type
*, const compare_type
*);
268 /* Equality and hash functions for hashtab code. */
271 name_to_copy_hasher::equal (const value_type
*a
, const compare_type
*b
)
273 return a
->version
== b
->version
;
277 name_to_copy_hasher::hash (const value_type
*a
)
279 return (hashval_t
) a
->version
;
282 typedef hash_table
<name_to_copy_hasher
> name_to_copy_table_type
;
284 /* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
285 matrix. Rather than use floats, we simply keep a single DENOMINATOR that
286 represents the denominator for every element in the matrix. */
287 typedef struct lambda_trans_matrix_s
289 lambda_matrix matrix
;
293 } *lambda_trans_matrix
;
294 #define LTM_MATRIX(T) ((T)->matrix)
295 #define LTM_ROWSIZE(T) ((T)->rowsize)
296 #define LTM_COLSIZE(T) ((T)->colsize)
297 #define LTM_DENOMINATOR(T) ((T)->denominator)
299 /* Allocate a new transformation matrix. */
301 static lambda_trans_matrix
302 lambda_trans_matrix_new (int colsize
, int rowsize
,
303 struct obstack
* lambda_obstack
)
305 lambda_trans_matrix ret
;
307 ret
= (lambda_trans_matrix
)
308 obstack_alloc (lambda_obstack
, sizeof (struct lambda_trans_matrix_s
));
309 LTM_MATRIX (ret
) = lambda_matrix_new (rowsize
, colsize
, lambda_obstack
);
310 LTM_ROWSIZE (ret
) = rowsize
;
311 LTM_COLSIZE (ret
) = colsize
;
312 LTM_DENOMINATOR (ret
) = 1;
316 /* Multiply a vector VEC by a matrix MAT.
317 MAT is an M*N matrix, and VEC is a vector with length N. The result
318 is stored in DEST which must be a vector of length M. */
321 lambda_matrix_vector_mult (lambda_matrix matrix
, int m
, int n
,
322 lambda_vector vec
, lambda_vector dest
)
326 lambda_vector_clear (dest
, m
);
327 for (i
= 0; i
< m
; i
++)
328 for (j
= 0; j
< n
; j
++)
329 dest
[i
] += matrix
[i
][j
] * vec
[j
];
332 /* Return true if TRANS is a legal transformation matrix that respects
333 the dependence vectors in DISTS and DIRS. The conservative answer
336 "Wolfe proves that a unimodular transformation represented by the
337 matrix T is legal when applied to a loop nest with a set of
338 lexicographically non-negative distance vectors RDG if and only if
339 for each vector d in RDG, (T.d >= 0) is lexicographically positive.
340 i.e.: if and only if it transforms the lexicographically positive
341 distance vectors to lexicographically positive vectors. Note that
342 a unimodular matrix must transform the zero vector (and only it) to
343 the zero vector." S.Muchnick. */
346 lambda_transform_legal_p (lambda_trans_matrix trans
,
348 vec
<ddr_p
> dependence_relations
)
351 lambda_vector distres
;
352 struct data_dependence_relation
*ddr
;
354 gcc_assert (LTM_COLSIZE (trans
) == nb_loops
355 && LTM_ROWSIZE (trans
) == nb_loops
);
357 /* When there are no dependences, the transformation is correct. */
358 if (dependence_relations
.length () == 0)
361 ddr
= dependence_relations
[0];
365 /* When there is an unknown relation in the dependence_relations, we
366 know that it is no worth looking at this loop nest: give up. */
367 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
370 distres
= lambda_vector_new (nb_loops
);
372 /* For each distance vector in the dependence graph. */
373 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
375 /* Don't care about relations for which we know that there is no
376 dependence, nor about read-read (aka. output-dependences):
377 these data accesses can happen in any order. */
378 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
379 || (DR_IS_READ (DDR_A (ddr
)) && DR_IS_READ (DDR_B (ddr
))))
382 /* Conservatively answer: "this transformation is not valid". */
383 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
386 /* If the dependence could not be captured by a distance vector,
387 conservatively answer that the transform is not valid. */
388 if (DDR_NUM_DIST_VECTS (ddr
) == 0)
391 /* Compute trans.dist_vect */
392 for (j
= 0; j
< DDR_NUM_DIST_VECTS (ddr
); j
++)
394 lambda_matrix_vector_mult (LTM_MATRIX (trans
), nb_loops
, nb_loops
,
395 DDR_DIST_VECT (ddr
, j
), distres
);
397 if (!lambda_vector_lexico_pos (distres
, nb_loops
))
404 /* Data dependency analysis. Returns true if the iterations of LOOP
405 are independent on each other (that is, if we can execute them
409 loop_parallel_p (struct loop
*loop
, struct obstack
* parloop_obstack
)
411 vec
<ddr_p
> dependence_relations
;
412 vec
<data_reference_p
> datarefs
;
413 lambda_trans_matrix trans
;
416 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
418 fprintf (dump_file
, "Considering loop %d\n", loop
->num
);
420 fprintf (dump_file
, "loop is innermost\n");
422 fprintf (dump_file
, "loop NOT innermost\n");
425 /* Check for problems with dependences. If the loop can be reversed,
426 the iterations are independent. */
427 auto_vec
<loop_p
, 3> loop_nest
;
428 datarefs
.create (10);
429 dependence_relations
.create (100);
430 if (! compute_data_dependences_for_loop (loop
, true, &loop_nest
, &datarefs
,
431 &dependence_relations
))
433 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
434 fprintf (dump_file
, " FAILED: cannot analyze data dependencies\n");
438 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
439 dump_data_dependence_relations (dump_file
, dependence_relations
);
441 trans
= lambda_trans_matrix_new (1, 1, parloop_obstack
);
442 LTM_MATRIX (trans
)[0][0] = -1;
444 if (lambda_transform_legal_p (trans
, 1, dependence_relations
))
447 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
448 fprintf (dump_file
, " SUCCESS: may be parallelized\n");
450 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
452 " FAILED: data dependencies exist across iterations\n");
455 free_dependence_relations (dependence_relations
);
456 free_data_refs (datarefs
);
461 /* Return true when LOOP contains basic blocks marked with the
462 BB_IRREDUCIBLE_LOOP flag. */
465 loop_has_blocks_with_irreducible_flag (struct loop
*loop
)
468 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
471 for (i
= 0; i
< loop
->num_nodes
; i
++)
472 if (bbs
[i
]->flags
& BB_IRREDUCIBLE_LOOP
)
481 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
482 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
483 to their addresses that can be reused. The address of OBJ is known to
484 be invariant in the whole function. Other needed statements are placed
488 take_address_of (tree obj
, tree type
, edge entry
,
489 int_tree_htab_type
*decl_address
, gimple_stmt_iterator
*gsi
)
492 tree
*var_p
, name
, addr
;
496 /* Since the address of OBJ is invariant, the trees may be shared.
497 Avoid rewriting unrelated parts of the code. */
498 obj
= unshare_expr (obj
);
500 handled_component_p (*var_p
);
501 var_p
= &TREE_OPERAND (*var_p
, 0))
504 /* Canonicalize the access to base on a MEM_REF. */
506 *var_p
= build_simple_mem_ref (build_fold_addr_expr (*var_p
));
508 /* Assign a canonical SSA name to the address of the base decl used
509 in the address and share it for all accesses and addresses based
511 uid
= DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p
, 0), 0));
514 int_tree_map
*slot
= decl_address
->find_slot (elt
, INSERT
);
519 addr
= TREE_OPERAND (*var_p
, 0);
521 = get_name (TREE_OPERAND (TREE_OPERAND (*var_p
, 0), 0));
523 name
= make_temp_ssa_name (TREE_TYPE (addr
), NULL
, obj_name
);
525 name
= make_ssa_name (TREE_TYPE (addr
), NULL
);
526 stmt
= gimple_build_assign (name
, addr
);
527 gsi_insert_on_edge_immediate (entry
, stmt
);
535 /* Express the address in terms of the canonical SSA name. */
536 TREE_OPERAND (*var_p
, 0) = name
;
538 return build_fold_addr_expr_with_type (obj
, type
);
540 name
= force_gimple_operand (build_addr (obj
, current_function_decl
),
541 &stmts
, true, NULL_TREE
);
542 if (!gimple_seq_empty_p (stmts
))
543 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
545 if (!useless_type_conversion_p (type
, TREE_TYPE (name
)))
547 name
= force_gimple_operand (fold_convert (type
, name
), &stmts
, true,
549 if (!gimple_seq_empty_p (stmts
))
550 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
556 /* Callback for htab_traverse. Create the initialization statement
557 for reduction described in SLOT, and place it at the preheader of
558 the loop described in DATA. */
561 initialize_reductions (reduction_info
**slot
, struct loop
*loop
)
564 tree bvar
, type
, arg
;
567 struct reduction_info
*const reduc
= *slot
;
569 /* Create initialization in preheader:
570 reduction_variable = initialization value of reduction. */
572 /* In the phi node at the header, replace the argument coming
573 from the preheader with the reduction initialization value. */
575 /* Create a new variable to initialize the reduction. */
576 type
= TREE_TYPE (PHI_RESULT (reduc
->reduc_phi
));
577 bvar
= create_tmp_var (type
, "reduction");
579 c
= build_omp_clause (gimple_location (reduc
->reduc_stmt
),
580 OMP_CLAUSE_REDUCTION
);
581 OMP_CLAUSE_REDUCTION_CODE (c
) = reduc
->reduction_code
;
582 OMP_CLAUSE_DECL (c
) = SSA_NAME_VAR (gimple_assign_lhs (reduc
->reduc_stmt
));
584 init
= omp_reduction_init (c
, TREE_TYPE (bvar
));
587 /* Replace the argument representing the initialization value
588 with the initialization value for the reduction (neutral
589 element for the particular operation, e.g. 0 for PLUS_EXPR,
590 1 for MULT_EXPR, etc).
591 Keep the old value in a new variable "reduction_initial",
592 that will be taken in consideration after the parallel
593 computing is done. */
595 e
= loop_preheader_edge (loop
);
596 arg
= PHI_ARG_DEF_FROM_EDGE (reduc
->reduc_phi
, e
);
597 /* Create new variable to hold the initial value. */
599 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
600 (reduc
->reduc_phi
, loop_preheader_edge (loop
)), init
);
601 reduc
->initial_value
= arg
;
607 struct walk_stmt_info info
;
609 int_tree_htab_type
*decl_address
;
610 gimple_stmt_iterator
*gsi
;
615 /* Eliminates references to local variables in *TP out of the single
616 entry single exit region starting at DTA->ENTRY.
617 DECL_ADDRESS contains addresses of the references that had their
618 address taken already. If the expression is changed, CHANGED is
619 set to true. Callback for walk_tree. */
622 eliminate_local_variables_1 (tree
*tp
, int *walk_subtrees
, void *data
)
624 struct elv_data
*const dta
= (struct elv_data
*) data
;
625 tree t
= *tp
, var
, addr
, addr_type
, type
, obj
;
631 if (!SSA_VAR_P (t
) || DECL_EXTERNAL (t
))
634 type
= TREE_TYPE (t
);
635 addr_type
= build_pointer_type (type
);
636 addr
= take_address_of (t
, addr_type
, dta
->entry
, dta
->decl_address
,
638 if (dta
->gsi
== NULL
&& addr
== NULL_TREE
)
644 *tp
= build_simple_mem_ref (addr
);
650 if (TREE_CODE (t
) == ADDR_EXPR
)
652 /* ADDR_EXPR may appear in two contexts:
653 -- as a gimple operand, when the address taken is a function invariant
654 -- as gimple rhs, when the resulting address in not a function
656 We do not need to do anything special in the latter case (the base of
657 the memory reference whose address is taken may be replaced in the
658 DECL_P case). The former case is more complicated, as we need to
659 ensure that the new address is still a gimple operand. Thus, it
660 is not sufficient to replace just the base of the memory reference --
661 we need to move the whole computation of the address out of the
663 if (!is_gimple_val (t
))
667 obj
= TREE_OPERAND (t
, 0);
668 var
= get_base_address (obj
);
669 if (!var
|| !SSA_VAR_P (var
) || DECL_EXTERNAL (var
))
672 addr_type
= TREE_TYPE (t
);
673 addr
= take_address_of (obj
, addr_type
, dta
->entry
, dta
->decl_address
,
675 if (dta
->gsi
== NULL
&& addr
== NULL_TREE
)
692 /* Moves the references to local variables in STMT at *GSI out of the single
693 entry single exit region starting at ENTRY. DECL_ADDRESS contains
694 addresses of the references that had their address taken
698 eliminate_local_variables_stmt (edge entry
, gimple_stmt_iterator
*gsi
,
699 int_tree_htab_type
*decl_address
)
702 gimple stmt
= gsi_stmt (*gsi
);
704 memset (&dta
.info
, '\0', sizeof (dta
.info
));
706 dta
.decl_address
= decl_address
;
710 if (gimple_debug_bind_p (stmt
))
713 walk_tree (gimple_debug_bind_get_value_ptr (stmt
),
714 eliminate_local_variables_1
, &dta
.info
, NULL
);
717 gimple_debug_bind_reset_value (stmt
);
721 else if (gimple_clobber_p (stmt
))
723 stmt
= gimple_build_nop ();
724 gsi_replace (gsi
, stmt
, false);
730 walk_gimple_op (stmt
, eliminate_local_variables_1
, &dta
.info
);
737 /* Eliminates the references to local variables from the single entry
738 single exit region between the ENTRY and EXIT edges.
741 1) Taking address of a local variable -- these are moved out of the
742 region (and temporary variable is created to hold the address if
745 2) Dereferencing a local variable -- these are replaced with indirect
749 eliminate_local_variables (edge entry
, edge exit
)
752 auto_vec
<basic_block
, 3> body
;
754 gimple_stmt_iterator gsi
;
755 bool has_debug_stmt
= false;
756 int_tree_htab_type
decl_address (10);
757 basic_block entry_bb
= entry
->src
;
758 basic_block exit_bb
= exit
->dest
;
760 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
762 FOR_EACH_VEC_ELT (body
, i
, bb
)
763 if (bb
!= entry_bb
&& bb
!= exit_bb
)
764 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
765 if (is_gimple_debug (gsi_stmt (gsi
)))
767 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
768 has_debug_stmt
= true;
771 eliminate_local_variables_stmt (entry
, &gsi
, &decl_address
);
774 FOR_EACH_VEC_ELT (body
, i
, bb
)
775 if (bb
!= entry_bb
&& bb
!= exit_bb
)
776 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
777 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
778 eliminate_local_variables_stmt (entry
, &gsi
, &decl_address
);
781 /* Returns true if expression EXPR is not defined between ENTRY and
782 EXIT, i.e. if all its operands are defined outside of the region. */
785 expr_invariant_in_region_p (edge entry
, edge exit
, tree expr
)
787 basic_block entry_bb
= entry
->src
;
788 basic_block exit_bb
= exit
->dest
;
791 if (is_gimple_min_invariant (expr
))
794 if (TREE_CODE (expr
) == SSA_NAME
)
796 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
798 && dominated_by_p (CDI_DOMINATORS
, def_bb
, entry_bb
)
799 && !dominated_by_p (CDI_DOMINATORS
, def_bb
, exit_bb
))
808 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
809 The copies are stored to NAME_COPIES, if NAME was already duplicated,
810 its duplicate stored in NAME_COPIES is returned.
812 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
813 duplicated, storing the copies in DECL_COPIES. */
816 separate_decls_in_region_name (tree name
, name_to_copy_table_type
*name_copies
,
817 int_tree_htab_type
*decl_copies
,
820 tree copy
, var
, var_copy
;
821 unsigned idx
, uid
, nuid
;
822 struct int_tree_map ielt
;
823 struct name_to_copy_elt elt
, *nelt
;
824 name_to_copy_elt
**slot
;
827 if (TREE_CODE (name
) != SSA_NAME
)
830 idx
= SSA_NAME_VERSION (name
);
832 slot
= name_copies
->find_slot_with_hash (&elt
, idx
,
833 copy_name_p
? INSERT
: NO_INSERT
);
835 return (*slot
)->new_name
;
839 copy
= duplicate_ssa_name (name
, NULL
);
840 nelt
= XNEW (struct name_to_copy_elt
);
842 nelt
->new_name
= copy
;
843 nelt
->field
= NULL_TREE
;
852 var
= SSA_NAME_VAR (name
);
856 uid
= DECL_UID (var
);
858 dslot
= decl_copies
->find_slot_with_hash (ielt
, uid
, INSERT
);
861 var_copy
= create_tmp_var (TREE_TYPE (var
), get_name (var
));
862 DECL_GIMPLE_REG_P (var_copy
) = DECL_GIMPLE_REG_P (var
);
864 dslot
->to
= var_copy
;
866 /* Ensure that when we meet this decl next time, we won't duplicate
868 nuid
= DECL_UID (var_copy
);
870 dslot
= decl_copies
->find_slot_with_hash (ielt
, nuid
, INSERT
);
871 gcc_assert (!dslot
->to
);
873 dslot
->to
= var_copy
;
876 var_copy
= 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
;
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
, dslot
->to
);
957 else if (gimple_debug_source_bind_p (stmt
))
958 gimple_debug_source_bind_set_var (stmt
, 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 (10);
1290 int_tree_htab_type
decl_copies (10);
1292 tree type
, type_name
, nvar
;
1293 gimple_stmt_iterator gsi
;
1294 struct clsn_data clsn_data
;
1295 auto_vec
<basic_block
, 3> body
;
1297 basic_block entry_bb
= bb1
;
1298 basic_block exit_bb
= exit
->dest
;
1299 bool has_debug_stmt
= false;
1301 entry
= single_succ_edge (entry_bb
);
1302 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
1304 FOR_EACH_VEC_ELT (body
, i
, bb
)
1306 if (bb
!= entry_bb
&& bb
!= exit_bb
)
1308 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1309 separate_decls_in_region_stmt (entry
, exit
, gsi_stmt (gsi
),
1310 &name_copies
, &decl_copies
);
1312 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1314 gimple stmt
= gsi_stmt (gsi
);
1316 if (is_gimple_debug (stmt
))
1317 has_debug_stmt
= true;
1319 separate_decls_in_region_stmt (entry
, exit
, stmt
,
1320 &name_copies
, &decl_copies
);
1325 /* Now process debug bind stmts. We must not create decls while
1326 processing debug stmts, so we defer their processing so as to
1327 make sure we will have debug info for as many variables as
1328 possible (all of those that were dealt with in the loop above),
1329 and discard those for which we know there's nothing we can
1332 FOR_EACH_VEC_ELT (body
, i
, bb
)
1333 if (bb
!= entry_bb
&& bb
!= exit_bb
)
1335 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
1337 gimple stmt
= gsi_stmt (gsi
);
1339 if (is_gimple_debug (stmt
))
1341 if (separate_decls_in_region_debug (stmt
, &name_copies
,
1344 gsi_remove (&gsi
, true);
1353 if (name_copies
.elements () == 0 && reduction_list
->elements () == 0)
1355 /* It may happen that there is nothing to copy (if there are only
1356 loop carried and external variables in the loop). */
1358 *new_arg_struct
= NULL
;
1362 /* Create the type for the structure to store the ssa names to. */
1363 type
= lang_hooks
.types
.make_type (RECORD_TYPE
);
1364 type_name
= build_decl (UNKNOWN_LOCATION
,
1365 TYPE_DECL
, create_tmp_var_name (".paral_data"),
1367 TYPE_NAME (type
) = type_name
;
1369 name_copies
.traverse
<tree
, add_field_for_name
> (type
);
1370 if (reduction_list
&& reduction_list
->elements () > 0)
1372 /* Create the fields for reductions. */
1373 reduction_list
->traverse
<tree
, add_field_for_reduction
> (type
);
1377 /* Create the loads and stores. */
1378 *arg_struct
= create_tmp_var (type
, ".paral_data_store");
1379 nvar
= create_tmp_var (build_pointer_type (type
), ".paral_data_load");
1380 *new_arg_struct
= make_ssa_name (nvar
, NULL
);
1382 ld_st_data
->store
= *arg_struct
;
1383 ld_st_data
->load
= *new_arg_struct
;
1384 ld_st_data
->store_bb
= bb0
;
1385 ld_st_data
->load_bb
= bb1
;
1388 .traverse
<struct clsn_data
*, create_loads_and_stores_for_name
>
1391 /* Load the calculation from memory (after the join of the threads). */
1393 if (reduction_list
&& reduction_list
->elements () > 0)
1396 ->traverse
<struct clsn_data
*, create_stores_for_reduction
>
1398 clsn_data
.load
= make_ssa_name (nvar
, NULL
);
1399 clsn_data
.load_bb
= exit
->dest
;
1400 clsn_data
.store
= ld_st_data
->store
;
1401 create_final_loads_for_reduction (reduction_list
, &clsn_data
);
1406 /* Bitmap containing uids of functions created by parallelization. We cannot
1407 allocate it from the default obstack, as it must live across compilation
1408 of several functions; we make it gc allocated instead. */
1410 static GTY(()) bitmap parallelized_functions
;
1412 /* Returns true if FN was created by create_loop_fn. */
1415 parallelized_function_p (tree fn
)
1417 if (!parallelized_functions
|| !DECL_ARTIFICIAL (fn
))
1420 return bitmap_bit_p (parallelized_functions
, DECL_UID (fn
));
1423 /* Creates and returns an empty function that will receive the body of
1424 a parallelized loop. */
1427 create_loop_fn (location_t loc
)
1431 tree decl
, type
, name
, t
;
1432 struct function
*act_cfun
= cfun
;
1433 static unsigned loopfn_num
;
1435 loc
= LOCATION_LOCUS (loc
);
1436 snprintf (buf
, 100, "%s.$loopfn", current_function_name ());
1437 ASM_FORMAT_PRIVATE_NAME (tname
, buf
, loopfn_num
++);
1438 clean_symbol_name (tname
);
1439 name
= get_identifier (tname
);
1440 type
= build_function_type_list (void_type_node
, ptr_type_node
, NULL_TREE
);
1442 decl
= build_decl (loc
, FUNCTION_DECL
, name
, type
);
1443 if (!parallelized_functions
)
1444 parallelized_functions
= BITMAP_GGC_ALLOC ();
1445 bitmap_set_bit (parallelized_functions
, DECL_UID (decl
));
1447 TREE_STATIC (decl
) = 1;
1448 TREE_USED (decl
) = 1;
1449 DECL_ARTIFICIAL (decl
) = 1;
1450 DECL_IGNORED_P (decl
) = 0;
1451 TREE_PUBLIC (decl
) = 0;
1452 DECL_UNINLINABLE (decl
) = 1;
1453 DECL_EXTERNAL (decl
) = 0;
1454 DECL_CONTEXT (decl
) = NULL_TREE
;
1455 DECL_INITIAL (decl
) = make_node (BLOCK
);
1457 t
= build_decl (loc
, RESULT_DECL
, NULL_TREE
, void_type_node
);
1458 DECL_ARTIFICIAL (t
) = 1;
1459 DECL_IGNORED_P (t
) = 1;
1460 DECL_RESULT (decl
) = t
;
1462 t
= build_decl (loc
, PARM_DECL
, get_identifier (".paral_data_param"),
1464 DECL_ARTIFICIAL (t
) = 1;
1465 DECL_ARG_TYPE (t
) = ptr_type_node
;
1466 DECL_CONTEXT (t
) = decl
;
1468 DECL_ARGUMENTS (decl
) = t
;
1470 allocate_struct_function (decl
, false);
1472 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1474 set_cfun (act_cfun
);
1479 /* Moves the exit condition of LOOP to the beginning of its header, and
1480 duplicates the part of the last iteration that gets disabled to the
1481 exit of the loop. NIT is the number of iterations of the loop
1482 (used to initialize the variables in the duplicated part).
1484 TODO: the common case is that latch of the loop is empty and immediately
1485 follows the loop exit. In this case, it would be better not to copy the
1486 body of the loop, but only move the entry of the loop directly before the
1487 exit check and increase the number of iterations of the loop by one.
1488 This may need some additional preconditioning in case NIT = ~0.
1489 REDUCTION_LIST describes the reductions in LOOP. */
1492 transform_to_exit_first_loop (struct loop
*loop
,
1493 reduction_info_table_type
*reduction_list
,
1496 basic_block
*bbs
, *nbbs
, ex_bb
, orig_header
;
1499 edge exit
= single_dom_exit (loop
), hpred
;
1500 tree control
, control_name
, res
, t
;
1501 gimple_phi phi
, nphi
;
1503 gimple_cond cond_stmt
, cond_nit
;
1506 split_block_after_labels (loop
->header
);
1507 orig_header
= single_succ (loop
->header
);
1508 hpred
= single_succ_edge (loop
->header
);
1510 cond_stmt
= as_a
<gimple_cond
> (last_stmt (exit
->src
));
1511 control
= gimple_cond_lhs (cond_stmt
);
1512 gcc_assert (gimple_cond_rhs (cond_stmt
) == nit
);
1514 /* Make sure that we have phi nodes on exit for all loop header phis
1515 (create_parallel_loop requires that). */
1516 for (gimple_phi_iterator gsi
= gsi_start_phis (loop
->header
);
1521 res
= PHI_RESULT (phi
);
1522 t
= copy_ssa_name (res
, phi
);
1523 SET_PHI_RESULT (phi
, t
);
1524 nphi
= create_phi_node (res
, orig_header
);
1525 add_phi_arg (nphi
, t
, hpred
, UNKNOWN_LOCATION
);
1529 gimple_cond_set_lhs (cond_stmt
, t
);
1530 update_stmt (cond_stmt
);
1535 bbs
= get_loop_body_in_dom_order (loop
);
1537 for (n
= 0; bbs
[n
] != exit
->src
; n
++)
1539 nbbs
= XNEWVEC (basic_block
, n
);
1540 ok
= gimple_duplicate_sese_tail (single_succ_edge (loop
->header
), exit
,
1547 /* Other than reductions, the only gimple reg that should be copied
1548 out of the loop is the control variable. */
1549 exit
= single_dom_exit (loop
);
1550 control_name
= NULL_TREE
;
1551 for (gimple_phi_iterator gsi
= gsi_start_phis (ex_bb
);
1555 res
= PHI_RESULT (phi
);
1556 if (virtual_operand_p (res
))
1562 /* Check if it is a part of reduction. If it is,
1563 keep the phi at the reduction's keep_res field. The
1564 PHI_RESULT of this phi is the resulting value of the reduction
1565 variable when exiting the loop. */
1567 if (reduction_list
->elements () > 0)
1569 struct reduction_info
*red
;
1571 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1572 red
= reduction_phi (reduction_list
, SSA_NAME_DEF_STMT (val
));
1575 red
->keep_res
= phi
;
1580 gcc_assert (control_name
== NULL_TREE
1581 && SSA_NAME_VAR (res
) == SSA_NAME_VAR (control
));
1583 remove_phi_node (&gsi
, false);
1585 gcc_assert (control_name
!= NULL_TREE
);
1587 /* Initialize the control variable to number of iterations
1588 according to the rhs of the exit condition. */
1589 gimple_stmt_iterator gsi
= gsi_after_labels (ex_bb
);
1590 cond_nit
= as_a
<gimple_cond
> (last_stmt (exit
->src
));
1591 nit_1
= gimple_cond_rhs (cond_nit
);
1592 nit_1
= force_gimple_operand_gsi (&gsi
,
1593 fold_convert (TREE_TYPE (control_name
), nit_1
),
1594 false, NULL_TREE
, false, GSI_SAME_STMT
);
1595 stmt
= gimple_build_assign (control_name
, nit_1
);
1596 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1599 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
1600 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
1601 NEW_DATA is the variable that should be initialized from the argument
1602 of LOOP_FN. N_THREADS is the requested number of threads. Returns the
1603 basic block containing GIMPLE_OMP_PARALLEL tree. */
1606 create_parallel_loop (struct loop
*loop
, tree loop_fn
, tree data
,
1607 tree new_data
, unsigned n_threads
, location_t loc
)
1609 gimple_stmt_iterator gsi
;
1610 basic_block bb
, paral_bb
, for_bb
, ex_bb
;
1612 gimple_omp_parallel omp_par_stmt
;
1613 gimple omp_return_stmt1
, omp_return_stmt2
;
1615 gimple_cond cond_stmt
;
1616 gimple_omp_for for_stmt
;
1617 gimple_omp_continue omp_cont_stmt
;
1618 tree cvar
, cvar_init
, initvar
, cvar_next
, cvar_base
, type
;
1619 edge exit
, nexit
, guard
, end
, e
;
1621 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
1622 bb
= loop_preheader_edge (loop
)->src
;
1623 paral_bb
= single_pred (bb
);
1624 gsi
= gsi_last_bb (paral_bb
);
1626 t
= build_omp_clause (loc
, OMP_CLAUSE_NUM_THREADS
);
1627 OMP_CLAUSE_NUM_THREADS_EXPR (t
)
1628 = build_int_cst (integer_type_node
, n_threads
);
1629 omp_par_stmt
= gimple_build_omp_parallel (NULL
, t
, loop_fn
, data
);
1630 gimple_set_location (omp_par_stmt
, loc
);
1632 gsi_insert_after (&gsi
, omp_par_stmt
, GSI_NEW_STMT
);
1634 /* Initialize NEW_DATA. */
1637 gimple_assign assign_stmt
;
1639 gsi
= gsi_after_labels (bb
);
1641 param
= make_ssa_name (DECL_ARGUMENTS (loop_fn
), NULL
);
1642 assign_stmt
= gimple_build_assign (param
, build_fold_addr_expr (data
));
1643 gsi_insert_before (&gsi
, assign_stmt
, GSI_SAME_STMT
);
1645 assign_stmt
= gimple_build_assign (new_data
,
1646 fold_convert (TREE_TYPE (new_data
), param
));
1647 gsi_insert_before (&gsi
, assign_stmt
, GSI_SAME_STMT
);
1650 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
1651 bb
= split_loop_exit_edge (single_dom_exit (loop
));
1652 gsi
= gsi_last_bb (bb
);
1653 omp_return_stmt1
= gimple_build_omp_return (false);
1654 gimple_set_location (omp_return_stmt1
, loc
);
1655 gsi_insert_after (&gsi
, omp_return_stmt1
, GSI_NEW_STMT
);
1657 /* Extract data for GIMPLE_OMP_FOR. */
1658 gcc_assert (loop
->header
== single_dom_exit (loop
)->src
);
1659 cond_stmt
= as_a
<gimple_cond
> (last_stmt (loop
->header
));
1661 cvar
= gimple_cond_lhs (cond_stmt
);
1662 cvar_base
= SSA_NAME_VAR (cvar
);
1663 phi
= SSA_NAME_DEF_STMT (cvar
);
1664 cvar_init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
1665 initvar
= copy_ssa_name (cvar
, NULL
);
1666 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, loop_preheader_edge (loop
)),
1668 cvar_next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
1670 gsi
= gsi_last_nondebug_bb (loop
->latch
);
1671 gcc_assert (gsi_stmt (gsi
) == SSA_NAME_DEF_STMT (cvar_next
));
1672 gsi_remove (&gsi
, true);
1675 for_bb
= split_edge (loop_preheader_edge (loop
));
1676 ex_bb
= split_loop_exit_edge (single_dom_exit (loop
));
1677 extract_true_false_edges_from_block (loop
->header
, &nexit
, &exit
);
1678 gcc_assert (exit
== single_dom_exit (loop
));
1680 guard
= make_edge (for_bb
, ex_bb
, 0);
1681 single_succ_edge (loop
->latch
)->flags
= 0;
1682 end
= make_edge (loop
->latch
, ex_bb
, EDGE_FALLTHRU
);
1683 for (gimple_phi_iterator gpi
= gsi_start_phis (ex_bb
);
1684 !gsi_end_p (gpi
); gsi_next (&gpi
))
1686 source_location locus
;
1688 gimple_phi phi
= gpi
.phi ();
1691 stmt
= as_a
<gimple_phi
> (
1692 SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi
, exit
)));
1694 def
= PHI_ARG_DEF_FROM_EDGE (stmt
, loop_preheader_edge (loop
));
1695 locus
= gimple_phi_arg_location_from_edge (stmt
,
1696 loop_preheader_edge (loop
));
1697 add_phi_arg (phi
, def
, guard
, locus
);
1699 def
= PHI_ARG_DEF_FROM_EDGE (stmt
, loop_latch_edge (loop
));
1700 locus
= gimple_phi_arg_location_from_edge (stmt
, loop_latch_edge (loop
));
1701 add_phi_arg (phi
, def
, end
, locus
);
1703 e
= redirect_edge_and_branch (exit
, nexit
->dest
);
1704 PENDING_STMT (e
) = NULL
;
1706 /* Emit GIMPLE_OMP_FOR. */
1707 gimple_cond_set_lhs (cond_stmt
, cvar_base
);
1708 type
= TREE_TYPE (cvar
);
1709 t
= build_omp_clause (loc
, OMP_CLAUSE_SCHEDULE
);
1710 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_STATIC
;
1712 for_stmt
= gimple_build_omp_for (NULL
, GF_OMP_FOR_KIND_FOR
, t
, 1, NULL
);
1713 gimple_set_location (for_stmt
, loc
);
1714 gimple_omp_for_set_index (for_stmt
, 0, initvar
);
1715 gimple_omp_for_set_initial (for_stmt
, 0, cvar_init
);
1716 gimple_omp_for_set_final (for_stmt
, 0, gimple_cond_rhs (cond_stmt
));
1717 gimple_omp_for_set_cond (for_stmt
, 0, gimple_cond_code (cond_stmt
));
1718 gimple_omp_for_set_incr (for_stmt
, 0, build2 (PLUS_EXPR
, type
,
1720 build_int_cst (type
, 1)));
1722 gsi
= gsi_last_bb (for_bb
);
1723 gsi_insert_after (&gsi
, for_stmt
, GSI_NEW_STMT
);
1724 SSA_NAME_DEF_STMT (initvar
) = for_stmt
;
1726 /* Emit GIMPLE_OMP_CONTINUE. */
1727 gsi
= gsi_last_bb (loop
->latch
);
1728 omp_cont_stmt
= gimple_build_omp_continue (cvar_next
, cvar
);
1729 gimple_set_location (omp_cont_stmt
, loc
);
1730 gsi_insert_after (&gsi
, omp_cont_stmt
, GSI_NEW_STMT
);
1731 SSA_NAME_DEF_STMT (cvar_next
) = omp_cont_stmt
;
1733 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
1734 gsi
= gsi_last_bb (ex_bb
);
1735 omp_return_stmt2
= gimple_build_omp_return (true);
1736 gimple_set_location (omp_return_stmt2
, loc
);
1737 gsi_insert_after (&gsi
, omp_return_stmt2
, GSI_NEW_STMT
);
1739 /* After the above dom info is hosed. Re-compute it. */
1740 free_dominance_info (CDI_DOMINATORS
);
1741 calculate_dominance_info (CDI_DOMINATORS
);
1746 /* Generates code to execute the iterations of LOOP in N_THREADS
1747 threads in parallel.
1749 NITER describes number of iterations of LOOP.
1750 REDUCTION_LIST describes the reductions existent in the LOOP. */
1753 gen_parallel_loop (struct loop
*loop
,
1754 reduction_info_table_type
*reduction_list
,
1755 unsigned n_threads
, struct tree_niter_desc
*niter
)
1757 tree many_iterations_cond
, type
, nit
;
1758 tree arg_struct
, new_arg_struct
;
1760 basic_block parallel_head
;
1762 struct clsn_data clsn_data
;
1766 unsigned int m_p_thread
=2;
1770 ---------------------------------------------------------------------
1773 IV = phi (INIT, IV + STEP)
1779 ---------------------------------------------------------------------
1781 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
1782 we generate the following code:
1784 ---------------------------------------------------------------------
1787 || NITER < MIN_PER_THREAD * N_THREADS)
1791 store all local loop-invariant variables used in body of the loop to DATA.
1792 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
1793 load the variables from DATA.
1794 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
1797 GIMPLE_OMP_CONTINUE;
1798 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
1799 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
1805 IV = phi (INIT, IV + STEP)
1816 /* Create two versions of the loop -- in the old one, we know that the
1817 number of iterations is large enough, and we will transform it into the
1818 loop that will be split to loop_fn, the new one will be used for the
1819 remaining iterations. */
1821 /* We should compute a better number-of-iterations value for outer loops.
1824 for (i = 0; i < n; ++i)
1825 for (j = 0; j < m; ++j)
1828 we should compute nit = n * m, not nit = n.
1829 Also may_be_zero handling would need to be adjusted. */
1831 type
= TREE_TYPE (niter
->niter
);
1832 nit
= force_gimple_operand (unshare_expr (niter
->niter
), &stmts
, true,
1835 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1840 m_p_thread
=MIN_PER_THREAD
;
1842 many_iterations_cond
=
1843 fold_build2 (GE_EXPR
, boolean_type_node
,
1844 nit
, build_int_cst (type
, m_p_thread
* n_threads
));
1846 many_iterations_cond
1847 = fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
1848 invert_truthvalue (unshare_expr (niter
->may_be_zero
)),
1849 many_iterations_cond
);
1850 many_iterations_cond
1851 = force_gimple_operand (many_iterations_cond
, &stmts
, false, NULL_TREE
);
1853 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1854 if (!is_gimple_condexpr (many_iterations_cond
))
1856 many_iterations_cond
1857 = force_gimple_operand (many_iterations_cond
, &stmts
,
1860 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
1863 initialize_original_copy_tables ();
1865 /* We assume that the loop usually iterates a lot. */
1866 prob
= 4 * REG_BR_PROB_BASE
/ 5;
1867 loop_version (loop
, many_iterations_cond
, NULL
,
1868 prob
, prob
, REG_BR_PROB_BASE
- prob
, true);
1869 update_ssa (TODO_update_ssa
);
1870 free_original_copy_tables ();
1872 /* Base all the induction variables in LOOP on a single control one. */
1873 canonicalize_loop_ivs (loop
, &nit
, true);
1875 /* Ensure that the exit condition is the first statement in the loop. */
1876 transform_to_exit_first_loop (loop
, reduction_list
, nit
);
1878 /* Generate initializations for reductions. */
1879 if (reduction_list
->elements () > 0)
1880 reduction_list
->traverse
<struct loop
*, initialize_reductions
> (loop
);
1882 /* Eliminate the references to local variables from the loop. */
1883 gcc_assert (single_exit (loop
));
1884 entry
= loop_preheader_edge (loop
);
1885 exit
= single_dom_exit (loop
);
1887 eliminate_local_variables (entry
, exit
);
1888 /* In the old loop, move all variables non-local to the loop to a structure
1889 and back, and create separate decls for the variables used in loop. */
1890 separate_decls_in_region (entry
, exit
, reduction_list
, &arg_struct
,
1891 &new_arg_struct
, &clsn_data
);
1893 /* Create the parallel constructs. */
1894 loc
= UNKNOWN_LOCATION
;
1895 cond_stmt
= last_stmt (loop
->header
);
1897 loc
= gimple_location (cond_stmt
);
1898 parallel_head
= create_parallel_loop (loop
, create_loop_fn (loc
), arg_struct
,
1899 new_arg_struct
, n_threads
, loc
);
1900 if (reduction_list
->elements () > 0)
1901 create_call_for_reduction (loop
, reduction_list
, &clsn_data
);
1905 /* Cancel the loop (it is simpler to do it here rather than to teach the
1906 expander to do it). */
1907 cancel_loop_tree (loop
);
1909 /* Free loop bound estimations that could contain references to
1910 removed statements. */
1911 FOR_EACH_LOOP (loop
, 0)
1912 free_numbers_of_iterations_estimates_loop (loop
);
1914 /* Expand the parallel constructs. We do it directly here instead of running
1915 a separate expand_omp pass, since it is more efficient, and less likely to
1916 cause troubles with further analyses not being able to deal with the
1919 omp_expand_local (parallel_head
);
1922 /* Returns true when LOOP contains vector phi nodes. */
1925 loop_has_vector_phi_nodes (struct loop
*loop ATTRIBUTE_UNUSED
)
1928 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
1929 gimple_stmt_iterator gsi
;
1932 for (i
= 0; i
< loop
->num_nodes
; i
++)
1933 for (gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
1934 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi_stmt (gsi
)))) == VECTOR_TYPE
)
1943 /* Create a reduction_info struct, initialize it with REDUC_STMT
1944 and PHI, insert it to the REDUCTION_LIST. */
1947 build_new_reduction (reduction_info_table_type
*reduction_list
,
1948 gimple reduc_stmt
, gimple_phi phi
)
1950 reduction_info
**slot
;
1951 struct reduction_info
*new_reduction
;
1953 gcc_assert (reduc_stmt
);
1955 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1958 "Detected reduction. reduction stmt is: \n");
1959 print_gimple_stmt (dump_file
, reduc_stmt
, 0, 0);
1960 fprintf (dump_file
, "\n");
1963 new_reduction
= XCNEW (struct reduction_info
);
1965 new_reduction
->reduc_stmt
= reduc_stmt
;
1966 new_reduction
->reduc_phi
= phi
;
1967 new_reduction
->reduc_version
= SSA_NAME_VERSION (gimple_phi_result (phi
));
1968 new_reduction
->reduction_code
= gimple_assign_rhs_code (reduc_stmt
);
1969 slot
= reduction_list
->find_slot (new_reduction
, INSERT
);
1970 *slot
= new_reduction
;
1973 /* Callback for htab_traverse. Sets gimple_uid of reduc_phi stmts. */
1976 set_reduc_phi_uids (reduction_info
**slot
, void *data ATTRIBUTE_UNUSED
)
1978 struct reduction_info
*const red
= *slot
;
1979 gimple_set_uid (red
->reduc_phi
, red
->reduc_version
);
1983 /* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
1986 gather_scalar_reductions (loop_p loop
, reduction_info_table_type
*reduction_list
)
1988 gimple_phi_iterator gsi
;
1989 loop_vec_info simple_loop_info
;
1991 simple_loop_info
= vect_analyze_loop_form (loop
);
1993 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1995 gimple_phi phi
= gsi
.phi ();
1997 tree res
= PHI_RESULT (phi
);
2000 if (virtual_operand_p (res
))
2003 if (!simple_iv (loop
, loop
, res
, &iv
, true)
2004 && simple_loop_info
)
2006 gimple reduc_stmt
= vect_force_simple_reduction (simple_loop_info
,
2009 if (reduc_stmt
&& !double_reduc
)
2010 build_new_reduction (reduction_list
, reduc_stmt
, phi
);
2013 destroy_loop_vec_info (simple_loop_info
, true);
2015 /* As gimple_uid is used by the vectorizer in between vect_analyze_loop_form
2016 and destroy_loop_vec_info, we can set gimple_uid of reduc_phi stmts
2018 reduction_list
->traverse
<void *, set_reduc_phi_uids
> (NULL
);
2021 /* Try to initialize NITER for code generation part. */
2024 try_get_loop_niter (loop_p loop
, struct tree_niter_desc
*niter
)
2026 edge exit
= single_dom_exit (loop
);
2030 /* We need to know # of iterations, and there should be no uses of values
2031 defined inside loop outside of it, unless the values are invariants of
2033 if (!number_of_iterations_exit (loop
, exit
, niter
, false))
2035 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2036 fprintf (dump_file
, " FAILED: number of iterations not known\n");
2043 /* Try to initialize REDUCTION_LIST for code generation part.
2044 REDUCTION_LIST describes the reductions. */
2047 try_create_reduction_list (loop_p loop
,
2048 reduction_info_table_type
*reduction_list
)
2050 edge exit
= single_dom_exit (loop
);
2051 gimple_phi_iterator gsi
;
2055 gather_scalar_reductions (loop
, reduction_list
);
2058 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2060 gimple_phi phi
= gsi
.phi ();
2061 struct reduction_info
*red
;
2062 imm_use_iterator imm_iter
;
2063 use_operand_p use_p
;
2065 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2067 if (!virtual_operand_p (val
))
2069 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2071 fprintf (dump_file
, "phi is ");
2072 print_gimple_stmt (dump_file
, phi
, 0, 0);
2073 fprintf (dump_file
, "arg of phi to exit: value ");
2074 print_generic_expr (dump_file
, val
, 0);
2075 fprintf (dump_file
, " used outside loop\n");
2077 " checking if it a part of reduction pattern: \n");
2079 if (reduction_list
->elements () == 0)
2081 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2083 " FAILED: it is not a part of reduction.\n");
2087 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, val
)
2089 if (!gimple_debug_bind_p (USE_STMT (use_p
))
2090 && flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
2092 reduc_phi
= USE_STMT (use_p
);
2096 red
= reduction_phi (reduction_list
, reduc_phi
);
2099 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2101 " FAILED: it is not a part of reduction.\n");
2104 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2106 fprintf (dump_file
, "reduction phi is ");
2107 print_gimple_stmt (dump_file
, red
->reduc_phi
, 0, 0);
2108 fprintf (dump_file
, "reduction stmt is ");
2109 print_gimple_stmt (dump_file
, red
->reduc_stmt
, 0, 0);
2114 /* The iterations of the loop may communicate only through bivs whose
2115 iteration space can be distributed efficiently. */
2116 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2118 gimple_phi phi
= gsi
.phi ();
2119 tree def
= PHI_RESULT (phi
);
2122 if (!virtual_operand_p (def
) && !simple_iv (loop
, loop
, def
, &iv
, true))
2124 struct reduction_info
*red
;
2126 red
= reduction_phi (reduction_list
, phi
);
2129 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2131 " FAILED: scalar dependency between iterations\n");
2141 /* Detect parallel loops and generate parallel code using libgomp
2142 primitives. Returns true if some loop was parallelized, false
2146 parallelize_loops (void)
2148 unsigned n_threads
= flag_tree_parallelize_loops
;
2149 bool changed
= false;
2151 struct tree_niter_desc niter_desc
;
2152 struct obstack parloop_obstack
;
2153 HOST_WIDE_INT estimated
;
2154 source_location loop_loc
;
2156 /* Do not parallelize loops in the functions created by parallelization. */
2157 if (parallelized_function_p (cfun
->decl
))
2159 if (cfun
->has_nonlocal_label
)
2162 gcc_obstack_init (&parloop_obstack
);
2163 reduction_info_table_type
reduction_list (10);
2164 init_stmt_vec_info_vec ();
2166 FOR_EACH_LOOP (loop
, 0)
2168 reduction_list
.empty ();
2169 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2171 fprintf (dump_file
, "Trying loop %d as candidate\n",loop
->num
);
2173 fprintf (dump_file
, "loop %d is not innermost\n",loop
->num
);
2175 fprintf (dump_file
, "loop %d is innermost\n",loop
->num
);
2178 /* If we use autopar in graphite pass, we use its marked dependency
2179 checking results. */
2180 if (flag_loop_parallelize_all
&& !loop
->can_be_parallel
)
2182 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2183 fprintf (dump_file
, "loop is not parallel according to graphite\n");
2187 if (!single_dom_exit (loop
))
2190 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2191 fprintf (dump_file
, "loop is !single_dom_exit\n");
2196 if (/* And of course, the loop must be parallelizable. */
2197 !can_duplicate_loop_p (loop
)
2198 || loop_has_blocks_with_irreducible_flag (loop
)
2199 || (loop_preheader_edge (loop
)->src
->flags
& BB_IRREDUCIBLE_LOOP
)
2200 /* FIXME: the check for vector phi nodes could be removed. */
2201 || loop_has_vector_phi_nodes (loop
))
2204 estimated
= estimated_stmt_executions_int (loop
);
2205 if (estimated
== -1)
2206 estimated
= max_stmt_executions_int (loop
);
2207 /* FIXME: Bypass this check as graphite doesn't update the
2208 count and frequency correctly now. */
2209 if (!flag_loop_parallelize_all
2210 && ((estimated
!= -1
2211 && estimated
<= (HOST_WIDE_INT
) n_threads
* MIN_PER_THREAD
)
2212 /* Do not bother with loops in cold areas. */
2213 || optimize_loop_nest_for_size_p (loop
)))
2216 if (!try_get_loop_niter (loop
, &niter_desc
))
2219 if (!try_create_reduction_list (loop
, &reduction_list
))
2222 if (!flag_loop_parallelize_all
2223 && !loop_parallel_p (loop
, &parloop_obstack
))
2227 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2230 fprintf (dump_file
, "parallelizing outer loop %d\n",loop
->header
->index
);
2232 fprintf (dump_file
, "parallelizing inner loop %d\n",loop
->header
->index
);
2233 loop_loc
= find_loop_location (loop
);
2234 if (loop_loc
!= UNKNOWN_LOCATION
)
2235 fprintf (dump_file
, "\nloop at %s:%d: ",
2236 LOCATION_FILE (loop_loc
), LOCATION_LINE (loop_loc
));
2238 gen_parallel_loop (loop
, &reduction_list
,
2239 n_threads
, &niter_desc
);
2242 free_stmt_vec_info_vec ();
2243 obstack_free (&parloop_obstack
, NULL
);
2245 /* Parallelization will cause new function calls to be inserted through
2246 which local variables will escape. Reset the points-to solution
2249 pt_solution_reset (&cfun
->gimple_df
->escaped
);
2254 /* Parallelization. */
2258 const pass_data pass_data_parallelize_loops
=
2260 GIMPLE_PASS
, /* type */
2261 "parloops", /* name */
2262 OPTGROUP_LOOP
, /* optinfo_flags */
2263 TV_TREE_PARALLELIZE_LOOPS
, /* tv_id */
2264 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2265 0, /* properties_provided */
2266 0, /* properties_destroyed */
2267 0, /* todo_flags_start */
2268 0, /* todo_flags_finish */
2271 class pass_parallelize_loops
: public gimple_opt_pass
2274 pass_parallelize_loops (gcc::context
*ctxt
)
2275 : gimple_opt_pass (pass_data_parallelize_loops
, ctxt
)
2278 /* opt_pass methods: */
2279 virtual bool gate (function
*) { return flag_tree_parallelize_loops
> 1; }
2280 virtual unsigned int execute (function
*);
2282 }; // class pass_parallelize_loops
2285 pass_parallelize_loops::execute (function
*fun
)
2287 if (number_of_loops (fun
) <= 1)
2290 if (parallelize_loops ())
2291 return TODO_cleanup_cfg
| TODO_rebuild_alias
;
2298 make_pass_parallelize_loops (gcc::context
*ctxt
)
2300 return new pass_parallelize_loops (ctxt
);
2304 #include "gt-tree-parloops.h"