2 Copyright (C) 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Georges-Andre Silber <Georges-Andre.Silber@ensmp.fr>
5 and Sebastian Pop <sebastian.pop@amd.com>.
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 3, or (at your option) any
14 GCC is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
23 /* This pass performs loop distribution: for example, the loop
40 This pass uses an RDG, Reduced Dependence Graph built on top of the
41 data dependence relations. The RDG is then topologically sorted to
42 obtain a map of information producers/consumers based on which it
43 generates the new loops. */
47 #include "coretypes.h"
50 #include "basic-block.h"
51 #include "tree-flow.h"
52 #include "tree-dump.h"
55 #include "tree-chrec.h"
56 #include "tree-data-ref.h"
57 #include "tree-scalar-evolution.h"
58 #include "tree-pass.h"
60 #include "langhooks.h"
61 #include "tree-vectorizer.h"
63 /* If bit I is not set, it means that this node represents an
64 operation that has already been performed, and that should not be
65 performed again. This is the subgraph of remaining important
66 computations that is passed to the DFS algorithm for avoiding to
67 include several times the same stores in different loops. */
68 static bitmap remaining_stmts;
70 /* A node of the RDG is marked in this bitmap when it has as a
71 predecessor a node that writes to memory. */
72 static bitmap upstream_mem_writes;
74 /* Update the PHI nodes of NEW_LOOP. NEW_LOOP is a duplicate of
78 update_phis_for_loop_copy (struct loop *orig_loop, struct loop *new_loop)
81 gimple_stmt_iterator si_new, si_orig;
82 edge orig_loop_latch = loop_latch_edge (orig_loop);
83 edge orig_entry_e = loop_preheader_edge (orig_loop);
84 edge new_loop_entry_e = loop_preheader_edge (new_loop);
86 /* Scan the phis in the headers of the old and new loops
87 (they are organized in exactly the same order). */
88 for (si_new = gsi_start_phis (new_loop->header),
89 si_orig = gsi_start_phis (orig_loop->header);
90 !gsi_end_p (si_new) && !gsi_end_p (si_orig);
91 gsi_next (&si_new), gsi_next (&si_orig))
94 source_location locus;
95 gimple phi_new = gsi_stmt (si_new);
96 gimple phi_orig = gsi_stmt (si_orig);
98 /* Add the first phi argument for the phi in NEW_LOOP (the one
99 associated with the entry of NEW_LOOP) */
100 def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_entry_e);
101 locus = gimple_phi_arg_location_from_edge (phi_orig, orig_entry_e);
102 add_phi_arg (phi_new, def, new_loop_entry_e, locus);
104 /* Add the second phi argument for the phi in NEW_LOOP (the one
105 associated with the latch of NEW_LOOP) */
106 def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
107 locus = gimple_phi_arg_location_from_edge (phi_orig, orig_loop_latch);
109 if (TREE_CODE (def) == SSA_NAME)
111 new_ssa_name = get_current_def (def);
114 /* This only happens if there are no definitions inside the
115 loop. Use the the invariant in the new loop as is. */
119 /* Could be an integer. */
122 add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop), locus);
126 /* Return a copy of LOOP placed before LOOP. */
129 copy_loop_before (struct loop *loop)
132 edge preheader = loop_preheader_edge (loop);
134 if (!single_exit (loop))
137 initialize_original_copy_tables ();
138 res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, preheader);
139 free_original_copy_tables ();
144 update_phis_for_loop_copy (loop, res);
145 rename_variables_in_loop (res);
150 /* Creates an empty basic block after LOOP. */
153 create_bb_after_loop (struct loop *loop)
155 edge exit = single_exit (loop);
163 /* Generate code for PARTITION from the code in LOOP. The loop is
164 copied when COPY_P is true. All the statements not flagged in the
165 PARTITION bitmap are removed from the loop or from its copy. The
166 statements are indexed in sequence inside a basic block, and the
167 basic blocks of a loop are taken in dom order. Returns true when
168 the code gen succeeded. */
171 generate_loops_for_partition (struct loop *loop, bitmap partition, bool copy_p)
174 gimple_stmt_iterator bsi;
179 loop = copy_loop_before (loop);
180 create_preheader (loop, CP_SIMPLE_PREHEADERS);
181 create_bb_after_loop (loop);
187 /* Remove stmts not in the PARTITION bitmap. The order in which we
188 visit the phi nodes and the statements is exactly as in
190 bbs = get_loop_body_in_dom_order (loop);
192 for (x = 0, i = 0; i < loop->num_nodes; i++)
194 basic_block bb = bbs[i];
196 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
197 if (!bitmap_bit_p (partition, x++))
199 gimple phi = gsi_stmt (bsi);
200 if (!is_gimple_reg (gimple_phi_result (phi)))
201 mark_virtual_phi_result_for_renaming (phi);
202 remove_phi_node (&bsi, true);
207 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi);)
209 gimple stmt = gsi_stmt (bsi);
210 if (gimple_code (gsi_stmt (bsi)) != GIMPLE_LABEL
211 && !bitmap_bit_p (partition, x++))
213 unlink_stmt_vdef (stmt);
214 gsi_remove (&bsi, true);
226 /* Build the size argument for a memset call. */
229 build_size_arg_loc (location_t loc, tree nb_iter, tree op,
230 gimple_seq *stmt_list)
233 tree x = size_binop_loc (loc, MULT_EXPR,
234 fold_convert_loc (loc, sizetype, nb_iter),
235 TYPE_SIZE_UNIT (TREE_TYPE (op)));
236 x = force_gimple_operand (x, &stmts, true, NULL);
237 gimple_seq_add_seq (stmt_list, stmts);
242 /* Generate a call to memset. Return true when the operation succeeded. */
245 generate_memset_zero (gimple stmt, tree op0, tree nb_iter,
246 gimple_stmt_iterator bsi)
248 tree addr_base, nb_bytes;
250 gimple_seq stmt_list = NULL, stmts;
253 struct data_reference *dr = XCNEW (struct data_reference);
254 location_t loc = gimple_location (stmt);
258 if (!dr_analyze_innermost (dr))
261 /* Test for a positive stride, iterating over every element. */
262 if (integer_zerop (size_binop (MINUS_EXPR,
263 fold_convert (sizetype, DR_STEP (dr)),
264 TYPE_SIZE_UNIT (TREE_TYPE (op0)))))
266 addr_base = fold_convert_loc (loc, sizetype,
267 size_binop_loc (loc, PLUS_EXPR,
270 addr_base = fold_build2_loc (loc, POINTER_PLUS_EXPR,
271 TREE_TYPE (DR_BASE_ADDRESS (dr)),
272 DR_BASE_ADDRESS (dr), addr_base);
274 nb_bytes = build_size_arg_loc (loc, nb_iter, op0, &stmt_list);
277 /* Test for a negative stride, iterating over every element. */
278 else if (integer_zerop (size_binop (PLUS_EXPR,
279 TYPE_SIZE_UNIT (TREE_TYPE (op0)),
280 fold_convert (sizetype, DR_STEP (dr)))))
282 nb_bytes = build_size_arg_loc (loc, nb_iter, op0, &stmt_list);
284 addr_base = size_binop_loc (loc, PLUS_EXPR, DR_OFFSET (dr), DR_INIT (dr));
285 addr_base = fold_convert_loc (loc, sizetype, addr_base);
286 addr_base = size_binop_loc (loc, MINUS_EXPR, addr_base,
287 fold_convert_loc (loc, sizetype, nb_bytes));
288 addr_base = size_binop_loc (loc, PLUS_EXPR, addr_base,
289 TYPE_SIZE_UNIT (TREE_TYPE (op0)));
290 addr_base = fold_build2_loc (loc, POINTER_PLUS_EXPR,
291 TREE_TYPE (DR_BASE_ADDRESS (dr)),
292 DR_BASE_ADDRESS (dr), addr_base);
297 mem = force_gimple_operand (addr_base, &stmts, true, NULL);
298 gimple_seq_add_seq (&stmt_list, stmts);
300 fn = build_fold_addr_expr (implicit_built_in_decls [BUILT_IN_MEMSET]);
301 fn_call = gimple_build_call (fn, 3, mem, integer_zero_node, nb_bytes);
302 gimple_seq_add_stmt (&stmt_list, fn_call);
303 gsi_insert_seq_after (&bsi, stmt_list, GSI_CONTINUE_LINKING);
306 if (dump_file && (dump_flags & TDF_DETAILS))
307 fprintf (dump_file, "generated memset zero\n");
314 /* Tries to generate a builtin function for the instructions of LOOP
315 pointed to by the bits set in PARTITION. Returns true when the
316 operation succeeded. */
319 generate_builtin (struct loop *loop, bitmap partition, bool copy_p)
326 gimple_stmt_iterator bsi;
327 tree nb_iter = number_of_exit_cond_executions (loop);
329 if (!nb_iter || nb_iter == chrec_dont_know)
332 bbs = get_loop_body_in_dom_order (loop);
334 for (i = 0; i < loop->num_nodes; i++)
336 basic_block bb = bbs[i];
338 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
341 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
343 gimple stmt = gsi_stmt (bsi);
345 if (bitmap_bit_p (partition, x++)
346 && is_gimple_assign (stmt)
347 && !is_gimple_reg (gimple_assign_lhs (stmt)))
349 /* Don't generate the builtins when there are more than
355 if (bb == loop->latch)
356 nb_iter = number_of_latch_executions (loop);
364 op0 = gimple_assign_lhs (write);
365 op1 = gimple_assign_rhs1 (write);
367 if (!(TREE_CODE (op0) == ARRAY_REF
368 || TREE_CODE (op0) == MEM_REF))
371 /* The new statements will be placed before LOOP. */
372 bsi = gsi_last_bb (loop_preheader_edge (loop)->src);
374 if (gimple_assign_rhs_code (write) == INTEGER_CST
375 && (integer_zerop (op1) || real_zerop (op1)))
376 res = generate_memset_zero (write, op0, nb_iter, bsi);
378 /* If this is the last partition for which we generate code, we have
379 to destroy the loop. */
382 unsigned nbbs = loop->num_nodes;
383 edge exit = single_exit (loop);
384 basic_block src = loop_preheader_edge (loop)->src, dest = exit->dest;
385 redirect_edge_pred (exit, src);
386 exit->flags &= ~(EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
387 exit->flags |= EDGE_FALLTHRU;
388 cancel_loop_tree (loop);
389 rescan_loop_exit (exit, false, true);
391 for (i = 0; i < nbbs; i++)
392 delete_basic_block (bbs[i]);
394 set_immediate_dominator (CDI_DOMINATORS, dest,
395 recompute_dominator (CDI_DOMINATORS, dest));
403 /* Generates code for PARTITION. For simple loops, this function can
404 generate a built-in. */
407 generate_code_for_partition (struct loop *loop, bitmap partition, bool copy_p)
409 if (generate_builtin (loop, partition, copy_p))
412 return generate_loops_for_partition (loop, partition, copy_p);
416 /* Returns true if the node V of RDG cannot be recomputed. */
419 rdg_cannot_recompute_vertex_p (struct graph *rdg, int v)
421 if (RDG_MEM_WRITE_STMT (rdg, v))
427 /* Returns true when the vertex V has already been generated in the
428 current partition (V is in PROCESSED), or when V belongs to another
429 partition and cannot be recomputed (V is not in REMAINING_STMTS). */
432 already_processed_vertex_p (bitmap processed, int v)
434 return (bitmap_bit_p (processed, v)
435 || !bitmap_bit_p (remaining_stmts, v));
438 /* Returns NULL when there is no anti-dependence among the successors
439 of vertex V, otherwise returns the edge with the anti-dep. */
441 static struct graph_edge *
442 has_anti_dependence (struct vertex *v)
444 struct graph_edge *e;
447 for (e = v->succ; e; e = e->succ_next)
448 if (RDGE_TYPE (e) == anti_dd)
454 /* Returns true when V has an anti-dependence edge among its successors. */
457 predecessor_has_mem_write (struct graph *rdg, struct vertex *v)
459 struct graph_edge *e;
462 for (e = v->pred; e; e = e->pred_next)
463 if (bitmap_bit_p (upstream_mem_writes, e->src)
464 /* Don't consider flow channels: a write to memory followed
465 by a read from memory. These channels allow the split of
466 the RDG in different partitions. */
467 && !RDG_MEM_WRITE_STMT (rdg, e->src))
473 /* Initializes the upstream_mem_writes bitmap following the
474 information from RDG. */
477 mark_nodes_having_upstream_mem_writes (struct graph *rdg)
480 bitmap seen = BITMAP_ALLOC (NULL);
482 for (v = rdg->n_vertices - 1; v >= 0; v--)
483 if (!bitmap_bit_p (seen, v))
486 VEC (int, heap) *nodes = VEC_alloc (int, heap, 3);
488 graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
490 FOR_EACH_VEC_ELT (int, nodes, i, x)
492 if (!bitmap_set_bit (seen, x))
495 if (RDG_MEM_WRITE_STMT (rdg, x)
496 || predecessor_has_mem_write (rdg, &(rdg->vertices[x]))
497 /* In anti dependences the read should occur before
498 the write, this is why both the read and the write
499 should be placed in the same partition. */
500 || has_anti_dependence (&(rdg->vertices[x])))
502 bitmap_set_bit (upstream_mem_writes, x);
506 VEC_free (int, heap, nodes);
510 /* Returns true when vertex u has a memory write node as a predecessor
514 has_upstream_mem_writes (int u)
516 return bitmap_bit_p (upstream_mem_writes, u);
519 static void rdg_flag_vertex_and_dependent (struct graph *, int, bitmap, bitmap,
522 /* Flag all the uses of U. */
525 rdg_flag_all_uses (struct graph *rdg, int u, bitmap partition, bitmap loops,
526 bitmap processed, bool *part_has_writes)
528 struct graph_edge *e;
530 for (e = rdg->vertices[u].succ; e; e = e->succ_next)
531 if (!bitmap_bit_p (processed, e->dest))
533 rdg_flag_vertex_and_dependent (rdg, e->dest, partition, loops,
534 processed, part_has_writes);
535 rdg_flag_all_uses (rdg, e->dest, partition, loops, processed,
540 /* Flag the uses of U stopping following the information from
541 upstream_mem_writes. */
544 rdg_flag_uses (struct graph *rdg, int u, bitmap partition, bitmap loops,
545 bitmap processed, bool *part_has_writes)
548 struct vertex *x = &(rdg->vertices[u]);
549 gimple stmt = RDGV_STMT (x);
550 struct graph_edge *anti_dep = has_anti_dependence (x);
552 /* Keep in the same partition the destination of an antidependence,
553 because this is a store to the exact same location. Putting this
554 in another partition is bad for cache locality. */
557 int v = anti_dep->dest;
559 if (!already_processed_vertex_p (processed, v))
560 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
561 processed, part_has_writes);
564 if (gimple_code (stmt) != GIMPLE_PHI)
566 if ((use_p = gimple_vuse_op (stmt)) != NULL_USE_OPERAND_P)
568 tree use = USE_FROM_PTR (use_p);
570 if (TREE_CODE (use) == SSA_NAME)
572 gimple def_stmt = SSA_NAME_DEF_STMT (use);
573 int v = rdg_vertex_for_stmt (rdg, def_stmt);
576 && !already_processed_vertex_p (processed, v))
577 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
578 processed, part_has_writes);
583 if (is_gimple_assign (stmt) && has_upstream_mem_writes (u))
585 tree op0 = gimple_assign_lhs (stmt);
587 /* Scalar channels don't have enough space for transmitting data
588 between tasks, unless we add more storage by privatizing. */
589 if (is_gimple_reg (op0))
592 imm_use_iterator iter;
594 FOR_EACH_IMM_USE_FAST (use_p, iter, op0)
596 int v = rdg_vertex_for_stmt (rdg, USE_STMT (use_p));
598 if (!already_processed_vertex_p (processed, v))
599 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
600 processed, part_has_writes);
606 /* Flag V from RDG as part of PARTITION, and also flag its loop number
610 rdg_flag_vertex (struct graph *rdg, int v, bitmap partition, bitmap loops,
611 bool *part_has_writes)
615 if (!bitmap_set_bit (partition, v))
618 loop = loop_containing_stmt (RDG_STMT (rdg, v));
619 bitmap_set_bit (loops, loop->num);
621 if (rdg_cannot_recompute_vertex_p (rdg, v))
623 *part_has_writes = true;
624 bitmap_clear_bit (remaining_stmts, v);
628 /* Flag in the bitmap PARTITION the vertex V and all its predecessors.
629 Also flag their loop number in LOOPS. */
632 rdg_flag_vertex_and_dependent (struct graph *rdg, int v, bitmap partition,
633 bitmap loops, bitmap processed,
634 bool *part_has_writes)
637 VEC (int, heap) *nodes = VEC_alloc (int, heap, 3);
640 bitmap_set_bit (processed, v);
641 rdg_flag_uses (rdg, v, partition, loops, processed, part_has_writes);
642 graphds_dfs (rdg, &v, 1, &nodes, false, remaining_stmts);
643 rdg_flag_vertex (rdg, v, partition, loops, part_has_writes);
645 FOR_EACH_VEC_ELT (int, nodes, i, x)
646 if (!already_processed_vertex_p (processed, x))
647 rdg_flag_vertex_and_dependent (rdg, x, partition, loops, processed,
650 VEC_free (int, heap, nodes);
653 /* Initialize CONDS with all the condition statements from the basic
657 collect_condition_stmts (struct loop *loop, VEC (gimple, heap) **conds)
661 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
663 FOR_EACH_VEC_ELT (edge, exits, i, e)
665 gimple cond = last_stmt (e->src);
668 VEC_safe_push (gimple, heap, *conds, cond);
671 VEC_free (edge, heap, exits);
674 /* Add to PARTITION all the exit condition statements for LOOPS
675 together with all their dependent statements determined from
679 rdg_flag_loop_exits (struct graph *rdg, bitmap loops, bitmap partition,
680 bitmap processed, bool *part_has_writes)
684 VEC (gimple, heap) *conds = VEC_alloc (gimple, heap, 3);
686 EXECUTE_IF_SET_IN_BITMAP (loops, 0, i, bi)
687 collect_condition_stmts (get_loop (i), &conds);
689 while (!VEC_empty (gimple, conds))
691 gimple cond = VEC_pop (gimple, conds);
692 int v = rdg_vertex_for_stmt (rdg, cond);
693 bitmap new_loops = BITMAP_ALLOC (NULL);
695 if (!already_processed_vertex_p (processed, v))
696 rdg_flag_vertex_and_dependent (rdg, v, partition, new_loops, processed,
699 EXECUTE_IF_SET_IN_BITMAP (new_loops, 0, i, bi)
700 if (bitmap_set_bit (loops, i))
701 collect_condition_stmts (get_loop (i), &conds);
703 BITMAP_FREE (new_loops);
707 /* Flag all the nodes of RDG containing memory accesses that could
708 potentially belong to arrays already accessed in the current
712 rdg_flag_similar_memory_accesses (struct graph *rdg, bitmap partition,
713 bitmap loops, bitmap processed,
714 VEC (int, heap) **other_stores)
720 struct graph_edge *e;
722 EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii)
723 if (RDG_MEM_WRITE_STMT (rdg, i)
724 || RDG_MEM_READS_STMT (rdg, i))
726 for (j = 0; j < rdg->n_vertices; j++)
727 if (!bitmap_bit_p (processed, j)
728 && (RDG_MEM_WRITE_STMT (rdg, j)
729 || RDG_MEM_READS_STMT (rdg, j))
730 && rdg_has_similar_memory_accesses (rdg, i, j))
732 /* Flag first the node J itself, and all the nodes that
733 are needed to compute J. */
734 rdg_flag_vertex_and_dependent (rdg, j, partition, loops,
737 /* When J is a read, we want to coalesce in the same
738 PARTITION all the nodes that are using J: this is
739 needed for better cache locality. */
740 rdg_flag_all_uses (rdg, j, partition, loops, processed, &foo);
742 /* Remove from OTHER_STORES the vertex that we flagged. */
743 if (RDG_MEM_WRITE_STMT (rdg, j))
744 FOR_EACH_VEC_ELT (int, *other_stores, k, kk)
747 VEC_unordered_remove (int, *other_stores, k);
752 /* If the node I has two uses, then keep these together in the
754 for (n = 0, e = rdg->vertices[i].succ; e; e = e->succ_next, n++);
757 rdg_flag_all_uses (rdg, i, partition, loops, processed, &foo);
761 /* Returns a bitmap in which all the statements needed for computing
762 the strongly connected component C of the RDG are flagged, also
763 including the loop exit conditions. */
766 build_rdg_partition_for_component (struct graph *rdg, rdgc c,
767 bool *part_has_writes,
768 VEC (int, heap) **other_stores)
771 bitmap partition = BITMAP_ALLOC (NULL);
772 bitmap loops = BITMAP_ALLOC (NULL);
773 bitmap processed = BITMAP_ALLOC (NULL);
775 FOR_EACH_VEC_ELT (int, c->vertices, i, v)
776 if (!already_processed_vertex_p (processed, v))
777 rdg_flag_vertex_and_dependent (rdg, v, partition, loops, processed,
780 /* Also iterate on the array of stores not in the starting vertices,
781 and determine those vertices that have some memory affinity with
782 the current nodes in the component: these are stores to the same
783 arrays, i.e. we're taking care of cache locality. */
784 rdg_flag_similar_memory_accesses (rdg, partition, loops, processed,
787 rdg_flag_loop_exits (rdg, loops, partition, processed, part_has_writes);
789 BITMAP_FREE (processed);
794 /* Free memory for COMPONENTS. */
797 free_rdg_components (VEC (rdgc, heap) *components)
802 FOR_EACH_VEC_ELT (rdgc, components, i, x)
804 VEC_free (int, heap, x->vertices);
809 /* Build the COMPONENTS vector with the strongly connected components
810 of RDG in which the STARTING_VERTICES occur. */
813 rdg_build_components (struct graph *rdg, VEC (int, heap) *starting_vertices,
814 VEC (rdgc, heap) **components)
817 bitmap saved_components = BITMAP_ALLOC (NULL);
818 int n_components = graphds_scc (rdg, NULL);
819 VEC (int, heap) **all_components = XNEWVEC (VEC (int, heap) *, n_components);
821 for (i = 0; i < n_components; i++)
822 all_components[i] = VEC_alloc (int, heap, 3);
824 for (i = 0; i < rdg->n_vertices; i++)
825 VEC_safe_push (int, heap, all_components[rdg->vertices[i].component], i);
827 FOR_EACH_VEC_ELT (int, starting_vertices, i, v)
829 int c = rdg->vertices[v].component;
831 if (bitmap_set_bit (saved_components, c))
833 rdgc x = XCNEW (struct rdg_component);
835 x->vertices = all_components[c];
837 VEC_safe_push (rdgc, heap, *components, x);
841 for (i = 0; i < n_components; i++)
842 if (!bitmap_bit_p (saved_components, i))
843 VEC_free (int, heap, all_components[i]);
845 free (all_components);
846 BITMAP_FREE (saved_components);
849 /* Aggregate several components into a useful partition that is
850 registered in the PARTITIONS vector. Partitions will be
851 distributed in different loops. */
854 rdg_build_partitions (struct graph *rdg, VEC (rdgc, heap) *components,
855 VEC (int, heap) **other_stores,
856 VEC (bitmap, heap) **partitions, bitmap processed)
860 bitmap partition = BITMAP_ALLOC (NULL);
862 FOR_EACH_VEC_ELT (rdgc, components, i, x)
865 bool part_has_writes = false;
866 int v = VEC_index (int, x->vertices, 0);
868 if (bitmap_bit_p (processed, v))
871 np = build_rdg_partition_for_component (rdg, x, &part_has_writes,
873 bitmap_ior_into (partition, np);
874 bitmap_ior_into (processed, np);
879 if (dump_file && (dump_flags & TDF_DETAILS))
881 fprintf (dump_file, "ldist useful partition:\n");
882 dump_bitmap (dump_file, partition);
885 VEC_safe_push (bitmap, heap, *partitions, partition);
886 partition = BITMAP_ALLOC (NULL);
890 /* Add the nodes from the RDG that were not marked as processed, and
891 that are used outside the current loop. These are scalar
892 computations that are not yet part of previous partitions. */
893 for (i = 0; i < rdg->n_vertices; i++)
894 if (!bitmap_bit_p (processed, i)
895 && rdg_defs_used_in_other_loops_p (rdg, i))
896 VEC_safe_push (int, heap, *other_stores, i);
898 /* If there are still statements left in the OTHER_STORES array,
899 create other components and partitions with these stores and
900 their dependences. */
901 if (VEC_length (int, *other_stores) > 0)
903 VEC (rdgc, heap) *comps = VEC_alloc (rdgc, heap, 3);
904 VEC (int, heap) *foo = VEC_alloc (int, heap, 3);
906 rdg_build_components (rdg, *other_stores, &comps);
907 rdg_build_partitions (rdg, comps, &foo, partitions, processed);
909 VEC_free (int, heap, foo);
910 free_rdg_components (comps);
913 /* If there is something left in the last partition, save it. */
914 if (bitmap_count_bits (partition) > 0)
915 VEC_safe_push (bitmap, heap, *partitions, partition);
917 BITMAP_FREE (partition);
920 /* Dump to FILE the PARTITIONS. */
923 dump_rdg_partitions (FILE *file, VEC (bitmap, heap) *partitions)
928 FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
929 debug_bitmap_file (file, partition);
932 /* Debug PARTITIONS. */
933 extern void debug_rdg_partitions (VEC (bitmap, heap) *);
936 debug_rdg_partitions (VEC (bitmap, heap) *partitions)
938 dump_rdg_partitions (stderr, partitions);
941 /* Returns the number of read and write operations in the RDG. */
944 number_of_rw_in_rdg (struct graph *rdg)
948 for (i = 0; i < rdg->n_vertices; i++)
950 if (RDG_MEM_WRITE_STMT (rdg, i))
953 if (RDG_MEM_READS_STMT (rdg, i))
960 /* Returns the number of read and write operations in a PARTITION of
964 number_of_rw_in_partition (struct graph *rdg, bitmap partition)
970 EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii)
972 if (RDG_MEM_WRITE_STMT (rdg, i))
975 if (RDG_MEM_READS_STMT (rdg, i))
982 /* Returns true when one of the PARTITIONS contains all the read or
983 write operations of RDG. */
986 partition_contains_all_rw (struct graph *rdg, VEC (bitmap, heap) *partitions)
990 int nrw = number_of_rw_in_rdg (rdg);
992 FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
993 if (nrw == number_of_rw_in_partition (rdg, partition))
999 /* Generate code from STARTING_VERTICES in RDG. Returns the number of
1000 distributed loops. */
1003 ldist_gen (struct loop *loop, struct graph *rdg,
1004 VEC (int, heap) *starting_vertices)
1007 VEC (rdgc, heap) *components = VEC_alloc (rdgc, heap, 3);
1008 VEC (bitmap, heap) *partitions = VEC_alloc (bitmap, heap, 3);
1009 VEC (int, heap) *other_stores = VEC_alloc (int, heap, 3);
1010 bitmap partition, processed = BITMAP_ALLOC (NULL);
1012 remaining_stmts = BITMAP_ALLOC (NULL);
1013 upstream_mem_writes = BITMAP_ALLOC (NULL);
1015 for (i = 0; i < rdg->n_vertices; i++)
1017 bitmap_set_bit (remaining_stmts, i);
1019 /* Save in OTHER_STORES all the memory writes that are not in
1020 STARTING_VERTICES. */
1021 if (RDG_MEM_WRITE_STMT (rdg, i))
1027 FOR_EACH_VEC_ELT (int, starting_vertices, j, v)
1035 VEC_safe_push (int, heap, other_stores, i);
1039 mark_nodes_having_upstream_mem_writes (rdg);
1040 rdg_build_components (rdg, starting_vertices, &components);
1041 rdg_build_partitions (rdg, components, &other_stores, &partitions,
1043 BITMAP_FREE (processed);
1044 nbp = VEC_length (bitmap, partitions);
1047 || partition_contains_all_rw (rdg, partitions))
1050 if (dump_file && (dump_flags & TDF_DETAILS))
1051 dump_rdg_partitions (dump_file, partitions);
1053 FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
1054 if (!generate_code_for_partition (loop, partition, i < nbp - 1))
1057 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1058 update_ssa (TODO_update_ssa_only_virtuals | TODO_update_ssa);
1062 BITMAP_FREE (remaining_stmts);
1063 BITMAP_FREE (upstream_mem_writes);
1065 FOR_EACH_VEC_ELT (bitmap, partitions, i, partition)
1066 BITMAP_FREE (partition);
1068 VEC_free (int, heap, other_stores);
1069 VEC_free (bitmap, heap, partitions);
1070 free_rdg_components (components);
1074 /* Distributes the code from LOOP in such a way that producer
1075 statements are placed before consumer statements. When STMTS is
1076 NULL, performs the maximal distribution, if STMTS is not NULL,
1077 tries to separate only these statements from the LOOP's body.
1078 Returns the number of distributed loops. */
1081 distribute_loop (struct loop *loop, VEC (gimple, heap) *stmts)
1087 VEC (int, heap) *vertices;
1089 if (loop->num_nodes > 2)
1091 if (dump_file && (dump_flags & TDF_DETAILS))
1093 "FIXME: Loop %d not distributed: it has more than two basic blocks.\n",
1099 rdg = build_rdg (loop);
1103 if (dump_file && (dump_flags & TDF_DETAILS))
1105 "FIXME: Loop %d not distributed: failed to build the RDG.\n",
1111 vertices = VEC_alloc (int, heap, 3);
1113 if (dump_file && (dump_flags & TDF_DETAILS))
1114 dump_rdg (dump_file, rdg);
1116 FOR_EACH_VEC_ELT (gimple, stmts, i, s)
1118 int v = rdg_vertex_for_stmt (rdg, s);
1122 VEC_safe_push (int, heap, vertices, v);
1124 if (dump_file && (dump_flags & TDF_DETAILS))
1126 "ldist asked to generate code for vertex %d\n", v);
1130 res = ldist_gen (loop, rdg, vertices);
1131 VEC_free (int, heap, vertices);
1137 /* Distribute all loops in the current function. */
1140 tree_loop_distribution (void)
1144 int nb_generated_loops = 0;
1146 FOR_EACH_LOOP (li, loop, 0)
1148 VEC (gimple, heap) *work_list = NULL;
1150 /* If the loop doesn't have a single exit we will fail anyway,
1151 so do that early. */
1152 if (!single_exit (loop))
1155 /* If both flag_tree_loop_distribute_patterns and
1156 flag_tree_loop_distribution are set, then only
1157 distribute_patterns is executed. */
1158 if (flag_tree_loop_distribute_patterns)
1160 /* With the following working list, we're asking
1161 distribute_loop to separate from the rest of the loop the
1162 stores of the form "A[i] = 0". */
1163 stores_zero_from_loop (loop, &work_list);
1165 /* Do nothing if there are no patterns to be distributed. */
1166 if (VEC_length (gimple, work_list) > 0)
1167 nb_generated_loops = distribute_loop (loop, work_list);
1169 else if (flag_tree_loop_distribution)
1171 /* With the following working list, we're asking
1172 distribute_loop to separate the stores of the loop: when
1173 dependences allow, it will end on having one store per
1175 stores_from_loop (loop, &work_list);
1177 /* A simple heuristic for cache locality is to not split
1178 stores to the same array. Without this call, an unrolled
1179 loop would be split into as many loops as unroll factor,
1180 each loop storing in the same array. */
1181 remove_similar_memory_refs (&work_list);
1183 nb_generated_loops = distribute_loop (loop, work_list);
1186 if (dump_file && (dump_flags & TDF_DETAILS))
1188 if (nb_generated_loops > 1)
1189 fprintf (dump_file, "Loop %d distributed: split to %d loops.\n",
1190 loop->num, nb_generated_loops);
1192 fprintf (dump_file, "Loop %d is the same.\n", loop->num);
1195 verify_loop_structure ();
1197 VEC_free (gimple, heap, work_list);
1204 gate_tree_loop_distribution (void)
1206 return flag_tree_loop_distribution
1207 || flag_tree_loop_distribute_patterns;
1210 struct gimple_opt_pass pass_loop_distribution =
1215 gate_tree_loop_distribution, /* gate */
1216 tree_loop_distribution, /* execute */
1219 0, /* static_pass_number */
1220 TV_TREE_LOOP_DISTRIBUTION, /* tv_id */
1221 PROP_cfg | PROP_ssa, /* properties_required */
1222 0, /* properties_provided */
1223 0, /* properties_destroyed */
1224 0, /* todo_flags_start */
1225 TODO_dump_func /* todo_flags_finish */