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 unlink_stmt_vdef (stmt
);
729 stmt
= gimple_build_nop ();
730 gsi_replace (gsi
, stmt
, false);
736 walk_gimple_op (stmt
, eliminate_local_variables_1
, &dta
.info
);
743 /* Eliminates the references to local variables from the single entry
744 single exit region between the ENTRY and EXIT edges.
747 1) Taking address of a local variable -- these are moved out of the
748 region (and temporary variable is created to hold the address if
751 2) Dereferencing a local variable -- these are replaced with indirect
755 eliminate_local_variables (edge entry
, edge exit
)
758 auto_vec
<basic_block
, 3> body
;
760 gimple_stmt_iterator gsi
;
761 bool has_debug_stmt
= false;
762 int_tree_htab_type
decl_address (10);
763 basic_block entry_bb
= entry
->src
;
764 basic_block exit_bb
= exit
->dest
;
766 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
768 FOR_EACH_VEC_ELT (body
, i
, bb
)
769 if (bb
!= entry_bb
&& bb
!= exit_bb
)
770 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
771 if (is_gimple_debug (gsi_stmt (gsi
)))
773 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
774 has_debug_stmt
= true;
777 eliminate_local_variables_stmt (entry
, &gsi
, &decl_address
);
780 FOR_EACH_VEC_ELT (body
, i
, bb
)
781 if (bb
!= entry_bb
&& bb
!= exit_bb
)
782 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
783 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
784 eliminate_local_variables_stmt (entry
, &gsi
, &decl_address
);
787 /* Returns true if expression EXPR is not defined between ENTRY and
788 EXIT, i.e. if all its operands are defined outside of the region. */
791 expr_invariant_in_region_p (edge entry
, edge exit
, tree expr
)
793 basic_block entry_bb
= entry
->src
;
794 basic_block exit_bb
= exit
->dest
;
797 if (is_gimple_min_invariant (expr
))
800 if (TREE_CODE (expr
) == SSA_NAME
)
802 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
804 && dominated_by_p (CDI_DOMINATORS
, def_bb
, entry_bb
)
805 && !dominated_by_p (CDI_DOMINATORS
, def_bb
, exit_bb
))
814 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
815 The copies are stored to NAME_COPIES, if NAME was already duplicated,
816 its duplicate stored in NAME_COPIES is returned.
818 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
819 duplicated, storing the copies in DECL_COPIES. */
822 separate_decls_in_region_name (tree name
, name_to_copy_table_type
*name_copies
,
823 int_tree_htab_type
*decl_copies
,
826 tree copy
, var
, var_copy
;
827 unsigned idx
, uid
, nuid
;
828 struct int_tree_map ielt
;
829 struct name_to_copy_elt elt
, *nelt
;
830 name_to_copy_elt
**slot
;
833 if (TREE_CODE (name
) != SSA_NAME
)
836 idx
= SSA_NAME_VERSION (name
);
838 slot
= name_copies
->find_slot_with_hash (&elt
, idx
,
839 copy_name_p
? INSERT
: NO_INSERT
);
841 return (*slot
)->new_name
;
845 copy
= duplicate_ssa_name (name
, NULL
);
846 nelt
= XNEW (struct name_to_copy_elt
);
848 nelt
->new_name
= copy
;
849 nelt
->field
= NULL_TREE
;
858 var
= SSA_NAME_VAR (name
);
862 uid
= DECL_UID (var
);
864 dslot
= decl_copies
->find_slot_with_hash (ielt
, uid
, INSERT
);
867 var_copy
= create_tmp_var (TREE_TYPE (var
), get_name (var
));
868 DECL_GIMPLE_REG_P (var_copy
) = DECL_GIMPLE_REG_P (var
);
870 dslot
->to
= var_copy
;
872 /* Ensure that when we meet this decl next time, we won't duplicate
874 nuid
= DECL_UID (var_copy
);
876 dslot
= decl_copies
->find_slot_with_hash (ielt
, nuid
, INSERT
);
877 gcc_assert (!dslot
->to
);
879 dslot
->to
= var_copy
;
882 var_copy
= dslot
->to
;
884 replace_ssa_name_symbol (copy
, var_copy
);
888 /* Finds the ssa names used in STMT that are defined outside the
889 region between ENTRY and EXIT and replaces such ssa names with
890 their duplicates. The duplicates are stored to NAME_COPIES. Base
891 decls of all ssa names used in STMT (including those defined in
892 LOOP) are replaced with the new temporary variables; the
893 replacement decls are stored in DECL_COPIES. */
896 separate_decls_in_region_stmt (edge entry
, edge exit
, gimple
*stmt
,
897 name_to_copy_table_type
*name_copies
,
898 int_tree_htab_type
*decl_copies
)
906 FOR_EACH_PHI_OR_STMT_DEF (def
, stmt
, oi
, SSA_OP_DEF
)
908 name
= DEF_FROM_PTR (def
);
909 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
910 copy
= separate_decls_in_region_name (name
, name_copies
, decl_copies
,
912 gcc_assert (copy
== name
);
915 FOR_EACH_PHI_OR_STMT_USE (use
, stmt
, oi
, SSA_OP_USE
)
917 name
= USE_FROM_PTR (use
);
918 if (TREE_CODE (name
) != SSA_NAME
)
921 copy_name_p
= expr_invariant_in_region_p (entry
, exit
, name
);
922 copy
= separate_decls_in_region_name (name
, name_copies
, decl_copies
,
928 /* Finds the ssa names used in STMT that are defined outside the
929 region between ENTRY and EXIT and replaces such ssa names with
930 their duplicates. The duplicates are stored to NAME_COPIES. Base
931 decls of all ssa names used in STMT (including those defined in
932 LOOP) are replaced with the new temporary variables; the
933 replacement decls are stored in DECL_COPIES. */
936 separate_decls_in_region_debug (gimple
*stmt
,
937 name_to_copy_table_type
*name_copies
,
938 int_tree_htab_type
*decl_copies
)
943 struct int_tree_map ielt
;
944 struct name_to_copy_elt elt
;
945 name_to_copy_elt
**slot
;
948 if (gimple_debug_bind_p (stmt
))
949 var
= gimple_debug_bind_get_var (stmt
);
950 else if (gimple_debug_source_bind_p (stmt
))
951 var
= gimple_debug_source_bind_get_var (stmt
);
954 if (TREE_CODE (var
) == DEBUG_EXPR_DECL
|| TREE_CODE (var
) == LABEL_DECL
)
956 gcc_assert (DECL_P (var
) && SSA_VAR_P (var
));
957 ielt
.uid
= DECL_UID (var
);
958 dslot
= decl_copies
->find_slot_with_hash (ielt
, ielt
.uid
, NO_INSERT
);
961 if (gimple_debug_bind_p (stmt
))
962 gimple_debug_bind_set_var (stmt
, dslot
->to
);
963 else if (gimple_debug_source_bind_p (stmt
))
964 gimple_debug_source_bind_set_var (stmt
, dslot
->to
);
966 FOR_EACH_PHI_OR_STMT_USE (use
, stmt
, oi
, SSA_OP_USE
)
968 name
= USE_FROM_PTR (use
);
969 if (TREE_CODE (name
) != SSA_NAME
)
972 elt
.version
= SSA_NAME_VERSION (name
);
973 slot
= name_copies
->find_slot_with_hash (&elt
, elt
.version
, NO_INSERT
);
976 gimple_debug_bind_reset_value (stmt
);
981 SET_USE (use
, (*slot
)->new_name
);
987 /* Callback for htab_traverse. Adds a field corresponding to the reduction
988 specified in SLOT. The type is passed in DATA. */
991 add_field_for_reduction (reduction_info
**slot
, tree type
)
994 struct reduction_info
*const red
= *slot
;
995 tree var
= reduc_stmt_res (red
->reduc_stmt
);
996 tree field
= build_decl (gimple_location (red
->reduc_stmt
), FIELD_DECL
,
997 SSA_NAME_IDENTIFIER (var
), TREE_TYPE (var
));
999 insert_field_into_struct (type
, field
);
1006 /* Callback for htab_traverse. Adds a field corresponding to a ssa name
1007 described in SLOT. The type is passed in DATA. */
1010 add_field_for_name (name_to_copy_elt
**slot
, tree type
)
1012 struct name_to_copy_elt
*const elt
= *slot
;
1013 tree name
= ssa_name (elt
->version
);
1014 tree field
= build_decl (UNKNOWN_LOCATION
,
1015 FIELD_DECL
, SSA_NAME_IDENTIFIER (name
),
1018 insert_field_into_struct (type
, field
);
1024 /* Callback for htab_traverse. A local result is the intermediate result
1025 computed by a single
1026 thread, or the initial value in case no iteration was executed.
1027 This function creates a phi node reflecting these values.
1028 The phi's result will be stored in NEW_PHI field of the
1029 reduction's data structure. */
1032 create_phi_for_local_result (reduction_info
**slot
, struct loop
*loop
)
1034 struct reduction_info
*const reduc
= *slot
;
1037 basic_block store_bb
, continue_bb
;
1039 source_location locus
;
1041 /* STORE_BB is the block where the phi
1042 should be stored. It is the destination of the loop exit.
1043 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
1044 continue_bb
= single_pred (loop
->latch
);
1045 store_bb
= FALLTHRU_EDGE (continue_bb
)->dest
;
1047 /* STORE_BB has two predecessors. One coming from the loop
1048 (the reduction's result is computed at the loop),
1049 and another coming from a block preceding the loop,
1051 are executed (the initial value should be taken). */
1052 if (EDGE_PRED (store_bb
, 0) == FALLTHRU_EDGE (continue_bb
))
1053 e
= EDGE_PRED (store_bb
, 1);
1055 e
= EDGE_PRED (store_bb
, 0);
1056 tree lhs
= reduc_stmt_res (reduc
->reduc_stmt
);
1057 local_res
= copy_ssa_name (lhs
);
1058 locus
= gimple_location (reduc
->reduc_stmt
);
1059 new_phi
= create_phi_node (local_res
, store_bb
);
1060 add_phi_arg (new_phi
, reduc
->init
, e
, locus
);
1061 add_phi_arg (new_phi
, lhs
, FALLTHRU_EDGE (continue_bb
), locus
);
1062 reduc
->new_phi
= new_phi
;
1072 basic_block store_bb
;
1073 basic_block load_bb
;
1076 /* Callback for htab_traverse. Create an atomic instruction for the
1077 reduction described in SLOT.
1078 DATA annotates the place in memory the atomic operation relates to,
1079 and the basic block it needs to be generated in. */
1082 create_call_for_reduction_1 (reduction_info
**slot
, struct clsn_data
*clsn_data
)
1084 struct reduction_info
*const reduc
= *slot
;
1085 gimple_stmt_iterator gsi
;
1086 tree type
= TREE_TYPE (PHI_RESULT (reduc
->reduc_phi
));
1091 tree t
, addr
, ref
, x
;
1092 tree tmp_load
, name
;
1095 if (reduc
->reduc_addr
== NULL_TREE
)
1097 load_struct
= build_simple_mem_ref (clsn_data
->load
);
1098 t
= build3 (COMPONENT_REF
, type
, load_struct
, reduc
->field
, NULL_TREE
);
1100 addr
= build_addr (t
);
1104 /* Set the address for the atomic store. */
1105 addr
= reduc
->reduc_addr
;
1107 /* Remove the non-atomic store '*addr = sum'. */
1108 tree res
= PHI_RESULT (reduc
->keep_res
);
1109 use_operand_p use_p
;
1111 bool single_use_p
= single_imm_use (res
, &use_p
, &stmt
);
1112 gcc_assert (single_use_p
);
1113 replace_uses_by (gimple_vdef (stmt
),
1114 gimple_vuse (stmt
));
1115 gimple_stmt_iterator gsi
= gsi_for_stmt (stmt
);
1116 gsi_remove (&gsi
, true);
1119 /* Create phi node. */
1120 bb
= clsn_data
->load_bb
;
1122 gsi
= gsi_last_bb (bb
);
1123 e
= split_block (bb
, gsi_stmt (gsi
));
1126 tmp_load
= create_tmp_var (TREE_TYPE (TREE_TYPE (addr
)));
1127 tmp_load
= make_ssa_name (tmp_load
);
1128 load
= gimple_build_omp_atomic_load (tmp_load
, addr
);
1129 SSA_NAME_DEF_STMT (tmp_load
) = load
;
1130 gsi
= gsi_start_bb (new_bb
);
1131 gsi_insert_after (&gsi
, load
, GSI_NEW_STMT
);
1133 e
= split_block (new_bb
, load
);
1135 gsi
= gsi_start_bb (new_bb
);
1137 x
= fold_build2 (reduc
->reduction_code
,
1138 TREE_TYPE (PHI_RESULT (reduc
->new_phi
)), ref
,
1139 PHI_RESULT (reduc
->new_phi
));
1141 name
= force_gimple_operand_gsi (&gsi
, x
, true, NULL_TREE
, true,
1142 GSI_CONTINUE_LINKING
);
1144 gsi_insert_after (&gsi
, gimple_build_omp_atomic_store (name
), GSI_NEW_STMT
);
1148 /* Create the atomic operation at the join point of the threads.
1149 REDUCTION_LIST describes the reductions in the LOOP.
1150 LD_ST_DATA describes the shared data structure where
1151 shared data is stored in and loaded from. */
1153 create_call_for_reduction (struct loop
*loop
,
1154 reduction_info_table_type
*reduction_list
,
1155 struct clsn_data
*ld_st_data
)
1157 reduction_list
->traverse
<struct loop
*, create_phi_for_local_result
> (loop
);
1158 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
1159 basic_block continue_bb
= single_pred (loop
->latch
);
1160 ld_st_data
->load_bb
= FALLTHRU_EDGE (continue_bb
)->dest
;
1162 ->traverse
<struct clsn_data
*, create_call_for_reduction_1
> (ld_st_data
);
1165 /* Callback for htab_traverse. Loads the final reduction value at the
1166 join point of all threads, and inserts it in the right place. */
1169 create_loads_for_reductions (reduction_info
**slot
, struct clsn_data
*clsn_data
)
1171 struct reduction_info
*const red
= *slot
;
1173 gimple_stmt_iterator gsi
;
1174 tree type
= TREE_TYPE (reduc_stmt_res (red
->reduc_stmt
));
1179 /* If there's no exit phi, the result of the reduction is unused. */
1180 if (red
->keep_res
== NULL
)
1183 gsi
= gsi_after_labels (clsn_data
->load_bb
);
1184 load_struct
= build_simple_mem_ref (clsn_data
->load
);
1185 load_struct
= build3 (COMPONENT_REF
, type
, load_struct
, red
->field
,
1189 name
= PHI_RESULT (red
->keep_res
);
1190 stmt
= gimple_build_assign (name
, x
);
1192 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1194 for (gsi
= gsi_start_phis (gimple_bb (red
->keep_res
));
1195 !gsi_end_p (gsi
); gsi_next (&gsi
))
1196 if (gsi_stmt (gsi
) == red
->keep_res
)
1198 remove_phi_node (&gsi
, false);
1204 /* Load the reduction result that was stored in LD_ST_DATA.
1205 REDUCTION_LIST describes the list of reductions that the
1206 loads should be generated for. */
1208 create_final_loads_for_reduction (reduction_info_table_type
*reduction_list
,
1209 struct clsn_data
*ld_st_data
)
1211 gimple_stmt_iterator gsi
;
1215 gsi
= gsi_after_labels (ld_st_data
->load_bb
);
1216 t
= build_fold_addr_expr (ld_st_data
->store
);
1217 stmt
= gimple_build_assign (ld_st_data
->load
, t
);
1219 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1222 ->traverse
<struct clsn_data
*, create_loads_for_reductions
> (ld_st_data
);
1226 /* Callback for htab_traverse. Store the neutral value for the
1227 particular reduction's operation, e.g. 0 for PLUS_EXPR,
1228 1 for MULT_EXPR, etc. into the reduction field.
1229 The reduction is specified in SLOT. The store information is
1233 create_stores_for_reduction (reduction_info
**slot
, struct clsn_data
*clsn_data
)
1235 struct reduction_info
*const red
= *slot
;
1238 gimple_stmt_iterator gsi
;
1239 tree type
= TREE_TYPE (reduc_stmt_res (red
->reduc_stmt
));
1241 gsi
= gsi_last_bb (clsn_data
->store_bb
);
1242 t
= build3 (COMPONENT_REF
, type
, clsn_data
->store
, red
->field
, NULL_TREE
);
1243 stmt
= gimple_build_assign (t
, red
->initial_value
);
1244 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1249 /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
1250 store to a field of STORE in STORE_BB for the ssa name and its duplicate
1251 specified in SLOT. */
1254 create_loads_and_stores_for_name (name_to_copy_elt
**slot
,
1255 struct clsn_data
*clsn_data
)
1257 struct name_to_copy_elt
*const elt
= *slot
;
1260 gimple_stmt_iterator gsi
;
1261 tree type
= TREE_TYPE (elt
->new_name
);
1264 gsi
= gsi_last_bb (clsn_data
->store_bb
);
1265 t
= build3 (COMPONENT_REF
, type
, clsn_data
->store
, elt
->field
, NULL_TREE
);
1266 stmt
= gimple_build_assign (t
, ssa_name (elt
->version
));
1267 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1269 gsi
= gsi_last_bb (clsn_data
->load_bb
);
1270 load_struct
= build_simple_mem_ref (clsn_data
->load
);
1271 t
= build3 (COMPONENT_REF
, type
, load_struct
, elt
->field
, NULL_TREE
);
1272 stmt
= gimple_build_assign (elt
->new_name
, t
);
1273 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1278 /* Moves all the variables used in LOOP and defined outside of it (including
1279 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1280 name) to a structure created for this purpose. The code
1288 is transformed this way:
1303 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1304 pointer `new' is intentionally not initialized (the loop will be split to a
1305 separate function later, and `new' will be initialized from its arguments).
1306 LD_ST_DATA holds information about the shared data structure used to pass
1307 information among the threads. It is initialized here, and
1308 gen_parallel_loop will pass it to create_call_for_reduction that
1309 needs this information. REDUCTION_LIST describes the reductions
1313 separate_decls_in_region (edge entry
, edge exit
,
1314 reduction_info_table_type
*reduction_list
,
1315 tree
*arg_struct
, tree
*new_arg_struct
,
1316 struct clsn_data
*ld_st_data
)
1319 basic_block bb1
= split_edge (entry
);
1320 basic_block bb0
= single_pred (bb1
);
1321 name_to_copy_table_type
name_copies (10);
1322 int_tree_htab_type
decl_copies (10);
1324 tree type
, type_name
, nvar
;
1325 gimple_stmt_iterator gsi
;
1326 struct clsn_data clsn_data
;
1327 auto_vec
<basic_block
, 3> body
;
1329 basic_block entry_bb
= bb1
;
1330 basic_block exit_bb
= exit
->dest
;
1331 bool has_debug_stmt
= false;
1333 entry
= single_succ_edge (entry_bb
);
1334 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
1336 FOR_EACH_VEC_ELT (body
, i
, bb
)
1338 if (bb
!= entry_bb
&& bb
!= exit_bb
)
1340 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1341 separate_decls_in_region_stmt (entry
, exit
, gsi_stmt (gsi
),
1342 &name_copies
, &decl_copies
);
1344 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1346 gimple
*stmt
= gsi_stmt (gsi
);
1348 if (is_gimple_debug (stmt
))
1349 has_debug_stmt
= true;
1351 separate_decls_in_region_stmt (entry
, exit
, stmt
,
1352 &name_copies
, &decl_copies
);
1357 /* Now process debug bind stmts. We must not create decls while
1358 processing debug stmts, so we defer their processing so as to
1359 make sure we will have debug info for as many variables as
1360 possible (all of those that were dealt with in the loop above),
1361 and discard those for which we know there's nothing we can
1364 FOR_EACH_VEC_ELT (body
, i
, bb
)
1365 if (bb
!= entry_bb
&& bb
!= exit_bb
)
1367 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
1369 gimple
*stmt
= gsi_stmt (gsi
);
1371 if (is_gimple_debug (stmt
))
1373 if (separate_decls_in_region_debug (stmt
, &name_copies
,
1376 gsi_remove (&gsi
, true);
1385 if (name_copies
.elements () == 0 && reduction_list
->elements () == 0)
1387 /* It may happen that there is nothing to copy (if there are only
1388 loop carried and external variables in the loop). */
1390 *new_arg_struct
= NULL
;
1394 /* Create the type for the structure to store the ssa names to. */
1395 type
= lang_hooks
.types
.make_type (RECORD_TYPE
);
1396 type_name
= build_decl (UNKNOWN_LOCATION
,
1397 TYPE_DECL
, create_tmp_var_name (".paral_data"),
1399 TYPE_NAME (type
) = type_name
;
1401 name_copies
.traverse
<tree
, add_field_for_name
> (type
);
1402 if (reduction_list
&& reduction_list
->elements () > 0)
1404 /* Create the fields for reductions. */
1405 reduction_list
->traverse
<tree
, add_field_for_reduction
> (type
);
1409 /* Create the loads and stores. */
1410 *arg_struct
= create_tmp_var (type
, ".paral_data_store");
1411 nvar
= create_tmp_var (build_pointer_type (type
), ".paral_data_load");
1412 *new_arg_struct
= make_ssa_name (nvar
);
1414 ld_st_data
->store
= *arg_struct
;
1415 ld_st_data
->load
= *new_arg_struct
;
1416 ld_st_data
->store_bb
= bb0
;
1417 ld_st_data
->load_bb
= bb1
;
1420 .traverse
<struct clsn_data
*, create_loads_and_stores_for_name
>
1423 /* Load the calculation from memory (after the join of the threads). */
1425 if (reduction_list
&& reduction_list
->elements () > 0)
1428 ->traverse
<struct clsn_data
*, create_stores_for_reduction
>
1430 clsn_data
.load
= make_ssa_name (nvar
);
1431 clsn_data
.load_bb
= exit
->dest
;
1432 clsn_data
.store
= ld_st_data
->store
;
1433 create_final_loads_for_reduction (reduction_list
, &clsn_data
);
1438 /* Returns true if FN was created to run in parallel. */
1441 parallelized_function_p (tree fndecl
)
1443 cgraph_node
*node
= cgraph_node::get (fndecl
);
1444 gcc_assert (node
!= NULL
);
1445 return node
->parallelized_function
;
1448 /* Creates and returns an empty function that will receive the body of
1449 a parallelized loop. */
1452 create_loop_fn (location_t loc
)
1456 tree decl
, type
, name
, t
;
1457 struct function
*act_cfun
= cfun
;
1458 static unsigned loopfn_num
;
1460 loc
= LOCATION_LOCUS (loc
);
1461 snprintf (buf
, 100, "%s.$loopfn", current_function_name ());
1462 ASM_FORMAT_PRIVATE_NAME (tname
, buf
, loopfn_num
++);
1463 clean_symbol_name (tname
);
1464 name
= get_identifier (tname
);
1465 type
= build_function_type_list (void_type_node
, ptr_type_node
, NULL_TREE
);
1467 decl
= build_decl (loc
, FUNCTION_DECL
, name
, type
);
1468 TREE_STATIC (decl
) = 1;
1469 TREE_USED (decl
) = 1;
1470 DECL_ARTIFICIAL (decl
) = 1;
1471 DECL_IGNORED_P (decl
) = 0;
1472 TREE_PUBLIC (decl
) = 0;
1473 DECL_UNINLINABLE (decl
) = 1;
1474 DECL_EXTERNAL (decl
) = 0;
1475 DECL_CONTEXT (decl
) = NULL_TREE
;
1476 DECL_INITIAL (decl
) = make_node (BLOCK
);
1478 t
= build_decl (loc
, RESULT_DECL
, NULL_TREE
, void_type_node
);
1479 DECL_ARTIFICIAL (t
) = 1;
1480 DECL_IGNORED_P (t
) = 1;
1481 DECL_RESULT (decl
) = t
;
1483 t
= build_decl (loc
, PARM_DECL
, get_identifier (".paral_data_param"),
1485 DECL_ARTIFICIAL (t
) = 1;
1486 DECL_ARG_TYPE (t
) = ptr_type_node
;
1487 DECL_CONTEXT (t
) = decl
;
1489 DECL_ARGUMENTS (decl
) = t
;
1491 allocate_struct_function (decl
, false);
1493 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1495 set_cfun (act_cfun
);
1500 /* Replace uses of NAME by VAL in block BB. */
1503 replace_uses_in_bb_by (tree name
, tree val
, basic_block bb
)
1506 imm_use_iterator imm_iter
;
1508 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, name
)
1510 if (gimple_bb (use_stmt
) != bb
)
1513 use_operand_p use_p
;
1514 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1515 SET_USE (use_p
, val
);
1519 /* Do transformation from:
1526 ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1527 sum_a = PHI <sum_init (preheader), sum_b (latch)>
1531 sum_b = sum_a + sum_update
1539 ivtmp_b = ivtmp_a + 1;
1543 sum_z = PHI <sum_b (cond[1]), ...>
1545 [1] Where <bb cond> is single_pred (bb latch); In the simplest case,
1555 ivtmp_a = PHI <ivtmp_c (latch)>
1556 sum_a = PHI <sum_c (latch)>
1560 sum_b = sum_a + sum_update
1565 ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1566 sum_c = PHI <sum_init (preheader), sum_b (latch)>
1567 if (ivtmp_c < n + 1)
1573 ivtmp_b = ivtmp_a + 1;
1577 sum_y = PHI <sum_c (newheader)>
1580 sum_z = PHI <sum_y (newexit), ...>
1583 In unified diff format:
1588 + goto <bb newheader>
1591 - ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1592 - sum_a = PHI <sum_init (preheader), sum_b (latch)>
1593 + ivtmp_a = PHI <ivtmp_c (latch)>
1594 + sum_a = PHI <sum_c (latch)>
1598 sum_b = sum_a + sum_update
1605 + ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1606 + sum_c = PHI <sum_init (preheader), sum_b (latch)>
1607 + if (ivtmp_c < n + 1)
1613 ivtmp_b = ivtmp_a + 1;
1615 + goto <bb newheader>
1618 + sum_y = PHI <sum_c (newheader)>
1621 - sum_z = PHI <sum_b (cond[1]), ...>
1622 + sum_z = PHI <sum_y (newexit), ...>
1624 Note: the example does not show any virtual phis, but these are handled more
1625 or less as reductions.
1628 Moves the exit condition of LOOP to the beginning of its header.
1629 REDUCTION_LIST describes the reductions in LOOP. BOUND is the new loop
1633 transform_to_exit_first_loop_alt (struct loop
*loop
,
1634 reduction_info_table_type
*reduction_list
,
1637 basic_block header
= loop
->header
;
1638 basic_block latch
= loop
->latch
;
1639 edge exit
= single_dom_exit (loop
);
1640 basic_block exit_block
= exit
->dest
;
1641 gcond
*cond_stmt
= as_a
<gcond
*> (last_stmt (exit
->src
));
1642 tree control
= gimple_cond_lhs (cond_stmt
);
1645 /* Rewriting virtuals into loop-closed ssa normal form makes this
1646 transformation simpler. It also ensures that the virtuals are in
1647 loop-closed ssa normal from after the transformation, which is required by
1648 create_parallel_loop. */
1649 rewrite_virtuals_into_loop_closed_ssa (loop
);
1651 /* Create the new_header block. */
1652 basic_block new_header
= split_block_before_cond_jump (exit
->src
);
1653 edge edge_at_split
= single_pred_edge (new_header
);
1655 /* Redirect entry edge to new_header. */
1656 edge entry
= loop_preheader_edge (loop
);
1657 e
= redirect_edge_and_branch (entry
, new_header
);
1658 gcc_assert (e
== entry
);
1660 /* Redirect post_inc_edge to new_header. */
1661 edge post_inc_edge
= single_succ_edge (latch
);
1662 e
= redirect_edge_and_branch (post_inc_edge
, new_header
);
1663 gcc_assert (e
== post_inc_edge
);
1665 /* Redirect post_cond_edge to header. */
1666 edge post_cond_edge
= single_pred_edge (latch
);
1667 e
= redirect_edge_and_branch (post_cond_edge
, header
);
1668 gcc_assert (e
== post_cond_edge
);
1670 /* Redirect edge_at_split to latch. */
1671 e
= redirect_edge_and_branch (edge_at_split
, latch
);
1672 gcc_assert (e
== edge_at_split
);
1674 /* Set the new loop bound. */
1675 gimple_cond_set_rhs (cond_stmt
, bound
);
1676 update_stmt (cond_stmt
);
1678 /* Repair the ssa. */
1679 vec
<edge_var_map
> *v
= redirect_edge_var_map_vector (post_inc_edge
);
1683 for (gsi
= gsi_start_phis (header
), i
= 0;
1684 !gsi_end_p (gsi
) && v
->iterate (i
, &vm
);
1685 gsi_next (&gsi
), i
++)
1687 gphi
*phi
= gsi
.phi ();
1688 tree res_a
= PHI_RESULT (phi
);
1690 /* Create new phi. */
1691 tree res_c
= copy_ssa_name (res_a
, phi
);
1692 gphi
*nphi
= create_phi_node (res_c
, new_header
);
1694 /* Replace ivtmp_a with ivtmp_c in condition 'if (ivtmp_a < n)'. */
1695 replace_uses_in_bb_by (res_a
, res_c
, new_header
);
1697 /* Replace ivtmp/sum_b with ivtmp/sum_c in header phi. */
1698 add_phi_arg (phi
, res_c
, post_cond_edge
, UNKNOWN_LOCATION
);
1700 /* Replace sum_b with sum_c in exit phi. */
1701 tree res_b
= redirect_edge_var_map_def (vm
);
1702 replace_uses_in_bb_by (res_b
, res_c
, exit_block
);
1704 struct reduction_info
*red
= reduction_phi (reduction_list
, phi
);
1705 gcc_assert (virtual_operand_p (res_a
)
1711 /* Register the new reduction phi. */
1712 red
->reduc_phi
= nphi
;
1713 gimple_set_uid (red
->reduc_phi
, red
->reduc_version
);
1716 gcc_assert (gsi_end_p (gsi
) && !v
->iterate (i
, &vm
));
1718 /* Set the preheader argument of the new phis to ivtmp/sum_init. */
1719 flush_pending_stmts (entry
);
1721 /* Set the latch arguments of the new phis to ivtmp/sum_b. */
1722 flush_pending_stmts (post_inc_edge
);
1725 basic_block new_exit_block
= NULL
;
1726 if (!single_pred_p (exit
->dest
))
1728 /* Create a new empty exit block, inbetween the new loop header and the
1729 old exit block. The function separate_decls_in_region needs this block
1730 to insert code that is active on loop exit, but not any other path. */
1731 new_exit_block
= split_edge (exit
);
1734 /* Insert and register the reduction exit phis. */
1735 for (gphi_iterator gsi
= gsi_start_phis (exit_block
);
1739 gphi
*phi
= gsi
.phi ();
1741 tree res_z
= PHI_RESULT (phi
);
1744 if (new_exit_block
!= NULL
)
1746 /* Now that we have a new exit block, duplicate the phi of the old
1747 exit block in the new exit block to preserve loop-closed ssa. */
1748 edge succ_new_exit_block
= single_succ_edge (new_exit_block
);
1749 edge pred_new_exit_block
= single_pred_edge (new_exit_block
);
1750 tree res_y
= copy_ssa_name (res_z
, phi
);
1751 nphi
= create_phi_node (res_y
, new_exit_block
);
1752 res_c
= PHI_ARG_DEF_FROM_EDGE (phi
, succ_new_exit_block
);
1753 add_phi_arg (nphi
, res_c
, pred_new_exit_block
, UNKNOWN_LOCATION
);
1754 add_phi_arg (phi
, res_y
, succ_new_exit_block
, UNKNOWN_LOCATION
);
1757 res_c
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1759 if (virtual_operand_p (res_z
))
1762 gimple
*reduc_phi
= SSA_NAME_DEF_STMT (res_c
);
1763 struct reduction_info
*red
= reduction_phi (reduction_list
, reduc_phi
);
1765 red
->keep_res
= (nphi
!= NULL
1770 /* We're going to cancel the loop at the end of gen_parallel_loop, but until
1771 then we're still using some fields, so only bother about fields that are
1772 still used: header and latch.
1773 The loop has a new header bb, so we update it. The latch bb stays the
1775 loop
->header
= new_header
;
1777 /* Recalculate dominance info. */
1778 free_dominance_info (CDI_DOMINATORS
);
1779 calculate_dominance_info (CDI_DOMINATORS
);
1781 checking_verify_ssa (true, true);
1784 /* Tries to moves the exit condition of LOOP to the beginning of its header
1785 without duplication of the loop body. NIT is the number of iterations of the
1786 loop. REDUCTION_LIST describes the reductions in LOOP. Return true if
1787 transformation is successful. */
1790 try_transform_to_exit_first_loop_alt (struct loop
*loop
,
1791 reduction_info_table_type
*reduction_list
,
1794 /* Check whether the latch contains a single statement. */
1795 if (!gimple_seq_nondebug_singleton_p (bb_seq (loop
->latch
)))
1798 /* Check whether the latch contains no phis. */
1799 if (phi_nodes (loop
->latch
) != NULL
)
1802 /* Check whether the latch contains the loop iv increment. */
1803 edge back
= single_succ_edge (loop
->latch
);
1804 edge exit
= single_dom_exit (loop
);
1805 gcond
*cond_stmt
= as_a
<gcond
*> (last_stmt (exit
->src
));
1806 tree control
= gimple_cond_lhs (cond_stmt
);
1807 gphi
*phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (control
));
1808 tree inc_res
= gimple_phi_arg_def (phi
, back
->dest_idx
);
1809 if (gimple_bb (SSA_NAME_DEF_STMT (inc_res
)) != loop
->latch
)
1812 /* Check whether there's no code between the loop condition and the latch. */
1813 if (!single_pred_p (loop
->latch
)
1814 || single_pred (loop
->latch
) != exit
->src
)
1817 tree alt_bound
= NULL_TREE
;
1818 tree nit_type
= TREE_TYPE (nit
);
1820 /* Figure out whether nit + 1 overflows. */
1821 if (TREE_CODE (nit
) == INTEGER_CST
)
1823 if (!tree_int_cst_equal (nit
, TYPE_MAXVAL (nit_type
)))
1825 alt_bound
= fold_build2_loc (UNKNOWN_LOCATION
, PLUS_EXPR
, nit_type
,
1826 nit
, build_one_cst (nit_type
));
1828 gcc_assert (TREE_CODE (alt_bound
) == INTEGER_CST
);
1829 transform_to_exit_first_loop_alt (loop
, reduction_list
, alt_bound
);
1834 /* Todo: Figure out if we can trigger this, if it's worth to handle
1835 optimally, and if we can handle it optimally. */
1840 gcc_assert (TREE_CODE (nit
) == SSA_NAME
);
1842 /* Variable nit is the loop bound as returned by canonicalize_loop_ivs, for an
1843 iv with base 0 and step 1 that is incremented in the latch, like this:
1846 # iv_1 = PHI <0 (preheader), iv_2 (latch)>
1857 The range of iv_1 is [0, nit]. The latch edge is taken for
1858 iv_1 == [0, nit - 1] and the exit edge is taken for iv_1 == nit. So the
1859 number of latch executions is equal to nit.
1861 The function max_loop_iterations gives us the maximum number of latch
1862 executions, so it gives us the maximum value of nit. */
1864 if (!max_loop_iterations (loop
, &nit_max
))
1867 /* Check if nit + 1 overflows. */
1868 widest_int type_max
= wi::to_widest (TYPE_MAXVAL (nit_type
));
1869 if (!wi::lts_p (nit_max
, type_max
))
1872 gimple
*def
= SSA_NAME_DEF_STMT (nit
);
1874 /* Try to find nit + 1, in the form of n in an assignment nit = n - 1. */
1876 && is_gimple_assign (def
)
1877 && gimple_assign_rhs_code (def
) == PLUS_EXPR
)
1879 tree op1
= gimple_assign_rhs1 (def
);
1880 tree op2
= gimple_assign_rhs2 (def
);
1881 if (integer_minus_onep (op1
))
1883 else if (integer_minus_onep (op2
))
1887 /* If not found, insert nit + 1. */
1888 if (alt_bound
== NULL_TREE
)
1890 alt_bound
= fold_build2 (PLUS_EXPR
, nit_type
, nit
,
1891 build_int_cst_type (nit_type
, 1));
1893 gimple_stmt_iterator gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
1896 = force_gimple_operand_gsi (&gsi
, alt_bound
, true, NULL_TREE
, false,
1897 GSI_CONTINUE_LINKING
);
1900 transform_to_exit_first_loop_alt (loop
, reduction_list
, alt_bound
);
1904 /* Moves the exit condition of LOOP to the beginning of its header. NIT is the
1905 number of iterations of the loop. REDUCTION_LIST describes the reductions in
1909 transform_to_exit_first_loop (struct loop
*loop
,
1910 reduction_info_table_type
*reduction_list
,
1913 basic_block
*bbs
, *nbbs
, ex_bb
, orig_header
;
1916 edge exit
= single_dom_exit (loop
), hpred
;
1917 tree control
, control_name
, res
, t
;
1920 gcond
*cond_stmt
, *cond_nit
;
1923 split_block_after_labels (loop
->header
);
1924 orig_header
= single_succ (loop
->header
);
1925 hpred
= single_succ_edge (loop
->header
);
1927 cond_stmt
= as_a
<gcond
*> (last_stmt (exit
->src
));
1928 control
= gimple_cond_lhs (cond_stmt
);
1929 gcc_assert (gimple_cond_rhs (cond_stmt
) == nit
);
1931 /* Make sure that we have phi nodes on exit for all loop header phis
1932 (create_parallel_loop requires that). */
1933 for (gphi_iterator gsi
= gsi_start_phis (loop
->header
);
1938 res
= PHI_RESULT (phi
);
1939 t
= copy_ssa_name (res
, phi
);
1940 SET_PHI_RESULT (phi
, t
);
1941 nphi
= create_phi_node (res
, orig_header
);
1942 add_phi_arg (nphi
, t
, hpred
, UNKNOWN_LOCATION
);
1946 gimple_cond_set_lhs (cond_stmt
, t
);
1947 update_stmt (cond_stmt
);
1952 bbs
= get_loop_body_in_dom_order (loop
);
1954 for (n
= 0; bbs
[n
] != exit
->src
; n
++)
1956 nbbs
= XNEWVEC (basic_block
, n
);
1957 ok
= gimple_duplicate_sese_tail (single_succ_edge (loop
->header
), exit
,
1964 /* Other than reductions, the only gimple reg that should be copied
1965 out of the loop is the control variable. */
1966 exit
= single_dom_exit (loop
);
1967 control_name
= NULL_TREE
;
1968 for (gphi_iterator gsi
= gsi_start_phis (ex_bb
);
1972 res
= PHI_RESULT (phi
);
1973 if (virtual_operand_p (res
))
1979 /* Check if it is a part of reduction. If it is,
1980 keep the phi at the reduction's keep_res field. The
1981 PHI_RESULT of this phi is the resulting value of the reduction
1982 variable when exiting the loop. */
1984 if (reduction_list
->elements () > 0)
1986 struct reduction_info
*red
;
1988 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1989 red
= reduction_phi (reduction_list
, SSA_NAME_DEF_STMT (val
));
1992 red
->keep_res
= phi
;
1997 gcc_assert (control_name
== NULL_TREE
1998 && SSA_NAME_VAR (res
) == SSA_NAME_VAR (control
));
2000 remove_phi_node (&gsi
, false);
2002 gcc_assert (control_name
!= NULL_TREE
);
2004 /* Initialize the control variable to number of iterations
2005 according to the rhs of the exit condition. */
2006 gimple_stmt_iterator gsi
= gsi_after_labels (ex_bb
);
2007 cond_nit
= as_a
<gcond
*> (last_stmt (exit
->src
));
2008 nit_1
= gimple_cond_rhs (cond_nit
);
2009 nit_1
= force_gimple_operand_gsi (&gsi
,
2010 fold_convert (TREE_TYPE (control_name
), nit_1
),
2011 false, NULL_TREE
, false, GSI_SAME_STMT
);
2012 stmt
= gimple_build_assign (control_name
, nit_1
);
2013 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
2016 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
2017 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
2018 NEW_DATA is the variable that should be initialized from the argument
2019 of LOOP_FN. N_THREADS is the requested number of threads. */
2022 create_parallel_loop (struct loop
*loop
, tree loop_fn
, tree data
,
2023 tree new_data
, unsigned n_threads
, location_t loc
,
2024 bool oacc_kernels_p
)
2026 gimple_stmt_iterator gsi
;
2027 basic_block for_bb
, ex_bb
, continue_bb
;
2029 gomp_parallel
*omp_par_stmt
;
2030 gimple
*omp_return_stmt1
, *omp_return_stmt2
;
2034 gomp_continue
*omp_cont_stmt
;
2035 tree cvar
, cvar_init
, initvar
, cvar_next
, cvar_base
, type
;
2036 edge exit
, nexit
, guard
, end
, e
;
2038 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
2041 tree clause
= build_omp_clause (loc
, OMP_CLAUSE_NUM_GANGS
);
2042 OMP_CLAUSE_NUM_GANGS_EXPR (clause
)
2043 = build_int_cst (integer_type_node
, n_threads
);
2044 set_oacc_fn_attrib (cfun
->decl
, clause
, NULL
);
2048 basic_block bb
= loop_preheader_edge (loop
)->src
;
2049 basic_block paral_bb
= single_pred (bb
);
2050 gsi
= gsi_last_bb (paral_bb
);
2052 t
= build_omp_clause (loc
, OMP_CLAUSE_NUM_THREADS
);
2053 OMP_CLAUSE_NUM_THREADS_EXPR (t
)
2054 = build_int_cst (integer_type_node
, n_threads
);
2055 omp_par_stmt
= gimple_build_omp_parallel (NULL
, t
, loop_fn
, data
);
2056 gimple_set_location (omp_par_stmt
, loc
);
2058 gsi_insert_after (&gsi
, omp_par_stmt
, GSI_NEW_STMT
);
2060 /* Initialize NEW_DATA. */
2063 gassign
*assign_stmt
;
2065 gsi
= gsi_after_labels (bb
);
2067 param
= make_ssa_name (DECL_ARGUMENTS (loop_fn
));
2068 assign_stmt
= gimple_build_assign (param
, build_fold_addr_expr (data
));
2069 gsi_insert_before (&gsi
, assign_stmt
, GSI_SAME_STMT
);
2071 assign_stmt
= gimple_build_assign (new_data
,
2072 fold_convert (TREE_TYPE (new_data
), param
));
2073 gsi_insert_before (&gsi
, assign_stmt
, GSI_SAME_STMT
);
2076 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
2077 bb
= split_loop_exit_edge (single_dom_exit (loop
));
2078 gsi
= gsi_last_bb (bb
);
2079 omp_return_stmt1
= gimple_build_omp_return (false);
2080 gimple_set_location (omp_return_stmt1
, loc
);
2081 gsi_insert_after (&gsi
, omp_return_stmt1
, GSI_NEW_STMT
);
2084 /* Extract data for GIMPLE_OMP_FOR. */
2085 gcc_assert (loop
->header
== single_dom_exit (loop
)->src
);
2086 cond_stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
2088 cvar
= gimple_cond_lhs (cond_stmt
);
2089 cvar_base
= SSA_NAME_VAR (cvar
);
2090 phi
= SSA_NAME_DEF_STMT (cvar
);
2091 cvar_init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2092 initvar
= copy_ssa_name (cvar
);
2093 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, loop_preheader_edge (loop
)),
2095 cvar_next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2097 gsi
= gsi_last_nondebug_bb (loop
->latch
);
2098 gcc_assert (gsi_stmt (gsi
) == SSA_NAME_DEF_STMT (cvar_next
));
2099 gsi_remove (&gsi
, true);
2102 for_bb
= split_edge (loop_preheader_edge (loop
));
2103 ex_bb
= split_loop_exit_edge (single_dom_exit (loop
));
2104 extract_true_false_edges_from_block (loop
->header
, &nexit
, &exit
);
2105 gcc_assert (exit
== single_dom_exit (loop
));
2107 guard
= make_edge (for_bb
, ex_bb
, 0);
2108 /* Split the latch edge, so LOOPS_HAVE_SIMPLE_LATCHES is still valid. */
2109 loop
->latch
= split_edge (single_succ_edge (loop
->latch
));
2110 single_pred_edge (loop
->latch
)->flags
= 0;
2111 end
= make_edge (single_pred (loop
->latch
), ex_bb
, EDGE_FALLTHRU
);
2112 rescan_loop_exit (end
, true, false);
2114 for (gphi_iterator gpi
= gsi_start_phis (ex_bb
);
2115 !gsi_end_p (gpi
); gsi_next (&gpi
))
2117 source_location locus
;
2118 gphi
*phi
= gpi
.phi ();
2119 tree def
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2120 gimple
*def_stmt
= SSA_NAME_DEF_STMT (def
);
2122 /* If the exit phi is not connected to a header phi in the same loop, this
2123 value is not modified in the loop, and we're done with this phi. */
2124 if (!(gimple_code (def_stmt
) == GIMPLE_PHI
2125 && gimple_bb (def_stmt
) == loop
->header
))
2127 locus
= gimple_phi_arg_location_from_edge (phi
, exit
);
2128 add_phi_arg (phi
, def
, guard
, locus
);
2129 add_phi_arg (phi
, def
, end
, locus
);
2133 gphi
*stmt
= as_a
<gphi
*> (def_stmt
);
2134 def
= PHI_ARG_DEF_FROM_EDGE (stmt
, loop_preheader_edge (loop
));
2135 locus
= gimple_phi_arg_location_from_edge (stmt
,
2136 loop_preheader_edge (loop
));
2137 add_phi_arg (phi
, def
, guard
, locus
);
2139 def
= PHI_ARG_DEF_FROM_EDGE (stmt
, loop_latch_edge (loop
));
2140 locus
= gimple_phi_arg_location_from_edge (stmt
, loop_latch_edge (loop
));
2141 add_phi_arg (phi
, def
, end
, locus
);
2143 e
= redirect_edge_and_branch (exit
, nexit
->dest
);
2144 PENDING_STMT (e
) = NULL
;
2146 /* Emit GIMPLE_OMP_FOR. */
2148 /* In combination with the NUM_GANGS on the parallel. */
2149 t
= build_omp_clause (loc
, OMP_CLAUSE_GANG
);
2152 t
= build_omp_clause (loc
, OMP_CLAUSE_SCHEDULE
);
2153 int chunk_size
= PARAM_VALUE (PARAM_PARLOOPS_CHUNK_SIZE
);
2154 enum PARAM_PARLOOPS_SCHEDULE_KIND schedule_type \
2155 = (enum PARAM_PARLOOPS_SCHEDULE_KIND
) PARAM_VALUE (PARAM_PARLOOPS_SCHEDULE
);
2156 switch (schedule_type
)
2158 case PARAM_PARLOOPS_SCHEDULE_KIND_static
:
2159 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_STATIC
;
2161 case PARAM_PARLOOPS_SCHEDULE_KIND_dynamic
:
2162 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_DYNAMIC
;
2164 case PARAM_PARLOOPS_SCHEDULE_KIND_guided
:
2165 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_GUIDED
;
2167 case PARAM_PARLOOPS_SCHEDULE_KIND_auto
:
2168 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_AUTO
;
2171 case PARAM_PARLOOPS_SCHEDULE_KIND_runtime
:
2172 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_RUNTIME
;
2178 if (chunk_size
!= 0)
2179 OMP_CLAUSE_SCHEDULE_CHUNK_EXPR (t
)
2180 = build_int_cst (integer_type_node
, chunk_size
);
2183 for_stmt
= gimple_build_omp_for (NULL
,
2185 ? GF_OMP_FOR_KIND_OACC_LOOP
2186 : GF_OMP_FOR_KIND_FOR
),
2189 gimple_cond_set_lhs (cond_stmt
, cvar_base
);
2190 type
= TREE_TYPE (cvar
);
2191 gimple_set_location (for_stmt
, loc
);
2192 gimple_omp_for_set_index (for_stmt
, 0, initvar
);
2193 gimple_omp_for_set_initial (for_stmt
, 0, cvar_init
);
2194 gimple_omp_for_set_final (for_stmt
, 0, gimple_cond_rhs (cond_stmt
));
2195 gimple_omp_for_set_cond (for_stmt
, 0, gimple_cond_code (cond_stmt
));
2196 gimple_omp_for_set_incr (for_stmt
, 0, build2 (PLUS_EXPR
, type
,
2198 build_int_cst (type
, 1)));
2200 gsi
= gsi_last_bb (for_bb
);
2201 gsi_insert_after (&gsi
, for_stmt
, GSI_NEW_STMT
);
2202 SSA_NAME_DEF_STMT (initvar
) = for_stmt
;
2204 /* Emit GIMPLE_OMP_CONTINUE. */
2205 continue_bb
= single_pred (loop
->latch
);
2206 gsi
= gsi_last_bb (continue_bb
);
2207 omp_cont_stmt
= gimple_build_omp_continue (cvar_next
, cvar
);
2208 gimple_set_location (omp_cont_stmt
, loc
);
2209 gsi_insert_after (&gsi
, omp_cont_stmt
, GSI_NEW_STMT
);
2210 SSA_NAME_DEF_STMT (cvar_next
) = omp_cont_stmt
;
2212 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
2213 gsi
= gsi_last_bb (ex_bb
);
2214 omp_return_stmt2
= gimple_build_omp_return (true);
2215 gimple_set_location (omp_return_stmt2
, loc
);
2216 gsi_insert_after (&gsi
, omp_return_stmt2
, GSI_NEW_STMT
);
2218 /* After the above dom info is hosed. Re-compute it. */
2219 free_dominance_info (CDI_DOMINATORS
);
2220 calculate_dominance_info (CDI_DOMINATORS
);
2223 /* Generates code to execute the iterations of LOOP in N_THREADS
2224 threads in parallel.
2226 NITER describes number of iterations of LOOP.
2227 REDUCTION_LIST describes the reductions existent in the LOOP. */
2230 gen_parallel_loop (struct loop
*loop
,
2231 reduction_info_table_type
*reduction_list
,
2232 unsigned n_threads
, struct tree_niter_desc
*niter
,
2233 bool oacc_kernels_p
)
2235 tree many_iterations_cond
, type
, nit
;
2236 tree arg_struct
, new_arg_struct
;
2239 struct clsn_data clsn_data
;
2243 unsigned int m_p_thread
=2;
2247 ---------------------------------------------------------------------
2250 IV = phi (INIT, IV + STEP)
2256 ---------------------------------------------------------------------
2258 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
2259 we generate the following code:
2261 ---------------------------------------------------------------------
2264 || NITER < MIN_PER_THREAD * N_THREADS)
2268 store all local loop-invariant variables used in body of the loop to DATA.
2269 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
2270 load the variables from DATA.
2271 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
2274 GIMPLE_OMP_CONTINUE;
2275 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
2276 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
2282 IV = phi (INIT, IV + STEP)
2293 /* Create two versions of the loop -- in the old one, we know that the
2294 number of iterations is large enough, and we will transform it into the
2295 loop that will be split to loop_fn, the new one will be used for the
2296 remaining iterations. */
2298 /* We should compute a better number-of-iterations value for outer loops.
2301 for (i = 0; i < n; ++i)
2302 for (j = 0; j < m; ++j)
2305 we should compute nit = n * m, not nit = n.
2306 Also may_be_zero handling would need to be adjusted. */
2308 type
= TREE_TYPE (niter
->niter
);
2309 nit
= force_gimple_operand (unshare_expr (niter
->niter
), &stmts
, true,
2312 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
2314 if (!oacc_kernels_p
)
2319 m_p_thread
=MIN_PER_THREAD
;
2321 many_iterations_cond
=
2322 fold_build2 (GE_EXPR
, boolean_type_node
,
2323 nit
, build_int_cst (type
, m_p_thread
* n_threads
));
2325 many_iterations_cond
2326 = fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
2327 invert_truthvalue (unshare_expr (niter
->may_be_zero
)),
2328 many_iterations_cond
);
2329 many_iterations_cond
2330 = force_gimple_operand (many_iterations_cond
, &stmts
, false, NULL_TREE
);
2332 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
2333 if (!is_gimple_condexpr (many_iterations_cond
))
2335 many_iterations_cond
2336 = force_gimple_operand (many_iterations_cond
, &stmts
,
2339 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
),
2343 initialize_original_copy_tables ();
2345 /* We assume that the loop usually iterates a lot. */
2346 prob
= 4 * REG_BR_PROB_BASE
/ 5;
2347 loop_version (loop
, many_iterations_cond
, NULL
,
2348 prob
, prob
, REG_BR_PROB_BASE
- prob
, true);
2349 update_ssa (TODO_update_ssa
);
2350 free_original_copy_tables ();
2353 /* Base all the induction variables in LOOP on a single control one. */
2354 canonicalize_loop_ivs (loop
, &nit
, true);
2356 /* Ensure that the exit condition is the first statement in the loop.
2357 The common case is that latch of the loop is empty (apart from the
2358 increment) and immediately follows the loop exit test. Attempt to move the
2359 entry of the loop directly before the exit check and increase the number of
2360 iterations of the loop by one. */
2361 if (try_transform_to_exit_first_loop_alt (loop
, reduction_list
, nit
))
2364 && (dump_flags
& TDF_DETAILS
))
2366 "alternative exit-first loop transform succeeded"
2367 " for loop %d\n", loop
->num
);
2374 /* Fall back on the method that handles more cases, but duplicates the
2375 loop body: move the exit condition of LOOP to the beginning of its
2376 header, and duplicate the part of the last iteration that gets disabled
2377 to the exit of the loop. */
2378 transform_to_exit_first_loop (loop
, reduction_list
, nit
);
2381 /* Generate initializations for reductions. */
2382 if (reduction_list
->elements () > 0)
2383 reduction_list
->traverse
<struct loop
*, initialize_reductions
> (loop
);
2385 /* Eliminate the references to local variables from the loop. */
2386 gcc_assert (single_exit (loop
));
2387 entry
= loop_preheader_edge (loop
);
2388 exit
= single_dom_exit (loop
);
2390 /* This rewrites the body in terms of new variables. This has already
2391 been done for oacc_kernels_p in pass_lower_omp/lower_omp (). */
2392 if (!oacc_kernels_p
)
2394 eliminate_local_variables (entry
, exit
);
2395 /* In the old loop, move all variables non-local to the loop to a
2396 structure and back, and create separate decls for the variables used in
2398 separate_decls_in_region (entry
, exit
, reduction_list
, &arg_struct
,
2399 &new_arg_struct
, &clsn_data
);
2403 arg_struct
= NULL_TREE
;
2404 new_arg_struct
= NULL_TREE
;
2405 clsn_data
.load
= NULL_TREE
;
2406 clsn_data
.load_bb
= exit
->dest
;
2407 clsn_data
.store
= NULL_TREE
;
2408 clsn_data
.store_bb
= NULL
;
2411 /* Create the parallel constructs. */
2412 loc
= UNKNOWN_LOCATION
;
2413 cond_stmt
= last_stmt (loop
->header
);
2415 loc
= gimple_location (cond_stmt
);
2416 create_parallel_loop (loop
, create_loop_fn (loc
), arg_struct
, new_arg_struct
,
2417 n_threads
, loc
, oacc_kernels_p
);
2418 if (reduction_list
->elements () > 0)
2419 create_call_for_reduction (loop
, reduction_list
, &clsn_data
);
2423 /* Free loop bound estimations that could contain references to
2424 removed statements. */
2425 FOR_EACH_LOOP (loop
, 0)
2426 free_numbers_of_iterations_estimates_loop (loop
);
2429 /* Returns true when LOOP contains vector phi nodes. */
2432 loop_has_vector_phi_nodes (struct loop
*loop ATTRIBUTE_UNUSED
)
2435 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
2439 for (i
= 0; i
< loop
->num_nodes
; i
++)
2440 for (gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
2441 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi
.phi ()))) == VECTOR_TYPE
)
2450 /* Create a reduction_info struct, initialize it with REDUC_STMT
2451 and PHI, insert it to the REDUCTION_LIST. */
2454 build_new_reduction (reduction_info_table_type
*reduction_list
,
2455 gimple
*reduc_stmt
, gphi
*phi
)
2457 reduction_info
**slot
;
2458 struct reduction_info
*new_reduction
;
2459 enum tree_code reduction_code
;
2461 gcc_assert (reduc_stmt
);
2463 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2466 "Detected reduction. reduction stmt is:\n");
2467 print_gimple_stmt (dump_file
, reduc_stmt
, 0, 0);
2468 fprintf (dump_file
, "\n");
2471 if (gimple_code (reduc_stmt
) == GIMPLE_PHI
)
2473 tree op1
= PHI_ARG_DEF (reduc_stmt
, 0);
2474 gimple
*def1
= SSA_NAME_DEF_STMT (op1
);
2475 reduction_code
= gimple_assign_rhs_code (def1
);
2479 reduction_code
= gimple_assign_rhs_code (reduc_stmt
);
2481 new_reduction
= XCNEW (struct reduction_info
);
2483 new_reduction
->reduc_stmt
= reduc_stmt
;
2484 new_reduction
->reduc_phi
= phi
;
2485 new_reduction
->reduc_version
= SSA_NAME_VERSION (gimple_phi_result (phi
));
2486 new_reduction
->reduction_code
= reduction_code
;
2487 slot
= reduction_list
->find_slot (new_reduction
, INSERT
);
2488 *slot
= new_reduction
;
2491 /* Callback for htab_traverse. Sets gimple_uid of reduc_phi stmts. */
2494 set_reduc_phi_uids (reduction_info
**slot
, void *data ATTRIBUTE_UNUSED
)
2496 struct reduction_info
*const red
= *slot
;
2497 gimple_set_uid (red
->reduc_phi
, red
->reduc_version
);
2501 /* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
2504 gather_scalar_reductions (loop_p loop
, reduction_info_table_type
*reduction_list
)
2507 loop_vec_info simple_loop_info
;
2508 loop_vec_info simple_inner_loop_info
= NULL
;
2509 bool allow_double_reduc
= true;
2511 if (!stmt_vec_info_vec
.exists ())
2512 init_stmt_vec_info_vec ();
2514 simple_loop_info
= vect_analyze_loop_form (loop
);
2515 if (simple_loop_info
== NULL
)
2518 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2520 gphi
*phi
= gsi
.phi ();
2522 tree res
= PHI_RESULT (phi
);
2525 if (virtual_operand_p (res
))
2528 if (simple_iv (loop
, loop
, res
, &iv
, true))
2532 = vect_force_simple_reduction (simple_loop_info
, phi
, true,
2533 &double_reduc
, true);
2539 if (!allow_double_reduc
2540 || loop
->inner
->inner
!= NULL
)
2543 if (!simple_inner_loop_info
)
2545 simple_inner_loop_info
= vect_analyze_loop_form (loop
->inner
);
2546 if (!simple_inner_loop_info
)
2548 allow_double_reduc
= false;
2553 use_operand_p use_p
;
2555 bool single_use_p
= single_imm_use (res
, &use_p
, &inner_stmt
);
2556 gcc_assert (single_use_p
);
2557 if (gimple_code (inner_stmt
) != GIMPLE_PHI
)
2559 gphi
*inner_phi
= as_a
<gphi
*> (inner_stmt
);
2560 if (simple_iv (loop
->inner
, loop
->inner
, PHI_RESULT (inner_phi
),
2564 gimple
*inner_reduc_stmt
2565 = vect_force_simple_reduction (simple_inner_loop_info
, inner_phi
,
2566 true, &double_reduc
, true);
2567 gcc_assert (!double_reduc
);
2568 if (inner_reduc_stmt
== NULL
)
2572 build_new_reduction (reduction_list
, reduc_stmt
, phi
);
2574 destroy_loop_vec_info (simple_loop_info
, true);
2575 destroy_loop_vec_info (simple_inner_loop_info
, true);
2578 /* Release the claim on gimple_uid. */
2579 free_stmt_vec_info_vec ();
2581 if (reduction_list
->elements () == 0)
2584 /* As gimple_uid is used by the vectorizer in between vect_analyze_loop_form
2585 and free_stmt_vec_info_vec, we can set gimple_uid of reduc_phi stmts only
2588 FOR_EACH_BB_FN (bb
, cfun
)
2589 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2590 gimple_set_uid (gsi_stmt (gsi
), (unsigned int)-1);
2591 reduction_list
->traverse
<void *, set_reduc_phi_uids
> (NULL
);
2594 /* Try to initialize NITER for code generation part. */
2597 try_get_loop_niter (loop_p loop
, struct tree_niter_desc
*niter
)
2599 edge exit
= single_dom_exit (loop
);
2603 /* We need to know # of iterations, and there should be no uses of values
2604 defined inside loop outside of it, unless the values are invariants of
2606 if (!number_of_iterations_exit (loop
, exit
, niter
, false))
2608 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2609 fprintf (dump_file
, " FAILED: number of iterations not known\n");
2616 /* Return the default def of the first function argument. */
2619 get_omp_data_i_param (void)
2621 tree decl
= DECL_ARGUMENTS (cfun
->decl
);
2622 gcc_assert (DECL_CHAIN (decl
) == NULL_TREE
);
2623 return ssa_default_def (cfun
, decl
);
2626 /* For PHI in loop header of LOOP, look for pattern:
2629 .omp_data_i = &.omp_data_arr;
2630 addr = .omp_data_i->sum;
2634 sum_b = PHI <sum_a (preheader), sum_c (latch)>
2636 and return addr. Otherwise, return NULL_TREE. */
2639 find_reduc_addr (struct loop
*loop
, gphi
*phi
)
2641 edge e
= loop_preheader_edge (loop
);
2642 tree arg
= PHI_ARG_DEF_FROM_EDGE (phi
, e
);
2643 gimple
*stmt
= SSA_NAME_DEF_STMT (arg
);
2644 if (!gimple_assign_single_p (stmt
))
2646 tree memref
= gimple_assign_rhs1 (stmt
);
2647 if (TREE_CODE (memref
) != MEM_REF
)
2649 tree addr
= TREE_OPERAND (memref
, 0);
2651 gimple
*stmt2
= SSA_NAME_DEF_STMT (addr
);
2652 if (!gimple_assign_single_p (stmt2
))
2654 tree compref
= gimple_assign_rhs1 (stmt2
);
2655 if (TREE_CODE (compref
) != COMPONENT_REF
)
2657 tree addr2
= TREE_OPERAND (compref
, 0);
2658 if (TREE_CODE (addr2
) != MEM_REF
)
2660 addr2
= TREE_OPERAND (addr2
, 0);
2661 if (TREE_CODE (addr2
) != SSA_NAME
2662 || addr2
!= get_omp_data_i_param ())
2668 /* Try to initialize REDUCTION_LIST for code generation part.
2669 REDUCTION_LIST describes the reductions. */
2672 try_create_reduction_list (loop_p loop
,
2673 reduction_info_table_type
*reduction_list
,
2674 bool oacc_kernels_p
)
2676 edge exit
= single_dom_exit (loop
);
2681 /* Try to get rid of exit phis. */
2682 final_value_replacement_loop (loop
);
2684 gather_scalar_reductions (loop
, reduction_list
);
2687 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2689 gphi
*phi
= gsi
.phi ();
2690 struct reduction_info
*red
;
2691 imm_use_iterator imm_iter
;
2692 use_operand_p use_p
;
2694 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2696 if (!virtual_operand_p (val
))
2698 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2700 fprintf (dump_file
, "phi is ");
2701 print_gimple_stmt (dump_file
, phi
, 0, 0);
2702 fprintf (dump_file
, "arg of phi to exit: value ");
2703 print_generic_expr (dump_file
, val
, 0);
2704 fprintf (dump_file
, " used outside loop\n");
2706 " checking if it is part of reduction pattern:\n");
2708 if (reduction_list
->elements () == 0)
2710 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2712 " FAILED: it is not a part of reduction.\n");
2716 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, val
)
2718 if (!gimple_debug_bind_p (USE_STMT (use_p
))
2719 && flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
2721 reduc_phi
= USE_STMT (use_p
);
2725 red
= reduction_phi (reduction_list
, reduc_phi
);
2728 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2730 " FAILED: it is not a part of reduction.\n");
2733 if (red
->keep_res
!= NULL
)
2735 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2737 " FAILED: reduction has multiple exit phis.\n");
2740 red
->keep_res
= phi
;
2741 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2743 fprintf (dump_file
, "reduction phi is ");
2744 print_gimple_stmt (dump_file
, red
->reduc_phi
, 0, 0);
2745 fprintf (dump_file
, "reduction stmt is ");
2746 print_gimple_stmt (dump_file
, red
->reduc_stmt
, 0, 0);
2751 /* The iterations of the loop may communicate only through bivs whose
2752 iteration space can be distributed efficiently. */
2753 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2755 gphi
*phi
= gsi
.phi ();
2756 tree def
= PHI_RESULT (phi
);
2759 if (!virtual_operand_p (def
) && !simple_iv (loop
, loop
, def
, &iv
, true))
2761 struct reduction_info
*red
;
2763 red
= reduction_phi (reduction_list
, phi
);
2766 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2768 " FAILED: scalar dependency between iterations\n");
2776 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
);
2779 gphi
*phi
= gsi
.phi ();
2780 tree def
= PHI_RESULT (phi
);
2783 if (!virtual_operand_p (def
)
2784 && !simple_iv (loop
, loop
, def
, &iv
, true))
2786 tree addr
= find_reduc_addr (loop
, phi
);
2787 if (addr
== NULL_TREE
)
2789 struct reduction_info
*red
= reduction_phi (reduction_list
, phi
);
2790 red
->reduc_addr
= addr
;
2798 /* Return true if LOOP contains phis with ADDR_EXPR in args. */
2801 loop_has_phi_with_address_arg (struct loop
*loop
)
2803 basic_block
*bbs
= get_loop_body (loop
);
2808 for (i
= 0; i
< loop
->num_nodes
; i
++)
2809 for (gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
2811 gphi
*phi
= gsi
.phi ();
2812 for (j
= 0; j
< gimple_phi_num_args (phi
); j
++)
2814 tree arg
= gimple_phi_arg_def (phi
, j
);
2815 if (TREE_CODE (arg
) == ADDR_EXPR
)
2817 /* This should be handled by eliminate_local_variables, but that
2818 function currently ignores phis. */
2830 /* Return true if memory ref REF (corresponding to the stmt at GSI in
2831 REGIONS_BB[I]) conflicts with the statements in REGIONS_BB[I] after gsi,
2832 or the statements in REGIONS_BB[I + n]. REF_IS_STORE indicates if REF is a
2833 store. Ignore conflicts with SKIP_STMT. */
2836 ref_conflicts_with_region (gimple_stmt_iterator gsi
, ao_ref
*ref
,
2837 bool ref_is_store
, vec
<basic_block
> region_bbs
,
2838 unsigned int i
, gimple
*skip_stmt
)
2840 basic_block bb
= region_bbs
[i
];
2845 for (; !gsi_end_p (gsi
);
2848 gimple
*stmt
= gsi_stmt (gsi
);
2849 if (stmt
== skip_stmt
)
2853 fprintf (dump_file
, "skipping reduction store: ");
2854 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2859 if (!gimple_vdef (stmt
)
2860 && !gimple_vuse (stmt
))
2863 if (gimple_code (stmt
) == GIMPLE_RETURN
)
2868 if (ref_maybe_used_by_stmt_p (stmt
, ref
))
2872 fprintf (dump_file
, "Stmt ");
2873 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2880 if (stmt_may_clobber_ref_p_1 (stmt
, ref
))
2884 fprintf (dump_file
, "Stmt ");
2885 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2892 if (i
== region_bbs
.length ())
2895 gsi
= gsi_start_bb (bb
);
2901 /* Return true if the bbs in REGION_BBS but not in in_loop_bbs can be executed
2902 in parallel with REGION_BBS containing the loop. Return the stores of
2903 reduction results in REDUCTION_STORES. */
2906 oacc_entry_exit_ok_1 (bitmap in_loop_bbs
, vec
<basic_block
> region_bbs
,
2907 reduction_info_table_type
*reduction_list
,
2908 bitmap reduction_stores
)
2910 tree omp_data_i
= get_omp_data_i_param ();
2914 FOR_EACH_VEC_ELT (region_bbs
, i
, bb
)
2916 if (bitmap_bit_p (in_loop_bbs
, bb
->index
))
2919 gimple_stmt_iterator gsi
;
2920 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
2923 gimple
*stmt
= gsi_stmt (gsi
);
2924 gimple
*skip_stmt
= NULL
;
2926 if (is_gimple_debug (stmt
)
2927 || gimple_code (stmt
) == GIMPLE_COND
)
2931 bool ref_is_store
= false;
2932 if (gimple_assign_load_p (stmt
))
2934 tree rhs
= gimple_assign_rhs1 (stmt
);
2935 tree base
= get_base_address (rhs
);
2936 if (TREE_CODE (base
) == MEM_REF
2937 && operand_equal_p (TREE_OPERAND (base
, 0), omp_data_i
, 0))
2940 tree lhs
= gimple_assign_lhs (stmt
);
2941 if (TREE_CODE (lhs
) == SSA_NAME
2942 && has_single_use (lhs
))
2944 use_operand_p use_p
;
2946 single_imm_use (lhs
, &use_p
, &use_stmt
);
2947 if (gimple_code (use_stmt
) == GIMPLE_PHI
)
2949 struct reduction_info
*red
;
2950 red
= reduction_phi (reduction_list
, use_stmt
);
2951 tree val
= PHI_RESULT (red
->keep_res
);
2952 if (has_single_use (val
))
2954 single_imm_use (val
, &use_p
, &use_stmt
);
2955 if (gimple_store_p (use_stmt
))
2958 = SSA_NAME_VERSION (gimple_vdef (use_stmt
));
2959 bitmap_set_bit (reduction_stores
, id
);
2960 skip_stmt
= use_stmt
;
2963 fprintf (dump_file
, "found reduction load: ");
2964 print_gimple_stmt (dump_file
, stmt
, 0, 0);
2971 ao_ref_init (&ref
, rhs
);
2973 else if (gimple_store_p (stmt
))
2975 ao_ref_init (&ref
, gimple_assign_lhs (stmt
));
2976 ref_is_store
= true;
2978 else if (gimple_code (stmt
) == GIMPLE_OMP_RETURN
)
2980 else if (!gimple_has_side_effects (stmt
)
2981 && !gimple_could_trap_p (stmt
)
2982 && !stmt_could_throw_p (stmt
)
2983 && !gimple_vdef (stmt
)
2984 && !gimple_vuse (stmt
))
2986 else if (is_gimple_call (stmt
)
2987 && gimple_call_internal_p (stmt
)
2988 && gimple_call_internal_fn (stmt
) == IFN_GOACC_DIM_POS
)
2990 else if (gimple_code (stmt
) == GIMPLE_RETURN
)
2996 fprintf (dump_file
, "Unhandled stmt in entry/exit: ");
2997 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3002 if (ref_conflicts_with_region (gsi
, &ref
, ref_is_store
, region_bbs
,
3007 fprintf (dump_file
, "conflicts with entry/exit stmt: ");
3008 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3018 /* Find stores inside REGION_BBS and outside IN_LOOP_BBS, and guard them with
3019 gang_pos == 0, except when the stores are REDUCTION_STORES. Return true
3020 if any changes were made. */
3023 oacc_entry_exit_single_gang (bitmap in_loop_bbs
, vec
<basic_block
> region_bbs
,
3024 bitmap reduction_stores
)
3026 tree gang_pos
= NULL_TREE
;
3027 bool changed
= false;
3031 FOR_EACH_VEC_ELT (region_bbs
, i
, bb
)
3033 if (bitmap_bit_p (in_loop_bbs
, bb
->index
))
3036 gimple_stmt_iterator gsi
;
3037 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
3039 gimple
*stmt
= gsi_stmt (gsi
);
3041 if (!gimple_store_p (stmt
))
3043 /* Update gsi to point to next stmt. */
3048 if (bitmap_bit_p (reduction_stores
,
3049 SSA_NAME_VERSION (gimple_vdef (stmt
))))
3054 "skipped reduction store for single-gang"
3056 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3059 /* Update gsi to point to next stmt. */
3066 if (gang_pos
== NULL_TREE
)
3068 tree arg
= build_int_cst (integer_type_node
, GOMP_DIM_GANG
);
3070 = gimple_build_call_internal (IFN_GOACC_DIM_POS
, 1, arg
);
3071 gang_pos
= make_ssa_name (integer_type_node
);
3072 gimple_call_set_lhs (gang_single
, gang_pos
);
3073 gimple_stmt_iterator start
3074 = gsi_start_bb (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
)));
3075 tree vuse
= ssa_default_def (cfun
, gimple_vop (cfun
));
3076 gimple_set_vuse (gang_single
, vuse
);
3077 gsi_insert_before (&start
, gang_single
, GSI_SAME_STMT
);
3083 "found store that needs single-gang neutering: ");
3084 print_gimple_stmt (dump_file
, stmt
, 0, 0);
3088 /* Split block before store. */
3089 gimple_stmt_iterator gsi2
= gsi
;
3092 if (gsi_end_p (gsi2
))
3094 e
= split_block_after_labels (bb
);
3095 gsi2
= gsi_last_bb (bb
);
3098 e
= split_block (bb
, gsi_stmt (gsi2
));
3099 basic_block bb2
= e
->dest
;
3101 /* Split block after store. */
3102 gimple_stmt_iterator gsi3
= gsi_start_bb (bb2
);
3103 edge e2
= split_block (bb2
, gsi_stmt (gsi3
));
3104 basic_block bb3
= e2
->dest
;
3107 = gimple_build_cond (EQ_EXPR
, gang_pos
, integer_zero_node
,
3108 NULL_TREE
, NULL_TREE
);
3109 gsi_insert_after (&gsi2
, cond
, GSI_NEW_STMT
);
3111 edge e3
= make_edge (bb
, bb3
, EDGE_FALSE_VALUE
);
3112 e
->flags
= EDGE_TRUE_VALUE
;
3114 tree vdef
= gimple_vdef (stmt
);
3115 tree vuse
= gimple_vuse (stmt
);
3117 tree phi_res
= copy_ssa_name (vdef
);
3118 gphi
*new_phi
= create_phi_node (phi_res
, bb3
);
3119 replace_uses_by (vdef
, phi_res
);
3120 add_phi_arg (new_phi
, vuse
, e3
, UNKNOWN_LOCATION
);
3121 add_phi_arg (new_phi
, vdef
, e2
, UNKNOWN_LOCATION
);
3123 /* Update gsi to point to next stmt. */
3125 gsi
= gsi_start_bb (bb
);
3133 /* Return true if the statements before and after the LOOP can be executed in
3134 parallel with the function containing the loop. Resolve conflicting stores
3135 outside LOOP by guarding them such that only a single gang executes them. */
3138 oacc_entry_exit_ok (struct loop
*loop
,
3139 reduction_info_table_type
*reduction_list
)
3141 basic_block
*loop_bbs
= get_loop_body_in_dom_order (loop
);
3142 vec
<basic_block
> region_bbs
3143 = get_all_dominated_blocks (CDI_DOMINATORS
, ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3145 bitmap in_loop_bbs
= BITMAP_ALLOC (NULL
);
3146 bitmap_clear (in_loop_bbs
);
3147 for (unsigned int i
= 0; i
< loop
->num_nodes
; i
++)
3148 bitmap_set_bit (in_loop_bbs
, loop_bbs
[i
]->index
);
3150 bitmap reduction_stores
= BITMAP_ALLOC (NULL
);
3151 bool res
= oacc_entry_exit_ok_1 (in_loop_bbs
, region_bbs
, reduction_list
,
3156 bool changed
= oacc_entry_exit_single_gang (in_loop_bbs
, region_bbs
,
3160 free_dominance_info (CDI_DOMINATORS
);
3161 calculate_dominance_info (CDI_DOMINATORS
);
3167 BITMAP_FREE (in_loop_bbs
);
3168 BITMAP_FREE (reduction_stores
);
3173 /* Detect parallel loops and generate parallel code using libgomp
3174 primitives. Returns true if some loop was parallelized, false
3178 parallelize_loops (bool oacc_kernels_p
)
3180 unsigned n_threads
= flag_tree_parallelize_loops
;
3181 bool changed
= false;
3183 struct loop
*skip_loop
= NULL
;
3184 struct tree_niter_desc niter_desc
;
3185 struct obstack parloop_obstack
;
3186 HOST_WIDE_INT estimated
;
3187 source_location loop_loc
;
3189 /* Do not parallelize loops in the functions created by parallelization. */
3191 && parallelized_function_p (cfun
->decl
))
3194 /* Do not parallelize loops in offloaded functions. */
3196 && get_oacc_fn_attrib (cfun
->decl
) != NULL
)
3199 if (cfun
->has_nonlocal_label
)
3202 gcc_obstack_init (&parloop_obstack
);
3203 reduction_info_table_type
reduction_list (10);
3205 calculate_dominance_info (CDI_DOMINATORS
);
3207 FOR_EACH_LOOP (loop
, 0)
3209 if (loop
== skip_loop
)
3211 if (!loop
->in_oacc_kernels_region
3212 && dump_file
&& (dump_flags
& TDF_DETAILS
))
3214 "Skipping loop %d as inner loop of parallelized loop\n",
3217 skip_loop
= loop
->inner
;
3223 reduction_list
.empty ();
3227 if (!loop
->in_oacc_kernels_region
)
3230 /* Don't try to parallelize inner loops in an oacc kernels region. */
3232 skip_loop
= loop
->inner
;
3234 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3236 "Trying loop %d with header bb %d in oacc kernels"
3237 " region\n", loop
->num
, loop
->header
->index
);
3240 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3242 fprintf (dump_file
, "Trying loop %d as candidate\n",loop
->num
);
3244 fprintf (dump_file
, "loop %d is not innermost\n",loop
->num
);
3246 fprintf (dump_file
, "loop %d is innermost\n",loop
->num
);
3249 /* If we use autopar in graphite pass, we use its marked dependency
3250 checking results. */
3251 if (flag_loop_parallelize_all
&& !loop
->can_be_parallel
)
3253 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3254 fprintf (dump_file
, "loop is not parallel according to graphite\n");
3258 if (!single_dom_exit (loop
))
3261 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3262 fprintf (dump_file
, "loop is !single_dom_exit\n");
3267 if (/* And of course, the loop must be parallelizable. */
3268 !can_duplicate_loop_p (loop
)
3269 || loop_has_blocks_with_irreducible_flag (loop
)
3270 || (loop_preheader_edge (loop
)->src
->flags
& BB_IRREDUCIBLE_LOOP
)
3271 /* FIXME: the check for vector phi nodes could be removed. */
3272 || loop_has_vector_phi_nodes (loop
))
3275 estimated
= estimated_stmt_executions_int (loop
);
3276 if (estimated
== -1)
3277 estimated
= max_stmt_executions_int (loop
);
3278 /* FIXME: Bypass this check as graphite doesn't update the
3279 count and frequency correctly now. */
3280 if (!flag_loop_parallelize_all
3282 && ((estimated
!= -1
3283 && estimated
<= (HOST_WIDE_INT
) n_threads
* MIN_PER_THREAD
)
3284 /* Do not bother with loops in cold areas. */
3285 || optimize_loop_nest_for_size_p (loop
)))
3288 if (!try_get_loop_niter (loop
, &niter_desc
))
3291 if (!try_create_reduction_list (loop
, &reduction_list
, oacc_kernels_p
))
3294 if (loop_has_phi_with_address_arg (loop
))
3297 if (!flag_loop_parallelize_all
3298 && !loop_parallel_p (loop
, &parloop_obstack
))
3302 && !oacc_entry_exit_ok (loop
, &reduction_list
))
3305 fprintf (dump_file
, "entry/exit not ok: FAILED\n");
3310 skip_loop
= loop
->inner
;
3311 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3314 fprintf (dump_file
, "parallelizing outer loop %d\n",loop
->header
->index
);
3316 fprintf (dump_file
, "parallelizing inner loop %d\n",loop
->header
->index
);
3317 loop_loc
= find_loop_location (loop
);
3318 if (loop_loc
!= UNKNOWN_LOCATION
)
3319 fprintf (dump_file
, "\nloop at %s:%d: ",
3320 LOCATION_FILE (loop_loc
), LOCATION_LINE (loop_loc
));
3323 gen_parallel_loop (loop
, &reduction_list
,
3324 n_threads
, &niter_desc
, oacc_kernels_p
);
3327 obstack_free (&parloop_obstack
, NULL
);
3329 /* Parallelization will cause new function calls to be inserted through
3330 which local variables will escape. Reset the points-to solution
3333 pt_solution_reset (&cfun
->gimple_df
->escaped
);
3338 /* Parallelization. */
3342 const pass_data pass_data_parallelize_loops
=
3344 GIMPLE_PASS
, /* type */
3345 "parloops", /* name */
3346 OPTGROUP_LOOP
, /* optinfo_flags */
3347 TV_TREE_PARALLELIZE_LOOPS
, /* tv_id */
3348 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3349 0, /* properties_provided */
3350 0, /* properties_destroyed */
3351 0, /* todo_flags_start */
3352 0, /* todo_flags_finish */
3355 class pass_parallelize_loops
: public gimple_opt_pass
3358 pass_parallelize_loops (gcc::context
*ctxt
)
3359 : gimple_opt_pass (pass_data_parallelize_loops
, ctxt
),
3360 oacc_kernels_p (false)
3363 /* opt_pass methods: */
3364 virtual bool gate (function
*) { return flag_tree_parallelize_loops
> 1; }
3365 virtual unsigned int execute (function
*);
3366 opt_pass
* clone () { return new pass_parallelize_loops (m_ctxt
); }
3367 void set_pass_param (unsigned int n
, bool param
)
3369 gcc_assert (n
== 0);
3370 oacc_kernels_p
= param
;
3374 bool oacc_kernels_p
;
3375 }; // class pass_parallelize_loops
3378 pass_parallelize_loops::execute (function
*fun
)
3380 tree nthreads
= builtin_decl_explicit (BUILT_IN_OMP_GET_NUM_THREADS
);
3381 if (nthreads
== NULL_TREE
)
3384 bool in_loop_pipeline
= scev_initialized_p ();
3385 if (!in_loop_pipeline
)
3386 loop_optimizer_init (LOOPS_NORMAL
3387 | LOOPS_HAVE_RECORDED_EXITS
);
3389 if (number_of_loops (fun
) <= 1)
3392 if (!in_loop_pipeline
)
3394 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
3398 unsigned int todo
= 0;
3399 if (parallelize_loops (oacc_kernels_p
))
3401 fun
->curr_properties
&= ~(PROP_gimple_eomp
);
3403 checking_verify_loop_structure ();
3405 todo
|= TODO_update_ssa
;
3408 if (!in_loop_pipeline
)
3411 loop_optimizer_finalize ();
3420 make_pass_parallelize_loops (gcc::context
*ctxt
)
3422 return new pass_parallelize_loops (ctxt
);