1	/* Loop distribution.
2	Copyright (C) 2006-2024 Free Software Foundation, Inc.
3	Contributed by Georges-Andre Silber <Georges-Andre.Silber@ensmp.fr>
4	and Sebastian Pop <sebastian.pop@amd.com>.
5
6	This file is part of GCC.
7
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
11	later version.
12
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
16	for more details.
17
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/>. */
21
22	/* This pass performs loop distribution: for example, the loop
23
24	|DO I = 2, N
25	| A(I) = B(I) + C
26	| D(I) = A(I-1)*E
27	|ENDDO
28
29	is transformed to
30
31	|DOALL I = 2, N
32	| A(I) = B(I) + C
33	|ENDDO
34	|
35	|DOALL I = 2, N
36	| D(I) = A(I-1)*E
37	|ENDDO
38
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:
44
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
66	data dependencies.
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.
84
85	TODO:
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
90	data reuse. */
91
92	#include "config.h"
93	#include "system.h"
94	#include "coretypes.h"
95	#include "backend.h"
96	#include "tree.h"
97	#include "gimple.h"
98	#include "cfghooks.h"
99	#include "tree-pass.h"
100	#include "ssa.h"
101	#include "gimple-pretty-print.h"
102	#include "fold-const.h"
103	#include "cfganal.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"
113	#include "cfgloop.h"
114	#include "tree-scalar-evolution.h"
115	#include "tree-vectorizer.h"
116	#include "tree-eh.h"
117	#include "gimple-fold.h"
118	#include "tree-affine.h"
119	#include "intl.h"
120	#include "rtl.h"
121	#include "memmodel.h"
122	#include "optabs.h"
123	#include "tree-ssa-loop-niter.h"
124
125
126	#define MAX_DATAREFS_NUM \
127	((unsigned) param_loop_max_datarefs_for_datadeps)
128
129	/* Threshold controlling number of distributed partitions. Given it may
130	be unnecessary if a memory stream cost model is invented in the future,
131	we define it as a temporary macro, rather than a parameter. */
132	#define NUM_PARTITION_THRESHOLD (4)
133
134	/* Hashtable helpers. */
135
136	struct ddr_hasher : nofree_ptr_hash <struct data_dependence_relation>
137	{
138	static inline hashval_t hash (const data_dependence_relation *);
139	static inline bool equal (const data_dependence_relation *,
140	const data_dependence_relation *);
141	};
142
143	/* Hash function for data dependence. */
144
145	inline hashval_t
146	ddr_hasher::hash (const data_dependence_relation *ddr)
147	{
148	inchash::hash h;
149	h.add_ptr (DDR_A (ddr));
150	h.add_ptr (DDR_B (ddr));
151	return h.end ();
152	}
153
154	/* Hash table equality function for data dependence. */
155
156	inline bool
157	ddr_hasher::equal (const data_dependence_relation *ddr1,
158	const data_dependence_relation *ddr2)
159	{
160	return (DDR_A (ddr1) == DDR_A (ddr2) && DDR_B (ddr1) == DDR_B (ddr2));
161	}
162
163
164
165	#define DR_INDEX(dr) ((uintptr_t) (dr)->aux)
166
167	/* A Reduced Dependence Graph (RDG) vertex representing a statement. */
168	struct rdg_vertex
169	{
170	/* The statement represented by this vertex. */
171	gimple *stmt;
172
173	/* Vector of data-references in this statement. */
174	vec<data_reference_p> datarefs;
175
176	/* True when the statement contains a write to memory. */
177	bool has_mem_write;
178
179	/* True when the statement contains a read from memory. */
180	bool has_mem_reads;
181	};
182
183	#define RDGV_STMT(V) ((struct rdg_vertex *) ((V)->data))->stmt
184	#define RDGV_DATAREFS(V) ((struct rdg_vertex *) ((V)->data))->datarefs
185	#define RDGV_HAS_MEM_WRITE(V) ((struct rdg_vertex *) ((V)->data))->has_mem_write
186	#define RDGV_HAS_MEM_READS(V) ((struct rdg_vertex *) ((V)->data))->has_mem_reads
187	#define RDG_STMT(RDG, I) RDGV_STMT (&(RDG->vertices[I]))
188	#define RDG_DATAREFS(RDG, I) RDGV_DATAREFS (&(RDG->vertices[I]))
189	#define RDG_MEM_WRITE_STMT(RDG, I) RDGV_HAS_MEM_WRITE (&(RDG->vertices[I]))
190	#define RDG_MEM_READS_STMT(RDG, I) RDGV_HAS_MEM_READS (&(RDG->vertices[I]))
191
192	/* Data dependence type. */
193
194	enum rdg_dep_type
195	{
196	/* Read After Write (RAW). */
197	flow_dd = 'f',
198
199	/* Control dependence (execute conditional on). */
200	control_dd = 'c'
201	};
202
203	/* Dependence information attached to an edge of the RDG. */
204
205	struct rdg_edge
206	{
207	/* Type of the dependence. */
208	enum rdg_dep_type type;
209	};
210
211	#define RDGE_TYPE(E) ((struct rdg_edge *) ((E)->data))->type
212
213	/* Kind of distributed loop. */
214	enum partition_kind {
215	PKIND_NORMAL,
216	/* Partial memset stands for a paritition can be distributed into a loop
217	of memset calls, rather than a single memset call. It's handled just
218	like a normal parition, i.e, distributed as separate loop, no memset
219	call is generated.
220
221	Note: This is a hacking fix trying to distribute ZERO-ing stmt in a
222	loop nest as deep as possible. As a result, parloop achieves better
223	parallelization by parallelizing deeper loop nest. This hack should
224	be unnecessary and removed once distributed memset can be understood
225	and analyzed in data reference analysis. See PR82604 for more. */
226	PKIND_PARTIAL_MEMSET,
227	PKIND_MEMSET, PKIND_MEMCPY, PKIND_MEMMOVE
228	};
229
230	/* Type of distributed loop. */
231	enum partition_type {
232	/* The distributed loop can be executed parallelly. */
233	PTYPE_PARALLEL = 0,
234	/* The distributed loop has to be executed sequentially. */
235	PTYPE_SEQUENTIAL
236	};
237
238	/* Builtin info for loop distribution. */
239	struct builtin_info
240	{
241	/* data-references a kind != PKIND_NORMAL partition is about. */
242	data_reference_p dst_dr;
243	data_reference_p src_dr;
244	/* Base address and size of memory objects operated by the builtin. Note
245	both dest and source memory objects must have the same size. */
246	tree dst_base;
247	tree src_base;
248	tree size;
249	/* Base and offset part of dst_base after stripping constant offset. This
250	is only used in memset builtin distribution for now. */
251	tree dst_base_base;
252	unsigned HOST_WIDE_INT dst_base_offset;
253	};
254
255	/* Partition for loop distribution. */
256	struct partition
257	{
258	/* Statements of the partition. */
259	bitmap stmts;
260	/* True if the partition defines variable which is used outside of loop. */
261	bool reduction_p;
262	location_t loc;
263	enum partition_kind kind;
264	enum partition_type type;
265	/* Data references in the partition. */
266	bitmap datarefs;
267	/* Information of builtin parition. */
268	struct builtin_info *builtin;
269	};
270
271	/* Partitions are fused because of different reasons. */
272	enum fuse_type
273	{
274	FUSE_NON_BUILTIN = 0,
275	FUSE_REDUCTION = 1,
276	FUSE_SHARE_REF = 2,
277	FUSE_SAME_SCC = 3,
278	FUSE_FINALIZE = 4
279	};
280
281	/* Description on different fusing reason. */
282	static const char *fuse_message[] = {
283	"they are non-builtins",
284	"they have reductions",
285	"they have shared memory refs",
286	"they are in the same dependence scc",
287	"there is no point to distribute loop"};
288
289
290	/* Dump vertex I in RDG to FILE. */
291
292	static void
293	dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
294	{
295	struct vertex *v = &(rdg->vertices[i]);
296	struct graph_edge *e;
297
298	fprintf (stream: file, format: "(vertex %d: (%s%s) (in:", i,
299	RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
300	RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
301
302	if (v->pred)
303	for (e = v->pred; e; e = e->pred_next)
304	fprintf (stream: file, format: " %d", e->src);
305
306	fprintf (stream: file, format: ") (out:");
307
308	if (v->succ)
309	for (e = v->succ; e; e = e->succ_next)
310	fprintf (stream: file, format: " %d", e->dest);
311
312	fprintf (stream: file, format: ")\n");
313	print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
314	fprintf (stream: file, format: ")\n");
315	}
316
317	/* Call dump_rdg_vertex on stderr. */
318
319	DEBUG_FUNCTION void
320	debug_rdg_vertex (struct graph *rdg, int i)
321	{
322	dump_rdg_vertex (stderr, rdg, i);
323	}
324
325	/* Dump the reduced dependence graph RDG to FILE. */
326
327	static void
328	dump_rdg (FILE *file, struct graph *rdg)
329	{
330	fprintf (stream: file, format: "(rdg\n");
331	for (int i = 0; i < rdg->n_vertices; i++)
332	dump_rdg_vertex (file, rdg, i);
333	fprintf (stream: file, format: ")\n");
334	}
335
336	/* Call dump_rdg on stderr. */
337
338	DEBUG_FUNCTION void
339	debug_rdg (struct graph *rdg)
340	{
341	dump_rdg (stderr, rdg);
342	}
343
344	static void
345	dot_rdg_1 (FILE *file, struct graph *rdg)
346	{
347	int i;
348	pretty_printer buffer;
349	pp_needs_newline (&buffer) = false;
350	buffer.buffer->stream = file;
351
352	fprintf (stream: file, format: "digraph RDG {\n");
353
354	for (i = 0; i < rdg->n_vertices; i++)
355	{
356	struct vertex *v = &(rdg->vertices[i]);
357	struct graph_edge *e;
358
359	fprintf (stream: file, format: "%d [label=\"[%d] ", i, i);
360	pp_gimple_stmt_1 (&buffer, RDGV_STMT (v), 0, TDF_SLIM);
361	pp_flush (&buffer);
362	fprintf (stream: file, format: "\"]\n");
363
364	/* Highlight reads from memory. */
365	if (RDG_MEM_READS_STMT (rdg, i))
366	fprintf (stream: file, format: "%d [style=filled, fillcolor=green]\n", i);
367
368	/* Highlight stores to memory. */
369	if (RDG_MEM_WRITE_STMT (rdg, i))
370	fprintf (stream: file, format: "%d [style=filled, fillcolor=red]\n", i);
371
372	if (v->succ)
373	for (e = v->succ; e; e = e->succ_next)
374	switch (RDGE_TYPE (e))
375	{
376	case flow_dd:
377	/* These are the most common dependences: don't print these. */
378	fprintf (stream: file, format: "%d -> %d \n", i, e->dest);
379	break;
380
381	case control_dd:
382	fprintf (stream: file, format: "%d -> %d [label=control] \n", i, e->dest);
383	break;
384
385	default:
386	gcc_unreachable ();
387	}
388	}
389
390	fprintf (stream: file, format: "}\n\n");
391	}
392
393	/* Display the Reduced Dependence Graph using dotty. */
394
395	DEBUG_FUNCTION void
396	dot_rdg (struct graph *rdg)
397	{
398	/* When debugging, you may want to enable the following code. */
399	#ifdef HAVE_POPEN
400	FILE *file = popen (command: "dot -Tx11", modes: "w");
401	if (!file)
402	return;
403	dot_rdg_1 (file, rdg);
404	fflush (stream: file);
405	close (fileno (file));
406	pclose (stream: file);
407	#else
408	dot_rdg_1 (stderr, rdg);
409	#endif
410	}
411
412	/* Returns the index of STMT in RDG. */
413
414	static int
415	rdg_vertex_for_stmt (struct graph *rdg ATTRIBUTE_UNUSED, gimple *stmt)
416	{
417	int index = gimple_uid (g: stmt);
418	gcc_checking_assert (index == -1 || RDG_STMT (rdg, index) == stmt);
419	return index;
420	}
421
422	/* Creates dependence edges in RDG for all the uses of DEF. IDEF is
423	the index of DEF in RDG. */
424
425	static void
426	create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
427	{
428	use_operand_p imm_use_p;
429	imm_use_iterator iterator;
430
431	FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
432	{
433	struct graph_edge *e;
434	int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
435
436	if (use < 0)
437	continue;
438
439	e = add_edge (rdg, idef, use);
440	e->data = XNEW (struct rdg_edge);
441	RDGE_TYPE (e) = flow_dd;
442	}
443	}
444
445	/* Creates an edge for the control dependences of BB to the vertex V. */
446
447	static void
448	create_edge_for_control_dependence (struct graph *rdg, basic_block bb,
449	int v, control_dependences *cd)
450	{
451	bitmap_iterator bi;
452	unsigned edge_n;
453	EXECUTE_IF_SET_IN_BITMAP (cd->get_edges_dependent_on (bb->index),
454	0, edge_n, bi)
455	{
456	basic_block cond_bb = cd->get_edge_src (edge_n);
457	gimple *stmt = *gsi_last_bb (bb: cond_bb);
458	if (stmt && is_ctrl_stmt (stmt))
459	{
460	struct graph_edge *e;
461	int c = rdg_vertex_for_stmt (rdg, stmt);
462	if (c < 0)
463	continue;
464
465	e = add_edge (rdg, c, v);
466	e->data = XNEW (struct rdg_edge);
467	RDGE_TYPE (e) = control_dd;
468	}
469	}
470	}
471
472	/* Creates the edges of the reduced dependence graph RDG. */
473
474	static void
475	create_rdg_flow_edges (struct graph *rdg)
476	{
477	int i;
478	def_operand_p def_p;
479	ssa_op_iter iter;
480
481	for (i = 0; i < rdg->n_vertices; i++)
482	FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
483	iter, SSA_OP_DEF)
484	create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), idef: i);
485	}
486
487	/* Creates the edges of the reduced dependence graph RDG. */
488
489	static void
490	create_rdg_cd_edges (struct graph *rdg, control_dependences *cd, loop_p loop)
491	{
492	int i;
493
494	for (i = 0; i < rdg->n_vertices; i++)
495	{
496	gimple *stmt = RDG_STMT (rdg, i);
497	if (gimple_code (g: stmt) == GIMPLE_PHI)
498	{
499	edge_iterator ei;
500	edge e;
501	FOR_EACH_EDGE (e, ei, gimple_bb (stmt)->preds)
502	if (flow_bb_inside_loop_p (loop, e->src))
503	create_edge_for_control_dependence (rdg, bb: e->src, v: i, cd);
504	}
505	else
506	create_edge_for_control_dependence (rdg, bb: gimple_bb (g: stmt), v: i, cd);
507	}
508	}
509
510
511	class loop_distribution
512	{
513	private:
514	/* The loop (nest) to be distributed. */
515	vec<loop_p> loop_nest;
516
517	/* Vector of data references in the loop to be distributed. */
518	vec<data_reference_p> datarefs_vec;
519
520	/* If there is nonaddressable data reference in above vector. */
521	bool has_nonaddressable_dataref_p;
522
523	/* Store index of data reference in aux field. */
524
525	/* Hash table for data dependence relation in the loop to be distributed. */
526	hash_table<ddr_hasher> *ddrs_table;
527
528	/* Array mapping basic block's index to its topological order. */
529	int *bb_top_order_index;
530	/* And size of the array. */
531	int bb_top_order_index_size;
532
533	/* Build the vertices of the reduced dependence graph RDG. Return false
534	if that failed. */
535	bool create_rdg_vertices (struct graph *rdg, const vec<gimple *> &stmts,
536	loop_p loop);
537
538	/* Initialize STMTS with all the statements of LOOP. We use topological
539	order to discover all statements. The order is important because
540	generate_loops_for_partition is using the same traversal for identifying
541	statements in loop copies. */
542	void stmts_from_loop (class loop *loop, vec<gimple *> *stmts);
543
544
545	/* Build the Reduced Dependence Graph (RDG) with one vertex per statement of
546	LOOP, and one edge per flow dependence or control dependence from control
547	dependence CD. During visiting each statement, data references are also
548	collected and recorded in global data DATAREFS_VEC. */
549	struct graph * build_rdg (class loop *loop, control_dependences *cd);
550
551	/* Merge PARTITION into the partition DEST. RDG is the reduced dependence
552	graph and we update type for result partition if it is non-NULL. */
553	void partition_merge_into (struct graph *rdg,
554	partition *dest, partition *partition,
555	enum fuse_type ft);
556
557
558	/* Return data dependence relation for data references A and B. The two
559	data references must be in lexicographic order wrto reduced dependence
560	graph RDG. We firstly try to find ddr from global ddr hash table. If
561	it doesn't exist, compute the ddr and cache it. */
562	data_dependence_relation * get_data_dependence (struct graph *rdg,
563	data_reference_p a,
564	data_reference_p b);
565
566
567	/* In reduced dependence graph RDG for loop distribution, return true if
568	dependence between references DR1 and DR2 leads to a dependence cycle
569	and such dependence cycle can't be resolved by runtime alias check. */
570	bool data_dep_in_cycle_p (struct graph *rdg, data_reference_p dr1,
571	data_reference_p dr2);
572
573
574	/* Given reduced dependence graph RDG, PARTITION1 and PARTITION2, update
575	PARTITION1's type after merging PARTITION2 into PARTITION1. */
576	void update_type_for_merge (struct graph *rdg,
577	partition *partition1, partition *partition2);
578
579
580	/* Returns a partition with all the statements needed for computing
581	the vertex V of the RDG, also including the loop exit conditions. */
582	partition *build_rdg_partition_for_vertex (struct graph *rdg, int v);
583
584	/* Given data references DST_DR and SRC_DR in loop nest LOOP and RDG, classify
585	if it forms builtin memcpy or memmove call. */
586	void classify_builtin_ldst (loop_p loop, struct graph *rdg, partition *partition,
587	data_reference_p dst_dr, data_reference_p src_dr);
588
589	/* Classifies the builtin kind we can generate for PARTITION of RDG and LOOP.
590	For the moment we detect memset, memcpy and memmove patterns. Bitmap
591	STMT_IN_ALL_PARTITIONS contains statements belonging to all partitions.
592	Returns true if there is a reduction in all partitions and we
593	possibly did not mark PARTITION as having one for this reason. */
594
595	bool
596	classify_partition (loop_p loop,
597	struct graph *rdg, partition *partition,
598	bitmap stmt_in_all_partitions);
599
600
601	/* Returns true when PARTITION1 and PARTITION2 access the same memory
602	object in RDG. */
603	bool share_memory_accesses (struct graph *rdg,
604	partition *partition1, partition *partition2);
605
606	/* For each seed statement in STARTING_STMTS, this function builds
607	partition for it by adding depended statements according to RDG.
608	All partitions are recorded in PARTITIONS. */
609	void rdg_build_partitions (struct graph *rdg,
610	vec<gimple *> starting_stmts,
611	vec<partition *> *partitions);
612
613	/* Compute partition dependence created by the data references in DRS1
614	and DRS2, modify and return DIR according to that. IF ALIAS_DDR is
615	not NULL, we record dependence introduced by possible alias between
616	two data references in ALIAS_DDRS; otherwise, we simply ignore such
617	dependence as if it doesn't exist at all. */
618	int pg_add_dependence_edges (struct graph *rdg, int dir, bitmap drs1,
619	bitmap drs2, vec<ddr_p> *alias_ddrs);
620
621
622	/* Build and return partition dependence graph for PARTITIONS. RDG is
623	reduced dependence graph for the loop to be distributed. If IGNORE_ALIAS_P
624	is true, data dependence caused by possible alias between references
625	is ignored, as if it doesn't exist at all; otherwise all depdendences
626	are considered. */
627	struct graph *build_partition_graph (struct graph *rdg,
628	vec<struct partition *> *partitions,
629	bool ignore_alias_p);
630
631	/* Given reduced dependence graph RDG merge strong connected components
632	of PARTITIONS. If IGNORE_ALIAS_P is true, data dependence caused by
633	possible alias between references is ignored, as if it doesn't exist
634	at all; otherwise all depdendences are considered. */
635	void merge_dep_scc_partitions (struct graph *rdg, vec<struct partition *>
636	*partitions, bool ignore_alias_p);
637
638	/* This is the main function breaking strong conected components in
639	PARTITIONS giving reduced depdendence graph RDG. Store data dependence
640	relations for runtime alias check in ALIAS_DDRS. */
641	void break_alias_scc_partitions (struct graph *rdg, vec<struct partition *>
642	*partitions, vec<ddr_p> *alias_ddrs);
643
644
645	/* Fuse PARTITIONS of LOOP if necessary before finalizing distribution.
646	ALIAS_DDRS contains ddrs which need runtime alias check. */
647	void finalize_partitions (class loop *loop, vec<struct partition *>
648	*partitions, vec<ddr_p> *alias_ddrs);
649
650	/* Distributes the code from LOOP in such a way that producer statements
651	are placed before consumer statements. Tries to separate only the
652	statements from STMTS into separate loops. Returns the number of
653	distributed loops. Set NB_CALLS to number of generated builtin calls.
654	Set *DESTROY_P to whether LOOP needs to be destroyed. */
655	int distribute_loop (class loop *loop, const vec<gimple *> &stmts,
656	control_dependences *cd, int *nb_calls, bool *destroy_p,
657	bool only_patterns_p);
658
659	/* Transform loops which mimic the effects of builtins rawmemchr or strlen and
660	replace them accordingly. */
661	bool transform_reduction_loop (loop_p loop);
662
663	/* Compute topological order for basic blocks. Topological order is
664	needed because data dependence is computed for data references in
665	lexicographical order. */
666	void bb_top_order_init (void);
667
668	void bb_top_order_destroy (void);
669
670	public:
671
672	/* Getter for bb_top_order. */
673
674	inline int get_bb_top_order_index_size (void)
675	{
676	return bb_top_order_index_size;
677	}
678
679	inline int get_bb_top_order_index (int i)
680	{
681	return bb_top_order_index[i];
682	}
683
684	unsigned int execute (function *fun);
685	};
686
687
688	/* If X has a smaller topological sort number than Y, returns -1;
689	if greater, returns 1. */
690	static int
691	bb_top_order_cmp_r (const void *x, const void *y, void *loop)
692	{
693	loop_distribution *_loop =
694	(loop_distribution *) loop;
695
696	basic_block bb1 = *(const basic_block *) x;
697	basic_block bb2 = *(const basic_block *) y;
698
699	int bb_top_order_index_size = _loop->get_bb_top_order_index_size ();
700
701	gcc_assert (bb1->index < bb_top_order_index_size
702	&& bb2->index < bb_top_order_index_size);
703	gcc_assert (bb1 == bb2
704	|| _loop->get_bb_top_order_index(bb1->index)
705	!= _loop->get_bb_top_order_index(bb2->index));
706
707	return (_loop->get_bb_top_order_index(i: bb1->index) -
708	_loop->get_bb_top_order_index(i: bb2->index));
709	}
710
711	bool
712	loop_distribution::create_rdg_vertices (struct graph *rdg,
713	const vec<gimple *> &stmts,
714	loop_p loop)
715	{
716	int i;
717	gimple *stmt;
718
719	FOR_EACH_VEC_ELT (stmts, i, stmt)
720	{
721	struct vertex *v = &(rdg->vertices[i]);
722
723	/* Record statement to vertex mapping. */
724	gimple_set_uid (g: stmt, uid: i);
725
726	v->data = XNEW (struct rdg_vertex);
727	RDGV_STMT (v) = stmt;
728	RDGV_DATAREFS (v).create (nelems: 0);
729	RDGV_HAS_MEM_WRITE (v) = false;
730	RDGV_HAS_MEM_READS (v) = false;
731	if (gimple_code (g: stmt) == GIMPLE_PHI)
732	continue;
733
734	unsigned drp = datarefs_vec.length ();
735	if (!find_data_references_in_stmt (loop, stmt, &datarefs_vec))
736	return false;
737	for (unsigned j = drp; j < datarefs_vec.length (); ++j)
738	{
739	data_reference_p dr = datarefs_vec[j];
740	if (DR_IS_READ (dr))
741	RDGV_HAS_MEM_READS (v) = true;
742	else
743	RDGV_HAS_MEM_WRITE (v) = true;
744	RDGV_DATAREFS (v).safe_push (obj: dr);
745	has_nonaddressable_dataref_p |= may_be_nonaddressable_p (expr: dr->ref);
746	}
747	}
748	return true;
749	}
750
751	void
752	loop_distribution::stmts_from_loop (class loop *loop, vec<gimple *> *stmts)
753	{
754	unsigned int i;
755	basic_block *bbs = get_loop_body_in_custom_order (loop, this, bb_top_order_cmp_r);
756
757	for (i = 0; i < loop->num_nodes; i++)
758	{
759	basic_block bb = bbs[i];
760
761	for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (i: bsi);
762	gsi_next (i: &bsi))
763	if (!virtual_operand_p (op: gimple_phi_result (gs: bsi.phi ())))
764	stmts->safe_push (obj: bsi.phi ());
765
766	for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (i: bsi);
767	gsi_next (i: &bsi))
768	{
769	gimple *stmt = gsi_stmt (i: bsi);
770	if (gimple_code (g: stmt) != GIMPLE_LABEL && !is_gimple_debug (gs: stmt))
771	stmts->safe_push (obj: stmt);
772	}
773	}
774
775	free (ptr: bbs);
776	}
777
778	/* Free the reduced dependence graph RDG. */
779
780	static void
781	free_rdg (struct graph *rdg)
782	{
783	int i;
784
785	for (i = 0; i < rdg->n_vertices; i++)
786	{
787	struct vertex *v = &(rdg->vertices[i]);
788	struct graph_edge *e;
789
790	for (e = v->succ; e; e = e->succ_next)
791	free (ptr: e->data);
792
793	if (v->data)
794	{
795	gimple_set_uid (RDGV_STMT (v), uid: -1);
796	(RDGV_DATAREFS (v)).release ();
797	free (ptr: v->data);
798	}
799	}
800
801	free_graph (g: rdg);
802	}
803
804	struct graph *
805	loop_distribution::build_rdg (class loop *loop, control_dependences *cd)
806	{
807	struct graph *rdg;
808
809	/* Create the RDG vertices from the stmts of the loop nest. */
810	auto_vec<gimple *, 10> stmts;
811	stmts_from_loop (loop, stmts: &stmts);
812	rdg = new_graph (stmts.length ());
813	if (!create_rdg_vertices (rdg, stmts, loop))
814	{
815	free_rdg (rdg);
816	return NULL;
817	}
818	stmts.release ();
819
820	create_rdg_flow_edges (rdg);
821	if (cd)
822	create_rdg_cd_edges (rdg, cd, loop);
823
824	return rdg;
825	}
826
827
828	/* Allocate and initialize a partition from BITMAP. */
829
830	static partition *
831	partition_alloc (void)
832	{
833	partition *partition = XCNEW (struct partition);
834	partition->stmts = BITMAP_ALLOC (NULL);
835	partition->reduction_p = false;
836	partition->loc = UNKNOWN_LOCATION;
837	partition->kind = PKIND_NORMAL;
838	partition->type = PTYPE_PARALLEL;
839	partition->datarefs = BITMAP_ALLOC (NULL);
840	return partition;
841	}
842
843	/* Free PARTITION. */
844
845	static void
846	partition_free (partition *partition)
847	{
848	BITMAP_FREE (partition->stmts);
849	BITMAP_FREE (partition->datarefs);
850	if (partition->builtin)
851	free (ptr: partition->builtin);
852
853	free (ptr: partition);
854	}
855
856	/* Returns true if the partition can be generated as a builtin. */
857
858	static bool
859	partition_builtin_p (partition *partition)
860	{
861	return partition->kind > PKIND_PARTIAL_MEMSET;
862	}
863
864	/* Returns true if the partition contains a reduction. */
865
866	static bool
867	partition_reduction_p (partition *partition)
868	{
869	return partition->reduction_p;
870	}
871
872	void
873	loop_distribution::partition_merge_into (struct graph *rdg,
874	partition *dest, partition *partition, enum fuse_type ft)
875	{
876	if (dump_file && (dump_flags & TDF_DETAILS))
877	{
878	fprintf (stream: dump_file, format: "Fuse partitions because %s:\n", fuse_message[ft]);
879	fprintf (stream: dump_file, format: " Part 1: ");
880	dump_bitmap (file: dump_file, map: dest->stmts);
881	fprintf (stream: dump_file, format: " Part 2: ");
882	dump_bitmap (file: dump_file, map: partition->stmts);
883	}
884
885	dest->kind = PKIND_NORMAL;
886	if (dest->type == PTYPE_PARALLEL)
887	dest->type = partition->type;
888
889	bitmap_ior_into (dest->stmts, partition->stmts);
890	if (partition_reduction_p (partition))
891	dest->reduction_p = true;
892
893	/* Further check if any data dependence prevents us from executing the
894	new partition parallelly. */
895	if (dest->type == PTYPE_PARALLEL && rdg != NULL)
896	update_type_for_merge (rdg, partition1: dest, partition2: partition);
897
898	bitmap_ior_into (dest->datarefs, partition->datarefs);
899	}
900
901
902	/* Returns true when DEF is an SSA_NAME defined in LOOP and used after
903	the LOOP. */
904
905	static bool
906	ssa_name_has_uses_outside_loop_p (tree def, loop_p loop)
907	{
908	imm_use_iterator imm_iter;
909	use_operand_p use_p;
910
911	FOR_EACH_IMM_USE_FAST (use_p, imm_iter, def)
912	{
913	if (is_gimple_debug (USE_STMT (use_p)))
914	continue;
915
916	basic_block use_bb = gimple_bb (USE_STMT (use_p));
917	if (!flow_bb_inside_loop_p (loop, use_bb))
918	return true;
919	}
920
921	return false;
922	}
923
924	/* Returns true when STMT defines a scalar variable used after the
925	loop LOOP. */
926
927	static bool
928	stmt_has_scalar_dependences_outside_loop (loop_p loop, gimple *stmt)
929	{
930	def_operand_p def_p;
931	ssa_op_iter op_iter;
932
933	if (gimple_code (g: stmt) == GIMPLE_PHI)
934	return ssa_name_has_uses_outside_loop_p (def: gimple_phi_result (gs: stmt), loop);
935
936	FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, op_iter, SSA_OP_DEF)
937	if (ssa_name_has_uses_outside_loop_p (DEF_FROM_PTR (def_p), loop))
938	return true;
939
940	return false;
941	}
942
943	/* Return a copy of LOOP placed before LOOP. */
944
945	static class loop *
946	copy_loop_before (class loop *loop, bool redirect_lc_phi_defs)
947	{
948	class loop *res;
949	edge preheader = loop_preheader_edge (loop);
950
951	initialize_original_copy_tables ();
952	res = slpeel_tree_duplicate_loop_to_edge_cfg (loop, single_exit (loop), NULL,
953	NULL, preheader, NULL, false);
954	gcc_assert (res != NULL);
955
956	/* When a not last partition is supposed to keep the LC PHIs computed
957	adjust their definitions. */
958	if (redirect_lc_phi_defs)
959	{
960	edge exit = single_exit (loop);
961	for (gphi_iterator si = gsi_start_phis (exit->dest); !gsi_end_p (i: si);
962	gsi_next (i: &si))
963	{
964	gphi *phi = si.phi ();
965	if (virtual_operand_p (op: gimple_phi_result (gs: phi)))
966	continue;
967	use_operand_p use_p = PHI_ARG_DEF_PTR_FROM_EDGE (phi, exit);
968	tree new_def = get_current_def (USE_FROM_PTR (use_p));
969	SET_USE (use_p, new_def);
970	}
971	}
972
973	free_original_copy_tables ();
974	delete_update_ssa ();
975
976	return res;
977	}
978
979	/* Creates an empty basic block after LOOP. */
980
981	static void
982	create_bb_after_loop (class loop *loop)
983	{
984	edge exit = single_exit (loop);
985
986	if (!exit)
987	return;
988
989	split_edge (exit);
990	}
991
992	/* Generate code for PARTITION from the code in LOOP. The loop is
993	copied when COPY_P is true. All the statements not flagged in the
994	PARTITION bitmap are removed from the loop or from its copy. The
995	statements are indexed in sequence inside a basic block, and the
996	basic blocks of a loop are taken in dom order. */
997
998	static void
999	generate_loops_for_partition (class loop *loop, partition *partition,
1000	bool copy_p, bool keep_lc_phis_p)
1001	{
1002	unsigned i;
1003	basic_block *bbs;
1004
1005	if (copy_p)
1006	{
1007	int orig_loop_num = loop->orig_loop_num;
1008	loop = copy_loop_before (loop, redirect_lc_phi_defs: keep_lc_phis_p);
1009	gcc_assert (loop != NULL);
1010	loop->orig_loop_num = orig_loop_num;
1011	create_preheader (loop, CP_SIMPLE_PREHEADERS);
1012	create_bb_after_loop (loop);
1013	}
1014	else
1015	{
1016	/* Origin number is set to the new versioned loop's num. */
1017	gcc_assert (loop->orig_loop_num != loop->num);
1018	}
1019
1020	/* Remove stmts not in the PARTITION bitmap. */
1021	bbs = get_loop_body_in_dom_order (loop);
1022
1023	if (MAY_HAVE_DEBUG_BIND_STMTS)
1024	for (i = 0; i < loop->num_nodes; i++)
1025	{
1026	basic_block bb = bbs[i];
1027
1028	for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (i: bsi);
1029	gsi_next (i: &bsi))
1030	{
1031	gphi *phi = bsi.phi ();
1032	if (!virtual_operand_p (op: gimple_phi_result (gs: phi))
1033	&& !bitmap_bit_p (partition->stmts, gimple_uid (g: phi)))
1034	reset_debug_uses (phi);
1035	}
1036
1037	for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (i: bsi); gsi_next (i: &bsi))
1038	{
1039	gimple *stmt = gsi_stmt (i: bsi);
1040	if (gimple_code (g: stmt) != GIMPLE_LABEL
1041	&& !is_gimple_debug (gs: stmt)
1042	&& !bitmap_bit_p (partition->stmts, gimple_uid (g: stmt)))
1043	reset_debug_uses (stmt);
1044	}
1045	}
1046
1047	for (i = 0; i < loop->num_nodes; i++)
1048	{
1049	basic_block bb = bbs[i];
1050	edge inner_exit = NULL;
1051
1052	if (loop != bb->loop_father)
1053	inner_exit = single_exit (bb->loop_father);
1054
1055	for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (i: bsi);)
1056	{
1057	gphi *phi = bsi.phi ();
1058	if (!virtual_operand_p (op: gimple_phi_result (gs: phi))
1059	&& !bitmap_bit_p (partition->stmts, gimple_uid (g: phi)))
1060	remove_phi_node (&bsi, true);
1061	else
1062	gsi_next (i: &bsi);
1063	}
1064
1065	for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (i: bsi);)
1066	{
1067	gimple *stmt = gsi_stmt (i: bsi);
1068	if (gimple_code (g: stmt) != GIMPLE_LABEL
1069	&& !is_gimple_debug (gs: stmt)
1070	&& !bitmap_bit_p (partition->stmts, gimple_uid (g: stmt)))
1071	{
1072	/* In distribution of loop nest, if bb is inner loop's exit_bb,
1073	we choose its exit edge/path in order to avoid generating
1074	infinite loop. For all other cases, we choose an arbitrary
1075	path through the empty CFG part that this unnecessary
1076	control stmt controls. */
1077	if (gcond *cond_stmt = dyn_cast <gcond *> (p: stmt))
1078	{
1079	if (inner_exit && inner_exit->flags & EDGE_TRUE_VALUE)
1080	gimple_cond_make_true (gs: cond_stmt);
1081	else
1082	gimple_cond_make_false (gs: cond_stmt);
1083	update_stmt (s: stmt);
1084	}
1085	else if (gimple_code (g: stmt) == GIMPLE_SWITCH)
1086	{
1087	gswitch *switch_stmt = as_a <gswitch *> (p: stmt);
1088	gimple_switch_set_index
1089	(gs: switch_stmt, CASE_LOW (gimple_switch_label (switch_stmt, 1)));
1090	update_stmt (s: stmt);
1091	}
1092	else
1093	{
1094	unlink_stmt_vdef (stmt);
1095	gsi_remove (&bsi, true);
1096	release_defs (stmt);
1097	continue;
1098	}
1099	}
1100	gsi_next (i: &bsi);
1101	}
1102	}
1103
1104	free (ptr: bbs);
1105	}
1106
1107	/* If VAL memory representation contains the same value in all bytes,
1108	return that value, otherwise return -1.
1109	E.g. for 0x24242424 return 0x24, for IEEE double
1110	747708026454360457216.0 return 0x44, etc. */
1111
1112	static int
1113	const_with_all_bytes_same (tree val)
1114	{
1115	unsigned char buf[64];
1116	int i, len;
1117
1118	if (integer_zerop (val)
1119	|| (TREE_CODE (val) == CONSTRUCTOR
1120	&& !TREE_CLOBBER_P (val)
1121	&& CONSTRUCTOR_NELTS (val) == 0))
1122	return 0;
1123
1124	if (real_zerop (val))
1125	{
1126	/* Only return 0 for +0.0, not for -0.0, which doesn't have
1127	an all bytes same memory representation. Don't transform
1128	-0.0 stores into +0.0 even for !HONOR_SIGNED_ZEROS. */
1129	switch (TREE_CODE (val))
1130	{
1131	case REAL_CST:
1132	if (!real_isneg (TREE_REAL_CST_PTR (val)))
1133	return 0;
1134	break;
1135	case COMPLEX_CST:
1136	if (!const_with_all_bytes_same (TREE_REALPART (val))
1137	&& !const_with_all_bytes_same (TREE_IMAGPART (val)))
1138	return 0;
1139	break;
1140	case VECTOR_CST:
1141	{
1142	unsigned int count = vector_cst_encoded_nelts (t: val);
1143	unsigned int j;
1144	for (j = 0; j < count; ++j)
1145	if (const_with_all_bytes_same (VECTOR_CST_ENCODED_ELT (val, j)))
1146	break;
1147	if (j == count)
1148	return 0;
1149	break;
1150	}
1151	default:
1152	break;
1153	}
1154	}
1155
1156	if (CHAR_BIT != 8 || BITS_PER_UNIT != 8)
1157	return -1;
1158
1159	len = native_encode_expr (val, buf, sizeof (buf));
1160	if (len == 0)
1161	return -1;
1162	for (i = 1; i < len; i++)
1163	if (buf[i] != buf[0])
1164	return -1;
1165	return buf[0];
1166	}
1167
1168	/* Generate a call to memset for PARTITION in LOOP. */
1169
1170	static void
1171	generate_memset_builtin (class loop *loop, partition *partition)
1172	{
1173	gimple_stmt_iterator gsi;
1174	tree mem, fn, nb_bytes;
1175	tree val;
1176	struct builtin_info *builtin = partition->builtin;
1177	gimple *fn_call;
1178
1179	/* The new statements will be placed before LOOP. */
1180	gsi = gsi_last_bb (bb: loop_preheader_edge (loop)->src);
1181
1182	nb_bytes = rewrite_to_non_trapping_overflow (builtin->size);
1183	nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE,
1184	false, GSI_CONTINUE_LINKING);
1185	mem = rewrite_to_non_trapping_overflow (builtin->dst_base);
1186	mem = force_gimple_operand_gsi (&gsi, mem, true, NULL_TREE,
1187	false, GSI_CONTINUE_LINKING);
1188
1189	/* This exactly matches the pattern recognition in classify_partition. */
1190	val = gimple_assign_rhs1 (DR_STMT (builtin->dst_dr));
1191	/* Handle constants like 0x15151515 and similarly
1192	floating point constants etc. where all bytes are the same. */
1193	int bytev = const_with_all_bytes_same (val);
1194	if (bytev != -1)
1195	val = build_int_cst (integer_type_node, bytev);
1196	else if (TREE_CODE (val) == INTEGER_CST)
1197	val = fold_convert (integer_type_node, val);
1198	else if (!useless_type_conversion_p (integer_type_node, TREE_TYPE (val)))
1199	{
1200	tree tem = make_ssa_name (integer_type_node);
1201	gimple *cstmt = gimple_build_assign (tem, NOP_EXPR, val);
1202	gsi_insert_after (&gsi, cstmt, GSI_CONTINUE_LINKING);
1203	val = tem;
1204	}
1205
1206	fn = build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_MEMSET));
1207	fn_call = gimple_build_call (fn, 3, mem, val, nb_bytes);
1208	gimple_set_location (g: fn_call, location: partition->loc);
1209	gsi_insert_after (&gsi, fn_call, GSI_CONTINUE_LINKING);
1210	fold_stmt (&gsi);
1211
1212	if (dump_file && (dump_flags & TDF_DETAILS))
1213	{
1214	fprintf (stream: dump_file, format: "generated memset");
1215	if (bytev == 0)
1216	fprintf (stream: dump_file, format: " zero\n");
1217	else
1218	fprintf (stream: dump_file, format: "\n");
1219	}
1220	}
1221
1222	/* Generate a call to memcpy for PARTITION in LOOP. */
1223
1224	static void
1225	generate_memcpy_builtin (class loop *loop, partition *partition)
1226	{
1227	gimple_stmt_iterator gsi;
1228	gimple *fn_call;
1229	tree dest, src, fn, nb_bytes;
1230	enum built_in_function kind;
1231	struct builtin_info *builtin = partition->builtin;
1232
1233	/* The new statements will be placed before LOOP. */
1234	gsi = gsi_last_bb (bb: loop_preheader_edge (loop)->src);
1235
1236	nb_bytes = rewrite_to_non_trapping_overflow (builtin->size);
1237	nb_bytes = force_gimple_operand_gsi (&gsi, nb_bytes, true, NULL_TREE,
1238	false, GSI_CONTINUE_LINKING);
1239	dest = rewrite_to_non_trapping_overflow (builtin->dst_base);
1240	src = rewrite_to_non_trapping_overflow (builtin->src_base);
1241	if (partition->kind == PKIND_MEMCPY
1242	|| ! ptr_derefs_may_alias_p (dest, src))
1243	kind = BUILT_IN_MEMCPY;
1244	else
1245	kind = BUILT_IN_MEMMOVE;
1246	/* Try harder if we're copying a constant size. */
1247	if (kind == BUILT_IN_MEMMOVE && poly_int_tree_p (t: nb_bytes))
1248	{
1249	aff_tree asrc, adest;
1250	tree_to_aff_combination (src, ptr_type_node, &asrc);
1251	tree_to_aff_combination (dest, ptr_type_node, &adest);
1252	aff_combination_scale (&adest, -1);
1253	aff_combination_add (&asrc, &adest);
1254	if (aff_comb_cannot_overlap_p (&asrc, wi::to_poly_widest (t: nb_bytes),
1255	wi::to_poly_widest (t: nb_bytes)))
1256	kind = BUILT_IN_MEMCPY;
1257	}
1258
1259	dest = force_gimple_operand_gsi (&gsi, dest, true, NULL_TREE,
1260	false, GSI_CONTINUE_LINKING);
1261	src = force_gimple_operand_gsi (&gsi, src, true, NULL_TREE,
1262	false, GSI_CONTINUE_LINKING);
1263	fn = build_fold_addr_expr (builtin_decl_implicit (kind));
1264	fn_call = gimple_build_call (fn, 3, dest, src, nb_bytes);
1265	gimple_set_location (g: fn_call, location: partition->loc);
1266	gsi_insert_after (&gsi, fn_call, GSI_CONTINUE_LINKING);
1267	fold_stmt (&gsi);
1268
1269	if (dump_file && (dump_flags & TDF_DETAILS))
1270	{
1271	if (kind == BUILT_IN_MEMCPY)
1272	fprintf (stream: dump_file, format: "generated memcpy\n");
1273	else
1274	fprintf (stream: dump_file, format: "generated memmove\n");
1275	}
1276	}
1277
1278	/* Remove and destroy the loop LOOP. */
1279
1280	static void
1281	destroy_loop (class loop *loop)
1282	{
1283	unsigned nbbs = loop->num_nodes;
1284	edge exit = single_exit (loop);
1285	basic_block src = loop_preheader_edge (loop)->src, dest = exit->dest;
1286	basic_block *bbs;
1287	unsigned i;
1288
1289	bbs = get_loop_body_in_dom_order (loop);
1290
1291	gimple_stmt_iterator dst_gsi = gsi_after_labels (bb: exit->dest);
1292	bool safe_p = single_pred_p (bb: exit->dest);
1293	for (unsigned i = 0; i < nbbs; ++i)
1294	{
1295	/* We have made sure to not leave any dangling uses of SSA
1296	names defined in the loop. With the exception of virtuals.
1297	Make sure we replace all uses of virtual defs that will remain
1298	outside of the loop with the bare symbol as delete_basic_block
1299	will release them. */
1300	for (gphi_iterator gsi = gsi_start_phis (bbs[i]); !gsi_end_p (i: gsi);
1301	gsi_next (i: &gsi))
1302	{
1303	gphi *phi = gsi.phi ();
1304	if (virtual_operand_p (op: gimple_phi_result (gs: phi)))
1305	mark_virtual_phi_result_for_renaming (phi);
1306	}
1307	for (gimple_stmt_iterator gsi = gsi_start_bb (bb: bbs[i]); !gsi_end_p (i: gsi);)
1308	{
1309	gimple *stmt = gsi_stmt (i: gsi);
1310	tree vdef = gimple_vdef (g: stmt);
1311	if (vdef && TREE_CODE (vdef) == SSA_NAME)
1312	mark_virtual_operand_for_renaming (vdef);
1313	/* Also move and eventually reset debug stmts. We can leave
1314	constant values in place in case the stmt dominates the exit.
1315	??? Non-constant values from the last iteration can be
1316	replaced with final values if we can compute them. */
1317	if (gimple_debug_bind_p (s: stmt))
1318	{
1319	tree val = gimple_debug_bind_get_value (dbg: stmt);
1320	gsi_move_before (&gsi, &dst_gsi);
1321	if (val
1322	&& (!safe_p
1323	|| !is_gimple_min_invariant (val)
1324	|| !dominated_by_p (CDI_DOMINATORS, exit->src, bbs[i])))
1325	{
1326	gimple_debug_bind_reset_value (dbg: stmt);
1327	update_stmt (s: stmt);
1328	}
1329	}
1330	else
1331	gsi_next (i: &gsi);
1332	}
1333	}
1334
1335	redirect_edge_pred (exit, src);
1336	exit->flags &= ~(EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
1337	exit->flags |= EDGE_FALLTHRU;
1338	cancel_loop_tree (loop);
1339	rescan_loop_exit (exit, false, true);
1340
1341	i = nbbs;
1342	do
1343	{
1344	--i;
1345	delete_basic_block (bbs[i]);
1346	}
1347	while (i != 0);
1348
1349	free (ptr: bbs);
1350
1351	set_immediate_dominator (CDI_DOMINATORS, dest,
1352	recompute_dominator (CDI_DOMINATORS, dest));
1353	}
1354
1355	/* Generates code for PARTITION. Return whether LOOP needs to be destroyed. */
1356
1357	static bool
1358	generate_code_for_partition (class loop *loop,
1359	partition *partition, bool copy_p,
1360	bool keep_lc_phis_p)
1361	{
1362	switch (partition->kind)
1363	{
1364	case PKIND_NORMAL:
1365	case PKIND_PARTIAL_MEMSET:
1366	/* Reductions all have to be in the last partition. */
1367	gcc_assert (!partition_reduction_p (partition)
1368	|| !copy_p);
1369	generate_loops_for_partition (loop, partition, copy_p,
1370	keep_lc_phis_p);
1371	return false;
1372
1373	case PKIND_MEMSET:
1374	generate_memset_builtin (loop, partition);
1375	break;
1376
1377	case PKIND_MEMCPY:
1378	case PKIND_MEMMOVE:
1379	generate_memcpy_builtin (loop, partition);
1380	break;
1381
1382	default:
1383	gcc_unreachable ();
1384	}
1385
1386	/* Common tail for partitions we turn into a call. If this was the last
1387	partition for which we generate code, we have to destroy the loop. */
1388	if (!copy_p)
1389	return true;
1390	return false;
1391	}
1392
1393	data_dependence_relation *
1394	loop_distribution::get_data_dependence (struct graph *rdg, data_reference_p a,
1395	data_reference_p b)
1396	{
1397	struct data_dependence_relation ent, **slot;
1398	struct data_dependence_relation *ddr;
1399
1400	gcc_assert (DR_IS_WRITE (a) || DR_IS_WRITE (b));
1401	gcc_assert (rdg_vertex_for_stmt (rdg, DR_STMT (a))
1402	<= rdg_vertex_for_stmt (rdg, DR_STMT (b)));
1403	ent.a = a;
1404	ent.b = b;
1405	slot = ddrs_table->find_slot (value: &ent, insert: INSERT);
1406	if (*slot == NULL)
1407	{
1408	ddr = initialize_data_dependence_relation (a, b, loop_nest);
1409	compute_affine_dependence (ddr, loop_nest[0]);
1410	*slot = ddr;
1411	}
1412
1413	return *slot;
1414	}
1415
1416	bool
1417	loop_distribution::data_dep_in_cycle_p (struct graph *rdg,
1418	data_reference_p dr1,
1419	data_reference_p dr2)
1420	{
1421	struct data_dependence_relation *ddr;
1422
1423	/* Re-shuffle data-refs to be in topological order. */
1424	if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1))
1425	> rdg_vertex_for_stmt (rdg, DR_STMT (dr2)))
1426	std::swap (a&: dr1, b&: dr2);
1427
1428	ddr = get_data_dependence (rdg, a: dr1, b: dr2);
1429
1430	/* In case of no data dependence. */
1431	if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
1432	return false;
1433	/* For unknown data dependence or known data dependence which can't be
1434	expressed in classic distance vector, we check if it can be resolved
1435	by runtime alias check. If yes, we still consider data dependence
1436	as won't introduce data dependence cycle. */
1437	else if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
1438	|| DDR_NUM_DIST_VECTS (ddr) == 0)
1439	return !runtime_alias_check_p (ddr, NULL, true);
1440	else if (DDR_NUM_DIST_VECTS (ddr) > 1)
1441	return true;
1442	else if (DDR_REVERSED_P (ddr)
1443	|| lambda_vector_zerop (DDR_DIST_VECT (ddr, 0), DDR_NB_LOOPS (ddr)))
1444	return false;
1445
1446	return true;
1447	}
1448
1449	void
1450	loop_distribution::update_type_for_merge (struct graph *rdg,
1451	partition *partition1,
1452	partition *partition2)
1453	{
1454	unsigned i, j;
1455	bitmap_iterator bi, bj;
1456	data_reference_p dr1, dr2;
1457
1458	EXECUTE_IF_SET_IN_BITMAP (partition1->datarefs, 0, i, bi)
1459	{
1460	unsigned start = (partition1 == partition2) ? i + 1 : 0;
1461
1462	dr1 = datarefs_vec[i];
1463	EXECUTE_IF_SET_IN_BITMAP (partition2->datarefs, start, j, bj)
1464	{
1465	dr2 = datarefs_vec[j];
1466	if (DR_IS_READ (dr1) && DR_IS_READ (dr2))
1467	continue;
1468
1469	/* Partition can only be executed sequentially if there is any
1470	data dependence cycle. */
1471	if (data_dep_in_cycle_p (rdg, dr1, dr2))
1472	{
1473	partition1->type = PTYPE_SEQUENTIAL;
1474	return;
1475	}
1476	}
1477	}
1478	}
1479
1480	partition *
1481	loop_distribution::build_rdg_partition_for_vertex (struct graph *rdg, int v)
1482	{
1483	partition *partition = partition_alloc ();
1484	auto_vec<int, 3> nodes;
1485	unsigned i, j;
1486	int x;
1487	data_reference_p dr;
1488
1489	graphds_dfs (rdg, &v, 1, &nodes, false, NULL);
1490
1491	FOR_EACH_VEC_ELT (nodes, i, x)
1492	{
1493	bitmap_set_bit (partition->stmts, x);
1494
1495	for (j = 0; RDG_DATAREFS (rdg, x).iterate (ix: j, ptr: &dr); ++j)
1496	{
1497	unsigned idx = (unsigned) DR_INDEX (dr);
1498	gcc_assert (idx < datarefs_vec.length ());
1499
1500	/* Partition can only be executed sequentially if there is any
1501	unknown data reference. */
1502	if (!DR_BASE_ADDRESS (dr) || !DR_OFFSET (dr)
1503	|| !DR_INIT (dr) || !DR_STEP (dr))
1504	partition->type = PTYPE_SEQUENTIAL;
1505
1506	bitmap_set_bit (partition->datarefs, idx);
1507	}
1508	}
1509
1510	if (partition->type == PTYPE_SEQUENTIAL)
1511	return partition;
1512
1513	/* Further check if any data dependence prevents us from executing the
1514	partition parallelly. */
1515	update_type_for_merge (rdg, partition1: partition, partition2: partition);
1516
1517	return partition;
1518	}
1519
1520	/* Given PARTITION of LOOP and RDG, record single load/store data references
1521	for builtin partition in SRC_DR/DST_DR, return false if there is no such
1522	data references. */
1523
1524	static bool
1525	find_single_drs (class loop *loop, struct graph *rdg, const bitmap &partition_stmts,
1526	data_reference_p *dst_dr, data_reference_p *src_dr)
1527	{
1528	unsigned i;
1529	data_reference_p single_ld = NULL, single_st = NULL;
1530	bitmap_iterator bi;
1531
1532	EXECUTE_IF_SET_IN_BITMAP (partition_stmts, 0, i, bi)
1533	{
1534	gimple *stmt = RDG_STMT (rdg, i);
1535	data_reference_p dr;
1536
1537	if (gimple_code (g: stmt) == GIMPLE_PHI)
1538	continue;
1539
1540	/* Any scalar stmts are ok. */
1541	if (!gimple_vuse (g: stmt))
1542	continue;
1543
1544	/* Otherwise just regular loads/stores. */
1545	if (!gimple_assign_single_p (gs: stmt))
1546	return false;
1547
1548	/* But exactly one store and/or load. */
1549	for (unsigned j = 0; RDG_DATAREFS (rdg, i).iterate (ix: j, ptr: &dr); ++j)
1550	{
1551	tree type = TREE_TYPE (DR_REF (dr));
1552
1553	/* The memset, memcpy and memmove library calls are only
1554	able to deal with generic address space. */
1555	if (!ADDR_SPACE_GENERIC_P (TYPE_ADDR_SPACE (type)))
1556	return false;
1557
1558	if (DR_IS_READ (dr))
1559	{
1560	if (single_ld != NULL)
1561	return false;
1562	single_ld = dr;
1563	}
1564	else
1565	{
1566	if (single_st != NULL)
1567	return false;
1568	single_st = dr;
1569	}
1570	}
1571	}
1572
1573	if (!single_ld && !single_st)
1574	return false;
1575
1576	basic_block bb_ld = NULL;
1577	basic_block bb_st = NULL;
1578	edge exit = single_exit (loop);
1579
1580	if (single_ld)
1581	{
1582	/* Bail out if this is a bitfield memory reference. */
1583	if (TREE_CODE (DR_REF (single_ld)) == COMPONENT_REF
1584	&& DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_ld), 1)))
1585	return false;
1586
1587	/* Data reference must be executed exactly once per iteration of each
1588	loop in the loop nest. We only need to check dominance information
1589	against the outermost one in a perfect loop nest because a bb can't
1590	dominate outermost loop's latch without dominating inner loop's. */
1591	bb_ld = gimple_bb (DR_STMT (single_ld));
1592	if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb_ld))
1593	return false;
1594
1595	/* The data reference must also be executed before possibly exiting
1596	the loop as otherwise we'd for example unconditionally execute
1597	memset (ptr, 0, n) which even with n == 0 implies ptr is non-NULL. */
1598	if (bb_ld != loop->header
1599	&& (!exit
1600	|| !dominated_by_p (CDI_DOMINATORS, exit->src, bb_ld)))
1601	return false;
1602	}
1603
1604	if (single_st)
1605	{
1606	/* Bail out if this is a bitfield memory reference. */
1607	if (TREE_CODE (DR_REF (single_st)) == COMPONENT_REF
1608	&& DECL_BIT_FIELD (TREE_OPERAND (DR_REF (single_st), 1)))
1609	return false;
1610
1611	/* Data reference must be executed exactly once per iteration.
1612	Same as single_ld, we only need to check against the outermost
1613	loop. */
1614	bb_st = gimple_bb (DR_STMT (single_st));
1615	if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb_st))
1616	return false;
1617
1618	/* And before exiting the loop. */
1619	if (bb_st != loop->header
1620	&& (!exit
1621	|| !dominated_by_p (CDI_DOMINATORS, exit->src, bb_st)))
1622	return false;
1623	}
1624
1625	if (single_ld && single_st)
1626	{
1627	/* Load and store must be in the same loop nest. */
1628	if (bb_st->loop_father != bb_ld->loop_father)
1629	return false;
1630
1631	edge e = single_exit (bb_st->loop_father);
1632	bool dom_ld = dominated_by_p (CDI_DOMINATORS, e->src, bb_ld);
1633	bool dom_st = dominated_by_p (CDI_DOMINATORS, e->src, bb_st);
1634	if (dom_ld != dom_st)
1635	return false;
1636	}
1637
1638	*src_dr = single_ld;
1639	*dst_dr = single_st;
1640	return true;
1641	}
1642
1643	/* Given data reference DR in LOOP_NEST, this function checks the enclosing
1644	loops from inner to outer to see if loop's step equals to access size at
1645	each level of loop. Return 2 if we can prove this at all level loops;
1646	record access base and size in BASE and SIZE; save loop's step at each
1647	level of loop in STEPS if it is not null. For example:
1648
1649	int arr[100][100][100];
1650	for (i = 0; i < 100; i++) ;steps[2] = 40000
1651	for (j = 100; j > 0; j--) ;steps[1] = -400
1652	for (k = 0; k < 100; k++) ;steps[0] = 4
1653	arr[i][j - 1][k] = 0; ;base = &arr, size = 4000000
1654
1655	Return 1 if we can prove the equality at the innermost loop, but not all
1656	level loops. In this case, no information is recorded.
1657
1658	Return 0 if no equality can be proven at any level loops. */
1659
1660	static int
1661	compute_access_range (loop_p loop_nest, data_reference_p dr, tree *base,
1662	tree *size, vec<tree> *steps = NULL)
1663	{
1664	location_t loc = gimple_location (DR_STMT (dr));
1665	basic_block bb = gimple_bb (DR_STMT (dr));
1666	class loop *loop = bb->loop_father;
1667	tree ref = DR_REF (dr);
1668	tree access_base = build_fold_addr_expr (ref);
1669	tree access_size = TYPE_SIZE_UNIT (TREE_TYPE (ref));
1670	int res = 0;
1671
1672	do {
1673	tree scev_fn = analyze_scalar_evolution (loop, access_base);
1674	if (TREE_CODE (scev_fn) != POLYNOMIAL_CHREC)
1675	return res;
1676
1677	access_base = CHREC_LEFT (scev_fn);
1678	if (tree_contains_chrecs (access_base, NULL))
1679	return res;
1680
1681	tree scev_step = CHREC_RIGHT (scev_fn);
1682	/* Only support constant steps. */
1683	if (TREE_CODE (scev_step) != INTEGER_CST)
1684	return res;
1685
1686	enum ev_direction access_dir = scev_direction (scev_fn);
1687	if (access_dir == EV_DIR_UNKNOWN)
1688	return res;
1689
1690	if (steps != NULL)
1691	steps->safe_push (obj: scev_step);
1692
1693	scev_step = fold_convert_loc (loc, sizetype, scev_step);
1694	/* Compute absolute value of scev step. */
1695	if (access_dir == EV_DIR_DECREASES)
1696	scev_step = fold_build1_loc (loc, NEGATE_EXPR, sizetype, scev_step);
1697
1698	/* At each level of loop, scev step must equal to access size. In other
1699	words, DR must access consecutive memory between loop iterations. */
1700	if (!operand_equal_p (scev_step, access_size, flags: 0))
1701	return res;
1702
1703	/* Access stride can be computed for data reference at least for the
1704	innermost loop. */
1705	res = 1;
1706
1707	/* Compute DR's execution times in loop. */
1708	tree niters = number_of_latch_executions (loop);
1709	niters = fold_convert_loc (loc, sizetype, niters);
1710	if (dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src, bb))
1711	niters = size_binop_loc (loc, PLUS_EXPR, niters, size_one_node);
1712
1713	/* Compute DR's overall access size in loop. */
1714	access_size = fold_build2_loc (loc, MULT_EXPR, sizetype,
1715	niters, scev_step);
1716	/* Adjust base address in case of negative step. */
1717	if (access_dir == EV_DIR_DECREASES)
1718	{
1719	tree adj = fold_build2_loc (loc, MINUS_EXPR, sizetype,
1720	scev_step, access_size);
1721	access_base = fold_build_pointer_plus_loc (loc, ptr: access_base, off: adj);
1722	}
1723	} while (loop != loop_nest && (loop = loop_outer (loop)) != NULL);
1724
1725	*base = access_base;
1726	*size = access_size;
1727	/* Access stride can be computed for data reference at each level loop. */
1728	return 2;
1729	}
1730
1731	/* Allocate and return builtin struct. Record information like DST_DR,
1732	SRC_DR, DST_BASE, SRC_BASE and SIZE in the allocated struct. */
1733
1734	static struct builtin_info *
1735	alloc_builtin (data_reference_p dst_dr, data_reference_p src_dr,
1736	tree dst_base, tree src_base, tree size)
1737	{
1738	struct builtin_info *builtin = XNEW (struct builtin_info);
1739	builtin->dst_dr = dst_dr;
1740	builtin->src_dr = src_dr;
1741	builtin->dst_base = dst_base;
1742	builtin->src_base = src_base;
1743	builtin->size = size;
1744	return builtin;
1745	}
1746
1747	/* Given data reference DR in loop nest LOOP, classify if it forms builtin
1748	memset call. */
1749
1750	static void
1751	classify_builtin_st (loop_p loop, partition *partition, data_reference_p dr)
1752	{
1753	gimple *stmt = DR_STMT (dr);
1754	tree base, size, rhs = gimple_assign_rhs1 (gs: stmt);
1755
1756	if (const_with_all_bytes_same (val: rhs) == -1
1757	&& (!INTEGRAL_TYPE_P (TREE_TYPE (rhs))
1758	|| (TYPE_MODE (TREE_TYPE (rhs))
1759	!= TYPE_MODE (unsigned_char_type_node))))
1760	return;
1761
1762	if (TREE_CODE (rhs) == SSA_NAME
1763	&& !SSA_NAME_IS_DEFAULT_DEF (rhs)
1764	&& flow_bb_inside_loop_p (loop, gimple_bb (SSA_NAME_DEF_STMT (rhs))))
1765	return;
1766
1767	int res = compute_access_range (loop_nest: loop, dr, base: &base, size: &size);
1768	if (res == 0)
1769	return;
1770	if (res == 1)
1771	{
1772	partition->kind = PKIND_PARTIAL_MEMSET;
1773	return;
1774	}
1775
1776	tree base_offset;
1777	tree base_base;
1778	split_constant_offset (base, &base_base, &base_offset);
1779	if (!cst_and_fits_in_hwi (base_offset))
1780	return;
1781	unsigned HOST_WIDE_INT const_base_offset = int_cst_value (base_offset);
1782
1783	struct builtin_info *builtin;
1784	builtin = alloc_builtin (dst_dr: dr, NULL, dst_base: base, NULL_TREE, size);
1785	builtin->dst_base_base = base_base;
1786	builtin->dst_base_offset = const_base_offset;
1787	partition->builtin = builtin;
1788	partition->kind = PKIND_MEMSET;
1789	}
1790
1791	/* Given data references DST_DR and SRC_DR in loop nest LOOP and RDG, classify
1792	if it forms builtin memcpy or memmove call. */
1793
1794	void
1795	loop_distribution::classify_builtin_ldst (loop_p loop, struct graph *rdg,
1796	partition *partition,
1797	data_reference_p dst_dr,
1798	data_reference_p src_dr)
1799	{
1800	tree base, size, src_base, src_size;
1801	auto_vec<tree> dst_steps, src_steps;
1802
1803	/* Compute access range of both load and store. */
1804	int res = compute_access_range (loop_nest: loop, dr: dst_dr, base: &base, size: &size, steps: &dst_steps);
1805	if (res != 2)
1806	return;
1807	res = compute_access_range (loop_nest: loop, dr: src_dr, base: &src_base, size: &src_size, steps: &src_steps);
1808	if (res != 2)
1809	return;
1810
1811	/* They must have the same access size. */
1812	if (!operand_equal_p (size, src_size, flags: 0))
1813	return;
1814
1815	/* They must have the same storage order. */
1816	if (reverse_storage_order_for_component_p (DR_REF (dst_dr))
1817	!= reverse_storage_order_for_component_p (DR_REF (src_dr)))
1818	return;
1819
1820	/* Load and store in loop nest must access memory in the same way, i.e,
1821	their must have the same steps in each loop of the nest. */
1822	if (dst_steps.length () != src_steps.length ())
1823	return;
1824	for (unsigned i = 0; i < dst_steps.length (); ++i)
1825	if (!operand_equal_p (dst_steps[i], src_steps[i], flags: 0))
1826	return;
1827
1828	/* Now check that if there is a dependence. */
1829	ddr_p ddr = get_data_dependence (rdg, a: src_dr, b: dst_dr);
1830
1831	/* Classify as memmove if no dependence between load and store. */
1832	if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
1833	{
1834	partition->builtin = alloc_builtin (dst_dr, src_dr, dst_base: base, src_base, size);
1835	partition->kind = PKIND_MEMMOVE;
1836	return;
1837	}
1838
1839	/* Can't do memmove in case of unknown dependence or dependence without
1840	classical distance vector. */
1841	if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know
1842	|| DDR_NUM_DIST_VECTS (ddr) == 0)
1843	return;
1844
1845	unsigned i;
1846	lambda_vector dist_v;
1847	int num_lev = (DDR_LOOP_NEST (ddr)).length ();
1848	FOR_EACH_VEC_ELT (DDR_DIST_VECTS (ddr), i, dist_v)
1849	{
1850	unsigned dep_lev = dependence_level (dist_vect: dist_v, length: num_lev);
1851	/* Can't do memmove if load depends on store. */
1852	if (dep_lev > 0 && dist_v[dep_lev - 1] > 0 && !DDR_REVERSED_P (ddr))
1853	return;
1854	}
1855
1856	partition->builtin = alloc_builtin (dst_dr, src_dr, dst_base: base, src_base, size);
1857	partition->kind = PKIND_MEMMOVE;
1858	return;
1859	}
1860
1861	bool
1862	loop_distribution::classify_partition (loop_p loop,
1863	struct graph *rdg, partition *partition,
1864	bitmap stmt_in_all_partitions)
1865	{
1866	bitmap_iterator bi;
1867	unsigned i;
1868	data_reference_p single_ld = NULL, single_st = NULL;
1869	bool volatiles_p = false, has_reduction = false;
1870
1871	EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, bi)
1872	{
1873	gimple *stmt = RDG_STMT (rdg, i);
1874
1875	if (gimple_has_volatile_ops (stmt))
1876	volatiles_p = true;
1877
1878	/* If the stmt is not included by all partitions and there is uses
1879	outside of the loop, then mark the partition as reduction. */
1880	if (stmt_has_scalar_dependences_outside_loop (loop, stmt))
1881	{
1882	/* Due to limitation in the transform phase we have to fuse all
1883	reduction partitions. As a result, this could cancel valid
1884	loop distribution especially for loop that induction variable
1885	is used outside of loop. To workaround this issue, we skip
1886	marking partition as reudction if the reduction stmt belongs
1887	to all partitions. In such case, reduction will be computed
1888	correctly no matter how partitions are fused/distributed. */
1889	if (!bitmap_bit_p (stmt_in_all_partitions, i))
1890	partition->reduction_p = true;
1891	else
1892	has_reduction = true;
1893	}
1894	}
1895
1896	/* Simple workaround to prevent classifying the partition as builtin
1897	if it contains any use outside of loop. For the case where all
1898	partitions have the reduction this simple workaround is delayed
1899	to only affect the last partition. */
1900	if (partition->reduction_p)
1901	return has_reduction;
1902
1903	/* Perform general partition disqualification for builtins. */
1904	if (volatiles_p
1905	|| !flag_tree_loop_distribute_patterns)
1906	return has_reduction;
1907
1908	/* Find single load/store data references for builtin partition. */
1909	if (!find_single_drs (loop, rdg, partition_stmts: partition->stmts, dst_dr: &single_st, src_dr: &single_ld)
1910	|| !single_st)
1911	return has_reduction;
1912
1913	if (single_ld && single_st)
1914	{
1915	gimple *store = DR_STMT (single_st), *load = DR_STMT (single_ld);
1916	/* Direct aggregate copy or via an SSA name temporary. */
1917	if (load != store
1918	&& gimple_assign_lhs (gs: load) != gimple_assign_rhs1 (gs: store))
1919	return has_reduction;
1920	}
1921
1922	partition->loc = gimple_location (DR_STMT (single_st));
1923
1924	/* Classify the builtin kind. */
1925	if (single_ld == NULL)
1926	classify_builtin_st (loop, partition, dr: single_st);
1927	else
1928	classify_builtin_ldst (loop, rdg, partition, dst_dr: single_st, src_dr: single_ld);
1929	return has_reduction;
1930	}
1931
1932	bool
1933	loop_distribution::share_memory_accesses (struct graph *rdg,
1934	partition *partition1, partition *partition2)
1935	{
1936	unsigned i, j;
1937	bitmap_iterator bi, bj;
1938	data_reference_p dr1, dr2;
1939
1940	/* First check whether in the intersection of the two partitions are
1941	any loads or stores. Common loads are the situation that happens
1942	most often. */
1943	EXECUTE_IF_AND_IN_BITMAP (partition1->stmts, partition2->stmts, 0, i, bi)
1944	if (RDG_MEM_WRITE_STMT (rdg, i)
1945	|| RDG_MEM_READS_STMT (rdg, i))
1946	return true;
1947
1948	/* Then check whether the two partitions access the same memory object. */
1949	EXECUTE_IF_SET_IN_BITMAP (partition1->datarefs, 0, i, bi)
1950	{
1951	dr1 = datarefs_vec[i];
1952
1953	if (!DR_BASE_ADDRESS (dr1)
1954	|| !DR_OFFSET (dr1) || !DR_INIT (dr1) || !DR_STEP (dr1))
1955	continue;
1956
1957	EXECUTE_IF_SET_IN_BITMAP (partition2->datarefs, 0, j, bj)
1958	{
1959	dr2 = datarefs_vec[j];
1960
1961	if (!DR_BASE_ADDRESS (dr2)
1962	|| !DR_OFFSET (dr2) || !DR_INIT (dr2) || !DR_STEP (dr2))
1963	continue;
1964
1965	if (operand_equal_p (DR_BASE_ADDRESS (dr1), DR_BASE_ADDRESS (dr2), flags: 0)
1966	&& operand_equal_p (DR_OFFSET (dr1), DR_OFFSET (dr2), flags: 0)
1967	&& operand_equal_p (DR_INIT (dr1), DR_INIT (dr2), flags: 0)
1968	&& operand_equal_p (DR_STEP (dr1), DR_STEP (dr2), flags: 0))
1969	return true;
1970	}
1971	}
1972
1973	return false;
1974	}
1975
1976	/* For each seed statement in STARTING_STMTS, this function builds
1977	partition for it by adding depended statements according to RDG.
1978	All partitions are recorded in PARTITIONS. */
1979
1980	void
1981	loop_distribution::rdg_build_partitions (struct graph *rdg,
1982	vec<gimple *> starting_stmts,
1983	vec<partition *> *partitions)
1984	{
1985	auto_bitmap processed;
1986	int i;
1987	gimple *stmt;
1988
1989	FOR_EACH_VEC_ELT (starting_stmts, i, stmt)
1990	{
1991	int v = rdg_vertex_for_stmt (rdg, stmt);
1992
1993	if (dump_file && (dump_flags & TDF_DETAILS))
1994	fprintf (stream: dump_file,
1995	format: "ldist asked to generate code for vertex %d\n", v);
1996
1997	/* If the vertex is already contained in another partition so
1998	is the partition rooted at it. */
1999	if (bitmap_bit_p (processed, v))
2000	continue;
2001
2002	partition *partition = build_rdg_partition_for_vertex (rdg, v);
2003	bitmap_ior_into (processed, partition->stmts);
2004
2005	if (dump_file && (dump_flags & TDF_DETAILS))
2006	{
2007	fprintf (stream: dump_file, format: "ldist creates useful %s partition:\n",
2008	partition->type == PTYPE_PARALLEL ? "parallel" : "sequent");
2009	bitmap_print (dump_file, partition->stmts, " ", "\n");
2010	}
2011
2012	partitions->safe_push (obj: partition);
2013	}
2014
2015	/* All vertices should have been assigned to at least one partition now,
2016	other than vertices belonging to dead code. */
2017	}
2018
2019	/* Dump to FILE the PARTITIONS. */
2020
2021	static void
2022	dump_rdg_partitions (FILE *file, const vec<partition *> &partitions)
2023	{
2024	int i;
2025	partition *partition;
2026
2027	FOR_EACH_VEC_ELT (partitions, i, partition)
2028	debug_bitmap_file (file, partition->stmts);
2029	}
2030
2031	/* Debug PARTITIONS. */
2032	extern void debug_rdg_partitions (const vec<partition *> &);
2033
2034	DEBUG_FUNCTION void
2035	debug_rdg_partitions (const vec<partition *> &partitions)
2036	{
2037	dump_rdg_partitions (stderr, partitions);
2038	}
2039
2040	/* Returns the number of read and write operations in the RDG. */
2041
2042	static int
2043	number_of_rw_in_rdg (struct graph *rdg)
2044	{
2045	int i, res = 0;
2046
2047	for (i = 0; i < rdg->n_vertices; i++)
2048	{
2049	if (RDG_MEM_WRITE_STMT (rdg, i))
2050	++res;
2051
2052	if (RDG_MEM_READS_STMT (rdg, i))
2053	++res;
2054	}
2055
2056	return res;
2057	}
2058
2059	/* Returns the number of read and write operations in a PARTITION of
2060	the RDG. */
2061
2062	static int
2063	number_of_rw_in_partition (struct graph *rdg, partition *partition)
2064	{
2065	int res = 0;
2066	unsigned i;
2067	bitmap_iterator ii;
2068
2069	EXECUTE_IF_SET_IN_BITMAP (partition->stmts, 0, i, ii)
2070	{
2071	if (RDG_MEM_WRITE_STMT (rdg, i))
2072	++res;
2073
2074	if (RDG_MEM_READS_STMT (rdg, i))
2075	++res;
2076	}
2077
2078	return res;
2079	}
2080
2081	/* Returns true when one of the PARTITIONS contains all the read or
2082	write operations of RDG. */
2083
2084	static bool
2085	partition_contains_all_rw (struct graph *rdg,
2086	const vec<partition *> &partitions)
2087	{
2088	int i;
2089	partition *partition;
2090	int nrw = number_of_rw_in_rdg (rdg);
2091
2092	FOR_EACH_VEC_ELT (partitions, i, partition)
2093	if (nrw == number_of_rw_in_partition (rdg, partition))
2094	return true;
2095
2096	return false;
2097	}
2098
2099	int
2100	loop_distribution::pg_add_dependence_edges (struct graph *rdg, int dir,
2101	bitmap drs1, bitmap drs2, vec<ddr_p> *alias_ddrs)
2102	{
2103	unsigned i, j;
2104	bitmap_iterator bi, bj;
2105	data_reference_p dr1, dr2, saved_dr1;
2106
2107	/* dependence direction - 0 is no dependence, -1 is back,
2108	1 is forth, 2 is both (we can stop then, merging will occur). */
2109	EXECUTE_IF_SET_IN_BITMAP (drs1, 0, i, bi)
2110	{
2111	dr1 = datarefs_vec[i];
2112
2113	EXECUTE_IF_SET_IN_BITMAP (drs2, 0, j, bj)
2114	{
2115	int res, this_dir = 1;
2116	ddr_p ddr;
2117
2118	dr2 = datarefs_vec[j];
2119
2120	/* Skip all <read, read> data dependence. */
2121	if (DR_IS_READ (dr1) && DR_IS_READ (dr2))
2122	continue;
2123
2124	saved_dr1 = dr1;
2125	/* Re-shuffle data-refs to be in topological order. */
2126	if (rdg_vertex_for_stmt (rdg, DR_STMT (dr1))
2127	> rdg_vertex_for_stmt (rdg, DR_STMT (dr2)))
2128	{
2129	std::swap (a&: dr1, b&: dr2);
2130	this_dir = -this_dir;
2131	}
2132	ddr = get_data_dependence (rdg, a: dr1, b: dr2);
2133	if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
2134	{
2135	this_dir = 0;
2136	res = data_ref_compare_tree (DR_BASE_ADDRESS (dr1),
2137	DR_BASE_ADDRESS (dr2));
2138	/* Be conservative. If data references are not well analyzed,
2139	or the two data references have the same base address and
2140	offset, add dependence and consider it alias to each other.
2141	In other words, the dependence cannot be resolved by
2142	runtime alias check. */
2143	if (!DR_BASE_ADDRESS (dr1) || !DR_BASE_ADDRESS (dr2)
2144	|| !DR_OFFSET (dr1) || !DR_OFFSET (dr2)
2145	|| !DR_INIT (dr1) || !DR_INIT (dr2)
2146	|| !DR_STEP (dr1) || !tree_fits_uhwi_p (DR_STEP (dr1))
2147	|| !DR_STEP (dr2) || !tree_fits_uhwi_p (DR_STEP (dr2))
2148	|| res == 0)
2149	this_dir = 2;
2150	/* Data dependence could be resolved by runtime alias check,
2151	record it in ALIAS_DDRS. */
2152	else if (alias_ddrs != NULL)
2153	alias_ddrs->safe_push (obj: ddr);
2154	/* Or simply ignore it. */
2155	}
2156	else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
2157	{
2158	/* Known dependences can still be unordered througout the
2159	iteration space, see gcc.dg/tree-ssa/ldist-16.c and
2160	gcc.dg/tree-ssa/pr94969.c. */
2161	if (DDR_NUM_DIST_VECTS (ddr) != 1)
2162	this_dir = 2;
2163	/* If the overlap is exact preserve stmt order. */
2164	else if (lambda_vector_zerop (DDR_DIST_VECT (ddr, 0),
2165	DDR_NB_LOOPS (ddr)))
2166	;
2167	/* Else as the distance vector is lexicographic positive swap
2168	the dependence direction. */
2169	else
2170	{
2171	if (DDR_REVERSED_P (ddr))
2172	this_dir = -this_dir;
2173	this_dir = -this_dir;
2174
2175	/* When then dependence distance of the innermost common
2176	loop of the DRs is zero we have a conflict. */
2177	auto l1 = gimple_bb (DR_STMT (dr1))->loop_father;
2178	auto l2 = gimple_bb (DR_STMT (dr2))->loop_father;
2179	int idx = index_in_loop_nest (var: find_common_loop (l1, l2)->num,
2180	DDR_LOOP_NEST (ddr));
2181	if (DDR_DIST_VECT (ddr, 0)[idx] == 0)
2182	this_dir = 2;
2183	}
2184	}
2185	else
2186	this_dir = 0;
2187	if (this_dir == 2)
2188	return 2;
2189	else if (dir == 0)
2190	dir = this_dir;
2191	else if (this_dir != 0 && dir != this_dir)
2192	return 2;
2193	/* Shuffle "back" dr1. */
2194	dr1 = saved_dr1;
2195	}
2196	}
2197	return dir;
2198	}
2199
2200	/* Compare postorder number of the partition graph vertices V1 and V2. */
2201
2202	static int
2203	pgcmp (const void *v1_, const void *v2_)
2204	{
2205	const vertex *v1 = (const vertex *)v1_;
2206	const vertex *v2 = (const vertex *)v2_;
2207	return v2->post - v1->post;
2208	}
2209
2210	/* Data attached to vertices of partition dependence graph. */
2211	struct pg_vdata
2212	{
2213	/* ID of the corresponding partition. */
2214	int id;
2215	/* The partition. */
2216	struct partition *partition;
2217	};
2218
2219	/* Data attached to edges of partition dependence graph. */
2220	struct pg_edata
2221	{
2222	/* If the dependence edge can be resolved by runtime alias check,
2223	this vector contains data dependence relations for runtime alias
2224	check. On the other hand, if the dependence edge is introduced
2225	because of compilation time known data dependence, this vector
2226	contains nothing. */
2227	vec<ddr_p> alias_ddrs;
2228	};
2229
2230	/* Callback data for traversing edges in graph. */
2231	struct pg_edge_callback_data
2232	{
2233	/* Bitmap contains strong connected components should be merged. */
2234	bitmap sccs_to_merge;
2235	/* Array constains component information for all vertices. */
2236	int *vertices_component;
2237	/* Vector to record all data dependence relations which are needed
2238	to break strong connected components by runtime alias checks. */
2239	vec<ddr_p> *alias_ddrs;
2240	};
2241
2242	/* Initialize vertice's data for partition dependence graph PG with
2243	PARTITIONS. */
2244
2245	static void
2246	init_partition_graph_vertices (struct graph *pg,
2247	vec<struct partition *> *partitions)
2248	{
2249	int i;
2250	partition *partition;
2251	struct pg_vdata *data;
2252
2253	for (i = 0; partitions->iterate (ix: i, ptr: &partition); ++i)
2254	{
2255	data = new pg_vdata;
2256	pg->vertices[i].data = data;
2257	data->id = i;
2258	data->partition = partition;
2259	}
2260	}
2261
2262	/* Add edge <I, J> to partition dependence graph PG. Attach vector of data
2263	dependence relations to the EDGE if DDRS isn't NULL. */
2264
2265	static void
2266	add_partition_graph_edge (struct graph *pg, int i, int j, vec<ddr_p> *ddrs)
2267	{
2268	struct graph_edge *e = add_edge (pg, i, j);
2269
2270	/* If the edge is attached with data dependence relations, it means this
2271	dependence edge can be resolved by runtime alias checks. */
2272	if (ddrs != NULL)
2273	{
2274	struct pg_edata *data = new pg_edata;
2275
2276	gcc_assert (ddrs->length () > 0);
2277	e->data = data;
2278	data->alias_ddrs = vNULL;
2279	data->alias_ddrs.safe_splice (src: *ddrs);
2280	}
2281	}
2282
2283	/* Callback function for graph travesal algorithm. It returns true
2284	if edge E should skipped when traversing the graph. */
2285
2286	static bool
2287	pg_skip_alias_edge (struct graph_edge *e)
2288	{
2289	struct pg_edata *data = (struct pg_edata *)e->data;
2290	return (data != NULL && data->alias_ddrs.length () > 0);
2291	}
2292
2293	/* Callback function freeing data attached to edge E of graph. */
2294
2295	static void
2296	free_partition_graph_edata_cb (struct graph *, struct graph_edge *e, void *)
2297	{
2298	if (e->data != NULL)
2299	{
2300	struct pg_edata *data = (struct pg_edata *)e->data;
2301	data->alias_ddrs.release ();
2302	delete data;
2303	}
2304	}
2305
2306	/* Free data attached to vertice of partition dependence graph PG. */
2307
2308	static void
2309	free_partition_graph_vdata (struct graph *pg)
2310	{
2311	int i;
2312	struct pg_vdata *data;
2313
2314	for (i = 0; i < pg->n_vertices; ++i)
2315	{
2316	data = (struct pg_vdata *)pg->vertices[i].data;
2317	delete data;
2318	}
2319	}
2320
2321	/* Build and return partition dependence graph for PARTITIONS. RDG is
2322	reduced dependence graph for the loop to be distributed. If IGNORE_ALIAS_P
2323	is true, data dependence caused by possible alias between references
2324	is ignored, as if it doesn't exist at all; otherwise all depdendences
2325	are considered. */
2326
2327	struct graph *
2328	loop_distribution::build_partition_graph (struct graph *rdg,
2329	vec<struct partition *> *partitions,
2330	bool ignore_alias_p)
2331	{
2332	int i, j;
2333	struct partition *partition1, *partition2;
2334	graph *pg = new_graph (partitions->length ());
2335	auto_vec<ddr_p> alias_ddrs, *alias_ddrs_p;
2336
2337	alias_ddrs_p = ignore_alias_p ? NULL : &alias_ddrs;
2338
2339	init_partition_graph_vertices (pg, partitions);
2340
2341	for (i = 0; partitions->iterate (ix: i, ptr: &partition1); ++i)
2342	{
2343	for (j = i + 1; partitions->iterate (ix: j, ptr: &partition2); ++j)
2344	{
2345	/* dependence direction - 0 is no dependence, -1 is back,
2346	1 is forth, 2 is both (we can stop then, merging will occur). */
2347	int dir = 0;
2348
2349	/* If the first partition has reduction, add back edge; if the
2350	second partition has reduction, add forth edge. This makes
2351	sure that reduction partition will be sorted as the last one. */
2352	if (partition_reduction_p (partition: partition1))
2353	dir = -1;
2354	else if (partition_reduction_p (partition: partition2))
2355	dir = 1;
2356
2357	/* Cleanup the temporary vector. */
2358	alias_ddrs.truncate (size: 0);
2359
2360	dir = pg_add_dependence_edges (rdg, dir, drs1: partition1->datarefs,
2361	drs2: partition2->datarefs, alias_ddrs: alias_ddrs_p);
2362
2363	/* Add edge to partition graph if there exists dependence. There
2364	are two types of edges. One type edge is caused by compilation
2365	time known dependence, this type cannot be resolved by runtime
2366	alias check. The other type can be resolved by runtime alias
2367	check. */
2368	if (dir == 1 || dir == 2
2369	|| alias_ddrs.length () > 0)
2370	{
2371	/* Attach data dependence relations to edge that can be resolved
2372	by runtime alias check. */
2373	bool alias_edge_p = (dir != 1 && dir != 2);
2374	add_partition_graph_edge (pg, i, j,
2375	ddrs: (alias_edge_p) ? &alias_ddrs : NULL);
2376	}
2377	if (dir == -1 || dir == 2
2378	|| alias_ddrs.length () > 0)
2379	{
2380	/* Attach data dependence relations to edge that can be resolved
2381	by runtime alias check. */
2382	bool alias_edge_p = (dir != -1 && dir != 2);
2383	add_partition_graph_edge (pg, i: j, j: i,
2384	ddrs: (alias_edge_p) ? &alias_ddrs : NULL);
2385	}
2386	}
2387	}
2388	return pg;
2389	}
2390
2391	/* Sort partitions in PG in descending post order and store them in
2392	PARTITIONS. */
2393
2394	static void
2395	sort_partitions_by_post_order (struct graph *pg,
2396	vec<struct partition *> *partitions)
2397	{
2398	int i;
2399	struct pg_vdata *data;
2400
2401	/* Now order the remaining nodes in descending postorder. */
2402	qsort (pg->vertices, pg->n_vertices, sizeof (vertex), pgcmp);
2403	partitions->truncate (size: 0);
2404	for (i = 0; i < pg->n_vertices; ++i)
2405	{
2406	data = (struct pg_vdata *)pg->vertices[i].data;
2407	if (data->partition)
2408	partitions->safe_push (obj: data->partition);
2409	}
2410	}
2411
2412	void
2413	loop_distribution::merge_dep_scc_partitions (struct graph *rdg,
2414	vec<struct partition *> *partitions,
2415	bool ignore_alias_p)
2416	{
2417	struct partition *partition1, *partition2;
2418	struct pg_vdata *data;
2419	graph *pg = build_partition_graph (rdg, partitions, ignore_alias_p);
2420	int i, j, num_sccs = graphds_scc (pg, NULL);
2421
2422	/* Strong connected compoenent means dependence cycle, we cannot distribute
2423	them. So fuse them together. */
2424	if ((unsigned) num_sccs < partitions->length ())
2425	{
2426	for (i = 0; i < num_sccs; ++i)
2427	{
2428	for (j = 0; partitions->iterate (ix: j, ptr: &partition1); ++j)
2429	if (pg->vertices[j].component == i)
2430	break;
2431	for (j = j + 1; partitions->iterate (ix: j, ptr: &partition2); ++j)
2432	if (pg->vertices[j].component == i)
2433	{
2434	partition_merge_into (NULL, dest: partition1,
2435	partition: partition2, ft: FUSE_SAME_SCC);
2436	partition1->type = PTYPE_SEQUENTIAL;
2437	(*partitions)[j] = NULL;
2438	partition_free (partition: partition2);
2439	data = (struct pg_vdata *)pg->vertices[j].data;
2440	data->partition = NULL;
2441	}
2442	}
2443	}
2444
2445	sort_partitions_by_post_order (pg, partitions);
2446	gcc_assert (partitions->length () == (unsigned)num_sccs);
2447	free_partition_graph_vdata (pg);
2448	for_each_edge (pg, free_partition_graph_edata_cb, NULL);
2449	free_graph (g: pg);
2450	}
2451
2452	/* Callback function for traversing edge E in graph G. DATA is private
2453	callback data. */
2454
2455	static void
2456	pg_collect_alias_ddrs (struct graph *g, struct graph_edge *e, void *data)
2457	{
2458	int i, j, component;
2459	struct pg_edge_callback_data *cbdata;
2460	struct pg_edata *edata = (struct pg_edata *) e->data;
2461
2462	/* If the edge doesn't have attached data dependence, it represents
2463	compilation time known dependences. This type dependence cannot
2464	be resolved by runtime alias check. */
2465	if (edata == NULL || edata->alias_ddrs.length () == 0)
2466	return;
2467
2468	cbdata = (struct pg_edge_callback_data *) data;
2469	i = e->src;
2470	j = e->dest;
2471	component = cbdata->vertices_component[i];
2472	/* Vertices are topologically sorted according to compilation time
2473	known dependences, so we can break strong connected components
2474	by removing edges of the opposite direction, i.e, edges pointing
2475	from vertice with smaller post number to vertice with bigger post
2476	number. */
2477	if (g->vertices[i].post < g->vertices[j].post
2478	/* We only need to remove edges connecting vertices in the same
2479	strong connected component to break it. */
2480	&& component == cbdata->vertices_component[j]
2481	/* Check if we want to break the strong connected component or not. */
2482	&& !bitmap_bit_p (cbdata->sccs_to_merge, component))
2483	cbdata->alias_ddrs->safe_splice (src: edata->alias_ddrs);
2484	}
2485
2486	/* Callback function for traversing edge E. DATA is private
2487	callback data. */
2488
2489	static void
2490	pg_unmark_merged_alias_ddrs (struct graph *, struct graph_edge *e, void *data)
2491	{
2492	int i, j, component;
2493	struct pg_edge_callback_data *cbdata;
2494	struct pg_edata *edata = (struct pg_edata *) e->data;
2495
2496	if (edata == NULL || edata->alias_ddrs.length () == 0)
2497	return;
2498
2499	cbdata = (struct pg_edge_callback_data *) data;
2500	i = e->src;
2501	j = e->dest;
2502	component = cbdata->vertices_component[i];
2503	/* Make sure to not skip vertices inside SCCs we are going to merge. */
2504	if (component == cbdata->vertices_component[j]
2505	&& bitmap_bit_p (cbdata->sccs_to_merge, component))
2506	{
2507	edata->alias_ddrs.release ();
2508	delete edata;
2509	e->data = NULL;
2510	}
2511	}
2512
2513	/* This is the main function breaking strong conected components in
2514	PARTITIONS giving reduced depdendence graph RDG. Store data dependence
2515	relations for runtime alias check in ALIAS_DDRS. */
2516	void
2517	loop_distribution::break_alias_scc_partitions (struct graph *rdg,
2518	vec<struct partition *> *partitions,
2519	vec<ddr_p> *alias_ddrs)
2520	{
2521	int i, j, k, num_sccs, num_sccs_no_alias = 0;
2522	/* Build partition dependence graph. */
2523	graph *pg = build_partition_graph (rdg, partitions, ignore_alias_p: false);
2524
2525	alias_ddrs->truncate (size: 0);
2526	/* Find strong connected components in the graph, with all dependence edges
2527	considered. */
2528	num_sccs = graphds_scc (pg, NULL);
2529	/* All SCCs now can be broken by runtime alias checks because SCCs caused by
2530	compilation time known dependences are merged before this function. */
2531	if ((unsigned) num_sccs < partitions->length ())
2532	{
2533	struct pg_edge_callback_data cbdata;
2534	auto_bitmap sccs_to_merge;
2535	auto_vec<enum partition_type> scc_types;
2536	struct partition *partition, *first;
2537
2538	/* If all partitions in a SCC have the same type, we can simply merge the
2539	SCC. This loop finds out such SCCS and record them in bitmap. */
2540	bitmap_set_range (sccs_to_merge, 0, (unsigned) num_sccs);
2541	for (i = 0; i < num_sccs; ++i)
2542	{
2543	for (j = 0; partitions->iterate (ix: j, ptr: &first); ++j)
2544	if (pg->vertices[j].component == i)
2545	break;
2546
2547	bool same_type = true, all_builtins = partition_builtin_p (partition: first);
2548	for (++j; partitions->iterate (ix: j, ptr: &partition); ++j)
2549	{
2550	if (pg->vertices[j].component != i)
2551	continue;
2552
2553	if (first->type != partition->type)
2554	{
2555	same_type = false;
2556	break;
2557	}
2558	all_builtins &= partition_builtin_p (partition);
2559	}
2560	/* Merge SCC if all partitions in SCC have the same type, though the
2561	result partition is sequential, because vectorizer can do better
2562	runtime alias check. One expecption is all partitions in SCC are
2563	builtins. */
2564	if (!same_type || all_builtins)
2565	bitmap_clear_bit (sccs_to_merge, i);
2566	}
2567
2568	/* Initialize callback data for traversing. */
2569	cbdata.sccs_to_merge = sccs_to_merge;
2570	cbdata.alias_ddrs = alias_ddrs;
2571	cbdata.vertices_component = XNEWVEC (int, pg->n_vertices);
2572	/* Record the component information which will be corrupted by next
2573	graph scc finding call. */
2574	for (i = 0; i < pg->n_vertices; ++i)
2575	cbdata.vertices_component[i] = pg->vertices[i].component;
2576
2577	/* Collect data dependences for runtime alias checks to break SCCs. */
2578	if (bitmap_count_bits (sccs_to_merge) != (unsigned) num_sccs)
2579	{
2580	/* For SCCs we want to merge clear all alias_ddrs for edges
2581	inside the component. */
2582	for_each_edge (pg, pg_unmark_merged_alias_ddrs, &cbdata);
2583
2584	/* Run SCC finding algorithm again, with alias dependence edges
2585	skipped. This is to topologically sort partitions according to
2586	compilation time known dependence. Note the topological order
2587	is stored in the form of pg's post order number. */
2588	num_sccs_no_alias = graphds_scc (pg, NULL, pg_skip_alias_edge);
2589	/* We cannot assert partitions->length () == num_sccs_no_alias
2590	since we are not ignoring alias edges in cycles we are
2591	going to merge. That's required to compute correct postorder. */
2592	/* With topological order, we can construct two subgraphs L and R.
2593	L contains edge <x, y> where x < y in terms of post order, while
2594	R contains edge <x, y> where x > y. Edges for compilation time
2595	known dependence all fall in R, so we break SCCs by removing all
2596	(alias) edges of in subgraph L. */
2597	for_each_edge (pg, pg_collect_alias_ddrs, &cbdata);
2598	}
2599
2600	/* For SCC that doesn't need to be broken, merge it. */
2601	for (i = 0; i < num_sccs; ++i)
2602	{
2603	if (!bitmap_bit_p (sccs_to_merge, i))
2604	continue;
2605
2606	for (j = 0; partitions->iterate (ix: j, ptr: &first); ++j)
2607	if (cbdata.vertices_component[j] == i)
2608	break;
2609	for (k = j + 1; partitions->iterate (ix: k, ptr: &partition); ++k)
2610	{
2611	struct pg_vdata *data;
2612
2613	if (cbdata.vertices_component[k] != i)
2614	continue;
2615
2616	partition_merge_into (NULL, dest: first, partition, ft: FUSE_SAME_SCC);
2617	(*partitions)[k] = NULL;
2618	partition_free (partition);
2619	data = (struct pg_vdata *)pg->vertices[k].data;
2620	gcc_assert (data->id == k);
2621	data->partition = NULL;
2622	/* The result partition of merged SCC must be sequential. */
2623	first->type = PTYPE_SEQUENTIAL;
2624	}
2625	}
2626	/* If reduction partition's SCC is broken by runtime alias checks,
2627	we force a negative post order to it making sure it will be scheduled
2628	in the last. */
2629	if (num_sccs_no_alias > 0)
2630	{
2631	j = -1;
2632	for (i = 0; i < pg->n_vertices; ++i)
2633	{
2634	struct pg_vdata *data = (struct pg_vdata *)pg->vertices[i].data;
2635	if (data->partition && partition_reduction_p (partition: data->partition))
2636	{
2637	gcc_assert (j == -1);
2638	j = i;
2639	}
2640	}
2641	if (j >= 0)
2642	pg->vertices[j].post = -1;
2643	}
2644
2645	free (ptr: cbdata.vertices_component);
2646	}
2647
2648	sort_partitions_by_post_order (pg, partitions);
2649	free_partition_graph_vdata (pg);
2650	for_each_edge (pg, free_partition_graph_edata_cb, NULL);
2651	free_graph (g: pg);
2652
2653	if (dump_file && (dump_flags & TDF_DETAILS))
2654	{
2655	fprintf (stream: dump_file, format: "Possible alias data dependence to break:\n");
2656	dump_data_dependence_relations (dump_file, *alias_ddrs);
2657	}
2658	}
2659
2660	/* Compute and return an expression whose value is the segment length which
2661	will be accessed by DR in NITERS iterations. */
2662
2663	static tree
2664	data_ref_segment_size (struct data_reference *dr, tree niters)
2665	{
2666	niters = size_binop (MINUS_EXPR,
2667	fold_convert (sizetype, niters),
2668	size_one_node);
2669	return size_binop (MULT_EXPR,
2670	fold_convert (sizetype, DR_STEP (dr)),
2671	fold_convert (sizetype, niters));
2672	}
2673
2674	/* Return true if LOOP's latch is dominated by statement for data reference
2675	DR. */
2676
2677	static inline bool
2678	latch_dominated_by_data_ref (class loop *loop, data_reference *dr)
2679	{
2680	return dominated_by_p (CDI_DOMINATORS, single_exit (loop)->src,
2681	gimple_bb (DR_STMT (dr)));
2682	}
2683
2684	/* Compute alias check pairs and store them in COMP_ALIAS_PAIRS for LOOP's
2685	data dependence relations ALIAS_DDRS. */
2686
2687	static void
2688	compute_alias_check_pairs (class loop *loop, vec<ddr_p> *alias_ddrs,
2689	vec<dr_with_seg_len_pair_t> *comp_alias_pairs)
2690	{
2691	unsigned int i;
2692	unsigned HOST_WIDE_INT factor = 1;
2693	tree niters_plus_one, niters = number_of_latch_executions (loop);
2694
2695	gcc_assert (niters != NULL_TREE && niters != chrec_dont_know);
2696	niters = fold_convert (sizetype, niters);
2697	niters_plus_one = size_binop (PLUS_EXPR, niters, size_one_node);
2698
2699	if (dump_file && (dump_flags & TDF_DETAILS))
2700	fprintf (stream: dump_file, format: "Creating alias check pairs:\n");
2701
2702	/* Iterate all data dependence relations and compute alias check pairs. */
2703	for (i = 0; i < alias_ddrs->length (); i++)
2704	{
2705	ddr_p ddr = (*alias_ddrs)[i];
2706	struct data_reference *dr_a = DDR_A (ddr);
2707	struct data_reference *dr_b = DDR_B (ddr);
2708	tree seg_length_a, seg_length_b;
2709
2710	if (latch_dominated_by_data_ref (loop, dr: dr_a))
2711	seg_length_a = data_ref_segment_size (dr: dr_a, niters: niters_plus_one);
2712	else
2713	seg_length_a = data_ref_segment_size (dr: dr_a, niters);
2714
2715	if (latch_dominated_by_data_ref (loop, dr: dr_b))
2716	seg_length_b = data_ref_segment_size (dr: dr_b, niters: niters_plus_one);
2717	else
2718	seg_length_b = data_ref_segment_size (dr: dr_b, niters);
2719
2720	unsigned HOST_WIDE_INT access_size_a
2721	= tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a))));
2722	unsigned HOST_WIDE_INT access_size_b
2723	= tree_to_uhwi (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_b))));
2724	unsigned int align_a = TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_a)));
2725	unsigned int align_b = TYPE_ALIGN_UNIT (TREE_TYPE (DR_REF (dr_b)));
2726
2727	dr_with_seg_len_pair_t dr_with_seg_len_pair
2728	(dr_with_seg_len (dr_a, seg_length_a, access_size_a, align_a),
2729	dr_with_seg_len (dr_b, seg_length_b, access_size_b, align_b),
2730	/* ??? Would WELL_ORDERED be safe? */
2731	dr_with_seg_len_pair_t::REORDERED);
2732
2733	comp_alias_pairs->safe_push (obj: dr_with_seg_len_pair);
2734	}
2735
2736	if (tree_fits_uhwi_p (niters))
2737	factor = tree_to_uhwi (niters);
2738
2739	/* Prune alias check pairs. */
2740	prune_runtime_alias_test_list (comp_alias_pairs, factor);
2741	if (dump_file && (dump_flags & TDF_DETAILS))
2742	fprintf (stream: dump_file,
2743	format: "Improved number of alias checks from %d to %d\n",
2744	alias_ddrs->length (), comp_alias_pairs->length ());
2745	}
2746
2747	/* Given data dependence relations in ALIAS_DDRS, generate runtime alias
2748	checks and version LOOP under condition of these runtime alias checks. */
2749
2750	static void
2751	version_loop_by_alias_check (vec<struct partition *> *partitions,
2752	class loop *loop, vec<ddr_p> *alias_ddrs)
2753	{
2754	profile_probability prob;
2755	basic_block cond_bb;
2756	class loop *nloop;
2757	tree lhs, arg0, cond_expr = NULL_TREE;
2758	gimple_seq cond_stmts = NULL;
2759	gimple *call_stmt = NULL;
2760	auto_vec<dr_with_seg_len_pair_t> comp_alias_pairs;
2761
2762	/* Generate code for runtime alias checks if necessary. */
2763	gcc_assert (alias_ddrs->length () > 0);
2764
2765	if (dump_file && (dump_flags & TDF_DETAILS))
2766	fprintf (stream: dump_file,
2767	format: "Version loop <%d> with runtime alias check\n", loop->num);
2768
2769	compute_alias_check_pairs (loop, alias_ddrs, comp_alias_pairs: &comp_alias_pairs);
2770	create_runtime_alias_checks (loop, &comp_alias_pairs, &cond_expr);
2771	cond_expr = force_gimple_operand_1 (cond_expr, &cond_stmts,
2772	is_gimple_val, NULL_TREE);
2773
2774	/* Depend on vectorizer to fold IFN_LOOP_DIST_ALIAS. */
2775	bool cancelable_p = flag_tree_loop_vectorize;
2776	if (cancelable_p)
2777	{
2778	unsigned i = 0;
2779	struct partition *partition;
2780	for (; partitions->iterate (ix: i, ptr: &partition); ++i)
2781	if (!partition_builtin_p (partition))
2782	break;
2783
2784	/* If all partitions are builtins, distributing it would be profitable and
2785	we don't want to cancel the runtime alias checks. */
2786	if (i == partitions->length ())
2787	cancelable_p = false;
2788	}
2789
2790	/* Generate internal function call for loop distribution alias check if the
2791	runtime alias check should be cancelable. */
2792	if (cancelable_p)
2793	{
2794	call_stmt = gimple_build_call_internal (IFN_LOOP_DIST_ALIAS,
2795	2, NULL_TREE, cond_expr);
2796	lhs = make_ssa_name (boolean_type_node);
2797	gimple_call_set_lhs (gs: call_stmt, lhs);
2798	}
2799	else
2800	lhs = cond_expr;
2801
2802	prob = profile_probability::guessed_always ().apply_scale (num: 9, den: 10);
2803	initialize_original_copy_tables ();
2804	nloop = loop_version (loop, lhs, &cond_bb, prob, prob.invert (),
2805	prob, prob.invert (), true);
2806	free_original_copy_tables ();
2807	/* Record the original loop number in newly generated loops. In case of
2808	distribution, the original loop will be distributed and the new loop
2809	is kept. */
2810	loop->orig_loop_num = nloop->num;
2811	nloop->orig_loop_num = nloop->num;
2812	nloop->dont_vectorize = true;
2813	nloop->force_vectorize = false;
2814
2815	if (call_stmt)
2816	{
2817	/* Record new loop's num in IFN_LOOP_DIST_ALIAS because the original
2818	loop could be destroyed. */
2819	arg0 = build_int_cst (integer_type_node, loop->orig_loop_num);
2820	gimple_call_set_arg (gs: call_stmt, index: 0, arg: arg0);
2821	gimple_seq_add_stmt_without_update (&cond_stmts, call_stmt);
2822	}
2823
2824	if (cond_stmts)
2825	{
2826	gimple_stmt_iterator cond_gsi = gsi_last_bb (bb: cond_bb);
2827	gsi_insert_seq_before (&cond_gsi, cond_stmts, GSI_SAME_STMT);
2828	}
2829	update_ssa (TODO_update_ssa_no_phi);
2830	}
2831
2832	/* Return true if loop versioning is needed to distrubute PARTITIONS.
2833	ALIAS_DDRS are data dependence relations for runtime alias check. */
2834
2835	static inline bool
2836	version_for_distribution_p (vec<struct partition *> *partitions,
2837	vec<ddr_p> *alias_ddrs)
2838	{
2839	/* No need to version loop if we have only one partition. */
2840	if (partitions->length () == 1)
2841	return false;
2842
2843	/* Need to version loop if runtime alias check is necessary. */
2844	return (alias_ddrs->length () > 0);
2845	}
2846
2847	/* Compare base offset of builtin mem* partitions P1 and P2. */
2848
2849	static int
2850	offset_cmp (const void *vp1, const void *vp2)
2851	{
2852	struct partition *p1 = *(struct partition *const *) vp1;
2853	struct partition *p2 = *(struct partition *const *) vp2;
2854	unsigned HOST_WIDE_INT o1 = p1->builtin->dst_base_offset;
2855	unsigned HOST_WIDE_INT o2 = p2->builtin->dst_base_offset;
2856	return (o2 < o1) - (o1 < o2);
2857	}
2858
2859	/* Fuse adjacent memset builtin PARTITIONS if possible. This is a special
2860	case optimization transforming below code:
2861
2862	__builtin_memset (&obj, 0, 100);
2863	_1 = &obj + 100;
2864	__builtin_memset (_1, 0, 200);
2865	_2 = &obj + 300;
2866	__builtin_memset (_2, 0, 100);
2867
2868	into:
2869
2870	__builtin_memset (&obj, 0, 400);
2871
2872	Note we don't have dependence information between different partitions
2873	at this point, as a result, we can't handle nonadjacent memset builtin
2874	partitions since dependence might be broken. */
2875
2876	static void
2877	fuse_memset_builtins (vec<struct partition *> *partitions)
2878	{
2879	unsigned i, j;
2880	struct partition *part1, *part2;
2881	tree rhs1, rhs2;
2882
2883	for (i = 0; partitions->iterate (ix: i, ptr: &part1);)
2884	{
2885	if (part1->kind != PKIND_MEMSET)
2886	{
2887	i++;
2888	continue;
2889	}
2890
2891	/* Find sub-array of memset builtins of the same base. Index range
2892	of the sub-array is [i, j) with "j > i". */
2893	for (j = i + 1; partitions->iterate (ix: j, ptr: &part2); ++j)
2894	{
2895	if (part2->kind != PKIND_MEMSET
2896	|| !operand_equal_p (part1->builtin->dst_base_base,
2897	part2->builtin->dst_base_base, flags: 0))
2898	break;
2899
2900	/* Memset calls setting different values can't be merged. */
2901	rhs1 = gimple_assign_rhs1 (DR_STMT (part1->builtin->dst_dr));
2902	rhs2 = gimple_assign_rhs1 (DR_STMT (part2->builtin->dst_dr));
2903	if (!operand_equal_p (rhs1, rhs2, flags: 0))
2904	break;
2905	}
2906
2907	/* Stable sort is required in order to avoid breaking dependence. */
2908	gcc_stablesort (&(*partitions)[i], j - i, sizeof (*partitions)[i],
2909	offset_cmp);
2910	/* Continue with next partition. */
2911	i = j;
2912	}
2913
2914	/* Merge all consecutive memset builtin partitions. */
2915	for (i = 0; i < partitions->length () - 1;)
2916	{
2917	part1 = (*partitions)[i];
2918	if (part1->kind != PKIND_MEMSET)
2919	{
2920	i++;
2921	continue;
2922	}
2923
2924	part2 = (*partitions)[i + 1];
2925	/* Only merge memset partitions of the same base and with constant
2926	access sizes. */
2927	if (part2->kind != PKIND_MEMSET
2928	|| TREE_CODE (part1->builtin->size) != INTEGER_CST
2929	|| TREE_CODE (part2->builtin->size) != INTEGER_CST
2930	|| !operand_equal_p (part1->builtin->dst_base_base,
2931	part2->builtin->dst_base_base, flags: 0))
2932	{
2933	i++;
2934	continue;
2935	}
2936	rhs1 = gimple_assign_rhs1 (DR_STMT (part1->builtin->dst_dr));
2937	rhs2 = gimple_assign_rhs1 (DR_STMT (part2->builtin->dst_dr));
2938	int bytev1 = const_with_all_bytes_same (val: rhs1);
2939	int bytev2 = const_with_all_bytes_same (val: rhs2);
2940	/* Only merge memset partitions of the same value. */
2941	if (bytev1 != bytev2 || bytev1 == -1)
2942	{
2943	i++;
2944	continue;
2945	}
2946	wide_int end1 = wi::add (x: part1->builtin->dst_base_offset,
2947	y: wi::to_wide (t: part1->builtin->size));
2948	/* Only merge adjacent memset partitions. */
2949	if (wi::ne_p (x: end1, y: part2->builtin->dst_base_offset))
2950	{
2951	i++;
2952	continue;
2953	}
2954	/* Merge partitions[i] and partitions[i+1]. */
2955	part1->builtin->size = fold_build2 (PLUS_EXPR, sizetype,
2956	part1->builtin->size,
2957	part2->builtin->size);
2958	partition_free (partition: part2);
2959	partitions->ordered_remove (ix: i + 1);
2960	}
2961	}
2962
2963	void
2964	loop_distribution::finalize_partitions (class loop *loop,
2965	vec<struct partition *> *partitions,
2966	vec<ddr_p> *alias_ddrs)
2967	{
2968	unsigned i;
2969	struct partition *partition, *a;
2970
2971	if (partitions->length () == 1
2972	|| alias_ddrs->length () > 0)
2973	return;
2974
2975	unsigned num_builtin = 0, num_normal = 0, num_partial_memset = 0;
2976	bool same_type_p = true;
2977	enum partition_type type = ((*partitions)[0])->type;
2978	for (i = 0; partitions->iterate (ix: i, ptr: &partition); ++i)
2979	{
2980	same_type_p &= (type == partition->type);
2981	if (partition_builtin_p (partition))
2982	{
2983	num_builtin++;
2984	continue;
2985	}
2986	num_normal++;
2987	if (partition->kind == PKIND_PARTIAL_MEMSET)
2988	num_partial_memset++;
2989	}
2990
2991	/* Don't distribute current loop into too many loops given we don't have
2992	memory stream cost model. Be even more conservative in case of loop
2993	nest distribution. */
2994	if ((same_type_p && num_builtin == 0
2995	&& (loop->inner == NULL || num_normal != 2 || num_partial_memset != 1))
2996	|| (loop->inner != NULL
2997	&& i >= NUM_PARTITION_THRESHOLD && num_normal > 1)
2998	|| (loop->inner == NULL
2999	&& i >= NUM_PARTITION_THRESHOLD && num_normal > num_builtin))
3000	{
3001	a = (*partitions)[0];
3002	for (i = 1; partitions->iterate (ix: i, ptr: &partition); ++i)
3003	{
3004	partition_merge_into (NULL, dest: a, partition, ft: FUSE_FINALIZE);
3005	partition_free (partition);
3006	}
3007	partitions->truncate (size: 1);
3008	}
3009
3010	/* Fuse memset builtins if possible. */
3011	if (partitions->length () > 1)
3012	fuse_memset_builtins (partitions);
3013	}
3014
3015	/* Distributes the code from LOOP in such a way that producer statements
3016	are placed before consumer statements. Tries to separate only the
3017	statements from STMTS into separate loops. Returns the number of
3018	distributed loops. Set NB_CALLS to number of generated builtin calls.
3019	Set *DESTROY_P to whether LOOP needs to be destroyed. */
3020
3021	int
3022	loop_distribution::distribute_loop (class loop *loop,
3023	const vec<gimple *> &stmts,
3024	control_dependences *cd, int *nb_calls, bool *destroy_p,
3025	bool only_patterns_p)
3026	{
3027	ddrs_table = new hash_table<ddr_hasher> (389);
3028	struct graph *rdg;
3029	partition *partition;
3030	int i, nbp;
3031
3032	*destroy_p = false;
3033	*nb_calls = 0;
3034	loop_nest.create (nelems: 0);
3035	if (!find_loop_nest (loop, &loop_nest))
3036	{
3037	loop_nest.release ();
3038	delete ddrs_table;
3039	return 0;
3040	}
3041
3042	datarefs_vec.create (nelems: 20);
3043	has_nonaddressable_dataref_p = false;
3044	rdg = build_rdg (loop, cd);
3045	if (!rdg)
3046	{
3047	if (dump_file && (dump_flags & TDF_DETAILS))
3048	fprintf (stream: dump_file,
3049	format: "Loop %d not distributed: failed to build the RDG.\n",
3050	loop->num);
3051
3052	loop_nest.release ();
3053	free_data_refs (datarefs_vec);
3054	delete ddrs_table;
3055	return 0;
3056	}
3057
3058	if (datarefs_vec.length () > MAX_DATAREFS_NUM)
3059	{
3060	if (dump_file && (dump_flags & TDF_DETAILS))
3061	fprintf (stream: dump_file,
3062	format: "Loop %d not distributed: too many memory references.\n",
3063	loop->num);
3064
3065	free_rdg (rdg);
3066	loop_nest.release ();
3067	free_data_refs (datarefs_vec);
3068	delete ddrs_table;
3069	return 0;
3070	}
3071
3072	data_reference_p dref;
3073	for (i = 0; datarefs_vec.iterate (ix: i, ptr: &dref); ++i)
3074	dref->aux = (void *) (uintptr_t) i;
3075
3076	if (dump_file && (dump_flags & TDF_DETAILS))
3077	dump_rdg (file: dump_file, rdg);
3078
3079	auto_vec<struct partition *, 3> partitions;
3080	rdg_build_partitions (rdg, starting_stmts: stmts, partitions: &partitions);
3081
3082	auto_vec<ddr_p> alias_ddrs;
3083
3084	auto_bitmap stmt_in_all_partitions;
3085	bitmap_copy (stmt_in_all_partitions, partitions[0]->stmts);
3086	for (i = 1; partitions.iterate (ix: i, ptr: &partition); ++i)
3087	bitmap_and_into (stmt_in_all_partitions, partitions[i]->stmts);
3088
3089	bool any_builtin = false;
3090	bool reduction_in_all = false;
3091	int reduction_partition_num = -1;
3092	FOR_EACH_VEC_ELT (partitions, i, partition)
3093	{
3094	reduction_in_all
3095	|= classify_partition (loop, rdg, partition, stmt_in_all_partitions);
3096	any_builtin |= partition_builtin_p (partition);
3097	}
3098
3099	/* If we are only distributing patterns but did not detect any,
3100	simply bail out. */
3101	if (only_patterns_p
3102	&& !any_builtin)
3103	{
3104	nbp = 0;
3105	goto ldist_done;
3106	}
3107
3108	/* If we are only distributing patterns fuse all partitions that
3109	were not classified as builtins. This also avoids chopping
3110	a loop into pieces, separated by builtin calls. That is, we
3111	only want no or a single loop body remaining. */
3112	struct partition *into;
3113	if (only_patterns_p)
3114	{
3115	for (i = 0; partitions.iterate (ix: i, ptr: &into); ++i)
3116	if (!partition_builtin_p (partition: into))
3117	break;
3118	for (++i; partitions.iterate (ix: i, ptr: &partition); ++i)
3119	if (!partition_builtin_p (partition))
3120	{
3121	partition_merge_into (NULL, dest: into, partition, ft: FUSE_NON_BUILTIN);
3122	partitions.unordered_remove (ix: i);
3123	partition_free (partition);
3124	i--;
3125	}
3126	}
3127
3128	/* Due to limitations in the transform phase we have to fuse all
3129	reduction partitions into the last partition so the existing
3130	loop will contain all loop-closed PHI nodes. */
3131	for (i = 0; partitions.iterate (ix: i, ptr: &into); ++i)
3132	if (partition_reduction_p (partition: into))
3133	break;
3134	for (i = i + 1; partitions.iterate (ix: i, ptr: &partition); ++i)
3135	if (partition_reduction_p (partition))
3136	{
3137	partition_merge_into (rdg, dest: into, partition, ft: FUSE_REDUCTION);
3138	partitions.unordered_remove (ix: i);
3139	partition_free (partition);
3140	i--;
3141	}
3142
3143	/* Apply our simple cost model - fuse partitions with similar
3144	memory accesses. */
3145	for (i = 0; partitions.iterate (ix: i, ptr: &into); ++i)
3146	{
3147	bool changed = false;
3148	for (int j = i + 1; partitions.iterate (ix: j, ptr: &partition); ++j)
3149	{
3150	if (share_memory_accesses (rdg, partition1: into, partition2: partition))
3151	{
3152	partition_merge_into (rdg, dest: into, partition, ft: FUSE_SHARE_REF);
3153	partitions.unordered_remove (ix: j);
3154	partition_free (partition);
3155	j--;
3156	changed = true;
3157	}
3158	}
3159	/* If we fused 0 1 2 in step 1 to 0,2 1 as 0 and 2 have similar
3160	accesses when 1 and 2 have similar accesses but not 0 and 1
3161	then in the next iteration we will fail to consider merging
3162	1 into 0,2. So try again if we did any merging into 0. */
3163	if (changed)
3164	i--;
3165	}
3166
3167	/* Put a non-builtin partition last if we need to preserve a reduction.
3168	In most cases this helps to keep a normal partition last avoiding to
3169	spill a reduction result across builtin calls.
3170	??? The proper way would be to use dependences to see whether we
3171	can move builtin partitions earlier during merge_dep_scc_partitions
3172	and its sort_partitions_by_post_order. Especially when the
3173	dependence graph is composed of multiple independent subgraphs the
3174	heuristic does not work reliably. */
3175	if (reduction_in_all
3176	&& partition_builtin_p (partition: partitions.last()))
3177	FOR_EACH_VEC_ELT (partitions, i, partition)
3178	if (!partition_builtin_p (partition))
3179	{
3180	partitions.unordered_remove (ix: i);
3181	partitions.quick_push (obj: partition);
3182	break;
3183	}
3184
3185	/* Build the partition dependency graph and fuse partitions in strong
3186	connected component. */
3187	if (partitions.length () > 1)
3188	{
3189	/* Don't support loop nest distribution under runtime alias check
3190	since it's not likely to enable many vectorization opportunities.
3191	Also if loop has any data reference which may be not addressable
3192	since alias check needs to take, compare address of the object. */
3193	if (loop->inner || has_nonaddressable_dataref_p)
3194	merge_dep_scc_partitions (rdg, partitions: &partitions, ignore_alias_p: false);
3195	else
3196	{
3197	merge_dep_scc_partitions (rdg, partitions: &partitions, ignore_alias_p: true);
3198	if (partitions.length () > 1)
3199	break_alias_scc_partitions (rdg, partitions: &partitions, alias_ddrs: &alias_ddrs);
3200	}
3201	}
3202
3203	finalize_partitions (loop, partitions: &partitions, alias_ddrs: &alias_ddrs);
3204
3205	/* If there is a reduction in all partitions make sure the last
3206	non-builtin partition provides the LC PHI defs. */
3207	if (reduction_in_all)
3208	{
3209	FOR_EACH_VEC_ELT (partitions, i, partition)
3210	if (!partition_builtin_p (partition))
3211	reduction_partition_num = i;
3212	if (reduction_partition_num == -1)
3213	{
3214	/* If all partitions are builtin, force the last one to
3215	be code generated as normal partition. */
3216	partition = partitions.last ();
3217	partition->kind = PKIND_NORMAL;
3218	}
3219	}
3220
3221	nbp = partitions.length ();
3222	if (nbp == 0
3223	|| (nbp == 1 && !partition_builtin_p (partition: partitions[0]))
3224	|| (nbp > 1 && partition_contains_all_rw (rdg, partitions)))
3225	{
3226	nbp = 0;
3227	goto ldist_done;
3228	}
3229
3230	if (version_for_distribution_p (partitions: &partitions, alias_ddrs: &alias_ddrs))
3231	version_loop_by_alias_check (partitions: &partitions, loop, alias_ddrs: &alias_ddrs);
3232
3233	if (dump_file && (dump_flags & TDF_DETAILS))
3234	{
3235	fprintf (stream: dump_file,
3236	format: "distribute loop <%d> into partitions:\n", loop->num);
3237	dump_rdg_partitions (file: dump_file, partitions);
3238	}
3239
3240	FOR_EACH_VEC_ELT (partitions, i, partition)
3241	{
3242	if (partition_builtin_p (partition))
3243	(*nb_calls)++;
3244	*destroy_p |= generate_code_for_partition (loop, partition, copy_p: i < nbp - 1,
3245	keep_lc_phis_p: i == reduction_partition_num);
3246	}
3247
3248	ldist_done:
3249	loop_nest.release ();
3250	free_data_refs (datarefs_vec);
3251	for (hash_table<ddr_hasher>::iterator iter = ddrs_table->begin ();
3252	iter != ddrs_table->end (); ++iter)
3253	{
3254	free_dependence_relation (*iter);
3255	*iter = NULL;
3256	}
3257	delete ddrs_table;
3258
3259	FOR_EACH_VEC_ELT (partitions, i, partition)
3260	partition_free (partition);
3261
3262	free_rdg (rdg);
3263	return nbp - *nb_calls;
3264	}
3265
3266
3267	void loop_distribution::bb_top_order_init (void)
3268	{
3269	int rpo_num;
3270	int *rpo = XNEWVEC (int, n_basic_blocks_for_fn (cfun) - NUM_FIXED_BLOCKS);
3271	edge entry = single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3272	bitmap exit_bbs = BITMAP_ALLOC (NULL);
3273
3274	bb_top_order_index = XNEWVEC (int, last_basic_block_for_fn (cfun));
3275	bb_top_order_index_size = last_basic_block_for_fn (cfun);
3276
3277	entry->flags &= ~EDGE_DFS_BACK;
3278	bitmap_set_bit (exit_bbs, EXIT_BLOCK);
3279	rpo_num = rev_post_order_and_mark_dfs_back_seme (cfun, entry, exit_bbs, true,
3280	rpo, NULL);
3281	BITMAP_FREE (exit_bbs);
3282
3283	for (int i = 0; i < rpo_num; i++)
3284	bb_top_order_index[rpo[i]] = i;
3285
3286	free (ptr: rpo);
3287	}
3288
3289	void loop_distribution::bb_top_order_destroy ()
3290	{
3291	free (ptr: bb_top_order_index);
3292	bb_top_order_index = NULL;
3293	bb_top_order_index_size = 0;
3294	}
3295
3296
3297	/* Given LOOP, this function records seed statements for distribution in
3298	WORK_LIST. Return false if there is nothing for distribution. */
3299
3300	static bool
3301	find_seed_stmts_for_distribution (class loop *loop, vec<gimple *> *work_list)
3302	{
3303	basic_block *bbs = get_loop_body_in_dom_order (loop);
3304
3305	/* Initialize the worklist with stmts we seed the partitions with. */
3306	for (unsigned i = 0; i < loop->num_nodes; ++i)
3307	{
3308	/* In irreducible sub-regions we don't know how to redirect
3309	conditions, so fail. See PR100492. */
3310	if (bbs[i]->flags & BB_IRREDUCIBLE_LOOP)
3311	{
3312	if (dump_file && (dump_flags & TDF_DETAILS))
3313	fprintf (stream: dump_file, format: "loop %d contains an irreducible region.\n",
3314	loop->num);
3315	work_list->truncate (size: 0);
3316	break;
3317	}
3318	for (gphi_iterator gsi = gsi_start_phis (bbs[i]);
3319	!gsi_end_p (i: gsi); gsi_next (i: &gsi))
3320	{
3321	gphi *phi = gsi.phi ();
3322	if (virtual_operand_p (op: gimple_phi_result (gs: phi)))
3323	continue;
3324	/* Distribute stmts which have defs that are used outside of
3325	the loop. */
3326	if (!stmt_has_scalar_dependences_outside_loop (loop, stmt: phi))
3327	continue;
3328	work_list->safe_push (obj: phi);
3329	}
3330	for (gimple_stmt_iterator gsi = gsi_start_bb (bb: bbs[i]);
3331	!gsi_end_p (i: gsi); gsi_next (i: &gsi))
3332	{
3333	gimple *stmt = gsi_stmt (i: gsi);
3334
3335	/* Ignore clobbers, they do not have true side effects. */
3336	if (gimple_clobber_p (s: stmt))
3337	continue;
3338
3339	/* If there is a stmt with side-effects bail out - we
3340	cannot and should not distribute this loop. */
3341	if (gimple_has_side_effects (stmt))
3342	{
3343	free (ptr: bbs);
3344	return false;
3345	}
3346
3347	/* Distribute stmts which have defs that are used outside of
3348	the loop. */
3349	if (stmt_has_scalar_dependences_outside_loop (loop, stmt))
3350	;
3351	/* Otherwise only distribute stores for now. */
3352	else if (!gimple_vdef (g: stmt))
3353	continue;
3354
3355	work_list->safe_push (obj: stmt);
3356	}
3357	}
3358	bool res = work_list->length () > 0;
3359	if (res && !can_copy_bbs_p (bbs, loop->num_nodes))
3360	{
3361	if (dump_file && (dump_flags & TDF_DETAILS))
3362	fprintf (stream: dump_file, format: "cannot copy loop %d.\n", loop->num);
3363	res = false;
3364	}
3365	free (ptr: bbs);
3366	return res;
3367	}
3368
3369	/* A helper function for generate_{rawmemchr,strlen}_builtin functions in order
3370	to place new statements SEQ before LOOP and replace the old reduction
3371	variable with the new one. */
3372
3373	static void
3374	generate_reduction_builtin_1 (loop_p loop, gimple_seq &seq,
3375	tree reduction_var_old, tree reduction_var_new,
3376	const char *info, machine_mode load_mode)
3377	{
3378	gcc_assert (flag_tree_loop_distribute_patterns);
3379
3380	/* Place new statements before LOOP. */
3381	gimple_stmt_iterator gsi = gsi_last_bb (bb: loop_preheader_edge (loop)->src);
3382	gsi_insert_seq_after (&gsi, seq, GSI_CONTINUE_LINKING);
3383
3384	/* Replace old reduction variable with new one. */
3385	imm_use_iterator iter;
3386	gimple *stmt;
3387	use_operand_p use_p;
3388	FOR_EACH_IMM_USE_STMT (stmt, iter, reduction_var_old)
3389	{
3390	FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
3391	SET_USE (use_p, reduction_var_new);
3392
3393	update_stmt (s: stmt);
3394	}
3395
3396	if (dump_file && (dump_flags & TDF_DETAILS))
3397	fprintf (stream: dump_file, format: info, GET_MODE_NAME (load_mode));
3398	}
3399
3400	/* Generate a call to rawmemchr and place it before LOOP. REDUCTION_VAR is
3401	replaced with a fresh SSA name representing the result of the call. */
3402
3403	static void
3404	generate_rawmemchr_builtin (loop_p loop, tree reduction_var,
3405	data_reference_p store_dr, tree base, tree pattern,
3406	location_t loc)
3407	{
3408	gimple_seq seq = NULL;
3409
3410	tree mem = force_gimple_operand (base, &seq, true, NULL_TREE);
3411	gimple *fn_call = gimple_build_call_internal (IFN_RAWMEMCHR, 2, mem, pattern);
3412	tree reduction_var_new = copy_ssa_name (var: reduction_var);
3413	gimple_call_set_lhs (gs: fn_call, lhs: reduction_var_new);
3414	gimple_set_location (g: fn_call, location: loc);
3415	gimple_seq_add_stmt (&seq, fn_call);
3416
3417	if (store_dr)
3418	{
3419	gassign *g = gimple_build_assign (DR_REF (store_dr), reduction_var_new);
3420	gimple_seq_add_stmt (&seq, g);
3421	}
3422
3423	generate_reduction_builtin_1 (loop, seq, reduction_var_old: reduction_var, reduction_var_new,
3424	info: "generated rawmemchr%s\n",
3425	TYPE_MODE (TREE_TYPE (TREE_TYPE (base))));
3426	}
3427
3428	/* Helper function for generate_strlen_builtin(,_using_rawmemchr) */
3429
3430	static void
3431	generate_strlen_builtin_1 (loop_p loop, gimple_seq &seq,
3432	tree reduction_var_old, tree reduction_var_new,
3433	machine_mode mode, tree start_len)
3434	{
3435	/* REDUCTION_VAR_NEW has either size type or ptrdiff type and must be
3436	converted if types of old and new reduction variable are not compatible. */
3437	reduction_var_new = gimple_convert (seq: &seq, TREE_TYPE (reduction_var_old),
3438	op: reduction_var_new);
3439
3440	/* Loops of the form `for (i=42; s[i]; ++i);` have an additional start
3441	length. */
3442	if (!integer_zerop (start_len))
3443	{
3444	tree lhs = make_ssa_name (TREE_TYPE (reduction_var_new));
3445	gimple *g = gimple_build_assign (lhs, PLUS_EXPR, reduction_var_new,
3446	start_len);
3447	gimple_seq_add_stmt (&seq, g);
3448	reduction_var_new = lhs;
3449	}
3450
3451	generate_reduction_builtin_1 (loop, seq, reduction_var_old, reduction_var_new,
3452	info: "generated strlen%s\n", load_mode: mode);
3453	}
3454
3455	/* Generate a call to strlen and place it before LOOP. REDUCTION_VAR is
3456	replaced with a fresh SSA name representing the result of the call. */
3457
3458	static void
3459	generate_strlen_builtin (loop_p loop, tree reduction_var, tree base,
3460	tree start_len, location_t loc)
3461	{
3462	gimple_seq seq = NULL;
3463
3464	tree reduction_var_new = make_ssa_name (size_type_node);
3465
3466	tree mem = force_gimple_operand (base, &seq, true, NULL_TREE);
3467	tree fn = build_fold_addr_expr (builtin_decl_implicit (BUILT_IN_STRLEN));
3468	gimple *fn_call = gimple_build_call (fn, 1, mem);
3469	gimple_call_set_lhs (gs: fn_call, lhs: reduction_var_new);
3470	gimple_set_location (g: fn_call, location: loc);
3471	gimple_seq_add_stmt (&seq, fn_call);
3472
3473	generate_strlen_builtin_1 (loop, seq, reduction_var_old: reduction_var, reduction_var_new,
3474	QImode, start_len);
3475	}
3476
3477	/* Generate code in order to mimic the behaviour of strlen but this time over
3478	an array of elements with mode different than QI. REDUCTION_VAR is replaced
3479	with a fresh SSA name representing the result, i.e., the length. */
3480
3481	static void
3482	generate_strlen_builtin_using_rawmemchr (loop_p loop, tree reduction_var,
3483	tree base, tree load_type,
3484	tree start_len, location_t loc)
3485	{
3486	gimple_seq seq = NULL;
3487
3488	tree start = force_gimple_operand (base, &seq, true, NULL_TREE);
3489	tree zero = build_zero_cst (load_type);
3490	gimple *fn_call = gimple_build_call_internal (IFN_RAWMEMCHR, 2, start, zero);
3491	tree end = make_ssa_name (TREE_TYPE (base));
3492	gimple_call_set_lhs (gs: fn_call, lhs: end);
3493	gimple_set_location (g: fn_call, location: loc);
3494	gimple_seq_add_stmt (&seq, fn_call);
3495
3496	/* Determine the number of elements between START and END by
3497	evaluating (END - START) / sizeof (*START). */
3498	tree diff = make_ssa_name (ptrdiff_type_node);
3499	gimple *diff_stmt = gimple_build_assign (diff, POINTER_DIFF_EXPR, end, start);
3500	gimple_seq_add_stmt (&seq, diff_stmt);
3501	/* Let SIZE be the size of each character. */
3502	tree size = gimple_convert (seq: &seq, ptrdiff_type_node,
3503	TYPE_SIZE_UNIT (load_type));
3504	tree count = make_ssa_name (ptrdiff_type_node);
3505	gimple *count_stmt = gimple_build_assign (count, TRUNC_DIV_EXPR, diff, size);
3506	gimple_seq_add_stmt (&seq, count_stmt);
3507
3508	generate_strlen_builtin_1 (loop, seq, reduction_var_old: reduction_var, reduction_var_new: count,
3509	TYPE_MODE (load_type),
3510	start_len);
3511	}
3512
3513	/* Return true if we can count at least as many characters by taking pointer
3514	difference as we can count via reduction_var without an overflow. Thus
3515	compute 2^n < (2^(m-1) / s) where n = TYPE_PRECISION (reduction_var_type),
3516	m = TYPE_PRECISION (ptrdiff_type_node), and s = size of each character. */
3517	static bool
3518	reduction_var_overflows_first (tree reduction_var_type, tree load_type)
3519	{
3520	widest_int n2 = wi::lshift (x: 1, TYPE_PRECISION (reduction_var_type));;
3521	widest_int m2 = wi::lshift (x: 1, TYPE_PRECISION (ptrdiff_type_node) - 1);
3522	widest_int s = wi::to_widest (TYPE_SIZE_UNIT (load_type));
3523	return wi::ltu_p (x: n2, y: wi::udiv_trunc (x: m2, y: s));
3524	}
3525
3526	static gimple *
3527	determine_reduction_stmt_1 (const loop_p loop, const basic_block *bbs)
3528	{
3529	gimple *reduction_stmt = NULL;
3530
3531	for (unsigned i = 0, ninsns = 0; i < loop->num_nodes; ++i)
3532	{
3533	basic_block bb = bbs[i];
3534
3535	for (gphi_iterator bsi = gsi_start_phis (bb); !gsi_end_p (i: bsi);
3536	gsi_next_nondebug (i: &bsi))
3537	{
3538	gphi *phi = bsi.phi ();
3539	if (virtual_operand_p (op: gimple_phi_result (gs: phi)))
3540	continue;
3541	if (stmt_has_scalar_dependences_outside_loop (loop, stmt: phi))
3542	{
3543	if (reduction_stmt)
3544	return NULL;
3545	reduction_stmt = phi;
3546	}
3547	}
3548
3549	for (gimple_stmt_iterator bsi = gsi_start_bb (bb); !gsi_end_p (i: bsi);
3550	gsi_next_nondebug (i: &bsi), ++ninsns)
3551	{
3552	/* Bail out early for loops which are unlikely to match. */
3553	if (ninsns > 16)
3554	return NULL;
3555	gimple *stmt = gsi_stmt (i: bsi);
3556	if (gimple_clobber_p (s: stmt))
3557	continue;
3558	if (gimple_code (g: stmt) == GIMPLE_LABEL)
3559	continue;
3560	if (gimple_has_volatile_ops (stmt))
3561	return NULL;
3562	if (stmt_has_scalar_dependences_outside_loop (loop, stmt))
3563	{
3564	if (reduction_stmt)
3565	return NULL;
3566	reduction_stmt = stmt;
3567	}
3568	}
3569	}
3570
3571	return reduction_stmt;
3572	}
3573
3574	/* If LOOP has a single non-volatile reduction statement, then return a pointer
3575	to it. Otherwise return NULL. */
3576	static gimple *
3577	determine_reduction_stmt (const loop_p loop)
3578	{
3579	basic_block *bbs = get_loop_body (loop);
3580	gimple *reduction_stmt = determine_reduction_stmt_1 (loop, bbs);
3581	XDELETEVEC (bbs);
3582	return reduction_stmt;
3583	}
3584
3585	/* Transform loops which mimic the effects of builtins rawmemchr or strlen and
3586	replace them accordingly. For example, a loop of the form
3587
3588	for (; *p != 42; ++p);
3589
3590	is replaced by
3591
3592	p = rawmemchr<MODE> (p, 42);
3593
3594	under the assumption that rawmemchr is available for a particular MODE.
3595	Another example is
3596
3597	int i;
3598	for (i = 42; s[i]; ++i);
3599
3600	which is replaced by
3601
3602	i = (int)strlen (&s[42]) + 42;
3603
3604	for some character array S. In case array S is not of type character array
3605	we end up with
3606
3607	i = (int)(rawmemchr<MODE> (&s[42], 0) - &s[42]) + 42;
3608
3609	assuming that rawmemchr is available for a particular MODE. */
3610
3611	bool
3612	loop_distribution::transform_reduction_loop (loop_p loop)
3613	{
3614	gimple *reduction_stmt;
3615	data_reference_p load_dr = NULL, store_dr = NULL;
3616
3617	edge e = single_exit (loop);
3618	gcond *cond = safe_dyn_cast <gcond *> (p: *gsi_last_bb (bb: e->src));
3619	if (!cond)
3620	return false;
3621	/* Ensure loop condition is an (in)equality test and loop is exited either if
3622	the inequality test fails or the equality test succeeds. */
3623	if (!(e->flags & EDGE_FALSE_VALUE && gimple_cond_code (gs: cond) == NE_EXPR)
3624	&& !(e->flags & EDGE_TRUE_VALUE && gimple_cond_code (gs: cond) == EQ_EXPR))
3625	return false;
3626	/* A limitation of the current implementation is that we only support
3627	constant patterns in (in)equality tests. */
3628	tree pattern = gimple_cond_rhs (gs: cond);
3629	if (TREE_CODE (pattern) != INTEGER_CST)
3630	return false;
3631
3632	reduction_stmt = determine_reduction_stmt (loop);
3633
3634	/* A limitation of the current implementation is that we require a reduction
3635	statement. Therefore, loops without a reduction statement as in the
3636	following are not recognized:
3637	int *p;
3638	void foo (void) { for (; *p; ++p); } */
3639	if (reduction_stmt == NULL)
3640	return false;
3641
3642	/* Reduction variables are guaranteed to be SSA names. */
3643	tree reduction_var;
3644	switch (gimple_code (g: reduction_stmt))
3645	{
3646	case GIMPLE_ASSIGN:
3647	case GIMPLE_PHI:
3648	reduction_var = gimple_get_lhs (reduction_stmt);
3649	break;
3650	default:
3651	/* Bail out e.g. for GIMPLE_CALL. */
3652	return false;
3653	}
3654
3655	struct graph *rdg = build_rdg (loop, NULL);
3656	if (rdg == NULL)
3657	{
3658	if (dump_file && (dump_flags & TDF_DETAILS))
3659	fprintf (stream: dump_file,
3660	format: "Loop %d not transformed: failed to build the RDG.\n",
3661	loop->num);
3662
3663	return false;
3664	}
3665	auto_bitmap partition_stmts;
3666	bitmap_set_range (partition_stmts, 0, rdg->n_vertices);
3667	find_single_drs (loop, rdg, partition_stmts, dst_dr: &store_dr, src_dr: &load_dr);
3668	free_rdg (rdg);
3669
3670	/* Bail out if there is no single load. */
3671	if (load_dr == NULL)
3672	return false;
3673
3674	/* Reaching this point we have a loop with a single reduction variable,
3675	a single load, and an optional single store. */
3676
3677	tree load_ref = DR_REF (load_dr);
3678	tree load_type = TREE_TYPE (load_ref);
3679	tree load_access_base = build_fold_addr_expr (load_ref);
3680	tree load_access_size = TYPE_SIZE_UNIT (load_type);
3681	affine_iv load_iv, reduction_iv;
3682
3683	if (!INTEGRAL_TYPE_P (load_type)
3684	|| !type_has_mode_precision_p (t: load_type))
3685	return false;
3686
3687	/* We already ensured that the loop condition tests for (in)equality where the
3688	rhs is a constant pattern. Now ensure that the lhs is the result of the
3689	load. */
3690	if (gimple_cond_lhs (gs: cond) != gimple_assign_lhs (DR_STMT (load_dr)))
3691	return false;
3692
3693	/* Bail out if no affine induction variable with constant step can be
3694	determined. */
3695	if (!simple_iv (loop, loop, load_access_base, &load_iv, false))
3696	return false;
3697
3698	/* Bail out if memory accesses are not consecutive or not growing. */
3699	if (!operand_equal_p (load_iv.step, load_access_size, flags: 0))
3700	return false;
3701
3702	if (!simple_iv (loop, loop, reduction_var, &reduction_iv, false))
3703	return false;
3704
3705	/* Handle rawmemchr like loops. */
3706	if (operand_equal_p (load_iv.base, reduction_iv.base)
3707	&& operand_equal_p (load_iv.step, reduction_iv.step))
3708	{
3709	if (store_dr)
3710	{
3711	/* Ensure that we store to X and load from X+I where I>0. */
3712	if (TREE_CODE (load_iv.base) != POINTER_PLUS_EXPR
3713	|| !integer_onep (TREE_OPERAND (load_iv.base, 1)))
3714	return false;
3715	tree ptr_base = TREE_OPERAND (load_iv.base, 0);
3716	if (TREE_CODE (ptr_base) != SSA_NAME)
3717	return false;
3718	gimple *def = SSA_NAME_DEF_STMT (ptr_base);
3719	if (!gimple_assign_single_p (gs: def)
3720	|| gimple_assign_rhs1 (gs: def) != DR_REF (store_dr))
3721	return false;
3722	/* Ensure that the reduction value is stored. */
3723	if (gimple_assign_rhs1 (DR_STMT (store_dr)) != reduction_var)
3724	return false;
3725	}
3726	/* Bail out if target does not provide rawmemchr for a certain mode. */
3727	machine_mode mode = TYPE_MODE (load_type);
3728	if (direct_optab_handler (op: rawmemchr_optab, mode) == CODE_FOR_nothing)
3729	return false;
3730	location_t loc = gimple_location (DR_STMT (load_dr));
3731	generate_rawmemchr_builtin (loop, reduction_var, store_dr, base: load_iv.base,
3732	pattern, loc);
3733	return true;
3734	}
3735
3736	/* Handle strlen like loops. */
3737	if (store_dr == NULL
3738	&& integer_zerop (pattern)
3739	&& INTEGRAL_TYPE_P (TREE_TYPE (reduction_var))
3740	&& TREE_CODE (reduction_iv.base) == INTEGER_CST
3741	&& TREE_CODE (reduction_iv.step) == INTEGER_CST
3742	&& integer_onep (reduction_iv.step))
3743	{
3744	location_t loc = gimple_location (DR_STMT (load_dr));
3745	tree reduction_var_type = TREE_TYPE (reduction_var);
3746	/* While determining the length of a string an overflow might occur.
3747	If an overflow only occurs in the loop implementation and not in the
3748	strlen implementation, then either the overflow is undefined or the
3749	truncated result of strlen equals the one of the loop. Otherwise if
3750	an overflow may also occur in the strlen implementation, then
3751	replacing a loop by a call to strlen is sound whenever we ensure that
3752	if an overflow occurs in the strlen implementation, then also an
3753	overflow occurs in the loop implementation which is undefined. It
3754	seems reasonable to relax this and assume that the strlen
3755	implementation cannot overflow in case sizetype is big enough in the
3756	sense that an overflow can only happen for string objects which are
3757	bigger than half of the address space; at least for 32-bit targets and
3758	up.
3759
3760	For strlen which makes use of rawmemchr the maximal length of a string
3761	which can be determined without an overflow is PTRDIFF_MAX / S where
3762	each character has size S. Since an overflow for ptrdiff type is
3763	undefined we have to make sure that if an overflow occurs, then an
3764	overflow occurs in the loop implementation, too, and this is
3765	undefined, too. Similar as before we relax this and assume that no
3766	string object is larger than half of the address space; at least for
3767	32-bit targets and up. */
3768	if (TYPE_MODE (load_type) == TYPE_MODE (char_type_node)
3769	&& TYPE_PRECISION (load_type) == TYPE_PRECISION (char_type_node)
3770	&& ((TYPE_PRECISION (sizetype) >= TYPE_PRECISION (ptr_type_node) - 1
3771	&& TYPE_PRECISION (ptr_type_node) >= 32)
3772	|| (TYPE_OVERFLOW_UNDEFINED (reduction_var_type)
3773	&& TYPE_PRECISION (reduction_var_type) <= TYPE_PRECISION (sizetype)))
3774	&& builtin_decl_implicit (fncode: BUILT_IN_STRLEN))
3775	generate_strlen_builtin (loop, reduction_var, base: load_iv.base,
3776	start_len: reduction_iv.base, loc);
3777	else if (direct_optab_handler (op: rawmemchr_optab, TYPE_MODE (load_type))
3778	!= CODE_FOR_nothing
3779	&& ((TYPE_PRECISION (ptrdiff_type_node) == TYPE_PRECISION (ptr_type_node)
3780	&& TYPE_PRECISION (ptrdiff_type_node) >= 32)
3781	|| (TYPE_OVERFLOW_UNDEFINED (reduction_var_type)
3782	&& reduction_var_overflows_first (reduction_var_type, load_type))))
3783	generate_strlen_builtin_using_rawmemchr (loop, reduction_var,
3784	base: load_iv.base,
3785	load_type,
3786	start_len: reduction_iv.base, loc);
3787	else
3788	return false;
3789	return true;
3790	}
3791
3792	return false;
3793	}
3794
3795	/* Given innermost LOOP, return the outermost enclosing loop that forms a
3796	perfect loop nest. */
3797
3798	static class loop *
3799	prepare_perfect_loop_nest (class loop *loop)
3800	{
3801	class loop *outer = loop_outer (loop);
3802	tree niters = number_of_latch_executions (loop);
3803
3804	/* TODO: We only support the innermost 3-level loop nest distribution
3805	because of compilation time issue for now. This should be relaxed
3806	in the future. Note we only allow 3-level loop nest distribution
3807	when parallelizing loops. */
3808	while ((loop->inner == NULL
3809	|| (loop->inner->inner == NULL && flag_tree_parallelize_loops > 1))
3810	&& loop_outer (loop: outer)
3811	&& outer->inner == loop && loop->next == NULL
3812	&& single_exit (outer)
3813	&& !chrec_contains_symbols_defined_in_loop (niters, outer->num)
3814	&& (niters = number_of_latch_executions (outer)) != NULL_TREE
3815	&& niters != chrec_dont_know)
3816	{
3817	loop = outer;
3818	outer = loop_outer (loop);
3819	}
3820
3821	return loop;
3822	}
3823
3824
3825	unsigned int
3826	loop_distribution::execute (function *fun)
3827	{
3828	bool changed = false;
3829	basic_block bb;
3830	control_dependences *cd = NULL;
3831	auto_vec<loop_p> loops_to_be_destroyed;
3832
3833	if (number_of_loops (fn: fun) <= 1)
3834	return 0;
3835
3836	bb_top_order_init ();
3837
3838	FOR_ALL_BB_FN (bb, fun)
3839	{
3840	gimple_stmt_iterator gsi;
3841	for (gsi = gsi_start_phis (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
3842	gimple_set_uid (g: gsi_stmt (i: gsi), uid: -1);
3843	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
3844	gimple_set_uid (g: gsi_stmt (i: gsi), uid: -1);
3845	}
3846
3847	/* We can at the moment only distribute non-nested loops, thus restrict
3848	walking to innermost loops. */
3849	for (auto loop : loops_list (cfun, LI_ONLY_INNERMOST))
3850	{
3851	/* Don't distribute multiple exit edges loop, or cold loop when
3852	not doing pattern detection. */
3853	if (!single_exit (loop)
3854	|| (!flag_tree_loop_distribute_patterns
3855	&& !optimize_loop_for_speed_p (loop)))
3856	continue;
3857
3858	/* If niters is unknown don't distribute loop but rather try to transform
3859	it to a call to a builtin. */
3860	tree niters = number_of_latch_executions (loop);
3861	if (niters == NULL_TREE || niters == chrec_dont_know)
3862	{
3863	datarefs_vec.create (nelems: 20);
3864	if (flag_tree_loop_distribute_patterns
3865	&& transform_reduction_loop (loop))
3866	{
3867	changed = true;
3868	loops_to_be_destroyed.safe_push (obj: loop);
3869	if (dump_enabled_p ())
3870	{
3871	dump_user_location_t loc = find_loop_location (loop);
3872	dump_printf_loc (MSG_OPTIMIZED_LOCATIONS,
3873	loc, "Loop %d transformed into a builtin.\n",
3874	loop->num);
3875	}
3876	}
3877	free_data_refs (datarefs_vec);
3878	continue;
3879	}
3880
3881	/* Get the perfect loop nest for distribution. */
3882	loop = prepare_perfect_loop_nest (loop);
3883	for (; loop; loop = loop->inner)
3884	{
3885	auto_vec<gimple *> work_list;
3886	if (!find_seed_stmts_for_distribution (loop, work_list: &work_list))
3887	continue;
3888
3889	const char *str = loop->inner ? " nest" : "";
3890	dump_user_location_t loc = find_loop_location (loop);
3891	if (!cd)
3892	{
3893	calculate_dominance_info (CDI_DOMINATORS);
3894	calculate_dominance_info (CDI_POST_DOMINATORS);
3895	cd = new control_dependences ();
3896	free_dominance_info (CDI_POST_DOMINATORS);
3897	}
3898
3899	bool destroy_p;
3900	int nb_generated_loops, nb_generated_calls;
3901	bool only_patterns = !optimize_loop_for_speed_p (loop)
3902	|| !flag_tree_loop_distribution;
3903	/* do not try to distribute loops that are not expected to iterate. */
3904	if (!only_patterns)
3905	{
3906	HOST_WIDE_INT iterations = estimated_loop_iterations_int (loop);
3907	if (iterations < 0)
3908	iterations = likely_max_loop_iterations_int (loop);
3909	if (!iterations)
3910	only_patterns = true;
3911	}
3912	nb_generated_loops
3913	= distribute_loop (loop, stmts: work_list, cd, nb_calls: &nb_generated_calls,
3914	destroy_p: &destroy_p, only_patterns_p: only_patterns);
3915	if (destroy_p)
3916	loops_to_be_destroyed.safe_push (obj: loop);
3917
3918	if (nb_generated_loops + nb_generated_calls > 0)
3919	{
3920	changed = true;
3921	if (dump_enabled_p ())
3922	dump_printf_loc (MSG_OPTIMIZED_LOCATIONS,
3923	loc, "Loop%s %d distributed: split to %d loops "
3924	"and %d library calls.\n", str, loop->num,
3925	nb_generated_loops, nb_generated_calls);
3926
3927	break;
3928	}
3929
3930	if (dump_file && (dump_flags & TDF_DETAILS))
3931	fprintf (stream: dump_file, format: "Loop%s %d not distributed.\n", str, loop->num);
3932	}
3933	}
3934
3935	if (cd)
3936	delete cd;
3937
3938	if (bb_top_order_index != NULL)
3939	bb_top_order_destroy ();
3940
3941	if (changed)
3942	{
3943	/* Destroy loop bodies that could not be reused. Do this late as we
3944	otherwise can end up refering to stale data in control dependences. */
3945	unsigned i;
3946	class loop *loop;
3947	FOR_EACH_VEC_ELT (loops_to_be_destroyed, i, loop)
3948	destroy_loop (loop);
3949
3950	/* Cached scalar evolutions now may refer to wrong or non-existing
3951	loops. */
3952	scev_reset ();
3953	mark_virtual_operands_for_renaming (fun);
3954	rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
3955	}
3956
3957	checking_verify_loop_structure ();
3958
3959	return changed ? TODO_cleanup_cfg : 0;
3960	}
3961
3962
3963	/* Distribute all loops in the current function. */
3964
3965	namespace {
3966
3967	const pass_data pass_data_loop_distribution =
3968	{
3969	.type: GIMPLE_PASS, /* type */
3970	.name: "ldist", /* name */
3971	.optinfo_flags: OPTGROUP_LOOP, /* optinfo_flags */
3972	.tv_id: TV_TREE_LOOP_DISTRIBUTION, /* tv_id */
3973	.properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */
3974	.properties_provided: 0, /* properties_provided */
3975	.properties_destroyed: 0, /* properties_destroyed */
3976	.todo_flags_start: 0, /* todo_flags_start */
3977	.todo_flags_finish: 0, /* todo_flags_finish */
3978	};
3979
3980	class pass_loop_distribution : public gimple_opt_pass
3981	{
3982	public:
3983	pass_loop_distribution (gcc::context *ctxt)
3984	: gimple_opt_pass (pass_data_loop_distribution, ctxt)
3985	{}
3986
3987	/* opt_pass methods: */
3988	bool gate (function *) final override
3989	{
3990	return flag_tree_loop_distribution
3991	|| flag_tree_loop_distribute_patterns;
3992	}
3993
3994	unsigned int execute (function *) final override;
3995
3996	}; // class pass_loop_distribution
3997
3998	unsigned int
3999	pass_loop_distribution::execute (function *fun)
4000	{
4001	return loop_distribution ().execute (fun);
4002	}
4003
4004	} // anon namespace
4005
4006	gimple_opt_pass *
4007	make_pass_loop_distribution (gcc::context *ctxt)
4008	{
4009	return new pass_loop_distribution (ctxt);
4010	}
4011