1 /* Loop autoparallelization.
2 Copyright (C) 2006-2015 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 "fold-const.h"
32 #include "hard-reg-set.h"
34 #include "dominance.h"
36 #include "basic-block.h"
37 #include "tree-ssa-alias.h"
38 #include "internal-fn.h"
39 #include "gimple-expr.h"
42 #include "gimple-iterator.h"
43 #include "gimplify-me.h"
44 #include "gimple-walk.h"
45 #include "stor-layout.h"
46 #include "tree-nested.h"
47 #include "gimple-ssa.h"
49 #include "tree-phinodes.h"
50 #include "ssa-iterators.h"
51 #include "stringpool.h"
52 #include "tree-ssanames.h"
53 #include "tree-ssa-loop-ivopts.h"
54 #include "tree-ssa-loop-manip.h"
55 #include "tree-ssa-loop-niter.h"
56 #include "tree-ssa-loop.h"
57 #include "tree-into-ssa.h"
59 #include "tree-data-ref.h"
60 #include "tree-scalar-evolution.h"
61 #include "gimple-pretty-print.h"
62 #include "tree-pass.h"
63 #include "langhooks.h"
64 #include "tree-vectorizer.h"
65 #include "tree-hasher.h"
66 #include "tree-parloops.h"
68 #include "tree-nested.h"
72 /* This pass tries to distribute iterations of loops into several threads.
73 The implementation is straightforward -- for each loop we test whether its
74 iterations are independent, and if it is the case (and some additional
75 conditions regarding profitability and correctness are satisfied), we
76 add GIMPLE_OMP_PARALLEL and GIMPLE_OMP_FOR codes and let omp expansion
79 The most of the complexity is in bringing the code into shape expected
81 -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction
82 variable and that the exit test is at the start of the loop body
83 -- for GIMPLE_OMP_PARALLEL, replacing the references to local addressable
84 variables by accesses through pointers, and breaking up ssa chains
85 by storing the values incoming to the parallelized loop to a structure
86 passed to the new function as an argument (something similar is done
87 in omp gimplification, unfortunately only a small part of the code
91 -- if there are several parallelizable loops in a function, it may be
92 possible to generate the threads just once (using synchronization to
93 ensure that cross-loop dependences are obeyed).
94 -- handling of common reduction patterns for outer loops.
96 More info can also be found at http://gcc.gnu.org/wiki/AutoParInGCC */
99 currently we use vect_force_simple_reduction() to detect reduction patterns.
100 The code transformation will be introduced by an example.
107 for (i = 0; i < N; i++)
117 # sum_29 = PHI <sum_11(5), 1(3)>
118 # i_28 = PHI <i_12(5), 0(3)>
121 sum_11 = D.1795_8 + sum_29;
129 # sum_21 = PHI <sum_11(4)>
130 printf (&"%d"[0], sum_21);
133 after reduction transformation (only relevant parts):
141 # Storing the initial value given by the user. #
143 .paral_data_store.32.sum.27 = 1;
145 #pragma omp parallel num_threads(4)
147 #pragma omp for schedule(static)
149 # The neutral element corresponding to the particular
150 reduction's operation, e.g. 0 for PLUS_EXPR,
151 1 for MULT_EXPR, etc. replaces the user's initial value. #
153 # sum.27_29 = PHI <sum.27_11, 0>
155 sum.27_11 = D.1827_8 + sum.27_29;
159 # Adding this reduction phi is done at create_phi_for_local_result() #
160 # sum.27_56 = PHI <sum.27_11, 0>
163 # Creating the atomic operation is done at
164 create_call_for_reduction_1() #
166 #pragma omp atomic_load
167 D.1839_59 = *&.paral_data_load.33_51->reduction.23;
168 D.1840_60 = sum.27_56 + D.1839_59;
169 #pragma omp atomic_store (D.1840_60);
173 # collecting the result after the join of the threads is done at
174 create_loads_for_reductions().
175 The value computed by the threads is loaded from the
179 .paral_data_load.33_52 = &.paral_data_store.32;
180 sum_37 = .paral_data_load.33_52->sum.27;
181 sum_43 = D.1795_41 + sum_37;
184 # sum_21 = PHI <sum_43, sum_26>
185 printf (&"%d"[0], sum_21);
193 /* Minimal number of iterations of a loop that should be executed in each
195 #define MIN_PER_THREAD 100
197 /* Element of the hashtable, representing a
198 reduction in the current loop. */
199 struct reduction_info
201 gimple reduc_stmt
; /* reduction statement. */
202 gimple reduc_phi
; /* The phi node defining the reduction. */
203 enum tree_code reduction_code
;/* code for the reduction operation. */
204 unsigned reduc_version
; /* SSA_NAME_VERSION of original reduc_phi
206 gphi
*keep_res
; /* The PHI_RESULT of this phi is the resulting value
207 of the reduction variable when existing the loop. */
208 tree initial_value
; /* The initial value of the reduction var before entering the loop. */
209 tree field
; /* the name of the field in the parloop data structure intended for reduction. */
210 tree init
; /* reduction initialization value. */
211 gphi
*new_phi
; /* (helper field) Newly created phi node whose result
212 will be passed to the atomic operation. Represents
213 the local result each thread computed for the reduction
217 /* Reduction info hashtable helpers. */
219 struct reduction_hasher
: free_ptr_hash
<reduction_info
>
221 static inline hashval_t
hash (const reduction_info
*);
222 static inline bool equal (const reduction_info
*, const reduction_info
*);
225 /* Equality and hash functions for hashtab code. */
228 reduction_hasher::equal (const reduction_info
*a
, const reduction_info
*b
)
230 return (a
->reduc_phi
== b
->reduc_phi
);
234 reduction_hasher::hash (const reduction_info
*a
)
236 return a
->reduc_version
;
239 typedef hash_table
<reduction_hasher
> reduction_info_table_type
;
242 static struct reduction_info
*
243 reduction_phi (reduction_info_table_type
*reduction_list
, gimple phi
)
245 struct reduction_info tmpred
, *red
;
247 if (reduction_list
->elements () == 0 || phi
== NULL
)
250 tmpred
.reduc_phi
= phi
;
251 tmpred
.reduc_version
= gimple_uid (phi
);
252 red
= reduction_list
->find (&tmpred
);
257 /* Element of hashtable of names to copy. */
259 struct name_to_copy_elt
261 unsigned version
; /* The version of the name to copy. */
262 tree new_name
; /* The new name used in the copy. */
263 tree field
; /* The field of the structure used to pass the
267 /* Name copies hashtable helpers. */
269 struct name_to_copy_hasher
: free_ptr_hash
<name_to_copy_elt
>
271 static inline hashval_t
hash (const name_to_copy_elt
*);
272 static inline bool equal (const name_to_copy_elt
*, const name_to_copy_elt
*);
275 /* Equality and hash functions for hashtab code. */
278 name_to_copy_hasher::equal (const name_to_copy_elt
*a
, const name_to_copy_elt
*b
)
280 return a
->version
== b
->version
;
284 name_to_copy_hasher::hash (const name_to_copy_elt
*a
)
286 return (hashval_t
) a
->version
;
289 typedef hash_table
<name_to_copy_hasher
> name_to_copy_table_type
;
291 /* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
292 matrix. Rather than use floats, we simply keep a single DENOMINATOR that
293 represents the denominator for every element in the matrix. */
294 typedef struct lambda_trans_matrix_s
296 lambda_matrix matrix
;
300 } *lambda_trans_matrix
;
301 #define LTM_MATRIX(T) ((T)->matrix)
302 #define LTM_ROWSIZE(T) ((T)->rowsize)
303 #define LTM_COLSIZE(T) ((T)->colsize)
304 #define LTM_DENOMINATOR(T) ((T)->denominator)
306 /* Allocate a new transformation matrix. */
308 static lambda_trans_matrix
309 lambda_trans_matrix_new (int colsize
, int rowsize
,
310 struct obstack
* lambda_obstack
)
312 lambda_trans_matrix ret
;
314 ret
= (lambda_trans_matrix
)
315 obstack_alloc (lambda_obstack
, sizeof (struct lambda_trans_matrix_s
));
316 LTM_MATRIX (ret
) = lambda_matrix_new (rowsize
, colsize
, lambda_obstack
);
317 LTM_ROWSIZE (ret
) = rowsize
;
318 LTM_COLSIZE (ret
) = colsize
;
319 LTM_DENOMINATOR (ret
) = 1;
323 /* Multiply a vector VEC by a matrix MAT.
324 MAT is an M*N matrix, and VEC is a vector with length N. The result
325 is stored in DEST which must be a vector of length M. */
328 lambda_matrix_vector_mult (lambda_matrix matrix
, int m
, int n
,
329 lambda_vector vec
, lambda_vector dest
)
333 lambda_vector_clear (dest
, m
);
334 for (i
= 0; i
< m
; i
++)
335 for (j
= 0; j
< n
; j
++)
336 dest
[i
] += matrix
[i
][j
] * vec
[j
];
339 /* Return true if TRANS is a legal transformation matrix that respects
340 the dependence vectors in DISTS and DIRS. The conservative answer
343 "Wolfe proves that a unimodular transformation represented by the
344 matrix T is legal when applied to a loop nest with a set of
345 lexicographically non-negative distance vectors RDG if and only if
346 for each vector d in RDG, (T.d >= 0) is lexicographically positive.
347 i.e.: if and only if it transforms the lexicographically positive
348 distance vectors to lexicographically positive vectors. Note that
349 a unimodular matrix must transform the zero vector (and only it) to
350 the zero vector." S.Muchnick. */
353 lambda_transform_legal_p (lambda_trans_matrix trans
,
355 vec
<ddr_p
> dependence_relations
)
358 lambda_vector distres
;
359 struct data_dependence_relation
*ddr
;
361 gcc_assert (LTM_COLSIZE (trans
) == nb_loops
362 && LTM_ROWSIZE (trans
) == nb_loops
);
364 /* When there are no dependences, the transformation is correct. */
365 if (dependence_relations
.length () == 0)
368 ddr
= dependence_relations
[0];
372 /* When there is an unknown relation in the dependence_relations, we
373 know that it is no worth looking at this loop nest: give up. */
374 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
377 distres
= lambda_vector_new (nb_loops
);
379 /* For each distance vector in the dependence graph. */
380 FOR_EACH_VEC_ELT (dependence_relations
, i
, ddr
)
382 /* Don't care about relations for which we know that there is no
383 dependence, nor about read-read (aka. output-dependences):
384 these data accesses can happen in any order. */
385 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
386 || (DR_IS_READ (DDR_A (ddr
)) && DR_IS_READ (DDR_B (ddr
))))
389 /* Conservatively answer: "this transformation is not valid". */
390 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
393 /* If the dependence could not be captured by a distance vector,
394 conservatively answer that the transform is not valid. */
395 if (DDR_NUM_DIST_VECTS (ddr
) == 0)
398 /* Compute trans.dist_vect */
399 for (j
= 0; j
< DDR_NUM_DIST_VECTS (ddr
); j
++)
401 lambda_matrix_vector_mult (LTM_MATRIX (trans
), nb_loops
, nb_loops
,
402 DDR_DIST_VECT (ddr
, j
), distres
);
404 if (!lambda_vector_lexico_pos (distres
, nb_loops
))
411 /* Data dependency analysis. Returns true if the iterations of LOOP
412 are independent on each other (that is, if we can execute them
416 loop_parallel_p (struct loop
*loop
, struct obstack
* parloop_obstack
)
418 vec
<ddr_p
> dependence_relations
;
419 vec
<data_reference_p
> datarefs
;
420 lambda_trans_matrix trans
;
423 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
425 fprintf (dump_file
, "Considering loop %d\n", loop
->num
);
427 fprintf (dump_file
, "loop is innermost\n");
429 fprintf (dump_file
, "loop NOT innermost\n");
432 /* Check for problems with dependences. If the loop can be reversed,
433 the iterations are independent. */
434 auto_vec
<loop_p
, 3> loop_nest
;
435 datarefs
.create (10);
436 dependence_relations
.create (100);
437 if (! compute_data_dependences_for_loop (loop
, true, &loop_nest
, &datarefs
,
438 &dependence_relations
))
440 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
441 fprintf (dump_file
, " FAILED: cannot analyze data dependencies\n");
445 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
446 dump_data_dependence_relations (dump_file
, dependence_relations
);
448 trans
= lambda_trans_matrix_new (1, 1, parloop_obstack
);
449 LTM_MATRIX (trans
)[0][0] = -1;
451 if (lambda_transform_legal_p (trans
, 1, dependence_relations
))
454 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
455 fprintf (dump_file
, " SUCCESS: may be parallelized\n");
457 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
459 " FAILED: data dependencies exist across iterations\n");
462 free_dependence_relations (dependence_relations
);
463 free_data_refs (datarefs
);
468 /* Return true when LOOP contains basic blocks marked with the
469 BB_IRREDUCIBLE_LOOP flag. */
472 loop_has_blocks_with_irreducible_flag (struct loop
*loop
)
475 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
478 for (i
= 0; i
< loop
->num_nodes
; i
++)
479 if (bbs
[i
]->flags
& BB_IRREDUCIBLE_LOOP
)
488 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
489 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
490 to their addresses that can be reused. The address of OBJ is known to
491 be invariant in the whole function. Other needed statements are placed
495 take_address_of (tree obj
, tree type
, edge entry
,
496 int_tree_htab_type
*decl_address
, gimple_stmt_iterator
*gsi
)
499 tree
*var_p
, name
, addr
;
503 /* Since the address of OBJ is invariant, the trees may be shared.
504 Avoid rewriting unrelated parts of the code. */
505 obj
= unshare_expr (obj
);
507 handled_component_p (*var_p
);
508 var_p
= &TREE_OPERAND (*var_p
, 0))
511 /* Canonicalize the access to base on a MEM_REF. */
513 *var_p
= build_simple_mem_ref (build_fold_addr_expr (*var_p
));
515 /* Assign a canonical SSA name to the address of the base decl used
516 in the address and share it for all accesses and addresses based
518 uid
= DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p
, 0), 0));
521 int_tree_map
*slot
= decl_address
->find_slot (elt
, INSERT
);
526 addr
= TREE_OPERAND (*var_p
, 0);
528 = get_name (TREE_OPERAND (TREE_OPERAND (*var_p
, 0), 0));
530 name
= make_temp_ssa_name (TREE_TYPE (addr
), NULL
, obj_name
);
532 name
= make_ssa_name (TREE_TYPE (addr
));
533 stmt
= gimple_build_assign (name
, addr
);
534 gsi_insert_on_edge_immediate (entry
, stmt
);
542 /* Express the address in terms of the canonical SSA name. */
543 TREE_OPERAND (*var_p
, 0) = name
;
545 return build_fold_addr_expr_with_type (obj
, type
);
547 name
= force_gimple_operand (build_addr (obj
, current_function_decl
),
548 &stmts
, true, NULL_TREE
);
549 if (!gimple_seq_empty_p (stmts
))
550 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
552 if (!useless_type_conversion_p (type
, TREE_TYPE (name
)))
554 name
= force_gimple_operand (fold_convert (type
, name
), &stmts
, true,
556 if (!gimple_seq_empty_p (stmts
))
557 gsi_insert_seq_before (gsi
, stmts
, GSI_SAME_STMT
);
563 /* Callback for htab_traverse. Create the initialization statement
564 for reduction described in SLOT, and place it at the preheader of
565 the loop described in DATA. */
568 initialize_reductions (reduction_info
**slot
, struct loop
*loop
)
571 tree bvar
, type
, arg
;
574 struct reduction_info
*const reduc
= *slot
;
576 /* Create initialization in preheader:
577 reduction_variable = initialization value of reduction. */
579 /* In the phi node at the header, replace the argument coming
580 from the preheader with the reduction initialization value. */
582 /* Create a new variable to initialize the reduction. */
583 type
= TREE_TYPE (PHI_RESULT (reduc
->reduc_phi
));
584 bvar
= create_tmp_var (type
, "reduction");
586 c
= build_omp_clause (gimple_location (reduc
->reduc_stmt
),
587 OMP_CLAUSE_REDUCTION
);
588 OMP_CLAUSE_REDUCTION_CODE (c
) = reduc
->reduction_code
;
589 OMP_CLAUSE_DECL (c
) = SSA_NAME_VAR (gimple_assign_lhs (reduc
->reduc_stmt
));
591 init
= omp_reduction_init (c
, TREE_TYPE (bvar
));
594 /* Replace the argument representing the initialization value
595 with the initialization value for the reduction (neutral
596 element for the particular operation, e.g. 0 for PLUS_EXPR,
597 1 for MULT_EXPR, etc).
598 Keep the old value in a new variable "reduction_initial",
599 that will be taken in consideration after the parallel
600 computing is done. */
602 e
= loop_preheader_edge (loop
);
603 arg
= PHI_ARG_DEF_FROM_EDGE (reduc
->reduc_phi
, e
);
604 /* Create new variable to hold the initial value. */
606 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
607 (reduc
->reduc_phi
, loop_preheader_edge (loop
)), init
);
608 reduc
->initial_value
= arg
;
614 struct walk_stmt_info info
;
616 int_tree_htab_type
*decl_address
;
617 gimple_stmt_iterator
*gsi
;
622 /* Eliminates references to local variables in *TP out of the single
623 entry single exit region starting at DTA->ENTRY.
624 DECL_ADDRESS contains addresses of the references that had their
625 address taken already. If the expression is changed, CHANGED is
626 set to true. Callback for walk_tree. */
629 eliminate_local_variables_1 (tree
*tp
, int *walk_subtrees
, void *data
)
631 struct elv_data
*const dta
= (struct elv_data
*) data
;
632 tree t
= *tp
, var
, addr
, addr_type
, type
, obj
;
638 if (!SSA_VAR_P (t
) || DECL_EXTERNAL (t
))
641 type
= TREE_TYPE (t
);
642 addr_type
= build_pointer_type (type
);
643 addr
= take_address_of (t
, addr_type
, dta
->entry
, dta
->decl_address
,
645 if (dta
->gsi
== NULL
&& addr
== NULL_TREE
)
651 *tp
= build_simple_mem_ref (addr
);
657 if (TREE_CODE (t
) == ADDR_EXPR
)
659 /* ADDR_EXPR may appear in two contexts:
660 -- as a gimple operand, when the address taken is a function invariant
661 -- as gimple rhs, when the resulting address in not a function
663 We do not need to do anything special in the latter case (the base of
664 the memory reference whose address is taken may be replaced in the
665 DECL_P case). The former case is more complicated, as we need to
666 ensure that the new address is still a gimple operand. Thus, it
667 is not sufficient to replace just the base of the memory reference --
668 we need to move the whole computation of the address out of the
670 if (!is_gimple_val (t
))
674 obj
= TREE_OPERAND (t
, 0);
675 var
= get_base_address (obj
);
676 if (!var
|| !SSA_VAR_P (var
) || DECL_EXTERNAL (var
))
679 addr_type
= TREE_TYPE (t
);
680 addr
= take_address_of (obj
, addr_type
, dta
->entry
, dta
->decl_address
,
682 if (dta
->gsi
== NULL
&& addr
== NULL_TREE
)
699 /* Moves the references to local variables in STMT at *GSI out of the single
700 entry single exit region starting at ENTRY. DECL_ADDRESS contains
701 addresses of the references that had their address taken
705 eliminate_local_variables_stmt (edge entry
, gimple_stmt_iterator
*gsi
,
706 int_tree_htab_type
*decl_address
)
709 gimple stmt
= gsi_stmt (*gsi
);
711 memset (&dta
.info
, '\0', sizeof (dta
.info
));
713 dta
.decl_address
= decl_address
;
717 if (gimple_debug_bind_p (stmt
))
720 walk_tree (gimple_debug_bind_get_value_ptr (stmt
),
721 eliminate_local_variables_1
, &dta
.info
, NULL
);
724 gimple_debug_bind_reset_value (stmt
);
728 else if (gimple_clobber_p (stmt
))
730 stmt
= gimple_build_nop ();
731 gsi_replace (gsi
, stmt
, false);
737 walk_gimple_op (stmt
, eliminate_local_variables_1
, &dta
.info
);
744 /* Eliminates the references to local variables from the single entry
745 single exit region between the ENTRY and EXIT edges.
748 1) Taking address of a local variable -- these are moved out of the
749 region (and temporary variable is created to hold the address if
752 2) Dereferencing a local variable -- these are replaced with indirect
756 eliminate_local_variables (edge entry
, edge exit
)
759 auto_vec
<basic_block
, 3> body
;
761 gimple_stmt_iterator gsi
;
762 bool has_debug_stmt
= false;
763 int_tree_htab_type
decl_address (10);
764 basic_block entry_bb
= entry
->src
;
765 basic_block exit_bb
= exit
->dest
;
767 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
769 FOR_EACH_VEC_ELT (body
, i
, bb
)
770 if (bb
!= entry_bb
&& bb
!= exit_bb
)
771 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
772 if (is_gimple_debug (gsi_stmt (gsi
)))
774 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
775 has_debug_stmt
= true;
778 eliminate_local_variables_stmt (entry
, &gsi
, &decl_address
);
781 FOR_EACH_VEC_ELT (body
, i
, bb
)
782 if (bb
!= entry_bb
&& bb
!= exit_bb
)
783 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
784 if (gimple_debug_bind_p (gsi_stmt (gsi
)))
785 eliminate_local_variables_stmt (entry
, &gsi
, &decl_address
);
788 /* Returns true if expression EXPR is not defined between ENTRY and
789 EXIT, i.e. if all its operands are defined outside of the region. */
792 expr_invariant_in_region_p (edge entry
, edge exit
, tree expr
)
794 basic_block entry_bb
= entry
->src
;
795 basic_block exit_bb
= exit
->dest
;
798 if (is_gimple_min_invariant (expr
))
801 if (TREE_CODE (expr
) == SSA_NAME
)
803 def_bb
= gimple_bb (SSA_NAME_DEF_STMT (expr
));
805 && dominated_by_p (CDI_DOMINATORS
, def_bb
, entry_bb
)
806 && !dominated_by_p (CDI_DOMINATORS
, def_bb
, exit_bb
))
815 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
816 The copies are stored to NAME_COPIES, if NAME was already duplicated,
817 its duplicate stored in NAME_COPIES is returned.
819 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
820 duplicated, storing the copies in DECL_COPIES. */
823 separate_decls_in_region_name (tree name
, name_to_copy_table_type
*name_copies
,
824 int_tree_htab_type
*decl_copies
,
827 tree copy
, var
, var_copy
;
828 unsigned idx
, uid
, nuid
;
829 struct int_tree_map ielt
;
830 struct name_to_copy_elt elt
, *nelt
;
831 name_to_copy_elt
**slot
;
834 if (TREE_CODE (name
) != SSA_NAME
)
837 idx
= SSA_NAME_VERSION (name
);
839 slot
= name_copies
->find_slot_with_hash (&elt
, idx
,
840 copy_name_p
? INSERT
: NO_INSERT
);
842 return (*slot
)->new_name
;
846 copy
= duplicate_ssa_name (name
, NULL
);
847 nelt
= XNEW (struct name_to_copy_elt
);
849 nelt
->new_name
= copy
;
850 nelt
->field
= NULL_TREE
;
859 var
= SSA_NAME_VAR (name
);
863 uid
= DECL_UID (var
);
865 dslot
= decl_copies
->find_slot_with_hash (ielt
, uid
, INSERT
);
868 var_copy
= create_tmp_var (TREE_TYPE (var
), get_name (var
));
869 DECL_GIMPLE_REG_P (var_copy
) = DECL_GIMPLE_REG_P (var
);
871 dslot
->to
= var_copy
;
873 /* Ensure that when we meet this decl next time, we won't duplicate
875 nuid
= DECL_UID (var_copy
);
877 dslot
= decl_copies
->find_slot_with_hash (ielt
, nuid
, INSERT
);
878 gcc_assert (!dslot
->to
);
880 dslot
->to
= var_copy
;
883 var_copy
= dslot
->to
;
885 replace_ssa_name_symbol (copy
, var_copy
);
889 /* Finds the ssa names used in STMT that are defined outside the
890 region between ENTRY and EXIT and replaces such ssa names with
891 their duplicates. The duplicates are stored to NAME_COPIES. Base
892 decls of all ssa names used in STMT (including those defined in
893 LOOP) are replaced with the new temporary variables; the
894 replacement decls are stored in DECL_COPIES. */
897 separate_decls_in_region_stmt (edge entry
, edge exit
, gimple stmt
,
898 name_to_copy_table_type
*name_copies
,
899 int_tree_htab_type
*decl_copies
)
907 FOR_EACH_PHI_OR_STMT_DEF (def
, stmt
, oi
, SSA_OP_DEF
)
909 name
= DEF_FROM_PTR (def
);
910 gcc_assert (TREE_CODE (name
) == SSA_NAME
);
911 copy
= separate_decls_in_region_name (name
, name_copies
, decl_copies
,
913 gcc_assert (copy
== name
);
916 FOR_EACH_PHI_OR_STMT_USE (use
, stmt
, oi
, SSA_OP_USE
)
918 name
= USE_FROM_PTR (use
);
919 if (TREE_CODE (name
) != SSA_NAME
)
922 copy_name_p
= expr_invariant_in_region_p (entry
, exit
, name
);
923 copy
= separate_decls_in_region_name (name
, name_copies
, decl_copies
,
929 /* Finds the ssa names used in STMT that are defined outside the
930 region between ENTRY and EXIT and replaces such ssa names with
931 their duplicates. The duplicates are stored to NAME_COPIES. Base
932 decls of all ssa names used in STMT (including those defined in
933 LOOP) are replaced with the new temporary variables; the
934 replacement decls are stored in DECL_COPIES. */
937 separate_decls_in_region_debug (gimple stmt
,
938 name_to_copy_table_type
*name_copies
,
939 int_tree_htab_type
*decl_copies
)
944 struct int_tree_map ielt
;
945 struct name_to_copy_elt elt
;
946 name_to_copy_elt
**slot
;
949 if (gimple_debug_bind_p (stmt
))
950 var
= gimple_debug_bind_get_var (stmt
);
951 else if (gimple_debug_source_bind_p (stmt
))
952 var
= gimple_debug_source_bind_get_var (stmt
);
955 if (TREE_CODE (var
) == DEBUG_EXPR_DECL
|| TREE_CODE (var
) == LABEL_DECL
)
957 gcc_assert (DECL_P (var
) && SSA_VAR_P (var
));
958 ielt
.uid
= DECL_UID (var
);
959 dslot
= decl_copies
->find_slot_with_hash (ielt
, ielt
.uid
, NO_INSERT
);
962 if (gimple_debug_bind_p (stmt
))
963 gimple_debug_bind_set_var (stmt
, dslot
->to
);
964 else if (gimple_debug_source_bind_p (stmt
))
965 gimple_debug_source_bind_set_var (stmt
, dslot
->to
);
967 FOR_EACH_PHI_OR_STMT_USE (use
, stmt
, oi
, SSA_OP_USE
)
969 name
= USE_FROM_PTR (use
);
970 if (TREE_CODE (name
) != SSA_NAME
)
973 elt
.version
= SSA_NAME_VERSION (name
);
974 slot
= name_copies
->find_slot_with_hash (&elt
, elt
.version
, NO_INSERT
);
977 gimple_debug_bind_reset_value (stmt
);
982 SET_USE (use
, (*slot
)->new_name
);
988 /* Callback for htab_traverse. Adds a field corresponding to the reduction
989 specified in SLOT. The type is passed in DATA. */
992 add_field_for_reduction (reduction_info
**slot
, tree type
)
995 struct reduction_info
*const red
= *slot
;
996 tree var
= gimple_assign_lhs (red
->reduc_stmt
);
997 tree field
= build_decl (gimple_location (red
->reduc_stmt
), FIELD_DECL
,
998 SSA_NAME_IDENTIFIER (var
), TREE_TYPE (var
));
1000 insert_field_into_struct (type
, field
);
1007 /* Callback for htab_traverse. Adds a field corresponding to a ssa name
1008 described in SLOT. The type is passed in DATA. */
1011 add_field_for_name (name_to_copy_elt
**slot
, tree type
)
1013 struct name_to_copy_elt
*const elt
= *slot
;
1014 tree name
= ssa_name (elt
->version
);
1015 tree field
= build_decl (UNKNOWN_LOCATION
,
1016 FIELD_DECL
, SSA_NAME_IDENTIFIER (name
),
1019 insert_field_into_struct (type
, field
);
1025 /* Callback for htab_traverse. A local result is the intermediate result
1026 computed by a single
1027 thread, or the initial value in case no iteration was executed.
1028 This function creates a phi node reflecting these values.
1029 The phi's result will be stored in NEW_PHI field of the
1030 reduction's data structure. */
1033 create_phi_for_local_result (reduction_info
**slot
, struct loop
*loop
)
1035 struct reduction_info
*const reduc
= *slot
;
1038 basic_block store_bb
;
1040 source_location locus
;
1042 /* STORE_BB is the block where the phi
1043 should be stored. It is the destination of the loop exit.
1044 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
1045 store_bb
= FALLTHRU_EDGE (loop
->latch
)->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 (loop
->latch
))
1053 e
= EDGE_PRED (store_bb
, 1);
1055 e
= EDGE_PRED (store_bb
, 0);
1056 local_res
= copy_ssa_name (gimple_assign_lhs (reduc
->reduc_stmt
));
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
, gimple_assign_lhs (reduc
->reduc_stmt
),
1061 FALLTHRU_EDGE (loop
->latch
), 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 load_struct
= build_simple_mem_ref (clsn_data
->load
);
1096 t
= build3 (COMPONENT_REF
, type
, load_struct
, reduc
->field
, NULL_TREE
);
1098 addr
= build_addr (t
, current_function_decl
);
1100 /* Create phi node. */
1101 bb
= clsn_data
->load_bb
;
1103 gsi
= gsi_last_bb (bb
);
1104 e
= split_block (bb
, gsi_stmt (gsi
));
1107 tmp_load
= create_tmp_var (TREE_TYPE (TREE_TYPE (addr
)));
1108 tmp_load
= make_ssa_name (tmp_load
);
1109 load
= gimple_build_omp_atomic_load (tmp_load
, addr
);
1110 SSA_NAME_DEF_STMT (tmp_load
) = load
;
1111 gsi
= gsi_start_bb (new_bb
);
1112 gsi_insert_after (&gsi
, load
, GSI_NEW_STMT
);
1114 e
= split_block (new_bb
, load
);
1116 gsi
= gsi_start_bb (new_bb
);
1118 x
= fold_build2 (reduc
->reduction_code
,
1119 TREE_TYPE (PHI_RESULT (reduc
->new_phi
)), ref
,
1120 PHI_RESULT (reduc
->new_phi
));
1122 name
= force_gimple_operand_gsi (&gsi
, x
, true, NULL_TREE
, true,
1123 GSI_CONTINUE_LINKING
);
1125 gsi_insert_after (&gsi
, gimple_build_omp_atomic_store (name
), GSI_NEW_STMT
);
1129 /* Create the atomic operation at the join point of the threads.
1130 REDUCTION_LIST describes the reductions in the LOOP.
1131 LD_ST_DATA describes the shared data structure where
1132 shared data is stored in and loaded from. */
1134 create_call_for_reduction (struct loop
*loop
,
1135 reduction_info_table_type
*reduction_list
,
1136 struct clsn_data
*ld_st_data
)
1138 reduction_list
->traverse
<struct loop
*, create_phi_for_local_result
> (loop
);
1139 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
1140 ld_st_data
->load_bb
= FALLTHRU_EDGE (loop
->latch
)->dest
;
1142 ->traverse
<struct clsn_data
*, create_call_for_reduction_1
> (ld_st_data
);
1145 /* Callback for htab_traverse. Loads the final reduction value at the
1146 join point of all threads, and inserts it in the right place. */
1149 create_loads_for_reductions (reduction_info
**slot
, struct clsn_data
*clsn_data
)
1151 struct reduction_info
*const red
= *slot
;
1153 gimple_stmt_iterator gsi
;
1154 tree type
= TREE_TYPE (gimple_assign_lhs (red
->reduc_stmt
));
1159 gsi
= gsi_after_labels (clsn_data
->load_bb
);
1160 load_struct
= build_simple_mem_ref (clsn_data
->load
);
1161 load_struct
= build3 (COMPONENT_REF
, type
, load_struct
, red
->field
,
1165 name
= PHI_RESULT (red
->keep_res
);
1166 stmt
= gimple_build_assign (name
, x
);
1168 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1170 for (gsi
= gsi_start_phis (gimple_bb (red
->keep_res
));
1171 !gsi_end_p (gsi
); gsi_next (&gsi
))
1172 if (gsi_stmt (gsi
) == red
->keep_res
)
1174 remove_phi_node (&gsi
, false);
1180 /* Load the reduction result that was stored in LD_ST_DATA.
1181 REDUCTION_LIST describes the list of reductions that the
1182 loads should be generated for. */
1184 create_final_loads_for_reduction (reduction_info_table_type
*reduction_list
,
1185 struct clsn_data
*ld_st_data
)
1187 gimple_stmt_iterator gsi
;
1191 gsi
= gsi_after_labels (ld_st_data
->load_bb
);
1192 t
= build_fold_addr_expr (ld_st_data
->store
);
1193 stmt
= gimple_build_assign (ld_st_data
->load
, t
);
1195 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1198 ->traverse
<struct clsn_data
*, create_loads_for_reductions
> (ld_st_data
);
1202 /* Callback for htab_traverse. Store the neutral value for the
1203 particular reduction's operation, e.g. 0 for PLUS_EXPR,
1204 1 for MULT_EXPR, etc. into the reduction field.
1205 The reduction is specified in SLOT. The store information is
1209 create_stores_for_reduction (reduction_info
**slot
, struct clsn_data
*clsn_data
)
1211 struct reduction_info
*const red
= *slot
;
1214 gimple_stmt_iterator gsi
;
1215 tree type
= TREE_TYPE (gimple_assign_lhs (red
->reduc_stmt
));
1217 gsi
= gsi_last_bb (clsn_data
->store_bb
);
1218 t
= build3 (COMPONENT_REF
, type
, clsn_data
->store
, red
->field
, NULL_TREE
);
1219 stmt
= gimple_build_assign (t
, red
->initial_value
);
1220 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1225 /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
1226 store to a field of STORE in STORE_BB for the ssa name and its duplicate
1227 specified in SLOT. */
1230 create_loads_and_stores_for_name (name_to_copy_elt
**slot
,
1231 struct clsn_data
*clsn_data
)
1233 struct name_to_copy_elt
*const elt
= *slot
;
1236 gimple_stmt_iterator gsi
;
1237 tree type
= TREE_TYPE (elt
->new_name
);
1240 gsi
= gsi_last_bb (clsn_data
->store_bb
);
1241 t
= build3 (COMPONENT_REF
, type
, clsn_data
->store
, elt
->field
, NULL_TREE
);
1242 stmt
= gimple_build_assign (t
, ssa_name (elt
->version
));
1243 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1245 gsi
= gsi_last_bb (clsn_data
->load_bb
);
1246 load_struct
= build_simple_mem_ref (clsn_data
->load
);
1247 t
= build3 (COMPONENT_REF
, type
, load_struct
, elt
->field
, NULL_TREE
);
1248 stmt
= gimple_build_assign (elt
->new_name
, t
);
1249 gsi_insert_after (&gsi
, stmt
, GSI_NEW_STMT
);
1254 /* Moves all the variables used in LOOP and defined outside of it (including
1255 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1256 name) to a structure created for this purpose. The code
1264 is transformed this way:
1279 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1280 pointer `new' is intentionally not initialized (the loop will be split to a
1281 separate function later, and `new' will be initialized from its arguments).
1282 LD_ST_DATA holds information about the shared data structure used to pass
1283 information among the threads. It is initialized here, and
1284 gen_parallel_loop will pass it to create_call_for_reduction that
1285 needs this information. REDUCTION_LIST describes the reductions
1289 separate_decls_in_region (edge entry
, edge exit
,
1290 reduction_info_table_type
*reduction_list
,
1291 tree
*arg_struct
, tree
*new_arg_struct
,
1292 struct clsn_data
*ld_st_data
)
1295 basic_block bb1
= split_edge (entry
);
1296 basic_block bb0
= single_pred (bb1
);
1297 name_to_copy_table_type
name_copies (10);
1298 int_tree_htab_type
decl_copies (10);
1300 tree type
, type_name
, nvar
;
1301 gimple_stmt_iterator gsi
;
1302 struct clsn_data clsn_data
;
1303 auto_vec
<basic_block
, 3> body
;
1305 basic_block entry_bb
= bb1
;
1306 basic_block exit_bb
= exit
->dest
;
1307 bool has_debug_stmt
= false;
1309 entry
= single_succ_edge (entry_bb
);
1310 gather_blocks_in_sese_region (entry_bb
, exit_bb
, &body
);
1312 FOR_EACH_VEC_ELT (body
, i
, bb
)
1314 if (bb
!= entry_bb
&& bb
!= exit_bb
)
1316 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1317 separate_decls_in_region_stmt (entry
, exit
, gsi_stmt (gsi
),
1318 &name_copies
, &decl_copies
);
1320 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1322 gimple stmt
= gsi_stmt (gsi
);
1324 if (is_gimple_debug (stmt
))
1325 has_debug_stmt
= true;
1327 separate_decls_in_region_stmt (entry
, exit
, stmt
,
1328 &name_copies
, &decl_copies
);
1333 /* Now process debug bind stmts. We must not create decls while
1334 processing debug stmts, so we defer their processing so as to
1335 make sure we will have debug info for as many variables as
1336 possible (all of those that were dealt with in the loop above),
1337 and discard those for which we know there's nothing we can
1340 FOR_EACH_VEC_ELT (body
, i
, bb
)
1341 if (bb
!= entry_bb
&& bb
!= exit_bb
)
1343 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);)
1345 gimple stmt
= gsi_stmt (gsi
);
1347 if (is_gimple_debug (stmt
))
1349 if (separate_decls_in_region_debug (stmt
, &name_copies
,
1352 gsi_remove (&gsi
, true);
1361 if (name_copies
.elements () == 0 && reduction_list
->elements () == 0)
1363 /* It may happen that there is nothing to copy (if there are only
1364 loop carried and external variables in the loop). */
1366 *new_arg_struct
= NULL
;
1370 /* Create the type for the structure to store the ssa names to. */
1371 type
= lang_hooks
.types
.make_type (RECORD_TYPE
);
1372 type_name
= build_decl (UNKNOWN_LOCATION
,
1373 TYPE_DECL
, create_tmp_var_name (".paral_data"),
1375 TYPE_NAME (type
) = type_name
;
1377 name_copies
.traverse
<tree
, add_field_for_name
> (type
);
1378 if (reduction_list
&& reduction_list
->elements () > 0)
1380 /* Create the fields for reductions. */
1381 reduction_list
->traverse
<tree
, add_field_for_reduction
> (type
);
1385 /* Create the loads and stores. */
1386 *arg_struct
= create_tmp_var (type
, ".paral_data_store");
1387 nvar
= create_tmp_var (build_pointer_type (type
), ".paral_data_load");
1388 *new_arg_struct
= make_ssa_name (nvar
);
1390 ld_st_data
->store
= *arg_struct
;
1391 ld_st_data
->load
= *new_arg_struct
;
1392 ld_st_data
->store_bb
= bb0
;
1393 ld_st_data
->load_bb
= bb1
;
1396 .traverse
<struct clsn_data
*, create_loads_and_stores_for_name
>
1399 /* Load the calculation from memory (after the join of the threads). */
1401 if (reduction_list
&& reduction_list
->elements () > 0)
1404 ->traverse
<struct clsn_data
*, create_stores_for_reduction
>
1406 clsn_data
.load
= make_ssa_name (nvar
);
1407 clsn_data
.load_bb
= exit
->dest
;
1408 clsn_data
.store
= ld_st_data
->store
;
1409 create_final_loads_for_reduction (reduction_list
, &clsn_data
);
1414 /* Returns true if FN was created to run in parallel. */
1417 parallelized_function_p (tree fndecl
)
1419 cgraph_node
*node
= cgraph_node::get (fndecl
);
1420 gcc_assert (node
!= NULL
);
1421 return node
->parallelized_function
;
1424 /* Creates and returns an empty function that will receive the body of
1425 a parallelized loop. */
1428 create_loop_fn (location_t loc
)
1432 tree decl
, type
, name
, t
;
1433 struct function
*act_cfun
= cfun
;
1434 static unsigned loopfn_num
;
1436 loc
= LOCATION_LOCUS (loc
);
1437 snprintf (buf
, 100, "%s.$loopfn", current_function_name ());
1438 ASM_FORMAT_PRIVATE_NAME (tname
, buf
, loopfn_num
++);
1439 clean_symbol_name (tname
);
1440 name
= get_identifier (tname
);
1441 type
= build_function_type_list (void_type_node
, ptr_type_node
, NULL_TREE
);
1443 decl
= build_decl (loc
, FUNCTION_DECL
, name
, type
);
1444 TREE_STATIC (decl
) = 1;
1445 TREE_USED (decl
) = 1;
1446 DECL_ARTIFICIAL (decl
) = 1;
1447 DECL_IGNORED_P (decl
) = 0;
1448 TREE_PUBLIC (decl
) = 0;
1449 DECL_UNINLINABLE (decl
) = 1;
1450 DECL_EXTERNAL (decl
) = 0;
1451 DECL_CONTEXT (decl
) = NULL_TREE
;
1452 DECL_INITIAL (decl
) = make_node (BLOCK
);
1454 t
= build_decl (loc
, RESULT_DECL
, NULL_TREE
, void_type_node
);
1455 DECL_ARTIFICIAL (t
) = 1;
1456 DECL_IGNORED_P (t
) = 1;
1457 DECL_RESULT (decl
) = t
;
1459 t
= build_decl (loc
, PARM_DECL
, get_identifier (".paral_data_param"),
1461 DECL_ARTIFICIAL (t
) = 1;
1462 DECL_ARG_TYPE (t
) = ptr_type_node
;
1463 DECL_CONTEXT (t
) = decl
;
1465 DECL_ARGUMENTS (decl
) = t
;
1467 allocate_struct_function (decl
, false);
1469 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1471 set_cfun (act_cfun
);
1476 /* Replace uses of NAME by VAL in block BB. */
1479 replace_uses_in_bb_by (tree name
, tree val
, basic_block bb
)
1482 imm_use_iterator imm_iter
;
1484 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, name
)
1486 if (gimple_bb (use_stmt
) != bb
)
1489 use_operand_p use_p
;
1490 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1491 SET_USE (use_p
, val
);
1495 /* Replace uses of NAME by VAL in blocks BBS. */
1498 replace_uses_in_bbs_by (tree name
, tree val
, bitmap bbs
)
1501 imm_use_iterator imm_iter
;
1503 FOR_EACH_IMM_USE_STMT (use_stmt
, imm_iter
, name
)
1505 if (!bitmap_bit_p (bbs
, gimple_bb (use_stmt
)->index
))
1508 use_operand_p use_p
;
1509 FOR_EACH_IMM_USE_ON_STMT (use_p
, imm_iter
)
1510 SET_USE (use_p
, val
);
1514 /* Do transformation from:
1521 ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1522 sum_a = PHI <sum_init (preheader), sum_b (latch)>
1526 sum_b = sum_a + sum_update
1534 ivtmp_b = ivtmp_a + 1;
1538 sum_z = PHI <sum_b (cond[1])>
1540 [1] Where <bb cond> is single_pred (bb latch); In the simplest case,
1550 ivtmp_a = PHI <ivtmp_c (latch)>
1551 sum_a = PHI <sum_c (latch)>
1555 sum_b = sum_a + sum_update
1560 ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1561 sum_c = PHI <sum_init (preheader), sum_b (latch)>
1562 if (ivtmp_c < n + 1)
1568 ivtmp_b = ivtmp_a + 1;
1572 sum_z = PHI <sum_c (newheader)>
1575 In unified diff format:
1580 + goto <bb newheader>
1583 - ivtmp_a = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1584 - sum_a = PHI <sum_init (preheader), sum_b (latch)>
1585 + ivtmp_a = PHI <ivtmp_c (latch)>
1586 + sum_a = PHI <sum_c (latch)>
1590 sum_b = sum_a + sum_update
1597 + ivtmp_c = PHI <ivtmp_init (preheader), ivtmp_b (latch)>
1598 + sum_c = PHI <sum_init (preheader), sum_b (latch)>
1599 + if (ivtmp_c < n + 1)
1605 ivtmp_b = ivtmp_a + 1;
1607 + goto <bb newheader>
1610 - sum_z = PHI <sum_b (cond[1])>
1611 + sum_z = PHI <sum_c (newheader)>
1613 Note: the example does not show any virtual phis, but these are handled more
1614 or less as reductions.
1617 Moves the exit condition of LOOP to the beginning of its header.
1618 REDUCTION_LIST describes the reductions in LOOP. BOUND is the new loop
1622 transform_to_exit_first_loop_alt (struct loop
*loop
,
1623 reduction_info_table_type
*reduction_list
,
1626 basic_block header
= loop
->header
;
1627 basic_block latch
= loop
->latch
;
1628 edge exit
= single_dom_exit (loop
);
1629 basic_block exit_block
= exit
->dest
;
1630 gcond
*cond_stmt
= as_a
<gcond
*> (last_stmt (exit
->src
));
1631 tree control
= gimple_cond_lhs (cond_stmt
);
1634 /* Gather the bbs dominated by the exit block. */
1635 bitmap exit_dominated
= BITMAP_ALLOC (NULL
);
1636 bitmap_set_bit (exit_dominated
, exit_block
->index
);
1637 vec
<basic_block
> exit_dominated_vec
1638 = get_dominated_by (CDI_DOMINATORS
, exit_block
);
1642 FOR_EACH_VEC_ELT (exit_dominated_vec
, i
, dom_bb
)
1643 bitmap_set_bit (exit_dominated
, dom_bb
->index
);
1645 exit_dominated_vec
.release ();
1647 /* Create the new_header block. */
1648 basic_block new_header
= split_block_before_cond_jump (exit
->src
);
1649 edge split_edge
= single_pred_edge (new_header
);
1651 /* Redirect entry edge to new_header. */
1652 edge entry
= loop_preheader_edge (loop
);
1653 e
= redirect_edge_and_branch (entry
, new_header
);
1654 gcc_assert (e
== entry
);
1656 /* Redirect post_inc_edge to new_header. */
1657 edge post_inc_edge
= single_succ_edge (latch
);
1658 e
= redirect_edge_and_branch (post_inc_edge
, new_header
);
1659 gcc_assert (e
== post_inc_edge
);
1661 /* Redirect post_cond_edge to header. */
1662 edge post_cond_edge
= single_pred_edge (latch
);
1663 e
= redirect_edge_and_branch (post_cond_edge
, header
);
1664 gcc_assert (e
== post_cond_edge
);
1666 /* Redirect split_edge to latch. */
1667 e
= redirect_edge_and_branch (split_edge
, latch
);
1668 gcc_assert (e
== split_edge
);
1670 /* Set the new loop bound. */
1671 gimple_cond_set_rhs (cond_stmt
, bound
);
1672 update_stmt (cond_stmt
);
1674 /* Repair the ssa. */
1675 vec
<edge_var_map
> *v
= redirect_edge_var_map_vector (post_inc_edge
);
1678 for (gsi
= gsi_start_phis (header
), i
= 0;
1679 !gsi_end_p (gsi
) && v
->iterate (i
, &vm
);
1680 gsi_next (&gsi
), i
++)
1682 gphi
*phi
= gsi
.phi ();
1683 tree res_a
= PHI_RESULT (phi
);
1685 /* Create new phi. */
1686 tree res_c
= copy_ssa_name (res_a
, phi
);
1687 gphi
*nphi
= create_phi_node (res_c
, new_header
);
1689 /* Replace ivtmp_a with ivtmp_c in condition 'if (ivtmp_a < n)'. */
1690 replace_uses_in_bb_by (res_a
, res_c
, new_header
);
1692 /* Replace ivtmp/sum_b with ivtmp/sum_c in header phi. */
1693 add_phi_arg (phi
, res_c
, post_cond_edge
, UNKNOWN_LOCATION
);
1695 /* Replace sum_b with sum_c in exit phi. Loop-closed ssa does not hold
1696 for virtuals, so we cannot get away with exit_block only. */
1697 tree res_b
= redirect_edge_var_map_def (vm
);
1698 replace_uses_in_bbs_by (res_b
, res_c
, exit_dominated
);
1700 struct reduction_info
*red
= reduction_phi (reduction_list
, phi
);
1701 gcc_assert (virtual_operand_p (res_a
)
1707 /* Register the new reduction phi. */
1708 red
->reduc_phi
= nphi
;
1709 gimple_set_uid (red
->reduc_phi
, red
->reduc_version
);
1712 gcc_assert (gsi_end_p (gsi
) && !v
->iterate (i
, &vm
));
1713 BITMAP_FREE (exit_dominated
);
1715 /* Set the preheader argument of the new phis to ivtmp/sum_init. */
1716 flush_pending_stmts (entry
);
1718 /* Set the latch arguments of the new phis to ivtmp/sum_b. */
1719 flush_pending_stmts (post_inc_edge
);
1721 /* Register the reduction exit phis. */
1722 for (gphi_iterator gsi
= gsi_start_phis (exit_block
);
1726 gphi
*phi
= gsi
.phi ();
1727 tree res_z
= PHI_RESULT (phi
);
1728 if (virtual_operand_p (res_z
))
1731 tree res_c
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1732 gimple reduc_phi
= SSA_NAME_DEF_STMT (res_c
);
1733 struct reduction_info
*red
= reduction_phi (reduction_list
, reduc_phi
);
1735 red
->keep_res
= phi
;
1738 /* We're going to cancel the loop at the end of gen_parallel_loop, but until
1739 then we're still using some fields, so only bother about fields that are
1740 still used: header and latch.
1741 The loop has a new header bb, so we update it. The latch bb stays the
1743 loop
->header
= new_header
;
1745 /* Recalculate dominance info. */
1746 free_dominance_info (CDI_DOMINATORS
);
1747 calculate_dominance_info (CDI_DOMINATORS
);
1750 /* Tries to moves the exit condition of LOOP to the beginning of its header
1751 without duplication of the loop body. NIT is the number of iterations of the
1752 loop. REDUCTION_LIST describes the reductions in LOOP. Return true if
1753 transformation is successful. */
1756 try_transform_to_exit_first_loop_alt (struct loop
*loop
,
1757 reduction_info_table_type
*reduction_list
,
1760 /* Check whether the latch contains a single statement. */
1761 if (!gimple_seq_nondebug_singleton_p (bb_seq (loop
->latch
)))
1764 /* Check whether the latch contains the loop iv increment. */
1765 edge back
= single_succ_edge (loop
->latch
);
1766 edge exit
= single_dom_exit (loop
);
1767 gcond
*cond_stmt
= as_a
<gcond
*> (last_stmt (exit
->src
));
1768 tree control
= gimple_cond_lhs (cond_stmt
);
1769 gphi
*phi
= as_a
<gphi
*> (SSA_NAME_DEF_STMT (control
));
1770 tree inc_res
= gimple_phi_arg_def (phi
, back
->dest_idx
);
1771 if (gimple_bb (SSA_NAME_DEF_STMT (inc_res
)) != loop
->latch
)
1774 /* Check whether there's no code between the loop condition and the latch. */
1775 if (!single_pred_p (loop
->latch
)
1776 || single_pred (loop
->latch
) != exit
->src
)
1779 tree alt_bound
= NULL_TREE
;
1780 tree nit_type
= TREE_TYPE (nit
);
1782 /* Figure out whether nit + 1 overflows. */
1783 if (TREE_CODE (nit
) == INTEGER_CST
)
1785 if (!tree_int_cst_equal (nit
, TYPE_MAXVAL (nit_type
)))
1787 alt_bound
= fold_build2_loc (UNKNOWN_LOCATION
, PLUS_EXPR
, nit_type
,
1788 nit
, build_one_cst (nit_type
));
1790 gcc_assert (TREE_CODE (alt_bound
) == INTEGER_CST
);
1794 /* Todo: Figure out if we can trigger this, if it's worth to handle
1795 optimally, and if we can handle it optimally. */
1800 gcc_assert (TREE_CODE (nit
) == SSA_NAME
);
1802 gimple def
= SSA_NAME_DEF_STMT (nit
);
1805 && is_gimple_assign (def
)
1806 && gimple_assign_rhs_code (def
) == PLUS_EXPR
)
1808 tree op1
= gimple_assign_rhs1 (def
);
1809 tree op2
= gimple_assign_rhs2 (def
);
1810 if (integer_minus_onep (op1
))
1812 else if (integer_minus_onep (op2
))
1816 /* There is a number of test-cases for which we don't get an alt_bound
1817 here: they're listed here, with the lhs of the last stmt as the nit:
1819 libgomp.graphite/force-parallel-1.c:
1820 _21 = (signed long) N_6(D);
1822 _7 = (unsigned long) _19;
1824 libgomp.graphite/force-parallel-2.c:
1825 _33 = (signed long) N_9(D);
1827 _37 = (unsigned long) _16;
1829 libgomp.graphite/force-parallel-5.c:
1831 # graphite_IV.5_46 = PHI <0(5), graphite_IV.5_47(11)>
1833 _33 = (unsigned long) graphite_IV.5_46;
1835 g++.dg/tree-ssa/pr34355.C:
1836 _2 = (unsigned int) i_9;
1841 _18 = (unsigned int) _5;
1843 We will be able to handle some of these cases, if we can determine when
1844 it's safe to look past casts. */
1847 if (alt_bound
== NULL_TREE
)
1850 transform_to_exit_first_loop_alt (loop
, reduction_list
, alt_bound
);
1854 /* Moves the exit condition of LOOP to the beginning of its header. NIT is the
1855 number of iterations of the loop. REDUCTION_LIST describes the reductions in
1859 transform_to_exit_first_loop (struct loop
*loop
,
1860 reduction_info_table_type
*reduction_list
,
1863 basic_block
*bbs
, *nbbs
, ex_bb
, orig_header
;
1866 edge exit
= single_dom_exit (loop
), hpred
;
1867 tree control
, control_name
, res
, t
;
1870 gcond
*cond_stmt
, *cond_nit
;
1873 split_block_after_labels (loop
->header
);
1874 orig_header
= single_succ (loop
->header
);
1875 hpred
= single_succ_edge (loop
->header
);
1877 cond_stmt
= as_a
<gcond
*> (last_stmt (exit
->src
));
1878 control
= gimple_cond_lhs (cond_stmt
);
1879 gcc_assert (gimple_cond_rhs (cond_stmt
) == nit
);
1881 /* Make sure that we have phi nodes on exit for all loop header phis
1882 (create_parallel_loop requires that). */
1883 for (gphi_iterator gsi
= gsi_start_phis (loop
->header
);
1888 res
= PHI_RESULT (phi
);
1889 t
= copy_ssa_name (res
, phi
);
1890 SET_PHI_RESULT (phi
, t
);
1891 nphi
= create_phi_node (res
, orig_header
);
1892 add_phi_arg (nphi
, t
, hpred
, UNKNOWN_LOCATION
);
1896 gimple_cond_set_lhs (cond_stmt
, t
);
1897 update_stmt (cond_stmt
);
1902 bbs
= get_loop_body_in_dom_order (loop
);
1904 for (n
= 0; bbs
[n
] != exit
->src
; n
++)
1906 nbbs
= XNEWVEC (basic_block
, n
);
1907 ok
= gimple_duplicate_sese_tail (single_succ_edge (loop
->header
), exit
,
1914 /* Other than reductions, the only gimple reg that should be copied
1915 out of the loop is the control variable. */
1916 exit
= single_dom_exit (loop
);
1917 control_name
= NULL_TREE
;
1918 for (gphi_iterator gsi
= gsi_start_phis (ex_bb
);
1922 res
= PHI_RESULT (phi
);
1923 if (virtual_operand_p (res
))
1929 /* Check if it is a part of reduction. If it is,
1930 keep the phi at the reduction's keep_res field. The
1931 PHI_RESULT of this phi is the resulting value of the reduction
1932 variable when exiting the loop. */
1934 if (reduction_list
->elements () > 0)
1936 struct reduction_info
*red
;
1938 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
1939 red
= reduction_phi (reduction_list
, SSA_NAME_DEF_STMT (val
));
1942 red
->keep_res
= phi
;
1947 gcc_assert (control_name
== NULL_TREE
1948 && SSA_NAME_VAR (res
) == SSA_NAME_VAR (control
));
1950 remove_phi_node (&gsi
, false);
1952 gcc_assert (control_name
!= NULL_TREE
);
1954 /* Initialize the control variable to number of iterations
1955 according to the rhs of the exit condition. */
1956 gimple_stmt_iterator gsi
= gsi_after_labels (ex_bb
);
1957 cond_nit
= as_a
<gcond
*> (last_stmt (exit
->src
));
1958 nit_1
= gimple_cond_rhs (cond_nit
);
1959 nit_1
= force_gimple_operand_gsi (&gsi
,
1960 fold_convert (TREE_TYPE (control_name
), nit_1
),
1961 false, NULL_TREE
, false, GSI_SAME_STMT
);
1962 stmt
= gimple_build_assign (control_name
, nit_1
);
1963 gsi_insert_before (&gsi
, stmt
, GSI_NEW_STMT
);
1966 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
1967 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
1968 NEW_DATA is the variable that should be initialized from the argument
1969 of LOOP_FN. N_THREADS is the requested number of threads. Returns the
1970 basic block containing GIMPLE_OMP_PARALLEL tree. */
1973 create_parallel_loop (struct loop
*loop
, tree loop_fn
, tree data
,
1974 tree new_data
, unsigned n_threads
, location_t loc
)
1976 gimple_stmt_iterator gsi
;
1977 basic_block bb
, paral_bb
, for_bb
, ex_bb
;
1979 gomp_parallel
*omp_par_stmt
;
1980 gimple omp_return_stmt1
, omp_return_stmt2
;
1984 gomp_continue
*omp_cont_stmt
;
1985 tree cvar
, cvar_init
, initvar
, cvar_next
, cvar_base
, type
;
1986 edge exit
, nexit
, guard
, end
, e
;
1988 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
1989 bb
= loop_preheader_edge (loop
)->src
;
1990 paral_bb
= single_pred (bb
);
1991 gsi
= gsi_last_bb (paral_bb
);
1993 t
= build_omp_clause (loc
, OMP_CLAUSE_NUM_THREADS
);
1994 OMP_CLAUSE_NUM_THREADS_EXPR (t
)
1995 = build_int_cst (integer_type_node
, n_threads
);
1996 omp_par_stmt
= gimple_build_omp_parallel (NULL
, t
, loop_fn
, data
);
1997 gimple_set_location (omp_par_stmt
, loc
);
1999 gsi_insert_after (&gsi
, omp_par_stmt
, GSI_NEW_STMT
);
2001 /* Initialize NEW_DATA. */
2004 gassign
*assign_stmt
;
2006 gsi
= gsi_after_labels (bb
);
2008 param
= make_ssa_name (DECL_ARGUMENTS (loop_fn
));
2009 assign_stmt
= gimple_build_assign (param
, build_fold_addr_expr (data
));
2010 gsi_insert_before (&gsi
, assign_stmt
, GSI_SAME_STMT
);
2012 assign_stmt
= gimple_build_assign (new_data
,
2013 fold_convert (TREE_TYPE (new_data
), param
));
2014 gsi_insert_before (&gsi
, assign_stmt
, GSI_SAME_STMT
);
2017 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
2018 bb
= split_loop_exit_edge (single_dom_exit (loop
));
2019 gsi
= gsi_last_bb (bb
);
2020 omp_return_stmt1
= gimple_build_omp_return (false);
2021 gimple_set_location (omp_return_stmt1
, loc
);
2022 gsi_insert_after (&gsi
, omp_return_stmt1
, GSI_NEW_STMT
);
2024 /* Extract data for GIMPLE_OMP_FOR. */
2025 gcc_assert (loop
->header
== single_dom_exit (loop
)->src
);
2026 cond_stmt
= as_a
<gcond
*> (last_stmt (loop
->header
));
2028 cvar
= gimple_cond_lhs (cond_stmt
);
2029 cvar_base
= SSA_NAME_VAR (cvar
);
2030 phi
= SSA_NAME_DEF_STMT (cvar
);
2031 cvar_init
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_preheader_edge (loop
));
2032 initvar
= copy_ssa_name (cvar
);
2033 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi
, loop_preheader_edge (loop
)),
2035 cvar_next
= PHI_ARG_DEF_FROM_EDGE (phi
, loop_latch_edge (loop
));
2037 gsi
= gsi_last_nondebug_bb (loop
->latch
);
2038 gcc_assert (gsi_stmt (gsi
) == SSA_NAME_DEF_STMT (cvar_next
));
2039 gsi_remove (&gsi
, true);
2042 for_bb
= split_edge (loop_preheader_edge (loop
));
2043 ex_bb
= split_loop_exit_edge (single_dom_exit (loop
));
2044 extract_true_false_edges_from_block (loop
->header
, &nexit
, &exit
);
2045 gcc_assert (exit
== single_dom_exit (loop
));
2047 guard
= make_edge (for_bb
, ex_bb
, 0);
2048 single_succ_edge (loop
->latch
)->flags
= 0;
2049 end
= make_edge (loop
->latch
, ex_bb
, EDGE_FALLTHRU
);
2050 for (gphi_iterator gpi
= gsi_start_phis (ex_bb
);
2051 !gsi_end_p (gpi
); gsi_next (&gpi
))
2053 source_location locus
;
2055 gphi
*phi
= gpi
.phi ();
2058 stmt
= as_a
<gphi
*> (
2059 SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi
, exit
)));
2061 def
= PHI_ARG_DEF_FROM_EDGE (stmt
, loop_preheader_edge (loop
));
2062 locus
= gimple_phi_arg_location_from_edge (stmt
,
2063 loop_preheader_edge (loop
));
2064 add_phi_arg (phi
, def
, guard
, locus
);
2066 def
= PHI_ARG_DEF_FROM_EDGE (stmt
, loop_latch_edge (loop
));
2067 locus
= gimple_phi_arg_location_from_edge (stmt
, loop_latch_edge (loop
));
2068 add_phi_arg (phi
, def
, end
, locus
);
2070 e
= redirect_edge_and_branch (exit
, nexit
->dest
);
2071 PENDING_STMT (e
) = NULL
;
2073 /* Emit GIMPLE_OMP_FOR. */
2074 gimple_cond_set_lhs (cond_stmt
, cvar_base
);
2075 type
= TREE_TYPE (cvar
);
2076 t
= build_omp_clause (loc
, OMP_CLAUSE_SCHEDULE
);
2077 OMP_CLAUSE_SCHEDULE_KIND (t
) = OMP_CLAUSE_SCHEDULE_STATIC
;
2079 for_stmt
= gimple_build_omp_for (NULL
, GF_OMP_FOR_KIND_FOR
, t
, 1, NULL
);
2080 gimple_set_location (for_stmt
, loc
);
2081 gimple_omp_for_set_index (for_stmt
, 0, initvar
);
2082 gimple_omp_for_set_initial (for_stmt
, 0, cvar_init
);
2083 gimple_omp_for_set_final (for_stmt
, 0, gimple_cond_rhs (cond_stmt
));
2084 gimple_omp_for_set_cond (for_stmt
, 0, gimple_cond_code (cond_stmt
));
2085 gimple_omp_for_set_incr (for_stmt
, 0, build2 (PLUS_EXPR
, type
,
2087 build_int_cst (type
, 1)));
2089 gsi
= gsi_last_bb (for_bb
);
2090 gsi_insert_after (&gsi
, for_stmt
, GSI_NEW_STMT
);
2091 SSA_NAME_DEF_STMT (initvar
) = for_stmt
;
2093 /* Emit GIMPLE_OMP_CONTINUE. */
2094 gsi
= gsi_last_bb (loop
->latch
);
2095 omp_cont_stmt
= gimple_build_omp_continue (cvar_next
, cvar
);
2096 gimple_set_location (omp_cont_stmt
, loc
);
2097 gsi_insert_after (&gsi
, omp_cont_stmt
, GSI_NEW_STMT
);
2098 SSA_NAME_DEF_STMT (cvar_next
) = omp_cont_stmt
;
2100 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
2101 gsi
= gsi_last_bb (ex_bb
);
2102 omp_return_stmt2
= gimple_build_omp_return (true);
2103 gimple_set_location (omp_return_stmt2
, loc
);
2104 gsi_insert_after (&gsi
, omp_return_stmt2
, GSI_NEW_STMT
);
2106 /* After the above dom info is hosed. Re-compute it. */
2107 free_dominance_info (CDI_DOMINATORS
);
2108 calculate_dominance_info (CDI_DOMINATORS
);
2113 /* Generates code to execute the iterations of LOOP in N_THREADS
2114 threads in parallel.
2116 NITER describes number of iterations of LOOP.
2117 REDUCTION_LIST describes the reductions existent in the LOOP. */
2120 gen_parallel_loop (struct loop
*loop
,
2121 reduction_info_table_type
*reduction_list
,
2122 unsigned n_threads
, struct tree_niter_desc
*niter
)
2124 tree many_iterations_cond
, type
, nit
;
2125 tree arg_struct
, new_arg_struct
;
2128 struct clsn_data clsn_data
;
2132 unsigned int m_p_thread
=2;
2136 ---------------------------------------------------------------------
2139 IV = phi (INIT, IV + STEP)
2145 ---------------------------------------------------------------------
2147 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
2148 we generate the following code:
2150 ---------------------------------------------------------------------
2153 || NITER < MIN_PER_THREAD * N_THREADS)
2157 store all local loop-invariant variables used in body of the loop to DATA.
2158 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
2159 load the variables from DATA.
2160 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
2163 GIMPLE_OMP_CONTINUE;
2164 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
2165 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
2171 IV = phi (INIT, IV + STEP)
2182 /* Create two versions of the loop -- in the old one, we know that the
2183 number of iterations is large enough, and we will transform it into the
2184 loop that will be split to loop_fn, the new one will be used for the
2185 remaining iterations. */
2187 /* We should compute a better number-of-iterations value for outer loops.
2190 for (i = 0; i < n; ++i)
2191 for (j = 0; j < m; ++j)
2194 we should compute nit = n * m, not nit = n.
2195 Also may_be_zero handling would need to be adjusted. */
2197 type
= TREE_TYPE (niter
->niter
);
2198 nit
= force_gimple_operand (unshare_expr (niter
->niter
), &stmts
, true,
2201 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
2206 m_p_thread
=MIN_PER_THREAD
;
2208 many_iterations_cond
=
2209 fold_build2 (GE_EXPR
, boolean_type_node
,
2210 nit
, build_int_cst (type
, m_p_thread
* n_threads
));
2212 many_iterations_cond
2213 = fold_build2 (TRUTH_AND_EXPR
, boolean_type_node
,
2214 invert_truthvalue (unshare_expr (niter
->may_be_zero
)),
2215 many_iterations_cond
);
2216 many_iterations_cond
2217 = force_gimple_operand (many_iterations_cond
, &stmts
, false, NULL_TREE
);
2219 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
2220 if (!is_gimple_condexpr (many_iterations_cond
))
2222 many_iterations_cond
2223 = force_gimple_operand (many_iterations_cond
, &stmts
,
2226 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop
), stmts
);
2229 initialize_original_copy_tables ();
2231 /* We assume that the loop usually iterates a lot. */
2232 prob
= 4 * REG_BR_PROB_BASE
/ 5;
2233 loop_version (loop
, many_iterations_cond
, NULL
,
2234 prob
, prob
, REG_BR_PROB_BASE
- prob
, true);
2235 update_ssa (TODO_update_ssa
);
2236 free_original_copy_tables ();
2238 /* Base all the induction variables in LOOP on a single control one. */
2239 canonicalize_loop_ivs (loop
, &nit
, true);
2241 /* Ensure that the exit condition is the first statement in the loop.
2242 The common case is that latch of the loop is empty (apart from the
2243 increment) and immediately follows the loop exit test. Attempt to move the
2244 entry of the loop directly before the exit check and increase the number of
2245 iterations of the loop by one. */
2246 if (!try_transform_to_exit_first_loop_alt (loop
, reduction_list
, nit
))
2248 /* Fall back on the method that handles more cases, but duplicates the
2249 loop body: move the exit condition of LOOP to the beginning of its
2250 header, and duplicate the part of the last iteration that gets disabled
2251 to the exit of the loop. */
2252 transform_to_exit_first_loop (loop
, reduction_list
, nit
);
2255 /* Generate initializations for reductions. */
2256 if (reduction_list
->elements () > 0)
2257 reduction_list
->traverse
<struct loop
*, initialize_reductions
> (loop
);
2259 /* Eliminate the references to local variables from the loop. */
2260 gcc_assert (single_exit (loop
));
2261 entry
= loop_preheader_edge (loop
);
2262 exit
= single_dom_exit (loop
);
2264 eliminate_local_variables (entry
, exit
);
2265 /* In the old loop, move all variables non-local to the loop to a structure
2266 and back, and create separate decls for the variables used in loop. */
2267 separate_decls_in_region (entry
, exit
, reduction_list
, &arg_struct
,
2268 &new_arg_struct
, &clsn_data
);
2270 /* Create the parallel constructs. */
2271 loc
= UNKNOWN_LOCATION
;
2272 cond_stmt
= last_stmt (loop
->header
);
2274 loc
= gimple_location (cond_stmt
);
2275 create_parallel_loop (loop
, create_loop_fn (loc
), arg_struct
,
2276 new_arg_struct
, n_threads
, loc
);
2277 if (reduction_list
->elements () > 0)
2278 create_call_for_reduction (loop
, reduction_list
, &clsn_data
);
2282 /* Cancel the loop (it is simpler to do it here rather than to teach the
2283 expander to do it). */
2284 cancel_loop_tree (loop
);
2286 /* Free loop bound estimations that could contain references to
2287 removed statements. */
2288 FOR_EACH_LOOP (loop
, 0)
2289 free_numbers_of_iterations_estimates_loop (loop
);
2292 /* Returns true when LOOP contains vector phi nodes. */
2295 loop_has_vector_phi_nodes (struct loop
*loop ATTRIBUTE_UNUSED
)
2298 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
2302 for (i
= 0; i
< loop
->num_nodes
; i
++)
2303 for (gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
2304 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi
.phi ()))) == VECTOR_TYPE
)
2313 /* Create a reduction_info struct, initialize it with REDUC_STMT
2314 and PHI, insert it to the REDUCTION_LIST. */
2317 build_new_reduction (reduction_info_table_type
*reduction_list
,
2318 gimple reduc_stmt
, gphi
*phi
)
2320 reduction_info
**slot
;
2321 struct reduction_info
*new_reduction
;
2323 gcc_assert (reduc_stmt
);
2325 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2328 "Detected reduction. reduction stmt is: \n");
2329 print_gimple_stmt (dump_file
, reduc_stmt
, 0, 0);
2330 fprintf (dump_file
, "\n");
2333 new_reduction
= XCNEW (struct reduction_info
);
2335 new_reduction
->reduc_stmt
= reduc_stmt
;
2336 new_reduction
->reduc_phi
= phi
;
2337 new_reduction
->reduc_version
= SSA_NAME_VERSION (gimple_phi_result (phi
));
2338 new_reduction
->reduction_code
= gimple_assign_rhs_code (reduc_stmt
);
2339 slot
= reduction_list
->find_slot (new_reduction
, INSERT
);
2340 *slot
= new_reduction
;
2343 /* Callback for htab_traverse. Sets gimple_uid of reduc_phi stmts. */
2346 set_reduc_phi_uids (reduction_info
**slot
, void *data ATTRIBUTE_UNUSED
)
2348 struct reduction_info
*const red
= *slot
;
2349 gimple_set_uid (red
->reduc_phi
, red
->reduc_version
);
2353 /* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
2356 gather_scalar_reductions (loop_p loop
, reduction_info_table_type
*reduction_list
)
2359 loop_vec_info simple_loop_info
;
2361 simple_loop_info
= vect_analyze_loop_form (loop
);
2363 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2365 gphi
*phi
= gsi
.phi ();
2367 tree res
= PHI_RESULT (phi
);
2370 if (virtual_operand_p (res
))
2373 if (!simple_iv (loop
, loop
, res
, &iv
, true)
2374 && simple_loop_info
)
2376 gimple reduc_stmt
= vect_force_simple_reduction (simple_loop_info
,
2379 if (reduc_stmt
&& !double_reduc
)
2380 build_new_reduction (reduction_list
, reduc_stmt
, phi
);
2383 destroy_loop_vec_info (simple_loop_info
, true);
2385 /* As gimple_uid is used by the vectorizer in between vect_analyze_loop_form
2386 and destroy_loop_vec_info, we can set gimple_uid of reduc_phi stmts
2388 reduction_list
->traverse
<void *, set_reduc_phi_uids
> (NULL
);
2391 /* Try to initialize NITER for code generation part. */
2394 try_get_loop_niter (loop_p loop
, struct tree_niter_desc
*niter
)
2396 edge exit
= single_dom_exit (loop
);
2400 /* We need to know # of iterations, and there should be no uses of values
2401 defined inside loop outside of it, unless the values are invariants of
2403 if (!number_of_iterations_exit (loop
, exit
, niter
, false))
2405 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2406 fprintf (dump_file
, " FAILED: number of iterations not known\n");
2413 /* Try to initialize REDUCTION_LIST for code generation part.
2414 REDUCTION_LIST describes the reductions. */
2417 try_create_reduction_list (loop_p loop
,
2418 reduction_info_table_type
*reduction_list
)
2420 edge exit
= single_dom_exit (loop
);
2425 gather_scalar_reductions (loop
, reduction_list
);
2428 for (gsi
= gsi_start_phis (exit
->dest
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2430 gphi
*phi
= gsi
.phi ();
2431 struct reduction_info
*red
;
2432 imm_use_iterator imm_iter
;
2433 use_operand_p use_p
;
2435 tree val
= PHI_ARG_DEF_FROM_EDGE (phi
, exit
);
2437 if (!virtual_operand_p (val
))
2439 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2441 fprintf (dump_file
, "phi is ");
2442 print_gimple_stmt (dump_file
, phi
, 0, 0);
2443 fprintf (dump_file
, "arg of phi to exit: value ");
2444 print_generic_expr (dump_file
, val
, 0);
2445 fprintf (dump_file
, " used outside loop\n");
2447 " checking if it a part of reduction pattern: \n");
2449 if (reduction_list
->elements () == 0)
2451 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2453 " FAILED: it is not a part of reduction.\n");
2457 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, val
)
2459 if (!gimple_debug_bind_p (USE_STMT (use_p
))
2460 && flow_bb_inside_loop_p (loop
, gimple_bb (USE_STMT (use_p
))))
2462 reduc_phi
= USE_STMT (use_p
);
2466 red
= reduction_phi (reduction_list
, reduc_phi
);
2469 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2471 " FAILED: it is not a part of reduction.\n");
2474 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2476 fprintf (dump_file
, "reduction phi is ");
2477 print_gimple_stmt (dump_file
, red
->reduc_phi
, 0, 0);
2478 fprintf (dump_file
, "reduction stmt is ");
2479 print_gimple_stmt (dump_file
, red
->reduc_stmt
, 0, 0);
2484 /* The iterations of the loop may communicate only through bivs whose
2485 iteration space can be distributed efficiently. */
2486 for (gsi
= gsi_start_phis (loop
->header
); !gsi_end_p (gsi
); gsi_next (&gsi
))
2488 gphi
*phi
= gsi
.phi ();
2489 tree def
= PHI_RESULT (phi
);
2492 if (!virtual_operand_p (def
) && !simple_iv (loop
, loop
, def
, &iv
, true))
2494 struct reduction_info
*red
;
2496 red
= reduction_phi (reduction_list
, phi
);
2499 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2501 " FAILED: scalar dependency between iterations\n");
2511 /* Detect parallel loops and generate parallel code using libgomp
2512 primitives. Returns true if some loop was parallelized, false
2516 parallelize_loops (void)
2518 unsigned n_threads
= flag_tree_parallelize_loops
;
2519 bool changed
= false;
2521 struct tree_niter_desc niter_desc
;
2522 struct obstack parloop_obstack
;
2523 HOST_WIDE_INT estimated
;
2524 source_location loop_loc
;
2526 /* Do not parallelize loops in the functions created by parallelization. */
2527 if (parallelized_function_p (cfun
->decl
))
2529 if (cfun
->has_nonlocal_label
)
2532 gcc_obstack_init (&parloop_obstack
);
2533 reduction_info_table_type
reduction_list (10);
2534 init_stmt_vec_info_vec ();
2536 FOR_EACH_LOOP (loop
, 0)
2538 reduction_list
.empty ();
2539 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2541 fprintf (dump_file
, "Trying loop %d as candidate\n",loop
->num
);
2543 fprintf (dump_file
, "loop %d is not innermost\n",loop
->num
);
2545 fprintf (dump_file
, "loop %d is innermost\n",loop
->num
);
2548 /* If we use autopar in graphite pass, we use its marked dependency
2549 checking results. */
2550 if (flag_loop_parallelize_all
&& !loop
->can_be_parallel
)
2552 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2553 fprintf (dump_file
, "loop is not parallel according to graphite\n");
2557 if (!single_dom_exit (loop
))
2560 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2561 fprintf (dump_file
, "loop is !single_dom_exit\n");
2566 if (/* And of course, the loop must be parallelizable. */
2567 !can_duplicate_loop_p (loop
)
2568 || loop_has_blocks_with_irreducible_flag (loop
)
2569 || (loop_preheader_edge (loop
)->src
->flags
& BB_IRREDUCIBLE_LOOP
)
2570 /* FIXME: the check for vector phi nodes could be removed. */
2571 || loop_has_vector_phi_nodes (loop
))
2574 estimated
= estimated_stmt_executions_int (loop
);
2575 if (estimated
== -1)
2576 estimated
= max_stmt_executions_int (loop
);
2577 /* FIXME: Bypass this check as graphite doesn't update the
2578 count and frequency correctly now. */
2579 if (!flag_loop_parallelize_all
2580 && ((estimated
!= -1
2581 && estimated
<= (HOST_WIDE_INT
) n_threads
* MIN_PER_THREAD
)
2582 /* Do not bother with loops in cold areas. */
2583 || optimize_loop_nest_for_size_p (loop
)))
2586 if (!try_get_loop_niter (loop
, &niter_desc
))
2589 if (!try_create_reduction_list (loop
, &reduction_list
))
2592 if (!flag_loop_parallelize_all
2593 && !loop_parallel_p (loop
, &parloop_obstack
))
2597 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2600 fprintf (dump_file
, "parallelizing outer loop %d\n",loop
->header
->index
);
2602 fprintf (dump_file
, "parallelizing inner loop %d\n",loop
->header
->index
);
2603 loop_loc
= find_loop_location (loop
);
2604 if (loop_loc
!= UNKNOWN_LOCATION
)
2605 fprintf (dump_file
, "\nloop at %s:%d: ",
2606 LOCATION_FILE (loop_loc
), LOCATION_LINE (loop_loc
));
2608 gen_parallel_loop (loop
, &reduction_list
,
2609 n_threads
, &niter_desc
);
2612 free_stmt_vec_info_vec ();
2613 obstack_free (&parloop_obstack
, NULL
);
2615 /* Parallelization will cause new function calls to be inserted through
2616 which local variables will escape. Reset the points-to solution
2619 pt_solution_reset (&cfun
->gimple_df
->escaped
);
2624 /* Parallelization. */
2628 const pass_data pass_data_parallelize_loops
=
2630 GIMPLE_PASS
, /* type */
2631 "parloops", /* name */
2632 OPTGROUP_LOOP
, /* optinfo_flags */
2633 TV_TREE_PARALLELIZE_LOOPS
, /* tv_id */
2634 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2635 0, /* properties_provided */
2636 0, /* properties_destroyed */
2637 0, /* todo_flags_start */
2638 0, /* todo_flags_finish */
2641 class pass_parallelize_loops
: public gimple_opt_pass
2644 pass_parallelize_loops (gcc::context
*ctxt
)
2645 : gimple_opt_pass (pass_data_parallelize_loops
, ctxt
)
2648 /* opt_pass methods: */
2649 virtual bool gate (function
*) { return flag_tree_parallelize_loops
> 1; }
2650 virtual unsigned int execute (function
*);
2652 }; // class pass_parallelize_loops
2655 pass_parallelize_loops::execute (function
*fun
)
2657 if (number_of_loops (fun
) <= 1)
2660 if (parallelize_loops ())
2662 fun
->curr_properties
&= ~(PROP_gimple_eomp
);
2663 return TODO_update_ssa
;
2672 make_pass_parallelize_loops (gcc::context
*ctxt
)
2674 return new pass_parallelize_loops (ctxt
);