2 Copyright (C) 2006-2015 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"
55 #include "fold-const.h"
58 #include "hard-reg-set.h"
61 #include "dominance.h"
64 #include "basic-block.h"
65 #include "tree-ssa-alias.h"
66 #include "internal-fn.h"
67 #include "gimple-expr.h"
70 #include "gimple-iterator.h"
71 #include "gimplify-me.h"
72 #include "stor-layout.h"
73 #include "gimple-ssa.h"
75 #include "tree-phinodes.h"
76 #include "ssa-iterators.h"
77 #include "stringpool.h"
78 #include "tree-ssanames.h"
79 #include "tree-ssa-loop-manip.h"
80 #include "tree-ssa-loop.h"
81 #include "tree-into-ssa.h"
84 #include "tree-chrec.h"
85 #include "tree-data-ref.h"
86 #include "tree-scalar-evolution.h"
87 #include "tree-pass.h"
88 #include "gimple-pretty-print.h"
89 #include "tree-vectorizer.h"
92 /* A Reduced Dependence Graph (RDG) vertex representing a statement. */
93 typedef struct rdg_vertex
95 /* The statement represented by this vertex. */
98 /* Vector of data-references in this statement. */
99 vec
<data_reference_p
> datarefs
;
101 /* True when the statement contains a write to memory. */
104 /* True when the statement contains a read from memory. */
108 #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
109 #define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs
110 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
111 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
112 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
113 #define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I]))
114 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
115 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
117 /* Data dependence type. */
121 /* Read After Write (RAW). */
124 /* Control dependence (execute conditional on). */
128 /* Dependence information attached to an edge of the RDG. */
130 typedef struct rdg_edge
132 /* Type of the dependence. */
133 enum rdg_dep_type type
;
136 #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
138 /* Dump vertex I in RDG to FILE. */
141 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
143 struct vertex
*v
= &(rdg
->vertices
[i
]);
144 struct graph_edge
*e
;
146 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
147 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
148 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
151 for (e
= v
->pred
; e
; e
= e
->pred_next
)
152 fprintf (file
, " %d", e
->src
);
154 fprintf (file
, ") (out:");
157 for (e
= v
->succ
; e
; e
= e
->succ_next
)
158 fprintf (file
, " %d", e
->dest
);
160 fprintf (file
, ")\n");
161 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
162 fprintf (file
, ")\n");
165 /* Call dump_rdg_vertex on stderr. */
168 debug_rdg_vertex (struct graph
*rdg
, int i
)
170 dump_rdg_vertex (stderr
, rdg
, i
);
173 /* Dump the reduced dependence graph RDG to FILE. */
176 dump_rdg (FILE *file
, struct graph
*rdg
)
178 fprintf (file
, "(rdg\n");
179 for (int i
= 0; i
< rdg
->n_vertices
; i
++)
180 dump_rdg_vertex (file
, rdg
, i
);
181 fprintf (file
, ")\n");
184 /* Call dump_rdg on stderr. */
187 debug_rdg (struct graph
*rdg
)
189 dump_rdg (stderr
, rdg
);
193 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
196 pretty_printer buffer
;
197 pp_needs_newline (&buffer
) = false;
198 buffer
.buffer
->stream
= file
;
200 fprintf (file
, "digraph RDG {\n");
202 for (i
= 0; i
< rdg
->n_vertices
; i
++)
204 struct vertex
*v
= &(rdg
->vertices
[i
]);
205 struct graph_edge
*e
;
207 fprintf (file
, "%d [label=\"[%d] ", i
, i
);
208 pp_gimple_stmt_1 (&buffer
, RDGV_STMT (v
), 0, TDF_SLIM
);
210 fprintf (file
, "\"]\n");
212 /* Highlight reads from memory. */
213 if (RDG_MEM_READS_STMT (rdg
, i
))
214 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
216 /* Highlight stores to memory. */
217 if (RDG_MEM_WRITE_STMT (rdg
, i
))
218 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
221 for (e
= v
->succ
; e
; e
= e
->succ_next
)
222 switch (RDGE_TYPE (e
))
225 /* These are the most common dependences: don't print these. */
226 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
230 fprintf (file
, "%d -> %d [label=control] \n", i
, e
->dest
);
238 fprintf (file
, "}\n\n");
241 /* Display the Reduced Dependence Graph using dotty. */
244 dot_rdg (struct graph
*rdg
)
246 /* When debugging, you may want to enable the following code. */
248 FILE *file
= popen ("dot -Tx11", "w");
251 dot_rdg_1 (file
, rdg
);
253 close (fileno (file
));
256 dot_rdg_1 (stderr
, rdg
);
260 /* Returns the index of STMT in RDG. */
263 rdg_vertex_for_stmt (struct graph
*rdg ATTRIBUTE_UNUSED
, gimple stmt
)
265 int index
= gimple_uid (stmt
);
266 gcc_checking_assert (index
== -1 || RDG_STMT (rdg
, index
) == stmt
);
270 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
271 the index of DEF in RDG. */
274 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
276 use_operand_p imm_use_p
;
277 imm_use_iterator iterator
;
279 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
281 struct graph_edge
*e
;
282 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
287 e
= add_edge (rdg
, idef
, use
);
288 e
->data
= XNEW (struct rdg_edge
);
289 RDGE_TYPE (e
) = flow_dd
;
293 /* Creates an edge for the control dependences of BB to the vertex V. */
296 create_edge_for_control_dependence (struct graph
*rdg
, basic_block bb
,
297 int v
, control_dependences
*cd
)
301 EXECUTE_IF_SET_IN_BITMAP (cd
->get_edges_dependent_on (bb
->index
),
304 basic_block cond_bb
= cd
->get_edge (edge_n
)->src
;
305 gimple stmt
= last_stmt (cond_bb
);
306 if (stmt
&& is_ctrl_stmt (stmt
))
308 struct graph_edge
*e
;
309 int c
= rdg_vertex_for_stmt (rdg
, stmt
);
313 e
= add_edge (rdg
, c
, v
);
314 e
->data
= XNEW (struct rdg_edge
);
315 RDGE_TYPE (e
) = control_dd
;
320 /* Creates the edges of the reduced dependence graph RDG. */
323 create_rdg_flow_edges (struct graph
*rdg
)
329 for (i
= 0; i
< rdg
->n_vertices
; i
++)
330 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
332 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
335 /* Creates the edges of the reduced dependence graph RDG. */
338 create_rdg_cd_edges (struct graph
*rdg
, control_dependences
*cd
)
342 for (i
= 0; i
< rdg
->n_vertices
; i
++)
344 gimple stmt
= RDG_STMT (rdg
, i
);
345 if (gimple_code (stmt
) == GIMPLE_PHI
)
349 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->preds
)
350 create_edge_for_control_dependence (rdg
, e
->src
, i
, cd
);
353 create_edge_for_control_dependence (rdg
, gimple_bb (stmt
), i
, cd
);
357 /* Build the vertices of the reduced dependence graph RDG. Return false
361 create_rdg_vertices (struct graph
*rdg
, vec
<gimple
> stmts
, loop_p loop
,
362 vec
<data_reference_p
> *datarefs
)
367 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
369 struct vertex
*v
= &(rdg
->vertices
[i
]);
371 /* Record statement to vertex mapping. */
372 gimple_set_uid (stmt
, i
);
374 v
->data
= XNEW (struct rdg_vertex
);
375 RDGV_STMT (v
) = stmt
;
376 RDGV_DATAREFS (v
).create (0);
377 RDGV_HAS_MEM_WRITE (v
) = false;
378 RDGV_HAS_MEM_READS (v
) = false;
379 if (gimple_code (stmt
) == GIMPLE_PHI
)
382 unsigned drp
= datarefs
->length ();
383 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
385 for (unsigned j
= drp
; j
< datarefs
->length (); ++j
)
387 data_reference_p dr
= (*datarefs
)[j
];
389 RDGV_HAS_MEM_READS (v
) = true;
391 RDGV_HAS_MEM_WRITE (v
) = true;
392 RDGV_DATAREFS (v
).safe_push (dr
);
398 /* Initialize STMTS with all the statements of LOOP. The order in
399 which we discover statements is important as
400 generate_loops_for_partition is using the same traversal for
401 identifying statements in loop copies. */
404 stmts_from_loop (struct loop
*loop
, vec
<gimple
> *stmts
)
407 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
409 for (i
= 0; i
< loop
->num_nodes
; i
++)
411 basic_block bb
= bbs
[i
];
413 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
415 if (!virtual_operand_p (gimple_phi_result (bsi
.phi ())))
416 stmts
->safe_push (bsi
.phi ());
418 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
421 gimple stmt
= gsi_stmt (bsi
);
422 if (gimple_code (stmt
) != GIMPLE_LABEL
&& !is_gimple_debug (stmt
))
423 stmts
->safe_push (stmt
);
430 /* Free the reduced dependence graph RDG. */
433 free_rdg (struct graph
*rdg
)
437 for (i
= 0; i
< rdg
->n_vertices
; i
++)
439 struct vertex
*v
= &(rdg
->vertices
[i
]);
440 struct graph_edge
*e
;
442 for (e
= v
->succ
; e
; e
= e
->succ_next
)
447 gimple_set_uid (RDGV_STMT (v
), -1);
448 free_data_refs (RDGV_DATAREFS (v
));
456 /* Build the Reduced Dependence Graph (RDG) with one vertex per
457 statement of the loop nest LOOP_NEST, and one edge per data dependence or
458 scalar dependence. */
460 static struct graph
*
461 build_rdg (vec
<loop_p
> loop_nest
, control_dependences
*cd
)
464 vec
<data_reference_p
> datarefs
;
466 /* Create the RDG vertices from the stmts of the loop nest. */
467 auto_vec
<gimple
, 10> stmts
;
468 stmts_from_loop (loop_nest
[0], &stmts
);
469 rdg
= new_graph (stmts
.length ());
470 datarefs
.create (10);
471 if (!create_rdg_vertices (rdg
, stmts
, loop_nest
[0], &datarefs
))
479 create_rdg_flow_edges (rdg
);
481 create_rdg_cd_edges (rdg
, cd
);
490 enum partition_kind
{
491 PKIND_NORMAL
, PKIND_MEMSET
, PKIND_MEMCPY
494 typedef struct partition_s
499 enum partition_kind kind
;
500 /* data-references a kind != PKIND_NORMAL partition is about. */
501 data_reference_p main_dr
;
502 data_reference_p secondary_dr
;
508 /* Allocate and initialize a partition from BITMAP. */
511 partition_alloc (bitmap stmts
, bitmap loops
)
513 partition_t partition
= XCNEW (struct partition_s
);
514 partition
->stmts
= stmts
? stmts
: BITMAP_ALLOC (NULL
);
515 partition
->loops
= loops
? loops
: BITMAP_ALLOC (NULL
);
516 partition
->reduction_p
= false;
517 partition
->kind
= PKIND_NORMAL
;
521 /* Free PARTITION. */
524 partition_free (partition_t partition
)
526 BITMAP_FREE (partition
->stmts
);
527 BITMAP_FREE (partition
->loops
);
531 /* Returns true if the partition can be generated as a builtin. */
534 partition_builtin_p (partition_t partition
)
536 return partition
->kind
!= PKIND_NORMAL
;
539 /* Returns true if the partition contains a reduction. */
542 partition_reduction_p (partition_t partition
)
544 return partition
->reduction_p
;
547 /* Merge PARTITION into the partition DEST. */
550 partition_merge_into (partition_t dest
, partition_t partition
)
552 dest
->kind
= PKIND_NORMAL
;
553 bitmap_ior_into (dest
->stmts
, partition
->stmts
);
554 if (partition_reduction_p (partition
))
555 dest
->reduction_p
= true;
559 /* Returns true when DEF is an SSA_NAME defined in LOOP and used after
563 ssa_name_has_uses_outside_loop_p (tree def
, loop_p loop
)
565 imm_use_iterator imm_iter
;
568 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
570 gimple use_stmt
= USE_STMT (use_p
);
571 if (!is_gimple_debug (use_stmt
)
572 && loop
!= loop_containing_stmt (use_stmt
))
579 /* Returns true when STMT defines a scalar variable used after the
583 stmt_has_scalar_dependences_outside_loop (loop_p loop
, gimple stmt
)
588 if (gimple_code (stmt
) == GIMPLE_PHI
)
589 return ssa_name_has_uses_outside_loop_p (gimple_phi_result (stmt
), loop
);
591 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
592 if (ssa_name_has_uses_outside_loop_p (DEF_FROM_PTR (def_p
), loop
))
598 /* Return a copy of LOOP placed before LOOP. */
601 copy_loop_before (struct loop
*loop
)
604 edge preheader
= loop_preheader_edge (loop
);
606 initialize_original_copy_tables ();
607 res
= slpeel_tree_duplicate_loop_to_edge_cfg (loop
, NULL
, preheader
);
608 gcc_assert (res
!= NULL
);
609 free_original_copy_tables ();
610 delete_update_ssa ();
615 /* Creates an empty basic block after LOOP. */
618 create_bb_after_loop (struct loop
*loop
)
620 edge exit
= single_exit (loop
);
628 /* Generate code for PARTITION from the code in LOOP. The loop is
629 copied when COPY_P is true. All the statements not flagged in the
630 PARTITION bitmap are removed from the loop or from its copy. The
631 statements are indexed in sequence inside a basic block, and the
632 basic blocks of a loop are taken in dom order. */
635 generate_loops_for_partition (struct loop
*loop
, partition_t partition
,
643 loop
= copy_loop_before (loop
);
644 gcc_assert (loop
!= NULL
);
645 create_preheader (loop
, CP_SIMPLE_PREHEADERS
);
646 create_bb_after_loop (loop
);
649 /* Remove stmts not in the PARTITION bitmap. */
650 bbs
= get_loop_body_in_dom_order (loop
);
652 if (MAY_HAVE_DEBUG_STMTS
)
653 for (i
= 0; i
< loop
->num_nodes
; i
++)
655 basic_block bb
= bbs
[i
];
657 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 reset_debug_uses (phi
);
666 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
668 gimple stmt
= gsi_stmt (bsi
);
669 if (gimple_code (stmt
) != GIMPLE_LABEL
670 && !is_gimple_debug (stmt
)
671 && !bitmap_bit_p (partition
->stmts
, gimple_uid (stmt
)))
672 reset_debug_uses (stmt
);
676 for (i
= 0; i
< loop
->num_nodes
; i
++)
678 basic_block bb
= bbs
[i
];
680 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);)
682 gphi
*phi
= bsi
.phi ();
683 if (!virtual_operand_p (gimple_phi_result (phi
))
684 && !bitmap_bit_p (partition
->stmts
, gimple_uid (phi
)))
685 remove_phi_node (&bsi
, true);
690 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);)
692 gimple stmt
= gsi_stmt (bsi
);
693 if (gimple_code (stmt
) != GIMPLE_LABEL
694 && !is_gimple_debug (stmt
)
695 && !bitmap_bit_p (partition
->stmts
, gimple_uid (stmt
)))
697 /* Choose an arbitrary path through the empty CFG part
698 that this unnecessary control stmt controls. */
699 if (gcond
*cond_stmt
= dyn_cast
<gcond
*> (stmt
))
701 gimple_cond_make_false (cond_stmt
);
704 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
706 gswitch
*switch_stmt
= as_a
<gswitch
*> (stmt
);
707 gimple_switch_set_index
708 (switch_stmt
, CASE_LOW (gimple_switch_label (switch_stmt
, 1)));
713 unlink_stmt_vdef (stmt
);
714 gsi_remove (&bsi
, true);
726 /* Build the size argument for a memory operation call. */
729 build_size_arg_loc (location_t loc
, data_reference_p dr
, tree nb_iter
,
732 tree size
= fold_convert_loc (loc
, sizetype
, nb_iter
);
734 size
= size_binop (PLUS_EXPR
, size
, size_one_node
);
735 size
= fold_build2_loc (loc
, MULT_EXPR
, sizetype
, size
,
736 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
))));
737 size
= fold_convert_loc (loc
, size_type_node
, size
);
741 /* Build an address argument for a memory operation call. */
744 build_addr_arg_loc (location_t loc
, data_reference_p dr
, tree nb_bytes
)
748 addr_base
= size_binop_loc (loc
, PLUS_EXPR
, DR_OFFSET (dr
), DR_INIT (dr
));
749 addr_base
= fold_convert_loc (loc
, sizetype
, addr_base
);
751 /* Test for a negative stride, iterating over every element. */
752 if (tree_int_cst_sgn (DR_STEP (dr
)) == -1)
754 addr_base
= size_binop_loc (loc
, MINUS_EXPR
, addr_base
,
755 fold_convert_loc (loc
, sizetype
, nb_bytes
));
756 addr_base
= size_binop_loc (loc
, PLUS_EXPR
, addr_base
,
757 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
))));
760 return fold_build_pointer_plus_loc (loc
, DR_BASE_ADDRESS (dr
), addr_base
);
763 /* If VAL memory representation contains the same value in all bytes,
764 return that value, otherwise return -1.
765 E.g. for 0x24242424 return 0x24, for IEEE double
766 747708026454360457216.0 return 0x44, etc. */
769 const_with_all_bytes_same (tree val
)
771 unsigned char buf
[64];
774 if (integer_zerop (val
)
776 || (TREE_CODE (val
) == CONSTRUCTOR
777 && !TREE_CLOBBER_P (val
)
778 && CONSTRUCTOR_NELTS (val
) == 0))
781 if (CHAR_BIT
!= 8 || BITS_PER_UNIT
!= 8)
784 len
= native_encode_expr (val
, buf
, sizeof (buf
));
787 for (i
= 1; i
< len
; i
++)
788 if (buf
[i
] != buf
[0])
793 /* Generate a call to memset for PARTITION in LOOP. */
796 generate_memset_builtin (struct loop
*loop
, partition_t partition
)
798 gimple_stmt_iterator gsi
;
799 gimple stmt
, fn_call
;
800 tree mem
, fn
, nb_bytes
;
804 stmt
= DR_STMT (partition
->main_dr
);
805 loc
= gimple_location (stmt
);
807 /* The new statements will be placed before LOOP. */
808 gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
810 nb_bytes
= build_size_arg_loc (loc
, partition
->main_dr
, partition
->niter
,
811 partition
->plus_one
);
812 nb_bytes
= force_gimple_operand_gsi (&gsi
, nb_bytes
, true, NULL_TREE
,
813 false, GSI_CONTINUE_LINKING
);
814 mem
= build_addr_arg_loc (loc
, partition
->main_dr
, nb_bytes
);
815 mem
= force_gimple_operand_gsi (&gsi
, mem
, true, NULL_TREE
,
816 false, GSI_CONTINUE_LINKING
);
818 /* This exactly matches the pattern recognition in classify_partition. */
819 val
= gimple_assign_rhs1 (stmt
);
820 /* Handle constants like 0x15151515 and similarly
821 floating point constants etc. where all bytes are the same. */
822 int bytev
= const_with_all_bytes_same (val
);
824 val
= build_int_cst (integer_type_node
, bytev
);
825 else if (TREE_CODE (val
) == INTEGER_CST
)
826 val
= fold_convert (integer_type_node
, val
);
827 else if (!useless_type_conversion_p (integer_type_node
, TREE_TYPE (val
)))
829 tree tem
= make_ssa_name (integer_type_node
);
830 gimple cstmt
= gimple_build_assign (tem
, NOP_EXPR
, val
);
831 gsi_insert_after (&gsi
, cstmt
, GSI_CONTINUE_LINKING
);
835 fn
= build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET
));
836 fn_call
= gimple_build_call (fn
, 3, mem
, val
, nb_bytes
);
837 gsi_insert_after (&gsi
, fn_call
, GSI_CONTINUE_LINKING
);
839 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
841 fprintf (dump_file
, "generated memset");
843 fprintf (dump_file
, " zero\n");
845 fprintf (dump_file
, "\n");
849 /* Generate a call to memcpy for PARTITION in LOOP. */
852 generate_memcpy_builtin (struct loop
*loop
, partition_t partition
)
854 gimple_stmt_iterator gsi
;
855 gimple stmt
, fn_call
;
856 tree dest
, src
, fn
, nb_bytes
;
858 enum built_in_function kind
;
860 stmt
= DR_STMT (partition
->main_dr
);
861 loc
= gimple_location (stmt
);
863 /* The new statements will be placed before LOOP. */
864 gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
866 nb_bytes
= build_size_arg_loc (loc
, partition
->main_dr
, partition
->niter
,
867 partition
->plus_one
);
868 nb_bytes
= force_gimple_operand_gsi (&gsi
, nb_bytes
, true, NULL_TREE
,
869 false, GSI_CONTINUE_LINKING
);
870 dest
= build_addr_arg_loc (loc
, partition
->main_dr
, nb_bytes
);
871 src
= build_addr_arg_loc (loc
, partition
->secondary_dr
, nb_bytes
);
872 if (ptr_derefs_may_alias_p (dest
, src
))
873 kind
= BUILT_IN_MEMMOVE
;
875 kind
= BUILT_IN_MEMCPY
;
877 dest
= force_gimple_operand_gsi (&gsi
, dest
, true, NULL_TREE
,
878 false, GSI_CONTINUE_LINKING
);
879 src
= force_gimple_operand_gsi (&gsi
, src
, true, NULL_TREE
,
880 false, GSI_CONTINUE_LINKING
);
881 fn
= build_fold_addr_expr (builtin_decl_implicit (kind
));
882 fn_call
= gimple_build_call (fn
, 3, dest
, src
, nb_bytes
);
883 gsi_insert_after (&gsi
, fn_call
, GSI_CONTINUE_LINKING
);
885 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
887 if (kind
== BUILT_IN_MEMCPY
)
888 fprintf (dump_file
, "generated memcpy\n");
890 fprintf (dump_file
, "generated memmove\n");
894 /* Remove and destroy the loop LOOP. */
897 destroy_loop (struct loop
*loop
)
899 unsigned nbbs
= loop
->num_nodes
;
900 edge exit
= single_exit (loop
);
901 basic_block src
= loop_preheader_edge (loop
)->src
, dest
= exit
->dest
;
905 bbs
= get_loop_body_in_dom_order (loop
);
907 redirect_edge_pred (exit
, src
);
908 exit
->flags
&= ~(EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
909 exit
->flags
|= EDGE_FALLTHRU
;
910 cancel_loop_tree (loop
);
911 rescan_loop_exit (exit
, false, true);
913 for (i
= 0; i
< nbbs
; i
++)
915 /* We have made sure to not leave any dangling uses of SSA
916 names defined in the loop. With the exception of virtuals.
917 Make sure we replace all uses of virtual defs that will remain
918 outside of the loop with the bare symbol as delete_basic_block
919 will release them. */
920 for (gphi_iterator gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
);
923 gphi
*phi
= gsi
.phi ();
924 if (virtual_operand_p (gimple_phi_result (phi
)))
925 mark_virtual_phi_result_for_renaming (phi
);
927 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]); !gsi_end_p (gsi
);
930 gimple stmt
= gsi_stmt (gsi
);
931 tree vdef
= gimple_vdef (stmt
);
932 if (vdef
&& TREE_CODE (vdef
) == SSA_NAME
)
933 mark_virtual_operand_for_renaming (vdef
);
935 delete_basic_block (bbs
[i
]);
939 set_immediate_dominator (CDI_DOMINATORS
, dest
,
940 recompute_dominator (CDI_DOMINATORS
, dest
));
943 /* Generates code for PARTITION. */
946 generate_code_for_partition (struct loop
*loop
,
947 partition_t partition
, bool copy_p
)
949 switch (partition
->kind
)
952 /* Reductions all have to be in the last partition. */
953 gcc_assert (!partition_reduction_p (partition
)
955 generate_loops_for_partition (loop
, partition
, copy_p
);
959 generate_memset_builtin (loop
, partition
);
963 generate_memcpy_builtin (loop
, partition
);
970 /* Common tail for partitions we turn into a call. If this was the last
971 partition for which we generate code, we have to destroy the loop. */
977 /* Returns a partition with all the statements needed for computing
978 the vertex V of the RDG, also including the loop exit conditions. */
981 build_rdg_partition_for_vertex (struct graph
*rdg
, int v
)
983 partition_t partition
= partition_alloc (NULL
, NULL
);
984 auto_vec
<int, 3> nodes
;
988 graphds_dfs (rdg
, &v
, 1, &nodes
, false, NULL
);
990 FOR_EACH_VEC_ELT (nodes
, i
, x
)
992 bitmap_set_bit (partition
->stmts
, x
);
993 bitmap_set_bit (partition
->loops
,
994 loop_containing_stmt (RDG_STMT (rdg
, x
))->num
);
1000 /* Classifies the builtin kind we can generate for PARTITION of RDG and LOOP.
1001 For the moment we detect only the memset zero pattern. */
1004 classify_partition (loop_p loop
, struct graph
*rdg
, partition_t partition
)
1009 data_reference_p single_load
, single_store
;
1010 bool volatiles_p
= false;
1011 bool plus_one
= false;
1013 partition
->kind
= PKIND_NORMAL
;
1014 partition
->main_dr
= NULL
;
1015 partition
->secondary_dr
= NULL
;
1016 partition
->niter
= NULL_TREE
;
1017 partition
->plus_one
= false;
1019 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, bi
)
1021 gimple stmt
= RDG_STMT (rdg
, i
);
1023 if (gimple_has_volatile_ops (stmt
))
1026 /* If the stmt has uses outside of the loop mark it as reduction. */
1027 if (stmt_has_scalar_dependences_outside_loop (loop
, stmt
))
1029 partition
->reduction_p
= true;
1034 /* Perform general partition disqualification for builtins. */
1036 || !flag_tree_loop_distribute_patterns
)
1039 /* Detect memset and memcpy. */
1041 single_store
= NULL
;
1042 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, bi
)
1044 gimple stmt
= RDG_STMT (rdg
, i
);
1045 data_reference_p dr
;
1048 if (gimple_code (stmt
) == GIMPLE_PHI
)
1051 /* Any scalar stmts are ok. */
1052 if (!gimple_vuse (stmt
))
1055 /* Otherwise just regular loads/stores. */
1056 if (!gimple_assign_single_p (stmt
))
1059 /* But exactly one store and/or load. */
1060 for (j
= 0; RDG_DATAREFS (rdg
, i
).iterate (j
, &dr
); ++j
)
1062 if (DR_IS_READ (dr
))
1064 if (single_load
!= NULL
)
1070 if (single_store
!= NULL
)
1080 nb_iter
= number_of_latch_executions (loop
);
1081 if (!nb_iter
|| nb_iter
== chrec_dont_know
)
1083 if (dominated_by_p (CDI_DOMINATORS
, single_exit (loop
)->src
,
1084 gimple_bb (DR_STMT (single_store
))))
1087 if (single_store
&& !single_load
)
1089 gimple stmt
= DR_STMT (single_store
);
1090 tree rhs
= gimple_assign_rhs1 (stmt
);
1091 if (const_with_all_bytes_same (rhs
) == -1
1092 && (!INTEGRAL_TYPE_P (TREE_TYPE (rhs
))
1093 || (TYPE_MODE (TREE_TYPE (rhs
))
1094 != TYPE_MODE (unsigned_char_type_node
))))
1096 if (TREE_CODE (rhs
) == SSA_NAME
1097 && !SSA_NAME_IS_DEFAULT_DEF (rhs
)
1098 && flow_bb_inside_loop_p (loop
, gimple_bb (SSA_NAME_DEF_STMT (rhs
))))
1100 if (!adjacent_dr_p (single_store
)
1101 || !dominated_by_p (CDI_DOMINATORS
,
1102 loop
->latch
, gimple_bb (stmt
)))
1104 partition
->kind
= PKIND_MEMSET
;
1105 partition
->main_dr
= single_store
;
1106 partition
->niter
= nb_iter
;
1107 partition
->plus_one
= plus_one
;
1109 else if (single_store
&& single_load
)
1111 gimple store
= DR_STMT (single_store
);
1112 gimple load
= DR_STMT (single_load
);
1113 /* Direct aggregate copy or via an SSA name temporary. */
1115 && gimple_assign_lhs (load
) != gimple_assign_rhs1 (store
))
1117 if (!adjacent_dr_p (single_store
)
1118 || !adjacent_dr_p (single_load
)
1119 || !operand_equal_p (DR_STEP (single_store
),
1120 DR_STEP (single_load
), 0)
1121 || !dominated_by_p (CDI_DOMINATORS
,
1122 loop
->latch
, gimple_bb (store
)))
1124 /* Now check that if there is a dependence this dependence is
1125 of a suitable form for memmove. */
1126 vec
<loop_p
> loops
= vNULL
;
1128 loops
.safe_push (loop
);
1129 ddr
= initialize_data_dependence_relation (single_load
, single_store
,
1131 compute_affine_dependence (ddr
, loop
);
1132 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
1134 free_dependence_relation (ddr
);
1138 if (DDR_ARE_DEPENDENT (ddr
) != chrec_known
)
1140 if (DDR_NUM_DIST_VECTS (ddr
) == 0)
1142 free_dependence_relation (ddr
);
1146 lambda_vector dist_v
;
1147 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
1149 int dist
= dist_v
[index_in_loop_nest (loop
->num
,
1150 DDR_LOOP_NEST (ddr
))];
1151 if (dist
> 0 && !DDR_REVERSED_P (ddr
))
1153 free_dependence_relation (ddr
);
1159 free_dependence_relation (ddr
);
1161 partition
->kind
= PKIND_MEMCPY
;
1162 partition
->main_dr
= single_store
;
1163 partition
->secondary_dr
= single_load
;
1164 partition
->niter
= nb_iter
;
1165 partition
->plus_one
= plus_one
;
1169 /* For a data reference REF, return the declaration of its base
1170 address or NULL_TREE if the base is not determined. */
1173 ref_base_address (data_reference_p dr
)
1175 tree base_address
= DR_BASE_ADDRESS (dr
);
1177 && TREE_CODE (base_address
) == ADDR_EXPR
)
1178 return TREE_OPERAND (base_address
, 0);
1180 return base_address
;
1183 /* Returns true when PARTITION1 and PARTITION2 have similar memory
1187 similar_memory_accesses (struct graph
*rdg
, partition_t partition1
,
1188 partition_t partition2
)
1190 unsigned i
, j
, k
, l
;
1191 bitmap_iterator bi
, bj
;
1192 data_reference_p ref1
, ref2
;
1194 /* First check whether in the intersection of the two partitions are
1195 any loads or stores. Common loads are the situation that happens
1197 EXECUTE_IF_AND_IN_BITMAP (partition1
->stmts
, partition2
->stmts
, 0, i
, bi
)
1198 if (RDG_MEM_WRITE_STMT (rdg
, i
)
1199 || RDG_MEM_READS_STMT (rdg
, i
))
1202 /* Then check all data-references against each other. */
1203 EXECUTE_IF_SET_IN_BITMAP (partition1
->stmts
, 0, i
, bi
)
1204 if (RDG_MEM_WRITE_STMT (rdg
, i
)
1205 || RDG_MEM_READS_STMT (rdg
, i
))
1206 EXECUTE_IF_SET_IN_BITMAP (partition2
->stmts
, 0, j
, bj
)
1207 if (RDG_MEM_WRITE_STMT (rdg
, j
)
1208 || RDG_MEM_READS_STMT (rdg
, j
))
1210 FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg
, i
), k
, ref1
)
1212 tree base1
= ref_base_address (ref1
);
1214 FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg
, j
), l
, ref2
)
1215 if (base1
== ref_base_address (ref2
))
1223 /* Aggregate several components into a useful partition that is
1224 registered in the PARTITIONS vector. Partitions will be
1225 distributed in different loops. */
1228 rdg_build_partitions (struct graph
*rdg
,
1229 vec
<gimple
> starting_stmts
,
1230 vec
<partition_t
> *partitions
)
1232 bitmap processed
= BITMAP_ALLOC (NULL
);
1236 FOR_EACH_VEC_ELT (starting_stmts
, i
, stmt
)
1238 int v
= rdg_vertex_for_stmt (rdg
, stmt
);
1240 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1242 "ldist asked to generate code for vertex %d\n", v
);
1244 /* If the vertex is already contained in another partition so
1245 is the partition rooted at it. */
1246 if (bitmap_bit_p (processed
, v
))
1249 partition_t partition
= build_rdg_partition_for_vertex (rdg
, v
);
1250 bitmap_ior_into (processed
, partition
->stmts
);
1252 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1254 fprintf (dump_file
, "ldist useful partition:\n");
1255 dump_bitmap (dump_file
, partition
->stmts
);
1258 partitions
->safe_push (partition
);
1261 /* All vertices should have been assigned to at least one partition now,
1262 other than vertices belonging to dead code. */
1264 BITMAP_FREE (processed
);
1267 /* Dump to FILE the PARTITIONS. */
1270 dump_rdg_partitions (FILE *file
, vec
<partition_t
> partitions
)
1273 partition_t partition
;
1275 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1276 debug_bitmap_file (file
, partition
->stmts
);
1279 /* Debug PARTITIONS. */
1280 extern void debug_rdg_partitions (vec
<partition_t
> );
1283 debug_rdg_partitions (vec
<partition_t
> partitions
)
1285 dump_rdg_partitions (stderr
, partitions
);
1288 /* Returns the number of read and write operations in the RDG. */
1291 number_of_rw_in_rdg (struct graph
*rdg
)
1295 for (i
= 0; i
< rdg
->n_vertices
; i
++)
1297 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1300 if (RDG_MEM_READS_STMT (rdg
, i
))
1307 /* Returns the number of read and write operations in a PARTITION of
1311 number_of_rw_in_partition (struct graph
*rdg
, partition_t partition
)
1317 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, ii
)
1319 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1322 if (RDG_MEM_READS_STMT (rdg
, i
))
1329 /* Returns true when one of the PARTITIONS contains all the read or
1330 write operations of RDG. */
1333 partition_contains_all_rw (struct graph
*rdg
,
1334 vec
<partition_t
> partitions
)
1337 partition_t partition
;
1338 int nrw
= number_of_rw_in_rdg (rdg
);
1340 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1341 if (nrw
== number_of_rw_in_partition (rdg
, partition
))
1347 /* Compute partition dependence created by the data references in DRS1
1348 and DRS2 and modify and return DIR according to that. */
1351 pg_add_dependence_edges (struct graph
*rdg
, vec
<loop_p
> loops
, int dir
,
1352 vec
<data_reference_p
> drs1
,
1353 vec
<data_reference_p
> drs2
)
1355 data_reference_p dr1
, dr2
;
1357 /* dependence direction - 0 is no dependence, -1 is back,
1358 1 is forth, 2 is both (we can stop then, merging will occur). */
1359 for (int ii
= 0; drs1
.iterate (ii
, &dr1
); ++ii
)
1360 for (int jj
= 0; drs2
.iterate (jj
, &dr2
); ++jj
)
1362 data_reference_p saved_dr1
= dr1
;
1365 /* Re-shuffle data-refs to be in dominator order. */
1366 if (rdg_vertex_for_stmt (rdg
, DR_STMT (dr1
))
1367 > rdg_vertex_for_stmt (rdg
, DR_STMT (dr2
)))
1369 data_reference_p tem
= dr1
;
1372 this_dir
= -this_dir
;
1374 ddr
= initialize_data_dependence_relation (dr1
, dr2
, loops
);
1375 compute_affine_dependence (ddr
, loops
[0]);
1376 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
1378 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1380 if (DDR_REVERSED_P (ddr
))
1382 data_reference_p tem
= dr1
;
1385 this_dir
= -this_dir
;
1387 /* Known dependences can still be unordered througout the
1388 iteration space, see gcc.dg/tree-ssa/ldist-16.c. */
1389 if (DDR_NUM_DIST_VECTS (ddr
) != 1)
1391 /* If the overlap is exact preserve stmt order. */
1392 else if (lambda_vector_zerop (DDR_DIST_VECT (ddr
, 0), 1))
1396 /* Else as the distance vector is lexicographic positive
1397 swap the dependence direction. */
1398 this_dir
= -this_dir
;
1403 free_dependence_relation (ddr
);
1406 else if (dir
!= this_dir
)
1408 /* Shuffle "back" dr1. */
1414 /* Compare postorder number of the partition graph vertices V1 and V2. */
1417 pgcmp (const void *v1_
, const void *v2_
)
1419 const vertex
*v1
= (const vertex
*)v1_
;
1420 const vertex
*v2
= (const vertex
*)v2_
;
1421 return v2
->post
- v1
->post
;
1424 /* Distributes the code from LOOP in such a way that producer
1425 statements are placed before consumer statements. Tries to separate
1426 only the statements from STMTS into separate loops.
1427 Returns the number of distributed loops. */
1430 distribute_loop (struct loop
*loop
, vec
<gimple
> stmts
,
1431 control_dependences
*cd
, int *nb_calls
)
1434 partition_t partition
;
1441 auto_vec
<loop_p
, 3> loop_nest
;
1442 if (!find_loop_nest (loop
, &loop_nest
))
1445 rdg
= build_rdg (loop_nest
, cd
);
1448 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1450 "Loop %d not distributed: failed to build the RDG.\n",
1456 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1457 dump_rdg (dump_file
, rdg
);
1459 auto_vec
<partition_t
, 3> partitions
;
1460 rdg_build_partitions (rdg
, stmts
, &partitions
);
1462 any_builtin
= false;
1463 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1465 classify_partition (loop
, rdg
, partition
);
1466 any_builtin
|= partition_builtin_p (partition
);
1469 /* If we are only distributing patterns but did not detect any,
1471 if (!flag_tree_loop_distribution
1478 /* If we are only distributing patterns fuse all partitions that
1479 were not classified as builtins. This also avoids chopping
1480 a loop into pieces, separated by builtin calls. That is, we
1481 only want no or a single loop body remaining. */
1483 if (!flag_tree_loop_distribution
)
1485 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
1486 if (!partition_builtin_p (into
))
1488 for (++i
; partitions
.iterate (i
, &partition
); ++i
)
1489 if (!partition_builtin_p (partition
))
1491 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1493 fprintf (dump_file
, "fusing non-builtin partitions\n");
1494 dump_bitmap (dump_file
, into
->stmts
);
1495 dump_bitmap (dump_file
, partition
->stmts
);
1497 partition_merge_into (into
, partition
);
1498 partitions
.unordered_remove (i
);
1499 partition_free (partition
);
1504 /* Due to limitations in the transform phase we have to fuse all
1505 reduction partitions into the last partition so the existing
1506 loop will contain all loop-closed PHI nodes. */
1507 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
1508 if (partition_reduction_p (into
))
1510 for (i
= i
+ 1; partitions
.iterate (i
, &partition
); ++i
)
1511 if (partition_reduction_p (partition
))
1513 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1515 fprintf (dump_file
, "fusing partitions\n");
1516 dump_bitmap (dump_file
, into
->stmts
);
1517 dump_bitmap (dump_file
, partition
->stmts
);
1518 fprintf (dump_file
, "because they have reductions\n");
1520 partition_merge_into (into
, partition
);
1521 partitions
.unordered_remove (i
);
1522 partition_free (partition
);
1526 /* Apply our simple cost model - fuse partitions with similar
1528 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
1530 if (partition_builtin_p (into
))
1533 partitions
.iterate (j
, &partition
); ++j
)
1535 if (!partition_builtin_p (partition
)
1536 && similar_memory_accesses (rdg
, into
, partition
))
1538 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1540 fprintf (dump_file
, "fusing partitions\n");
1541 dump_bitmap (dump_file
, into
->stmts
);
1542 dump_bitmap (dump_file
, partition
->stmts
);
1543 fprintf (dump_file
, "because they have similar "
1544 "memory accesses\n");
1546 partition_merge_into (into
, partition
);
1547 partitions
.unordered_remove (j
);
1548 partition_free (partition
);
1554 /* Build the partition dependency graph. */
1555 if (partitions
.length () > 1)
1557 pg
= new_graph (partitions
.length ());
1559 partition_t partition
;
1560 vec
<data_reference_p
> writes
;
1561 vec
<data_reference_p
> reads
;
1563 #define PGDATA(i) ((pgdata *)(pg->vertices[i].data))
1564 for (i
= 0; partitions
.iterate (i
, &partition
); ++i
)
1566 vertex
*v
= &pg
->vertices
[i
];
1567 pgdata
*data
= new pgdata
;
1568 data_reference_p dr
;
1569 /* FIXME - leaks. */
1573 data
->partition
= partition
;
1574 data
->reads
= vNULL
;
1575 data
->writes
= vNULL
;
1576 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, j
, bi
)
1577 for (int k
= 0; RDG_DATAREFS (rdg
, j
).iterate (k
, &dr
); ++k
)
1578 if (DR_IS_READ (dr
))
1579 data
->reads
.safe_push (dr
);
1581 data
->writes
.safe_push (dr
);
1583 partition_t partition1
, partition2
;
1584 for (i
= 0; partitions
.iterate (i
, &partition1
); ++i
)
1585 for (int j
= i
+ 1; partitions
.iterate (j
, &partition2
); ++j
)
1587 /* dependence direction - 0 is no dependence, -1 is back,
1588 1 is forth, 2 is both (we can stop then, merging will occur). */
1590 dir
= pg_add_dependence_edges (rdg
, loop_nest
, dir
,
1594 dir
= pg_add_dependence_edges (rdg
, loop_nest
, dir
,
1598 dir
= pg_add_dependence_edges (rdg
, loop_nest
, dir
,
1601 if (dir
== 1 || dir
== 2)
1602 add_edge (pg
, i
, j
);
1603 if (dir
== -1 || dir
== 2)
1604 add_edge (pg
, j
, i
);
1607 /* Add edges to the reduction partition (if any) to force it last. */
1609 for (j
= 0; partitions
.iterate (j
, &partition
); ++j
)
1610 if (partition_reduction_p (partition
))
1612 if (j
< partitions
.length ())
1614 for (unsigned i
= 0; partitions
.iterate (i
, &partition
); ++i
)
1616 add_edge (pg
, i
, j
);
1619 /* Compute partitions we cannot separate and fuse them. */
1620 num_sccs
= graphds_scc (pg
, NULL
);
1621 for (i
= 0; i
< num_sccs
; ++i
)
1625 for (j
= 0; partitions
.iterate (j
, &first
); ++j
)
1626 if (pg
->vertices
[j
].component
== i
)
1628 for (j
= j
+ 1; partitions
.iterate (j
, &partition
); ++j
)
1629 if (pg
->vertices
[j
].component
== i
)
1631 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1633 fprintf (dump_file
, "fusing partitions\n");
1634 dump_bitmap (dump_file
, first
->stmts
);
1635 dump_bitmap (dump_file
, partition
->stmts
);
1636 fprintf (dump_file
, "because they are in the same "
1637 "dependence SCC\n");
1639 partition_merge_into (first
, partition
);
1640 partitions
[j
] = NULL
;
1641 partition_free (partition
);
1642 PGDATA (j
)->partition
= NULL
;
1646 /* Now order the remaining nodes in postorder. */
1647 qsort (pg
->vertices
, pg
->n_vertices
, sizeof (vertex
), pgcmp
);
1648 partitions
.truncate (0);
1649 for (i
= 0; i
< pg
->n_vertices
; ++i
)
1651 pgdata
*data
= PGDATA (i
);
1652 if (data
->partition
)
1653 partitions
.safe_push (data
->partition
);
1654 data
->reads
.release ();
1655 data
->writes
.release ();
1658 gcc_assert (partitions
.length () == (unsigned)num_sccs
);
1662 nbp
= partitions
.length ();
1664 || (nbp
== 1 && !partition_builtin_p (partitions
[0]))
1665 || (nbp
> 1 && partition_contains_all_rw (rdg
, partitions
)))
1671 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1672 dump_rdg_partitions (dump_file
, partitions
);
1674 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1676 if (partition_builtin_p (partition
))
1678 generate_code_for_partition (loop
, partition
, i
< nbp
- 1);
1683 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1684 partition_free (partition
);
1687 return nbp
- *nb_calls
;
1690 /* Distribute all loops in the current function. */
1694 const pass_data pass_data_loop_distribution
=
1696 GIMPLE_PASS
, /* type */
1698 OPTGROUP_LOOP
, /* optinfo_flags */
1699 TV_TREE_LOOP_DISTRIBUTION
, /* tv_id */
1700 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1701 0, /* properties_provided */
1702 0, /* properties_destroyed */
1703 0, /* todo_flags_start */
1704 0, /* todo_flags_finish */
1707 class pass_loop_distribution
: public gimple_opt_pass
1710 pass_loop_distribution (gcc::context
*ctxt
)
1711 : gimple_opt_pass (pass_data_loop_distribution
, ctxt
)
1714 /* opt_pass methods: */
1715 virtual bool gate (function
*)
1717 return flag_tree_loop_distribution
1718 || flag_tree_loop_distribute_patterns
;
1721 virtual unsigned int execute (function
*);
1723 }; // class pass_loop_distribution
1726 pass_loop_distribution::execute (function
*fun
)
1729 bool changed
= false;
1731 control_dependences
*cd
= NULL
;
1733 FOR_ALL_BB_FN (bb
, fun
)
1735 gimple_stmt_iterator gsi
;
1736 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1737 gimple_set_uid (gsi_stmt (gsi
), -1);
1738 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1739 gimple_set_uid (gsi_stmt (gsi
), -1);
1742 /* We can at the moment only distribute non-nested loops, thus restrict
1743 walking to innermost loops. */
1744 FOR_EACH_LOOP (loop
, LI_ONLY_INNERMOST
)
1746 auto_vec
<gimple
> work_list
;
1748 int num
= loop
->num
;
1751 /* If the loop doesn't have a single exit we will fail anyway,
1752 so do that early. */
1753 if (!single_exit (loop
))
1756 /* Only optimize hot loops. */
1757 if (!optimize_loop_for_speed_p (loop
))
1760 /* Initialize the worklist with stmts we seed the partitions with. */
1761 bbs
= get_loop_body_in_dom_order (loop
);
1762 for (i
= 0; i
< loop
->num_nodes
; ++i
)
1764 for (gphi_iterator gsi
= gsi_start_phis (bbs
[i
]);
1768 gphi
*phi
= gsi
.phi ();
1769 if (virtual_operand_p (gimple_phi_result (phi
)))
1771 /* Distribute stmts which have defs that are used outside of
1773 if (!stmt_has_scalar_dependences_outside_loop (loop
, phi
))
1775 work_list
.safe_push (phi
);
1777 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]);
1781 gimple stmt
= gsi_stmt (gsi
);
1783 /* If there is a stmt with side-effects bail out - we
1784 cannot and should not distribute this loop. */
1785 if (gimple_has_side_effects (stmt
))
1787 work_list
.truncate (0);
1791 /* Distribute stmts which have defs that are used outside of
1793 if (stmt_has_scalar_dependences_outside_loop (loop
, stmt
))
1795 /* Otherwise only distribute stores for now. */
1796 else if (!gimple_vdef (stmt
))
1799 work_list
.safe_push (stmt
);
1805 int nb_generated_loops
= 0;
1806 int nb_generated_calls
= 0;
1807 location_t loc
= find_loop_location (loop
);
1808 if (work_list
.length () > 0)
1812 calculate_dominance_info (CDI_DOMINATORS
);
1813 calculate_dominance_info (CDI_POST_DOMINATORS
);
1814 cd
= new control_dependences (create_edge_list ());
1815 free_dominance_info (CDI_POST_DOMINATORS
);
1817 nb_generated_loops
= distribute_loop (loop
, work_list
, cd
,
1818 &nb_generated_calls
);
1821 if (nb_generated_loops
+ nb_generated_calls
> 0)
1824 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
,
1825 loc
, "Loop %d distributed: split to %d loops "
1826 "and %d library calls.\n",
1827 num
, nb_generated_loops
, nb_generated_calls
);
1829 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1830 fprintf (dump_file
, "Loop %d is the same.\n", num
);
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 #ifdef ENABLE_CHECKING
1846 verify_loop_structure ();
1855 make_pass_loop_distribution (gcc::context
*ctxt
)
1857 return new pass_loop_distribution (ctxt
);