1	/* Induction variable canonicalization and loop peeling.
2	Copyright (C) 2004-2023 Free Software Foundation, Inc.
3
4	This file is part of GCC.
5
6	GCC is free software; you can redistribute it and/or modify it
7	under the terms of the GNU General Public License as published by the
8	Free Software Foundation; either version 3, or (at your option) any
9	later version.
10
11	GCC is distributed in the hope that it will be useful, but WITHOUT
12	ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14	for more details.
15
16	You should have received a copy of the GNU General Public License
17	along with GCC; see the file COPYING3. If not see
18	<http://www.gnu.org/licenses/>. */
19
20	/* This pass detects the loops that iterate a constant number of times,
21	adds a canonical induction variable (step -1, tested against 0)
22	and replaces the exit test. This enables the less powerful rtl
23	level analysis to use this information.
24
25	This might spoil the code in some cases (by increasing register pressure).
26	Note that in the case the new variable is not needed, ivopts will get rid
27	of it, so it might only be a problem when there are no other linear induction
28	variables. In that case the created optimization possibilities are likely
29	to pay up.
30
31	We also perform
32	- complete unrolling (or peeling) when the loops is rolling few enough
33	times
34	- simple peeling (i.e. copying few initial iterations prior the loop)
35	when number of iteration estimate is known (typically by the profile
36	info). */
37
38	#include "config.h"
39	#include "system.h"
40	#include "coretypes.h"
41	#include "backend.h"
42	#include "tree.h"
43	#include "gimple.h"
44	#include "cfghooks.h"
45	#include "tree-pass.h"
46	#include "ssa.h"
47	#include "cgraph.h"
48	#include "gimple-pretty-print.h"
49	#include "fold-const.h"
50	#include "profile.h"
51	#include "gimple-iterator.h"
52	#include "gimple-fold.h"
53	#include "tree-eh.h"
54	#include "tree-cfg.h"
55	#include "tree-ssa-loop-manip.h"
56	#include "tree-ssa-loop-niter.h"
57	#include "tree-ssa-loop.h"
58	#include "tree-into-ssa.h"
59	#include "cfgloop.h"
60	#include "tree-chrec.h"
61	#include "tree-scalar-evolution.h"
62	#include "tree-inline.h"
63	#include "tree-cfgcleanup.h"
64	#include "builtins.h"
65	#include "tree-ssa-sccvn.h"
66	#include "tree-vectorizer.h" /* For find_loop_location */
67	#include "dbgcnt.h"
68
69	/* Specifies types of loops that may be unrolled. */
70
71	enum unroll_level
72	{
73	UL_SINGLE_ITER, /* Only loops that exit immediately in the first
74	iteration. */
75	UL_NO_GROWTH, /* Only loops whose unrolling will not cause increase
76	of code size. */
77	UL_ALL /* All suitable loops. */
78	};
79
80	/* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
81	is the exit edge whose condition is replaced. The ssa versions of the new
82	IV before and after increment will be stored in VAR_BEFORE and VAR_AFTER
83	if they are not NULL. */
84
85	void
86	create_canonical_iv (class loop *loop, edge exit, tree niter,
87	tree *var_before = NULL, tree *var_after = NULL)
88	{
89	edge in;
90	tree type, var;
91	gcond *cond;
92	gimple_stmt_iterator incr_at;
93	enum tree_code cmp;
94
95	if (dump_file && (dump_flags & TDF_DETAILS))
96	{
97	fprintf (stream: dump_file, format: "Added canonical iv to loop %d, ", loop->num);
98	print_generic_expr (dump_file, niter, TDF_SLIM);
99	fprintf (stream: dump_file, format: " iterations.\n");
100	}
101
102	cond = as_a <gcond *> (p: *gsi_last_bb (bb: exit->src));
103	in = EDGE_SUCC (exit->src, 0);
104	if (in == exit)
105	in = EDGE_SUCC (exit->src, 1);
106
107	/* Note that we do not need to worry about overflows, since
108	type of niter is always unsigned and all comparisons are
109	just for equality/nonequality -- i.e. everything works
110	with a modulo arithmetics. */
111
112	type = TREE_TYPE (niter);
113	niter = fold_build2 (PLUS_EXPR, type,
114	niter,
115	build_int_cst (type, 1));
116	incr_at = gsi_last_bb (bb: in->src);
117	create_iv (niter, PLUS_EXPR,
118	build_int_cst (type, -1),
119	NULL_TREE, loop,
120	&incr_at, false, var_before, &var);
121	if (var_after)
122	*var_after = var;
123
124	cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
125	gimple_cond_set_code (gs: cond, code: cmp);
126	gimple_cond_set_lhs (gs: cond, lhs: var);
127	gimple_cond_set_rhs (gs: cond, rhs: build_int_cst (type, 0));
128	update_stmt (s: cond);
129	}
130
131	/* Describe size of loop as detected by tree_estimate_loop_size. */
132	struct loop_size
133	{
134	/* Number of instructions in the loop. */
135	int overall;
136
137	/* Number of instructions that will be likely optimized out in
138	peeled iterations of loop (i.e. computation based on induction
139	variable where induction variable starts at known constant.) */
140	int eliminated_by_peeling;
141
142	/* Same statistics for last iteration of loop: it is smaller because
143	instructions after exit are not executed. */
144	int last_iteration;
145	int last_iteration_eliminated_by_peeling;
146
147	/* If some IV computation will become constant. */
148	bool constant_iv;
149
150	/* Number of call stmts that are not a builtin and are pure or const
151	present on the hot path. */
152	int num_pure_calls_on_hot_path;
153	/* Number of call stmts that are not a builtin and are not pure nor const
154	present on the hot path. */
155	int num_non_pure_calls_on_hot_path;
156	/* Number of statements other than calls in the loop. */
157	int non_call_stmts_on_hot_path;
158	/* Number of branches seen on the hot path. */
159	int num_branches_on_hot_path;
160	};
161
162	/* Return true if OP in STMT will be constant after peeling LOOP. */
163
164	static bool
165	constant_after_peeling (tree op, gimple *stmt, class loop *loop)
166	{
167	if (CONSTANT_CLASS_P (op))
168	return true;
169
170	/* Get at the actual SSA operand. */
171	if (handled_component_p (t: op)
172	&& TREE_CODE (TREE_OPERAND (op, 0)) == SSA_NAME)
173	op = TREE_OPERAND (op, 0);
174
175	/* We can still fold accesses to constant arrays when index is known. */
176	if (TREE_CODE (op) != SSA_NAME)
177	{
178	tree base = op;
179
180	/* First make fast look if we see constant array inside. */
181	while (handled_component_p (t: base))
182	base = TREE_OPERAND (base, 0);
183	if ((DECL_P (base)
184	&& ctor_for_folding (base) != error_mark_node)
185	|| CONSTANT_CLASS_P (base))
186	{
187	/* If so, see if we understand all the indices. */
188	base = op;
189	while (handled_component_p (t: base))
190	{
191	if (TREE_CODE (base) == ARRAY_REF
192	&& !constant_after_peeling (TREE_OPERAND (base, 1), stmt, loop))
193	return false;
194	base = TREE_OPERAND (base, 0);
195	}
196	return true;
197	}
198	return false;
199	}
200
201	/* Induction variables are constants when defined in loop. */
202	if (loop_containing_stmt (stmt) != loop)
203	return false;
204	tree ev = analyze_scalar_evolution (loop, op);
205	if (chrec_contains_undetermined (ev)
206	|| chrec_contains_symbols (ev))
207	{
208	if (ANY_INTEGRAL_TYPE_P (TREE_TYPE (op)))
209	{
210	gassign *ass = nullptr;
211	gphi *phi = nullptr;
212	if (is_a <gassign *> (SSA_NAME_DEF_STMT (op)))
213	{
214	ass = as_a <gassign *> (SSA_NAME_DEF_STMT (op));
215	if (TREE_CODE (gimple_assign_rhs1 (ass)) == SSA_NAME)
216	phi = dyn_cast <gphi *>
217	(SSA_NAME_DEF_STMT (gimple_assign_rhs1 (ass)));
218	}
219	else if (is_a <gphi *> (SSA_NAME_DEF_STMT (op)))
220	{
221	phi = as_a <gphi *> (SSA_NAME_DEF_STMT (op));
222	if (gimple_bb (g: phi) == loop->header)
223	{
224	tree def = gimple_phi_arg_def_from_edge
225	(gs: phi, e: loop_latch_edge (loop));
226	if (TREE_CODE (def) == SSA_NAME
227	&& is_a <gassign *> (SSA_NAME_DEF_STMT (def)))
228	ass = as_a <gassign *> (SSA_NAME_DEF_STMT (def));
229	}
230	}
231	if (ass && phi)
232	{
233	tree rhs1 = gimple_assign_rhs1 (gs: ass);
234	if (gimple_assign_rhs_class (gs: ass) == GIMPLE_BINARY_RHS
235	&& CONSTANT_CLASS_P (gimple_assign_rhs2 (ass))
236	&& rhs1 == gimple_phi_result (gs: phi)
237	&& gimple_bb (g: phi) == loop->header
238	&& (gimple_phi_arg_def_from_edge (gs: phi, e: loop_latch_edge (loop))
239	== gimple_assign_lhs (gs: ass))
240	&& (CONSTANT_CLASS_P (gimple_phi_arg_def_from_edge
241	(phi, loop_preheader_edge (loop)))))
242	return true;
243	}
244	}
245	return false;
246	}
247	return true;
248	}
249
250	/* Computes an estimated number of insns in LOOP.
251	EXIT (if non-NULL) is an exite edge that will be eliminated in all but last
252	iteration of the loop.
253	EDGE_TO_CANCEL (if non-NULL) is an non-exit edge eliminated in the last iteration
254	of loop.
255	Return results in SIZE, estimate benefits for complete unrolling exiting by EXIT.
256	Stop estimating after UPPER_BOUND is met. Return true in this case. */
257
258	static bool
259	tree_estimate_loop_size (class loop *loop, edge exit, edge edge_to_cancel,
260	struct loop_size *size, int upper_bound)
261	{
262	basic_block *body = get_loop_body (loop);
263	gimple_stmt_iterator gsi;
264	unsigned int i;
265	bool after_exit;
266	auto_vec<basic_block> path = get_loop_hot_path (loop);
267
268	size->overall = 0;
269	size->eliminated_by_peeling = 0;
270	size->last_iteration = 0;
271	size->last_iteration_eliminated_by_peeling = 0;
272	size->num_pure_calls_on_hot_path = 0;
273	size->num_non_pure_calls_on_hot_path = 0;
274	size->non_call_stmts_on_hot_path = 0;
275	size->num_branches_on_hot_path = 0;
276	size->constant_iv = 0;
277
278	if (dump_file && (dump_flags & TDF_DETAILS))
279	fprintf (stream: dump_file, format: "Estimating sizes for loop %i\n", loop->num);
280	for (i = 0; i < loop->num_nodes; i++)
281	{
282	if (edge_to_cancel && body[i] != edge_to_cancel->src
283	&& dominated_by_p (CDI_DOMINATORS, body[i], edge_to_cancel->src))
284	after_exit = true;
285	else
286	after_exit = false;
287	if (dump_file && (dump_flags & TDF_DETAILS))
288	fprintf (stream: dump_file, format: " BB: %i, after_exit: %i\n", body[i]->index,
289	after_exit);
290
291	for (gsi = gsi_start_bb (bb: body[i]); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
292	{
293	gimple *stmt = gsi_stmt (i: gsi);
294	int num = estimate_num_insns (stmt, &eni_size_weights);
295	bool likely_eliminated = false;
296	bool likely_eliminated_last = false;
297	bool likely_eliminated_peeled = false;
298
299	if (dump_file && (dump_flags & TDF_DETAILS))
300	{
301	fprintf (stream: dump_file, format: " size: %3i ", num);
302	print_gimple_stmt (dump_file, gsi_stmt (i: gsi), 0);
303	}
304
305	/* Look for reasons why we might optimize this stmt away. */
306
307	if (!gimple_has_side_effects (stmt))
308	{
309	/* Exit conditional. */
310	if (exit && body[i] == exit->src
311	&& stmt == *gsi_last_bb (bb: exit->src))
312	{
313	if (dump_file && (dump_flags & TDF_DETAILS))
314	fprintf (stream: dump_file, format: " Exit condition will be eliminated "
315	"in peeled copies.\n");
316	likely_eliminated_peeled = true;
317	}
318	if (edge_to_cancel && body[i] == edge_to_cancel->src
319	&& stmt == *gsi_last_bb (bb: edge_to_cancel->src))
320	{
321	if (dump_file && (dump_flags & TDF_DETAILS))
322	fprintf (stream: dump_file, format: " Exit condition will be eliminated "
323	"in last copy.\n");
324	likely_eliminated_last = true;
325	}
326	/* Sets of IV variables */
327	if (gimple_code (g: stmt) == GIMPLE_ASSIGN
328	&& constant_after_peeling (op: gimple_assign_lhs (gs: stmt), stmt, loop))
329	{
330	if (dump_file && (dump_flags & TDF_DETAILS))
331	fprintf (stream: dump_file, format: " Induction variable computation will"
332	" be folded away.\n");
333	likely_eliminated = true;
334	}
335	/* Assignments of IV variables. */
336	else if (gimple_code (g: stmt) == GIMPLE_ASSIGN
337	&& TREE_CODE (gimple_assign_lhs (stmt)) == SSA_NAME
338	&& constant_after_peeling (op: gimple_assign_rhs1 (gs: stmt),
339	stmt, loop)
340	&& (gimple_assign_rhs_class (gs: stmt) != GIMPLE_BINARY_RHS
341	|| constant_after_peeling (op: gimple_assign_rhs2 (gs: stmt),
342	stmt, loop))
343	&& gimple_assign_rhs_class (gs: stmt) != GIMPLE_TERNARY_RHS)
344	{
345	size->constant_iv = true;
346	if (dump_file && (dump_flags & TDF_DETAILS))
347	fprintf (stream: dump_file,
348	format: " Constant expression will be folded away.\n");
349	likely_eliminated = true;
350	}
351	/* Conditionals. */
352	else if ((gimple_code (g: stmt) == GIMPLE_COND
353	&& constant_after_peeling (op: gimple_cond_lhs (gs: stmt), stmt,
354	loop)
355	&& constant_after_peeling (op: gimple_cond_rhs (gs: stmt), stmt,
356	loop)
357	/* We don't simplify all constant compares so make sure
358	they are not both constant already. See PR70288. */
359	&& (! is_gimple_min_invariant (gimple_cond_lhs (gs: stmt))
360	|| ! is_gimple_min_invariant
361	(gimple_cond_rhs (gs: stmt))))
362	|| (gimple_code (g: stmt) == GIMPLE_SWITCH
363	&& constant_after_peeling (op: gimple_switch_index (
364	gs: as_a <gswitch *>
365	(p: stmt)),
366	stmt, loop)
367	&& ! is_gimple_min_invariant
368	(gimple_switch_index
369	(gs: as_a <gswitch *> (p: stmt)))))
370	{
371	if (dump_file && (dump_flags & TDF_DETAILS))
372	fprintf (stream: dump_file, format: " Constant conditional.\n");
373	likely_eliminated = true;
374	}
375	}
376
377	size->overall += num;
378	if (likely_eliminated || likely_eliminated_peeled)
379	size->eliminated_by_peeling += num;
380	if (!after_exit)
381	{
382	size->last_iteration += num;
383	if (likely_eliminated || likely_eliminated_last)
384	size->last_iteration_eliminated_by_peeling += num;
385	}
386	if ((size->overall * 3 / 2 - size->eliminated_by_peeling
387	- size->last_iteration_eliminated_by_peeling) > upper_bound)
388	{
389	free (ptr: body);
390	return true;
391	}
392	}
393	}
394	while (path.length ())
395	{
396	basic_block bb = path.pop ();
397	for (gsi = gsi_start_bb (bb); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
398	{
399	gimple *stmt = gsi_stmt (i: gsi);
400	if (gimple_code (g: stmt) == GIMPLE_CALL
401	&& !gimple_inexpensive_call_p (as_a <gcall *> (p: stmt)))
402	{
403	int flags = gimple_call_flags (stmt);
404	if (flags & (ECF_PURE | ECF_CONST))
405	size->num_pure_calls_on_hot_path++;
406	else
407	size->num_non_pure_calls_on_hot_path++;
408	size->num_branches_on_hot_path ++;
409	}
410	/* Count inexpensive calls as non-calls, because they will likely
411	expand inline. */
412	else if (gimple_code (g: stmt) != GIMPLE_DEBUG)
413	size->non_call_stmts_on_hot_path++;
414	if (((gimple_code (g: stmt) == GIMPLE_COND
415	&& (!constant_after_peeling (op: gimple_cond_lhs (gs: stmt), stmt, loop)
416	|| !constant_after_peeling (op: gimple_cond_rhs (gs: stmt), stmt,
417	loop)))
418	|| (gimple_code (g: stmt) == GIMPLE_SWITCH
419	&& !constant_after_peeling (op: gimple_switch_index (
420	gs: as_a <gswitch *> (p: stmt)),
421	stmt, loop)))
422	&& (!exit || bb != exit->src))
423	size->num_branches_on_hot_path++;
424	}
425	}
426
427	if (dump_file && (dump_flags & TDF_DETAILS))
428	fprintf (stream: dump_file, format: "size: %i-%i, last_iteration: %i-%i\n", size->overall,
429	size->eliminated_by_peeling, size->last_iteration,
430	size->last_iteration_eliminated_by_peeling);
431
432	free (ptr: body);
433	return false;
434	}
435
436	/* Estimate number of insns of completely unrolled loop.
437	It is (NUNROLL + 1) * size of loop body with taking into account
438	the fact that in last copy everything after exit conditional
439	is dead and that some instructions will be eliminated after
440	peeling.
441
442	Loop body is likely going to simplify further, this is difficult
443	to guess, we just decrease the result by 1/3. */
444
445	static unsigned HOST_WIDE_INT
446	estimated_unrolled_size (struct loop_size *size,
447	unsigned HOST_WIDE_INT nunroll)
448	{
449	HOST_WIDE_INT unr_insns = ((nunroll)
450	* (HOST_WIDE_INT) (size->overall
451	- size->eliminated_by_peeling));
452	if (!nunroll)
453	unr_insns = 0;
454	unr_insns += size->last_iteration - size->last_iteration_eliminated_by_peeling;
455
456	unr_insns = unr_insns * 2 / 3;
457	if (unr_insns <= 0)
458	unr_insns = 1;
459
460	return unr_insns;
461	}
462
463	/* Loop LOOP is known to not loop. See if there is an edge in the loop
464	body that can be remove to make the loop to always exit and at
465	the same time it does not make any code potentially executed
466	during the last iteration dead.
467
468	After complete unrolling we still may get rid of the conditional
469	on the exit in the last copy even if we have no idea what it does.
470	This is quite common case for loops of form
471
472	int a[5];
473	for (i=0;i<b;i++)
474	a[i]=0;
475
476	Here we prove the loop to iterate 5 times but we do not know
477	it from induction variable.
478
479	For now we handle only simple case where there is exit condition
480	just before the latch block and the latch block contains no statements
481	with side effect that may otherwise terminate the execution of loop
482	(such as by EH or by terminating the program or longjmp).
483
484	In the general case we may want to cancel the paths leading to statements
485	loop-niter identified as having undefined effect in the last iteration.
486	The other cases are hopefully rare and will be cleaned up later. */
487
488	static edge
489	loop_edge_to_cancel (class loop *loop)
490	{
491	unsigned i;
492	edge edge_to_cancel;
493	gimple_stmt_iterator gsi;
494
495	/* We want only one predecestor of the loop. */
496	if (EDGE_COUNT (loop->latch->preds) > 1)
497	return NULL;
498
499	auto_vec<edge> exits = get_loop_exit_edges (loop);
500
501	FOR_EACH_VEC_ELT (exits, i, edge_to_cancel)
502	{
503	/* Find the other edge than the loop exit
504	leaving the conditoinal. */
505	if (EDGE_COUNT (edge_to_cancel->src->succs) != 2)
506	continue;
507	if (EDGE_SUCC (edge_to_cancel->src, 0) == edge_to_cancel)
508	edge_to_cancel = EDGE_SUCC (edge_to_cancel->src, 1);
509	else
510	edge_to_cancel = EDGE_SUCC (edge_to_cancel->src, 0);
511
512	/* We only can handle conditionals. */
513	if (!(edge_to_cancel->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
514	continue;
515
516	/* We should never have conditionals in the loop latch. */
517	gcc_assert (edge_to_cancel->dest != loop->header);
518
519	/* Check that it leads to loop latch. */
520	if (edge_to_cancel->dest != loop->latch)
521	continue;
522
523	/* Verify that the code in loop latch does nothing that may end program
524	execution without really reaching the exit. This may include
525	non-pure/const function calls, EH statements, volatile ASMs etc. */
526	for (gsi = gsi_start_bb (bb: loop->latch); !gsi_end_p (i: gsi); gsi_next (i: &gsi))
527	if (gimple_has_side_effects (gsi_stmt (i: gsi)))
528	return NULL;
529	return edge_to_cancel;
530	}
531	return NULL;
532	}
533
534	/* Remove all tests for exits that are known to be taken after LOOP was
535	peeled NPEELED times. Put gcc_unreachable before every statement
536	known to not be executed. */
537
538	static bool
539	remove_exits_and_undefined_stmts (class loop *loop, unsigned int npeeled)
540	{
541	class nb_iter_bound *elt;
542	bool changed = false;
543
544	for (elt = loop->bounds; elt; elt = elt->next)
545	{
546	/* If statement is known to be undefined after peeling, turn it
547	into unreachable (or trap when debugging experience is supposed
548	to be good). */
549	if (!elt->is_exit
550	&& wi::ltu_p (x: elt->bound, y: npeeled))
551	{
552	gimple_stmt_iterator gsi = gsi_for_stmt (elt->stmt);
553	location_t loc = gimple_location (g: elt->stmt);
554	gcall *stmt = gimple_build_builtin_unreachable (loc);
555	gsi_insert_before (&gsi, stmt, GSI_NEW_STMT);
556	split_block (gimple_bb (g: stmt), stmt);
557	changed = true;
558	if (dump_file && (dump_flags & TDF_DETAILS))
559	{
560	fprintf (stream: dump_file, format: "Forced statement unreachable: ");
561	print_gimple_stmt (dump_file, elt->stmt, 0);
562	}
563	}
564	/* If we know the exit will be taken after peeling, update. */
565	else if (elt->is_exit
566	&& wi::leu_p (x: elt->bound, y: npeeled))
567	{
568	basic_block bb = gimple_bb (g: elt->stmt);
569	edge exit_edge = EDGE_SUCC (bb, 0);
570
571	if (dump_file && (dump_flags & TDF_DETAILS))
572	{
573	fprintf (stream: dump_file, format: "Forced exit to be taken: ");
574	print_gimple_stmt (dump_file, elt->stmt, 0);
575	}
576	if (!loop_exit_edge_p (loop, exit_edge))
577	exit_edge = EDGE_SUCC (bb, 1);
578	exit_edge->probability = profile_probability::always ();
579	gcc_checking_assert (loop_exit_edge_p (loop, exit_edge));
580	gcond *cond_stmt = as_a <gcond *> (p: elt->stmt);
581	if (exit_edge->flags & EDGE_TRUE_VALUE)
582	gimple_cond_make_true (gs: cond_stmt);
583	else
584	gimple_cond_make_false (gs: cond_stmt);
585	update_stmt (s: cond_stmt);
586	changed = true;
587	}
588	}
589	return changed;
590	}
591
592	/* Remove all exits that are known to be never taken because of the loop bound
593	discovered. */
594
595	static bool
596	remove_redundant_iv_tests (class loop *loop)
597	{
598	class nb_iter_bound *elt;
599	bool changed = false;
600
601	if (!loop->any_upper_bound)
602	return false;
603	for (elt = loop->bounds; elt; elt = elt->next)
604	{
605	/* Exit is pointless if it won't be taken before loop reaches
606	upper bound. */
607	if (elt->is_exit && loop->any_upper_bound
608	&& wi::ltu_p (x: loop->nb_iterations_upper_bound, y: elt->bound))
609	{
610	basic_block bb = gimple_bb (g: elt->stmt);
611	edge exit_edge = EDGE_SUCC (bb, 0);
612	class tree_niter_desc niter;
613
614	if (!loop_exit_edge_p (loop, exit_edge))
615	exit_edge = EDGE_SUCC (bb, 1);
616
617	/* Only when we know the actual number of iterations, not
618	just a bound, we can remove the exit. */
619	if (!number_of_iterations_exit (loop, exit_edge,
620	niter: &niter, false, every_iteration: false)
621	|| !integer_onep (niter.assumptions)
622	|| !integer_zerop (niter.may_be_zero)
623	|| !niter.niter
624	|| TREE_CODE (niter.niter) != INTEGER_CST
625	|| !wi::ltu_p (x: widest_int::from (x: loop->nb_iterations_upper_bound,
626	sgn: SIGNED),
627	y: wi::to_widest (t: niter.niter)))
628	continue;
629
630	if (dump_file && (dump_flags & TDF_DETAILS))
631	{
632	fprintf (stream: dump_file, format: "Removed pointless exit: ");
633	print_gimple_stmt (dump_file, elt->stmt, 0);
634	}
635	gcond *cond_stmt = as_a <gcond *> (p: elt->stmt);
636	if (exit_edge->flags & EDGE_TRUE_VALUE)
637	gimple_cond_make_false (gs: cond_stmt);
638	else
639	gimple_cond_make_true (gs: cond_stmt);
640	update_stmt (s: cond_stmt);
641	changed = true;
642	}
643	}
644	return changed;
645	}
646
647	/* Stores loops that will be unlooped and edges that will be removed
648	after we process whole loop tree. */
649	static vec<loop_p> loops_to_unloop;
650	static vec<int> loops_to_unloop_nunroll;
651	static vec<edge> edges_to_remove;
652	/* Stores loops that has been peeled. */
653	static bitmap peeled_loops;
654
655	/* Cancel all fully unrolled loops by putting __builtin_unreachable
656	on the latch edge.
657	We do it after all unrolling since unlooping moves basic blocks
658	across loop boundaries trashing loop closed SSA form as well
659	as SCEV info needed to be intact during unrolling.
660
661	IRRED_INVALIDATED is used to bookkeep if information about
662	irreducible regions may become invalid as a result
663	of the transformation.
664	LOOP_CLOSED_SSA_INVALIDATED is used to bookkepp the case
665	when we need to go into loop closed SSA form. */
666
667	void
668	unloop_loops (vec<class loop *> &loops_to_unloop,
669	vec<int> &loops_to_unloop_nunroll,
670	bitmap loop_closed_ssa_invalidated,
671	bool *irred_invalidated)
672	{
673	while (loops_to_unloop.length ())
674	{
675	class loop *loop = loops_to_unloop.pop ();
676	int n_unroll = loops_to_unloop_nunroll.pop ();
677	basic_block latch = loop->latch;
678	edge latch_edge = loop_latch_edge (loop);
679	int flags = latch_edge->flags;
680	location_t locus = latch_edge->goto_locus;
681	gcall *stmt;
682	gimple_stmt_iterator gsi;
683
684	remove_exits_and_undefined_stmts (loop, npeeled: n_unroll);
685
686	/* Unloop destroys the latch edge. */
687	unloop (loop, irred_invalidated, loop_closed_ssa_invalidated);
688
689	/* Create new basic block for the latch edge destination and wire
690	it in. */
691	stmt = gimple_build_builtin_unreachable (locus);
692	latch_edge = make_edge (latch, create_basic_block (NULL, NULL, latch), flags);
693	latch_edge->probability = profile_probability::never ();
694	latch_edge->flags |= flags;
695	latch_edge->goto_locus = locus;
696
697	add_bb_to_loop (latch_edge->dest, current_loops->tree_root);
698	latch_edge->dest->count = profile_count::zero ();
699	set_immediate_dominator (CDI_DOMINATORS, latch_edge->dest, latch_edge->src);
700
701	gsi = gsi_start_bb (bb: latch_edge->dest);
702	gsi_insert_after (&gsi, stmt, GSI_NEW_STMT);
703	}
704
705	/* Remove edges in peeled copies. Given remove_path removes dominated
706	regions we need to cope with removal of already removed paths. */
707	unsigned i;
708	edge e;
709	auto_vec<int, 20> src_bbs;
710	src_bbs.reserve_exact (nelems: edges_to_remove.length ());
711	FOR_EACH_VEC_ELT (edges_to_remove, i, e)
712	src_bbs.quick_push (obj: e->src->index);
713	FOR_EACH_VEC_ELT (edges_to_remove, i, e)
714	if (BASIC_BLOCK_FOR_FN (cfun, src_bbs[i]))
715	{
716	bool ok = remove_path (e, irred_invalidated,
717	loop_closed_ssa_invalidated);
718	gcc_assert (ok);
719	}
720	edges_to_remove.release ();
721	}
722
723	/* Tries to unroll LOOP completely, i.e. NITER times.
724	UL determines which loops we are allowed to unroll.
725	EXIT is the exit of the loop that should be eliminated.
726	MAXITER specfy bound on number of iterations, -1 if it is
727	not known or too large for HOST_WIDE_INT. The location
728	LOCUS corresponding to the loop is used when emitting
729	a summary of the unroll to the dump file. */
730
731	static bool
732	try_unroll_loop_completely (class loop *loop,
733	edge exit, tree niter, bool may_be_zero,
734	enum unroll_level ul,
735	HOST_WIDE_INT maxiter,
736	dump_user_location_t locus, bool allow_peel)
737	{
738	unsigned HOST_WIDE_INT n_unroll = 0;
739	bool n_unroll_found = false;
740	edge edge_to_cancel = NULL;
741
742	/* See if we proved number of iterations to be low constant.
743
744	EXIT is an edge that will be removed in all but last iteration of
745	the loop.
746
747	EDGE_TO_CACNEL is an edge that will be removed from the last iteration
748	of the unrolled sequence and is expected to make the final loop not
749	rolling.
750
751	If the number of execution of loop is determined by standard induction
752	variable test, then EXIT and EDGE_TO_CANCEL are the two edges leaving
753	from the iv test. */
754	if (tree_fits_uhwi_p (niter))
755	{
756	n_unroll = tree_to_uhwi (niter);
757	n_unroll_found = true;
758	edge_to_cancel = EDGE_SUCC (exit->src, 0);
759	if (edge_to_cancel == exit)
760	edge_to_cancel = EDGE_SUCC (exit->src, 1);
761	}
762	/* We do not know the number of iterations and thus we cannot eliminate
763	the EXIT edge. */
764	else
765	exit = NULL;
766
767	/* See if we can improve our estimate by using recorded loop bounds. */
768	if ((maxiter == 0 || ul != UL_SINGLE_ITER)
769	&& maxiter >= 0
770	&& (!n_unroll_found || (unsigned HOST_WIDE_INT)maxiter < n_unroll))
771	{
772	n_unroll = maxiter;
773	n_unroll_found = true;
774	/* Loop terminates before the IV variable test, so we cannot
775	remove it in the last iteration. */
776	edge_to_cancel = NULL;
777	/* If we do not allow peeling and we iterate just allow cases
778	that do not grow code. */
779	if (!allow_peel && maxiter != 0)
780	ul = UL_NO_GROWTH;
781	}
782
783	if (!n_unroll_found)
784	return false;
785
786	if (!loop->unroll
787	&& n_unroll > (unsigned) param_max_completely_peel_times)
788	{
789	if (dump_file && (dump_flags & TDF_DETAILS))
790	fprintf (stream: dump_file, format: "Not unrolling loop %d "
791	"(--param max-completely-peel-times limit reached).\n",
792	loop->num);
793	return false;
794	}
795
796	if (!edge_to_cancel)
797	edge_to_cancel = loop_edge_to_cancel (loop);
798
799	if (n_unroll)
800	{
801	if (ul == UL_SINGLE_ITER)
802	return false;
803
804	if (loop->unroll)
805	{
806	/* If the unrolling factor is too large, bail out. */
807	if (n_unroll > (unsigned)loop->unroll)
808	{
809	if (dump_file && (dump_flags & TDF_DETAILS))
810	fprintf (stream: dump_file,
811	format: "Not unrolling loop %d: "
812	"user didn't want it unrolled completely.\n",
813	loop->num);
814	return false;
815	}
816	}
817	else
818	{
819	struct loop_size size;
820	/* EXIT can be removed only if we are sure it passes first N_UNROLL
821	iterations. */
822	bool remove_exit = (exit && niter
823	&& TREE_CODE (niter) == INTEGER_CST
824	&& wi::leu_p (x: n_unroll, y: wi::to_widest (t: niter)));
825	bool large
826	= tree_estimate_loop_size
827	(loop, exit: remove_exit ? exit : NULL, edge_to_cancel, size: &size,
828	param_max_completely_peeled_insns);
829	if (large)
830	{
831	if (dump_file && (dump_flags & TDF_DETAILS))
832	fprintf (stream: dump_file, format: "Not unrolling loop %d: it is too large.\n",
833	loop->num);
834	return false;
835	}
836
837	unsigned HOST_WIDE_INT ninsns = size.overall;
838	unsigned HOST_WIDE_INT unr_insns
839	= estimated_unrolled_size (size: &size, nunroll: n_unroll);
840	if (dump_file && (dump_flags & TDF_DETAILS))
841	{
842	fprintf (stream: dump_file, format: " Loop size: %d\n", (int) ninsns);
843	fprintf (stream: dump_file, format: " Estimated size after unrolling: %d\n",
844	(int) unr_insns);
845	}
846
847	/* If the code is going to shrink, we don't need to be extra
848	cautious on guessing if the unrolling is going to be
849	profitable. */
850	if (unr_insns
851	/* If there is IV variable that will become constant, we
852	save one instruction in the loop prologue we do not
853	account otherwise. */
854	<= ninsns + (size.constant_iv != false))
855	;
856	/* We unroll only inner loops, because we do not consider it
857	profitable otheriwse. We still can cancel loopback edge
858	of not rolling loop; this is always a good idea. */
859	else if (ul == UL_NO_GROWTH)
860	{
861	if (dump_file && (dump_flags & TDF_DETAILS))
862	fprintf (stream: dump_file, format: "Not unrolling loop %d: size would grow.\n",
863	loop->num);
864	return false;
865	}
866	/* Outer loops tend to be less interesting candidates for
867	complete unrolling unless we can do a lot of propagation
868	into the inner loop body. For now we disable outer loop
869	unrolling when the code would grow. */
870	else if (loop->inner)
871	{
872	if (dump_file && (dump_flags & TDF_DETAILS))
873	fprintf (stream: dump_file, format: "Not unrolling loop %d: "
874	"it is not innermost and code would grow.\n",
875	loop->num);
876	return false;
877	}
878	/* If there is call on a hot path through the loop, then
879	there is most probably not much to optimize. */
880	else if (size.num_non_pure_calls_on_hot_path)
881	{
882	if (dump_file && (dump_flags & TDF_DETAILS))
883	fprintf (stream: dump_file, format: "Not unrolling loop %d: "
884	"contains call and code would grow.\n",
885	loop->num);
886	return false;
887	}
888	/* If there is pure/const call in the function, then we can
889	still optimize the unrolled loop body if it contains some
890	other interesting code than the calls and code storing or
891	cumulating the return value. */
892	else if (size.num_pure_calls_on_hot_path
893	/* One IV increment, one test, one ivtmp store and
894	one useful stmt. That is about minimal loop
895	doing pure call. */
896	&& (size.non_call_stmts_on_hot_path
897	<= 3 + size.num_pure_calls_on_hot_path))
898	{
899	if (dump_file && (dump_flags & TDF_DETAILS))
900	fprintf (stream: dump_file, format: "Not unrolling loop %d: "
901	"contains just pure calls and code would grow.\n",
902	loop->num);
903	return false;
904	}
905	/* Complete unrolling is major win when control flow is
906	removed and one big basic block is created. If the loop
907	contains control flow the optimization may still be a win
908	because of eliminating the loop overhead but it also may
909	blow the branch predictor tables. Limit number of
910	branches on the hot path through the peeled sequence. */
911	else if (size.num_branches_on_hot_path * (int)n_unroll
912	> param_max_peel_branches)
913	{
914	if (dump_file && (dump_flags & TDF_DETAILS))
915	fprintf (stream: dump_file, format: "Not unrolling loop %d: "
916	"number of branches on hot path in the unrolled "
917	"sequence reaches --param max-peel-branches limit.\n",
918	loop->num);
919	return false;
920	}
921	else if (unr_insns
922	> (unsigned) param_max_completely_peeled_insns)
923	{
924	if (dump_file && (dump_flags & TDF_DETAILS))
925	fprintf (stream: dump_file, format: "Not unrolling loop %d: "
926	"number of insns in the unrolled sequence reaches "
927	"--param max-completely-peeled-insns limit.\n",
928	loop->num);
929	return false;
930	}
931	}
932
933	if (!dbg_cnt (index: gimple_unroll))
934	return false;
935
936	initialize_original_copy_tables ();
937	auto_sbitmap wont_exit (n_unroll + 1);
938	if (exit && niter
939	&& TREE_CODE (niter) == INTEGER_CST
940	&& wi::leu_p (x: n_unroll, y: wi::to_widest (t: niter)))
941	{
942	bitmap_ones (wont_exit);
943	if (wi::eq_p (x: wi::to_widest (t: niter), y: n_unroll)
944	|| edge_to_cancel)
945	bitmap_clear_bit (map: wont_exit, bitno: 0);
946	}
947	else
948	{
949	exit = NULL;
950	bitmap_clear (wont_exit);
951	}
952	if (may_be_zero)
953	bitmap_clear_bit (map: wont_exit, bitno: 1);
954
955	/* If loop was originally estimated to iterate too many times,
956	reduce the profile to avoid new profile inconsistencies. */
957	scale_loop_profile (loop, profile_probability::always (), n_unroll);
958
959	if (!gimple_duplicate_loop_body_to_header_edge (
960	loop, loop_preheader_edge (loop), n_unroll, wont_exit, exit,
961	&edges_to_remove,
962	DLTHE_FLAG_UPDATE_FREQ | DLTHE_FLAG_COMPLETTE_PEEL))
963	{
964	free_original_copy_tables ();
965	if (dump_file && (dump_flags & TDF_DETAILS))
966	fprintf (stream: dump_file, format: "Failed to duplicate the loop\n");
967	return false;
968	}
969
970	free_original_copy_tables ();
971	}
972	else
973	scale_loop_profile (loop, profile_probability::always (), 0);
974
975	/* Remove the conditional from the last copy of the loop. */
976	if (edge_to_cancel)
977	{
978	gcond *cond = as_a <gcond *> (p: *gsi_last_bb (bb: edge_to_cancel->src));
979	force_edge_cold (edge_to_cancel, true);
980	if (edge_to_cancel->flags & EDGE_TRUE_VALUE)
981	gimple_cond_make_false (gs: cond);
982	else
983	gimple_cond_make_true (gs: cond);
984	update_stmt (s: cond);
985	/* Do not remove the path, as doing so may remove outer loop and
986	confuse bookkeeping code in tree_unroll_loops_completely. */
987	}
988
989	/* Store the loop for later unlooping and exit removal. */
990	loops_to_unloop.safe_push (obj: loop);
991	loops_to_unloop_nunroll.safe_push (obj: n_unroll);
992
993	if (dump_enabled_p ())
994	{
995	if (!n_unroll)
996	dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
997	"loop turned into non-loop; it never loops\n");
998	else
999	{
1000	dump_printf_loc (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, locus,
1001	"loop with %d iterations completely unrolled",
1002	(int) n_unroll);
1003	if (loop->header->count.initialized_p ())
1004	dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS,
1005	" (header execution count %d)",
1006	(int)loop->header->count.to_gcov_type ());
1007	dump_printf (MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS, "\n");
1008	}
1009	}
1010
1011	if (dump_file && (dump_flags & TDF_DETAILS))
1012	{
1013	if (exit)
1014	fprintf (stream: dump_file, format: "Exit condition of peeled iterations was "
1015	"eliminated.\n");
1016	if (edge_to_cancel)
1017	fprintf (stream: dump_file, format: "Last iteration exit edge was proved true.\n");
1018	else
1019	fprintf (stream: dump_file, format: "Latch of last iteration was marked by "
1020	"__builtin_unreachable ().\n");
1021	}
1022
1023	return true;
1024	}
1025
1026	/* Return number of instructions after peeling. */
1027	static unsigned HOST_WIDE_INT
1028	estimated_peeled_sequence_size (struct loop_size *size,
1029	unsigned HOST_WIDE_INT npeel)
1030	{
1031	return MAX (npeel * (HOST_WIDE_INT) (size->overall
1032	- size->eliminated_by_peeling), 1);
1033	}
1034
1035	/* Update loop estimates after peeling LOOP by NPEEL.
1036	If PRECISE is false only likely exists were duplicated and thus
1037	do not update any estimates that are supposed to be always reliable. */
1038	void
1039	adjust_loop_info_after_peeling (class loop *loop, int npeel, bool precise)
1040	{
1041	if (loop->any_estimate)
1042	{
1043	/* Since peeling is mostly about loops where first few
1044	iterations are special, it is not quite correct to
1045	assume that the remaining iterations will behave
1046	the same way. However we do not have better info
1047	so update the esitmate, since it is likely better
1048	than keeping it as it is.
1049
1050	Remove it if it looks wrong.
1051
1052	TODO: We likely want to special case the situation where
1053	peeling is optimizing out exit edges and only update
1054	estimates here. */
1055	if (wi::leu_p (x: npeel, y: loop->nb_iterations_estimate))
1056	loop->nb_iterations_estimate -= npeel;
1057	else
1058	loop->any_estimate = false;
1059	}
1060	if (loop->any_upper_bound && precise)
1061	{
1062	if (wi::leu_p (x: npeel, y: loop->nb_iterations_upper_bound))
1063	loop->nb_iterations_upper_bound -= npeel;
1064	else
1065	{
1066	/* Peeling maximal number of iterations or more
1067	makes no sense and is a bug.
1068	We should peel completely. */
1069	gcc_unreachable ();
1070	}
1071	}
1072	if (loop->any_likely_upper_bound)
1073	{
1074	if (wi::leu_p (x: npeel, y: loop->nb_iterations_likely_upper_bound))
1075	loop->nb_iterations_likely_upper_bound -= npeel;
1076	else
1077	{
1078	loop->any_estimate = true;
1079	loop->nb_iterations_estimate = 0;
1080	loop->nb_iterations_likely_upper_bound = 0;
1081	}
1082	}
1083	}
1084
1085	/* If the loop is expected to iterate N times and is
1086	small enough, duplicate the loop body N+1 times before
1087	the loop itself. This way the hot path will never
1088	enter the loop.
1089	Parameters are the same as for try_unroll_loops_completely */
1090
1091	static bool
1092	try_peel_loop (class loop *loop,
1093	edge exit, tree niter, bool may_be_zero,
1094	HOST_WIDE_INT maxiter)
1095	{
1096	HOST_WIDE_INT npeel;
1097	struct loop_size size;
1098	int peeled_size;
1099
1100	if (!flag_peel_loops
1101	|| param_max_peel_times <= 0
1102	|| !peeled_loops)
1103	return false;
1104
1105	if (bitmap_bit_p (peeled_loops, loop->num))
1106	{
1107	if (dump_file)
1108	fprintf (stream: dump_file, format: "Not peeling: loop is already peeled\n");
1109	return false;
1110	}
1111
1112	/* We don't peel loops that will be unrolled as this can duplicate a
1113	loop more times than the user requested. */
1114	if (loop->unroll)
1115	{
1116	if (dump_file)
1117	fprintf (stream: dump_file, format: "Not peeling: user didn't want it peeled.\n");
1118	return false;
1119	}
1120
1121	/* Peel only innermost loops.
1122	While the code is perfectly capable of peeling non-innermost loops,
1123	the heuristics would probably need some improvements. */
1124	if (loop->inner)
1125	{
1126	if (dump_file)
1127	fprintf (stream: dump_file, format: "Not peeling: outer loop\n");
1128	return false;
1129	}
1130
1131	if (!optimize_loop_for_speed_p (loop))
1132	{
1133	if (dump_file)
1134	fprintf (stream: dump_file, format: "Not peeling: cold loop\n");
1135	return false;
1136	}
1137
1138	/* Check if there is an estimate on the number of iterations. */
1139	npeel = estimated_loop_iterations_int (loop);
1140	if (npeel < 0)
1141	npeel = likely_max_loop_iterations_int (loop);
1142	if (npeel < 0)
1143	{
1144	if (dump_file)
1145	fprintf (stream: dump_file, format: "Not peeling: number of iterations is not "
1146	"estimated\n");
1147	return false;
1148	}
1149	if (maxiter >= 0 && maxiter <= npeel)
1150	{
1151	if (dump_file)
1152	fprintf (stream: dump_file, format: "Not peeling: upper bound is known so can "
1153	"unroll completely\n");
1154	return false;
1155	}
1156
1157	/* We want to peel estimated number of iterations + 1 (so we never
1158	enter the loop on quick path). Check against PARAM_MAX_PEEL_TIMES
1159	and be sure to avoid overflows. */
1160	if (npeel > param_max_peel_times - 1)
1161	{
1162	if (dump_file)
1163	fprintf (stream: dump_file, format: "Not peeling: rolls too much "
1164	"(%i + 1 > --param max-peel-times)\n", (int) npeel);
1165	return false;
1166	}
1167	npeel++;
1168
1169	/* Check peeled loops size. */
1170	tree_estimate_loop_size (loop, exit, NULL, size: &size,
1171	param_max_peeled_insns);
1172	if ((peeled_size = estimated_peeled_sequence_size (size: &size, npeel: (int) npeel))
1173	> param_max_peeled_insns)
1174	{
1175	if (dump_file)
1176	fprintf (stream: dump_file, format: "Not peeling: peeled sequence size is too large "
1177	"(%i insns > --param max-peel-insns)", peeled_size);
1178	return false;
1179	}
1180
1181	if (!dbg_cnt (index: gimple_unroll))
1182	return false;
1183
1184	/* Duplicate possibly eliminating the exits. */
1185	initialize_original_copy_tables ();
1186	auto_sbitmap wont_exit (npeel + 1);
1187	if (exit && niter
1188	&& TREE_CODE (niter) == INTEGER_CST
1189	&& wi::leu_p (x: npeel, y: wi::to_widest (t: niter)))
1190	{
1191	bitmap_ones (wont_exit);
1192	bitmap_clear_bit (map: wont_exit, bitno: 0);
1193	}
1194	else
1195	{
1196	exit = NULL;
1197	bitmap_clear (wont_exit);
1198	}
1199	if (may_be_zero)
1200	bitmap_clear_bit (map: wont_exit, bitno: 1);
1201
1202	if (!gimple_duplicate_loop_body_to_header_edge (
1203	loop, loop_preheader_edge (loop), npeel, wont_exit, exit,
1204	&edges_to_remove, DLTHE_FLAG_UPDATE_FREQ))
1205	{
1206	free_original_copy_tables ();
1207	return false;
1208	}
1209	free_original_copy_tables ();
1210	if (dump_file && (dump_flags & TDF_DETAILS))
1211	{
1212	fprintf (stream: dump_file, format: "Peeled loop %d, %i times.\n",
1213	loop->num, (int) npeel);
1214	}
1215	adjust_loop_info_after_peeling (loop, npeel, precise: true);
1216
1217	bitmap_set_bit (peeled_loops, loop->num);
1218	return true;
1219	}
1220	/* Adds a canonical induction variable to LOOP if suitable.
1221	CREATE_IV is true if we may create a new iv. UL determines
1222	which loops we are allowed to completely unroll. If TRY_EVAL is true, we try
1223	to determine the number of iterations of a loop by direct evaluation.
1224	Returns true if cfg is changed. */
1225
1226	static bool
1227	canonicalize_loop_induction_variables (class loop *loop,
1228	bool create_iv, enum unroll_level ul,
1229	bool try_eval, bool allow_peel)
1230	{
1231	edge exit = NULL;
1232	tree niter;
1233	HOST_WIDE_INT maxiter;
1234	bool modified = false;
1235	class tree_niter_desc niter_desc;
1236	bool may_be_zero = false;
1237
1238	/* For unrolling allow conditional constant or zero iterations, thus
1239	perform loop-header copying on-the-fly. */
1240	exit = single_exit (loop);
1241	niter = chrec_dont_know;
1242	if (exit && number_of_iterations_exit (loop, exit, niter: &niter_desc, false))
1243	{
1244	niter = niter_desc.niter;
1245	may_be_zero
1246	= niter_desc.may_be_zero && !integer_zerop (niter_desc.may_be_zero);
1247	}
1248	if (TREE_CODE (niter) != INTEGER_CST)
1249	{
1250	/* For non-constant niter fold may_be_zero into niter again. */
1251	if (may_be_zero)
1252	{
1253	if (COMPARISON_CLASS_P (niter_desc.may_be_zero))
1254	niter = fold_build3 (COND_EXPR, TREE_TYPE (niter),
1255	niter_desc.may_be_zero,
1256	build_int_cst (TREE_TYPE (niter), 0), niter);
1257	else
1258	niter = chrec_dont_know;
1259	may_be_zero = false;
1260	}
1261
1262	/* If the loop has more than one exit, try checking all of them
1263	for # of iterations determinable through scev. */
1264	if (!exit)
1265	niter = find_loop_niter (loop, &exit);
1266
1267	/* Finally if everything else fails, try brute force evaluation. */
1268	if (try_eval
1269	&& (chrec_contains_undetermined (niter)
1270	|| TREE_CODE (niter) != INTEGER_CST))
1271	niter = find_loop_niter_by_eval (loop, &exit);
1272
1273	if (TREE_CODE (niter) != INTEGER_CST)
1274	exit = NULL;
1275	}
1276
1277	/* We work exceptionally hard here to estimate the bound
1278	by find_loop_niter_by_eval. Be sure to keep it for future. */
1279	if (niter && TREE_CODE (niter) == INTEGER_CST)
1280	{
1281	auto_vec<edge> exits = get_loop_exit_edges (loop);
1282	record_niter_bound (loop, wi::to_widest (t: niter),
1283	exit == single_likely_exit (loop, exits), true);
1284	}
1285
1286	/* Force re-computation of loop bounds so we can remove redundant exits. */
1287	maxiter = max_loop_iterations_int (loop);
1288
1289	if (dump_file && (dump_flags & TDF_DETAILS)
1290	&& TREE_CODE (niter) == INTEGER_CST)
1291	{
1292	fprintf (stream: dump_file, format: "Loop %d iterates ", loop->num);
1293	print_generic_expr (dump_file, niter, TDF_SLIM);
1294	fprintf (stream: dump_file, format: " times.\n");
1295	}
1296	if (dump_file && (dump_flags & TDF_DETAILS)
1297	&& maxiter >= 0)
1298	{
1299	fprintf (stream: dump_file, format: "Loop %d iterates at most %i times.\n", loop->num,
1300	(int)maxiter);
1301	}
1302	if (dump_file && (dump_flags & TDF_DETAILS)
1303	&& likely_max_loop_iterations_int (loop) >= 0)
1304	{
1305	fprintf (stream: dump_file, format: "Loop %d likely iterates at most %i times.\n",
1306	loop->num, (int)likely_max_loop_iterations_int (loop));
1307	}
1308
1309	/* Remove exits that are known to be never taken based on loop bound.
1310	Needs to be called after compilation of max_loop_iterations_int that
1311	populates the loop bounds. */
1312	modified |= remove_redundant_iv_tests (loop);
1313
1314	dump_user_location_t locus = find_loop_location (loop);
1315	if (try_unroll_loop_completely (loop, exit, niter, may_be_zero, ul,
1316	maxiter, locus, allow_peel))
1317	return true;
1318
1319	if (create_iv
1320	&& niter && !chrec_contains_undetermined (niter)
1321	&& exit && just_once_each_iteration_p (loop, exit->src))
1322	{
1323	tree iv_niter = niter;
1324	if (may_be_zero)
1325	{
1326	if (COMPARISON_CLASS_P (niter_desc.may_be_zero))
1327	iv_niter = fold_build3 (COND_EXPR, TREE_TYPE (iv_niter),
1328	niter_desc.may_be_zero,
1329	build_int_cst (TREE_TYPE (iv_niter), 0),
1330	iv_niter);
1331	else
1332	iv_niter = NULL_TREE;
1333	}
1334	if (iv_niter)
1335	create_canonical_iv (loop, exit, niter: iv_niter);
1336	}
1337
1338	if (ul == UL_ALL)
1339	modified |= try_peel_loop (loop, exit, niter, may_be_zero, maxiter);
1340
1341	return modified;
1342	}
1343
1344	/* The main entry point of the pass. Adds canonical induction variables
1345	to the suitable loops. */
1346
1347	unsigned int
1348	canonicalize_induction_variables (void)
1349	{
1350	bool changed = false;
1351	bool irred_invalidated = false;
1352	bitmap loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
1353
1354	estimate_numbers_of_iterations (cfun);
1355
1356	for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
1357	{
1358	changed |= canonicalize_loop_induction_variables (loop,
1359	create_iv: true, ul: UL_SINGLE_ITER,
1360	try_eval: true, allow_peel: false);
1361	}
1362	gcc_assert (!need_ssa_update_p (cfun));
1363
1364	unloop_loops (loops_to_unloop, loops_to_unloop_nunroll,
1365	loop_closed_ssa_invalidated, irred_invalidated: &irred_invalidated);
1366	loops_to_unloop.release ();
1367	loops_to_unloop_nunroll.release ();
1368	if (irred_invalidated
1369	&& loops_state_satisfies_p (flags: LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1370	mark_irreducible_loops ();
1371
1372	/* Clean up the information about numbers of iterations, since brute force
1373	evaluation could reveal new information. */
1374	free_numbers_of_iterations_estimates (cfun);
1375	scev_reset ();
1376
1377	if (!bitmap_empty_p (map: loop_closed_ssa_invalidated))
1378	{
1379	gcc_checking_assert (loops_state_satisfies_p (LOOP_CLOSED_SSA));
1380	rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
1381	}
1382	BITMAP_FREE (loop_closed_ssa_invalidated);
1383
1384	if (changed)
1385	return TODO_cleanup_cfg;
1386	return 0;
1387	}
1388
1389	/* Process loops from innermost to outer, stopping at the innermost
1390	loop we unrolled. */
1391
1392	static bool
1393	tree_unroll_loops_completely_1 (bool may_increase_size, bool unroll_outer,
1394	bitmap father_bbs, class loop *loop)
1395	{
1396	class loop *loop_father;
1397	bool changed = false;
1398	class loop *inner;
1399	enum unroll_level ul;
1400	unsigned num = number_of_loops (cfun);
1401
1402	/* Process inner loops first. Don't walk loops added by the recursive
1403	calls because SSA form is not up-to-date. They can be handled in the
1404	next iteration. */
1405	bitmap child_father_bbs = NULL;
1406	for (inner = loop->inner; inner != NULL; inner = inner->next)
1407	if ((unsigned) inner->num < num)
1408	{
1409	if (!child_father_bbs)
1410	child_father_bbs = BITMAP_ALLOC (NULL);
1411	if (tree_unroll_loops_completely_1 (may_increase_size, unroll_outer,
1412	father_bbs: child_father_bbs, loop: inner))
1413	{
1414	bitmap_ior_into (father_bbs, child_father_bbs);
1415	bitmap_clear (child_father_bbs);
1416	changed = true;
1417	}
1418	}
1419	if (child_father_bbs)
1420	BITMAP_FREE (child_father_bbs);
1421
1422	/* If we changed an inner loop we cannot process outer loops in this
1423	iteration because SSA form is not up-to-date. Continue with
1424	siblings of outer loops instead. */
1425	if (changed)
1426	{
1427	/* If we are recorded as father clear all other fathers that
1428	are necessarily covered already to avoid redundant work. */
1429	if (bitmap_bit_p (father_bbs, loop->header->index))
1430	{
1431	bitmap_clear (father_bbs);
1432	bitmap_set_bit (father_bbs, loop->header->index);
1433	}
1434	return true;
1435	}
1436
1437	/* Don't unroll #pragma omp simd loops until the vectorizer
1438	attempts to vectorize those. */
1439	if (loop->force_vectorize)
1440	return false;
1441
1442	/* Try to unroll this loop. */
1443	loop_father = loop_outer (loop);
1444	if (!loop_father)
1445	return false;
1446
1447	if (loop->unroll > 1)
1448	ul = UL_ALL;
1449	else if (may_increase_size && optimize_loop_nest_for_speed_p (loop)
1450	/* Unroll outermost loops only if asked to do so or they do
1451	not cause code growth. */
1452	&& (unroll_outer || loop_outer (loop: loop_father)))
1453	ul = UL_ALL;
1454	else
1455	ul = UL_NO_GROWTH;
1456
1457	if (canonicalize_loop_induction_variables
1458	(loop, create_iv: false, ul, try_eval: !flag_tree_loop_ivcanon, allow_peel: unroll_outer))
1459	{
1460	/* If we'll continue unrolling, we need to propagate constants
1461	within the new basic blocks to fold away induction variable
1462	computations; otherwise, the size might blow up before the
1463	iteration is complete and the IR eventually cleaned up. */
1464	if (loop_outer (loop: loop_father))
1465	{
1466	/* Once we process our father we will have processed
1467	the fathers of our children as well, so avoid doing
1468	redundant work and clear fathers we've gathered sofar. */
1469	bitmap_clear (father_bbs);
1470	bitmap_set_bit (father_bbs, loop_father->header->index);
1471	}
1472	else if (unroll_outer)
1473	/* Trigger scalar cleanup once any outermost loop gets unrolled. */
1474	cfun->pending_TODOs |= PENDING_TODO_force_next_scalar_cleanup;
1475
1476	return true;
1477	}
1478
1479	return false;
1480	}
1481
1482	/* Unroll LOOPS completely if they iterate just few times. Unless
1483	MAY_INCREASE_SIZE is true, perform the unrolling only if the
1484	size of the code does not increase. */
1485
1486	static unsigned int
1487	tree_unroll_loops_completely (bool may_increase_size, bool unroll_outer)
1488	{
1489	bitmap father_bbs = BITMAP_ALLOC (NULL);
1490	bool changed;
1491	int iteration = 0;
1492	bool irred_invalidated = false;
1493
1494	estimate_numbers_of_iterations (cfun);
1495
1496	do
1497	{
1498	changed = false;
1499	bitmap loop_closed_ssa_invalidated = NULL;
1500
1501	if (loops_state_satisfies_p (flags: LOOP_CLOSED_SSA))
1502	loop_closed_ssa_invalidated = BITMAP_ALLOC (NULL);
1503
1504	free_numbers_of_iterations_estimates (cfun);
1505	estimate_numbers_of_iterations (cfun);
1506
1507	changed = tree_unroll_loops_completely_1 (may_increase_size,
1508	unroll_outer, father_bbs,
1509	current_loops->tree_root);
1510	if (changed)
1511	{
1512	unsigned i;
1513
1514	unloop_loops (loops_to_unloop,
1515	loops_to_unloop_nunroll,
1516	loop_closed_ssa_invalidated,
1517	irred_invalidated: &irred_invalidated);
1518	loops_to_unloop.release ();
1519	loops_to_unloop_nunroll.release ();
1520
1521	/* We cannot use TODO_update_ssa_no_phi because VOPS gets confused. */
1522	if (loop_closed_ssa_invalidated
1523	&& !bitmap_empty_p (map: loop_closed_ssa_invalidated))
1524	rewrite_into_loop_closed_ssa (loop_closed_ssa_invalidated,
1525	TODO_update_ssa);
1526	else
1527	update_ssa (TODO_update_ssa);
1528
1529	/* father_bbs is a bitmap of loop father header BB indices.
1530	Translate that to what non-root loops these BBs belong to now. */
1531	bitmap_iterator bi;
1532	bitmap fathers = BITMAP_ALLOC (NULL);
1533	EXECUTE_IF_SET_IN_BITMAP (father_bbs, 0, i, bi)
1534	{
1535	basic_block unrolled_loop_bb = BASIC_BLOCK_FOR_FN (cfun, i);
1536	if (! unrolled_loop_bb)
1537	continue;
1538	if (loop_outer (loop: unrolled_loop_bb->loop_father))
1539	bitmap_set_bit (fathers,
1540	unrolled_loop_bb->loop_father->num);
1541	}
1542	bitmap_clear (father_bbs);
1543	/* Propagate the constants within the new basic blocks. */
1544	EXECUTE_IF_SET_IN_BITMAP (fathers, 0, i, bi)
1545	{
1546	loop_p father = get_loop (cfun, num: i);
1547	bitmap exit_bbs = BITMAP_ALLOC (NULL);
1548	loop_exit *exit = father->exits->next;
1549	while (exit->e)
1550	{
1551	bitmap_set_bit (exit_bbs, exit->e->dest->index);
1552	exit = exit->next;
1553	}
1554	do_rpo_vn (cfun, loop_preheader_edge (father), exit_bbs);
1555	}
1556	BITMAP_FREE (fathers);
1557
1558	/* Clean up the information about numbers of iterations, since
1559	complete unrolling might have invalidated it. */
1560	scev_reset ();
1561
1562	/* This will take care of removing completely unrolled loops
1563	from the loop structures so we can continue unrolling now
1564	innermost loops. */
1565	if (cleanup_tree_cfg ())
1566	update_ssa (TODO_update_ssa_only_virtuals);
1567
1568	if (flag_checking && loops_state_satisfies_p (flags: LOOP_CLOSED_SSA))
1569	verify_loop_closed_ssa (true);
1570	}
1571	if (loop_closed_ssa_invalidated)
1572	BITMAP_FREE (loop_closed_ssa_invalidated);
1573	}
1574	while (changed
1575	&& ++iteration <= param_max_unroll_iterations);
1576
1577	BITMAP_FREE (father_bbs);
1578
1579	if (irred_invalidated
1580	&& loops_state_satisfies_p (flags: LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS))
1581	mark_irreducible_loops ();
1582
1583	return 0;
1584	}
1585
1586	/* Canonical induction variable creation pass. */
1587
1588	namespace {
1589
1590	const pass_data pass_data_iv_canon =
1591	{
1592	.type: GIMPLE_PASS, /* type */
1593	.name: "ivcanon", /* name */
1594	.optinfo_flags: OPTGROUP_LOOP, /* optinfo_flags */
1595	.tv_id: TV_TREE_LOOP_IVCANON, /* tv_id */
1596	.properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */
1597	.properties_provided: 0, /* properties_provided */
1598	.properties_destroyed: 0, /* properties_destroyed */
1599	.todo_flags_start: 0, /* todo_flags_start */
1600	.todo_flags_finish: 0, /* todo_flags_finish */
1601	};
1602
1603	class pass_iv_canon : public gimple_opt_pass
1604	{
1605	public:
1606	pass_iv_canon (gcc::context *ctxt)
1607	: gimple_opt_pass (pass_data_iv_canon, ctxt)
1608	{}
1609
1610	/* opt_pass methods: */
1611	bool gate (function *) final override { return flag_tree_loop_ivcanon != 0; }
1612	unsigned int execute (function *fun) final override;
1613
1614	}; // class pass_iv_canon
1615
1616	unsigned int
1617	pass_iv_canon::execute (function *fun)
1618	{
1619	if (number_of_loops (fn: fun) <= 1)
1620	return 0;
1621
1622	return canonicalize_induction_variables ();
1623	}
1624
1625	} // anon namespace
1626
1627	gimple_opt_pass *
1628	make_pass_iv_canon (gcc::context *ctxt)
1629	{
1630	return new pass_iv_canon (ctxt);
1631	}
1632
1633	/* Complete unrolling of loops. */
1634
1635	namespace {
1636
1637	const pass_data pass_data_complete_unroll =
1638	{
1639	.type: GIMPLE_PASS, /* type */
1640	.name: "cunroll", /* name */
1641	.optinfo_flags: OPTGROUP_LOOP, /* optinfo_flags */
1642	.tv_id: TV_COMPLETE_UNROLL, /* tv_id */
1643	.properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */
1644	.properties_provided: 0, /* properties_provided */
1645	.properties_destroyed: 0, /* properties_destroyed */
1646	.todo_flags_start: 0, /* todo_flags_start */
1647	.todo_flags_finish: 0, /* todo_flags_finish */
1648	};
1649
1650	class pass_complete_unroll : public gimple_opt_pass
1651	{
1652	public:
1653	pass_complete_unroll (gcc::context *ctxt)
1654	: gimple_opt_pass (pass_data_complete_unroll, ctxt)
1655	{}
1656
1657	/* opt_pass methods: */
1658	unsigned int execute (function *) final override;
1659
1660	}; // class pass_complete_unroll
1661
1662	unsigned int
1663	pass_complete_unroll::execute (function *fun)
1664	{
1665	if (number_of_loops (fn: fun) <= 1)
1666	return 0;
1667
1668	/* If we ever decide to run loop peeling more than once, we will need to
1669	track loops already peeled in loop structures themselves to avoid
1670	re-peeling the same loop multiple times. */
1671	if (flag_peel_loops)
1672	peeled_loops = BITMAP_ALLOC (NULL);
1673	unsigned int val = tree_unroll_loops_completely (flag_cunroll_grow_size,
1674	unroll_outer: true);
1675	if (peeled_loops)
1676	{
1677	BITMAP_FREE (peeled_loops);
1678	peeled_loops = NULL;
1679	}
1680	return val;
1681	}
1682
1683	} // anon namespace
1684
1685	gimple_opt_pass *
1686	make_pass_complete_unroll (gcc::context *ctxt)
1687	{
1688	return new pass_complete_unroll (ctxt);
1689	}
1690
1691	/* Complete unrolling of inner loops. */
1692
1693	namespace {
1694
1695	const pass_data pass_data_complete_unrolli =
1696	{
1697	.type: GIMPLE_PASS, /* type */
1698	.name: "cunrolli", /* name */
1699	.optinfo_flags: OPTGROUP_LOOP, /* optinfo_flags */
1700	.tv_id: TV_COMPLETE_UNROLL, /* tv_id */
1701	.properties_required: ( PROP_cfg | PROP_ssa ), /* properties_required */
1702	.properties_provided: 0, /* properties_provided */
1703	.properties_destroyed: 0, /* properties_destroyed */
1704	.todo_flags_start: 0, /* todo_flags_start */
1705	.todo_flags_finish: 0, /* todo_flags_finish */
1706	};
1707
1708	class pass_complete_unrolli : public gimple_opt_pass
1709	{
1710	public:
1711	pass_complete_unrolli (gcc::context *ctxt)
1712	: gimple_opt_pass (pass_data_complete_unrolli, ctxt)
1713	{}
1714
1715	/* opt_pass methods: */
1716	bool gate (function *) final override { return optimize >= 2; }
1717	unsigned int execute (function *) final override;
1718
1719	}; // class pass_complete_unrolli
1720
1721	unsigned int
1722	pass_complete_unrolli::execute (function *fun)
1723	{
1724	unsigned ret = 0;
1725
1726	loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
1727	if (number_of_loops (fn: fun) > 1)
1728	{
1729	scev_initialize ();
1730	ret = tree_unroll_loops_completely (optimize >= 3, unroll_outer: false);
1731	scev_finalize ();
1732	}
1733	loop_optimizer_finalize ();
1734
1735	return ret;
1736	}
1737
1738	} // anon namespace
1739
1740	gimple_opt_pass *
1741	make_pass_complete_unrolli (gcc::context *ctxt)
1742	{
1743	return new pass_complete_unrolli (ctxt);
1744	}
1745
1746
1747