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"
118 #include "gimple-fold.h"
121 #define MAX_DATAREFS_NUM \
122 ((unsigned) PARAM_VALUE (PARAM_LOOP_MAX_DATAREFS_FOR_DATADEPS))
124 /* Threshold controlling number of distributed partitions. Given it may
125 be unnecessary if a memory stream cost model is invented in the future,
126 we define it as a temporary macro, rather than a parameter. */
127 #define NUM_PARTITION_THRESHOLD (4)
129 /* Hashtable helpers. */
131 struct ddr_hasher
: nofree_ptr_hash
<struct data_dependence_relation
>
133 static inline hashval_t
hash (const data_dependence_relation
*);
134 static inline bool equal (const data_dependence_relation
*,
135 const data_dependence_relation
*);
138 /* Hash function for data dependence. */
141 ddr_hasher::hash (const data_dependence_relation
*ddr
)
144 h
.add_ptr (DDR_A (ddr
));
145 h
.add_ptr (DDR_B (ddr
));
149 /* Hash table equality function for data dependence. */
152 ddr_hasher::equal (const data_dependence_relation
*ddr1
,
153 const data_dependence_relation
*ddr2
)
155 return (DDR_A (ddr1
) == DDR_A (ddr2
) && DDR_B (ddr1
) == DDR_B (ddr2
));
158 /* The loop (nest) to be distributed. */
159 static vec
<loop_p
> loop_nest
;
161 /* Vector of data references in the loop to be distributed. */
162 static vec
<data_reference_p
> datarefs_vec
;
164 /* If there is nonaddressable data reference in above vector. */
165 static bool has_nonaddressable_dataref_p
;
167 /* Store index of data reference in aux field. */
168 #define DR_INDEX(dr) ((uintptr_t) (dr)->aux)
170 /* Hash table for data dependence relation in the loop to be distributed. */
171 static hash_table
<ddr_hasher
> *ddrs_table
;
173 /* A Reduced Dependence Graph (RDG) vertex representing a statement. */
176 /* The statement represented by this vertex. */
179 /* Vector of data-references in this statement. */
180 vec
<data_reference_p
> datarefs
;
182 /* True when the statement contains a write to memory. */
185 /* True when the statement contains a read from memory. */
189 #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
190 #define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs
191 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
192 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
193 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
194 #define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I]))
195 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
196 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
198 /* Data dependence type. */
202 /* Read After Write (RAW). */
205 /* Control dependence (execute conditional on). */
209 /* Dependence information attached to an edge of the RDG. */
213 /* Type of the dependence. */
214 enum rdg_dep_type type
;
217 #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
219 /* Dump vertex I in RDG to FILE. */
222 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
224 struct vertex
*v
= &(rdg
->vertices
[i
]);
225 struct graph_edge
*e
;
227 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
228 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
229 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
232 for (e
= v
->pred
; e
; e
= e
->pred_next
)
233 fprintf (file
, " %d", e
->src
);
235 fprintf (file
, ") (out:");
238 for (e
= v
->succ
; e
; e
= e
->succ_next
)
239 fprintf (file
, " %d", e
->dest
);
241 fprintf (file
, ")\n");
242 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
243 fprintf (file
, ")\n");
246 /* Call dump_rdg_vertex on stderr. */
249 debug_rdg_vertex (struct graph
*rdg
, int i
)
251 dump_rdg_vertex (stderr
, rdg
, i
);
254 /* Dump the reduced dependence graph RDG to FILE. */
257 dump_rdg (FILE *file
, struct graph
*rdg
)
259 fprintf (file
, "(rdg\n");
260 for (int i
= 0; i
< rdg
->n_vertices
; i
++)
261 dump_rdg_vertex (file
, rdg
, i
);
262 fprintf (file
, ")\n");
265 /* Call dump_rdg on stderr. */
268 debug_rdg (struct graph
*rdg
)
270 dump_rdg (stderr
, rdg
);
274 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
277 pretty_printer buffer
;
278 pp_needs_newline (&buffer
) = false;
279 buffer
.buffer
->stream
= file
;
281 fprintf (file
, "digraph RDG {\n");
283 for (i
= 0; i
< rdg
->n_vertices
; i
++)
285 struct vertex
*v
= &(rdg
->vertices
[i
]);
286 struct graph_edge
*e
;
288 fprintf (file
, "%d [label=\"[%d] ", i
, i
);
289 pp_gimple_stmt_1 (&buffer
, RDGV_STMT (v
), 0, TDF_SLIM
);
291 fprintf (file
, "\"]\n");
293 /* Highlight reads from memory. */
294 if (RDG_MEM_READS_STMT (rdg
, i
))
295 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
297 /* Highlight stores to memory. */
298 if (RDG_MEM_WRITE_STMT (rdg
, i
))
299 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
302 for (e
= v
->succ
; e
; e
= e
->succ_next
)
303 switch (RDGE_TYPE (e
))
306 /* These are the most common dependences: don't print these. */
307 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
311 fprintf (file
, "%d -> %d [label=control] \n", i
, e
->dest
);
319 fprintf (file
, "}\n\n");
322 /* Display the Reduced Dependence Graph using dotty. */
325 dot_rdg (struct graph
*rdg
)
327 /* When debugging, you may want to enable the following code. */
329 FILE *file
= popen ("dot -Tx11", "w");
332 dot_rdg_1 (file
, rdg
);
334 close (fileno (file
));
337 dot_rdg_1 (stderr
, rdg
);
341 /* Returns the index of STMT in RDG. */
344 rdg_vertex_for_stmt (struct graph
*rdg ATTRIBUTE_UNUSED
, gimple
*stmt
)
346 int index
= gimple_uid (stmt
);
347 gcc_checking_assert (index
== -1 || RDG_STMT (rdg
, index
) == stmt
);
351 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
352 the index of DEF in RDG. */
355 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
357 use_operand_p imm_use_p
;
358 imm_use_iterator iterator
;
360 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
362 struct graph_edge
*e
;
363 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
368 e
= add_edge (rdg
, idef
, use
);
369 e
->data
= XNEW (struct rdg_edge
);
370 RDGE_TYPE (e
) = flow_dd
;
374 /* Creates an edge for the control dependences of BB to the vertex V. */
377 create_edge_for_control_dependence (struct graph
*rdg
, basic_block bb
,
378 int v
, control_dependences
*cd
)
382 EXECUTE_IF_SET_IN_BITMAP (cd
->get_edges_dependent_on (bb
->index
),
385 basic_block cond_bb
= cd
->get_edge_src (edge_n
);
386 gimple
*stmt
= last_stmt (cond_bb
);
387 if (stmt
&& is_ctrl_stmt (stmt
))
389 struct graph_edge
*e
;
390 int c
= rdg_vertex_for_stmt (rdg
, stmt
);
394 e
= add_edge (rdg
, c
, v
);
395 e
->data
= XNEW (struct rdg_edge
);
396 RDGE_TYPE (e
) = control_dd
;
401 /* Creates the edges of the reduced dependence graph RDG. */
404 create_rdg_flow_edges (struct graph
*rdg
)
410 for (i
= 0; i
< rdg
->n_vertices
; i
++)
411 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
413 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
416 /* Creates the edges of the reduced dependence graph RDG. */
419 create_rdg_cd_edges (struct graph
*rdg
, control_dependences
*cd
, loop_p loop
)
423 for (i
= 0; i
< rdg
->n_vertices
; i
++)
425 gimple
*stmt
= RDG_STMT (rdg
, i
);
426 if (gimple_code (stmt
) == GIMPLE_PHI
)
430 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->preds
)
431 if (flow_bb_inside_loop_p (loop
, e
->src
))
432 create_edge_for_control_dependence (rdg
, e
->src
, i
, cd
);
435 create_edge_for_control_dependence (rdg
, gimple_bb (stmt
), i
, cd
);
439 /* Build the vertices of the reduced dependence graph RDG. Return false
443 create_rdg_vertices (struct graph
*rdg
, vec
<gimple
*> stmts
, loop_p loop
)
448 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
450 struct vertex
*v
= &(rdg
->vertices
[i
]);
452 /* Record statement to vertex mapping. */
453 gimple_set_uid (stmt
, i
);
455 v
->data
= XNEW (struct rdg_vertex
);
456 RDGV_STMT (v
) = stmt
;
457 RDGV_DATAREFS (v
).create (0);
458 RDGV_HAS_MEM_WRITE (v
) = false;
459 RDGV_HAS_MEM_READS (v
) = false;
460 if (gimple_code (stmt
) == GIMPLE_PHI
)
463 unsigned drp
= datarefs_vec
.length ();
464 if (!find_data_references_in_stmt (loop
, stmt
, &datarefs_vec
))
466 for (unsigned j
= drp
; j
< datarefs_vec
.length (); ++j
)
468 data_reference_p dr
= datarefs_vec
[j
];
470 RDGV_HAS_MEM_READS (v
) = true;
472 RDGV_HAS_MEM_WRITE (v
) = true;
473 RDGV_DATAREFS (v
).safe_push (dr
);
474 has_nonaddressable_dataref_p
|= may_be_nonaddressable_p (dr
->ref
);
480 /* Array mapping basic block's index to its topological order. */
481 static int *bb_top_order_index
;
482 /* And size of the array. */
483 static int bb_top_order_index_size
;
485 /* If X has a smaller topological sort number than Y, returns -1;
486 if greater, returns 1. */
489 bb_top_order_cmp (const void *x
, const void *y
)
491 basic_block bb1
= *(const basic_block
*) x
;
492 basic_block bb2
= *(const basic_block
*) y
;
494 gcc_assert (bb1
->index
< bb_top_order_index_size
495 && bb2
->index
< bb_top_order_index_size
);
496 gcc_assert (bb1
== bb2
497 || bb_top_order_index
[bb1
->index
]
498 != bb_top_order_index
[bb2
->index
]);
500 return (bb_top_order_index
[bb1
->index
] - bb_top_order_index
[bb2
->index
]);
503 /* Initialize STMTS with all the statements of LOOP. We use topological
504 order to discover all statements. The order is important because
505 generate_loops_for_partition is using the same traversal for identifying
506 statements in loop copies. */
509 stmts_from_loop (class loop
*loop
, vec
<gimple
*> *stmts
)
512 basic_block
*bbs
= get_loop_body_in_custom_order (loop
, bb_top_order_cmp
);
514 for (i
= 0; i
< loop
->num_nodes
; i
++)
516 basic_block bb
= bbs
[i
];
518 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
520 if (!virtual_operand_p (gimple_phi_result (bsi
.phi ())))
521 stmts
->safe_push (bsi
.phi ());
523 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
526 gimple
*stmt
= gsi_stmt (bsi
);
527 if (gimple_code (stmt
) != GIMPLE_LABEL
&& !is_gimple_debug (stmt
))
528 stmts
->safe_push (stmt
);
535 /* Free the reduced dependence graph RDG. */
538 free_rdg (struct graph
*rdg
)
542 for (i
= 0; i
< rdg
->n_vertices
; i
++)
544 struct vertex
*v
= &(rdg
->vertices
[i
]);
545 struct graph_edge
*e
;
547 for (e
= v
->succ
; e
; e
= e
->succ_next
)
552 gimple_set_uid (RDGV_STMT (v
), -1);
553 (RDGV_DATAREFS (v
)).release ();
561 /* Build the Reduced Dependence Graph (RDG) with one vertex per statement of
562 LOOP, and one edge per flow dependence or control dependence from control
563 dependence CD. During visiting each statement, data references are also
564 collected and recorded in global data DATAREFS_VEC. */
566 static struct graph
*
567 build_rdg (class loop
*loop
, control_dependences
*cd
)
571 /* Create the RDG vertices from the stmts of the loop nest. */
572 auto_vec
<gimple
*, 10> stmts
;
573 stmts_from_loop (loop
, &stmts
);
574 rdg
= new_graph (stmts
.length ());
575 if (!create_rdg_vertices (rdg
, stmts
, loop
))
582 create_rdg_flow_edges (rdg
);
584 create_rdg_cd_edges (rdg
, cd
, loop
);
590 /* Kind of distributed loop. */
591 enum partition_kind
{
593 /* Partial memset stands for a paritition can be distributed into a loop
594 of memset calls, rather than a single memset call. It's handled just
595 like a normal parition, i.e, distributed as separate loop, no memset
598 Note: This is a hacking fix trying to distribute ZERO-ing stmt in a
599 loop nest as deep as possible. As a result, parloop achieves better
600 parallelization by parallelizing deeper loop nest. This hack should
601 be unnecessary and removed once distributed memset can be understood
602 and analyzed in data reference analysis. See PR82604 for more. */
603 PKIND_PARTIAL_MEMSET
,
604 PKIND_MEMSET
, PKIND_MEMCPY
, PKIND_MEMMOVE
607 /* Type of distributed loop. */
608 enum partition_type
{
609 /* The distributed loop can be executed parallelly. */
611 /* The distributed loop has to be executed sequentially. */
615 /* Builtin info for loop distribution. */
618 /* data-references a kind != PKIND_NORMAL partition is about. */
619 data_reference_p dst_dr
;
620 data_reference_p src_dr
;
621 /* Base address and size of memory objects operated by the builtin. Note
622 both dest and source memory objects must have the same size. */
626 /* Base and offset part of dst_base after stripping constant offset. This
627 is only used in memset builtin distribution for now. */
629 unsigned HOST_WIDE_INT dst_base_offset
;
632 /* Partition for loop distribution. */
635 /* Statements of the partition. */
637 /* True if the partition defines variable which is used outside of loop. */
640 enum partition_kind kind
;
641 enum partition_type type
;
642 /* Data references in the partition. */
644 /* Information of builtin parition. */
645 struct builtin_info
*builtin
;
649 /* Allocate and initialize a partition from BITMAP. */
652 partition_alloc (void)
654 partition
*partition
= XCNEW (struct partition
);
655 partition
->stmts
= BITMAP_ALLOC (NULL
);
656 partition
->reduction_p
= false;
657 partition
->loc
= UNKNOWN_LOCATION
;
658 partition
->kind
= PKIND_NORMAL
;
659 partition
->type
= PTYPE_PARALLEL
;
660 partition
->datarefs
= BITMAP_ALLOC (NULL
);
664 /* Free PARTITION. */
667 partition_free (partition
*partition
)
669 BITMAP_FREE (partition
->stmts
);
670 BITMAP_FREE (partition
->datarefs
);
671 if (partition
->builtin
)
672 free (partition
->builtin
);
677 /* Returns true if the partition can be generated as a builtin. */
680 partition_builtin_p (partition
*partition
)
682 return partition
->kind
> PKIND_PARTIAL_MEMSET
;
685 /* Returns true if the partition contains a reduction. */
688 partition_reduction_p (partition
*partition
)
690 return partition
->reduction_p
;
693 /* Partitions are fused because of different reasons. */
696 FUSE_NON_BUILTIN
= 0,
703 /* Description on different fusing reason. */
704 static const char *fuse_message
[] = {
705 "they are non-builtins",
706 "they have reductions",
707 "they have shared memory refs",
708 "they are in the same dependence scc",
709 "there is no point to distribute loop"};
712 update_type_for_merge (struct graph
*, partition
*, partition
*);
714 /* Merge PARTITION into the partition DEST. RDG is the reduced dependence
715 graph and we update type for result partition if it is non-NULL. */
718 partition_merge_into (struct graph
*rdg
, partition
*dest
,
719 partition
*partition
, enum fuse_type ft
)
721 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
723 fprintf (dump_file
, "Fuse partitions because %s:\n", fuse_message
[ft
]);
724 fprintf (dump_file
, " Part 1: ");
725 dump_bitmap (dump_file
, dest
->stmts
);
726 fprintf (dump_file
, " Part 2: ");
727 dump_bitmap (dump_file
, partition
->stmts
);
730 dest
->kind
= PKIND_NORMAL
;
731 if (dest
->type
== PTYPE_PARALLEL
)
732 dest
->type
= partition
->type
;
734 bitmap_ior_into (dest
->stmts
, partition
->stmts
);
735 if (partition_reduction_p (partition
))
736 dest
->reduction_p
= true;
738 /* Further check if any data dependence prevents us from executing the
739 new partition parallelly. */
740 if (dest
->type
== PTYPE_PARALLEL
&& rdg
!= NULL
)
741 update_type_for_merge (rdg
, dest
, partition
);
743 bitmap_ior_into (dest
->datarefs
, partition
->datarefs
);
747 /* Returns true when DEF is an SSA_NAME defined in LOOP and used after
751 ssa_name_has_uses_outside_loop_p (tree def
, loop_p loop
)
753 imm_use_iterator imm_iter
;
756 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
758 if (is_gimple_debug (USE_STMT (use_p
)))
761 basic_block use_bb
= gimple_bb (USE_STMT (use_p
));
762 if (!flow_bb_inside_loop_p (loop
, use_bb
))
769 /* Returns true when STMT defines a scalar variable used after the
773 stmt_has_scalar_dependences_outside_loop (loop_p loop
, gimple
*stmt
)
778 if (gimple_code (stmt
) == GIMPLE_PHI
)
779 return ssa_name_has_uses_outside_loop_p (gimple_phi_result (stmt
), loop
);
781 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
782 if (ssa_name_has_uses_outside_loop_p (DEF_FROM_PTR (def_p
), loop
))
788 /* Return a copy of LOOP placed before LOOP. */
791 copy_loop_before (class loop
*loop
)
794 edge preheader
= loop_preheader_edge (loop
);
796 initialize_original_copy_tables ();
797 res
= slpeel_tree_duplicate_loop_to_edge_cfg (loop
, NULL
, preheader
);
798 gcc_assert (res
!= NULL
);
799 free_original_copy_tables ();
800 delete_update_ssa ();
805 /* Creates an empty basic block after LOOP. */
808 create_bb_after_loop (class loop
*loop
)
810 edge exit
= single_exit (loop
);
818 /* Generate code for PARTITION from the code in LOOP. The loop is
819 copied when COPY_P is true. All the statements not flagged in the
820 PARTITION bitmap are removed from the loop or from its copy. The
821 statements are indexed in sequence inside a basic block, and the
822 basic blocks of a loop are taken in dom order. */
825 generate_loops_for_partition (class loop
*loop
, partition
*partition
,
833 int orig_loop_num
= loop
->orig_loop_num
;
834 loop
= copy_loop_before (loop
);
835 gcc_assert (loop
!= NULL
);
836 loop
->orig_loop_num
= orig_loop_num
;
837 create_preheader (loop
, CP_SIMPLE_PREHEADERS
);
838 create_bb_after_loop (loop
);
842 /* Origin number is set to the new versioned loop's num. */
843 gcc_assert (loop
->orig_loop_num
!= loop
->num
);
846 /* Remove stmts not in the PARTITION bitmap. */
847 bbs
= get_loop_body_in_dom_order (loop
);
849 if (MAY_HAVE_DEBUG_BIND_STMTS
)
850 for (i
= 0; i
< loop
->num_nodes
; i
++)
852 basic_block bb
= bbs
[i
];
854 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
857 gphi
*phi
= bsi
.phi ();
858 if (!virtual_operand_p (gimple_phi_result (phi
))
859 && !bitmap_bit_p (partition
->stmts
, gimple_uid (phi
)))
860 reset_debug_uses (phi
);
863 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
865 gimple
*stmt
= gsi_stmt (bsi
);
866 if (gimple_code (stmt
) != GIMPLE_LABEL
867 && !is_gimple_debug (stmt
)
868 && !bitmap_bit_p (partition
->stmts
, gimple_uid (stmt
)))
869 reset_debug_uses (stmt
);
873 for (i
= 0; i
< loop
->num_nodes
; i
++)
875 basic_block bb
= bbs
[i
];
876 edge inner_exit
= NULL
;
878 if (loop
!= bb
->loop_father
)
879 inner_exit
= single_exit (bb
->loop_father
);
881 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);)
883 gphi
*phi
= bsi
.phi ();
884 if (!virtual_operand_p (gimple_phi_result (phi
))
885 && !bitmap_bit_p (partition
->stmts
, gimple_uid (phi
)))
886 remove_phi_node (&bsi
, true);
891 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);)
893 gimple
*stmt
= gsi_stmt (bsi
);
894 if (gimple_code (stmt
) != GIMPLE_LABEL
895 && !is_gimple_debug (stmt
)
896 && !bitmap_bit_p (partition
->stmts
, gimple_uid (stmt
)))
898 /* In distribution of loop nest, if bb is inner loop's exit_bb,
899 we choose its exit edge/path in order to avoid generating
900 infinite loop. For all other cases, we choose an arbitrary
901 path through the empty CFG part that this unnecessary
902 control stmt controls. */
903 if (gcond
*cond_stmt
= dyn_cast
<gcond
*> (stmt
))
905 if (inner_exit
&& inner_exit
->flags
& EDGE_TRUE_VALUE
)
906 gimple_cond_make_true (cond_stmt
);
908 gimple_cond_make_false (cond_stmt
);
911 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
913 gswitch
*switch_stmt
= as_a
<gswitch
*> (stmt
);
914 gimple_switch_set_index
915 (switch_stmt
, CASE_LOW (gimple_switch_label (switch_stmt
, 1)));
920 unlink_stmt_vdef (stmt
);
921 gsi_remove (&bsi
, true);
933 /* If VAL memory representation contains the same value in all bytes,
934 return that value, otherwise return -1.
935 E.g. for 0x24242424 return 0x24, for IEEE double
936 747708026454360457216.0 return 0x44, etc. */
939 const_with_all_bytes_same (tree val
)
941 unsigned char buf
[64];
944 if (integer_zerop (val
)
945 || (TREE_CODE (val
) == CONSTRUCTOR
946 && !TREE_CLOBBER_P (val
)
947 && CONSTRUCTOR_NELTS (val
) == 0))
950 if (real_zerop (val
))
952 /* Only return 0 for +0.0, not for -0.0, which doesn't have
953 an all bytes same memory representation. Don't transform
954 -0.0 stores into +0.0 even for !HONOR_SIGNED_ZEROS. */
955 switch (TREE_CODE (val
))
958 if (!real_isneg (TREE_REAL_CST_PTR (val
)))
962 if (!const_with_all_bytes_same (TREE_REALPART (val
))
963 && !const_with_all_bytes_same (TREE_IMAGPART (val
)))
968 unsigned int count
= vector_cst_encoded_nelts (val
);
970 for (j
= 0; j
< count
; ++j
)
971 if (const_with_all_bytes_same (VECTOR_CST_ENCODED_ELT (val
, j
)))
982 if (CHAR_BIT
!= 8 || BITS_PER_UNIT
!= 8)
985 len
= native_encode_expr (val
, buf
, sizeof (buf
));
988 for (i
= 1; i
< len
; i
++)
989 if (buf
[i
] != buf
[0])
994 /* Generate a call to memset for PARTITION in LOOP. */
997 generate_memset_builtin (class loop
*loop
, partition
*partition
)
999 gimple_stmt_iterator gsi
;
1000 tree mem
, fn
, nb_bytes
;
1002 struct builtin_info
*builtin
= partition
->builtin
;
1005 /* The new statements will be placed before LOOP. */
1006 gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
1008 nb_bytes
= rewrite_to_non_trapping_overflow (builtin
->size
);
1009 nb_bytes
= force_gimple_operand_gsi (&gsi
, nb_bytes
, true, NULL_TREE
,
1010 false, GSI_CONTINUE_LINKING
);
1011 mem
= builtin
->dst_base
;
1012 mem
= force_gimple_operand_gsi (&gsi
, mem
, true, NULL_TREE
,
1013 false, GSI_CONTINUE_LINKING
);
1015 /* This exactly matches the pattern recognition in classify_partition. */
1016 val
= gimple_assign_rhs1 (DR_STMT (builtin
->dst_dr
));
1017 /* Handle constants like 0x15151515 and similarly
1018 floating point constants etc. where all bytes are the same. */
1019 int bytev
= const_with_all_bytes_same (val
);
1021 val
= build_int_cst (integer_type_node
, bytev
);
1022 else if (TREE_CODE (val
) == INTEGER_CST
)
1023 val
= fold_convert (integer_type_node
, val
);
1024 else if (!useless_type_conversion_p (integer_type_node
, TREE_TYPE (val
)))
1026 tree tem
= make_ssa_name (integer_type_node
);
1027 gimple
*cstmt
= gimple_build_assign (tem
, NOP_EXPR
, val
);
1028 gsi_insert_after (&gsi
, cstmt
, GSI_CONTINUE_LINKING
);
1032 fn
= build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET
));
1033 fn_call
= gimple_build_call (fn
, 3, mem
, val
, nb_bytes
);
1034 gimple_set_location (fn_call
, partition
->loc
);
1035 gsi_insert_after (&gsi
, fn_call
, GSI_CONTINUE_LINKING
);
1038 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1040 fprintf (dump_file
, "generated memset");
1042 fprintf (dump_file
, " zero\n");
1044 fprintf (dump_file
, "\n");
1048 /* Generate a call to memcpy for PARTITION in LOOP. */
1051 generate_memcpy_builtin (class loop
*loop
, partition
*partition
)
1053 gimple_stmt_iterator gsi
;
1055 tree dest
, src
, fn
, nb_bytes
;
1056 enum built_in_function kind
;
1057 struct builtin_info
*builtin
= partition
->builtin
;
1059 /* The new statements will be placed before LOOP. */
1060 gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
1062 nb_bytes
= rewrite_to_non_trapping_overflow (builtin
->size
);
1063 nb_bytes
= force_gimple_operand_gsi (&gsi
, nb_bytes
, true, NULL_TREE
,
1064 false, GSI_CONTINUE_LINKING
);
1065 dest
= builtin
->dst_base
;
1066 src
= builtin
->src_base
;
1067 if (partition
->kind
== PKIND_MEMCPY
1068 || ! ptr_derefs_may_alias_p (dest
, src
))
1069 kind
= BUILT_IN_MEMCPY
;
1071 kind
= BUILT_IN_MEMMOVE
;
1073 dest
= force_gimple_operand_gsi (&gsi
, dest
, true, NULL_TREE
,
1074 false, GSI_CONTINUE_LINKING
);
1075 src
= force_gimple_operand_gsi (&gsi
, src
, true, NULL_TREE
,
1076 false, GSI_CONTINUE_LINKING
);
1077 fn
= build_fold_addr_expr (builtin_decl_implicit (kind
));
1078 fn_call
= gimple_build_call (fn
, 3, dest
, src
, nb_bytes
);
1079 gimple_set_location (fn_call
, partition
->loc
);
1080 gsi_insert_after (&gsi
, fn_call
, GSI_CONTINUE_LINKING
);
1083 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1085 if (kind
== BUILT_IN_MEMCPY
)
1086 fprintf (dump_file
, "generated memcpy\n");
1088 fprintf (dump_file
, "generated memmove\n");
1092 /* Remove and destroy the loop LOOP. */
1095 destroy_loop (class loop
*loop
)
1097 unsigned nbbs
= loop
->num_nodes
;
1098 edge exit
= single_exit (loop
);
1099 basic_block src
= loop_preheader_edge (loop
)->src
, dest
= exit
->dest
;
1103 bbs
= get_loop_body_in_dom_order (loop
);
1105 gimple_stmt_iterator dst_gsi
= gsi_after_labels (exit
->dest
);
1106 bool safe_p
= single_pred_p (exit
->dest
);
1107 for (unsigned i
= 0; i
< nbbs
; ++i
)
1109 /* We have made sure to not leave any dangling uses of SSA
1110 names defined in the loop. With the exception of virtuals.
1111 Make sure we replace all uses of virtual defs that will remain
1112 outside of the loop with the bare symbol as delete_basic_block
1113 will release them. */
1114 for (gphi_iterator gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
);
1117 gphi
*phi
= gsi
.phi ();
1118 if (virtual_operand_p (gimple_phi_result (phi
)))
1119 mark_virtual_phi_result_for_renaming (phi
);
1121 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]); !gsi_end_p (gsi
);)
1123 gimple
*stmt
= gsi_stmt (gsi
);
1124 tree vdef
= gimple_vdef (stmt
);
1125 if (vdef
&& TREE_CODE (vdef
) == SSA_NAME
)
1126 mark_virtual_operand_for_renaming (vdef
);
1127 /* Also move and eventually reset debug stmts. We can leave
1128 constant values in place in case the stmt dominates the exit.
1129 ??? Non-constant values from the last iteration can be
1130 replaced with final values if we can compute them. */
1131 if (gimple_debug_bind_p (stmt
))
1133 tree val
= gimple_debug_bind_get_value (stmt
);
1134 gsi_move_before (&gsi
, &dst_gsi
);
1137 || !is_gimple_min_invariant (val
)
1138 || !dominated_by_p (CDI_DOMINATORS
, exit
->src
, bbs
[i
])))
1140 gimple_debug_bind_reset_value (stmt
);
1149 redirect_edge_pred (exit
, src
);
1150 exit
->flags
&= ~(EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
1151 exit
->flags
|= EDGE_FALLTHRU
;
1152 cancel_loop_tree (loop
);
1153 rescan_loop_exit (exit
, false, true);
1159 delete_basic_block (bbs
[i
]);
1165 set_immediate_dominator (CDI_DOMINATORS
, dest
,
1166 recompute_dominator (CDI_DOMINATORS
, dest
));
1169 /* Generates code for PARTITION. Return whether LOOP needs to be destroyed. */
1172 generate_code_for_partition (class loop
*loop
,
1173 partition
*partition
, bool copy_p
)
1175 switch (partition
->kind
)
1178 case PKIND_PARTIAL_MEMSET
:
1179 /* Reductions all have to be in the last partition. */
1180 gcc_assert (!partition_reduction_p (partition
)
1182 generate_loops_for_partition (loop
, partition
, copy_p
);
1186 generate_memset_builtin (loop
, partition
);
1191 generate_memcpy_builtin (loop
, partition
);
1198 /* Common tail for partitions we turn into a call. If this was the last
1199 partition for which we generate code, we have to destroy the loop. */
1205 /* Return data dependence relation for data references A and B. The two
1206 data references must be in lexicographic order wrto reduced dependence
1207 graph RDG. We firstly try to find ddr from global ddr hash table. If
1208 it doesn't exist, compute the ddr and cache it. */
1210 static data_dependence_relation
*
1211 get_data_dependence (struct graph
*rdg
, data_reference_p a
, data_reference_p b
)
1213 struct data_dependence_relation ent
, **slot
;
1214 struct data_dependence_relation
*ddr
;
1216 gcc_assert (DR_IS_WRITE (a
) || DR_IS_WRITE (b
));
1217 gcc_assert (rdg_vertex_for_stmt (rdg
, DR_STMT (a
))
1218 <= rdg_vertex_for_stmt (rdg
, DR_STMT (b
)));
1221 slot
= ddrs_table
->find_slot (&ent
, INSERT
);
1224 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
1225 compute_affine_dependence (ddr
, loop_nest
[0]);
1232 /* In reduced dependence graph RDG for loop distribution, return true if
1233 dependence between references DR1 and DR2 leads to a dependence cycle
1234 and such dependence cycle can't be resolved by runtime alias check. */
1237 data_dep_in_cycle_p (struct graph
*rdg
,
1238 data_reference_p dr1
, data_reference_p dr2
)
1240 struct data_dependence_relation
*ddr
;
1242 /* Re-shuffle data-refs to be in topological order. */
1243 if (rdg_vertex_for_stmt (rdg
, DR_STMT (dr1
))
1244 > rdg_vertex_for_stmt (rdg
, DR_STMT (dr2
)))
1245 std::swap (dr1
, dr2
);
1247 ddr
= get_data_dependence (rdg
, dr1
, dr2
);
1249 /* In case of no data dependence. */
1250 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
1252 /* For unknown data dependence or known data dependence which can't be
1253 expressed in classic distance vector, we check if it can be resolved
1254 by runtime alias check. If yes, we still consider data dependence
1255 as won't introduce data dependence cycle. */
1256 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
1257 || DDR_NUM_DIST_VECTS (ddr
) == 0)
1258 return !runtime_alias_check_p (ddr
, NULL
, true);
1259 else if (DDR_NUM_DIST_VECTS (ddr
) > 1)
1261 else if (DDR_REVERSED_P (ddr
)
1262 || lambda_vector_zerop (DDR_DIST_VECT (ddr
, 0), 1))
1268 /* Given reduced dependence graph RDG, PARTITION1 and PARTITION2, update
1269 PARTITION1's type after merging PARTITION2 into PARTITION1. */
1272 update_type_for_merge (struct graph
*rdg
,
1273 partition
*partition1
, partition
*partition2
)
1276 bitmap_iterator bi
, bj
;
1277 data_reference_p dr1
, dr2
;
1279 EXECUTE_IF_SET_IN_BITMAP (partition1
->datarefs
, 0, i
, bi
)
1281 unsigned start
= (partition1
== partition2
) ? i
+ 1 : 0;
1283 dr1
= datarefs_vec
[i
];
1284 EXECUTE_IF_SET_IN_BITMAP (partition2
->datarefs
, start
, j
, bj
)
1286 dr2
= datarefs_vec
[j
];
1287 if (DR_IS_READ (dr1
) && DR_IS_READ (dr2
))
1290 /* Partition can only be executed sequentially if there is any
1291 data dependence cycle. */
1292 if (data_dep_in_cycle_p (rdg
, dr1
, dr2
))
1294 partition1
->type
= PTYPE_SEQUENTIAL
;
1301 /* Returns a partition with all the statements needed for computing
1302 the vertex V of the RDG, also including the loop exit conditions. */
1305 build_rdg_partition_for_vertex (struct graph
*rdg
, int v
)
1307 partition
*partition
= partition_alloc ();
1308 auto_vec
<int, 3> nodes
;
1311 data_reference_p dr
;
1313 graphds_dfs (rdg
, &v
, 1, &nodes
, false, NULL
);
1315 FOR_EACH_VEC_ELT (nodes
, i
, x
)
1317 bitmap_set_bit (partition
->stmts
, x
);
1319 for (j
= 0; RDG_DATAREFS (rdg
, x
).iterate (j
, &dr
); ++j
)
1321 unsigned idx
= (unsigned) DR_INDEX (dr
);
1322 gcc_assert (idx
< datarefs_vec
.length ());
1324 /* Partition can only be executed sequentially if there is any
1325 unknown data reference. */
1326 if (!DR_BASE_ADDRESS (dr
) || !DR_OFFSET (dr
)
1327 || !DR_INIT (dr
) || !DR_STEP (dr
))
1328 partition
->type
= PTYPE_SEQUENTIAL
;
1330 bitmap_set_bit (partition
->datarefs
, idx
);
1334 if (partition
->type
== PTYPE_SEQUENTIAL
)
1337 /* Further check if any data dependence prevents us from executing the
1338 partition parallelly. */
1339 update_type_for_merge (rdg
, partition
, partition
);
1344 /* Given PARTITION of LOOP and RDG, record single load/store data references
1345 for builtin partition in SRC_DR/DST_DR, return false if there is no such
1349 find_single_drs (class loop
*loop
, struct graph
*rdg
, partition
*partition
,
1350 data_reference_p
*dst_dr
, data_reference_p
*src_dr
)
1353 data_reference_p single_ld
= NULL
, single_st
= NULL
;
1356 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, bi
)
1358 gimple
*stmt
= RDG_STMT (rdg
, i
);
1359 data_reference_p dr
;
1361 if (gimple_code (stmt
) == GIMPLE_PHI
)
1364 /* Any scalar stmts are ok. */
1365 if (!gimple_vuse (stmt
))
1368 /* Otherwise just regular loads/stores. */
1369 if (!gimple_assign_single_p (stmt
))
1372 /* But exactly one store and/or load. */
1373 for (unsigned j
= 0; RDG_DATAREFS (rdg
, i
).iterate (j
, &dr
); ++j
)
1375 tree type
= TREE_TYPE (DR_REF (dr
));
1377 /* The memset, memcpy and memmove library calls are only
1378 able to deal with generic address space. */
1379 if (!ADDR_SPACE_GENERIC_P (TYPE_ADDR_SPACE (type
)))
1382 if (DR_IS_READ (dr
))
1384 if (single_ld
!= NULL
)
1390 if (single_st
!= NULL
)
1400 /* Bail out if this is a bitfield memory reference. */
1401 if (TREE_CODE (DR_REF (single_st
)) == COMPONENT_REF
1402 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_st
), 1)))
1405 /* Data reference must be executed exactly once per iteration of each
1406 loop in the loop nest. We only need to check dominance information
1407 against the outermost one in a perfect loop nest because a bb can't
1408 dominate outermost loop's latch without dominating inner loop's. */
1409 basic_block bb_st
= gimple_bb (DR_STMT (single_st
));
1410 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb_st
))
1415 gimple
*store
= DR_STMT (single_st
), *load
= DR_STMT (single_ld
);
1416 /* Direct aggregate copy or via an SSA name temporary. */
1418 && gimple_assign_lhs (load
) != gimple_assign_rhs1 (store
))
1421 /* Bail out if this is a bitfield memory reference. */
1422 if (TREE_CODE (DR_REF (single_ld
)) == COMPONENT_REF
1423 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_ld
), 1)))
1426 /* Load and store must be in the same loop nest. */
1427 basic_block bb_ld
= gimple_bb (DR_STMT (single_ld
));
1428 if (bb_st
->loop_father
!= bb_ld
->loop_father
)
1431 /* Data reference must be executed exactly once per iteration.
1432 Same as single_st, we only need to check against the outermost
1434 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb_ld
))
1437 edge e
= single_exit (bb_st
->loop_father
);
1438 bool dom_ld
= dominated_by_p (CDI_DOMINATORS
, e
->src
, bb_ld
);
1439 bool dom_st
= dominated_by_p (CDI_DOMINATORS
, e
->src
, bb_st
);
1440 if (dom_ld
!= dom_st
)
1444 *src_dr
= single_ld
;
1445 *dst_dr
= single_st
;
1449 /* Given data reference DR in LOOP_NEST, this function checks the enclosing
1450 loops from inner to outer to see if loop's step equals to access size at
1451 each level of loop. Return 2 if we can prove this at all level loops;
1452 record access base and size in BASE and SIZE; save loop's step at each
1453 level of loop in STEPS if it is not null. For example:
1455 int arr[100][100][100];
1456 for (i = 0; i < 100; i++) ;steps[2] = 40000
1457 for (j = 100; j > 0; j--) ;steps[1] = -400
1458 for (k = 0; k < 100; k++) ;steps[0] = 4
1459 arr[i][j - 1][k] = 0; ;base = &arr, size = 4000000
1461 Return 1 if we can prove the equality at the innermost loop, but not all
1462 level loops. In this case, no information is recorded.
1464 Return 0 if no equality can be proven at any level loops. */
1467 compute_access_range (loop_p loop_nest
, data_reference_p dr
, tree
*base
,
1468 tree
*size
, vec
<tree
> *steps
= NULL
)
1470 location_t loc
= gimple_location (DR_STMT (dr
));
1471 basic_block bb
= gimple_bb (DR_STMT (dr
));
1472 class loop
*loop
= bb
->loop_father
;
1473 tree ref
= DR_REF (dr
);
1474 tree access_base
= build_fold_addr_expr (ref
);
1475 tree access_size
= TYPE_SIZE_UNIT (TREE_TYPE (ref
));
1479 tree scev_fn
= analyze_scalar_evolution (loop
, access_base
);
1480 if (TREE_CODE (scev_fn
) != POLYNOMIAL_CHREC
)
1483 access_base
= CHREC_LEFT (scev_fn
);
1484 if (tree_contains_chrecs (access_base
, NULL
))
1487 tree scev_step
= CHREC_RIGHT (scev_fn
);
1488 /* Only support constant steps. */
1489 if (TREE_CODE (scev_step
) != INTEGER_CST
)
1492 enum ev_direction access_dir
= scev_direction (scev_fn
);
1493 if (access_dir
== EV_DIR_UNKNOWN
)
1497 steps
->safe_push (scev_step
);
1499 scev_step
= fold_convert_loc (loc
, sizetype
, scev_step
);
1500 /* Compute absolute value of scev step. */
1501 if (access_dir
== EV_DIR_DECREASES
)
1502 scev_step
= fold_build1_loc (loc
, NEGATE_EXPR
, sizetype
, scev_step
);
1504 /* At each level of loop, scev step must equal to access size. In other
1505 words, DR must access consecutive memory between loop iterations. */
1506 if (!operand_equal_p (scev_step
, access_size
, 0))
1509 /* Access stride can be computed for data reference at least for the
1513 /* Compute DR's execution times in loop. */
1514 tree niters
= number_of_latch_executions (loop
);
1515 niters
= fold_convert_loc (loc
, sizetype
, niters
);
1516 if (dominated_by_p (CDI_DOMINATORS
, single_exit (loop
)->src
, bb
))
1517 niters
= size_binop_loc (loc
, PLUS_EXPR
, niters
, size_one_node
);
1519 /* Compute DR's overall access size in loop. */
1520 access_size
= fold_build2_loc (loc
, MULT_EXPR
, sizetype
,
1522 /* Adjust base address in case of negative step. */
1523 if (access_dir
== EV_DIR_DECREASES
)
1525 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, sizetype
,
1526 scev_step
, access_size
);
1527 access_base
= fold_build_pointer_plus_loc (loc
, access_base
, adj
);
1529 } while (loop
!= loop_nest
&& (loop
= loop_outer (loop
)) != NULL
);
1531 *base
= access_base
;
1532 *size
= access_size
;
1533 /* Access stride can be computed for data reference at each level loop. */
1537 /* Allocate and return builtin struct. Record information like DST_DR,
1538 SRC_DR, DST_BASE, SRC_BASE and SIZE in the allocated struct. */
1540 static struct builtin_info
*
1541 alloc_builtin (data_reference_p dst_dr
, data_reference_p src_dr
,
1542 tree dst_base
, tree src_base
, tree size
)
1544 struct builtin_info
*builtin
= XNEW (struct builtin_info
);
1545 builtin
->dst_dr
= dst_dr
;
1546 builtin
->src_dr
= src_dr
;
1547 builtin
->dst_base
= dst_base
;
1548 builtin
->src_base
= src_base
;
1549 builtin
->size
= size
;
1553 /* Given data reference DR in loop nest LOOP, classify if it forms builtin
1557 classify_builtin_st (loop_p loop
, partition
*partition
, data_reference_p dr
)
1559 gimple
*stmt
= DR_STMT (dr
);
1560 tree base
, size
, rhs
= gimple_assign_rhs1 (stmt
);
1562 if (const_with_all_bytes_same (rhs
) == -1
1563 && (!INTEGRAL_TYPE_P (TREE_TYPE (rhs
))
1564 || (TYPE_MODE (TREE_TYPE (rhs
))
1565 != TYPE_MODE (unsigned_char_type_node
))))
1568 if (TREE_CODE (rhs
) == SSA_NAME
1569 && !SSA_NAME_IS_DEFAULT_DEF (rhs
)
1570 && flow_bb_inside_loop_p (loop
, gimple_bb (SSA_NAME_DEF_STMT (rhs
))))
1573 int res
= compute_access_range (loop
, dr
, &base
, &size
);
1578 partition
->kind
= PKIND_PARTIAL_MEMSET
;
1582 poly_uint64 base_offset
;
1583 unsigned HOST_WIDE_INT const_base_offset
;
1584 tree base_base
= strip_offset (base
, &base_offset
);
1585 if (!base_offset
.is_constant (&const_base_offset
))
1588 struct builtin_info
*builtin
;
1589 builtin
= alloc_builtin (dr
, NULL
, base
, NULL_TREE
, size
);
1590 builtin
->dst_base_base
= base_base
;
1591 builtin
->dst_base_offset
= const_base_offset
;
1592 partition
->builtin
= builtin
;
1593 partition
->kind
= PKIND_MEMSET
;
1596 /* Given data references DST_DR and SRC_DR in loop nest LOOP and RDG, classify
1597 if it forms builtin memcpy or memmove call. */
1600 classify_builtin_ldst (loop_p loop
, struct graph
*rdg
, partition
*partition
,
1601 data_reference_p dst_dr
, data_reference_p src_dr
)
1603 tree base
, size
, src_base
, src_size
;
1604 auto_vec
<tree
> dst_steps
, src_steps
;
1606 /* Compute access range of both load and store. */
1607 int res
= compute_access_range (loop
, dst_dr
, &base
, &size
, &dst_steps
);
1610 res
= compute_access_range (loop
, src_dr
, &src_base
, &src_size
, &src_steps
);
1614 /* They much have the same access size. */
1615 if (!operand_equal_p (size
, src_size
, 0))
1618 /* Load and store in loop nest must access memory in the same way, i.e,
1619 their must have the same steps in each loop of the nest. */
1620 if (dst_steps
.length () != src_steps
.length ())
1622 for (unsigned i
= 0; i
< dst_steps
.length (); ++i
)
1623 if (!operand_equal_p (dst_steps
[i
], src_steps
[i
], 0))
1626 /* Now check that if there is a dependence. */
1627 ddr_p ddr
= get_data_dependence (rdg
, src_dr
, dst_dr
);
1629 /* Classify as memcpy if no dependence between load and store. */
1630 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
1632 partition
->builtin
= alloc_builtin (dst_dr
, src_dr
, base
, src_base
, size
);
1633 partition
->kind
= PKIND_MEMCPY
;
1637 /* Can't do memmove in case of unknown dependence or dependence without
1638 classical distance vector. */
1639 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
1640 || DDR_NUM_DIST_VECTS (ddr
) == 0)
1644 lambda_vector dist_v
;
1645 int num_lev
= (DDR_LOOP_NEST (ddr
)).length ();
1646 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
1648 unsigned dep_lev
= dependence_level (dist_v
, num_lev
);
1649 /* Can't do memmove if load depends on store. */
1650 if (dep_lev
> 0 && dist_v
[dep_lev
- 1] > 0 && !DDR_REVERSED_P (ddr
))
1654 partition
->builtin
= alloc_builtin (dst_dr
, src_dr
, base
, src_base
, size
);
1655 partition
->kind
= PKIND_MEMMOVE
;
1659 /* Classifies the builtin kind we can generate for PARTITION of RDG and LOOP.
1660 For the moment we detect memset, memcpy and memmove patterns. Bitmap
1661 STMT_IN_ALL_PARTITIONS contains statements belonging to all partitions.
1662 Returns true if there is a reduction in all partitions and we
1663 possibly did not mark PARTITION as having one for this reason. */
1666 classify_partition (loop_p loop
, struct graph
*rdg
, partition
*partition
,
1667 bitmap stmt_in_all_partitions
)
1671 data_reference_p single_ld
= NULL
, single_st
= NULL
;
1672 bool volatiles_p
= false, has_reduction
= false;
1674 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, bi
)
1676 gimple
*stmt
= RDG_STMT (rdg
, i
);
1678 if (gimple_has_volatile_ops (stmt
))
1681 /* If the stmt is not included by all partitions and there is uses
1682 outside of the loop, then mark the partition as reduction. */
1683 if (stmt_has_scalar_dependences_outside_loop (loop
, stmt
))
1685 /* Due to limitation in the transform phase we have to fuse all
1686 reduction partitions. As a result, this could cancel valid
1687 loop distribution especially for loop that induction variable
1688 is used outside of loop. To workaround this issue, we skip
1689 marking partition as reudction if the reduction stmt belongs
1690 to all partitions. In such case, reduction will be computed
1691 correctly no matter how partitions are fused/distributed. */
1692 if (!bitmap_bit_p (stmt_in_all_partitions
, i
))
1693 partition
->reduction_p
= true;
1695 has_reduction
= true;
1699 /* Simple workaround to prevent classifying the partition as builtin
1700 if it contains any use outside of loop. For the case where all
1701 partitions have the reduction this simple workaround is delayed
1702 to only affect the last partition. */
1703 if (partition
->reduction_p
)
1704 return has_reduction
;
1706 /* Perform general partition disqualification for builtins. */
1708 || !flag_tree_loop_distribute_patterns
)
1709 return has_reduction
;
1711 /* Find single load/store data references for builtin partition. */
1712 if (!find_single_drs (loop
, rdg
, partition
, &single_st
, &single_ld
))
1713 return has_reduction
;
1715 partition
->loc
= gimple_location (DR_STMT (single_st
));
1717 /* Classify the builtin kind. */
1718 if (single_ld
== NULL
)
1719 classify_builtin_st (loop
, partition
, single_st
);
1721 classify_builtin_ldst (loop
, rdg
, partition
, single_st
, single_ld
);
1722 return has_reduction
;
1725 /* Returns true when PARTITION1 and PARTITION2 access the same memory
1729 share_memory_accesses (struct graph
*rdg
,
1730 partition
*partition1
, partition
*partition2
)
1733 bitmap_iterator bi
, bj
;
1734 data_reference_p dr1
, dr2
;
1736 /* First check whether in the intersection of the two partitions are
1737 any loads or stores. Common loads are the situation that happens
1739 EXECUTE_IF_AND_IN_BITMAP (partition1
->stmts
, partition2
->stmts
, 0, i
, bi
)
1740 if (RDG_MEM_WRITE_STMT (rdg
, i
)
1741 || RDG_MEM_READS_STMT (rdg
, i
))
1744 /* Then check whether the two partitions access the same memory object. */
1745 EXECUTE_IF_SET_IN_BITMAP (partition1
->datarefs
, 0, i
, bi
)
1747 dr1
= datarefs_vec
[i
];
1749 if (!DR_BASE_ADDRESS (dr1
)
1750 || !DR_OFFSET (dr1
) || !DR_INIT (dr1
) || !DR_STEP (dr1
))
1753 EXECUTE_IF_SET_IN_BITMAP (partition2
->datarefs
, 0, j
, bj
)
1755 dr2
= datarefs_vec
[j
];
1757 if (!DR_BASE_ADDRESS (dr2
)
1758 || !DR_OFFSET (dr2
) || !DR_INIT (dr2
) || !DR_STEP (dr2
))
1761 if (operand_equal_p (DR_BASE_ADDRESS (dr1
), DR_BASE_ADDRESS (dr2
), 0)
1762 && operand_equal_p (DR_OFFSET (dr1
), DR_OFFSET (dr2
), 0)
1763 && operand_equal_p (DR_INIT (dr1
), DR_INIT (dr2
), 0)
1764 && operand_equal_p (DR_STEP (dr1
), DR_STEP (dr2
), 0))
1772 /* For each seed statement in STARTING_STMTS, this function builds
1773 partition for it by adding depended statements according to RDG.
1774 All partitions are recorded in PARTITIONS. */
1777 rdg_build_partitions (struct graph
*rdg
,
1778 vec
<gimple
*> starting_stmts
,
1779 vec
<partition
*> *partitions
)
1781 auto_bitmap processed
;
1785 FOR_EACH_VEC_ELT (starting_stmts
, i
, stmt
)
1787 int v
= rdg_vertex_for_stmt (rdg
, stmt
);
1789 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1791 "ldist asked to generate code for vertex %d\n", v
);
1793 /* If the vertex is already contained in another partition so
1794 is the partition rooted at it. */
1795 if (bitmap_bit_p (processed
, v
))
1798 partition
*partition
= build_rdg_partition_for_vertex (rdg
, v
);
1799 bitmap_ior_into (processed
, partition
->stmts
);
1801 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1803 fprintf (dump_file
, "ldist creates useful %s partition:\n",
1804 partition
->type
== PTYPE_PARALLEL
? "parallel" : "sequent");
1805 bitmap_print (dump_file
, partition
->stmts
, " ", "\n");
1808 partitions
->safe_push (partition
);
1811 /* All vertices should have been assigned to at least one partition now,
1812 other than vertices belonging to dead code. */
1815 /* Dump to FILE the PARTITIONS. */
1818 dump_rdg_partitions (FILE *file
, vec
<partition
*> partitions
)
1821 partition
*partition
;
1823 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1824 debug_bitmap_file (file
, partition
->stmts
);
1827 /* Debug PARTITIONS. */
1828 extern void debug_rdg_partitions (vec
<partition
*> );
1831 debug_rdg_partitions (vec
<partition
*> partitions
)
1833 dump_rdg_partitions (stderr
, partitions
);
1836 /* Returns the number of read and write operations in the RDG. */
1839 number_of_rw_in_rdg (struct graph
*rdg
)
1843 for (i
= 0; i
< rdg
->n_vertices
; i
++)
1845 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1848 if (RDG_MEM_READS_STMT (rdg
, i
))
1855 /* Returns the number of read and write operations in a PARTITION of
1859 number_of_rw_in_partition (struct graph
*rdg
, partition
*partition
)
1865 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, ii
)
1867 if (RDG_MEM_WRITE_STMT (rdg
, i
))
1870 if (RDG_MEM_READS_STMT (rdg
, i
))
1877 /* Returns true when one of the PARTITIONS contains all the read or
1878 write operations of RDG. */
1881 partition_contains_all_rw (struct graph
*rdg
,
1882 vec
<partition
*> partitions
)
1885 partition
*partition
;
1886 int nrw
= number_of_rw_in_rdg (rdg
);
1888 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
1889 if (nrw
== number_of_rw_in_partition (rdg
, partition
))
1895 /* Compute partition dependence created by the data references in DRS1
1896 and DRS2, modify and return DIR according to that. IF ALIAS_DDR is
1897 not NULL, we record dependence introduced by possible alias between
1898 two data references in ALIAS_DDRS; otherwise, we simply ignore such
1899 dependence as if it doesn't exist at all. */
1902 pg_add_dependence_edges (struct graph
*rdg
, int dir
,
1903 bitmap drs1
, bitmap drs2
, vec
<ddr_p
> *alias_ddrs
)
1906 bitmap_iterator bi
, bj
;
1907 data_reference_p dr1
, dr2
, saved_dr1
;
1909 /* dependence direction - 0 is no dependence, -1 is back,
1910 1 is forth, 2 is both (we can stop then, merging will occur). */
1911 EXECUTE_IF_SET_IN_BITMAP (drs1
, 0, i
, bi
)
1913 dr1
= datarefs_vec
[i
];
1915 EXECUTE_IF_SET_IN_BITMAP (drs2
, 0, j
, bj
)
1917 int res
, this_dir
= 1;
1920 dr2
= datarefs_vec
[j
];
1922 /* Skip all <read, read> data dependence. */
1923 if (DR_IS_READ (dr1
) && DR_IS_READ (dr2
))
1927 /* Re-shuffle data-refs to be in topological order. */
1928 if (rdg_vertex_for_stmt (rdg
, DR_STMT (dr1
))
1929 > rdg_vertex_for_stmt (rdg
, DR_STMT (dr2
)))
1931 std::swap (dr1
, dr2
);
1932 this_dir
= -this_dir
;
1934 ddr
= get_data_dependence (rdg
, dr1
, dr2
);
1935 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
1938 res
= data_ref_compare_tree (DR_BASE_ADDRESS (dr1
),
1939 DR_BASE_ADDRESS (dr2
));
1940 /* Be conservative. If data references are not well analyzed,
1941 or the two data references have the same base address and
1942 offset, add dependence and consider it alias to each other.
1943 In other words, the dependence cannot be resolved by
1944 runtime alias check. */
1945 if (!DR_BASE_ADDRESS (dr1
) || !DR_BASE_ADDRESS (dr2
)
1946 || !DR_OFFSET (dr1
) || !DR_OFFSET (dr2
)
1947 || !DR_INIT (dr1
) || !DR_INIT (dr2
)
1948 || !DR_STEP (dr1
) || !tree_fits_uhwi_p (DR_STEP (dr1
))
1949 || !DR_STEP (dr2
) || !tree_fits_uhwi_p (DR_STEP (dr2
))
1952 /* Data dependence could be resolved by runtime alias check,
1953 record it in ALIAS_DDRS. */
1954 else if (alias_ddrs
!= NULL
)
1955 alias_ddrs
->safe_push (ddr
);
1956 /* Or simply ignore it. */
1958 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
1960 if (DDR_REVERSED_P (ddr
))
1961 this_dir
= -this_dir
;
1963 /* Known dependences can still be unordered througout the
1964 iteration space, see gcc.dg/tree-ssa/ldist-16.c. */
1965 if (DDR_NUM_DIST_VECTS (ddr
) != 1)
1967 /* If the overlap is exact preserve stmt order. */
1968 else if (lambda_vector_zerop (DDR_DIST_VECT (ddr
, 0),
1969 DDR_NB_LOOPS (ddr
)))
1971 /* Else as the distance vector is lexicographic positive swap
1972 the dependence direction. */
1974 this_dir
= -this_dir
;
1982 else if (this_dir
!= 0 && dir
!= this_dir
)
1984 /* Shuffle "back" dr1. */
1991 /* Compare postorder number of the partition graph vertices V1 and V2. */
1994 pgcmp (const void *v1_
, const void *v2_
)
1996 const vertex
*v1
= (const vertex
*)v1_
;
1997 const vertex
*v2
= (const vertex
*)v2_
;
1998 return v2
->post
- v1
->post
;
2001 /* Data attached to vertices of partition dependence graph. */
2004 /* ID of the corresponding partition. */
2006 /* The partition. */
2007 struct partition
*partition
;
2010 /* Data attached to edges of partition dependence graph. */
2013 /* If the dependence edge can be resolved by runtime alias check,
2014 this vector contains data dependence relations for runtime alias
2015 check. On the other hand, if the dependence edge is introduced
2016 because of compilation time known data dependence, this vector
2017 contains nothing. */
2018 vec
<ddr_p
> alias_ddrs
;
2021 /* Callback data for traversing edges in graph. */
2022 struct pg_edge_callback_data
2024 /* Bitmap contains strong connected components should be merged. */
2025 bitmap sccs_to_merge
;
2026 /* Array constains component information for all vertices. */
2027 int *vertices_component
;
2028 /* Vector to record all data dependence relations which are needed
2029 to break strong connected components by runtime alias checks. */
2030 vec
<ddr_p
> *alias_ddrs
;
2033 /* Initialize vertice's data for partition dependence graph PG with
2037 init_partition_graph_vertices (struct graph
*pg
,
2038 vec
<struct partition
*> *partitions
)
2041 partition
*partition
;
2042 struct pg_vdata
*data
;
2044 for (i
= 0; partitions
->iterate (i
, &partition
); ++i
)
2046 data
= new pg_vdata
;
2047 pg
->vertices
[i
].data
= data
;
2049 data
->partition
= partition
;
2053 /* Add edge <I, J> to partition dependence graph PG. Attach vector of data
2054 dependence relations to the EDGE if DDRS isn't NULL. */
2057 add_partition_graph_edge (struct graph
*pg
, int i
, int j
, vec
<ddr_p
> *ddrs
)
2059 struct graph_edge
*e
= add_edge (pg
, i
, j
);
2061 /* If the edge is attached with data dependence relations, it means this
2062 dependence edge can be resolved by runtime alias checks. */
2065 struct pg_edata
*data
= new pg_edata
;
2067 gcc_assert (ddrs
->length () > 0);
2069 data
->alias_ddrs
= vNULL
;
2070 data
->alias_ddrs
.safe_splice (*ddrs
);
2074 /* Callback function for graph travesal algorithm. It returns true
2075 if edge E should skipped when traversing the graph. */
2078 pg_skip_alias_edge (struct graph_edge
*e
)
2080 struct pg_edata
*data
= (struct pg_edata
*)e
->data
;
2081 return (data
!= NULL
&& data
->alias_ddrs
.length () > 0);
2084 /* Callback function freeing data attached to edge E of graph. */
2087 free_partition_graph_edata_cb (struct graph
*, struct graph_edge
*e
, void *)
2089 if (e
->data
!= NULL
)
2091 struct pg_edata
*data
= (struct pg_edata
*)e
->data
;
2092 data
->alias_ddrs
.release ();
2097 /* Free data attached to vertice of partition dependence graph PG. */
2100 free_partition_graph_vdata (struct graph
*pg
)
2103 struct pg_vdata
*data
;
2105 for (i
= 0; i
< pg
->n_vertices
; ++i
)
2107 data
= (struct pg_vdata
*)pg
->vertices
[i
].data
;
2112 /* Build and return partition dependence graph for PARTITIONS. RDG is
2113 reduced dependence graph for the loop to be distributed. If IGNORE_ALIAS_P
2114 is true, data dependence caused by possible alias between references
2115 is ignored, as if it doesn't exist at all; otherwise all depdendences
2118 static struct graph
*
2119 build_partition_graph (struct graph
*rdg
,
2120 vec
<struct partition
*> *partitions
,
2121 bool ignore_alias_p
)
2124 struct partition
*partition1
, *partition2
;
2125 graph
*pg
= new_graph (partitions
->length ());
2126 auto_vec
<ddr_p
> alias_ddrs
, *alias_ddrs_p
;
2128 alias_ddrs_p
= ignore_alias_p
? NULL
: &alias_ddrs
;
2130 init_partition_graph_vertices (pg
, partitions
);
2132 for (i
= 0; partitions
->iterate (i
, &partition1
); ++i
)
2134 for (j
= i
+ 1; partitions
->iterate (j
, &partition2
); ++j
)
2136 /* dependence direction - 0 is no dependence, -1 is back,
2137 1 is forth, 2 is both (we can stop then, merging will occur). */
2140 /* If the first partition has reduction, add back edge; if the
2141 second partition has reduction, add forth edge. This makes
2142 sure that reduction partition will be sorted as the last one. */
2143 if (partition_reduction_p (partition1
))
2145 else if (partition_reduction_p (partition2
))
2148 /* Cleanup the temporary vector. */
2149 alias_ddrs
.truncate (0);
2151 dir
= pg_add_dependence_edges (rdg
, dir
, partition1
->datarefs
,
2152 partition2
->datarefs
, alias_ddrs_p
);
2154 /* Add edge to partition graph if there exists dependence. There
2155 are two types of edges. One type edge is caused by compilation
2156 time known dependence, this type cannot be resolved by runtime
2157 alias check. The other type can be resolved by runtime alias
2159 if (dir
== 1 || dir
== 2
2160 || alias_ddrs
.length () > 0)
2162 /* Attach data dependence relations to edge that can be resolved
2163 by runtime alias check. */
2164 bool alias_edge_p
= (dir
!= 1 && dir
!= 2);
2165 add_partition_graph_edge (pg
, i
, j
,
2166 (alias_edge_p
) ? &alias_ddrs
: NULL
);
2168 if (dir
== -1 || dir
== 2
2169 || alias_ddrs
.length () > 0)
2171 /* Attach data dependence relations to edge that can be resolved
2172 by runtime alias check. */
2173 bool alias_edge_p
= (dir
!= -1 && dir
!= 2);
2174 add_partition_graph_edge (pg
, j
, i
,
2175 (alias_edge_p
) ? &alias_ddrs
: NULL
);
2182 /* Sort partitions in PG in descending post order and store them in
2186 sort_partitions_by_post_order (struct graph
*pg
,
2187 vec
<struct partition
*> *partitions
)
2190 struct pg_vdata
*data
;
2192 /* Now order the remaining nodes in descending postorder. */
2193 qsort (pg
->vertices
, pg
->n_vertices
, sizeof (vertex
), pgcmp
);
2194 partitions
->truncate (0);
2195 for (i
= 0; i
< pg
->n_vertices
; ++i
)
2197 data
= (struct pg_vdata
*)pg
->vertices
[i
].data
;
2198 if (data
->partition
)
2199 partitions
->safe_push (data
->partition
);
2203 /* Given reduced dependence graph RDG merge strong connected components
2204 of PARTITIONS. If IGNORE_ALIAS_P is true, data dependence caused by
2205 possible alias between references is ignored, as if it doesn't exist
2206 at all; otherwise all depdendences are considered. */
2209 merge_dep_scc_partitions (struct graph
*rdg
,
2210 vec
<struct partition
*> *partitions
,
2211 bool ignore_alias_p
)
2213 struct partition
*partition1
, *partition2
;
2214 struct pg_vdata
*data
;
2215 graph
*pg
= build_partition_graph (rdg
, partitions
, ignore_alias_p
);
2216 int i
, j
, num_sccs
= graphds_scc (pg
, NULL
);
2218 /* Strong connected compoenent means dependence cycle, we cannot distribute
2219 them. So fuse them together. */
2220 if ((unsigned) num_sccs
< partitions
->length ())
2222 for (i
= 0; i
< num_sccs
; ++i
)
2224 for (j
= 0; partitions
->iterate (j
, &partition1
); ++j
)
2225 if (pg
->vertices
[j
].component
== i
)
2227 for (j
= j
+ 1; partitions
->iterate (j
, &partition2
); ++j
)
2228 if (pg
->vertices
[j
].component
== i
)
2230 partition_merge_into (NULL
, partition1
,
2231 partition2
, FUSE_SAME_SCC
);
2232 partition1
->type
= PTYPE_SEQUENTIAL
;
2233 (*partitions
)[j
] = NULL
;
2234 partition_free (partition2
);
2235 data
= (struct pg_vdata
*)pg
->vertices
[j
].data
;
2236 data
->partition
= NULL
;
2241 sort_partitions_by_post_order (pg
, partitions
);
2242 gcc_assert (partitions
->length () == (unsigned)num_sccs
);
2243 free_partition_graph_vdata (pg
);
2247 /* Callback function for traversing edge E in graph G. DATA is private
2251 pg_collect_alias_ddrs (struct graph
*g
, struct graph_edge
*e
, void *data
)
2253 int i
, j
, component
;
2254 struct pg_edge_callback_data
*cbdata
;
2255 struct pg_edata
*edata
= (struct pg_edata
*) e
->data
;
2257 /* If the edge doesn't have attached data dependence, it represents
2258 compilation time known dependences. This type dependence cannot
2259 be resolved by runtime alias check. */
2260 if (edata
== NULL
|| edata
->alias_ddrs
.length () == 0)
2263 cbdata
= (struct pg_edge_callback_data
*) data
;
2266 component
= cbdata
->vertices_component
[i
];
2267 /* Vertices are topologically sorted according to compilation time
2268 known dependences, so we can break strong connected components
2269 by removing edges of the opposite direction, i.e, edges pointing
2270 from vertice with smaller post number to vertice with bigger post
2272 if (g
->vertices
[i
].post
< g
->vertices
[j
].post
2273 /* We only need to remove edges connecting vertices in the same
2274 strong connected component to break it. */
2275 && component
== cbdata
->vertices_component
[j
]
2276 /* Check if we want to break the strong connected component or not. */
2277 && !bitmap_bit_p (cbdata
->sccs_to_merge
, component
))
2278 cbdata
->alias_ddrs
->safe_splice (edata
->alias_ddrs
);
2281 /* This is the main function breaking strong conected components in
2282 PARTITIONS giving reduced depdendence graph RDG. Store data dependence
2283 relations for runtime alias check in ALIAS_DDRS. */
2286 break_alias_scc_partitions (struct graph
*rdg
,
2287 vec
<struct partition
*> *partitions
,
2288 vec
<ddr_p
> *alias_ddrs
)
2290 int i
, j
, k
, num_sccs
, num_sccs_no_alias
;
2291 /* Build partition dependence graph. */
2292 graph
*pg
= build_partition_graph (rdg
, partitions
, false);
2294 alias_ddrs
->truncate (0);
2295 /* Find strong connected components in the graph, with all dependence edges
2297 num_sccs
= graphds_scc (pg
, NULL
);
2298 /* All SCCs now can be broken by runtime alias checks because SCCs caused by
2299 compilation time known dependences are merged before this function. */
2300 if ((unsigned) num_sccs
< partitions
->length ())
2302 struct pg_edge_callback_data cbdata
;
2303 auto_bitmap sccs_to_merge
;
2304 auto_vec
<enum partition_type
> scc_types
;
2305 struct partition
*partition
, *first
;
2307 /* If all partitions in a SCC have the same type, we can simply merge the
2308 SCC. This loop finds out such SCCS and record them in bitmap. */
2309 bitmap_set_range (sccs_to_merge
, 0, (unsigned) num_sccs
);
2310 for (i
= 0; i
< num_sccs
; ++i
)
2312 for (j
= 0; partitions
->iterate (j
, &first
); ++j
)
2313 if (pg
->vertices
[j
].component
== i
)
2316 bool same_type
= true, all_builtins
= partition_builtin_p (first
);
2317 for (++j
; partitions
->iterate (j
, &partition
); ++j
)
2319 if (pg
->vertices
[j
].component
!= i
)
2322 if (first
->type
!= partition
->type
)
2327 all_builtins
&= partition_builtin_p (partition
);
2329 /* Merge SCC if all partitions in SCC have the same type, though the
2330 result partition is sequential, because vectorizer can do better
2331 runtime alias check. One expecption is all partitions in SCC are
2333 if (!same_type
|| all_builtins
)
2334 bitmap_clear_bit (sccs_to_merge
, i
);
2337 /* Initialize callback data for traversing. */
2338 cbdata
.sccs_to_merge
= sccs_to_merge
;
2339 cbdata
.alias_ddrs
= alias_ddrs
;
2340 cbdata
.vertices_component
= XNEWVEC (int, pg
->n_vertices
);
2341 /* Record the component information which will be corrupted by next
2342 graph scc finding call. */
2343 for (i
= 0; i
< pg
->n_vertices
; ++i
)
2344 cbdata
.vertices_component
[i
] = pg
->vertices
[i
].component
;
2346 /* Collect data dependences for runtime alias checks to break SCCs. */
2347 if (bitmap_count_bits (sccs_to_merge
) != (unsigned) num_sccs
)
2349 /* Run SCC finding algorithm again, with alias dependence edges
2350 skipped. This is to topologically sort partitions according to
2351 compilation time known dependence. Note the topological order
2352 is stored in the form of pg's post order number. */
2353 num_sccs_no_alias
= graphds_scc (pg
, NULL
, pg_skip_alias_edge
);
2354 gcc_assert (partitions
->length () == (unsigned) num_sccs_no_alias
);
2355 /* With topological order, we can construct two subgraphs L and R.
2356 L contains edge <x, y> where x < y in terms of post order, while
2357 R contains edge <x, y> where x > y. Edges for compilation time
2358 known dependence all fall in R, so we break SCCs by removing all
2359 (alias) edges of in subgraph L. */
2360 for_each_edge (pg
, pg_collect_alias_ddrs
, &cbdata
);
2363 /* For SCC that doesn't need to be broken, merge it. */
2364 for (i
= 0; i
< num_sccs
; ++i
)
2366 if (!bitmap_bit_p (sccs_to_merge
, i
))
2369 for (j
= 0; partitions
->iterate (j
, &first
); ++j
)
2370 if (cbdata
.vertices_component
[j
] == i
)
2372 for (k
= j
+ 1; partitions
->iterate (k
, &partition
); ++k
)
2374 struct pg_vdata
*data
;
2376 if (cbdata
.vertices_component
[k
] != i
)
2379 /* Update postorder number so that merged reduction partition is
2380 sorted after other partitions. */
2381 if (!partition_reduction_p (first
)
2382 && partition_reduction_p (partition
))
2384 gcc_assert (pg
->vertices
[k
].post
< pg
->vertices
[j
].post
);
2385 pg
->vertices
[j
].post
= pg
->vertices
[k
].post
;
2387 partition_merge_into (NULL
, first
, partition
, FUSE_SAME_SCC
);
2388 (*partitions
)[k
] = NULL
;
2389 partition_free (partition
);
2390 data
= (struct pg_vdata
*)pg
->vertices
[k
].data
;
2391 gcc_assert (data
->id
== k
);
2392 data
->partition
= NULL
;
2393 /* The result partition of merged SCC must be sequential. */
2394 first
->type
= PTYPE_SEQUENTIAL
;
2399 sort_partitions_by_post_order (pg
, partitions
);
2400 free_partition_graph_vdata (pg
);
2401 for_each_edge (pg
, free_partition_graph_edata_cb
, NULL
);
2404 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2406 fprintf (dump_file
, "Possible alias data dependence to break:\n");
2407 dump_data_dependence_relations (dump_file
, *alias_ddrs
);
2411 /* Compute and return an expression whose value is the segment length which
2412 will be accessed by DR in NITERS iterations. */
2415 data_ref_segment_size (struct data_reference
*dr
, tree niters
)
2417 niters
= size_binop (MINUS_EXPR
,
2418 fold_convert (sizetype
, niters
),
2420 return size_binop (MULT_EXPR
,
2421 fold_convert (sizetype
, DR_STEP (dr
)),
2422 fold_convert (sizetype
, niters
));
2425 /* Return true if LOOP's latch is dominated by statement for data reference
2429 latch_dominated_by_data_ref (class loop
*loop
, data_reference
*dr
)
2431 return dominated_by_p (CDI_DOMINATORS
, single_exit (loop
)->src
,
2432 gimple_bb (DR_STMT (dr
)));
2435 /* Compute alias check pairs and store them in COMP_ALIAS_PAIRS for LOOP's
2436 data dependence relations ALIAS_DDRS. */
2439 compute_alias_check_pairs (class loop
*loop
, vec
<ddr_p
> *alias_ddrs
,
2440 vec
<dr_with_seg_len_pair_t
> *comp_alias_pairs
)
2443 unsigned HOST_WIDE_INT factor
= 1;
2444 tree niters_plus_one
, niters
= number_of_latch_executions (loop
);
2446 gcc_assert (niters
!= NULL_TREE
&& niters
!= chrec_dont_know
);
2447 niters
= fold_convert (sizetype
, niters
);
2448 niters_plus_one
= size_binop (PLUS_EXPR
, niters
, size_one_node
);
2450 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2451 fprintf (dump_file
, "Creating alias check pairs:\n");
2453 /* Iterate all data dependence relations and compute alias check pairs. */
2454 for (i
= 0; i
< alias_ddrs
->length (); i
++)
2456 ddr_p ddr
= (*alias_ddrs
)[i
];
2457 struct data_reference
*dr_a
= DDR_A (ddr
);
2458 struct data_reference
*dr_b
= DDR_B (ddr
);
2459 tree seg_length_a
, seg_length_b
;
2460 int comp_res
= data_ref_compare_tree (DR_BASE_ADDRESS (dr_a
),
2461 DR_BASE_ADDRESS (dr_b
));
2464 comp_res
= data_ref_compare_tree (DR_OFFSET (dr_a
), DR_OFFSET (dr_b
));
2465 gcc_assert (comp_res
!= 0);
2467 if (latch_dominated_by_data_ref (loop
, dr_a
))
2468 seg_length_a
= data_ref_segment_size (dr_a
, niters_plus_one
);
2470 seg_length_a
= data_ref_segment_size (dr_a
, niters
);
2472 if (latch_dominated_by_data_ref (loop
, dr_b
))
2473 seg_length_b
= data_ref_segment_size (dr_b
, niters_plus_one
);
2475 seg_length_b
= data_ref_segment_size (dr_b
, niters
);
2477 unsigned HOST_WIDE_INT access_size_a
2478 = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a
))));
2479 unsigned HOST_WIDE_INT access_size_b
2480 = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_b
))));
2481 unsigned int align_a
= TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_a
)));
2482 unsigned int align_b
= TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_b
)));
2484 dr_with_seg_len_pair_t dr_with_seg_len_pair
2485 (dr_with_seg_len (dr_a
, seg_length_a
, access_size_a
, align_a
),
2486 dr_with_seg_len (dr_b
, seg_length_b
, access_size_b
, align_b
));
2488 /* Canonicalize pairs by sorting the two DR members. */
2490 std::swap (dr_with_seg_len_pair
.first
, dr_with_seg_len_pair
.second
);
2492 comp_alias_pairs
->safe_push (dr_with_seg_len_pair
);
2495 if (tree_fits_uhwi_p (niters
))
2496 factor
= tree_to_uhwi (niters
);
2498 /* Prune alias check pairs. */
2499 prune_runtime_alias_test_list (comp_alias_pairs
, factor
);
2500 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2502 "Improved number of alias checks from %d to %d\n",
2503 alias_ddrs
->length (), comp_alias_pairs
->length ());
2506 /* Given data dependence relations in ALIAS_DDRS, generate runtime alias
2507 checks and version LOOP under condition of these runtime alias checks. */
2510 version_loop_by_alias_check (vec
<struct partition
*> *partitions
,
2511 class loop
*loop
, vec
<ddr_p
> *alias_ddrs
)
2513 profile_probability prob
;
2514 basic_block cond_bb
;
2516 tree lhs
, arg0
, cond_expr
= NULL_TREE
;
2517 gimple_seq cond_stmts
= NULL
;
2518 gimple
*call_stmt
= NULL
;
2519 auto_vec
<dr_with_seg_len_pair_t
> comp_alias_pairs
;
2521 /* Generate code for runtime alias checks if necessary. */
2522 gcc_assert (alias_ddrs
->length () > 0);
2524 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2526 "Version loop <%d> with runtime alias check\n", loop
->num
);
2528 compute_alias_check_pairs (loop
, alias_ddrs
, &comp_alias_pairs
);
2529 create_runtime_alias_checks (loop
, &comp_alias_pairs
, &cond_expr
);
2530 cond_expr
= force_gimple_operand_1 (cond_expr
, &cond_stmts
,
2531 is_gimple_val
, NULL_TREE
);
2533 /* Depend on vectorizer to fold IFN_LOOP_DIST_ALIAS. */
2534 bool cancelable_p
= flag_tree_loop_vectorize
;
2538 struct partition
*partition
;
2539 for (; partitions
->iterate (i
, &partition
); ++i
)
2540 if (!partition_builtin_p (partition
))
2543 /* If all partitions are builtins, distributing it would be profitable and
2544 we don't want to cancel the runtime alias checks. */
2545 if (i
== partitions
->length ())
2546 cancelable_p
= false;
2549 /* Generate internal function call for loop distribution alias check if the
2550 runtime alias check should be cancelable. */
2553 call_stmt
= gimple_build_call_internal (IFN_LOOP_DIST_ALIAS
,
2554 2, NULL_TREE
, cond_expr
);
2555 lhs
= make_ssa_name (boolean_type_node
);
2556 gimple_call_set_lhs (call_stmt
, lhs
);
2561 prob
= profile_probability::guessed_always ().apply_scale (9, 10);
2562 initialize_original_copy_tables ();
2563 nloop
= loop_version (loop
, lhs
, &cond_bb
, prob
, prob
.invert (),
2564 prob
, prob
.invert (), true);
2565 free_original_copy_tables ();
2566 /* Record the original loop number in newly generated loops. In case of
2567 distribution, the original loop will be distributed and the new loop
2569 loop
->orig_loop_num
= nloop
->num
;
2570 nloop
->orig_loop_num
= nloop
->num
;
2571 nloop
->dont_vectorize
= true;
2572 nloop
->force_vectorize
= false;
2576 /* Record new loop's num in IFN_LOOP_DIST_ALIAS because the original
2577 loop could be destroyed. */
2578 arg0
= build_int_cst (integer_type_node
, loop
->orig_loop_num
);
2579 gimple_call_set_arg (call_stmt
, 0, arg0
);
2580 gimple_seq_add_stmt_without_update (&cond_stmts
, call_stmt
);
2585 gimple_stmt_iterator cond_gsi
= gsi_last_bb (cond_bb
);
2586 gsi_insert_seq_before (&cond_gsi
, cond_stmts
, GSI_SAME_STMT
);
2588 update_ssa (TODO_update_ssa
);
2591 /* Return true if loop versioning is needed to distrubute PARTITIONS.
2592 ALIAS_DDRS are data dependence relations for runtime alias check. */
2595 version_for_distribution_p (vec
<struct partition
*> *partitions
,
2596 vec
<ddr_p
> *alias_ddrs
)
2598 /* No need to version loop if we have only one partition. */
2599 if (partitions
->length () == 1)
2602 /* Need to version loop if runtime alias check is necessary. */
2603 return (alias_ddrs
->length () > 0);
2606 /* Compare base offset of builtin mem* partitions P1 and P2. */
2609 offset_cmp (const void *vp1
, const void *vp2
)
2611 struct partition
*p1
= *(struct partition
*const *) vp1
;
2612 struct partition
*p2
= *(struct partition
*const *) vp2
;
2613 unsigned HOST_WIDE_INT o1
= p1
->builtin
->dst_base_offset
;
2614 unsigned HOST_WIDE_INT o2
= p2
->builtin
->dst_base_offset
;
2615 return (o2
< o1
) - (o1
< o2
);
2618 /* Fuse adjacent memset builtin PARTITIONS if possible. This is a special
2619 case optimization transforming below code:
2621 __builtin_memset (&obj, 0, 100);
2623 __builtin_memset (_1, 0, 200);
2625 __builtin_memset (_2, 0, 100);
2629 __builtin_memset (&obj, 0, 400);
2631 Note we don't have dependence information between different partitions
2632 at this point, as a result, we can't handle nonadjacent memset builtin
2633 partitions since dependence might be broken. */
2636 fuse_memset_builtins (vec
<struct partition
*> *partitions
)
2639 struct partition
*part1
, *part2
;
2642 for (i
= 0; partitions
->iterate (i
, &part1
);)
2644 if (part1
->kind
!= PKIND_MEMSET
)
2650 /* Find sub-array of memset builtins of the same base. Index range
2651 of the sub-array is [i, j) with "j > i". */
2652 for (j
= i
+ 1; partitions
->iterate (j
, &part2
); ++j
)
2654 if (part2
->kind
!= PKIND_MEMSET
2655 || !operand_equal_p (part1
->builtin
->dst_base_base
,
2656 part2
->builtin
->dst_base_base
, 0))
2659 /* Memset calls setting different values can't be merged. */
2660 rhs1
= gimple_assign_rhs1 (DR_STMT (part1
->builtin
->dst_dr
));
2661 rhs2
= gimple_assign_rhs1 (DR_STMT (part2
->builtin
->dst_dr
));
2662 if (!operand_equal_p (rhs1
, rhs2
, 0))
2666 /* Stable sort is required in order to avoid breaking dependence. */
2667 gcc_stablesort (&(*partitions
)[i
], j
- i
, sizeof (*partitions
)[i
],
2669 /* Continue with next partition. */
2673 /* Merge all consecutive memset builtin partitions. */
2674 for (i
= 0; i
< partitions
->length () - 1;)
2676 part1
= (*partitions
)[i
];
2677 if (part1
->kind
!= PKIND_MEMSET
)
2683 part2
= (*partitions
)[i
+ 1];
2684 /* Only merge memset partitions of the same base and with constant
2686 if (part2
->kind
!= PKIND_MEMSET
2687 || TREE_CODE (part1
->builtin
->size
) != INTEGER_CST
2688 || TREE_CODE (part2
->builtin
->size
) != INTEGER_CST
2689 || !operand_equal_p (part1
->builtin
->dst_base_base
,
2690 part2
->builtin
->dst_base_base
, 0))
2695 rhs1
= gimple_assign_rhs1 (DR_STMT (part1
->builtin
->dst_dr
));
2696 rhs2
= gimple_assign_rhs1 (DR_STMT (part2
->builtin
->dst_dr
));
2697 int bytev1
= const_with_all_bytes_same (rhs1
);
2698 int bytev2
= const_with_all_bytes_same (rhs2
);
2699 /* Only merge memset partitions of the same value. */
2700 if (bytev1
!= bytev2
|| bytev1
== -1)
2705 wide_int end1
= wi::add (part1
->builtin
->dst_base_offset
,
2706 wi::to_wide (part1
->builtin
->size
));
2707 /* Only merge adjacent memset partitions. */
2708 if (wi::ne_p (end1
, part2
->builtin
->dst_base_offset
))
2713 /* Merge partitions[i] and partitions[i+1]. */
2714 part1
->builtin
->size
= fold_build2 (PLUS_EXPR
, sizetype
,
2715 part1
->builtin
->size
,
2716 part2
->builtin
->size
);
2717 partition_free (part2
);
2718 partitions
->ordered_remove (i
+ 1);
2722 /* Fuse PARTITIONS of LOOP if necessary before finalizing distribution.
2723 ALIAS_DDRS contains ddrs which need runtime alias check. */
2726 finalize_partitions (class loop
*loop
, vec
<struct partition
*> *partitions
,
2727 vec
<ddr_p
> *alias_ddrs
)
2730 struct partition
*partition
, *a
;
2732 if (partitions
->length () == 1
2733 || alias_ddrs
->length () > 0)
2736 unsigned num_builtin
= 0, num_normal
= 0, num_partial_memset
= 0;
2737 bool same_type_p
= true;
2738 enum partition_type type
= ((*partitions
)[0])->type
;
2739 for (i
= 0; partitions
->iterate (i
, &partition
); ++i
)
2741 same_type_p
&= (type
== partition
->type
);
2742 if (partition_builtin_p (partition
))
2748 if (partition
->kind
== PKIND_PARTIAL_MEMSET
)
2749 num_partial_memset
++;
2752 /* Don't distribute current loop into too many loops given we don't have
2753 memory stream cost model. Be even more conservative in case of loop
2754 nest distribution. */
2755 if ((same_type_p
&& num_builtin
== 0
2756 && (loop
->inner
== NULL
|| num_normal
!= 2 || num_partial_memset
!= 1))
2757 || (loop
->inner
!= NULL
2758 && i
>= NUM_PARTITION_THRESHOLD
&& num_normal
> 1)
2759 || (loop
->inner
== NULL
2760 && i
>= NUM_PARTITION_THRESHOLD
&& num_normal
> num_builtin
))
2762 a
= (*partitions
)[0];
2763 for (i
= 1; partitions
->iterate (i
, &partition
); ++i
)
2765 partition_merge_into (NULL
, a
, partition
, FUSE_FINALIZE
);
2766 partition_free (partition
);
2768 partitions
->truncate (1);
2771 /* Fuse memset builtins if possible. */
2772 if (partitions
->length () > 1)
2773 fuse_memset_builtins (partitions
);
2776 /* Distributes the code from LOOP in such a way that producer statements
2777 are placed before consumer statements. Tries to separate only the
2778 statements from STMTS into separate loops. Returns the number of
2779 distributed loops. Set NB_CALLS to number of generated builtin calls.
2780 Set *DESTROY_P to whether LOOP needs to be destroyed. */
2783 distribute_loop (class loop
*loop
, vec
<gimple
*> stmts
,
2784 control_dependences
*cd
, int *nb_calls
, bool *destroy_p
,
2785 bool only_patterns_p
)
2787 ddrs_table
= new hash_table
<ddr_hasher
> (389);
2789 partition
*partition
;
2794 loop_nest
.create (0);
2795 if (!find_loop_nest (loop
, &loop_nest
))
2797 loop_nest
.release ();
2802 datarefs_vec
.create (20);
2803 has_nonaddressable_dataref_p
= false;
2804 rdg
= build_rdg (loop
, cd
);
2807 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2809 "Loop %d not distributed: failed to build the RDG.\n",
2812 loop_nest
.release ();
2813 free_data_refs (datarefs_vec
);
2818 if (datarefs_vec
.length () > MAX_DATAREFS_NUM
)
2820 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2822 "Loop %d not distributed: too many memory references.\n",
2826 loop_nest
.release ();
2827 free_data_refs (datarefs_vec
);
2832 data_reference_p dref
;
2833 for (i
= 0; datarefs_vec
.iterate (i
, &dref
); ++i
)
2834 dref
->aux
= (void *) (uintptr_t) i
;
2836 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2837 dump_rdg (dump_file
, rdg
);
2839 auto_vec
<struct partition
*, 3> partitions
;
2840 rdg_build_partitions (rdg
, stmts
, &partitions
);
2842 auto_vec
<ddr_p
> alias_ddrs
;
2844 auto_bitmap stmt_in_all_partitions
;
2845 bitmap_copy (stmt_in_all_partitions
, partitions
[0]->stmts
);
2846 for (i
= 1; partitions
.iterate (i
, &partition
); ++i
)
2847 bitmap_and_into (stmt_in_all_partitions
, partitions
[i
]->stmts
);
2849 bool any_builtin
= false;
2850 bool reduction_in_all
= false;
2851 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
2854 |= classify_partition (loop
, rdg
, partition
, stmt_in_all_partitions
);
2855 any_builtin
|= partition_builtin_p (partition
);
2858 /* If we are only distributing patterns but did not detect any,
2867 /* If we are only distributing patterns fuse all partitions that
2868 were not classified as builtins. This also avoids chopping
2869 a loop into pieces, separated by builtin calls. That is, we
2870 only want no or a single loop body remaining. */
2871 struct partition
*into
;
2872 if (only_patterns_p
)
2874 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
2875 if (!partition_builtin_p (into
))
2877 for (++i
; partitions
.iterate (i
, &partition
); ++i
)
2878 if (!partition_builtin_p (partition
))
2880 partition_merge_into (NULL
, into
, partition
, FUSE_NON_BUILTIN
);
2881 partitions
.unordered_remove (i
);
2882 partition_free (partition
);
2887 /* Due to limitations in the transform phase we have to fuse all
2888 reduction partitions into the last partition so the existing
2889 loop will contain all loop-closed PHI nodes. */
2890 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
2891 if (partition_reduction_p (into
))
2893 for (i
= i
+ 1; partitions
.iterate (i
, &partition
); ++i
)
2894 if (partition_reduction_p (partition
))
2896 partition_merge_into (rdg
, into
, partition
, FUSE_REDUCTION
);
2897 partitions
.unordered_remove (i
);
2898 partition_free (partition
);
2902 /* Apply our simple cost model - fuse partitions with similar
2904 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
2906 bool changed
= false;
2907 if (partition_builtin_p (into
) || into
->kind
== PKIND_PARTIAL_MEMSET
)
2910 partitions
.iterate (j
, &partition
); ++j
)
2912 if (share_memory_accesses (rdg
, into
, partition
))
2914 partition_merge_into (rdg
, into
, partition
, FUSE_SHARE_REF
);
2915 partitions
.unordered_remove (j
);
2916 partition_free (partition
);
2921 /* If we fused 0 1 2 in step 1 to 0,2 1 as 0 and 2 have similar
2922 accesses when 1 and 2 have similar accesses but not 0 and 1
2923 then in the next iteration we will fail to consider merging
2924 1 into 0,2. So try again if we did any merging into 0. */
2929 /* Put a non-builtin partition last if we need to preserve a reduction.
2930 ??? This is a workaround that makes sort_partitions_by_post_order do
2931 the correct thing while in reality it should sort each component
2932 separately and then put the component with a reduction or a non-builtin
2934 if (reduction_in_all
2935 && partition_builtin_p (partitions
.last()))
2936 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
2937 if (!partition_builtin_p (partition
))
2939 partitions
.unordered_remove (i
);
2940 partitions
.quick_push (partition
);
2944 /* Build the partition dependency graph and fuse partitions in strong
2945 connected component. */
2946 if (partitions
.length () > 1)
2948 /* Don't support loop nest distribution under runtime alias check
2949 since it's not likely to enable many vectorization opportunities.
2950 Also if loop has any data reference which may be not addressable
2951 since alias check needs to take, compare address of the object. */
2952 if (loop
->inner
|| has_nonaddressable_dataref_p
)
2953 merge_dep_scc_partitions (rdg
, &partitions
, false);
2956 merge_dep_scc_partitions (rdg
, &partitions
, true);
2957 if (partitions
.length () > 1)
2958 break_alias_scc_partitions (rdg
, &partitions
, &alias_ddrs
);
2962 finalize_partitions (loop
, &partitions
, &alias_ddrs
);
2964 /* If there is a reduction in all partitions make sure the last one
2965 is not classified for builtin code generation. */
2966 if (reduction_in_all
)
2968 partition
= partitions
.last ();
2970 && partition_builtin_p (partition
)
2971 && !partition_builtin_p (partitions
[0]))
2976 partition
->kind
= PKIND_NORMAL
;
2979 nbp
= partitions
.length ();
2981 || (nbp
== 1 && !partition_builtin_p (partitions
[0]))
2982 || (nbp
> 1 && partition_contains_all_rw (rdg
, partitions
)))
2988 if (version_for_distribution_p (&partitions
, &alias_ddrs
))
2989 version_loop_by_alias_check (&partitions
, loop
, &alias_ddrs
);
2991 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2994 "distribute loop <%d> into partitions:\n", loop
->num
);
2995 dump_rdg_partitions (dump_file
, partitions
);
2998 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
3000 if (partition_builtin_p (partition
))
3002 *destroy_p
|= generate_code_for_partition (loop
, partition
, i
< nbp
- 1);
3006 loop_nest
.release ();
3007 free_data_refs (datarefs_vec
);
3008 for (hash_table
<ddr_hasher
>::iterator iter
= ddrs_table
->begin ();
3009 iter
!= ddrs_table
->end (); ++iter
)
3011 free_dependence_relation (*iter
);
3016 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
3017 partition_free (partition
);
3020 return nbp
- *nb_calls
;
3023 /* Distribute all loops in the current function. */
3027 const pass_data pass_data_loop_distribution
=
3029 GIMPLE_PASS
, /* type */
3031 OPTGROUP_LOOP
, /* optinfo_flags */
3032 TV_TREE_LOOP_DISTRIBUTION
, /* tv_id */
3033 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3034 0, /* properties_provided */
3035 0, /* properties_destroyed */
3036 0, /* todo_flags_start */
3037 0, /* todo_flags_finish */
3040 class pass_loop_distribution
: public gimple_opt_pass
3043 pass_loop_distribution (gcc::context
*ctxt
)
3044 : gimple_opt_pass (pass_data_loop_distribution
, ctxt
)
3047 /* opt_pass methods: */
3048 virtual bool gate (function
*)
3050 return flag_tree_loop_distribution
3051 || flag_tree_loop_distribute_patterns
;
3054 virtual unsigned int execute (function
*);
3056 }; // class pass_loop_distribution
3059 /* Given LOOP, this function records seed statements for distribution in
3060 WORK_LIST. Return false if there is nothing for distribution. */
3063 find_seed_stmts_for_distribution (class loop
*loop
, vec
<gimple
*> *work_list
)
3065 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
3067 /* Initialize the worklist with stmts we seed the partitions with. */
3068 for (unsigned i
= 0; i
< loop
->num_nodes
; ++i
)
3070 for (gphi_iterator gsi
= gsi_start_phis (bbs
[i
]);
3071 !gsi_end_p (gsi
); gsi_next (&gsi
))
3073 gphi
*phi
= gsi
.phi ();
3074 if (virtual_operand_p (gimple_phi_result (phi
)))
3076 /* Distribute stmts which have defs that are used outside of
3078 if (!stmt_has_scalar_dependences_outside_loop (loop
, phi
))
3080 work_list
->safe_push (phi
);
3082 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]);
3083 !gsi_end_p (gsi
); gsi_next (&gsi
))
3085 gimple
*stmt
= gsi_stmt (gsi
);
3087 /* Ignore clobbers, they do not have true side effects. */
3088 if (gimple_clobber_p (stmt
))
3091 /* If there is a stmt with side-effects bail out - we
3092 cannot and should not distribute this loop. */
3093 if (gimple_has_side_effects (stmt
))
3099 /* Distribute stmts which have defs that are used outside of
3101 if (stmt_has_scalar_dependences_outside_loop (loop
, stmt
))
3103 /* Otherwise only distribute stores for now. */
3104 else if (!gimple_vdef (stmt
))
3107 work_list
->safe_push (stmt
);
3111 return work_list
->length () > 0;
3114 /* Given innermost LOOP, return the outermost enclosing loop that forms a
3115 perfect loop nest. */
3118 prepare_perfect_loop_nest (class loop
*loop
)
3120 class loop
*outer
= loop_outer (loop
);
3121 tree niters
= number_of_latch_executions (loop
);
3123 /* TODO: We only support the innermost 3-level loop nest distribution
3124 because of compilation time issue for now. This should be relaxed
3125 in the future. Note we only allow 3-level loop nest distribution
3126 when parallelizing loops. */
3127 while ((loop
->inner
== NULL
3128 || (loop
->inner
->inner
== NULL
&& flag_tree_parallelize_loops
> 1))
3129 && loop_outer (outer
)
3130 && outer
->inner
== loop
&& loop
->next
== NULL
3131 && single_exit (outer
)
3132 && !chrec_contains_symbols_defined_in_loop (niters
, outer
->num
)
3133 && (niters
= number_of_latch_executions (outer
)) != NULL_TREE
3134 && niters
!= chrec_dont_know
)
3137 outer
= loop_outer (loop
);
3144 pass_loop_distribution::execute (function
*fun
)
3147 bool changed
= false;
3149 control_dependences
*cd
= NULL
;
3150 auto_vec
<loop_p
> loops_to_be_destroyed
;
3152 if (number_of_loops (fun
) <= 1)
3155 /* Compute topological order for basic blocks. Topological order is
3156 needed because data dependence is computed for data references in
3157 lexicographical order. */
3158 if (bb_top_order_index
== NULL
)
3161 int *rpo
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
3163 bb_top_order_index
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
3164 bb_top_order_index_size
= last_basic_block_for_fn (cfun
);
3165 rpo_num
= pre_and_rev_post_order_compute_fn (cfun
, NULL
, rpo
, true);
3166 for (int i
= 0; i
< rpo_num
; i
++)
3167 bb_top_order_index
[rpo
[i
]] = i
;
3172 FOR_ALL_BB_FN (bb
, fun
)
3174 gimple_stmt_iterator gsi
;
3175 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3176 gimple_set_uid (gsi_stmt (gsi
), -1);
3177 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3178 gimple_set_uid (gsi_stmt (gsi
), -1);
3181 /* We can at the moment only distribute non-nested loops, thus restrict
3182 walking to innermost loops. */
3183 FOR_EACH_LOOP (loop
, LI_ONLY_INNERMOST
)
3185 /* Don't distribute multiple exit edges loop, or cold loop when
3186 not doing pattern detection. */
3187 if (!single_exit (loop
)
3188 || (!flag_tree_loop_distribute_patterns
3189 && !optimize_loop_for_speed_p (loop
)))
3192 /* Don't distribute loop if niters is unknown. */
3193 tree niters
= number_of_latch_executions (loop
);
3194 if (niters
== NULL_TREE
|| niters
== chrec_dont_know
)
3197 /* Get the perfect loop nest for distribution. */
3198 loop
= prepare_perfect_loop_nest (loop
);
3199 for (; loop
; loop
= loop
->inner
)
3201 auto_vec
<gimple
*> work_list
;
3202 if (!find_seed_stmts_for_distribution (loop
, &work_list
))
3205 const char *str
= loop
->inner
? " nest" : "";
3206 dump_user_location_t loc
= find_loop_location (loop
);
3209 calculate_dominance_info (CDI_DOMINATORS
);
3210 calculate_dominance_info (CDI_POST_DOMINATORS
);
3211 cd
= new control_dependences ();
3212 free_dominance_info (CDI_POST_DOMINATORS
);
3216 int nb_generated_loops
, nb_generated_calls
;
3218 = distribute_loop (loop
, work_list
, cd
, &nb_generated_calls
,
3219 &destroy_p
, (!optimize_loop_for_speed_p (loop
)
3220 || !flag_tree_loop_distribution
));
3222 loops_to_be_destroyed
.safe_push (loop
);
3224 if (nb_generated_loops
+ nb_generated_calls
> 0)
3227 if (dump_enabled_p ())
3228 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
,
3229 loc
, "Loop%s %d distributed: split to %d loops "
3230 "and %d library calls.\n", str
, loop
->num
,
3231 nb_generated_loops
, nb_generated_calls
);
3236 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3237 fprintf (dump_file
, "Loop%s %d not distributed.\n", str
, loop
->num
);
3244 if (bb_top_order_index
!= NULL
)
3246 free (bb_top_order_index
);
3247 bb_top_order_index
= NULL
;
3248 bb_top_order_index_size
= 0;
3253 /* Destroy loop bodies that could not be reused. Do this late as we
3254 otherwise can end up refering to stale data in control dependences. */
3256 FOR_EACH_VEC_ELT (loops_to_be_destroyed
, i
, loop
)
3257 destroy_loop (loop
);
3259 /* Cached scalar evolutions now may refer to wrong or non-existing
3262 mark_virtual_operands_for_renaming (fun
);
3263 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
3266 checking_verify_loop_structure ();
3268 return changed
? TODO_cleanup_cfg
: 0;
3274 make_pass_loop_distribution (gcc::context
*ctxt
)
3276 return new pass_loop_distribution (ctxt
);