2 Copyright (C) 2006-2013 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"
49 #include "gimple-ssa.h"
51 #include "tree-phinodes.h"
52 #include "ssa-iterators.h"
53 #include "tree-ssanames.h"
54 #include "tree-ssa-loop.h"
55 #include "tree-into-ssa.h"
58 #include "tree-chrec.h"
59 #include "tree-data-ref.h"
60 #include "tree-scalar-evolution.h"
61 #include "tree-pass.h"
62 #include "gimple-pretty-print.h"
63 #include "tree-vectorizer.h"
66 /* A Reduced Dependence Graph (RDG) vertex representing a statement. */
67 typedef struct rdg_vertex
69 /* The statement represented by this vertex. */
72 /* Vector of data-references in this statement. */
73 vec
<data_reference_p
> datarefs
;
75 /* True when the statement contains a write to memory. */
78 /* True when the statement contains a read from memory. */
82 #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
83 #define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs
84 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
85 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
86 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
87 #define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I]))
88 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
89 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
91 /* Data dependence type. */
95 /* Read After Write (RAW). */
98 /* Write After Read (WAR). */
101 /* Write After Write (WAW). */
104 /* Read After Read (RAR). */
107 /* Control dependence (execute conditional on). */
111 /* Dependence information attached to an edge of the RDG. */
113 typedef struct rdg_edge
115 /* Type of the dependence. */
116 enum rdg_dep_type type
;
118 /* Levels of the dependence: the depth of the loops that carry the
122 /* Dependence relation between data dependences, NULL when one of
123 the vertices is a scalar. */
127 #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
128 #define RDGE_LEVEL(E) ((struct rdg_edge *) ((E)->data))->level
129 #define RDGE_RELATION(E) ((struct rdg_edge *) ((E)->data))->relation
131 /* Dump vertex I in RDG to FILE. */
134 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
136 struct vertex
*v
= &(rdg
->vertices
[i
]);
137 struct graph_edge
*e
;
139 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
140 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
141 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
144 for (e
= v
->pred
; e
; e
= e
->pred_next
)
145 fprintf (file
, " %d", e
->src
);
147 fprintf (file
, ") (out:");
150 for (e
= v
->succ
; e
; e
= e
->succ_next
)
151 fprintf (file
, " %d", e
->dest
);
153 fprintf (file
, ")\n");
154 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
155 fprintf (file
, ")\n");
158 /* Call dump_rdg_vertex on stderr. */
161 debug_rdg_vertex (struct graph
*rdg
, int i
)
163 dump_rdg_vertex (stderr
, rdg
, i
);
166 /* Dump the reduced dependence graph RDG to FILE. */
169 dump_rdg (FILE *file
, struct graph
*rdg
)
171 fprintf (file
, "(rdg\n");
172 for (int i
= 0; i
< rdg
->n_vertices
; i
++)
173 dump_rdg_vertex (file
, rdg
, i
);
174 fprintf (file
, ")\n");
177 /* Call dump_rdg on stderr. */
180 debug_rdg (struct graph
*rdg
)
182 dump_rdg (stderr
, rdg
);
186 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
189 pretty_printer buffer
;
190 pp_needs_newline (&buffer
) = false;
191 buffer
.buffer
->stream
= file
;
193 fprintf (file
, "digraph RDG {\n");
195 for (i
= 0; i
< rdg
->n_vertices
; i
++)
197 struct vertex
*v
= &(rdg
->vertices
[i
]);
198 struct graph_edge
*e
;
200 fprintf (file
, "%d [label=\"[%d] ", i
, i
);
201 pp_gimple_stmt_1 (&buffer
, RDGV_STMT (v
), 0, TDF_SLIM
);
203 fprintf (file
, "\"]\n");
205 /* Highlight reads from memory. */
206 if (RDG_MEM_READS_STMT (rdg
, i
))
207 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
209 /* Highlight stores to memory. */
210 if (RDG_MEM_WRITE_STMT (rdg
, i
))
211 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
214 for (e
= v
->succ
; e
; e
= e
->succ_next
)
215 switch (RDGE_TYPE (e
))
218 fprintf (file
, "%d -> %d [label=input] \n", i
, e
->dest
);
222 fprintf (file
, "%d -> %d [label=output] \n", i
, e
->dest
);
226 /* These are the most common dependences: don't print these. */
227 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
231 fprintf (file
, "%d -> %d [label=anti] \n", i
, e
->dest
);
235 fprintf (file
, "%d -> %d [label=control] \n", i
, e
->dest
);
243 fprintf (file
, "}\n\n");
246 /* Display the Reduced Dependence Graph using dotty. */
249 dot_rdg (struct graph
*rdg
)
251 /* When debugging, you may want to enable the following code. */
253 FILE *file
= popen ("dot -Tx11", "w");
256 dot_rdg_1 (file
, rdg
);
258 close (fileno (file
));
261 dot_rdg_1 (stderr
, rdg
);
265 /* Returns the index of STMT in RDG. */
268 rdg_vertex_for_stmt (struct graph
*rdg ATTRIBUTE_UNUSED
, gimple stmt
)
270 int index
= gimple_uid (stmt
);
271 gcc_checking_assert (index
== -1 || RDG_STMT (rdg
, index
) == stmt
);
275 /* Creates an edge in RDG for each distance vector from DDR. The
276 order that we keep track of in the RDG is the order in which
277 statements have to be executed. */
280 create_rdg_edge_for_ddr (struct graph
*rdg
, ddr_p ddr
)
282 struct graph_edge
*e
;
284 data_reference_p dra
= DDR_A (ddr
);
285 data_reference_p drb
= DDR_B (ddr
);
286 unsigned level
= ddr_dependence_level (ddr
);
288 /* For non scalar dependences, when the dependence is REVERSED,
289 statement B has to be executed before statement A. */
291 && !DDR_REVERSED_P (ddr
))
293 data_reference_p tmp
= dra
;
298 va
= rdg_vertex_for_stmt (rdg
, DR_STMT (dra
));
299 vb
= rdg_vertex_for_stmt (rdg
, DR_STMT (drb
));
301 if (va
< 0 || vb
< 0)
304 e
= add_edge (rdg
, va
, vb
);
305 e
->data
= XNEW (struct rdg_edge
);
307 RDGE_LEVEL (e
) = level
;
308 RDGE_RELATION (e
) = ddr
;
310 /* Determines the type of the data dependence. */
311 if (DR_IS_READ (dra
) && DR_IS_READ (drb
))
312 RDGE_TYPE (e
) = input_dd
;
313 else if (DR_IS_WRITE (dra
) && DR_IS_WRITE (drb
))
314 RDGE_TYPE (e
) = output_dd
;
315 else if (DR_IS_WRITE (dra
) && DR_IS_READ (drb
))
316 RDGE_TYPE (e
) = flow_dd
;
317 else if (DR_IS_READ (dra
) && DR_IS_WRITE (drb
))
318 RDGE_TYPE (e
) = anti_dd
;
321 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
322 the index of DEF in RDG. */
325 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
327 use_operand_p imm_use_p
;
328 imm_use_iterator iterator
;
330 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
332 struct graph_edge
*e
;
333 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
338 e
= add_edge (rdg
, idef
, use
);
339 e
->data
= XNEW (struct rdg_edge
);
340 RDGE_TYPE (e
) = flow_dd
;
341 RDGE_RELATION (e
) = NULL
;
345 /* Creates an edge for the control dependences of BB to the vertex V. */
348 create_edge_for_control_dependence (struct graph
*rdg
, basic_block bb
,
349 int v
, control_dependences
*cd
)
353 EXECUTE_IF_SET_IN_BITMAP (cd
->get_edges_dependent_on (bb
->index
),
356 basic_block cond_bb
= cd
->get_edge (edge_n
)->src
;
357 gimple stmt
= last_stmt (cond_bb
);
358 if (stmt
&& is_ctrl_stmt (stmt
))
360 struct graph_edge
*e
;
361 int c
= rdg_vertex_for_stmt (rdg
, stmt
);
365 e
= add_edge (rdg
, c
, v
);
366 e
->data
= XNEW (struct rdg_edge
);
367 RDGE_TYPE (e
) = control_dd
;
368 RDGE_RELATION (e
) = NULL
;
373 /* Creates the edges of the reduced dependence graph RDG. */
376 create_rdg_edges (struct graph
*rdg
, vec
<ddr_p
> ddrs
, control_dependences
*cd
)
379 struct data_dependence_relation
*ddr
;
383 FOR_EACH_VEC_ELT (ddrs
, i
, ddr
)
384 if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
385 create_rdg_edge_for_ddr (rdg
, ddr
);
387 free_dependence_relation (ddr
);
389 for (i
= 0; i
< rdg
->n_vertices
; i
++)
390 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
392 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
395 for (i
= 0; i
< rdg
->n_vertices
; i
++)
397 gimple stmt
= RDG_STMT (rdg
, i
);
398 if (gimple_code (stmt
) == GIMPLE_PHI
)
402 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->preds
)
403 create_edge_for_control_dependence (rdg
, e
->src
, i
, cd
);
406 create_edge_for_control_dependence (rdg
, gimple_bb (stmt
), i
, cd
);
410 /* Build the vertices of the reduced dependence graph RDG. Return false
414 create_rdg_vertices (struct graph
*rdg
, vec
<gimple
> stmts
, loop_p loop
,
415 vec
<data_reference_p
> *datarefs
)
420 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
422 struct vertex
*v
= &(rdg
->vertices
[i
]);
424 /* Record statement to vertex mapping. */
425 gimple_set_uid (stmt
, i
);
427 v
->data
= XNEW (struct rdg_vertex
);
428 RDGV_STMT (v
) = stmt
;
429 RDGV_DATAREFS (v
).create (0);
430 RDGV_HAS_MEM_WRITE (v
) = false;
431 RDGV_HAS_MEM_READS (v
) = false;
432 if (gimple_code (stmt
) == GIMPLE_PHI
)
435 unsigned drp
= datarefs
->length ();
436 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
438 for (unsigned j
= drp
; j
< datarefs
->length (); ++j
)
440 data_reference_p dr
= (*datarefs
)[j
];
442 RDGV_HAS_MEM_READS (v
) = true;
444 RDGV_HAS_MEM_WRITE (v
) = true;
445 RDGV_DATAREFS (v
).safe_push (dr
);
451 /* Initialize STMTS with all the statements of LOOP. The order in
452 which we discover statements is important as
453 generate_loops_for_partition is using the same traversal for
454 identifying statements in loop copies. */
457 stmts_from_loop (struct loop
*loop
, vec
<gimple
> *stmts
)
460 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
462 for (i
= 0; i
< loop
->num_nodes
; i
++)
464 basic_block bb
= bbs
[i
];
465 gimple_stmt_iterator bsi
;
468 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
469 if (!virtual_operand_p (gimple_phi_result (gsi_stmt (bsi
))))
470 stmts
->safe_push (gsi_stmt (bsi
));
472 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
474 stmt
= gsi_stmt (bsi
);
475 if (gimple_code (stmt
) != GIMPLE_LABEL
&& !is_gimple_debug (stmt
))
476 stmts
->safe_push (stmt
);
483 /* Free the reduced dependence graph RDG. */
486 free_rdg (struct graph
*rdg
)
490 for (i
= 0; i
< rdg
->n_vertices
; i
++)
492 struct vertex
*v
= &(rdg
->vertices
[i
]);
493 struct graph_edge
*e
;
495 for (e
= v
->succ
; e
; e
= e
->succ_next
)
497 free_dependence_relation (RDGE_RELATION (e
));
503 gimple_set_uid (RDGV_STMT (v
), -1);
504 free_data_refs (RDGV_DATAREFS (v
));
512 /* Build the Reduced Dependence Graph (RDG) with one vertex per
513 statement of the loop nest LOOP_NEST, and one edge per data dependence or
514 scalar dependence. */
516 static struct graph
*
517 build_rdg (vec
<loop_p
> loop_nest
, control_dependences
*cd
)
521 vec
<data_reference_p
> datarefs
;
522 vec
<ddr_p
> dependence_relations
;
524 /* Create the RDG vertices from the stmts of the loop nest. */
526 stmts_from_loop (loop_nest
[0], &stmts
);
527 rdg
= new_graph (stmts
.length ());
528 datarefs
.create (10);
529 if (!create_rdg_vertices (rdg
, stmts
, loop_nest
[0], &datarefs
))
538 /* Create the RDG edges from the data dependences in the loop nest. */
539 dependence_relations
.create (100);
540 if (!compute_all_dependences (datarefs
, &dependence_relations
, loop_nest
,
542 || !known_dependences_p (dependence_relations
))
544 free_dependence_relations (dependence_relations
);
549 create_rdg_edges (rdg
, dependence_relations
, cd
);
550 dependence_relations
.release ();
558 enum partition_kind
{
559 PKIND_NORMAL
, PKIND_MEMSET
, PKIND_MEMCPY
562 typedef struct partition_s
567 enum partition_kind kind
;
568 /* data-references a kind != PKIND_NORMAL partition is about. */
569 data_reference_p main_dr
;
570 data_reference_p secondary_dr
;
575 /* Allocate and initialize a partition from BITMAP. */
578 partition_alloc (bitmap stmts
, bitmap loops
)
580 partition_t partition
= XCNEW (struct partition_s
);
581 partition
->stmts
= stmts
? stmts
: BITMAP_ALLOC (NULL
);
582 partition
->loops
= loops
? loops
: BITMAP_ALLOC (NULL
);
583 partition
->reduction_p
= false;
584 partition
->kind
= PKIND_NORMAL
;
588 /* Free PARTITION. */
591 partition_free (partition_t partition
)
593 BITMAP_FREE (partition
->stmts
);
594 BITMAP_FREE (partition
->loops
);
598 /* Returns true if the partition can be generated as a builtin. */
601 partition_builtin_p (partition_t partition
)
603 return partition
->kind
!= PKIND_NORMAL
;
606 /* Returns true if the partition contains a reduction. */
609 partition_reduction_p (partition_t partition
)
611 return partition
->reduction_p
;
614 /* Merge PARTITION into the partition DEST. */
617 partition_merge_into (partition_t dest
, partition_t partition
)
619 dest
->kind
= PKIND_NORMAL
;
620 bitmap_ior_into (dest
->stmts
, partition
->stmts
);
621 if (partition_reduction_p (partition
))
622 dest
->reduction_p
= true;
626 /* Returns true when DEF is an SSA_NAME defined in LOOP and used after
630 ssa_name_has_uses_outside_loop_p (tree def
, loop_p loop
)
632 imm_use_iterator imm_iter
;
635 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
637 gimple use_stmt
= USE_STMT (use_p
);
638 if (!is_gimple_debug (use_stmt
)
639 && loop
!= loop_containing_stmt (use_stmt
))
646 /* Returns true when STMT defines a scalar variable used after the
650 stmt_has_scalar_dependences_outside_loop (loop_p loop
, gimple stmt
)
655 if (gimple_code (stmt
) == GIMPLE_PHI
)
656 return ssa_name_has_uses_outside_loop_p (gimple_phi_result (stmt
), loop
);
658 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
659 if (ssa_name_has_uses_outside_loop_p (DEF_FROM_PTR (def_p
), loop
))
665 /* Return a copy of LOOP placed before LOOP. */
668 copy_loop_before (struct loop
*loop
)
671 edge preheader
= loop_preheader_edge (loop
);
673 initialize_original_copy_tables ();
674 res
= slpeel_tree_duplicate_loop_to_edge_cfg (loop
, preheader
);
675 gcc_assert (res
!= NULL
);
676 free_original_copy_tables ();
677 delete_update_ssa ();
682 /* Creates an empty basic block after LOOP. */
685 create_bb_after_loop (struct loop
*loop
)
687 edge exit
= single_exit (loop
);
695 /* Generate code for PARTITION from the code in LOOP. The loop is
696 copied when COPY_P is true. All the statements not flagged in the
697 PARTITION bitmap are removed from the loop or from its copy. The
698 statements are indexed in sequence inside a basic block, and the
699 basic blocks of a loop are taken in dom order. */
702 generate_loops_for_partition (struct loop
*loop
, partition_t partition
,
706 gimple_stmt_iterator bsi
;
711 loop
= copy_loop_before (loop
);
712 gcc_assert (loop
!= NULL
);
713 create_preheader (loop
, CP_SIMPLE_PREHEADERS
);
714 create_bb_after_loop (loop
);
717 /* Remove stmts not in the PARTITION bitmap. */
718 bbs
= get_loop_body_in_dom_order (loop
);
720 if (MAY_HAVE_DEBUG_STMTS
)
721 for (i
= 0; i
< loop
->num_nodes
; i
++)
723 basic_block bb
= bbs
[i
];
725 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
727 gimple phi
= gsi_stmt (bsi
);
728 if (!virtual_operand_p (gimple_phi_result (phi
))
729 && !bitmap_bit_p (partition
->stmts
, gimple_uid (phi
)))
730 reset_debug_uses (phi
);
733 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
735 gimple stmt
= gsi_stmt (bsi
);
736 if (gimple_code (stmt
) != GIMPLE_LABEL
737 && !is_gimple_debug (stmt
)
738 && !bitmap_bit_p (partition
->stmts
, gimple_uid (stmt
)))
739 reset_debug_uses (stmt
);
743 for (i
= 0; i
< loop
->num_nodes
; i
++)
745 basic_block bb
= bbs
[i
];
747 for (bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);)
749 gimple phi
= gsi_stmt (bsi
);
750 if (!virtual_operand_p (gimple_phi_result (phi
))
751 && !bitmap_bit_p (partition
->stmts
, gimple_uid (phi
)))
752 remove_phi_node (&bsi
, true);
757 for (bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);)
759 gimple stmt
= gsi_stmt (bsi
);
760 if (gimple_code (stmt
) != GIMPLE_LABEL
761 && !is_gimple_debug (stmt
)
762 && !bitmap_bit_p (partition
->stmts
, gimple_uid (stmt
)))
764 /* Choose an arbitrary path through the empty CFG part
765 that this unnecessary control stmt controls. */
766 if (gimple_code (stmt
) == GIMPLE_COND
)
768 gimple_cond_make_false (stmt
);
771 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
773 gimple_switch_set_index
774 (stmt
, CASE_LOW (gimple_switch_label (stmt
, 1)));
779 unlink_stmt_vdef (stmt
);
780 gsi_remove (&bsi
, true);
792 /* Build the size argument for a memory operation call. */
795 build_size_arg_loc (location_t loc
, data_reference_p dr
, tree nb_iter
)
798 size
= fold_build2_loc (loc
, MULT_EXPR
, sizetype
,
799 fold_convert_loc (loc
, sizetype
, nb_iter
),
800 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
))));
801 return fold_convert_loc (loc
, size_type_node
, size
);
804 /* Build an address argument for a memory operation call. */
807 build_addr_arg_loc (location_t loc
, data_reference_p dr
, tree nb_bytes
)
811 addr_base
= size_binop_loc (loc
, PLUS_EXPR
, DR_OFFSET (dr
), DR_INIT (dr
));
812 addr_base
= fold_convert_loc (loc
, sizetype
, addr_base
);
814 /* Test for a negative stride, iterating over every element. */
815 if (tree_int_cst_sgn (DR_STEP (dr
)) == -1)
817 addr_base
= size_binop_loc (loc
, MINUS_EXPR
, addr_base
,
818 fold_convert_loc (loc
, sizetype
, nb_bytes
));
819 addr_base
= size_binop_loc (loc
, PLUS_EXPR
, addr_base
,
820 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
))));
823 return fold_build_pointer_plus_loc (loc
, DR_BASE_ADDRESS (dr
), addr_base
);
826 /* If VAL memory representation contains the same value in all bytes,
827 return that value, otherwise return -1.
828 E.g. for 0x24242424 return 0x24, for IEEE double
829 747708026454360457216.0 return 0x44, etc. */
832 const_with_all_bytes_same (tree val
)
834 unsigned char buf
[64];
837 if (integer_zerop (val
)
839 || (TREE_CODE (val
) == CONSTRUCTOR
840 && !TREE_CLOBBER_P (val
)
841 && CONSTRUCTOR_NELTS (val
) == 0))
844 if (CHAR_BIT
!= 8 || BITS_PER_UNIT
!= 8)
847 len
= native_encode_expr (val
, buf
, sizeof (buf
));
850 for (i
= 1; i
< len
; i
++)
851 if (buf
[i
] != buf
[0])
856 /* Generate a call to memset for PARTITION in LOOP. */
859 generate_memset_builtin (struct loop
*loop
, partition_t partition
)
861 gimple_stmt_iterator gsi
;
862 gimple stmt
, fn_call
;
863 tree mem
, fn
, nb_bytes
;
867 stmt
= DR_STMT (partition
->main_dr
);
868 loc
= gimple_location (stmt
);
870 /* The new statements will be placed before LOOP. */
871 gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
873 nb_bytes
= build_size_arg_loc (loc
, partition
->main_dr
, partition
->niter
);
874 nb_bytes
= force_gimple_operand_gsi (&gsi
, nb_bytes
, true, NULL_TREE
,
875 false, GSI_CONTINUE_LINKING
);
876 mem
= build_addr_arg_loc (loc
, partition
->main_dr
, nb_bytes
);
877 mem
= force_gimple_operand_gsi (&gsi
, mem
, true, NULL_TREE
,
878 false, GSI_CONTINUE_LINKING
);
880 /* This exactly matches the pattern recognition in classify_partition. */
881 val
= gimple_assign_rhs1 (stmt
);
882 /* Handle constants like 0x15151515 and similarly
883 floating point constants etc. where all bytes are the same. */
884 int bytev
= const_with_all_bytes_same (val
);
886 val
= build_int_cst (integer_type_node
, bytev
);
887 else if (TREE_CODE (val
) == INTEGER_CST
)
888 val
= fold_convert (integer_type_node
, val
);
889 else if (!useless_type_conversion_p (integer_type_node
, TREE_TYPE (val
)))
892 tree tem
= make_ssa_name (integer_type_node
, NULL
);
893 cstmt
= gimple_build_assign_with_ops (NOP_EXPR
, tem
, val
, NULL_TREE
);
894 gsi_insert_after (&gsi
, cstmt
, GSI_CONTINUE_LINKING
);
898 fn
= build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET
));
899 fn_call
= gimple_build_call (fn
, 3, mem
, val
, nb_bytes
);
900 gsi_insert_after (&gsi
, fn_call
, GSI_CONTINUE_LINKING
);
902 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
904 fprintf (dump_file
, "generated memset");
906 fprintf (dump_file
, " zero\n");
908 fprintf (dump_file
, "\n");
912 /* Generate a call to memcpy for PARTITION in LOOP. */
915 generate_memcpy_builtin (struct loop
*loop
, partition_t partition
)
917 gimple_stmt_iterator gsi
;
918 gimple stmt
, fn_call
;
919 tree dest
, src
, fn
, nb_bytes
;
921 enum built_in_function kind
;
923 stmt
= DR_STMT (partition
->main_dr
);
924 loc
= gimple_location (stmt
);
926 /* The new statements will be placed before LOOP. */
927 gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
929 nb_bytes
= build_size_arg_loc (loc
, partition
->main_dr
, partition
->niter
);
930 nb_bytes
= force_gimple_operand_gsi (&gsi
, nb_bytes
, true, NULL_TREE
,
931 false, GSI_CONTINUE_LINKING
);
932 dest
= build_addr_arg_loc (loc
, partition
->main_dr
, nb_bytes
);
933 src
= build_addr_arg_loc (loc
, partition
->secondary_dr
, nb_bytes
);
934 if (ptr_derefs_may_alias_p (dest
, src
))
935 kind
= BUILT_IN_MEMMOVE
;
937 kind
= BUILT_IN_MEMCPY
;
939 dest
= force_gimple_operand_gsi (&gsi
, dest
, true, NULL_TREE
,
940 false, GSI_CONTINUE_LINKING
);
941 src
= force_gimple_operand_gsi (&gsi
, src
, true, NULL_TREE
,
942 false, GSI_CONTINUE_LINKING
);
943 fn
= build_fold_addr_expr (builtin_decl_implicit (kind
));
944 fn_call
= gimple_build_call (fn
, 3, dest
, src
, nb_bytes
);
945 gsi_insert_after (&gsi
, fn_call
, GSI_CONTINUE_LINKING
);
947 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
949 if (kind
== BUILT_IN_MEMCPY
)
950 fprintf (dump_file
, "generated memcpy\n");
952 fprintf (dump_file
, "generated memmove\n");
956 /* Remove and destroy the loop LOOP. */
959 destroy_loop (struct loop
*loop
)
961 unsigned nbbs
= loop
->num_nodes
;
962 edge exit
= single_exit (loop
);
963 basic_block src
= loop_preheader_edge (loop
)->src
, dest
= exit
->dest
;
967 bbs
= get_loop_body_in_dom_order (loop
);
969 redirect_edge_pred (exit
, src
);
970 exit
->flags
&= ~(EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
971 exit
->flags
|= EDGE_FALLTHRU
;
972 cancel_loop_tree (loop
);
973 rescan_loop_exit (exit
, false, true);
975 for (i
= 0; i
< nbbs
; i
++)
977 /* We have made sure to not leave any dangling uses of SSA
978 names defined in the loop. With the exception of virtuals.
979 Make sure we replace all uses of virtual defs that will remain
980 outside of the loop with the bare symbol as delete_basic_block
981 will release them. */
982 gimple_stmt_iterator gsi
;
983 for (gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
985 gimple phi
= gsi_stmt (gsi
);
986 if (virtual_operand_p (gimple_phi_result (phi
)))
987 mark_virtual_phi_result_for_renaming (phi
);
989 for (gsi
= gsi_start_bb (bbs
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
991 gimple stmt
= gsi_stmt (gsi
);
992 tree vdef
= gimple_vdef (stmt
);
993 if (vdef
&& TREE_CODE (vdef
) == SSA_NAME
)
994 mark_virtual_operand_for_renaming (vdef
);
996 delete_basic_block (bbs
[i
]);
1000 set_immediate_dominator (CDI_DOMINATORS
, dest
,
1001 recompute_dominator (CDI_DOMINATORS
, dest
));
1004 /* Generates code for PARTITION. */
1007 generate_code_for_partition (struct loop
*loop
,
1008 partition_t partition
, bool copy_p
)
1010 switch (partition
->kind
)
1013 /* Reductions all have to be in the last partition. */
1014 gcc_assert (!partition_reduction_p (partition
)
1016 generate_loops_for_partition (loop
, partition
, copy_p
);
1020 generate_memset_builtin (loop
, partition
);
1024 generate_memcpy_builtin (loop
, partition
);
1031 /* Common tail for partitions we turn into a call. If this was the last
1032 partition for which we generate code, we have to destroy the loop. */
1034 destroy_loop (loop
);
1038 /* Returns a partition with all the statements needed for computing
1039 the vertex V of the RDG, also including the loop exit conditions. */
1042 build_rdg_partition_for_vertex (struct graph
*rdg
, int v
)
1044 partition_t partition
= partition_alloc (NULL
, NULL
);
1050 graphds_dfs (rdg
, &v
, 1, &nodes
, false, NULL
);
1052 FOR_EACH_VEC_ELT (nodes
, i
, x
)
1054 bitmap_set_bit (partition
->stmts
, x
);
1055 bitmap_set_bit (partition
->loops
,
1056 loop_containing_stmt (RDG_STMT (rdg
, x
))->num
);
1063 /* Classifies the builtin kind we can generate for PARTITION of RDG and LOOP.
1064 For the moment we detect only the memset zero pattern. */
1067 classify_partition (loop_p loop
, struct graph
*rdg
, partition_t partition
)
1072 data_reference_p single_load
, single_store
;
1073 bool volatiles_p
= false;
1075 partition
->kind
= PKIND_NORMAL
;
1076 partition
->main_dr
= NULL
;
1077 partition
->secondary_dr
= NULL
;
1078 partition
->niter
= NULL_TREE
;
1080 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, bi
)
1082 gimple stmt
= RDG_STMT (rdg
, i
);
1084 if (gimple_has_volatile_ops (stmt
))
1087 /* If the stmt has uses outside of the loop mark it as reduction. */
1088 if (stmt_has_scalar_dependences_outside_loop (loop
, stmt
))
1090 partition
->reduction_p
= true;
1095 /* Perform general partition disqualification for builtins. */
1097 || !flag_tree_loop_distribute_patterns
)
1100 /* Detect memset and memcpy. */
1102 single_store
= NULL
;
1103 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, bi
)
1105 gimple stmt
= RDG_STMT (rdg
, i
);
1106 data_reference_p dr
;
1109 if (gimple_code (stmt
) == GIMPLE_PHI
)
1112 /* Any scalar stmts are ok. */
1113 if (!gimple_vuse (stmt
))
1116 /* Otherwise just regular loads/stores. */
1117 if (!gimple_assign_single_p (stmt
))
1120 /* But exactly one store and/or load. */
1121 for (j
= 0; RDG_DATAREFS (rdg
, i
).iterate (j
, &dr
); ++j
)
1123 if (DR_IS_READ (dr
))
1125 if (single_load
!= NULL
)
1131 if (single_store
!= NULL
)
1141 if (!dominated_by_p (CDI_DOMINATORS
, single_exit (loop
)->src
,
1142 gimple_bb (DR_STMT (single_store
))))
1143 nb_iter
= number_of_latch_executions (loop
);
1145 nb_iter
= number_of_exit_cond_executions (loop
);
1146 if (!nb_iter
|| nb_iter
== chrec_dont_know
)
1149 if (single_store
&& !single_load
)
1151 gimple stmt
= DR_STMT (single_store
);
1152 tree rhs
= gimple_assign_rhs1 (stmt
);
1153 if (const_with_all_bytes_same (rhs
) == -1
1154 && (!INTEGRAL_TYPE_P (TREE_TYPE (rhs
))
1155 || (TYPE_MODE (TREE_TYPE (rhs
))
1156 != TYPE_MODE (unsigned_char_type_node
))))
1158 if (TREE_CODE (rhs
) == SSA_NAME
1159 && !SSA_NAME_IS_DEFAULT_DEF (rhs
)
1160 && flow_bb_inside_loop_p (loop
, gimple_bb (SSA_NAME_DEF_STMT (rhs
))))
1162 if (!adjacent_dr_p (single_store
)
1163 || !dominated_by_p (CDI_DOMINATORS
,
1164 loop
->latch
, gimple_bb (stmt
)))
1166 partition
->kind
= PKIND_MEMSET
;
1167 partition
->main_dr
= single_store
;
1168 partition
->niter
= nb_iter
;
1170 else if (single_store
&& single_load
)
1172 gimple store
= DR_STMT (single_store
);
1173 gimple load
= DR_STMT (single_load
);
1174 /* Direct aggregate copy or via an SSA name temporary. */
1176 && gimple_assign_lhs (load
) != gimple_assign_rhs1 (store
))
1178 if (!adjacent_dr_p (single_store
)
1179 || !adjacent_dr_p (single_load
)
1180 || !operand_equal_p (DR_STEP (single_store
),
1181 DR_STEP (single_load
), 0)
1182 || !dominated_by_p (CDI_DOMINATORS
,
1183 loop
->latch
, gimple_bb (store
)))
1185 /* Now check that if there is a dependence this dependence is
1186 of a suitable form for memmove. */
1187 vec
<loop_p
> loops
= vNULL
;
1189 loops
.safe_push (loop
);
1190 ddr
= initialize_data_dependence_relation (single_load
, single_store
,
1192 compute_affine_dependence (ddr
, loop
);
1193 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
1195 free_dependence_relation (ddr
);
1199 if (DDR_ARE_DEPENDENT (ddr
) != chrec_known
)
1201 if (DDR_NUM_DIST_VECTS (ddr
) == 0)
1203 free_dependence_relation (ddr
);
1207 lambda_vector dist_v
;
1208 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
1210 int dist
= dist_v
[index_in_loop_nest (loop
->num
,
1211 DDR_LOOP_NEST (ddr
))];
1212 if (dist
> 0 && !DDR_REVERSED_P (ddr
))
1214 free_dependence_relation (ddr
);
1220 free_dependence_relation (ddr
);
1222 partition
->kind
= PKIND_MEMCPY
;
1223 partition
->main_dr
= single_store
;
1224 partition
->secondary_dr
= single_load
;
1225 partition
->niter
= nb_iter
;
1229 /* For a data reference REF, return the declaration of its base
1230 address or NULL_TREE if the base is not determined. */
1233 ref_base_address (data_reference_p dr
)
1235 tree base_address
= DR_BASE_ADDRESS (dr
);
1237 && TREE_CODE (base_address
) == ADDR_EXPR
)
1238 return TREE_OPERAND (base_address
, 0);
1240 return base_address
;
1243 /* Returns true when PARTITION1 and PARTITION2 have similar memory
1247 similar_memory_accesses (struct graph
*rdg
, partition_t partition1
,
1248 partition_t partition2
)
1250 unsigned i
, j
, k
, l
;
1251 bitmap_iterator bi
, bj
;
1252 data_reference_p ref1
, ref2
;
1254 /* First check whether in the intersection of the two partitions are
1255 any loads or stores. Common loads are the situation that happens
1257 EXECUTE_IF_AND_IN_BITMAP (partition1
->stmts
, partition2
->stmts
, 0, i
, bi
)
1258 if (RDG_MEM_WRITE_STMT (rdg
, i
)
1259 || RDG_MEM_READS_STMT (rdg
, i
))
1262 /* Then check all data-references against each other. */
1263 EXECUTE_IF_SET_IN_BITMAP (partition1
->stmts
, 0, i
, bi
)
1264 if (RDG_MEM_WRITE_STMT (rdg
, i
)
1265 || RDG_MEM_READS_STMT (rdg
, i
))
1266 EXECUTE_IF_SET_IN_BITMAP (partition2
->stmts
, 0, j
, bj
)
1267 if (RDG_MEM_WRITE_STMT (rdg
, j
)
1268 || RDG_MEM_READS_STMT (rdg
, j
))
1270 FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg
, i
), k
, ref1
)
1272 tree base1
= ref_base_address (ref1
);
1274 FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg
, j
), l
, ref2
)
1275 if (base1
== ref_base_address (ref2
))
1283 /* Aggregate several components into a useful partition that is
1284 registered in the PARTITIONS vector. Partitions will be
1285 distributed in different loops. */
1288 rdg_build_partitions (struct graph
*rdg
,
1289 vec
<gimple
> starting_stmts
,
1290 vec
<partition_t
> *partitions
)
1292 bitmap processed
= BITMAP_ALLOC (NULL
);
1296 FOR_EACH_VEC_ELT (starting_stmts
, i
, stmt
)
1298 int v
= rdg_vertex_for_stmt (rdg
, stmt
);
1300 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1302 "ldist asked to generate code for vertex %d\n", v
);
1304 /* If the vertex is already contained in another partition so
1305 is the partition rooted at it. */
1306 if (bitmap_bit_p (processed
, v
))
1309 partition_t partition
= build_rdg_partition_for_vertex (rdg
, v
);
1310 bitmap_ior_into (processed
, partition
->stmts
);
1312 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1314 fprintf (dump_file
, "ldist useful partition:\n");
1315 dump_bitmap (dump_file
, partition
->stmts
);
1318 partitions
->safe_push (partition
);
1321 /* All vertices should have been assigned to at least one partition now,
1322 other than vertices belonging to dead code. */
1324 BITMAP_FREE (processed
);
1327 /* Dump to FILE the PARTITIONS. */
1330 dump_rdg_partitions (FILE *file
, vec
<partition_t
> partitions
)
1333 partition_t partition
;
1335 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1336 debug_bitmap_file (file
, partition
->stmts
);
1339 /* Debug PARTITIONS. */
1340 extern void debug_rdg_partitions (vec
<partition_t
> );
1343 debug_rdg_partitions (vec
<partition_t
> partitions
)
1345 dump_rdg_partitions (stderr
, partitions
);
1348 /* Returns the number of read and write operations in the RDG. */
1351 number_of_rw_in_rdg (struct graph
*rdg
)
1355 for (i
= 0; i
< rdg
->n_vertices
; i
++)
1357 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1360 if (RDG_MEM_READS_STMT (rdg
, i
))
1367 /* Returns the number of read and write operations in a PARTITION of
1371 number_of_rw_in_partition (struct graph
*rdg
, partition_t partition
)
1377 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, ii
)
1379 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1382 if (RDG_MEM_READS_STMT (rdg
, i
))
1389 /* Returns true when one of the PARTITIONS contains all the read or
1390 write operations of RDG. */
1393 partition_contains_all_rw (struct graph
*rdg
,
1394 vec
<partition_t
> partitions
)
1397 partition_t partition
;
1398 int nrw
= number_of_rw_in_rdg (rdg
);
1400 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1401 if (nrw
== number_of_rw_in_partition (rdg
, partition
))
1408 /* Distributes the code from LOOP in such a way that producer
1409 statements are placed before consumer statements. Tries to separate
1410 only the statements from STMTS into separate loops.
1411 Returns the number of distributed loops. */
1414 distribute_loop (struct loop
*loop
, vec
<gimple
> stmts
,
1415 control_dependences
*cd
, int *nb_calls
)
1418 vec
<loop_p
> loop_nest
;
1419 vec
<partition_t
> partitions
;
1420 partition_t partition
;
1425 loop_nest
.create (3);
1426 if (!find_loop_nest (loop
, &loop_nest
))
1428 loop_nest
.release ();
1432 rdg
= build_rdg (loop_nest
, cd
);
1435 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1437 "Loop %d not distributed: failed to build the RDG.\n",
1440 loop_nest
.release ();
1444 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1445 dump_rdg (dump_file
, rdg
);
1447 partitions
.create (3);
1448 rdg_build_partitions (rdg
, stmts
, &partitions
);
1450 any_builtin
= false;
1451 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1453 classify_partition (loop
, rdg
, partition
);
1454 any_builtin
|= partition_builtin_p (partition
);
1457 /* If we did not detect any builtin but are not asked to apply
1458 regular loop distribution simply bail out. */
1459 if (!flag_tree_loop_distribution
1466 /* Apply our simple cost model - fuse partitions with similar
1469 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
1471 if (partition_builtin_p (into
))
1474 partitions
.iterate (j
, &partition
); ++j
)
1476 if (!partition_builtin_p (partition
)
1477 && similar_memory_accesses (rdg
, into
, partition
))
1479 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1481 fprintf (dump_file
, "fusing partitions\n");
1482 dump_bitmap (dump_file
, into
->stmts
);
1483 dump_bitmap (dump_file
, partition
->stmts
);
1484 fprintf (dump_file
, "because they have similar "
1485 "memory accesses\n");
1487 partition_merge_into (into
, partition
);
1488 partitions
.ordered_remove (j
);
1489 partition_free (partition
);
1495 /* If we are only distributing patterns fuse all partitions that
1496 were not properly classified as builtins. */
1497 if (!flag_tree_loop_distribution
)
1500 /* Only fuse adjacent non-builtin partitions, see PR53616.
1501 ??? Use dependence information to improve partition ordering. */
1505 for (; partitions
.iterate (i
, &into
); ++i
)
1506 if (!partition_builtin_p (into
))
1508 for (++i
; partitions
.iterate (i
, &partition
); ++i
)
1509 if (!partition_builtin_p (partition
))
1511 partition_merge_into (into
, partition
);
1512 partitions
.ordered_remove (i
);
1513 partition_free (partition
);
1519 while ((unsigned) i
< partitions
.length ());
1522 /* Fuse all reduction partitions into the last. */
1523 if (partitions
.length () > 1)
1525 partition_t into
= partitions
.last ();
1526 for (i
= partitions
.length () - 2; i
>= 0; --i
)
1528 partition_t what
= partitions
[i
];
1529 if (partition_reduction_p (what
))
1531 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1533 fprintf (dump_file
, "fusing partitions\n");
1534 dump_bitmap (dump_file
, into
->stmts
);
1535 dump_bitmap (dump_file
, what
->stmts
);
1536 fprintf (dump_file
, "because the latter has reductions\n");
1538 partition_merge_into (into
, what
);
1539 partitions
.ordered_remove (i
);
1540 partition_free (what
);
1545 nbp
= partitions
.length ();
1547 || (nbp
== 1 && !partition_builtin_p (partitions
[0]))
1548 || (nbp
> 1 && partition_contains_all_rw (rdg
, partitions
)))
1554 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1555 dump_rdg_partitions (dump_file
, partitions
);
1557 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1559 if (partition_builtin_p (partition
))
1561 generate_code_for_partition (loop
, partition
, i
< nbp
- 1);
1566 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1567 partition_free (partition
);
1568 partitions
.release ();
1571 loop_nest
.release ();
1572 return nbp
- *nb_calls
;
1575 /* Distribute all loops in the current function. */
1578 tree_loop_distribution (void)
1582 bool changed
= false;
1584 control_dependences
*cd
= NULL
;
1588 gimple_stmt_iterator gsi
;
1589 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1590 gimple_set_uid (gsi_stmt (gsi
), -1);
1591 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1592 gimple_set_uid (gsi_stmt (gsi
), -1);
1595 /* We can at the moment only distribute non-nested loops, thus restrict
1596 walking to innermost loops. */
1597 FOR_EACH_LOOP (li
, loop
, LI_ONLY_INNERMOST
)
1599 vec
<gimple
> work_list
= vNULL
;
1601 int num
= loop
->num
;
1604 /* If the loop doesn't have a single exit we will fail anyway,
1605 so do that early. */
1606 if (!single_exit (loop
))
1609 /* Only optimize hot loops. */
1610 if (!optimize_loop_for_speed_p (loop
))
1613 /* Initialize the worklist with stmts we seed the partitions with. */
1614 bbs
= get_loop_body_in_dom_order (loop
);
1615 for (i
= 0; i
< loop
->num_nodes
; ++i
)
1617 gimple_stmt_iterator gsi
;
1618 for (gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
1620 gimple phi
= gsi_stmt (gsi
);
1621 if (virtual_operand_p (gimple_phi_result (phi
)))
1623 /* Distribute stmts which have defs that are used outside of
1625 if (!stmt_has_scalar_dependences_outside_loop (loop
, phi
))
1627 work_list
.safe_push (phi
);
1629 for (gsi
= gsi_start_bb (bbs
[i
]); !gsi_end_p (gsi
); gsi_next (&gsi
))
1631 gimple stmt
= gsi_stmt (gsi
);
1633 /* If there is a stmt with side-effects bail out - we
1634 cannot and should not distribute this loop. */
1635 if (gimple_has_side_effects (stmt
))
1637 work_list
.truncate (0);
1641 /* Distribute stmts which have defs that are used outside of
1643 if (stmt_has_scalar_dependences_outside_loop (loop
, stmt
))
1645 /* Otherwise only distribute stores for now. */
1646 else if (!gimple_assign_single_p (stmt
)
1647 || is_gimple_reg (gimple_assign_lhs (stmt
)))
1650 work_list
.safe_push (stmt
);
1656 int nb_generated_loops
= 0;
1657 int nb_generated_calls
= 0;
1658 location_t loc
= find_loop_location (loop
);
1659 if (work_list
.length () > 0)
1663 calculate_dominance_info (CDI_DOMINATORS
);
1664 calculate_dominance_info (CDI_POST_DOMINATORS
);
1665 cd
= new control_dependences (create_edge_list ());
1666 free_dominance_info (CDI_POST_DOMINATORS
);
1668 nb_generated_loops
= distribute_loop (loop
, work_list
, cd
,
1669 &nb_generated_calls
);
1672 if (nb_generated_loops
+ nb_generated_calls
> 0)
1675 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
,
1676 loc
, "Loop %d distributed: split to %d loops "
1677 "and %d library calls.\n",
1678 num
, nb_generated_loops
, nb_generated_calls
);
1680 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1681 fprintf (dump_file
, "Loop %d is the same.\n", num
);
1683 work_list
.release ();
1691 mark_virtual_operands_for_renaming (cfun
);
1692 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1695 #ifdef ENABLE_CHECKING
1696 verify_loop_structure ();
1703 gate_tree_loop_distribution (void)
1705 return flag_tree_loop_distribution
1706 || flag_tree_loop_distribute_patterns
;
1711 const pass_data pass_data_loop_distribution
=
1713 GIMPLE_PASS
, /* type */
1715 OPTGROUP_LOOP
, /* optinfo_flags */
1716 true, /* has_gate */
1717 true, /* has_execute */
1718 TV_TREE_LOOP_DISTRIBUTION
, /* tv_id */
1719 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1720 0, /* properties_provided */
1721 0, /* properties_destroyed */
1722 0, /* todo_flags_start */
1723 TODO_verify_ssa
, /* todo_flags_finish */
1726 class pass_loop_distribution
: public gimple_opt_pass
1729 pass_loop_distribution (gcc::context
*ctxt
)
1730 : gimple_opt_pass (pass_data_loop_distribution
, ctxt
)
1733 /* opt_pass methods: */
1734 bool gate () { return gate_tree_loop_distribution (); }
1735 unsigned int execute () { return tree_loop_distribution (); }
1737 }; // class pass_loop_distribution
1742 make_pass_loop_distribution (gcc::context
*ctxt
)
1744 return new pass_loop_distribution (ctxt
);