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 /* Strongly connected components of the reduced data dependence graph. */
715 typedef struct rdg_component
718 VEC (int, heap
) *vertices
;
722 DEF_VEC_ALLOC_P (rdgc
, heap
);
724 /* Flag all the nodes of RDG containing memory accesses that could
725 potentially belong to arrays already accessed in the current
729 rdg_flag_similar_memory_accesses (struct graph
*rdg
, bitmap partition
,
730 bitmap loops
, bitmap processed
,
731 VEC (int, heap
) **other_stores
)
737 struct graph_edge
*e
;
739 EXECUTE_IF_SET_IN_BITMAP (partition
, 0, i
, ii
)
740 if (RDG_MEM_WRITE_STMT (rdg
, i
)
741 || RDG_MEM_READS_STMT (rdg
, i
))
743 for (j
= 0; j
< rdg
->n_vertices
; j
++)
744 if (!bitmap_bit_p (processed
, j
)
745 && (RDG_MEM_WRITE_STMT (rdg
, j
)
746 || RDG_MEM_READS_STMT (rdg
, j
))
747 && rdg_has_similar_memory_accesses (rdg
, i
, j
))
749 /* Flag first the node J itself, and all the nodes that
750 are needed to compute J. */
751 rdg_flag_vertex_and_dependent (rdg
, j
, partition
, loops
,
754 /* When J is a read, we want to coalesce in the same
755 PARTITION all the nodes that are using J: this is
756 needed for better cache locality. */
757 rdg_flag_all_uses (rdg
, j
, partition
, loops
, processed
, &foo
);
759 /* Remove from OTHER_STORES the vertex that we flagged. */
760 if (RDG_MEM_WRITE_STMT (rdg
, j
))
761 for (k
= 0; VEC_iterate (int, *other_stores
, k
, kk
); k
++)
764 VEC_unordered_remove (int, *other_stores
, k
);
769 /* If the node I has two uses, then keep these together in the
771 for (n
= 0, e
= rdg
->vertices
[i
].succ
; e
; e
= e
->succ_next
, n
++);
774 rdg_flag_all_uses (rdg
, i
, partition
, loops
, processed
, &foo
);
778 /* Returns a bitmap in which all the statements needed for computing
779 the strongly connected component C of the RDG are flagged, also
780 including the loop exit conditions. */
783 build_rdg_partition_for_component (struct graph
*rdg
, rdgc c
,
784 bool *part_has_writes
,
785 VEC (int, heap
) **other_stores
)
788 bitmap partition
= BITMAP_ALLOC (NULL
);
789 bitmap loops
= BITMAP_ALLOC (NULL
);
790 bitmap processed
= BITMAP_ALLOC (NULL
);
792 for (i
= 0; VEC_iterate (int, c
->vertices
, i
, v
); i
++)
793 if (!already_processed_vertex_p (processed
, v
))
794 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
, processed
,
797 /* Also iterate on the array of stores not in the starting vertices,
798 and determine those vertices that have some memory affinity with
799 the current nodes in the component: these are stores to the same
800 arrays, i.e. we're taking care of cache locality. */
801 rdg_flag_similar_memory_accesses (rdg
, partition
, loops
, processed
,
804 rdg_flag_loop_exits (rdg
, loops
, partition
, processed
, part_has_writes
);
806 BITMAP_FREE (processed
);
811 /* Free memory for COMPONENTS. */
814 free_rdg_components (VEC (rdgc
, heap
) *components
)
819 for (i
= 0; VEC_iterate (rdgc
, components
, i
, x
); i
++)
821 VEC_free (int, heap
, x
->vertices
);
826 /* Build the COMPONENTS vector with the strongly connected components
827 of RDG in which the STARTING_VERTICES occur. */
830 rdg_build_components (struct graph
*rdg
, VEC (int, heap
) *starting_vertices
,
831 VEC (rdgc
, heap
) **components
)
834 bitmap saved_components
= BITMAP_ALLOC (NULL
);
835 int n_components
= graphds_scc (rdg
, NULL
);
836 VEC (int, heap
) **all_components
= XNEWVEC (VEC (int, heap
) *, n_components
);
838 for (i
= 0; i
< n_components
; i
++)
839 all_components
[i
] = VEC_alloc (int, heap
, 3);
841 for (i
= 0; i
< rdg
->n_vertices
; i
++)
842 VEC_safe_push (int, heap
, all_components
[rdg
->vertices
[i
].component
], i
);
844 for (i
= 0; VEC_iterate (int, starting_vertices
, i
, v
); i
++)
846 int c
= rdg
->vertices
[v
].component
;
848 if (!bitmap_bit_p (saved_components
, c
))
850 rdgc x
= XCNEW (struct rdg_component
);
852 x
->vertices
= all_components
[c
];
854 VEC_safe_push (rdgc
, heap
, *components
, x
);
855 bitmap_set_bit (saved_components
, c
);
859 for (i
= 0; i
< n_components
; i
++)
860 if (!bitmap_bit_p (saved_components
, i
))
861 VEC_free (int, heap
, all_components
[i
]);
863 free (all_components
);
864 BITMAP_FREE (saved_components
);
868 DEF_VEC_ALLOC_P (bitmap
, heap
);
870 /* Aggregate several components into a useful partition that is
871 registered in the PARTITIONS vector. Partitions will be
872 distributed in different loops. */
875 rdg_build_partitions (struct graph
*rdg
, VEC (rdgc
, heap
) *components
,
876 VEC (int, heap
) **other_stores
,
877 VEC (bitmap
, heap
) **partitions
, bitmap processed
)
881 bitmap partition
= BITMAP_ALLOC (NULL
);
883 for (i
= 0; VEC_iterate (rdgc
, components
, i
, x
); i
++)
886 bool part_has_writes
= false;
887 int v
= VEC_index (int, x
->vertices
, 0);
889 if (bitmap_bit_p (processed
, v
))
892 np
= build_rdg_partition_for_component (rdg
, x
, &part_has_writes
,
894 bitmap_ior_into (partition
, np
);
895 bitmap_ior_into (processed
, np
);
900 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
902 fprintf (dump_file
, "ldist useful partition:\n");
903 dump_bitmap (dump_file
, partition
);
906 VEC_safe_push (bitmap
, heap
, *partitions
, partition
);
907 partition
= BITMAP_ALLOC (NULL
);
911 /* Add the nodes from the RDG that were not marked as processed, and
912 that are used outside the current loop. These are scalar
913 computations that are not yet part of previous partitions. */
914 for (i
= 0; i
< rdg
->n_vertices
; i
++)
915 if (!bitmap_bit_p (processed
, i
)
916 && rdg_defs_used_in_other_loops_p (rdg
, i
))
917 VEC_safe_push (int, heap
, *other_stores
, i
);
919 /* If there are still statements left in the OTHER_STORES array,
920 create other components and partitions with these stores and
921 their dependences. */
922 if (VEC_length (int, *other_stores
) > 0)
924 VEC (rdgc
, heap
) *comps
= VEC_alloc (rdgc
, heap
, 3);
925 VEC (int, heap
) *foo
= VEC_alloc (int, heap
, 3);
927 rdg_build_components (rdg
, *other_stores
, &comps
);
928 rdg_build_partitions (rdg
, comps
, &foo
, partitions
, processed
);
930 VEC_free (int, heap
, foo
);
931 free_rdg_components (comps
);
934 /* If there is something left in the last partition, save it. */
935 if (bitmap_count_bits (partition
) > 0)
936 VEC_safe_push (bitmap
, heap
, *partitions
, partition
);
938 BITMAP_FREE (partition
);
941 /* Dump to FILE the PARTITIONS. */
944 dump_rdg_partitions (FILE *file
, VEC (bitmap
, heap
) *partitions
)
949 for (i
= 0; VEC_iterate (bitmap
, partitions
, i
, partition
); i
++)
950 debug_bitmap_file (file
, partition
);
953 /* Debug PARTITIONS. */
954 extern void debug_rdg_partitions (VEC (bitmap
, heap
) *);
957 debug_rdg_partitions (VEC (bitmap
, heap
) *partitions
)
959 dump_rdg_partitions (stderr
, partitions
);
962 /* Generate code from STARTING_VERTICES in RDG. Returns the number of
963 distributed loops. */
966 ldist_gen (struct loop
*loop
, struct graph
*rdg
,
967 VEC (int, heap
) *starting_vertices
)
970 VEC (rdgc
, heap
) *components
= VEC_alloc (rdgc
, heap
, 3);
971 VEC (bitmap
, heap
) *partitions
= VEC_alloc (bitmap
, heap
, 3);
972 VEC (int, heap
) *other_stores
= VEC_alloc (int, heap
, 3);
973 bitmap partition
, processed
= BITMAP_ALLOC (NULL
);
975 remaining_stmts
= BITMAP_ALLOC (NULL
);
976 upstream_mem_writes
= BITMAP_ALLOC (NULL
);
978 for (i
= 0; i
< rdg
->n_vertices
; i
++)
980 bitmap_set_bit (remaining_stmts
, i
);
982 /* Save in OTHER_STORES all the memory writes that are not in
983 STARTING_VERTICES. */
984 if (RDG_MEM_WRITE_STMT (rdg
, i
))
990 for (j
= 0; VEC_iterate (int, starting_vertices
, j
, v
); j
++)
998 VEC_safe_push (int, heap
, other_stores
, i
);
1002 mark_nodes_having_upstream_mem_writes (rdg
);
1003 rdg_build_components (rdg
, starting_vertices
, &components
);
1004 rdg_build_partitions (rdg
, components
, &other_stores
, &partitions
,
1006 BITMAP_FREE (processed
);
1007 nbp
= VEC_length (bitmap
, partitions
);
1012 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1013 dump_rdg_partitions (dump_file
, partitions
);
1015 for (i
= 0; VEC_iterate (bitmap
, partitions
, i
, partition
); i
++)
1016 if (!generate_code_for_partition (loop
, partition
, i
< nbp
- 1))
1019 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1020 update_ssa (TODO_update_ssa_only_virtuals
| TODO_update_ssa
);
1024 BITMAP_FREE (remaining_stmts
);
1025 BITMAP_FREE (upstream_mem_writes
);
1027 for (i
= 0; VEC_iterate (bitmap
, partitions
, i
, partition
); i
++)
1028 BITMAP_FREE (partition
);
1030 VEC_free (int, heap
, other_stores
);
1031 VEC_free (bitmap
, heap
, partitions
);
1032 free_rdg_components (components
);
1036 /* Distributes the code from LOOP in such a way that producer
1037 statements are placed before consumer statements. When STMTS is
1038 NULL, performs the maximal distribution, if STMTS is not NULL,
1039 tries to separate only these statements from the LOOP's body.
1040 Returns the number of distributed loops. */
1043 distribute_loop (struct loop
*loop
, VEC (gimple
, heap
) *stmts
)
1049 VEC (int, heap
) *vertices
;
1051 if (loop
->num_nodes
> 2)
1053 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1055 "FIXME: Loop %d not distributed: it has more than two basic blocks.\n",
1061 rdg
= build_rdg (loop
);
1065 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1067 "FIXME: Loop %d not distributed: failed to build the RDG.\n",
1073 vertices
= VEC_alloc (int, heap
, 3);
1075 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1076 dump_rdg (dump_file
, rdg
);
1078 for (i
= 0; VEC_iterate (gimple
, stmts
, i
, s
); i
++)
1080 int v
= rdg_vertex_for_stmt (rdg
, s
);
1084 VEC_safe_push (int, heap
, vertices
, v
);
1086 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1088 "ldist asked to generate code for vertex %d\n", v
);
1092 res
= ldist_gen (loop
, rdg
, vertices
);
1093 VEC_free (int, heap
, vertices
);
1099 /* Distribute all loops in the current function. */
1102 tree_loop_distribution (void)
1106 int nb_generated_loops
= 0;
1108 FOR_EACH_LOOP (li
, loop
, 0)
1110 VEC (gimple
, heap
) *work_list
= VEC_alloc (gimple
, heap
, 3);
1112 /* With the following working list, we're asking distribute_loop
1113 to separate the stores of the loop: when dependences allow,
1114 it will end on having one store per loop. */
1115 stores_from_loop (loop
, &work_list
);
1117 /* A simple heuristic for cache locality is to not split stores
1118 to the same array. Without this call, an unrolled loop would
1119 be split into as many loops as unroll factor, each loop
1120 storing in the same array. */
1121 remove_similar_memory_refs (&work_list
);
1123 nb_generated_loops
= distribute_loop (loop
, work_list
);
1125 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1127 if (nb_generated_loops
> 1)
1128 fprintf (dump_file
, "Loop %d distributed: split to %d loops.\n",
1129 loop
->num
, nb_generated_loops
);
1131 fprintf (dump_file
, "Loop %d is the same.\n", loop
->num
);
1134 verify_loop_structure ();
1136 VEC_free (gimple
, heap
, work_list
);
1143 gate_tree_loop_distribution (void)
1145 return flag_tree_loop_distribution
!= 0;
1148 struct gimple_opt_pass pass_loop_distribution
=
1153 gate_tree_loop_distribution
, /* gate */
1154 tree_loop_distribution
, /* execute */
1157 0, /* static_pass_number */
1158 TV_TREE_LOOP_DISTRIBUTION
, /* tv_id */
1159 PROP_cfg
| PROP_ssa
, /* properties_required */
1160 0, /* properties_provided */
1161 0, /* properties_destroyed */
1162 0, /* todo_flags_start */
1163 TODO_dump_func
| TODO_verify_loops
/* todo_flags_finish */