2 Copyright (C) 2006-2019 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 Loop distribution is the dual of loop fusion. It separates statements
40 of a loop (or loop nest) into multiple loops (or loop nests) with the
41 same loop header. The major goal is to separate statements which may
42 be vectorized from those that can't. This pass implements distribution
43 in the following steps:
45 1) Seed partitions with specific type statements. For now we support
46 two types seed statements: statement defining variable used outside
47 of loop; statement storing to memory.
48 2) Build reduced dependence graph (RDG) for loop to be distributed.
49 The vertices (RDG:V) model all statements in the loop and the edges
50 (RDG:E) model flow and control dependencies between statements.
51 3) Apart from RDG, compute data dependencies between memory references.
52 4) Starting from seed statement, build up partition by adding depended
53 statements according to RDG's dependence information. Partition is
54 classified as parallel type if it can be executed paralleled; or as
55 sequential type if it can't. Parallel type partition is further
56 classified as different builtin kinds if it can be implemented as
57 builtin function calls.
58 5) Build partition dependence graph (PG) based on data dependencies.
59 The vertices (PG:V) model all partitions and the edges (PG:E) model
60 all data dependencies between every partitions pair. In general,
61 data dependence is either compilation time known or unknown. In C
62 family languages, there exists quite amount compilation time unknown
63 dependencies because of possible alias relation of data references.
64 We categorize PG's edge to two types: "true" edge that represents
65 compilation time known data dependencies; "alias" edge for all other
67 6) Traverse subgraph of PG as if all "alias" edges don't exist. Merge
68 partitions in each strong connected component (SCC) correspondingly.
69 Build new PG for merged partitions.
70 7) Traverse PG again and this time with both "true" and "alias" edges
71 included. We try to break SCCs by removing some edges. Because
72 SCCs by "true" edges are all fused in step 6), we can break SCCs
73 by removing some "alias" edges. It's NP-hard to choose optimal
74 edge set, fortunately simple approximation is good enough for us
75 given the small problem scale.
76 8) Collect all data dependencies of the removed "alias" edges. Create
77 runtime alias checks for collected data dependencies.
78 9) Version loop under the condition of runtime alias checks. Given
79 loop distribution generally introduces additional overhead, it is
80 only useful if vectorization is achieved in distributed loop. We
81 version loop with internal function call IFN_LOOP_DIST_ALIAS. If
82 no distributed loop can be vectorized, we simply remove distributed
83 loops and recover to the original one.
86 1) We only distribute innermost two-level loop nest now. We should
87 extend it for arbitrary loop nests in the future.
88 2) We only fuse partitions in SCC now. A better fusion algorithm is
89 desired to minimize loop overhead, maximize parallelism and maximize
94 #include "coretypes.h"
99 #include "tree-pass.h"
101 #include "gimple-pretty-print.h"
102 #include "fold-const.h"
104 #include "gimple-iterator.h"
105 #include "gimplify-me.h"
106 #include "stor-layout.h"
107 #include "tree-cfg.h"
108 #include "tree-ssa-loop-manip.h"
109 #include "tree-ssa-loop-ivopts.h"
110 #include "tree-ssa-loop.h"
111 #include "tree-into-ssa.h"
112 #include "tree-ssa.h"
114 #include "tree-scalar-evolution.h"
116 #include "tree-vectorizer.h"
120 #define MAX_DATAREFS_NUM \
121 ((unsigned) PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS))
123 /* Threshold controlling number of distributed partitions. Given it may
124 be unnecessary if a memory stream cost model is invented in the future,
125 we define it as a temporary macro, rather than a parameter. */
126 #define NUM_PARTITION_THRESHOLD (4)
128 /* Hashtable helpers. */
130 struct ddr_hasher
: nofree_ptr_hash
<struct data_dependence_relation
>
132 static inline hashval_t
hash (const data_dependence_relation
*);
133 static inline bool equal (const data_dependence_relation
*,
134 const data_dependence_relation
*);
137 /* Hash function for data dependence. */
140 ddr_hasher::hash (const data_dependence_relation
*ddr
)
143 h
.add_ptr (DDR_A (ddr
));
144 h
.add_ptr (DDR_B (ddr
));
148 /* Hash table equality function for data dependence. */
151 ddr_hasher::equal (const data_dependence_relation
*ddr1
,
152 const data_dependence_relation
*ddr2
)
154 return (DDR_A (ddr1
) == DDR_A (ddr2
) && DDR_B (ddr1
) == DDR_B (ddr2
));
157 /* The loop (nest) to be distributed. */
158 static vec
<loop_p
> loop_nest
;
160 /* Vector of data references in the loop to be distributed. */
161 static vec
<data_reference_p
> datarefs_vec
;
163 /* If there is nonaddressable data reference in above vector. */
164 static bool has_nonaddressable_dataref_p
;
166 /* Store index of data reference in aux field. */
167 #define DR_INDEX(dr) ((uintptr_t) (dr)->aux)
169 /* Hash table for data dependence relation in the loop to be distributed. */
170 static hash_table
<ddr_hasher
> *ddrs_table
;
172 /* A Reduced Dependence Graph (RDG) vertex representing a statement. */
175 /* The statement represented by this vertex. */
178 /* Vector of data-references in this statement. */
179 vec
<data_reference_p
> datarefs
;
181 /* True when the statement contains a write to memory. */
184 /* True when the statement contains a read from memory. */
188 #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
189 #define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs
190 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
191 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
192 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
193 #define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I]))
194 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
195 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
197 /* Data dependence type. */
201 /* Read After Write (RAW). */
204 /* Control dependence (execute conditional on). */
208 /* Dependence information attached to an edge of the RDG. */
212 /* Type of the dependence. */
213 enum rdg_dep_type type
;
216 #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
218 /* Dump vertex I in RDG to FILE. */
221 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
223 struct vertex
*v
= &(rdg
->vertices
[i
]);
224 struct graph_edge
*e
;
226 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
227 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
228 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
231 for (e
= v
->pred
; e
; e
= e
->pred_next
)
232 fprintf (file
, " %d", e
->src
);
234 fprintf (file
, ") (out:");
237 for (e
= v
->succ
; e
; e
= e
->succ_next
)
238 fprintf (file
, " %d", e
->dest
);
240 fprintf (file
, ")\n");
241 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
242 fprintf (file
, ")\n");
245 /* Call dump_rdg_vertex on stderr. */
248 debug_rdg_vertex (struct graph
*rdg
, int i
)
250 dump_rdg_vertex (stderr
, rdg
, i
);
253 /* Dump the reduced dependence graph RDG to FILE. */
256 dump_rdg (FILE *file
, struct graph
*rdg
)
258 fprintf (file
, "(rdg\n");
259 for (int i
= 0; i
< rdg
->n_vertices
; i
++)
260 dump_rdg_vertex (file
, rdg
, i
);
261 fprintf (file
, ")\n");
264 /* Call dump_rdg on stderr. */
267 debug_rdg (struct graph
*rdg
)
269 dump_rdg (stderr
, rdg
);
273 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
276 pretty_printer buffer
;
277 pp_needs_newline (&buffer
) = false;
278 buffer
.buffer
->stream
= file
;
280 fprintf (file
, "digraph RDG {\n");
282 for (i
= 0; i
< rdg
->n_vertices
; i
++)
284 struct vertex
*v
= &(rdg
->vertices
[i
]);
285 struct graph_edge
*e
;
287 fprintf (file
, "%d [label=\"[%d] ", i
, i
);
288 pp_gimple_stmt_1 (&buffer
, RDGV_STMT (v
), 0, TDF_SLIM
);
290 fprintf (file
, "\"]\n");
292 /* Highlight reads from memory. */
293 if (RDG_MEM_READS_STMT (rdg
, i
))
294 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
296 /* Highlight stores to memory. */
297 if (RDG_MEM_WRITE_STMT (rdg
, i
))
298 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
301 for (e
= v
->succ
; e
; e
= e
->succ_next
)
302 switch (RDGE_TYPE (e
))
305 /* These are the most common dependences: don't print these. */
306 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
310 fprintf (file
, "%d -> %d [label=control] \n", i
, e
->dest
);
318 fprintf (file
, "}\n\n");
321 /* Display the Reduced Dependence Graph using dotty. */
324 dot_rdg (struct graph
*rdg
)
326 /* When debugging, you may want to enable the following code. */
328 FILE *file
= popen ("dot -Tx11", "w");
331 dot_rdg_1 (file
, rdg
);
333 close (fileno (file
));
336 dot_rdg_1 (stderr
, rdg
);
340 /* Returns the index of STMT in RDG. */
343 rdg_vertex_for_stmt (struct graph
*rdg ATTRIBUTE_UNUSED
, gimple
*stmt
)
345 int index
= gimple_uid (stmt
);
346 gcc_checking_assert (index
== -1 || RDG_STMT (rdg
, index
) == stmt
);
350 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
351 the index of DEF in RDG. */
354 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
356 use_operand_p imm_use_p
;
357 imm_use_iterator iterator
;
359 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
361 struct graph_edge
*e
;
362 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
367 e
= add_edge (rdg
, idef
, use
);
368 e
->data
= XNEW (struct rdg_edge
);
369 RDGE_TYPE (e
) = flow_dd
;
373 /* Creates an edge for the control dependences of BB to the vertex V. */
376 create_edge_for_control_dependence (struct graph
*rdg
, basic_block bb
,
377 int v
, control_dependences
*cd
)
381 EXECUTE_IF_SET_IN_BITMAP (cd
->get_edges_dependent_on (bb
->index
),
384 basic_block cond_bb
= cd
->get_edge_src (edge_n
);
385 gimple
*stmt
= last_stmt (cond_bb
);
386 if (stmt
&& is_ctrl_stmt (stmt
))
388 struct graph_edge
*e
;
389 int c
= rdg_vertex_for_stmt (rdg
, stmt
);
393 e
= add_edge (rdg
, c
, v
);
394 e
->data
= XNEW (struct rdg_edge
);
395 RDGE_TYPE (e
) = control_dd
;
400 /* Creates the edges of the reduced dependence graph RDG. */
403 create_rdg_flow_edges (struct graph
*rdg
)
409 for (i
= 0; i
< rdg
->n_vertices
; i
++)
410 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
412 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
415 /* Creates the edges of the reduced dependence graph RDG. */
418 create_rdg_cd_edges (struct graph
*rdg
, control_dependences
*cd
, loop_p loop
)
422 for (i
= 0; i
< rdg
->n_vertices
; i
++)
424 gimple
*stmt
= RDG_STMT (rdg
, i
);
425 if (gimple_code (stmt
) == GIMPLE_PHI
)
429 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->preds
)
430 if (flow_bb_inside_loop_p (loop
, e
->src
))
431 create_edge_for_control_dependence (rdg
, e
->src
, i
, cd
);
434 create_edge_for_control_dependence (rdg
, gimple_bb (stmt
), i
, cd
);
438 /* Build the vertices of the reduced dependence graph RDG. Return false
442 create_rdg_vertices (struct graph
*rdg
, vec
<gimple
*> stmts
, loop_p loop
)
447 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
449 struct vertex
*v
= &(rdg
->vertices
[i
]);
451 /* Record statement to vertex mapping. */
452 gimple_set_uid (stmt
, i
);
454 v
->data
= XNEW (struct rdg_vertex
);
455 RDGV_STMT (v
) = stmt
;
456 RDGV_DATAREFS (v
).create (0);
457 RDGV_HAS_MEM_WRITE (v
) = false;
458 RDGV_HAS_MEM_READS (v
) = false;
459 if (gimple_code (stmt
) == GIMPLE_PHI
)
462 unsigned drp
= datarefs_vec
.length ();
463 if (!find_data_references_in_stmt (loop
, stmt
, &datarefs_vec
))
465 for (unsigned j
= drp
; j
< datarefs_vec
.length (); ++j
)
467 data_reference_p dr
= datarefs_vec
[j
];
469 RDGV_HAS_MEM_READS (v
) = true;
471 RDGV_HAS_MEM_WRITE (v
) = true;
472 RDGV_DATAREFS (v
).safe_push (dr
);
473 has_nonaddressable_dataref_p
|= may_be_nonaddressable_p (dr
->ref
);
479 /* Array mapping basic block's index to its topological order. */
480 static int *bb_top_order_index
;
481 /* And size of the array. */
482 static int bb_top_order_index_size
;
484 /* If X has a smaller topological sort number than Y, returns -1;
485 if greater, returns 1. */
488 bb_top_order_cmp (const void *x
, const void *y
)
490 basic_block bb1
= *(const basic_block
*) x
;
491 basic_block bb2
= *(const basic_block
*) y
;
493 gcc_assert (bb1
->index
< bb_top_order_index_size
494 && bb2
->index
< bb_top_order_index_size
);
495 gcc_assert (bb1
== bb2
496 || bb_top_order_index
[bb1
->index
]
497 != bb_top_order_index
[bb2
->index
]);
499 return (bb_top_order_index
[bb1
->index
] - bb_top_order_index
[bb2
->index
]);
502 /* Initialize STMTS with all the statements of LOOP. We use topological
503 order to discover all statements. The order is important because
504 generate_loops_for_partition is using the same traversal for identifying
505 statements in loop copies. */
508 stmts_from_loop (struct loop
*loop
, vec
<gimple
*> *stmts
)
511 basic_block
*bbs
= get_loop_body_in_custom_order (loop
, bb_top_order_cmp
);
513 for (i
= 0; i
< loop
->num_nodes
; i
++)
515 basic_block bb
= bbs
[i
];
517 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
519 if (!virtual_operand_p (gimple_phi_result (bsi
.phi ())))
520 stmts
->safe_push (bsi
.phi ());
522 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
525 gimple
*stmt
= gsi_stmt (bsi
);
526 if (gimple_code (stmt
) != GIMPLE_LABEL
&& !is_gimple_debug (stmt
))
527 stmts
->safe_push (stmt
);
534 /* Free the reduced dependence graph RDG. */
537 free_rdg (struct graph
*rdg
)
541 for (i
= 0; i
< rdg
->n_vertices
; i
++)
543 struct vertex
*v
= &(rdg
->vertices
[i
]);
544 struct graph_edge
*e
;
546 for (e
= v
->succ
; e
; e
= e
->succ_next
)
551 gimple_set_uid (RDGV_STMT (v
), -1);
552 (RDGV_DATAREFS (v
)).release ();
560 /* Build the Reduced Dependence Graph (RDG) with one vertex per statement of
561 LOOP, and one edge per flow dependence or control dependence from control
562 dependence CD. During visiting each statement, data references are also
563 collected and recorded in global data DATAREFS_VEC. */
565 static struct graph
*
566 build_rdg (struct loop
*loop
, control_dependences
*cd
)
570 /* Create the RDG vertices from the stmts of the loop nest. */
571 auto_vec
<gimple
*, 10> stmts
;
572 stmts_from_loop (loop
, &stmts
);
573 rdg
= new_graph (stmts
.length ());
574 if (!create_rdg_vertices (rdg
, stmts
, loop
))
581 create_rdg_flow_edges (rdg
);
583 create_rdg_cd_edges (rdg
, cd
, loop
);
589 /* Kind of distributed loop. */
590 enum partition_kind
{
592 /* Partial memset stands for a paritition can be distributed into a loop
593 of memset calls, rather than a single memset call. It's handled just
594 like a normal parition, i.e, distributed as separate loop, no memset
597 Note: This is a hacking fix trying to distribute ZERO-ing stmt in a
598 loop nest as deep as possible. As a result, parloop achieves better
599 parallelization by parallelizing deeper loop nest. This hack should
600 be unnecessary and removed once distributed memset can be understood
601 and analyzed in data reference analysis. See PR82604 for more. */
602 PKIND_PARTIAL_MEMSET
,
603 PKIND_MEMSET
, PKIND_MEMCPY
, PKIND_MEMMOVE
606 /* Type of distributed loop. */
607 enum partition_type
{
608 /* The distributed loop can be executed parallelly. */
610 /* The distributed loop has to be executed sequentially. */
614 /* Builtin info for loop distribution. */
617 /* data-references a kind != PKIND_NORMAL partition is about. */
618 data_reference_p dst_dr
;
619 data_reference_p src_dr
;
620 /* Base address and size of memory objects operated by the builtin. Note
621 both dest and source memory objects must have the same size. */
625 /* Base and offset part of dst_base after stripping constant offset. This
626 is only used in memset builtin distribution for now. */
628 unsigned HOST_WIDE_INT dst_base_offset
;
631 /* Partition for loop distribution. */
634 /* Statements of the partition. */
636 /* True if the partition defines variable which is used outside of loop. */
638 enum partition_kind kind
;
639 enum partition_type type
;
640 /* Data references in the partition. */
642 /* Information of builtin parition. */
643 struct builtin_info
*builtin
;
647 /* Allocate and initialize a partition from BITMAP. */
650 partition_alloc (void)
652 partition
*partition
= XCNEW (struct partition
);
653 partition
->stmts
= BITMAP_ALLOC (NULL
);
654 partition
->reduction_p
= false;
655 partition
->kind
= PKIND_NORMAL
;
656 partition
->datarefs
= BITMAP_ALLOC (NULL
);
660 /* Free PARTITION. */
663 partition_free (partition
*partition
)
665 BITMAP_FREE (partition
->stmts
);
666 BITMAP_FREE (partition
->datarefs
);
667 if (partition
->builtin
)
668 free (partition
->builtin
);
673 /* Returns true if the partition can be generated as a builtin. */
676 partition_builtin_p (partition
*partition
)
678 return partition
->kind
> PKIND_PARTIAL_MEMSET
;
681 /* Returns true if the partition contains a reduction. */
684 partition_reduction_p (partition
*partition
)
686 return partition
->reduction_p
;
689 /* Partitions are fused because of different reasons. */
692 FUSE_NON_BUILTIN
= 0,
699 /* Description on different fusing reason. */
700 static const char *fuse_message
[] = {
701 "they are non-builtins",
702 "they have reductions",
703 "they have shared memory refs",
704 "they are in the same dependence scc",
705 "there is no point to distribute loop"};
708 update_type_for_merge (struct graph
*, partition
*, partition
*);
710 /* Merge PARTITION into the partition DEST. RDG is the reduced dependence
711 graph and we update type for result partition if it is non-NULL. */
714 partition_merge_into (struct graph
*rdg
, partition
*dest
,
715 partition
*partition
, enum fuse_type ft
)
717 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
719 fprintf (dump_file
, "Fuse partitions because %s:\n", fuse_message
[ft
]);
720 fprintf (dump_file
, " Part 1: ");
721 dump_bitmap (dump_file
, dest
->stmts
);
722 fprintf (dump_file
, " Part 2: ");
723 dump_bitmap (dump_file
, partition
->stmts
);
726 dest
->kind
= PKIND_NORMAL
;
727 if (dest
->type
== PTYPE_PARALLEL
)
728 dest
->type
= partition
->type
;
730 bitmap_ior_into (dest
->stmts
, partition
->stmts
);
731 if (partition_reduction_p (partition
))
732 dest
->reduction_p
= true;
734 /* Further check if any data dependence prevents us from executing the
735 new partition parallelly. */
736 if (dest
->type
== PTYPE_PARALLEL
&& rdg
!= NULL
)
737 update_type_for_merge (rdg
, dest
, partition
);
739 bitmap_ior_into (dest
->datarefs
, partition
->datarefs
);
743 /* Returns true when DEF is an SSA_NAME defined in LOOP and used after
747 ssa_name_has_uses_outside_loop_p (tree def
, loop_p loop
)
749 imm_use_iterator imm_iter
;
752 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
754 if (is_gimple_debug (USE_STMT (use_p
)))
757 basic_block use_bb
= gimple_bb (USE_STMT (use_p
));
758 if (!flow_bb_inside_loop_p (loop
, use_bb
))
765 /* Returns true when STMT defines a scalar variable used after the
769 stmt_has_scalar_dependences_outside_loop (loop_p loop
, gimple
*stmt
)
774 if (gimple_code (stmt
) == GIMPLE_PHI
)
775 return ssa_name_has_uses_outside_loop_p (gimple_phi_result (stmt
), loop
);
777 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
778 if (ssa_name_has_uses_outside_loop_p (DEF_FROM_PTR (def_p
), loop
))
784 /* Return a copy of LOOP placed before LOOP. */
787 copy_loop_before (struct loop
*loop
)
790 edge preheader
= loop_preheader_edge (loop
);
792 initialize_original_copy_tables ();
793 res
= slpeel_tree_duplicate_loop_to_edge_cfg (loop
, NULL
, preheader
);
794 gcc_assert (res
!= NULL
);
795 free_original_copy_tables ();
796 delete_update_ssa ();
801 /* Creates an empty basic block after LOOP. */
804 create_bb_after_loop (struct loop
*loop
)
806 edge exit
= single_exit (loop
);
814 /* Generate code for PARTITION from the code in LOOP. The loop is
815 copied when COPY_P is true. All the statements not flagged in the
816 PARTITION bitmap are removed from the loop or from its copy. The
817 statements are indexed in sequence inside a basic block, and the
818 basic blocks of a loop are taken in dom order. */
821 generate_loops_for_partition (struct loop
*loop
, partition
*partition
,
829 int orig_loop_num
= loop
->orig_loop_num
;
830 loop
= copy_loop_before (loop
);
831 gcc_assert (loop
!= NULL
);
832 loop
->orig_loop_num
= orig_loop_num
;
833 create_preheader (loop
, CP_SIMPLE_PREHEADERS
);
834 create_bb_after_loop (loop
);
838 /* Origin number is set to the new versioned loop's num. */
839 gcc_assert (loop
->orig_loop_num
!= loop
->num
);
842 /* Remove stmts not in the PARTITION bitmap. */
843 bbs
= get_loop_body_in_dom_order (loop
);
845 if (MAY_HAVE_DEBUG_BIND_STMTS
)
846 for (i
= 0; i
< loop
->num_nodes
; i
++)
848 basic_block bb
= bbs
[i
];
850 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
853 gphi
*phi
= bsi
.phi ();
854 if (!virtual_operand_p (gimple_phi_result (phi
))
855 && !bitmap_bit_p (partition
->stmts
, gimple_uid (phi
)))
856 reset_debug_uses (phi
);
859 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
861 gimple
*stmt
= gsi_stmt (bsi
);
862 if (gimple_code (stmt
) != GIMPLE_LABEL
863 && !is_gimple_debug (stmt
)
864 && !bitmap_bit_p (partition
->stmts
, gimple_uid (stmt
)))
865 reset_debug_uses (stmt
);
869 for (i
= 0; i
< loop
->num_nodes
; i
++)
871 basic_block bb
= bbs
[i
];
872 edge inner_exit
= NULL
;
874 if (loop
!= bb
->loop_father
)
875 inner_exit
= single_exit (bb
->loop_father
);
877 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);)
879 gphi
*phi
= bsi
.phi ();
880 if (!virtual_operand_p (gimple_phi_result (phi
))
881 && !bitmap_bit_p (partition
->stmts
, gimple_uid (phi
)))
882 remove_phi_node (&bsi
, true);
887 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);)
889 gimple
*stmt
= gsi_stmt (bsi
);
890 if (gimple_code (stmt
) != GIMPLE_LABEL
891 && !is_gimple_debug (stmt
)
892 && !bitmap_bit_p (partition
->stmts
, gimple_uid (stmt
)))
894 /* In distribution of loop nest, if bb is inner loop's exit_bb,
895 we choose its exit edge/path in order to avoid generating
896 infinite loop. For all other cases, we choose an arbitrary
897 path through the empty CFG part that this unnecessary
898 control stmt controls. */
899 if (gcond
*cond_stmt
= dyn_cast
<gcond
*> (stmt
))
901 if (inner_exit
&& inner_exit
->flags
& EDGE_TRUE_VALUE
)
902 gimple_cond_make_true (cond_stmt
);
904 gimple_cond_make_false (cond_stmt
);
907 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
909 gswitch
*switch_stmt
= as_a
<gswitch
*> (stmt
);
910 gimple_switch_set_index
911 (switch_stmt
, CASE_LOW (gimple_switch_label (switch_stmt
, 1)));
916 unlink_stmt_vdef (stmt
);
917 gsi_remove (&bsi
, true);
929 /* If VAL memory representation contains the same value in all bytes,
930 return that value, otherwise return -1.
931 E.g. for 0x24242424 return 0x24, for IEEE double
932 747708026454360457216.0 return 0x44, etc. */
935 const_with_all_bytes_same (tree val
)
937 unsigned char buf
[64];
940 if (integer_zerop (val
)
941 || (TREE_CODE (val
) == CONSTRUCTOR
942 && !TREE_CLOBBER_P (val
)
943 && CONSTRUCTOR_NELTS (val
) == 0))
946 if (real_zerop (val
))
948 /* Only return 0 for +0.0, not for -0.0, which doesn't have
949 an all bytes same memory representation. Don't transform
950 -0.0 stores into +0.0 even for !HONOR_SIGNED_ZEROS. */
951 switch (TREE_CODE (val
))
954 if (!real_isneg (TREE_REAL_CST_PTR (val
)))
958 if (!const_with_all_bytes_same (TREE_REALPART (val
))
959 && !const_with_all_bytes_same (TREE_IMAGPART (val
)))
964 unsigned int count
= vector_cst_encoded_nelts (val
);
966 for (j
= 0; j
< count
; ++j
)
967 if (const_with_all_bytes_same (VECTOR_CST_ENCODED_ELT (val
, j
)))
978 if (CHAR_BIT
!= 8 || BITS_PER_UNIT
!= 8)
981 len
= native_encode_expr (val
, buf
, sizeof (buf
));
984 for (i
= 1; i
< len
; i
++)
985 if (buf
[i
] != buf
[0])
990 /* Generate a call to memset for PARTITION in LOOP. */
993 generate_memset_builtin (struct loop
*loop
, partition
*partition
)
995 gimple_stmt_iterator gsi
;
996 tree mem
, fn
, nb_bytes
;
998 struct builtin_info
*builtin
= partition
->builtin
;
1001 /* The new statements will be placed before LOOP. */
1002 gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
1004 nb_bytes
= rewrite_to_non_trapping_overflow (builtin
->size
);
1005 nb_bytes
= force_gimple_operand_gsi (&gsi
, nb_bytes
, true, NULL_TREE
,
1006 false, GSI_CONTINUE_LINKING
);
1007 mem
= builtin
->dst_base
;
1008 mem
= force_gimple_operand_gsi (&gsi
, mem
, true, NULL_TREE
,
1009 false, GSI_CONTINUE_LINKING
);
1011 /* This exactly matches the pattern recognition in classify_partition. */
1012 val
= gimple_assign_rhs1 (DR_STMT (builtin
->dst_dr
));
1013 /* Handle constants like 0x15151515 and similarly
1014 floating point constants etc. where all bytes are the same. */
1015 int bytev
= const_with_all_bytes_same (val
);
1017 val
= build_int_cst (integer_type_node
, bytev
);
1018 else if (TREE_CODE (val
) == INTEGER_CST
)
1019 val
= fold_convert (integer_type_node
, val
);
1020 else if (!useless_type_conversion_p (integer_type_node
, TREE_TYPE (val
)))
1022 tree tem
= make_ssa_name (integer_type_node
);
1023 gimple
*cstmt
= gimple_build_assign (tem
, NOP_EXPR
, val
);
1024 gsi_insert_after (&gsi
, cstmt
, GSI_CONTINUE_LINKING
);
1028 fn
= build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET
));
1029 fn_call
= gimple_build_call (fn
, 3, mem
, val
, nb_bytes
);
1030 gsi_insert_after (&gsi
, fn_call
, GSI_CONTINUE_LINKING
);
1032 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1034 fprintf (dump_file
, "generated memset");
1036 fprintf (dump_file
, " zero\n");
1038 fprintf (dump_file
, "\n");
1042 /* Generate a call to memcpy for PARTITION in LOOP. */
1045 generate_memcpy_builtin (struct loop
*loop
, partition
*partition
)
1047 gimple_stmt_iterator gsi
;
1049 tree dest
, src
, fn
, nb_bytes
;
1050 enum built_in_function kind
;
1051 struct builtin_info
*builtin
= partition
->builtin
;
1053 /* The new statements will be placed before LOOP. */
1054 gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
1056 nb_bytes
= rewrite_to_non_trapping_overflow (builtin
->size
);
1057 nb_bytes
= force_gimple_operand_gsi (&gsi
, nb_bytes
, true, NULL_TREE
,
1058 false, GSI_CONTINUE_LINKING
);
1059 dest
= builtin
->dst_base
;
1060 src
= builtin
->src_base
;
1061 if (partition
->kind
== PKIND_MEMCPY
1062 || ! ptr_derefs_may_alias_p (dest
, src
))
1063 kind
= BUILT_IN_MEMCPY
;
1065 kind
= BUILT_IN_MEMMOVE
;
1067 dest
= force_gimple_operand_gsi (&gsi
, dest
, true, NULL_TREE
,
1068 false, GSI_CONTINUE_LINKING
);
1069 src
= force_gimple_operand_gsi (&gsi
, src
, true, NULL_TREE
,
1070 false, GSI_CONTINUE_LINKING
);
1071 fn
= build_fold_addr_expr (builtin_decl_implicit (kind
));
1072 fn_call
= gimple_build_call (fn
, 3, dest
, src
, nb_bytes
);
1073 gsi_insert_after (&gsi
, fn_call
, GSI_CONTINUE_LINKING
);
1075 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1077 if (kind
== BUILT_IN_MEMCPY
)
1078 fprintf (dump_file
, "generated memcpy\n");
1080 fprintf (dump_file
, "generated memmove\n");
1084 /* Remove and destroy the loop LOOP. */
1087 destroy_loop (struct loop
*loop
)
1089 unsigned nbbs
= loop
->num_nodes
;
1090 edge exit
= single_exit (loop
);
1091 basic_block src
= loop_preheader_edge (loop
)->src
, dest
= exit
->dest
;
1095 bbs
= get_loop_body_in_dom_order (loop
);
1097 redirect_edge_pred (exit
, src
);
1098 exit
->flags
&= ~(EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
1099 exit
->flags
|= EDGE_FALLTHRU
;
1100 cancel_loop_tree (loop
);
1101 rescan_loop_exit (exit
, false, true);
1106 /* We have made sure to not leave any dangling uses of SSA
1107 names defined in the loop. With the exception of virtuals.
1108 Make sure we replace all uses of virtual defs that will remain
1109 outside of the loop with the bare symbol as delete_basic_block
1110 will release them. */
1112 for (gphi_iterator gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
);
1115 gphi
*phi
= gsi
.phi ();
1116 if (virtual_operand_p (gimple_phi_result (phi
)))
1117 mark_virtual_phi_result_for_renaming (phi
);
1119 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]); !gsi_end_p (gsi
);
1122 gimple
*stmt
= gsi_stmt (gsi
);
1123 tree vdef
= gimple_vdef (stmt
);
1124 if (vdef
&& TREE_CODE (vdef
) == SSA_NAME
)
1125 mark_virtual_operand_for_renaming (vdef
);
1127 delete_basic_block (bbs
[i
]);
1133 set_immediate_dominator (CDI_DOMINATORS
, dest
,
1134 recompute_dominator (CDI_DOMINATORS
, dest
));
1137 /* Generates code for PARTITION. Return whether LOOP needs to be destroyed. */
1140 generate_code_for_partition (struct loop
*loop
,
1141 partition
*partition
, bool copy_p
)
1143 switch (partition
->kind
)
1146 case PKIND_PARTIAL_MEMSET
:
1147 /* Reductions all have to be in the last partition. */
1148 gcc_assert (!partition_reduction_p (partition
)
1150 generate_loops_for_partition (loop
, partition
, copy_p
);
1154 generate_memset_builtin (loop
, partition
);
1159 generate_memcpy_builtin (loop
, partition
);
1166 /* Common tail for partitions we turn into a call. If this was the last
1167 partition for which we generate code, we have to destroy the loop. */
1173 /* Return data dependence relation for data references A and B. The two
1174 data references must be in lexicographic order wrto reduced dependence
1175 graph RDG. We firstly try to find ddr from global ddr hash table. If
1176 it doesn't exist, compute the ddr and cache it. */
1178 static data_dependence_relation
*
1179 get_data_dependence (struct graph
*rdg
, data_reference_p a
, data_reference_p b
)
1181 struct data_dependence_relation ent
, **slot
;
1182 struct data_dependence_relation
*ddr
;
1184 gcc_assert (DR_IS_WRITE (a
) || DR_IS_WRITE (b
));
1185 gcc_assert (rdg_vertex_for_stmt (rdg
, DR_STMT (a
))
1186 <= rdg_vertex_for_stmt (rdg
, DR_STMT (b
)));
1189 slot
= ddrs_table
->find_slot (&ent
, INSERT
);
1192 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
1193 compute_affine_dependence (ddr
, loop_nest
[0]);
1200 /* In reduced dependence graph RDG for loop distribution, return true if
1201 dependence between references DR1 and DR2 leads to a dependence cycle
1202 and such dependence cycle can't be resolved by runtime alias check. */
1205 data_dep_in_cycle_p (struct graph
*rdg
,
1206 data_reference_p dr1
, data_reference_p dr2
)
1208 struct data_dependence_relation
*ddr
;
1210 /* Re-shuffle data-refs to be in topological order. */
1211 if (rdg_vertex_for_stmt (rdg
, DR_STMT (dr1
))
1212 > rdg_vertex_for_stmt (rdg
, DR_STMT (dr2
)))
1213 std::swap (dr1
, dr2
);
1215 ddr
= get_data_dependence (rdg
, dr1
, dr2
);
1217 /* In case of no data dependence. */
1218 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
1220 /* For unknown data dependence or known data dependence which can't be
1221 expressed in classic distance vector, we check if it can be resolved
1222 by runtime alias check. If yes, we still consider data dependence
1223 as won't introduce data dependence cycle. */
1224 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
1225 || DDR_NUM_DIST_VECTS (ddr
) == 0)
1226 return !runtime_alias_check_p (ddr
, NULL
, true);
1227 else if (DDR_NUM_DIST_VECTS (ddr
) > 1)
1229 else if (DDR_REVERSED_P (ddr
)
1230 || lambda_vector_zerop (DDR_DIST_VECT (ddr
, 0), 1))
1236 /* Given reduced dependence graph RDG, PARTITION1 and PARTITION2, update
1237 PARTITION1's type after merging PARTITION2 into PARTITION1. */
1240 update_type_for_merge (struct graph
*rdg
,
1241 partition
*partition1
, partition
*partition2
)
1244 bitmap_iterator bi
, bj
;
1245 data_reference_p dr1
, dr2
;
1247 EXECUTE_IF_SET_IN_BITMAP (partition1
->datarefs
, 0, i
, bi
)
1249 unsigned start
= (partition1
== partition2
) ? i
+ 1 : 0;
1251 dr1
= datarefs_vec
[i
];
1252 EXECUTE_IF_SET_IN_BITMAP (partition2
->datarefs
, start
, j
, bj
)
1254 dr2
= datarefs_vec
[j
];
1255 if (DR_IS_READ (dr1
) && DR_IS_READ (dr2
))
1258 /* Partition can only be executed sequentially if there is any
1259 data dependence cycle. */
1260 if (data_dep_in_cycle_p (rdg
, dr1
, dr2
))
1262 partition1
->type
= PTYPE_SEQUENTIAL
;
1269 /* Returns a partition with all the statements needed for computing
1270 the vertex V of the RDG, also including the loop exit conditions. */
1273 build_rdg_partition_for_vertex (struct graph
*rdg
, int v
)
1275 partition
*partition
= partition_alloc ();
1276 auto_vec
<int, 3> nodes
;
1279 data_reference_p dr
;
1281 graphds_dfs (rdg
, &v
, 1, &nodes
, false, NULL
);
1283 FOR_EACH_VEC_ELT (nodes
, i
, x
)
1285 bitmap_set_bit (partition
->stmts
, x
);
1287 for (j
= 0; RDG_DATAREFS (rdg
, x
).iterate (j
, &dr
); ++j
)
1289 unsigned idx
= (unsigned) DR_INDEX (dr
);
1290 gcc_assert (idx
< datarefs_vec
.length ());
1292 /* Partition can only be executed sequentially if there is any
1293 unknown data reference. */
1294 if (!DR_BASE_ADDRESS (dr
) || !DR_OFFSET (dr
)
1295 || !DR_INIT (dr
) || !DR_STEP (dr
))
1296 partition
->type
= PTYPE_SEQUENTIAL
;
1298 bitmap_set_bit (partition
->datarefs
, idx
);
1302 if (partition
->type
== PTYPE_SEQUENTIAL
)
1305 /* Further check if any data dependence prevents us from executing the
1306 partition parallelly. */
1307 update_type_for_merge (rdg
, partition
, partition
);
1312 /* Given PARTITION of LOOP and RDG, record single load/store data references
1313 for builtin partition in SRC_DR/DST_DR, return false if there is no such
1317 find_single_drs (struct loop
*loop
, struct graph
*rdg
, partition
*partition
,
1318 data_reference_p
*dst_dr
, data_reference_p
*src_dr
)
1321 data_reference_p single_ld
= NULL
, single_st
= NULL
;
1324 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, bi
)
1326 gimple
*stmt
= RDG_STMT (rdg
, i
);
1327 data_reference_p dr
;
1329 if (gimple_code (stmt
) == GIMPLE_PHI
)
1332 /* Any scalar stmts are ok. */
1333 if (!gimple_vuse (stmt
))
1336 /* Otherwise just regular loads/stores. */
1337 if (!gimple_assign_single_p (stmt
))
1340 /* But exactly one store and/or load. */
1341 for (unsigned j
= 0; RDG_DATAREFS (rdg
, i
).iterate (j
, &dr
); ++j
)
1343 tree type
= TREE_TYPE (DR_REF (dr
));
1345 /* The memset, memcpy and memmove library calls are only
1346 able to deal with generic address space. */
1347 if (!ADDR_SPACE_GENERIC_P (TYPE_ADDR_SPACE (type
)))
1350 if (DR_IS_READ (dr
))
1352 if (single_ld
!= NULL
)
1358 if (single_st
!= NULL
)
1368 /* Bail out if this is a bitfield memory reference. */
1369 if (TREE_CODE (DR_REF (single_st
)) == COMPONENT_REF
1370 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_st
), 1)))
1373 /* Data reference must be executed exactly once per iteration of each
1374 loop in the loop nest. We only need to check dominance information
1375 against the outermost one in a perfect loop nest because a bb can't
1376 dominate outermost loop's latch without dominating inner loop's. */
1377 basic_block bb_st
= gimple_bb (DR_STMT (single_st
));
1378 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb_st
))
1383 gimple
*store
= DR_STMT (single_st
), *load
= DR_STMT (single_ld
);
1384 /* Direct aggregate copy or via an SSA name temporary. */
1386 && gimple_assign_lhs (load
) != gimple_assign_rhs1 (store
))
1389 /* Bail out if this is a bitfield memory reference. */
1390 if (TREE_CODE (DR_REF (single_ld
)) == COMPONENT_REF
1391 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_ld
), 1)))
1394 /* Load and store must be in the same loop nest. */
1395 basic_block bb_ld
= gimple_bb (DR_STMT (single_ld
));
1396 if (bb_st
->loop_father
!= bb_ld
->loop_father
)
1399 /* Data reference must be executed exactly once per iteration.
1400 Same as single_st, we only need to check against the outermost
1402 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb_ld
))
1405 edge e
= single_exit (bb_st
->loop_father
);
1406 bool dom_ld
= dominated_by_p (CDI_DOMINATORS
, e
->src
, bb_ld
);
1407 bool dom_st
= dominated_by_p (CDI_DOMINATORS
, e
->src
, bb_st
);
1408 if (dom_ld
!= dom_st
)
1412 *src_dr
= single_ld
;
1413 *dst_dr
= single_st
;
1417 /* Given data reference DR in LOOP_NEST, this function checks the enclosing
1418 loops from inner to outer to see if loop's step equals to access size at
1419 each level of loop. Return 2 if we can prove this at all level loops;
1420 record access base and size in BASE and SIZE; save loop's step at each
1421 level of loop in STEPS if it is not null. For example:
1423 int arr[100][100][100];
1424 for (i = 0; i < 100; i++) ;steps[2] = 40000
1425 for (j = 100; j > 0; j--) ;steps[1] = -400
1426 for (k = 0; k < 100; k++) ;steps[0] = 4
1427 arr[i][j - 1][k] = 0; ;base = &arr, size = 4000000
1429 Return 1 if we can prove the equality at the innermost loop, but not all
1430 level loops. In this case, no information is recorded.
1432 Return 0 if no equality can be proven at any level loops. */
1435 compute_access_range (loop_p loop_nest
, data_reference_p dr
, tree
*base
,
1436 tree
*size
, vec
<tree
> *steps
= NULL
)
1438 location_t loc
= gimple_location (DR_STMT (dr
));
1439 basic_block bb
= gimple_bb (DR_STMT (dr
));
1440 struct loop
*loop
= bb
->loop_father
;
1441 tree ref
= DR_REF (dr
);
1442 tree access_base
= build_fold_addr_expr (ref
);
1443 tree access_size
= TYPE_SIZE_UNIT (TREE_TYPE (ref
));
1447 tree scev_fn
= analyze_scalar_evolution (loop
, access_base
);
1448 if (TREE_CODE (scev_fn
) != POLYNOMIAL_CHREC
)
1451 access_base
= CHREC_LEFT (scev_fn
);
1452 if (tree_contains_chrecs (access_base
, NULL
))
1455 tree scev_step
= CHREC_RIGHT (scev_fn
);
1456 /* Only support constant steps. */
1457 if (TREE_CODE (scev_step
) != INTEGER_CST
)
1460 enum ev_direction access_dir
= scev_direction (scev_fn
);
1461 if (access_dir
== EV_DIR_UNKNOWN
)
1465 steps
->safe_push (scev_step
);
1467 scev_step
= fold_convert_loc (loc
, sizetype
, scev_step
);
1468 /* Compute absolute value of scev step. */
1469 if (access_dir
== EV_DIR_DECREASES
)
1470 scev_step
= fold_build1_loc (loc
, NEGATE_EXPR
, sizetype
, scev_step
);
1472 /* At each level of loop, scev step must equal to access size. In other
1473 words, DR must access consecutive memory between loop iterations. */
1474 if (!operand_equal_p (scev_step
, access_size
, 0))
1477 /* Access stride can be computed for data reference at least for the
1481 /* Compute DR's execution times in loop. */
1482 tree niters
= number_of_latch_executions (loop
);
1483 niters
= fold_convert_loc (loc
, sizetype
, niters
);
1484 if (dominated_by_p (CDI_DOMINATORS
, single_exit (loop
)->src
, bb
))
1485 niters
= size_binop_loc (loc
, PLUS_EXPR
, niters
, size_one_node
);
1487 /* Compute DR's overall access size in loop. */
1488 access_size
= fold_build2_loc (loc
, MULT_EXPR
, sizetype
,
1490 /* Adjust base address in case of negative step. */
1491 if (access_dir
== EV_DIR_DECREASES
)
1493 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, sizetype
,
1494 scev_step
, access_size
);
1495 access_base
= fold_build_pointer_plus_loc (loc
, access_base
, adj
);
1497 } while (loop
!= loop_nest
&& (loop
= loop_outer (loop
)) != NULL
);
1499 *base
= access_base
;
1500 *size
= access_size
;
1501 /* Access stride can be computed for data reference at each level loop. */
1505 /* Allocate and return builtin struct. Record information like DST_DR,
1506 SRC_DR, DST_BASE, SRC_BASE and SIZE in the allocated struct. */
1508 static struct builtin_info
*
1509 alloc_builtin (data_reference_p dst_dr
, data_reference_p src_dr
,
1510 tree dst_base
, tree src_base
, tree size
)
1512 struct builtin_info
*builtin
= XNEW (struct builtin_info
);
1513 builtin
->dst_dr
= dst_dr
;
1514 builtin
->src_dr
= src_dr
;
1515 builtin
->dst_base
= dst_base
;
1516 builtin
->src_base
= src_base
;
1517 builtin
->size
= size
;
1521 /* Given data reference DR in loop nest LOOP, classify if it forms builtin
1525 classify_builtin_st (loop_p loop
, partition
*partition
, data_reference_p dr
)
1527 gimple
*stmt
= DR_STMT (dr
);
1528 tree base
, size
, rhs
= gimple_assign_rhs1 (stmt
);
1530 if (const_with_all_bytes_same (rhs
) == -1
1531 && (!INTEGRAL_TYPE_P (TREE_TYPE (rhs
))
1532 || (TYPE_MODE (TREE_TYPE (rhs
))
1533 != TYPE_MODE (unsigned_char_type_node
))))
1536 if (TREE_CODE (rhs
) == SSA_NAME
1537 && !SSA_NAME_IS_DEFAULT_DEF (rhs
)
1538 && flow_bb_inside_loop_p (loop
, gimple_bb (SSA_NAME_DEF_STMT (rhs
))))
1541 int res
= compute_access_range (loop
, dr
, &base
, &size
);
1546 partition
->kind
= PKIND_PARTIAL_MEMSET
;
1550 poly_uint64 base_offset
;
1551 unsigned HOST_WIDE_INT const_base_offset
;
1552 tree base_base
= strip_offset (base
, &base_offset
);
1553 if (!base_offset
.is_constant (&const_base_offset
))
1556 struct builtin_info
*builtin
;
1557 builtin
= alloc_builtin (dr
, NULL
, base
, NULL_TREE
, size
);
1558 builtin
->dst_base_base
= base_base
;
1559 builtin
->dst_base_offset
= const_base_offset
;
1560 partition
->builtin
= builtin
;
1561 partition
->kind
= PKIND_MEMSET
;
1564 /* Given data references DST_DR and SRC_DR in loop nest LOOP and RDG, classify
1565 if it forms builtin memcpy or memmove call. */
1568 classify_builtin_ldst (loop_p loop
, struct graph
*rdg
, partition
*partition
,
1569 data_reference_p dst_dr
, data_reference_p src_dr
)
1571 tree base
, size
, src_base
, src_size
;
1572 auto_vec
<tree
> dst_steps
, src_steps
;
1574 /* Compute access range of both load and store. */
1575 int res
= compute_access_range (loop
, dst_dr
, &base
, &size
, &dst_steps
);
1578 res
= compute_access_range (loop
, src_dr
, &src_base
, &src_size
, &src_steps
);
1582 /* They much have the same access size. */
1583 if (!operand_equal_p (size
, src_size
, 0))
1586 /* Load and store in loop nest must access memory in the same way, i.e,
1587 their must have the same steps in each loop of the nest. */
1588 if (dst_steps
.length () != src_steps
.length ())
1590 for (unsigned i
= 0; i
< dst_steps
.length (); ++i
)
1591 if (!operand_equal_p (dst_steps
[i
], src_steps
[i
], 0))
1594 /* Now check that if there is a dependence. */
1595 ddr_p ddr
= get_data_dependence (rdg
, src_dr
, dst_dr
);
1597 /* Classify as memcpy if no dependence between load and store. */
1598 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
1600 partition
->builtin
= alloc_builtin (dst_dr
, src_dr
, base
, src_base
, size
);
1601 partition
->kind
= PKIND_MEMCPY
;
1605 /* Can't do memmove in case of unknown dependence or dependence without
1606 classical distance vector. */
1607 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
1608 || DDR_NUM_DIST_VECTS (ddr
) == 0)
1612 lambda_vector dist_v
;
1613 int num_lev
= (DDR_LOOP_NEST (ddr
)).length ();
1614 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
1616 unsigned dep_lev
= dependence_level (dist_v
, num_lev
);
1617 /* Can't do memmove if load depends on store. */
1618 if (dep_lev
> 0 && dist_v
[dep_lev
- 1] > 0 && !DDR_REVERSED_P (ddr
))
1622 partition
->builtin
= alloc_builtin (dst_dr
, src_dr
, base
, src_base
, size
);
1623 partition
->kind
= PKIND_MEMMOVE
;
1627 /* Classifies the builtin kind we can generate for PARTITION of RDG and LOOP.
1628 For the moment we detect memset, memcpy and memmove patterns. Bitmap
1629 STMT_IN_ALL_PARTITIONS contains statements belonging to all partitions. */
1632 classify_partition (loop_p loop
, struct graph
*rdg
, partition
*partition
,
1633 bitmap stmt_in_all_partitions
)
1637 data_reference_p single_ld
= NULL
, single_st
= NULL
;
1638 bool volatiles_p
= false, has_reduction
= false;
1640 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, bi
)
1642 gimple
*stmt
= RDG_STMT (rdg
, i
);
1644 if (gimple_has_volatile_ops (stmt
))
1647 /* If the stmt is not included by all partitions and there is uses
1648 outside of the loop, then mark the partition as reduction. */
1649 if (stmt_has_scalar_dependences_outside_loop (loop
, stmt
))
1651 /* Due to limitation in the transform phase we have to fuse all
1652 reduction partitions. As a result, this could cancel valid
1653 loop distribution especially for loop that induction variable
1654 is used outside of loop. To workaround this issue, we skip
1655 marking partition as reudction if the reduction stmt belongs
1656 to all partitions. In such case, reduction will be computed
1657 correctly no matter how partitions are fused/distributed. */
1658 if (!bitmap_bit_p (stmt_in_all_partitions
, i
))
1660 partition
->reduction_p
= true;
1663 has_reduction
= true;
1667 /* Perform general partition disqualification for builtins. */
1669 /* Simple workaround to prevent classifying the partition as builtin
1670 if it contains any use outside of loop. */
1672 || !flag_tree_loop_distribute_patterns
)
1675 /* Find single load/store data references for builtin partition. */
1676 if (!find_single_drs (loop
, rdg
, partition
, &single_st
, &single_ld
))
1679 /* Classify the builtin kind. */
1680 if (single_ld
== NULL
)
1681 classify_builtin_st (loop
, partition
, single_st
);
1683 classify_builtin_ldst (loop
, rdg
, partition
, single_st
, single_ld
);
1686 /* Returns true when PARTITION1 and PARTITION2 access the same memory
1690 share_memory_accesses (struct graph
*rdg
,
1691 partition
*partition1
, partition
*partition2
)
1694 bitmap_iterator bi
, bj
;
1695 data_reference_p dr1
, dr2
;
1697 /* First check whether in the intersection of the two partitions are
1698 any loads or stores. Common loads are the situation that happens
1700 EXECUTE_IF_AND_IN_BITMAP (partition1
->stmts
, partition2
->stmts
, 0, i
, bi
)
1701 if (RDG_MEM_WRITE_STMT (rdg
, i
)
1702 || RDG_MEM_READS_STMT (rdg
, i
))
1705 /* Then check whether the two partitions access the same memory object. */
1706 EXECUTE_IF_SET_IN_BITMAP (partition1
->datarefs
, 0, i
, bi
)
1708 dr1
= datarefs_vec
[i
];
1710 if (!DR_BASE_ADDRESS (dr1
)
1711 || !DR_OFFSET (dr1
) || !DR_INIT (dr1
) || !DR_STEP (dr1
))
1714 EXECUTE_IF_SET_IN_BITMAP (partition2
->datarefs
, 0, j
, bj
)
1716 dr2
= datarefs_vec
[j
];
1718 if (!DR_BASE_ADDRESS (dr2
)
1719 || !DR_OFFSET (dr2
) || !DR_INIT (dr2
) || !DR_STEP (dr2
))
1722 if (operand_equal_p (DR_BASE_ADDRESS (dr1
), DR_BASE_ADDRESS (dr2
), 0)
1723 && operand_equal_p (DR_OFFSET (dr1
), DR_OFFSET (dr2
), 0)
1724 && operand_equal_p (DR_INIT (dr1
), DR_INIT (dr2
), 0)
1725 && operand_equal_p (DR_STEP (dr1
), DR_STEP (dr2
), 0))
1733 /* For each seed statement in STARTING_STMTS, this function builds
1734 partition for it by adding depended statements according to RDG.
1735 All partitions are recorded in PARTITIONS. */
1738 rdg_build_partitions (struct graph
*rdg
,
1739 vec
<gimple
*> starting_stmts
,
1740 vec
<partition
*> *partitions
)
1742 auto_bitmap processed
;
1746 FOR_EACH_VEC_ELT (starting_stmts
, i
, stmt
)
1748 int v
= rdg_vertex_for_stmt (rdg
, stmt
);
1750 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1752 "ldist asked to generate code for vertex %d\n", v
);
1754 /* If the vertex is already contained in another partition so
1755 is the partition rooted at it. */
1756 if (bitmap_bit_p (processed
, v
))
1759 partition
*partition
= build_rdg_partition_for_vertex (rdg
, v
);
1760 bitmap_ior_into (processed
, partition
->stmts
);
1762 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1764 fprintf (dump_file
, "ldist creates useful %s partition:\n",
1765 partition
->type
== PTYPE_PARALLEL
? "parallel" : "sequent");
1766 bitmap_print (dump_file
, partition
->stmts
, " ", "\n");
1769 partitions
->safe_push (partition
);
1772 /* All vertices should have been assigned to at least one partition now,
1773 other than vertices belonging to dead code. */
1776 /* Dump to FILE the PARTITIONS. */
1779 dump_rdg_partitions (FILE *file
, vec
<partition
*> partitions
)
1782 partition
*partition
;
1784 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1785 debug_bitmap_file (file
, partition
->stmts
);
1788 /* Debug PARTITIONS. */
1789 extern void debug_rdg_partitions (vec
<partition
*> );
1792 debug_rdg_partitions (vec
<partition
*> partitions
)
1794 dump_rdg_partitions (stderr
, partitions
);
1797 /* Returns the number of read and write operations in the RDG. */
1800 number_of_rw_in_rdg (struct graph
*rdg
)
1804 for (i
= 0; i
< rdg
->n_vertices
; i
++)
1806 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1809 if (RDG_MEM_READS_STMT (rdg
, i
))
1816 /* Returns the number of read and write operations in a PARTITION of
1820 number_of_rw_in_partition (struct graph
*rdg
, partition
*partition
)
1826 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, ii
)
1828 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1831 if (RDG_MEM_READS_STMT (rdg
, i
))
1838 /* Returns true when one of the PARTITIONS contains all the read or
1839 write operations of RDG. */
1842 partition_contains_all_rw (struct graph
*rdg
,
1843 vec
<partition
*> partitions
)
1846 partition
*partition
;
1847 int nrw
= number_of_rw_in_rdg (rdg
);
1849 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1850 if (nrw
== number_of_rw_in_partition (rdg
, partition
))
1856 /* Compute partition dependence created by the data references in DRS1
1857 and DRS2, modify and return DIR according to that. IF ALIAS_DDR is
1858 not NULL, we record dependence introduced by possible alias between
1859 two data references in ALIAS_DDRS; otherwise, we simply ignore such
1860 dependence as if it doesn't exist at all. */
1863 pg_add_dependence_edges (struct graph
*rdg
, int dir
,
1864 bitmap drs1
, bitmap drs2
, vec
<ddr_p
> *alias_ddrs
)
1867 bitmap_iterator bi
, bj
;
1868 data_reference_p dr1
, dr2
, saved_dr1
;
1870 /* dependence direction - 0 is no dependence, -1 is back,
1871 1 is forth, 2 is both (we can stop then, merging will occur). */
1872 EXECUTE_IF_SET_IN_BITMAP (drs1
, 0, i
, bi
)
1874 dr1
= datarefs_vec
[i
];
1876 EXECUTE_IF_SET_IN_BITMAP (drs2
, 0, j
, bj
)
1878 int res
, this_dir
= 1;
1881 dr2
= datarefs_vec
[j
];
1883 /* Skip all <read, read> data dependence. */
1884 if (DR_IS_READ (dr1
) && DR_IS_READ (dr2
))
1888 /* Re-shuffle data-refs to be in topological order. */
1889 if (rdg_vertex_for_stmt (rdg
, DR_STMT (dr1
))
1890 > rdg_vertex_for_stmt (rdg
, DR_STMT (dr2
)))
1892 std::swap (dr1
, dr2
);
1893 this_dir
= -this_dir
;
1895 ddr
= get_data_dependence (rdg
, dr1
, dr2
);
1896 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
1899 res
= data_ref_compare_tree (DR_BASE_ADDRESS (dr1
),
1900 DR_BASE_ADDRESS (dr2
));
1901 /* Be conservative. If data references are not well analyzed,
1902 or the two data references have the same base address and
1903 offset, add dependence and consider it alias to each other.
1904 In other words, the dependence cannot be resolved by
1905 runtime alias check. */
1906 if (!DR_BASE_ADDRESS (dr1
) || !DR_BASE_ADDRESS (dr2
)
1907 || !DR_OFFSET (dr1
) || !DR_OFFSET (dr2
)
1908 || !DR_INIT (dr1
) || !DR_INIT (dr2
)
1909 || !DR_STEP (dr1
) || !tree_fits_uhwi_p (DR_STEP (dr1
))
1910 || !DR_STEP (dr2
) || !tree_fits_uhwi_p (DR_STEP (dr2
))
1913 /* Data dependence could be resolved by runtime alias check,
1914 record it in ALIAS_DDRS. */
1915 else if (alias_ddrs
!= NULL
)
1916 alias_ddrs
->safe_push (ddr
);
1917 /* Or simply ignore it. */
1919 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1921 if (DDR_REVERSED_P (ddr
))
1922 this_dir
= -this_dir
;
1924 /* Known dependences can still be unordered througout the
1925 iteration space, see gcc.dg/tree-ssa/ldist-16.c. */
1926 if (DDR_NUM_DIST_VECTS (ddr
) != 1)
1928 /* If the overlap is exact preserve stmt order. */
1929 else if (lambda_vector_zerop (DDR_DIST_VECT (ddr
, 0),
1930 DDR_NB_LOOPS (ddr
)))
1932 /* Else as the distance vector is lexicographic positive swap
1933 the dependence direction. */
1935 this_dir
= -this_dir
;
1943 else if (this_dir
!= 0 && dir
!= this_dir
)
1945 /* Shuffle "back" dr1. */
1952 /* Compare postorder number of the partition graph vertices V1 and V2. */
1955 pgcmp (const void *v1_
, const void *v2_
)
1957 const vertex
*v1
= (const vertex
*)v1_
;
1958 const vertex
*v2
= (const vertex
*)v2_
;
1959 return v2
->post
- v1
->post
;
1962 /* Data attached to vertices of partition dependence graph. */
1965 /* ID of the corresponding partition. */
1967 /* The partition. */
1968 struct partition
*partition
;
1971 /* Data attached to edges of partition dependence graph. */
1974 /* If the dependence edge can be resolved by runtime alias check,
1975 this vector contains data dependence relations for runtime alias
1976 check. On the other hand, if the dependence edge is introduced
1977 because of compilation time known data dependence, this vector
1978 contains nothing. */
1979 vec
<ddr_p
> alias_ddrs
;
1982 /* Callback data for traversing edges in graph. */
1983 struct pg_edge_callback_data
1985 /* Bitmap contains strong connected components should be merged. */
1986 bitmap sccs_to_merge
;
1987 /* Array constains component information for all vertices. */
1988 int *vertices_component
;
1989 /* Vector to record all data dependence relations which are needed
1990 to break strong connected components by runtime alias checks. */
1991 vec
<ddr_p
> *alias_ddrs
;
1994 /* Initialize vertice's data for partition dependence graph PG with
1998 init_partition_graph_vertices (struct graph
*pg
,
1999 vec
<struct partition
*> *partitions
)
2002 partition
*partition
;
2003 struct pg_vdata
*data
;
2005 for (i
= 0; partitions
->iterate (i
, &partition
); ++i
)
2007 data
= new pg_vdata
;
2008 pg
->vertices
[i
].data
= data
;
2010 data
->partition
= partition
;
2014 /* Add edge <I, J> to partition dependence graph PG. Attach vector of data
2015 dependence relations to the EDGE if DDRS isn't NULL. */
2018 add_partition_graph_edge (struct graph
*pg
, int i
, int j
, vec
<ddr_p
> *ddrs
)
2020 struct graph_edge
*e
= add_edge (pg
, i
, j
);
2022 /* If the edge is attached with data dependence relations, it means this
2023 dependence edge can be resolved by runtime alias checks. */
2026 struct pg_edata
*data
= new pg_edata
;
2028 gcc_assert (ddrs
->length () > 0);
2030 data
->alias_ddrs
= vNULL
;
2031 data
->alias_ddrs
.safe_splice (*ddrs
);
2035 /* Callback function for graph travesal algorithm. It returns true
2036 if edge E should skipped when traversing the graph. */
2039 pg_skip_alias_edge (struct graph_edge
*e
)
2041 struct pg_edata
*data
= (struct pg_edata
*)e
->data
;
2042 return (data
!= NULL
&& data
->alias_ddrs
.length () > 0);
2045 /* Callback function freeing data attached to edge E of graph. */
2048 free_partition_graph_edata_cb (struct graph
*, struct graph_edge
*e
, void *)
2050 if (e
->data
!= NULL
)
2052 struct pg_edata
*data
= (struct pg_edata
*)e
->data
;
2053 data
->alias_ddrs
.release ();
2058 /* Free data attached to vertice of partition dependence graph PG. */
2061 free_partition_graph_vdata (struct graph
*pg
)
2064 struct pg_vdata
*data
;
2066 for (i
= 0; i
< pg
->n_vertices
; ++i
)
2068 data
= (struct pg_vdata
*)pg
->vertices
[i
].data
;
2073 /* Build and return partition dependence graph for PARTITIONS. RDG is
2074 reduced dependence graph for the loop to be distributed. If IGNORE_ALIAS_P
2075 is true, data dependence caused by possible alias between references
2076 is ignored, as if it doesn't exist at all; otherwise all depdendences
2079 static struct graph
*
2080 build_partition_graph (struct graph
*rdg
,
2081 vec
<struct partition
*> *partitions
,
2082 bool ignore_alias_p
)
2085 struct partition
*partition1
, *partition2
;
2086 graph
*pg
= new_graph (partitions
->length ());
2087 auto_vec
<ddr_p
> alias_ddrs
, *alias_ddrs_p
;
2089 alias_ddrs_p
= ignore_alias_p
? NULL
: &alias_ddrs
;
2091 init_partition_graph_vertices (pg
, partitions
);
2093 for (i
= 0; partitions
->iterate (i
, &partition1
); ++i
)
2095 for (j
= i
+ 1; partitions
->iterate (j
, &partition2
); ++j
)
2097 /* dependence direction - 0 is no dependence, -1 is back,
2098 1 is forth, 2 is both (we can stop then, merging will occur). */
2101 /* If the first partition has reduction, add back edge; if the
2102 second partition has reduction, add forth edge. This makes
2103 sure that reduction partition will be sorted as the last one. */
2104 if (partition_reduction_p (partition1
))
2106 else if (partition_reduction_p (partition2
))
2109 /* Cleanup the temporary vector. */
2110 alias_ddrs
.truncate (0);
2112 dir
= pg_add_dependence_edges (rdg
, dir
, partition1
->datarefs
,
2113 partition2
->datarefs
, alias_ddrs_p
);
2115 /* Add edge to partition graph if there exists dependence. There
2116 are two types of edges. One type edge is caused by compilation
2117 time known dependence, this type cannot be resolved by runtime
2118 alias check. The other type can be resolved by runtime alias
2120 if (dir
== 1 || dir
== 2
2121 || alias_ddrs
.length () > 0)
2123 /* Attach data dependence relations to edge that can be resolved
2124 by runtime alias check. */
2125 bool alias_edge_p
= (dir
!= 1 && dir
!= 2);
2126 add_partition_graph_edge (pg
, i
, j
,
2127 (alias_edge_p
) ? &alias_ddrs
: NULL
);
2129 if (dir
== -1 || dir
== 2
2130 || alias_ddrs
.length () > 0)
2132 /* Attach data dependence relations to edge that can be resolved
2133 by runtime alias check. */
2134 bool alias_edge_p
= (dir
!= -1 && dir
!= 2);
2135 add_partition_graph_edge (pg
, j
, i
,
2136 (alias_edge_p
) ? &alias_ddrs
: NULL
);
2143 /* Sort partitions in PG in descending post order and store them in
2147 sort_partitions_by_post_order (struct graph
*pg
,
2148 vec
<struct partition
*> *partitions
)
2151 struct pg_vdata
*data
;
2153 /* Now order the remaining nodes in descending postorder. */
2154 qsort (pg
->vertices
, pg
->n_vertices
, sizeof (vertex
), pgcmp
);
2155 partitions
->truncate (0);
2156 for (i
= 0; i
< pg
->n_vertices
; ++i
)
2158 data
= (struct pg_vdata
*)pg
->vertices
[i
].data
;
2159 if (data
->partition
)
2160 partitions
->safe_push (data
->partition
);
2164 /* Given reduced dependence graph RDG merge strong connected components
2165 of PARTITIONS. If IGNORE_ALIAS_P is true, data dependence caused by
2166 possible alias between references is ignored, as if it doesn't exist
2167 at all; otherwise all depdendences are considered. */
2170 merge_dep_scc_partitions (struct graph
*rdg
,
2171 vec
<struct partition
*> *partitions
,
2172 bool ignore_alias_p
)
2174 struct partition
*partition1
, *partition2
;
2175 struct pg_vdata
*data
;
2176 graph
*pg
= build_partition_graph (rdg
, partitions
, ignore_alias_p
);
2177 int i
, j
, num_sccs
= graphds_scc (pg
, NULL
);
2179 /* Strong connected compoenent means dependence cycle, we cannot distribute
2180 them. So fuse them together. */
2181 if ((unsigned) num_sccs
< partitions
->length ())
2183 for (i
= 0; i
< num_sccs
; ++i
)
2185 for (j
= 0; partitions
->iterate (j
, &partition1
); ++j
)
2186 if (pg
->vertices
[j
].component
== i
)
2188 for (j
= j
+ 1; partitions
->iterate (j
, &partition2
); ++j
)
2189 if (pg
->vertices
[j
].component
== i
)
2191 partition_merge_into (NULL
, partition1
,
2192 partition2
, FUSE_SAME_SCC
);
2193 partition1
->type
= PTYPE_SEQUENTIAL
;
2194 (*partitions
)[j
] = NULL
;
2195 partition_free (partition2
);
2196 data
= (struct pg_vdata
*)pg
->vertices
[j
].data
;
2197 data
->partition
= NULL
;
2202 sort_partitions_by_post_order (pg
, partitions
);
2203 gcc_assert (partitions
->length () == (unsigned)num_sccs
);
2204 free_partition_graph_vdata (pg
);
2208 /* Callback function for traversing edge E in graph G. DATA is private
2212 pg_collect_alias_ddrs (struct graph
*g
, struct graph_edge
*e
, void *data
)
2214 int i
, j
, component
;
2215 struct pg_edge_callback_data
*cbdata
;
2216 struct pg_edata
*edata
= (struct pg_edata
*) e
->data
;
2218 /* If the edge doesn't have attached data dependence, it represents
2219 compilation time known dependences. This type dependence cannot
2220 be resolved by runtime alias check. */
2221 if (edata
== NULL
|| edata
->alias_ddrs
.length () == 0)
2224 cbdata
= (struct pg_edge_callback_data
*) data
;
2227 component
= cbdata
->vertices_component
[i
];
2228 /* Vertices are topologically sorted according to compilation time
2229 known dependences, so we can break strong connected components
2230 by removing edges of the opposite direction, i.e, edges pointing
2231 from vertice with smaller post number to vertice with bigger post
2233 if (g
->vertices
[i
].post
< g
->vertices
[j
].post
2234 /* We only need to remove edges connecting vertices in the same
2235 strong connected component to break it. */
2236 && component
== cbdata
->vertices_component
[j
]
2237 /* Check if we want to break the strong connected component or not. */
2238 && !bitmap_bit_p (cbdata
->sccs_to_merge
, component
))
2239 cbdata
->alias_ddrs
->safe_splice (edata
->alias_ddrs
);
2242 /* This is the main function breaking strong conected components in
2243 PARTITIONS giving reduced depdendence graph RDG. Store data dependence
2244 relations for runtime alias check in ALIAS_DDRS. */
2247 break_alias_scc_partitions (struct graph
*rdg
,
2248 vec
<struct partition
*> *partitions
,
2249 vec
<ddr_p
> *alias_ddrs
)
2251 int i
, j
, k
, num_sccs
, num_sccs_no_alias
;
2252 /* Build partition dependence graph. */
2253 graph
*pg
= build_partition_graph (rdg
, partitions
, false);
2255 alias_ddrs
->truncate (0);
2256 /* Find strong connected components in the graph, with all dependence edges
2258 num_sccs
= graphds_scc (pg
, NULL
);
2259 /* All SCCs now can be broken by runtime alias checks because SCCs caused by
2260 compilation time known dependences are merged before this function. */
2261 if ((unsigned) num_sccs
< partitions
->length ())
2263 struct pg_edge_callback_data cbdata
;
2264 auto_bitmap sccs_to_merge
;
2265 auto_vec
<enum partition_type
> scc_types
;
2266 struct partition
*partition
, *first
;
2268 /* If all partitions in a SCC have the same type, we can simply merge the
2269 SCC. This loop finds out such SCCS and record them in bitmap. */
2270 bitmap_set_range (sccs_to_merge
, 0, (unsigned) num_sccs
);
2271 for (i
= 0; i
< num_sccs
; ++i
)
2273 for (j
= 0; partitions
->iterate (j
, &first
); ++j
)
2274 if (pg
->vertices
[j
].component
== i
)
2277 bool same_type
= true, all_builtins
= partition_builtin_p (first
);
2278 for (++j
; partitions
->iterate (j
, &partition
); ++j
)
2280 if (pg
->vertices
[j
].component
!= i
)
2283 if (first
->type
!= partition
->type
)
2288 all_builtins
&= partition_builtin_p (partition
);
2290 /* Merge SCC if all partitions in SCC have the same type, though the
2291 result partition is sequential, because vectorizer can do better
2292 runtime alias check. One expecption is all partitions in SCC are
2294 if (!same_type
|| all_builtins
)
2295 bitmap_clear_bit (sccs_to_merge
, i
);
2298 /* Initialize callback data for traversing. */
2299 cbdata
.sccs_to_merge
= sccs_to_merge
;
2300 cbdata
.alias_ddrs
= alias_ddrs
;
2301 cbdata
.vertices_component
= XNEWVEC (int, pg
->n_vertices
);
2302 /* Record the component information which will be corrupted by next
2303 graph scc finding call. */
2304 for (i
= 0; i
< pg
->n_vertices
; ++i
)
2305 cbdata
.vertices_component
[i
] = pg
->vertices
[i
].component
;
2307 /* Collect data dependences for runtime alias checks to break SCCs. */
2308 if (bitmap_count_bits (sccs_to_merge
) != (unsigned) num_sccs
)
2310 /* Run SCC finding algorithm again, with alias dependence edges
2311 skipped. This is to topologically sort partitions according to
2312 compilation time known dependence. Note the topological order
2313 is stored in the form of pg's post order number. */
2314 num_sccs_no_alias
= graphds_scc (pg
, NULL
, pg_skip_alias_edge
);
2315 gcc_assert (partitions
->length () == (unsigned) num_sccs_no_alias
);
2316 /* With topological order, we can construct two subgraphs L and R.
2317 L contains edge <x, y> where x < y in terms of post order, while
2318 R contains edge <x, y> where x > y. Edges for compilation time
2319 known dependence all fall in R, so we break SCCs by removing all
2320 (alias) edges of in subgraph L. */
2321 for_each_edge (pg
, pg_collect_alias_ddrs
, &cbdata
);
2324 /* For SCC that doesn't need to be broken, merge it. */
2325 for (i
= 0; i
< num_sccs
; ++i
)
2327 if (!bitmap_bit_p (sccs_to_merge
, i
))
2330 for (j
= 0; partitions
->iterate (j
, &first
); ++j
)
2331 if (cbdata
.vertices_component
[j
] == i
)
2333 for (k
= j
+ 1; partitions
->iterate (k
, &partition
); ++k
)
2335 struct pg_vdata
*data
;
2337 if (cbdata
.vertices_component
[k
] != i
)
2340 /* Update postorder number so that merged reduction partition is
2341 sorted after other partitions. */
2342 if (!partition_reduction_p (first
)
2343 && partition_reduction_p (partition
))
2345 gcc_assert (pg
->vertices
[k
].post
< pg
->vertices
[j
].post
);
2346 pg
->vertices
[j
].post
= pg
->vertices
[k
].post
;
2348 partition_merge_into (NULL
, first
, partition
, FUSE_SAME_SCC
);
2349 (*partitions
)[k
] = NULL
;
2350 partition_free (partition
);
2351 data
= (struct pg_vdata
*)pg
->vertices
[k
].data
;
2352 gcc_assert (data
->id
== k
);
2353 data
->partition
= NULL
;
2354 /* The result partition of merged SCC must be sequential. */
2355 first
->type
= PTYPE_SEQUENTIAL
;
2360 sort_partitions_by_post_order (pg
, partitions
);
2361 free_partition_graph_vdata (pg
);
2362 for_each_edge (pg
, free_partition_graph_edata_cb
, NULL
);
2365 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2367 fprintf (dump_file
, "Possible alias data dependence to break:\n");
2368 dump_data_dependence_relations (dump_file
, *alias_ddrs
);
2372 /* Compute and return an expression whose value is the segment length which
2373 will be accessed by DR in NITERS iterations. */
2376 data_ref_segment_size (struct data_reference
*dr
, tree niters
)
2378 niters
= size_binop (MINUS_EXPR
,
2379 fold_convert (sizetype
, niters
),
2381 return size_binop (MULT_EXPR
,
2382 fold_convert (sizetype
, DR_STEP (dr
)),
2383 fold_convert (sizetype
, niters
));
2386 /* Return true if LOOP's latch is dominated by statement for data reference
2390 latch_dominated_by_data_ref (struct loop
*loop
, data_reference
*dr
)
2392 return dominated_by_p (CDI_DOMINATORS
, single_exit (loop
)->src
,
2393 gimple_bb (DR_STMT (dr
)));
2396 /* Compute alias check pairs and store them in COMP_ALIAS_PAIRS for LOOP's
2397 data dependence relations ALIAS_DDRS. */
2400 compute_alias_check_pairs (struct loop
*loop
, vec
<ddr_p
> *alias_ddrs
,
2401 vec
<dr_with_seg_len_pair_t
> *comp_alias_pairs
)
2404 unsigned HOST_WIDE_INT factor
= 1;
2405 tree niters_plus_one
, niters
= number_of_latch_executions (loop
);
2407 gcc_assert (niters
!= NULL_TREE
&& niters
!= chrec_dont_know
);
2408 niters
= fold_convert (sizetype
, niters
);
2409 niters_plus_one
= size_binop (PLUS_EXPR
, niters
, size_one_node
);
2411 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2412 fprintf (dump_file
, "Creating alias check pairs:\n");
2414 /* Iterate all data dependence relations and compute alias check pairs. */
2415 for (i
= 0; i
< alias_ddrs
->length (); i
++)
2417 ddr_p ddr
= (*alias_ddrs
)[i
];
2418 struct data_reference
*dr_a
= DDR_A (ddr
);
2419 struct data_reference
*dr_b
= DDR_B (ddr
);
2420 tree seg_length_a
, seg_length_b
;
2421 int comp_res
= data_ref_compare_tree (DR_BASE_ADDRESS (dr_a
),
2422 DR_BASE_ADDRESS (dr_b
));
2425 comp_res
= data_ref_compare_tree (DR_OFFSET (dr_a
), DR_OFFSET (dr_b
));
2426 gcc_assert (comp_res
!= 0);
2428 if (latch_dominated_by_data_ref (loop
, dr_a
))
2429 seg_length_a
= data_ref_segment_size (dr_a
, niters_plus_one
);
2431 seg_length_a
= data_ref_segment_size (dr_a
, niters
);
2433 if (latch_dominated_by_data_ref (loop
, dr_b
))
2434 seg_length_b
= data_ref_segment_size (dr_b
, niters_plus_one
);
2436 seg_length_b
= data_ref_segment_size (dr_b
, niters
);
2438 unsigned HOST_WIDE_INT access_size_a
2439 = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a
))));
2440 unsigned HOST_WIDE_INT access_size_b
2441 = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_b
))));
2442 unsigned int align_a
= TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_a
)));
2443 unsigned int align_b
= TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_b
)));
2445 dr_with_seg_len_pair_t dr_with_seg_len_pair
2446 (dr_with_seg_len (dr_a
, seg_length_a
, access_size_a
, align_a
),
2447 dr_with_seg_len (dr_b
, seg_length_b
, access_size_b
, align_b
));
2449 /* Canonicalize pairs by sorting the two DR members. */
2451 std::swap (dr_with_seg_len_pair
.first
, dr_with_seg_len_pair
.second
);
2453 comp_alias_pairs
->safe_push (dr_with_seg_len_pair
);
2456 if (tree_fits_uhwi_p (niters
))
2457 factor
= tree_to_uhwi (niters
);
2459 /* Prune alias check pairs. */
2460 prune_runtime_alias_test_list (comp_alias_pairs
, factor
);
2461 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2463 "Improved number of alias checks from %d to %d\n",
2464 alias_ddrs
->length (), comp_alias_pairs
->length ());
2467 /* Given data dependence relations in ALIAS_DDRS, generate runtime alias
2468 checks and version LOOP under condition of these runtime alias checks. */
2471 version_loop_by_alias_check (vec
<struct partition
*> *partitions
,
2472 struct loop
*loop
, vec
<ddr_p
> *alias_ddrs
)
2474 profile_probability prob
;
2475 basic_block cond_bb
;
2477 tree lhs
, arg0
, cond_expr
= NULL_TREE
;
2478 gimple_seq cond_stmts
= NULL
;
2479 gimple
*call_stmt
= NULL
;
2480 auto_vec
<dr_with_seg_len_pair_t
> comp_alias_pairs
;
2482 /* Generate code for runtime alias checks if necessary. */
2483 gcc_assert (alias_ddrs
->length () > 0);
2485 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2487 "Version loop <%d> with runtime alias check\n", loop
->num
);
2489 compute_alias_check_pairs (loop
, alias_ddrs
, &comp_alias_pairs
);
2490 create_runtime_alias_checks (loop
, &comp_alias_pairs
, &cond_expr
);
2491 cond_expr
= force_gimple_operand_1 (cond_expr
, &cond_stmts
,
2492 is_gimple_val
, NULL_TREE
);
2494 /* Depend on vectorizer to fold IFN_LOOP_DIST_ALIAS. */
2495 bool cancelable_p
= flag_tree_loop_vectorize
;
2499 struct partition
*partition
;
2500 for (; partitions
->iterate (i
, &partition
); ++i
)
2501 if (!partition_builtin_p (partition
))
2504 /* If all partitions are builtins, distributing it would be profitable and
2505 we don't want to cancel the runtime alias checks. */
2506 if (i
== partitions
->length ())
2507 cancelable_p
= false;
2510 /* Generate internal function call for loop distribution alias check if the
2511 runtime alias check should be cancelable. */
2514 call_stmt
= gimple_build_call_internal (IFN_LOOP_DIST_ALIAS
,
2515 2, NULL_TREE
, cond_expr
);
2516 lhs
= make_ssa_name (boolean_type_node
);
2517 gimple_call_set_lhs (call_stmt
, lhs
);
2522 prob
= profile_probability::guessed_always ().apply_scale (9, 10);
2523 initialize_original_copy_tables ();
2524 nloop
= loop_version (loop
, lhs
, &cond_bb
, prob
, prob
.invert (),
2525 prob
, prob
.invert (), true);
2526 free_original_copy_tables ();
2527 /* Record the original loop number in newly generated loops. In case of
2528 distribution, the original loop will be distributed and the new loop
2530 loop
->orig_loop_num
= nloop
->num
;
2531 nloop
->orig_loop_num
= nloop
->num
;
2532 nloop
->dont_vectorize
= true;
2533 nloop
->force_vectorize
= false;
2537 /* Record new loop's num in IFN_LOOP_DIST_ALIAS because the original
2538 loop could be destroyed. */
2539 arg0
= build_int_cst (integer_type_node
, loop
->orig_loop_num
);
2540 gimple_call_set_arg (call_stmt
, 0, arg0
);
2541 gimple_seq_add_stmt_without_update (&cond_stmts
, call_stmt
);
2546 gimple_stmt_iterator cond_gsi
= gsi_last_bb (cond_bb
);
2547 gsi_insert_seq_before (&cond_gsi
, cond_stmts
, GSI_SAME_STMT
);
2549 update_ssa (TODO_update_ssa
);
2552 /* Return true if loop versioning is needed to distrubute PARTITIONS.
2553 ALIAS_DDRS are data dependence relations for runtime alias check. */
2556 version_for_distribution_p (vec
<struct partition
*> *partitions
,
2557 vec
<ddr_p
> *alias_ddrs
)
2559 /* No need to version loop if we have only one partition. */
2560 if (partitions
->length () == 1)
2563 /* Need to version loop if runtime alias check is necessary. */
2564 return (alias_ddrs
->length () > 0);
2567 /* Compare base offset of builtin mem* partitions P1 and P2. */
2570 offset_cmp (const void *vp1
, const void *vp2
)
2572 struct partition
*p1
= *(struct partition
*const *) vp1
;
2573 struct partition
*p2
= *(struct partition
*const *) vp2
;
2574 unsigned HOST_WIDE_INT o1
= p1
->builtin
->dst_base_offset
;
2575 unsigned HOST_WIDE_INT o2
= p2
->builtin
->dst_base_offset
;
2576 return (o2
< o1
) - (o1
< o2
);
2579 /* Fuse adjacent memset builtin PARTITIONS if possible. This is a special
2580 case optimization transforming below code:
2582 __builtin_memset (&obj, 0, 100);
2584 __builtin_memset (_1, 0, 200);
2586 __builtin_memset (_2, 0, 100);
2590 __builtin_memset (&obj, 0, 400);
2592 Note we don't have dependence information between different partitions
2593 at this point, as a result, we can't handle nonadjacent memset builtin
2594 partitions since dependence might be broken. */
2597 fuse_memset_builtins (vec
<struct partition
*> *partitions
)
2600 struct partition
*part1
, *part2
;
2603 for (i
= 0; partitions
->iterate (i
, &part1
);)
2605 if (part1
->kind
!= PKIND_MEMSET
)
2611 /* Find sub-array of memset builtins of the same base. Index range
2612 of the sub-array is [i, j) with "j > i". */
2613 for (j
= i
+ 1; partitions
->iterate (j
, &part2
); ++j
)
2615 if (part2
->kind
!= PKIND_MEMSET
2616 || !operand_equal_p (part1
->builtin
->dst_base_base
,
2617 part2
->builtin
->dst_base_base
, 0))
2620 /* Memset calls setting different values can't be merged. */
2621 rhs1
= gimple_assign_rhs1 (DR_STMT (part1
->builtin
->dst_dr
));
2622 rhs2
= gimple_assign_rhs1 (DR_STMT (part2
->builtin
->dst_dr
));
2623 if (!operand_equal_p (rhs1
, rhs2
, 0))
2627 /* Stable sort is required in order to avoid breaking dependence. */
2628 gcc_stablesort (&(*partitions
)[i
], j
- i
, sizeof (*partitions
)[i
],
2630 /* Continue with next partition. */
2634 /* Merge all consecutive memset builtin partitions. */
2635 for (i
= 0; i
< partitions
->length () - 1;)
2637 part1
= (*partitions
)[i
];
2638 if (part1
->kind
!= PKIND_MEMSET
)
2644 part2
= (*partitions
)[i
+ 1];
2645 /* Only merge memset partitions of the same base and with constant
2647 if (part2
->kind
!= PKIND_MEMSET
2648 || TREE_CODE (part1
->builtin
->size
) != INTEGER_CST
2649 || TREE_CODE (part2
->builtin
->size
) != INTEGER_CST
2650 || !operand_equal_p (part1
->builtin
->dst_base_base
,
2651 part2
->builtin
->dst_base_base
, 0))
2656 rhs1
= gimple_assign_rhs1 (DR_STMT (part1
->builtin
->dst_dr
));
2657 rhs2
= gimple_assign_rhs1 (DR_STMT (part2
->builtin
->dst_dr
));
2658 int bytev1
= const_with_all_bytes_same (rhs1
);
2659 int bytev2
= const_with_all_bytes_same (rhs2
);
2660 /* Only merge memset partitions of the same value. */
2661 if (bytev1
!= bytev2
|| bytev1
== -1)
2666 wide_int end1
= wi::add (part1
->builtin
->dst_base_offset
,
2667 wi::to_wide (part1
->builtin
->size
));
2668 /* Only merge adjacent memset partitions. */
2669 if (wi::ne_p (end1
, part2
->builtin
->dst_base_offset
))
2674 /* Merge partitions[i] and partitions[i+1]. */
2675 part1
->builtin
->size
= fold_build2 (PLUS_EXPR
, sizetype
,
2676 part1
->builtin
->size
,
2677 part2
->builtin
->size
);
2678 partition_free (part2
);
2679 partitions
->ordered_remove (i
+ 1);
2683 /* Fuse PARTITIONS of LOOP if necessary before finalizing distribution.
2684 ALIAS_DDRS contains ddrs which need runtime alias check. */
2687 finalize_partitions (struct loop
*loop
, vec
<struct partition
*> *partitions
,
2688 vec
<ddr_p
> *alias_ddrs
)
2691 struct partition
*partition
, *a
;
2693 if (partitions
->length () == 1
2694 || alias_ddrs
->length () > 0)
2697 unsigned num_builtin
= 0, num_normal
= 0, num_partial_memset
= 0;
2698 bool same_type_p
= true;
2699 enum partition_type type
= ((*partitions
)[0])->type
;
2700 for (i
= 0; partitions
->iterate (i
, &partition
); ++i
)
2702 same_type_p
&= (type
== partition
->type
);
2703 if (partition_builtin_p (partition
))
2709 if (partition
->kind
== PKIND_PARTIAL_MEMSET
)
2710 num_partial_memset
++;
2713 /* Don't distribute current loop into too many loops given we don't have
2714 memory stream cost model. Be even more conservative in case of loop
2715 nest distribution. */
2716 if ((same_type_p
&& num_builtin
== 0
2717 && (loop
->inner
== NULL
|| num_normal
!= 2 || num_partial_memset
!= 1))
2718 || (loop
->inner
!= NULL
2719 && i
>= NUM_PARTITION_THRESHOLD
&& num_normal
> 1)
2720 || (loop
->inner
== NULL
2721 && i
>= NUM_PARTITION_THRESHOLD
&& num_normal
> num_builtin
))
2723 a
= (*partitions
)[0];
2724 for (i
= 1; partitions
->iterate (i
, &partition
); ++i
)
2726 partition_merge_into (NULL
, a
, partition
, FUSE_FINALIZE
);
2727 partition_free (partition
);
2729 partitions
->truncate (1);
2732 /* Fuse memset builtins if possible. */
2733 if (partitions
->length () > 1)
2734 fuse_memset_builtins (partitions
);
2737 /* Distributes the code from LOOP in such a way that producer statements
2738 are placed before consumer statements. Tries to separate only the
2739 statements from STMTS into separate loops. Returns the number of
2740 distributed loops. Set NB_CALLS to number of generated builtin calls.
2741 Set *DESTROY_P to whether LOOP needs to be destroyed. */
2744 distribute_loop (struct loop
*loop
, vec
<gimple
*> stmts
,
2745 control_dependences
*cd
, int *nb_calls
, bool *destroy_p
)
2747 ddrs_table
= new hash_table
<ddr_hasher
> (389);
2749 partition
*partition
;
2755 loop_nest
.create (0);
2756 if (!find_loop_nest (loop
, &loop_nest
))
2758 loop_nest
.release ();
2763 datarefs_vec
.create (20);
2764 has_nonaddressable_dataref_p
= false;
2765 rdg
= build_rdg (loop
, cd
);
2768 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2770 "Loop %d not distributed: failed to build the RDG.\n",
2773 loop_nest
.release ();
2774 free_data_refs (datarefs_vec
);
2779 if (datarefs_vec
.length () > MAX_DATAREFS_NUM
)
2781 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2783 "Loop %d not distributed: too many memory references.\n",
2787 loop_nest
.release ();
2788 free_data_refs (datarefs_vec
);
2793 data_reference_p dref
;
2794 for (i
= 0; datarefs_vec
.iterate (i
, &dref
); ++i
)
2795 dref
->aux
= (void *) (uintptr_t) i
;
2797 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2798 dump_rdg (dump_file
, rdg
);
2800 auto_vec
<struct partition
*, 3> partitions
;
2801 rdg_build_partitions (rdg
, stmts
, &partitions
);
2803 auto_vec
<ddr_p
> alias_ddrs
;
2805 auto_bitmap stmt_in_all_partitions
;
2806 bitmap_copy (stmt_in_all_partitions
, partitions
[0]->stmts
);
2807 for (i
= 1; partitions
.iterate (i
, &partition
); ++i
)
2808 bitmap_and_into (stmt_in_all_partitions
, partitions
[i
]->stmts
);
2810 any_builtin
= false;
2811 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
2813 classify_partition (loop
, rdg
, partition
, stmt_in_all_partitions
);
2814 any_builtin
|= partition_builtin_p (partition
);
2817 /* If we are only distributing patterns but did not detect any,
2819 if (!flag_tree_loop_distribution
2826 /* If we are only distributing patterns fuse all partitions that
2827 were not classified as builtins. This also avoids chopping
2828 a loop into pieces, separated by builtin calls. That is, we
2829 only want no or a single loop body remaining. */
2830 struct partition
*into
;
2831 if (!flag_tree_loop_distribution
)
2833 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
2834 if (!partition_builtin_p (into
))
2836 for (++i
; partitions
.iterate (i
, &partition
); ++i
)
2837 if (!partition_builtin_p (partition
))
2839 partition_merge_into (NULL
, into
, partition
, FUSE_NON_BUILTIN
);
2840 partitions
.unordered_remove (i
);
2841 partition_free (partition
);
2846 /* Due to limitations in the transform phase we have to fuse all
2847 reduction partitions into the last partition so the existing
2848 loop will contain all loop-closed PHI nodes. */
2849 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
2850 if (partition_reduction_p (into
))
2852 for (i
= i
+ 1; partitions
.iterate (i
, &partition
); ++i
)
2853 if (partition_reduction_p (partition
))
2855 partition_merge_into (rdg
, into
, partition
, FUSE_REDUCTION
);
2856 partitions
.unordered_remove (i
);
2857 partition_free (partition
);
2861 /* Apply our simple cost model - fuse partitions with similar
2863 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
2865 bool changed
= false;
2866 if (partition_builtin_p (into
) || into
->kind
== PKIND_PARTIAL_MEMSET
)
2869 partitions
.iterate (j
, &partition
); ++j
)
2871 if (share_memory_accesses (rdg
, into
, partition
))
2873 partition_merge_into (rdg
, into
, partition
, FUSE_SHARE_REF
);
2874 partitions
.unordered_remove (j
);
2875 partition_free (partition
);
2880 /* If we fused 0 1 2 in step 1 to 0,2 1 as 0 and 2 have similar
2881 accesses when 1 and 2 have similar accesses but not 0 and 1
2882 then in the next iteration we will fail to consider merging
2883 1 into 0,2. So try again if we did any merging into 0. */
2888 /* Build the partition dependency graph and fuse partitions in strong
2889 connected component. */
2890 if (partitions
.length () > 1)
2892 /* Don't support loop nest distribution under runtime alias check
2893 since it's not likely to enable many vectorization opportunities.
2894 Also if loop has any data reference which may be not addressable
2895 since alias check needs to take, compare address of the object. */
2896 if (loop
->inner
|| has_nonaddressable_dataref_p
)
2897 merge_dep_scc_partitions (rdg
, &partitions
, false);
2900 merge_dep_scc_partitions (rdg
, &partitions
, true);
2901 if (partitions
.length () > 1)
2902 break_alias_scc_partitions (rdg
, &partitions
, &alias_ddrs
);
2906 finalize_partitions (loop
, &partitions
, &alias_ddrs
);
2908 nbp
= partitions
.length ();
2910 || (nbp
== 1 && !partition_builtin_p (partitions
[0]))
2911 || (nbp
> 1 && partition_contains_all_rw (rdg
, partitions
)))
2917 if (version_for_distribution_p (&partitions
, &alias_ddrs
))
2918 version_loop_by_alias_check (&partitions
, loop
, &alias_ddrs
);
2920 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2923 "distribute loop <%d> into partitions:\n", loop
->num
);
2924 dump_rdg_partitions (dump_file
, partitions
);
2927 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
2929 if (partition_builtin_p (partition
))
2931 *destroy_p
|= generate_code_for_partition (loop
, partition
, i
< nbp
- 1);
2935 loop_nest
.release ();
2936 free_data_refs (datarefs_vec
);
2937 for (hash_table
<ddr_hasher
>::iterator iter
= ddrs_table
->begin ();
2938 iter
!= ddrs_table
->end (); ++iter
)
2940 free_dependence_relation (*iter
);
2945 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
2946 partition_free (partition
);
2949 return nbp
- *nb_calls
;
2952 /* Distribute all loops in the current function. */
2956 const pass_data pass_data_loop_distribution
=
2958 GIMPLE_PASS
, /* type */
2960 OPTGROUP_LOOP
, /* optinfo_flags */
2961 TV_TREE_LOOP_DISTRIBUTION
, /* tv_id */
2962 ( PROP_cfg
| PROP_ssa
), /* properties_required */
2963 0, /* properties_provided */
2964 0, /* properties_destroyed */
2965 0, /* todo_flags_start */
2966 0, /* todo_flags_finish */
2969 class pass_loop_distribution
: public gimple_opt_pass
2972 pass_loop_distribution (gcc::context
*ctxt
)
2973 : gimple_opt_pass (pass_data_loop_distribution
, ctxt
)
2976 /* opt_pass methods: */
2977 virtual bool gate (function
*)
2979 return flag_tree_loop_distribution
2980 || flag_tree_loop_distribute_patterns
;
2983 virtual unsigned int execute (function
*);
2985 }; // class pass_loop_distribution
2988 /* Given LOOP, this function records seed statements for distribution in
2989 WORK_LIST. Return false if there is nothing for distribution. */
2992 find_seed_stmts_for_distribution (struct loop
*loop
, vec
<gimple
*> *work_list
)
2994 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
2996 /* Initialize the worklist with stmts we seed the partitions with. */
2997 for (unsigned i
= 0; i
< loop
->num_nodes
; ++i
)
2999 for (gphi_iterator gsi
= gsi_start_phis (bbs
[i
]);
3000 !gsi_end_p (gsi
); gsi_next (&gsi
))
3002 gphi
*phi
= gsi
.phi ();
3003 if (virtual_operand_p (gimple_phi_result (phi
)))
3005 /* Distribute stmts which have defs that are used outside of
3007 if (!stmt_has_scalar_dependences_outside_loop (loop
, phi
))
3009 work_list
->safe_push (phi
);
3011 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]);
3012 !gsi_end_p (gsi
); gsi_next (&gsi
))
3014 gimple
*stmt
= gsi_stmt (gsi
);
3016 /* If there is a stmt with side-effects bail out - we
3017 cannot and should not distribute this loop. */
3018 if (gimple_has_side_effects (stmt
))
3024 /* Distribute stmts which have defs that are used outside of
3026 if (stmt_has_scalar_dependences_outside_loop (loop
, stmt
))
3028 /* Otherwise only distribute stores for now. */
3029 else if (!gimple_vdef (stmt
))
3032 work_list
->safe_push (stmt
);
3036 return work_list
->length () > 0;
3039 /* Given innermost LOOP, return the outermost enclosing loop that forms a
3040 perfect loop nest. */
3042 static struct loop
*
3043 prepare_perfect_loop_nest (struct loop
*loop
)
3045 struct loop
*outer
= loop_outer (loop
);
3046 tree niters
= number_of_latch_executions (loop
);
3048 /* TODO: We only support the innermost 3-level loop nest distribution
3049 because of compilation time issue for now. This should be relaxed
3050 in the future. Note we only allow 3-level loop nest distribution
3051 when parallelizing loops. */
3052 while ((loop
->inner
== NULL
3053 || (loop
->inner
->inner
== NULL
&& flag_tree_parallelize_loops
> 1))
3054 && loop_outer (outer
)
3055 && outer
->inner
== loop
&& loop
->next
== NULL
3056 && single_exit (outer
)
3057 && optimize_loop_for_speed_p (outer
)
3058 && !chrec_contains_symbols_defined_in_loop (niters
, outer
->num
)
3059 && (niters
= number_of_latch_executions (outer
)) != NULL_TREE
3060 && niters
!= chrec_dont_know
)
3063 outer
= loop_outer (loop
);
3070 pass_loop_distribution::execute (function
*fun
)
3073 bool changed
= false;
3075 control_dependences
*cd
= NULL
;
3076 auto_vec
<loop_p
> loops_to_be_destroyed
;
3078 if (number_of_loops (fun
) <= 1)
3081 /* Compute topological order for basic blocks. Topological order is
3082 needed because data dependence is computed for data references in
3083 lexicographical order. */
3084 if (bb_top_order_index
== NULL
)
3087 int *rpo
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
3089 bb_top_order_index
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
3090 bb_top_order_index_size
= last_basic_block_for_fn (cfun
);
3091 rpo_num
= pre_and_rev_post_order_compute_fn (cfun
, NULL
, rpo
, true);
3092 for (int i
= 0; i
< rpo_num
; i
++)
3093 bb_top_order_index
[rpo
[i
]] = i
;
3098 FOR_ALL_BB_FN (bb
, fun
)
3100 gimple_stmt_iterator gsi
;
3101 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3102 gimple_set_uid (gsi_stmt (gsi
), -1);
3103 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3104 gimple_set_uid (gsi_stmt (gsi
), -1);
3107 /* We can at the moment only distribute non-nested loops, thus restrict
3108 walking to innermost loops. */
3109 FOR_EACH_LOOP (loop
, LI_ONLY_INNERMOST
)
3111 /* Don't distribute multiple exit edges loop, or cold loop. */
3112 if (!single_exit (loop
)
3113 || !optimize_loop_for_speed_p (loop
))
3116 /* Don't distribute loop if niters is unknown. */
3117 tree niters
= number_of_latch_executions (loop
);
3118 if (niters
== NULL_TREE
|| niters
== chrec_dont_know
)
3121 /* Get the perfect loop nest for distribution. */
3122 loop
= prepare_perfect_loop_nest (loop
);
3123 for (; loop
; loop
= loop
->inner
)
3125 auto_vec
<gimple
*> work_list
;
3126 if (!find_seed_stmts_for_distribution (loop
, &work_list
))
3129 const char *str
= loop
->inner
? " nest" : "";
3130 dump_user_location_t loc
= find_loop_location (loop
);
3133 calculate_dominance_info (CDI_DOMINATORS
);
3134 calculate_dominance_info (CDI_POST_DOMINATORS
);
3135 cd
= new control_dependences ();
3136 free_dominance_info (CDI_POST_DOMINATORS
);
3140 int nb_generated_loops
, nb_generated_calls
;
3141 nb_generated_loops
= distribute_loop (loop
, work_list
, cd
,
3142 &nb_generated_calls
,
3145 loops_to_be_destroyed
.safe_push (loop
);
3147 if (nb_generated_loops
+ nb_generated_calls
> 0)
3150 if (dump_enabled_p ())
3151 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
,
3152 loc
, "Loop%s %d distributed: split to %d loops "
3153 "and %d library calls.\n", str
, loop
->num
,
3154 nb_generated_loops
, nb_generated_calls
);
3159 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3160 fprintf (dump_file
, "Loop%s %d not distributed.\n", str
, loop
->num
);
3167 if (bb_top_order_index
!= NULL
)
3169 free (bb_top_order_index
);
3170 bb_top_order_index
= NULL
;
3171 bb_top_order_index_size
= 0;
3176 /* Destroy loop bodies that could not be reused. Do this late as we
3177 otherwise can end up refering to stale data in control dependences. */
3179 FOR_EACH_VEC_ELT (loops_to_be_destroyed
, i
, loop
)
3180 destroy_loop (loop
);
3182 /* Cached scalar evolutions now may refer to wrong or non-existing
3185 mark_virtual_operands_for_renaming (fun
);
3186 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
3189 checking_verify_loop_structure ();
3191 return changed
? TODO_cleanup_cfg
: 0;
3197 make_pass_loop_distribution (gcc::context
*ctxt
)
3199 return new pass_loop_distribution (ctxt
);