Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-parloops.c @ 55:77e2b8dfacca gcc-4.4.5

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