tree-scalar-evolution.c source code [gcc/tree-scalar-evolution.c]

1	/ Scalar evolution detector.*
2	Copyright (C) 2003-2017 Free Software Foundation, Inc.
3	Contributed by Sebastian Pop <s.pop@laposte.net>
4
5	This file is part of GCC.
6
7	GCC is free software; you can redistribute it and/or modify it under
8	the terms of the GNU General Public License as published by the Free
9	Software Foundation; either version 3, or (at your option) any later
10	version.
11
12	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13	WARRANTY; without even the implied warranty of MERCHANTABILITY or
14	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15	for more details.
16
17	You should have received a copy of the GNU General Public License
18	along with GCC; see the file COPYING3. If not see
19	<http://www.gnu.org/licenses/>. /*
20
21	/*
22	Description:
23
24	This pass analyzes the evolution of scalar variables in loop
25	structures. The algorithm is based on the SSA representation,
26	and on the loop hierarchy tree. This algorithm is not based on
27	the notion of versions of a variable, as it was the case for the
28	previous implementations of the scalar evolution algorithm, but
29	it assumes that each defined name is unique.
30
31	The notation used in this file is called "chains of recurrences",
32	and has been proposed by Eugene Zima, Robert Van Engelen, and
33	others for describing induction variables in programs. For example
34	"b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
35	when entering in the loop_1 and has a step 2 in this loop, in other
36	words "for (b = 0; b < N; b+=2);". Note that the coefficients of
37	this chain of recurrence (or chrec [shrek]) can contain the name of
38	other variables, in which case they are called parametric chrecs.
39	For example, "b -> {a, +, 2}_1" means that the initial value of "b"
40	is the value of "a". In most of the cases these parametric chrecs
41	are fully instantiated before their use because symbolic names can
42	hide some difficult cases such as self-references described later
43	(see the Fibonacci example).
44
45	A short sketch of the algorithm is:
46
47	Given a scalar variable to be analyzed, follow the SSA edge to
48	its definition:
49
50	- When the definition is a GIMPLE_ASSIGN: if the right hand side
51	(RHS) of the definition cannot be statically analyzed, the answer
52	of the analyzer is: "don't know".
53	Otherwise, for all the variables that are not yet analyzed in the
54	RHS, try to determine their evolution, and finally try to
55	evaluate the operation of the RHS that gives the evolution
56	function of the analyzed variable.
57
58	- When the definition is a condition-phi-node: determine the
59	evolution function for all the branches of the phi node, and
60	finally merge these evolutions (see chrec_merge).
61
62	- When the definition is a loop-phi-node: determine its initial
63	condition, that is the SSA edge defined in an outer loop, and
64	keep it symbolic. Then determine the SSA edges that are defined
65	in the body of the loop. Follow the inner edges until ending on
66	another loop-phi-node of the same analyzed loop. If the reached
67	loop-phi-node is not the starting loop-phi-node, then we keep
68	this definition under a symbolic form. If the reached
69	loop-phi-node is the same as the starting one, then we compute a
70	symbolic stride on the return path. The result is then the
71	symbolic chrec {initial_condition, +, symbolic_stride}_loop.
72
73	Examples:
74
75	Example 1: Illustration of the basic algorithm.
76
77	\| a = 3
78	\| loop_1
79	\| b = phi (a, c)
80	\| c = b + 1
81	\| if (c > 10) exit_loop
82	\| endloop
83
84	Suppose that we want to know the number of iterations of the
85	loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
86	ask the scalar evolution analyzer two questions: what's the
87	scalar evolution (scev) of "c", and what's the scev of "10". For
88	"10" the answer is "10" since it is a scalar constant. For the
89	scalar variable "c", it follows the SSA edge to its definition,
90	"c = b + 1", and then asks again what's the scev of "b".
91	Following the SSA edge, we end on a loop-phi-node "b = phi (a,
92	c)", where the initial condition is "a", and the inner loop edge
93	is "c". The initial condition is kept under a symbolic form (it
94	may be the case that the copy constant propagation has done its
95	work and we end with the constant "3" as one of the edges of the
96	loop-phi-node). The update edge is followed to the end of the
97	loop, and until reaching again the starting loop-phi-node: b -> c
98	-> b. At this point we have drawn a path from "b" to "b" from
99	which we compute the stride in the loop: in this example it is
100	"+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
101	that the scev for "b" is known, it is possible to compute the
102	scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
103	determine the number of iterations in the loop_1, we have to
104	instantiate_parameters (loop_1, {a + 1, +, 1}_1), that gives after some
105	more analysis the scev {4, +, 1}_1, or in other words, this is
106	the function "f (x) = x + 4", where x is the iteration count of
107	the loop_1. Now we have to solve the inequality "x + 4 > 10",
108	and take the smallest iteration number for which the loop is
109	exited: x = 7. This loop runs from x = 0 to x = 7, and in total
110	there are 8 iterations. In terms of loop normalization, we have
111	created a variable that is implicitly defined, "x" or just "_1",
112	and all the other analyzed scalars of the loop are defined in
113	function of this variable:
114
115	a -> 3
116	b -> {3, +, 1}_1
117	c -> {4, +, 1}_1
118
119	or in terms of a C program:
120
121	\| a = 3
122	\| for (x = 0; x <= 7; x++)
123	\| {
124	\| b = x + 3
125	\| c = x + 4
126	\| }
127
128	Example 2a: Illustration of the algorithm on nested loops.
129
130	\| loop_1
131	\| a = phi (1, b)
132	\| c = a + 2
133	\| loop_2 10 times
134	\| b = phi (c, d)
135	\| d = b + 3
136	\| endloop
137	\| endloop
138
139	For analyzing the scalar evolution of "a", the algorithm follows
140	the SSA edge into the loop's body: "a -> b". "b" is an inner
141	loop-phi-node, and its analysis as in Example 1, gives:
142
143	b -> {c, +, 3}_2
144	d -> {c + 3, +, 3}_2
145
146	Following the SSA edge for the initial condition, we end on "c = a
147	+ 2", and then on the starting loop-phi-node "a". From this point,
148	the loop stride is computed: back on "c = a + 2" we get a "+2" in
149	the loop_1, then on the loop-phi-node "b" we compute the overall
150	effect of the inner loop that is "b = c + 30", and we get a "+30"
151	in the loop_1. That means that the overall stride in loop_1 is
152	equal to "+32", and the result is:
153
154	a -> {1, +, 32}_1
155	c -> {3, +, 32}_1
156
157	Example 2b: Multivariate chains of recurrences.
158
159	\| loop_1
160	\| k = phi (0, k + 1)
161	\| loop_2 4 times
162	\| j = phi (0, j + 1)
163	\| loop_3 4 times
164	\| i = phi (0, i + 1)
165	\| A[j + k] = ...
166	\| endloop
167	\| endloop
168	\| endloop
169
170	Analyzing the access function of array A with
171	instantiate_parameters (loop_1, "j + k"), we obtain the
172	instantiation and the analysis of the scalar variables "j" and "k"
173	in loop_1. This leads to the scalar evolution {4, +, 1}_1: the end
174	value of loop_2 for "j" is 4, and the evolution of "k" in loop_1 is
175	{0, +, 1}_1. To obtain the evolution function in loop_3 and
176	instantiate the scalar variables up to loop_1, one has to use:
177	instantiate_scev (block_before_loop (loop_1), loop_3, "j + k").
178	The result of this call is {{0, +, 1}_1, +, 1}_2.
179
180	Example 3: Higher degree polynomials.
181
182	\| loop_1
183	\| a = phi (2, b)
184	\| c = phi (5, d)
185	\| b = a + 1
186	\| d = c + a
187	\| endloop
188
189	a -> {2, +, 1}_1
190	b -> {3, +, 1}_1
191	c -> {5, +, a}_1
192	d -> {5 + a, +, a}_1
193
194	instantiate_parameters (loop_1, {5, +, a}_1) -> {5, +, 2, +, 1}_1
195	instantiate_parameters (loop_1, {5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
196
197	Example 4: Lucas, Fibonacci, or mixers in general.
198
199	\| loop_1
200	\| a = phi (1, b)
201	\| c = phi (3, d)
202	\| b = c
203	\| d = c + a
204	\| endloop
205
206	a -> (1, c)_1
207	c -> {3, +, a}_1
208
209	The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
210	following semantics: during the first iteration of the loop_1, the
211	variable contains the value 1, and then it contains the value "c".
212	Note that this syntax is close to the syntax of the loop-phi-node:
213	"a -> (1, c)_1" vs. "a = phi (1, c)".
214
215	The symbolic chrec representation contains all the semantics of the
216	original code. What is more difficult is to use this information.
217
218	Example 5: Flip-flops, or exchangers.
219
220	\| loop_1
221	\| a = phi (1, b)
222	\| c = phi (3, d)
223	\| b = c
224	\| d = a
225	\| endloop
226
227	a -> (1, c)_1
228	c -> (3, a)_1
229
230	Based on these symbolic chrecs, it is possible to refine this
231	information into the more precise PERIODIC_CHRECs:
232
233	a -> \|1, 3\|_1
234	c -> \|3, 1\|_1
235
236	This transformation is not yet implemented.
237
238	Further readings:
239
240	You can find a more detailed description of the algorithm in:
241	http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
242	http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
243	this is a preliminary report and some of the details of the
244	algorithm have changed. I'm working on a research report that
245	updates the description of the algorithms to reflect the design
246	choices used in this implementation.
247
248	A set of slides show a high level overview of the algorithm and run
249	an example through the scalar evolution analyzer:
250	http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
251
252	The slides that I have presented at the GCC Summit'04 are available
253	at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
254	*/
255
256	#include "config.h"
257	#include "system.h"
258	#include "coretypes.h"
259	#include "backend.h"
260	#include "rtl.h"
261	#include "tree.h"
262	#include "gimple.h"
263	#include "ssa.h"
264	#include "gimple-pretty-print.h"
265	#include "fold-const.h"
266	#include "gimplify.h"
267	#include "gimple-iterator.h"
268	#include "gimplify-me.h"
269	#include "tree-cfg.h"
270	#include "tree-ssa-loop-ivopts.h"
271	#include "tree-ssa-loop-manip.h"
272	#include "tree-ssa-loop-niter.h"
273	#include "tree-ssa-loop.h"
274	#include "tree-ssa.h"
275	#include "cfgloop.h"
276	#include "tree-chrec.h"
277	#include "tree-affine.h"
278	#include "tree-scalar-evolution.h"
279	#include "dumpfile.h"
280	#include "params.h"
281	#include "tree-ssa-propagate.h"
282	#include "gimple-fold.h"
283
284	static tree analyze_scalar_evolution_1 (struct loop *, tree);
285	static tree analyze_scalar_evolution_for_address_of (struct loop *loop,
286	tree var);
287
288	/ The cached information about an SSA name with version NAME_VERSION,*
289	claiming that below basic block with index INSTANTIATED_BELOW, the
290	value of the SSA name can be expressed as CHREC. /*
291
292	struct GTY((for_user)) scev_info_str {
293	unsigned int name_version;
294	int instantiated_below;
295	tree chrec;
296	};
297
298	/ Counters for the scev database. /
299	static unsigned nb_set_scev = `0`;
300	static unsigned nb_get_scev = `0`;
301
302	/ The following trees are unique elements. Thus the comparison of*
303	another element to these elements should be done on the pointer to
304	these trees, and not on their value. /*
305
306	/ The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. /
307	tree chrec_not_analyzed_yet;
308
309	/ Reserved to the cases where the analyzer has detected an*
310	undecidable property at compile time. /*
311	tree chrec_dont_know;
312
313	/ When the analyzer has detected that a property will never*
314	happen, then it qualifies it with chrec_known. /*
315	tree chrec_known;
316
317	struct scev_info_hasher : ggc_ptr_hash<scev_info_str>
318	{
319	static hashval_t hash (scev_info_str *i);
320	static bool equal (const scev_info_str a, const* scev_info_str *b);
321	};
322
323	static GTY (()) hash_table<scev_info_hasher> *scalar_evolution_info;
324
325
326	/ Constructs a new SCEV_INFO_STR structure for VAR and INSTANTIATED_BELOW. /
327
328	static inline struct scev_info_str *
329	new_scev_info_str (basic_block instantiated_below, tree var)
330	{
331	struct scev_info_str *res;
332
333	res = ggc_alloc<scev_info_str> ();
334	res->name_version = SSA_NAME_VERSION (var);
335	res->chrec = chrec_not_analyzed_yet;
336	res->instantiated_below = instantiated_below->index;
337
338	return res;
339	}
340
341	/ Computes a hash function for database element ELT. /
342
343	hashval_t
344	scev_info_hasher::hash (scev_info_str *elt)
345	{
346	return elt->name_version ^ elt->instantiated_below;
347	}
348
349	/ Compares database elements E1 and E2. /
350
351	bool
352	scev_info_hasher::equal (const scev_info_str elt1, const* scev_info_str *elt2)
353	{
354	return (elt1->name_version == elt2->name_version
355	&& elt1->instantiated_below == elt2->instantiated_below);
356	}
357
358	/ Get the scalar evolution of VAR for INSTANTIATED_BELOW basic block.*
359	A first query on VAR returns chrec_not_analyzed_yet. /*
360
361	static tree *
362	find_var_scev_info (basic_block instantiated_below, tree var)
363	{
364	struct scev_info_str *res;
365	struct scev_info_str tmp;
366
367	tmp.name_version = SSA_NAME_VERSION (var);
368	tmp.instantiated_below = instantiated_below->index;
369	scev_info_str **slot = scalar_evolution_info->find_slot (&tmp, INSERT);
370
371	if (!*slot)
372	*slot = new_scev_info_str (instantiated_below, var);
373	res = *slot;
374
375	return &res->chrec;
376	}
377
378	/ Return true when CHREC contains symbolic names defined in*
379	LOOP_NB. /*
380
381	bool
382	chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
383	{
384	int i, n;
385
386	if (chrec == NULL_TREE)
387	return false;
388
389	if (is_gimple_min_invariant (chrec))
390	return false;
391
392	if (TREE_CODE (chrec) == SSA_NAME)
393	{
394	gimple *def;
395	loop_p def_loop, loop;
396
397	if (SSA_NAME_IS_DEFAULT_DEF (chrec))
398	return false;
399
400	def = SSA_NAME_DEF_STMT (chrec);
401	def_loop = loop_containing_stmt (def);
402	loop = get_loop (cfun, loop_nb);
403
404	if (def_loop == NULL)
405	return false;
406
407	if (loop == def_loop \|\| flow_loop_nested_p (loop, def_loop))
408	return true;
409
410	return false;
411	}
412
413	n = TREE_OPERAND_LENGTH (chrec);
414	for (i = `0`; i < n; i++)
415	if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
416	loop_nb))
417	return true;
418	return false;
419	}
420
421	/ Return true when PHI is a loop-phi-node. /
422
423	static bool
424	loop_phi_node_p (gimple *phi)
425	{
426	/ The implementation of this function is based on the following*
427	property: "all the loop-phi-nodes of a loop are contained in the
428	loop's header basic block". /*
429
430	return loop_containing_stmt (phi)->header == gimple_bb (phi);
431	}
432
433	/ Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.*
434	In general, in the case of multivariate evolutions we want to get
435	the evolution in different loops. LOOP specifies the level for
436	which to get the evolution.
437
438	Example:
439
440	\| for (j = 0; j < 100; j++)
441	\| {
442	\| for (k = 0; k < 100; k++)
443	\| {
444	\| i = k + j; - Here the value of i is a function of j, k.
445	\| }
446	\| ... = i - Here the value of i is a function of j.
447	\| }
448	\| ... = i - Here the value of i is a scalar.
449
450	Example:
451
452	\| i_0 = ...
453	\| loop_1 10 times
454	\| i_1 = phi (i_0, i_2)
455	\| i_2 = i_1 + 2
456	\| endloop
457
458	This loop has the same effect as:
459	LOOP_1 has the same effect as:
460
461	\| i_1 = i_0 + 20
462
463	The overall effect of the loop, "i_0 + 20" in the previous example,
464	is obtained by passing in the parameters: LOOP = 1,
465	EVOLUTION_FN = {i_0, +, 2}_1.
466	*/
467
468	tree
469	compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
470	{
471	bool val = false;
472
473	if (evolution_fn == chrec_dont_know)
474	return chrec_dont_know;
475
476	else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
477	{
478	struct loop *inner_loop = get_chrec_loop (evolution_fn);
479
480	if (inner_loop == loop
481	\|\| flow_loop_nested_p (loop, inner_loop))
482	{
483	tree nb_iter = number_of_latch_executions (inner_loop);
484
485	if (nb_iter == chrec_dont_know)
486	return chrec_dont_know;
487	else
488	{
489	tree res;
490
491	/ evolution_fn is the evolution function in LOOP. Get*
492	its value in the nb_iter-th iteration. /*
493	res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
494
495	if (chrec_contains_symbols_defined_in_loop (res, loop->num))
496	res = instantiate_parameters (loop, res);
497
498	/ Continue the computation until ending on a parent of LOOP. /
499	return compute_overall_effect_of_inner_loop (loop, res);
500	}
501	}
502	else
503	return evolution_fn;
504	}
505
506	/ If the evolution function is an invariant, there is nothing to do. /
507	else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
508	return evolution_fn;
509
510	else
511	return chrec_dont_know;
512	}
513
514	/ Associate CHREC to SCALAR. /
515
516	static void
517	set_scalar_evolution (basic_block instantiated_below, tree scalar, tree chrec)
518	{
519	tree *scalar_info;
520
521	if (TREE_CODE (scalar) != SSA_NAME)
522	return;
523
524	scalar_info = find_var_scev_info (instantiated_below, scalar);
525
526	if (dump_file)
527	{
528	if (dump_flags & TDF_SCEV)
529	{
530	fprintf (dump_file, "(set_scalar_evolution \n");
531	fprintf (dump_file, " instantiated_below = %d \n",
532	instantiated_below->index);
533	fprintf (dump_file, " (scalar = ");
534	print_generic_expr (dump_file, scalar);
535	fprintf (dump_file, ")\n (scalar_evolution = ");
536	print_generic_expr (dump_file, chrec);
537	fprintf (dump_file, "))\n");
538	}
539	if (dump_flags & TDF_STATS)
540	nb_set_scev++;
541	}
542
543	*scalar_info = chrec;
544	}
545
546	/ Retrieve the chrec associated to SCALAR instantiated below*
547	INSTANTIATED_BELOW block. /*
548
549	static tree
550	get_scalar_evolution (basic_block instantiated_below, tree scalar)
551	{
552	tree res;
553
554	if (dump_file)
555	{
556	if (dump_flags & TDF_SCEV)
557	{
558	fprintf (dump_file, "(get_scalar_evolution \n");
559	fprintf (dump_file, " (scalar = ");
560	print_generic_expr (dump_file, scalar);
561	fprintf (dump_file, ")\n");
562	}
563	if (dump_flags & TDF_STATS)
564	nb_get_scev++;
565	}
566
567	if (VECTOR_TYPE_P (TREE_TYPE (scalar))
568	\|\| TREE_CODE (TREE_TYPE (scalar)) == COMPLEX_TYPE)
569	/ For chrec_dont_know we keep the symbolic form. /
570	res = scalar;
571	else
572	switch (TREE_CODE (scalar))
573	{
574	case SSA_NAME:
575	if (SSA_NAME_IS_DEFAULT_DEF (scalar))
576	res = scalar;
577	else
578	res = *find_var_scev_info (instantiated_below, scalar);
579	break;
580
581	case REAL_CST:
582	case FIXED_CST:
583	case INTEGER_CST:
584	res = scalar;
585	break;
586
587	default:
588	res = chrec_not_analyzed_yet;
589	break;
590	}
591
592	if (dump_file && (dump_flags & TDF_SCEV))
593	{
594	fprintf (dump_file, " (scalar_evolution = ");
595	print_generic_expr (dump_file, res);
596	fprintf (dump_file, "))\n");
597	}
598
599	return res;
600	}
601
602	/ Helper function for add_to_evolution. Returns the evolution*
603	function for an assignment of the form "a = b + c", where "a" and
604	"b" are on the strongly connected component. CHREC_BEFORE is the
605	information that we already have collected up to this point.
606	TO_ADD is the evolution of "c".
607
608	When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
609	evolution the expression TO_ADD, otherwise construct an evolution
610	part for this loop. /*
611
612	static tree
613	add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
614	gimple *at_stmt)
615	{
616	tree type, left, right;
617	struct loop loop = get_loop (cfun, loop_nb), chloop;
618
619	switch (TREE_CODE (chrec_before))
620	{
621	case POLYNOMIAL_CHREC:
622	chloop = get_chrec_loop (chrec_before);
623	if (chloop == loop
624	\|\| flow_loop_nested_p (chloop, loop))
625	{
626	unsigned var;
627
628	type = chrec_type (chrec_before);
629
630	/ When there is no evolution part in this loop, build it. /
631	if (chloop != loop)
632	{
633	var = loop_nb;
634	left = chrec_before;
635	right = SCALAR_FLOAT_TYPE_P (type)
636	? build_real (type, dconst0)
637	: build_int_cst (type, `0`);
638	}
639	else
640	{
641	var = CHREC_VARIABLE (chrec_before);
642	left = CHREC_LEFT (chrec_before);
643	right = CHREC_RIGHT (chrec_before);
644	}
645
646	to_add = chrec_convert (type, to_add, at_stmt);
647	right = chrec_convert_rhs (type, right, at_stmt);
648	right = chrec_fold_plus (chrec_type (right), right, to_add);
649	return build_polynomial_chrec (var, left, right);
650	}
651	else
652	{
653	gcc_assert (flow_loop_nested_p (loop, chloop));
654
655	/ Search the evolution in LOOP_NB. /
656	left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
657	to_add, at_stmt);
658	right = CHREC_RIGHT (chrec_before);
659	right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
660	return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
661	left, right);
662	}
663
664	default:
665	/ These nodes do not depend on a loop. /
666	if (chrec_before == chrec_dont_know)
667	return chrec_dont_know;
668
669	left = chrec_before;
670	right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
671	return build_polynomial_chrec (loop_nb, left, right);
672	}
673	}
674
675	/ Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension*
676	of LOOP_NB.
677
678	Description (provided for completeness, for those who read code in
679	a plane, and for my poor 62 bytes brain that would have forgotten
680	all this in the next two or three months):
681
682	The algorithm of translation of programs from the SSA representation
683	into the chrecs syntax is based on a pattern matching. After having
684	reconstructed the overall tree expression for a loop, there are only
685	two cases that can arise:
686
687	1. a = loop-phi (init, a + expr)
688	2. a = loop-phi (init, expr)
689
690	where EXPR is either a scalar constant with respect to the analyzed
691	loop (this is a degree 0 polynomial), or an expression containing
692	other loop-phi definitions (these are higher degree polynomials).
693
694	Examples:
695
696	1.
697	\| init = ...
698	\| loop_1
699	\| a = phi (init, a + 5)
700	\| endloop
701
702	2.
703	\| inita = ...
704	\| initb = ...
705	\| loop_1
706	\| a = phi (inita, 2 b + 3)*
707	\| b = phi (initb, b + 1)
708	\| endloop
709
710	For the first case, the semantics of the SSA representation is:
711
712	\| a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
713
714	that is, there is a loop index "x" that determines the scalar value
715	of the variable during the loop execution. During the first
716	iteration, the value is that of the initial condition INIT, while
717	during the subsequent iterations, it is the sum of the initial
718	condition with the sum of all the values of EXPR from the initial
719	iteration to the before last considered iteration.
720
721	For the second case, the semantics of the SSA program is:
722
723	\| a (x) = init, if x = 0;
724	\| expr (x - 1), otherwise.
725
726	The second case corresponds to the PEELED_CHREC, whose syntax is
727	close to the syntax of a loop-phi-node:
728
729	\| phi (init, expr) vs. (init, expr)_x
730
731	The proof of the translation algorithm for the first case is a
732	proof by structural induction based on the degree of EXPR.
733
734	Degree 0:
735	When EXPR is a constant with respect to the analyzed loop, or in
736	other words when EXPR is a polynomial of degree 0, the evolution of
737	the variable A in the loop is an affine function with an initial
738	condition INIT, and a step EXPR. In order to show this, we start
739	from the semantics of the SSA representation:
740
741	f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
742
743	and since "expr (j)" is a constant with respect to "j",
744
745	f (x) = init + x expr*
746
747	Finally, based on the semantics of the pure sum chrecs, by
748	identification we get the corresponding chrecs syntax:
749
750	f (x) = init \binom{x}{0} + expr * \binom{x}{1}*
751	f (x) -> {init, +, expr}_x
752
753	Higher degree:
754	Suppose that EXPR is a polynomial of degree N with respect to the
755	analyzed loop_x for which we have already determined that it is
756	written under the chrecs syntax:
757
758	\| expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
759
760	We start from the semantics of the SSA program:
761
762	\| f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
763	\|
764	\| f (x) = init + \sum_{j = 0}^{x - 1}
765	\| (b_0 \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})*
766	\|
767	\| f (x) = init + \sum_{j = 0}^{x - 1}
768	\| \sum_{k = 0}^{n - 1} (b_k \binom{j}{k})*
769	\|
770	\| f (x) = init + \sum_{k = 0}^{n - 1}
771	\| (b_k \sum_{j = 0}^{x - 1} \binom{j}{k})*
772	\|
773	\| f (x) = init + \sum_{k = 0}^{n - 1}
774	\| (b_k \binom{x}{k + 1})*
775	\|
776	\| f (x) = init + b_0 \binom{x}{1} + ...*
777	\| + b_{n-1} \binom{x}{n}*
778	\|
779	\| f (x) = init \binom{x}{0} + b_0 * \binom{x}{1} + ...*
780	\| + b_{n-1} \binom{x}{n}*
781	\|
782
783	And finally from the definition of the chrecs syntax, we identify:
784	\| f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
785
786	This shows the mechanism that stands behind the add_to_evolution
787	function. An important point is that the use of symbolic
788	parameters avoids the need of an analysis schedule.
789
790	Example:
791
792	\| inita = ...
793	\| initb = ...
794	\| loop_1
795	\| a = phi (inita, a + 2 + b)
796	\| b = phi (initb, b + 1)
797	\| endloop
798
799	When analyzing "a", the algorithm keeps "b" symbolically:
800
801	\| a -> {inita, +, 2 + b}_1
802
803	Then, after instantiation, the analyzer ends on the evolution:
804
805	\| a -> {inita, +, 2 + initb, +, 1}_1
806
807	*/
808
809	static tree
810	add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
811	tree to_add, gimple *at_stmt)
812	{
813	tree type = chrec_type (to_add);
814	tree res = NULL_TREE;
815
816	if (to_add == NULL_TREE)
817	return chrec_before;
818
819	/ TO_ADD is either a scalar, or a parameter. TO_ADD is not*
820	instantiated at this point. /*
821	if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
822	/ This should not happen. /
823	return chrec_dont_know;
824
825	if (dump_file && (dump_flags & TDF_SCEV))
826	{
827	fprintf (dump_file, "(add_to_evolution \n");
828	fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
829	fprintf (dump_file, " (chrec_before = ");
830	print_generic_expr (dump_file, chrec_before);
831	fprintf (dump_file, ")\n (to_add = ");
832	print_generic_expr (dump_file, to_add);
833	fprintf (dump_file, ")\n");
834	}
835
836	if (code == MINUS_EXPR)
837	to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
838	? build_real (type, dconstm1)
839	: build_int_cst_type (type, -`1`));
840
841	res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
842
843	if (dump_file && (dump_flags & TDF_SCEV))
844	{
845	fprintf (dump_file, " (res = ");
846	print_generic_expr (dump_file, res);
847	fprintf (dump_file, "))\n");
848	}
849
850	return res;
851	}
852
853
854
855	/ This section selects the loops that will be good candidates for the*
856	scalar evolution analysis. For the moment, greedily select all the
857	loop nests we could analyze. /*
858
859	/ For a loop with a single exit edge, return the COND_EXPR that*
860	guards the exit edge. If the expression is too difficult to
861	analyze, then give up. /*
862
863	gcond *
864	get_loop_exit_condition (const struct loop *loop)
865	{
866	gcond *res = NULL;
867	edge exit_edge = single_exit (loop);
868
869	if (dump_file && (dump_flags & TDF_SCEV))
870	fprintf (dump_file, "(get_loop_exit_condition \n ");
871
872	if (exit_edge)
873	{
874	gimple *stmt;
875
876	stmt = last_stmt (exit_edge->src);
877	if (gcond cond_stmt = dyn_cast <gcond > (stmt))
878	res = cond_stmt;
879	}
880
881	if (dump_file && (dump_flags & TDF_SCEV))
882	{
883	print_gimple_stmt (dump_file, res, `0`);
884	fprintf (dump_file, ")\n");
885	}
886
887	return res;
888	}
889
890
891	/ Depth first search algorithm. /
892
893	enum t_bool {
894	t_false,
895	t_true,
896	t_dont_know
897	};
898
899
900	static t_bool follow_ssa_edge (struct loop loop, gimple , gphi *,
901	tree , int*);
902
903	/ Follow the ssa edge into the binary expression RHS0 CODE RHS1.*
904	Return true if the strongly connected component has been found. /*
905
906	static t_bool
907	follow_ssa_edge_binary (struct loop loop, gimple at_stmt,
908	tree type, tree rhs0, enum tree_code code, tree rhs1,
909	gphi halting_phi, tree evolution_of_loop,
910	int limit)
911	{
912	t_bool res = t_false;
913	tree evol;
914
915	switch (code)
916	{
917	case POINTER_PLUS_EXPR:
918	case PLUS_EXPR:
919	if (TREE_CODE (rhs0) == SSA_NAME)
920	{
921	if (TREE_CODE (rhs1) == SSA_NAME)
922	{
923	/ Match an assignment under the form:*
924	"a = b + c". /*
925
926	/ We want only assignments of form "name + name" contribute to*
927	LIMIT, as the other cases do not necessarily contribute to
928	the complexity of the expression. /*
929	limit++;
930
931	evol = *evolution_of_loop;
932	evol = add_to_evolution
933	(loop->num,
934	chrec_convert (type, evol, at_stmt),
935	code, rhs1, at_stmt);
936	res = follow_ssa_edge
937	(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi, &evol, limit);
938	if (res == t_true)
939	*evolution_of_loop = evol;
940	else if (res == t_false)
941	{
942	*evolution_of_loop = add_to_evolution
943	(loop->num,
944	chrec_convert (type, *evolution_of_loop, at_stmt),
945	code, rhs0, at_stmt);
946	res = follow_ssa_edge
947	(loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
948	evolution_of_loop, limit);
949	if (res == t_true)
950	;
951	else if (res == t_dont_know)
952	*evolution_of_loop = chrec_dont_know;
953	}
954
955	else if (res == t_dont_know)
956	*evolution_of_loop = chrec_dont_know;
957	}
958
959	else
960	{
961	/ Match an assignment under the form:*
962	"a = b + ...". /*
963	*evolution_of_loop = add_to_evolution
964	(loop->num, chrec_convert (type, *evolution_of_loop,
965	at_stmt),
966	code, rhs1, at_stmt);
967	res = follow_ssa_edge
968	(loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
969	evolution_of_loop, limit);
970	if (res == t_true)
971	;
972	else if (res == t_dont_know)
973	*evolution_of_loop = chrec_dont_know;
974	}
975	}
976
977	else if (TREE_CODE (rhs1) == SSA_NAME)
978	{
979	/ Match an assignment under the form:*
980	"a = ... + c". /*
981	*evolution_of_loop = add_to_evolution
982	(loop->num, chrec_convert (type, *evolution_of_loop,
983	at_stmt),
984	code, rhs0, at_stmt);
985	res = follow_ssa_edge
986	(loop, SSA_NAME_DEF_STMT (rhs1), halting_phi,
987	evolution_of_loop, limit);
988	if (res == t_true)
989	;
990	else if (res == t_dont_know)
991	*evolution_of_loop = chrec_dont_know;
992	}
993
994	else
995	/ Otherwise, match an assignment under the form:*
996	"a = ... + ...". /*
997	/ And there is nothing to do. /
998	res = t_false;
999	break;
1000
1001	case MINUS_EXPR:
1002	/ This case is under the form "opnd0 = rhs0 - rhs1". /
1003	if (TREE_CODE (rhs0) == SSA_NAME)
1004	{
1005	/ Match an assignment under the form:*
1006	"a = b - ...". /*
1007
1008	/ We want only assignments of form "name - name" contribute to*
1009	LIMIT, as the other cases do not necessarily contribute to
1010	the complexity of the expression. /*
1011	if (TREE_CODE (rhs1) == SSA_NAME)
1012	limit++;
1013
1014	*evolution_of_loop = add_to_evolution
1015	(loop->num, chrec_convert (type, *evolution_of_loop, at_stmt),
1016	MINUS_EXPR, rhs1, at_stmt);
1017	res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0), halting_phi,
1018	evolution_of_loop, limit);
1019	if (res == t_true)
1020	;
1021	else if (res == t_dont_know)
1022	*evolution_of_loop = chrec_dont_know;
1023	}
1024	else
1025	/ Otherwise, match an assignment under the form:*
1026	"a = ... - ...". /*
1027	/ And there is nothing to do. /
1028	res = t_false;
1029	break;
1030
1031	default:
1032	res = t_false;
1033	}
1034
1035	return res;
1036	}
1037
1038	/ Follow the ssa edge into the expression EXPR.*
1039	Return true if the strongly connected component has been found. /*
1040
1041	static t_bool
1042	follow_ssa_edge_expr (struct loop loop, gimple at_stmt, tree expr,
1043	gphi halting_phi, tree evolution_of_loop,
1044	int limit)
1045	{
1046	enum tree_code code = TREE_CODE (expr);
1047	tree type = TREE_TYPE (expr), rhs0, rhs1;
1048	t_bool res;
1049
1050	/ The EXPR is one of the following cases:*
1051	- an SSA_NAME,
1052	- an INTEGER_CST,
1053	- a PLUS_EXPR,
1054	- a POINTER_PLUS_EXPR,
1055	- a MINUS_EXPR,
1056	- an ASSERT_EXPR,
1057	- other cases are not yet handled. /*
1058
1059	switch (code)
1060	{
1061	CASE_CONVERT:
1062	/ This assignment is under the form "a_1 = (cast) rhs. /
1063	res = follow_ssa_edge_expr (loop, at_stmt, TREE_OPERAND (expr, `0`),
1064	halting_phi, evolution_of_loop, limit);
1065	evolution_of_loop = chrec_convert (type, evolution_of_loop, at_stmt);
1066	break;
1067
1068	case INTEGER_CST:
1069	/ This assignment is under the form "a_1 = 7". /
1070	res = t_false;
1071	break;
1072
1073	case SSA_NAME:
1074	/ This assignment is under the form: "a_1 = b_2". /
1075	res = follow_ssa_edge
1076	(loop, SSA_NAME_DEF_STMT (expr), halting_phi, evolution_of_loop, limit);
1077	break;
1078
1079	case POINTER_PLUS_EXPR:
1080	case PLUS_EXPR:
1081	case MINUS_EXPR:
1082	/ This case is under the form "rhs0 +- rhs1". /
1083	rhs0 = TREE_OPERAND (expr, `0`);
1084	rhs1 = TREE_OPERAND (expr, `1`);
1085	type = TREE_TYPE (rhs0);
1086	STRIP_USELESS_TYPE_CONVERSION (rhs0);
1087	STRIP_USELESS_TYPE_CONVERSION (rhs1);
1088	res = follow_ssa_edge_binary (loop, at_stmt, type, rhs0, code, rhs1,
1089	halting_phi, evolution_of_loop, limit);
1090	break;
1091
1092	case ADDR_EXPR:
1093	/ Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. /
1094	if (TREE_CODE (TREE_OPERAND (expr, `0`)) == MEM_REF)
1095	{
1096	expr = TREE_OPERAND (expr, `0`);
1097	rhs0 = TREE_OPERAND (expr, `0`);
1098	rhs1 = TREE_OPERAND (expr, `1`);
1099	type = TREE_TYPE (rhs0);
1100	STRIP_USELESS_TYPE_CONVERSION (rhs0);
1101	STRIP_USELESS_TYPE_CONVERSION (rhs1);
1102	res = follow_ssa_edge_binary (loop, at_stmt, type,
1103	rhs0, POINTER_PLUS_EXPR, rhs1,
1104	halting_phi, evolution_of_loop, limit);
1105	}
1106	else
1107	res = t_false;
1108	break;
1109
1110	case ASSERT_EXPR:
1111	/ This assignment is of the form: "a_1 = ASSERT_EXPR <a_2, ...>"*
1112	It must be handled as a copy assignment of the form a_1 = a_2. /*
1113	rhs0 = ASSERT_EXPR_VAR (expr);
1114	if (TREE_CODE (rhs0) == SSA_NAME)
1115	res = follow_ssa_edge (loop, SSA_NAME_DEF_STMT (rhs0),
1116	halting_phi, evolution_of_loop, limit);
1117	else
1118	res = t_false;
1119	break;
1120
1121	default:
1122	res = t_false;
1123	break;
1124	}
1125
1126	return res;
1127	}
1128
1129	/ Follow the ssa edge into the right hand side of an assignment STMT.*
1130	Return true if the strongly connected component has been found. /*
1131
1132	static t_bool
1133	follow_ssa_edge_in_rhs (struct loop loop, gimple stmt,
1134	gphi halting_phi, tree evolution_of_loop,
1135	int limit)
1136	{
1137	enum tree_code code = gimple_assign_rhs_code (stmt);
1138	tree type = gimple_expr_type (stmt), rhs1, rhs2;
1139	t_bool res;
1140
1141	switch (code)
1142	{
1143	CASE_CONVERT:
1144	/ This assignment is under the form "a_1 = (cast) rhs. /
1145	res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1146	halting_phi, evolution_of_loop, limit);
1147	evolution_of_loop = chrec_convert (type, evolution_of_loop, stmt);
1148	break;
1149
1150	case POINTER_PLUS_EXPR:
1151	case PLUS_EXPR:
1152	case MINUS_EXPR:
1153	rhs1 = gimple_assign_rhs1 (stmt);
1154	rhs2 = gimple_assign_rhs2 (stmt);
1155	type = TREE_TYPE (rhs1);
1156	res = follow_ssa_edge_binary (loop, stmt, type, rhs1, code, rhs2,
1157	halting_phi, evolution_of_loop, limit);
1158	break;
1159
1160	default:
1161	if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1162	res = follow_ssa_edge_expr (loop, stmt, gimple_assign_rhs1 (stmt),
1163	halting_phi, evolution_of_loop, limit);
1164	else
1165	res = t_false;
1166	break;
1167	}
1168
1169	return res;
1170	}
1171
1172	/ Checks whether the I-th argument of a PHI comes from a backedge. /
1173
1174	static bool
1175	backedge_phi_arg_p (gphi phi, int* i)
1176	{
1177	const_edge e = gimple_phi_arg_edge (phi, i);
1178
1179	/ We would in fact like to test EDGE_DFS_BACK here, but we do not care*
1180	about updating it anywhere, and this should work as well most of the
1181	time. /*
1182	if (e->flags & EDGE_IRREDUCIBLE_LOOP)
1183	return true;
1184
1185	return false;
1186	}
1187
1188	/ Helper function for one branch of the condition-phi-node. Return*
1189	true if the strongly connected component has been found following
1190	this path. /*
1191
1192	static inline t_bool
1193	follow_ssa_edge_in_condition_phi_branch (int i,
1194	struct loop *loop,
1195	gphi *condition_phi,
1196	gphi *halting_phi,
1197	tree *evolution_of_branch,
1198	tree init_cond, int limit)
1199	{
1200	tree branch = PHI_ARG_DEF (condition_phi, i);
1201	*evolution_of_branch = chrec_dont_know;
1202
1203	/ Do not follow back edges (they must belong to an irreducible loop, which*
1204	we really do not want to worry about). /*
1205	if (backedge_phi_arg_p (condition_phi, i))
1206	return t_false;
1207
1208	if (TREE_CODE (branch) == SSA_NAME)
1209	{
1210	*evolution_of_branch = init_cond;
1211	return follow_ssa_edge (loop, SSA_NAME_DEF_STMT (branch), halting_phi,
1212	evolution_of_branch, limit);
1213	}
1214
1215	/ This case occurs when one of the condition branches sets*
1216	the variable to a constant: i.e. a phi-node like
1217	"a_2 = PHI <a_7(5), 2(6)>;".
1218
1219	FIXME: This case have to be refined correctly:
1220	in some cases it is possible to say something better than
1221	chrec_dont_know, for example using a wrap-around notation. /*
1222	return t_false;
1223	}
1224
1225	/ This function merges the branches of a condition-phi-node in a*
1226	loop. /*
1227
1228	static t_bool
1229	follow_ssa_edge_in_condition_phi (struct loop *loop,
1230	gphi *condition_phi,
1231	gphi *halting_phi,
1232	tree evolution_of_loop, int* limit)
1233	{
1234	int i, n;
1235	tree init = *evolution_of_loop;
1236	tree evolution_of_branch;
1237	t_bool res = follow_ssa_edge_in_condition_phi_branch (`0`, loop, condition_phi,
1238	halting_phi,
1239	&evolution_of_branch,
1240	init, limit);
1241	if (res == t_false \|\| res == t_dont_know)
1242	return res;
1243
1244	*evolution_of_loop = evolution_of_branch;
1245
1246	n = gimple_phi_num_args (condition_phi);
1247	for (i = `1`; i < n; i++)
1248	{
1249	/ Quickly give up when the evolution of one of the branches is*
1250	not known. /*
1251	if (*evolution_of_loop == chrec_dont_know)
1252	return t_true;
1253
1254	/ Increase the limit by the PHI argument number to avoid exponential*
1255	time and memory complexity. /*
1256	res = follow_ssa_edge_in_condition_phi_branch (i, loop, condition_phi,
1257	halting_phi,
1258	&evolution_of_branch,
1259	init, limit + i);
1260	if (res == t_false \|\| res == t_dont_know)
1261	return res;
1262
1263	evolution_of_loop = chrec_merge (evolution_of_loop,
1264	evolution_of_branch);
1265	}
1266
1267	return t_true;
1268	}
1269
1270	/ Follow an SSA edge in an inner loop. It computes the overall*
1271	effect of the loop, and following the symbolic initial conditions,
1272	it follows the edges in the parent loop. The inner loop is
1273	considered as a single statement. /*
1274
1275	static t_bool
1276	follow_ssa_edge_inner_loop_phi (struct loop *outer_loop,
1277	gphi *loop_phi_node,
1278	gphi *halting_phi,
1279	tree evolution_of_loop, int* limit)
1280	{
1281	struct loop *loop = loop_containing_stmt (loop_phi_node);
1282	tree ev = analyze_scalar_evolution (loop, PHI_RESULT (loop_phi_node));
1283
1284	/ Sometimes, the inner loop is too difficult to analyze, and the*
1285	result of the analysis is a symbolic parameter. /*
1286	if (ev == PHI_RESULT (loop_phi_node))
1287	{
1288	t_bool res = t_false;
1289	int i, n = gimple_phi_num_args (loop_phi_node);
1290
1291	for (i = `0`; i < n; i++)
1292	{
1293	tree arg = PHI_ARG_DEF (loop_phi_node, i);
1294	basic_block bb;
1295
1296	/ Follow the edges that exit the inner loop. /
1297	bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1298	if (!flow_bb_inside_loop_p (loop, bb))
1299	res = follow_ssa_edge_expr (outer_loop, loop_phi_node,
1300	arg, halting_phi,
1301	evolution_of_loop, limit);
1302	if (res == t_true)
1303	break;
1304	}
1305
1306	/ If the path crosses this loop-phi, give up. /
1307	if (res == t_true)
1308	*evolution_of_loop = chrec_dont_know;
1309
1310	return res;
1311	}
1312
1313	/ Otherwise, compute the overall effect of the inner loop. /
1314	ev = compute_overall_effect_of_inner_loop (loop, ev);
1315	return follow_ssa_edge_expr (outer_loop, loop_phi_node, ev, halting_phi,
1316	evolution_of_loop, limit);
1317	}
1318
1319	/ Follow an SSA edge from a loop-phi-node to itself, constructing a*
1320	path that is analyzed on the return walk. /*
1321
1322	static t_bool
1323	follow_ssa_edge (struct loop loop, gimple def, gphi *halting_phi,
1324	tree evolution_of_loop, int* limit)
1325	{
1326	struct loop *def_loop;
1327
1328	if (gimple_nop_p (def))
1329	return t_false;
1330
1331	/ Give up if the path is longer than the MAX that we allow. /
1332	if (limit > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_COMPLEXITY))
1333	return t_dont_know;
1334
1335	def_loop = loop_containing_stmt (def);
1336
1337	switch (gimple_code (def))
1338	{
1339	case GIMPLE_PHI:
1340	if (!loop_phi_node_p (def))
1341	/ DEF is a condition-phi-node. Follow the branches, and*
1342	record their evolutions. Finally, merge the collected
1343	information and set the approximation to the main
1344	variable. /*
1345	return follow_ssa_edge_in_condition_phi
1346	(loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1347	limit);
1348
1349	/ When the analyzed phi is the halting_phi, the*
1350	depth-first search is over: we have found a path from
1351	the halting_phi to itself in the loop. /*
1352	if (def == halting_phi)
1353	return t_true;
1354
1355	/ Otherwise, the evolution of the HALTING_PHI depends*
1356	on the evolution of another loop-phi-node, i.e. the
1357	evolution function is a higher degree polynomial. /*
1358	if (def_loop == loop)
1359	return t_false;
1360
1361	/ Inner loop. /
1362	if (flow_loop_nested_p (loop, def_loop))
1363	return follow_ssa_edge_inner_loop_phi
1364	(loop, as_a <gphi *> (def), halting_phi, evolution_of_loop,
1365	limit + `1`);
1366
1367	/ Outer loop. /
1368	return t_false;
1369
1370	case GIMPLE_ASSIGN:
1371	return follow_ssa_edge_in_rhs (loop, def, halting_phi,
1372	evolution_of_loop, limit);
1373
1374	default:
1375	/ At this level of abstraction, the program is just a set*
1376	of GIMPLE_ASSIGNs and PHI_NODEs. In principle there is no
1377	other node to be handled. /*
1378	return t_false;
1379	}
1380	}
1381
1382
1383	/ Simplify PEELED_CHREC represented by (init_cond, arg) in LOOP.*
1384	Handle below case and return the corresponding POLYNOMIAL_CHREC:
1385
1386	# i_17 = PHI <i_13(5), 0(3)>
1387	# _20 = PHI <_5(5), start_4(D)(3)>
1388	...
1389	i_13 = i_17 + 1;
1390	_5 = start_4(D) + i_13;
1391
1392	Though variable _20 appears as a PEELED_CHREC in the form of
1393	(start_4, _5)_LOOP, it's a POLYNOMIAL_CHREC like {start_4, 1}_LOOP.
1394
1395	See PR41488. /*
1396
1397	static tree
1398	simplify_peeled_chrec (struct loop *loop, tree arg, tree init_cond)
1399	{
1400	aff_tree aff1, aff2;
1401	tree ev, left, right, type, step_val;
1402	hash_map<tree, name_expansion > peeled_chrec_map = NULL;
1403
1404	ev = instantiate_parameters (loop, analyze_scalar_evolution (loop, arg));
1405	if (ev == NULL_TREE \|\| TREE_CODE (ev) != POLYNOMIAL_CHREC)
1406	return chrec_dont_know;
1407
1408	left = CHREC_LEFT (ev);
1409	right = CHREC_RIGHT (ev);
1410	type = TREE_TYPE (left);
1411	step_val = chrec_fold_plus (type, init_cond, right);
1412
1413	/ Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP*
1414	if "left" equals to "init + right". /*
1415	if (operand_equal_p (left, step_val, `0`))
1416	{
1417	if (dump_file && (dump_flags & TDF_SCEV))
1418	fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1419
1420	return build_polynomial_chrec (loop->num, init_cond, right);
1421	}
1422
1423	/ Try harder to check if they are equal. /
1424	tree_to_aff_combination_expand (left, type, &aff1, &peeled_chrec_map);
1425	tree_to_aff_combination_expand (step_val, type, &aff2, &peeled_chrec_map);
1426	free_affine_expand_cache (&peeled_chrec_map);
1427	aff_combination_scale (&aff2, -`1`);
1428	aff_combination_add (&aff1, &aff2);
1429
1430	/ Transform (init, {left, right}_LOOP)_LOOP to {init, right}_LOOP*
1431	if "left" equals to "init + right". /*
1432	if (aff_combination_zero_p (&aff1))
1433	{
1434	if (dump_file && (dump_flags & TDF_SCEV))
1435	fprintf (dump_file, "Simplify PEELED_CHREC into POLYNOMIAL_CHREC.\n");
1436
1437	return build_polynomial_chrec (loop->num, init_cond, right);
1438	}
1439	return chrec_dont_know;
1440	}
1441
1442	/ Given a LOOP_PHI_NODE, this function determines the evolution*
1443	function from LOOP_PHI_NODE to LOOP_PHI_NODE in the loop. /*
1444
1445	static tree
1446	analyze_evolution_in_loop (gphi *loop_phi_node,
1447	tree init_cond)
1448	{
1449	int i, n = gimple_phi_num_args (loop_phi_node);
1450	tree evolution_function = chrec_not_analyzed_yet;
1451	struct loop *loop = loop_containing_stmt (loop_phi_node);
1452	basic_block bb;
1453	static bool simplify_peeled_chrec_p = true;
1454
1455	if (dump_file && (dump_flags & TDF_SCEV))
1456	{
1457	fprintf (dump_file, "(analyze_evolution_in_loop \n");
1458	fprintf (dump_file, " (loop_phi_node = ");
1459	print_gimple_stmt (dump_file, loop_phi_node, `0`);
1460	fprintf (dump_file, ")\n");
1461	}
1462
1463	for (i = `0`; i < n; i++)
1464	{
1465	tree arg = PHI_ARG_DEF (loop_phi_node, i);
1466	gimple *ssa_chain;
1467	tree ev_fn;
1468	t_bool res;
1469
1470	/ Select the edges that enter the loop body. /
1471	bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1472	if (!flow_bb_inside_loop_p (loop, bb))
1473	continue;
1474
1475	if (TREE_CODE (arg) == SSA_NAME)
1476	{
1477	bool val = false;
1478
1479	ssa_chain = SSA_NAME_DEF_STMT (arg);
1480
1481	/ Pass in the initial condition to the follow edge function. /
1482	ev_fn = init_cond;
1483	res = follow_ssa_edge (loop, ssa_chain, loop_phi_node, &ev_fn, `0`);
1484
1485	/ If ev_fn has no evolution in the inner loop, and the*
1486	init_cond is not equal to ev_fn, then we have an
1487	ambiguity between two possible values, as we cannot know
1488	the number of iterations at this point. /*
1489	if (TREE_CODE (ev_fn) != POLYNOMIAL_CHREC
1490	&& no_evolution_in_loop_p (ev_fn, loop->num, &val) && val
1491	&& !operand_equal_p (init_cond, ev_fn, `0`))
1492	ev_fn = chrec_dont_know;
1493	}
1494	else
1495	res = t_false;
1496
1497	/ When it is impossible to go back on the same*
1498	loop_phi_node by following the ssa edges, the
1499	evolution is represented by a peeled chrec, i.e. the
1500	first iteration, EV_FN has the value INIT_COND, then
1501	all the other iterations it has the value of ARG.
1502	For the moment, PEELED_CHREC nodes are not built. /*
1503	if (res != t_true)
1504	{
1505	ev_fn = chrec_dont_know;
1506	/ Try to recognize POLYNOMIAL_CHREC which appears in*
1507	the form of PEELED_CHREC, but guard the process with
1508	a bool variable to keep the analyzer from infinite
1509	recurrence for real PEELED_RECs. /*
1510	if (simplify_peeled_chrec_p && TREE_CODE (arg) == SSA_NAME)
1511	{
1512	simplify_peeled_chrec_p = false;
1513	ev_fn = simplify_peeled_chrec (loop, arg, init_cond);
1514	simplify_peeled_chrec_p = true;
1515	}
1516	}
1517
1518	/ When there are multiple back edges of the loop (which in fact never*
1519	happens currently, but nevertheless), merge their evolutions. /*
1520	evolution_function = chrec_merge (evolution_function, ev_fn);
1521
1522	if (evolution_function == chrec_dont_know)
1523	break;
1524	}
1525
1526	if (dump_file && (dump_flags & TDF_SCEV))
1527	{
1528	fprintf (dump_file, " (evolution_function = ");
1529	print_generic_expr (dump_file, evolution_function);
1530	fprintf (dump_file, "))\n");
1531	}
1532
1533	return evolution_function;
1534	}
1535
1536	/ Looks to see if VAR is a copy of a constant (via straightforward assignments*
1537	or degenerate phi's). If so, returns the constant; else, returns VAR. /*
1538
1539	static tree
1540	follow_copies_to_constant (tree var)
1541	{
1542	tree res = var;
1543	while (TREE_CODE (res) == SSA_NAME)
1544	{
1545	gimple *def = SSA_NAME_DEF_STMT (res);
1546	if (gphi phi = dyn_cast <gphi > (def))
1547	{
1548	if (tree rhs = degenerate_phi_result (phi))
1549	res = rhs;
1550	else
1551	break;
1552	}
1553	else if (gimple_assign_single_p (def))
1554	/ Will exit loop if not an SSA_NAME. /
1555	res = gimple_assign_rhs1 (def);
1556	else
1557	break;
1558	}
1559	if (CONSTANT_CLASS_P (res))
1560	return res;
1561	return var;
1562	}
1563
1564	/ Given a loop-phi-node, return the initial conditions of the*
1565	variable on entry of the loop. When the CCP has propagated
1566	constants into the loop-phi-node, the initial condition is
1567	instantiated, otherwise the initial condition is kept symbolic.
1568	This analyzer does not analyze the evolution outside the current
1569	loop, and leaves this task to the on-demand tree reconstructor. /*
1570
1571	static tree
1572	analyze_initial_condition (gphi *loop_phi_node)
1573	{
1574	int i, n;
1575	tree init_cond = chrec_not_analyzed_yet;
1576	struct loop *loop = loop_containing_stmt (loop_phi_node);
1577
1578	if (dump_file && (dump_flags & TDF_SCEV))
1579	{
1580	fprintf (dump_file, "(analyze_initial_condition \n");
1581	fprintf (dump_file, " (loop_phi_node = \n");
1582	print_gimple_stmt (dump_file, loop_phi_node, `0`);
1583	fprintf (dump_file, ")\n");
1584	}
1585
1586	n = gimple_phi_num_args (loop_phi_node);
1587	for (i = `0`; i < n; i++)
1588	{
1589	tree branch = PHI_ARG_DEF (loop_phi_node, i);
1590	basic_block bb = gimple_phi_arg_edge (loop_phi_node, i)->src;
1591
1592	/ When the branch is oriented to the loop's body, it does*
1593	not contribute to the initial condition. /*
1594	if (flow_bb_inside_loop_p (loop, bb))
1595	continue;
1596
1597	if (init_cond == chrec_not_analyzed_yet)
1598	{
1599	init_cond = branch;
1600	continue;
1601	}
1602
1603	if (TREE_CODE (branch) == SSA_NAME)
1604	{
1605	init_cond = chrec_dont_know;
1606	break;
1607	}
1608
1609	init_cond = chrec_merge (init_cond, branch);
1610	}
1611
1612	/ Ooops -- a loop without an entry??? /
1613	if (init_cond == chrec_not_analyzed_yet)
1614	init_cond = chrec_dont_know;
1615
1616	/ We may not have fully constant propagated IL. Handle degenerate PHIs here*
1617	to not miss important early loop unrollings. /*
1618	init_cond = follow_copies_to_constant (init_cond);
1619
1620	if (dump_file && (dump_flags & TDF_SCEV))
1621	{
1622	fprintf (dump_file, " (init_cond = ");
1623	print_generic_expr (dump_file, init_cond);
1624	fprintf (dump_file, "))\n");
1625	}
1626
1627	return init_cond;
1628	}
1629
1630	/ Analyze the scalar evolution for LOOP_PHI_NODE. /
1631
1632	static tree
1633	interpret_loop_phi (struct loop loop, gphi loop_phi_node)
1634	{
1635	tree res;
1636	struct loop *phi_loop = loop_containing_stmt (loop_phi_node);
1637	tree init_cond;
1638
1639	gcc_assert (phi_loop == loop);
1640
1641	/ Otherwise really interpret the loop phi. /
1642	init_cond = analyze_initial_condition (loop_phi_node);
1643	res = analyze_evolution_in_loop (loop_phi_node, init_cond);
1644
1645	/ Verify we maintained the correct initial condition throughout*
1646	possible conversions in the SSA chain. /*
1647	if (res != chrec_dont_know)
1648	{
1649	tree new_init = res;
1650	if (CONVERT_EXPR_P (res)
1651	&& TREE_CODE (TREE_OPERAND (res, `0`)) == POLYNOMIAL_CHREC)
1652	new_init = fold_convert (TREE_TYPE (res),
1653	CHREC_LEFT (TREE_OPERAND (res, `0`)));
1654	else if (TREE_CODE (res) == POLYNOMIAL_CHREC)
1655	new_init = CHREC_LEFT (res);
1656	STRIP_USELESS_TYPE_CONVERSION (new_init);
1657	if (TREE_CODE (new_init) == POLYNOMIAL_CHREC
1658	\|\| !operand_equal_p (init_cond, new_init, `0`))
1659	return chrec_dont_know;
1660	}
1661
1662	return res;
1663	}
1664
1665	/ This function merges the branches of a condition-phi-node,*
1666	contained in the outermost loop, and whose arguments are already
1667	analyzed. /*
1668
1669	static tree
1670	interpret_condition_phi (struct loop loop, gphi condition_phi)
1671	{
1672	int i, n = gimple_phi_num_args (condition_phi);
1673	tree res = chrec_not_analyzed_yet;
1674
1675	for (i = `0`; i < n; i++)
1676	{
1677	tree branch_chrec;
1678
1679	if (backedge_phi_arg_p (condition_phi, i))
1680	{
1681	res = chrec_dont_know;
1682	break;
1683	}
1684
1685	branch_chrec = analyze_scalar_evolution
1686	(loop, PHI_ARG_DEF (condition_phi, i));
1687
1688	res = chrec_merge (res, branch_chrec);
1689	if (res == chrec_dont_know)
1690	break;
1691	}
1692
1693	return res;
1694	}
1695
1696	/ Interpret the operation RHS1 OP RHS2. If we didn't*
1697	analyze this node before, follow the definitions until ending
1698	either on an analyzed GIMPLE_ASSIGN, or on a loop-phi-node. On the
1699	return path, this function propagates evolutions (ala constant copy
1700	propagation). OPND1 is not a GIMPLE expression because we could
1701	analyze the effect of an inner loop: see interpret_loop_phi. /*
1702
1703	static tree
1704	interpret_rhs_expr (struct loop loop, gimple at_stmt,
1705	tree type, tree rhs1, enum tree_code code, tree rhs2)
1706	{
1707	tree res, chrec1, chrec2, ctype;
1708	gimple *def;
1709
1710	if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS)
1711	{
1712	if (is_gimple_min_invariant (rhs1))
1713	return chrec_convert (type, rhs1, at_stmt);
1714
1715	if (code == SSA_NAME)
1716	return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1717	at_stmt);
1718
1719	if (code == ASSERT_EXPR)
1720	{
1721	rhs1 = ASSERT_EXPR_VAR (rhs1);
1722	return chrec_convert (type, analyze_scalar_evolution (loop, rhs1),
1723	at_stmt);
1724	}
1725	}
1726
1727	switch (code)
1728	{
1729	case ADDR_EXPR:
1730	if (TREE_CODE (TREE_OPERAND (rhs1, `0`)) == MEM_REF
1731	\|\| handled_component_p (TREE_OPERAND (rhs1, `0`)))
1732	{
1733	machine_mode mode;
1734	HOST_WIDE_INT bitsize, bitpos;
1735	int unsignedp, reversep;
1736	int volatilep = `0`;
1737	tree base, offset;
1738	tree chrec3;
1739	tree unitpos;
1740
1741	base = get_inner_reference (TREE_OPERAND (rhs1, `0`),
1742	&bitsize, &bitpos, &offset, &mode,
1743	&unsignedp, &reversep, &volatilep);
1744
1745	if (TREE_CODE (base) == MEM_REF)
1746	{
1747	rhs2 = TREE_OPERAND (base, `1`);
1748	rhs1 = TREE_OPERAND (base, `0`);
1749
1750	chrec1 = analyze_scalar_evolution (loop, rhs1);
1751	chrec2 = analyze_scalar_evolution (loop, rhs2);
1752	chrec1 = chrec_convert (type, chrec1, at_stmt);
1753	chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1754	chrec1 = instantiate_parameters (loop, chrec1);
1755	chrec2 = instantiate_parameters (loop, chrec2);
1756	res = chrec_fold_plus (type, chrec1, chrec2);
1757	}
1758	else
1759	{
1760	chrec1 = analyze_scalar_evolution_for_address_of (loop, base);
1761	chrec1 = chrec_convert (type, chrec1, at_stmt);
1762	res = chrec1;
1763	}
1764
1765	if (offset != NULL_TREE)
1766	{
1767	chrec2 = analyze_scalar_evolution (loop, offset);
1768	chrec2 = chrec_convert (TREE_TYPE (offset), chrec2, at_stmt);
1769	chrec2 = instantiate_parameters (loop, chrec2);
1770	res = chrec_fold_plus (type, res, chrec2);
1771	}
1772
1773	if (bitpos != `0`)
1774	{
1775	gcc_assert ((bitpos % BITS_PER_UNIT) == `0`);
1776
1777	unitpos = size_int (bitpos / BITS_PER_UNIT);
1778	chrec3 = analyze_scalar_evolution (loop, unitpos);
1779	chrec3 = chrec_convert (TREE_TYPE (unitpos), chrec3, at_stmt);
1780	chrec3 = instantiate_parameters (loop, chrec3);
1781	res = chrec_fold_plus (type, res, chrec3);
1782	}
1783	}
1784	else
1785	res = chrec_dont_know;
1786	break;
1787
1788	case POINTER_PLUS_EXPR:
1789	chrec1 = analyze_scalar_evolution (loop, rhs1);
1790	chrec2 = analyze_scalar_evolution (loop, rhs2);
1791	chrec1 = chrec_convert (type, chrec1, at_stmt);
1792	chrec2 = chrec_convert (TREE_TYPE (rhs2), chrec2, at_stmt);
1793	chrec1 = instantiate_parameters (loop, chrec1);
1794	chrec2 = instantiate_parameters (loop, chrec2);
1795	res = chrec_fold_plus (type, chrec1, chrec2);
1796	break;
1797
1798	case PLUS_EXPR:
1799	chrec1 = analyze_scalar_evolution (loop, rhs1);
1800	chrec2 = analyze_scalar_evolution (loop, rhs2);
1801	ctype = type;
1802	/ When the stmt is conditionally executed re-write the CHREC*
1803	into a form that has well-defined behavior on overflow. /*
1804	if (at_stmt
1805	&& INTEGRAL_TYPE_P (type)
1806	&& ! TYPE_OVERFLOW_WRAPS (type)
1807	&& ! dominated_by_p (CDI_DOMINATORS, loop->latch,
1808	gimple_bb (at_stmt)))
1809	ctype = unsigned_type_for (type);
1810	chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1811	chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1812	chrec1 = instantiate_parameters (loop, chrec1);
1813	chrec2 = instantiate_parameters (loop, chrec2);
1814	res = chrec_fold_plus (ctype, chrec1, chrec2);
1815	if (type != ctype)
1816	res = chrec_convert (type, res, at_stmt);
1817	break;
1818
1819	case MINUS_EXPR:
1820	chrec1 = analyze_scalar_evolution (loop, rhs1);
1821	chrec2 = analyze_scalar_evolution (loop, rhs2);
1822	ctype = type;
1823	/ When the stmt is conditionally executed re-write the CHREC*
1824	into a form that has well-defined behavior on overflow. /*
1825	if (at_stmt
1826	&& INTEGRAL_TYPE_P (type)
1827	&& ! TYPE_OVERFLOW_WRAPS (type)
1828	&& ! dominated_by_p (CDI_DOMINATORS,
1829	loop->latch, gimple_bb (at_stmt)))
1830	ctype = unsigned_type_for (type);
1831	chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1832	chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1833	chrec1 = instantiate_parameters (loop, chrec1);
1834	chrec2 = instantiate_parameters (loop, chrec2);
1835	res = chrec_fold_minus (ctype, chrec1, chrec2);
1836	if (type != ctype)
1837	res = chrec_convert (type, res, at_stmt);
1838	break;
1839
1840	case NEGATE_EXPR:
1841	chrec1 = analyze_scalar_evolution (loop, rhs1);
1842	ctype = type;
1843	/ When the stmt is conditionally executed re-write the CHREC*
1844	into a form that has well-defined behavior on overflow. /*
1845	if (at_stmt
1846	&& INTEGRAL_TYPE_P (type)
1847	&& ! TYPE_OVERFLOW_WRAPS (type)
1848	&& ! dominated_by_p (CDI_DOMINATORS,
1849	loop->latch, gimple_bb (at_stmt)))
1850	ctype = unsigned_type_for (type);
1851	chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1852	/ TYPE may be integer, real or complex, so use fold_convert. /
1853	chrec1 = instantiate_parameters (loop, chrec1);
1854	res = chrec_fold_multiply (ctype, chrec1,
1855	fold_convert (ctype, integer_minus_one_node));
1856	if (type != ctype)
1857	res = chrec_convert (type, res, at_stmt);
1858	break;
1859
1860	case BIT_NOT_EXPR:
1861	/ Handle ~X as -1 - X. /
1862	chrec1 = analyze_scalar_evolution (loop, rhs1);
1863	chrec1 = chrec_convert (type, chrec1, at_stmt);
1864	chrec1 = instantiate_parameters (loop, chrec1);
1865	res = chrec_fold_minus (type,
1866	fold_convert (type, integer_minus_one_node),
1867	chrec1);
1868	break;
1869
1870	case MULT_EXPR:
1871	chrec1 = analyze_scalar_evolution (loop, rhs1);
1872	chrec2 = analyze_scalar_evolution (loop, rhs2);
1873	ctype = type;
1874	/ When the stmt is conditionally executed re-write the CHREC*
1875	into a form that has well-defined behavior on overflow. /*
1876	if (at_stmt
1877	&& INTEGRAL_TYPE_P (type)
1878	&& ! TYPE_OVERFLOW_WRAPS (type)
1879	&& ! dominated_by_p (CDI_DOMINATORS,
1880	loop->latch, gimple_bb (at_stmt)))
1881	ctype = unsigned_type_for (type);
1882	chrec1 = chrec_convert (ctype, chrec1, at_stmt);
1883	chrec2 = chrec_convert (ctype, chrec2, at_stmt);
1884	chrec1 = instantiate_parameters (loop, chrec1);
1885	chrec2 = instantiate_parameters (loop, chrec2);
1886	res = chrec_fold_multiply (ctype, chrec1, chrec2);
1887	if (type != ctype)
1888	res = chrec_convert (type, res, at_stmt);
1889	break;
1890
1891	case LSHIFT_EXPR:
1892	{
1893	/ Handle A<<B as A * (1<<B). /
1894	tree uns = unsigned_type_for (type);
1895	chrec1 = analyze_scalar_evolution (loop, rhs1);
1896	chrec2 = analyze_scalar_evolution (loop, rhs2);
1897	chrec1 = chrec_convert (uns, chrec1, at_stmt);
1898	chrec1 = instantiate_parameters (loop, chrec1);
1899	chrec2 = instantiate_parameters (loop, chrec2);
1900
1901	tree one = build_int_cst (uns, `1`);
1902	chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2);
1903	res = chrec_fold_multiply (uns, chrec1, chrec2);
1904	res = chrec_convert (type, res, at_stmt);
1905	}
1906	break;
1907
1908	CASE_CONVERT:
1909	/ In case we have a truncation of a widened operation that in*
1910	the truncated type has undefined overflow behavior analyze
1911	the operation done in an unsigned type of the same precision
1912	as the final truncation. We cannot derive a scalar evolution
1913	for the widened operation but for the truncated result. /*
1914	if (TREE_CODE (type) == INTEGER_TYPE
1915	&& TREE_CODE (TREE_TYPE (rhs1)) == INTEGER_TYPE
1916	&& TYPE_PRECISION (type) < TYPE_PRECISION (TREE_TYPE (rhs1))
1917	&& TYPE_OVERFLOW_UNDEFINED (type)
1918	&& TREE_CODE (rhs1) == SSA_NAME
1919	&& (def = SSA_NAME_DEF_STMT (rhs1))
1920	&& is_gimple_assign (def)
1921	&& TREE_CODE_CLASS (gimple_assign_rhs_code (def)) == tcc_binary
1922	&& TREE_CODE (gimple_assign_rhs2 (def)) == INTEGER_CST)
1923	{
1924	tree utype = unsigned_type_for (type);
1925	chrec1 = interpret_rhs_expr (loop, at_stmt, utype,
1926	gimple_assign_rhs1 (def),
1927	gimple_assign_rhs_code (def),
1928	gimple_assign_rhs2 (def));
1929	}
1930	else
1931	chrec1 = analyze_scalar_evolution (loop, rhs1);
1932	res = chrec_convert (type, chrec1, at_stmt, true, rhs1);
1933	break;
1934
1935	case BIT_AND_EXPR:
1936	/ Given int variable A, handle A&0xffff as (int)(unsigned short)A.*
1937	If A is SCEV and its value is in the range of representable set
1938	of type unsigned short, the result expression is a (no-overflow)
1939	SCEV. /*
1940	res = chrec_dont_know;
1941	if (tree_fits_uhwi_p (rhs2))
1942	{
1943	int precision;
1944	unsigned HOST_WIDE_INT val = tree_to_uhwi (rhs2);
1945
1946	val ++;
1947	/ Skip if value of rhs2 wraps in unsigned HOST_WIDE_INT or*
1948	it's not the maximum value of a smaller type than rhs1. /*
1949	if (val != `0`
1950	&& (precision = exact_log2 (val)) > `0`
1951	&& (unsigned) precision < TYPE_PRECISION (TREE_TYPE (rhs1)))
1952	{
1953	tree utype = build_nonstandard_integer_type (precision, `1`);
1954
1955	if (TYPE_PRECISION (utype) < TYPE_PRECISION (TREE_TYPE (rhs1)))
1956	{
1957	chrec1 = analyze_scalar_evolution (loop, rhs1);
1958	chrec1 = chrec_convert (utype, chrec1, at_stmt);
1959	res = chrec_convert (TREE_TYPE (rhs1), chrec1, at_stmt);
1960	}
1961	}
1962	}
1963	break;
1964
1965	default:
1966	res = chrec_dont_know;
1967	break;
1968	}
1969
1970	return res;
1971	}
1972
1973	/ Interpret the expression EXPR. /
1974
1975	static tree
1976	interpret_expr (struct loop loop, gimple at_stmt, tree expr)
1977	{
1978	enum tree_code code;
1979	tree type = TREE_TYPE (expr), op0, op1;
1980
1981	if (automatically_generated_chrec_p (expr))
1982	return expr;
1983
1984	if (TREE_CODE (expr) == POLYNOMIAL_CHREC
1985	\|\| get_gimple_rhs_class (TREE_CODE (expr)) == GIMPLE_TERNARY_RHS)
1986	return chrec_dont_know;
1987
1988	extract_ops_from_tree (expr, &code, &op0, &op1);
1989
1990	return interpret_rhs_expr (loop, at_stmt, type,
1991	op0, code, op1);
1992	}
1993
1994	/ Interpret the rhs of the assignment STMT. /
1995
1996	static tree
1997	interpret_gimple_assign (struct loop loop, gimple stmt)
1998	{
1999	tree type = TREE_TYPE (gimple_assign_lhs (stmt));
2000	enum tree_code code = gimple_assign_rhs_code (stmt);
2001
2002	return interpret_rhs_expr (loop, stmt, type,
2003	gimple_assign_rhs1 (stmt), code,
2004	gimple_assign_rhs2 (stmt));
2005	}
2006
2007
2008
2009	/ This section contains all the entry points:*
2010	- number_of_iterations_in_loop,
2011	- analyze_scalar_evolution,
2012	- instantiate_parameters.
2013	*/
2014
2015	/ Helper recursive function. /
2016
2017	static tree
2018	analyze_scalar_evolution_1 (struct loop *loop, tree var)
2019	{
2020	gimple *def;
2021	basic_block bb;
2022	struct loop *def_loop;
2023	tree res;
2024
2025	if (TREE_CODE (var) != SSA_NAME)
2026	return interpret_expr (loop, NULL, var);
2027
2028	def = SSA_NAME_DEF_STMT (var);
2029	bb = gimple_bb (def);
2030	def_loop = bb->loop_father;
2031
2032	if (!flow_bb_inside_loop_p (loop, bb))
2033	{
2034	/ Keep symbolic form, but look through obvious copies for constants. /
2035	res = follow_copies_to_constant (var);
2036	goto set_and_end;
2037	}
2038
2039	if (loop != def_loop)
2040	{
2041	res = analyze_scalar_evolution_1 (def_loop, var);
2042	struct loop *loop_to_skip = superloop_at_depth (def_loop,
2043	loop_depth (loop) + `1`);
2044	res = compute_overall_effect_of_inner_loop (loop_to_skip, res);
2045	if (chrec_contains_symbols_defined_in_loop (res, loop->num))
2046	res = analyze_scalar_evolution_1 (loop, res);
2047	goto set_and_end;
2048	}
2049
2050	switch (gimple_code (def))
2051	{
2052	case GIMPLE_ASSIGN:
2053	res = interpret_gimple_assign (loop, def);
2054	break;
2055
2056	case GIMPLE_PHI:
2057	if (loop_phi_node_p (def))
2058	res = interpret_loop_phi (loop, as_a <gphi *> (def));
2059	else
2060	res = interpret_condition_phi (loop, as_a <gphi *> (def));
2061	break;
2062
2063	default:
2064	res = chrec_dont_know;
2065	break;
2066	}
2067
2068	set_and_end:
2069
2070	/ Keep the symbolic form. /
2071	if (res == chrec_dont_know)
2072	res = var;
2073
2074	if (loop == def_loop)
2075	set_scalar_evolution (block_before_loop (loop), var, res);
2076
2077	return res;
2078	}
2079
2080	/ Analyzes and returns the scalar evolution of the ssa_name VAR in*
2081	LOOP. LOOP is the loop in which the variable is used.
2082
2083	Example of use: having a pointer VAR to a SSA_NAME node, STMT a
2084	pointer to the statement that uses this variable, in order to
2085	determine the evolution function of the variable, use the following
2086	calls:
2087
2088	loop_p loop = loop_containing_stmt (stmt);
2089	tree chrec_with_symbols = analyze_scalar_evolution (loop, var);
2090	tree chrec_instantiated = instantiate_parameters (loop, chrec_with_symbols);
2091	*/
2092
2093	tree
2094	analyze_scalar_evolution (struct loop *loop, tree var)
2095	{
2096	tree res;
2097
2098	/ ??? Fix callers. /
2099	if (! loop)
2100	return var;
2101
2102	if (dump_file && (dump_flags & TDF_SCEV))
2103	{
2104	fprintf (dump_file, "(analyze_scalar_evolution \n");
2105	fprintf (dump_file, " (loop_nb = %d)\n", loop->num);
2106	fprintf (dump_file, " (scalar = ");
2107	print_generic_expr (dump_file, var);
2108	fprintf (dump_file, ")\n");
2109	}
2110
2111	res = get_scalar_evolution (block_before_loop (loop), var);
2112	if (res == chrec_not_analyzed_yet)
2113	res = analyze_scalar_evolution_1 (loop, var);
2114
2115	if (dump_file && (dump_flags & TDF_SCEV))
2116	fprintf (dump_file, ")\n");
2117
2118	return res;
2119	}
2120
2121	/ Analyzes and returns the scalar evolution of VAR address in LOOP. /
2122
2123	static tree
2124	analyze_scalar_evolution_for_address_of (struct loop *loop, tree var)
2125	{
2126	return analyze_scalar_evolution (loop, build_fold_addr_expr (var));
2127	}
2128
2129	/ Analyze scalar evolution of use of VERSION in USE_LOOP with respect to*
2130	WRTO_LOOP (which should be a superloop of USE_LOOP)
2131
2132	FOLDED_CASTS is set to true if resolve_mixers used
2133	chrec_convert_aggressive (TODO -- not really, we are way too conservative
2134	at the moment in order to keep things simple).
2135
2136	To illustrate the meaning of USE_LOOP and WRTO_LOOP, consider the following
2137	example:
2138
2139	for (i = 0; i < 100; i++) -- loop 1
2140	{
2141	for (j = 0; j < 100; j++) -- loop 2
2142	{
2143	k1 = i;
2144	k2 = j;
2145
2146	use2 (k1, k2);
2147
2148	for (t = 0; t < 100; t++) -- loop 3
2149	use3 (k1, k2);
2150
2151	}
2152	use1 (k1, k2);
2153	}
2154
2155	Both k1 and k2 are invariants in loop3, thus
2156	analyze_scalar_evolution_in_loop (loop3, loop3, k1) = k1
2157	analyze_scalar_evolution_in_loop (loop3, loop3, k2) = k2
2158
2159	As they are invariant, it does not matter whether we consider their
2160	usage in loop 3 or loop 2, hence
2161	analyze_scalar_evolution_in_loop (loop2, loop3, k1) =
2162	analyze_scalar_evolution_in_loop (loop2, loop2, k1) = i
2163	analyze_scalar_evolution_in_loop (loop2, loop3, k2) =
2164	analyze_scalar_evolution_in_loop (loop2, loop2, k2) = [0,+,1]_2
2165
2166	Similarly for their evolutions with respect to loop 1. The values of K2
2167	in the use in loop 2 vary independently on loop 1, thus we cannot express
2168	the evolution with respect to loop 1:
2169	analyze_scalar_evolution_in_loop (loop1, loop3, k1) =
2170	analyze_scalar_evolution_in_loop (loop1, loop2, k1) = [0,+,1]_1
2171	analyze_scalar_evolution_in_loop (loop1, loop3, k2) =
2172	analyze_scalar_evolution_in_loop (loop1, loop2, k2) = dont_know
2173
2174	The value of k2 in the use in loop 1 is known, though:
2175	analyze_scalar_evolution_in_loop (loop1, loop1, k1) = [0,+,1]_1
2176	analyze_scalar_evolution_in_loop (loop1, loop1, k2) = 100
2177	*/
2178
2179	static tree
2180	analyze_scalar_evolution_in_loop (struct loop wrto_loop, struct* loop *use_loop,
2181	tree version, bool *folded_casts)
2182	{
2183	bool val = false;
2184	tree ev = version, tmp;
2185
2186	/ We cannot just do*
2187
2188	tmp = analyze_scalar_evolution (use_loop, version);
2189	ev = resolve_mixers (wrto_loop, tmp, folded_casts);
2190
2191	as resolve_mixers would query the scalar evolution with respect to
2192	wrto_loop. For example, in the situation described in the function
2193	comment, suppose that wrto_loop = loop1, use_loop = loop3 and
2194	version = k2. Then
2195
2196	analyze_scalar_evolution (use_loop, version) = k2
2197
2198	and resolve_mixers (loop1, k2, folded_casts) finds that the value of
2199	k2 in loop 1 is 100, which is a wrong result, since we are interested
2200	in the value in loop 3.
2201
2202	Instead, we need to proceed from use_loop to wrto_loop loop by loop,
2203	each time checking that there is no evolution in the inner loop. /*
2204
2205	if (folded_casts)
2206	folded_casts = false*;
2207	while (`1`)
2208	{
2209	tmp = analyze_scalar_evolution (use_loop, ev);
2210	ev = resolve_mixers (use_loop, tmp, folded_casts);
2211
2212	if (use_loop == wrto_loop)
2213	return ev;
2214
2215	/ If the value of the use changes in the inner loop, we cannot express*
2216	its value in the outer loop (we might try to return interval chrec,
2217	but we do not have a user for it anyway) /*
2218	if (!no_evolution_in_loop_p (ev, use_loop->num, &val)
2219	\|\| !val)
2220	return chrec_dont_know;
2221
2222	use_loop = loop_outer (use_loop);
2223	}
2224	}
2225
2226
2227	/ Hashtable helpers for a temporary hash-table used when*
2228	instantiating a CHREC or resolving mixers. For this use
2229	instantiated_below is always the same. /*
2230
2231	struct instantiate_cache_type
2232	{
2233	htab_t map;
2234	vec<scev_info_str> entries;
2235
2236	instantiate_cache_type () : map (NULL), entries (vNULL) {}
2237	~instantiate_cache_type ();
2238	tree get (unsigned slot) { return entries [slot].chrec; }
2239	void set (unsigned slot, tree chrec) { entries [slot].chrec = chrec; }
2240	};
2241
2242	instantiate_cache_type::~instantiate_cache_type ()
2243	{
2244	if (map != NULL)
2245	{
2246	htab_delete (map);
2247	entries.release ();
2248	}
2249	}
2250
2251	/ Cache to avoid infinite recursion when instantiating an SSA name.*
2252	Live during the outermost instantiate_scev or resolve_mixers call. /*
2253	static instantiate_cache_type *global_cache;
2254
2255	/ Computes a hash function for database element ELT. /
2256
2257	static inline hashval_t
2258	hash_idx_scev_info (const void *elt_)
2259	{
2260	unsigned idx = ((size_t) elt_) - `2`;
2261	return scev_info_hasher::hash (&global_cache->entries [idx]);
2262	}
2263
2264	/ Compares database elements E1 and E2. /
2265
2266	static inline int
2267	eq_idx_scev_info (const void e1, const* void *e2)
2268	{
2269	unsigned idx1 = ((size_t) e1) - `2`;
2270	return scev_info_hasher::equal (&global_cache->entries [idx1],
2271	(const scev_info_str *) e2);
2272	}
2273
2274	/ Returns from CACHE the slot number of the cached chrec for NAME. /
2275
2276	static unsigned
2277	get_instantiated_value_entry (instantiate_cache_type &cache,
2278	tree name, edge instantiate_below)
2279	{
2280	if (!cache.map)
2281	{
2282	cache.map = htab_create (`10`, hash_idx_scev_info, eq_idx_scev_info, NULL);
2283	cache.entries.create (`10`);
2284	}
2285
2286	scev_info_str e;
2287	e.name_version = SSA_NAME_VERSION (name);
2288	e.instantiated_below = instantiate_below->dest->index;
2289	void **slot = htab_find_slot_with_hash (cache.map, &e,
2290	scev_info_hasher::hash (&e), INSERT);
2291	if (!*slot)
2292	{
2293	e.chrec = chrec_not_analyzed_yet;
2294	slot = (void* *)(size_t)(cache.entries.length () + `2`);
2295	cache.entries.safe_push (e);
2296	}
2297
2298	return ((size_t)*slot) - `2`;
2299	}
2300
2301
2302	/ Return the closed_loop_phi node for VAR. If there is none, return*
2303	NULL_TREE. /*
2304
2305	static tree
2306	loop_closed_phi_def (tree var)
2307	{
2308	struct loop *loop;
2309	edge exit;
2310	gphi *phi;
2311	gphi_iterator psi;
2312
2313	if (var == NULL_TREE
2314	\|\| TREE_CODE (var) != SSA_NAME)
2315	return NULL_TREE;
2316
2317	loop = loop_containing_stmt (SSA_NAME_DEF_STMT (var));
2318	exit = single_exit (loop);
2319	if (!exit)
2320	return NULL_TREE;
2321
2322	for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); gsi_next (&psi))
2323	{
2324	phi = psi.phi ();
2325	if (PHI_ARG_DEF_FROM_EDGE (phi, exit) == var)
2326	return PHI_RESULT (phi);
2327	}
2328
2329	return NULL_TREE;
2330	}
2331
2332	static tree instantiate_scev_r (edge, struct loop , struct* loop *,
2333	tree, bool , int*);
2334
2335	/ Analyze all the parameters of the chrec, between INSTANTIATE_BELOW*
2336	and EVOLUTION_LOOP, that were left under a symbolic form.
2337
2338	CHREC is an SSA_NAME to be instantiated.
2339
2340	CACHE is the cache of already instantiated values.
2341
2342	Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2343	conversions that may wrap in signed/pointer type are folded, as long
2344	as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2345	then we don't do such fold.
2346
2347	SIZE_EXPR is used for computing the size of the expression to be
2348	instantiated, and to stop if it exceeds some limit. /*
2349
2350	static tree
2351	instantiate_scev_name (edge instantiate_below,
2352	struct loop evolution_loop, struct* loop *inner_loop,
2353	tree chrec,
2354	bool *fold_conversions,
2355	int size_expr)
2356	{
2357	tree res;
2358	struct loop *def_loop;
2359	basic_block def_bb = gimple_bb (SSA_NAME_DEF_STMT (chrec));
2360
2361	/ A parameter, nothing to do. /
2362	if (!def_bb
2363	\|\| !dominated_by_p (CDI_DOMINATORS, def_bb, instantiate_below->dest))
2364	return chrec;
2365
2366	/ We cache the value of instantiated variable to avoid exponential*
2367	time complexity due to reevaluations. We also store the convenient
2368	value in the cache in order to prevent infinite recursion -- we do
2369	not want to instantiate the SSA_NAME if it is in a mixer
2370	structure. This is used for avoiding the instantiation of
2371	recursively defined functions, such as:
2372
2373	\| a_2 -> {0, +, 1, +, a_2}_1 /*
2374
2375	unsigned si = get_instantiated_value_entry (*global_cache,
2376	chrec, instantiate_below);
2377	if (global_cache->get (si) != chrec_not_analyzed_yet)
2378	return global_cache->get (si);
2379
2380	/ On recursion return chrec_dont_know. /
2381	global_cache->set (si, chrec_dont_know);
2382
2383	def_loop = find_common_loop (evolution_loop, def_bb->loop_father);
2384
2385	if (! dominated_by_p (CDI_DOMINATORS,
2386	def_loop->header, instantiate_below->dest))
2387	{
2388	gimple *def = SSA_NAME_DEF_STMT (chrec);
2389	if (gassign ass = dyn_cast <gassign > (def))
2390	{
2391	switch (gimple_assign_rhs_class (ass))
2392	{
2393	case GIMPLE_UNARY_RHS:
2394	{
2395	tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2396	inner_loop, gimple_assign_rhs1 (ass),
2397	fold_conversions, size_expr);
2398	if (op0 == chrec_dont_know)
2399	return chrec_dont_know;
2400	res = fold_build1 (gimple_assign_rhs_code (ass),
2401	TREE_TYPE (chrec), op0);
2402	break;
2403	}
2404	case GIMPLE_BINARY_RHS:
2405	{
2406	tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2407	inner_loop, gimple_assign_rhs1 (ass),
2408	fold_conversions, size_expr);
2409	if (op0 == chrec_dont_know)
2410	return chrec_dont_know;
2411	tree op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2412	inner_loop, gimple_assign_rhs2 (ass),
2413	fold_conversions, size_expr);
2414	if (op1 == chrec_dont_know)
2415	return chrec_dont_know;
2416	res = fold_build2 (gimple_assign_rhs_code (ass),
2417	TREE_TYPE (chrec), op0, op1);
2418	break;
2419	}
2420	default:
2421	res = chrec_dont_know;
2422	}
2423	}
2424	else
2425	res = chrec_dont_know;
2426	global_cache->set (si, res);
2427	return res;
2428	}
2429
2430	/ If the analysis yields a parametric chrec, instantiate the*
2431	result again. /*
2432	res = analyze_scalar_evolution (def_loop, chrec);
2433
2434	/ Don't instantiate default definitions. /
2435	if (TREE_CODE (res) == SSA_NAME
2436	&& SSA_NAME_IS_DEFAULT_DEF (res))
2437	;
2438
2439	/ Don't instantiate loop-closed-ssa phi nodes. /
2440	else if (TREE_CODE (res) == SSA_NAME
2441	&& loop_depth (loop_containing_stmt (SSA_NAME_DEF_STMT (res)))
2442	> loop_depth (def_loop))
2443	{
2444	if (res == chrec)
2445	res = loop_closed_phi_def (chrec);
2446	else
2447	res = chrec;
2448
2449	/ When there is no loop_closed_phi_def, it means that the*
2450	variable is not used after the loop: try to still compute the
2451	value of the variable when exiting the loop. /*
2452	if (res == NULL_TREE)
2453	{
2454	loop_p loop = loop_containing_stmt (SSA_NAME_DEF_STMT (chrec));
2455	res = analyze_scalar_evolution (loop, chrec);
2456	res = compute_overall_effect_of_inner_loop (loop, res);
2457	res = instantiate_scev_r (instantiate_below, evolution_loop,
2458	inner_loop, res,
2459	fold_conversions, size_expr);
2460	}
2461	else if (dominated_by_p (CDI_DOMINATORS,
2462	gimple_bb (SSA_NAME_DEF_STMT (res)),
2463	instantiate_below->dest))
2464	res = chrec_dont_know;
2465	}
2466
2467	else if (res != chrec_dont_know)
2468	{
2469	if (inner_loop
2470	&& def_bb->loop_father != inner_loop
2471	&& !flow_loop_nested_p (def_bb->loop_father, inner_loop))
2472	/ ??? We could try to compute the overall effect of the loop here. /
2473	res = chrec_dont_know;
2474	else
2475	res = instantiate_scev_r (instantiate_below, evolution_loop,
2476	inner_loop, res,
2477	fold_conversions, size_expr);
2478	}
2479
2480	/ Store the correct value to the cache. /
2481	global_cache->set (si, res);
2482	return res;
2483	}
2484
2485	/ Analyze all the parameters of the chrec, between INSTANTIATE_BELOW*
2486	and EVOLUTION_LOOP, that were left under a symbolic form.
2487
2488	CHREC is a polynomial chain of recurrence to be instantiated.
2489
2490	CACHE is the cache of already instantiated values.
2491
2492	Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2493	conversions that may wrap in signed/pointer type are folded, as long
2494	as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2495	then we don't do such fold.
2496
2497	SIZE_EXPR is used for computing the size of the expression to be
2498	instantiated, and to stop if it exceeds some limit. /*
2499
2500	static tree
2501	instantiate_scev_poly (edge instantiate_below,
2502	struct loop evolution_loop, struct* loop *,
2503	tree chrec, bool fold_conversions, int* size_expr)
2504	{
2505	tree op1;
2506	tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2507	get_chrec_loop (chrec),
2508	CHREC_LEFT (chrec), fold_conversions,
2509	size_expr);
2510	if (op0 == chrec_dont_know)
2511	return chrec_dont_know;
2512
2513	op1 = instantiate_scev_r (instantiate_below, evolution_loop,
2514	get_chrec_loop (chrec),
2515	CHREC_RIGHT (chrec), fold_conversions,
2516	size_expr);
2517	if (op1 == chrec_dont_know)
2518	return chrec_dont_know;
2519
2520	if (CHREC_LEFT (chrec) != op0
2521	\|\| CHREC_RIGHT (chrec) != op1)
2522	{
2523	op1 = chrec_convert_rhs (chrec_type (op0), op1, NULL);
2524	chrec = build_polynomial_chrec (CHREC_VARIABLE (chrec), op0, op1);
2525	}
2526
2527	return chrec;
2528	}
2529
2530	/ Analyze all the parameters of the chrec, between INSTANTIATE_BELOW*
2531	and EVOLUTION_LOOP, that were left under a symbolic form.
2532
2533	"C0 CODE C1" is a binary expression of type TYPE to be instantiated.
2534
2535	CACHE is the cache of already instantiated values.
2536
2537	Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2538	conversions that may wrap in signed/pointer type are folded, as long
2539	as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2540	then we don't do such fold.
2541
2542	SIZE_EXPR is used for computing the size of the expression to be
2543	instantiated, and to stop if it exceeds some limit. /*
2544
2545	static tree
2546	instantiate_scev_binary (edge instantiate_below,
2547	struct loop evolution_loop, struct* loop *inner_loop,
2548	tree chrec, enum tree_code code,
2549	tree type, tree c0, tree c1,
2550	bool fold_conversions, int* size_expr)
2551	{
2552	tree op1;
2553	tree op0 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2554	c0, fold_conversions, size_expr);
2555	if (op0 == chrec_dont_know)
2556	return chrec_dont_know;
2557
2558	op1 = instantiate_scev_r (instantiate_below, evolution_loop, inner_loop,
2559	c1, fold_conversions, size_expr);
2560	if (op1 == chrec_dont_know)
2561	return chrec_dont_know;
2562
2563	if (c0 != op0
2564	\|\| c1 != op1)
2565	{
2566	op0 = chrec_convert (type, op0, NULL);
2567	op1 = chrec_convert_rhs (type, op1, NULL);
2568
2569	switch (code)
2570	{
2571	case POINTER_PLUS_EXPR:
2572	case PLUS_EXPR:
2573	return chrec_fold_plus (type, op0, op1);
2574
2575	case MINUS_EXPR:
2576	return chrec_fold_minus (type, op0, op1);
2577
2578	case MULT_EXPR:
2579	return chrec_fold_multiply (type, op0, op1);
2580
2581	default:
2582	gcc_unreachable ();
2583	}
2584	}
2585
2586	return chrec ? chrec : fold_build2 (code, type, c0, c1);
2587	}
2588
2589	/ Analyze all the parameters of the chrec, between INSTANTIATE_BELOW*
2590	and EVOLUTION_LOOP, that were left under a symbolic form.
2591
2592	"CHREC" that stands for a convert expression "(TYPE) OP" is to be
2593	instantiated.
2594
2595	CACHE is the cache of already instantiated values.
2596
2597	Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2598	conversions that may wrap in signed/pointer type are folded, as long
2599	as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2600	then we don't do such fold.
2601
2602	SIZE_EXPR is used for computing the size of the expression to be
2603	instantiated, and to stop if it exceeds some limit. /*
2604
2605	static tree
2606	instantiate_scev_convert (edge instantiate_below,
2607	struct loop evolution_loop, struct* loop *inner_loop,
2608	tree chrec, tree type, tree op,
2609	bool fold_conversions, int* size_expr)
2610	{
2611	tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2612	inner_loop, op,
2613	fold_conversions, size_expr);
2614
2615	if (op0 == chrec_dont_know)
2616	return chrec_dont_know;
2617
2618	if (fold_conversions)
2619	{
2620	tree tmp = chrec_convert_aggressive (type, op0, fold_conversions);
2621	if (tmp)
2622	return tmp;
2623
2624	/ If we used chrec_convert_aggressive, we can no longer assume that*
2625	signed chrecs do not overflow, as chrec_convert does, so avoid
2626	calling it in that case. /*
2627	if (*fold_conversions)
2628	{
2629	if (chrec && op0 == op)
2630	return chrec;
2631
2632	return fold_convert (type, op0);
2633	}
2634	}
2635
2636	return chrec_convert (type, op0, NULL);
2637	}
2638
2639	/ Analyze all the parameters of the chrec, between INSTANTIATE_BELOW*
2640	and EVOLUTION_LOOP, that were left under a symbolic form.
2641
2642	CHREC is a BIT_NOT_EXPR or a NEGATE_EXPR expression to be instantiated.
2643	Handle ~X as -1 - X.
2644	Handle -X as -1 X.*
2645
2646	CACHE is the cache of already instantiated values.
2647
2648	Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2649	conversions that may wrap in signed/pointer type are folded, as long
2650	as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2651	then we don't do such fold.
2652
2653	SIZE_EXPR is used for computing the size of the expression to be
2654	instantiated, and to stop if it exceeds some limit. /*
2655
2656	static tree
2657	instantiate_scev_not (edge instantiate_below,
2658	struct loop evolution_loop, struct* loop *inner_loop,
2659	tree chrec,
2660	enum tree_code code, tree type, tree op,
2661	bool fold_conversions, int* size_expr)
2662	{
2663	tree op0 = instantiate_scev_r (instantiate_below, evolution_loop,
2664	inner_loop, op,
2665	fold_conversions, size_expr);
2666
2667	if (op0 == chrec_dont_know)
2668	return chrec_dont_know;
2669
2670	if (op != op0)
2671	{
2672	op0 = chrec_convert (type, op0, NULL);
2673
2674	switch (code)
2675	{
2676	case BIT_NOT_EXPR:
2677	return chrec_fold_minus
2678	(type, fold_convert (type, integer_minus_one_node), op0);
2679
2680	case NEGATE_EXPR:
2681	return chrec_fold_multiply
2682	(type, fold_convert (type, integer_minus_one_node), op0);
2683
2684	default:
2685	gcc_unreachable ();
2686	}
2687	}
2688
2689	return chrec ? chrec : fold_build1 (code, type, op0);
2690	}
2691
2692	/ Analyze all the parameters of the chrec, between INSTANTIATE_BELOW*
2693	and EVOLUTION_LOOP, that were left under a symbolic form.
2694
2695	CHREC is the scalar evolution to instantiate.
2696
2697	CACHE is the cache of already instantiated values.
2698
2699	Variable pointed by FOLD_CONVERSIONS is set to TRUE when the
2700	conversions that may wrap in signed/pointer type are folded, as long
2701	as the value of the chrec is preserved. If FOLD_CONVERSIONS is NULL
2702	then we don't do such fold.
2703
2704	SIZE_EXPR is used for computing the size of the expression to be
2705	instantiated, and to stop if it exceeds some limit. /*
2706
2707	static tree
2708	instantiate_scev_r (edge instantiate_below,
2709	struct loop evolution_loop, struct* loop *inner_loop,
2710	tree chrec,
2711	bool fold_conversions, int* size_expr)
2712	{
2713	/ Give up if the expression is larger than the MAX that we allow. /
2714	if (size_expr++ > PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
2715	return chrec_dont_know;
2716
2717	if (chrec == NULL_TREE
2718	\|\| automatically_generated_chrec_p (chrec)
2719	\|\| is_gimple_min_invariant (chrec))
2720	return chrec;
2721
2722	switch (TREE_CODE (chrec))
2723	{
2724	case SSA_NAME:
2725	return instantiate_scev_name (instantiate_below, evolution_loop,
2726	inner_loop, chrec,
2727	fold_conversions, size_expr);
2728
2729	case POLYNOMIAL_CHREC:
2730	return instantiate_scev_poly (instantiate_below, evolution_loop,
2731	inner_loop, chrec,
2732	fold_conversions, size_expr);
2733
2734	case POINTER_PLUS_EXPR:
2735	case PLUS_EXPR:
2736	case MINUS_EXPR:
2737	case MULT_EXPR:
2738	return instantiate_scev_binary (instantiate_below, evolution_loop,
2739	inner_loop, chrec,
2740	TREE_CODE (chrec), chrec_type (chrec),
2741	TREE_OPERAND (chrec, `0`),
2742	TREE_OPERAND (chrec, `1`),
2743	fold_conversions, size_expr);
2744
2745	CASE_CONVERT:
2746	return instantiate_scev_convert (instantiate_below, evolution_loop,
2747	inner_loop, chrec,
2748	TREE_TYPE (chrec), TREE_OPERAND (chrec, `0`),
2749	fold_conversions, size_expr);
2750
2751	case NEGATE_EXPR:
2752	case BIT_NOT_EXPR:
2753	return instantiate_scev_not (instantiate_below, evolution_loop,
2754	inner_loop, chrec,
2755	TREE_CODE (chrec), TREE_TYPE (chrec),
2756	TREE_OPERAND (chrec, `0`),
2757	fold_conversions, size_expr);
2758
2759	case ADDR_EXPR:
2760	if (is_gimple_min_invariant (chrec))
2761	return chrec;
2762	/ Fallthru. /
2763	case SCEV_NOT_KNOWN:
2764	return chrec_dont_know;
2765
2766	case SCEV_KNOWN:
2767	return chrec_known;
2768
2769	default:
2770	if (CONSTANT_CLASS_P (chrec))
2771	return chrec;
2772	return chrec_dont_know;
2773	}
2774	}
2775
2776	/ Analyze all the parameters of the chrec that were left under a*
2777	symbolic form. INSTANTIATE_BELOW is the basic block that stops the
2778	recursive instantiation of parameters: a parameter is a variable
2779	that is defined in a basic block that dominates INSTANTIATE_BELOW or
2780	a function parameter. /*
2781
2782	tree
2783	instantiate_scev (edge instantiate_below, struct loop *evolution_loop,
2784	tree chrec)
2785	{
2786	tree res;
2787
2788	if (dump_file && (dump_flags & TDF_SCEV))
2789	{
2790	fprintf (dump_file, "(instantiate_scev \n");
2791	fprintf (dump_file, " (instantiate_below = %d -> %d)\n",
2792	instantiate_below->src->index, instantiate_below->dest->index);
2793	if (evolution_loop)
2794	fprintf (dump_file, " (evolution_loop = %d)\n", evolution_loop->num);
2795	fprintf (dump_file, " (chrec = ");
2796	print_generic_expr (dump_file, chrec);
2797	fprintf (dump_file, ")\n");
2798	}
2799
2800	bool destr = false;
2801	if (!global_cache)
2802	{
2803	global_cache = new instantiate_cache_type;
2804	destr = true;
2805	}
2806
2807	res = instantiate_scev_r (instantiate_below, evolution_loop,
2808	NULL, chrec, NULL, `0`);
2809
2810	if (destr)
2811	{
2812	delete global_cache;
2813	global_cache = NULL;
2814	}
2815
2816	if (dump_file && (dump_flags & TDF_SCEV))
2817	{
2818	fprintf (dump_file, " (res = ");
2819	print_generic_expr (dump_file, res);
2820	fprintf (dump_file, "))\n");
2821	}
2822
2823	return res;
2824	}
2825
2826	/ Similar to instantiate_parameters, but does not introduce the*
2827	evolutions in outer loops for LOOP invariants in CHREC, and does not
2828	care about causing overflows, as long as they do not affect value
2829	of an expression. /*
2830
2831	tree
2832	resolve_mixers (struct loop loop, tree chrec, bool* *folded_casts)
2833	{
2834	bool destr = false;
2835	bool fold_conversions = false;
2836	if (!global_cache)
2837	{
2838	global_cache = new instantiate_cache_type;
2839	destr = true;
2840	}
2841
2842	tree ret = instantiate_scev_r (loop_preheader_edge (loop), loop, NULL,
2843	chrec, &fold_conversions, `0`);
2844
2845	if (folded_casts && !*folded_casts)
2846	*folded_casts = fold_conversions;
2847
2848	if (destr)
2849	{
2850	delete global_cache;
2851	global_cache = NULL;
2852	}
2853
2854	return ret;
2855	}
2856
2857	/ Entry point for the analysis of the number of iterations pass.*
2858	This function tries to safely approximate the number of iterations
2859	the loop will run. When this property is not decidable at compile
2860	time, the result is chrec_dont_know. Otherwise the result is a
2861	scalar or a symbolic parameter. When the number of iterations may
2862	be equal to zero and the property cannot be determined at compile
2863	time, the result is a COND_EXPR that represents in a symbolic form
2864	the conditions under which the number of iterations is not zero.
2865
2866	Example of analysis: suppose that the loop has an exit condition:
2867
2868	"if (b > 49) goto end_loop;"
2869
2870	and that in a previous analysis we have determined that the
2871	variable 'b' has an evolution function:
2872
2873	"EF = {23, +, 5}_2".
2874
2875	When we evaluate the function at the point 5, i.e. the value of the
2876	variable 'b' after 5 iterations in the loop, we have EF (5) = 48,
2877	and EF (6) = 53. In this case the value of 'b' on exit is '53' and
2878	the loop body has been executed 6 times. /*
2879
2880	tree
2881	number_of_latch_executions (struct loop *loop)
2882	{
2883	edge exit;
2884	struct tree_niter_desc niter_desc;
2885	tree may_be_zero;
2886	tree res;
2887
2888	/ Determine whether the number of iterations in loop has already*
2889	been computed. /*
2890	res = loop->nb_iterations;
2891	if (res)
2892	return res;
2893
2894	may_be_zero = NULL_TREE;
2895
2896	if (dump_file && (dump_flags & TDF_SCEV))
2897	fprintf (dump_file, "(number_of_iterations_in_loop = \n");
2898
2899	res = chrec_dont_know;
2900	exit = single_exit (loop);
2901
2902	if (exit && number_of_iterations_exit (loop, exit, &niter_desc, false))
2903	{
2904	may_be_zero = niter_desc.may_be_zero;
2905	res = niter_desc.niter;
2906	}
2907
2908	if (res == chrec_dont_know
2909	\|\| !may_be_zero
2910	\|\| integer_zerop (may_be_zero))
2911	;
2912	else if (integer_nonzerop (may_be_zero))
2913	res = build_int_cst (TREE_TYPE (res), `0`);
2914
2915	else if (COMPARISON_CLASS_P (may_be_zero))
2916	res = fold_build3 (COND_EXPR, TREE_TYPE (res), may_be_zero,
2917	build_int_cst (TREE_TYPE (res), `0`), res);
2918	else
2919	res = chrec_dont_know;
2920
2921	if (dump_file && (dump_flags & TDF_SCEV))
2922	{
2923	fprintf (dump_file, " (set_nb_iterations_in_loop = ");
2924	print_generic_expr (dump_file, res);
2925	fprintf (dump_file, "))\n");
2926	}
2927
2928	loop->nb_iterations = res;
2929	return res;
2930	}
2931
2932
2933	/ Counters for the stats. /
2934
2935	struct chrec_stats
2936	{
2937	unsigned nb_chrecs;
2938	unsigned nb_affine;
2939	unsigned nb_affine_multivar;
2940	unsigned nb_higher_poly;
2941	unsigned nb_chrec_dont_know;
2942	unsigned nb_undetermined;
2943	};
2944
2945	/ Reset the counters. /
2946
2947	static inline void
2948	reset_chrecs_counters (struct chrec_stats *stats)
2949	{
2950	stats->nb_chrecs = `0`;
2951	stats->nb_affine = `0`;
2952	stats->nb_affine_multivar = `0`;
2953	stats->nb_higher_poly = `0`;
2954	stats->nb_chrec_dont_know = `0`;
2955	stats->nb_undetermined = `0`;
2956	}
2957
2958	/ Dump the contents of a CHREC_STATS structure. /
2959
2960	static void
2961	dump_chrecs_stats (FILE file, struct* chrec_stats *stats)
2962	{
2963	fprintf (file, "\n(\n");
2964	fprintf (file, "-----------------------------------------\n");
2965	fprintf (file, "%d\taffine univariate chrecs\n", stats->nb_affine);
2966	fprintf (file, "%d\taffine multivariate chrecs\n", stats->nb_affine_multivar);
2967	fprintf (file, "%d\tdegree greater than 2 polynomials\n",
2968	stats->nb_higher_poly);
2969	fprintf (file, "%d\tchrec_dont_know chrecs\n", stats->nb_chrec_dont_know);
2970	fprintf (file, "-----------------------------------------\n");
2971	fprintf (file, "%d\ttotal chrecs\n", stats->nb_chrecs);
2972	fprintf (file, "%d\twith undetermined coefficients\n",
2973	stats->nb_undetermined);
2974	fprintf (file, "-----------------------------------------\n");
2975	fprintf (file, "%d\tchrecs in the scev database\n",
2976	(int) scalar_evolution_info->elements ());
2977	fprintf (file, "%d\tsets in the scev database\n", nb_set_scev);
2978	fprintf (file, "%d\tgets in the scev database\n", nb_get_scev);
2979	fprintf (file, "-----------------------------------------\n");
2980	fprintf (file, ")\n\n");
2981	}
2982
2983	/ Gather statistics about CHREC. /
2984
2985	static void
2986	gather_chrec_stats (tree chrec, struct chrec_stats *stats)
2987	{
2988	if (dump_file && (dump_flags & TDF_STATS))
2989	{
2990	fprintf (dump_file, "(classify_chrec ");
2991	print_generic_expr (dump_file, chrec);
2992	fprintf (dump_file, "\n");
2993	}
2994
2995	stats->nb_chrecs++;
2996
2997	if (chrec == NULL_TREE)
2998	{
2999	stats->nb_undetermined++;
3000	return;
3001	}
3002
3003	switch (TREE_CODE (chrec))
3004	{
3005	case POLYNOMIAL_CHREC:
3006	if (evolution_function_is_affine_p (chrec))
3007	{
3008	if (dump_file && (dump_flags & TDF_STATS))
3009	fprintf (dump_file, " affine_univariate\n");
3010	stats->nb_affine++;
3011	}
3012	else if (evolution_function_is_affine_multivariate_p (chrec, `0`))
3013	{
3014	if (dump_file && (dump_flags & TDF_STATS))
3015	fprintf (dump_file, " affine_multivariate\n");
3016	stats->nb_affine_multivar++;
3017	}
3018	else
3019	{
3020	if (dump_file && (dump_flags & TDF_STATS))
3021	fprintf (dump_file, " higher_degree_polynomial\n");
3022	stats->nb_higher_poly++;
3023	}
3024
3025	break;
3026
3027	default:
3028	break;
3029	}
3030
3031	if (chrec_contains_undetermined (chrec))
3032	{
3033	if (dump_file && (dump_flags & TDF_STATS))
3034	fprintf (dump_file, " undetermined\n");
3035	stats->nb_undetermined++;
3036	}
3037
3038	if (dump_file && (dump_flags & TDF_STATS))
3039	fprintf (dump_file, ")\n");
3040	}
3041
3042	/ Classify the chrecs of the whole database. /
3043
3044	void
3045	gather_stats_on_scev_database (void)
3046	{
3047	struct chrec_stats stats;
3048
3049	if (!dump_file)
3050	return;
3051
3052	reset_chrecs_counters (&stats);
3053
3054	hash_table<scev_info_hasher>::iterator iter;
3055	scev_info_str *elt;
3056	FOR_EACH_HASH_TABLE_ELEMENT (scalar_evolution_info, elt, scev_info_str ,
3057	iter)
3058	gather_chrec_stats (elt->chrec, &stats);
3059
3060	dump_chrecs_stats (dump_file, &stats);
3061	}
3062
3063
3064
3065	/ Initializer. /
3066
3067	static void
3068	initialize_scalar_evolutions_analyzer (void)
3069	{
3070	/ The elements below are unique. /
3071	if (chrec_dont_know == NULL_TREE)
3072	{
3073	chrec_not_analyzed_yet = NULL_TREE;
3074	chrec_dont_know = make_node (SCEV_NOT_KNOWN);
3075	chrec_known = make_node (SCEV_KNOWN);
3076	TREE_TYPE (chrec_dont_know) = void_type_node;
3077	TREE_TYPE (chrec_known) = void_type_node;
3078	}
3079	}
3080
3081	/ Initialize the analysis of scalar evolutions for LOOPS. /
3082
3083	void
3084	scev_initialize (void)
3085	{
3086	struct loop *loop;
3087
3088	gcc_assert (! scev_initialized_p ());
3089
3090	scalar_evolution_info = hash_table<scev_info_hasher>::create_ggc (`100`);
3091
3092	initialize_scalar_evolutions_analyzer ();
3093
3094	FOR_EACH_LOOP (loop, `0`)
3095	{
3096	loop->nb_iterations = NULL_TREE;
3097	}
3098	}
3099
3100	/ Return true if SCEV is initialized. /
3101
3102	bool
3103	scev_initialized_p (void)
3104	{
3105	return scalar_evolution_info != NULL;
3106	}
3107
3108	/ Cleans up the information cached by the scalar evolutions analysis*
3109	in the hash table. /*
3110
3111	void
3112	scev_reset_htab (void)
3113	{
3114	if (!scalar_evolution_info)
3115	return;
3116
3117	scalar_evolution_info->empty ();
3118	}
3119
3120	/ Cleans up the information cached by the scalar evolutions analysis*
3121	in the hash table and in the loop->nb_iterations. /*
3122
3123	void
3124	scev_reset (void)
3125	{
3126	struct loop *loop;
3127
3128	scev_reset_htab ();
3129
3130	FOR_EACH_LOOP (loop, `0`)
3131	{
3132	loop->nb_iterations = NULL_TREE;
3133	}
3134	}
3135
3136	/ Return true if the IV calculation in TYPE can overflow based on the knowledge*
3137	of the upper bound on the number of iterations of LOOP, the BASE and STEP
3138	of IV.
3139
3140	We do not use information whether TYPE can overflow so it is safe to
3141	use this test even for derived IVs not computed every iteration or
3142	hypotetical IVs to be inserted into code. /*
3143
3144	bool
3145	iv_can_overflow_p (struct loop *loop, tree type, tree base, tree step)
3146	{
3147	widest_int nit;
3148	wide_int base_min, base_max, step_min, step_max, type_min, type_max;
3149	signop sgn = TYPE_SIGN (type);
3150
3151	if (integer_zerop (step))
3152	return false;
3153
3154	if (TREE_CODE (base) == INTEGER_CST)
3155	base_min = base_max = wi::to_wide (base);
3156	else if (TREE_CODE (base) == SSA_NAME
3157	&& INTEGRAL_TYPE_P (TREE_TYPE (base))
3158	&& get_range_info (base, &base_min, &base_max) == VR_RANGE)
3159	;
3160	else
3161	return true;
3162
3163	if (TREE_CODE (step) == INTEGER_CST)
3164	step_min = step_max = wi::to_wide (step);
3165	else if (TREE_CODE (step) == SSA_NAME
3166	&& INTEGRAL_TYPE_P (TREE_TYPE (step))
3167	&& get_range_info (step, &step_min, &step_max) == VR_RANGE)
3168	;
3169	else
3170	return true;
3171
3172	if (!get_max_loop_iterations (loop, &nit))
3173	return true;
3174
3175	type_min = wi::min_value (type);
3176	type_max = wi::max_value (type);
3177
3178	/ Just sanity check that we don't see values out of the range of the type.*
3179	In this case the arithmetics bellow would overflow. /*
3180	gcc_checking_assert (wi::ge_p (base_min, type_min, sgn)
3181	&& wi::le_p (base_max, type_max, sgn));
3182
3183	/ Account the possible increment in the last ieration. /
3184	bool overflow = false;
3185	nit = wi::add (nit, `1`, SIGNED, &overflow);
3186	if (overflow)
3187	return true;
3188
3189	/ NIT is typeless and can exceed the precision of the type. In this case*
3190	overflow is always possible, because we know STEP is non-zero. /*
3191	if (wi::min_precision (nit, UNSIGNED) > TYPE_PRECISION (type))
3192	return true;
3193	wide_int nit2 = wide_int::from (nit, TYPE_PRECISION (type), UNSIGNED);
3194
3195	/ If step can be positive, check that nitstep <= type_max-base.
3196	This can be done by unsigned arithmetic and we only need to watch overflow
3197	in the multiplication. The right hand side can always be represented in
3198	the type. /*
3199	if (sgn == UNSIGNED \|\| !wi::neg_p (step_max))
3200	{
3201	bool overflow = false;
3202	if (wi::gtu_p (wi::mul (step_max, nit2, UNSIGNED, &overflow),
3203	type_max - base_max)
3204	\|\| overflow)
3205	return true;
3206	}
3207	/ If step can be negative, check that nit(-step) <= base_min-type_min. /*
3208	if (sgn == SIGNED && wi::neg_p (step_min))
3209	{
3210	bool overflow = false, overflow2 = false;
3211	if (wi::gtu_p (wi::mul (wi::neg (step_min, &overflow2),
3212	nit2, UNSIGNED, &overflow),
3213	base_min - type_min)
3214	\|\| overflow \|\| overflow2)
3215	return true;
3216	}
3217
3218	return false;
3219	}
3220
3221	/ Given EV with form of "(type) {inner_base, inner_step}_loop", this*
3222	function tries to derive condition under which it can be simplified
3223	into "{(type)inner_base, (type)inner_step}_loop". The condition is
3224	the maximum number that inner iv can iterate. /*
3225
3226	static tree
3227	derive_simple_iv_with_niters (tree ev, tree *niters)
3228	{
3229	if (!CONVERT_EXPR_P (ev))
3230	return ev;
3231
3232	tree inner_ev = TREE_OPERAND (ev, `0`);
3233	if (TREE_CODE (inner_ev) != POLYNOMIAL_CHREC)
3234	return ev;
3235
3236	tree init = CHREC_LEFT (inner_ev);
3237	tree step = CHREC_RIGHT (inner_ev);
3238	if (TREE_CODE (init) != INTEGER_CST
3239	\|\| TREE_CODE (step) != INTEGER_CST \|\| integer_zerop (step))
3240	return ev;
3241
3242	tree type = TREE_TYPE (ev);
3243	tree inner_type = TREE_TYPE (inner_ev);
3244	if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type))
3245	return ev;
3246
3247	/ Type conversion in "(type) {inner_base, inner_step}_loop" can be*
3248	folded only if inner iv won't overflow. We compute the maximum
3249	number the inner iv can iterate before overflowing and return the
3250	simplified affine iv. /*
3251	tree delta;
3252	init = fold_convert (type, init);
3253	step = fold_convert (type, step);
3254	ev = build_polynomial_chrec (CHREC_VARIABLE (inner_ev), init, step);
3255	if (tree_int_cst_sign_bit (step))
3256	{
3257	tree bound = lower_bound_in_type (inner_type, inner_type);
3258	delta = fold_build2 (MINUS_EXPR, type, init, fold_convert (type, bound));
3259	step = fold_build1 (NEGATE_EXPR, type, step);
3260	}
3261	else
3262	{
3263	tree bound = upper_bound_in_type (inner_type, inner_type);
3264	delta = fold_build2 (MINUS_EXPR, type, fold_convert (type, bound), init);
3265	}
3266	*niters = fold_build2 (FLOOR_DIV_EXPR, type, delta, step);
3267	return ev;
3268	}
3269
3270	/ Checks whether use of OP in USE_LOOP behaves as a simple affine iv with*
3271	respect to WRTO_LOOP and returns its base and step in IV if possible
3272	(see analyze_scalar_evolution_in_loop for more details on USE_LOOP
3273	and WRTO_LOOP). If ALLOW_NONCONSTANT_STEP is true, we want step to be
3274	invariant in LOOP. Otherwise we require it to be an integer constant.
3275
3276	IV->no_overflow is set to true if we are sure the iv cannot overflow (e.g.
3277	because it is computed in signed arithmetics). Consequently, adding an
3278	induction variable
3279
3280	for (i = IV->base; ; i += IV->step)
3281
3282	is only safe if IV->no_overflow is false, or TYPE_OVERFLOW_UNDEFINED is
3283	false for the type of the induction variable, or you can prove that i does
3284	not wrap by some other argument. Otherwise, this might introduce undefined
3285	behavior, and
3286
3287	i = iv->base;
3288	for (; ; i = (type) ((unsigned type) i + (unsigned type) iv->step))
3289
3290	must be used instead.
3291
3292	When IV_NITERS is not NULL, this function also checks case in which OP
3293	is a conversion of an inner simple iv of below form:
3294
3295	(outer_type){inner_base, inner_step}_loop.
3296
3297	If type of inner iv has smaller precision than outer_type, it can't be
3298	folded into {(outer_type)inner_base, (outer_type)inner_step}_loop because
3299	the inner iv could overflow/wrap. In this case, we derive a condition
3300	under which the inner iv won't overflow/wrap and do the simplification.
3301	The derived condition normally is the maximum number the inner iv can
3302	iterate, and will be stored in IV_NITERS. This is useful in loop niter
3303	analysis, to derive break conditions when a loop must terminate, when is
3304	infinite. /*
3305
3306	bool
3307	simple_iv_with_niters (struct loop wrto_loop, struct* loop *use_loop,
3308	tree op, affine_iv iv, tree iv_niters,
3309	bool allow_nonconstant_step)
3310	{
3311	enum tree_code code;
3312	tree type, ev, base, e;
3313	wide_int extreme;
3314	bool folded_casts, overflow;
3315
3316	iv->base = NULL_TREE;
3317	iv->step = NULL_TREE;
3318	iv->no_overflow = false;
3319
3320	type = TREE_TYPE (op);
3321	if (!POINTER_TYPE_P (type)
3322	&& !INTEGRAL_TYPE_P (type))
3323	return false;
3324
3325	ev = analyze_scalar_evolution_in_loop (wrto_loop, use_loop, op,
3326	&folded_casts);
3327	if (chrec_contains_undetermined (ev)
3328	\|\| chrec_contains_symbols_defined_in_loop (ev, wrto_loop->num))
3329	return false;
3330
3331	if (tree_does_not_contain_chrecs (ev))
3332	{
3333	iv->base = ev;
3334	iv->step = build_int_cst (TREE_TYPE (ev), `0`);
3335	iv->no_overflow = true;
3336	return true;
3337	}
3338
3339	/ If we can derive valid scalar evolution with assumptions. /
3340	if (iv_niters && TREE_CODE (ev) != POLYNOMIAL_CHREC)
3341	ev = derive_simple_iv_with_niters (ev, iv_niters);
3342
3343	if (TREE_CODE (ev) != POLYNOMIAL_CHREC)
3344	return false;
3345
3346	if (CHREC_VARIABLE (ev) != (unsigned) wrto_loop->num)
3347	return false;
3348
3349	iv->step = CHREC_RIGHT (ev);
3350	if ((!allow_nonconstant_step && TREE_CODE (iv->step) != INTEGER_CST)
3351	\|\| tree_contains_chrecs (iv->step, NULL))
3352	return false;
3353
3354	iv->base = CHREC_LEFT (ev);
3355	if (tree_contains_chrecs (iv->base, NULL))
3356	return false;
3357
3358	iv->no_overflow = !folded_casts && nowrap_type_p (type);
3359
3360	if (!iv->no_overflow
3361	&& !iv_can_overflow_p (wrto_loop, type, iv->base, iv->step))
3362	iv->no_overflow = true;
3363
3364	/ Try to simplify iv base:*
3365
3366	(signed T) ((unsigned T)base + step) ;; TREE_TYPE (base) == signed T
3367	== (signed T)(unsigned T)base + step
3368	== base + step
3369
3370	If we can prove operation (base + step) doesn't overflow or underflow.
3371	Specifically, we try to prove below conditions are satisfied:
3372
3373	base <= UPPER_BOUND (type) - step ;;step > 0
3374	base >= LOWER_BOUND (type) - step ;;step < 0
3375
3376	This is done by proving the reverse conditions are false using loop's
3377	initial conditions.
3378
3379	The is necessary to make loop niter, or iv overflow analysis easier
3380	for below example:
3381
3382	int foo (int a, signed char s, signed char l)*
3383	{
3384	signed char i;
3385	for (i = s; i < l; i++)
3386	a[i] = 0;
3387	return 0;
3388	}
3389
3390	Note variable I is firstly converted to type unsigned char, incremented,
3391	then converted back to type signed char. /*
3392
3393	if (wrto_loop->num != use_loop->num)
3394	return true;
3395
3396	if (!CONVERT_EXPR_P (iv->base) \|\| TREE_CODE (iv->step) != INTEGER_CST)
3397	return true;
3398
3399	type = TREE_TYPE (iv->base);
3400	e = TREE_OPERAND (iv->base, `0`);
3401	if (TREE_CODE (e) != PLUS_EXPR
3402	\|\| TREE_CODE (TREE_OPERAND (e, `1`)) != INTEGER_CST
3403	\|\| !tree_int_cst_equal (iv->step,
3404	fold_convert (type, TREE_OPERAND (e, `1`))))
3405	return true;
3406	e = TREE_OPERAND (e, `0`);
3407	if (!CONVERT_EXPR_P (e))
3408	return true;
3409	base = TREE_OPERAND (e, `0`);
3410	if (!useless_type_conversion_p (type, TREE_TYPE (base)))
3411	return true;
3412
3413	if (tree_int_cst_sign_bit (iv->step))
3414	{
3415	code = LT_EXPR;
3416	extreme = wi::min_value (type);
3417	}
3418	else
3419	{
3420	code = GT_EXPR;
3421	extreme = wi::max_value (type);
3422	}
3423	overflow = false;
3424	extreme = wi::sub (extreme, wi::to_wide (iv->step),
3425	TYPE_SIGN (type), &overflow);
3426	if (overflow)
3427	return true;
3428	e = fold_build2 (code, boolean_type_node, base,
3429	wide_int_to_tree (type, extreme));
3430	e = simplify_using_initial_conditions (use_loop, e);
3431	if (!integer_zerop (e))
3432	return true;
3433
3434	if (POINTER_TYPE_P (TREE_TYPE (base)))
3435	code = POINTER_PLUS_EXPR;
3436	else
3437	code = PLUS_EXPR;
3438
3439	iv->base = fold_build2 (code, TREE_TYPE (base), base, iv->step);
3440	return true;
3441	}
3442
3443	/ Like simple_iv_with_niters, but return TRUE when OP behaves as a simple*
3444	affine iv unconditionally. /*
3445
3446	bool
3447	simple_iv (struct loop wrto_loop, struct* loop *use_loop, tree op,
3448	affine_iv iv, bool* allow_nonconstant_step)
3449	{
3450	return simple_iv_with_niters (wrto_loop, use_loop, op, iv,
3451	NULL, allow_nonconstant_step);
3452	}
3453
3454	/ Finalize the scalar evolution analysis. /
3455
3456	void
3457	scev_finalize (void)
3458	{
3459	if (!scalar_evolution_info)
3460	return;
3461	scalar_evolution_info->empty ();
3462	scalar_evolution_info = NULL;
3463	free_numbers_of_iterations_estimates (cfun);
3464	}
3465
3466	/ Returns true if the expression EXPR is considered to be too expensive*
3467	for scev_const_prop. /*
3468
3469	bool
3470	expression_expensive_p (tree expr)
3471	{
3472	enum tree_code code;
3473
3474	if (is_gimple_val (expr))
3475	return false;
3476
3477	code = TREE_CODE (expr);
3478	if (code == TRUNC_DIV_EXPR
3479	\|\| code == CEIL_DIV_EXPR
3480	\|\| code == FLOOR_DIV_EXPR
3481	\|\| code == ROUND_DIV_EXPR
3482	\|\| code == TRUNC_MOD_EXPR
3483	\|\| code == CEIL_MOD_EXPR
3484	\|\| code == FLOOR_MOD_EXPR
3485	\|\| code == ROUND_MOD_EXPR
3486	\|\| code == EXACT_DIV_EXPR)
3487	{
3488	/ Division by power of two is usually cheap, so we allow it.*
3489	Forbid anything else. /*
3490	if (!integer_pow2p (TREE_OPERAND (expr, `1`)))
3491	return true;
3492	}
3493
3494	switch (TREE_CODE_CLASS (code))
3495	{
3496	case tcc_binary:
3497	case tcc_comparison:
3498	if (expression_expensive_p (TREE_OPERAND (expr, `1`)))
3499	return true;
3500
3501	/ Fallthru. /
3502	case tcc_unary:
3503	return expression_expensive_p (TREE_OPERAND (expr, `0`));
3504
3505	default:
3506	return true;
3507	}
3508	}
3509
3510	/ Do final value replacement for LOOP. /
3511
3512	void
3513	final_value_replacement_loop (struct loop *loop)
3514	{
3515	/ If we do not know exact number of iterations of the loop, we cannot*
3516	replace the final value. /*
3517	edge exit = single_exit (loop);
3518	if (!exit)
3519	return;
3520
3521	tree niter = number_of_latch_executions (loop);
3522	if (niter == chrec_dont_know)
3523	return;
3524
3525	/ Ensure that it is possible to insert new statements somewhere. /
3526	if (!single_pred_p (exit->dest))
3527	split_loop_exit_edge (exit);
3528
3529	/ Set stmt insertion pointer. All stmts are inserted before this point. /
3530	gimple_stmt_iterator gsi = gsi_after_labels (exit->dest);
3531
3532	struct loop *ex_loop
3533	= superloop_at_depth (loop,
3534	loop_depth (exit->dest->loop_father) + `1`);
3535
3536	gphi_iterator psi;
3537	for (psi = gsi_start_phis (exit->dest); !gsi_end_p (psi); )
3538	{
3539	gphi *phi = psi.phi ();
3540	tree rslt = PHI_RESULT (phi);
3541	tree def = PHI_ARG_DEF_FROM_EDGE (phi, exit);
3542	if (virtual_operand_p (def))
3543	{
3544	gsi_next (&psi);
3545	continue;
3546	}
3547
3548	if (!POINTER_TYPE_P (TREE_TYPE (def))
3549	&& !INTEGRAL_TYPE_P (TREE_TYPE (def)))
3550	{
3551	gsi_next (&psi);
3552	continue;
3553	}
3554
3555	bool folded_casts;
3556	def = analyze_scalar_evolution_in_loop (ex_loop, loop, def,
3557	&folded_casts);
3558	def = compute_overall_effect_of_inner_loop (ex_loop, def);
3559	if (!tree_does_not_contain_chrecs (def)
3560	\|\| chrec_contains_symbols_defined_in_loop (def, ex_loop->num)
3561	/ Moving the computation from the loop may prolong life range*
3562	of some ssa names, which may cause problems if they appear
3563	on abnormal edges. /*
3564	\|\| contains_abnormal_ssa_name_p (def)
3565	/ Do not emit expensive expressions. The rationale is that*
3566	when someone writes a code like
3567
3568	while (n > 45) n -= 45;
3569
3570	he probably knows that n is not large, and does not want it
3571	to be turned into n %= 45. /*
3572	\|\| expression_expensive_p (def))
3573	{
3574	if (dump_file && (dump_flags & TDF_DETAILS))
3575	{
3576	fprintf (dump_file, "not replacing:\n ");
3577	print_gimple_stmt (dump_file, phi, `0`);
3578	fprintf (dump_file, "\n");
3579	}
3580	gsi_next (&psi);
3581	continue;
3582	}
3583
3584	/ Eliminate the PHI node and replace it by a computation outside*
3585	the loop. /*
3586	if (dump_file)
3587	{
3588	fprintf (dump_file, "\nfinal value replacement:\n ");
3589	print_gimple_stmt (dump_file, phi, `0`);
3590	fprintf (dump_file, " with\n ");
3591	}
3592	def = unshare_expr (def);
3593	remove_phi_node (&psi, false);
3594
3595	/ If def's type has undefined overflow and there were folded*
3596	casts, rewrite all stmts added for def into arithmetics
3597	with defined overflow behavior. /*
3598	if (folded_casts && ANY_INTEGRAL_TYPE_P (TREE_TYPE (def))
3599	&& TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (def)))
3600	{
3601	gimple_seq stmts;
3602	gimple_stmt_iterator gsi2;
3603	def = force_gimple_operand (def, &stmts, true, NULL_TREE);
3604	gsi2 = gsi_start (stmts);
3605	while (!gsi_end_p (gsi2))
3606	{
3607	gimple *stmt = gsi_stmt (gsi2);
3608	gimple_stmt_iterator gsi3 = gsi2;
3609	gsi_next (&gsi2);
3610	gsi_remove (&gsi3, false);
3611	if (is_gimple_assign (stmt)
3612	&& arith_code_with_undefined_signed_overflow
3613	(gimple_assign_rhs_code (stmt)))
3614	gsi_insert_seq_before (&gsi,
3615	rewrite_to_defined_overflow (stmt),
3616	GSI_SAME_STMT);
3617	else
3618	gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
3619	}
3620	}
3621	else
3622	def = force_gimple_operand_gsi (&gsi, def, false, NULL_TREE,
3623	true, GSI_SAME_STMT);
3624
3625	gassign *ass = gimple_build_assign (rslt, def);
3626	gsi_insert_before (&gsi, ass, GSI_SAME_STMT);
3627	if (dump_file)
3628	{
3629	print_gimple_stmt (dump_file, ass, `0`);
3630	fprintf (dump_file, "\n");
3631	}
3632	}
3633	}
3634
3635	/ Replace ssa names for that scev can prove they are constant by the*
3636	appropriate constants. Also perform final value replacement in loops,
3637	in case the replacement expressions are cheap.
3638
3639	We only consider SSA names defined by phi nodes; rest is left to the
3640	ordinary constant propagation pass. /*
3641
3642	unsigned int
3643	scev_const_prop (void)
3644	{
3645	basic_block bb;
3646	tree name, type, ev;
3647	gphi *phi;
3648	struct loop *loop;
3649	bitmap ssa_names_to_remove = NULL;
3650	unsigned i;
3651	gphi_iterator psi;
3652
3653	if (number_of_loops (cfun) <= `1`)
3654	return `0`;
3655
3656	FOR_EACH_BB_FN (bb, cfun)
3657	{
3658	loop = bb->loop_father;
3659
3660	for (psi = gsi_start_phis (bb); !gsi_end_p (psi); gsi_next (&psi))
3661	{
3662	phi = psi.phi ();
3663	name = PHI_RESULT (phi);
3664
3665	if (virtual_operand_p (name))
3666	continue;
3667
3668	type = TREE_TYPE (name);
3669
3670	if (!POINTER_TYPE_P (type)
3671	&& !INTEGRAL_TYPE_P (type))
3672	continue;
3673
3674	ev = resolve_mixers (loop, analyze_scalar_evolution (loop, name),
3675	NULL);
3676	if (!is_gimple_min_invariant (ev)
3677	\|\| !may_propagate_copy (name, ev))
3678	continue;
3679
3680	/ Replace the uses of the name. /
3681	if (name != ev)
3682	{
3683	if (dump_file && (dump_flags & TDF_DETAILS))
3684	{
3685	fprintf (dump_file, "Replacing uses of: ");
3686	print_generic_expr (dump_file, name);
3687	fprintf (dump_file, " with: ");
3688	print_generic_expr (dump_file, ev);
3689	fprintf (dump_file, "\n");
3690	}
3691	replace_uses_by (name, ev);
3692	}
3693
3694	if (!ssa_names_to_remove)
3695	ssa_names_to_remove = BITMAP_ALLOC (NULL);
3696	bitmap_set_bit (ssa_names_to_remove, SSA_NAME_VERSION (name));
3697	}
3698	}
3699
3700	/ Remove the ssa names that were replaced by constants. We do not*
3701	remove them directly in the previous cycle, since this
3702	invalidates scev cache. /*
3703	if (ssa_names_to_remove)
3704	{
3705	bitmap_iterator bi;
3706
3707	EXECUTE_IF_SET_IN_BITMAP (ssa_names_to_remove, `0`, i, bi)
3708	{
3709	gimple_stmt_iterator psi;
3710	name = ssa_name (i);
3711	phi = as_a <gphi *> (SSA_NAME_DEF_STMT (name));
3712
3713	gcc_assert (gimple_code (phi) == GIMPLE_PHI);
3714	psi = gsi_for_stmt (phi);
3715	remove_phi_node (&psi, true);
3716	}
3717
3718	BITMAP_FREE (ssa_names_to_remove);
3719	scev_reset ();
3720	}
3721
3722	/ Now the regular final value replacement. /
3723	FOR_EACH_LOOP (loop, LI_FROM_INNERMOST)
3724	final_value_replacement_loop (loop);
3725
3726	return `0`;
3727	}
3728
3729	#include "gt-tree-scalar-evolution.h"
3730

Browse the source code of gcc/tree-scalar-evolution.c