1 /* Loop autoparallelization.
2 Copyright (C) 2006-2016 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"
29 #include "tree-pass.h"
32 #include "gimple-pretty-print.h"
33 #include "fold-const.h"
35 #include "gimple-iterator.h"
36 #include "gimplify-me.h"
37 #include "gimple-walk.h"
38 #include "stor-layout.h"
39 #include "tree-nested.h"
41 #include "tree-ssa-loop-ivopts.h"
42 #include "tree-ssa-loop-manip.h"
43 #include "tree-ssa-loop-niter.h"
44 #include "tree-ssa-loop.h"
45 #include "tree-into-ssa.h"
47 #include "tree-scalar-evolution.h"
48 #include "langhooks.h"
49 #include "tree-vectorizer.h"
50 #include "tree-hasher.h"
51 #include "tree-parloops.h"
55 #include "params-enum.h"
56 #include "tree-ssa-alias.h"
58 #include "gomp-constants.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 gphi
*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 reduc_addr
; /* The address of the reduction variable for
200 openacc reductions. */
201 tree init
; /* reduction initialization value. */
202 gphi
*new_phi
; /* (helper field) Newly created phi node whose result
203 will be passed to the atomic operation. Represents
204 the local result each thread computed for the reduction
208 /* Reduction info hashtable helpers. */
210 struct reduction_hasher
: free_ptr_hash
<reduction_info
>
212 static inline hashval_t
hash (const reduction_info
*);
213 static inline bool equal (const reduction_info
*, const reduction_info
*);
216 /* Equality and hash functions for hashtab code. */
219 reduction_hasher::equal (const reduction_info
*a
, const reduction_info
*b
)
221 return (a
->reduc_phi
== b
->reduc_phi
);
225 reduction_hasher::hash (const reduction_info
*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 if (gimple_uid (phi
) == (unsigned int)-1
242 || gimple_uid (phi
) == 0)
245 tmpred
.reduc_phi
= phi
;
246 tmpred
.reduc_version
= gimple_uid (phi
);
247 red
= reduction_list
->find (&tmpred
);
248 gcc_assert (red
== NULL
|| red
->reduc_phi
== phi
);
253 /* Element of hashtable of names to copy. */
255 struct name_to_copy_elt
257 unsigned version
; /* The version of the name to copy. */
258 tree new_name
; /* The new name used in the copy. */
259 tree field
; /* The field of the structure used to pass the
263 /* Name copies hashtable helpers. */
265 struct name_to_copy_hasher
: free_ptr_hash
<name_to_copy_elt
>
267 static inline hashval_t
hash (const name_to_copy_elt
*);
268 static inline bool equal (const name_to_copy_elt
*, const name_to_copy_elt
*);
271 /* Equality and hash functions for hashtab code. */
274 name_to_copy_hasher::equal (const name_to_copy_elt
*a
, const name_to_copy_elt
*b
)
276 return a
->version
== b
->version
;
280 name_to_copy_hasher::hash (const name_to_copy_elt
*a
)
282 return (hashval_t
) a
->version
;
285 typedef hash_table
<name_to_copy_hasher
> name_to_copy_table_type
;
287 /* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
288 matrix. Rather than use floats, we simply keep a single DENOMINATOR that
289 represents the denominator for every element in the matrix. */
290 typedef struct lambda_trans_matrix_s
292 lambda_matrix matrix
;
296 } *lambda_trans_matrix
;
297 #define LTM_MATRIX(T) ((T)->matrix)
298 #define LTM_ROWSIZE(T) ((T)->rowsize)
299 #define LTM_COLSIZE(T) ((T)->colsize)
300 #define LTM_DENOMINATOR(T) ((T)->denominator)
302 /* Allocate a new transformation matrix. */
304 static lambda_trans_matrix
305 lambda_trans_matrix_new (int colsize
, int rowsize
,
306 struct obstack
* lambda_obstack
)
308 lambda_trans_matrix ret
;
310 ret
= (lambda_trans_matrix
)
311 obstack_alloc (lambda_obstack
, sizeof (struct lambda_trans_matrix_s
));
312 LTM_MATRIX (ret
) = lambda_matrix_new (rowsize
, colsize
, lambda_obstack
);
313 LTM_ROWSIZE (ret
) = rowsize
;
314 LTM_COLSIZE (ret
) = colsize
;
315 LTM_DENOMINATOR (ret
) = 1;
319 /* Multiply a vector VEC by a matrix MAT.
320 MAT is an M*N matrix, and VEC is a vector with length N. The result
321 is stored in DEST which must be a vector of length M. */
324 lambda_matrix_vector_mult (lambda_matrix matrix
, int m
, int n
,
325 lambda_vector vec
, lambda_vector dest
)
329 lambda_vector_clear (dest
, m
);
330 for (i
= 0; i
< m
; i
++)
331 for (j
= 0; j
< n
; j
++)
332 dest
[i
] += matrix
[i
][j
] * vec
[j
];
335 /* Return true if TRANS is a legal transformation matrix that respects
336 the dependence vectors in DISTS and DIRS. The conservative answer
339 "Wolfe proves that a unimodular transformation represented by the
340 matrix T is legal when applied to a loop nest with a set of
341 lexicographically non-negative distance vectors RDG if and only if
342 for each vector d in RDG, (T.d >= 0) is lexicographically positive.
343 i.e.: if and only if it transforms the lexicographically positive
344 distance vectors to lexicographically positive vectors. Note that
345 a unimodular matrix must transform the zero vector (and only it) to
346 the zero vector." S.Muchnick. */
349 lambda_transform_legal_p (lambda_trans_matrix trans
,
351 vec
<ddr_p
> dependence_relations
)
354 lambda_vector distres
;
355 struct data_dependence_relation
*ddr
;
357 gcc_assert (LTM_COLSIZE (trans
) == nb_loops
358 && LTM_ROWSIZE (trans
) == nb_loops
);
360 /* When there are no dependences, the transformation is correct. */
361 if (dependence_relations
.length () == 0)
364 ddr
= dependence_relations
[0];
368 /* When there is an unknown relation in the dependence_relations, we
369 know that it is no worth looking at this loop nest: give up. */
370 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
373 distres
= lambda_vector_new (nb_loops
);
375 /* For each distance vector in the dependence graph. */
376 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
378 /* Don't care about relations for which we know that there is no
379 dependence, nor about read-read (aka. output-dependences):
380 these data accesses can happen in any order. */
381 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
382 || (DR_IS_READ (DDR_A (ddr
)) && DR_IS_READ (DDR_B (ddr
))))
385 /* Conservatively answer: "this transformation is not valid". */
386 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
389 /* If the dependence could not be captured by a distance vector,
390 conservatively answer that the transform is not valid. */
391 if (DDR_NUM_DIST_VECTS (ddr
) == 0)
394 /* Compute trans.dist_vect */
395 for (j
= 0; j
< DDR_NUM_DIST_VECTS (ddr
); j
++)
397 lambda_matrix_vector_mult (LTM_MATRIX (trans
), nb_loops
, nb_loops
,
398 DDR_DIST_VECT (ddr
, j
), distres
);
400 if (!lambda_vector_lexico_pos (distres
, nb_loops
))
407 /* Data dependency analysis. Returns true if the iterations of LOOP
408 are independent on each other (that is, if we can execute them
412 loop_parallel_p (struct loop
*loop
, struct obstack
* parloop_obstack
)
414 vec
<ddr_p
> dependence_relations
;
415 vec
<data_reference_p
> datarefs
;
416 lambda_trans_matrix trans
;
419 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
421 fprintf (dump_file
, "Considering loop %d\n", loop
->num
);
423 fprintf (dump_file
, "loop is innermost\n");
425 fprintf (dump_file
, "loop NOT innermost\n");
428 /* Check for problems with dependences. If the loop can be reversed,
429 the iterations are independent. */
430 auto_vec
<loop_p
, 3> loop_nest
;
431 datarefs
.create (10);
432 dependence_relations
.create (100);
433 if (! compute_data_dependences_for_loop (loop
, true, &loop_nest
, &datarefs
,
434 &dependence_relations
))
436 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
437 fprintf (dump_file
, " FAILED: cannot analyze data dependencies\n");
441 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
442 dump_data_dependence_relations (dump_file
, dependence_relations
);
444 trans
= lambda_trans_matrix_new (1, 1, parloop_obstack
);
445 LTM_MATRIX (trans
)[0][0] = -1;
447 if (lambda_transform_legal_p (trans
, 1, dependence_relations
))
450 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
451 fprintf (dump_file
, " SUCCESS: may be parallelized\n");
453 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
455 " FAILED: data dependencies exist across iterations\n");
458 free_dependence_relations (dependence_relations
);
459 free_data_refs (datarefs
);
464 /* Return true when LOOP contains basic blocks marked with the
465 BB_IRREDUCIBLE_LOOP flag. */
468 loop_has_blocks_with_irreducible_flag (struct loop
*loop
)
471 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
474 for (i
= 0; i
< loop
->num_nodes
; i
++)
475 if (bbs
[i
]->flags
& BB_IRREDUCIBLE_LOOP
)
484 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
485 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
486 to their addresses that can be reused. The address of OBJ is known to
487 be invariant in the whole function. Other needed statements are placed
491 take_address_of (tree obj
, tree type
, edge entry
,
492 int_tree_htab_type
*decl_address
, gimple_stmt_iterator
*gsi
)
495 tree
*var_p
, name
, addr
;
499 /* Since the address of OBJ is invariant, the trees may be shared.
500 Avoid rewriting unrelated parts of the code. */
501 obj
= unshare_expr (obj
);
503 handled_component_p (*var_p
);
504 var_p
= &TREE_OPERAND (*var_p
, 0))
507 /* Canonicalize the access to base on a MEM_REF. */
509 *var_p
= build_simple_mem_ref (build_fold_addr_expr (*var_p
));
511 /* Assign a canonical SSA name to the address of the base decl used
512 in the address and share it for all accesses and addresses based
514 uid
= DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p
, 0), 0));
517 int_tree_map
*slot
= decl_address
->find_slot (elt
, INSERT
);
522 addr
= TREE_OPERAND (*var_p
, 0);
524 = get_name (TREE_OPERAND (TREE_OPERAND (*var_p
, 0), 0));
526 name
= make_temp_ssa_name (TREE_TYPE (addr
), NULL
, obj_name
);
528 name
= make_ssa_name (TREE_TYPE (addr
));
529 stmt
= gimple_build_assign (name
, addr
);
530 gsi_insert_on_edge_immediate (entry
, stmt
);
538 /* Express the address in terms of the canonical SSA name. */
539 TREE_OPERAND (*var_p
, 0) = name
;
541 return build_fold_addr_expr_with_type (obj
, type
);
543 name
= force_gimple_operand (build_addr (obj
),
544 &stmts
, true, NULL_TREE
);
545 if (!gimple_seq_empty_p (stmts
))
546 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
548 if (!useless_type_conversion_p (type
, TREE_TYPE (name
)))
550 name
= force_gimple_operand (fold_convert (type
, name
), &stmts
, true,
552 if (!gimple_seq_empty_p (stmts
))
553 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
560 reduc_stmt_res (gimple
*stmt
)
562 return (gimple_code (stmt
) == GIMPLE_PHI
563 ? gimple_phi_result (stmt
)
564 : gimple_assign_lhs (stmt
));
567 /* Callback for htab_traverse. Create the initialization statement
568 for reduction described in SLOT, and place it at the preheader of
569 the loop described in DATA. */
572 initialize_reductions (reduction_info
**slot
, struct loop
*loop
)
578 struct reduction_info
*const reduc
= *slot
;
580 /* Create initialization in preheader:
581 reduction_variable = initialization value of reduction. */
583 /* In the phi node at the header, replace the argument coming
584 from the preheader with the reduction initialization value. */
586 /* Initialize the reduction. */
587 type
= TREE_TYPE (PHI_RESULT (reduc
->reduc_phi
));
588 init
= omp_reduction_init_op (gimple_location (reduc
->reduc_stmt
),
589 reduc
->reduction_code
, type
);
592 /* Replace the argument representing the initialization value
593 with the initialization value for the reduction (neutral
594 element for the particular operation, e.g. 0 for PLUS_EXPR,
595 1 for MULT_EXPR, etc).
596 Keep the old value in a new variable "reduction_initial",
597 that will be taken in consideration after the parallel
598 computing is done. */
600 e
= loop_preheader_edge (loop
);
601 arg
= PHI_ARG_DEF_FROM_EDGE (reduc
->reduc_phi
, e
);
602 /* Create new variable to hold the initial value. */
604 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
605 (reduc
->reduc_phi
, loop_preheader_edge (loop
)), init
);
606 reduc
->initial_value
= arg
;
612 struct walk_stmt_info info
;
614 int_tree_htab_type
*decl_address
;
615 gimple_stmt_iterator
*gsi
;
620 /* Eliminates references to local variables in *TP out of the single
621 entry single exit region starting at DTA->ENTRY.
622 DECL_ADDRESS contains addresses of the references that had their
623 address taken already. If the expression is changed, CHANGED is
624 set to true. Callback for walk_tree. */
627 eliminate_local_variables_1 (tree
*tp
, int *walk_subtrees
, void *data
)
629 struct elv_data
*const dta
= (struct elv_data
*) data
;
630 tree t
= *tp
, var
, addr
, addr_type
, type
, obj
;
636 if (!SSA_VAR_P (t
) || DECL_EXTERNAL (t
))
639 type
= TREE_TYPE (t
);
640 addr_type
= build_pointer_type (type
);
641 addr
= take_address_of (t
, addr_type
, dta
->entry
, dta
->decl_address
,
643 if (dta
->gsi
== NULL
&& addr
== NULL_TREE
)
649 *tp
= build_simple_mem_ref (addr
);
655 if (TREE_CODE (t
) == ADDR_EXPR
)
657 /* ADDR_EXPR may appear in two contexts:
658 -- as a gimple operand, when the address taken is a function invariant
659 -- as gimple rhs, when the resulting address in not a function
661 We do not need to do anything special in the latter case (the base of
662 the memory reference whose address is taken may be replaced in the
663 DECL_P case). The former case is more complicated, as we need to
664 ensure that the new address is still a gimple operand. Thus, it
665 is not sufficient to replace just the base of the memory reference --
666 we need to move the whole computation of the address out of the
668 if (!is_gimple_val (t
))
672 obj
= TREE_OPERAND (t
, 0);
673 var
= get_base_address (obj
);
674 if (!var
|| !SSA_VAR_P (var
) || DECL_EXTERNAL (var
))
677 addr_type
= TREE_TYPE (t
);
678 addr
= take_address_of (obj
, addr_type
, dta
->entry
, dta
->decl_address
,
680 if (dta
->gsi
== NULL
&& addr
== NULL_TREE
)
697 /* Moves the references to local variables in STMT at *GSI out of the single
698 entry single exit region starting at ENTRY. DECL_ADDRESS contains
699 addresses of the references that had their address taken
703 eliminate_local_variables_stmt (edge entry
, gimple_stmt_iterator
*gsi
,
704 int_tree_htab_type
*decl_address
)
707 gimple
*stmt
= gsi_stmt (*gsi
);
709 memset (&dta
.info
, '\0', sizeof (dta
.info
));
711 dta
.decl_address
= decl_address
;
715 if (gimple_debug_bind_p (stmt
))
718 walk_tree (gimple_debug_bind_get_value_ptr (stmt
),
719 eliminate_local_variables_1
, &dta
.info
, NULL
);
722 gimple_debug_bind_reset_value (stmt
);
726 else if (gimple_clobber_p (stmt
))
728 stmt
= gimple_build_nop ();
729 gsi_replace (gsi
, stmt
, false);
735 walk_gimple_op (stmt
, eliminate_local_variables_1
, &dta
.info
);
742 /* Eliminates the references to local variables from the single entry
743 single exit region between the ENTRY and EXIT edges.
746 1) Taking address of a local variable -- these are moved out of the
747 region (and temporary variable is created to hold the address if
750 2) Dereferencing a local variable -- these are replaced with indirect
754 eliminate_local_variables (edge entry
, edge exit
)
757 auto_vec
<basic_block
, 3> body
;
759 gimple_stmt_iterator gsi
;
760 bool has_debug_stmt
= false;
761 int_tree_htab_type
decl_address (10);
762 basic_block entry_bb
= entry
->src
;
763 basic_block exit_bb
= exit
->dest
;
765 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
767 FOR_EACH_VEC_ELT (body
, i
, bb
)
768 if (bb
!= entry_bb
&& bb
!= exit_bb
)
769 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
770 if (is_gimple_debug (gsi_stmt (gsi
)))
772 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
773 has_debug_stmt
= true;
776 eliminate_local_variables_stmt (entry
, &gsi
, &decl_address
);
779 FOR_EACH_VEC_ELT (body
, i
, bb
)
780 if (bb
!= entry_bb
&& bb
!= exit_bb
)
781 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
782 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
783 eliminate_local_variables_stmt (entry
, &gsi
, &decl_address
);
786 /* Returns true if expression EXPR is not defined between ENTRY and
787 EXIT, i.e. if all its operands are defined outside of the region. */
790 expr_invariant_in_region_p (edge entry
, edge exit
, tree expr
)
792 basic_block entry_bb
= entry
->src
;
793 basic_block exit_bb
= exit
->dest
;
796 if (is_gimple_min_invariant (expr
))
799 if (TREE_CODE (expr
) == SSA_NAME
)
801 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
803 && dominated_by_p (CDI_DOMINATORS
, def_bb
, entry_bb
)
804 && !dominated_by_p (CDI_DOMINATORS
, def_bb
, exit_bb
))
813 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
814 The copies are stored to NAME_COPIES, if NAME was already duplicated,
815 its duplicate stored in NAME_COPIES is returned.
817 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
818 duplicated, storing the copies in DECL_COPIES. */
821 separate_decls_in_region_name (tree name
, name_to_copy_table_type
*name_copies
,
822 int_tree_htab_type
*decl_copies
,
825 tree copy
, var
, var_copy
;
826 unsigned idx
, uid
, nuid
;
827 struct int_tree_map ielt
;
828 struct name_to_copy_elt elt
, *nelt
;
829 name_to_copy_elt
**slot
;
832 if (TREE_CODE (name
) != SSA_NAME
)
835 idx
= SSA_NAME_VERSION (name
);
837 slot
= name_copies
->find_slot_with_hash (&elt
, idx
,
838 copy_name_p
? INSERT
: NO_INSERT
);
840 return (*slot
)->new_name
;
844 copy
= duplicate_ssa_name (name
, NULL
);
845 nelt
= XNEW (struct name_to_copy_elt
);
847 nelt
->new_name
= copy
;
848 nelt
->field
= NULL_TREE
;
857 var
= SSA_NAME_VAR (name
);
861 uid
= DECL_UID (var
);
863 dslot
= decl_copies
->find_slot_with_hash (ielt
, uid
, INSERT
);
866 var_copy
= create_tmp_var (TREE_TYPE (var
), get_name (var
));
867 DECL_GIMPLE_REG_P (var_copy
) = DECL_GIMPLE_REG_P (var
);
869 dslot
->to
= var_copy
;
871 /* Ensure that when we meet this decl next time, we won't duplicate
873 nuid
= DECL_UID (var_copy
);
875 dslot
= decl_copies
->find_slot_with_hash (ielt
, nuid
, INSERT
);
876 gcc_assert (!dslot
->to
);
878 dslot
->to
= var_copy
;
881 var_copy
= dslot
->to
;
883 replace_ssa_name_symbol (copy
, var_copy
);
887 /* Finds the ssa names used in STMT that are defined outside the
888 region between ENTRY and EXIT and replaces such ssa names with
889 their duplicates. The duplicates are stored to NAME_COPIES. Base
890 decls of all ssa names used in STMT (including those defined in
891 LOOP) are replaced with the new temporary variables; the
892 replacement decls are stored in DECL_COPIES. */
895 separate_decls_in_region_stmt (edge entry
, edge exit
, gimple
*stmt
,
896 name_to_copy_table_type
*name_copies
,
897 int_tree_htab_type
*decl_copies
)
905 FOR_EACH_PHI_OR_STMT_DEF (def
, stmt
, oi
, SSA_OP_DEF
)
907 name
= DEF_FROM_PTR (def
);
908 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
909 copy
= separate_decls_in_region_name (name
, name_copies
, decl_copies
,
911 gcc_assert (copy
== name
);
914 FOR_EACH_PHI_OR_STMT_USE (use
, stmt
, oi
, SSA_OP_USE
)
916 name
= USE_FROM_PTR (use
);
917 if (TREE_CODE (name
) != SSA_NAME
)
920 copy_name_p
= expr_invariant_in_region_p (entry
, exit
, name
);
921 copy
= separate_decls_in_region_name (name
, name_copies
, decl_copies
,
927 /* Finds the ssa names used in STMT that are defined outside the
928 region between ENTRY and EXIT and replaces such ssa names with
929 their duplicates. The duplicates are stored to NAME_COPIES. Base
930 decls of all ssa names used in STMT (including those defined in
931 LOOP) are replaced with the new temporary variables; the
932 replacement decls are stored in DECL_COPIES. */
935 separate_decls_in_region_debug (gimple
*stmt
,
936 name_to_copy_table_type
*name_copies
,
937 int_tree_htab_type
*decl_copies
)
942 struct int_tree_map ielt
;
943 struct name_to_copy_elt elt
;
944 name_to_copy_elt
**slot
;
947 if (gimple_debug_bind_p (stmt
))
948 var
= gimple_debug_bind_get_var (stmt
);
949 else if (gimple_debug_source_bind_p (stmt
))
950 var
= gimple_debug_source_bind_get_var (stmt
);
953 if (TREE_CODE (var
) == DEBUG_EXPR_DECL
|| TREE_CODE (var
) == LABEL_DECL
)
955 gcc_assert (DECL_P (var
) && SSA_VAR_P (var
));
956 ielt
.uid
= DECL_UID (var
);
957 dslot
= decl_copies
->find_slot_with_hash (ielt
, ielt
.uid
, NO_INSERT
);
960 if (gimple_debug_bind_p (stmt
))
961 gimple_debug_bind_set_var (stmt
, dslot
->to
);
962 else if (gimple_debug_source_bind_p (stmt
))
963 gimple_debug_source_bind_set_var (stmt
, dslot
->to
);
965 FOR_EACH_PHI_OR_STMT_USE (use
, stmt
, oi
, SSA_OP_USE
)
967 name
= USE_FROM_PTR (use
);
968 if (TREE_CODE (name
) != SSA_NAME
)
971 elt
.version
= SSA_NAME_VERSION (name
);
972 slot
= name_copies
->find_slot_with_hash (&elt
, elt
.version
, NO_INSERT
);
975 gimple_debug_bind_reset_value (stmt
);
980 SET_USE (use
, (*slot
)->new_name
);
986 /* Callback for htab_traverse. Adds a field corresponding to the reduction
987 specified in SLOT. The type is passed in DATA. */
990 add_field_for_reduction (reduction_info
**slot
, tree type
)
993 struct reduction_info
*const red
= *slot
;
994 tree var
= reduc_stmt_res (red
->reduc_stmt
);
995 tree field
= build_decl (gimple_location (red
->reduc_stmt
), FIELD_DECL
,
996 SSA_NAME_IDENTIFIER (var
), TREE_TYPE (var
));
998 insert_field_into_struct (type
, field
);
1005 /* Callback for htab_traverse. Adds a field corresponding to a ssa name
1006 described in SLOT. The type is passed in DATA. */
1009 add_field_for_name (name_to_copy_elt
**slot
, tree type
)
1011 struct name_to_copy_elt
*const elt
= *slot
;
1012 tree name
= ssa_name (elt
->version
);
1013 tree field
= build_decl (UNKNOWN_LOCATION
,
1014 FIELD_DECL
, SSA_NAME_IDENTIFIER (name
),
1017 insert_field_into_struct (type
, field
);
1023 /* Callback for htab_traverse. A local result is the intermediate result
1024 computed by a single
1025 thread, or the initial value in case no iteration was executed.
1026 This function creates a phi node reflecting these values.
1027 The phi's result will be stored in NEW_PHI field of the
1028 reduction's data structure. */
1031 create_phi_for_local_result (reduction_info
**slot
, struct loop
*loop
)
1033 struct reduction_info
*const reduc
= *slot
;
1036 basic_block store_bb
, continue_bb
;
1038 source_location locus
;
1040 /* STORE_BB is the block where the phi
1041 should be stored. It is the destination of the loop exit.
1042 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
1043 continue_bb
= single_pred (loop
->latch
);
1044 store_bb
= FALLTHRU_EDGE (continue_bb
)->dest
;
1046 /* STORE_BB has two predecessors. One coming from the loop
1047 (the reduction's result is computed at the loop),
1048 and another coming from a block preceding the loop,
1050 are executed (the initial value should be taken). */
1051 if (EDGE_PRED (store_bb
, 0) == FALLTHRU_EDGE (continue_bb
))
1052 e
= EDGE_PRED (store_bb
, 1);
1054 e
= EDGE_PRED (store_bb
, 0);
1055 tree lhs
= reduc_stmt_res (reduc
->reduc_stmt
);
1056 local_res
= copy_ssa_name (lhs
);
1057 locus
= gimple_location (reduc
->reduc_stmt
);
1058 new_phi
= create_phi_node (local_res
, store_bb
);
1059 add_phi_arg (new_phi
, reduc
->init
, e
, locus
);
1060 add_phi_arg (new_phi
, lhs
, FALLTHRU_EDGE (continue_bb
), locus
);
1061 reduc
->new_phi
= new_phi
;
1071 basic_block store_bb
;
1072 basic_block load_bb
;
1075 /* Callback for htab_traverse. Create an atomic instruction for the
1076 reduction described in SLOT.
1077 DATA annotates the place in memory the atomic operation relates to,
1078 and the basic block it needs to be generated in. */
1081 create_call_for_reduction_1 (reduction_info
**slot
, struct clsn_data
*clsn_data
)
1083 struct reduction_info
*const reduc
= *slot
;
1084 gimple_stmt_iterator gsi
;
1085 tree type
= TREE_TYPE (PHI_RESULT (reduc
->reduc_phi
));
1090 tree t
, addr
, ref
, x
;
1091 tree tmp_load
, name
;
1094 if (reduc
->reduc_addr
== NULL_TREE
)
1096 load_struct
= build_simple_mem_ref (clsn_data
->load
);
1097 t
= build3 (COMPONENT_REF
, type
, load_struct
, reduc
->field
, NULL_TREE
);
1099 addr
= build_addr (t
);
1103 /* Set the address for the atomic store. */
1104 addr
= reduc
->reduc_addr
;
1106 /* Remove the non-atomic store '*addr = sum'. */
1107 tree res
= PHI_RESULT (reduc
->keep_res
);
1108 use_operand_p use_p
;
1110 bool single_use_p
= single_imm_use (res
, &use_p
, &stmt
);
1111 gcc_assert (single_use_p
);
1112 replace_uses_by (gimple_vdef (stmt
),
1113 gimple_vuse (stmt
));
1114 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
1115 gsi_remove (&gsi
, true);
1118 /* Create phi node. */
1119 bb
= clsn_data
->load_bb
;
1121 gsi
= gsi_last_bb (bb
);
1122 e
= split_block (bb
, gsi_stmt (gsi
));
1125 tmp_load
= create_tmp_var (TREE_TYPE (TREE_TYPE (addr
)));
1126 tmp_load
= make_ssa_name (tmp_load
);
1127 load
= gimple_build_omp_atomic_load (tmp_load
, addr
);
1128 SSA_NAME_DEF_STMT (tmp_load
) = load
;
1129 gsi
= gsi_start_bb (new_bb
);
1130 gsi_insert_after (&gsi
, load
, GSI_NEW_STMT
);
1132 e
= split_block (new_bb
, load
);
1134 gsi
= gsi_start_bb (new_bb
);
1136 x
= fold_build2 (reduc
->reduction_code
,
1137 TREE_TYPE (PHI_RESULT (reduc
->new_phi
)), ref
,
1138 PHI_RESULT (reduc
->new_phi
));
1140 name
= force_gimple_operand_gsi (&gsi
, x
, true, NULL_TREE
, true,
1141 GSI_CONTINUE_LINKING
);
1143 gsi_insert_after (&gsi
, gimple_build_omp_atomic_store (name
), GSI_NEW_STMT
);
1147 /* Create the atomic operation at the join point of the threads.
1148 REDUCTION_LIST describes the reductions in the LOOP.
1149 LD_ST_DATA describes the shared data structure where
1150 shared data is stored in and loaded from. */
1152 create_call_for_reduction (struct loop
*loop
,
1153 reduction_info_table_type
*reduction_list
,
1154 struct clsn_data
*ld_st_data
)
1156 reduction_list
->traverse
<struct loop
*, create_phi_for_local_result
> (loop
);
1157 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
1158 basic_block continue_bb
= single_pred (loop
->latch
);
1159 ld_st_data
->load_bb
= FALLTHRU_EDGE (continue_bb
)->dest
;
1161 ->traverse
<struct clsn_data
*, create_call_for_reduction_1
> (ld_st_data
);
1164 /* Callback for htab_traverse. Loads the final reduction value at the
1165 join point of all threads, and inserts it in the right place. */
1168 create_loads_for_reductions (reduction_info
**slot
, struct clsn_data
*clsn_data
)
1170 struct reduction_info
*const red
= *slot
;
1172 gimple_stmt_iterator gsi
;
1173 tree type
= TREE_TYPE (reduc_stmt_res (red
->reduc_stmt
));
1178 /* If there's no exit phi, the result of the reduction is unused. */
1179 if (red
->keep_res
== NULL
)
1182 gsi
= gsi_after_labels (clsn_data
->load_bb
);
1183 load_struct
= build_simple_mem_ref (clsn_data
->load
);
1184 load_struct
= build3 (COMPONENT_REF
, type
, load_struct
, red
->field
,
1188 name
= PHI_RESULT (red
->keep_res
);
1189 stmt
= gimple_build_assign (name
, x
);
1191 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1193 for (gsi
= gsi_start_phis (gimple_bb (red
->keep_res
));
1194 !gsi_end_p (gsi
); gsi_next (&gsi
))
1195 if (gsi_stmt (gsi
) == red
->keep_res
)
1197 remove_phi_node (&gsi
, false);
1203 /* Load the reduction result that was stored in LD_ST_DATA.
1204 REDUCTION_LIST describes the list of reductions that the
1205 loads should be generated for. */
1207 create_final_loads_for_reduction (reduction_info_table_type
*reduction_list
,
1208 struct clsn_data
*ld_st_data
)
1210 gimple_stmt_iterator gsi
;
1214 gsi
= gsi_after_labels (ld_st_data
->load_bb
);
1215 t
= build_fold_addr_expr (ld_st_data
->store
);
1216 stmt
= gimple_build_assign (ld_st_data
->load
, t
);
1218 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1221 ->traverse
<struct clsn_data
*, create_loads_for_reductions
> (ld_st_data
);
1225 /* Callback for htab_traverse. Store the neutral value for the
1226 particular reduction's operation, e.g. 0 for PLUS_EXPR,
1227 1 for MULT_EXPR, etc. into the reduction field.
1228 The reduction is specified in SLOT. The store information is
1232 create_stores_for_reduction (reduction_info
**slot
, struct clsn_data
*clsn_data
)
1234 struct reduction_info
*const red
= *slot
;
1237 gimple_stmt_iterator gsi
;
1238 tree type
= TREE_TYPE (reduc_stmt_res (red
->reduc_stmt
));
1240 gsi
= gsi_last_bb (clsn_data
->store_bb
);
1241 t
= build3 (COMPONENT_REF
, type
, clsn_data
->store
, red
->field
, NULL_TREE
);
1242 stmt
= gimple_build_assign (t
, red
->initial_value
);
1243 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1248 /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
1249 store to a field of STORE in STORE_BB for the ssa name and its duplicate
1250 specified in SLOT. */
1253 create_loads_and_stores_for_name (name_to_copy_elt
**slot
,
1254 struct clsn_data
*clsn_data
)
1256 struct name_to_copy_elt
*const elt
= *slot
;
1259 gimple_stmt_iterator gsi
;
1260 tree type
= TREE_TYPE (elt
->new_name
);
1263 gsi
= gsi_last_bb (clsn_data
->store_bb
);
1264 t
= build3 (COMPONENT_REF
, type
, clsn_data
->store
, elt
->field
, NULL_TREE
);
1265 stmt
= gimple_build_assign (t
, ssa_name (elt
->version
));
1266 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1268 gsi
= gsi_last_bb (clsn_data
->load_bb
);
1269 load_struct
= build_simple_mem_ref (clsn_data
->load
);
1270 t
= build3 (COMPONENT_REF
, type
, load_struct
, elt
->field
, NULL_TREE
);
1271 stmt
= gimple_build_assign (elt
->new_name
, t
);
1272 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1277 /* Moves all the variables used in LOOP and defined outside of it (including
1278 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1279 name) to a structure created for this purpose. The code
1287 is transformed this way:
1302 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1303 pointer `new' is intentionally not initialized (the loop will be split to a
1304 separate function later, and `new' will be initialized from its arguments).
1305 LD_ST_DATA holds information about the shared data structure used to pass
1306 information among the threads. It is initialized here, and
1307 gen_parallel_loop will pass it to create_call_for_reduction that
1308 needs this information. REDUCTION_LIST describes the reductions
1312 separate_decls_in_region (edge entry
, edge exit
,
1313 reduction_info_table_type
*reduction_list
,
1314 tree
*arg_struct
, tree
*new_arg_struct
,
1315 struct clsn_data
*ld_st_data
)
1318 basic_block bb1
= split_edge (entry
);
1319 basic_block bb0
= single_pred (bb1
);
1320 name_to_copy_table_type
name_copies (10);
1321 int_tree_htab_type
decl_copies (10);
1323 tree type
, type_name
, nvar
;
1324 gimple_stmt_iterator gsi
;
1325 struct clsn_data clsn_data
;
1326 auto_vec
<basic_block
, 3> body
;
1328 basic_block entry_bb
= bb1
;
1329 basic_block exit_bb
= exit
->dest
;
1330 bool has_debug_stmt
= false;
1332 entry
= single_succ_edge (entry_bb
);
1333 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
1335 FOR_EACH_VEC_ELT (body
, i
, bb
)
1337 if (bb
!= entry_bb
&& bb
!= exit_bb
)
1339 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1340 separate_decls_in_region_stmt (entry
, exit
, gsi_stmt (gsi
),
1341 &name_copies
, &decl_copies
);
1343 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1345 gimple
*stmt
= gsi_stmt (gsi
);
1347 if (is_gimple_debug (stmt
))
1348 has_debug_stmt
= true;
1350 separate_decls_in_region_stmt (entry
, exit
, stmt
,
1351 &name_copies
, &decl_copies
);
1356 /* Now process debug bind stmts. We must not create decls while
1357 processing debug stmts, so we defer their processing so as to
1358 make sure we will have debug info for as many variables as
1359 possible (all of those that were dealt with in the loop above),
1360 and discard those for which we know there's nothing we can
1363 FOR_EACH_VEC_ELT (body
, i
, bb
)
1364 if (bb
!= entry_bb
&& bb
!= exit_bb
)
1366 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
1368 gimple
*stmt
= gsi_stmt (gsi
);
1370 if (is_gimple_debug (stmt
))
1372 if (separate_decls_in_region_debug (stmt
, &name_copies
,
1375 gsi_remove (&gsi
, true);
1384 if (name_copies
.elements () == 0 && reduction_list
->elements () == 0)
1386 /* It may happen that there is nothing to copy (if there are only
1387 loop carried and external variables in the loop). */
1389 *new_arg_struct
= NULL
;
1393 /* Create the type for the structure to store the ssa names to. */
1394 type
= lang_hooks
.types
.make_type (RECORD_TYPE
);
1395 type_name
= build_decl (UNKNOWN_LOCATION
,
1396 TYPE_DECL
, create_tmp_var_name (".paral_data"),
1398 TYPE_NAME (type
) = type_name
;
1400 name_copies
.traverse
<tree
, add_field_for_name
> (type
);
1401 if (reduction_list
&& reduction_list
->elements () > 0)
1403 /* Create the fields for reductions. */
1404 reduction_list
->traverse
<tree
, add_field_for_reduction
> (type
);
1408 /* Create the loads and stores. */
1409 *arg_struct
= create_tmp_var (type
, ".paral_data_store");
1410 nvar
= create_tmp_var (build_pointer_type (type
), ".paral_data_load");
1411 *new_arg_struct
= make_ssa_name (nvar
);
1413 ld_st_data
->store
= *arg_struct
;
1414 ld_st_data
->load
= *new_arg_struct
;
1415 ld_st_data
->store_bb
= bb0
;
1416 ld_st_data
->load_bb
= bb1
;
1419 .traverse
<struct clsn_data
*, create_loads_and_stores_for_name
>
1422 /* Load the calculation from memory (after the join of the threads). */
1424 if (reduction_list
&& reduction_list
->elements () > 0)
1427 ->traverse
<struct clsn_data
*, create_stores_for_reduction
>
1429 clsn_data
.load
= make_ssa_name (nvar
);
1430 clsn_data
.load_bb
= exit
->dest
;
1431 clsn_data
.store
= ld_st_data
->store
;
1432 create_final_loads_for_reduction (reduction_list
, &clsn_data
);
1437 /* Returns true if FN was created to run in parallel. */
1440 parallelized_function_p (tree fndecl
)
1442 cgraph_node
*node
= cgraph_node::get (fndecl
);
1443 gcc_assert (node
!= NULL
);
1444 return node
->parallelized_function
;
1447 /* Creates and returns an empty function that will receive the body of
1448 a parallelized loop. */
1451 create_loop_fn (location_t loc
)
1455 tree decl
, type
, name
, t
;
1456 struct function
*act_cfun
= cfun
;
1457 static unsigned loopfn_num
;
1459 loc
= LOCATION_LOCUS (loc
);
1460 snprintf (buf
, 100, "%s.$loopfn", current_function_name ());
1461 ASM_FORMAT_PRIVATE_NAME (tname
, buf
, loopfn_num
++);
1462 clean_symbol_name (tname
);
1463 name
= get_identifier (tname
);
1464 type
= build_function_type_list (void_type_node
, ptr_type_node
, NULL_TREE
);
1466 decl
= build_decl (loc
, FUNCTION_DECL
, name
, type
);
1467 TREE_STATIC (decl
) = 1;
1468 TREE_USED (decl
) = 1;
1469 DECL_ARTIFICIAL (decl
) = 1;
1470 DECL_IGNORED_P (decl
) = 0;
1471 TREE_PUBLIC (decl
) = 0;
1472 DECL_UNINLINABLE (decl
) = 1;
1473 DECL_EXTERNAL (decl
) = 0;
1474 DECL_CONTEXT (decl
) = NULL_TREE
;
1475 DECL_INITIAL (decl
) = make_node (BLOCK
);
1477 t
= build_decl (loc
, RESULT_DECL
, NULL_TREE
, void_type_node
);
1478 DECL_ARTIFICIAL (t
) = 1;
1479 DECL_IGNORED_P (t
) = 1;
1480 DECL_RESULT (decl
) = t
;
1482 t
= build_decl (loc
, PARM_DECL
, get_identifier (".paral_data_param"),
1484 DECL_ARTIFICIAL (t
) = 1;
1485 DECL_ARG_TYPE (t
) = ptr_type_node
;
1486 DECL_CONTEXT (t
) = decl
;
1488 DECL_ARGUMENTS (decl
) = t
;
1490 allocate_struct_function (decl
, false);
1492 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1494 set_cfun (act_cfun
);
1499 /* Replace uses of NAME by VAL in block BB. */
1502 replace_uses_in_bb_by (tree name
, tree val
, basic_block bb
)
1505 imm_use_iterator imm_iter
;
1507 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, name
)
1509 if (gimple_bb (use_stmt
) != bb
)
1512 use_operand_p use_p
;
1513 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1514 SET_USE (use_p
, val
);
1518 /* Do transformation from:
1525 ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1526 sum_a = PHI <sum_init (preheader), sum_b (latch)>
1530 sum_b = sum_a + sum_update
1538 ivtmp_b = ivtmp_a + 1;
1542 sum_z = PHI <sum_b (cond[1]), ...>
1544 [1] Where <bb cond> is single_pred (bb latch); In the simplest case,
1554 ivtmp_a = PHI <ivtmp_c (latch)>
1555 sum_a = PHI <sum_c (latch)>
1559 sum_b = sum_a + sum_update
1564 ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1565 sum_c = PHI <sum_init (preheader), sum_b (latch)>
1566 if (ivtmp_c < n + 1)
1572 ivtmp_b = ivtmp_a + 1;
1576 sum_y = PHI <sum_c (newheader)>
1579 sum_z = PHI <sum_y (newexit), ...>
1582 In unified diff format:
1587 + goto <bb newheader>
1590 - ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1591 - sum_a = PHI <sum_init (preheader), sum_b (latch)>
1592 + ivtmp_a = PHI <ivtmp_c (latch)>
1593 + sum_a = PHI <sum_c (latch)>
1597 sum_b = sum_a + sum_update
1604 + ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1605 + sum_c = PHI <sum_init (preheader), sum_b (latch)>
1606 + if (ivtmp_c < n + 1)
1612 ivtmp_b = ivtmp_a + 1;
1614 + goto <bb newheader>
1617 + sum_y = PHI <sum_c (newheader)>
1620 - sum_z = PHI <sum_b (cond[1]), ...>
1621 + sum_z = PHI <sum_y (newexit), ...>
1623 Note: the example does not show any virtual phis, but these are handled more
1624 or less as reductions.
1627 Moves the exit condition of LOOP to the beginning of its header.
1628 REDUCTION_LIST describes the reductions in LOOP. BOUND is the new loop
1632 transform_to_exit_first_loop_alt (struct loop
*loop
,
1633 reduction_info_table_type
*reduction_list
,
1636 basic_block header
= loop
->header
;
1637 basic_block latch
= loop
->latch
;
1638 edge exit
= single_dom_exit (loop
);
1639 basic_block exit_block
= exit
->dest
;
1640 gcond
*cond_stmt
= as_a
<gcond
*> (last_stmt (exit
->src
));
1641 tree control
= gimple_cond_lhs (cond_stmt
);
1644 /* Rewriting virtuals into loop-closed ssa normal form makes this
1645 transformation simpler. It also ensures that the virtuals are in
1646 loop-closed ssa normal from after the transformation, which is required by
1647 create_parallel_loop. */
1648 rewrite_virtuals_into_loop_closed_ssa (loop
);
1650 /* Create the new_header block. */
1651 basic_block new_header
= split_block_before_cond_jump (exit
->src
);
1652 edge edge_at_split
= single_pred_edge (new_header
);
1654 /* Redirect entry edge to new_header. */
1655 edge entry
= loop_preheader_edge (loop
);
1656 e
= redirect_edge_and_branch (entry
, new_header
);
1657 gcc_assert (e
== entry
);
1659 /* Redirect post_inc_edge to new_header. */
1660 edge post_inc_edge
= single_succ_edge (latch
);
1661 e
= redirect_edge_and_branch (post_inc_edge
, new_header
);
1662 gcc_assert (e
== post_inc_edge
);
1664 /* Redirect post_cond_edge to header. */
1665 edge post_cond_edge
= single_pred_edge (latch
);
1666 e
= redirect_edge_and_branch (post_cond_edge
, header
);
1667 gcc_assert (e
== post_cond_edge
);
1669 /* Redirect edge_at_split to latch. */
1670 e
= redirect_edge_and_branch (edge_at_split
, latch
);
1671 gcc_assert (e
== edge_at_split
);
1673 /* Set the new loop bound. */
1674 gimple_cond_set_rhs (cond_stmt
, bound
);
1675 update_stmt (cond_stmt
);
1677 /* Repair the ssa. */
1678 vec
<edge_var_map
> *v
= redirect_edge_var_map_vector (post_inc_edge
);
1682 for (gsi
= gsi_start_phis (header
), i
= 0;
1683 !gsi_end_p (gsi
) && v
->iterate (i
, &vm
);
1684 gsi_next (&gsi
), i
++)
1686 gphi
*phi
= gsi
.phi ();
1687 tree res_a
= PHI_RESULT (phi
);
1689 /* Create new phi. */
1690 tree res_c
= copy_ssa_name (res_a
, phi
);
1691 gphi
*nphi
= create_phi_node (res_c
, new_header
);
1693 /* Replace ivtmp_a with ivtmp_c in condition 'if (ivtmp_a < n)'. */
1694 replace_uses_in_bb_by (res_a
, res_c
, new_header
);
1696 /* Replace ivtmp/sum_b with ivtmp/sum_c in header phi. */
1697 add_phi_arg (phi
, res_c
, post_cond_edge
, UNKNOWN_LOCATION
);
1699 /* Replace sum_b with sum_c in exit phi. */
1700 tree res_b
= redirect_edge_var_map_def (vm
);
1701 replace_uses_in_bb_by (res_b
, res_c
, exit_block
);
1703 struct reduction_info
*red
= reduction_phi (reduction_list
, phi
);
1704 gcc_assert (virtual_operand_p (res_a
)
1710 /* Register the new reduction phi. */
1711 red
->reduc_phi
= nphi
;
1712 gimple_set_uid (red
->reduc_phi
, red
->reduc_version
);
1715 gcc_assert (gsi_end_p (gsi
) && !v
->iterate (i
, &vm
));
1717 /* Set the preheader argument of the new phis to ivtmp/sum_init. */
1718 flush_pending_stmts (entry
);
1720 /* Set the latch arguments of the new phis to ivtmp/sum_b. */
1721 flush_pending_stmts (post_inc_edge
);
1724 basic_block new_exit_block
= NULL
;
1725 if (!single_pred_p (exit
->dest
))
1727 /* Create a new empty exit block, inbetween the new loop header and the
1728 old exit block. The function separate_decls_in_region needs this block
1729 to insert code that is active on loop exit, but not any other path. */
1730 new_exit_block
= split_edge (exit
);
1733 /* Insert and register the reduction exit phis. */
1734 for (gphi_iterator gsi
= gsi_start_phis (exit_block
);
1738 gphi
*phi
= gsi
.phi ();
1740 tree res_z
= PHI_RESULT (phi
);
1743 if (new_exit_block
!= NULL
)
1745 /* Now that we have a new exit block, duplicate the phi of the old
1746 exit block in the new exit block to preserve loop-closed ssa. */
1747 edge succ_new_exit_block
= single_succ_edge (new_exit_block
);
1748 edge pred_new_exit_block
= single_pred_edge (new_exit_block
);
1749 tree res_y
= copy_ssa_name (res_z
, phi
);
1750 nphi
= create_phi_node (res_y
, new_exit_block
);
1751 res_c
= PHI_ARG_DEF_FROM_EDGE (phi
, succ_new_exit_block
);
1752 add_phi_arg (nphi
, res_c
, pred_new_exit_block
, UNKNOWN_LOCATION
);
1753 add_phi_arg (phi
, res_y
, succ_new_exit_block
, UNKNOWN_LOCATION
);
1756 res_c
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1758 if (virtual_operand_p (res_z
))
1761 gimple
*reduc_phi
= SSA_NAME_DEF_STMT (res_c
);
1762 struct reduction_info
*red
= reduction_phi (reduction_list
, reduc_phi
);
1764 red
->keep_res
= (nphi
!= NULL
1769 /* We're going to cancel the loop at the end of gen_parallel_loop, but until
1770 then we're still using some fields, so only bother about fields that are
1771 still used: header and latch.
1772 The loop has a new header bb, so we update it. The latch bb stays the
1774 loop
->header
= new_header
;
1776 /* Recalculate dominance info. */
1777 free_dominance_info (CDI_DOMINATORS
);
1778 calculate_dominance_info (CDI_DOMINATORS
);
1780 checking_verify_ssa (true, true);
1783 /* Tries to moves the exit condition of LOOP to the beginning of its header
1784 without duplication of the loop body. NIT is the number of iterations of the
1785 loop. REDUCTION_LIST describes the reductions in LOOP. Return true if
1786 transformation is successful. */
1789 try_transform_to_exit_first_loop_alt (struct loop
*loop
,
1790 reduction_info_table_type
*reduction_list
,
1793 /* Check whether the latch contains a single statement. */
1794 if (!gimple_seq_nondebug_singleton_p (bb_seq (loop
->latch
)))
1797 /* Check whether the latch contains no phis. */
1798 if (phi_nodes (loop
->latch
) != NULL
)
1801 /* Check whether the latch contains the loop iv increment. */
1802 edge back
= single_succ_edge (loop
->latch
);
1803 edge exit
= single_dom_exit (loop
);
1804 gcond
*cond_stmt
= as_a
<gcond
*> (last_stmt (exit
->src
));
1805 tree control
= gimple_cond_lhs (cond_stmt
);
1806 gphi
*phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (control
));
1807 tree inc_res
= gimple_phi_arg_def (phi
, back
->dest_idx
);
1808 if (gimple_bb (SSA_NAME_DEF_STMT (inc_res
)) != loop
->latch
)
1811 /* Check whether there's no code between the loop condition and the latch. */
1812 if (!single_pred_p (loop
->latch
)
1813 || single_pred (loop
->latch
) != exit
->src
)
1816 tree alt_bound
= NULL_TREE
;
1817 tree nit_type
= TREE_TYPE (nit
);
1819 /* Figure out whether nit + 1 overflows. */
1820 if (TREE_CODE (nit
) == INTEGER_CST
)
1822 if (!tree_int_cst_equal (nit
, TYPE_MAXVAL (nit_type
)))
1824 alt_bound
= fold_build2_loc (UNKNOWN_LOCATION
, PLUS_EXPR
, nit_type
,
1825 nit
, build_one_cst (nit_type
));
1827 gcc_assert (TREE_CODE (alt_bound
) == INTEGER_CST
);
1828 transform_to_exit_first_loop_alt (loop
, reduction_list
, alt_bound
);
1833 /* Todo: Figure out if we can trigger this, if it's worth to handle
1834 optimally, and if we can handle it optimally. */
1839 gcc_assert (TREE_CODE (nit
) == SSA_NAME
);
1841 /* Variable nit is the loop bound as returned by canonicalize_loop_ivs, for an
1842 iv with base 0 and step 1 that is incremented in the latch, like this:
1845 # iv_1 = PHI <0 (preheader), iv_2 (latch)>
1856 The range of iv_1 is [0, nit]. The latch edge is taken for
1857 iv_1 == [0, nit - 1] and the exit edge is taken for iv_1 == nit. So the
1858 number of latch executions is equal to nit.
1860 The function max_loop_iterations gives us the maximum number of latch
1861 executions, so it gives us the maximum value of nit. */
1863 if (!max_loop_iterations (loop
, &nit_max
))
1866 /* Check if nit + 1 overflows. */
1867 widest_int type_max
= wi::to_widest (TYPE_MAXVAL (nit_type
));
1868 if (!wi::lts_p (nit_max
, type_max
))
1871 gimple
*def
= SSA_NAME_DEF_STMT (nit
);
1873 /* Try to find nit + 1, in the form of n in an assignment nit = n - 1. */
1875 && is_gimple_assign (def
)
1876 && gimple_assign_rhs_code (def
) == PLUS_EXPR
)
1878 tree op1
= gimple_assign_rhs1 (def
);
1879 tree op2
= gimple_assign_rhs2 (def
);
1880 if (integer_minus_onep (op1
))
1882 else if (integer_minus_onep (op2
))
1886 /* If not found, insert nit + 1. */
1887 if (alt_bound
== NULL_TREE
)
1889 alt_bound
= fold_build2 (PLUS_EXPR
, nit_type
, nit
,
1890 build_int_cst_type (nit_type
, 1));
1892 gimple_stmt_iterator gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
1895 = force_gimple_operand_gsi (&gsi
, alt_bound
, true, NULL_TREE
, false,
1896 GSI_CONTINUE_LINKING
);
1899 transform_to_exit_first_loop_alt (loop
, reduction_list
, alt_bound
);
1903 /* Moves the exit condition of LOOP to the beginning of its header. NIT is the
1904 number of iterations of the loop. REDUCTION_LIST describes the reductions in
1908 transform_to_exit_first_loop (struct loop
*loop
,
1909 reduction_info_table_type
*reduction_list
,
1912 basic_block
*bbs
, *nbbs
, ex_bb
, orig_header
;
1915 edge exit
= single_dom_exit (loop
), hpred
;
1916 tree control
, control_name
, res
, t
;
1919 gcond
*cond_stmt
, *cond_nit
;
1922 split_block_after_labels (loop
->header
);
1923 orig_header
= single_succ (loop
->header
);
1924 hpred
= single_succ_edge (loop
->header
);
1926 cond_stmt
= as_a
<gcond
*> (last_stmt (exit
->src
));
1927 control
= gimple_cond_lhs (cond_stmt
);
1928 gcc_assert (gimple_cond_rhs (cond_stmt
) == nit
);
1930 /* Make sure that we have phi nodes on exit for all loop header phis
1931 (create_parallel_loop requires that). */
1932 for (gphi_iterator gsi
= gsi_start_phis (loop
->header
);
1937 res
= PHI_RESULT (phi
);
1938 t
= copy_ssa_name (res
, phi
);
1939 SET_PHI_RESULT (phi
, t
);
1940 nphi
= create_phi_node (res
, orig_header
);
1941 add_phi_arg (nphi
, t
, hpred
, UNKNOWN_LOCATION
);
1945 gimple_cond_set_lhs (cond_stmt
, t
);
1946 update_stmt (cond_stmt
);
1951 bbs
= get_loop_body_in_dom_order (loop
);
1953 for (n
= 0; bbs
[n
] != exit
->src
; n
++)
1955 nbbs
= XNEWVEC (basic_block
, n
);
1956 ok
= gimple_duplicate_sese_tail (single_succ_edge (loop
->header
), exit
,
1963 /* Other than reductions, the only gimple reg that should be copied
1964 out of the loop is the control variable. */
1965 exit
= single_dom_exit (loop
);
1966 control_name
= NULL_TREE
;
1967 for (gphi_iterator gsi
= gsi_start_phis (ex_bb
);
1971 res
= PHI_RESULT (phi
);
1972 if (virtual_operand_p (res
))
1978 /* Check if it is a part of reduction. If it is,
1979 keep the phi at the reduction's keep_res field. The
1980 PHI_RESULT of this phi is the resulting value of the reduction
1981 variable when exiting the loop. */
1983 if (reduction_list
->elements () > 0)
1985 struct reduction_info
*red
;
1987 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1988 red
= reduction_phi (reduction_list
, SSA_NAME_DEF_STMT (val
));
1991 red
->keep_res
= phi
;
1996 gcc_assert (control_name
== NULL_TREE
1997 && SSA_NAME_VAR (res
) == SSA_NAME_VAR (control
));
1999 remove_phi_node (&gsi
, false);
2001 gcc_assert (control_name
!= NULL_TREE
);
2003 /* Initialize the control variable to number of iterations
2004 according to the rhs of the exit condition. */
2005 gimple_stmt_iterator gsi
= gsi_after_labels (ex_bb
);
2006 cond_nit
= as_a
<gcond
*> (last_stmt (exit
->src
));
2007 nit_1
= gimple_cond_rhs (cond_nit
);
2008 nit_1
= force_gimple_operand_gsi (&gsi
,
2009 fold_convert (TREE_TYPE (control_name
), nit_1
),
2010 false, NULL_TREE
, false, GSI_SAME_STMT
);
2011 stmt
= gimple_build_assign (control_name
, nit_1
);
2012 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2015 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
2016 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
2017 NEW_DATA is the variable that should be initialized from the argument
2018 of LOOP_FN. N_THREADS is the requested number of threads. */
2021 create_parallel_loop (struct loop
*loop
, tree loop_fn
, tree data
,
2022 tree new_data
, unsigned n_threads
, location_t loc
,
2023 bool oacc_kernels_p
)
2025 gimple_stmt_iterator gsi
;
2026 basic_block for_bb
, ex_bb
, continue_bb
;
2028 gomp_parallel
*omp_par_stmt
;
2029 gimple
*omp_return_stmt1
, *omp_return_stmt2
;
2033 gomp_continue
*omp_cont_stmt
;
2034 tree cvar
, cvar_init
, initvar
, cvar_next
, cvar_base
, type
;
2035 edge exit
, nexit
, guard
, end
, e
;
2037 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
2040 tree clause
= build_omp_clause (loc
, OMP_CLAUSE_NUM_GANGS
);
2041 OMP_CLAUSE_NUM_GANGS_EXPR (clause
)
2042 = build_int_cst (integer_type_node
, n_threads
);
2043 set_oacc_fn_attrib (cfun
->decl
, clause
, NULL
);
2047 basic_block bb
= loop_preheader_edge (loop
)->src
;
2048 basic_block paral_bb
= single_pred (bb
);
2049 gsi
= gsi_last_bb (paral_bb
);
2051 t
= build_omp_clause (loc
, OMP_CLAUSE_NUM_THREADS
);
2052 OMP_CLAUSE_NUM_THREADS_EXPR (t
)
2053 = build_int_cst (integer_type_node
, n_threads
);
2054 omp_par_stmt
= gimple_build_omp_parallel (NULL
, t
, loop_fn
, data
);
2055 gimple_set_location (omp_par_stmt
, loc
);
2057 gsi_insert_after (&gsi
, omp_par_stmt
, GSI_NEW_STMT
);
2059 /* Initialize NEW_DATA. */
2062 gassign
*assign_stmt
;
2064 gsi
= gsi_after_labels (bb
);
2066 param
= make_ssa_name (DECL_ARGUMENTS (loop_fn
));
2067 assign_stmt
= gimple_build_assign (param
, build_fold_addr_expr (data
));
2068 gsi_insert_before (&gsi
, assign_stmt
, GSI_SAME_STMT
);
2070 assign_stmt
= gimple_build_assign (new_data
,
2071 fold_convert (TREE_TYPE (new_data
), param
));
2072 gsi_insert_before (&gsi
, assign_stmt
, GSI_SAME_STMT
);
2075 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
2076 bb
= split_loop_exit_edge (single_dom_exit (loop
));
2077 gsi
= gsi_last_bb (bb
);
2078 omp_return_stmt1
= gimple_build_omp_return (false);
2079 gimple_set_location (omp_return_stmt1
, loc
);
2080 gsi_insert_after (&gsi
, omp_return_stmt1
, GSI_NEW_STMT
);
2083 /* Extract data for GIMPLE_OMP_FOR. */
2084 gcc_assert (loop
->header
== single_dom_exit (loop
)->src
);
2085 cond_stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
2087 cvar
= gimple_cond_lhs (cond_stmt
);
2088 cvar_base
= SSA_NAME_VAR (cvar
);
2089 phi
= SSA_NAME_DEF_STMT (cvar
);
2090 cvar_init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2091 initvar
= copy_ssa_name (cvar
);
2092 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, loop_preheader_edge (loop
)),
2094 cvar_next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2096 gsi
= gsi_last_nondebug_bb (loop
->latch
);
2097 gcc_assert (gsi_stmt (gsi
) == SSA_NAME_DEF_STMT (cvar_next
));
2098 gsi_remove (&gsi
, true);
2101 for_bb
= split_edge (loop_preheader_edge (loop
));
2102 ex_bb
= split_loop_exit_edge (single_dom_exit (loop
));
2103 extract_true_false_edges_from_block (loop
->header
, &nexit
, &exit
);
2104 gcc_assert (exit
== single_dom_exit (loop
));
2106 guard
= make_edge (for_bb
, ex_bb
, 0);
2107 /* Split the latch edge, so LOOPS_HAVE_SIMPLE_LATCHES is still valid. */
2108 loop
->latch
= split_edge (single_succ_edge (loop
->latch
));
2109 single_pred_edge (loop
->latch
)->flags
= 0;
2110 end
= make_edge (single_pred (loop
->latch
), ex_bb
, EDGE_FALLTHRU
);
2111 rescan_loop_exit (end
, true, false);
2113 for (gphi_iterator gpi
= gsi_start_phis (ex_bb
);
2114 !gsi_end_p (gpi
); gsi_next (&gpi
))
2116 source_location locus
;
2117 gphi
*phi
= gpi
.phi ();
2118 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2119 gimple
*def_stmt
= SSA_NAME_DEF_STMT (def
);
2121 /* If the exit phi is not connected to a header phi in the same loop, this
2122 value is not modified in the loop, and we're done with this phi. */
2123 if (!(gimple_code (def_stmt
) == GIMPLE_PHI
2124 && gimple_bb (def_stmt
) == loop
->header
))
2126 locus
= gimple_phi_arg_location_from_edge (phi
, exit
);
2127 add_phi_arg (phi
, def
, guard
, locus
);
2128 add_phi_arg (phi
, def
, end
, locus
);
2132 gphi
*stmt
= as_a
<gphi
*> (def_stmt
);
2133 def
= PHI_ARG_DEF_FROM_EDGE (stmt
, loop_preheader_edge (loop
));
2134 locus
= gimple_phi_arg_location_from_edge (stmt
,
2135 loop_preheader_edge (loop
));
2136 add_phi_arg (phi
, def
, guard
, locus
);
2138 def
= PHI_ARG_DEF_FROM_EDGE (stmt
, loop_latch_edge (loop
));
2139 locus
= gimple_phi_arg_location_from_edge (stmt
, loop_latch_edge (loop
));
2140 add_phi_arg (phi
, def
, end
, locus
);
2142 e
= redirect_edge_and_branch (exit
, nexit
->dest
);
2143 PENDING_STMT (e
) = NULL
;
2145 /* Emit GIMPLE_OMP_FOR. */
2147 /* In combination with the NUM_GANGS on the parallel. */
2148 t
= build_omp_clause (loc
, OMP_CLAUSE_GANG
);
2151 t
= build_omp_clause (loc
, OMP_CLAUSE_SCHEDULE
);
2152 int chunk_size
= PARAM_VALUE (PARAM_PARLOOPS_CHUNK_SIZE
);
2153 enum PARAM_PARLOOPS_SCHEDULE_KIND schedule_type \
2154 = (enum PARAM_PARLOOPS_SCHEDULE_KIND
) PARAM_VALUE (PARAM_PARLOOPS_SCHEDULE
);
2155 switch (schedule_type
)
2157 case PARAM_PARLOOPS_SCHEDULE_KIND_static
:
2158 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_STATIC
;
2160 case PARAM_PARLOOPS_SCHEDULE_KIND_dynamic
:
2161 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_DYNAMIC
;
2163 case PARAM_PARLOOPS_SCHEDULE_KIND_guided
:
2164 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_GUIDED
;
2166 case PARAM_PARLOOPS_SCHEDULE_KIND_auto
:
2167 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_AUTO
;
2170 case PARAM_PARLOOPS_SCHEDULE_KIND_runtime
:
2171 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_RUNTIME
;
2177 if (chunk_size
!= 0)
2178 OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (t
)
2179 = build_int_cst (integer_type_node
, chunk_size
);
2182 for_stmt
= gimple_build_omp_for (NULL
,
2184 ? GF_OMP_FOR_KIND_OACC_LOOP
2185 : GF_OMP_FOR_KIND_FOR
),
2188 gimple_cond_set_lhs (cond_stmt
, cvar_base
);
2189 type
= TREE_TYPE (cvar
);
2190 gimple_set_location (for_stmt
, loc
);
2191 gimple_omp_for_set_index (for_stmt
, 0, initvar
);
2192 gimple_omp_for_set_initial (for_stmt
, 0, cvar_init
);
2193 gimple_omp_for_set_final (for_stmt
, 0, gimple_cond_rhs (cond_stmt
));
2194 gimple_omp_for_set_cond (for_stmt
, 0, gimple_cond_code (cond_stmt
));
2195 gimple_omp_for_set_incr (for_stmt
, 0, build2 (PLUS_EXPR
, type
,
2197 build_int_cst (type
, 1)));
2199 gsi
= gsi_last_bb (for_bb
);
2200 gsi_insert_after (&gsi
, for_stmt
, GSI_NEW_STMT
);
2201 SSA_NAME_DEF_STMT (initvar
) = for_stmt
;
2203 /* Emit GIMPLE_OMP_CONTINUE. */
2204 continue_bb
= single_pred (loop
->latch
);
2205 gsi
= gsi_last_bb (continue_bb
);
2206 omp_cont_stmt
= gimple_build_omp_continue (cvar_next
, cvar
);
2207 gimple_set_location (omp_cont_stmt
, loc
);
2208 gsi_insert_after (&gsi
, omp_cont_stmt
, GSI_NEW_STMT
);
2209 SSA_NAME_DEF_STMT (cvar_next
) = omp_cont_stmt
;
2211 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
2212 gsi
= gsi_last_bb (ex_bb
);
2213 omp_return_stmt2
= gimple_build_omp_return (true);
2214 gimple_set_location (omp_return_stmt2
, loc
);
2215 gsi_insert_after (&gsi
, omp_return_stmt2
, GSI_NEW_STMT
);
2217 /* After the above dom info is hosed. Re-compute it. */
2218 free_dominance_info (CDI_DOMINATORS
);
2219 calculate_dominance_info (CDI_DOMINATORS
);
2222 /* Generates code to execute the iterations of LOOP in N_THREADS
2223 threads in parallel.
2225 NITER describes number of iterations of LOOP.
2226 REDUCTION_LIST describes the reductions existent in the LOOP. */
2229 gen_parallel_loop (struct loop
*loop
,
2230 reduction_info_table_type
*reduction_list
,
2231 unsigned n_threads
, struct tree_niter_desc
*niter
,
2232 bool oacc_kernels_p
)
2234 tree many_iterations_cond
, type
, nit
;
2235 tree arg_struct
, new_arg_struct
;
2238 struct clsn_data clsn_data
;
2242 unsigned int m_p_thread
=2;
2246 ---------------------------------------------------------------------
2249 IV = phi (INIT, IV + STEP)
2255 ---------------------------------------------------------------------
2257 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
2258 we generate the following code:
2260 ---------------------------------------------------------------------
2263 || NITER < MIN_PER_THREAD * N_THREADS)
2267 store all local loop-invariant variables used in body of the loop to DATA.
2268 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
2269 load the variables from DATA.
2270 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
2273 GIMPLE_OMP_CONTINUE;
2274 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
2275 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
2281 IV = phi (INIT, IV + STEP)
2292 /* Create two versions of the loop -- in the old one, we know that the
2293 number of iterations is large enough, and we will transform it into the
2294 loop that will be split to loop_fn, the new one will be used for the
2295 remaining iterations. */
2297 /* We should compute a better number-of-iterations value for outer loops.
2300 for (i = 0; i < n; ++i)
2301 for (j = 0; j < m; ++j)
2304 we should compute nit = n * m, not nit = n.
2305 Also may_be_zero handling would need to be adjusted. */
2307 type
= TREE_TYPE (niter
->niter
);
2308 nit
= force_gimple_operand (unshare_expr (niter
->niter
), &stmts
, true,
2311 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
2313 if (!oacc_kernels_p
)
2318 m_p_thread
=MIN_PER_THREAD
;
2320 many_iterations_cond
=
2321 fold_build2 (GE_EXPR
, boolean_type_node
,
2322 nit
, build_int_cst (type
, m_p_thread
* n_threads
));
2324 many_iterations_cond
2325 = fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
2326 invert_truthvalue (unshare_expr (niter
->may_be_zero
)),
2327 many_iterations_cond
);
2328 many_iterations_cond
2329 = force_gimple_operand (many_iterations_cond
, &stmts
, false, NULL_TREE
);
2331 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
2332 if (!is_gimple_condexpr (many_iterations_cond
))
2334 many_iterations_cond
2335 = force_gimple_operand (many_iterations_cond
, &stmts
,
2338 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
),
2342 initialize_original_copy_tables ();
2344 /* We assume that the loop usually iterates a lot. */
2345 prob
= 4 * REG_BR_PROB_BASE
/ 5;
2346 loop_version (loop
, many_iterations_cond
, NULL
,
2347 prob
, prob
, REG_BR_PROB_BASE
- prob
, true);
2348 update_ssa (TODO_update_ssa
);
2349 free_original_copy_tables ();
2352 /* Base all the induction variables in LOOP on a single control one. */
2353 canonicalize_loop_ivs (loop
, &nit
, true);
2355 /* Ensure that the exit condition is the first statement in the loop.
2356 The common case is that latch of the loop is empty (apart from the
2357 increment) and immediately follows the loop exit test. Attempt to move the
2358 entry of the loop directly before the exit check and increase the number of
2359 iterations of the loop by one. */
2360 if (try_transform_to_exit_first_loop_alt (loop
, reduction_list
, nit
))
2363 && (dump_flags
& TDF_DETAILS
))
2365 "alternative exit-first loop transform succeeded"
2366 " for loop %d\n", loop
->num
);
2373 /* Fall back on the method that handles more cases, but duplicates the
2374 loop body: move the exit condition of LOOP to the beginning of its
2375 header, and duplicate the part of the last iteration that gets disabled
2376 to the exit of the loop. */
2377 transform_to_exit_first_loop (loop
, reduction_list
, nit
);
2380 /* Generate initializations for reductions. */
2381 if (reduction_list
->elements () > 0)
2382 reduction_list
->traverse
<struct loop
*, initialize_reductions
> (loop
);
2384 /* Eliminate the references to local variables from the loop. */
2385 gcc_assert (single_exit (loop
));
2386 entry
= loop_preheader_edge (loop
);
2387 exit
= single_dom_exit (loop
);
2389 /* This rewrites the body in terms of new variables. This has already
2390 been done for oacc_kernels_p in pass_lower_omp/lower_omp (). */
2391 if (!oacc_kernels_p
)
2393 eliminate_local_variables (entry
, exit
);
2394 /* In the old loop, move all variables non-local to the loop to a
2395 structure and back, and create separate decls for the variables used in
2397 separate_decls_in_region (entry
, exit
, reduction_list
, &arg_struct
,
2398 &new_arg_struct
, &clsn_data
);
2402 arg_struct
= NULL_TREE
;
2403 new_arg_struct
= NULL_TREE
;
2404 clsn_data
.load
= NULL_TREE
;
2405 clsn_data
.load_bb
= exit
->dest
;
2406 clsn_data
.store
= NULL_TREE
;
2407 clsn_data
.store_bb
= NULL
;
2410 /* Create the parallel constructs. */
2411 loc
= UNKNOWN_LOCATION
;
2412 cond_stmt
= last_stmt (loop
->header
);
2414 loc
= gimple_location (cond_stmt
);
2415 create_parallel_loop (loop
, create_loop_fn (loc
), arg_struct
, new_arg_struct
,
2416 n_threads
, loc
, oacc_kernels_p
);
2417 if (reduction_list
->elements () > 0)
2418 create_call_for_reduction (loop
, reduction_list
, &clsn_data
);
2422 /* Free loop bound estimations that could contain references to
2423 removed statements. */
2424 FOR_EACH_LOOP (loop
, 0)
2425 free_numbers_of_iterations_estimates_loop (loop
);
2428 /* Returns true when LOOP contains vector phi nodes. */
2431 loop_has_vector_phi_nodes (struct loop
*loop ATTRIBUTE_UNUSED
)
2434 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
2438 for (i
= 0; i
< loop
->num_nodes
; i
++)
2439 for (gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
2440 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi
.phi ()))) == VECTOR_TYPE
)
2449 /* Create a reduction_info struct, initialize it with REDUC_STMT
2450 and PHI, insert it to the REDUCTION_LIST. */
2453 build_new_reduction (reduction_info_table_type
*reduction_list
,
2454 gimple
*reduc_stmt
, gphi
*phi
)
2456 reduction_info
**slot
;
2457 struct reduction_info
*new_reduction
;
2458 enum tree_code reduction_code
;
2460 gcc_assert (reduc_stmt
);
2462 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2465 "Detected reduction. reduction stmt is:\n");
2466 print_gimple_stmt (dump_file
, reduc_stmt
, 0, 0);
2467 fprintf (dump_file
, "\n");
2470 if (gimple_code (reduc_stmt
) == GIMPLE_PHI
)
2472 tree op1
= PHI_ARG_DEF (reduc_stmt
, 0);
2473 gimple
*def1
= SSA_NAME_DEF_STMT (op1
);
2474 reduction_code
= gimple_assign_rhs_code (def1
);
2478 reduction_code
= gimple_assign_rhs_code (reduc_stmt
);
2480 new_reduction
= XCNEW (struct reduction_info
);
2482 new_reduction
->reduc_stmt
= reduc_stmt
;
2483 new_reduction
->reduc_phi
= phi
;
2484 new_reduction
->reduc_version
= SSA_NAME_VERSION (gimple_phi_result (phi
));
2485 new_reduction
->reduction_code
= reduction_code
;
2486 slot
= reduction_list
->find_slot (new_reduction
, INSERT
);
2487 *slot
= new_reduction
;
2490 /* Callback for htab_traverse. Sets gimple_uid of reduc_phi stmts. */
2493 set_reduc_phi_uids (reduction_info
**slot
, void *data ATTRIBUTE_UNUSED
)
2495 struct reduction_info
*const red
= *slot
;
2496 gimple_set_uid (red
->reduc_phi
, red
->reduc_version
);
2500 /* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
2503 gather_scalar_reductions (loop_p loop
, reduction_info_table_type
*reduction_list
)
2506 loop_vec_info simple_loop_info
;
2507 loop_vec_info simple_inner_loop_info
= NULL
;
2508 bool allow_double_reduc
= true;
2510 if (!stmt_vec_info_vec
.exists ())
2511 init_stmt_vec_info_vec ();
2513 simple_loop_info
= vect_analyze_loop_form (loop
);
2514 if (simple_loop_info
== NULL
)
2517 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2519 gphi
*phi
= gsi
.phi ();
2521 tree res
= PHI_RESULT (phi
);
2524 if (virtual_operand_p (res
))
2527 if (simple_iv (loop
, loop
, res
, &iv
, true))
2531 = vect_force_simple_reduction (simple_loop_info
, phi
, true,
2532 &double_reduc
, true);
2538 if (!allow_double_reduc
2539 || loop
->inner
->inner
!= NULL
)
2542 if (!simple_inner_loop_info
)
2544 simple_inner_loop_info
= vect_analyze_loop_form (loop
->inner
);
2545 if (!simple_inner_loop_info
)
2547 allow_double_reduc
= false;
2552 use_operand_p use_p
;
2554 bool single_use_p
= single_imm_use (res
, &use_p
, &inner_stmt
);
2555 gcc_assert (single_use_p
);
2556 if (gimple_code (inner_stmt
) != GIMPLE_PHI
)
2558 gphi
*inner_phi
= as_a
<gphi
*> (inner_stmt
);
2559 if (simple_iv (loop
->inner
, loop
->inner
, PHI_RESULT (inner_phi
),
2563 gimple
*inner_reduc_stmt
2564 = vect_force_simple_reduction (simple_inner_loop_info
, inner_phi
,
2565 true, &double_reduc
, true);
2566 gcc_assert (!double_reduc
);
2567 if (inner_reduc_stmt
== NULL
)
2571 build_new_reduction (reduction_list
, reduc_stmt
, phi
);
2573 destroy_loop_vec_info (simple_loop_info
, true);
2574 destroy_loop_vec_info (simple_inner_loop_info
, true);
2577 /* Release the claim on gimple_uid. */
2578 free_stmt_vec_info_vec ();
2580 if (reduction_list
->elements () == 0)
2583 /* As gimple_uid is used by the vectorizer in between vect_analyze_loop_form
2584 and free_stmt_vec_info_vec, we can set gimple_uid of reduc_phi stmts only
2587 FOR_EACH_BB_FN (bb
, cfun
)
2588 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2589 gimple_set_uid (gsi_stmt (gsi
), (unsigned int)-1);
2590 reduction_list
->traverse
<void *, set_reduc_phi_uids
> (NULL
);
2593 /* Try to initialize NITER for code generation part. */
2596 try_get_loop_niter (loop_p loop
, struct tree_niter_desc
*niter
)
2598 edge exit
= single_dom_exit (loop
);
2602 /* We need to know # of iterations, and there should be no uses of values
2603 defined inside loop outside of it, unless the values are invariants of
2605 if (!number_of_iterations_exit (loop
, exit
, niter
, false))
2607 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2608 fprintf (dump_file
, " FAILED: number of iterations not known\n");
2615 /* Return the default def of the first function argument. */
2618 get_omp_data_i_param (void)
2620 tree decl
= DECL_ARGUMENTS (cfun
->decl
);
2621 gcc_assert (DECL_CHAIN (decl
) == NULL_TREE
);
2622 return ssa_default_def (cfun
, decl
);
2625 /* For PHI in loop header of LOOP, look for pattern:
2628 .omp_data_i = &.omp_data_arr;
2629 addr = .omp_data_i->sum;
2633 sum_b = PHI <sum_a (preheader), sum_c (latch)>
2635 and return addr. Otherwise, return NULL_TREE. */
2638 find_reduc_addr (struct loop
*loop
, gphi
*phi
)
2640 edge e
= loop_preheader_edge (loop
);
2641 tree arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
2642 gimple
*stmt
= SSA_NAME_DEF_STMT (arg
);
2643 if (!gimple_assign_single_p (stmt
))
2645 tree memref
= gimple_assign_rhs1 (stmt
);
2646 if (TREE_CODE (memref
) != MEM_REF
)
2648 tree addr
= TREE_OPERAND (memref
, 0);
2650 gimple
*stmt2
= SSA_NAME_DEF_STMT (addr
);
2651 if (!gimple_assign_single_p (stmt2
))
2653 tree compref
= gimple_assign_rhs1 (stmt2
);
2654 if (TREE_CODE (compref
) != COMPONENT_REF
)
2656 tree addr2
= TREE_OPERAND (compref
, 0);
2657 if (TREE_CODE (addr2
) != MEM_REF
)
2659 addr2
= TREE_OPERAND (addr2
, 0);
2660 if (TREE_CODE (addr2
) != SSA_NAME
2661 || addr2
!= get_omp_data_i_param ())
2667 /* Try to initialize REDUCTION_LIST for code generation part.
2668 REDUCTION_LIST describes the reductions. */
2671 try_create_reduction_list (loop_p loop
,
2672 reduction_info_table_type
*reduction_list
,
2673 bool oacc_kernels_p
)
2675 edge exit
= single_dom_exit (loop
);
2680 /* Try to get rid of exit phis. */
2681 final_value_replacement_loop (loop
);
2683 gather_scalar_reductions (loop
, reduction_list
);
2686 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2688 gphi
*phi
= gsi
.phi ();
2689 struct reduction_info
*red
;
2690 imm_use_iterator imm_iter
;
2691 use_operand_p use_p
;
2693 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2695 if (!virtual_operand_p (val
))
2697 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2699 fprintf (dump_file
, "phi is ");
2700 print_gimple_stmt (dump_file
, phi
, 0, 0);
2701 fprintf (dump_file
, "arg of phi to exit: value ");
2702 print_generic_expr (dump_file
, val
, 0);
2703 fprintf (dump_file
, " used outside loop\n");
2705 " checking if it is part of reduction pattern:\n");
2707 if (reduction_list
->elements () == 0)
2709 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2711 " FAILED: it is not a part of reduction.\n");
2715 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, val
)
2717 if (!gimple_debug_bind_p (USE_STMT (use_p
))
2718 && flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
2720 reduc_phi
= USE_STMT (use_p
);
2724 red
= reduction_phi (reduction_list
, reduc_phi
);
2727 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2729 " FAILED: it is not a part of reduction.\n");
2732 if (red
->keep_res
!= NULL
)
2734 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2736 " FAILED: reduction has multiple exit phis.\n");
2739 red
->keep_res
= phi
;
2740 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2742 fprintf (dump_file
, "reduction phi is ");
2743 print_gimple_stmt (dump_file
, red
->reduc_phi
, 0, 0);
2744 fprintf (dump_file
, "reduction stmt is ");
2745 print_gimple_stmt (dump_file
, red
->reduc_stmt
, 0, 0);
2750 /* The iterations of the loop may communicate only through bivs whose
2751 iteration space can be distributed efficiently. */
2752 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2754 gphi
*phi
= gsi
.phi ();
2755 tree def
= PHI_RESULT (phi
);
2758 if (!virtual_operand_p (def
) && !simple_iv (loop
, loop
, def
, &iv
, true))
2760 struct reduction_info
*red
;
2762 red
= reduction_phi (reduction_list
, phi
);
2765 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2767 " FAILED: scalar dependency between iterations\n");
2775 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
);
2778 gphi
*phi
= gsi
.phi ();
2779 tree def
= PHI_RESULT (phi
);
2782 if (!virtual_operand_p (def
)
2783 && !simple_iv (loop
, loop
, def
, &iv
, true))
2785 tree addr
= find_reduc_addr (loop
, phi
);
2786 if (addr
== NULL_TREE
)
2788 struct reduction_info
*red
= reduction_phi (reduction_list
, phi
);
2789 red
->reduc_addr
= addr
;
2797 /* Return true if LOOP contains phis with ADDR_EXPR in args. */
2800 loop_has_phi_with_address_arg (struct loop
*loop
)
2802 basic_block
*bbs
= get_loop_body (loop
);
2807 for (i
= 0; i
< loop
->num_nodes
; i
++)
2808 for (gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
2810 gphi
*phi
= gsi
.phi ();
2811 for (j
= 0; j
< gimple_phi_num_args (phi
); j
++)
2813 tree arg
= gimple_phi_arg_def (phi
, j
);
2814 if (TREE_CODE (arg
) == ADDR_EXPR
)
2816 /* This should be handled by eliminate_local_variables, but that
2817 function currently ignores phis. */
2829 /* Return true if memory ref REF (corresponding to the stmt at GSI in
2830 REGIONS_BB[I]) conflicts with the statements in REGIONS_BB[I] after gsi,
2831 or the statements in REGIONS_BB[I + n]. REF_IS_STORE indicates if REF is a
2832 store. Ignore conflicts with SKIP_STMT. */
2835 ref_conflicts_with_region (gimple_stmt_iterator gsi
, ao_ref
*ref
,
2836 bool ref_is_store
, vec
<basic_block
> region_bbs
,
2837 unsigned int i
, gimple
*skip_stmt
)
2839 basic_block bb
= region_bbs
[i
];
2844 for (; !gsi_end_p (gsi
);
2847 gimple
*stmt
= gsi_stmt (gsi
);
2848 if (stmt
== skip_stmt
)
2852 fprintf (dump_file
, "skipping reduction store: ");
2853 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2858 if (!gimple_vdef (stmt
)
2859 && !gimple_vuse (stmt
))
2862 if (gimple_code (stmt
) == GIMPLE_RETURN
)
2867 if (ref_maybe_used_by_stmt_p (stmt
, ref
))
2871 fprintf (dump_file
, "Stmt ");
2872 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2879 if (stmt_may_clobber_ref_p_1 (stmt
, ref
))
2883 fprintf (dump_file
, "Stmt ");
2884 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2891 if (i
== region_bbs
.length ())
2894 gsi
= gsi_start_bb (bb
);
2900 /* Return true if the bbs in REGION_BBS but not in in_loop_bbs can be executed
2901 in parallel with REGION_BBS containing the loop. Return the stores of
2902 reduction results in REDUCTION_STORES. */
2905 oacc_entry_exit_ok_1 (bitmap in_loop_bbs
, vec
<basic_block
> region_bbs
,
2906 reduction_info_table_type
*reduction_list
,
2907 bitmap reduction_stores
)
2909 tree omp_data_i
= get_omp_data_i_param ();
2913 FOR_EACH_VEC_ELT (region_bbs
, i
, bb
)
2915 if (bitmap_bit_p (in_loop_bbs
, bb
->index
))
2918 gimple_stmt_iterator gsi
;
2919 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2922 gimple
*stmt
= gsi_stmt (gsi
);
2923 gimple
*skip_stmt
= NULL
;
2925 if (is_gimple_debug (stmt
)
2926 || gimple_code (stmt
) == GIMPLE_COND
)
2930 bool ref_is_store
= false;
2931 if (gimple_assign_load_p (stmt
))
2933 tree rhs
= gimple_assign_rhs1 (stmt
);
2934 tree base
= get_base_address (rhs
);
2935 if (TREE_CODE (base
) == MEM_REF
2936 && operand_equal_p (TREE_OPERAND (base
, 0), omp_data_i
, 0))
2939 tree lhs
= gimple_assign_lhs (stmt
);
2940 if (TREE_CODE (lhs
) == SSA_NAME
2941 && has_single_use (lhs
))
2943 use_operand_p use_p
;
2945 single_imm_use (lhs
, &use_p
, &use_stmt
);
2946 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
2948 struct reduction_info
*red
;
2949 red
= reduction_phi (reduction_list
, use_stmt
);
2950 tree val
= PHI_RESULT (red
->keep_res
);
2951 if (has_single_use (val
))
2953 single_imm_use (val
, &use_p
, &use_stmt
);
2954 if (gimple_store_p (use_stmt
))
2957 = SSA_NAME_VERSION (gimple_vdef (use_stmt
));
2958 bitmap_set_bit (reduction_stores
, id
);
2959 skip_stmt
= use_stmt
;
2962 fprintf (dump_file
, "found reduction load: ");
2963 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2970 ao_ref_init (&ref
, rhs
);
2972 else if (gimple_store_p (stmt
))
2974 ao_ref_init (&ref
, gimple_assign_lhs (stmt
));
2975 ref_is_store
= true;
2977 else if (gimple_code (stmt
) == GIMPLE_OMP_RETURN
)
2979 else if (!gimple_has_side_effects (stmt
)
2980 && !gimple_could_trap_p (stmt
)
2981 && !stmt_could_throw_p (stmt
)
2982 && !gimple_vdef (stmt
)
2983 && !gimple_vuse (stmt
))
2985 else if (is_gimple_call (stmt
)
2986 && gimple_call_internal_p (stmt
)
2987 && gimple_call_internal_fn (stmt
) == IFN_GOACC_DIM_POS
)
2989 else if (gimple_code (stmt
) == GIMPLE_RETURN
)
2995 fprintf (dump_file
, "Unhandled stmt in entry/exit: ");
2996 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3001 if (ref_conflicts_with_region (gsi
, &ref
, ref_is_store
, region_bbs
,
3006 fprintf (dump_file
, "conflicts with entry/exit stmt: ");
3007 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3017 /* Find stores inside REGION_BBS and outside IN_LOOP_BBS, and guard them with
3018 gang_pos == 0, except when the stores are REDUCTION_STORES. Return true
3019 if any changes were made. */
3022 oacc_entry_exit_single_gang (bitmap in_loop_bbs
, vec
<basic_block
> region_bbs
,
3023 bitmap reduction_stores
)
3025 tree gang_pos
= NULL_TREE
;
3026 bool changed
= false;
3030 FOR_EACH_VEC_ELT (region_bbs
, i
, bb
)
3032 if (bitmap_bit_p (in_loop_bbs
, bb
->index
))
3035 gimple_stmt_iterator gsi
;
3036 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
3038 gimple
*stmt
= gsi_stmt (gsi
);
3040 if (!gimple_store_p (stmt
))
3042 /* Update gsi to point to next stmt. */
3047 if (bitmap_bit_p (reduction_stores
,
3048 SSA_NAME_VERSION (gimple_vdef (stmt
))))
3053 "skipped reduction store for single-gang"
3055 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3058 /* Update gsi to point to next stmt. */
3065 if (gang_pos
== NULL_TREE
)
3067 tree arg
= build_int_cst (integer_type_node
, GOMP_DIM_GANG
);
3069 = gimple_build_call_internal (IFN_GOACC_DIM_POS
, 1, arg
);
3070 gang_pos
= make_ssa_name (integer_type_node
);
3071 gimple_call_set_lhs (gang_single
, gang_pos
);
3072 gimple_stmt_iterator start
3073 = gsi_start_bb (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
3074 tree vuse
= ssa_default_def (cfun
, gimple_vop (cfun
));
3075 gimple_set_vuse (gang_single
, vuse
);
3076 gsi_insert_before (&start
, gang_single
, GSI_SAME_STMT
);
3082 "found store that needs single-gang neutering: ");
3083 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3087 /* Split block before store. */
3088 gimple_stmt_iterator gsi2
= gsi
;
3091 if (gsi_end_p (gsi2
))
3093 e
= split_block_after_labels (bb
);
3094 gsi2
= gsi_last_bb (bb
);
3097 e
= split_block (bb
, gsi_stmt (gsi2
));
3098 basic_block bb2
= e
->dest
;
3100 /* Split block after store. */
3101 gimple_stmt_iterator gsi3
= gsi_start_bb (bb2
);
3102 edge e2
= split_block (bb2
, gsi_stmt (gsi3
));
3103 basic_block bb3
= e2
->dest
;
3106 = gimple_build_cond (EQ_EXPR
, gang_pos
, integer_zero_node
,
3107 NULL_TREE
, NULL_TREE
);
3108 gsi_insert_after (&gsi2
, cond
, GSI_NEW_STMT
);
3110 edge e3
= make_edge (bb
, bb3
, EDGE_FALSE_VALUE
);
3111 e
->flags
= EDGE_TRUE_VALUE
;
3113 tree vdef
= gimple_vdef (stmt
);
3114 tree vuse
= gimple_vuse (stmt
);
3116 tree phi_res
= copy_ssa_name (vdef
);
3117 gphi
*new_phi
= create_phi_node (phi_res
, bb3
);
3118 replace_uses_by (vdef
, phi_res
);
3119 add_phi_arg (new_phi
, vuse
, e3
, UNKNOWN_LOCATION
);
3120 add_phi_arg (new_phi
, vdef
, e2
, UNKNOWN_LOCATION
);
3122 /* Update gsi to point to next stmt. */
3124 gsi
= gsi_start_bb (bb
);
3132 /* Return true if the statements before and after the LOOP can be executed in
3133 parallel with the function containing the loop. Resolve conflicting stores
3134 outside LOOP by guarding them such that only a single gang executes them. */
3137 oacc_entry_exit_ok (struct loop
*loop
,
3138 reduction_info_table_type
*reduction_list
)
3140 basic_block
*loop_bbs
= get_loop_body_in_dom_order (loop
);
3141 vec
<basic_block
> region_bbs
3142 = get_all_dominated_blocks (CDI_DOMINATORS
, ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3144 bitmap in_loop_bbs
= BITMAP_ALLOC (NULL
);
3145 bitmap_clear (in_loop_bbs
);
3146 for (unsigned int i
= 0; i
< loop
->num_nodes
; i
++)
3147 bitmap_set_bit (in_loop_bbs
, loop_bbs
[i
]->index
);
3149 bitmap reduction_stores
= BITMAP_ALLOC (NULL
);
3150 bool res
= oacc_entry_exit_ok_1 (in_loop_bbs
, region_bbs
, reduction_list
,
3155 bool changed
= oacc_entry_exit_single_gang (in_loop_bbs
, region_bbs
,
3159 free_dominance_info (CDI_DOMINATORS
);
3160 calculate_dominance_info (CDI_DOMINATORS
);
3166 BITMAP_FREE (in_loop_bbs
);
3167 BITMAP_FREE (reduction_stores
);
3172 /* Detect parallel loops and generate parallel code using libgomp
3173 primitives. Returns true if some loop was parallelized, false
3177 parallelize_loops (bool oacc_kernels_p
)
3179 unsigned n_threads
= flag_tree_parallelize_loops
;
3180 bool changed
= false;
3182 struct loop
*skip_loop
= NULL
;
3183 struct tree_niter_desc niter_desc
;
3184 struct obstack parloop_obstack
;
3185 HOST_WIDE_INT estimated
;
3186 source_location loop_loc
;
3188 /* Do not parallelize loops in the functions created by parallelization. */
3190 && parallelized_function_p (cfun
->decl
))
3193 /* Do not parallelize loops in offloaded functions. */
3195 && get_oacc_fn_attrib (cfun
->decl
) != NULL
)
3198 if (cfun
->has_nonlocal_label
)
3201 gcc_obstack_init (&parloop_obstack
);
3202 reduction_info_table_type
reduction_list (10);
3204 calculate_dominance_info (CDI_DOMINATORS
);
3206 FOR_EACH_LOOP (loop
, 0)
3208 if (loop
== skip_loop
)
3210 if (!loop
->in_oacc_kernels_region
3211 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3213 "Skipping loop %d as inner loop of parallelized loop\n",
3216 skip_loop
= loop
->inner
;
3222 reduction_list
.empty ();
3226 if (!loop
->in_oacc_kernels_region
)
3229 /* Don't try to parallelize inner loops in an oacc kernels region. */
3231 skip_loop
= loop
->inner
;
3233 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3235 "Trying loop %d with header bb %d in oacc kernels"
3236 " region\n", loop
->num
, loop
->header
->index
);
3239 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3241 fprintf (dump_file
, "Trying loop %d as candidate\n",loop
->num
);
3243 fprintf (dump_file
, "loop %d is not innermost\n",loop
->num
);
3245 fprintf (dump_file
, "loop %d is innermost\n",loop
->num
);
3248 /* If we use autopar in graphite pass, we use its marked dependency
3249 checking results. */
3250 if (flag_loop_parallelize_all
&& !loop
->can_be_parallel
)
3252 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3253 fprintf (dump_file
, "loop is not parallel according to graphite\n");
3257 if (!single_dom_exit (loop
))
3260 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3261 fprintf (dump_file
, "loop is !single_dom_exit\n");
3266 if (/* And of course, the loop must be parallelizable. */
3267 !can_duplicate_loop_p (loop
)
3268 || loop_has_blocks_with_irreducible_flag (loop
)
3269 || (loop_preheader_edge (loop
)->src
->flags
& BB_IRREDUCIBLE_LOOP
)
3270 /* FIXME: the check for vector phi nodes could be removed. */
3271 || loop_has_vector_phi_nodes (loop
))
3274 estimated
= estimated_stmt_executions_int (loop
);
3275 if (estimated
== -1)
3276 estimated
= max_stmt_executions_int (loop
);
3277 /* FIXME: Bypass this check as graphite doesn't update the
3278 count and frequency correctly now. */
3279 if (!flag_loop_parallelize_all
3281 && ((estimated
!= -1
3282 && estimated
<= (HOST_WIDE_INT
) n_threads
* MIN_PER_THREAD
)
3283 /* Do not bother with loops in cold areas. */
3284 || optimize_loop_nest_for_size_p (loop
)))
3287 if (!try_get_loop_niter (loop
, &niter_desc
))
3290 if (!try_create_reduction_list (loop
, &reduction_list
, oacc_kernels_p
))
3293 if (loop_has_phi_with_address_arg (loop
))
3296 if (!flag_loop_parallelize_all
3297 && !loop_parallel_p (loop
, &parloop_obstack
))
3301 && !oacc_entry_exit_ok (loop
, &reduction_list
))
3304 fprintf (dump_file
, "entry/exit not ok: FAILED\n");
3309 skip_loop
= loop
->inner
;
3310 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3313 fprintf (dump_file
, "parallelizing outer loop %d\n",loop
->header
->index
);
3315 fprintf (dump_file
, "parallelizing inner loop %d\n",loop
->header
->index
);
3316 loop_loc
= find_loop_location (loop
);
3317 if (loop_loc
!= UNKNOWN_LOCATION
)
3318 fprintf (dump_file
, "\nloop at %s:%d: ",
3319 LOCATION_FILE (loop_loc
), LOCATION_LINE (loop_loc
));
3322 gen_parallel_loop (loop
, &reduction_list
,
3323 n_threads
, &niter_desc
, oacc_kernels_p
);
3326 obstack_free (&parloop_obstack
, NULL
);
3328 /* Parallelization will cause new function calls to be inserted through
3329 which local variables will escape. Reset the points-to solution
3332 pt_solution_reset (&cfun
->gimple_df
->escaped
);
3337 /* Parallelization. */
3341 const pass_data pass_data_parallelize_loops
=
3343 GIMPLE_PASS
, /* type */
3344 "parloops", /* name */
3345 OPTGROUP_LOOP
, /* optinfo_flags */
3346 TV_TREE_PARALLELIZE_LOOPS
, /* tv_id */
3347 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3348 0, /* properties_provided */
3349 0, /* properties_destroyed */
3350 0, /* todo_flags_start */
3351 0, /* todo_flags_finish */
3354 class pass_parallelize_loops
: public gimple_opt_pass
3357 pass_parallelize_loops (gcc::context
*ctxt
)
3358 : gimple_opt_pass (pass_data_parallelize_loops
, ctxt
),
3359 oacc_kernels_p (false)
3362 /* opt_pass methods: */
3363 virtual bool gate (function
*) { return flag_tree_parallelize_loops
> 1; }
3364 virtual unsigned int execute (function
*);
3365 opt_pass
* clone () { return new pass_parallelize_loops (m_ctxt
); }
3366 void set_pass_param (unsigned int n
, bool param
)
3368 gcc_assert (n
== 0);
3369 oacc_kernels_p
= param
;
3373 bool oacc_kernels_p
;
3374 }; // class pass_parallelize_loops
3377 pass_parallelize_loops::execute (function
*fun
)
3379 tree nthreads
= builtin_decl_explicit (BUILT_IN_OMP_GET_NUM_THREADS
);
3380 if (nthreads
== NULL_TREE
)
3383 bool in_loop_pipeline
= scev_initialized_p ();
3384 if (!in_loop_pipeline
)
3385 loop_optimizer_init (LOOPS_NORMAL
3386 | LOOPS_HAVE_RECORDED_EXITS
);
3388 if (number_of_loops (fun
) <= 1)
3391 if (!in_loop_pipeline
)
3393 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
3397 unsigned int todo
= 0;
3398 if (parallelize_loops (oacc_kernels_p
))
3400 fun
->curr_properties
&= ~(PROP_gimple_eomp
);
3402 checking_verify_loop_structure ();
3404 todo
|= TODO_update_ssa
;
3407 if (!in_loop_pipeline
)
3410 loop_optimizer_finalize ();
3419 make_pass_parallelize_loops (gcc::context
*ctxt
)
3421 return new pass_parallelize_loops (ctxt
);