Update gcc-50 to SVN version 221572
[dragonfly.git] / contrib / gcc-5.0 / gcc / tree-parloops.c
CommitLineData
dda118e3
JM
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>.
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not see
20<http://www.gnu.org/licenses/>. */
21
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "hash-set.h"
26#include "machmode.h"
27#include "vec.h"
28#include "double-int.h"
29#include "input.h"
30#include "alias.h"
31#include "symtab.h"
32#include "options.h"
33#include "wide-int.h"
34#include "inchash.h"
35#include "tree.h"
36#include "fold-const.h"
37#include "predict.h"
38#include "tm.h"
39#include "hard-reg-set.h"
40#include "input.h"
41#include "function.h"
42#include "dominance.h"
43#include "cfg.h"
44#include "basic-block.h"
45#include "tree-ssa-alias.h"
46#include "internal-fn.h"
47#include "gimple-expr.h"
48#include "is-a.h"
49#include "gimple.h"
50#include "gimplify.h"
51#include "gimple-iterator.h"
52#include "gimplify-me.h"
53#include "gimple-walk.h"
54#include "stor-layout.h"
55#include "tree-nested.h"
56#include "gimple-ssa.h"
57#include "tree-cfg.h"
58#include "tree-phinodes.h"
59#include "ssa-iterators.h"
60#include "stringpool.h"
61#include "tree-ssanames.h"
62#include "tree-ssa-loop-ivopts.h"
63#include "tree-ssa-loop-manip.h"
64#include "tree-ssa-loop-niter.h"
65#include "tree-ssa-loop.h"
66#include "tree-into-ssa.h"
67#include "cfgloop.h"
68#include "tree-data-ref.h"
69#include "tree-scalar-evolution.h"
70#include "gimple-pretty-print.h"
71#include "tree-pass.h"
72#include "langhooks.h"
73#include "tree-vectorizer.h"
74#include "tree-hasher.h"
75#include "tree-parloops.h"
76#include "omp-low.h"
77#include "tree-nested.h"
38c0c85b
JM
78#include "plugin-api.h"
79#include "ipa-ref.h"
80#include "cgraph.h"
dda118e3
JM
81
82/* This pass tries to distribute iterations of loops into several threads.
83 The implementation is straightforward -- for each loop we test whether its
84 iterations are independent, and if it is the case (and some additional
85 conditions regarding profitability and correctness are satisfied), we
86 add GIMPLE_OMP_PARALLEL and GIMPLE_OMP_FOR codes and let omp expansion
87 machinery do its job.
88
89 The most of the complexity is in bringing the code into shape expected
90 by the omp expanders:
91 -- for GIMPLE_OMP_FOR, ensuring that the loop has only one induction
92 variable and that the exit test is at the start of the loop body
93 -- for GIMPLE_OMP_PARALLEL, replacing the references to local addressable
94 variables by accesses through pointers, and breaking up ssa chains
95 by storing the values incoming to the parallelized loop to a structure
96 passed to the new function as an argument (something similar is done
97 in omp gimplification, unfortunately only a small part of the code
98 can be shared).
99
100 TODO:
101 -- if there are several parallelizable loops in a function, it may be
102 possible to generate the threads just once (using synchronization to
103 ensure that cross-loop dependences are obeyed).
104 -- handling of common reduction patterns for outer loops.
105
106 More info can also be found at http://gcc.gnu.org/wiki/AutoParInGCC */
107/*
108 Reduction handling:
109 currently we use vect_force_simple_reduction() to detect reduction patterns.
110 The code transformation will be introduced by an example.
111
112
113parloop
114{
115 int sum=1;
116
117 for (i = 0; i < N; i++)
118 {
119 x[i] = i + 3;
120 sum+=x[i];
121 }
122}
123
124gimple-like code:
125header_bb:
126
127 # sum_29 = PHI <sum_11(5), 1(3)>
128 # i_28 = PHI <i_12(5), 0(3)>
129 D.1795_8 = i_28 + 3;
130 x[i_28] = D.1795_8;
131 sum_11 = D.1795_8 + sum_29;
132 i_12 = i_28 + 1;
133 if (N_6(D) > i_12)
134 goto header_bb;
135
136
137exit_bb:
138
139 # sum_21 = PHI <sum_11(4)>
140 printf (&"%d"[0], sum_21);
141
142
143after reduction transformation (only relevant parts):
144
145parloop
146{
147
148....
149
150
151 # Storing the initial value given by the user. #
152
153 .paral_data_store.32.sum.27 = 1;
154
155 #pragma omp parallel num_threads(4)
156
157 #pragma omp for schedule(static)
158
159 # The neutral element corresponding to the particular
160 reduction's operation, e.g. 0 for PLUS_EXPR,
161 1 for MULT_EXPR, etc. replaces the user's initial value. #
162
163 # sum.27_29 = PHI <sum.27_11, 0>
164
165 sum.27_11 = D.1827_8 + sum.27_29;
166
167 GIMPLE_OMP_CONTINUE
168
169 # Adding this reduction phi is done at create_phi_for_local_result() #
170 # sum.27_56 = PHI <sum.27_11, 0>
171 GIMPLE_OMP_RETURN
172
173 # Creating the atomic operation is done at
174 create_call_for_reduction_1() #
175
176 #pragma omp atomic_load
177 D.1839_59 = *&.paral_data_load.33_51->reduction.23;
178 D.1840_60 = sum.27_56 + D.1839_59;
179 #pragma omp atomic_store (D.1840_60);
180
181 GIMPLE_OMP_RETURN
182
183 # collecting the result after the join of the threads is done at
184 create_loads_for_reductions().
185 The value computed by the threads is loaded from the
186 shared struct. #
187
188
189 .paral_data_load.33_52 = &.paral_data_store.32;
190 sum_37 = .paral_data_load.33_52->sum.27;
191 sum_43 = D.1795_41 + sum_37;
192
193 exit bb:
194 # sum_21 = PHI <sum_43, sum_26>
195 printf (&"%d"[0], sum_21);
196
197...
198
199}
200
201*/
202
203/* Minimal number of iterations of a loop that should be executed in each
204 thread. */
205#define MIN_PER_THREAD 100
206
207/* Element of the hashtable, representing a
208 reduction in the current loop. */
209struct reduction_info
210{
211 gimple reduc_stmt; /* reduction statement. */
212 gimple reduc_phi; /* The phi node defining the reduction. */
213 enum tree_code reduction_code;/* code for the reduction operation. */
214 unsigned reduc_version; /* SSA_NAME_VERSION of original reduc_phi
215 result. */
216 gphi *keep_res; /* The PHI_RESULT of this phi is the resulting value
217 of the reduction variable when existing the loop. */
218 tree initial_value; /* The initial value of the reduction var before entering the loop. */
219 tree field; /* the name of the field in the parloop data structure intended for reduction. */
220 tree init; /* reduction initialization value. */
221 gphi *new_phi; /* (helper field) Newly created phi node whose result
222 will be passed to the atomic operation. Represents
223 the local result each thread computed for the reduction
224 operation. */
225};
226
227/* Reduction info hashtable helpers. */
228
229struct reduction_hasher : typed_free_remove <reduction_info>
230{
231 typedef reduction_info value_type;
232 typedef reduction_info compare_type;
233 static inline hashval_t hash (const value_type *);
234 static inline bool equal (const value_type *, const compare_type *);
235};
236
237/* Equality and hash functions for hashtab code. */
238
239inline bool
240reduction_hasher::equal (const value_type *a, const compare_type *b)
241{
242 return (a->reduc_phi == b->reduc_phi);
243}
244
245inline hashval_t
246reduction_hasher::hash (const value_type *a)
247{
248 return a->reduc_version;
249}
250
251typedef hash_table<reduction_hasher> reduction_info_table_type;
252
253
254static struct reduction_info *
255reduction_phi (reduction_info_table_type *reduction_list, gimple phi)
256{
257 struct reduction_info tmpred, *red;
258
259 if (reduction_list->elements () == 0 || phi == NULL)
260 return NULL;
261
262 tmpred.reduc_phi = phi;
263 tmpred.reduc_version = gimple_uid (phi);
264 red = reduction_list->find (&tmpred);
265
266 return red;
267}
268
269/* Element of hashtable of names to copy. */
270
271struct name_to_copy_elt
272{
273 unsigned version; /* The version of the name to copy. */
274 tree new_name; /* The new name used in the copy. */
275 tree field; /* The field of the structure used to pass the
276 value. */
277};
278
279/* Name copies hashtable helpers. */
280
281struct name_to_copy_hasher : typed_free_remove <name_to_copy_elt>
282{
283 typedef name_to_copy_elt value_type;
284 typedef name_to_copy_elt compare_type;
285 static inline hashval_t hash (const value_type *);
286 static inline bool equal (const value_type *, const compare_type *);
287};
288
289/* Equality and hash functions for hashtab code. */
290
291inline bool
292name_to_copy_hasher::equal (const value_type *a, const compare_type *b)
293{
294 return a->version == b->version;
295}
296
297inline hashval_t
298name_to_copy_hasher::hash (const value_type *a)
299{
300 return (hashval_t) a->version;
301}
302
303typedef hash_table<name_to_copy_hasher> name_to_copy_table_type;
304
305/* A transformation matrix, which is a self-contained ROWSIZE x COLSIZE
306 matrix. Rather than use floats, we simply keep a single DENOMINATOR that
307 represents the denominator for every element in the matrix. */
308typedef struct lambda_trans_matrix_s
309{
310 lambda_matrix matrix;
311 int rowsize;
312 int colsize;
313 int denominator;
314} *lambda_trans_matrix;
315#define LTM_MATRIX(T) ((T)->matrix)
316#define LTM_ROWSIZE(T) ((T)->rowsize)
317#define LTM_COLSIZE(T) ((T)->colsize)
318#define LTM_DENOMINATOR(T) ((T)->denominator)
319
320/* Allocate a new transformation matrix. */
321
322static lambda_trans_matrix
323lambda_trans_matrix_new (int colsize, int rowsize,
324 struct obstack * lambda_obstack)
325{
326 lambda_trans_matrix ret;
327
328 ret = (lambda_trans_matrix)
329 obstack_alloc (lambda_obstack, sizeof (struct lambda_trans_matrix_s));
330 LTM_MATRIX (ret) = lambda_matrix_new (rowsize, colsize, lambda_obstack);
331 LTM_ROWSIZE (ret) = rowsize;
332 LTM_COLSIZE (ret) = colsize;
333 LTM_DENOMINATOR (ret) = 1;
334 return ret;
335}
336
337/* Multiply a vector VEC by a matrix MAT.
338 MAT is an M*N matrix, and VEC is a vector with length N. The result
339 is stored in DEST which must be a vector of length M. */
340
341static void
342lambda_matrix_vector_mult (lambda_matrix matrix, int m, int n,
343 lambda_vector vec, lambda_vector dest)
344{
345 int i, j;
346
347 lambda_vector_clear (dest, m);
348 for (i = 0; i < m; i++)
349 for (j = 0; j < n; j++)
350 dest[i] += matrix[i][j] * vec[j];
351}
352
353/* Return true if TRANS is a legal transformation matrix that respects
354 the dependence vectors in DISTS and DIRS. The conservative answer
355 is false.
356
357 "Wolfe proves that a unimodular transformation represented by the
358 matrix T is legal when applied to a loop nest with a set of
359 lexicographically non-negative distance vectors RDG if and only if
360 for each vector d in RDG, (T.d >= 0) is lexicographically positive.
361 i.e.: if and only if it transforms the lexicographically positive
362 distance vectors to lexicographically positive vectors. Note that
363 a unimodular matrix must transform the zero vector (and only it) to
364 the zero vector." S.Muchnick. */
365
366static bool
367lambda_transform_legal_p (lambda_trans_matrix trans,
368 int nb_loops,
369 vec<ddr_p> dependence_relations)
370{
371 unsigned int i, j;
372 lambda_vector distres;
373 struct data_dependence_relation *ddr;
374
375 gcc_assert (LTM_COLSIZE (trans) == nb_loops
376 && LTM_ROWSIZE (trans) == nb_loops);
377
378 /* When there are no dependences, the transformation is correct. */
379 if (dependence_relations.length () == 0)
380 return true;
381
382 ddr = dependence_relations[0];
383 if (ddr == NULL)
384 return true;
385
386 /* When there is an unknown relation in the dependence_relations, we
387 know that it is no worth looking at this loop nest: give up. */
388 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
389 return false;
390
391 distres = lambda_vector_new (nb_loops);
392
393 /* For each distance vector in the dependence graph. */
394 FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
395 {
396 /* Don't care about relations for which we know that there is no
397 dependence, nor about read-read (aka. output-dependences):
398 these data accesses can happen in any order. */
399 if (DDR_ARE_DEPENDENT (ddr) == chrec_known
400 || (DR_IS_READ (DDR_A (ddr)) && DR_IS_READ (DDR_B (ddr))))
401 continue;
402
403 /* Conservatively answer: "this transformation is not valid". */
404 if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
405 return false;
406
407 /* If the dependence could not be captured by a distance vector,
408 conservatively answer that the transform is not valid. */
409 if (DDR_NUM_DIST_VECTS (ddr) == 0)
410 return false;
411
412 /* Compute trans.dist_vect */
413 for (j = 0; j < DDR_NUM_DIST_VECTS (ddr); j++)
414 {
415 lambda_matrix_vector_mult (LTM_MATRIX (trans), nb_loops, nb_loops,
416 DDR_DIST_VECT (ddr, j), distres);
417
418 if (!lambda_vector_lexico_pos (distres, nb_loops))
419 return false;
420 }
421 }
422 return true;
423}
424
425/* Data dependency analysis. Returns true if the iterations of LOOP
426 are independent on each other (that is, if we can execute them
427 in parallel). */
428
429static bool
430loop_parallel_p (struct loop *loop, struct obstack * parloop_obstack)
431{
432 vec<ddr_p> dependence_relations;
433 vec<data_reference_p> datarefs;
434 lambda_trans_matrix trans;
435 bool ret = false;
436
437 if (dump_file && (dump_flags & TDF_DETAILS))
438 {
439 fprintf (dump_file, "Considering loop %d\n", loop->num);
440 if (!loop->inner)
441 fprintf (dump_file, "loop is innermost\n");
442 else
443 fprintf (dump_file, "loop NOT innermost\n");
444 }
445
446 /* Check for problems with dependences. If the loop can be reversed,
447 the iterations are independent. */
448 auto_vec<loop_p, 3> loop_nest;
449 datarefs.create (10);
450 dependence_relations.create (100);
451 if (! compute_data_dependences_for_loop (loop, true, &loop_nest, &datarefs,
452 &dependence_relations))
453 {
454 if (dump_file && (dump_flags & TDF_DETAILS))
455 fprintf (dump_file, " FAILED: cannot analyze data dependencies\n");
456 ret = false;
457 goto end;
458 }
459 if (dump_file && (dump_flags & TDF_DETAILS))
460 dump_data_dependence_relations (dump_file, dependence_relations);
461
462 trans = lambda_trans_matrix_new (1, 1, parloop_obstack);
463 LTM_MATRIX (trans)[0][0] = -1;
464
465 if (lambda_transform_legal_p (trans, 1, dependence_relations))
466 {
467 ret = true;
468 if (dump_file && (dump_flags & TDF_DETAILS))
469 fprintf (dump_file, " SUCCESS: may be parallelized\n");
470 }
471 else if (dump_file && (dump_flags & TDF_DETAILS))
472 fprintf (dump_file,
473 " FAILED: data dependencies exist across iterations\n");
474
475 end:
476 free_dependence_relations (dependence_relations);
477 free_data_refs (datarefs);
478
479 return ret;
480}
481
482/* Return true when LOOP contains basic blocks marked with the
483 BB_IRREDUCIBLE_LOOP flag. */
484
485static inline bool
486loop_has_blocks_with_irreducible_flag (struct loop *loop)
487{
488 unsigned i;
489 basic_block *bbs = get_loop_body_in_dom_order (loop);
490 bool res = true;
491
492 for (i = 0; i < loop->num_nodes; i++)
493 if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
494 goto end;
495
496 res = false;
497 end:
498 free (bbs);
499 return res;
500}
501
502/* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
503 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
504 to their addresses that can be reused. The address of OBJ is known to
505 be invariant in the whole function. Other needed statements are placed
506 right before GSI. */
507
508static tree
509take_address_of (tree obj, tree type, edge entry,
510 int_tree_htab_type *decl_address, gimple_stmt_iterator *gsi)
511{
512 int uid;
513 tree *var_p, name, addr;
514 gassign *stmt;
515 gimple_seq stmts;
516
517 /* Since the address of OBJ is invariant, the trees may be shared.
518 Avoid rewriting unrelated parts of the code. */
519 obj = unshare_expr (obj);
520 for (var_p = &obj;
521 handled_component_p (*var_p);
522 var_p = &TREE_OPERAND (*var_p, 0))
523 continue;
524
525 /* Canonicalize the access to base on a MEM_REF. */
526 if (DECL_P (*var_p))
527 *var_p = build_simple_mem_ref (build_fold_addr_expr (*var_p));
528
529 /* Assign a canonical SSA name to the address of the base decl used
530 in the address and share it for all accesses and addresses based
531 on it. */
532 uid = DECL_UID (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));
533 int_tree_map elt;
534 elt.uid = uid;
535 int_tree_map *slot = decl_address->find_slot (elt, INSERT);
536 if (!slot->to)
537 {
538 if (gsi == NULL)
539 return NULL;
540 addr = TREE_OPERAND (*var_p, 0);
541 const char *obj_name
542 = get_name (TREE_OPERAND (TREE_OPERAND (*var_p, 0), 0));
543 if (obj_name)
544 name = make_temp_ssa_name (TREE_TYPE (addr), NULL, obj_name);
545 else
546 name = make_ssa_name (TREE_TYPE (addr));
547 stmt = gimple_build_assign (name, addr);
548 gsi_insert_on_edge_immediate (entry, stmt);
549
550 slot->uid = uid;
551 slot->to = name;
552 }
553 else
554 name = slot->to;
555
556 /* Express the address in terms of the canonical SSA name. */
557 TREE_OPERAND (*var_p, 0) = name;
558 if (gsi == NULL)
559 return build_fold_addr_expr_with_type (obj, type);
560
561 name = force_gimple_operand (build_addr (obj, current_function_decl),
562 &stmts, true, NULL_TREE);
563 if (!gimple_seq_empty_p (stmts))
564 gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
565
566 if (!useless_type_conversion_p (type, TREE_TYPE (name)))
567 {
568 name = force_gimple_operand (fold_convert (type, name), &stmts, true,
569 NULL_TREE);
570 if (!gimple_seq_empty_p (stmts))
571 gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
572 }
573
574 return name;
575}
576
577/* Callback for htab_traverse. Create the initialization statement
578 for reduction described in SLOT, and place it at the preheader of
579 the loop described in DATA. */
580
581int
582initialize_reductions (reduction_info **slot, struct loop *loop)
583{
584 tree init, c;
585 tree bvar, type, arg;
586 edge e;
587
588 struct reduction_info *const reduc = *slot;
589
590 /* Create initialization in preheader:
591 reduction_variable = initialization value of reduction. */
592
593 /* In the phi node at the header, replace the argument coming
594 from the preheader with the reduction initialization value. */
595
596 /* Create a new variable to initialize the reduction. */
597 type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
598 bvar = create_tmp_var (type, "reduction");
599
600 c = build_omp_clause (gimple_location (reduc->reduc_stmt),
601 OMP_CLAUSE_REDUCTION);
602 OMP_CLAUSE_REDUCTION_CODE (c) = reduc->reduction_code;
603 OMP_CLAUSE_DECL (c) = SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt));
604
605 init = omp_reduction_init (c, TREE_TYPE (bvar));
606 reduc->init = init;
607
608 /* Replace the argument representing the initialization value
609 with the initialization value for the reduction (neutral
610 element for the particular operation, e.g. 0 for PLUS_EXPR,
611 1 for MULT_EXPR, etc).
612 Keep the old value in a new variable "reduction_initial",
613 that will be taken in consideration after the parallel
614 computing is done. */
615
616 e = loop_preheader_edge (loop);
617 arg = PHI_ARG_DEF_FROM_EDGE (reduc->reduc_phi, e);
618 /* Create new variable to hold the initial value. */
619
620 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
621 (reduc->reduc_phi, loop_preheader_edge (loop)), init);
622 reduc->initial_value = arg;
623 return 1;
624}
625
626struct elv_data
627{
628 struct walk_stmt_info info;
629 edge entry;
630 int_tree_htab_type *decl_address;
631 gimple_stmt_iterator *gsi;
632 bool changed;
633 bool reset;
634};
635
636/* Eliminates references to local variables in *TP out of the single
637 entry single exit region starting at DTA->ENTRY.
638 DECL_ADDRESS contains addresses of the references that had their
639 address taken already. If the expression is changed, CHANGED is
640 set to true. Callback for walk_tree. */
641
642static tree
643eliminate_local_variables_1 (tree *tp, int *walk_subtrees, void *data)
644{
645 struct elv_data *const dta = (struct elv_data *) data;
646 tree t = *tp, var, addr, addr_type, type, obj;
647
648 if (DECL_P (t))
649 {
650 *walk_subtrees = 0;
651
652 if (!SSA_VAR_P (t) || DECL_EXTERNAL (t))
653 return NULL_TREE;
654
655 type = TREE_TYPE (t);
656 addr_type = build_pointer_type (type);
657 addr = take_address_of (t, addr_type, dta->entry, dta->decl_address,
658 dta->gsi);
659 if (dta->gsi == NULL && addr == NULL_TREE)
660 {
661 dta->reset = true;
662 return NULL_TREE;
663 }
664
665 *tp = build_simple_mem_ref (addr);
666
667 dta->changed = true;
668 return NULL_TREE;
669 }
670
671 if (TREE_CODE (t) == ADDR_EXPR)
672 {
673 /* ADDR_EXPR may appear in two contexts:
674 -- as a gimple operand, when the address taken is a function invariant
675 -- as gimple rhs, when the resulting address in not a function
676 invariant
677 We do not need to do anything special in the latter case (the base of
678 the memory reference whose address is taken may be replaced in the
679 DECL_P case). The former case is more complicated, as we need to
680 ensure that the new address is still a gimple operand. Thus, it
681 is not sufficient to replace just the base of the memory reference --
682 we need to move the whole computation of the address out of the
683 loop. */
684 if (!is_gimple_val (t))
685 return NULL_TREE;
686
687 *walk_subtrees = 0;
688 obj = TREE_OPERAND (t, 0);
689 var = get_base_address (obj);
690 if (!var || !SSA_VAR_P (var) || DECL_EXTERNAL (var))
691 return NULL_TREE;
692
693 addr_type = TREE_TYPE (t);
694 addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address,
695 dta->gsi);
696 if (dta->gsi == NULL && addr == NULL_TREE)
697 {
698 dta->reset = true;
699 return NULL_TREE;
700 }
701 *tp = addr;
702
703 dta->changed = true;
704 return NULL_TREE;
705 }
706
707 if (!EXPR_P (t))
708 *walk_subtrees = 0;
709
710 return NULL_TREE;
711}
712
713/* Moves the references to local variables in STMT at *GSI out of the single
714 entry single exit region starting at ENTRY. DECL_ADDRESS contains
715 addresses of the references that had their address taken
716 already. */
717
718static void
719eliminate_local_variables_stmt (edge entry, gimple_stmt_iterator *gsi,
720 int_tree_htab_type *decl_address)
721{
722 struct elv_data dta;
723 gimple stmt = gsi_stmt (*gsi);
724
725 memset (&dta.info, '\0', sizeof (dta.info));
726 dta.entry = entry;
727 dta.decl_address = decl_address;
728 dta.changed = false;
729 dta.reset = false;
730
731 if (gimple_debug_bind_p (stmt))
732 {
733 dta.gsi = NULL;
734 walk_tree (gimple_debug_bind_get_value_ptr (stmt),
735 eliminate_local_variables_1, &dta.info, NULL);
736 if (dta.reset)
737 {
738 gimple_debug_bind_reset_value (stmt);
739 dta.changed = true;
740 }
741 }
742 else if (gimple_clobber_p (stmt))
743 {
744 stmt = gimple_build_nop ();
745 gsi_replace (gsi, stmt, false);
746 dta.changed = true;
747 }
748 else
749 {
750 dta.gsi = gsi;
751 walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
752 }
753
754 if (dta.changed)
755 update_stmt (stmt);
756}
757
758/* Eliminates the references to local variables from the single entry
759 single exit region between the ENTRY and EXIT edges.
760
761 This includes:
762 1) Taking address of a local variable -- these are moved out of the
763 region (and temporary variable is created to hold the address if
764 necessary).
765
766 2) Dereferencing a local variable -- these are replaced with indirect
767 references. */
768
769static void
770eliminate_local_variables (edge entry, edge exit)
771{
772 basic_block bb;
773 auto_vec<basic_block, 3> body;
774 unsigned i;
775 gimple_stmt_iterator gsi;
776 bool has_debug_stmt = false;
777 int_tree_htab_type decl_address (10);
778 basic_block entry_bb = entry->src;
779 basic_block exit_bb = exit->dest;
780
781 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
782
783 FOR_EACH_VEC_ELT (body, i, bb)
784 if (bb != entry_bb && bb != exit_bb)
785 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
786 if (is_gimple_debug (gsi_stmt (gsi)))
787 {
788 if (gimple_debug_bind_p (gsi_stmt (gsi)))
789 has_debug_stmt = true;
790 }
791 else
792 eliminate_local_variables_stmt (entry, &gsi, &decl_address);
793
794 if (has_debug_stmt)
795 FOR_EACH_VEC_ELT (body, i, bb)
796 if (bb != entry_bb && bb != exit_bb)
797 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
798 if (gimple_debug_bind_p (gsi_stmt (gsi)))
799 eliminate_local_variables_stmt (entry, &gsi, &decl_address);
800}
801
802/* Returns true if expression EXPR is not defined between ENTRY and
803 EXIT, i.e. if all its operands are defined outside of the region. */
804
805static bool
806expr_invariant_in_region_p (edge entry, edge exit, tree expr)
807{
808 basic_block entry_bb = entry->src;
809 basic_block exit_bb = exit->dest;
810 basic_block def_bb;
811
812 if (is_gimple_min_invariant (expr))
813 return true;
814
815 if (TREE_CODE (expr) == SSA_NAME)
816 {
817 def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
818 if (def_bb
819 && dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)
820 && !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))
821 return false;
822
823 return true;
824 }
825
826 return false;
827}
828
829/* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
830 The copies are stored to NAME_COPIES, if NAME was already duplicated,
831 its duplicate stored in NAME_COPIES is returned.
832
833 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
834 duplicated, storing the copies in DECL_COPIES. */
835
836static tree
837separate_decls_in_region_name (tree name, name_to_copy_table_type *name_copies,
838 int_tree_htab_type *decl_copies,
839 bool copy_name_p)
840{
841 tree copy, var, var_copy;
842 unsigned idx, uid, nuid;
843 struct int_tree_map ielt;
844 struct name_to_copy_elt elt, *nelt;
845 name_to_copy_elt **slot;
846 int_tree_map *dslot;
847
848 if (TREE_CODE (name) != SSA_NAME)
849 return name;
850
851 idx = SSA_NAME_VERSION (name);
852 elt.version = idx;
853 slot = name_copies->find_slot_with_hash (&elt, idx,
854 copy_name_p ? INSERT : NO_INSERT);
855 if (slot && *slot)
856 return (*slot)->new_name;
857
858 if (copy_name_p)
859 {
860 copy = duplicate_ssa_name (name, NULL);
861 nelt = XNEW (struct name_to_copy_elt);
862 nelt->version = idx;
863 nelt->new_name = copy;
864 nelt->field = NULL_TREE;
865 *slot = nelt;
866 }
867 else
868 {
869 gcc_assert (!slot);
870 copy = name;
871 }
872
873 var = SSA_NAME_VAR (name);
874 if (!var)
875 return copy;
876
877 uid = DECL_UID (var);
878 ielt.uid = uid;
879 dslot = decl_copies->find_slot_with_hash (ielt, uid, INSERT);
880 if (!dslot->to)
881 {
882 var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
883 DECL_GIMPLE_REG_P (var_copy) = DECL_GIMPLE_REG_P (var);
884 dslot->uid = uid;
885 dslot->to = var_copy;
886
887 /* Ensure that when we meet this decl next time, we won't duplicate
888 it again. */
889 nuid = DECL_UID (var_copy);
890 ielt.uid = nuid;
891 dslot = decl_copies->find_slot_with_hash (ielt, nuid, INSERT);
892 gcc_assert (!dslot->to);
893 dslot->uid = nuid;
894 dslot->to = var_copy;
895 }
896 else
897 var_copy = dslot->to;
898
899 replace_ssa_name_symbol (copy, var_copy);
900 return copy;
901}
902
903/* Finds the ssa names used in STMT that are defined outside the
904 region between ENTRY and EXIT and replaces such ssa names with
905 their duplicates. The duplicates are stored to NAME_COPIES. Base
906 decls of all ssa names used in STMT (including those defined in
907 LOOP) are replaced with the new temporary variables; the
908 replacement decls are stored in DECL_COPIES. */
909
910static void
911separate_decls_in_region_stmt (edge entry, edge exit, gimple stmt,
912 name_to_copy_table_type *name_copies,
913 int_tree_htab_type *decl_copies)
914{
915 use_operand_p use;
916 def_operand_p def;
917 ssa_op_iter oi;
918 tree name, copy;
919 bool copy_name_p;
920
921 FOR_EACH_PHI_OR_STMT_DEF (def, stmt, oi, SSA_OP_DEF)
922 {
923 name = DEF_FROM_PTR (def);
924 gcc_assert (TREE_CODE (name) == SSA_NAME);
925 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
926 false);
927 gcc_assert (copy == name);
928 }
929
930 FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
931 {
932 name = USE_FROM_PTR (use);
933 if (TREE_CODE (name) != SSA_NAME)
934 continue;
935
936 copy_name_p = expr_invariant_in_region_p (entry, exit, name);
937 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
938 copy_name_p);
939 SET_USE (use, copy);
940 }
941}
942
943/* Finds the ssa names used in STMT that are defined outside the
944 region between ENTRY and EXIT and replaces such ssa names with
945 their duplicates. The duplicates are stored to NAME_COPIES. Base
946 decls of all ssa names used in STMT (including those defined in
947 LOOP) are replaced with the new temporary variables; the
948 replacement decls are stored in DECL_COPIES. */
949
950static bool
951separate_decls_in_region_debug (gimple stmt,
952 name_to_copy_table_type *name_copies,
953 int_tree_htab_type *decl_copies)
954{
955 use_operand_p use;
956 ssa_op_iter oi;
957 tree var, name;
958 struct int_tree_map ielt;
959 struct name_to_copy_elt elt;
960 name_to_copy_elt **slot;
961 int_tree_map *dslot;
962
963 if (gimple_debug_bind_p (stmt))
964 var = gimple_debug_bind_get_var (stmt);
965 else if (gimple_debug_source_bind_p (stmt))
966 var = gimple_debug_source_bind_get_var (stmt);
967 else
968 return true;
969 if (TREE_CODE (var) == DEBUG_EXPR_DECL || TREE_CODE (var) == LABEL_DECL)
970 return true;
971 gcc_assert (DECL_P (var) && SSA_VAR_P (var));
972 ielt.uid = DECL_UID (var);
973 dslot = decl_copies->find_slot_with_hash (ielt, ielt.uid, NO_INSERT);
974 if (!dslot)
975 return true;
976 if (gimple_debug_bind_p (stmt))
977 gimple_debug_bind_set_var (stmt, dslot->to);
978 else if (gimple_debug_source_bind_p (stmt))
979 gimple_debug_source_bind_set_var (stmt, dslot->to);
980
981 FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
982 {
983 name = USE_FROM_PTR (use);
984 if (TREE_CODE (name) != SSA_NAME)
985 continue;
986
987 elt.version = SSA_NAME_VERSION (name);
988 slot = name_copies->find_slot_with_hash (&elt, elt.version, NO_INSERT);
989 if (!slot)
990 {
991 gimple_debug_bind_reset_value (stmt);
992 update_stmt (stmt);
993 break;
994 }
995
996 SET_USE (use, (*slot)->new_name);
997 }
998
999 return false;
1000}
1001
1002/* Callback for htab_traverse. Adds a field corresponding to the reduction
1003 specified in SLOT. The type is passed in DATA. */
1004
1005int
1006add_field_for_reduction (reduction_info **slot, tree type)
1007{
1008
1009 struct reduction_info *const red = *slot;
1010 tree var = gimple_assign_lhs (red->reduc_stmt);
1011 tree field = build_decl (gimple_location (red->reduc_stmt), FIELD_DECL,
1012 SSA_NAME_IDENTIFIER (var), TREE_TYPE (var));
1013
1014 insert_field_into_struct (type, field);
1015
1016 red->field = field;
1017
1018 return 1;
1019}
1020
1021/* Callback for htab_traverse. Adds a field corresponding to a ssa name
1022 described in SLOT. The type is passed in DATA. */
1023
1024int
1025add_field_for_name (name_to_copy_elt **slot, tree type)
1026{
1027 struct name_to_copy_elt *const elt = *slot;
1028 tree name = ssa_name (elt->version);
1029 tree field = build_decl (UNKNOWN_LOCATION,
1030 FIELD_DECL, SSA_NAME_IDENTIFIER (name),
1031 TREE_TYPE (name));
1032
1033 insert_field_into_struct (type, field);
1034 elt->field = field;
1035
1036 return 1;
1037}
1038
1039/* Callback for htab_traverse. A local result is the intermediate result
1040 computed by a single
1041 thread, or the initial value in case no iteration was executed.
1042 This function creates a phi node reflecting these values.
1043 The phi's result will be stored in NEW_PHI field of the
1044 reduction's data structure. */
1045
1046int
1047create_phi_for_local_result (reduction_info **slot, struct loop *loop)
1048{
1049 struct reduction_info *const reduc = *slot;
1050 edge e;
1051 gphi *new_phi;
1052 basic_block store_bb;
1053 tree local_res;
1054 source_location locus;
1055
1056 /* STORE_BB is the block where the phi
1057 should be stored. It is the destination of the loop exit.
1058 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
1059 store_bb = FALLTHRU_EDGE (loop->latch)->dest;
1060
1061 /* STORE_BB has two predecessors. One coming from the loop
1062 (the reduction's result is computed at the loop),
1063 and another coming from a block preceding the loop,
1064 when no iterations
1065 are executed (the initial value should be taken). */
1066 if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (loop->latch))
1067 e = EDGE_PRED (store_bb, 1);
1068 else
1069 e = EDGE_PRED (store_bb, 0);
1070 local_res = copy_ssa_name (gimple_assign_lhs (reduc->reduc_stmt));
1071 locus = gimple_location (reduc->reduc_stmt);
1072 new_phi = create_phi_node (local_res, store_bb);
1073 add_phi_arg (new_phi, reduc->init, e, locus);
1074 add_phi_arg (new_phi, gimple_assign_lhs (reduc->reduc_stmt),
1075 FALLTHRU_EDGE (loop->latch), locus);
1076 reduc->new_phi = new_phi;
1077
1078 return 1;
1079}
1080
1081struct clsn_data
1082{
1083 tree store;
1084 tree load;
1085
1086 basic_block store_bb;
1087 basic_block load_bb;
1088};
1089
1090/* Callback for htab_traverse. Create an atomic instruction for the
1091 reduction described in SLOT.
1092 DATA annotates the place in memory the atomic operation relates to,
1093 and the basic block it needs to be generated in. */
1094
1095int
1096create_call_for_reduction_1 (reduction_info **slot, struct clsn_data *clsn_data)
1097{
1098 struct reduction_info *const reduc = *slot;
1099 gimple_stmt_iterator gsi;
1100 tree type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
1101 tree load_struct;
1102 basic_block bb;
1103 basic_block new_bb;
1104 edge e;
1105 tree t, addr, ref, x;
1106 tree tmp_load, name;
1107 gimple load;
1108
1109 load_struct = build_simple_mem_ref (clsn_data->load);
1110 t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
1111
1112 addr = build_addr (t, current_function_decl);
1113
1114 /* Create phi node. */
1115 bb = clsn_data->load_bb;
1116
f09a3553
JM
1117 gsi = gsi_last_bb (bb);
1118 e = split_block (bb, gsi_stmt (gsi));
dda118e3
JM
1119 new_bb = e->dest;
1120
1121 tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)));
1122 tmp_load = make_ssa_name (tmp_load);
1123 load = gimple_build_omp_atomic_load (tmp_load, addr);
1124 SSA_NAME_DEF_STMT (tmp_load) = load;
1125 gsi = gsi_start_bb (new_bb);
1126 gsi_insert_after (&gsi, load, GSI_NEW_STMT);
1127
1128 e = split_block (new_bb, load);
1129 new_bb = e->dest;
1130 gsi = gsi_start_bb (new_bb);
1131 ref = tmp_load;
1132 x = fold_build2 (reduc->reduction_code,
1133 TREE_TYPE (PHI_RESULT (reduc->new_phi)), ref,
1134 PHI_RESULT (reduc->new_phi));
1135
1136 name = force_gimple_operand_gsi (&gsi, x, true, NULL_TREE, true,
1137 GSI_CONTINUE_LINKING);
1138
1139 gsi_insert_after (&gsi, gimple_build_omp_atomic_store (name), GSI_NEW_STMT);
1140 return 1;
1141}
1142
1143/* Create the atomic operation at the join point of the threads.
1144 REDUCTION_LIST describes the reductions in the LOOP.
1145 LD_ST_DATA describes the shared data structure where
1146 shared data is stored in and loaded from. */
1147static void
1148create_call_for_reduction (struct loop *loop,
1149 reduction_info_table_type *reduction_list,
1150 struct clsn_data *ld_st_data)
1151{
1152 reduction_list->traverse <struct loop *, create_phi_for_local_result> (loop);
1153 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
1154 ld_st_data->load_bb = FALLTHRU_EDGE (loop->latch)->dest;
1155 reduction_list
1156 ->traverse <struct clsn_data *, create_call_for_reduction_1> (ld_st_data);
1157}
1158
1159/* Callback for htab_traverse. Loads the final reduction value at the
1160 join point of all threads, and inserts it in the right place. */
1161
1162int
1163create_loads_for_reductions (reduction_info **slot, struct clsn_data *clsn_data)
1164{
1165 struct reduction_info *const red = *slot;
1166 gimple stmt;
1167 gimple_stmt_iterator gsi;
1168 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
1169 tree load_struct;
1170 tree name;
1171 tree x;
1172
1173 gsi = gsi_after_labels (clsn_data->load_bb);
1174 load_struct = build_simple_mem_ref (clsn_data->load);
1175 load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
1176 NULL_TREE);
1177
1178 x = load_struct;
1179 name = PHI_RESULT (red->keep_res);
1180 stmt = gimple_build_assign (name, x);
1181
1182 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1183
1184 for (gsi = gsi_start_phis (gimple_bb (red->keep_res));
1185 !gsi_end_p (gsi); gsi_next (&gsi))
1186 if (gsi_stmt (gsi) == red->keep_res)
1187 {
1188 remove_phi_node (&gsi, false);
1189 return 1;
1190 }
1191 gcc_unreachable ();
1192}
1193
1194/* Load the reduction result that was stored in LD_ST_DATA.
1195 REDUCTION_LIST describes the list of reductions that the
1196 loads should be generated for. */
1197static void
1198create_final_loads_for_reduction (reduction_info_table_type *reduction_list,
1199 struct clsn_data *ld_st_data)
1200{
1201 gimple_stmt_iterator gsi;
1202 tree t;
1203 gimple stmt;
1204
1205 gsi = gsi_after_labels (ld_st_data->load_bb);
1206 t = build_fold_addr_expr (ld_st_data->store);
1207 stmt = gimple_build_assign (ld_st_data->load, t);
1208
1209 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1210
1211 reduction_list
1212 ->traverse <struct clsn_data *, create_loads_for_reductions> (ld_st_data);
1213
1214}
1215
1216/* Callback for htab_traverse. Store the neutral value for the
1217 particular reduction's operation, e.g. 0 for PLUS_EXPR,
1218 1 for MULT_EXPR, etc. into the reduction field.
1219 The reduction is specified in SLOT. The store information is
1220 passed in DATA. */
1221
1222int
1223create_stores_for_reduction (reduction_info **slot, struct clsn_data *clsn_data)
1224{
1225 struct reduction_info *const red = *slot;
1226 tree t;
1227 gimple stmt;
1228 gimple_stmt_iterator gsi;
1229 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
1230
1231 gsi = gsi_last_bb (clsn_data->store_bb);
1232 t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE);
1233 stmt = gimple_build_assign (t, red->initial_value);
1234 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1235
1236 return 1;
1237}
1238
1239/* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
1240 store to a field of STORE in STORE_BB for the ssa name and its duplicate
1241 specified in SLOT. */
1242
1243int
1244create_loads_and_stores_for_name (name_to_copy_elt **slot,
1245 struct clsn_data *clsn_data)
1246{
1247 struct name_to_copy_elt *const elt = *slot;
1248 tree t;
1249 gimple stmt;
1250 gimple_stmt_iterator gsi;
1251 tree type = TREE_TYPE (elt->new_name);
1252 tree load_struct;
1253
1254 gsi = gsi_last_bb (clsn_data->store_bb);
1255 t = build3 (COMPONENT_REF, type, clsn_data->store, elt->field, NULL_TREE);
1256 stmt = gimple_build_assign (t, ssa_name (elt->version));
1257 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1258
1259 gsi = gsi_last_bb (clsn_data->load_bb);
1260 load_struct = build_simple_mem_ref (clsn_data->load);
1261 t = build3 (COMPONENT_REF, type, load_struct, elt->field, NULL_TREE);
1262 stmt = gimple_build_assign (elt->new_name, t);
1263 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
1264
1265 return 1;
1266}
1267
1268/* Moves all the variables used in LOOP and defined outside of it (including
1269 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
1270 name) to a structure created for this purpose. The code
1271
1272 while (1)
1273 {
1274 use (a);
1275 use (b);
1276 }
1277
1278 is transformed this way:
1279
1280 bb0:
1281 old.a = a;
1282 old.b = b;
1283
1284 bb1:
1285 a' = new->a;
1286 b' = new->b;
1287 while (1)
1288 {
1289 use (a');
1290 use (b');
1291 }
1292
1293 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
1294 pointer `new' is intentionally not initialized (the loop will be split to a
1295 separate function later, and `new' will be initialized from its arguments).
1296 LD_ST_DATA holds information about the shared data structure used to pass
1297 information among the threads. It is initialized here, and
1298 gen_parallel_loop will pass it to create_call_for_reduction that
1299 needs this information. REDUCTION_LIST describes the reductions
1300 in LOOP. */
1301
1302static void
1303separate_decls_in_region (edge entry, edge exit,
1304 reduction_info_table_type *reduction_list,
1305 tree *arg_struct, tree *new_arg_struct,
1306 struct clsn_data *ld_st_data)
1307
1308{
1309 basic_block bb1 = split_edge (entry);
1310 basic_block bb0 = single_pred (bb1);
1311 name_to_copy_table_type name_copies (10);
1312 int_tree_htab_type decl_copies (10);
1313 unsigned i;
1314 tree type, type_name, nvar;
1315 gimple_stmt_iterator gsi;
1316 struct clsn_data clsn_data;
1317 auto_vec<basic_block, 3> body;
1318 basic_block bb;
1319 basic_block entry_bb = bb1;
1320 basic_block exit_bb = exit->dest;
1321 bool has_debug_stmt = false;
1322
1323 entry = single_succ_edge (entry_bb);
1324 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
1325
1326 FOR_EACH_VEC_ELT (body, i, bb)
1327 {
1328 if (bb != entry_bb && bb != exit_bb)
1329 {
1330 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1331 separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
1332 &name_copies, &decl_copies);
1333
1334 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
1335 {
1336 gimple stmt = gsi_stmt (gsi);
1337
1338 if (is_gimple_debug (stmt))
1339 has_debug_stmt = true;
1340 else
1341 separate_decls_in_region_stmt (entry, exit, stmt,
1342 &name_copies, &decl_copies);
1343 }
1344 }
1345 }
1346
1347 /* Now process debug bind stmts. We must not create decls while
1348 processing debug stmts, so we defer their processing so as to
1349 make sure we will have debug info for as many variables as
1350 possible (all of those that were dealt with in the loop above),
1351 and discard those for which we know there's nothing we can
1352 do. */
1353 if (has_debug_stmt)
1354 FOR_EACH_VEC_ELT (body, i, bb)
1355 if (bb != entry_bb && bb != exit_bb)
1356 {
1357 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi);)
1358 {
1359 gimple stmt = gsi_stmt (gsi);
1360
1361 if (is_gimple_debug (stmt))
1362 {
1363 if (separate_decls_in_region_debug (stmt, &name_copies,
1364 &decl_copies))
1365 {
1366 gsi_remove (&gsi, true);
1367 continue;
1368 }
1369 }
1370
1371 gsi_next (&gsi);
1372 }
1373 }
1374
1375 if (name_copies.elements () == 0 && reduction_list->elements () == 0)
1376 {
1377 /* It may happen that there is nothing to copy (if there are only
1378 loop carried and external variables in the loop). */
1379 *arg_struct = NULL;
1380 *new_arg_struct = NULL;
1381 }
1382 else
1383 {
1384 /* Create the type for the structure to store the ssa names to. */
1385 type = lang_hooks.types.make_type (RECORD_TYPE);
1386 type_name = build_decl (UNKNOWN_LOCATION,
1387 TYPE_DECL, create_tmp_var_name (".paral_data"),
1388 type);
1389 TYPE_NAME (type) = type_name;
1390
1391 name_copies.traverse <tree, add_field_for_name> (type);
1392 if (reduction_list && reduction_list->elements () > 0)
1393 {
1394 /* Create the fields for reductions. */
1395 reduction_list->traverse <tree, add_field_for_reduction> (type);
1396 }
1397 layout_type (type);
1398
1399 /* Create the loads and stores. */
1400 *arg_struct = create_tmp_var (type, ".paral_data_store");
1401 nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load");
1402 *new_arg_struct = make_ssa_name (nvar);
1403
1404 ld_st_data->store = *arg_struct;
1405 ld_st_data->load = *new_arg_struct;
1406 ld_st_data->store_bb = bb0;
1407 ld_st_data->load_bb = bb1;
1408
1409 name_copies
1410 .traverse <struct clsn_data *, create_loads_and_stores_for_name>
1411 (ld_st_data);
1412
1413 /* Load the calculation from memory (after the join of the threads). */
1414
1415 if (reduction_list && reduction_list->elements () > 0)
1416 {
1417 reduction_list
1418 ->traverse <struct clsn_data *, create_stores_for_reduction>
1419 (ld_st_data);
1420 clsn_data.load = make_ssa_name (nvar);
1421 clsn_data.load_bb = exit->dest;
1422 clsn_data.store = ld_st_data->store;
1423 create_final_loads_for_reduction (reduction_list, &clsn_data);
1424 }
1425 }
1426}
1427
38c0c85b 1428/* Returns true if FN was created to run in parallel. */
dda118e3
JM
1429
1430bool
38c0c85b 1431parallelized_function_p (tree fndecl)
dda118e3 1432{
38c0c85b
JM
1433 cgraph_node *node = cgraph_node::get (fndecl);
1434 gcc_assert (node != NULL);
1435 return node->parallelized_function;
dda118e3
JM
1436}
1437
1438/* Creates and returns an empty function that will receive the body of
1439 a parallelized loop. */
1440
1441static tree
1442create_loop_fn (location_t loc)
1443{
1444 char buf[100];
1445 char *tname;
1446 tree decl, type, name, t;
1447 struct function *act_cfun = cfun;
1448 static unsigned loopfn_num;
1449
1450 loc = LOCATION_LOCUS (loc);
1451 snprintf (buf, 100, "%s.$loopfn", current_function_name ());
1452 ASM_FORMAT_PRIVATE_NAME (tname, buf, loopfn_num++);
1453 clean_symbol_name (tname);
1454 name = get_identifier (tname);
1455 type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
1456
1457 decl = build_decl (loc, FUNCTION_DECL, name, type);
dda118e3
JM
1458 TREE_STATIC (decl) = 1;
1459 TREE_USED (decl) = 1;
1460 DECL_ARTIFICIAL (decl) = 1;
1461 DECL_IGNORED_P (decl) = 0;
1462 TREE_PUBLIC (decl) = 0;
1463 DECL_UNINLINABLE (decl) = 1;
1464 DECL_EXTERNAL (decl) = 0;
1465 DECL_CONTEXT (decl) = NULL_TREE;
1466 DECL_INITIAL (decl) = make_node (BLOCK);
1467
1468 t = build_decl (loc, RESULT_DECL, NULL_TREE, void_type_node);
1469 DECL_ARTIFICIAL (t) = 1;
1470 DECL_IGNORED_P (t) = 1;
1471 DECL_RESULT (decl) = t;
1472
1473 t = build_decl (loc, PARM_DECL, get_identifier (".paral_data_param"),
1474 ptr_type_node);
1475 DECL_ARTIFICIAL (t) = 1;
1476 DECL_ARG_TYPE (t) = ptr_type_node;
1477 DECL_CONTEXT (t) = decl;
1478 TREE_USED (t) = 1;
1479 DECL_ARGUMENTS (decl) = t;
1480
1481 allocate_struct_function (decl, false);
1482
1483 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
1484 it. */
1485 set_cfun (act_cfun);
1486
1487 return decl;
1488}
1489
1490/* Moves the exit condition of LOOP to the beginning of its header, and
1491 duplicates the part of the last iteration that gets disabled to the
1492 exit of the loop. NIT is the number of iterations of the loop
1493 (used to initialize the variables in the duplicated part).
1494
1495 TODO: the common case is that latch of the loop is empty and immediately
1496 follows the loop exit. In this case, it would be better not to copy the
1497 body of the loop, but only move the entry of the loop directly before the
1498 exit check and increase the number of iterations of the loop by one.
1499 This may need some additional preconditioning in case NIT = ~0.
1500 REDUCTION_LIST describes the reductions in LOOP. */
1501
1502static void
1503transform_to_exit_first_loop (struct loop *loop,
1504 reduction_info_table_type *reduction_list,
1505 tree nit)
1506{
1507 basic_block *bbs, *nbbs, ex_bb, orig_header;
1508 unsigned n;
1509 bool ok;
1510 edge exit = single_dom_exit (loop), hpred;
1511 tree control, control_name, res, t;
1512 gphi *phi, *nphi;
1513 gassign *stmt;
1514 gcond *cond_stmt, *cond_nit;
1515 tree nit_1;
1516
1517 split_block_after_labels (loop->header);
1518 orig_header = single_succ (loop->header);
1519 hpred = single_succ_edge (loop->header);
1520
1521 cond_stmt = as_a <gcond *> (last_stmt (exit->src));
1522 control = gimple_cond_lhs (cond_stmt);
1523 gcc_assert (gimple_cond_rhs (cond_stmt) == nit);
1524
1525 /* Make sure that we have phi nodes on exit for all loop header phis
1526 (create_parallel_loop requires that). */
1527 for (gphi_iterator gsi = gsi_start_phis (loop->header);
1528 !gsi_end_p (gsi);
1529 gsi_next (&gsi))
1530 {
1531 phi = gsi.phi ();
1532 res = PHI_RESULT (phi);
1533 t = copy_ssa_name (res, phi);
1534 SET_PHI_RESULT (phi, t);
1535 nphi = create_phi_node (res, orig_header);
1536 add_phi_arg (nphi, t, hpred, UNKNOWN_LOCATION);
1537
1538 if (res == control)
1539 {
1540 gimple_cond_set_lhs (cond_stmt, t);
1541 update_stmt (cond_stmt);
1542 control = t;
1543 }
1544 }
1545
1546 bbs = get_loop_body_in_dom_order (loop);
1547
1548 for (n = 0; bbs[n] != exit->src; n++)
1549 continue;
1550 nbbs = XNEWVEC (basic_block, n);
1551 ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
1552 bbs + 1, n, nbbs);
1553 gcc_assert (ok);
1554 free (bbs);
1555 ex_bb = nbbs[0];
1556 free (nbbs);
1557
1558 /* Other than reductions, the only gimple reg that should be copied
1559 out of the loop is the control variable. */
1560 exit = single_dom_exit (loop);
1561 control_name = NULL_TREE;
1562 for (gphi_iterator gsi = gsi_start_phis (ex_bb);
1563 !gsi_end_p (gsi); )
1564 {
1565 phi = gsi.phi ();
1566 res = PHI_RESULT (phi);
1567 if (virtual_operand_p (res))
1568 {
1569 gsi_next (&gsi);
1570 continue;
1571 }
1572
1573 /* Check if it is a part of reduction. If it is,
1574 keep the phi at the reduction's keep_res field. The
1575 PHI_RESULT of this phi is the resulting value of the reduction
1576 variable when exiting the loop. */
1577
1578 if (reduction_list->elements () > 0)
1579 {
1580 struct reduction_info *red;
1581
1582 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
1583 red = reduction_phi (reduction_list, SSA_NAME_DEF_STMT (val));
1584 if (red)
1585 {
1586 red->keep_res = phi;
1587 gsi_next (&gsi);
1588 continue;
1589 }
1590 }
1591 gcc_assert (control_name == NULL_TREE
1592 && SSA_NAME_VAR (res) == SSA_NAME_VAR (control));
1593 control_name = res;
1594 remove_phi_node (&gsi, false);
1595 }
1596 gcc_assert (control_name != NULL_TREE);
1597
1598 /* Initialize the control variable to number of iterations
1599 according to the rhs of the exit condition. */
1600 gimple_stmt_iterator gsi = gsi_after_labels (ex_bb);
1601 cond_nit = as_a <gcond *> (last_stmt (exit->src));
1602 nit_1 = gimple_cond_rhs (cond_nit);
1603 nit_1 = force_gimple_operand_gsi (&gsi,
1604 fold_convert (TREE_TYPE (control_name), nit_1),
1605 false, NULL_TREE, false, GSI_SAME_STMT);
1606 stmt = gimple_build_assign (control_name, nit_1);
1607 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
1608}
1609
1610/* Create the parallel constructs for LOOP as described in gen_parallel_loop.
1611 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
1612 NEW_DATA is the variable that should be initialized from the argument
1613 of LOOP_FN. N_THREADS is the requested number of threads. Returns the
1614 basic block containing GIMPLE_OMP_PARALLEL tree. */
1615
1616static basic_block
1617create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
1618 tree new_data, unsigned n_threads, location_t loc)
1619{
1620 gimple_stmt_iterator gsi;
1621 basic_block bb, paral_bb, for_bb, ex_bb;
1622 tree t, param;
1623 gomp_parallel *omp_par_stmt;
1624 gimple omp_return_stmt1, omp_return_stmt2;
1625 gimple phi;
1626 gcond *cond_stmt;
1627 gomp_for *for_stmt;
1628 gomp_continue *omp_cont_stmt;
1629 tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
1630 edge exit, nexit, guard, end, e;
1631
1632 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
1633 bb = loop_preheader_edge (loop)->src;
1634 paral_bb = single_pred (bb);
1635 gsi = gsi_last_bb (paral_bb);
1636
1637 t = build_omp_clause (loc, OMP_CLAUSE_NUM_THREADS);
1638 OMP_CLAUSE_NUM_THREADS_EXPR (t)
1639 = build_int_cst (integer_type_node, n_threads);
1640 omp_par_stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
1641 gimple_set_location (omp_par_stmt, loc);
1642
1643 gsi_insert_after (&gsi, omp_par_stmt, GSI_NEW_STMT);
1644
1645 /* Initialize NEW_DATA. */
1646 if (data)
1647 {
1648 gassign *assign_stmt;
1649
1650 gsi = gsi_after_labels (bb);
1651
1652 param = make_ssa_name (DECL_ARGUMENTS (loop_fn));
1653 assign_stmt = gimple_build_assign (param, build_fold_addr_expr (data));
1654 gsi_insert_before (&gsi, assign_stmt, GSI_SAME_STMT);
1655
1656 assign_stmt = gimple_build_assign (new_data,
1657 fold_convert (TREE_TYPE (new_data), param));
1658 gsi_insert_before (&gsi, assign_stmt, GSI_SAME_STMT);
1659 }
1660
1661 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
1662 bb = split_loop_exit_edge (single_dom_exit (loop));
1663 gsi = gsi_last_bb (bb);
1664 omp_return_stmt1 = gimple_build_omp_return (false);
1665 gimple_set_location (omp_return_stmt1, loc);
1666 gsi_insert_after (&gsi, omp_return_stmt1, GSI_NEW_STMT);
1667
1668 /* Extract data for GIMPLE_OMP_FOR. */
1669 gcc_assert (loop->header == single_dom_exit (loop)->src);
1670 cond_stmt = as_a <gcond *> (last_stmt (loop->header));
1671
1672 cvar = gimple_cond_lhs (cond_stmt);
1673 cvar_base = SSA_NAME_VAR (cvar);
1674 phi = SSA_NAME_DEF_STMT (cvar);
1675 cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
1676 initvar = copy_ssa_name (cvar);
1677 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
1678 initvar);
1679 cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
1680
1681 gsi = gsi_last_nondebug_bb (loop->latch);
1682 gcc_assert (gsi_stmt (gsi) == SSA_NAME_DEF_STMT (cvar_next));
1683 gsi_remove (&gsi, true);
1684
1685 /* Prepare cfg. */
1686 for_bb = split_edge (loop_preheader_edge (loop));
1687 ex_bb = split_loop_exit_edge (single_dom_exit (loop));
1688 extract_true_false_edges_from_block (loop->header, &nexit, &exit);
1689 gcc_assert (exit == single_dom_exit (loop));
1690
1691 guard = make_edge (for_bb, ex_bb, 0);
1692 single_succ_edge (loop->latch)->flags = 0;
1693 end = make_edge (loop->latch, ex_bb, EDGE_FALLTHRU);
1694 for (gphi_iterator gpi = gsi_start_phis (ex_bb);
1695 !gsi_end_p (gpi); gsi_next (&gpi))
1696 {
1697 source_location locus;
1698 tree def;
1699 gphi *phi = gpi.phi ();
1700 gphi *stmt;
1701
1702 stmt = as_a <gphi *> (
1703 SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi, exit)));
1704
1705 def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop));
1706 locus = gimple_phi_arg_location_from_edge (stmt,
1707 loop_preheader_edge (loop));
1708 add_phi_arg (phi, def, guard, locus);
1709
1710 def = PHI_ARG_DEF_FROM_EDGE (stmt, loop_latch_edge (loop));
1711 locus = gimple_phi_arg_location_from_edge (stmt, loop_latch_edge (loop));
1712 add_phi_arg (phi, def, end, locus);
1713 }
1714 e = redirect_edge_and_branch (exit, nexit->dest);
1715 PENDING_STMT (e) = NULL;
1716
1717 /* Emit GIMPLE_OMP_FOR. */
1718 gimple_cond_set_lhs (cond_stmt, cvar_base);
1719 type = TREE_TYPE (cvar);
1720 t = build_omp_clause (loc, OMP_CLAUSE_SCHEDULE);
1721 OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
1722
1723 for_stmt = gimple_build_omp_for (NULL, GF_OMP_FOR_KIND_FOR, t, 1, NULL);
1724 gimple_set_location (for_stmt, loc);
1725 gimple_omp_for_set_index (for_stmt, 0, initvar);
1726 gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
1727 gimple_omp_for_set_final (for_stmt, 0, gimple_cond_rhs (cond_stmt));
1728 gimple_omp_for_set_cond (for_stmt, 0, gimple_cond_code (cond_stmt));
1729 gimple_omp_for_set_incr (for_stmt, 0, build2 (PLUS_EXPR, type,
1730 cvar_base,
1731 build_int_cst (type, 1)));
1732
1733 gsi = gsi_last_bb (for_bb);
1734 gsi_insert_after (&gsi, for_stmt, GSI_NEW_STMT);
1735 SSA_NAME_DEF_STMT (initvar) = for_stmt;
1736
1737 /* Emit GIMPLE_OMP_CONTINUE. */
1738 gsi = gsi_last_bb (loop->latch);
1739 omp_cont_stmt = gimple_build_omp_continue (cvar_next, cvar);
1740 gimple_set_location (omp_cont_stmt, loc);
1741 gsi_insert_after (&gsi, omp_cont_stmt, GSI_NEW_STMT);
1742 SSA_NAME_DEF_STMT (cvar_next) = omp_cont_stmt;
1743
1744 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
1745 gsi = gsi_last_bb (ex_bb);
1746 omp_return_stmt2 = gimple_build_omp_return (true);
1747 gimple_set_location (omp_return_stmt2, loc);
1748 gsi_insert_after (&gsi, omp_return_stmt2, GSI_NEW_STMT);
1749
1750 /* After the above dom info is hosed. Re-compute it. */
1751 free_dominance_info (CDI_DOMINATORS);
1752 calculate_dominance_info (CDI_DOMINATORS);
1753
1754 return paral_bb;
1755}
1756
1757/* Generates code to execute the iterations of LOOP in N_THREADS
1758 threads in parallel.
1759
1760 NITER describes number of iterations of LOOP.
1761 REDUCTION_LIST describes the reductions existent in the LOOP. */
1762
1763static void
1764gen_parallel_loop (struct loop *loop,
1765 reduction_info_table_type *reduction_list,
1766 unsigned n_threads, struct tree_niter_desc *niter)
1767{
1768 tree many_iterations_cond, type, nit;
1769 tree arg_struct, new_arg_struct;
1770 gimple_seq stmts;
1771 edge entry, exit;
1772 struct clsn_data clsn_data;
1773 unsigned prob;
1774 location_t loc;
1775 gimple cond_stmt;
1776 unsigned int m_p_thread=2;
1777
1778 /* From
1779
1780 ---------------------------------------------------------------------
1781 loop
1782 {
1783 IV = phi (INIT, IV + STEP)
1784 BODY1;
1785 if (COND)
1786 break;
1787 BODY2;
1788 }
1789 ---------------------------------------------------------------------
1790
1791 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
1792 we generate the following code:
1793
1794 ---------------------------------------------------------------------
1795
1796 if (MAY_BE_ZERO
1797 || NITER < MIN_PER_THREAD * N_THREADS)
1798 goto original;
1799
1800 BODY1;
1801 store all local loop-invariant variables used in body of the loop to DATA.
1802 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
1803 load the variables from DATA.
1804 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
1805 BODY2;
1806 BODY1;
1807 GIMPLE_OMP_CONTINUE;
1808 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
1809 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
1810 goto end;
1811
1812 original:
1813 loop
1814 {
1815 IV = phi (INIT, IV + STEP)
1816 BODY1;
1817 if (COND)
1818 break;
1819 BODY2;
1820 }
1821
1822 end:
1823
1824 */
1825
1826 /* Create two versions of the loop -- in the old one, we know that the
1827 number of iterations is large enough, and we will transform it into the
1828 loop that will be split to loop_fn, the new one will be used for the
1829 remaining iterations. */
1830
1831 /* We should compute a better number-of-iterations value for outer loops.
1832 That is, if we have
1833
1834 for (i = 0; i < n; ++i)
1835 for (j = 0; j < m; ++j)
1836 ...
1837
1838 we should compute nit = n * m, not nit = n.
1839 Also may_be_zero handling would need to be adjusted. */
1840
1841 type = TREE_TYPE (niter->niter);
1842 nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true,
1843 NULL_TREE);
1844 if (stmts)
1845 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1846
1847 if (loop->inner)
1848 m_p_thread=2;
1849 else
1850 m_p_thread=MIN_PER_THREAD;
1851
1852 many_iterations_cond =
1853 fold_build2 (GE_EXPR, boolean_type_node,
1854 nit, build_int_cst (type, m_p_thread * n_threads));
1855
1856 many_iterations_cond
1857 = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
1858 invert_truthvalue (unshare_expr (niter->may_be_zero)),
1859 many_iterations_cond);
1860 many_iterations_cond
1861 = force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
1862 if (stmts)
1863 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1864 if (!is_gimple_condexpr (many_iterations_cond))
1865 {
1866 many_iterations_cond
1867 = force_gimple_operand (many_iterations_cond, &stmts,
1868 true, NULL_TREE);
1869 if (stmts)
1870 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
1871 }
1872
1873 initialize_original_copy_tables ();
1874
1875 /* We assume that the loop usually iterates a lot. */
1876 prob = 4 * REG_BR_PROB_BASE / 5;
1877 loop_version (loop, many_iterations_cond, NULL,
1878 prob, prob, REG_BR_PROB_BASE - prob, true);
1879 update_ssa (TODO_update_ssa);
1880 free_original_copy_tables ();
1881
1882 /* Base all the induction variables in LOOP on a single control one. */
1883 canonicalize_loop_ivs (loop, &nit, true);
1884
1885 /* Ensure that the exit condition is the first statement in the loop. */
1886 transform_to_exit_first_loop (loop, reduction_list, nit);
1887
1888 /* Generate initializations for reductions. */
1889 if (reduction_list->elements () > 0)
1890 reduction_list->traverse <struct loop *, initialize_reductions> (loop);
1891
1892 /* Eliminate the references to local variables from the loop. */
1893 gcc_assert (single_exit (loop));
1894 entry = loop_preheader_edge (loop);
1895 exit = single_dom_exit (loop);
1896
1897 eliminate_local_variables (entry, exit);
1898 /* In the old loop, move all variables non-local to the loop to a structure
1899 and back, and create separate decls for the variables used in loop. */
1900 separate_decls_in_region (entry, exit, reduction_list, &arg_struct,
1901 &new_arg_struct, &clsn_data);
1902
1903 /* Create the parallel constructs. */
1904 loc = UNKNOWN_LOCATION;
1905 cond_stmt = last_stmt (loop->header);
1906 if (cond_stmt)
1907 loc = gimple_location (cond_stmt);
1908 create_parallel_loop (loop, create_loop_fn (loc), arg_struct,
1909 new_arg_struct, n_threads, loc);
1910 if (reduction_list->elements () > 0)
1911 create_call_for_reduction (loop, reduction_list, &clsn_data);
1912
1913 scev_reset ();
1914
1915 /* Cancel the loop (it is simpler to do it here rather than to teach the
1916 expander to do it). */
1917 cancel_loop_tree (loop);
1918
1919 /* Free loop bound estimations that could contain references to
1920 removed statements. */
1921 FOR_EACH_LOOP (loop, 0)
1922 free_numbers_of_iterations_estimates_loop (loop);
1923}
1924
1925/* Returns true when LOOP contains vector phi nodes. */
1926
1927static bool
1928loop_has_vector_phi_nodes (struct loop *loop ATTRIBUTE_UNUSED)
1929{
1930 unsigned i;
1931 basic_block *bbs = get_loop_body_in_dom_order (loop);
1932 gphi_iterator gsi;
1933 bool res = true;
1934
1935 for (i = 0; i < loop->num_nodes; i++)
1936 for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
1937 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi.phi ()))) == VECTOR_TYPE)
1938 goto end;
1939
1940 res = false;
1941 end:
1942 free (bbs);
1943 return res;
1944}
1945
1946/* Create a reduction_info struct, initialize it with REDUC_STMT
1947 and PHI, insert it to the REDUCTION_LIST. */
1948
1949static void
1950build_new_reduction (reduction_info_table_type *reduction_list,
1951 gimple reduc_stmt, gphi *phi)
1952{
1953 reduction_info **slot;
1954 struct reduction_info *new_reduction;
1955
1956 gcc_assert (reduc_stmt);
1957
1958 if (dump_file && (dump_flags & TDF_DETAILS))
1959 {
1960 fprintf (dump_file,
1961 "Detected reduction. reduction stmt is: \n");
1962 print_gimple_stmt (dump_file, reduc_stmt, 0, 0);
1963 fprintf (dump_file, "\n");
1964 }
1965
1966 new_reduction = XCNEW (struct reduction_info);
1967
1968 new_reduction->reduc_stmt = reduc_stmt;
1969 new_reduction->reduc_phi = phi;
1970 new_reduction->reduc_version = SSA_NAME_VERSION (gimple_phi_result (phi));
1971 new_reduction->reduction_code = gimple_assign_rhs_code (reduc_stmt);
1972 slot = reduction_list->find_slot (new_reduction, INSERT);
1973 *slot = new_reduction;
1974}
1975
1976/* Callback for htab_traverse. Sets gimple_uid of reduc_phi stmts. */
1977
1978int
1979set_reduc_phi_uids (reduction_info **slot, void *data ATTRIBUTE_UNUSED)
1980{
1981 struct reduction_info *const red = *slot;
1982 gimple_set_uid (red->reduc_phi, red->reduc_version);
1983 return 1;
1984}
1985
1986/* Detect all reductions in the LOOP, insert them into REDUCTION_LIST. */
1987
1988static void
1989gather_scalar_reductions (loop_p loop, reduction_info_table_type *reduction_list)
1990{
1991 gphi_iterator gsi;
1992 loop_vec_info simple_loop_info;
1993
1994 simple_loop_info = vect_analyze_loop_form (loop);
1995
1996 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
1997 {
1998 gphi *phi = gsi.phi ();
1999 affine_iv iv;
2000 tree res = PHI_RESULT (phi);
2001 bool double_reduc;
2002
2003 if (virtual_operand_p (res))
2004 continue;
2005
2006 if (!simple_iv (loop, loop, res, &iv, true)
2007 && simple_loop_info)
2008 {
2009 gimple reduc_stmt = vect_force_simple_reduction (simple_loop_info,
2010 phi, true,
2011 &double_reduc);
2012 if (reduc_stmt && !double_reduc)
2013 build_new_reduction (reduction_list, reduc_stmt, phi);
2014 }
2015 }
2016 destroy_loop_vec_info (simple_loop_info, true);
2017
2018 /* As gimple_uid is used by the vectorizer in between vect_analyze_loop_form
2019 and destroy_loop_vec_info, we can set gimple_uid of reduc_phi stmts
2020 only now. */
2021 reduction_list->traverse <void *, set_reduc_phi_uids> (NULL);
2022}
2023
2024/* Try to initialize NITER for code generation part. */
2025
2026static bool
2027try_get_loop_niter (loop_p loop, struct tree_niter_desc *niter)
2028{
2029 edge exit = single_dom_exit (loop);
2030
2031 gcc_assert (exit);
2032
2033 /* We need to know # of iterations, and there should be no uses of values
2034 defined inside loop outside of it, unless the values are invariants of
2035 the loop. */
2036 if (!number_of_iterations_exit (loop, exit, niter, false))
2037 {
2038 if (dump_file && (dump_flags & TDF_DETAILS))
2039 fprintf (dump_file, " FAILED: number of iterations not known\n");
2040 return false;
2041 }
2042
2043 return true;
2044}
2045
2046/* Try to initialize REDUCTION_LIST for code generation part.
2047 REDUCTION_LIST describes the reductions. */
2048
2049static bool
2050try_create_reduction_list (loop_p loop,
2051 reduction_info_table_type *reduction_list)
2052{
2053 edge exit = single_dom_exit (loop);
2054 gphi_iterator gsi;
2055
2056 gcc_assert (exit);
2057
2058 gather_scalar_reductions (loop, reduction_list);
2059
2060
2061 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
2062 {
2063 gphi *phi = gsi.phi ();
2064 struct reduction_info *red;
2065 imm_use_iterator imm_iter;
2066 use_operand_p use_p;
2067 gimple reduc_phi;
2068 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
2069
2070 if (!virtual_operand_p (val))
2071 {
2072 if (dump_file && (dump_flags & TDF_DETAILS))
2073 {
2074 fprintf (dump_file, "phi is ");
2075 print_gimple_stmt (dump_file, phi, 0, 0);
2076 fprintf (dump_file, "arg of phi to exit: value ");
2077 print_generic_expr (dump_file, val, 0);
2078 fprintf (dump_file, " used outside loop\n");
2079 fprintf (dump_file,
2080 " checking if it a part of reduction pattern: \n");
2081 }
2082 if (reduction_list->elements () == 0)
2083 {
2084 if (dump_file && (dump_flags & TDF_DETAILS))
2085 fprintf (dump_file,
2086 " FAILED: it is not a part of reduction.\n");
2087 return false;
2088 }
2089 reduc_phi = NULL;
2090 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
2091 {
2092 if (!gimple_debug_bind_p (USE_STMT (use_p))
2093 && flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
2094 {
2095 reduc_phi = USE_STMT (use_p);
2096 break;
2097 }
2098 }
2099 red = reduction_phi (reduction_list, reduc_phi);
2100 if (red == NULL)
2101 {
2102 if (dump_file && (dump_flags & TDF_DETAILS))
2103 fprintf (dump_file,
2104 " FAILED: it is not a part of reduction.\n");
2105 return false;
2106 }
2107 if (dump_file && (dump_flags & TDF_DETAILS))
2108 {
2109 fprintf (dump_file, "reduction phi is ");
2110 print_gimple_stmt (dump_file, red->reduc_phi, 0, 0);
2111 fprintf (dump_file, "reduction stmt is ");
2112 print_gimple_stmt (dump_file, red->reduc_stmt, 0, 0);
2113 }
2114 }
2115 }
2116
2117 /* The iterations of the loop may communicate only through bivs whose
2118 iteration space can be distributed efficiently. */
2119 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
2120 {
2121 gphi *phi = gsi.phi ();
2122 tree def = PHI_RESULT (phi);
2123 affine_iv iv;
2124
2125 if (!virtual_operand_p (def) && !simple_iv (loop, loop, def, &iv, true))
2126 {
2127 struct reduction_info *red;
2128
2129 red = reduction_phi (reduction_list, phi);
2130 if (red == NULL)
2131 {
2132 if (dump_file && (dump_flags & TDF_DETAILS))
2133 fprintf (dump_file,
2134 " FAILED: scalar dependency between iterations\n");
2135 return false;
2136 }
2137 }
2138 }
2139
2140
2141 return true;
2142}
2143
2144/* Detect parallel loops and generate parallel code using libgomp
2145 primitives. Returns true if some loop was parallelized, false
2146 otherwise. */
2147
38c0c85b 2148static bool
dda118e3
JM
2149parallelize_loops (void)
2150{
2151 unsigned n_threads = flag_tree_parallelize_loops;
2152 bool changed = false;
2153 struct loop *loop;
2154 struct tree_niter_desc niter_desc;
2155 struct obstack parloop_obstack;
2156 HOST_WIDE_INT estimated;
2157 source_location loop_loc;
2158
2159 /* Do not parallelize loops in the functions created by parallelization. */
2160 if (parallelized_function_p (cfun->decl))
2161 return false;
2162 if (cfun->has_nonlocal_label)
2163 return false;
2164
2165 gcc_obstack_init (&parloop_obstack);
2166 reduction_info_table_type reduction_list (10);
2167 init_stmt_vec_info_vec ();
2168
2169 FOR_EACH_LOOP (loop, 0)
2170 {
2171 reduction_list.empty ();
2172 if (dump_file && (dump_flags & TDF_DETAILS))
2173 {
2174 fprintf (dump_file, "Trying loop %d as candidate\n",loop->num);
2175 if (loop->inner)
2176 fprintf (dump_file, "loop %d is not innermost\n",loop->num);
2177 else
2178 fprintf (dump_file, "loop %d is innermost\n",loop->num);
2179 }
2180
2181 /* If we use autopar in graphite pass, we use its marked dependency
2182 checking results. */
2183 if (flag_loop_parallelize_all && !loop->can_be_parallel)
2184 {
2185 if (dump_file && (dump_flags & TDF_DETAILS))
2186 fprintf (dump_file, "loop is not parallel according to graphite\n");
2187 continue;
2188 }
2189
2190 if (!single_dom_exit (loop))
2191 {
2192
2193 if (dump_file && (dump_flags & TDF_DETAILS))
2194 fprintf (dump_file, "loop is !single_dom_exit\n");
2195
2196 continue;
2197 }
2198
2199 if (/* And of course, the loop must be parallelizable. */
2200 !can_duplicate_loop_p (loop)
2201 || loop_has_blocks_with_irreducible_flag (loop)
2202 || (loop_preheader_edge (loop)->src->flags & BB_IRREDUCIBLE_LOOP)
2203 /* FIXME: the check for vector phi nodes could be removed. */
2204 || loop_has_vector_phi_nodes (loop))
2205 continue;
2206
2207 estimated = estimated_stmt_executions_int (loop);
2208 if (estimated == -1)
2209 estimated = max_stmt_executions_int (loop);
2210 /* FIXME: Bypass this check as graphite doesn't update the
2211 count and frequency correctly now. */
2212 if (!flag_loop_parallelize_all
2213 && ((estimated != -1
2214 && estimated <= (HOST_WIDE_INT) n_threads * MIN_PER_THREAD)
2215 /* Do not bother with loops in cold areas. */
2216 || optimize_loop_nest_for_size_p (loop)))
2217 continue;
2218
2219 if (!try_get_loop_niter (loop, &niter_desc))
2220 continue;
2221
2222 if (!try_create_reduction_list (loop, &reduction_list))
2223 continue;
2224
2225 if (!flag_loop_parallelize_all
2226 && !loop_parallel_p (loop, &parloop_obstack))
2227 continue;
2228
2229 changed = true;
2230 if (dump_file && (dump_flags & TDF_DETAILS))
2231 {
2232 if (loop->inner)
2233 fprintf (dump_file, "parallelizing outer loop %d\n",loop->header->index);
2234 else
2235 fprintf (dump_file, "parallelizing inner loop %d\n",loop->header->index);
2236 loop_loc = find_loop_location (loop);
2237 if (loop_loc != UNKNOWN_LOCATION)
2238 fprintf (dump_file, "\nloop at %s:%d: ",
2239 LOCATION_FILE (loop_loc), LOCATION_LINE (loop_loc));
2240 }
2241 gen_parallel_loop (loop, &reduction_list,
2242 n_threads, &niter_desc);
2243 }
2244
2245 free_stmt_vec_info_vec ();
2246 obstack_free (&parloop_obstack, NULL);
2247
2248 /* Parallelization will cause new function calls to be inserted through
2249 which local variables will escape. Reset the points-to solution
2250 for ESCAPED. */
2251 if (changed)
2252 pt_solution_reset (&cfun->gimple_df->escaped);
2253
2254 return changed;
2255}
2256
2257/* Parallelization. */
2258
2259namespace {
2260
2261const pass_data pass_data_parallelize_loops =
2262{
2263 GIMPLE_PASS, /* type */
2264 "parloops", /* name */
2265 OPTGROUP_LOOP, /* optinfo_flags */
2266 TV_TREE_PARALLELIZE_LOOPS, /* tv_id */
2267 ( PROP_cfg | PROP_ssa ), /* properties_required */
2268 0, /* properties_provided */
2269 0, /* properties_destroyed */
2270 0, /* todo_flags_start */
2271 0, /* todo_flags_finish */
2272};
2273
2274class pass_parallelize_loops : public gimple_opt_pass
2275{
2276public:
2277 pass_parallelize_loops (gcc::context *ctxt)
2278 : gimple_opt_pass (pass_data_parallelize_loops, ctxt)
2279 {}
2280
2281 /* opt_pass methods: */
2282 virtual bool gate (function *) { return flag_tree_parallelize_loops > 1; }
2283 virtual unsigned int execute (function *);
2284
2285}; // class pass_parallelize_loops
2286
2287unsigned
2288pass_parallelize_loops::execute (function *fun)
2289{
2290 if (number_of_loops (fun) <= 1)
2291 return 0;
2292
2293 if (parallelize_loops ())
2294 {
2295 fun->curr_properties &= ~(PROP_gimple_eomp);
2296 return TODO_update_ssa;
2297 }
2298
2299 return 0;
2300}
2301
2302} // anon namespace
2303
2304gimple_opt_pass *
2305make_pass_parallelize_loops (gcc::context *ctxt)
2306{
2307 return new pass_parallelize_loops (ctxt);
2308}