2 Copyright (C) 2006-2023 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"
115 #include "tree-vectorizer.h"
117 #include "gimple-fold.h"
118 #include "tree-affine.h"
121 #include "memmodel.h"
125 #define MAX_DATAREFS_NUM \
126 ((unsigned) param_loop_max_datarefs_for_datadeps)
128 /* Threshold controlling number of distributed partitions. Given it may
129 be unnecessary if a memory stream cost model is invented in the future,
130 we define it as a temporary macro, rather than a parameter. */
131 #define NUM_PARTITION_THRESHOLD (4)
133 /* Hashtable helpers. */
135 struct ddr_hasher
: nofree_ptr_hash
<struct data_dependence_relation
>
137 static inline hashval_t
hash (const data_dependence_relation
*);
138 static inline bool equal (const data_dependence_relation
*,
139 const data_dependence_relation
*);
142 /* Hash function for data dependence. */
145 ddr_hasher::hash (const data_dependence_relation
*ddr
)
148 h
.add_ptr (DDR_A (ddr
));
149 h
.add_ptr (DDR_B (ddr
));
153 /* Hash table equality function for data dependence. */
156 ddr_hasher::equal (const data_dependence_relation
*ddr1
,
157 const data_dependence_relation
*ddr2
)
159 return (DDR_A (ddr1
) == DDR_A (ddr2
) && DDR_B (ddr1
) == DDR_B (ddr2
));
164 #define DR_INDEX(dr) ((uintptr_t) (dr)->aux)
166 /* A Reduced Dependence Graph (RDG) vertex representing a statement. */
169 /* The statement represented by this vertex. */
172 /* Vector of data-references in this statement. */
173 vec
<data_reference_p
> datarefs
;
175 /* True when the statement contains a write to memory. */
178 /* True when the statement contains a read from memory. */
182 #define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
183 #define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs
184 #define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
185 #define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
186 #define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
187 #define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I]))
188 #define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
189 #define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
191 /* Data dependence type. */
195 /* Read After Write (RAW). */
198 /* Control dependence (execute conditional on). */
202 /* Dependence information attached to an edge of the RDG. */
206 /* Type of the dependence. */
207 enum rdg_dep_type type
;
210 #define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
212 /* Kind of distributed loop. */
213 enum partition_kind
{
215 /* Partial memset stands for a paritition can be distributed into a loop
216 of memset calls, rather than a single memset call. It's handled just
217 like a normal parition, i.e, distributed as separate loop, no memset
220 Note: This is a hacking fix trying to distribute ZERO-ing stmt in a
221 loop nest as deep as possible. As a result, parloop achieves better
222 parallelization by parallelizing deeper loop nest. This hack should
223 be unnecessary and removed once distributed memset can be understood
224 and analyzed in data reference analysis. See PR82604 for more. */
225 PKIND_PARTIAL_MEMSET
,
226 PKIND_MEMSET
, PKIND_MEMCPY
, PKIND_MEMMOVE
229 /* Type of distributed loop. */
230 enum partition_type
{
231 /* The distributed loop can be executed parallelly. */
233 /* The distributed loop has to be executed sequentially. */
237 /* Builtin info for loop distribution. */
240 /* data-references a kind != PKIND_NORMAL partition is about. */
241 data_reference_p dst_dr
;
242 data_reference_p src_dr
;
243 /* Base address and size of memory objects operated by the builtin. Note
244 both dest and source memory objects must have the same size. */
248 /* Base and offset part of dst_base after stripping constant offset. This
249 is only used in memset builtin distribution for now. */
251 unsigned HOST_WIDE_INT dst_base_offset
;
254 /* Partition for loop distribution. */
257 /* Statements of the partition. */
259 /* True if the partition defines variable which is used outside of loop. */
262 enum partition_kind kind
;
263 enum partition_type type
;
264 /* Data references in the partition. */
266 /* Information of builtin parition. */
267 struct builtin_info
*builtin
;
270 /* Partitions are fused because of different reasons. */
273 FUSE_NON_BUILTIN
= 0,
280 /* Description on different fusing reason. */
281 static const char *fuse_message
[] = {
282 "they are non-builtins",
283 "they have reductions",
284 "they have shared memory refs",
285 "they are in the same dependence scc",
286 "there is no point to distribute loop"};
289 /* Dump vertex I in RDG to FILE. */
292 dump_rdg_vertex (FILE *file
, struct graph
*rdg
, int i
)
294 struct vertex
*v
= &(rdg
->vertices
[i
]);
295 struct graph_edge
*e
;
297 fprintf (file
, "(vertex %d: (%s%s) (in:", i
,
298 RDG_MEM_WRITE_STMT (rdg
, i
) ? "w" : "",
299 RDG_MEM_READS_STMT (rdg
, i
) ? "r" : "");
302 for (e
= v
->pred
; e
; e
= e
->pred_next
)
303 fprintf (file
, " %d", e
->src
);
305 fprintf (file
, ") (out:");
308 for (e
= v
->succ
; e
; e
= e
->succ_next
)
309 fprintf (file
, " %d", e
->dest
);
311 fprintf (file
, ")\n");
312 print_gimple_stmt (file
, RDGV_STMT (v
), 0, TDF_VOPS
|TDF_MEMSYMS
);
313 fprintf (file
, ")\n");
316 /* Call dump_rdg_vertex on stderr. */
319 debug_rdg_vertex (struct graph
*rdg
, int i
)
321 dump_rdg_vertex (stderr
, rdg
, i
);
324 /* Dump the reduced dependence graph RDG to FILE. */
327 dump_rdg (FILE *file
, struct graph
*rdg
)
329 fprintf (file
, "(rdg\n");
330 for (int i
= 0; i
< rdg
->n_vertices
; i
++)
331 dump_rdg_vertex (file
, rdg
, i
);
332 fprintf (file
, ")\n");
335 /* Call dump_rdg on stderr. */
338 debug_rdg (struct graph
*rdg
)
340 dump_rdg (stderr
, rdg
);
344 dot_rdg_1 (FILE *file
, struct graph
*rdg
)
347 pretty_printer buffer
;
348 pp_needs_newline (&buffer
) = false;
349 buffer
.buffer
->stream
= file
;
351 fprintf (file
, "digraph RDG {\n");
353 for (i
= 0; i
< rdg
->n_vertices
; i
++)
355 struct vertex
*v
= &(rdg
->vertices
[i
]);
356 struct graph_edge
*e
;
358 fprintf (file
, "%d [label=\"[%d] ", i
, i
);
359 pp_gimple_stmt_1 (&buffer
, RDGV_STMT (v
), 0, TDF_SLIM
);
361 fprintf (file
, "\"]\n");
363 /* Highlight reads from memory. */
364 if (RDG_MEM_READS_STMT (rdg
, i
))
365 fprintf (file
, "%d [style=filled, fillcolor=green]\n", i
);
367 /* Highlight stores to memory. */
368 if (RDG_MEM_WRITE_STMT (rdg
, i
))
369 fprintf (file
, "%d [style=filled, fillcolor=red]\n", i
);
372 for (e
= v
->succ
; e
; e
= e
->succ_next
)
373 switch (RDGE_TYPE (e
))
376 /* These are the most common dependences: don't print these. */
377 fprintf (file
, "%d -> %d \n", i
, e
->dest
);
381 fprintf (file
, "%d -> %d [label=control] \n", i
, e
->dest
);
389 fprintf (file
, "}\n\n");
392 /* Display the Reduced Dependence Graph using dotty. */
395 dot_rdg (struct graph
*rdg
)
397 /* When debugging, you may want to enable the following code. */
399 FILE *file
= popen ("dot -Tx11", "w");
402 dot_rdg_1 (file
, rdg
);
404 close (fileno (file
));
407 dot_rdg_1 (stderr
, rdg
);
411 /* Returns the index of STMT in RDG. */
414 rdg_vertex_for_stmt (struct graph
*rdg ATTRIBUTE_UNUSED
, gimple
*stmt
)
416 int index
= gimple_uid (stmt
);
417 gcc_checking_assert (index
== -1 || RDG_STMT (rdg
, index
) == stmt
);
421 /* Creates dependence edges in RDG for all the uses of DEF. IDEF is
422 the index of DEF in RDG. */
425 create_rdg_edges_for_scalar (struct graph
*rdg
, tree def
, int idef
)
427 use_operand_p imm_use_p
;
428 imm_use_iterator iterator
;
430 FOR_EACH_IMM_USE_FAST (imm_use_p
, iterator
, def
)
432 struct graph_edge
*e
;
433 int use
= rdg_vertex_for_stmt (rdg
, USE_STMT (imm_use_p
));
438 e
= add_edge (rdg
, idef
, use
);
439 e
->data
= XNEW (struct rdg_edge
);
440 RDGE_TYPE (e
) = flow_dd
;
444 /* Creates an edge for the control dependences of BB to the vertex V. */
447 create_edge_for_control_dependence (struct graph
*rdg
, basic_block bb
,
448 int v
, control_dependences
*cd
)
452 EXECUTE_IF_SET_IN_BITMAP (cd
->get_edges_dependent_on (bb
->index
),
455 basic_block cond_bb
= cd
->get_edge_src (edge_n
);
456 gimple
*stmt
= *gsi_last_bb (cond_bb
);
457 if (stmt
&& is_ctrl_stmt (stmt
))
459 struct graph_edge
*e
;
460 int c
= rdg_vertex_for_stmt (rdg
, stmt
);
464 e
= add_edge (rdg
, c
, v
);
465 e
->data
= XNEW (struct rdg_edge
);
466 RDGE_TYPE (e
) = control_dd
;
471 /* Creates the edges of the reduced dependence graph RDG. */
474 create_rdg_flow_edges (struct graph
*rdg
)
480 for (i
= 0; i
< rdg
->n_vertices
; i
++)
481 FOR_EACH_PHI_OR_STMT_DEF (def_p
, RDG_STMT (rdg
, i
),
483 create_rdg_edges_for_scalar (rdg
, DEF_FROM_PTR (def_p
), i
);
486 /* Creates the edges of the reduced dependence graph RDG. */
489 create_rdg_cd_edges (struct graph
*rdg
, control_dependences
*cd
, loop_p loop
)
493 for (i
= 0; i
< rdg
->n_vertices
; i
++)
495 gimple
*stmt
= RDG_STMT (rdg
, i
);
496 if (gimple_code (stmt
) == GIMPLE_PHI
)
500 FOR_EACH_EDGE (e
, ei
, gimple_bb (stmt
)->preds
)
501 if (flow_bb_inside_loop_p (loop
, e
->src
))
502 create_edge_for_control_dependence (rdg
, e
->src
, i
, cd
);
505 create_edge_for_control_dependence (rdg
, gimple_bb (stmt
), i
, cd
);
510 class loop_distribution
513 /* The loop (nest) to be distributed. */
514 vec
<loop_p
> loop_nest
;
516 /* Vector of data references in the loop to be distributed. */
517 vec
<data_reference_p
> datarefs_vec
;
519 /* If there is nonaddressable data reference in above vector. */
520 bool has_nonaddressable_dataref_p
;
522 /* Store index of data reference in aux field. */
524 /* Hash table for data dependence relation in the loop to be distributed. */
525 hash_table
<ddr_hasher
> *ddrs_table
;
527 /* Array mapping basic block's index to its topological order. */
528 int *bb_top_order_index
;
529 /* And size of the array. */
530 int bb_top_order_index_size
;
532 /* Build the vertices of the reduced dependence graph RDG. Return false
534 bool create_rdg_vertices (struct graph
*rdg
, const vec
<gimple
*> &stmts
,
537 /* Initialize STMTS with all the statements of LOOP. We use topological
538 order to discover all statements. The order is important because
539 generate_loops_for_partition is using the same traversal for identifying
540 statements in loop copies. */
541 void stmts_from_loop (class loop
*loop
, vec
<gimple
*> *stmts
);
544 /* Build the Reduced Dependence Graph (RDG) with one vertex per statement of
545 LOOP, and one edge per flow dependence or control dependence from control
546 dependence CD. During visiting each statement, data references are also
547 collected and recorded in global data DATAREFS_VEC. */
548 struct graph
* build_rdg (class loop
*loop
, control_dependences
*cd
);
550 /* Merge PARTITION into the partition DEST. RDG is the reduced dependence
551 graph and we update type for result partition if it is non-NULL. */
552 void partition_merge_into (struct graph
*rdg
,
553 partition
*dest
, partition
*partition
,
557 /* Return data dependence relation for data references A and B. The two
558 data references must be in lexicographic order wrto reduced dependence
559 graph RDG. We firstly try to find ddr from global ddr hash table. If
560 it doesn't exist, compute the ddr and cache it. */
561 data_dependence_relation
* get_data_dependence (struct graph
*rdg
,
566 /* In reduced dependence graph RDG for loop distribution, return true if
567 dependence between references DR1 and DR2 leads to a dependence cycle
568 and such dependence cycle can't be resolved by runtime alias check. */
569 bool data_dep_in_cycle_p (struct graph
*rdg
, data_reference_p dr1
,
570 data_reference_p dr2
);
573 /* Given reduced dependence graph RDG, PARTITION1 and PARTITION2, update
574 PARTITION1's type after merging PARTITION2 into PARTITION1. */
575 void update_type_for_merge (struct graph
*rdg
,
576 partition
*partition1
, partition
*partition2
);
579 /* Returns a partition with all the statements needed for computing
580 the vertex V of the RDG, also including the loop exit conditions. */
581 partition
*build_rdg_partition_for_vertex (struct graph
*rdg
, int v
);
583 /* Given data references DST_DR and SRC_DR in loop nest LOOP and RDG, classify
584 if it forms builtin memcpy or memmove call. */
585 void classify_builtin_ldst (loop_p loop
, struct graph
*rdg
, partition
*partition
,
586 data_reference_p dst_dr
, data_reference_p src_dr
);
588 /* Classifies the builtin kind we can generate for PARTITION of RDG and LOOP.
589 For the moment we detect memset, memcpy and memmove patterns. Bitmap
590 STMT_IN_ALL_PARTITIONS contains statements belonging to all partitions.
591 Returns true if there is a reduction in all partitions and we
592 possibly did not mark PARTITION as having one for this reason. */
595 classify_partition (loop_p loop
,
596 struct graph
*rdg
, partition
*partition
,
597 bitmap stmt_in_all_partitions
);
600 /* Returns true when PARTITION1 and PARTITION2 access the same memory
602 bool share_memory_accesses (struct graph
*rdg
,
603 partition
*partition1
, partition
*partition2
);
605 /* For each seed statement in STARTING_STMTS, this function builds
606 partition for it by adding depended statements according to RDG.
607 All partitions are recorded in PARTITIONS. */
608 void rdg_build_partitions (struct graph
*rdg
,
609 vec
<gimple
*> starting_stmts
,
610 vec
<partition
*> *partitions
);
612 /* Compute partition dependence created by the data references in DRS1
613 and DRS2, modify and return DIR according to that. IF ALIAS_DDR is
614 not NULL, we record dependence introduced by possible alias between
615 two data references in ALIAS_DDRS; otherwise, we simply ignore such
616 dependence as if it doesn't exist at all. */
617 int pg_add_dependence_edges (struct graph
*rdg
, int dir
, bitmap drs1
,
618 bitmap drs2
, vec
<ddr_p
> *alias_ddrs
);
621 /* Build and return partition dependence graph for PARTITIONS. RDG is
622 reduced dependence graph for the loop to be distributed. If IGNORE_ALIAS_P
623 is true, data dependence caused by possible alias between references
624 is ignored, as if it doesn't exist at all; otherwise all depdendences
626 struct graph
*build_partition_graph (struct graph
*rdg
,
627 vec
<struct partition
*> *partitions
,
628 bool ignore_alias_p
);
630 /* Given reduced dependence graph RDG merge strong connected components
631 of PARTITIONS. If IGNORE_ALIAS_P is true, data dependence caused by
632 possible alias between references is ignored, as if it doesn't exist
633 at all; otherwise all depdendences are considered. */
634 void merge_dep_scc_partitions (struct graph
*rdg
, vec
<struct partition
*>
635 *partitions
, bool ignore_alias_p
);
637 /* This is the main function breaking strong conected components in
638 PARTITIONS giving reduced depdendence graph RDG. Store data dependence
639 relations for runtime alias check in ALIAS_DDRS. */
640 void break_alias_scc_partitions (struct graph
*rdg
, vec
<struct partition
*>
641 *partitions
, vec
<ddr_p
> *alias_ddrs
);
644 /* Fuse PARTITIONS of LOOP if necessary before finalizing distribution.
645 ALIAS_DDRS contains ddrs which need runtime alias check. */
646 void finalize_partitions (class loop
*loop
, vec
<struct partition
*>
647 *partitions
, vec
<ddr_p
> *alias_ddrs
);
649 /* Distributes the code from LOOP in such a way that producer statements
650 are placed before consumer statements. Tries to separate only the
651 statements from STMTS into separate loops. Returns the number of
652 distributed loops. Set NB_CALLS to number of generated builtin calls.
653 Set *DESTROY_P to whether LOOP needs to be destroyed. */
654 int distribute_loop (class loop
*loop
, const vec
<gimple
*> &stmts
,
655 control_dependences
*cd
, int *nb_calls
, bool *destroy_p
,
656 bool only_patterns_p
);
658 /* Transform loops which mimic the effects of builtins rawmemchr or strlen and
659 replace them accordingly. */
660 bool transform_reduction_loop (loop_p loop
);
662 /* Compute topological order for basic blocks. Topological order is
663 needed because data dependence is computed for data references in
664 lexicographical order. */
665 void bb_top_order_init (void);
667 void bb_top_order_destroy (void);
671 /* Getter for bb_top_order. */
673 inline int get_bb_top_order_index_size (void)
675 return bb_top_order_index_size
;
678 inline int get_bb_top_order_index (int i
)
680 return bb_top_order_index
[i
];
683 unsigned int execute (function
*fun
);
687 /* If X has a smaller topological sort number than Y, returns -1;
688 if greater, returns 1. */
690 bb_top_order_cmp_r (const void *x
, const void *y
, void *loop
)
692 loop_distribution
*_loop
=
693 (loop_distribution
*) loop
;
695 basic_block bb1
= *(const basic_block
*) x
;
696 basic_block bb2
= *(const basic_block
*) y
;
698 int bb_top_order_index_size
= _loop
->get_bb_top_order_index_size ();
700 gcc_assert (bb1
->index
< bb_top_order_index_size
701 && bb2
->index
< bb_top_order_index_size
);
702 gcc_assert (bb1
== bb2
703 || _loop
->get_bb_top_order_index(bb1
->index
)
704 != _loop
->get_bb_top_order_index(bb2
->index
));
706 return (_loop
->get_bb_top_order_index(bb1
->index
) -
707 _loop
->get_bb_top_order_index(bb2
->index
));
711 loop_distribution::create_rdg_vertices (struct graph
*rdg
,
712 const vec
<gimple
*> &stmts
,
718 FOR_EACH_VEC_ELT (stmts
, i
, stmt
)
720 struct vertex
*v
= &(rdg
->vertices
[i
]);
722 /* Record statement to vertex mapping. */
723 gimple_set_uid (stmt
, i
);
725 v
->data
= XNEW (struct rdg_vertex
);
726 RDGV_STMT (v
) = stmt
;
727 RDGV_DATAREFS (v
).create (0);
728 RDGV_HAS_MEM_WRITE (v
) = false;
729 RDGV_HAS_MEM_READS (v
) = false;
730 if (gimple_code (stmt
) == GIMPLE_PHI
)
733 unsigned drp
= datarefs_vec
.length ();
734 if (!find_data_references_in_stmt (loop
, stmt
, &datarefs_vec
))
736 for (unsigned j
= drp
; j
< datarefs_vec
.length (); ++j
)
738 data_reference_p dr
= datarefs_vec
[j
];
740 RDGV_HAS_MEM_READS (v
) = true;
742 RDGV_HAS_MEM_WRITE (v
) = true;
743 RDGV_DATAREFS (v
).safe_push (dr
);
744 has_nonaddressable_dataref_p
|= may_be_nonaddressable_p (dr
->ref
);
751 loop_distribution::stmts_from_loop (class loop
*loop
, vec
<gimple
*> *stmts
)
754 basic_block
*bbs
= get_loop_body_in_custom_order (loop
, this, bb_top_order_cmp_r
);
756 for (i
= 0; i
< loop
->num_nodes
; i
++)
758 basic_block bb
= bbs
[i
];
760 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
762 if (!virtual_operand_p (gimple_phi_result (bsi
.phi ())))
763 stmts
->safe_push (bsi
.phi ());
765 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
768 gimple
*stmt
= gsi_stmt (bsi
);
769 if (gimple_code (stmt
) != GIMPLE_LABEL
&& !is_gimple_debug (stmt
))
770 stmts
->safe_push (stmt
);
777 /* Free the reduced dependence graph RDG. */
780 free_rdg (struct graph
*rdg
)
784 for (i
= 0; i
< rdg
->n_vertices
; i
++)
786 struct vertex
*v
= &(rdg
->vertices
[i
]);
787 struct graph_edge
*e
;
789 for (e
= v
->succ
; e
; e
= e
->succ_next
)
794 gimple_set_uid (RDGV_STMT (v
), -1);
795 (RDGV_DATAREFS (v
)).release ();
804 loop_distribution::build_rdg (class loop
*loop
, control_dependences
*cd
)
808 /* Create the RDG vertices from the stmts of the loop nest. */
809 auto_vec
<gimple
*, 10> stmts
;
810 stmts_from_loop (loop
, &stmts
);
811 rdg
= new_graph (stmts
.length ());
812 if (!create_rdg_vertices (rdg
, stmts
, loop
))
819 create_rdg_flow_edges (rdg
);
821 create_rdg_cd_edges (rdg
, cd
, loop
);
827 /* Allocate and initialize a partition from BITMAP. */
830 partition_alloc (void)
832 partition
*partition
= XCNEW (struct partition
);
833 partition
->stmts
= BITMAP_ALLOC (NULL
);
834 partition
->reduction_p
= false;
835 partition
->loc
= UNKNOWN_LOCATION
;
836 partition
->kind
= PKIND_NORMAL
;
837 partition
->type
= PTYPE_PARALLEL
;
838 partition
->datarefs
= BITMAP_ALLOC (NULL
);
842 /* Free PARTITION. */
845 partition_free (partition
*partition
)
847 BITMAP_FREE (partition
->stmts
);
848 BITMAP_FREE (partition
->datarefs
);
849 if (partition
->builtin
)
850 free (partition
->builtin
);
855 /* Returns true if the partition can be generated as a builtin. */
858 partition_builtin_p (partition
*partition
)
860 return partition
->kind
> PKIND_PARTIAL_MEMSET
;
863 /* Returns true if the partition contains a reduction. */
866 partition_reduction_p (partition
*partition
)
868 return partition
->reduction_p
;
872 loop_distribution::partition_merge_into (struct graph
*rdg
,
873 partition
*dest
, partition
*partition
, enum fuse_type ft
)
875 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
877 fprintf (dump_file
, "Fuse partitions because %s:\n", fuse_message
[ft
]);
878 fprintf (dump_file
, " Part 1: ");
879 dump_bitmap (dump_file
, dest
->stmts
);
880 fprintf (dump_file
, " Part 2: ");
881 dump_bitmap (dump_file
, partition
->stmts
);
884 dest
->kind
= PKIND_NORMAL
;
885 if (dest
->type
== PTYPE_PARALLEL
)
886 dest
->type
= partition
->type
;
888 bitmap_ior_into (dest
->stmts
, partition
->stmts
);
889 if (partition_reduction_p (partition
))
890 dest
->reduction_p
= true;
892 /* Further check if any data dependence prevents us from executing the
893 new partition parallelly. */
894 if (dest
->type
== PTYPE_PARALLEL
&& rdg
!= NULL
)
895 update_type_for_merge (rdg
, dest
, partition
);
897 bitmap_ior_into (dest
->datarefs
, partition
->datarefs
);
901 /* Returns true when DEF is an SSA_NAME defined in LOOP and used after
905 ssa_name_has_uses_outside_loop_p (tree def
, loop_p loop
)
907 imm_use_iterator imm_iter
;
910 FOR_EACH_IMM_USE_FAST (use_p
, imm_iter
, def
)
912 if (is_gimple_debug (USE_STMT (use_p
)))
915 basic_block use_bb
= gimple_bb (USE_STMT (use_p
));
916 if (!flow_bb_inside_loop_p (loop
, use_bb
))
923 /* Returns true when STMT defines a scalar variable used after the
927 stmt_has_scalar_dependences_outside_loop (loop_p loop
, gimple
*stmt
)
932 if (gimple_code (stmt
) == GIMPLE_PHI
)
933 return ssa_name_has_uses_outside_loop_p (gimple_phi_result (stmt
), loop
);
935 FOR_EACH_SSA_DEF_OPERAND (def_p
, stmt
, op_iter
, SSA_OP_DEF
)
936 if (ssa_name_has_uses_outside_loop_p (DEF_FROM_PTR (def_p
), loop
))
942 /* Return a copy of LOOP placed before LOOP. */
945 copy_loop_before (class loop
*loop
, bool redirect_lc_phi_defs
)
948 edge preheader
= loop_preheader_edge (loop
);
950 initialize_original_copy_tables ();
951 res
= slpeel_tree_duplicate_loop_to_edge_cfg (loop
, NULL
, preheader
);
952 gcc_assert (res
!= NULL
);
954 /* When a not last partition is supposed to keep the LC PHIs computed
955 adjust their definitions. */
956 if (redirect_lc_phi_defs
)
958 edge exit
= single_exit (loop
);
959 for (gphi_iterator si
= gsi_start_phis (exit
->dest
); !gsi_end_p (si
);
962 gphi
*phi
= si
.phi ();
963 if (virtual_operand_p (gimple_phi_result (phi
)))
965 use_operand_p use_p
= PHI_ARG_DEF_PTR_FROM_EDGE (phi
, exit
);
966 tree new_def
= get_current_def (USE_FROM_PTR (use_p
));
967 SET_USE (use_p
, new_def
);
971 free_original_copy_tables ();
972 delete_update_ssa ();
977 /* Creates an empty basic block after LOOP. */
980 create_bb_after_loop (class loop
*loop
)
982 edge exit
= single_exit (loop
);
990 /* Generate code for PARTITION from the code in LOOP. The loop is
991 copied when COPY_P is true. All the statements not flagged in the
992 PARTITION bitmap are removed from the loop or from its copy. The
993 statements are indexed in sequence inside a basic block, and the
994 basic blocks of a loop are taken in dom order. */
997 generate_loops_for_partition (class loop
*loop
, partition
*partition
,
998 bool copy_p
, bool keep_lc_phis_p
)
1005 int orig_loop_num
= loop
->orig_loop_num
;
1006 loop
= copy_loop_before (loop
, keep_lc_phis_p
);
1007 gcc_assert (loop
!= NULL
);
1008 loop
->orig_loop_num
= orig_loop_num
;
1009 create_preheader (loop
, CP_SIMPLE_PREHEADERS
);
1010 create_bb_after_loop (loop
);
1014 /* Origin number is set to the new versioned loop's num. */
1015 gcc_assert (loop
->orig_loop_num
!= loop
->num
);
1018 /* Remove stmts not in the PARTITION bitmap. */
1019 bbs
= get_loop_body_in_dom_order (loop
);
1021 if (MAY_HAVE_DEBUG_BIND_STMTS
)
1022 for (i
= 0; i
< loop
->num_nodes
; i
++)
1024 basic_block bb
= bbs
[i
];
1026 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
1029 gphi
*phi
= bsi
.phi ();
1030 if (!virtual_operand_p (gimple_phi_result (phi
))
1031 && !bitmap_bit_p (partition
->stmts
, gimple_uid (phi
)))
1032 reset_debug_uses (phi
);
1035 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
); gsi_next (&bsi
))
1037 gimple
*stmt
= gsi_stmt (bsi
);
1038 if (gimple_code (stmt
) != GIMPLE_LABEL
1039 && !is_gimple_debug (stmt
)
1040 && !bitmap_bit_p (partition
->stmts
, gimple_uid (stmt
)))
1041 reset_debug_uses (stmt
);
1045 for (i
= 0; i
< loop
->num_nodes
; i
++)
1047 basic_block bb
= bbs
[i
];
1048 edge inner_exit
= NULL
;
1050 if (loop
!= bb
->loop_father
)
1051 inner_exit
= single_exit (bb
->loop_father
);
1053 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);)
1055 gphi
*phi
= bsi
.phi ();
1056 if (!virtual_operand_p (gimple_phi_result (phi
))
1057 && !bitmap_bit_p (partition
->stmts
, gimple_uid (phi
)))
1058 remove_phi_node (&bsi
, true);
1063 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);)
1065 gimple
*stmt
= gsi_stmt (bsi
);
1066 if (gimple_code (stmt
) != GIMPLE_LABEL
1067 && !is_gimple_debug (stmt
)
1068 && !bitmap_bit_p (partition
->stmts
, gimple_uid (stmt
)))
1070 /* In distribution of loop nest, if bb is inner loop's exit_bb,
1071 we choose its exit edge/path in order to avoid generating
1072 infinite loop. For all other cases, we choose an arbitrary
1073 path through the empty CFG part that this unnecessary
1074 control stmt controls. */
1075 if (gcond
*cond_stmt
= dyn_cast
<gcond
*> (stmt
))
1077 if (inner_exit
&& inner_exit
->flags
& EDGE_TRUE_VALUE
)
1078 gimple_cond_make_true (cond_stmt
);
1080 gimple_cond_make_false (cond_stmt
);
1083 else if (gimple_code (stmt
) == GIMPLE_SWITCH
)
1085 gswitch
*switch_stmt
= as_a
<gswitch
*> (stmt
);
1086 gimple_switch_set_index
1087 (switch_stmt
, CASE_LOW (gimple_switch_label (switch_stmt
, 1)));
1092 unlink_stmt_vdef (stmt
);
1093 gsi_remove (&bsi
, true);
1094 release_defs (stmt
);
1105 /* If VAL memory representation contains the same value in all bytes,
1106 return that value, otherwise return -1.
1107 E.g. for 0x24242424 return 0x24, for IEEE double
1108 747708026454360457216.0 return 0x44, etc. */
1111 const_with_all_bytes_same (tree val
)
1113 unsigned char buf
[64];
1116 if (integer_zerop (val
)
1117 || (TREE_CODE (val
) == CONSTRUCTOR
1118 && !TREE_CLOBBER_P (val
)
1119 && CONSTRUCTOR_NELTS (val
) == 0))
1122 if (real_zerop (val
))
1124 /* Only return 0 for +0.0, not for -0.0, which doesn't have
1125 an all bytes same memory representation. Don't transform
1126 -0.0 stores into +0.0 even for !HONOR_SIGNED_ZEROS. */
1127 switch (TREE_CODE (val
))
1130 if (!real_isneg (TREE_REAL_CST_PTR (val
)))
1134 if (!const_with_all_bytes_same (TREE_REALPART (val
))
1135 && !const_with_all_bytes_same (TREE_IMAGPART (val
)))
1140 unsigned int count
= vector_cst_encoded_nelts (val
);
1142 for (j
= 0; j
< count
; ++j
)
1143 if (const_with_all_bytes_same (VECTOR_CST_ENCODED_ELT (val
, j
)))
1154 if (CHAR_BIT
!= 8 || BITS_PER_UNIT
!= 8)
1157 len
= native_encode_expr (val
, buf
, sizeof (buf
));
1160 for (i
= 1; i
< len
; i
++)
1161 if (buf
[i
] != buf
[0])
1166 /* Generate a call to memset for PARTITION in LOOP. */
1169 generate_memset_builtin (class loop
*loop
, partition
*partition
)
1171 gimple_stmt_iterator gsi
;
1172 tree mem
, fn
, nb_bytes
;
1174 struct builtin_info
*builtin
= partition
->builtin
;
1177 /* The new statements will be placed before LOOP. */
1178 gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
1180 nb_bytes
= rewrite_to_non_trapping_overflow (builtin
->size
);
1181 nb_bytes
= force_gimple_operand_gsi (&gsi
, nb_bytes
, true, NULL_TREE
,
1182 false, GSI_CONTINUE_LINKING
);
1183 mem
= rewrite_to_non_trapping_overflow (builtin
->dst_base
);
1184 mem
= force_gimple_operand_gsi (&gsi
, mem
, true, NULL_TREE
,
1185 false, GSI_CONTINUE_LINKING
);
1187 /* This exactly matches the pattern recognition in classify_partition. */
1188 val
= gimple_assign_rhs1 (DR_STMT (builtin
->dst_dr
));
1189 /* Handle constants like 0x15151515 and similarly
1190 floating point constants etc. where all bytes are the same. */
1191 int bytev
= const_with_all_bytes_same (val
);
1193 val
= build_int_cst (integer_type_node
, bytev
);
1194 else if (TREE_CODE (val
) == INTEGER_CST
)
1195 val
= fold_convert (integer_type_node
, val
);
1196 else if (!useless_type_conversion_p (integer_type_node
, TREE_TYPE (val
)))
1198 tree tem
= make_ssa_name (integer_type_node
);
1199 gimple
*cstmt
= gimple_build_assign (tem
, NOP_EXPR
, val
);
1200 gsi_insert_after (&gsi
, cstmt
, GSI_CONTINUE_LINKING
);
1204 fn
= build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET
));
1205 fn_call
= gimple_build_call (fn
, 3, mem
, val
, nb_bytes
);
1206 gimple_set_location (fn_call
, partition
->loc
);
1207 gsi_insert_after (&gsi
, fn_call
, GSI_CONTINUE_LINKING
);
1210 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1212 fprintf (dump_file
, "generated memset");
1214 fprintf (dump_file
, " zero\n");
1216 fprintf (dump_file
, "\n");
1220 /* Generate a call to memcpy for PARTITION in LOOP. */
1223 generate_memcpy_builtin (class loop
*loop
, partition
*partition
)
1225 gimple_stmt_iterator gsi
;
1227 tree dest
, src
, fn
, nb_bytes
;
1228 enum built_in_function kind
;
1229 struct builtin_info
*builtin
= partition
->builtin
;
1231 /* The new statements will be placed before LOOP. */
1232 gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
1234 nb_bytes
= rewrite_to_non_trapping_overflow (builtin
->size
);
1235 nb_bytes
= force_gimple_operand_gsi (&gsi
, nb_bytes
, true, NULL_TREE
,
1236 false, GSI_CONTINUE_LINKING
);
1237 dest
= rewrite_to_non_trapping_overflow (builtin
->dst_base
);
1238 src
= rewrite_to_non_trapping_overflow (builtin
->src_base
);
1239 if (partition
->kind
== PKIND_MEMCPY
1240 || ! ptr_derefs_may_alias_p (dest
, src
))
1241 kind
= BUILT_IN_MEMCPY
;
1243 kind
= BUILT_IN_MEMMOVE
;
1244 /* Try harder if we're copying a constant size. */
1245 if (kind
== BUILT_IN_MEMMOVE
&& poly_int_tree_p (nb_bytes
))
1247 aff_tree asrc
, adest
;
1248 tree_to_aff_combination (src
, ptr_type_node
, &asrc
);
1249 tree_to_aff_combination (dest
, ptr_type_node
, &adest
);
1250 aff_combination_scale (&adest
, -1);
1251 aff_combination_add (&asrc
, &adest
);
1252 if (aff_comb_cannot_overlap_p (&asrc
, wi::to_poly_widest (nb_bytes
),
1253 wi::to_poly_widest (nb_bytes
)))
1254 kind
= BUILT_IN_MEMCPY
;
1257 dest
= force_gimple_operand_gsi (&gsi
, dest
, true, NULL_TREE
,
1258 false, GSI_CONTINUE_LINKING
);
1259 src
= force_gimple_operand_gsi (&gsi
, src
, true, NULL_TREE
,
1260 false, GSI_CONTINUE_LINKING
);
1261 fn
= build_fold_addr_expr (builtin_decl_implicit (kind
));
1262 fn_call
= gimple_build_call (fn
, 3, dest
, src
, nb_bytes
);
1263 gimple_set_location (fn_call
, partition
->loc
);
1264 gsi_insert_after (&gsi
, fn_call
, GSI_CONTINUE_LINKING
);
1267 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1269 if (kind
== BUILT_IN_MEMCPY
)
1270 fprintf (dump_file
, "generated memcpy\n");
1272 fprintf (dump_file
, "generated memmove\n");
1276 /* Remove and destroy the loop LOOP. */
1279 destroy_loop (class loop
*loop
)
1281 unsigned nbbs
= loop
->num_nodes
;
1282 edge exit
= single_exit (loop
);
1283 basic_block src
= loop_preheader_edge (loop
)->src
, dest
= exit
->dest
;
1287 bbs
= get_loop_body_in_dom_order (loop
);
1289 gimple_stmt_iterator dst_gsi
= gsi_after_labels (exit
->dest
);
1290 bool safe_p
= single_pred_p (exit
->dest
);
1291 for (unsigned i
= 0; i
< nbbs
; ++i
)
1293 /* We have made sure to not leave any dangling uses of SSA
1294 names defined in the loop. With the exception of virtuals.
1295 Make sure we replace all uses of virtual defs that will remain
1296 outside of the loop with the bare symbol as delete_basic_block
1297 will release them. */
1298 for (gphi_iterator gsi
= gsi_start_phis (bbs
[i
]); !gsi_end_p (gsi
);
1301 gphi
*phi
= gsi
.phi ();
1302 if (virtual_operand_p (gimple_phi_result (phi
)))
1303 mark_virtual_phi_result_for_renaming (phi
);
1305 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]); !gsi_end_p (gsi
);)
1307 gimple
*stmt
= gsi_stmt (gsi
);
1308 tree vdef
= gimple_vdef (stmt
);
1309 if (vdef
&& TREE_CODE (vdef
) == SSA_NAME
)
1310 mark_virtual_operand_for_renaming (vdef
);
1311 /* Also move and eventually reset debug stmts. We can leave
1312 constant values in place in case the stmt dominates the exit.
1313 ??? Non-constant values from the last iteration can be
1314 replaced with final values if we can compute them. */
1315 if (gimple_debug_bind_p (stmt
))
1317 tree val
= gimple_debug_bind_get_value (stmt
);
1318 gsi_move_before (&gsi
, &dst_gsi
);
1321 || !is_gimple_min_invariant (val
)
1322 || !dominated_by_p (CDI_DOMINATORS
, exit
->src
, bbs
[i
])))
1324 gimple_debug_bind_reset_value (stmt
);
1333 redirect_edge_pred (exit
, src
);
1334 exit
->flags
&= ~(EDGE_TRUE_VALUE
|EDGE_FALSE_VALUE
);
1335 exit
->flags
|= EDGE_FALLTHRU
;
1336 cancel_loop_tree (loop
);
1337 rescan_loop_exit (exit
, false, true);
1343 delete_basic_block (bbs
[i
]);
1349 set_immediate_dominator (CDI_DOMINATORS
, dest
,
1350 recompute_dominator (CDI_DOMINATORS
, dest
));
1353 /* Generates code for PARTITION. Return whether LOOP needs to be destroyed. */
1356 generate_code_for_partition (class loop
*loop
,
1357 partition
*partition
, bool copy_p
,
1358 bool keep_lc_phis_p
)
1360 switch (partition
->kind
)
1363 case PKIND_PARTIAL_MEMSET
:
1364 /* Reductions all have to be in the last partition. */
1365 gcc_assert (!partition_reduction_p (partition
)
1367 generate_loops_for_partition (loop
, partition
, copy_p
,
1372 generate_memset_builtin (loop
, partition
);
1377 generate_memcpy_builtin (loop
, partition
);
1384 /* Common tail for partitions we turn into a call. If this was the last
1385 partition for which we generate code, we have to destroy the loop. */
1391 data_dependence_relation
*
1392 loop_distribution::get_data_dependence (struct graph
*rdg
, data_reference_p a
,
1395 struct data_dependence_relation ent
, **slot
;
1396 struct data_dependence_relation
*ddr
;
1398 gcc_assert (DR_IS_WRITE (a
) || DR_IS_WRITE (b
));
1399 gcc_assert (rdg_vertex_for_stmt (rdg
, DR_STMT (a
))
1400 <= rdg_vertex_for_stmt (rdg
, DR_STMT (b
)));
1403 slot
= ddrs_table
->find_slot (&ent
, INSERT
);
1406 ddr
= initialize_data_dependence_relation (a
, b
, loop_nest
);
1407 compute_affine_dependence (ddr
, loop_nest
[0]);
1415 loop_distribution::data_dep_in_cycle_p (struct graph
*rdg
,
1416 data_reference_p dr1
,
1417 data_reference_p dr2
)
1419 struct data_dependence_relation
*ddr
;
1421 /* Re-shuffle data-refs to be in topological order. */
1422 if (rdg_vertex_for_stmt (rdg
, DR_STMT (dr1
))
1423 > rdg_vertex_for_stmt (rdg
, DR_STMT (dr2
)))
1424 std::swap (dr1
, dr2
);
1426 ddr
= get_data_dependence (rdg
, dr1
, dr2
);
1428 /* In case of no data dependence. */
1429 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
1431 /* For unknown data dependence or known data dependence which can't be
1432 expressed in classic distance vector, we check if it can be resolved
1433 by runtime alias check. If yes, we still consider data dependence
1434 as won't introduce data dependence cycle. */
1435 else if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
1436 || DDR_NUM_DIST_VECTS (ddr
) == 0)
1437 return !runtime_alias_check_p (ddr
, NULL
, true);
1438 else if (DDR_NUM_DIST_VECTS (ddr
) > 1)
1440 else if (DDR_REVERSED_P (ddr
)
1441 || lambda_vector_zerop (DDR_DIST_VECT (ddr
, 0), 1))
1448 loop_distribution::update_type_for_merge (struct graph
*rdg
,
1449 partition
*partition1
,
1450 partition
*partition2
)
1453 bitmap_iterator bi
, bj
;
1454 data_reference_p dr1
, dr2
;
1456 EXECUTE_IF_SET_IN_BITMAP (partition1
->datarefs
, 0, i
, bi
)
1458 unsigned start
= (partition1
== partition2
) ? i
+ 1 : 0;
1460 dr1
= datarefs_vec
[i
];
1461 EXECUTE_IF_SET_IN_BITMAP (partition2
->datarefs
, start
, j
, bj
)
1463 dr2
= datarefs_vec
[j
];
1464 if (DR_IS_READ (dr1
) && DR_IS_READ (dr2
))
1467 /* Partition can only be executed sequentially if there is any
1468 data dependence cycle. */
1469 if (data_dep_in_cycle_p (rdg
, dr1
, dr2
))
1471 partition1
->type
= PTYPE_SEQUENTIAL
;
1479 loop_distribution::build_rdg_partition_for_vertex (struct graph
*rdg
, int v
)
1481 partition
*partition
= partition_alloc ();
1482 auto_vec
<int, 3> nodes
;
1485 data_reference_p dr
;
1487 graphds_dfs (rdg
, &v
, 1, &nodes
, false, NULL
);
1489 FOR_EACH_VEC_ELT (nodes
, i
, x
)
1491 bitmap_set_bit (partition
->stmts
, x
);
1493 for (j
= 0; RDG_DATAREFS (rdg
, x
).iterate (j
, &dr
); ++j
)
1495 unsigned idx
= (unsigned) DR_INDEX (dr
);
1496 gcc_assert (idx
< datarefs_vec
.length ());
1498 /* Partition can only be executed sequentially if there is any
1499 unknown data reference. */
1500 if (!DR_BASE_ADDRESS (dr
) || !DR_OFFSET (dr
)
1501 || !DR_INIT (dr
) || !DR_STEP (dr
))
1502 partition
->type
= PTYPE_SEQUENTIAL
;
1504 bitmap_set_bit (partition
->datarefs
, idx
);
1508 if (partition
->type
== PTYPE_SEQUENTIAL
)
1511 /* Further check if any data dependence prevents us from executing the
1512 partition parallelly. */
1513 update_type_for_merge (rdg
, partition
, partition
);
1518 /* Given PARTITION of LOOP and RDG, record single load/store data references
1519 for builtin partition in SRC_DR/DST_DR, return false if there is no such
1523 find_single_drs (class loop
*loop
, struct graph
*rdg
, const bitmap
&partition_stmts
,
1524 data_reference_p
*dst_dr
, data_reference_p
*src_dr
)
1527 data_reference_p single_ld
= NULL
, single_st
= NULL
;
1530 EXECUTE_IF_SET_IN_BITMAP (partition_stmts
, 0, i
, bi
)
1532 gimple
*stmt
= RDG_STMT (rdg
, i
);
1533 data_reference_p dr
;
1535 if (gimple_code (stmt
) == GIMPLE_PHI
)
1538 /* Any scalar stmts are ok. */
1539 if (!gimple_vuse (stmt
))
1542 /* Otherwise just regular loads/stores. */
1543 if (!gimple_assign_single_p (stmt
))
1546 /* But exactly one store and/or load. */
1547 for (unsigned j
= 0; RDG_DATAREFS (rdg
, i
).iterate (j
, &dr
); ++j
)
1549 tree type
= TREE_TYPE (DR_REF (dr
));
1551 /* The memset, memcpy and memmove library calls are only
1552 able to deal with generic address space. */
1553 if (!ADDR_SPACE_GENERIC_P (TYPE_ADDR_SPACE (type
)))
1556 if (DR_IS_READ (dr
))
1558 if (single_ld
!= NULL
)
1564 if (single_st
!= NULL
)
1571 if (!single_ld
&& !single_st
)
1574 basic_block bb_ld
= NULL
;
1575 basic_block bb_st
= NULL
;
1579 /* Bail out if this is a bitfield memory reference. */
1580 if (TREE_CODE (DR_REF (single_ld
)) == COMPONENT_REF
1581 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_ld
), 1)))
1584 /* Data reference must be executed exactly once per iteration of each
1585 loop in the loop nest. We only need to check dominance information
1586 against the outermost one in a perfect loop nest because a bb can't
1587 dominate outermost loop's latch without dominating inner loop's. */
1588 bb_ld
= gimple_bb (DR_STMT (single_ld
));
1589 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb_ld
))
1595 /* Bail out if this is a bitfield memory reference. */
1596 if (TREE_CODE (DR_REF (single_st
)) == COMPONENT_REF
1597 && DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_st
), 1)))
1600 /* Data reference must be executed exactly once per iteration.
1601 Same as single_ld, we only need to check against the outermost
1603 bb_st
= gimple_bb (DR_STMT (single_st
));
1604 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb_st
))
1608 if (single_ld
&& single_st
)
1610 /* Load and store must be in the same loop nest. */
1611 if (bb_st
->loop_father
!= bb_ld
->loop_father
)
1614 edge e
= single_exit (bb_st
->loop_father
);
1615 bool dom_ld
= dominated_by_p (CDI_DOMINATORS
, e
->src
, bb_ld
);
1616 bool dom_st
= dominated_by_p (CDI_DOMINATORS
, e
->src
, bb_st
);
1617 if (dom_ld
!= dom_st
)
1621 *src_dr
= single_ld
;
1622 *dst_dr
= single_st
;
1626 /* Given data reference DR in LOOP_NEST, this function checks the enclosing
1627 loops from inner to outer to see if loop's step equals to access size at
1628 each level of loop. Return 2 if we can prove this at all level loops;
1629 record access base and size in BASE and SIZE; save loop's step at each
1630 level of loop in STEPS if it is not null. For example:
1632 int arr[100][100][100];
1633 for (i = 0; i < 100; i++) ;steps[2] = 40000
1634 for (j = 100; j > 0; j--) ;steps[1] = -400
1635 for (k = 0; k < 100; k++) ;steps[0] = 4
1636 arr[i][j - 1][k] = 0; ;base = &arr, size = 4000000
1638 Return 1 if we can prove the equality at the innermost loop, but not all
1639 level loops. In this case, no information is recorded.
1641 Return 0 if no equality can be proven at any level loops. */
1644 compute_access_range (loop_p loop_nest
, data_reference_p dr
, tree
*base
,
1645 tree
*size
, vec
<tree
> *steps
= NULL
)
1647 location_t loc
= gimple_location (DR_STMT (dr
));
1648 basic_block bb
= gimple_bb (DR_STMT (dr
));
1649 class loop
*loop
= bb
->loop_father
;
1650 tree ref
= DR_REF (dr
);
1651 tree access_base
= build_fold_addr_expr (ref
);
1652 tree access_size
= TYPE_SIZE_UNIT (TREE_TYPE (ref
));
1656 tree scev_fn
= analyze_scalar_evolution (loop
, access_base
);
1657 if (TREE_CODE (scev_fn
) != POLYNOMIAL_CHREC
)
1660 access_base
= CHREC_LEFT (scev_fn
);
1661 if (tree_contains_chrecs (access_base
, NULL
))
1664 tree scev_step
= CHREC_RIGHT (scev_fn
);
1665 /* Only support constant steps. */
1666 if (TREE_CODE (scev_step
) != INTEGER_CST
)
1669 enum ev_direction access_dir
= scev_direction (scev_fn
);
1670 if (access_dir
== EV_DIR_UNKNOWN
)
1674 steps
->safe_push (scev_step
);
1676 scev_step
= fold_convert_loc (loc
, sizetype
, scev_step
);
1677 /* Compute absolute value of scev step. */
1678 if (access_dir
== EV_DIR_DECREASES
)
1679 scev_step
= fold_build1_loc (loc
, NEGATE_EXPR
, sizetype
, scev_step
);
1681 /* At each level of loop, scev step must equal to access size. In other
1682 words, DR must access consecutive memory between loop iterations. */
1683 if (!operand_equal_p (scev_step
, access_size
, 0))
1686 /* Access stride can be computed for data reference at least for the
1690 /* Compute DR's execution times in loop. */
1691 tree niters
= number_of_latch_executions (loop
);
1692 niters
= fold_convert_loc (loc
, sizetype
, niters
);
1693 if (dominated_by_p (CDI_DOMINATORS
, single_exit (loop
)->src
, bb
))
1694 niters
= size_binop_loc (loc
, PLUS_EXPR
, niters
, size_one_node
);
1696 /* Compute DR's overall access size in loop. */
1697 access_size
= fold_build2_loc (loc
, MULT_EXPR
, sizetype
,
1699 /* Adjust base address in case of negative step. */
1700 if (access_dir
== EV_DIR_DECREASES
)
1702 tree adj
= fold_build2_loc (loc
, MINUS_EXPR
, sizetype
,
1703 scev_step
, access_size
);
1704 access_base
= fold_build_pointer_plus_loc (loc
, access_base
, adj
);
1706 } while (loop
!= loop_nest
&& (loop
= loop_outer (loop
)) != NULL
);
1708 *base
= access_base
;
1709 *size
= access_size
;
1710 /* Access stride can be computed for data reference at each level loop. */
1714 /* Allocate and return builtin struct. Record information like DST_DR,
1715 SRC_DR, DST_BASE, SRC_BASE and SIZE in the allocated struct. */
1717 static struct builtin_info
*
1718 alloc_builtin (data_reference_p dst_dr
, data_reference_p src_dr
,
1719 tree dst_base
, tree src_base
, tree size
)
1721 struct builtin_info
*builtin
= XNEW (struct builtin_info
);
1722 builtin
->dst_dr
= dst_dr
;
1723 builtin
->src_dr
= src_dr
;
1724 builtin
->dst_base
= dst_base
;
1725 builtin
->src_base
= src_base
;
1726 builtin
->size
= size
;
1730 /* Given data reference DR in loop nest LOOP, classify if it forms builtin
1734 classify_builtin_st (loop_p loop
, partition
*partition
, data_reference_p dr
)
1736 gimple
*stmt
= DR_STMT (dr
);
1737 tree base
, size
, rhs
= gimple_assign_rhs1 (stmt
);
1739 if (const_with_all_bytes_same (rhs
) == -1
1740 && (!INTEGRAL_TYPE_P (TREE_TYPE (rhs
))
1741 || (TYPE_MODE (TREE_TYPE (rhs
))
1742 != TYPE_MODE (unsigned_char_type_node
))))
1745 if (TREE_CODE (rhs
) == SSA_NAME
1746 && !SSA_NAME_IS_DEFAULT_DEF (rhs
)
1747 && flow_bb_inside_loop_p (loop
, gimple_bb (SSA_NAME_DEF_STMT (rhs
))))
1750 int res
= compute_access_range (loop
, dr
, &base
, &size
);
1755 partition
->kind
= PKIND_PARTIAL_MEMSET
;
1761 split_constant_offset (base
, &base_base
, &base_offset
);
1762 if (!cst_and_fits_in_hwi (base_offset
))
1764 unsigned HOST_WIDE_INT const_base_offset
= int_cst_value (base_offset
);
1766 struct builtin_info
*builtin
;
1767 builtin
= alloc_builtin (dr
, NULL
, base
, NULL_TREE
, size
);
1768 builtin
->dst_base_base
= base_base
;
1769 builtin
->dst_base_offset
= const_base_offset
;
1770 partition
->builtin
= builtin
;
1771 partition
->kind
= PKIND_MEMSET
;
1774 /* Given data references DST_DR and SRC_DR in loop nest LOOP and RDG, classify
1775 if it forms builtin memcpy or memmove call. */
1778 loop_distribution::classify_builtin_ldst (loop_p loop
, struct graph
*rdg
,
1779 partition
*partition
,
1780 data_reference_p dst_dr
,
1781 data_reference_p src_dr
)
1783 tree base
, size
, src_base
, src_size
;
1784 auto_vec
<tree
> dst_steps
, src_steps
;
1786 /* Compute access range of both load and store. */
1787 int res
= compute_access_range (loop
, dst_dr
, &base
, &size
, &dst_steps
);
1790 res
= compute_access_range (loop
, src_dr
, &src_base
, &src_size
, &src_steps
);
1794 /* They must have the same access size. */
1795 if (!operand_equal_p (size
, src_size
, 0))
1798 /* They must have the same storage order. */
1799 if (reverse_storage_order_for_component_p (DR_REF (dst_dr
))
1800 != reverse_storage_order_for_component_p (DR_REF (src_dr
)))
1803 /* Load and store in loop nest must access memory in the same way, i.e,
1804 their must have the same steps in each loop of the nest. */
1805 if (dst_steps
.length () != src_steps
.length ())
1807 for (unsigned i
= 0; i
< dst_steps
.length (); ++i
)
1808 if (!operand_equal_p (dst_steps
[i
], src_steps
[i
], 0))
1811 /* Now check that if there is a dependence. */
1812 ddr_p ddr
= get_data_dependence (rdg
, src_dr
, dst_dr
);
1814 /* Classify as memmove if no dependence between load and store. */
1815 if (DDR_ARE_DEPENDENT (ddr
) == chrec_known
)
1817 partition
->builtin
= alloc_builtin (dst_dr
, src_dr
, base
, src_base
, size
);
1818 partition
->kind
= PKIND_MEMMOVE
;
1822 /* Can't do memmove in case of unknown dependence or dependence without
1823 classical distance vector. */
1824 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
1825 || DDR_NUM_DIST_VECTS (ddr
) == 0)
1829 lambda_vector dist_v
;
1830 int num_lev
= (DDR_LOOP_NEST (ddr
)).length ();
1831 FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr
), i
, dist_v
)
1833 unsigned dep_lev
= dependence_level (dist_v
, num_lev
);
1834 /* Can't do memmove if load depends on store. */
1835 if (dep_lev
> 0 && dist_v
[dep_lev
- 1] > 0 && !DDR_REVERSED_P (ddr
))
1839 partition
->builtin
= alloc_builtin (dst_dr
, src_dr
, base
, src_base
, size
);
1840 partition
->kind
= PKIND_MEMMOVE
;
1845 loop_distribution::classify_partition (loop_p loop
,
1846 struct graph
*rdg
, partition
*partition
,
1847 bitmap stmt_in_all_partitions
)
1851 data_reference_p single_ld
= NULL
, single_st
= NULL
;
1852 bool volatiles_p
= false, has_reduction
= false;
1854 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, bi
)
1856 gimple
*stmt
= RDG_STMT (rdg
, i
);
1858 if (gimple_has_volatile_ops (stmt
))
1861 /* If the stmt is not included by all partitions and there is uses
1862 outside of the loop, then mark the partition as reduction. */
1863 if (stmt_has_scalar_dependences_outside_loop (loop
, stmt
))
1865 /* Due to limitation in the transform phase we have to fuse all
1866 reduction partitions. As a result, this could cancel valid
1867 loop distribution especially for loop that induction variable
1868 is used outside of loop. To workaround this issue, we skip
1869 marking partition as reudction if the reduction stmt belongs
1870 to all partitions. In such case, reduction will be computed
1871 correctly no matter how partitions are fused/distributed. */
1872 if (!bitmap_bit_p (stmt_in_all_partitions
, i
))
1873 partition
->reduction_p
= true;
1875 has_reduction
= true;
1879 /* Simple workaround to prevent classifying the partition as builtin
1880 if it contains any use outside of loop. For the case where all
1881 partitions have the reduction this simple workaround is delayed
1882 to only affect the last partition. */
1883 if (partition
->reduction_p
)
1884 return has_reduction
;
1886 /* Perform general partition disqualification for builtins. */
1888 || !flag_tree_loop_distribute_patterns
)
1889 return has_reduction
;
1891 /* Find single load/store data references for builtin partition. */
1892 if (!find_single_drs (loop
, rdg
, partition
->stmts
, &single_st
, &single_ld
)
1894 return has_reduction
;
1896 if (single_ld
&& single_st
)
1898 gimple
*store
= DR_STMT (single_st
), *load
= DR_STMT (single_ld
);
1899 /* Direct aggregate copy or via an SSA name temporary. */
1901 && gimple_assign_lhs (load
) != gimple_assign_rhs1 (store
))
1902 return has_reduction
;
1905 partition
->loc
= gimple_location (DR_STMT (single_st
));
1907 /* Classify the builtin kind. */
1908 if (single_ld
== NULL
)
1909 classify_builtin_st (loop
, partition
, single_st
);
1911 classify_builtin_ldst (loop
, rdg
, partition
, single_st
, single_ld
);
1912 return has_reduction
;
1916 loop_distribution::share_memory_accesses (struct graph
*rdg
,
1917 partition
*partition1
, partition
*partition2
)
1920 bitmap_iterator bi
, bj
;
1921 data_reference_p dr1
, dr2
;
1923 /* First check whether in the intersection of the two partitions are
1924 any loads or stores. Common loads are the situation that happens
1926 EXECUTE_IF_AND_IN_BITMAP (partition1
->stmts
, partition2
->stmts
, 0, i
, bi
)
1927 if (RDG_MEM_WRITE_STMT (rdg
, i
)
1928 || RDG_MEM_READS_STMT (rdg
, i
))
1931 /* Then check whether the two partitions access the same memory object. */
1932 EXECUTE_IF_SET_IN_BITMAP (partition1
->datarefs
, 0, i
, bi
)
1934 dr1
= datarefs_vec
[i
];
1936 if (!DR_BASE_ADDRESS (dr1
)
1937 || !DR_OFFSET (dr1
) || !DR_INIT (dr1
) || !DR_STEP (dr1
))
1940 EXECUTE_IF_SET_IN_BITMAP (partition2
->datarefs
, 0, j
, bj
)
1942 dr2
= datarefs_vec
[j
];
1944 if (!DR_BASE_ADDRESS (dr2
)
1945 || !DR_OFFSET (dr2
) || !DR_INIT (dr2
) || !DR_STEP (dr2
))
1948 if (operand_equal_p (DR_BASE_ADDRESS (dr1
), DR_BASE_ADDRESS (dr2
), 0)
1949 && operand_equal_p (DR_OFFSET (dr1
), DR_OFFSET (dr2
), 0)
1950 && operand_equal_p (DR_INIT (dr1
), DR_INIT (dr2
), 0)
1951 && operand_equal_p (DR_STEP (dr1
), DR_STEP (dr2
), 0))
1959 /* For each seed statement in STARTING_STMTS, this function builds
1960 partition for it by adding depended statements according to RDG.
1961 All partitions are recorded in PARTITIONS. */
1964 loop_distribution::rdg_build_partitions (struct graph
*rdg
,
1965 vec
<gimple
*> starting_stmts
,
1966 vec
<partition
*> *partitions
)
1968 auto_bitmap processed
;
1972 FOR_EACH_VEC_ELT (starting_stmts
, i
, stmt
)
1974 int v
= rdg_vertex_for_stmt (rdg
, stmt
);
1976 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1978 "ldist asked to generate code for vertex %d\n", v
);
1980 /* If the vertex is already contained in another partition so
1981 is the partition rooted at it. */
1982 if (bitmap_bit_p (processed
, v
))
1985 partition
*partition
= build_rdg_partition_for_vertex (rdg
, v
);
1986 bitmap_ior_into (processed
, partition
->stmts
);
1988 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1990 fprintf (dump_file
, "ldist creates useful %s partition:\n",
1991 partition
->type
== PTYPE_PARALLEL
? "parallel" : "sequent");
1992 bitmap_print (dump_file
, partition
->stmts
, " ", "\n");
1995 partitions
->safe_push (partition
);
1998 /* All vertices should have been assigned to at least one partition now,
1999 other than vertices belonging to dead code. */
2002 /* Dump to FILE the PARTITIONS. */
2005 dump_rdg_partitions (FILE *file
, const vec
<partition
*> &partitions
)
2008 partition
*partition
;
2010 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
2011 debug_bitmap_file (file
, partition
->stmts
);
2014 /* Debug PARTITIONS. */
2015 extern void debug_rdg_partitions (const vec
<partition
*> &);
2018 debug_rdg_partitions (const vec
<partition
*> &partitions
)
2020 dump_rdg_partitions (stderr
, partitions
);
2023 /* Returns the number of read and write operations in the RDG. */
2026 number_of_rw_in_rdg (struct graph
*rdg
)
2030 for (i
= 0; i
< rdg
->n_vertices
; i
++)
2032 if (RDG_MEM_WRITE_STMT (rdg
, i
))
2035 if (RDG_MEM_READS_STMT (rdg
, i
))
2042 /* Returns the number of read and write operations in a PARTITION of
2046 number_of_rw_in_partition (struct graph
*rdg
, partition
*partition
)
2052 EXECUTE_IF_SET_IN_BITMAP (partition
->stmts
, 0, i
, ii
)
2054 if (RDG_MEM_WRITE_STMT (rdg
, i
))
2057 if (RDG_MEM_READS_STMT (rdg
, i
))
2064 /* Returns true when one of the PARTITIONS contains all the read or
2065 write operations of RDG. */
2068 partition_contains_all_rw (struct graph
*rdg
,
2069 const vec
<partition
*> &partitions
)
2072 partition
*partition
;
2073 int nrw
= number_of_rw_in_rdg (rdg
);
2075 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
2076 if (nrw
== number_of_rw_in_partition (rdg
, partition
))
2083 loop_distribution::pg_add_dependence_edges (struct graph
*rdg
, int dir
,
2084 bitmap drs1
, bitmap drs2
, vec
<ddr_p
> *alias_ddrs
)
2087 bitmap_iterator bi
, bj
;
2088 data_reference_p dr1
, dr2
, saved_dr1
;
2090 /* dependence direction - 0 is no dependence, -1 is back,
2091 1 is forth, 2 is both (we can stop then, merging will occur). */
2092 EXECUTE_IF_SET_IN_BITMAP (drs1
, 0, i
, bi
)
2094 dr1
= datarefs_vec
[i
];
2096 EXECUTE_IF_SET_IN_BITMAP (drs2
, 0, j
, bj
)
2098 int res
, this_dir
= 1;
2101 dr2
= datarefs_vec
[j
];
2103 /* Skip all <read, read> data dependence. */
2104 if (DR_IS_READ (dr1
) && DR_IS_READ (dr2
))
2108 /* Re-shuffle data-refs to be in topological order. */
2109 if (rdg_vertex_for_stmt (rdg
, DR_STMT (dr1
))
2110 > rdg_vertex_for_stmt (rdg
, DR_STMT (dr2
)))
2112 std::swap (dr1
, dr2
);
2113 this_dir
= -this_dir
;
2115 ddr
= get_data_dependence (rdg
, dr1
, dr2
);
2116 if (DDR_ARE_DEPENDENT (ddr
) == chrec_dont_know
)
2119 res
= data_ref_compare_tree (DR_BASE_ADDRESS (dr1
),
2120 DR_BASE_ADDRESS (dr2
));
2121 /* Be conservative. If data references are not well analyzed,
2122 or the two data references have the same base address and
2123 offset, add dependence and consider it alias to each other.
2124 In other words, the dependence cannot be resolved by
2125 runtime alias check. */
2126 if (!DR_BASE_ADDRESS (dr1
) || !DR_BASE_ADDRESS (dr2
)
2127 || !DR_OFFSET (dr1
) || !DR_OFFSET (dr2
)
2128 || !DR_INIT (dr1
) || !DR_INIT (dr2
)
2129 || !DR_STEP (dr1
) || !tree_fits_uhwi_p (DR_STEP (dr1
))
2130 || !DR_STEP (dr2
) || !tree_fits_uhwi_p (DR_STEP (dr2
))
2133 /* Data dependence could be resolved by runtime alias check,
2134 record it in ALIAS_DDRS. */
2135 else if (alias_ddrs
!= NULL
)
2136 alias_ddrs
->safe_push (ddr
);
2137 /* Or simply ignore it. */
2139 else if (DDR_ARE_DEPENDENT (ddr
) == NULL_TREE
)
2141 if (DDR_REVERSED_P (ddr
))
2142 this_dir
= -this_dir
;
2144 /* Known dependences can still be unordered througout the
2145 iteration space, see gcc.dg/tree-ssa/ldist-16.c and
2146 gcc.dg/tree-ssa/pr94969.c. */
2147 if (DDR_NUM_DIST_VECTS (ddr
) != 1)
2149 /* If the overlap is exact preserve stmt order. */
2150 else if (lambda_vector_zerop (DDR_DIST_VECT (ddr
, 0),
2151 DDR_NB_LOOPS (ddr
)))
2153 /* Else as the distance vector is lexicographic positive swap
2154 the dependence direction. */
2156 this_dir
= -this_dir
;
2164 else if (this_dir
!= 0 && dir
!= this_dir
)
2166 /* Shuffle "back" dr1. */
2173 /* Compare postorder number of the partition graph vertices V1 and V2. */
2176 pgcmp (const void *v1_
, const void *v2_
)
2178 const vertex
*v1
= (const vertex
*)v1_
;
2179 const vertex
*v2
= (const vertex
*)v2_
;
2180 return v2
->post
- v1
->post
;
2183 /* Data attached to vertices of partition dependence graph. */
2186 /* ID of the corresponding partition. */
2188 /* The partition. */
2189 struct partition
*partition
;
2192 /* Data attached to edges of partition dependence graph. */
2195 /* If the dependence edge can be resolved by runtime alias check,
2196 this vector contains data dependence relations for runtime alias
2197 check. On the other hand, if the dependence edge is introduced
2198 because of compilation time known data dependence, this vector
2199 contains nothing. */
2200 vec
<ddr_p
> alias_ddrs
;
2203 /* Callback data for traversing edges in graph. */
2204 struct pg_edge_callback_data
2206 /* Bitmap contains strong connected components should be merged. */
2207 bitmap sccs_to_merge
;
2208 /* Array constains component information for all vertices. */
2209 int *vertices_component
;
2210 /* Vector to record all data dependence relations which are needed
2211 to break strong connected components by runtime alias checks. */
2212 vec
<ddr_p
> *alias_ddrs
;
2215 /* Initialize vertice's data for partition dependence graph PG with
2219 init_partition_graph_vertices (struct graph
*pg
,
2220 vec
<struct partition
*> *partitions
)
2223 partition
*partition
;
2224 struct pg_vdata
*data
;
2226 for (i
= 0; partitions
->iterate (i
, &partition
); ++i
)
2228 data
= new pg_vdata
;
2229 pg
->vertices
[i
].data
= data
;
2231 data
->partition
= partition
;
2235 /* Add edge <I, J> to partition dependence graph PG. Attach vector of data
2236 dependence relations to the EDGE if DDRS isn't NULL. */
2239 add_partition_graph_edge (struct graph
*pg
, int i
, int j
, vec
<ddr_p
> *ddrs
)
2241 struct graph_edge
*e
= add_edge (pg
, i
, j
);
2243 /* If the edge is attached with data dependence relations, it means this
2244 dependence edge can be resolved by runtime alias checks. */
2247 struct pg_edata
*data
= new pg_edata
;
2249 gcc_assert (ddrs
->length () > 0);
2251 data
->alias_ddrs
= vNULL
;
2252 data
->alias_ddrs
.safe_splice (*ddrs
);
2256 /* Callback function for graph travesal algorithm. It returns true
2257 if edge E should skipped when traversing the graph. */
2260 pg_skip_alias_edge (struct graph_edge
*e
)
2262 struct pg_edata
*data
= (struct pg_edata
*)e
->data
;
2263 return (data
!= NULL
&& data
->alias_ddrs
.length () > 0);
2266 /* Callback function freeing data attached to edge E of graph. */
2269 free_partition_graph_edata_cb (struct graph
*, struct graph_edge
*e
, void *)
2271 if (e
->data
!= NULL
)
2273 struct pg_edata
*data
= (struct pg_edata
*)e
->data
;
2274 data
->alias_ddrs
.release ();
2279 /* Free data attached to vertice of partition dependence graph PG. */
2282 free_partition_graph_vdata (struct graph
*pg
)
2285 struct pg_vdata
*data
;
2287 for (i
= 0; i
< pg
->n_vertices
; ++i
)
2289 data
= (struct pg_vdata
*)pg
->vertices
[i
].data
;
2294 /* Build and return partition dependence graph for PARTITIONS. RDG is
2295 reduced dependence graph for the loop to be distributed. If IGNORE_ALIAS_P
2296 is true, data dependence caused by possible alias between references
2297 is ignored, as if it doesn't exist at all; otherwise all depdendences
2301 loop_distribution::build_partition_graph (struct graph
*rdg
,
2302 vec
<struct partition
*> *partitions
,
2303 bool ignore_alias_p
)
2306 struct partition
*partition1
, *partition2
;
2307 graph
*pg
= new_graph (partitions
->length ());
2308 auto_vec
<ddr_p
> alias_ddrs
, *alias_ddrs_p
;
2310 alias_ddrs_p
= ignore_alias_p
? NULL
: &alias_ddrs
;
2312 init_partition_graph_vertices (pg
, partitions
);
2314 for (i
= 0; partitions
->iterate (i
, &partition1
); ++i
)
2316 for (j
= i
+ 1; partitions
->iterate (j
, &partition2
); ++j
)
2318 /* dependence direction - 0 is no dependence, -1 is back,
2319 1 is forth, 2 is both (we can stop then, merging will occur). */
2322 /* If the first partition has reduction, add back edge; if the
2323 second partition has reduction, add forth edge. This makes
2324 sure that reduction partition will be sorted as the last one. */
2325 if (partition_reduction_p (partition1
))
2327 else if (partition_reduction_p (partition2
))
2330 /* Cleanup the temporary vector. */
2331 alias_ddrs
.truncate (0);
2333 dir
= pg_add_dependence_edges (rdg
, dir
, partition1
->datarefs
,
2334 partition2
->datarefs
, alias_ddrs_p
);
2336 /* Add edge to partition graph if there exists dependence. There
2337 are two types of edges. One type edge is caused by compilation
2338 time known dependence, this type cannot be resolved by runtime
2339 alias check. The other type can be resolved by runtime alias
2341 if (dir
== 1 || dir
== 2
2342 || alias_ddrs
.length () > 0)
2344 /* Attach data dependence relations to edge that can be resolved
2345 by runtime alias check. */
2346 bool alias_edge_p
= (dir
!= 1 && dir
!= 2);
2347 add_partition_graph_edge (pg
, i
, j
,
2348 (alias_edge_p
) ? &alias_ddrs
: NULL
);
2350 if (dir
== -1 || dir
== 2
2351 || alias_ddrs
.length () > 0)
2353 /* Attach data dependence relations to edge that can be resolved
2354 by runtime alias check. */
2355 bool alias_edge_p
= (dir
!= -1 && dir
!= 2);
2356 add_partition_graph_edge (pg
, j
, i
,
2357 (alias_edge_p
) ? &alias_ddrs
: NULL
);
2364 /* Sort partitions in PG in descending post order and store them in
2368 sort_partitions_by_post_order (struct graph
*pg
,
2369 vec
<struct partition
*> *partitions
)
2372 struct pg_vdata
*data
;
2374 /* Now order the remaining nodes in descending postorder. */
2375 qsort (pg
->vertices
, pg
->n_vertices
, sizeof (vertex
), pgcmp
);
2376 partitions
->truncate (0);
2377 for (i
= 0; i
< pg
->n_vertices
; ++i
)
2379 data
= (struct pg_vdata
*)pg
->vertices
[i
].data
;
2380 if (data
->partition
)
2381 partitions
->safe_push (data
->partition
);
2386 loop_distribution::merge_dep_scc_partitions (struct graph
*rdg
,
2387 vec
<struct partition
*> *partitions
,
2388 bool ignore_alias_p
)
2390 struct partition
*partition1
, *partition2
;
2391 struct pg_vdata
*data
;
2392 graph
*pg
= build_partition_graph (rdg
, partitions
, ignore_alias_p
);
2393 int i
, j
, num_sccs
= graphds_scc (pg
, NULL
);
2395 /* Strong connected compoenent means dependence cycle, we cannot distribute
2396 them. So fuse them together. */
2397 if ((unsigned) num_sccs
< partitions
->length ())
2399 for (i
= 0; i
< num_sccs
; ++i
)
2401 for (j
= 0; partitions
->iterate (j
, &partition1
); ++j
)
2402 if (pg
->vertices
[j
].component
== i
)
2404 for (j
= j
+ 1; partitions
->iterate (j
, &partition2
); ++j
)
2405 if (pg
->vertices
[j
].component
== i
)
2407 partition_merge_into (NULL
, partition1
,
2408 partition2
, FUSE_SAME_SCC
);
2409 partition1
->type
= PTYPE_SEQUENTIAL
;
2410 (*partitions
)[j
] = NULL
;
2411 partition_free (partition2
);
2412 data
= (struct pg_vdata
*)pg
->vertices
[j
].data
;
2413 data
->partition
= NULL
;
2418 sort_partitions_by_post_order (pg
, partitions
);
2419 gcc_assert (partitions
->length () == (unsigned)num_sccs
);
2420 free_partition_graph_vdata (pg
);
2421 for_each_edge (pg
, free_partition_graph_edata_cb
, NULL
);
2425 /* Callback function for traversing edge E in graph G. DATA is private
2429 pg_collect_alias_ddrs (struct graph
*g
, struct graph_edge
*e
, void *data
)
2431 int i
, j
, component
;
2432 struct pg_edge_callback_data
*cbdata
;
2433 struct pg_edata
*edata
= (struct pg_edata
*) e
->data
;
2435 /* If the edge doesn't have attached data dependence, it represents
2436 compilation time known dependences. This type dependence cannot
2437 be resolved by runtime alias check. */
2438 if (edata
== NULL
|| edata
->alias_ddrs
.length () == 0)
2441 cbdata
= (struct pg_edge_callback_data
*) data
;
2444 component
= cbdata
->vertices_component
[i
];
2445 /* Vertices are topologically sorted according to compilation time
2446 known dependences, so we can break strong connected components
2447 by removing edges of the opposite direction, i.e, edges pointing
2448 from vertice with smaller post number to vertice with bigger post
2450 if (g
->vertices
[i
].post
< g
->vertices
[j
].post
2451 /* We only need to remove edges connecting vertices in the same
2452 strong connected component to break it. */
2453 && component
== cbdata
->vertices_component
[j
]
2454 /* Check if we want to break the strong connected component or not. */
2455 && !bitmap_bit_p (cbdata
->sccs_to_merge
, component
))
2456 cbdata
->alias_ddrs
->safe_splice (edata
->alias_ddrs
);
2459 /* Callback function for traversing edge E. DATA is private
2463 pg_unmark_merged_alias_ddrs (struct graph
*, struct graph_edge
*e
, void *data
)
2465 int i
, j
, component
;
2466 struct pg_edge_callback_data
*cbdata
;
2467 struct pg_edata
*edata
= (struct pg_edata
*) e
->data
;
2469 if (edata
== NULL
|| edata
->alias_ddrs
.length () == 0)
2472 cbdata
= (struct pg_edge_callback_data
*) data
;
2475 component
= cbdata
->vertices_component
[i
];
2476 /* Make sure to not skip vertices inside SCCs we are going to merge. */
2477 if (component
== cbdata
->vertices_component
[j
]
2478 && bitmap_bit_p (cbdata
->sccs_to_merge
, component
))
2480 edata
->alias_ddrs
.release ();
2486 /* This is the main function breaking strong conected components in
2487 PARTITIONS giving reduced depdendence graph RDG. Store data dependence
2488 relations for runtime alias check in ALIAS_DDRS. */
2490 loop_distribution::break_alias_scc_partitions (struct graph
*rdg
,
2491 vec
<struct partition
*> *partitions
,
2492 vec
<ddr_p
> *alias_ddrs
)
2494 int i
, j
, k
, num_sccs
, num_sccs_no_alias
= 0;
2495 /* Build partition dependence graph. */
2496 graph
*pg
= build_partition_graph (rdg
, partitions
, false);
2498 alias_ddrs
->truncate (0);
2499 /* Find strong connected components in the graph, with all dependence edges
2501 num_sccs
= graphds_scc (pg
, NULL
);
2502 /* All SCCs now can be broken by runtime alias checks because SCCs caused by
2503 compilation time known dependences are merged before this function. */
2504 if ((unsigned) num_sccs
< partitions
->length ())
2506 struct pg_edge_callback_data cbdata
;
2507 auto_bitmap sccs_to_merge
;
2508 auto_vec
<enum partition_type
> scc_types
;
2509 struct partition
*partition
, *first
;
2511 /* If all partitions in a SCC have the same type, we can simply merge the
2512 SCC. This loop finds out such SCCS and record them in bitmap. */
2513 bitmap_set_range (sccs_to_merge
, 0, (unsigned) num_sccs
);
2514 for (i
= 0; i
< num_sccs
; ++i
)
2516 for (j
= 0; partitions
->iterate (j
, &first
); ++j
)
2517 if (pg
->vertices
[j
].component
== i
)
2520 bool same_type
= true, all_builtins
= partition_builtin_p (first
);
2521 for (++j
; partitions
->iterate (j
, &partition
); ++j
)
2523 if (pg
->vertices
[j
].component
!= i
)
2526 if (first
->type
!= partition
->type
)
2531 all_builtins
&= partition_builtin_p (partition
);
2533 /* Merge SCC if all partitions in SCC have the same type, though the
2534 result partition is sequential, because vectorizer can do better
2535 runtime alias check. One expecption is all partitions in SCC are
2537 if (!same_type
|| all_builtins
)
2538 bitmap_clear_bit (sccs_to_merge
, i
);
2541 /* Initialize callback data for traversing. */
2542 cbdata
.sccs_to_merge
= sccs_to_merge
;
2543 cbdata
.alias_ddrs
= alias_ddrs
;
2544 cbdata
.vertices_component
= XNEWVEC (int, pg
->n_vertices
);
2545 /* Record the component information which will be corrupted by next
2546 graph scc finding call. */
2547 for (i
= 0; i
< pg
->n_vertices
; ++i
)
2548 cbdata
.vertices_component
[i
] = pg
->vertices
[i
].component
;
2550 /* Collect data dependences for runtime alias checks to break SCCs. */
2551 if (bitmap_count_bits (sccs_to_merge
) != (unsigned) num_sccs
)
2553 /* For SCCs we want to merge clear all alias_ddrs for edges
2554 inside the component. */
2555 for_each_edge (pg
, pg_unmark_merged_alias_ddrs
, &cbdata
);
2557 /* Run SCC finding algorithm again, with alias dependence edges
2558 skipped. This is to topologically sort partitions according to
2559 compilation time known dependence. Note the topological order
2560 is stored in the form of pg's post order number. */
2561 num_sccs_no_alias
= graphds_scc (pg
, NULL
, pg_skip_alias_edge
);
2562 /* We cannot assert partitions->length () == num_sccs_no_alias
2563 since we are not ignoring alias edges in cycles we are
2564 going to merge. That's required to compute correct postorder. */
2565 /* With topological order, we can construct two subgraphs L and R.
2566 L contains edge <x, y> where x < y in terms of post order, while
2567 R contains edge <x, y> where x > y. Edges for compilation time
2568 known dependence all fall in R, so we break SCCs by removing all
2569 (alias) edges of in subgraph L. */
2570 for_each_edge (pg
, pg_collect_alias_ddrs
, &cbdata
);
2573 /* For SCC that doesn't need to be broken, merge it. */
2574 for (i
= 0; i
< num_sccs
; ++i
)
2576 if (!bitmap_bit_p (sccs_to_merge
, i
))
2579 for (j
= 0; partitions
->iterate (j
, &first
); ++j
)
2580 if (cbdata
.vertices_component
[j
] == i
)
2582 for (k
= j
+ 1; partitions
->iterate (k
, &partition
); ++k
)
2584 struct pg_vdata
*data
;
2586 if (cbdata
.vertices_component
[k
] != i
)
2589 partition_merge_into (NULL
, first
, partition
, FUSE_SAME_SCC
);
2590 (*partitions
)[k
] = NULL
;
2591 partition_free (partition
);
2592 data
= (struct pg_vdata
*)pg
->vertices
[k
].data
;
2593 gcc_assert (data
->id
== k
);
2594 data
->partition
= NULL
;
2595 /* The result partition of merged SCC must be sequential. */
2596 first
->type
= PTYPE_SEQUENTIAL
;
2599 /* If reduction partition's SCC is broken by runtime alias checks,
2600 we force a negative post order to it making sure it will be scheduled
2602 if (num_sccs_no_alias
> 0)
2605 for (i
= 0; i
< pg
->n_vertices
; ++i
)
2607 struct pg_vdata
*data
= (struct pg_vdata
*)pg
->vertices
[i
].data
;
2608 if (data
->partition
&& partition_reduction_p (data
->partition
))
2610 gcc_assert (j
== -1);
2615 pg
->vertices
[j
].post
= -1;
2618 free (cbdata
.vertices_component
);
2621 sort_partitions_by_post_order (pg
, partitions
);
2622 free_partition_graph_vdata (pg
);
2623 for_each_edge (pg
, free_partition_graph_edata_cb
, NULL
);
2626 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2628 fprintf (dump_file
, "Possible alias data dependence to break:\n");
2629 dump_data_dependence_relations (dump_file
, *alias_ddrs
);
2633 /* Compute and return an expression whose value is the segment length which
2634 will be accessed by DR in NITERS iterations. */
2637 data_ref_segment_size (struct data_reference
*dr
, tree niters
)
2639 niters
= size_binop (MINUS_EXPR
,
2640 fold_convert (sizetype
, niters
),
2642 return size_binop (MULT_EXPR
,
2643 fold_convert (sizetype
, DR_STEP (dr
)),
2644 fold_convert (sizetype
, niters
));
2647 /* Return true if LOOP's latch is dominated by statement for data reference
2651 latch_dominated_by_data_ref (class loop
*loop
, data_reference
*dr
)
2653 return dominated_by_p (CDI_DOMINATORS
, single_exit (loop
)->src
,
2654 gimple_bb (DR_STMT (dr
)));
2657 /* Compute alias check pairs and store them in COMP_ALIAS_PAIRS for LOOP's
2658 data dependence relations ALIAS_DDRS. */
2661 compute_alias_check_pairs (class loop
*loop
, vec
<ddr_p
> *alias_ddrs
,
2662 vec
<dr_with_seg_len_pair_t
> *comp_alias_pairs
)
2665 unsigned HOST_WIDE_INT factor
= 1;
2666 tree niters_plus_one
, niters
= number_of_latch_executions (loop
);
2668 gcc_assert (niters
!= NULL_TREE
&& niters
!= chrec_dont_know
);
2669 niters
= fold_convert (sizetype
, niters
);
2670 niters_plus_one
= size_binop (PLUS_EXPR
, niters
, size_one_node
);
2672 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2673 fprintf (dump_file
, "Creating alias check pairs:\n");
2675 /* Iterate all data dependence relations and compute alias check pairs. */
2676 for (i
= 0; i
< alias_ddrs
->length (); i
++)
2678 ddr_p ddr
= (*alias_ddrs
)[i
];
2679 struct data_reference
*dr_a
= DDR_A (ddr
);
2680 struct data_reference
*dr_b
= DDR_B (ddr
);
2681 tree seg_length_a
, seg_length_b
;
2683 if (latch_dominated_by_data_ref (loop
, dr_a
))
2684 seg_length_a
= data_ref_segment_size (dr_a
, niters_plus_one
);
2686 seg_length_a
= data_ref_segment_size (dr_a
, niters
);
2688 if (latch_dominated_by_data_ref (loop
, dr_b
))
2689 seg_length_b
= data_ref_segment_size (dr_b
, niters_plus_one
);
2691 seg_length_b
= data_ref_segment_size (dr_b
, niters
);
2693 unsigned HOST_WIDE_INT access_size_a
2694 = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a
))));
2695 unsigned HOST_WIDE_INT access_size_b
2696 = tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_b
))));
2697 unsigned int align_a
= TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_a
)));
2698 unsigned int align_b
= TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_b
)));
2700 dr_with_seg_len_pair_t dr_with_seg_len_pair
2701 (dr_with_seg_len (dr_a
, seg_length_a
, access_size_a
, align_a
),
2702 dr_with_seg_len (dr_b
, seg_length_b
, access_size_b
, align_b
),
2703 /* ??? Would WELL_ORDERED be safe? */
2704 dr_with_seg_len_pair_t::REORDERED
);
2706 comp_alias_pairs
->safe_push (dr_with_seg_len_pair
);
2709 if (tree_fits_uhwi_p (niters
))
2710 factor
= tree_to_uhwi (niters
);
2712 /* Prune alias check pairs. */
2713 prune_runtime_alias_test_list (comp_alias_pairs
, factor
);
2714 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2716 "Improved number of alias checks from %d to %d\n",
2717 alias_ddrs
->length (), comp_alias_pairs
->length ());
2720 /* Given data dependence relations in ALIAS_DDRS, generate runtime alias
2721 checks and version LOOP under condition of these runtime alias checks. */
2724 version_loop_by_alias_check (vec
<struct partition
*> *partitions
,
2725 class loop
*loop
, vec
<ddr_p
> *alias_ddrs
)
2727 profile_probability prob
;
2728 basic_block cond_bb
;
2730 tree lhs
, arg0
, cond_expr
= NULL_TREE
;
2731 gimple_seq cond_stmts
= NULL
;
2732 gimple
*call_stmt
= NULL
;
2733 auto_vec
<dr_with_seg_len_pair_t
> comp_alias_pairs
;
2735 /* Generate code for runtime alias checks if necessary. */
2736 gcc_assert (alias_ddrs
->length () > 0);
2738 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2740 "Version loop <%d> with runtime alias check\n", loop
->num
);
2742 compute_alias_check_pairs (loop
, alias_ddrs
, &comp_alias_pairs
);
2743 create_runtime_alias_checks (loop
, &comp_alias_pairs
, &cond_expr
);
2744 cond_expr
= force_gimple_operand_1 (cond_expr
, &cond_stmts
,
2745 is_gimple_val
, NULL_TREE
);
2747 /* Depend on vectorizer to fold IFN_LOOP_DIST_ALIAS. */
2748 bool cancelable_p
= flag_tree_loop_vectorize
;
2752 struct partition
*partition
;
2753 for (; partitions
->iterate (i
, &partition
); ++i
)
2754 if (!partition_builtin_p (partition
))
2757 /* If all partitions are builtins, distributing it would be profitable and
2758 we don't want to cancel the runtime alias checks. */
2759 if (i
== partitions
->length ())
2760 cancelable_p
= false;
2763 /* Generate internal function call for loop distribution alias check if the
2764 runtime alias check should be cancelable. */
2767 call_stmt
= gimple_build_call_internal (IFN_LOOP_DIST_ALIAS
,
2768 2, NULL_TREE
, cond_expr
);
2769 lhs
= make_ssa_name (boolean_type_node
);
2770 gimple_call_set_lhs (call_stmt
, lhs
);
2775 prob
= profile_probability::guessed_always ().apply_scale (9, 10);
2776 initialize_original_copy_tables ();
2777 nloop
= loop_version (loop
, lhs
, &cond_bb
, prob
, prob
.invert (),
2778 prob
, prob
.invert (), true);
2779 free_original_copy_tables ();
2780 /* Record the original loop number in newly generated loops. In case of
2781 distribution, the original loop will be distributed and the new loop
2783 loop
->orig_loop_num
= nloop
->num
;
2784 nloop
->orig_loop_num
= nloop
->num
;
2785 nloop
->dont_vectorize
= true;
2786 nloop
->force_vectorize
= false;
2790 /* Record new loop's num in IFN_LOOP_DIST_ALIAS because the original
2791 loop could be destroyed. */
2792 arg0
= build_int_cst (integer_type_node
, loop
->orig_loop_num
);
2793 gimple_call_set_arg (call_stmt
, 0, arg0
);
2794 gimple_seq_add_stmt_without_update (&cond_stmts
, call_stmt
);
2799 gimple_stmt_iterator cond_gsi
= gsi_last_bb (cond_bb
);
2800 gsi_insert_seq_before (&cond_gsi
, cond_stmts
, GSI_SAME_STMT
);
2802 update_ssa (TODO_update_ssa_no_phi
);
2805 /* Return true if loop versioning is needed to distrubute PARTITIONS.
2806 ALIAS_DDRS are data dependence relations for runtime alias check. */
2809 version_for_distribution_p (vec
<struct partition
*> *partitions
,
2810 vec
<ddr_p
> *alias_ddrs
)
2812 /* No need to version loop if we have only one partition. */
2813 if (partitions
->length () == 1)
2816 /* Need to version loop if runtime alias check is necessary. */
2817 return (alias_ddrs
->length () > 0);
2820 /* Compare base offset of builtin mem* partitions P1 and P2. */
2823 offset_cmp (const void *vp1
, const void *vp2
)
2825 struct partition
*p1
= *(struct partition
*const *) vp1
;
2826 struct partition
*p2
= *(struct partition
*const *) vp2
;
2827 unsigned HOST_WIDE_INT o1
= p1
->builtin
->dst_base_offset
;
2828 unsigned HOST_WIDE_INT o2
= p2
->builtin
->dst_base_offset
;
2829 return (o2
< o1
) - (o1
< o2
);
2832 /* Fuse adjacent memset builtin PARTITIONS if possible. This is a special
2833 case optimization transforming below code:
2835 __builtin_memset (&obj, 0, 100);
2837 __builtin_memset (_1, 0, 200);
2839 __builtin_memset (_2, 0, 100);
2843 __builtin_memset (&obj, 0, 400);
2845 Note we don't have dependence information between different partitions
2846 at this point, as a result, we can't handle nonadjacent memset builtin
2847 partitions since dependence might be broken. */
2850 fuse_memset_builtins (vec
<struct partition
*> *partitions
)
2853 struct partition
*part1
, *part2
;
2856 for (i
= 0; partitions
->iterate (i
, &part1
);)
2858 if (part1
->kind
!= PKIND_MEMSET
)
2864 /* Find sub-array of memset builtins of the same base. Index range
2865 of the sub-array is [i, j) with "j > i". */
2866 for (j
= i
+ 1; partitions
->iterate (j
, &part2
); ++j
)
2868 if (part2
->kind
!= PKIND_MEMSET
2869 || !operand_equal_p (part1
->builtin
->dst_base_base
,
2870 part2
->builtin
->dst_base_base
, 0))
2873 /* Memset calls setting different values can't be merged. */
2874 rhs1
= gimple_assign_rhs1 (DR_STMT (part1
->builtin
->dst_dr
));
2875 rhs2
= gimple_assign_rhs1 (DR_STMT (part2
->builtin
->dst_dr
));
2876 if (!operand_equal_p (rhs1
, rhs2
, 0))
2880 /* Stable sort is required in order to avoid breaking dependence. */
2881 gcc_stablesort (&(*partitions
)[i
], j
- i
, sizeof (*partitions
)[i
],
2883 /* Continue with next partition. */
2887 /* Merge all consecutive memset builtin partitions. */
2888 for (i
= 0; i
< partitions
->length () - 1;)
2890 part1
= (*partitions
)[i
];
2891 if (part1
->kind
!= PKIND_MEMSET
)
2897 part2
= (*partitions
)[i
+ 1];
2898 /* Only merge memset partitions of the same base and with constant
2900 if (part2
->kind
!= PKIND_MEMSET
2901 || TREE_CODE (part1
->builtin
->size
) != INTEGER_CST
2902 || TREE_CODE (part2
->builtin
->size
) != INTEGER_CST
2903 || !operand_equal_p (part1
->builtin
->dst_base_base
,
2904 part2
->builtin
->dst_base_base
, 0))
2909 rhs1
= gimple_assign_rhs1 (DR_STMT (part1
->builtin
->dst_dr
));
2910 rhs2
= gimple_assign_rhs1 (DR_STMT (part2
->builtin
->dst_dr
));
2911 int bytev1
= const_with_all_bytes_same (rhs1
);
2912 int bytev2
= const_with_all_bytes_same (rhs2
);
2913 /* Only merge memset partitions of the same value. */
2914 if (bytev1
!= bytev2
|| bytev1
== -1)
2919 wide_int end1
= wi::add (part1
->builtin
->dst_base_offset
,
2920 wi::to_wide (part1
->builtin
->size
));
2921 /* Only merge adjacent memset partitions. */
2922 if (wi::ne_p (end1
, part2
->builtin
->dst_base_offset
))
2927 /* Merge partitions[i] and partitions[i+1]. */
2928 part1
->builtin
->size
= fold_build2 (PLUS_EXPR
, sizetype
,
2929 part1
->builtin
->size
,
2930 part2
->builtin
->size
);
2931 partition_free (part2
);
2932 partitions
->ordered_remove (i
+ 1);
2937 loop_distribution::finalize_partitions (class loop
*loop
,
2938 vec
<struct partition
*> *partitions
,
2939 vec
<ddr_p
> *alias_ddrs
)
2942 struct partition
*partition
, *a
;
2944 if (partitions
->length () == 1
2945 || alias_ddrs
->length () > 0)
2948 unsigned num_builtin
= 0, num_normal
= 0, num_partial_memset
= 0;
2949 bool same_type_p
= true;
2950 enum partition_type type
= ((*partitions
)[0])->type
;
2951 for (i
= 0; partitions
->iterate (i
, &partition
); ++i
)
2953 same_type_p
&= (type
== partition
->type
);
2954 if (partition_builtin_p (partition
))
2960 if (partition
->kind
== PKIND_PARTIAL_MEMSET
)
2961 num_partial_memset
++;
2964 /* Don't distribute current loop into too many loops given we don't have
2965 memory stream cost model. Be even more conservative in case of loop
2966 nest distribution. */
2967 if ((same_type_p
&& num_builtin
== 0
2968 && (loop
->inner
== NULL
|| num_normal
!= 2 || num_partial_memset
!= 1))
2969 || (loop
->inner
!= NULL
2970 && i
>= NUM_PARTITION_THRESHOLD
&& num_normal
> 1)
2971 || (loop
->inner
== NULL
2972 && i
>= NUM_PARTITION_THRESHOLD
&& num_normal
> num_builtin
))
2974 a
= (*partitions
)[0];
2975 for (i
= 1; partitions
->iterate (i
, &partition
); ++i
)
2977 partition_merge_into (NULL
, a
, partition
, FUSE_FINALIZE
);
2978 partition_free (partition
);
2980 partitions
->truncate (1);
2983 /* Fuse memset builtins if possible. */
2984 if (partitions
->length () > 1)
2985 fuse_memset_builtins (partitions
);
2988 /* Distributes the code from LOOP in such a way that producer statements
2989 are placed before consumer statements. Tries to separate only the
2990 statements from STMTS into separate loops. Returns the number of
2991 distributed loops. Set NB_CALLS to number of generated builtin calls.
2992 Set *DESTROY_P to whether LOOP needs to be destroyed. */
2995 loop_distribution::distribute_loop (class loop
*loop
,
2996 const vec
<gimple
*> &stmts
,
2997 control_dependences
*cd
, int *nb_calls
, bool *destroy_p
,
2998 bool only_patterns_p
)
3000 ddrs_table
= new hash_table
<ddr_hasher
> (389);
3002 partition
*partition
;
3007 loop_nest
.create (0);
3008 if (!find_loop_nest (loop
, &loop_nest
))
3010 loop_nest
.release ();
3015 datarefs_vec
.create (20);
3016 has_nonaddressable_dataref_p
= false;
3017 rdg
= build_rdg (loop
, cd
);
3020 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3022 "Loop %d not distributed: failed to build the RDG.\n",
3025 loop_nest
.release ();
3026 free_data_refs (datarefs_vec
);
3031 if (datarefs_vec
.length () > MAX_DATAREFS_NUM
)
3033 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3035 "Loop %d not distributed: too many memory references.\n",
3039 loop_nest
.release ();
3040 free_data_refs (datarefs_vec
);
3045 data_reference_p dref
;
3046 for (i
= 0; datarefs_vec
.iterate (i
, &dref
); ++i
)
3047 dref
->aux
= (void *) (uintptr_t) i
;
3049 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3050 dump_rdg (dump_file
, rdg
);
3052 auto_vec
<struct partition
*, 3> partitions
;
3053 rdg_build_partitions (rdg
, stmts
, &partitions
);
3055 auto_vec
<ddr_p
> alias_ddrs
;
3057 auto_bitmap stmt_in_all_partitions
;
3058 bitmap_copy (stmt_in_all_partitions
, partitions
[0]->stmts
);
3059 for (i
= 1; partitions
.iterate (i
, &partition
); ++i
)
3060 bitmap_and_into (stmt_in_all_partitions
, partitions
[i
]->stmts
);
3062 bool any_builtin
= false;
3063 bool reduction_in_all
= false;
3064 int reduction_partition_num
= -1;
3065 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
3068 |= classify_partition (loop
, rdg
, partition
, stmt_in_all_partitions
);
3069 any_builtin
|= partition_builtin_p (partition
);
3072 /* If we are only distributing patterns but did not detect any,
3081 /* If we are only distributing patterns fuse all partitions that
3082 were not classified as builtins. This also avoids chopping
3083 a loop into pieces, separated by builtin calls. That is, we
3084 only want no or a single loop body remaining. */
3085 struct partition
*into
;
3086 if (only_patterns_p
)
3088 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
3089 if (!partition_builtin_p (into
))
3091 for (++i
; partitions
.iterate (i
, &partition
); ++i
)
3092 if (!partition_builtin_p (partition
))
3094 partition_merge_into (NULL
, into
, partition
, FUSE_NON_BUILTIN
);
3095 partitions
.unordered_remove (i
);
3096 partition_free (partition
);
3101 /* Due to limitations in the transform phase we have to fuse all
3102 reduction partitions into the last partition so the existing
3103 loop will contain all loop-closed PHI nodes. */
3104 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
3105 if (partition_reduction_p (into
))
3107 for (i
= i
+ 1; partitions
.iterate (i
, &partition
); ++i
)
3108 if (partition_reduction_p (partition
))
3110 partition_merge_into (rdg
, into
, partition
, FUSE_REDUCTION
);
3111 partitions
.unordered_remove (i
);
3112 partition_free (partition
);
3116 /* Apply our simple cost model - fuse partitions with similar
3118 for (i
= 0; partitions
.iterate (i
, &into
); ++i
)
3120 bool changed
= false;
3121 for (int j
= i
+ 1; partitions
.iterate (j
, &partition
); ++j
)
3123 if (share_memory_accesses (rdg
, into
, partition
))
3125 partition_merge_into (rdg
, into
, partition
, FUSE_SHARE_REF
);
3126 partitions
.unordered_remove (j
);
3127 partition_free (partition
);
3132 /* If we fused 0 1 2 in step 1 to 0,2 1 as 0 and 2 have similar
3133 accesses when 1 and 2 have similar accesses but not 0 and 1
3134 then in the next iteration we will fail to consider merging
3135 1 into 0,2. So try again if we did any merging into 0. */
3140 /* Put a non-builtin partition last if we need to preserve a reduction.
3141 In most cases this helps to keep a normal partition last avoiding to
3142 spill a reduction result across builtin calls.
3143 ??? The proper way would be to use dependences to see whether we
3144 can move builtin partitions earlier during merge_dep_scc_partitions
3145 and its sort_partitions_by_post_order. Especially when the
3146 dependence graph is composed of multiple independent subgraphs the
3147 heuristic does not work reliably. */
3148 if (reduction_in_all
3149 && partition_builtin_p (partitions
.last()))
3150 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
3151 if (!partition_builtin_p (partition
))
3153 partitions
.unordered_remove (i
);
3154 partitions
.quick_push (partition
);
3158 /* Build the partition dependency graph and fuse partitions in strong
3159 connected component. */
3160 if (partitions
.length () > 1)
3162 /* Don't support loop nest distribution under runtime alias check
3163 since it's not likely to enable many vectorization opportunities.
3164 Also if loop has any data reference which may be not addressable
3165 since alias check needs to take, compare address of the object. */
3166 if (loop
->inner
|| has_nonaddressable_dataref_p
)
3167 merge_dep_scc_partitions (rdg
, &partitions
, false);
3170 merge_dep_scc_partitions (rdg
, &partitions
, true);
3171 if (partitions
.length () > 1)
3172 break_alias_scc_partitions (rdg
, &partitions
, &alias_ddrs
);
3176 finalize_partitions (loop
, &partitions
, &alias_ddrs
);
3178 /* If there is a reduction in all partitions make sure the last
3179 non-builtin partition provides the LC PHI defs. */
3180 if (reduction_in_all
)
3182 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
3183 if (!partition_builtin_p (partition
))
3184 reduction_partition_num
= i
;
3185 if (reduction_partition_num
== -1)
3187 /* If all partitions are builtin, force the last one to
3188 be code generated as normal partition. */
3189 partition
= partitions
.last ();
3190 partition
->kind
= PKIND_NORMAL
;
3194 nbp
= partitions
.length ();
3196 || (nbp
== 1 && !partition_builtin_p (partitions
[0]))
3197 || (nbp
> 1 && partition_contains_all_rw (rdg
, partitions
)))
3203 if (version_for_distribution_p (&partitions
, &alias_ddrs
))
3204 version_loop_by_alias_check (&partitions
, loop
, &alias_ddrs
);
3206 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3209 "distribute loop <%d> into partitions:\n", loop
->num
);
3210 dump_rdg_partitions (dump_file
, partitions
);
3213 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
3215 if (partition_builtin_p (partition
))
3217 *destroy_p
|= generate_code_for_partition (loop
, partition
, i
< nbp
- 1,
3218 i
== reduction_partition_num
);
3222 loop_nest
.release ();
3223 free_data_refs (datarefs_vec
);
3224 for (hash_table
<ddr_hasher
>::iterator iter
= ddrs_table
->begin ();
3225 iter
!= ddrs_table
->end (); ++iter
)
3227 free_dependence_relation (*iter
);
3232 FOR_EACH_VEC_ELT (partitions
, i
, partition
)
3233 partition_free (partition
);
3236 return nbp
- *nb_calls
;
3240 void loop_distribution::bb_top_order_init (void)
3243 int *rpo
= XNEWVEC (int, n_basic_blocks_for_fn (cfun
) - NUM_FIXED_BLOCKS
);
3244 edge entry
= single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
3245 bitmap exit_bbs
= BITMAP_ALLOC (NULL
);
3247 bb_top_order_index
= XNEWVEC (int, last_basic_block_for_fn (cfun
));
3248 bb_top_order_index_size
= last_basic_block_for_fn (cfun
);
3250 entry
->flags
&= ~EDGE_DFS_BACK
;
3251 bitmap_set_bit (exit_bbs
, EXIT_BLOCK
);
3252 rpo_num
= rev_post_order_and_mark_dfs_back_seme (cfun
, entry
, exit_bbs
, true,
3254 BITMAP_FREE (exit_bbs
);
3256 for (int i
= 0; i
< rpo_num
; i
++)
3257 bb_top_order_index
[rpo
[i
]] = i
;
3262 void loop_distribution::bb_top_order_destroy ()
3264 free (bb_top_order_index
);
3265 bb_top_order_index
= NULL
;
3266 bb_top_order_index_size
= 0;
3270 /* Given LOOP, this function records seed statements for distribution in
3271 WORK_LIST. Return false if there is nothing for distribution. */
3274 find_seed_stmts_for_distribution (class loop
*loop
, vec
<gimple
*> *work_list
)
3276 basic_block
*bbs
= get_loop_body_in_dom_order (loop
);
3278 /* Initialize the worklist with stmts we seed the partitions with. */
3279 for (unsigned i
= 0; i
< loop
->num_nodes
; ++i
)
3281 /* In irreducible sub-regions we don't know how to redirect
3282 conditions, so fail. See PR100492. */
3283 if (bbs
[i
]->flags
& BB_IRREDUCIBLE_LOOP
)
3285 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3286 fprintf (dump_file
, "loop %d contains an irreducible region.\n",
3288 work_list
->truncate (0);
3291 for (gphi_iterator gsi
= gsi_start_phis (bbs
[i
]);
3292 !gsi_end_p (gsi
); gsi_next (&gsi
))
3294 gphi
*phi
= gsi
.phi ();
3295 if (virtual_operand_p (gimple_phi_result (phi
)))
3297 /* Distribute stmts which have defs that are used outside of
3299 if (!stmt_has_scalar_dependences_outside_loop (loop
, phi
))
3301 work_list
->safe_push (phi
);
3303 for (gimple_stmt_iterator gsi
= gsi_start_bb (bbs
[i
]);
3304 !gsi_end_p (gsi
); gsi_next (&gsi
))
3306 gimple
*stmt
= gsi_stmt (gsi
);
3308 /* Ignore clobbers, they do not have true side effects. */
3309 if (gimple_clobber_p (stmt
))
3312 /* If there is a stmt with side-effects bail out - we
3313 cannot and should not distribute this loop. */
3314 if (gimple_has_side_effects (stmt
))
3320 /* Distribute stmts which have defs that are used outside of
3322 if (stmt_has_scalar_dependences_outside_loop (loop
, stmt
))
3324 /* Otherwise only distribute stores for now. */
3325 else if (!gimple_vdef (stmt
))
3328 work_list
->safe_push (stmt
);
3331 bool res
= work_list
->length () > 0;
3332 if (res
&& !can_copy_bbs_p (bbs
, loop
->num_nodes
))
3334 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3335 fprintf (dump_file
, "cannot copy loop %d.\n", loop
->num
);
3342 /* A helper function for generate_{rawmemchr,strlen}_builtin functions in order
3343 to place new statements SEQ before LOOP and replace the old reduction
3344 variable with the new one. */
3347 generate_reduction_builtin_1 (loop_p loop
, gimple_seq
&seq
,
3348 tree reduction_var_old
, tree reduction_var_new
,
3349 const char *info
, machine_mode load_mode
)
3351 gcc_assert (flag_tree_loop_distribute_patterns
);
3353 /* Place new statements before LOOP. */
3354 gimple_stmt_iterator gsi
= gsi_last_bb (loop_preheader_edge (loop
)->src
);
3355 gsi_insert_seq_after (&gsi
, seq
, GSI_CONTINUE_LINKING
);
3357 /* Replace old reduction variable with new one. */
3358 imm_use_iterator iter
;
3360 use_operand_p use_p
;
3361 FOR_EACH_IMM_USE_STMT (stmt
, iter
, reduction_var_old
)
3363 FOR_EACH_IMM_USE_ON_STMT (use_p
, iter
)
3364 SET_USE (use_p
, reduction_var_new
);
3369 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3370 fprintf (dump_file
, info
, GET_MODE_NAME (load_mode
));
3373 /* Generate a call to rawmemchr and place it before LOOP. REDUCTION_VAR is
3374 replaced with a fresh SSA name representing the result of the call. */
3377 generate_rawmemchr_builtin (loop_p loop
, tree reduction_var
,
3378 data_reference_p store_dr
, tree base
, tree pattern
,
3381 gimple_seq seq
= NULL
;
3383 tree mem
= force_gimple_operand (base
, &seq
, true, NULL_TREE
);
3384 gimple
*fn_call
= gimple_build_call_internal (IFN_RAWMEMCHR
, 2, mem
, pattern
);
3385 tree reduction_var_new
= copy_ssa_name (reduction_var
);
3386 gimple_call_set_lhs (fn_call
, reduction_var_new
);
3387 gimple_set_location (fn_call
, loc
);
3388 gimple_seq_add_stmt (&seq
, fn_call
);
3392 gassign
*g
= gimple_build_assign (DR_REF (store_dr
), reduction_var_new
);
3393 gimple_seq_add_stmt (&seq
, g
);
3396 generate_reduction_builtin_1 (loop
, seq
, reduction_var
, reduction_var_new
,
3397 "generated rawmemchr%s\n",
3398 TYPE_MODE (TREE_TYPE (TREE_TYPE (base
))));
3401 /* Helper function for generate_strlen_builtin(,_using_rawmemchr) */
3404 generate_strlen_builtin_1 (loop_p loop
, gimple_seq
&seq
,
3405 tree reduction_var_old
, tree reduction_var_new
,
3406 machine_mode mode
, tree start_len
)
3408 /* REDUCTION_VAR_NEW has either size type or ptrdiff type and must be
3409 converted if types of old and new reduction variable are not compatible. */
3410 reduction_var_new
= gimple_convert (&seq
, TREE_TYPE (reduction_var_old
),
3413 /* Loops of the form `for (i=42; s[i]; ++i);` have an additional start
3415 if (!integer_zerop (start_len
))
3417 tree lhs
= make_ssa_name (TREE_TYPE (reduction_var_new
));
3418 gimple
*g
= gimple_build_assign (lhs
, PLUS_EXPR
, reduction_var_new
,
3420 gimple_seq_add_stmt (&seq
, g
);
3421 reduction_var_new
= lhs
;
3424 generate_reduction_builtin_1 (loop
, seq
, reduction_var_old
, reduction_var_new
,
3425 "generated strlen%s\n", mode
);
3428 /* Generate a call to strlen and place it before LOOP. REDUCTION_VAR is
3429 replaced with a fresh SSA name representing the result of the call. */
3432 generate_strlen_builtin (loop_p loop
, tree reduction_var
, tree base
,
3433 tree start_len
, location_t loc
)
3435 gimple_seq seq
= NULL
;
3437 tree reduction_var_new
= make_ssa_name (size_type_node
);
3439 tree mem
= force_gimple_operand (base
, &seq
, true, NULL_TREE
);
3440 tree fn
= build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_STRLEN
));
3441 gimple
*fn_call
= gimple_build_call (fn
, 1, mem
);
3442 gimple_call_set_lhs (fn_call
, reduction_var_new
);
3443 gimple_set_location (fn_call
, loc
);
3444 gimple_seq_add_stmt (&seq
, fn_call
);
3446 generate_strlen_builtin_1 (loop
, seq
, reduction_var
, reduction_var_new
,
3450 /* Generate code in order to mimic the behaviour of strlen but this time over
3451 an array of elements with mode different than QI. REDUCTION_VAR is replaced
3452 with a fresh SSA name representing the result, i.e., the length. */
3455 generate_strlen_builtin_using_rawmemchr (loop_p loop
, tree reduction_var
,
3456 tree base
, tree load_type
,
3457 tree start_len
, location_t loc
)
3459 gimple_seq seq
= NULL
;
3461 tree start
= force_gimple_operand (base
, &seq
, true, NULL_TREE
);
3462 tree zero
= build_zero_cst (load_type
);
3463 gimple
*fn_call
= gimple_build_call_internal (IFN_RAWMEMCHR
, 2, start
, zero
);
3464 tree end
= make_ssa_name (TREE_TYPE (base
));
3465 gimple_call_set_lhs (fn_call
, end
);
3466 gimple_set_location (fn_call
, loc
);
3467 gimple_seq_add_stmt (&seq
, fn_call
);
3469 /* Determine the number of elements between START and END by
3470 evaluating (END - START) / sizeof (*START). */
3471 tree diff
= make_ssa_name (ptrdiff_type_node
);
3472 gimple
*diff_stmt
= gimple_build_assign (diff
, POINTER_DIFF_EXPR
, end
, start
);
3473 gimple_seq_add_stmt (&seq
, diff_stmt
);
3474 /* Let SIZE be the size of each character. */
3475 tree size
= gimple_convert (&seq
, ptrdiff_type_node
,
3476 TYPE_SIZE_UNIT (load_type
));
3477 tree count
= make_ssa_name (ptrdiff_type_node
);
3478 gimple
*count_stmt
= gimple_build_assign (count
, TRUNC_DIV_EXPR
, diff
, size
);
3479 gimple_seq_add_stmt (&seq
, count_stmt
);
3481 generate_strlen_builtin_1 (loop
, seq
, reduction_var
, count
,
3482 TYPE_MODE (load_type
),
3486 /* Return true if we can count at least as many characters by taking pointer
3487 difference as we can count via reduction_var without an overflow. Thus
3488 compute 2^n < (2^(m-1) / s) where n = TYPE_PRECISION (reduction_var_type),
3489 m = TYPE_PRECISION (ptrdiff_type_node), and s = size of each character. */
3491 reduction_var_overflows_first (tree reduction_var_type
, tree load_type
)
3493 widest_int n2
= wi::lshift (1, TYPE_PRECISION (reduction_var_type
));;
3494 widest_int m2
= wi::lshift (1, TYPE_PRECISION (ptrdiff_type_node
) - 1);
3495 widest_int s
= wi::to_widest (TYPE_SIZE_UNIT (load_type
));
3496 return wi::ltu_p (n2
, wi::udiv_trunc (m2
, s
));
3500 determine_reduction_stmt_1 (const loop_p loop
, const basic_block
*bbs
)
3502 gimple
*reduction_stmt
= NULL
;
3504 for (unsigned i
= 0, ninsns
= 0; i
< loop
->num_nodes
; ++i
)
3506 basic_block bb
= bbs
[i
];
3508 for (gphi_iterator bsi
= gsi_start_phis (bb
); !gsi_end_p (bsi
);
3509 gsi_next_nondebug (&bsi
))
3511 gphi
*phi
= bsi
.phi ();
3512 if (virtual_operand_p (gimple_phi_result (phi
)))
3514 if (stmt_has_scalar_dependences_outside_loop (loop
, phi
))
3518 reduction_stmt
= phi
;
3522 for (gimple_stmt_iterator bsi
= gsi_start_bb (bb
); !gsi_end_p (bsi
);
3523 gsi_next_nondebug (&bsi
), ++ninsns
)
3525 /* Bail out early for loops which are unlikely to match. */
3528 gimple
*stmt
= gsi_stmt (bsi
);
3529 if (gimple_clobber_p (stmt
))
3531 if (gimple_code (stmt
) == GIMPLE_LABEL
)
3533 if (gimple_has_volatile_ops (stmt
))
3535 if (stmt_has_scalar_dependences_outside_loop (loop
, stmt
))
3539 reduction_stmt
= stmt
;
3544 return reduction_stmt
;
3547 /* If LOOP has a single non-volatile reduction statement, then return a pointer
3548 to it. Otherwise return NULL. */
3550 determine_reduction_stmt (const loop_p loop
)
3552 basic_block
*bbs
= get_loop_body (loop
);
3553 gimple
*reduction_stmt
= determine_reduction_stmt_1 (loop
, bbs
);
3555 return reduction_stmt
;
3558 /* Transform loops which mimic the effects of builtins rawmemchr or strlen and
3559 replace them accordingly. For example, a loop of the form
3561 for (; *p != 42; ++p);
3565 p = rawmemchr<MODE> (p, 42);
3567 under the assumption that rawmemchr is available for a particular MODE.
3571 for (i = 42; s[i]; ++i);
3573 which is replaced by
3575 i = (int)strlen (&s[42]) + 42;
3577 for some character array S. In case array S is not of type character array
3580 i = (int)(rawmemchr<MODE> (&s[42], 0) - &s[42]) + 42;
3582 assuming that rawmemchr is available for a particular MODE. */
3585 loop_distribution::transform_reduction_loop (loop_p loop
)
3587 gimple
*reduction_stmt
;
3588 data_reference_p load_dr
= NULL
, store_dr
= NULL
;
3590 edge e
= single_exit (loop
);
3591 gcond
*cond
= safe_dyn_cast
<gcond
*> (*gsi_last_bb (e
->src
));
3594 /* Ensure loop condition is an (in)equality test and loop is exited either if
3595 the inequality test fails or the equality test succeeds. */
3596 if (!(e
->flags
& EDGE_FALSE_VALUE
&& gimple_cond_code (cond
) == NE_EXPR
)
3597 && !(e
->flags
& EDGE_TRUE_VALUE
&& gimple_cond_code (cond
) == EQ_EXPR
))
3599 /* A limitation of the current implementation is that we only support
3600 constant patterns in (in)equality tests. */
3601 tree pattern
= gimple_cond_rhs (cond
);
3602 if (TREE_CODE (pattern
) != INTEGER_CST
)
3605 reduction_stmt
= determine_reduction_stmt (loop
);
3607 /* A limitation of the current implementation is that we require a reduction
3608 statement. Therefore, loops without a reduction statement as in the
3609 following are not recognized:
3611 void foo (void) { for (; *p; ++p); } */
3612 if (reduction_stmt
== NULL
)
3615 /* Reduction variables are guaranteed to be SSA names. */
3617 switch (gimple_code (reduction_stmt
))
3621 reduction_var
= gimple_get_lhs (reduction_stmt
);
3624 /* Bail out e.g. for GIMPLE_CALL. */
3628 struct graph
*rdg
= build_rdg (loop
, NULL
);
3631 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3633 "Loop %d not transformed: failed to build the RDG.\n",
3638 auto_bitmap partition_stmts
;
3639 bitmap_set_range (partition_stmts
, 0, rdg
->n_vertices
);
3640 find_single_drs (loop
, rdg
, partition_stmts
, &store_dr
, &load_dr
);
3643 /* Bail out if there is no single load. */
3644 if (load_dr
== NULL
)
3647 /* Reaching this point we have a loop with a single reduction variable,
3648 a single load, and an optional single store. */
3650 tree load_ref
= DR_REF (load_dr
);
3651 tree load_type
= TREE_TYPE (load_ref
);
3652 tree load_access_base
= build_fold_addr_expr (load_ref
);
3653 tree load_access_size
= TYPE_SIZE_UNIT (load_type
);
3654 affine_iv load_iv
, reduction_iv
;
3656 if (!INTEGRAL_TYPE_P (load_type
)
3657 || !type_has_mode_precision_p (load_type
))
3660 /* We already ensured that the loop condition tests for (in)equality where the
3661 rhs is a constant pattern. Now ensure that the lhs is the result of the
3663 if (gimple_cond_lhs (cond
) != gimple_assign_lhs (DR_STMT (load_dr
)))
3666 /* Bail out if no affine induction variable with constant step can be
3668 if (!simple_iv (loop
, loop
, load_access_base
, &load_iv
, false))
3671 /* Bail out if memory accesses are not consecutive or not growing. */
3672 if (!operand_equal_p (load_iv
.step
, load_access_size
, 0))
3675 if (!simple_iv (loop
, loop
, reduction_var
, &reduction_iv
, false))
3678 /* Handle rawmemchr like loops. */
3679 if (operand_equal_p (load_iv
.base
, reduction_iv
.base
)
3680 && operand_equal_p (load_iv
.step
, reduction_iv
.step
))
3684 /* Ensure that we store to X and load from X+I where I>0. */
3685 if (TREE_CODE (load_iv
.base
) != POINTER_PLUS_EXPR
3686 || !integer_onep (TREE_OPERAND (load_iv
.base
, 1)))
3688 tree ptr_base
= TREE_OPERAND (load_iv
.base
, 0);
3689 if (TREE_CODE (ptr_base
) != SSA_NAME
)
3691 gimple
*def
= SSA_NAME_DEF_STMT (ptr_base
);
3692 if (!gimple_assign_single_p (def
)
3693 || gimple_assign_rhs1 (def
) != DR_REF (store_dr
))
3695 /* Ensure that the reduction value is stored. */
3696 if (gimple_assign_rhs1 (DR_STMT (store_dr
)) != reduction_var
)
3699 /* Bail out if target does not provide rawmemchr for a certain mode. */
3700 machine_mode mode
= TYPE_MODE (load_type
);
3701 if (direct_optab_handler (rawmemchr_optab
, mode
) == CODE_FOR_nothing
)
3703 location_t loc
= gimple_location (DR_STMT (load_dr
));
3704 generate_rawmemchr_builtin (loop
, reduction_var
, store_dr
, load_iv
.base
,
3709 /* Handle strlen like loops. */
3710 if (store_dr
== NULL
3711 && integer_zerop (pattern
)
3712 && INTEGRAL_TYPE_P (TREE_TYPE (reduction_var
))
3713 && TREE_CODE (reduction_iv
.base
) == INTEGER_CST
3714 && TREE_CODE (reduction_iv
.step
) == INTEGER_CST
3715 && integer_onep (reduction_iv
.step
))
3717 location_t loc
= gimple_location (DR_STMT (load_dr
));
3718 tree reduction_var_type
= TREE_TYPE (reduction_var
);
3719 /* While determining the length of a string an overflow might occur.
3720 If an overflow only occurs in the loop implementation and not in the
3721 strlen implementation, then either the overflow is undefined or the
3722 truncated result of strlen equals the one of the loop. Otherwise if
3723 an overflow may also occur in the strlen implementation, then
3724 replacing a loop by a call to strlen is sound whenever we ensure that
3725 if an overflow occurs in the strlen implementation, then also an
3726 overflow occurs in the loop implementation which is undefined. It
3727 seems reasonable to relax this and assume that the strlen
3728 implementation cannot overflow in case sizetype is big enough in the
3729 sense that an overflow can only happen for string objects which are
3730 bigger than half of the address space; at least for 32-bit targets and
3733 For strlen which makes use of rawmemchr the maximal length of a string
3734 which can be determined without an overflow is PTRDIFF_MAX / S where
3735 each character has size S. Since an overflow for ptrdiff type is
3736 undefined we have to make sure that if an overflow occurs, then an
3737 overflow occurs in the loop implementation, too, and this is
3738 undefined, too. Similar as before we relax this and assume that no
3739 string object is larger than half of the address space; at least for
3740 32-bit targets and up. */
3741 if (TYPE_MODE (load_type
) == TYPE_MODE (char_type_node
)
3742 && TYPE_PRECISION (load_type
) == TYPE_PRECISION (char_type_node
)
3743 && ((TYPE_PRECISION (sizetype
) >= TYPE_PRECISION (ptr_type_node
) - 1
3744 && TYPE_PRECISION (ptr_type_node
) >= 32)
3745 || (TYPE_OVERFLOW_UNDEFINED (reduction_var_type
)
3746 && TYPE_PRECISION (reduction_var_type
) <= TYPE_PRECISION (sizetype
)))
3747 && builtin_decl_implicit (BUILT_IN_STRLEN
))
3748 generate_strlen_builtin (loop
, reduction_var
, load_iv
.base
,
3749 reduction_iv
.base
, loc
);
3750 else if (direct_optab_handler (rawmemchr_optab
, TYPE_MODE (load_type
))
3752 && ((TYPE_PRECISION (ptrdiff_type_node
) == TYPE_PRECISION (ptr_type_node
)
3753 && TYPE_PRECISION (ptrdiff_type_node
) >= 32)
3754 || (TYPE_OVERFLOW_UNDEFINED (reduction_var_type
)
3755 && reduction_var_overflows_first (reduction_var_type
, load_type
))))
3756 generate_strlen_builtin_using_rawmemchr (loop
, reduction_var
,
3759 reduction_iv
.base
, loc
);
3768 /* Given innermost LOOP, return the outermost enclosing loop that forms a
3769 perfect loop nest. */
3772 prepare_perfect_loop_nest (class loop
*loop
)
3774 class loop
*outer
= loop_outer (loop
);
3775 tree niters
= number_of_latch_executions (loop
);
3777 /* TODO: We only support the innermost 3-level loop nest distribution
3778 because of compilation time issue for now. This should be relaxed
3779 in the future. Note we only allow 3-level loop nest distribution
3780 when parallelizing loops. */
3781 while ((loop
->inner
== NULL
3782 || (loop
->inner
->inner
== NULL
&& flag_tree_parallelize_loops
> 1))
3783 && loop_outer (outer
)
3784 && outer
->inner
== loop
&& loop
->next
== NULL
3785 && single_exit (outer
)
3786 && !chrec_contains_symbols_defined_in_loop (niters
, outer
->num
)
3787 && (niters
= number_of_latch_executions (outer
)) != NULL_TREE
3788 && niters
!= chrec_dont_know
)
3791 outer
= loop_outer (loop
);
3799 loop_distribution::execute (function
*fun
)
3801 bool changed
= false;
3803 control_dependences
*cd
= NULL
;
3804 auto_vec
<loop_p
> loops_to_be_destroyed
;
3806 if (number_of_loops (fun
) <= 1)
3809 bb_top_order_init ();
3811 FOR_ALL_BB_FN (bb
, fun
)
3813 gimple_stmt_iterator gsi
;
3814 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3815 gimple_set_uid (gsi_stmt (gsi
), -1);
3816 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
3817 gimple_set_uid (gsi_stmt (gsi
), -1);
3820 /* We can at the moment only distribute non-nested loops, thus restrict
3821 walking to innermost loops. */
3822 for (auto loop
: loops_list (cfun
, LI_ONLY_INNERMOST
))
3824 /* Don't distribute multiple exit edges loop, or cold loop when
3825 not doing pattern detection. */
3826 if (!single_exit (loop
)
3827 || (!flag_tree_loop_distribute_patterns
3828 && !optimize_loop_for_speed_p (loop
)))
3831 /* If niters is unknown don't distribute loop but rather try to transform
3832 it to a call to a builtin. */
3833 tree niters
= number_of_latch_executions (loop
);
3834 if (niters
== NULL_TREE
|| niters
== chrec_dont_know
)
3836 datarefs_vec
.create (20);
3837 if (flag_tree_loop_distribute_patterns
3838 && transform_reduction_loop (loop
))
3841 loops_to_be_destroyed
.safe_push (loop
);
3842 if (dump_enabled_p ())
3844 dump_user_location_t loc
= find_loop_location (loop
);
3845 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
,
3846 loc
, "Loop %d transformed into a builtin.\n",
3850 free_data_refs (datarefs_vec
);
3854 /* Get the perfect loop nest for distribution. */
3855 loop
= prepare_perfect_loop_nest (loop
);
3856 for (; loop
; loop
= loop
->inner
)
3858 auto_vec
<gimple
*> work_list
;
3859 if (!find_seed_stmts_for_distribution (loop
, &work_list
))
3862 const char *str
= loop
->inner
? " nest" : "";
3863 dump_user_location_t loc
= find_loop_location (loop
);
3866 calculate_dominance_info (CDI_DOMINATORS
);
3867 calculate_dominance_info (CDI_POST_DOMINATORS
);
3868 cd
= new control_dependences ();
3869 free_dominance_info (CDI_POST_DOMINATORS
);
3873 int nb_generated_loops
, nb_generated_calls
;
3875 = distribute_loop (loop
, work_list
, cd
, &nb_generated_calls
,
3876 &destroy_p
, (!optimize_loop_for_speed_p (loop
)
3877 || !flag_tree_loop_distribution
));
3879 loops_to_be_destroyed
.safe_push (loop
);
3881 if (nb_generated_loops
+ nb_generated_calls
> 0)
3884 if (dump_enabled_p ())
3885 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS
,
3886 loc
, "Loop%s %d distributed: split to %d loops "
3887 "and %d library calls.\n", str
, loop
->num
,
3888 nb_generated_loops
, nb_generated_calls
);
3893 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3894 fprintf (dump_file
, "Loop%s %d not distributed.\n", str
, loop
->num
);
3901 if (bb_top_order_index
!= NULL
)
3902 bb_top_order_destroy ();
3906 /* Destroy loop bodies that could not be reused. Do this late as we
3907 otherwise can end up refering to stale data in control dependences. */
3910 FOR_EACH_VEC_ELT (loops_to_be_destroyed
, i
, loop
)
3911 destroy_loop (loop
);
3913 /* Cached scalar evolutions now may refer to wrong or non-existing
3916 mark_virtual_operands_for_renaming (fun
);
3917 rewrite_into_loop_closed_ssa (NULL
, TODO_update_ssa
);
3920 checking_verify_loop_structure ();
3922 return changed
? TODO_cleanup_cfg
: 0;
3926 /* Distribute all loops in the current function. */
3930 const pass_data pass_data_loop_distribution
=
3932 GIMPLE_PASS
, /* type */
3934 OPTGROUP_LOOP
, /* optinfo_flags */
3935 TV_TREE_LOOP_DISTRIBUTION
, /* tv_id */
3936 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3937 0, /* properties_provided */
3938 0, /* properties_destroyed */
3939 0, /* todo_flags_start */
3940 0, /* todo_flags_finish */
3943 class pass_loop_distribution
: public gimple_opt_pass
3946 pass_loop_distribution (gcc::context
*ctxt
)
3947 : gimple_opt_pass (pass_data_loop_distribution
, ctxt
)
3950 /* opt_pass methods: */
3951 bool gate (function
*) final override
3953 return flag_tree_loop_distribution
3954 || flag_tree_loop_distribute_patterns
;
3957 unsigned int execute (function
*) final override
;
3959 }; // class pass_loop_distribution
3962 pass_loop_distribution::execute (function
*fun
)
3964 return loop_distribution ().execute (fun
);
3970 make_pass_loop_distribution (gcc::context
*ctxt
)
3972 return new pass_loop_distribution (ctxt
);