2 Copyright (C) 2006-2014 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"
54 #include "hard-reg-set.h"
57 #include "dominance.h"
60 #include "basic-block.h"
61 #include "tree-ssa-alias.h"
62 #include "internal-fn.h"
63 #include "gimple-expr.h"
66 #include "gimple-iterator.h"
67 #include "gimplify-me.h"
68 #include "stor-layout.h"
69 #include "gimple-ssa.h"
71 #include "tree-phinodes.h"
72 #include "ssa-iterators.h"
73 #include "stringpool.h"
74 #include "tree-ssanames.h"
75 #include "tree-ssa-loop-manip.h"
76 #include "tree-ssa-loop.h"
77 #include "tree-into-ssa.h"
80 #include "tree-chrec.h"
81 #include "tree-data-ref.h"
82 #include "tree-scalar-evolution.h"
83 #include "tree-pass.h"
84 #include "gimple-pretty-print.h"
85 #include "tree-vectorizer.h"
88 /* A Reduced Dependence Graph (RDG) vertex representing a statement. */
89 typedef struct rdg_vertex
91 /* The statement represented by this vertex. */
94 /* Vector of data-references in this statement. */
95 vec
<data_reference_p
> datarefs
;
97 /* True when the statement contains a write to memory. */
100 /* True when the statement contains a read from memory. */
104 #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
105 #define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs
106 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
107 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
108 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
109 #define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I]))
110 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
111 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
113 /* Data dependence type. */
117 /* Read After Write (RAW). */
120 /* Control dependence (execute conditional on). */
124 /* Dependence information attached to an edge of the RDG. */
126 typedef struct rdg_edge
128 /* Type of the dependence. */
129 enum rdg_dep_type type
;
132 #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
134 /* Dump vertex I in RDG to FILE. */
137 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
139 struct vertex
*v
= &(rdg
->vertices
[i
]);
140 struct graph_edge
*e
;
142 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
143 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
144 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
147 for (e
= v
->pred
; e
; e
= e
->pred_next
)
148 fprintf (file
, " %d", e
->src
);
150 fprintf (file
, ") (out:");
153 for (e
= v
->succ
; e
; e
= e
->succ_next
)
154 fprintf (file
, " %d", e
->dest
);
156 fprintf (file
, ")\n");
157 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
158 fprintf (file
, ")\n");
161 /* Call dump_rdg_vertex on stderr. */
164 debug_rdg_vertex (struct graph
*rdg
, int i
)
166 dump_rdg_vertex (stderr
, rdg
, i
);
169 /* Dump the reduced dependence graph RDG to FILE. */
172 dump_rdg (FILE *file
, struct graph
*rdg
)
174 fprintf (file
, "(rdg\n");
175 for (int i
= 0; i
< rdg
->n_vertices
; i
++)
176 dump_rdg_vertex (file
, rdg
, i
);
177 fprintf (file
, ")\n");
180 /* Call dump_rdg on stderr. */
183 debug_rdg (struct graph
*rdg
)
185 dump_rdg (stderr
, rdg
);
189 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
192 pretty_printer buffer
;
193 pp_needs_newline (&buffer
) = false;
194 buffer
.buffer
->stream
= file
;
196 fprintf (file
, "digraph RDG {\n");
198 for (i
= 0; i
< rdg
->n_vertices
; i
++)
200 struct vertex
*v
= &(rdg
->vertices
[i
]);
201 struct graph_edge
*e
;
203 fprintf (file
, "%d [label=\"[%d] ", i
, i
);
204 pp_gimple_stmt_1 (&buffer
, RDGV_STMT (v
), 0, TDF_SLIM
);
206 fprintf (file
, "\"]\n");
208 /* Highlight reads from memory. */
209 if (RDG_MEM_READS_STMT (rdg
, i
))
210 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
212 /* Highlight stores to memory. */
213 if (RDG_MEM_WRITE_STMT (rdg
, i
))
214 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
217 for (e
= v
->succ
; e
; e
= e
->succ_next
)
218 switch (RDGE_TYPE (e
))
221 /* These are the most common dependences: don't print these. */
222 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
226 fprintf (file
, "%d -> %d [label=control] \n", i
, e
->dest
);
234 fprintf (file
, "}\n\n");
237 /* Display the Reduced Dependence Graph using dotty. */
240 dot_rdg (struct graph
*rdg
)
242 /* When debugging, you may want to enable the following code. */
244 FILE *file
= popen ("dot -Tx11", "w");
247 dot_rdg_1 (file
, rdg
);
249 close (fileno (file
));
252 dot_rdg_1 (stderr
, rdg
);
256 /* Returns the index of STMT in RDG. */
259 rdg_vertex_for_stmt (struct graph
*rdg ATTRIBUTE_UNUSED
, gimple stmt
)
261 int index
= gimple_uid (stmt
);
262 gcc_checking_assert (index
== -1 || RDG_STMT (rdg
, index
) == stmt
);
266 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
267 the index of DEF in RDG. */
270 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
272 use_operand_p imm_use_p
;
273 imm_use_iterator iterator
;
275 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
277 struct graph_edge
*e
;
278 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
283 e
= add_edge (rdg
, idef
, use
);
284 e
->data
= XNEW (struct rdg_edge
);
285 RDGE_TYPE (e
) = flow_dd
;
289 /* Creates an edge for the control dependences of BB to the vertex V. */
292 create_edge_for_control_dependence (struct graph
*rdg
, basic_block bb
,
293 int v
, control_dependences
*cd
)
297 EXECUTE_IF_SET_IN_BITMAP (cd
->get_edges_dependent_on (bb
->index
),
300 basic_block cond_bb
= cd
->get_edge (edge_n
)->src
;
301 gimple stmt
= last_stmt (cond_bb
);
302 if (stmt
&& is_ctrl_stmt (stmt
))
304 struct graph_edge
*e
;
305 int c
= rdg_vertex_for_stmt (rdg
, stmt
);
309 e
= add_edge (rdg
, c
, v
);
310 e
->data
= XNEW (struct rdg_edge
);
311 RDGE_TYPE (e
) = control_dd
;
316 /* Creates the edges of the reduced dependence graph RDG. */
319 create_rdg_flow_edges (struct graph
*rdg
)
325 for (i
= 0; i
< rdg
->n_vertices
; i
++)
326 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
328 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
331 /* Creates the edges of the reduced dependence graph RDG. */
334 create_rdg_cd_edges (struct graph
*rdg
, control_dependences
*cd
)
338 for (i
= 0; i
< rdg
->n_vertices
; i
++)
340 gimple stmt
= RDG_STMT (rdg
, i
);
341 if (gimple_code (stmt
) == GIMPLE_PHI
)
345 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->preds
)
346 create_edge_for_control_dependence (rdg
, e
->src
, i
, cd
);
349 create_edge_for_control_dependence (rdg
, gimple_bb (stmt
), i
, cd
);
353 /* Build the vertices of the reduced dependence graph RDG. Return false
357 create_rdg_vertices (struct graph
*rdg
, vec
<gimple
> stmts
, loop_p loop
,
358 vec
<data_reference_p
> *datarefs
)
363 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
365 struct vertex
*v
= &(rdg
->vertices
[i
]);
367 /* Record statement to vertex mapping. */
368 gimple_set_uid (stmt
, i
);
370 v
->data
= XNEW (struct rdg_vertex
);
371 RDGV_STMT (v
) = stmt
;
372 RDGV_DATAREFS (v
).create (0);
373 RDGV_HAS_MEM_WRITE (v
) = false;
374 RDGV_HAS_MEM_READS (v
) = false;
375 if (gimple_code (stmt
) == GIMPLE_PHI
)
378 unsigned drp
= datarefs
->length ();
379 if (!find_data_references_in_stmt (loop
, stmt
, datarefs
))
381 for (unsigned j
= drp
; j
< datarefs
->length (); ++j
)
383 data_reference_p dr
= (*datarefs
)[j
];
385 RDGV_HAS_MEM_READS (v
) = true;
387 RDGV_HAS_MEM_WRITE (v
) = true;
388 RDGV_DATAREFS (v
).safe_push (dr
);
394 /* Initialize STMTS with all the statements of LOOP. The order in
395 which we discover statements is important as
396 generate_loops_for_partition is using the same traversal for
397 identifying statements in loop copies. */
400 stmts_from_loop (struct loop
*loop
, vec
<gimple
> *stmts
)
403 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
405 for (i
= 0; i
< loop
->num_nodes
; i
++)
407 basic_block bb
= bbs
[i
];
409 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
411 if (!virtual_operand_p (gimple_phi_result (bsi
.phi ())))
412 stmts
->safe_push (bsi
.phi ());
414 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
417 gimple stmt
= gsi_stmt (bsi
);
418 if (gimple_code (stmt
) != GIMPLE_LABEL
&& !is_gimple_debug (stmt
))
419 stmts
->safe_push (stmt
);
426 /* Free the reduced dependence graph RDG. */
429 free_rdg (struct graph
*rdg
)
433 for (i
= 0; i
< rdg
->n_vertices
; i
++)
435 struct vertex
*v
= &(rdg
->vertices
[i
]);
436 struct graph_edge
*e
;
438 for (e
= v
->succ
; e
; e
= e
->succ_next
)
443 gimple_set_uid (RDGV_STMT (v
), -1);
444 free_data_refs (RDGV_DATAREFS (v
));
452 /* Build the Reduced Dependence Graph (RDG) with one vertex per
453 statement of the loop nest LOOP_NEST, and one edge per data dependence or
454 scalar dependence. */
456 static struct graph
*
457 build_rdg (vec
<loop_p
> loop_nest
, control_dependences
*cd
)
460 vec
<data_reference_p
> datarefs
;
462 /* Create the RDG vertices from the stmts of the loop nest. */
463 auto_vec
<gimple
, 10> stmts
;
464 stmts_from_loop (loop_nest
[0], &stmts
);
465 rdg
= new_graph (stmts
.length ());
466 datarefs
.create (10);
467 if (!create_rdg_vertices (rdg
, stmts
, loop_nest
[0], &datarefs
))
475 create_rdg_flow_edges (rdg
);
477 create_rdg_cd_edges (rdg
, cd
);
486 enum partition_kind
{
487 PKIND_NORMAL
, PKIND_MEMSET
, PKIND_MEMCPY
490 typedef struct partition_s
495 enum partition_kind kind
;
496 /* data-references a kind != PKIND_NORMAL partition is about. */
497 data_reference_p main_dr
;
498 data_reference_p secondary_dr
;
504 /* Allocate and initialize a partition from BITMAP. */
507 partition_alloc (bitmap stmts
, bitmap loops
)
509 partition_t partition
= XCNEW (struct partition_s
);
510 partition
->stmts
= stmts
? stmts
: BITMAP_ALLOC (NULL
);
511 partition
->loops
= loops
? loops
: BITMAP_ALLOC (NULL
);
512 partition
->reduction_p
= false;
513 partition
->kind
= PKIND_NORMAL
;
517 /* Free PARTITION. */
520 partition_free (partition_t partition
)
522 BITMAP_FREE (partition
->stmts
);
523 BITMAP_FREE (partition
->loops
);
527 /* Returns true if the partition can be generated as a builtin. */
530 partition_builtin_p (partition_t partition
)
532 return partition
->kind
!= PKIND_NORMAL
;
535 /* Returns true if the partition contains a reduction. */
538 partition_reduction_p (partition_t partition
)
540 return partition
->reduction_p
;
543 /* Merge PARTITION into the partition DEST. */
546 partition_merge_into (partition_t dest
, partition_t partition
)
548 dest
->kind
= PKIND_NORMAL
;
549 bitmap_ior_into (dest
->stmts
, partition
->stmts
);
550 if (partition_reduction_p (partition
))
551 dest
->reduction_p
= true;
555 /* Returns true when DEF is an SSA_NAME defined in LOOP and used after
559 ssa_name_has_uses_outside_loop_p (tree def
, loop_p loop
)
561 imm_use_iterator imm_iter
;
564 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
566 gimple use_stmt
= USE_STMT (use_p
);
567 if (!is_gimple_debug (use_stmt
)
568 && loop
!= loop_containing_stmt (use_stmt
))
575 /* Returns true when STMT defines a scalar variable used after the
579 stmt_has_scalar_dependences_outside_loop (loop_p loop
, gimple stmt
)
584 if (gimple_code (stmt
) == GIMPLE_PHI
)
585 return ssa_name_has_uses_outside_loop_p (gimple_phi_result (stmt
), loop
);
587 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
588 if (ssa_name_has_uses_outside_loop_p (DEF_FROM_PTR (def_p
), loop
))
594 /* Return a copy of LOOP placed before LOOP. */
597 copy_loop_before (struct loop
*loop
)
600 edge preheader
= loop_preheader_edge (loop
);
602 initialize_original_copy_tables ();
603 res
= slpeel_tree_duplicate_loop_to_edge_cfg (loop
, NULL
, preheader
);
604 gcc_assert (res
!= NULL
);
605 free_original_copy_tables ();
606 delete_update_ssa ();
611 /* Creates an empty basic block after LOOP. */
614 create_bb_after_loop (struct loop
*loop
)
616 edge exit
= single_exit (loop
);
624 /* Generate code for PARTITION from the code in LOOP. The loop is
625 copied when COPY_P is true. All the statements not flagged in the
626 PARTITION bitmap are removed from the loop or from its copy. The
627 statements are indexed in sequence inside a basic block, and the
628 basic blocks of a loop are taken in dom order. */
631 generate_loops_for_partition (struct loop
*loop
, partition_t partition
,
639 loop
= copy_loop_before (loop
);
640 gcc_assert (loop
!= NULL
);
641 create_preheader (loop
, CP_SIMPLE_PREHEADERS
);
642 create_bb_after_loop (loop
);
645 /* Remove stmts not in the PARTITION bitmap. */
646 bbs
= get_loop_body_in_dom_order (loop
);
648 if (MAY_HAVE_DEBUG_STMTS
)
649 for (i
= 0; i
< loop
->num_nodes
; i
++)
651 basic_block bb
= bbs
[i
];
653 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
656 gphi
*phi
= bsi
.phi ();
657 if (!virtual_operand_p (gimple_phi_result (phi
))
658 && !bitmap_bit_p (partition
->stmts
, gimple_uid (phi
)))
659 reset_debug_uses (phi
);
662 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
664 gimple stmt
= gsi_stmt (bsi
);
665 if (gimple_code (stmt
) != GIMPLE_LABEL
666 && !is_gimple_debug (stmt
)
667 && !bitmap_bit_p (partition
->stmts
, gimple_uid (stmt
)))
668 reset_debug_uses (stmt
);
672 for (i
= 0; i
< loop
->num_nodes
; i
++)
674 basic_block bb
= bbs
[i
];
676 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);)
678 gphi
*phi
= bsi
.phi ();
679 if (!virtual_operand_p (gimple_phi_result (phi
))
680 && !bitmap_bit_p (partition
->stmts
, gimple_uid (phi
)))
681 remove_phi_node (&bsi
, true);
686 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);)
688 gimple stmt
= gsi_stmt (bsi
);
689 if (gimple_code (stmt
) != GIMPLE_LABEL
690 && !is_gimple_debug (stmt
)
691 && !bitmap_bit_p (partition
->stmts
, gimple_uid (stmt
)))
693 /* Choose an arbitrary path through the empty CFG part
694 that this unnecessary control stmt controls. */
695 if (gcond
*cond_stmt
= dyn_cast
<gcond
*> (stmt
))
697 gimple_cond_make_false (cond_stmt
);
700 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
702 gswitch
*switch_stmt
= as_a
<gswitch
*> (stmt
);
703 gimple_switch_set_index
704 (switch_stmt
, CASE_LOW (gimple_switch_label (switch_stmt
, 1)));
709 unlink_stmt_vdef (stmt
);
710 gsi_remove (&bsi
, true);
722 /* Build the size argument for a memory operation call. */
725 build_size_arg_loc (location_t loc
, data_reference_p dr
, tree nb_iter
,
728 tree size
= fold_convert_loc (loc
, sizetype
, nb_iter
);
730 size
= size_binop (PLUS_EXPR
, size
, size_one_node
);
731 size
= fold_build2_loc (loc
, MULT_EXPR
, sizetype
, size
,
732 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
))));
733 size
= fold_convert_loc (loc
, size_type_node
, size
);
737 /* Build an address argument for a memory operation call. */
740 build_addr_arg_loc (location_t loc
, data_reference_p dr
, tree nb_bytes
)
744 addr_base
= size_binop_loc (loc
, PLUS_EXPR
, DR_OFFSET (dr
), DR_INIT (dr
));
745 addr_base
= fold_convert_loc (loc
, sizetype
, addr_base
);
747 /* Test for a negative stride, iterating over every element. */
748 if (tree_int_cst_sgn (DR_STEP (dr
)) == -1)
750 addr_base
= size_binop_loc (loc
, MINUS_EXPR
, addr_base
,
751 fold_convert_loc (loc
, sizetype
, nb_bytes
));
752 addr_base
= size_binop_loc (loc
, PLUS_EXPR
, addr_base
,
753 TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr
))));
756 return fold_build_pointer_plus_loc (loc
, DR_BASE_ADDRESS (dr
), addr_base
);
759 /* If VAL memory representation contains the same value in all bytes,
760 return that value, otherwise return -1.
761 E.g. for 0x24242424 return 0x24, for IEEE double
762 747708026454360457216.0 return 0x44, etc. */
765 const_with_all_bytes_same (tree val
)
767 unsigned char buf
[64];
770 if (integer_zerop (val
)
772 || (TREE_CODE (val
) == CONSTRUCTOR
773 && !TREE_CLOBBER_P (val
)
774 && CONSTRUCTOR_NELTS (val
) == 0))
777 if (CHAR_BIT
!= 8 || BITS_PER_UNIT
!= 8)
780 len
= native_encode_expr (val
, buf
, sizeof (buf
));
783 for (i
= 1; i
< len
; i
++)
784 if (buf
[i
] != buf
[0])
789 /* Generate a call to memset for PARTITION in LOOP. */
792 generate_memset_builtin (struct loop
*loop
, partition_t partition
)
794 gimple_stmt_iterator gsi
;
795 gimple stmt
, fn_call
;
796 tree mem
, fn
, nb_bytes
;
800 stmt
= DR_STMT (partition
->main_dr
);
801 loc
= gimple_location (stmt
);
803 /* The new statements will be placed before LOOP. */
804 gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
806 nb_bytes
= build_size_arg_loc (loc
, partition
->main_dr
, partition
->niter
,
807 partition
->plus_one
);
808 nb_bytes
= force_gimple_operand_gsi (&gsi
, nb_bytes
, true, NULL_TREE
,
809 false, GSI_CONTINUE_LINKING
);
810 mem
= build_addr_arg_loc (loc
, partition
->main_dr
, nb_bytes
);
811 mem
= force_gimple_operand_gsi (&gsi
, mem
, true, NULL_TREE
,
812 false, GSI_CONTINUE_LINKING
);
814 /* This exactly matches the pattern recognition in classify_partition. */
815 val
= gimple_assign_rhs1 (stmt
);
816 /* Handle constants like 0x15151515 and similarly
817 floating point constants etc. where all bytes are the same. */
818 int bytev
= const_with_all_bytes_same (val
);
820 val
= build_int_cst (integer_type_node
, bytev
);
821 else if (TREE_CODE (val
) == INTEGER_CST
)
822 val
= fold_convert (integer_type_node
, val
);
823 else if (!useless_type_conversion_p (integer_type_node
, TREE_TYPE (val
)))
825 tree tem
= make_ssa_name (integer_type_node
);
826 gimple cstmt
= gimple_build_assign_with_ops (NOP_EXPR
, tem
, val
);
827 gsi_insert_after (&gsi
, cstmt
, GSI_CONTINUE_LINKING
);
831 fn
= build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET
));
832 fn_call
= gimple_build_call (fn
, 3, mem
, val
, nb_bytes
);
833 gsi_insert_after (&gsi
, fn_call
, GSI_CONTINUE_LINKING
);
835 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
837 fprintf (dump_file
, "generated memset");
839 fprintf (dump_file
, " zero\n");
841 fprintf (dump_file
, "\n");
845 /* Generate a call to memcpy for PARTITION in LOOP. */
848 generate_memcpy_builtin (struct loop
*loop
, partition_t partition
)
850 gimple_stmt_iterator gsi
;
851 gimple stmt
, fn_call
;
852 tree dest
, src
, fn
, nb_bytes
;
854 enum built_in_function kind
;
856 stmt
= DR_STMT (partition
->main_dr
);
857 loc
= gimple_location (stmt
);
859 /* The new statements will be placed before LOOP. */
860 gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
862 nb_bytes
= build_size_arg_loc (loc
, partition
->main_dr
, partition
->niter
,
863 partition
->plus_one
);
864 nb_bytes
= force_gimple_operand_gsi (&gsi
, nb_bytes
, true, NULL_TREE
,
865 false, GSI_CONTINUE_LINKING
);
866 dest
= build_addr_arg_loc (loc
, partition
->main_dr
, nb_bytes
);
867 src
= build_addr_arg_loc (loc
, partition
->secondary_dr
, nb_bytes
);
868 if (ptr_derefs_may_alias_p (dest
, src
))
869 kind
= BUILT_IN_MEMMOVE
;
871 kind
= BUILT_IN_MEMCPY
;
873 dest
= force_gimple_operand_gsi (&gsi
, dest
, true, NULL_TREE
,
874 false, GSI_CONTINUE_LINKING
);
875 src
= force_gimple_operand_gsi (&gsi
, src
, true, NULL_TREE
,
876 false, GSI_CONTINUE_LINKING
);
877 fn
= build_fold_addr_expr (builtin_decl_implicit (kind
));
878 fn_call
= gimple_build_call (fn
, 3, dest
, src
, nb_bytes
);
879 gsi_insert_after (&gsi
, fn_call
, GSI_CONTINUE_LINKING
);
881 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
883 if (kind
== BUILT_IN_MEMCPY
)
884 fprintf (dump_file
, "generated memcpy\n");
886 fprintf (dump_file
, "generated memmove\n");
890 /* Remove and destroy the loop LOOP. */
893 destroy_loop (struct loop
*loop
)
895 unsigned nbbs
= loop
->num_nodes
;
896 edge exit
= single_exit (loop
);
897 basic_block src
= loop_preheader_edge (loop
)->src
, dest
= exit
->dest
;
901 bbs
= get_loop_body_in_dom_order (loop
);
903 redirect_edge_pred (exit
, src
);
904 exit
->flags
&= ~(EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
905 exit
->flags
|= EDGE_FALLTHRU
;
906 cancel_loop_tree (loop
);
907 rescan_loop_exit (exit
, false, true);
909 for (i
= 0; i
< nbbs
; i
++)
911 /* We have made sure to not leave any dangling uses of SSA
912 names defined in the loop. With the exception of virtuals.
913 Make sure we replace all uses of virtual defs that will remain
914 outside of the loop with the bare symbol as delete_basic_block
915 will release them. */
916 for (gphi_iterator gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
);
919 gphi
*phi
= gsi
.phi ();
920 if (virtual_operand_p (gimple_phi_result (phi
)))
921 mark_virtual_phi_result_for_renaming (phi
);
923 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]); !gsi_end_p (gsi
);
926 gimple stmt
= gsi_stmt (gsi
);
927 tree vdef
= gimple_vdef (stmt
);
928 if (vdef
&& TREE_CODE (vdef
) == SSA_NAME
)
929 mark_virtual_operand_for_renaming (vdef
);
931 delete_basic_block (bbs
[i
]);
935 set_immediate_dominator (CDI_DOMINATORS
, dest
,
936 recompute_dominator (CDI_DOMINATORS
, dest
));
939 /* Generates code for PARTITION. */
942 generate_code_for_partition (struct loop
*loop
,
943 partition_t partition
, bool copy_p
)
945 switch (partition
->kind
)
948 /* Reductions all have to be in the last partition. */
949 gcc_assert (!partition_reduction_p (partition
)
951 generate_loops_for_partition (loop
, partition
, copy_p
);
955 generate_memset_builtin (loop
, partition
);
959 generate_memcpy_builtin (loop
, partition
);
966 /* Common tail for partitions we turn into a call. If this was the last
967 partition for which we generate code, we have to destroy the loop. */
973 /* Returns a partition with all the statements needed for computing
974 the vertex V of the RDG, also including the loop exit conditions. */
977 build_rdg_partition_for_vertex (struct graph
*rdg
, int v
)
979 partition_t partition
= partition_alloc (NULL
, NULL
);
980 auto_vec
<int, 3> nodes
;
984 graphds_dfs (rdg
, &v
, 1, &nodes
, false, NULL
);
986 FOR_EACH_VEC_ELT (nodes
, i
, x
)
988 bitmap_set_bit (partition
->stmts
, x
);
989 bitmap_set_bit (partition
->loops
,
990 loop_containing_stmt (RDG_STMT (rdg
, x
))->num
);
996 /* Classifies the builtin kind we can generate for PARTITION of RDG and LOOP.
997 For the moment we detect only the memset zero pattern. */
1000 classify_partition (loop_p loop
, struct graph
*rdg
, partition_t partition
)
1005 data_reference_p single_load
, single_store
;
1006 bool volatiles_p
= false;
1007 bool plus_one
= false;
1009 partition
->kind
= PKIND_NORMAL
;
1010 partition
->main_dr
= NULL
;
1011 partition
->secondary_dr
= NULL
;
1012 partition
->niter
= NULL_TREE
;
1013 partition
->plus_one
= false;
1015 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, bi
)
1017 gimple stmt
= RDG_STMT (rdg
, i
);
1019 if (gimple_has_volatile_ops (stmt
))
1022 /* If the stmt has uses outside of the loop mark it as reduction. */
1023 if (stmt_has_scalar_dependences_outside_loop (loop
, stmt
))
1025 partition
->reduction_p
= true;
1030 /* Perform general partition disqualification for builtins. */
1032 || !flag_tree_loop_distribute_patterns
)
1035 /* Detect memset and memcpy. */
1037 single_store
= NULL
;
1038 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, bi
)
1040 gimple stmt
= RDG_STMT (rdg
, i
);
1041 data_reference_p dr
;
1044 if (gimple_code (stmt
) == GIMPLE_PHI
)
1047 /* Any scalar stmts are ok. */
1048 if (!gimple_vuse (stmt
))
1051 /* Otherwise just regular loads/stores. */
1052 if (!gimple_assign_single_p (stmt
))
1055 /* But exactly one store and/or load. */
1056 for (j
= 0; RDG_DATAREFS (rdg
, i
).iterate (j
, &dr
); ++j
)
1058 if (DR_IS_READ (dr
))
1060 if (single_load
!= NULL
)
1066 if (single_store
!= NULL
)
1076 nb_iter
= number_of_latch_executions (loop
);
1077 if (!nb_iter
|| nb_iter
== chrec_dont_know
)
1079 if (dominated_by_p (CDI_DOMINATORS
, single_exit (loop
)->src
,
1080 gimple_bb (DR_STMT (single_store
))))
1083 if (single_store
&& !single_load
)
1085 gimple stmt
= DR_STMT (single_store
);
1086 tree rhs
= gimple_assign_rhs1 (stmt
);
1087 if (const_with_all_bytes_same (rhs
) == -1
1088 && (!INTEGRAL_TYPE_P (TREE_TYPE (rhs
))
1089 || (TYPE_MODE (TREE_TYPE (rhs
))
1090 != TYPE_MODE (unsigned_char_type_node
))))
1092 if (TREE_CODE (rhs
) == SSA_NAME
1093 && !SSA_NAME_IS_DEFAULT_DEF (rhs
)
1094 && flow_bb_inside_loop_p (loop
, gimple_bb (SSA_NAME_DEF_STMT (rhs
))))
1096 if (!adjacent_dr_p (single_store
)
1097 || !dominated_by_p (CDI_DOMINATORS
,
1098 loop
->latch
, gimple_bb (stmt
)))
1100 partition
->kind
= PKIND_MEMSET
;
1101 partition
->main_dr
= single_store
;
1102 partition
->niter
= nb_iter
;
1103 partition
->plus_one
= plus_one
;
1105 else if (single_store
&& single_load
)
1107 gimple store
= DR_STMT (single_store
);
1108 gimple load
= DR_STMT (single_load
);
1109 /* Direct aggregate copy or via an SSA name temporary. */
1111 && gimple_assign_lhs (load
) != gimple_assign_rhs1 (store
))
1113 if (!adjacent_dr_p (single_store
)
1114 || !adjacent_dr_p (single_load
)
1115 || !operand_equal_p (DR_STEP (single_store
),
1116 DR_STEP (single_load
), 0)
1117 || !dominated_by_p (CDI_DOMINATORS
,
1118 loop
->latch
, gimple_bb (store
)))
1120 /* Now check that if there is a dependence this dependence is
1121 of a suitable form for memmove. */
1122 vec
<loop_p
> loops
= vNULL
;
1124 loops
.safe_push (loop
);
1125 ddr
= initialize_data_dependence_relation (single_load
, single_store
,
1127 compute_affine_dependence (ddr
, loop
);
1128 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
1130 free_dependence_relation (ddr
);
1134 if (DDR_ARE_DEPENDENT (ddr
) != chrec_known
)
1136 if (DDR_NUM_DIST_VECTS (ddr
) == 0)
1138 free_dependence_relation (ddr
);
1142 lambda_vector dist_v
;
1143 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
1145 int dist
= dist_v
[index_in_loop_nest (loop
->num
,
1146 DDR_LOOP_NEST (ddr
))];
1147 if (dist
> 0 && !DDR_REVERSED_P (ddr
))
1149 free_dependence_relation (ddr
);
1155 free_dependence_relation (ddr
);
1157 partition
->kind
= PKIND_MEMCPY
;
1158 partition
->main_dr
= single_store
;
1159 partition
->secondary_dr
= single_load
;
1160 partition
->niter
= nb_iter
;
1161 partition
->plus_one
= plus_one
;
1165 /* For a data reference REF, return the declaration of its base
1166 address or NULL_TREE if the base is not determined. */
1169 ref_base_address (data_reference_p dr
)
1171 tree base_address
= DR_BASE_ADDRESS (dr
);
1173 && TREE_CODE (base_address
) == ADDR_EXPR
)
1174 return TREE_OPERAND (base_address
, 0);
1176 return base_address
;
1179 /* Returns true when PARTITION1 and PARTITION2 have similar memory
1183 similar_memory_accesses (struct graph
*rdg
, partition_t partition1
,
1184 partition_t partition2
)
1186 unsigned i
, j
, k
, l
;
1187 bitmap_iterator bi
, bj
;
1188 data_reference_p ref1
, ref2
;
1190 /* First check whether in the intersection of the two partitions are
1191 any loads or stores. Common loads are the situation that happens
1193 EXECUTE_IF_AND_IN_BITMAP (partition1
->stmts
, partition2
->stmts
, 0, i
, bi
)
1194 if (RDG_MEM_WRITE_STMT (rdg
, i
)
1195 || RDG_MEM_READS_STMT (rdg
, i
))
1198 /* Then check all data-references against each other. */
1199 EXECUTE_IF_SET_IN_BITMAP (partition1
->stmts
, 0, i
, bi
)
1200 if (RDG_MEM_WRITE_STMT (rdg
, i
)
1201 || RDG_MEM_READS_STMT (rdg
, i
))
1202 EXECUTE_IF_SET_IN_BITMAP (partition2
->stmts
, 0, j
, bj
)
1203 if (RDG_MEM_WRITE_STMT (rdg
, j
)
1204 || RDG_MEM_READS_STMT (rdg
, j
))
1206 FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg
, i
), k
, ref1
)
1208 tree base1
= ref_base_address (ref1
);
1210 FOR_EACH_VEC_ELT (RDG_DATAREFS (rdg
, j
), l
, ref2
)
1211 if (base1
== ref_base_address (ref2
))
1219 /* Aggregate several components into a useful partition that is
1220 registered in the PARTITIONS vector. Partitions will be
1221 distributed in different loops. */
1224 rdg_build_partitions (struct graph
*rdg
,
1225 vec
<gimple
> starting_stmts
,
1226 vec
<partition_t
> *partitions
)
1228 bitmap processed
= BITMAP_ALLOC (NULL
);
1232 FOR_EACH_VEC_ELT (starting_stmts
, i
, stmt
)
1234 int v
= rdg_vertex_for_stmt (rdg
, stmt
);
1236 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1238 "ldist asked to generate code for vertex %d\n", v
);
1240 /* If the vertex is already contained in another partition so
1241 is the partition rooted at it. */
1242 if (bitmap_bit_p (processed
, v
))
1245 partition_t partition
= build_rdg_partition_for_vertex (rdg
, v
);
1246 bitmap_ior_into (processed
, partition
->stmts
);
1248 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1250 fprintf (dump_file
, "ldist useful partition:\n");
1251 dump_bitmap (dump_file
, partition
->stmts
);
1254 partitions
->safe_push (partition
);
1257 /* All vertices should have been assigned to at least one partition now,
1258 other than vertices belonging to dead code. */
1260 BITMAP_FREE (processed
);
1263 /* Dump to FILE the PARTITIONS. */
1266 dump_rdg_partitions (FILE *file
, vec
<partition_t
> partitions
)
1269 partition_t partition
;
1271 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1272 debug_bitmap_file (file
, partition
->stmts
);
1275 /* Debug PARTITIONS. */
1276 extern void debug_rdg_partitions (vec
<partition_t
> );
1279 debug_rdg_partitions (vec
<partition_t
> partitions
)
1281 dump_rdg_partitions (stderr
, partitions
);
1284 /* Returns the number of read and write operations in the RDG. */
1287 number_of_rw_in_rdg (struct graph
*rdg
)
1291 for (i
= 0; i
< rdg
->n_vertices
; i
++)
1293 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1296 if (RDG_MEM_READS_STMT (rdg
, i
))
1303 /* Returns the number of read and write operations in a PARTITION of
1307 number_of_rw_in_partition (struct graph
*rdg
, partition_t partition
)
1313 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, ii
)
1315 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1318 if (RDG_MEM_READS_STMT (rdg
, i
))
1325 /* Returns true when one of the PARTITIONS contains all the read or
1326 write operations of RDG. */
1329 partition_contains_all_rw (struct graph
*rdg
,
1330 vec
<partition_t
> partitions
)
1333 partition_t partition
;
1334 int nrw
= number_of_rw_in_rdg (rdg
);
1336 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1337 if (nrw
== number_of_rw_in_partition (rdg
, partition
))
1343 /* Compute partition dependence created by the data references in DRS1
1344 and DRS2 and modify and return DIR according to that. */
1347 pg_add_dependence_edges (struct graph
*rdg
, vec
<loop_p
> loops
, int dir
,
1348 vec
<data_reference_p
> drs1
,
1349 vec
<data_reference_p
> drs2
)
1351 data_reference_p dr1
, dr2
;
1353 /* dependence direction - 0 is no dependence, -1 is back,
1354 1 is forth, 2 is both (we can stop then, merging will occur). */
1355 for (int ii
= 0; drs1
.iterate (ii
, &dr1
); ++ii
)
1356 for (int jj
= 0; drs2
.iterate (jj
, &dr2
); ++jj
)
1360 /* Re-shuffle data-refs to be in dominator order. */
1361 if (rdg_vertex_for_stmt (rdg
, DR_STMT (dr1
))
1362 > rdg_vertex_for_stmt (rdg
, DR_STMT (dr2
)))
1364 data_reference_p tem
= dr1
;
1367 this_dir
= -this_dir
;
1369 ddr
= initialize_data_dependence_relation (dr1
, dr2
, loops
);
1370 compute_affine_dependence (ddr
, loops
[0]);
1371 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
1373 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1375 if (DDR_REVERSED_P (ddr
))
1377 data_reference_p tem
= dr1
;
1380 this_dir
= -this_dir
;
1382 /* Known dependences can still be unordered througout the
1383 iteration space, see gcc.dg/tree-ssa/ldist-16.c. */
1384 if (DDR_NUM_DIST_VECTS (ddr
) != 1)
1386 /* If the overlap is exact preserve stmt order. */
1387 else if (lambda_vector_zerop (DDR_DIST_VECT (ddr
, 0), 1))
1391 /* Else as the distance vector is lexicographic positive
1392 swap the dependence direction. */
1393 this_dir
= -this_dir
;
1398 free_dependence_relation (ddr
);
1401 else if (dir
!= this_dir
)
1407 /* Compare postorder number of the partition graph vertices V1 and V2. */
1410 pgcmp (const void *v1_
, const void *v2_
)
1412 const vertex
*v1
= (const vertex
*)v1_
;
1413 const vertex
*v2
= (const vertex
*)v2_
;
1414 return v2
->post
- v1
->post
;
1417 /* Distributes the code from LOOP in such a way that producer
1418 statements are placed before consumer statements. Tries to separate
1419 only the statements from STMTS into separate loops.
1420 Returns the number of distributed loops. */
1423 distribute_loop (struct loop
*loop
, vec
<gimple
> stmts
,
1424 control_dependences
*cd
, int *nb_calls
)
1427 partition_t partition
;
1434 auto_vec
<loop_p
, 3> loop_nest
;
1435 if (!find_loop_nest (loop
, &loop_nest
))
1438 rdg
= build_rdg (loop_nest
, cd
);
1441 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1443 "Loop %d not distributed: failed to build the RDG.\n",
1449 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1450 dump_rdg (dump_file
, rdg
);
1452 auto_vec
<partition_t
, 3> partitions
;
1453 rdg_build_partitions (rdg
, stmts
, &partitions
);
1455 any_builtin
= false;
1456 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1458 classify_partition (loop
, rdg
, partition
);
1459 any_builtin
|= partition_builtin_p (partition
);
1462 /* If we are only distributing patterns but did not detect any,
1464 if (!flag_tree_loop_distribution
1471 /* If we are only distributing patterns fuse all partitions that
1472 were not classified as builtins. This also avoids chopping
1473 a loop into pieces, separated by builtin calls. That is, we
1474 only want no or a single loop body remaining. */
1476 if (!flag_tree_loop_distribution
)
1478 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
1479 if (!partition_builtin_p (into
))
1481 for (++i
; partitions
.iterate (i
, &partition
); ++i
)
1482 if (!partition_builtin_p (partition
))
1484 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1486 fprintf (dump_file
, "fusing non-builtin partitions\n");
1487 dump_bitmap (dump_file
, into
->stmts
);
1488 dump_bitmap (dump_file
, partition
->stmts
);
1490 partition_merge_into (into
, partition
);
1491 partitions
.unordered_remove (i
);
1492 partition_free (partition
);
1497 /* Due to limitations in the transform phase we have to fuse all
1498 reduction partitions into the last partition so the existing
1499 loop will contain all loop-closed PHI nodes. */
1500 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
1501 if (partition_reduction_p (into
))
1503 for (i
= i
+ 1; partitions
.iterate (i
, &partition
); ++i
)
1504 if (partition_reduction_p (partition
))
1506 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1508 fprintf (dump_file
, "fusing partitions\n");
1509 dump_bitmap (dump_file
, into
->stmts
);
1510 dump_bitmap (dump_file
, partition
->stmts
);
1511 fprintf (dump_file
, "because they have reductions\n");
1513 partition_merge_into (into
, partition
);
1514 partitions
.unordered_remove (i
);
1515 partition_free (partition
);
1519 /* Apply our simple cost model - fuse partitions with similar
1521 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
1523 if (partition_builtin_p (into
))
1526 partitions
.iterate (j
, &partition
); ++j
)
1528 if (!partition_builtin_p (partition
)
1529 && similar_memory_accesses (rdg
, into
, partition
))
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
, partition
->stmts
);
1536 fprintf (dump_file
, "because they have similar "
1537 "memory accesses\n");
1539 partition_merge_into (into
, partition
);
1540 partitions
.unordered_remove (j
);
1541 partition_free (partition
);
1547 /* Build the partition dependency graph. */
1548 if (partitions
.length () > 1)
1550 pg
= new_graph (partitions
.length ());
1552 partition_t partition
;
1553 vec
<data_reference_p
> writes
;
1554 vec
<data_reference_p
> reads
;
1556 #define PGDATA(i) ((pgdata *)(pg->vertices[i].data))
1557 for (i
= 0; partitions
.iterate (i
, &partition
); ++i
)
1559 vertex
*v
= &pg
->vertices
[i
];
1560 pgdata
*data
= new pgdata
;
1561 data_reference_p dr
;
1562 /* FIXME - leaks. */
1566 data
->partition
= partition
;
1567 data
->reads
= vNULL
;
1568 data
->writes
= vNULL
;
1569 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, j
, bi
)
1570 for (int k
= 0; RDG_DATAREFS (rdg
, j
).iterate (k
, &dr
); ++k
)
1571 if (DR_IS_READ (dr
))
1572 data
->reads
.safe_push (dr
);
1574 data
->writes
.safe_push (dr
);
1576 partition_t partition1
, partition2
;
1577 for (i
= 0; partitions
.iterate (i
, &partition1
); ++i
)
1578 for (int j
= i
+ 1; partitions
.iterate (j
, &partition2
); ++j
)
1580 /* dependence direction - 0 is no dependence, -1 is back,
1581 1 is forth, 2 is both (we can stop then, merging will occur). */
1583 dir
= pg_add_dependence_edges (rdg
, loop_nest
, dir
,
1587 dir
= pg_add_dependence_edges (rdg
, loop_nest
, dir
,
1591 dir
= pg_add_dependence_edges (rdg
, loop_nest
, dir
,
1594 if (dir
== 1 || dir
== 2)
1595 add_edge (pg
, i
, j
);
1596 if (dir
== -1 || dir
== 2)
1597 add_edge (pg
, j
, i
);
1600 /* Add edges to the reduction partition (if any) to force it last. */
1602 for (j
= 0; partitions
.iterate (j
, &partition
); ++j
)
1603 if (partition_reduction_p (partition
))
1605 if (j
< partitions
.length ())
1607 for (unsigned i
= 0; partitions
.iterate (i
, &partition
); ++i
)
1609 add_edge (pg
, i
, j
);
1612 /* Compute partitions we cannot separate and fuse them. */
1613 num_sccs
= graphds_scc (pg
, NULL
);
1614 for (i
= 0; i
< num_sccs
; ++i
)
1618 for (j
= 0; partitions
.iterate (j
, &first
); ++j
)
1619 if (pg
->vertices
[j
].component
== i
)
1621 for (j
= j
+ 1; partitions
.iterate (j
, &partition
); ++j
)
1622 if (pg
->vertices
[j
].component
== i
)
1624 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1626 fprintf (dump_file
, "fusing partitions\n");
1627 dump_bitmap (dump_file
, first
->stmts
);
1628 dump_bitmap (dump_file
, partition
->stmts
);
1629 fprintf (dump_file
, "because they are in the same "
1630 "dependence SCC\n");
1632 partition_merge_into (first
, partition
);
1633 partitions
[j
] = NULL
;
1634 partition_free (partition
);
1635 PGDATA (j
)->partition
= NULL
;
1639 /* Now order the remaining nodes in postorder. */
1640 qsort (pg
->vertices
, pg
->n_vertices
, sizeof (vertex
), pgcmp
);
1641 partitions
.truncate (0);
1642 for (i
= 0; i
< pg
->n_vertices
; ++i
)
1644 pgdata
*data
= PGDATA (i
);
1645 if (data
->partition
)
1646 partitions
.safe_push (data
->partition
);
1647 data
->reads
.release ();
1648 data
->writes
.release ();
1651 gcc_assert (partitions
.length () == (unsigned)num_sccs
);
1655 nbp
= partitions
.length ();
1657 || (nbp
== 1 && !partition_builtin_p (partitions
[0]))
1658 || (nbp
> 1 && partition_contains_all_rw (rdg
, partitions
)))
1664 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1665 dump_rdg_partitions (dump_file
, partitions
);
1667 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1669 if (partition_builtin_p (partition
))
1671 generate_code_for_partition (loop
, partition
, i
< nbp
- 1);
1676 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1677 partition_free (partition
);
1680 return nbp
- *nb_calls
;
1683 /* Distribute all loops in the current function. */
1687 const pass_data pass_data_loop_distribution
=
1689 GIMPLE_PASS
, /* type */
1691 OPTGROUP_LOOP
, /* optinfo_flags */
1692 TV_TREE_LOOP_DISTRIBUTION
, /* tv_id */
1693 ( PROP_cfg
| PROP_ssa
), /* properties_required */
1694 0, /* properties_provided */
1695 0, /* properties_destroyed */
1696 0, /* todo_flags_start */
1697 0, /* todo_flags_finish */
1700 class pass_loop_distribution
: public gimple_opt_pass
1703 pass_loop_distribution (gcc::context
*ctxt
)
1704 : gimple_opt_pass (pass_data_loop_distribution
, ctxt
)
1707 /* opt_pass methods: */
1708 virtual bool gate (function
*)
1710 return flag_tree_loop_distribution
1711 || flag_tree_loop_distribute_patterns
;
1714 virtual unsigned int execute (function
*);
1716 }; // class pass_loop_distribution
1719 pass_loop_distribution::execute (function
*fun
)
1722 bool changed
= false;
1724 control_dependences
*cd
= NULL
;
1726 FOR_ALL_BB_FN (bb
, fun
)
1728 gimple_stmt_iterator gsi
;
1729 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1730 gimple_set_uid (gsi_stmt (gsi
), -1);
1731 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1732 gimple_set_uid (gsi_stmt (gsi
), -1);
1735 /* We can at the moment only distribute non-nested loops, thus restrict
1736 walking to innermost loops. */
1737 FOR_EACH_LOOP (loop
, LI_ONLY_INNERMOST
)
1739 auto_vec
<gimple
> work_list
;
1741 int num
= loop
->num
;
1744 /* If the loop doesn't have a single exit we will fail anyway,
1745 so do that early. */
1746 if (!single_exit (loop
))
1749 /* Only optimize hot loops. */
1750 if (!optimize_loop_for_speed_p (loop
))
1753 /* Initialize the worklist with stmts we seed the partitions with. */
1754 bbs
= get_loop_body_in_dom_order (loop
);
1755 for (i
= 0; i
< loop
->num_nodes
; ++i
)
1757 for (gphi_iterator gsi
= gsi_start_phis (bbs
[i
]);
1761 gphi
*phi
= gsi
.phi ();
1762 if (virtual_operand_p (gimple_phi_result (phi
)))
1764 /* Distribute stmts which have defs that are used outside of
1766 if (!stmt_has_scalar_dependences_outside_loop (loop
, phi
))
1768 work_list
.safe_push (phi
);
1770 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]);
1774 gimple stmt
= gsi_stmt (gsi
);
1776 /* If there is a stmt with side-effects bail out - we
1777 cannot and should not distribute this loop. */
1778 if (gimple_has_side_effects (stmt
))
1780 work_list
.truncate (0);
1784 /* Distribute stmts which have defs that are used outside of
1786 if (stmt_has_scalar_dependences_outside_loop (loop
, stmt
))
1788 /* Otherwise only distribute stores for now. */
1789 else if (!gimple_vdef (stmt
))
1792 work_list
.safe_push (stmt
);
1798 int nb_generated_loops
= 0;
1799 int nb_generated_calls
= 0;
1800 location_t loc
= find_loop_location (loop
);
1801 if (work_list
.length () > 0)
1805 calculate_dominance_info (CDI_DOMINATORS
);
1806 calculate_dominance_info (CDI_POST_DOMINATORS
);
1807 cd
= new control_dependences (create_edge_list ());
1808 free_dominance_info (CDI_POST_DOMINATORS
);
1810 nb_generated_loops
= distribute_loop (loop
, work_list
, cd
,
1811 &nb_generated_calls
);
1814 if (nb_generated_loops
+ nb_generated_calls
> 0)
1817 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
,
1818 loc
, "Loop %d distributed: split to %d loops "
1819 "and %d library calls.\n",
1820 num
, nb_generated_loops
, nb_generated_calls
);
1822 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1823 fprintf (dump_file
, "Loop %d is the same.\n", num
);
1831 mark_virtual_operands_for_renaming (fun
);
1832 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
1835 #ifdef ENABLE_CHECKING
1836 verify_loop_structure ();
1845 make_pass_loop_distribution (gcc::context
*ctxt
)
1847 return new pass_loop_distribution (ctxt
);