|
0
|
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>.
|
|
|
5
|
|
|
6 This file is part of GCC.
|
|
|
7
|
|
|
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.
|
|
|
12
|
|
|
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.
|
|
|
17
|
|
|
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/>. */
|
|
|
21
|
|
|
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"
|
|
|
38
|
|
|
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.
|
|
|
45
|
|
|
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).
|
|
|
56
|
|
|
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 */
|
|
|
63
|
|
|
64 /*
|
|
|
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.
|
|
|
68
|
|
|
69
|
|
|
70 parloop
|
|
|
71 {
|
|
|
72 int sum=1;
|
|
|
73
|
|
|
74 for (i = 0; i < N; i++)
|
|
|
75 {
|
|
|
76 x[i] = i + 3;
|
|
|
77 sum+=x[i];
|
|
|
78 }
|
|
|
79 }
|
|
|
80
|
|
|
81 gimple-like code:
|
|
|
82 header_bb:
|
|
|
83
|
|
|
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;
|
|
|
92
|
|
|
93
|
|
|
94 exit_bb:
|
|
|
95
|
|
|
96 # sum_21 = PHI <sum_11(4)>
|
|
|
97 printf (&"%d"[0], sum_21);
|
|
|
98
|
|
|
99
|
|
|
100 after reduction transformation (only relevant parts):
|
|
|
101
|
|
|
102 parloop
|
|
|
103 {
|
|
|
104
|
|
|
105 ....
|
|
|
106
|
|
|
107
|
|
|
108 # Storing the initial value given by the user. #
|
|
|
109
|
|
|
110 .paral_data_store.32.sum.27 = 1;
|
|
|
111
|
|
|
112 #pragma omp parallel num_threads(4)
|
|
|
113
|
|
|
114 #pragma omp for schedule(static)
|
|
|
115
|
|
|
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. #
|
|
|
119
|
|
|
120 # sum.27_29 = PHI <sum.27_11, 0>
|
|
|
121
|
|
|
122 sum.27_11 = D.1827_8 + sum.27_29;
|
|
|
123
|
|
|
124 GIMPLE_OMP_CONTINUE
|
|
|
125
|
|
|
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
|
|
|
129
|
|
|
130 # Creating the atomic operation is done at
|
|
|
131 create_call_for_reduction_1() #
|
|
|
132
|
|
|
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);
|
|
|
137
|
|
|
138 GIMPLE_OMP_RETURN
|
|
|
139
|
|
|
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. #
|
|
|
144
|
|
|
145
|
|
|
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;
|
|
|
149
|
|
|
150 exit bb:
|
|
|
151 # sum_21 = PHI <sum_43, sum_26>
|
|
|
152 printf (&"%d"[0], sum_21);
|
|
|
153
|
|
|
154 ...
|
|
|
155
|
|
|
156 }
|
|
|
157
|
|
|
158 */
|
|
|
159
|
|
|
160 /* Minimal number of iterations of a loop that should be executed in each
|
|
|
161 thread. */
|
|
|
162 #define MIN_PER_THREAD 100
|
|
|
163
|
|
|
164 /* Element of the hashtable, representing a
|
|
|
165 reduction in the current loop. */
|
|
|
166 struct reduction_info
|
|
|
167 {
|
|
|
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. */
|
|
|
180 };
|
|
|
181
|
|
|
182 /* Equality and hash functions for hashtab code. */
|
|
|
183
|
|
|
184 static int
|
|
|
185 reduction_info_eq (const void *aa, const void *bb)
|
|
|
186 {
|
|
|
187 const struct reduction_info *a = (const struct reduction_info *) aa;
|
|
|
188 const struct reduction_info *b = (const struct reduction_info *) bb;
|
|
|
189
|
|
|
190 return (a->reduc_phi == b->reduc_phi);
|
|
|
191 }
|
|
|
192
|
|
|
193 static hashval_t
|
|
|
194 reduction_info_hash (const void *aa)
|
|
|
195 {
|
|
|
196 const struct reduction_info *a = (const struct reduction_info *) aa;
|
|
|
197
|
|
|
198 return htab_hash_pointer (a->reduc_phi);
|
|
|
199 }
|
|
|
200
|
|
|
201 static struct reduction_info *
|
|
|
202 reduction_phi (htab_t reduction_list, gimple phi)
|
|
|
203 {
|
|
|
204 struct reduction_info tmpred, *red;
|
|
|
205
|
|
|
206 if (htab_elements (reduction_list) == 0)
|
|
|
207 return NULL;
|
|
|
208
|
|
|
209 tmpred.reduc_phi = phi;
|
|
|
210 red = (struct reduction_info *) htab_find (reduction_list, &tmpred);
|
|
|
211
|
|
|
212 return red;
|
|
|
213 }
|
|
|
214
|
|
|
215 /* Element of hashtable of names to copy. */
|
|
|
216
|
|
|
217 struct name_to_copy_elt
|
|
|
218 {
|
|
|
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. */
|
|
|
223 };
|
|
|
224
|
|
|
225 /* Equality and hash functions for hashtab code. */
|
|
|
226
|
|
|
227 static int
|
|
|
228 name_to_copy_elt_eq (const void *aa, const void *bb)
|
|
|
229 {
|
|
|
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;
|
|
|
232
|
|
|
233 return a->version == b->version;
|
|
|
234 }
|
|
|
235
|
|
|
236 static hashval_t
|
|
|
237 name_to_copy_elt_hash (const void *aa)
|
|
|
238 {
|
|
|
239 const struct name_to_copy_elt *a = (const struct name_to_copy_elt *) aa;
|
|
|
240
|
|
|
241 return (hashval_t) a->version;
|
|
|
242 }
|
|
|
243
|
|
|
244 /* Returns true if the iterations of LOOP are independent on each other (that
|
|
|
245 is, if we can execute them in parallel), and if LOOP satisfies other
|
|
|
246 conditions that we need to be able to parallelize it. Description of number
|
|
|
247 of iterations is stored to NITER. Reduction analysis is done, if
|
|
|
248 reductions are found, they are inserted to the REDUCTION_LIST. */
|
|
|
249
|
|
|
250 static bool
|
|
|
251 loop_parallel_p (struct loop *loop, htab_t reduction_list,
|
|
|
252 struct tree_niter_desc *niter)
|
|
|
253 {
|
|
|
254 edge exit = single_dom_exit (loop);
|
|
|
255 VEC (ddr_p, heap) * dependence_relations;
|
|
|
256 VEC (data_reference_p, heap) *datarefs;
|
|
|
257 lambda_trans_matrix trans;
|
|
|
258 bool ret = false;
|
|
|
259 gimple_stmt_iterator gsi;
|
|
|
260 loop_vec_info simple_loop_info;
|
|
|
261
|
|
|
262 /* Only consider innermost loops with just one exit. The innermost-loop
|
|
|
263 restriction is not necessary, but it makes things simpler. */
|
|
|
264 if (loop->inner || !exit)
|
|
|
265 return false;
|
|
|
266
|
|
|
267 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
268 fprintf (dump_file, "\nConsidering loop %d\n", loop->num);
|
|
|
269
|
|
|
270 /* We need to know # of iterations, and there should be no uses of values
|
|
|
271 defined inside loop outside of it, unless the values are invariants of
|
|
|
272 the loop. */
|
|
|
273 if (!number_of_iterations_exit (loop, exit, niter, false))
|
|
|
274 {
|
|
|
275 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
276 fprintf (dump_file, " FAILED: number of iterations not known\n");
|
|
|
277 return false;
|
|
|
278 }
|
|
|
279
|
|
|
280 vect_dump = NULL;
|
|
|
281 simple_loop_info = vect_analyze_loop_form (loop);
|
|
|
282
|
|
|
283 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
284 {
|
|
|
285 gimple phi = gsi_stmt (gsi);
|
|
|
286 gimple reduc_stmt = NULL;
|
|
|
287
|
|
|
288 /* ??? TODO: Change this into a generic function that
|
|
|
289 recognizes reductions. */
|
|
|
290 if (!is_gimple_reg (PHI_RESULT (phi)))
|
|
|
291 continue;
|
|
|
292 if (simple_loop_info)
|
|
|
293 reduc_stmt = vect_is_simple_reduction (simple_loop_info, phi);
|
|
|
294
|
|
|
295 /* Create a reduction_info struct, initialize it and insert it to
|
|
|
296 the reduction list. */
|
|
|
297
|
|
|
298 if (reduc_stmt)
|
|
|
299 {
|
|
|
300 PTR *slot;
|
|
|
301 struct reduction_info *new_reduction;
|
|
|
302
|
|
|
303 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
304 {
|
|
|
305 fprintf (dump_file,
|
|
|
306 "Detected reduction. reduction stmt is: \n");
|
|
|
307 print_gimple_stmt (dump_file, reduc_stmt, 0, 0);
|
|
|
308 fprintf (dump_file, "\n");
|
|
|
309 }
|
|
|
310
|
|
|
311 new_reduction = XCNEW (struct reduction_info);
|
|
|
312
|
|
|
313 new_reduction->reduc_stmt = reduc_stmt;
|
|
|
314 new_reduction->reduc_phi = phi;
|
|
|
315 new_reduction->reduction_code = gimple_assign_rhs_code (reduc_stmt);
|
|
|
316 slot = htab_find_slot (reduction_list, new_reduction, INSERT);
|
|
|
317 *slot = new_reduction;
|
|
|
318 }
|
|
|
319 }
|
|
|
320
|
|
|
321 /* Get rid of the information created by the vectorizer functions. */
|
|
|
322 destroy_loop_vec_info (simple_loop_info, true);
|
|
|
323
|
|
|
324 for (gsi = gsi_start_phis (exit->dest); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
325 {
|
|
|
326 gimple phi = gsi_stmt (gsi);
|
|
|
327 struct reduction_info *red;
|
|
|
328 imm_use_iterator imm_iter;
|
|
|
329 use_operand_p use_p;
|
|
|
330 gimple reduc_phi;
|
|
|
331 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
|
|
|
332
|
|
|
333 if (is_gimple_reg (val))
|
|
|
334 {
|
|
|
335 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
336 {
|
|
|
337 fprintf (dump_file, "phi is ");
|
|
|
338 print_gimple_stmt (dump_file, phi, 0, 0);
|
|
|
339 fprintf (dump_file, "arg of phi to exit: value ");
|
|
|
340 print_generic_expr (dump_file, val, 0);
|
|
|
341 fprintf (dump_file, " used outside loop\n");
|
|
|
342 fprintf (dump_file,
|
|
|
343 " checking if it a part of reduction pattern: \n");
|
|
|
344 }
|
|
|
345 if (htab_elements (reduction_list) == 0)
|
|
|
346 {
|
|
|
347 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
348 fprintf (dump_file,
|
|
|
349 " FAILED: it is not a part of reduction.\n");
|
|
|
350 return false;
|
|
|
351 }
|
|
|
352 reduc_phi = NULL;
|
|
|
353 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, val)
|
|
|
354 {
|
|
|
355 if (flow_bb_inside_loop_p (loop, gimple_bb (USE_STMT (use_p))))
|
|
|
356 {
|
|
|
357 reduc_phi = USE_STMT (use_p);
|
|
|
358 break;
|
|
|
359 }
|
|
|
360 }
|
|
|
361 red = reduction_phi (reduction_list, reduc_phi);
|
|
|
362 if (red == NULL)
|
|
|
363 {
|
|
|
364 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
365 fprintf (dump_file,
|
|
|
366 " FAILED: it is not a part of reduction.\n");
|
|
|
367 return false;
|
|
|
368 }
|
|
|
369 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
370 {
|
|
|
371 fprintf (dump_file, "reduction phi is ");
|
|
|
372 print_gimple_stmt (dump_file, red->reduc_phi, 0, 0);
|
|
|
373 fprintf (dump_file, "reduction stmt is ");
|
|
|
374 print_gimple_stmt (dump_file, red->reduc_stmt, 0, 0);
|
|
|
375 }
|
|
|
376
|
|
|
377 }
|
|
|
378 }
|
|
|
379
|
|
|
380 /* The iterations of the loop may communicate only through bivs whose
|
|
|
381 iteration space can be distributed efficiently. */
|
|
|
382 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
383 {
|
|
|
384 gimple phi = gsi_stmt (gsi);
|
|
|
385 tree def = PHI_RESULT (phi);
|
|
|
386 affine_iv iv;
|
|
|
387
|
|
|
388 if (is_gimple_reg (def) && !simple_iv (loop, loop, def, &iv, true))
|
|
|
389 {
|
|
|
390 struct reduction_info *red;
|
|
|
391
|
|
|
392 red = reduction_phi (reduction_list, phi);
|
|
|
393 if (red == NULL)
|
|
|
394 {
|
|
|
395 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
396 fprintf (dump_file,
|
|
|
397 " FAILED: scalar dependency between iterations\n");
|
|
|
398 return false;
|
|
|
399 }
|
|
|
400 }
|
|
|
401 }
|
|
|
402
|
|
|
403 /* We need to version the loop to verify assumptions in runtime. */
|
|
|
404 if (!can_duplicate_loop_p (loop))
|
|
|
405 {
|
|
|
406 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
407 fprintf (dump_file, " FAILED: cannot be duplicated\n");
|
|
|
408 return false;
|
|
|
409 }
|
|
|
410
|
|
|
411 /* Check for problems with dependences. If the loop can be reversed,
|
|
|
412 the iterations are independent. */
|
|
|
413 datarefs = VEC_alloc (data_reference_p, heap, 10);
|
|
|
414 dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
|
|
|
415 compute_data_dependences_for_loop (loop, true, &datarefs,
|
|
|
416 &dependence_relations);
|
|
|
417 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
418 dump_data_dependence_relations (dump_file, dependence_relations);
|
|
|
419
|
|
|
420 trans = lambda_trans_matrix_new (1, 1);
|
|
|
421 LTM_MATRIX (trans)[0][0] = -1;
|
|
|
422
|
|
|
423 if (lambda_transform_legal_p (trans, 1, dependence_relations))
|
|
|
424 {
|
|
|
425 ret = true;
|
|
|
426 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
427 fprintf (dump_file, " SUCCESS: may be parallelized\n");
|
|
|
428 }
|
|
|
429 else if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
430 fprintf (dump_file,
|
|
|
431 " FAILED: data dependencies exist across iterations\n");
|
|
|
432
|
|
|
433 free_dependence_relations (dependence_relations);
|
|
|
434 free_data_refs (datarefs);
|
|
|
435
|
|
|
436 return ret;
|
|
|
437 }
|
|
|
438
|
|
|
439 /* Return true when LOOP contains basic blocks marked with the
|
|
|
440 BB_IRREDUCIBLE_LOOP flag. */
|
|
|
441
|
|
|
442 static inline bool
|
|
|
443 loop_has_blocks_with_irreducible_flag (struct loop *loop)
|
|
|
444 {
|
|
|
445 unsigned i;
|
|
|
446 basic_block *bbs = get_loop_body_in_dom_order (loop);
|
|
|
447 bool res = true;
|
|
|
448
|
|
|
449 for (i = 0; i < loop->num_nodes; i++)
|
|
|
450 if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
|
|
|
451 goto end;
|
|
|
452
|
|
|
453 res = false;
|
|
|
454 end:
|
|
|
455 free (bbs);
|
|
|
456 return res;
|
|
|
457 }
|
|
|
458
|
|
|
459 /* Assigns the address of OBJ in TYPE to an ssa name, and returns this name.
|
|
|
460 The assignment statement is placed on edge ENTRY. DECL_ADDRESS maps decls
|
|
|
461 to their addresses that can be reused. The address of OBJ is known to
|
|
|
462 be invariant in the whole function. */
|
|
|
463
|
|
|
464 static tree
|
|
|
465 take_address_of (tree obj, tree type, edge entry, htab_t decl_address)
|
|
|
466 {
|
|
|
467 int uid;
|
|
|
468 void **dslot;
|
|
|
469 struct int_tree_map ielt, *nielt;
|
|
|
470 tree *var_p, name, bvar, addr;
|
|
|
471 gimple stmt;
|
|
|
472 gimple_seq stmts;
|
|
|
473
|
|
|
474 /* Since the address of OBJ is invariant, the trees may be shared.
|
|
|
475 Avoid rewriting unrelated parts of the code. */
|
|
|
476 obj = unshare_expr (obj);
|
|
|
477 for (var_p = &obj;
|
|
|
478 handled_component_p (*var_p);
|
|
|
479 var_p = &TREE_OPERAND (*var_p, 0))
|
|
|
480 continue;
|
|
|
481 uid = DECL_UID (*var_p);
|
|
|
482
|
|
|
483 ielt.uid = uid;
|
|
|
484 dslot = htab_find_slot_with_hash (decl_address, &ielt, uid, INSERT);
|
|
|
485 if (!*dslot)
|
|
|
486 {
|
|
|
487 addr = build_addr (*var_p, current_function_decl);
|
|
|
488 bvar = create_tmp_var (TREE_TYPE (addr), get_name (*var_p));
|
|
|
489 add_referenced_var (bvar);
|
|
|
490 stmt = gimple_build_assign (bvar, addr);
|
|
|
491 name = make_ssa_name (bvar, stmt);
|
|
|
492 gimple_assign_set_lhs (stmt, name);
|
|
|
493 gsi_insert_on_edge_immediate (entry, stmt);
|
|
|
494
|
|
|
495 nielt = XNEW (struct int_tree_map);
|
|
|
496 nielt->uid = uid;
|
|
|
497 nielt->to = name;
|
|
|
498 *dslot = nielt;
|
|
|
499 }
|
|
|
500 else
|
|
|
501 name = ((struct int_tree_map *) *dslot)->to;
|
|
|
502
|
|
|
503 if (var_p != &obj)
|
|
|
504 {
|
|
|
505 *var_p = build1 (INDIRECT_REF, TREE_TYPE (*var_p), name);
|
|
|
506 name = force_gimple_operand (build_addr (obj, current_function_decl),
|
|
|
507 &stmts, true, NULL_TREE);
|
|
|
508 if (!gimple_seq_empty_p (stmts))
|
|
|
509 gsi_insert_seq_on_edge_immediate (entry, stmts);
|
|
|
510 }
|
|
|
511
|
|
|
512 if (TREE_TYPE (name) != type)
|
|
|
513 {
|
|
|
514 name = force_gimple_operand (fold_convert (type, name), &stmts, true,
|
|
|
515 NULL_TREE);
|
|
|
516 if (!gimple_seq_empty_p (stmts))
|
|
|
517 gsi_insert_seq_on_edge_immediate (entry, stmts);
|
|
|
518 }
|
|
|
519
|
|
|
520 return name;
|
|
|
521 }
|
|
|
522
|
|
|
523 /* Callback for htab_traverse. Create the initialization statement
|
|
|
524 for reduction described in SLOT, and place it at the preheader of
|
|
|
525 the loop described in DATA. */
|
|
|
526
|
|
|
527 static int
|
|
|
528 initialize_reductions (void **slot, void *data)
|
|
|
529 {
|
|
|
530 tree init, c;
|
|
|
531 tree bvar, type, arg;
|
|
|
532 edge e;
|
|
|
533
|
|
|
534 struct reduction_info *const reduc = (struct reduction_info *) *slot;
|
|
|
535 struct loop *loop = (struct loop *) data;
|
|
|
536
|
|
|
537 /* Create initialization in preheader:
|
|
|
538 reduction_variable = initialization value of reduction. */
|
|
|
539
|
|
|
540 /* In the phi node at the header, replace the argument coming
|
|
|
541 from the preheader with the reduction initialization value. */
|
|
|
542
|
|
|
543 /* Create a new variable to initialize the reduction. */
|
|
|
544 type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
|
|
|
545 bvar = create_tmp_var (type, "reduction");
|
|
|
546 add_referenced_var (bvar);
|
|
|
547
|
|
|
548 c = build_omp_clause (OMP_CLAUSE_REDUCTION);
|
|
|
549 OMP_CLAUSE_REDUCTION_CODE (c) = reduc->reduction_code;
|
|
|
550 OMP_CLAUSE_DECL (c) = SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt));
|
|
|
551
|
|
|
552 init = omp_reduction_init (c, TREE_TYPE (bvar));
|
|
|
553 reduc->init = init;
|
|
|
554
|
|
|
555 /* Replace the argument representing the initialization value
|
|
|
556 with the initialization value for the reduction (neutral
|
|
|
557 element for the particular operation, e.g. 0 for PLUS_EXPR,
|
|
|
558 1 for MULT_EXPR, etc).
|
|
|
559 Keep the old value in a new variable "reduction_initial",
|
|
|
560 that will be taken in consideration after the parallel
|
|
|
561 computing is done. */
|
|
|
562
|
|
|
563 e = loop_preheader_edge (loop);
|
|
|
564 arg = PHI_ARG_DEF_FROM_EDGE (reduc->reduc_phi, e);
|
|
|
565 /* Create new variable to hold the initial value. */
|
|
|
566
|
|
|
567 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE
|
|
|
568 (reduc->reduc_phi, loop_preheader_edge (loop)), init);
|
|
|
569 reduc->initial_value = arg;
|
|
|
570 return 1;
|
|
|
571 }
|
|
|
572
|
|
|
573 struct elv_data
|
|
|
574 {
|
|
|
575 struct walk_stmt_info info;
|
|
|
576 edge entry;
|
|
|
577 htab_t decl_address;
|
|
|
578 bool changed;
|
|
|
579 };
|
|
|
580
|
|
|
581 /* Eliminates references to local variables in *TP out of the single
|
|
|
582 entry single exit region starting at DTA->ENTRY.
|
|
|
583 DECL_ADDRESS contains addresses of the references that had their
|
|
|
584 address taken already. If the expression is changed, CHANGED is
|
|
|
585 set to true. Callback for walk_tree. */
|
|
|
586
|
|
|
587 static tree
|
|
|
588 eliminate_local_variables_1 (tree *tp, int *walk_subtrees, void *data)
|
|
|
589 {
|
|
|
590 struct elv_data *const dta = (struct elv_data *) data;
|
|
|
591 tree t = *tp, var, addr, addr_type, type, obj;
|
|
|
592
|
|
|
593 if (DECL_P (t))
|
|
|
594 {
|
|
|
595 *walk_subtrees = 0;
|
|
|
596
|
|
|
597 if (!SSA_VAR_P (t) || DECL_EXTERNAL (t))
|
|
|
598 return NULL_TREE;
|
|
|
599
|
|
|
600 type = TREE_TYPE (t);
|
|
|
601 addr_type = build_pointer_type (type);
|
|
|
602 addr = take_address_of (t, addr_type, dta->entry, dta->decl_address);
|
|
|
603 *tp = build1 (INDIRECT_REF, TREE_TYPE (*tp), addr);
|
|
|
604
|
|
|
605 dta->changed = true;
|
|
|
606 return NULL_TREE;
|
|
|
607 }
|
|
|
608
|
|
|
609 if (TREE_CODE (t) == ADDR_EXPR)
|
|
|
610 {
|
|
|
611 /* ADDR_EXPR may appear in two contexts:
|
|
|
612 -- as a gimple operand, when the address taken is a function invariant
|
|
|
613 -- as gimple rhs, when the resulting address in not a function
|
|
|
614 invariant
|
|
|
615 We do not need to do anything special in the latter case (the base of
|
|
|
616 the memory reference whose address is taken may be replaced in the
|
|
|
617 DECL_P case). The former case is more complicated, as we need to
|
|
|
618 ensure that the new address is still a gimple operand. Thus, it
|
|
|
619 is not sufficient to replace just the base of the memory reference --
|
|
|
620 we need to move the whole computation of the address out of the
|
|
|
621 loop. */
|
|
|
622 if (!is_gimple_val (t))
|
|
|
623 return NULL_TREE;
|
|
|
624
|
|
|
625 *walk_subtrees = 0;
|
|
|
626 obj = TREE_OPERAND (t, 0);
|
|
|
627 var = get_base_address (obj);
|
|
|
628 if (!var || !SSA_VAR_P (var) || DECL_EXTERNAL (var))
|
|
|
629 return NULL_TREE;
|
|
|
630
|
|
|
631 addr_type = TREE_TYPE (t);
|
|
|
632 addr = take_address_of (obj, addr_type, dta->entry, dta->decl_address);
|
|
|
633 *tp = addr;
|
|
|
634
|
|
|
635 dta->changed = true;
|
|
|
636 return NULL_TREE;
|
|
|
637 }
|
|
|
638
|
|
|
639 if (!EXPR_P (t))
|
|
|
640 *walk_subtrees = 0;
|
|
|
641
|
|
|
642 return NULL_TREE;
|
|
|
643 }
|
|
|
644
|
|
|
645 /* Moves the references to local variables in STMT out of the single
|
|
|
646 entry single exit region starting at ENTRY. DECL_ADDRESS contains
|
|
|
647 addresses of the references that had their address taken
|
|
|
648 already. */
|
|
|
649
|
|
|
650 static void
|
|
|
651 eliminate_local_variables_stmt (edge entry, gimple stmt,
|
|
|
652 htab_t decl_address)
|
|
|
653 {
|
|
|
654 struct elv_data dta;
|
|
|
655
|
|
|
656 memset (&dta.info, '\0', sizeof (dta.info));
|
|
|
657 dta.entry = entry;
|
|
|
658 dta.decl_address = decl_address;
|
|
|
659 dta.changed = false;
|
|
|
660
|
|
|
661 walk_gimple_op (stmt, eliminate_local_variables_1, &dta.info);
|
|
|
662
|
|
|
663 if (dta.changed)
|
|
|
664 update_stmt (stmt);
|
|
|
665 }
|
|
|
666
|
|
|
667 /* Eliminates the references to local variables from the single entry
|
|
|
668 single exit region between the ENTRY and EXIT edges.
|
|
|
669
|
|
|
670 This includes:
|
|
|
671 1) Taking address of a local variable -- these are moved out of the
|
|
|
672 region (and temporary variable is created to hold the address if
|
|
|
673 necessary).
|
|
|
674
|
|
|
675 2) Dereferencing a local variable -- these are replaced with indirect
|
|
|
676 references. */
|
|
|
677
|
|
|
678 static void
|
|
|
679 eliminate_local_variables (edge entry, edge exit)
|
|
|
680 {
|
|
|
681 basic_block bb;
|
|
|
682 VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
|
|
|
683 unsigned i;
|
|
|
684 gimple_stmt_iterator gsi;
|
|
|
685 htab_t decl_address = htab_create (10, int_tree_map_hash, int_tree_map_eq,
|
|
|
686 free);
|
|
|
687 basic_block entry_bb = entry->src;
|
|
|
688 basic_block exit_bb = exit->dest;
|
|
|
689
|
|
|
690 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
|
|
|
691
|
|
|
692 for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
|
|
|
693 if (bb != entry_bb && bb != exit_bb)
|
|
|
694 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
695 eliminate_local_variables_stmt (entry, gsi_stmt (gsi),
|
|
|
696 decl_address);
|
|
|
697
|
|
|
698 htab_delete (decl_address);
|
|
|
699 VEC_free (basic_block, heap, body);
|
|
|
700 }
|
|
|
701
|
|
|
702 /* Returns true if expression EXPR is not defined between ENTRY and
|
|
|
703 EXIT, i.e. if all its operands are defined outside of the region. */
|
|
|
704
|
|
|
705 static bool
|
|
|
706 expr_invariant_in_region_p (edge entry, edge exit, tree expr)
|
|
|
707 {
|
|
|
708 basic_block entry_bb = entry->src;
|
|
|
709 basic_block exit_bb = exit->dest;
|
|
|
710 basic_block def_bb;
|
|
|
711
|
|
|
712 if (is_gimple_min_invariant (expr))
|
|
|
713 return true;
|
|
|
714
|
|
|
715 if (TREE_CODE (expr) == SSA_NAME)
|
|
|
716 {
|
|
|
717 def_bb = gimple_bb (SSA_NAME_DEF_STMT (expr));
|
|
|
718 if (def_bb
|
|
|
719 && dominated_by_p (CDI_DOMINATORS, def_bb, entry_bb)
|
|
|
720 && !dominated_by_p (CDI_DOMINATORS, def_bb, exit_bb))
|
|
|
721 return false;
|
|
|
722
|
|
|
723 return true;
|
|
|
724 }
|
|
|
725
|
|
|
726 return false;
|
|
|
727 }
|
|
|
728
|
|
|
729 /* If COPY_NAME_P is true, creates and returns a duplicate of NAME.
|
|
|
730 The copies are stored to NAME_COPIES, if NAME was already duplicated,
|
|
|
731 its duplicate stored in NAME_COPIES is returned.
|
|
|
732
|
|
|
733 Regardless of COPY_NAME_P, the decl used as a base of the ssa name is also
|
|
|
734 duplicated, storing the copies in DECL_COPIES. */
|
|
|
735
|
|
|
736 static tree
|
|
|
737 separate_decls_in_region_name (tree name,
|
|
|
738 htab_t name_copies, htab_t decl_copies,
|
|
|
739 bool copy_name_p)
|
|
|
740 {
|
|
|
741 tree copy, var, var_copy;
|
|
|
742 unsigned idx, uid, nuid;
|
|
|
743 struct int_tree_map ielt, *nielt;
|
|
|
744 struct name_to_copy_elt elt, *nelt;
|
|
|
745 void **slot, **dslot;
|
|
|
746
|
|
|
747 if (TREE_CODE (name) != SSA_NAME)
|
|
|
748 return name;
|
|
|
749
|
|
|
750 idx = SSA_NAME_VERSION (name);
|
|
|
751 elt.version = idx;
|
|
|
752 slot = htab_find_slot_with_hash (name_copies, &elt, idx,
|
|
|
753 copy_name_p ? INSERT : NO_INSERT);
|
|
|
754 if (slot && *slot)
|
|
|
755 return ((struct name_to_copy_elt *) *slot)->new_name;
|
|
|
756
|
|
|
757 var = SSA_NAME_VAR (name);
|
|
|
758 uid = DECL_UID (var);
|
|
|
759 ielt.uid = uid;
|
|
|
760 dslot = htab_find_slot_with_hash (decl_copies, &ielt, uid, INSERT);
|
|
|
761 if (!*dslot)
|
|
|
762 {
|
|
|
763 var_copy = create_tmp_var (TREE_TYPE (var), get_name (var));
|
|
|
764 DECL_GIMPLE_REG_P (var_copy) = DECL_GIMPLE_REG_P (var);
|
|
|
765 add_referenced_var (var_copy);
|
|
|
766 nielt = XNEW (struct int_tree_map);
|
|
|
767 nielt->uid = uid;
|
|
|
768 nielt->to = var_copy;
|
|
|
769 *dslot = nielt;
|
|
|
770
|
|
|
771 /* Ensure that when we meet this decl next time, we won't duplicate
|
|
|
772 it again. */
|
|
|
773 nuid = DECL_UID (var_copy);
|
|
|
774 ielt.uid = nuid;
|
|
|
775 dslot = htab_find_slot_with_hash (decl_copies, &ielt, nuid, INSERT);
|
|
|
776 gcc_assert (!*dslot);
|
|
|
777 nielt = XNEW (struct int_tree_map);
|
|
|
778 nielt->uid = nuid;
|
|
|
779 nielt->to = var_copy;
|
|
|
780 *dslot = nielt;
|
|
|
781 }
|
|
|
782 else
|
|
|
783 var_copy = ((struct int_tree_map *) *dslot)->to;
|
|
|
784
|
|
|
785 if (copy_name_p)
|
|
|
786 {
|
|
|
787 copy = duplicate_ssa_name (name, NULL);
|
|
|
788 nelt = XNEW (struct name_to_copy_elt);
|
|
|
789 nelt->version = idx;
|
|
|
790 nelt->new_name = copy;
|
|
|
791 nelt->field = NULL_TREE;
|
|
|
792 *slot = nelt;
|
|
|
793 }
|
|
|
794 else
|
|
|
795 {
|
|
|
796 gcc_assert (!slot);
|
|
|
797 copy = name;
|
|
|
798 }
|
|
|
799
|
|
|
800 SSA_NAME_VAR (copy) = var_copy;
|
|
|
801 return copy;
|
|
|
802 }
|
|
|
803
|
|
|
804 /* Finds the ssa names used in STMT that are defined outside the
|
|
|
805 region between ENTRY and EXIT and replaces such ssa names with
|
|
|
806 their duplicates. The duplicates are stored to NAME_COPIES. Base
|
|
|
807 decls of all ssa names used in STMT (including those defined in
|
|
|
808 LOOP) are replaced with the new temporary variables; the
|
|
|
809 replacement decls are stored in DECL_COPIES. */
|
|
|
810
|
|
|
811 static void
|
|
|
812 separate_decls_in_region_stmt (edge entry, edge exit, gimple stmt,
|
|
|
813 htab_t name_copies, htab_t decl_copies)
|
|
|
814 {
|
|
|
815 use_operand_p use;
|
|
|
816 def_operand_p def;
|
|
|
817 ssa_op_iter oi;
|
|
|
818 tree name, copy;
|
|
|
819 bool copy_name_p;
|
|
|
820
|
|
|
821 mark_virtual_ops_for_renaming (stmt);
|
|
|
822
|
|
|
823 FOR_EACH_PHI_OR_STMT_DEF (def, stmt, oi, SSA_OP_DEF)
|
|
|
824 {
|
|
|
825 name = DEF_FROM_PTR (def);
|
|
|
826 gcc_assert (TREE_CODE (name) == SSA_NAME);
|
|
|
827 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
|
|
|
828 false);
|
|
|
829 gcc_assert (copy == name);
|
|
|
830 }
|
|
|
831
|
|
|
832 FOR_EACH_PHI_OR_STMT_USE (use, stmt, oi, SSA_OP_USE)
|
|
|
833 {
|
|
|
834 name = USE_FROM_PTR (use);
|
|
|
835 if (TREE_CODE (name) != SSA_NAME)
|
|
|
836 continue;
|
|
|
837
|
|
|
838 copy_name_p = expr_invariant_in_region_p (entry, exit, name);
|
|
|
839 copy = separate_decls_in_region_name (name, name_copies, decl_copies,
|
|
|
840 copy_name_p);
|
|
|
841 SET_USE (use, copy);
|
|
|
842 }
|
|
|
843 }
|
|
|
844
|
|
|
845 /* Callback for htab_traverse. Adds a field corresponding to the reduction
|
|
|
846 specified in SLOT. The type is passed in DATA. */
|
|
|
847
|
|
|
848 static int
|
|
|
849 add_field_for_reduction (void **slot, void *data)
|
|
|
850 {
|
|
|
851
|
|
|
852 struct reduction_info *const red = (struct reduction_info *) *slot;
|
|
|
853 tree const type = (tree) data;
|
|
|
854 tree var = SSA_NAME_VAR (gimple_assign_lhs (red->reduc_stmt));
|
|
|
855 tree field = build_decl (FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
|
|
|
856
|
|
|
857 insert_field_into_struct (type, field);
|
|
|
858
|
|
|
859 red->field = field;
|
|
|
860
|
|
|
861 return 1;
|
|
|
862 }
|
|
|
863
|
|
|
864 /* Callback for htab_traverse. Adds a field corresponding to a ssa name
|
|
|
865 described in SLOT. The type is passed in DATA. */
|
|
|
866
|
|
|
867 static int
|
|
|
868 add_field_for_name (void **slot, void *data)
|
|
|
869 {
|
|
|
870 struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
|
|
|
871 tree type = (tree) data;
|
|
|
872 tree name = ssa_name (elt->version);
|
|
|
873 tree var = SSA_NAME_VAR (name);
|
|
|
874 tree field = build_decl (FIELD_DECL, DECL_NAME (var), TREE_TYPE (var));
|
|
|
875
|
|
|
876 insert_field_into_struct (type, field);
|
|
|
877 elt->field = field;
|
|
|
878
|
|
|
879 return 1;
|
|
|
880 }
|
|
|
881
|
|
|
882 /* Callback for htab_traverse. A local result is the intermediate result
|
|
|
883 computed by a single
|
|
|
884 thread, or the initial value in case no iteration was executed.
|
|
|
885 This function creates a phi node reflecting these values.
|
|
|
886 The phi's result will be stored in NEW_PHI field of the
|
|
|
887 reduction's data structure. */
|
|
|
888
|
|
|
889 static int
|
|
|
890 create_phi_for_local_result (void **slot, void *data)
|
|
|
891 {
|
|
|
892 struct reduction_info *const reduc = (struct reduction_info *) *slot;
|
|
|
893 const struct loop *const loop = (const struct loop *) data;
|
|
|
894 edge e;
|
|
|
895 gimple new_phi;
|
|
|
896 basic_block store_bb;
|
|
|
897 tree local_res;
|
|
|
898
|
|
|
899 /* STORE_BB is the block where the phi
|
|
|
900 should be stored. It is the destination of the loop exit.
|
|
|
901 (Find the fallthru edge from GIMPLE_OMP_CONTINUE). */
|
|
|
902 store_bb = FALLTHRU_EDGE (loop->latch)->dest;
|
|
|
903
|
|
|
904 /* STORE_BB has two predecessors. One coming from the loop
|
|
|
905 (the reduction's result is computed at the loop),
|
|
|
906 and another coming from a block preceding the loop,
|
|
|
907 when no iterations
|
|
|
908 are executed (the initial value should be taken). */
|
|
|
909 if (EDGE_PRED (store_bb, 0) == FALLTHRU_EDGE (loop->latch))
|
|
|
910 e = EDGE_PRED (store_bb, 1);
|
|
|
911 else
|
|
|
912 e = EDGE_PRED (store_bb, 0);
|
|
|
913 local_res
|
|
|
914 = make_ssa_name (SSA_NAME_VAR (gimple_assign_lhs (reduc->reduc_stmt)),
|
|
|
915 NULL);
|
|
|
916 new_phi = create_phi_node (local_res, store_bb);
|
|
|
917 SSA_NAME_DEF_STMT (local_res) = new_phi;
|
|
|
918 add_phi_arg (new_phi, reduc->init, e);
|
|
|
919 add_phi_arg (new_phi, gimple_assign_lhs (reduc->reduc_stmt),
|
|
|
920 FALLTHRU_EDGE (loop->latch));
|
|
|
921 reduc->new_phi = new_phi;
|
|
|
922
|
|
|
923 return 1;
|
|
|
924 }
|
|
|
925
|
|
|
926 struct clsn_data
|
|
|
927 {
|
|
|
928 tree store;
|
|
|
929 tree load;
|
|
|
930
|
|
|
931 basic_block store_bb;
|
|
|
932 basic_block load_bb;
|
|
|
933 };
|
|
|
934
|
|
|
935 /* Callback for htab_traverse. Create an atomic instruction for the
|
|
|
936 reduction described in SLOT.
|
|
|
937 DATA annotates the place in memory the atomic operation relates to,
|
|
|
938 and the basic block it needs to be generated in. */
|
|
|
939
|
|
|
940 static int
|
|
|
941 create_call_for_reduction_1 (void **slot, void *data)
|
|
|
942 {
|
|
|
943 struct reduction_info *const reduc = (struct reduction_info *) *slot;
|
|
|
944 struct clsn_data *const clsn_data = (struct clsn_data *) data;
|
|
|
945 gimple_stmt_iterator gsi;
|
|
|
946 tree type = TREE_TYPE (PHI_RESULT (reduc->reduc_phi));
|
|
|
947 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
|
|
|
948 tree load_struct;
|
|
|
949 basic_block bb;
|
|
|
950 basic_block new_bb;
|
|
|
951 edge e;
|
|
|
952 tree t, addr, addr_type, ref, x;
|
|
|
953 tree tmp_load, name;
|
|
|
954 gimple load;
|
|
|
955
|
|
|
956 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
|
|
|
957 t = build3 (COMPONENT_REF, type, load_struct, reduc->field, NULL_TREE);
|
|
|
958 addr_type = build_pointer_type (type);
|
|
|
959
|
|
|
960 addr = build_addr (t, current_function_decl);
|
|
|
961
|
|
|
962 /* Create phi node. */
|
|
|
963 bb = clsn_data->load_bb;
|
|
|
964
|
|
|
965 e = split_block (bb, t);
|
|
|
966 new_bb = e->dest;
|
|
|
967
|
|
|
968 tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)), NULL);
|
|
|
969 add_referenced_var (tmp_load);
|
|
|
970 tmp_load = make_ssa_name (tmp_load, NULL);
|
|
|
971 load = gimple_build_omp_atomic_load (tmp_load, addr);
|
|
|
972 SSA_NAME_DEF_STMT (tmp_load) = load;
|
|
|
973 gsi = gsi_start_bb (new_bb);
|
|
|
974 gsi_insert_after (&gsi, load, GSI_NEW_STMT);
|
|
|
975
|
|
|
976 e = split_block (new_bb, load);
|
|
|
977 new_bb = e->dest;
|
|
|
978 gsi = gsi_start_bb (new_bb);
|
|
|
979 ref = tmp_load;
|
|
|
980 x = fold_build2 (reduc->reduction_code,
|
|
|
981 TREE_TYPE (PHI_RESULT (reduc->new_phi)), ref,
|
|
|
982 PHI_RESULT (reduc->new_phi));
|
|
|
983
|
|
|
984 name = force_gimple_operand_gsi (&gsi, x, true, NULL_TREE, true,
|
|
|
985 GSI_CONTINUE_LINKING);
|
|
|
986
|
|
|
987 gsi_insert_after (&gsi, gimple_build_omp_atomic_store (name), GSI_NEW_STMT);
|
|
|
988 return 1;
|
|
|
989 }
|
|
|
990
|
|
|
991 /* Create the atomic operation at the join point of the threads.
|
|
|
992 REDUCTION_LIST describes the reductions in the LOOP.
|
|
|
993 LD_ST_DATA describes the shared data structure where
|
|
|
994 shared data is stored in and loaded from. */
|
|
|
995 static void
|
|
|
996 create_call_for_reduction (struct loop *loop, htab_t reduction_list,
|
|
|
997 struct clsn_data *ld_st_data)
|
|
|
998 {
|
|
|
999 htab_traverse (reduction_list, create_phi_for_local_result, loop);
|
|
|
1000 /* Find the fallthru edge from GIMPLE_OMP_CONTINUE. */
|
|
|
1001 ld_st_data->load_bb = FALLTHRU_EDGE (loop->latch)->dest;
|
|
|
1002 htab_traverse (reduction_list, create_call_for_reduction_1, ld_st_data);
|
|
|
1003 }
|
|
|
1004
|
|
|
1005 /* Callback for htab_traverse. Loads the final reduction value at the
|
|
|
1006 join point of all threads, and inserts it in the right place. */
|
|
|
1007
|
|
|
1008 static int
|
|
|
1009 create_loads_for_reductions (void **slot, void *data)
|
|
|
1010 {
|
|
|
1011 struct reduction_info *const red = (struct reduction_info *) *slot;
|
|
|
1012 struct clsn_data *const clsn_data = (struct clsn_data *) data;
|
|
|
1013 gimple stmt;
|
|
|
1014 gimple_stmt_iterator gsi;
|
|
|
1015 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
|
|
|
1016 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
|
|
|
1017 tree load_struct;
|
|
|
1018 tree name;
|
|
|
1019 tree x;
|
|
|
1020
|
|
|
1021 gsi = gsi_after_labels (clsn_data->load_bb);
|
|
|
1022 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
|
|
|
1023 load_struct = build3 (COMPONENT_REF, type, load_struct, red->field,
|
|
|
1024 NULL_TREE);
|
|
|
1025
|
|
|
1026 x = load_struct;
|
|
|
1027 name = PHI_RESULT (red->keep_res);
|
|
|
1028 stmt = gimple_build_assign (name, x);
|
|
|
1029 SSA_NAME_DEF_STMT (name) = stmt;
|
|
|
1030
|
|
|
1031 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
|
|
|
1032
|
|
|
1033 for (gsi = gsi_start_phis (gimple_bb (red->keep_res));
|
|
|
1034 !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
1035 if (gsi_stmt (gsi) == red->keep_res)
|
|
|
1036 {
|
|
|
1037 remove_phi_node (&gsi, false);
|
|
|
1038 return 1;
|
|
|
1039 }
|
|
|
1040 gcc_unreachable ();
|
|
|
1041 }
|
|
|
1042
|
|
|
1043 /* Load the reduction result that was stored in LD_ST_DATA.
|
|
|
1044 REDUCTION_LIST describes the list of reductions that the
|
|
|
1045 loads should be generated for. */
|
|
|
1046 static void
|
|
|
1047 create_final_loads_for_reduction (htab_t reduction_list,
|
|
|
1048 struct clsn_data *ld_st_data)
|
|
|
1049 {
|
|
|
1050 gimple_stmt_iterator gsi;
|
|
|
1051 tree t;
|
|
|
1052 gimple stmt;
|
|
|
1053
|
|
|
1054 gsi = gsi_after_labels (ld_st_data->load_bb);
|
|
|
1055 t = build_fold_addr_expr (ld_st_data->store);
|
|
|
1056 stmt = gimple_build_assign (ld_st_data->load, t);
|
|
|
1057
|
|
|
1058 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
|
|
|
1059 SSA_NAME_DEF_STMT (ld_st_data->load) = stmt;
|
|
|
1060
|
|
|
1061 htab_traverse (reduction_list, create_loads_for_reductions, ld_st_data);
|
|
|
1062
|
|
|
1063 }
|
|
|
1064
|
|
|
1065 /* Callback for htab_traverse. Store the neutral value for the
|
|
|
1066 particular reduction's operation, e.g. 0 for PLUS_EXPR,
|
|
|
1067 1 for MULT_EXPR, etc. into the reduction field.
|
|
|
1068 The reduction is specified in SLOT. The store information is
|
|
|
1069 passed in DATA. */
|
|
|
1070
|
|
|
1071 static int
|
|
|
1072 create_stores_for_reduction (void **slot, void *data)
|
|
|
1073 {
|
|
|
1074 struct reduction_info *const red = (struct reduction_info *) *slot;
|
|
|
1075 struct clsn_data *const clsn_data = (struct clsn_data *) data;
|
|
|
1076 tree t;
|
|
|
1077 gimple stmt;
|
|
|
1078 gimple_stmt_iterator gsi;
|
|
|
1079 tree type = TREE_TYPE (gimple_assign_lhs (red->reduc_stmt));
|
|
|
1080
|
|
|
1081 gsi = gsi_last_bb (clsn_data->store_bb);
|
|
|
1082 t = build3 (COMPONENT_REF, type, clsn_data->store, red->field, NULL_TREE);
|
|
|
1083 stmt = gimple_build_assign (t, red->initial_value);
|
|
|
1084 mark_virtual_ops_for_renaming (stmt);
|
|
|
1085 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
|
|
|
1086
|
|
|
1087 return 1;
|
|
|
1088 }
|
|
|
1089
|
|
|
1090 /* Callback for htab_traverse. Creates loads to a field of LOAD in LOAD_BB and
|
|
|
1091 store to a field of STORE in STORE_BB for the ssa name and its duplicate
|
|
|
1092 specified in SLOT. */
|
|
|
1093
|
|
|
1094 static int
|
|
|
1095 create_loads_and_stores_for_name (void **slot, void *data)
|
|
|
1096 {
|
|
|
1097 struct name_to_copy_elt *const elt = (struct name_to_copy_elt *) *slot;
|
|
|
1098 struct clsn_data *const clsn_data = (struct clsn_data *) data;
|
|
|
1099 tree t;
|
|
|
1100 gimple stmt;
|
|
|
1101 gimple_stmt_iterator gsi;
|
|
|
1102 tree type = TREE_TYPE (elt->new_name);
|
|
|
1103 tree struct_type = TREE_TYPE (TREE_TYPE (clsn_data->load));
|
|
|
1104 tree load_struct;
|
|
|
1105
|
|
|
1106 gsi = gsi_last_bb (clsn_data->store_bb);
|
|
|
1107 t = build3 (COMPONENT_REF, type, clsn_data->store, elt->field, NULL_TREE);
|
|
|
1108 stmt = gimple_build_assign (t, ssa_name (elt->version));
|
|
|
1109 mark_virtual_ops_for_renaming (stmt);
|
|
|
1110 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
|
|
|
1111
|
|
|
1112 gsi = gsi_last_bb (clsn_data->load_bb);
|
|
|
1113 load_struct = fold_build1 (INDIRECT_REF, struct_type, clsn_data->load);
|
|
|
1114 t = build3 (COMPONENT_REF, type, load_struct, elt->field, NULL_TREE);
|
|
|
1115 stmt = gimple_build_assign (elt->new_name, t);
|
|
|
1116 SSA_NAME_DEF_STMT (elt->new_name) = stmt;
|
|
|
1117 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
|
|
|
1118
|
|
|
1119 return 1;
|
|
|
1120 }
|
|
|
1121
|
|
|
1122 /* Moves all the variables used in LOOP and defined outside of it (including
|
|
|
1123 the initial values of loop phi nodes, and *PER_THREAD if it is a ssa
|
|
|
1124 name) to a structure created for this purpose. The code
|
|
|
1125
|
|
|
1126 while (1)
|
|
|
1127 {
|
|
|
1128 use (a);
|
|
|
1129 use (b);
|
|
|
1130 }
|
|
|
1131
|
|
|
1132 is transformed this way:
|
|
|
1133
|
|
|
1134 bb0:
|
|
|
1135 old.a = a;
|
|
|
1136 old.b = b;
|
|
|
1137
|
|
|
1138 bb1:
|
|
|
1139 a' = new->a;
|
|
|
1140 b' = new->b;
|
|
|
1141 while (1)
|
|
|
1142 {
|
|
|
1143 use (a');
|
|
|
1144 use (b');
|
|
|
1145 }
|
|
|
1146
|
|
|
1147 `old' is stored to *ARG_STRUCT and `new' is stored to NEW_ARG_STRUCT. The
|
|
|
1148 pointer `new' is intentionally not initialized (the loop will be split to a
|
|
|
1149 separate function later, and `new' will be initialized from its arguments).
|
|
|
1150 LD_ST_DATA holds information about the shared data structure used to pass
|
|
|
1151 information among the threads. It is initialized here, and
|
|
|
1152 gen_parallel_loop will pass it to create_call_for_reduction that
|
|
|
1153 needs this information. REDUCTION_LIST describes the reductions
|
|
|
1154 in LOOP. */
|
|
|
1155
|
|
|
1156 static void
|
|
|
1157 separate_decls_in_region (edge entry, edge exit, htab_t reduction_list,
|
|
|
1158 tree *arg_struct, tree *new_arg_struct,
|
|
|
1159 struct clsn_data *ld_st_data)
|
|
|
1160
|
|
|
1161 {
|
|
|
1162 basic_block bb1 = split_edge (entry);
|
|
|
1163 basic_block bb0 = single_pred (bb1);
|
|
|
1164 htab_t name_copies = htab_create (10, name_to_copy_elt_hash,
|
|
|
1165 name_to_copy_elt_eq, free);
|
|
|
1166 htab_t decl_copies = htab_create (10, int_tree_map_hash, int_tree_map_eq,
|
|
|
1167 free);
|
|
|
1168 unsigned i;
|
|
|
1169 tree type, type_name, nvar;
|
|
|
1170 gimple_stmt_iterator gsi;
|
|
|
1171 struct clsn_data clsn_data;
|
|
|
1172 VEC (basic_block, heap) *body = VEC_alloc (basic_block, heap, 3);
|
|
|
1173 basic_block bb;
|
|
|
1174 basic_block entry_bb = bb1;
|
|
|
1175 basic_block exit_bb = exit->dest;
|
|
|
1176
|
|
|
1177 entry = single_succ_edge (entry_bb);
|
|
|
1178 gather_blocks_in_sese_region (entry_bb, exit_bb, &body);
|
|
|
1179
|
|
|
1180 for (i = 0; VEC_iterate (basic_block, body, i, bb); i++)
|
|
|
1181 {
|
|
|
1182 if (bb != entry_bb && bb != exit_bb)
|
|
|
1183 {
|
|
|
1184 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
1185 separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
|
|
|
1186 name_copies, decl_copies);
|
|
|
1187
|
|
|
1188 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
1189 separate_decls_in_region_stmt (entry, exit, gsi_stmt (gsi),
|
|
|
1190 name_copies, decl_copies);
|
|
|
1191 }
|
|
|
1192 }
|
|
|
1193
|
|
|
1194 VEC_free (basic_block, heap, body);
|
|
|
1195
|
|
|
1196 if (htab_elements (name_copies) == 0 && reduction_list == 0)
|
|
|
1197 {
|
|
|
1198 /* It may happen that there is nothing to copy (if there are only
|
|
|
1199 loop carried and external variables in the loop). */
|
|
|
1200 *arg_struct = NULL;
|
|
|
1201 *new_arg_struct = NULL;
|
|
|
1202 }
|
|
|
1203 else
|
|
|
1204 {
|
|
|
1205 /* Create the type for the structure to store the ssa names to. */
|
|
|
1206 type = lang_hooks.types.make_type (RECORD_TYPE);
|
|
|
1207 type_name = build_decl (TYPE_DECL, create_tmp_var_name (".paral_data"),
|
|
|
1208 type);
|
|
|
1209 TYPE_NAME (type) = type_name;
|
|
|
1210
|
|
|
1211 htab_traverse (name_copies, add_field_for_name, type);
|
|
|
1212 if (reduction_list && htab_elements (reduction_list) > 0)
|
|
|
1213 {
|
|
|
1214 /* Create the fields for reductions. */
|
|
|
1215 htab_traverse (reduction_list, add_field_for_reduction,
|
|
|
1216 type);
|
|
|
1217 }
|
|
|
1218 layout_type (type);
|
|
|
1219
|
|
|
1220 /* Create the loads and stores. */
|
|
|
1221 *arg_struct = create_tmp_var (type, ".paral_data_store");
|
|
|
1222 add_referenced_var (*arg_struct);
|
|
|
1223 nvar = create_tmp_var (build_pointer_type (type), ".paral_data_load");
|
|
|
1224 add_referenced_var (nvar);
|
|
|
1225 *new_arg_struct = make_ssa_name (nvar, NULL);
|
|
|
1226
|
|
|
1227 ld_st_data->store = *arg_struct;
|
|
|
1228 ld_st_data->load = *new_arg_struct;
|
|
|
1229 ld_st_data->store_bb = bb0;
|
|
|
1230 ld_st_data->load_bb = bb1;
|
|
|
1231
|
|
|
1232 htab_traverse (name_copies, create_loads_and_stores_for_name,
|
|
|
1233 ld_st_data);
|
|
|
1234
|
|
|
1235 /* Load the calculation from memory (after the join of the threads). */
|
|
|
1236
|
|
|
1237 if (reduction_list && htab_elements (reduction_list) > 0)
|
|
|
1238 {
|
|
|
1239 htab_traverse (reduction_list, create_stores_for_reduction,
|
|
|
1240 ld_st_data);
|
|
|
1241 clsn_data.load = make_ssa_name (nvar, NULL);
|
|
|
1242 clsn_data.load_bb = exit->dest;
|
|
|
1243 clsn_data.store = ld_st_data->store;
|
|
|
1244 create_final_loads_for_reduction (reduction_list, &clsn_data);
|
|
|
1245 }
|
|
|
1246 }
|
|
|
1247
|
|
|
1248 htab_delete (decl_copies);
|
|
|
1249 htab_delete (name_copies);
|
|
|
1250 }
|
|
|
1251
|
|
|
1252 /* Bitmap containing uids of functions created by parallelization. We cannot
|
|
|
1253 allocate it from the default obstack, as it must live across compilation
|
|
|
1254 of several functions; we make it gc allocated instead. */
|
|
|
1255
|
|
|
1256 static GTY(()) bitmap parallelized_functions;
|
|
|
1257
|
|
|
1258 /* Returns true if FN was created by create_loop_fn. */
|
|
|
1259
|
|
|
1260 static bool
|
|
|
1261 parallelized_function_p (tree fn)
|
|
|
1262 {
|
|
|
1263 if (!parallelized_functions || !DECL_ARTIFICIAL (fn))
|
|
|
1264 return false;
|
|
|
1265
|
|
|
1266 return bitmap_bit_p (parallelized_functions, DECL_UID (fn));
|
|
|
1267 }
|
|
|
1268
|
|
|
1269 /* Creates and returns an empty function that will receive the body of
|
|
|
1270 a parallelized loop. */
|
|
|
1271
|
|
|
1272 static tree
|
|
|
1273 create_loop_fn (void)
|
|
|
1274 {
|
|
|
1275 char buf[100];
|
|
|
1276 char *tname;
|
|
|
1277 tree decl, type, name, t;
|
|
|
1278 struct function *act_cfun = cfun;
|
|
|
1279 static unsigned loopfn_num;
|
|
|
1280
|
|
|
1281 snprintf (buf, 100, "%s.$loopfn", current_function_name ());
|
|
|
1282 ASM_FORMAT_PRIVATE_NAME (tname, buf, loopfn_num++);
|
|
|
1283 clean_symbol_name (tname);
|
|
|
1284 name = get_identifier (tname);
|
|
|
1285 type = build_function_type_list (void_type_node, ptr_type_node, NULL_TREE);
|
|
|
1286
|
|
|
1287 decl = build_decl (FUNCTION_DECL, name, type);
|
|
|
1288 if (!parallelized_functions)
|
|
|
1289 parallelized_functions = BITMAP_GGC_ALLOC ();
|
|
|
1290 bitmap_set_bit (parallelized_functions, DECL_UID (decl));
|
|
|
1291
|
|
|
1292 TREE_STATIC (decl) = 1;
|
|
|
1293 TREE_USED (decl) = 1;
|
|
|
1294 DECL_ARTIFICIAL (decl) = 1;
|
|
|
1295 DECL_IGNORED_P (decl) = 0;
|
|
|
1296 TREE_PUBLIC (decl) = 0;
|
|
|
1297 DECL_UNINLINABLE (decl) = 1;
|
|
|
1298 DECL_EXTERNAL (decl) = 0;
|
|
|
1299 DECL_CONTEXT (decl) = NULL_TREE;
|
|
|
1300 DECL_INITIAL (decl) = make_node (BLOCK);
|
|
|
1301
|
|
|
1302 t = build_decl (RESULT_DECL, NULL_TREE, void_type_node);
|
|
|
1303 DECL_ARTIFICIAL (t) = 1;
|
|
|
1304 DECL_IGNORED_P (t) = 1;
|
|
|
1305 DECL_RESULT (decl) = t;
|
|
|
1306
|
|
|
1307 t = build_decl (PARM_DECL, get_identifier (".paral_data_param"),
|
|
|
1308 ptr_type_node);
|
|
|
1309 DECL_ARTIFICIAL (t) = 1;
|
|
|
1310 DECL_ARG_TYPE (t) = ptr_type_node;
|
|
|
1311 DECL_CONTEXT (t) = decl;
|
|
|
1312 TREE_USED (t) = 1;
|
|
|
1313 DECL_ARGUMENTS (decl) = t;
|
|
|
1314
|
|
|
1315 allocate_struct_function (decl, false);
|
|
|
1316
|
|
|
1317 /* The call to allocate_struct_function clobbers CFUN, so we need to restore
|
|
|
1318 it. */
|
|
|
1319 set_cfun (act_cfun);
|
|
|
1320
|
|
|
1321 return decl;
|
|
|
1322 }
|
|
|
1323
|
|
|
1324 /* Bases all the induction variables in LOOP on a single induction
|
|
|
1325 variable (unsigned with base 0 and step 1), whose final value is
|
|
|
1326 compared with *NIT. When the IV type precision has to be larger
|
|
|
1327 than *NIT type precision, *NIT is converted to the larger type, the
|
|
|
1328 conversion code is inserted before the loop, and *NIT is updated to
|
|
|
1329 the new definition. The induction variable is incremented in the
|
|
|
1330 loop latch. REDUCTION_LIST describes the reductions in LOOP.
|
|
|
1331 Return the induction variable that was created. */
|
|
|
1332
|
|
|
1333 tree
|
|
|
1334 canonicalize_loop_ivs (struct loop *loop, htab_t reduction_list, tree *nit)
|
|
|
1335 {
|
|
|
1336 unsigned precision = TYPE_PRECISION (TREE_TYPE (*nit));
|
|
|
1337 unsigned original_precision = precision;
|
|
|
1338 tree res, type, var_before, val, atype, mtype;
|
|
|
1339 gimple_stmt_iterator gsi, psi;
|
|
|
1340 gimple phi, stmt;
|
|
|
1341 bool ok;
|
|
|
1342 affine_iv iv;
|
|
|
1343 edge exit = single_dom_exit (loop);
|
|
|
1344 struct reduction_info *red;
|
|
|
1345 gimple_seq stmts;
|
|
|
1346
|
|
|
1347 for (psi = gsi_start_phis (loop->header);
|
|
|
1348 !gsi_end_p (psi); gsi_next (&psi))
|
|
|
1349 {
|
|
|
1350 phi = gsi_stmt (psi);
|
|
|
1351 res = PHI_RESULT (phi);
|
|
|
1352
|
|
|
1353 if (is_gimple_reg (res) && TYPE_PRECISION (TREE_TYPE (res)) > precision)
|
|
|
1354 precision = TYPE_PRECISION (TREE_TYPE (res));
|
|
|
1355 }
|
|
|
1356
|
|
|
1357 type = lang_hooks.types.type_for_size (precision, 1);
|
|
|
1358
|
|
|
1359 if (original_precision != precision)
|
|
|
1360 {
|
|
|
1361 *nit = fold_convert (type, *nit);
|
|
|
1362 *nit = force_gimple_operand (*nit, &stmts, true, NULL_TREE);
|
|
|
1363 if (stmts)
|
|
|
1364 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
|
|
|
1365 }
|
|
|
1366
|
|
|
1367 gsi = gsi_last_bb (loop->latch);
|
|
|
1368 create_iv (build_int_cst_type (type, 0), build_int_cst (type, 1), NULL_TREE,
|
|
|
1369 loop, &gsi, true, &var_before, NULL);
|
|
|
1370
|
|
|
1371 gsi = gsi_after_labels (loop->header);
|
|
|
1372 for (psi = gsi_start_phis (loop->header); !gsi_end_p (psi); )
|
|
|
1373 {
|
|
|
1374 phi = gsi_stmt (psi);
|
|
|
1375 res = PHI_RESULT (phi);
|
|
|
1376
|
|
|
1377 if (!is_gimple_reg (res) || res == var_before)
|
|
|
1378 {
|
|
|
1379 gsi_next (&psi);
|
|
|
1380 continue;
|
|
|
1381 }
|
|
|
1382
|
|
|
1383 ok = simple_iv (loop, loop, res, &iv, true);
|
|
|
1384
|
|
|
1385 if (reduction_list)
|
|
|
1386 red = reduction_phi (reduction_list, phi);
|
|
|
1387 else
|
|
|
1388 red = NULL;
|
|
|
1389
|
|
|
1390 /* We preserve the reduction phi nodes. */
|
|
|
1391 if (!ok && red)
|
|
|
1392 {
|
|
|
1393 gsi_next (&psi);
|
|
|
1394 continue;
|
|
|
1395 }
|
|
|
1396 else
|
|
|
1397 gcc_assert (ok);
|
|
|
1398 remove_phi_node (&psi, false);
|
|
|
1399
|
|
|
1400 atype = TREE_TYPE (res);
|
|
|
1401 mtype = POINTER_TYPE_P (atype) ? sizetype : atype;
|
|
|
1402 val = fold_build2 (MULT_EXPR, mtype, unshare_expr (iv.step),
|
|
|
1403 fold_convert (mtype, var_before));
|
|
|
1404 val = fold_build2 (POINTER_TYPE_P (atype)
|
|
|
1405 ? POINTER_PLUS_EXPR : PLUS_EXPR,
|
|
|
1406 atype, unshare_expr (iv.base), val);
|
|
|
1407 val = force_gimple_operand_gsi (&gsi, val, false, NULL_TREE, true,
|
|
|
1408 GSI_SAME_STMT);
|
|
|
1409 stmt = gimple_build_assign (res, val);
|
|
|
1410 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
|
|
|
1411 SSA_NAME_DEF_STMT (res) = stmt;
|
|
|
1412 }
|
|
|
1413
|
|
|
1414 stmt = last_stmt (exit->src);
|
|
|
1415 /* Make the loop exit if the control condition is not satisfied. */
|
|
|
1416 if (exit->flags & EDGE_TRUE_VALUE)
|
|
|
1417 {
|
|
|
1418 edge te, fe;
|
|
|
1419
|
|
|
1420 extract_true_false_edges_from_block (exit->src, &te, &fe);
|
|
|
1421 te->flags = EDGE_FALSE_VALUE;
|
|
|
1422 fe->flags = EDGE_TRUE_VALUE;
|
|
|
1423 }
|
|
|
1424 gimple_cond_set_code (stmt, LT_EXPR);
|
|
|
1425 gimple_cond_set_lhs (stmt, var_before);
|
|
|
1426 gimple_cond_set_rhs (stmt, *nit);
|
|
|
1427 update_stmt (stmt);
|
|
|
1428
|
|
|
1429 return var_before;
|
|
|
1430 }
|
|
|
1431
|
|
|
1432 /* Moves the exit condition of LOOP to the beginning of its header, and
|
|
|
1433 duplicates the part of the last iteration that gets disabled to the
|
|
|
1434 exit of the loop. NIT is the number of iterations of the loop
|
|
|
1435 (used to initialize the variables in the duplicated part).
|
|
|
1436
|
|
|
1437 TODO: the common case is that latch of the loop is empty and immediately
|
|
|
1438 follows the loop exit. In this case, it would be better not to copy the
|
|
|
1439 body of the loop, but only move the entry of the loop directly before the
|
|
|
1440 exit check and increase the number of iterations of the loop by one.
|
|
|
1441 This may need some additional preconditioning in case NIT = ~0.
|
|
|
1442 REDUCTION_LIST describes the reductions in LOOP. */
|
|
|
1443
|
|
|
1444 static void
|
|
|
1445 transform_to_exit_first_loop (struct loop *loop, htab_t reduction_list, tree nit)
|
|
|
1446 {
|
|
|
1447 basic_block *bbs, *nbbs, ex_bb, orig_header;
|
|
|
1448 unsigned n;
|
|
|
1449 bool ok;
|
|
|
1450 edge exit = single_dom_exit (loop), hpred;
|
|
|
1451 tree control, control_name, res, t;
|
|
|
1452 gimple phi, nphi, cond_stmt, stmt;
|
|
|
1453 gimple_stmt_iterator gsi;
|
|
|
1454
|
|
|
1455 split_block_after_labels (loop->header);
|
|
|
1456 orig_header = single_succ (loop->header);
|
|
|
1457 hpred = single_succ_edge (loop->header);
|
|
|
1458
|
|
|
1459 cond_stmt = last_stmt (exit->src);
|
|
|
1460 control = gimple_cond_lhs (cond_stmt);
|
|
|
1461 gcc_assert (gimple_cond_rhs (cond_stmt) == nit);
|
|
|
1462
|
|
|
1463 /* Make sure that we have phi nodes on exit for all loop header phis
|
|
|
1464 (create_parallel_loop requires that). */
|
|
|
1465 for (gsi = gsi_start_phis (loop->header); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
1466 {
|
|
|
1467 phi = gsi_stmt (gsi);
|
|
|
1468 res = PHI_RESULT (phi);
|
|
|
1469 t = make_ssa_name (SSA_NAME_VAR (res), phi);
|
|
|
1470 SET_PHI_RESULT (phi, t);
|
|
|
1471
|
|
|
1472 nphi = create_phi_node (res, orig_header);
|
|
|
1473 SSA_NAME_DEF_STMT (res) = nphi;
|
|
|
1474 add_phi_arg (nphi, t, hpred);
|
|
|
1475
|
|
|
1476 if (res == control)
|
|
|
1477 {
|
|
|
1478 gimple_cond_set_lhs (cond_stmt, t);
|
|
|
1479 update_stmt (cond_stmt);
|
|
|
1480 control = t;
|
|
|
1481 }
|
|
|
1482 }
|
|
|
1483
|
|
|
1484 bbs = get_loop_body_in_dom_order (loop);
|
|
|
1485 for (n = 0; bbs[n] != exit->src; n++)
|
|
|
1486 continue;
|
|
|
1487 nbbs = XNEWVEC (basic_block, n);
|
|
|
1488 ok = gimple_duplicate_sese_tail (single_succ_edge (loop->header), exit,
|
|
|
1489 bbs + 1, n, nbbs);
|
|
|
1490 gcc_assert (ok);
|
|
|
1491 free (bbs);
|
|
|
1492 ex_bb = nbbs[0];
|
|
|
1493 free (nbbs);
|
|
|
1494
|
|
|
1495 /* Other than reductions, the only gimple reg that should be copied
|
|
|
1496 out of the loop is the control variable. */
|
|
|
1497
|
|
|
1498 control_name = NULL_TREE;
|
|
|
1499 for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); )
|
|
|
1500 {
|
|
|
1501 phi = gsi_stmt (gsi);
|
|
|
1502 res = PHI_RESULT (phi);
|
|
|
1503 if (!is_gimple_reg (res))
|
|
|
1504 {
|
|
|
1505 gsi_next (&gsi);
|
|
|
1506 continue;
|
|
|
1507 }
|
|
|
1508
|
|
|
1509 /* Check if it is a part of reduction. If it is,
|
|
|
1510 keep the phi at the reduction's keep_res field. The
|
|
|
1511 PHI_RESULT of this phi is the resulting value of the reduction
|
|
|
1512 variable when exiting the loop. */
|
|
|
1513
|
|
|
1514 exit = single_dom_exit (loop);
|
|
|
1515
|
|
|
1516 if (htab_elements (reduction_list) > 0)
|
|
|
1517 {
|
|
|
1518 struct reduction_info *red;
|
|
|
1519
|
|
|
1520 tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
|
|
|
1521
|
|
|
1522 red = reduction_phi (reduction_list, SSA_NAME_DEF_STMT (val));
|
|
|
1523 if (red)
|
|
|
1524 {
|
|
|
1525 red->keep_res = phi;
|
|
|
1526 gsi_next (&gsi);
|
|
|
1527 continue;
|
|
|
1528 }
|
|
|
1529 }
|
|
|
1530 gcc_assert (control_name == NULL_TREE
|
|
|
1531 && SSA_NAME_VAR (res) == SSA_NAME_VAR (control));
|
|
|
1532 control_name = res;
|
|
|
1533 remove_phi_node (&gsi, false);
|
|
|
1534 }
|
|
|
1535 gcc_assert (control_name != NULL_TREE);
|
|
|
1536
|
|
|
1537 /* Initialize the control variable to NIT. */
|
|
|
1538 gsi = gsi_after_labels (ex_bb);
|
|
|
1539 nit = force_gimple_operand_gsi (&gsi,
|
|
|
1540 fold_convert (TREE_TYPE (control_name), nit),
|
|
|
1541 false, NULL_TREE, false, GSI_SAME_STMT);
|
|
|
1542 stmt = gimple_build_assign (control_name, nit);
|
|
|
1543 gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
|
|
|
1544 SSA_NAME_DEF_STMT (control_name) = stmt;
|
|
|
1545 }
|
|
|
1546
|
|
|
1547 /* Create the parallel constructs for LOOP as described in gen_parallel_loop.
|
|
|
1548 LOOP_FN and DATA are the arguments of GIMPLE_OMP_PARALLEL.
|
|
|
1549 NEW_DATA is the variable that should be initialized from the argument
|
|
|
1550 of LOOP_FN. N_THREADS is the requested number of threads. Returns the
|
|
|
1551 basic block containing GIMPLE_OMP_PARALLEL tree. */
|
|
|
1552
|
|
|
1553 static basic_block
|
|
|
1554 create_parallel_loop (struct loop *loop, tree loop_fn, tree data,
|
|
|
1555 tree new_data, unsigned n_threads)
|
|
|
1556 {
|
|
|
1557 gimple_stmt_iterator gsi;
|
|
|
1558 basic_block bb, paral_bb, for_bb, ex_bb;
|
|
|
1559 tree t, param, res;
|
|
|
1560 gimple stmt, for_stmt, phi, cond_stmt;
|
|
|
1561 tree cvar, cvar_init, initvar, cvar_next, cvar_base, type;
|
|
|
1562 edge exit, nexit, guard, end, e;
|
|
|
1563
|
|
|
1564 /* Prepare the GIMPLE_OMP_PARALLEL statement. */
|
|
|
1565 bb = loop_preheader_edge (loop)->src;
|
|
|
1566 paral_bb = single_pred (bb);
|
|
|
1567 gsi = gsi_last_bb (paral_bb);
|
|
|
1568
|
|
|
1569 t = build_omp_clause (OMP_CLAUSE_NUM_THREADS);
|
|
|
1570 OMP_CLAUSE_NUM_THREADS_EXPR (t)
|
|
|
1571 = build_int_cst (integer_type_node, n_threads);
|
|
|
1572 stmt = gimple_build_omp_parallel (NULL, t, loop_fn, data);
|
|
|
1573
|
|
|
1574 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
|
|
|
1575
|
|
|
1576 /* Initialize NEW_DATA. */
|
|
|
1577 if (data)
|
|
|
1578 {
|
|
|
1579 gsi = gsi_after_labels (bb);
|
|
|
1580
|
|
|
1581 param = make_ssa_name (DECL_ARGUMENTS (loop_fn), NULL);
|
|
|
1582 stmt = gimple_build_assign (param, build_fold_addr_expr (data));
|
|
|
1583 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
|
|
|
1584 SSA_NAME_DEF_STMT (param) = stmt;
|
|
|
1585
|
|
|
1586 stmt = gimple_build_assign (new_data,
|
|
|
1587 fold_convert (TREE_TYPE (new_data), param));
|
|
|
1588 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
|
|
|
1589 SSA_NAME_DEF_STMT (new_data) = stmt;
|
|
|
1590 }
|
|
|
1591
|
|
|
1592 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_PARALLEL. */
|
|
|
1593 bb = split_loop_exit_edge (single_dom_exit (loop));
|
|
|
1594 gsi = gsi_last_bb (bb);
|
|
|
1595 gsi_insert_after (&gsi, gimple_build_omp_return (false), GSI_NEW_STMT);
|
|
|
1596
|
|
|
1597 /* Extract data for GIMPLE_OMP_FOR. */
|
|
|
1598 gcc_assert (loop->header == single_dom_exit (loop)->src);
|
|
|
1599 cond_stmt = last_stmt (loop->header);
|
|
|
1600
|
|
|
1601 cvar = gimple_cond_lhs (cond_stmt);
|
|
|
1602 cvar_base = SSA_NAME_VAR (cvar);
|
|
|
1603 phi = SSA_NAME_DEF_STMT (cvar);
|
|
|
1604 cvar_init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
|
|
|
1605 initvar = make_ssa_name (cvar_base, NULL);
|
|
|
1606 SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, loop_preheader_edge (loop)),
|
|
|
1607 initvar);
|
|
|
1608 cvar_next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
|
|
|
1609
|
|
|
1610 gsi = gsi_last_bb (loop->latch);
|
|
|
1611 gcc_assert (gsi_stmt (gsi) == SSA_NAME_DEF_STMT (cvar_next));
|
|
|
1612 gsi_remove (&gsi, true);
|
|
|
1613
|
|
|
1614 /* Prepare cfg. */
|
|
|
1615 for_bb = split_edge (loop_preheader_edge (loop));
|
|
|
1616 ex_bb = split_loop_exit_edge (single_dom_exit (loop));
|
|
|
1617 extract_true_false_edges_from_block (loop->header, &nexit, &exit);
|
|
|
1618 gcc_assert (exit == single_dom_exit (loop));
|
|
|
1619
|
|
|
1620 guard = make_edge (for_bb, ex_bb, 0);
|
|
|
1621 single_succ_edge (loop->latch)->flags = 0;
|
|
|
1622 end = make_edge (loop->latch, ex_bb, EDGE_FALLTHRU);
|
|
|
1623 for (gsi = gsi_start_phis (ex_bb); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
1624 {
|
|
|
1625 phi = gsi_stmt (gsi);
|
|
|
1626 res = PHI_RESULT (phi);
|
|
|
1627 stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF_FROM_EDGE (phi, exit));
|
|
|
1628 add_phi_arg (phi,
|
|
|
1629 PHI_ARG_DEF_FROM_EDGE (stmt, loop_preheader_edge (loop)),
|
|
|
1630 guard);
|
|
|
1631 add_phi_arg (phi, PHI_ARG_DEF_FROM_EDGE (stmt, loop_latch_edge (loop)),
|
|
|
1632 end);
|
|
|
1633 }
|
|
|
1634 e = redirect_edge_and_branch (exit, nexit->dest);
|
|
|
1635 PENDING_STMT (e) = NULL;
|
|
|
1636
|
|
|
1637 /* Emit GIMPLE_OMP_FOR. */
|
|
|
1638 gimple_cond_set_lhs (cond_stmt, cvar_base);
|
|
|
1639 type = TREE_TYPE (cvar);
|
|
|
1640 t = build_omp_clause (OMP_CLAUSE_SCHEDULE);
|
|
|
1641 OMP_CLAUSE_SCHEDULE_KIND (t) = OMP_CLAUSE_SCHEDULE_STATIC;
|
|
|
1642
|
|
|
1643 for_stmt = gimple_build_omp_for (NULL, t, 1, NULL);
|
|
|
1644 gimple_omp_for_set_index (for_stmt, 0, initvar);
|
|
|
1645 gimple_omp_for_set_initial (for_stmt, 0, cvar_init);
|
|
|
1646 gimple_omp_for_set_final (for_stmt, 0, gimple_cond_rhs (cond_stmt));
|
|
|
1647 gimple_omp_for_set_cond (for_stmt, 0, gimple_cond_code (cond_stmt));
|
|
|
1648 gimple_omp_for_set_incr (for_stmt, 0, build2 (PLUS_EXPR, type,
|
|
|
1649 cvar_base,
|
|
|
1650 build_int_cst (type, 1)));
|
|
|
1651
|
|
|
1652 gsi = gsi_last_bb (for_bb);
|
|
|
1653 gsi_insert_after (&gsi, for_stmt, GSI_NEW_STMT);
|
|
|
1654 SSA_NAME_DEF_STMT (initvar) = for_stmt;
|
|
|
1655
|
|
|
1656 /* Emit GIMPLE_OMP_CONTINUE. */
|
|
|
1657 gsi = gsi_last_bb (loop->latch);
|
|
|
1658 stmt = gimple_build_omp_continue (cvar_next, cvar);
|
|
|
1659 gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
|
|
|
1660 SSA_NAME_DEF_STMT (cvar_next) = stmt;
|
|
|
1661
|
|
|
1662 /* Emit GIMPLE_OMP_RETURN for GIMPLE_OMP_FOR. */
|
|
|
1663 gsi = gsi_last_bb (ex_bb);
|
|
|
1664 gsi_insert_after (&gsi, gimple_build_omp_return (true), GSI_NEW_STMT);
|
|
|
1665
|
|
|
1666 return paral_bb;
|
|
|
1667 }
|
|
|
1668
|
|
|
1669 /* Generates code to execute the iterations of LOOP in N_THREADS threads in
|
|
|
1670 parallel. NITER describes number of iterations of LOOP.
|
|
|
1671 REDUCTION_LIST describes the reductions existent in the LOOP. */
|
|
|
1672
|
|
|
1673 static void
|
|
|
1674 gen_parallel_loop (struct loop *loop, htab_t reduction_list,
|
|
|
1675 unsigned n_threads, struct tree_niter_desc *niter)
|
|
|
1676 {
|
|
|
1677 struct loop *nloop;
|
|
|
1678 loop_iterator li;
|
|
|
1679 tree many_iterations_cond, type, nit;
|
|
|
1680 tree arg_struct, new_arg_struct;
|
|
|
1681 gimple_seq stmts;
|
|
|
1682 basic_block parallel_head;
|
|
|
1683 edge entry, exit;
|
|
|
1684 struct clsn_data clsn_data;
|
|
|
1685 unsigned prob;
|
|
|
1686
|
|
|
1687 /* From
|
|
|
1688
|
|
|
1689 ---------------------------------------------------------------------
|
|
|
1690 loop
|
|
|
1691 {
|
|
|
1692 IV = phi (INIT, IV + STEP)
|
|
|
1693 BODY1;
|
|
|
1694 if (COND)
|
|
|
1695 break;
|
|
|
1696 BODY2;
|
|
|
1697 }
|
|
|
1698 ---------------------------------------------------------------------
|
|
|
1699
|
|
|
1700 with # of iterations NITER (possibly with MAY_BE_ZERO assumption),
|
|
|
1701 we generate the following code:
|
|
|
1702
|
|
|
1703 ---------------------------------------------------------------------
|
|
|
1704
|
|
|
1705 if (MAY_BE_ZERO
|
|
|
1706 || NITER < MIN_PER_THREAD * N_THREADS)
|
|
|
1707 goto original;
|
|
|
1708
|
|
|
1709 BODY1;
|
|
|
1710 store all local loop-invariant variables used in body of the loop to DATA.
|
|
|
1711 GIMPLE_OMP_PARALLEL (OMP_CLAUSE_NUM_THREADS (N_THREADS), LOOPFN, DATA);
|
|
|
1712 load the variables from DATA.
|
|
|
1713 GIMPLE_OMP_FOR (IV = INIT; COND; IV += STEP) (OMP_CLAUSE_SCHEDULE (static))
|
|
|
1714 BODY2;
|
|
|
1715 BODY1;
|
|
|
1716 GIMPLE_OMP_CONTINUE;
|
|
|
1717 GIMPLE_OMP_RETURN -- GIMPLE_OMP_FOR
|
|
|
1718 GIMPLE_OMP_RETURN -- GIMPLE_OMP_PARALLEL
|
|
|
1719 goto end;
|
|
|
1720
|
|
|
1721 original:
|
|
|
1722 loop
|
|
|
1723 {
|
|
|
1724 IV = phi (INIT, IV + STEP)
|
|
|
1725 BODY1;
|
|
|
1726 if (COND)
|
|
|
1727 break;
|
|
|
1728 BODY2;
|
|
|
1729 }
|
|
|
1730
|
|
|
1731 end:
|
|
|
1732
|
|
|
1733 */
|
|
|
1734
|
|
|
1735 /* Create two versions of the loop -- in the old one, we know that the
|
|
|
1736 number of iterations is large enough, and we will transform it into the
|
|
|
1737 loop that will be split to loop_fn, the new one will be used for the
|
|
|
1738 remaining iterations. */
|
|
|
1739
|
|
|
1740 type = TREE_TYPE (niter->niter);
|
|
|
1741 nit = force_gimple_operand (unshare_expr (niter->niter), &stmts, true,
|
|
|
1742 NULL_TREE);
|
|
|
1743 if (stmts)
|
|
|
1744 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
|
|
|
1745
|
|
|
1746 many_iterations_cond =
|
|
|
1747 fold_build2 (GE_EXPR, boolean_type_node,
|
|
|
1748 nit, build_int_cst (type, MIN_PER_THREAD * n_threads));
|
|
|
1749 many_iterations_cond
|
|
|
1750 = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
|
|
|
1751 invert_truthvalue (unshare_expr (niter->may_be_zero)),
|
|
|
1752 many_iterations_cond);
|
|
|
1753 many_iterations_cond
|
|
|
1754 = force_gimple_operand (many_iterations_cond, &stmts, false, NULL_TREE);
|
|
|
1755 if (stmts)
|
|
|
1756 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
|
|
|
1757 if (!is_gimple_condexpr (many_iterations_cond))
|
|
|
1758 {
|
|
|
1759 many_iterations_cond
|
|
|
1760 = force_gimple_operand (many_iterations_cond, &stmts,
|
|
|
1761 true, NULL_TREE);
|
|
|
1762 if (stmts)
|
|
|
1763 gsi_insert_seq_on_edge_immediate (loop_preheader_edge (loop), stmts);
|
|
|
1764 }
|
|
|
1765
|
|
|
1766 initialize_original_copy_tables ();
|
|
|
1767
|
|
|
1768 /* We assume that the loop usually iterates a lot. */
|
|
|
1769 prob = 4 * REG_BR_PROB_BASE / 5;
|
|
|
1770 nloop = loop_version (loop, many_iterations_cond, NULL,
|
|
|
1771 prob, prob, REG_BR_PROB_BASE - prob, true);
|
|
|
1772 update_ssa (TODO_update_ssa);
|
|
|
1773 free_original_copy_tables ();
|
|
|
1774
|
|
|
1775 /* Base all the induction variables in LOOP on a single control one. */
|
|
|
1776 canonicalize_loop_ivs (loop, reduction_list, &nit);
|
|
|
1777
|
|
|
1778 /* Ensure that the exit condition is the first statement in the loop. */
|
|
|
1779 transform_to_exit_first_loop (loop, reduction_list, nit);
|
|
|
1780
|
|
|
1781 /* Generate initializations for reductions. */
|
|
|
1782 if (htab_elements (reduction_list) > 0)
|
|
|
1783 htab_traverse (reduction_list, initialize_reductions, loop);
|
|
|
1784
|
|
|
1785 /* Eliminate the references to local variables from the loop. */
|
|
|
1786 gcc_assert (single_exit (loop));
|
|
|
1787 entry = loop_preheader_edge (loop);
|
|
|
1788 exit = single_dom_exit (loop);
|
|
|
1789
|
|
|
1790 eliminate_local_variables (entry, exit);
|
|
|
1791 /* In the old loop, move all variables non-local to the loop to a structure
|
|
|
1792 and back, and create separate decls for the variables used in loop. */
|
|
|
1793 separate_decls_in_region (entry, exit, reduction_list, &arg_struct,
|
|
|
1794 &new_arg_struct, &clsn_data);
|
|
|
1795
|
|
|
1796 /* Create the parallel constructs. */
|
|
|
1797 parallel_head = create_parallel_loop (loop, create_loop_fn (), arg_struct,
|
|
|
1798 new_arg_struct, n_threads);
|
|
|
1799 if (htab_elements (reduction_list) > 0)
|
|
|
1800 create_call_for_reduction (loop, reduction_list, &clsn_data);
|
|
|
1801
|
|
|
1802 scev_reset ();
|
|
|
1803
|
|
|
1804 /* Cancel the loop (it is simpler to do it here rather than to teach the
|
|
|
1805 expander to do it). */
|
|
|
1806 cancel_loop_tree (loop);
|
|
|
1807
|
|
|
1808 /* Free loop bound estimations that could contain references to
|
|
|
1809 removed statements. */
|
|
|
1810 FOR_EACH_LOOP (li, loop, 0)
|
|
|
1811 free_numbers_of_iterations_estimates_loop (loop);
|
|
|
1812
|
|
|
1813 /* Expand the parallel constructs. We do it directly here instead of running
|
|
|
1814 a separate expand_omp pass, since it is more efficient, and less likely to
|
|
|
1815 cause troubles with further analyses not being able to deal with the
|
|
|
1816 OMP trees. */
|
|
|
1817
|
|
|
1818 omp_expand_local (parallel_head);
|
|
|
1819 }
|
|
|
1820
|
|
|
1821 /* Returns true when LOOP contains vector phi nodes. */
|
|
|
1822
|
|
|
1823 static bool
|
|
|
1824 loop_has_vector_phi_nodes (struct loop *loop ATTRIBUTE_UNUSED)
|
|
|
1825 {
|
|
|
1826 unsigned i;
|
|
|
1827 basic_block *bbs = get_loop_body_in_dom_order (loop);
|
|
|
1828 gimple_stmt_iterator gsi;
|
|
|
1829 bool res = true;
|
|
|
1830
|
|
|
1831 for (i = 0; i < loop->num_nodes; i++)
|
|
|
1832 for (gsi = gsi_start_phis (bbs[i]); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
1833 if (TREE_CODE (TREE_TYPE (PHI_RESULT (gsi_stmt (gsi)))) == VECTOR_TYPE)
|
|
|
1834 goto end;
|
|
|
1835
|
|
|
1836 res = false;
|
|
|
1837 end:
|
|
|
1838 free (bbs);
|
|
|
1839 return res;
|
|
|
1840 }
|
|
|
1841
|
|
|
1842 /* Detect parallel loops and generate parallel code using libgomp
|
|
|
1843 primitives. Returns true if some loop was parallelized, false
|
|
|
1844 otherwise. */
|
|
|
1845
|
|
|
1846 bool
|
|
|
1847 parallelize_loops (void)
|
|
|
1848 {
|
|
|
1849 unsigned n_threads = flag_tree_parallelize_loops;
|
|
|
1850 bool changed = false;
|
|
|
1851 struct loop *loop;
|
|
|
1852 struct tree_niter_desc niter_desc;
|
|
|
1853 loop_iterator li;
|
|
|
1854 htab_t reduction_list;
|
|
|
1855
|
|
|
1856 /* Do not parallelize loops in the functions created by parallelization. */
|
|
|
1857 if (parallelized_function_p (cfun->decl))
|
|
|
1858 return false;
|
|
|
1859
|
|
|
1860 reduction_list = htab_create (10, reduction_info_hash,
|
|
|
1861 reduction_info_eq, free);
|
|
|
1862 init_stmt_vec_info_vec ();
|
|
|
1863
|
|
|
1864 FOR_EACH_LOOP (li, loop, 0)
|
|
|
1865 {
|
|
|
1866 htab_empty (reduction_list);
|
|
|
1867 if (/* Do not bother with loops in cold areas. */
|
|
|
1868 optimize_loop_nest_for_size_p (loop)
|
|
|
1869 /* Or loops that roll too little. */
|
|
|
1870 || expected_loop_iterations (loop) <= n_threads
|
|
|
1871 /* And of course, the loop must be parallelizable. */
|
|
|
1872 || !can_duplicate_loop_p (loop)
|
|
|
1873 || loop_has_blocks_with_irreducible_flag (loop)
|
|
|
1874 /* FIXME: the check for vector phi nodes could be removed. */
|
|
|
1875 || loop_has_vector_phi_nodes (loop)
|
|
|
1876 || !loop_parallel_p (loop, reduction_list, &niter_desc))
|
|
|
1877 continue;
|
|
|
1878
|
|
|
1879 changed = true;
|
|
|
1880 gen_parallel_loop (loop, reduction_list, n_threads, &niter_desc);
|
|
|
1881 verify_flow_info ();
|
|
|
1882 verify_dominators (CDI_DOMINATORS);
|
|
|
1883 verify_loop_structure ();
|
|
|
1884 verify_loop_closed_ssa ();
|
|
|
1885 }
|
|
|
1886
|
|
|
1887 free_stmt_vec_info_vec ();
|
|
|
1888 htab_delete (reduction_list);
|
|
|
1889 return changed;
|
|
|
1890 }
|
|
|
1891
|
|
|
1892 #include "gt-tree-parloops.h"
|
