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"
54 #include "basic-block.h"
55 #include "diagnostic.h"
56 #include "tree-flow.h"
57 #include "tree-dump.h"
62 #include "tree-chrec.h"
63 #include "tree-data-ref.h"
64 #include "tree-scalar-evolution.h"
65 #include "tree-pass.h"
67 #include "langhooks.h"
68 #include "tree-vectorizer.h"
70 /* If bit I is not set, it means that this node represents an
71 operation that has already been performed, and that should not be
72 performed again. This is the subgraph of remaining important
73 computations that is passed to the DFS algorithm for avoiding to
74 include several times the same stores in different loops. */
75 static bitmap remaining_stmts;
77 /* A node of the RDG is marked in this bitmap when it has as a
78 predecessor a node that writes to memory. */
79 static bitmap upstream_mem_writes;
81 /* Update the PHI nodes of NEW_LOOP. NEW_LOOP is a duplicate of
85 update_phis_for_loop_copy (struct loop *orig_loop, struct loop *new_loop)
88 gimple_stmt_iterator si_new, si_orig;
89 edge orig_loop_latch = loop_latch_edge (orig_loop);
90 edge orig_entry_e = loop_preheader_edge (orig_loop);
91 edge new_loop_entry_e = loop_preheader_edge (new_loop);
93 /* Scan the phis in the headers of the old and new loops
94 (they are organized in exactly the same order). */
95 for (si_new = gsi_start_phis (new_loop->header),
96 si_orig = gsi_start_phis (orig_loop->header);
97 !gsi_end_p (si_new) && !gsi_end_p (si_orig);
98 gsi_next (&si_new), gsi_next (&si_orig))
101 source_location locus;
102 gimple phi_new = gsi_stmt (si_new);
103 gimple phi_orig = gsi_stmt (si_orig);
105 /* Add the first phi argument for the phi in NEW_LOOP (the one
106 associated with the entry of NEW_LOOP) */
107 def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_entry_e);
108 locus = gimple_phi_arg_location_from_edge (phi_orig, orig_entry_e);
109 add_phi_arg (phi_new, def, new_loop_entry_e, locus);
111 /* Add the second phi argument for the phi in NEW_LOOP (the one
112 associated with the latch of NEW_LOOP) */
113 def = PHI_ARG_DEF_FROM_EDGE (phi_orig, orig_loop_latch);
114 locus = gimple_phi_arg_location_from_edge (phi_orig, orig_loop_latch);
116 if (TREE_CODE (def) == SSA_NAME)
118 new_ssa_name = get_current_def (def);
121 /* This only happens if there are no definitions inside the
122 loop. Use the the invariant in the new loop as is. */
126 /* Could be an integer. */
129 add_phi_arg (phi_new, new_ssa_name, loop_latch_edge (new_loop), locus);
133 /* Return a copy of LOOP placed before LOOP. */
136 copy_loop_before (struct loop *loop)
139 edge preheader = loop_preheader_edge (loop);
141 if (!single_exit (loop))
144 initialize_original_copy_tables ();
145 res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, preheader);
146 free_original_copy_tables ();
151 update_phis_for_loop_copy (loop, res);
152 rename_variables_in_loop (res);
157 /* Creates an empty basic block after LOOP. */
160 create_bb_after_loop (struct loop *loop)
162 edge exit = single_exit (loop);
170 /* Generate code for PARTITION from the code in LOOP. The loop is
171 copied when COPY_P is true. All the statements not flagged in the
172 PARTITION bitmap are removed from the loop or from its copy. The
173 statements are indexed in sequence inside a basic block, and the
174 basic blocks of a loop are taken in dom order. Returns true when
175 the code gen succeeded. */
178 generate_loops_for_partition (struct loop *loop, bitmap partition, bool copy_p)
181 gimple_stmt_iterator bsi;
186 loop = copy_loop_before (loop);
187 create_preheader (loop, CP_SIMPLE_PREHEADERS);
188 create_bb_after_loop (loop);
194 /* Remove stmts not in the PARTITION bitmap. The order in which we
195 visit the phi nodes and the statements is exactly as in
197 bbs = get_loop_body_in_dom_order (loop);
199 for (x = 0, i = 0; i < loop->num_nodes; i++)
201 basic_block bb = bbs[i];
203 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
204 if (!bitmap_bit_p (partition, x++))
205 remove_phi_node (&bsi, true);
209 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi);)
210 if (gimple_code (gsi_stmt (bsi)) != GIMPLE_LABEL
211 && !bitmap_bit_p (partition, x++))
212 gsi_remove (&bsi, false);
216 mark_virtual_ops_in_bb (bb);
223 /* Build the size argument for a memset call. */
226 build_size_arg_loc (location_t loc, tree nb_iter, tree op,
227 gimple_seq *stmt_list)
232 x = fold_build2_loc (loc, MULT_EXPR, size_type_node,
233 fold_convert_loc (loc, size_type_node, nb_iter),
234 fold_convert_loc (loc, size_type_node,
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 gimple_stmt_iterator i;
254 struct data_reference *dr = XCNEW (struct data_reference);
255 location_t loc = gimple_location (stmt);
259 if (!dr_analyze_innermost (dr))
262 /* Test for a positive stride, iterating over every element. */
263 if (integer_zerop (size_binop (MINUS_EXPR,
264 fold_convert (sizetype, DR_STEP (dr)),
265 TYPE_SIZE_UNIT (TREE_TYPE (op0)))))
267 addr_base = fold_convert_loc (loc, sizetype,
268 size_binop_loc (loc, PLUS_EXPR,
271 addr_base = fold_build2_loc (loc, POINTER_PLUS_EXPR,
272 TREE_TYPE (DR_BASE_ADDRESS (dr)),
273 DR_BASE_ADDRESS (dr), addr_base);
275 nb_bytes = build_size_arg_loc (loc, nb_iter, op0, &stmt_list);
278 /* Test for a negative stride, iterating over every element. */
279 else if (integer_zerop (size_binop (PLUS_EXPR,
280 TYPE_SIZE_UNIT (TREE_TYPE (op0)),
281 fold_convert (sizetype, DR_STEP (dr)))))
283 nb_bytes = build_size_arg_loc (loc, nb_iter, op0, &stmt_list);
285 addr_base = size_binop_loc (loc, PLUS_EXPR, DR_OFFSET (dr), DR_INIT (dr));
286 addr_base = fold_convert_loc (loc, sizetype, addr_base);
287 addr_base = size_binop_loc (loc, MINUS_EXPR, addr_base,
288 fold_convert_loc (loc, sizetype, nb_bytes));
289 addr_base = size_binop_loc (loc, PLUS_EXPR, addr_base,
290 TYPE_SIZE_UNIT (TREE_TYPE (op0)));
291 addr_base = fold_build2_loc (loc, POINTER_PLUS_EXPR,
292 TREE_TYPE (DR_BASE_ADDRESS (dr)),
293 DR_BASE_ADDRESS (dr), addr_base);
298 mem = force_gimple_operand (addr_base, &stmts, true, NULL);
299 gimple_seq_add_seq (&stmt_list, stmts);
301 fn = build_fold_addr_expr (implicit_built_in_decls [BUILT_IN_MEMSET]);
302 fn_call = gimple_build_call (fn, 3, mem, integer_zero_node, nb_bytes);
303 gimple_seq_add_stmt (&stmt_list, fn_call);
305 for (i = gsi_start (stmt_list); !gsi_end_p (i); gsi_next (&i))
307 gimple s = gsi_stmt (i);
308 update_stmt_if_modified (s);
311 gsi_insert_seq_after (&bsi, stmt_list, GSI_CONTINUE_LINKING);
314 if (dump_file && (dump_flags & TDF_DETAILS))
315 fprintf (dump_file, "generated memset zero\n");
322 /* Propagate phis in BB b to their uses and remove them. */
325 prop_phis (basic_block b)
327 gimple_stmt_iterator psi;
328 gimple_seq phis = phi_nodes (b);
330 for (psi = gsi_start (phis); !gsi_end_p (psi); )
332 gimple phi = gsi_stmt (psi);
333 tree def = gimple_phi_result (phi), use = gimple_phi_arg_def (phi, 0);
335 gcc_assert (gimple_phi_num_args (phi) == 1);
337 if (!is_gimple_reg (def))
339 imm_use_iterator iter;
343 FOR_EACH_IMM_USE_STMT (stmt, iter, def)
344 FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
345 SET_USE (use_p, use);
348 replace_uses_by (def, use);
350 remove_phi_node (&psi, true);
354 /* Tries to generate a builtin function for the instructions of LOOP
355 pointed to by the bits set in PARTITION. Returns true when the
356 operation succeeded. */
359 generate_builtin (struct loop *loop, bitmap partition, bool copy_p)
366 gimple_stmt_iterator bsi;
367 tree nb_iter = number_of_exit_cond_executions (loop);
369 if (!nb_iter || nb_iter == chrec_dont_know)
372 bbs = get_loop_body_in_dom_order (loop);
374 for (i = 0; i < loop->num_nodes; i++)
376 basic_block bb = bbs[i];
378 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
381 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
383 gimple stmt = gsi_stmt (bsi);
385 if (bitmap_bit_p (partition, x++)
386 && is_gimple_assign (stmt)
387 && !is_gimple_reg (gimple_assign_lhs (stmt)))
389 /* Don't generate the builtins when there are more than
395 if (bb == loop->latch)
396 nb_iter = number_of_latch_executions (loop);
404 op0 = gimple_assign_lhs (write);
405 op1 = gimple_assign_rhs1 (write);
407 if (!(TREE_CODE (op0) == ARRAY_REF
408 || TREE_CODE (op0) == INDIRECT_REF))
411 /* The new statements will be placed before LOOP. */
412 bsi = gsi_last_bb (loop_preheader_edge (loop)->src);
414 if (gimple_assign_rhs_code (write) == INTEGER_CST
415 && (integer_zerop (op1) || real_zerop (op1)))
416 res = generate_memset_zero (write, op0, nb_iter, bsi);
418 /* If this is the last partition for which we generate code, we have
419 to destroy the loop. */
422 unsigned nbbs = loop->num_nodes;
423 basic_block src = loop_preheader_edge (loop)->src;
424 basic_block dest = single_exit (loop)->dest;
426 make_edge (src, dest, EDGE_FALLTHRU);
427 cancel_loop_tree (loop);
429 for (i = 0; i < nbbs; i++)
430 delete_basic_block (bbs[i]);
432 set_immediate_dominator (CDI_DOMINATORS, dest,
433 recompute_dominator (CDI_DOMINATORS, dest));
441 /* Generates code for PARTITION. For simple loops, this function can
442 generate a built-in. */
445 generate_code_for_partition (struct loop *loop, bitmap partition, bool copy_p)
447 if (generate_builtin (loop, partition, copy_p))
450 return generate_loops_for_partition (loop, partition, copy_p);
454 /* Returns true if the node V of RDG cannot be recomputed. */
457 rdg_cannot_recompute_vertex_p (struct graph *rdg, int v)
459 if (RDG_MEM_WRITE_STMT (rdg, v))
465 /* Returns true when the vertex V has already been generated in the
466 current partition (V is in PROCESSED), or when V belongs to another
467 partition and cannot be recomputed (V is not in REMAINING_STMTS). */
470 already_processed_vertex_p (bitmap processed, int v)
472 return (bitmap_bit_p (processed, v)
473 || !bitmap_bit_p (remaining_stmts, v));
476 /* Returns NULL when there is no anti-dependence among the successors
477 of vertex V, otherwise returns the edge with the anti-dep. */
479 static struct graph_edge *
480 has_anti_dependence (struct vertex *v)
482 struct graph_edge *e;
485 for (e = v->succ; e; e = e->succ_next)
486 if (RDGE_TYPE (e) == anti_dd)
492 /* Returns true when V has an anti-dependence edge among its successors. */
495 predecessor_has_mem_write (struct graph *rdg, struct vertex *v)
497 struct graph_edge *e;
500 for (e = v->pred; e; e = e->pred_next)
501 if (bitmap_bit_p (upstream_mem_writes, e->src)
502 /* Don't consider flow channels: a write to memory followed
503 by a read from memory. These channels allow the split of
504 the RDG in different partitions. */
505 && !RDG_MEM_WRITE_STMT (rdg, e->src))
511 /* Initializes the upstream_mem_writes bitmap following the
512 information from RDG. */
515 mark_nodes_having_upstream_mem_writes (struct graph *rdg)
518 bitmap seen = BITMAP_ALLOC (NULL);
520 for (v = rdg->n_vertices - 1; v >= 0; v--)
521 if (!bitmap_bit_p (seen, v))
524 VEC (int, heap) *nodes = VEC_alloc (int, heap, 3);
526 graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
528 for (i = 0; VEC_iterate (int, nodes, i, x); i++)
530 if (bitmap_bit_p (seen, x))
533 bitmap_set_bit (seen, x);
535 if (RDG_MEM_WRITE_STMT (rdg, x)
536 || predecessor_has_mem_write (rdg, &(rdg->vertices[x]))
537 /* In anti dependences the read should occur before
538 the write, this is why both the read and the write
539 should be placed in the same partition. */
540 || has_anti_dependence (&(rdg->vertices[x])))
542 bitmap_set_bit (upstream_mem_writes, x);
546 VEC_free (int, heap, nodes);
550 /* Returns true when vertex u has a memory write node as a predecessor
554 has_upstream_mem_writes (int u)
556 return bitmap_bit_p (upstream_mem_writes, u);
559 static void rdg_flag_vertex_and_dependent (struct graph *, int, bitmap, bitmap,
562 /* Flag all the uses of U. */
565 rdg_flag_all_uses (struct graph *rdg, int u, bitmap partition, bitmap loops,
566 bitmap processed, bool *part_has_writes)
568 struct graph_edge *e;
570 for (e = rdg->vertices[u].succ; e; e = e->succ_next)
571 if (!bitmap_bit_p (processed, e->dest))
573 rdg_flag_vertex_and_dependent (rdg, e->dest, partition, loops,
574 processed, part_has_writes);
575 rdg_flag_all_uses (rdg, e->dest, partition, loops, processed,
580 /* Flag the uses of U stopping following the information from
581 upstream_mem_writes. */
584 rdg_flag_uses (struct graph *rdg, int u, bitmap partition, bitmap loops,
585 bitmap processed, bool *part_has_writes)
588 struct vertex *x = &(rdg->vertices[u]);
589 gimple stmt = RDGV_STMT (x);
590 struct graph_edge *anti_dep = has_anti_dependence (x);
592 /* Keep in the same partition the destination of an antidependence,
593 because this is a store to the exact same location. Putting this
594 in another partition is bad for cache locality. */
597 int v = anti_dep->dest;
599 if (!already_processed_vertex_p (processed, v))
600 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
601 processed, part_has_writes);
604 if (gimple_code (stmt) != GIMPLE_PHI)
606 if ((use_p = gimple_vuse_op (stmt)) != NULL_USE_OPERAND_P)
608 tree use = USE_FROM_PTR (use_p);
610 if (TREE_CODE (use) == SSA_NAME)
612 gimple def_stmt = SSA_NAME_DEF_STMT (use);
613 int v = rdg_vertex_for_stmt (rdg, def_stmt);
616 && !already_processed_vertex_p (processed, v))
617 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
618 processed, part_has_writes);
623 if (is_gimple_assign (stmt) && has_upstream_mem_writes (u))
625 tree op0 = gimple_assign_lhs (stmt);
627 /* Scalar channels don't have enough space for transmitting data
628 between tasks, unless we add more storage by privatizing. */
629 if (is_gimple_reg (op0))
632 imm_use_iterator iter;
634 FOR_EACH_IMM_USE_FAST (use_p, iter, op0)
636 int v = rdg_vertex_for_stmt (rdg, USE_STMT (use_p));
638 if (!already_processed_vertex_p (processed, v))
639 rdg_flag_vertex_and_dependent (rdg, v, partition, loops,
640 processed, part_has_writes);
646 /* Flag V from RDG as part of PARTITION, and also flag its loop number
650 rdg_flag_vertex (struct graph *rdg, int v, bitmap partition, bitmap loops,
651 bool *part_has_writes)
655 if (bitmap_bit_p (partition, v))
658 loop = loop_containing_stmt (RDG_STMT (rdg, v));
659 bitmap_set_bit (loops, loop->num);
660 bitmap_set_bit (partition, v);
662 if (rdg_cannot_recompute_vertex_p (rdg, v))
664 *part_has_writes = true;
665 bitmap_clear_bit (remaining_stmts, v);
669 /* Flag in the bitmap PARTITION the vertex V and all its predecessors.
670 Also flag their loop number in LOOPS. */
673 rdg_flag_vertex_and_dependent (struct graph *rdg, int v, bitmap partition,
674 bitmap loops, bitmap processed,
675 bool *part_has_writes)
678 VEC (int, heap) *nodes = VEC_alloc (int, heap, 3);
681 bitmap_set_bit (processed, v);
682 rdg_flag_uses (rdg, v, partition, loops, processed, part_has_writes);
683 graphds_dfs (rdg, &v, 1, &nodes, false, remaining_stmts);
684 rdg_flag_vertex (rdg, v, partition, loops, part_has_writes);
686 for (i = 0; VEC_iterate (int, nodes, i, x); i++)
687 if (!already_processed_vertex_p (processed, x))
688 rdg_flag_vertex_and_dependent (rdg, x, partition, loops, processed,
691 VEC_free (int, heap, nodes);
694 /* Initialize CONDS with all the condition statements from the basic
698 collect_condition_stmts (struct loop *loop, VEC (gimple, heap) **conds)
702 VEC (edge, heap) *exits = get_loop_exit_edges (loop);
704 for (i = 0; VEC_iterate (edge, exits, i, e); i++)
706 gimple cond = last_stmt (e->src);
709 VEC_safe_push (gimple, heap, *conds, cond);
712 VEC_free (edge, heap, exits);
715 /* Add to PARTITION all the exit condition statements for LOOPS
716 together with all their dependent statements determined from
720 rdg_flag_loop_exits (struct graph *rdg, bitmap loops, bitmap partition,
721 bitmap processed, bool *part_has_writes)
725 VEC (gimple, heap) *conds = VEC_alloc (gimple, heap, 3);
727 EXECUTE_IF_SET_IN_BITMAP (loops, 0, i, bi)
728 collect_condition_stmts (get_loop (i), &conds);
730 while (!VEC_empty (gimple, conds))
732 gimple cond = VEC_pop (gimple, conds);
733 int v = rdg_vertex_for_stmt (rdg, cond);
734 bitmap new_loops = BITMAP_ALLOC (NULL);
736 if (!already_processed_vertex_p (processed, v))
737 rdg_flag_vertex_and_dependent (rdg, v, partition, new_loops, processed,
740 EXECUTE_IF_SET_IN_BITMAP (new_loops, 0, i, bi)
741 if (!bitmap_bit_p (loops, i))
743 bitmap_set_bit (loops, i);
744 collect_condition_stmts (get_loop (i), &conds);
747 BITMAP_FREE (new_loops);
751 /* Flag all the nodes of RDG containing memory accesses that could
752 potentially belong to arrays already accessed in the current
756 rdg_flag_similar_memory_accesses (struct graph *rdg, bitmap partition,
757 bitmap loops, bitmap processed,
758 VEC (int, heap) **other_stores)
764 struct graph_edge *e;
766 EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii)
767 if (RDG_MEM_WRITE_STMT (rdg, i)
768 || RDG_MEM_READS_STMT (rdg, i))
770 for (j = 0; j < rdg->n_vertices; j++)
771 if (!bitmap_bit_p (processed, j)
772 && (RDG_MEM_WRITE_STMT (rdg, j)
773 || RDG_MEM_READS_STMT (rdg, j))
774 && rdg_has_similar_memory_accesses (rdg, i, j))
776 /* Flag first the node J itself, and all the nodes that
777 are needed to compute J. */
778 rdg_flag_vertex_and_dependent (rdg, j, partition, loops,
781 /* When J is a read, we want to coalesce in the same
782 PARTITION all the nodes that are using J: this is
783 needed for better cache locality. */
784 rdg_flag_all_uses (rdg, j, partition, loops, processed, &foo);
786 /* Remove from OTHER_STORES the vertex that we flagged. */
787 if (RDG_MEM_WRITE_STMT (rdg, j))
788 for (k = 0; VEC_iterate (int, *other_stores, k, kk); k++)
791 VEC_unordered_remove (int, *other_stores, k);
796 /* If the node I has two uses, then keep these together in the
798 for (n = 0, e = rdg->vertices[i].succ; e; e = e->succ_next, n++);
801 rdg_flag_all_uses (rdg, i, partition, loops, processed, &foo);
805 /* Returns a bitmap in which all the statements needed for computing
806 the strongly connected component C of the RDG are flagged, also
807 including the loop exit conditions. */
810 build_rdg_partition_for_component (struct graph *rdg, rdgc c,
811 bool *part_has_writes,
812 VEC (int, heap) **other_stores)
815 bitmap partition = BITMAP_ALLOC (NULL);
816 bitmap loops = BITMAP_ALLOC (NULL);
817 bitmap processed = BITMAP_ALLOC (NULL);
819 for (i = 0; VEC_iterate (int, c->vertices, i, v); i++)
820 if (!already_processed_vertex_p (processed, v))
821 rdg_flag_vertex_and_dependent (rdg, v, partition, loops, processed,
824 /* Also iterate on the array of stores not in the starting vertices,
825 and determine those vertices that have some memory affinity with
826 the current nodes in the component: these are stores to the same
827 arrays, i.e. we're taking care of cache locality. */
828 rdg_flag_similar_memory_accesses (rdg, partition, loops, processed,
831 rdg_flag_loop_exits (rdg, loops, partition, processed, part_has_writes);
833 BITMAP_FREE (processed);
838 /* Free memory for COMPONENTS. */
841 free_rdg_components (VEC (rdgc, heap) *components)
846 for (i = 0; VEC_iterate (rdgc, components, i, x); i++)
848 VEC_free (int, heap, x->vertices);
853 /* Build the COMPONENTS vector with the strongly connected components
854 of RDG in which the STARTING_VERTICES occur. */
857 rdg_build_components (struct graph *rdg, VEC (int, heap) *starting_vertices,
858 VEC (rdgc, heap) **components)
861 bitmap saved_components = BITMAP_ALLOC (NULL);
862 int n_components = graphds_scc (rdg, NULL);
863 VEC (int, heap) **all_components = XNEWVEC (VEC (int, heap) *, n_components);
865 for (i = 0; i < n_components; i++)
866 all_components[i] = VEC_alloc (int, heap, 3);
868 for (i = 0; i < rdg->n_vertices; i++)
869 VEC_safe_push (int, heap, all_components[rdg->vertices[i].component], i);
871 for (i = 0; VEC_iterate (int, starting_vertices, i, v); i++)
873 int c = rdg->vertices[v].component;
875 if (!bitmap_bit_p (saved_components, c))
877 rdgc x = XCNEW (struct rdg_component);
879 x->vertices = all_components[c];
881 VEC_safe_push (rdgc, heap, *components, x);
882 bitmap_set_bit (saved_components, c);
886 for (i = 0; i < n_components; i++)
887 if (!bitmap_bit_p (saved_components, i))
888 VEC_free (int, heap, all_components[i]);
890 free (all_components);
891 BITMAP_FREE (saved_components);
894 /* Aggregate several components into a useful partition that is
895 registered in the PARTITIONS vector. Partitions will be
896 distributed in different loops. */
899 rdg_build_partitions (struct graph *rdg, VEC (rdgc, heap) *components,
900 VEC (int, heap) **other_stores,
901 VEC (bitmap, heap) **partitions, bitmap processed)
905 bitmap partition = BITMAP_ALLOC (NULL);
907 for (i = 0; VEC_iterate (rdgc, components, i, x); i++)
910 bool part_has_writes = false;
911 int v = VEC_index (int, x->vertices, 0);
913 if (bitmap_bit_p (processed, v))
916 np = build_rdg_partition_for_component (rdg, x, &part_has_writes,
918 bitmap_ior_into (partition, np);
919 bitmap_ior_into (processed, np);
924 if (dump_file && (dump_flags & TDF_DETAILS))
926 fprintf (dump_file, "ldist useful partition:\n");
927 dump_bitmap (dump_file, partition);
930 VEC_safe_push (bitmap, heap, *partitions, partition);
931 partition = BITMAP_ALLOC (NULL);
935 /* Add the nodes from the RDG that were not marked as processed, and
936 that are used outside the current loop. These are scalar
937 computations that are not yet part of previous partitions. */
938 for (i = 0; i < rdg->n_vertices; i++)
939 if (!bitmap_bit_p (processed, i)
940 && rdg_defs_used_in_other_loops_p (rdg, i))
941 VEC_safe_push (int, heap, *other_stores, i);
943 /* If there are still statements left in the OTHER_STORES array,
944 create other components and partitions with these stores and
945 their dependences. */
946 if (VEC_length (int, *other_stores) > 0)
948 VEC (rdgc, heap) *comps = VEC_alloc (rdgc, heap, 3);
949 VEC (int, heap) *foo = VEC_alloc (int, heap, 3);
951 rdg_build_components (rdg, *other_stores, &comps);
952 rdg_build_partitions (rdg, comps, &foo, partitions, processed);
954 VEC_free (int, heap, foo);
955 free_rdg_components (comps);
958 /* If there is something left in the last partition, save it. */
959 if (bitmap_count_bits (partition) > 0)
960 VEC_safe_push (bitmap, heap, *partitions, partition);
962 BITMAP_FREE (partition);
965 /* Dump to FILE the PARTITIONS. */
968 dump_rdg_partitions (FILE *file, VEC (bitmap, heap) *partitions)
973 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
974 debug_bitmap_file (file, partition);
977 /* Debug PARTITIONS. */
978 extern void debug_rdg_partitions (VEC (bitmap, heap) *);
981 debug_rdg_partitions (VEC (bitmap, heap) *partitions)
983 dump_rdg_partitions (stderr, partitions);
986 /* Returns the number of read and write operations in the RDG. */
989 number_of_rw_in_rdg (struct graph *rdg)
993 for (i = 0; i < rdg->n_vertices; i++)
995 if (RDG_MEM_WRITE_STMT (rdg, i))
998 if (RDG_MEM_READS_STMT (rdg, i))
1005 /* Returns the number of read and write operations in a PARTITION of
1009 number_of_rw_in_partition (struct graph *rdg, bitmap partition)
1015 EXECUTE_IF_SET_IN_BITMAP (partition, 0, i, ii)
1017 if (RDG_MEM_WRITE_STMT (rdg, i))
1020 if (RDG_MEM_READS_STMT (rdg, i))
1027 /* Returns true when one of the PARTITIONS contains all the read or
1028 write operations of RDG. */
1031 partition_contains_all_rw (struct graph *rdg, VEC (bitmap, heap) *partitions)
1035 int nrw = number_of_rw_in_rdg (rdg);
1037 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
1038 if (nrw == number_of_rw_in_partition (rdg, partition))
1044 /* Generate code from STARTING_VERTICES in RDG. Returns the number of
1045 distributed loops. */
1048 ldist_gen (struct loop *loop, struct graph *rdg,
1049 VEC (int, heap) *starting_vertices)
1052 VEC (rdgc, heap) *components = VEC_alloc (rdgc, heap, 3);
1053 VEC (bitmap, heap) *partitions = VEC_alloc (bitmap, heap, 3);
1054 VEC (int, heap) *other_stores = VEC_alloc (int, heap, 3);
1055 bitmap partition, processed = BITMAP_ALLOC (NULL);
1057 remaining_stmts = BITMAP_ALLOC (NULL);
1058 upstream_mem_writes = BITMAP_ALLOC (NULL);
1060 for (i = 0; i < rdg->n_vertices; i++)
1062 bitmap_set_bit (remaining_stmts, i);
1064 /* Save in OTHER_STORES all the memory writes that are not in
1065 STARTING_VERTICES. */
1066 if (RDG_MEM_WRITE_STMT (rdg, i))
1072 for (j = 0; VEC_iterate (int, starting_vertices, j, v); j++)
1080 VEC_safe_push (int, heap, other_stores, i);
1084 mark_nodes_having_upstream_mem_writes (rdg);
1085 rdg_build_components (rdg, starting_vertices, &components);
1086 rdg_build_partitions (rdg, components, &other_stores, &partitions,
1088 BITMAP_FREE (processed);
1089 nbp = VEC_length (bitmap, partitions);
1092 || partition_contains_all_rw (rdg, partitions))
1095 if (dump_file && (dump_flags & TDF_DETAILS))
1096 dump_rdg_partitions (dump_file, partitions);
1098 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
1099 if (!generate_code_for_partition (loop, partition, i < nbp - 1))
1102 rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1103 update_ssa (TODO_update_ssa_only_virtuals | TODO_update_ssa);
1107 BITMAP_FREE (remaining_stmts);
1108 BITMAP_FREE (upstream_mem_writes);
1110 for (i = 0; VEC_iterate (bitmap, partitions, i, partition); i++)
1111 BITMAP_FREE (partition);
1113 VEC_free (int, heap, other_stores);
1114 VEC_free (bitmap, heap, partitions);
1115 free_rdg_components (components);
1119 /* Distributes the code from LOOP in such a way that producer
1120 statements are placed before consumer statements. When STMTS is
1121 NULL, performs the maximal distribution, if STMTS is not NULL,
1122 tries to separate only these statements from the LOOP's body.
1123 Returns the number of distributed loops. */
1126 distribute_loop (struct loop *loop, VEC (gimple, heap) *stmts)
1132 VEC (int, heap) *vertices;
1134 if (loop->num_nodes > 2)
1136 if (dump_file && (dump_flags & TDF_DETAILS))
1138 "FIXME: Loop %d not distributed: it has more than two basic blocks.\n",
1144 rdg = build_rdg (loop);
1148 if (dump_file && (dump_flags & TDF_DETAILS))
1150 "FIXME: Loop %d not distributed: failed to build the RDG.\n",
1156 vertices = VEC_alloc (int, heap, 3);
1158 if (dump_file && (dump_flags & TDF_DETAILS))
1159 dump_rdg (dump_file, rdg);
1161 for (i = 0; VEC_iterate (gimple, stmts, i, s); i++)
1163 int v = rdg_vertex_for_stmt (rdg, s);
1167 VEC_safe_push (int, heap, vertices, v);
1169 if (dump_file && (dump_flags & TDF_DETAILS))
1171 "ldist asked to generate code for vertex %d\n", v);
1175 res = ldist_gen (loop, rdg, vertices);
1176 VEC_free (int, heap, vertices);
1182 /* Distribute all loops in the current function. */
1185 tree_loop_distribution (void)
1189 int nb_generated_loops = 0;
1191 FOR_EACH_LOOP (li, loop, 0)
1193 VEC (gimple, heap) *work_list = VEC_alloc (gimple, heap, 3);
1195 /* With the following working list, we're asking distribute_loop
1196 to separate the stores of the loop: when dependences allow,
1197 it will end on having one store per loop. */
1198 stores_from_loop (loop, &work_list);
1200 /* A simple heuristic for cache locality is to not split stores
1201 to the same array. Without this call, an unrolled loop would
1202 be split into as many loops as unroll factor, each loop
1203 storing in the same array. */
1204 remove_similar_memory_refs (&work_list);
1206 nb_generated_loops = distribute_loop (loop, work_list);
1208 if (dump_file && (dump_flags & TDF_DETAILS))
1210 if (nb_generated_loops > 1)
1211 fprintf (dump_file, "Loop %d distributed: split to %d loops.\n",
1212 loop->num, nb_generated_loops);
1214 fprintf (dump_file, "Loop %d is the same.\n", loop->num);
1217 verify_loop_structure ();
1219 VEC_free (gimple, heap, work_list);
1226 gate_tree_loop_distribution (void)
1228 return flag_tree_loop_distribution != 0;
1231 struct gimple_opt_pass pass_loop_distribution =
1236 gate_tree_loop_distribution, /* gate */
1237 tree_loop_distribution, /* execute */
1240 0, /* static_pass_number */
1241 TV_TREE_LOOP_DISTRIBUTION, /* tv_id */
1242 PROP_cfg | PROP_ssa, /* properties_required */
1243 0, /* properties_provided */
1244 0, /* properties_destroyed */
1245 0, /* todo_flags_start */
1246 TODO_dump_func /* todo_flags_finish */