2 Copyright (C) 2006, 2007, 2008, 2009, 2010, 2011
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"
48 #include "tree-flow.h"
50 #include "tree-chrec.h"
51 #include "tree-data-ref.h"
52 #include "tree-scalar-evolution.h"
53 #include "tree-pass.h"
55 /* If bit I is not set, it means that this node represents an
56 operation that has already been performed, and that should not be
57 performed again. This is the subgraph of remaining important
58 computations that is passed to the DFS algorithm for avoiding to
59 include several times the same stores in different loops. */
60 static bitmap remaining_stmts
;
62 /* A node of the RDG is marked in this bitmap when it has as a
63 predecessor a node that writes to memory. */
64 static bitmap upstream_mem_writes
;
66 /* Returns true when DEF is an SSA_NAME defined in LOOP and used after
70 ssa_name_has_uses_outside_loop_p (tree def
, loop_p loop
)
72 imm_use_iterator imm_iter
;
75 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
76 if (loop
!= loop_containing_stmt (USE_STMT (use_p
)))
82 /* Returns true when STMT defines a scalar variable used after the
86 stmt_has_scalar_dependences_outside_loop (gimple stmt
)
90 switch (gimple_code (stmt
))
94 name
= gimple_get_lhs (stmt
);
98 name
= gimple_phi_result (stmt
);
106 && TREE_CODE (name
) == SSA_NAME
107 && ssa_name_has_uses_outside_loop_p (name
,
108 loop_containing_stmt (stmt
)));
111 /* Update the PHI nodes of NEW_LOOP. NEW_LOOP is a duplicate of
115 update_phis_for_loop_copy (struct loop
*orig_loop
, struct loop
*new_loop
)
118 gimple_stmt_iterator si_new
, si_orig
;
119 edge orig_loop_latch
= loop_latch_edge (orig_loop
);
120 edge orig_entry_e
= loop_preheader_edge (orig_loop
);
121 edge new_loop_entry_e
= loop_preheader_edge (new_loop
);
123 /* Scan the phis in the headers of the old and new loops
124 (they are organized in exactly the same order). */
125 for (si_new
= gsi_start_phis (new_loop
->header
),
126 si_orig
= gsi_start_phis (orig_loop
->header
);
127 !gsi_end_p (si_new
) && !gsi_end_p (si_orig
);
128 gsi_next (&si_new
), gsi_next (&si_orig
))
131 source_location locus
;
132 gimple phi_new
= gsi_stmt (si_new
);
133 gimple phi_orig
= gsi_stmt (si_orig
);
135 /* Add the first phi argument for the phi in NEW_LOOP (the one
136 associated with the entry of NEW_LOOP) */
137 def
= PHI_ARG_DEF_FROM_EDGE (phi_orig
, orig_entry_e
);
138 locus
= gimple_phi_arg_location_from_edge (phi_orig
, orig_entry_e
);
139 add_phi_arg (phi_new
, def
, new_loop_entry_e
, locus
);
141 /* Add the second phi argument for the phi in NEW_LOOP (the one
142 associated with the latch of NEW_LOOP) */
143 def
= PHI_ARG_DEF_FROM_EDGE (phi_orig
, orig_loop_latch
);
144 locus
= gimple_phi_arg_location_from_edge (phi_orig
, orig_loop_latch
);
146 if (TREE_CODE (def
) == SSA_NAME
)
148 new_ssa_name
= get_current_def (def
);
151 /* This only happens if there are no definitions inside the
152 loop. Use the the invariant in the new loop as is. */
156 /* Could be an integer. */
159 add_phi_arg (phi_new
, new_ssa_name
, loop_latch_edge (new_loop
), locus
);
163 /* Return a copy of LOOP placed before LOOP. */
166 copy_loop_before (struct loop
*loop
)
169 edge preheader
= loop_preheader_edge (loop
);
171 if (!single_exit (loop
))
174 initialize_original_copy_tables ();
175 res
= slpeel_tree_duplicate_loop_to_edge_cfg (loop
, preheader
);
176 free_original_copy_tables ();
181 update_phis_for_loop_copy (loop
, res
);
182 rename_variables_in_loop (res
);
187 /* Creates an empty basic block after LOOP. */
190 create_bb_after_loop (struct loop
*loop
)
192 edge exit
= single_exit (loop
);
200 /* Generate code for PARTITION from the code in LOOP. The loop is
201 copied when COPY_P is true. All the statements not flagged in the
202 PARTITION bitmap are removed from the loop or from its copy. The
203 statements are indexed in sequence inside a basic block, and the
204 basic blocks of a loop are taken in dom order. Returns true when
205 the code gen succeeded. */
208 generate_loops_for_partition (struct loop
*loop
, bitmap partition
, bool copy_p
)
211 gimple_stmt_iterator bsi
;
216 loop
= copy_loop_before (loop
);
217 create_preheader (loop
, CP_SIMPLE_PREHEADERS
);
218 create_bb_after_loop (loop
);
224 /* Remove stmts not in the PARTITION bitmap. The order in which we
225 visit the phi nodes and the statements is exactly as in
227 bbs
= get_loop_body_in_dom_order (loop
);
229 if (MAY_HAVE_DEBUG_STMTS
)
230 for (x
= 0, i
= 0; i
< loop
->num_nodes
; i
++)
232 basic_block bb
= bbs
[i
];
234 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
235 if (!bitmap_bit_p (partition
, x
++))
236 reset_debug_uses (gsi_stmt (bsi
));
238 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
240 gimple stmt
= gsi_stmt (bsi
);
241 if (gimple_code (stmt
) != GIMPLE_LABEL
242 && !is_gimple_debug (stmt
)
243 && !bitmap_bit_p (partition
, x
++))
244 reset_debug_uses (stmt
);
248 for (x
= 0, i
= 0; i
< loop
->num_nodes
; i
++)
250 basic_block bb
= bbs
[i
];
252 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);)
253 if (!bitmap_bit_p (partition
, x
++))
255 gimple phi
= gsi_stmt (bsi
);
256 if (!is_gimple_reg (gimple_phi_result (phi
)))
257 mark_virtual_phi_result_for_renaming (phi
);
258 remove_phi_node (&bsi
, true);
263 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);)
265 gimple stmt
= gsi_stmt (bsi
);
266 if (gimple_code (stmt
) != GIMPLE_LABEL
267 && !is_gimple_debug (stmt
)
268 && !bitmap_bit_p (partition
, x
++))
270 unlink_stmt_vdef (stmt
);
271 gsi_remove (&bsi
, true);
283 /* Build the size argument for a memset call. */
286 build_size_arg_loc (location_t loc
, tree nb_iter
, tree op
,
287 gimple_seq
*stmt_list
)
290 tree x
= fold_build2_loc (loc
, MULT_EXPR
, size_type_node
,
291 fold_convert_loc (loc
, size_type_node
, nb_iter
),
292 fold_convert_loc (loc
, size_type_node
,
293 TYPE_SIZE_UNIT (TREE_TYPE (op
))));
294 x
= force_gimple_operand (x
, &stmts
, true, NULL
);
295 gimple_seq_add_seq (stmt_list
, stmts
);
300 /* Generate a call to memset. Return true when the operation succeeded. */
303 generate_memset_zero (gimple stmt
, tree op0
, tree nb_iter
,
304 gimple_stmt_iterator bsi
)
306 tree addr_base
, nb_bytes
;
308 gimple_seq stmt_list
= NULL
, stmts
;
311 struct data_reference
*dr
= XCNEW (struct data_reference
);
312 location_t loc
= gimple_location (stmt
);
316 res
= dr_analyze_innermost (dr
, loop_containing_stmt (stmt
));
317 gcc_assert (res
&& stride_of_unit_type_p (DR_STEP (dr
), TREE_TYPE (op0
)));
319 nb_bytes
= build_size_arg_loc (loc
, nb_iter
, op0
, &stmt_list
);
320 addr_base
= size_binop_loc (loc
, PLUS_EXPR
, DR_OFFSET (dr
), DR_INIT (dr
));
321 addr_base
= fold_convert_loc (loc
, sizetype
, addr_base
);
323 /* Test for a negative stride, iterating over every element. */
324 if (tree_int_cst_sgn (DR_STEP (dr
)) == -1)
326 addr_base
= size_binop_loc (loc
, MINUS_EXPR
, addr_base
,
327 fold_convert_loc (loc
, sizetype
, nb_bytes
));
328 addr_base
= size_binop_loc (loc
, PLUS_EXPR
, addr_base
,
329 TYPE_SIZE_UNIT (TREE_TYPE (op0
)));
332 addr_base
= fold_build_pointer_plus_loc (loc
,
333 DR_BASE_ADDRESS (dr
), addr_base
);
334 mem
= force_gimple_operand (addr_base
, &stmts
, true, NULL
);
335 gimple_seq_add_seq (&stmt_list
, stmts
);
337 fn
= build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET
));
338 fn_call
= gimple_build_call (fn
, 3, mem
, integer_zero_node
, nb_bytes
);
339 gimple_seq_add_stmt (&stmt_list
, fn_call
);
340 gsi_insert_seq_after (&bsi
, stmt_list
, GSI_CONTINUE_LINKING
);
342 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
343 fprintf (dump_file
, "generated memset zero\n");
348 /* Tries to generate a builtin function for the instructions of LOOP
349 pointed to by the bits set in PARTITION. Returns true when the
350 operation succeeded. */
353 generate_builtin (struct loop
*loop
, bitmap partition
, bool copy_p
)
359 gimple_stmt_iterator bsi
;
360 tree nb_iter
= number_of_exit_cond_executions (loop
);
362 if (!nb_iter
|| nb_iter
== chrec_dont_know
)
365 bbs
= get_loop_body_in_dom_order (loop
);
367 for (i
= 0; i
< loop
->num_nodes
; i
++)
369 basic_block bb
= bbs
[i
];
371 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
374 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
376 gimple stmt
= gsi_stmt (bsi
);
378 if (gimple_code (stmt
) == GIMPLE_LABEL
379 || is_gimple_debug (stmt
))
382 if (!bitmap_bit_p (partition
, x
++))
385 /* If the stmt has uses outside of the loop fail. */
386 if (stmt_has_scalar_dependences_outside_loop (stmt
))
389 if (is_gimple_assign (stmt
)
390 && !is_gimple_reg (gimple_assign_lhs (stmt
)))
392 /* Don't generate the builtins when there are more than
398 if (bb
== loop
->latch
)
399 nb_iter
= number_of_latch_executions (loop
);
404 if (!stmt_with_adjacent_zero_store_dr_p (write
))
407 /* The new statements will be placed before LOOP. */
408 bsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
409 generate_memset_zero (write
, gimple_assign_lhs (write
), nb_iter
, bsi
);
412 /* If this is the last partition for which we generate code, we have
413 to destroy the loop. */
416 unsigned nbbs
= loop
->num_nodes
;
417 edge exit
= single_exit (loop
);
418 basic_block src
= loop_preheader_edge (loop
)->src
, dest
= exit
->dest
;
419 redirect_edge_pred (exit
, src
);
420 exit
->flags
&= ~(EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
421 exit
->flags
|= EDGE_FALLTHRU
;
422 cancel_loop_tree (loop
);
423 rescan_loop_exit (exit
, false, true);
425 for (i
= 0; i
< nbbs
; i
++)
426 delete_basic_block (bbs
[i
]);
428 set_immediate_dominator (CDI_DOMINATORS
, dest
,
429 recompute_dominator (CDI_DOMINATORS
, dest
));
437 /* Generates code for PARTITION. For simple loops, this function can
438 generate a built-in. */
441 generate_code_for_partition (struct loop
*loop
, bitmap partition
, bool copy_p
)
443 if (generate_builtin (loop
, partition
, copy_p
))
446 return generate_loops_for_partition (loop
, partition
, copy_p
);
450 /* Returns true if the node V of RDG cannot be recomputed. */
453 rdg_cannot_recompute_vertex_p (struct graph
*rdg
, int v
)
455 if (RDG_MEM_WRITE_STMT (rdg
, v
))
461 /* Returns true when the vertex V has already been generated in the
462 current partition (V is in PROCESSED), or when V belongs to another
463 partition and cannot be recomputed (V is not in REMAINING_STMTS). */
466 already_processed_vertex_p (bitmap processed
, int v
)
468 return (bitmap_bit_p (processed
, v
)
469 || !bitmap_bit_p (remaining_stmts
, v
));
472 /* Returns NULL when there is no anti-dependence among the successors
473 of vertex V, otherwise returns the edge with the anti-dep. */
475 static struct graph_edge
*
476 has_anti_dependence (struct vertex
*v
)
478 struct graph_edge
*e
;
481 for (e
= v
->succ
; e
; e
= e
->succ_next
)
482 if (RDGE_TYPE (e
) == anti_dd
)
488 /* Returns true when V has an anti-dependence edge among its successors. */
491 predecessor_has_mem_write (struct graph
*rdg
, struct vertex
*v
)
493 struct graph_edge
*e
;
496 for (e
= v
->pred
; e
; e
= e
->pred_next
)
497 if (bitmap_bit_p (upstream_mem_writes
, e
->src
)
498 /* Don't consider flow channels: a write to memory followed
499 by a read from memory. These channels allow the split of
500 the RDG in different partitions. */
501 && !RDG_MEM_WRITE_STMT (rdg
, e
->src
))
507 /* Initializes the upstream_mem_writes bitmap following the
508 information from RDG. */
511 mark_nodes_having_upstream_mem_writes (struct graph
*rdg
)
514 bitmap seen
= BITMAP_ALLOC (NULL
);
516 for (v
= rdg
->n_vertices
- 1; v
>= 0; v
--)
517 if (!bitmap_bit_p (seen
, v
))
520 VEC (int, heap
) *nodes
= VEC_alloc (int, heap
, 3);
522 graphds_dfs (rdg
, &v
, 1, &nodes
, false, NULL
);
524 FOR_EACH_VEC_ELT (int, nodes
, i
, x
)
526 if (!bitmap_set_bit (seen
, x
))
529 if (RDG_MEM_WRITE_STMT (rdg
, x
)
530 || predecessor_has_mem_write (rdg
, &(rdg
->vertices
[x
]))
531 /* In anti dependences the read should occur before
532 the write, this is why both the read and the write
533 should be placed in the same partition. */
534 || has_anti_dependence (&(rdg
->vertices
[x
])))
536 bitmap_set_bit (upstream_mem_writes
, x
);
540 VEC_free (int, heap
, nodes
);
544 /* Returns true when vertex u has a memory write node as a predecessor
548 has_upstream_mem_writes (int u
)
550 return bitmap_bit_p (upstream_mem_writes
, u
);
553 static void rdg_flag_vertex_and_dependent (struct graph
*, int, bitmap
, bitmap
,
556 /* Flag the uses of U stopping following the information from
557 upstream_mem_writes. */
560 rdg_flag_uses (struct graph
*rdg
, int u
, bitmap partition
, bitmap loops
,
561 bitmap processed
, bool *part_has_writes
)
564 struct vertex
*x
= &(rdg
->vertices
[u
]);
565 gimple stmt
= RDGV_STMT (x
);
566 struct graph_edge
*anti_dep
= has_anti_dependence (x
);
568 /* Keep in the same partition the destination of an antidependence,
569 because this is a store to the exact same location. Putting this
570 in another partition is bad for cache locality. */
573 int v
= anti_dep
->dest
;
575 if (!already_processed_vertex_p (processed
, v
))
576 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
,
577 processed
, part_has_writes
);
580 if (gimple_code (stmt
) != GIMPLE_PHI
)
582 if ((use_p
= gimple_vuse_op (stmt
)) != NULL_USE_OPERAND_P
)
584 tree use
= USE_FROM_PTR (use_p
);
586 if (TREE_CODE (use
) == SSA_NAME
)
588 gimple def_stmt
= SSA_NAME_DEF_STMT (use
);
589 int v
= rdg_vertex_for_stmt (rdg
, def_stmt
);
592 && !already_processed_vertex_p (processed
, v
))
593 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
,
594 processed
, part_has_writes
);
599 if (is_gimple_assign (stmt
) && has_upstream_mem_writes (u
))
601 tree op0
= gimple_assign_lhs (stmt
);
603 /* Scalar channels don't have enough space for transmitting data
604 between tasks, unless we add more storage by privatizing. */
605 if (is_gimple_reg (op0
))
608 imm_use_iterator iter
;
610 FOR_EACH_IMM_USE_FAST (use_p
, iter
, op0
)
612 int v
= rdg_vertex_for_stmt (rdg
, USE_STMT (use_p
));
614 if (!already_processed_vertex_p (processed
, v
))
615 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
,
616 processed
, part_has_writes
);
622 /* Flag V from RDG as part of PARTITION, and also flag its loop number
626 rdg_flag_vertex (struct graph
*rdg
, int v
, bitmap partition
, bitmap loops
,
627 bool *part_has_writes
)
631 if (!bitmap_set_bit (partition
, v
))
634 loop
= loop_containing_stmt (RDG_STMT (rdg
, v
));
635 bitmap_set_bit (loops
, loop
->num
);
637 if (rdg_cannot_recompute_vertex_p (rdg
, v
))
639 *part_has_writes
= true;
640 bitmap_clear_bit (remaining_stmts
, v
);
644 /* Flag in the bitmap PARTITION the vertex V and all its predecessors.
645 Also flag their loop number in LOOPS. */
648 rdg_flag_vertex_and_dependent (struct graph
*rdg
, int v
, bitmap partition
,
649 bitmap loops
, bitmap processed
,
650 bool *part_has_writes
)
653 VEC (int, heap
) *nodes
= VEC_alloc (int, heap
, 3);
656 bitmap_set_bit (processed
, v
);
657 rdg_flag_uses (rdg
, v
, partition
, loops
, processed
, part_has_writes
);
658 graphds_dfs (rdg
, &v
, 1, &nodes
, false, remaining_stmts
);
659 rdg_flag_vertex (rdg
, v
, partition
, loops
, part_has_writes
);
661 FOR_EACH_VEC_ELT (int, nodes
, i
, x
)
662 if (!already_processed_vertex_p (processed
, x
))
663 rdg_flag_vertex_and_dependent (rdg
, x
, partition
, loops
, processed
,
666 VEC_free (int, heap
, nodes
);
669 /* Initialize CONDS with all the condition statements from the basic
673 collect_condition_stmts (struct loop
*loop
, VEC (gimple
, heap
) **conds
)
677 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
679 FOR_EACH_VEC_ELT (edge
, exits
, i
, e
)
681 gimple cond
= last_stmt (e
->src
);
684 VEC_safe_push (gimple
, heap
, *conds
, cond
);
687 VEC_free (edge
, heap
, exits
);
690 /* Add to PARTITION all the exit condition statements for LOOPS
691 together with all their dependent statements determined from
695 rdg_flag_loop_exits (struct graph
*rdg
, bitmap loops
, bitmap partition
,
696 bitmap processed
, bool *part_has_writes
)
700 VEC (gimple
, heap
) *conds
= VEC_alloc (gimple
, heap
, 3);
702 EXECUTE_IF_SET_IN_BITMAP (loops
, 0, i
, bi
)
703 collect_condition_stmts (get_loop (i
), &conds
);
705 while (!VEC_empty (gimple
, conds
))
707 gimple cond
= VEC_pop (gimple
, conds
);
708 int v
= rdg_vertex_for_stmt (rdg
, cond
);
709 bitmap new_loops
= BITMAP_ALLOC (NULL
);
711 if (!already_processed_vertex_p (processed
, v
))
712 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, new_loops
, processed
,
715 EXECUTE_IF_SET_IN_BITMAP (new_loops
, 0, i
, bi
)
716 if (bitmap_set_bit (loops
, i
))
717 collect_condition_stmts (get_loop (i
), &conds
);
719 BITMAP_FREE (new_loops
);
722 VEC_free (gimple
, heap
, conds
);
725 /* Returns a bitmap in which all the statements needed for computing
726 the strongly connected component C of the RDG are flagged, also
727 including the loop exit conditions. */
730 build_rdg_partition_for_component (struct graph
*rdg
, rdgc c
,
731 bool *part_has_writes
)
734 bitmap partition
= BITMAP_ALLOC (NULL
);
735 bitmap loops
= BITMAP_ALLOC (NULL
);
736 bitmap processed
= BITMAP_ALLOC (NULL
);
738 FOR_EACH_VEC_ELT (int, c
->vertices
, i
, v
)
739 if (!already_processed_vertex_p (processed
, v
))
740 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
, processed
,
743 rdg_flag_loop_exits (rdg
, loops
, partition
, processed
, part_has_writes
);
745 BITMAP_FREE (processed
);
750 /* Free memory for COMPONENTS. */
753 free_rdg_components (VEC (rdgc
, heap
) *components
)
758 FOR_EACH_VEC_ELT (rdgc
, components
, i
, x
)
760 VEC_free (int, heap
, x
->vertices
);
764 VEC_free (rdgc
, heap
, components
);
767 /* Build the COMPONENTS vector with the strongly connected components
768 of RDG in which the STARTING_VERTICES occur. */
771 rdg_build_components (struct graph
*rdg
, VEC (int, heap
) *starting_vertices
,
772 VEC (rdgc
, heap
) **components
)
775 bitmap saved_components
= BITMAP_ALLOC (NULL
);
776 int n_components
= graphds_scc (rdg
, NULL
);
777 VEC (int, heap
) **all_components
= XNEWVEC (VEC (int, heap
) *, n_components
);
779 for (i
= 0; i
< n_components
; i
++)
780 all_components
[i
] = VEC_alloc (int, heap
, 3);
782 for (i
= 0; i
< rdg
->n_vertices
; i
++)
783 VEC_safe_push (int, heap
, all_components
[rdg
->vertices
[i
].component
], i
);
785 FOR_EACH_VEC_ELT (int, starting_vertices
, i
, v
)
787 int c
= rdg
->vertices
[v
].component
;
789 if (bitmap_set_bit (saved_components
, c
))
791 rdgc x
= XCNEW (struct rdg_component
);
793 x
->vertices
= all_components
[c
];
795 VEC_safe_push (rdgc
, heap
, *components
, x
);
799 for (i
= 0; i
< n_components
; i
++)
800 if (!bitmap_bit_p (saved_components
, i
))
801 VEC_free (int, heap
, all_components
[i
]);
803 free (all_components
);
804 BITMAP_FREE (saved_components
);
807 /* Returns true when it is possible to generate a builtin pattern for
808 the PARTITION of RDG. For the moment we detect only the memset
812 can_generate_builtin (struct graph
*rdg
, bitmap partition
)
820 EXECUTE_IF_SET_IN_BITMAP (partition
, 0, i
, bi
)
821 if (RDG_MEM_READS_STMT (rdg
, i
))
823 else if (RDG_MEM_WRITE_STMT (rdg
, i
))
826 if (stmt_with_adjacent_zero_store_dr_p (RDG_STMT (rdg
, i
)))
830 return stores_zero
== 1 && nb_writes
== 1 && nb_reads
== 0;
833 /* Returns true when PARTITION1 and PARTITION2 have similar memory
837 similar_memory_accesses (struct graph
*rdg
, bitmap partition1
,
841 bitmap_iterator bi
, bj
;
843 EXECUTE_IF_SET_IN_BITMAP (partition1
, 0, i
, bi
)
844 if (RDG_MEM_WRITE_STMT (rdg
, i
)
845 || RDG_MEM_READS_STMT (rdg
, i
))
846 EXECUTE_IF_SET_IN_BITMAP (partition2
, 0, j
, bj
)
847 if (RDG_MEM_WRITE_STMT (rdg
, j
)
848 || RDG_MEM_READS_STMT (rdg
, j
))
849 if (rdg_has_similar_memory_accesses (rdg
, i
, j
))
855 /* Fuse all the partitions from PARTITIONS that contain similar memory
856 references, i.e., we're taking care of cache locality. This
857 function does not fuse those partitions that contain patterns that
858 can be code generated with builtins. */
861 fuse_partitions_with_similar_memory_accesses (struct graph
*rdg
,
862 VEC (bitmap
, heap
) **partitions
)
865 bitmap partition1
, partition2
;
867 FOR_EACH_VEC_ELT (bitmap
, *partitions
, p1
, partition1
)
868 if (!can_generate_builtin (rdg
, partition1
))
869 FOR_EACH_VEC_ELT (bitmap
, *partitions
, p2
, partition2
)
871 && !can_generate_builtin (rdg
, partition2
)
872 && similar_memory_accesses (rdg
, partition1
, partition2
))
874 bitmap_ior_into (partition1
, partition2
);
875 VEC_ordered_remove (bitmap
, *partitions
, p2
);
880 /* Returns true when STMT will be code generated in a partition of RDG
881 different than PART and that will not be code generated as a
885 stmt_generated_in_another_partition (struct graph
*rdg
, gimple stmt
, int part
,
886 VEC (bitmap
, heap
) *partitions
)
893 FOR_EACH_VEC_ELT (bitmap
, partitions
, p
, pp
)
895 && !can_generate_builtin (rdg
, pp
))
896 EXECUTE_IF_SET_IN_BITMAP (pp
, 0, i
, bi
)
897 if (stmt
== RDG_STMT (rdg
, i
))
903 /* For each partition in PARTITIONS that will be code generated using
904 a builtin, add its scalar computations used after the loop to
908 add_scalar_computations_to_partition (struct graph
*rdg
,
909 VEC (bitmap
, heap
) *partitions
,
916 bitmap l
= BITMAP_ALLOC (NULL
);
917 bitmap pr
= BITMAP_ALLOC (NULL
);
920 FOR_EACH_VEC_ELT (bitmap
, partitions
, p
, pp
)
921 if (can_generate_builtin (rdg
, pp
))
922 EXECUTE_IF_SET_IN_BITMAP (pp
, 0, i
, bi
)
923 if (stmt_has_scalar_dependences_outside_loop (RDG_STMT (rdg
, i
))
924 && !stmt_generated_in_another_partition (rdg
, RDG_STMT (rdg
, i
), p
,
926 rdg_flag_vertex_and_dependent (rdg
, i
, partition
, l
, pr
, &f
);
928 rdg_flag_loop_exits (rdg
, l
, partition
, pr
, &f
);
934 /* Aggregate several components into a useful partition that is
935 registered in the PARTITIONS vector. Partitions will be
936 distributed in different loops. */
939 rdg_build_partitions (struct graph
*rdg
, VEC (rdgc
, heap
) *components
,
940 VEC (int, heap
) **other_stores
,
941 VEC (bitmap
, heap
) **partitions
, bitmap processed
)
945 bitmap partition
= BITMAP_ALLOC (NULL
);
947 FOR_EACH_VEC_ELT (rdgc
, components
, i
, x
)
950 bool part_has_writes
= false;
951 int v
= VEC_index (int, x
->vertices
, 0);
953 if (bitmap_bit_p (processed
, v
))
956 np
= build_rdg_partition_for_component (rdg
, x
, &part_has_writes
);
957 bitmap_ior_into (partition
, np
);
958 bitmap_ior_into (processed
, np
);
963 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
965 fprintf (dump_file
, "ldist useful partition:\n");
966 dump_bitmap (dump_file
, partition
);
969 VEC_safe_push (bitmap
, heap
, *partitions
, partition
);
970 partition
= BITMAP_ALLOC (NULL
);
974 /* Add the nodes from the RDG that were not marked as processed, and
975 that are used outside the current loop. These are scalar
976 computations that are not yet part of previous partitions. */
977 for (i
= 0; i
< rdg
->n_vertices
; i
++)
978 if (!bitmap_bit_p (processed
, i
)
979 && rdg_defs_used_in_other_loops_p (rdg
, i
))
980 VEC_safe_push (int, heap
, *other_stores
, i
);
982 /* If there are still statements left in the OTHER_STORES array,
983 create other components and partitions with these stores and
984 their dependences. */
985 if (VEC_length (int, *other_stores
) > 0)
987 VEC (rdgc
, heap
) *comps
= VEC_alloc (rdgc
, heap
, 3);
988 VEC (int, heap
) *foo
= VEC_alloc (int, heap
, 3);
990 rdg_build_components (rdg
, *other_stores
, &comps
);
991 rdg_build_partitions (rdg
, comps
, &foo
, partitions
, processed
);
993 VEC_free (int, heap
, foo
);
994 free_rdg_components (comps
);
997 add_scalar_computations_to_partition (rdg
, *partitions
, partition
);
999 /* If there is something left in the last partition, save it. */
1000 if (bitmap_count_bits (partition
) > 0)
1001 VEC_safe_push (bitmap
, heap
, *partitions
, partition
);
1003 BITMAP_FREE (partition
);
1005 fuse_partitions_with_similar_memory_accesses (rdg
, partitions
);
1008 /* Dump to FILE the PARTITIONS. */
1011 dump_rdg_partitions (FILE *file
, VEC (bitmap
, heap
) *partitions
)
1016 FOR_EACH_VEC_ELT (bitmap
, partitions
, i
, partition
)
1017 debug_bitmap_file (file
, partition
);
1020 /* Debug PARTITIONS. */
1021 extern void debug_rdg_partitions (VEC (bitmap
, heap
) *);
1024 debug_rdg_partitions (VEC (bitmap
, heap
) *partitions
)
1026 dump_rdg_partitions (stderr
, partitions
);
1029 /* Returns the number of read and write operations in the RDG. */
1032 number_of_rw_in_rdg (struct graph
*rdg
)
1036 for (i
= 0; i
< rdg
->n_vertices
; i
++)
1038 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1041 if (RDG_MEM_READS_STMT (rdg
, i
))
1048 /* Returns the number of read and write operations in a PARTITION of
1052 number_of_rw_in_partition (struct graph
*rdg
, bitmap partition
)
1058 EXECUTE_IF_SET_IN_BITMAP (partition
, 0, i
, ii
)
1060 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1063 if (RDG_MEM_READS_STMT (rdg
, i
))
1070 /* Returns true when one of the PARTITIONS contains all the read or
1071 write operations of RDG. */
1074 partition_contains_all_rw (struct graph
*rdg
, VEC (bitmap
, heap
) *partitions
)
1078 int nrw
= number_of_rw_in_rdg (rdg
);
1080 FOR_EACH_VEC_ELT (bitmap
, partitions
, i
, partition
)
1081 if (nrw
== number_of_rw_in_partition (rdg
, partition
))
1087 /* Generate code from STARTING_VERTICES in RDG. Returns the number of
1088 distributed loops. */
1091 ldist_gen (struct loop
*loop
, struct graph
*rdg
,
1092 VEC (int, heap
) *starting_vertices
)
1095 VEC (rdgc
, heap
) *components
= VEC_alloc (rdgc
, heap
, 3);
1096 VEC (bitmap
, heap
) *partitions
= VEC_alloc (bitmap
, heap
, 3);
1097 VEC (int, heap
) *other_stores
= VEC_alloc (int, heap
, 3);
1098 bitmap partition
, processed
= BITMAP_ALLOC (NULL
);
1100 remaining_stmts
= BITMAP_ALLOC (NULL
);
1101 upstream_mem_writes
= BITMAP_ALLOC (NULL
);
1103 for (i
= 0; i
< rdg
->n_vertices
; i
++)
1105 bitmap_set_bit (remaining_stmts
, i
);
1107 /* Save in OTHER_STORES all the memory writes that are not in
1108 STARTING_VERTICES. */
1109 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1115 FOR_EACH_VEC_ELT (int, starting_vertices
, j
, v
)
1123 VEC_safe_push (int, heap
, other_stores
, i
);
1127 mark_nodes_having_upstream_mem_writes (rdg
);
1128 rdg_build_components (rdg
, starting_vertices
, &components
);
1129 rdg_build_partitions (rdg
, components
, &other_stores
, &partitions
,
1131 BITMAP_FREE (processed
);
1132 nbp
= VEC_length (bitmap
, partitions
);
1135 || partition_contains_all_rw (rdg
, partitions
))
1138 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1139 dump_rdg_partitions (dump_file
, partitions
);
1141 FOR_EACH_VEC_ELT (bitmap
, partitions
, i
, partition
)
1142 if (!generate_code_for_partition (loop
, partition
, i
< nbp
- 1))
1145 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1146 mark_sym_for_renaming (gimple_vop (cfun
));
1147 update_ssa (TODO_update_ssa_only_virtuals
);
1151 BITMAP_FREE (remaining_stmts
);
1152 BITMAP_FREE (upstream_mem_writes
);
1154 FOR_EACH_VEC_ELT (bitmap
, partitions
, i
, partition
)
1155 BITMAP_FREE (partition
);
1157 VEC_free (int, heap
, other_stores
);
1158 VEC_free (bitmap
, heap
, partitions
);
1159 free_rdg_components (components
);
1163 /* Distributes the code from LOOP in such a way that producer
1164 statements are placed before consumer statements. When STMTS is
1165 NULL, performs the maximal distribution, if STMTS is not NULL,
1166 tries to separate only these statements from the LOOP's body.
1167 Returns the number of distributed loops. */
1170 distribute_loop (struct loop
*loop
, VEC (gimple
, heap
) *stmts
)
1176 VEC (int, heap
) *vertices
;
1177 VEC (ddr_p
, heap
) *dependence_relations
;
1178 VEC (data_reference_p
, heap
) *datarefs
;
1179 VEC (loop_p
, heap
) *loop_nest
;
1181 if (loop
->num_nodes
> 2)
1183 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1185 "FIXME: Loop %d not distributed: it has more than two basic blocks.\n",
1191 datarefs
= VEC_alloc (data_reference_p
, heap
, 10);
1192 dependence_relations
= VEC_alloc (ddr_p
, heap
, 100);
1193 loop_nest
= VEC_alloc (loop_p
, heap
, 3);
1194 rdg
= build_rdg (loop
, &loop_nest
, &dependence_relations
, &datarefs
);
1198 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1200 "FIXME: Loop %d not distributed: failed to build the RDG.\n",
1203 free_dependence_relations (dependence_relations
);
1204 free_data_refs (datarefs
);
1205 VEC_free (loop_p
, heap
, loop_nest
);
1209 vertices
= VEC_alloc (int, heap
, 3);
1211 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1212 dump_rdg (dump_file
, rdg
);
1214 FOR_EACH_VEC_ELT (gimple
, stmts
, i
, s
)
1216 int v
= rdg_vertex_for_stmt (rdg
, s
);
1220 VEC_safe_push (int, heap
, vertices
, v
);
1222 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1224 "ldist asked to generate code for vertex %d\n", v
);
1228 res
= ldist_gen (loop
, rdg
, vertices
);
1229 VEC_free (int, heap
, vertices
);
1231 free_dependence_relations (dependence_relations
);
1232 free_data_refs (datarefs
);
1233 VEC_free (loop_p
, heap
, loop_nest
);
1237 /* Distribute all loops in the current function. */
1240 tree_loop_distribution (void)
1244 int nb_generated_loops
= 0;
1246 FOR_EACH_LOOP (li
, loop
, 0)
1248 VEC (gimple
, heap
) *work_list
= NULL
;
1249 int num
= loop
->num
;
1251 /* If the loop doesn't have a single exit we will fail anyway,
1252 so do that early. */
1253 if (!single_exit (loop
))
1256 /* If both flag_tree_loop_distribute_patterns and
1257 flag_tree_loop_distribution are set, then only
1258 distribute_patterns is executed. */
1259 if (flag_tree_loop_distribute_patterns
)
1261 /* With the following working list, we're asking
1262 distribute_loop to separate from the rest of the loop the
1263 stores of the form "A[i] = 0". */
1264 stores_zero_from_loop (loop
, &work_list
);
1266 /* Do nothing if there are no patterns to be distributed. */
1267 if (VEC_length (gimple
, work_list
) > 0)
1268 nb_generated_loops
= distribute_loop (loop
, work_list
);
1270 else if (flag_tree_loop_distribution
)
1272 /* With the following working list, we're asking
1273 distribute_loop to separate the stores of the loop: when
1274 dependences allow, it will end on having one store per
1276 stores_from_loop (loop
, &work_list
);
1278 /* A simple heuristic for cache locality is to not split
1279 stores to the same array. Without this call, an unrolled
1280 loop would be split into as many loops as unroll factor,
1281 each loop storing in the same array. */
1282 remove_similar_memory_refs (&work_list
);
1284 nb_generated_loops
= distribute_loop (loop
, work_list
);
1287 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1289 if (nb_generated_loops
> 1)
1290 fprintf (dump_file
, "Loop %d distributed: split to %d loops.\n",
1291 num
, nb_generated_loops
);
1293 fprintf (dump_file
, "Loop %d is the same.\n", num
);
1296 verify_loop_structure ();
1298 VEC_free (gimple
, heap
, work_list
);
1305 gate_tree_loop_distribution (void)
1307 return flag_tree_loop_distribution
1308 || flag_tree_loop_distribute_patterns
;
1311 struct gimple_opt_pass pass_loop_distribution
=
1316 gate_tree_loop_distribution
, /* gate */
1317 tree_loop_distribution
, /* execute */
1320 0, /* static_pass_number */
1321 TV_TREE_LOOP_DISTRIBUTION
, /* tv_id */
1322 PROP_cfg
| PROP_ssa
, /* properties_required */
1323 0, /* properties_provided */
1324 0, /* properties_destroyed */
1325 0, /* todo_flags_start */
1327 | TODO_verify_ssa
/* todo_flags_finish */