2 Copyright (C) 2006-2016 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"
51 #include "tree-pass.h"
53 #include "gimple-pretty-print.h"
54 #include "fold-const.h"
56 #include "gimple-iterator.h"
57 #include "gimplify-me.h"
58 #include "stor-layout.h"
60 #include "tree-ssa-loop-manip.h"
61 #include "tree-ssa-loop.h"
62 #include "tree-into-ssa.h"
65 #include "tree-scalar-evolution.h"
66 #include "tree-vectorizer.h"
69 /* A Reduced Dependence Graph (RDG) vertex representing a statement. */
72 /* The statement represented by this vertex. */
75 /* Vector of data-references in this statement. */
76 vec
<data_reference_p
> datarefs
;
78 /* True when the statement contains a write to memory. */
81 /* True when the statement contains a read from memory. */
85 #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
86 #define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs
87 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
88 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
89 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
90 #define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I]))
91 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
92 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
94 /* Data dependence type. */
98 /* Read After Write (RAW). */
101 /* Control dependence (execute conditional on). */
105 /* Dependence information attached to an edge of the RDG. */
109 /* Type of the dependence. */
110 enum rdg_dep_type type
;
113 #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
115 /* Dump vertex I in RDG to FILE. */
118 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
120 struct vertex
*v
= &(rdg
->vertices
[i
]);
121 struct graph_edge
*e
;
123 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
124 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
125 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
128 for (e
= v
->pred
; e
; e
= e
->pred_next
)
129 fprintf (file
, " %d", e
->src
);
131 fprintf (file
, ") (out:");
134 for (e
= v
->succ
; e
; e
= e
->succ_next
)
135 fprintf (file
, " %d", e
->dest
);
137 fprintf (file
, ")\n");
138 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
139 fprintf (file
, ")\n");
142 /* Call dump_rdg_vertex on stderr. */
145 debug_rdg_vertex (struct graph
*rdg
, int i
)
147 dump_rdg_vertex (stderr
, rdg
, i
);
150 /* Dump the reduced dependence graph RDG to FILE. */
153 dump_rdg (FILE *file
, struct graph
*rdg
)
155 fprintf (file
, "(rdg\n");
156 for (int i
= 0; i
< rdg
->n_vertices
; i
++)
157 dump_rdg_vertex (file
, rdg
, i
);
158 fprintf (file
, ")\n");
161 /* Call dump_rdg on stderr. */
164 debug_rdg (struct graph
*rdg
)
166 dump_rdg (stderr
, rdg
);
170 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
173 pretty_printer buffer
;
174 pp_needs_newline (&buffer
) = false;
175 buffer
.buffer
->stream
= file
;
177 fprintf (file
, "digraph RDG {\n");
179 for (i
= 0; i
< rdg
->n_vertices
; i
++)
181 struct vertex
*v
= &(rdg
->vertices
[i
]);
182 struct graph_edge
*e
;
184 fprintf (file
, "%d [label=\"[%d] ", i
, i
);
185 pp_gimple_stmt_1 (&buffer
, RDGV_STMT (v
), 0, TDF_SLIM
);
187 fprintf (file
, "\"]\n");
189 /* Highlight reads from memory. */
190 if (RDG_MEM_READS_STMT (rdg
, i
))
191 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
193 /* Highlight stores to memory. */
194 if (RDG_MEM_WRITE_STMT (rdg
, i
))
195 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
198 for (e
= v
->succ
; e
; e
= e
->succ_next
)
199 switch (RDGE_TYPE (e
))
202 /* These are the most common dependences: don't print these. */
203 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
207 fprintf (file
, "%d -> %d [label=control] \n", i
, e
->dest
);
215 fprintf (file
, "}\n\n");
218 /* Display the Reduced Dependence Graph using dotty. */
221 dot_rdg (struct graph
*rdg
)
223 /* When debugging, you may want to enable the following code. */
225 FILE *file
= popen ("dot -Tx11", "w");
228 dot_rdg_1 (file
, rdg
);
230 close (fileno (file
));
233 dot_rdg_1 (stderr
, rdg
);
237 /* Returns the index of STMT in RDG. */
240 rdg_vertex_for_stmt (struct graph
*rdg ATTRIBUTE_UNUSED
, gimple
*stmt
)
242 int index
= gimple_uid (stmt
);
243 gcc_checking_assert (index
== -1 || RDG_STMT (rdg
, index
) == stmt
);
247 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
248 the index of DEF in RDG. */
251 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
253 use_operand_p imm_use_p
;
254 imm_use_iterator iterator
;
256 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
258 struct graph_edge
*e
;
259 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
264 e
= add_edge (rdg
, idef
, use
);
265 e
->data
= XNEW (struct rdg_edge
);
266 RDGE_TYPE (e
) = flow_dd
;
270 /* Creates an edge for the control dependences of BB to the vertex V. */
273 create_edge_for_control_dependence (struct graph
*rdg
, basic_block bb
,
274 int v
, control_dependences
*cd
)
278 EXECUTE_IF_SET_IN_BITMAP (cd
->get_edges_dependent_on (bb
->index
),
281 basic_block cond_bb
= cd
->get_edge_src (edge_n
);
282 gimple
*stmt
= last_stmt (cond_bb
);
283 if (stmt
&& is_ctrl_stmt (stmt
))
285 struct graph_edge
*e
;
286 int c
= rdg_vertex_for_stmt (rdg
, stmt
);
290 e
= add_edge (rdg
, c
, v
);
291 e
->data
= XNEW (struct rdg_edge
);
292 RDGE_TYPE (e
) = control_dd
;
297 /* Creates the edges of the reduced dependence graph RDG. */
300 create_rdg_flow_edges (struct graph
*rdg
)
306 for (i
= 0; i
< rdg
->n_vertices
; i
++)
307 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
309 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
312 /* Creates the edges of the reduced dependence graph RDG. */
315 create_rdg_cd_edges (struct graph
*rdg
, control_dependences
*cd
, loop_p loop
)
319 for (i
= 0; i
< rdg
->n_vertices
; i
++)
321 gimple
*stmt
= RDG_STMT (rdg
, i
);
322 if (gimple_code (stmt
) == GIMPLE_PHI
)
326 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->preds
)
327 if (flow_bb_inside_loop_p (loop
, e
->src
))
328 create_edge_for_control_dependence (rdg
, e
->src
, i
, cd
);
331 create_edge_for_control_dependence (rdg
, gimple_bb (stmt
), i
, cd
);
335 /* Build the vertices of the reduced dependence graph RDG. Return false
339 create_rdg_vertices (struct graph
*rdg
, vec
<gimple
*> stmts
, loop_p loop
,
340 vec
<data_reference_p
> *datarefs
)
345 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
347 struct vertex
*v
= &(rdg
->vertices
[i
]);
349 /* Record statement to vertex mapping. */
350 gimple_set_uid (stmt
, i
);
352 v
->data
= XNEW (struct rdg_vertex
);
353 RDGV_STMT (v
) = stmt
;
354 RDGV_DATAREFS (v
).create (0);
355 RDGV_HAS_MEM_WRITE (v
) = false;
356 RDGV_HAS_MEM_READS (v
) = false;
357 if (gimple_code (stmt
) == GIMPLE_PHI
)
360 unsigned drp
= datarefs
->length ();
361 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
363 for (unsigned j
= drp
; j
< datarefs
->length (); ++j
)
365 data_reference_p dr
= (*datarefs
)[j
];
367 RDGV_HAS_MEM_READS (v
) = true;
369 RDGV_HAS_MEM_WRITE (v
) = true;
370 RDGV_DATAREFS (v
).safe_push (dr
);
376 /* Initialize STMTS with all the statements of LOOP. The order in
377 which we discover statements is important as
378 generate_loops_for_partition is using the same traversal for
379 identifying statements in loop copies. */
382 stmts_from_loop (struct loop
*loop
, vec
<gimple
*> *stmts
)
385 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
387 for (i
= 0; i
< loop
->num_nodes
; i
++)
389 basic_block bb
= bbs
[i
];
391 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
393 if (!virtual_operand_p (gimple_phi_result (bsi
.phi ())))
394 stmts
->safe_push (bsi
.phi ());
396 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
399 gimple
*stmt
= gsi_stmt (bsi
);
400 if (gimple_code (stmt
) != GIMPLE_LABEL
&& !is_gimple_debug (stmt
))
401 stmts
->safe_push (stmt
);
408 /* Free the reduced dependence graph RDG. */
411 free_rdg (struct graph
*rdg
)
415 for (i
= 0; i
< rdg
->n_vertices
; i
++)
417 struct vertex
*v
= &(rdg
->vertices
[i
]);
418 struct graph_edge
*e
;
420 for (e
= v
->succ
; e
; e
= e
->succ_next
)
425 gimple_set_uid (RDGV_STMT (v
), -1);
426 free_data_refs (RDGV_DATAREFS (v
));
434 /* Build the Reduced Dependence Graph (RDG) with one vertex per
435 statement of the loop nest LOOP_NEST, and one edge per data dependence or
436 scalar dependence. */
438 static struct graph
*
439 build_rdg (vec
<loop_p
> loop_nest
, control_dependences
*cd
)
442 vec
<data_reference_p
> datarefs
;
444 /* Create the RDG vertices from the stmts of the loop nest. */
445 auto_vec
<gimple
*, 10> stmts
;
446 stmts_from_loop (loop_nest
[0], &stmts
);
447 rdg
= new_graph (stmts
.length ());
448 datarefs
.create (10);
449 if (!create_rdg_vertices (rdg
, stmts
, loop_nest
[0], &datarefs
))
457 create_rdg_flow_edges (rdg
);
459 create_rdg_cd_edges (rdg
, cd
, loop_nest
[0]);
468 enum partition_kind
{
469 PKIND_NORMAL
, PKIND_MEMSET
, PKIND_MEMCPY
477 enum partition_kind kind
;
478 /* data-references a kind != PKIND_NORMAL partition is about. */
479 data_reference_p main_dr
;
480 data_reference_p secondary_dr
;
486 /* Allocate and initialize a partition from BITMAP. */
489 partition_alloc (bitmap stmts
, bitmap loops
)
491 partition
*partition
= XCNEW (struct partition
);
492 partition
->stmts
= stmts
? stmts
: BITMAP_ALLOC (NULL
);
493 partition
->loops
= loops
? loops
: BITMAP_ALLOC (NULL
);
494 partition
->reduction_p
= false;
495 partition
->kind
= PKIND_NORMAL
;
499 /* Free PARTITION. */
502 partition_free (partition
*partition
)
504 BITMAP_FREE (partition
->stmts
);
505 BITMAP_FREE (partition
->loops
);
509 /* Returns true if the partition can be generated as a builtin. */
512 partition_builtin_p (partition
*partition
)
514 return partition
->kind
!= PKIND_NORMAL
;
517 /* Returns true if the partition contains a reduction. */
520 partition_reduction_p (partition
*partition
)
522 return partition
->reduction_p
;
525 /* Merge PARTITION into the partition DEST. */
528 partition_merge_into (partition
*dest
, partition
*partition
)
530 dest
->kind
= PKIND_NORMAL
;
531 bitmap_ior_into (dest
->stmts
, partition
->stmts
);
532 if (partition_reduction_p (partition
))
533 dest
->reduction_p
= true;
537 /* Returns true when DEF is an SSA_NAME defined in LOOP and used after
541 ssa_name_has_uses_outside_loop_p (tree def
, loop_p loop
)
543 imm_use_iterator imm_iter
;
546 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
548 gimple
*use_stmt
= USE_STMT (use_p
);
549 if (!is_gimple_debug (use_stmt
)
550 && loop
!= loop_containing_stmt (use_stmt
))
557 /* Returns true when STMT defines a scalar variable used after the
561 stmt_has_scalar_dependences_outside_loop (loop_p loop
, gimple
*stmt
)
566 if (gimple_code (stmt
) == GIMPLE_PHI
)
567 return ssa_name_has_uses_outside_loop_p (gimple_phi_result (stmt
), loop
);
569 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
570 if (ssa_name_has_uses_outside_loop_p (DEF_FROM_PTR (def_p
), loop
))
576 /* Return a copy of LOOP placed before LOOP. */
579 copy_loop_before (struct loop
*loop
)
582 edge preheader
= loop_preheader_edge (loop
);
584 initialize_original_copy_tables ();
585 res
= slpeel_tree_duplicate_loop_to_edge_cfg (loop
, NULL
, preheader
);
586 gcc_assert (res
!= NULL
);
587 free_original_copy_tables ();
588 delete_update_ssa ();
593 /* Creates an empty basic block after LOOP. */
596 create_bb_after_loop (struct loop
*loop
)
598 edge exit
= single_exit (loop
);
606 /* Generate code for PARTITION from the code in LOOP. The loop is
607 copied when COPY_P is true. All the statements not flagged in the
608 PARTITION bitmap are removed from the loop or from its copy. The
609 statements are indexed in sequence inside a basic block, and the
610 basic blocks of a loop are taken in dom order. */
613 generate_loops_for_partition (struct loop
*loop
, partition
*partition
,
621 loop
= copy_loop_before (loop
);
622 gcc_assert (loop
!= NULL
);
623 create_preheader (loop
, CP_SIMPLE_PREHEADERS
);
624 create_bb_after_loop (loop
);
627 /* Remove stmts not in the PARTITION bitmap. */
628 bbs
= get_loop_body_in_dom_order (loop
);
630 if (MAY_HAVE_DEBUG_STMTS
)
631 for (i
= 0; i
< loop
->num_nodes
; i
++)
633 basic_block bb
= bbs
[i
];
635 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
638 gphi
*phi
= bsi
.phi ();
639 if (!virtual_operand_p (gimple_phi_result (phi
))
640 && !bitmap_bit_p (partition
->stmts
, gimple_uid (phi
)))
641 reset_debug_uses (phi
);
644 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
646 gimple
*stmt
= gsi_stmt (bsi
);
647 if (gimple_code (stmt
) != GIMPLE_LABEL
648 && !is_gimple_debug (stmt
)
649 && !bitmap_bit_p (partition
->stmts
, gimple_uid (stmt
)))
650 reset_debug_uses (stmt
);
654 for (i
= 0; i
< loop
->num_nodes
; i
++)
656 basic_block bb
= bbs
[i
];
658 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);)
660 gphi
*phi
= bsi
.phi ();
661 if (!virtual_operand_p (gimple_phi_result (phi
))
662 && !bitmap_bit_p (partition
->stmts
, gimple_uid (phi
)))
663 remove_phi_node (&bsi
, true);
668 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);)
670 gimple
*stmt
= gsi_stmt (bsi
);
671 if (gimple_code (stmt
) != GIMPLE_LABEL
672 && !is_gimple_debug (stmt
)
673 && !bitmap_bit_p (partition
->stmts
, gimple_uid (stmt
)))
675 /* Choose an arbitrary path through the empty CFG part
676 that this unnecessary control stmt controls. */
677 if (gcond
*cond_stmt
= dyn_cast
<gcond
*> (stmt
))
679 gimple_cond_make_false (cond_stmt
);
682 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
684 gswitch
*switch_stmt
= as_a
<gswitch
*> (stmt
);
685 gimple_switch_set_index
686 (switch_stmt
, CASE_LOW (gimple_switch_label (switch_stmt
, 1)));
691 unlink_stmt_vdef (stmt
);
692 gsi_remove (&bsi
, true);
704 /* Build the size argument for a memory operation call. */
707 build_size_arg_loc (location_t loc
, data_reference_p dr
, tree nb_iter
,
710 tree size
= fold_convert_loc (loc
, sizetype
, nb_iter
);
712 size
= size_binop (PLUS_EXPR
, size
, size_one_node
);
713 size
= fold_build2_loc (loc
, MULT_EXPR
, sizetype
, size
,
714 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
))));
715 size
= fold_convert_loc (loc
, size_type_node
, size
);
719 /* Build an address argument for a memory operation call. */
722 build_addr_arg_loc (location_t loc
, data_reference_p dr
, tree nb_bytes
)
726 addr_base
= size_binop_loc (loc
, PLUS_EXPR
, DR_OFFSET (dr
), DR_INIT (dr
));
727 addr_base
= fold_convert_loc (loc
, sizetype
, addr_base
);
729 /* Test for a negative stride, iterating over every element. */
730 if (tree_int_cst_sgn (DR_STEP (dr
)) == -1)
732 addr_base
= size_binop_loc (loc
, MINUS_EXPR
, addr_base
,
733 fold_convert_loc (loc
, sizetype
, nb_bytes
));
734 addr_base
= size_binop_loc (loc
, PLUS_EXPR
, addr_base
,
735 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
))));
738 return fold_build_pointer_plus_loc (loc
, DR_BASE_ADDRESS (dr
), addr_base
);
741 /* If VAL memory representation contains the same value in all bytes,
742 return that value, otherwise return -1.
743 E.g. for 0x24242424 return 0x24, for IEEE double
744 747708026454360457216.0 return 0x44, etc. */
747 const_with_all_bytes_same (tree val
)
749 unsigned char buf
[64];
752 if (integer_zerop (val
)
754 || (TREE_CODE (val
) == CONSTRUCTOR
755 && !TREE_CLOBBER_P (val
)
756 && CONSTRUCTOR_NELTS (val
) == 0))
759 if (CHAR_BIT
!= 8 || BITS_PER_UNIT
!= 8)
762 len
= native_encode_expr (val
, buf
, sizeof (buf
));
765 for (i
= 1; i
< len
; i
++)
766 if (buf
[i
] != buf
[0])
771 /* Generate a call to memset for PARTITION in LOOP. */
774 generate_memset_builtin (struct loop
*loop
, partition
*partition
)
776 gimple_stmt_iterator gsi
;
777 gimple
*stmt
, *fn_call
;
778 tree mem
, fn
, nb_bytes
;
782 stmt
= DR_STMT (partition
->main_dr
);
783 loc
= gimple_location (stmt
);
785 /* The new statements will be placed before LOOP. */
786 gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
788 nb_bytes
= build_size_arg_loc (loc
, partition
->main_dr
, partition
->niter
,
789 partition
->plus_one
);
790 nb_bytes
= force_gimple_operand_gsi (&gsi
, nb_bytes
, true, NULL_TREE
,
791 false, GSI_CONTINUE_LINKING
);
792 mem
= build_addr_arg_loc (loc
, partition
->main_dr
, nb_bytes
);
793 mem
= force_gimple_operand_gsi (&gsi
, mem
, true, NULL_TREE
,
794 false, GSI_CONTINUE_LINKING
);
796 /* This exactly matches the pattern recognition in classify_partition. */
797 val
= gimple_assign_rhs1 (stmt
);
798 /* Handle constants like 0x15151515 and similarly
799 floating point constants etc. where all bytes are the same. */
800 int bytev
= const_with_all_bytes_same (val
);
802 val
= build_int_cst (integer_type_node
, bytev
);
803 else if (TREE_CODE (val
) == INTEGER_CST
)
804 val
= fold_convert (integer_type_node
, val
);
805 else if (!useless_type_conversion_p (integer_type_node
, TREE_TYPE (val
)))
807 tree tem
= make_ssa_name (integer_type_node
);
808 gimple
*cstmt
= gimple_build_assign (tem
, NOP_EXPR
, val
);
809 gsi_insert_after (&gsi
, cstmt
, GSI_CONTINUE_LINKING
);
813 fn
= build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET
));
814 fn_call
= gimple_build_call (fn
, 3, mem
, val
, nb_bytes
);
815 gsi_insert_after (&gsi
, fn_call
, GSI_CONTINUE_LINKING
);
817 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
819 fprintf (dump_file
, "generated memset");
821 fprintf (dump_file
, " zero\n");
823 fprintf (dump_file
, "\n");
827 /* Generate a call to memcpy for PARTITION in LOOP. */
830 generate_memcpy_builtin (struct loop
*loop
, partition
*partition
)
832 gimple_stmt_iterator gsi
;
833 gimple
*stmt
, *fn_call
;
834 tree dest
, src
, fn
, nb_bytes
;
836 enum built_in_function kind
;
838 stmt
= DR_STMT (partition
->main_dr
);
839 loc
= gimple_location (stmt
);
841 /* The new statements will be placed before LOOP. */
842 gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
844 nb_bytes
= build_size_arg_loc (loc
, partition
->main_dr
, partition
->niter
,
845 partition
->plus_one
);
846 nb_bytes
= force_gimple_operand_gsi (&gsi
, nb_bytes
, true, NULL_TREE
,
847 false, GSI_CONTINUE_LINKING
);
848 dest
= build_addr_arg_loc (loc
, partition
->main_dr
, nb_bytes
);
849 src
= build_addr_arg_loc (loc
, partition
->secondary_dr
, nb_bytes
);
850 if (ptr_derefs_may_alias_p (dest
, src
))
851 kind
= BUILT_IN_MEMMOVE
;
853 kind
= BUILT_IN_MEMCPY
;
855 dest
= force_gimple_operand_gsi (&gsi
, dest
, true, NULL_TREE
,
856 false, GSI_CONTINUE_LINKING
);
857 src
= force_gimple_operand_gsi (&gsi
, src
, true, NULL_TREE
,
858 false, GSI_CONTINUE_LINKING
);
859 fn
= build_fold_addr_expr (builtin_decl_implicit (kind
));
860 fn_call
= gimple_build_call (fn
, 3, dest
, src
, nb_bytes
);
861 gsi_insert_after (&gsi
, fn_call
, GSI_CONTINUE_LINKING
);
863 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
865 if (kind
== BUILT_IN_MEMCPY
)
866 fprintf (dump_file
, "generated memcpy\n");
868 fprintf (dump_file
, "generated memmove\n");
872 /* Remove and destroy the loop LOOP. */
875 destroy_loop (struct loop
*loop
)
877 unsigned nbbs
= loop
->num_nodes
;
878 edge exit
= single_exit (loop
);
879 basic_block src
= loop_preheader_edge (loop
)->src
, dest
= exit
->dest
;
883 bbs
= get_loop_body_in_dom_order (loop
);
885 redirect_edge_pred (exit
, src
);
886 exit
->flags
&= ~(EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
887 exit
->flags
|= EDGE_FALLTHRU
;
888 cancel_loop_tree (loop
);
889 rescan_loop_exit (exit
, false, true);
894 /* We have made sure to not leave any dangling uses of SSA
895 names defined in the loop. With the exception of virtuals.
896 Make sure we replace all uses of virtual defs that will remain
897 outside of the loop with the bare symbol as delete_basic_block
898 will release them. */
900 for (gphi_iterator gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
);
903 gphi
*phi
= gsi
.phi ();
904 if (virtual_operand_p (gimple_phi_result (phi
)))
905 mark_virtual_phi_result_for_renaming (phi
);
907 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]); !gsi_end_p (gsi
);
910 gimple
*stmt
= gsi_stmt (gsi
);
911 tree vdef
= gimple_vdef (stmt
);
912 if (vdef
&& TREE_CODE (vdef
) == SSA_NAME
)
913 mark_virtual_operand_for_renaming (vdef
);
915 delete_basic_block (bbs
[i
]);
921 set_immediate_dominator (CDI_DOMINATORS
, dest
,
922 recompute_dominator (CDI_DOMINATORS
, dest
));
925 /* Generates code for PARTITION. Return whether LOOP needs to be destroyed. */
928 generate_code_for_partition (struct loop
*loop
,
929 partition
*partition
, bool copy_p
)
931 switch (partition
->kind
)
934 /* Reductions all have to be in the last partition. */
935 gcc_assert (!partition_reduction_p (partition
)
937 generate_loops_for_partition (loop
, partition
, copy_p
);
941 generate_memset_builtin (loop
, partition
);
945 generate_memcpy_builtin (loop
, partition
);
952 /* Common tail for partitions we turn into a call. If this was the last
953 partition for which we generate code, we have to destroy the loop. */
960 /* Returns a partition with all the statements needed for computing
961 the vertex V of the RDG, also including the loop exit conditions. */
964 build_rdg_partition_for_vertex (struct graph
*rdg
, int v
)
966 partition
*partition
= partition_alloc (NULL
, NULL
);
967 auto_vec
<int, 3> nodes
;
971 graphds_dfs (rdg
, &v
, 1, &nodes
, false, NULL
);
973 FOR_EACH_VEC_ELT (nodes
, i
, x
)
975 bitmap_set_bit (partition
->stmts
, x
);
976 bitmap_set_bit (partition
->loops
,
977 loop_containing_stmt (RDG_STMT (rdg
, x
))->num
);
983 /* Classifies the builtin kind we can generate for PARTITION of RDG and LOOP.
984 For the moment we detect only the memset zero pattern. */
987 classify_partition (loop_p loop
, struct graph
*rdg
, partition
*partition
)
992 data_reference_p single_load
, single_store
;
993 bool volatiles_p
= false;
994 bool plus_one
= false;
996 partition
->kind
= PKIND_NORMAL
;
997 partition
->main_dr
= NULL
;
998 partition
->secondary_dr
= NULL
;
999 partition
->niter
= NULL_TREE
;
1000 partition
->plus_one
= false;
1002 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, bi
)
1004 gimple
*stmt
= RDG_STMT (rdg
, i
);
1006 if (gimple_has_volatile_ops (stmt
))
1009 /* If the stmt has uses outside of the loop mark it as reduction. */
1010 if (stmt_has_scalar_dependences_outside_loop (loop
, stmt
))
1012 partition
->reduction_p
= true;
1017 /* Perform general partition disqualification for builtins. */
1019 || !flag_tree_loop_distribute_patterns
)
1022 /* Detect memset and memcpy. */
1024 single_store
= NULL
;
1025 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, bi
)
1027 gimple
*stmt
= RDG_STMT (rdg
, i
);
1028 data_reference_p dr
;
1031 if (gimple_code (stmt
) == GIMPLE_PHI
)
1034 /* Any scalar stmts are ok. */
1035 if (!gimple_vuse (stmt
))
1038 /* Otherwise just regular loads/stores. */
1039 if (!gimple_assign_single_p (stmt
))
1042 /* But exactly one store and/or load. */
1043 for (j
= 0; RDG_DATAREFS (rdg
, i
).iterate (j
, &dr
); ++j
)
1045 if (DR_IS_READ (dr
))
1047 if (single_load
!= NULL
)
1053 if (single_store
!= NULL
)
1063 nb_iter
= number_of_latch_executions (loop
);
1064 if (!nb_iter
|| nb_iter
== chrec_dont_know
)
1066 if (dominated_by_p (CDI_DOMINATORS
, single_exit (loop
)->src
,
1067 gimple_bb (DR_STMT (single_store
))))
1070 if (single_store
&& !single_load
)
1072 gimple
*stmt
= DR_STMT (single_store
);
1073 tree rhs
= gimple_assign_rhs1 (stmt
);
1074 if (const_with_all_bytes_same (rhs
) == -1
1075 && (!INTEGRAL_TYPE_P (TREE_TYPE (rhs
))
1076 || (TYPE_MODE (TREE_TYPE (rhs
))
1077 != TYPE_MODE (unsigned_char_type_node
))))
1079 if (TREE_CODE (rhs
) == SSA_NAME
1080 && !SSA_NAME_IS_DEFAULT_DEF (rhs
)
1081 && flow_bb_inside_loop_p (loop
, gimple_bb (SSA_NAME_DEF_STMT (rhs
))))
1083 if (!adjacent_dr_p (single_store
)
1084 || !dominated_by_p (CDI_DOMINATORS
,
1085 loop
->latch
, gimple_bb (stmt
)))
1087 partition
->kind
= PKIND_MEMSET
;
1088 partition
->main_dr
= single_store
;
1089 partition
->niter
= nb_iter
;
1090 partition
->plus_one
= plus_one
;
1092 else if (single_store
&& single_load
)
1094 gimple
*store
= DR_STMT (single_store
);
1095 gimple
*load
= DR_STMT (single_load
);
1096 /* Direct aggregate copy or via an SSA name temporary. */
1098 && gimple_assign_lhs (load
) != gimple_assign_rhs1 (store
))
1100 if (!adjacent_dr_p (single_store
)
1101 || !adjacent_dr_p (single_load
)
1102 || !operand_equal_p (DR_STEP (single_store
),
1103 DR_STEP (single_load
), 0)
1104 || !dominated_by_p (CDI_DOMINATORS
,
1105 loop
->latch
, gimple_bb (store
)))
1107 /* Now check that if there is a dependence this dependence is
1108 of a suitable form for memmove. */
1109 vec
<loop_p
> loops
= vNULL
;
1111 loops
.safe_push (loop
);
1112 ddr
= initialize_data_dependence_relation (single_load
, single_store
,
1114 compute_affine_dependence (ddr
, loop
);
1115 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
1117 free_dependence_relation (ddr
);
1121 if (DDR_ARE_DEPENDENT (ddr
) != chrec_known
)
1123 if (DDR_NUM_DIST_VECTS (ddr
) == 0)
1125 free_dependence_relation (ddr
);
1129 lambda_vector dist_v
;
1130 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
1132 int dist
= dist_v
[index_in_loop_nest (loop
->num
,
1133 DDR_LOOP_NEST (ddr
))];
1134 if (dist
> 0 && !DDR_REVERSED_P (ddr
))
1136 free_dependence_relation (ddr
);
1142 free_dependence_relation (ddr
);
1144 partition
->kind
= PKIND_MEMCPY
;
1145 partition
->main_dr
= single_store
;
1146 partition
->secondary_dr
= single_load
;
1147 partition
->niter
= nb_iter
;
1148 partition
->plus_one
= plus_one
;
1152 /* For a data reference REF, return the declaration of its base
1153 address or NULL_TREE if the base is not determined. */
1156 ref_base_address (data_reference_p dr
)
1158 tree base_address
= DR_BASE_ADDRESS (dr
);
1160 && TREE_CODE (base_address
) == ADDR_EXPR
)
1161 return TREE_OPERAND (base_address
, 0);
1163 return base_address
;
1166 /* Returns true when PARTITION1 and PARTITION2 have similar memory
1170 similar_memory_accesses (struct graph
*rdg
, partition
*partition1
,
1171 partition
*partition2
)
1173 unsigned i
, j
, k
, l
;
1174 bitmap_iterator bi
, bj
;
1175 data_reference_p ref1
, ref2
;
1177 /* First check whether in the intersection of the two partitions are
1178 any loads or stores. Common loads are the situation that happens
1180 EXECUTE_IF_AND_IN_BITMAP (partition1
->stmts
, partition2
->stmts
, 0, i
, bi
)
1181 if (RDG_MEM_WRITE_STMT (rdg
, i
)
1182 || RDG_MEM_READS_STMT (rdg
, i
))
1185 /* Then check all data-references against each other. */
1186 EXECUTE_IF_SET_IN_BITMAP (partition1
->stmts
, 0, i
, bi
)
1187 if (RDG_MEM_WRITE_STMT (rdg
, i
)
1188 || RDG_MEM_READS_STMT (rdg
, i
))
1189 EXECUTE_IF_SET_IN_BITMAP (partition2
->stmts
, 0, j
, bj
)
1190 if (RDG_MEM_WRITE_STMT (rdg
, j
)
1191 || RDG_MEM_READS_STMT (rdg
, j
))
1193 FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg
, i
), k
, ref1
)
1195 tree base1
= ref_base_address (ref1
);
1197 FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg
, j
), l
, ref2
)
1198 if (base1
== ref_base_address (ref2
))
1206 /* Aggregate several components into a useful partition that is
1207 registered in the PARTITIONS vector. Partitions will be
1208 distributed in different loops. */
1211 rdg_build_partitions (struct graph
*rdg
,
1212 vec
<gimple
*> starting_stmts
,
1213 vec
<partition
*> *partitions
)
1215 bitmap processed
= BITMAP_ALLOC (NULL
);
1219 FOR_EACH_VEC_ELT (starting_stmts
, i
, stmt
)
1221 int v
= rdg_vertex_for_stmt (rdg
, stmt
);
1223 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1225 "ldist asked to generate code for vertex %d\n", v
);
1227 /* If the vertex is already contained in another partition so
1228 is the partition rooted at it. */
1229 if (bitmap_bit_p (processed
, v
))
1232 partition
*partition
= build_rdg_partition_for_vertex (rdg
, v
);
1233 bitmap_ior_into (processed
, partition
->stmts
);
1235 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1237 fprintf (dump_file
, "ldist useful partition:\n");
1238 dump_bitmap (dump_file
, partition
->stmts
);
1241 partitions
->safe_push (partition
);
1244 /* All vertices should have been assigned to at least one partition now,
1245 other than vertices belonging to dead code. */
1247 BITMAP_FREE (processed
);
1250 /* Dump to FILE the PARTITIONS. */
1253 dump_rdg_partitions (FILE *file
, vec
<partition
*> partitions
)
1256 partition
*partition
;
1258 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1259 debug_bitmap_file (file
, partition
->stmts
);
1262 /* Debug PARTITIONS. */
1263 extern void debug_rdg_partitions (vec
<partition
*> );
1266 debug_rdg_partitions (vec
<partition
*> partitions
)
1268 dump_rdg_partitions (stderr
, partitions
);
1271 /* Returns the number of read and write operations in the RDG. */
1274 number_of_rw_in_rdg (struct graph
*rdg
)
1278 for (i
= 0; i
< rdg
->n_vertices
; i
++)
1280 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1283 if (RDG_MEM_READS_STMT (rdg
, i
))
1290 /* Returns the number of read and write operations in a PARTITION of
1294 number_of_rw_in_partition (struct graph
*rdg
, partition
*partition
)
1300 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, ii
)
1302 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1305 if (RDG_MEM_READS_STMT (rdg
, i
))
1312 /* Returns true when one of the PARTITIONS contains all the read or
1313 write operations of RDG. */
1316 partition_contains_all_rw (struct graph
*rdg
,
1317 vec
<partition
*> partitions
)
1320 partition
*partition
;
1321 int nrw
= number_of_rw_in_rdg (rdg
);
1323 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1324 if (nrw
== number_of_rw_in_partition (rdg
, partition
))
1330 /* Compute partition dependence created by the data references in DRS1
1331 and DRS2 and modify and return DIR according to that. */
1334 pg_add_dependence_edges (struct graph
*rdg
, vec
<loop_p
> loops
, int dir
,
1335 vec
<data_reference_p
> drs1
,
1336 vec
<data_reference_p
> drs2
)
1338 data_reference_p dr1
, dr2
;
1340 /* dependence direction - 0 is no dependence, -1 is back,
1341 1 is forth, 2 is both (we can stop then, merging will occur). */
1342 for (int ii
= 0; drs1
.iterate (ii
, &dr1
); ++ii
)
1343 for (int jj
= 0; drs2
.iterate (jj
, &dr2
); ++jj
)
1345 data_reference_p saved_dr1
= dr1
;
1348 /* Re-shuffle data-refs to be in dominator order. */
1349 if (rdg_vertex_for_stmt (rdg
, DR_STMT (dr1
))
1350 > rdg_vertex_for_stmt (rdg
, DR_STMT (dr2
)))
1352 std::swap (dr1
, dr2
);
1353 this_dir
= -this_dir
;
1355 ddr
= initialize_data_dependence_relation (dr1
, dr2
, loops
);
1356 compute_affine_dependence (ddr
, loops
[0]);
1357 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
1359 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1361 if (DDR_REVERSED_P (ddr
))
1363 std::swap (dr1
, dr2
);
1364 this_dir
= -this_dir
;
1366 /* Known dependences can still be unordered througout the
1367 iteration space, see gcc.dg/tree-ssa/ldist-16.c. */
1368 if (DDR_NUM_DIST_VECTS (ddr
) != 1)
1370 /* If the overlap is exact preserve stmt order. */
1371 else if (lambda_vector_zerop (DDR_DIST_VECT (ddr
, 0), 1))
1375 /* Else as the distance vector is lexicographic positive
1376 swap the dependence direction. */
1377 this_dir
= -this_dir
;
1382 free_dependence_relation (ddr
);
1385 else if (dir
!= this_dir
)
1387 /* Shuffle "back" dr1. */
1393 /* Compare postorder number of the partition graph vertices V1 and V2. */
1396 pgcmp (const void *v1_
, const void *v2_
)
1398 const vertex
*v1
= (const vertex
*)v1_
;
1399 const vertex
*v2
= (const vertex
*)v2_
;
1400 return v2
->post
- v1
->post
;
1403 /* Distributes the code from LOOP in such a way that producer
1404 statements are placed before consumer statements. Tries to separate
1405 only the statements from STMTS into separate loops.
1406 Returns the number of distributed loops. Set *DESTROY_P to whether
1407 LOOP needs to be destroyed. */
1410 distribute_loop (struct loop
*loop
, vec
<gimple
*> stmts
,
1411 control_dependences
*cd
, int *nb_calls
, bool *destroy_p
)
1414 partition
*partition
;
1422 auto_vec
<loop_p
, 3> loop_nest
;
1423 if (!find_loop_nest (loop
, &loop_nest
))
1426 rdg
= build_rdg (loop_nest
, cd
);
1429 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1431 "Loop %d not distributed: failed to build the RDG.\n",
1437 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1438 dump_rdg (dump_file
, rdg
);
1440 auto_vec
<struct partition
*, 3> partitions
;
1441 rdg_build_partitions (rdg
, stmts
, &partitions
);
1443 any_builtin
= false;
1444 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1446 classify_partition (loop
, rdg
, partition
);
1447 any_builtin
|= partition_builtin_p (partition
);
1450 /* If we are only distributing patterns but did not detect any,
1452 if (!flag_tree_loop_distribution
1459 /* If we are only distributing patterns fuse all partitions that
1460 were not classified as builtins. This also avoids chopping
1461 a loop into pieces, separated by builtin calls. That is, we
1462 only want no or a single loop body remaining. */
1463 struct partition
*into
;
1464 if (!flag_tree_loop_distribution
)
1466 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
1467 if (!partition_builtin_p (into
))
1469 for (++i
; partitions
.iterate (i
, &partition
); ++i
)
1470 if (!partition_builtin_p (partition
))
1472 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1474 fprintf (dump_file
, "fusing non-builtin partitions\n");
1475 dump_bitmap (dump_file
, into
->stmts
);
1476 dump_bitmap (dump_file
, partition
->stmts
);
1478 partition_merge_into (into
, partition
);
1479 partitions
.unordered_remove (i
);
1480 partition_free (partition
);
1485 /* Due to limitations in the transform phase we have to fuse all
1486 reduction partitions into the last partition so the existing
1487 loop will contain all loop-closed PHI nodes. */
1488 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
1489 if (partition_reduction_p (into
))
1491 for (i
= i
+ 1; partitions
.iterate (i
, &partition
); ++i
)
1492 if (partition_reduction_p (partition
))
1494 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1496 fprintf (dump_file
, "fusing partitions\n");
1497 dump_bitmap (dump_file
, into
->stmts
);
1498 dump_bitmap (dump_file
, partition
->stmts
);
1499 fprintf (dump_file
, "because they have reductions\n");
1501 partition_merge_into (into
, partition
);
1502 partitions
.unordered_remove (i
);
1503 partition_free (partition
);
1507 /* Apply our simple cost model - fuse partitions with similar
1509 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
1511 bool changed
= false;
1512 if (partition_builtin_p (into
))
1515 partitions
.iterate (j
, &partition
); ++j
)
1517 if (!partition_builtin_p (partition
)
1518 && similar_memory_accesses (rdg
, into
, partition
))
1520 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1522 fprintf (dump_file
, "fusing partitions\n");
1523 dump_bitmap (dump_file
, into
->stmts
);
1524 dump_bitmap (dump_file
, partition
->stmts
);
1525 fprintf (dump_file
, "because they have similar "
1526 "memory accesses\n");
1528 partition_merge_into (into
, partition
);
1529 partitions
.unordered_remove (j
);
1530 partition_free (partition
);
1535 /* If we fused 0 1 2 in step 1 to 0,2 1 as 0 and 2 have similar
1536 accesses when 1 and 2 have similar accesses but not 0 and 1
1537 then in the next iteration we will fail to consider merging
1538 1 into 0,2. So try again if we did any merging into 0. */
1543 /* Build the partition dependency graph. */
1544 if (partitions
.length () > 1)
1546 pg
= new_graph (partitions
.length ());
1548 struct partition
*partition
;
1549 vec
<data_reference_p
> writes
;
1550 vec
<data_reference_p
> reads
;
1552 #define PGDATA(i) ((pgdata *)(pg->vertices[i].data))
1553 for (i
= 0; partitions
.iterate (i
, &partition
); ++i
)
1555 vertex
*v
= &pg
->vertices
[i
];
1556 pgdata
*data
= new pgdata
;
1557 data_reference_p dr
;
1558 /* FIXME - leaks. */
1562 data
->partition
= partition
;
1563 data
->reads
= vNULL
;
1564 data
->writes
= vNULL
;
1565 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, j
, bi
)
1566 for (int k
= 0; RDG_DATAREFS (rdg
, j
).iterate (k
, &dr
); ++k
)
1567 if (DR_IS_READ (dr
))
1568 data
->reads
.safe_push (dr
);
1570 data
->writes
.safe_push (dr
);
1572 struct partition
*partition1
, *partition2
;
1573 for (i
= 0; partitions
.iterate (i
, &partition1
); ++i
)
1574 for (int j
= i
+ 1; partitions
.iterate (j
, &partition2
); ++j
)
1576 /* dependence direction - 0 is no dependence, -1 is back,
1577 1 is forth, 2 is both (we can stop then, merging will occur). */
1579 dir
= pg_add_dependence_edges (rdg
, loop_nest
, dir
,
1583 dir
= pg_add_dependence_edges (rdg
, loop_nest
, dir
,
1587 dir
= pg_add_dependence_edges (rdg
, loop_nest
, dir
,
1590 if (dir
== 1 || dir
== 2)
1591 add_edge (pg
, i
, j
);
1592 if (dir
== -1 || dir
== 2)
1593 add_edge (pg
, j
, i
);
1596 /* Add edges to the reduction partition (if any) to force it last. */
1598 for (j
= 0; partitions
.iterate (j
, &partition
); ++j
)
1599 if (partition_reduction_p (partition
))
1601 if (j
< partitions
.length ())
1603 for (unsigned i
= 0; partitions
.iterate (i
, &partition
); ++i
)
1605 add_edge (pg
, i
, j
);
1608 /* Compute partitions we cannot separate and fuse them. */
1609 num_sccs
= graphds_scc (pg
, NULL
);
1610 for (i
= 0; i
< num_sccs
; ++i
)
1612 struct partition
*first
;
1614 for (j
= 0; partitions
.iterate (j
, &first
); ++j
)
1615 if (pg
->vertices
[j
].component
== i
)
1617 for (j
= j
+ 1; partitions
.iterate (j
, &partition
); ++j
)
1618 if (pg
->vertices
[j
].component
== i
)
1620 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1622 fprintf (dump_file
, "fusing partitions\n");
1623 dump_bitmap (dump_file
, first
->stmts
);
1624 dump_bitmap (dump_file
, partition
->stmts
);
1625 fprintf (dump_file
, "because they are in the same "
1626 "dependence SCC\n");
1628 partition_merge_into (first
, partition
);
1629 partitions
[j
] = NULL
;
1630 partition_free (partition
);
1631 PGDATA (j
)->partition
= NULL
;
1635 /* Now order the remaining nodes in postorder. */
1636 qsort (pg
->vertices
, pg
->n_vertices
, sizeof (vertex
), pgcmp
);
1637 partitions
.truncate (0);
1638 for (i
= 0; i
< pg
->n_vertices
; ++i
)
1640 pgdata
*data
= PGDATA (i
);
1641 if (data
->partition
)
1642 partitions
.safe_push (data
->partition
);
1643 data
->reads
.release ();
1644 data
->writes
.release ();
1647 gcc_assert (partitions
.length () == (unsigned)num_sccs
);
1651 nbp
= partitions
.length ();
1653 || (nbp
== 1 && !partition_builtin_p (partitions
[0]))
1654 || (nbp
> 1 && partition_contains_all_rw (rdg
, partitions
)))
1660 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1661 dump_rdg_partitions (dump_file
, partitions
);
1663 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1665 if (partition_builtin_p (partition
))
1667 *destroy_p
|= generate_code_for_partition (loop
, partition
, i
< nbp
- 1);
1672 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1673 partition_free (partition
);
1676 return nbp
- *nb_calls
;
1679 /* Distribute all loops in the current function. */
1683 const pass_data pass_data_loop_distribution
=
1685 GIMPLE_PASS
, /* type */
1687 OPTGROUP_LOOP
, /* optinfo_flags */
1688 TV_TREE_LOOP_DISTRIBUTION
, /* tv_id */
1689 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1690 0, /* properties_provided */
1691 0, /* properties_destroyed */
1692 0, /* todo_flags_start */
1693 0, /* todo_flags_finish */
1696 class pass_loop_distribution
: public gimple_opt_pass
1699 pass_loop_distribution (gcc::context
*ctxt
)
1700 : gimple_opt_pass (pass_data_loop_distribution
, ctxt
)
1703 /* opt_pass methods: */
1704 virtual bool gate (function
*)
1706 return flag_tree_loop_distribution
1707 || flag_tree_loop_distribute_patterns
;
1710 virtual unsigned int execute (function
*);
1712 }; // class pass_loop_distribution
1715 pass_loop_distribution::execute (function
*fun
)
1718 bool changed
= false;
1720 control_dependences
*cd
= NULL
;
1721 auto_vec
<loop_p
> loops_to_be_destroyed
;
1723 FOR_ALL_BB_FN (bb
, fun
)
1725 gimple_stmt_iterator gsi
;
1726 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1727 gimple_set_uid (gsi_stmt (gsi
), -1);
1728 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1729 gimple_set_uid (gsi_stmt (gsi
), -1);
1732 /* We can at the moment only distribute non-nested loops, thus restrict
1733 walking to innermost loops. */
1734 FOR_EACH_LOOP (loop
, LI_ONLY_INNERMOST
)
1736 auto_vec
<gimple
*> work_list
;
1738 int num
= loop
->num
;
1741 /* If the loop doesn't have a single exit we will fail anyway,
1742 so do that early. */
1743 if (!single_exit (loop
))
1746 /* Only optimize hot loops. */
1747 if (!optimize_loop_for_speed_p (loop
))
1750 /* Initialize the worklist with stmts we seed the partitions with. */
1751 bbs
= get_loop_body_in_dom_order (loop
);
1752 for (i
= 0; i
< loop
->num_nodes
; ++i
)
1754 for (gphi_iterator gsi
= gsi_start_phis (bbs
[i
]);
1758 gphi
*phi
= gsi
.phi ();
1759 if (virtual_operand_p (gimple_phi_result (phi
)))
1761 /* Distribute stmts which have defs that are used outside of
1763 if (!stmt_has_scalar_dependences_outside_loop (loop
, phi
))
1765 work_list
.safe_push (phi
);
1767 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]);
1771 gimple
*stmt
= gsi_stmt (gsi
);
1773 /* If there is a stmt with side-effects bail out - we
1774 cannot and should not distribute this loop. */
1775 if (gimple_has_side_effects (stmt
))
1777 work_list
.truncate (0);
1781 /* Distribute stmts which have defs that are used outside of
1783 if (stmt_has_scalar_dependences_outside_loop (loop
, stmt
))
1785 /* Otherwise only distribute stores for now. */
1786 else if (!gimple_vdef (stmt
))
1789 work_list
.safe_push (stmt
);
1795 int nb_generated_loops
= 0;
1796 int nb_generated_calls
= 0;
1797 location_t loc
= find_loop_location (loop
);
1798 if (work_list
.length () > 0)
1802 calculate_dominance_info (CDI_DOMINATORS
);
1803 calculate_dominance_info (CDI_POST_DOMINATORS
);
1804 cd
= new control_dependences ();
1805 free_dominance_info (CDI_POST_DOMINATORS
);
1808 nb_generated_loops
= distribute_loop (loop
, work_list
, cd
,
1809 &nb_generated_calls
,
1812 loops_to_be_destroyed
.safe_push (loop
);
1815 if (nb_generated_loops
+ nb_generated_calls
> 0)
1818 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
,
1819 loc
, "Loop %d distributed: split to %d loops "
1820 "and %d library calls.\n",
1821 num
, nb_generated_loops
, nb_generated_calls
);
1823 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1824 fprintf (dump_file
, "Loop %d is the same.\n", num
);
1832 /* Destroy loop bodies that could not be reused. Do this late as we
1833 otherwise can end up refering to stale data in control dependences. */
1835 FOR_EACH_VEC_ELT (loops_to_be_destroyed
, i
, loop
)
1836 destroy_loop (loop
);
1838 /* Cached scalar evolutions now may refer to wrong or non-existing
1841 mark_virtual_operands_for_renaming (fun
);
1842 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1845 checking_verify_loop_structure ();
1853 make_pass_loop_distribution (gcc::context
*ctxt
)
1855 return new pass_loop_distribution (ctxt
);