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 /* Update the PHI nodes of NEW_LOOP. NEW_LOOP is a duplicate of
70 update_phis_for_loop_copy (struct loop
*orig_loop
, struct loop
*new_loop
)
73 gimple_stmt_iterator si_new
, si_orig
;
74 edge orig_loop_latch
= loop_latch_edge (orig_loop
);
75 edge orig_entry_e
= loop_preheader_edge (orig_loop
);
76 edge new_loop_entry_e
= loop_preheader_edge (new_loop
);
78 /* Scan the phis in the headers of the old and new loops
79 (they are organized in exactly the same order). */
80 for (si_new
= gsi_start_phis (new_loop
->header
),
81 si_orig
= gsi_start_phis (orig_loop
->header
);
82 !gsi_end_p (si_new
) && !gsi_end_p (si_orig
);
83 gsi_next (&si_new
), gsi_next (&si_orig
))
86 source_location locus
;
87 gimple phi_new
= gsi_stmt (si_new
);
88 gimple phi_orig
= gsi_stmt (si_orig
);
90 /* Add the first phi argument for the phi in NEW_LOOP (the one
91 associated with the entry of NEW_LOOP) */
92 def
= PHI_ARG_DEF_FROM_EDGE (phi_orig
, orig_entry_e
);
93 locus
= gimple_phi_arg_location_from_edge (phi_orig
, orig_entry_e
);
94 add_phi_arg (phi_new
, def
, new_loop_entry_e
, locus
);
96 /* Add the second phi argument for the phi in NEW_LOOP (the one
97 associated with the latch of NEW_LOOP) */
98 def
= PHI_ARG_DEF_FROM_EDGE (phi_orig
, orig_loop_latch
);
99 locus
= gimple_phi_arg_location_from_edge (phi_orig
, orig_loop_latch
);
101 if (TREE_CODE (def
) == SSA_NAME
)
103 new_ssa_name
= get_current_def (def
);
106 /* This only happens if there are no definitions inside the
107 loop. Use the the invariant in the new loop as is. */
111 /* Could be an integer. */
114 add_phi_arg (phi_new
, new_ssa_name
, loop_latch_edge (new_loop
), locus
);
118 /* Return a copy of LOOP placed before LOOP. */
121 copy_loop_before (struct loop
*loop
)
124 edge preheader
= loop_preheader_edge (loop
);
126 if (!single_exit (loop
))
129 initialize_original_copy_tables ();
130 res
= slpeel_tree_duplicate_loop_to_edge_cfg (loop
, preheader
);
131 free_original_copy_tables ();
136 update_phis_for_loop_copy (loop
, res
);
137 rename_variables_in_loop (res
);
142 /* Creates an empty basic block after LOOP. */
145 create_bb_after_loop (struct loop
*loop
)
147 edge exit
= single_exit (loop
);
155 /* Generate code for PARTITION from the code in LOOP. The loop is
156 copied when COPY_P is true. All the statements not flagged in the
157 PARTITION bitmap are removed from the loop or from its copy. The
158 statements are indexed in sequence inside a basic block, and the
159 basic blocks of a loop are taken in dom order. Returns true when
160 the code gen succeeded. */
163 generate_loops_for_partition (struct loop
*loop
, bitmap partition
, bool copy_p
)
166 gimple_stmt_iterator bsi
;
171 loop
= copy_loop_before (loop
);
172 create_preheader (loop
, CP_SIMPLE_PREHEADERS
);
173 create_bb_after_loop (loop
);
179 /* Remove stmts not in the PARTITION bitmap. The order in which we
180 visit the phi nodes and the statements is exactly as in
182 bbs
= get_loop_body_in_dom_order (loop
);
184 if (MAY_HAVE_DEBUG_STMTS
)
185 for (x
= 0, i
= 0; i
< loop
->num_nodes
; i
++)
187 basic_block bb
= bbs
[i
];
189 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
190 if (!bitmap_bit_p (partition
, x
++))
191 reset_debug_uses (gsi_stmt (bsi
));
193 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
195 gimple stmt
= gsi_stmt (bsi
);
196 if (gimple_code (stmt
) != GIMPLE_LABEL
197 && !is_gimple_debug (stmt
)
198 && !bitmap_bit_p (partition
, x
++))
199 reset_debug_uses (stmt
);
203 for (x
= 0, i
= 0; i
< loop
->num_nodes
; i
++)
205 basic_block bb
= bbs
[i
];
207 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);)
208 if (!bitmap_bit_p (partition
, x
++))
210 gimple phi
= gsi_stmt (bsi
);
211 if (!is_gimple_reg (gimple_phi_result (phi
)))
212 mark_virtual_phi_result_for_renaming (phi
);
213 remove_phi_node (&bsi
, true);
218 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);)
220 gimple stmt
= gsi_stmt (bsi
);
221 if (gimple_code (stmt
) != GIMPLE_LABEL
222 && !is_gimple_debug (stmt
)
223 && !bitmap_bit_p (partition
, x
++))
225 unlink_stmt_vdef (stmt
);
226 gsi_remove (&bsi
, true);
238 /* Build the size argument for a memset call. */
241 build_size_arg_loc (location_t loc
, tree nb_iter
, tree op
,
242 gimple_seq
*stmt_list
)
245 tree x
= size_binop_loc (loc
, MULT_EXPR
,
246 fold_convert_loc (loc
, sizetype
, nb_iter
),
247 TYPE_SIZE_UNIT (TREE_TYPE (op
)));
248 x
= force_gimple_operand (x
, &stmts
, true, NULL
);
249 gimple_seq_add_seq (stmt_list
, stmts
);
254 /* Generate a call to memset. Return true when the operation succeeded. */
257 generate_memset_zero (gimple stmt
, tree op0
, tree nb_iter
,
258 gimple_stmt_iterator bsi
)
260 tree addr_base
, nb_bytes
;
262 gimple_seq stmt_list
= NULL
, stmts
;
265 struct data_reference
*dr
= XCNEW (struct data_reference
);
266 location_t loc
= gimple_location (stmt
);
270 res
= dr_analyze_innermost (dr
);
271 gcc_assert (res
&& stride_of_unit_type_p (DR_STEP (dr
), TREE_TYPE (op0
)));
273 nb_bytes
= build_size_arg_loc (loc
, nb_iter
, op0
, &stmt_list
);
274 addr_base
= size_binop_loc (loc
, PLUS_EXPR
, DR_OFFSET (dr
), DR_INIT (dr
));
275 addr_base
= fold_convert_loc (loc
, sizetype
, addr_base
);
277 /* Test for a negative stride, iterating over every element. */
278 if (integer_zerop (size_binop (PLUS_EXPR
,
279 TYPE_SIZE_UNIT (TREE_TYPE (op0
)),
280 fold_convert (sizetype
, DR_STEP (dr
)))))
282 addr_base
= size_binop_loc (loc
, MINUS_EXPR
, addr_base
,
283 fold_convert_loc (loc
, sizetype
, nb_bytes
));
284 addr_base
= size_binop_loc (loc
, PLUS_EXPR
, addr_base
,
285 TYPE_SIZE_UNIT (TREE_TYPE (op0
)));
288 addr_base
= fold_build2_loc (loc
, POINTER_PLUS_EXPR
,
289 TREE_TYPE (DR_BASE_ADDRESS (dr
)),
290 DR_BASE_ADDRESS (dr
), addr_base
);
291 mem
= force_gimple_operand (addr_base
, &stmts
, true, NULL
);
292 gimple_seq_add_seq (&stmt_list
, stmts
);
294 fn
= build_fold_addr_expr (implicit_built_in_decls
[BUILT_IN_MEMSET
]);
295 fn_call
= gimple_build_call (fn
, 3, mem
, integer_zero_node
, nb_bytes
);
296 gimple_seq_add_stmt (&stmt_list
, fn_call
);
297 gsi_insert_seq_after (&bsi
, stmt_list
, GSI_CONTINUE_LINKING
);
299 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
300 fprintf (dump_file
, "generated memset zero\n");
305 /* Tries to generate a builtin function for the instructions of LOOP
306 pointed to by the bits set in PARTITION. Returns true when the
307 operation succeeded. */
310 generate_builtin (struct loop
*loop
, bitmap partition
, bool copy_p
)
316 gimple_stmt_iterator bsi
;
317 tree nb_iter
= number_of_exit_cond_executions (loop
);
319 if (!nb_iter
|| nb_iter
== chrec_dont_know
)
322 bbs
= get_loop_body_in_dom_order (loop
);
324 for (i
= 0; i
< loop
->num_nodes
; i
++)
326 basic_block bb
= bbs
[i
];
328 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
331 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
333 gimple stmt
= gsi_stmt (bsi
);
335 if (gimple_code (stmt
) != GIMPLE_LABEL
336 && !is_gimple_debug (stmt
)
337 && bitmap_bit_p (partition
, x
++)
338 && is_gimple_assign (stmt
)
339 && !is_gimple_reg (gimple_assign_lhs (stmt
)))
341 /* Don't generate the builtins when there are more than
347 if (bb
== loop
->latch
)
348 nb_iter
= number_of_latch_executions (loop
);
353 if (!stmt_with_adjacent_zero_store_dr_p (write
))
356 /* The new statements will be placed before LOOP. */
357 bsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
358 generate_memset_zero (write
, gimple_assign_lhs (write
), nb_iter
, bsi
);
361 /* If this is the last partition for which we generate code, we have
362 to destroy the loop. */
365 unsigned nbbs
= loop
->num_nodes
;
366 edge exit
= single_exit (loop
);
367 basic_block src
= loop_preheader_edge (loop
)->src
, dest
= exit
->dest
;
368 redirect_edge_pred (exit
, src
);
369 exit
->flags
&= ~(EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
370 exit
->flags
|= EDGE_FALLTHRU
;
371 cancel_loop_tree (loop
);
372 rescan_loop_exit (exit
, false, true);
374 for (i
= 0; i
< nbbs
; i
++)
375 delete_basic_block (bbs
[i
]);
377 set_immediate_dominator (CDI_DOMINATORS
, dest
,
378 recompute_dominator (CDI_DOMINATORS
, dest
));
386 /* Generates code for PARTITION. For simple loops, this function can
387 generate a built-in. */
390 generate_code_for_partition (struct loop
*loop
, bitmap partition
, bool copy_p
)
392 if (generate_builtin (loop
, partition
, copy_p
))
395 return generate_loops_for_partition (loop
, partition
, copy_p
);
399 /* Returns true if the node V of RDG cannot be recomputed. */
402 rdg_cannot_recompute_vertex_p (struct graph
*rdg
, int v
)
404 if (RDG_MEM_WRITE_STMT (rdg
, v
))
410 /* Returns true when the vertex V has already been generated in the
411 current partition (V is in PROCESSED), or when V belongs to another
412 partition and cannot be recomputed (V is not in REMAINING_STMTS). */
415 already_processed_vertex_p (bitmap processed
, int v
)
417 return (bitmap_bit_p (processed
, v
)
418 || !bitmap_bit_p (remaining_stmts
, v
));
421 /* Returns NULL when there is no anti-dependence among the successors
422 of vertex V, otherwise returns the edge with the anti-dep. */
424 static struct graph_edge
*
425 has_anti_dependence (struct vertex
*v
)
427 struct graph_edge
*e
;
430 for (e
= v
->succ
; e
; e
= e
->succ_next
)
431 if (RDGE_TYPE (e
) == anti_dd
)
437 /* Returns true when V has an anti-dependence edge among its successors. */
440 predecessor_has_mem_write (struct graph
*rdg
, struct vertex
*v
)
442 struct graph_edge
*e
;
445 for (e
= v
->pred
; e
; e
= e
->pred_next
)
446 if (bitmap_bit_p (upstream_mem_writes
, e
->src
)
447 /* Don't consider flow channels: a write to memory followed
448 by a read from memory. These channels allow the split of
449 the RDG in different partitions. */
450 && !RDG_MEM_WRITE_STMT (rdg
, e
->src
))
456 /* Initializes the upstream_mem_writes bitmap following the
457 information from RDG. */
460 mark_nodes_having_upstream_mem_writes (struct graph
*rdg
)
463 bitmap seen
= BITMAP_ALLOC (NULL
);
465 for (v
= rdg
->n_vertices
- 1; v
>= 0; v
--)
466 if (!bitmap_bit_p (seen
, v
))
469 VEC (int, heap
) *nodes
= VEC_alloc (int, heap
, 3);
471 graphds_dfs (rdg
, &v
, 1, &nodes
, false, NULL
);
473 FOR_EACH_VEC_ELT (int, nodes
, i
, x
)
475 if (!bitmap_set_bit (seen
, x
))
478 if (RDG_MEM_WRITE_STMT (rdg
, x
)
479 || predecessor_has_mem_write (rdg
, &(rdg
->vertices
[x
]))
480 /* In anti dependences the read should occur before
481 the write, this is why both the read and the write
482 should be placed in the same partition. */
483 || has_anti_dependence (&(rdg
->vertices
[x
])))
485 bitmap_set_bit (upstream_mem_writes
, x
);
489 VEC_free (int, heap
, nodes
);
493 /* Returns true when vertex u has a memory write node as a predecessor
497 has_upstream_mem_writes (int u
)
499 return bitmap_bit_p (upstream_mem_writes
, u
);
502 static void rdg_flag_vertex_and_dependent (struct graph
*, int, bitmap
, bitmap
,
505 /* Flag the uses of U stopping following the information from
506 upstream_mem_writes. */
509 rdg_flag_uses (struct graph
*rdg
, int u
, bitmap partition
, bitmap loops
,
510 bitmap processed
, bool *part_has_writes
)
513 struct vertex
*x
= &(rdg
->vertices
[u
]);
514 gimple stmt
= RDGV_STMT (x
);
515 struct graph_edge
*anti_dep
= has_anti_dependence (x
);
517 /* Keep in the same partition the destination of an antidependence,
518 because this is a store to the exact same location. Putting this
519 in another partition is bad for cache locality. */
522 int v
= anti_dep
->dest
;
524 if (!already_processed_vertex_p (processed
, v
))
525 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
,
526 processed
, part_has_writes
);
529 if (gimple_code (stmt
) != GIMPLE_PHI
)
531 if ((use_p
= gimple_vuse_op (stmt
)) != NULL_USE_OPERAND_P
)
533 tree use
= USE_FROM_PTR (use_p
);
535 if (TREE_CODE (use
) == SSA_NAME
)
537 gimple def_stmt
= SSA_NAME_DEF_STMT (use
);
538 int v
= rdg_vertex_for_stmt (rdg
, def_stmt
);
541 && !already_processed_vertex_p (processed
, v
))
542 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
,
543 processed
, part_has_writes
);
548 if (is_gimple_assign (stmt
) && has_upstream_mem_writes (u
))
550 tree op0
= gimple_assign_lhs (stmt
);
552 /* Scalar channels don't have enough space for transmitting data
553 between tasks, unless we add more storage by privatizing. */
554 if (is_gimple_reg (op0
))
557 imm_use_iterator iter
;
559 FOR_EACH_IMM_USE_FAST (use_p
, iter
, op0
)
561 int v
= rdg_vertex_for_stmt (rdg
, USE_STMT (use_p
));
563 if (!already_processed_vertex_p (processed
, v
))
564 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
,
565 processed
, part_has_writes
);
571 /* Flag V from RDG as part of PARTITION, and also flag its loop number
575 rdg_flag_vertex (struct graph
*rdg
, int v
, bitmap partition
, bitmap loops
,
576 bool *part_has_writes
)
580 if (!bitmap_set_bit (partition
, v
))
583 loop
= loop_containing_stmt (RDG_STMT (rdg
, v
));
584 bitmap_set_bit (loops
, loop
->num
);
586 if (rdg_cannot_recompute_vertex_p (rdg
, v
))
588 *part_has_writes
= true;
589 bitmap_clear_bit (remaining_stmts
, v
);
593 /* Flag in the bitmap PARTITION the vertex V and all its predecessors.
594 Also flag their loop number in LOOPS. */
597 rdg_flag_vertex_and_dependent (struct graph
*rdg
, int v
, bitmap partition
,
598 bitmap loops
, bitmap processed
,
599 bool *part_has_writes
)
602 VEC (int, heap
) *nodes
= VEC_alloc (int, heap
, 3);
605 bitmap_set_bit (processed
, v
);
606 rdg_flag_uses (rdg
, v
, partition
, loops
, processed
, part_has_writes
);
607 graphds_dfs (rdg
, &v
, 1, &nodes
, false, remaining_stmts
);
608 rdg_flag_vertex (rdg
, v
, partition
, loops
, part_has_writes
);
610 FOR_EACH_VEC_ELT (int, nodes
, i
, x
)
611 if (!already_processed_vertex_p (processed
, x
))
612 rdg_flag_vertex_and_dependent (rdg
, x
, partition
, loops
, processed
,
615 VEC_free (int, heap
, nodes
);
618 /* Initialize CONDS with all the condition statements from the basic
622 collect_condition_stmts (struct loop
*loop
, VEC (gimple
, heap
) **conds
)
626 VEC (edge
, heap
) *exits
= get_loop_exit_edges (loop
);
628 FOR_EACH_VEC_ELT (edge
, exits
, i
, e
)
630 gimple cond
= last_stmt (e
->src
);
633 VEC_safe_push (gimple
, heap
, *conds
, cond
);
636 VEC_free (edge
, heap
, exits
);
639 /* Add to PARTITION all the exit condition statements for LOOPS
640 together with all their dependent statements determined from
644 rdg_flag_loop_exits (struct graph
*rdg
, bitmap loops
, bitmap partition
,
645 bitmap processed
, bool *part_has_writes
)
649 VEC (gimple
, heap
) *conds
= VEC_alloc (gimple
, heap
, 3);
651 EXECUTE_IF_SET_IN_BITMAP (loops
, 0, i
, bi
)
652 collect_condition_stmts (get_loop (i
), &conds
);
654 while (!VEC_empty (gimple
, conds
))
656 gimple cond
= VEC_pop (gimple
, conds
);
657 int v
= rdg_vertex_for_stmt (rdg
, cond
);
658 bitmap new_loops
= BITMAP_ALLOC (NULL
);
660 if (!already_processed_vertex_p (processed
, v
))
661 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, new_loops
, processed
,
664 EXECUTE_IF_SET_IN_BITMAP (new_loops
, 0, i
, bi
)
665 if (bitmap_set_bit (loops
, i
))
666 collect_condition_stmts (get_loop (i
), &conds
);
668 BITMAP_FREE (new_loops
);
671 VEC_free (gimple
, heap
, conds
);
674 /* Returns a bitmap in which all the statements needed for computing
675 the strongly connected component C of the RDG are flagged, also
676 including the loop exit conditions. */
679 build_rdg_partition_for_component (struct graph
*rdg
, rdgc c
,
680 bool *part_has_writes
)
683 bitmap partition
= BITMAP_ALLOC (NULL
);
684 bitmap loops
= BITMAP_ALLOC (NULL
);
685 bitmap processed
= BITMAP_ALLOC (NULL
);
687 FOR_EACH_VEC_ELT (int, c
->vertices
, i
, v
)
688 if (!already_processed_vertex_p (processed
, v
))
689 rdg_flag_vertex_and_dependent (rdg
, v
, partition
, loops
, processed
,
692 rdg_flag_loop_exits (rdg
, loops
, partition
, processed
, part_has_writes
);
694 BITMAP_FREE (processed
);
699 /* Free memory for COMPONENTS. */
702 free_rdg_components (VEC (rdgc
, heap
) *components
)
707 FOR_EACH_VEC_ELT (rdgc
, components
, i
, x
)
709 VEC_free (int, heap
, x
->vertices
);
713 VEC_free (rdgc
, heap
, components
);
716 /* Build the COMPONENTS vector with the strongly connected components
717 of RDG in which the STARTING_VERTICES occur. */
720 rdg_build_components (struct graph
*rdg
, VEC (int, heap
) *starting_vertices
,
721 VEC (rdgc
, heap
) **components
)
724 bitmap saved_components
= BITMAP_ALLOC (NULL
);
725 int n_components
= graphds_scc (rdg
, NULL
);
726 VEC (int, heap
) **all_components
= XNEWVEC (VEC (int, heap
) *, n_components
);
728 for (i
= 0; i
< n_components
; i
++)
729 all_components
[i
] = VEC_alloc (int, heap
, 3);
731 for (i
= 0; i
< rdg
->n_vertices
; i
++)
732 VEC_safe_push (int, heap
, all_components
[rdg
->vertices
[i
].component
], i
);
734 FOR_EACH_VEC_ELT (int, starting_vertices
, i
, v
)
736 int c
= rdg
->vertices
[v
].component
;
738 if (bitmap_set_bit (saved_components
, c
))
740 rdgc x
= XCNEW (struct rdg_component
);
742 x
->vertices
= all_components
[c
];
744 VEC_safe_push (rdgc
, heap
, *components
, x
);
748 for (i
= 0; i
< n_components
; i
++)
749 if (!bitmap_bit_p (saved_components
, i
))
750 VEC_free (int, heap
, all_components
[i
]);
752 free (all_components
);
753 BITMAP_FREE (saved_components
);
756 /* Returns true when it is possible to generate a builtin pattern for
757 the PARTITION of RDG. For the moment we detect only the memset
761 can_generate_builtin (struct graph
*rdg
, bitmap partition
)
769 EXECUTE_IF_SET_IN_BITMAP (partition
, 0, i
, bi
)
770 if (RDG_MEM_READS_STMT (rdg
, i
))
772 else if (RDG_MEM_WRITE_STMT (rdg
, i
))
775 if (stmt_with_adjacent_zero_store_dr_p (RDG_STMT (rdg
, i
)))
779 return stores_zero
== 1 && nb_writes
== 1 && nb_reads
== 0;
782 /* Returns true when PARTITION1 and PARTITION2 have similar memory
786 similar_memory_accesses (struct graph
*rdg
, bitmap partition1
,
790 bitmap_iterator bi
, bj
;
792 EXECUTE_IF_SET_IN_BITMAP (partition1
, 0, i
, bi
)
793 if (RDG_MEM_WRITE_STMT (rdg
, i
)
794 || RDG_MEM_READS_STMT (rdg
, i
))
795 EXECUTE_IF_SET_IN_BITMAP (partition2
, 0, j
, bj
)
796 if (RDG_MEM_WRITE_STMT (rdg
, j
)
797 || RDG_MEM_READS_STMT (rdg
, j
))
798 if (rdg_has_similar_memory_accesses (rdg
, i
, j
))
804 /* Fuse all the partitions from PARTITIONS that contain similar memory
805 references, i.e., we're taking care of cache locality. This
806 function does not fuse those partitions that contain patterns that
807 can be code generated with builtins. */
810 fuse_partitions_with_similar_memory_accesses (struct graph
*rdg
,
811 VEC (bitmap
, heap
) **partitions
)
814 bitmap partition1
, partition2
;
816 FOR_EACH_VEC_ELT (bitmap
, *partitions
, p1
, partition1
)
817 if (!can_generate_builtin (rdg
, partition1
))
818 FOR_EACH_VEC_ELT (bitmap
, *partitions
, p2
, partition2
)
820 && !can_generate_builtin (rdg
, partition2
)
821 && similar_memory_accesses (rdg
, partition1
, partition2
))
823 bitmap_ior_into (partition1
, partition2
);
824 VEC_ordered_remove (bitmap
, *partitions
, p2
);
829 /* Returns true when DEF is an SSA_NAME defined in LOOP and used after
833 ssa_name_has_uses_outside_loop_p (tree def
, loop_p loop
)
835 imm_use_iterator imm_iter
;
838 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
839 if (loop
!= loop_containing_stmt (USE_STMT (use_p
)))
845 /* Returns true when STMT defines a scalar variable used after the
849 stmt_has_scalar_dependences_outside_loop (gimple stmt
)
853 switch (gimple_code (stmt
))
856 name
= gimple_assign_lhs (stmt
);
860 name
= gimple_phi_result (stmt
);
867 return TREE_CODE (name
) == SSA_NAME
868 && ssa_name_has_uses_outside_loop_p (name
, loop_containing_stmt (stmt
));
871 /* Returns true when STMT will be code generated in a partition of RDG
872 different than PART and that will not be code generated as a
876 stmt_generated_in_another_partition (struct graph
*rdg
, gimple stmt
, int part
,
877 VEC (bitmap
, heap
) *partitions
)
884 FOR_EACH_VEC_ELT (bitmap
, partitions
, p
, pp
)
886 && !can_generate_builtin (rdg
, pp
))
887 EXECUTE_IF_SET_IN_BITMAP (pp
, 0, i
, bi
)
888 if (stmt
== RDG_STMT (rdg
, i
))
894 /* For each partition in PARTITIONS that will be code generated using
895 a builtin, add its scalar computations used after the loop to
899 add_scalar_computations_to_partition (struct graph
*rdg
,
900 VEC (bitmap
, heap
) *partitions
,
907 bitmap l
= BITMAP_ALLOC (NULL
);
908 bitmap pr
= BITMAP_ALLOC (NULL
);
911 FOR_EACH_VEC_ELT (bitmap
, partitions
, p
, pp
)
912 if (can_generate_builtin (rdg
, pp
))
913 EXECUTE_IF_SET_IN_BITMAP (pp
, 0, i
, bi
)
914 if (stmt_has_scalar_dependences_outside_loop (RDG_STMT (rdg
, i
))
915 && !stmt_generated_in_another_partition (rdg
, RDG_STMT (rdg
, i
), p
,
917 rdg_flag_vertex_and_dependent (rdg
, i
, partition
, l
, pr
, &f
);
919 rdg_flag_loop_exits (rdg
, l
, partition
, pr
, &f
);
925 /* Aggregate several components into a useful partition that is
926 registered in the PARTITIONS vector. Partitions will be
927 distributed in different loops. */
930 rdg_build_partitions (struct graph
*rdg
, VEC (rdgc
, heap
) *components
,
931 VEC (int, heap
) **other_stores
,
932 VEC (bitmap
, heap
) **partitions
, bitmap processed
)
936 bitmap partition
= BITMAP_ALLOC (NULL
);
938 FOR_EACH_VEC_ELT (rdgc
, components
, i
, x
)
941 bool part_has_writes
= false;
942 int v
= VEC_index (int, x
->vertices
, 0);
944 if (bitmap_bit_p (processed
, v
))
947 np
= build_rdg_partition_for_component (rdg
, x
, &part_has_writes
);
948 bitmap_ior_into (partition
, np
);
949 bitmap_ior_into (processed
, np
);
954 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
956 fprintf (dump_file
, "ldist useful partition:\n");
957 dump_bitmap (dump_file
, partition
);
960 VEC_safe_push (bitmap
, heap
, *partitions
, partition
);
961 partition
= BITMAP_ALLOC (NULL
);
965 /* Add the nodes from the RDG that were not marked as processed, and
966 that are used outside the current loop. These are scalar
967 computations that are not yet part of previous partitions. */
968 for (i
= 0; i
< rdg
->n_vertices
; i
++)
969 if (!bitmap_bit_p (processed
, i
)
970 && rdg_defs_used_in_other_loops_p (rdg
, i
))
971 VEC_safe_push (int, heap
, *other_stores
, i
);
973 /* If there are still statements left in the OTHER_STORES array,
974 create other components and partitions with these stores and
975 their dependences. */
976 if (VEC_length (int, *other_stores
) > 0)
978 VEC (rdgc
, heap
) *comps
= VEC_alloc (rdgc
, heap
, 3);
979 VEC (int, heap
) *foo
= VEC_alloc (int, heap
, 3);
981 rdg_build_components (rdg
, *other_stores
, &comps
);
982 rdg_build_partitions (rdg
, comps
, &foo
, partitions
, processed
);
984 VEC_free (int, heap
, foo
);
985 free_rdg_components (comps
);
988 add_scalar_computations_to_partition (rdg
, *partitions
, partition
);
990 /* If there is something left in the last partition, save it. */
991 if (bitmap_count_bits (partition
) > 0)
992 VEC_safe_push (bitmap
, heap
, *partitions
, partition
);
994 BITMAP_FREE (partition
);
996 fuse_partitions_with_similar_memory_accesses (rdg
, partitions
);
999 /* Dump to FILE the PARTITIONS. */
1002 dump_rdg_partitions (FILE *file
, VEC (bitmap
, heap
) *partitions
)
1007 FOR_EACH_VEC_ELT (bitmap
, partitions
, i
, partition
)
1008 debug_bitmap_file (file
, partition
);
1011 /* Debug PARTITIONS. */
1012 extern void debug_rdg_partitions (VEC (bitmap
, heap
) *);
1015 debug_rdg_partitions (VEC (bitmap
, heap
) *partitions
)
1017 dump_rdg_partitions (stderr
, partitions
);
1020 /* Returns the number of read and write operations in the RDG. */
1023 number_of_rw_in_rdg (struct graph
*rdg
)
1027 for (i
= 0; i
< rdg
->n_vertices
; i
++)
1029 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1032 if (RDG_MEM_READS_STMT (rdg
, i
))
1039 /* Returns the number of read and write operations in a PARTITION of
1043 number_of_rw_in_partition (struct graph
*rdg
, bitmap partition
)
1049 EXECUTE_IF_SET_IN_BITMAP (partition
, 0, i
, ii
)
1051 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1054 if (RDG_MEM_READS_STMT (rdg
, i
))
1061 /* Returns true when one of the PARTITIONS contains all the read or
1062 write operations of RDG. */
1065 partition_contains_all_rw (struct graph
*rdg
, VEC (bitmap
, heap
) *partitions
)
1069 int nrw
= number_of_rw_in_rdg (rdg
);
1071 FOR_EACH_VEC_ELT (bitmap
, partitions
, i
, partition
)
1072 if (nrw
== number_of_rw_in_partition (rdg
, partition
))
1078 /* Generate code from STARTING_VERTICES in RDG. Returns the number of
1079 distributed loops. */
1082 ldist_gen (struct loop
*loop
, struct graph
*rdg
,
1083 VEC (int, heap
) *starting_vertices
)
1086 VEC (rdgc
, heap
) *components
= VEC_alloc (rdgc
, heap
, 3);
1087 VEC (bitmap
, heap
) *partitions
= VEC_alloc (bitmap
, heap
, 3);
1088 VEC (int, heap
) *other_stores
= VEC_alloc (int, heap
, 3);
1089 bitmap partition
, processed
= BITMAP_ALLOC (NULL
);
1091 remaining_stmts
= BITMAP_ALLOC (NULL
);
1092 upstream_mem_writes
= BITMAP_ALLOC (NULL
);
1094 for (i
= 0; i
< rdg
->n_vertices
; i
++)
1096 bitmap_set_bit (remaining_stmts
, i
);
1098 /* Save in OTHER_STORES all the memory writes that are not in
1099 STARTING_VERTICES. */
1100 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1106 FOR_EACH_VEC_ELT (int, starting_vertices
, j
, v
)
1114 VEC_safe_push (int, heap
, other_stores
, i
);
1118 mark_nodes_having_upstream_mem_writes (rdg
);
1119 rdg_build_components (rdg
, starting_vertices
, &components
);
1120 rdg_build_partitions (rdg
, components
, &other_stores
, &partitions
,
1122 BITMAP_FREE (processed
);
1123 nbp
= VEC_length (bitmap
, partitions
);
1126 || partition_contains_all_rw (rdg
, partitions
))
1129 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1130 dump_rdg_partitions (dump_file
, partitions
);
1132 FOR_EACH_VEC_ELT (bitmap
, partitions
, i
, partition
)
1133 if (!generate_code_for_partition (loop
, partition
, i
< nbp
- 1))
1136 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1137 update_ssa (TODO_update_ssa_only_virtuals
| TODO_update_ssa
);
1141 BITMAP_FREE (remaining_stmts
);
1142 BITMAP_FREE (upstream_mem_writes
);
1144 FOR_EACH_VEC_ELT (bitmap
, partitions
, i
, partition
)
1145 BITMAP_FREE (partition
);
1147 VEC_free (int, heap
, other_stores
);
1148 VEC_free (bitmap
, heap
, partitions
);
1149 free_rdg_components (components
);
1153 /* Distributes the code from LOOP in such a way that producer
1154 statements are placed before consumer statements. When STMTS is
1155 NULL, performs the maximal distribution, if STMTS is not NULL,
1156 tries to separate only these statements from the LOOP's body.
1157 Returns the number of distributed loops. */
1160 distribute_loop (struct loop
*loop
, VEC (gimple
, heap
) *stmts
)
1166 VEC (int, heap
) *vertices
;
1167 VEC (ddr_p
, heap
) *dependence_relations
;
1168 VEC (data_reference_p
, heap
) *datarefs
;
1169 VEC (loop_p
, heap
) *loop_nest
;
1171 if (loop
->num_nodes
> 2)
1173 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1175 "FIXME: Loop %d not distributed: it has more than two basic blocks.\n",
1181 datarefs
= VEC_alloc (data_reference_p
, heap
, 10);
1182 dependence_relations
= VEC_alloc (ddr_p
, heap
, 100);
1183 loop_nest
= VEC_alloc (loop_p
, heap
, 3);
1184 rdg
= build_rdg (loop
, &loop_nest
, &dependence_relations
, &datarefs
);
1188 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1190 "FIXME: Loop %d not distributed: failed to build the RDG.\n",
1193 free_dependence_relations (dependence_relations
);
1194 free_data_refs (datarefs
);
1195 VEC_free (loop_p
, heap
, loop_nest
);
1199 vertices
= VEC_alloc (int, heap
, 3);
1201 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1202 dump_rdg (dump_file
, rdg
);
1204 FOR_EACH_VEC_ELT (gimple
, stmts
, i
, s
)
1206 int v
= rdg_vertex_for_stmt (rdg
, s
);
1210 VEC_safe_push (int, heap
, vertices
, v
);
1212 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1214 "ldist asked to generate code for vertex %d\n", v
);
1218 res
= ldist_gen (loop
, rdg
, vertices
);
1219 VEC_free (int, heap
, vertices
);
1221 free_dependence_relations (dependence_relations
);
1222 free_data_refs (datarefs
);
1223 VEC_free (loop_p
, heap
, loop_nest
);
1227 /* Distribute all loops in the current function. */
1230 tree_loop_distribution (void)
1234 int nb_generated_loops
= 0;
1236 FOR_EACH_LOOP (li
, loop
, 0)
1238 VEC (gimple
, heap
) *work_list
= NULL
;
1239 int num
= loop
->num
;
1241 /* If the loop doesn't have a single exit we will fail anyway,
1242 so do that early. */
1243 if (!single_exit (loop
))
1246 /* If both flag_tree_loop_distribute_patterns and
1247 flag_tree_loop_distribution are set, then only
1248 distribute_patterns is executed. */
1249 if (flag_tree_loop_distribute_patterns
)
1251 /* With the following working list, we're asking
1252 distribute_loop to separate from the rest of the loop the
1253 stores of the form "A[i] = 0". */
1254 stores_zero_from_loop (loop
, &work_list
);
1256 /* Do nothing if there are no patterns to be distributed. */
1257 if (VEC_length (gimple
, work_list
) > 0)
1258 nb_generated_loops
= distribute_loop (loop
, work_list
);
1260 else if (flag_tree_loop_distribution
)
1262 /* With the following working list, we're asking
1263 distribute_loop to separate the stores of the loop: when
1264 dependences allow, it will end on having one store per
1266 stores_from_loop (loop
, &work_list
);
1268 /* A simple heuristic for cache locality is to not split
1269 stores to the same array. Without this call, an unrolled
1270 loop would be split into as many loops as unroll factor,
1271 each loop storing in the same array. */
1272 remove_similar_memory_refs (&work_list
);
1274 nb_generated_loops
= distribute_loop (loop
, work_list
);
1277 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1279 if (nb_generated_loops
> 1)
1280 fprintf (dump_file
, "Loop %d distributed: split to %d loops.\n",
1281 num
, nb_generated_loops
);
1283 fprintf (dump_file
, "Loop %d is the same.\n", num
);
1286 verify_loop_structure ();
1288 VEC_free (gimple
, heap
, work_list
);
1295 gate_tree_loop_distribution (void)
1297 return flag_tree_loop_distribution
1298 || flag_tree_loop_distribute_patterns
;
1301 struct gimple_opt_pass pass_loop_distribution
=
1306 gate_tree_loop_distribution
, /* gate */
1307 tree_loop_distribution
, /* execute */
1310 0, /* static_pass_number */
1311 TV_TREE_LOOP_DISTRIBUTION
, /* tv_id */
1312 PROP_cfg
| PROP_ssa
, /* properties_required */
1313 0, /* properties_provided */
1314 0, /* properties_destroyed */
1315 0, /* todo_flags_start */
1316 TODO_dump_func
/* todo_flags_finish */