Merged r157653 through r157895 into branch.
[official-gcc.git] / gcc / tree-parloops.c
blob35638315c9c7d642d9d64cdbf68fad46ddd79f4c
1 /* Loop autoparallelization.
2 Copyright (C) 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr> and
4 Zdenek Dvorak <dvorakz@suse.cz>.
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
11 version.
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
16 for more details.
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/>. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "rtl.h"
28 #include "tree-flow.h"
29 #include "cfgloop.h"
30 #include "ggc.h"
31 #include "tree-data-ref.h"
32 #include "diagnostic.h"
33 #include "tree-pass.h"
34 #include "tree-scalar-evolution.h"
35 #include "hashtab.h"
36 #include "langhooks.h"
37 #include "tree-vectorizer.h"
39 /* This pass tries to distribute iterations of loops into several threads.
40 The implementation is straightforward -- for each loop we test whether its
41 iterations are independent, and if it is the case (and some additional
42 conditions regarding profitability and correctness are satisfied), we
43 add GIMPLE_OMP_PARALLEL and GIMPLE_OMP_FOR codes and let omp expansion
44 machinery do its job.
46 The most of the complexity is in bringing the code into shape expected
47 by the omp expanders:
48 -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction
49 variable and that the exit test is at the start of the loop body
50 -- for GIMPLE_OMP_PARALLEL, replacing the references to local addressable
51 variables by accesses through pointers, and breaking up ssa chains
52 by storing the values incoming to the parallelized loop to a structure
53 passed to the new function as an argument (something similar is done
54 in omp gimplification, unfortunately only a small part of the code
55 can be shared).
57 TODO:
58 -- if there are several parallelizable loops in a function, it may be
59 possible to generate the threads just once (using synchronization to
60 ensure that cross-loop dependences are obeyed).
61 -- handling of common scalar dependence patterns (accumulation, ...)
62 -- handling of non-innermost loops */
65 Reduction handling:
66 currently we use vect_is_simple_reduction() to detect reduction patterns.
67 The code transformation will be introduced by an example.
70 parloop
72 int sum=1;
74 for (i = 0; i < N; i++)
76 x[i] = i + 3;
77 sum+=x[i];
81 gimple-like code:
82 header_bb:
84 # sum_29 = PHI <sum_11(5), 1(3)>
85 # i_28 = PHI <i_12(5), 0(3)>
86 D.1795_8 = i_28 + 3;
87 x[i_28] = D.1795_8;
88 sum_11 = D.1795_8 + sum_29;
89 i_12 = i_28 + 1;
90 if (N_6(D) > i_12)
91 goto header_bb;
94 exit_bb:
96 # sum_21 = PHI <sum_11(4)>
97 printf (&"%d"[0], sum_21);
100 after reduction transformation (only relevant parts):
102 parloop
105 ....
108 # Storing the initial value given by the user. #
110 .paral_data_store.32.sum.27 = 1;
112 #pragma omp parallel num_threads(4)
114 #pragma omp for schedule(static)
116 # The neutral element corresponding to the particular
117 reduction's operation, e.g. 0 for PLUS_EXPR,
118 1 for MULT_EXPR, etc. replaces the user's initial value. #
120 # sum.27_29 = PHI <sum.27_11, 0>
122 sum.27_11 = D.1827_8 + sum.27_29;
124 GIMPLE_OMP_CONTINUE
126 # Adding this reduction phi is done at create_phi_for_local_result() #
127 # sum.27_56 = PHI <sum.27_11, 0>
128 GIMPLE_OMP_RETURN
130 # Creating the atomic operation is done at
131 create_call_for_reduction_1() #
133 #pragma omp atomic_load
134 D.1839_59 = *&.paral_data_load.33_51->reduction.23;
135 D.1840_60 = sum.27_56 + D.1839_59;
136 #pragma omp atomic_store (D.1840_60);
138 GIMPLE_OMP_RETURN
140 # collecting the result after the join of the threads is done at
141 create_loads_for_reductions().
142 The value computed by the threads is loaded from the
143 shared struct. #
146 .paral_data_load.33_52 = &.paral_data_store.32;
147 sum_37 = .paral_data_load.33_52->sum.27;
148 sum_43 = D.1795_41 + sum_37;
150 exit bb:
151 # sum_21 = PHI <sum_43, sum_26>
152 printf (&"%d"[0], sum_21);
160 /* Minimal number of iterations of a loop that should be executed in each
161 thread. */
162 #define MIN_PER_THREAD 100
164 /* Element of the hashtable, representing a
165 reduction in the current loop. */
166 struct reduction_info
168 gimple reduc_stmt; /* reduction statement. */
169 gimple reduc_phi; /* The phi node defining the reduction. */
170 enum tree_code reduction_code;/* code for the reduction operation. */
171 gimple keep_res; /* The PHI_RESULT of this phi is the resulting value
172 of the reduction variable when existing the loop. */
173 tree initial_value; /* The initial value of the reduction var before entering the loop. */
174 tree field; /* the name of the field in the parloop data structure intended for reduction. */
175 tree init; /* reduction initialization value. */
176 gimple new_phi; /* (helper field) Newly created phi node whose result
177 will be passed to the atomic operation. Represents
178 the local result each thread computed for the reduction
179 operation. */
182 /* Equality and hash functions for hashtab code. */
184 static int
185 reduction_info_eq (const void *aa, const void *bb)
187 const struct reduction_info *a = (const struct reduction_info *) aa;
188 const struct reduction_info *b = (const struct reduction_info *) bb;
190 return (a->reduc_phi == b->reduc_phi);
193 static hashval_t
194 reduction_info_hash (const void *aa)
196 const struct reduction_info *a = (const struct reduction_info *) aa;
198 return htab_hash_pointer (a->reduc_phi);
201 static struct reduction_info *
202 reduction_phi (htab_t reduction_list, gimple phi)
204 struct reduction_info tmpred, *red;
206 if (htab_elements (reduction_list) == 0)
207 return NULL;
209 tmpred.reduc_phi = phi;
210 red = (struct reduction_info *) htab_find (reduction_list, &tmpred);
212 return red;
215 /* Element of hashtable of names to copy. */
217 struct name_to_copy_elt
219 unsigned version; /* The version of the name to copy. */
220 tree new_name; /* The new name used in the copy. */
221 tree field; /* The field of the structure used to pass the
222 value. */
225 /* Equality and hash functions for hashtab code. */
227 static int
228 name_to_copy_elt_eq (const void *aa, const void *bb)
230 const struct name_to_copy_elt *a = (const struct name_to_copy_elt *) aa;
231 const struct name_to_copy_elt *b = (const struct name_to_copy_elt *) bb;
233 return a->version == b->version;
236 static hashval_t
237 name_to_copy_elt_hash (const void *aa)
239 const struct name_to_copy_elt *a = (const struct name_to_copy_elt *) aa;
241 return (hashval_t) a->version;
245 /* Data dependency analysis. Returns true if the iterations of LOOP
246 are independent on each other (that is, if we can execute them
247 in parallel). */
249 static bool
250 loop_parallel_p (struct loop *loop)
252 VEC (ddr_p, heap) * dependence_relations;
253 VEC (data_reference_p, heap) *datarefs;
254 lambda_trans_matrix trans;
255 bool ret = false;
257 if (dump_file && (dump_flags & TDF_DETAILS))
259 fprintf (dump_file, "Considering loop %d\n", loop->num);
260 if (!loop->inner)
261 fprintf (dump_file, "loop is innermost\n");
262 else
263 fprintf (dump_file, "loop NOT innermost\n");
266 /* Check for problems with dependences. If the loop can be reversed,
267 the iterations are independent. */
268 datarefs = VEC_alloc (data_reference_p, heap, 10);
269 dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
270 compute_data_dependences_for_loop (loop, true, &datarefs,
271 &dependence_relations);
272 if (dump_file && (dump_flags & TDF_DETAILS))
273 dump_data_dependence_relations (dump_file, dependence_relations);
275 trans = lambda_trans_matrix_new (1, 1);
276 LTM_MATRIX (trans)[0][0] = -1;
278 if (lambda_transform_legal_p (trans, 1, dependence_relations))
280 ret = true;
281 if (dump_file && (dump_flags & TDF_DETAILS))
282 fprintf (dump_file, " SUCCESS: may be parallelized\n");
284 else if (dump_file && (dump_flags & TDF_DETAILS))
285 fprintf (dump_file,
286 " FAILED: data dependencies exist across iterations\n");
288 free_dependence_relations (dependence_relations);
289 free_data_refs (datarefs);
291 return ret;
294 /* Return true when LOOP contains basic blocks marked with the
295 BB_IRREDUCIBLE_LOOP flag. */
297 static inline bool
298 loop_has_blocks_with_irreducible_flag (struct loop *loop)
300 unsigned i;
301 basic_block *bbs = get_loop_body_in_dom_order (loop);
302 bool res = true;
304 for (i = 0; i < loop->num_nodes; i++)
305 if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
306 goto end;
308 res = false;
309 end:
310 free (bbs);
311 return res;
314 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
315 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
316 to their addresses that can be reused. The address of OBJ is known to
317 be invariant in the whole function. */
319 static tree
320 take_address_of (tree obj, tree type, edge entry, htab_t decl_address)
322 int uid;
323 void **dslot;
324 struct int_tree_map ielt, *nielt;
325 tree *var_p, name, bvar, addr;
326 gimple stmt;
327 gimple_seq stmts;
329 /* Since the address of OBJ is invariant, the trees may be shared.
330 Avoid rewriting unrelated parts of the code. */
331 obj = unshare_expr (obj);
332 for (var_p = &obj;
333 handled_component_p (*var_p);
334 var_p = &TREE_OPERAND (*var_p, 0))
335 continue;
336 uid = DECL_UID (*var_p);
338 ielt.uid = uid;
339 dslot = htab_find_slot_with_hash (decl_address, &ielt, uid, INSERT);
340 if (!*dslot)
342 addr = build_addr (*var_p, current_function_decl);
343 bvar = create_tmp_var (TREE_TYPE (addr), get_name (*var_p));
344 add_referenced_var (bvar);
345 stmt = gimple_build_assign (bvar, addr);
346 name = make_ssa_name (bvar, stmt);
347 gimple_assign_set_lhs (stmt, name);
348 gsi_insert_on_edge_immediate (entry, stmt);
350 nielt = XNEW (struct int_tree_map);
351 nielt->uid = uid;
352 nielt->to = name;
353 *dslot = nielt;
355 else
356 name = ((struct int_tree_map *) *dslot)->to;
358 if (var_p != &obj)
360 *var_p = build1 (INDIRECT_REF, TREE_TYPE (*var_p), name);
361 name = force_gimple_operand (build_addr (obj, current_function_decl),
362 &stmts, true, NULL_TREE);
363 if (!gimple_seq_empty_p (stmts))
364 gsi_insert_seq_on_edge_immediate (entry, stmts);
367 if (TREE_TYPE (name) != type)
369 name = force_gimple_operand (fold_convert (type, name), &stmts, true,
370 NULL_TREE);
371 if (!gimple_seq_empty_p (stmts))
372 gsi_insert_seq_on_edge_immediate (entry, stmts);
375 return name;
378 /* Callback for htab_traverse. Create the initialization statement
379 for reduction described in SLOT, and place it at the preheader of
380 the loop described in DATA. */
382 static int
383 initialize_reductions (void **slot, void *data)
385 tree init, c;
386 tree bvar, type, arg;
387 edge e;
389 struct reduction_info *const reduc = (struct reduction_info *) *slot;
390 struct loop *loop = (struct loop *) data;
392 /* Create initialization in preheader:
393 reduction_variable = initialization value of reduction. */
395 /* In the phi node at the header, replace the argument coming
396 from the preheader with the reduction initialization value. */
398 /* Create a new variable to initialize the reduction. */
399 type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
400 bvar = create_tmp_var (type, "reduction");
401 add_referenced_var (bvar);
403 c = build_omp_clause (gimple_location (reduc->reduc_stmt),
404 OMP_CLAUSE_REDUCTION);
405 OMP_CLAUSE_REDUCTION_CODE (c) = reduc->reduction_code;
406 OMP_CLAUSE_DECL (c) = SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt));
408 init = omp_reduction_init (c, TREE_TYPE (bvar));
409 reduc->init = init;
411 /* Replace the argument representing the initialization value
412 with the initialization value for the reduction (neutral
413 element for the particular operation, e.g. 0 for PLUS_EXPR,
414 1 for MULT_EXPR, etc).
415 Keep the old value in a new variable "reduction_initial",
416 that will be taken in consideration after the parallel
417 computing is done. */
419 e = loop_preheader_edge (loop);
420 arg = PHI_ARG_DEF_FROM_EDGE (reduc->reduc_phi, e);
421 /* Create new variable to hold the initial value. */
423 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
424 (reduc->reduc_phi, loop_preheader_edge (loop)), init);
425 reduc->initial_value = arg;
426 return 1;
429 struct elv_data
431 struct walk_stmt_info info;
432 edge entry;
433 htab_t decl_address;
434 bool changed;
437 /* Eliminates references to local variables in *TP out of the single
438 entry single exit region starting at DTA->ENTRY.
439 DECL_ADDRESS contains addresses of the references that had their
440 address taken already. If the expression is changed, CHANGED is
441 set to true. Callback for walk_tree. */
443 static tree
444 eliminate_local_variables_1 (tree *tp, int *walk_subtrees, void *data)
446 struct elv_data *const dta = (struct elv_data *) data;
447 tree t = *tp, var, addr, addr_type, type, obj;
449 if (DECL_P (t))
451 *walk_subtrees = 0;
453 if (!SSA_VAR_P (t) || DECL_EXTERNAL (t))
454 return NULL_TREE;
456 type = TREE_TYPE (t);
457 addr_type = build_pointer_type (type);
458 addr = take_address_of (t, addr_type, dta->entry, dta->decl_address);
459 *tp = build1 (INDIRECT_REF, TREE_TYPE (*tp), addr);
461 dta->changed = true;
462 return NULL_TREE;
465 if (TREE_CODE (t) == ADDR_EXPR)
467 /* ADDR_EXPR may appear in two contexts:
468 -- as a gimple operand, when the address taken is a function invariant
469 -- as gimple rhs, when the resulting address in not a function
470 invariant
471 We do not need to do anything special in the latter case (the base of
472 the memory reference whose address is taken may be replaced in the
473 DECL_P case). The former case is more complicated, as we need to
474 ensure that the new address is still a gimple operand. Thus, it
475 is not sufficient to replace just the base of the memory reference --
476 we need to move the whole computation of the address out of the
477 loop. */
478 if (!is_gimple_val (t))
479 return NULL_TREE;
481 *walk_subtrees = 0;
482 obj = TREE_OPERAND (t, 0);
483 var = get_base_address (obj);
484 if (!var || !SSA_VAR_P (var) || DECL_EXTERNAL (var))
485 return NULL_TREE;
487 addr_type = TREE_TYPE (t);
488 addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address);
489 *tp = addr;
491 dta->changed = true;
492 return NULL_TREE;
495 if (!EXPR_P (t))
496 *walk_subtrees = 0;
498 return NULL_TREE;
501 /* Moves the references to local variables in STMT out of the single
502 entry single exit region starting at ENTRY. DECL_ADDRESS contains
503 addresses of the references that had their address taken
504 already. */
506 static void
507 eliminate_local_variables_stmt (edge entry, gimple stmt,
508 htab_t decl_address)
510 struct elv_data dta;
512 memset (&dta.info, '\0', sizeof (dta.info));
513 dta.entry = entry;
514 dta.decl_address = decl_address;
515 dta.changed = false;
517 if (gimple_debug_bind_p (stmt))
518 walk_tree (gimple_debug_bind_get_value_ptr (stmt),
519 eliminate_local_variables_1, &dta.info, NULL);
520 else
521 walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
523 if (dta.changed)
524 update_stmt (stmt);
527 /* Eliminates the references to local variables from the single entry
528 single exit region between the ENTRY and EXIT edges.
530 This includes:
531 1) Taking address of a local variable -- these are moved out of the
532 region (and temporary variable is created to hold the address if
533 necessary).
535 2) Dereferencing a local variable -- these are replaced with indirect
536 references. */
538 static void
539 eliminate_local_variables (edge entry, edge exit)
541 basic_block bb;
542 VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
543 unsigned i;
544 gimple_stmt_iterator gsi;
545 htab_t decl_address = htab_create (10, int_tree_map_hash, int_tree_map_eq,
546 free);
547 basic_block entry_bb = entry->src;
548 basic_block exit_bb = exit->dest;
550 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
552 for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
553 if (bb != entry_bb && bb != exit_bb)
554 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
555 eliminate_local_variables_stmt (entry, gsi_stmt (gsi),
556 decl_address);
558 htab_delete (decl_address);
559 VEC_free (basic_block, heap, body);
562 /* Returns true if expression EXPR is not defined between ENTRY and
563 EXIT, i.e. if all its operands are defined outside of the region. */
565 static bool
566 expr_invariant_in_region_p (edge entry, edge exit, tree expr)
568 basic_block entry_bb = entry->src;
569 basic_block exit_bb = exit->dest;
570 basic_block def_bb;
572 if (is_gimple_min_invariant (expr))
573 return true;
575 if (TREE_CODE (expr) == SSA_NAME)
577 def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
578 if (def_bb
579 && dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)
580 && !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))
581 return false;
583 return true;
586 return false;
589 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
590 The copies are stored to NAME_COPIES, if NAME was already duplicated,
591 its duplicate stored in NAME_COPIES is returned.
593 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
594 duplicated, storing the copies in DECL_COPIES. */
596 static tree
597 separate_decls_in_region_name (tree name,
598 htab_t name_copies, htab_t decl_copies,
599 bool copy_name_p)
601 tree copy, var, var_copy;
602 unsigned idx, uid, nuid;
603 struct int_tree_map ielt, *nielt;
604 struct name_to_copy_elt elt, *nelt;
605 void **slot, **dslot;
607 if (TREE_CODE (name) != SSA_NAME)
608 return name;
610 idx = SSA_NAME_VERSION (name);
611 elt.version = idx;
612 slot = htab_find_slot_with_hash (name_copies, &elt, idx,
613 copy_name_p ? INSERT : NO_INSERT);
614 if (slot && *slot)
615 return ((struct name_to_copy_elt *) *slot)->new_name;
617 var = SSA_NAME_VAR (name);
618 uid = DECL_UID (var);
619 ielt.uid = uid;
620 dslot = htab_find_slot_with_hash (decl_copies, &ielt, uid, INSERT);
621 if (!*dslot)
623 var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
624 DECL_GIMPLE_REG_P (var_copy) = DECL_GIMPLE_REG_P (var);
625 add_referenced_var (var_copy);
626 nielt = XNEW (struct int_tree_map);
627 nielt->uid = uid;
628 nielt->to = var_copy;
629 *dslot = nielt;
631 /* Ensure that when we meet this decl next time, we won't duplicate
632 it again. */
633 nuid = DECL_UID (var_copy);
634 ielt.uid = nuid;
635 dslot = htab_find_slot_with_hash (decl_copies, &ielt, nuid, INSERT);
636 gcc_assert (!*dslot);
637 nielt = XNEW (struct int_tree_map);
638 nielt->uid = nuid;
639 nielt->to = var_copy;
640 *dslot = nielt;
642 else
643 var_copy = ((struct int_tree_map *) *dslot)->to;
645 if (copy_name_p)
647 copy = duplicate_ssa_name (name, NULL);
648 nelt = XNEW (struct name_to_copy_elt);
649 nelt->version = idx;
650 nelt->new_name = copy;
651 nelt->field = NULL_TREE;
652 *slot = nelt;
654 else
656 gcc_assert (!slot);
657 copy = name;
660 SSA_NAME_VAR (copy) = var_copy;
661 return copy;
664 /* Finds the ssa names used in STMT that are defined outside the
665 region between ENTRY and EXIT and replaces such ssa names with
666 their duplicates. The duplicates are stored to NAME_COPIES. Base
667 decls of all ssa names used in STMT (including those defined in
668 LOOP) are replaced with the new temporary variables; the
669 replacement decls are stored in DECL_COPIES. */
671 static void
672 separate_decls_in_region_stmt (edge entry, edge exit, gimple stmt,
673 htab_t name_copies, htab_t decl_copies)
675 use_operand_p use;
676 def_operand_p def;
677 ssa_op_iter oi;
678 tree name, copy;
679 bool copy_name_p;
681 mark_virtual_ops_for_renaming (stmt);
683 FOR_EACH_PHI_OR_STMT_DEF (def, stmt, oi, SSA_OP_DEF)
685 name = DEF_FROM_PTR (def);
686 gcc_assert (TREE_CODE (name) == SSA_NAME);
687 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
688 false);
689 gcc_assert (copy == name);
692 FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
694 name = USE_FROM_PTR (use);
695 if (TREE_CODE (name) != SSA_NAME)
696 continue;
698 copy_name_p = expr_invariant_in_region_p (entry, exit, name);
699 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
700 copy_name_p);
701 SET_USE (use, copy);
705 /* Finds the ssa names used in STMT that are defined outside the
706 region between ENTRY and EXIT and replaces such ssa names with
707 their duplicates. The duplicates are stored to NAME_COPIES. Base
708 decls of all ssa names used in STMT (including those defined in
709 LOOP) are replaced with the new temporary variables; the
710 replacement decls are stored in DECL_COPIES. */
712 static bool
713 separate_decls_in_region_debug_bind (gimple stmt,
714 htab_t name_copies, htab_t decl_copies)
716 use_operand_p use;
717 ssa_op_iter oi;
718 tree var, name;
719 struct int_tree_map ielt;
720 struct name_to_copy_elt elt;
721 void **slot, **dslot;
723 var = gimple_debug_bind_get_var (stmt);
724 if (TREE_CODE (var) == DEBUG_EXPR_DECL)
725 return true;
726 gcc_assert (DECL_P (var) && SSA_VAR_P (var));
727 ielt.uid = DECL_UID (var);
728 dslot = htab_find_slot_with_hash (decl_copies, &ielt, ielt.uid, NO_INSERT);
729 if (!dslot)
730 return true;
731 gimple_debug_bind_set_var (stmt, ((struct int_tree_map *) *dslot)->to);
733 FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
735 name = USE_FROM_PTR (use);
736 if (TREE_CODE (name) != SSA_NAME)
737 continue;
739 elt.version = SSA_NAME_VERSION (name);
740 slot = htab_find_slot_with_hash (name_copies, &elt, elt.version, NO_INSERT);
741 if (!slot)
743 gimple_debug_bind_reset_value (stmt);
744 update_stmt (stmt);
745 break;
748 SET_USE (use, ((struct name_to_copy_elt *) *slot)->new_name);
751 return false;
754 /* Callback for htab_traverse. Adds a field corresponding to the reduction
755 specified in SLOT. The type is passed in DATA. */
757 static int
758 add_field_for_reduction (void **slot, void *data)
761 struct reduction_info *const red = (struct reduction_info *) *slot;
762 tree const type = (tree) data;
763 tree var = SSA_NAME_VAR (gimple_assign_lhs (red->reduc_stmt));
764 tree field = build_decl (gimple_location (red->reduc_stmt),
765 FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
767 insert_field_into_struct (type, field);
769 red->field = field;
771 return 1;
774 /* Callback for htab_traverse. Adds a field corresponding to a ssa name
775 described in SLOT. The type is passed in DATA. */
777 static int
778 add_field_for_name (void **slot, void *data)
780 struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
781 tree type = (tree) data;
782 tree name = ssa_name (elt->version);
783 tree var = SSA_NAME_VAR (name);
784 tree field = build_decl (DECL_SOURCE_LOCATION (var),
785 FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
787 insert_field_into_struct (type, field);
788 elt->field = field;
790 return 1;
793 /* Callback for htab_traverse. A local result is the intermediate result
794 computed by a single
795 thread, or the initial value in case no iteration was executed.
796 This function creates a phi node reflecting these values.
797 The phi's result will be stored in NEW_PHI field of the
798 reduction's data structure. */
800 static int
801 create_phi_for_local_result (void **slot, void *data)
803 struct reduction_info *const reduc = (struct reduction_info *) *slot;
804 const struct loop *const loop = (const struct loop *) data;
805 edge e;
806 gimple new_phi;
807 basic_block store_bb;
808 tree local_res;
809 source_location locus;
811 /* STORE_BB is the block where the phi
812 should be stored. It is the destination of the loop exit.
813 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
814 store_bb = FALLTHRU_EDGE (loop->latch)->dest;
816 /* STORE_BB has two predecessors. One coming from the loop
817 (the reduction's result is computed at the loop),
818 and another coming from a block preceding the loop,
819 when no iterations
820 are executed (the initial value should be taken). */
821 if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (loop->latch))
822 e = EDGE_PRED (store_bb, 1);
823 else
824 e = EDGE_PRED (store_bb, 0);
825 local_res
826 = make_ssa_name (SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt)),
827 NULL);
828 locus = gimple_location (reduc->reduc_stmt);
829 new_phi = create_phi_node (local_res, store_bb);
830 SSA_NAME_DEF_STMT (local_res) = new_phi;
831 add_phi_arg (new_phi, reduc->init, e, locus);
832 add_phi_arg (new_phi, gimple_assign_lhs (reduc->reduc_stmt),
833 FALLTHRU_EDGE (loop->latch), locus);
834 reduc->new_phi = new_phi;
836 return 1;
839 struct clsn_data
841 tree store;
842 tree load;
844 basic_block store_bb;
845 basic_block load_bb;
848 /* Callback for htab_traverse. Create an atomic instruction for the
849 reduction described in SLOT.
850 DATA annotates the place in memory the atomic operation relates to,
851 and the basic block it needs to be generated in. */
853 static int
854 create_call_for_reduction_1 (void **slot, void *data)
856 struct reduction_info *const reduc = (struct reduction_info *) *slot;
857 struct clsn_data *const clsn_data = (struct clsn_data *) data;
858 gimple_stmt_iterator gsi;
859 tree type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
860 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
861 tree load_struct;
862 basic_block bb;
863 basic_block new_bb;
864 edge e;
865 tree t, addr, ref, x;
866 tree tmp_load, name;
867 gimple load;
869 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
870 t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
872 addr = build_addr (t, current_function_decl);
874 /* Create phi node. */
875 bb = clsn_data->load_bb;
877 e = split_block (bb, t);
878 new_bb = e->dest;
880 tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)), NULL);
881 add_referenced_var (tmp_load);
882 tmp_load = make_ssa_name (tmp_load, NULL);
883 load = gimple_build_omp_atomic_load (tmp_load, addr);
884 SSA_NAME_DEF_STMT (tmp_load) = load;
885 gsi = gsi_start_bb (new_bb);
886 gsi_insert_after (&gsi, load, GSI_NEW_STMT);
888 e = split_block (new_bb, load);
889 new_bb = e->dest;
890 gsi = gsi_start_bb (new_bb);
891 ref = tmp_load;
892 x = fold_build2 (reduc->reduction_code,
893 TREE_TYPE (PHI_RESULT (reduc->new_phi)), ref,
894 PHI_RESULT (reduc->new_phi));
896 name = force_gimple_operand_gsi (&gsi, x, true, NULL_TREE, true,
897 GSI_CONTINUE_LINKING);
899 gsi_insert_after (&gsi, gimple_build_omp_atomic_store (name), GSI_NEW_STMT);
900 return 1;
903 /* Create the atomic operation at the join point of the threads.
904 REDUCTION_LIST describes the reductions in the LOOP.
905 LD_ST_DATA describes the shared data structure where
906 shared data is stored in and loaded from. */
907 static void
908 create_call_for_reduction (struct loop *loop, htab_t reduction_list,
909 struct clsn_data *ld_st_data)
911 htab_traverse (reduction_list, create_phi_for_local_result, loop);
912 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
913 ld_st_data->load_bb = FALLTHRU_EDGE (loop->latch)->dest;
914 htab_traverse (reduction_list, create_call_for_reduction_1, ld_st_data);
917 /* Callback for htab_traverse. Loads the final reduction value at the
918 join point of all threads, and inserts it in the right place. */
920 static int
921 create_loads_for_reductions (void **slot, void *data)
923 struct reduction_info *const red = (struct reduction_info *) *slot;
924 struct clsn_data *const clsn_data = (struct clsn_data *) data;
925 gimple stmt;
926 gimple_stmt_iterator gsi;
927 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
928 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
929 tree load_struct;
930 tree name;
931 tree x;
933 gsi = gsi_after_labels (clsn_data->load_bb);
934 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
935 load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
936 NULL_TREE);
938 x = load_struct;
939 name = PHI_RESULT (red->keep_res);
940 stmt = gimple_build_assign (name, x);
941 SSA_NAME_DEF_STMT (name) = stmt;
943 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
945 for (gsi = gsi_start_phis (gimple_bb (red->keep_res));
946 !gsi_end_p (gsi); gsi_next (&gsi))
947 if (gsi_stmt (gsi) == red->keep_res)
949 remove_phi_node (&gsi, false);
950 return 1;
952 gcc_unreachable ();
955 /* Load the reduction result that was stored in LD_ST_DATA.
956 REDUCTION_LIST describes the list of reductions that the
957 loads should be generated for. */
958 static void
959 create_final_loads_for_reduction (htab_t reduction_list,
960 struct clsn_data *ld_st_data)
962 gimple_stmt_iterator gsi;
963 tree t;
964 gimple stmt;
966 gsi = gsi_after_labels (ld_st_data->load_bb);
967 t = build_fold_addr_expr (ld_st_data->store);
968 stmt = gimple_build_assign (ld_st_data->load, t);
970 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
971 SSA_NAME_DEF_STMT (ld_st_data->load) = stmt;
973 htab_traverse (reduction_list, create_loads_for_reductions, ld_st_data);
977 /* Callback for htab_traverse. Store the neutral value for the
978 particular reduction's operation, e.g. 0 for PLUS_EXPR,
979 1 for MULT_EXPR, etc. into the reduction field.
980 The reduction is specified in SLOT. The store information is
981 passed in DATA. */
983 static int
984 create_stores_for_reduction (void **slot, void *data)
986 struct reduction_info *const red = (struct reduction_info *) *slot;
987 struct clsn_data *const clsn_data = (struct clsn_data *) data;
988 tree t;
989 gimple stmt;
990 gimple_stmt_iterator gsi;
991 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
993 gsi = gsi_last_bb (clsn_data->store_bb);
994 t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE);
995 stmt = gimple_build_assign (t, red->initial_value);
996 mark_virtual_ops_for_renaming (stmt);
997 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
999 return 1;
1002 /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
1003 store to a field of STORE in STORE_BB for the ssa name and its duplicate
1004 specified in SLOT. */
1006 static int
1007 create_loads_and_stores_for_name (void **slot, void *data)
1009 struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
1010 struct clsn_data *const clsn_data = (struct clsn_data *) data;
1011 tree t;
1012 gimple stmt;
1013 gimple_stmt_iterator gsi;
1014 tree type = TREE_TYPE (elt->new_name);
1015 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
1016 tree load_struct;
1018 gsi = gsi_last_bb (clsn_data->store_bb);
1019 t = build3 (COMPONENT_REF, type, clsn_data->store, elt->field, NULL_TREE);
1020 stmt = gimple_build_assign (t, ssa_name (elt->version));
1021 mark_virtual_ops_for_renaming (stmt);
1022 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1024 gsi = gsi_last_bb (clsn_data->load_bb);
1025 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
1026 t = build3 (COMPONENT_REF, type, load_struct, elt->field, NULL_TREE);
1027 stmt = gimple_build_assign (elt->new_name, t);
1028 SSA_NAME_DEF_STMT (elt->new_name) = stmt;
1029 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1031 return 1;
1034 /* Moves all the variables used in LOOP and defined outside of it (including
1035 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1036 name) to a structure created for this purpose. The code
1038 while (1)
1040 use (a);
1041 use (b);
1044 is transformed this way:
1046 bb0:
1047 old.a = a;
1048 old.b = b;
1050 bb1:
1051 a' = new->a;
1052 b' = new->b;
1053 while (1)
1055 use (a');
1056 use (b');
1059 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1060 pointer `new' is intentionally not initialized (the loop will be split to a
1061 separate function later, and `new' will be initialized from its arguments).
1062 LD_ST_DATA holds information about the shared data structure used to pass
1063 information among the threads. It is initialized here, and
1064 gen_parallel_loop will pass it to create_call_for_reduction that
1065 needs this information. REDUCTION_LIST describes the reductions
1066 in LOOP. */
1068 static void
1069 separate_decls_in_region (edge entry, edge exit, htab_t reduction_list,
1070 tree *arg_struct, tree *new_arg_struct,
1071 struct clsn_data *ld_st_data)
1074 basic_block bb1 = split_edge (entry);
1075 basic_block bb0 = single_pred (bb1);
1076 htab_t name_copies = htab_create (10, name_to_copy_elt_hash,
1077 name_to_copy_elt_eq, free);
1078 htab_t decl_copies = htab_create (10, int_tree_map_hash, int_tree_map_eq,
1079 free);
1080 unsigned i;
1081 tree type, type_name, nvar;
1082 gimple_stmt_iterator gsi;
1083 struct clsn_data clsn_data;
1084 VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
1085 basic_block bb;
1086 basic_block entry_bb = bb1;
1087 basic_block exit_bb = exit->dest;
1088 bool has_debug_stmt = false;
1090 entry = single_succ_edge (entry_bb);
1091 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
1093 for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
1095 if (bb != entry_bb && bb != exit_bb)
1097 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1098 separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
1099 name_copies, decl_copies);
1101 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1103 gimple stmt = gsi_stmt (gsi);
1105 if (is_gimple_debug (stmt))
1106 has_debug_stmt = true;
1107 else
1108 separate_decls_in_region_stmt (entry, exit, stmt,
1109 name_copies, decl_copies);
1114 /* Now process debug bind stmts. We must not create decls while
1115 processing debug stmts, so we defer their processing so as to
1116 make sure we will have debug info for as many variables as
1117 possible (all of those that were dealt with in the loop above),
1118 and discard those for which we know there's nothing we can
1119 do. */
1120 if (has_debug_stmt)
1121 for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
1122 if (bb != entry_bb && bb != exit_bb)
1124 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
1126 gimple stmt = gsi_stmt (gsi);
1128 if (gimple_debug_bind_p (stmt))
1130 if (separate_decls_in_region_debug_bind (stmt,
1131 name_copies,
1132 decl_copies))
1134 gsi_remove (&gsi, true);
1135 continue;
1139 gsi_next (&gsi);
1143 VEC_free (basic_block, heap, body);
1145 if (htab_elements (name_copies) == 0 && htab_elements (reduction_list) == 0)
1147 /* It may happen that there is nothing to copy (if there are only
1148 loop carried and external variables in the loop). */
1149 *arg_struct = NULL;
1150 *new_arg_struct = NULL;
1152 else
1154 /* Create the type for the structure to store the ssa names to. */
1155 type = lang_hooks.types.make_type (RECORD_TYPE);
1156 type_name = build_decl (BUILTINS_LOCATION,
1157 TYPE_DECL, create_tmp_var_name (".paral_data"),
1158 type);
1159 TYPE_NAME (type) = type_name;
1161 htab_traverse (name_copies, add_field_for_name, type);
1162 if (reduction_list && htab_elements (reduction_list) > 0)
1164 /* Create the fields for reductions. */
1165 htab_traverse (reduction_list, add_field_for_reduction,
1166 type);
1168 layout_type (type);
1170 /* Create the loads and stores. */
1171 *arg_struct = create_tmp_var (type, ".paral_data_store");
1172 add_referenced_var (*arg_struct);
1173 nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load");
1174 add_referenced_var (nvar);
1175 *new_arg_struct = make_ssa_name (nvar, NULL);
1177 ld_st_data->store = *arg_struct;
1178 ld_st_data->load = *new_arg_struct;
1179 ld_st_data->store_bb = bb0;
1180 ld_st_data->load_bb = bb1;
1182 htab_traverse (name_copies, create_loads_and_stores_for_name,
1183 ld_st_data);
1185 /* Load the calculation from memory (after the join of the threads). */
1187 if (reduction_list && htab_elements (reduction_list) > 0)
1189 htab_traverse (reduction_list, create_stores_for_reduction,
1190 ld_st_data);
1191 clsn_data.load = make_ssa_name (nvar, NULL);
1192 clsn_data.load_bb = exit->dest;
1193 clsn_data.store = ld_st_data->store;
1194 create_final_loads_for_reduction (reduction_list, &clsn_data);
1198 htab_delete (decl_copies);
1199 htab_delete (name_copies);
1202 /* Bitmap containing uids of functions created by parallelization. We cannot
1203 allocate it from the default obstack, as it must live across compilation
1204 of several functions; we make it gc allocated instead. */
1206 static GTY(()) bitmap parallelized_functions;
1208 /* Returns true if FN was created by create_loop_fn. */
1210 static bool
1211 parallelized_function_p (tree fn)
1213 if (!parallelized_functions || !DECL_ARTIFICIAL (fn))
1214 return false;
1216 return bitmap_bit_p (parallelized_functions, DECL_UID (fn));
1219 /* Creates and returns an empty function that will receive the body of
1220 a parallelized loop. */
1222 static tree
1223 create_loop_fn (void)
1225 char buf[100];
1226 char *tname;
1227 tree decl, type, name, t;
1228 struct function *act_cfun = cfun;
1229 static unsigned loopfn_num;
1231 snprintf (buf, 100, "%s.$loopfn", current_function_name ());
1232 ASM_FORMAT_PRIVATE_NAME (tname, buf, loopfn_num++);
1233 clean_symbol_name (tname);
1234 name = get_identifier (tname);
1235 type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
1237 decl = build_decl (BUILTINS_LOCATION,
1238 FUNCTION_DECL, name, type);
1239 if (!parallelized_functions)
1240 parallelized_functions = BITMAP_GGC_ALLOC ();
1241 bitmap_set_bit (parallelized_functions, DECL_UID (decl));
1243 TREE_STATIC (decl) = 1;
1244 TREE_USED (decl) = 1;
1245 DECL_ARTIFICIAL (decl) = 1;
1246 DECL_IGNORED_P (decl) = 0;
1247 TREE_PUBLIC (decl) = 0;
1248 DECL_UNINLINABLE (decl) = 1;
1249 DECL_EXTERNAL (decl) = 0;
1250 DECL_CONTEXT (decl) = NULL_TREE;
1251 DECL_INITIAL (decl) = make_node (BLOCK);
1253 t = build_decl (BUILTINS_LOCATION,
1254 RESULT_DECL, NULL_TREE, void_type_node);
1255 DECL_ARTIFICIAL (t) = 1;
1256 DECL_IGNORED_P (t) = 1;
1257 DECL_RESULT (decl) = t;
1259 t = build_decl (BUILTINS_LOCATION,
1260 PARM_DECL, get_identifier (".paral_data_param"),
1261 ptr_type_node);
1262 DECL_ARTIFICIAL (t) = 1;
1263 DECL_ARG_TYPE (t) = ptr_type_node;
1264 DECL_CONTEXT (t) = decl;
1265 TREE_USED (t) = 1;
1266 DECL_ARGUMENTS (decl) = t;
1268 allocate_struct_function (decl, false);
1270 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1271 it. */
1272 set_cfun (act_cfun);
1274 return decl;
1277 /* Moves the exit condition of LOOP to the beginning of its header, and
1278 duplicates the part of the last iteration that gets disabled to the
1279 exit of the loop. NIT is the number of iterations of the loop
1280 (used to initialize the variables in the duplicated part).
1282 TODO: the common case is that latch of the loop is empty and immediately
1283 follows the loop exit. In this case, it would be better not to copy the
1284 body of the loop, but only move the entry of the loop directly before the
1285 exit check and increase the number of iterations of the loop by one.
1286 This may need some additional preconditioning in case NIT = ~0.
1287 REDUCTION_LIST describes the reductions in LOOP. */
1289 static void
1290 transform_to_exit_first_loop (struct loop *loop, htab_t reduction_list, tree nit)
1292 basic_block *bbs, *nbbs, ex_bb, orig_header;
1293 unsigned n;
1294 bool ok;
1295 edge exit = single_dom_exit (loop), hpred;
1296 tree control, control_name, res, t;
1297 gimple phi, nphi, cond_stmt, stmt, cond_nit;
1298 gimple_stmt_iterator gsi;
1299 tree nit_1;
1301 split_block_after_labels (loop->header);
1302 orig_header = single_succ (loop->header);
1303 hpred = single_succ_edge (loop->header);
1305 cond_stmt = last_stmt (exit->src);
1306 control = gimple_cond_lhs (cond_stmt);
1307 gcc_assert (gimple_cond_rhs (cond_stmt) == nit);
1309 /* Make sure that we have phi nodes on exit for all loop header phis
1310 (create_parallel_loop requires that). */
1311 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1313 phi = gsi_stmt (gsi);
1314 res = PHI_RESULT (phi);
1315 t = make_ssa_name (SSA_NAME_VAR (res), phi);
1316 SET_PHI_RESULT (phi, t);
1317 nphi = create_phi_node (res, orig_header);
1318 SSA_NAME_DEF_STMT (res) = nphi;
1319 add_phi_arg (nphi, t, hpred, UNKNOWN_LOCATION);
1321 if (res == control)
1323 gimple_cond_set_lhs (cond_stmt, t);
1324 update_stmt (cond_stmt);
1325 control = t;
1328 bbs = get_loop_body_in_dom_order (loop);
1330 for (n = 0; bbs[n] != loop->latch; n++)
1331 continue;
1332 nbbs = XNEWVEC (basic_block, n);
1333 ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
1334 bbs + 1, n, nbbs);
1335 gcc_assert (ok);
1336 free (bbs);
1337 ex_bb = nbbs[0];
1338 free (nbbs);
1340 /* Other than reductions, the only gimple reg that should be copied
1341 out of the loop is the control variable. */
1343 control_name = NULL_TREE;
1344 for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); )
1346 phi = gsi_stmt (gsi);
1347 res = PHI_RESULT (phi);
1348 if (!is_gimple_reg (res))
1350 gsi_next (&gsi);
1351 continue;
1354 /* Check if it is a part of reduction. If it is,
1355 keep the phi at the reduction's keep_res field. The
1356 PHI_RESULT of this phi is the resulting value of the reduction
1357 variable when exiting the loop. */
1359 exit = single_dom_exit (loop);
1361 if (htab_elements (reduction_list) > 0)
1363 struct reduction_info *red;
1365 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1366 red = reduction_phi (reduction_list, SSA_NAME_DEF_STMT (val));
1367 if (red)
1369 red->keep_res = phi;
1370 gsi_next (&gsi);
1371 continue;
1374 gcc_assert (control_name == NULL_TREE
1375 && SSA_NAME_VAR (res) == SSA_NAME_VAR (control));
1376 control_name = res;
1377 remove_phi_node (&gsi, false);
1379 gcc_assert (control_name != NULL_TREE);
1381 /* Initialize the control variable to number of iterations
1382 according to the rhs of the exit condition. */
1383 gsi = gsi_after_labels (ex_bb);
1384 cond_nit = last_stmt (exit->src);
1385 nit_1 = gimple_cond_rhs (cond_nit);
1386 nit_1 = force_gimple_operand_gsi (&gsi,
1387 fold_convert (TREE_TYPE (control_name), nit_1),
1388 false, NULL_TREE, false, GSI_SAME_STMT);
1389 stmt = gimple_build_assign (control_name, nit_1);
1390 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1391 SSA_NAME_DEF_STMT (control_name) = stmt;
1394 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
1395 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
1396 NEW_DATA is the variable that should be initialized from the argument
1397 of LOOP_FN. N_THREADS is the requested number of threads. Returns the
1398 basic block containing GIMPLE_OMP_PARALLEL tree. */
1400 static basic_block
1401 create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
1402 tree new_data, unsigned n_threads)
1404 gimple_stmt_iterator gsi;
1405 basic_block bb, paral_bb, for_bb, ex_bb;
1406 tree t, param;
1407 gimple stmt, for_stmt, phi, cond_stmt;
1408 tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
1409 edge exit, nexit, guard, end, e;
1411 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
1412 bb = loop_preheader_edge (loop)->src;
1413 paral_bb = single_pred (bb);
1414 gsi = gsi_last_bb (paral_bb);
1416 t = build_omp_clause (BUILTINS_LOCATION, OMP_CLAUSE_NUM_THREADS);
1417 OMP_CLAUSE_NUM_THREADS_EXPR (t)
1418 = build_int_cst (integer_type_node, n_threads);
1419 stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
1421 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1423 /* Initialize NEW_DATA. */
1424 if (data)
1426 gsi = gsi_after_labels (bb);
1428 param = make_ssa_name (DECL_ARGUMENTS (loop_fn), NULL);
1429 stmt = gimple_build_assign (param, build_fold_addr_expr (data));
1430 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1431 SSA_NAME_DEF_STMT (param) = stmt;
1433 stmt = gimple_build_assign (new_data,
1434 fold_convert (TREE_TYPE (new_data), param));
1435 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
1436 SSA_NAME_DEF_STMT (new_data) = stmt;
1439 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
1440 bb = split_loop_exit_edge (single_dom_exit (loop));
1441 gsi = gsi_last_bb (bb);
1442 gsi_insert_after (&gsi, gimple_build_omp_return (false), GSI_NEW_STMT);
1444 /* Extract data for GIMPLE_OMP_FOR. */
1445 gcc_assert (loop->header == single_dom_exit (loop)->src);
1446 cond_stmt = last_stmt (loop->header);
1448 cvar = gimple_cond_lhs (cond_stmt);
1449 cvar_base = SSA_NAME_VAR (cvar);
1450 phi = SSA_NAME_DEF_STMT (cvar);
1451 cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1452 initvar = make_ssa_name (cvar_base, NULL);
1453 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
1454 initvar);
1455 cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1457 gsi = gsi_last_bb (loop->latch);
1458 gcc_assert (gsi_stmt (gsi) == SSA_NAME_DEF_STMT (cvar_next));
1459 gsi_remove (&gsi, true);
1461 /* Prepare cfg. */
1462 for_bb = split_edge (loop_preheader_edge (loop));
1463 ex_bb = split_loop_exit_edge (single_dom_exit (loop));
1464 extract_true_false_edges_from_block (loop->header, &nexit, &exit);
1465 gcc_assert (exit == single_dom_exit (loop));
1467 guard = make_edge (for_bb, ex_bb, 0);
1468 single_succ_edge (loop->latch)->flags = 0;
1469 end = make_edge (loop->latch, ex_bb, EDGE_FALLTHRU);
1470 for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); gsi_next (&gsi))
1472 source_location locus;
1473 tree def;
1474 phi = gsi_stmt (gsi);
1475 stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi, exit));
1477 def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop));
1478 locus = gimple_phi_arg_location_from_edge (stmt,
1479 loop_preheader_edge (loop));
1480 add_phi_arg (phi, def, guard, locus);
1482 def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_latch_edge (loop));
1483 locus = gimple_phi_arg_location_from_edge (stmt, loop_latch_edge (loop));
1484 add_phi_arg (phi, def, end, locus);
1486 e = redirect_edge_and_branch (exit, nexit->dest);
1487 PENDING_STMT (e) = NULL;
1489 /* Emit GIMPLE_OMP_FOR. */
1490 gimple_cond_set_lhs (cond_stmt, cvar_base);
1491 type = TREE_TYPE (cvar);
1492 t = build_omp_clause (BUILTINS_LOCATION, OMP_CLAUSE_SCHEDULE);
1493 OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
1495 for_stmt = gimple_build_omp_for (NULL, t, 1, NULL);
1496 gimple_omp_for_set_index (for_stmt, 0, initvar);
1497 gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
1498 gimple_omp_for_set_final (for_stmt, 0, gimple_cond_rhs (cond_stmt));
1499 gimple_omp_for_set_cond (for_stmt, 0, gimple_cond_code (cond_stmt));
1500 gimple_omp_for_set_incr (for_stmt, 0, build2 (PLUS_EXPR, type,
1501 cvar_base,
1502 build_int_cst (type, 1)));
1504 gsi = gsi_last_bb (for_bb);
1505 gsi_insert_after (&gsi, for_stmt, GSI_NEW_STMT);
1506 SSA_NAME_DEF_STMT (initvar) = for_stmt;
1508 /* Emit GIMPLE_OMP_CONTINUE. */
1509 gsi = gsi_last_bb (loop->latch);
1510 stmt = gimple_build_omp_continue (cvar_next, cvar);
1511 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1512 SSA_NAME_DEF_STMT (cvar_next) = stmt;
1514 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
1515 gsi = gsi_last_bb (ex_bb);
1516 gsi_insert_after (&gsi, gimple_build_omp_return (true), GSI_NEW_STMT);
1518 return paral_bb;
1521 /* Generates code to execute the iterations of LOOP in N_THREADS
1522 threads in parallel.
1524 NITER describes number of iterations of LOOP.
1525 REDUCTION_LIST describes the reductions existent in the LOOP. */
1527 static void
1528 gen_parallel_loop (struct loop *loop, htab_t reduction_list,
1529 unsigned n_threads, struct tree_niter_desc *niter)
1531 loop_iterator li;
1532 tree many_iterations_cond, type, nit;
1533 tree arg_struct, new_arg_struct;
1534 gimple_seq stmts;
1535 basic_block parallel_head;
1536 edge entry, exit;
1537 struct clsn_data clsn_data;
1538 unsigned prob;
1540 /* From
1542 ---------------------------------------------------------------------
1543 loop
1545 IV = phi (INIT, IV + STEP)
1546 BODY1;
1547 if (COND)
1548 break;
1549 BODY2;
1551 ---------------------------------------------------------------------
1553 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
1554 we generate the following code:
1556 ---------------------------------------------------------------------
1558 if (MAY_BE_ZERO
1559 || NITER < MIN_PER_THREAD * N_THREADS)
1560 goto original;
1562 BODY1;
1563 store all local loop-invariant variables used in body of the loop to DATA.
1564 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
1565 load the variables from DATA.
1566 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
1567 BODY2;
1568 BODY1;
1569 GIMPLE_OMP_CONTINUE;
1570 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
1571 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
1572 goto end;
1574 original:
1575 loop
1577 IV = phi (INIT, IV + STEP)
1578 BODY1;
1579 if (COND)
1580 break;
1581 BODY2;
1584 end:
1588 /* Create two versions of the loop -- in the old one, we know that the
1589 number of iterations is large enough, and we will transform it into the
1590 loop that will be split to loop_fn, the new one will be used for the
1591 remaining iterations. */
1593 type = TREE_TYPE (niter->niter);
1594 nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true,
1595 NULL_TREE);
1596 if (stmts)
1597 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1599 many_iterations_cond =
1600 fold_build2 (GE_EXPR, boolean_type_node,
1601 nit, build_int_cst (type, MIN_PER_THREAD * n_threads));
1602 many_iterations_cond
1603 = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1604 invert_truthvalue (unshare_expr (niter->may_be_zero)),
1605 many_iterations_cond);
1606 many_iterations_cond
1607 = force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
1608 if (stmts)
1609 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1610 if (!is_gimple_condexpr (many_iterations_cond))
1612 many_iterations_cond
1613 = force_gimple_operand (many_iterations_cond, &stmts,
1614 true, NULL_TREE);
1615 if (stmts)
1616 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1619 initialize_original_copy_tables ();
1621 /* We assume that the loop usually iterates a lot. */
1622 prob = 4 * REG_BR_PROB_BASE / 5;
1623 loop_version (loop, many_iterations_cond, NULL,
1624 prob, prob, REG_BR_PROB_BASE - prob, true);
1625 update_ssa (TODO_update_ssa);
1626 free_original_copy_tables ();
1628 /* Base all the induction variables in LOOP on a single control one. */
1629 canonicalize_loop_ivs (loop, &nit, true);
1631 /* Ensure that the exit condition is the first statement in the loop. */
1632 transform_to_exit_first_loop (loop, reduction_list, nit);
1634 /* Generate initializations for reductions. */
1635 if (htab_elements (reduction_list) > 0)
1636 htab_traverse (reduction_list, initialize_reductions, loop);
1638 /* Eliminate the references to local variables from the loop. */
1639 gcc_assert (single_exit (loop));
1640 entry = loop_preheader_edge (loop);
1641 exit = single_dom_exit (loop);
1643 eliminate_local_variables (entry, exit);
1644 /* In the old loop, move all variables non-local to the loop to a structure
1645 and back, and create separate decls for the variables used in loop. */
1646 separate_decls_in_region (entry, exit, reduction_list, &arg_struct,
1647 &new_arg_struct, &clsn_data);
1649 /* Create the parallel constructs. */
1650 parallel_head = create_parallel_loop (loop, create_loop_fn (), arg_struct,
1651 new_arg_struct, n_threads);
1652 if (htab_elements (reduction_list) > 0)
1653 create_call_for_reduction (loop, reduction_list, &clsn_data);
1655 scev_reset ();
1657 /* Cancel the loop (it is simpler to do it here rather than to teach the
1658 expander to do it). */
1659 cancel_loop_tree (loop);
1661 /* Free loop bound estimations that could contain references to
1662 removed statements. */
1663 FOR_EACH_LOOP (li, loop, 0)
1664 free_numbers_of_iterations_estimates_loop (loop);
1666 /* Expand the parallel constructs. We do it directly here instead of running
1667 a separate expand_omp pass, since it is more efficient, and less likely to
1668 cause troubles with further analyses not being able to deal with the
1669 OMP trees. */
1671 omp_expand_local (parallel_head);
1674 /* Returns true when LOOP contains vector phi nodes. */
1676 static bool
1677 loop_has_vector_phi_nodes (struct loop *loop ATTRIBUTE_UNUSED)
1679 unsigned i;
1680 basic_block *bbs = get_loop_body_in_dom_order (loop);
1681 gimple_stmt_iterator gsi;
1682 bool res = true;
1684 for (i = 0; i < loop->num_nodes; i++)
1685 for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
1686 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi_stmt (gsi)))) == VECTOR_TYPE)
1687 goto end;
1689 res = false;
1690 end:
1691 free (bbs);
1692 return res;
1695 /* Create a reduction_info struct, initialize it with REDUC_STMT
1696 and PHI, insert it to the REDUCTION_LIST. */
1698 static void
1699 build_new_reduction (htab_t reduction_list, gimple reduc_stmt, gimple phi)
1701 PTR *slot;
1702 struct reduction_info *new_reduction;
1704 gcc_assert (reduc_stmt);
1706 if (dump_file && (dump_flags & TDF_DETAILS))
1708 fprintf (dump_file,
1709 "Detected reduction. reduction stmt is: \n");
1710 print_gimple_stmt (dump_file, reduc_stmt, 0, 0);
1711 fprintf (dump_file, "\n");
1714 new_reduction = XCNEW (struct reduction_info);
1716 new_reduction->reduc_stmt = reduc_stmt;
1717 new_reduction->reduc_phi = phi;
1718 new_reduction->reduction_code = gimple_assign_rhs_code (reduc_stmt);
1719 slot = htab_find_slot (reduction_list, new_reduction, INSERT);
1720 *slot = new_reduction;
1723 /* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
1725 static void
1726 gather_scalar_reductions (loop_p loop, htab_t reduction_list)
1728 gimple_stmt_iterator gsi;
1729 loop_vec_info simple_loop_info;
1731 vect_dump = NULL;
1732 simple_loop_info = vect_analyze_loop_form (loop);
1734 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1736 gimple phi = gsi_stmt (gsi);
1737 affine_iv iv;
1738 tree res = PHI_RESULT (phi);
1739 bool double_reduc;
1741 if (!is_gimple_reg (res))
1742 continue;
1744 if (!simple_iv (loop, loop, res, &iv, true)
1745 && simple_loop_info)
1747 gimple reduc_stmt = vect_is_simple_reduction (simple_loop_info, phi, true, &double_reduc);
1748 if (reduc_stmt && !double_reduc)
1749 build_new_reduction (reduction_list, reduc_stmt, phi);
1752 destroy_loop_vec_info (simple_loop_info, true);
1755 /* Try to initialize NITER for code generation part. */
1757 static bool
1758 try_get_loop_niter (loop_p loop, struct tree_niter_desc *niter)
1760 edge exit = single_dom_exit (loop);
1762 gcc_assert (exit);
1764 /* We need to know # of iterations, and there should be no uses of values
1765 defined inside loop outside of it, unless the values are invariants of
1766 the loop. */
1767 if (!number_of_iterations_exit (loop, exit, niter, false))
1769 if (dump_file && (dump_flags & TDF_DETAILS))
1770 fprintf (dump_file, " FAILED: number of iterations not known\n");
1771 return false;
1774 return true;
1777 /* Try to initialize REDUCTION_LIST for code generation part.
1778 REDUCTION_LIST describes the reductions. */
1780 static bool
1781 try_create_reduction_list (loop_p loop, htab_t reduction_list)
1783 edge exit = single_dom_exit (loop);
1784 gimple_stmt_iterator gsi;
1786 gcc_assert (exit);
1788 gather_scalar_reductions (loop, reduction_list);
1791 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
1793 gimple phi = gsi_stmt (gsi);
1794 struct reduction_info *red;
1795 imm_use_iterator imm_iter;
1796 use_operand_p use_p;
1797 gimple reduc_phi;
1798 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1800 if (is_gimple_reg (val))
1802 if (dump_file && (dump_flags & TDF_DETAILS))
1804 fprintf (dump_file, "phi is ");
1805 print_gimple_stmt (dump_file, phi, 0, 0);
1806 fprintf (dump_file, "arg of phi to exit: value ");
1807 print_generic_expr (dump_file, val, 0);
1808 fprintf (dump_file, " used outside loop\n");
1809 fprintf (dump_file,
1810 " checking if it a part of reduction pattern: \n");
1812 if (htab_elements (reduction_list) == 0)
1814 if (dump_file && (dump_flags & TDF_DETAILS))
1815 fprintf (dump_file,
1816 " FAILED: it is not a part of reduction.\n");
1817 return false;
1819 reduc_phi = NULL;
1820 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
1822 if (flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
1824 reduc_phi = USE_STMT (use_p);
1825 break;
1828 red = reduction_phi (reduction_list, reduc_phi);
1829 if (red == NULL)
1831 if (dump_file && (dump_flags & TDF_DETAILS))
1832 fprintf (dump_file,
1833 " FAILED: it is not a part of reduction.\n");
1834 return false;
1836 if (dump_file && (dump_flags & TDF_DETAILS))
1838 fprintf (dump_file, "reduction phi is ");
1839 print_gimple_stmt (dump_file, red->reduc_phi, 0, 0);
1840 fprintf (dump_file, "reduction stmt is ");
1841 print_gimple_stmt (dump_file, red->reduc_stmt, 0, 0);
1846 /* The iterations of the loop may communicate only through bivs whose
1847 iteration space can be distributed efficiently. */
1848 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1850 gimple phi = gsi_stmt (gsi);
1851 tree def = PHI_RESULT (phi);
1852 affine_iv iv;
1854 if (is_gimple_reg (def) && !simple_iv (loop, loop, def, &iv, true))
1856 struct reduction_info *red;
1858 red = reduction_phi (reduction_list, phi);
1859 if (red == NULL)
1861 if (dump_file && (dump_flags & TDF_DETAILS))
1862 fprintf (dump_file,
1863 " FAILED: scalar dependency between iterations\n");
1864 return false;
1870 return true;
1873 /* Detect parallel loops and generate parallel code using libgomp
1874 primitives. Returns true if some loop was parallelized, false
1875 otherwise. */
1877 bool
1878 parallelize_loops (void)
1880 unsigned n_threads = flag_tree_parallelize_loops;
1881 bool changed = false;
1882 struct loop *loop;
1883 struct tree_niter_desc niter_desc;
1884 loop_iterator li;
1885 htab_t reduction_list;
1886 HOST_WIDE_INT estimated;
1887 LOC loop_loc;
1889 /* Do not parallelize loops in the functions created by parallelization. */
1890 if (parallelized_function_p (cfun->decl))
1891 return false;
1892 if (cfun->has_nonlocal_label)
1893 return false;
1895 reduction_list = htab_create (10, reduction_info_hash,
1896 reduction_info_eq, free);
1897 init_stmt_vec_info_vec ();
1899 FOR_EACH_LOOP (li, loop, 0)
1901 htab_empty (reduction_list);
1902 if (dump_file && (dump_flags & TDF_DETAILS))
1904 fprintf (dump_file, "Trying loop %d as candidate\n",loop->num);
1905 if (loop->inner)
1906 fprintf (dump_file, "loop %d is not innermost\n",loop->num);
1907 else
1908 fprintf (dump_file, "loop %d is innermost\n",loop->num);
1911 /* If we use autopar in graphite pass, we use its marked dependency
1912 checking results. */
1913 if (flag_loop_parallelize_all && !loop->can_be_parallel)
1915 if (dump_file && (dump_flags & TDF_DETAILS))
1916 fprintf (dump_file, "loop is not parallel according to graphite\n");
1917 continue;
1920 if (!single_dom_exit (loop))
1923 if (dump_file && (dump_flags & TDF_DETAILS))
1924 fprintf (dump_file, "loop is !single_dom_exit\n");
1926 continue;
1929 if (/* And of course, the loop must be parallelizable. */
1930 !can_duplicate_loop_p (loop)
1931 || loop_has_blocks_with_irreducible_flag (loop)
1932 || (loop_preheader_edge (loop)->src->flags & BB_IRREDUCIBLE_LOOP)
1933 /* FIXME: the check for vector phi nodes could be removed. */
1934 || loop_has_vector_phi_nodes (loop))
1935 continue;
1936 estimated = estimated_loop_iterations_int (loop, false);
1937 /* FIXME: Bypass this check as graphite doesn't update the
1938 count and frequency correctly now. */
1939 if (!flag_loop_parallelize_all
1940 && ((estimated !=-1
1941 && estimated <= (HOST_WIDE_INT) n_threads * MIN_PER_THREAD)
1942 /* Do not bother with loops in cold areas. */
1943 || optimize_loop_nest_for_size_p (loop)))
1944 continue;
1946 if (!try_get_loop_niter (loop, &niter_desc))
1947 continue;
1949 if (!try_create_reduction_list (loop, reduction_list))
1950 continue;
1952 if (!flag_loop_parallelize_all && !loop_parallel_p (loop))
1953 continue;
1955 changed = true;
1956 if (dump_file && (dump_flags & TDF_DETAILS))
1958 if (loop->inner)
1959 fprintf (dump_file, "parallelizing outer loop %d\n",loop->header->index);
1960 else
1961 fprintf (dump_file, "parallelizing inner loop %d\n",loop->header->index);
1962 loop_loc = find_loop_location (loop);
1963 if (loop_loc != UNKNOWN_LOC)
1964 fprintf (dump_file, "\nloop at %s:%d: ",
1965 LOC_FILE (loop_loc), LOC_LINE (loop_loc));
1967 gen_parallel_loop (loop, reduction_list,
1968 n_threads, &niter_desc);
1969 verify_flow_info ();
1970 verify_dominators (CDI_DOMINATORS);
1971 verify_loop_structure ();
1972 verify_loop_closed_ssa ();
1975 free_stmt_vec_info_vec ();
1976 htab_delete (reduction_list);
1978 /* Parallelization will cause new function calls to be inserted through
1979 which local variables will escape. Reset the points-to solutions
1980 for ESCAPED and CALLUSED. */
1981 if (changed)
1983 pt_solution_reset (&cfun->gimple_df->escaped);
1984 pt_solution_reset (&cfun->gimple_df->callused);
1987 return changed;
1990 #include "gt-tree-parloops.h"