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 /* Build size argument. */
222 build_size_arg (tree nb_iter
, tree op
, gimple_seq
* stmt_list
)
225 gimple_seq stmts
= NULL
;
227 nb_bytes
= fold_build2 (MULT_EXPR
, TREE_TYPE (nb_iter
),
228 nb_iter
, TYPE_SIZE_UNIT (TREE_TYPE (op
)));
229 nb_bytes
= force_gimple_operand (nb_bytes
, &stmts
, true, NULL
);
230 gimple_seq_add_seq (stmt_list
, stmts
);
235 /* Generate a call to memset. Return true when the operation succeeded. */
238 generate_memset_zero (gimple stmt
, tree op0
, tree nb_iter
,
239 gimple_stmt_iterator bsi
)
242 tree nb_bytes
= NULL
;
244 gimple_seq stmts
= NULL
, stmt_list
= NULL
;
246 tree mem
, fndecl
, fntype
, fn
;
247 gimple_stmt_iterator i
;
249 struct data_reference
*dr
= XCNEW (struct data_reference
);
253 if (!dr_analyze_innermost (dr
))
256 /* Test for a positive stride, iterating over every element. */
257 if (integer_zerop (fold_build2 (MINUS_EXPR
, integer_type_node
, DR_STEP (dr
),
258 TYPE_SIZE_UNIT (TREE_TYPE (op0
)))))
259 addr_base
= fold_build2 (PLUS_EXPR
, TREE_TYPE (DR_BASE_ADDRESS (dr
)),
260 DR_BASE_ADDRESS (dr
),
261 size_binop (PLUS_EXPR
,
262 DR_OFFSET (dr
), DR_INIT (dr
)));
264 /* Test for a negative stride, iterating over every element. */
265 else if (integer_zerop (fold_build2 (PLUS_EXPR
, integer_type_node
,
266 TYPE_SIZE_UNIT (TREE_TYPE (op0
)),
269 nb_bytes
= build_size_arg (nb_iter
, op0
, &stmt_list
);
270 addr_base
= size_binop (PLUS_EXPR
, DR_OFFSET (dr
), DR_INIT (dr
));
271 addr_base
= fold_build2 (MINUS_EXPR
, sizetype
, addr_base
, nb_bytes
);
272 addr_base
= force_gimple_operand (addr_base
, &stmts
, true, NULL
);
273 gimple_seq_add_seq (&stmt_list
, stmts
);
275 addr_base
= fold_build2 (POINTER_PLUS_EXPR
,
276 TREE_TYPE (DR_BASE_ADDRESS (dr
)),
277 DR_BASE_ADDRESS (dr
), addr_base
);
282 mem
= force_gimple_operand (addr_base
, &stmts
, true, NULL
);
283 gimple_seq_add_seq (&stmt_list
, stmts
);
285 fndecl
= implicit_built_in_decls
[BUILT_IN_MEMSET
];
286 fntype
= TREE_TYPE (fndecl
);
287 fn
= build1 (ADDR_EXPR
, build_pointer_type (fntype
), fndecl
);
290 nb_bytes
= build_size_arg (nb_iter
, op0
, &stmt_list
);
291 fn_call
= gimple_build_call (fn
, 3, mem
, integer_zero_node
, nb_bytes
);
292 gimple_seq_add_stmt (&stmt_list
, fn_call
);
294 for (i
= gsi_start (stmt_list
); !gsi_end_p (i
); gsi_next (&i
))
296 gimple s
= gsi_stmt (i
);
297 update_stmt_if_modified (s
);
299 FOR_EACH_SSA_TREE_OPERAND (t
, s
, iter
, SSA_OP_VIRTUAL_DEFS
)
301 if (TREE_CODE (t
) == SSA_NAME
)
302 t
= SSA_NAME_VAR (t
);
303 mark_sym_for_renaming (t
);
307 /* Mark also the uses of the VDEFS of STMT to be renamed. */
308 FOR_EACH_SSA_TREE_OPERAND (t
, stmt
, iter
, SSA_OP_VIRTUAL_DEFS
)
310 if (TREE_CODE (t
) == SSA_NAME
)
313 imm_use_iterator imm_iter
;
315 FOR_EACH_IMM_USE_STMT (s
, imm_iter
, t
)
318 t
= SSA_NAME_VAR (t
);
320 mark_sym_for_renaming (t
);
323 gsi_insert_seq_after (&bsi
, stmt_list
, GSI_CONTINUE_LINKING
);
326 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
327 fprintf (dump_file
, "generated memset zero\n");
334 /* Tries to generate a builtin function for the instructions of LOOP
335 pointed to by the bits set in PARTITION. Returns true when the
336 operation succeeded. */
339 generate_builtin (struct loop
*loop
, bitmap partition
, bool copy_p
)
346 gimple_stmt_iterator bsi
;
347 tree nb_iter
= number_of_exit_cond_executions (loop
);
349 if (!nb_iter
|| nb_iter
== chrec_dont_know
)
352 bbs
= get_loop_body_in_dom_order (loop
);
354 for (i
= 0; i
< loop
->num_nodes
; i
++)
356 basic_block bb
= bbs
[i
];
358 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
361 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
363 gimple stmt
= gsi_stmt (bsi
);
365 if (bitmap_bit_p (partition
, x
++)
366 && is_gimple_assign (stmt
)
367 && !is_gimple_reg (gimple_assign_lhs (stmt
)))
369 /* Don't generate the builtins when there are more than
382 op0
= gimple_assign_lhs (write
);
383 op1
= gimple_assign_rhs1 (write
);
385 if (!(TREE_CODE (op0
) == ARRAY_REF
386 || TREE_CODE (op0
) == INDIRECT_REF
))
389 /* The new statements will be placed before LOOP. */
390 bsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
392 if (gimple_assign_rhs_code (write
) == INTEGER_CST
393 && (integer_zerop (op1
) || real_zerop (op1
)))
394 res
= generate_memset_zero (write
, op0
, nb_iter
, bsi
);
396 /* If this is the last partition for which we generate code, we have
397 to destroy the loop. */
400 unsigned nbbs
= loop
->num_nodes
;
401 basic_block src
= loop_preheader_edge (loop
)->src
;
402 basic_block dest
= single_exit (loop
)->dest
;
403 make_edge (src
, dest
, EDGE_FALLTHRU
);
404 set_immediate_dominator (CDI_DOMINATORS
, dest
, src
);
405 cancel_loop_tree (loop
);
407 for (i
= 0; i
< nbbs
; i
++)
408 delete_basic_block (bbs
[i
]);
416 /* Generates code for PARTITION. For simple loops, this function can
417 generate a built-in. */
420 generate_code_for_partition (struct loop
*loop
, bitmap partition
, bool copy_p
)
422 if (generate_builtin (loop
, partition
, copy_p
))
425 return generate_loops_for_partition (loop
, partition
, copy_p
);
429 /* Returns true if the node V of RDG cannot be recomputed. */
432 rdg_cannot_recompute_vertex_p (struct graph
*rdg
, int v
)
434 if (RDG_MEM_WRITE_STMT (rdg
, v
))
440 /* Returns true when the vertex V has already been generated in the
441 current partition (V is in PROCESSED), or when V belongs to another
442 partition and cannot be recomputed (V is not in REMAINING_STMTS). */
445 already_processed_vertex_p (bitmap processed
, int v
)
447 return (bitmap_bit_p (processed
, v
)
448 || !bitmap_bit_p (remaining_stmts
, v
));
451 /* Returns NULL when there is no anti-dependence among the successors
452 of vertex V, otherwise returns the edge with the anti-dep. */
454 static struct graph_edge
*
455 has_anti_dependence (struct vertex
*v
)
457 struct graph_edge
*e
;
460 for (e
= v
->succ
; e
; e
= e
->succ_next
)
461 if (RDGE_TYPE (e
) == anti_dd
)
467 /* Returns true when V has an anti-dependence edge among its successors. */
470 predecessor_has_mem_write (struct graph
*rdg
, struct vertex
*v
)
472 struct graph_edge
*e
;
475 for (e
= v
->pred
; e
; e
= e
->pred_next
)
476 if (bitmap_bit_p (upstream_mem_writes
, e
->src
)
477 /* Don't consider flow channels: a write to memory followed
478 by a read from memory. These channels allow the split of
479 the RDG in different partitions. */
480 && !RDG_MEM_WRITE_STMT (rdg
, e
->src
))
486 /* Initializes the upstream_mem_writes bitmap following the
487 information from RDG. */
490 mark_nodes_having_upstream_mem_writes (struct graph
*rdg
)
493 bitmap seen
= BITMAP_ALLOC (NULL
);
495 for (v
= rdg
->n_vertices
- 1; v
>= 0; v
--)
496 if (!bitmap_bit_p (seen
, v
))
499 VEC (int, heap
) *nodes
= VEC_alloc (int, heap
, 3);
500 bool has_upstream_mem_write_p
= false;
502 graphds_dfs (rdg
, &v
, 1, &nodes
, false, NULL
);
504 for (i
= 0; VEC_iterate (int, nodes
, i
, x
); i
++)
506 if (bitmap_bit_p (seen
, x
))
509 bitmap_set_bit (seen
, x
);
511 if (RDG_MEM_WRITE_STMT (rdg
, x
)
512 || predecessor_has_mem_write (rdg
, &(rdg
->vertices
[x
]))
513 /* In anti dependences the read should occur before
514 the write, this is why both the read and the write
515 should be placed in the same partition. */
516 || has_anti_dependence (&(rdg
->vertices
[x
])))
518 has_upstream_mem_write_p
= true;
519 bitmap_set_bit (upstream_mem_writes
, x
);
523 VEC_free (int, heap
, nodes
);
527 /* Returns true when vertex u has a memory write node as a predecessor
531 has_upstream_mem_writes (int u
)
533 return bitmap_bit_p (upstream_mem_writes
, u
);
536 static void rdg_flag_vertex_and_dependent (struct graph
*, int, bitmap
, bitmap
,
539 /* Flag all the uses of U. */
542 rdg_flag_all_uses (struct graph
*rdg
, int u
, bitmap partition
, bitmap loops
,
543 bitmap processed
, bool *part_has_writes
)
545 struct graph_edge
*e
;
547 for (e
= rdg
->vertices
[u
].succ
; e
; e
= e
->succ_next
)
548 if (!bitmap_bit_p (processed
, e
->dest
))
550 rdg_flag_vertex_and_dependent (rdg
, e
->dest
, partition
, loops
,
551 processed
, part_has_writes
);
552 rdg_flag_all_uses (rdg
, e
->dest
, partition
, loops
, processed
,
557 /* Flag the uses of U stopping following the information from
558 upstream_mem_writes. */
561 rdg_flag_uses (struct graph
*rdg
, int u
, bitmap partition
, bitmap loops
,
562 bitmap processed
, bool *part_has_writes
)
566 struct vertex
*x
= &(rdg
->vertices
[u
]);
567 gimple stmt
= RDGV_STMT (x
);
568 struct graph_edge
*anti_dep
= has_anti_dependence (x
);
570 /* Keep in the same partition the destination of an antidependence,
571 because this is a store to the exact same location. Putting this
572 in another partition is bad for cache locality. */
575 int v
= anti_dep
->dest
;
577 if (!already_processed_vertex_p (processed
, v
))
578 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
,
579 processed
, part_has_writes
);
582 if (gimple_code (stmt
) != GIMPLE_PHI
)
584 FOR_EACH_SSA_USE_OPERAND (use_p
, stmt
, iter
, SSA_OP_VIRTUAL_USES
)
586 tree use
= USE_FROM_PTR (use_p
);
588 if (TREE_CODE (use
) == SSA_NAME
)
590 gimple def_stmt
= SSA_NAME_DEF_STMT (use
);
591 int v
= rdg_vertex_for_stmt (rdg
, def_stmt
);
594 && !already_processed_vertex_p (processed
, v
))
595 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
,
596 processed
, part_has_writes
);
601 if (is_gimple_assign (stmt
) && has_upstream_mem_writes (u
))
603 tree op0
= gimple_assign_lhs (stmt
);
605 /* Scalar channels don't have enough space for transmitting data
606 between tasks, unless we add more storage by privatizing. */
607 if (is_gimple_reg (op0
))
610 imm_use_iterator iter
;
612 FOR_EACH_IMM_USE_FAST (use_p
, iter
, op0
)
614 int v
= rdg_vertex_for_stmt (rdg
, USE_STMT (use_p
));
616 if (!already_processed_vertex_p (processed
, v
))
617 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
,
618 processed
, part_has_writes
);
624 /* Flag V from RDG as part of PARTITION, and also flag its loop number
628 rdg_flag_vertex (struct graph
*rdg
, int v
, bitmap partition
, bitmap loops
,
629 bool *part_has_writes
)
633 if (bitmap_bit_p (partition
, v
))
636 loop
= loop_containing_stmt (RDG_STMT (rdg
, v
));
637 bitmap_set_bit (loops
, loop
->num
);
638 bitmap_set_bit (partition
, v
);
640 if (rdg_cannot_recompute_vertex_p (rdg
, v
))
642 *part_has_writes
= true;
643 bitmap_clear_bit (remaining_stmts
, v
);
647 /* Flag in the bitmap PARTITION the vertex V and all its predecessors.
648 Also flag their loop number in LOOPS. */
651 rdg_flag_vertex_and_dependent (struct graph
*rdg
, int v
, bitmap partition
,
652 bitmap loops
, bitmap processed
,
653 bool *part_has_writes
)
656 VEC (int, heap
) *nodes
= VEC_alloc (int, heap
, 3);
659 bitmap_set_bit (processed
, v
);
660 rdg_flag_uses (rdg
, v
, partition
, loops
, processed
, part_has_writes
);
661 graphds_dfs (rdg
, &v
, 1, &nodes
, false, remaining_stmts
);
662 rdg_flag_vertex (rdg
, v
, partition
, loops
, part_has_writes
);
664 for (i
= 0; VEC_iterate (int, nodes
, i
, x
); i
++)
665 if (!already_processed_vertex_p (processed
, x
))
666 rdg_flag_vertex_and_dependent (rdg
, x
, partition
, loops
, processed
,
669 VEC_free (int, heap
, nodes
);
672 /* Initialize CONDS with all the condition statements from the basic
676 collect_condition_stmts (struct loop
*loop
, VEC (gimple
, heap
) **conds
)
680 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
682 for (i
= 0; VEC_iterate (edge
, exits
, i
, e
); i
++)
684 gimple cond
= last_stmt (e
->src
);
687 VEC_safe_push (gimple
, heap
, *conds
, cond
);
690 VEC_free (edge
, heap
, exits
);
693 /* Add to PARTITION all the exit condition statements for LOOPS
694 together with all their dependent statements determined from
698 rdg_flag_loop_exits (struct graph
*rdg
, bitmap loops
, bitmap partition
,
699 bitmap processed
, bool *part_has_writes
)
703 VEC (gimple
, heap
) *conds
= VEC_alloc (gimple
, heap
, 3);
705 EXECUTE_IF_SET_IN_BITMAP (loops
, 0, i
, bi
)
706 collect_condition_stmts (get_loop (i
), &conds
);
708 while (!VEC_empty (gimple
, conds
))
710 gimple cond
= VEC_pop (gimple
, conds
);
711 int v
= rdg_vertex_for_stmt (rdg
, cond
);
712 bitmap new_loops
= BITMAP_ALLOC (NULL
);
714 if (!already_processed_vertex_p (processed
, v
))
715 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, new_loops
, processed
,
718 EXECUTE_IF_SET_IN_BITMAP (new_loops
, 0, i
, bi
)
719 if (!bitmap_bit_p (loops
, i
))
721 bitmap_set_bit (loops
, i
);
722 collect_condition_stmts (get_loop (i
), &conds
);
725 BITMAP_FREE (new_loops
);
729 /* Flag all the nodes of RDG containing memory accesses that could
730 potentially belong to arrays already accessed in the current
734 rdg_flag_similar_memory_accesses (struct graph
*rdg
, bitmap partition
,
735 bitmap loops
, bitmap processed
,
736 VEC (int, heap
) **other_stores
)
742 struct graph_edge
*e
;
744 EXECUTE_IF_SET_IN_BITMAP (partition
, 0, i
, ii
)
745 if (RDG_MEM_WRITE_STMT (rdg
, i
)
746 || RDG_MEM_READS_STMT (rdg
, i
))
748 for (j
= 0; j
< rdg
->n_vertices
; j
++)
749 if (!bitmap_bit_p (processed
, j
)
750 && (RDG_MEM_WRITE_STMT (rdg
, j
)
751 || RDG_MEM_READS_STMT (rdg
, j
))
752 && rdg_has_similar_memory_accesses (rdg
, i
, j
))
754 /* Flag first the node J itself, and all the nodes that
755 are needed to compute J. */
756 rdg_flag_vertex_and_dependent (rdg
, j
, partition
, loops
,
759 /* When J is a read, we want to coalesce in the same
760 PARTITION all the nodes that are using J: this is
761 needed for better cache locality. */
762 rdg_flag_all_uses (rdg
, j
, partition
, loops
, processed
, &foo
);
764 /* Remove from OTHER_STORES the vertex that we flagged. */
765 if (RDG_MEM_WRITE_STMT (rdg
, j
))
766 for (k
= 0; VEC_iterate (int, *other_stores
, k
, kk
); k
++)
769 VEC_unordered_remove (int, *other_stores
, k
);
774 /* If the node I has two uses, then keep these together in the
776 for (n
= 0, e
= rdg
->vertices
[i
].succ
; e
; e
= e
->succ_next
, n
++);
779 rdg_flag_all_uses (rdg
, i
, partition
, loops
, processed
, &foo
);
783 /* Returns a bitmap in which all the statements needed for computing
784 the strongly connected component C of the RDG are flagged, also
785 including the loop exit conditions. */
788 build_rdg_partition_for_component (struct graph
*rdg
, rdgc c
,
789 bool *part_has_writes
,
790 VEC (int, heap
) **other_stores
)
793 bitmap partition
= BITMAP_ALLOC (NULL
);
794 bitmap loops
= BITMAP_ALLOC (NULL
);
795 bitmap processed
= BITMAP_ALLOC (NULL
);
797 for (i
= 0; VEC_iterate (int, c
->vertices
, i
, v
); i
++)
798 if (!already_processed_vertex_p (processed
, v
))
799 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
, processed
,
802 /* Also iterate on the array of stores not in the starting vertices,
803 and determine those vertices that have some memory affinity with
804 the current nodes in the component: these are stores to the same
805 arrays, i.e. we're taking care of cache locality. */
806 rdg_flag_similar_memory_accesses (rdg
, partition
, loops
, processed
,
809 rdg_flag_loop_exits (rdg
, loops
, partition
, processed
, part_has_writes
);
811 BITMAP_FREE (processed
);
816 /* Free memory for COMPONENTS. */
819 free_rdg_components (VEC (rdgc
, heap
) *components
)
824 for (i
= 0; VEC_iterate (rdgc
, components
, i
, x
); i
++)
826 VEC_free (int, heap
, x
->vertices
);
831 /* Build the COMPONENTS vector with the strongly connected components
832 of RDG in which the STARTING_VERTICES occur. */
835 rdg_build_components (struct graph
*rdg
, VEC (int, heap
) *starting_vertices
,
836 VEC (rdgc
, heap
) **components
)
839 bitmap saved_components
= BITMAP_ALLOC (NULL
);
840 int n_components
= graphds_scc (rdg
, NULL
);
841 VEC (int, heap
) **all_components
= XNEWVEC (VEC (int, heap
) *, n_components
);
843 for (i
= 0; i
< n_components
; i
++)
844 all_components
[i
] = VEC_alloc (int, heap
, 3);
846 for (i
= 0; i
< rdg
->n_vertices
; i
++)
847 VEC_safe_push (int, heap
, all_components
[rdg
->vertices
[i
].component
], i
);
849 for (i
= 0; VEC_iterate (int, starting_vertices
, i
, v
); i
++)
851 int c
= rdg
->vertices
[v
].component
;
853 if (!bitmap_bit_p (saved_components
, c
))
855 rdgc x
= XCNEW (struct rdg_component
);
857 x
->vertices
= all_components
[c
];
859 VEC_safe_push (rdgc
, heap
, *components
, x
);
860 bitmap_set_bit (saved_components
, c
);
864 for (i
= 0; i
< n_components
; i
++)
865 if (!bitmap_bit_p (saved_components
, i
))
866 VEC_free (int, heap
, all_components
[i
]);
868 free (all_components
);
869 BITMAP_FREE (saved_components
);
872 /* Aggregate several components into a useful partition that is
873 registered in the PARTITIONS vector. Partitions will be
874 distributed in different loops. */
877 rdg_build_partitions (struct graph
*rdg
, VEC (rdgc
, heap
) *components
,
878 VEC (int, heap
) **other_stores
,
879 VEC (bitmap
, heap
) **partitions
, bitmap processed
)
883 bitmap partition
= BITMAP_ALLOC (NULL
);
885 for (i
= 0; VEC_iterate (rdgc
, components
, i
, x
); i
++)
888 bool part_has_writes
= false;
889 int v
= VEC_index (int, x
->vertices
, 0);
891 if (bitmap_bit_p (processed
, v
))
894 np
= build_rdg_partition_for_component (rdg
, x
, &part_has_writes
,
896 bitmap_ior_into (partition
, np
);
897 bitmap_ior_into (processed
, np
);
902 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
904 fprintf (dump_file
, "ldist useful partition:\n");
905 dump_bitmap (dump_file
, partition
);
908 VEC_safe_push (bitmap
, heap
, *partitions
, partition
);
909 partition
= BITMAP_ALLOC (NULL
);
913 /* Add the nodes from the RDG that were not marked as processed, and
914 that are used outside the current loop. These are scalar
915 computations that are not yet part of previous partitions. */
916 for (i
= 0; i
< rdg
->n_vertices
; i
++)
917 if (!bitmap_bit_p (processed
, i
)
918 && rdg_defs_used_in_other_loops_p (rdg
, i
))
919 VEC_safe_push (int, heap
, *other_stores
, i
);
921 /* If there are still statements left in the OTHER_STORES array,
922 create other components and partitions with these stores and
923 their dependences. */
924 if (VEC_length (int, *other_stores
) > 0)
926 VEC (rdgc
, heap
) *comps
= VEC_alloc (rdgc
, heap
, 3);
927 VEC (int, heap
) *foo
= VEC_alloc (int, heap
, 3);
929 rdg_build_components (rdg
, *other_stores
, &comps
);
930 rdg_build_partitions (rdg
, comps
, &foo
, partitions
, processed
);
932 VEC_free (int, heap
, foo
);
933 free_rdg_components (comps
);
936 /* If there is something left in the last partition, save it. */
937 if (bitmap_count_bits (partition
) > 0)
938 VEC_safe_push (bitmap
, heap
, *partitions
, partition
);
940 BITMAP_FREE (partition
);
943 /* Dump to FILE the PARTITIONS. */
946 dump_rdg_partitions (FILE *file
, VEC (bitmap
, heap
) *partitions
)
951 for (i
= 0; VEC_iterate (bitmap
, partitions
, i
, partition
); i
++)
952 debug_bitmap_file (file
, partition
);
955 /* Debug PARTITIONS. */
956 extern void debug_rdg_partitions (VEC (bitmap
, heap
) *);
959 debug_rdg_partitions (VEC (bitmap
, heap
) *partitions
)
961 dump_rdg_partitions (stderr
, partitions
);
964 /* Returns the number of read and write operations in the RDG. */
967 number_of_rw_in_rdg (struct graph
*rdg
)
971 for (i
= 0; i
< rdg
->n_vertices
; i
++)
973 if (RDG_MEM_WRITE_STMT (rdg
, i
))
976 if (RDG_MEM_READS_STMT (rdg
, i
))
983 /* Returns the number of read and write operations in a PARTITION of
987 number_of_rw_in_partition (struct graph
*rdg
, bitmap partition
)
993 EXECUTE_IF_SET_IN_BITMAP (partition
, 0, i
, ii
)
995 if (RDG_MEM_WRITE_STMT (rdg
, i
))
998 if (RDG_MEM_READS_STMT (rdg
, i
))
1005 /* Returns true when one of the PARTITIONS contains all the read or
1006 write operations of RDG. */
1009 partition_contains_all_rw (struct graph
*rdg
, VEC (bitmap
, heap
) *partitions
)
1013 int nrw
= number_of_rw_in_rdg (rdg
);
1015 for (i
= 0; VEC_iterate (bitmap
, partitions
, i
, partition
); i
++)
1016 if (nrw
== number_of_rw_in_partition (rdg
, partition
))
1022 /* Generate code from STARTING_VERTICES in RDG. Returns the number of
1023 distributed loops. */
1026 ldist_gen (struct loop
*loop
, struct graph
*rdg
,
1027 VEC (int, heap
) *starting_vertices
)
1030 VEC (rdgc
, heap
) *components
= VEC_alloc (rdgc
, heap
, 3);
1031 VEC (bitmap
, heap
) *partitions
= VEC_alloc (bitmap
, heap
, 3);
1032 VEC (int, heap
) *other_stores
= VEC_alloc (int, heap
, 3);
1033 bitmap partition
, processed
= BITMAP_ALLOC (NULL
);
1035 remaining_stmts
= BITMAP_ALLOC (NULL
);
1036 upstream_mem_writes
= BITMAP_ALLOC (NULL
);
1038 for (i
= 0; i
< rdg
->n_vertices
; i
++)
1040 bitmap_set_bit (remaining_stmts
, i
);
1042 /* Save in OTHER_STORES all the memory writes that are not in
1043 STARTING_VERTICES. */
1044 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1050 for (j
= 0; VEC_iterate (int, starting_vertices
, j
, v
); j
++)
1058 VEC_safe_push (int, heap
, other_stores
, i
);
1062 mark_nodes_having_upstream_mem_writes (rdg
);
1063 rdg_build_components (rdg
, starting_vertices
, &components
);
1064 rdg_build_partitions (rdg
, components
, &other_stores
, &partitions
,
1066 BITMAP_FREE (processed
);
1067 nbp
= VEC_length (bitmap
, partitions
);
1070 || partition_contains_all_rw (rdg
, partitions
))
1073 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1074 dump_rdg_partitions (dump_file
, partitions
);
1076 for (i
= 0; VEC_iterate (bitmap
, partitions
, i
, partition
); i
++)
1077 if (!generate_code_for_partition (loop
, partition
, i
< nbp
- 1))
1080 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1081 update_ssa (TODO_update_ssa_only_virtuals
| TODO_update_ssa
);
1085 BITMAP_FREE (remaining_stmts
);
1086 BITMAP_FREE (upstream_mem_writes
);
1088 for (i
= 0; VEC_iterate (bitmap
, partitions
, i
, partition
); i
++)
1089 BITMAP_FREE (partition
);
1091 VEC_free (int, heap
, other_stores
);
1092 VEC_free (bitmap
, heap
, partitions
);
1093 free_rdg_components (components
);
1097 /* Distributes the code from LOOP in such a way that producer
1098 statements are placed before consumer statements. When STMTS is
1099 NULL, performs the maximal distribution, if STMTS is not NULL,
1100 tries to separate only these statements from the LOOP's body.
1101 Returns the number of distributed loops. */
1104 distribute_loop (struct loop
*loop
, VEC (gimple
, heap
) *stmts
)
1110 VEC (int, heap
) *vertices
;
1112 if (loop
->num_nodes
> 2)
1114 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1116 "FIXME: Loop %d not distributed: it has more than two basic blocks.\n",
1122 rdg
= build_rdg (loop
);
1126 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1128 "FIXME: Loop %d not distributed: failed to build the RDG.\n",
1134 vertices
= VEC_alloc (int, heap
, 3);
1136 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1137 dump_rdg (dump_file
, rdg
);
1139 for (i
= 0; VEC_iterate (gimple
, stmts
, i
, s
); i
++)
1141 int v
= rdg_vertex_for_stmt (rdg
, s
);
1145 VEC_safe_push (int, heap
, vertices
, v
);
1147 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1149 "ldist asked to generate code for vertex %d\n", v
);
1153 res
= ldist_gen (loop
, rdg
, vertices
);
1154 VEC_free (int, heap
, vertices
);
1160 /* Distribute all loops in the current function. */
1163 tree_loop_distribution (void)
1167 int nb_generated_loops
= 0;
1169 FOR_EACH_LOOP (li
, loop
, 0)
1171 VEC (gimple
, heap
) *work_list
= VEC_alloc (gimple
, heap
, 3);
1173 /* With the following working list, we're asking distribute_loop
1174 to separate the stores of the loop: when dependences allow,
1175 it will end on having one store per loop. */
1176 stores_from_loop (loop
, &work_list
);
1178 /* A simple heuristic for cache locality is to not split stores
1179 to the same array. Without this call, an unrolled loop would
1180 be split into as many loops as unroll factor, each loop
1181 storing in the same array. */
1182 remove_similar_memory_refs (&work_list
);
1184 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
!= 0;
1209 struct gimple_opt_pass pass_loop_distribution
=
1214 gate_tree_loop_distribution
, /* gate */
1215 tree_loop_distribution
, /* execute */
1218 0, /* static_pass_number */
1219 TV_TREE_LOOP_DISTRIBUTION
, /* tv_id */
1220 PROP_cfg
| PROP_ssa
, /* properties_required */
1221 0, /* properties_provided */
1222 0, /* properties_destroyed */
1223 0, /* todo_flags_start */
1224 TODO_dump_func
| TODO_verify_loops
/* todo_flags_finish */