2 Copyright (C) 2006, 2007, 2008 Free Software Foundation, Inc.
3 Contributed by Georges-Andre Silber <Georges-Andre.Silber@ensmp.fr>
4 and Sebastian Pop <sebastian.pop@amd.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 3, or (at your option) any
13 GCC is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This pass performs loop distribution: for example, the loop
39 This pass uses an RDG, Reduced Dependence Graph built on top of the
40 data dependence relations. The RDG is then topologically sorted to
41 obtain a map of information producers/consumers based on which it
42 generates the new loops. */
46 #include "coretypes.h"
53 #include "basic-block.h"
54 #include "diagnostic.h"
55 #include "tree-flow.h"
56 #include "tree-dump.h"
61 #include "tree-chrec.h"
62 #include "tree-data-ref.h"
63 #include "tree-scalar-evolution.h"
64 #include "tree-pass.h"
66 #include "langhooks.h"
67 #include "tree-vectorizer.h"
69 /* If bit I is not set, it means that this node represents an
70 operation that has already been performed, and that should not be
71 performed again. This is the subgraph of remaining important
72 computations that is passed to the DFS algorithm for avoiding to
73 include several times the same stores in different loops. */
74 static bitmap remaining_stmts;
76 /* A node of the RDG is marked in this bitmap when it has as a
77 predecessor a node that writes to memory. */
78 static bitmap upstream_mem_writes;
80 /* Update the PHI nodes of NEW_LOOP. NEW_LOOP is a duplicate of
84 update_phis_for_loop_copy (struct loop *orig_loop, struct loop *new_loop)
87 gimple_stmt_iterator si_new, si_orig;
88 edge orig_loop_latch = loop_latch_edge (orig_loop);
89 edge orig_entry_e = loop_preheader_edge (orig_loop);
90 edge new_loop_entry_e = loop_preheader_edge (new_loop);
92 /* Scan the phis in the headers of the old and new loops
93 (they are organized in exactly the same order). */
94 for (si_new = gsi_start_phis (new_loop->header),
95 si_orig = gsi_start_phis (orig_loop->header);
96 !gsi_end_p (si_new) && !gsi_end_p (si_orig);
97 gsi_next (&si_new), gsi_next (&si_orig))
100 gimple phi_new = gsi_stmt (si_new);
101 gimple phi_orig = gsi_stmt (si_orig);
103 /* Add the first phi argument for the phi in NEW_LOOP (the one
104 associated with the entry of NEW_LOOP) */
105 def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_entry_e);
106 add_phi_arg (phi_new, def, new_loop_entry_e);
108 /* Add the second phi argument for the phi in NEW_LOOP (the one
109 associated with the latch of NEW_LOOP) */
110 def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
112 if (TREE_CODE (def) == SSA_NAME)
114 new_ssa_name = get_current_def (def);
117 /* This only happens if there are no definitions inside the
118 loop. Use the phi_result in this case. */
119 new_ssa_name = PHI_RESULT (phi_new);
122 /* Could be an integer. */
125 add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop));
129 /* Return a copy of LOOP placed before LOOP. */
132 copy_loop_before (struct loop *loop)
135 edge preheader = loop_preheader_edge (loop);
137 if (!single_exit (loop))
140 initialize_original_copy_tables ();
141 res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, preheader);
142 free_original_copy_tables ();
147 update_phis_for_loop_copy (loop, res);
148 rename_variables_in_loop (res);
153 /* Creates an empty basic block after LOOP. */
156 create_bb_after_loop (struct loop *loop)
158 edge exit = single_exit (loop);
166 /* Generate code for PARTITION from the code in LOOP. The loop is
167 copied when COPY_P is true. All the statements not flagged in the
168 PARTITION bitmap are removed from the loop or from its copy. The
169 statements are indexed in sequence inside a basic block, and the
170 basic blocks of a loop are taken in dom order. Returns true when
171 the code gen succeeded. */
174 generate_loops_for_partition (struct loop *loop, bitmap partition, bool copy_p)
177 gimple_stmt_iterator bsi;
182 loop = copy_loop_before (loop);
183 create_preheader (loop, CP_SIMPLE_PREHEADERS);
184 create_bb_after_loop (loop);
190 /* Remove stmts not in the PARTITION bitmap. The order in which we
191 visit the phi nodes and the statements is exactly as in
193 bbs = get_loop_body_in_dom_order (loop);
195 for (x = 0, i = 0; i < loop->num_nodes; i++)
197 basic_block bb = bbs[i];
199 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
200 if (!bitmap_bit_p (partition, x++))
201 remove_phi_node (&bsi, true);
205 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi);)
206 if (gimple_code (gsi_stmt (bsi)) != GIMPLE_LABEL
207 && !bitmap_bit_p (partition, x++))
208 gsi_remove (&bsi, false);
212 mark_virtual_ops_in_bb (bb);
219 /* Generate a call to memset. Return true when the operation succeeded. */
222 generate_memset_zero (gimple stmt, tree op0, tree nb_iter,
223 gimple_stmt_iterator bsi)
225 tree t, nb_bytes, addr_base;
227 gimple_seq stmts = NULL, stmt_list = NULL;
229 tree mem, fndecl, fntype, fn;
230 gimple_stmt_iterator i;
232 struct data_reference *dr = XCNEW (struct data_reference);
234 nb_bytes = fold_build2 (MULT_EXPR, TREE_TYPE (nb_iter),
235 nb_iter, TYPE_SIZE_UNIT (TREE_TYPE (op0)));
236 nb_bytes = force_gimple_operand (nb_bytes, &stmts, true, NULL);
237 gimple_seq_add_seq (&stmt_list, stmts);
241 dr_analyze_innermost (dr);
243 /* Test for a positive stride, iterating over every element. */
244 if (integer_zerop (fold_build2 (MINUS_EXPR, integer_type_node, DR_STEP (dr),
245 TYPE_SIZE_UNIT (TREE_TYPE (op0)))))
246 addr_base = fold_build2 (PLUS_EXPR, TREE_TYPE (DR_BASE_ADDRESS (dr)),
247 DR_BASE_ADDRESS (dr),
248 size_binop (PLUS_EXPR,
249 DR_OFFSET (dr), DR_INIT (dr)));
251 /* Test for a negative stride, iterating over every element. */
252 else if (integer_zerop (fold_build2 (PLUS_EXPR, integer_type_node,
253 TYPE_SIZE_UNIT (TREE_TYPE (op0)),
256 addr_base = size_binop (PLUS_EXPR, DR_OFFSET (dr), DR_INIT (dr));
257 addr_base = fold_build2 (MINUS_EXPR, sizetype, addr_base, nb_bytes);
258 addr_base = force_gimple_operand (addr_base, &stmts, true, NULL);
259 gimple_seq_add_seq (&stmt_list, stmts);
261 addr_base = fold_build2 (POINTER_PLUS_EXPR,
262 TREE_TYPE (DR_BASE_ADDRESS (dr)),
263 DR_BASE_ADDRESS (dr), addr_base);
268 mem = force_gimple_operand (addr_base, &stmts, true, NULL);
269 gimple_seq_add_seq (&stmt_list, stmts);
271 fndecl = implicit_built_in_decls [BUILT_IN_MEMSET];
272 fntype = TREE_TYPE (fndecl);
273 fn = build1 (ADDR_EXPR, build_pointer_type (fntype), fndecl);
275 fn_call = gimple_build_call (fn, 3, mem, integer_zero_node, nb_bytes);
276 gimple_seq_add_stmt (&stmt_list, fn_call);
278 for (i = gsi_start (stmt_list); !gsi_end_p (i); gsi_next (&i))
280 gimple s = gsi_stmt (i);
281 update_stmt_if_modified (s);
283 FOR_EACH_SSA_TREE_OPERAND (t, s, iter, SSA_OP_VIRTUAL_DEFS)
285 if (TREE_CODE (t) == SSA_NAME)
286 t = SSA_NAME_VAR (t);
287 mark_sym_for_renaming (t);
291 /* Mark also the uses of the VDEFS of STMT to be renamed. */
292 FOR_EACH_SSA_TREE_OPERAND (t, stmt, iter, SSA_OP_VIRTUAL_DEFS)
294 if (TREE_CODE (t) == SSA_NAME)
297 imm_use_iterator imm_iter;
299 FOR_EACH_IMM_USE_STMT (s, imm_iter, t)
302 t = SSA_NAME_VAR (t);
304 mark_sym_for_renaming (t);
307 gsi_insert_seq_after (&bsi, stmt_list, GSI_CONTINUE_LINKING);
310 if (dump_file && (dump_flags & TDF_DETAILS))
311 fprintf (dump_file, "generated memset zero\n");
318 /* Tries to generate a builtin function for the instructions of LOOP
319 pointed to by the bits set in PARTITION. Returns true when the
320 operation succeeded. */
323 generate_builtin (struct loop *loop, bitmap partition, bool copy_p)
330 gimple_stmt_iterator bsi;
331 tree nb_iter = number_of_exit_cond_executions (loop);
333 if (!nb_iter || nb_iter == chrec_dont_know)
336 bbs = get_loop_body_in_dom_order (loop);
338 for (i = 0; i < loop->num_nodes; i++)
340 basic_block bb = bbs[i];
342 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
345 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
347 gimple stmt = gsi_stmt (bsi);
349 if (bitmap_bit_p (partition, x++)
350 && is_gimple_assign (stmt)
351 && !is_gimple_reg (gimple_assign_lhs (stmt)))
353 /* Don't generate the builtins when there are more than
366 op0 = gimple_assign_lhs (write);
367 op1 = gimple_assign_rhs1 (write);
369 if (!(TREE_CODE (op0) == ARRAY_REF
370 || TREE_CODE (op0) == INDIRECT_REF))
373 /* The new statements will be placed before LOOP. */
374 bsi = gsi_last_bb (loop_preheader_edge (loop)->src);
376 if (gimple_assign_rhs_code (write) == INTEGER_CST
377 && (integer_zerop (op1) || real_zerop (op1)))
378 res = generate_memset_zero (write, op0, nb_iter, bsi);
380 /* If this is the last partition for which we generate code, we have
381 to destroy the loop. */
384 unsigned nbbs = loop->num_nodes;
385 basic_block src = loop_preheader_edge (loop)->src;
386 basic_block dest = single_exit (loop)->dest;
387 make_edge (src, dest, EDGE_FALLTHRU);
388 set_immediate_dominator (CDI_DOMINATORS, dest, src);
389 cancel_loop_tree (loop);
391 for (i = 0; i < nbbs; i++)
392 delete_basic_block (bbs[i]);
400 /* Generates code for PARTITION. For simple loops, this function can
401 generate a built-in. */
404 generate_code_for_partition (struct loop *loop, bitmap partition, bool copy_p)
406 if (generate_builtin (loop, partition, copy_p))
409 return generate_loops_for_partition (loop, partition, copy_p);
413 /* Returns true if the node V of RDG cannot be recomputed. */
416 rdg_cannot_recompute_vertex_p (struct graph *rdg, int v)
418 if (RDG_MEM_WRITE_STMT (rdg, v))
424 /* Returns true when the vertex V has already been generated in the
425 current partition (V is in PROCESSED), or when V belongs to another
426 partition and cannot be recomputed (V is not in REMAINING_STMTS). */
429 already_processed_vertex_p (bitmap processed, int v)
431 return (bitmap_bit_p (processed, v)
432 || !bitmap_bit_p (remaining_stmts, v));
435 /* Returns NULL when there is no anti-dependence among the successors
436 of vertex V, otherwise returns the edge with the anti-dep. */
438 static struct graph_edge *
439 has_anti_dependence (struct vertex *v)
441 struct graph_edge *e;
444 for (e = v->succ; e; e = e->succ_next)
445 if (RDGE_TYPE (e) == anti_dd)
451 /* Returns true when V has an anti-dependence edge among its successors. */
454 predecessor_has_mem_write (struct graph *rdg, struct vertex *v)
456 struct graph_edge *e;
459 for (e = v->pred; e; e = e->pred_next)
460 if (bitmap_bit_p (upstream_mem_writes, e->src)
461 /* Don't consider flow channels: a write to memory followed
462 by a read from memory. These channels allow the split of
463 the RDG in different partitions. */
464 && !RDG_MEM_WRITE_STMT (rdg, e->src))
470 /* Initializes the upstream_mem_writes bitmap following the
471 information from RDG. */
474 mark_nodes_having_upstream_mem_writes (struct graph *rdg)
477 bitmap seen = BITMAP_ALLOC (NULL);
479 for (v = rdg->n_vertices - 1; v >= 0; v--)
480 if (!bitmap_bit_p (seen, v))
483 VEC (int, heap) *nodes = VEC_alloc (int, heap, 3);
484 bool has_upstream_mem_write_p = false;
486 graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
488 for (i = 0; VEC_iterate (int, nodes, i, x); i++)
490 if (bitmap_bit_p (seen, x))
493 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 has_upstream_mem_write_p = true;
503 bitmap_set_bit (upstream_mem_writes, x);
507 VEC_free (int, heap, nodes);
511 /* Returns true when vertex u has a memory write node as a predecessor
515 has_upstream_mem_writes (int u)
517 return bitmap_bit_p (upstream_mem_writes, u);
520 static void rdg_flag_vertex_and_dependent (struct graph *, int, bitmap, bitmap,
523 /* Flag all the uses of U. */
526 rdg_flag_all_uses (struct graph *rdg, int u, bitmap partition, bitmap loops,
527 bitmap processed, bool *part_has_writes)
529 struct graph_edge *e;
531 for (e = rdg->vertices[u].succ; e; e = e->succ_next)
532 if (!bitmap_bit_p (processed, e->dest))
534 rdg_flag_vertex_and_dependent (rdg, e->dest, partition, loops,
535 processed, part_has_writes);
536 rdg_flag_all_uses (rdg, e->dest, partition, loops, processed,
541 /* Flag the uses of U stopping following the information from
542 upstream_mem_writes. */
545 rdg_flag_uses (struct graph *rdg, int u, bitmap partition, bitmap loops,
546 bitmap processed, bool *part_has_writes)
550 struct vertex *x = &(rdg->vertices[u]);
551 gimple stmt = RDGV_STMT (x);
552 struct graph_edge *anti_dep = has_anti_dependence (x);
554 /* Keep in the same partition the destination of an antidependence,
555 because this is a store to the exact same location. Putting this
556 in another partition is bad for cache locality. */
559 int v = anti_dep->dest;
561 if (!already_processed_vertex_p (processed, v))
562 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
563 processed, part_has_writes);
566 if (gimple_code (stmt) != GIMPLE_PHI)
568 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_VIRTUAL_USES)
570 tree use = USE_FROM_PTR (use_p);
572 if (TREE_CODE (use) == SSA_NAME)
574 gimple def_stmt = SSA_NAME_DEF_STMT (use);
575 int v = rdg_vertex_for_stmt (rdg, def_stmt);
578 && !already_processed_vertex_p (processed, v))
579 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
580 processed, part_has_writes);
585 if (is_gimple_assign (stmt) && has_upstream_mem_writes (u))
587 tree op0 = gimple_assign_lhs (stmt);
589 /* Scalar channels don't have enough space for transmitting data
590 between tasks, unless we add more storage by privatizing. */
591 if (is_gimple_reg (op0))
594 imm_use_iterator iter;
596 FOR_EACH_IMM_USE_FAST (use_p, iter, op0)
598 int v = rdg_vertex_for_stmt (rdg, USE_STMT (use_p));
600 if (!already_processed_vertex_p (processed, v))
601 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
602 processed, part_has_writes);
608 /* Flag V from RDG as part of PARTITION, and also flag its loop number
612 rdg_flag_vertex (struct graph *rdg, int v, bitmap partition, bitmap loops,
613 bool *part_has_writes)
617 if (bitmap_bit_p (partition, v))
620 loop = loop_containing_stmt (RDG_STMT (rdg, v));
621 bitmap_set_bit (loops, loop->num);
622 bitmap_set_bit (partition, v);
624 if (rdg_cannot_recompute_vertex_p (rdg, v))
626 *part_has_writes = true;
627 bitmap_clear_bit (remaining_stmts, v);
631 /* Flag in the bitmap PARTITION the vertex V and all its predecessors.
632 Also flag their loop number in LOOPS. */
635 rdg_flag_vertex_and_dependent (struct graph *rdg, int v, bitmap partition,
636 bitmap loops, bitmap processed,
637 bool *part_has_writes)
640 VEC (int, heap) *nodes = VEC_alloc (int, heap, 3);
643 bitmap_set_bit (processed, v);
644 rdg_flag_uses (rdg, v, partition, loops, processed, part_has_writes);
645 graphds_dfs (rdg, &v, 1, &nodes, false, remaining_stmts);
646 rdg_flag_vertex (rdg, v, partition, loops, part_has_writes);
648 for (i = 0; VEC_iterate (int, nodes, i, x); i++)
649 if (!already_processed_vertex_p (processed, x))
650 rdg_flag_vertex_and_dependent (rdg, x, partition, loops, processed,
653 VEC_free (int, heap, nodes);
656 /* Initialize CONDS with all the condition statements from the basic
660 collect_condition_stmts (struct loop *loop, VEC (gimple, heap) **conds)
664 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
666 for (i = 0; VEC_iterate (edge, exits, i, e); i++)
668 gimple cond = last_stmt (e->src);
671 VEC_safe_push (gimple, heap, *conds, cond);
674 VEC_free (edge, heap, exits);
677 /* Add to PARTITION all the exit condition statements for LOOPS
678 together with all their dependent statements determined from
682 rdg_flag_loop_exits (struct graph *rdg, bitmap loops, bitmap partition,
683 bitmap processed, bool *part_has_writes)
687 VEC (gimple, heap) *conds = VEC_alloc (gimple, heap, 3);
689 EXECUTE_IF_SET_IN_BITMAP (loops, 0, i, bi)
690 collect_condition_stmts (get_loop (i), &conds);
692 while (!VEC_empty (gimple, conds))
694 gimple cond = VEC_pop (gimple, conds);
695 int v = rdg_vertex_for_stmt (rdg, cond);
696 bitmap new_loops = BITMAP_ALLOC (NULL);
698 if (!already_processed_vertex_p (processed, v))
699 rdg_flag_vertex_and_dependent (rdg, v, partition, new_loops, processed,
702 EXECUTE_IF_SET_IN_BITMAP (new_loops, 0, i, bi)
703 if (!bitmap_bit_p (loops, i))
705 bitmap_set_bit (loops, i);
706 collect_condition_stmts (get_loop (i), &conds);
709 BITMAP_FREE (new_loops);
713 /* Flag all the nodes of RDG containing memory accesses that could
714 potentially belong to arrays already accessed in the current
718 rdg_flag_similar_memory_accesses (struct graph *rdg, bitmap partition,
719 bitmap loops, bitmap processed,
720 VEC (int, heap) **other_stores)
726 struct graph_edge *e;
728 EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii)
729 if (RDG_MEM_WRITE_STMT (rdg, i)
730 || RDG_MEM_READS_STMT (rdg, i))
732 for (j = 0; j < rdg->n_vertices; j++)
733 if (!bitmap_bit_p (processed, j)
734 && (RDG_MEM_WRITE_STMT (rdg, j)
735 || RDG_MEM_READS_STMT (rdg, j))
736 && rdg_has_similar_memory_accesses (rdg, i, j))
738 /* Flag first the node J itself, and all the nodes that
739 are needed to compute J. */
740 rdg_flag_vertex_and_dependent (rdg, j, partition, loops,
743 /* When J is a read, we want to coalesce in the same
744 PARTITION all the nodes that are using J: this is
745 needed for better cache locality. */
746 rdg_flag_all_uses (rdg, j, partition, loops, processed, &foo);
748 /* Remove from OTHER_STORES the vertex that we flagged. */
749 if (RDG_MEM_WRITE_STMT (rdg, j))
750 for (k = 0; VEC_iterate (int, *other_stores, k, kk); k++)
753 VEC_unordered_remove (int, *other_stores, k);
758 /* If the node I has two uses, then keep these together in the
760 for (n = 0, e = rdg->vertices[i].succ; e; e = e->succ_next, n++);
763 rdg_flag_all_uses (rdg, i, partition, loops, processed, &foo);
767 /* Returns a bitmap in which all the statements needed for computing
768 the strongly connected component C of the RDG are flagged, also
769 including the loop exit conditions. */
772 build_rdg_partition_for_component (struct graph *rdg, rdgc c,
773 bool *part_has_writes,
774 VEC (int, heap) **other_stores)
777 bitmap partition = BITMAP_ALLOC (NULL);
778 bitmap loops = BITMAP_ALLOC (NULL);
779 bitmap processed = BITMAP_ALLOC (NULL);
781 for (i = 0; VEC_iterate (int, c->vertices, i, v); i++)
782 if (!already_processed_vertex_p (processed, v))
783 rdg_flag_vertex_and_dependent (rdg, v, partition, loops, processed,
786 /* Also iterate on the array of stores not in the starting vertices,
787 and determine those vertices that have some memory affinity with
788 the current nodes in the component: these are stores to the same
789 arrays, i.e. we're taking care of cache locality. */
790 rdg_flag_similar_memory_accesses (rdg, partition, loops, processed,
793 rdg_flag_loop_exits (rdg, loops, partition, processed, part_has_writes);
795 BITMAP_FREE (processed);
800 /* Free memory for COMPONENTS. */
803 free_rdg_components (VEC (rdgc, heap) *components)
808 for (i = 0; VEC_iterate (rdgc, components, i, x); i++)
810 VEC_free (int, heap, x->vertices);
815 /* Build the COMPONENTS vector with the strongly connected components
816 of RDG in which the STARTING_VERTICES occur. */
819 rdg_build_components (struct graph *rdg, VEC (int, heap) *starting_vertices,
820 VEC (rdgc, heap) **components)
823 bitmap saved_components = BITMAP_ALLOC (NULL);
824 int n_components = graphds_scc (rdg, NULL);
825 VEC (int, heap) **all_components = XNEWVEC (VEC (int, heap) *, n_components);
827 for (i = 0; i < n_components; i++)
828 all_components[i] = VEC_alloc (int, heap, 3);
830 for (i = 0; i < rdg->n_vertices; i++)
831 VEC_safe_push (int, heap, all_components[rdg->vertices[i].component], i);
833 for (i = 0; VEC_iterate (int, starting_vertices, i, v); i++)
835 int c = rdg->vertices[v].component;
837 if (!bitmap_bit_p (saved_components, c))
839 rdgc x = XCNEW (struct rdg_component);
841 x->vertices = all_components[c];
843 VEC_safe_push (rdgc, heap, *components, x);
844 bitmap_set_bit (saved_components, c);
848 for (i = 0; i < n_components; i++)
849 if (!bitmap_bit_p (saved_components, i))
850 VEC_free (int, heap, all_components[i]);
852 free (all_components);
853 BITMAP_FREE (saved_components);
856 /* Aggregate several components into a useful partition that is
857 registered in the PARTITIONS vector. Partitions will be
858 distributed in different loops. */
861 rdg_build_partitions (struct graph *rdg, VEC (rdgc, heap) *components,
862 VEC (int, heap) **other_stores,
863 VEC (bitmap, heap) **partitions, bitmap processed)
867 bitmap partition = BITMAP_ALLOC (NULL);
869 for (i = 0; VEC_iterate (rdgc, components, i, x); i++)
872 bool part_has_writes = false;
873 int v = VEC_index (int, x->vertices, 0);
875 if (bitmap_bit_p (processed, v))
878 np = build_rdg_partition_for_component (rdg, x, &part_has_writes,
880 bitmap_ior_into (partition, np);
881 bitmap_ior_into (processed, np);
886 if (dump_file && (dump_flags & TDF_DETAILS))
888 fprintf (dump_file, "ldist useful partition:\n");
889 dump_bitmap (dump_file, partition);
892 VEC_safe_push (bitmap, heap, *partitions, partition);
893 partition = BITMAP_ALLOC (NULL);
897 /* Add the nodes from the RDG that were not marked as processed, and
898 that are used outside the current loop. These are scalar
899 computations that are not yet part of previous partitions. */
900 for (i = 0; i < rdg->n_vertices; i++)
901 if (!bitmap_bit_p (processed, i)
902 && rdg_defs_used_in_other_loops_p (rdg, i))
903 VEC_safe_push (int, heap, *other_stores, i);
905 /* If there are still statements left in the OTHER_STORES array,
906 create other components and partitions with these stores and
907 their dependences. */
908 if (VEC_length (int, *other_stores) > 0)
910 VEC (rdgc, heap) *comps = VEC_alloc (rdgc, heap, 3);
911 VEC (int, heap) *foo = VEC_alloc (int, heap, 3);
913 rdg_build_components (rdg, *other_stores, &comps);
914 rdg_build_partitions (rdg, comps, &foo, partitions, processed);
916 VEC_free (int, heap, foo);
917 free_rdg_components (comps);
920 /* If there is something left in the last partition, save it. */
921 if (bitmap_count_bits (partition) > 0)
922 VEC_safe_push (bitmap, heap, *partitions, partition);
924 BITMAP_FREE (partition);
927 /* Dump to FILE the PARTITIONS. */
930 dump_rdg_partitions (FILE *file, VEC (bitmap, heap) *partitions)
935 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
936 debug_bitmap_file (file, partition);
939 /* Debug PARTITIONS. */
940 extern void debug_rdg_partitions (VEC (bitmap, heap) *);
943 debug_rdg_partitions (VEC (bitmap, heap) *partitions)
945 dump_rdg_partitions (stderr, partitions);
948 /* Returns the number of read and write operations in the RDG. */
951 number_of_rw_in_rdg (struct graph *rdg)
955 for (i = 0; i < rdg->n_vertices; i++)
957 if (RDG_MEM_WRITE_STMT (rdg, i))
960 if (RDG_MEM_READS_STMT (rdg, i))
967 /* Returns the number of read and write operations in a PARTITION of
971 number_of_rw_in_partition (struct graph *rdg, bitmap partition)
977 EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii)
979 if (RDG_MEM_WRITE_STMT (rdg, i))
982 if (RDG_MEM_READS_STMT (rdg, i))
989 /* Returns true when one of the PARTITIONS contains all the read or
990 write operations of RDG. */
993 partition_contains_all_rw (struct graph *rdg, VEC (bitmap, heap) *partitions)
997 int nrw = number_of_rw_in_rdg (rdg);
999 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
1000 if (nrw == number_of_rw_in_partition (rdg, partition))
1006 /* Generate code from STARTING_VERTICES in RDG. Returns the number of
1007 distributed loops. */
1010 ldist_gen (struct loop *loop, struct graph *rdg,
1011 VEC (int, heap) *starting_vertices)
1014 VEC (rdgc, heap) *components = VEC_alloc (rdgc, heap, 3);
1015 VEC (bitmap, heap) *partitions = VEC_alloc (bitmap, heap, 3);
1016 VEC (int, heap) *other_stores = VEC_alloc (int, heap, 3);
1017 bitmap partition, processed = BITMAP_ALLOC (NULL);
1019 remaining_stmts = BITMAP_ALLOC (NULL);
1020 upstream_mem_writes = BITMAP_ALLOC (NULL);
1022 for (i = 0; i < rdg->n_vertices; i++)
1024 bitmap_set_bit (remaining_stmts, i);
1026 /* Save in OTHER_STORES all the memory writes that are not in
1027 STARTING_VERTICES. */
1028 if (RDG_MEM_WRITE_STMT (rdg, i))
1034 for (j = 0; VEC_iterate (int, starting_vertices, j, v); j++)
1042 VEC_safe_push (int, heap, other_stores, i);
1046 mark_nodes_having_upstream_mem_writes (rdg);
1047 rdg_build_components (rdg, starting_vertices, &components);
1048 rdg_build_partitions (rdg, components, &other_stores, &partitions,
1050 BITMAP_FREE (processed);
1051 nbp = VEC_length (bitmap, partitions);
1054 || partition_contains_all_rw (rdg, partitions))
1057 if (dump_file && (dump_flags & TDF_DETAILS))
1058 dump_rdg_partitions (dump_file, partitions);
1060 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
1061 if (!generate_code_for_partition (loop, partition, i < nbp - 1))
1064 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1065 update_ssa (TODO_update_ssa_only_virtuals | TODO_update_ssa);
1069 BITMAP_FREE (remaining_stmts);
1070 BITMAP_FREE (upstream_mem_writes);
1072 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
1073 BITMAP_FREE (partition);
1075 VEC_free (int, heap, other_stores);
1076 VEC_free (bitmap, heap, partitions);
1077 free_rdg_components (components);
1081 /* Distributes the code from LOOP in such a way that producer
1082 statements are placed before consumer statements. When STMTS is
1083 NULL, performs the maximal distribution, if STMTS is not NULL,
1084 tries to separate only these statements from the LOOP's body.
1085 Returns the number of distributed loops. */
1088 distribute_loop (struct loop *loop, VEC (gimple, heap) *stmts)
1094 VEC (int, heap) *vertices;
1096 if (loop->num_nodes > 2)
1098 if (dump_file && (dump_flags & TDF_DETAILS))
1100 "FIXME: Loop %d not distributed: it has more than two basic blocks.\n",
1106 rdg = build_rdg (loop);
1110 if (dump_file && (dump_flags & TDF_DETAILS))
1112 "FIXME: Loop %d not distributed: failed to build the RDG.\n",
1118 vertices = VEC_alloc (int, heap, 3);
1120 if (dump_file && (dump_flags & TDF_DETAILS))
1121 dump_rdg (dump_file, rdg);
1123 for (i = 0; VEC_iterate (gimple, stmts, i, s); i++)
1125 int v = rdg_vertex_for_stmt (rdg, s);
1129 VEC_safe_push (int, heap, vertices, v);
1131 if (dump_file && (dump_flags & TDF_DETAILS))
1133 "ldist asked to generate code for vertex %d\n", v);
1137 res = ldist_gen (loop, rdg, vertices);
1138 VEC_free (int, heap, vertices);
1144 /* Distribute all loops in the current function. */
1147 tree_loop_distribution (void)
1151 int nb_generated_loops = 0;
1153 FOR_EACH_LOOP (li, loop, 0)
1155 VEC (gimple, heap) *work_list = VEC_alloc (gimple, heap, 3);
1157 /* With the following working list, we're asking distribute_loop
1158 to separate the stores of the loop: when dependences allow,
1159 it will end on having one store per loop. */
1160 stores_from_loop (loop, &work_list);
1162 /* A simple heuristic for cache locality is to not split stores
1163 to the same array. Without this call, an unrolled loop would
1164 be split into as many loops as unroll factor, each loop
1165 storing in the same array. */
1166 remove_similar_memory_refs (&work_list);
1168 nb_generated_loops = distribute_loop (loop, work_list);
1170 if (dump_file && (dump_flags & TDF_DETAILS))
1172 if (nb_generated_loops > 1)
1173 fprintf (dump_file, "Loop %d distributed: split to %d loops.\n",
1174 loop->num, nb_generated_loops);
1176 fprintf (dump_file, "Loop %d is the same.\n", loop->num);
1179 verify_loop_structure ();
1181 VEC_free (gimple, heap, work_list);
1188 gate_tree_loop_distribution (void)
1190 return flag_tree_loop_distribution != 0;
1193 struct gimple_opt_pass pass_loop_distribution =
1198 gate_tree_loop_distribution, /* gate */
1199 tree_loop_distribution, /* execute */
1202 0, /* static_pass_number */
1203 TV_TREE_LOOP_DISTRIBUTION, /* tv_id */
1204 PROP_cfg | PROP_ssa, /* properties_required */
1205 0, /* properties_provided */
1206 0, /* properties_destroyed */
1207 0, /* todo_flags_start */
1208 TODO_dump_func | TODO_verify_loops /* todo_flags_finish */