2 Copyright (C) 2006, 2007, 2008, 2009 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 source_location locus
;
101 gimple phi_new
= gsi_stmt (si_new
);
102 gimple phi_orig
= gsi_stmt (si_orig
);
104 /* Add the first phi argument for the phi in NEW_LOOP (the one
105 associated with the entry of NEW_LOOP) */
106 def
= PHI_ARG_DEF_FROM_EDGE (phi_orig
, orig_entry_e
);
107 locus
= gimple_phi_arg_location_from_edge (phi_orig
, orig_entry_e
);
108 add_phi_arg (phi_new
, def
, new_loop_entry_e
, locus
);
110 /* Add the second phi argument for the phi in NEW_LOOP (the one
111 associated with the latch of NEW_LOOP) */
112 def
= PHI_ARG_DEF_FROM_EDGE (phi_orig
, orig_loop_latch
);
113 locus
= gimple_phi_arg_location_from_edge (phi_orig
, orig_loop_latch
);
115 if (TREE_CODE (def
) == SSA_NAME
)
117 new_ssa_name
= get_current_def (def
);
120 /* This only happens if there are no definitions inside the
121 loop. Use the phi_result in this case. */
122 new_ssa_name
= PHI_RESULT (phi_new
);
125 /* Could be an integer. */
128 add_phi_arg (phi_new
, new_ssa_name
, loop_latch_edge (new_loop
), locus
);
132 /* Return a copy of LOOP placed before LOOP. */
135 copy_loop_before (struct loop
*loop
)
138 edge preheader
= loop_preheader_edge (loop
);
140 if (!single_exit (loop
))
143 initialize_original_copy_tables ();
144 res
= slpeel_tree_duplicate_loop_to_edge_cfg (loop
, preheader
);
145 free_original_copy_tables ();
150 update_phis_for_loop_copy (loop
, res
);
151 rename_variables_in_loop (res
);
156 /* Creates an empty basic block after LOOP. */
159 create_bb_after_loop (struct loop
*loop
)
161 edge exit
= single_exit (loop
);
169 /* Generate code for PARTITION from the code in LOOP. The loop is
170 copied when COPY_P is true. All the statements not flagged in the
171 PARTITION bitmap are removed from the loop or from its copy. The
172 statements are indexed in sequence inside a basic block, and the
173 basic blocks of a loop are taken in dom order. Returns true when
174 the code gen succeeded. */
177 generate_loops_for_partition (struct loop
*loop
, bitmap partition
, bool copy_p
)
180 gimple_stmt_iterator bsi
;
185 loop
= copy_loop_before (loop
);
186 create_preheader (loop
, CP_SIMPLE_PREHEADERS
);
187 create_bb_after_loop (loop
);
193 /* Remove stmts not in the PARTITION bitmap. The order in which we
194 visit the phi nodes and the statements is exactly as in
196 bbs
= get_loop_body_in_dom_order (loop
);
198 for (x
= 0, i
= 0; i
< loop
->num_nodes
; i
++)
200 basic_block bb
= bbs
[i
];
202 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);)
203 if (!bitmap_bit_p (partition
, x
++))
204 remove_phi_node (&bsi
, true);
208 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);)
209 if (gimple_code (gsi_stmt (bsi
)) != GIMPLE_LABEL
210 && !bitmap_bit_p (partition
, x
++))
211 gsi_remove (&bsi
, false);
215 mark_virtual_ops_in_bb (bb
);
222 /* Build the size argument for a memset call. */
225 build_size_arg_loc (location_t loc
, tree nb_iter
, tree op
,
226 gimple_seq
*stmt_list
)
231 x
= fold_build2_loc (loc
, MULT_EXPR
, size_type_node
,
232 fold_convert_loc (loc
, size_type_node
, nb_iter
),
233 fold_convert_loc (loc
, size_type_node
,
234 TYPE_SIZE_UNIT (TREE_TYPE (op
))));
235 x
= force_gimple_operand (x
, &stmts
, true, NULL
);
236 gimple_seq_add_seq (stmt_list
, stmts
);
241 /* Generate a call to memset. Return true when the operation succeeded. */
244 generate_memset_zero (gimple stmt
, tree op0
, tree nb_iter
,
245 gimple_stmt_iterator bsi
)
247 tree addr_base
, nb_bytes
;
249 gimple_seq stmt_list
= NULL
, stmts
;
252 gimple_stmt_iterator i
;
253 struct data_reference
*dr
= XCNEW (struct data_reference
);
254 location_t loc
= gimple_location (stmt
);
258 if (!dr_analyze_innermost (dr
))
261 /* Test for a positive stride, iterating over every element. */
262 if (integer_zerop (size_binop (MINUS_EXPR
,
263 fold_convert (sizetype
, DR_STEP (dr
)),
264 TYPE_SIZE_UNIT (TREE_TYPE (op0
)))))
266 addr_base
= fold_convert_loc (loc
, sizetype
,
267 size_binop_loc (loc
, PLUS_EXPR
,
270 addr_base
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
271 TREE_TYPE (DR_BASE_ADDRESS (dr
)),
272 DR_BASE_ADDRESS (dr
), addr_base
);
274 nb_bytes
= build_size_arg_loc (loc
, nb_iter
, op0
, &stmt_list
);
277 /* Test for a negative stride, iterating over every element. */
278 else if (integer_zerop (size_binop (PLUS_EXPR
,
279 TYPE_SIZE_UNIT (TREE_TYPE (op0
)),
280 fold_convert (sizetype
, DR_STEP (dr
)))))
282 nb_bytes
= build_size_arg_loc (loc
, nb_iter
, op0
, &stmt_list
);
284 addr_base
= size_binop_loc (loc
, PLUS_EXPR
, DR_OFFSET (dr
), DR_INIT (dr
));
285 addr_base
= fold_convert_loc (loc
, sizetype
, addr_base
);
286 addr_base
= size_binop_loc (loc
, MINUS_EXPR
, addr_base
,
287 fold_convert_loc (loc
, sizetype
, nb_bytes
));
288 addr_base
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
289 TREE_TYPE (DR_BASE_ADDRESS (dr
)),
290 DR_BASE_ADDRESS (dr
), addr_base
);
295 mem
= force_gimple_operand (addr_base
, &stmts
, true, NULL
);
296 gimple_seq_add_seq (&stmt_list
, stmts
);
298 fn
= build_fold_addr_expr (implicit_built_in_decls
[BUILT_IN_MEMSET
]);
299 fn_call
= gimple_build_call (fn
, 3, mem
, integer_zero_node
, nb_bytes
);
300 gimple_seq_add_stmt (&stmt_list
, fn_call
);
302 for (i
= gsi_start (stmt_list
); !gsi_end_p (i
); gsi_next (&i
))
304 gimple s
= gsi_stmt (i
);
305 update_stmt_if_modified (s
);
308 gsi_insert_seq_after (&bsi
, stmt_list
, GSI_CONTINUE_LINKING
);
311 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
312 fprintf (dump_file
, "generated memset zero\n");
319 /* Propagate phis in BB b to their uses and remove them. */
322 prop_phis (basic_block b
)
324 gimple_stmt_iterator psi
;
325 gimple_seq phis
= phi_nodes (b
);
327 for (psi
= gsi_start (phis
); !gsi_end_p (psi
); )
329 gimple phi
= gsi_stmt (psi
);
330 tree def
= gimple_phi_result (phi
), use
= gimple_phi_arg_def (phi
, 0);
332 gcc_assert (gimple_phi_num_args (phi
) == 1);
334 if (!is_gimple_reg (def
))
336 imm_use_iterator iter
;
340 FOR_EACH_IMM_USE_STMT (stmt
, iter
, def
)
341 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
342 SET_USE (use_p
, use
);
345 replace_uses_by (def
, use
);
347 remove_phi_node (&psi
, true);
351 /* Tries to generate a builtin function for the instructions of LOOP
352 pointed to by the bits set in PARTITION. Returns true when the
353 operation succeeded. */
356 generate_builtin (struct loop
*loop
, bitmap partition
, bool copy_p
)
363 gimple_stmt_iterator bsi
;
364 tree nb_iter
= number_of_exit_cond_executions (loop
);
366 if (!nb_iter
|| nb_iter
== chrec_dont_know
)
369 bbs
= get_loop_body_in_dom_order (loop
);
371 for (i
= 0; i
< loop
->num_nodes
; i
++)
373 basic_block bb
= bbs
[i
];
375 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
378 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
380 gimple stmt
= gsi_stmt (bsi
);
382 if (bitmap_bit_p (partition
, x
++)
383 && is_gimple_assign (stmt
)
384 && !is_gimple_reg (gimple_assign_lhs (stmt
)))
386 /* Don't generate the builtins when there are more than
399 op0
= gimple_assign_lhs (write
);
400 op1
= gimple_assign_rhs1 (write
);
402 if (!(TREE_CODE (op0
) == ARRAY_REF
403 || TREE_CODE (op0
) == INDIRECT_REF
))
406 /* The new statements will be placed before LOOP. */
407 bsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
409 if (gimple_assign_rhs_code (write
) == INTEGER_CST
410 && (integer_zerop (op1
) || real_zerop (op1
)))
411 res
= generate_memset_zero (write
, op0
, nb_iter
, bsi
);
413 /* If this is the last partition for which we generate code, we have
414 to destroy the loop. */
417 unsigned nbbs
= loop
->num_nodes
;
418 basic_block src
= loop_preheader_edge (loop
)->src
;
419 basic_block dest
= single_exit (loop
)->dest
;
421 make_edge (src
, dest
, EDGE_FALLTHRU
);
422 cancel_loop_tree (loop
);
424 for (i
= 0; i
< nbbs
; i
++)
425 delete_basic_block (bbs
[i
]);
427 set_immediate_dominator (CDI_DOMINATORS
, dest
,
428 recompute_dominator (CDI_DOMINATORS
, dest
));
436 /* Generates code for PARTITION. For simple loops, this function can
437 generate a built-in. */
440 generate_code_for_partition (struct loop
*loop
, bitmap partition
, bool copy_p
)
442 if (generate_builtin (loop
, partition
, copy_p
))
445 return generate_loops_for_partition (loop
, partition
, copy_p
);
449 /* Returns true if the node V of RDG cannot be recomputed. */
452 rdg_cannot_recompute_vertex_p (struct graph
*rdg
, int v
)
454 if (RDG_MEM_WRITE_STMT (rdg
, v
))
460 /* Returns true when the vertex V has already been generated in the
461 current partition (V is in PROCESSED), or when V belongs to another
462 partition and cannot be recomputed (V is not in REMAINING_STMTS). */
465 already_processed_vertex_p (bitmap processed
, int v
)
467 return (bitmap_bit_p (processed
, v
)
468 || !bitmap_bit_p (remaining_stmts
, v
));
471 /* Returns NULL when there is no anti-dependence among the successors
472 of vertex V, otherwise returns the edge with the anti-dep. */
474 static struct graph_edge
*
475 has_anti_dependence (struct vertex
*v
)
477 struct graph_edge
*e
;
480 for (e
= v
->succ
; e
; e
= e
->succ_next
)
481 if (RDGE_TYPE (e
) == anti_dd
)
487 /* Returns true when V has an anti-dependence edge among its successors. */
490 predecessor_has_mem_write (struct graph
*rdg
, struct vertex
*v
)
492 struct graph_edge
*e
;
495 for (e
= v
->pred
; e
; e
= e
->pred_next
)
496 if (bitmap_bit_p (upstream_mem_writes
, e
->src
)
497 /* Don't consider flow channels: a write to memory followed
498 by a read from memory. These channels allow the split of
499 the RDG in different partitions. */
500 && !RDG_MEM_WRITE_STMT (rdg
, e
->src
))
506 /* Initializes the upstream_mem_writes bitmap following the
507 information from RDG. */
510 mark_nodes_having_upstream_mem_writes (struct graph
*rdg
)
513 bitmap seen
= BITMAP_ALLOC (NULL
);
515 for (v
= rdg
->n_vertices
- 1; v
>= 0; v
--)
516 if (!bitmap_bit_p (seen
, v
))
519 VEC (int, heap
) *nodes
= VEC_alloc (int, heap
, 3);
521 graphds_dfs (rdg
, &v
, 1, &nodes
, false, NULL
);
523 for (i
= 0; VEC_iterate (int, nodes
, i
, x
); i
++)
525 if (bitmap_bit_p (seen
, x
))
528 bitmap_set_bit (seen
, x
);
530 if (RDG_MEM_WRITE_STMT (rdg
, x
)
531 || predecessor_has_mem_write (rdg
, &(rdg
->vertices
[x
]))
532 /* In anti dependences the read should occur before
533 the write, this is why both the read and the write
534 should be placed in the same partition. */
535 || has_anti_dependence (&(rdg
->vertices
[x
])))
537 bitmap_set_bit (upstream_mem_writes
, x
);
541 VEC_free (int, heap
, nodes
);
545 /* Returns true when vertex u has a memory write node as a predecessor
549 has_upstream_mem_writes (int u
)
551 return bitmap_bit_p (upstream_mem_writes
, u
);
554 static void rdg_flag_vertex_and_dependent (struct graph
*, int, bitmap
, bitmap
,
557 /* Flag all the uses of U. */
560 rdg_flag_all_uses (struct graph
*rdg
, int u
, bitmap partition
, bitmap loops
,
561 bitmap processed
, bool *part_has_writes
)
563 struct graph_edge
*e
;
565 for (e
= rdg
->vertices
[u
].succ
; e
; e
= e
->succ_next
)
566 if (!bitmap_bit_p (processed
, e
->dest
))
568 rdg_flag_vertex_and_dependent (rdg
, e
->dest
, partition
, loops
,
569 processed
, part_has_writes
);
570 rdg_flag_all_uses (rdg
, e
->dest
, partition
, loops
, processed
,
575 /* Flag the uses of U stopping following the information from
576 upstream_mem_writes. */
579 rdg_flag_uses (struct graph
*rdg
, int u
, bitmap partition
, bitmap loops
,
580 bitmap processed
, bool *part_has_writes
)
583 struct vertex
*x
= &(rdg
->vertices
[u
]);
584 gimple stmt
= RDGV_STMT (x
);
585 struct graph_edge
*anti_dep
= has_anti_dependence (x
);
587 /* Keep in the same partition the destination of an antidependence,
588 because this is a store to the exact same location. Putting this
589 in another partition is bad for cache locality. */
592 int v
= anti_dep
->dest
;
594 if (!already_processed_vertex_p (processed
, v
))
595 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
,
596 processed
, part_has_writes
);
599 if (gimple_code (stmt
) != GIMPLE_PHI
)
601 if ((use_p
= gimple_vuse_op (stmt
)) != NULL_USE_OPERAND_P
)
603 tree use
= USE_FROM_PTR (use_p
);
605 if (TREE_CODE (use
) == SSA_NAME
)
607 gimple def_stmt
= SSA_NAME_DEF_STMT (use
);
608 int v
= rdg_vertex_for_stmt (rdg
, def_stmt
);
611 && !already_processed_vertex_p (processed
, v
))
612 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
,
613 processed
, part_has_writes
);
618 if (is_gimple_assign (stmt
) && has_upstream_mem_writes (u
))
620 tree op0
= gimple_assign_lhs (stmt
);
622 /* Scalar channels don't have enough space for transmitting data
623 between tasks, unless we add more storage by privatizing. */
624 if (is_gimple_reg (op0
))
627 imm_use_iterator iter
;
629 FOR_EACH_IMM_USE_FAST (use_p
, iter
, op0
)
631 int v
= rdg_vertex_for_stmt (rdg
, USE_STMT (use_p
));
633 if (!already_processed_vertex_p (processed
, v
))
634 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
,
635 processed
, part_has_writes
);
641 /* Flag V from RDG as part of PARTITION, and also flag its loop number
645 rdg_flag_vertex (struct graph
*rdg
, int v
, bitmap partition
, bitmap loops
,
646 bool *part_has_writes
)
650 if (bitmap_bit_p (partition
, v
))
653 loop
= loop_containing_stmt (RDG_STMT (rdg
, v
));
654 bitmap_set_bit (loops
, loop
->num
);
655 bitmap_set_bit (partition
, v
);
657 if (rdg_cannot_recompute_vertex_p (rdg
, v
))
659 *part_has_writes
= true;
660 bitmap_clear_bit (remaining_stmts
, v
);
664 /* Flag in the bitmap PARTITION the vertex V and all its predecessors.
665 Also flag their loop number in LOOPS. */
668 rdg_flag_vertex_and_dependent (struct graph
*rdg
, int v
, bitmap partition
,
669 bitmap loops
, bitmap processed
,
670 bool *part_has_writes
)
673 VEC (int, heap
) *nodes
= VEC_alloc (int, heap
, 3);
676 bitmap_set_bit (processed
, v
);
677 rdg_flag_uses (rdg
, v
, partition
, loops
, processed
, part_has_writes
);
678 graphds_dfs (rdg
, &v
, 1, &nodes
, false, remaining_stmts
);
679 rdg_flag_vertex (rdg
, v
, partition
, loops
, part_has_writes
);
681 for (i
= 0; VEC_iterate (int, nodes
, i
, x
); i
++)
682 if (!already_processed_vertex_p (processed
, x
))
683 rdg_flag_vertex_and_dependent (rdg
, x
, partition
, loops
, processed
,
686 VEC_free (int, heap
, nodes
);
689 /* Initialize CONDS with all the condition statements from the basic
693 collect_condition_stmts (struct loop
*loop
, VEC (gimple
, heap
) **conds
)
697 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
699 for (i
= 0; VEC_iterate (edge
, exits
, i
, e
); i
++)
701 gimple cond
= last_stmt (e
->src
);
704 VEC_safe_push (gimple
, heap
, *conds
, cond
);
707 VEC_free (edge
, heap
, exits
);
710 /* Add to PARTITION all the exit condition statements for LOOPS
711 together with all their dependent statements determined from
715 rdg_flag_loop_exits (struct graph
*rdg
, bitmap loops
, bitmap partition
,
716 bitmap processed
, bool *part_has_writes
)
720 VEC (gimple
, heap
) *conds
= VEC_alloc (gimple
, heap
, 3);
722 EXECUTE_IF_SET_IN_BITMAP (loops
, 0, i
, bi
)
723 collect_condition_stmts (get_loop (i
), &conds
);
725 while (!VEC_empty (gimple
, conds
))
727 gimple cond
= VEC_pop (gimple
, conds
);
728 int v
= rdg_vertex_for_stmt (rdg
, cond
);
729 bitmap new_loops
= BITMAP_ALLOC (NULL
);
731 if (!already_processed_vertex_p (processed
, v
))
732 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, new_loops
, processed
,
735 EXECUTE_IF_SET_IN_BITMAP (new_loops
, 0, i
, bi
)
736 if (!bitmap_bit_p (loops
, i
))
738 bitmap_set_bit (loops
, i
);
739 collect_condition_stmts (get_loop (i
), &conds
);
742 BITMAP_FREE (new_loops
);
746 /* Flag all the nodes of RDG containing memory accesses that could
747 potentially belong to arrays already accessed in the current
751 rdg_flag_similar_memory_accesses (struct graph
*rdg
, bitmap partition
,
752 bitmap loops
, bitmap processed
,
753 VEC (int, heap
) **other_stores
)
759 struct graph_edge
*e
;
761 EXECUTE_IF_SET_IN_BITMAP (partition
, 0, i
, ii
)
762 if (RDG_MEM_WRITE_STMT (rdg
, i
)
763 || RDG_MEM_READS_STMT (rdg
, i
))
765 for (j
= 0; j
< rdg
->n_vertices
; j
++)
766 if (!bitmap_bit_p (processed
, j
)
767 && (RDG_MEM_WRITE_STMT (rdg
, j
)
768 || RDG_MEM_READS_STMT (rdg
, j
))
769 && rdg_has_similar_memory_accesses (rdg
, i
, j
))
771 /* Flag first the node J itself, and all the nodes that
772 are needed to compute J. */
773 rdg_flag_vertex_and_dependent (rdg
, j
, partition
, loops
,
776 /* When J is a read, we want to coalesce in the same
777 PARTITION all the nodes that are using J: this is
778 needed for better cache locality. */
779 rdg_flag_all_uses (rdg
, j
, partition
, loops
, processed
, &foo
);
781 /* Remove from OTHER_STORES the vertex that we flagged. */
782 if (RDG_MEM_WRITE_STMT (rdg
, j
))
783 for (k
= 0; VEC_iterate (int, *other_stores
, k
, kk
); k
++)
786 VEC_unordered_remove (int, *other_stores
, k
);
791 /* If the node I has two uses, then keep these together in the
793 for (n
= 0, e
= rdg
->vertices
[i
].succ
; e
; e
= e
->succ_next
, n
++);
796 rdg_flag_all_uses (rdg
, i
, partition
, loops
, processed
, &foo
);
800 /* Returns a bitmap in which all the statements needed for computing
801 the strongly connected component C of the RDG are flagged, also
802 including the loop exit conditions. */
805 build_rdg_partition_for_component (struct graph
*rdg
, rdgc c
,
806 bool *part_has_writes
,
807 VEC (int, heap
) **other_stores
)
810 bitmap partition
= BITMAP_ALLOC (NULL
);
811 bitmap loops
= BITMAP_ALLOC (NULL
);
812 bitmap processed
= BITMAP_ALLOC (NULL
);
814 for (i
= 0; VEC_iterate (int, c
->vertices
, i
, v
); i
++)
815 if (!already_processed_vertex_p (processed
, v
))
816 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
, processed
,
819 /* Also iterate on the array of stores not in the starting vertices,
820 and determine those vertices that have some memory affinity with
821 the current nodes in the component: these are stores to the same
822 arrays, i.e. we're taking care of cache locality. */
823 rdg_flag_similar_memory_accesses (rdg
, partition
, loops
, processed
,
826 rdg_flag_loop_exits (rdg
, loops
, partition
, processed
, part_has_writes
);
828 BITMAP_FREE (processed
);
833 /* Free memory for COMPONENTS. */
836 free_rdg_components (VEC (rdgc
, heap
) *components
)
841 for (i
= 0; VEC_iterate (rdgc
, components
, i
, x
); i
++)
843 VEC_free (int, heap
, x
->vertices
);
848 /* Build the COMPONENTS vector with the strongly connected components
849 of RDG in which the STARTING_VERTICES occur. */
852 rdg_build_components (struct graph
*rdg
, VEC (int, heap
) *starting_vertices
,
853 VEC (rdgc
, heap
) **components
)
856 bitmap saved_components
= BITMAP_ALLOC (NULL
);
857 int n_components
= graphds_scc (rdg
, NULL
);
858 VEC (int, heap
) **all_components
= XNEWVEC (VEC (int, heap
) *, n_components
);
860 for (i
= 0; i
< n_components
; i
++)
861 all_components
[i
] = VEC_alloc (int, heap
, 3);
863 for (i
= 0; i
< rdg
->n_vertices
; i
++)
864 VEC_safe_push (int, heap
, all_components
[rdg
->vertices
[i
].component
], i
);
866 for (i
= 0; VEC_iterate (int, starting_vertices
, i
, v
); i
++)
868 int c
= rdg
->vertices
[v
].component
;
870 if (!bitmap_bit_p (saved_components
, c
))
872 rdgc x
= XCNEW (struct rdg_component
);
874 x
->vertices
= all_components
[c
];
876 VEC_safe_push (rdgc
, heap
, *components
, x
);
877 bitmap_set_bit (saved_components
, c
);
881 for (i
= 0; i
< n_components
; i
++)
882 if (!bitmap_bit_p (saved_components
, i
))
883 VEC_free (int, heap
, all_components
[i
]);
885 free (all_components
);
886 BITMAP_FREE (saved_components
);
889 /* Aggregate several components into a useful partition that is
890 registered in the PARTITIONS vector. Partitions will be
891 distributed in different loops. */
894 rdg_build_partitions (struct graph
*rdg
, VEC (rdgc
, heap
) *components
,
895 VEC (int, heap
) **other_stores
,
896 VEC (bitmap
, heap
) **partitions
, bitmap processed
)
900 bitmap partition
= BITMAP_ALLOC (NULL
);
902 for (i
= 0; VEC_iterate (rdgc
, components
, i
, x
); i
++)
905 bool part_has_writes
= false;
906 int v
= VEC_index (int, x
->vertices
, 0);
908 if (bitmap_bit_p (processed
, v
))
911 np
= build_rdg_partition_for_component (rdg
, x
, &part_has_writes
,
913 bitmap_ior_into (partition
, np
);
914 bitmap_ior_into (processed
, np
);
919 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
921 fprintf (dump_file
, "ldist useful partition:\n");
922 dump_bitmap (dump_file
, partition
);
925 VEC_safe_push (bitmap
, heap
, *partitions
, partition
);
926 partition
= BITMAP_ALLOC (NULL
);
930 /* Add the nodes from the RDG that were not marked as processed, and
931 that are used outside the current loop. These are scalar
932 computations that are not yet part of previous partitions. */
933 for (i
= 0; i
< rdg
->n_vertices
; i
++)
934 if (!bitmap_bit_p (processed
, i
)
935 && rdg_defs_used_in_other_loops_p (rdg
, i
))
936 VEC_safe_push (int, heap
, *other_stores
, i
);
938 /* If there are still statements left in the OTHER_STORES array,
939 create other components and partitions with these stores and
940 their dependences. */
941 if (VEC_length (int, *other_stores
) > 0)
943 VEC (rdgc
, heap
) *comps
= VEC_alloc (rdgc
, heap
, 3);
944 VEC (int, heap
) *foo
= VEC_alloc (int, heap
, 3);
946 rdg_build_components (rdg
, *other_stores
, &comps
);
947 rdg_build_partitions (rdg
, comps
, &foo
, partitions
, processed
);
949 VEC_free (int, heap
, foo
);
950 free_rdg_components (comps
);
953 /* If there is something left in the last partition, save it. */
954 if (bitmap_count_bits (partition
) > 0)
955 VEC_safe_push (bitmap
, heap
, *partitions
, partition
);
957 BITMAP_FREE (partition
);
960 /* Dump to FILE the PARTITIONS. */
963 dump_rdg_partitions (FILE *file
, VEC (bitmap
, heap
) *partitions
)
968 for (i
= 0; VEC_iterate (bitmap
, partitions
, i
, partition
); i
++)
969 debug_bitmap_file (file
, partition
);
972 /* Debug PARTITIONS. */
973 extern void debug_rdg_partitions (VEC (bitmap
, heap
) *);
976 debug_rdg_partitions (VEC (bitmap
, heap
) *partitions
)
978 dump_rdg_partitions (stderr
, partitions
);
981 /* Returns the number of read and write operations in the RDG. */
984 number_of_rw_in_rdg (struct graph
*rdg
)
988 for (i
= 0; i
< rdg
->n_vertices
; i
++)
990 if (RDG_MEM_WRITE_STMT (rdg
, i
))
993 if (RDG_MEM_READS_STMT (rdg
, i
))
1000 /* Returns the number of read and write operations in a PARTITION of
1004 number_of_rw_in_partition (struct graph
*rdg
, bitmap partition
)
1010 EXECUTE_IF_SET_IN_BITMAP (partition
, 0, i
, ii
)
1012 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1015 if (RDG_MEM_READS_STMT (rdg
, i
))
1022 /* Returns true when one of the PARTITIONS contains all the read or
1023 write operations of RDG. */
1026 partition_contains_all_rw (struct graph
*rdg
, VEC (bitmap
, heap
) *partitions
)
1030 int nrw
= number_of_rw_in_rdg (rdg
);
1032 for (i
= 0; VEC_iterate (bitmap
, partitions
, i
, partition
); i
++)
1033 if (nrw
== number_of_rw_in_partition (rdg
, partition
))
1039 /* Generate code from STARTING_VERTICES in RDG. Returns the number of
1040 distributed loops. */
1043 ldist_gen (struct loop
*loop
, struct graph
*rdg
,
1044 VEC (int, heap
) *starting_vertices
)
1047 VEC (rdgc
, heap
) *components
= VEC_alloc (rdgc
, heap
, 3);
1048 VEC (bitmap
, heap
) *partitions
= VEC_alloc (bitmap
, heap
, 3);
1049 VEC (int, heap
) *other_stores
= VEC_alloc (int, heap
, 3);
1050 bitmap partition
, processed
= BITMAP_ALLOC (NULL
);
1052 remaining_stmts
= BITMAP_ALLOC (NULL
);
1053 upstream_mem_writes
= BITMAP_ALLOC (NULL
);
1055 for (i
= 0; i
< rdg
->n_vertices
; i
++)
1057 bitmap_set_bit (remaining_stmts
, i
);
1059 /* Save in OTHER_STORES all the memory writes that are not in
1060 STARTING_VERTICES. */
1061 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1067 for (j
= 0; VEC_iterate (int, starting_vertices
, j
, v
); j
++)
1075 VEC_safe_push (int, heap
, other_stores
, i
);
1079 mark_nodes_having_upstream_mem_writes (rdg
);
1080 rdg_build_components (rdg
, starting_vertices
, &components
);
1081 rdg_build_partitions (rdg
, components
, &other_stores
, &partitions
,
1083 BITMAP_FREE (processed
);
1084 nbp
= VEC_length (bitmap
, partitions
);
1087 || partition_contains_all_rw (rdg
, partitions
))
1090 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1091 dump_rdg_partitions (dump_file
, partitions
);
1093 for (i
= 0; VEC_iterate (bitmap
, partitions
, i
, partition
); i
++)
1094 if (!generate_code_for_partition (loop
, partition
, i
< nbp
- 1))
1097 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1098 update_ssa (TODO_update_ssa_only_virtuals
| TODO_update_ssa
);
1102 BITMAP_FREE (remaining_stmts
);
1103 BITMAP_FREE (upstream_mem_writes
);
1105 for (i
= 0; VEC_iterate (bitmap
, partitions
, i
, partition
); i
++)
1106 BITMAP_FREE (partition
);
1108 VEC_free (int, heap
, other_stores
);
1109 VEC_free (bitmap
, heap
, partitions
);
1110 free_rdg_components (components
);
1114 /* Distributes the code from LOOP in such a way that producer
1115 statements are placed before consumer statements. When STMTS is
1116 NULL, performs the maximal distribution, if STMTS is not NULL,
1117 tries to separate only these statements from the LOOP's body.
1118 Returns the number of distributed loops. */
1121 distribute_loop (struct loop
*loop
, VEC (gimple
, heap
) *stmts
)
1127 VEC (int, heap
) *vertices
;
1129 if (loop
->num_nodes
> 2)
1131 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1133 "FIXME: Loop %d not distributed: it has more than two basic blocks.\n",
1139 rdg
= build_rdg (loop
);
1143 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1145 "FIXME: Loop %d not distributed: failed to build the RDG.\n",
1151 vertices
= VEC_alloc (int, heap
, 3);
1153 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1154 dump_rdg (dump_file
, rdg
);
1156 for (i
= 0; VEC_iterate (gimple
, stmts
, i
, s
); i
++)
1158 int v
= rdg_vertex_for_stmt (rdg
, s
);
1162 VEC_safe_push (int, heap
, vertices
, v
);
1164 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1166 "ldist asked to generate code for vertex %d\n", v
);
1170 res
= ldist_gen (loop
, rdg
, vertices
);
1171 VEC_free (int, heap
, vertices
);
1177 /* Distribute all loops in the current function. */
1180 tree_loop_distribution (void)
1184 int nb_generated_loops
= 0;
1186 FOR_EACH_LOOP (li
, loop
, 0)
1188 VEC (gimple
, heap
) *work_list
= VEC_alloc (gimple
, heap
, 3);
1190 /* With the following working list, we're asking distribute_loop
1191 to separate the stores of the loop: when dependences allow,
1192 it will end on having one store per loop. */
1193 stores_from_loop (loop
, &work_list
);
1195 /* A simple heuristic for cache locality is to not split stores
1196 to the same array. Without this call, an unrolled loop would
1197 be split into as many loops as unroll factor, each loop
1198 storing in the same array. */
1199 remove_similar_memory_refs (&work_list
);
1201 nb_generated_loops
= distribute_loop (loop
, work_list
);
1203 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1205 if (nb_generated_loops
> 1)
1206 fprintf (dump_file
, "Loop %d distributed: split to %d loops.\n",
1207 loop
->num
, nb_generated_loops
);
1209 fprintf (dump_file
, "Loop %d is the same.\n", loop
->num
);
1212 verify_loop_structure ();
1214 VEC_free (gimple
, heap
, work_list
);
1221 gate_tree_loop_distribution (void)
1223 return flag_tree_loop_distribution
!= 0;
1226 struct gimple_opt_pass pass_loop_distribution
=
1231 gate_tree_loop_distribution
, /* gate */
1232 tree_loop_distribution
, /* execute */
1235 0, /* static_pass_number */
1236 TV_TREE_LOOP_DISTRIBUTION
, /* tv_id */
1237 PROP_cfg
| PROP_ssa
, /* properties_required */
1238 0, /* properties_provided */
1239 0, /* properties_destroyed */
1240 0, /* todo_flags_start */
1241 TODO_dump_func
| TODO_verify_loops
/* todo_flags_finish */